Re: [boost] Review Request: boost.lockfree

Subject: Re: [boost] Review Request: boost.lockfree
From: Andrew Venikov (andrew.venikov_at_[hidden])
Date: 2009-12-03 18:58:32

Tim Blechmann wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> hi all,
> 
> since my first review request for boost.lockfree [1] was completely
> ignored, here a second version for review. the main differences are bug
> fixes provided by various people, trying to run boost.lockfree on
> different compilers/platforms.
> 
<snip>

Sorry for doing it in stages, but reviewing lock-free algorithms is not 
easy. I just finished reviewing your fifo's "enqueue" function.

First, I've noticed that to alleviate the ABA problem on platforms where 
sizeof(void*) is 64 bits, you're using "packed" pointers, i.e. using 
some of the bits of the pointer returned by malloc to store the ABA tag 
with the assumption that the bits are always 0.
It is not safe to do with every libc implementation - some libc
implementations are meddling with the bits themselves and if you change 
them, then malloc/free will not function properly.

Let me write your code down here so that I can enumerate the lines:

     bool enqueue(T const & t)
     {
         node * n = alloc_node(t);

         if (n == NULL)
             return false;

         //Write barrier should be placed here

         for (;;)
         {
             atomic_node_ptr tail (tail_);  //1
             read_memory_barrier();  //2
             atomic_node_ptr next (tail->next);  //3

             if (likely(tail == tail_)) //4
             {
                 if (next.get_ptr() == 0) //5
                 {
                     if ( tail->next.cas(next, n) ) //6
                     {
                         tail_.cas(tail, n);  //7
                         return true;  //8
                     }
                 }
                 else
                     tail_.cas(tail, next.get_ptr());  //9
             }
         }
     }

First, you're missing a write barrier after a call to alloc_node().
That call is writing "NULL" to node's next pointer, but that write may 
not happen until after you've inserted your node, which is too late.

Second, I think you must declare head_ and tail_ as volatiles. Also, I 
believe the next pointer should point to a volatile object, not a 
regular object.

I've implemented Michael-Scott queue myself and remember that getting 
volatiles and barriers right was the toughest part.

I'll look into enqueue later.

HTH,
    Andy.