Introducing basic RCU primitives for lock-less shared data structures

6 files changed, 142 insertions, 1 deletions

diff --git a/lib/Makefile b/lib/Makefile
index 15f757d9..f4ade9a6 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -1,4 +1,4 @@
-src := a-path.c a-set.c 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 := a-path.c a-set.c 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 rcu.c resource.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/io-loop.h b/lib/io-loop.h
index dec7d040..2450a609 100644
--- a/lib/io-loop.h
+++ b/lib/io-loop.h
@@ -51,4 +51,8 @@ void birdloop_unlink(struct birdloop *loop);
 void birdloop_ping(struct birdloop *loop);
 
 void birdloop_init(void);
+
+/* Yield for a little while. Use only in special cases. */
+void birdloop_yield(void);
+
 #endif /* _BIRD_IO_LOOP_H_ */
diff --git a/lib/locking.h b/lib/locking.h
index 8ea1c968..a9a8aa9b 100644
--- a/lib/locking.h
+++ b/lib/locking.h
@@ -16,6 +16,7 @@ struct lock_order {
   struct domain_generic *the_bird;
   struct domain_generic *proto;
   struct domain_generic *rtable;
+  struct domain_generic *resource;
 };
 
 extern _Thread_local struct lock_order locking_stack;
diff --git a/lib/rcu.c b/lib/rcu.c
new file mode 100644
index 00000000..83fdd022
--- /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/io-loop.h"
+#include "lib/locking.h"
+
+_Atomic uint rcu_gp_ctl = RCU_NEST_CNT;
+_Thread_local struct rcu_birdloop *this_rcu_birdloop = NULL;
+
+static list rcu_birdloop_list;
+
+static struct rcu_birdloop main_rcu_birdloop;
+
+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_birdloop *rc;
+  WALK_LIST(rc, rcu_birdloop_list)
+    while (rcu_gp_ongoing(&rc->ctl))
+      birdloop_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_birdloop_start(struct rcu_birdloop *rc)
+{
+  LOCK_DOMAIN(resource, rcu_domain);
+  add_tail(&rcu_birdloop_list, &rc->n);
+  this_rcu_birdloop = rc;
+  UNLOCK_DOMAIN(resource, rcu_domain);
+}
+
+void
+rcu_birdloop_stop(struct rcu_birdloop *rc)
+{
+  LOCK_DOMAIN(resource, rcu_domain);
+  this_rcu_birdloop = 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_birdloop_list);
+  rcu_birdloop_start(&main_rcu_birdloop);
+}
diff --git a/lib/rcu.h b/lib/rcu.h
new file mode 100644
index 00000000..c537a1ef
--- /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_birdloop {
+  node n;
+  _Atomic uint ctl;
+};
+
+extern _Thread_local struct rcu_birdloop *this_rcu_birdloop;
+
+static inline void rcu_read_lock(void)
+{
+  uint cmp = atomic_load_explicit(&this_rcu_birdloop->ctl, memory_order_acquire);
+
+  if (cmp & RCU_NEST_MASK)
+    atomic_store_explicit(&this_rcu_birdloop->ctl, cmp + RCU_NEST_CNT, memory_order_relaxed);
+  else
+    atomic_store(&this_rcu_birdloop->ctl, atomic_load_explicit(&rcu_gp_ctl, memory_order_acquire));
+}
+
+static inline void rcu_read_unlock(void)
+{
+  atomic_fetch_sub(&this_rcu_birdloop->ctl, RCU_NEST_CNT);
+}
+
+void synchronize_rcu(void);
+
+/* Registering and unregistering a birdloop. To be called from birdloop implementation */
+void rcu_birdloop_start(struct rcu_birdloop *);
+void rcu_birdloop_stop(struct rcu_birdloop *);
+
+/* Run this from resource init */
+void rcu_init(void);
+
+#endif
diff --git a/lib/resource.c b/lib/resource.c
index a33fd214..898fb533 100644
--- a/lib/resource.c
+++ b/lib/resource.c
@@ -14,6 +14,7 @@
 #include "nest/bird.h"
 #include "lib/resource.h"
 #include "lib/string.h"
+#include "lib/rcu.h"
 
 /**
  * DOC: Resource pools
@@ -279,6 +280,7 @@ void
 resource_init(void)
 {
   resource_sys_init();
+  rcu_init();
 
   root_pool.r.class = &pool_class;
   root_pool.name = "Root";