[ovs-dev] [RFC 04/10] rcu-slist: Introduce RCU-protected singly linked list

Ben Pfaff blp at nicira.com
Fri Oct 10 16:13:25 UTC 2014


On Wed, Oct 08, 2014 at 02:09:50PM -0700, Daniele Di Proietto wrote:
> An rcu-slist can be read and written without explicit locking: it uses RCU
> protected pointers and compare-exchange operations.
> 
> Signed-off-by: Daniele Di Proietto <ddiproietto at vmware.com>

I think that there are a couple of key properties of this list that
should be mentioned somewhere.

First, this is a multiple-writer list.  It will of course work as a
single-writer list as well, but a single-writer list can be implemented
with cheaper operations on the write side (there is no need for
compare-and-exchange).

Second, when a list element has been removed, it must not be freed until
the next grace period (which is already stated), but it also must not be
modified or added back into the list or any other list before the next
grace period as well.

The condition in RCU_SLIST_FOR_EACH looks odd to me:

         INIT_CONTAINER(ITER, cursor__, MEMBER), cursor__;           \

because it uses INIT_CONTAINER on a pointer that might be null, which is
wasteful and somewhat risky.  I'd prefer to write it so that it only
uses INIT_CONTAINER if cursor__ if nonnull, even though that makes the
code uglier.  So that would be something like:

    cursor__ && (INIT_CONTAINER(ITER, cursor__, MEMBER), true)

or something similar with ?:.



More information about the dev mailing list