ax_task/sched/algorithm/
clock.rs

1//! Linux-style scheduler clock arithmetic.
2//!
3//! Scheduler timestamps deliberately remain an unsigned wrapping domain. Linux
4//! `rq_clock()` and SCHED_DEADLINE reserve the high bit of every relative
5//! interval, then compare absolute timestamps through a signed subtraction.
6//! This is distinct from the signed, finite `ktime_t` domain used by hrtimers
7//! and physical clockevent devices.
8
9use core::cmp::Ordering;
10
11use crate::time::{MonotonicDeadline, MonotonicInstant};
12
13pub(crate) const SCHEDULER_TIME_HALF_RANGE: u64 = 1_u64 << 63;
14
15/// One absolute timestamp in the wrapping per-runqueue clock domain.
16#[derive(Clone, Copy, Debug, Eq, PartialEq)]
17#[repr(transparent)]
18pub struct SchedulerTimestamp(u64);
19
20/// Result of mapping a runqueue timestamp onto the physical monotonic clock.
21#[derive(Clone, Copy, Debug, Eq, PartialEq)]
22pub(crate) enum SchedulerClockEvent {
23    /// The scheduler event is already due and must be handled by its runqueue.
24    Due,
25    /// A future event that may be submitted to the physical clockevent owner.
26    Future(MonotonicDeadline),
27}
28
29impl SchedulerTimestamp {
30    /// Creates one raw sample in the wrapping scheduler-clock domain.
31    pub const fn from_nanos(nanos: u64) -> Self {
32        Self(nanos)
33    }
34
35    /// Returns the raw wrapping scheduler timestamp.
36    pub const fn as_nanos(self) -> u64 {
37        self.0
38    }
39
40    /// Advances by a validated relative interval.
41    pub(crate) const fn advance(self, delta_ns: u64) -> Self {
42        assert!(delta_ns < SCHEDULER_TIME_HALF_RANGE);
43        Self(self.0.wrapping_add(delta_ns))
44    }
45
46    /// Moves backwards by one validated relative interval.
47    pub(crate) const fn retreat(self, delta_ns: u64) -> Self {
48        assert!(delta_ns < SCHEDULER_TIME_HALF_RANGE);
49        Self(self.0.wrapping_sub(delta_ns))
50    }
51
52    /// Returns the forward distance from `earlier` to this timestamp.
53    pub(crate) const fn since(self, earlier: Self) -> u64 {
54        let delta = self.0.wrapping_sub(earlier.0);
55        assert!(delta < SCHEDULER_TIME_HALF_RANGE);
56        delta
57    }
58
59    pub(crate) const fn is_before(self, other: Self) -> bool {
60        (self.0.wrapping_sub(other.0) as i64) < 0
61    }
62
63    pub(crate) const fn is_reached_by(self, now: Self) -> bool {
64        !now.is_before(self)
65    }
66}
67
68impl Ord for SchedulerTimestamp {
69    fn cmp(&self, other: &Self) -> Ordering {
70        scheduler_time_cmp(self.0, other.0)
71    }
72}
73
74impl PartialOrd for SchedulerTimestamp {
75    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
76        Some(self.cmp(other))
77    }
78}
79
80pub(crate) fn scheduler_time_cmp(left: u64, right: u64) -> Ordering {
81    if left == right {
82        Ordering::Equal
83    } else if SchedulerTimestamp::from_nanos(left).is_before(SchedulerTimestamp::from_nanos(right))
84    {
85        Ordering::Less
86    } else {
87        Ordering::Greater
88    }
89}
90
91pub(crate) const fn scheduler_time_reached(now_ns: u64, deadline_ns: u64) -> bool {
92    SchedulerTimestamp::from_nanos(deadline_ns)
93        .is_reached_by(SchedulerTimestamp::from_nanos(now_ns))
94}
95
96/// Maps one future scheduler timestamp onto the finite physical clock domain.
97///
98/// This is the equivalent of Linux `start_dl_timer()`: the scheduler keeps its
99/// absolute timestamp in `rq_clock()` space, then transfers only the forward
100/// distance onto `CLOCK_MONOTONIC`. A past scheduler timestamp is never armed
101/// as a physical timer.
102pub(crate) fn scheduler_clock_event(
103    scheduler_now_ns: u64,
104    monotonic_now: MonotonicInstant,
105    scheduler_deadline_ns: u64,
106) -> SchedulerClockEvent {
107    let scheduler_now = SchedulerTimestamp::from_nanos(scheduler_now_ns);
108    let scheduler_deadline = SchedulerTimestamp::from_nanos(scheduler_deadline_ns);
109    if scheduler_deadline.is_reached_by(scheduler_now) {
110        return SchedulerClockEvent::Due;
111    }
112    let deadline = monotonic_now.deadline_after(core::time::Duration::from_nanos(
113        scheduler_deadline.since(scheduler_now),
114    ));
115    if monotonic_now.reached(deadline) {
116        SchedulerClockEvent::Due
117    } else {
118        SchedulerClockEvent::Future(deadline)
119    }
120}
121
122#[cfg(test)]
123mod tests {
124    use super::*;
125
126    #[test]
127    fn scheduler_deadline_mapping_handles_wrap_and_elapsed_events() {
128        let monotonic_now = MonotonicInstant::from_nanos(100).unwrap();
129        assert_eq!(
130            scheduler_clock_event(u64::MAX - 2, monotonic_now, 2),
131            SchedulerClockEvent::Future(MonotonicDeadline::from_nanos(105).unwrap())
132        );
133        assert_eq!(
134            scheduler_clock_event(10, monotonic_now, 9),
135            SchedulerClockEvent::Due
136        );
137    }
138}
ax_task/sched/algorithm/clock.rs

ax_task/sched/algorithm/
clock.rs
