[Qemu-devel] [PATCH 0/3] rcu: add option to use upstream liburcu

[Qemu-devel] [PATCH 0/3] rcu: add option to use upstream liburcu

[Emilio G. Cota]

Hi Paolo + all,

First off, thanks for your ongoing RCU work, which I'm closely
following.

As you stated in the initial RCU patch (7911747b), the intent
is to keep the same API as liburcu's. I checked whether this
was the case and found a couple of issues that I'm addressing
in the appended series.

* The first two patches bring back the RCU API to exactly
  match that of liburcu.

* The third patch adds a configure flag to choose from either
  liburcu or QEMU's RCU.

Apart from this, I wonder what to do about other valuable bits in
liburcu, particularly in liburcu-cds, which I'm using currently
off-tree.  I see three ways of eventually doing this:

a) Add Windows support in liburcu, thereby eliminating the
   de facto fork in QEMU.

b) Bring (fork) liburcu-cds to QEMU, just like liburcu-mb was.

c) Add a compile-time flag (say CONFIG_LIBURCU_CDS), and then only
   use data structures from liburcu-cds where appropriate, falling
   back to traditional locked structures when !CONFIG_LIBURCU_CDS.

Currently I'm using c) because I cannot do either a) and b)--I
don't know anything about Windows and have no need for it.

Would c) be acceptable for upstream, provided the gains (say in
scalability/memory footprint) are significant?

Thanks,

		Emilio

[Qemu-devel] [PATCH 1/3] rcu: use call_rcu semantics from liburcu

[Emilio G. Cota]

The recently added call_rcu does not match liburcu's call_rcu's semantics;
instead, call_rcu1 does. Fix it by doing the following:

- Rename QEMU's call_rcu  to call_rcu_first_elem
- Rename QEMU's call_rcu1 to call_rcu

The end goal is to be able to switch at compile-time between
liburcu and QEMU's RCU implementation.

Signed-off-by: Emilio G. Cota <cota@braap.org>
---
 docs/rcu.txt       | 21 ++++++++++-----------
 include/qemu/rcu.h |  6 +++---
 memory.c           |  4 ++--
 util/rcu.c         |  2 +-
 4 files changed, 16 insertions(+), 17 deletions(-)

diff --git a/docs/rcu.txt b/docs/rcu.txt
index 61752b9..575f563 100644
--- a/docs/rcu.txt
+++ b/docs/rcu.txt
@@ -85,8 +85,8 @@ The core RCU API is small:
         synchronize_rcu.  If this is not possible (for example, because
         the updater is protected by the BQL), you can use call_rcu.
 
-     void call_rcu1(struct rcu_head * head,
-                    void (*func)(struct rcu_head *head));
+     void call_rcu(struct rcu_head * head,
+                   void (*func)(struct rcu_head *head));
 
         This function invokes func(head) after all pre-existing RCU
         read-side critical sections on all threads have completed.  This
@@ -106,7 +106,7 @@ The core RCU API is small:
         so that the reclaimer function can fetch the struct foo address
         and free it:
 
