use std::cell::RefCell;
use std::collections::{BTreeMap, BTreeSet};
use std::time::{Duration, SystemTime};
use crate::api::{Basis, HostMemory};
use crate::config::Config;
use crate::scheduler::priority::{
Around, Backfill, Candidate, Caps, Held, Older, RunTimes, Runner, Short,
};
use crate::scheduler::{Barrier, Drained, Left, Pool, Scarce, Waits};
use crate::sizing::{Measure, Ran};
use crate::time;
use super::{
Arrivals, Backfilled, Band, Barriers, Brake, Copies, CreditRoom, GrowthCount, GuardHold,
HIGH_WATER, Hazard, HostReserve, Key, OOMD_UNDER, Policy, PoolReplay, Predictor, Reading,
Recorded, Replay, Replaying, RunId, RunKey, RunReplay, RunTrace, STEP, THROTTLES_UNDER, Trace,
growth, host, pooled, spread,
};
struct Running<'run> {
run: &'run Ran,
job: u64,
profile: &'run str,
started: u64,
ends: u64,
backfilled: Option<u64>,
reserved: u64,
peak: u64,
cpu: u64,
starting_cpu: u64,
key: Key,
basis: Basis,
starting: u64,
trace: Option<&'run RunTrace>,
boot: u64,
}
impl Running<'_> {
fn job_ran(&self, moment: u64) -> Option<u64> {
moment.checked_sub(self.started + self.boot)
}
fn reading(&self, moment: u64) -> Option<Reading> {
let trace = self.trace?;
Some(
self.job_ran(moment)
.map_or(Reading::NotYet, |ran| trace.at(ran)),
)
}
fn cpu_at(&self, moment: u64) -> u64 {
if self.named(moment) {
self.cpu
} else {
self.starting_cpu.max(self.cpu)
}
}
fn named(&self, moment: u64) -> bool {
self.trace.is_none_or(|trace| {
self.job_ran(moment)
.is_some_and(|ran| ran >= trace.named_after)
})
}
}
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_reserve,
credit_room,
band,
growth,
} = 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_reserve,
expects_credit: credit_room,
host_band: host::HostBand::Plain,
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: pooled::Count::default(),
cohorts: Vec::new(),
growth: growth.filter(|_| trace.is_some() && policy == Policy::Measured),
brake: growth::Growth::default(),
};
replayer.play(&queue)
}
pub fn recorded(config: &Config, jobs: &[Ran]) -> Recorded {
let mut by_pool: BTreeMap<Pool, Vec<u64>> = BTreeMap::new();
let mut host_waited = 0;
let mut spans: BTreeMap<RunKey, RunSpan> = BTreeMap::new();
for Queued { run, .. } in replayable(config, jobs) {
let waited = run
.runner_started_at
.saturating_sub(run.queued_at)
.saturating_sub(run.unseen);
by_pool.entry(pool_of(run)).or_default().push(waited / 1000);
host_waited += run.host_waited;
let span = spans.entry(run_key(run)).or_insert(RunSpan {
first_arrival: run.queued_at,
last_end: 0,
profiles: BTreeSet::new(),
});
span.first_arrival = span.first_arrival.min(run.queued_at);
span.last_end = span.last_end.max(run.finished_at.unwrap_or(0));
span.profiles.insert(run.profile.clone());
}
Recorded {
pools: by_pool
.into_iter()
.map(|(pool, waits)| {
let replay = PoolReplay {
waits,
never_started: 0,
};
(pool, replay)
})
.collect(),
runs: spans.into_values().map(RunSpan::replay).collect(),
host_waited,
}
}
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,
starting_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_reserve: HostReserve,
expects_credit: CreditRoom,
host_band: host::HostBand,
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: pooled::Count,
cohorts: Vec<Cohort>,
growth: Option<GrowthCount>,
brake: growth::Growth<u64>,
}
#[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 = pooled::Count::default();
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 = signed(trace.total)
.saturating_sub(signed(outside))
.saturating_sub(signed(host_slice));
hazard.under_throttling += span * u64::from(available < signed(THROTTLES_UNDER));
hazard.under_oomd += span * u64::from(available < signed(OOMD_UNDER));
hazard.in_band += span * u64::from(self.host_band.is_short());
hazard.lowest_available = Some(
hazard
.lowest_available
.map_or(available, |lowest| lowest.min(available)),
);
}
let count = self.count();
let braked = self.braked();
let hazard = &mut self.hazard;
if self.growth.is_some() {
if braked {
hazard.braked += span;
} else if count.kept.is_none() {
hazard.guarded += span;
}
}
hazard.credit += u128::from(count.credit) * u128::from(span);
hazard.most_credit = hazard.most_credit.max(count.credit);
hazard.host_credit += u128::from(count.host_credit) * u128::from(span);
let fell = count.credit < self.last.credit;
hazard.credit_falls += u64::from(fell);
if fell || count.host_credit < self.last.host_credit {
self.hazard.overdrawn += u64::from(self.overdrawn(self.last, count));
}
self.last = count;
self.note_unfunded(span);
}
fn overdrawn(&self, last: 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.host_band.is_short())
});
let before = pooled::Count {
credit: last.credit,
host_credit: last.host_credit,
..now
};
let crossed = |read: fn(pooled::Count) -> u64, budget: u64| {
read(now) > budget && read(before) <= budget && read(last) <= budget
};
crossed(pooled::Count::pooled, max) || crossed(pooled::Count::hosted, host)
}
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.reading(self.moment)? {
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 {
self.count_with(None)
}
fn count_with(&self, starting: Option<u64>) -> pooled::Count {
self.count_by(starting, self.host_band)
}
fn count_by(&self, starting: Option<u64>, band: host::HostBand) -> pooled::Count {
let mut runners = self.held();
runners.extend(starting.map(|takes| pooled::Runner {
key: None,
takes,
used: Reading::NotYet,
ran: Some(Duration::ZERO),
basis: None,
}));
let hold = if self.braked() {
pooled::Hold::Held
} else {
pooled::Hold::Free
};
self.count_of(&runners, hold, band)
}
fn count_of(
&self,
runners: &[pooled::Runner<'_>],
hold: pooled::Hold,
band: host::HostBand,
) -> pooled::Count {
let host = self.host_memory();
let measured = self.trace.is_some() && self.policy == Policy::Measured;
pooled::count(&pooled::Snapshot {
runners,
committed: self.mirror,
slice: Some(pooled::Slice {
memory: self.slice_read(),
memory_max: self.memory_max,
}),
host: host.map(|memory| {
host::pooling(
&memory,
host::Remembered::new(band, host::Occupancy::Occupied),
)
}),
most: if measured { self.most_credit } else { 0 },
host_reserve: measured && self.host_reserve == HostReserve::Top2,
growth: self.growth.map(|growth| pooled::Growth {
hold,
..growth.growth
}),
})
}
fn held(&self) -> Vec<pooled::Runner<'_>> {
self.running
.iter()
.map(|running| {
if running.started == self.moment {
return pooled::Runner {
key: None,
takes: self.charge(running),
used: Reading::NotYet,
ran: Some(Duration::ZERO),
basis: None,
};
}
let used = running
.reading(self.moment)
.filter(|_| running.run.measure == Measure::WithoutPageCache)
.unwrap_or(Reading::Stale);
pooled::Runner {
key: running.named(self.moment).then_some(&running.key),
takes: self.charge(running),
used,
ran: Some(Duration::from_millis(
running.job_ran(self.moment).unwrap_or(0),
)),
basis: Some(running.basis),
}
})
.collect()
}
fn braked(&self) -> bool {
self.growth.is_some() && self.brake.braked(instant(self.moment)).is_some()
}
fn look_at_growth(&mut self) {
let Some(GrowthCount {
growth,
brake: Brake::On,
guard,
}) = self.growth
else {
return;
};
let held = self.held();
let room = pooled::growth_room(&held, growth);
let guard = match guard {
GuardHold::On
if self
.count_of(&held, pooled::Hold::Free, self.host_band)
.kept
.is_none() =>
{
growth::Guard::Crossed
}
GuardHold::On | GuardHold::Off => growth::Guard::Clear,
};
let used: Vec<growth::Use<u64>> = self
.running
.iter()
.zip(&held)
.filter_map(|(running, runner)| {
let memory = match runner.used {
Reading::Used(memory) => memory,
Reading::NotYet => 0,
Reading::Stale => return None,
};
Some(growth::Use {
runner: running.job,
memory,
})
})
.collect();
self.brake.look(instant(self.moment), used, room, guard);
}
fn host_left_with(&self, count: pooled::Count) -> Option<i64> {
self.host_left_by(count, self.host_band)
}
fn host_left_by(&self, count: pooled::Count, band: host::HostBand) -> Option<i64> {
let memory = self.host_memory()?;
let limit = host::limit(
&memory,
band.short(host::Occupancy::of(!self.running.is_empty())),
);
Some(host::left(limit, count.hosted(), false))
}
fn pass(&mut self, waiting: &mut Vec<Queued<'run>>, now: u64) {
let at = instant(now);
self.look_at_growth();
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.may_pass(queued, &listed).is_some() {
let cpu_short = self
.cpu_budget
.is_some_and(|budget| self.cpu_taken() + short.cpu > budget);
self.host_needs
.push(if cpu_short { u64::MAX } else { 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.host_band = self.next_band();
self.settle_waits(waiting);
}
fn next_band(&self) -> host::HostBand {
match self.band {
Band::AnyWaiter if self.held_for_host > 0 => host::HostBand::Larger,
Band::AnyWaiter => host::HostBand::Plain,
Band::NoWaiterFits => self.host_memory().map_or(host::HostBand::Plain, |memory| {
let reserved = self.count_by(None, host::HostBand::Plain).hosted();
let needs = self.host_needs.iter().copied();
host::HostBand::after_plan(&memory, reserved, false, needs)
}),
}
}
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 plain = self.count_by(None, host::HostBand::Plain);
let around = Around {
left: self.left_of(plain, host::HostBand::Plain),
run_times: RunTimes::Fresh,
credit_room: self.credit_room_of(plain),
host_credit_room: self.host_credit_room_of(plain),
drained: self.drained(),
runners: &runners,
older: &older,
};
self.backfill = Backfill::behind(barrier, &run.profile, around, instant(now));
}
fn credit_room_of(&self, count: pooled::Count) -> u64 {
if self.trace.is_none()
|| self.policy != Policy::Measured
|| self.expects_credit == CreditRoom::LeftOut
{
return 0;
}
count.credit_room
}
fn host_credit_room_of(&self, count: pooled::Count) -> u64 {
if self.expects_credit == CreditRoom::LeftOut {
return 0;
}
count.host_credit_room
}
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 may_pass(&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 = self.candidate(run, usual);
let backfill = self.backfill.as_ref()?;
backfill.passes(candidate).then_some(usual).flatten()
}
fn passes(&mut self, queued: Queued<'run>, listed: &[Queued<'run>]) -> Option<Duration> {
let usual = self.may_pass(queued, listed)?;
let candidate = self.candidate(queued.run, Some(usual));
if let Some(backfill) = self.backfill.as_mut() {
backfill.admit(candidate);
}
Some(usual)
}
fn candidate<'profile>(
&self,
run: &'profile Ran,
usual: Option<Duration>,
) -> Candidate<'profile> {
Candidate {
profile: &run.profile,
free_slots: self.free_slots(&run.profile),
usual,
caps: self.caps(&run.profile),
}
}
fn left_of(&self, count: pooled::Count, band: host::HostBand) -> Left {
let cpu = self.cpu_taken();
let left = |budget: u64, taken: u64| signed(budget).saturating_sub(signed(taken));
let taken = count.pooled().saturating_sub(self.mirror);
Left {
memory: self.budget.map(|budget| left(budget, taken)),
cpu: self.cpu_budget.map(|budget| left(budget, cpu)),
host: self.host_left_by(count, band),
}
}
fn cpu_taken(&self) -> u64 {
self.running
.iter()
.map(|running| running.cpu_at(self.moment))
.sum()
}
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: (running.started < self.moment && running.named(self.moment))
.then(|| self.predictor.usual(&Key::of(running.run), running.profile))
.flatten(),
memory: self.charge(running),
cpu: running.cpu_at(self.moment),
caps: self.caps(running.profile),
passed: running.backfilled.is_some(),
})
.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 {
if running.trace.is_none() || self.policy != Policy::Measured {
return match self.policy {
Policy::Caps => running.reserved,
Policy::Measured => running.reserved.max(running.peak),
};
}
let reserved = if running.named(self.moment) {
running.reserved
} else {
running.starting.max(running.reserved)
};
match running.reading(self.moment).unwrap_or(Reading::NotYet) {
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,
};
let count = self.count();
let needs = signed(starting.memory);
if let Some(budget) = self.budget {
let taken = count.pooled().saturating_sub(self.mirror);
if signed(budget).saturating_sub(signed(taken)) < needs {
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_with(count).is_some_and(|left| left < needs) {
return Err(Refused::Host(short(Scarce::Memory, Held::ByHost)));
}
if let Some(cpu_budget) = self.cpu_budget {
let taken = self.cpu_taken();
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),
starting_cpu: starting.cpu,
})
}
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.occupied().unwrap_or_default();
let boot = run
.started_at
.unwrap_or_default()
.saturating_sub(run.runner_started_at.max(run.queued_at));
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,
starting_cpu: admitted.starting_cpu,
key: Key::of(run),
basis: admitted.basis,
starting: admitted.starting,
trace: self.trace.and_then(|trace| trace.runs.get(&RunId::of(run))),
boot,
});
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)
}