Re: [GD-General] Totally Safe lock-free FIFO for arbitrary-sized items.

[Andras B. <and...@gm...>]

Jon, I very much appreciate all the explanation and sharing of the  =

implementation details! It is extremely helpful!!
To answer your question, when I asked for a 64 bit FIFO, I was thinking =
of  =

the fully generic FIFO's on 64bit systems, with unlimited queue length, =
 =

and with multiple producer and consumer threads. In this case, all the  =

solutions that I've found used linked lists with pointers, and required =
 =

using an atomic compare-and-swap primitive that works on double the  =

machine word size (so that you can use another machine word for ABA  =

resolution), which is non existent for 64 bit systems (there's no  =

cmpxchg16b AFAIK), hence my question.

I admit that I didn't even think about having only one producer and one =
 =

consumer thread and a fixed maximum queue length can simplify things thi=
s  =

much! Turns out that this is all I need.


Thanks again,


Andras


On Wed, 09 Aug 2006 14:10:50 -0600, Jon Watte <hp...@mi...>  =

wrote:

>
> And, to confuse things even more, if you have strict aliasing options
> turned on, the compiler may even decide to re-order the stores. Thus,
> the Totally Safe lock-free FIFO for arbitrary-sized items looks like  =

> this:
>
> /* Lock-free FIFO by Jon Watte.
>  * Stored can be a type of any size.
>  * Size must be power of 2.
>  * This FIFO is correct on systems with strongly consistent
>  * caches (such as Intel). It may require write barriers on
>  * systems with weakly consistent caches. Insert such a
>  * barrier in the inline function barrier() if that's the case.
>  */
> template<typename Stored, size_t Size>
> class LockFreeFifo {
>   public:
>     LockFreeFifo() { head =3D 0; tail =3D 0; }
>
>     /* Get an item from the FIFO.
>      * Return true if an item was there and was copied,
>      * false if the FIFO is empty.
>      */
>     bool get(Stored & out) {
>       if (head - tail > 0) {
>         out =3D fifo_[tail & (Size-1)];
>         ++tail;
>         barrier(); /* make sure writer knows FIFO isn't full */
>         return true;
>       }
>       return false;
>     }
>
>     /* Put an item into the FIFO.
>      * Return true if it fit and was copied,
>      * false if the FIFO is full.
>      */
>     bool put(Stored & in) {
>       if (head - tail < Size) {
>         fifo_[head & (Size-1)] =3D in;
>         barrier(); /* make sure FIFO is updated before head */
>         ++head;
>         barrier(); /* make sure reader can find the new item */
>         return true;
>       }
>       return false;
>     }
>
>   private:
>
>     inline void barrier() {
>       /* If your platform has a weakly consistent cache (i e,
>        * not Intel) then you need to insert a barrier instruction
>        * (such as EIEIO on PPC) here.
>        */
> #warning "Use the intrinsic specific to your platform, if needed."
>     }
>
>     /* Make these volatile, to avoid strict type aliasing analysis to =
 =

> allow
>      * the compiler to re-order stores.
>      */
>     volatile unsigned int head;
>     volatile unsigned int tail;
>     volatile Stored fifo_[Size];
> };
>
>
>
> Jon Watte wrote:
>> Note that the problem is with weakly _consistent_ cahces, not just
>> weakly ordered -- i e, if cache line A can flush before cache line B,=
 it
>> doesn't matter, as long as the mutliple CPUs implement cache snooping=
 to
>> stay consistent (which is the case on Intel). On PPC, you may end up
>> wanting to use the cache line reservations with a spin loop.