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