-            call_rcu1(&foo.rcu, foo_reclaim);
+            call_rcu(&foo.rcu, foo_reclaim);
 
             void foo_reclaim(struct rcu_head *rp)
             {
@@ -117,15 +117,15 @@ The core RCU API is small:
         For the common case where the rcu_head member is the first of the
         struct, you can use the following macro.
 
-     void call_rcu(T *p,
-                   void (*func)(T *p),
-                   field-name);
+     void call_rcu_first_elem(T *p,
+                              void (*func)(T *p),
+                              field-name);
 
-        call_rcu1 is typically used through this macro, in the common case
+        call_rcu is typically used through this macro, in the common case
         where the "struct rcu_head" is the first field in the struct.  In
         the above case, one could have written simply:
 
-            call_rcu(foo_reclaim, g_free, rcu);
+            call_rcu_first_elem(foo_reclaim, g_free, rcu);
 
      typeof(*p) atomic_rcu_read(p);
 
@@ -196,10 +196,9 @@ DIFFERENCES WITH LINUX
 - atomic_rcu_read and atomic_rcu_set replace rcu_dereference and
   rcu_assign_pointer.  They take a _pointer_ to the variable being accessed.
 
-- call_rcu is a macro that has an extra argument (the name of the first
-  field in the struct, which must be a struct rcu_head), and expects the
+- call_rcu_first_elem is a macro that has an extra argument (the name of the
+  first field in the struct, which must be a struct rcu_head), and expects the
   type of the callback's argument to be the type of the first argument.
-  call_rcu1 is the same as Linux's call_rcu.
 
 
 RCU PATTERNS
diff --git a/include/qemu/rcu.h b/include/qemu/rcu.h
index 068a279..492d943 100644
--- a/include/qemu/rcu.h
+++ b/include/qemu/rcu.h
@@ -126,13 +126,13 @@ struct rcu_head {
     RCUCBFunc *func;
 };
 
-extern void call_rcu1(struct rcu_head *head, RCUCBFunc *func);
+extern void call_rcu(struct rcu_head *head, RCUCBFunc *func);
 
 /* The operands of the minus operator must have the same type,
  * which must be the one that we specify in the cast.
  */
-#define call_rcu(head, func, field)                                      \
-    call_rcu1(({                                                         \
+#define call_rcu_first_elem(head, func, field)                           \
+    call_rcu(({                                                          \
          char __attribute__((unused))                                    \
             offset_must_be_zero[-offsetof(typeof(*(head)), field)],      \
             func_type_invalid = (func) - (void (*)(typeof(head)))(func); \
diff --git a/memory.c b/memory.c
index 9b91243..dc5e4e9 100644
--- a/memory.c
+++ b/memory.c
@@ -755,7 +755,7 @@ static void address_space_update_topology(AddressSpace *as)
 
     /* Writes are protected by the BQL.  */
     atomic_rcu_set(&as->current_map, new_view);
-    call_rcu(old_view, flatview_unref, rcu);
+    call_rcu_first_elem(old_view, flatview_unref, rcu);
 
     /* Note that all the old MemoryRegions are still alive up to this
      * point.  This relieves most MemoryListeners from the need to
@@ -1983,7 +1983,7 @@ void address_space_destroy(AddressSpace *as)
      * entries that the guest should never use.  Wait for the old
      * values to expire before freeing the data.
      */
-    call_rcu(as, do_address_space_destroy, rcu);
+    call_rcu_first_elem(as, do_address_space_destroy, rcu);
 }
 
 bool io_mem_read(MemoryRegion *mr, hwaddr addr, uint64_t *pval, unsigned size)
diff --git a/util/rcu.c b/util/rcu.c
index c9c3e6e..309a6e4 100644
--- a/util/rcu.c
+++ b/util/rcu.c
@@ -253,7 +253,7 @@ static void *call_rcu_thread(void *opaque)
     abort();
 }
 
-void call_rcu1(struct rcu_head *node, void (*func)(struct rcu_head *node))
+void call_rcu(struct rcu_head *node, void (*func)(struct rcu_head *node))
 {
     node->func = func;
     enqueue(node);
-- 
1.8.3

[Qemu-devel] [PATCH 2/3] rcu: use rcu_{dereference, assign_pointer} instead of atomic_rcu_{read, set}

[Emilio G. Cota]

This matches the semantics of liburcu.

Signed-off-by: Emilio G. Cota <cota@braap.org>
---
 docs/rcu.txt          | 33 +++++++++++++++------------------
 include/qemu/atomic.h | 35 ++++++++++++++++++-----------------
 memory.c              |  6 +++---
 tests/rcutorture.c    |  4 ++--
 4 files changed, 38 insertions(+), 40 deletions(-)

diff --git a/docs/rcu.txt b/docs/rcu.txt
index 575f563..154b18a 100644
--- a/docs/rcu.txt
+++ b/docs/rcu.txt
@@ -127,13 +127,13 @@ The core RCU API is small:
 
             call_rcu_first_elem(foo_reclaim, g_free, rcu);
 
-     typeof(*p) atomic_rcu_read(p);
+     typeof(p) rcu_dereference(p);
 
-        atomic_rcu_read() is similar to atomic_mb_read(), but it makes
+        rcu_dereference() is similar to atomic_mb_read(), but it makes
         some assumptions on the code that calls it.  This allows a more
         optimized implementation.
 
-        atomic_rcu_read assumes that whenever a single RCU critical
+        rcu_dereference assumes that whenever a single RCU critical
         section reads multiple shared data, these reads are either
         data-dependent or need no ordering.  This is almost always the
         case when using RCU, because read-side critical sections typically
@@ -141,7 +141,7 @@ The core RCU API is small:
         every update) until reaching a data structure of interest,
         and then read from there.
 
-        RCU read-side critical sections must use atomic_rcu_read() to
+        RCU read-side critical sections must use rcu_dereference() to
         read data, unless concurrent writes are presented by another
         synchronization mechanism.
 
@@ -149,18 +149,18 @@ The core RCU API is small:
         data structure in a single direction, opposite to the direction
         in which the updater initializes it.
 
-     void atomic_rcu_set(p, typeof(*p) v);
+     void rcu_assign_pointer(p, typeof(p) v);
 
-        atomic_rcu_set() is also similar to atomic_mb_set(), and it also
+        rcu_assign_pointer() is also similar to atomic_mb_set(), and it also
         makes assumptions on the code that calls it in order to allow a more
         optimized implementation.
 
-        In particular, atomic_rcu_set() suffices for synchronization
+        In particular, rcu_assign_pointer() suffices for synchronization
         with readers, if the updater never mutates a field within a
         data item that is already accessible to readers.  This is the
         case when initializing a new copy of the RCU-protected data
         structure; just ensure that initialization of *p is carried out
-        before atomic_rcu_set() makes the data item visible to readers.
+        before rcu_assign_pointer() makes the data item visible to readers.
         If this rule is observed, writes will happen in the opposite
         order as reads in the RCU read-side critical sections (or if
         there is just one update), and there will be no need for other
@@ -193,9 +193,6 @@ DIFFERENCES WITH LINUX
   programming; not allowing this would prevent upgrading an RCU read-side
   critical section to become an updater.
 
-- atomic_rcu_read and atomic_rcu_set replace rcu_dereference and
-  rcu_assign_pointer.  They take a _pointer_ to the variable being accessed.
-
 - call_rcu_first_elem is a macro that has an extra argument (the name of the
   first field in the struct, which must be a struct rcu_head), and expects the
   type of the callback's argument to be the type of the first argument.
@@ -237,7 +234,7 @@ may be used as a restricted reference-counting mechanism.  For example,
 consider the following code fragment:
 
     rcu_read_lock();
-    p = atomic_rcu_read(&foo);
+    p = rcu_dereference(foo);
     /* do something with p. */
     rcu_read_unlock();
 
@@ -248,7 +245,7 @@ The write side looks simply like this (with appropriate locking):
 
     qemu_mutex_lock(&foo_mutex);
     old = foo;
-    atomic_rcu_set(&foo, new);
+    rcu_assign_pointer(foo, new);
     qemu_mutex_unlock(&foo_mutex);
     synchronize_rcu();
     free(old);
@@ -257,7 +254,7 @@ If the processing cannot be done purely within the critical section, it
 is possible to combine this idiom with a "real" reference count:
 
     rcu_read_lock();
-    p = atomic_rcu_read(&foo);
+    p = rcu_dereference(foo);
     foo_ref(p);
     rcu_read_unlock();
     /* do something with p. */
@@ -267,7 +264,7 @@ The write side can be like this:
 
     qemu_mutex_lock(&foo_mutex);
     old = foo;
-    atomic_rcu_set(&foo, new);
+    rcu_assign_pointer(foo, new);
     qemu_mutex_unlock(&foo_mutex);
     synchronize_rcu();
     foo_unref(old);
@@ -276,7 +273,7 @@ or with call_rcu:
 
     qemu_mutex_lock(&foo_mutex);
     old = foo;
-    atomic_rcu_set(&foo, new);
+    rcu_assign_pointer(foo, new);
     qemu_mutex_unlock(&foo_mutex);
     call_rcu(foo_unref, old, rcu);
 
@@ -355,7 +352,7 @@ Instead, we store the size of the array with the array itself:
 
     read side:
         rcu_read_lock();
-        struct arr *array = atomic_rcu_read(&global_array);
+        struct arr *array = rcu_dereference(global_array);
         x = i < array->size ? array->data[i] : -1;
         rcu_read_unlock();
         return x;
@@ -372,7 +369,7 @@ Instead, we store the size of the array with the array itself:
 
             /* Removal phase.  */
             old_array = global_array;
-            atomic_rcu_set(&new_array->data, new_array);
+            rcu_assign_pointer(new_array->data, new_array);
             synchronize_rcu();
 
             /* Reclamation phase.  */
diff --git a/include/qemu/atomic.h b/include/qemu/atomic.h
index 98e05ca..4795e28 100644
--- a/include/qemu/atomic.h
+++ b/include/qemu/atomic.h
@@ -130,7 +130,7 @@
 #endif
 
 /**
- * atomic_rcu_read - reads a RCU-protected pointer to a local variable
+ * rcu_dereference - reads a RCU-protected pointer to a local variable
  * into a RCU read-side critical section. The pointer can later be safely
  * dereferenced within the critical section.
  *
@@ -140,25 +140,26 @@
  * Inserts memory barriers on architectures that require them (currently only
  * Alpha) and documents which pointers are protected by RCU.
  *
- * Unless the __ATOMIC_CONSUME memory order is available, atomic_rcu_read also
+ * Unless the __ATOMIC_CONSUME memory order is available, rcu_dereference also
  * includes a compiler barrier to ensure that value-speculative optimizations
  * (e.g. VSS: Value Speculation Scheduling) does not perform the data read
  * before the pointer read by speculating the value of the pointer.  On new
  * enough compilers, atomic_load takes care of such concern about
  * dependency-breaking optimizations.
  *
- * Should match atomic_rcu_set(), atomic_xchg(), atomic_cmpxchg().
+ * Should match rcu_assign_pointer(), atomic_xchg(), atomic_cmpxchg().
  */
-#ifndef atomic_rcu_read
+#ifndef rcu_dereference
+
 #ifdef __ATOMIC_CONSUME
-#define atomic_rcu_read(ptr)    ({                \
-    typeof(*ptr) _val;                            \
-     __atomic_load(ptr, &_val, __ATOMIC_CONSUME); \
+#define rcu_dereference(ptr)    ({                \
+    typeof(ptr) _val;                             \
+     __atomic_load(&ptr, &_val, __ATOMIC_CONSUME);\
     _val;                                         \
 })
 #else
-#define atomic_rcu_read(ptr)    ({                \
-    typeof(*ptr) _val = atomic_read(ptr);         \
+#define rcu_dereference(ptr)    ({                \
+    typeof(ptr) _val = atomic_read(&ptr);         \
     smp_read_barrier_depends();                   \
     _val;                                         \
 })
@@ -166,7 +167,7 @@
 #endif
 
 /**
- * atomic_rcu_set - assigns (publicizes) a pointer to a new data structure
+ * rcu_assign_pointer - assigns (publicizes) a pointer to a new data structure
  * meant to be read by RCU read-side critical sections.
  *
  * Documents which pointers will be dereferenced by RCU read-side critical
@@ -174,18 +175,18 @@
  * them. It also makes sure the compiler does not reorder code initializing the
  * data structure before its publication.
  *
- * Should match atomic_rcu_read().
+ * Should match rcu_dereference().
  */
-#ifndef atomic_rcu_set
+#ifndef rcu_assign_pointer
 #ifdef __ATOMIC_RELEASE
-#define atomic_rcu_set(ptr, i)  do {              \
-    typeof(*ptr) _val = (i);                      \
-    __atomic_store(ptr, &_val, __ATOMIC_RELEASE); \
+#define rcu_assign_pointer(ptr, i)  do {          \
+    typeof(ptr) _val = (i);                       \
+    __atomic_store(&ptr, &_val, __ATOMIC_RELEASE);\
 } while(0)
 #else
