use thiserror::Error;
use crate::format::MAX_EXPERTS;
pub const MAX_SLOTS: u32 = 1024;
pub const STUCK_PROTECTED_PLANS: u64 = 64;
#[derive(Debug, Clone, PartialEq, Eq, Error)]
pub enum CacheError {
#[error("layer cache needs at least one expert")]
NoExperts,
#[error("layer cache expert space {n_experts} is over the {limit} cap")]
ExpertSpaceTooLarge {
n_experts: u32,
limit: u32,
},
#[error("layer cache slot count {n_slots} is over the {limit} cap")]
TooManySlots {
n_slots: u32,
limit: u32,
},
#[error("expert {expert} out of range ({n_experts} experts)")]
ExpertOutOfRange {
expert: u32,
n_experts: u32,
},
#[error("{requested} experts requested in one step, layer has {n_slots} slots")]
TooFewSlots {
n_slots: u32,
requested: usize,
},
#[error(
"layer needs {needed} more slot(s) but only {free} of {n_slots} are free \
(the rest are filling or in use)"
)]
AllSlotsBusy {
n_slots: u32,
free: usize,
needed: usize,
},
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum SlotState {
Empty,
Filling,
Ready,
Idle,
}
#[derive(Debug, Clone, Copy)]
struct Slot {
expert: Option<u32>,
last_used: u64,
state: SlotState,
protected_at: u64,
}
impl Slot {
const EMPTY: Self = Self {
expert: None,
last_used: 0,
state: SlotState::Empty,
protected_at: 0,
};
}
#[derive(Debug, Clone, Default)]
pub struct CachePlan {
hits: Vec<(u32, u32)>,
misses: Vec<(u32, u32)>,
}
impl CachePlan {
pub fn new() -> Self {
Self::default()
}
pub fn with_capacity(top_k: usize) -> Self {
Self {
hits: Vec::with_capacity(top_k),
misses: Vec::with_capacity(top_k),
}
}
pub fn hits(&self) -> &[(u32, u32)] {
&self.hits
}
pub fn misses(&self) -> &[(u32, u32)] {
&self.misses
}
pub fn len(&self) -> usize {
self.hits.len() + self.misses.len()
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn clear(&mut self) {
self.hits.clear();
self.misses.clear();
}
pub fn capacity(&self) -> usize {
self.hits.capacity().min(self.misses.capacity())
}
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct CacheStats {
pub hits: u64,
pub pending_hits: u64,
pub misses: u64,
pub cold_misses: u64,
pub eviction_misses: u64,
pub evictions: u64,
}
impl CacheStats {
pub fn accesses(&self) -> u64 {
self.hits + self.pending_hits + self.misses
}
pub fn hit_rate(&self) -> f64 {
let accesses = self.accesses();
if accesses == 0 {
0.0
} else {
self.hits as f64 / accesses as f64
}
}
}
#[derive(Debug, Clone)]
pub struct LayerCache {
slots: Vec<Slot>,
freq: Vec<u32>,
fetched: Vec<bool>,
clock: u64,
plan_attempts: u64,
stats: CacheStats,
}
impl LayerCache {
pub fn new(n_slots: u32, n_experts: u32) -> Result<Self, CacheError> {
if n_experts == 0 {
return Err(CacheError::NoExperts);
}
if n_experts > MAX_EXPERTS {
return Err(CacheError::ExpertSpaceTooLarge {
n_experts,
limit: MAX_EXPERTS,
});
}
if n_slots > MAX_SLOTS {
return Err(CacheError::TooManySlots {
n_slots,
limit: MAX_SLOTS,
});
}
Ok(Self {
slots: vec![Slot::EMPTY; n_slots as usize],
freq: vec![0; n_experts as usize],
fetched: vec![false; n_experts as usize],
clock: 0,
plan_attempts: 0,
stats: CacheStats::default(),
})
}
pub fn n_slots(&self) -> u32 {
self.slots.len() as u32
}
pub fn n_experts(&self) -> u32 {
self.freq.len() as u32
}
pub fn stats(&self) -> CacheStats {
self.stats
}
pub fn is_ready(&self, slot: u32) -> bool {
self.slots
.get(slot as usize)
.is_some_and(|s| matches!(s.state, SlotState::Ready | SlotState::Idle))
}
pub fn resident(&self, slot: u32) -> Option<u32> {
self.slots.get(slot as usize).and_then(|s| s.expert)
}
pub fn plan(&mut self, experts: &[u32], out: &mut CachePlan) -> Result<(), CacheError> {
self.debug_assert_nothing_stuck_protected();
out.clear();
self.plan_attempts = self.plan_attempts.wrapping_add(1);
self.check(experts)?;
for (i, &expert) in experts.iter().enumerate() {
if experts[..i].contains(&expert) {
continue;
}
self.clock = self.clock.wrapping_add(1);
let counter = &mut self.freq[expert as usize];
*counter = counter.wrapping_add(1);
match self.find(expert) {
Some(slot) => {
let clock = self.clock;
let plan_attempts = self.plan_attempts;
let entry = &mut self.slots[slot];
entry.last_used = clock;
let still_filling = entry.state == SlotState::Filling;
if entry.state == SlotState::Idle {
entry.state = SlotState::Ready;
entry.protected_at = plan_attempts;
}
out.hits.push((expert, slot as u32));
if still_filling {
self.stats.pending_hits += 1;
} else {
self.stats.hits += 1;
}
}
None => {
let slot = self
.choose_victim(experts)
.ok_or(CacheError::AllSlotsBusy {
n_slots: self.n_slots(),
free: 0,
needed: 1,
})?;
let clock = self.clock;
let plan_attempts = self.plan_attempts;
let entry = &mut self.slots[slot];
if entry.expert.is_some() {
self.stats.evictions += 1;
}
*entry = Slot {
expert: Some(expert),
last_used: clock,
state: SlotState::Filling,
protected_at: plan_attempts,
};
out.misses.push((expert, slot as u32));
self.stats.misses += 1;
if self.fetched.get(expert as usize).copied().unwrap_or(false) {
self.stats.eviction_misses += 1;
} else {
self.stats.cold_misses += 1;
}
}
}
}
Ok(())
}
pub fn mark_ready(&mut self, slot: u32) {
let plan_attempts = self.plan_attempts;
let Some(entry) = self.slots.get_mut(slot as usize) else {
tracing::warn!(slot, "mark_ready for a slot outside the layer");
return;
};
let completed = match entry.state {
SlotState::Filling => {
entry.state = SlotState::Ready;
entry.protected_at = plan_attempts;
entry.expert
}
SlotState::Ready | SlotState::Idle => None,
SlotState::Empty => {
tracing::warn!(slot, "mark_ready for an unassigned slot");
None
}
};
if let Some(expert) = completed
&& let Some(fetched) = self.fetched.get_mut(expert as usize)
{
*fetched = true;
}
}
pub fn release(&mut self, slot: u32) {
let Some(entry) = self.slots.get_mut(slot as usize) else {
tracing::warn!(slot, "release for a slot outside the layer");
return;
};
match entry.state {
SlotState::Ready => entry.state = SlotState::Idle,
SlotState::Filling => {
tracing::warn!(
slot,
"release with a fill still in flight, keeping it protected"
);
}
SlotState::Idle | SlotState::Empty => {}
}
}
pub unsafe fn invalidate(&mut self, slot: u32) {
let Some(entry) = self.slots.get_mut(slot as usize) else {
tracing::warn!(slot, "invalidate for a slot outside the layer");
return;
};
*entry = Slot::EMPTY;
}
pub unsafe fn reset_occupancy(&mut self) {
self.slots.fill(Slot::EMPTY);
}
pub fn stuck_protected_slot(&self) -> Option<u32> {
self.slots
.iter()
.position(|slot| {
matches!(slot.state, SlotState::Filling | SlotState::Ready)
&& self.plan_attempts.wrapping_sub(slot.protected_at) > STUCK_PROTECTED_PLANS
})
.map(|slot| slot as u32)
}
fn debug_assert_nothing_stuck_protected(&self) {
debug_assert!(
self.stuck_protected_slot().is_none(),
"slot {:?} has been protected across more than {} plan attempts: a \
caller is releasing misses but not hits, or is not reaping its \
completions, and this layer will degrade to permanent AllSlotsBusy",
self.stuck_protected_slot(),
STUCK_PROTECTED_PLANS,
);
}
fn check(&self, experts: &[u32]) -> Result<(), CacheError> {
let n_experts = self.n_experts();
for &expert in experts {
if expert >= n_experts {
return Err(CacheError::ExpertOutOfRange { expert, n_experts });
}
}
let mut needed = 0usize;
let mut distinct = 0usize;
for (i, &expert) in experts.iter().enumerate() {
if experts[..i].contains(&expert) {
continue;
}
distinct += 1;
if self.find(expert).is_none() {
needed += 1;
}
}
if distinct > self.slots.len() {
return Err(CacheError::TooFewSlots {
n_slots: self.n_slots(),
requested: distinct,
});
}
let free = self
.slots
.iter()
.filter(|s| self.is_evictable(s, experts))
.count();
if needed > free {
return Err(CacheError::AllSlotsBusy {
n_slots: self.n_slots(),
free,
needed,
});
}
Ok(())
}
fn is_evictable(&self, slot: &Slot, requested: &[u32]) -> bool {
match slot.state {
SlotState::Empty => true,
SlotState::Idle => slot.expert.is_none_or(|e| !requested.contains(&e)),
SlotState::Filling | SlotState::Ready => false,
}
}
fn find(&self, expert: u32) -> Option<usize> {
self.slots.iter().position(|s| s.expert == Some(expert))
}
fn choose_victim(&self, requested: &[u32]) -> Option<usize> {
if let Some(empty) = self
.slots
.iter()
.position(|s| s.state == SlotState::Empty && s.expert.is_none())
{
return Some(empty);
}
self.slots
.iter()
.enumerate()
.filter(|(_, s)| self.is_evictable(s, requested))
.min_by_key(|(i, s)| {
let freq = s.expert.map_or(0, |e| self.freq[e as usize]);
(freq, s.last_used, *i)
})
.map(|(i, _)| i)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn new_cache(n_slots: u32, n_experts: u32) -> LayerCache {
LayerCache::new(n_slots, n_experts).expect("test geometry is in range")
}
fn step(cache: &mut LayerCache, experts: &[u32]) -> CachePlan {
let mut plan = CachePlan::with_capacity(experts.len());
cache.plan(experts, &mut plan).expect("step is satisfiable");
for &(_, slot) in plan.misses() {
cache.mark_ready(slot);
}
for &(_, slot) in plan.hits().iter().chain(plan.misses()) {
cache.release(slot);
}
plan
}
fn slot_of(plan: &CachePlan, expert: u32) -> u32 {
plan.hits()
.iter()
.chain(plan.misses())
.find(|(e, _)| *e == expert)
.map(|(_, s)| *s)
.expect("expert is in the plan")
}
fn holds(cache: &LayerCache, expert: u32) -> bool {
(0..cache.n_slots()).any(|slot| cache.resident(slot) == Some(expert))
}
#[test]
fn hit_returns_the_resident_slot_and_leaves_residency_alone() {
let mut cache = new_cache(4, 8);
let first = step(&mut cache, &[3]);
assert_eq!(first.misses(), [(3, 0)]);
assert!(first.hits().is_empty());
let second = step(&mut cache, &[3]);
assert_eq!(second.hits(), [(3, 0)]);
assert!(second.misses().is_empty());
assert_eq!(cache.resident(0), Some(3));
assert_eq!(cache.stats().evictions, 0);
for slot in 1..4 {
assert_eq!(cache.resident(slot), None);
}
}
#[test]
fn cold_misses_fill_empty_slots_before_evicting() {
let mut cache = new_cache(4, 8);
let plan = step(&mut cache, &[5, 1, 7]);
assert_eq!(plan.misses(), [(5, 0), (1, 1), (7, 2)]);
assert_eq!(cache.stats().evictions, 0);
assert_eq!(cache.stats().cold_misses, 3);
assert_eq!(cache.resident(3), None);
}
#[test]
fn eviction_picks_the_lowest_frequency() {
let mut cache = new_cache(3, 8);
for _ in 0..3 {
step(&mut cache, &[0]);
}
for _ in 0..2 {
step(&mut cache, &[1]);
}
step(&mut cache, &[2]);
let plan = step(&mut cache, &[4]);
assert_eq!(plan.misses(), [(4, 2)]);
assert_eq!(cache.resident(0), Some(0));
assert_eq!(cache.resident(1), Some(1));
assert_eq!(cache.stats().evictions, 1);
}
#[test]
fn frequency_ties_break_on_recency() {
let mut cache = new_cache(3, 8);
for expert in [0, 1, 2] {
step(&mut cache, &[expert]);
}
for expert in [0, 1, 2] {
step(&mut cache, &[expert]);
}
let plan = step(&mut cache, &[6]);
assert_eq!(plan.misses(), [(6, 0)], "least recently used loses the tie");
assert_eq!(cache.resident(1), Some(1));
assert_eq!(cache.resident(2), Some(2));
}
#[test]
fn ghost_history_changes_the_victim() {
let mut cache = new_cache(3, 8);
for _ in 0..5 {
step(&mut cache, &[0]);
}
for _ in 0..2 {
step(&mut cache, &[1]);
}
for _ in 0..2 {
step(&mut cache, &[2]);
}
let slot_1 = slot_of(&step(&mut cache, &[1]), 1);
let slot_2 = slot_of(&step(&mut cache, &[2]), 2);
let evicted = step(&mut cache, &[3]);
assert_eq!(evicted.misses(), [(3, slot_1)], "coldest and LRU loses");
let readmitted = step(&mut cache, &[1]);
assert_eq!(
readmitted.misses(),
[(1, slot_1)],
"expert 3 is now coldest"
);
let plan = step(&mut cache, &[4]);
assert_eq!(
plan.misses(),
[(4, slot_2)],
"expert 2 (count 3) is evicted, not the re-admitted expert 1 (count 4)"
);
assert_eq!(
cache.resident(slot_1),
Some(1),
"re-admitted expert survives"
);
}
#[test]
fn filling_and_in_use_slots_are_never_victims() {
let mut cache = new_cache(2, 8);
let mut plan = CachePlan::new();
cache
.plan(&[0, 1], &mut plan)
.expect("two slots, two experts");
assert_eq!(plan.misses(), [(0, 0), (1, 1)]);
let err = cache.plan(&[2], &mut plan).unwrap_err();
assert!(matches!(err, CacheError::AllSlotsBusy { free: 0, .. }));
cache.mark_ready(0);
cache.mark_ready(1);
let err = cache.plan(&[2], &mut plan).unwrap_err();
assert!(matches!(err, CacheError::AllSlotsBusy { free: 0, .. }));
cache.release(0);
cache.plan(&[2], &mut plan).expect("slot 0 is idle now");
assert_eq!(plan.misses(), [(2, 0)]);
assert_eq!(cache.resident(1), Some(1));
}
#[test]
fn a_slot_holding_an_expert_this_step_needs_is_not_a_victim() {
let mut cache = new_cache(2, 8);
for _ in 0..3 {
step(&mut cache, &[0]);
}
step(&mut cache, &[1]);
let plan = step(&mut cache, &[2, 1]);
assert_eq!(plan.hits(), [(1, 1)]);
assert_eq!(
plan.misses(),
[(2, 0)],
"the hot but unneeded expert 0 goes"
);
}
#[test]
fn release_of_a_filling_slot_keeps_it_protected() {
let mut cache = new_cache(1, 8);
let mut plan = CachePlan::new();
cache.plan(&[0], &mut plan).expect("empty cache");
cache.release(0);
assert!(!cache.is_ready(0));
let err = cache.plan(&[1], &mut plan).unwrap_err();
assert!(matches!(err, CacheError::AllSlotsBusy { .. }));
cache.mark_ready(0);
assert!(cache.is_ready(0));
cache.release(0);
cache.plan(&[1], &mut plan).expect("slot is idle");
assert_eq!(plan.misses(), [(1, 0)]);
}
#[test]
fn invalidate_frees_a_failed_fill() {
let mut cache = new_cache(1, 8);
let mut plan = CachePlan::new();
cache.plan(&[0], &mut plan).expect("empty cache");
unsafe { cache.invalidate(0) };
assert_eq!(cache.resident(0), None);
assert!(!cache.is_ready(0));
cache.plan(&[1], &mut plan).expect("slot is free again");
assert_eq!(plan.misses(), [(1, 0)]);
assert_eq!(
cache.stats().evictions,
0,
"an empty slot is not an eviction"
);
}
#[test]
fn too_few_slots_is_a_typed_error() {
let mut cache = new_cache(2, 8);
let mut plan = CachePlan::new();
let err = cache.plan(&[0, 1, 2], &mut plan).unwrap_err();
assert_eq!(
err,
CacheError::TooFewSlots {
n_slots: 2,
requested: 3
}
);
assert!(plan.is_empty());
assert_eq!(cache.stats(), CacheStats::default(), "nothing was touched");
}
#[test]
fn an_out_of_range_expert_is_a_typed_error() {
let mut cache = new_cache(4, 8);
let mut plan = CachePlan::new();
let err = cache.plan(&[1, 8], &mut plan).unwrap_err();
assert_eq!(
err,
CacheError::ExpertOutOfRange {
expert: 8,
n_experts: 8
}
);
assert!(plan.is_empty());
assert_eq!(
cache.resident(0),
None,
"the valid id was not admitted either"
);
}
#[test]
fn a_failed_step_changes_nothing() {
let mut cache = new_cache(2, 8);
let mut plan = CachePlan::new();
cache
.plan(&[0, 1], &mut plan)
.expect("two slots, two experts");
let before = cache.stats();
assert!(cache.plan(&[2], &mut plan).is_err());
assert!(plan.is_empty());
assert_eq!(cache.stats(), before);
assert_eq!(cache.resident(0), Some(0));
assert_eq!(cache.resident(1), Some(1));
}
#[test]
fn duplicate_ids_in_one_step_resolve_once() {
let mut cache = new_cache(4, 8);
let plan = step(&mut cache, &[2, 2, 5]);
assert_eq!(plan.misses(), [(2, 0), (5, 1)]);
assert_eq!(plan.len(), 2);
assert_eq!(cache.stats().misses, 2);
}
#[test]
fn stats_track_the_cold_and_eviction_split() {
let mut cache = new_cache(2, 8);
step(&mut cache, &[0, 1]); step(&mut cache, &[0, 1]); step(&mut cache, &[2]); step(&mut cache, &[0, 1]); step(&mut cache, &[2]);
let stats = cache.stats();
assert_eq!(stats.hits, 3);
assert_eq!(stats.misses, 5);
assert_eq!(stats.cold_misses, 3);
assert_eq!(stats.eviction_misses, 2);
assert_eq!(stats.accesses(), 8);
assert_eq!(stats.evictions, 3);
assert!((stats.hit_rate() - 0.375).abs() < 1e-12);
assert_eq!(CacheStats::default().hit_rate(), 0.0);
assert_eq!(stats.pending_hits, 0);
assert_eq!(stats.hits + stats.misses, stats.accesses());
}
#[test]
fn a_failed_fill_leaves_the_retry_a_cold_miss() {
let mut cache = new_cache(1, 8);
let mut plan = CachePlan::new();
cache.plan(&[5], &mut plan).expect("empty cache");
assert_eq!(cache.stats().cold_misses, 1);
unsafe { cache.invalidate(0) };
cache.plan(&[5], &mut plan).expect("slot is free again");
let stats = cache.stats();
assert_eq!(
stats.cold_misses, 2,
"expert 5 was never resident, so this is still a cold miss"
);
assert_eq!(
stats.eviction_misses, 0,
"an expert that was never fetched cannot have been evicted"
);
cache.mark_ready(0);
cache.release(0);
step(&mut cache, &[6]); assert!(!holds(&cache, 5));
step(&mut cache, &[5]);
let stats = cache.stats();
assert_eq!(stats.cold_misses, 3, "expert 6 was the third cold miss");
assert_eq!(
stats.eviction_misses, 1,
"expert 5 had been resident this time, so its retry is an eviction miss"
);
}
#[test]
fn a_request_on_an_in_flight_fill_is_not_counted_as_a_hit() {
let mut cache = new_cache(2, 8);
let mut plan = CachePlan::new();
cache.plan(&[0], &mut plan).expect("empty cache");
assert_eq!(plan.misses(), [(0, 0)]);
cache.plan(&[0], &mut plan).expect("expert 0 owns a slot");
assert_eq!(
plan.hits(),
[(0, 0)],
"the plan still reports it as resident, so no second read is issued"
);
assert!(
plan.misses().is_empty(),
"a second read would alias the buffer"
);
assert!(!cache.is_ready(0), "the bytes are not valid yet");
let stats = cache.stats();
assert_eq!(stats.hits, 0, "nothing has been served without a read");
assert_eq!(stats.pending_hits, 1);
assert_eq!(stats.misses, 1);
assert_eq!(stats.accesses(), 2);
assert_eq!(stats.hit_rate(), 0.0);
cache.mark_ready(0);
cache.plan(&[0], &mut plan).expect("expert 0 is resident");
let stats = cache.stats();
assert_eq!(stats.hits, 1);
assert_eq!(stats.pending_hits, 1);
assert_eq!(stats.accesses(), 3);
assert!((stats.hit_rate() - 1.0 / 3.0).abs() < 1e-12);
}
#[test]
fn construction_bounds_the_slot_count_and_the_id_space() {
assert_eq!(LayerCache::new(12, 0).unwrap_err(), CacheError::NoExperts);
assert_eq!(
LayerCache::new(12, MAX_EXPERTS + 1).unwrap_err(),
CacheError::ExpertSpaceTooLarge {
n_experts: MAX_EXPERTS + 1,
limit: MAX_EXPERTS,
}
);
assert_eq!(
LayerCache::new(u32::MAX, 128).unwrap_err(),
CacheError::TooManySlots {
n_slots: u32::MAX,
limit: MAX_SLOTS,
}
);
LayerCache::new(MAX_SLOTS, MAX_EXPERTS).expect("the caps are inclusive");
LayerCache::new(0, 8).expect("a zero-slot layer is legal");
let cache = LayerCache::new(11, 128).expect("the operating point");
assert_eq!(cache.n_slots(), 11);
assert_eq!(cache.n_experts(), 128);
}
#[test]
fn a_hit_slot_that_is_never_released_is_detected() {
let mut cache = new_cache(2, 8);
let mut plan = CachePlan::new();
cache.plan(&[0], &mut plan).expect("empty cache");
cache.mark_ready(0);
cache.release(0);
let mut plans = 0u64;
while cache.stuck_protected_slot().is_none() {
cache.plan(&[0], &mut plan).expect("expert 0 is resident");
assert!(plan.misses().is_empty(), "expert 0 stays resident");
plans += 1;
assert!(
plans <= STUCK_PROTECTED_PLANS + 8,
"the leaked Ready slot was never reported"
);
}
assert_eq!(cache.stuck_protected_slot(), Some(0));
assert!(
plans > STUCK_PROTECTED_PLANS,
"reported after only {plans} plans, before the slot could be called leaked"
);
}
#[test]
fn the_detector_still_fires_once_the_leak_wedges_the_whole_layer() {
const SLOTS: u32 = 11;
let mut cache = new_cache(SLOTS, 128);
let mut plan = CachePlan::new();
let tokens: [[u32; 8]; 4] = [
[0, 1, 2, 3, 4, 5, 6, 7],
[0, 1, 2, 3, 4, 5, 6, 7],
[8, 9, 10, 0, 1, 2, 3, 4],
[8, 9, 10, 0, 1, 2, 3, 4],
];
for experts in tokens {
cache.plan(&experts, &mut plan).expect("11 slots, top-8");
for &(_, slot) in plan.misses() {
cache.mark_ready(slot);
cache.release(slot);
}
}
assert_eq!(
(0..SLOTS).filter(|&s| cache.resident(s).is_some()).count(),
SLOTS as usize,
"every slot is occupied"
);
assert_eq!(
cache.stuck_protected_slot(),
None,
"four plans in, nothing has been protected long enough to be a leak"
);
let mut wedged = 0u64;
while cache.stuck_protected_slot().is_none() {
let err = cache.plan(&[11], &mut plan).unwrap_err();
assert_eq!(
err,
CacheError::AllSlotsBusy {
n_slots: SLOTS,
free: 0,
needed: 1,
},
"the layer should be wedged, not merely busy"
);
wedged += 1;
assert!(
wedged <= STUCK_PROTECTED_PLANS + 8,
"the layer has answered AllSlotsBusy for {wedged} consecutive \
steps and the detector has still not reported the leak"
);
}
assert!(
wedged >= STUCK_PROTECTED_PLANS - tokens.len() as u64,
"reported after only {wedged} wedged steps"
);
}
#[test]
fn a_fill_whose_completion_is_never_reaped_is_detected() {
let mut cache = new_cache(2, 8);
let mut plan = CachePlan::new();
cache.plan(&[0], &mut plan).expect("empty cache");
assert_eq!(plan.misses(), [(0, 0)]);
let mut plans = 0u64;
while cache.stuck_protected_slot().is_none() {
cache.plan(&[1], &mut plan).expect("slot 1 serves expert 1");
plans += 1;
assert!(
plans <= STUCK_PROTECTED_PLANS + 8,
"the unreaped fill was never reported"
);
}
assert_eq!(
cache.stuck_protected_slot(),
Some(0),
"the Filling slot is the leaked one"
);
}
#[test]
fn a_well_behaved_caller_never_looks_stuck() {
let mut cache = new_cache(4, 8);
for i in 0..(STUCK_PROTECTED_PLANS * 3) {
step(&mut cache, &[(i % 8) as u32]);
assert_eq!(
cache.stuck_protected_slot(),
None,
"false positive at step {i}"
);
}
}
#[test]
#[cfg(debug_assertions)]
#[should_panic(expected = "releasing misses but not hits")]
fn plan_asserts_on_a_stuck_protected_slot_in_debug_builds() {
let mut cache = new_cache(2, 8);
let mut plan = CachePlan::new();
cache.plan(&[0], &mut plan).expect("empty cache");
cache.mark_ready(0);
cache.release(0);
for _ in 0..(STUCK_PROTECTED_PLANS + 8) {
cache.plan(&[0], &mut plan).expect("expert 0 is resident");
}
}
#[test]
fn the_plan_buffer_is_reused_without_reallocating() {
let mut cache = new_cache(12, 128);
let mut plan = CachePlan::with_capacity(8);
let steps: [[u32; 8]; 3] = [
[0, 1, 2, 3, 4, 5, 6, 7],
[0, 9, 2, 11, 4, 13, 6, 15],
[16, 1, 18, 3, 20, 5, 22, 7],
];
for experts in steps {
cache.plan(&experts, &mut plan).expect("12 slots, top-8");
for &(_, slot) in plan.misses() {
cache.mark_ready(slot);
}
for &(_, slot) in plan.hits().iter().chain(plan.misses()) {
cache.release(slot);
}
assert_eq!(plan.len(), 8);
assert_eq!(plan.hits.capacity(), 8);
assert_eq!(plan.misses.capacity(), 8);
}
}
#[test]
fn counters_survive_but_never_decay() {
let mut cache = new_cache(2, 4);
for _ in 0..6 {
step(&mut cache, &[0]);
}
for _ in 0..40 {
step(&mut cache, &[1, 2]);
}
assert!(!holds(&cache, 0), "expert 0 was pushed out");
step(&mut cache, &[0]);
let plan = step(&mut cache, &[3]);
assert_eq!(plan.misses().len(), 1);
assert_eq!(cache.resident(plan.misses()[0].1), Some(3));
assert_ne!(
cache.stats().eviction_misses,
0,
"the thrash is counted as eviction misses, not cold ones"
);
}
#[test]
fn a_zero_slot_layer_reports_instead_of_panicking() {
let mut cache = new_cache(0, 8);
let mut plan = CachePlan::new();
let err = cache.plan(&[0], &mut plan).unwrap_err();
assert_eq!(
err,
CacheError::TooFewSlots {
n_slots: 0,
requested: 1
}
);
cache
.plan(&[], &mut plan)
.expect("an empty step is trivially fine");
assert!(plan.is_empty());
cache.mark_ready(9);
cache.release(9);
unsafe { cache.invalidate(9) };
assert!(!cache.is_ready(9));
assert_eq!(cache.resident(9), None);
}
}