Re: [boost] threadpool lockfree_channel

Subject: Re: [boost] threadpool lockfree_channel
From: Anthony Williams (anthony.ajw_at_[hidden])
Date: 2009-03-16 06:14:50

Tim Blechmann <tim_at_[hidden]> writes:

> i just saw, that you checked in a lockfree fifo implementation to the
> boost sandbox.
> it looks like an implementation of the michael/scott queue, isn't it? if
> so, i suppose, you are missing a thread-safe memory reclamation
> mechanism ...
> some time ago, i wrote a boost-style implementation of this data
> structure, not sure, if you came across it [1] ... maybe it would make
> sense to join our efforts in implementing a lockfree queue and get it
> into boost?

> [1] http://tim.klingt.org/git?p=boost_lockfree.git;a=summary

Firstly, I'd like to help with this. I have a couple of lock-free queue
implementations lying around from my book. I've attached a sample
implementation that uses atomic reference-counting --- it would need to
be "boostified", as it's written for C++0x, but that should be
relatively straightforward. I don't make any claims for performance, but
I believe it to be "correct", with no data races or undefined behaviour
--- I *really* want to know if that's not the case, so I can correct it
before the book goes to press.

Secondly, both these queues (Tim's at the posted link, and Oliver's at
https://svn.boost.org/trac/boost/browser/sandbox/threadpool/boost/tp/lockfree_channel.hpp)
have race conditions in dequeue/take.

First, let's look at Tim's implementation at
http://tim.klingt.org/git?p=boost_lockfree.git;a=blob;f=boost/lockfree/fifo.hpp;h=066465af55e8f030100093742c8534b3fbb9ce40;hb=HEAD

Suppose there are two threads calling deqeue() concurrently. If there is
an item in the queue, both will proceed identically down to line 137, as
neither thread modifies the queue data before then. Now suppose one
thread (A) gets preempted, but the other (B) proceeds. Thread B will
read next->data and assign it to ret. It will then update head_ with CAS
(which will succeed as no other thread is modifying/has modified the
data structure), and *deallocate the node* at line 141. This will
destroy next->data. Now, when thread A wakes up it will try and read
next->data => reading destroyed object, undefined behaviour.

Oliver's take() suffers a similar problem. Suppose there are two threads
calling take(). Both proceed as far as line 168, and then thread A gets
pre-empted whilst thread B proceeds. There is an item on the queue, so
val is non-NULL, and the queue hasn't been modified, so head_==head. No
other thread is modifying the queue, so we end up at line 197. We then
update head_ in line 198 and *delete head.ptr* at line 202 and set it to
NULL at line 203. Now, when thread A wakes up the first thing it does is
read head.ptr->prev, which is a dereference of a NULL ptr => undefined
behaviour.

Lock-free code is hard. Memory reclamation makes it doubly hard.

Anthony
-- 
Author of C++ Concurrency in Action | http://www.manning.com/williams
just::thread C++0x thread library   | http://www.stdthread.co.uk
Just Software Solutions Ltd         | http://www.justsoftwaresolutions.co.uk
15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976