Skip to main content

runnerd_core/
scheduler.rs

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