use std::collections::VecDeque;
use crate::job::{Capacity, Job, Live, State, Usage, Weights};
pub const BACKFILL_WINDOW_MS: i64 = 60_000;
const PCT: u64 = 90;
const CPU_PCT: u64 = 90;
pub const BUSY_WINDOW_MS: i64 = 20_000;
const LOAD_SOFT: f64 = 2.0;
const LOAD_BUSY_CPU_PCT: u64 = 90;
const LOAD_RISING_CPU_PCT: u64 = 75;
const LOAD_HARD: f64 = 4.0;
pub const RAMP_MS: i64 = 10_000;
pub const RAMP_FULL_MS: i64 = 3_000;
const FULL_HOLD_FRACTION: (u64, u64) = (3, 4);
const RAMP_IDLE_CPU_PCT: u64 = 50;
const RAMP_STEP_MS: i64 = 250;
const CPU_ASK: u64 = 100;
pub const SMOOTH_WINDOW: usize = 3;
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, serde::Serialize, serde::Deserialize)]
#[serde(rename_all = "lowercase")]
pub enum Block {
Cpu,
Mem,
Vram,
Load1,
Load5,
Queue,
Ramp,
}
impl Block {
#[must_use]
pub const fn name(self) -> &'static str {
match self {
Self::Cpu => "cpu",
Self::Mem => "mem",
Self::Vram => "vram",
Self::Load1 => "load1",
Self::Load5 => "load5",
Self::Queue => "queue",
Self::Ramp => "ramp",
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Decision {
Start,
Fail(String),
Wait {
reason: String,
live: bool,
block: Block,
ramp_end_ms: Option<i64>,
},
}
struct Blocked {
reason: String,
live: bool,
block: Block,
ramp_end_ms: Option<i64>,
}
fn blocked(reason: impl Into<String>, live: bool, block: Block) -> Blocked {
Blocked { reason: reason.into(), live, block, ramp_end_ms: None }
}
fn wait(reason: impl Into<String>, block: Block) -> Decision {
Decision::Wait { reason: reason.into(), live: false, block, ramp_end_ms: None }
}
#[derive(Debug, Default)]
pub struct Smoother {
window: VecDeque<Usage>,
}
impl Smoother {
pub fn push(&mut self, sample: Usage) -> Usage {
self.window.push_back(sample);
while self.window.len() > SMOOTH_WINDOW {
self.window.pop_front();
}
let n = u64::try_from(self.window.len().max(1)).unwrap_or(1);
let sum = self.window.iter().fold(Usage::default(), |a, b| Usage { cpu: a.cpu + b.cpu, mem: a.mem + b.mem, vram: a.vram + b.vram });
Usage { cpu: (sum.cpu / n).max(sample.cpu), mem: (sum.mem / n).max(sample.mem), vram: (sum.vram / n).max(sample.vram) }
}
}
#[must_use]
pub fn non_heavy(machine: Usage, heavy_trees: Usage) -> Usage {
machine.saturating_sub(heavy_trees)
}
fn centi(cores: u32) -> u64 {
u64::from(cores) * 100
}
fn ceiling(cap: &Capacity) -> Usage {
Usage { cpu: centi(cap.cpu) * CPU_PCT / 100, mem: cap.mem / 100 * PCT, vram: cap.vram / 100 * PCT }
}
fn request(w: Weights) -> Usage {
Usage { cpu: if w.cpu > 0 { CPU_ASK } else { 0 }, mem: w.mem, vram: w.vram }
}
fn fits(ask: Usage, room: Usage) -> bool {
ask.cpu <= room.cpu && ask.mem <= room.mem && ask.vram <= room.vram
}
#[must_use]
pub fn fits_reservations(req: Weights, running: &[&Job], cap: &Capacity) -> bool {
let used = running.iter().fold(Usage::default(), |a, j| Usage { cpu: 0, mem: a.mem + j.weights.mem, vram: a.vram + j.weights.vram });
let room = ceiling(cap).saturating_sub(used);
fits(Usage { cpu: 0, ..request(req) }, room)
}
#[must_use]
pub fn ramp_hold(peak: u64, machine: u64, elapsed_ms: i64, cpu_pct: u64, vm: bool) -> u64 {
if elapsed_ms >= RAMP_MS {
return 0;
}
if elapsed_ms < RAMP_FULL_MS || vm || peak * FULL_HOLD_FRACTION.1 >= machine * FULL_HOLD_FRACTION.0 {
return peak;
}
if cpu_pct < RAMP_IDLE_CPU_PCT {
return 0;
}
let left = u64::try_from(RAMP_MS - elapsed_ms).unwrap_or(0);
let span = u64::try_from(RAMP_MS - RAMP_FULL_MS).unwrap_or(1);
peak * left / span
}
#[must_use]
pub fn sustained_pct(latest: u64, readings: &[(i64, u64)], now_ms: i64) -> u64 {
let recent: Vec<u64> = readings.iter().filter(|(ts, _)| *ts <= now_ms && now_ms - *ts <= BUSY_WINDOW_MS).map(|(_, pct)| *pct).collect();
let n = u64::try_from(recent.len()).unwrap_or(u64::MAX);
recent.iter().sum::<u64>().checked_div(n).unwrap_or(0).max(latest)
}
#[must_use]
pub fn headroom(running: &[&Job], cap: &Capacity, live: &Live, now_ms: i64) -> Usage {
let (held, unmet) = running.iter().fold((Usage::default(), 0), |(a, unmet), j| {
let l = live.per_job.iter().find(|(id, _)| *id == j.id).map_or_else(Usage::default, |(_, u)| *u);
let hold = j.started_ms.map_or(0, |t| ramp_hold(centi(j.weights.cpu).min(centi(cap.cpu)), centi(cap.cpu), now_ms.saturating_sub(t).max(0), live.cpu_pct, crate::run::hosts_vm_work(&j.cmd)));
let cpu = l.cpu.max(hold);
(Usage { cpu: a.cpu + cpu, mem: a.mem + l.mem.max(j.weights.mem), vram: a.vram + l.vram.max(j.weights.vram) }, unmet + hold.saturating_sub(l.cpu))
});
let instant = live.non_heavy.cpu + held.cpu;
let sustained = live.cpu_sustained_pct * centi(cap.cpu) / 100 + unmet;
let room = ceiling(cap).saturating_sub(live.non_heavy).saturating_sub(held);
Usage { cpu: ceiling(cap).cpu.saturating_sub(instant.max(sustained)), ..room }
}
#[must_use]
pub fn disk_full(req: Weights, cap: &Capacity, live: &Live) -> Option<String> {
let need = u128::from(req.disk) + u128::from(cap.disk_total) / 10;
(u128::from(live.disk_free) < need).then(|| {
format!(
"the disk is full: {} free, need {} (the request plus 10% of the disk). Clean up, or ask Todd",
crate::sizes::fmt_size(live.disk_free),
crate::sizes::fmt_size(u64::try_from(need).unwrap_or(u64::MAX))
)
})
}
const RISING_MARGIN: f64 = 1.1;
#[must_use]
pub fn guard_block(cap: &Capacity, live: &Live) -> Option<(String, Block)> {
let cores = f64::from(cap.cpu);
let (soft, hard) = (LOAD_SOFT * cores, LOAD_HARD * cores);
let cpu = live.cpu_pct.max(live.cpu_sustained_pct);
if live.load1 >= hard {
return Some((format!("1-minute load {:.1} >= {hard:.0} (4 x {} cores)", live.load1, cap.cpu), Block::Load1));
}
if live.load1 >= soft {
if live.load1 > live.load5 * RISING_MARGIN && cpu >= LOAD_RISING_CPU_PCT {
return Some((
format!("1-minute load {:.1} >= {soft:.0} (2 x {} cores) and still rising (5-minute {:.1}), cpu {cpu}% busy", live.load1, cap.cpu, live.load5),
Block::Load1,
));
}
if cpu >= LOAD_BUSY_CPU_PCT {
return Some((format!("1-minute load {:.1} >= {soft:.0} (2 x {} cores) and cpu {cpu}% busy", live.load1, cap.cpu), Block::Load1));
}
}
if live.mem_used_pct >= PCT {
return Some((format!("memory {}% used", live.mem_used_pct), Block::Mem));
}
if live.mem_pressure {
return Some(("the system is under memory pressure".into(), Block::Mem));
}
None
}
fn blocker(w: Weights, running: &[&Job], cap: &Capacity, live: &Live, now_ms: i64) -> Option<Blocked> {
if !running.is_empty() {
if !fits_reservations(w, running, cap) {
let vram = Usage { cpu: 0, mem: 0, vram: w.vram };
let used_vram: u64 = running.iter().map(|j| j.weights.vram).sum();
let block = if fits(vram, ceiling(cap).saturating_sub(Usage { cpu: 0, mem: 0, vram: used_vram })) { Block::Mem } else { Block::Vram };
return Some(blocked("memory reservations full", false, block));
}
let ask = request(w);
if !fits(ask, headroom(running, cap, live, now_ms)) {
if fits(ask, headroom(running, cap, live, i64::MAX)) {
let last = running.iter().filter_map(|j| j.started_ms).map(|t| t + RAMP_MS).filter(|e| *e > now_ms).max();
let end = last.map(|last| {
let floors = running.iter().filter_map(|j| j.started_ms).map(|t| t + RAMP_FULL_MS);
let mut at: Vec<i64> = (1..=(last - now_ms) / RAMP_STEP_MS).map(|k| now_ms + k * RAMP_STEP_MS).chain(floors).filter(|t| *t > now_ms && *t < last).collect();
at.sort_unstable();
at.into_iter().find(|t| fits(ask, headroom(running, cap, live, *t))).unwrap_or(last)
});
return Some(Blocked { reason: "no headroom (jobs admitted a moment ago are still ramping up)".into(), live: true, block: Block::Ramp, ramp_end_ms: end });
}
let room = headroom(running, cap, live, now_ms);
let block = if ask.cpu > room.cpu {
Block::Cpu
} else if ask.mem > room.mem {
Block::Mem
} else {
Block::Vram
};
return Some(blocked("no headroom (other programs and running jobs use the machine)", true, block));
}
}
guard_block(cap, live).map(|(why, block)| blocked(why, true, block))
}
#[must_use]
pub fn evaluate(job: &Job, jobs: &[Job], cap: &Capacity, live: &Live, now_ms: i64) -> Decision {
let running: Vec<&Job> = jobs.iter().filter(|j| j.state == State::Running).collect();
let mut queued: Vec<&Job> = jobs.iter().filter(|j| j.state == State::Queued && (j.id == job.id || !live.stopped.contains(&j.id))).collect();
queued.sort_by(|a, b| (a.enqueued_ms, &a.id).cmp(&(b.enqueued_ms, &b.id)));
if let Some(why) = disk_full(job.weights, cap, live) {
return Decision::Fail(why);
}
if let Some(head) = queued.first().filter(|h| h.id != job.id) {
if blocker(head.weights, &running, cap, live, now_ms).is_none() {
let me = Job { state: State::Running, started_ms: Some(now_ms), ..job.clone() };
let mut with_me = running.clone();
with_me.push(&me);
if blocker(head.weights, &with_me, cap, live, now_ms).is_some() {
return wait("queued behind a job that fits now", Block::Queue);
}
} else {
if now_ms - head.enqueued_ms >= BACKFILL_WINDOW_MS {
return wait(format!("queued behind {} (waited over 60 s)", head.id), Block::Queue);
}
let (a, h) = (job.weights, head.weights);
if a.cpu > h.cpu || a.mem > h.mem || a.vram > h.vram {
return wait("queued behind a smaller-or-equal head", Block::Queue);
}
}
}
match blocker(job.weights, &running, cap, live, now_ms) {
Some(b) => Decision::Wait { reason: b.reason, live: b.live, block: b.block, ramp_end_ms: b.ramp_end_ms },
None => Decision::Start,
}
}
#[cfg(test)]
mod tests {
use super::*;
const G: u64 = 1 << 30;
fn cap() -> Capacity {
Capacity { cpu: 10, mem: 100 * G, vram: 0, disk_total: 1000 * G, vram_is_ram: false }
}
fn calm() -> Live {
Live { load1: 0.5, mem_used_pct: 10, disk_free: 900 * G, ..Live::default() }
}
fn job(id: &str, cpu: u32, mem_g: u64, state: State, enq: i64) -> Job {
Job {
id: id.into(),
pid: 1,
start_time: 0,
weights: Weights { cpu, mem: mem_g * G, vram: 0, disk: 0 },
cmd: vec!["x".into()],
cwd: "/".into(),
state,
enqueued_ms: enq,
started_ms: None,
blocked_by: None,
}
}
fn waits(d: &Decision) -> bool {
matches!(d, Decision::Wait { .. })
}
#[test]
fn alone_always_runs() {
let me = job("a", 10, 100, State::Queued, 0);
let busy = Live { non_heavy: Usage { cpu: 900, mem: 90 * G, vram: 0 }, ..calm() };
assert_eq!(evaluate(&me, std::slice::from_ref(&me), &cap(), &busy, 0), Decision::Start);
}
#[test]
fn ninety_percent_reservation_ceiling() {
let run = job("r", 5, 50, State::Running, 0);
let fits = job("a", 4, 40, State::Queued, 1);
let over = job("b", 5, 41, State::Queued, 1);
assert_eq!(evaluate(&fits, &[run.clone(), fits.clone()], &cap(), &calm(), 2), Decision::Start);
let d = evaluate(&over, &[run, over.clone()], &cap(), &calm(), 2);
assert!(matches!(d, Decision::Wait { live: false, .. }), "{d:?}");
}
#[test]
fn headroom_math_with_fake_non_heavy_usage() {
let run = job("r", 2, 10, State::Running, 0);
let live = Live {
non_heavy: Usage { cpu: 200, mem: 30 * G, vram: 0 },
per_job: vec![("r".into(), Usage { cpu: 300, mem: 20 * G, vram: 0 })],
..calm()
};
let room = headroom(&[&run], &cap(), &live, 100_000);
assert_eq!(room, Usage { cpu: 900 - 200 - 300, mem: 90 * G - 30 * G - 20 * G, vram: 0 });
let edge = job("e", 4, 40, State::Queued, 1);
assert_eq!(evaluate(&edge, &[run.clone(), edge.clone()], &cap(), &live, 2), Decision::Start);
let over = job("o", 5, 41, State::Queued, 1);
let d = evaluate(&over, &[run.clone(), over.clone()], &cap(), &live, 2);
assert!(matches!(d, Decision::Wait { live: true, .. }), "{d:?}");
let idle = Live { per_job: vec![("r".into(), Usage::default())], non_heavy: Usage::default(), ..calm() };
let room = headroom(&[&run], &cap(), &idle, 100_000);
assert_eq!((room.cpu, room.mem), (900, 80 * G));
}
#[test]
fn non_heavy_is_machine_minus_heavy_trees() {
let machine = Usage { cpu: 800, mem: 50 * G, vram: 2 * G };
let trees = Usage { cpu: 600, mem: 20 * G, vram: 5 * G };
assert_eq!(non_heavy(machine, trees), Usage { cpu: 200, mem: 30 * G, vram: 0 });
}
#[test]
fn smoother_is_fast_to_rise_and_slow_to_fall() {
let mut s = Smoother::default();
let low = Usage { cpu: 100, mem: 2 * G, vram: 0 };
let hi = Usage { cpu: 900, mem: 12 * G, vram: 0 };
assert_eq!(s.push(low), low);
assert_eq!(s.push(low), low);
assert_eq!(s.push(hi), hi, "a rise is not averaged away");
assert_eq!(s.push(low), Usage { cpu: 366, mem: 16 * G / 3, vram: 0 }, "a fall is released slowly");
assert_eq!(s.push(low), Usage { cpu: 366, mem: 16 * G / 3, vram: 0 });
for _ in 0..SMOOTH_WINDOW {
s.push(Usage::default());
}
assert_eq!(s.push(Usage::default()), Usage::default(), "old peaks age out");
}
#[test]
fn a_fresh_waiter_sees_a_jump_at_once() {
let mut s = Smoother::default();
let hot = Usage { cpu: 1500, mem: 30 * G, vram: 0 };
assert_eq!(s.push(hot), hot);
}
#[test]
fn many_tiny_jobs_run_together() {
let mut all: Vec<Job> = (0..50).map(|i| job(&format!("r{i:02}"), 0, 0, State::Running, 0)).collect();
let me = job("a", 0, 0, State::Queued, 1);
all.push(me.clone());
assert_eq!(evaluate(&me, &all, &cap(), &calm(), 2), Decision::Start, "no cap on the number of jobs");
}
#[test]
fn guards_veto() {
let me = job("a", 1, 1, State::Queued, 0);
let one = std::slice::from_ref(&me);
let busy = Live { load1: 21.0, load5: 22.0, cpu_pct: 95, ..calm() };
assert!(matches!(evaluate(&me, one, &cap(), &busy, 0), Decision::Wait { live: true, block: Block::Load1, .. }));
let calm_1m = Live { load1: 19.0, load5: 5.0, cpu_pct: 95, ..calm() };
assert_eq!(evaluate(&me, one, &cap(), &calm_1m, 0), Decision::Start, "macOS load reads high: 2 x cores");
let io_bound = Live { load1: 35.0, load5: 36.0, cpu_pct: 40, ..calm() };
assert_eq!(evaluate(&me, one, &cap(), &io_bound, 0), Decision::Start, "high, falling load with a calm CPU is threads waiting on I/O");
let runaway = Live { load1: 40.0, cpu_pct: 10, ..calm() };
assert!(matches!(evaluate(&me, one, &cap(), &runaway, 0), Decision::Wait { block: Block::Load1, .. }), "4 x cores blocks whatever the CPU says");
let mem = Live { mem_used_pct: 95, ..calm() };
assert!(waits(&evaluate(&me, std::slice::from_ref(&me), &cap(), &mem, 0)));
}
#[test]
fn rising_load_blocks_at_two_times_cores_but_falling_load_admits() {
let me = job("a", 1, 1, State::Queued, 0);
let one = std::slice::from_ref(&me);
let rising = Live { load1: 30.0, load5: 22.0, cpu_pct: 80, ..calm() };
let d = evaluate(&me, one, &cap(), &rising, 0);
assert!(matches!(&d, Decision::Wait { block: Block::Load1, live: true, reason, .. } if reason.contains("rising")), "{d:?}");
let rising_io = Live { cpu_pct: 30, ..rising.clone() };
assert_eq!(evaluate(&me, one, &cap(), &rising_io, 0), Decision::Start);
let falling = Live { load1: 30.0, load5: 38.0, cpu_pct: 30, ..calm() };
assert_eq!(evaluate(&me, one, &cap(), &falling, 0), Decision::Start, "falling and CPU under 90%");
let level = Live { load1: 30.0, load5: 30.0, cpu_pct: 30, ..calm() };
assert_eq!(evaluate(&me, one, &cap(), &level, 0), Decision::Start, "load1 <= load5 is not rising");
let jitter = Live { load1: 31.5, load5: 30.0, cpu_pct: 30, ..calm() };
assert_eq!(evaluate(&me, one, &cap(), &jitter, 0), Decision::Start, "load1 = load5 x 1.05 is jitter, not rising");
let falling_busy = Live { cpu_pct: 92, ..falling.clone() };
assert!(waits(&evaluate(&me, one, &cap(), &falling_busy, 0)));
let ramping_up = Live { load1: 15.0, load5: 5.0, cpu_pct: 30, ..calm() };
assert_eq!(evaluate(&me, one, &cap(), &ramping_up, 0), Decision::Start);
let hard = Live { load1: 41.0, load5: 80.0, cpu_pct: 5, ..calm() };
assert!(waits(&evaluate(&me, one, &cap(), &hard, 0)));
}
#[test]
fn memory_pressure_blocks() {
let me = job("a", 1, 1, State::Queued, 0);
let one = std::slice::from_ref(&me);
let pressured = Live { mem_pressure: true, ..calm() };
assert!(matches!(evaluate(&me, one, &cap(), &pressured, 0), Decision::Wait { block: Block::Mem, live: true, .. }));
assert_eq!(evaluate(&me, one, &cap(), &calm(), 0), Decision::Start);
}
#[test]
fn eight_cold_builds_start_one_ramp_apart() {
let c = Capacity { cpu: 16, ..cap() };
let mut jobs: Vec<Job> = (0..8).map(|i| job(&format!("j{i}"), 16, 1, State::Queued, i)).collect();
let mut starts = Vec::new();
let mut t = 100;
while t < 100 + 8 * RAMP_MS && starts.len() < 8 {
for i in 0..jobs.len() {
if jobs[i].state == State::Queued && evaluate(&jobs[i].clone(), &jobs, &c, &calm(), t) == Decision::Start {
jobs[i].state = State::Running;
jobs[i].started_ms = Some(t);
starts.push(t);
}
}
t += 100;
}
assert_eq!(starts.len(), 8);
assert!(starts.windows(2).all(|w| w[1] - w[0] >= RAMP_MS), "one cold build per ramp: {starts:?}");
let busy = Live { cpu_pct: 60, non_heavy: Usage { cpu: 960, mem: 0, vram: 0 }, ..calm() };
let mut jobs: Vec<Job> = (0..3).map(|i| job(&format!("k{i}"), 16, 1, State::Queued, i)).collect();
let mut starts = Vec::new();
let mut t = 100;
while t < 100 + 4 * RAMP_MS && starts.len() < 3 {
for i in 0..jobs.len() {
if jobs[i].state == State::Queued && evaluate(&jobs[i].clone(), &jobs, &c, &busy, t) == Decision::Start {
jobs[i].state = State::Running;
jobs[i].started_ms = Some(t);
starts.push(t);
}
}
t += 100;
}
assert_eq!(starts.len(), 3);
assert!(starts.windows(2).all(|w| w[1] - w[0] >= RAMP_MS), "busy: one cold build per ramp: {starts:?}");
let mut now = jobs.clone();
for j in &mut now {
j.state = State::Queued;
j.started_ms = None;
}
let first = evaluate(&now[0], &now, &c, &calm(), 5000);
assert_eq!(first, Decision::Start);
}
#[test]
fn disk_guard() {
let mut me = job("a", 1, 1, State::Queued, 0);
me.weights.disk = 500 * G;
let low = Live { disk_free: 550 * G, ..calm() };
assert!(matches!(evaluate(&me, std::slice::from_ref(&me), &cap(), &low, 0), Decision::Fail(m) if m.contains("disk is full")));
let ok = Live { disk_free: 600 * G, ..calm() };
assert_eq!(evaluate(&me, std::slice::from_ref(&me), &cap(), &ok, 0), Decision::Start);
}
#[test]
fn fifo_head_blocks_non_fitting_follower() {
let run = job("r", 8, 50, State::Running, 0);
let head = job("h", 5, 30, State::Queued, 1);
let big = job("z", 6, 40, State::Queued, 2);
assert!(waits(&evaluate(&big, &[run, head, big.clone()], &cap(), &calm(), 3)));
}
#[test]
fn backfill_only_while_head_is_young_and_follower_smaller() {
let run = job("r", 8, 70, State::Running, 0);
let head = job("h", 5, 30, State::Queued, 1);
let small = job("s", 1, 5, State::Queued, 2);
let all = [run, head, small.clone()];
assert_eq!(evaluate(&small, &all, &cap(), &calm(), 1000), Decision::Start);
assert!(waits(&evaluate(&small, &all, &cap(), &calm(), BACKFILL_WINDOW_MS + 1)));
}
#[test]
fn follower_starts_when_it_fits_together_with_the_head() {
let head = job("h", 5, 10, State::Queued, 1);
let small = job("s", 1, 5, State::Queued, 2);
let all = [head.clone(), small.clone()];
assert_eq!(evaluate(&small, &all, &cap(), &calm(), 3), Decision::Start);
assert_eq!(evaluate(&head, &all, &cap(), &calm(), 3), Decision::Start);
}
#[test]
fn follower_waits_when_it_would_stop_the_head_fitting() {
let head = job("h", 5, 50, State::Queued, 1);
let other = job("o", 5, 50, State::Queued, 2);
let all = [head.clone(), other.clone()];
assert!(waits(&evaluate(&other, &all, &cap(), &calm(), 3)));
assert_eq!(evaluate(&head, &all, &cap(), &calm(), 3), Decision::Start);
let run = job("r", 3, 30, State::Running, 0);
let follow = job("f", 2, 20, State::Queued, 3);
let all = [run, head.clone(), follow.clone()];
assert!(waits(&evaluate(&follow, &all, &cap(), &calm(), 4)));
}
#[test]
fn a_ramp_blocker_names_the_moment_it_ends() {
let c = Capacity { cpu: 16, ..cap() };
let live = Live { non_heavy: Usage { cpu: 320, mem: 8 * G, vram: 0 }, ..calm() };
let ra = Job { state: State::Running, started_ms: Some(10), ..job("a", 16, 8, State::Running, 0) };
let b = job("b", 16, 8, State::Queued, 2);
let d = evaluate(&b, &[ra.clone(), b.clone()], &c, &live, 500);
assert!(matches!(d, Decision::Wait { block: Block::Ramp, ramp_end_ms: Some(e), live: true, .. } if e == 10 + RAMP_MS), "{d:?}");
let warm = Live { cpu_pct: 60, ..live.clone() };
let d = evaluate(&b, &[ra, b.clone()], &c, &warm, 500);
assert!(matches!(d, Decision::Wait { block: Block::Ramp, ramp_end_ms: Some(e), .. } if e == 10 + RAMP_MS), "{d:?}");
let live = Live { non_heavy: Usage { cpu: 800, mem: 8 * G, vram: 0 }, ..calm() };
let warm = Live { cpu_pct: 60, ..live.clone() };
let rl = Job { state: State::Running, started_ms: Some(10), ..job("l", 8, 8, State::Running, 0) };
let d = evaluate(&b, &[rl.clone(), b.clone()], &c, &live, 500);
assert!(matches!(d, Decision::Wait { block: Block::Ramp, ramp_end_ms: Some(e), .. } if e == 10 + RAMP_FULL_MS), "{d:?}");
let d = evaluate(&b, &[rl.clone(), b.clone()], &c, &warm, 500);
assert!(matches!(d, Decision::Wait { block: Block::Ramp, ramp_end_ms: Some(5500), .. }), "{d:?}");
assert_eq!(evaluate(&b, &[rl, b.clone()], &c, &warm, 5500), Decision::Start);
let busy = Live { non_heavy: Usage { cpu: 1550, mem: 8 * G, vram: 0 }, ..calm() };
let run = Job { state: State::Running, started_ms: Some(0), ..job("r", 1, 8, State::Running, 0) };
let d = evaluate(&b, &[run, b.clone()], &c, &busy, 100_000);
assert!(matches!(d, Decision::Wait { block: Block::Cpu, ramp_end_ms: None, .. }), "{d:?}");
}
#[test]
fn peak_core_waiters_start_on_a_mostly_idle_machine() {
let c = Capacity { cpu: 16, ..cap() };
let live = Live { non_heavy: Usage { cpu: 320, mem: 8 * G, vram: 0 }, ..calm() };
let a = job("a", 16, 8, State::Queued, 1);
let b = job("b", 16, 8, State::Queued, 2);
assert_eq!(evaluate(&a, &[a.clone(), b.clone()], &c, &live, 10), Decision::Start);
let ra = Job { state: State::Running, started_ms: Some(10), ..a };
assert!(waits(&evaluate(&b, &[ra.clone(), b.clone()], &c, &live, 11)), "blocked by a's ramp hold");
assert!(waits(&evaluate(&b, &[ra.clone(), b.clone()], &c, &live, 10 + RAMP_FULL_MS)), "a whole-machine hold is not released early");
assert_eq!(evaluate(&b, &[ra.clone(), b.clone()], &c, &live, 10 + RAMP_MS), Decision::Start, "the second starts once the first one's ramp has ended");
let ca = job("c", 16, 8, State::Queued, 3);
let busy = Live { non_heavy: Usage { cpu: 1550, mem: 8 * G, vram: 0 }, ..calm() };
let run = Job { state: State::Running, started_ms: Some(0), ..job("r", 16, 8, State::Running, 0) };
assert!(waits(&evaluate(&ca, &[run, ca.clone()], &c, &busy, 100_000)));
}
#[test]
fn burst_is_held_back_by_ramp_holds() {
let c = Capacity { cpu: 16, ..cap() };
let mut jobs: Vec<Job> = (0..8).map(|i| job(&format!("j{i}"), 4, 1, State::Queued, i)).collect();
let mut started = 0;
for i in 0..jobs.len() {
let me = jobs[i].clone();
if evaluate(&me, &jobs, &c, &calm(), 100) == Decision::Start {
jobs[i].state = State::Running;
jobs[i].started_ms = Some(100);
started += 1;
}
}
assert_eq!(started, 4, "holds of 400 each leave 240 for the 4th and none for the 5th: not a burst of 8");
let next = jobs.iter().find(|j| j.state == State::Queued).unwrap().clone();
assert_eq!(evaluate(&next, &jobs, &c, &calm(), 100 + RAMP_MS), Decision::Start);
let ramped = Job { state: State::Running, started_ms: Some(0), ..job("r", 16, 1, State::Running, 0) };
let room = headroom(&[&ramped], &c, &calm(), RAMP_MS + 1);
assert_eq!(room.cpu, 1440);
}
#[test]
fn stopped_waiter_file_does_not_block_the_next_waiter() {
let run = job("r", 1, 50, State::Running, 0);
let head = job("h", 1, 30, State::Queued, 1);
let next = job("n", 1, 40, State::Queued, 2);
let t = 3 + BACKFILL_WINDOW_MS;
assert!(waits(&evaluate(&next, &[run.clone(), head.clone(), next.clone()], &cap(), &calm(), t)));
let stopped = Job { state: State::Stopped, ..head };
assert_eq!(evaluate(&next, &[run, stopped, next.clone()], &cap(), &calm(), t), Decision::Start);
}
#[test]
fn stopped_head_does_not_block_the_next_waiter() {
let run = job("r", 1, 50, State::Running, 0);
let head = job("h", 1, 30, State::Queued, 1);
let next = job("n", 1, 40, State::Queued, 2);
let all = [run, head, next.clone()];
assert!(waits(&evaluate(&next, &all, &cap(), &calm(), 3 + BACKFILL_WINDOW_MS)), "a live head blocks the bigger follower");
let live = Live { stopped: vec!["h".into()], ..calm() };
assert_eq!(evaluate(&next, &all, &cap(), &live, 3 + BACKFILL_WINDOW_MS), Decision::Start);
}
fn mac() -> Capacity {
Capacity { cpu: 16, mem: 64 * G, vram: 0, disk_total: 1000 * G, vram_is_ram: true }
}
#[test]
fn a_lagging_five_minute_load_never_blocks_an_idle_machine() {
let me = job("a", 4, 4, State::Queued, 0);
let live = Live { load1: 22.6, load5: 34.2, cpu_pct: 12, mem_used_pct: 46, non_heavy: Usage { cpu: 192, mem: 29 * G, vram: 0 }, ..calm() };
assert_eq!(evaluate(&me, std::slice::from_ref(&me), &mac(), &live, 0), Decision::Start);
let run = Job { started_ms: Some(0), ..job("r", 4, 4, State::Running, 0) };
let live = Live { load1: 21.3, load5: 32.9, cpu_pct: 16, per_job: vec![("r".into(), Usage { cpu: 100, mem: 2 * G, vram: 0 })], non_heavy: Usage { cpu: 156, mem: 24 * G, vram: 0 }, ..live };
assert_eq!(evaluate(&me, &[run, me.clone()], &mac(), &live, 100_000), Decision::Start);
}
#[test]
fn a_small_job_starts_at_seventy_percent_cpu() {
let run = Job { started_ms: Some(0), ..job("r", 8, 4, State::Running, 0) };
let me = job("a", 4, 4, State::Queued, 1);
let live = Live {
load1: 26.0,
load5: 31.0,
cpu_pct: 72,
per_job: vec![("r".into(), Usage { cpu: 800, mem: 4 * G, vram: 0 })],
non_heavy: Usage { cpu: 352, mem: 22 * G, vram: 0 },
..calm()
};
assert_eq!(evaluate(&me, &[run.clone(), me.clone()], &mac(), &live, 100_000), Decision::Start);
let full = Live { per_job: vec![("r".into(), Usage { cpu: 1100, mem: 4 * G, vram: 0 })], non_heavy: Usage { cpu: 420, mem: 22 * G, vram: 0 }, cpu_pct: 95, ..live };
assert!(matches!(evaluate(&me, &[run, me.clone()], &mac(), &full, 100_000), Decision::Wait { block: Block::Cpu, .. }));
}
#[test]
fn ramp_hold_is_released_while_measured_cpu_is_low() {
let run = Job { started_ms: Some(0), ..job("r", 8, 4, State::Running, 0) };
let me = job("a", 16, 4, State::Queued, 1);
let all = [run.clone(), me.clone()];
let live = Live {
load1: 29.4,
load5: 23.7,
cpu_pct: 20,
mem_used_pct: 38,
per_job: vec![("r".into(), Usage { cpu: 150, mem: 2 * G, vram: 0 })],
non_heavy: Usage { cpu: 800, mem: 22 * G, vram: 0 },
..calm()
};
let d = evaluate(&me, &all, &mac(), &live, 1_000);
assert!(matches!(d, Decision::Wait { block: Block::Ramp, ramp_end_ms: Some(RAMP_FULL_MS), .. }), "{d:?}");
assert_eq!(evaluate(&me, &all, &mac(), &live, 4_000), Decision::Start);
assert_eq!(evaluate(&me, &all, &mac(), &live, RAMP_FULL_MS), Decision::Start);
let cold = Job { started_ms: Some(0), ..job("r", 16, 4, State::Running, 0) };
let all_cold = [cold, me.clone()];
let d = evaluate(&me, &all_cold, &mac(), &live, 4_000);
assert!(matches!(d, Decision::Wait { block: Block::Ramp, ramp_end_ms: Some(RAMP_MS), .. }), "{d:?}");
assert!(waits(&evaluate(&me, &all_cold, &mac(), &live, RAMP_MS - 1)));
assert_eq!(evaluate(&me, &all_cold, &mac(), &live, RAMP_MS), Decision::Start);
let mut all: Vec<Job> = (0..3).map(|i| Job { started_ms: Some(0), ..job(&format!("d{i}"), 4, 2, State::Running, 0) }).collect();
all.push(Job { started_ms: Some(95_000), ..job("new", 8, 2, State::Running, 1) });
all.push(me.clone());
let live = Live {
load1: 15.5,
load5: 14.3,
cpu_pct: 24,
mem_used_pct: 46,
per_job: vec![
("d0".into(), Usage { cpu: 80, mem: G, vram: 0 }),
("d1".into(), Usage { cpu: 60, mem: G, vram: 0 }),
("d2".into(), Usage { cpu: 40, mem: G, vram: 0 }),
("new".into(), Usage { cpu: 50, mem: G, vram: 0 }),
],
non_heavy: Usage { cpu: 150, mem: 25 * G, vram: 0 },
..calm()
};
assert_eq!(evaluate(&me, &all, &mac(), &live, 100_000), Decision::Start);
let busy = Live { cpu_pct: 70, non_heavy: Usage { cpu: 1180 - 230, mem: 25 * G, vram: 0 }, ..live };
assert!(matches!(evaluate(&me, &all, &mac(), &busy, 100_000), Decision::Wait { block: Block::Ramp, .. }));
}
#[test]
fn big_learned_peaks_and_docker_keep_the_full_hold() {
let c = Capacity { cpu: 16, ..cap() };
let idle = Live { non_heavy: Usage { cpu: 100, mem: 8 * G, vram: 0 }, ..calm() };
let b = job("b", 15, 8, State::Queued, 2);
let ra = Job { state: State::Running, started_ms: Some(10), ..job("a", 15, 8, State::Running, 0) };
assert!(waits(&evaluate(&b, &[ra.clone(), b.clone()], &c, &idle, 10 + RAMP_FULL_MS)), "no early release at 94%");
assert!(waits(&evaluate(&b, &[ra.clone(), b.clone()], &c, &idle, 10 + RAMP_MS - 1)));
assert_eq!(evaluate(&b, &[ra, b.clone()], &c, &idle, 10 + RAMP_MS), Decision::Start);
let busy_other = Live { non_heavy: Usage { cpu: 800, mem: 8 * G, vram: 0 }, ..calm() };
let rh = Job { state: State::Running, started_ms: Some(10), ..job("h", 8, 8, State::Running, 0) };
assert!(waits(&evaluate(&b, &[rh.clone(), b.clone()], &c, &busy_other, 11)));
assert_eq!(evaluate(&b, &[rh, b.clone()], &c, &busy_other, 10 + RAMP_FULL_MS), Decision::Start);
let rd = Job { state: State::Running, started_ms: Some(10), cmd: vec!["docker".into(), "build".into()], ..job("d", 8, 8, State::Running, 0) };
assert!(waits(&evaluate(&b, &[rd.clone(), b.clone()], &c, &busy_other, 10 + RAMP_FULL_MS)));
assert_eq!(evaluate(&b, &[rd, b.clone()], &c, &busy_other, 10 + RAMP_MS), Decision::Start);
assert_eq!(ramp_hold(1200, 1600, RAMP_FULL_MS, 0, false), 1200);
assert_eq!(ramp_hold(1100, 1600, RAMP_FULL_MS, 0, false), 0);
assert_eq!(ramp_hold(800, 1600, RAMP_FULL_MS, 0, true), 800);
}
#[test]
fn ramp_hold_schedule() {
let (peak, machine) = (800, 1600);
assert_eq!(ramp_hold(peak, machine, 0, 0, false), peak, "full at admission");
assert_eq!(ramp_hold(peak, machine, RAMP_FULL_MS - 1, 0, false), peak, "full through the floor, however idle");
assert_eq!(ramp_hold(peak, machine, RAMP_FULL_MS, 49, false), 0, "released on an idle machine");
assert_eq!(ramp_hold(peak, machine, RAMP_FULL_MS, 50, false), peak, "shrinks from the full peak on a busy one");
assert_eq!(ramp_hold(peak, machine, 6_500, 80, false), 400, "halfway down at the middle of the shrink");
assert_eq!(ramp_hold(peak, machine, RAMP_MS, 100, false), 0, "gone when the ramp ends");
assert_eq!(ramp_hold(machine, machine, RAMP_FULL_MS, 0, false), machine);
assert_eq!(ramp_hold(machine, machine, RAMP_MS - 1, 0, false), machine);
assert_eq!(ramp_hold(machine, machine, RAMP_MS, 0, false), 0);
}
#[test]
fn rising_load_with_idle_cpu_is_io_wait_not_overload() {
let me = job("a", 4, 4, State::Queued, 0);
let one = std::slice::from_ref(&me);
for (load1, load5, cpu_pct) in [(57.85, 24.18, 26), (53.44, 24.32, 28), (46.16, 25.83, 16)] {
let live = Live { load1, load5, cpu_pct, mem_used_pct: 36, non_heavy: Usage { cpu: cpu_pct * 16, mem: 23 * G, vram: 0 }, ..calm() };
assert_eq!(evaluate(&me, one, &mac(), &live, 0), Decision::Start, "load1 {load1} cpu {cpu_pct}%");
let busy = Live { cpu_pct: 80, ..live.clone() };
assert!(matches!(evaluate(&me, one, &mac(), &busy, 0), Decision::Wait { block: Block::Load1, .. }), "load1 {load1} busy");
}
let hard = Live { load1: 64.0, load5: 24.0, cpu_pct: 16, ..calm() };
assert!(matches!(evaluate(&me, one, &mac(), &hard, 0), Decision::Wait { block: Block::Load1, .. }));
let pressured = Live { load1: 50.0, load5: 24.0, cpu_pct: 16, mem_pressure: true, ..calm() };
assert!(matches!(evaluate(&me, one, &mac(), &pressured, 0), Decision::Wait { block: Block::Mem, .. }));
}
#[test]
fn a_saturated_machine_still_blocks() {
let me = job("a", 4, 4, State::Queued, 0);
let live = Live { load1: 55.3, load5: 39.6, cpu_pct: 100, ..calm() };
assert!(matches!(evaluate(&me, std::slice::from_ref(&me), &mac(), &live, 0), Decision::Wait { block: Block::Load1, .. }));
let storm = Live { load1: 120.0, cpu_pct: 5, ..calm() };
assert!(matches!(evaluate(&me, std::slice::from_ref(&me), &mac(), &storm, 0), Decision::Wait { block: Block::Load1, .. }));
}
#[test]
fn clamp_to_machine_and_fold_vram() {
let c = cap();
let w = c.clamp(Weights { cpu: 64, mem: 999 * G, vram: 5 * G, disk: 9999 * G });
assert_eq!(w, Weights { cpu: 10, mem: 100 * G, vram: 0, disk: 1000 * G });
let mac = Capacity { vram_is_ram: true, ..c };
assert_eq!(mac.clamp(Weights { cpu: 1, mem: 4 * G, vram: 2 * G, disk: 0 }).mem, 6 * G);
}
fn pinned(jobs: u64, non_heavy: u64) -> (Vec<Job>, Live) {
let a = Job { started_ms: Some(0), ..job("a", 8, 2, State::Running, 0) };
let b = Job { started_ms: Some(0), ..job("b", 8, 2, State::Running, 0) };
let live = Live {
cpu_pct: (jobs + non_heavy) / 16,
per_job: vec![("a".into(), Usage { cpu: jobs / 2, mem: 2 * G, vram: 0 }), ("b".into(), Usage { cpu: jobs / 2, mem: 2 * G, vram: 0 })],
non_heavy: Usage { cpu: non_heavy, mem: 20 * G, vram: 0 },
..calm()
};
(vec![a, b], live)
}
#[test]
fn a_dip_between_build_steps_does_not_admit_onto_a_pinned_machine() {
let (mut jobs, dip) = pinned(1_100, 180);
let me = job("c", 4, 2, State::Queued, 50_000);
jobs.push(me.clone());
assert_eq!(dip.cpu_pct, 80);
let readings = [(40_000, 100), (45_000, 100), (52_000, 98), (60_000, 80)];
let live = Live { cpu_sustained_pct: sustained_pct(dip.cpu_pct, &readings, 60_000), ..dip.clone() };
assert_eq!(live.cpu_sustained_pct, 94);
let d = evaluate(&me, &jobs, &mac(), &live, 60_000);
assert!(matches!(d, Decision::Wait { block: Block::Cpu, ramp_end_ms: None, .. }), "{d:?}");
let settled = [(45_000, 81), (52_000, 79), (60_000, 80)];
let live = Live { cpu_sustained_pct: sustained_pct(80, &settled, 60_000), ..dip };
assert_eq!(evaluate(&me, &jobs, &mac(), &live, 60_000), Decision::Start);
}
#[test]
fn jobs_start_up_to_the_band_and_wait_inside_it() {
let me = job("c", 4, 2, State::Queued, 1);
for (busy, starts) in [(60, true), (75, true), (83, true), (84, false), (88, false), (100, false)] {
let (mut jobs, live) = pinned(busy * 16 - 160, 160);
jobs.push(me.clone());
let live = Live { cpu_sustained_pct: busy, ..live };
assert_eq!(evaluate(&me, &jobs, &mac(), &live, 100_000) == Decision::Start, starts, "{busy}% busy");
}
}
#[test]
fn sustained_cpu_rises_at_once_and_falls_slowly() {
assert_eq!(sustained_pct(70, &[], 0), 70, "no readings: the latest");
assert_eq!(sustained_pct(10, &[(0, 10), (90_000, 100)], 5_000), 10, "a reading from the future (clock skew) is dropped");
assert_eq!(sustained_pct(100, &[(0, 40), (5_000, 40)], 5_000), 100, "a rise counts at once");
assert_eq!(sustained_pct(40, &[(0, 100), (10_000, 100), (20_000, 40)], 20_000), 80, "a fall is averaged");
assert_eq!(sustained_pct(40, &[(0, 100), (25_000, 40)], 25_000), 40, "readings over 20 s old are dropped");
}
#[test]
fn a_rising_load_in_the_underused_zone_admits() {
let me = job("c", 4, 2, State::Queued, 1);
let (mut jobs, live) = pinned(1_000, 120);
jobs.push(me.clone());
let rising = Live { load1: 40.0, load5: 30.0, cpu_sustained_pct: 70, ..live };
assert_eq!(rising.cpu_pct, 70);
assert_eq!(evaluate(&me, &jobs, &mac(), &rising, 100_000), Decision::Start);
let busy = Live { cpu_sustained_pct: 80, ..rising };
assert!(matches!(evaluate(&me, &jobs, &mac(), &busy, 100_000), Decision::Wait { block: Block::Load1, .. }));
}
#[test]
fn thread_inflated_memory_reservations_starve_an_idle_rig() {
let rig = Capacity { cpu: 32, mem: 64 * G, vram: 0, disk_total: 1000 * G, vram_is_ram: false };
let live = Live { cpu_pct: 21, cpu_sustained_pct: 21, mem_used_pct: 6, ..calm() };
let me = job("w", 4, 3, State::Queued, 1);
let inflated = |id: &str| Job { started_ms: Some(0), ..job(id, 32, 46, State::Running, 0) };
let d = evaluate(&me, &[inflated("r"), inflated("s"), me.clone()], &rig, &live, 100_000);
assert!(matches!(d, Decision::Wait { block: Block::Mem, .. }), "{d:?}");
let real = |id: &str| Job { started_ms: Some(0), ..job(id, 4, 3, State::Running, 0) };
assert_eq!(evaluate(&me, &[real("r"), real("s"), me.clone()], &rig, &live, 100_000), Decision::Start);
}
}