summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Makefile2
-rw-r--r--lib/a-path.c41
-rw-r--r--lib/a-path_test.c6
-rw-r--r--lib/a-set.c48
-rw-r--r--lib/a-set_test.c1
-rw-r--r--lib/attrs.h7
-rw-r--r--lib/birdlib.h15
-rw-r--r--lib/event.c295
-rw-r--r--lib/event.h38
-rw-r--r--lib/event_test.c1
-rw-r--r--lib/io-loop.h66
-rw-r--r--lib/lists.c15
-rw-r--r--lib/lists.h12
-rw-r--r--lib/locking.h65
-rw-r--r--lib/rcu.c79
-rw-r--r--lib/rcu.h55
-rw-r--r--lib/resource.c8
-rw-r--r--lib/resource.h11
-rw-r--r--lib/route.h131
-rw-r--r--lib/settle.h64
-rw-r--r--lib/slab.c2
-rw-r--r--lib/socket.h3
-rw-r--r--lib/timer.c114
-rw-r--r--lib/timer.h40
24 files changed, 890 insertions, 229 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..d743ecdf 100644
--- a/lib/birdlib.h
+++ b/lib/birdlib.h
@@ -14,8 +14,9 @@
/* Ugly structure offset handling macros */
+#define SAME_TYPE(a, b) ({ int _ = ((a) != (b)); !_; })
#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))); SAME_TYPE(&_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 +87,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 +95,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 +176,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..68ee4c06 100644
--- a/lib/event.c
+++ b/lib/event.c
@@ -19,20 +19,152 @@
* 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)
+//#ifdef DEBUGGING
+#if 0
+#define EDL_MAX 16384
+enum edl_caller {
+ EDL_REMOVE_FROM = 1,
+ EDL_POSTPONE = 2,
+ EDL_RUN = 3,
+ EDL_SEND = 4,
+ EDL_RUN_LIST = 5,
+} caller;
+static struct event_debug_log {
+ event_list *target_list;
+ event *event;
+ event *receiver;
+ uint pos;
+ uint prev_edl_pos;
+ uint thread;
+ enum edl_caller caller;
+} edl[EDL_MAX];
+static _Atomic uint edl_cnt;
+_Thread_local static uint edl_thread;
+_Thread_local static uint prev_edl_pos = ~0;
+static inline void edlog(event_list *list, event *e, event *receiver, uint pos, enum edl_caller caller)
+{
+ uint edl_pos = atomic_fetch_add_explicit(&edl_cnt, 1, memory_order_acq_rel);
+ if (!edl_thread)
+ edl_thread = edl_pos;
+
+ edl[edl_pos % EDL_MAX] = (struct event_debug_log) {
+ .target_list = list,
+ .event = e,
+ .receiver = receiver,
+ .pos = pos,
+ .prev_edl_pos = prev_edl_pos,
+ .thread = edl_thread,
+ .caller = caller,
+ };
+
+ prev_edl_pos = edl_pos;
+}
+#else
+#define edlog(...)
+#endif
+
+
+void
+ev_init_list(event_list *el, struct birdloop *loop, const char *name)
{
- if (ev_active(e))
+ el->name = name;
+ el->loop = loop;
+
+ atomic_store_explicit(&el->receiver, NULL, memory_order_release);
+ atomic_store_explicit(&el->_executor, NULL, memory_order_release);
+}
+
+/*
+ * 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)
+{
+ /* 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);
+
+ /* This part of queue is empty! */
+ if (!cur)
+ return 0;
+
+ edlog(NULL, e, cur, 1, EDL_REMOVE_FROM);
+ while (cur)
+ {
+ /* Pre-loaded next pointer */
+ event *next = atomic_load_explicit(&cur->next, memory_order_acquire);
+
+ if (e == cur)
{
- rem_node(&e->n);
- e->n.next = NULL;
+ edlog(NULL, e, next, 3, EDL_REMOVE_FROM);
+
+ /* 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;
}
+
+ edlog(NULL, e, next, 2, EDL_REMOVE_FROM);
+
+ /* Go to the next event. */
+ prev = &cur->next;
+ cur = next;
+ }
+
+ edlog(NULL, e, cur, 4, EDL_REMOVE_FROM);
+
+ return 0;
+}
+
+inline void
+ev_postpone(event *e)
+{
+ /* Find the list to remove the event from */
+ event_list *sl = ev_get_list(e);
+ edlog(sl, e, NULL, 1, EDL_POSTPONE);
+ 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));
+
+ /* Mark as inactive */
+ ASSERT_DIE(sl == atomic_exchange_explicit(&e->list, NULL, memory_order_acq_rel));
+ edlog(sl, e, NULL, 2, EDL_POSTPONE);
}
static void
@@ -43,7 +175,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 = {
@@ -82,8 +214,10 @@ ev_new(pool *p)
inline void
ev_run(event *e)
{
+ edlog(NULL, e, NULL, 1, EDL_RUN);
ev_postpone(e);
e->hook(e->data);
+ edlog(NULL, e, NULL, 2, EDL_RUN);
}
/**
@@ -95,40 +229,39 @@ 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_send(event_list *l, event *e)
{
- ev_postpone(e);
- add_tail(l, &e->n);
-}
+ edlog(l, e, NULL, 1, EDL_SEND);
+ /* Set the target list */
+ event_list *ol = NULL;
+ if (!atomic_compare_exchange_strong_explicit(
+ &e->list, &ol, l,
+ memory_order_acq_rel, memory_order_acquire))
+ if (ol == l)
+ return;
+ else
+ bug("Queuing an already queued event to another queue is not supported.");
-/**
- * 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);
-}
+ /* Here should be no concurrent senders */
+ event *next = atomic_load_explicit(&l->receiver, memory_order_acquire);
+ edlog(l, e, next, 2, EDL_SEND);
+ event *old_next = NULL;
+ do
+ if (!atomic_compare_exchange_strong_explicit(
+ &e->next, &old_next, next,
+ memory_order_acq_rel, memory_order_acquire))
+ bug("Event %p in inconsistent state");
+ else
+ {
+ old_next = next;
+ edlog(l, old_next, next, 3, EDL_SEND);
+ }
+ while (!atomic_compare_exchange_strong_explicit(
+ &l->receiver, &next, e,
+ memory_order_acq_rel, memory_order_acquire));
-/**
- * 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)
-{
- if (!ev_active(e))
- add_tail(&global_work_list, &e->n);
+ edlog(l, e, next, 4, EDL_SEND);
+ birdloop_ping(l->loop);
}
void io_log_event(void *hook, void *data);
@@ -140,62 +273,66 @@ 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;
-
- 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);
+ event * _Atomic *ep = &l->_executor;
+ edlog(l, NULL, NULL, 1, EDL_RUN_LIST);
- /* 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_acquire))
+ {
+ /* Move the current event list aside and create a new one. */
+ event *received = atomic_exchange_explicit(&l->receiver, NULL, memory_order_acq_rel);
+ edlog(l, NULL, received, 2, EDL_RUN_LIST);
- ev_run(e);
- tmp_flush();
- }
+ /* No event to run. */
+ if (!received)
+ return 0;
- return !EMPTY_LIST(*l);
-}
+ /* Setup the executor queue */
+ event *head = NULL;
-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)
+ {
+ event *cur = received;
+ received = atomic_exchange_explicit(&cur->next, head, memory_order_acq_rel);
+ edlog(l, head, received, 3, EDL_RUN_LIST);
+ head = cur;
+ }
- init_list(&tmp_list);
- add_tail_list(&tmp_list, l);
- init_list(l);
+ /* Store the executor queue to its designated place */
+ ASSERT_DIE(atomic_exchange_explicit(ep, head, memory_order_acq_rel) == NULL);
+ edlog(l, NULL, head, 4, EDL_RUN_LIST);
+ }
- WALK_LIST_FIRST(n, tmp_list)
+ /* Run the events in order. */
+ event *e;
+ while (e = atomic_load_explicit(ep, memory_order_acquire))
{
- event *e = SKIP_BACK(event, n, n);
-
- if (!limit)
- break;
+ edlog(l, e, NULL, 5, EDL_RUN_LIST);
+ /* 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);
+ edlog(l, e, NULL, 6, EDL_RUN_LIST);
+ /* Inactivate the event */
+ event *next = atomic_load_explicit(&e->next, memory_order_relaxed);
+ ASSERT_DIE(e == atomic_exchange_explicit(ep, next, memory_order_acq_rel));
+ ASSERT_DIE(next == atomic_exchange_explicit(&e->next, NULL, memory_order_acq_rel));
+ ASSERT_DIE(l == atomic_exchange_explicit(&e->list, NULL, memory_order_acq_rel));
+ edlog(l, e, next, 7, EDL_RUN_LIST);
+
+ /* 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);
- }
+ edlog(l, e, next, 8, EDL_RUN_LIST);
+ }
- return !EMPTY_LIST(*l);
+ return !!atomic_load_explicit(&l->receiver, memory_order_acquire);
}
diff --git a/lib/event.h b/lib/event.h
index 5f3b78d8..0bef737a 100644
--- a/lib/event.h
+++ b/lib/event.h
@@ -10,33 +10,57 @@
#define _BIRD_EVENT_H_
#include "lib/resource.h"
+#include "lib/locking.h"
+#include "lib/rcu.h"
+
+#include <stdatomic.h>
+
+struct birdloop;
typedef struct event {
resource r;
void (*hook)(void *);
void *data;
- node n; /* Internal link */
+ struct event * _Atomic next;
+ struct event_list * _Atomic list;
} event;
-typedef list event_list;
+typedef struct event_list {
+ event * _Atomic receiver; /* Event receive list */
+ event * _Atomic _executor; /* Event execute list */
+ const char *name;
+ struct birdloop *loop; /* The executor loop */
+} 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->list, memory_order_acquire) != NULL;
+}
+
+static inline event_list *
+ev_get_list(event *e)
+{
+ return atomic_load_explicit(&e->list, memory_order_acquire);
}
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..ae58bbee
--- /dev/null
+++ b/lib/io-loop.h
@@ -0,0 +1,66 @@
+/*
+ * 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);
+
+struct birdloop_flag_handler {
+ void (*hook)(struct birdloop_flag_handler *, u32 flags);
+ void *data;
+};
+
+void birdloop_flag(struct birdloop *loop, u32 flag);
+void birdloop_flag_set_handler(struct birdloop *, struct birdloop_flag_handler *);
+
+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..498afdc8
--- /dev/null
+++ b/lib/locking.h
@@ -0,0 +1,65 @@
+/*
+ * 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 *service;
+ struct domain_generic *rtable;
+ struct domain_generic *attrs;
+ 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..2e367132 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);
@@ -284,6 +279,7 @@ rlookup(unsigned long a)
void
resource_init(void)
{
+ rcu_init();
resource_sys_init();
root_pool.r.class = &pool_class;
diff --git a/lib/resource.h b/lib/resource.h
index 4cedbf00..5d9e2165 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,9 +120,13 @@ 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;
+extern _Atomic int pages_kept;
+extern _Atomic int pages_kept_locally;
void *alloc_page(void);
void free_page(void *);
+void flush_local_pages(void);
void resource_sys_init(void);
diff --git a/lib/route.h b/lib/route.h
index 68596316..eae251e7 100644
--- a/lib/route.h
+++ b/lib/route.h
@@ -10,12 +10,17 @@
#ifndef _BIRD_LIB_ROUTE_H_
#define _BIRD_LIB_ROUTE_H_
+#undef RT_SOURCE_DEBUG
+
#include "lib/type.h"
+#include "lib/rcu.h"
+#include "lib/hash.h"
+#include "lib/event.h"
struct network;
struct proto;
struct cli;
-
+struct rtable_private;
typedef struct rte {
struct ea_list *attrs; /* Attributes of this route */
@@ -29,12 +34,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 */
@@ -45,19 +48,114 @@ static inline int rte_is_filtered(rte *r) { return !!(r->flags & REF_FILTERED);
struct rte_src {
struct rte_src *next; /* Hash chain */
- struct proto *proto; /* Protocol the source is based on */
+ struct rte_owner *owner; /* Route source owner */
u32 private_id; /* Private ID, assigned by the protocol */
u32 global_id; /* Globally unique ID of the source */
- unsigned uc; /* Use count */
+ _Atomic u64 uc; /* Use count */
+};
+
+struct rte_owner_class {
+ void (*get_route_info)(struct rte *, byte *buf); /* Get route information (for `show route' command) */
+ int (*rte_better)(struct rte *, struct rte *);
+ int (*rte_mergable)(struct rte *, struct rte *);
+ u32 (*rte_igp_metric)(const rte *);
};
+struct rte_owner {
+ struct rte_owner_class *class;
+ int (*rte_recalculate)(struct rtable_private *, struct network *, struct rte *, struct rte *, struct rte *);
+ HASH(struct rte_src) hash;
+ const char *name;
+ u32 hash_key;
+ u32 uc;
+ event_list *list;
+ event *prune;
+ event *stop;
+};
+
+DEFINE_DOMAIN(attrs);
+extern DOMAIN(attrs) attrs_domain;
+
+#define RTA_LOCK LOCK_DOMAIN(attrs, attrs_domain)
+#define RTA_UNLOCK UNLOCK_DOMAIN(attrs, attrs_domain)
+
+#define RTE_SRC_PU_SHIFT 44
+#define RTE_SRC_IN_PROGRESS (1ULL << RTE_SRC_PU_SHIFT)
+
+/* Get a route source. This also locks the source, therefore the caller has to
+ * unlock the source after the route has been propagated. */
+struct rte_src *rt_get_source_o(struct rte_owner *o, u32 id);
+#define rt_get_source(p, id) rt_get_source_o(&(p)->sources, (id))
-struct rte_src *rt_find_source(struct proto *p, u32 id);
-struct rte_src *rt_get_source(struct proto *p, u32 id);
struct rte_src *rt_find_source_global(u32 id);
-static inline void rt_lock_source(struct rte_src *src) { src->uc++; }
-static inline void rt_unlock_source(struct rte_src *src) { src->uc--; }
-void rt_prune_sources(void);
+
+#ifdef RT_SOURCE_DEBUG
+#define rt_lock_source _rt_lock_source_internal
+#define rt_unlock_source _rt_unlock_source_internal
+#endif
+
+static inline void rt_lock_source(struct rte_src *src)
+{
+ /* Locking a source is trivial; somebody already holds it so we just increase
+ * the use count. Nothing can be freed underneath our hands. */
+ u64 uc = atomic_fetch_add_explicit(&src->uc, 1, memory_order_acq_rel);
+ ASSERT_DIE(uc > 0);
+}
+
+static inline void rt_unlock_source(struct rte_src *src)
+{
+ /* Unlocking is tricky. We do it lockless so at the same time, the prune
+ * event may be running, therefore if the unlock gets us to zero, it must be
+ * the last thing in this routine, otherwise the prune routine may find the
+ * source's usecount zeroed, freeing it prematurely.
+ *
+ * The usecount is split into two parts:
+ * the top 20 bits are an in-progress indicator
+ * the bottom 44 bits keep the actual usecount.
+ *
+ * Therefore at most 1 million of writers can simultaneously unlock the same
+ * source, while at most ~17T different routes can reference it. Both limits
+ * are insanely high from the 2022 point of view. Let's suppose that when 17T
+ * routes or 1M writers get real, we get also 128bit atomic variables in the
+ * C norm. */
+
+ /* First, we push the in-progress indicator */
+ u64 uc = atomic_fetch_add_explicit(&src->uc, RTE_SRC_IN_PROGRESS, memory_order_acq_rel);
+
+ /* Then we split the indicator to its parts. Remember, we got the value before the operation happened. */
+ u64 pending = (uc >> RTE_SRC_PU_SHIFT) + 1;
+ uc &= RTE_SRC_IN_PROGRESS - 1;
+
+ /* We per-use the RCU critical section indicator to make the prune event wait
+ * until we finish here in the rare case we get preempted. */
+ rcu_read_lock();
+
+ /* Obviously, there can't be more pending unlocks than the usecount itself */
+ if (uc == pending)
+ /* If we're the last unlocker, schedule the owner's prune event */
+ ev_send(src->owner->list, src->owner->prune);
+ else
+ ASSERT_DIE(uc > pending);
+
+ /* And now, finally, simultaneously pop the in-progress indicator and the
+ * usecount, possibly allowing the source pruning routine to free this structure */
+ atomic_fetch_sub_explicit(&src->uc, RTE_SRC_IN_PROGRESS + 1, memory_order_acq_rel);
+
+ /* ... and to reduce the load a bit, the source pruning routine will better wait for
+ * RCU synchronization instead of a busy loop. */
+ rcu_read_unlock();
+}
+
+#ifdef RT_SOURCE_DEBUG
+#undef rt_lock_source
+#undef rt_unlock_source
+
+#define rt_lock_source(x) ( log(L_INFO "Lock source %uG at %s:%d", (x)->global_id, __FILE__, __LINE__), _rt_lock_source_internal(x) )
+#define rt_unlock_source(x) ( log(L_INFO "Unlock source %uG at %s:%d", (x)->global_id, __FILE__, __LINE__), _rt_unlock_source_internal(x) )
+#endif
+
+void rt_init_sources(struct rte_owner *, const char *name, event_list *list);
+void rt_destroy_sources(struct rte_owner *, event *);
/*
* Route Attributes
@@ -159,7 +257,7 @@ typedef struct ea_list {
struct ea_storage {
struct ea_storage *next_hash; /* Next in hash chain */
struct ea_storage **pprev_hash; /* Previous in hash chain */
- u32 uc; /* Use count */
+ _Atomic u32 uc; /* Use count */
u32 hash_key; /* List hash */
ea_list l[0]; /* The list itself */
};
@@ -425,15 +523,18 @@ 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; }
+static inline ea_list *ea_clone(ea_list *r) {
+ ASSERT_DIE(0 < atomic_fetch_add_explicit(&ea_get_storage(r)->uc, 1, memory_order_acq_rel));
+ return r;
+}
void ea__free(struct ea_storage *r);
static inline void ea_free(ea_list *l) {
if (!l) return;
struct ea_storage *r = ea_get_storage(l);
- if (!--r->uc) ea__free(r);
+ if (1 == atomic_fetch_sub_explicit(&r->uc, 1, memory_order_acq_rel)) ea__free(r);
}
void ea_dump(ea_list *);
diff --git a/lib/settle.h b/lib/settle.h
new file mode 100644
index 00000000..d274599d
--- /dev/null
+++ b/lib/settle.h
@@ -0,0 +1,64 @@
+/*
+ * BIRD -- Settle timer
+ *
+ * (c) 2022 Maria Matejka <mq@jmq.cz>
+ * (c) 2022 CZ.NIC z.s.p.o.
+ *
+ * Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#ifndef _BIRD_SETTLE_H_
+#define _BIRD_SETTLE_H_
+
+#include "lib/birdlib.h"
+#include "lib/timer.h"
+
+struct settle_config {
+ btime min, max;
+};
+
+struct settle {
+ union {
+ /* Timer hook polymorphism. */
+ struct {
+ resource _r;
+ void (*hook)(struct settle *);
+ };
+ timer tm;
+ };
+ struct settle_config cf;
+ btime started;
+};
+
+STATIC_ASSERT(OFFSETOF(struct settle, hook) == OFFSETOF(struct settle, tm) + OFFSETOF(timer, hook));
+
+#define SETTLE_INIT(_cfp, _hook, _data) (struct settle) { .tm = { .data = (_data), }, .hook = (_hook), .cf = ({ASSERT_DIE((_cfp)->min <= (_cfp)->max); *(_cfp); }), }
+
+
+static inline void settle_init(struct settle *s, struct settle_config *cf, void (*hook)(struct settle *), void *data)
+{
+ *s = SETTLE_INIT(cf, hook, data);
+}
+
+#define settle_active(s) tm_active(&(s)->tm)
+
+static inline void settle_kick(struct settle *s, struct birdloop *loop)
+{
+ if (!tm_active(&s->tm))
+ {
+ s->started = current_time();
+ tm_set_in(&s->tm, s->started + s->cf.min, loop);
+ }
+ else
+ {
+ btime now = current_time();
+ tm_set_in(&s->tm, MIN_(now + s->cf.min, s->started + s->cf.max), loop);
+ }
+}
+
+static inline void settle_cancel(struct settle *s)
+{
+ tm_stop(&s->tm);
+}
+
+#endif
diff --git a/lib/slab.c b/lib/slab.c
index 38d10626..054daea1 100644
--- a/lib/slab.c
+++ b/lib/slab.c
@@ -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(&current_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 {
generated by cgit v1.2.3 (git 2.39.1) at 2025-02-08 23:35:50 +0000