Fix condition variable broadcasting

The broadcast implementation is based on an invalid assumption, namely
that the first mutex_unlock call following condition_wait would be invoked
on the same mutex. Fixing this while guarding against the thundering herd
effect requires augmenting mutexes with a pointer to the condition
variable they may be associated with. Since the size of mutexes is
currently more important than broadcast scalability, the implementation
is simplified into one which suffers from the thundering herd effect.

8 files changed, 13 insertions, 169 deletions

diff --git a/kern/condition.c b/kern/condition.c
index e6d65951..c407e949 100644
--- a/kern/condition.c
+++ b/kern/condition.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2013-2017 Richard Braun.
+ * Copyright (c) 2013-2018 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
@@ -27,46 +27,21 @@
 #include <kern/condition_types.h>
 #include <kern/mutex.h>
 #include <kern/sleepq.h>
-#include <kern/thread.h>
 
 static int
 condition_wait_common(struct condition *condition, struct mutex *mutex,
                       bool timed, uint64_t ticks)
 {
-    struct condition *last_cond;
     struct sleepq *sleepq;
     unsigned long flags;
     int error;
 
     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, &flags);
 
     mutex_unlock(mutex);
 
-    if (last_cond != NULL) {
-        assert(last_cond == condition);
-        sleepq_wakeup(sleepq);
-    }
-
     if (timed) {
         error = sleepq_timedwait(sleepq, "cond", ticks);
     } else {
@@ -74,10 +49,6 @@ condition_wait_common(struct condition *condition, struct mutex *mutex,
         error = 0;
     }
 
-    if (!error) {
-        thread_set_last_cond(condition);
-    }
-
     sleepq_return(sleepq, flags);
 
     mutex_lock(mutex);
@@ -134,20 +105,3 @@ condition_broadcast(struct condition *condition)
 
     sleepq_release(sleepq, flags);
 }
