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`, 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}