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