diff options
| -rw-r--r-- | lib/Makefile | 2 | ||||
| -rw-r--r-- | lib/coro.h | 2 | ||||
| -rw-r--r-- | lib/rcu.c | 79 | ||||
| -rw-r--r-- | lib/rcu.h | 55 | ||||
| -rw-r--r-- | lib/resource.c | 3 | ||||
| -rw-r--r-- | sysdep/unix/coroutine.c | 10 |
6 files changed, 150 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) @@ -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); diff --git a/sysdep/unix/coroutine.c b/sysdep/unix/coroutine.c index 4758c056..12ba55d8 100644 --- a/sysdep/unix/coroutine.c +++ b/sysdep/unix/coroutine.c @@ -18,6 +18,7 @@ #include "lib/birdlib.h" #include "lib/locking.h" #include "lib/coro.h" +#include "lib/rcu.h" #include "lib/resource.h" #include "lib/timer.h" @@ -128,6 +129,7 @@ struct coroutine { resource r; pthread_t id; pthread_attr_t attr; + struct rcu_coro rcu; void (*entry)(void *); void *data; }; @@ -137,6 +139,7 @@ static _Thread_local _Bool coro_cleaned_up = 0; static void coro_free(resource *r) { struct coroutine *c = (void *) r; + rcu_coro_stop(&c->rcu); ASSERT_DIE(pthread_equal(pthread_self(), c->id)); pthread_attr_destroy(&c->attr); coro_cleaned_up = 1; @@ -157,6 +160,7 @@ static void *coro_entry(void *p) ASSERT_DIE(c->entry); this_coro = c; + rcu_coro_start(&c->rcu); c->entry(c->data); ASSERT_DIE(coro_cleaned_up); @@ -190,3 +194,9 @@ struct coroutine *coro_run(pool *p, void (*entry)(void *), void *data) return c; } + +void +coro_yield(void) +{ + usleep(100); +} |