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