qualia_core_db/net/peer/runtime/
scheduler.rs1use 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 pub const fn index(self) -> usize {
33 self as usize
34 }
35
36 #[inline]
37 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 pub const fn new() -> Self {
88 Self::with_quanta(1, 1, 1)
89 }
90
91 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 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 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 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 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}