From mboxrd@z Thu Jan 1 00:00:00 1970 From: Jason Wang Subject: Re: [PATCH 09/12] ring: introduce lockless ring buffer Date: Thu, 28 Jun 2018 21:36:00 +0800 Message-ID: <355310d0-a33d-dab1-1781-2de37dd648f7@redhat.com> References: <20180604095520.8563-1-xiaoguangrong@tencent.com> <20180604095520.8563-10-xiaoguangrong@tencent.com> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: quoted-printable Cc: kvm@vger.kernel.org, Xiao Guangrong , qemu-devel@nongnu.org, peterx@redhat.com, dgilbert@redhat.com, wei.w.wang@intel.com, jiang.biao2@zte.com.cn To: guangrong.xiao@gmail.com, pbonzini@redhat.com, mst@redhat.com, mtosatti@redhat.com Return-path: In-Reply-To: <20180604095520.8563-10-xiaoguangrong@tencent.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 2018=E5=B9=B406=E6=9C=8804=E6=97=A5 17:55, guangrong.xiao@gmail.com wr= ote: > 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. > > 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 =3D ring->in > if (cmpxhg(&ring->in, in, in +1) !=3D in) > goto retry; > > after that the entry pointed by ring->data[in] has been owned by > the producer. > > assert(ring->data[in] =3D=3D 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] =3D 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 =3D &ring[ring->out]; > > Note: the ring->out has not been updated so that the entry pointe= d > by ring->out is completely owned by the consumer. > > Then it checks if the data is ready: > > retry: > if (*entry =3D=3D 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 initialize= d > state and update ring->out to make the entry be usable to the producer: > > data =3D *entry; > *entry =3D 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/t= ree/include/linux/kfifo.h > (2)http://dpdk.org/doc/api/rte__ring_8h.html > > Signed-off-by: Xiao Guangrong > --- May I ask why you need a MPSC ring here? Can we just use N SPSC ring for=20 submitting pages and another N SPSC ring for passing back results? Thanks