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