#[cfg(test)]
use std::sync::mpsc;
use std::sync::{Arc, Mutex};
#[cfg(test)]
use std::thread::ThreadId;
use super::{DepCache, Hook, HookFn, LRU_SHARE, Lru, LruNode, lock, lru_key};
use crate::budget::Reservation;
use crate::env::registry::{Dependency, Open, open_bare};
use crate::env::{EnvOptions, Environment, Source};
use crate::files::File;
use crate::limits::Meter;
use crate::options::FileContext;
use crate::raw::RawStr;
use bytes::Bytes;
use unityrs_testkit::env::{Obj, bundle, res_bytes, serialized};
use unityrs_testkit::guard;
use unityrs_testkit::rng::Rng;
fn bundle_with(cab: &str, pad: usize) -> Vec<u8> {
let named = serialized(&[], &[Obj::named(1, cab, &[])]);
if pad == 0 {
return bundle(&[(cab, named)]);
}
bundle(&[(cab, named), (&format!("{cab}.resS"), res_bytes(pad, 1))])
}
fn source(cab: &str, pad: usize) -> Source {
Source::Bytes {
name: RawStr::from(format!("{cab}.bundle").as_str()),
data: Bytes::from(bundle_with(cab, pad)),
}
}
impl DepCache {
pub(crate) fn check(&self) {
lock(&self.lru).check();
}
pub(crate) fn total(&self) -> u64 {
lock(&self.lru).total
}
pub(crate) fn len(&self) -> usize {
lock(&self.lru).nodes.len()
}
}
struct Rig {
cache: Arc<DepCache>,
deps: Vec<(Arc<Dependency>, File)>,
}
impl Rig {
fn new(n: usize) -> Self {
let ctx = Arc::new(FileContext::unitypy());
let open = |i: usize| {
let src = source(&format!("CAB-{i}"), 64);
let name = RawStr::from(format!("d{i}").as_str());
let meter = Meter::for_input(&ctx.limits, ctx.budget.clone(), Reservation::Dependency);
let file = open_bare(&name, &src, &meter, &ctx).unwrap();
(name, src, meter, file)
};
let (_, _, meter, file) = open(0);
let one = meter.used() + LRU_SHARE;
drop(file);
let cache = Arc::new(DepCache::new(one * 5 / 2, true));
let deps = (0..n)
.map(|i| {
let (name, source, meter, file) = open(i);
let dep = Arc::new(Dependency {
name,
source,
open: Mutex::new(Open::of(&file, meter)),
ctx: ctx.clone(),
cache: Arc::downgrade(&cache),
slots: std::sync::atomic::AtomicUsize::new(0),
#[cfg(feature = "test-counters")]
load_id: crate::counters::LoadId::BARE,
});
(dep, file)
})
.collect();
Self { cache, deps }
}
fn apply(&self, op: Op) {
let dep = |i: usize| &self.deps[i].0;
match op {
Op::Touch(i) => self.cache.touch(dep(i), &self.deps[i].1).unwrap(),
Op::Refresh(i) => self.cache.refresh(dep(i)),
Op::EvictOthers(keep) => self.cache.evict_others(keep.map(dep)),
Op::Forget(i) => self.cache.forget(dep(i)),
Op::Bytes => {
self.cache.bytes();
}
}
}
fn settle(&self) {
let cache = &self.cache;
cache.check();
assert_eq!(cache.bytes(), cache.total(), "the sum is the meters'");
let last = self.deps.len() - 1;
self.apply(Op::Touch(last));
assert!(
cache.total() <= cache.bound || cache.len() == 1,
"one use evicts to the bound: {} > {} over {}",
cache.total(),
cache.bound,
cache.len()
);
assert_eq!(cache.bytes(), cache.total());
}
}
#[derive(Clone, Copy, Debug)]
enum Op {
Touch(usize),
Refresh(usize),
EvictOthers(Option<usize>),
Forget(usize),
Bytes,
}
#[derive(Debug, PartialEq, Eq)]
enum Event {
Stopped,
Done,
}
#[cfg(test)]
struct Gate {
at: Hook,
nth: usize,
armed: Mutex<Option<(ThreadId, usize)>>,
events: Mutex<mpsc::Sender<Event>>,
go: Mutex<mpsc::Receiver<()>>,
}
#[cfg(test)]
struct Held {
gate: Arc<Gate>,
events: mpsc::Receiver<Event>,
go: mpsc::Sender<()>,
}
#[cfg(test)]
impl Held {
fn install(cache: &DepCache, at: Hook, nth: usize) -> Self {
let (events_tx, events) = mpsc::channel();
let (go, go_rx) = mpsc::channel();
let gate = Arc::new(Gate {
at,
nth,
armed: Mutex::new(None),
events: Mutex::new(events_tx),
go: Mutex::new(go_rx),
});
let g = gate.clone();
*lock(&cache.hook) = Some(HookFn(Arc::new(move |h| g.reach(h))));
Self { gate, events, go }
}
fn run(&self, f: impl FnOnce() + Send + 'static) -> std::thread::JoinHandle<()> {
let gate = self.gate.clone();
std::thread::spawn(move || {
*lock(&gate.armed) = Some((std::thread::current().id(), 0));
f();
let _ = lock(&gate.events).send(Event::Done);
})
}
fn next(&self) -> Event {
guard::recv(&self.events, "the armed thread to stop or finish")
}
fn release(&self) {
self.go.send(()).unwrap();
}
}
#[cfg(test)]
impl Gate {
fn reach(&self, h: Hook) {
if h != self.at {
return;
}
let me = std::thread::current().id();
let stop = {
let mut armed = lock(&self.armed);
match armed.as_mut() {
Some((t, seen)) if *t == me => {
*seen += 1;
let stop = *seen == self.nth;
if stop {
*armed = None;
}
stop
}
_ => false,
}
};
if stop {
let _ = lock(&self.events).send(Event::Stopped);
guard::hold(&lock(&self.go), "the test to let the stopped thread go");
}
}
}
#[cfg(test)]
#[test]
fn every_operation_stopped_between_its_steps_while_another_runs_keeps_the_lru_one() {
let stopped_ops = [
Op::Touch(2),
Op::Touch(0),
Op::Refresh(1),
Op::EvictOthers(None),
Op::EvictOthers(Some(0)),
Op::Forget(1),
];
let points = [
(Hook::Touching, 1),
(Hook::Used, 1),
(Hook::Evicting, 1),
(Hook::Evicting, 2),
(Hook::Evicting, 3),
];
let others = [
Op::Touch(3),
Op::Touch(0),
Op::Touch(1),
Op::Touch(2),
Op::Refresh(0),
Op::Refresh(1),
Op::EvictOthers(None),
Op::EvictOthers(Some(1)),
Op::EvictOthers(Some(2)),
Op::Forget(0),
Op::Forget(1),
Op::Forget(2),
Op::Bytes,
];
let mut stopped = 0;
for p in stopped_ops {
for (at, nth) in points {
for q in others {
let rig = Arc::new(Rig::new(5));
rig.apply(Op::Touch(0));
rig.apply(Op::Touch(1));
assert_eq!(rig.cache.len(), 2, "two fit the bound");
let held = Held::install(&rig.cache, at, nth);
let thread = {
let rig = rig.clone();
held.run(move || rig.apply(p))
};
if held.next() == Event::Stopped {
stopped += 1;
rig.apply(q);
rig.cache.check();
held.release();
assert_eq!(held.next(), Event::Done, "{p:?} at {at:?} {nth}, {q:?}");
}
thread.join().unwrap();
*lock(&rig.cache.hook) = None;
rig.settle();
}
}
}
assert_eq!(stopped, (4 + 3 + 2 + 3 + 2) * others.len());
}
#[cfg(test)]
#[test]
fn a_use_stopped_while_its_key_is_evicted_lists_no_key_without_an_entry() {
let env_of = |bound: u64| {
let mut o = EnvOptions::batch(Arc::new(FileContext::unitypy()));
o.dep_cache_bytes = bound;
Environment::new(o)
};
let bound = {
let env = env_of(u64::MAX);
let mut held = Vec::new();
for cab in ["CAB-A", "CAB-B", "CAB-C"] {
env.load_dependency(source(cab, 64)).unwrap();
held.push(env.stats().dependency_bytes);
}
u64::midpoint(held[1], held[2])
};
let env = env_of(bound);
env.load_dependency(source("CAB-A", 64)).unwrap();
env.load_dependency(source("CAB-B", 64)).unwrap();
let held = Held::install(&env.inner.cache, Hook::Touching, 1);
let thread = {
let env = env.clone();
held.run(move || {
let m = Meter::unlimited();
assert!(env.get_cab(&RawStr::from("cab-a"), &m).unwrap().is_some());
})
};
assert_eq!(held.next(), Event::Stopped);
env.load_dependency(source("CAB-C", 64)).unwrap();
assert_eq!(env.stats().dependencies_evicted, 1, "C's load evicted A");
held.release();
assert_eq!(held.next(), Event::Done);
thread.join().unwrap();
env.inner.cache.check();
env.load_dependency(source("CAB-D", 64 * 1024)).unwrap();
let (tx, rx) = mpsc::channel();
let get = {
let env = env.clone();
std::thread::spawn(move || {
let m = Meter::unlimited();
let found = env.get_cab(&RawStr::from("cab-b"), &m).unwrap().is_some();
let _ = tx.send(found);
})
};
let found = guard::recv(&rx, "a get of B to return (round 3's eviction spun here)");
assert!(found);
get.join().unwrap();
env.inner.cache.check();
let cache = &env.inner.cache;
assert!(cache.total() <= bound || cache.len() == 1);
assert_eq!(env.stats().dependency_bytes, cache.total());
}
#[cfg(test)]
#[test]
fn an_eviction_ends_on_a_corrupt_state() {
let rig = Rig::new(3);
let node = |i: usize, prev: Option<usize>, next: Option<usize>| {
let (dep, file) = &rig.deps[i];
LruNode {
_dep: dep.clone(),
file: file.clone(),
seen: rig.cache.bound,
prev,
next,
_charge: file.meter().charge(0).unwrap(),
}
};
let k = |i: usize| lru_key(&rig.deps[i].0);
let ghost = usize::MAX;
let corrupt = [
(ghost, vec![(0, None, Some(1)), (1, Some(0), None)]),
(
0,
vec![
(0, Some(1), Some(1)),
(1, Some(0), Some(0)),
(2, None, None),
],
),
];
for (head, nodes) in corrupt {
let mut lru = Lru {
unchecked: true,
..Lru::default()
};
for (i, prev, next) in nodes {
let n = node(i, prev.map(k), next.map(k));
lru.total += n.seen;
lru.nodes.insert(k(i), n);
}
lru.head = Some(if head == ghost { ghost } else { k(head) });
lru.tail = Some(ghost);
let cache = rig.cache.clone();
*lock(&cache.lru) = lru;
let (tx, rx) = mpsc::channel();
let evict = std::thread::spawn(move || {
cache.evict_over(0);
cache.evict_others(None);
let _ = tx.send(());
});
guard::wait(&rx, "an eviction to end (round 3's eviction spun here)");
evict.join().unwrap();
*lock(&rig.cache.lru) = Lru::default();
}
}
#[cfg(test)]
#[test]
fn random_operations_on_many_threads_keep_the_lru_one() {
const THREADS: u64 = 4;
const OPS: usize = 4_000;
let rig = Arc::new(Rig::new(6));
let (tx, rx) = mpsc::channel();
let threads: Vec<_> = (0..THREADS)
.map(|t| {
let (rig, tx) = (rig.clone(), tx.clone());
std::thread::spawn(move || {
let mut rng = Rng::new(0x5eed_0000 + t);
for _ in 0..OPS {
let i = rng.below(5);
let op = match rng.below(10) {
0..=4 => Op::Touch(i),
5 => Op::Refresh(i),
6 => Op::EvictOthers((rng.below(2) == 0).then_some(i)),
7 | 8 => Op::Forget(i),
_ => Op::Bytes,
};
rig.apply(op);
rig.cache.check();
}
let _ = tx.send(());
})
})
.collect();
drop(tx);
for _ in 0..THREADS {
guard::hold(
&rx,
"every thread to finish (an eviction that spins never does)",
);
}
for t in threads {
t.join().unwrap();
}
rig.settle();
}
#[test]
fn the_lru_visits_a_constant_number_of_entries_per_use() {
let visits = |n: usize| {
let env = Environment::new(EnvOptions::batch(Arc::new(FileContext::unitypy())));
for i in 0..n {
env.load_dependency(source(&format!("CAB-{i}"), 0)).unwrap();
}
let cache: &DepCache = &env.inner.cache;
let before = lock(&cache.lru).visits;
for i in 0..n {
let name = RawStr::from(format!("cab-{i}").as_str());
assert!(env.get_cab(&name, &Meter::unlimited()).unwrap().is_some());
}
lock(&cache.lru).visits - before
};
let (small, large) = (visits(200), visits(800));
assert!(
large <= 2 * 800 && small <= 2 * 200,
"visits: {small} for 200 lookups over 200 dependencies, {large} for 800 over 800"
);
}
#[cfg(test)]
#[test]
fn a_paid_touch_that_finds_its_entry_cached_reads_it_without_the_share() {
let pool = Arc::new(crate::budget::Counting::new(u64::MAX));
let mut ctx = FileContext::unitypy();
ctx.budget = pool.clone();
let mut options = EnvOptions::unitypy();
options.context = Arc::new(ctx);
options.load = crate::env::LoadMode::Lazy;
let env = Environment::new(options);
let held = Held::install(&env.inner.cache, Hook::LoadRegistered, 1);
let load = {
let env = env.clone();
held.run(move || {
env.load_dependency(source("CAB-A", 64)).unwrap();
})
};
assert_eq!(held.next(), Event::Stopped);
let m = Meter::unlimited();
assert!(env.get_cab(&RawStr::from("cab-a"), &m).unwrap().is_some());
assert_eq!(env.inner.cache.len(), 1, "the get cached the dependency");
held.release();
assert_eq!(held.next(), Event::Done);
load.join().unwrap();
let cache = &env.inner.cache;
cache.check();
assert_eq!(cache.len(), 1);
assert_eq!(cache.total(), env.stats().dependency_bytes);
drop(env);
assert_eq!(pool.used(), 0, "a charge was kept");
}