Re: [RFC] Lock elision implementation guidelines

[Rich Felker <dalias at aerifal dot cx>]

On Sun, Feb 10, 2013 at 09:20:52PM +0100, Torvald Riegel wrote:
> --- Compability of lock()/unlock() with pthreads mutex types
> 
> This scheme allows a thread to acquire a lock that it has already
> acquired, and there is no error checking when releasing a lock.  Thus,
> for which pthreads mutex types is it a suitable implementation?:
> 
> PTHREAD_MUTEX_DEFAULT: Yes.  Recursive locking or releasing an unlocked
> mutex result in undefined behavior, so the implementation is free to do
> anything in such cases.
> 
> PTHREAD_MUTEX_NORMAL: Strictly speaking, no.  Allows undefined behavior
> on releasing an unlocked mutex, but requires deadlock when trying to
> lock an acquired lock.  Deadlock is not the same as undefined behavior:
> even though there's no progress on deadlock, nothing bad will happen
> either.
> ??? PTHREAD_MUTEX_NORMAL is the same type as PTHREAD_MUTEX_DEFAULT in
> current glibc.  This would mean that we'd have to assume the program
> wanted NORMAL, so we couldn't use elision for the default mutex type.
> However, it's probably rare for correct programs to rely on the deadlock
> guarantee in a meaningful way -- should we ignore the deadlock
> requirement?

No. You cannot ignore any requirements. That's why they're called
requirements and not recommendations. If it would be beneficial to
make DEFAULT and NORMAL different, a new constant should be added for
DEFAULT with the relaxed semantics. Unfortunately this may require new
symbol versions since the type is encoded statically into the mutex
structure with the mutex initializers.

> --- trylock() and alternative LE implementations
> 
> With the monitor-the-lock implementation scheme described previously,
> there is no way to reliably detect whether a lock has already been
> acquired by a thread.  This makes it unsuitable for most mutex types,
> and also has implications for trylock():  For recursive mutexes,
> trylock() will just acquire the lock, as expected; for nonrecursive
> mutexes, trylock() must return an error if the mutex is already
> acquired.  This doesn't work in all cases:
> - If acquired without elision, then trylock() can see this.
> - If acquired with elision by another thread, then trylock() will just
> try to acquire, which is fine. (If with elision, this is like plain
> elision; if without elision, this will abort the transaction of the
> other thread that used elision.)
> - If acquired with elision by the same thread, trylock() must return an
> error but it can't because it cannot check whether the lock has been
> acquired already.
> 
> There are a few potential solutions:
> 
> 1) Track which mutexes have been acquired (in software)
> - Can't track this using bits in the lock itself or in shared data, or
> the write will prevent elision due to data conflicts with other
> transactions.  Could track using TLS.
> - Con: larger runtime overheads and increases the amount of data
> transactions touch (important because an HTM's access tracking capacity
> is limited).  Could still increase scalability of contended CS, but
> overheads for uncontended.
> - Pro: allows elision to be used for all mutex types.

I would track with a single TLS pointer to the mutex locked. If more
than one mutex is being held at the same time, this is almost surely
an indication that elision should not be used. This would make for a
much simpler implementation than the current proposal and would be
much more useful -- it could actually be used for all lock types,
including the current DEFAULT which aliases NORMAL.

> 2) trylock() on non-recursive mutexes aborts transactions/elision
> - Con: bad for custom spinlocks in programs built on top of trylock()

This is an idiotic idiom and not worth making design decisions based
on it.

> - Pro: Simple to implement. 

I don't think it's simpler than my variant of option 1 above.

> 3) Add a new kind of trylock() with different semantics; use option 2
> for the original trylock():
> A) possibly_recursive_trylock(): would behave like a recursive mutex if
> used with elision and like a nonrecursive mutex' trylock() if used
> without elision on a nonrecursive mutex.
> - Con: Adds a new kind of trylock().  Unclear whether it's a useful
> addition in the long term because it's just used to support a certain
> kind of HW support.
> - Con: The semantics are cumbersome.  The program can't detect whether
> elision is currently being used in a clean way, and it can't force it
> either.
> B) nonrecursive_trylock(): has undefined behavior when used to acquire a
> mutex recursively -- the program must never do that.
> - Con: Adds a new kind of trylock().
> - Con: Adds more undefined behavior.
> - Pro: Semantics are clearer, and might be practical in the context of
> typical uses of nonrecursive mutex types.

This option is just hideous, as it's not at all transparent, but
requires applications to use highly nonstandard interfaces designed
around the lock-elision implementation rather than designed to be
naturally idiomatic.

> 4) New nonrecursive mutex types with different trylock() semantics.

Again, same as above...

> 5) Advise programmers to switch from nonrecursive to recursive mutexes

Any solution that starts with "advise programmers" is outside the
scope of a solution to this problem.

> ??? Which of these options do we prefer? Option 2) is a safe approach,
> might still allow using LE often in most programs (if we ignore the
> conservative deadlock requirement of default==normal mutexes), and is
> easy to do.  Option 1) has runtime overheads and currently no
> implementation, but would allow for using LE on all mutex types.  Option
> 3) adds another glibc-only extension; not sure whether this is worth it.
> Option 5) might be a useful workaround, but still faces the error
> checking issue of recursive mutexes.

I think option 1 is by far the preferred option.

> ??? Does the Austin Group have an opinion about how to solve this?

The Austin Group's "opinion" is the text of the standard, which
specifies certain behavior for the standard mutex types that conflicts
with all of the options above except option 1 or putting all the
lock-elision in new nonstandard mutex types.

Rich