use std::io;
use crate::config::runtime::L1EvictionPolicy;
use crate::hashing::FixedPrehashedMap;
pub const MAX_POLICY_SCAN_STEPS: usize = 64;
pub const MAX_POLICY_SLOT_INDEX: usize = (u32::MAX - 1) as usize;
const NO_POLICY_SLOT: u32 = u32::MAX;
const RESIDENT_BIT: u8 = 1 << 0;
const CLOCK_VISITED_BIT: u8 = 1 << 1;
const S3FIFO_FREQUENCY_SHIFT: u8 = 1;
const S3FIFO_FREQUENCY_MASK: u8 = 0b11 << S3FIFO_FREQUENCY_SHIFT;
const S3FIFO_MAIN_BIT: u8 = 1 << 3;
const S3FIFO_MAX_FREQUENCY: u8 = 3;
const S3FIFO_MOVE_TO_MAIN_THRESHOLD: u8 = 2;
#[derive(Clone, Copy, Debug, Default)]
pub struct PolicySlot {
hash: u64,
clock_position: u32,
flags: u8,
}
impl PolicySlot {
pub const fn new_free(next: u32) -> Self {
Self {
hash: 0,
clock_position: next,
flags: 0,
}
}
pub fn free_next(&self) -> u32 {
debug_assert!(!self.is_resident());
self.clock_position
}
fn new_clock(hash: u64, visited: bool, position: u32) -> Self {
Self {
hash,
clock_position: position,
flags: RESIDENT_BIT | (u8::from(visited) * CLOCK_VISITED_BIT),
}
}
fn new_s3fifo(hash: u64, queue: QueueKind, frequency: u8) -> Self {
debug_assert!(frequency <= S3FIFO_MAX_FREQUENCY);
Self {
hash,
clock_position: 0,
flags: RESIDENT_BIT
| ((frequency << S3FIFO_FREQUENCY_SHIFT) & S3FIFO_FREQUENCY_MASK)
| (u8::from(queue == QueueKind::Main) * S3FIFO_MAIN_BIT),
}
}
pub const fn hash(&self) -> u64 {
self.hash
}
const fn is_resident(&self) -> bool {
self.flags & RESIDENT_BIT != 0
}
const fn clock_visited(&self) -> bool {
self.flags & CLOCK_VISITED_BIT != 0
}
fn set_clock_visited(&mut self, visited: bool) {
self.flags = (self.flags & !CLOCK_VISITED_BIT) | (u8::from(visited) * CLOCK_VISITED_BIT);
}
const fn clock_position(&self) -> u32 {
self.clock_position
}
fn set_clock_position(&mut self, position: u32) {
self.clock_position = position;
}
const fn s3fifo_queue(&self) -> QueueKind {
if self.flags & S3FIFO_MAIN_BIT == 0 {
QueueKind::Small
} else {
QueueKind::Main
}
}
const fn s3fifo_frequency(&self) -> u8 {
(self.flags & S3FIFO_FREQUENCY_MASK) >> S3FIFO_FREQUENCY_SHIFT
}
fn set_s3fifo_frequency(&mut self, frequency: u8) {
debug_assert!(frequency <= S3FIFO_MAX_FREQUENCY);
self.flags = (self.flags & !S3FIFO_FREQUENCY_MASK)
| ((frequency << S3FIFO_FREQUENCY_SHIFT) & S3FIFO_FREQUENCY_MASK);
}
fn increment_s3fifo_frequency(&mut self) {
let frequency = self.flags & S3FIFO_FREQUENCY_MASK;
self.flags += u8::from(frequency != S3FIFO_FREQUENCY_MASK) << S3FIFO_FREQUENCY_SHIFT;
}
fn set_s3fifo_queue(&mut self, queue: QueueKind) {
self.flags = (self.flags & !S3FIFO_MAIN_BIT)
| (u8::from(queue == QueueKind::Main) * S3FIFO_MAIN_BIT);
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
enum QueueKind {
Small,
Main,
}
#[derive(Clone, Copy, Debug)]
enum DetachedPolicyKind {
Clock,
S3Fifo { queue: QueueKind, frequency: u8 },
}
#[derive(Clone, Copy, Debug)]
pub struct DetachedPolicy {
hash: u64,
weight: usize,
kind: DetachedPolicyKind,
}
impl DetachedPolicy {
pub const fn hash(self) -> u64 {
self.hash
}
pub const fn weight(self) -> usize {
self.weight
}
}
pub enum EvictionState {
Clock(ClockState),
S3Fifo(S3FifoState),
}
impl EvictionState {
pub fn new(
policy: L1EvictionPolicy,
capacity_bytes: usize,
maximum_entries: usize,
) -> io::Result<Self> {
match policy {
L1EvictionPolicy::Clock => Ok(Self::Clock(ClockState::new(maximum_entries)?)),
L1EvictionPolicy::S3Fifo => Ok(Self::S3Fifo(S3FifoState::new(
capacity_bytes,
maximum_entries,
)?)),
}
}
pub fn allocation_bytes(policy: L1EvictionPolicy, maximum_entries: usize) -> io::Result<usize> {
match policy {
L1EvictionPolicy::Clock => ClockState::allocation_bytes(maximum_entries),
L1EvictionPolicy::S3Fifo => S3FifoState::allocation_bytes(maximum_entries),
}
}
pub fn insert(&mut self, slots: &mut [PolicySlot], index: usize, hash: u64, weight: usize) {
debug_assert!(!slots[index].is_resident());
match self {
Self::Clock(state) => {
state.insert(slots, index, hash, false);
}
Self::S3Fifo(state) => {
state.insert(slots, index, hash, weight);
}
}
}
pub fn record_hit(&mut self, slots: &mut [PolicySlot], index: usize) {
match self {
Self::Clock(_) => slots[index].set_clock_visited(true),
Self::S3Fifo(_) => slots[index].increment_s3fifo_frequency(),
}
}
pub fn remove(&mut self, slots: &mut [PolicySlot], index: usize) {
if !slots.get(index).is_some_and(PolicySlot::is_resident) {
return;
}
match self {
Self::Clock(state) => state.remove(slots, index),
Self::S3Fifo(state) => state.remove(slots, index),
}
}
pub fn detach_for_admission(
&mut self,
slots: &mut [PolicySlot],
index: usize,
weight: usize,
) -> DetachedPolicy {
match self {
Self::Clock(state) => {
let hash = slots[index].hash();
state.remove(slots, index);
DetachedPolicy {
hash,
weight,
kind: DetachedPolicyKind::Clock,
}
}
Self::S3Fifo(state) => state.detach(slots, index, weight),
}
}
pub fn restore_for_admission(
&mut self,
slots: &mut [PolicySlot],
index: usize,
detached: DetachedPolicy,
) {
debug_assert!(!slots[index].is_resident());
match (self, detached.kind) {
(Self::Clock(state), DetachedPolicyKind::Clock) => {
state.insert(slots, index, detached.hash, true);
}
(Self::S3Fifo(state), DetachedPolicyKind::S3Fifo { queue, frequency }) => state
.restore(
slots,
index,
detached.hash,
detached.weight,
queue,
frequency,
),
_ => unreachable!("detached L1 policy does not match the configured policy"),
}
}
pub fn commit_eviction(&mut self, detached: DetachedPolicy) {
match (self, detached.kind) {
(Self::Clock(_), DetachedPolicyKind::Clock) => {}
(Self::S3Fifo(state), DetachedPolicyKind::S3Fifo { queue, .. }) => {
if queue == QueueKind::Small {
state.ghost.insert(detached.hash, detached.weight);
}
}
_ => unreachable!("detached L1 policy does not match the configured policy"),
}
}
pub fn select_victim<F>(
&mut self,
slots: &mut [PolicySlot],
remaining_steps: &mut usize,
can_reclaim: F,
) -> Option<usize>
where
F: Fn(usize) -> bool,
{
match self {
Self::Clock(state) => state.select_victim(slots, remaining_steps, can_reclaim),
Self::S3Fifo(state) => state.select_victim(slots, remaining_steps, can_reclaim),
}
}
}
pub struct ClockState {
hand: usize,
residents: Vec<u32>,
}
impl ClockState {
fn new(maximum_entries: usize) -> io::Result<Self> {
let mut residents = Vec::new();
residents.try_reserve_exact(maximum_entries).map_err(|_| {
io::Error::new(
io::ErrorKind::OutOfMemory,
"cannot allocate CLOCK resident positions",
)
})?;
Ok(Self { hand: 0, residents })
}
fn allocation_bytes(maximum_entries: usize) -> io::Result<usize> {
maximum_entries
.checked_mul(size_of::<u32>())
.ok_or_else(|| io::Error::new(io::ErrorKind::InvalidInput, "CLOCK is too large"))
}
fn insert(&mut self, slots: &mut [PolicySlot], index: usize, hash: u64, visited: bool) {
assert!(
self.residents.len() < slots.len() && self.residents.len() < self.residents.capacity(),
"CLOCK resident capacity exhausted"
);
let position = u32::try_from(self.residents.len())
.expect("validated CLOCK resident position exceeds u32");
let packed_index =
u32::try_from(index).expect("validated CLOCK resident index exceeds u32");
slots[index] = PolicySlot::new_clock(hash, visited, position);
self.residents.push(packed_index);
}
fn remove(&mut self, slots: &mut [PolicySlot], index: usize) {
let position = usize::try_from(slots[index].clock_position())
.expect("CLOCK resident position exceeds usize");
let removed = self.residents.swap_remove(position);
debug_assert_eq!(usize::try_from(removed).ok(), Some(index));
if position < self.residents.len() {
let moved = usize::try_from(self.residents[position])
.expect("CLOCK resident index exceeds usize");
slots[moved].set_clock_position(
u32::try_from(position).expect("CLOCK resident position exceeds u32"),
);
}
slots[index] = PolicySlot::default();
if self.hand >= self.residents.len() {
self.hand = 0;
}
}
fn select_victim<F>(
&mut self,
slots: &mut [PolicySlot],
remaining_steps: &mut usize,
can_reclaim: F,
) -> Option<usize>
where
F: Fn(usize) -> bool,
{
for _ in 0..maximum_scan_steps(self.residents.len()) {
if self.residents.is_empty() || !take_scan_step(remaining_steps) {
break;
}
let position = if self.hand < self.residents.len() {
self.hand
} else {
0
};
self.hand = if position + 1 == self.residents.len() {
0
} else {
position + 1
};
let index = usize::try_from(self.residents[position])
.expect("CLOCK resident index exceeds usize");
let slot = &mut slots[index];
debug_assert!(slot.is_resident());
if slot.clock_visited() {
slot.set_clock_visited(false);
continue;
}
if can_reclaim(index) {
return Some(index);
}
}
None
}
}
#[derive(Clone, Copy)]
struct S3FifoLink {
previous: u32,
next: u32,
weight: u32,
}
const _: () = assert!(size_of::<S3FifoLink>() == 12);
impl Default for S3FifoLink {
fn default() -> Self {
Self {
previous: NO_POLICY_SLOT,
next: NO_POLICY_SLOT,
weight: 0,
}
}
}
struct PolicyQueue {
head: u32,
tail: u32,
bytes: usize,
}
impl PolicyQueue {
const fn empty() -> Self {
Self {
head: NO_POLICY_SLOT,
tail: NO_POLICY_SLOT,
bytes: 0,
}
}
fn is_empty(&self) -> bool {
self.head == NO_POLICY_SLOT
}
fn front(&self) -> Option<usize> {
(self.head != NO_POLICY_SLOT)
.then(|| usize::try_from(self.head).expect("policy slot index exceeds usize"))
}
fn push_back(&mut self, links: &mut [S3FifoLink], index: usize, weight: usize) {
let packed = u32::try_from(index).expect("policy slot index exceeds u32");
let packed_weight = u32::try_from(weight).expect("L1 entry weight exceeds u32");
debug_assert_eq!(links[index].weight, 0);
links[index] = S3FifoLink {
previous: self.tail,
next: NO_POLICY_SLOT,
weight: packed_weight,
};
if self.tail == NO_POLICY_SLOT {
self.head = packed;
} else {
let tail = usize::try_from(self.tail).expect("policy slot index exceeds usize");
links[tail].next = packed;
}
self.tail = packed;
self.bytes = self.bytes.saturating_add(weight);
}
fn remove(&mut self, links: &mut [S3FifoLink], index: usize) -> usize {
let packed = u32::try_from(index).expect("policy slot index exceeds u32");
let link = links[index];
debug_assert_ne!(link.weight, 0);
if link.previous == NO_POLICY_SLOT {
debug_assert_eq!(self.head, packed);
self.head = link.next;
} else {
let previous = usize::try_from(link.previous).expect("policy slot index exceeds usize");
links[previous].next = link.next;
}
if link.next == NO_POLICY_SLOT {
debug_assert_eq!(self.tail, packed);
self.tail = link.previous;
} else {
let next = usize::try_from(link.next).expect("policy slot index exceeds usize");
links[next].previous = link.previous;
}
links[index] = S3FifoLink::default();
let weight = link.weight as usize;
self.bytes = self.bytes.saturating_sub(weight);
weight
}
fn move_to_back(&mut self, links: &mut [S3FifoLink], index: usize) {
let packed = u32::try_from(index).expect("policy slot index exceeds u32");
if self.tail == packed {
return;
}
let weight = self.remove(links, index);
self.push_back(links, index, weight);
}
}
pub struct S3FifoState {
links: Box<[S3FifoLink]>,
small: PolicyQueue,
main: PolicyQueue,
main_capacity_bytes: usize,
ghost: GhostQueue,
}
impl S3FifoState {
fn new(capacity_bytes: usize, maximum_entries: usize) -> io::Result<Self> {
let mut links = Vec::new();
links.try_reserve_exact(maximum_entries).map_err(|_| {
io::Error::new(
io::ErrorKind::OutOfMemory,
"cannot allocate S3-FIFO resident links",
)
})?;
links.resize(maximum_entries, S3FifoLink::default());
let small_capacity_bytes = capacity_bytes / 10;
let main_capacity_bytes = capacity_bytes.saturating_sub(small_capacity_bytes);
Ok(Self {
links: links.into_boxed_slice(),
small: PolicyQueue::empty(),
main: PolicyQueue::empty(),
main_capacity_bytes,
ghost: GhostQueue::new(maximum_entries, main_capacity_bytes)?,
})
}
fn allocation_bytes(maximum_entries: usize) -> io::Result<usize> {
let links = maximum_entries
.checked_mul(size_of::<S3FifoLink>())
.ok_or_else(|| io::Error::new(io::ErrorKind::InvalidInput, "S3-FIFO is too large"))?;
links
.checked_add(GhostQueue::allocation_bytes(maximum_entries)?)
.ok_or_else(|| io::Error::new(io::ErrorKind::InvalidInput, "S3-FIFO is too large"))
}
fn insert(&mut self, slots: &mut [PolicySlot], index: usize, hash: u64, weight: usize) {
let queue = if self.ghost.take(hash) {
QueueKind::Main
} else {
QueueKind::Small
};
slots[index] = PolicySlot::new_s3fifo(hash, queue, 0);
self.push_back(queue, index, weight);
}
fn remove(&mut self, slots: &mut [PolicySlot], index: usize) {
let queue = slots[index].s3fifo_queue();
self.remove_from(queue, index);
slots[index] = PolicySlot::default();
}
fn detach(
&mut self,
slots: &mut [PolicySlot],
index: usize,
expected_weight: usize,
) -> DetachedPolicy {
let slot = slots[index];
let queue = slot.s3fifo_queue();
let frequency = slot.s3fifo_frequency();
let weight = self.remove_from(queue, index);
debug_assert_eq!(weight, expected_weight);
slots[index] = PolicySlot::default();
DetachedPolicy {
hash: slot.hash(),
weight,
kind: DetachedPolicyKind::S3Fifo { queue, frequency },
}
}
fn restore(
&mut self,
slots: &mut [PolicySlot],
index: usize,
hash: u64,
weight: usize,
queue: QueueKind,
frequency: u8,
) {
slots[index] = PolicySlot::new_s3fifo(hash, queue, frequency);
self.push_back(queue, index, weight);
}
fn select_victim<F>(
&mut self,
slots: &mut [PolicySlot],
remaining_steps: &mut usize,
can_reclaim: F,
) -> Option<usize>
where
F: Fn(usize) -> bool,
{
let mut prefer_small = false;
for _ in 0..maximum_scan_steps(slots.len()) {
if !take_scan_step(remaining_steps) {
break;
}
let queue = if prefer_small && !self.small.is_empty() {
prefer_small = false;
QueueKind::Small
} else if self.main.bytes > self.main_capacity_bytes || self.small.is_empty() {
QueueKind::Main
} else {
QueueKind::Small
};
let index = self.queue(queue).front()?;
let frequency = slots[index].s3fifo_frequency();
match queue {
QueueKind::Small if frequency >= S3FIFO_MOVE_TO_MAIN_THRESHOLD => {
self.move_small_to_main(slots, index);
}
QueueKind::Main if frequency > 0 => {
slots[index].set_s3fifo_frequency(frequency - 1);
self.main.move_to_back(&mut self.links, index);
}
_ if can_reclaim(index) => return Some(index),
QueueKind::Small => {
self.move_small_to_main(slots, index);
}
QueueKind::Main => {
self.main.move_to_back(&mut self.links, index);
prefer_small = true;
}
}
}
None
}
fn move_small_to_main(&mut self, slots: &mut [PolicySlot], index: usize) {
let weight = self.small.remove(&mut self.links, index);
slots[index].set_s3fifo_queue(QueueKind::Main);
self.main.push_back(&mut self.links, index, weight);
}
fn queue(&self, queue: QueueKind) -> &PolicyQueue {
match queue {
QueueKind::Small => &self.small,
QueueKind::Main => &self.main,
}
}
fn push_back(&mut self, queue: QueueKind, index: usize, weight: usize) {
let links = &mut self.links;
match queue {
QueueKind::Small => self.small.push_back(links, index, weight),
QueueKind::Main => self.main.push_back(links, index, weight),
}
}
fn remove_from(&mut self, queue: QueueKind, index: usize) -> usize {
let links = &mut self.links;
match queue {
QueueKind::Small => self.small.remove(links, index),
QueueKind::Main => self.main.remove(links, index),
}
}
}
struct GhostQueue {
directory: FixedPrehashedMap,
hashes: Box<[u64]>,
links: Box<[S3FifoLink]>,
free_head: u32,
queue: PolicyQueue,
capacity_bytes: usize,
}
impl GhostQueue {
fn new(maximum_entries: usize, capacity_bytes: usize) -> io::Result<Self> {
let directory = FixedPrehashedMap::try_new(maximum_entries)?;
let mut hashes = Vec::new();
hashes.try_reserve_exact(maximum_entries).map_err(|_| {
io::Error::new(
io::ErrorKind::OutOfMemory,
"cannot allocate S3-FIFO ghost hashes",
)
})?;
hashes.resize(maximum_entries, 0);
let mut links = Vec::new();
links.try_reserve_exact(maximum_entries).map_err(|_| {
io::Error::new(
io::ErrorKind::OutOfMemory,
"cannot allocate S3-FIFO ghost links",
)
})?;
links.resize(maximum_entries, S3FifoLink::default());
for (index, link) in links.iter_mut().enumerate() {
link.next = if index + 1 == maximum_entries {
NO_POLICY_SLOT
} else {
u32::try_from(index + 1).expect("validated L1 entry capacity exceeds u32")
};
}
Ok(Self {
directory,
hashes: hashes.into_boxed_slice(),
links: links.into_boxed_slice(),
free_head: if maximum_entries == 0 {
NO_POLICY_SLOT
} else {
0
},
queue: PolicyQueue::empty(),
capacity_bytes,
})
}
fn allocation_bytes(maximum_entries: usize) -> io::Result<usize> {
let hashes = maximum_entries
.checked_mul(size_of::<u64>())
.ok_or_else(|| {
io::Error::new(io::ErrorKind::InvalidInput, "ghost queue is too large")
})?;
let links = maximum_entries
.checked_mul(size_of::<S3FifoLink>())
.ok_or_else(|| {
io::Error::new(io::ErrorKind::InvalidInput, "ghost queue is too large")
})?;
FixedPrehashedMap::allocation_bytes(maximum_entries)?
.checked_add(hashes)
.and_then(|bytes| bytes.checked_add(links))
.ok_or_else(|| io::Error::new(io::ErrorKind::InvalidInput, "ghost queue is too large"))
}
fn take(&mut self, hash: u64) -> bool {
let Some(packed) = self.directory.remove(hash) else {
return false;
};
let index = usize::try_from(packed).expect("ghost slot index exceeds usize");
let matched = self.hashes[index] == hash;
self.unlink(index);
matched
}
fn insert(&mut self, hash: u64, weight: usize) {
debug_assert_ne!(weight, 0);
if u32::try_from(weight).is_err() || weight > self.capacity_bytes || self.links.is_empty() {
return;
}
if self.free_head == NO_POLICY_SLOT
|| self.queue.bytes.saturating_add(weight) > self.capacity_bytes
{
let Some(head) = self.queue.front() else {
return;
};
let head_weight = self.links[head].weight as usize;
if self
.queue
.bytes
.saturating_sub(head_weight)
.saturating_add(weight)
> self.capacity_bytes
{
return;
}
let removed = self.directory.remove(self.hashes[head]);
debug_assert_eq!(removed, Some(self.queue.head));
self.unlink(head);
}
let packed = self.free_head;
debug_assert_ne!(packed, NO_POLICY_SLOT);
let index = usize::try_from(packed).expect("ghost slot index exceeds usize");
self.free_head = self.links[index].next;
self.hashes[index] = hash;
self.queue.push_back(&mut self.links, index, weight);
match self.directory.insert(hash, packed) {
Some(Some(previous)) => {
let previous = usize::try_from(previous).expect("ghost slot index exceeds usize");
self.unlink(previous);
}
Some(None) => {}
None => self.unlink(index),
}
}
fn unlink(&mut self, index: usize) {
let packed = u32::try_from(index).expect("ghost slot index exceeds u32");
let _ = self.queue.remove(&mut self.links, index);
self.hashes[index] = 0;
self.links[index] = S3FifoLink {
next: self.free_head,
..S3FifoLink::default()
};
self.free_head = packed;
}
}
fn maximum_scan_steps(slot_count: usize) -> usize {
slot_count
.saturating_mul(2)
.saturating_add(1)
.min(MAX_POLICY_SCAN_STEPS)
}
fn take_scan_step(remaining_steps: &mut usize) -> bool {
if *remaining_steps == 0 {
false
} else {
*remaining_steps -= 1;
true
}
}
#[cfg(test)]
mod tests {
use super::*;
fn policy(kind: L1EvictionPolicy, capacity: usize, entries: usize) -> EvictionState {
EvictionState::new(kind, capacity, entries).unwrap()
}
fn install(
policy: &mut EvictionState,
slots: &mut Vec<PolicySlot>,
hash: u64,
weight: usize,
) -> usize {
let index = slots.len();
slots.push(PolicySlot::default());
policy.insert(slots, index, hash, weight);
index
}
#[test]
fn clock_new_entries_are_immediately_evictable() {
let mut policy = policy(L1EvictionPolicy::Clock, 1024, 2);
let mut slots = Vec::new();
let first = install(&mut policy, &mut slots, 1, 1);
let second = install(&mut policy, &mut slots, 2, 1);
let mut remaining_steps = MAX_POLICY_SCAN_STEPS;
assert_eq!(
policy.select_victim(&mut slots, &mut remaining_steps, |_| true),
Some(first)
);
assert_eq!(
policy.select_victim(&mut slots, &mut remaining_steps, |_| true),
Some(second)
);
}
#[test]
fn clock_scans_residents_in_sparse_slot_arrays() {
let mut policy = policy(L1EvictionPolicy::Clock, 1024, 128);
let mut slots = vec![PolicySlot::default(); 128];
policy.insert(&mut slots, 96, 7, 1);
let mut remaining_steps = MAX_POLICY_SCAN_STEPS;
assert_eq!(
policy.select_victim(&mut slots, &mut remaining_steps, |_| true),
Some(96)
);
}
#[test]
fn clock_removal_updates_a_moved_resident_position() {
let mut policy = policy(L1EvictionPolicy::Clock, 1024, 8);
let mut slots = vec![PolicySlot::default(); 8];
policy.insert(&mut slots, 1, 1, 1);
policy.insert(&mut slots, 4, 4, 1);
policy.insert(&mut slots, 7, 7, 1);
policy.remove(&mut slots, 4);
policy.remove(&mut slots, 7);
let mut remaining_steps = MAX_POLICY_SCAN_STEPS;
assert_eq!(
policy.select_victim(&mut slots, &mut remaining_steps, |_| true),
Some(1)
);
}
#[test]
fn one_clock_admission_has_one_fixed_scan_budget() {
let mut policy = policy(L1EvictionPolicy::Clock, 1024, 100);
let mut slots = Vec::new();
for hash in 0..100 {
let index = install(&mut policy, &mut slots, hash, 1);
policy.record_hit(&mut slots, index);
}
let mut remaining_steps = MAX_POLICY_SCAN_STEPS;
assert_eq!(
policy.select_victim(&mut slots, &mut remaining_steps, |_| true),
None
);
assert_eq!(remaining_steps, 0);
}
#[test]
fn failed_clock_admission_restores_a_detached_entry() {
let mut policy = policy(L1EvictionPolicy::Clock, 1024, 1);
let mut slots = Vec::new();
let index = install(&mut policy, &mut slots, 7, 11);
let detached = policy.detach_for_admission(&mut slots, index, 11);
policy.restore_for_admission(&mut slots, index, detached);
assert_eq!(slots[index].hash(), 7);
assert!(slots[index].clock_visited());
}
#[test]
fn clock_prefers_a_hit_over_a_cold_one_shot_entry() {
let mut policy = policy(L1EvictionPolicy::Clock, 1024, 2);
let mut slots = Vec::new();
let hot = install(&mut policy, &mut slots, 1, 1);
let cold = install(&mut policy, &mut slots, 2, 1);
policy.record_hit(&mut slots, hot);
let mut remaining_steps = MAX_POLICY_SCAN_STEPS;
assert_eq!(
policy.select_victim(&mut slots, &mut remaining_steps, |_| true),
Some(cold)
);
}
#[test]
fn s3fifo_promotes_reused_small_entries_and_ghost_hits_enter_main() {
let mut policy = policy(L1EvictionPolicy::S3Fifo, 1000, 10);
let mut slots = Vec::new();
for hash in 1..=10 {
install(&mut policy, &mut slots, hash, 100);
}
policy.record_hit(&mut slots, 0);
policy.record_hit(&mut slots, 0);
let mut remaining_steps = MAX_POLICY_SCAN_STEPS;
let victim = policy
.select_victim(&mut slots, &mut remaining_steps, |_| true)
.unwrap();
assert_eq!(victim, 1);
assert_eq!(slots[0].s3fifo_queue(), QueueKind::Main);
let detached = policy.detach_for_admission(&mut slots, victim, 100);
policy.commit_eviction(detached);
policy.insert(&mut slots, victim, 2, 100);
assert_eq!(slots[victim].s3fifo_queue(), QueueKind::Main);
}
#[test]
fn s3fifo_main_frequency_is_consumed_with_a_fixed_budget() {
let mut policy = policy(L1EvictionPolicy::S3Fifo, 100, 1);
let mut slots = Vec::new();
let hot = install(&mut policy, &mut slots, 7, 100);
policy.record_hit(&mut slots, hot);
policy.record_hit(&mut slots, hot);
let mut remaining_steps = MAX_POLICY_SCAN_STEPS;
assert_eq!(
policy.select_victim(&mut slots, &mut remaining_steps, |_| true),
None
);
assert_eq!(slots[hot].s3fifo_queue(), QueueKind::Main);
assert_eq!(slots[hot].s3fifo_frequency(), 0);
assert_eq!(
policy.select_victim(&mut slots, &mut remaining_steps, |_| true),
Some(hot)
);
}
#[test]
fn failed_s3fifo_admission_restores_queue_and_frequency() {
let mut policy = policy(L1EvictionPolicy::S3Fifo, 1000, 1);
let mut slots = Vec::new();
let index = install(&mut policy, &mut slots, 7, 100);
policy.record_hit(&mut slots, index);
let detached = policy.detach_for_admission(&mut slots, index, 100);
policy.restore_for_admission(&mut slots, index, detached);
assert_eq!(slots[index].hash(), 7);
assert_eq!(slots[index].s3fifo_queue(), QueueKind::Small);
assert_eq!(slots[index].s3fifo_frequency(), 1);
}
#[test]
fn retained_small_entry_does_not_block_a_reclaimable_follower() {
let mut policy = policy(L1EvictionPolicy::S3Fifo, 1000, 2);
let mut slots = Vec::new();
let retained = install(&mut policy, &mut slots, 7, 100);
let reclaimable = install(&mut policy, &mut slots, 8, 100);
let mut remaining_steps = MAX_POLICY_SCAN_STEPS;
assert_eq!(
policy.select_victim(&mut slots, &mut remaining_steps, |index| index != retained),
Some(reclaimable)
);
assert_eq!(slots[retained].s3fifo_queue(), QueueKind::Main);
}
#[test]
fn mixed_size_ghost_insert_never_runs_a_multi_entry_cleanup() {
let mut ghost = GhostQueue::new(3, 100).unwrap();
ghost.insert(1, 10);
ghost.insert(2, 10);
ghost.insert(3, 80);
ghost.insert(4, 80);
assert_eq!(ghost.queue.bytes, 100);
assert_eq!(ghost.free_head, NO_POLICY_SLOT);
assert_eq!(ghost.directory.get(1), Some(0));
assert_eq!(ghost.directory.get(2), Some(1));
assert_eq!(ghost.directory.get(3), Some(2));
assert_eq!(ghost.directory.get(4), None);
}
#[test]
fn ghost_fingerprint_collision_is_not_a_false_hit() {
let mut ghost = GhostQueue::new(2, 100).unwrap();
let first = 1_u64;
let colliding = 1_u64 << 45;
ghost.insert(first, 10);
assert!(!ghost.take(colliding));
assert_eq!(ghost.queue.bytes, 0);
assert!(!ghost.take(first));
}
#[test]
fn ghost_reuses_an_unlinked_slot() {
let mut ghost = GhostQueue::new(2, 100).unwrap();
ghost.insert(1, 10);
ghost.insert(2, 10);
assert!(ghost.take(1));
ghost.insert(3, 10);
assert_eq!(ghost.free_head, NO_POLICY_SLOT);
assert_eq!(ghost.directory.get(3), Some(0));
}
}