From: Xiao Guangrong<address@hidden>
It's the simple lockless ring buffer implement which supports both
single producer vs. single consumer and multiple producers vs.
single consumer.
Many lessons were learned from Linux Kernel's kfifo (1) and DPDK's
rte_ring (2) before i wrote this implement. It corrects some bugs of
memory barriers in kfifo and it is the simpler lockless version of
rte_ring as currently multiple access is only allowed for producer.
If has single producer vs. single consumer, it is the traditional fifo,
If has multiple producers, it uses the algorithm as followings:
For the producer, it uses two steps to update the ring:
- first step, occupy the entry in the ring:
retry:
in = ring->in
if (cmpxhg(&ring->in, in, in +1) != in)
goto retry;
after that the entry pointed by ring->data[in] has been owned by
the producer.
assert(ring->data[in] == NULL);
Note, no other producer can touch this entry so that this entry
should always be the initialized state.
- second step, write the data to the entry:
ring->data[in] = data;
For the consumer, it first checks if there is available entry in the
ring and fetches the entry from the ring:
if (!ring_is_empty(ring))
entry = &ring[ring->out];
Note: the ring->out has not been updated so that the entry pointed
by ring->out is completely owned by the consumer.
Then it checks if the data is ready:
retry:
if (*entry == NULL)
goto retry;
That means, the producer has updated the index but haven't written any
data to it.
Finally, it fetches the valid data out, set the entry to the initialized
state and update ring->out to make the entry be usable to the producer:
data = *entry;
*entry = NULL;
ring->out++;
Memory barrier is omitted here, please refer to the comment in the code.
(1)https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/kfifo.h
(2)http://dpdk.org/doc/api/rte__ring_8h.html
Signed-off-by: Xiao Guangrong<address@hidden>
---