use std::time::{Duration, SystemTime};
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);
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum Scarce {
Memory,
Cpu,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Wait {
pub job: u64,
pub since: SystemTime,
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct Waits {
pub memory: Option<Wait>,
pub cpu: Option<Wait>,
pub owner: Option<u64>,
pub served: bool,
}
impl Waits {
pub fn is_empty(&self) -> bool {
*self == Waits::default()
}
pub fn note(&mut self, scarce: Scarce, job: u64, now: SystemTime) -> bool {
let wait = match scarce {
Scarce::Memory => &mut self.memory,
Scarce::Cpu => &mut self.cpu,
};
let started = wait.is_none();
wait.get_or_insert(Wait { job, since: now });
started
}
pub fn retain(&mut self, queued: impl Fn(u64) -> bool) {
for wait in [&mut self.memory, &mut self.cpu] {
if wait.is_some_and(|wait| !queued(wait.job)) {
*wait = None;
}
}
self.owner = self.owner.filter(|job| queued(*job));
}
pub fn own(&mut self, job: u64) {
let waits = [self.memory, self.cpu];
if waits.iter().flatten().any(|wait| wait.job == job) {
self.owner = Some(job);
}
}
pub fn started(&mut self) {
self.served |= self.owner.is_some();
*self = Waits {
served: self.served,
..Waits::default()
};
}
pub fn emptied(&mut self) {
self.served = false;
}
fn limit(&self) -> Duration {
if self.served {
SERVED_PRIORITY_AFTER
} else {
PRIORITY_AFTER
}
}
pub fn deadlines(&self) -> impl Iterator<Item = SystemTime> {
let limit = self.limit();
[self.memory, self.cpu]
.into_iter()
.flatten()
.map(move |wait| wait.since + limit)
}
fn matured(&self, job: u64, now: SystemTime) -> Option<SystemTime> {
let limit = self.limit();
[self.memory, self.cpu]
.into_iter()
.flatten()
.filter(|wait| wait.job == job)
.map(|wait| wait.since + limit)
.filter(|reached| *reached <= now)
.min()
}
}
#[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(crate) struct Caps {
pub(crate) memory: u64,
pub(crate) 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,
}
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) 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: 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 {
left,
credit_room,
drained,
runners,
older,
} = around;
let mut left = left;
left.memory = left
.memory
.map(|memory| memory.saturating_add(signed(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 owner = ending.room_in(left, barrier.memory, barrier.cpu)?;
let starts = older.iter().filter_map(|job| ending.start_of(job, left));
let until = starts.fold(owner, Duration::min);
if until.is_zero() {
return None;
}
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 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.started_at >= barrier.since)
{
spare.take(runner.caps.memory, runner.caps.cpu);
}
Some(Backfill {
profile,
until,
spare,
})
}
pub(crate) fn admits(&mut self, candidate: Candidate<'_>) -> bool {
let caps = candidate.caps;
let admitted = candidate.usual.is_some_and(|usual| usual <= self.until)
&& self.spare.fits(caps.memory, caps.cpu)
&& (candidate.profile != self.profile || candidate.free_slots > 1);
if admitted {
self.spare.take(caps.memory, caps.cpu);
}
admitted
}
}