use std::collections::HashMap;
use std::collections::hash_map::Entry;
use std::convert::Infallible;
use std::mem::size_of;
use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::{Arc, Mutex};
use super::{Dependency, lock};
use crate::error::Error;
use crate::files::File;
use crate::limits::{Charge, HASH_TABLE_SHARES};
#[derive(Debug)]
pub(crate) struct DepCache {
bound: u64,
evicts: bool,
lru: Mutex<Lru>,
pub(crate) loaded: AtomicU64,
pub(crate) evicted: AtomicU64,
#[cfg(test)]
pub(crate) hook: Mutex<Option<HookFn>>,
}
#[cfg(test)]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Hook {
SlotReleased,
LoadRegistered,
LoadChecked,
Touching,
Used,
Evicting,
Published,
Deferred,
SettleTook,
Reached,
Listing,
Listed,
Watched,
Search {
row: usize,
index: usize,
},
Step {
row: usize,
index: usize,
},
}
#[cfg(test)]
#[derive(Clone)]
pub(crate) struct HookFn(pub(crate) Arc<dyn Fn(Hook) + Send + Sync>);
#[cfg(test)]
impl std::fmt::Debug for HookFn {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str("HookFn")
}
}
#[derive(Debug)]
struct LruNode {
_dep: Arc<Dependency>,
file: File,
seen: u64,
prev: Option<usize>,
next: Option<usize>,
_charge: Charge,
}
#[derive(Debug, Default)]
struct Lru {
nodes: HashMap<usize, LruNode>,
head: Option<usize>,
tail: Option<usize>,
total: u64,
#[cfg(test)]
visits: u64,
#[cfg(test)]
unchecked: bool,
}
const LRU_SHARE: u64 = HASH_TABLE_SHARES * (size_of::<usize>() + size_of::<LruNode>() + 1) as u64;
fn lru_key(dep: &Arc<Dependency>) -> usize {
Arc::as_ptr(dep).addr()
}
impl Lru {
#[cfg_attr(not(test), allow(clippy::unused_self))]
fn visit(&mut self) {
#[cfg(test)]
{
self.visits += 1;
}
}
fn unlink(&mut self, k: usize) {
let Some((prev, next)) = self.nodes.get(&k).map(|n| (n.prev, n.next)) else {
return;
};
match prev.and_then(|p| self.nodes.get_mut(&p)) {
Some(p) => p.next = next,
None => self.head = next,
}
match next.and_then(|n| self.nodes.get_mut(&n)) {
Some(n) => n.prev = prev,
None => self.tail = prev,
}
if let Some(n) = self.nodes.get_mut(&k) {
n.prev = None;
n.next = None;
}
}
fn link_back(&mut self, k: usize) {
let old = self.tail;
let Some(n) = self.nodes.get_mut(&k) else {
return;
};
n.prev = old;
n.next = None;
match old.and_then(|t| self.nodes.get_mut(&t)) {
Some(t) => t.next = Some(k),
None => self.head = Some(k),
}
self.tail = Some(k);
}
fn use_key<E, S: FnOnce() -> Result<Charge, E>>(
&mut self,
k: usize,
share: S,
node: impl FnOnce(Charge) -> LruNode,
) -> Result<Option<S>, E> {
self.visit();
let unused = match self.nodes.entry(k) {
Entry::Occupied(_) => Some(share),
Entry::Vacant(v) => {
v.insert(node(share()?));
None
}
};
if unused.is_some() {
self.unlink(k);
}
self.link_back(k);
Ok(unused)
}
fn remove(&mut self, k: usize) -> Option<LruNode> {
self.unlink(k);
let node = self.nodes.remove(&k)?;
self.total = self.total.saturating_sub(node.seen);
Some(node)
}
fn reread(&mut self, k: usize) {
if let Some(n) = self.nodes.get_mut(&k) {
let now = n.file.meter().used();
self.total = self.total.saturating_sub(n.seen).saturating_add(now);
n.seen = now;
}
}
fn take_over(&mut self, bound: u64, keep: usize) -> Option<LruNode> {
if self.total <= bound || self.nodes.len() <= 1 {
return None;
}
let h = self.head.filter(|&h| h != keep)?;
self.visit();
self.reread(h);
if self.total <= bound {
return None;
}
self.remove(h)
}
fn take_other(&mut self, keep: Option<usize>) -> Option<LruNode> {
let h = self.head?;
let k = if Some(h) == keep {
self.nodes.get(&h)?.next?
} else {
h
};
self.visit();
self.remove(k)
}
#[cfg(test)]
fn check(&self) {
if self.unchecked {
return;
}
let (mut at, mut prev, mut listed) = (self.head, None, 0_usize);
while let Some(k) = at {
let Some(n) = self.nodes.get(&k) else {
panic!("the list holds {k:#x}, which the map does not");
};
assert_eq!(n.prev, prev, "the back link of {k:#x}");
listed += 1;
assert!(listed <= self.nodes.len(), "a key listed twice");
prev = Some(k);
at = n.next;
}
assert_eq!(self.tail, prev, "the tail is the last key listed");
assert_eq!(
listed,
self.nodes.len(),
"every key the map holds is listed"
);
let sum = self.nodes.values().map(|n| n.seen).sum::<u64>();
assert_eq!(self.total, sum, "the total is the entries' sum");
}
}
impl DepCache {
pub(crate) fn new(bound: u64, evicts: bool) -> Self {
Self {
bound,
evicts,
lru: Mutex::new(Lru::default()),
loaded: AtomicU64::new(0),
evicted: AtomicU64::new(0),
#[cfg(test)]
hook: Mutex::new(None),
}
}
fn step<R>(&self, f: impl FnOnce(&mut Lru) -> R) -> R {
let mut lru = lock(&self.lru);
let r = f(&mut lru);
#[cfg(test)]
lru.check();
r
}
#[cfg(test)]
pub(crate) fn hook(&self, at: Hook) {
let hook = lock(&self.hook).clone();
if let Some(HookFn(f)) = hook {
f(at);
}
}
pub(crate) fn touch(&self, dep: &Arc<Dependency>, file: &File) -> Result<(), Error> {
let k = lru_key(dep);
#[cfg(test)]
self.hook(Hook::Touching);
self.step(|lru| {
let unused = lru.use_key(k, || Self::room(file), |c| Self::node(dep, file, c))?;
lru.reread(k);
Ok::<_, Error>(unused)
})?;
self.used(k);
Ok(())
}
pub(crate) fn room(file: &File) -> Result<Charge, Error> {
Ok(file.meter().charge(LRU_SHARE)?)
}
pub(crate) fn touch_paid(&self, dep: &Arc<Dependency>, file: &File, room: Charge) {
let k = lru_key(dep);
#[cfg(test)]
self.hook(Hook::Touching);
let Ok(unused) = self.step(|lru| {
let unused = lru.use_key::<Infallible, _>(k, || Ok(room), |c| Self::node(dep, file, c));
if matches!(unused, Ok(None)) {
lru.reread(k);
}
unused
});
if let Some(unused) = unused {
drop(unused);
self.step(|lru| {
if lru.nodes.contains_key(&k) {
lru.visit();
lru.reread(k);
}
});
}
self.used(k);
}
fn node(dep: &Arc<Dependency>, file: &File, charge: Charge) -> LruNode {
LruNode {
_dep: dep.clone(),
file: file.clone(),
seen: 0,
prev: None,
next: None,
_charge: charge,
}
}
fn used(&self, k: usize) {
#[cfg(test)]
self.hook(Hook::Used);
self.evict_over(k);
}
pub(crate) fn refresh(&self, dep: &Arc<Dependency>) {
let k = lru_key(dep);
let held = self.step(|lru| {
if !lru.nodes.contains_key(&k) {
return false;
}
lru.visit();
lru.reread(k);
true
});
if held {
#[cfg(test)]
self.hook(Hook::Used);
self.evict_over(k);
}
}
fn evict_over(&self, keep: usize) {
let mut left = None;
loop {
#[cfg(test)]
self.hook(Hook::Evicting);
let node = self.step(|lru| {
let n = left.get_or_insert(lru.nodes.len());
*n = n.checked_sub(1)?;
lru.take_over(self.bound, keep)
});
let Some(node) = node else {
return;
};
self.evicted(node);
}
}
pub(crate) fn evict_others(&self, keep: Option<&Arc<Dependency>>) {
if !self.evicts {
return;
}
let keep = keep.map(lru_key);
let mut left = None;
loop {
#[cfg(test)]
self.hook(Hook::Evicting);
let node = self.step(|lru| {
let n = left.get_or_insert(lru.nodes.len());
*n = n.checked_sub(1)?;
lru.take_other(keep)
});
let Some(node) = node else {
return;
};
self.evicted(node);
}
}
pub(crate) fn forget(&self, dep: &Arc<Dependency>) {
let gone = self.step(|lru| lru.remove(lru_key(dep)));
drop(gone);
}
fn evicted(&self, node: LruNode) {
self.evicted.fetch_add(1, Ordering::Relaxed);
drop(node);
}
pub(crate) fn bytes(&self) -> u64 {
self.step(|lru| {
lru.nodes
.values()
.map(|n| n.file.meter().used())
.fold(0, u64::saturating_add)
})
}
}
#[cfg(test)]
mod tests;