-
-void
-condition_wakeup(struct condition *condition)
-{
-    struct sleepq *sleepq;
-    unsigned long flags;
-
-    sleepq = sleepq_acquire(condition, true, &flags);
-
-    if (sleepq == NULL) {
-        return;
-    }
-
-    sleepq_wakeup(sleepq);
-
-    sleepq_release(sleepq, flags);
-}
diff --git a/kern/condition.h b/kern/condition.h
index 90a59f0d..2082bee5 100644
--- a/kern/condition.h
+++ b/kern/condition.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2013-2017 Richard Braun.
+ * Copyright (c) 2013-2018 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
@@ -65,16 +65,4 @@ int condition_timedwait(struct condition *condition,
 void condition_signal(struct condition *condition);
 void condition_broadcast(struct condition *condition);
 
-/*
- * 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/mutex.h b/kern/mutex.h
index 10872e6e..b4332dea 100644
--- a/kern/mutex.h
+++ b/kern/mutex.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2013-2017 Richard Braun.
+ * Copyright (c) 2013-2018 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
@@ -37,7 +37,6 @@
 
 #include <kern/init.h>
 #include <kern/mutex_types.h>
-#include <kern/thread.h>
 
 /*
  * Initialize a mutex.
@@ -102,12 +101,6 @@ static inline void
 mutex_unlock(struct mutex *mutex)
 {
     mutex_impl_unlock(mutex);
-
-    /*
-     * If this mutex was used along with a condition variable, wake up
-     * a potential pending waiter.
-     */
-    thread_wakeup_last_cond();
 }
 
 /*
diff --git a/kern/sleepq.c b/kern/sleepq.c
index 0d04c6ea..1fd1ac42 100644
--- a/kern/sleepq.c
+++ b/kern/sleepq.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2017 Richard Braun.
+ * Copyright (c) 2017-2018 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
@@ -503,46 +503,23 @@ sleepq_signal(struct sleepq *sleepq)
     sleepq_waiter_wakeup(waiter);
 }
 
-static void
-sleepq_wakeup_common(struct sleepq *sleepq)
-{
-    struct sleepq_waiter *waiter;
-
-    assert(!list_empty(&sleepq->waiters));
-
-    waiter = list_last_entry(&sleepq->waiters, struct sleepq_waiter, node);
-    sleepq_waiter_wakeup(waiter);
-}
-
 void
 sleepq_broadcast(struct sleepq *sleepq)
 {
     struct sleepq_waiter *waiter;
 
     if (sleepq->oldest_waiter == NULL) {
-        goto out;
+        return;
     }
 
+    sleepq->oldest_waiter = NULL;
+
     list_for_each_entry(&sleepq->waiters, waiter, node) {
         sleepq_waiter_set_pending_wakeup(waiter);
+        sleepq_waiter_wakeup(waiter);
 
         if (waiter == sleepq->oldest_waiter) {
             break;
         }
     }
-
-    sleepq->oldest_waiter = NULL;
-
-out:
-    sleepq_wakeup_common(sleepq);
-}
-
-void
-sleepq_wakeup(struct sleepq *sleepq)
-{
-    if (list_empty(&sleepq->waiters)) {
-        return;
-    }
-
-    sleepq_wakeup_common(sleepq);
 }
diff --git a/kern/sleepq.h b/kern/sleepq.h
index 007e3f2f..213925cb 100644
--- a/kern/sleepq.h
+++ b/kern/sleepq.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2017 Richard Braun.
+ * Copyright (c) 2017-2018 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
@@ -125,25 +125,12 @@ int sleepq_timedwait(struct sleepq *sleepq, const char *wchan, uint64_t ticks);
  * At least one thread is awaken if any threads are waiting on the sleep
  * queue.
  *
- * A broadcast differs only by also making all currently waiting threads
- * pending for wake-up. As with sleepq_signal, a single thread may be
- * awaken. The rationale is to force users to implement "chained waking"
- * in order to avoid the thundering herd effect.
+ * Broadcasting a sleep queue wakes up all waiting threads.
  */
 void sleepq_signal(struct sleepq *sleepq);
 void sleepq_broadcast(struct sleepq *sleepq);
 
 /*
- * Wake up a pending thread.
- *
- * This function may only wake up a thread pending for wake-up after a
- * broadcast. It is used to chain wake-ups to avoid the thundering herd
- * effect. If there are no threads pending for wake-up, this function
- * does nothing.
- */
-void sleepq_wakeup(struct sleepq *sleepq);
-
-/*
  * This init operation provides :
  *  - sleepq creation
  *  - module fully initialized
diff --git a/kern/thread.c b/kern/thread.c
index 330b5375..f41e5936 100644
--- a/kern/thread.c
+++ b/kern/thread.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2012-2017 Richard Braun.
+ * Copyright (c) 2012-2018 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
@@ -92,7 +92,6 @@
 
 #include <kern/atomic.h>
 #include <kern/clock.h>
-#include <kern/condition.h>
 #include <kern/cpumap.h>
 #include <kern/error.h>
 #include <kern/init.h>
@@ -1821,7 +1820,6 @@ thread_init(struct thread *thread, void *stack,
     }
 
     turnstile_td_init(&thread->turnstile_td);
-    thread->last_cond = NULL;
     thread->propagate_priority = false;
     thread->preempt_level = THREAD_SUSPEND_PREEMPT_LEVEL;
     thread->pin_level = 0;
diff --git a/kern/thread.h b/kern/thread.h
index 4761e1ec..8084c114 100644
--- a/kern/thread.h
+++ b/kern/thread.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2012-2017 Richard Braun.
+ * Copyright (c) 2012-2018 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
@@ -41,7 +41,6 @@
 
 #include <kern/atomic.h>
 #include <kern/init.h>
-#include <kern/condition.h>
 #include <kern/cpumap.h>
 #include <kern/kernel.h>
 #include <kern/macros.h>
@@ -442,48 +441,6 @@ 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 067b31ed..96ce100a 100644
--- a/kern/thread_i.h
+++ b/kern/thread_i.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2017 Richard Braun.
+ * Copyright (c) 2017-2018 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
@@ -22,7 +22,6 @@
 #include <stdbool.h>
 
 #include <kern/atomic.h>
-#include <kern/condition_types.h>
 #include <kern/cpumap.h>
 #include <kern/list_types.h>
 #include <kern/spinlock_types.h>
@@ -121,15 +120,6 @@ 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;        /* (-) */
-
     struct turnstile_td turnstile_td;   /* (t) */
 
     /* True if priority must be propagated when preemption is reenabled */