-#define atomic_rcu_set(ptr, i)  do {              \
+#define rcu_assign_pointer(ptr, i)  do {          \
     smp_wmb();                                    \
-    atomic_set(ptr, i);                           \
+    atomic_set(&ptr, i);                          \
 } while (0)
 #endif
 #endif
diff --git a/memory.c b/memory.c
index dc5e4e9..b950259 100644
--- a/memory.c
+++ b/memory.c
@@ -642,7 +642,7 @@ static FlatView *address_space_get_flatview(AddressSpace *as)
     FlatView *view;
 
     rcu_read_lock();
-    view = atomic_rcu_read(&as->current_map);
+    view = rcu_dereference(as->current_map);
     flatview_ref(view);
     rcu_read_unlock();
     return view;
@@ -754,7 +754,7 @@ static void address_space_update_topology(AddressSpace *as)
     address_space_update_topology_pass(as, old_view, new_view, true);
 
     /* Writes are protected by the BQL.  */
-    atomic_rcu_set(&as->current_map, new_view);
+    rcu_assign_pointer(as->current_map, new_view);
     call_rcu_first_elem(old_view, flatview_unref, rcu);
 
     /* Note that all the old MemoryRegions are still alive up to this
@@ -1829,7 +1829,7 @@ MemoryRegionSection memory_region_find(MemoryRegion *mr,
     range = addrrange_make(int128_make64(addr), int128_make64(size));
 
     rcu_read_lock();
-    view = atomic_rcu_read(&as->current_map);
+    view = rcu_dereference(as->current_map);
     fr = flatview_lookup(view, range);
     if (!fr) {
         goto out;
diff --git a/tests/rcutorture.c b/tests/rcutorture.c
index 60a2ccf..2c10107 100644
--- a/tests/rcutorture.c
+++ b/tests/rcutorture.c
@@ -251,7 +251,7 @@ static void *rcu_read_stress_test(void *arg)
     }
     while (goflag == GOFLAG_RUN) {
         rcu_read_lock();
-        p = atomic_rcu_read(&rcu_stress_current);
+        p = rcu_dereference(rcu_stress_current);
         if (p->mbtest == 0) {
             n_mberror++;
         }
@@ -298,7 +298,7 @@ static void *rcu_update_stress_test(void *arg)
         smp_mb();
         p->pipe_count = 0;
         p->mbtest = 1;
-        atomic_rcu_set(&rcu_stress_current, p);
+        rcu_assign_pointer(rcu_stress_current, p);
         rcu_stress_idx = i;
         for (i = 0; i < RCU_STRESS_PIPE_LEN; i++) {
             if (i != rcu_stress_idx) {
-- 
1.8.3

Re: [Qemu-devel] [PATCH 2/3] rcu: use rcu_{dereference, assign_pointer} instead of atomic_rcu_{read, set}

[Paolo Bonzini]

On 03/02/2015 23:08, Emilio G. Cota wrote:
> This matches the semantics of liburcu.

This is not necessary.  The two sets of macros are exactly the same, so
it's okay to use atomic_rcu_read/write.

Paolo

Re: [Qemu-devel] [PATCH 2/3] rcu: use rcu_{dereference, assign_pointer} instead of atomic_rcu_{read, set}

[Emilio G. Cota]

On Wed, Feb 04, 2015 at 11:01:00 +0100, Paolo Bonzini wrote:
> On 03/02/2015 23:08, Emilio G. Cota wrote:
> > This matches the semantics of liburcu.
> 
> This is not necessary.  The two sets of macros are exactly the same, so
> it's okay to use atomic_rcu_read/write.

They're not exactly the same, otherwise the patch would be trivial.

The difference can be seen in the change to the macros' documentation:

On Tue, Feb 03, 2015 at 17:08:18 -0500, Emilio G. Cota wrote:
> This matches the semantics of liburcu.
> --- a/docs/rcu.txt
> +++ b/docs/rcu.txt
(snip)
> -     typeof(*p) atomic_rcu_read(p);
> +     typeof(p) rcu_dereference(p);
(snip)
> -     void atomic_rcu_set(p, typeof(*p) v);
> +     void rcu_assign_pointer(p, typeof(p) v);

The liburcu macros take a variable (usually a pointer, hence the
macros' names, but unsigned long is also common), not its address.

These changes require modifications to the calling code as well, e.g.
memory.c:

struct AddressSpace {
...
    /* Accessed via RCU.  */
    struct FlatView *current_map;
