Skip to main content

runnerd_core/sizing/
auto.rs

1//! Auto sizing: which profiles' `memory`, `slots` and `cpus` the daemon changes now, from the advice, the runs since
2//! each profile's last change and the limits `[sizing]` and each profile set. Pure: the daemon reads the history and
3//! when each profile last changed, writes each change through the config check as `PUT /v1/config` does, and records
4//! it. Never lowers a profile while a job is on its cap, never changes `memory` from fewer than `[sizing] min_jobs`
5//! jobs, never lowers within `[sizing] interval` of a profile's last change or raises within `raise_interval`, never
6//! leaves a profile outside its bounds, and sizes each profile against the budget the changes before it in the same
7//! look leave. Reads `cpus` only from runs at the profile's current `cpus` since its last change and since the daemon
8//! got them. Under `caps` admission raises them only on those runs' CPU averages, never on peaks: a parallel build
9//! peaks at whatever cap it gets, and there `cpus` take budget. Under `measured`, where a running job reserves its
10//! average, runs the cap held back raise them too, within what the CPU budget holds at caps, and nothing lowers them.
11//! Under `caps` lowers them only when the cap held none of those runs back, never under their highest peak. A run
12//! the cap held back is one its quota throttled in 15% of its run or more, or, without that figure, one whose bursts
13//! met the cap (ADRs 0075 and 0079); under `measured` a raise goes on only while the one before made the job's runs
14//! faster or less throttled.
15
16use std::collections::BTreeMap;
17use std::fmt::Write as _;
18
19use crate::api::{
20    Advice, ProfileSizing, Resize, Sizing, SizingChange, SizingRefused, ago, cores, duration,
21    job_title,
22};
23use crate::config::{Admission, ByteSize, Config, Profile, cpu_budget};
24
25use super::{
26    BUSY, CpusSet, GRANULE, HELD, History, Throttling, WAITED, Window, advise, busy, first_runner,
27    spread, waits,
28};
29
30/// The fewest runs a raise of `slots` or `cpus` reads: the jobs queued since the profile's last change, or one job's
31/// runs at its current `cpus`. It does not wait for `min_jobs`: a slot too few costs every queued job a wait now.
32pub(crate) const RAISE_RUNS: u64 = 3;
33
34/// A job whose runs averaged this share of their CPU cap or more, in percent, at the median, is held back by it over
35/// the whole run, not in a burst: its checkout, cache restore and upload steps barely use a CPU, so the rest of it
36/// ran at the cap. On the owner's history no job's median came past 37%, whatever its cap: their builds are bursts.
37const BOUND: u64 = 70;
38
39/// `cpus` come down toward this many times the heaviest job's p95 CPU average, and never under the highest peak of
40/// the runs read: a job back at the cap would average half of it, far under `BOUND`, so a lowering never asks for
41/// the raise back.
42const HEADROOM: u64 = 2;
43
44/// A run without a throttling figure, as one from before schema 17, whose CPU peak came this close to its cap, in
45/// percent, met it in a burst, and counts as held back (ADR 0075). Peaks are the highest 2-second interval, so one
46/// can pass the cap a little.
47const MET: u64 = 95;
48
49/// What auto sizing reads besides the config and the history.
50#[derive(Debug, Clone, Copy)]
51pub struct Context<'run> {
52    /// The slice's `MemoryMax`; `None` when it is unlimited.
53    pub memory_max: Option<u64>,
54    /// The slice's CPUs, in millicores; `None` when they could not be read, and then `cpus` are never raised.
55    pub cpus: Option<u64>,
56    /// The history's window; `now` is when the changes are made.
57    pub window: Window,
58    /// When auto sizing last changed each profile, in seconds, by name, however long ago.
59    pub last: &'run BTreeMap<String, u64>,
60    /// Each profile's `cpus` as the daemon ran them, oldest first: what a `cpus` change reads runs since, as a
61    /// hand edit, a reload or an undo leaves no change of auto sizing's.
62    pub cpus_set: &'run [CpusSet],
63    /// How many runners each profile runs now, by name.
64    pub running: &'run BTreeMap<String, u32>,
65}
66
67/// The changes to make now, in order, one per profile at most. Empty unless `[sizing] auto` is on.
68///
69/// A change that lowers `memory` or `cpus` waits `[sizing] interval` after the profile's last change; one that only
70/// raises waits `raise_interval`. A lowering moves `memory` toward the advice, and `cpus` move toward what their runs
71/// reach, by at most `[sizing] max_step` percent; a raise of `memory` goes straight to the advice, which only a run
72/// that met the cap gives. `memory` stays within the profile's `min_memory` and `max_memory`, `cpus` within the
73/// slice's CPUs. A lowering that went too far is taken back at once (`ProfileSizing::revert`). A profile whose jobs
74/// waited for a slot, or whose slots were busy, since its last change gets one more slot when every profile's slots
75/// still fit `MemoryMax`: at their caps under `caps` admission, at their jobs' p95 peaks under `measured`; at most
76/// `max_slots` when set, and never under what runs. Under `caps` a lowered `memory` adds the slots the advice gives. Each change is sized as if the ones before it were written: they take
77/// budget the later ones cannot.
78///
79/// `cpus` go up `max_step` percent, at least 1, when one job's runs at them since the profile's last change and since
80/// the daemon got them (`Context::cpus_set`), 3 at least, averaged `BOUND` percent of them at the median, or under
81/// `measured` admission were held back by them (throttled, or without that figure met in a burst) while the raise
82/// before helped them (`unhelped`); up to the slice's CPUs, and with a CPU budget only as far as it holds: every
83/// profile's `slots × cpus` under `caps`; under `measured`, what that admission reserves at caps, every profile's
84/// warm runners and one more runner at the largest cap (`Budget::at_caps`). Under `caps` admission they come down, `interval` after the last change and by `max_step`
85/// percent at most, toward `HEADROOM` times the heaviest job's p95 average or the highest peak of those runs,
86/// whichever is larger, rounded up to whole CPUs, at least 1, once `min_jobs` such runs say so, every job among them
87/// has a measured average, and the cap held none of them back. Under `measured` they never come down: they bound no
88/// slot there. Only successful runs with a measured average count; see [`next_look`] for the raises it cannot make.
89pub fn changes(config: &Config, history: &History, context: Context<'_>) -> Vec<SizingChange> {
90    next_look(config, history, context).changes
91}
92
93/// What a look does: the changes [`changes`] picks, and the `cpus` raises it cannot make.
94#[derive(Debug, Clone, Default, PartialEq, Eq)]
95pub struct Look {
96    /// The changes to make now, in order, one per profile at most.
97    pub changes: Vec<SizingChange>,
98    /// The profiles whose jobs the CPU cap holds back but whose `cpus` cannot go up: the slice's CPUs are unknown or
99    /// all theirs, the CPU budget has no room, or under `measured` admission the raise before did not help them.
100    pub refused: Vec<SizingRefused>,
101}
102
103/// The changes [`changes`] picks, and the `cpus` raises the same look cannot make.
104pub fn next_look(config: &Config, history: &History, context: Context<'_>) -> Look {
105    let rules = &config.sizing;
106    if !rules.auto {
107        return Look::default();
108    }
109    let window = context.window;
110    let sizing = advise(config, context.memory_max, history, window);
111    let now = window.now / 1000;
112    let mut budget = Budget::new(config, &sizing.profiles);
113    let mut changes = Vec::new();
114    let mut refused = Vec::new();
115    for advised in &sizing.profiles {
116        let Some(profile) = config.profiles.get(&advised.name) else {
117            continue;
118        };
119        let last = context.last.get(&advised.name).copied();
120        let since = last.map_or(u64::MAX, |at| now.saturating_sub(at));
121        if advised.revert.is_some() {
122            match reverted(config, profile, advised, &sizing, &context, &budget) {
123                Revert::Write(change) => {
124                    budget.take(&advised.name, profile, change.from, change.to);
125                    changes.push(change);
126                    continue;
127                }
128                Revert::Wait => continue,
129                // Raised as far as its bounds allow, as any raise is.
130                Revert::Outside => {}
131            }
132        }
133        if since < rules.raise_after().as_secs() {
134            continue;
135        }
136        let lowering = if since >= rules.interval.as_secs() {
137            Lowering::Allowed
138        } else {
139            Lowering::Held
140        };
141        let fresh = Fresh::read(history, advised, last, window);
142        let mut reasons = Vec::new();
143        let memory = memory(config, profile, advised.advice, lowering);
144        let running = context.running.get(&advised.name).copied().unwrap_or(0);
145        let slots = match config.host.admission {
146            Admission::Caps => {
147                caps_slots(profile, advised, &fresh, memory, &context, &budget, running)
148            }
149            Admission::Measured => {
150                measured_slots(config, &sizing.profiles, advised, &fresh, &context, &budget)
151            }
152        };
153        let (slots, cpus) = cpus_and_slots(
154            config,
155            profile,
156            advised,
157            history,
158            fresh.start,
159            &context,
160            &budget,
161            slots,
162            lowering,
163        );
164        if memory != profile.memory.0 {
165            reasons.push(memory_reason(
166                &sizing,
167                advised,
168                memory,
169                slots,
170                config.sizing.max_step,
171            ));
172        }
173        // Under caps a lowered memory's slots are its line's.
174        let advised_slots = config.host.admission == Admission::Caps && memory < profile.memory.0;
175        if slots > profile.slots && !advised_slots {
176            reasons.push(fresh.waited(last.is_some()));
177        }
178        let cpus = cpus.taken(&advised.name, &mut reasons, &mut refused);
179        let from = Resize {
180            memory: profile.memory.0,
181            slots: profile.slots,
182            cpus: cpus.map(|_| profile.cpus),
183        };
184        let to = Resize {
185            memory,
186            slots,
187            cpus,
188        };
189        if to == from || slots == 0 {
190            continue;
191        }
192        budget.take(&advised.name, profile, from, to);
193        changes.push(SizingChange {
194            at: now,
195            profile: advised.name.clone(),
196            from,
197            to,
198            reason: reasons.join("; "),
199            uncertain: false,
200        });
201    }
202    Look { changes, refused }
203}
204
205/// How far back a config that lowers `memory` is compared with auto sizing's raises, in seconds: a day.
206pub const UNDONE_RAISES: u64 = 24 * 3600;
207
208/// What a new config undoes of auto sizing's `memory` raises: a line for each profile whose `memory` it lowers under
209/// what one of `changes` raised it to in the `UNDONE_RAISES` before `now` (seconds), as a config saved from a text read
210/// before the raise does. A raise comes only after the jobs needed more than the cap (ADR 0070), so they may run out
211/// of memory again. The config is not refused: the owner may mean it.
212pub fn undone_raises(
213    running: &Config,
214    new: &Config,
215    changes: &[SizingChange],
216    now: u64,
217) -> Vec<String> {
218    new.profiles
219        .iter()
220        .filter_map(|(name, profile)| {
221            let memory = profile.memory.0;
222            let before = running.profiles.get(name)?.memory.0;
223            let raise = changes
224                .iter()
225                .filter(|change| {
226                    change.profile == *name
227                        && change.to.memory > change.from.memory
228                        && now.saturating_sub(change.at) < UNDONE_RAISES
229                })
230                .max_by_key(|change| change.at)?;
231            (memory < before && memory < raise.to.memory).then(|| {
232                format!(
233                    "{name}'s memory goes to {}, under the {} auto sizing raised it to {} because its jobs needed \
234                     more than {}: they may run out of memory again",
235                    ByteSize(memory),
236                    ByteSize(raise.to.memory),
237                    ago(raise.at, now),
238                    ByteSize(raise.from.memory)
239                )
240            })
241        })
242        .collect()
243}
244
245/// Whether a change may lower `memory` or `cpus`: only `interval` after the profile's last change.
246#[derive(Debug, Clone, Copy, PartialEq, Eq)]
247enum Lowering {
248    Allowed,
249    Held,
250}
251
252/// The budget as the changes picked so far leave it.
253struct Budget {
254    /// `slots × memory` over all profiles, with the mirror.
255    caps: u64,
256    /// `slots × cpus` over all profiles, in millicores.
257    cpus: u64,
258    /// Each profile's slots.
259    slots: BTreeMap<String, u32>,
260    /// Each profile's `cpus`.
261    each: BTreeMap<String, u32>,
262}
263
264impl Budget {
265    /// Takes what a change of `profile` from `from` to `to` adds, and gives back what it frees.
266    fn take(&mut self, name: &str, profile: &Profile, from: Resize, to: Resize) {
267        self.caps = self
268            .caps
269            .saturating_sub(from.memory.saturating_mul(u64::from(from.slots)))
270            .saturating_add(to.memory.saturating_mul(u64::from(to.slots)));
271        let millicores = |resize: Resize| {
272            u64::from(resize.cpus.unwrap_or(profile.cpus)) * 1000 * u64::from(resize.slots)
273        };
274        self.cpus = self
275            .cpus
276            .saturating_sub(millicores(from))
277            .saturating_add(millicores(to));
278        self.slots.insert(name.to_owned(), to.slots);
279        self.each
280            .insert(name.to_owned(), to.cpus.unwrap_or(profile.cpus));
281    }
282
283    /// The budget the config takes as it is.
284    fn new(config: &Config, profiles: &[ProfileSizing]) -> Budget {
285        Budget {
286            caps: config.memory_caps().map_or(u64::MAX, |caps| caps.0),
287            cpus: config
288                .profiles
289                .values()
290                .map(|profile| u64::from(profile.cpus) * 1000 * u64::from(profile.slots))
291                .sum(),
292            slots: profiles
293                .iter()
294                .map(|advised| (advised.name.clone(), advised.slots))
295                .collect(),
296            each: config
297                .profiles
298                .iter()
299                .map(|(name, profile)| (name.clone(), profile.cpus))
300                .collect(),
301        }
302    }
303
304    /// The CPUs, millicores, that measured admission holds at caps with `name` at `cpus`: every profile's warm
305    /// runners idle at their caps (`warm_runners`), and one more runner at the largest cap, as one of a job with no
306    /// prediction reserves.
307    fn at_caps(&self, config: &Config, name: &str, cpus: u32) -> u64 {
308        let each = |other: &str| {
309            if other == name {
310                cpus
311            } else {
312                self.each.get(other).copied().unwrap_or(0)
313            }
314        };
315        let warm: u64 = config
316            .profiles
317            .keys()
318            .map(|other| {
319                let slots = self.slots.get(other).copied().unwrap_or(0);
320                u64::from(warm_runners(config, other, slots)) * u64::from(each(other))
321            })
322            .sum();
323        let largest = config
324            .profiles
325            .keys()
326            .map(|other| each(other))
327            .max()
328            .unwrap_or(0);
329        (warm + u64::from(largest)) * 1000
330    }
331}
332
333/// How many warm runners `profile`'s pools keep at most, with `slots`: their `warm` added up, at most its slots.
334fn warm_runners(config: &Config, profile: &str, slots: u32) -> u32 {
335    config
336        .repositories
337        .iter()
338        .filter(|repository| repository.profile == profile)
339        .map(|repository| repository.warm)
340        .sum::<u32>()
341        .min(slots)
342}
343
344/// What the jobs queued since a profile's last change say about its slots: a raise reads only them, so one slot
345/// that fixed a month's waits is not followed by another every `raise_interval`.
346struct Fresh {
347    /// When the evidence starts, in milliseconds: the last change, or the window's start.
348    start: u64,
349    jobs: u64,
350    /// Seconds from queued to started, p95.
351    wait: u64,
352    busy: u32,
353}
354
355impl Fresh {
356    /// The profile's jobs queued since `last` (seconds), or in the whole window without a last change.
357    fn read(
358        history: &History,
359        advised: &ProfileSizing,
360        last: Option<u64>,
361        window: Window,
362    ) -> Fresh {
363        let start = last.map_or(window.since, |at| at.saturating_mul(1000).max(window.since));
364        let jobs: Vec<_> = history
365            .jobs
366            .iter()
367            .filter(|job| job.profile == advised.name && job.queued_at >= start)
368            .collect();
369        Fresh {
370            start,
371            jobs: jobs.len() as u64,
372            wait: waits(&jobs, history.kept_since).p95,
373            busy: busy(
374                history,
375                &advised.name,
376                advised.slots,
377                first_runner(history, start),
378                window.now,
379            ),
380        }
381    }
382
383    /// Whether another slot would help: enough jobs, which waited a minute at p95 or kept the slots busy half the
384    /// time.
385    fn wants_slots(&self) -> bool {
386        self.jobs >= RAISE_RUNS && (self.wait >= WAITED || self.busy >= BUSY)
387    }
388
389    /// Why a slot is added.
390    fn waited(&self, changed: bool) -> String {
391        format!(
392            "{} jobs {}waited {}s for a slot (p95) and slots were busy {}%; one more fits the slice beside the \
393             other profiles'",
394            self.jobs,
395            if changed {
396                "since its last change "
397            } else {
398                ""
399            },
400            self.wait,
401            self.busy
402        )
403    }
404}
405
406/// Why `memory` changes, as the advice line says it of the `memory` and `slots` this change writes, not the
407/// advice's own: a step of `max_step` stops short of a lowering's memory, and the slots that fit follow. A change
408/// short of the advice says what it goes toward.
409fn memory_reason(
410    sizing: &Sizing,
411    advised: &ProfileSizing,
412    memory: u64,
413    slots: u32,
414    max_step: u32,
415) -> String {
416    let made = ProfileSizing {
417        advice: match advised.advice {
418            Advice::Lower { .. } => Advice::Lower { memory, slots },
419            Advice::Raise { .. } => Advice::Raise { memory, slots },
420            other => other,
421        },
422        ..advised.clone()
423    };
424    let line = sizing.memory_line(&made);
425    match advised.advice.change() {
426        Some(advice) if advice.memory != memory => format!(
427            "{line}; a step toward {}, at most {max_step}% a change",
428            ByteSize(advice.memory)
429        ),
430        _ => line,
431    }
432}
433
434/// What a look does with a lowering that went too far.
435enum Revert {
436    /// Takes it back with this change.
437    Write(SizingChange),
438    /// Waits while more runners run than the slots it gives back hold, or while the changes before it in this look
439    /// leave the slice no slot at its `memory`: nothing else changes the profile meanwhile.
440    Wait,
441    /// It gets no raise: the profile is sized as any other.
442    Outside,
443}
444
445/// The change that takes back a lowering that went too far (`ProfileSizing::revert`): straight to the `memory`
446/// it came from, or as far toward it as `[host] memory_ceiling` and `max_memory` allow, and, under caps, the slots it
447/// had, without waiting for `raise_interval` or keeping to `max_step`, as an undo would.
448fn reverted(
449    config: &Config,
450    profile: &Profile,
451    advised: &ProfileSizing,
452    sizing: &Sizing,
453    context: &Context<'_>,
454    budget: &Budget,
455) -> Revert {
456    let Advice::Raise { memory, slots } = advised.advice else {
457        return Revert::Outside;
458    };
459    let from = Resize {
460        memory: profile.memory.0,
461        slots: profile.slots,
462        cpus: None,
463    };
464    // The advice holds the slots the slice holds beside the config's other profiles; under caps, the changes before
465    // it in this look may have taken some of that.
466    let slots = match (config.host.admission, context.memory_max) {
467        (Admission::Caps, Some(memory_max)) => {
468            let share = profile.memory.0.saturating_mul(u64::from(profile.slots));
469            let room = memory_max.saturating_sub(budget.caps.saturating_sub(share));
470            slots.min(u32::try_from(room / memory.max(1)).unwrap_or(u32::MAX))
471        }
472        _ => slots,
473    };
474    if slots == 0 {
475        return Revert::Wait;
476    }
477    let running = context.running.get(&advised.name).copied().unwrap_or(0);
478    let to = Resize {
479        memory,
480        slots,
481        cpus: None,
482    };
483    if config.host.admission == Admission::Caps && running > slots {
484        return Revert::Wait;
485    }
486    Revert::Write(SizingChange {
487        at: sizing.until,
488        profile: advised.name.clone(),
489        from,
490        to,
491        reason: sizing.memory_line(advised),
492        uncertain: false,
493    })
494}
495
496/// The profile's next `memory`: a lowering at most `max_step` percent away, in steps of `GRANULE`, and only while
497/// `lowering` allows it; a raise straight to the advice's, since only a run that met the cap raises it (ADR 0070),
498/// and a kill is direct evidence. The advice keeps to `min_memory` and `max_memory`, and lowers nothing while a job
499/// is on its cap.
500fn memory(config: &Config, profile: &Profile, advice: Advice, lowering: Lowering) -> u64 {
501    let current = profile.memory.0;
502    let step = current.saturating_mul(u64::from(config.sizing.max_step)) / 100;
503    match advice {
504        Advice::Lower { memory, .. } if lowering == Lowering::Allowed => {
505            let floor = current
506                .saturating_sub(step)
507                .div_ceil(GRANULE)
508                .saturating_mul(GRANULE);
509            memory.max(floor).min(current)
510        }
511        Advice::Raise { memory, .. } => memory,
512        _ => current,
513    }
514}
515
516/// Under `caps`: as many slots as the advice gives for the new memory. A lowering whose jobs waited adds as many as
517/// the memory the slots take now holds, up to the advice's slots, which keep to `max_slots`; a raise keeps as many as the slice holds beside the other
518/// profiles, and 0, no change, while more than that run. With the memory kept, one more slot when its jobs waited
519/// since the last change and its cap fits `MemoryMax` beside every other cap, up to `max_slots`. Otherwise the same.
520fn caps_slots(
521    profile: &Profile,
522    advised: &ProfileSizing,
523    fresh: &Fresh,
524    memory: u64,
525    context: &Context<'_>,
526    budget: &Budget,
527    running: u32,
528) -> u32 {
529    let current = profile.slots;
530    let fit = |room: u64| u32::try_from(room / memory.max(1)).unwrap_or(u32::MAX);
531    // A step toward the advice's memory fits no more slots than the advice gives, which keeps to `max_slots`.
532    if let Advice::Lower { slots, .. } = advised.advice
533        && memory < profile.memory.0
534        && advised.wants_slots
535    {
536        let share = profile.memory.0.saturating_mul(u64::from(current));
537        return fit(share).min(slots).max(current);
538    }
539    let Some(memory_max) = context.memory_max else {
540        return current;
541    };
542    if memory > profile.memory.0 {
543        let share = profile.memory.0.saturating_mul(u64::from(current));
544        let room = memory_max.saturating_sub(budget.caps.saturating_sub(share));
545        // Fewer slots than run would leave the running ones over the budget: wait for some to finish.
546        let slots = fit(room).min(current);
547        return if slots < running { 0 } else { slots };
548    }
549    if fresh.wants_slots()
550        && profile.max_slots.is_none_or(|max| current < max)
551        && budget.caps.saturating_add(memory) <= memory_max
552    {
553        return current + 1;
554    }
555    current
556}
557
558/// Under `measured`: one more slot when its jobs waited since the last change and every profile's slots, this one's
559/// with the new one, fit the slice beside the mirror at their jobs' p95 peaks (at its cap, a profile with fewer than
560/// `min_jobs` jobs), up to `max_slots`, with the slots the changes before it gave. Without `max_slots` or a
561/// `MemoryMax`, nothing bounds slots, so none is added. Otherwise the same.
562fn measured_slots(
563    config: &Config,
564    profiles: &[ProfileSizing],
565    advised: &ProfileSizing,
566    fresh: &Fresh,
567    context: &Context<'_>,
568    budget: &Budget,
569) -> u32 {
570    let current = advised.slots;
571    let max_slots = config
572        .profiles
573        .get(&advised.name)
574        .and_then(|profile| profile.max_slots);
575    if !fresh.wants_slots() || max_slots.is_some_and(|max| max <= current) {
576        return current;
577    }
578    let Some(memory_max) = context.memory_max else {
579        return if max_slots.is_some() {
580            current + 1
581        } else {
582            current
583        };
584    };
585    let peaks: u64 = profiles
586        .iter()
587        .map(|other| {
588            let peak = if matches!(other.advice, Advice::TooFew { .. }) {
589                other.memory
590            } else {
591                other.peaks.memory.p95
592            };
593            let slots = if other.name == advised.name {
594                current + 1
595            } else {
596                budget
597                    .slots
598                    .get(&other.name)
599                    .copied()
600                    .unwrap_or(other.slots)
601            };
602            peak.saturating_mul(u64::from(slots))
603        })
604        .fold(config.mirror_memory(), u64::saturating_add);
605    if peaks <= memory_max {
606        current + 1
607    } else {
608        current
609    }
610}
611
612/// The profile's next `cpus` and `slots`, from the `slots` memory and waits chose: under `caps` with a CPU budget,
613/// slots past what the budget holds at the new `cpus` are dropped, and the `cpus` sized again at the slots that stay,
614/// so an extra slot the budget refuses does not also refuse a CPU raise that fits without it.
615#[expect(
616    clippy::too_many_arguments,
617    reason = "each is one thing a CPU change reads; a struct for them would be read here only"
618)]
619fn cpus_and_slots(
620    config: &Config,
621    profile: &Profile,
622    advised: &ProfileSizing,
623    history: &History,
624    since: u64,
625    context: &Context<'_>,
626    budget: &Budget,
627    slots: u32,
628    lowering: Lowering,
629) -> (u32, CpuStep) {
630    let size = |slots: u32| {
631        cpus(
632            config, profile, advised, history, since, context, budget, slots, lowering,
633        )
634    };
635    // Slots the CPU budget cannot hold would wait for CPU anyway, and their waits would ask for more.
636    let fit = |slots: u32, cpus: &CpuStep| {
637        let cpus = match cpus {
638            CpuStep::To(cpus) => cpus.to,
639            CpuStep::Keep | CpuStep::Refused(_) => profile.cpus,
640        };
641        if slots > profile.slots {
642            cpu_slots(config, profile, context, budget, cpus)
643                .map_or(slots, |fit| slots.min(fit.max(profile.slots)))
644        } else {
645            slots
646        }
647    };
648    let mut cpus = size(slots);
649    let fitted = fit(slots, &cpus);
650    if fitted < slots {
651        cpus = size(fitted);
652    }
653    (fit(fitted, &cpus), cpus)
654}
655
656/// Under `caps` admission with a CPU budget, the most slots of the profile at `cpus` each that fit the budget beside
657/// every other profile's `slots × cpus`, as the changes before it left them; none more than it has when the slice's
658/// CPUs are unknown. `None` when no CPU budget bounds slots.
659fn cpu_slots(
660    config: &Config,
661    profile: &Profile,
662    context: &Context<'_>,
663    budget: &Budget,
664    cpus: u32,
665) -> Option<u32> {
666    let (Admission::Caps, Some(overcommit)) = (config.host.admission, config.host.cpu_overcommit)
667    else {
668        return None;
669    };
670    let Some(slice) = context.cpus else {
671        return Some(profile.slots);
672    };
673    let others = budget
674        .cpus
675        .saturating_sub(u64::from(profile.cpus) * 1000 * u64::from(profile.slots));
676    let room = cpu_budget(slice, overcommit).saturating_sub(others);
677    Some(u32::try_from(room / (u64::from(cpus.max(1)) * 1000)).unwrap_or(u32::MAX))
678}
679
680/// What a look does with a profile's `cpus`.
681enum CpuStep {
682    Keep,
683    To(Cpus),
684    /// Its jobs are held back by the cap, and this says why it cannot go up.
685    Refused(String),
686}
687
688impl CpuStep {
689    /// The new `cpus`, if any, its reason added to `reasons`, or a refused raise to `refused`.
690    fn taken(
691        self,
692        profile: &str,
693        reasons: &mut Vec<String>,
694        refused: &mut Vec<SizingRefused>,
695    ) -> Option<u32> {
696        match self {
697            CpuStep::To(cpus) => {
698                reasons.push(cpus.reason);
699                Some(cpus.to)
700            }
701            CpuStep::Refused(reason) => {
702                refused.push(SizingRefused {
703                    profile: profile.to_owned(),
704                    reason,
705                });
706                None
707            }
708            CpuStep::Keep => None,
709        }
710    }
711}
712
713/// A new `cpus` and why.
714struct Cpus {
715    to: u32,
716    reason: String,
717}
718
719/// A job: its repository, workflow and name.
720type JobKey<'run> = (&'run str, Option<&'run str>, &'run str);
721
722/// When the daemon started running the profile with `cpus`, in ms, by `set`: its first event since the last one
723/// with other `cpus`. `now` when its latest has other `cpus`, as before a reload announces them; 0 with no events.
724fn cpus_since(set: &[CpusSet], profile: &str, cpus: u32, now: u64) -> u64 {
725    let mut since = None;
726    let mut seen = false;
727    for event in set.iter().filter(|event| event.profile == profile) {
728        seen = true;
729        if event.cpus != cpus {
730            since = None;
731        } else if since.is_none() {
732            since = Some(event.at);
733        }
734    }
735    since.unwrap_or(if seen { now } else { 0 })
736}
737
738/// What one job's runs a `cpus` change reads say.
739#[derive(Default)]
740struct JobCpu {
741    /// Their measured averages, millicores.
742    averages: Vec<u64>,
743    /// The highest of their peaks, millicores.
744    peak: u64,
745    /// How many of them their quota throttled in `HELD` percent of their run or more.
746    throttled: u64,
747    /// How many of them without a throttling figure peaked within `MET` percent of the cap.
748    peaked: u64,
749    /// What their quota did to each of them.
750    runs: Vec<Throttling>,
751}
752
753impl JobCpu {
754    /// How many of them the cap held back: throttled where that was measured, else met in a burst.
755    fn held(&self) -> u64 {
756        self.throttled + self.peaked
757    }
758
759    /// Why `job`'s runs at `current` CPUs raise them under measured admission.
760    fn held_reason(&self, job: JobKey<'_>, current: u32) -> String {
761        let how = if self.peaked == 0 {
762            format!("throttled in {HELD}% of their run or more")
763        } else {
764            format!(
765                "throttled in {HELD}% of their run or more, or peaking at the cap where that was not measured"
766            )
767        };
768        format!(
769            "{} runs of {} were held back by its {current} CPUs, {how}: under measured admission they bound no slot, \
770             so the cap only slows them",
771            self.held(),
772            job_named(job)
773        )
774    }
775}
776
777/// Whether the cap held a run back. With a throttling figure that alone says so, whatever the run's peak: a 2-second
778/// peak at the cap says nothing of what the cap cost. Without one, as in runs from before schema 17 or on a kernel
779/// that keeps none, its peak says so as it did before (ADR 0075): missing is not read as never throttled.
780enum Hold {
781    Throttled,
782    Peaked,
783    Free,
784}
785
786impl Hold {
787    fn of(job: &super::Ran, cap: u64) -> Hold {
788        match job.throttling().held() {
789            Some(true) => Hold::Throttled,
790            Some(false) => Hold::Free,
791            None => Hold::peaked(job, cap),
792        }
793    }
794
795    fn peaked(job: &super::Ran, cap: u64) -> Hold {
796        if job.cpu_peak.saturating_mul(100) >= cap.saturating_mul(MET) {
797            Hold::Peaked
798        } else {
799            Hold::Free
800        }
801    }
802}
803
804/// The runs of the profile a `cpus` change reads, by job: successful runs whose container had `cap`, queued at or
805/// after `since` (ms), the later of the profile's last change and when it got these `cpus` (`cpus_since`). A run
806/// without a measured average adds none; nor does an average of 0, which only a run sampled once records. Its job is
807/// still listed, so a lowering can tell a job it knows nothing of from one it lacks.
808fn runs_at<'run>(
809    history: &'run History,
810    profile: &str,
811    cap: u64,
812    since: u64,
813) -> BTreeMap<JobKey<'run>, JobCpu> {
814    let mut jobs: BTreeMap<JobKey<'run>, JobCpu> = BTreeMap::new();
815    for job in &history.jobs {
816        if job.profile == profile
817            && job.cpu_cap == Some(cap)
818            && job.succeeded
819            && job.queued_at >= since
820        {
821            let read = jobs
822                .entry((&job.repository, job.workflow.as_deref(), &job.name))
823                .or_default();
824            read.averages
825                .extend(job.cpu_average.filter(|average| *average > 0));
826            read.peak = read.peak.max(job.cpu_peak);
827            match Hold::of(job, cap) {
828                Hold::Throttled => read.throttled += 1,
829                Hold::Peaked => read.peaked += 1,
830                Hold::Free => {}
831            }
832            read.runs.push(job.throttling());
833        }
834    }
835    jobs
836}
837
838/// One successful run of a job in a profile, as [`unhelped_raise`] reads it.
839#[derive(Debug, Clone, Copy, PartialEq, Eq)]
840pub struct CpuRun {
841    /// Its container's CPU cap, millicores, when recorded.
842    pub cap: Option<u64>,
843    /// When it was queued, ms.
844    pub queued_at: u64,
845    /// What its quota did to it.
846    pub throttling: Throttling,
847}
848
849/// A figure at the median of a job's runs at its current `cpus` and at the `cpus` before.
850#[derive(Debug, Clone, Copy, PartialEq, Eq)]
851pub struct Medians {
852    /// At its current `cpus`.
853    pub now: u64,
854    /// At the `cpus` before.
855    pub before: u64,
856}
857
858/// A raise of `cpus` that did not help a job: its runs neither took less time nor were throttled in less of their run.
859#[derive(Debug, Clone, Copy, PartialEq, Eq)]
860pub struct Unhelped {
861    /// The CPU cap before, millicores.
862    pub from: u64,
863    /// How long its runs took, ms, where that is known on both sides.
864    pub took: Option<Medians>,
865    /// The share of their run their quota throttled them in, per mille, where that is known on both sides.
866    pub throttled: Option<Medians>,
867}
868
869/// Whether the raise that brought a job to `cap` (millicores) did not help it, by `runs`, its successful runs in one
870/// profile at any cap, and `now`, those at `cap` the reader counts; `None` when it did, or when nothing says: no
871/// raise came before, as when its latest runs at another cap had more, or fewer than `RAISE_RUNS` runs at the cap
872/// before. It helped when its runs at `cap` took less time at the median than at the cap before, or were throttled
873/// in less of their run. A tool that sizes its pool from the quota (the JVM's `availableProcessors`, cargo's `-j`,
874/// Go's `GOMAXPROCS`) starts more workers at each raise and stays throttled, running no faster: its raises stop
875/// there, as more `cpus` would only take memory and weight (ADR 0079).
876pub fn unhelped_raise(runs: &[CpuRun], cap: u64, now: &[Throttling]) -> Option<Unhelped> {
877    let from = runs
878        .iter()
879        .filter(|run| run.cap.is_some_and(|other| other != cap))
880        .max_by_key(|run| run.queued_at)?
881        .cap
882        .filter(|before| *before < cap)?;
883    let at_before: Vec<Throttling> = runs
884        .iter()
885        .filter(|run| run.cap == Some(from))
886        .map(|run| run.throttling)
887        .collect();
888    if (at_before.len() as u64) < RAISE_RUNS {
889        return None;
890    }
891    let median = |runs: &[Throttling], figure: fn(Throttling) -> Option<u64>| {
892        let values: Vec<u64> = runs.iter().copied().filter_map(figure).collect();
893        (!values.is_empty()).then(|| spread(values).p50)
894    };
895    let medians = |figure: fn(Throttling) -> Option<u64>| {
896        Some(Medians {
897            now: median(now, figure)?,
898            before: median(&at_before, figure)?,
899        })
900    };
901    let took = medians(Throttling::took);
902    let throttled = medians(Throttling::share);
903    let helped = |medians: Option<Medians>| medians.map(|medians| medians.now < medians.before);
904    match (helped(took), helped(throttled)) {
905        (None, None) | (Some(true), _) | (_, Some(true)) => None,
906        _ => Some(Unhelped {
907            from,
908            took,
909            throttled,
910        }),
911    }
912}
913
914/// Why the raise before did not help `job`, whose runs at `cap` are `now`, as [`unhelped_raise`] finds it.
915fn unhelped(
916    history: &History,
917    profile: &str,
918    job: JobKey<'_>,
919    cap: u64,
920    now: &JobCpu,
921) -> Option<String> {
922    let runs: Vec<CpuRun> = history
923        .jobs
924        .iter()
925        .filter(|run| {
926            run.profile == profile
927                && run.succeeded
928                && (
929                    run.repository.as_str(),
930                    run.workflow.as_deref(),
931                    run.name.as_str(),
932                ) == job
933        })
934        .map(|run| CpuRun {
935            cap: run.cpu_cap,
936            queued_at: run.queued_at,
937            throttling: run.throttling(),
938        })
939        .collect();
940    let unhelped = unhelped_raise(&runs, cap, &now.runs)?;
941    let mut why = format!(
942        "the raise from {} to its {} CPUs did not help it:",
943        unhelped.from / 1000,
944        cap / 1000
945    );
946    if let Some(took) = unhelped.took {
947        let _ = write!(
948            why,
949            " its runs took {} at the median, against {} before",
950            duration(took.now / 1000),
951            duration(took.before / 1000)
952        );
953    }
954    if let Some(throttled) = unhelped.throttled {
955        let joined = if unhelped.took.is_some() { "," } else { "" };
956        let _ = write!(
957            why,
958            "{joined} its quota throttled them in {}% of their run, against {}%",
959            throttled.now / 10,
960            throttled.before / 10
961        );
962    }
963    Some(why)
964}
965
966/// Under measured admission, why the runs the cap held back raise `cpus` at `cap`: the job with the most held runs,
967/// `RAISE_RUNS` at least, among those the raise before helped (`Ok`); or, when it helped none of them, why not, for
968/// the one with the most (`Err`). `None` when no job's runs were held back that often. A job the raise before did not
969/// help says nothing for another raise, but another held job still may.
970fn held_raise(
971    history: &History,
972    profile: &str,
973    jobs: &BTreeMap<JobKey<'_>, JobCpu>,
974    cap: u64,
975    current: u32,
976) -> Option<Result<String, String>> {
977    let (helped, refused): (Vec<_>, Vec<_>) = jobs
978        .iter()
979        .filter(|(_, read)| read.held() >= RAISE_RUNS)
980        .map(|(job, read)| (*job, read, unhelped(history, profile, *job, cap, read)))
981        .partition(|(_, _, why)| why.is_none());
982    if let Some((job, read, _)) = helped.into_iter().max_by_key(|(_, read, _)| read.held()) {
983        return Some(Ok(read.held_reason(job, current)));
984    }
985    let (job, read, why) = refused.into_iter().max_by_key(|(_, read, _)| read.held())?;
986    Some(Err(format!(
987        "{}; {}",
988        read.held_reason(job, current),
989        why.unwrap_or_default()
990    )))
991}
992
993/// `owner/name workflow / job`, as a CPU change's reason names a job.
994fn job_named(job: JobKey<'_>) -> String {
995    let (repository, workflow, name) = job;
996    format!("{repository} {}", job_title(workflow, name, None))
997}
998
999/// A raise of `name`'s `cpus` held back by the cap, as `held` says: `step` more, up to the slice's CPUs, and with a
1000/// CPU budget only as many as it holds: under `caps` every profile's `slots × cpus`, under `measured` every profile's
1001/// warm runners and one more runner at the largest cap (`Budget::at_caps`). Refused, with why, when that is none.
1002#[expect(
1003    clippy::too_many_arguments,
1004    reason = "each is one thing a CPU raise reads; a struct for them would be read here only"
1005)]
1006fn raised(
1007    config: &Config,
1008    name: &str,
1009    profile: &Profile,
1010    context: &Context<'_>,
1011    budget: &Budget,
1012    slots: u32,
1013    step: u32,
1014    held: String,
1015) -> CpuStep {
1016    let current = profile.cpus;
1017    let cap = u64::from(current) * 1000;
1018    let Some(slice) = context.cpus else {
1019        return CpuStep::Refused(format!("{held}; the slice's CPUs could not be read"));
1020    };
1021    let slice_cpus = u32::try_from(slice / 1000).unwrap_or(u32::MAX);
1022    let mut to = current.saturating_add(step).min(slice_cpus);
1023    let mut why = format!("it has all {slice_cpus} of the slice's CPUs");
1024    if let (Admission::Caps, Some(overcommit)) = (config.host.admission, config.host.cpu_overcommit)
1025    {
1026        let others = budget
1027            .cpus
1028            .saturating_sub(cap.saturating_mul(u64::from(profile.slots)));
1029        let room = cpu_budget(slice, overcommit).saturating_sub(others);
1030        let fit = room / 1000 / u64::from(slots.max(1));
1031        let fit = u32::try_from(fit).unwrap_or(u32::MAX);
1032        if fit < to {
1033            to = fit;
1034            why = format!(
1035                "{} CPUs for each of its {slots} slots do not fit the CPU budget beside the other profiles'",
1036                current.saturating_add(1)
1037            );
1038        }
1039    }
1040    // Under measured admission a running job reserves its average, whatever its cap, but an idle warm runner and a
1041    // runner whose job has no prediction reserve the cap.
1042    if let (Admission::Measured, Some(overcommit)) =
1043        (config.host.admission, config.host.cpu_overcommit)
1044    {
1045        let room = cpu_budget(slice, overcommit);
1046        while to > current && budget.at_caps(config, name, to) > room {
1047            to -= 1;
1048            why = format!(
1049                "{} CPUs do not fit the CPU budget with every profile's warm runners and one more runner at the \
1050                 largest cap",
1051                current.saturating_add(1)
1052            );
1053        }
1054    }
1055    if to > current {
1056        CpuStep::To(Cpus { to, reason: held })
1057    } else {
1058        CpuStep::Refused(format!("{held}; {why}"))
1059    }
1060}
1061
1062/// How many `cpus` one change moves a profile at `current` by: `[sizing] max_step` percent of them, at least 1.
1063pub(crate) fn cpu_step(config: &Config, current: u32) -> u32 {
1064    (current.saturating_mul(config.sizing.max_step) / 100).max(1)
1065}
1066
1067/// The profile's next `cpus`, from the CPU averages of its runs at its current `cpus` since `since` (ms), the last
1068/// change, and since it got them (`runs_at`). A raise, `max_step` percent, at least 1, when one job's `RAISE_RUNS`
1069/// runs or more averaged `BOUND` percent of the cap at the median, or under `measured` admission were held back by it
1070/// (kept, not refused, when there is no room; refused when the raise before did not help them): up to the slice's
1071/// CPUs, and with a CPU budget only as many as `raised` fits in it, at the `slots` this change gives; refused, with
1072/// why, when that is none. A lowering, under `caps`
1073/// admission while `lowering` allows it, with `min_jobs` runs, none of a job without a measured average and none the
1074/// cap held back: toward `HEADROOM` times the heaviest job's p95 average or the highest peak, whichever is larger,
1075/// rounded up to whole CPUs, at least 1, by at most `max_step` percent.
1076#[expect(
1077    clippy::too_many_arguments,
1078    reason = "each is one thing a CPU change reads; a struct for them would be read here only"
1079)]
1080fn cpus(
1081    config: &Config,
1082    profile: &Profile,
1083    advised: &ProfileSizing,
1084    history: &History,
1085    since: u64,
1086    context: &Context<'_>,
1087    budget: &Budget,
1088    slots: u32,
1089    lowering: Lowering,
1090) -> CpuStep {
1091    let current = profile.cpus;
1092    let cap = u64::from(current) * 1000;
1093    let since = since.max(cpus_since(
1094        context.cpus_set,
1095        &advised.name,
1096        current,
1097        context.window.now,
1098    ));
1099    let jobs = runs_at(history, &advised.name, cap, since);
1100    let step = cpu_step(config, current);
1101    let raise = |held| {
1102        raised(
1103            config,
1104            &advised.name,
1105            profile,
1106            context,
1107            budget,
1108            slots,
1109            step,
1110            held,
1111        )
1112    };
1113    let bound = jobs
1114        .iter()
1115        .filter(|(_, read)| read.averages.len() as u64 >= RAISE_RUNS)
1116        .map(|(job, read)| (*job, read.averages.len(), spread(read.averages.clone()).p50))
1117        .filter(|(_, _, median)| median.saturating_mul(100) >= cap.saturating_mul(BOUND))
1118        .max_by_key(|(_, _, median)| *median);
1119    if let Some((job, runs, median)) = bound {
1120        let held = format!(
1121            "{} runs of {} averaged {} of its {current} CPUs (median): the cap holds them back",
1122            runs,
1123            job_named(job),
1124            cores(median)
1125        );
1126        return raise(held);
1127    }
1128    // Under measured admission `cpus` bound no slot: a cap that holds runs back only slows them, and frees nothing.
1129    if config.host.admission == Admission::Measured {
1130        match held_raise(history, &advised.name, &jobs, cap, current) {
1131            // A burst the slice's CPUs hold back is the slice's to give, not the profile's.
1132            Some(Ok(held)) => {
1133                return match raise(held) {
1134                    CpuStep::Refused(_) => CpuStep::Keep,
1135                    step => step,
1136                };
1137            }
1138            Some(Err(why)) => return CpuStep::Refused(why),
1139            None => {}
1140        }
1141    }
1142    let runs: usize = jobs.values().map(|read| read.averages.len()).sum();
1143    let peak = jobs.values().map(|read| read.peak).max().unwrap_or(0);
1144    // Under measured admission `cpus` bound no slot, so a lowering frees nothing and only slows the bursts. A job
1145    // whose runs at the cap have no measured average may be the one that needs it, and one the cap held back ran as
1146    // fast as the cap let it: its average says what the cap allowed, not what it needs.
1147    if lowering == Lowering::Held
1148        || config.host.admission == Admission::Measured
1149        || (runs as u64) < u64::from(config.sizing.min_jobs)
1150        || jobs
1151            .values()
1152            .any(|read| read.averages.is_empty() || read.held() > 0)
1153    {
1154        return CpuStep::Keep;
1155    }
1156    let Some((job, heaviest)) = jobs
1157        .iter()
1158        .map(|(job, read)| (*job, spread(read.averages.clone()).p95))
1159        .max_by_key(|(_, p95)| *p95)
1160    else {
1161        return CpuStep::Keep;
1162    };
1163    let need = heaviest.saturating_mul(HEADROOM).max(peak);
1164    let target = u32::try_from(need.div_ceil(1000))
1165        .unwrap_or(u32::MAX)
1166        .max(1);
1167    if target >= current {
1168        return CpuStep::Keep;
1169    }
1170    let to = target.max(current.saturating_sub(step)).max(1);
1171    let mut reason = format!(
1172        "{runs} runs at its {current} CPUs peaked at {} CPUs at most, none held back by the cap, and the heaviest job, {}, \
1173         averaged {} CPUs (p95); the larger of that peak and twice that average is {target}",
1174        cores(peak),
1175        job_named(job),
1176        cores(heaviest)
1177    );
1178    if to != target {
1179        let _ = write!(
1180            reason,
1181            "; a step toward {target}, at most {}% a change",
1182            config.sizing.max_step
1183        );
1184    }
1185    CpuStep::To(Cpus { to, reason })
1186}