From e91754f5b9ef68d52f5ff3abcd24661034a0feed Mon Sep 17 00:00:00 2001
From: Maria Matejka <mq@ucw.cz>
Date: Fri, 24 Jun 2022 19:53:34 +0200
Subject: Event lists rewritten to a single linked list

In multithreaded environment, we need to pass messages between workers.
This is done by queuing events to their respective queues. The
double-linked list is not really useful for that as it needs locking
everywhere.

This commit rewrites the event subsystem to use a single-linked list
where events are enqueued by a single atomic instruction and the queue
is processed after atomically moving the whole queue aside.
---
 lib/event.h | 55 +++++++++++++++++++++++++++++++------------------------
 1 file changed, 31 insertions(+), 24 deletions(-)

(limited to 'lib/event.h')

diff --git a/lib/event.h b/lib/event.h
index 6c358f84..9773c3a9 100644
--- a/lib/event.h
+++ b/lib/event.h
@@ -14,21 +14,24 @@
 
 #include <stdatomic.h>
 
-DEFINE_DOMAIN(event);
+struct birdloop;
 
 typedef struct event {
   resource r;
   void (*hook)(void *);
   void *data;
-  node n;				/* Internal link */
-  struct event_list *list;		/* List where this event is put in */
+  struct event * _Atomic next;
 } event;
 
-typedef struct event_list {
-  list events;
-  pool *pool;
-  struct birdloop *loop;
-  DOMAIN(event) lock;
+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;
@@ -36,36 +39,40 @@ extern event_list global_work_list;
 
 event *ev_new(pool *);
 void ev_run(event *);
-
-static inline void ev_init_list(event_list *el, struct birdloop *loop, const char *name)
-{
-  init_list(&el->events);
-  el->loop = loop;
-  el->lock = DOMAIN_NEW(event, name);
-}
-
-void ev_send(event_list *, event *);
+void ev_init_list(event_list *, struct birdloop *loop, const char *name);
+void ev_enqueue(event_list *, 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))
 
-_Bool birdloop_inside(struct birdloop *loop);
-
 static inline int
 ev_active(event *e)
 {
-  if (e->list == NULL)
-    return 0;
+  return atomic_load_explicit(&e->next, memory_order_relaxed) != NULL;
+}
 
-  ASSERT_DIE(birdloop_inside(e->list->loop));
-  return enlisted(&e->n);
+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*
-- 
cgit v1.2.3