use std::collections::{BTreeMap, BTreeSet};
use super::invariants::Rng;
use crate::api::WaitCause;
use crate::scheduler::engine::open_waits::{
CAUSE_CHECKPOINT, CauseWaited, OpenWaits, WaitFor, Waited,
};
#[derive(Default)]
struct PerJob {
open: BTreeMap<u64, (WaitCause, u64)>,
taken: BTreeSet<u64>,
counted: BTreeMap<(u64, WaitCause), u64>,
}
impl PerJob {
fn count(&mut self, job: u64, now: u64) -> Option<(WaitCause, u64)> {
let (cause, since) = self.open.remove(&job)?;
*self.counted.entry((job, cause)).or_insert(0) += now.saturating_sub(since);
Some((cause, since))
}
fn hold(&mut self, held: &BTreeMap<u64, WaitCause>, going_on: &BTreeSet<u64>, now: u64) {
let open: Vec<u64> = self.open.keys().copied().collect();
for job in open {
if let Some((cause, _)) = self.count(job, now)
&& going_on.contains(&job)
{
self.open.insert(job, (cause, now));
}
}
for (job, cause) in held {
if !self.taken.contains(job) {
self.open.insert(*job, (*cause, now));
}
}
self.taken.clear();
}
}
fn add(counted: &mut BTreeMap<(u64, WaitCause), u64>, caused: Vec<CauseWaited>) {
for CauseWaited { job, cause, ms } in caused {
*counted.entry((job, cause)).or_insert(0) += ms;
}
}
fn some_causes(rng: &mut Rng) -> BTreeMap<u64, WaitCause> {
let causes = [WaitCause::Barrier, WaitCause::Host, WaitCause::Slot];
some_jobs(rng)
.into_iter()
.map(|job| (job, causes[usize::try_from(rng.below(3)).unwrap()]))
.collect()
}
#[derive(Default)]
struct TwoSets {
slot: (BTreeSet<u64>, u64),
host: (BTreeSet<u64>, u64),
}
impl TwoSets {
fn of(&mut self, kind: WaitFor) -> &mut (BTreeSet<u64>, u64) {
match kind {
WaitFor::Slot => &mut self.slot,
WaitFor::Host => &mut self.host,
}
}
fn end(&mut self, kind: WaitFor, jobs: &BTreeSet<u64>, now: u64) -> Option<Waited> {
let (waiting, since) = self.of(kind);
let ended: Vec<u64> = waiting.intersection(jobs).copied().collect();
if ended.is_empty() {
return None;
}
waiting.retain(|job| !jobs.contains(job));
Some(Waited {
kind,
jobs: ended,
ms: now.saturating_sub(*since),
})
}
fn commit(&mut self, kind: WaitFor, waiting: BTreeSet<u64>, now: u64) -> Vec<Waited> {
let other = match kind {
WaitFor::Slot => WaitFor::Host,
WaitFor::Host => WaitFor::Slot,
};
let moved = self.end(other, &waiting, now);
let (waited, since) = std::mem::replace(self.of(kind), (waiting, now));
let own = (!waited.is_empty()).then(|| Waited {
kind,
jobs: waited.into_iter().collect(),
ms: now.saturating_sub(since),
});
moved.into_iter().chain(own).collect()
}
fn started(&mut self, job: u64, now: u64) -> Vec<Waited> {
let jobs = BTreeSet::from([job]);
[WaitFor::Slot, WaitFor::Host]
.into_iter()
.filter_map(|kind| self.end(kind, &jobs, now))
.collect()
}
}
fn waited(kind: WaitFor, jobs: &[u64], ms: u64) -> Waited {
Waited {
kind,
jobs: jobs.to_vec(),
ms,
}
}
#[test]
fn a_wait_that_moves_to_the_host_and_back_counts_each_part_to_its_own_kind() {
let job = BTreeSet::from([3]);
let mut waits = OpenWaits::default();
assert!(
waits.open_wait(WaitFor::Slot, job.clone(), 10).is_empty(),
"a new wait has nothing to count yet"
);
assert_eq!(
waits.open_wait(WaitFor::Host, job.clone(), 25),
[waited(WaitFor::Slot, &[3], 15)],
"the slot wait ends where the host wait starts"
);
assert_eq!(waits.jobs(WaitFor::Slot), BTreeSet::new());
assert_eq!(waits.jobs(WaitFor::Host), job);
assert_eq!(
waits.open_wait(WaitFor::Slot, job.clone(), 40),
[waited(WaitFor::Host, &[3], 15)],
"the host wait counts from its own start, not the first slot wait's"
);
assert_eq!(waits.jobs(WaitFor::Host), BTreeSet::new());
assert_eq!(waits.jobs(WaitFor::Slot), job);
assert_eq!(
waits.end_wait(3, 50),
Some(waited(WaitFor::Slot, &[3], 10)),
"a start ends the wait it is in"
);
assert_eq!(waits.end_wait(3, 60), None, "and there is none left to end");
}
fn some_jobs(rng: &mut Rng) -> BTreeSet<u64> {
if rng.below(4) == 0 {
return BTreeSet::new();
}
(1..=6).filter(|_| rng.below(2) == 0).collect()
}
#[test]
fn any_sequence_of_commits_starts_and_causes_records_what_the_models_recorded() {
for seed in 0..512 {
let mut rng = Rng(seed);
let (mut waits, mut sets) = (OpenWaits::default(), TwoSets::default());
let (mut model, mut counted) = (PerJob::default(), BTreeMap::new());
let rough = seed % 2 == 0;
let mut exact = true;
let mut now = 1000_u64;
for _ in 0..60 {
now = match rng.below(10) {
0 => now,
1 if rough => {
exact = false;
now.saturating_sub(rng.below(50))
}
2 => now + CAUSE_CHECKPOINT,
_ => now + rng.below(100),
};
match rng.below(15) {
0..=3 => {
let jobs = some_jobs(&mut rng);
let opened = &jobs - &model.taken;
assert_eq!(
waits.open_wait(WaitFor::Slot, jobs, now),
sets.commit(WaitFor::Slot, opened, now),
"seed {seed}: a commit of slot waits"
);
}
4..=7 => {
let jobs = some_jobs(&mut rng);
let opened = &jobs - &model.taken;
assert_eq!(
waits.open_wait(WaitFor::Host, jobs, now),
sets.commit(WaitFor::Host, opened, now),
"seed {seed}: a commit of host waits"
);
}
8 => {
let job = rng.below(8) + 1;
assert_eq!(
waits.end_wait(job, now).into_iter().collect::<Vec<_>>(),
sets.started(job, now),
"seed {seed}: job {job} started"
);
}
9..=11 => {
let (held, going_on) = (some_causes(&mut rng), some_jobs(&mut rng));
add(&mut counted, waits.hold(&held, &going_on, now));
model.hold(&held, &going_on, now);
}
12 => {
let job = rng.below(8) + 1;
add(&mut counted, waits.booting(job, now).into_iter().collect());
if !model.taken.contains(&job) {
model.count(job, now);
model.open.insert(job, (WaitCause::Booting, now));
}
}
13 => {
let job = rng.below(8) + 1;
let ended = if rng.below(2) == 0 {
waits.end_cause(job, now)
} else {
model.taken.insert(job);
waits.taken(job, now)
};
add(&mut counted, ended.into_iter().collect());
model.count(job, now);
}
_ if rough => {
(waits, sets) = (OpenWaits::default(), TwoSets::default());
model.open.clear();
model.taken.clear();
exact = false;
}
_ => {}
}
for job in 1..=8 {
assert_eq!(
waits.cause(job),
model.open.get(&job).map(|(cause, _)| *cause),
"seed {seed}: job {job}'s cause"
);
}
assert_eq!(waits.jobs(WaitFor::Slot), sets.slot.0, "seed {seed}");
assert_eq!(waits.jobs(WaitFor::Host), sets.host.0, "seed {seed}");
}
for kind in [WaitFor::Slot, WaitFor::Host] {
assert_eq!(
waits.open_wait(kind, BTreeSet::new(), now + 7),
sets.commit(kind, BTreeSet::new(), now + 7),
"seed {seed}: every wait still open counts from its own start"
);
}
add(
&mut counted,
waits.hold(&BTreeMap::new(), &BTreeSet::new(), now + 7),
);
model.hold(&BTreeMap::new(), &BTreeSet::new(), now + 7);
assert_counted(seed, exact, counted, model.counted);
}
}
fn assert_counted(
seed: u64,
exact: bool,
mut counted: BTreeMap<(u64, WaitCause), u64>,
mut model: BTreeMap<(u64, WaitCause), u64>,
) {
counted.retain(|_, ms| *ms > 0);
model.retain(|_, ms| *ms > 0);
if exact {
assert_eq!(
counted, model,
"seed {seed}: each job counts each stretch once, to the cause it was held for"
);
}
for (key, ms) in &counted {
assert!(
model.get(key).is_some_and(|model| ms <= model),
"seed {seed}: {key:?} counts {ms} ms, more than it waited: {:?}",
model.get(key)
);
}
}
#[test]
fn a_cause_that_goes_on_is_counted_only_when_it_changes_ends_or_a_checkpoint_passes() {
let mut waits = OpenWaits::default();
let held = BTreeMap::from([(1, WaitCause::Host), (2, WaitCause::Slot)]);
let none = BTreeSet::new();
let start = 10 * CAUSE_CHECKPOINT;
assert_eq!(waits.hold(&held, &none, start), []);
for step in 1..10 {
assert_eq!(
waits.hold(&held, &none, start + step * 1000),
[],
"an identical plan writes nothing"
);
}
let checkpoint = start + CAUSE_CHECKPOINT;
let counted = |ms| {
vec![
CauseWaited {
job: 1,
cause: WaitCause::Host,
ms,
},
CauseWaited {
job: 2,
cause: WaitCause::Slot,
ms,
},
]
};
assert_eq!(
waits.hold(&held, &none, checkpoint),
counted(CAUSE_CHECKPOINT)
);
assert_eq!(waits.hold(&held, &none, checkpoint + 1000), []);
let moved = BTreeMap::from([(1, WaitCause::Host), (2, WaitCause::Barrier)]);
assert_eq!(
waits.hold(&moved, &none, checkpoint + 2000),
[CauseWaited {
job: 2,
cause: WaitCause::Slot,
ms: 2000
}]
);
}