...
};
...
struct FlatView *view;
...
-    view = atomic_rcu_read(&as->current_map);                                                                                                                                                                                                                                                
+    view = rcu_dereference(as->current_map);
...
-    atomic_rcu_set(&as->current_map, new_view);                                                                                                                                                                                                                                              
+    rcu_assign_pointer(as->current_map, new_view);  

Thanks,

		Emilio

Re: [Qemu-devel] [PATCH 2/3] rcu: use rcu_{dereference, assign_pointer} instead of atomic_rcu_{read, set}

[Paolo Bonzini]

On 04/02/2015 18:25, Emilio G. Cota wrote:
> On Wed, Feb 04, 2015 at 11:01:00 +0100, Paolo Bonzini wrote:
>> On 03/02/2015 23:08, Emilio G. Cota wrote:
>>> This matches the semantics of liburcu.
>>
>> This is not necessary.  The two sets of macros are exactly the same, so
>> it's okay to use atomic_rcu_read/write.
> 
> They're not exactly the same, otherwise the patch would be trivial.

You're right, I was imprecise---I meant they are interoperable.  You can
use atomic_rcu_read/write together with liburcu, you do not need to use
the liburcu-provided rcu_dereference/rcu_assign_pointer.

Paolo

> The difference can be seen in the change to the macros' documentation:
> 
> On Tue, Feb 03, 2015 at 17:08:18 -0500, Emilio G. Cota wrote:
>> This matches the semantics of liburcu.
>> --- a/docs/rcu.txt
>> +++ b/docs/rcu.txt
> (snip)
>> -     typeof(*p) atomic_rcu_read(p);
>> +     typeof(p) rcu_dereference(p);
> (snip)
>> -     void atomic_rcu_set(p, typeof(*p) v);
>> +     void rcu_assign_pointer(p, typeof(p) v);
> 
> The liburcu macros take a variable (usually a pointer, hence the
> macros' names, but unsigned long is also common), not its address.
> 
> These changes require modifications to the calling code as well, e.g.
> memory.c:
> 
> struct AddressSpace {
> ...
>     /* Accessed via RCU.  */
>     struct FlatView *current_map;
> ...
> };
> ...
> struct FlatView *view;
> ...
> -    view = atomic_rcu_read(&as->current_map);                                                                                                                                                                                                                                                
> +    view = rcu_dereference(as->current_map);
> ...
> -    atomic_rcu_set(&as->current_map, new_view);                                                                                                                                                                                                                                              
> +    rcu_assign_pointer(as->current_map, new_view);  
> 
> Thanks,
> 
> 		Emilio
> 

[Qemu-devel] [PATCH 3/3] rcu: add liburcu knob to configure script

[Emilio G. Cota]

The default is --disable-liburcu, which means QEMU's RCU
implementation is used.

When building with --enable-liburcu, the memory barrier version
of liburcu (urcu-mb) is linked against. We might want to make this
configurable in the future for greater performance; for now we just
match the liburcu flavor to the one that QEMU's RCU is using.

Note that the rcutorture under test/ doesn't work with --enable-liburcu,
since it relies on some internals of QEMU's RCU. liburcu is tested with
the urcutorture distributed with it.

Signed-off-by: Emilio G. Cota <cota@braap.org>
---
 configure             | 35 +++++++++++++++++++++++++++++++++++
 include/qemu/atomic.h |  4 ++++
 include/qemu/rcu.h    | 38 ++++++++++++++++++++++++--------------
 util/Makefile.objs    |  2 +-
 4 files changed, 64 insertions(+), 15 deletions(-)

diff --git a/configure b/configure
index f185dd0..71c9802 100755
--- a/configure
+++ b/configure
@@ -335,6 +335,7 @@ libssh2=""
 vhdx=""
 quorum=""
 numa=""
+liburcu=""
 
 # parse CC options first
 for opt do
@@ -1129,6 +1130,10 @@ for opt do
   ;;
   --enable-numa) numa="yes"
   ;;
