Skip to main content

rusty_rtos_kernel_core/
kernel.rs

1//! The scheduler: `tasks.c` and `queue.c` as a state machine over indices.
2//!
3//! Every public function here is a FreeRTOS API function, and its body
4//! follows the C body statement for statement — including **where the
5//! critical sections open and close**, because on the sim that is where
6//! time passes (`ORACLES.md`, sim contract v1, rule 3), and including where
7//! the `trace*` macros fire, because the order of those lines is the gate.
8//!
9//! The subtlety that costs a diff if you miss it: FreeRTOS yields from
10//! *inside* the critical section in `vTaskResume`, `vTaskPrioritySet`,
11//! `xTaskResumeAll` and the queue calls, and from *outside* it in
12//! `vTaskSuspend` and `vTaskDelay`. Since `portYIELD()` on the Posix port
13//! is itself a critical section, an inside yield nests (and counts one
14//! outermost exit) where an outside yield counts two. Each site below says
15//! which it is.
16//!
17//! Where the C has a `configASSERT`, this has an [`Error`]: the C kernel
18//! stops the world on a bad handle, and the whole point of the remake is
19//! that we do not.
20
21use core::marker::PhantomData;
22
23use rusty_rtos_core::arena::Arena;
24use rusty_rtos_core::config::Config;
25use core::num::NonZeroU64;
26
27use rusty_rtos_core::error::{Error, Result};
28use rusty_rtos_core::handle::{
29    EventGroup as EventGroupKind, EventGroupHandle, Queue as QueueKind, QueueHandle,
30    StreamBuffer as StreamKind, StreamBufferHandle, Task as TaskKind, TaskHandle,
31    Timer as TimerKind, TimerHandle,
32};
33use rusty_rtos_core::hooks::TickHook;
34use rusty_rtos_core::isr::Woken;
35use rusty_rtos_core::list::{ItemId, ListId, Lists};
36use rusty_rtos_core::port::Port;
37use rusty_rtos_core::priority::Priority;
38use rusty_rtos_core::tick::TickWidth;
39use rusty_rtos_core::trace::{Event, Trace};
40
41use crate::events::EventGroup;
42use crate::name::Name;
43use crate::queue::Queue;
44use crate::queue::Wait;
45use crate::stream::StreamBuffer;
46use crate::timer::{Message, Timer};
47use crate::{OVERHEAD_LISTS, list_slots_for, lists_for};
48
49/// How many times [`Kernel::trace_failure_or_owe`] has been entered.
50///
51/// A reachability anchor, not a measurement. Every row of
52/// `riscv32-qemu-tick-work` read **zero** here until the failure rows were
53/// added, which is why a change to the `OwedTrace` machinery measured as pure
54/// code layout. It is behind its own feature because the `fetch_add` sits
55/// INSIDE the measured bracket, so a build that quotes instruction counts must
56/// not carry it.
57#[cfg(feature = "census")]
58pub static CENSUS_OWE: core::sync::atomic::AtomicU32 = core::sync::atomic::AtomicU32::new(0);
59
60/// A trace line owed by a task that was switched out before it could
61/// emit one. Only the queue failure paths can owe one: they are the only
62/// places FreeRTOS traces *after* leaving a critical section.
63/// Why `vTaskSwitchContext` could not choose a task to run.
64///
65/// # Law 3: no silent failures
66///
67/// Every variant here was, until 2026-09-11, a bare `return` — the scheduler
68/// declining to switch and saying nothing. Three of them are impossible in a
69/// healthy kernel and the fourth is what the C asserts on
70/// (`configASSERT( uxTopPriority )`), so reaching any of them means an
71/// invariant has already broken somewhere else.
72///
73/// They cost a multi-flash hardware hunt on the day the Xtensa port first
74/// ran a stacked task: every ready list had emptied, the kernel kept
75/// quietly running whoever was current, and nothing said so. A counter and
76/// a reason turn that into one printed line.
77#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
78pub enum Stall {
79    /// The scheduler chose normally.
80    #[default]
81    None,
82    /// No ready task at ANY priority. The idle task keeps priority 0
83    /// non-empty, so reaching this means the idle task is gone — which is
84    /// exactly what `configASSERT( uxTopPriority )` fires on.
85    NoReadyTask,
86    /// A ready list refused to answer at all.
87    ListError,
88    /// The chosen priority's list had nothing to rotate to, having just
89    /// reported itself non-empty.
90    EmptyRotation,
91    /// The chosen list item named no live task.
92    UnknownTask,
93}
94
95#[derive(Debug, Clone, Copy, PartialEq, Eq)]
96pub(crate) enum OwedTrace {
97    /// Nothing owed.
98    None,
99    /// `traceQUEUE_SEND_FAILED`.
100    SendFailed(QueueHandle),
101    /// `traceQUEUE_RECEIVE_FAILED`.
102    ReceiveFailed(QueueHandle),
103    /// `traceTIMER_COMMAND_SEND`, which the C runs on the line *after*
104    /// `xQueueSendToBack` — so a send that made the daemon ready traces
105    /// only once this task has the CPU back.
106    TimerCommandSend {
107        timer: TimerHandle,
108        name: Name,
109        command: i32,
110        value: u64,
111    },
112    /// `traceSTREAM_BUFFER_CREATE`, which the C runs after the
113    /// `pvPortMalloc` that made the buffer.
114    ///
115    /// `heap_4` brackets that malloc with `vTaskSuspendAll` /
116    /// `xTaskResumeAll`, so a tick can land on its exit -- and the C's
117    /// thread then stops inside the allocator, with the trace still ahead
118    /// of it. Emitting it anyway puts the line in another task's run of the
119    /// trace. `StreamBufferDemo`'s echo client showed it at tick 429, one
120    /// line early and a whole task's work out of place.
121    StreamBufferCreate {
122        buffer: StreamBufferHandle,
123        is_message_buffer: bool,
124    },
125    /// `traceEVENT_GROUP_WAIT_BITS_END`, which the C runs after the
126    /// `xTaskResumeAll` that ends the wait — so a resume that switched away
127    /// traces once this task has the CPU back.
128    EventGroupWaitBitsEnd {
129        group: EventGroupHandle,
130        bits: u32,
131        timed_out: bool,
132    },
133    /// `prvAddNewTaskToReadyList`, the second half of `xTaskCreate`.
134    ///
135    /// A create costs three outermost exits before it reaches this — two
136    /// `pvPortMalloc`s and the port's `pthread_create` section — and a tick
137    /// can land on any of them. The C is a real thread, so it simply stops
138    /// there and the new task is not on a ready list until the creator runs
139    /// again. This is that pause, and it is the only owed item that is not
140    /// purely a trace line: it carries the ready-list insertion too.
141    AddNewTaskToReadyList { task: TaskHandle, priority: u8 },
142}
143
144/// `eTaskState`: what a task is doing, derived from the list it is in
145/// exactly as `eTaskGetState` derives it.
146#[derive(Debug, Clone, Copy, PartialEq, Eq)]
147pub enum TaskState {
148    /// The task `current` names.
149    Running,
150    /// On a ready list.
151    Ready,
152    /// On a delayed list, or on an event list with a timeout.
153    Blocked,
154    /// On the suspended list with no event pending.
155    Suspended,
156    /// The handle names no live task.
157    Deleted,
158}
159
160/// Where a preempted queue call has to start again.
161///
162/// A queue call has SEVERAL critical-section exits that can release a tick
163/// and switch the caller away, and the C's thread resumes below whichever
164/// one it stopped at. One marker is not enough to say which.
165#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
166pub(crate) enum QueueResume {
167    /// Nothing to resume; enter at the top.
168    #[default]
169    No,
170    /// Below the section that samples the queue, in the caller.
171    BelowSample,
172    /// Below the `xTaskResumeAll` of the TIMED-OUT branch, which is the one
173    /// `IntQueue` reaches at tick 16,260: the tick pended inside the
174    /// scheduler suspension is replayed there, and replaying it switches
175    /// the caller away with `prvIsQueueEmpty` still to run.
176    BelowTimedOutResume,
177}
178
179/// One task control block: the C `TCB_t` minus everything that is a
180/// pointer. No stack, no TLS, no `pxTopOfStack`.
181#[derive(Debug, Clone, Copy, Default)]
182pub(crate) struct Tcb {
183    name: Name,
184    /// `uxPriority`, the possibly-inherited one the scheduler sorts by.
185    priority: u8,
186    /// `uxBasePriority`, what the task asked for.
187    base_priority: u8,
188    /// `uxMutexesHeld`: how many mutexes this task holds, which is what
189    /// decides whether giving one back may drop an inherited priority.
190    mutexes_held: u32,
191    /// The locals a blocking queue call keeps on the C stack across a
192    /// block. This kernel has no stack, so they live here — see
193    /// [`crate::queue`].
194    wait: WaitFrame,
195    /// `ulNotifiedValue[]`.
196    notified: [u32; MAX_NOTIFICATION_ENTRIES],
197    /// `ucNotifyState[]`.
198    notify_state: [NotifyState; MAX_NOTIFICATION_ENTRIES],
199    /// Whether a stream-buffer call this task made was preempted at the
200    /// critical-section exit that samples the buffer, and must resume
201    /// *after* that exit rather than repeat it.
202    stream_resume: bool,
203    /// Where a preempted queue call resumes. See [`QueueResume`].
204    ///
205    /// `xQueueGenericSend` and `xQueueReceive` exit their sampling section
206    /// before suspending the scheduler to block, and THAT exit can release
207    /// a tick which switches the caller away. The C's thread stops inside
208    /// the exit; everything below it -- `traceBLOCKING_ON_QUEUE_SEND` and
209    /// `vTaskPlaceOnEventList` -- runs when the task is next scheduled, and
210    /// so names the right task. Without this marker the trace attributes
211    /// the block to whoever the tick switched TO, which `IntQueue` catches
212    /// at tick 5 and no other scenario reaches.
213    queue_resume: QueueResume,
214    /// Whether a blocking `xStreamBufferSend` has already run its
215    /// `vTaskSetTimeOutState`. See [`Kernel::take_stream_timed`].
216    stream_timed: bool,
217    /// Whether a stream-buffer call's notify wait has already finished.
218    /// See [`Kernel::take_stream_waited`].
219    stream_waited: bool,
220    /// The stack local that exit produced — `xBytesAvailable` on a receive,
221    /// `xSpace` on a send — kept because the frame it belonged to is gone.
222    stream_local: usize,
223    /// Whether this task has already blocked inside the notification wait
224    /// it is in. The C blocks inside `xTaskGenericNotifyWait`; a kernel
225    /// with no stacks returns `Blocked` and is called again, so it needs to
226    /// know the second call is a resumption rather than a fresh wait.
227    notify_blocked: bool,
228    /// The same, for the event-group wait this task is inside. Those two
229    /// functions have no retry loop — the C blocks once and then reads the
230    /// event item value — so the second call has to know it is the far side
231    /// of the switch and not a fresh wait.
232    event_blocked: bool,
233    /// Padding that rounds `Slot<Tcb>` up to a POWER OF TWO (128 bytes), so
234    /// `index * size_of::<Slot<Tcb>>()` is a shift and not a multiply.
235    ///
236    /// `bench/kernel-ram` pins the stride at 128 and `bench/kernel-flash` pins
237    /// `mul` at 0; without this the stride is 92 and every TCB resolve pays a
238    /// `mul`. It is a deliberate flash-for-RAM trade: 254 bytes of flash
239    /// against 36 bytes of RAM per task, so it pays below roughly eight tasks
240    /// and is the owner's call above that.
241    _stride_pad: [u32; STRIDE_PAD_WORDS],
242}
243
244/// How many `u32`s of [`Tcb::_stride_pad`] it takes to make `Slot<Tcb>` a power
245/// of two, which is what keeps `index * stride` a shift instead of a multiply.
246///
247/// It differs by pointer width because the fields it pads out do: `usize` and
248/// the `Name` alignment (see [`crate::name::Name`], aligned to eight on a
249/// 64-bit host only) both change size. Nine words gives 128 bytes on a 32-bit
250/// target -- the number `bench/kernel-ram` pins and `bench/kernel-flash`'s
251/// `mul = 0` depends on -- and four gives 128 on the host.
252///
253/// Before this was split, the host slot was 144 bytes and every TCB index cost
254/// a `lea`+`shl` where a power-of-two stride costs one `shl`.
255#[cfg(target_pointer_width = "64")]
256pub(crate) const STRIDE_PAD_WORDS: usize = 4;
257
258/// See the 64-bit case above; nine words is what makes an rv32 `Slot<Tcb>` 128
259/// bytes, and that number is pinned by two benches.
260#[cfg(not(target_pointer_width = "64"))]
261pub(crate) const STRIDE_PAD_WORDS: usize = 9;
262
263/// How many notification slots a task has room for.
264///
265/// The C sizes its arrays from `configTASK_NOTIFICATION_ARRAY_ENTRIES`
266/// directly. A `Config` is a type here and stable Rust cannot size an array
267/// from one of its associated consts, so the arrays are the largest a
268/// configuration may ask for and [`Config::validate`] refuses more. The
269/// cost is a few bytes per task per unused slot; the alternative was a
270/// tenth const generic on every kernel type.
271pub const MAX_NOTIFICATION_ENTRIES: usize = 4;
272
273/// `ucNotifyState[]`: what a task's notification slot is doing.
274#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
275pub enum NotifyState {
276    /// `taskNOT_WAITING_NOTIFICATION`.
277    #[default]
278    NotWaiting,
279    /// `taskWAITING_NOTIFICATION`.
280    Waiting,
281    /// `taskNOTIFICATION_RECEIVED`.
282    Received,
283}
284
285/// `eNotifyAction`: what a notification does to the value already there.
286#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
287pub enum NotifyAction {
288    /// `eNoAction`: wake the task, leave the value alone.
289    #[default]
290    None,
291    /// `eSetBits`.
292    SetBits,
293    /// `eIncrement`.
294    Increment,
295    /// `eSetValueWithOverwrite`.
296    Overwrite,
297    /// `eSetValueWithoutOverwrite`: fails if one is already pending.
298    NoOverwrite,
299}
300
301/// What `xQueueGenericSend` and friends keep between passes of their
302/// `for(;;)`: the queue being waited on, the ticks left, and the timeout
303/// bookkeeping (`TimeOut_t`).
304#[derive(Debug, Clone, Copy, Default)]
305struct WaitFrame {
306    /// The queue this task is part-way through a blocking call on;
307    /// `TaskHandle::NULL`-equivalent when there is none.
308    queue: QueueHandle,
309    /// `xTicksToWait`, decremented by each `xTaskCheckForTimeOut`.
310    ///
311    /// All three are SPLIT (`timer::Split64`), so a `WaitFrame` does not align
312    /// a `Tcb` to eight. An arena slot pays its value's alignment as padding,
313    /// and `Tcb` is one per task.
314    ticks: crate::timer::Split64,
315    /// `xTimeOut.xTimeOnEntering`.
316    entering: crate::timer::Split64,
317    /// `xTimeOut.xOverflowCount`.
318    /// Counted in a `u32`: it advances once per delayed-list swap, so four
319    /// billion of them is not a bound anything reaches, and a `u64` here was
320    /// two instructions an operation on rv32.
321    overflows: u32,
322    /// `xEntryTimeSet`.
323    entry_set: bool,
324    /// `xInheritanceOccurred`.
325    inherited: bool,
326}
327
328/// What [`Kernel::start_scheduler`] created, so a runner can attach bodies.
329#[derive(Debug, Clone, Copy)]
330pub struct StartHandles {
331    /// The idle task.
332    pub idle: TaskHandle,
333    /// The timer service task.
334    pub timer: TaskHandle,
335    /// The timer command queue.
336    pub timer_queue: QueueHandle,
337}
338
339/// The scheduler.
340///
341/// `TASKS`, `ITEMS`, `LISTS`, `QUEUES`, `SLOTS`, `BUFFERS` and `BYTES` are
342/// the geometry: how many tasks, list items, lists, queues, queue item
343/// slots, stream buffers, and stream-buffer bytes this kernel has room
344/// for. See the crate docs and [`items_for`] / [`lists_for`].
345/// [`Kernel::new`] refuses a geometry that does not add up.
346#[repr(C)]
347pub struct Kernel<
348    C: Config,
349    P: Port,
350    T: Trace,
351    H,
352    const TASKS: usize,
353    const ITEMS: usize,
354    const LISTS: usize,
355    const QUEUES: usize,
356    const SLOTS: usize,
357    const BUFFERS: usize,
358    const BYTES: usize,
359    const TIMERS: usize,
360    const GROUPS: usize,
361    const TIMER_CMDS: usize,
362> {
363    /// `xTickCount`, masked to the configuration's tick width.
364    pub(crate) tick: u64,
365    /// `xPendedTicks`.
366    /// Counted in a `u32`, for the reason `overflows` is: it counts ticks
367    /// that arrived while the scheduler was suspended, which a suspension
368    /// long enough to overflow four billion would have to outlive.
369    pended_ticks: u32,
370    /// `xNextTaskUnblockTime`.
371    next_unblock_time: u64,
372    /// `xNumOfOverflows`.
373    overflows: u32,
374    /// `xLastTime` in `prvSampleTimeNow`.
375    pub(crate) timer_last_time: u64,
376    /// `pxCurrentTCB`.
377    pub(crate) current: TaskHandle,
378    /// `uxSchedulerSuspended`.
379    suspended_depth: u32,
380    /// `uxCurrentNumberOfTasks`.
381    task_count: usize,
382    /// How many times the scheduler could not choose a task, and why the
383    /// FIRST time. See [`Stall`].
384    stalls: u32,
385    pub(crate) timer_message_next: usize,
386    pub(crate) bytes_used: usize,
387    pub(crate) free_count: usize,
388    pub(crate) free_slot_count: usize,
389    pub(crate) slots_used: usize,
390    /// The task whose abandoned frame is running right now, if any.
391    /// `TaskHandle::NULL` for "nobody", not `Option<TaskHandle>`.
392    ///
393    /// A `Handle` is two `u16`s with no niche, so the `Option` was eight bytes
394    /// and a real discriminant — and `resume_pending` tests this field on
395    /// every step the runner takes, which is the most-called entry in the
396    /// kernel. `NULL` is already the sentinel (`generation == 0`), so the
397    /// representation carries the fact the discriminant was carrying.
398    unwinding: TaskHandle,
399    /// A task that deleted ITSELF and whose slot the idle task has not
400    /// reclaimed yet — the C's `xTasksWaitingTermination`, which only ever
401    /// holds the running task, because any other task is freed on the spot.
402    ///
403    /// One slot is enough, and that is a property rather than a guess: a
404    /// self-deleting task is off every ready list and yields immediately, so
405    /// a second self-delete cannot happen until a switch has occurred, and
406    /// the switch is where this is reaped.
407    awaiting_reap: TaskHandle,
408    /// `xTimerQueue`.
409    pub(crate) timer_queue: QueueHandle,
410    /// How many tasks are parked at a queue call's sampling exit.
411    ///
412    /// A summary, so that [`Kernel::take_queue_resume`] — which runs at the
413    /// top of every queue send and every queue receive — can answer "nothing
414    /// to resume" from one field instead of resolving the caller's TCB out of
415    /// the arena. Only the three sites that park a task raise it, and only a
416    /// take that finds a slot set lowers it, so it counts exactly the slots
417    /// that are not `QueueResume::No`.
418    queue_resumes: u16,
419    /// How many tasks are parked inside an event-group wait, for the same
420    /// reason [`Kernel::queue_resumes`] exists: `take_event_resume` runs at
421    /// the top of every `event_group_wait_bits` and every `event_group_sync`,
422    /// and on all but the parked few the answer is no.
423    event_resumes: u16,
424    /// `uxTopReadyPriority`.
425    top_ready_priority: u8,
426    /// The running task's scheduling priority, kept beside `current`.
427    ///
428    /// The C reads `pxCurrentTCB->uxPriority`: one pointer dereference,
429    /// because the pointer IS the task. A handle is not a pointer, so the
430    /// same read went through `Arena::resolve` — a bounds check, a generation
431    /// compare and an `Option` — **every tick**, on the one handle the kernel
432    /// itself maintains and cannot have wrong.
433    ///
434    /// Measured: that resolve was **43 of the tick's 56 instructions, 77 %**.
435    /// Stubbing it to a constant took `increment_tick` from 56 to 13 against
436    /// the C's 15 — from 3.73x against us to 0.87x. This field is that
437    /// finding, done correctly.
438    ///
439    /// **It is written in exactly two places** — [`Self::set_current`] and
440    /// [`Self::set_task_priority`] — so that a call site cannot forget it.
441    /// `current_priority` debug-asserts it against the resolved value, so the
442    /// kernel's own tests and the conformance corpus fail loudly if it ever
443    /// drifts.
444    current_priority: u8,
445    /// `xSchedulerRunning`.
446    running: bool,
447    /// `xYieldPendings[0]`.
448    yield_pending: bool,
449    /// Which of the two delayed lists is `pxDelayedTaskList` right now.
450    delayed_swapped: bool,
451    /// Which of the two timer lists is `pxCurrentTimerList` right now.
452    pub(crate) timers_swapped: bool,
453    first_stall: Stall,
454
455    pub(crate) port: P,
456    pub(crate) trace: T,
457    /// `vApplicationTickHook`, held by value so it can borrow the kernel.
458    pub(crate) tick_hook: H,
459    /// How many outermost critical-section exits a task owes the clock.
460    ///
461    /// This is `uxSavedCriticalNesting` in the Posix port's
462    /// `prvSwitchThread` and then some. A thread stops at the switch; a
463    /// stackless call does not, so the abandoned frame runs on — closing
464    /// the sections it had open and, on some paths, opening one more. The
465    /// port tallies every exit that frame makes instead of counting it as
466    /// sim time, and the tally is paid here when the task runs again. That
467    /// is what puts a sim tick where the C one lands.
468    /// Five per-task booleans, one bit each, in ONE array.
469    ///
470    /// They were five `[bool; TASKS]`. Each one is a separate base address, so
471    /// a function touching two of them — and the owed body touches three —
472    /// computed two bases and did two loads to read two bits that now share a
473    /// byte. Packed they cost one byte a task instead of five, and one base
474    /// instead of five across the whole kernel.
475    flags: [u8; TASKS],
476    /// `started`, kept OUT of `flags` on purpose.
477    ///
478    /// It is the only one of the five that `switch_context` reads — through
479    /// `hand_over`, on every switch — and packing it cost the selection row
480    /// one instruction for the mask. The other four are never on that path,
481    /// so they stay packed. Per-call-site, not per-idea.
482    started: [bool; TASKS],
483    /// `owes_anything`, kept OUT of `flags` for the reason `started` is: it is
484    /// the single most-read byte in the kernel — `resume_pending` tests it
485    /// before every step the runner takes — and packing it cost that row three
486    /// instructions for the mask. Per call site, not per idea.
487    owes_anything: [bool; TASKS],
488    /// `delay_aborted`, kept OUT of `flags`: `check_for_timeout` reads it on
489    /// every pass of every blocking call.
490    delay_aborted: [bool; TASKS],
491    pub(crate) lists: Lists<ITEMS, LISTS>,
492    pub(crate) tcbs: Arena<TaskKind, Tcb, TASKS>,
493    owed_exits: [u32; TASKS],
494    /// A trace line a task owes from a call it was switched out of.
495    ///
496    /// `xQueueReceive`'s failure path is `taskEXIT_CRITICAL();
497    /// traceQUEUE_RECEIVE_FAILED( pxQueue ); return errQUEUE_EMPTY;` — and
498    /// if the tick that the exit released switches the task away, those two
499    /// lines sit on a stack that is not running. The C emits the trace when
500    /// the task resumes, so this kernel does too.
501    owed_trace: [OwedTrace; TASKS],
502    pub(crate) queues: Arena<QueueKind, Queue, QUEUES>,
503    pub(crate) timers: Arena<TimerKind, Timer, TIMERS>,
504    pub(crate) groups: Arena<EventGroupKind, EventGroup, GROUPS>,
505    pub(crate) buffers: Arena<StreamKind, StreamBuffer, BUFFERS>,
506    /// Blocks of the byte arena that a deleted stream buffer gave back,
507    /// as `(base, length)`, kept sorted and coalesced.
508    ///
509    /// This is the one allocator in the kernel, and it exists because the
510    /// C's stream buffers are heap objects: `MessageBufferDemo`'s echo
511    /// server creates one and deletes it again on every loop, and a bump
512    /// allocator would run out in a few hundred ticks. At most `BUFFERS`
513    /// buffers can be alive, so at most `BUFFERS` holes can exist between
514    /// them, which is why the list is that long and cannot overflow.
515    pub(crate) free_blocks: [(usize, usize); BUFFERS],
516    /// Extents of the SLOT arena that a deleted queue gave back, as
517    /// `(base, length)`, coalesced the same way `free_blocks` is.
518    ///
519    /// The byte arena has had this since `MessageBufferDemo` needed it. The
520    /// slot arena did not, so `queue_delete` returned the descriptor while
521    /// the storage stayed spent and a create/delete loop exhausted `SLOTS`
522    /// permanently — found through `AbortDelay` on 2026-09-21, after nine
523    /// hypotheses and eight refutations, because the descriptor arena works
524    /// perfectly and that is where everyone looked.
525    ///
526    /// At most `QUEUES` queues are alive, so at most `QUEUES` holes can sit
527    /// between them and the list cannot overflow.
528    pub(crate) free_slots: [(usize, usize); QUEUES],
529    /// The ring of `DaemonTaskMessage_t`s the timer queue carries indices
530    /// into. It is exactly as long as the queue, so a message can only be
531    /// overwritten once the queue has already refused to hold its index.
532    /// The timer daemon's command mailbox, sized by the configuration.
533    ///
534    /// It used to be `[Message; MAX_TIMER_COMMANDS]` — a hardcoded 32 — while
535    /// `Config::TIMER_QUEUE_LENGTH` already said how many the configuration
536    /// wanted and defaulted to ten. Because it scaled with **nothing**, it was
537    /// a fixed 768 bytes at every geometry, which is **39 % of a two-task
538    /// kernel's entire static footprint** and 31 % of a four-task one.
539    ///
540    /// `TIMER_CMDS` is that number, checked against the config in
541    /// [`Self::with_tick_hook`] exactly as `ITEMS` and `LISTS` are.
542    pub(crate) timer_messages: [Message; TIMER_CMDS],
543    pub(crate) slots: [u64; SLOTS],
544    pub(crate) bytes: [u8; BYTES],
545    _config: PhantomData<C>,
546}
547
548impl<
549    C: Config,
550    P: Port,
551    T: Trace,
552    H,
553    const TASKS: usize,
554    const ITEMS: usize,
555    const LISTS: usize,
556    const QUEUES: usize,
557    const SLOTS: usize,
558    const BUFFERS: usize,
559    const BYTES: usize,
560    const TIMERS: usize,
561    const GROUPS: usize,
562    const TIMER_CMDS: usize,
563> Kernel<C, P, T, H, TASKS, ITEMS, LISTS, QUEUES, SLOTS, BUFFERS, BYTES, TIMERS, GROUPS, TIMER_CMDS>
564where
565    H: TickHook<Self>,
566{
567    /// `portMAX_DELAY` at this configuration's tick width.
568    pub const MAX_DELAY: u64 = <C::Tick as TickWidth>::MAX;
569
570    // ------------------------------------------------------- footprint --
571
572    /// The kernel's own static size, and the same number `size_of` gives.
573    ///
574    /// The consts below decompose it. They exist because a footprint you
575    /// cannot decompose to the byte is a footprint you cannot optimise: the
576    /// arena fields are `pub(crate)` and their types are private, so nothing
577    /// outside this crate can measure them, and a decomposition assembled
578    /// from per-dimension SLOPES is not one — `ITEMS` and `LISTS` are derived
579    /// from `TASKS`, `QUEUES` and `GROUPS`, so the function is not linear and
580    /// slopes do not sum to the total. That was tried; it produced 696 bytes
581    /// of nonsense.
582    ///
583    /// Every one is `size_of` on whatever target this is compiled for, which
584    /// is the only place the number means anything: a host `usize` is eight
585    /// bytes and rv32's is four.
586    ///
587    /// [`FOOTPRINT_ACCOUNTED`](Self::FOOTPRINT_ACCOUNTED) sums them, and the
588    /// difference from [`FOOTPRINT`](Self::FOOTPRINT) is padding plus the
589    /// scalar tail — print both, never one. `bench/kernel-ram` does.
590    pub const FOOTPRINT: usize = core::mem::size_of::<Self>();
591
592    /// The task control blocks.
593    pub const FOOTPRINT_TCBS: usize = core::mem::size_of::<Arena<TaskKind, Tcb, TASKS>>();
594    /// The queue descriptors, and NOT their item storage.
595    pub const FOOTPRINT_QUEUES: usize = core::mem::size_of::<Arena<QueueKind, Queue, QUEUES>>();
596    /// Every intrusive list: ready, delayed, and the per-object waiters.
597    pub const FOOTPRINT_LISTS: usize = core::mem::size_of::<Lists<ITEMS, LISTS>>();
598    /// Queue item storage, as `u64` slots.
599    pub const FOOTPRINT_SLOTS: usize = core::mem::size_of::<[u64; SLOTS]>();
600    /// The stream-buffer descriptors, and NOT their bytes.
601    pub const FOOTPRINT_BUFFERS: usize =
602        core::mem::size_of::<Arena<StreamKind, StreamBuffer, BUFFERS>>();
603    /// The software timers.
604    pub const FOOTPRINT_TIMERS: usize = core::mem::size_of::<Arena<TimerKind, Timer, TIMERS>>();
605    /// The event groups.
606    pub const FOOTPRINT_GROUPS: usize =
607        core::mem::size_of::<Arena<EventGroupKind, EventGroup, GROUPS>>();
608    /// The timer daemon's command mailbox.
609    ///
610    /// It scales with `TIMER_CMDS` now, which the geometry check pins to
611    /// `Config::TIMER_QUEUE_LENGTH`. It used to be a hardcoded 32 and so
612    /// scaled with nothing — a fixed 768 bytes, 39 % of a two-task kernel.
613    /// The line stays separate because that history is worth being able to
614    /// read off a decomposition.
615    pub const FOOTPRINT_TIMER_MESSAGES: usize = core::mem::size_of::<[Message; TIMER_CMDS]>();
616    /// The byte arena, for stream-buffer contents.
617    pub const FOOTPRINT_BYTES: usize = core::mem::size_of::<[u8; BYTES]>();
618    /// The two free lists, over the byte arena and the slot arena.
619    pub const FOOTPRINT_FREE_LISTS: usize = core::mem::size_of::<[(usize, usize); BUFFERS]>()
620        + core::mem::size_of::<[(usize, usize); QUEUES]>();
621
622    /// The seven per-task side arrays, together.
623    ///
624    /// Seven arrays indexed by the same task, five of them `[bool; TASKS]`.
625    /// Whether that wants to be one array of a flags byte is a question this
626    /// number is here to make askable.
627    pub const FOOTPRINT_PER_TASK_SIDE: usize = core::mem::size_of::<[u8; TASKS]>()
628        + core::mem::size_of::<[bool; TASKS]>() * 3
629        + core::mem::size_of::<[OwedTrace; TASKS]>()
630        + core::mem::size_of::<[u32; TASKS]>();
631
632    /// What the lines above account for.
633    ///
634    /// `FOOTPRINT - FOOTPRINT_ACCOUNTED` is the unattributed remainder: the
635    /// scalar tail (`tick`, `current`, the counters) plus whatever padding
636    /// the layout inserts. It was 140 bytes of 6,784 when this was written. A
637    /// remainder that grows is a field somebody added without adding a line
638    /// here.
639    pub const FOOTPRINT_ACCOUNTED: usize = Self::FOOTPRINT_TCBS
640        + Self::FOOTPRINT_QUEUES
641        + Self::FOOTPRINT_LISTS
642        + Self::FOOTPRINT_SLOTS
643        + Self::FOOTPRINT_BUFFERS
644        + Self::FOOTPRINT_TIMERS
645        + Self::FOOTPRINT_GROUPS
646        + Self::FOOTPRINT_TIMER_MESSAGES
647        + Self::FOOTPRINT_BYTES
648        + Self::FOOTPRINT_FREE_LISTS
649        + Self::FOOTPRINT_PER_TASK_SIDE;
650
651    // ------------------------------------------------------------ setup --
652
653    /// A kernel with no tasks, ready for [`Kernel::create_task`].
654    ///
655    /// # Errors
656    /// [`Error::InvalidArgument`] if the configuration is invalid
657    /// ([`Config::validate`]), if the name capacity cannot hold
658    /// `MAX_TASK_NAME_LEN`, or if the const geometry does not match the
659    /// configuration: `ITEMS` must be [`items_for`]`(TASKS)` and `LISTS`
660    /// must be [`lists_for`]`(MAX_PRIORITIES, QUEUES)`.
661    pub fn new(port: P, trace: T) -> Result<Self>
662    where
663        H: Default,
664    {
665        Self::with_tick_hook(port, trace, H::default())
666    }
667
668    /// [`Kernel::new`] with `vApplicationTickHook` installed.
669    ///
670    /// # Errors
671    /// As [`Kernel::new`].
672    pub fn with_tick_hook(port: P, trace: T, tick_hook: H) -> Result<Self> {
673        C::validate()?;
674        if ITEMS != list_slots_for(TASKS, TIMERS, LISTS)
675            || LISTS != lists_for(C::MAX_PRIORITIES, QUEUES, GROUPS)
676            || TASKS == 0
677            || C::MAX_TASK_NAME_LEN > crate::NAME_CAPACITY
678            // The mailbox is a declared dimension now, so a declaration that
679            // disagrees with its own config is refused rather than silently
680            // sized to whichever one the type happened to carry.
681            || TIMER_CMDS != C::TIMER_QUEUE_LENGTH
682        {
683            return Err(Error::InvalidArgument);
684        }
685        Ok(Self {
686            port,
687            trace,
688            tcbs: Arena::new(),
689            queues: Arena::new(),
690            lists: Lists::new(),
691            slots: [0; SLOTS],
692            slots_used: 0,
693            buffers: Arena::new(),
694            timers: Arena::new(),
695            groups: Arena::new(),
696            timer_messages: [Message::default(); TIMER_CMDS],
697            timer_message_next: 0,
698            timers_swapped: false,
699            timer_last_time: 0,
700            timer_queue: QueueHandle::NULL,
701            bytes: [0; BYTES],
702            bytes_used: 0,
703            free_blocks: [(0, 0); BUFFERS],
704            free_count: 0,
705            free_slots: [(0, 0); QUEUES],
706            free_slot_count: 0,
707            current: TaskHandle::NULL,
708            top_ready_priority: 0,
709            current_priority: 0,
710            tick: C::INITIAL_TICK_COUNT,
711            pended_ticks: 0,
712            suspended_depth: 0,
713            running: false,
714            next_unblock_time: Self::MAX_DELAY,
715            yield_pending: false,
716            task_count: 0,
717            stalls: 0,
718            first_stall: Stall::None,
719            awaiting_reap: TaskHandle::NULL,
720            delayed_swapped: false,
721            overflows: 0,
722            flags: [0; TASKS],
723            started: [false; TASKS],
724            owes_anything: [false; TASKS],
725            delay_aborted: [false; TASKS],
726            owed_exits: [0; TASKS],
727            unwinding: TaskHandle::NULL,
728            queue_resumes: 0,
729            event_resumes: 0,
730            tick_hook,
731            owed_trace: [OwedTrace::None; TASKS],
732            _config: PhantomData,
733        })
734    }
735
736    /// The port, for a runner that needs its counters.
737    pub const fn port(&self) -> &P {
738        &self.port
739    }
740
741    /// The trace sink.
742    pub const fn trace(&self) -> &T {
743        &self.trace
744    }
745
746    /// The trace sink, mutably.
747    pub const fn trace_mut(&mut self) -> &mut T {
748        &mut self.trace
749    }
750
751    /// Take the trace sink back when the run is over, so a deliverable can
752    /// flush whatever it was writing to.
753    pub fn into_trace(self) -> T {
754        self.trace
755    }
756
757    /// `xNumOfOverflows`, for a scenario that reports counters.
758    #[must_use]
759    pub const fn overflows(&self) -> u64 {
760        self.overflows as u64
761    }
762
763    // ------------------------------------------------------ list indices --
764
765    // `ListId` is a `u8` and `ItemId` a `u16` (the core's `list`): the
766    // whole scheduler addresses lists and items by small integers, which is
767    // what keeps a TCB free of pointers.
768
769    pub(crate) const fn ready_list(priority: u8) -> ListId {
770        priority
771    }
772
773    const fn delayed_list(&self) -> ListId {
774        if self.delayed_swapped {
775            C::MAX_PRIORITIES.saturating_add(1)
776        } else {
777            C::MAX_PRIORITIES
778        }
779    }
780
781    const fn overflow_delayed_list(&self) -> ListId {
782        if self.delayed_swapped {
783            C::MAX_PRIORITIES
784        } else {
785            C::MAX_PRIORITIES.saturating_add(1)
786        }
787    }
788
789    const fn pending_ready_list() -> ListId {
790        C::MAX_PRIORITIES.saturating_add(2)
791    }
792
793    const fn suspended_list() -> ListId {
794        C::MAX_PRIORITIES.saturating_add(3)
795    }
796
797    /// `xTasksWaitingToSend` of a queue.
798    pub(crate) fn queue_send_list(queue: QueueHandle) -> ListId {
799        let offset = u8::try_from(queue.index().saturating_mul(2)).unwrap_or(u8::MAX);
800        C::MAX_PRIORITIES
801            .saturating_add(u8::try_from(OVERHEAD_LISTS).unwrap_or(u8::MAX))
802            .saturating_add(offset)
803    }
804
805    /// `xTasksWaitingToReceive` of a queue.
806    pub(crate) fn queue_receive_list(queue: QueueHandle) -> ListId {
807        Self::queue_send_list(queue).saturating_add(1)
808    }
809
810    /// A task's `xStateListItem`: the task's own arena index.
811    pub(crate) const fn state_item(task: TaskHandle) -> ItemId {
812        task.index() as u16
813    }
814
815    /// A task's `xEventListItem`: `TASKS` above its state item, so the two
816    /// never collide and either maps back to its task by arithmetic alone.
817    pub(crate) fn event_item(task: TaskHandle) -> ItemId {
818        Self::task_item_base().saturating_add(task.index() as u16)
819    }
820
821    fn task_item_base() -> ItemId {
822        u16::try_from(TASKS).unwrap_or(u16::MAX)
823    }
824
825    fn task_of_state_item(&self, item: ItemId) -> Result<TaskHandle> {
826        self.tcbs.handle_at(item).ok_or(Error::Gone)
827    }
828
829    fn task_of_event_item(&self, item: ItemId) -> Result<TaskHandle> {
830        let index = item
831            .checked_sub(Self::task_item_base())
832            .ok_or(Error::InvalidArgument)?;
833        self.tcbs.handle_at(index).ok_or(Error::Gone)
834    }
835
836    // ----------------------------------------------------------- getters --
837
838    /// `pxCurrentTCB`.
839    #[must_use]
840    pub const fn current(&self) -> TaskHandle {
841        self.current
842    }
843
844    /// `xTaskGetTickCount`.
845    #[must_use]
846    pub const fn tick_count(&self) -> u64 {
847        self.tick
848    }
849
850    /// `xSchedulerRunning`.
851    #[must_use]
852    pub const fn is_running(&self) -> bool {
853        self.running
854    }
855
856    /// `uxCurrentNumberOfTasks`.
857    #[must_use]
858    pub const fn task_count(&self) -> usize {
859        self.task_count
860    }
861
862    /// `uxSchedulerSuspended`, for a stepper reporting why a tick pended.
863    #[must_use]
864    pub const fn scheduler_suspended(&self) -> u32 {
865        self.suspended_depth
866    }
867
868    /// `xPendedTicks`, likewise.
869    #[must_use]
870    pub const fn pended_ticks(&self) -> u64 {
871        self.pended_ticks as u64
872    }
873
874    /// The item ids in `priority`'s ready list, in order, into `out`.
875    ///
876    /// Returns how many were written. The companion to
877    /// [`Kernel::ready_cursor`]: when a ready task is never chosen, the
878    /// cursor says whether the rotation moved and this says what it was
879    /// moving THROUGH.
880    pub fn ready_items(&self, priority: u8, out: &mut [u16]) -> usize {
881        let mut n = 0;
882        for item in self.lists.iter(Self::ready_list(priority)) {
883            let Some(slot) = out.get_mut(n) else {
884                break;
885            };
886            *slot = item;
887            n = n.wrapping_add(1);
888        }
889        n
890    }
891
892    /// Where the round-robin cursor sits in `priority`'s ready list.
893    ///
894    /// A diagnostic, paired with [`Kernel::ready_len`]: a ready task that
895    /// is never chosen is either not in the list the scheduler looks at,
896    /// or the cursor is not moving. These two answer both halves.
897    #[must_use]
898    pub fn ready_cursor(&self, priority: u8) -> u16 {
899        self.lists
900            .cursor_of(Self::ready_list(priority))
901            .unwrap_or(0)
902    }
903
904    /// The live handle in arena slot `index`, if that slot holds a task.
905    ///
906    /// The generation is the point: a bare index names a SLOT, and a slot
907    /// outlives the tasks that occupy it, so an index is not a task. This
908    /// answers the handle, which is.
909    ///
910    /// It exists so a diagnostic can walk every task without knowing any
911    /// of their names -- `task_get_handle` needs the name it is looking
912    /// for, and a crash report is exactly the case where you do not have
913    /// one.
914    #[must_use]
915    pub fn task_at(&self, index: usize) -> Option<TaskHandle> {
916        let index = u16::try_from(index).ok()?;
917        self.tcbs.handle_at(index)
918    }
919
920    /// A task's name.
921    ///
922    /// # Errors
923    /// [`Error::Gone`] for a stale or null handle.
924    pub fn name_of(&self, task: TaskHandle) -> Result<Name> {
925        self.tcbs.resolve(task).map(|t| t.name)
926    }
927
928    /// `uxTaskPriorityGet`. `None` means the current task, as in C.
929    ///
930    /// # Errors
931    /// [`Error::Gone`] for a stale handle.
932    pub fn priority_of(&self, task: Option<TaskHandle>) -> Result<u8> {
933        let h = task.unwrap_or(self.current);
934        self.tcbs.resolve(h).map(|t| t.priority)
935    }
936
937    pub(crate) fn current_priority(&self) -> u8 {
938        // The cache is the whole point; this is the proof it is honest. It
939        // costs nothing in release and fails the kernel's own tests, the
940        // Kani proofs and the conformance corpus the moment a new write to
941        // `current` or to a priority forgets its helper.
942        debug_assert_eq!(
943            self.current_priority,
944            self.priority_of(None).unwrap_or(0),
945            "the cached current priority went stale -- a write to `current` or              to a task's priority bypassed set_current/set_task_priority"
946        );
947        self.current_priority
948    }
949
950    /// Make `task` the running task, keeping [`Self::current_priority`] with
951    /// it, where the caller already knows the priority.
952    ///
953    /// One of the two places that field is written; assigning `self.current`
954    /// directly is what this exists to prevent.
955    ///
956    /// **The priority is a parameter and not resolved here**, because every
957    /// caller already has it. `switch_context`'s search loop finds the highest
958    /// non-empty ready list and takes `next` out of it, so `next`'s priority
959    /// IS that list's index; task creation has it as an argument. Resolving
960    /// the TCB again to learn what the caller just proved cost **9
961    /// instructions on the switch row** — measured, by landing this without
962    /// the parameter and watching `switch_select` go 79 → 88, then 88 → 82
963    /// when it was threaded through.
964    fn set_current_at(&mut self, task: TaskHandle, priority: u8) {
965        self.current = task;
966        self.current_priority = priority;
967    }
968
969    /// Write a task's scheduling priority, keeping [`Self::current_priority`]
970    /// with it when that task is the running one.
971    ///
972    /// The other of the two. Note it is the SCHEDULING priority only:
973    /// `base_priority` does not decide which ready list a task sits on, so it
974    /// is written directly at its call sites.
975    ///
976    /// # Errors
977    /// [`Error::InvalidHandle`] or [`Error::Gone`] for a handle the arena
978    /// refuses, exactly as `resolve_mut` does.
979    fn set_task_priority(&mut self, task: TaskHandle, priority: u8) -> Result<()> {
980        self.tcbs.resolve_mut(task)?.priority = priority;
981        if task == self.current {
982            self.current_priority = priority;
983        }
984        Ok(())
985    }
986
987    /// `uxTaskPriorityGet`: the C API, which takes a critical section.
988    ///
989    /// The distinction matters: on the sim a critical-section exit is where
990    /// time passes, so reading a priority through the API costs a tick
991    /// sixteen calls later, exactly as it does in C
992    /// (`portBASE_TYPE_ENTER_CRITICAL` is `taskENTER_CRITICAL` on the Posix
993    /// port). The kernel's own reads use the field directly, as C's do.
994    ///
995    /// # Errors
996    /// [`Error::Gone`] for a stale handle.
997    pub fn task_priority_get(&mut self, task: Option<TaskHandle>) -> Result<u8> {
998        self.enter_critical();
999        let result = self.priority_of(task);
1000        self.exit_critical();
1001        result
1002    }
1003
1004    /// `eTaskGetState`: the C API, which takes a critical section for any
1005    /// task but the running one.
1006    ///
1007    /// # Errors
1008    /// A list error surfaces as itself.
1009    pub fn task_state_get(&mut self, task: TaskHandle) -> Result<TaskState> {
1010        if task == self.current {
1011            return Ok(TaskState::Running);
1012        }
1013        self.enter_critical();
1014        let result = self.state_of(task);
1015        self.exit_critical();
1016        result
1017    }
1018
1019    /// `eTaskGetState`, derived from the list the task is in.
1020    ///
1021    /// # Errors
1022    /// A list error surfaces as itself.
1023    pub fn state_of(&self, task: TaskHandle) -> Result<TaskState> {
1024        if !self.tcbs.contains(task) {
1025            return Ok(TaskState::Deleted);
1026        }
1027        if task == self.current {
1028            return Ok(TaskState::Running);
1029        }
1030        let Some(list) = self.lists.container(Self::state_item(task))? else {
1031            return Ok(TaskState::Deleted);
1032        };
1033        if list == Self::suspended_list() {
1034            if self.lists.container(Self::event_item(task))?.is_some() {
1035                return Ok(TaskState::Blocked);
1036            }
1037            // A task blocked indefinitely on a notification is in the
1038            // suspended list and on no event list at all, so the C scans
1039            // the notification array before it calls such a task suspended.
1040            // Miss this and a stream buffer's reader looks suspended to
1041            // `eTaskGetState` while it is plainly waiting.
1042            let waiting_notification = self
1043                .tcbs
1044                .resolve(task)
1045                .map(|t| {
1046                    t.notify_state
1047                        .iter()
1048                        .take(C::NOTIFICATION_ARRAY_ENTRIES)
1049                        .any(|s| *s == NotifyState::Waiting)
1050                })
1051                .unwrap_or(false);
1052            return Ok(if waiting_notification {
1053                TaskState::Blocked
1054            } else {
1055                TaskState::Suspended
1056            });
1057        }
1058        if list == self.delayed_list() || list == self.overflow_delayed_list() {
1059            return Ok(TaskState::Blocked);
1060        }
1061        Ok(TaskState::Ready)
1062    }
1063
1064    /// How many tasks sit on a priority's ready list — what the idle task
1065    /// checks before yielding (`configIDLE_SHOULD_YIELD`).
1066    ///
1067    /// # Errors
1068    /// [`Error::InvalidPriority`] for a priority outside the configuration.
1069    pub fn ready_len(&self, priority: u8) -> Result<usize> {
1070        if priority >= C::MAX_PRIORITIES {
1071            return Err(Error::InvalidPriority);
1072        }
1073        self.lists.len(Self::ready_list(priority))
1074    }
1075
1076    /// Record that the scheduler could not choose.
1077    ///
1078    /// Counts every occurrence and keeps the FIRST reason: the first is the
1079    /// diagnosis and the rest are consequences.
1080    #[cold]
1081    #[inline(never)]
1082    fn note_stall(&mut self, why: Stall) {
1083        self.stalls = self.stalls.saturating_add(1);
1084        if self.first_stall == Stall::None {
1085            self.first_stall = why;
1086        }
1087    }
1088
1089    /// How many times the scheduler could not choose a task.
1090    ///
1091    /// **Non-zero means an invariant broke.** A healthy kernel never stalls:
1092    /// the idle task is always ready. A firmware that prints this alongside
1093    /// its own counters turns a hang into a sentence.
1094    #[must_use]
1095    pub const fn stalls(&self) -> u32 {
1096        self.stalls
1097    }
1098
1099    /// Why the scheduler first failed to choose. [`Stall::None`] if it never
1100    /// has.
1101    #[must_use]
1102    pub const fn first_stall(&self) -> Stall {
1103        self.first_stall
1104    }
1105
1106    // ------------------------------------------------------------ tracing --
1107
1108    pub(crate) fn trace_task<F>(&mut self, task: TaskHandle, make: F)
1109    where
1110        F: for<'a> FnOnce(TaskHandle, &'a str) -> Event<'a>,
1111    {
1112        // `tcbs` and `trace` are different fields, so the name can be read
1113        // where it lives rather than copied onto the stack to end a borrow
1114        // that never had to end.
1115        //
1116        // A sink that never reads the name pays for neither the lookup nor
1117        // the UTF-8 validation that turning one into a `&str` costs.
1118        let Self {
1119            tcbs,
1120            trace,
1121            port,
1122            tick,
1123            ..
1124        } = self;
1125        let name = if T::WANTS_NAMES {
1126            tcbs.get(task).map(|t| t.name.as_str()).unwrap_or("")
1127        } else {
1128            ""
1129        };
1130        let tick = *tick;
1131        trace.note_exits(port.exits());
1132        trace.event(tick, make(task, name));
1133    }
1134
1135    pub(crate) fn priority_value(raw: u8) -> Priority {
1136        Priority::new(raw, C::MAX_PRIORITIES).unwrap_or(Priority::IDLE)
1137    }
1138
1139    // --------------------------------------------------- critical section --
1140
1141    /// What `pvPortMalloc` costs in sim time on a heap-backed C kernel:
1142    /// `vTaskSuspendAll()` around the allocation, then `xTaskResumeAll()`,
1143    /// whose critical section is one outermost exit.
1144    ///
1145    /// This kernel allocates nothing, so the call is the whole of it. On a
1146    /// configuration with [`Config::DYNAMIC_ALLOCATION`] off it compiles
1147    /// away to nothing at all.
1148    // Out of line: 12 cold create/delete sites, each otherwise inlining
1149    // suspend_all + resume_all. Worth -46 B, and the Ir cost is nil because
1150    // every caller is a create or a delete.
1151    #[inline(never)]
1152    pub(crate) fn account_for_allocation(&mut self) {
1153        if C::DYNAMIC_ALLOCATION {
1154            self.suspend_all();
1155            let _ = self.resume_all();
1156        }
1157    }
1158
1159    /// `taskENTER_CRITICAL()`.
1160    pub fn enter_critical(&mut self) {
1161        self.port.enter_critical();
1162    }
1163
1164    /// `taskEXIT_CRITICAL()`.
1165    ///
1166    /// On the sim this is where time passes: the port raises a tick on
1167    /// every sixteenth outermost exit and the kernel takes it here, which
1168    /// is exactly where the C kernel's `SIGALRM` handler would have run.
1169    ///
1170    /// NOT in line, though it is three statements called 118,640 times in
1171    /// a 20,000-tick `StreamBufferDemo`. `#[inline(always)]` was measured:
1172    /// it saves that scenario 210,292 and costs `BlockQ` 200,912 and
1173    /// `GenQTest` 280,540, for a net loss of 271,962 over six scenarios.
1174    /// Whatever the hot sites gain, the switch-heavy ones lose more.
1175    pub fn exit_critical(&mut self) {
1176        self.port.exit_critical();
1177        if self.port.take_pending_tick() {
1178            self.tick_on_exit();
1179        }
1180    }
1181
1182    /// The tick as [`Kernel::exit_critical`] reaches it, deliberately out of
1183    /// line.
1184    ///
1185    /// `exit_critical` is inlined into every queue walker and every demo
1186    /// step, and the tick is its rare arm -- 8,000 of 48,000 sends in
1187    /// `khot-ir` raise one, and 38,013 ticks across 18 scenarios in
1188    /// `kernel-ir`. Left in line it put `increment_tick` and
1189    /// `switch_context` inside all of those frames.
1190    ///
1191    /// Taking it out is worth 233,207 on `kernel-ir` and costs the four
1192    /// kernel micro-instruments 9,650 between them, which is about what one
1193    /// extra call layer costs at their call counts.
1194    ///
1195    /// The other half was refuted: `#[inline(always)]` on
1196    /// [`Kernel::tick_from_isr`] itself costs `khot-ir` 178,245 while saving
1197    /// the three lighter instruments 82,642, and stacked on top of this
1198    /// outlining it still costs `khot-ir` 12,001, `ksched-ir` 7,555 and
1199    /// `kipc-ir` 2,000 for nothing `kernel-ir` did not already have. So the
1200    /// body keeps LLVM's own choice and only this call site is pinned.
1201    #[cold]
1202    #[inline(never)]
1203    fn tick_on_exit(&mut self) {
1204        self.tick_from_isr();
1205    }
1206
1207    /// `vPortSystemTickHandler`: the tick, from interrupt context.
1208    ///
1209    /// A silicon port calls this from its timer interrupt. The sim reaches
1210    /// it from [`Kernel::exit_critical`] -- through [`Kernel::tick_on_exit`],
1211    /// which is where the reason for this attribute is written down -- and
1212    /// from the idle hook.
1213    pub fn tick_from_isr(&mut self) {
1214        self.port.set_in_tick_entry(true);
1215        self.port.count_tick();
1216        // The C handler bumps `uxCriticalNesting` by hand and drops it the
1217        // same way — a raw `--`, never `vPortExitCritical` — so the bump is
1218        // invisible to the exit count and to anything that unwinds later.
1219        // Modelling it as a real critical section would invent an exit at
1220        // every tick that caused a switch.
1221        if self.increment_tick() {
1222            self.switch_context();
1223        }
1224        self.port.set_in_tick_entry(false);
1225    }
1226
1227    /// The idle hook's tick, `vPortKairosTick()` on the C side: a critical
1228    /// section around one unconditional tick. The enclosing section counts
1229    /// toward rule 3 exactly as the C one does.
1230    pub fn idle_hook_tick(&mut self) {
1231        self.enter_critical();
1232        self.tick_from_isr();
1233        self.exit_critical();
1234    }
1235
1236    // ---- tickless idle --------------------------------------------------
1237
1238    /// `tskIDLE_PRIORITY`.
1239    const IDLE_PRIORITY: u8 = 0;
1240
1241    /// `prvGetExpectedIdleTime`: how long nothing is due, in ticks.
1242    ///
1243    /// Zero whenever the answer would be unsafe to sleep on -- something
1244    /// above the idle priority is running, another idle-priority task is
1245    /// ready to share the slice, or a higher-priority task is ready. The
1246    /// last of those cannot happen with preemption on, and the C keeps the
1247    /// test anyway because a cooperative build reaches it.
1248    fn expected_idle_time(&self) -> u64 {
1249        // The C spells these as three arms so each carries its own reason;
1250        // they answer zero alike, so here they are one short-circuit chain
1251        // in the same order:
1252        //
1253        //  - something above the idle priority is running;
1254        //  - another idle-priority task is ready to share the slice, so the
1255        //    very next tick has to be processed;
1256        //  - a higher-priority task is ready, which only a cooperative
1257        //    build can reach and which the C tests for anyway.
1258        let due = self.current_priority() > Self::IDLE_PRIORITY
1259            || self.ready_len(Self::IDLE_PRIORITY).unwrap_or(0) > 1
1260            || self.top_ready_priority > Self::IDLE_PRIORITY;
1261
1262        if due {
1263            0
1264        } else {
1265            self.next_unblock_time.saturating_sub(self.tick)
1266        }
1267    }
1268
1269    /// `vTaskStepTick`: wind the tick count forward over a suppressed period.
1270    ///
1271    /// Note this does *not* call the tick hook for each stepped tick, which
1272    /// is the C's own note and the reason a tickless trace has no heartbeat
1273    /// in it.
1274    ///
1275    /// The C `configASSERT`s that the jump does not pass the next unblock
1276    /// time. This clamps instead: a port that overslept is a port bug, and
1277    /// winding the clock past a task's wake would lose the wake entirely,
1278    /// where losing the extra sleep is recoverable. `forbid(unsafe)` buys
1279    /// nothing if the kernel panics on a misbehaving port.
1280    ///
1281    /// Landing exactly on the next unblock time leaves the last tick pended
1282    /// rather than stepped, so `increment_tick` runs it when the scheduler
1283    /// resumes and the delayed task is woken by the same code that would
1284    /// have woken it.
1285    pub fn step_tick(&mut self, ticks_to_jump: u64) {
1286        let room = self.next_unblock_time.saturating_sub(self.tick);
1287        let mut jump = ticks_to_jump.min(room);
1288
1289        if self.tick.saturating_add(jump) == self.next_unblock_time && jump > 0 {
1290            self.pended_ticks = self.pended_ticks.saturating_add(1);
1291            jump = jump.wrapping_sub(1);
1292        }
1293
1294        self.tick = self.tick.wrapping_add(jump) & Self::MAX_DELAY;
1295    }
1296
1297    /// The `configUSE_TICKLESS_IDLE` block of `prvIdleTask`.
1298    ///
1299    /// Compiled away entirely when the configuration leaves tickless idle
1300    /// off, which is the default and is why every existing scenario is
1301    /// byte-identical with this in the tree.
1302    ///
1303    /// The shape is the C's, including the part that looks redundant: the
1304    /// expected idle time is sampled once WITHOUT the scheduler suspended,
1305    /// and again with it. The first answer is not necessarily valid and the
1306    /// C takes it anyway, because suspending and resuming the scheduler on
1307    /// every pass of the idle task costs more than a sample that is
1308    /// sometimes wasted.
1309    pub fn idle_suppress_ticks(&mut self) {
1310        if !C::USE_TICKLESS_IDLE {
1311            return;
1312        }
1313
1314        if self.expected_idle_time() < C::EXPECTED_IDLE_TIME_BEFORE_SLEEP {
1315            return;
1316        }
1317
1318        self.suspend_all();
1319        let expected = self.expected_idle_time();
1320        if expected >= C::EXPECTED_IDLE_TIME_BEFORE_SLEEP {
1321            let tick = self.tick;
1322            self.note_exits();
1323            self.trace.event(tick, Event::LowPowerIdleBegin);
1324
1325            let slept = self.port.suppress_ticks_and_sleep(expected);
1326            self.step_tick(slept);
1327
1328            let tick = self.tick;
1329            self.note_exits();
1330            self.trace.event(tick, Event::LowPowerIdleEnd);
1331        }
1332        let _ = self.resume_all();
1333    }
1334
1335    /// `portYIELD()` as the Posix port spells it: a critical section around
1336    /// the context switch, so a tick raised during it lands on the way out.
1337    /// `#[cold]` because the call is GUARDED and reached from many sites on
1338    /// one hot path, which is the shape that pays: it lets LLVM keep the
1339    /// caller's frame setup out of the likely route. Measured on
1340    /// `riscv32-qemu-tick-work`, one attribute at a time.
1341    /// Worth queue -7, group -3 on its own.
1342    #[cold]
1343    pub(crate) fn port_yield(&mut self) {
1344        self.enter_critical();
1345        self.port.count_yield();
1346        if P::COMMITS_SWITCH {
1347            // A STACKED port. Raise its switching exception and leave
1348            // `current` where it is: the exception will call
1349            // `switch_context` itself, so the decision and the register
1350            // swap happen together and nothing runs in between as a task
1351            // the kernel has already moved on from.
1352            //
1353            // The exception cannot fire yet -- `exit_critical` below is
1354            // what unmasks -- so the kernel is consistent at the moment it
1355            // is taken.
1356            self.port.yield_now();
1357        } else {
1358            // A STACKLESS kernel: moving `current` IS the switch, because
1359            // no task owns a stack. This is the path every corpus
1360            // architecture takes, and it is unchanged.
1361            self.switch_context();
1362        }
1363        self.exit_critical();
1364    }
1365
1366    /// `taskYIELD()` from a task body (the idle task's yield).
1367    pub fn task_yield(&mut self) {
1368        self.port_yield();
1369    }
1370
1371    // -------------------------------------------------------- task create --
1372
1373    /// `xTaskCreate`.
1374    ///
1375    /// Like the C, **the new task becomes current if its priority is at or
1376    /// above the running one's**. On a hosted firmware that is the sharp
1377    /// edge: the CPU is still on the caller's stack, so creating a
1378    /// higher-priority task hands `current` to something that is not
1379    /// running. See [`Kernel::start_scheduler`], which creates the timer
1380    /// daemon at [`Config::TIMER_TASK_PRIORITY`] for exactly this reason and
1381    /// documents the failure it produces — a clean run reporting zero laps.
1382    ///
1383    /// # Errors
1384    /// [`Error::Full`] when the task arena is full (the C
1385    /// `errCOULD_NOT_ALLOCATE_REQUIRED_MEMORY`).
1386    pub fn create_task(&mut self, name: &str, priority: u8) -> Result<TaskHandle> {
1387        let caller = self.current;
1388        // configASSERT( uxPriority < configMAX_PRIORITIES ), then C clamps.
1389        let priority = priority.min(C::MAX_PRIORITIES.saturating_sub(1));
1390        // `prvCreateTask` takes the stack and then the TCB from the heap
1391        // before anything is initialised — `portSTACK_GROWTH` is negative on
1392        // the oracle's port, which fixes that order — and `pvPortMallocStack`
1393        // *is* `pvPortMalloc` with the MPU wrappers off. On heap_3 each one
1394        // suspends the scheduler, so a create costs two outermost exits.
1395        //
1396        // Every scenario before `death` created its tasks BEFORE
1397        // `vTaskStartScheduler`, and the sim port counts no exits there (the
1398        // C patch counts only on a FreeRTOS thread), so this cost was
1399        // invisible to the whole corpus. `death` is the first scenario that
1400        // creates a task with the scheduler running, and the first that can
1401        // tell the difference.
1402        self.account_for_allocation();
1403        self.account_for_allocation();
1404        let tcb = Tcb {
1405            name: Name::new(name, C::MAX_TASK_NAME_LEN),
1406            priority,
1407            base_priority: priority,
1408            mutexes_held: 0,
1409            wait: WaitFrame::default(),
1410            notified: [0; MAX_NOTIFICATION_ENTRIES],
1411            notify_state: [NotifyState::NotWaiting; MAX_NOTIFICATION_ENTRIES],
1412            notify_blocked: false,
1413            event_blocked: false,
1414            stream_resume: false,
1415            queue_resume: QueueResume::No,
1416            stream_timed: false,
1417            stream_waited: false,
1418            stream_local: 0,
1419            _stride_pad: [0; STRIDE_PAD_WORDS],
1420        };
1421        let handle = match self.tcbs.try_insert(tcb) {
1422            Ok(h) => h,
1423            Err(_) => {
1424                let tick = self.tick;
1425                self.note_exits();
1426                self.trace.event(tick, Event::TaskCreateFailed);
1427                return Err(Error::Full);
1428            }
1429        };
1430        // The event item sorts by `configMAX_PRIORITIES - uxPriority`, so a
1431        // higher-priority task waits nearer the head of an event list.
1432        let event_value = u64::from(C::MAX_PRIORITIES.saturating_sub(priority));
1433        self.lists
1434            .set_value(Self::event_item(handle), event_value)?;
1435        // `prvInitialiseNewTask` ends by calling `pxPortInitialiseStack`,
1436        // which on the oracle's Posix port wraps `pthread_create` in a
1437        // critical section — one more exit, and a PORT cost rather than a
1438        // kernel one, which is why it has a flag of its own.
1439        if C::PORT_STACK_INIT_CRITICAL {
1440            self.enter_critical();
1441            self.exit_critical();
1442        }
1443        // Any of the three exits above can release a tick that switches the
1444        // creator out. In the C the creator is a thread and simply STOPS
1445        // there: `prvAddNewTaskToReadyList` has not run, so the new task is
1446        // on no ready list and `traceTASK_CREATE` has not fired. Running it
1447        // now would put both events on the wrong side of the switch — which
1448        // is precisely how `death` first diverged.
1449        if self.current != caller {
1450            if let Some(slot) = self.owed_trace.get_mut(caller.index() as usize) {
1451                *slot = OwedTrace::AddNewTaskToReadyList {
1452                    task: handle,
1453                    priority,
1454                };
1455            }
1456            self.owe(caller);
1457            return Ok(handle);
1458        }
1459        self.add_new_task_to_ready_list(handle, priority)?;
1460        Ok(handle)
1461    }
1462
1463    /// `prvAddNewTaskToReadyList`.
1464    fn add_new_task_to_ready_list(&mut self, task: TaskHandle, priority: u8) -> Result<()> {
1465        self.enter_critical();
1466        {
1467            self.task_count = self.task_count.wrapping_add(1);
1468            if self.current.is_null() {
1469                self.set_current_at(task, priority);
1470            } else if !self.running {
1471                // `<=`, so the last-created task of the highest priority is
1472                // the one that runs first.
1473                if self.current_priority() <= priority {
1474                    self.set_current_at(task, priority);
1475                }
1476            }
1477            self.trace_task(task, |task, name| Event::TaskCreate {
1478                task,
1479                name,
1480                priority: Self::priority_value(priority),
1481            });
1482            self.add_task_to_ready_list(task)?;
1483        }
1484        self.exit_critical();
1485        // taskYIELD_IF_USING_PREEMPTION(), outside the section.
1486        if self.running && C::USE_PREEMPTION && self.current_priority() < priority {
1487            self.port_yield();
1488        }
1489        Ok(())
1490    }
1491
1492    /// `prvAddTaskToReadyList`.
1493    /// Returns `Result<()>`, and that is a measured decision, not an
1494    /// oversight.
1495    ///
1496    /// Its two hot callers -- the tick's wake loop and the pending-ready
1497    /// drain -- resolve the SAME TCB again on the next line for the SAME
1498    /// field, to ask whether the woken task outranks the running one. Having
1499    /// this hand the priority back instead costs **+3.69% on kdelay-ir and
1500    /// +3.10% on ksched-ir**.
1501    ///
1502    /// Wrapping it -- narrow signature for the eleven callers that ignore the
1503    /// value, a wide inner for the two that want it -- does NOT help: that
1504    /// measured bit-for-bit identical to the unwrapped version on all four
1505    /// arms, because LLVM inlines through the wrapper and propagates the wide
1506    /// return anyway.
1507    ///
1508    /// The likely mechanism is the tail call. At `Result<()>` this function
1509    /// ends by handing back `insert_end`'s own result; at `Result<u8>` it has
1510    /// to capture that result, test it, and build a new one, at every site.
1511    pub(crate) fn add_task_to_ready_list(&mut self, task: TaskHandle) -> Result<()> {
1512        let priority = self.tcbs.resolve(task)?.priority;
1513        self.trace_task(task, |task, name| Event::MovedTaskToReadyState {
1514            task,
1515            name,
1516        });
1517        // taskRECORD_READY_PRIORITY
1518        if priority > self.top_ready_priority {
1519            self.top_ready_priority = priority;
1520        }
1521        self.lists
1522            .insert_end(Self::ready_list(priority), Self::state_item(task))
1523    }
1524
1525    // ---------------------------------------------------- scheduler start --
1526
1527    /// `vTaskStartScheduler`, minus the part that never returns.
1528    ///
1529    /// Creates the idle task, the timer command queue and the timer service
1530    /// task, fires `TASK_SWITCHED_IN` for whichever task will run first and
1531    /// then `STARTING_SCHEDULER`, and returns the handles so the runner can
1532    /// attach their bodies.
1533    ///
1534    /// # ★ The timer daemon is created at [`Config::TIMER_TASK_PRIORITY`],
1535    /// and it will outrank a task you created below it
1536    ///
1537    /// This is the C's behaviour and it is deliberate, but on a hosted
1538    /// firmware it has a failure mode that looks like nothing at all.
1539    ///
1540    /// `Tmr Svc` is created here **unconditionally**, and
1541    /// [`Kernel::create_task`] makes the highest-priority task current. So a
1542    /// firmware whose own `main` runs below `TIMER_TASK_PRIORITY` leaves the
1543    /// kernel believing a **stackless** task is running: `current` names the
1544    /// daemon while the CPU is on `main`'s stack. Every
1545    /// [`Kernel::switch_context`] then declines as `from == to`, the workers
1546    /// never start, and the symptom is a clean run reporting **zero laps**
1547    /// rather than a fault.
1548    ///
1549    /// Nothing here can detect it — a stackless kernel cannot see whose stack
1550    /// the CPU is actually on — so it is a caller's invariant:
1551    ///
1552    /// > **Give the task that owns the CPU a priority at or above
1553    /// > [`Config::TIMER_TASK_PRIORITY`]**, or lower `TIMER_TASK_PRIORITY`
1554    /// > below it.
1555    ///
1556    /// Reported from the Janus side, where it cost a board run
1557    /// (`docs/plans/janus-rtos.md` §5b), and seen again in the radio cell.
1558    ///
1559    /// # Errors
1560    /// As [`Kernel::create_task`].
1561    pub fn start_scheduler(&mut self) -> Result<StartHandles> {
1562        let idle = self.create_task("IDLE", 0)?;
1563        // `xTimerCreateTimerTask` opens with `prvCheckForValidListAndQueue`,
1564        // which makes the command queue only if no `xTimerCreate` has made
1565        // it already.
1566        self.check_for_valid_list_and_queue()?;
1567        let timer_queue = self.timer_queue;
1568        let timer = self.create_task("Tmr Svc", C::TIMER_TASK_PRIORITY)?;
1569        self.next_unblock_time = Self::MAX_DELAY;
1570        self.running = true;
1571        self.tick = C::INITIAL_TICK_COUNT;
1572        self.port.scheduler_started();
1573        // `vPortStartFirstTask` runs the first task through the same
1574        // first-start path as every other.
1575        let current = self.current;
1576        self.note_first_start(current);
1577        self.trace_task(current, |task, name| Event::TaskSwitchedIn { task, name });
1578        let tick = self.tick;
1579        self.note_exits();
1580        self.trace.event(tick, Event::StartingScheduler);
1581        Ok(StartHandles {
1582            idle,
1583            timer,
1584            timer_queue,
1585        })
1586    }
1587
1588    // -------------------------------------------------------- the switch --
1589
1590    /// `vTaskSwitchContext`.
1591    pub fn switch_context(&mut self) {
1592        if self.suspended_depth != 0 {
1593            self.yield_pending = true;
1594            return;
1595        }
1596        self.yield_pending = false;
1597        let current = self.current;
1598        self.trace_task(current, |task, name| Event::TaskSwitchedOut { task, name });
1599        // taskSELECT_HIGHEST_PRIORITY_TASK
1600        //
1601        // ONE call per priority level, not two. The search used to ask
1602        // `is_empty` — a bounded read of the list's metadata — and then hand
1603        // the winning level to `next_round_robin`, which reads that same
1604        // metadata again to find the cursor. `next_round_robin` already
1605        // answers `None` for an empty list, and does so BEFORE it touches the
1606        // cursor, so it is its own emptiness probe and the level that loses
1607        // is left exactly as it was found.
1608        let mut top = self.top_ready_priority;
1609        // ★ `Err` is folded into "that level is empty" below, and the fold IS
1610        // the win: with three arms the walk carried a packed
1611        // `Result<Option<ItemId>>` across the back edge -- a `setb`/`shl`/`or`
1612        // to build it and a `test`/`jne` to take it apart, on every one of the
1613        // 1.58 levels a call walks. Two arms took this function from 168.0 to
1614        // 157.7 Ir per call, -937,965 on `bench/kernel-ir`, all of it here.
1615        //
1616        // But an out-of-range list id is a different fault from an empty level,
1617        // and the fold alone would have reported it as `NoReadyTask`. So it is
1618        // proved HERE instead, once, where it can still name itself:
1619        // `ready_list` is the identity, so the only way the walk can index out
1620        // of range is a `top_ready_priority` above the configured ceiling.
1621        // That is the diagnostic bought back, and the cost of buying it is in
1622        // the commit message beside the fold's.
1623        if top >= C::MAX_PRIORITIES {
1624            self.note_stall(Stall::ListError);
1625            return;
1626        }
1627        let item = loop {
1628            match self.lists.next_round_robin(Self::ready_list(top)) {
1629                Ok(Some(item)) => break item,
1630                Ok(None) | Err(_) => {
1631                    if top == 0 {
1632                        // The C `configASSERT( uxTopPriority )`. The idle
1633                        // task keeps priority 0 non-empty, so reaching here
1634                        // means it is gone. The kernel keeps the current
1635                        // task rather than indexing out of range -- and now
1636                        // SAYS so, because carrying on quietly is how this
1637                        // costs an afternoon on a board.
1638                        self.note_stall(Stall::NoReadyTask);
1639                        return;
1640                    }
1641                    // At least 1: the arm above returns at zero.
1642                    top = top.wrapping_sub(1);
1643                }
1644            }
1645        };
1646        let Ok(next) = self.task_of_state_item(item) else {
1647            self.note_stall(Stall::UnknownTask);
1648            return;
1649        };
1650        self.top_ready_priority = top;
1651        // INDICES, and `hand_over` takes only the incoming handle: together
1652        // those two delete the load of `current`'s generation word entirely.
1653        // Either alone leaves it live -- the full-handle `!=` compares both
1654        // halves, and a `hand_over` taking the outgoing handle needs both -- so
1655        // the index compare measured 0 on its own. `rusty-compiler-leverage`
1656        // A2: price the SET, not the halves.
1657        //
1658        // Comparing indices is sound because both handles are LIVE: `next` came
1659        // out of a slot whose generation was just matched, and `current` names
1660        // the running task. The arena issues one live handle per slot at a time,
1661        // so two live handles sharing an index share a generation. That is the
1662        // same argument `Handle::is_null` makes in the other direction.
1663        if next.index() != current.index() {
1664            self.hand_over(next);
1665        }
1666        // `top` is `next`'s priority by construction: the loop above found
1667        // the highest non-empty ready list and `next` came out of it.
1668        self.set_current_at(next, top);
1669        self.trace_task(next, |task, name| Event::TaskSwitchedIn { task, name });
1670    }
1671
1672    // ----------------------------------------------------------- the tick --
1673
1674    /// Pay whatever the running task still owes from a call it was
1675    /// preempted inside. The runner calls this before stepping a body;
1676    /// `true` means work was done and the current task may have changed
1677    /// again, so nothing else should be assumed.
1678    #[inline(always)]
1679    pub fn resume_pending(&mut self) -> bool {
1680        // The fast path, in line at the runner's one call site.
1681        //
1682        // `Runner::step_once` asks this before every step -- 214,488 times
1683        // in a 20,000-tick `StreamBufferDemo` -- and the answer is "nothing
1684        // owed" almost every time. Two loads and two branches decide it,
1685        // and out of line they cost a call and a frame as well.
1686        //
1687        // The two tests are the entry conditions of the two things the
1688        // body does: `settle_unwind` returns at once unless `unwinding` is
1689        // set, and the rest returns at once unless this task owes
1690        // something. Neither is duplicated -- the cold half still runs
1691        // both in full.
1692        // On a `COMMITS_SWITCH` port `unwinding` is never set (see `hand_over`),
1693        // and saying so with the const lets LLVM drop the load and the branch.
1694        if P::COMMITS_SWITCH || self.unwinding.is_null() {
1695            // Nothing to settle, which is the shape of almost every call.
1696            // `settle_unwind` would test `unwinding` and return at once, and
1697            // the cold half would then re-read the very byte this line reads
1698            // — so on this shape both are skipped and the owed body is
1699            // entered directly.
1700            let index = self.current.index() as usize;
1701            // B1, the shape win 7 established: `self.current` is read RAW here -- no
1702            // bound-checking accessor between the field and the use -- and `index` then
1703            // feeds `owes_anything.get(index)`. Contrast `remove_from_event_list`, where
1704            // the same proof measured EXACTLY +0 because its handle comes back from
1705            // `handle_at`, which bound-checks, so the fact was already local.
1706            if index >= TASKS {
1707                return false;
1708            }
1709            if !self.owes_anything.get(index).copied().unwrap_or(true) {
1710                return false;
1711            }
1712            return self.resume_pending_owed(index);
1713        }
1714        self.resume_pending_cold()
1715    }
1716
1717    /// Everything [`Kernel::resume_pending`] does when something IS owed.
1718    ///
1719    /// Out of line on purpose: it is reached on a small fraction of steps,
1720    /// and inlining it would put the whole `OwedTrace` match at the hot
1721    /// site. Same body/symbol split the trace sink's `num` measured.
1722    #[inline(never)]
1723    fn resume_pending_cold(&mut self) -> bool {
1724        self.settle_unwind();
1725        let index = self.current.index() as usize;
1726        // B1, the shape win 7 established: `self.current` is read RAW here -- no
1727        // bound-checking accessor between the field and the use -- and `index` then
1728        // feeds `owes_anything.get(index)`. Contrast `remove_from_event_list`, where
1729        // the same proof measured EXACTLY +0 because its handle comes back from
1730        // `handle_at`, which bound-checks, so the fact was already local.
1731        if index >= TASKS {
1732            return false;
1733        }
1734
1735        // One load and one test for the overwhelmingly common case. The
1736        // combined check below is the fallback, and it is what clears the hint
1737        // -- so a hint left standing costs one slow path and then goes away.
1738        //
1739        // This read cannot be threaded in from `resume_pending`: settling an
1740        // unwind calls `owe` itself, so the answer here is not always the
1741        // answer there. That is exactly why the no-unwind shape gets its own
1742        // entry rather than this one being made cheaper.
1743        if !self.owes_anything.get(index).copied().unwrap_or(true) {
1744            return false;
1745        }
1746        self.resume_pending_owed(index)
1747    }
1748
1749    /// Everything owed to the current task, once it is known that something
1750    /// is.
1751    ///
1752    /// Its own symbol so that both shapes above can reach it without either
1753    /// paying for the other's entry conditions.
1754    #[inline(never)]
1755    fn resume_pending_owed(&mut self, index: usize) -> bool {
1756        let did = self.resume_pending_owed_inner(index);
1757        if did {
1758            // Every branch below that did work returned with the hint still
1759            // standing, so the runner came straight back and spent a second
1760            // entry re-deriving "nothing owed". Clearing it here covers all
1761            // of them at one site.
1762            self.clear_owe_if_settled(index);
1763        }
1764        did
1765    }
1766
1767    /// The body of [`Kernel::resume_pending_owed`].
1768    fn resume_pending_owed_inner(&mut self, index: usize) -> bool {
1769        // Almost every call answers "nothing owed", and the sequence below
1770        // reaches that answer in three stages -- a compare, a match over
1771        // `OwedTrace`, then another compare -- each reachable only after the
1772        // one before. The same three loads, but one branch instead of three.
1773        // No `.copied()` on `owed_trace`: that materialises an
1774        // `Option<OwedTrace>`, and `OwedTrace` is forty bytes wide because of
1775        // `TimerCommandSend`'s `Name`. Matching through the reference tests
1776        // the discriminant where the copy moved the whole variant to test it.
1777        if self.owed_exits.get(index).copied().unwrap_or(0) == 0
1778            && matches!(self.owed_trace.get(index), Some(OwedTrace::None) | None)
1779            && !self.flag(index, Self::F_YIELD, false)
1780        {
1781            if let Some(f) = self.owes_anything.get_mut(index) {
1782                *f = false;
1783            }
1784            return false;
1785        }
1786        // First the stack unwinds — the sections the task had open when it
1787        // was switched out, and whatever its abandoned frame opened after
1788        // that — and only then does the statement after the yield run.
1789        // Reversing the two moves every tick.
1790        let owed = self.owed_exits.get(index).copied().unwrap_or(0);
1791        if owed > 0 {
1792            if let Some(slot) = self.owed_exits.get_mut(index) {
1793                *slot = 0;
1794            }
1795            // One counted exit each: the tally is already in outermost
1796            // exits, so replaying it as nesting would lose the sections the
1797            // tail opened and closed on its own.
1798            for _ in 0..owed {
1799                self.enter_critical();
1800                self.exit_critical();
1801                // A replayed exit can release a tick that switches this
1802                // task straight back out. The rest of the loop is then the
1803                // tail of *this* frame, which the port tallies and the next
1804                // resume pays — so there is nothing to unwind by hand.
1805            }
1806            return true;
1807        }
1808        // Then the line the abandoned frame had not reached yet.
1809        match self.owed_trace.get(index).copied() {
1810            Some(OwedTrace::SendFailed(queue)) => {
1811                if let Some(slot) = self.owed_trace.get_mut(index) {
1812                    *slot = crate::kernel::OwedTrace::None;
1813                }
1814                let tick = self.tick;
1815                self.note_exits();
1816                self.trace
1817                    .event(tick, Event::QueueSendFailed { queue, name: "" });
1818                return true;
1819            }
1820            Some(OwedTrace::ReceiveFailed(queue)) => {
1821                if let Some(slot) = self.owed_trace.get_mut(index) {
1822                    *slot = crate::kernel::OwedTrace::None;
1823                }
1824                let tick = self.tick;
1825                self.note_exits();
1826                self.trace
1827                    .event(tick, Event::QueueReceiveFailed { queue, name: "" });
1828                return true;
1829            }
1830            Some(OwedTrace::EventGroupWaitBitsEnd {
1831                group,
1832                bits,
1833                timed_out,
1834            }) => {
1835                if let Some(slot) = self.owed_trace.get_mut(index) {
1836                    *slot = crate::kernel::OwedTrace::None;
1837                }
1838                let tick = self.tick;
1839                self.note_exits();
1840                self.trace.event(
1841                    tick,
1842                    Event::EventGroupWaitBitsEnd {
1843                        group,
1844                        bits,
1845                        timed_out,
1846                    },
1847                );
1848                return true;
1849            }
1850            Some(OwedTrace::StreamBufferCreate {
1851                buffer,
1852                is_message_buffer,
1853            }) => {
1854                if let Some(slot) = self.owed_trace.get_mut(index) {
1855                    *slot = crate::kernel::OwedTrace::None;
1856                }
1857                let tick = self.tick;
1858                self.note_exits();
1859                self.trace.event(
1860                    tick,
1861                    Event::StreamBufferCreate {
1862                        buffer,
1863                        is_message_buffer,
1864                    },
1865                );
1866                return true;
1867            }
1868            Some(OwedTrace::TimerCommandSend {
1869                timer,
1870                name,
1871                command,
1872                value,
1873            }) => {
1874                if let Some(slot) = self.owed_trace.get_mut(index) {
1875                    *slot = crate::kernel::OwedTrace::None;
1876                }
1877                let tick = self.tick;
1878                self.note_exits();
1879                self.trace.event(
1880                    tick,
1881                    Event::TimerCommandSend {
1882                        timer,
1883                        name: name.as_str(),
1884                        command,
1885                        value,
1886                    },
1887                );
1888                return true;
1889            }
1890            Some(OwedTrace::AddNewTaskToReadyList { task, priority }) => {
1891                if let Some(slot) = self.owed_trace.get_mut(index) {
1892                    *slot = crate::kernel::OwedTrace::None;
1893                }
1894                let _ = self.add_new_task_to_ready_list(task, priority);
1895                return true;
1896            }
1897            Some(OwedTrace::None) | None => {}
1898        }
1899        if !self.flag(index, Self::F_YIELD, false) {
1900            return false;
1901        }
1902        self.set_flag(index, Self::F_YIELD, false);
1903        self.port_yield();
1904        true
1905    }
1906
1907    /// Collect the tally of an abandoned frame that has finished running.
1908    ///
1909    /// The frame runs to its end before control comes back to the runner,
1910    /// so this is called once, at the top of [`Kernel::resume_pending`],
1911    /// which is the first thing the runner does.
1912    fn settle_unwind(&mut self) {
1913        // Never anything to settle on a port that commits its own switches.
1914        if P::COMMITS_SWITCH {
1915            return;
1916        }
1917        // Nothing to settle is the common case by a wide margin, and `take()`
1918        // writes `None` back even then -- a store, on every call, to clear a
1919        // slot that was already clear. Peeking first leaves the store for the
1920        // calls that actually have something to clear.
1921        if self.unwinding.is_null() {
1922            return;
1923        }
1924        let task = core::mem::replace(&mut self.unwinding, TaskHandle::NULL);
1925        if task.is_null() {
1926            return;
1927        };
1928        let owed = self.port.end_unwind();
1929        if let Some(slot) = self.owed_exits.get_mut(task.index() as usize) {
1930            // Accumulate: a replay that is itself interrupted leaves the
1931            // rest of its own loop as a tail, and that tail is more of the
1932            // same debt.
1933            *slot = slot.saturating_add(owed);
1934        }
1935        if owed > 0 {
1936            self.owe(task);
1937        }
1938    }
1939
1940    /// Emit a queue failure line now, or owe it if a tick switched the
1941    /// caller out of the call that was about to emit it.
1942    /// In line on purpose, at all seven call sites. It is reached 46,671
1943    /// times in kernel-ir and every one of them paid a call and a frame to
1944    /// choose between two events the caller had already decided between.
1945    #[inline(always)]
1946    pub(crate) fn trace_failure_or_owe(&mut self, caller: TaskHandle, owed: OwedTrace) {
1947        #[cfg(feature = "census")]
1948        CENSUS_OWE.fetch_add(1, core::sync::atomic::Ordering::Relaxed);
1949        // Unlike every other trace site, this one has a side effect a no-op
1950        // sink cannot delete: the miss path STORES an `OwedTrace` and raises
1951        // `owes_anything`, which sends the task down the owed body on its next
1952        // run to reproduce a line the sink will drop.
1953        if !T::EMITS {
1954            return;
1955        }
1956        if self.current == caller {
1957            let tick = self.tick;
1958            self.note_exits();
1959            match owed {
1960                OwedTrace::SendFailed(queue) => self
1961                    .trace
1962                    .event(tick, Event::QueueSendFailed { queue, name: "" }),
1963                OwedTrace::ReceiveFailed(queue) => self
1964                    .trace
1965                    .event(tick, Event::QueueReceiveFailed { queue, name: "" }),
1966                OwedTrace::StreamBufferCreate {
1967                    buffer,
1968                    is_message_buffer,
1969                } => self.trace.event(
1970                    tick,
1971                    Event::StreamBufferCreate {
1972                        buffer,
1973                        is_message_buffer,
1974                    },
1975                ),
1976                OwedTrace::TimerCommandSend {
1977                    timer,
1978                    name,
1979                    command,
1980                    value,
1981                } => self.trace.event(
1982                    tick,
1983                    Event::TimerCommandSend {
1984                        timer,
1985                        name: name.as_str(),
1986                        command,
1987                        value,
1988                    },
1989                ),
1990                OwedTrace::EventGroupWaitBitsEnd {
1991                    group,
1992                    bits,
1993                    timed_out,
1994                } => self.trace.event(
1995                    tick,
1996                    Event::EventGroupWaitBitsEnd {
1997                        group,
1998                        bits,
1999                        timed_out,
2000                    },
2001                ),
2002                // Not reachable through this function: `create_task` owes
2003                // its second half directly, because that half is not a
2004                // trace line — it inserts into a ready list — and it must
2005                // run INSIDE the section this one has already left.
2006                OwedTrace::AddNewTaskToReadyList { .. } | OwedTrace::None => {}
2007            }
2008            return;
2009        }
2010        if let Some(slot) = self.owed_trace.get_mut(caller.index() as usize) {
2011            *slot = owed;
2012        }
2013        self.owe(caller);
2014    }
2015
2016    /// Raise the hint that `task` owes something.
2017    ///
2018    /// Called by every writer of `owed_trace`, `owes_yield` and `owed_exits`.
2019    /// Missing one would let `resume_pending` skip work that was really owed,
2020    /// which the conformance differential would show as a missing trace line.
2021    /// `owes_yield`: a `portYIELD()` the task was preempted before reaching.
2022    const F_YIELD: u8 = 1 << 1;
2023    /// `wait_set`: a blocking call's `WaitFrame` is live in the TCB.
2024    const F_WAIT: u8 = 1 << 2;
2025
2026    /// Read one per-task flag.
2027    ///
2028    /// `missing` is what an index past the end answers. Each caller chooses it
2029    /// so an impossible index takes the SLOW path rather than the fast one,
2030    /// which is what the five separate arrays did with `unwrap_or`.
2031    #[inline(always)]
2032    fn flag(&self, index: usize, bit: u8, missing: bool) -> bool {
2033        match self.flags.get(index) {
2034            Some(f) => f & bit != 0,
2035            None => missing,
2036        }
2037    }
2038
2039    /// Write one per-task flag. An index past the end writes nothing, as
2040    /// `get_mut` did.
2041    #[inline(always)]
2042    fn set_flag(&mut self, index: usize, bit: u8, on: bool) {
2043        if let Some(f) = self.flags.get_mut(index) {
2044            if on {
2045                *f |= bit;
2046            } else {
2047                *f &= !bit;
2048            }
2049        }
2050    }
2051
2052    /// Drop the hint if nothing is owed any more.
2053    ///
2054    /// Worth one whole entry to [`Kernel::resume_pending_owed`] per owed item.
2055    /// A census over three scenarios found every raise producing exactly TWO
2056    /// entries — one that did the work and returned `true`, and a second that
2057    /// re-derived "nothing owed" and cleared the hint on its way out (BlockQ:
2058    /// 43,110 raises, 86,207 entries, 43,103 of them finding nothing). Doing
2059    /// it at the end of the branch that did the work turns that second entry
2060    /// into a `resume_pending` fast path, which is a few instructions instead
2061    /// of forty-odd.
2062    ///
2063    /// This cannot clear a live hint. Everything that opens new debt raises
2064    /// the hint itself — a replay that gets switched out leaves its tail to
2065    /// `settle_unwind`, which raises it again when it collects the tally.
2066    fn clear_owe_if_settled(&mut self, index: usize) {
2067        if self.owed_exits.get(index).copied().unwrap_or(0) == 0
2068            && matches!(self.owed_trace.get(index), Some(OwedTrace::None) | None)
2069            && !self.flag(index, Self::F_YIELD, false)
2070        {
2071            if let Some(f) = self.owes_anything.get_mut(index) {
2072                *f = false;
2073            }
2074        }
2075    }
2076
2077    fn owe(&mut self, task: TaskHandle) {
2078        if let Some(f) = self.owes_anything.get_mut(task.index() as usize) {
2079            *f = true;
2080        }
2081    }
2082
2083    /// Record that `task` was preempted before the `portYIELD()` at the end
2084    /// of the call it is inside.
2085    pub(crate) fn owe_yield(&mut self, task: TaskHandle) {
2086        self.set_flag(task.index() as usize, Self::F_YIELD, true);
2087        self.owe(task);
2088    }
2089
2090    /// Hand the CPU from `outgoing` to `incoming`: what `prvSwitchThread`
2091    /// does to `uxCriticalNesting`.
2092    ///
2093    /// Everything the outgoing task's call still does from here belongs to
2094    /// that task at the time it runs again, so the port stops counting the
2095    /// frame's exits as sim time and starts tallying them;
2096    /// [`Kernel::settle_unwind`] collects the tally once the frame has
2097    /// finished. A task being switched in for the first time has a fresh
2098    /// stack and owes nothing.
2099    /// Takes only the INCOMING handle. The outgoing one is `self.current`, which
2100    /// this reads for itself -- `set_current_at` has not run yet, so the field
2101    /// still names the task being left. Passing it in made `switch_context` load
2102    /// BOTH words of the handle at the top of the function, and the generation
2103    /// half is read only on the unwind arm below, which is skipped on every
2104    /// switch after the first.
2105    fn hand_over(&mut self, incoming: TaskHandle) {
2106        // A tail that switches again is still the first frame's tail: the
2107        // code after the second switch is on the same abandoned stack.
2108        // The unwinding marker exists for a port that does NOT commit the switch:
2109        // there `switch_context` returns into the OUTGOING task's Rust frame,
2110        // whose tail then runs on an abandoned stack and must be tallied rather
2111        // than counted. A `COMMITS_SWITCH` port saves the registers itself and
2112        // resumes the incoming task in ITS frame; nothing is abandoned, its
2113        // `begin_unwind` is a no-op and its `end_unwind` answers 0 -- so on
2114        // those ports this only forced `resume_pending` down its cold path
2115        // once per switch to settle a tally of zero. The const folds the whole
2116        // thing away on silicon and leaves the sim untouched.
2117        if !P::COMMITS_SWITCH && self.unwinding.is_null() {
2118            self.unwinding = self.current;
2119            self.port.begin_unwind();
2120        }
2121        let index = incoming.index() as usize;
2122        // ONE access to the byte, not two: the test and the two bit writes all
2123        // work on the same `&mut`. STARTED goes on and YIELD goes off together,
2124        // which is the whole point of their sharing a byte.
2125        let first = match self.started.get_mut(index) {
2126            Some(f) if !*f => {
2127                *f = true;
2128                true
2129            }
2130            _ => false,
2131        };
2132        if first {
2133            self.set_flag(index, Self::F_YIELD, false);
2134            if let Some(slot) = self.owed_exits.get_mut(index) {
2135                *slot = 0;
2136            }
2137            if let Some(slot) = self.owed_trace.get_mut(index) {
2138                *slot = crate::kernel::OwedTrace::None;
2139            }
2140        }
2141    }
2142
2143    /// Mark a task as having run, without a hand-over: the first task the
2144    /// scheduler starts has no predecessor.
2145    fn note_first_start(&mut self, task: TaskHandle) {
2146        if let Some(f) = self.started.get_mut(task.index() as usize) {
2147            *f = true;
2148        }
2149    }
2150
2151    /// `xTaskIncrementTick`; `true` when a context switch is required.
2152    pub fn increment_tick(&mut self) -> bool {
2153        let tick = self.tick;
2154        self.note_exits();
2155        self.trace.event(tick, Event::TaskIncrementTick { tick });
2156        let mut switch_required = false;
2157        if self.suspended_depth == 0 {
2158            let next = self.tick.wrapping_add(1) & Self::MAX_DELAY;
2159            self.tick = next;
2160            if next == 0 {
2161                self.switch_delayed_lists();
2162            }
2163            // The mask is not arithmetic, it is INFORMATION. Both sides are
2164            // tick values and every writer of either has already masked with
2165            // `MAX_DELAY` -- `next` two lines above, `next_unblock_time` from a
2166            // `wake_at` that `add_current_task_to_delayed_list` masked, or from
2167            // `MAX_DELAY` itself. So at a 32-bit tick width the high half of
2168            // both is invariantly zero.
2169            //
2170            // LLVM proves that for `next`, which it just computed, and cannot
2171            // for `next_unblock_time`, which it loaded -- so the comparison was
2172            // emitted as a full 64-bit one: a second `lw` for the high word,
2173            // then `sltu`/`snez`/`or` to combine. Masking says the high half is
2174            // zero and the compare collapses to the single `bltu` the values
2175            // deserve. At a 64-bit width `MAX_DELAY` is `u64::MAX` and the mask
2176            // folds to nothing, so this costs those configurations no
2177            // instruction at all.
2178            // The mask is only sound while every writer of the field has
2179            // already applied it. All six do -- three store `MAX_DELAY`, two
2180            // store a delayed list's head value, and the one place that MINTS
2181            // such a value masks it (`add_current_task_to_delayed_list`'s
2182            // `wake_at`). This is the proof, and it costs nothing in release:
2183            // a writer that forgets fails the kernel's own tests, the Kani
2184            // proofs and the conformance corpus instead of silently changing a
2185            // comparison. Same guard shape as `current_priority`'s.
2186            debug_assert_eq!(
2187                self.next_unblock_time,
2188                self.next_unblock_time & Self::MAX_DELAY,
2189                "next_unblock_time holds a value wider than the tick, so masking                  it in the comparison below would change the answer"
2190            );
2191            if next >= self.next_unblock_time & Self::MAX_DELAY {
2192                switch_required = self.wake_due_tasks(next);
2193            }
2194            // `!switch_required` first: when the tick already woke a
2195            // task, this can only set what is already set, and asking
2196            // costs a TCB resolve for the running priority plus a list
2197            // read. Setting a `true` to `true` is not worth either.
2198            if C::USE_PREEMPTION
2199                && C::USE_TIME_SLICING
2200                && !switch_required
2201                && self
2202                    .lists
2203                    .len(Self::ready_list(self.current_priority()))
2204                    .unwrap_or(0)
2205                    > 1
2206            {
2207                switch_required = true;
2208            }
2209            // The C guards this site with `xPendedTicks == 0`, so a hook
2210            // does not fire again for each tick being unwound by
2211            // `xTaskResumeAll`. It sits after the time-slicing test and
2212            // before the yield-pending one, and a `FromISR` call inside it
2213            // can set `yield_pending`, so the order is load-bearing.
2214            if self.pended_ticks == 0 {
2215                self.run_tick_hook();
2216            }
2217            if C::USE_PREEMPTION && self.yield_pending {
2218                switch_required = true;
2219            }
2220        } else {
2221            self.pended_ticks = self.pended_ticks.wrapping_add(1);
2222            // "The tick hook gets called at regular intervals, even if the
2223            // scheduler is locked" — and here with no guard, because this
2224            // tick is being pended rather than unwound.
2225            self.run_tick_hook();
2226        }
2227        switch_required
2228    }
2229
2230    // ------------------------------------------- task notifications --
2231    //
2232    // A notification is the lightest thing a task can block on: no object,
2233    // no event list, just a slot in the TCB and the delayed list. That is
2234    // why the stream buffers use one rather than a queue, and why waking a
2235    // task this way is a list move rather than an event-list walk.
2236
2237    /// `xTaskGenericNotifyWait`.
2238    ///
2239    /// `true` is `pdTRUE`: a notification was received. `Blocked` means the
2240    /// caller must call again — the C blocks inside this function, and a
2241    /// kernel with no stacks returns instead.
2242    ///
2243    /// # Errors
2244    /// [`Error::InvalidArgument`] for an index past the configured array.
2245    pub fn notify_wait(
2246        &mut self,
2247        index: usize,
2248        clear_on_entry: u32,
2249        clear_on_exit: u32,
2250        ticks: u64,
2251    ) -> Result<Wait<(bool, u32)>> {
2252        if index >= C::NOTIFICATION_ARRAY_ENTRIES {
2253            return Err(Error::InvalidArgument);
2254        }
2255        let caller = self.current;
2256        let state = self.notify_state_of(caller, index);
2257        if state != NotifyState::Received && ticks > 0 && !self.notify_blocked(caller) {
2258            self.suspend_all();
2259            self.enter_critical();
2260            let mut should_block = false;
2261            if self.notify_state_of(caller, index) != NotifyState::Received {
2262                if let Ok(tcb) = self.tcbs.resolve_mut(caller) {
2263                    if let Some(slot) = tcb.notified.get_mut(index) {
2264                        *slot &= !clear_on_entry;
2265                    }
2266                    if let Some(slot) = tcb.notify_state.get_mut(index) {
2267                        *slot = NotifyState::Waiting;
2268                    }
2269                }
2270                should_block = true;
2271            }
2272            self.exit_critical();
2273            if should_block {
2274                let tick = self.tick;
2275                self.note_exits();
2276                self.trace_task(caller, |task, name| Event::TaskNotifyWaitBlock {
2277                    task,
2278                    name,
2279                    index,
2280                });
2281                let _ = tick;
2282                self.add_current_task_to_delayed_list(ticks, true)?;
2283            }
2284            let already_yielded = self.resume_all();
2285            if should_block && !already_yielded {
2286                if self.current == caller {
2287                    self.port_yield();
2288                } else {
2289                    self.owe_yield(caller);
2290                }
2291            }
2292            // The C blocks here; this kernel comes back and is called again.
2293            self.set_notify_blocked(caller, true);
2294            return Ok(Wait::Blocked);
2295        }
2296        self.set_notify_blocked(caller, false);
2297        self.enter_critical();
2298        self.note_exits();
2299        self.trace_task(caller, |task, name| Event::TaskNotifyWait {
2300            task,
2301            name,
2302            index,
2303        });
2304        let value = self.notified_value_of(caller, index);
2305        let received = self.notify_state_of(caller, index) == NotifyState::Received;
2306        if let Ok(tcb) = self.tcbs.resolve_mut(caller) {
2307            if received {
2308                if let Some(slot) = tcb.notified.get_mut(index) {
2309                    *slot &= !clear_on_exit;
2310                }
2311            }
2312            if let Some(slot) = tcb.notify_state.get_mut(index) {
2313                *slot = NotifyState::NotWaiting;
2314            }
2315        }
2316        self.exit_critical();
2317        Ok(Wait::Ready((received, value)))
2318    }
2319
2320    /// `ulTaskGenericNotifyTake`: the notification used as a lightweight
2321    /// counting semaphore — block until the value is non-zero, then either
2322    /// zero it or decrement it by one.
2323    ///
2324    /// This is the half of the notification API the kernel was missing.
2325    /// `notify_wait` waits on *bits*; this waits on a *count*, and the two
2326    /// are separate calls in the C with their own trace events. Its
2327    /// partner, `xTaskNotifyGive`, needs no method of its own: the C
2328    /// defines it as `xTaskGenericNotify( .., 0, eIncrement, NULL )` and
2329    /// it traces as an ordinary notify, so
2330    /// `notify(task, index, 0, NotifyAction::Increment)` already is it.
2331    ///
2332    /// # The shape, and why it is not `notify_wait`'s
2333    ///
2334    /// The C blocks on `ulNotifiedValue == 0`, **not** on the notify
2335    /// state, and it does no clear-on-entry. Both halves run on the way
2336    /// out: `traceTASK_NOTIFY_TAKE` fires whether or not the call ever
2337    /// blocked, which is what makes a take that finds a count already
2338    /// waiting still emit one line.
2339    ///
2340    /// This kernel has no stack, so the block is a return: the first call
2341    /// answers [`Wait::Blocked`] and the caller is entered again when the
2342    /// scheduler runs it, taking the second half. `notify_wait_pending`
2343    /// answers for this call too — a task is only ever inside one of the
2344    /// two.
2345    ///
2346    /// # Errors
2347    /// [`Error::InvalidArgument`] for an index past the configured array.
2348    pub fn notify_take(
2349        &mut self,
2350        index: usize,
2351        clear_on_exit: bool,
2352        ticks: u64,
2353    ) -> Result<Wait<u32>> {
2354        if index >= C::NOTIFICATION_ARRAY_ENTRIES {
2355            return Err(Error::InvalidArgument);
2356        }
2357        let caller = self.current;
2358        if self.notified_value_of(caller, index) == 0 && ticks > 0 && !self.notify_blocked(caller) {
2359            self.suspend_all();
2360            self.enter_critical();
2361            let mut should_block = false;
2362            // Re-checked inside the section, as the C does: a notify from
2363            // an ISR between the two reads would otherwise be lost.
2364            if self.notified_value_of(caller, index) == 0 {
2365                if let Ok(tcb) = self.tcbs.resolve_mut(caller) {
2366                    if let Some(slot) = tcb.notify_state.get_mut(index) {
2367                        *slot = NotifyState::Waiting;
2368                    }
2369                }
2370                should_block = true;
2371            }
2372            self.exit_critical();
2373            if should_block {
2374                // The C traces BEFORE it adds itself to the delayed list.
2375                self.note_exits();
2376                self.trace_task(caller, |task, name| Event::TaskNotifyTakeBlock {
2377                    task,
2378                    name,
2379                    index,
2380                });
2381                self.add_current_task_to_delayed_list(ticks, true)?;
2382            }
2383            let already_yielded = self.resume_all();
2384            if should_block && !already_yielded {
2385                if self.current == caller {
2386                    self.port_yield();
2387                } else {
2388                    self.owe_yield(caller);
2389                }
2390            }
2391            self.set_notify_blocked(caller, true);
2392            return Ok(Wait::Blocked);
2393        }
2394        self.set_notify_blocked(caller, false);
2395        self.enter_critical();
2396        self.note_exits();
2397        self.trace_task(caller, |task, name| Event::TaskNotifyTake {
2398            task,
2399            name,
2400            index,
2401        });
2402        // One resolve for the read and both writes. `notified_value_of`
2403        // resolved the TCB to read the value and this line resolved it again
2404        // to write it back -- the same trade `unlock_queue` makes, and a
2405        // `&mut self` call sits between this and the read at the top of the
2406        // function, so the two cannot be folded by the compiler.
2407        let mut value = 0;
2408        if let Ok(tcb) = self.tcbs.resolve_mut(caller) {
2409            value = tcb.notified.get(index).copied().unwrap_or(0);
2410            if value != 0 {
2411                if let Some(slot) = tcb.notified.get_mut(index) {
2412                    // Guarded by `value != 0` above, so the saturation
2413                    // never fires; it is here because the workspace forbids
2414                    // bare arithmetic, and a decrement is exactly the place
2415                    // an unguarded one would wrap.
2416                    *slot = if clear_on_exit {
2417                        0
2418                    } else {
2419                        value.saturating_sub(1)
2420                    };
2421                }
2422            }
2423            if let Some(slot) = tcb.notify_state.get_mut(index) {
2424                *slot = NotifyState::NotWaiting;
2425            }
2426        }
2427        self.exit_critical();
2428        Ok(Wait::Ready(value))
2429    }
2430
2431    /// `xTaskGetHandle`: the task registered under `name`.
2432    ///
2433    /// # It is not free, and that is the point
2434    ///
2435    /// The C walks every ready list, then the delayed lists, then the
2436    /// suspended and waiting-termination lists, all inside
2437    /// `vTaskSuspendAll` / `xTaskResumeAll` — and `xTaskResumeAll` takes a
2438    /// critical section. So a lookup that emits **no trace event** still
2439    /// costs **one critical-section exit**, which under the sim contract is
2440    /// one unit of time.
2441    ///
2442    /// That is why this exists rather than a scenario keeping the handle it
2443    /// was given at creation. `AbortDelay`'s remake did exactly that, on the
2444    /// reasoning that a lookup emitting no event could not change the trace,
2445    /// and the corpus caught it: every event still agreed and the
2446    /// exit column was one short at the first block.
2447    ///
2448    /// The arena is searched instead of five lists, which cannot change the
2449    /// answer — a live task is in exactly one of them — and does not change
2450    /// the accounting either, because the cost is the suspend/resume pair.
2451    ///
2452    /// # Errors
2453    /// [`Error::Gone`] when no live task carries that name.
2454    pub fn task_get_handle(&mut self, name: &str) -> Result<TaskHandle> {
2455        self.suspend_all();
2456        let mut found = None;
2457        for index in 0..u16::try_from(self.tcbs.capacity()).unwrap_or(u16::MAX) {
2458            let Some(handle) = self.tcbs.handle_at(index) else {
2459                continue;
2460            };
2461            if self
2462                .tcbs
2463                .resolve(handle)
2464                .is_ok_and(|tcb| tcb.name.matches(name))
2465            {
2466                found = Some(handle);
2467                break;
2468            }
2469        }
2470        let _ = self.resume_all();
2471        found.ok_or(Error::Gone)
2472    }
2473
2474    /// `xTaskGenericNotify`.
2475    ///
2476    /// # Errors
2477    /// [`Error::InvalidArgument`] for a bad index; [`Error::Gone`] for a
2478    /// stale handle.
2479    pub fn notify(
2480        &mut self,
2481        task: TaskHandle,
2482        index: usize,
2483        value: u32,
2484        action: NotifyAction,
2485    ) -> Result<bool> {
2486        if index >= C::NOTIFICATION_ARRAY_ENTRIES {
2487            return Err(Error::InvalidArgument);
2488        }
2489        self.enter_critical();
2490        let result = self.notify_locked(task, index, value, action, false);
2491        self.exit_critical();
2492        result.map(|(ok, _)| ok)
2493    }
2494
2495    /// `xTaskGenericNotifyFromISR`: the same, without a critical section
2496    /// that costs anything, and putting a woken task on the pending-ready
2497    /// list when the scheduler is suspended.
2498    ///
2499    /// # Errors
2500    /// As [`Kernel::notify`].
2501    pub fn notify_from_isr(
2502        &mut self,
2503        task: TaskHandle,
2504        index: usize,
2505        value: u32,
2506        action: NotifyAction,
2507    ) -> Result<(bool, Woken)> {
2508        if index >= C::NOTIFICATION_ARRAY_ENTRIES {
2509            return Err(Error::InvalidArgument);
2510        }
2511        let mask = self.port.enter_critical_from_isr();
2512        let result = self.notify_locked(task, index, value, action, true);
2513        self.port.exit_critical_from_isr(mask);
2514        result.map(|(ok, woken)| (ok, if woken { Woken::YES } else { Woken::NO }))
2515    }
2516
2517    /// `xTaskGenericNotify` with its `pulPreviousNotificationValue`
2518    /// out-parameter filled: `xTaskNotifyAndQuery`.
2519    ///
2520    /// It exists because the answer has to come out of the SAME critical
2521    /// section as the notification. Reading [`Kernel::notify_value`] first
2522    /// and then notifying yields the same two numbers and costs a second
2523    /// critical section -- and on the sim a critical-section exit is a
2524    /// tick opportunity, so the extra one moves the tick and the trace
2525    /// stops matching the C. `TaskNotify.c` calls this eleven times.
2526    ///
2527    /// # Errors
2528    /// As [`Kernel::notify`].
2529    pub fn notify_and_query(
2530        &mut self,
2531        task: TaskHandle,
2532        index: usize,
2533        value: u32,
2534        action: NotifyAction,
2535    ) -> Result<(bool, u32)> {
2536        if index >= C::NOTIFICATION_ARRAY_ENTRIES {
2537            return Err(Error::InvalidArgument);
2538        }
2539        self.enter_critical();
2540        let previous = self
2541            .tcbs
2542            .resolve(task)
2543            .map(|tcb| tcb.notified.get(index).copied().unwrap_or(0));
2544        let result = self.notify_locked(task, index, value, action, false);
2545        self.exit_critical();
2546        Ok((result?.0, previous?))
2547    }
2548
2549    /// `xTaskGenericNotifyAndQueryFromISR`.
2550    ///
2551    /// # Errors
2552    /// As [`Kernel::notify`].
2553    pub fn notify_and_query_from_isr(
2554        &mut self,
2555        task: TaskHandle,
2556        index: usize,
2557        value: u32,
2558        action: NotifyAction,
2559    ) -> Result<(bool, u32, Woken)> {
2560        if index >= C::NOTIFICATION_ARRAY_ENTRIES {
2561            return Err(Error::InvalidArgument);
2562        }
2563        let mask = self.port.enter_critical_from_isr();
2564        let previous = self
2565            .tcbs
2566            .resolve(task)
2567            .map(|tcb| tcb.notified.get(index).copied().unwrap_or(0));
2568        let result = self.notify_locked(task, index, value, action, true);
2569        self.port.exit_critical_from_isr(mask);
2570        let (ok, woken) = result?;
2571        Ok((ok, previous?, if woken { Woken::YES } else { Woken::NO }))
2572    }
2573
2574    /// The body both notify paths share.
2575    fn notify_locked(
2576        &mut self,
2577        task: TaskHandle,
2578        index: usize,
2579        value: u32,
2580        action: NotifyAction,
2581        from_isr: bool,
2582    ) -> Result<(bool, bool)> {
2583        let original = self.notify_state_of(task, index);
2584        let mut ok = true;
2585        {
2586            let tcb = self.tcbs.resolve_mut(task)?;
2587            if let Some(slot) = tcb.notify_state.get_mut(index) {
2588                *slot = NotifyState::Received;
2589            }
2590            if let Some(slot) = tcb.notified.get_mut(index) {
2591                match action {
2592                    NotifyAction::SetBits => *slot |= value,
2593                    NotifyAction::Increment => *slot = slot.wrapping_add(1),
2594                    NotifyAction::Overwrite => *slot = value,
2595                    NotifyAction::NoOverwrite => {
2596                        if original == NotifyState::Received {
2597                            ok = false;
2598                        } else {
2599                            *slot = value;
2600                        }
2601                    }
2602                    NotifyAction::None => {}
2603                }
2604            }
2605        }
2606        // `traceTASK_NOTIFY` is hooked; `traceTASK_NOTIFY_FROM_ISR` is not,
2607        // so an interrupt's notification says nothing on either side.
2608        if !from_isr {
2609            self.note_exits();
2610            self.trace_task(task, |t, name| Event::TaskNotify {
2611                task: t,
2612                name,
2613                index,
2614            });
2615        }
2616        let mut woke_higher = false;
2617        if original == NotifyState::Waiting {
2618            let item = Self::state_item(task);
2619            if from_isr && self.suspended_depth != 0 {
2620                let _ = self.lists.remove(Self::event_item(task));
2621                let value = self.lists.value(Self::event_item(task))?;
2622                self.lists
2623                    .insert(Self::pending_ready_list(), Self::event_item(task), value)?;
2624            } else {
2625                if self.lists.container(item)?.is_some() {
2626                    let _ = self.lists.remove(item);
2627                }
2628                self.add_task_to_ready_list(task)?;
2629            }
2630            let woken = self.tcbs.resolve(task).map(|t| t.priority).unwrap_or(0);
2631            if woken > self.current_priority() {
2632                woke_higher = true;
2633                if from_isr {
2634                    // The C sets `xYieldPendings[ 0 ]` here as well as
2635                    // reporting the wake through the caller's flag — so an
2636                    // interrupt that discards the flag still gets the
2637                    // switch, on the way out of `xTaskIncrementTick`. That
2638                    // is why the tick hook runs before the yield-pending
2639                    // test and not after it.
2640                    self.yield_pending = true;
2641                } else {
2642                    // taskYIELD_ANY_CORE_IF_USING_PREEMPTION, inside the
2643                    // section.
2644                    self.port_yield();
2645                }
2646            }
2647        }
2648        Ok((ok, woke_higher))
2649    }
2650
2651    /// `xTaskGenericNotifyStateClear`. `None` is the calling task.
2652    ///
2653    /// # Errors
2654    /// As [`Kernel::notify`].
2655    pub fn notify_state_clear(&mut self, task: Option<TaskHandle>, index: usize) -> Result<bool> {
2656        if index >= C::NOTIFICATION_ARRAY_ENTRIES {
2657            return Err(Error::InvalidArgument);
2658        }
2659        let target = task.unwrap_or(self.current);
2660        self.enter_critical();
2661        let cleared = self.notify_state_of(target, index) == NotifyState::Received;
2662        if cleared {
2663            if let Ok(tcb) = self.tcbs.resolve_mut(target) {
2664                if let Some(slot) = tcb.notify_state.get_mut(index) {
2665                    *slot = NotifyState::NotWaiting;
2666                }
2667            }
2668        }
2669        self.exit_critical();
2670        Ok(cleared)
2671    }
2672
2673    /// `ulNotifiedValue[ index ]` for a task. `None` is the calling task.
2674    ///
2675    /// The C reaches this through `xTaskNotifyAndQuery`, which hands back
2676    /// the value a notification is about to REPLACE, and through
2677    /// `ulTaskNotifyValueClear`. Neither could be implemented without it:
2678    /// `xTaskNotifyAndQuery` is `xTaskGenericNotify` with a
2679    /// `pulPreviousNotificationValue` out-parameter, and `TaskNotify.c:373`
2680    /// asserts on what comes back. The field existed; only the way to read
2681    /// it was missing, which is the kind of gap a C ABI finds and a Rust
2682    /// face never does.
2683    ///
2684    /// # Errors
2685    /// `InvalidArgument` if `index` is outside the notification array, or
2686    /// the resolve error if the handle is stale.
2687    pub fn notify_value(&mut self, task: Option<TaskHandle>, index: usize) -> Result<u32> {
2688        if index >= C::NOTIFICATION_ARRAY_ENTRIES {
2689            return Err(Error::InvalidArgument);
2690        }
2691        let target = task.unwrap_or(self.current);
2692        self.enter_critical();
2693        let value = self
2694            .tcbs
2695            .resolve(target)
2696            .map(|tcb| tcb.notified.get(index).copied().unwrap_or(0));
2697        self.exit_critical();
2698        value
2699    }
2700
2701    /// `ulTaskGenericNotifyValueClear`: clear `bits` in the task's
2702    /// notification value and answer what it was BEFORE the clear.
2703    ///
2704    /// # Errors
2705    /// As [`Kernel::notify_value`].
2706    pub fn notify_value_clear(
2707        &mut self,
2708        task: Option<TaskHandle>,
2709        index: usize,
2710        bits: u32,
2711    ) -> Result<u32> {
2712        if index >= C::NOTIFICATION_ARRAY_ENTRIES {
2713            return Err(Error::InvalidArgument);
2714        }
2715        let target = task.unwrap_or(self.current);
2716        self.enter_critical();
2717        let before = match self.tcbs.resolve_mut(target) {
2718            Ok(tcb) => match tcb.notified.get_mut(index) {
2719                Some(slot) => {
2720                    let was = *slot;
2721                    *slot &= !bits;
2722                    Ok(was)
2723                }
2724                None => Err(Error::InvalidArgument),
2725            },
2726            Err(e) => Err(e),
2727        };
2728        self.exit_critical();
2729        before
2730    }
2731
2732    /// Whether `task` is part-way through a notification wait — it blocked
2733    /// once and has not yet run the half of `xTaskGenericNotifyWait` that
2734    /// happens when a task wakes.
2735    ///
2736    /// A caller that blocks on a notification needs this: the C's wait
2737    /// returns *after* the wake, so its second half always runs, and a
2738    /// stackless caller that decided not to block again would otherwise
2739    /// skip it and leave the slot marked as received for ever.
2740    #[must_use]
2741    pub fn notify_wait_pending(&self, task: TaskHandle) -> bool {
2742        self.notify_blocked(task)
2743    }
2744
2745    /// Whether `task` has a stream-buffer call to resume, and the local it
2746    /// left behind. Taking it clears the marker.
2747    pub(crate) fn take_stream_resume(&mut self, task: TaskHandle) -> Option<usize> {
2748        let tcb = self.tcbs.resolve_mut(task).ok()?;
2749        if !tcb.stream_resume {
2750            return None;
2751        }
2752        tcb.stream_resume = false;
2753        Some(tcb.stream_local)
2754    }
2755
2756    /// Remember where a preempted stream-buffer call has to start again.
2757    pub(crate) fn set_stream_resume(&mut self, task: TaskHandle, local: usize) {
2758        if let Ok(tcb) = self.tcbs.resolve_mut(task) {
2759            tcb.stream_resume = true;
2760            tcb.stream_local = local;
2761        }
2762    }
2763
2764    /// Whether `task` has a queue call to resume below its sampling exit.
2765    /// Taking it clears the marker.
2766    pub(crate) fn take_queue_resume(&mut self, task: TaskHandle) -> QueueResume {
2767        // Nobody is parked at a sampling exit, so there is nothing to read.
2768        // This is the answer on all but a handful of queue calls, and it costs
2769        // one field load where resolving the TCB costs an arena lookup.
2770        if self.queue_resumes == 0 {
2771            return QueueResume::No;
2772        }
2773        let Ok(tcb) = self.tcbs.resolve_mut(task) else {
2774            return QueueResume::No;
2775        };
2776        let resume = tcb.queue_resume;
2777        // Peek before clearing, the same trade `settle_unwind` makes: every
2778        // queue send and every queue receive passes through here, and on all
2779        // but the handful that were preempted at a sampling exit the slot is
2780        // already `No` — so the unconditional write was a store, on every
2781        // queue call, to clear something already clear.
2782        if resume != QueueResume::No {
2783            tcb.queue_resume = QueueResume::No;
2784            self.queue_resumes = self.queue_resumes.saturating_sub(1);
2785        }
2786        resume
2787    }
2788
2789    /// Remember that a queue call was preempted at its sampling exit.
2790    ///
2791    /// No local travels with it, unlike [`Kernel::set_stream_resume`]: the C
2792    /// re-reads the queue under `prvLockQueue` on the other side of the
2793    /// exit, so there is nothing sampled to carry.
2794    pub(crate) fn set_queue_resume(&mut self, task: TaskHandle, at: QueueResume) {
2795        debug_assert_ne!(
2796            at,
2797            QueueResume::No,
2798            "set_queue_resume only ever parks a task; clearing is take's job, and the summary count depends on that"
2799        );
2800        if let Ok(tcb) = self.tcbs.resolve_mut(task) {
2801            // Count the slot, not the call: re-parking a task already parked
2802            // replaces its slot and must not be counted twice.
2803            if tcb.queue_resume == QueueResume::No {
2804                self.queue_resumes = self.queue_resumes.wrapping_add(1);
2805            }
2806            tcb.queue_resume = at;
2807        }
2808    }
2809
2810    /// Has this task's blocking send already paid for `vTaskSetTimeOutState`?
2811    ///
2812    /// A one-shot, like [`Kernel::take_stream_resume`], and for the same
2813    /// reason: `vTaskSetTimeOutState`'s own exit can release a tick and
2814    /// switch the caller away, and the C's thread then resumes **below** it,
2815    /// in the sampling loop. Running it again on re-entry would spend a
2816    /// second exit the C never spends -- which is a sixteenth of a tick, and
2817    /// `StreamBufferDemo`'s echo client hit it at tick 419.
2818    pub(crate) fn take_stream_timed(&mut self, task: TaskHandle) -> bool {
2819        let Ok(tcb) = self.tcbs.resolve_mut(task) else {
2820            return false;
2821        };
2822        let was = tcb.stream_timed;
2823        tcb.stream_timed = false;
2824        was
2825    }
2826
2827    /// Remember that the timeout state is set and must not be set again.
2828    pub(crate) fn set_stream_timed(&mut self, task: TaskHandle) {
2829        if let Ok(tcb) = self.tcbs.resolve_mut(task) {
2830            tcb.stream_timed = true;
2831        }
2832    }
2833
2834    /// Has this task's stream-buffer call already finished its wait?
2835    ///
2836    /// The other half of [`Kernel::take_stream_resume`]. A call can be
2837    /// preempted at two different exits, and the two resume in different
2838    /// places: at the SAMPLING exit the C goes on to block, and at the
2839    /// WAIT's own exit it goes on to move the bytes and trace them. Without
2840    /// this the second case is indistinguishable from the first, and a call
2841    /// that had already waited would wait again.
2842    pub(crate) fn take_stream_waited(&mut self, task: TaskHandle) -> bool {
2843        let Ok(tcb) = self.tcbs.resolve_mut(task) else {
2844            return false;
2845        };
2846        let was = tcb.stream_waited;
2847        tcb.stream_waited = false;
2848        was
2849    }
2850
2851    /// Remember that the wait is done and only the transfer is left.
2852    pub(crate) fn set_stream_waited(&mut self, task: TaskHandle) {
2853        if let Ok(tcb) = self.tcbs.resolve_mut(task) {
2854            tcb.stream_waited = true;
2855        }
2856    }
2857
2858    fn notify_blocked(&self, task: TaskHandle) -> bool {
2859        self.tcbs
2860            .resolve(task)
2861            .map(|t| t.notify_blocked)
2862            .unwrap_or(false)
2863    }
2864
2865    fn set_notify_blocked(&mut self, task: TaskHandle, blocked: bool) {
2866        if let Ok(tcb) = self.tcbs.resolve_mut(task) {
2867            tcb.notify_blocked = blocked;
2868        }
2869    }
2870
2871    fn notify_state_of(&self, task: TaskHandle, index: usize) -> NotifyState {
2872        self.tcbs
2873            .resolve(task)
2874            .ok()
2875            .and_then(|t| t.notify_state.get(index).copied())
2876            .unwrap_or(NotifyState::NotWaiting)
2877    }
2878
2879    fn notified_value_of(&self, task: TaskHandle, index: usize) -> u32 {
2880        self.tcbs
2881            .resolve(task)
2882            .ok()
2883            .and_then(|t| t.notified.get(index).copied())
2884            .unwrap_or(0)
2885    }
2886
2887    /// `xTaskGetTickCountFromISR`.
2888    ///
2889    /// No critical section, exactly as `xTaskGetTickCount` takes none: the
2890    /// Posix port sets `portTICK_TYPE_IS_ATOMIC`, so reading the count is
2891    /// a single load on both sides and costs no sim time.
2892    #[must_use]
2893    pub const fn tick_count_from_isr(&self) -> u64 {
2894        self.tick
2895    }
2896
2897    /// `vTaskMissedYield`: a yield that could not be taken where it was
2898    /// asked for — because a task is walking an event list, or because the
2899    /// scheduler is suspended — and must happen on the way out instead.
2900    pub(crate) fn missed_yield(&mut self) {
2901        self.yield_pending = true;
2902    }
2903
2904    /// `vApplicationTickHook()`, when `configUSE_TICK_HOOK` is 1.
2905    ///
2906    /// The hook is copied out, run, and the result stored: that is what
2907    /// lets it borrow the kernel mutably while the kernel owns it. A hook
2908    /// that reads the kernel's own copy of itself therefore sees the value
2909    /// from before this call.
2910    fn run_tick_hook(&mut self) {
2911        if !C::USE_TICK_HOOK {
2912            return;
2913        }
2914        let hook = self.tick_hook;
2915        self.tick_hook = hook.tick(self);
2916    }
2917
2918    /// The tick hook, as it now stands.
2919    ///
2920    /// A scenario's `xAre...StillRunning()` reads the status its interrupt
2921    /// half latched, so the owner of the kernel needs to see it.
2922    pub const fn tick_hook(&self) -> &H {
2923        &self.tick_hook
2924    }
2925
2926    /// The tick hook, to install or reset one after construction.
2927    pub const fn tick_hook_mut(&mut self) -> &mut H {
2928        &mut self.tick_hook
2929    }
2930
2931    /// The wake loop inside `xTaskIncrementTick`.
2932    // Out of line: this walks the delayed list and runs only when a tick
2933    // reaches the next unblock time, but `increment_tick` runs on EVERY tick
2934    // and was carrying a frame sized for the walk regardless.
2935    #[inline(never)]
2936    fn wake_due_tasks(&mut self, now: u64) -> bool {
2937        let mut switch_required = false;
2938        // Hoisted: see the note at the bottom of the loop.
2939        let running = if C::USE_PREEMPTION {
2940            self.current_priority()
2941        } else {
2942            0
2943        };
2944        loop {
2945            let delayed = self.delayed_list();
2946            if self.lists.is_empty_of(delayed) {
2947                self.next_unblock_time = Self::MAX_DELAY;
2948                return switch_required;
2949            }
2950            let Ok(Some(item)) = self.lists.head(delayed) else {
2951                self.next_unblock_time = Self::MAX_DELAY;
2952                return switch_required;
2953            };
2954            let Ok(wake_at) = self.lists.value(item) else {
2955                return switch_required;
2956            };
2957            if now < wake_at {
2958                self.next_unblock_time = wake_at;
2959                return switch_required;
2960            }
2961            let Ok(task) = self.task_of_state_item(item) else {
2962                return switch_required;
2963            };
2964            let _ = self.lists.remove(item);
2965            if self
2966                .lists
2967                .container(Self::event_item(task))
2968                .unwrap_or(None)
2969                .is_some()
2970            {
2971                let _ = self.lists.remove(Self::event_item(task));
2972            }
2973            if self.add_task_to_ready_list(task).is_err() {
2974                return switch_required;
2975            }
2976            // `!switch_required` FIRST, and the running priority read once
2977            // for the whole drain.
2978            //
2979            // Both of these cost a TCB resolve -- a generation check, a
2980            // bounds check and an `Option` -- and this loop runs once per
2981            // task the tick wakes. `self.current` cannot move while the
2982            // drain is running (nothing here switches), so the running
2983            // priority is a loop invariant that was being re-derived on
2984            // every lap. And once a switch is already required, asking again
2985            // can only set a `true` to `true`, which is not worth the
2986            // resolve it costs -- the same reasoning `increment_tick`
2987            // already applies one level up.
2988            if C::USE_PREEMPTION && !switch_required {
2989                let woken = self.tcbs.resolve(task).map(|t| t.priority).unwrap_or(0);
2990                if woken > running {
2991                    switch_required = true;
2992                }
2993            }
2994        }
2995    }
2996
2997    /// `taskSWITCH_DELAYED_LISTS()`.
2998    // Out of line for the same reason: the overflow swap happens when the
2999    // tick count wraps, which is once in a very long while.
3000    // In line at its ONE caller (A3): win 26. It carried #[inline(never)] AND a
3001    // later #[inline] together, so the A3 change was dead from the day it was
3002    // written -- and rustc said so on every build.
3003    #[inline(always)]
3004    fn switch_delayed_lists(&mut self) {
3005        self.delayed_swapped = !self.delayed_swapped;
3006        self.overflows = self.overflows.wrapping_add(1);
3007        self.reset_next_task_unblock_time();
3008    }
3009
3010    /// `prvResetNextTaskUnblockTime`.
3011    ///
3012    /// ★ The EMPTY case is `MAX_DELAY`, not the list's own maximum.
3013    ///
3014    /// `head_value` cannot answer "empty": on an empty list the head IS the end
3015    /// marker, whose value is `u64::MAX` so that sorted inserts always find a
3016    /// larger value to stop at. So `unwrap_or` never fired and a reset over an
3017    /// empty delayed list stored `u64::MAX`, where the C stores `portMAX_DELAY`:
3018    ///
3019    /// ```c
3020    /// if( listLIST_IS_EMPTY( pxDelayedTaskList ) != pdFALSE ) {
3021    ///     xNextTaskUnblockTime = portMAX_DELAY;
3022    /// ```
3023    ///
3024    /// Unobservable in the corpus -- the difference only shows at a tick equal
3025    /// to `MAX_DELAY`, and `switch_delayed_lists` resets at the wrap anyway --
3026    /// which is why a test had PINNED the divergence rather than a gate
3027    /// catching it. Asking the emptiness question directly matches the C and
3028    /// makes `next_unblock_time <= MAX_DELAY` an invariant of the field.
3029    ///
3030    /// That invariant is worth five instructions per TICK: `increment_tick`
3031    /// compares `next` against this field, and while the field could hold a
3032    /// value wider than the tick that comparison had to be a full 64-bit one on
3033    /// a 32-bit target -- a second load, a `snez` and an `or` on top of the
3034    /// ordinary compare. With the invariant true, the comparison masks to the
3035    /// tick width and collapses. `bench/tick-work`: tick_idle and tick_delayed
3036    /// 14 -> 9 against the C's 15, 0.93x -> 0.60x.
3037    /// # Out of line, and that is load-bearing
3038    ///
3039    /// `switch_delayed_lists` is `#[inline(always)]` (win 26) and it calls this,
3040    /// so this body lands inside `increment_tick` -- on the arm taken when the
3041    /// tick WRAPS, i.e. once in `MAX_DELAY` ticks. Asking the emptiness question
3042    /// above made the body bigger, and in line that cost the tick row
3043    /// **14 -> 34** on `bench/tick-work`: twenty instructions of register
3044    /// pressure on every tick, to serve an arm that had not run once in the
3045    /// measurement. `rusty-compiler-leverage` A2, and the largest single
3046    /// instance of it this kernel has produced.
3047    #[cold]
3048    #[inline(never)]
3049    fn reset_next_task_unblock_time(&mut self) {
3050        let delayed = self.delayed_list();
3051        self.next_unblock_time = if self.lists.is_empty_of(delayed) {
3052            Self::MAX_DELAY
3053        } else {
3054            self.lists.head_value(delayed).unwrap_or(Self::MAX_DELAY)
3055        };
3056    }
3057
3058    // ------------------------------------------------------------- delay --
3059
3060    /// `vTaskDelay`.
3061    ///
3062    /// # Errors
3063    /// A list error surfaces as itself.
3064    pub fn delay(&mut self, ticks: u64) -> Result<()> {
3065        let caller = self.current;
3066        let mut already_yielded = false;
3067        if ticks > 0 {
3068            self.suspend_all();
3069            {
3070                let current = self.current;
3071                self.trace_task(current, |task, name| Event::TaskDelay { task, name, ticks });
3072                self.add_current_task_to_delayed_list(ticks, false)?;
3073            }
3074            already_yielded = self.resume_all();
3075        }
3076        // taskYIELD_WITHIN_API(), outside any critical section — unless a
3077        // tick switched us out somewhere above, in which case this line is
3078        // on a stack that is not running, and runs when the task does.
3079        if !already_yielded {
3080            if self.current == caller {
3081                self.port_yield();
3082            } else {
3083                self.owe_yield(caller);
3084            }
3085        }
3086        Ok(())
3087    }
3088
3089    /// `xTaskAbortDelay`: pull a task out of the Blocked state early.
3090    ///
3091    /// `true` is `pdPASS` — the task really was blocked and is now ready.
3092    /// A task that was not blocked is left alone and `false` comes back,
3093    /// which is the C's `pdFAIL`.
3094    ///
3095    /// The shape matters as much as the effect: the whole thing runs with
3096    /// the scheduler suspended, the event list is touched inside a critical
3097    /// section of its own because an interrupt can reach it, and a yield
3098    /// that the higher priority of the woken task calls for is *pended*
3099    /// rather than taken, so it happens on the way out of `xTaskResumeAll`.
3100    ///
3101    /// # Errors
3102    /// [`Error::Gone`] for a stale handle.
3103    pub fn abort_delay(&mut self, task: TaskHandle) -> Result<bool> {
3104        if !self.tcbs.contains(task) {
3105            return Err(Error::Gone);
3106        }
3107        self.suspend_all();
3108        // eTaskGetState: a critical section of its own on any task but the
3109        // running one, and the running one is never Blocked.
3110        let blocked = self.task_state_get(task)? == TaskState::Blocked;
3111        if !blocked {
3112            let _ = self.resume_all();
3113            return Ok(false);
3114        }
3115        let item = Self::state_item(task);
3116        // `remove` is its own guard, as above.
3117        let _ = self.lists.remove(item);
3118        self.enter_critical();
3119        {
3120            let event = Self::event_item(task);
3121            // `remove` answers `NotActive` when the item is in no list, so
3122            // it is its own guard -- and `is_ok` is exactly "something was
3123            // removed", which is what the flag below depends on.
3124            if self.lists.remove(event).is_ok() {
3125                if let Some(f) = self.delay_aborted.get_mut(task.index() as usize) {
3126                    *f = true;
3127                }
3128            }
3129        }
3130        self.exit_critical();
3131        self.add_task_to_ready_list(task)?;
3132        // configUSE_PREEMPTION, one core: pend the yield rather than take
3133        // it, so it lands where `xTaskResumeAll` puts it.
3134        let woken = self.tcbs.resolve(task).map(|t| t.priority).unwrap_or(0);
3135        if woken > self.current_priority() {
3136            self.yield_pending = true;
3137        }
3138        let _ = self.resume_all();
3139        Ok(true)
3140    }
3141
3142    /// `prvAddCurrentTaskToDelayedList`.
3143    pub(crate) fn add_current_task_to_delayed_list(
3144        &mut self,
3145        ticks: u64,
3146        can_block_indefinitely: bool,
3147    ) -> Result<()> {
3148        // Both masked, and for the reason `increment_tick`'s comparison is: at a
3149        // 32-bit tick width the high half of every tick value is invariantly
3150        // zero, LLVM cannot know that of a field it loaded or a parameter it was
3151        // handed, and without being told it emits full 64-bit compares on a
3152        // 32-bit target. Three of them live below -- `ticks == MAX_DELAY`,
3153        // `wake_at < now`, and `wake_at < next_unblock_time`.
3154        //
3155        // `self.tick` is masked by every writer (`increment_tick` and
3156        // `step_tick` both `& MAX_DELAY`). `ticks` reaches here from
3157        // `check_for_timeout`, whose answers are all at most `MAX_DELAY`, and
3158        // from `begin_wait`, which truncates what it stores. At a 64-bit width
3159        // `MAX_DELAY` is `u64::MAX` and both masks fold to nothing.
3160        debug_assert_eq!(
3161            self.tick,
3162            self.tick & Self::MAX_DELAY,
3163            "the tick is wider than its own width"
3164        );
3165        let now = self.tick & Self::MAX_DELAY;
3166        let ticks = ticks & Self::MAX_DELAY;
3167        let current = self.current;
3168        // B1, and this function is where it pays most: by its own note below it
3169        // is the single largest consumer of the blocking workload, and it
3170        // derives FOUR bound-checked accesses from an index it read out of
3171        // memory -- `delay_aborted`, then `state_item` feeding `lists.remove`
3172        // and one of three inserts. `self.current` is a live task on every path
3173        // that reaches here, but it is a FIELD, so nothing carries that across
3174        // the calls above.
3175        if current.index() as usize >= TASKS {
3176            return Err(Error::Gone);
3177        }
3178        // About to enter a delayed list, so the abort flag is cleared here
3179        // and can only be seen set by a task that really was aborted.
3180        if let Some(f) = self.delay_aborted.get_mut(current.index() as usize) {
3181            *f = false;
3182        }
3183        let item = Self::state_item(current);
3184        // `uxListRemove` already answers `NotActive` for an item that is
3185        // in no list, and both it and the container test are one read of
3186        // the same node — so asking first was reading it twice. This is
3187        // the running task's state item, so it is in the ready list and
3188        // the test passed anyway.
3189        let _ = self.lists.remove(item);
3190        if ticks == Self::MAX_DELAY && can_block_indefinitely {
3191            self.lists.insert_end(Self::suspended_list(), item)?;
3192            return Ok(());
3193        }
3194        let wake_at = now.wrapping_add(ticks) & Self::MAX_DELAY;
3195        // `vListInsert` sets the item's value from the one it sorts by, so
3196        // both arms below write `wake_at` themselves. Setting it here as
3197        // well was a second lookup of the same item to store the same
3198        // number into it.
3199        if wake_at < now {
3200            self.trace_task(current, |task, name| {
3201                Event::MovedTaskToOverflowDelayedList { task, name }
3202            });
3203            let list = self.overflow_delayed_list();
3204            self.lists.insert(list, item, wake_at)?;
3205        } else {
3206            self.trace_task(current, |task, name| Event::MovedTaskToDelayedList {
3207                task,
3208                name,
3209            });
3210            let list = self.delayed_list();
3211            // ---- append, when the wake time says we may ------------------
3212            //
3213            // `vListInsert` walks from the head until it finds a larger
3214            // value, so a delayed list `n` deep costs `n` steps -- and this
3215            // function is the single largest consumer of the blocking
3216            // workload, most of it that walk.
3217            //
3218            // The walk is almost always finding the same answer: the END.
3219            // `wake_at` is `now + ticks` and `now` only increases, so tasks
3220            // blocking with comparable timeouts produce ASCENDING wake times
3221            // and belong after everything already there.
3222            //
3223            // `insert_sorted` takes that shortcut, and it asks this caller
3224            // for exactly ONE thing: that the list is already sorted. The
3225            // delayed list is, because it is only ever built by sorted
3226            // inserts and by this append -- so its last item carries its
3227            // largest value.
3228            //
3229            // The other two promises this call site used to make are gone
3230            // into the list, where they are written once instead of at
3231            // every future call site: the `>=` tie rule, and the fact that
3232            // `insert_end` only appends while the cursor is at the marker.
3233            // Both were silent when wrong. See `ListsOf::insert_sorted`,
3234            // and `ListsOf::is_sorted` for checking the one that is left.
3235            self.lists.insert_sorted(list, item, wake_at)?;
3236            // Masked for the same reason `increment_tick`'s comparison is, and
3237            // it is the second site of that win: `next_unblock_time <=
3238            // MAX_DELAY` is an invariant of the field (see
3239            // `reset_next_task_unblock_time`, which is what made it one), and
3240            // `wake_at` was masked where it was computed above. So at a 32-bit
3241            // tick width the high half of both is invariantly zero, and without
3242            // saying so LLVM emits a full 64-bit compare on a 32-bit target --
3243            // a second load, a `snez` and an `or` on top of the ordinary one.
3244            //
3245            // At a 64-bit width `MAX_DELAY` is `u64::MAX` and the mask folds to
3246            // nothing, so that configuration pays no instruction for this.
3247            debug_assert_eq!(
3248                self.next_unblock_time,
3249                self.next_unblock_time & Self::MAX_DELAY,
3250                "next_unblock_time holds a value wider than the tick"
3251            );
3252            if wake_at < self.next_unblock_time & Self::MAX_DELAY {
3253                self.next_unblock_time = wake_at;
3254            }
3255        }
3256        Ok(())
3257    }
3258
3259    // --------------------------------------------------- suspend / resume --
3260
3261    /// `vTaskSuspend`. `None` suspends the calling task.
3262    ///
3263    /// # Errors
3264    /// [`Error::Gone`] for a stale handle.
3265    pub fn suspend(&mut self, task: Option<TaskHandle>) -> Result<()> {
3266        let caller = self.current;
3267        let target = task.unwrap_or(caller);
3268        self.enter_critical();
3269        {
3270            if !self.tcbs.contains(target) {
3271                self.exit_critical();
3272                return Err(Error::Gone);
3273            }
3274            self.trace_task(target, |task, name| Event::TaskSuspend { task, name });
3275            let item = Self::state_item(target);
3276            // `remove` is its own guard: it answers `NotActive` for an item
3277            // in no list, and the result was discarded either way.
3278            let _ = self.lists.remove(item);
3279            let event = Self::event_item(target);
3280            if self.lists.container(event)?.is_some() {
3281                let _ = self.lists.remove(event);
3282            }
3283            self.lists.insert_end(Self::suspended_list(), item)?;
3284            // `vTaskSuspend`, `tasks.c`:
3285            //
3286            // ```c
3287            // if( pxTCB->ucNotifyState[ x ] == taskWAITING_NOTIFICATION )
3288            // {
3289            //     /* The task was blocked to wait for a notification, but
3290            //      * is now suspended, so no notification was received. */
3291            //     pxTCB->ucNotifyState[ x ] = taskNOT_WAITING_NOTIFICATION;
3292            // }
3293            // ```
3294            //
3295            // Not tidying: `eTaskGetState` calls a task on the suspended
3296            // list BLOCKED rather than SUSPENDED if any of its notification
3297            // slots is still waiting, so leaving the flag set makes a
3298            // suspended task report as blocked for ever.
3299            // `TaskNotify.c:498` asserts exactly that, in a timer callback
3300            // that suspends a task which is waiting for a notification --
3301            // and a task that reports the wrong state there is a task the
3302            // rest of that test never resumes correctly.
3303            if let Ok(tcb) = self.tcbs.resolve_mut(target) {
3304                for slot in &mut tcb.notify_state {
3305                    if *slot == NotifyState::Waiting {
3306                        *slot = NotifyState::NotWaiting;
3307                    }
3308                }
3309            }
3310        }
3311        self.exit_critical();
3312        // A second, separate critical section — two outermost exits, which
3313        // is what the C does and therefore what the tick count depends on.
3314        if self.running {
3315            self.enter_critical();
3316            self.reset_next_task_unblock_time();
3317            self.exit_critical();
3318        }
3319        if target == caller {
3320            if self.running {
3321                // portYIELD_WITHIN_API(), outside the section.
3322                if self.current == caller {
3323                    self.port_yield();
3324                } else {
3325                    self.owe_yield(caller);
3326                }
3327            } else if self.lists.len(Self::suspended_list()).unwrap_or(0) != self.task_count {
3328                self.switch_context();
3329            }
3330        }
3331        Ok(())
3332    }
3333
3334    /// `vTaskResume`.
3335    ///
3336    /// # Errors
3337    /// [`Error::Gone`] for a stale handle.
3338    pub fn resume(&mut self, task: TaskHandle) -> Result<()> {
3339        if task == self.current || task.is_null() {
3340            return Ok(());
3341        }
3342        if !self.tcbs.contains(task) {
3343            return Err(Error::Gone);
3344        }
3345        self.enter_critical();
3346        {
3347            if self.task_is_suspended(task)? {
3348                self.trace_task(task, |task, name| Event::TaskResume { task, name });
3349                let _ = self.lists.remove(Self::state_item(task));
3350                self.add_task_to_ready_list(task)?;
3351                // taskYIELD_ANY_CORE_IF_USING_PREEMPTION: inside the
3352                // section, and only when the resumed task outranks the
3353                // running one.
3354                let resumed = self.tcbs.resolve(task)?.priority;
3355                if C::USE_PREEMPTION && self.current_priority() < resumed {
3356                    self.port_yield();
3357                }
3358            }
3359        }
3360        self.exit_critical();
3361        Ok(())
3362    }
3363
3364    /// `prvTaskIsTaskSuspended`: on the suspended list, not on the pending
3365    /// ready list, and not waiting on an event.
3366    fn task_is_suspended(&self, task: TaskHandle) -> Result<bool> {
3367        if self.lists.container(Self::state_item(task))? != Some(Self::suspended_list()) {
3368            return Ok(false);
3369        }
3370        let event_list = self.lists.container(Self::event_item(task))?;
3371        if event_list == Some(Self::pending_ready_list()) {
3372            return Ok(false);
3373        }
3374        Ok(event_list.is_none())
3375    }
3376
3377    // -------------------------------------------------------- priorities --
3378
3379    /// `vTaskDelete`. `None` deletes the calling task.
3380    ///
3381    /// # Two paths, and the C picks between them for a reason
3382    ///
3383    /// Deleting *another* task frees its TCB on the spot. Deleting the
3384    /// **running** task cannot: the caller is still executing out of it. The
3385    /// C parks such a task on `xTasksWaitingTermination` and lets the idle
3386    /// task reclaim it, which is what `prvCheckTasksWaitingTermination` is
3387    /// for — so [`Kernel::check_tasks_waiting_termination`] is where the
3388    /// deferred half lands here, called from the idle body at the same point
3389    /// in the same loop.
3390    ///
3391    /// # The frees are outside the critical section, and they cost exits
3392    ///
3393    /// `prvDeleteTCB` runs **after** `taskEXIT_CRITICAL()` and frees twice —
3394    /// `vPortFreeStack( pxStack )` then `vPortFree( pxTCB )`. On the oracle's
3395    /// heap every free suspends the scheduler, so a delete is one exit for
3396    /// its own section plus two for the frees, in that order. Folding the
3397    /// frees into the section, or forgetting them, moves every later tick.
3398    ///
3399    /// # Errors
3400    /// [`Error::Gone`] for a stale handle.
3401    pub fn task_delete(&mut self, task: Option<TaskHandle>) -> Result<()> {
3402        // `prvGetTCBFromHandle`: NULL is the calling task.
3403        let target = task.unwrap_or(self.current);
3404        self.tcbs.resolve(target)?;
3405
3406        self.enter_critical();
3407        // `uxListRemove( &( pxTCB->xStateListItem ) )`. The C follows this
3408        // with `taskRESET_READY_PRIORITY`, which is an EMPTY MACRO under the
3409        // oracle's `configUSE_PORT_OPTIMISED_TASK_SELECTION 0` — there is no
3410        // priority bitmap to clear, and `vTaskSwitchContext` rediscovers the
3411        // top priority by walking down. Nothing to model.
3412        let state = Self::state_item(target);
3413        if matches!(self.lists.container(state), Ok(Some(_))) {
3414            let _ = self.lists.remove(state);
3415        }
3416        // `if( listLIST_ITEM_CONTAINER( &( pxTCB->xEventListItem ) ) != NULL )`
3417        // — a task blocked on a queue is on two lists, and both must let go.
3418        let event = Self::event_item(target);
3419        if matches!(self.lists.container(event), Ok(Some(_))) {
3420            let _ = self.lists.remove(event);
3421        }
3422        // `uxTaskNumber++` is not modelled: it exists so kernel-aware
3423        // debuggers can tell the task lists changed, and nothing the trace
3424        // records reads it.
3425
3426        // `xSchedulerRunning != pdFALSE && taskTASK_IS_RUNNING_OR_SCHEDULED_
3427        // _TO_YIELD( pxTCB )`, which at `configNUMBER_OF_CORES 1` is exactly
3428        // `pxTCB == pxCurrentTCB`.
3429        let defer = self.running && target == self.current;
3430        if defer {
3431            // `vListInsertEnd( &xTasksWaitingTermination, ... )` and
3432            // `++uxDeletedTasksWaitingCleanUp`. The count is NOT decremented
3433            // here — the idle task does that when it reaps.
3434            self.awaiting_reap = target;
3435            self.trace_task(target, |task, name| Event::TaskDelete { task, name });
3436        } else {
3437            self.task_count = self.task_count.saturating_sub(1);
3438            self.trace_task(target, |task, name| Event::TaskDelete { task, name });
3439            self.reset_next_task_unblock_time();
3440        }
3441        self.exit_critical();
3442
3443        // `if( xDeleteTCBInIdleTask != pdTRUE ) { prvDeleteTCB( pxTCB ); }`,
3444        // outside the section.
3445        if !defer {
3446            self.delete_tcb(target);
3447        }
3448
3449        // `taskYIELD_WITHIN_API()`. The C guards this with
3450        // `xSchedulerRunning && pxTCB == pxCurrentTCB`, which is the same
3451        // condition that chose the deferred path.
3452        if defer {
3453            self.port_yield();
3454        }
3455        Ok(())
3456    }
3457
3458    /// `prvDeleteTCB`: two frees, and on the oracle's heap each one suspends
3459    /// the scheduler, so each is one outermost exit.
3460    fn delete_tcb(&mut self, task: TaskHandle) {
3461        // `vPortFreeStack( pxTCB->pxStack )`.
3462        self.account_for_allocation();
3463        // `vPortFree( pxTCB )`.
3464        self.account_for_allocation();
3465        let _ = self.tcbs.remove(task);
3466
3467        // The index is now free for reuse, so mark the task UNSTARTED.
3468        //
3469        // The C frees the TCB and a later `xTaskCreate` gets fresh memory,
3470        // so a new task cannot inherit anything. Our arena hands back the
3471        // same index, and the per-index bookkeeping — owed exits, an owed
3472        // yield, an owed trace line — is keyed on that index, not on the
3473        // TCB. Without this a task deleted while it still owed the tail of
3474        // a call bequeaths that debt to its successor, and the successor
3475        // pays an exit it never incurred: exactly how `death`'s second
3476        // cycle first diverged, one exit early, 1,100 lines after the first
3477        // cycle had matched perfectly.
3478        //
3479        // Clearing this ONE flag is the whole fix, and deliberately so.
3480        // `hand_over` already empties all three of those on a task's first
3481        // switch-in, and a reused index is a first switch-in again. Zeroing
3482        // them here as well would work and would be worse: two places that
3483        // must agree about what a fresh task owes, and a gate that cannot
3484        // catch either one being dropped because the other still covers it.
3485        if let Some(f) = self.started.get_mut(task.index() as usize) {
3486            *f = false;
3487        }
3488    }
3489
3490    /// `prvCheckTasksWaitingTermination`, called from the idle task.
3491    ///
3492    /// # This must cost NOTHING when nothing is pending
3493    ///
3494    /// The C's body is `while( uxDeletedTasksWaitingCleanUp > 0 )`, so an
3495    /// idle loop with no deleted task takes no critical section and pays no
3496    /// exit. That is what lets this be wired into the idle body without
3497    /// disturbing a single scenario in the corpus — and it is the property
3498    /// the corpus is checking when it stays byte-identical.
3499    ///
3500    /// At most one task can be pending: only the *running* task defers, and
3501    /// it yields before it can return, so a second deferred delete cannot
3502    /// happen until this has run.
3503    pub fn check_tasks_waiting_termination(&mut self) {
3504        let task = self.awaiting_reap;
3505        if task.is_null() {
3506            return;
3507        };
3508        // The C takes the section per reaped task, decrements both counts
3509        // inside it, and calls `prvDeleteTCB` outside.
3510        self.enter_critical();
3511        self.awaiting_reap = TaskHandle::NULL;
3512        self.task_count = self.task_count.saturating_sub(1);
3513        self.exit_critical();
3514        self.delete_tcb(task);
3515    }
3516
3517    /// `vTaskPrioritySet`. `None` is the calling task.    /// `vTaskPrioritySet`. `None` is the calling task.
3518    ///
3519    /// # Errors
3520    /// [`Error::Gone`] for a stale handle.
3521    pub fn set_priority(&mut self, task: Option<TaskHandle>, new_priority: u8) -> Result<()> {
3522        let new_priority = new_priority.min(C::MAX_PRIORITIES.saturating_sub(1));
3523        let target = task.unwrap_or(self.current);
3524        let mut yield_required = false;
3525        self.enter_critical();
3526        {
3527            if !self.tcbs.contains(target) {
3528                self.exit_critical();
3529                return Err(Error::Gone);
3530            }
3531            self.trace_task(target, |task, name| Event::TaskPrioritySet {
3532                task,
3533                name,
3534                priority: Self::priority_value(new_priority),
3535            });
3536            let base = self.tcbs.resolve(target)?.base_priority;
3537            if base != new_priority {
3538                if new_priority > base {
3539                    if target != self.current && new_priority > self.current_priority() {
3540                        yield_required = true;
3541                    }
3542                } else if target == self.current {
3543                    yield_required = true;
3544                }
3545                let used_on_entry = self.tcbs.resolve(target)?.priority;
3546                {
3547                    let tcb = self.tcbs.resolve(target)?;
3548                    let raise = tcb.base_priority == tcb.priority || new_priority > tcb.priority;
3549                    if raise {
3550                        self.set_task_priority(target, new_priority)?;
3551                    }
3552                    self.tcbs.resolve_mut(target)?.base_priority = new_priority;
3553                }
3554                let event_value = u64::from(C::MAX_PRIORITIES.saturating_sub(new_priority));
3555                self.lists
3556                    .set_value(Self::event_item(target), event_value)?;
3557                let item = Self::state_item(target);
3558                if self.lists.container(item)? == Some(Self::ready_list(used_on_entry)) {
3559                    let _ = self.lists.remove(item);
3560                    self.add_task_to_ready_list(target)?;
3561                }
3562                // taskYIELD_TASK_CORE_IF_USING_PREEMPTION: inside the
3563                // section.
3564                if yield_required && C::USE_PREEMPTION {
3565                    self.port_yield();
3566                }
3567            }
3568        }
3569        self.exit_critical();
3570        Ok(())
3571    }
3572
3573    // ------------------------------------------------- scheduler suspend --
3574
3575    /// `vTaskSuspendAll`.
3576    pub fn suspend_all(&mut self) {
3577        self.suspended_depth = self.suspended_depth.wrapping_add(1);
3578    }
3579
3580    /// Move everything an ISR readied onto the ready lists.
3581    ///
3582    /// Out of line because it is the rare half of [`Kernel::resume_all`]: the
3583    /// pending list is empty on essentially every call, and inlining this made
3584    /// every one of those calls carry a frame sized for the walk.
3585    ///
3586    /// **The GUARD is inlined and only the WALK is out of line.** Outlining
3587    /// the whole thing — which is what this used to do — meant every call paid
3588    /// a call and a frame to discover there was nothing to do, on a path taken
3589    /// three times inside `queue_send_blocking` and three more inside
3590    /// `queue_take_blocking`. Asking "is the list empty" is one list read; the
3591    /// walk behind it is what wanted outlining.
3592    #[inline(always)]
3593    fn drain_pending_ready(&mut self) {
3594        if self.lists.is_empty_of(Self::pending_ready_list()) {
3595            // Empty, or a list error: either way the walk below moves nothing,
3596            // so `moved_any` would stay false and the reset would not happen.
3597            return;
3598        }
3599        self.drain_pending_ready_walk();
3600    }
3601
3602    /// The walk itself. See [`Kernel::drain_pending_ready`].
3603    #[cold]
3604    #[inline(never)]
3605    fn drain_pending_ready_walk(&mut self) {
3606        let mut moved_any = false;
3607        while !self.lists.is_empty_of(Self::pending_ready_list()) {
3608            let Ok(Some(item)) = self.lists.head(Self::pending_ready_list()) else {
3609                break;
3610            };
3611            let Ok(task) = self.task_of_event_item(item) else {
3612                break;
3613            };
3614            let _ = self.lists.remove(Self::event_item(task));
3615            let _ = self.lists.remove(Self::state_item(task));
3616            if self.add_task_to_ready_list(task).is_err() {
3617                break;
3618            }
3619            moved_any = true;
3620            let woken = self.tcbs.resolve(task).map(|t| t.priority).unwrap_or(0);
3621            if woken > self.current_priority() {
3622                self.yield_pending = true;
3623            }
3624        }
3625        if moved_any {
3626            self.reset_next_task_unblock_time();
3627        }
3628    }
3629
3630    /// Run the ticks that landed while the scheduler was suspended.
3631    ///
3632    /// Out of line for the same reason as its sibling: `pended_ticks` is zero
3633    /// on essentially every call — and, as there, **only the loop is out of
3634    /// line now**. The guard is a field read, and it also skips the
3635    /// `pended_ticks = 0` store that the zero case was writing over a zero.
3636    #[inline(always)]
3637    fn unwind_pended_ticks(&mut self) {
3638        if self.pended_ticks == 0 {
3639            return;
3640        }
3641        self.unwind_pended_ticks_loop();
3642    }
3643
3644    /// The loop itself. See [`Kernel::unwind_pended_ticks`].
3645    #[cold]
3646    #[inline(never)]
3647    fn unwind_pended_ticks_loop(&mut self) {
3648        let mut pended = self.pended_ticks;
3649        while pended > 0 {
3650            if self.increment_tick() {
3651                self.yield_pending = true;
3652            }
3653            pended = pended.saturating_sub(1);
3654        }
3655        self.pended_ticks = 0;
3656    }
3657
3658    /// Hand the port's critical-section exit tally to the trace sink.
3659    ///
3660    /// Gated on `T::EMITS` because `Port::exits` reads an ATOMIC counter, and
3661    /// LLVM may not delete an atomic load even when the value it produces is
3662    /// unused. With `NoTrace` the body folds to nothing while the `lw` behind it
3663    /// would stay, so every site was paying a load of a counter no sink was
3664    /// going to read. The gate is a compile-time constant, so an emitting sink
3665    /// is unchanged and a silent one loses the load entirely.
3666    #[inline(always)]
3667    pub(crate) fn note_exits(&mut self) {
3668        if T::EMITS {
3669            self.trace.note_exits(self.port.exits());
3670        }
3671    }
3672
3673    /// `xTaskResumeAll`; `true` when it yielded on the caller's behalf.
3674    ///
3675    /// Out of line for the cold callers; the body is [`Kernel::resume_all_inline`].
3676    #[inline(never)]
3677    pub fn resume_all(&mut self) -> bool {
3678        self.resume_all_inline()
3679    }
3680
3681    /// The body of [`Kernel::resume_all`], in line for the hot callers.
3682    #[inline(always)]
3683    pub(crate) fn resume_all_inline(&mut self) -> bool {
3684        let mut already_yielded = false;
3685        self.enter_critical();
3686        {
3687            self.suspended_depth = self.suspended_depth.saturating_sub(1);
3688            if self.suspended_depth == 0 && self.task_count > 0 {
3689                if !self.lists.is_empty_of(Self::pending_ready_list()) {
3690                    self.drain_pending_ready();
3691                }
3692                if self.pended_ticks > 0 {
3693                    self.unwind_pended_ticks();
3694                }
3695                if self.yield_pending {
3696                    if C::USE_PREEMPTION {
3697                        already_yielded = true;
3698                    }
3699                    // taskYIELD_TASK_CORE_IF_USING_PREEMPTION: inside the
3700                    // section.
3701                    self.port_yield();
3702                }
3703            }
3704        }
3705        self.exit_critical();
3706        already_yielded
3707    }
3708
3709    // ------------------------------------------- the blocking-call frame --
3710
3711    /// Start (or continue) a blocking call's `for(;;)`.
3712    ///
3713    /// The first pass records the block time and the entry timestamp, the
3714    /// way `xEntryTimeSet` / `vTaskInternalSetTimeOutState` do; later
3715    /// passes leave the running total alone, because the `ticks` the caller
3716    /// passes is the original block time and the kernel is holding what is
3717    /// left of it.
3718    ///
3719    /// Answers the block time that is LEFT. Both call sites wanted it right
3720    /// afterwards and used to resolve the same TCB a second time to read a
3721    /// field this function is already holding a `&mut` to. The answer is exact
3722    /// rather than merely equal to `ticks`, because the frame may be an earlier
3723    /// pass's — in which case the remaining time is what the kernel has been
3724    /// counting down, not what the caller passed.
3725    ///
3726    /// `None` means no frame was written at all, so the caller can skip the
3727    /// `end_wait` that would tear one down.
3728    pub(crate) fn begin_wait(
3729        &mut self,
3730        task: TaskHandle,
3731        queue: QueueHandle,
3732        ticks: u64,
3733    ) -> Option<u64> {
3734        // ★ TRUNCATE TO THE TICK WIDTH, at the boundary, because that is what
3735        // the C does and it is what makes every later comparison 32-bit.
3736        //
3737        // C's `xTicksToWait` is a `TickType_t`. At a 32-bit configuration a
3738        // caller CANNOT express a wait longer than `MAX_DELAY` -- the value is
3739        // truncated by the assignment, so `2^32` ticks becomes 0 and
3740        // `u64::MAX` becomes `portMAX_DELAY`, i.e. forever. This API takes a
3741        // `u64` so the kernel is width-independent, which means it must do that
3742        // truncation itself rather than let a value the C could not represent
3743        // reach a wait frame.
3744        //
3745        // The masking is BEFORE the zero test on purpose: C's truncation
3746        // happens at the assignment, so a caller asking for exactly `2^32`
3747        // ticks gets C's answer -- do not block -- and not a very long wait.
3748        //
3749        // What it buys: every field of a `WaitFrame` is then provably no wider
3750        // than the tick, so `check_for_timeout`'s comparisons against them stop
3751        // being 64-bit ones on a 32-bit target. That is the same lever that took
3752        // `tick_idle` 14 -> 9; see `reset_next_task_unblock_time`.
3753        let ticks = ticks & Self::MAX_DELAY;
3754        // The zero-block-time exit, taken before anything is read. `wait_set`
3755        // mirrors the TCB's `entry_set` in one byte, which is the same trade
3756        // `end_wait` documents and makes — so the frame can be ruled out
3757        // without an arena lookup, and without reading the clock either.
3758        // Out of range reads as SET, so an impossible index still goes the
3759        // long way round.
3760        if ticks == 0 && !self.flag(task.index() as usize, Self::F_WAIT, true) {
3761            // `None`, not `Some(0)`: no frame was written, so the caller can
3762            // skip the `end_wait` that would tear one down. It reads the same
3763            // `wait_set` byte to find nothing to do.
3764            return None;
3765        }
3766        let tick = self.tick;
3767        let overflows = self.overflows;
3768        let Ok(tcb) = self.tcbs.resolve_mut(task) else {
3769            // A queue call made before the scheduler started, from what the
3770            // C would call `main()`: there is no task to keep a frame for,
3771            // and such a call never blocks — `xSemaphoreGive` on a fresh
3772            // semaphore is the usual one. The old read answered 0 here
3773            // (`unwrap_or(0)` on the same failed resolve), so 0 is what this
3774            // must answer to keep the call sites reading the same.
3775            return Some(0);
3776        };
3777        if tcb.wait.queue != queue || !tcb.wait.entry_set {
3778            tcb.wait = WaitFrame {
3779                queue,
3780                ticks: crate::timer::Split64::new(ticks),
3781                entering: crate::timer::Split64::new(tick),
3782                overflows,
3783                entry_set: true,
3784                inherited: false,
3785            };
3786        }
3787        let remaining = tcb.wait.ticks.get();
3788        // The frame is set either way on this path -- either it was written
3789        // just now, or it was already this queue's.
3790        self.set_flag(task.index() as usize, Self::F_WAIT, true);
3791        Some(remaining)
3792    }
3793
3794    /// The call finished, one way or the other.
3795    pub(crate) fn end_wait(&mut self, task: TaskHandle) {
3796        // Almost every call arrives with no frame to clear, and the mirror
3797        // says so in one byte where resolving the TCB to read `entry_set`
3798        // cost an arena lookup. Out of range reads as SET, so an impossible
3799        // index still takes the slow path below.
3800        let at = task.index() as usize;
3801        if !self.flag(at, Self::F_WAIT, true) {
3802            return;
3803        }
3804        self.set_flag(at, Self::F_WAIT, false);
3805        if let Ok(tcb) = self.tcbs.resolve_mut(task) {
3806            // Now that the frame is only set on the path that blocks, most
3807            // calls reach here with nothing to clear, and this was writing
3808            // a default frame over a default frame. `entry_set` is the
3809            // sentinel the C calls `xEntryTimeSet`, and it is the first
3810            // thing set — `inherited` is only reached far inside the
3811            // blocking path, so it cannot be true while this is false.
3812            if tcb.wait.entry_set {
3813                tcb.wait = WaitFrame::default();
3814            }
3815        }
3816    }
3817
3818    /// `xInheritanceOccurred`.
3819    pub(crate) fn wait_inherited(&self, task: TaskHandle) -> bool {
3820        self.tcbs
3821            .resolve(task)
3822            .map(|t| t.wait.inherited)
3823            .unwrap_or(false)
3824    }
3825
3826    pub(crate) fn set_wait_inherited(&mut self, task: TaskHandle) {
3827        if let Ok(tcb) = self.tcbs.resolve_mut(task) {
3828            tcb.wait.inherited = true;
3829        }
3830    }
3831
3832    /// `xTaskCheckForTimeOut`: `true` when the block time has run out.
3833    /// Takes a critical section, as the C does, and charges the elapsed
3834    /// time against what is left.
3835    /// `None` is `pdTRUE` — the block time has run out. `Some(left)` is
3836    /// `pdFALSE`, and carries what is left of it.
3837    ///
3838    /// The block time is threaded out because both call sites asked for it
3839    /// immediately afterwards by resolving the TCB again, which
3840    /// the same TCB out of the arena again to read the very field the match
3841    /// below has just written.
3842    /// ★ `Option<NonZeroU64>`, not `Option<u64>`, and the reason is the
3843    /// CALLER's register budget.
3844    ///
3845    /// `Option<u64>` has no niche, so it is sixteen bytes — two registers —
3846    /// and `queue_take_blocking` holds it live across the branch that tests
3847    /// it. That function sits at a register cliff: six callee-saved pushes, a
3848    /// 72-byte frame, `caller`'s index spilled and re-read five times, and
3849    /// four separate attempts to make it cheaper all LOST because each added a
3850    /// live value or a branch (+200,668, +11,619, +254,429, +624,386; see
3851    /// `docs/LEDGER.md`). The one shape left is to make an existing value
3852    /// smaller, which is `rusty-compiler-leverage` B5 — the representation
3853    /// change that won −987,806 elsewhere by turning a 16-byte `Option` into
3854    /// one word.
3855    ///
3856    /// `Some(0)` is unreachable, which is what makes this free: the indefinite
3857    /// arm answers `MAX_DELAY` (non-zero at either tick width), and the
3858    /// still-waiting arm answers `held - elapsed` under `elapsed < held`, so at
3859    /// least one. `NonZeroU64::new` therefore maps every reachable `Some` to
3860    /// itself; a zero would become `None`, which is the same verdict a caller
3861    /// draws from zero ticks left anyway.
3862    pub(crate) fn check_for_timeout(&mut self, task: TaskHandle) -> Option<NonZeroU64> {
3863        self.enter_critical();
3864        // Prove the index in range ONCE. Three bounded reads below key on the
3865        // same task -- the abort flag, its clear, and the TCB resolve -- and an
3866        // out-of-range task already answers `None` through every one of them, so
3867        // saying so up front is free of behaviour and lets their checks fold.
3868        // `rusty-compiler-leverage` B1, the lever that took `switch_context`
3869        // -969,669 and the tick 14 -> 9 today.
3870        //
3871        // AFTER `enter_critical`, and the exit below is not optional: on the sim
3872        // an outermost critical-section exit IS the clock, so a return that
3873        // skipped it would move every later event in the trace and `conform`
3874        // would fail on all twenty-six scenarios.
3875        let index = task.index() as usize;
3876        if index >= TASKS {
3877            self.exit_critical();
3878            return None;
3879        }
3880        // An aborted delay is not the same as a time out, but it has the
3881        // same result: stop waiting.
3882        if self.delay_aborted.get(index).copied().unwrap_or(false) {
3883            if let Some(f) = self.delay_aborted.get_mut(index) {
3884                *f = false;
3885            }
3886            self.exit_critical();
3887            return None;
3888        }
3889        let now = self.tick;
3890        let overflows = self.overflows;
3891        let result = match self.tcbs.resolve_mut(task) {
3892            Ok(tcb) => {
3893                // Masked: `begin_wait` truncates what it stores to the tick
3894                // width, so these are no-ops on the VALUE and information to
3895                // LLVM, which cannot otherwise know a field it loaded is
3896                // narrow. Without them every comparison below is a 64-bit one.
3897                debug_assert_eq!(
3898                    tcb.wait.entering.get(),
3899                    tcb.wait.entering.get() & Self::MAX_DELAY,
3900                    "a wait frame's `entering` is wider than the tick"
3901                );
3902                debug_assert_eq!(
3903                    tcb.wait.ticks.get(),
3904                    tcb.wait.ticks.get() & Self::MAX_DELAY,
3905                    "a wait frame's `ticks` is wider than the tick"
3906                );
3907                let entering = tcb.wait.entering.get() & Self::MAX_DELAY;
3908                let held = tcb.wait.ticks.get() & Self::MAX_DELAY;
3909                let elapsed = now.wrapping_sub(entering) & Self::MAX_DELAY;
3910                if held == Self::MAX_DELAY {
3911                    // An indefinite block never times out. `MAX_DELAY` is
3912                    // non-zero at either tick width, so this is always `Some`.
3913                    debug_assert_ne!(Self::MAX_DELAY, 0, "MAX_DELAY must be non-zero");
3914                    NonZeroU64::new(Self::MAX_DELAY)
3915                } else if overflows != tcb.wait.overflows && now >= entering {
3916                    tcb.wait.ticks = crate::timer::Split64::new(0);
3917                    None
3918                } else if elapsed < held {
3919                    let left = held.wrapping_sub(elapsed);
3920                    tcb.wait.ticks = crate::timer::Split64::new(left);
3921                    tcb.wait.entering = crate::timer::Split64::new(now);
3922                    tcb.wait.overflows = overflows;
3923                    // `elapsed < held` on this arm, so `left` is at least one
3924                    // and this is always `Some`. The assert is what keeps the
3925                    // niche honest if that ever stops being true.
3926                    debug_assert_ne!(left, 0, "left must be non-zero on the still-waiting arm");
3927                    NonZeroU64::new(left)
3928                } else {
3929                    tcb.wait.ticks = crate::timer::Split64::new(0);
3930                    None
3931                }
3932            }
3933            Err(_) => None,
3934        };
3935        self.exit_critical();
3936        result
3937    }
3938
3939    /// `vTaskPlaceOnUnorderedEventList`: the item value carries the
3940    /// condition rather than the priority, so the item goes on the end and
3941    /// the list is never sorted.
3942    ///
3943    /// `taskEVENT_LIST_ITEM_VALUE_IN_USE` is not set here the way the C
3944    /// sets it. The C needs it because the same `ListItem_t` is a
3945    /// priority-ordered event item the rest of the time and the flag says
3946    /// which; the value is only ever read back by the event-group code,
3947    /// which masks the control byte off, so setting it would change
3948    /// nothing but the arithmetic in the doc comment.
3949    pub(crate) fn place_on_unordered_event_list(
3950        &mut self,
3951        list: ListId,
3952        value: u64,
3953        ticks: u64,
3954    ) -> Result<()> {
3955        let item = Self::event_item(self.current);
3956        self.lists.set_value(item, value)?;
3957        self.lists.insert_end(list, item)?;
3958        self.add_current_task_to_delayed_list(ticks, true)
3959    }
3960
3961    /// `vTaskRemoveFromUnorderedEventList`: write the answer into the item
3962    /// value, then wake the task.
3963    ///
3964    /// Unlike `xTaskRemoveFromEventList` this always goes straight to the
3965    /// ready list. It is only ever called with the scheduler suspended —
3966    /// `xEventGroupSetBits` holds it across the whole walk — and the C
3967    /// still bypasses the pending-ready list, because the value it just
3968    /// wrote is the task's return value and a second pass would overwrite
3969    /// it.
3970    pub(crate) fn remove_from_unordered_event_list(
3971        &mut self,
3972        item: ItemId,
3973        value: u64,
3974    ) -> Result<()> {
3975        self.lists.set_value(item, value)?;
3976        let task = self.task_of_event_item(item)?;
3977        let _ = self.lists.remove(item);
3978        let _ = self.lists.remove(Self::state_item(task));
3979        self.add_task_to_ready_list(task)?;
3980        if self.tcbs.resolve(task)?.priority > self.current_priority() {
3981            self.yield_pending = true;
3982        }
3983        Ok(())
3984    }
3985
3986    /// `uxTaskResetEventItemValue`: read the answer the unblocker left, and
3987    /// put the item back to the priority order an ordinary event list wants.
3988    pub(crate) fn reset_event_item_value(&mut self, task: TaskHandle) -> Result<u64> {
3989        let item = Self::event_item(task);
3990        let value = self.lists.value(item)?;
3991        let priority = self.tcbs.resolve(task)?.priority;
3992        self.lists
3993            .set_value(item, u64::from(C::MAX_PRIORITIES.saturating_sub(priority)))?;
3994        Ok(value)
3995    }
3996
3997    /// Whether `task` is resuming an event-group wait rather than starting
3998    /// one. Taking it clears the marker.
3999    pub(crate) fn take_event_resume(&mut self, task: TaskHandle) -> bool {
4000        // Nobody is parked in a wait, so there is nothing to read — one field
4001        // load in place of an arena lookup.
4002        if self.event_resumes == 0 {
4003            return false;
4004        }
4005        match self.tcbs.resolve_mut(task) {
4006            Ok(tcb) if tcb.event_blocked => {
4007                tcb.event_blocked = false;
4008                self.event_resumes = self.event_resumes.wrapping_sub(1);
4009                true
4010            }
4011            _ => false,
4012        }
4013    }
4014
4015    /// Mark that `task` blocked inside an event-group wait, so the call it
4016    /// is inside resumes rather than restarts.
4017    pub(crate) fn set_event_resume(&mut self, task: TaskHandle) {
4018        if let Ok(tcb) = self.tcbs.resolve_mut(task) {
4019            // Count the slot, not the call.
4020            if !tcb.event_blocked {
4021                self.event_resumes = self.event_resumes.wrapping_add(1);
4022            }
4023            tcb.event_blocked = true;
4024        }
4025    }
4026
4027    /// `vTaskPlaceOnEventList`: sorted by priority, then blocked.
4028    // The attribute is load-bearing and the measurement is the reason. The
4029    // bound proof below grew this function past LLVM's own inlining threshold,
4030    // and outlining it turned a -668,718 row win in `queue_take_blocking` into
4031    // a **+154,439 LOSS on the program** -- A3: the frame and the argument
4032    // marshalling cost more than the proof saves. Asking for the inline puts it
4033    // back to -96,574.
4034    //
4035    // `#[inline]` and `#[inline(always)]` measured IDENTICALLY here, on both
4036    // axes, so the weaker word is the honest one: the 22 bytes of rv32 flash
4037    // this costs are the bound check duplicated at each site, not the
4038    // attribute's doing.
4039    #[inline]
4040    pub(crate) fn place_on_event_list(&mut self, list: ListId, ticks: u64) -> Result<()> {
4041        let current = self.current;
4042        // B1, and the bound is the whole point: `event_item` is
4043        // `TASKS.saturating_add(index)`, which tells LLVM only that the result
4044        // fits a `u16` -- so `insert_keeping_value` still emits its own check
4045        // that the item names a real node, and the saturate costs a `mov` and a
4046        // `cmov` besides. Proving the index here instead makes the sum provably
4047        // below `2 * TASKS`, and both of those fold.
4048        //
4049        // It has to be proved HERE rather than relied on: `self.current` is a
4050        // live task on every path that reaches this function, but the calls in
4051        // between take `&mut self`, so LLVM cannot carry that across them.
4052        if current.index() as usize >= TASKS {
4053            self.note_stall(Stall::ListError);
4054            return Err(Error::Gone);
4055        }
4056        let item = Self::event_item(current);
4057        // The item keeps the value its call set; reading it out only to
4058        // hand it back made the list read the item twice and write it once
4059        // for no change.
4060        self.lists.insert_keeping_value(list, item)?;
4061        self.add_current_task_to_delayed_list(ticks, true)
4062    }
4063
4064    /// Take the trailing `portYIELD()` now, or owe it if a tick already
4065    /// switched us out of this call.
4066    pub(crate) fn yield_or_owe(&mut self, caller: TaskHandle) {
4067        if self.current == caller {
4068            self.port_yield();
4069        } else {
4070            self.owe_yield(caller);
4071        }
4072    }
4073
4074    /// `pvTaskIncrementMutexHeldCount`.
4075    pub(crate) fn increment_mutexes_held(&mut self, task: TaskHandle) {
4076        if let Ok(tcb) = self.tcbs.resolve_mut(task) {
4077            tcb.mutexes_held = tcb.mutexes_held.wrapping_add(1);
4078        }
4079    }
4080
4081    // ------------------------------------------------ priority inheritance --
4082
4083    /// `xTaskPriorityInherit`: lift the mutex holder to the waiter's
4084    /// priority. `true` when the holder is (or already was) lifted, which
4085    /// is what the waiter remembers so it can undo it on a timeout.
4086    #[cold]
4087    pub(crate) fn priority_inherit(&mut self, holder: TaskHandle) -> Result<bool> {
4088        if holder.is_null() || !self.tcbs.contains(holder) {
4089            return Ok(false);
4090        }
4091        let waiter_priority = self.current_priority();
4092        let (holder_priority, holder_base) = {
4093            let tcb = self.tcbs.resolve(holder)?;
4094            (tcb.priority, tcb.base_priority)
4095        };
4096        if holder_priority >= waiter_priority {
4097            // Already at least as urgent; the waiter still records that the
4098            // holder is running above its base, if it is.
4099            return Ok(holder_base < waiter_priority);
4100        }
4101        let event_value = u64::from(C::MAX_PRIORITIES.saturating_sub(waiter_priority));
4102        self.lists
4103            .set_value(Self::event_item(holder), event_value)?;
4104        let item = Self::state_item(holder);
4105        if self.lists.container(item)? == Some(Self::ready_list(holder_priority)) {
4106            let _ = self.lists.remove(item);
4107            self.set_task_priority(holder, waiter_priority)?;
4108            self.add_task_to_ready_list(holder)?;
4109        } else {
4110            self.set_task_priority(holder, waiter_priority)?;
4111        }
4112        self.trace_task(holder, |task, name| Event::TaskPriorityInherit {
4113            task,
4114            name,
4115            priority: Self::priority_value(waiter_priority),
4116        });
4117        Ok(true)
4118    }
4119
4120    /// `xTaskPriorityDisinherit`: giving the mutex back drops the
4121    /// inherited priority. `true` when a yield is wanted.
4122    #[cold]
4123    pub(crate) fn priority_disinherit(&mut self, holder: TaskHandle) -> Result<bool> {
4124        if holder.is_null() {
4125            return Ok(false);
4126        }
4127        // One lookup where there were three: `contains` asked the arena
4128        // whether the holder is there, `resolve` asked again to read its
4129        // three fields, and `resolve_mut` asked a third time to put one back
4130        // -- with nothing but a subtraction in between. A holder the arena
4131        // does not have still answers `Ok(false)`, which is what `contains`
4132        // was for.
4133        let (priority, base, remaining) = match self.tcbs.resolve_mut(holder) {
4134            Ok(tcb) => {
4135                let remaining = tcb.mutexes_held.saturating_sub(1);
4136                tcb.mutexes_held = remaining;
4137                (tcb.priority, tcb.base_priority, remaining)
4138            }
4139            Err(_) => return Ok(false),
4140        };
4141        if priority == base || remaining != 0 {
4142            return Ok(false);
4143        }
4144        let item = Self::state_item(holder);
4145        if self.lists.remove(item).is_err() {
4146            return Ok(false);
4147        }
4148        self.trace_task(holder, |task, name| Event::TaskPriorityDisinherit {
4149            task,
4150            name,
4151            priority: Self::priority_value(base),
4152        });
4153        self.set_task_priority(holder, base)?;
4154        let event_value = u64::from(C::MAX_PRIORITIES.saturating_sub(base));
4155        self.lists
4156            .set_value(Self::event_item(holder), event_value)?;
4157        self.add_task_to_ready_list(holder)?;
4158        Ok(true)
4159    }
4160
4161    /// `vTaskPriorityDisinheritAfterTimeout`: a waiter gave up, so the
4162    /// holder keeps only what the tasks still waiting justify.
4163    #[cold]
4164    pub(crate) fn priority_disinherit_after_timeout(
4165        &mut self,
4166        holder: TaskHandle,
4167        highest_waiting: u8,
4168    ) -> Result<()> {
4169        if holder.is_null() || !self.tcbs.contains(holder) {
4170            return Ok(());
4171        }
4172        let (priority, base, held) = {
4173            let tcb = self.tcbs.resolve(holder)?;
4174            (tcb.priority, tcb.base_priority, tcb.mutexes_held)
4175        };
4176        if priority == base || held != 1 {
4177            return Ok(());
4178        }
4179        let target = if highest_waiting > base {
4180            highest_waiting
4181        } else {
4182            base
4183        };
4184        if priority == target {
4185            return Ok(());
4186        }
4187        self.trace_task(holder, |task, name| Event::TaskPriorityDisinherit {
4188            task,
4189            name,
4190            priority: Self::priority_value(target),
4191        });
4192        self.set_task_priority(holder, target)?;
4193        let event_value = u64::from(C::MAX_PRIORITIES.saturating_sub(target));
4194        self.lists
4195            .set_value(Self::event_item(holder), event_value)?;
4196        let item = Self::state_item(holder);
4197        if self.lists.container(item)? == Some(Self::ready_list(priority)) {
4198            let _ = self.lists.remove(item);
4199            self.add_task_to_ready_list(holder)?;
4200        }
4201        Ok(())
4202    }
4203
4204    // ------------------------------------------------------- delay until --
4205
4206    /// `xTaskDelayUntil`: wake at `*previous_wake + period`, whatever the
4207    /// task did in between. `false` when the deadline has already passed,
4208    /// in which case nothing blocks — exactly as the C returns `pdFALSE`.
4209    ///
4210    /// # Errors
4211    /// A list error surfaces as itself.
4212    pub fn delay_until(&mut self, previous_wake: &mut u64, period: u64) -> Result<bool> {
4213        let caller = self.current;
4214        let mut should_delay = false;
4215        self.suspend_all();
4216        {
4217            let now = self.tick;
4218            let wake_at = previous_wake.wrapping_add(period) & Self::MAX_DELAY;
4219            if now < *previous_wake {
4220                // The tick count overflowed since the last wake.
4221                if wake_at < *previous_wake && wake_at > now {
4222                    should_delay = true;
4223                }
4224            } else if wake_at < *previous_wake || wake_at > now {
4225                should_delay = true;
4226            }
4227            *previous_wake = wake_at;
4228            if should_delay {
4229                self.trace_task(caller, |task, name| Event::TaskDelayUntil {
4230                    task,
4231                    name,
4232                    wake_at,
4233                });
4234                let ticks = wake_at.wrapping_sub(now) & Self::MAX_DELAY;
4235                self.add_current_task_to_delayed_list(ticks, false)?;
4236            }
4237        }
4238        if !self.resume_all() {
4239            self.yield_or_owe(caller);
4240        }
4241        Ok(should_delay)
4242    }
4243
4244    /// Which error `task_of_event_item` would have produced, re-derived out of
4245    /// line so its two discriminants do not sit in the caller's entry block.
4246    // `#[inline(never)]` is load-bearing, not decoration: with `#[cold]` alone
4247    // LLVM inlines this back and re-materialises the constants in the caller's
4248    // entry block -- measured EXACTLY +0 Ir for -2 B. The hint only reweights
4249    // the branch; MOVING the code is what sinks the constants.
4250    #[cold]
4251    #[inline(never)]
4252    fn event_item_error(&self, item: ItemId) -> Error {
4253        match item.checked_sub(Self::task_item_base()) {
4254            None => Error::InvalidArgument,
4255            Some(_) => Error::Gone,
4256        }
4257    }
4258
4259    /// `xTaskRemoveFromEventList`; `true` when the woken task outranks the
4260    /// running one and a yield is therefore required.
4261    /// `#[cold]` because the call is GUARDED and reached from many sites on
4262    /// one hot path, which is the shape that pays: it lets LLVM keep the
4263    /// caller's frame setup out of the likely route. Measured on
4264    /// `riscv32-qemu-tick-work`, one attribute at a time.
4265    /// Worth queue -7 on its own.
4266    #[cold]
4267    pub(crate) fn remove_from_event_list(&mut self, list: ListId) -> Result<bool> {
4268        let Some(item) = self.lists.head(list)? else {
4269            return Ok(false);
4270        };
4271        // The `?` put FIVE constants in the entry block -- `xor %eax,%eax`,
4272        // `mov $0x0,%edx`, `mov $0x1,%al`, `mov $0x8,%dl`, `mov $0x5,%dl` --
4273        // the Ok/Err tags and both error discriminants, materialised before the
4274        // tests that would use them. The census says ALL 21,487 BlockQ calls
4275        // pass every one of those tests, so that is five instructions of dead
4276        // setup on the only path anybody takes. Producing the error inside a
4277        // `#[cold]` callee sinks them out of the entry block.
4278        let Ok(task) = self.task_of_event_item(item) else {
4279            return Err(self.event_item_error(item));
4280        };
4281        let _ = self.lists.remove(item);
4282        if self.suspended_depth == 0 {
4283            let _ = self.lists.remove(Self::state_item(task));
4284            self.add_task_to_ready_list(task)?;
4285        } else {
4286            self.lists.insert_end(Self::pending_ready_list(), item)?;
4287        }
4288        let woken = self.tcbs.resolve(task)?.priority;
4289        if woken > self.current_priority() {
4290            self.yield_pending = true;
4291            return Ok(true);
4292        }
4293        Ok(false)
4294    }
4295}
4296
4297// ================================================================ tests ==
4298
4299/// `kernel.rs` is corpus-oracled BY DESIGN (`docs/HOLES.md` H3), and these
4300/// do not change that. They exist for the mutants that survived BOTH
4301/// oracles — measured, 80 of 415 viable — because the corpus and the unit
4302/// suite each cannot reach them:
4303///
4304/// * the corpus runs `PosixDemoConfig` for 2,000 ticks, so the TICK
4305///   OVERFLOW arms of `delay_until` never execute. Nine survivors sat
4306///   there, and the only way to reach them is to choose a
4307///   `previous_wake` near the maximum rather than to simulate 2^32 ticks;
4308/// * the diagnostic accessors (`task_at`, `ready_items`, `ready_cursor`)
4309///   and the geometry guard in `with_tick_hook` are called by no scenario
4310///   at all — they are also on H2's list of APIs with no differential, so
4311///   two independent methods agree on the same surface.
4312#[cfg(test)]
4313#[allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
4314mod tests {
4315    use rusty_rtos_core::config::Config;
4316    use rusty_rtos_core::hooks::NoTickHook;
4317
4318    use crate::system::tests::{NoTrace, TestConfig, TestPort};
4319
4320    type K = crate::Kernel<
4321        TestConfig,
4322        TestPort,
4323        NoTrace,
4324        NoTickHook,
4325        4,
4326        { crate::list_slots_for(4, 0, crate::lists_for(TestConfig::MAX_PRIORITIES, 1, 0)) },
4327        { crate::lists_for(TestConfig::MAX_PRIORITIES, 1, 0) },
4328        1,
4329        1,
4330        0,
4331        0,
4332        0,
4333        0,
4334        { <TestConfig as ::rusty_rtos_core::config::Config>::TIMER_QUEUE_LENGTH },
4335    >;
4336
4337    fn kernel() -> K {
4338        K::new(TestPort::default(), NoTrace).expect("the declared geometry adds up")
4339    }
4340
4341    /// A kernel with one task of our own running, so the calls that act on
4342    /// "the current task" have one.
4343    fn running() -> K {
4344        let mut k = kernel();
4345        k.create_task("t", 1).expect("a task");
4346        let h = k.start_scheduler().expect("start");
4347        k.suspend(Some(h.timer)).expect("park the daemon");
4348        for _ in 0..50_u32 {
4349            if k.name_of(k.current()).expect("a name").as_str() == "t" {
4350                return k;
4351            }
4352            k.switch_context();
4353        }
4354        panic!("the task never reached the CPU");
4355    }
4356
4357    /// `vTaskDelayUntil` with no overflow: a deadline still ahead delays,
4358    /// and one already passed does NOT.
4359    ///
4360    /// ```c
4361    /// else if( ( xTimeIncrement > ( xConstTickCount - *pxPreviousWakeTime ) ) ... )
4362    /// ```
4363    ///
4364    /// The second half is the one that matters and the one a naive test
4365    /// misses: a task that overran its period must NOT sleep a whole extra
4366    /// one, it must return immediately and say it did not delay.
4367    #[test]
4368    fn delay_until_skips_a_deadline_that_has_already_passed() {
4369        let mut k = running();
4370
4371        // now is 0; the deadline is 20 ticks away, so it delays.
4372        let mut previous = 0_u64;
4373        assert_eq!(k.delay_until(&mut previous, 20), Ok(true));
4374        assert_eq!(previous, 20, "the wake time advances by the period");
4375
4376        // Run the clock well past the next deadline.
4377        for _ in 0..60_u32 {
4378            k.tick_from_isr();
4379        }
4380
4381        // now is 60 and the deadline was 40: already gone.
4382        let mut previous = 20_u64;
4383        assert_eq!(
4384            k.delay_until(&mut previous, 20),
4385            Ok(false),
4386            "the period was overrun, so it must not sleep another one"
4387        );
4388        assert_eq!(
4389            previous, 40,
4390            "and the wake time STILL advances, or the task never catches up"
4391        );
4392    }
4393
4394    /// The tick-overflow arm, which the corpus cannot reach in 2,000 ticks.
4395    ///
4396    /// ```c
4397    /// if( xConstTickCount < *pxPreviousWakeTime ) {
4398    ///     if( ( xTimeToWake < *pxPreviousWakeTime ) && ( xTimeToWake > xConstTickCount ) )
4399    /// ```
4400    ///
4401    /// Both halves are needed: the wake time must have wrapped TOO, and it
4402    /// must still be ahead of the wrapped-around now. Reaching it needs a
4403    /// `previous_wake` near the maximum, not 2^32 ticks of simulation.
4404    #[test]
4405    fn delay_until_handles_a_wake_time_that_wrapped_with_the_tick() {
4406        let mut k = running();
4407        let max = K::MAX_DELAY;
4408
4409        // A few ticks, so `now` is small and positive.
4410        for _ in 0..5_u32 {
4411            k.tick_from_isr();
4412        }
4413
4414        // previous_wake sits just below the maximum; the period carries the
4415        // wake time over the top, to 9. now is 5, so 9 is still ahead.
4416        let mut previous = max.wrapping_sub(10);
4417        assert_eq!(
4418            k.delay_until(&mut previous, 20),
4419            Ok(true),
4420            "wrapped, and still in the future: it must delay"
4421        );
4422        assert_eq!(previous, 9, "the wake time wrapped with the tick");
4423
4424        // Same wrap, but the wake time is already behind a larger now.
4425        let mut k = running();
4426        for _ in 0..40_u32 {
4427            k.tick_from_isr();
4428        }
4429        let mut previous = max.wrapping_sub(10);
4430        assert_eq!(
4431            k.delay_until(&mut previous, 20),
4432            Ok(false),
4433            "wrapped, and now is already past it: it must NOT delay"
4434        );
4435    }
4436
4437    /// `task_at` walks the arena by SLOT, which is how a debugger or a
4438    /// health check enumerates tasks without holding handles.
4439    #[test]
4440    fn task_at_enumerates_live_slots_and_stops_at_the_end() {
4441        let mut k = kernel();
4442        let a = k.create_task("a", 1).expect("a task");
4443
4444        assert_eq!(k.task_at(0), Some(a), "slot zero is the first task");
4445        assert_eq!(
4446            k.task_at(usize::from(u16::MAX)),
4447            None,
4448            "past the arena is None, not a handle"
4449        );
4450        assert_eq!(
4451            k.task_at(usize::from(u16::MAX) + 1),
4452            None,
4453            "and an index that does not even fit a u16 is None, not a panic"
4454        );
4455    }
4456
4457    /// `ready_items` fills the caller's buffer and answers how many it
4458    /// wrote, stopping at the buffer's end rather than running past it.
4459    #[test]
4460    fn ready_items_fills_what_it_can_and_counts_what_it_filled() {
4461        let mut k = kernel();
4462        k.create_task("a", 1).expect("a");
4463        k.create_task("b", 1).expect("b");
4464
4465        let mut out = [0_u16; 8];
4466        let n = k.ready_items(1, &mut out);
4467        assert_eq!(n, 2, "two tasks are ready at priority 1");
4468
4469        // A buffer too small must be filled to its end and no further.
4470        let mut small = [0_u16; 1];
4471        assert_eq!(
4472            k.ready_items(1, &mut small),
4473            1,
4474            "it wrote one, because one is all there was room for"
4475        );
4476
4477        // An empty priority writes nothing.
4478        let mut out = [0_u16; 8];
4479        assert_eq!(k.ready_items(0, &mut out), 0);
4480    }
4481
4482    /// `ready_cursor` is the diagnostic that answers "did the round robin
4483    /// move", so it must report the list it was asked about.
4484    #[test]
4485    fn ready_cursor_reports_the_list_it_was_asked_about() {
4486        let mut k = kernel();
4487        k.create_task("a", 1).expect("a");
4488        k.create_task("b", 1).expect("b");
4489
4490        let before = k.ready_cursor(1);
4491        k.switch_context();
4492        let after = k.ready_cursor(1);
4493        assert_ne!(after, before, "a switch moved the cursor at priority 1");
4494        assert_eq!(
4495            k.ready_cursor(0),
4496            k.ready_cursor(0),
4497            "and an untouched priority answers the same thing twice"
4498        );
4499    }
4500
4501    /// `with_tick_hook`'s geometry guard, which is the only thing standing
4502    /// between a mis-declared kernel and a silently wrong one.
4503    ///
4504    /// `ITEMS` and `LISTS` are derived constants; if a caller writes them
4505    /// by hand and gets them wrong, every list index is off. The guard
4506    /// refuses, and these are the arms of it.
4507    #[test]
4508    fn the_geometry_guard_refuses_a_kernel_that_does_not_add_up() {
4509        // ITEMS too small for the declared tasks and timers.
4510        type WrongItems = crate::Kernel<
4511            TestConfig,
4512            TestPort,
4513            NoTrace,
4514            NoTickHook,
4515            4,
4516            // Legal as a geometry — a power of two above `LISTS` — but not
4517            // the derived value, which is 32. A grosser error (2 slots for
4518            // 12 lists) is now a COMPILE error in `SIZES_FIT`, so it cannot
4519            // be used to exercise the runtime guard any more. That the
4520            // check moved earlier is the improvement; this keeps the later
4521            // one honest.
4522            16,
4523            { crate::lists_for(TestConfig::MAX_PRIORITIES, 1, 0) },
4524            1,
4525            1,
4526            0,
4527            0,
4528            0,
4529            0,
4530            { <TestConfig as ::rusty_rtos_core::config::Config>::TIMER_QUEUE_LENGTH },
4531        >;
4532        assert!(
4533            WrongItems::new(TestPort::default(), NoTrace).is_err(),
4534            "ITEMS must be list_slots_for(TASKS, TIMERS, LISTS)"
4535        );
4536
4537        // LISTS not derived from the priorities, queues and groups.
4538        type WrongLists = crate::Kernel<
4539            TestConfig,
4540            TestPort,
4541            NoTrace,
4542            NoTickHook,
4543            4,
4544            // Correct for the two lists declared below, so the refusal
4545            // below is attributable to `LISTS` and nothing else.
4546            { crate::list_slots_for(4, 0, 2) },
4547            2,
4548            1,
4549            1,
4550            0,
4551            0,
4552            0,
4553            0,
4554            { <TestConfig as ::rusty_rtos_core::config::Config>::TIMER_QUEUE_LENGTH },
4555        >;
4556        assert!(
4557            WrongLists::new(TestPort::default(), NoTrace).is_err(),
4558            "LISTS must be lists_for(MAX_PRIORITIES, QUEUES, GROUPS)"
4559        );
4560
4561        // A kernel with no room for a single task.
4562        type NoTasks = crate::Kernel<
4563            TestConfig,
4564            TestPort,
4565            NoTrace,
4566            NoTickHook,
4567            0,
4568            { crate::list_slots_for(0, 0, crate::lists_for(TestConfig::MAX_PRIORITIES, 1, 0)) },
4569            { crate::lists_for(TestConfig::MAX_PRIORITIES, 1, 0) },
4570            1,
4571            1,
4572            0,
4573            0,
4574            0,
4575            0,
4576            { <TestConfig as ::rusty_rtos_core::config::Config>::TIMER_QUEUE_LENGTH },
4577        >;
4578        assert!(
4579            NoTasks::new(TestPort::default(), NoTrace).is_err(),
4580            "TASKS == 0 cannot even hold the idle task"
4581        );
4582
4583        // And the geometry that DOES add up is accepted, or the three
4584        // assertions above would pass for the wrong reason.
4585        assert!(K::new(TestPort::default(), NoTrace).is_ok());
4586    }
4587    /// `prvGetExpectedIdleTime`, arm one: something above the idle
4588    /// priority is running, so there is no window to sleep through.
4589    ///
4590    /// The three arms are a short-circuit chain and each is separately
4591    /// constructible, which is how they get pinned one at a time. A `>`
4592    /// turned `>=` in any of them would let the kernel sleep through work
4593    /// that is ready NOW.
4594    #[test]
4595    fn expected_idle_time_is_zero_while_anything_outranks_the_idle_task() {
4596        let mut k = kernel();
4597        k.create_task("hi", 1).expect("a task above idle");
4598        k.start_scheduler().expect("start");
4599
4600        assert!(
4601            k.current_priority() > 0,
4602            "the task above idle is the one running"
4603        );
4604        assert_eq!(
4605            k.expected_idle_time(),
4606            0,
4607            "something outranks idle, so the window is zero"
4608        );
4609    }
4610
4611    /// Arm two: another task shares the idle priority, so the very next
4612    /// tick has to be processed to give it its slice.
4613    #[test]
4614    fn expected_idle_time_is_zero_when_another_idle_task_wants_the_slice() {
4615        let mut k = kernel();
4616        k.create_task("a", 0).expect("a task AT the idle priority");
4617        k.start_scheduler().expect("start");
4618
4619        assert!(
4620            k.ready_len(0).unwrap_or(0) > 1,
4621            "the idle task and ours are both ready at priority 0"
4622        );
4623        assert_eq!(
4624            k.expected_idle_time(),
4625            0,
4626            "a shared slice cannot be slept through"
4627        );
4628    }
4629
4630    /// And with none of the three arms true, the window is the time to the
4631    /// next unblock -- which is the number the whole tickless feature
4632    /// rests on.
4633    #[test]
4634    fn expected_idle_time_is_the_window_to_the_next_unblock() {
4635        let mut k = running();
4636        k.delay(30).expect("park our task for thirty ticks");
4637
4638        // Only the idle task is ready now, and nothing outranks it.
4639        assert_eq!(k.current_priority(), 0, "the idle task is running");
4640        assert_eq!(k.ready_len(0).unwrap_or(0), 1, "and it is alone at zero");
4641        assert_eq!(
4642            k.expected_idle_time(),
4643            30,
4644            "so the port may sleep right up to the next unblock"
4645        );
4646    }
4647
4648    /// `ulTaskNotifyValueClear`'s reader half, and `xTaskNotifyAndQuery`'s:
4649    /// it answers the slot it was ASKED for, for the task it was asked
4650    /// about.
4651    ///
4652    /// Pinned with a value that is neither 0 nor 1, because those are what
4653    /// the surviving mutants replaced it with.
4654    #[test]
4655    fn notify_value_answers_the_slot_it_was_asked_for() {
4656        use crate::kernel::NotifyAction;
4657
4658        let mut k = running();
4659        let me = k.current();
4660        k.notify(me, 0, 0xabcd_1234, NotifyAction::Overwrite)
4661            .expect("notify");
4662
4663        assert_eq!(
4664            k.notify_value(Some(me), 0),
4665            Ok(0xabcd_1234),
4666            "the value that was set, not zero and not one"
4667        );
4668        assert_eq!(
4669            k.notify_value(None, 0),
4670            Ok(0xabcd_1234),
4671            "None means the CURRENT task"
4672        );
4673        assert!(
4674            k.notify_value(Some(me), TestConfig::NOTIFICATION_ARRAY_ENTRIES)
4675                .is_err(),
4676            "an index past the configured array is an error, not a zero"
4677        );
4678    }
4679    /// `delay_until`'s BOUNDARIES, which is where the four mutants that
4680    /// survived both oracles live.
4681    ///
4682    /// Each comparison in it has an edge the ordinary tests never touch,
4683    /// and each edge is reachable once you notice that `previous_wake` is
4684    /// a CALLER variable and the period may be zero:
4685    ///
4686    /// | line | comparison | the edge |
4687    /// |---|---|---|
4688    /// | 3228 | `wake_at < *previous_wake` | equal, via a period of 0 |
4689    /// | 3228 | `wake_at > now` | equal, by ticking to the wake time |
4690    /// | 3231 | `wake_at < *previous_wake` | equal, via a period of 0 |
4691    ///
4692    /// All three answers must be "do not delay". A `<=` or a `>=` in any of
4693    /// them turns a zero-length wait into a full period of sleep.
4694    #[test]
4695    fn delay_until_does_not_delay_on_any_of_its_boundaries() {
4696        let max = K::MAX_DELAY;
4697
4698        // (1) OVERFLOW arm, period zero: the wake time equals the previous
4699        // one, so there is nothing to wait for.
4700        let mut k = running();
4701        for _ in 0..5_u32 {
4702            k.tick_from_isr();
4703        }
4704        let mut previous = max.wrapping_sub(10);
4705        assert_eq!(
4706            k.delay_until(&mut previous, 0),
4707            Ok(false),
4708            "a period of zero is not a period of MAX_DELAY"
4709        );
4710
4711        // (2) OVERFLOW arm, wake time exactly equal to now: already due.
4712        // (max - 10) + 20 wraps to 9, so tick to 9.
4713        let mut k = running();
4714        for _ in 0..9_u32 {
4715            k.tick_from_isr();
4716        }
4717        let mut previous = max.wrapping_sub(10);
4718        assert_eq!(
4719            previous.wrapping_add(20) & max,
4720            9,
4721            "the wake time wraps to 9"
4722        );
4723        assert_eq!(
4724            k.delay_until(&mut previous, 20),
4725            Ok(false),
4726            "the wrapped wake time is NOW, so it is not in the future"
4727        );
4728
4729        // (3) NON-overflow arm, period zero with now already at the wake
4730        // time: neither disjunct holds.
4731        let mut k = running();
4732        for _ in 0..10_u32 {
4733            k.tick_from_isr();
4734        }
4735        let mut previous = 10_u64;
4736        assert_eq!(
4737            k.delay_until(&mut previous, 0),
4738            Ok(false),
4739            "nothing to wait for, and no period to sleep"
4740        );
4741        assert_eq!(previous, 10, "and the wake time does not move");
4742    }
4743    /// The tick-wrap bookkeeping, which `xTaskIncrementTick` runs once
4744    /// every `MAX_DELAY + 1` ticks.
4745    ///
4746    /// Neither oracle can reach it: the corpus runs 2,000 ticks and the
4747    /// unit suite does not wrap either, so every mutation of it survived
4748    /// both. It is a private `fn` and this module is inside `kernel.rs`,
4749    /// so the test calls it directly rather than trying to simulate 2^32
4750    /// ticks — which is the right answer when the trigger is unreachable
4751    /// but the behaviour is not.
4752    #[test]
4753    fn switching_the_delayed_lists_flips_the_pair_and_counts_the_wrap() {
4754        let mut k = running();
4755        let swapped = k.delayed_swapped;
4756        let overflows = k.overflows;
4757
4758        k.switch_delayed_lists();
4759        assert_ne!(
4760            k.delayed_swapped, swapped,
4761            "the delayed and overflow lists change places"
4762        );
4763        assert_eq!(
4764            k.overflows,
4765            overflows.wrapping_add(1),
4766            "and the wrap is counted, because `overflows` is how a trace \
4767             tells one epoch from the next"
4768        );
4769
4770        k.switch_delayed_lists();
4771        assert_eq!(k.delayed_swapped, swapped, "flipping twice is the identity");
4772        assert_eq!(k.overflows, overflows.wrapping_add(2));
4773    }
4774
4775    /// `prvResetNextTaskUnblockTime`, which the wrap calls: after the swap
4776    /// the next unblock time has to be recomputed from the list that is
4777    /// NOW the delayed one.
4778    ///
4779    /// That list is empty immediately after a wrap, so the answer must be
4780    /// `MAX_DELAY` — a stale value from the old list would make the
4781    /// kernel think a task is due and spin, or sleep through one that is.
4782    #[test]
4783    fn switching_the_delayed_lists_recomputes_the_next_unblock_time() {
4784        let mut k = running();
4785        let due = k.tick_count().wrapping_add(30);
4786        k.delay(30).expect("park our task on the delayed list");
4787        assert_eq!(k.next_unblock_time, due, "the parked task is what is next");
4788
4789        k.switch_delayed_lists();
4790        assert_eq!(
4791            k.next_unblock_time,
4792            K::MAX_DELAY,
4793            "the list that is now 'delayed' is empty, so nothing is due"
4794        );
4795    }
4796
4797    /// The sentinel for "nothing is due" is the SAME value in both places this
4798    /// kernel writes it, and this pins that.
4799    ///
4800    /// ★ It used to differ, and this test used to pin the difference. A reset
4801    /// over an empty delayed list stored `u64::MAX` because `head_value` cannot
4802    /// answer "empty" -- on an empty list the head IS the end marker, whose
4803    /// value is `u64::MAX` so sorted inserts always find something larger to
4804    /// stop at -- so the `unwrap_or(MAX_DELAY)` never fired. The C stores
4805    /// `portMAX_DELAY` there.
4806    ///
4807    /// The divergence was unobservable (it shows only at a tick equal to
4808    /// `MAX_DELAY`, and the wrap resets anyway), which is why a test pinned it
4809    /// instead of a gate catching it -- and the test one screen up had said in
4810    /// prose that `MAX_DELAY` "must" be the answer while asserting `u64::MAX`.
4811    /// The prose was right.
4812    ///
4813    /// Worth five instructions per tick: with the field provably no wider than
4814    /// the tick, `increment_tick`'s comparison against it stops being a 64-bit
4815    /// one on a 32-bit target. See `reset_next_task_unblock_time`.
4816    ///
4817    /// `new()` starts it at `MAX_DELAY` -- the tick mask, and what the C's
4818    /// `portMAX_DELAY` is. `reset_next_task_unblock_time` instead takes
4819    /// `head_value` of an empty list, which answers `ListsOf::MAX_VALUE`
4820    /// = `u64::MAX`, so the `unwrap_or(MAX_DELAY)` beside it never fires
4821    /// for emptiness.
4822    ///
4823    /// Neither is reachable as a tick, because the tick is masked to
4824    /// `MAX_DELAY`, so no scheduling decision can tell them apart and the
4825    /// corpus is green either way. It IS visible to the tickless path:
4826    /// `expected_idle_time` answers `next_unblock_time - tick`, which is
4827    /// the window the port is handed, and the two sentinels differ there
4828    /// by four billion.
4829    ///
4830    /// Recorded rather than changed: making them agree is an owner
4831    /// decision, because `expected_idle_time` feeds a port and any change
4832    /// to it moves what a tickless build asks for.
4833    #[test]
4834    fn the_nothing_is_due_sentinel_differs_between_init_and_reset() {
4835        let k = kernel();
4836        assert_eq!(
4837            k.next_unblock_time,
4838            K::MAX_DELAY,
4839            "a fresh kernel uses the tick mask, which is the C's portMAX_DELAY"
4840        );
4841
4842        let mut k = running();
4843        k.reset_next_task_unblock_time();
4844        assert_eq!(
4845            k.next_unblock_time,
4846            K::MAX_DELAY,
4847            "and a reset over an empty list uses the SAME sentinel, as the C does"
4848        );
4849        assert_ne!(
4850            K::MAX_DELAY,
4851            u64::MAX,
4852            "MAX_DELAY must be narrower than u64::MAX at this width, or the              invariant this test defends is vacuous"
4853        );
4854        assert_eq!(
4855            k.next_unblock_time & K::MAX_DELAY,
4856            k.next_unblock_time,
4857            "the field must never hold a value wider than the tick: that is what              lets increment_tick's comparison stay 32-bit"
4858        );
4859    }
4860
4861    /// The owe hint must not outlive the debt it stands for.
4862    ///
4863    /// A census over three scenarios found every raise producing exactly TWO
4864    /// entries to `resume_pending_owed` — one that did the work and returned
4865    /// `true`, and a second that re-derived "nothing owed" and cleared the
4866    /// hint on its way out. BlockQ: 43,110 raises, 86,207 entries. Clearing
4867    /// the hint at the end of the work made entries equal raises.
4868    ///
4869    /// Both directions are asserted. A `clear_owe_if_settled` that cleared
4870    /// unconditionally would pass the first half and lose a real owed item,
4871    /// which is a missing trace line in the differential — so the second half
4872    /// is the half that matters.
4873    #[test]
4874    fn the_owe_hint_does_not_outlive_the_debt() {
4875        let mut k = running();
4876        let me = k.current();
4877        let i = me.index() as usize;
4878        fn hint(k: &K, i: usize) -> bool {
4879            k.owes_anything.get(i).copied().unwrap_or(false)
4880        }
4881
4882        k.owe(me);
4883        assert!(hint(&k, i), "the hint was raised");
4884        k.clear_owe_if_settled(i);
4885        assert!(
4886            !hint(&k, i),
4887            "nothing is owed, so the hint is dead and must go -- leaving it standing costs one whole entry to the owed body per owed item"
4888        );
4889
4890        // The negative case, once per kind of debt. A `clear_owe_if_settled`
4891        // that cleared unconditionally would pass the half above and lose a
4892        // real owed item, which is a missing line in the differential.
4893        for kind in 0..3 {
4894            match kind {
4895                0 => *k.owed_exits.get_mut(i).expect("in range") = 1,
4896                1 => k.set_flag(i, K::F_YIELD, true),
4897                _ => {
4898                    *k.owed_trace.get_mut(i).expect("in range") =
4899                        crate::kernel::OwedTrace::AddNewTaskToReadyList {
4900                            task: me,
4901                            priority: 1,
4902                        }
4903                }
4904            }
4905            k.owe(me);
4906            k.clear_owe_if_settled(i);
4907            assert!(hint(&k, i), "kind {kind} is live debt; the hint must stay");
4908            *k.owed_exits.get_mut(i).expect("in range") = 0;
4909            k.set_flag(i, K::F_YIELD, false);
4910            *k.owed_trace.get_mut(i).expect("in range") = crate::kernel::OwedTrace::None;
4911        }
4912    }
4913
4914    /// The stream-buffer resume flag is a ONE-SHOT: the take clears it, so
4915    /// a second take answers None. A `take` that did not clear would let a
4916    /// blocked reader wake twice on one send.
4917    #[test]
4918    fn a_stream_resume_is_taken_once_and_then_gone() {
4919        let mut k = running();
4920        let me = k.current();
4921        assert_eq!(k.take_stream_resume(me), None, "nothing set yet");
4922
4923        k.set_stream_resume(me, 7);
4924        assert_eq!(k.take_stream_resume(me), Some(7), "the value that was set");
4925        assert_eq!(k.take_stream_resume(me), None, "and it is consumed");
4926    }
4927
4928    /// `vTaskMissedYield`: a yield asked for while the scheduler is
4929    /// suspended has to be remembered, or it is simply lost.
4930    #[test]
4931    fn a_missed_yield_is_remembered_rather_than_dropped() {
4932        let mut k = running();
4933        k.yield_pending = false;
4934        k.missed_yield();
4935        assert!(
4936            k.yield_pending,
4937            "the yield survives until something can act on it"
4938        );
4939    }
4940}