Rendezvous: plan9 style sync with CVs
authorBarret Rhoden <brho@cs.berkeley.edu>
Tue, 8 Oct 2013 00:56:40 +0000 (17:56 -0700)
committerBarret Rhoden <brho@cs.berkeley.edu>
Thu, 16 Jan 2014 02:22:55 +0000 (18:22 -0800)
Rendezvous encapsulates a common CV pattern, albeit one where the
locking is grabbed internally.  If you need the lock grabbed externally
to protect some invariant, then you can probably just use CVs directly.

To reiterate: the rendez locks internally, and when we run the func
pointer to check cond, we hold the lock.  But that lock isn't meant to
protect against concurrent changes to the state - it protects the rv
(rendez variable, btw).

The timeout code is a bit trickier.  You can either use rendez as an
example, or use it directly.  If the locking style of rendez is
insufficient and you need a timer, we can consider exposing the rendez
lock, similar to cv_lock().  Assuming your timer code is fairly
identical.  We'll see.

The test handles a few basic cases, but nothing with actual IRQs.

kern/include/rendez.h [new file with mode: 0644]
kern/src/Kbuild
kern/src/rendez.c [new file with mode: 0644]
kern/src/testing.c

diff --git a/kern/include/rendez.h b/kern/include/rendez.h
new file mode 100644 (file)
index 0000000..e819bdb
--- /dev/null
@@ -0,0 +1,54 @@
+/* Copyright (c) 2013 The Regents of the University of California
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * Plan9 style Rendezvous (http://plan9.bell-labs.com/sys/doc/sleep.html)
+ *
+ * We implement it with CVs, and it can handle multiple sleepers/wakers.
+ *
+ * Init:
+ *             rendez_init(&rv);
+ *
+ * Sleeper usage:
+ *             rendez_sleep(&rv, some_func_taking_void*, void *arg);
+ *                     or
+ *             rendez_sleep_timeout(&rv, some_func_taking_void*, void *arg, msec);
+ *
+ * Waker usage: (can be used from IRQ context)
+ *             // set the condition to TRUE, then:
+ *             rendez_wakeup(&rv);
+ *
+ * Some notes:
+ * - Some_func checks some condition and returns TRUE when we want to wake up.
+ * - Sleep returns when the condition is true and when it has been woken up.
+ *   It can return without sleeping or requiring a wakeup if the condition is
+ *   already true.
+ * - Wakers should set the condition, then trigger the wakeup to ensure the
+ *   sleeper has awakened.  (internal locks provide the needed barriers).
+ * - Timeout sleep is like regular sleep, with the addition that it will return
+ *   after some milliseconds, regardless of the condition.
+ * - The only locking/protection is done internally.  In plan9, they expect to
+ *   only have one sleeper and one waker.  So your code around the rendez needs
+ *   to take that into account.  The old plan9 code should already do this.
+ *
+ * - TODO: i dislike the int vs bool on the func pointer.  prob would need to
+ *   change all 9ns rendez functions
+ */
+
+#ifndef ROS_KERN_RENDEZ_H
+#define ROS_KERN_RENDEZ_H
+
+#include <ros/common.h>
+#include <kthread.h>
+
+struct rendez {
+       struct cond_var                         cv;
+};
+
+void rendez_init(struct rendez *rv);
+void rendez_sleep(struct rendez *rv, int (*cond)(void*), void *arg);
+void rendez_sleep_timeout(struct rendez *rv, int (*cond)(void*), void *arg,
+                          unsigned int msec);
+void rendez_wakeup(struct rendez *rv);
+
+#endif /* ROS_KERN_RENDEZ_H */
index 3aaf92d..ba85ea5 100644 (file)
@@ -32,6 +32,7 @@ obj-y                                         += printfmt.o
 obj-y                                          += process.o
 obj-y                                          += radix.o
 obj-y                                          += readline.o
+obj-y                                          += rendez.o
 obj-y                                          += rwlock.o
 obj-y                                          += schedule.o
 obj-y                                          += slab.o
