Skip to main content

hyprstream_discovery/
scheduling.rs

1//! Scheduling Substrate — the shared vocabulary + small primitives every
2//! scheduling surface composes on (#523 P0 / #524 / #628).
3//!
4//! Five selection systems grew independently (`selection.rs` backend pick,
5//! `SandboxPool::acquire`, `DevicePool`, `CellRouter`/HRW routing,
6//! `queryCandidates`). They share one shape —
7//! `candidates → filter(predicates) → rank → select → explain` — so this module
8//! is the ONE place that shape lives. Each provider declares capability truth
9//! once (as labels + resources via [`CapabilitySource`]); each consumer filters
10//! and ranks through [`filter`] / [`rank`] / [`select`] and gets a trace
11//! ([`SelectionReport`]) for free, because every [`Predicate`] returns *why* it
12//! rejected.
13//!
14//! ## Guardrail (non-negotiable)
15//! This is small on purpose: plain types + free functions. **No trait towers,
16//! no `Scheduler<T>` abstraction-without-consumers.** If it grows past
17//! "vocabulary + small helpers," it is wrong — extend by adding real consumers,
18//! not by abstracting in a vacuum.
19
20use std::cmp::Ordering;
21
22// ─── Vocabulary (mirrors `discovery.capnp` #523 P0) ─────────────────────────
23
24/// A named resource amount (`{name, quantity}`); `quantity` is a k8s-quantity
25/// string e.g. `"8"`, `"512Gi"`, `"100m"`.
26#[derive(Debug, Clone, PartialEq, Eq)]
27pub struct Resource {
28    pub name: String,
29    pub quantity: String,
30}
31
32impl Resource {
33    pub fn new(name: impl Into<String>, quantity: impl Into<String>) -> Self {
34        Self {
35            name: name.into(),
36            quantity: quantity.into(),
37        }
38    }
39}
40
41/// A resource requirement: a candidate must have at least `min_quantity` of
42/// `name` allocatable (declared − already-allocated).
43#[derive(Debug, Clone, PartialEq, Eq)]
44pub struct ResourceRequest {
45    pub name: String,
46    pub min_quantity: String,
47}
48
49impl ResourceRequest {
50    pub fn new(name: impl Into<String>, min_quantity: impl Into<String>) -> Self {
51        Self {
52            name: name.into(),
53            min_quantity: min_quantity.into(),
54        }
55    }
56
57    /// Satisfied iff `available` parses and is `>= min_quantity`. A missing/
58    /// unparseable available value is *not* satisfiable (fail-closed).
59    pub fn satisfied_by(&self, available: &str) -> bool {
60        match (
61            parse_k8s_quantity(available),
62            parse_k8s_quantity(&self.min_quantity),
63        ) {
64            (Some(have), Some(need)) => have >= need,
65            _ => false,
66        }
67    }
68}
69
70/// Label-selector match operator (k8s match-expressions).
71#[derive(Debug, Clone, Copy, PartialEq, Eq)]
72pub enum SelectorOp {
73    In,
74    NotIn,
75    Exists,
76    DoesNotExist,
77    Gt,
78    Lt,
79}
80
81/// One label-selector conjunct: `key <op> values`. A query carries a list of
82/// these (all must match — AND). `values` is ignored for `Exists`/`DoesNotExist`.
83#[derive(Debug, Clone, PartialEq, Eq)]
84pub struct LabelSelector {
85    pub key: String,
86    pub op: SelectorOp,
87    pub values: Vec<String>,
88}
89
90impl LabelSelector {
91    pub fn new(key: impl Into<String>, op: SelectorOp, values: Vec<String>) -> Self {
92        Self {
93            key: key.into(),
94            op,
95            values,
96        }
97    }
98
99    /// Evaluate this selector against a label set `(key, value)`.
100    pub fn matches(&self, labels: &[(String, String)]) -> bool {
101        let entry = labels.iter().find(|(k, _)| k == &self.key);
102        match self.op {
103            SelectorOp::Exists => entry.is_some(),
104            SelectorOp::DoesNotExist => entry.is_none(),
105            SelectorOp::In => entry.is_some_and(|(_, v)| self.values.iter().any(|w| w == v)),
106            SelectorOp::NotIn => entry.is_none_or(|(_, v)| !self.values.iter().any(|w| w == v)),
107            // Gt/Lt compare numerically over the k8s-quantity value (k8s restricts
108            // these to integer resources; we extend to any parseable quantity).
109            SelectorOp::Gt => {
110                self.cmp_numeric(entry.map(|(_, v)| v.as_str()), |o| o == Ordering::Greater)
111            }
112            SelectorOp::Lt => {
113                self.cmp_numeric(entry.map(|(_, v)| v.as_str()), |o| o == Ordering::Less)
114            }
115        }
116    }
117
118    fn cmp_numeric(&self, have: Option<&str>, want: impl Fn(Ordering) -> bool) -> bool {
119        let have = match have.and_then(parse_k8s_quantity) {
120            Some(h) => h,
121            None => return false,
122        };
123        // Gt/Lt compare against `values[0]` (k8s: a single value for these ops).
124        let need = match self.values.first().and_then(|v| parse_k8s_quantity(v)) {
125            Some(n) => n,
126            None => return false,
127        };
128        want(have.cmp(&need))
129    }
130}
131
132/// A placement candidate returned by `queryCandidates`.
133#[derive(Debug, Clone, PartialEq)]
134pub struct PlacementCandidate {
135    pub node: String,
136    pub record_uri: String,
137    pub load_fraction: f32,
138    pub allocatable: Vec<Resource>,
139    pub last_seen: i64,
140}
141
142/// Bounded result set. `total_matching` is the full match count before the
143/// bound was applied.
144#[derive(Debug, Clone)]
145pub struct PlacementCandidateSet {
146    pub candidates: Vec<PlacementCandidate>,
147    pub total_matching: u32,
148}
149
150// ─── k8s-quantity parsing (minimal, for comparison) ────────────────────────
151
152/// Parse a k8s-quantity string into a canonical comparable value (milli of the
153/// base unit, as `i128`). Handles the common suffixes:
154/// - binary: `Ki`/`Mi`/`Gi`/`Ti`/`Pi`/`Ei` (×1024^n)
155/// - decimal: `k`/`M`/`G`/`T`/`P`/`E` (×1000^n)
156/// - `m` (milli, ÷1000)
157/// - plain decimal number
158///
159/// Returns `None` for unparseable input. This is deliberately **minimal** — it
160/// covers the suffixes in real use here; full k8s quantity semantics (sign,
161/// exponents, the binary/decimal distinction k8s preserves) are deferred to the
162/// scheduler engine that actually does capacity math. Comparison only needs the
163/// same input to canonicalize consistently.
164pub fn parse_k8s_quantity(s: &str) -> Option<i128> {
165    let s = s.trim();
166    if s.is_empty() {
167        return None;
168    }
169    // Split trailing non-digit suffix from the numeric prefix. k8s quantities are
170    // `<number><suffix>`; a leading sign is allowed.
171    let split = s
172        .find(|c: char| !(c.is_ascii_digit() || c == '.' || c == '-' || c == '+'))
173        .unwrap_or(s.len());
174    let (num, suffix) = s.split_at(split);
175    let v: f64 = num.parse().ok()?;
176    // Canonicalize to milli of the base unit (i128). One multiplier per suffix.
177    // Sub-unit suffixes (`m`, `u`) divide instead of multiply.
178    let milli: i128 = match suffix {
179        "" => (v * 1_000.0) as i128,
180        "m" => v as i128,                   // already milli
181        "u" | "µ" => (v / 1_000.0) as i128, // micro → milli
182        "k" => (v * 1_000.0 * 1_000.0) as i128,
183        "M" => (v * 1_000_000.0 * 1_000.0) as i128,
184        "G" => (v * 1_000_000_000.0 * 1_000.0) as i128,
185        "T" => (v * 1_000_000_000_000.0 * 1_000.0) as i128,
186        "Ki" => (v * 1_024.0 * 1_000.0) as i128,
187        "Mi" => (v * 1_048_576.0 * 1_000.0) as i128,
188        "Gi" => (v * 1_073_741_824.0 * 1_000.0) as i128,
189        "Ti" => (v * 1_099_511_627_776.0 * 1_000.0) as i128,
190        // P/E and Pi/Ei overflow i128 milli in real magnitudes; fall through to
191        // the catch-all `None` (not in use here).
192        _ => return None,
193    };
194    Some(milli)
195}
196
197// ─── filter → rank → select ────────────────────────────────────────────────
198
199/// Why a predicate rejected a candidate (carried into the explain trace).
200#[derive(Debug, Clone)]
201pub struct RejectionReason(pub String);
202
203/// A predicate over a candidate: returns `None` if it passes, `Some(reason)` if
204/// rejected (and why). Because every predicate returns its reason, a
205/// [`SelectionReport`] trace falls out of [`filter`] / [`select`] for free.
206pub type Predicate<C> = Box<dyn Fn(&C) -> Option<RejectionReason>>;
207
208/// Per-candidate outcome from [`filter`]: the candidate plus its first rejection
209/// (if any). Short-circuits per candidate on the first rejecting predicate.
210#[derive(Debug, Clone)]
211pub struct Outcome<'c, C> {
212    pub candidate: &'c C,
213    pub rejected: Option<RejectionReason>,
214}
215
216impl<'c, C> Outcome<'c, C> {
217    pub fn passed(&self) -> bool {
218        self.rejected.is_none()
219    }
220}
221
222/// Run every candidate through every predicate, recording the first rejection
223/// (if any) per candidate. Predicates are evaluated in order; a candidate
224/// rejected by predicate *i* is not tested against *i+1*.
225#[allow(clippy::needless_lifetimes)] // two input refs; the `'c` ties the borrow unambiguously
226pub fn filter<'c, C>(candidates: &'c [C], predicates: &[Predicate<C>]) -> Vec<Outcome<'c, C>> {
227    candidates
228        .iter()
229        .map(|c| {
230            let rejected = predicates.iter().find_map(|p| p(c));
231            Outcome {
232                candidate: c,
233                rejected,
234            }
235        })
236        .collect()
237}
238
239/// Order survivors by `by`. Stable. Consumes the slice of survivor references
240/// (typically `filter(...).iter().filter(|o| o.passed()).map(|o| o.candidate)`).
241pub fn rank<C>(mut survivors: Vec<&C>, by: impl Fn(&C, &C) -> Ordering) -> Vec<&C> {
242    survivors.sort_by(|a, b| by(a, b));
243    survivors
244}
245
246/// One candidate's verdict in a [`SelectionReport`] (generic — consumer-agnostic;
247/// `selection.rs` adds its own backend-specific fields when it adopts this).
248#[derive(Debug, Clone)]
249pub struct CandidateOutcome<C> {
250    pub candidate: C,
251    pub selected: bool,
252    pub rejection_reason: Option<String>,
253}
254
255/// Full trace of a selection decision: every candidate considered + the winner.
256/// The explain shape (generalized from the backend-selection diagnostics).
257#[derive(Debug, Clone)]
258pub struct SelectionReport<C> {
259    pub requested: String,
260    pub candidates: Vec<CandidateOutcome<C>>,
261    pub selected: Option<usize>, // index into `candidates`
262    pub summary: String,
263}
264
265/// The full pipeline: filter → rank → bounded select, returning both the chosen
266/// candidates and the explain trace. `identify` maps a `&C` to the name used in
267/// the report's per-candidate entries (so the report stays generic over `C`).
268///
269/// `selected` in the report marks every returned (post-bound) candidate.
270pub fn select<C>(
271    candidates: &[C],
272    predicates: &[Predicate<C>],
273    rank_by: impl Fn(&C, &C) -> Ordering,
274    max: usize,
275) -> SelectionReport<C>
276where
277    C: Clone,
278{
279    let outcomes = filter(candidates, predicates);
280    let mut survivors: Vec<&C> = outcomes
281        .iter()
282        .filter(|o| o.passed())
283        .map(|o| o.candidate)
284        .collect();
285    survivors = rank(survivors, rank_by);
286    let bound: Vec<&C> = survivors.into_iter().take(max).collect();
287    let chosen: Vec<&C> = bound.clone();
288    let summary = format!(
289        "{} considered, {} survived filters, {} selected (bound {max})",
290        candidates.len(),
291        outcomes.iter().filter(|o| o.passed()).count(),
292        chosen.len(),
293    );
294    let candidate_reports = candidates
295        .iter()
296        .map(|c| {
297            let is_selected = chosen.iter().any(|s| std::ptr::eq(*s, c));
298            let rejection = outcomes
299                .iter()
300                .find(|o| std::ptr::eq(o.candidate, c))
301                .and_then(|o| o.rejected.as_ref().map(|r| r.0.clone()));
302            CandidateOutcome {
303                candidate: c.clone(),
304                selected: is_selected,
305                rejection_reason: rejection,
306            }
307        })
308        .collect();
309    let selected_idx = bound.first().and_then(|b| {
310        candidates
311            .iter()
312            .position(|c| std::ptr::eq(c as *const _, *b as *const _))
313    });
314    SelectionReport {
315        requested: String::new(),
316        candidates: candidate_reports,
317        selected: selected_idx,
318        summary,
319    }
320}
321
322// ─── Capability-source contract ────────────────────────────────────────────
323
324/// A provider of scheduling capability truth: emits its stable capabilities +
325/// declared capacity in the shared vocabulary so a `PlacementCandidate` / node
326/// record can aggregate them (one source of truth — no hand-declaration, no
327/// drift between e.g. a node record claiming `runtime=kata` and the live
328/// `selection.rs` knowing `cloud-hypervisor` is missing).
329///
330/// Implementors: backend-selection registries, device pools, future NUMA/
331/// topology providers. Aggregators (the node-record publisher) call
332/// [`CapabilitySource::capability_labels`] / [`CapabilitySource::capability_resources`]
333/// and fold the results into the published record.
334pub trait CapabilitySource {
335    /// Stable capability labels — e.g. `("runtime", "kata")`, `("gpu.arch", "hopper")`,
336    /// `("topology.zone", "us-east-1a")`.
337    fn capability_labels(&self) -> Vec<(String, String)>;
338    /// Declared countable capacity — e.g. `Resource("nvidia.com/gpu", "8")`,
339    /// `Resource("memory", "512Gi")`. (Live/allocatable is volatile; the node
340    /// record combines declared capacity with a liveness report.)
341    fn capability_resources(&self) -> Vec<Resource>;
342}
343
344#[cfg(test)]
345mod tests {
346    #![allow(clippy::unwrap_used)]
347    use super::*;
348
349    fn sel(key: &str, op: SelectorOp, values: &[&str]) -> LabelSelector {
350        LabelSelector::new(key, op, values.iter().map(|&s| s.to_owned()).collect())
351    }
352
353    #[test]
354    fn selector_in_not_in() {
355        let labels = vec![("env".into(), "prod".into()), ("gpu".into(), "h100".into())];
356        assert!(sel("env", SelectorOp::In, &["prod", "staging"]).matches(&labels));
357        assert!(!sel("env", SelectorOp::In, &["dev"]).matches(&labels));
358        assert!(sel("env", SelectorOp::NotIn, &["dev"]).matches(&labels));
359        assert!(!sel("env", SelectorOp::NotIn, &["prod"]).matches(&labels));
360    }
361
362    #[test]
363    fn selector_exists_does_not_exist() {
364        let labels = vec![("env".into(), "prod".into())];
365        assert!(sel("env", SelectorOp::Exists, &[]).matches(&labels));
366        assert!(!sel("missing", SelectorOp::Exists, &[]).matches(&labels));
367        assert!(sel("missing", SelectorOp::DoesNotExist, &[]).matches(&labels));
368        assert!(!sel("env", SelectorOp::DoesNotExist, &[]).matches(&labels));
369    }
370
371    #[test]
372    fn selector_gt_lt_numeric() {
373        let labels = vec![("gpu.count".into(), "8".into())];
374        assert!(sel("gpu.count", SelectorOp::Gt, &["4"]).matches(&labels));
375        assert!(!sel("gpu.count", SelectorOp::Gt, &["8"]).matches(&labels));
376        assert!(sel("gpu.count", SelectorOp::Lt, &["16"]).matches(&labels));
377        assert!(!sel("gpu.count", SelectorOp::Lt, &["8"]).matches(&labels));
378        // missing key → not greater/less (fail-closed)
379        assert!(!sel("absent", SelectorOp::Gt, &["1"]).matches(&labels));
380    }
381
382    #[test]
383    fn k8s_quantity_compares_across_suffixes() {
384        assert!(parse_k8s_quantity("8").unwrap() == parse_k8s_quantity("8000m").unwrap());
385        assert!(parse_k8s_quantity("1Gi").unwrap() > parse_k8s_quantity("512Mi").unwrap());
386        assert!(parse_k8s_quantity("2").unwrap() > parse_k8s_quantity("1").unwrap());
387        assert!(parse_k8s_quantity("100m").unwrap() < parse_k8s_quantity("1").unwrap());
388        assert!(parse_k8s_quantity("garbage").is_none());
389        assert!(parse_k8s_quantity("").is_none());
390    }
391
392    #[test]
393    fn resource_request_satisfied() {
394        let req = ResourceRequest::new("memory", "256Gi");
395        assert!(req.satisfied_by("512Gi"));
396        assert!(req.satisfied_by("256Gi"));
397        assert!(!req.satisfied_by("128Gi"));
398        assert!(!req.satisfied_by("garbage")); // fail-closed
399    }
400
401    #[test]
402    fn filter_rank_select_pipeline() {
403        // candidates: (name, priority). predicate: keep priority >= 2.
404        let cands = vec![
405            ("a".to_owned(), 1),
406            ("b".to_owned(), 3),
407            ("c".to_owned(), 2),
408            ("d".to_owned(), 2),
409        ];
410        let preds: Vec<Predicate<(String, i32)>> = vec![Box::new(|c| {
411            if c.1 >= 2 {
412                None
413            } else {
414                Some(RejectionReason("priority < 2".into()))
415            }
416        })];
417        let report = select(
418            &cands,
419            &preds,
420            |a, b| b.1.cmp(&a.1).then(a.0.cmp(&b.0)), // priority desc, name asc
421            2,                                        // bound
422        );
423        // survivors after filter: b(3), c(2), d(2) → ranked b, c, d → bound 2 → [b, c]
424        let selected: Vec<&String> = report
425            .candidates
426            .iter()
427            .filter(|o| o.selected)
428            .map(|o| &o.candidate.0)
429            .collect();
430        assert_eq!(selected, vec![&"b".to_owned(), &"c".to_owned()]);
431        // rejected candidate carries its reason
432        let a = report
433            .candidates
434            .iter()
435            .find(|o| o.candidate.0 == "a")
436            .unwrap();
437        assert_eq!(a.rejection_reason.as_deref(), Some("priority < 2"));
438        assert!(report.summary.contains("4 considered") && report.summary.contains("3 survived"));
439    }
440
441    #[test]
442    fn filter_records_first_rejection_only() {
443        let cands = vec![1, 2, 3];
444        let preds: Vec<Predicate<i32>> = vec![
445            Box::new(|c| {
446                if c % 2 == 0 {
447                    Some(RejectionReason("even".into()))
448                } else {
449                    None
450                }
451            }),
452            Box::new(|c| {
453                if *c == 1 {
454                    Some(RejectionReason("is-one".into()))
455                } else {
456                    None
457                }
458            }),
459        ];
460        let out = filter(&cands, &preds);
461        // 1 rejected by FIRST predicate? no — 1 is odd, passes pred 0, rejected by pred 1 ("is-one")
462        assert_eq!(out[0].rejected.as_ref().unwrap().0, "is-one");
463        // 2 rejected by first predicate ("even"), pred 1 not evaluated
464        assert_eq!(out[1].rejected.as_ref().unwrap().0, "even");
465        // 3 passes both
466        assert!(out[2].passed());
467    }
468
469    #[test]
470    fn capability_source_trait() {
471        struct Gpu;
472        impl CapabilitySource for Gpu {
473            fn capability_labels(&self) -> Vec<(String, String)> {
474                vec![("gpu.arch".into(), "hopper".into())]
475            }
476            fn capability_resources(&self) -> Vec<Resource> {
477                vec![Resource::new("nvidia.com/gpu", "8")]
478            }
479        }
480        let g = Gpu;
481        assert_eq!(
482            g.capability_labels(),
483            vec![("gpu.arch".into(), "hopper".into())]
484        );
485        assert_eq!(g.capability_resources().len(), 1);
486    }
487}