Subject: Re: [boost] [lockfree::fifo] Review
From: Tim Blechmann (tim_at_[hidden])
Date: 2009-12-05 09:27:14
thanks for your comments!
> First of all I think that having a library of lock-free
> algorithms/containers would be greatly beneficial to a great number of
> boost users. On the other hand, having implemented several lock-free
> algorithms, I know that it is notoriously hard to get them right. We'll
> need all the help we can get from knowledgeable people in the field. The
> implementation needs to be thoroughly reviewed. Let me give the first
> attempt at that.
i know of the difficulty to get lock-free data structures right, and
several issues have been solved by people, reviewing my code ...
> Second, this algorithm makes certain assumptions about the ability to
> access memory that has been freed. The algorithm can try to read memory
> that has been de-allocated. (See further down for description of how).
> Several debug implementations of malloc/free store every allocated
> element on one page and when the element is freed, the page is marked
> protected for both reading and writing. That means that this algorithm
> can only work with a subset of custom allocators. Your "free_list" for
> example can't work with it since it's possible for a node to be freed
> when you call "deallocate". The "caching_freelist" and "static_freelist"
> on the other hand work just fine because they never return the memory
> back to the system.
the free_list class should not be used for the stack/fifo classes (i
should remove it to avoid confusion). i chose the freelist approach,
since hazard pointers and pass-the-buck are/may be subject of patents/
> Third, and the biggest limitation, is the algorithm's assumption that
> you can store a pointer to an element plus an ABA tag in a contiguous
> memory space that can be passed to a CAS instruction. I believe not all
> platforms provide a DCAS instruction, that's why you're trying to work
> around this issue by using "packed pointers", i.e. storing the ABA tag
> in the part of the pointer that presumably is never used. The problem
> with that, however, is that some libc implementations of malloc/free do
> use all the bits in the pointer for their own needs, so you can't assume
> that you can meddle with them.
puh, can you elaborate on this? i haven't been aware of any use of the
unused address space bits.
> My experience with this algorithm shows that the safest approach is to
> use a pre-allocated array for the queue and replace pointers with
> indexes into the array. Assuming that the size of an index is
> sufficiently lower than the size of a pointer, you can use the remaining
> bits to store the ABA tag. This alleviates both point 2 and 3. This does
> mean however, that the queue can't have an unbound size, the size has to
> be specified during the queue instantiation.
that would greatly increase the portability ... it would be even
possible to use e.g. 16bit indices and 16bit tags on 32bit platforms
without dcas
> Fourth, on platforms where CAS is implemented using LL/SC (such as
> PowerPC and MIPS), it is possible to livelock. The problem with LL/SC on
> most platforms is that the write granulum for marking LL's address as
> "dirty" isn't just the memory pointed to by LL, but the whole cache line
> where the memory resides. On these platforms it is important to make
> sure that each "node" of the queue is located on a separate cache line.
interesting point! i should somehow handle size and alignment of the
nodes on these platforms
> Here's the code of your enqueue:
>
>
> bool enqueue(T const & t)
> {
> node * n = alloc_node(t);
>
> if (n == NULL)
> return false;
>
> 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);
> return true;
> }
> }
> else
> tail_.cas(tail, next.get_ptr());
> }
> }
> }
>
>
> 1. You're missing write barrier after a call to alloc_node().
> Rational: alloc_node sets the "next" pointer of the newly allocated node
> to NULL. That is a store to shared memory. Setting next pointer to NULL
> has to be observable to other threads BEFORE they observe the inserted
> node. If you don't insert a write barrier, it is possible for other
> threads to see the new element in the list before element's next pointer
> is initialized with NULL.
i was assuming, that cas issues a full memory barrier (at least my cas
implementation does), so i don't think, this would be an issue.
> 2. You've misplaced the read_barrier.
> Rational: Line 4 checks the validity of the load done on line 3. That
> means that the read_barrier should be between lines 3 and 4. If you
> don't have a read_barrier after loading *tail->next, then this load can
> happen after the load of tail_ on line 4, which defies the purpose of
> line 4.
> You still need to have a barrier between lines 1 and 3, but here only a
> data dependency barrier will suffice, which is a weaker form of a read
> barrier and on most all platforms is a no-op since data dependent loads
> can be handled by processors automatically.
thanks for this explanation ...
> 3. Your tail_ and head_ should be volatile. Furthermore, the getters for
> you tagged_ptr (like get_ptr, operator->() and operator* ) should
> return pointers/references to volatile types.
> Rational: If your tail_ is not volatile, then the compiler is free to
> load head_ just once and line 4 effectively becomes a no-op.
this was already pointed out a few days ago and is fixed in my repository.
> 1. Again, you need to put read_barrier between lines 4 and 5. Only data
> dependency barrier will suffice at line 2.
> 2. You need to add write barrier after line 7 for the same reason as in
> the enqueue.
same as above
> Hope this was descriptive,
i am currently porting the data structures to the boost.atomic proposal,
which provides better language support to specify the memory order
constraints. the code is available from a separate branch of my
repository. i would be curious, if you could have a look at that
implementation as well.
thanks a lot for your review!
cheers, tim
-- tim_at_[hidden] http://tim.klingt.org There's no such entity as "most people". These are generalities. All generalities are meaningless. You've got to pin it down to a specific person doing a specific thing at a specific time and space. William S. Burroughs