[PATCH] Lock elision: Give PTHREAD_MUTEX_NORMAL-like mutexes a new internal type.

[Torvald Riegel <triegel at redhat dot com>]

This patch gives mutexes that have been explicitly initialized to the
PTHREAD_MUTEX_NORMAL type or semantically similar types a new *internal*
mutex type, which in turn allows the mutex implementations to
distinguish between PTHREAD_MUTEX_NORMAL(-like) mutexes and
PTHREAD_MUTEX_DEFAULT mutexes.  This is necessary to be able to use lock
elision widely without violation the POSIX reguirements for NORMAL
mutexes.  See http://sourceware.org/glibc/wiki/LockElisionGuide for
details on the differences in the semantics.


What it does:
* Adds a new *internal* type:  PTHREAD_MUTEX_NORMAL_INT_NP.
* Adds a new *internal* alias for the types that have been previously
aliased with PTHREAD_MUTEX_DEFAULT (enum value 0):
PTHREAD_MUTEX_DEFAULT_INT_NP.  (The purpose is to make the code
cleaner.)
* Default-initialized mutexes (via PTHREAD_MUTEX_INITIALIZER,
pthread_mutexattr_init, pthread_mutex_init with NULL attr) all remain at
the PTHREAD_MUTEX_DEFAULT_INT_NP type.  We can use elision for them.
* PTHREAD_MUTEX_NORMAL(-like) mutexes can only be created via
pthread_mutexattr_settype because there are no static initializers for
them.  Thus, in settype, we translate all these kinds of mutexes to
PTHREAD_MUTEX_NORMAL_INT_NP.  We cannot use elision for them (or just in
a limited way, see the guidelines).
* All mutexes with additional flags (robust, PI, ...) are not affected.
* In pthread_mutex_lock etc. we just handle PTHREAD_MUTEX_NORMAL_INT_NP
like any other type.  Right now we do the same as for
PTHREAD_MUTEX_DEFAULT_INT_NP, but this will change once we have elision
because we need to treat DEFAULT and NORMAL differently.


Benefits:
* We can enable elision for most of the mutexes (i.e., the
default-initialized instances).  Previously, we couldn't without
violating POSIX because we were using the same enum value for NORMAL and
DEFAULT mutexes.  Thus, we can get wide testing. This includes existing
binaries that haven't been recompiled.
* We don't violate POSIX by changing the semantic guarantees of any
existing mutex types.
* We don't change external interfaces at all, and we don't need to bump
symbol versions.


Shortcomings:
* Mutexes _explicitly_ initialized to PTHREAD_MUTEX_DEFAULT via
pthread_mutex_settype are treated like PTHREAD_MUTEX_NORMAL.  This is
correct because DEFAULT provides strictly weaker guarantees, but means
that we can't use elision for those mutexes.  However, setting this
explicitly is redundant, and probably used rarely.


Things that could be added / changed:
* We could try to not subsume explicitly initialized DEFAULT mutexes
under the NORMAL mutexes.  But this seems to require bumping symbol
versions.  So might not be worth it.


Contrast to the approach in Andi's patches:
* Andi's patches introduce ELISION_NP and NO_ELISION_NP flags that are
combined with existing mutex types, and are exposed externally to users.
ELISION_NP changes the semantics of some types, notably the NORMAL-like
mutexes, which violates POSIX requirements.  If neither ELISION_NP nor
NO_ELISION_NP is set, additional flags determine whether elision is
used.
* My patch splits out NORMAL mutexes into their own internal type. This
does not grow the state space that needs to be handled but leads to
fewer states (no combinations).  The mutex_lock fastpath code, for
example, gets one unlikely conditional in addition to the 3 it already
had (all on the mutex type).
* ELISION_NP is, in addition to it's change to semantics, also a way to
request elision for a certain mutex (likewise for NO_ELISION_NP).  If
these were changed to pure performance hints, they could later still be
easily combined with the approach of my patch.  The benefit of this
would be that then we would have separated performance hints from
semantics-affecting modifiers, which is very important, allows for more
leeway in how to interpret those hints, and IMO will also lead to
cleaner code.


The main motivation for this patch, besides solving the technical
problem it addresses, is to carve out the parts of Andi's patches that
we can hopefully reach consensus on *now*.  This patch solves one of the
most important issues that we have been discussing.  It also allows us
to put a lean implementation of lock elision on top of it; this will not
contain everything of what Andi proposed, but this gives us the 90% that
we're interested in (ie, enabling elision for most mutexes including in
existing binaries), and we can (hopefully) agree on this now so that
this can make 2.18.
I've outlined the remaining stages 2 and 3 (this patch is stage 1) for
such a lean implementation in my reply to v12 of Andi's patches.  It
would also not change or extend the external interfaces (modulo a
configure switch), so the maintenance risk would be very small.

Thanks to everyone involved for their ideas and input, in particular to
Rich who had the same idea, and Roland who triggered this idea in my
head. :)


Torvald

Note that there are no changelogs in the patch, but I can add them once
we have consensus on whether to take this approach or not.

Attachment: patch
Description: Text document