diff options
Diffstat (limited to 'lib')
-rw-r--r-- | lib/Makefile | 2 | ||||
-rw-r--r-- | lib/a-path.c | 41 | ||||
-rw-r--r-- | lib/a-path_test.c | 6 | ||||
-rw-r--r-- | lib/a-set.c | 48 | ||||
-rw-r--r-- | lib/a-set_test.c | 1 | ||||
-rw-r--r-- | lib/attrs.h | 7 | ||||
-rw-r--r-- | lib/birdlib.h | 14 | ||||
-rw-r--r-- | lib/event.c | 212 | ||||
-rw-r--r-- | lib/event.h | 50 | ||||
-rw-r--r-- | lib/event_test.c | 1 | ||||
-rw-r--r-- | lib/io-loop.h | 58 | ||||
-rw-r--r-- | lib/lists.c | 15 | ||||
-rw-r--r-- | lib/lists.h | 12 | ||||
-rw-r--r-- | lib/locking.h | 63 | ||||
-rw-r--r-- | lib/rcu.c | 79 | ||||
-rw-r--r-- | lib/rcu.h | 55 | ||||
-rw-r--r-- | lib/resource.c | 8 | ||||
-rw-r--r-- | lib/resource.h | 8 | ||||
-rw-r--r-- | lib/route.h | 6 | ||||
-rw-r--r-- | lib/slab.c | 2 | ||||
-rw-r--r-- | lib/socket.h | 3 | ||||
-rw-r--r-- | lib/timer.c | 114 | ||||
-rw-r--r-- | lib/timer.h | 40 |
23 files changed, 625 insertions, 220 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/a-path.c b/lib/a-path.c index 0eca8475..a7a22e40 100644 --- a/lib/a-path.c +++ b/lib/a-path.c @@ -602,8 +602,10 @@ as_path_match_set(const struct adata *path, const struct f_tree *set) } const struct adata * -as_path_filter(struct linpool *pool, const struct adata *path, const struct f_tree *set, u32 key, int pos) +as_path_filter(struct linpool *pool, const struct adata *path, const struct f_val *set, int pos) { + ASSERT((set->type == T_SET) || (set->type == T_INT)); + if (!path) return NULL; @@ -629,13 +631,13 @@ as_path_filter(struct linpool *pool, const struct adata *path, const struct f_tr u32 as = get_as(p); int match; - if (set) + if (set->type == T_SET) { struct f_val v = { .type = T_INT, .val.i = as}; - match = !!find_tree(set, &v); + match = !!find_tree(set->val.t, &v); } - else - match = (as == key); + else /* T_INT */ + match = (as == set->val.i); if (match == pos) { @@ -667,6 +669,35 @@ as_path_filter(struct linpool *pool, const struct adata *path, const struct f_tr return res; } +int +as_path_walk(const struct adata *path, uint *pos, uint *val) +{ + if (!path) + return 0; + + const u8 *p = path->data; + const u8 *q = p + path->length; + uint n, x = *pos; + + while (p < q) + { + n = p[1]; + p += 2; + + if (x < n) + { + *val = get_as(p + x * BS); + *pos += 1; + return 1; + } + + p += n * BS; + x -= n; + } + + return 0; +} + struct pm_pos { diff --git a/lib/a-path_test.c b/lib/a-path_test.c index 38f77642..c6f8ce8b 100644 --- a/lib/a-path_test.c +++ b/lib/a-path_test.c @@ -12,6 +12,7 @@ #include "nest/rt.h" #include "lib/attrs.h" #include "lib/resource.h" +#include "filter/data.h" #define TESTS_NUM 30 #define AS_PATH_LENGTH 1000 @@ -127,8 +128,9 @@ t_path_include(void) int counts_of_contains = count_asn_in_array(as_nums, as_nums[i]); bt_assert_msg(as_path_contains(as_path, as_nums[i], counts_of_contains), "AS Path should contains %d-times number %d", counts_of_contains, as_nums[i]); - bt_assert(as_path_filter(tmp_linpool, as_path, NULL, as_nums[i], 0) != NULL); - bt_assert(as_path_filter(tmp_linpool, as_path, NULL, as_nums[i], 1) != NULL); + struct f_val v = { .type = T_INT, .val.i = as_nums[i] }; + bt_assert(as_path_filter(tmp_linpool, as_path, &v, 0) != NULL); + bt_assert(as_path_filter(tmp_linpool, as_path, &v, 1) != NULL); } for (i = 0; i < 10000; i++) diff --git a/lib/a-set.c b/lib/a-set.c index 8ede9b83..dcb86058 100644 --- a/lib/a-set.c +++ b/lib/a-set.c @@ -693,3 +693,51 @@ lc_set_max(const struct adata *list, lcomm *val) *val = (lcomm) { res[0], res[1], res[2] }; return 1; } + +int +int_set_walk(const struct adata *list, uint *pos, uint *val) +{ + if (!list) + return 0; + + if (*pos >= (uint) int_set_get_size(list)) + return 0; + + u32 *res = int_set_get_data(list) + *pos; + *val = *res; + *pos += 1; + + return 1; +} + +int +ec_set_walk(const struct adata *list, uint *pos, u64 *val) +{ + if (!list) + return 0; + + if (*pos >= (uint) int_set_get_size(list)) + return 0; + + u32 *res = int_set_get_data(list) + *pos; + *val = ec_generic(res[0], res[1]); + *pos += 2; + + return 1; +} + +int +lc_set_walk(const struct adata *list, uint *pos, lcomm *val) +{ + if (!list) + return 0; + + if (*pos >= (uint) int_set_get_size(list)) + return 0; + + u32 *res = int_set_get_data(list) + *pos; + *val = (lcomm) { res[0], res[1], res[2] }; + *pos += 3; + + return 1; +} diff --git a/lib/a-set_test.c b/lib/a-set_test.c index 3280031f..693b8f08 100644 --- a/lib/a-set_test.c +++ b/lib/a-set_test.c @@ -221,6 +221,7 @@ t_set_ec_delete(void) return 1; } + int main(int argc, char *argv[]) { diff --git a/lib/attrs.h b/lib/attrs.h index a75abcd3..af2f1036 100644 --- a/lib/attrs.h +++ b/lib/attrs.h @@ -60,6 +60,7 @@ static inline int adata_same(const struct adata *a, const struct adata *b) * to 16bit slot (like in 16bit AS_PATH). See RFC 4893 for details */ +struct f_val; struct f_tree; int as_path_valid(byte *data, uint len, int bs, int sets, int confed, char *err, uint elen); @@ -81,7 +82,8 @@ int as_path_get_last(const struct adata *path, u32 *last_as); u32 as_path_get_last_nonaggregated(const struct adata *path); int as_path_contains(const struct adata *path, u32 as, int min); int as_path_match_set(const struct adata *path, const struct f_tree *set); -const struct adata *as_path_filter(struct linpool *pool, const struct adata *path, const struct f_tree *set, u32 key, int pos); +const struct adata *as_path_filter(struct linpool *pool, const struct adata *path, const struct f_val *set, int pos); +int as_path_walk(const struct adata *path, uint *pos, uint *val); static inline struct adata *as_path_prepend(struct linpool *pool, const struct adata *path, u32 as) { return as_path_prepend2(pool, path, AS_PATH_SEQUENCE, as); } @@ -256,6 +258,9 @@ int lc_set_min(const struct adata *list, lcomm *val); int int_set_max(const struct adata *list, u32 *val); int ec_set_max(const struct adata *list, u64 *val); int lc_set_max(const struct adata *list, lcomm *val); +int int_set_walk(const struct adata *list, uint *pos, u32 *val); +int ec_set_walk(const struct adata *list, uint *pos, u64 *val); +int lc_set_walk(const struct adata *list, uint *pos, lcomm *val); void ec_set_sort_x(struct adata *set); /* Sort in place */ diff --git a/lib/birdlib.h b/lib/birdlib.h index 9b6e4a16..d55b1a44 100644 --- a/lib/birdlib.h +++ b/lib/birdlib.h @@ -15,7 +15,7 @@ /* Ugly structure offset handling macros */ #define OFFSETOF(s, i) ((size_t) &((s *)0)->i) -#define SKIP_BACK(s, i, p) ((s *)((char *)p - OFFSETOF(s, i))) +#define SKIP_BACK(s, i, p) ({ s *_ptr = ((s *)((char *)p - OFFSETOF(s, i))); ASSERT_DIE(&_ptr->i == p); _ptr; }) #define BIRD_ALIGN(s, a) (((s)+a-1)&~(a-1)) #define CPU_STRUCT_ALIGN (MAX_(_Alignof(void*), _Alignof(u64))) #define BIRD_CPU_ALIGN(s) BIRD_ALIGN((s), CPU_STRUCT_ALIGN) @@ -86,6 +86,7 @@ static inline int u64_cmp(u64 i1, u64 i2) /* Macros for gcc attributes */ #define NORET __attribute__((noreturn)) +#define USE_RESULT __atribute__((warn_unused_result)) #define UNUSED __attribute__((unused)) #define PACKED __attribute__((packed)) #define NONNULL(...) __attribute__((nonnull((__VA_ARGS__)))) @@ -93,10 +94,6 @@ static inline int u64_cmp(u64 i1, u64 i2) #define STATIC_ASSERT(EXP) _Static_assert(EXP, #EXP) #define STATIC_ASSERT_MSG(EXP,MSG) _Static_assert(EXP, MSG) -#ifndef HAVE_THREAD_LOCAL -#define _Thread_local -#endif - /* Microsecond time */ typedef s64 btime; @@ -178,8 +175,13 @@ void debug(const char *msg, ...); /* Printf to debug output */ #if defined(LOCAL_DEBUG) || defined(GLOBAL_DEBUG) #define DBG(x, y...) debug(x, ##y) +#define DBGL(x, y...) debug(x "\n", ##y) +#elif defined(DEBUG_TO_LOG) +#define DBG(...) do { } while (0) +#define DBGL(...) log(L_DEBUG __VA_ARGS__) #else -#define DBG(x, y...) do { } while(0) +#define DBG(...) do { } while(0) +#define DBGL(...) do { } while (0) #endif #define ASSERT_DIE(x) do { if (!(x)) bug("Assertion '%s' failed at %s:%d", #x, __FILE__, __LINE__); } while(0) diff --git a/lib/event.c b/lib/event.c index 33dc00b0..07d7dc53 100644 --- a/lib/event.c +++ b/lib/event.c @@ -19,20 +19,95 @@ * events in them and explicitly ask to run them. */ +#undef LOCAL_DEBUG + #include "nest/bird.h" #include "lib/event.h" +#include "lib/io-loop.h" event_list global_event_list; event_list global_work_list; -inline void -ev_postpone(event *e) +STATIC_ASSERT(OFFSETOF(event_list, _sentinel.next) >= OFFSETOF(event_list, _end[0])); + +void +ev_init_list(event_list *el, struct birdloop *loop, const char *name) +{ + el->name = name; + el->loop = loop; + + atomic_store_explicit(&el->receiver, &el->_sentinel, memory_order_relaxed); + atomic_store_explicit(&el->_executor, &el->_sentinel, memory_order_relaxed); + atomic_store_explicit(&el->_sentinel.next, NULL, memory_order_relaxed); +} + +/* + * The event list should work as a message passing point. Sending a message + * must be a fairly fast process with no locks and low waiting times. OTOH, + * processing messages always involves running the assigned code and the + * receiver is always a single one thread with no concurrency at all. There is + * also a postponing requirement to synchronously remove an event from a queue, + * yet we allow this only when the caller has its receiver event loop locked. + * It still means that the event may get postponed from other event in the same + * list, therefore we have to be careful. + */ + +static inline int +ev_remove_from(event *e, event * _Atomic * head) { - if (ev_active(e)) + /* The head pointer stores where cur is pointed to from */ + event * _Atomic *prev = head; + + /* The current event in queue to check */ + event *cur = atomic_load_explicit(prev, memory_order_acquire); + + /* Pre-loaded next pointer; if NULL, this is sentinel */ + event *next = atomic_load_explicit(&cur->next, memory_order_acquire); + + while (next) + { + if (e == cur) { - rem_node(&e->n); - e->n.next = NULL; + /* Check whether we have collided with somebody else + * adding an item to the queue. */ + if (!atomic_compare_exchange_strong_explicit( + prev, &cur, next, + memory_order_acq_rel, memory_order_acquire)) + { + /* This may happen only on list head */ + ASSERT_DIE(prev == head); + + /* Restart. The collision should never happen again. */ + return ev_remove_from(e, head); + } + + /* Successfully removed from the list; inactivate this event. */ + atomic_store_explicit(&cur->next, NULL, memory_order_release); + return 1; } + + /* Go to the next event. */ + prev = &cur->next; + cur = next; + next = atomic_load_explicit(&cur->next, memory_order_acquire); + } + + return 0; +} + +inline void +ev_postpone(event *e) +{ + /* Find the list to remove the event from */ + event_list *sl = ev_get_list(e); + if (!sl) + return; + + /* Postponing allowed only from the target loop */ + ASSERT_DIE(birdloop_inside(sl->loop)); + + /* Remove from one of these lists. */ + ASSERT(ev_remove_from(e, &sl->_executor) || ev_remove_from(e, &sl->receiver)); } static void @@ -43,7 +118,7 @@ ev_dump(resource *r) debug("(code %p, data %p, %s)\n", e->hook, e->data, - e->n.next ? "scheduled" : "inactive"); + atomic_load_explicit(&e->next, memory_order_relaxed) ? "scheduled" : "inactive"); } static struct resclass ev_class = { @@ -95,40 +170,21 @@ ev_run(event *e) * list @l which can be run by calling ev_run_list(). */ inline void -ev_enqueue(event_list *l, event *e) -{ - ev_postpone(e); - add_tail(l, &e->n); -} - -/** - * ev_schedule - schedule an event - * @e: an event - * - * This function schedules an event by enqueueing it to a system-wide - * event list which is run by the platform dependent code whenever - * appropriate. - */ -void -ev_schedule(event *e) -{ - ev_enqueue(&global_event_list, e); -} - -/** - * ev_schedule_work - schedule a work-event. - * @e: an event - * - * This function schedules an event by enqueueing it to a system-wide work-event - * list which is run by the platform dependent code whenever appropriate. This - * is designated for work-events instead of regular events. They are executed - * less often in order to not clog I/O loop. - */ -void -ev_schedule_work(event *e) +ev_send(event_list *l, event *e) { - if (!ev_active(e)) - add_tail(&global_work_list, &e->n); + event_list *sl = ev_get_list(e); + if (sl == l) + return; + if (sl) + bug("Queuing an already queued event to another queue is not supported."); + + event *next = atomic_load_explicit(&l->receiver, memory_order_acquire); + do atomic_store_explicit(&e->next, next, memory_order_relaxed); + while (!atomic_compare_exchange_strong_explicit( + &l->receiver, &next, e, + memory_order_acq_rel, memory_order_acquire)); + + birdloop_ping(l->loop); } void io_log_event(void *hook, void *data); @@ -140,62 +196,56 @@ void io_log_event(void *hook, void *data); * This function calls ev_run() for all events enqueued in the list @l. */ int -ev_run_list(event_list *l) +ev_run_list_limited(event_list *l, uint limit) { - node *n; - list tmp_list; + event * _Atomic *ep = &l->_executor; - init_list(&tmp_list); - add_tail_list(&tmp_list, l); - init_list(l); - WALK_LIST_FIRST(n, tmp_list) - { - event *e = SKIP_BACK(event, n, n); - - /* This is ugly hack, we want to log just events executed from the main I/O loop */ - if ((l == &global_event_list) || (l == &global_work_list)) - io_log_event(e->hook, e->data); + /* No pending events, refill the queue. */ + if (atomic_load_explicit(ep, memory_order_relaxed) == &l->_sentinel) + { + /* Move the current event list aside and create a new one. */ + event *received = atomic_exchange_explicit( + &l->receiver, &l->_sentinel, memory_order_acq_rel); - ev_run(e); - tmp_flush(); - } + /* No event to run. */ + if (received == &l->_sentinel) + return 0; - return !EMPTY_LIST(*l); -} + /* Setup the executor queue */ + event *head = &l->_sentinel; -int -ev_run_list_limited(event_list *l, uint limit) -{ - node *n; - list tmp_list; + /* Flip the order of the events by relinking them one by one (push-pop) */ + while (received != &l->_sentinel) + { + event *cur = received; + received = atomic_exchange_explicit(&cur->next, head, memory_order_relaxed); + head = cur; + } - init_list(&tmp_list); - add_tail_list(&tmp_list, l); - init_list(l); + /* Store the executor queue to its designated place */ + atomic_store_explicit(ep, head, memory_order_relaxed); + } - WALK_LIST_FIRST(n, tmp_list) + /* Run the events in order. */ + event *e; + while ((e = atomic_load_explicit(ep, memory_order_relaxed)) != &l->_sentinel) { - event *e = SKIP_BACK(event, n, n); - - if (!limit) - break; + /* Check limit */ + if (!--limit) + return 1; /* This is ugly hack, we want to log just events executed from the main I/O loop */ if ((l == &global_event_list) || (l == &global_work_list)) io_log_event(e->hook, e->data); - ev_run(e); + /* Inactivate the event */ + atomic_store_explicit(ep, atomic_load_explicit(&e->next, memory_order_relaxed), memory_order_relaxed); + atomic_store_explicit(&e->next, NULL, memory_order_relaxed); + + /* Run the event */ + e->hook(e->data); tmp_flush(); - limit--; } - if (!EMPTY_LIST(tmp_list)) - { - /* Attach new items after the unprocessed old items */ - add_tail_list(&tmp_list, l); - init_list(l); - add_tail_list(l, &tmp_list); - } - - return !EMPTY_LIST(*l); + return atomic_load_explicit(&l->receiver, memory_order_relaxed) != &l->_sentinel; } diff --git a/lib/event.h b/lib/event.h index 5f3b78d8..9773c3a9 100644 --- a/lib/event.h +++ b/lib/event.h @@ -10,33 +10,69 @@ #define _BIRD_EVENT_H_ #include "lib/resource.h" +#include "lib/locking.h" + +#include <stdatomic.h> + +struct birdloop; typedef struct event { resource r; void (*hook)(void *); void *data; - node n; /* Internal link */ + struct event * _Atomic next; } event; -typedef list event_list; +typedef union event_list { + struct { + event * _Atomic receiver; /* Event receive list */ + event * _Atomic _executor; /* Event execute list */ + const char *name; + struct birdloop *loop; /* The executor loop */ + char _end[0]; + }; + event _sentinel; /* Sentinel node to actively detect list end */ +} event_list; extern event_list global_event_list; extern event_list global_work_list; event *ev_new(pool *); void ev_run(event *); -#define ev_init_list(el) init_list(el) +void ev_init_list(event_list *, struct birdloop *loop, const char *name); void ev_enqueue(event_list *, event *); -void ev_schedule(event *); -void ev_schedule_work(event *); +#define ev_send ev_enqueue +#define ev_send_loop(l, e) ev_send(birdloop_event_list((l)), (e)) + +#define ev_schedule(e) ({ ASSERT_THE_BIRD_LOCKED; if (!ev_active((e))) ev_send(&global_event_list, (e)); }) +#define ev_schedule_work(e) ({ ASSERT_THE_BIRD_LOCKED; if (!ev_active((e))) ev_send(&global_work_list, (e)); }) + void ev_postpone(event *); -int ev_run_list(event_list *); int ev_run_list_limited(event_list *, uint); +#define ev_run_list(l) ev_run_list_limited((l), ~0) + +#define LEGACY_EVENT_LIST(l) (((l) == &global_event_list) || ((l) == &global_work_list)) static inline int ev_active(event *e) { - return e->n.next != NULL; + return atomic_load_explicit(&e->next, memory_order_relaxed) != NULL; +} + +static inline event_list * +ev_get_list(event *e) +{ + /* We are looking for the sentinel node at the list end. + * After this, we have s->next == NULL */ + event *s = e; + for (event *sn; sn = atomic_load_explicit(&s->next, memory_order_acquire); s = sn) + ; + + /* No sentinel, no list. */ + if (s == e) + return NULL; + else + return SKIP_BACK(event_list, _sentinel, s); } static inline event* diff --git a/lib/event_test.c b/lib/event_test.c index 3070327d..612deb25 100644 --- a/lib/event_test.c +++ b/lib/event_test.c @@ -54,7 +54,6 @@ t_ev_run_list(void) int i; olock_init(); - timer_init(); rt_init(); io_init(); if_init(); diff --git a/lib/io-loop.h b/lib/io-loop.h new file mode 100644 index 00000000..2450a609 --- /dev/null +++ b/lib/io-loop.h @@ -0,0 +1,58 @@ +/* + * BIRD -- I/O and event loop + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_IO_LOOP_H_ +#define _BIRD_IO_LOOP_H_ + +#include "nest/bird.h" +#include "lib/lists.h" +#include "lib/locking.h" +#include "lib/resource.h" +#include "lib/event.h" +#include "lib/socket.h" + +extern struct birdloop main_birdloop; + +void sk_start(sock *s); +void sk_stop(sock *s); +void sk_reloop(sock *s, struct birdloop *loop); + +/* Start a new birdloop owned by given pool and domain */ +struct birdloop *birdloop_new(pool *p, uint order, const char *name); + +/* Stop the loop. At the end, the @stopped callback is called unlocked in tail + * position to finish cleanup. Run birdloop_free() from that callback to free + * the loop itself. */ +void birdloop_stop(struct birdloop *loop, void (*stopped)(void *data), void *data); +void birdloop_stop_self(struct birdloop *loop, void (*stopped)(void *data), void *data); +void birdloop_free(struct birdloop *loop); + +/* Get birdloop's event list */ +event_list *birdloop_event_list(struct birdloop *loop); + +/* Get birdloop's time heap */ +struct timeloop *birdloop_time_loop(struct birdloop *loop); + +/* Enter and exit the birdloop */ +void birdloop_enter(struct birdloop *loop); +void birdloop_leave(struct birdloop *loop); + +_Bool birdloop_inside(struct birdloop *loop); + +void birdloop_mask_wakeups(struct birdloop *loop); +void birdloop_unmask_wakeups(struct birdloop *loop); + +void birdloop_link(struct birdloop *loop); +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/lists.c b/lib/lists.c index 200576cf..8f95c7c2 100644 --- a/lib/lists.c +++ b/lib/lists.c @@ -26,7 +26,7 @@ #define _BIRD_LISTS_C_ -#include "nest/bird.h" +#include "lib/birdlib.h" #include "lib/lists.h" LIST_INLINE int @@ -35,11 +35,12 @@ check_list(list *l, node *n) if (!l) { ASSERT_DIE(n); - ASSERT_DIE(n->prev); - do { n = n->prev; } while (n->prev); + node *nn = n; + while (nn->prev) + nn = nn->prev; - l = SKIP_BACK(list, head_node, n); + l = SKIP_BACK(list, head_node, nn); } int seen = 0; @@ -60,7 +61,7 @@ check_list(list *l, node *n) } ASSERT_DIE(cur == &(l->tail_node)); - ASSERT_DIE(!n || (seen == 1)); + ASSERT_DIE(!n || (seen == 1) || (n == &l->head_node) || (n == &l->tail_node)); return 1; } @@ -120,7 +121,7 @@ add_head(list *l, node *n) LIST_INLINE void insert_node(node *n, node *after) { - EXPENSIVE_CHECK(check_list(l, after)); + EXPENSIVE_CHECK(check_list(NULL, after)); ASSUME(n->prev == NULL); ASSUME(n->next == NULL); @@ -141,7 +142,7 @@ insert_node(node *n, node *after) LIST_INLINE void rem_node(node *n) { - EXPENSIVE_CHECK(check_list(NULL, n)); + EXPENSIVE_CHECK((n == n->prev) && (n == n->next) || check_list(NULL, n)); node *z = n->prev; node *x = n->next; diff --git a/lib/lists.h b/lib/lists.h index 7e6d5467..86ff59c9 100644 --- a/lib/lists.h +++ b/lib/lists.h @@ -69,6 +69,18 @@ typedef union list { /* In fact two overlayed nodes */ #define EMPTY_LIST(list) (!(list).head->next) +static inline _Bool +enlisted(node *n) +{ + switch ((!!n->next) + (!!n->prev)) + { + case 0: return 0; + case 2: return 1; + case 1: bug("Garbled event list node"); + } + + bug("Maths is broken. And you should see a new heaven and a new earth: for the first heaven and the first earth had been passed away."); +} #ifndef _BIRD_LISTS_C_ #define LIST_INLINE static inline diff --git a/lib/locking.h b/lib/locking.h new file mode 100644 index 00000000..a9a8aa9b --- /dev/null +++ b/lib/locking.h @@ -0,0 +1,63 @@ +/* + * BIRD Library -- Locking + * + * (c) 2020--2021 Maria Matejka <mq@jmq.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_LOCKING_H_ +#define _BIRD_LOCKING_H_ + +struct domain_generic; + +/* Here define the global lock order; first to last. */ +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; +extern _Thread_local struct domain_generic **last_locked; + +#define DOMAIN(type) struct domain__##type +#define DEFINE_DOMAIN(type) DOMAIN(type) { struct domain_generic *type; } +#define DOMAIN_ORDER(type) OFFSETOF(struct lock_order, type) + +#define DOMAIN_NEW(type, name) (DOMAIN(type)) { .type = domain_new(name, DOMAIN_ORDER(type)) } +struct domain_generic *domain_new(const char *name, uint order); + +#define DOMAIN_FREE(type, d) domain_free((d).type) +void domain_free(struct domain_generic *); + +#define DOMAIN_NULL(type) (DOMAIN(type)) {} + +#define LOCK_DOMAIN(type, d) do_lock(((d).type), &(locking_stack.type)) +#define UNLOCK_DOMAIN(type, d) do_unlock(((d).type), &(locking_stack.type)) + +#define DOMAIN_IS_LOCKED(type, d) (((d).type) == (locking_stack.type)) +#define DG_IS_LOCKED(d) ((d) == *(DG_LSP(d))) + +/* Internal for locking */ +void do_lock(struct domain_generic *dg, struct domain_generic **lsp); +void do_unlock(struct domain_generic *dg, struct domain_generic **lsp); + +uint dg_order(struct domain_generic *dg); + +#define DG_LSP(d) ((struct domain_generic **) (((void *) &locking_stack) + dg_order(d))) +#define DG_LOCK(d) do_lock(d, DG_LSP(d)) +#define DG_UNLOCK(d) do_unlock(d, DG_LSP(d)) + +/* Use with care. To be removed in near future. */ +DEFINE_DOMAIN(the_bird); +extern DOMAIN(the_bird) the_bird_domain; + +#define the_bird_lock() LOCK_DOMAIN(the_bird, the_bird_domain) +#define the_bird_unlock() UNLOCK_DOMAIN(the_bird, the_bird_domain) +#define the_bird_locked() DOMAIN_IS_LOCKED(the_bird, the_bird_domain) + +#define ASSERT_THE_BIRD_LOCKED ({ if (!the_bird_locked()) bug("The BIRD lock must be locked here: %s:%d", __FILE__, __LINE__); }) + +#endif 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 c31d9889..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 @@ -29,12 +30,6 @@ * is freed upon shutdown of the module. */ -struct pool { - resource r; - list inside; - const char *name; -}; - static void pool_dump(resource *); static void pool_free(resource *); static resource *pool_lookup(resource *, unsigned long); @@ -285,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/lib/resource.h b/lib/resource.h index 4cedbf00..5ad011ec 100644 --- a/lib/resource.h +++ b/lib/resource.h @@ -40,7 +40,12 @@ struct resclass { /* Generic resource manipulation */ -typedef struct pool pool; +typedef struct pool { + resource r; + list inside; + const char *name; +} pool; + void resource_init(void); pool *rp_new(pool *, const char *); /* Create new pool */ @@ -115,6 +120,7 @@ void sl_free(void *); void buffer_realloc(void **buf, unsigned *size, unsigned need, unsigned item_size); /* Allocator of whole pages; for use in slabs and other high-level allocators. */ +#define PAGE_HEAD(x) ((void *) (((uintptr_t) (x)) & ~(page_size-1))) extern long page_size; void *alloc_page(void); void free_page(void *); diff --git a/lib/route.h b/lib/route.h index 68596316..2d691215 100644 --- a/lib/route.h +++ b/lib/route.h @@ -29,12 +29,10 @@ typedef struct rte { u8 generation; /* If this route import is based on other previously exported route, this value should be 1 + MAX(generation of the parent routes). Otherwise the route is independent and this value is zero. */ + u8 stale_cycle; /* Auxiliary value for route refresh */ } rte; #define REF_FILTERED 2 /* Route is rejected by import filter */ -#define REF_STALE 4 /* Route is stale in a refresh cycle */ -#define REF_DISCARD 8 /* Route is scheduled for discard */ -#define REF_MODIFY 16 /* Route is scheduled for modify */ #define REF_PENDING 32 /* Route has not propagated completely yet */ /* Route is valid for propagation (may depend on other flags in the future), accepts NULL */ @@ -425,7 +423,7 @@ static inline int ea_is_cached(const ea_list *r) { return r->flags & EALF_CACHED static inline struct ea_storage *ea_get_storage(ea_list *r) { ASSERT_DIE(ea_is_cached(r)); - return SKIP_BACK(struct ea_storage, l, r); + return SKIP_BACK(struct ea_storage, l[0], r); } static inline ea_list *ea_clone(ea_list *r) { ea_get_storage(r)->uc++; return r; } @@ -197,7 +197,7 @@ static struct resclass sl_class = { slab_memsize }; -#define SL_GET_HEAD(x) ((struct sl_head *) (((uintptr_t) (x)) & ~(page_size-1))) +#define SL_GET_HEAD(x) PAGE_HEAD(x) #define SL_HEAD_CHANGE_STATE(_s, _h, _from, _to) ({ \ ASSERT_DIE(_h->state == slh_##_from); \ diff --git a/lib/socket.h b/lib/socket.h index 0b6ac589..5c69482e 100644 --- a/lib/socket.h +++ b/lib/socket.h @@ -12,6 +12,7 @@ #include <errno.h> #include "lib/resource.h" +#include "lib/event.h" #ifdef HAVE_LIBSSH #define LIBSSH_LEGACY_0_4 #include <libssh/libssh.h> @@ -79,6 +80,7 @@ typedef struct birdsock { const char *password; /* Password for MD5 authentication */ const char *err; /* Error message */ struct ssh_sock *ssh; /* Used in SK_SSH */ + struct event reloop; /* Reloop event */ } sock; sock *sock_new(pool *); /* Allocate new socket */ @@ -129,6 +131,7 @@ extern int sk_priority_control; /* Suggested priority for control traffic, shou #define SKF_TRUNCATED 0x200 /* Received packet was truncated, set by IO layer */ #define SKF_HDRINCL 0x400 /* Used internally */ #define SKF_PKTINFO 0x800 /* Used internally */ +#define SKF_PASSIVE_THREAD 0x1000 /* Child sockets used in thread, do not add to main loop */ /* * Socket types SA SP DA DP IF TTL SendTo (?=may, -=must not, *=must) diff --git a/lib/timer.c b/lib/timer.c index c47e0bbc..ff6975a4 100644 --- a/lib/timer.c +++ b/lib/timer.c @@ -36,57 +36,13 @@ #include "lib/resource.h" #include "lib/timer.h" - -struct timeloop main_timeloop; - - -#ifdef USE_PTHREADS - #include <pthread.h> -/* Data accessed and modified from proto/bfd/io.c */ -pthread_key_t current_time_key; - -static inline struct timeloop * -timeloop_current(void) -{ - return pthread_getspecific(current_time_key); -} - -static inline void -timeloop_init_current(void) -{ - pthread_key_create(¤t_time_key, NULL); - pthread_setspecific(current_time_key, &main_timeloop); -} +_Atomic btime last_time; +_Atomic btime real_time; void wakeup_kick_current(void); -#else - -/* Just use main timelooop */ -static inline struct timeloop * timeloop_current(void) { return &main_timeloop; } -static inline void timeloop_init_current(void) { } - -#endif - -btime -current_time(void) -{ - return timeloop_current()->last_time; -} - -btime -current_real_time(void) -{ - struct timeloop *loop = timeloop_current(); - - if (!loop->real_time) - times_update_real_time(loop); - - return loop->real_time; -} - #define TIMER_LESS(a,b) ((a)->expires < (b)->expires) #define TIMER_SWAP(heap,a,b,t) (t = heap[a], heap[a] = heap[b], heap[b] = t, \ @@ -112,7 +68,7 @@ tm_dump(resource *r) if (t->recurrent) debug("recur %d, ", t->recurrent); if (t->expires) - debug("expires in %d ms)\n", (t->expires - current_time()) TO_MS); + debug("in loop %p expires in %d ms)\n", t->loop, (t->expires - current_time()) TO_MS); else debug("inactive)\n"); } @@ -135,41 +91,40 @@ tm_new(pool *p) return t; } -void -tm_set(timer *t, btime when) +static void +tm_set_in_tl(timer *t, btime when, struct timeloop *local_timeloop) { - struct timeloop *loop = timeloop_current(); - uint tc = timers_count(loop); + uint tc = timers_count(local_timeloop); if (!t->expires) { t->index = ++tc; t->expires = when; - BUFFER_PUSH(loop->timers) = t; - HEAP_INSERT(loop->timers.data, tc, timer *, TIMER_LESS, TIMER_SWAP); + BUFFER_PUSH(local_timeloop->timers) = t; + HEAP_INSERT(local_timeloop->timers.data, tc, timer *, TIMER_LESS, TIMER_SWAP); } else if (t->expires < when) { t->expires = when; - HEAP_INCREASE(loop->timers.data, tc, timer *, TIMER_LESS, TIMER_SWAP, t->index); + HEAP_INCREASE(local_timeloop->timers.data, tc, timer *, TIMER_LESS, TIMER_SWAP, t->index); } else if (t->expires > when) { t->expires = when; - HEAP_DECREASE(loop->timers.data, tc, timer *, TIMER_LESS, TIMER_SWAP, t->index); + HEAP_DECREASE(local_timeloop->timers.data, tc, timer *, TIMER_LESS, TIMER_SWAP, t->index); } -#ifdef CONFIG_BFD - /* Hack to notify BFD loops */ - if ((loop != &main_timeloop) && (t->index == 1)) - wakeup_kick_current(); -#endif + t->loop = local_timeloop; + + if (t->index == 1) + birdloop_ping(local_timeloop->loop); } void -tm_start(timer *t, btime after) +tm_set_in(timer *t, btime when, struct birdloop *loop) { - tm_set(t, current_time() + MAX(after, 0)); + ASSERT_DIE(birdloop_inside(loop)); + tm_set_in_tl(t, when, birdloop_time_loop(loop)); } void @@ -178,20 +133,22 @@ tm_stop(timer *t) if (!t->expires) return; - struct timeloop *loop = timeloop_current(); - uint tc = timers_count(loop); + TLOCK_TIMER_ASSERT(t->loop); - HEAP_DELETE(loop->timers.data, tc, timer *, TIMER_LESS, TIMER_SWAP, t->index); - BUFFER_POP(loop->timers); + uint tc = timers_count(t->loop); + + HEAP_DELETE(t->loop->timers.data, tc, timer *, TIMER_LESS, TIMER_SWAP, t->index); + BUFFER_POP(t->loop->timers); t->index = -1; t->expires = 0; + t->loop = NULL; } void timers_init(struct timeloop *loop, pool *p) { - times_init(loop); + TLOCK_TIMER_ASSERT(loop); BUFFER_INIT(loop->timers, p, 4); BUFFER_PUSH(loop->timers) = NULL; @@ -200,13 +157,15 @@ timers_init(struct timeloop *loop, pool *p) void io_log_event(void *hook, void *data); void -timers_fire(struct timeloop *loop) +timers_fire(struct timeloop *loop, int io_log) { + TLOCK_TIMER_ASSERT(loop); + btime base_time; timer *t; - times_update(loop); - base_time = loop->last_time; + times_update(); + base_time = current_time(); while (t = timers_first(loop)) { @@ -217,19 +176,19 @@ timers_fire(struct timeloop *loop) { btime when = t->expires + t->recurrent; - if (when <= loop->last_time) - when = loop->last_time + t->recurrent; + if (when <= base_time) + when = base_time + t->recurrent; if (t->randomize) when += random() % (t->randomize + 1); - tm_set(t, when); + tm_set_in_tl(t, when, loop); } else tm_stop(t); /* This is ugly hack, we want to log just timers executed from the main I/O loop */ - if (loop == &main_timeloop) + if (io_log) io_log_event(t->hook, t->data); t->hook(t); @@ -237,13 +196,6 @@ timers_fire(struct timeloop *loop) } } -void -timer_init(void) -{ - timers_init(&main_timeloop, &root_pool); - timeloop_init_current(); -} - /** * tm_parse_time - parse a date and time diff --git a/lib/timer.h b/lib/timer.h index c5ea430c..555fc96f 100644 --- a/lib/timer.h +++ b/lib/timer.h @@ -12,8 +12,14 @@ #include "nest/bird.h" #include "lib/buffer.h" +#include "lib/io-loop.h" +#include "lib/locking.h" #include "lib/resource.h" +#include <stdatomic.h> + +extern _Atomic btime last_time; +extern _Atomic btime real_time; typedef struct timer { @@ -25,36 +31,42 @@ typedef struct timer uint randomize; /* Amount of randomization */ uint recurrent; /* Timer recurrence */ + struct timeloop *loop; /* Loop where the timer is active */ + int index; } timer; struct timeloop { BUFFER_(timer *) timers; - btime last_time; - btime real_time; + struct domain_generic *domain; + struct birdloop *loop; }; +#define TLOCK_TIMER_ASSERT(loop) ASSERT_DIE((loop)->domain && DG_IS_LOCKED((loop)->domain)) +#define TLOCK_LOCAL_ASSERT(loop) ASSERT_DIE(!(loop)->domain || DG_IS_LOCKED((loop)->domain)) + static inline uint timers_count(struct timeloop *loop) -{ return loop->timers.used - 1; } +{ TLOCK_TIMER_ASSERT(loop); return loop->timers.used - 1; } static inline timer *timers_first(struct timeloop *loop) -{ return (loop->timers.used > 1) ? loop->timers.data[1] : NULL; } +{ TLOCK_TIMER_ASSERT(loop); return (loop->timers.used > 1) ? loop->timers.data[1] : NULL; } -extern struct timeloop main_timeloop; - -btime current_time(void); -btime current_real_time(void); +#define current_time() atomic_load_explicit(&last_time, memory_order_acquire) +#define current_real_time() atomic_load_explicit(&real_time, memory_order_acquire) //#define now (current_time() TO_S) //#define now_real (current_real_time() TO_S) extern btime boot_time; timer *tm_new(pool *p); -void tm_set(timer *t, btime when); -void tm_start(timer *t, btime after); +#define tm_set(t, when) tm_set_in((t), (when), &main_birdloop) +#define tm_start(t, after) tm_start_in((t), (after), &main_birdloop) void tm_stop(timer *t); +void tm_set_in(timer *t, btime when, struct birdloop *loop); +#define tm_start_in(t, after, loop) tm_set_in((t), (current_time() + MAX_((after), 0)), loop) + static inline int tm_active(timer *t) { @@ -94,15 +106,11 @@ tm_start_max(timer *t, btime after) } /* In sysdep code */ -void times_init(struct timeloop *loop); -void times_update(struct timeloop *loop); -void times_update_real_time(struct timeloop *loop); +void times_update(void); /* For I/O loop */ void timers_init(struct timeloop *loop, pool *p); -void timers_fire(struct timeloop *loop); - -void timer_init(void); +void timers_fire(struct timeloop *loop, int io_log); struct timeformat { |