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

Subject: Re: [boost] [lockfree::fifo] Review
From: Tim Blechmann (tim_at_[hidden])
Date: 2009-12-09 15:49:21

> Yes. Recently I did an experiment on 32 bit 2.6 linux using SUSE 9.1 and 
> libc that came with it. (libc version was 2.3.3-97). I was doing all 
> sorts of allocations and looking at the returned pointer. What I found 
> was that the only the two low bits were always the same (obviously 
> because malloc has to return aligned data). All other bits could be 
> different depending on the size of the requested allocation. I think 
> they were also depended on the thread that was requesting the 
> allocation, but I'm not sure on this point. So, other than the 2 lower 
> bits, you can't assume you can use any more. And 2 bits seems kinda low 
> for an ABA tag.

all 32 bit platforms that i know of are using the full 32bit as address
space (the lower two bits are 0 because of 32bit alignment) ... on 64bit
platforms it is quite different ... ppc64, ia64 and x86_64 all use just
a part of the full address space (iirc 48 bit for x86_64) ... the rest
should be usable as aba prevention tag.

>>> 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.
> 
> 
> You know, it's an interesting question whether CAS really implies a 
> memory barrier or not. Obviously, you've implemented it that way, but I 
> think it not need be that way. I think there's really no "standard" on 
> CAS so we need to go with what is commonly accepted. It may be another 
> question that would be good to ask at c.p.t
> If someone can answer this question, please chime in.

the c++0x atomic library handles it explicitly ... compare_exchange has
takes the behavior as argument ...

>> 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.
> 
> 
> Definitely.
> How can I get to your latest code?

the code can be found in my git repository [1], branch lockfree-atomic
... unfortunately, i am stuck with the fifo implementation, which is
currently broken, although i cannot see why :/

thnx, tim

[1] http://tim.klingt.org/git?p=boost_lockfree.git

-- 
tim_at_[hidden]
http://tim.klingt.org
Relying on the government to protect your privacy is like asking a
peeping tom to install your window blinds.
  John Perry Barlow