pub mod host;
pub mod pooled;
pub mod recent;
pub mod trace;
use std::cell::RefCell;
use std::collections::{BTreeMap, BTreeSet};
use std::time::{Duration, SystemTime};
use crate::api::Spread;
use crate::api::{Basis, HostMemory, JobPeak};
use crate::config::{self, Config};
use crate::scheduler::priority::{Around, Backfill, Candidate, Caps, Held, Older, Runner, Short};
use crate::scheduler::{Barrier, Drained, Left, Pool, Scarce, Waits};
use crate::sizing::{GRANULE, History, Measure, Ran, spread};
use crate::time;
use recent::{Ending, RECENT_RUNS, Recent};
use trace::{Hazard, OOMD_UNDER, Reading, RunId, RunTrace, STEP, THROTTLES_UNDER, Trace};
pub const UNPREDICTABLE_FOR: u64 = 7 * 24 * 3600 * 1000;
pub const OWN_RUNS: u64 = 2;
pub const HIGH_WATER: u64 = 90;
pub const CPU_GRANULE: u64 = 100;
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct Key {
pub repository: String,
pub workflow: Option<String>,
pub name: String,
}
impl Key {
pub fn of(run: &Ran) -> Key {
Key {
repository: run.repository.clone(),
workflow: run.workflow.clone(),
name: run.name.clone(),
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Copies {
Alone,
Several,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Prediction {
pub memory: u64,
pub basis: Basis,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct CpuPrediction {
pub cpu: u64,
pub basis: Basis,
}
#[derive(Debug, Clone, Default)]
struct Averages {
sorted: Vec<u64>,
succeeded: u64,
}
impl Averages {
fn add(&mut self, average: u64, succeeded: bool) {
let at = self.sorted.partition_point(|known| *known <= average);
self.sorted.insert(at, average);
self.succeeded += u64::from(succeeded);
}
fn runs(&self) -> u64 {
self.sorted.len() as u64
}
fn p95(&self) -> u64 {
spread(self.sorted.clone()).p95
}
fn max(&self) -> u64 {
self.sorted.last().copied().unwrap_or(0)
}
}
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct InProfile {
key: Key,
profile: String,
}
impl InProfile {
fn new(key: &Key, profile: &str) -> InProfile {
InProfile {
key: key.clone(),
profile: profile.to_owned(),
}
}
}
#[derive(Debug, Clone)]
pub struct Predictor {
margin: u32,
min_jobs: u32,
recent: Recent,
cpu_jobs: BTreeMap<InProfile, Averages>,
cpu_profiles: BTreeMap<String, Averages>,
}
impl Predictor {
pub fn new(rules: &config::Sizing) -> Predictor {
Predictor {
margin: rules.margin,
min_jobs: rules.min_jobs,
recent: Recent::new(RECENT_RUNS.max(u64::from(rules.min_jobs))),
cpu_jobs: BTreeMap::new(),
cpu_profiles: BTreeMap::new(),
}
}
pub fn read(
rules: &config::Sizing,
history: &History,
cap_of: impl Fn(&str) -> Option<u64>,
) -> Predictor {
let mut predictor = Predictor::new(rules);
predictor.read_until(history, u64::MAX, cap_of);
predictor
}
fn read_until(&mut self, history: &History, until: u64, cap_of: impl Fn(&str) -> Option<u64>) {
for (run, ending) in recent::rows(history) {
let cap = run
.memory_cap
.or_else(|| cap_of(&run.profile))
.unwrap_or(u64::MAX);
let at = recent::finished(run);
if at >= until {
break;
}
match ending {
Ending::Finished => self.learn(run, &run.profile, cap, at),
Ending::Cancelled => self.mark(run, &run.profile, cap, at),
}
}
}
pub fn learn(&mut self, run: &Ran, profile: &str, cap: u64, at: u64) {
self.recent.read(run, profile, Ending::Finished, cap, at);
self.learn_cpu(run, profile);
}
pub fn learn_cpu(&mut self, run: &Ran, profile: &str) {
let Some(average) = run.cpu_average else {
return;
};
self.cpu_profiles
.entry(profile.to_owned())
.or_default()
.add(average, run.succeeded);
self.cpu_jobs
.entry(InProfile::new(&Key::of(run), profile))
.or_default()
.add(average, run.succeeded);
}
pub fn predict_cpu(&self, key: &Key, profile: &str, cap: u64) -> CpuPrediction {
let job = self.cpu_jobs.get(&InProfile::new(key, profile));
let min_jobs = u64::from(self.min_jobs);
let peers = self
.cpu_profiles
.get(profile)
.filter(|peers| peers.runs() >= min_jobs);
let (cpu, basis) = match (job.filter(|job| job.runs() > 0), peers) {
(Some(job), _) if job.runs() >= min_jobs => (
job.p95(),
Basis::Job {
runs: job.runs(),
peak: JobPeak::P95,
},
),
(Some(job), Some(_)) if job.succeeded >= OWN_RUNS => (
job.max(),
Basis::Job {
runs: job.runs(),
peak: JobPeak::Largest,
},
),
(Some(job), Some(peers)) => (
job.max().max(peers.p95()),
Basis::Profile { runs: peers.runs() },
),
(None, Some(peers)) => (peers.max(), Basis::ProfileMax { runs: peers.runs() }),
_ => (cap, Basis::Cap),
};
CpuPrediction {
cpu: cpu
.div_ceil(CPU_GRANULE)
.saturating_mul(CPU_GRANULE)
.clamp(CPU_GRANULE, cap.max(CPU_GRANULE)),
basis,
}
}
pub fn usual(&self, key: &Key, profile: &str) -> Option<Duration> {
self.recent.job(key, profile)?.usual()
}
pub fn longest_usual(
&self,
keys: impl IntoIterator<Item = Key>,
profile: &str,
) -> Option<Duration> {
let usual: Option<Vec<Duration>> = keys
.into_iter()
.map(|key| self.usual(&key, profile))
.collect();
usual?.into_iter().max()
}
pub fn mark(&mut self, run: &Ran, profile: &str, cap: u64, at: u64) {
self.recent.read(run, profile, Ending::Cancelled, cap, at);
}
pub fn predict(
&self,
key: &Key,
profile: &str,
cap: u64,
now: u64,
copies: Copies,
) -> Prediction {
let job = self.recent.job(key, profile);
if let Some(hold) = job.and_then(|job| job.held(now, Some(UNPREDICTABLE_FOR))) {
return Prediction {
memory: cap,
basis: Basis::Unpredictable {
until: hold.at.saturating_add(UNPREDICTABLE_FOR) / 1000,
},
};
}
let min_jobs = u64::from(self.min_jobs);
let peers = self.recent.profile(profile);
let peers_runs = peers.len() as u64;
let overran = job.and_then(|job| {
job.overruns(now, UNPREDICTABLE_FOR)
.fold(None, |most: Option<(u64, u64)>, overrun| {
let until = overrun.at.saturating_add(UNPREDICTABLE_FOR);
Some(most.map_or((overrun.peak, until), |(peak, last)| {
(peak.max(overrun.peak), last.max(until))
}))
})
});
let (memory, basis) = match (job, peers_runs >= min_jobs) {
(Some(job), _) if job.runs() == 0 => (cap, Basis::Cap),
(Some(job), _) if let Some((peak, until)) = overran => (
self.with_margin(job.max().max(peak)),
Basis::Overran {
until: until / 1000,
},
),
(Some(job), _) if job.runs() >= min_jobs => (
self.with_margin(spread(job.peaks().to_vec()).p95),
Basis::Job {
runs: job.runs(),
peak: JobPeak::P95,
},
),
(Some(job), true) if job.succeeded() >= OWN_RUNS && copies == Copies::Alone => (
self.with_margin(job.max()),
Basis::Job {
runs: job.runs(),
peak: JobPeak::Largest,
},
),
(Some(job), true) => (
self.with_margin(job.max().max(spread(peers.to_vec()).p95)),
Basis::Profile { runs: peers_runs },
),
(None, true) => (
self.with_margin(peers.last().copied().unwrap_or(0)),
Basis::ProfileMax { runs: peers_runs },
),
_ => (cap, Basis::Cap),
};
Prediction {
memory: memory.min(cap),
basis,
}
}
fn with_margin(&self, peak: u64) -> u64 {
let memory = peak.saturating_add(peak.saturating_mul(u64::from(self.margin)) / 100);
memory
.div_ceil(GRANULE)
.saturating_mul(GRANULE)
.max(GRANULE)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Policy {
Caps,
Measured,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Barriers {
On,
Strict,
Off,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Arrivals {
AsQueued,
AfterNeeds,
}
#[derive(Debug, Clone, Copy)]
pub struct Replaying<'known> {
pub barriers: Barriers,
pub arrivals: Arrivals,
pub known: Option<&'known History>,
pub trace: Option<&'known Trace>,
pub most_credit: u64,
pub host_hold: u64,
pub credit_room: CreditRoom,
pub band: Band,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Band {
NoWaiterFits,
AnyWaiter,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum CreditRoom {
Counted,
LeftOut,
}
impl From<Barriers> for Replaying<'_> {
fn from(barriers: Barriers) -> Self {
Replaying {
barriers,
arrivals: Arrivals::AsQueued,
known: None,
trace: None,
most_credit: 0,
host_hold: u64::MAX,
credit_room: CreditRoom::Counted,
band: Band::NoWaiterFits,
}
}
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct PoolReplay {
pub waits: Vec<u64>,
pub never_started: u64,
}
impl PoolReplay {
pub fn wait(&self) -> Spread {
spread(self.waits.clone())
}
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct RunReplay {
pub took: u64,
pub profiles: BTreeSet<String>,
}
type RunKey = (String, u64, u32);
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct Backfilled {
pub jobs: u64,
pub overran: u64,
pub most_overrun: u64,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Replay {
pub jobs: u64,
pub never_started: u64,
pub wait: Spread,
pub mean_wait: u64,
pub most_running: u64,
pub worst_overlap: u64,
pub makespan: u64,
pub under_predicted: u64,
pub held_back: u64,
pub cpu_held: u64,
pub worst_cpu: u64,
pub pools: BTreeMap<Pool, PoolReplay>,
pub charged: u128,
pub capacity: u128,
pub barrier_for: u64,
pub withheld: u128,
pub runs: Vec<RunReplay>,
pub backfilled: Backfilled,
pub slice_waited: u64,
pub host_waited: u64,
pub hazard: Hazard,
}
struct Running<'run> {
run: &'run Ran,
job: u64,
profile: &'run str,
started: u64,
ends: u64,
backfilled: Option<u64>,
reserved: u64,
peak: u64,
cpu: u64,
key: Key,
basis: Basis,
starting: u64,
trace: Option<&'run RunTrace>,
}
pub fn simulate<'known>(
config: &Config,
memory_max: Option<u64>,
cpu_budget: Option<u64>,
jobs: &[Ran],
policy: Policy,
slots: &BTreeMap<String, u32>,
how: impl Into<Replaying<'known>>,
) -> Replay {
let Replaying {
barriers,
arrivals,
known,
trace,
most_credit,
host_hold,
credit_room,
band,
} = how.into();
let mirror = config.mirror_memory();
let budget = memory_max.map(|max| max.saturating_sub(mirror));
let queue = replayable(config, jobs);
let followers = match arrivals {
Arrivals::AsQueued => BTreeMap::new(),
Arrivals::AfterNeeds => followers(&queue),
};
let following: BTreeSet<u64> = followers
.values()
.flatten()
.map(|follower| queue[follower.at].job)
.collect();
let arriving = (0_usize..)
.zip(&queue)
.filter(|(_, queued)| !following.contains(&queued.job))
.map(|(at, queued)| (queued.run.queued_at, at))
.collect();
let mut predictor = Predictor::new(&config.sizing);
if let (Some(known), Some(first)) = (known, queue.first()) {
predictor.read_until(known, first.run.queued_at, |profile| {
config.profiles.get(profile).map(|limits| limits.memory.0)
});
}
let replayer = Replayer {
config,
budget,
cpu_budget,
policy,
slots,
predictor,
running: Vec::new(),
waits: Vec::new(),
most_running: 0,
worst_overlap: 0,
last_end: 0,
under_predicted: 0,
held_back: 0,
cpu_held: 0,
worst_cpu: 0,
barriers,
pool_waits: BTreeMap::new(),
pools: BTreeMap::new(),
barrier: None,
backfill: None,
usual: BTreeMap::new(),
arriving,
followers,
started: Vec::new(),
runs: BTreeMap::new(),
backfilled: Backfilled::default(),
moment: queue.first().map_or(0, |queued| queued.run.queued_at),
charged: 0,
capacity: 0,
barrier_for: 0,
withheld: 0,
memory_max,
mirror,
trace,
most_credit,
host_hold,
expects_credit: credit_room,
short: false,
next_plan: 0,
needs: RefCell::new(BTreeMap::new()),
held_for_slice: 0,
held_for_host: 0,
host_needs: Vec::new(),
band,
slice_waited: 0,
host_waited: 0,
hazard: Hazard::default(),
last_credit: 0,
cohorts: Vec::new(),
};
replayer.play(&queue)
}
fn replayable<'run>(config: &Config, jobs: &'run [Ran]) -> Vec<Queued<'run>> {
let mut queue: Vec<Queued<'_>> = (0_u64..)
.zip(jobs)
.filter(|(_, run)| config.profiles.contains_key(&run.profile))
.filter(|(_, run)| matches!((run.started_at, run.finished_at), (Some(start), Some(end)) if end >= start))
.map(|(job, run)| Queued {
job,
run,
arrived: run.queued_at,
})
.collect();
queue.sort_by_key(|queued| queued.run.queued_at);
queue
}
#[derive(Clone, Copy)]
struct Queued<'run> {
job: u64,
run: &'run Ran,
arrived: u64,
}
#[derive(Clone, Copy)]
struct Follower {
at: usize,
gap: u64,
}
fn followers(queue: &[Queued<'_>]) -> BTreeMap<u64, Vec<Follower>> {
let mut attempts: BTreeMap<RunKey, Vec<usize>> = BTreeMap::new();
for (at, queued) in queue.iter().enumerate() {
attempts.entry(run_key(queued.run)).or_default().push(at);
}
let mut followers: BTreeMap<u64, Vec<Follower>> = BTreeMap::new();
for attempt in attempts.values() {
for &at in attempt {
let queued_at = queue[at].run.queued_at;
let followed = attempt
.iter()
.map(|other| &queue[*other])
.filter(|other| other.run.queued_at < queued_at)
.filter_map(|other| Some((other.run.finished_at?, other.job)))
.filter(|(ended, _)| *ended <= queued_at)
.max();
if let Some((ended, job)) = followed {
let gap = queued_at - ended;
followers.entry(job).or_default().push(Follower { at, gap });
}
}
}
followers
}
fn run_key(run: &Ran) -> RunKey {
(run.repository.clone(), run.run_id, run.run_attempt)
}
struct RunSpan {
first_arrival: u64,
last_end: u64,
profiles: BTreeSet<String>,
}
impl RunSpan {
fn replay(self) -> RunReplay {
RunReplay {
took: self.last_end.saturating_sub(self.first_arrival) / 1000,
profiles: self.profiles,
}
}
}
fn pool_of(run: &Ran) -> Pool {
Pool {
repository: run.repository.clone(),
profile: run.profile.clone(),
}
}
struct Admitted {
reserved: u64,
starting: u64,
basis: Basis,
peak: u64,
cpu: u64,
}
fn same_job(one: &Ran, other: &Ran) -> bool {
one.name == other.name && one.repository == other.repository && one.workflow == other.workflow
}
struct Starting {
memory: u64,
reserved: u64,
basis: Basis,
cpu: u64,
}
enum Refused {
Slot,
Budget(Short),
Host(Short),
HighWater(Short),
}
struct Replayer<'run> {
config: &'run Config,
budget: Option<u64>,
cpu_budget: Option<u64>,
policy: Policy,
slots: &'run BTreeMap<String, u32>,
predictor: Predictor,
running: Vec<Running<'run>>,
waits: Vec<u64>,
most_running: u64,
worst_overlap: u64,
last_end: u64,
under_predicted: u64,
held_back: u64,
cpu_held: u64,
worst_cpu: u64,
barriers: Barriers,
pool_waits: BTreeMap<Pool, Waits>,
pools: BTreeMap<Pool, PoolReplay>,
barrier: Option<Barrier>,
backfill: Option<Backfill<'run>>,
usual: BTreeMap<Pool, Option<Duration>>,
arriving: BTreeSet<(u64, usize)>,
followers: BTreeMap<u64, Vec<Follower>>,
started: Vec<u64>,
runs: BTreeMap<RunKey, RunSpan>,
backfilled: Backfilled,
moment: u64,
charged: u128,
capacity: u128,
barrier_for: u64,
withheld: u128,
memory_max: Option<u64>,
mirror: u64,
trace: Option<&'run Trace>,
most_credit: u64,
host_hold: u64,
expects_credit: CreditRoom,
short: bool,
next_plan: u64,
needs: RefCell<BTreeMap<Pool, Need>>,
held_for_slice: u64,
held_for_host: u64,
host_needs: Vec<u64>,
band: Band,
slice_waited: u64,
host_waited: u64,
hazard: Hazard,
last_credit: u64,
cohorts: Vec<Cohort>,
}
#[derive(Clone, Copy)]
struct Need {
memory: u64,
cpu: u64,
}
struct Cohort {
jobs: Vec<u64>,
count: u64,
}
impl<'run> Replayer<'run> {
fn play(mut self, queue: &[Queued<'run>]) -> Replay {
let mut waiting: Vec<Queued<'_>> = Vec::new();
loop {
let arrival = self.arriving.first().map(|(arrives, _)| *arrives);
let end = self.running.iter().map(|running| running.ends).min();
let event = [arrival, end, self.next_limit()]
.into_iter()
.flatten()
.min();
let Some(now) = [event, self.next_look(&waiting)]
.into_iter()
.flatten()
.min()
else {
break;
};
self.account(now);
self.finish(now);
if event != Some(now) && !self.plans_at(now) {
continue;
}
self.rereserve(now);
while let Some(&(arrived, at)) =
self.arriving.first().filter(|(arrives, _)| *arrives <= now)
{
self.arriving.remove(&(arrived, at));
waiting.push(Queued {
arrived,
..queue[at]
});
}
waiting.sort_by_key(|queued| (queued.arrived, queued.job));
self.pass(&mut waiting, now);
self.note_worst(self.mirror);
}
self.replay(queue)
}
fn next_look(&self, waiting: &[Queued<'run>]) -> Option<u64> {
let trace = self.trace?;
let waits = !waiting.is_empty() && self.moment < trace.ends();
(!self.running.is_empty() || waits).then_some(self.moment + STEP)
}
fn plans_at(&mut self, now: u64) -> bool {
if now < self.next_plan {
return false;
}
let poll = u64::try_from(self.config.host.poll_interval.as_millis()).unwrap_or(u64::MAX);
self.next_plan = now.saturating_add(poll);
true
}
fn next_limit(&self) -> Option<u64> {
self.pool_waits
.values()
.flat_map(Waits::deadlines)
.map(time::ms)
.filter(|limit| *limit > self.moment)
.min()
}
fn account(&mut self, now: u64) {
let span = now.saturating_sub(self.moment);
self.look(span);
let taken = self.taken();
self.charged += u128::from(taken) * u128::from(span);
if let Some(budget) = self.budget {
self.capacity += u128::from(budget) * u128::from(span);
if self.barrier.is_some() {
self.withheld += u128::from(budget.saturating_sub(taken)) * u128::from(span);
}
}
if self.barrier.is_some() {
self.barrier_for += span;
}
self.moment = now;
}
fn look(&mut self, span: u64) {
let Some(trace) = self.trace else {
return;
};
self.slice_waited += self.held_for_slice * span;
self.host_waited += self.held_for_host * span;
if self.running.is_empty() {
self.last_credit = 0;
return;
}
let slice = self.slice();
let host_slice = self.used_now() + trace.host_overhead;
let hazard = &mut self.hazard;
hazard.slice_peak = hazard.slice_peak.max(slice);
hazard.active += span;
if let Some(max) = self.memory_max {
let mark = max / 100 * HIGH_WATER;
hazard.over_mark.note(slice.checked_sub(mark), span);
hazard.over_max.note(slice.checked_sub(max), span);
}
if let Some(outside) = trace.outside_at(self.moment) {
let available = trace
.total
.saturating_sub(outside)
.saturating_sub(host_slice);
hazard.under_throttling += span * u64::from(available < THROTTLES_UNDER);
hazard.under_oomd += span * u64::from(available < OOMD_UNDER);
hazard.in_band += span * u64::from(self.short);
hazard.lowest_available = Some(
hazard
.lowest_available
.map_or(available, |lowest| lowest.min(available)),
);
}
let count = self.count();
let hazard = &mut self.hazard;
hazard.credit += u128::from(count.credit) * u128::from(span);
hazard.most_credit = hazard.most_credit.max(count.credit);
if count.credit < self.last_credit {
hazard.credit_falls += 1;
let before = pooled::Count {
credit: self.last_credit,
..count
};
self.hazard.overdrawn += u64::from(self.overdrawn(before, count));
}
self.last_credit = count.credit;
self.note_unfunded(span);
}
fn overdrawn(&self, before: pooled::Count, now: pooled::Count) -> bool {
let max = self.memory_max.unwrap_or(u64::MAX);
let host = self
.host_memory()
.map_or(u64::MAX, |memory| host::limit(&memory, self.short));
(now.pooled() > max && before.pooled() <= max)
|| (self.hosted(now) > host && self.hosted(before) <= host)
}
fn hosted(&self, count: pooled::Count) -> u64 {
count.plain - count.credit.saturating_sub(self.host_hold)
}
fn note_unfunded(&mut self, span: u64) {
let used: BTreeMap<u64, u64> = self
.running
.iter()
.map(|running| (running.job, self.used(running).unwrap_or(0)))
.collect();
self.cohorts
.retain(|cohort| cohort.jobs.iter().any(|job| used.contains_key(job)));
let all: u64 = used.values().sum();
let lowest = self.cohorts.iter().map(|cohort| cohort.count).min();
let mut worst = None;
if lowest.is_some_and(|lowest| all > lowest) {
for cohort in &self.cohorts {
let of_cohort: u64 = cohort.jobs.iter().filter_map(|job| used.get(job)).sum();
worst = worst.max(of_cohort.checked_sub(cohort.count).filter(|past| *past > 0));
}
}
self.hazard.unfunded.note(worst, span);
}
fn used(&self, running: &Running<'_>) -> Option<u64> {
match running
.trace?
.at(self.moment.saturating_sub(running.started))
{
Reading::Used(memory) => Some(memory),
Reading::NotYet | Reading::Stale => None,
}
}
fn slice(&self) -> u64 {
self.used_now() + self.trace.map_or(0, |trace| trace.overhead)
}
fn slice_read(&self) -> u64 {
self.used_now() + self.trace.map_or(0, |trace| trace.guard_overhead)
}
fn used_now(&self) -> u64 {
self.running
.iter()
.map(|running| self.used(running).unwrap_or(0))
.sum()
}
fn host_memory(&self) -> Option<HostMemory> {
let trace = self.trace.filter(|trace| trace.total > 0)?;
let outside = trace.outside_at(self.moment)?;
let slice = self.used_now() + trace.host_overhead;
Some(HostMemory {
at: self.moment / 1000,
total: trace.total,
available: trace.total.saturating_sub(outside).saturating_sub(slice),
slice,
some: None,
full: None,
holders: Vec::new(),
ceiling: None,
swap: None,
})
}
fn count(&self) -> pooled::Count {
let held: Vec<pooled::Runner<'_>> = self
.running
.iter()
.map(|running| {
let ran = self.moment.saturating_sub(running.started);
let named = running.trace.is_none_or(|trace| ran >= trace.named_after);
pooled::Runner {
key: named.then_some(&running.key),
takes: self.charge(running),
used: self
.used(running)
.filter(|_| running.run.measure == Measure::WithoutPageCache),
ran: Some(Duration::from_millis(ran)),
basis: Some(running.basis),
}
})
.collect();
let host = self.host_memory();
pooled::count(&pooled::Snapshot {
runners: &held,
committed: self.mirror,
slice: self.memory_max.map(|memory_max| pooled::Slice {
memory: self.slice_read(),
memory_max,
}),
host: host.map(|memory| {
host::pooling(
&memory,
host::Remembered {
short: self.short,
stalled: false,
},
)
}),
most: if self.trace.is_some() && self.policy == Policy::Measured {
self.most_credit
} else {
0
},
})
}
fn host_left(&self) -> Option<i64> {
let memory = self.host_memory()?;
let limit = host::limit(&memory, self.short && !self.running.is_empty());
Some(host::left(limit, self.hosted(self.count()), false))
}
fn pass(&mut self, waiting: &mut Vec<Queued<'run>>, now: u64) {
let at = instant(now);
self.barrier = None;
self.backfill = None;
self.usual.clear();
self.needs.borrow_mut().clear();
self.held_for_slice = 0;
self.held_for_host = 0;
self.host_needs.clear();
let listed = waiting.clone();
let mut index = 0;
while let Some(queued) = waiting.get(index).copied() {
match self.admits(queued, waiting, now) {
Ok(admitted) if self.barrier.is_none() => {
waiting.remove(index);
self.start(queued, &admitted, None, now);
}
Ok(admitted) => match self.passes(queued, &listed) {
Some(usual) => {
waiting.remove(index);
self.start(queued, &admitted, Some(usual), now);
}
None => index += 1,
},
Err(Refused::Slot) => index += 1,
Err(Refused::Budget(short)) => {
if self.barrier.is_none() && short.scarce == Scarce::Cpu {
self.cpu_held += 1;
}
self.held_for_slice += u64::from(short.scarce == Scarce::Memory);
let first = self.barrier.is_none();
self.hold(queued.run, short, at);
if first && self.barrier.is_some() {
self.backfill_behind(queued.run, &waiting[..index], &listed, now);
}
index += 1;
}
Err(Refused::Host(short)) => {
self.held_for_host += 1;
if self.barrier.is_none() {
self.host_needs.push(short.memory);
}
let first = self.barrier.is_none();
self.hold(queued.run, short, at);
if first && self.barrier.is_some() {
self.backfill_behind(queued.run, &waiting[..index], &listed, now);
}
index += 1;
}
Err(Refused::HighWater(short)) => {
if self.barrier.is_none() {
self.held_back += 1;
}
self.hold(queued.run, short, at);
index += 1;
}
}
}
self.short = self.band_stands();
self.settle_waits(waiting);
}
fn band_stands(&self) -> bool {
match self.band {
Band::AnyWaiter => self.held_for_host > 0,
Band::NoWaiterFits => self.host_memory().is_some_and(|memory| {
let reserved = self.hosted(self.count());
host::short(&memory, reserved, false, self.host_needs.iter().copied())
}),
}
}
fn settle_waits(&mut self, waiting: &[Queued<'run>]) {
let queued: BTreeSet<Pool> = waiting.iter().map(|queued| pool_of(queued.run)).collect();
self.pool_waits.retain(|pool, waits| {
if !queued.contains(pool) {
waits.emptied();
}
!waits.is_empty()
});
}
fn hold(&mut self, run: &'run Ran, short: Short, at: SystemTime) {
if self.barriers == Barriers::Off {
return;
}
let drained = (!self.at_high_water()).then_some(self.drained());
let waits = self.pool_waits.entry(pool_of(run)).or_default();
if drained.is_some() {
waits.note(short.scarce, short.job, at);
}
if self.barrier.is_none() {
self.barrier = Barrier::of(short, waits, drained, at);
if self.barrier.is_some() {
waits.own(short.job);
}
}
}
fn backfill_behind(
&mut self,
run: &'run Ran,
older: &[Queued<'run>],
listed: &[Queued<'run>],
now: u64,
) {
let Some(barrier) = self.barrier.filter(|_| self.barriers == Barriers::On) else {
return;
};
let mut pools = BTreeSet::new();
let older: Vec<Older<'_>> = older
.iter()
.filter(|queued| self.config.profiles.contains_key(&queued.run.profile))
.filter(|queued| pools.insert(pool_of(queued.run)))
.map(|queued| {
let starting = self.starting(*queued, listed, now);
Older {
profile: &queued.run.profile,
free_slot: self.free_slots(&queued.run.profile) > 0,
memory: starting.memory,
cpu: starting.cpu,
}
})
.collect();
let runners = self.runners();
let around = Around {
left: self.left(),
credit_room: self.credit_room(),
drained: self.drained(),
runners: &runners,
older: &older,
};
self.backfill = Backfill::behind(barrier, &run.profile, around, instant(now));
}
fn credit_room(&self) -> u64 {
if self.trace.is_none()
|| self.policy != Policy::Measured
|| self.expects_credit == CreditRoom::LeftOut
{
return 0;
}
self.most_credit.saturating_sub(self.count().credit)
}
fn drained(&self) -> Drained {
Drained {
memory: self.budget.map(signed),
cpu: self.cpu_budget.map(signed),
host: self.host_memory().map(|memory| {
let limit = host::limit(&memory, !self.running.is_empty());
signed(limit).saturating_sub(signed(self.mirror))
}),
host_plain: self.host_memory().map(|memory| {
signed(host::limit(&memory, false)).saturating_sub(signed(self.mirror))
}),
}
}
fn free_slots(&self, profile: &str) -> usize {
let limits = &self.config.profiles[profile];
let slots = self.slots.get(profile).copied().unwrap_or(limits.slots);
let in_profile = self
.running
.iter()
.filter(|running| running.profile == profile)
.count();
(slots as usize).saturating_sub(in_profile)
}
fn passes(&mut self, queued: Queued<'run>, listed: &[Queued<'run>]) -> Option<Duration> {
let run = queued.run;
self.backfill.as_ref()?;
let predictor = &self.predictor;
let usual = *self.usual.entry(pool_of(run)).or_insert_with(|| {
let keys = listed
.iter()
.filter(|other| other.run.repository == run.repository)
.filter(|other| other.run.profile == run.profile)
.map(|other| Key::of(other.run));
predictor.longest_usual(keys, &run.profile)
});
let candidate = Candidate {
profile: &run.profile,
free_slots: self.free_slots(&run.profile),
usual,
caps: self.caps(&run.profile),
};
let backfill = self.backfill.as_mut()?;
backfill.admits(candidate).then_some(usual).flatten()
}
fn left(&self) -> Left {
let cpu: u64 = self.running.iter().map(|running| running.cpu).sum();
let left = |budget: u64, taken: u64| signed(budget).saturating_sub(signed(taken));
Left {
memory: self.budget.map(|budget| left(budget, self.taken())),
cpu: self.cpu_budget.map(|budget| left(budget, cpu)),
host: self.host_left(),
}
}
fn caps(&self, profile: &str) -> Caps {
let limits = &self.config.profiles[profile];
let cpu = u64::from(limits.cpus).saturating_mul(1000);
Caps {
memory: limits.memory.0,
cpu: self.cpu_budget.map_or(cpu, |budget| cpu.min(budget)),
}
}
fn note_worst(&mut self, mirror: u64) {
self.most_running = self.most_running.max(self.running.len() as u64);
let peaks: u64 = self.running.iter().map(|running| running.peak).sum();
self.worst_overlap = self.worst_overlap.max(peaks + mirror);
let cpu: u64 = self
.running
.iter()
.map(|running| running.run.cpu_average.unwrap_or(0))
.sum();
self.worst_cpu = self.worst_cpu.max(cpu);
}
fn replay(mut self, queue: &[Queued<'run>]) -> Replay {
let started: BTreeSet<u64> = self.started.iter().copied().collect();
let never_started: Vec<&Queued<'_>> = queue
.iter()
.filter(|queued| !started.contains(&queued.job))
.collect();
for queued in &never_started {
self.pools
.entry(pool_of(queued.run))
.or_default()
.never_started += 1;
}
let waits = self.waits;
let first = queue.first().map_or(0, |queued| queued.run.queued_at);
Replay {
jobs: queue.len() as u64,
never_started: never_started.len() as u64,
mean_wait: waits.iter().sum::<u64>() / (waits.len() as u64).max(1),
wait: spread(waits),
most_running: self.most_running,
worst_overlap: self.worst_overlap,
makespan: self.last_end.saturating_sub(first) / 1000,
under_predicted: self.under_predicted,
held_back: self.held_back,
cpu_held: self.cpu_held,
worst_cpu: self.worst_cpu,
pools: self.pools,
charged: self.charged,
capacity: self.capacity,
barrier_for: self.barrier_for,
withheld: self.withheld,
runs: self.runs.into_values().map(RunSpan::replay).collect(),
backfilled: self.backfilled,
slice_waited: self.slice_waited,
host_waited: self.host_waited,
hazard: self.hazard,
}
}
fn runners(&self) -> Vec<Runner<'_>> {
self.running
.iter()
.map(|running| Runner {
profile: running.profile,
started_at: instant(running.started),
usual: self.predictor.usual(&Key::of(running.run), running.profile),
memory: self.charge(running),
cpu: running.cpu,
caps: self.caps(running.profile),
})
.collect()
}
fn at_high_water(&self) -> bool {
if self.trace.is_some() {
return self.policy == Policy::Measured
&& self.memory_max.is_some_and(|max| {
self.slice_read().saturating_mul(100) >= max.saturating_mul(HIGH_WATER)
});
}
let peaks: u64 = self.running.iter().map(|running| running.peak).sum();
self.policy == Policy::Measured
&& self.budget.is_some_and(|budget| {
peaks.saturating_mul(100) >= budget.saturating_mul(HIGH_WATER)
})
}
fn finish(&mut self, now: u64) {
let (ended, running): (Vec<_>, Vec<_>) = std::mem::take(&mut self.running)
.into_iter()
.partition(|running| running.ends <= now);
self.running = running;
let mut ended = ended;
ended.sort_by_key(|ended| ended.ends);
for ended in ended {
let cap = ended
.run
.memory_cap
.unwrap_or(self.config.profiles[ended.profile].memory.0);
self.under_predicted += u64::from(ended.peak > ended.reserved);
let reserved = (self.policy == Policy::Measured).then_some(ended.reserved);
let run = Ran {
reserved,
..ended.run.clone()
};
self.predictor.learn(&run, ended.profile, cap, ended.ends);
self.last_end = self.last_end.max(ended.ends);
if let Some(by) = ended.backfilled {
let overrun = ended.ends.saturating_sub(by);
self.backfilled.overran += u64::from(overrun > 0);
self.backfilled.most_overrun = self.backfilled.most_overrun.max(overrun / 1000);
}
let span = self.runs.get_mut(&run_key(ended.run));
if let Some(span) = span {
span.last_end = span.last_end.max(ended.ends);
}
for follower in self.followers.remove(&ended.job).unwrap_or_default() {
self.arriving
.insert((ended.ends + follower.gap, follower.at));
}
}
}
fn rereserve(&mut self, now: u64) {
if self.policy != Policy::Measured {
return;
}
let cpus: Vec<u64> = self
.running
.iter()
.map(|running| self.cpu(&Key::of(running.run), running.profile))
.collect();
let mut seen = BTreeSet::new();
for (running, cpu) in self.running.iter_mut().zip(cpus) {
let key = Key::of(running.run);
let copies = if seen.insert(key.clone()) {
Copies::Alone
} else {
Copies::Several
};
let limits = &self.config.profiles[running.profile];
let prediction =
self.predictor
.predict(&key, running.profile, limits.memory.0, now, copies);
running.reserved = prediction.memory;
running.basis = prediction.basis;
running.cpu = cpu;
}
}
fn cpu(&self, key: &Key, profile: &str) -> u64 {
let cap = u64::from(self.config.profiles[profile].cpus).saturating_mul(1000);
let cpu = match self.policy {
Policy::Caps => cap,
Policy::Measured => self.predictor.predict_cpu(key, profile, cap).cpu,
};
self.cpu_budget.map_or(cpu, |budget| cpu.min(budget))
}
fn taken(&self) -> u64 {
self.count().pooled().saturating_sub(self.mirror)
}
fn charge(&self, running: &Running<'_>) -> u64 {
let Some(trace) = running.trace.filter(|_| self.policy == Policy::Measured) else {
return match self.policy {
Policy::Caps => running.reserved,
Policy::Measured => running.reserved.max(running.peak),
};
};
let ran = self.moment.saturating_sub(running.started);
let reserved = if ran < trace.named_after {
running.starting.max(running.reserved)
} else {
running.reserved
};
match trace.at(ran) {
Reading::NotYet => reserved,
Reading::Used(memory) => reserved.max(memory),
Reading::Stale => self.config.profiles[running.profile].memory.0,
}
}
fn admits(
&self,
queued: Queued<'run>,
waiting: &[Queued<'run>],
now: u64,
) -> Result<Admitted, Refused> {
let run = queued.run;
let Some(limits) = self.config.profiles.get(&run.profile) else {
return Err(Refused::Slot);
};
if self.free_slots(&run.profile) == 0 {
return Err(Refused::Slot);
}
let starting = self.starting(queued, waiting, now);
let short = |scarce, held| Short {
job: queued.job,
scarce,
held,
memory: starting.memory,
cpu: starting.cpu,
};
if let Some(budget) = self.budget {
if self.taken() + starting.memory > budget {
return Err(Refused::Budget(short(Scarce::Memory, Held::ByBudget)));
}
if self.at_high_water() {
return Err(Refused::HighWater(short(Scarce::Memory, Held::ByBudget)));
}
}
if self
.host_left()
.is_some_and(|left| left < signed(starting.memory))
{
return Err(Refused::Host(short(Scarce::Memory, Held::ByHost)));
}
if let Some(cpu_budget) = self.cpu_budget {
let taken: u64 = self.running.iter().map(|running| running.cpu).sum();
if taken + starting.cpu > cpu_budget {
return Err(Refused::Budget(short(Scarce::Cpu, Held::ByBudget)));
}
}
Ok(Admitted {
reserved: starting.reserved,
starting: starting.memory,
basis: starting.basis,
peak: run.memory_peak.min(limits.memory.0),
cpu: self.cpu(&Key::of(run), &run.profile),
})
}
fn starting(&self, queued: Queued<'run>, waiting: &[Queued<'run>], now: u64) -> Starting {
let run = queued.run;
let profile = run.profile.as_str();
let cap = self.config.profiles[profile].memory.0;
let running = |job: &Ran| {
self.running
.iter()
.any(|running| same_job(running.run, job))
};
let predicted = |job: &Ran| {
let key = Key::of(job);
let waiting = waiting
.iter()
.filter(|other| same_job(other.run, job))
.count();
let copies = if waiting > 1 || running(job) {
Copies::Several
} else {
Copies::Alone
};
self.predictor
.predict(&key, profile, cap, now, copies)
.memory
};
let started = || {
let key = Key::of(run);
let copies = if running(run) {
Copies::Several
} else {
Copies::Alone
};
self.predictor.predict(&key, profile, cap, now, copies)
};
let pool = || {
waiting
.iter()
.map(|other| other.run)
.filter(|job| job.repository == run.repository && job.profile == run.profile)
};
let own = started();
let need = || Need {
memory: pool().map(predicted).max().unwrap_or(0),
cpu: pool()
.map(|job| self.cpu(&Key::of(job), profile))
.max()
.unwrap_or(0),
};
let need = if self.trace.is_some() {
*self
.needs
.borrow_mut()
.entry(pool_of(run))
.or_insert_with(need)
} else {
need()
};
let (memory, reserved, basis) = match self.policy {
Policy::Caps => (cap, cap, Basis::Cap),
Policy::Measured => (need.memory.max(own.memory), own.memory, own.basis),
};
Starting {
memory,
reserved,
basis,
cpu: need.cpu.max(self.cpu(&Key::of(run), profile)),
}
}
fn start(
&mut self,
queued: Queued<'run>,
admitted: &Admitted,
usual: Option<Duration>,
now: u64,
) {
let run = queued.run;
let Some((profile, _)) = self.config.profiles.get_key_value(&run.profile) else {
return;
};
let ran_for = run
.finished_at
.unwrap_or_default()
.saturating_sub(run.started_at.unwrap_or_default());
let waited = now.saturating_sub(queued.arrived) / 1000;
let span = self.runs.entry(run_key(run)).or_insert(RunSpan {
first_arrival: queued.arrived,
last_end: now,
profiles: BTreeSet::new(),
});
span.first_arrival = span.first_arrival.min(queued.arrived);
span.profiles.insert(run.profile.clone());
self.started.push(queued.job);
self.backfilled.jobs += u64::from(usual.is_some());
let pool = pool_of(run);
if let Some(waits) = self.pool_waits.get_mut(&pool) {
waits.started();
}
self.pools.entry(pool).or_default().waits.push(waited);
self.waits.push(waited);
self.running.push(Running {
run,
job: queued.job,
profile,
started: now,
ends: now + ran_for,
backfilled: usual.map(|usual| {
now.saturating_add(u64::try_from(usual.as_millis()).unwrap_or(u64::MAX))
}),
reserved: admitted.reserved,
peak: admitted.peak,
cpu: admitted.cpu,
key: Key::of(run),
basis: admitted.basis,
starting: admitted.starting,
trace: self.trace.and_then(|trace| trace.runs.get(&RunId::of(run))),
});
self.needs.borrow_mut().clear();
if self.trace.is_some() {
self.cohorts.push(Cohort {
jobs: self.running.iter().map(|running| running.job).collect(),
count: self.taken(),
});
}
}
}
fn instant(ms: u64) -> SystemTime {
SystemTime::UNIX_EPOCH + Duration::from_millis(ms)
}
fn signed(amount: u64) -> i64 {
i64::try_from(amount).unwrap_or(i64::MAX)
}
#[cfg(test)]
mod tests;