+  --disable-liburcu) liburcu="no"
+  ;;
+  --enable-liburcu) liburcu="yes"
+  ;;
   *)
       echo "ERROR: unknown option $opt"
       echo "Try '$0 --help' for more information"
@@ -1400,6 +1405,8 @@ Advanced options (experts only):
   --enable-quorum          enable quorum block filter support
   --disable-numa           disable libnuma support
   --enable-numa            enable libnuma support
+  --disable-liburcu        disable liburcu, use QEMU RCU instead
+  --enable-liburcu         enable liburcu, the user-space RCU library
 
 NOTE: The object files are built at the place where configure is launched
 EOF
@@ -3277,6 +3284,29 @@ EOF
 fi
 
 ##########################################
+# liburcu probe
+
+if test "$liburcu" != "no" ; then
+  cat > $TMPC << EOF
+char synchronize_rcu_mb();
+int main()
+{
+    return synchronize_rcu_mb ();
+}
+EOF
+
+  if compile_prog "" "-lurcu-mb" ; then
+    liburcu=yes
+    libs_softmmu="-lurcu-mb $libs_softmmu"
+  else
+    if test "$liburcu" = "yes" ; then
+      feature_not_found "liburcu" "install liburcu > v0.6, or --disable-liburcu"
+    fi
+    liburcu=no
+  fi
+fi
+
+##########################################
 # signalfd probe
 signalfd="no"
 cat > $TMPC << EOF
@@ -4370,6 +4400,7 @@ echo "Quorum            $quorum"
 echo "lzo support       $lzo"
 echo "snappy support    $snappy"
 echo "NUMA host support $numa"
+echo "liburcu support   $liburcu"
 
 if test "$sdl_too_old" = "yes"; then
 echo "-> Your SDL version is too old - please upgrade to have SDL support"
@@ -5368,6 +5399,10 @@ if test "$numa" = "yes"; then
   echo "CONFIG_NUMA=y" >> $config_host_mak
 fi
 
