runnerd_core/scheduler/priority.rs
1//! Which one pool goes first once memory or CPU keeps running out before its next job's runner fits (ADR 0096): how
2//! long each pool's next job waited, whether a barrier has served the pool (ADR 0098), what an empty slice would hold,
3//! the rule that picks a plan's one barrier, and which younger jobs may start behind it all the same (`Backfill`, ADR
4//! 0097). `plan` and `admission::simulate` both decide by it, so a replay shows what the daemon does. It does no I/O
5//! and reads no clock; the engine keeps the waits (`waits`), and it never stops or clamps what already runs.
6
7use std::time::{Duration, SystemTime};
8
9use super::waits::Waits;
10use super::{Left, signed};
11use crate::api::Waiting;
12
13/// Once a pool's next job has waited this long for memory or CPU, no younger job starts until its runner fits: smaller
14/// jobs would otherwise take everything that frees up, and the room a large one needs would never gather. Long enough
15/// that a passing shortage puts up no barrier, whose cost is what stands idle behind it (ADR 0098).
16pub const PRIORITY_AFTER: Duration = Duration::from_secs(600);
17
18/// `PRIORITY_AFTER` for a pool a barrier has served, until its queue empties: its wait restarts with each job, so with
19/// the first limit a pool of many large jobs could run them only one at a time (ADR 0098).
20pub const SERVED_PRIORITY_AFTER: Duration = Duration::from_secs(120);
21
22/// What a job's runner lacks that a running job gives back.
23#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
24pub enum Scarce {
25 /// The slice's memory budget, or what the host's memory leaves it.
26 Memory,
27 /// The CPU budget.
28 Cpu,
29}
30
31/// What the budgets would leave once every runner ended, the mirror, seed containers and shells still there; `None`,
32/// no such bound known. A job holds younger ones only for room that draining can give it.
33#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
34pub struct Drained {
35 /// The slice's memory.
36 pub memory: Option<i64>,
37 /// The CPU budget, in millicores.
38 pub cpu: Option<i64>,
39 /// What the host's memory leaves the slice for a job the host holds: by the larger margin while a runner runs,
40 /// whichever margin is in force (ADR 0102).
41 pub host: Option<i64>,
42 /// What it leaves for a job something else holds, by the plain margin: such a job's wait does not follow the margin,
43 /// so its barrier need not keep off it.
44 pub host_plain: Option<i64>,
45}
46
47impl Drained {
48 /// Whether a runner of `memory` and `cpu`, of a job `held` so, fits, every known bound counted.
49 fn holds(self, memory: u64, cpu: u64, held: Held) -> bool {
50 let fits = |room: Option<i64>, needs: u64| {
51 room.is_none_or(|room| room >= i64::try_from(needs).unwrap_or(i64::MAX))
52 };
53 let host = match held {
54 Held::ByHost => self.host,
55 Held::ByBudget => self.host_plain,
56 };
57 fits(self.memory, memory) && fits(host, memory) && fits(self.cpu, cpu)
58 }
59}
60
61/// What holds a job back, which says by which margin a drain serves it.
62#[derive(Debug, Clone, Copy, PartialEq, Eq)]
63pub enum Held {
64 /// What the host's memory leaves the slice.
65 ByHost,
66 /// The slice's memory budget, its high-water mark or the CPU budget.
67 ByBudget,
68}
69
70/// A job a plan held for something scarce, with a free slot for its runner.
71#[derive(Debug, Clone, Copy, PartialEq, Eq)]
72pub struct Short {
73 /// Its ID.
74 pub job: u64,
75 /// What it lacks first: memory before CPU, as `Waiting` says it.
76 pub scarce: Scarce,
77 /// Whether the host holds it.
78 pub held: Held,
79 /// What its runner takes of the memory budget.
80 pub memory: u64,
81 /// What its runner takes of the CPU budget, in millicores.
82 pub cpu: u64,
83}
84
85/// The one job a plan lets no younger job start before, whichever of memory and CPU it lacks: it drains towards both.
86#[derive(Debug, Clone, Copy, PartialEq, Eq)]
87pub struct Barrier {
88 /// The job's ID.
89 pub job: u64,
90 /// What it lacks now.
91 pub scarce: Scarce,
92 /// What its runner takes of the memory budget.
93 pub memory: u64,
94 /// What its runner takes of the CPU budget, in millicores.
95 pub cpu: u64,
96 /// When its wait reached its limit: from then on, what starts counts against the room it is owed.
97 pub since: SystemTime,
98}
99
100impl Barrier {
101 /// The barrier `short`, whose pool `waits`, puts up: the first of a plan's jobs that waited long enough and that
102 /// `drained` has room for. `None` from a demand draining could not serve, as a runner past the budget or a host
103 /// short because of programs outside the slice: younger jobs that fit go on. `drained` is `None` while a safety
104 /// interlock starts nothing, whose zeros say nothing of the room there is: the wait keeps its age meanwhile.
105 pub fn of(
106 short: Short,
107 waits: &Waits,
108 drained: Option<Drained>,
109 now: SystemTime,
110 ) -> Option<Barrier> {
111 let drained = drained?;
112 let since = waits.matured(short.job, now)?;
113 let holds = drained.holds(short.memory, short.cpu, short.held);
114 holds.then_some(Barrier {
115 job: short.job,
116 scarce: short.scarce,
117 memory: short.memory,
118 cpu: short.cpu,
119 since,
120 })
121 }
122
123 /// Why a younger job waits behind it.
124 pub fn reason(self) -> Waiting {
125 match self.scarce {
126 Scarce::Memory => Waiting::BehindMemory { job: self.job },
127 Scarce::Cpu => Waiting::BehindCpu { job: self.job },
128 }
129 }
130}
131
132/// What a runner may take at most: its profile's caps.
133#[derive(Debug, Clone, Copy, PartialEq, Eq)]
134pub(crate) struct Caps {
135 /// Memory.
136 pub(crate) memory: u64,
137 /// CPU, in millicores.
138 pub(crate) cpu: u64,
139}
140
141/// A runner as a backfill reads it, one in a slot or one the plan already started.
142#[derive(Debug, Clone, Copy)]
143pub(crate) struct Runner<'plan> {
144 /// Its profile.
145 pub(crate) profile: &'plan str,
146 /// When it started.
147 pub(crate) started_at: SystemTime,
148 /// How long its job usually keeps it; `None`, it ends now as far as a backfill knows: it runs no job yet, or one
149 /// with no estimate. That only makes the room come sooner, and less starts behind the barrier.
150 pub(crate) usual: Option<Duration>,
151 /// What it takes of the memory budget now.
152 pub(crate) memory: u64,
153 /// What it takes of the CPU budget now, in millicores.
154 pub(crate) cpu: u64,
155 /// What it could take.
156 pub(crate) caps: Caps,
157 /// Whether it started behind a barrier (ADR 0131): a warm runner, one started for a job older than the owner and
158 /// one a restart adopted did not.
159 pub(crate) passed: bool,
160}
161
162impl Runner<'_> {
163 /// How long from `now` it usually ends: at once if that time has passed, or if it started in the future, as after
164 /// a clock went back: the room coming sooner is the side that starts less behind a barrier.
165 fn left_to_run(&self, now: SystemTime) -> Duration {
166 let Ok(ran) = now.duration_since(self.started_at) else {
167 return Duration::ZERO;
168 };
169 self.usual
170 .map_or(Duration::ZERO, |usual| usual.saturating_sub(ran))
171 }
172}
173
174/// A job older than a barrier's owner that the plan left waiting. It goes before the owner, so room it loses to a
175/// younger job comes back to the owner late.
176#[derive(Debug, Clone, Copy)]
177pub(crate) struct Older<'plan> {
178 /// Its pool's profile.
179 pub(crate) profile: &'plan str,
180 /// Whether that profile has a free slot, or will have one with no runner ending, as when it is preparing.
181 pub(crate) free_slot: bool,
182 /// What its runner takes of the memory budget.
183 pub(crate) memory: u64,
184 /// What its runner takes of the CPU budget, in millicores.
185 pub(crate) cpu: u64,
186}
187
188/// What a plan knows when a barrier goes up.
189#[derive(Debug, Clone, Copy)]
190pub(crate) struct Around<'plan> {
191 /// The budgets left.
192 pub(crate) left: Left,
193 /// How much more memory the pooled count could leave with no runner ending (`Budget::credit_room`).
194 pub(crate) credit_room: u64,
195 /// How much more the host's limit could leave with no runner ending (`Budget::host_credit_room`).
196 pub(crate) host_credit_room: u64,
197 /// What a drain leaves.
198 pub(crate) drained: Drained,
199 /// The runners in slots, and those the plan started so far.
200 pub(crate) runners: &'plan [Runner<'plan>],
201 /// The jobs older than the owner it left waiting.
202 pub(crate) older: &'plan [Older<'plan>],
203}
204
205/// A younger job a plan would start, had it no barrier to wait behind.
206#[derive(Debug, Clone, Copy)]
207pub(crate) struct Candidate<'plan> {
208 /// Its pool's profile.
209 pub(crate) profile: &'plan str,
210 /// How many of that profile's slots are free.
211 pub(crate) free_slots: usize,
212 /// The largest usual run time of its pool's queued jobs, since GitHub may give the runner any of them; `None` if
213 /// any has no estimate (`admission::Predictor::longest_usual`).
214 pub(crate) usual: Option<Duration>,
215 /// Its profile's caps.
216 pub(crate) caps: Caps,
217}
218
219/// The room behind a barrier, as ADRs 0097 and 0131 bound it. If each run takes what the plan read, everything started
220/// here has ended before the owner or any job older than it could start, so nothing they see changes and an owner that
221/// keeps the barrier starts no later than with no backfill. The plan reads p95s, so a run that ends early can bring the
222/// room while a job started here still runs, and that job can cost the owner what it has left. Whatever the run times
223/// do, what passed a barrier since this one matured cannot take, even at its caps, what an empty slice has for the owner
224/// and the older jobs, nor the last free slot of its profile, so the owner fits once the older jobs and what ran before
225/// have ended.
226#[derive(Debug, Clone, Copy)]
227pub(crate) struct Backfill<'plan> {
228 /// The owner's profile.
229 profile: &'plan str,
230 /// How long from now until the running runners' usual ends let the owner or an older job start.
231 until: Duration,
232 /// What a drain leaves past the owner and the caps of what passed a barrier since this one matured.
233 spare: Left,
234}
235
236/// The runners by how long each usually has left, soonest first.
237struct Ending<'plan>(Vec<(Duration, Runner<'plan>)>);
238
239impl Ending<'_> {
240 /// How long until their ends let a runner of `memory` and `cpu` fit `left`; `None` if none does.
241 fn room_in(&self, left: Left, memory: u64, cpu: u64) -> Option<Duration> {
242 if left.fits(memory, cpu) {
243 return Some(Duration::ZERO);
244 }
245 let mut room = left;
246 self.0.iter().find_map(|(left_to_run, runner)| {
247 room.give(runner.memory, runner.cpu);
248 room.fits(memory, cpu).then_some(*left_to_run)
249 })
250 }
251
252 /// How long until `older` could start, the budgets being `left`; `None` if no end lets it. Older jobs beside it may
253 /// well take that room first, so it may start later, never sooner.
254 fn start_of(&self, older: &Older<'_>, left: Left) -> Option<Duration> {
255 let room = self.room_in(left, older.memory, older.cpu)?;
256 let in_profile = |(_, runner): &&(Duration, Runner<'_>)| runner.profile == older.profile;
257 let slot = if older.free_slot {
258 Duration::ZERO
259 } else {
260 self.0.iter().find(in_profile)?.0
261 };
262 Some(room.max(slot))
263 }
264}
265
266impl<'plan> Backfill<'plan> {
267 /// What the `barrier` of a job of `profile` leaves room for, as things stand `around` it. `None` where nothing may
268 /// start behind it: the owner's room comes now, or no end of a running runner brings it, as when something other
269 /// than runners holds it.
270 pub(crate) fn behind(
271 barrier: Barrier,
272 profile: &'plan str,
273 around: Around<'_>,
274 now: SystemTime,
275 ) -> Option<Backfill<'plan>> {
276 let Around {
277 left,
278 credit_room,
279 host_credit_room,
280 drained,
281 runners,
282 older,
283 } = around;
284 // The room may come sooner than ends bring it: either credit can grow at any moment, and an end gives back at
285 // most what its runner counts. So the time found is the earliest the owner could start. A runner this plan
286 // started has no job yet, so it counts as ending now and gives back its whole take at once: what it may later
287 // add to the host's credit is its headroom, never more than that take, so `host_credit_room` need not count it.
288 let mut left = left;
289 left.memory = left
290 .memory
291 .map(|memory| memory.saturating_add(signed(credit_room)));
292 left.host = left
293 .host
294 .map(|host| host.saturating_add(signed(host_credit_room)));
295 let mut ending: Vec<(Duration, Runner<'_>)> = runners
296 .iter()
297 .map(|runner| (runner.left_to_run(now), *runner))
298 .collect();
299 ending.sort_by_key(|(left_to_run, _)| *left_to_run);
300 let ending = Ending(ending);
301 let owner = ending.room_in(left, barrier.memory, barrier.cpu)?;
302 let starts = older.iter().filter_map(|job| ending.start_of(job, left));
303 let until = starts.fold(owner, Duration::min);
304 if until.is_zero() {
305 return None;
306 }
307 let mut spare = Left {
308 memory: drained.memory,
309 cpu: drained.cpu,
310 host: drained.host,
311 };
312 // An older job that matures takes the barrier, so its room is kept as the owner's is. One no drain serves never
313 // will, and must not stop everything behind the barrier.
314 let served = older.iter().filter(|job| spare.fits(job.memory, job.cpu));
315 let memory = served.clone().map(|job| job.memory).max().unwrap_or(0);
316 let cpu = served.map(|job| job.cpu).max().unwrap_or(0);
317 spare.take(barrier.memory.max(memory), barrier.cpu.max(cpu));
318 // A runner started for an older job, or before T0, is one the owner waits out under a strict barrier too. One
319 // that passed counts at its caps, as it may hang and grow to them, whether or not GitHub gave it a job: an idle
320 // one holds its room until `IDLE_TIMEOUT`.
321 for runner in runners
322 .iter()
323 .filter(|runner| runner.passed && runner.started_at >= barrier.since)
324 {
325 spare.take(runner.caps.memory, runner.caps.cpu);
326 }
327 Some(Backfill {
328 profile,
329 until,
330 spare,
331 })
332 }
333
334 /// Whether `candidate`, which fits the budgets left and has a free slot, may start behind the barrier; if so, counts
335 /// its caps. It need not move the time found: a runner that usually ends by then gives back what it took.
336 pub(crate) fn admits(&mut self, candidate: Candidate<'_>) -> bool {
337 let caps = candidate.caps;
338 let admitted = candidate.usual.is_some_and(|usual| usual <= self.until)
339 && self.spare.fits(caps.memory, caps.cpu)
340 && (candidate.profile != self.profile || candidate.free_slots > 1);
341 if admitted {
342 self.spare.take(caps.memory, caps.cpu);
343 }
344 admitted
345 }
346}