Skip to main content

runnerd_core/
scheduler.rs

1//! Which runners to start and stop, as a pure function of queued jobs, slots, warm runners and the memory and CPU
2//! budgets (`plan`), how many warm runners each repository wants (`warm`), and the loop that applies those decisions
3//! with GitHub and Docker (`engine`). `plan` and `warm` do no I/O and read no clock.
4
5use std::collections::{BTreeMap, BTreeSet};
6use std::time::{Duration, SystemTime};
7
8use crate::admission::Key;
9use crate::api::Waiting;
10use crate::github::QueuedJob;
11
12pub mod engine;
13pub mod priority;
14pub mod warm;
15
16use priority::{Around, Backfill, Candidate, Caps, Held, Older, Runner};
17pub use priority::{Barrier, Drained, PRIORITY_AFTER, SERVED_PRIORITY_AFTER, Scarce, Wait, Waits};
18
19/// How long a started runner may wait for a job before it counts as surplus: covers the container's start and
20/// GitHub's assignment.
21pub const IDLE_TIMEOUT: Duration = Duration::from_secs(300);
22
23/// A repository's runners held back after they failed.
24#[derive(Debug, Clone, Copy)]
25pub struct Hold {
26    /// No runner starts for it before then.
27    pub until: SystemTime,
28    /// What failed.
29    pub cause: crate::api::HoldCause,
30}
31
32/// Names one of a repository's pools: its runners in one profile (ADR 0058). No two pools of a repository share a
33/// profile.
34#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
35pub struct Pool {
36    /// `owner/name` on GitHub.
37    pub repository: String,
38    /// The profile its runners start in.
39    pub profile: String,
40}
41
42impl From<&crate::config::Repository> for Pool {
43    fn from(repository: &crate::config::Repository) -> Pool {
44        Pool {
45            repository: repository.name.clone(),
46            profile: repository.profile.clone(),
47        }
48    }
49}
50
51/// One of a repository's pools as the planner sees it: its runners in one profile, registered with one set of labels
52/// (ADR 0058). A repository with one `[[repositories]]` entry has one.
53#[derive(Debug, Clone)]
54pub struct Repository {
55    /// `owner/name` on GitHub.
56    pub name: String,
57    /// The profile the jobs its labels match run in.
58    pub profile: String,
59    /// The labels its runners register with.
60    pub labels: Vec<String>,
61    /// Paused repositories get no new runners; their running jobs finish.
62    pub paused: bool,
63    /// No runner starts for this repository before then, after its runners failed.
64    pub held: Option<Hold>,
65    /// The repository's queued jobs at the last poll, those of its other pools too.
66    pub queued: Vec<QueuedJob>,
67    /// What a new runner of it takes of the budget: `None`, its profile's `memory`. Under measured admission, the
68    /// largest predicted peak of the queued jobs its labels match, since GitHub may give the runner any of them.
69    pub runner_memory: Option<u64>,
70    /// What a new runner of it takes of the CPU budget, in millicores: `None`, its profile's `cpus`. Under measured
71    /// admission, the largest predicted average CPU of its queued jobs.
72    pub runner_cpu: Option<u64>,
73    /// What its next job has waited for, and since when (ADR 0096), and whether a barrier has served it (ADR 0098).
74    pub waits: Waits,
75    /// The largest usual run time among the queued jobs its labels match, since GitHub may give a runner any of them;
76    /// `None` if any has no estimate, and then none of its jobs starts behind a barrier (ADR 0097).
77    pub usual: Option<Duration>,
78    /// How many idle runners it keeps beyond its queued jobs, for jobs not queued yet (`warm::target`).
79    pub warm: usize,
80}
81
82impl Repository {
83    /// Its name as a pool.
84    pub fn pool(&self) -> Pool {
85        Pool {
86            repository: self.name.clone(),
87            profile: self.profile.clone(),
88        }
89    }
90}
91
92/// A profile's slots: one concurrent job each.
93#[derive(Debug, Clone)]
94pub struct Profile {
95    /// Memory a slot's container may use.
96    pub memory: u64,
97    /// CPU a slot's container may use, in millicores; under a CPU budget, at most the budget, as a runner at its caps
98    /// reserves it.
99    pub cpus: u64,
100    /// While the profile's snapshot is rebuilt or its image pulled, none of its slots starts.
101    pub preparing: Option<Preparing>,
102    /// Upkeep waits for its runners, all idle: its reseed (slot 1 ran a job since the last), or the shared caches'
103    /// check, which waits for every profile's. Its warm runners stop, and none starts, so the upkeep can run.
104    pub upkeep_due: bool,
105    /// Its configured `slots`. A reload that lowered them leaves runners past them, whose slots close once they end.
106    pub count: usize,
107    /// Index 0 is slot 1.
108    pub slots: Vec<Slot>,
109    /// The job each slot ran last, which left its caches in the slot's layer (ADR 0080), by slot index; `None`, or
110    /// no entry, where none is known.
111    pub ran: Vec<Option<Key>>,
112}
113
114/// Why none of a profile's slots starts for now.
115#[derive(Debug, Clone, Copy, PartialEq, Eq)]
116pub enum Preparing {
117    /// Slot 1's layers become the profile's snapshot.
118    Reseeding,
119    /// Its image is being pulled.
120    PullingImage,
121}
122
123/// What a slot holds.
124#[derive(Debug, Clone, PartialEq, Eq)]
125pub enum Slot {
126    /// Nothing: a runner may start here.
127    Free,
128    /// A runner, waiting for its job or running it.
129    Runner(RunnerSlot),
130    /// Free, but over the profile's number of slots, which a reload lowered while its runners ran: nothing starts
131    /// here.
132    Closed,
133}
134
135/// A slot whose container runs a runner registered for one job.
136#[derive(Debug, Clone, PartialEq, Eq)]
137pub struct RunnerSlot {
138    /// `owner/name` the runner is registered on.
139    pub repository: String,
140    /// Whether GitHub reports the runner running a job.
141    pub busy: bool,
142    /// When its container started.
143    pub started_at: SystemTime,
144    /// What it takes of the memory budget, which it gives back if it stops.
145    pub memory: u64,
146    /// What it takes of the CPU budget, in millicores.
147    pub cpu: u64,
148    /// How long its job usually keeps it from `started_at`, once that job and its runs are known (ADR 0097).
149    pub usual: Option<Duration>,
150}
151
152/// Where slots are, by profile name and slot index (0 is slot 1).
153#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
154pub struct SlotRef {
155    /// The profile's name.
156    pub profile: String,
157    /// 0 is slot 1.
158    pub index: usize,
159}
160
161/// What `plan` decides for one slot.
162#[derive(Debug, Clone, PartialEq, Eq)]
163pub enum Decision {
164    /// Register a runner for the repository and start it in the slot.
165    Start {
166        /// The free slot.
167        slot: SlotRef,
168        /// `owner/name` the runner registers on.
169        repository: String,
170        /// What it takes of the budget.
171        memory: u64,
172        /// What it takes of the CPU budget, in millicores.
173        cpu: u64,
174        /// Whether it starts for no queued job, as a warm runner.
175        warm: bool,
176        /// The warm runners this plan stops to make room for it, just before: if one is still there, it took a job
177        /// meanwhile and the start waits for the next plan.
178        replacing: Vec<SlotRef>,
179        /// The barrier's owner, for a start behind a barrier (ADR 0097).
180        behind: Option<u64>,
181    },
182    /// Remove the slot's idle runner, for `reason`.
183    Stop {
184        /// The slot whose runner stops.
185        slot: SlotRef,
186        /// Why it stops.
187        reason: StopReason,
188    },
189}
190
191/// A pool's next job that lacks something scarce, as the plan found it: past the jobs its idle runners take, and
192/// those the plan starts a runner for.
193#[derive(Debug, Clone, PartialEq, Eq)]
194pub struct Demand {
195    /// The pool.
196    pub pool: Pool,
197    /// The job's ID.
198    pub job: u64,
199    /// What it lacks.
200    pub scarce: Scarce,
201}
202
203/// Why an idle runner is removed: what its removal log line and the history say (ADR 0092).
204#[derive(Debug, Clone, Copy, PartialEq, Eq)]
205pub enum StopReason {
206    /// It waited `IDLE_TIMEOUT`, and neither a queued job nor its repository's warm runners want it.
207    Expired,
208    /// A queued job of another pool takes its room.
209    Room,
210    /// Its profile's reseed or the shared caches' check waits for its slot.
211    Upkeep,
212    /// Its repository is paused.
213    Paused,
214    /// Its slot is past a lowered slot count.
215    Closed,
216    /// A reload changed its pool or profile, or a newer image or container spec replaces it.
217    Changed,
218    /// It was raised for a heavier queued job and no longer fits the budget.
219    OverBudget,
220    /// A cache clean needs the volumes it mounts.
221    Clean,
222    /// runnerd stops.
223    Shutdown,
224}
225
226impl StopReason {
227    /// How the history stores it.
228    pub fn as_str(self) -> &'static str {
229        match self {
230            StopReason::Expired => "expired",
231            StopReason::Room => "room",
232            StopReason::Upkeep => "upkeep",
233            StopReason::Paused => "paused",
234            StopReason::Closed => "closed",
235            StopReason::Changed => "changed",
236            StopReason::OverBudget => "over_budget",
237            StopReason::Clean => "clean",
238            StopReason::Shutdown => "shutdown",
239        }
240    }
241
242    /// Why, as the removal's log line says it.
243    pub fn words(self) -> &'static str {
244        match self {
245            StopReason::Expired => "no job came for it",
246            StopReason::Room => "a queued job takes its room",
247            StopReason::Upkeep => "its profile's upkeep waits for it",
248            StopReason::Paused => "its repository is paused",
249            StopReason::Closed => "its slot closed",
250            StopReason::Changed => "the config or runnerd changed its runners",
251            StopReason::OverBudget => "raised for a heavier job, it does not fit the budget",
252            StopReason::Clean => "a cache clean needs its volumes",
253            StopReason::Shutdown => "runnerd stops",
254        }
255    }
256}
257
258/// What `plan` decides, and why each queued job it starts no runner for waits.
259#[derive(Debug, Clone, Default, PartialEq, Eq)]
260pub struct Plan {
261    /// What to start and stop.
262    pub decisions: Vec<Decision>,
263    /// Why each queued job of a repository's matching jobs waits, by job ID. A job an idle runner will take is
264    /// `Waiting::RunnerStarting`; a job this plan starts a runner for has no reason, as that runner does not exist
265    /// until the start succeeds.
266    pub waiting: BTreeMap<u64, Waiting>,
267    /// The idle runners kept warm: no queued job of their repository waits for them.
268    pub warm: BTreeSet<SlotRef>,
269    /// The queued jobs one more slot of their profile would start now: none of its slots is free or a warm runner's
270    /// to give, while the memory and CPU budgets, less what the older of these jobs would take, have room for their
271    /// runners. Whatever `waiting` calls it, `NoSlot` or `BehindStart`; a job that also lacks memory or CPU is not
272    /// one (ADR 0090), nor is one a barrier holds, which another slot would not start.
273    pub slot_waiting: BTreeSet<u64>,
274    /// The pools' next jobs a slot had room for and memory or CPU not: one per pool and resource. What a wait starts
275    /// from, once a scheduling path commits the plan (ADR 0096).
276    pub held: Vec<Demand>,
277    /// The job no younger job starts before, if one waited long enough.
278    pub barrier: Option<Barrier>,
279}
280
281/// The budgets a plan starts runners within.
282#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
283pub struct Budget {
284    /// The memory left, negative by what the running containers take past `MemoryMax` (`left`); `None` for no
285    /// budget.
286    pub memory: Option<i64>,
287    /// The CPU left, in millicores, negative by what the runners reserve past the budget (`left`); `None` for no
288    /// budget.
289    pub cpu: Option<i64>,
290    /// The memory the host has to spare for new runners beside other programs (ADR 0055), negative by what the
291    /// running ones reserve past the host's limit; `None` when not known.
292    pub host: Option<i64>,
293    /// Nothing starts, so no warm runner stops to make room: measured admission holds the slice at its high-water
294    /// mark, or the host's tasks stall for memory. `memory` and `host` are then 0 whatever the room, so no job's wait
295    /// starts and none puts up a barrier. Not a reservation for a starved job (ADR 0096).
296    pub held: bool,
297    /// What the budgets would leave with no runner: what a job may hold younger ones for.
298    pub drained: Drained,
299    /// How much more the pooled count could take off what runs with no runner ending (ADR 0099): room that may come at
300    /// any moment, which a backfill must not outlast. 0 with pooling off.
301    pub credit_room: u64,
302}
303
304/// The workflow labels of GitHub-hosted runners, from
305/// <https://github.com/github/docs/blob/main/data/reusables/actions/supported-github-runners.md> and its single-CPU
306/// row (`single-cpu-table-row.md`), and the larger macOS runners of
307/// <https://github.com/github/docs/blob/main/data/reusables/actions/larger-runners-table.md>, as of 2026-10-16. Update it when GitHub adds or retires an image: a label
308/// missing here makes its jobs wait with `Waiting::NoPool`, whose wording stays true for them.
309const GITHUB_HOSTED: &[&str] = &[
310    "ubuntu-slim",
311    "ubuntu-latest",
312    "ubuntu-26.04",
313    "ubuntu-24.04",
314    "ubuntu-22.04",
315    "ubuntu-26.04-arm",
316    "ubuntu-24.04-arm",
317    "ubuntu-22.04-arm",
318    "windows-latest",
319    "windows-2025",
320    "windows-2025-vs2026",
321    "windows-2022",
322    "windows-11-arm",
323    "windows-11-vs2026-arm",
324    "macos-latest",
325    "macos-26",
326    "macos-15",
327    "macos-14",
328    "macos-26-intel",
329    "macos-15-intel",
330    "xcode-27",
331    "macos-latest-large",
332    "macos-26-large",
333    "macos-15-large",
334    "macos-14-large",
335    "macos-latest-xlarge",
336    "macos-26-xlarge",
337    "macos-15-xlarge",
338    "macos-14-xlarge",
339    "xcode-27-xlarge",
340];
341
342/// Whether GitHub runs a job on its own runners: it asks for exactly one label, one of `GITHUB_HOSTED`. No pool of
343/// this daemon is meant for it. A typo, a custom label and an image name beside `self-hosted` are the owner's to
344/// fix, so they wait for a pool instead.
345fn hosted_by_github(job: &QueuedJob) -> bool {
346    matches!(&job.labels[..], [label] if GITHUB_HOSTED.iter().any(|hosted| hosted.eq_ignore_ascii_case(label)))
347}
348
349/// Whether a job may run on a repository's runners: every label it asks for is one of theirs. GitHub compares
350/// labels without regard to case.
351pub fn matches(job: &QueuedJob, labels: &[String]) -> bool {
352    crate::config::labels_match(&job.labels, labels)
353}
354
355/// Decides which slots start a runner and which idle runners stop, and why each job left queued waits.
356///
357/// `repositories` holds each repository's pools; a job is served by the pool whose labels match it, and one no pool
358/// of its repository matches waits for a pool (`Waiting::NoPool`) unless it is for GitHub's own runners. Each pool
359/// gets a runner per matching queued job, less its runners still waiting for a job. Jobs are
360/// served oldest first across repositories, each in a free slot of its repository's profile (`free_slot`: the one
361/// that ran the same job last, else one that ran its repository, else the lowest), while what the runner takes (`Repository::runner_memory`, by default the slot's memory) fits `budget.memory` and
362/// `budget.host`, and its CPU
363/// (`Repository::runner_cpu`, by default the slot's `cpus`) fits `budget.cpu` (`None`: no budget). A job that does
364/// not fit takes the room of warm runners of other repositories, which stop. A pool whose job had a slot but not
365/// memory or CPU is held once for each (`Plan::held`). An idle runner stops once no queued job is left for it,
366/// it is not one of its repository's `warm` runners, and it waited `IDLE_TIMEOUT`. The first such job that waited
367/// long enough, and that draining the running jobs would make room for, puts up the plan's one barrier
368/// (`priority::Barrier`): no younger job starts until a runner of its pool does, unless it fits and `Backfill` says it
369/// costs the owner neither of ADR 0097's bounds. Last, while no job waits for room, each repository short of its `warm`
370/// runners starts them at its profile's caps, one per repository at a time.
371pub fn plan(
372    repositories: &[Repository],
373    profiles: &BTreeMap<String, Profile>,
374    budget: Budget,
375    now: SystemTime,
376) -> Plan {
377    let mut decided = Plan::default();
378    unserved(repositories, &mut decided);
379    let ToServe {
380        mut wanted,
381        jobs,
382        warm: warm_wanted,
383    } = to_serve(repositories, profiles, now, &mut decided);
384
385    let mut warm = Warm::new(&decided.warm, profiles, budget.held);
386    let mut taken = taken_slots(profiles);
387    let mut left = Left {
388        memory: budget.memory,
389        cpu: budget.cpu,
390        host: budget.host,
391    };
392    let mut started = Started::new(&taken, left);
393    let mut slot_bound = SlotBound::default();
394    // Under a safety interlock, what is left says nothing of the room there is.
395    let drained = (!budget.held).then_some(budget.drained);
396    let mut behind = Behind::new(profiles);
397    for (position, &(job, repository)) in jobs.iter().enumerate() {
398        let Some(missing) = wanted.get_mut(&pool_key(repository)) else {
399            continue;
400        };
401        if *missing == 0 {
402            continue;
403        }
404        let (Some(profile), Some(taken)) = (
405            profiles.get(&repository.profile),
406            taken.get_mut(repository.profile.as_str()),
407        ) else {
408            continue;
409        };
410        let memory = repository.runner_memory.unwrap_or(profile.memory);
411        let cpu = repository.runner_cpu.unwrap_or(profile.cpus);
412        let free_index = free_slot(taken, profile, repository, job, &jobs[position + 1..]);
413        let fits = free_index.is_some() && left.fits(memory, cpu);
414        let turn = Turn {
415            repository,
416            profile,
417            job,
418            memory,
419            cpu,
420            free_slot: free_index.is_some(),
421            left,
422            started: &started,
423        };
424        if let Some(barrier) = decided.barrier {
425            let candidate = Candidate {
426                profile: &repository.profile,
427                free_slots: taken.iter().filter(|taken| !**taken).count(),
428                usual: repository.usual,
429                caps: profile.caps(),
430            };
431            if !fits || !behind.admits(candidate) {
432                turn.behind(barrier, &mut decided);
433                continue;
434            }
435        }
436        let room = if fits || profile.preparing.is_some() {
437            None
438        } else {
439            warm.make_room(repository, free_index.is_none(), left, memory, cpu)
440        };
441        let index = match (room.as_ref(), free_index) {
442            (Some(room), free) => free.or(room.slot).unwrap_or_default(),
443            (None, Some(index)) if fits => index,
444            (None, _) => {
445                turn.waits(drained, &mut slot_bound, now, &mut decided);
446                let job = Older {
447                    profile: &repository.profile,
448                    free_slot: free_index.is_some() || profile.preparing.is_some(),
449                    memory,
450                    cpu,
451                };
452                behind.left_waiting(job, decided.barrier, left, &budget, now);
453                continue;
454            }
455        };
456        let replacing = room.map_or_else(Vec::new, |room| stop_for(room, &mut left, &mut decided));
457        taken[index] = true;
458        *missing -= 1;
459        started.note(&repository.profile, job);
460        left.take(memory, cpu);
461        behind.started(&repository.profile, profile.caps(), memory, cpu, now);
462        decided.decisions.push(start(
463            repository,
464            index,
465            memory,
466            cpu,
467            replacing,
468            decided.barrier,
469        ));
470    }
471    if !budget.held {
472        start_warm(&warm_wanted, profiles, &mut taken, left, &mut decided);
473    }
474    decided
475}
476
477/// Stops the warm runners whose `room` a start takes, before it: they give back what they took.
478fn stop_for(room: Room, left: &mut Left, decided: &mut Plan) -> Vec<SlotRef> {
479    left.give(room.memory, room.cpu);
480    for slot in &room.stopped {
481        decided.warm.remove(slot);
482        decided.decisions.push(Decision::Stop {
483            slot: slot.clone(),
484            reason: StopReason::Room,
485        });
486    }
487    room.stopped
488}
489
490/// What a plan gathers for what may start behind its barrier.
491struct Behind<'plan> {
492    /// The runners in slots, and those started so far.
493    runners: Vec<Runner<'plan>>,
494    /// The jobs left waiting before any barrier went up.
495    older: Vec<Older<'plan>>,
496    /// The room behind the barrier, once one stands and has any.
497    backfill: Option<Backfill<'plan>>,
498}
499
500impl<'plan> Behind<'plan> {
501    /// The runners in `profiles`' slots: what one that waits for a job will run is not known.
502    fn new(profiles: &'plan BTreeMap<String, Profile>) -> Behind<'plan> {
503        let mut runners = Vec::new();
504        for (name, profile) in profiles {
505            for slot in &profile.slots {
506                if let Slot::Runner(runner) = slot {
507                    runners.push(Runner {
508                        profile: name,
509                        started_at: runner.started_at,
510                        usual: runner.usual.filter(|_| runner.busy),
511                        memory: runner.memory,
512                        cpu: runner.cpu,
513                        caps: profile.caps(),
514                    });
515                }
516            }
517        }
518        Behind {
519            runners,
520            older: Vec::new(),
521            backfill: None,
522        }
523    }
524
525    /// Notes `job`, which did not start: it put up `barrier`, or goes before any barrier to come.
526    fn left_waiting(
527        &mut self,
528        job: Older<'plan>,
529        barrier: Option<Barrier>,
530        left: Left,
531        budget: &Budget,
532        now: SystemTime,
533    ) {
534        let Some(barrier) = barrier else {
535            self.older.push(job);
536            return;
537        };
538        let around = Around {
539            left,
540            credit_room: budget.credit_room,
541            drained: budget.drained,
542            runners: &self.runners,
543            older: &self.older,
544        };
545        self.backfill = Backfill::behind(barrier, job.profile, around, now);
546    }
547
548    /// Whether `candidate` may start behind the barrier, counting it if so.
549    fn admits(&mut self, candidate: Candidate<'_>) -> bool {
550        let backfill = self.backfill.as_mut();
551        backfill.is_some_and(|backfill| backfill.admits(candidate))
552    }
553
554    /// Notes a runner started now. It has no job yet: GitHub may give it a shorter one than its pool's longest, so its
555    /// room may come sooner than that says.
556    fn started(&mut self, profile: &'plan str, caps: Caps, memory: u64, cpu: u64, now: SystemTime) {
557        self.runners.push(Runner {
558            profile,
559            started_at: now,
560            usual: None,
561            memory,
562            cpu,
563            caps,
564        });
565    }
566}
567
568/// What `sort_out` leaves the plan to serve.
569struct ToServe<'plan> {
570    /// How many runners each pool wants for its jobs, by `pool_key`.
571    wanted: BTreeMap<(&'plan str, &'plan str), usize>,
572    /// Their jobs, oldest first, each with its pool.
573    jobs: Vec<(u64, &'plan Repository)>,
574    /// How many warm runners each pool is short of.
575    warm: Vec<(&'plan Repository, usize)>,
576}
577
578/// Sorts out each of `repositories` (`sort_out`) into what the plan serves.
579fn to_serve<'plan>(
580    repositories: &'plan [Repository],
581    profiles: &BTreeMap<String, Profile>,
582    now: SystemTime,
583    decided: &mut Plan,
584) -> ToServe<'plan> {
585    let mut serve = ToServe {
586        wanted: BTreeMap::new(),
587        jobs: Vec::new(),
588        warm: Vec::new(),
589    };
590    for repository in repositories {
591        if let Some(sorted) = sort_out(repository, profiles, now, decided) {
592            serve
593                .wanted
594                .insert(pool_key(repository), sorted.serve.len());
595            serve
596                .jobs
597                .extend(sorted.serve.into_iter().map(|job| (job, repository)));
598            serve.warm.push((repository, sorted.warm));
599        }
600    }
601    serve.jobs.sort_by_key(|(id, _)| *id);
602    serve
603}
604
605/// What the jobs a plan has waiting only for a slot would take of the budgets, oldest first
606/// (`Plan::slot_waiting`).
607#[derive(Debug, Default)]
608struct SlotBound {
609    memory: u64,
610    cpu: u64,
611}
612
613impl SlotBound {
614    /// Whether a runner of `memory` and `cpu` fits what is `left` beside the older ones it holds, and if so takes it.
615    fn takes(&mut self, left: Left, memory: u64, cpu: u64) -> bool {
616        let mut spare = left;
617        spare.take(self.memory, self.cpu);
618        let fits = spare.fits(memory, cpu);
619        if fits {
620            self.memory = self.memory.saturating_add(memory);
621            self.cpu = self.cpu.saturating_add(cpu);
622        }
623        fits
624    }
625}
626
627/// The free slot the queued job `job` of `repository` starts in: the one that ran the same job last (repository,
628/// workflow and name), else one that ran a job of the same repository, else the lowest. Warm caches are the slot's
629/// own layer (ADR 0007), so the same job there finds them. Only free slots count: a start never waits for the one it
630/// would prefer. Short of an exact match, a slot that a younger job of the `later` ones in the profile matches
631/// exactly is left to it while another is free.
632fn free_slot(
633    taken: &[bool],
634    profile: &Profile,
635    repository: &Repository,
636    job: u64,
637    later: &[(u64, &Repository)],
638) -> Option<usize> {
639    let ran = |index: usize| profile.ran.get(index).and_then(Option::as_ref);
640    let ran_it = |index: usize, repository: &Repository, job: u64| {
641        let queued = repository.queued.iter().find(|queued| queued.id == job);
642        queued.zip(ran(index)).is_some_and(|(queued, key)| {
643            key.repository == repository.name
644                && key.workflow == queued.workflow
645                && key.name == queued.name
646        })
647    };
648    taken
649        .iter()
650        .enumerate()
651        .filter(|(_, taken)| !**taken)
652        .map(|(index, _)| index)
653        .min_by_key(|&index| {
654            let wanted_later = later.iter().any(|&(id, other)| {
655                other.profile == repository.profile && ran_it(index, other, id)
656            });
657            let same_repository = ran(index).is_some_and(|key| key.repository == repository.name);
658            (
659                !ran_it(index, repository, job),
660                wanted_later,
661                !same_repository,
662                index,
663            )
664        })
665}
666
667/// Holds `job` of `repository`'s pool for `scarce`, unless the plan already held an older job of the pool for it.
668fn hold(repository: &Repository, job: u64, scarce: Scarce, decided: &mut Plan) {
669    let pool = repository.pool();
670    let held = decided
671        .held
672        .iter()
673        .any(|demand| demand.pool == pool && demand.scarce == scarce);
674    if !held {
675        decided.held.push(Demand { pool, job, scarce });
676    }
677}
678
679/// A queued job as `plan`'s loop reaches it, if no runner starts for it.
680struct Turn<'plan> {
681    repository: &'plan Repository,
682    profile: &'plan Profile,
683    job: u64,
684    memory: u64,
685    /// Millicores.
686    cpu: u64,
687    free_slot: bool,
688    left: Left,
689    started: &'plan Started<'plan>,
690}
691
692impl Turn<'_> {
693    /// Why the job waits, and what it lacks.
694    fn why(&self) -> (Waiting, Short) {
695        why_waits(
696            &self.repository.profile,
697            self.profile,
698            self.free_slot,
699            self.memory,
700            self.cpu,
701            self.left,
702            self.started,
703        )
704    }
705
706    /// Says why the job waits with no barrier up. Lacking memory or CPU it is held, unless a safety interlock left no
707    /// `drained` bounds, and it puts up the barrier if it may.
708    fn waits(
709        self,
710        drained: Option<Drained>,
711        slot_bound: &mut SlotBound,
712        now: SystemTime,
713        decided: &mut Plan,
714    ) {
715        let (reason, short) = self.why();
716        decided.waiting.insert(self.job, reason);
717        if !self.free_slot
718            && self.profile.preparing.is_none()
719            && slot_bound.takes(self.left, self.memory, self.cpu)
720        {
721            decided.slot_waiting.insert(self.job);
722        }
723        let Some(scarce) = short.scarce() else {
724            return;
725        };
726        if drained.is_some() {
727            hold(self.repository, self.job, scarce, decided);
728        }
729        decided.barrier = Barrier::of(
730            priority::Short {
731                job: self.job,
732                scarce,
733                held: short.held(),
734                memory: self.memory,
735                cpu: self.cpu,
736            },
737            &self.repository.waits,
738            drained,
739            now,
740        );
741    }
742
743    /// Says why the job waits behind `barrier`. A job with no slot keeps saying so, as the barrier is not what holds
744    /// it, but counts for no more slots: another one would not start it. One that lacks memory or CPU itself is held
745    /// all the same and ages behind the barrier, which it does not share: it may go next.
746    fn behind(self, barrier: Barrier, decided: &mut Plan) {
747        if self.free_slot && self.left.fits(self.memory, self.cpu) {
748            decided.waiting.insert(self.job, barrier.reason());
749            return;
750        }
751        let (reason, short) = self.why();
752        let reason = if self.free_slot {
753            barrier.reason()
754        } else {
755            reason
756        };
757        decided.waiting.insert(self.job, reason);
758        if let Some(scarce) = short.scarce() {
759            hold(self.repository, self.job, scarce, decided);
760        }
761    }
762}
763
764/// A pool's repository and profile, which tell it apart in a plan.
765fn pool_key(repository: &Repository) -> (&str, &str) {
766    (&repository.name, &repository.profile)
767}
768
769/// Says why each queued job no pool of its repository matches waits, unless GitHub runs it on its own runners.
770fn unserved(repositories: &[Repository], decided: &mut Plan) {
771    let mut seen = BTreeSet::new();
772    for repository in repositories {
773        if !seen.insert(repository.name.as_str()) {
774            continue;
775        }
776        let pools: Vec<&Repository> = repositories
777            .iter()
778            .filter(|pool| pool.name == repository.name)
779            .collect();
780        decided.waiting.extend(
781            repository
782                .queued
783                .iter()
784                .filter(|job| {
785                    !hosted_by_github(job) && !pools.iter().any(|pool| matches(job, &pool.labels))
786                })
787                .map(|job| {
788                    (
789                        job.id,
790                        Waiting::NoPool {
791                            labels: job.labels.clone(),
792                        },
793                    )
794                }),
795        );
796    }
797}
798
799/// What a job's runner lacks.
800#[derive(Debug, Clone, Copy, PartialEq, Eq)]
801enum Short {
802    Slot,
803    Memory,
804    Host,
805    Cpu,
806}
807
808impl Short {
809    /// What a running job gives back of it: not a slot, which a job waits for in turn.
810    fn scarce(self) -> Option<Scarce> {
811        match self {
812            Short::Slot => None,
813            Short::Memory | Short::Host => Some(Scarce::Memory),
814            Short::Cpu => Some(Scarce::Cpu),
815        }
816    }
817
818    /// Whether the host is what holds the job.
819    fn held(self) -> Held {
820        match self {
821            Short::Host => Held::ByHost,
822            Short::Slot | Short::Memory | Short::Cpu => Held::ByBudget,
823        }
824    }
825}
826
827/// Why a job whose runner of `memory` and `cpu` does not fit in `profile` (named `name`) waits, given whether it has
828/// a `free_slot` and the budgets `left`, and what it lacks.
829fn why_waits(
830    name: &str,
831    profile: &Profile,
832    free_slot: bool,
833    memory: u64,
834    cpu: u64,
835    left: Left,
836    started: &Started<'_>,
837) -> (Waiting, Short) {
838    let profile_name = || name.to_owned();
839    if !free_slot {
840        let reason = match profile.preparing {
841            Some(Preparing::Reseeding) => Waiting::Reseeding {
842                profile: profile_name(),
843            },
844            Some(Preparing::PullingImage) => Waiting::PullingImage {
845                profile: profile_name(),
846            },
847            None => started.for_slot(
848                name,
849                Waiting::NoSlot {
850                    profile: profile_name(),
851                },
852            ),
853        };
854        return (reason, Short::Slot);
855    }
856    match (left.memory, left.host, left.cpu) {
857        (Some(free), _, _) if free < signed(memory) => (
858            started.for_memory(
859                memory,
860                Waiting::Memory {
861                    needs: memory,
862                    free: unsigned(free),
863                },
864            ),
865            Short::Memory,
866        ),
867        (_, Some(free), _) if free < signed(memory) => (
868            started.for_host(
869                memory,
870                Waiting::HostMemory {
871                    needs: memory,
872                    free: unsigned(free),
873                },
874            ),
875            Short::Host,
876        ),
877        (_, _, Some(free)) => (
878            started.for_cpu(
879                cpu,
880                Waiting::Cpu {
881                    needs: cpu,
882                    free: unsigned(free),
883                },
884            ),
885            Short::Cpu,
886        ),
887        // `fits` said otherwise.
888        (_, _, None) => (
889            Waiting::NoSlot {
890                profile: profile_name(),
891            },
892            Short::Slot,
893        ),
894    }
895}
896
897/// A runner of `repository` in slot `index` of its profile for a queued job, after the warm runners it `replaces`
898/// stop.
899fn start(
900    repository: &Repository,
901    index: usize,
902    memory: u64,
903    cpu: u64,
904    replacing: Vec<SlotRef>,
905    barrier: Option<Barrier>,
906) -> Decision {
907    Decision::Start {
908        slot: SlotRef {
909            profile: repository.profile.clone(),
910            index,
911        },
912        repository: repository.name.clone(),
913        memory,
914        cpu,
915        warm: false,
916        replacing,
917        behind: barrier.map(|barrier| barrier.job),
918    }
919}
920
921/// Starts the warm runners each repository is short of (`wanted`), at its profile's caps, in the slots and budget
922/// the jobs `left`: one per repository at a time, so a few free slots go to several repositories rather than to the
923/// first. None while a job waits for room they would take.
924fn start_warm(
925    wanted: &[(&Repository, usize)],
926    profiles: &BTreeMap<String, Profile>,
927    taken: &mut BTreeMap<&str, Vec<bool>>,
928    mut left: Left,
929    decided: &mut Plan,
930) {
931    let room_wanted = decided.waiting.values().any(|reason| {
932        matches!(
933            reason,
934            Waiting::NoSlot { .. }
935                | Waiting::Memory { .. }
936                | Waiting::HostMemory { .. }
937                | Waiting::Cpu { .. }
938                | Waiting::BehindCpu { .. }
939                | Waiting::BehindMemory { .. }
940                | Waiting::BehindStart { .. }
941        )
942    });
943    if room_wanted {
944        return;
945    }
946    for round in 0.. {
947        let mut any = false;
948        for (repository, wants) in wanted {
949            if *wants <= round {
950                continue;
951            }
952            let (Some(profile), Some(taken)) = (
953                profiles.get(&repository.profile),
954                taken.get_mut(repository.profile.as_str()),
955            ) else {
956                continue;
957            };
958            let (memory, cpu) = (profile.memory, profile.cpus);
959            let Some(index) = taken.iter().position(|taken| !taken) else {
960                continue;
961            };
962            if !left.fits(memory, cpu) {
963                continue;
964            }
965            taken[index] = true;
966            left.take(memory, cpu);
967            any = true;
968            decided.decisions.push(Decision::Start {
969                slot: SlotRef {
970                    profile: repository.profile.clone(),
971                    index,
972                },
973                repository: repository.name.clone(),
974                memory,
975                cpu,
976                warm: true,
977                replacing: Vec::new(),
978                behind: None,
979            });
980        }
981        if !any {
982            break;
983        }
984    }
985}
986
987/// The memory, CPU and host budgets a plan has left; `None`, no budget. Each is negative while what runs takes past
988/// it: a stopped runner's reservation pays that back first, so a start never takes room that is owed.
989#[derive(Debug, Clone, Copy)]
990pub(crate) struct Left {
991    pub(crate) memory: Option<i64>,
992    pub(crate) cpu: Option<i64>,
993    /// The host's memory to spare, which a runner's memory takes from as it does from `memory`.
994    pub(crate) host: Option<i64>,
995}
996
997impl Profile {
998    /// What a runner of this profile could take.
999    fn caps(&self) -> Caps {
1000        Caps {
1001            memory: self.memory,
1002            cpu: self.cpus,
1003        }
1004    }
1005}
1006
1007impl Left {
1008    fn fits(self, memory: u64, cpu: u64) -> bool {
1009        let fits = |free: Option<i64>, needs: u64| free.is_none_or(|free| free >= signed(needs));
1010        fits(self.memory, memory) && fits(self.host, memory) && fits(self.cpu, cpu)
1011    }
1012
1013    /// What a runner of `memory` and `cpu` lacks, the host's memory counted with the slice's: none where there is
1014    /// no budget.
1015    fn short(self, memory: u64, cpu: u64) -> Left {
1016        let lacks = |free: Option<i64>, needs: u64| {
1017            free.map(|free| signed(needs).saturating_sub(free).max(0))
1018        };
1019        Left {
1020            memory: lacks(self.memory, memory).max(lacks(self.host, memory)),
1021            cpu: lacks(self.cpu, cpu),
1022            host: None,
1023        }
1024    }
1025
1026    fn take(&mut self, memory: u64, cpu: u64) {
1027        let take = |free: &mut Option<i64>, used: u64| {
1028            *free = free.map(|free| free.saturating_sub(signed(used)));
1029        };
1030        take(&mut self.memory, memory);
1031        take(&mut self.host, memory);
1032        take(&mut self.cpu, cpu);
1033    }
1034
1035    fn give(&mut self, memory: u64, cpu: u64) {
1036        let give = |free: &mut Option<i64>, freed: u64| {
1037            *free = free.map(|free| free.saturating_add(signed(freed)));
1038        };
1039        give(&mut self.memory, memory);
1040        give(&mut self.host, memory);
1041        give(&mut self.cpu, cpu);
1042    }
1043}
1044
1045/// What `budget` leaves beside what runs `in_use`: negative by what runs past it, so a deficit stays owed rather
1046/// than hidden at 0.
1047fn left(budget: u64, in_use: u64) -> i64 {
1048    signed(budget).saturating_sub(signed(in_use))
1049}
1050
1051/// A budget's bytes or millicores, signed as `Left` counts them.
1052fn signed(amount: u64) -> i64 {
1053    i64::try_from(amount).unwrap_or(i64::MAX)
1054}
1055
1056/// A signed budget as a job's wait shows it: none once it is spent.
1057fn unsigned(free: i64) -> u64 {
1058    u64::try_from(free).unwrap_or(0)
1059}
1060
1061/// What `sort_out` leaves a repository to start: runners for the IDs of its jobs, and warm runners.
1062struct Sorted {
1063    serve: Vec<u64>,
1064    warm: usize,
1065}
1066
1067/// Stops a repository's idle runners no job is left for, beyond its warm ones, and says why its jobs wait when it is
1068/// paused or held, or which an idle runner will take. Returns the jobs it wants a runner for and how many warm
1069/// runners it is short of, unless it is held.
1070fn sort_out(
1071    repository: &Repository,
1072    profiles: &BTreeMap<String, Profile>,
1073    now: SystemTime,
1074    decided: &mut Plan,
1075) -> Option<Sorted> {
1076    let mut matching: Vec<&QueuedJob> = repository
1077        .queued
1078        .iter()
1079        .filter(|job| matches(job, &repository.labels))
1080        .collect();
1081    let profile = profiles.get(&repository.profile);
1082    let mut warm = repository.warm;
1083    if repository.paused {
1084        decided
1085            .waiting
1086            .extend(matching.iter().map(|job| (job.id, Waiting::Paused)));
1087        // None is left for its idle runners, which stop at once.
1088        matching.clear();
1089        warm = 0;
1090    }
1091    // Upkeep waits for its profile's runners: none is kept, and none waits out `IDLE_TIMEOUT` first. Nor does a
1092    // paused repository's: GitHub would give it a job queued before the pause.
1093    let upkeep_due = profile.is_some_and(|profile| profile.upkeep_due);
1094    let stop_now = upkeep_due || repository.paused;
1095    if upkeep_due {
1096        warm = 0;
1097    }
1098    let (idle, closing): (Vec<(SlotRef, &RunnerSlot)>, Vec<_>) = profile
1099        .into_iter()
1100        .flat_map(|profile| profile.slots.iter().enumerate())
1101        .filter_map(|(index, slot)| match slot {
1102            Slot::Runner(runner) if runner.repository == repository.name && !runner.busy => Some((
1103                SlotRef {
1104                    profile: repository.profile.clone(),
1105                    index,
1106                },
1107                runner,
1108            )),
1109            _ => None,
1110        })
1111        .partition(|(slot, _)| profile.is_none_or(|profile| slot.index < profile.count));
1112    // Idle runners in slots a lowered `slots` closed stop now: neither warm nor room for a job, their slots close.
1113    decided
1114        .decisions
1115        .extend(closing.into_iter().map(|(slot, _)| Decision::Stop {
1116            slot,
1117            reason: StopReason::Closed,
1118        }));
1119    let surplus = idle.len().saturating_sub(matching.len());
1120    let stops: Vec<SlotRef> = idle
1121        .iter()
1122        .filter(|(_, runner)| {
1123            stop_now
1124                || now
1125                    .duration_since(runner.started_at)
1126                    .is_ok_and(|waited| waited >= IDLE_TIMEOUT)
1127        })
1128        .take(surplus.saturating_sub(warm))
1129        .map(|(slot, _)| slot.clone())
1130        .collect();
1131    // The idle runners left past those its jobs take are warm.
1132    let kept: Vec<&SlotRef> = idle
1133        .iter()
1134        .map(|(slot, _)| slot)
1135        .filter(|slot| !stops.contains(slot))
1136        .collect();
1137    decided
1138        .warm
1139        .extend(kept.iter().skip(matching.len()).map(|slot| (*slot).clone()));
1140    let warm = warm.saturating_sub(kept.len().saturating_sub(matching.len()));
1141    decided
1142        .decisions
1143        .extend(stops.into_iter().map(|slot| Decision::Stop {
1144            slot,
1145            reason: if repository.paused {
1146                StopReason::Paused
1147            } else if upkeep_due {
1148                StopReason::Upkeep
1149            } else {
1150                StopReason::Expired
1151            },
1152        }));
1153    let missing = matching.len().saturating_sub(idle.len());
1154    // The oldest jobs are the ones still waiting once the idle runners take theirs.
1155    let skip = matching.len() - missing;
1156    decided.waiting.extend(
1157        matching
1158            .iter()
1159            .take(skip)
1160            .map(|job| (job.id, Waiting::RunnerStarting)),
1161    );
1162    let serve = matching.iter().skip(skip).map(|job| job.id);
1163    match repository.held.filter(|held| held.until > now) {
1164        Some(held) => {
1165            let until = crate::time::ms(held.until) / 1000;
1166            decided.waiting.extend(serve.map(|job| {
1167                (
1168                    job,
1169                    Waiting::Backoff {
1170                        until,
1171                        cause: held.cause,
1172                    },
1173                )
1174            }));
1175            None
1176        }
1177        None => Some(Sorted {
1178            serve: serve.collect(),
1179            warm,
1180        }),
1181    }
1182}
1183
1184/// The warm runners a queued job may stop to make room for itself.
1185struct Warm<'plan> {
1186    /// Each warm runner with what it takes, in slot order; `None` once stopped for a job.
1187    runners: Vec<Option<(SlotRef, &'plan RunnerSlot)>>,
1188}
1189
1190/// The room some warm runners give back.
1191struct Room {
1192    /// The warm runners to stop.
1193    stopped: Vec<SlotRef>,
1194    /// A slot of the job's profile among them, when it needed one.
1195    slot: Option<usize>,
1196    memory: u64,
1197    cpu: u64,
1198}
1199
1200impl<'plan> Warm<'plan> {
1201    /// The warm runners of `warm`; none while the slice is `held`, when no start may use their room.
1202    fn new(
1203        warm: &BTreeSet<SlotRef>,
1204        profiles: &'plan BTreeMap<String, Profile>,
1205        held: bool,
1206    ) -> Warm<'plan> {
1207        let runners = warm
1208            .iter()
1209            .filter(|_| !held)
1210            .filter_map(
1211                |slot| match profiles.get(&slot.profile)?.slots.get(slot.index)? {
1212                    Slot::Runner(runner) => Some(Some((slot.clone(), runner))),
1213                    Slot::Free | Slot::Closed => None,
1214                },
1215            )
1216            .collect();
1217        Warm { runners }
1218    }
1219
1220    /// Picks warm runners of pools other than `repository` whose room lets its next runner, of `needs_memory` and
1221    /// `needs_cpu`, start in the budgets `left`: a slot of its profile when it has none (`slot`), and the memory
1222    /// and CPU it is short of. Those in its profile go first. `None`, and nothing picked, when all of them would
1223    /// not do.
1224    fn make_room(
1225        &mut self,
1226        repository: &Repository,
1227        slot: bool,
1228        left: Left,
1229        needs_memory: u64,
1230        needs_cpu: u64,
1231    ) -> Option<Room> {
1232        let short = left.short(needs_memory, needs_cpu);
1233        let (memory, cpu) = (
1234            unsigned(short.memory.unwrap_or(0)),
1235            unsigned(short.cpu.unwrap_or(0)),
1236        );
1237        let mut candidates: Vec<usize> = self
1238            .runners
1239            .iter()
1240            .enumerate()
1241            .filter_map(|(at, runner)| {
1242                runner
1243                    .as_ref()
1244                    .filter(|(slot, runner)| {
1245                        runner.repository != repository.name || slot.profile != repository.profile
1246                    })
1247                    .map(|_| at)
1248            })
1249            .collect();
1250        // Its own profile's first: their slots serve it too.
1251        candidates.sort_by_key(|at| {
1252            self.runners[*at]
1253                .as_ref()
1254                .is_some_and(|(slot, _)| slot.profile != repository.profile)
1255        });
1256        let mut room = Room {
1257            stopped: Vec::new(),
1258            slot: None,
1259            memory: 0,
1260            cpu: 0,
1261        };
1262        let mut picked = Vec::new();
1263        for at in candidates {
1264            let short = (slot && room.slot.is_none()) || room.memory < memory || room.cpu < cpu;
1265            if !short {
1266                break;
1267            }
1268            let Some((ref_, runner)) = &self.runners[at] else {
1269                continue;
1270            };
1271            let gives_slot = ref_.profile == repository.profile;
1272            // A runner that gives nothing the job still lacks stays.
1273            let helps = (gives_slot && slot && room.slot.is_none())
1274                || (room.memory < memory && runner.memory > 0)
1275                || (room.cpu < cpu && runner.cpu > 0);
1276            if !helps {
1277                continue;
1278            }
1279            if gives_slot && room.slot.is_none() {
1280                room.slot = Some(ref_.index);
1281            }
1282            room.memory += runner.memory;
1283            room.cpu += runner.cpu;
1284            room.stopped.push(ref_.clone());
1285            picked.push(at);
1286        }
1287        // What they give back must let it start: a start never takes what the stops do not free.
1288        let mut after = left;
1289        after.give(room.memory, room.cpu);
1290        if (slot && room.slot.is_none()) || !after.fits(needs_memory, needs_cpu) {
1291            return None;
1292        }
1293        for at in picked {
1294            self.runners[at] = None;
1295        }
1296        Some(room)
1297    }
1298}
1299
1300/// What a plan's own starts took, so a job held only by them waits behind them rather than for a slot, memory or CPU
1301/// in use. The status explains with a plan it does not run, whose starts may never happen.
1302struct Started<'plan> {
1303    /// The profiles with a free slot before the plan's starts.
1304    free_slots: BTreeSet<&'plan str>,
1305    /// The budgets left before them.
1306    before: Left,
1307    /// The first job each profile, and any profile, starts a runner for.
1308    by_profile: BTreeMap<&'plan str, u64>,
1309    first: Option<u64>,
1310}
1311
1312impl<'plan> Started<'plan> {
1313    fn new(taken: &BTreeMap<&'plan str, Vec<bool>>, before: Left) -> Started<'plan> {
1314        Started {
1315            free_slots: taken
1316                .iter()
1317                .filter(|(_, slots)| slots.contains(&false))
1318                .map(|(name, _)| *name)
1319                .collect(),
1320            before,
1321            by_profile: BTreeMap::new(),
1322            first: None,
1323        }
1324    }
1325
1326    /// The plan starts a runner for `job` in `profile`.
1327    fn note(&mut self, profile: &'plan str, job: u64) {
1328        self.by_profile.entry(profile).or_insert(job);
1329        self.first.get_or_insert(job);
1330    }
1331
1332    /// `reason` for a job `profile` has no slot for, unless only this plan's starts took its free slots.
1333    fn for_slot(&self, profile: &str, reason: Waiting) -> Waiting {
1334        match self.by_profile.get(profile) {
1335            Some(older) if self.free_slots.contains(profile) => {
1336                Waiting::BehindStart { job: *older }
1337            }
1338            _ => reason,
1339        }
1340    }
1341
1342    /// `reason` for a job whose `needs` of memory do not fit, unless they did before this plan's starts.
1343    fn for_memory(&self, needs: u64, reason: Waiting) -> Waiting {
1344        Self::behind(self.first, self.before.memory, needs).unwrap_or(reason)
1345    }
1346
1347    /// `reason` for a job whose `needs` of memory the host cannot spare, unless it could before this plan's starts.
1348    fn for_host(&self, needs: u64, reason: Waiting) -> Waiting {
1349        Self::behind(self.first, self.before.host, needs).unwrap_or(reason)
1350    }
1351
1352    /// `reason` for a job whose `needs` of CPU do not fit, unless they did before this plan's starts.
1353    fn for_cpu(&self, needs: u64, reason: Waiting) -> Waiting {
1354        Self::behind(self.first, self.before.cpu, needs).unwrap_or(reason)
1355    }
1356
1357    fn behind(first: Option<u64>, free: Option<i64>, needs: u64) -> Option<Waiting> {
1358        first
1359            .filter(|_| free.is_some_and(|free| free >= signed(needs)))
1360            .map(|job| Waiting::BehindStart { job })
1361    }
1362}
1363
1364/// Whether each slot of each profile is taken, by profile name: by a runner, closed, or its profile preparing.
1365fn taken_slots(profiles: &BTreeMap<String, Profile>) -> BTreeMap<&str, Vec<bool>> {
1366    profiles
1367        .iter()
1368        .map(|(name, profile)| {
1369            let taken = profile
1370                .slots
1371                .iter()
1372                .map(|slot| profile.preparing.is_some() || *slot != Slot::Free)
1373                .collect();
1374            (name.as_str(), taken)
1375        })
1376        .collect()
1377}
1378
1379#[cfg(test)]
1380mod tests;