use std::collections::BTreeMap;
use std::time::Duration;
use super::trace::Reading;
use super::{HIGH_WATER, Key};
use crate::api::Basis;
pub const POOL_AFTER: Duration = Duration::from_secs(60);
pub const MOST_CREDIT: u64 = 6 << 30;
pub const HIGH_WATER_RESERVE: u64 = 2 << 30;
pub const HOST_RESERVE_JOBS: usize = 2;
pub const HOST_RESERVE_FLOOR: u64 = 6 << 30;
pub const GROWTH_JOBS: usize = 3;
pub const GROWTH_FLOOR: u64 = 6 << 30;
pub const GROWTH_CEILING: u64 = 14 << 30;
pub const GROWTH: Growth = Growth {
jobs: GROWTH_JOBS,
bound: Bound::HighWater,
young: Young::Covered,
below: Below::Credits,
hold: Hold::Free,
ceiling: Some(GROWTH_CEILING),
};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Growth {
pub jobs: usize,
pub bound: Bound,
pub young: Young,
pub below: Below,
pub hold: Hold,
pub ceiling: Option<u64>,
}
impl Growth {
pub fn top(jobs: usize) -> Self {
Self {
jobs,
bound: Bound::Open,
young: Young::Ranked,
below: Below::Plain,
hold: Hold::Free,
ceiling: None,
}
}
#[must_use]
pub fn held(self) -> Self {
Self {
hold: Hold::Held,
..self
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Bound {
HighWater,
Open,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Young {
Covered,
Ranked,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Below {
Credits,
Plain,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Hold {
Free,
Held,
}
#[derive(Debug, Clone, Copy)]
pub struct Runner<'run> {
pub key: Option<&'run Key>,
pub takes: u64,
pub used: Reading,
pub ran: Option<Duration>,
pub basis: Option<Basis>,
}
impl Runner<'_> {
fn pooled(&self) -> Option<u64> {
let predicted = matches!(
self.basis,
Some(Basis::Job { .. } | Basis::Profile { .. } | Basis::ProfileMax { .. })
);
let settled = self.ran.is_some_and(|ran| ran >= POOL_AFTER);
self.sampled()
.filter(|_| predicted && settled && self.key.is_some())
}
fn young(&self) -> bool {
matches!(self.used, Reading::NotYet) || self.ran.is_none_or(|ran| ran < POOL_AFTER)
}
fn sampled(&self) -> Option<u64> {
match self.used {
Reading::Used(used) => Some(used.min(self.takes)),
Reading::NotYet | Reading::Stale => None,
}
}
fn headroom(&self) -> Option<u64> {
match self.used {
Reading::Used(used) => Some(self.takes.saturating_sub(used)),
Reading::NotYet => Some(self.takes),
Reading::Stale => None,
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Slice {
pub memory: u64,
pub memory_max: Option<u64>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Host {
pub available: u64,
pub keeps: u64,
pub stalled: bool,
}
#[derive(Debug, Clone, Copy)]
pub struct Snapshot<'run> {
pub runners: &'run [Runner<'run>],
pub committed: u64,
pub slice: Option<Slice>,
pub host: Option<Host>,
pub most: u64,
pub host_reserve: bool,
pub growth: Option<Growth>,
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct Count {
pub plain: u64,
pub credit: u64,
pub runners: usize,
pub host_credit: u64,
pub used: u64,
pub credit_room: u64,
pub host_credit_room: u64,
pub kept: Option<u64>,
}
impl Count {
pub fn pooled(self) -> u64 {
self.plain - self.credit
}
pub fn hosted(self) -> u64 {
self.plain - self.host_credit
}
}
pub fn count(snapshot: &Snapshot<'_>) -> Count {
let takes: u64 = snapshot.runners.iter().map(|runner| runner.takes).sum();
let plain = takes.saturating_add(snapshot.committed);
match snapshot.growth {
Some(growth) => grown(snapshot, plain, growth),
None => credits(snapshot, plain),
}
}
fn credits(snapshot: &Snapshot<'_>, plain: u64) -> Count {
let takes = plain.saturating_sub(snapshot.committed);
let mut room: BTreeMap<&Key, u64> = BTreeMap::new();
let mut runners = 0;
for runner in snapshot.runners {
if let (Some(key), Some(used)) = (runner.key, runner.pooled()) {
*room.entry(key).or_default() += runner.takes.saturating_sub(used);
runners += 1;
}
}
let added: u64 = room.values().sum();
let squares: u128 = room
.values()
.map(|room| u128::from(*room) * u128::from(*room))
.sum();
let credit = added
.saturating_sub(root(squares))
.min(snapshot.most)
.min(snapshot.slice.map_or(0, slice_room))
.min(snapshot.host.map_or(0, host_room));
let read = snapshot.slice.is_some() && snapshot.host.is_some_and(|host| !host.stalled);
let host_credit = if snapshot.host_reserve && read {
added.saturating_sub(kept_for_growth(room.into_values().collect()))
} else {
0
};
let used = used(snapshot.runners);
Count {
plain,
credit,
runners: if credit > 0 { runners } else { 0 },
host_credit,
used,
credit_room: snapshot.most.saturating_sub(credit),
host_credit_room: if snapshot.host_reserve {
takes
.saturating_sub(HOST_RESERVE_FLOOR)
.saturating_sub(host_credit)
} else {
0
},
kept: None,
}
}
fn used(runners: &[Runner<'_>]) -> u64 {
runners.iter().filter_map(Runner::sampled).sum()
}
fn grown(snapshot: &Snapshot<'_>, plain: u64, growth: Growth) -> Count {
let used = used(snapshot.runners);
let takes: Vec<u64> = snapshot.runners.iter().map(|runner| runner.takes).collect();
let lowest = snapshot
.committed
.saturating_add(takes.iter().sum::<u64>().min(room(&takes, growth.jobs)))
.max(
growth
.ceiling
.map_or(0, |ceiling| plain.saturating_sub(ceiling)),
);
let low = snapshot
.host
.is_none_or(|host| host.stalled || host.available < host.keeps);
if growth.hold == Hold::Held || snapshot.slice.is_none() || low {
let below = match growth.below {
Below::Credits => credits(snapshot, plain),
Below::Plain => Count {
plain,
used,
..Count::default()
},
};
return Count {
credit_room: below.credit_room.max(below.pooled().saturating_sub(lowest)),
host_credit_room: below
.host_credit_room
.max(below.hosted().saturating_sub(lowest)),
kept: None,
..below
};
}
let stale: u64 = snapshot
.runners
.iter()
.filter(|runner| runner.headroom().is_none())
.map(|runner| runner.takes)
.sum();
let headroom: u64 = snapshot.runners.iter().filter_map(Runner::headroom).sum();
let kept = headroom.min(growth_room(snapshot.runners, growth));
let counted = snapshot
.committed
.saturating_add(used)
.saturating_add(stale)
.saturating_add(kept);
let credit = plain.saturating_sub(counted);
let (credit, host_credit) = match growth.bound {
Bound::HighWater => {
let host = snapshot.host.map_or(0, host_room);
let slice = snapshot.slice.map_or(0, slice_room);
(credit.min(slice).min(host), credit.min(host))
}
Bound::Open => (credit, credit),
};
let (credit, host_credit) = match growth.ceiling {
Some(ceiling) => (credit.min(ceiling), host_credit.min(ceiling)),
None => (credit, host_credit),
};
let count = Count {
plain,
credit,
runners: snapshot
.runners
.iter()
.filter(|runner| runner.headroom().is_some())
.count(),
host_credit,
used,
credit_room: 0,
host_credit_room: 0,
kept: Some(kept),
};
Count {
credit_room: count.pooled().saturating_sub(lowest),
host_credit_room: count.hosted().saturating_sub(lowest),
..count
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Tally<Id> {
runners: Vec<Tallied<Id>>,
committed: u64,
slice: Option<Slice>,
host: Option<Host>,
most: u64,
host_reserve: bool,
growth: Option<Growth>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
struct Tallied<Id> {
id: Option<Id>,
key: Option<Key>,
takes: u64,
used: Reading,
ran: Option<Duration>,
basis: Option<Basis>,
}
impl<Id: PartialEq> Tally<Id> {
pub fn new(snapshot: &Snapshot<'_>, ids: impl IntoIterator<Item = Id>) -> Self {
Self {
runners: snapshot
.runners
.iter()
.zip(ids)
.map(|(runner, id)| Tallied {
id: Some(id),
key: runner.key.cloned(),
takes: runner.takes,
used: runner.used,
ran: runner.ran,
basis: runner.basis,
})
.collect(),
committed: snapshot.committed,
slice: snapshot.slice,
host: snapshot.host,
most: snapshot.most,
host_reserve: snapshot.host_reserve,
growth: snapshot.growth,
}
}
pub fn count(&self) -> Count {
let runners: Vec<Runner<'_>> = self
.runners
.iter()
.map(|runner| Runner {
key: runner.key.as_ref(),
takes: runner.takes,
used: runner.used,
ran: runner.ran,
basis: runner.basis,
})
.collect();
count(&Snapshot {
runners: &runners,
committed: self.committed,
slice: self.slice,
host: self.host,
most: self.most,
host_reserve: self.host_reserve,
growth: self.growth,
})
}
pub fn start(&mut self, takes: u64) {
self.runners.push(Tallied {
id: None,
key: None,
takes,
used: Reading::NotYet,
ran: Some(Duration::ZERO),
basis: None,
});
}
pub fn stop(&mut self, id: &Id) {
self.runners.retain(|runner| runner.id.as_ref() != Some(id));
}
}
pub fn growth_room(runners: &[Runner<'_>], growth: Growth) -> u64 {
let headroom: Vec<u64> = runners.iter().filter_map(Runner::headroom).collect();
let largest = room(&headroom, growth.jobs);
match growth.young {
Young::Covered => largest.max(
runners
.iter()
.filter(|runner| runner.young())
.filter_map(Runner::headroom)
.sum(),
),
Young::Ranked => largest,
}
}
fn room(headroom: &[u64], jobs: usize) -> u64 {
largest(headroom.to_vec(), jobs).max(GROWTH_FLOOR)
}
fn kept_for_growth(room: Vec<u64>) -> u64 {
largest(room, HOST_RESERVE_JOBS).max(HOST_RESERVE_FLOOR)
}
fn largest(mut values: Vec<u64>, jobs: usize) -> u64 {
values.sort_unstable_by(|a, b| b.cmp(a));
values.iter().take(jobs).sum()
}
fn slice_room(slice: Slice) -> u64 {
let Some(memory_max) = slice.memory_max else {
return 0;
};
let mark = u128::from(memory_max) * u128::from(HIGH_WATER) / 100;
u64::try_from(mark)
.unwrap_or(u64::MAX)
.saturating_sub(slice.memory)
.saturating_sub(HIGH_WATER_RESERVE)
}
fn host_room(host: Host) -> u64 {
if host.stalled {
return 0;
}
host.available.saturating_sub(host.keeps)
}
fn root(squares: u128) -> u64 {
let root = squares.isqrt();
let exact = root * root == squares;
u64::try_from(root + u128::from(!exact)).unwrap_or(u64::MAX)
}
#[cfg(test)]
mod tests;