Skip to main content

runnerd_core/
sizing.rs

1//! Right-sizing advice from the job history: the spread of each profile's and each job's sampled peaks, waits and
2//! slot use, and the `memory` and `slots` to set. Pure: the store reads the history, the daemon serves the result
3//! (`api::Sizing`). It never changes the config: a client applies advice through `PUT /v1/config`, which validates
4//! it like any other config, and under `[sizing] auto` the daemon applies what `auto::changes` picks the same way.
5
6use crate::admission::Key;
7use crate::admission::recent::Recent;
8use crate::api::{self, Advice, Peaks, Spread};
9use crate::config::{Admission, ByteSize, Config};
10use crate::observe::metrics::SAMPLE_INTERVAL;
11
12pub(crate) use crate::api::GRANULE;
13
14/// Without its container's `memory.events`, a peak at or above this share of its cap, in percent, likely met it.
15const AT_CAP: u64 = 95;
16
17/// Lowering a cap is advised once it saves at least this share of it, in percent.
18const WORTH_LOWERING: u64 = 10;
19
20/// Jobs that waited this long for a slot at p95, in seconds, or under `caps` admission slots busy this share of the
21/// time, in percent, want more slots.
22const WAITED: u64 = 60;
23const BUSY: u32 = 50;
24
25/// One finished job of this daemon's runners, as sizing reads it. Times in milliseconds.
26#[derive(Debug, Clone, PartialEq, Eq)]
27pub struct Ran {
28    /// `owner/name`.
29    pub repository: String,
30    /// The workflow's name, when known.
31    pub workflow: Option<String>,
32    /// The job's name.
33    pub name: String,
34    /// The profile its runner ran in.
35    pub profile: String,
36    /// Its container's memory cap, when recorded.
37    pub memory_cap: Option<u64>,
38    /// Its container's CPU cap, millicores, when recorded.
39    pub cpu_cap: Option<u64>,
40    /// Its sampled memory peak, bytes, as `measure` counts memory.
41    pub memory_peak: u64,
42    /// Its sampled CPU peak, millicores.
43    pub cpu_peak: u64,
44    /// Its CPU time over its run time, millicores; `None` when not recorded.
45    pub cpu_average: Option<u64>,
46    /// When it was queued.
47    pub queued_at: u64,
48    /// When it started; `None` for a job lost before.
49    pub started_at: Option<u64>,
50    /// When its runner's container started: before `queued_at`, it was a warm runner.
51    pub runner_started_at: u64,
52    /// When it finished, or was found lost.
53    pub finished_at: Option<u64>,
54    /// Whether the kernel killed a process in its container for memory.
55    pub oom_killed: bool,
56    /// Whether its container's memory, or a descendant's, reached a limit with nothing left to reclaim
57    /// (`memory.events` `oom`); `None` when its events were not recorded.
58    pub hit_cap: Option<bool>,
59    /// Whether its container's own limit failed reclaim (`memory.events.local` `oom`), not a descendant's; `None`
60    /// when not recorded, as before schema 14.
61    pub own_cap: Option<bool>,
62    /// What its sampled memory counts.
63    pub measure: Measure,
64    /// Whether it completed with success: a failed or lost run may have stopped before its heaviest step.
65    pub succeeded: bool,
66    /// Whether it completed with `failure` or `timed_out`: not lost, not cancelled.
67    pub failed: bool,
68    /// Its workflow run on GitHub: a re-run of its failed jobs has the same.
69    pub run_id: u64,
70    /// Which attempt of that run it belongs to, from 1.
71    pub run_attempt: u32,
72    /// The branch it ran for, when known.
73    pub branch: Option<String>,
74    /// What measured admission reserved for it; `None` under caps or for an adopted runner.
75    pub reserved: Option<u64>,
76    /// How long of its wait it waited because the host's memory could not take its runner, in ms: no more slots
77    /// would have started it sooner.
78    pub host_waited: u64,
79    /// How much of its wait passed while no runnerd ran, in ms.
80    pub unseen: u64,
81    /// The periods of its CPU quota it had work in (`api::JobMetrics::cpu_periods`); `None` where the kernel kept no
82    /// figure, as in runs from before schema 17.
83    pub cpu_periods: Option<u64>,
84    /// Of those, the periods its quota throttled it in (`api::JobMetrics::cpu_throttled`).
85    pub cpu_throttled: Option<u64>,
86    /// How long of its wait no slot of its profile was free while the slice's memory, the host's and the CPU budget
87    /// had room for its runner, in ms: what one more slot would have saved it (ADR 0090). 0 in runs from before
88    /// schema 18.
89    pub slot_waited: u64,
90}
91
92/// A job's wait for a runner as sizing, insights and the history's figures count it: from when GitHub queued it, or
93/// from when the history holds every job if that came later (`history_kept`), as for a job queued before runnerd
94/// first ran, to when it started, less what of it passed while no runnerd ran (ADR 0081). A job's own page shows its
95/// whole wait, as GitHub's does; arrivals, as `simulate` and warm runners model them, go by `queued_at`.
96#[derive(Debug, Clone, Copy, PartialEq, Eq)]
97pub struct Wait {
98    /// When GitHub queued it, in ms.
99    pub queued_at: u64,
100    /// When it started, in ms.
101    pub started_at: u64,
102    /// How much of it passed while no runnerd ran, in ms.
103    pub unseen: u64,
104}
105
106impl Wait {
107    /// In ms, 0 at least, with the history holding every job since `kept_since` (ms).
108    pub fn counted(self, kept_since: u64) -> u64 {
109        self.started_at
110            .saturating_sub(self.queued_at.max(kept_since))
111            .saturating_sub(self.unseen)
112    }
113}
114
115/// A run its CPU quota throttled in this share of its run or more, in percent, was held back by its cap: it ran as
116/// fast as the cap let it, so its average says what the cap allowed. No lowering reads it, under `measured`
117/// admission it raises the cap, and insights name its job (ADR 0079). The share is of the run's wall time in 100 ms
118/// periods, not of the periods the kernel counted, which leave out the time it was idle: a job that waits on the
119/// network for most of its run and bursts past its cap in a few compiles is throttled in most of its busy periods and
120/// in little of its run. A throttled period loses only part of its 100 ms, so the share is more than the time the cap
121/// cost. The Android quality gate lost about 90 s of its 517 at 9 CPUs, 17% of its run, and was throttled in 28% of
122/// it, 21% at 13 and 16% at 19; an 8-minute job whose three 20-second compiles want 20 CPUs is throttled in 11%, and
123/// lost about 6%.
124pub const HELD: u64 = 15;
125
126/// What a run's CPU quota did to it, as auto sizing and insights read it (ADR 0079). Times in milliseconds.
127#[derive(Debug, Clone, Copy, PartialEq, Eq)]
128pub struct Throttling {
129    /// When it started.
130    pub started_at: Option<u64>,
131    /// When it finished.
132    pub finished_at: Option<u64>,
133    /// The periods of its CPU quota it had work in (`api::JobMetrics::cpu_periods`); `None` where the kernel kept no
134    /// figure, as in runs from before schema 17.
135    pub periods: Option<u64>,
136    /// Of those, the periods its quota throttled it in (`api::JobMetrics::cpu_throttled`).
137    pub throttled: Option<u64>,
138}
139
140impl Throttling {
141    /// How long it ran, from its start to its finish; `None` without either.
142    pub fn took(self) -> Option<u64> {
143        Some(self.finished_at?.saturating_sub(self.started_at?))
144    }
145
146    /// The share of its run its quota throttled it in, per mille: its throttled periods over its run's wall time in
147    /// 100 ms periods, or over the periods the kernel counted when those are more, as when its start or finish is
148    /// unknown. `None` without a throttling figure.
149    pub fn share(self) -> Option<u64> {
150        let (periods, throttled) = self.periods.zip(self.throttled)?;
151        let run = self.took().map_or(0, |took| took / 100).max(periods);
152        Some(throttled.saturating_mul(1000) / run.max(1))
153    }
154
155    /// Whether its cap held it back: throttled in `HELD` percent of its run or more. `None` without a throttling
156    /// figure: unknown, never read as free.
157    pub fn held(self) -> Option<bool> {
158        let share = self.share()?;
159        Some(self.throttled.is_some_and(|throttled| throttled > 0) && share >= HELD * 10)
160    }
161}
162
163/// What a run's sampled memory counts.
164#[derive(Debug, Clone, Copy, PartialEq, Eq)]
165pub enum Measure {
166    /// `memory.current` less `inactive_file`, as runners started before schema version 8 were sampled: page cache
167    /// read twice (`active_file`) counts, so peaks overstate what a job needs.
168    WithActiveFile,
169    /// `memory.current` less the file LRU lists (`active_file`, `inactive_file`): an estimate of what a job holds
170    /// without the page cache the kernel can drop.
171    WithoutPageCache,
172}
173
174/// What a run says about its container's memory cap (ADR 0070).
175#[derive(Debug, Clone, Copy, PartialEq, Eq)]
176pub enum Capped {
177    /// The container's own limit failed reclaim: it needed more than the cap.
178    Met,
179    /// Recorded without the local counter: by the reading before it, a kill or a limit hit in the container, or
180    /// without events a peak within `AT_CAP` percent of the cap. Holds and floors as `Met`, never raises a cap.
181    Assumed,
182    /// A process in it was killed for memory while its own limit held: the slice or the host ran out.
183    Killed,
184    /// None of those. A peak near the cap with no `oom` at it is clear: a JVM fills the room it has.
185    Clear,
186}
187
188impl Capped {
189    /// Whether it says the job needed its cap: `Met` or `Assumed`.
190    pub fn met(self) -> bool {
191        matches!(self, Capped::Met | Capped::Assumed)
192    }
193
194    /// Whether it puts its job on its cap: anything but `Clear`.
195    pub fn holds(self) -> bool {
196        self != Capped::Clear
197    }
198}
199
200impl Ran {
201    /// How long it kept its runner from anything else, in ms: from the runner's start, a warm runner's from when the
202    /// job queued, to its finish. The start of a runner counts, as a slot's runner is what a plan waits to see end.
203    pub fn occupied(&self) -> Option<u64> {
204        let from = self.runner_started_at.max(self.queued_at);
205        self.finished_at.map(|end| end.saturating_sub(from))
206    }
207
208    /// Its wait, once it started.
209    pub fn wait(&self) -> Option<Wait> {
210        Some(Wait {
211            queued_at: self.queued_at,
212            started_at: self.started_at?,
213            unseen: self.unseen,
214        })
215    }
216
217    /// What its CPU quota did to it.
218    pub fn throttling(&self) -> Throttling {
219        Throttling {
220            started_at: self.started_at,
221            finished_at: self.finished_at,
222            periods: self.cpu_periods,
223            throttled: self.cpu_throttled,
224        }
225    }
226
227    /// What it says about its container's `cap`. A kill that only a descendant's own limit explains, the counters
228    /// showing a limit hit below the container and none at it, is a service container the job capped itself: clear.
229    /// A kill no sample saw an `oom` before, its last sample within `AT_CAP` percent of the cap, met it in the last
230    /// interval.
231    pub fn capped(&self, cap: u64) -> Capped {
232        match self.own_cap {
233            Some(true) => Capped::Met,
234            // No sample saw `oom` at any level and its last came near the cap: its own limit killed it before the
235            // next sample could count it.
236            Some(false)
237                if self.oom_killed
238                    && self.hit_cap == Some(false)
239                    && self.memory_peak.saturating_mul(100) >= cap.saturating_mul(AT_CAP) =>
240            {
241                Capped::Met
242            }
243            Some(false) if self.oom_killed && self.hit_cap != Some(true) => Capped::Killed,
244            None if self.oom_killed
245                || self.hit_cap.unwrap_or_else(|| {
246                    self.memory_peak.saturating_mul(100) >= cap.saturating_mul(AT_CAP)
247                }) =>
248            {
249                Capped::Assumed
250            }
251            Some(false) | None => Capped::Clear,
252        }
253    }
254}
255
256/// One runner container's time in a slot for a job. Times in milliseconds.
257#[derive(Debug, Clone, PartialEq, Eq)]
258pub struct Held {
259    /// Its profile.
260    pub profile: String,
261    /// When it started holding the slot for a job: its start, or when its job was queued if that came later, as for
262    /// a warm runner.
263    pub started_at: u64,
264    /// When it was removed; `None` while it runs.
265    pub removed_at: Option<u64>,
266}
267
268/// A profile's `cpus` as the daemon ran it from `at` (ms), by its `profile.changed` event: one when it started with
269/// the profile, and after each reload or restart that changed the profile's image, CPUs, memory or slots.
270#[derive(Debug, Clone, PartialEq, Eq)]
271pub struct CpusSet {
272    /// The profile.
273    pub profile: String,
274    /// Its `cpus` from then.
275    pub cpus: u32,
276    /// When, in milliseconds.
277    pub at: u64,
278}
279
280/// A profile's `memory` as the daemon ran it from `at` (ms), by its `profile.changed` event, as `CpusSet` has its
281/// `cpus`.
282#[derive(Debug, Clone, PartialEq, Eq)]
283pub struct MemorySet {
284    /// The profile.
285    pub profile: String,
286    /// Its `memory` from then, in bytes.
287    pub memory: u64,
288    /// When, in milliseconds.
289    pub at: u64,
290}
291
292/// A profile's `slots` as the daemon ran them from `at` (ms), by its `profile.changed` event, as `CpusSet` has its
293/// `cpus`.
294#[derive(Debug, Clone, PartialEq, Eq)]
295pub struct SlotsSet {
296    /// The profile.
297    pub profile: String,
298    /// Its slots from then.
299    pub slots: u32,
300    /// When, in milliseconds.
301    pub at: u64,
302}
303
304/// What the store reads for sizing.
305#[derive(Debug, Clone, Default, PartialEq, Eq)]
306pub struct History {
307    /// Finished jobs with a recorded peak, cancelled ones left out.
308    pub jobs: Vec<Ran>,
309    /// Cancelled jobs, for what admission learns from how they ended: a kill for memory, a peak at the cap or past
310    /// what was reserved. Their peaks (0 when never sampled) are not read as a job's size.
311    pub cancelled: Vec<Ran>,
312    /// Runners that held a slot at some point after the history's start.
313    pub runners: Vec<Held>,
314    /// Auto sizing's changes, oldest first, from `CHANGES_READ` before now: what a revert reads (ADR 0070). Empty
315    /// where nothing reads them, as for admission.
316    pub changes: Vec<api::SizingChange>,
317    /// Each profile's `memory` as the daemon ran it, oldest first: since when a raise reads runs at it.
318    pub memory_set: Vec<MemorySet>,
319    /// Each profile's slots as the daemon ran them, oldest first: since when a lowering of slots reads how many ran.
320    pub slots_set: Vec<SlotsSet>,
321    /// From when, in ms, the history holds every job (`history_kept`): a wait before it, as of a job queued before
322    /// runnerd first ran, counts from then.
323    pub kept_since: u64,
324    /// The jobs of the window `jobs` leaves out, for a replay to say what it did not see.
325    pub left_out: LeftOut,
326}
327
328/// The jobs queued in a window that no replay can run, as it has no run time for them.
329#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
330pub struct LeftOut {
331    /// Still queued: however long they waited, it is not over.
332    pub queued: u64,
333    /// Still running.
334    pub running: u64,
335    /// Cancelled before or while they ran.
336    pub cancelled: u64,
337    /// Taken by another machine's runner.
338    pub elsewhere: u64,
339}
340
341/// What `advise` sizes against besides the history.
342#[derive(Debug, Clone, Copy)]
343pub struct Window {
344    /// The start asked for, in milliseconds, at most `now`.
345    pub since: u64,
346    /// Now, in milliseconds.
347    pub now: u64,
348    /// Seconds between two samples of a container.
349    pub sample_interval: u64,
350}
351
352impl Window {
353    /// The window `GET /v1/sizing` reads: from `since` (seconds), default 30 days before `now` (seconds), and
354    /// never after `now`.
355    pub fn new(since: Option<u64>, now: u64) -> Window {
356        Window {
357            since: since
358                .unwrap_or_else(|| now.saturating_sub(30 * 24 * 3600))
359                .min(now)
360                .saturating_mul(1000),
361            now: now.saturating_mul(1000),
362            sample_interval: SAMPLE_INTERVAL.as_secs(),
363        }
364    }
365}
366
367/// The advice for every profile of `config` from `history`, against the slice's `memory_max` as `config`'s
368/// admission policy budgets it. Peaks, and the memory advice, go by each job's sizing window over the history's last
369/// 30 days (`memory`, ADR 0070); `window.since` narrows only the waits, the busy share and the starts.
370pub fn advise(
371    config: &Config,
372    memory_max: Option<u64>,
373    history: &History,
374    window: Window,
375) -> api::Sizing {
376    let since = first_runner(history, window.since);
377    let caps = config.memory_caps().map_or(u64::MAX, |caps| caps.0);
378    let mirror = config.mirror_memory();
379    let rules = &config.sizing;
380    let recent = memory::windows(config, history, window.now);
381    let ceiling = Bound::ceiling(config);
382    let profiles = config
383        .profiles
384        .iter()
385        .map(|(name, profile)| {
386            let jobs: Vec<&Ran> = history
387                .jobs
388                .iter()
389                .filter(|job| job.profile == *name && job.queued_at >= window.since)
390                .collect();
391            let share = profile.memory.0.saturating_mul(u64::from(profile.slots));
392            let busy = busy(history, name, profile.slots, since, window.now);
393            let (wait, slot_wait) = (waits(&jobs, history.kept_since), slot_waits(&jobs));
394            let starts = starts(&jobs, history.kept_since);
395            let cap = profile.memory.0;
396            let took = memory::took(&history.memory_set, name, cap, window.now);
397            let sized = Sized {
398                cap,
399                cpus: u64::from(profile.cpus) * 1000,
400                slots: profile.slots,
401                share,
402                admission: config.host.admission,
403                room: memory_max.map(|max| match config.host.admission {
404                    // What the slice leaves this profile once the other profiles and the mirror took theirs.
405                    Admission::Caps => max.saturating_sub(caps.saturating_sub(share)),
406                    // Measured admission reserves predicted peaks, not caps: the config check only holds one
407                    // runner of each profile beside the mirror.
408                    Admission::Measured => max.saturating_sub(mirror),
409                }),
410                wants_slots: wants_slots(config.host.admission, &jobs, history.kept_since, busy),
411                min_jobs: rules.min_jobs,
412                upper: upper(
413                    ceiling,
414                    Bound::of(profile.max_memory, api::MemoryBound::MaxMemory),
415                ),
416                lower: Bound::of(profile.min_memory, api::MemoryBound::MinMemory),
417                max_slots: profile.max_slots.unwrap_or(u32::MAX),
418            };
419            let raises = Raises {
420                history,
421                recent: &recent,
422                profile: name,
423                cap,
424                took,
425                margin: rules.margin,
426            };
427            let memory = job_memory(&raises, &jobs, &sized, window.now, busy);
428            let peaks = memory::peaks(
429                recent.jobs_of(name).flat_map(|(_, runs)| runs.window()),
430                memory.on_cap,
431                sized.cpus,
432            );
433            let current = api::Resize {
434                memory: cap,
435                slots: profile.slots,
436                cpus: None,
437            };
438            let revert = memory::revert(config, history, name, current);
439            let advised = if let Some((_, to)) = &revert {
440                sized.reverted(*to)
441            } else {
442                let needs = Needs {
443                    raise: raises.need(None),
444                    floor: memory.floor.max(memory::revert_floor(history, name)),
445                };
446                sized.advice(&peaks, needs, sized.wants_slots)
447            };
448            api::ProfileSizing {
449                name: name.clone(),
450                memory: cap,
451                cpus: profile.cpus,
452                slots: profile.slots,
453                advice: advised.advice,
454                revert: revert.map(|(revert, _)| revert),
455                hold: advised.hold,
456                peaks,
457                wait,
458                slot_wait,
459                starts,
460                busy,
461                wants_slots: sized.wants_slots,
462                jobs: memory.jobs,
463            }
464        })
465        .collect();
466    api::Sizing {
467        since: since / 1000,
468        until: window.now / 1000,
469        margin: rules.margin,
470        sample_interval: window.sample_interval,
471        min_jobs: rules.min_jobs,
472        memory_max,
473        admission: config.host.admission.policy(),
474        profiles,
475        auto: config.sizing.auto,
476        changes: Vec::new(),
477        auto_plan: None,
478    }
479}
480
481/// The bound of a raise: the lower of `ceiling` and `max_memory`, the ceiling when they are the same, since
482/// raising `max_memory` alone would not let a raise past it.
483fn upper(ceiling: Option<Bound>, max_memory: Option<Bound>) -> Option<Bound> {
484    match (ceiling, max_memory) {
485        (Some(ceiling), Some(max)) if max.memory < ceiling.memory => Some(max),
486        (ceiling, max) => ceiling.or(max),
487    }
488}
489
490/// What a raise of one profile reads (`memory::raise_need`).
491struct Raises<'history> {
492    history: &'history History,
493    recent: &'history Recent,
494    profile: &'history str,
495    /// Its `memory`.
496    cap: u64,
497    /// Since when it has had it, in ms.
498    took: u64,
499    margin: u32,
500}
501
502impl Raises<'_> {
503    /// What a raise needs from the job `key`, or from every job for `None`.
504    fn need(&self, key: Option<&Key>) -> u64 {
505        memory::raise_need(
506            self.history,
507            self.recent,
508            self.profile,
509            self.cap,
510            self.took,
511            self.margin,
512            key,
513        )
514    }
515}
516
517/// What a profile's jobs say about its `memory`.
518struct JobMemory {
519    /// Each job's sizing.
520    jobs: Vec<api::JobSizing>,
521    /// How many of them are on their cap.
522    on_cap: u64,
523    /// The largest of their floors.
524    floor: u64,
525}
526
527/// Each job of `raises.profile` with runs in its window: its peaks, waits and advice; `jobs` are the profile's runs
528/// since the window's start, for the waits.
529fn job_memory(raises: &Raises<'_>, jobs: &[&Ran], sized: &Sized, now: u64, busy: u32) -> JobMemory {
530    let mut on_cap = 0;
531    let mut floor = 0;
532    let sizings = raises
533        .recent
534        .jobs_of(raises.profile)
535        .filter(|(_, runs)| runs.runs() > 0)
536        .map(|(key, runs)| {
537            let held = memory::on_cap(runs, now);
538            on_cap += u64::from(held);
539            let peaks = memory::peaks(runs.window(), u64::from(held), sized.cpus);
540            let needs = Needs {
541                raise: raises.need(Some(key)),
542                floor: memory::floor(runs, raises.margin),
543            };
544            floor = floor.max(needs.floor);
545            let runs_of: Vec<&Ran> = jobs
546                .iter()
547                .copied()
548                .filter(|job| Key::of(job) == *key)
549                .collect();
550            let wait = waits(&runs_of, raises.history.kept_since);
551            let wants = wants_slots(sized.admission, &runs_of, raises.history.kept_since, busy);
552            // A job's advice says what it needs; only its profile's is bounded by what can be written.
553            let unbounded = Sized {
554                upper: None,
555                lower: None,
556                ..*sized
557            };
558            api::JobSizing {
559                repository: key.repository.clone(),
560                workflow: key.workflow.clone(),
561                name: key.name.clone(),
562                advice: unbounded.advice(&peaks, needs, wants).advice,
563                peaks,
564                wait,
565            }
566        })
567        .collect();
568    JobMemory {
569        jobs: sizings,
570        on_cap,
571        floor,
572    }
573}
574
575/// Where a history read from `start` (ms) begins: at its first runner when that started later, as a new daemon's
576/// history does.
577fn first_runner(history: &History, start: u64) -> u64 {
578    history
579        .runners
580        .iter()
581        .map(|runner| runner.started_at)
582        .min()
583        .map_or(start, |first| first.max(start))
584}
585
586/// The percent of the time from `since` to `now` (ms) that the profile's runners held its `slots`.
587fn busy(history: &History, profile: &str, slots: u32, since: u64, now: u64) -> u32 {
588    let span = now.saturating_sub(since).max(1);
589    let held: u64 = history
590        .runners
591        .iter()
592        .filter(|runner| runner.profile == profile)
593        .map(|runner| {
594            let end = runner.removed_at.unwrap_or(now).min(now);
595            end.saturating_sub(runner.started_at.max(since))
596        })
597        .sum();
598    u32::try_from(
599        (held.saturating_mul(100) / span.saturating_mul(u64::from(slots).max(1))).min(100),
600    )
601    .unwrap_or(100)
602}
603
604/// A profile's limits and the rules advice follows.
605#[derive(Clone, Copy)]
606struct Sized {
607    cap: u64,
608    /// Its `cpus`, in millicores: CPU peaks are read only of runs at them.
609    cpus: u64,
610    slots: u32,
611    /// What its slots take of the budget now: `memory × slots`.
612    share: u64,
613    admission: Admission,
614    /// The memory the slice holds for it, as `admission` budgets it: all its slots at their caps under `caps`, one
615    /// runner under `measured`; `None` for an unlimited slice.
616    room: Option<u64>,
617    /// Whether its jobs waited for a slot at p95, or under `caps` its slots were busy, enough to want more.
618    wants_slots: bool,
619    min_jobs: u32,
620    /// The most `memory` a raise goes to: what `[host] memory_ceiling` leaves one runner (`Config::runner_ceiling`)
621    /// down to a granule, or `max_memory` when that is less; `None` without either.
622    upper: Option<Bound>,
623    /// The least `memory` a lowering goes to, `min_memory`.
624    lower: Option<Bound>,
625    /// The most `slots` a lowering or a revert gives it, `max_slots`: the config check refuses more.
626    max_slots: u32,
627}
628
629/// A bound of the config on a profile's `memory`: the config check refuses a profile past it.
630#[derive(Clone, Copy)]
631struct Bound {
632    memory: u64,
633    by: api::MemoryBound,
634}
635
636impl Bound {
637    /// What `[host] memory_ceiling` leaves one runner (`Config::runner_ceiling`), down to a granule so the config
638    /// file says it exactly and the check never reads more back.
639    fn ceiling(config: &Config) -> Option<Bound> {
640        let most = config.runner_ceiling()?;
641        Some(Bound {
642            memory: most / GRANULE * GRANULE,
643            by: api::MemoryBound::Ceiling {
644                ceiling: config.host.memory_ceiling?.0,
645                mirror: config.mirror_memory(),
646            },
647        })
648    }
649
650    /// A profile's `size` as the bound `by`.
651    fn of(size: Option<ByteSize>, by: api::MemoryBound) -> Option<Bound> {
652        size.map(|size| Bound { memory: size.0, by })
653    }
654}
655
656/// A profile's advice, and the bound that holds its `memory` away from what its jobs need.
657struct Advised {
658    advice: Advice,
659    hold: Option<api::MemoryHold>,
660}
661
662impl From<Advice> for Advised {
663    fn from(advice: Advice) -> Advised {
664        Advised { advice, hold: None }
665    }
666}
667
668/// What a set of jobs' runs say its `memory` needs (`memory`, ADR 0070).
669#[derive(Debug, Clone, Copy)]
670struct Needs {
671    /// What a raise goes to: from runs that met the current cap since the profile took it; 0 without one.
672    raise: u64,
673    /// What a lowering stays at or above: every windowed run's need, and any revert's floor.
674    floor: u64,
675}
676
677impl Sized {
678    /// A raise toward `needs.raise` when it is above the cap; a lowering toward `needs.floor`, no further than
679    /// `min_memory`, when that saves a tenth and no job is on its cap; else keep, with `needs.floor` as what the jobs
680    /// need, above the cap or not.
681    fn advice(&self, peaks: &Peaks, needs: Needs, wants_slots: bool) -> Advised {
682        if peaks.jobs < u64::from(self.min_jobs) {
683            return Advice::TooFew { jobs: peaks.jobs }.into();
684        }
685        if needs.raise > self.cap {
686            return self.raise(needs.raise, self.slots);
687        }
688        let need = needs.floor.max(GRANULE);
689        // A job on its cap may have been held back or killed by it: no lowering until it ran clear of it again.
690        if peaks.on_cap == 0
691            && need <= self.cap
692            && self.cap - need >= self.cap * WORTH_LOWERING / 100
693        {
694            let hold = self
695                .lower
696                .filter(|min| min.memory > need)
697                .map(|min| api::MemoryHold {
698                    need,
699                    bound: min.memory,
700                    by: min.by,
701                });
702            let memory = hold.map_or(need, |hold| hold.bound);
703            if memory >= self.cap {
704                return Advised {
705                    advice: Advice::Keep { memory: need },
706                    hold,
707                };
708            }
709            let fit = |room: u64| u32::try_from(room / memory).unwrap_or(u32::MAX);
710            // Under measured admission slots are not bought with caps: the advice line says when more may help.
711            let advice = Advice::Lower {
712                memory,
713                slots: if wants_slots && self.admission == Admission::Caps {
714                    fit(self.share).min(self.max_slots).max(self.slots)
715                } else {
716                    self.slots
717                },
718            };
719            return Advised { advice, hold };
720        }
721        Advice::Keep { memory: need }.into()
722    }
723
724    /// The raise that takes back a lowering that went too far, to `to`: as far as `[host] memory_ceiling` and
725    /// `max_memory` allow, which a reload may have lowered since, with as many of `to`'s slots as the slice and
726    /// `max_slots` hold now.
727    fn reverted(&self, to: api::Resize) -> Advised {
728        self.raise(to.memory, to.slots.min(self.max_slots))
729    }
730
731    /// A raise toward `need` with at most `slots`: no further than `[host] memory_ceiling` and `max_memory` allow,
732    /// since a raise the config check refuses would be proposed again at every look, and with the slots the slice
733    /// holds at that memory, as `admission` budgets it. None while the bound allows nothing past the cap or the slice
734    /// holds no slot: the jobs need `need`.
735    fn raise(&self, need: u64, slots: u32) -> Advised {
736        let hold = self
737            .upper
738            .filter(|most| need > most.memory)
739            .map(|most| api::MemoryHold {
740                need,
741                bound: most.memory,
742                by: most.by,
743            });
744        let memory = hold.map_or(need, |hold| hold.bound);
745        let too_small = Advised {
746            advice: Advice::SliceTooSmall { memory: need },
747            hold,
748        };
749        if memory <= self.cap {
750            return too_small;
751        }
752        let fit = |room: u64| u32::try_from(room / memory).unwrap_or(u32::MAX);
753        let slots = match (self.admission, self.room) {
754            (Admission::Caps, Some(room)) => fit(room).min(slots),
755            (Admission::Measured, Some(room)) if room < memory => 0,
756            (_, _) => slots,
757        };
758        if slots == 0 {
759            return too_small;
760        }
761        Advised {
762            advice: Advice::Raise { memory, slots },
763            hold,
764        }
765    }
766}
767
768/// The [waits](Wait) of the jobs that started, in seconds, less what they waited for the host's memory.
769fn waits(jobs: &[&Ran], kept_since: u64) -> Spread {
770    spread(
771        jobs.iter()
772            .filter_map(|job| {
773                job.wait()
774                    .map(|wait| wait.counted(kept_since).saturating_sub(job.host_waited) / 1000)
775            })
776            .collect(),
777    )
778}
779
780/// The waits of the jobs that started with no slot free while the budgets had room for their runners, in seconds
781/// (`Ran::slot_waited`).
782fn slot_waits(jobs: &[&Ran]) -> Spread {
783    spread(
784        jobs.iter()
785            .filter(|job| job.started_at.is_some())
786            .map(|job| job.slot_waited / 1000)
787            .collect(),
788    )
789}
790
791/// The p95 wait of `jobs`, in seconds, that asks for more slots under `admission`. Under `measured` only the wait
792/// with no slot free while the budgets had room for the job's runner (`slot_waits`): a job memory or CPU held back
793/// would wait for them in a new slot as well (ADR 0090). Under `caps` the whole wait less the host's part (`waits`):
794/// a slot is bought with its cap, and with every slot busy and the caps filling `MemoryMax` no job has room for its
795/// runner, so none would count.
796fn slot_asking_wait(admission: Admission, jobs: &[&Ran], kept_since: u64) -> u64 {
797    match admission {
798        Admission::Caps => waits(jobs, kept_since).p95,
799        Admission::Measured => slot_waits(jobs).p95,
800    }
801}
802
803/// Whether more slots would help a profile, or a job of it: its `jobs` waited `WAITED` at p95 by
804/// `slot_asking_wait`, or under `caps`, where a slot is bought with its cap, its slots were `busy` half the time.
805/// Under `measured` slots that are busy and never waited for would start nothing sooner.
806fn wants_slots(admission: Admission, jobs: &[&Ran], kept_since: u64, busy: u32) -> bool {
807    slot_asking_wait(admission, jobs, kept_since) >= WAITED
808        || (admission == Admission::Caps && busy >= BUSY)
809}
810
811/// The most of `jobs` that waited only for a slot at once, each from `Ran::slot_waited` before its start to its
812/// start: the slots that would have started them all.
813fn short_of_slots(jobs: &[&Ran]) -> u32 {
814    let mut edges: Vec<(u64, i32)> = jobs
815        .iter()
816        .filter(|job| job.slot_waited > 0)
817        .filter_map(|job| {
818            let started = job.started_at?;
819            Some([(started.saturating_sub(job.slot_waited), 1), (started, -1)])
820        })
821        .flatten()
822        .collect();
823    peak(&mut edges)
824}
825
826/// The most intervals open at once, from each one's opening (`1`) and closing (`-1`) edge; one that closes as
827/// another opens does not overlap it.
828fn peak(edges: &mut [(u64, i32)]) -> u32 {
829    edges.sort_unstable();
830    let mut open = 0i32;
831    let mut most = 0;
832    for (_, edge) in edges.iter() {
833        open += edge;
834        most = most.max(open);
835    }
836    u32::try_from(most).unwrap_or(0)
837}
838
839/// The jobs that started on a warm runner and the others, and their median waits.
840fn starts(jobs: &[&Ran], kept_since: u64) -> api::Starts {
841    let (warm, cold): (Vec<&Ran>, Vec<&Ran>) = jobs
842        .iter()
843        .filter(|job| job.started_at.is_some())
844        .partition(|job| job.runner_started_at < job.queued_at);
845    let count = |jobs: &[&Ran]| u32::try_from(jobs.len()).unwrap_or(u32::MAX);
846    api::Starts {
847        warm: count(&warm),
848        warm_p50: waits(&warm, kept_since).p50,
849        cold: count(&cold),
850        cold_p50: waits(&cold, kept_since).p50,
851    }
852}
853
854/// Nearest-rank percentiles; all zero for no values.
855pub(crate) fn spread(mut values: Vec<u64>) -> Spread {
856    values.sort_unstable();
857    let rank = |percent: usize| {
858        let index = (values.len() * percent).div_ceil(100).saturating_sub(1);
859        values.get(index).copied().unwrap_or(0)
860    };
861    Spread {
862        p50: rank(50),
863        p95: rank(95),
864        p99: rank(99),
865        max: values.last().copied().unwrap_or(0),
866    }
867}
868
869pub mod auto;
870pub mod memory;
871
872#[cfg(test)]
873mod tests;