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

[Paul E. McKenney]

On Fri, Jun 29, 2018 at 11:55:08AM +0800, Xiao Guangrong wrote:
> 
> 
> On 06/28/2018 07:55 PM, Wei Wang wrote:
> >On 06/28/2018 06:02 PM, Xiao Guangrong wrote:
> >>
> >>CC: Paul, Peter Zijlstra, Stefani, Lai who are all good at memory barrier.
> >>
> >>
> >>On 06/20/2018 12:52 PM, Peter Xu wrote:
> >>>On Mon, Jun 04, 2018 at 05:55:17PM +0800, 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.
> >>>
> >>>Could you provide some more information about the kfifo bug? Any
> >>>pointer would be appreciated.
> >>>
> >>
> >>Sure, i reported one of the memory barrier issue to linux kernel:
> >>   https://lkml.org/lkml/2018/5/11/58
> >>
> >>Actually, beside that, there is another memory barrier issue in kfifo,
> >>please consider this case:
> >>
> >>   at the beginning
> >>   ring->size = 4
> >>   ring->out = 0
> >>   ring->in = 4
> >>
> >>     Consumer                            Producer
> >> ---------------                     --------------
> >>   index = ring->out; /* index == 0 */
> >>   ring->out++; /* ring->out == 1 */
> >>   < Re-Order >
> >>                                    out = ring->out;
> >>                                    if (ring->in - out >= ring->mask)
> >>                                        return -EFULL;
> >>                                    /* see the ring is not full */
> >>                                    index = ring->in & ring->mask; /* index 
> >>== 0 */
> >>                                    ring->data[index] = new_data;
> >>　　　　　　　　　　　　　　　　　　　　　ring->in++;
> >>
> >>   data = ring->data[index];
> >>   !!!!!! the old data is lost !!!!!!
> >>
> >>So we need to make sure:
> >>1) for the consumer, we should read the ring->data[] out before updating 
> >>ring->out
> >>2) for the producer, we should read ring->out before updating ring->data[]
> >>
> >>as followings:
> >>      Producer                                       Consumer
> >>  ------------------------------------ ------------------------
> >>      Reading ring->out                            Reading ring->data[index]
> >>      smp_mb()                                     smp_mb()
> >>      Setting ring->data[index] = data ring->out++
> >>
> >>[ i used atomic_store_release() and atomic_load_acquire() instead of 
> >>smp_mb() in the
> >>  patch. ]
> >>
> >>But i am not sure if we can use smp_acquire__after_ctrl_dep() in the 
> >>producer?
> >
> >
> >I wonder if this could be solved by simply tweaking the above consumer 
> >implementation:
> >
> >[1] index = ring->out;
> >[2] data = ring->data[index];
> >[3] index++;
> >[4] ring->out = index;
> >
> >Now [2] and [3] forms a WAR dependency, which avoids the reordering.
> 
> It can not. [2] and [4] still do not any dependency, CPU and complainer can 
> omit
> the 'index'.

One thing to try would be the Linux-kernel memory model tools in
tools/memory-model in current mainline.  There is a README file describing
how to install and set it up, with a number of files in Documentation
and litmus-tests that can help guide you.

                                                        Thanx, Paul