Skip to main content

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}