+if test "$liburcu" = "yes"; then
+  echo "CONFIG_LIBURCU=y" >> $config_host_mak
+fi
+
 # build tree in object directory in case the source is not in the current directory
 DIRS="tests tests/tcg tests/tcg/cris tests/tcg/lm32 tests/libqos tests/qapi-schema tests/tcg/xtensa tests/qemu-iotests"
 DIRS="$DIRS fsdev"
diff --git a/include/qemu/atomic.h b/include/qemu/atomic.h
index 4795e28..d7ad0d5 100644
--- a/include/qemu/atomic.h
+++ b/include/qemu/atomic.h
@@ -129,6 +129,8 @@
 #define atomic_set(ptr, i)     ((*(__typeof__(*ptr) volatile*) (ptr)) = (i))
 #endif
 
+#ifndef CONFIG_LIBURCU
+
 /**
  * rcu_dereference - reads a RCU-protected pointer to a local variable
  * into a RCU read-side critical section. The pointer can later be safely
@@ -191,6 +193,8 @@
 #endif
 #endif
 
+#endif /* !CONFIG_LIBURCU */
+
 /* These have the same semantics as Java volatile variables.
  * See http://gee.cs.oswego.edu/dl/jmm/cookbook.html:
  * "1. Issue a StoreStore barrier (wmb) before each volatile store."
diff --git a/include/qemu/rcu.h b/include/qemu/rcu.h
index 492d943..0aeb8f0 100644
--- a/include/qemu/rcu.h
+++ b/include/qemu/rcu.h
@@ -40,6 +40,29 @@
 extern "C" {
 #endif
 
+struct rcu_head;
+typedef void RCUCBFunc(struct rcu_head *head);
+
+/* The operands of the minus operator must have the same type,
+ * which must be the one that we specify in the cast.
+ */
+#define call_rcu_first_elem(head, func, field)                           \
+    call_rcu(({                                                          \
+         char __attribute__((unused))                                    \
+            offset_must_be_zero[-offsetof(typeof(*(head)), field)],      \
+            func_type_invalid = (func) - (void (*)(typeof(head)))(func); \
+         &(head)->field;                                                 \
+      }),                                                                \
+      (RCUCBFunc *)(func))
+
+#ifdef CONFIG_LIBURCU
+
+#define _LGPL_SOURCE
+#define RCU_MB
+#include <urcu.h>
+
+#else
+
 /*
  * Important !
  *
@@ -118,9 +141,6 @@ extern void synchronize_rcu(void);
 extern void rcu_register_thread(void);
 extern void rcu_unregister_thread(void);
 
-struct rcu_head;
-typedef void RCUCBFunc(struct rcu_head *head);
-
 struct rcu_head {
     struct rcu_head *next;
     RCUCBFunc *func;
@@ -128,17 +148,7 @@ struct rcu_head {
 
 extern void call_rcu(struct rcu_head *head, RCUCBFunc *func);
 
-/* The operands of the minus operator must have the same type,
- * which must be the one that we specify in the cast.
- */
-#define call_rcu_first_elem(head, func, field)                           \
-    call_rcu(({                                                          \
-         char __attribute__((unused))                                    \
-            offset_must_be_zero[-offsetof(typeof(*(head)), field)],      \
-            func_type_invalid = (func) - (void (*)(typeof(head)))(func); \
-         &(head)->field;                                                 \
-      }),                                                                \
-      (RCUCBFunc *)(func))
+#endif /* CONFIG_LIBURCU */
 
 #ifdef __cplusplus
 }
diff --git a/util/Makefile.objs b/util/Makefile.objs
index ceaba30..eacc4c4 100644
--- a/util/Makefile.objs
+++ b/util/Makefile.objs
@@ -17,4 +17,4 @@ util-obj-y += throttle.o
 util-obj-y += getauxval.o
 util-obj-y += readline.o
 util-obj-y += rfifolock.o
-util-obj-y += rcu.o
+util-obj-$(call lnot,$(CONFIG_LIBURCU)) += rcu.o
-- 
1.8.3

Re: [Qemu-devel] [PATCH 0/3] rcu: add option to use upstream liburcu

[Paolo Bonzini]

On 03/02/2015 23:08, Emilio G. Cota wrote:
> * The first two patches bring back the RCU API to exactly
>   match that of liburcu.

Bringing over rcu_dereference/rcu_assign_pointer is unnecessary, I
think.  The names do not conflict.

As to call_rcu/call_rcu1, I understand there is a problem.  Maybe call
the QEMU versions rcu_call/rcu_call1?  Then you can add simple wrappers
if you want to use liburcu-mb.

> * The third patch adds a configure flag to choose from either
>   liburcu or QEMU's RCU.
> 
> Apart from this, I wonder what to do about other valuable bits in
> liburcu, particularly in liburcu-cds, which I'm using currently
> off-tree.  I see three ways of eventually doing this:
> 
> a) Add Windows support in liburcu, thereby eliminating the
>    de facto fork in QEMU.

This would be certainly doable.

Note that liburcu is not widely packaged, so we would have to add it as
a submodule.  What is the advantage of using liburcu?

> b) Bring (fork) liburcu-cds to QEMU, just like liburcu-mb was.

To some extent this is what we're doing.  cds is very much inspired by
the Linux kernel, but QEMU is already using both BSD (intrusive) and
GLib (non-intrusive) lists, and I didn't like the idea of adding yet
another API.  I like the simplicity of the Linux hlist/list APIs, but
two kinds of lists are already one too many.

