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