kern/{condition,mutex}: reimplement on top of sleep queues

10 files changed, 292 insertions, 186 deletions

diff --git a/kern/condition.c b/kern/condition.c
index 467cb85a..bcd5ba42 100644
--- a/kern/condition.c
+++ b/kern/condition.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2013-2014 Richard Braun.
+ * Copyright (c) 2013-2017 Richard Braun.
  *
  * This program is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -15,124 +15,178 @@
  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  *
  *
- * In order to avoid the infamous thundering herd problem, this implementation
- * doesn't wake all threads when broadcasting a condition. Instead, they are
- * queued on the mutex associated with the condition, and an attempt to wake
- * one by locking and unlocking the mutex is performed. If the mutex is already
- * locked, the current owner does the same when unlocking.
+ * Locking order : mutex -> sleep queue
  */
 
 #include <stddef.h>
 
 #include <kern/assert.h>
 #include <kern/condition.h>
-#include <kern/list.h>
+#include <kern/condition_types.h>
 #include <kern/mutex.h>
-#include <kern/mutex_i.h>
-#include <kern/spinlock.h>
+#include <kern/sleepq.h>
 #include <kern/thread.h>
 
-void
-condition_wait(struct condition *condition, struct mutex *mutex)
+static void
+condition_inc_nr_sleeping_waiters(struct condition *condition)
 {
-    struct mutex_waiter waiter;
-    unsigned int state;
+    condition->nr_sleeping_waiters++;
+    assert(condition->nr_sleeping_waiters != 0);
+}
 
-    waiter.thread = thread_self();
+static void
+condition_dec_nr_sleeping_waiters(struct condition *condition)
+{
+    assert(condition->nr_sleeping_waiters != 0);
+    condition->nr_sleeping_waiters--;
+}
 
-    spinlock_lock(&condition->lock);
+static void
+condition_inc_nr_pending_waiters(struct condition *condition)
+{
+    condition->nr_pending_waiters++;
+    assert(condition->nr_pending_waiters != 0);
+}
 
-    assert((condition->mutex == NULL) || (condition->mutex == mutex));
+static void
+condition_dec_nr_pending_waiters(struct condition *condition)
+{
+    assert(condition->nr_pending_waiters != 0);
+    condition->nr_pending_waiters--;
+}
 
-    if (condition->mutex == NULL) {
-        condition->mutex = mutex;
-    }
+static void
+condition_move_waiters(struct condition *condition)
+{
+    unsigned short old;
 
-    list_insert_tail(&condition->waiters, &waiter.node);
+    assert(condition->nr_sleeping_waiters != 0);
+    old = condition->nr_pending_waiters;
+    condition->nr_pending_waiters += condition->nr_sleeping_waiters;
+    assert(old < condition->nr_pending_waiters);
+    condition->nr_sleeping_waiters = 0;
+}
 
