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

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

Hmm, I have one more question regarding your implementation: You put  =

barrier() after the increments, because otherwise get() might think that=
  =

the FIFO is empty, when it's not, and put() might think that the FIFO is=
  =

full, when it's not. I believe that putting in these memory barriers won=
't  =

solve the problem, because what if the threads get switched after the  =

increment, but before executing the barrier()?? Even using  =

interlocked_increment won't help, because only one thread is changing th=
e  =

value, and again, what if the thread switch occurs after the store and  =

before the increment?

Of course, none of this really matters, because it should not result in =
 =

corrupt data in any way, I just think that those barriers are unnecessar=
y.



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.