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