From 559fe1daace8f48a8dc37906f840e9981b961415 Mon Sep 17 00:00:00 2001
From: wm4 <wm4@nowhere>
Date: Sat, 26 Jul 2014 20:29:48 +0200
Subject: Add Plan 9-style barriers

Plan 9 has a very interesting synchronization mechanism, the
rendezvous() call. A good property of this is that you don't need to
explicitly initialize and destroy a barrier object, unlike as with e.g.
POSIX barriers (which are mandatory to begin with). Upon "meeting", they
can exchange a value.

This mechanism will be nice to synchronize certain stages of
initialization between threads in the following commit.

Unlike Plan 9 rendezvous(), this is not implemented with a hashtable,
because that would require additional effort (especially if you want to
make it actually scele). Unlike the Plan 9 variant, we use intptr_t
instead of void* as type for the value, because I expect that we will be
mostly passing a status code as value and not a pointer. Converting an
integer to void* requires two cast (because the integer needs to be
intptr_t), the other way around it's only one cast.

We don't particularly care about performance in this case either. It's
simply not important for our use-case. So a simple linked list is used
for waiters, and on wakeup, all waiters are temporarily woken up.
---
 misc/rendezvous.c | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 misc/rendezvous.h |  8 ++++++++
 old-makefile      |  1 +
 wscript_build.py  |  1 +
 4 files changed, 64 insertions(+)
 create mode 100644 misc/rendezvous.c
 create mode 100644 misc/rendezvous.h

diff --git a/misc/rendezvous.c b/misc/rendezvous.c
new file mode 100644
index 0000000000..9af798dd07
--- /dev/null
+++ b/misc/rendezvous.c
@@ -0,0 +1,54 @@
+#include <pthread.h>
+
+#include "rendezvous.h"
+
+static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
+static pthread_cond_t wakeup = PTHREAD_COND_INITIALIZER;
+
+static struct waiter *waiters;
+
+struct waiter {
+    void *tag;
+    struct waiter *next;
+    intptr_t *value;
+};
+
+/* A barrier for 2 threads, which can exchange a value when they meet.
+ * The first thread to call this function will block. As soon as two threads
+ * are calling this function with the same tag value, they will unblock, and
+ * on each thread the call return the value parameter of the _other_ thread.
+ *
+ * tag is an arbitrary value, but it must be an unique pointer. If there are
+ * more than 2 threads using the same tag, things won't work. Typically, it
+ * will have to point to a memory allocation or to the stack, while pointing
+ * it to static data is always a bug.
+ *
+ * This shouldn't be used for performance critical code (uses a linked list
+ * of _all_ waiters in the process, and temporarily wakes up _all_ waiters on
+ * each second call).
+ *
+ * This is inspired by: http://9atom.org/magic/man2html/2/rendezvous */
+intptr_t mp_rendezvous(void *tag, intptr_t value)
+{
+    struct waiter wait = { .tag = tag, .value = &value };
+    pthread_mutex_lock(&lock);
+    struct waiter **prev = &waiters;
+    while (*prev) {
+        if ((*prev)->tag == tag) {
+            intptr_t tmp = *(*prev)->value;
+            *(*prev)->value = value;
+            value = tmp;
+            (*prev)->value = NULL; // signals completion
+            *prev = (*prev)->next; // unlink
+            pthread_cond_broadcast(&wakeup);
+            goto done;
+        }
+        prev = &(*prev)->next;
+    }
+    *prev = &wait;
+    while (wait.value)
+        pthread_cond_wait(&wakeup, &lock);
+done:
+    pthread_mutex_unlock(&lock);
+    return value;
+}
diff --git a/misc/rendezvous.h b/misc/rendezvous.h
new file mode 100644
index 0000000000..ffcc89a22c
--- /dev/null
+++ b/misc/rendezvous.h
@@ -0,0 +1,8 @@
+#ifndef MP_RENDEZVOUS_H_
+#define MP_RENDEZVOUS_H_
+
+#include <stdint.h>
+
+intptr_t mp_rendezvous(void *tag, intptr_t value);
+
+#endif
diff --git a/old-makefile b/old-makefile
index c5d8e6a223..a1d98e60ec 100644
--- a/old-makefile
+++ b/old-makefile
@@ -177,6 +177,7 @@ SOURCES = audio/audio.c \
           input/keycodes.c \
           misc/charset_conv.c \
           misc/dispatch.c \
+          misc/rendezvous.c \
           misc/ring.c \
           options/m_config.c \
           options/m_option.c \
diff --git a/wscript_build.py b/wscript_build.py
index 62446d1907..463c3c1084 100644
--- a/wscript_build.py
+++ b/wscript_build.py
@@ -201,6 +201,7 @@ def build(ctx):
         ( "misc/charset_conv.c" ),
         ( "misc/dispatch.c" ),
         ( "misc/ring.c" ),
+        ( "misc/rendezvous.c" ),
 
         ## Options
         ( "options/m_config.c" ),
-- 
cgit v1.2.3