Introducing basic RCU primitives for lock-less shared data structures

5 files changed, 140 insertions, 1 deletions

diff --git a/lib/Makefile b/lib/Makefile
index 4378a7bd..98c5db3c 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -1,4 +1,4 @@
-src := bitmap.c bitops.c blake2s.c blake2b.c checksum.c event.c flowspec.c idm.c ip.c lists.c mac.c md5.c mempool.c net.c patmatch.c printf.c resource.c sha1.c sha256.c sha512.c slab.c slists.c strtoul.c tbf.c timer.c xmalloc.c
+src := bitmap.c bitops.c blake2s.c blake2b.c checksum.c event.c flowspec.c idm.c ip.c lists.c mac.c md5.c mempool.c net.c patmatch.c printf.c resource.c rcu.c sha1.c sha256.c sha512.c slab.c slists.c strtoul.c tbf.c timer.c xmalloc.c
 obj := $(src-o-files)
 $(all-daemon)
 
diff --git a/lib/coro.h b/lib/coro.h
index 17ccff89..b36f1d2c 100644
--- a/lib/coro.h
+++ b/lib/coro.h
@@ -25,5 +25,7 @@ struct coroutine *coro_run(pool *, void (*entry)(void *), void *data);
 /* Get self. */
 extern _Thread_local struct coroutine *this_coro;
 
+/* Just wait for a little while. Not intended for general use; use events if possible. */
+void coro_yield(void);
 
 #endif
diff --git a/lib/rcu.c b/lib/rcu.c
new file mode 100644
index 00000000..69f3442f
--- /dev/null
+++ b/lib/rcu.c
@@ -0,0 +1,79 @@
+/*
+ *	BIRD Library -- Read-Copy-Update Basic Operations
+ *
+ *	(c) 2021 Maria Matejka <mq@jmq.cz>
+ *	(c) 2021 CZ.NIC z.s.p.o.
+ *
+ *	Can be freely distributed and used under the terms of the GNU GPL.
+ *	Note: all the relevant patents shall be expired.
+ *
+ *	Using the Supplementary Material for User-Level Implementations of Read-Copy-Update
+ *	by Matthieu Desnoyers, Paul E. McKenney, Alan S. Stern, Michel R. Dagenais and Jonathan Walpole
+ *	obtained from https://www.efficios.com/pub/rcu/urcu-supp-accepted.pdf
+ */
+
+#include "lib/rcu.h"
+#include "lib/coro.h"
+#include "lib/locking.h"
+
+_Atomic uint rcu_gp_ctl = RCU_NEST_CNT;
+_Thread_local struct rcu_coro *this_rcu_coro = NULL;
+
+static list rcu_coro_list;
+
+static struct rcu_coro main_rcu_coro;
+
+DEFINE_DOMAIN(resource);
+static DOMAIN(resource) rcu_domain;
+
+static int
+rcu_gp_ongoing(_Atomic uint *ctl)
+{
+  uint val = atomic_load(ctl);
+  return (val & RCU_NEST_CNT) && ((val ^ rcu_gp_ctl) & RCU_GP_PHASE);
+}
+
+static void
+update_counter_and_wait(void)
+{
+  atomic_fetch_xor(&rcu_gp_ctl, RCU_GP_PHASE);
+  struct rcu_coro *rc;
+  WALK_LIST(rc, rcu_coro_list)
+    while (rcu_gp_ongoing(&rc->ctl))
+      coro_yield();
+}
+
+void
+synchronize_rcu(void)
+{
+  LOCK_DOMAIN(resource, rcu_domain);
+  update_counter_and_wait();
+  update_counter_and_wait();
+  UNLOCK_DOMAIN(resource, rcu_domain);
+}
+
+void
+rcu_coro_start(struct rcu_coro *rc)
+{
+  LOCK_DOMAIN(resource, rcu_domain);
+  add_tail(&rcu_coro_list, &rc->n);
+  this_rcu_coro = rc;
+  UNLOCK_DOMAIN(resource, rcu_domain);
+}
+
+void
+rcu_coro_stop(struct rcu_coro *rc)
+{
+  LOCK_DOMAIN(resource, rcu_domain);
+  this_rcu_coro = NULL;
+  rem_node(&rc->n);
+  UNLOCK_DOMAIN(resource, rcu_domain);
+}
+
+void
+rcu_init(void)
+{
+  rcu_domain = DOMAIN_NEW(resource, "Read-Copy-Update");
+  init_list(&rcu_coro_list);
+  rcu_coro_start(&main_rcu_coro);
+}
diff --git a/lib/rcu.h b/lib/rcu.h
new file mode 100644
index 00000000..ac8fc9ce
--- /dev/null
+++ b/lib/rcu.h
@@ -0,0 +1,55 @@
+/*
+ *	BIRD Library -- Read-Copy-Update Basic Operations
+ *
+ *	(c) 2021 Maria Matejka <mq@jmq.cz>
+ *	(c) 2021 CZ.NIC z.s.p.o.
+ *
+ *	Can be freely distributed and used under the terms of the GNU GPL.
+ *	Note: all the relevant patents shall be expired.
+ */
+
+#ifndef _BIRD_RCU_H_
+#define _BIRD_RCU_H_
+
+#include "lib/birdlib.h"
+#include "lib/lists.h"
+#include <stdatomic.h>
+
+#define RCU_GP_PHASE  0x100000
+#define RCU_NEST_MASK 0x0fffff
+#define RCU_NEST_CNT  0x000001
+
+extern _Atomic uint rcu_gp_ctl;
+
+struct rcu_coro {
+  node n;
+  _Atomic uint ctl;
+};
+
+extern _Thread_local struct rcu_coro *this_rcu_coro;
+
+static inline void rcu_read_lock(void)
+{
+  uint cmp = atomic_load_explicit(&this_rcu_coro->ctl, memory_order_acquire);
+
+  if (cmp & RCU_NEST_MASK)
+    atomic_store_explicit(&this_rcu_coro->ctl, cmp + RCU_NEST_CNT, memory_order_relaxed);
+  else
+    atomic_store(&this_rcu_coro->ctl, atomic_load_explicit(&rcu_gp_ctl, memory_order_acquire));
+}
+
+static inline void rcu_read_unlock(void)
+{
+  atomic_fetch_sub(&this_rcu_coro->ctl, RCU_NEST_CNT);
+}
+
+void synchronize_rcu(void);
+
+/* Registering and unregistering a coroutine. To be called from coroutine implementation */
+void rcu_coro_start(struct rcu_coro *);
+void rcu_coro_stop(struct rcu_coro *);
+
+/* Run this from resource init */
+void rcu_init(void);
+
+#endif
diff --git a/lib/resource.c b/lib/resource.c
index 2d041ad5..0651406f 100644
--- a/lib/resource.c
+++ b/lib/resource.c
@@ -13,6 +13,7 @@
 #include "nest/bird.h"
 #include "lib/resource.h"
 #include "lib/string.h"
+#include "lib/rcu.h"
 
 /**
  * DOC: Resource pools
@@ -284,6 +285,8 @@ rlookup(unsigned long a)
 void
 resource_init(void)
 {
+  rcu_init();
+
   root_pool.r.class = &pool_class;
   root_pool.name = "Root";
   init_list(&root_pool.inside);