kernel::queue

Kernel-side queue waiter management (plan W4).

When a task blocks on a full queue (send) or empty queue (recv), it is recorded in a per-queue waiter list keyed by the queue’s address. A successful send wakes one receiver; a successful receive wakes one sender. Finite timeouts are handled cooperatively with the scheduler: a timed-out task is woken by the tick and discovers the timeout because it is still in the waiter list on resume (block_* returns false).

All waiter-table access happens under one lock, QUEUE_WAITERS.

Structs

Wait

struct Wait {
    pub addr: usize,
    pub send: bool,
    pub timeout_ms: u32,
    pub since: u64,
}

What a task is blocked on, and since when.

Every blocking primitive the blob is given — queue send and receive, semaphore take, mutex lock — funnels through [block_send] and [block_recv], so recording here covers all four. It exists because a wait that is never signalled looks exactly like a dead system from outside: the task is simply not runnable, and nothing says which object it is holding out for.

Implements: Clone, Copy, Debug, Eq, PartialEq, StructuralPartialEq

Functions

block_recv

fn block_recv(q_addr: usize, timeout_ms: u32) -> bool

Block the caller waiting to receive on an empty queue. See [block_send].

block_send

fn block_send(q_addr: usize, timeout_ms: u32) -> bool

Block the caller waiting to send on a full queue. Returns true if woken by an opening slot (caller should retry), false on timeout, if the waiter table is full, or (item 11) if called from interrupt context — blocking there would suspend the interrupted task, not the caller, wedging it forever, so we refuse instead.

consume_or_block

fn consume_or_block<impl FnOnce() -> bool>(q_addr: usize, timeout_ms: u32, ready: impl FnOnce) -> bool

Test a resource and enrol as a waiter without a gap between the two.

The bug this exists to remove

Every blocking primitive here used to be written as “try, and if that fails, block”: Semaphore::take called try_take, which took its own look at the count and released whatever it held, and only then called [block_recv] to join the waiter list. A producer landing in that gap makes the resource available and wakes nobody, because there is nobody enrolled yet — and the consumer then blocks on a resource that is already there. With a finite timeout that is a stall; with an infinite one, which is what the radio driver asks for, it never ends.

It is not theoretical: the driver’s start-up hung on a semaphore that had been given exactly once and taken exactly once.

ready runs while this holds the scheduler and the waiter table, which is the same pair the wake path takes and in the same order. So a producer cannot run between the test and the enrolment: it is waiting for one of these two locks.

Returns true when ready claimed the resource — the caller has it and did not block. false means it blocked and has since been woken or timed out, and should test again.

ready must not take either lock itself, and must not block. It is a count decrement or a byte copy, nothing more.

consume_or_block_waking_sender

fn consume_or_block_waking_sender<impl FnOnce() -> bool>(q_addr: usize, timeout_ms: u32, ready: impl FnOnce) -> bool

As [consume_or_block], and wake one sender when the test succeeds.

A queue receive frees a slot, so whoever was waiting for space should be told — under the same locks, for the same reason.

forget_task

fn forget_task(id: u32)

Remove a task from every waiter list it appears in.

Called when a task is deleted. Without this, a deleted task’s id stays listed and a later wake_one_* unblocks it — by which time the slot may belong to a different task, which is then woken from a wait it never entered. The bug that produces is a task returning from recv with nothing received, arbitrarily far from the delete that caused it.

is_waiting_anywhere

fn is_waiting_anywhere(id: u32) -> bool

Whether a task is listed as waiting anywhere. Test support for [forget_task].

produce_and_wake

fn produce_and_wake<impl FnOnce() -> bool>(q_addr: usize, produce: impl FnOnce) -> bool

Make a resource available and wake one waiter, with no gap between.

The producer half of [consume_or_block]. produce runs under the same two locks, so a consumer testing the resource either sees it before this runs — and enrols — or after, and takes it. There is no third case.

produce returns whether it actually made anything available; a semaphore already at its ceiling has not, and waking for it would be a spurious wakeup rather than a delivery.

produce_or_block

fn produce_or_block<impl FnOnce() -> bool>(q_addr: usize, timeout_ms: u32, produce: impl FnOnce) -> bool

The producer’s mirror: try to make something available, and if that fails join the queue of those waiting for room.

On success one receiver is woken, because an item has appeared.

retry_deadline

fn retry_deadline(timeout_ms: u32) -> u64

Absolute deadline for a retry loop, on the same clock block_send and block_recv arm their timeouts against. 0 means “forever”.

A retry loop must not pass its original timeout_ms to block_* each time round: deadline_for computes a fresh now + timeout_ms on every call, so re-passing it re-arms the full wait, and under repeated spurious wakeups the total wait is unbounded even though the caller asked for a bounded one. api::queue learned this first (item 9); the pair lives here so that the next caller inherits the fix rather than the bug.

retry_remaining

fn retry_remaining(deadline: u64) -> Option<u32>

Time left before deadline, to pass to the next block_* call. None means it has passed and the caller should report a timeout.

waiting_on

fn waiting_on(task: u32) -> Option<Wait>

What task is blocked on, if it is blocked in a queue primitive.

Stale by design in one direction only: it is cleared on the way out, so a task that is running reports None, and a task that reports a wait really is in one.

References: Wait

wake_one_receiver

fn wake_one_receiver(q_addr: usize)

Wake one receiver after a successful send (a message is now available).

wake_one_sender

fn wake_one_sender(q_addr: usize)

Wake one sender after a successful receive (a slot is now free).