ax_task/sched/
policy.rs

1//! Validated scheduling policies and Deadline CBS state.
2
3use alloc::sync::Arc;
4use core::cmp::Ordering;
5
6use crate::{
7    runtime::{config::DEFAULT_RR_QUANTUM_NS, lock::IrqTicketLock},
8    sched::{
9        SchedulerTimestamp,
10        algorithm::{SCHEDULER_TIME_HALF_RANGE, scheduler_time_cmp},
11    },
12    thread::TaskError,
13};
14
15pub(crate) const DEADLINE_CLASS_RANK: u8 = 1;
16pub(crate) const REALTIME_CLASS_RANK: u8 = 2;
17
18/// Linux-compatible nice value in the inclusive range `-20..=19`.
19#[repr(transparent)]
20#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
21pub struct Nice(i8);
22
23impl Nice {
24    /// Default fair priority.
25    pub const ZERO: Self = Self(0);
26    /// Lowest nice-derived Fair weight. SCHED_IDLE uses `WEIGHT_IDLEPRIO`
27    /// independently and preserves its stored nice value.
28    pub const LOWEST: Self = Self(19);
29
30    /// Validates and creates a nice value.
31    pub const fn new(value: i8) -> Result<Self, TaskError> {
32        if value >= -20 && value <= 19 {
33            Ok(Self(value))
34        } else {
35            Err(TaskError::InvalidNice(value))
36        }
37    }
38
39    /// Returns the signed nice value.
40    pub const fn get(self) -> i8 {
41        self.0
42    }
43
44    /// Returns the Linux scheduler weight corresponding to this nice value.
45    pub const fn weight(self) -> u32 {
46        NICE_WEIGHTS[(self.0 + 20) as usize]
47    }
48}
49
50/// POSIX real-time priority in the inclusive range `1..=99`.
51#[repr(transparent)]
52#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
53pub struct RtPriority(u8);
54
55impl RtPriority {
56    /// Validates and creates a real-time priority.
57    pub const fn new(value: u8) -> Result<Self, TaskError> {
58        if value >= 1 && value <= 99 {
59            Ok(Self(value))
60        } else {
61            Err(TaskError::InvalidRtPriority(value))
62        }
63    }
64
65    /// Returns the POSIX priority number.
66    pub const fn get(self) -> u8 {
67        self.0
68    }
69}
70
71/// Fair-class scheduling behavior.
72#[derive(Clone, Copy, Debug, Eq, PartialEq)]
73pub enum FairMode {
74    /// Interactive/default behavior with wake-up preemption.
75    Normal,
76    /// Throughput behavior without ordinary wake-up preemption.
77    Batch,
78    /// Lowest-priority fair work, selected after other fair work.
79    Idle,
80}
81
82/// Linux-compatible Deadline behavior flags supported by the core.
83#[repr(transparent)]
84#[derive(Clone, Copy, Debug, Eq, PartialEq)]
85pub struct DeadlineFlags(u32);
86
87impl DeadlineFlags {
88    /// No optional Deadline behavior.
89    pub const NONE: Self = Self(0);
90    /// Permit unused root-domain Deadline bandwidth to be reclaimed.
91    pub const RECLAIM: Self = Self(1 << 0);
92    /// Request a task-context overrun notification.
93    pub const DL_OVERRUN: Self = Self(1 << 1);
94    /// Reset the scheduling policy when a child is created.
95    pub const RESET_ON_FORK: Self = Self(1 << 2);
96    const KNOWN_BITS: u32 = Self::RECLAIM.0 | Self::DL_OVERRUN.0 | Self::RESET_ON_FORK.0;
97
98    /// Creates validated flags from their integer representation.
99    pub const fn from_bits(bits: u32) -> Result<Self, TaskError> {
100        if bits & !Self::KNOWN_BITS == 0 {
101            Ok(Self(bits))
102        } else {
103            Err(TaskError::UnsupportedDeadlineFlags(bits))
104        }
105    }
106
107    /// Returns the integer representation.
108    pub const fn bits(self) -> u32 {
109        self.0
110    }
111
112    /// Tests whether every bit in `other` is present.
113    pub const fn contains(self, other: Self) -> bool {
114        self.0 & other.0 == other.0
115    }
116}
117
118impl core::ops::BitOr for DeadlineFlags {
119    type Output = Self;
120
121    fn bitor(self, rhs: Self) -> Self::Output {
122        Self(self.0 | rhs.0)
123    }
124}
125
126/// Validated SCHED_DEADLINE reservation parameters.
127#[derive(Clone, Copy, Debug, Eq, PartialEq)]
128pub struct DeadlinePolicy {
129    runtime_ns: u64,
130    deadline_ns: u64,
131    period_ns: u64,
132    flags: DeadlineFlags,
133}
134
135impl DeadlinePolicy {
136    /// Validates `0 < runtime <= deadline <= period` and creates a reservation.
137    pub const fn new(
138        runtime_ns: u64,
139        deadline_ns: u64,
140        period_ns: u64,
141        flags: DeadlineFlags,
142    ) -> Result<Self, TaskError> {
143        if runtime_ns > 0
144            && runtime_ns <= deadline_ns
145            && deadline_ns <= period_ns
146            && period_ns < SCHEDULER_TIME_HALF_RANGE
147        {
148            Ok(Self {
149                runtime_ns,
150                deadline_ns,
151                period_ns,
152                flags,
153            })
154        } else {
155            Err(TaskError::InvalidDeadline {
156                runtime_ns,
157                deadline_ns,
158                period_ns,
159            })
160        }
161    }
162
163    /// Returns the reserved runtime in nanoseconds.
164    pub const fn runtime_ns(self) -> u64 {
165        self.runtime_ns
166    }
167
168    /// Returns the relative deadline in nanoseconds.
169    pub const fn deadline_ns(self) -> u64 {
170        self.deadline_ns
171    }
172
173    /// Returns the replenishment period in nanoseconds.
174    pub const fn period_ns(self) -> u64 {
175        self.period_ns
176    }
177
178    /// Returns optional Deadline behavior flags.
179    pub const fn flags(self) -> DeadlineFlags {
180        self.flags
181    }
182}
183
184/// Base scheduling policy of a thread.
185#[derive(Clone, Copy, Debug, Eq, PartialEq)]
186pub enum SchedulePolicy {
187    /// Per-CPU kernel stopper work, above Deadline and POSIX RT classes.
188    ///
189    /// This class is reserved for runtime-owned workers that implement Linux
190    /// CPU-stopper semantics. User-facing policy adapters must not construct it.
191    KernelStop,
192    /// EEVDF fair scheduling.
193    Fair {
194        /// Nice-derived weight.
195        nice: Nice,
196        /// Normal, batch, or idle fair semantics.
197        mode: FairMode,
198    },
199    /// Fixed-priority first-in/first-out scheduling.
200    Fifo {
201        /// POSIX RT priority.
202        priority: RtPriority,
203    },
204    /// Fixed-priority round-robin scheduling.
205    RoundRobin {
206        /// POSIX RT priority.
207        priority: RtPriority,
208        /// Per-dispatch quantum in nanoseconds.
209        quantum_ns: u64,
210    },
211    /// Earliest-deadline-first scheduling with CBS accounting.
212    Deadline(DeadlinePolicy),
213}
214
215impl SchedulePolicy {
216    /// Linux `WEIGHT_IDLEPRIO`: the fixed load weight of a SCHED_IDLE task.
217    pub(crate) const IDLE_POLICY_WEIGHT: u32 = 3;
218
219    /// Returns the instantaneous cross-CPU demand represented by this policy.
220    ///
221    /// Fair policies use the same Linux nice weights as EEVDF. Fixed-priority
222    /// and Deadline work consume one normal-capacity unit until a future
223    /// utilization tracker can provide a stronger class-specific estimate.
224    pub(crate) const fn placement_demand(self) -> u64 {
225        match self {
226            Self::KernelStop => 0,
227            Self::Fair {
228                mode: FairMode::Idle,
229                ..
230            } => Self::IDLE_POLICY_WEIGHT as u64,
231            Self::Fair { nice, .. } => nice.weight() as u64,
232            Self::Fifo { .. } | Self::RoundRobin { .. } | Self::Deadline(_) => {
233                Nice::ZERO.weight() as u64
234            }
235        }
236    }
237
238    /// Returns the nice-weighted Fair component of cross-CPU demand.
239    pub(crate) const fn fair_demand(self) -> u64 {
240        match self {
241            Self::Fair { .. } => self.placement_demand(),
242            Self::KernelStop | Self::Fifo { .. } | Self::RoundRobin { .. } | Self::Deadline(_) => 0,
243        }
244    }
245
246    /// Validates policy fields that remain directly constructible through enum variants.
247    pub const fn validate(self) -> Result<(), TaskError> {
248        match self {
249            Self::RoundRobin { quantum_ns: 0, .. } => Err(TaskError::InvalidRoundRobinQuantum),
250            _ => Ok(()),
251        }
252    }
253
254    /// Creates a fair policy.
255    pub const fn fair(nice: Nice, mode: FairMode) -> Self {
256        Self::Fair { nice, mode }
257    }
258
259    /// Creates the runtime-only per-CPU stopper policy.
260    #[doc(hidden)]
261    pub const fn kernel_stop() -> Self {
262        Self::KernelStop
263    }
264
265    /// Creates a FIFO policy.
266    pub const fn fifo(priority: RtPriority) -> Self {
267        Self::Fifo { priority }
268    }
269
270    /// Creates a round-robin policy with the Linux default 100 ms quantum.
271    pub const fn round_robin(priority: RtPriority) -> Self {
272        Self::RoundRobin {
273            priority,
274            quantum_ns: DEFAULT_RR_QUANTUM_NS,
275        }
276    }
277
278    /// Creates a round-robin policy with an explicit quantum.
279    pub const fn round_robin_with_quantum(
280        priority: RtPriority,
281        quantum_ns: u64,
282    ) -> Result<Self, TaskError> {
283        if quantum_ns == 0 {
284            Err(TaskError::InvalidRoundRobinQuantum)
285        } else {
286            Ok(Self::RoundRobin {
287                priority,
288                quantum_ns,
289            })
290        }
291    }
292
293    /// Creates a Deadline policy.
294    pub const fn deadline(policy: DeadlinePolicy) -> Self {
295        Self::Deadline(policy)
296    }
297
298    /// Returns the strict scheduler class rank, where smaller values run first.
299    ///
300    /// Linux maps SCHED_IDLE onto `fair_sched_class`: Normal, Batch, and Idle
301    /// policy tasks share this rank and compete inside one EEVDF tree. The
302    /// per-CPU dedicated idle thread is not a policy class and remains the
303    /// dispatch layer's last-choice fallback.
304    pub const fn class_rank(&self) -> u8 {
305        match self {
306            Self::KernelStop => 0,
307            Self::Deadline(_) => DEADLINE_CLASS_RANK,
308            Self::Fifo { .. } | Self::RoundRobin { .. } => REALTIME_CLASS_RANK,
309            Self::Fair { .. } => 3,
310        }
311    }
312
313    /// Returns the fixed real-time priority for FIFO/RR policies.
314    pub(crate) const fn rt_priority(self) -> Option<RtPriority> {
315        match self {
316            Self::Fifo { priority } | Self::RoundRobin { priority, .. } => Some(priority),
317            Self::KernelStop | Self::Fair { .. } | Self::Deadline(_) => None,
318        }
319    }
320
321    /// Creates an urgency key suitable for PI waiter ordering.
322    pub(crate) const fn scheduling_key(self, sequence: u64) -> SchedulingKey {
323        let urgency = self.scheduling_urgency();
324        SchedulingKey::new(urgency.class_rank(), urgency.primary(), sequence)
325    }
326
327    /// Returns scheduler urgency without an identity or arrival tie-break.
328    pub(crate) const fn scheduling_urgency(&self) -> SchedulingUrgency {
329        let primary = match self {
330            Self::KernelStop => 0,
331            Self::Deadline(policy) => policy.deadline_ns(),
332            Self::Fifo { priority } | Self::RoundRobin { priority, .. } => {
333                99 - priority.get() as u64
334            }
335            Self::Fair { nice, .. } => (nice.get() as i16 + 20) as u64,
336        };
337        SchedulingUrgency::new(self.class_rank(), primary)
338    }
339}
340
341impl Default for SchedulePolicy {
342    fn default() -> Self {
343        Self::fair(Nice::ZERO, FairMode::Normal)
344    }
345}
346
347fn density_exceeds_reservation(
348    remaining_runtime_ns: u128,
349    time_to_deadline_ns: u64,
350    policy: DeadlinePolicy,
351) -> bool {
352    remaining_runtime_ns * policy.deadline_ns() as u128
353        > policy.runtime_ns() as u128 * time_to_deadline_ns as u128
354}
355
356fn revised_wakeup_runtime(time_to_deadline_ns: u64, policy: DeadlinePolicy) -> i128 {
357    let runtime_ns =
358        (policy.runtime_ns() as u128 * time_to_deadline_ns as u128) / policy.deadline_ns() as u128;
359    runtime_ns as i128
360}
361
362/// Scheduler-class urgency without an identity or queue-order tie-break.
363#[derive(Clone, Copy, Debug, Eq, PartialEq)]
364pub(crate) struct SchedulingUrgency {
365    class_rank: u8,
366    primary: u64,
367}
368
369impl SchedulingUrgency {
370    /// Creates class-local urgency; lower values are more urgent.
371    pub const fn new(class_rank: u8, primary: u64) -> Self {
372        Self {
373            class_rank,
374            primary,
375        }
376    }
377
378    /// Returns the scheduler-class rank.
379    pub const fn class_rank(self) -> u8 {
380        self.class_rank
381    }
382
383    /// Returns the class-local urgency value.
384    pub const fn primary(self) -> u64 {
385        self.primary
386    }
387}
388
389impl Ord for SchedulingUrgency {
390    fn cmp(&self, other: &Self) -> Ordering {
391        self.class_rank.cmp(&other.class_rank).then_with(|| {
392            if self.class_rank == DEADLINE_CLASS_RANK {
393                scheduler_time_cmp(self.primary, other.primary)
394            } else {
395                self.primary.cmp(&other.primary)
396            }
397        })
398    }
399}
400
401impl PartialOrd for SchedulingUrgency {
402    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
403        Some(self.cmp(other))
404    }
405}
406
407/// Total ordering key used for runqueue and deterministic snapshot ordering.
408#[derive(Clone, Copy, Debug, Eq, PartialEq)]
409pub(crate) struct SchedulingKey {
410    class_rank: u8,
411    primary: u64,
412    sequence: u64,
413}
414
415impl SchedulingKey {
416    /// Creates a stable urgency key for a policy and class-local value.
417    pub const fn new(class_rank: u8, primary: u64, sequence: u64) -> Self {
418        Self {
419            class_rank,
420            primary,
421            sequence,
422        }
423    }
424
425    /// Returns the scheduler-class rank encoded in this urgency key.
426    pub const fn class_rank(self) -> u8 {
427        self.class_rank
428    }
429
430    /// Returns the class-local urgency value.
431    pub const fn primary(self) -> u64 {
432        self.primary
433    }
434}
435
436impl Ord for SchedulingKey {
437    fn cmp(&self, other: &Self) -> Ordering {
438        self.class_rank
439            .cmp(&other.class_rank)
440            .then_with(|| {
441                if self.class_rank == DEADLINE_CLASS_RANK {
442                    scheduler_time_cmp(self.primary, other.primary)
443                } else {
444                    self.primary.cmp(&other.primary)
445                }
446            })
447            .then_with(|| self.sequence.cmp(&other.sequence))
448    }
449}
450
451impl PartialOrd for SchedulingKey {
452    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
453        Some(self.cmp(other))
454    }
455}
456
457const NICE_WEIGHTS: [u32; 40] = [
458    88761, 71755, 56483, 46273, 36291, 29154, 23254, 18705, 14949, 11916, 9548, 7620, 6100, 4904,
459    3906, 3121, 2501, 1991, 1586, 1277, 1024, 820, 655, 526, 423, 335, 272, 215, 172, 137, 110, 87,
460    70, 56, 45, 36, 29, 23, 18, 15,
461];
462
463#[cfg(test)]
464mod tests;
465
466mod deadline;
467pub(crate) use deadline::{DeadlineEntity, DeadlineServer};
ax_task/sched/policy.rs

ax_task/sched/
policy.rs
