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