kern/sleepq: fix signal behaviour

In order to correctly implement the behaviour of condition_signal, which
must wake up at least one waiting thread if there's any, sleepq_signal
wakes up the oldest waiter and shifts it.

The FIFO behaviour is removed from the specification, as the only user
which relied on it was a previous condition variable implementation.

2 files changed, 6 insertions, 8 deletions

diff --git a/kern/sleepq.c b/kern/sleepq.c
index bd0e363e..0d04c6ea 100644
--- a/kern/sleepq.c
+++ b/kern/sleepq.c
@@ -492,11 +492,13 @@ sleepq_signal(struct sleepq *sleepq)
 {
     struct sleepq_waiter *waiter;
 
-    if (list_empty(&sleepq->waiters)) {
+    waiter = sleepq->oldest_waiter;
+
+    if (!waiter) {
         return;
     }
 
-    waiter = list_last_entry(&sleepq->waiters, struct sleepq_waiter, node);
+    sleepq_shift_oldest_waiter(sleepq);
     sleepq_waiter_set_pending_wakeup(waiter);
     sleepq_waiter_wakeup(waiter);
 }
diff --git a/kern/sleepq.h b/kern/sleepq.h
index 827d0436..007e3f2f 100644
--- a/kern/sleepq.h
+++ b/kern/sleepq.h
@@ -105,8 +105,6 @@ bool sleepq_empty(const struct sleepq *sleepq);
  * released, e.g. if a single thread is waiting and another signals
  * the queue, the queue is not immediately considered empty.
  *
- * Threads are queued in FIFO order.
- *
  * When bounding the duration of the wait, the caller must pass an absolute
  * time in ticks, and ERROR_TIMEDOUT is returned if that time is reached
  * before the sleep queue is signalled.
@@ -124,10 +122,8 @@ int sleepq_timedwait(struct sleepq *sleepq, const char *wchan, uint64_t ticks);
  * acquired) when waiting, and acquired in order to signal it,
  * wake-ups are serialized and cannot be missed.
  *
- * Threads are queued in FIFO order, which means signalling a sleep
- * queue multiple times always awakens the same thread, regardless
- * of new waiters, as long as that thread didn't reacquire the
- * sleep queue.
+ * 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