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

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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, 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.

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.


Best,
Wei



[Index of Archives]     [KVM ARM]     [KVM ia64]     [KVM ppc]     [Virtualization Tools]     [Spice Development]     [Libvirt]     [Libvirt Users]     [Linux USB Devel]     [Linux Audio Users]     [Yosemite Questions]     [Linux Kernel]     [Linux SCSI]     [XFree86]

  Powered by Linux