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 runner: it waited `IDLE_TIMEOUT` for a job no longer queued and is not kept warm, or it is a
191    /// warm runner whose room a queued job takes.
192    Stop {
193        /// The slot whose runner stops.
194        slot: SlotRef,
195    },
196}
197
198/// What `plan` decides, and why each queued job it starts no runner for waits.
199#[derive(Debug, Clone, Default, PartialEq, Eq)]
200pub struct Plan {
201    /// What to start, hold and stop.
202    pub decisions: Vec<Decision>,
203    /// Why each queued job of a repository's matching jobs waits, by job ID. A job an idle runner will take is
204    /// `Waiting::RunnerStarting`; a job this plan starts a runner for has no reason, as that runner does not exist
205    /// until the start succeeds.
206    pub waiting: BTreeMap<u64, Waiting>,
207    /// The idle runners kept warm: no queued job of their repository waits for them.
208    pub warm: BTreeSet<SlotRef>,
209}
210
211/// The budgets a plan starts runners within.
212#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
213pub struct Budget {
214    /// The memory left, negative by what the running containers take past `MemoryMax` (`left`); `None` for no
215    /// budget.
216    pub memory: Option<i64>,
217    /// The CPU left, in millicores, negative by what the runners reserve past the budget (`left`); `None` for no
218    /// budget.
219    pub cpu: Option<i64>,
220    /// The memory the host has to spare for new runners beside other programs (ADR 0055), negative by what the
221    /// running ones reserve past the host's limit; `None` when not known.
222    pub host: Option<i64>,
223    /// Nothing starts, so no warm runner stops to make room: measured admission holds the slice at its high-water
224    /// mark, or the host's tasks stall for memory.
225    pub held: bool,
226}
227
228/// The workflow labels of GitHub-hosted runners, from
229/// <https://github.com/github/docs/blob/main/data/reusables/actions/supported-github-runners.md> and its single-CPU
230/// row (`single-cpu-table-row.md`), and the larger macOS runners of
231/// <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
232/// missing here makes its jobs wait with `Waiting::NoPool`, whose wording stays true for them.
233const GITHUB_HOSTED: &[&str] = &[
234    "ubuntu-slim",
235    "ubuntu-latest",
236    "ubuntu-26.04",
237    "ubuntu-24.04",
238    "ubuntu-22.04",
239    "ubuntu-26.04-arm",
240    "ubuntu-24.04-arm",
241    "ubuntu-22.04-arm",
242    "windows-latest",
243    "windows-2025",
244    "windows-2025-vs2026",
245    "windows-2022",
246    "windows-11-arm",
247    "windows-11-vs2026-arm",
248    "macos-latest",
249    "macos-26",
250    "macos-15",
251    "macos-14",
252    "macos-26-intel",
253    "macos-15-intel",
254    "xcode-27",
255    "macos-latest-large",
256    "macos-26-large",
257    "macos-15-large",
258    "macos-14-large",
259    "macos-latest-xlarge",
260    "macos-26-xlarge",
261    "macos-15-xlarge",
262    "macos-14-xlarge",
263    "xcode-27-xlarge",
264];
265
266/// Whether GitHub runs a job on its own runners: it asks for exactly one label, one of `GITHUB_HOSTED`. No pool of
267/// this daemon is meant for it. A typo, a custom label and an image name beside `self-hosted` are the owner's to
268/// fix, so they wait for a pool instead.
269fn hosted_by_github(job: &QueuedJob) -> bool {
270    matches!(&job.labels[..], [label] if GITHUB_HOSTED.iter().any(|hosted| hosted.eq_ignore_ascii_case(label)))
271}
272
273/// Whether a job may run on a repository's runners: every label it asks for is one of theirs. GitHub compares
274/// labels without regard to case.
275pub fn matches(job: &QueuedJob, labels: &[String]) -> bool {
276    crate::config::labels_match(&job.labels, labels)
277}
278
279/// Decides which slots start a runner and which idle runners stop, and why each job left queued waits.
280///
281/// `repositories` holds each repository's pools; a job is served by the pool whose labels match it, and one no pool
282/// of its repository matches waits for a pool (`Waiting::NoPool`) unless it is for GitHub's own runners. Each pool
283/// gets a runner per matching queued job, less its runners still waiting for a job. Jobs are
284/// served oldest first across repositories, each in a free slot of its repository's profile (`free_slot`: the one
285/// 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
286/// `budget.host`, and its CPU
287/// (`Repository::runner_cpu`, by default the slot's `cpus`) fits `budget.cpu` (`None`: no budget). A job that does
288/// not fit takes the room of warm runners of other repositories, which stop. A repository whose job had a slot and
289/// memory but not CPU is held once (`Decision::HeldForCpu`). An idle runner stops once no queued job is left for it,
290/// it is not one of its repository's `warm` runners, and it waited `IDLE_TIMEOUT`. Once a held repository waited
291/// `CPU_PRIORITY_AFTER`, no younger job starts until its own fits. Last, while no job waits for room, each
292/// repository short of its `warm` runners starts them at its profile's caps, one per repository at a time.
293pub fn plan(
294    repositories: &[Repository],
295    profiles: &BTreeMap<String, Profile>,
296    budget: Budget,
297    now: SystemTime,
298) -> Plan {
299    let mut decided = Plan::default();
300    unserved(repositories, &mut decided);
301    let mut wanted = BTreeMap::new();
302    let mut warm_wanted = Vec::new();
303    let mut jobs = Vec::new();
304    for repository in repositories {
305        if let Some(sorted) = sort_out(repository, profiles, now, &mut decided) {
306            wanted.insert(pool_key(repository), sorted.serve.len());
307            jobs.extend(sorted.serve.into_iter().map(|job| (job, repository)));
308            warm_wanted.push((repository, sorted.warm));
309        }
310    }
311    jobs.sort_by_key(|(id, _)| *id);
312
313    let mut warm = Warm::new(&decided.warm, profiles, budget.held);
314    let mut taken = taken_slots(profiles);
315    let mut left = Left {
316        memory: budget.memory,
317        cpu: budget.cpu,
318        host: budget.host,
319    };
320    let mut started = Started::new(&taken, left);
321    // The job that waited long enough for CPU that no younger one takes CPU before it.
322    let mut first_for_cpu = None;
323    for (position, &(job, repository)) in jobs.iter().enumerate() {
324        let Some(missing) = wanted.get_mut(&pool_key(repository)) else {
325            continue;
326        };
327        if *missing == 0 {
328            continue;
329        }
330        let (Some(profile), Some(taken)) = (
331            profiles.get(&repository.profile),
332            taken.get_mut(repository.profile.as_str()),
333        ) else {
334            continue;
335        };
336        if let Some(older) = first_for_cpu {
337            decided
338                .waiting
339                .insert(job, Waiting::BehindCpu { job: older });
340            continue;
341        }
342        let memory = repository.runner_memory.unwrap_or(profile.memory);
343        let cpu = repository.runner_cpu.unwrap_or(profile.cpus);
344        let free_index = free_slot(taken, profile, repository, job, &jobs[position + 1..]);
345        let fits = free_index.is_some() && left.fits(memory, cpu);
346        let room = if fits || profile.preparing.is_some() {
347            None
348        } else {
349            warm.make_room(repository, free_index.is_none(), left, memory, cpu)
350        };
351        let index = match (room.as_ref(), free_index) {
352            (Some(room), free) => free.or(room.slot).unwrap_or_default(),
353            (None, Some(index)) if fits => index,
354            (None, free) => {
355                let (reason, short) = why_waits(
356                    &repository.profile,
357                    profile,
358                    free.is_some(),
359                    memory,
360                    cpu,
361                    left,
362                    &started,
363                );
364                decided.waiting.insert(job, reason);
365                if short == Short::Cpu {
366                    let held = held_for_cpu(repository);
367                    if !decided.decisions.contains(&held) {
368                        decided.decisions.push(held);
369                    }
370                    // It waited long enough: no younger job takes CPU until it fits.
371                    if repository.starved_of_cpu(now) {
372                        first_for_cpu = Some(job);
373                    }
374                }
375                continue;
376            }
377        };
378        // The warm runners whose room it takes stop first.
379        let replacing = room.map_or_else(Vec::new, |room| {
380            left.give(room.memory, room.cpu);
381            for slot in &room.stopped {
382                decided.warm.remove(slot);
383                decided
384                    .decisions
385                    .push(Decision::Stop { slot: slot.clone() });
386            }
387            room.stopped
388        });
389        taken[index] = true;
390        *missing -= 1;
391        started.note(&repository.profile, job);
392        left.take(memory, cpu);
393        decided
394            .decisions
395            .push(start(repository, index, memory, cpu, replacing));
396    }
397    if !budget.held {
398        start_warm(&warm_wanted, profiles, &mut taken, left, &mut decided);
399    }
400    decided
401}
402
403/// The free slot the queued job `job` of `repository` starts in: the one that ran the same job last (repository,
404/// workflow and name), else one that ran a job of the same repository, else the lowest. Warm caches are the slot's
405/// own layer (ADR 0007), so the same job there finds them. Only free slots count: a start never waits for the one it
406/// would prefer. Short of an exact match, a slot that a younger job of the `later` ones in the profile matches
407/// exactly is left to it while another is free.
408fn free_slot(
409    taken: &[bool],
410    profile: &Profile,
411    repository: &Repository,
412    job: u64,
413    later: &[(u64, &Repository)],
414) -> Option<usize> {
415    let ran = |index: usize| profile.ran.get(index).and_then(Option::as_ref);
416    let ran_it = |index: usize, repository: &Repository, job: u64| {
417        let queued = repository.queued.iter().find(|queued| queued.id == job);
418        queued.zip(ran(index)).is_some_and(|(queued, key)| {
419            key.repository == repository.name
420                && key.workflow == queued.workflow
421                && key.name == queued.name
422        })
423    };
424    taken
425        .iter()
426        .enumerate()
427        .filter(|(_, taken)| !**taken)
428        .map(|(index, _)| index)
429        .min_by_key(|&index| {
430            let wanted_later = later.iter().any(|&(id, other)| {
431                other.profile == repository.profile && ran_it(index, other, id)
432            });
433            let same_repository = ran(index).is_some_and(|key| key.repository == repository.name);
434            (
435                !ran_it(index, repository, job),
436                wanted_later,
437                !same_repository,
438                index,
439            )
440        })
441}
442
443/// The hold of `repository`'s next job for CPU.
444fn held_for_cpu(repository: &Repository) -> Decision {
445    Decision::HeldForCpu {
446        repository: repository.name.clone(),
447        profile: repository.profile.clone(),
448    }
449}
450
451/// A pool's repository and profile, which tell it apart in a plan.
452fn pool_key(repository: &Repository) -> (&str, &str) {
453    (&repository.name, &repository.profile)
454}
455
456/// Says why each queued job no pool of its repository matches waits, unless GitHub runs it on its own runners.
457fn unserved(repositories: &[Repository], decided: &mut Plan) {
458    let mut seen = BTreeSet::new();
459    for repository in repositories {
460        if !seen.insert(repository.name.as_str()) {
461            continue;
462        }
463        let pools: Vec<&Repository> = repositories
464            .iter()
465            .filter(|pool| pool.name == repository.name)
466            .collect();
467        decided.waiting.extend(
468            repository
469                .queued
470                .iter()
471                .filter(|job| {
472                    !hosted_by_github(job) && !pools.iter().any(|pool| matches(job, &pool.labels))
473                })
474                .map(|job| {
475                    (
476                        job.id,
477                        Waiting::NoPool {
478                            labels: job.labels.clone(),
479                        },
480                    )
481                }),
482        );
483    }
484}
485
486/// What a job's runner lacks.
487#[derive(Debug, Clone, Copy, PartialEq, Eq)]
488enum Short {
489    Slot,
490    Memory,
491    Cpu,
492}
493
494/// Why a job whose runner of `memory` and `cpu` does not fit in `profile` (named `name`) waits, given whether it has
495/// a `free_slot` and the budgets `left`, and what it lacks.
496fn why_waits(
497    name: &str,
498    profile: &Profile,
499    free_slot: bool,
500    memory: u64,
501    cpu: u64,
502    left: Left,
503    started: &Started<'_>,
504) -> (Waiting, Short) {
505    let profile_name = || name.to_owned();
506    if !free_slot {
507        let reason = match profile.preparing {
508            Some(Preparing::Reseeding) => Waiting::Reseeding {
509                profile: profile_name(),
510            },
511            Some(Preparing::PullingImage) => Waiting::PullingImage {
512                profile: profile_name(),
513            },
514            None => started.for_slot(
515                name,
516                Waiting::NoSlot {
517                    profile: profile_name(),
518                },
519            ),
520        };
521        return (reason, Short::Slot);
522    }
523    match (left.memory, left.host, left.cpu) {
524        (Some(free), _, _) if free < signed(memory) => (
525            started.for_memory(
526                memory,
527                Waiting::Memory {
528                    needs: memory,
529                    free: unsigned(free),
530                },
531            ),
532            Short::Memory,
533        ),
534        (_, Some(free), _) if free < signed(memory) => (
535            started.for_host(
536                memory,
537                Waiting::HostMemory {
538                    needs: memory,
539                    free: unsigned(free),
540                },
541            ),
542            Short::Memory,
543        ),
544        (_, _, Some(free)) => (
545            started.for_cpu(
546                cpu,
547                Waiting::Cpu {
548                    needs: cpu,
549                    free: unsigned(free),
550                },
551            ),
552            Short::Cpu,
553        ),
554        // `fits` said otherwise.
555        (_, _, None) => (
556            Waiting::NoSlot {
557                profile: profile_name(),
558            },
559            Short::Slot,
560        ),
561    }
562}
563
564/// A runner of `repository` in slot `index` of its profile for a queued job, after the warm runners it `replaces`
565/// stop.
566fn start(
567    repository: &Repository,
568    index: usize,
569    memory: u64,
570    cpu: u64,
571    replacing: Vec<SlotRef>,
572) -> Decision {
573    Decision::Start {
574        slot: SlotRef {
575            profile: repository.profile.clone(),
576            index,
577        },
578        repository: repository.name.clone(),
579        memory,
580        cpu,
581        warm: false,
582        replacing,
583    }
584}
585
586/// Starts the warm runners each repository is short of (`wanted`), at its profile's caps, in the slots and budget
587/// the jobs `left`: one per repository at a time, so a few free slots go to several repositories rather than to the
588/// first. None while a job waits for room they would take.
589fn start_warm(
590    wanted: &[(&Repository, usize)],
591    profiles: &BTreeMap<String, Profile>,
592    taken: &mut BTreeMap<&str, Vec<bool>>,
593    mut left: Left,
594    decided: &mut Plan,
595) {
596    let room_wanted = decided.waiting.values().any(|reason| {
597        matches!(
598            reason,
599            Waiting::NoSlot { .. }
600                | Waiting::Memory { .. }
601                | Waiting::HostMemory { .. }
602                | Waiting::Cpu { .. }
603                | Waiting::BehindCpu { .. }
604                | Waiting::BehindStart { .. }
605        )
606    });
607    if room_wanted {
608        return;
609    }
610    for round in 0.. {
611        let mut any = false;
612        for (repository, wants) in wanted {
613            if *wants <= round {
614                continue;
615            }
616            let (Some(profile), Some(taken)) = (
617                profiles.get(&repository.profile),
618                taken.get_mut(repository.profile.as_str()),
619            ) else {
620                continue;
621            };
622            let (memory, cpu) = (profile.memory, profile.cpus);
623            let Some(index) = taken.iter().position(|taken| !taken) else {
624                continue;
625            };
626            if !left.fits(memory, cpu) {
627                continue;
628            }
629            taken[index] = true;
630            left.take(memory, cpu);
631            any = true;
632            decided.decisions.push(Decision::Start {
633                slot: SlotRef {
634                    profile: repository.profile.clone(),
635                    index,
636                },
637                repository: repository.name.clone(),
638                memory,
639                cpu,
640                warm: true,
641                replacing: Vec::new(),
642            });
643        }
644        if !any {
645            break;
646        }
647    }
648}
649
650/// The memory, CPU and host budgets a plan has left; `None`, no budget. Each is negative while what runs takes past
651/// it: a stopped runner's reservation pays that back first, so a start never takes room that is owed.
652#[derive(Debug, Clone, Copy)]
653struct Left {
654    memory: Option<i64>,
655    cpu: Option<i64>,
656    /// The host's memory to spare, which a runner's memory takes from as it does from `memory`.
657    host: Option<i64>,
658}
659
660impl Left {
661    fn fits(self, memory: u64, cpu: u64) -> bool {
662        let fits = |free: Option<i64>, needs: u64| free.is_none_or(|free| free >= signed(needs));
663        fits(self.memory, memory) && fits(self.host, memory) && fits(self.cpu, cpu)
664    }
665
666    /// What a runner of `memory` and `cpu` lacks, the host's memory counted with the slice's: none where there is
667    /// no budget.
668    fn short(self, memory: u64, cpu: u64) -> Left {
669        let lacks = |free: Option<i64>, needs: u64| {
670            free.map(|free| signed(needs).saturating_sub(free).max(0))
671        };
672        Left {
673            memory: lacks(self.memory, memory).max(lacks(self.host, memory)),
674            cpu: lacks(self.cpu, cpu),
675            host: None,
676        }
677    }
678
679    fn take(&mut self, memory: u64, cpu: u64) {
680        let take = |free: &mut Option<i64>, used: u64| {
681            *free = free.map(|free| free.saturating_sub(signed(used)));
682        };
683        take(&mut self.memory, memory);
684        take(&mut self.host, memory);
685        take(&mut self.cpu, cpu);
686    }
687
688    fn give(&mut self, memory: u64, cpu: u64) {
689        let give = |free: &mut Option<i64>, freed: u64| {
690            *free = free.map(|free| free.saturating_add(signed(freed)));
691        };
692        give(&mut self.memory, memory);
693        give(&mut self.host, memory);
694        give(&mut self.cpu, cpu);
695    }
696}
697
698/// What `budget` leaves beside what runs `in_use`: negative by what runs past it, so a deficit stays owed rather
699/// than hidden at 0.
700fn left(budget: u64, in_use: u64) -> i64 {
701    signed(budget).saturating_sub(signed(in_use))
702}
703
704/// A budget's bytes or millicores, signed as `Left` counts them.
705fn signed(amount: u64) -> i64 {
706    i64::try_from(amount).unwrap_or(i64::MAX)
707}
708
709/// A signed budget as a job's wait shows it: none once it is spent.
710fn unsigned(free: i64) -> u64 {
711    u64::try_from(free).unwrap_or(0)
712}
713
714/// What `sort_out` leaves a repository to start: runners for the IDs of its jobs, and warm runners.
715struct Sorted {
716    serve: Vec<u64>,
717    warm: usize,
718}
719
720/// Stops a repository's idle runners no job is left for, beyond its warm ones, and says why its jobs wait when it is
721/// paused or held, or which an idle runner will take. Returns the jobs it wants a runner for and how many warm
722/// runners it is short of, unless it is held.
723fn sort_out(
724    repository: &Repository,
725    profiles: &BTreeMap<String, Profile>,
726    now: SystemTime,
727    decided: &mut Plan,
728) -> Option<Sorted> {
729    let mut matching: Vec<&QueuedJob> = repository
730        .queued
731        .iter()
732        .filter(|job| matches(job, &repository.labels))
733        .collect();
734    let profile = profiles.get(&repository.profile);
735    let mut warm = repository.warm;
736    if repository.paused {
737        decided
738            .waiting
739            .extend(matching.iter().map(|job| (job.id, Waiting::Paused)));
740        // None is left for its idle runners, which stop at once.
741        matching.clear();
742        warm = 0;
743    }
744    // Upkeep waits for its profile's runners: none is kept, and none waits out `IDLE_TIMEOUT` first. Nor does a
745    // paused repository's: GitHub would give it a job queued before the pause.
746    let upkeep_due = profile.is_some_and(|profile| profile.upkeep_due);
747    let stop_now = upkeep_due || repository.paused;
748    if upkeep_due {
749        warm = 0;
750    }
751    let (idle, closing): (Vec<(SlotRef, &RunnerSlot)>, Vec<_>) = profile
752        .into_iter()
753        .flat_map(|profile| profile.slots.iter().enumerate())
754        .filter_map(|(index, slot)| match slot {
755            Slot::Runner(runner) if runner.repository == repository.name && !runner.busy => Some((
756                SlotRef {
757                    profile: repository.profile.clone(),
758                    index,
759                },
760                runner,
761            )),
762            _ => None,
763        })
764        .partition(|(slot, _)| profile.is_none_or(|profile| slot.index < profile.count));
765    // Idle runners in slots a lowered `slots` closed stop now: neither warm nor room for a job, their slots close.
766    decided
767        .decisions
768        .extend(closing.into_iter().map(|(slot, _)| Decision::Stop { slot }));
769    let surplus = idle.len().saturating_sub(matching.len());
770    let stops: Vec<SlotRef> = idle
771        .iter()
772        .filter(|(_, runner)| {
773            stop_now
774                || now
775                    .duration_since(runner.started_at)
776                    .is_ok_and(|waited| waited >= IDLE_TIMEOUT)
777        })
778        .take(surplus.saturating_sub(warm))
779        .map(|(slot, _)| slot.clone())
780        .collect();
781    // The idle runners left past those its jobs take are warm.
782    let kept: Vec<&SlotRef> = idle
783        .iter()
784        .map(|(slot, _)| slot)
785        .filter(|slot| !stops.contains(slot))
786        .collect();
787    decided
788        .warm
789        .extend(kept.iter().skip(matching.len()).map(|slot| (*slot).clone()));
790    let warm = warm.saturating_sub(kept.len().saturating_sub(matching.len()));
791    decided
792        .decisions
793        .extend(stops.into_iter().map(|slot| Decision::Stop { slot }));
794    let missing = matching.len().saturating_sub(idle.len());
795    // The oldest jobs are the ones still waiting once the idle runners take theirs.
796    let skip = matching.len() - missing;
797    decided.waiting.extend(
798        matching
799            .iter()
800            .take(skip)
801            .map(|job| (job.id, Waiting::RunnerStarting)),
802    );
803    let serve = matching.iter().skip(skip).map(|job| job.id);
804    match repository.held.filter(|held| held.until > now) {
805        Some(held) => {
806            let until = crate::time::ms(held.until) / 1000;
807            decided.waiting.extend(serve.map(|job| {
808                (
809                    job,
810                    Waiting::Backoff {
811                        until,
812                        cause: held.cause,
813                    },
814                )
815            }));
816            None
817        }
818        None => Some(Sorted {
819            serve: serve.collect(),
820            warm,
821        }),
822    }
823}
824
825/// The warm runners a queued job may stop to make room for itself.
826struct Warm<'plan> {
827    /// Each warm runner with what it takes, in slot order; `None` once stopped for a job.
828    runners: Vec<Option<(SlotRef, &'plan RunnerSlot)>>,
829}
830
831/// The room some warm runners give back.
832struct Room {
833    /// The warm runners to stop.
834    stopped: Vec<SlotRef>,
835    /// A slot of the job's profile among them, when it needed one.
836    slot: Option<usize>,
837    memory: u64,
838    cpu: u64,
839}
840
841impl<'plan> Warm<'plan> {
842    /// The warm runners of `warm`; none while the slice is `held`, when no start may use their room.
843    fn new(
844        warm: &BTreeSet<SlotRef>,
845        profiles: &'plan BTreeMap<String, Profile>,
846        held: bool,
847    ) -> Warm<'plan> {
848        let runners = warm
849            .iter()
850            .filter(|_| !held)
851            .filter_map(
852                |slot| match profiles.get(&slot.profile)?.slots.get(slot.index)? {
853                    Slot::Runner(runner) => Some(Some((slot.clone(), runner))),
854                    Slot::Free | Slot::Closed => None,
855                },
856            )
857            .collect();
858        Warm { runners }
859    }
860
861    /// Picks warm runners of pools other than `repository` whose room lets its next runner, of `needs_memory` and
862    /// `needs_cpu`, start in the budgets `left`: a slot of its profile when it has none (`slot`), and the memory
863    /// and CPU it is short of. Those in its profile go first. `None`, and nothing picked, when all of them would
864    /// not do.
865    fn make_room(
866        &mut self,
867        repository: &Repository,
868        slot: bool,
869        left: Left,
870        needs_memory: u64,
871        needs_cpu: u64,
872    ) -> Option<Room> {
873        let short = left.short(needs_memory, needs_cpu);
874        let (memory, cpu) = (
875            unsigned(short.memory.unwrap_or(0)),
876            unsigned(short.cpu.unwrap_or(0)),
877        );
878        let mut candidates: Vec<usize> = self
879            .runners
880            .iter()
881            .enumerate()
882            .filter_map(|(at, runner)| {
883                runner
884                    .as_ref()
885                    .filter(|(slot, runner)| {
886                        runner.repository != repository.name || slot.profile != repository.profile
887                    })
888                    .map(|_| at)
889            })
890            .collect();
891        // Its own profile's first: their slots serve it too.
892        candidates.sort_by_key(|at| {
893            self.runners[*at]
894                .as_ref()
895                .is_some_and(|(slot, _)| slot.profile != repository.profile)
896        });
897        let mut room = Room {
898            stopped: Vec::new(),
899            slot: None,
900            memory: 0,
901            cpu: 0,
902        };
903        let mut picked = Vec::new();
904        for at in candidates {
905            let short = (slot && room.slot.is_none()) || room.memory < memory || room.cpu < cpu;
906            if !short {
907                break;
908            }
909            let Some((ref_, runner)) = &self.runners[at] else {
910                continue;
911            };
912            let gives_slot = ref_.profile == repository.profile;
913            // A runner that gives nothing the job still lacks stays.
914            let helps = (gives_slot && slot && room.slot.is_none())
915                || (room.memory < memory && runner.memory > 0)
916                || (room.cpu < cpu && runner.cpu > 0);
917            if !helps {
918                continue;
919            }
920            if gives_slot && room.slot.is_none() {
921                room.slot = Some(ref_.index);
922            }
923            room.memory += runner.memory;
924            room.cpu += runner.cpu;
925            room.stopped.push(ref_.clone());
926            picked.push(at);
927        }
928        // What they give back must let it start: a start never takes what the stops do not free.
929        let mut after = left;
930        after.give(room.memory, room.cpu);
931        if (slot && room.slot.is_none()) || !after.fits(needs_memory, needs_cpu) {
932            return None;
933        }
934        for at in picked {
935            self.runners[at] = None;
936        }
937        Some(room)
938    }
939}
940
941/// 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
942/// in use. The status explains with a plan it does not run, whose starts may never happen.
943struct Started<'plan> {
944    /// The profiles with a free slot before the plan's starts.
945    free_slots: BTreeSet<&'plan str>,
946    /// The budgets left before them.
947    before: Left,
948    /// The first job each profile, and any profile, starts a runner for.
949    by_profile: BTreeMap<&'plan str, u64>,
950    first: Option<u64>,
951}
952
953impl<'plan> Started<'plan> {
954    fn new(taken: &BTreeMap<&'plan str, Vec<bool>>, before: Left) -> Started<'plan> {
955        Started {
956            free_slots: taken
957                .iter()
958                .filter(|(_, slots)| slots.contains(&false))
959                .map(|(name, _)| *name)
960                .collect(),
961            before,
962            by_profile: BTreeMap::new(),
963            first: None,
964        }
965    }
966
967    /// The plan starts a runner for `job` in `profile`.
968    fn note(&mut self, profile: &'plan str, job: u64) {
969        self.by_profile.entry(profile).or_insert(job);
970        self.first.get_or_insert(job);
971    }
972
973    /// `reason` for a job `profile` has no slot for, unless only this plan's starts took its free slots.
974    fn for_slot(&self, profile: &str, reason: Waiting) -> Waiting {
975        match self.by_profile.get(profile) {
976            Some(older) if self.free_slots.contains(profile) => {
977                Waiting::BehindStart { job: *older }
978            }
979            _ => reason,
980        }
981    }
982
983    /// `reason` for a job whose `needs` of memory do not fit, unless they did before this plan's starts.
984    fn for_memory(&self, needs: u64, reason: Waiting) -> Waiting {
985        Self::behind(self.first, self.before.memory, needs).unwrap_or(reason)
986    }
987
988    /// `reason` for a job whose `needs` of memory the host cannot spare, unless it could before this plan's starts.
989    fn for_host(&self, needs: u64, reason: Waiting) -> Waiting {
990        Self::behind(self.first, self.before.host, needs).unwrap_or(reason)
991    }
992
993    /// `reason` for a job whose `needs` of CPU do not fit, unless they did before this plan's starts.
994    fn for_cpu(&self, needs: u64, reason: Waiting) -> Waiting {
995        Self::behind(self.first, self.before.cpu, needs).unwrap_or(reason)
996    }
997
998    fn behind(first: Option<u64>, free: Option<i64>, needs: u64) -> Option<Waiting> {
999        first
1000            .filter(|_| free.is_some_and(|free| free >= signed(needs)))
1001            .map(|job| Waiting::BehindStart { job })
1002    }
1003}
1004
1005/// Whether each slot of each profile is taken, by profile name: by a runner, closed, or its profile preparing.
1006fn taken_slots(profiles: &BTreeMap<String, Profile>) -> BTreeMap<&str, Vec<bool>> {
1007    profiles
1008        .iter()
1009        .map(|(name, profile)| {
1010            let taken = profile
1011                .slots
1012                .iter()
1013                .map(|slot| profile.preparing.is_some() || *slot != Slot::Free)
1014                .collect();
1015            (name.as_str(), taken)
1016        })
1017        .collect()
1018}
1019
1020#[cfg(test)]
1021mod tests;