use std::time::{Duration, SystemTime};
use super::waits::Waits;
use super::{Left, signed};
use crate::api::Waiting;
pub const PRIORITY_AFTER: Duration = Duration::from_secs(600);
pub const SERVED_PRIORITY_AFTER: Duration = Duration::from_secs(120);
pub const SHORT_RUN: Duration = Duration::from_secs(120);
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub enum RunTimes {
#[default]
Fresh,
Stale,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum Scarce {
Memory,
Cpu,
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct Drained {
pub memory: Option<i64>,
pub cpu: Option<i64>,
pub host: Option<i64>,
pub host_plain: Option<i64>,
}
impl Drained {
fn holds(self, memory: u64, cpu: u64, held: Held) -> bool {
let fits = |room: Option<i64>, needs: u64| {
room.is_none_or(|room| room >= i64::try_from(needs).unwrap_or(i64::MAX))
};
let host = match held {
Held::ByHost => self.host,
Held::ByBudget => self.host_plain,
};
fits(self.memory, memory) && fits(host, memory) && fits(self.cpu, cpu)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Held {
ByHost,
ByBudget,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Short {
pub job: u64,
pub scarce: Scarce,
pub held: Held,
pub memory: u64,
pub cpu: u64,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Barrier {
pub job: u64,
pub scarce: Scarce,
pub memory: u64,
pub cpu: u64,
pub since: SystemTime,
}
impl Barrier {
pub fn of(
short: Short,
waits: &Waits,
drained: Option<Drained>,
now: SystemTime,
) -> Option<Barrier> {
let drained = drained?;
let since = waits.matured(short.job, now)?;
let holds = drained.holds(short.memory, short.cpu, short.held);
holds.then_some(Barrier {
job: short.job,
scarce: short.scarce,
memory: short.memory,
cpu: short.cpu,
since,
})
}
pub fn reason(self) -> Waiting {
match self.scarce {
Scarce::Memory => Waiting::BehindMemory { job: self.job },
Scarce::Cpu => Waiting::BehindCpu { job: self.job },
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Caps {
pub memory: u64,
pub cpu: u64,
}
#[derive(Debug, Clone, Copy)]
pub(crate) struct Runner<'plan> {
pub(crate) profile: &'plan str,
pub(crate) started_at: SystemTime,
pub(crate) usual: Option<Duration>,
pub(crate) memory: u64,
pub(crate) cpu: u64,
pub(crate) caps: Caps,
pub(crate) passed: bool,
}
impl Runner<'_> {
fn left_to_run(&self, now: SystemTime) -> Duration {
let Ok(ran) = now.duration_since(self.started_at) else {
return Duration::ZERO;
};
self.usual
.map_or(Duration::ZERO, |usual| usual.saturating_sub(ran))
}
}
#[derive(Debug, Clone, Copy)]
pub(crate) struct Older<'plan> {
pub(crate) profile: &'plan str,
pub(crate) free_slot: bool,
pub(crate) memory: u64,
pub(crate) cpu: u64,
}
#[derive(Debug, Clone, Copy)]
pub(crate) struct Around<'plan> {
pub(crate) left: Left,
pub(crate) run_times: RunTimes,
pub(crate) credit_room: u64,
pub(crate) host_credit_room: u64,
pub(crate) drained: Drained,
pub(crate) runners: &'plan [Runner<'plan>],
pub(crate) older: &'plan [Older<'plan>],
}
#[derive(Debug, Clone, Copy)]
pub(crate) struct Candidate<'plan> {
pub(crate) profile: &'plan str,
pub(crate) free_slots: usize,
pub(crate) usual: Option<Duration>,
pub(crate) caps: Caps,
}
#[derive(Debug, Clone, Copy)]
pub(crate) struct Backfill<'plan> {
profile: &'plan str,
until: Option<Duration>,
short: Option<Duration>,
spare: Left,
}
struct Ending<'plan>(Vec<(Duration, Runner<'plan>)>);
impl Ending<'_> {
fn room_in(&self, left: Left, memory: u64, cpu: u64) -> Option<Duration> {
if left.fits(memory, cpu) {
return Some(Duration::ZERO);
}
let mut room = left;
self.0.iter().find_map(|(left_to_run, runner)| {
room.give(runner.memory, runner.cpu);
room.fits(memory, cpu).then_some(*left_to_run)
})
}
fn start_of(&self, older: &Older<'_>, left: Left) -> Option<Duration> {
let room = self.room_in(left, older.memory, older.cpu)?;
let in_profile = |(_, runner): &&(Duration, Runner<'_>)| runner.profile == older.profile;
let slot = if older.free_slot {
Duration::ZERO
} else {
self.0.iter().find(in_profile)?.0
};
Some(room.max(slot))
}
}
impl<'plan> Backfill<'plan> {
pub(crate) fn behind(
barrier: Barrier,
profile: &'plan str,
around: Around<'_>,
now: SystemTime,
) -> Option<Backfill<'plan>> {
let Around {
mut left,
run_times,
credit_room,
host_credit_room,
drained,
runners,
older,
} = around;
let mut freed = left;
for runner in runners.iter().filter(|runner| runner.passed) {
freed.give(runner.memory, runner.cpu);
}
let waiting_for_passes = freed.fits(barrier.memory, barrier.cpu);
left.memory = left
.memory
.map(|memory| memory.saturating_add(signed(credit_room)));
left.host = left
.host
.map(|host| host.saturating_add(signed(host_credit_room)));
let mut ending: Vec<(Duration, Runner<'_>)> = runners
.iter()
.map(|runner| (runner.left_to_run(now), *runner))
.collect();
ending.sort_by_key(|(left_to_run, _)| *left_to_run);
let ending = Ending(ending);
let until = ending
.room_in(left, barrier.memory, barrier.cpu)
.map(|owner| {
let starts = older.iter().filter_map(|job| ending.start_of(job, left));
starts.fold(owner, Duration::min)
})
.filter(|until| !until.is_zero());
let mut spare = Left {
memory: drained.memory,
cpu: drained.cpu,
host: drained.host,
};
let served = older.iter().filter(|job| spare.fits(job.memory, job.cpu));
let plain_drain = Left {
host: drained.host_plain.or(drained.host),
..spare
};
let short = older
.iter()
.filter(|job| plain_drain.fits(job.memory, job.cpu))
.map(|job| ending.start_of(job, left).unwrap_or(Duration::ZERO))
.fold(SHORT_RUN, Duration::min);
let short = (run_times == RunTimes::Fresh && !waiting_for_passes && !short.is_zero())
.then_some(short);
if until.is_none() && short.is_none() {
return None;
}
let memory = served.clone().map(|job| job.memory).max().unwrap_or(0);
let cpu = served.map(|job| job.cpu).max().unwrap_or(0);
spare.take(barrier.memory.max(memory), barrier.cpu.max(cpu));
for runner in runners
.iter()
.filter(|runner| runner.passed && runner.started_at >= barrier.since)
{
spare.take(runner.caps.memory, runner.caps.cpu);
}
Some(Backfill {
profile,
until,
short,
spare,
})
}
pub(crate) fn passes(&self, candidate: Candidate<'_>) -> bool {
let Some(usual) = candidate.usual else {
return false;
};
let other_profile = candidate.profile != self.profile;
let in_time = self.until.is_some_and(|until| usual <= until)
&& (other_profile || candidate.free_slots > 1);
let short = other_profile && self.short.is_some_and(|most| usual <= most);
(in_time || short) && self.spare.fits(candidate.caps.memory, candidate.caps.cpu)
}
pub(crate) fn admit(&mut self, candidate: Candidate<'_>) {
self.spare.take(candidate.caps.memory, candidate.caps.cpu);
}
}