So, part 2 of the RCU work has an API for RCU lists based on BSD lists
(that QEMU is already using).  These are not the lock-free data
structures available in CDS, just the usual RCU-based lists with
blocking write side and wait-free read side.

QEMU has very limited support for (non-RCU-based) lock-free data
structures in qemu/queue.h: see QSLIST_INSERT_HEAD_ATOMIC and
QSLIST_MOVE_ATOMIC.  The call_rcu implementation in util/rcu.c is based
on wfqueue from liburcu-cds, but it would not be hard to change it to
use QSLIST_INSERT_HEAD_ATOMIC/QSLIST_MOVE_ATOMIC instead.  In both cases
the data structure is multi-producer/single-consumer.

QEMU hardly uses hash tables at all.

Another thing to note is that I didn't envision a huge use of RCU in
QEMU; I'm employing it in decidedly central places where it can bring
great benefit, but I wouldn't be surprised if RCU only found a handful
of users in the end.

Coarse locks with very low contention (such as AioContext) have great
performance, and most data structures in QEMU fit this model: data
structures for separate devices are more or less independent, and the
lock is only needed for the rare cases when the main thread (for example
the monitor) interacts with the device.

> c) Add a compile-time flag (say CONFIG_LIBURCU_CDS), and then only
>    use data structures from liburcu-cds where appropriate, falling
>    back to traditional locked structures when !CONFIG_LIBURCU_CDS.
> 
> Would c) be acceptable for upstream, provided the gains (say in
> scalability/memory footprint) are significant?

I think if there were a killer use of liburcu-cds, we would just port
liburcu (the mb, bp and qsbr variants) to Windows, and switch to
liburcu-mb/liburcu-cds.

This brings the most important question of all: what are you doing with
QEMU? :)

Paolo

Re: [Qemu-devel] [PATCH 0/3] rcu: add option to use upstream liburcu

[Emilio G. Cota]

On Wed, Feb 04, 2015 at 11:32:57 +0100, Paolo Bonzini wrote:
> On 03/02/2015 23:08, Emilio G. Cota wrote:
> > * The first two patches bring back the RCU API to exactly
> >   match that of liburcu.
> 
> Bringing over rcu_dereference/rcu_assign_pointer is unnecessary, I
> think.  The names do not conflict.

On Wed, Feb 04, 2015 at 18:31:55 +0100, Paolo Bonzini wrote:
> On 04/02/2015 18:25, Emilio G. Cota wrote:
> > They're not exactly the same, otherwise the patch would be trivial.
> 
> You're right, I was imprecise---I meant they are interoperable.  You can
> use atomic_rcu_read/write together with liburcu, you do not need to use
> the liburcu-provided rcu_dereference/rcu_assign_pointer.

It's true that they can coexist. I'm just not sold on having two ways
of doing the same thing. It would make more sense to me to only divert
from the original API if there's a good reason to do so -- otherwise
an eventual merge (say after option a) discussed below) would be more
painful than necessary.

On Wed, Feb 04, 2015 at 11:32:57 +0100, Paolo Bonzini wrote:
> As to call_rcu/call_rcu1, I understand there is a problem.  Maybe call
> the QEMU versions rcu_call/rcu_call1?  Then you can add simple wrappers
> if you want to use liburcu-mb.

Again, adhering to the original API if possible makes more sense to me, to
prevent future confusion.

> > * The third patch adds a configure flag to choose from either
> >   liburcu or QEMU's RCU.
> > 
> > Apart from this, I wonder what to do about other valuable bits in
> > liburcu, particularly in liburcu-cds, which I'm using currently
> > off-tree.  I see three ways of eventually doing this:
> > 
> > a) Add Windows support in liburcu, thereby eliminating the
> >    de facto fork in QEMU.
> 
> This would be certainly doable.
> 
> Note that liburcu is not widely packaged, so we would have to add it as
> a submodule.  What is the advantage of using liburcu?

Better testing, (eventually) less work, less bugs, no code duplication,
ability to just merge new features from upstream.

Essentially the usual reasons against forking a project.

> > b) Bring (fork) liburcu-cds to QEMU, just like liburcu-mb was.
> 
> To some extent this is what we're doing.  cds is very much inspired by
> the Linux kernel, but QEMU is already using both BSD (intrusive) and
> GLib (non-intrusive) lists, and I didn't like the idea of adding yet
> another API.  I like the simplicity of the Linux hlist/list APIs, but
> two kinds of lists are already one too many.

Agreed.

> So, part 2 of the RCU work has an API for RCU lists based on BSD lists
> (that QEMU is already using).  These are not the lock-free data
> structures available in CDS, just the usual RCU-based lists with
> blocking write side and wait-free read side.
> 
> QEMU has very limited support for (non-RCU-based) lock-free data
> structures in qemu/queue.h: see QSLIST_INSERT_HEAD_ATOMIC and
> QSLIST_MOVE_ATOMIC.  The call_rcu implementation in util/rcu.c is based
> on wfqueue from liburcu-cds, but it would not be hard to change it to
> use QSLIST_INSERT_HEAD_ATOMIC/QSLIST_MOVE_ATOMIC instead.  In both cases
> the data structure is multi-producer/single-consumer.
> 
> 
> QEMU hardly uses hash tables at all.

