use super::*;
use crate::scheduler::{Barrier, Drained, PRIORITY_AFTER, SERVED_PRIORITY_AFTER, StartFor};
const LONG_AGO: Duration = Duration::from_mins(15);
fn waited(job: u64) -> Wait {
Wait {
job,
since: now() - LONG_AGO,
}
}
fn pool(name: &str, memory: u64, waits: Waits, queued: &[u64]) -> Repository {
Repository {
runner_memory: Some(memory),
waits,
..repository(
name,
"app",
queued.iter().map(|id| job(*id, &["app"])).collect(),
)
}
}
fn starved_of_memory(job: u64) -> Waits {
Waits::default().with_memory(Some(waited(job)))
}
fn memory_left(free: i64) -> Budget {
Budget {
memory: Some(free),
drained: Drained {
memory: Some(16 * i64::try_from(GIB).unwrap()),
..Drained::default()
},
..Budget::default()
}
}
fn gib(amount: i64) -> i64 {
amount * i64::try_from(GIB).unwrap()
}
fn a_big_job_and_a_small_one(waits: Waits) -> [Repository; 2] {
[
pool("o/big", 8 * GIB, waits, &[1]),
pool("o/small", GIB, Waits::default(), &[2]),
]
}
#[test]
fn younger_jobs_wait_behind_one_starved_of_memory_though_they_fit() {
let plan = plan(
&a_big_job_and_a_small_one(starved_of_memory(1)),
&profiles(vec![Slot::Free, Slot::Free]),
memory_left(gib(4)),
now(),
);
assert_eq!(starts(&plan.decisions), []);
assert_eq!(
plan.waiting,
BTreeMap::from([
(
1,
Waiting::Memory {
needs: 8 * GIB,
free: 4 * GIB
}
),
(2, Waiting::BehindMemory { job: 1 }),
])
);
assert_eq!(
plan.barrier,
Some(Barrier {
job: 1,
scarce: Scarce::Memory,
memory: 8 * GIB,
cpu: 2000,
since: now() - LONG_AGO + PRIORITY_AFTER,
})
);
}
#[test]
fn a_job_short_of_memory_lets_younger_ones_past_until_it_waited_long_enough() {
let just_now = Waits::default().with_memory(Some(Wait {
job: 1,
since: now() - PRIORITY_AFTER + Duration::from_secs(1),
}));
let plan = plan(
&a_big_job_and_a_small_one(just_now),
&profiles(vec![Slot::Free, Slot::Free]),
memory_left(gib(4)),
now(),
);
assert_eq!(starts(&plan.decisions), [(0, "o/small")]);
assert_eq!(plan.barrier, None);
assert!(
plan.held.contains(&held("o/big", 1, Scarce::Memory)),
"the plan names the job whose wait goes on"
);
}
fn waited_for(job: u64, waited: Duration) -> Waits {
Waits::default().with_memory(Some(Wait {
job,
since: now() - waited,
}))
}
#[test]
fn a_job_holds_after_the_limit_of_whether_a_barrier_served_its_pool() {
let barrier = |waits: Waits| {
plan(
&a_big_job_and_a_small_one(waits),
&profiles(vec![Slot::Free, Slot::Free]),
memory_left(gib(4)),
now(),
)
.barrier
.map(|barrier| barrier.job)
};
let second = Duration::from_secs(1);
let served = |waits: Waits| waits.with_served(true);
assert_eq!(
barrier(waited_for(1, PRIORITY_AFTER.saturating_sub(second))),
None
);
assert_eq!(barrier(waited_for(1, PRIORITY_AFTER)), Some(1));
assert_eq!(barrier(waited_for(1, SERVED_PRIORITY_AFTER)), None);
assert_eq!(
barrier(served(waited_for(
1,
SERVED_PRIORITY_AFTER.saturating_sub(second)
))),
None
);
assert_eq!(
barrier(served(waited_for(1, SERVED_PRIORITY_AFTER))),
Some(1)
);
}
#[test]
fn an_older_job_of_an_unserved_pool_takes_the_barrier_when_it_matures() {
let owner = |older_waited| {
let served = waited_for(2, SERVED_PRIORITY_AFTER).with_served(true);
plan(
&[
pool("o/older", 8 * GIB, waited_for(1, older_waited), &[1]),
pool("o/served", 8 * GIB, served, &[2]),
pool("o/small", GIB, Waits::default(), &[3]),
],
&profiles(vec![Slot::Free, Slot::Free]),
memory_left(gib(4)),
now(),
)
.barrier
.map(|barrier| barrier.job)
};
assert_eq!(
owner(PRIORITY_AFTER.saturating_sub(Duration::from_secs(1))),
Some(2)
);
assert_eq!(owner(PRIORITY_AFTER), Some(1));
}
#[test]
fn a_wait_counts_for_its_own_job_alone() {
let plan = plan(
&[
pool("o/big", 8 * GIB, starved_of_memory(9), &[1]),
pool("o/small", GIB, Waits::default(), &[2]),
],
&profiles(vec![Slot::Free, Slot::Free]),
memory_left(gib(4)),
now(),
);
assert_eq!(starts(&plan.decisions), [(0, "o/small")]);
}
#[test]
fn a_budget_overdrawn_now_still_erects_a_barrier_as_draining_repays_it() {
let plan = plan(
&a_big_job_and_a_small_one(starved_of_memory(1)),
&profiles(vec![Slot::Free, Slot::Free]),
memory_left(gib(-3)),
now(),
);
assert_eq!(plan.barrier.map(|barrier| barrier.job), Some(1));
assert_eq!(plan.waiting[&2], Waiting::BehindMemory { job: 1 });
}
#[test]
fn a_runner_no_empty_slice_holds_erects_no_barrier() {
let budget = Budget {
drained: Drained {
memory: Some(gib(7)),
..Drained::default()
},
..memory_left(gib(4))
};
let plan = plan(
&a_big_job_and_a_small_one(starved_of_memory(1)),
&profiles(vec![Slot::Free, Slot::Free]),
budget,
now(),
);
assert_eq!(plan.barrier, None);
assert_eq!(starts(&plan.decisions), [(0, "o/small")]);
assert_eq!(
plan.waiting[&1],
Waiting::Memory {
needs: 8 * GIB,
free: 4 * GIB
},
"it says why it waits as before"
);
}
#[test]
fn a_host_short_even_with_an_empty_slice_erects_no_barrier() {
let budget = Budget {
memory: Some(gib(12)),
host: Some(gib(4)),
drained: Drained {
memory: Some(gib(16)),
host: Some(gib(6)),
..Drained::default()
},
..Budget::default()
};
let plan = plan(
&a_big_job_and_a_small_one(starved_of_memory(1)),
&profiles(vec![Slot::Free, Slot::Free]),
budget,
now(),
);
assert_eq!(plan.barrier, None);
assert_eq!(starts(&plan.decisions), [(0, "o/small")]);
assert!(
matches!(plan.waiting[&1], Waiting::HostMemory { .. }),
"{:?}",
plan.waiting
);
}
#[test]
fn without_a_memory_budget_or_a_host_figure_a_wait_changes_nothing() {
let plan = plan(
&a_big_job_and_a_small_one(starved_of_memory(1)),
&profiles(vec![Slot::Free, Slot::Free]),
Budget::default(),
now(),
);
assert_eq!(starts(&plan.decisions), [(0, "o/big"), (1, "o/small")]);
assert_eq!(plan.barrier, None);
}
#[test]
fn a_host_figure_alone_erects_a_barrier() {
let budget = Budget {
host: Some(gib(4)),
drained: Drained {
host: Some(gib(16)),
..Drained::default()
},
..Budget::default()
};
let plan = plan(
&a_big_job_and_a_small_one(starved_of_memory(1)),
&profiles(vec![Slot::Free, Slot::Free]),
budget,
now(),
);
assert_eq!(plan.barrier.map(|barrier| barrier.job), Some(1));
assert_eq!(plan.waiting[&2], Waiting::BehindMemory { job: 1 });
}
#[test]
fn a_safety_interlock_suspends_the_barrier_and_starts_no_wait() {
let budget = Budget {
held: true,
..memory_left(0)
};
let plan = plan(
&[
pool("o/big", 8 * GIB, starved_of_memory(1), &[1]),
pool("o/small", GIB, Waits::default(), &[2]),
],
&profiles(vec![Slot::Free, Slot::Free]),
budget,
now(),
);
assert_eq!(plan.barrier, None);
assert_eq!(starts(&plan.decisions), []);
assert_eq!(
plan.waiting[&2],
Waiting::Memory {
needs: GIB,
free: 0
}
);
assert_eq!(plan.held, []);
}
#[test]
fn a_second_starved_pool_waits_behind_the_first_and_keeps_ageing() {
let plan = plan(
&[
pool("o/first", 8 * GIB, starved_of_memory(1), &[1]),
pool("o/second", 8 * GIB, Waits::default(), &[2]),
pool("o/small", GIB, Waits::default(), &[3]),
],
&profiles(vec![Slot::Free; 3]),
memory_left(gib(4)),
now(),
);
assert_eq!(plan.barrier.map(|barrier| barrier.job), Some(1));
assert_eq!(plan.waiting[&2], Waiting::BehindMemory { job: 1 });
assert_eq!(plan.waiting[&3], Waiting::BehindMemory { job: 1 });
assert_eq!(
plan.held,
[
held("o/first", 1, Scarce::Memory),
held("o/second", 2, Scarce::Memory)
]
);
}
#[test]
fn an_older_job_that_fits_starts_before_the_barrier_of_a_younger_one() {
let plan = plan(
&[
pool("o/small", GIB, Waits::default(), &[1]),
pool("o/big", 8 * GIB, starved_of_memory(2), &[2]),
],
&profiles(vec![Slot::Free, Slot::Free]),
memory_left(gib(4)),
now(),
);
assert_eq!(starts(&plan.decisions), [(0, "o/small")]);
assert_eq!(plan.barrier.map(|barrier| barrier.job), Some(2));
}
#[test]
fn the_owner_starting_in_this_plan_erects_no_barrier() {
let plan = plan(
&a_big_job_and_a_small_one(starved_of_memory(1)),
&profiles(vec![Slot::Free, Slot::Free]),
memory_left(gib(9)),
now(),
);
assert_eq!(starts(&plan.decisions), [(0, "o/big"), (1, "o/small")]);
assert_eq!(plan.barrier, None);
}
#[test]
fn a_starved_pool_without_a_free_slot_erects_no_barrier_and_keeps_its_wait() {
let repositories = [
pool("o/big", 8 * GIB, starved_of_memory(1), &[1]),
Repository {
runner_memory: Some(GIB),
..repository("o/small", "small", vec![job(2, &["small"])])
},
];
let mut profiles = profiles(vec![Slot::Runner(RunnerSlot {
repository: "o/other".to_owned(),
busy: true,
started_at: now(),
memory: 4 * GIB,
cpu: 2000,
usual: None,
caps: Caps {
memory: 4 * GIB,
cpu: 2000,
},
behind: None,
})]);
profiles.insert(
"small".to_owned(),
Profile {
memory: GIB,
cpus: 1000,
preparing: None,
upkeep_due: false,
count: 1,
ran: Vec::new(),
slots: vec![Slot::Free],
},
);
let plan = plan(&repositories, &profiles, memory_left(gib(4)), now());
assert_eq!(plan.barrier, None);
assert_eq!(starts(&plan.decisions), [(0, "o/small")]);
assert_eq!(
plan.waiting[&1],
Waiting::NoSlot {
profile: "app".to_owned()
}
);
}
#[test]
fn a_job_starved_of_cpu_that_now_lacks_memory_owns_the_barrier_as_memory() {
let waits = Waits::default().with_cpu(Some(waited(1)));
let plan = plan(
&a_big_job_and_a_small_one(waits),
&profiles(vec![Slot::Free, Slot::Free]),
memory_left(gib(4)),
now(),
);
assert_eq!(
plan.barrier,
Some(Barrier {
job: 1,
scarce: Scarce::Memory,
memory: 8 * GIB,
cpu: 2000,
since: now() - LONG_AGO + PRIORITY_AFTER,
})
);
assert_eq!(plan.waiting[&2], Waiting::BehindMemory { job: 1 });
}
#[test]
fn a_job_starved_of_memory_that_now_lacks_cpu_owns_the_barrier_as_cpu() {
let repositories = [
Repository {
runner_cpu: Some(4000),
..pool("o/big", 8 * GIB, starved_of_memory(1), &[1])
},
Repository {
runner_cpu: Some(500),
..pool("o/small", GIB, Waits::default(), &[2])
},
];
let budget = Budget {
cpu: Some(1000),
..memory_left(gib(12))
};
let plan = plan(
&repositories,
&profiles(vec![Slot::Free, Slot::Free]),
budget,
now(),
);
assert_eq!(
plan.barrier,
Some(Barrier {
job: 1,
scarce: Scarce::Cpu,
memory: 8 * GIB,
cpu: 4000,
since: now() - LONG_AGO + PRIORITY_AFTER,
})
);
assert_eq!(plan.waiting[&2], Waiting::BehindCpu { job: 1 });
}
#[test]
fn opposing_demands_share_one_barrier_the_older_ones() {
let repositories = [
Repository {
runner_cpu: Some(500),
..pool("o/memory", 8 * GIB, starved_of_memory(1), &[1])
},
Repository {
runner_cpu: Some(4000),
..pool(
"o/cpu",
GIB,
Waits::default().with_cpu(Some(waited(2))),
&[2],
)
},
];
let budget = Budget {
cpu: Some(1000),
..memory_left(gib(4))
};
let plan = plan(
&repositories,
&profiles(vec![Slot::Free, Slot::Free]),
budget,
now(),
);
assert_eq!(plan.barrier.map(|barrier| barrier.job), Some(1));
assert_eq!(plan.waiting[&2], Waiting::BehindMemory { job: 1 });
}
#[test]
fn a_starved_pool_that_may_not_start_erects_no_barrier() {
for (paused, held) in [
(true, None),
(
false,
Some(Hold {
until: now() + LONG_AGO,
cause: HoldCause::Start,
}),
),
] {
let mut repositories = a_big_job_and_a_small_one(starved_of_memory(1));
repositories[0].paused = paused;
repositories[0].held = held;
let plan = plan(
&repositories,
&profiles(vec![Slot::Free, Slot::Free]),
memory_left(gib(4)),
now(),
);
assert_eq!(plan.barrier, None);
assert_eq!(starts(&plan.decisions), [(0, "o/small")]);
}
}
#[test]
fn a_job_behind_a_barrier_with_no_slot_says_so_and_asks_for_no_slot() {
let repositories = [
pool("o/big", 8 * GIB, starved_of_memory(1), &[1]),
Repository {
runner_memory: Some(GIB),
..repository("o/full", "full", vec![job(2, &["full"])])
},
Repository {
runner_memory: Some(GIB),
..repository("o/seeding", "seeding", vec![job(3, &["seeding"])])
},
];
let mut profiles = profiles(vec![Slot::Free]);
let other = Profile {
memory: GIB,
cpus: 1000,
preparing: None,
upkeep_due: false,
count: 1,
ran: Vec::new(),
slots: vec![Slot::Runner(RunnerSlot {
repository: "o/other".to_owned(),
busy: true,
started_at: now(),
memory: GIB,
cpu: 1000,
usual: None,
caps: Caps {
memory: GIB,
cpu: 1000,
},
behind: None,
})],
};
profiles.insert("full".to_owned(), other.clone());
profiles.insert(
"seeding".to_owned(),
Profile {
preparing: Some(Preparing::Reseeding),
..other
},
);
let plan = plan(&repositories, &profiles, memory_left(gib(4)), now());
assert_eq!(
plan.waiting[&2],
Waiting::NoSlot {
profile: "full".to_owned()
}
);
assert_eq!(
plan.waiting[&3],
Waiting::Reseeding {
profile: "seeding".to_owned()
}
);
assert_eq!(plan.slot_waiting, BTreeSet::new());
}
#[test]
fn a_job_behind_a_barrier_is_no_slot_wait() {
let plan = plan(
&a_big_job_and_a_small_one(starved_of_memory(1)),
&profiles(vec![Slot::Free, Slot::Free]),
memory_left(gib(4)),
now(),
);
assert_eq!(plan.slot_waiting, BTreeSet::new());
}
#[test]
fn no_warm_runner_starts_while_a_barrier_stands() {
let repositories = [
pool("o/big", 8 * GIB, starved_of_memory(1), &[1]),
Repository {
warm: 1,
..pool("o/warm", GIB, Waits::default(), &[])
},
];
let plan = plan(
&repositories,
&profiles(vec![Slot::Free, Slot::Free]),
memory_left(gib(5)),
now(),
);
assert_eq!(starts(&plan.decisions), []);
}
fn warm_runner(repository: &str, memory: u64) -> Slot {
Slot::Runner(RunnerSlot {
repository: repository.to_owned(),
busy: false,
started_at: now(),
memory,
cpu: 500,
usual: None,
caps: Caps { memory, cpu: 500 },
behind: None,
})
}
#[test]
fn warm_runners_stop_only_for_the_owners_whole_start() {
let warm = |waiting: &[u64], free: i64| {
let repositories = [
pool("o/big", 8 * GIB, starved_of_memory(1), &[1]),
Repository {
warm: 1,
..pool("o/warm", GIB, Waits::default(), waiting)
},
];
plan(
&repositories,
&profiles(vec![Slot::Free, warm_runner("o/warm", GIB), Slot::Free]),
memory_left(free),
now(),
)
};
let short = warm(&[], gib(4));
assert_eq!(short.barrier.map(|barrier| barrier.job), Some(1));
assert!(
!short
.decisions
.iter()
.any(|decision| matches!(decision, Decision::Stop { .. })),
"{:?}",
short.decisions
);
let enough = warm(&[], gib(7));
assert_eq!(enough.barrier, None);
assert_eq!(starts(&enough.decisions), [(0, "o/big")]);
assert!(
enough.decisions.contains(&Decision::Stop {
slot: SlotRef {
profile: "app".to_owned(),
index: 1
},
reason: StopReason::Room
}),
"{:?}",
enough.decisions
);
}
#[test]
fn a_job_no_pool_serves_erects_no_barrier() {
let plan = plan(
&[pool("o/big", 8 * GIB, starved_of_memory(1), &[])],
&profiles(vec![Slot::Free]),
memory_left(gib(4)),
now(),
);
assert_eq!(plan, Plan::default());
let unserved = [Repository {
queued: vec![job(1, &["gpu"])],
..pool("o/big", 8 * GIB, starved_of_memory(1), &[])
}];
let plan = super::plan(
&unserved,
&profiles(vec![Slot::Free]),
memory_left(gib(4)),
now(),
);
assert_eq!(plan.barrier, None);
assert!(
matches!(plan.waiting[&1], Waiting::NoPool { .. }),
"{:?}",
plan.waiting
);
}
mod generated {
use super::*;
const TICK: Duration = Duration::from_secs(30);
const LONGEST: u64 = 12;
const BUDGET: u64 = 16 * GIB;
const POOLS: [&str; 3] = ["o/big", "o/mid", "o/small"];
struct Rng(u64);
impl Rng {
fn next(&mut self) -> u64 {
self.0 = self.0.wrapping_add(0x9E37_79B9_7F4A_7C15);
let mut z = self.0;
z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
z ^ (z >> 31)
}
fn below(&mut self, n: u64) -> u64 {
self.next() % n
}
}
struct Running {
memory: u64,
ends: u64,
}
struct Model {
tick: u64,
next_job: u64,
queued: [Vec<u64>; 3],
waits: [Waits; 3],
memory: [u64; 3],
removed: [bool; 3],
running: Vec<Running>,
warm: Vec<u64>,
warm_wanted: usize,
host: Option<u64>,
}
impl Model {
fn new() -> Model {
Model {
tick: 0,
next_job: 1,
queued: [Vec::new(), Vec::new(), Vec::new()],
waits: [Waits::default(); 3],
memory: [12 * GIB, 6 * GIB, GIB],
removed: [false; 3],
running: Vec::new(),
warm: Vec::new(),
warm_wanted: 0,
host: None,
}
}
fn in_use(&self) -> u64 {
let running: u64 = self.running.iter().map(|running| running.memory).sum();
running + self.warm.iter().sum::<u64>()
}
fn at(&self) -> SystemTime {
now() + TICK * u32::try_from(self.tick).unwrap()
}
fn queue(&mut self, pool: usize) {
self.queued[pool].push(self.next_job);
self.next_job += 1;
}
fn plan(&mut self, unlisted: Option<usize>, rng: &mut Rng) -> Plan {
let at = self.at();
let in_use = self.in_use();
let repositories: Vec<Repository> = (0..POOLS.len())
.filter(|pool| !self.removed[*pool])
.map(|pool| {
let queued = if unlisted == Some(pool) {
&[][..]
} else {
&self.queued[pool][..]
};
super::pool(POOLS[pool], self.memory[pool], self.waits[pool], queued)
})
.chain((self.warm_wanted > 0).then(|| warm("o/warm", "app", self.warm_wanted)))
.collect();
let mut slots: Vec<Slot> = self
.warm
.iter()
.map(|&memory| {
let caps = Caps { memory, cpu: 0 };
Slot::Runner(RunnerSlot {
repository: "o/warm".to_owned(),
busy: false,
started_at: at,
memory,
cpu: 0,
usual: None,
caps,
behind: None,
})
})
.collect();
let all = 8usize.saturating_sub(self.running.len()).max(slots.len());
slots.resize(all, Slot::Free);
let budget = Budget {
memory: Some(crate::scheduler::left(BUDGET, in_use)),
host: self.host.map(|host| crate::scheduler::left(host, in_use)),
drained: Drained {
memory: Some(crate::scheduler::left(BUDGET, 0)),
host: self.host.map(|host| crate::scheduler::left(host, 0)),
..Drained::default()
},
..Budget::default()
};
let plan = plan(&repositories, &profiles(slots), budget, at);
let mut stopped: Vec<usize> = plan
.decisions
.iter()
.filter_map(|decision| match decision {
Decision::Stop { slot, .. } => Some(slot.index),
Decision::Start { .. } => None,
})
.collect();
stopped.sort_unstable();
for index in stopped.into_iter().rev() {
self.warm.remove(index);
}
for decision in &plan.decisions {
if let Decision::Start {
for_: StartFor::Warm,
memory,
..
} = decision
{
self.warm.push(*memory);
} else if let Decision::Start {
repository, memory, ..
} = decision
{
let pool = POOLS.iter().position(|name| name == repository).unwrap();
let taken = usize::try_from(rng.below(self.queued[pool].len() as u64));
self.queued[pool].remove(taken.unwrap());
self.waits[pool].started();
let ends = self.tick + 1 + rng.below(LONGEST);
self.running.push(Running {
memory: *memory,
ends,
});
}
}
for demand in &plan.held {
let pool = POOLS
.iter()
.position(|name| *name == demand.pool.repository)
.unwrap();
self.waits[pool].note(demand.scarce, demand.job, at);
}
for pool in 0..POOLS.len() {
if unlisted != Some(pool) {
let queued = &self.queued[pool];
self.waits[pool].retain(|job| queued.contains(&job));
if queued.is_empty() {
self.waits[pool].emptied();
}
}
if let Some(barrier) = plan.barrier {
self.waits[pool].own(barrier.job);
}
}
plan
}
fn elapse(&mut self) {
self.tick += 1;
let tick = self.tick;
self.running.retain(|running| running.ends > tick);
}
}
fn holds(model: &Model, plan: &Plan, in_use_before: u64) {
let behind: BTreeSet<u64> = plan
.waiting
.values()
.filter_map(|reason| match reason {
Waiting::BehindMemory { job } | Waiting::BehindCpu { job } => Some(*job),
_ => None,
})
.collect();
assert!(behind.len() <= 1, "never two barriers: {:?}", plan.waiting);
assert!(
behind
.iter()
.all(|job| plan.barrier.map(|barrier| barrier.job) == Some(*job)),
"only the plan's barrier holds a job back: {plan:?}"
);
let started: u64 = plan
.decisions
.iter()
.filter_map(|decision| match decision {
Decision::Start { memory, .. } => Some(*memory),
Decision::Stop { .. } => None,
})
.sum();
assert!(
in_use_before + started <= BUDGET,
"starts fit the budget: {plan:?}"
);
if let Some(barrier) = plan.barrier {
assert!(
model.memory.iter().any(|memory| *memory <= BUDGET),
"a barrier stands only for what an empty slice holds"
);
assert!(
!plan.waiting.contains_key(&barrier.job)
|| !matches!(
plan.waiting[&barrier.job],
Waiting::BehindMemory { .. } | Waiting::BehindCpu { .. }
),
"its owner keeps its own reason: {plan:?}"
);
}
}
#[test]
fn the_barrier_never_stalls_the_queue_over_generated_sequences() {
for seed in 0..256 {
let mut rng = Rng(seed);
let mut model = Model::new();
for _ in 0..200 {
match rng.below(10) {
0..=3 => model.queue(usize::try_from(rng.below(3)).unwrap()),
4 => model.waits = [Waits::default(); 3],
5 => {
let pool = usize::try_from(rng.below(3)).unwrap();
model.memory[pool] = (1 + rng.below(20)) * GIB;
}
6 => {
let pool = usize::try_from(rng.below(3)).unwrap();
model.removed[pool] = !model.removed[pool];
model.waits[pool] = Waits::default();
}
_ => {}
}
let unlisted = (rng.below(5) == 0).then(|| usize::try_from(rng.below(3)).unwrap());
let in_use = model.in_use();
let plan = model.plan(unlisted, &mut rng);
holds(&model, &plan, in_use);
let started = !starts(&plan.decisions).is_empty();
let fits = (0..POOLS.len()).any(|pool| {
!model.removed[pool]
&& unlisted != Some(pool)
&& !model.queued[pool].is_empty()
&& in_use + model.memory[pool] <= BUDGET
});
assert!(
started || !fits || plan.barrier.is_some() || model.running.len() >= 8,
"seed {seed}: a job's runner fits, no hold is owed, and nothing started: {plan:?}"
);
model.elapse();
}
}
}
#[test]
fn a_standing_barrier_ends_within_one_longest_run_of_the_last_start() {
let (mut stood, mut for_served) = (0, 0);
for seed in 0..256 {
let mut rng = Rng(seed);
let mut model = Model::new();
model.warm_wanted = usize::try_from(rng.below(3)).unwrap();
model.host = [None, Some(9 * GIB), Some(11 * GIB), Some(14 * GIB)]
[usize::try_from(rng.below(4)).unwrap()];
let mut standing: Option<(u64, u64)> = None;
for _ in 0..200 {
for _ in 0..rng.below(3) {
model.queue(usize::try_from(rng.below(3)).unwrap());
}
let plan = model.plan(None, &mut rng);
let limit = model.host.unwrap_or(BUDGET).min(BUDGET);
assert!(
model.in_use() <= limit,
"seed {seed}: starts fit the budgets: {plan:?}"
);
let started = !starts(&plan.decisions).is_empty();
standing = plan.barrier.map(|barrier| match standing {
Some((job, last)) if job == barrier.job && !started => (job, last),
_ => (barrier.job, model.tick),
});
if let Some((job, last)) = standing {
stood += 1;
for_served += u32::from(model.waits.iter().any(Waits::served));
assert!(
model.tick <= last + LONGEST + 1,
"seed {seed}: job {job} still holds at tick {} with no start since {last}: {plan:?}",
model.tick
);
}
model.elapse();
}
}
assert!(stood > 0, "generated runs reach a barrier");
assert!(for_served > 0, "and one beside a pool a barrier served");
}
#[test]
fn a_starved_pool_starts_within_a_bound_under_a_stream_of_younger_jobs() {
let limit = PRIORITY_AFTER.as_secs() / TICK.as_secs();
for seed in 0..256 {
let mut rng = Rng(seed);
let mut model = Model::new();
model.queue(2);
model.queue(2);
for _ in 0..6 {
model.queue(2);
}
let plan = model.plan(None, &mut rng);
assert_eq!(starts(&plan.decisions).len(), 8);
model.queue(0);
let big = model.next_job - 1;
let began = model.tick;
let started = loop {
model.queue(2);
model.queue(2);
let plan = model.plan(None, &mut rng);
if !model.queued[0].contains(&big) {
break model.tick;
}
if plan.barrier.is_some() {
assert_eq!(
starts(&plan.decisions),
[],
"seed {seed}: nothing younger starts past the barrier"
);
}
assert!(
model.tick <= began + limit + LONGEST + 2,
"seed {seed}: the starved pool has not started by tick {}",
model.tick
);
model.elapse();
};
assert!(started <= began + limit + LONGEST + 2);
}
}
}
#[test]
fn a_start_or_a_listing_between_two_plans_leaves_what_the_last_plan_said_of_cpu() {
let mut waits = Waits::default();
waits.note(Scarce::Cpu, 1, now());
waits.set_cpu_held(true);
waits.started();
assert_eq!(waits.cpu(), None, "the start ended its wait");
assert!(waits.cpu_held(), "a start is not the next plan");
waits.note(Scarce::Cpu, 2, now());
waits.retain(|_| false);
assert_eq!(waits.cpu(), None, "the job left the queue");
assert!(waits.cpu_held(), "a listing is not the next plan");
assert!(
!waits.is_empty(),
"the pool is kept while the last plan's word stands"
);
waits.set_cpu_held(false);
assert!(waits.is_empty(), "the next plan held nothing for CPU");
}
#[test]
fn only_the_first_start_for_a_barriers_owner_serves_the_pool() {
let mut waits = Waits::default();
waits.note(Scarce::Memory, 1, now());
assert!(!waits.started(), "no barrier was its own");
waits.note(Scarce::Memory, 2, now());
waits.own(2);
assert!(waits.started(), "job 2 owned the barrier");
assert!(waits.served(), "the pool was served");
waits.note(Scarce::Memory, 3, now());
waits.own(3);
assert!(!waits.started(), "it was served already");
}