From mboxrd@z Thu Jan 1 00:00:00 1970 From: Xiao Guangrong Subject: Re: [PATCH 09/12] ring: introduce lockless ring buffer Date: Fri, 29 Jun 2018 11:55:08 +0800 Message-ID: References: <20180604095520.8563-1-xiaoguangrong@tencent.com> <20180604095520.8563-10-xiaoguangrong@tencent.com> <20180620045203.GE18985@xz-mi> <6f871708-d38b-2acf-350a-985c8a23a013@gmail.com> <5B34CCB9.5040406@intel.com> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Cc: kvm@vger.kernel.org, mst@redhat.com, peterz@infradead.org, Lai Jiangshan , stefani@seibold.net, mtosatti@redhat.com, Xiao Guangrong , dgilbert@redhat.com, qemu-devel@nongnu.org, jiang.biao2@zte.com.cn, pbonzini@redhat.com, paulmck@linux.vnet.ibm.com To: Wei Wang , Peter Xu Return-path: In-Reply-To: <5B34CCB9.5040406@intel.com> Content-Language: en-US List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+gceq-qemu-devel2=m.gmane.org@nongnu.org Sender: "Qemu-devel" List-Id: kvm.vger.kernel.org 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, guangrong.xiao@gmail.com wrote: >>>> From: Xiao Guangrong >>>> >>>> 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'.