diff --git a/kern/src/rendez.c b/kern/src/rendez.c
new file mode 100644 (file)
index 0000000..52e6a1c
--- /dev/null
@@ -0,0 +1,81 @@
+/* Copyright (c) 2013 The Regents of the University of California
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * Plan9 style Rendezvous (http://plan9.bell-labs.com/sys/doc/sleep.html)
+ *
+ * We implement it with CVs, and it can handle multiple sleepers/wakers. */
+
+#include <rendez.h>
+#include <kthread.h>
+#include <alarm.h>
+#include <assert.h>
+#include <smp.h>
+
+void rendez_init(struct rendez *rv)
+{
+       cv_init_irqsave(&rv->cv);
+}
+
+void rendez_sleep(struct rendez *rv, int (*cond)(void*), void *arg)
+{
+       int8_t irq_state = 0;
+       cv_lock_irqsave(&rv->cv, &irq_state);
+       /* Mesa-style semantics, which is definitely what you want.  See the
+        * discussion at the end of the URL above. */
+       while (!cond(arg)) {
+               cv_wait(&rv->cv);
+               cpu_relax();
+       }
+       cv_unlock_irqsave(&rv->cv, &irq_state);
+}
+
+/* Force a wakeup of all waiters on the rv, including non-timeout users.  For
+ * those, they will just wake up, see the condition is still false (probably)
+ * and go back to sleep. */
+static void rendez_alarm_handler(struct alarm_waiter *awaiter)
+{
+       struct rendez *rv = (struct rendez*)awaiter->data;
+       rendez_wakeup(rv);
+}
+
+/* Like sleep, but it will timeout in 'msec' milliseconds. */
+void rendez_sleep_timeout(struct rendez *rv, int (*cond)(void*), void *arg,
+                          unsigned int msec)
+{
+       int8_t irq_state = 0;
+       struct alarm_waiter awaiter;
+       struct timer_chain *pcpui_tchain = &per_cpu_info[core_id()].tchain;
+
+       assert((int)msec > 0);
+       /* The handler will call rendez_wake, but won't mess with the condition
+        * state.  It's enough to break us out of cv_wait() to see .has_fired. */
+       init_awaiter(&awaiter, rendez_alarm_handler);
+       awaiter.data = rv;
+       set_awaiter_rel(&awaiter, msec);
+       /* Set our alarm on this cpu's tchain.  Note that when we sleep in cv_wait,
+        * we could be migrated, and later on we could be unsetting the alarm
+        * remotely. */
+       set_alarm(pcpui_tchain, &awaiter);
+       cv_lock_irqsave(&rv->cv, &irq_state);
+       /* We could wake early for a few reasons.  Legit wakeups after a changed
+        * condition (and we should exit), other alarms with different timeouts (and
+        * we should go back to sleep), etc.  Note it is possible for our alarm to
+        * fire immediately upon setting it: before we even cv_lock. */
+       while (!cond(arg) && !awaiter.has_fired) {
+               cv_wait(&rv->cv);
+               cpu_relax();
+       }
+       cv_unlock_irqsave(&rv->cv, &irq_state);
+       /* Turn off our alarm.  If it already fired, this is a no-op.  Note this
+        * could be cross-core. */
+       unset_alarm(pcpui_tchain, &awaiter);
+}
+
+void rendez_wakeup(struct rendez *rv)
+{
+       int8_t irq_state = 0;
+       /* The plan9 style "one sleeper, one waker" could get by with a signal here.
+        * But we want to make sure all potential waiters are woken up. */
+       cv_broadcast_irqsave(&rv->cv, &irq_state);
+}
index 7c7a072..381eeea 100644 (file)
@@ -40,6 +40,7 @@
 #include <setjmp.h>
 #include <apipe.h>
 #include <rwlock.h>
+#include <rendez.h>
 
 #define l1 (available_caches.l1)
 #define l2 (available_caches.l2)
@@ -1768,3 +1769,87 @@ void test_rwlock(void)
                cpu_relax();
        printk("rwlock test complete\n");
 }
+
+/* Funcs and global vars for test_rv() */
+static struct rendez local_rv;
+static struct rendez *rv = &local_rv;
+/* reusing state and counter from test_cv... */
+
+static int __rendez_cond(void *arg)
+{
+       return *(bool*)arg;
+}
+
+void __test_rv_wakeup(uint32_t srcid, long a0, long a1, long a2)
+{
+       if (atomic_read(&counter) % 4)
+               cv_signal(cv);
+       else
+               cv_broadcast(cv);
+       atomic_dec(&counter);
+}
+
+void __test_rv_sleeper(uint32_t srcid, long a0, long a1, long a2)
+{
+       rendez_sleep(rv, __rendez_cond, (void*)&state);
+       atomic_dec(&counter);
+}
+
+void __test_rv_sleeper_timeout(uint32_t srcid, long a0, long a1, long a2)
+{
+       /* half-assed amount of time. */
+       rendez_sleep_timeout(rv, __rendez_cond, (void*)&state, a0);
+       atomic_dec(&counter);
+}
+
+void test_rv(void)
+{
+       int nr_msgs;
+
+       rendez_init(rv);
+       /* Test 0: signal without waiting */
+       rendez_wakeup(rv);
+       kthread_yield();
+       printk("test_rv: wakeup without sleeping complete\n");
+
+       /* Test 1: a few sleepers */
+       nr_msgs = num_cpus - 1; /* not using cpu 0 */
+       atomic_init(&counter, nr_msgs);
+       state = FALSE;
+       for (int i = 1; i < num_cpus; i++)
+               send_kernel_message(i, __test_rv_sleeper, 0, 0, 0, KMSG_ROUTINE);
+       udelay(1000000);
+       cmb();
+       state = TRUE;
+       rendez_wakeup(rv);
+       /* broadcast probably woke up the waiters on our core.  since we want to
+        * spin on their completion, we need to yield for a bit. */
+       kthread_yield();
+       while (atomic_read(&counter))
+               cpu_relax();
+       printk("test_rv: bulk wakeup complete\n");
+
+       /* Test 2: different types of sleepers / timeouts */
+       state = FALSE;
+       nr_msgs = 0x500;        /* any more than 0x20000 could go OOM */
+       atomic_init(&counter, nr_msgs);
+       for (int i = 0; i < nr_msgs; i++) {
+               int cpu = (i % (num_cpus - 1)) + 1;
+               /* timeouts from 0ms ..5000ms (enough that they should wake via cond */
+               if (atomic_read(&counter) % 5)
+                       send_kernel_message(cpu, __test_rv_sleeper_timeout, i * 4, 0, 0,
+                                           KMSG_ROUTINE);
+               else
+                       send_kernel_message(cpu, __test_rv_sleeper, 0, 0, 0, KMSG_ROUTINE);
+       }
+       kthread_yield();        /* run whatever messages we sent to ourselves */
+       state = TRUE;
+       while (atomic_read(&counter)) {
+               cpu_relax();
+               rendez_wakeup(rv);
+               udelay(1000000);
+               kthread_yield();        /* run whatever messages we sent to ourselves */
+       }
+       assert(!rv->cv.nr_waiters);
+       printk("test_rv: lots of sleepers/timeouts complete\n");
+}