ax_task/time/queue/
node.rs

1//! Task-deadline identity and generation state.
2
3use core::sync::atomic::{AtomicU64, Ordering};
4
5use super::TaskDeadlineError;
6use crate::{thread::ThreadId, time::MonotonicDeadline};
7
8pub(super) const TASK_DEADLINE_CLASS_COUNT: usize = 4;
9static NEXT_TASK_DEADLINE_NODE_ID: AtomicU64 = AtomicU64::new(1);
10
11/// Process-lifetime identity assigned lazily to one physical timer node.
12#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
13#[repr(transparent)]
14pub(super) struct TaskDeadlineNodeId(u64);
15
16impl TaskDeadlineNodeId {
17    const fn from_raw(raw: u64) -> Self {
18        Self(raw)
19    }
20
21    pub(super) const fn as_u64(self) -> u64 {
22        self.0
23    }
24}
25
26/// Independent physical timer slot owned by one scheduler thread.
27#[derive(Clone, Copy, Debug, Eq, PartialEq)]
28#[repr(u8)]
29pub(super) enum TaskDeadlineClass {
30    ParkSoft        = 0,
31    ParkHard        = 1,
32    DeadlineCbs     = 2,
33    DeadlineZeroLag = 3,
34}
35
36impl TaskDeadlineClass {
37    pub(super) const ALL: [Self; TASK_DEADLINE_CLASS_COUNT] = [
38        Self::ParkSoft,
39        Self::ParkHard,
40        Self::DeadlineCbs,
41        Self::DeadlineZeroLag,
42    ];
43
44    pub(super) const fn index(self) -> usize {
45        self as usize
46    }
47}
48
49#[derive(Clone, Copy, Debug, Eq, PartialEq)]
50enum TaskDeadlineNodeKind {
51    Park,
52    DeadlineCbs,
53    DeadlineZeroLag,
54}
55
56impl TaskDeadlineNodeKind {
57    const fn supports(self, class: TaskDeadlineClass) -> bool {
58        matches!(
59            (self, class),
60            (
61                Self::Park,
62                TaskDeadlineClass::ParkSoft | TaskDeadlineClass::ParkHard
63            ) | (Self::DeadlineCbs, TaskDeadlineClass::DeadlineCbs)
64                | (Self::DeadlineZeroLag, TaskDeadlineClass::DeadlineZeroLag)
65        )
66    }
67}
68
69/// Node identity and generation identifying one task-deadline arm operation.
70#[derive(Clone, Copy, Debug, Eq, PartialEq)]
71pub struct TaskDeadlineToken {
72    node: TaskDeadlineNodeId,
73    generation: u64,
74}
75
76impl TaskDeadlineToken {
77    /// Sentinel that cannot identify a live task-deadline arm.
78    pub const NONE: Self = Self {
79        node: TaskDeadlineNodeId::from_raw(0),
80        generation: 0,
81    };
82
83    /// Returns the monotonically assigned arm generation.
84    pub const fn generation(self) -> u64 {
85        self.generation
86    }
87
88    const fn new(node: TaskDeadlineNodeId, generation: u64) -> Self {
89        Self { node, generation }
90    }
91
92    pub(super) const fn node(self) -> TaskDeadlineNodeId {
93        self.node
94    }
95}
96
97/// Task-deadline node embedded in one generation-checked scheduler thread.
98#[derive(Debug)]
99pub struct TaskDeadlineNode {
100    thread: ThreadId,
101    kind: TaskDeadlineNodeKind,
102    identity: AtomicU64,
103    sequence: AtomicU64,
104}
105
106impl TaskDeadlineNode {
107    /// Creates a deadline node owned by one generation-checked scheduler thread.
108    pub const fn for_thread(thread: ThreadId) -> Self {
109        Self::new(thread, TaskDeadlineNodeKind::Park)
110    }
111
112    pub(crate) const fn deadline_cbs_for_thread(thread: ThreadId) -> Self {
113        Self::new(thread, TaskDeadlineNodeKind::DeadlineCbs)
114    }
115
116    pub(crate) const fn deadline_zero_lag_for_thread(thread: ThreadId) -> Self {
117        Self::new(thread, TaskDeadlineNodeKind::DeadlineZeroLag)
118    }
119
120    const fn new(thread: ThreadId, kind: TaskDeadlineNodeKind) -> Self {
121        Self {
122            thread,
123            kind,
124            identity: AtomicU64::new(0),
125            sequence: AtomicU64::new(0),
126        }
127    }
128
129    pub(super) const fn thread(&self) -> ThreadId {
130        self.thread
131    }
132
133    pub(super) const fn supports(&self, class: TaskDeadlineClass) -> bool {
134        self.kind.supports(class)
135    }
136
137    pub(super) fn identity(&self) -> Result<TaskDeadlineNodeId, TaskDeadlineError> {
138        let identity = self.identity.load(Ordering::Acquire);
139        if identity != 0 {
140            return Ok(TaskDeadlineNodeId::from_raw(identity));
141        }
142
143        let mut candidate = NEXT_TASK_DEADLINE_NODE_ID.load(Ordering::Relaxed);
144        loop {
145            if candidate == u64::MAX {
146                return Err(TaskDeadlineError::GenerationExhausted);
147            }
148            match NEXT_TASK_DEADLINE_NODE_ID.compare_exchange_weak(
149                candidate,
150                candidate + 1,
151                Ordering::Relaxed,
152                Ordering::Relaxed,
153            ) {
154                Ok(_) => {
155                    return match self.identity.compare_exchange(
156                        0,
157                        candidate,
158                        Ordering::Release,
159                        Ordering::Acquire,
160                    ) {
161                        Ok(_) => Ok(TaskDeadlineNodeId::from_raw(candidate)),
162                        Err(published) => Ok(TaskDeadlineNodeId::from_raw(published)),
163                    };
164                }
165                Err(updated) => candidate = updated,
166            }
167        }
168    }
169
170    pub(super) fn next_token(
171        &self,
172        identity: TaskDeadlineNodeId,
173    ) -> Result<TaskDeadlineToken, TaskDeadlineError> {
174        debug_assert_eq!(self.identity.load(Ordering::Relaxed), identity.as_u64());
175        let mut sequence = self.sequence.load(Ordering::Relaxed);
176        loop {
177            if sequence == u64::MAX {
178                return Err(TaskDeadlineError::GenerationExhausted);
179            }
180            match self.sequence.compare_exchange_weak(
181                sequence,
182                sequence + 1,
183                Ordering::Relaxed,
184                Ordering::Relaxed,
185            ) {
186                Ok(_) => return Ok(TaskDeadlineToken::new(identity, sequence + 1)),
187                Err(updated) => sequence = updated,
188            }
189        }
190    }
191}
192
193/// Scheduler-owned meaning of one task deadline.
194///
195/// The queue deliberately has no arbitrary callback variant. Every entry is a
196/// value-owned scheduler identity that can be validated again at a safe point.
197#[non_exhaustive]
198#[derive(Clone, Copy, Debug, Eq, PartialEq)]
199pub enum TaskDeadlineKind {
200    /// Timeout for one generation of the thread park handshake.
201    ParkTimeout { park_generation: u64 },
202    /// CBS deadline miss or replenishment boundary.
203    DeadlineCbs,
204    /// GRUB inactive-bandwidth transition at zero lag.
205    DeadlineZeroLag,
206}
207
208impl TaskDeadlineKind {
209    /// Creates a timeout for one generation of a move-only park ticket.
210    pub const fn park_timeout(park_generation: u64) -> Self {
211        Self::ParkTimeout { park_generation }
212    }
213
214    /// Returns the park generation carried by this deadline, when applicable.
215    pub const fn park_generation(self) -> Option<u64> {
216        match self {
217            Self::ParkTimeout { park_generation } => Some(park_generation),
218            Self::DeadlineCbs | Self::DeadlineZeroLag => None,
219        }
220    }
221
222    pub(super) const fn default_class(self) -> TaskDeadlineClass {
223        match self {
224            Self::ParkTimeout { .. } => TaskDeadlineClass::ParkSoft,
225            Self::DeadlineCbs => TaskDeadlineClass::DeadlineCbs,
226            Self::DeadlineZeroLag => TaskDeadlineClass::DeadlineZeroLag,
227        }
228    }
229}
230
231/// Move-only ownership of one physical task-deadline queue registration.
232///
233/// This type intentionally does not implement [`Copy`] or [`Clone`]. A failed
234/// owner-CPU check may borrow it and retry, while successful cancellation or
235/// expiration consumes the one queue entry identified by its generation.
236#[must_use = "a task-deadline registration must remain owned until cancellation or expiration"]
237#[derive(Debug, Eq, PartialEq)]
238pub struct TaskDeadlineRegistration {
239    thread: ThreadId,
240    token: TaskDeadlineToken,
241    deadline: MonotonicDeadline,
242    kind: TaskDeadlineKind,
243    class: TaskDeadlineClass,
244}
245
246impl TaskDeadlineRegistration {
247    pub(super) const fn new(
248        thread: ThreadId,
249        token: TaskDeadlineToken,
250        deadline: MonotonicDeadline,
251        kind: TaskDeadlineKind,
252        class: TaskDeadlineClass,
253    ) -> Self {
254        Self {
255            thread,
256            token,
257            deadline,
258            kind,
259            class,
260        }
261    }
262
263    /// Returns the generation-bearing thread identity.
264    pub const fn thread(&self) -> ThreadId {
265        self.thread
266    }
267
268    /// Returns the arm generation owned by this registration.
269    pub const fn token(&self) -> TaskDeadlineToken {
270        self.token
271    }
272
273    /// Returns the absolute monotonic deadline owned by this registration.
274    pub const fn deadline(&self) -> MonotonicDeadline {
275        self.deadline
276    }
277
278    /// Returns the typed scheduler event.
279    pub const fn kind(&self) -> TaskDeadlineKind {
280        self.kind
281    }
282
283    /// Returns whether IRQ expiry may move this registration into the soft
284    /// expiration buffer before its owner commits the park transition.
285    pub(crate) const fn may_enter_soft_expiry_buffer(&self) -> bool {
286        matches!(self.class, TaskDeadlineClass::ParkSoft)
287    }
288
289    pub(super) const fn class(&self) -> TaskDeadlineClass {
290        self.class
291    }
292}
293
294/// Allocation-free task expiration copied into caller-owned IRQ storage.
295#[derive(Clone, Copy, Debug, Eq, PartialEq)]
296pub struct ExpiredTaskDeadline {
297    thread: ThreadId,
298    token: TaskDeadlineToken,
299    deadline: MonotonicDeadline,
300    valid: bool,
301    kind: TaskDeadlineKind,
302}
303
304impl ExpiredTaskDeadline {
305    /// Empty value used to initialize fixed output arrays.
306    pub const EMPTY: Self = Self {
307        thread: ThreadId::from_parts(0, 0),
308        token: TaskDeadlineToken::NONE,
309        deadline: MonotonicDeadline::ORIGIN,
310        valid: false,
311        kind: TaskDeadlineKind::ParkTimeout { park_generation: 0 },
312    };
313
314    pub(super) const fn new(
315        thread: ThreadId,
316        token: TaskDeadlineToken,
317        deadline: MonotonicDeadline,
318        kind: TaskDeadlineKind,
319    ) -> Self {
320        Self {
321            thread,
322            token,
323            deadline,
324            valid: true,
325            kind,
326        }
327    }
328
329    /// Returns the generation-checked thread owning this deadline.
330    pub const fn thread(self) -> Option<ThreadId> {
331        if self.valid { Some(self.thread) } else { None }
332    }
333
334    /// Returns the generation that reached expiration.
335    pub const fn token(self) -> TaskDeadlineToken {
336        self.token
337    }
338
339    /// Returns the absolute requested deadline.
340    pub const fn deadline(self) -> Option<MonotonicDeadline> {
341        if self.valid {
342            Some(self.deadline)
343        } else {
344            None
345        }
346    }
347
348    /// Returns the typed scheduler event, or `None` for an empty buffer slot.
349    pub const fn kind(self) -> Option<TaskDeadlineKind> {
350        if self.valid { Some(self.kind) } else { None }
351    }
352
353    /// Reports whether this value was written by an expiration pass.
354    pub const fn is_valid(self) -> bool {
355        self.valid
356    }
357}
ax_task/time/queue/node.rs

ax_task/time/queue/
node.rs
