A Novel Ring Buffer Implementation

Whilst wandering around the Solaris on Xen source yesterday, I came across a ring buffer approach that I’d not seen before. It’s part of the mechanism used by the Xen hypervisor to move network packets between the various domains. Most ring implementations that I’ve used have involved interfacing with hardware, so it was a case of determining how the hardware behaved and coding to that mechanism. In the case of Xen networking, there’s no real hardware involved, so some more flexibility is possible.

Typical ring buffer implementations use a couple of pointers to producer and consumer indexes in the ring. Both producer and consumer have to take care to wrap the pointers when they hit the end and comparisons between the producer and consumer indexes have to be managed carefully (because the producer index may wrap around and end up “in front of” the consumer index).

The approach taken by the Xen network driver is somewhat different. The index pointers into the ring are free-running counters. The actual slot in the ring (there are 256) represented by the pointer is found by masking out high bits in this index. Moving one of the index pointers in the ring forward involves simply adding one to the pointer.

The novel part, for me at least, is that the index pointers are stored as unsigned 32 bit quantities, so testing the distance between two pointers is a simple matter of subtraction. There’s no need to worry about the pointers wrapping - they simply run around to zero and both the mask operation to find a slot and comparisons between indexes continue to work. Of course, it’s still necessary to include checks to avoid pushing one pointer past another (i.e. producer past consumer).

It’s a neat approach that simplifies the code somewhat.

The definitions of the data structures include a comment (re-formatted slightly) that made me smile:

/*
 * We use a special capitalised type name because it is _essential_ that all 
 * arithmetic on indexes is done on an integer type of the correct size.
 */
typedef u32 NETIF_RING_IDX;

Wow, that’s a feature of gcc that I wasn’t aware of. Maybe I should go looking for other capitalised type names :-)