Skip to main content

qualia_core_db/net/peer/runtime/
scheduler.rs

1//! Bounded deficit round-robin across admitted scopes and work classes.
2//!
3//! Essential control, interactive service work, and background replication sit
4//! in separate capped queues. Strict control priority would starve background
5//! reconciliation; an uncapped control queue would let a flood monopolize the
6//! host. Unknown senders are charged to the ledger transient pool before enqueue
7//! (`ReservationLedger::reserve(..., verified_peer = false)`).
8
9use crate::net::qdnf::errors::QdnfError;
10use crate::net::qdnf::types::OperationId;
11
12pub const MAX_SCOPES: usize = 8;
13mod incarnation;
14mod inspect;
15pub const CONTROL_CAP: usize = 4;
16pub const INTERACTIVE_CAP: usize = 8;
17pub const BACKGROUND_CAP: usize = 8;
18
19#[repr(u8)]
20#[derive(Clone, Copy, Debug, PartialEq, Eq)]
21pub enum WorkClass {
22    Control = 0,
23    Interactive = 1,
24    Background = 2,
25}
26
27impl WorkClass {
28    pub const COUNT: usize = 3;
29
30    #[inline]
31    /// `WorkClass::index`.
32    pub const fn index(self) -> usize {
33        self as usize
34    }
35
36    #[inline]
37    /// `WorkClass::from_index`.
38    pub const fn from_index(i: usize) -> Option<Self> {
39        match i {
40            0 => Some(Self::Control),
41            1 => Some(Self::Interactive),
42            2 => Some(Self::Background),
43            _ => None,
44        }
45    }
46}
47
48#[repr(C)]
49#[derive(Clone, Copy, Debug, PartialEq, Eq)]
50pub struct ScheduledWork {
51    pub operation: OperationId,
52    pub scope: u64,
53    pub class: WorkClass,
54    pub cost: u16,
55    pub deadline: u64,
56}
57
58#[derive(Clone, Copy, Debug, PartialEq, Eq)]
59pub enum PollOutcome {
60    Ready(ScheduledWork),
61    Expired(ScheduledWork),
62}
63
64#[derive(Clone, Copy)]
65struct ScopeSlot {
66    occupied: bool,
67    id: u64,
68    class_cursor: u8,
69    deficit: [u32; WorkClass::COUNT],
70    quantum: [u32; WorkClass::COUNT],
71    control: [Option<ScheduledWork>; CONTROL_CAP],
72    interactive: [Option<ScheduledWork>; INTERACTIVE_CAP],
73    background: [Option<ScheduledWork>; BACKGROUND_CAP],
74    control_len: u8,
75    interactive_len: u8,
76    background_len: u8,
77}
78
79pub struct FairScheduler {
80    incarnation: super::incarnation::CanonicalIncarnation,
81    scopes: [ScopeSlot; MAX_SCOPES],
82    cursor: u8,
83}
84
85impl FairScheduler {
86    /// Creates a default `FairScheduler`.
87    pub const fn new() -> Self {
88        Self::with_quanta(1, 1, 1)
89    }
90
91    /// Builder: `quanta`.
92    pub const fn with_quanta(control: u32, interactive: u32, background: u32) -> Self {
93        let blank = ScopeSlot {
94            occupied: false,
95            id: 0,
96            class_cursor: 0,
97            deficit: [0; WorkClass::COUNT],
98            quantum: [control, interactive, background],
99            control: [None; CONTROL_CAP],
100            interactive: [None; INTERACTIVE_CAP],
101            background: [None; BACKGROUND_CAP],
102            control_len: 0,
103            interactive_len: 0,
104            background_len: 0,
105        };
106        Self {
107            incarnation: super::incarnation::CanonicalIncarnation::UNASSIGNED,
108            scopes: [blank; MAX_SCOPES],
109            cursor: 0,
110        }
111    }
112
113    /// Read-only identity check for adapters sharing this canonical queue.
114    /// Caller must retain exclusive access through the subsequent enqueue.
115    pub fn contains_operation(&self, operation: OperationId) -> bool {
116        self.scopes
117            .iter()
118            .filter(|scope| scope.occupied)
119            .any(|scope| {
120                scope
121                    .control
122                    .iter()
123                    .chain(scope.interactive.iter())
124                    .chain(scope.background.iter())
125                    .flatten()
126                    .any(|work| work.operation == operation)
127            })
128    }
129
130    /// Enqueues a task.
131    pub fn enqueue(&mut self, work: ScheduledWork) -> Result<(), QdnfError> {
132        if work.cost == 0 {
133            return Err(QdnfError::Malformed);
134        }
135        let idx = self.find_or_alloc_scope(work.scope)?;
136        let scope = &mut self.scopes[idx];
137        match work.class {
138            WorkClass::Control => push_front_cap(&mut scope.control, &mut scope.control_len, work),
139            WorkClass::Interactive => {
140                push_front_cap(&mut scope.interactive, &mut scope.interactive_len, work)
141            }
142            WorkClass::Background => {
143                push_front_cap(&mut scope.background, &mut scope.background_len, work)
144            }
145        }
146    }
147
148    /// One DRR step: next ready item, or `WouldBlock` if every capped queue is idle.
149    pub fn poll(&mut self, now: u64) -> Result<PollOutcome, QdnfError> {
150        for s in 0..MAX_SCOPES {
151            let idx = (self.cursor as usize + s) % MAX_SCOPES;
152            if !self.scopes[idx].occupied {
153                continue;
154            }
155            let start = self.scopes[idx].class_cursor as usize;
156            for c in 0..WorkClass::COUNT {
157                let class_i = (start + c) % WorkClass::COUNT;
158                if let Some(work) = self.try_take(idx, class_i) {
159                    self.scopes[idx].class_cursor = ((class_i + 1) % WorkClass::COUNT) as u8;
160                    self.cursor = ((idx + 1) % MAX_SCOPES) as u8;
161                    self.release_scope_if_idle(idx);
162                    if work.deadline < now {
163                        return Ok(PollOutcome::Expired(work));
164                    }
165                    return Ok(PollOutcome::Ready(work));
166                }
167            }
168        }
169        Err(QdnfError::WouldBlock)
170    }
171
172    /// `class` length.
173    pub fn class_len(&self, scope: u64, class: WorkClass) -> usize {
174        match self.scope_index(scope) {
175            None => 0,
176            Some(idx) => match class {
177                WorkClass::Control => self.scopes[idx].control_len as usize,
178                WorkClass::Interactive => self.scopes[idx].interactive_len as usize,
179                WorkClass::Background => self.scopes[idx].background_len as usize,
180            },
181        }
182    }
183
184    fn find_or_alloc_scope(&mut self, id: u64) -> Result<usize, QdnfError> {
185        if let Some(idx) = self.scope_index(id) {
186            return Ok(idx);
187        }
188        for (i, slot) in self.scopes.iter_mut().enumerate() {
189            if !slot.occupied {
190                slot.occupied = true;
191                slot.id = id;
192                slot.class_cursor = 0;
193                slot.deficit = [0; WorkClass::COUNT];
194                slot.control_len = 0;
195                slot.interactive_len = 0;
196                slot.background_len = 0;
197                slot.control = [None; CONTROL_CAP];
198                slot.interactive = [None; INTERACTIVE_CAP];
199                slot.background = [None; BACKGROUND_CAP];
200                return Ok(i);
201            }
202        }
203        Err(QdnfError::Capacity)
204    }
205
206    fn scope_index(&self, id: u64) -> Option<usize> {
207        self.scopes.iter().position(|s| s.occupied && s.id == id)
208    }
209
210    fn try_take(&mut self, idx: usize, class_i: usize) -> Option<ScheduledWork> {
211        let scope = &mut self.scopes[idx];
212        let (len, quantum) = match class_i {
213            0 => (scope.control_len, scope.quantum[0]),
214            1 => (scope.interactive_len, scope.quantum[1]),
215            _ => (scope.background_len, scope.quantum[2]),
216        };
217        if len == 0 {
218            scope.deficit[class_i] = 0;
219            return None;
220        }
221        scope.deficit[class_i] = scope.deficit[class_i].saturating_add(quantum);
222        let front = match class_i {
223            0 => scope.control[0],
224            1 => scope.interactive[0],
225            _ => scope.background[0],
226        }?;
227        let cost = front.cost as u32;
228        if cost > scope.deficit[class_i] {
229            return None;
230        }
231        scope.deficit[class_i] -= cost;
232        match class_i {
233            0 => pop_front(&mut scope.control, &mut scope.control_len),
234            1 => pop_front(&mut scope.interactive, &mut scope.interactive_len),
235            _ => pop_front(&mut scope.background, &mut scope.background_len),
236        }
237    }
238
239    fn release_scope_if_idle(&mut self, idx: usize) {
240        let slot = &mut self.scopes[idx];
241        if slot.control_len == 0 && slot.interactive_len == 0 && slot.background_len == 0 {
242            slot.occupied = false;
243            slot.id = 0;
244            slot.class_cursor = 0;
245            slot.deficit = [0; WorkClass::COUNT];
246        }
247    }
248}
249
250impl Default for FairScheduler {
251    fn default() -> Self {
252        Self::new()
253    }
254}
255
256fn push_front_cap<const N: usize>(
257    slots: &mut [Option<ScheduledWork>; N],
258    len: &mut u8,
259    work: ScheduledWork,
260) -> Result<(), QdnfError> {
261    let n = *len as usize;
262    if n >= N {
263        return Err(QdnfError::Capacity);
264    }
265    slots[n] = Some(work);
266    *len = (n + 1) as u8;
267    Ok(())
268}
269
270fn pop_front<const N: usize>(
271    slots: &mut [Option<ScheduledWork>; N],
272    len: &mut u8,
273) -> Option<ScheduledWork> {
274    if *len == 0 {
275        return None;
276    }
277    let item = slots[0].take();
278    let n = *len as usize;
279    for i in 0..n - 1 {
280        slots[i] = slots[i + 1];
281    }
282    *len -= 1;
283    slots[*len as usize] = None;
284    item
285}
286
287#[cfg(test)]
288mod tests {
289    use super::*;
290
291    fn op(n: u8) -> OperationId {
292        let mut id = [0u8; 16];
293        id[0] = n;
294        OperationId(id)
295    }
296
297    fn work(n: u8, class: WorkClass) -> ScheduledWork {
298        ScheduledWork {
299            operation: op(n),
300            scope: 1,
301            class,
302            cost: 1,
303            deadline: u64::MAX,
304        }
305    }
306
307    #[test]
308    fn identity_lookup_covers_classes_and_scopes_without_removing_work() {
309        let mut sched = FairScheduler::new();
310        let a = work(10, WorkClass::Control);
311        let mut b = work(11, WorkClass::Interactive);
312        b.scope = 2;
313        let mut c = work(12, WorkClass::Background);
314        c.scope = 3;
315        for item in [a, b, c] {
316            sched.enqueue(item).unwrap();
317        }
318        for id in [a.operation, b.operation, c.operation] {
319            assert!(sched.contains_operation(id));
320        }
321        assert!(!sched.contains_operation(op(99)));
322        for _ in 0..3 {
323            let PollOutcome::Ready(item) = sched.poll(0).unwrap() else {
324                panic!("unexpected expiry");
325            };
326            assert!(!sched.contains_operation(item.operation));
327        }
328        assert_eq!(sched.poll(0), Err(QdnfError::WouldBlock));
329    }
330
331    #[test]
332    fn control_queue_is_capped() {
333        let mut sched = FairScheduler::new();
334        for i in 0..CONTROL_CAP as u8 {
335            sched.enqueue(work(i, WorkClass::Control)).unwrap();
336        }
337        assert_eq!(
338            sched.enqueue(work(99, WorkClass::Control)),
339            Err(QdnfError::Capacity)
340        );
341    }
342
343    #[test]
344    fn background_not_starved_when_control_is_capped() {
345        let mut sched = FairScheduler::new();
346        for i in 0..CONTROL_CAP as u8 {
347            sched.enqueue(work(i, WorkClass::Control)).unwrap();
348        }
349        assert_eq!(
350            sched.enqueue(work(80, WorkClass::Control)),
351            Err(QdnfError::Capacity)
352        );
353        sched.enqueue(work(40, WorkClass::Background)).unwrap();
354        let mut saw_background = false;
355        let mut remaining_control = CONTROL_CAP;
356        for _ in 0..(CONTROL_CAP + 2) {
357            match sched.poll(0) {
358                Ok(PollOutcome::Ready(w)) if w.class == WorkClass::Background => {
359                    saw_background = true;
360                    break;
361                }
362                Ok(PollOutcome::Ready(w)) if w.class == WorkClass::Control => {
363                    remaining_control -= 1;
364                }
365                other => panic!("unexpected poll {other:?}"),
366            }
367        }
368        assert!(
369            saw_background,
370            "background must run while control still has {remaining_control} queued"
371        );
372        assert!(
373            remaining_control > 0,
374            "fairness requires background before control drains"
375        );
376    }
377
378    #[test]
379    fn ninth_scope_is_capacity() {
380        let mut sched = FairScheduler::new();
381        for s in 0..MAX_SCOPES as u64 {
382            let mut w = work(s as u8, WorkClass::Background);
383            w.scope = s;
384            sched.enqueue(w).unwrap();
385        }
386        let mut extra = work(8, WorkClass::Background);
387        extra.scope = 99;
388        assert_eq!(sched.enqueue(extra), Err(QdnfError::Capacity));
389    }
390
391    #[test]
392    fn expired_deadline_does_not_run() {
393        let mut sched = FairScheduler::new();
394        let mut w = work(1, WorkClass::Interactive);
395        w.deadline = 10;
396        sched.enqueue(w).unwrap();
397        assert_eq!(sched.poll(11), Ok(PollOutcome::Expired(w)));
398    }
399}