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