ax_task/time/queue/
kernel.rs

1//! Task-context kernel callbacks sharing the scheduler clockevent owner.
2
3use alloc::{boxed::Box, vec::Vec};
4use core::{
5    fmt,
6    num::NonZeroU64,
7    sync::atomic::{AtomicU64, Ordering},
8};
9
10use super::TaskDeadlineError;
11use crate::{
12    sched::CpuId,
13    time::{MonotonicDeadline, MonotonicInstant},
14};
15
16static NEXT_KERNEL_TIMER_ID: AtomicU64 = AtomicU64::new(1);
17
18/// Callback executed by the owner CPU's `ktimers/%u` service thread.
19pub type KernelTimerCallback = Box<dyn FnOnce(MonotonicInstant) + Send + 'static>;
20
21/// Callback for a stable timer registration that may restart itself.
22pub type RestartableKernelTimerCallback =
23    Box<dyn FnMut(MonotonicInstant) -> KernelTimerAction + Send + 'static>;
24/// Owned callback for an explicitly hard-expiry kernel timer.
25pub type HardRestartableKernelTimerCallback =
26    Box<dyn FnMut(MonotonicInstant) -> HardKernelTimerAction + Send + 'static>;
27
28/// Explicit capability for a bounded callback that may execute in hard IRQ.
29///
30/// The callback allocation is created and destroyed in task context. The
31/// timer base invokes it without allocating, freeing, sleeping, performing a
32/// registry lookup, or holding the deadline-base lock. Completion is moved to
33/// `ktimers/%u` before the callback payload can be dropped.
34pub struct HardKernelTimerCallback {
35    callback: HardRestartableKernelTimerCallback,
36}
37
38impl HardKernelTimerCallback {
39    /// Creates one hard-expiry callback capability.
40    ///
41    /// # Safety
42    ///
43    /// Every invocation must be bounded, non-panicking, allocation-free and
44    /// valid in hard IRQ context. It must use only IRQ-safe synchronization
45    /// and prebound capabilities; it may not sleep, perform registry lookup,
46    /// invoke an untyped external callback, or clone/drop owning references.
47    pub unsafe fn new(callback: HardRestartableKernelTimerCallback) -> Self {
48        Self { callback }
49    }
50
51    fn invoke(&mut self, expired_at: MonotonicInstant) -> HardKernelTimerAction {
52        (self.callback)(expired_at)
53    }
54}
55
56/// Result returned by an explicitly hard-expiry callback.
57#[derive(Clone, Copy, Debug, Eq, PartialEq)]
58pub enum HardKernelTimerAction {
59    /// Destroy this registration after task-context reclamation.
60    Complete,
61    /// Keep the stable registration inactive until task context arms it again.
62    Disarm,
63    /// Reinsert the same registration at a new absolute deadline.
64    Rearm(MonotonicDeadline),
65}
66
67/// Result returned by a restartable kernel-timer callback.
68#[derive(Clone, Copy, Debug, Eq, PartialEq)]
69pub enum KernelTimerAction {
70    /// Finish this registration after the current callback.
71    Complete,
72    /// Reinsert the same registration at a new absolute deadline.
73    Rearm(MonotonicDeadline),
74}
75
76/// Stable identity of one host kernel-timer registration.
77#[derive(Clone, Copy, Debug, Eq, PartialEq)]
78pub struct KernelTimerHandle {
79    owner: CpuId,
80    identity: NonZeroU64,
81}
82
83impl KernelTimerHandle {
84    pub(crate) const fn new(owner: CpuId, identity: NonZeroU64) -> Self {
85        Self { owner, identity }
86    }
87
88    /// Returns the CPU deadline base that owns this registration.
89    pub const fn owner(self) -> CpuId {
90        self.owner
91    }
92
93    pub(crate) const fn identity(self) -> NonZeroU64 {
94        self.identity
95    }
96}
97
98/// Capability to arm or disarm an explicitly hard-expiry registration.
99///
100/// Only hard registration creates this capability. Conversion to the general
101/// cancellation handle is one-way; neither handle owns the callback payload.
102#[derive(Clone, Copy, Debug, Eq, PartialEq)]
103pub struct HardKernelTimerHandle(KernelTimerHandle);
104
105impl HardKernelTimerHandle {
106    pub(crate) const fn new(handle: KernelTimerHandle) -> Self {
107        Self(handle)
108    }
109
110    /// Returns the CPU deadline base that owns this registration.
111    pub const fn owner(self) -> CpuId {
112        self.0.owner()
113    }
114}
115
116impl From<HardKernelTimerHandle> for KernelTimerHandle {
117    fn from(handle: HardKernelTimerHandle) -> Self {
118        handle.0
119    }
120}
121
122/// Outcome of a non-blocking kernel-timer cancellation attempt.
123#[derive(Clone, Copy, Debug, Eq, PartialEq)]
124pub enum KernelTimerCancelOutcome {
125    /// The registration was removed and its payload is reclaimed before return.
126    Cancelled,
127    /// Cancellation was accepted, but a claimed callback or deferred payload
128    /// reclamation is still in flight. The callback cannot restart itself.
129    /// This result does not permit the caller to release borrowed resources.
130    CancellationDeferred,
131    /// No registration remains in the base for this handle. Another caller
132    /// may still be reclaiming a removed payload; this is not a reclamation fence.
133    AlreadyCompleted,
134}
135
136pub(crate) struct KernelTimerEntry {
137    identity: NonZeroU64,
138    deadline: Option<MonotonicDeadline>,
139    expired_at: Option<MonotonicInstant>,
140    callback: KernelTimerCallbackState,
141}
142
143enum KernelTimerCallbackState {
144    OneShot(Option<KernelTimerCallback>),
145    Restartable(RestartableKernelTimerCallback),
146    HardRestartable(HardKernelTimerCallback),
147}
148
149impl KernelTimerEntry {
150    pub(crate) fn new(
151        deadline: MonotonicDeadline,
152        callback: KernelTimerCallback,
153    ) -> Result<Self, TaskDeadlineError> {
154        Ok(Self {
155            identity: next_kernel_timer_identity()?,
156            deadline: Some(deadline),
157            expired_at: None,
158            callback: KernelTimerCallbackState::OneShot(Some(callback)),
159        })
160    }
161
162    pub(crate) fn new_restartable(
163        deadline: MonotonicDeadline,
164        callback: RestartableKernelTimerCallback,
165    ) -> Result<Self, TaskDeadlineError> {
166        Ok(Self {
167            identity: next_kernel_timer_identity()?,
168            deadline: Some(deadline),
169            expired_at: None,
170            callback: KernelTimerCallbackState::Restartable(callback),
171        })
172    }
173
174    pub(crate) fn new_hard_restartable(
175        deadline: MonotonicDeadline,
176        callback: HardKernelTimerCallback,
177    ) -> Result<Self, TaskDeadlineError> {
178        Ok(Self {
179            identity: next_kernel_timer_identity()?,
180            deadline: Some(deadline),
181            expired_at: None,
182            callback: KernelTimerCallbackState::HardRestartable(callback),
183        })
184    }
185
186    fn deadline(&self) -> MonotonicDeadline {
187        self.deadline
188            .expect("only an armed kernel timer has a deadline")
189    }
190
191    const fn identity(&self) -> NonZeroU64 {
192        self.identity
193    }
194
195    fn expire(&mut self, now: MonotonicInstant) {
196        assert!(self.expired_at.replace(now).is_none());
197    }
198
199    fn rearm(&mut self, deadline: MonotonicDeadline) {
200        self.deadline = Some(deadline);
201        self.expired_at = None;
202    }
203
204    fn disarm(&mut self) -> MonotonicDeadline {
205        self.expired_at = None;
206        self.deadline
207            .take()
208            .expect("only an armed kernel timer can be disarmed")
209    }
210
211    const fn is_armed(&self) -> bool {
212        self.deadline.is_some()
213    }
214
215    const fn is_hard(&self) -> bool {
216        matches!(self.callback, KernelTimerCallbackState::HardRestartable(_))
217    }
218}
219
220fn next_kernel_timer_identity() -> Result<NonZeroU64, TaskDeadlineError> {
221    let identity = NEXT_KERNEL_TIMER_ID
222        .try_update(Ordering::Relaxed, Ordering::Relaxed, |current| {
223            current.checked_add(1)
224        })
225        .map_err(|_| TaskDeadlineError::GenerationExhausted)?;
226    NonZeroU64::new(identity).ok_or(TaskDeadlineError::GenerationExhausted)
227}
228
229impl fmt::Debug for KernelTimerEntry {
230    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
231        formatter
232            .debug_struct("KernelTimerEntry")
233            .field("identity", &self.identity)
234            .field("deadline", &self.deadline)
235            .field("expired_at", &self.expired_at)
236            .finish_non_exhaustive()
237    }
238}
239
240/// One callback claimed by the ktimer worker.
241///
242/// Cancellation while the callback runs leaves a tombstone that prevents a
243/// restartable callback from returning the entry to the active queue.
244pub(crate) struct KernelTimerExecution {
245    entry: KernelTimerEntry,
246}
247
248impl KernelTimerExecution {
249    pub(crate) fn invoke_soft(&mut self) -> KernelTimerAction {
250        let expired_at = self
251            .entry
252            .expired_at
253            .expect("claimed kernel timer must have an expiry sample");
254        match &mut self.entry.callback {
255            KernelTimerCallbackState::OneShot(callback) => {
256                callback
257                    .take()
258                    .expect("kernel timer callback may execute only once")(
259                    expired_at
260                );
261                KernelTimerAction::Complete
262            }
263            KernelTimerCallbackState::Restartable(callback) => callback(expired_at),
264            KernelTimerCallbackState::HardRestartable(_) => {
265                panic!("hard kernel timer must not execute in ktimers/%u")
266            }
267        }
268    }
269
270    /// Invokes an explicitly hard-IRQ-safe callback.
271    ///
272    /// # Safety
273    ///
274    /// The caller must own the CPU's hard-timer execution context with local
275    /// IRQs excluded. The deadline-base lock must not be held.
276    pub(crate) unsafe fn invoke_hard(&mut self) -> HardKernelTimerAction {
277        let expired_at = self
278            .entry
279            .expired_at
280            .expect("claimed hard kernel timer must have an expiry sample");
281        match &mut self.entry.callback {
282            KernelTimerCallbackState::HardRestartable(callback) => callback.invoke(expired_at),
283            KernelTimerCallbackState::OneShot(_) | KernelTimerCallbackState::Restartable(_) => {
284                panic!("task-context kernel timer must not execute in hard IRQ")
285            }
286        }
287    }
288
289    const fn is_hard(&self) -> bool {
290        self.entry.is_hard()
291    }
292}
293
294#[derive(Clone, Copy, Debug, Eq, PartialEq)]
295struct ExecutingKernelTimer {
296    identity: NonZeroU64,
297    hard: bool,
298    disposition: ExecutingKernelTimerDisposition,
299}
300
301#[derive(Clone, Copy, Debug, Eq, PartialEq)]
302enum ExecutingKernelTimerDisposition {
303    Continue,
304    Disarm,
305    Rearm(MonotonicDeadline),
306    Destroy,
307}
308
309/// Result of one bounded hard-IRQ promotion pass.
310#[derive(Clone, Copy, Debug, Eq, PartialEq)]
311pub(crate) struct KernelTimerExpireBatch {
312    expired: usize,
313    pending: bool,
314}
315
316impl KernelTimerExpireBatch {
317    pub(crate) const fn expired(self) -> usize {
318        self.expired
319    }
320
321    pub(crate) const fn pending(self) -> bool {
322        self.pending
323    }
324}
325
326/// Fixed-capacity kernel callback clock base.
327///
328/// Callback ownership is allocated before this queue is locked. Expiry only
329/// moves entries between preallocated vectors, so hard IRQ never
330/// allocates, frees, or invokes arbitrary code.
331pub(crate) struct KernelTimerQueue {
332    active: Vec<KernelTimerEntry>,
333    inactive: Vec<KernelTimerEntry>,
334    expired: Vec<KernelTimerEntry>,
335    executing: Vec<ExecutingKernelTimer>,
336    completed: Vec<KernelTimerEntry>,
337    capacity: usize,
338}
339
340impl fmt::Debug for KernelTimerQueue {
341    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
342        formatter
343            .debug_struct("KernelTimerQueue")
344            .field("active", &self.active)
345            .field("inactive", &self.inactive)
346            .field("expired", &self.expired)
347            .field("executing", &self.executing)
348            .field("completed", &self.completed)
349            .field("capacity", &self.capacity)
350            .finish()
351    }
352}
353
354mod registration;
355
356mod expiry;
357
358mod completion;
359
360mod ordering;
361
362#[cfg(test)]
363mod tests {
364    use alloc::{boxed::Box, sync::Arc};
365    use core::sync::atomic::{AtomicUsize, Ordering};
366
367    use super::*;
368
369    fn deadline(nanos: u64) -> MonotonicDeadline {
370        MonotonicDeadline::from_nanos(nanos).unwrap()
371    }
372
373    fn instant(nanos: u64) -> MonotonicInstant {
374        MonotonicInstant::from_nanos(nanos).unwrap()
375    }
376
377    #[test]
378    fn hard_operations_reject_executing_soft_timer_without_changing_restart() {
379        let entry = KernelTimerEntry::new_restartable(
380            deadline(10),
381            Box::new(|_| KernelTimerAction::Rearm(deadline(20))),
382        )
383        .unwrap();
384        let mut queue = KernelTimerQueue::new(1);
385        let handle = queue.insert(CpuId::new(0), entry).unwrap();
386        queue.expire_due_soft(instant(10), 1);
387        let mut execution = queue.claim_expired().unwrap();
388        assert!(!queue.arm_hard(handle, deadline(30)));
389        assert_eq!(queue.disarm_hard(handle), None);
390        let action = execution.invoke_soft();
391        assert!(queue.complete_soft_execution(execution, action).is_none());
392        assert_eq!(queue.next_soft_deadline(), Some(deadline(20)));
393    }
394
395    #[test]
396    fn restartable_timer_reuses_identity_until_cancelled() {
397        let invocations = Arc::new(AtomicUsize::new(0));
398        let callback_invocations = Arc::clone(&invocations);
399        let entry = KernelTimerEntry::new_restartable(
400            deadline(10),
401            Box::new(move |_| {
402                let invocation = callback_invocations.fetch_add(1, Ordering::Relaxed) + 1;
403                KernelTimerAction::Rearm(deadline(10 + invocation as u64 * 10))
404            }),
405        )
406        .unwrap();
407        let mut queue = KernelTimerQueue::new(1);
408        let handle = queue.insert(CpuId::new(0), entry).unwrap();
409
410        assert_eq!(queue.expire_due_soft(instant(10), 1).expired(), 1);
411        let mut execution = queue.claim_expired().unwrap();
412        let action = execution.invoke_soft();
413        assert!(queue.complete_soft_execution(execution, action).is_none());
414        assert_eq!(queue.next_soft_deadline(), Some(deadline(20)));
415
416        assert_eq!(queue.expire_due_soft(instant(20), 1).expired(), 1);
417        let mut execution = queue.claim_expired().unwrap();
418        let action = execution.invoke_soft();
419        assert!(queue.complete_soft_execution(execution, action).is_none());
420        assert_eq!(queue.next_soft_deadline(), Some(deadline(30)));
421        assert_eq!(invocations.load(Ordering::Relaxed), 2);
422
423        assert!(queue.cancel(handle).1.is_some());
424        assert!(!queue.has_active_work());
425    }
426
427    #[test]
428    fn cancellation_during_callback_prevents_restart() {
429        let entry = KernelTimerEntry::new_restartable(
430            deadline(10),
431            Box::new(|_| KernelTimerAction::Rearm(deadline(20))),
432        )
433        .unwrap();
434        let mut queue = KernelTimerQueue::new(1);
435        let handle = queue.insert(CpuId::new(0), entry).unwrap();
436        assert_eq!(queue.expire_due_soft(instant(10), 1).expired(), 1);
437        let mut execution = queue.claim_expired().unwrap();
438
439        assert_eq!(
440            queue.cancel(handle).0,
441            KernelTimerCancelOutcome::CancellationDeferred
442        );
443        let action = execution.invoke_soft();
444        assert!(queue.complete_soft_execution(execution, action).is_some());
445        assert!(!queue.has_active_work());
446        assert_eq!(
447            queue.cancel(handle).0,
448            KernelTimerCancelOutcome::AlreadyCompleted
449        );
450    }
451
452    #[test]
453    fn hard_completion_defers_callback_reclamation_to_task_context() {
454        let invocations = Arc::new(AtomicUsize::new(0));
455        let callback_invocations = Arc::clone(&invocations);
456        let callback = unsafe {
457            // SAFETY: this test callback performs one bounded atomic operation.
458            HardKernelTimerCallback::new(Box::new(move |_| {
459                callback_invocations.fetch_add(1, Ordering::Relaxed);
460                HardKernelTimerAction::Complete
461            }))
462        };
463        let entry = KernelTimerEntry::new_hard_restartable(deadline(10), callback).unwrap();
464        let mut queue = KernelTimerQueue::new(1);
465        let handle = queue.insert(CpuId::new(0), entry).unwrap();
466
467        let mut execution = queue.claim_due_hard(instant(10)).unwrap();
468        let action = unsafe {
469            // SAFETY: the pure queue test models the hard callback transaction.
470            execution.invoke_hard()
471        };
472        assert!(queue.complete_hard_execution(execution, action));
473        assert_eq!(invocations.load(Ordering::Relaxed), 1);
474        assert!(queue.has_completed());
475        assert!(queue.cancel(handle).1.is_none());
476
477        drop(queue.claim_completed());
478        assert!(!queue.has_active_work());
479    }
480
481    #[test]
482    fn hard_disarm_retains_one_stable_registration_without_reaping() {
483        let callback = unsafe {
484            // SAFETY: this callback returns one constant action.
485            HardKernelTimerCallback::new(Box::new(|_| HardKernelTimerAction::Disarm))
486        };
487        let entry = KernelTimerEntry::new_hard_restartable(deadline(10), callback).unwrap();
488        let mut queue = KernelTimerQueue::new(1);
489        let handle = queue.insert(CpuId::new(0), entry).unwrap();
490
491        let mut execution = queue.claim_due_hard(instant(10)).unwrap();
492        let action = unsafe {
493            // SAFETY: the pure queue test models the hard callback transaction.
494            execution.invoke_hard()
495        };
496        assert!(!queue.complete_hard_execution(execution, action));
497        assert!(queue.has_inactive());
498        assert!(!queue.has_completed());
499
500        assert!(queue.arm_hard(handle, deadline(20)));
501        let mut execution = queue.claim_due_hard(instant(20)).unwrap();
502        let action = unsafe {
503            // SAFETY: the pure queue test models the second hard transaction.
504            execution.invoke_hard()
505        };
506        assert!(!queue.complete_hard_execution(execution, action));
507        assert!(queue.has_inactive());
508        assert!(queue.cancel(handle).1.is_some());
509        assert!(!queue.has_active_work());
510    }
511
512    #[test]
513    fn task_arm_while_hard_callback_runs_owns_the_next_deadline() {
514        let callback = unsafe {
515            // SAFETY: this callback returns one constant action.
516            HardKernelTimerCallback::new(Box::new(|_| HardKernelTimerAction::Disarm))
517        };
518        let entry = KernelTimerEntry::new_hard_restartable(deadline(10), callback).unwrap();
519        let mut queue = KernelTimerQueue::new(1);
520        let handle = queue.insert(CpuId::new(0), entry).unwrap();
521
522        let mut execution = queue.claim_due_hard(instant(10)).unwrap();
523        assert!(queue.arm_hard(handle, deadline(20)));
524        let action = unsafe {
525            // SAFETY: the pure queue test models the hard callback transaction.
526            execution.invoke_hard()
527        };
528        assert!(!queue.complete_hard_execution(execution, action));
529        assert_eq!(queue.next_hard_deadline(), Some(deadline(20)));
530    }
531}
ax_task/time/queue/kernel.rs

ax_task/time/queue/
kernel.rs