-    spinlock_lock(&mutex->lock);
+void
+condition_wait(struct condition *condition, struct mutex *mutex)
+{
+    struct condition *last_cond;
+    struct sleepq *sleepq;
+
+    mutex_assert_locked(mutex);
+
+    /*
+     * Special case :
+     *
+     * mutex_lock(lock);
+     *
+     * for (;;) {
+     *     while (!done) {
+     *         condition_wait(condition, lock);
+     *     }
+     *
+     *     do_something();
+     * }
+     *
+     * Pull the last condition before unlocking the mutex to prevent
+     * mutex_unlock() from reacquiring the condition sleep queue.
+     */
+    last_cond = thread_pull_last_cond();
+
+    sleepq = sleepq_lend(condition, true);
+
+    mutex_unlock(mutex);
+
+    if (last_cond != NULL) {
+        assert(last_cond == condition);
+
+        if (condition->nr_pending_waiters != 0) {
+            sleepq_signal(sleepq);
+        }
+    }
 
-    state = mutex_release(mutex);
+    condition_inc_nr_sleeping_waiters(condition);
+    sleepq_wait(sleepq, "cond");
+    condition_dec_nr_pending_waiters(condition);
 
-    if (state == MUTEX_CONTENDED) {
-        mutex_signal(mutex);
+    if (condition->nr_pending_waiters != 0) {
+        thread_set_last_cond(condition);
     }
 
-    spinlock_unlock(&condition->lock);
+    sleepq_return(sleepq);
 
-    mutex_wait(mutex, &waiter);
-    mutex_trydowngrade(mutex);
-
-    spinlock_unlock(&mutex->lock);
+    mutex_lock(mutex);
 }
 
 void
 condition_signal(struct condition *condition)
 {
-    struct mutex_waiter *waiter;
-    struct mutex *mutex;
-    unsigned int state;
+    struct sleepq *sleepq;
 
-    spinlock_lock(&condition->lock);
+    sleepq = sleepq_acquire(condition, true);
 
-    if (condition->mutex == NULL) {
-        spinlock_unlock(&condition->lock);
+    if (sleepq == NULL) {
         return;
     }
 
-    mutex = condition->mutex;
-    waiter = list_first_entry(&condition->waiters, struct mutex_waiter, node);
-    list_remove(&waiter->node);
-
-    if (list_empty(&condition->waiters)) {
-        condition->mutex = NULL;
+    if (condition->nr_sleeping_waiters == 0) {
+        goto out;
     }
 
-    spinlock_unlock(&condition->lock);
-
-    spinlock_lock(&mutex->lock);
-
-    mutex_queue(mutex, waiter);
-    state = mutex_tryacquire_slow(mutex);
+    sleepq_signal(sleepq);
 
-    if (state == MUTEX_UNLOCKED) {
-        mutex_release(mutex);
-        mutex_signal(mutex);
-    }
+    condition_dec_nr_sleeping_waiters(condition);
+    condition_inc_nr_pending_waiters(condition);
 
-    spinlock_unlock(&mutex->lock);
+out:
+    sleepq_release(sleepq);
 }
 
 void
 condition_broadcast(struct condition *condition)
 {
-    struct list waiters;
-    struct mutex *mutex;
-    unsigned int state;
+    struct sleepq *sleepq;
 
-    spinlock_lock(&condition->lock);
+    sleepq = sleepq_acquire(condition, true);
 
-    if (condition->mutex == NULL) {
-        spinlock_unlock(&condition->lock);
+    if (sleepq == NULL) {
         return;
     }
 
-    mutex = condition->mutex;
-    condition->mutex = NULL;
-    list_set_head(&waiters, &condition->waiters);
-    list_init(&condition->waiters);
+    if (condition->nr_sleeping_waiters == 0) {
+        goto out;
+    }
 
-    spinlock_unlock(&condition->lock);
+    sleepq_signal(sleepq);
 
-    spinlock_lock(&mutex->lock);
+    condition_move_waiters(condition);
 
-    mutex_queue_list(mutex, &waiters);
-    state = mutex_tryacquire_slow(mutex);
+out:
+    sleepq_release(sleepq);
+}
 
-    if (state == MUTEX_UNLOCKED) {
-        mutex_release(mutex);
-        mutex_signal(mutex);
+void
+condition_wakeup(struct condition *condition)
+{
+    struct sleepq *sleepq;
+
+    sleepq = sleepq_acquire(condition, true);
+
+    if (sleepq == NULL) {
+        return;
     }
 
-    spinlock_unlock(&mutex->lock);
+    if (condition->nr_pending_waiters == 0) {
+        goto out;
+    }
+
+    /*
+     * Rely on the FIFO ordering of sleep queues so that signalling multiple
+     * times always wakes up the same thread, as long as that thread didn't
+     * reacquire the sleep queue.
+     */
+    sleepq_signal(sleepq);
+
+out:
+    sleepq_release(sleepq);
 }
diff --git a/kern/condition.h b/kern/condition.h
index 55d37bf2..0ce8d94f 100644
--- a/kern/condition.h
+++ b/kern/condition.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2013-2014 Richard Braun.
+ * Copyright (c) 2013-2017 Richard Braun.
  *
  * This program is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -16,34 +16,62 @@
  *
  *
  * Condition variables.
+ *
+ * A condition variable is a synchronization primitive used to wait
+ * until a predicate becomes true. Multiple threads can be waiting
+ * for this condition. In order to synchronize changes on the predicate
+ * with waiting and signalling, a condition variable must be associated
+ * with a mutex.
  */
 
 #ifndef _KERN_CONDITION_H
 #define _KERN_CONDITION_H
 
-#include <stddef.h>
-
 #include <kern/condition_types.h>
-#include <kern/list.h>
-#include <kern/spinlock.h>
+#include <kern/mutex_types.h>
 
-/*
- * Condition variable.
- */
 struct condition;
 
+/*
+ * Initialize a condition variable.
+ */
 static inline void
 condition_init(struct condition *condition)
 {
-    spinlock_init(&condition->lock);
-    condition->mutex = NULL;
-    list_init(&condition->waiters);
+    condition->nr_sleeping_waiters = 0;
+    condition->nr_pending_waiters = 0;
 }
 
-void condition_wait(struct condition *cond, struct mutex *mutex);
+/*
+ * Wait for a wake-up on the given condition variable.
+ *
+ * The associated mutex must be locked when calling this function.
+ * It is unlocked before waiting and relocked before returning.
+ */
+void condition_wait(struct condition *condition, struct mutex *mutex);
 
-void condition_signal(struct condition *cond);
+/*
+ * Wake up one (signal) or all (broadcast) threads waiting on a
+ * condition variable, if any.
+ *
+ * Although it is not necessary to hold the mutex associated to the
+ * condition variable when calling these functions, doing so guarantees
+ * that a wake-up done when changing the predicate cannot be missed by
+ * waiting threads.
+ */
+void condition_signal(struct condition *condition);
+void condition_broadcast(struct condition *condition);
 
-void condition_broadcast(struct condition *cond);
+/*
+ * Wake up a pending thread.
+ *
+ * This function isn't part of the standard condition variable interface.
+ * It is used to chain wake-ups to avoid the thundering herd effect.
+ * When broadcasting a condition variable, a single thread is actually
+ * awaken. Other threads become "pending waiters", still asleep but
+ * eligible for wake-up when the mutex associated to the condition variable,
+ * relocked when returning from condition_wait(), is finally unlocked.
+ */
+void condition_wakeup(struct condition *condition);
 
 #endif /* _KERN_CONDITION_H */
diff --git a/kern/condition_types.h b/kern/condition_types.h
index 03b22676..13a29205 100644
--- a/kern/condition_types.h
+++ b/kern/condition_types.h
@@ -21,14 +21,9 @@
 #ifndef _KERN_CONDITION_TYPES_H
 #define _KERN_CONDITION_TYPES_H
 
-#include <kern/list_types.h>
-#include <kern/mutex_types.h>
-#include <kern/spinlock_types.h>
-
 struct condition {
-    struct spinlock lock;
-    struct mutex *mutex;
-    struct list waiters;
+    unsigned short nr_sleeping_waiters;
+    unsigned short nr_pending_waiters;
 };
 
 #endif /* _KERN_CONDITION_TYPES_H */
diff --git a/kern/mutex.c b/kern/mutex.c
index 58e24513..1a1c2ea7 100644
--- a/kern/mutex.c
+++ b/kern/mutex.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2013-2014 Richard Braun.
+ * Copyright (c) 2013-2017 Richard Braun.
  *
  * This program is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -15,36 +15,50 @@
  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
 
+#include <stddef.h>
+
 #include <kern/mutex.h>
 #include <kern/mutex_i.h>
-#include <kern/spinlock.h>
-#include <kern/thread.h>
+#include <kern/sleepq.h>
 
 void
 mutex_lock_slow(struct mutex *mutex)
 {
-    struct mutex_waiter waiter;
+    struct sleepq *sleepq;
     unsigned int state;
 
-    spinlock_lock(&mutex->lock);
+    sleepq = sleepq_lend(mutex, false);
+
+    for (;;) {
+        state = atomic_swap_uint(&mutex->state, MUTEX_CONTENDED);
 
-    state = mutex_tryacquire_slow(mutex);
+        if (state == MUTEX_UNLOCKED) {
+            break;
+        }
 
-    if (state != MUTEX_UNLOCKED) {
-        waiter.thread = thread_self();
-        mutex_queue(mutex, &waiter);
-        mutex_wait(mutex, &waiter);
+        sleepq_wait(sleepq, "mutex");
     }
 
-    mutex_trydowngrade(mutex);
+    if (sleepq_empty(sleepq)) {
+        state = atomic_swap_uint(&mutex->state, MUTEX_LOCKED);
+        assert(state == MUTEX_CONTENDED);
+    }
 
-    spinlock_unlock(&mutex->lock);
+    sleepq_return(sleepq);
 }
 
 void
 mutex_unlock_slow(struct mutex *mutex)
 {
-    spinlock_lock(&mutex->lock);
-    mutex_signal(mutex);
-    spinlock_unlock(&mutex->lock);
+    struct sleepq *sleepq;
+
+    sleepq = sleepq_acquire(mutex, false);
+
+    if (sleepq == NULL) {
+        return;
+    }
+
+    sleepq_signal(sleepq);
+
+    sleepq_release(sleepq);
 }
diff --git a/kern/mutex.h b/kern/mutex.h
index 64efa350..2804fc44 100644
--- a/kern/mutex.h
+++ b/kern/mutex.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2013-2014 Richard Braun.
+ * Copyright (c) 2013-2017 Richard Braun.
  *
  * This program is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -15,9 +15,11 @@
  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  *
  *
- * Mutual exclusion locks.
+ * Mutual exclusion sleep locks.
  *
  * Unlike spin locks, acquiring a mutex may make the calling thread sleep.
+ *
+ * TODO Adaptive spinning.
  */
 
 #ifndef _KERN_MUTEX_H
@@ -25,23 +27,30 @@
 
 #include <kern/assert.h>
 #include <kern/error.h>
-#include <kern/list.h>
 #include <kern/mutex_i.h>
 #include <kern/mutex_types.h>
-#include <kern/spinlock.h>
+#include <kern/thread.h>
 
 struct mutex;
 
+#define mutex_assert_locked(mutex) assert((mutex)->state != MUTEX_UNLOCKED)
+
+/*
+ * Initialize a mutex.
+ */
 static inline void
 mutex_init(struct mutex *mutex)
 {
     mutex->state = MUTEX_UNLOCKED;
-    spinlock_init(&mutex->lock);
-    list_init(&mutex->waiters);
 }
 
-#define mutex_assert_locked(mutex) assert((mutex)->state != MUTEX_UNLOCKED)
-
+/*
+ * Attempt to lock the given mutex.
+ *
+ * This function may not sleep.
+ *
+ * Return 0 on success, ERROR_BUSY if the mutex is already locked.
+ */
 static inline int
 mutex_trylock(struct mutex *mutex)
 {
@@ -56,6 +65,14 @@ mutex_trylock(struct mutex *mutex)
     return ERROR_BUSY;
 }
 
+/*
+ * Lock a mutex.
+ *
+ * If the mutex is already locked, the calling thread sleeps until the
+ * mutex is unlocked.
+ *
+ * A mutex can only be locked once.
+ */
 static inline void
 mutex_lock(struct mutex *mutex)
 {
@@ -72,6 +89,12 @@ mutex_lock(struct mutex *mutex)
     mutex_lock_slow(mutex);
 }
 
+/*
+ * Unlock a mutex.
+ *
+ * The mutex must be locked, and must have been locked by the calling
+ * thread.
+ */
 static inline void
 mutex_unlock(struct mutex *mutex)
 {
@@ -79,13 +102,16 @@ mutex_unlock(struct mutex *mutex)
 
     state = mutex_release(mutex);
 
-    if (state == MUTEX_LOCKED) {
-        return;
+    if (state != MUTEX_LOCKED) {
+        assert(state == MUTEX_CONTENDED);
+        mutex_unlock_slow(mutex);
     }
 
-    assert(state == MUTEX_CONTENDED);
-
-    mutex_unlock_slow(mutex);
+    /*
+     * If this mutex was used along with a condition variable, wake up
+     * a potential pending waiter.
+     */
+    thread_wakeup_last_cond();
 }
 
 #endif /* _KERN_MUTEX_H */
diff --git a/kern/mutex_i.h b/kern/mutex_i.h
index 5e78a4da..a161b1bb 100644
--- a/kern/mutex_i.h
+++ b/kern/mutex_i.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2013-2014 Richard Braun.
+ * Copyright (c) 2013-2017 Richard Braun.
  *
  * This program is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -19,24 +19,13 @@
 #define _KERN_MUTEX_I_H
 
 #include <kern/assert.h>
-#include <kern/list.h>
 #include <kern/mutex_types.h>
-#include <kern/thread.h>
 #include <machine/atomic.h>
 
 #define MUTEX_UNLOCKED  0
 #define MUTEX_LOCKED    1
 #define MUTEX_CONTENDED 2
 
-struct mutex_waiter {
-    struct list node;
-    struct thread *thread;
-};
-
-void mutex_lock_slow(struct mutex *mutex);
-
-void mutex_unlock_slow(struct mutex *mutex);
-
 static inline unsigned int
 mutex_tryacquire(struct mutex *mutex)
 {
@@ -44,12 +33,6 @@ mutex_tryacquire(struct mutex *mutex)
 }
 
 static inline unsigned int
-mutex_tryacquire_slow(struct mutex *mutex)
-{
-    return atomic_swap_uint(&mutex->state, MUTEX_CONTENDED);
-}
-
-static inline unsigned int
 mutex_release(struct mutex *mutex)
 {
     unsigned int state;
@@ -59,51 +42,9 @@ mutex_release(struct mutex *mutex)
     return state;
 }
 
-static inline void
-mutex_queue(struct mutex *mutex, struct mutex_waiter *waiter)
-{
-    list_insert_tail(&mutex->waiters, &waiter->node);
-}
-
-static inline void
-mutex_queue_list(struct mutex *mutex, struct list *waiters)
-{
-    list_concat(&mutex->waiters, waiters);
-}
-
-static inline void
-mutex_wait(struct mutex *mutex, struct mutex_waiter *waiter)
-{
-    unsigned int state;
-
-    do {
-        thread_sleep(&mutex->lock, mutex, "mutex");
-        state = mutex_tryacquire_slow(mutex);
-    } while (state != MUTEX_UNLOCKED);
-
-    list_remove(&waiter->node);
-}
-
-static inline void
-mutex_signal(struct mutex *mutex)
-{
-    struct mutex_waiter *waiter;
-
-    if (!list_empty(&mutex->waiters)) {
-        waiter = list_first_entry(&mutex->waiters, struct mutex_waiter, node);
-        thread_wakeup(waiter->thread);
-    }
-}
+void mutex_lock_slow(struct mutex *mutex);
 
-static inline void
-mutex_trydowngrade(struct mutex *mutex)
-{
-    if (list_empty(&mutex->waiters)) {
-        unsigned int state;
+void mutex_unlock_slow(struct mutex *mutex);
 
-        state = atomic_swap_uint(&mutex->state, MUTEX_LOCKED);
-        assert(state == MUTEX_CONTENDED);
-    }
-}
 
 #endif /* _KERN_MUTEX_I_H */
diff --git a/kern/mutex_types.h b/kern/mutex_types.h
index b348fb7b..e3126b10 100644
--- a/kern/mutex_types.h
+++ b/kern/mutex_types.h
@@ -21,13 +21,8 @@
 #ifndef _KERN_MUTEX_TYPES_H
 #define _KERN_MUTEX_TYPES_H
 
-#include <kern/list_types.h>
-#include <kern/spinlock_types.h>
-
 struct mutex {
     unsigned int state;
-    struct spinlock lock;
-    struct list waiters;
 };
 
 #endif /* _KERN_MUTEX_TYPES_H */
diff --git a/kern/thread.c b/kern/thread.c
index 3eccebda..436df07a 100644
--- a/kern/thread.c
+++ b/kern/thread.c
@@ -1803,6 +1803,7 @@ thread_init(struct thread *thread, void *stack,
     }
 
     turnstile_td_init(&thread->turnstile_td);
+    thread->last_cond = NULL;
     thread->propagate_priority = false;
     thread->preempt = THREAD_SUSPEND_PREEMPT_LEVEL;
     thread->pinned = 0;
diff --git a/kern/thread.h b/kern/thread.h
index 15babbfc..b9308b65 100644
--- a/kern/thread.h
+++ b/kern/thread.h
@@ -37,6 +37,7 @@
 #include <stddef.h>
 
 #include <kern/assert.h>
+#include <kern/condition.h>
 #include <kern/cpumap.h>
 #include <kern/macros.h>
 #include <kern/spinlock_types.h>
@@ -436,6 +437,48 @@ thread_sleepq_return(struct sleepq *sleepq)
 }
 
 /*
+ * Condition variable related functions.
+ */
+
+static inline void
+thread_set_last_cond(struct condition *last_cond)
+{
+    struct thread *thread;
+
+    thread = thread_self();
+    assert(thread->last_cond == NULL);
+    thread->last_cond = last_cond;
+}
+
+static inline struct condition *
+thread_pull_last_cond(void)
+{
+    struct condition *last_cond;
+    struct thread *thread;
+
+    thread = thread_self();
+    last_cond = thread->last_cond;
+
+    if (last_cond != NULL) {
+        thread->last_cond = NULL;
+    }
+
+    return last_cond;
+}
+
+static inline void
+thread_wakeup_last_cond(void)
+{
+    struct condition *last_cond;
+
+    last_cond = thread_pull_last_cond();
+
+    if (last_cond != NULL) {
+        condition_wakeup(last_cond);
+    }
+}
+
+/*
  * Turnstile lending functions.
  */
 
diff --git a/kern/thread_i.h b/kern/thread_i.h
index 865787a0..9bb55827 100644
--- a/kern/thread_i.h
+++ b/kern/thread_i.h
@@ -107,6 +107,15 @@ struct thread {
     /* Turnstile available for lending */
     struct turnstile *priv_turnstile;
 
+    /*
+     * When a thread wakes up after waiting for a condition variable,
+     * it sets this variable so that other waiters are only awaken
+     * after the associated mutex has actually been released.
+     *
+     * This member is thread-local.
+     */
+    struct condition *last_cond;
+
     /* Per-thread turnstile data */
     struct turnstile_td turnstile_td;