Re: [boost] [lockfree] review

Subject: Re: [boost] [lockfree] review
From: Hans Boehm (Hans.Boehm_at_[hidden])
Date: 2011-09-13 19:47:04

Alexander Terekhov <terekhov <at> web.de> writes:

> 
> 
> Hans Boehm wrote:
> [...]
> > Although the existence of such an algorithm is interesting, the point is 
that
> > avoiding the equivalent of the sequentuially consistent store here is
> > incredibly complicated, appears to require scheduler help and, at least for
> > me, would require careful study of the proof before I were willing to
> > implement it.  On the other hand, the algorithm using the equivalent of
> > sequentially consistent atomics (which I think is still far more widely 
used)
> > is orders of magnitude simpler.  If you understand the complex algorithm, 
we
> > assume you can add the ordering constraints corectly.
> 
> With waiters bit (0x80000000) and atomic RMW, mutex is simply:
> (pseudo-code below)
> 
>   WHILE atomic_bit_test_set_hlb(&lock, 1) // efficient acquire MO
>     lock_queue_wait(&lock, 1) // wait if locked bit is set
> 
> for lock() and
> 
>   uintptr_t lock_queue
>   IF atomic_decrement_rel(lock_queue = &lock) // release MO
>     THEN lock_queue_wake(lock_queue, 1) 
I'm not sure I understand your syntax here.

I don't see the correctness argument.  What prevents the sequence:

1. In thread T0, performing unlock, atomic_decr_rel update completes, sees no 
waiters, puts updated (released) lock word in store buffer.  (I'm informally 
viewing memory_order_release as just putting a value in a store buffer, which 
I think is reasonable here.)
2. Thread T1 tries to acquire the lock, sees it still held, since store buffer 
hasn't drained.  Enqueues itself.
3. Thread T0s store buffer drains.  Thread T1 is now waiting on an unlocked 
lock.

The real point here again is that such arguments are subtle.  I don't want to 
have to deal with them unless performance considerations warrant that I do, 
especially since we have lots of evidence that even experts get these things 
wrong.

Hans