Re: [Qemu-devel] [PATCH 09/12] ring: introduce lockless ring buffer

["Michael S. Tsirkin" <mst@redhat.com>]

On Thu, Jun 28, 2018 at 09:36:00PM +0800, Jason Wang wrote:
> 
> 
> On 2018年06月04日 17:55, guangrong.xiao@gmail.com wrote:
> > From: Xiao Guangrong<xiaoguangrong@tencent.com>
> > 
> > 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@tencent.com>
> > ---
> 
> 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