diff options
| -rw-r--r-- | lib/Makefile | 2 | ||||
| -rw-r--r-- | lib/io-loop.h | 4 | ||||
| -rw-r--r-- | lib/locking.h | 1 | ||||
| -rw-r--r-- | lib/rcu.c | 79 | ||||
| -rw-r--r-- | lib/rcu.h | 55 | ||||
| -rw-r--r-- | lib/resource.c | 2 | ||||
| -rw-r--r-- | sysdep/unix/io-loop.c | 9 | ||||
| -rw-r--r-- | sysdep/unix/io-loop.h | 4 |
8 files changed, 154 insertions, 2 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"; diff --git a/sysdep/unix/io-loop.c b/sysdep/unix/io-loop.c index 3419d9d8..3e3fc31a 100644 --- a/sysdep/unix/io-loop.c +++ b/sysdep/unix/io-loop.c @@ -416,6 +416,7 @@ birdloop_free(struct birdloop *loop) ASSERT_DIE(loop->links == 0); ASSERT_DIE(pthread_equal(pthread_self(), loop->thread_id)); + rcu_birdloop_stop(&loop->rcu); pthread_attr_destroy(&loop->thread_attr); domain_free(loop->time.domain); @@ -505,6 +506,8 @@ birdloop_main(void *arg) timer *t; int rv, timeout; + rcu_birdloop_start(&loop->rcu); + btime loop_begin = current_time(); tmp_init(loop->pool); @@ -568,4 +571,8 @@ birdloop_main(void *arg) return NULL; } - +void +birdloop_yield(void) +{ + usleep(100); +} diff --git a/sysdep/unix/io-loop.h b/sysdep/unix/io-loop.h index ca4322fc..31c40459 100644 --- a/sysdep/unix/io-loop.h +++ b/sysdep/unix/io-loop.h @@ -7,6 +7,8 @@ #ifndef _BIRD_SYSDEP_UNIX_IO_LOOP_H_ #define _BIRD_SYSDEP_UNIX_IO_LOOP_H_ +#include "lib/rcu.h" + struct birdloop { pool *pool; @@ -28,6 +30,8 @@ struct birdloop pthread_t thread_id; pthread_attr_t thread_attr; + struct rcu_birdloop rcu; + uint links; void (*stopped)(void *data); |