Re: Lock elision problems in glibc-2.18

[Torvald Riegel <triegel at redhat dot com>]

On Fri, 2013-08-23 at 10:49 +0200, Dominik Vogt wrote: 
> The current implementation of pthread_mutex lock elision is
> problematic if software uses a glibc with elision and other pieces
> of code that use transactions (other libraries for example).  The
> root cause of the problem is that transactions may be used in
> several independent contexts, but the cpu automatically nests
> these into the same transaction.

I agree that using HW transactions requires some care.  But I don't see
why the current lock elision implementation is problematic (except for
the abort codes not being part of any official ABI).

> > /* elision-lock.c: Elided pthread mutex lock.
> ...
> > int
> > __lll_lock_elision (int *futex, short *adapt_count, EXTRAARG int private)
> > {
> >   if (*adapt_count <= 0)
> >     {
> >       unsigned status;
> >       int try_xbegin;
> >
> >       for (try_xbegin = aconf.retry_try_xbegin;
> > 	   try_xbegin > 0;
> > 	   try_xbegin--)
> > 	{
> > 	  if ((status = _xbegin()) == _XBEGIN_STARTED)
> > 	    {
> > 	      if (*futex == 0)
> > 		return 0;
> >
> > 	      /* Lock was busy.  Fall back to normal locking.
> > 		 Could also _xend here but xabort with 0xff code
> > 		 is more visible in the profiler.  */
> > 	      _xabort (_ABORT_LOCK_BUSY);
> 
> Let's assume we have this user code:
> 
>   XBEGIN (abort_handler)
>   pthread_mutex_lock(&mutex);
>   /* do something */
>   pthread_mutex_unlock(&mutex);
>   XEND
>   ...
>   abort_handler:
>     ...
> 
> If the "_xabort (_ABORT_LOCK_BUSY)" is executed, this will abort
> the outermost transaction, i.e. the XBEGIN in the first line, and
> jump to abort_handler and _not_ use the abort handling code in
> elision-lock.c.
> 
> 1) This is inefficient because the _xabort terminates more
>    (nested) transactions than necessary; it would be sufficient to
>    use _xend here and just do the normal retries or spin a while.

In either case, the outermost transaction would abort.  There's no way
to emulate closed nesting in TSX-like HTMs.  As soon as the transaction
observes the lock in acquired state, it is doomed because it can't
continue to execute in this state; once the state changes so that it
could continue, it has to abort.

> 2) The user's abort_handler is probably not able to deal with the
>    abort code _ABORT_LOCK_BUSY because it does not know about it.

I agree that the abort codes can be misinterpreted.  Part of the problem
is that they form something like an ABI, but this ABI is "implicit" and
not specified anywhere.  That seems to be the case at least for TSX;
I've asked Andi in the past for a definitive spec for those abort codes
(i.e., the place where this ABI is defined), but didn't get a reply.
I'm also not aware of any effort to publish such a spec.
Is there any effort underway at IBM to assign certain meanings to
certain abort codes?

> 3) Even if the outermost transaction was started from glibc:
> 
>      pthread_mutex_lock(&mutex1);
>      pthread_mutex_lock(&mutex2);
>      /* do something */
>      pthread_mutex_unlock(&mutex2);
>      pthread_mutex_unlock(&mutex1);
> 
>    if mutex2 _xaborts, the abort handler is called for mutex*1*.
>    I.e., although mutex2 was busy, mutex1 is penalized for it.

I'm not quite sure which penalty you are referring to.  The outermost
transaction has to abort anyway -- we're having flat nesting after all.

> 4) Vice versa, the abort handling code in elision-lock.c might be
>    triggered by a third party abort that uses abort codes unknown
>    to glibc, or even the same codes with a different meaning.

That's true, but glibc's lock elision code will not do anything
incorrect if it misinterprets an abort code that it gets.  It might make
a decision that's not quite optimal regarding performance, but that's
it.

