From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:55776) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VE4e2-0002bq-N7 for qemu-devel@nongnu.org; Mon, 26 Aug 2013 17:48:22 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VE4dy-0001fJ-G0 for qemu-devel@nongnu.org; Mon, 26 Aug 2013 17:48:18 -0400 Received: from mail-ve0-f169.google.com ([209.85.128.169]:48419) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VE4dy-0001cT-Al for qemu-devel@nongnu.org; Mon, 26 Aug 2013 17:48:14 -0400 Received: by mail-ve0-f169.google.com with SMTP id db10so2658281veb.28 for ; Mon, 26 Aug 2013 14:48:13 -0700 (PDT) MIME-Version: 1.0 In-Reply-To: <20130825191835.GA1073@Krystal> References: <1377371209-2017-1-git-send-email-ncmike@ncultra.org> <20130825191835.GA1073@Krystal> Date: Mon, 26 Aug 2013 17:48:12 -0400 Message-ID: From: Mike Day Content-Type: multipart/alternative; boundary=089e0149d0ac88833204e4e0b696 Subject: Re: [Qemu-devel] [RFC PATCH] Introduce RCU-enabled DQs (v2) List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Mathieu Desnoyers Cc: rp@svcs.cs.pdx.edu, qemu-devel@nongnu.org, lttng-dev@lists.lttng.org, Anthony Liguori , Paolo Bonzini , Paul Mckenney --089e0149d0ac88833204e4e0b696 Content-Type: text/plain; charset=ISO-8859-1 On Sun, Aug 25, 2013 at 3:18 PM, Mathieu Desnoyers < mathieu.desnoyers@efficios.com> wrote: > > I'm not very comfortable with your DQ implementation not providing any > kind of guarantee to a forward traversal followed by backward traversal, > nor for backward followed by forward traversal. If a list add is > executed concurrently with traversals, and we can ensure there are no > list del of the node, if a traversal sees the added node when doing > forward iteration, I would clearly expect to still see it if a backward > iteration follows. > > I took the liberty of implementing a couple of ideas I had to provide > a RCU DQ with those guarantees. I just pushed the code here (beware, I > just did some basic single-threaded unit tests so far, so consider this > code as largely untested concurrency-wise): > > git clone git://git.urcu.io/urcu.git > branch: rcudq > file: urcu/rcudq.h > > Direct link to the file via gitweb: > http://git.lttng.org/?p=userspace-rcu.git;a=blob;f=urcu/rcudq.h;h=4a8d7b0d5143a958514cf130b1c124d99f3194ca;hb=refs/heads/rcudq Mathieu - Thanks for the review! And thanks for the code, I'm working with it right now. I like the idea of using a flag to provide a form of atomicity for the doubly-linked list elements. I'm also planning on running some timing tests to see of the additional memory barriers and atomic accesses make *any* difference whatsoever. Mike Mike Day | ncmike@ncultra.org | +1 919 371-8786 --089e0149d0ac88833204e4e0b696 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
On Sun, Aug 25, 2013 at 3:18 PM, Mathieu Desnoyers <mathieu.desnoyers@efficios.c= om> wrote:
>
> I'm not very comfortable with your DQ= implementation not providing any
> kind of guarantee to a forward traversal followed by backward traversa= l,
> nor for backward followed by forward traversal. If a list add is=
> executed concurrently with traversals, and we can ensure there are= no
> list del of the node, if a traversal sees the added node when doing> forward iteration, I would clearly expect to still see it if a backwa= rd
> iteration follows.
>
> I took the liberty of impleme= nting a couple of ideas I had to provide
> a RCU DQ with those guarantees. I just pushed the code here (beware, I=
> just did some basic single-threaded unit tests so far, so consider= this
> code as largely untested concurrency-wise):
>
> = =A0 git clone git://git.urcu.io/urc= u.git
> =A0 branch: rcudq
> =A0 file: urcu/rcudq.h
>
> Direc= t link to the file via gitweb:
> =A0 http://git.lttng.org/?p=3Duserspa= ce-rcu.git;a=3Dblob;f=3Durcu/rcudq.h;h=3D4a8d7b0d5143a958514cf130b1c124d99f= 3194ca;hb=3Drefs/heads/rcudq

Mathieu - Thanks for the review! And thanks for the code, I&= #39;m working with it right now. I like the idea of using a flag to provide= a form of atomicity for the doubly-linked list elements. I'm also plan= ning on running some timing tests to see of the additional memory barriers = and atomic accesses make *any* difference whatsoever.=A0

Mike

M= ike Day | ncmike@ncultra.org | +1= 919 371-8786=A0
--089e0149d0ac88833204e4e0b696--