feat: implement WaitQueue class for blocking synchronization

3 files changed, 169 insertions, 0 deletions

diff --git a/na/include/lume/wait.h b/na/include/lume/wait.h
new file mode 100644
index 0000000..02012ab
--- /dev/null
+++ b/na/include/lume/wait.h
@@ -0,0 +1,22 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/* Copyright (C) 2026 Richard Qin */
+
+#pragma once
+
+/*
+ * POSIX waitpid / wait4 Constants
+ * Reference: docs/specs/syscall.md §9
+ */
+
+/* waitpid options */
+inline constexpr int WNOHANG    = 1;
+inline constexpr int WUNTRACED  = 2;
+
+/* Exit status encoding (Linux-compatible) */
+static inline int WEXITSTATUS(int s) { return (s >> 8) & 0xFF; }
+static inline bool WIFEXITED(int s)  { return (s & 0x7F) == 0; }
+static inline bool WIFSIGNALED(int s){ return (s & 0x7F) != 0 && (s & 0x7F) != 0x7F; }
+static inline int WTERMSIG(int s)    { return s & 0x7F; }
+
+/* Encode exit code into wstatus (normal exit) */
+static inline int W_EXITCODE(int code) { return (code & 0xFF) << 8; }
diff --git a/na/include/lume/waitqueue.h b/na/include/lume/waitqueue.h
new file mode 100644
index 0000000..dd5edfe
--- /dev/null
+++ b/na/include/lume/waitqueue.h
@@ -0,0 +1,50 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/* Copyright (C) 2026 Richard Qin */
+
+#pragma once
+
+/*
+ * WaitQueue — blocking synchronization primitive
+ *
+ * A thread calls wq.sleep() to block itself until another thread
+ * (or interrupt handler) calls wq.wake_one() or wq.wake_all().
+ *
+ * Implementation: intrusive doubly-linked list of sleeping tasks,
+ * protected by an internal spinlock.
+ *
+ * Reference: docs/specs/scheduler.md, docs/specs/task.md §5
+ */
+
+#include <lume/types.h>
+#include <lume/list.h>
+#include <kernel/sync/spinlock.h>
+
+struct TaskControlBlock;
+
+class WaitQueue {
+public:
+    void init(const char* name = "wq") {
+        head_.init();
+        lock_.init(name);
+    }
+
+    /* Block the current task on this queue.
+     * If external_lock is provided, it is released AFTER the task is
+     * added to the wait queue but BEFORE schedule() is called,
+     * to avoid lost wakeups.
+     * Returns after wake_one/wake_all unblocks this task. */
+    void sleep(Spinlock* external_lock = nullptr);
+
+    /* Wake the first (oldest) sleeping task. Returns true if a task was woken. */
+    bool wake_one();
+
+    /* Wake all sleeping tasks. Returns the number of tasks woken. */
+    int wake_all();
+
+    /* Check if any tasks are waiting. */
+    bool is_empty() const { return head_.is_empty(); }
+
+private:
+    list_node head_;
+    Spinlock lock_;
+};
diff --git a/na/kernel/waitqueue.cc b/na/kernel/waitqueue.cc
new file mode 100644
index 0000000..9ee3f46
--- /dev/null
+++ b/na/kernel/waitqueue.cc
@@ -0,0 +1,97 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/* Copyright (C) 2026 Richard Qin */
+
+/*
+ * WaitQueue — blocking synchronization implementation
+ *
+ * sleep():    current task → Sleeping, link into queue, schedule()
+ * wake_one(): dequeue head task → Runnable, sched_enqueue()
+ *
+ * The internal spinlock protects the wait list only.
+ * schedule() is called AFTER releasing the spinlock to avoid
+ * holding a lock across a context switch.
+ */
+
+#include <lume/waitqueue.h>
+#include <lume/task.h>
+#include <lume/sched.h>
+#include <lume/kprintf.h>
+#include <arch/cpu.h>
+
+void WaitQueue::sleep(Spinlock* external_lock)
+{
+    TaskControlBlock* curr = current_task();
+    if (!curr) {
+        if (external_lock) external_lock->release();
+        return;
+    }
+
+    {
+        LockGuard guard(lock_);
+
+        /* Mark task as sleeping */
+        curr->state = TaskState::Sleeping;
+
+        /* Remove from RunQueue (sched_dequeue acquires its own lock) */
+        /* We do NOT call sched_dequeue here because schedule() handles
+         * the put_prev_task logic when state != Running. */
+
+        /* Link into wait queue tail */
+        list_node* node = &curr->run_link;
+        node->prev = head_.prev;
+        node->next = &head_;
+        head_.prev->next = node;
+        head_.prev = node;
+    }
+
+    if (external_lock) {
+        external_lock->release();
+    }
+
+    /* Context switch away — will return here when woken */
+    schedule();
+}
+
+bool WaitQueue::wake_one()
+{
+    LockGuard guard(lock_);
+
+    if (head_.is_empty())
+        return false;
+
+    /* Dequeue the first (oldest) waiter */
+    list_node* node = head_.next;
+    node->prev->next = node->next;
+    node->next->prev = node->prev;
+    node->init();
+
+    TaskControlBlock* task =
+        list_entry<TaskControlBlock, &TaskControlBlock::run_link>(node);
+
+    task->state = TaskState::Runnable;
+    sched_enqueue(task);
+
+    return true;
+}
+
+int WaitQueue::wake_all()
+{
+    LockGuard guard(lock_);
+
+    int count = 0;
+    while (!head_.is_empty()) {
+        list_node* node = head_.next;
+        node->prev->next = node->next;
+        node->next->prev = node->prev;
+        node->init();
+
+        TaskControlBlock* task =
+            list_entry<TaskControlBlock, &TaskControlBlock::run_link>(node);
+
+        task->state = TaskState::Runnable;
+        sched_enqueue(task);
+        count++;
+    }
+
+    return count;
+}