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

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

I think that we are talking about different barriers, here's a snippet  =

 from your code:

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;

I agree that the first barrier is absolutely necessary on those esoteric=
  =

systems, because it forces the data to be actually written out (and I me=
an  =

written in a sense that anyone else reading it will get the intended  =

value) before the head is incremented.

Now, the other barrier after the increment is the one that is not needed=
,  =

because it doesn't really matter if the head has been incremented or not=
.  =

In the worst case, the receiver won't know that there's a new element in=
  =

the queue until later, but it will by no means result in data loss or  =

corrupton, no matter what architecture you are running on.


Andras

On Sun, 20 Aug 2006 20:44:37 -0600, Jon Watte <hp...@mi...>  =

wrote:

> If you get switched out before the barrier, that's no different (reall=
y)
> from being switched out before the put operation -- you'll be switched=

> back in and perform the barrier in the next time-slice.
>
> The barriers are not necessary on Intel machines, because the data
> caches are guaranteed to be consistent. They use snooping to make
> read-after-write always return the consistent value.
>
> Some more esoteric hardware may have caches that don't have this nice
> property, and a read from a word that's already in cache may return th=
e
> old cache value, rather than the updated value living in some other  =

> cache.
>
> The barriers may also be needed on machines with out-of-order
> speculative memory, where the  write to update the FIFO contents may b=
e
> re-ordered to happen after the write to update the queue size. There m=
ay
> be some chance of this happening under certain circumstances on certai=
n
> Intel chips, AFAICT, so an SFENCE wouldn't hurt (although I believe th=
e
> "common, plain" cases don't actually have this problem).
>
> Cheers,
>
>              / h+