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

[Jon W. <hp...@mi...>]

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 = 0; tail = 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 = 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)] = 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.
>