Re: [RFC] Lock elision implementation guidelines

[Rich Felker <dalias at aerifal dot cx>]

On Wed, Feb 20, 2013 at 02:23:34PM -0800, Andi Kleen wrote:
> On Wed, Feb 20, 2013 at 11:35:35AM +0100, Torvald Riegel wrote:
> > On Tue, 2013-02-19 at 22:11 +0100, Andi Kleen wrote:
> > > > That's a good counter example -- I hadn't thought about signal handling.
> > > 
> > > Any signal will abort of course.
> > > 
> > > > The same question also applies to program exit: Is a program with a
> > > 
> > > Program exit will also abort.
> > 
> > I've thought about both cases before, in particular the case of HTMs
> > like Intel RTM that don't let any side effects escape.  This may seem
> > sufficient at first, but the problem is that we can't know whether
> > continuing to execute the program when it should in fact deadlock will
> > not commit the transaction.
> 
> I think that deadlock requirement is a red-hering. If that is really
> in the text should go to the Austin commitee and ask for clarification.
> I cannot imagine they really meant that.

The text is quite direct and intentional:

    If the mutex type is PTHREAD_MUTEX_NORMAL, deadlock detection
    shall not be provided. Attempting to relock the mutex causes
    deadlock. If a thread attempts to unlock a mutex that it has not
    locked or a mutex which is unlocked, undefined behavior results.

    If the mutex type is PTHREAD_MUTEX_DEFAULT, attempting to
    recursively lock the mutex results in undefined behavior.
    Attempting to unlock the mutex if it was not locked by the calling
    thread results in undefined behavior. Attempting to unlock the
    mutex if it is not locked results in undefined behavior.

You're free to think this is wrong, but I don't think that's going to
change anything. The problem is just that glibc defined
PTHREAD_MUTEX_NORMAL and PTHREAD_MUTEX_DEFAULT to the same value.
Splitting them out would allow the behavior you want.

> Just imagine seriously telling someone:
> "we made locking XX% slower to preserve deadlocks"

I don't think this is any more difficult than saying "we made sqrt XX%
slower to preserve the property that the result is correctly rounded".
A lot of people might not care that the correct behavior is preserved;
they're free to use their own fastsqrt function (or gcc -ffast-math)
or likewise use PTHREAD_MUTEX_DEFAULT instead of PTHREAD_MUTEX_NORMAL.

> > > Note that POSIX pthreads does not export enough primitives for
> > > efficient spinning.  However that's good for lock elision.
> > 
> > Can you elaborate?  You can both do a trylock() and block, so it seems
> > most of it is there in principal.  There's no getlock() or something
> > like that with which you could do test-and-test-and-set like locks, but
> > OTOH perhaps you can get as similar effect with backoff.
> 
> You normally need to spin reading, to prevent a flood of unnecessary
> cache line conflicts. Even with backoffs that works much better.

I'm not clear on how you'd cause a flood of cache line conflicts
accessing nothing but your own thread's stack and possibly memory in
the immediate vicinity of the lock itself. If you're accessing more
than that in your loop calling pthread_mutex_trylock, you're probably
doing something wrong...

Rich