#[cfg(test)]
use std::sync::mpsc::{Receiver, Sender, channel};
#[cfg(test)]
use std::sync::{Arc, Mutex, RwLock, Weak};
use super::{
FILES, FIRED, FLAG, Flag, Point, REGISTRY, Table, Under, WATCH_SHARE, Walk, Watches, set_hook,
};
use crate::budget::{BudgetExceeded, MemoryBudget, Permit, PermitHome, Reservation};
use crate::env::heap::{self, Noted};
use crate::env::held;
use crate::limits::{HASH_TABLE_SHARES, Meter, heap_cost};
#[cfg(test)]
use unityrs_testkit::guard;
#[cfg(test)]
#[derive(Debug, Default)]
struct Lock(RwLock<Table>);
#[cfg(test)]
impl Under for Lock {
fn with_table(&self, f: &mut dyn FnMut(&mut Table)) {
f(&mut held::write(&self.0));
}
}
#[cfg(test)]
fn stopping_at<T>(at: Point, stopped: Sender<()>, go: Receiver<()>, run: impl FnOnce() -> T) -> T {
let armed = std::cell::Cell::new(true);
set_hook(Some(std::rc::Rc::new(move |p| {
if p == at && armed.replace(false) {
let _ = stopped.send(());
guard::hold(&go, "the test to let the stopped thread go");
}
})));
let out = run();
set_hook(None);
out
}
#[cfg(test)]
#[derive(Debug, Default)]
struct Rig {
watches: Watches,
locks: [Lock; 2],
}
#[cfg(test)]
impl Rig {
fn start(&self, meter: &Arc<Meter>) -> Walk<'_> {
let [registry, files] = &self.locks;
self.watches.start(meter, [registry, files])
}
fn publish(&self, at: usize, hash: u64) {
self.locks[at].with_table(&mut |t| t.notify(hash));
}
fn room(&self) -> (usize, Vec<(usize, usize)>) {
let mut entries = 0;
let mut lists = Vec::new();
for lock in &self.locks {
let (n, _, l) = held::read(&lock.0).room();
entries += n;
lists.extend(l);
}
(entries, lists)
}
fn maps(&self) -> Vec<(usize, usize)> {
self.locks
.iter()
.map(|lock| {
let (n, room, _) = held::read(&lock.0).room();
(n, room)
})
.collect()
}
}
fn map_bound(len: usize) -> usize {
3 * len + 8
}
#[cfg(test)]
#[derive(Debug)]
struct Spy(Arc<Home>);
#[cfg(test)]
#[derive(Debug, Default)]
struct Home {
rig: Mutex<Option<Arc<Rig>>>,
seen: Mutex<Vec<(usize, usize, usize, usize)>>,
}
#[cfg(test)]
impl MemoryBudget for Spy {
fn try_reserve(&self, bytes: u64, _what: Reservation) -> Result<Permit, BudgetExceeded> {
Ok(Permit::new(bytes, self.0.clone()))
}
}
#[cfg(test)]
impl PermitHome for Home {
fn release(&self, _bytes: u64) {
let rig = self.rig.lock().unwrap().clone();
if let Some(r) = rig {
let (entries, lists) = r.room();
let excess = lists
.iter()
.map(|&(len, cap)| cap.saturating_sub(2 * len))
.max()
.unwrap_or(0);
let map_excess = r
.maps()
.iter()
.map(|&(len, room)| room.saturating_sub(map_bound(len)))
.max()
.unwrap_or(0);
self.seen
.lock()
.unwrap()
.push((r.watches.walks(), entries, excess, map_excess));
}
}
}
#[cfg(test)]
fn spied() -> (Arc<Rig>, Arc<Home>, Arc<Meter>) {
let rig = Arc::new(Rig::default());
let home = Arc::new(Home::default());
*home.rig.lock().unwrap() = Some(rig.clone());
let meter = Meter::new(u64::MAX, Arc::new(Spy(home.clone())), Reservation::Input);
(rig, home, meter)
}
#[test]
fn a_finished_walk_leaves_no_room_in_a_shared_keys_list() {
let (rig, home, meter) = spied();
let mut b = rig.start(&meter);
let k = b.hash(b"k");
let kept = b.watch(&[(REGISTRY, k)]).unwrap();
{
let mut a: Walk<'_> = rig.start(&meter);
for _ in 0..10_000 {
drop(a.watch(&[(REGISTRY, k)]).unwrap());
}
assert!(a.charged() > 0);
home.seen.lock().unwrap().clear();
}
let (entries, lists) = rig.room();
assert_eq!(entries, 1);
let &[(len, cap)] = lists.as_slice() else {
panic!("{lists:?}");
};
assert_eq!(len, 1, "only b's watch is left");
assert!(
cap <= 2 * len + 4,
"k's list kept room for {cap} after a ended"
);
let seen = home.seen.lock().unwrap().clone();
assert_ne!(seen.len(), 0, "a's charge was released");
for (walks, _, excess, _) in seen {
assert_eq!(walks, 1, "a's charge was released while a still ran");
assert!(
excess <= 4,
"a's charge was released before k's list shrank"
);
}
drop(kept);
drop(b);
assert_eq!(rig.room(), (0, Vec::new()));
}
#[test]
fn a_walks_charge_outlives_its_entries() {
let (rig, home, meter) = spied();
{
let mut walk = rig.start(&meter);
let keys: Vec<u64> = (0..64_u32).map(|i| walk.hash(&i.to_le_bytes())).collect();
let flags: Vec<_> = keys
.iter()
.map(|k| walk.watch(&[(REGISTRY, *k), (FILES, *k)]).unwrap())
.collect();
drop(flags);
home.seen.lock().unwrap().clear();
}
let seen = home.seen.lock().unwrap().clone();
assert_ne!(seen.len(), 0);
assert!(
seen.iter()
.all(|&(walks, entries, _, _)| walks == 0 && entries == 0),
"released while its entries were in a table: {seen:?}"
);
}
#[test]
fn a_finished_walk_gives_back_the_maps_room() {
let (rig, home, meter) = spied();
let mut b = rig.start(&meter);
let k = b.hash(b"k");
let kept = b.watch(&[(REGISTRY, k), (FILES, k)]).unwrap();
{
let mut a = rig.start(&meter);
let keys: Vec<(usize, u64)> = (0..10_000_u32)
.flat_map(|i| {
let h = a.hash(&i.to_le_bytes());
[(REGISTRY, h), (FILES, h)]
})
.collect();
drop(a.watch(&keys).unwrap());
for (len, room) in rig.maps() {
assert!(len >= 10_000 && room >= len, "a grew {len} keys, {room}");
}
home.seen.lock().unwrap().clear();
}
for (len, room) in rig.maps() {
assert_eq!(len, 1, "only b's key is left");
assert!(
room <= map_bound(len),
"the map kept room for {room} after a ended"
);
}
let seen = home.seen.lock().unwrap().clone();
assert_ne!(seen.len(), 0, "a's charge was released");
for (walks, _, _, map_excess) in seen {
assert_eq!(walks, 1, "a's charge was released while a still ran");
assert_eq!(map_excess, 0, "a's charge was released before a map shrank");
}
drop(kept);
drop(b);
assert_eq!(rig.room(), (0, Vec::new()));
}
#[cfg(test)]
fn map_bytes(t: &mut Table) -> usize {
let lists: usize = t
.map
.values()
.map(|l| l.capacity() * size_of::<Weak<Flag>>())
.sum();
let before = heap::live();
drop(std::mem::take(&mut t.map));
let freed = before.wrapping_sub(heap::live());
freed
.checked_sub(lists)
.unwrap_or_else(|| panic!("the map freed {freed} bytes, less than its lists' {lists}"))
}
fn room_of(buckets: usize) -> usize {
if buckets < 8 {
buckets.saturating_sub(1)
} else {
buckets / 8 * 7
}
}
#[test]
fn a_finished_walks_map_holds_no_more_buckets_than_the_running_walks_pay_for() {
heap::count();
let bucket = size_of::<u64>() + size_of::<Vec<Weak<Flag>>>() + 1;
let paid = usize::try_from(HASH_TABLE_SHARES).unwrap();
let keys = |walk: &Walk<'_>, from: u32, n: u32| -> Vec<(usize, u64)> {
(from..from + n)
.flat_map(|i| {
let h = walk.hash(&i.to_le_bytes());
[(REGISTRY, h), (FILES, h)]
})
.collect()
};
let scenes = [
(2_500_u32, 11_500, 0_usize),
(4_000, 10_000, 10_000),
(6_000, 8_000, 0),
];
for (kept, grown, changed) in scenes {
let what = format!("b keeps {kept} keys, a grows {grown} and has {changed} changed");
let rig = Rig::default();
let unlimited = Meter::unlimited();
let mut b = rig.start(&unlimited);
let mine = keys(&b, 1_000_000, kept);
let kept_flag = b.watch(&mine).unwrap();
let (meter, noted) = Noted::meter();
let mut a = rig.start(&meter);
let grew = keys(&a, 0, grown);
drop(a.watch(&grew).unwrap());
for &(at, h) in grew.iter().take(2 * changed) {
rig.publish(at, h);
}
let one = keys(&a, 2_000_000, 1);
drop(a.watch(&one).unwrap());
let from = noted.releases();
drop(a);
heap::released_last(¬ed, from, heap::live(), &what);
for lock in &rig.locks {
let mut t = held::write(&lock.0);
let (len, room, _) = t.room();
assert_eq!(
len,
usize::try_from(kept).unwrap(),
"{what}: only b's keys are left"
);
let bytes = map_bytes(&mut t);
let buckets = bytes / bucket;
assert!(
bytes <= paid * len * bucket + 16,
"{what}: the map holds {buckets} buckets, {bytes} bytes, where b pays for {}",
paid * len
);
assert_eq!(
room,
room_of(buckets),
"{what}: the room it reports is not its {buckets} buckets'"
);
}
drop(kept_flag);
drop(b);
}
}
#[test]
fn a_walks_charge_is_released_after_the_last_block_it_paid_for() {
heap::count();
let (meter, noted) = Noted::meter();
let rig = Rig::default();
let mut walk = rig.start(&meter);
let keys: Vec<u64> = (0..64_u32).map(|i| walk.hash(&i.to_le_bytes())).collect();
let flags: Vec<_> = keys
.iter()
.map(|k| walk.watch(&[(REGISTRY, *k), (FILES, *k)]).unwrap())
.collect();
drop(flags);
let (before, from) = (heap::live(), noted.releases());
drop(walk);
let after = heap::live();
assert!(before > after, "the walk's drop freed nothing");
heap::released_last(¬ed, from, after, "the walk's charge");
}
#[test]
fn a_walks_log_lists_each_flag_once_within_its_charge() {
let (rig, _home, meter) = spied();
for n in [1_usize, 3, 5, 64, 1000] {
let mut walk = rig.start(&meter);
let keys: Vec<[u64; 2]> = (0..n)
.map(|i| {
let i = u64::try_from(i).unwrap();
[
walk.hash(&i.to_le_bytes()),
walk.hash(&((i + 1) << 32).to_le_bytes()),
]
})
.collect();
let flags: Vec<_> = keys
.iter()
.map(|k| walk.watch(&[(REGISTRY, k[0]), (FILES, k[1])]).unwrap())
.collect();
let charged = walk.charged();
let flags_n = u64::try_from(n).unwrap();
assert_eq!(charged, FIRED + flags_n * (FLAG + 2 * WATCH_SHARE), "{n}");
let arcs = heap_cost(size_of::<super::Fired>() as u64 + 16)
+ flags_n * heap_cost(size_of::<super::Flag>() as u64 + 16);
let list_share = FIRED + flags_n * FLAG - arcs;
let room = u64::try_from(walk.flags_room()).unwrap();
assert!(
heap_cost(room * 8) <= list_share,
"{n}: room {room} past {list_share}"
);
let mut seen = Vec::new();
for (i, k) in keys.iter().enumerate() {
let order = if i % 2 == 0 {
[(REGISTRY, k[0]), (FILES, k[1])]
} else {
[(FILES, k[1]), (REGISTRY, k[0])]
};
for (at, h) in order {
rig.publish(at, h);
}
if i == n / 2 {
seen.extend(walk.fired());
}
}
seen.extend(walk.fired());
seen.sort_unstable();
assert_eq!(seen, (0..n).collect::<Vec<_>>(), "{n}: each flag once");
assert!(flags.iter().all(|f| f.changed()), "{n}");
assert_eq!(walk.fired().count(), 0, "{n}: taken");
drop(flags);
}
}
#[cfg(test)]
#[test]
fn another_threads_change_logs_the_walks_flag() {
let (rig, _home, meter) = spied();
let mut walk = rig.start(&meter);
let k = walk.hash(b"k");
let other = walk.hash(b"other");
let flag = walk.watch(&[(REGISTRY, k)]).unwrap();
let untouched = walk.watch(&[(REGISTRY, other)]).unwrap();
std::thread::scope(|s| {
s.spawn(|| rig.publish(REGISTRY, k));
});
assert!(flag.changed());
rig.publish(REGISTRY, k);
assert_eq!(walk.fired().collect::<Vec<_>>(), [flag.id()]);
assert!(!untouched.changed());
assert_eq!(walk.fired().count(), 0);
}
#[cfg(test)]
#[test]
fn the_log_lists_each_flag_once_under_changes_from_many_threads() {
const N: usize = 4096;
let (rig, _home, meter) = spied();
let mut walk = rig.start(&meter);
let keys: Vec<u64> = (0..N)
.map(|i| walk.hash(&u64::try_from(i).unwrap().to_le_bytes()))
.collect();
let flags: Vec<_> = keys
.iter()
.map(|&k| walk.watch(&[(REGISTRY, k)]).unwrap())
.collect();
let mut seen = Vec::new();
std::thread::scope(|s| {
let rig = &rig;
let keys = &keys;
let threads: Vec<_> = (0..4)
.map(|t| {
s.spawn(move || {
for _ in 0..2 {
for k in keys.iter().skip(t).step_by(4) {
rig.publish(REGISTRY, *k);
}
}
})
})
.collect();
while !threads
.iter()
.all(std::thread::ScopedJoinHandle::is_finished)
{
seen.extend(walk.fired());
}
});
seen.extend(walk.fired());
seen.sort_unstable();
assert_eq!(seen, (0..N).collect::<Vec<_>>());
assert!(flags.iter().all(|f| f.changed()));
}
#[cfg(test)]
#[test]
fn a_walks_end_takes_out_its_entries_while_another_thread_holds_its_flag() {
let (rig, home, meter) = spied();
let mut walk = rig.start(&meter);
let (r, f) = (walk.hash(b"r"), walk.hash(b"f"));
drop(walk.watch(&[(REGISTRY, r), (FILES, f)]).unwrap());
home.seen.lock().unwrap().clear();
let rig = &*rig;
std::thread::scope(|s| {
let (notified, notify_stopped) = channel();
let (notify_go, go) = channel();
let notify = s.spawn(move || {
stopping_at(Point::Upgraded, notified, go, || rig.publish(FILES, f));
});
guard::wait(¬ify_stopped, "the notify to hold the walk's flag");
let (ended, end_stopped) = channel();
let (end_go, go) = channel();
let end = s.spawn(move || {
stopping_at(Point::Ended(REGISTRY), ended, go, || drop(walk));
});
guard::wait(&end_stopped, "the walk's end to leave the registry's table");
notify_go.send(()).unwrap();
notify.join().unwrap();
end_go.send(()).unwrap();
end.join().unwrap();
});
assert_eq!(rig.room(), (0, Vec::new()), "the walk left an entry");
let seen = home.seen.lock().unwrap().clone();
assert_ne!(seen.len(), 0, "the walk's charge was released");
assert!(
seen.iter()
.all(|&(walks, entries, _, _)| walks == 0 && entries == 0),
"released while its entries were in a table: {seen:?}"
);
}
#[cfg(test)]
#[test]
fn a_push_that_meets_another_push_tries_again() {
let (rig, _home, meter) = spied();
let mut walk = rig.start(&meter);
let (a, b) = (walk.hash(b"a"), walk.hash(b"b"));
let first = walk.watch(&[(REGISTRY, a)]).unwrap();
let second = walk.watch(&[(FILES, b)]).unwrap();
let rig = &*rig;
std::thread::scope(|s| {
let (read, stopped) = channel();
let (go, go_rx) = channel();
let push = s.spawn(move || {
stopping_at(Point::Pushing, read, go_rx, || rig.publish(REGISTRY, a));
});
guard::wait(&stopped, "the first push to read the log's head");
rig.publish(FILES, b);
go.send(()).unwrap();
push.join().unwrap();
});
assert_eq!(
walk.fired().collect::<Vec<_>>(),
[first.id(), second.id()],
"the log lost a flag"
);
}
#[cfg(test)]
#[test]
fn a_push_that_meets_a_take_tries_again() {
let (rig, _home, meter) = spied();
let mut walk = rig.start(&meter);
let (a, c) = (walk.hash(b"a"), walk.hash(b"c"));
let earlier = walk.watch(&[(REGISTRY, c)]).unwrap();
let pushed = walk.watch(&[(REGISTRY, a)]).unwrap();
rig.publish(REGISTRY, c);
let rig = &*rig;
let mut taken = Vec::new();
std::thread::scope(|s| {
let (read, stopped) = channel();
let (go, go_rx) = channel();
let push = s.spawn(move || {
stopping_at(Point::Pushing, read, go_rx, || rig.publish(REGISTRY, a));
});
guard::wait(&stopped, "the push to read the log's head");
taken.extend(walk.fired());
go.send(()).unwrap();
push.join().unwrap();
});
assert_eq!(taken, [earlier.id()]);
assert!(pushed.changed());
assert_eq!(
walk.fired().collect::<Vec<_>>(),
[pushed.id()],
"the log lost a flag"
);
}