Tim Blechmann <tim@klingt.org> 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/lockfre...) 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.... 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