> 
> > /* elision-trylock.c: Lock eliding trylock for pthreads.
> ...
> > int
> > __lll_trylock_elision (int *futex, short *adapt_count)
> > {
> >   /* Implement POSIX semantics by forbiding nesting
> >      trylock.  Sorry.  After the abort the code is re-executed
> >      non transactional and if the lock was already locked
> >      return an error.  */
> >   _xabort (_ABORT_NESTED_TRYLOCK);
> 
> See (2) above; _ABORT_NESTED_TRYLOCK may be caught and
> misinterpreted by a third party abort handler.

This is fine (assuming that the third-party handler is aware of the
limitations of abort codes, which it should be).

> >   /* Only try a transaction if it's worth it.  */
> >   if (*adapt_count <= 0)
> >     {
> >       unsigned status;
> >
> >       if ((status = _xbegin()) == _XBEGIN_STARTED)
> > 	{
> > 	  if (*futex == 0)
> > 	    return 0;
> >
> > 	  /* Lock was busy.  Fall back to normal locking.
> > 	     Could also _xend here but xabort with 0xff code
> > 	     is more visible in the profiler.  */
> > 	  _xabort (_ABORT_LOCK_BUSY);
> 
> Same problem as in elision-lock.c.
> 
> 
> > /* elision-unlock.c: Commit an elided pthread lock.
> ...
> > int
> > __lll_unlock_elision(int *lock, int private)
> > {
> >   /* When the lock was free we're in a transaction.
> >      When you crash here you unlocked a free lock.  */
> >   if (*lock == 0)
> >     _xend();
> >   else
> >     lll_unlock ((*lock), private);
> >   return 0;
> > }
> 
> 5) We cannot assume that we are unlocking a free lock if no
> transaction is open at this point.

We can.  The only way we could have reached that point in a correct
program is if we acquired the lock using lock elision.

> This is because even if the
> transaction was created by pthread_mutex_lock(), third party code
> may have closed it before calling pthread_mutex_unlock():
> 
> The third party code might assume, that if a transaction is open
> at some point it must have been created by that third party code
> earlier (very much like __lll_unlock_elision):
> 
>   /* 3rd party code */
>   my_unlock()
>   {
>     if (_xtest())
>     {
>       /* We have an open transaction, close it.  */
>       _xend();
>     }
>     else
>     {
>       /* Nothing to do, we've already closed the transaction, or
>          it has aborted earlier.  */
>     }
>   }
> 
> While it is certainly the fault of the code in my_unlock()

my_unlock() is not a correct use of transactions.  You must only commit
the transaction you have started (or those you are allowed to commit).

> that
> the program won't work as expected (closing transactions
> prematurely), the general protection fault cause by the following
> code is definitely cause by the code in __lll_unlock_elision():
> 
>   pthread_mutex_lock();
>   my_unlock()
>   pthread_mutex_lock(); <-- crashes
> 
> (This crashes because an XEND outside of transactional mode causes
> a general protection fault.)
> 
> Note that HTM on z/Architecture suffers from similar problems.
> However, using TEND outside a transaction is safe while TABORT
> outside a transaction causes a special-operation exception.
> 
> Summary
> -------
> 
> Different pieces of code that use transactions that are logically
> independent share a single (nested) transaction in the cpu.  A
> user (e.g. a library) of transactions must not assume that
> 
>  * the outermost transactions is always created by the user,
>  * the innermost transaction has been created by the user,
>  * the abort code caught by its abort handler has been set by the
>    user,
>  * the abort code is passed to the user's abort handler, if the
>    user aborts a transaction,
>  * aborts are ever handled by the user's own abort handler.
> 
> Failing to do so might break Posix semantics of the elision
> code(!)

Right.  However, these rules should be clear for people familiar with
the semantics of current HTMs.  Do you think that it would be helpful if
we'd add them to the glibc HLE guidelines wiki page, for example?

> Rules for transactional coding (draft)
> --------------------------------------
> 
> The following rules help to reduce potential problems if each
> piece of software that uses transactions sticks to the rules:
> 
> A) Abort handlers should not interpret abort codes beyond what is
>    documented in the cpu specification (i.e. on Intel, it should
>    ignore the user defined bits 31:24 of the abort status; on z,
>    it should ignore the abort code completely and look only at the
>    condition code).

