Skip to main content

runnerd_core/
admission.rs

1//! Admission by measured peaks: a job's memory peak and average CPU predicted from the job history (`Predictor`),
2//! and the history replayed through admission by caps and by predictions, with or without a CPU budget
3//! (`simulate`), to show what each would have done with the same jobs, with the barrier `scheduler::plan` puts up for
4//! a starved job or without, and with jobs arriving when they did or after what they followed, or as they really ran
5//! (`trace`); what the host's memory leaves runners (`host`); and what all that runs counts for in the budget (`pooled`,
6//! ADR 0099). A job's memory and usual run time go by its last runs (`recent`, ADR 0070, 0097). Pure: no I/O, no clock.
7
8pub mod host;
9pub mod pooled;
10pub mod recent;
11pub mod trace;
12
13use std::cell::RefCell;
14use std::collections::{BTreeMap, BTreeSet};
15use std::time::{Duration, SystemTime};
16
17use crate::api::Spread;
18use crate::api::{Basis, HostMemory, JobPeak};
19use crate::config::{self, Config};
20use crate::scheduler::priority::{Around, Backfill, Candidate, Caps, Held, Older, Runner, Short};
21use crate::scheduler::{Barrier, Drained, Left, Pool, Scarce, Waits};
22use crate::sizing::{GRANULE, History, Measure, Ran, spread};
23use crate::time;
24use recent::{Ending, RECENT_RUNS, Recent};
25use trace::{Hazard, OOMD_UNDER, Reading, RunId, RunTrace, STEP, THROTTLES_UNDER, Trace};
26
27/// For at most this long after a run at its cap or killed for memory, in milliseconds, its job is admitted at its
28/// cap: 7 days, or until `recent::CLEAN_RUNS` clear runs. After a run past what it reserved, its job reserves its
29/// largest peak for at most as long, or until the run leaves its window.
30pub const UNPREDICTABLE_FOR: u64 = 7 * 24 * 3600 * 1000;
31
32/// From this many successful runs of its own, fewer than `[sizing] min_jobs` runs, a job reserves its own largest
33/// peak while no other copy of it is queued or running; otherwise the larger of that and its profile's p95.
34pub const OWN_RUNS: u64 = 2;
35
36/// While the slice uses this percent of its `MemoryMax` or more, measured admission starts nothing.
37pub const HIGH_WATER: u64 = 90;
38
39/// CPU predictions round up to this many millicores: a tenth of a CPU.
40pub const CPU_GRANULE: u64 = 100;
41
42/// A job as admission tells jobs apart: its repository, workflow and name.
43#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
44pub struct Key {
45    /// `owner/name`.
46    pub repository: String,
47    /// The workflow's name, when known.
48    pub workflow: Option<String>,
49    /// The job's name in the workflow.
50    pub name: String,
51}
52
53impl Key {
54    /// A finished run's key.
55    pub fn of(run: &Ran) -> Key {
56        Key {
57            repository: run.repository.clone(),
58            workflow: run.workflow.clone(),
59            name: run.name.clone(),
60        }
61    }
62}
63
64/// Whether other copies of a job may run beside the one predicted: queued with it, or running. A few light runs
65/// say little about a burst of copies, after a cache was invalidated, so only one copy at a time goes by them.
66#[derive(Debug, Clone, Copy, PartialEq, Eq)]
67pub enum Copies {
68    /// No other copy is queued or running.
69    Alone,
70    /// Another copy is queued or running.
71    Several,
72}
73
74/// The memory admission reserves for a job, at most its cap, and what it goes by.
75#[derive(Debug, Clone, Copy, PartialEq, Eq)]
76pub struct Prediction {
77    /// Bytes.
78    pub memory: u64,
79    /// Why that much.
80    pub basis: Basis,
81}
82
83/// The CPU a runner reserves for a job, in millicores, at most its profile's `cpus`, and what it goes by.
84#[derive(Debug, Clone, Copy, PartialEq, Eq)]
85pub struct CpuPrediction {
86    /// Millicores.
87    pub cpu: u64,
88    /// Why that much: `Basis::Job`, `Profile`, `ProfileMax` or `Cap`.
89    pub basis: Basis,
90}
91
92/// The CPU averages of a set of runs, sorted, and how many of those runs succeeded.
93#[derive(Debug, Clone, Default)]
94struct Averages {
95    sorted: Vec<u64>,
96    succeeded: u64,
97}
98
99impl Averages {
100    fn add(&mut self, average: u64, succeeded: bool) {
101        let at = self.sorted.partition_point(|known| *known <= average);
102        self.sorted.insert(at, average);
103        self.succeeded += u64::from(succeeded);
104    }
105
106    fn runs(&self) -> u64 {
107        self.sorted.len() as u64
108    }
109
110    fn p95(&self) -> u64 {
111        spread(self.sorted.clone()).p95
112    }
113
114    fn max(&self) -> u64 {
115        self.sorted.last().copied().unwrap_or(0)
116    }
117}
118
119/// A job in one profile, as the predictor keeps its CPU averages.
120#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
121struct InProfile {
122    key: Key,
123    profile: String,
124}
125
126impl InProfile {
127    fn new(key: &Key, profile: &str) -> InProfile {
128        InProfile {
129            key: key.clone(),
130            profile: profile.to_owned(),
131        }
132    }
133}
134
135/// Predicts a job's peak from the runs it learned.
136#[derive(Debug, Clone)]
137pub struct Predictor {
138    margin: u32,
139    min_jobs: u32,
140    /// Each job's last runs, by job and the profile it ran in (ADR 0070).
141    recent: Recent,
142    /// The CPU averages of the runs that have one, apart from the peaks: a run whose peak says nothing of its
143    /// memory still says what CPU it used, and must not make its job known to memory predictions.
144    cpu_jobs: BTreeMap<InProfile, Averages>,
145    cpu_profiles: BTreeMap<String, Averages>,
146}
147
148impl Predictor {
149    /// A predictor that knows no run yet, with `[sizing]`'s margin and minimum runs.
150    pub fn new(rules: &config::Sizing) -> Predictor {
151        Predictor {
152            margin: rules.margin,
153            min_jobs: rules.min_jobs,
154            recent: Recent::new(RECENT_RUNS.max(u64::from(rules.min_jobs))),
155            cpu_jobs: BTreeMap::new(),
156            cpu_profiles: BTreeMap::new(),
157        }
158    }
159
160    /// A predictor that learned every row of `history`, in the order they finished, each under the cap its
161    /// container had, else `cap_of(profile)`: what the daemon reads every minute, and again after a restart.
162    pub fn read(
163        rules: &config::Sizing,
164        history: &History,
165        cap_of: impl Fn(&str) -> Option<u64>,
166    ) -> Predictor {
167        let mut predictor = Predictor::new(rules);
168        predictor.read_until(history, u64::MAX, cap_of);
169        predictor
170    }
171
172    /// Learns the rows of `history` that ended before `until` (ms), in the order they finished, as `read` does.
173    fn read_until(&mut self, history: &History, until: u64, cap_of: impl Fn(&str) -> Option<u64>) {
174        for (run, ending) in recent::rows(history) {
175            let cap = run
176                .memory_cap
177                .or_else(|| cap_of(&run.profile))
178                .unwrap_or(u64::MAX);
179            let at = recent::finished(run);
180            if at >= until {
181                break;
182            }
183            match ending {
184                Ending::Finished => self.learn(run, &run.profile, cap, at),
185                Ending::Cancelled => self.mark(run, &run.profile, cap, at),
186            }
187        }
188    }
189
190    /// Learns a finished run of `profile` that ended at `at` (ms), having run under `cap`: its peak, how it ended,
191    /// and its CPU. Runs must come in the order they finished (`recent::Recent::read`).
192    pub fn learn(&mut self, run: &Ran, profile: &str, cap: u64, at: u64) {
193        self.recent.read(run, profile, Ending::Finished, cap, at);
194        self.learn_cpu(run, profile);
195    }
196
197    /// Learns the CPU a finished run of `profile` used, without its peak.
198    pub fn learn_cpu(&mut self, run: &Ran, profile: &str) {
199        let Some(average) = run.cpu_average else {
200            return;
201        };
202        self.cpu_profiles
203            .entry(profile.to_owned())
204            .or_default()
205            .add(average, run.succeeded);
206        self.cpu_jobs
207            .entry(InProfile::new(&Key::of(run), profile))
208            .or_default()
209            .add(average, run.succeeded);
210    }
211
212    /// The CPU to reserve for a run of `key` in `profile`, whose `cpus` are `cap` millicores: the job's average
213    /// CPU (its CPU time over its run time), by the same fallbacks as memory without the margin. CPU is shared, not
214    /// a kill limit, so neither a run at its cap nor copies of the job beside it change it.
215    pub fn predict_cpu(&self, key: &Key, profile: &str, cap: u64) -> CpuPrediction {
216        let job = self.cpu_jobs.get(&InProfile::new(key, profile));
217        let min_jobs = u64::from(self.min_jobs);
218        let peers = self
219            .cpu_profiles
220            .get(profile)
221            .filter(|peers| peers.runs() >= min_jobs);
222        let (cpu, basis) = match (job.filter(|job| job.runs() > 0), peers) {
223            (Some(job), _) if job.runs() >= min_jobs => (
224                job.p95(),
225                Basis::Job {
226                    runs: job.runs(),
227                    peak: JobPeak::P95,
228                },
229            ),
230            (Some(job), Some(_)) if job.succeeded >= OWN_RUNS => (
231                job.max(),
232                Basis::Job {
233                    runs: job.runs(),
234                    peak: JobPeak::Largest,
235                },
236            ),
237            (Some(job), Some(peers)) => (
238                job.max().max(peers.p95()),
239                Basis::Profile { runs: peers.runs() },
240            ),
241            (None, Some(peers)) => (peers.max(), Basis::ProfileMax { runs: peers.runs() }),
242            _ => (cap, Basis::Cap),
243        };
244        CpuPrediction {
245            cpu: cpu
246                .div_ceil(CPU_GRANULE)
247                .saturating_mul(CPU_GRANULE)
248                .clamp(CPU_GRANULE, cap.max(CPU_GRANULE)),
249            basis,
250        }
251    }
252
253    /// How long a run of `key` in `profile` usually keeps its runner, if its runs say (`recent::JobRuns::usual`).
254    pub fn usual(&self, key: &Key, profile: &str) -> Option<Duration> {
255        self.recent.job(key, profile)?.usual()
256    }
257
258    /// The longest `usual` of `keys`, the queued jobs of a pool in `profile`, since GitHub may give its runner any of
259    /// them; `None` if any has none, or there is none.
260    pub fn longest_usual(
261        &self,
262        keys: impl IntoIterator<Item = Key>,
263        profile: &str,
264    ) -> Option<Duration> {
265        let usual: Option<Vec<Duration>> = keys
266            .into_iter()
267            .map(|key| self.usual(&key, profile))
268            .collect();
269        usual?.into_iter().max()
270    }
271
272    /// Learns a cancelled run of `profile`: how it ended, and its peak only when it met its cap. A run that met
273    /// its cap or was killed for memory holds its job in that profile at its cap (`Ran::capped`), a peak past what
274    /// it reserved makes it reserve its largest peak while that run is in its window.
275    pub fn mark(&mut self, run: &Ran, profile: &str, cap: u64, at: u64) {
276        self.recent.read(run, profile, Ending::Cancelled, cap, at);
277    }
278
279    /// The memory to reserve for a run of `key` in `profile`, whose cap is `cap`, at `now` (ms), with `copies`
280    /// of it beside.
281    pub fn predict(
282        &self,
283        key: &Key,
284        profile: &str,
285        cap: u64,
286        now: u64,
287        copies: Copies,
288    ) -> Prediction {
289        let job = self.recent.job(key, profile);
290        if let Some(hold) = job.and_then(|job| job.held(now, Some(UNPREDICTABLE_FOR))) {
291            return Prediction {
292                memory: cap,
293                basis: Basis::Unpredictable {
294                    until: hold.at.saturating_add(UNPREDICTABLE_FOR) / 1000,
295                },
296            };
297        }
298        let min_jobs = u64::from(self.min_jobs);
299        let peers = self.recent.profile(profile);
300        let peers_runs = peers.len() as u64;
301        let overran = job.and_then(|job| {
302            job.overruns(now, UNPREDICTABLE_FOR)
303                .fold(None, |most: Option<(u64, u64)>, overrun| {
304                    let until = overrun.at.saturating_add(UNPREDICTABLE_FOR);
305                    Some(most.map_or((overrun.peak, until), |(peak, last)| {
306                        (peak.max(overrun.peak), last.max(until))
307                    }))
308                })
309        });
310        let (memory, basis) = match (job, peers_runs >= min_jobs) {
311            // Seen only cancelled, so its peaks say nothing.
312            (Some(job), _) if job.runs() == 0 => (cap, Basis::Cap),
313            (Some(job), _) if let Some((peak, until)) = overran => (
314                self.with_margin(job.max().max(peak)),
315                Basis::Overran {
316                    until: until / 1000,
317                },
318            ),
319            (Some(job), _) if job.runs() >= min_jobs => (
320                self.with_margin(spread(job.peaks().to_vec()).p95),
321                Basis::Job {
322                    runs: job.runs(),
323                    peak: JobPeak::P95,
324                },
325            ),
326            (Some(job), true) if job.succeeded() >= OWN_RUNS && copies == Copies::Alone => (
327                self.with_margin(job.max()),
328                Basis::Job {
329                    runs: job.runs(),
330                    peak: JobPeak::Largest,
331                },
332            ),
333            (Some(job), true) => (
334                self.with_margin(job.max().max(spread(peers.to_vec()).p95)),
335                Basis::Profile { runs: peers_runs },
336            ),
337            // A job never seen may be the profile's heaviest.
338            (None, true) => (
339                self.with_margin(peers.last().copied().unwrap_or(0)),
340                Basis::ProfileMax { runs: peers_runs },
341            ),
342            _ => (cap, Basis::Cap),
343        };
344        Prediction {
345            memory: memory.min(cap),
346            basis,
347        }
348    }
349    /// `peak` plus the margin, rounded up to 256M.
350    fn with_margin(&self, peak: u64) -> u64 {
351        let memory = peak.saturating_add(peak.saturating_mul(u64::from(self.margin)) / 100);
352        memory
353            .div_ceil(GRANULE)
354            .saturating_mul(GRANULE)
355            .max(GRANULE)
356    }
357}
358
359/// How a replay admits a queued job.
360#[derive(Debug, Clone, Copy, PartialEq, Eq)]
361pub enum Policy {
362    /// When a slot is free and the caps of the running jobs and its own fit the budget: what runnerd does now.
363    Caps,
364    /// As the daemon admits: when a slot is free, the running jobs (each at the larger of its prediction and its
365    /// peak) and the largest prediction among the repository's waiting jobs fit the budget, and the running jobs'
366    /// peaks are under `HIGH_WATER` percent of it. A started job then reserves its own prediction.
367    Measured,
368}
369
370/// Whether a replay puts up the barrier `scheduler::plan` does for a starved job (ADR 0096).
371#[derive(Debug, Clone, Copy, PartialEq, Eq)]
372pub enum Barriers {
373    /// As the daemon runs: a barrier, and the younger jobs `priority::Backfill` lets start behind it (ADR 0097).
374    On,
375    /// A barrier nothing younger starts behind: what to compare with.
376    Strict,
377    /// A job that does not fit lets every later one past, however long it waited: what to compare with.
378    Off,
379}
380
381/// When a replay's jobs arrive.
382#[derive(Debug, Clone, Copy, PartialEq, Eq)]
383pub enum Arrivals {
384    /// When they were queued, whatever the replay did to the jobs before them.
385    AsQueued,
386    /// A job that queued after another of its run attempt ended follows it: it arrives as long after the replayed end
387    /// of the last such job as it did after the real one. The history does not keep a job's `needs`, so this reads them
388    /// from the times. A job that follows one never started does not arrive.
389    AfterNeeds,
390}
391
392/// How a replay goes.
393#[derive(Debug, Clone, Copy)]
394pub struct Replaying<'known> {
395    /// The barrier for a starved job.
396    pub barriers: Barriers,
397    /// When jobs arrive.
398    pub arrivals: Arrivals,
399    /// The history to know from the start, as the daemon does by the time these jobs queue: its rows that ended before
400    /// the first job arrives. `None`, the replay knows only the runs it finishes.
401    pub known: Option<&'known History>,
402    /// How the jobs really ran. With it each job uses what its samples say from its replayed start, is known only when
403    /// the daemon could name it, and the host's memory bounds what starts. `None`, each holds its peak for its whole run.
404    pub trace: Option<&'known Trace>,
405    /// The most the pooled count may take off the plain one (`pooled::Snapshot::most`); read only with a `trace`.
406    pub most_credit: u64,
407    /// What of the credit the host's bound leaves out: all of it, `u64::MAX`, as the daemon's reads the plain count.
408    /// Less shows what a host bound that spent the credit would have done (ADR 0099).
409    pub host_hold: u64,
410    /// Whether `Backfill` expects what the credit may still give, as the daemon does.
411    pub credit_room: CreditRoom,
412    /// What holds the host's larger margin up.
413    pub band: Band,
414}
415
416/// What holds up the host's larger margin in a replay.
417#[derive(Debug, Clone, Copy, PartialEq, Eq)]
418pub enum Band {
419    /// As the daemon does: jobs wait for the host and none fits the plain margin (`host::short`).
420    NoWaiterFits,
421    /// To show what that gives (ADR 0102): any job that waits for the host.
422    AnyWaiter,
423}
424
425/// Whether a replay's `Backfill` reads `Budget::credit_room`.
426#[derive(Debug, Clone, Copy, PartialEq, Eq)]
427pub enum CreditRoom {
428    /// As the daemon does.
429    Counted,
430    /// To show what that keeps: an owner may then start before the time its younger jobs were held to.
431    LeftOut,
432}
433
434impl From<Barriers> for Replaying<'_> {
435    fn from(barriers: Barriers) -> Self {
436        Replaying {
437            barriers,
438            arrivals: Arrivals::AsQueued,
439            known: None,
440            trace: None,
441            most_credit: 0,
442            host_hold: u64::MAX,
443            credit_room: CreditRoom::Counted,
444            band: Band::NoWaiterFits,
445        }
446    }
447}
448
449/// What a replay did with one pool's jobs.
450#[derive(Debug, Clone, Default, PartialEq, Eq)]
451pub struct PoolReplay {
452    /// Seconds from queued to started, of each job that started.
453    pub waits: Vec<u64>,
454    /// The jobs the replay never started.
455    pub never_started: u64,
456}
457
458impl PoolReplay {
459    /// The spread of `waits`.
460    pub fn wait(&self) -> Spread {
461        spread(self.waits.clone())
462    }
463}
464
465/// What a replay did with one attempt of a workflow run: the closest fact it has to a pull request's checks finishing.
466#[derive(Debug, Clone, Default, PartialEq, Eq)]
467pub struct RunReplay {
468    /// Seconds from its first job's arrival to its last job's end.
469    pub took: u64,
470    /// The profiles its jobs ran in.
471    pub profiles: BTreeSet<String>,
472}
473
474/// A run attempt as a replay tells them apart.
475type RunKey = (String, u64, u32);
476
477/// The jobs a replay started behind a barrier (ADR 0097).
478#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
479pub struct Backfilled {
480    /// How many.
481    pub jobs: u64,
482    /// Of those, how many ran past the usual run time they passed by.
483    pub overran: u64,
484    /// The furthest one did, in seconds.
485    pub most_overrun: u64,
486}
487
488/// What a replay did with the history's jobs.
489#[derive(Debug, Clone, PartialEq, Eq)]
490pub struct Replay {
491    /// The jobs replayed: finished ones of a configured profile.
492    pub jobs: u64,
493    /// Of those, the ones the policy never started: more than the budget holds.
494    pub never_started: u64,
495    /// Seconds from queued to started.
496    pub wait: Spread,
497    /// The mean of those, in seconds.
498    pub mean_wait: u64,
499    /// The most jobs that ran at once.
500    pub most_running: u64,
501    /// The most memory, in bytes, the running jobs' peaks and the mirror add up to at one moment: as if every
502    /// running job peaked at once, which is more than the slice ever holds. Not a bound on the daemon, which can
503    /// overlap more: it sees what jobs use, less than their peaks while they warm up, and the replay leaves out
504    /// start latency, seeds, shells and cancelled jobs.
505    pub worst_overlap: u64,
506    /// Seconds from the first job queued to the last one finished.
507    pub makespan: u64,
508    /// Jobs whose peak was above what admission reserved for them when they ended.
509    pub under_predicted: u64,
510    /// How many times the high-water mark held a job back that the predictions had room for.
511    pub held_back: u64,
512    /// How many times the CPU budget held a job back that memory and its slots had room for.
513    pub cpu_held: u64,
514    /// The most CPU, in millicores, the running jobs' averages add up to at one moment.
515    pub worst_cpu: u64,
516    /// By pool, the jobs that ran in it.
517    pub pools: BTreeMap<Pool, PoolReplay>,
518    /// What the running jobs took of the budget over the replay, in byte-milliseconds.
519    pub charged: u128,
520    /// The budget over the replay, in byte-milliseconds; 0 without one. `charged` over it is the busy share.
521    pub capacity: u128,
522    /// How long a barrier stood, in milliseconds.
523    pub barrier_for: u64,
524    /// What the budget had free while a barrier stood, in byte-milliseconds: at most what the barrier cost, as some of
525    /// it no younger job could have used.
526    pub withheld: u128,
527    /// By run attempt, what the replay did with those whose jobs started.
528    pub runs: Vec<RunReplay>,
529    /// What started behind a barrier.
530    pub backfilled: Backfilled,
531    /// How long jobs waited, added up, for the slice's budget, in ms; only with a trace.
532    pub slice_waited: u64,
533    /// How long jobs the slice's budget had room for waited for the host's memory, added up, in ms; only with a trace.
534    pub host_waited: u64,
535    /// What the replay found of a pooled count's risks; only with a trace.
536    pub hazard: Hazard,
537}
538
539/// A job the replay started.
540struct Running<'run> {
541    run: &'run Ran,
542    /// Its place in the jobs replayed.
543    job: u64,
544    profile: &'run str,
545    /// When it started, in ms.
546    started: u64,
547    ends: u64,
548    /// When it usually ends by, in ms, if it started behind a barrier.
549    backfilled: Option<u64>,
550    reserved: u64,
551    peak: u64,
552    /// The CPU it reserves, in millicores.
553    cpu: u64,
554    /// Its job.
555    key: Key,
556    /// What its reservation goes by.
557    basis: Basis,
558    /// What it reserves until its job is known: its pool's largest prediction when it started.
559    starting: u64,
560    /// How it ran; `None` without a trace or a run the trace has no samples of.
561    trace: Option<&'run RunTrace>,
562}
563
564/// Replays `jobs` through `policy`: each arrives as `how` says and runs as long as it ran, in a profile with
565/// `slots` (by name; the config's where absent) under the slice's `memory_max`. Jobs start as soon as the policy
566/// admits them, in `jobs`' order, which is the job IDs' as the history reads them and `scheduler::plan` serves them: a
567/// job that does not fit lets a later one past, until it waited long enough under `how`'s barriers and no later one
568/// starts before its pool does, but those `priority::Backfill` lets by. The replay looks again at each such limit, so a
569/// quiet queue reaches it too. Usual run times come from `how`'s known runs and those finished before each moment, as
570/// predictions do.
571/// Measured admission predicts from the runs finished before it decides, as the daemon would, and holds each
572/// running job at its peak for its whole run, which the daemon does not see. A job with copies waiting or running
573/// beside it is predicted as one with `Copies::Several`. Each moment, the running jobs are predicted again, the
574/// first running copy of a job going by its own runs, as the daemon does each tick. Unlike the daemon, the replay
575/// knows a job from its start: it never sees a runner whose job is not known yet, and the order jobs started
576/// stands for the daemon's slot order.
577///
578/// With a `cpu_budget` in millicores, a job also starts only when the CPU the running jobs reserve and its own fit
579/// it: by caps, each its profile's `cpus`; measured, each its predicted average (`Predictor::predict_cpu`), at most
580/// the budget. The replay holds each job's run time whatever the CPU it shares: it shows what admission holds back,
581/// not how much a busy CPU slows the jobs.
582///
583/// With a `Replaying::trace`, the replay runs as the daemon counts: each job uses what its own samples say, shifted to
584/// its replayed start, and takes the larger of that and what it reserves; it reserves its pool's largest prediction
585/// until the daemon could name its job; a stale sample counts at its cap; the budget goes by `pooled::count`; the host's
586/// recorded programs bound what starts, with the margin of `host`; and the mark reads the runners' use with the trace's
587/// overhead. It looks every `trace::STEP` and plans every `[host] poll_interval` and at each arrival and end.
588pub fn simulate<'known>(
589    config: &Config,
590    memory_max: Option<u64>,
591    cpu_budget: Option<u64>,
592    jobs: &[Ran],
593    policy: Policy,
594    slots: &BTreeMap<String, u32>,
595    how: impl Into<Replaying<'known>>,
596) -> Replay {
597    let Replaying {
598        barriers,
599        arrivals,
600        known,
601        trace,
602        most_credit,
603        host_hold,
604        credit_room,
605        band,
606    } = how.into();
607    let mirror = config.mirror_memory();
608    let budget = memory_max.map(|max| max.saturating_sub(mirror));
609    let queue = replayable(config, jobs);
610    let followers = match arrivals {
611        Arrivals::AsQueued => BTreeMap::new(),
612        Arrivals::AfterNeeds => followers(&queue),
613    };
614    let following: BTreeSet<u64> = followers
615        .values()
616        .flatten()
617        .map(|follower| queue[follower.at].job)
618        .collect();
619    let arriving = (0_usize..)
620        .zip(&queue)
621        .filter(|(_, queued)| !following.contains(&queued.job))
622        .map(|(at, queued)| (queued.run.queued_at, at))
623        .collect();
624    let mut predictor = Predictor::new(&config.sizing);
625    if let (Some(known), Some(first)) = (known, queue.first()) {
626        predictor.read_until(known, first.run.queued_at, |profile| {
627            config.profiles.get(profile).map(|limits| limits.memory.0)
628        });
629    }
630    let replayer = Replayer {
631        config,
632        budget,
633        cpu_budget,
634        policy,
635        slots,
636        predictor,
637        running: Vec::new(),
638        waits: Vec::new(),
639        most_running: 0,
640        worst_overlap: 0,
641        last_end: 0,
642        under_predicted: 0,
643        held_back: 0,
644        cpu_held: 0,
645        worst_cpu: 0,
646        barriers,
647        pool_waits: BTreeMap::new(),
648        pools: BTreeMap::new(),
649        barrier: None,
650        backfill: None,
651        usual: BTreeMap::new(),
652        arriving,
653        followers,
654        started: Vec::new(),
655        runs: BTreeMap::new(),
656        backfilled: Backfilled::default(),
657        moment: queue.first().map_or(0, |queued| queued.run.queued_at),
658        charged: 0,
659        capacity: 0,
660        barrier_for: 0,
661        withheld: 0,
662        memory_max,
663        mirror,
664        trace,
665        most_credit,
666        host_hold,
667        expects_credit: credit_room,
668        short: false,
669        next_plan: 0,
670        needs: RefCell::new(BTreeMap::new()),
671        held_for_slice: 0,
672        held_for_host: 0,
673        host_needs: Vec::new(),
674        band,
675        slice_waited: 0,
676        host_waited: 0,
677        hazard: Hazard::default(),
678        last_credit: 0,
679        cohorts: Vec::new(),
680    };
681    replayer.play(&queue)
682}
683
684/// `jobs` a replay can run, in the order they queued: those of a known profile with a run time.
685fn replayable<'run>(config: &Config, jobs: &'run [Ran]) -> Vec<Queued<'run>> {
686    let mut queue: Vec<Queued<'_>> = (0_u64..)
687        .zip(jobs)
688        .filter(|(_, run)| config.profiles.contains_key(&run.profile))
689        .filter(|(_, run)| matches!((run.started_at, run.finished_at), (Some(start), Some(end)) if end >= start))
690        .map(|(job, run)| Queued {
691            job,
692            run,
693            arrived: run.queued_at,
694        })
695        .collect();
696    queue.sort_by_key(|queued| queued.run.queued_at);
697    queue
698}
699
700/// A job waiting in a replay.
701#[derive(Clone, Copy)]
702struct Queued<'run> {
703    /// Its place in the jobs replayed, which stands for its ID: the order `scheduler::plan` serves jobs in.
704    job: u64,
705    run: &'run Ran,
706    /// When it arrived in the replay, in ms.
707    arrived: u64,
708}
709
710/// A job that follows another in its run attempt.
711#[derive(Clone, Copy)]
712struct Follower {
713    /// Its place in the replay's queue.
714    at: usize,
715    /// How long after the job it follows it queued, in ms.
716    gap: u64,
717}
718
719/// By the job each follows, the jobs of `queue` that queued after another job of their run attempt ended: a job
720/// follows the last that ended before it queued, as GitHub queues a job once the last of its `needs` ends. Only a job
721/// queued earlier can be followed, so nothing follows itself through a job that took no time.
722fn followers(queue: &[Queued<'_>]) -> BTreeMap<u64, Vec<Follower>> {
723    let mut attempts: BTreeMap<RunKey, Vec<usize>> = BTreeMap::new();
724    for (at, queued) in queue.iter().enumerate() {
725        attempts.entry(run_key(queued.run)).or_default().push(at);
726    }
727    let mut followers: BTreeMap<u64, Vec<Follower>> = BTreeMap::new();
728    for attempt in attempts.values() {
729        for &at in attempt {
730            let queued_at = queue[at].run.queued_at;
731            let followed = attempt
732                .iter()
733                .map(|other| &queue[*other])
734                .filter(|other| other.run.queued_at < queued_at)
735                .filter_map(|other| Some((other.run.finished_at?, other.job)))
736                .filter(|(ended, _)| *ended <= queued_at)
737                .max();
738            if let Some((ended, job)) = followed {
739                let gap = queued_at - ended;
740                followers.entry(job).or_default().push(Follower { at, gap });
741            }
742        }
743    }
744    followers
745}
746
747/// The run attempt `run` belongs to.
748fn run_key(run: &Ran) -> RunKey {
749    (run.repository.clone(), run.run_id, run.run_attempt)
750}
751
752/// What a replay saw of a run attempt so far.
753struct RunSpan {
754    first_arrival: u64,
755    last_end: u64,
756    profiles: BTreeSet<String>,
757}
758
759impl RunSpan {
760    fn replay(self) -> RunReplay {
761        RunReplay {
762            took: self.last_end.saturating_sub(self.first_arrival) / 1000,
763            profiles: self.profiles,
764        }
765    }
766}
767
768/// The pool a job ran in.
769fn pool_of(run: &Ran) -> Pool {
770    Pool {
771        repository: run.repository.clone(),
772        profile: run.profile.clone(),
773    }
774}
775
776/// What a job started at a moment of a replay reserves.
777struct Admitted {
778    reserved: u64,
779    /// What it takes of the budget before its job is known.
780    starting: u64,
781    /// What `reserved` goes by.
782    basis: Basis,
783    peak: u64,
784    /// Millicores.
785    cpu: u64,
786}
787
788/// Whether `one` and `other` are the same job, as `Key` tells them apart. A long queue asks this of every pair of its
789/// jobs in every pass, too often for keys to be built.
790fn same_job(one: &Ran, other: &Ran) -> bool {
791    one.name == other.name && one.repository == other.repository && one.workflow == other.workflow
792}
793
794/// What a job's runner starts with at a moment of a replay.
795struct Starting {
796    /// What it takes of the budget before its job is known.
797    memory: u64,
798    /// What it reserves once it is.
799    reserved: u64,
800    /// What that goes by.
801    basis: Basis,
802    /// What it takes of the CPU budget, in millicores.
803    cpu: u64,
804}
805
806/// Why a job did not start at a moment of a replay.
807enum Refused {
808    /// Every slot of its profile is taken.
809    Slot,
810    /// It does not fit the budget named.
811    Budget(Short),
812    /// It fits the slice's budget but not what the host's memory leaves it.
813    Host(Short),
814    /// The slice is at the high-water mark, though the job fits the budget.
815    HighWater(Short),
816}
817
818/// A replay's state between two moments.
819struct Replayer<'run> {
820    config: &'run Config,
821    budget: Option<u64>,
822    cpu_budget: Option<u64>,
823    policy: Policy,
824    slots: &'run BTreeMap<String, u32>,
825    predictor: Predictor,
826    running: Vec<Running<'run>>,
827    waits: Vec<u64>,
828    most_running: u64,
829    worst_overlap: u64,
830    last_end: u64,
831    under_predicted: u64,
832    held_back: u64,
833    cpu_held: u64,
834    worst_cpu: u64,
835    barriers: Barriers,
836    /// What each pool's next job waited for, as the engine keeps it.
837    pool_waits: BTreeMap<Pool, Waits>,
838    pools: BTreeMap<Pool, PoolReplay>,
839    /// The barrier the last pass ended with.
840    barrier: Option<Barrier>,
841    /// The room behind it, under `Barriers::On`.
842    backfill: Option<Backfill<'run>>,
843    /// Each pool's `Predictor::longest_usual` as this pass found it, read once as a plan reads it.
844    usual: BTreeMap<Pool, Option<Duration>>,
845    /// The jobs not arrived yet whose arrival is known, by when, as places in the queue.
846    arriving: BTreeSet<(u64, usize)>,
847    /// What arrives once a job ends, by the job.
848    followers: BTreeMap<u64, Vec<Follower>>,
849    /// The jobs started.
850    started: Vec<u64>,
851    runs: BTreeMap<RunKey, RunSpan>,
852    backfilled: Backfilled,
853    /// The moment replayed last, in ms.
854    moment: u64,
855    charged: u128,
856    capacity: u128,
857    barrier_for: u64,
858    withheld: u128,
859    memory_max: Option<u64>,
860    mirror: u64,
861    trace: Option<&'run Trace>,
862    most_credit: u64,
863    host_hold: u64,
864    expects_credit: CreditRoom,
865    /// Whether the larger margin stands for the next plan (`band_stands`).
866    short: bool,
867    /// When the next plan with no arrival or end is, in ms.
868    next_plan: u64,
869    /// What each pool's next runner starts with this pass, with a trace: a long queue asks it of every job, every plan.
870    needs: RefCell<BTreeMap<Pool, Need>>,
871    /// How many jobs the last pass left waiting for the slice's budget.
872    held_for_slice: u64,
873    /// How many it left waiting for the host's memory alone.
874    held_for_host: u64,
875    /// What each of those needs of the host.
876    host_needs: Vec<u64>,
877    band: Band,
878    slice_waited: u64,
879    host_waited: u64,
880    hazard: Hazard,
881    /// The credit at the last look.
882    last_credit: u64,
883    /// The sets of runners that ran when a job started, and the count that let it, while one of them runs.
884    cohorts: Vec<Cohort>,
885}
886
887/// What a pool's next runner takes of the budgets before its job is known.
888#[derive(Clone, Copy)]
889struct Need {
890    memory: u64,
891    /// Millicores.
892    cpu: u64,
893}
894
895/// The runners a start left running, and the count it went by.
896struct Cohort {
897    /// Their places in the jobs replayed.
898    jobs: Vec<u64>,
899    /// What they counted, in bytes.
900    count: u64,
901}
902
903impl<'run> Replayer<'run> {
904    /// Runs the replay to its end: each moment jobs arrive or end, a limit passes or the samples are read.
905    fn play(mut self, queue: &[Queued<'run>]) -> Replay {
906        let mut waiting: Vec<Queued<'_>> = Vec::new();
907        loop {
908            let arrival = self.arriving.first().map(|(arrives, _)| *arrives);
909            let end = self.running.iter().map(|running| running.ends).min();
910            let event = [arrival, end, self.next_limit()]
911                .into_iter()
912                .flatten()
913                .min();
914            let Some(now) = [event, self.next_look(&waiting)]
915                .into_iter()
916                .flatten()
917                .min()
918            else {
919                break;
920            };
921            self.account(now);
922            self.finish(now);
923            if event != Some(now) && !self.plans_at(now) {
924                continue;
925            }
926            self.rereserve(now);
927            while let Some(&(arrived, at)) =
928                self.arriving.first().filter(|(arrives, _)| *arrives <= now)
929            {
930                self.arriving.remove(&(arrived, at));
931                waiting.push(Queued {
932                    arrived,
933                    ..queue[at]
934                });
935            }
936            // By arrival, as IDs follow queue time in the daemon: a job that follows a delayed one queues after what arrived
937            // meanwhile, though its ID in the history is older.
938            waiting.sort_by_key(|queued| (queued.arrived, queued.job));
939            self.pass(&mut waiting, now);
940            self.note_worst(self.mirror);
941        }
942        self.replay(queue)
943    }
944
945    /// The next moment to read the samples, in ms, with a trace and something to read: a job that ran, or one waiting
946    /// while the host's readings go on.
947    fn next_look(&self, waiting: &[Queued<'run>]) -> Option<u64> {
948        let trace = self.trace?;
949        let waits = !waiting.is_empty() && self.moment < trace.ends();
950        (!self.running.is_empty() || waits).then_some(self.moment + STEP)
951    }
952
953    /// Whether a plan with no arrival or end runs at `now`; if so, the next is a poll later.
954    fn plans_at(&mut self, now: u64) -> bool {
955        if now < self.next_plan {
956            return false;
957        }
958        let poll = u64::try_from(self.config.host.poll_interval.as_millis()).unwrap_or(u64::MAX);
959        self.next_plan = now.saturating_add(poll);
960        true
961    }
962
963    /// The next moment a pool's wait reaches its limit, in ms.
964    fn next_limit(&self) -> Option<u64> {
965        self.pool_waits
966            .values()
967            .flat_map(Waits::deadlines)
968            .map(time::ms)
969            .filter(|limit| *limit > self.moment)
970            .min()
971    }
972
973    /// Adds what ran from the last moment to `now`, which is what the last pass left.
974    fn account(&mut self, now: u64) {
975        let span = now.saturating_sub(self.moment);
976        self.look(span);
977        let taken = self.taken();
978        self.charged += u128::from(taken) * u128::from(span);
979        if let Some(budget) = self.budget {
980            self.capacity += u128::from(budget) * u128::from(span);
981            if self.barrier.is_some() {
982                self.withheld += u128::from(budget.saturating_sub(taken)) * u128::from(span);
983            }
984        }
985        if self.barrier.is_some() {
986            self.barrier_for += span;
987        }
988        self.moment = now;
989    }
990
991    /// With a trace, notes what the last `span` ms held: the waits, the slice and the host against their lines, what
992    /// started runners came to use, and what became of the credit.
993    fn look(&mut self, span: u64) {
994        let Some(trace) = self.trace else {
995            return;
996        };
997        self.slice_waited += self.held_for_slice * span;
998        self.host_waited += self.held_for_host * span;
999        if self.running.is_empty() {
1000            self.last_credit = 0;
1001            return;
1002        }
1003        let slice = self.slice();
1004        let host_slice = self.used_now() + trace.host_overhead;
1005        let hazard = &mut self.hazard;
1006        hazard.slice_peak = hazard.slice_peak.max(slice);
1007        hazard.active += span;
1008        if let Some(max) = self.memory_max {
1009            let mark = max / 100 * HIGH_WATER;
1010            hazard.over_mark.note(slice.checked_sub(mark), span);
1011            hazard.over_max.note(slice.checked_sub(max), span);
1012        }
1013        if let Some(outside) = trace.outside_at(self.moment) {
1014            let available = trace
1015                .total
1016                .saturating_sub(outside)
1017                .saturating_sub(host_slice);
1018            hazard.under_throttling += span * u64::from(available < THROTTLES_UNDER);
1019            hazard.under_oomd += span * u64::from(available < OOMD_UNDER);
1020            hazard.in_band += span * u64::from(self.short);
1021            hazard.lowest_available = Some(
1022                hazard
1023                    .lowest_available
1024                    .map_or(available, |lowest| lowest.min(available)),
1025            );
1026        }
1027        let count = self.count();
1028        let hazard = &mut self.hazard;
1029        hazard.credit += u128::from(count.credit) * u128::from(span);
1030        hazard.most_credit = hazard.most_credit.max(count.credit);
1031        if count.credit < self.last_credit {
1032            hazard.credit_falls += 1;
1033            let before = pooled::Count {
1034                credit: self.last_credit,
1035                ..count
1036            };
1037            self.hazard.overdrawn += u64::from(self.overdrawn(before, count));
1038        }
1039        self.last_credit = count.credit;
1040        self.note_unfunded(span);
1041    }
1042
1043    /// Whether the fall from `before` to `now` left the count past a budget it was within: `MemoryMax` or the host's
1044    /// limit, each read as it reads the count.
1045    fn overdrawn(&self, before: pooled::Count, now: pooled::Count) -> bool {
1046        let max = self.memory_max.unwrap_or(u64::MAX);
1047        let host = self
1048            .host_memory()
1049            .map_or(u64::MAX, |memory| host::limit(&memory, self.short));
1050        (now.pooled() > max && before.pooled() <= max)
1051            || (self.hosted(now) > host && self.hosted(before) <= host)
1052    }
1053
1054    /// What the host's limit reads of `count`.
1055    fn hosted(&self, count: pooled::Count) -> u64 {
1056        count.plain - count.credit.saturating_sub(self.host_hold)
1057    }
1058
1059    /// Notes how far what any start left running uses now stands past the count that let it start.
1060    fn note_unfunded(&mut self, span: u64) {
1061        let used: BTreeMap<u64, u64> = self
1062            .running
1063            .iter()
1064            .map(|running| (running.job, self.used(running).unwrap_or(0)))
1065            .collect();
1066        self.cohorts
1067            .retain(|cohort| cohort.jobs.iter().any(|job| used.contains_key(job)));
1068        let all: u64 = used.values().sum();
1069        let lowest = self.cohorts.iter().map(|cohort| cohort.count).min();
1070        let mut worst = None;
1071        // What they all use bounds what any set of them does.
1072        if lowest.is_some_and(|lowest| all > lowest) {
1073            for cohort in &self.cohorts {
1074                let of_cohort: u64 = cohort.jobs.iter().filter_map(|job| used.get(job)).sum();
1075                worst = worst.max(of_cohort.checked_sub(cohort.count).filter(|past| *past > 0));
1076            }
1077        }
1078        self.hazard.unfunded.note(worst, span);
1079    }
1080
1081    /// What `running` uses now, as its samples say; without a trace of it, or a sample of the moment, `None`.
1082    fn used(&self, running: &Running<'_>) -> Option<u64> {
1083        match running
1084            .trace?
1085            .at(self.moment.saturating_sub(running.started))
1086        {
1087            Reading::Used(memory) => Some(memory),
1088            Reading::NotYet | Reading::Stale => None,
1089        }
1090    }
1091
1092    /// What the slice holds now as the mark reads it: its runners' use with the trace's overhead.
1093    fn slice(&self) -> u64 {
1094        self.used_now() + self.trace.map_or(0, |trace| trace.overhead)
1095    }
1096
1097    /// What the guards read of the slice now, as a sample would show it at a decision.
1098    fn slice_read(&self) -> u64 {
1099        self.used_now() + self.trace.map_or(0, |trace| trace.guard_overhead)
1100    }
1101
1102    /// What the running jobs use now, as their samples say.
1103    fn used_now(&self) -> u64 {
1104        self.running
1105            .iter()
1106            .map(|running| self.used(running).unwrap_or(0))
1107            .sum()
1108    }
1109
1110    /// The host as a reading would have it now: its other programs as recorded, the slice as replayed. `None` without
1111    /// a trace of it.
1112    fn host_memory(&self) -> Option<HostMemory> {
1113        let trace = self.trace.filter(|trace| trace.total > 0)?;
1114        let outside = trace.outside_at(self.moment)?;
1115        let slice = self.used_now() + trace.host_overhead;
1116        Some(HostMemory {
1117            at: self.moment / 1000,
1118            total: trace.total,
1119            available: trace.total.saturating_sub(outside).saturating_sub(slice),
1120            slice,
1121            some: None,
1122            full: None,
1123            holders: Vec::new(),
1124            ceiling: None,
1125            swap: None,
1126        })
1127    }
1128
1129    /// The aggregate count of what runs, the mirror's memory with it.
1130    fn count(&self) -> pooled::Count {
1131        let held: Vec<pooled::Runner<'_>> = self
1132            .running
1133            .iter()
1134            .map(|running| {
1135                let ran = self.moment.saturating_sub(running.started);
1136                let named = running.trace.is_none_or(|trace| ran >= trace.named_after);
1137                pooled::Runner {
1138                    key: named.then_some(&running.key),
1139                    takes: self.charge(running),
1140                    used: self
1141                        .used(running)
1142                        .filter(|_| running.run.measure == Measure::WithoutPageCache),
1143                    ran: Some(Duration::from_millis(ran)),
1144                    basis: Some(running.basis),
1145                }
1146            })
1147            .collect();
1148        let host = self.host_memory();
1149        pooled::count(&pooled::Snapshot {
1150            runners: &held,
1151            committed: self.mirror,
1152            slice: self.memory_max.map(|memory_max| pooled::Slice {
1153                memory: self.slice_read(),
1154                memory_max,
1155            }),
1156            host: host.map(|memory| {
1157                host::pooling(
1158                    &memory,
1159                    host::Remembered {
1160                        short: self.short,
1161                        stalled: false,
1162                    },
1163                )
1164            }),
1165            most: if self.trace.is_some() && self.policy == Policy::Measured {
1166                self.most_credit
1167            } else {
1168                0
1169            },
1170        })
1171    }
1172
1173    /// What the host leaves beside what runs, the mirror's memory counted; `None` without a trace of it.
1174    fn host_left(&self) -> Option<i64> {
1175        let memory = self.host_memory()?;
1176        let limit = host::limit(&memory, self.short && !self.running.is_empty());
1177        Some(host::left(limit, self.hosted(self.count()), false))
1178    }
1179
1180    /// Serves `waiting` at `now`, as one `scheduler::plan` does: each job in turn starts if it fits, until a job that
1181    /// waited long enough puts up the barrier; the jobs behind it start if `Backfill` lets them, and still age by what
1182    /// they lack themselves.
1183    fn pass(&mut self, waiting: &mut Vec<Queued<'run>>, now: u64) {
1184        let at = instant(now);
1185        self.barrier = None;
1186        self.backfill = None;
1187        self.usual.clear();
1188        self.needs.borrow_mut().clear();
1189        self.held_for_slice = 0;
1190        self.held_for_host = 0;
1191        self.host_needs.clear();
1192        let listed = waiting.clone();
1193        let mut index = 0;
1194        while let Some(queued) = waiting.get(index).copied() {
1195            match self.admits(queued, waiting, now) {
1196                Ok(admitted) if self.barrier.is_none() => {
1197                    waiting.remove(index);
1198                    self.start(queued, &admitted, None, now);
1199                }
1200                Ok(admitted) => match self.passes(queued, &listed) {
1201                    Some(usual) => {
1202                        waiting.remove(index);
1203                        self.start(queued, &admitted, Some(usual), now);
1204                    }
1205                    None => index += 1,
1206                },
1207                Err(Refused::Slot) => index += 1,
1208                Err(Refused::Budget(short)) => {
1209                    if self.barrier.is_none() && short.scarce == Scarce::Cpu {
1210                        self.cpu_held += 1;
1211                    }
1212                    self.held_for_slice += u64::from(short.scarce == Scarce::Memory);
1213                    let first = self.barrier.is_none();
1214                    self.hold(queued.run, short, at);
1215                    if first && self.barrier.is_some() {
1216                        self.backfill_behind(queued.run, &waiting[..index], &listed, now);
1217                    }
1218                    index += 1;
1219                }
1220                Err(Refused::Host(short)) => {
1221                    self.held_for_host += 1;
1222                    // A job behind a barrier does not wait for the host, as the daemon's `Turn::behind`: the owner does.
1223                    if self.barrier.is_none() {
1224                        self.host_needs.push(short.memory);
1225                    }
1226                    let first = self.barrier.is_none();
1227                    self.hold(queued.run, short, at);
1228                    if first && self.barrier.is_some() {
1229                        self.backfill_behind(queued.run, &waiting[..index], &listed, now);
1230                    }
1231                    index += 1;
1232                }
1233                Err(Refused::HighWater(short)) => {
1234                    if self.barrier.is_none() {
1235                        self.held_back += 1;
1236                    }
1237                    self.hold(queued.run, short, at);
1238                    index += 1;
1239                }
1240            }
1241        }
1242        self.short = self.band_stands();
1243        self.settle_waits(waiting);
1244    }
1245
1246    /// Whether the larger margin stands for the next pass.
1247    fn band_stands(&self) -> bool {
1248        match self.band {
1249            Band::AnyWaiter => self.held_for_host > 0,
1250            Band::NoWaiterFits => self.host_memory().is_some_and(|memory| {
1251                let reserved = self.hosted(self.count());
1252                host::short(&memory, reserved, false, self.host_needs.iter().copied())
1253            }),
1254        }
1255    }
1256
1257    /// What the engine does after a plan: a pool with nothing `waiting` loses its served mark, and one with nothing left
1258    /// to keep goes.
1259    fn settle_waits(&mut self, waiting: &[Queued<'run>]) {
1260        let queued: BTreeSet<Pool> = waiting.iter().map(|queued| pool_of(queued.run)).collect();
1261        self.pool_waits.retain(|pool, waits| {
1262            if !queued.contains(pool) {
1263                waits.emptied();
1264            }
1265            !waits.is_empty()
1266        });
1267    }
1268
1269    /// Unless `Barriers::Off`, ages the pool of `run`, which lacks what `short` says, and lets it put up the barrier, as
1270    /// `scheduler::plan` and the engine do. None ages at the high-water mark, read job by job as `admits` reads it:
1271    /// its zeros say nothing.
1272    fn hold(&mut self, run: &'run Ran, short: Short, at: SystemTime) {
1273        if self.barriers == Barriers::Off {
1274            return;
1275        }
1276        let drained = (!self.at_high_water()).then_some(self.drained());
1277        let waits = self.pool_waits.entry(pool_of(run)).or_default();
1278        if drained.is_some() {
1279            waits.note(short.scarce, short.job, at);
1280        }
1281        if self.barrier.is_none() {
1282            self.barrier = Barrier::of(short, waits, drained, at);
1283            if self.barrier.is_some() {
1284                waits.own(short.job);
1285            }
1286        }
1287    }
1288
1289    /// Under `Barriers::On`, finds the room behind the barrier `run` just put up, `older` being the jobs left waiting
1290    /// before it and `listed` what the pass began with. A pool's jobs start alike, so its first speaks for it.
1291    fn backfill_behind(
1292        &mut self,
1293        run: &'run Ran,
1294        older: &[Queued<'run>],
1295        listed: &[Queued<'run>],
1296        now: u64,
1297    ) {
1298        let Some(barrier) = self.barrier.filter(|_| self.barriers == Barriers::On) else {
1299            return;
1300        };
1301        let mut pools = BTreeSet::new();
1302        let older: Vec<Older<'_>> = older
1303            .iter()
1304            .filter(|queued| self.config.profiles.contains_key(&queued.run.profile))
1305            .filter(|queued| pools.insert(pool_of(queued.run)))
1306            .map(|queued| {
1307                let starting = self.starting(*queued, listed, now);
1308                Older {
1309                    profile: &queued.run.profile,
1310                    free_slot: self.free_slots(&queued.run.profile) > 0,
1311                    memory: starting.memory,
1312                    cpu: starting.cpu,
1313                }
1314            })
1315            .collect();
1316        let runners = self.runners();
1317        let around = Around {
1318            left: self.left(),
1319            credit_room: self.credit_room(),
1320            drained: self.drained(),
1321            runners: &runners,
1322            older: &older,
1323        };
1324        self.backfill = Backfill::behind(barrier, &run.profile, around, instant(now));
1325    }
1326
1327    /// How much more the credit could take off what runs, as `Budget::credit_room`.
1328    fn credit_room(&self) -> u64 {
1329        if self.trace.is_none()
1330            || self.policy != Policy::Measured
1331            || self.expects_credit == CreditRoom::LeftOut
1332        {
1333            return 0;
1334        }
1335        self.most_credit.saturating_sub(self.count().credit)
1336    }
1337
1338    /// What a drain leaves.
1339    fn drained(&self) -> Drained {
1340        Drained {
1341            memory: self.budget.map(signed),
1342            cpu: self.cpu_budget.map(signed),
1343            host: self.host_memory().map(|memory| {
1344                let limit = host::limit(&memory, !self.running.is_empty());
1345                signed(limit).saturating_sub(signed(self.mirror))
1346            }),
1347            host_plain: self.host_memory().map(|memory| {
1348                signed(host::limit(&memory, false)).saturating_sub(signed(self.mirror))
1349            }),
1350        }
1351    }
1352
1353    /// How many of `profile`'s slots are free.
1354    fn free_slots(&self, profile: &str) -> usize {
1355        let limits = &self.config.profiles[profile];
1356        let slots = self.slots.get(profile).copied().unwrap_or(limits.slots);
1357        let in_profile = self
1358            .running
1359            .iter()
1360            .filter(|running| running.profile == profile)
1361            .count();
1362        (slots as usize).saturating_sub(in_profile)
1363    }
1364
1365    /// Whether `queued`, which fits, may start behind the barrier, `listed` being what the pass began with: the usual
1366    /// run time it passes by, if so.
1367    fn passes(&mut self, queued: Queued<'run>, listed: &[Queued<'run>]) -> Option<Duration> {
1368        let run = queued.run;
1369        self.backfill.as_ref()?;
1370        let predictor = &self.predictor;
1371        let usual = *self.usual.entry(pool_of(run)).or_insert_with(|| {
1372            let keys = listed
1373                .iter()
1374                .filter(|other| other.run.repository == run.repository)
1375                .filter(|other| other.run.profile == run.profile)
1376                .map(|other| Key::of(other.run));
1377            predictor.longest_usual(keys, &run.profile)
1378        });
1379        let candidate = Candidate {
1380            profile: &run.profile,
1381            free_slots: self.free_slots(&run.profile),
1382            usual,
1383            caps: self.caps(&run.profile),
1384        };
1385        let backfill = self.backfill.as_mut()?;
1386        backfill.admits(candidate).then_some(usual).flatten()
1387    }
1388
1389    /// The budgets left beside what runs.
1390    fn left(&self) -> Left {
1391        let cpu: u64 = self.running.iter().map(|running| running.cpu).sum();
1392        let left = |budget: u64, taken: u64| signed(budget).saturating_sub(signed(taken));
1393        Left {
1394            memory: self.budget.map(|budget| left(budget, self.taken())),
1395            cpu: self.cpu_budget.map(|budget| left(budget, cpu)),
1396            host: self.host_left(),
1397        }
1398    }
1399
1400    /// `profile`'s caps, its CPU at most the budget, as `scheduler::Profile` has them.
1401    fn caps(&self, profile: &str) -> Caps {
1402        let limits = &self.config.profiles[profile];
1403        let cpu = u64::from(limits.cpus).saturating_mul(1000);
1404        Caps {
1405            memory: limits.memory.0,
1406            cpu: self.cpu_budget.map_or(cpu, |budget| cpu.min(budget)),
1407        }
1408    }
1409
1410    /// Notes the worst moments so far, with the `mirror`'s memory.
1411    fn note_worst(&mut self, mirror: u64) {
1412        self.most_running = self.most_running.max(self.running.len() as u64);
1413        let peaks: u64 = self.running.iter().map(|running| running.peak).sum();
1414        self.worst_overlap = self.worst_overlap.max(peaks + mirror);
1415        let cpu: u64 = self
1416            .running
1417            .iter()
1418            .map(|running| running.run.cpu_average.unwrap_or(0))
1419            .sum();
1420        self.worst_cpu = self.worst_cpu.max(cpu);
1421    }
1422
1423    /// What the replay of `queue` came to.
1424    fn replay(mut self, queue: &[Queued<'run>]) -> Replay {
1425        let started: BTreeSet<u64> = self.started.iter().copied().collect();
1426        let never_started: Vec<&Queued<'_>> = queue
1427            .iter()
1428            .filter(|queued| !started.contains(&queued.job))
1429            .collect();
1430        for queued in &never_started {
1431            self.pools
1432                .entry(pool_of(queued.run))
1433                .or_default()
1434                .never_started += 1;
1435        }
1436        let waits = self.waits;
1437        let first = queue.first().map_or(0, |queued| queued.run.queued_at);
1438        Replay {
1439            jobs: queue.len() as u64,
1440            never_started: never_started.len() as u64,
1441            mean_wait: waits.iter().sum::<u64>() / (waits.len() as u64).max(1),
1442            wait: spread(waits),
1443            most_running: self.most_running,
1444            worst_overlap: self.worst_overlap,
1445            makespan: self.last_end.saturating_sub(first) / 1000,
1446            under_predicted: self.under_predicted,
1447            held_back: self.held_back,
1448            cpu_held: self.cpu_held,
1449            worst_cpu: self.worst_cpu,
1450            pools: self.pools,
1451            charged: self.charged,
1452            capacity: self.capacity,
1453            barrier_for: self.barrier_for,
1454            withheld: self.withheld,
1455            runs: self.runs.into_values().map(RunSpan::replay).collect(),
1456            backfilled: self.backfilled,
1457            slice_waited: self.slice_waited,
1458            host_waited: self.host_waited,
1459            hazard: self.hazard,
1460        }
1461    }
1462
1463    /// What runs, as a backfill reads it: each job's usual run time as the runs finished so far say.
1464    fn runners(&self) -> Vec<Runner<'_>> {
1465        self.running
1466            .iter()
1467            .map(|running| Runner {
1468                profile: running.profile,
1469                started_at: instant(running.started),
1470                usual: self.predictor.usual(&Key::of(running.run), running.profile),
1471                memory: self.charge(running),
1472                cpu: running.cpu,
1473                caps: self.caps(running.profile),
1474            })
1475            .collect()
1476    }
1477
1478    /// Whether measured admission starts nothing now: with a trace, what the slice holds is at the high-water mark, and
1479    /// without one the running jobs' peaks are.
1480    fn at_high_water(&self) -> bool {
1481        if self.trace.is_some() {
1482            return self.policy == Policy::Measured
1483                && self.memory_max.is_some_and(|max| {
1484                    self.slice_read().saturating_mul(100) >= max.saturating_mul(HIGH_WATER)
1485                });
1486        }
1487        let peaks: u64 = self.running.iter().map(|running| running.peak).sum();
1488        self.policy == Policy::Measured
1489            && self.budget.is_some_and(|budget| {
1490                peaks.saturating_mul(100) >= budget.saturating_mul(HIGH_WATER)
1491            })
1492    }
1493
1494    /// Ends the jobs that end by `now`, in the order they end; measured admission learns them as the daemon reads
1495    /// their rows.
1496    fn finish(&mut self, now: u64) {
1497        let (ended, running): (Vec<_>, Vec<_>) = std::mem::take(&mut self.running)
1498            .into_iter()
1499            .partition(|running| running.ends <= now);
1500        self.running = running;
1501        let mut ended = ended;
1502        ended.sort_by_key(|ended| ended.ends);
1503        for ended in ended {
1504            // As the daemon reads the row: under the cap its container had.
1505            let cap = ended
1506                .run
1507                .memory_cap
1508                .unwrap_or(self.config.profiles[ended.profile].memory.0);
1509            self.under_predicted += u64::from(ended.peak > ended.reserved);
1510            let reserved = (self.policy == Policy::Measured).then_some(ended.reserved);
1511            let run = Ran {
1512                reserved,
1513                ..ended.run.clone()
1514            };
1515            self.predictor.learn(&run, ended.profile, cap, ended.ends);
1516            self.last_end = self.last_end.max(ended.ends);
1517            if let Some(by) = ended.backfilled {
1518                let overrun = ended.ends.saturating_sub(by);
1519                self.backfilled.overran += u64::from(overrun > 0);
1520                self.backfilled.most_overrun = self.backfilled.most_overrun.max(overrun / 1000);
1521            }
1522            let span = self.runs.get_mut(&run_key(ended.run));
1523            if let Some(span) = span {
1524                span.last_end = span.last_end.max(ended.ends);
1525            }
1526            for follower in self.followers.remove(&ended.job).unwrap_or_default() {
1527                self.arriving
1528                    .insert((ended.ends + follower.gap, follower.at));
1529            }
1530        }
1531    }
1532
1533    /// Under measured admission, predicts each running job again, as the daemon's runners follow their job's
1534    /// prediction every tick: the first running copy of a job, in the order they started, goes by its own runs, and
1535    /// the others have it beside them.
1536    fn rereserve(&mut self, now: u64) {
1537        if self.policy != Policy::Measured {
1538            return;
1539        }
1540        let cpus: Vec<u64> = self
1541            .running
1542            .iter()
1543            .map(|running| self.cpu(&Key::of(running.run), running.profile))
1544            .collect();
1545        let mut seen = BTreeSet::new();
1546        for (running, cpu) in self.running.iter_mut().zip(cpus) {
1547            let key = Key::of(running.run);
1548            let copies = if seen.insert(key.clone()) {
1549                Copies::Alone
1550            } else {
1551                Copies::Several
1552            };
1553            let limits = &self.config.profiles[running.profile];
1554            let prediction =
1555                self.predictor
1556                    .predict(&key, running.profile, limits.memory.0, now, copies);
1557            running.reserved = prediction.memory;
1558            running.basis = prediction.basis;
1559            running.cpu = cpu;
1560        }
1561    }
1562
1563    /// The CPU a run of `key` in `profile` reserves, in millicores: its profile's `cpus` by caps, its predicted
1564    /// average measured, at most the CPU budget.
1565    fn cpu(&self, key: &Key, profile: &str) -> u64 {
1566        let cap = u64::from(self.config.profiles[profile].cpus).saturating_mul(1000);
1567        let cpu = match self.policy {
1568            Policy::Caps => cap,
1569            Policy::Measured => self.predictor.predict_cpu(key, profile, cap).cpu,
1570        };
1571        self.cpu_budget.map_or(cpu, |budget| cpu.min(budget))
1572    }
1573
1574    /// What the running jobs take of the budget, as `pooled::count` adds them up, the mirror left out: the budget is
1575    /// what it leaves.
1576    fn taken(&self) -> u64 {
1577        self.count().pooled().saturating_sub(self.mirror)
1578    }
1579
1580    /// What `running` takes of the budget: under measured admission, as the daemon counts it, the larger of what it
1581    /// reserved and what it uses, without a trace its peak for the whole run; with one, until its job is known what it
1582    /// started reserving, and at its cap while its samples say nothing.
1583    fn charge(&self, running: &Running<'_>) -> u64 {
1584        let Some(trace) = running.trace.filter(|_| self.policy == Policy::Measured) else {
1585            return match self.policy {
1586                Policy::Caps => running.reserved,
1587                Policy::Measured => running.reserved.max(running.peak),
1588            };
1589        };
1590        let ran = self.moment.saturating_sub(running.started);
1591        let reserved = if ran < trace.named_after {
1592            running.starting.max(running.reserved)
1593        } else {
1594            running.reserved
1595        };
1596        match trace.at(ran) {
1597            Reading::NotYet => reserved,
1598            Reading::Used(memory) => reserved.max(memory),
1599            Reading::Stale => self.config.profiles[running.profile].memory.0,
1600        }
1601    }
1602
1603    /// What `queued` reserves if it starts at `now`, or why the policy does not admit it, `waiting` being every job
1604    /// not started yet.
1605    fn admits(
1606        &self,
1607        queued: Queued<'run>,
1608        waiting: &[Queued<'run>],
1609        now: u64,
1610    ) -> Result<Admitted, Refused> {
1611        let run = queued.run;
1612        let Some(limits) = self.config.profiles.get(&run.profile) else {
1613            return Err(Refused::Slot);
1614        };
1615        if self.free_slots(&run.profile) == 0 {
1616            return Err(Refused::Slot);
1617        }
1618        let starting = self.starting(queued, waiting, now);
1619        let short = |scarce, held| Short {
1620            job: queued.job,
1621            scarce,
1622            held,
1623            memory: starting.memory,
1624            cpu: starting.cpu,
1625        };
1626        if let Some(budget) = self.budget {
1627            if self.taken() + starting.memory > budget {
1628                return Err(Refused::Budget(short(Scarce::Memory, Held::ByBudget)));
1629            }
1630            if self.at_high_water() {
1631                return Err(Refused::HighWater(short(Scarce::Memory, Held::ByBudget)));
1632            }
1633        }
1634        if self
1635            .host_left()
1636            .is_some_and(|left| left < signed(starting.memory))
1637        {
1638            return Err(Refused::Host(short(Scarce::Memory, Held::ByHost)));
1639        }
1640        if let Some(cpu_budget) = self.cpu_budget {
1641            let taken: u64 = self.running.iter().map(|running| running.cpu).sum();
1642            if taken + starting.cpu > cpu_budget {
1643                return Err(Refused::Budget(short(Scarce::Cpu, Held::ByBudget)));
1644            }
1645        }
1646        Ok(Admitted {
1647            reserved: starting.reserved,
1648            starting: starting.memory,
1649            basis: starting.basis,
1650            // A job over its cap is killed at it.
1651            peak: run.memory_peak.min(limits.memory.0),
1652            cpu: self.cpu(&Key::of(run), &run.profile),
1653        })
1654    }
1655
1656    /// What the runner of `queued` starts with. As in the daemon, it starts reserving the largest prediction among the
1657    /// waiting jobs of its repository's pool (those that ran in its profile), then its job's own.
1658    fn starting(&self, queued: Queued<'run>, waiting: &[Queued<'run>], now: u64) -> Starting {
1659        let run = queued.run;
1660        let profile = run.profile.as_str();
1661        let cap = self.config.profiles[profile].memory.0;
1662        let running = |job: &Ran| {
1663            self.running
1664                .iter()
1665                .any(|running| same_job(running.run, job))
1666        };
1667        // A waiting job with a copy waiting or running beside it, as the daemon sees its queue.
1668        let predicted = |job: &Ran| {
1669            let key = Key::of(job);
1670            let waiting = waiting
1671                .iter()
1672                .filter(|other| same_job(other.run, job))
1673                .count();
1674            let copies = if waiting > 1 || running(job) {
1675                Copies::Several
1676            } else {
1677                Copies::Alone
1678            };
1679            self.predictor
1680                .predict(&key, profile, cap, now, copies)
1681                .memory
1682        };
1683        // The started job, once known: the first of its copies to run goes by its own runs.
1684        let started = || {
1685            let key = Key::of(run);
1686            let copies = if running(run) {
1687                Copies::Several
1688            } else {
1689                Copies::Alone
1690            };
1691            self.predictor.predict(&key, profile, cap, now, copies)
1692        };
1693        let pool = || {
1694            waiting
1695                .iter()
1696                .map(|other| other.run)
1697                .filter(|job| job.repository == run.repository && job.profile == run.profile)
1698        };
1699        let own = started();
1700        let need = || Need {
1701            memory: pool().map(predicted).max().unwrap_or(0),
1702            // As the daemon starts a runner: at the most CPU any waiting job of its repository's pool reserves.
1703            cpu: pool()
1704                .map(|job| self.cpu(&Key::of(job), profile))
1705                .max()
1706                .unwrap_or(0),
1707        };
1708        let need = if self.trace.is_some() {
1709            *self
1710                .needs
1711                .borrow_mut()
1712                .entry(pool_of(run))
1713                .or_insert_with(need)
1714        } else {
1715            need()
1716        };
1717        let (memory, reserved, basis) = match self.policy {
1718            Policy::Caps => (cap, cap, Basis::Cap),
1719            Policy::Measured => (need.memory.max(own.memory), own.memory, own.basis),
1720        };
1721        Starting {
1722            memory,
1723            reserved,
1724            basis,
1725            cpu: need.cpu.max(self.cpu(&Key::of(run), profile)),
1726        }
1727    }
1728
1729    /// Starts `queued` at `now`, which ends its pool's wait; `usual`, the usual run time it started behind a barrier by.
1730    fn start(
1731        &mut self,
1732        queued: Queued<'run>,
1733        admitted: &Admitted,
1734        usual: Option<Duration>,
1735        now: u64,
1736    ) {
1737        let run = queued.run;
1738        let Some((profile, _)) = self.config.profiles.get_key_value(&run.profile) else {
1739            return;
1740        };
1741        let ran_for = run
1742            .finished_at
1743            .unwrap_or_default()
1744            .saturating_sub(run.started_at.unwrap_or_default());
1745        let waited = now.saturating_sub(queued.arrived) / 1000;
1746        let span = self.runs.entry(run_key(run)).or_insert(RunSpan {
1747            first_arrival: queued.arrived,
1748            last_end: now,
1749            profiles: BTreeSet::new(),
1750        });
1751        span.first_arrival = span.first_arrival.min(queued.arrived);
1752        span.profiles.insert(run.profile.clone());
1753        self.started.push(queued.job);
1754        self.backfilled.jobs += u64::from(usual.is_some());
1755        let pool = pool_of(run);
1756        if let Some(waits) = self.pool_waits.get_mut(&pool) {
1757            waits.started();
1758        }
1759        self.pools.entry(pool).or_default().waits.push(waited);
1760        self.waits.push(waited);
1761        self.running.push(Running {
1762            run,
1763            job: queued.job,
1764            profile,
1765            started: now,
1766            ends: now + ran_for,
1767            backfilled: usual.map(|usual| {
1768                now.saturating_add(u64::try_from(usual.as_millis()).unwrap_or(u64::MAX))
1769            }),
1770            reserved: admitted.reserved,
1771            peak: admitted.peak,
1772            cpu: admitted.cpu,
1773            key: Key::of(run),
1774            basis: admitted.basis,
1775            starting: admitted.starting,
1776            trace: self.trace.and_then(|trace| trace.runs.get(&RunId::of(run))),
1777        });
1778        self.needs.borrow_mut().clear();
1779        if self.trace.is_some() {
1780            self.cohorts.push(Cohort {
1781                jobs: self.running.iter().map(|running| running.job).collect(),
1782                count: self.taken(),
1783            });
1784        }
1785    }
1786}
1787
1788/// `ms` since the epoch, as `scheduler::plan` reads the clock.
1789fn instant(ms: u64) -> SystemTime {
1790    SystemTime::UNIX_EPOCH + Duration::from_millis(ms)
1791}
1792
1793/// A budget's bytes or millicores as `Drained` counts them.
1794fn signed(amount: u64) -> i64 {
1795    i64::try_from(amount).unwrap_or(i64::MAX)
1796}
1797
1798#[cfg(test)]
1799mod tests;