ax_task/time/queue/
mod.rs

1//! Fixed-capacity owner-CPU task-deadline storage.
2
3mod heap;
4mod kernel;
5mod node;
6
7pub use kernel::{
8    HardKernelTimerAction, HardKernelTimerCallback, HardKernelTimerHandle,
9    HardRestartableKernelTimerCallback, KernelTimerAction, KernelTimerCallback,
10    KernelTimerCancelOutcome, KernelTimerHandle, RestartableKernelTimerCallback,
11};
12pub(crate) use kernel::{KernelTimerEntry, KernelTimerExecution, KernelTimerQueue};
13pub use node::{
14    ExpiredTaskDeadline, TaskDeadlineKind, TaskDeadlineNode, TaskDeadlineRegistration,
15    TaskDeadlineToken,
16};
17
18use self::{
19    heap::{TimerEntry, TimerHeap},
20    node::{TASK_DEADLINE_CLASS_COUNT, TaskDeadlineClass, TaskDeadlineNodeId},
21};
22use crate::{
23    thread::ThreadCore,
24    time::{MonotonicDeadline, MonotonicInstant},
25};
26
27/// Failure returned while arming a fixed-capacity timer.
28#[derive(Clone, Copy, Debug, Eq, PartialEq, thiserror::Error)]
29pub enum TaskDeadlineError {
30    /// Every preallocated heap slot is occupied by an active task deadline.
31    #[error("per-CPU timer capacity is exhausted")]
32    Capacity,
33    /// The node identity or arm generation space has been exhausted.
34    #[error("timer identity or generation space is exhausted")]
35    GenerationExhausted,
36    /// The typed event does not belong to the supplied embedded timer node.
37    #[error("task deadline kind does not match its timer node")]
38    KindMismatch,
39}
40
41/// Bounded timer-IRQ expiration request.
42#[derive(Clone, Copy, Debug, Eq, PartialEq)]
43pub struct TaskDeadlineExpireRequest {
44    now: MonotonicInstant,
45    batch_limit: usize,
46}
47
48impl TaskDeadlineExpireRequest {
49    /// Creates one bounded timer expiration request.
50    pub const fn new(now: MonotonicInstant, batch_limit: usize) -> Self {
51        Self { now, batch_limit }
52    }
53}
54
55/// Result of one bounded timer-IRQ pass.
56#[derive(Clone, Copy, Debug, Eq, PartialEq)]
57pub struct TaskDeadlineExpireBatch {
58    processed: usize,
59    expired: usize,
60    pending: bool,
61    next_deadline: Option<MonotonicDeadline>,
62}
63
64pub(crate) enum HardTaskDeadlineClaim {
65    Park {
66        event: ExpiredTaskDeadline,
67        thread: alloc::sync::Arc<ThreadCore>,
68    },
69    Scheduler(ExpiredTaskDeadline),
70}
71
72impl TaskDeadlineExpireBatch {
73    /// Returns heap nodes removed during this pass.
74    pub const fn processed(self) -> usize {
75        self.processed
76    }
77
78    /// Returns valid expirations written into the caller's output storage.
79    pub const fn expired(self) -> usize {
80        self.expired
81    }
82
83    /// Reports that immediately actionable work remains after the batch.
84    pub const fn pending(self) -> bool {
85        self.pending
86    }
87
88    /// Returns the next logical task deadline.
89    pub const fn next_deadline(self) -> Option<MonotonicDeadline> {
90        self.next_deadline
91    }
92}
93
94/// Fixed-capacity value heap created during CPU-local initialization.
95///
96/// Construction is the only operation that reserves memory. Arming, cancelling,
97/// and expiring never grow or shrink the allocation.
98#[derive(Debug)]
99pub struct TaskDeadlineQueue {
100    heaps: [TimerHeap; TASK_DEADLINE_CLASS_COUNT],
101    capacity_per_class: usize,
102}
103
104/// Reversible removal of one task-deadline queue entry.
105///
106/// The owner CPU keeps this transaction while it derives and publishes the
107/// replacement clockevent state. A pre-publication failure can therefore
108/// restore the exact generation-bearing entry without allocating a new slot or
109/// consuming another timer generation.
110#[must_use = "a task-deadline cancellation must be committed or rolled back"]
111pub(crate) struct TaskDeadlineCancelTxn {
112    entry: TimerEntry,
113}
114
115/// Fully validated arm operation whose queue commit cannot fail.
116///
117/// Owner code may prepare every timer affected by one scheduler transition
118/// before changing any queue entry. This is the task-deadline equivalent of
119/// Linux hrtimer's prepare/enqueue split: capacity and generation failures stay
120/// on the recoverable side of the scheduler commit boundary.
121#[must_use = "a prepared task deadline must be committed or discarded"]
122pub(crate) struct TaskDeadlineArmPlan {
123    entry: TimerEntry,
124    replacing: Option<TaskDeadlineClass>,
125}
126
127impl TaskDeadlineCancelTxn {
128    pub(crate) fn commit(self) {}
129
130    pub(crate) fn rollback(self, queue: &mut TaskDeadlineQueue) {
131        queue.restore_cancelled(self.entry);
132    }
133}
134
135impl TaskDeadlineQueue {
136    /// Preallocates `capacity` independent slots for each typed timer class.
137    pub fn new(capacity: usize) -> Self {
138        Self {
139            heaps: core::array::from_fn(|_| TimerHeap::new(capacity)),
140            capacity_per_class: capacity,
141        }
142    }
143
144    fn heap(&self, class: TaskDeadlineClass) -> &TimerHeap {
145        &self.heaps[class.index()]
146    }
147
148    fn heap_mut(&mut self, class: TaskDeadlineClass) -> &mut TimerHeap {
149        &mut self.heaps[class.index()]
150    }
151
152    /// Arms a typed task deadline for an absolute monotonic deadline.
153    ///
154    /// Rearming replaces this physical node's previous entry in place. Distinct
155    /// nodes for one thread remain independent, and each node consumes at most
156    /// one preallocated heap slot.
157    ///
158    /// # Errors
159    ///
160    /// Returns [`TaskDeadlineError::Capacity`] without changing the queue or
161    /// consuming an arm generation if no heap slot remains. A node may retain
162    /// the lazily assigned identity used for this capacity check. Returns
163    /// [`TaskDeadlineError::GenerationExhausted`] instead of reusing an old
164    /// generation.
165    ///
166    /// Queue mutation must remain serialized on its owner CPU. The returned
167    /// move-only registration owns the physical entry; the queue stores the
168    /// thread, generation, and event kind by value and does not retain `node`.
169    pub fn arm(
170        &mut self,
171        node: &TaskDeadlineNode,
172        deadline: MonotonicDeadline,
173        kind: TaskDeadlineKind,
174    ) -> Result<TaskDeadlineRegistration, TaskDeadlineError> {
175        let plan = self.prepare_arm(node, deadline, kind)?;
176        Ok(self.commit_arm(plan))
177    }
178
179    pub(crate) fn prepare_arm(
180        &self,
181        node: &TaskDeadlineNode,
182        deadline: MonotonicDeadline,
183        kind: TaskDeadlineKind,
184    ) -> Result<TaskDeadlineArmPlan, TaskDeadlineError> {
185        self.prepare_arm_in_class(node, deadline, kind, kind.default_class(), None)
186    }
187
188    pub(crate) fn arm_hard_park(
189        &mut self,
190        node: &TaskDeadlineNode,
191        deadline: MonotonicDeadline,
192        kind: TaskDeadlineKind,
193        thread: alloc::sync::Arc<ThreadCore>,
194    ) -> Result<TaskDeadlineRegistration, TaskDeadlineError> {
195        let plan = self.prepare_arm_in_class(
196            node,
197            deadline,
198            kind,
199            TaskDeadlineClass::ParkHard,
200            Some(thread),
201        )?;
202        Ok(self.commit_arm(plan))
203    }
204
205    fn prepare_arm_in_class(
206        &self,
207        node: &TaskDeadlineNode,
208        deadline: MonotonicDeadline,
209        kind: TaskDeadlineKind,
210        class: TaskDeadlineClass,
211        park_thread: Option<alloc::sync::Arc<ThreadCore>>,
212    ) -> Result<TaskDeadlineArmPlan, TaskDeadlineError> {
213        let thread = node.thread();
214        if !node.supports(class) || (class == TaskDeadlineClass::ParkHard) != park_thread.is_some()
215        {
216            return Err(TaskDeadlineError::KindMismatch);
217        }
218        let identity = node.identity()?;
219        let heap = self.heap(class);
220        let replacing = self.find_node_class(identity);
221        if heap.is_full() && replacing != Some(class) {
222            return Err(TaskDeadlineError::Capacity);
223        }
224        let token = node.next_token(identity)?;
225        Ok(TaskDeadlineArmPlan {
226            entry: TimerEntry::new(deadline, thread, token, kind, class, park_thread),
227            replacing,
228        })
229    }
230
231    pub(crate) fn commit_arm(&mut self, plan: TaskDeadlineArmPlan) -> TaskDeadlineRegistration {
232        let TaskDeadlineArmPlan { entry, replacing } = plan;
233        let identity = entry.token().node();
234        if let Some(replacing) = replacing {
235            let removed = self.heap_mut(replacing).remove_node(identity);
236            assert!(
237                removed.is_some(),
238                "prepared replacement must retain its physical task deadline entry"
239            );
240        }
241        let registration = TaskDeadlineRegistration::new(
242            entry.thread(),
243            entry.token(),
244            entry.deadline(),
245            entry.kind(),
246            entry.class(),
247        );
248        self.heap_mut(entry.class()).push(entry);
249        registration
250    }
251
252    /// Cancels one matching arm operation and immediately releases its heap slot.
253    ///
254    /// Unlike lazy tombstoning, physical removal releases capacity immediately
255    /// and makes the registration terminal as soon as this method returns.
256    pub fn cancel(&mut self, registration: &TaskDeadlineRegistration) -> bool {
257        let Some(cancellation) = self.begin_cancel(registration) else {
258            return false;
259        };
260        cancellation.commit();
261        true
262    }
263
264    pub(crate) fn begin_cancel(
265        &mut self,
266        registration: &TaskDeadlineRegistration,
267    ) -> Option<TaskDeadlineCancelTxn> {
268        self.heap_mut(registration.class())
269            .remove(
270                registration.thread(),
271                registration.token(),
272                registration.kind(),
273            )
274            .map(|entry| TaskDeadlineCancelTxn { entry })
275    }
276
277    fn restore_cancelled(&mut self, entry: TimerEntry) {
278        let heap = self.heap_mut(entry.class());
279        assert!(
280            !heap.contains_node(entry.token().node()),
281            "cancelled task deadline node was reused before transaction completion"
282        );
283        heap.push(entry);
284    }
285
286    /// Returns the earliest logical task deadline without mutating the queue.
287    pub fn next_deadline(&self) -> Option<MonotonicDeadline> {
288        self.next_entry_in(&[
289            TaskDeadlineClass::ParkSoft,
290            TaskDeadlineClass::ParkHard,
291            TaskDeadlineClass::DeadlineCbs,
292            TaskDeadlineClass::DeadlineZeroLag,
293        ])
294        .map(TimerEntry::deadline)
295    }
296
297    pub(crate) fn next_soft_deadline(&self) -> Option<MonotonicDeadline> {
298        self.heap(TaskDeadlineClass::ParkSoft)
299            .peek()
300            .map(TimerEntry::deadline)
301    }
302
303    pub(crate) fn next_hard_deadline(&self) -> Option<MonotonicDeadline> {
304        self.next_entry_in(&[
305            TaskDeadlineClass::ParkHard,
306            TaskDeadlineClass::DeadlineCbs,
307            TaskDeadlineClass::DeadlineZeroLag,
308        ])
309        .map(TimerEntry::deadline)
310    }
311
312    pub(crate) fn has_immediately_actionable_soft_entry(&self, now: MonotonicInstant) -> bool {
313        self.heap(TaskDeadlineClass::ParkSoft)
314            .peek()
315            .is_some_and(|entry| now.reached(entry.deadline()))
316    }
317
318    /// Expires timers into caller-provided storage without allocating or invoking
319    /// callbacks.
320    pub fn expire(
321        &mut self,
322        request: TaskDeadlineExpireRequest,
323        output: &mut [ExpiredTaskDeadline],
324    ) -> TaskDeadlineExpireBatch {
325        self.expire_classes(
326            request,
327            output,
328            &[
329                TaskDeadlineClass::ParkSoft,
330                TaskDeadlineClass::ParkHard,
331                TaskDeadlineClass::DeadlineCbs,
332                TaskDeadlineClass::DeadlineZeroLag,
333            ],
334        )
335    }
336
337    pub(crate) fn expire_soft(
338        &mut self,
339        request: TaskDeadlineExpireRequest,
340        output: &mut [ExpiredTaskDeadline],
341    ) -> TaskDeadlineExpireBatch {
342        self.expire_classes(request, output, &[TaskDeadlineClass::ParkSoft])
343    }
344
345    pub(crate) fn claim_due_hard(
346        &mut self,
347        now: MonotonicInstant,
348    ) -> Option<HardTaskDeadlineClaim> {
349        let classes = [
350            TaskDeadlineClass::ParkHard,
351            TaskDeadlineClass::DeadlineCbs,
352            TaskDeadlineClass::DeadlineZeroLag,
353        ];
354        let class = self.next_class_in(&classes)?;
355        if !now.reached(self.heap(class).peek()?.deadline()) {
356            return None;
357        }
358        let mut entry = self
359            .heap_mut(class)
360            .pop_min()
361            .expect("peek proved the fixed timer heap is non-empty");
362        let event = ExpiredTaskDeadline::new(
363            entry.thread(),
364            entry.token(),
365            entry.deadline(),
366            entry.kind(),
367        );
368        if class == TaskDeadlineClass::ParkHard {
369            Some(HardTaskDeadlineClaim::Park {
370                event,
371                thread: entry
372                    .take_park_thread()
373                    .expect("a hard park deadline retains its scheduler thread"),
374            })
375        } else {
376            Some(HardTaskDeadlineClaim::Scheduler(event))
377        }
378    }
379
380    fn expire_classes(
381        &mut self,
382        request: TaskDeadlineExpireRequest,
383        output: &mut [ExpiredTaskDeadline],
384        classes: &[TaskDeadlineClass],
385    ) -> TaskDeadlineExpireBatch {
386        let mut processed = 0;
387        let mut expired = 0;
388
389        while processed < request.batch_limit {
390            let Some(class) = self.next_class_in(classes) else {
391                break;
392            };
393            if !request.now.reached(
394                self.heap(class)
395                    .peek()
396                    .expect("selected timer class remains non-empty")
397                    .deadline(),
398            ) {
399                break;
400            }
401            if expired == output.len() {
402                break;
403            }
404
405            let entry = self
406                .heap_mut(class)
407                .pop_min()
408                .expect("peek proved the fixed timer heap is non-empty");
409            processed += 1;
410            output[expired] = ExpiredTaskDeadline::new(
411                entry.thread(),
412                entry.token(),
413                entry.deadline(),
414                entry.kind(),
415            );
416            expired += 1;
417        }
418
419        let next_deadline = self.next_entry_in(classes).map(TimerEntry::deadline);
420        let pending = next_deadline.is_some_and(|deadline| request.now.reached(deadline));
421        TaskDeadlineExpireBatch {
422            processed,
423            expired,
424            pending,
425            next_deadline,
426        }
427    }
428
429    /// Returns the preallocated entry capacity.
430    pub const fn capacity(&self) -> usize {
431        self.capacity_per_class
432    }
433
434    /// Returns the number of active task deadline entries in storage.
435    pub fn len(&self) -> usize {
436        self.heaps.iter().map(TimerHeap::len).sum()
437    }
438
439    /// Reports whether no timer entries remain.
440    pub fn is_empty(&self) -> bool {
441        self.heaps.iter().all(TimerHeap::is_empty)
442    }
443
444    fn next_entry_in(&self, classes: &[TaskDeadlineClass]) -> Option<&TimerEntry> {
445        self.next_class_in(classes)
446            .and_then(|class| self.heap(class).peek())
447    }
448
449    fn next_class_in(&self, classes: &[TaskDeadlineClass]) -> Option<TaskDeadlineClass> {
450        classes
451            .iter()
452            .copied()
453            .filter(|class| !self.heap(*class).is_empty())
454            .reduce(|earliest, candidate| {
455                if self
456                    .heap(candidate)
457                    .peek()
458                    .expect("candidate timer class remains non-empty")
459                    .precedes(
460                        self.heap(earliest)
461                            .peek()
462                            .expect("selected timer class remains non-empty"),
463                    )
464                {
465                    candidate
466                } else {
467                    earliest
468                }
469            })
470    }
471
472    fn find_node_class(&self, node: TaskDeadlineNodeId) -> Option<TaskDeadlineClass> {
473        TaskDeadlineClass::ALL
474            .into_iter()
475            .find(|class| self.heap(*class).contains_node(node))
476    }
477}
478
479#[cfg(test)]
480mod tests;
ax_task/time/queue/mod.rs

ax_task/time/queue/
mod.rs
