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