Re: [boost] [lockfree::fifo] Review

Subject: Re: [boost] [lockfree::fifo] Review
From: Helge Bahmann (hcb_at_[hidden])
Date: 2009-12-11 09:47:11

On Fri, 11 Dec 2009, Tim Blechmann wrote:

> by definition ll/sc are immune to aba problems

This is NOT correct. The sequence of operations you would need to prevent 
ABA is:

         object *tmp=head.load_linked();
         object *next=tmp->next;
         head.store_conditional(next);

This is however NOT possible because you are not allowed to make any 
memory access between ll and sc -- some CPUs (definitely older mips, but 
not ppc, unsure about many of the other architectures) clear the 
reservation on _any_ memory reference and will cause this sequence to 
always fail. Alpha has the fun requirement of a memory barrier before you 
are allowed to dereference "tmp", which just provides another way to kill 
your reservation.

ll/sc only prevents "pathological" ABA races as you cannot inpsect the 
object being replaced. Exposing an ll/sc interface to a higher-level 
language is therefore unlikely to result in something usable.

> most cas-architectures provide dcas

I think x86 is the rare exception, not the rule, so relying on DCAS 
excludes pretty much all 32-bit except for x86.

Helge