I think that's too strict.  You can interpret them, but only in
situations where it's fine to misinterpret (e.g., if this can have a
limited effect on performance, it should be fine to interpret; in
contrast, you must not interpret if this might change semantics).

> Abort codes are thus only useful for
>    debugging and not as a means of controlling program flow.

I'd just explain the limitations.

>    If it is necessary to use abort codes to pass information from
>    the transaction to the user, the abort codes _must_ be globally
>    unique, at least if used in libraries.  It might be necessary
>    to register them through Icann or so.

I don't think ICANN is the right place.  These are arch-specific, and
thus should be part of the the respective arch's+platform's ABI.
Nonetheless, this is missing currently.

> B) Because of (A), user defined abort codes should not be used to
>    control program flow.  If they are, it is the responsibility of
>    the programmer to make sure that all software components that
>    deal with transactions agree on the interpretation of the abort
>    codes and can deal with codes set by third party software.
> 
> C) If a transaction body calls any functions, it cannot be assumed
>    that a transaction is still open when an XEND or XABORT
>    instruction is reached.  It is necessary to check whether a
>    transaction is still open and skip the XABORT or XEND if not.

I disagree strongly here.  You must never commit a transaction that you
haven't started.  Doing so will break atomicity assumptions, at the very
least.

> D) Explicitly aborting transactions should be avoided except for
>    debugging purposes.

I don't see a reason for such a guideline.  The aborts have their
limitations, but 

> E) The innermost transactions should only be closed (with XEND,
>    TEND etc.) if it was created by the same user.

That kind of follows once C) is removed / inverted.

> F) Make sure that control of program flow works as expected even
>    if your abort handler is never called when transactions abort 
>    (because it's not the outermost transaction).

I'd move that into the abort vs. flat nesting discussion.

> Applying the rules to the current elision code
> ----------------------------------------------
> 
> (A) and (B) are easy to implement.  Instead of aborting with
> _ABORT_LOCK_BUSY we can use XEND here and handle the (logical)
> transaction failure directly.

I think the aborts are fine.  XEND could be better if the aborts where
more costly in terms of performance than spinning and running into a
normal conflict with another transactions.  But we don't have data for
this, so I'd keep it as is as long as we have proof/indication to the
contrary.

Also, Andi's argument re better visibility of aborts in profilers
applies here.  Perhaps some performance counter or such could reveal the
location of the conflict, and the profiler could figure out that there's
a phtread mutex on the same cacheline, but that sounds rather
complicated.

> (C) can be implemented with "if (_xtest()) ..." where necessary.

See above.

> (D) can be implemented for lock(), but trylock() currently depends
> on the external abort because of Posix requirements.

This shouldn't need action either IMO.

> (E) would require to write down the current nesting depth each
> time a transaction is started and only use XEND, TEND, etc. if the
> nesting depth is still the same.  It's unclear though how to
> behave if the nesting depth has changed, though.  Furthermore,
> while it is possible to query the current nesting depth on z, I
> think there is no way to do that on Intel.

In the HLE implementation, we already take care of this implicitly.  We
don't know the exact nesting depth, but in a correct program, we'll
always pair an elided lock acquisition with an elided lock release.  So
no need for action either.

Keeping track of the nesting depth would increase the HTM capacity
footprint of elided critical sections by at least one cacheline (you
need to do it in thread-local state to avoid conflicts), which is
something I'd like to avoid.

> I have no solution for (F) yet; if pthread mutexes are only used
> from inside third party transactions, the adapt_count would never
> be modified in the abort path, because the abort path is never
> executed.  This completely breaks the adaption logic.

The robustness of the adaptation is indeed a problem.  In the worst case
a forward progress problem (ie, correctness).  A strict ABI for the
semantics of certain abort codes could be a solution, or perhaps we can
fake this effectively.  I'll think more about it.

Could you update this draft along with our discussion about it?  IMO, it
would make sense to add this to the HLE guidelines, I believe, so that
at least glibc's understanding of / assumptions about how to use
transactions is documented.


Torvald