Re: [boost] [lockfree] review

Subject: Re: [boost] [lockfree] review
From: Alexander Terekhov (terekhov_at_[hidden])
Date: 2011-09-15 14:05:24

Hans Boehm wrote:
> 
> 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.

lock_queue_wait() is meant to block the calling thread and set waiters
bit only if locked bit is actually set (an RMW operation).

The races for setting/clearing bits are resolved by RMWs on the same
(&lock) memory location.

The situation is no different when (&lock) memory location would be
protected by a lock except that with RMWs the program is lock-free on
fast paths.

regards,
alexander.