On Thu, Jun 28, 2018 at 09:36:00PM +0800, Jason Wang wrote: > > > On 2018年06月04日 17:55, guangrong.xiao@xxxxxxxxx wrote: > > From: Xiao Guangrong<xiaoguangrong@xxxxxxxxxxx> > > > > 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<xiaoguangrong@xxxxxxxxxxx> > > --- > > May I ask why you need a MPSC ring here? Can we just use N SPSC ring for > submitting pages and another N SPSC ring for passing back results? > > Thanks Or just an SPSC ring + a lock. How big of a gain is lockless access to a trivial structure like the ring? -- MST
