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