[RFC] Lock elision implementation guidelines

[Torvald Riegel]

On Wed, 2013-02-20 at 22:26 -0500, Rich Felker wrote:
> > > > 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...

trylock() tries to grab the lock, which, depending on how the hardware
handles this, can put the cache line that the lock resides in in a
different state than what would happen if you just read the lock.  The
test-and-test-and-set lock I mentioned previously would be something
like:

do {
  while (getlock(&mutex) == ACQUIRED);
} while (!trylock(&mutex);

If you don't have the getlock(), you better do the trylock() at the
right time with appropriate back-off, but as Andi says, this can be
hard.


Torvald