[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH 09/12] ring: introduce lockless ring buffer
From: |
Michael S. Tsirkin |
Subject: |
Re: [Qemu-devel] [PATCH 09/12] ring: introduce lockless ring buffer |
Date: |
Fri, 29 Jun 2018 07:23:50 +0300 |
On Thu, Jun 28, 2018 at 09:36:00PM +0800, Jason Wang wrote:
>
>
> On 2018年06月04日 17:55, address@hidden wrote:
> > 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>
> > ---
>
> 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
- Re: [Qemu-devel] [PATCH 09/12] ring: introduce lockless ring buffer, (continued)
Re: [Qemu-devel] [PATCH 09/12] ring: introduce lockless ring buffer, Peter Xu, 2018/06/20
Re: [Qemu-devel] [PATCH 09/12] ring: introduce lockless ring buffer, Michael S. Tsirkin, 2018/06/20
Re: [Qemu-devel] [PATCH 09/12] ring: introduce lockless ring buffer, Jason Wang, 2018/06/28
Re: [Qemu-devel] [PATCH 09/12] ring: introduce lockless ring buffer,
Michael S. Tsirkin <=
Re: [Qemu-devel] [PATCH 09/12] ring: introduce lockless ring buffer, Xiao Guangrong, 2018/06/29
[Qemu-devel] [PATCH 10/12] migration: introduce lockless multithreads model, guangrong . xiao, 2018/06/04
[Qemu-devel] [PATCH 11/12] migration: use lockless Multithread model for compression, guangrong . xiao, 2018/06/04
[Qemu-devel] [PATCH 12/12] migration: use lockless Multithread model for decompression, guangrong . xiao, 2018/06/04
Re: [Qemu-devel] [PATCH 00/12] migration: improve multithreads for compression and decompression, Peter Xu, 2018/06/11