From mboxrd@z Thu Jan 1 00:00:00 1970 From: Wei Wang Subject: Re: [PATCH 09/12] ring: introduce lockless ring buffer Date: Thu, 28 Jun 2018 19:55:37 +0800 Message-ID: <5B34CCB9.5040406@intel.com> References: <20180604095520.8563-1-xiaoguangrong@tencent.com> <20180604095520.8563-10-xiaoguangrong@tencent.com> <20180620045203.GE18985@xz-mi> <6f871708-d38b-2acf-350a-985c8a23a013@gmail.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: Xiao Guangrong , Peter Xu Return-path: In-Reply-To: <6f871708-d38b-2acf-350a-985c8a23a013@gmail.com> 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 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. Best, Wei