I understand there's currently not much demand for these. I think however
they might become valuable in the future, provided we end up having
a multi-threaded TCG.

> Another thing to note is that I didn't envision a huge use of RCU in
> QEMU; I'm employing it in decidedly central places where it can bring
> great benefit, but I wouldn't be surprised if RCU only found a handful
> of users in the end.

If RCU's history in the linux kernel is of any guide, chances are RCU
will end up being used in more places than one could initially guess:

  http://www2.rdrop.com/~paulmck/techreports/RCUUsage.2013.02.24a.pdf

I think the same reasoning is likely to apply to the concurrent data
structures in liburcu-cds.

> Coarse locks with very low contention (such as AioContext) have great
> performance, and most data structures in QEMU fit this model: data
> structures for separate devices are more or less independent, and the
> lock is only needed for the rare cases when the main thread (for example
> the monitor) interacts with the device.

Agreed, this has worked well so far.

> > c) Add a compile-time flag (say CONFIG_LIBURCU_CDS), and then only
> >    use data structures from liburcu-cds where appropriate, falling
> >    back to traditional locked structures when !CONFIG_LIBURCU_CDS.
> > 
> > Would c) be acceptable for upstream, provided the gains (say in
> > scalability/memory footprint) are significant?
> 
> I think if there were a killer use of liburcu-cds, we would just port
> liburcu (the mb, bp and qsbr variants) to Windows, and switch to
> liburcu-mb/liburcu-cds.

Agreed.

> This brings the most important question of all: what are you doing with
> QEMU? :)

So far I've been tinkering with it as a frontend for an instruction-set
simulator. I've managed to make it scale (TCG-based "multicore on multicore")
very well up to dozens of cores by modifying qsim[1], which requires one
library file per guest core.

What I'm investigating now is how to do this in a manner that is palatable
to upstream. For this as it's well known we need a multi-threaded TCG,
and I believe quite a few bits from liburcu(-cds) might help to
get there.

So for now I'll keep the liburcu(-cds) compile option in my tree and
see how far I can get. Of course I'll keep fallback code using locks
in there so that we can measure the performance differences.

Thanks,

		Emilio

[1] https://github.com/cdkersey/qsim

Re: [Qemu-devel] [PATCH 0/3] rcu: add option to use upstream liburcu

[Paolo Bonzini]

On 04/02/2015 22:01, Emilio G. Cota wrote:
>> You're right, I was imprecise---I meant they are interoperable.  You can
>> use atomic_rcu_read/write together with liburcu, you do not need to use
>> the liburcu-provided rcu_dereference/rcu_assign_pointer.
> 
> It's true that they can coexist. I'm just not sold on having two ways
> of doing the same thing. It would make more sense to me to only divert
> from the original API if there's a good reason to do so -- otherwise
> an eventual merge (say after option a) discussed below) would be more
> painful than necessary.

The good reason was to mimic the C11 atomic_load/atomic_store functions.

>> As to call_rcu/call_rcu1, I understand there is a problem.  Maybe call
>> the QEMU versions rcu_call/rcu_call1?  Then you can add simple wrappers
>> if you want to use liburcu-mb.
> 
> Again, adhering to the original API if possible makes more sense to me, to
> prevent future confusion.

Here the good reason is that QEMU's version of call_rcu is type-safe.

> Better testing, (eventually) less work, less bugs, no code duplication,
> ability to just merge new features from upstream.
> 
> Essentially the usual reasons against forking a project.

Agreed.

>> QEMU hardly uses hash tables at all.
> 
> I understand there's currently not much demand for these. I think however
> they might become valuable in the future, provided we end up having
> a multi-threaded TCG.
> 
> If RCU's history in the linux kernel is of any guide, chances are RCU
> will end up being used in more places than one could initially guess:
> 
>   http://www2.rdrop.com/~paulmck/techreports/RCUUsage.2013.02.24a.pdf

Yes, that's possible.  However, the "stupid coarse lock" strategy does
not work too well for Linux because you have N processes banging on the
same device or file system.  QEMU has much higher separation between
components: all the complicated stuff happens in the guest.

> What I'm investigating now is how to do this in a manner that is palatable
> to upstream. For this as it's well known we need a multi-threaded TCG,
> and I believe quite a few bits from liburcu(-cds) might help to
> get there.

Are you using (or planning to use) a shared translated code cache, or a
separate cache for each CPU?

Paolo

> So for now I'll keep the liburcu(-cds) compile option in my tree and
> see how far I can get. Of course I'll keep fallback code using locks
> in there so that we can measure the performance differences.
> 
> Thanks,
> 
> 		Emilio
> 
> [1] https://github.com/cdkersey/qsim
> 
> 
> 

Re: [Qemu-devel] [PATCH 0/3] rcu: add option to use upstream liburcu

[Emilio G. Cota]

On Wed, Feb 04, 2015 at 22:17:44 +0100, Paolo Bonzini wrote:
> > What I'm investigating now is how to do this in a manner that is palatable
> > to upstream. For this as it's well known we need a multi-threaded TCG,
> > and I believe quite a few bits from liburcu(-cds) might help to
> > get there.
> 
> Are you using (or planning to use) a shared translated code cache, or a
> separate cache for each CPU?

Hoping to try both in the end--currently I'm far from trying either,
got quite a few things to fix before that.

Cheers,

		Emilio