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