Scan-resistant eviction policies for the #147 benchmark: Segmented-LRU and SRRIP – the deterministic, low-metadata candidates a DO-178C page cache can actually ship (no ghost lists, bounded eviction scan). More...

#include "cache_bench.h"
#include "ra8_attributes.h"

Include dependency graph for policy_scanresist.c:

Data Structures
struct	slru_t
	Two LRU segments threaded through shared prev/next frame arrays. More...

Enumerations
enum	slru_seg_t : uint8_t { k_slru_probation = 0U , k_slru_protected = 1U }
	Per-frame segment tag stored in frame meta[0]. More...
enum	slru_dim_t : uint32_t { k_slru_protected_pct = 75U , k_slru_pct_full_scale = 100U , k_slru_meta_bytes = 9U }
	Protected-segment share of the cache, in percent, plus associated scaling and metadata constants. More...
enum	rrip_rrpv_t : uint8_t { k_rrip_near = 0U , k_rrip_long = 2U , k_rrip_max = 3U }
	RRIP re-reference prediction values (2-bit). More...

Functions
static void	internal_slru_unlink (slru_t l, int32_t f, int32_t head, int32_t *tail)
	Detach `f` from the list whose head/tail pointers are given.
static void	internal_slru_push_head (slru_t l, int32_t f, int32_t head, int32_t *tail)
	Push `f` to the MRU head of the segment.
static int	internal_slru_init (cb_cache_t *c)
	Bind SLRU state: two LRU segments over shared frame arrays.
static void	internal_slru_deinit (cb_cache_t *c)
	Release SLRU state (control block + shared index arrays).
static void	internal_slru_insert (cb_cache_t *c, uint32_t frame)
	SLRU insert hook: admit a fresh `frame` to the probationary segment.
static void	internal_slru_access (cb_cache_t *c, uint32_t frame)
	SLRU hit hook: promote or refresh `frame` on re-reference.
static uint32_t	internal_slru_victim (cb_cache_t c, uint32_t scanned)
	Choose the SLRU victim: probationary LRU first, else protected LRU.
static int	internal_srrip_init (cb_cache_t *c)
	Bind SRRIP state: a sweep hand over the frame ring.
static void	internal_srrip_deinit (cb_cache_t *c)
	Release SRRIP state (the sweep hand).
static void	internal_srrip_insert (cb_cache_t *c, uint32_t frame)
	SRRIP insert hook: predict a distant re-reference for `frame`.
static void	internal_srrip_access (cb_cache_t *c, uint32_t frame)
	SRRIP hit hook: predict an immediate re-reference for `frame`.
static uint32_t	internal_srrip_victim (cb_cache_t c, uint32_t scanned)
	Choose the SRRIP victim by aging RRPVs to the maximum.

Variables
const cache_policy_t	g_cb_policy_slru
	Segmented-LRU: the scan-resistant candidate (src/policy_scanresist.c).
const cache_policy_t	g_cb_policy_srrip
	SRRIP: the 2-bit re-reference-interval candidate (src/policy_scanresist.c).

Detailed Description

Scan-resistant eviction policies for the #147 benchmark: Segmented-LRU and SRRIP – the deterministic, low-metadata candidates a DO-178C page cache can actually ship (no ghost lists, bounded eviction scan).

SLRU (Segmented LRU / the 2Q family without a ghost list): a probationary and a protected LRU segment. New pages enter probationary; a second touch promotes to protected; eviction always takes the probationary LRU first. A one-time scan therefore churns only the probationary segment and cannot evict the re-referenced (protected) hot set – the scan resistance LRU/CLOCK lack.
SRRIP (Static Re-Reference Interval Prediction, the RRIP HW-cache family): a 2-bit re-reference prediction value per frame. Inserts predict a distant re-reference (RRPV = max-1) so scanned-once pages are evicted before re-referenced ones; a hit predicts immediate re-reference (RRPV = 0). Eviction picks an RRPV == max frame, aging all frames until one appears.

[Ring 7 / Tooling] {World: NS}

Copyright: Copyright (c) 2026 Brighton Sikarskie SPDX-License-Identifier: MIT

Since: 0.1.0

Definition in file policy_scanresist.c.

Enumeration Type Documentation

◆ rrip_rrpv_t

enum rrip_rrpv_t : uint8_t

RRIP re-reference prediction values (2-bit).

Enumerator
k_rrip_near	Immediate re-reference (just hit).
k_rrip_long	Distant re-reference (fresh insert).
k_rrip_max	Furthest – the eviction candidate.

Definition at line 327 of file policy_scanresist.c.

◆ slru_dim_t

enum slru_dim_t : uint32_t

Protected-segment share of the cache, in percent, plus associated scaling and metadata constants.

k_slru_protected_pct is the fraction of the cache reserved for the protected (re-referenced) segment, expressed as an integer percentage.
k_slru_pct_full_scale is the divisor that converts a ratio expressed in the same units as k_slru_protected_pct into a frame count.
k_slru_meta_bytes is the per-frame metadata consumed by SLRU: one uint8_t segment tag (meta[0]) plus eight bytes of linked-list indices (two int32_t values: prev and next, threaded through the shared arrays).
Since
0.1.0

Enumerator
k_slru_protected_pct	Protected-segment target, percent of capacity.
k_slru_pct_full_scale	Divisor for percent-to-frame-count conversion.
k_slru_meta_bytes	Per-frame metadata: 1 B tag + 8 B list indices.

Definition at line 52 of file policy_scanresist.c.

◆ slru_seg_t

enum slru_seg_t : uint8_t

Per-frame segment tag stored in frame meta[0].

Enumerator
k_slru_probation	Frame is in the probationary segment.
k_slru_protected	Frame is in the protected segment.

Definition at line 33 of file policy_scanresist.c.

Function Documentation

◆ internal_slru_access()

void internal_slru_access	(	cb_cache_t *	c,
		uint32_t	frame )

static

SLRU hit hook: promote or refresh frame on re-reference.

A protected-segment hit moves the frame to the protected MRU head. A probationary hit promotes the frame to protected; if the protected segment is full, its LRU is first demoted back to probationary, so a second touch is what earns scan-resistant residency. Bound as on_access.

Parameters

[in,out]	c	Cache holding the SLRU segments in policy_data.
[in]	frame	Frame that was just hit.

Precondition: c->policy_data is a valid internal_slru_init state.; frame is currently resident and linked in a segment.

Postcondition: frame is at the protected MRU head, tagged protected.; pt_count <= pt_cap (a demotion restored the bound if needed).

Note: Not thread-safe: mutates the shared segment lists.

Since: 0.1.0

Definition at line 251 of file policy_scanresist.c.

References cb_cache_t::frames, internal_slru_push_head(), internal_slru_unlink(), k_slru_probation, k_slru_protected, cb_frame_t::meta, slru_t::pb_head, slru_t::pb_tail, cb_cache_t::policy_data, slru_t::pt_cap, slru_t::pt_count, slru_t::pt_head, and slru_t::pt_tail.

◆ internal_slru_deinit()

void internal_slru_deinit ( cb_cache_t * c )

static

Release SLRU state (control block + shared index arrays).

Frees the prev/next arrays and the slru_t when present; a NULL policy_data (a failed init) is tolerated.

Parameters

[in,out] c Cache whose SLRU binding is ended.

Precondition: c is non-NULL.; c->policy_data is a internal_slru_init state or NULL.

Postcondition: The binding is cleared; caller storage is untouched.; c->policy_data is left dangling; the caller discards the cache.

Note: Safe for distinct caller-owned cache bindings.

Since: 0.1.0

Definition at line 199 of file policy_scanresist.c.

References cb_cache_t::policy_data.

◆ internal_slru_init()

int internal_slru_init ( cb_cache_t * c )

static

Bind SLRU state: two LRU segments over shared frame arrays.

Allocates the slru_t control block and the shared prev/next index arrays, empties both segments, and sizes the protected segment at k_slru_protected_pct percent of capacity. The control block and both arrays occupy one exact caller slab.

Parameters

[in,out] c Cache whose policy_data receives the segments; capacity sizes the index arrays and the protected cap.

Returns: int 0 on success, 1 when caller storage is too small.

Return values

0	c->policy_data holds empty probationary + protected segments.
1	Caller workspace does not meet the exact requirement.

Precondition: c is non-NULL with capacity > 0.; Called on the single benchmark thread.

Postcondition: On success both segment heads/tails are -1 and pt_cap is set.; On failure c->policy_data is untouched (nothing is leaked).

Note: Safe for distinct caller-owned cache bindings.

Since: 0.1.0

Definition at line 164 of file policy_scanresist.c.

References cb_cache_t::capacity, k_slru_pct_full_scale, k_slru_protected_pct, slru_t::next, slru_t::pb_head, slru_t::pb_tail, cb_cache_t::policy_data, cb_cache_t::policy_workspace, cb_cache_t::policy_workspace_bytes, slru_t::prev, slru_t::pt_cap, slru_t::pt_head, and slru_t::pt_tail.

◆ internal_slru_insert()

void internal_slru_insert	(	cb_cache_t *	c,
		uint32_t	frame )

static

SLRU insert hook: admit a fresh frame to the probationary segment.

Tags frame k_slru_probation in meta[0] and pushes it to the probationary MRU head. New pages always enter probationary, so a one-time scan churns only that segment. Bound as on_insert.

Parameters

[in,out]	c	Cache holding the SLRU segments in policy_data.
[in]	frame	Frame that was just (re)populated.

Precondition: c->policy_data is a valid internal_slru_init state.; frame is detached and frame < capacity.

Postcondition: frame is the probationary-segment head, tagged probationary.; The protected segment is unchanged.

Note: Not thread-safe: mutates the shared segment lists.

Since: 0.1.0

Definition at line 223 of file policy_scanresist.c.

References cb_cache_t::frames, internal_slru_push_head(), k_slru_probation, cb_frame_t::meta, slru_t::pb_head, slru_t::pb_tail, and cb_cache_t::policy_data.

◆ internal_slru_push_head()

void internal_slru_push_head	(	slru_t *	l,
		int32_t	f,
		int32_t *	head,
		int32_t *	tail )

static

Push f to the MRU head of the segment.

The generic head-insert for both SLRU segments: sets f as the new head, links the former head behind it, and initializes tail when the segment was empty. f must already be detached.

Parameters

[in,out]	l	Segment pair holding the shared prev/next arrays.
[in]	f	Frame index to insert at the head (currently detached).
[in,out]	head	The segment's head endpoint, set to `f`.
[in,out]	tail	The segment's tail endpoint, set to `f` if it was empty.

Precondition: f is detached and f < capacity.; head and tail are non-NULL.

Postcondition: *head == f and f precedes the former head.; *tail == f iff the segment was previously empty.

Note: Not thread-safe: mutates the shared segment lists.

Since: 0.1.0

Definition at line 127 of file policy_scanresist.c.

References slru_t::next, and slru_t::prev.

Referenced by internal_slru_access(), and internal_slru_insert().

◆ internal_slru_unlink()

void internal_slru_unlink	(	slru_t *	l,
		int32_t	f,
		int32_t *	head,
		int32_t *	tail )

static

Detach f from the list whose head/tail pointers are given.

The generic unlink used for both SLRU segments: it repairs the neighbours' prev/next links and advances head / tail inward when f is an endpoint, so one routine serves the probationary and protected lists sharing the frame arrays.

Parameters

[in,out]	l	Segment pair holding the shared prev/next arrays.
[in]	f	Frame index to detach (a member of head..tail).
[in,out]	head	The segment's head endpoint, updated if `f` was head.
[in,out]	tail	The segment's tail endpoint, updated if `f` was tail.

Precondition: f is currently linked in the segment named by head / tail.; head and tail are non-NULL and f < capacity.

Postcondition: f is absent from that segment; neighbour links stay consistent.; *head/*tail still name real members (or -1 if the segment emptied).

Note: Not thread-safe: mutates the shared segment lists.

Since: 0.1.0

Definition at line 92 of file policy_scanresist.c.

References slru_t::next, and slru_t::prev.

Referenced by internal_slru_access(), and internal_slru_victim().

◆ internal_slru_victim()

uint32_t internal_slru_victim	(	cb_cache_t *	c,
		uint32_t *	scanned )

static

Choose the SLRU victim: probationary LRU first, else protected LRU.

Evicts the probationary-segment tail when it exists (scan traffic lands here), falling back to the protected tail only when the probationary segment is empty. Reports a scan depth of one – the victim is always an O(1) tail lookup.

Parameters

[in,out]	c	Cache holding the SLRU segments in policy_data.
[out]	scanned	Receives the frames examined (always 1).

Returns: uint32_t The victim frame index (< capacity).

Return values

<capacity The probationary LRU, or the protected LRU if none.

Precondition: c->policy_data is a valid internal_slru_init state with a resident frame.; scanned is non-NULL.

Postcondition: *scanned == 1 and the victim is unlinked from its segment.; pt_count drops by one only when a protected frame was evicted.

Note: Not thread-safe: mutates the shared segment lists.

Since: 0.1.0

Definition at line 297 of file policy_scanresist.c.

References internal_slru_unlink(), slru_t::pb_head, slru_t::pb_tail, cb_cache_t::policy_data, slru_t::pt_count, slru_t::pt_head, and slru_t::pt_tail.

◆ internal_srrip_access()

void internal_srrip_access	(	cb_cache_t *	c,
		uint32_t	frame )

static

SRRIP hit hook: predict an immediate re-reference for frame.

Resets frame's RRPV to k_rrip_near (0) in meta[0], marking a re-referenced page as the furthest from eviction. Bound as on_access.

Parameters

[in,out]	c	Cache whose frame RRPV is reset.
[in]	frame	Frame that was just hit.

Precondition: c is non-NULL and frame < capacity.; frame is currently resident.

Postcondition: frames[frame].meta[0] == k_rrip_near.; No other frame or policy state changes.

Note: Not thread-safe: writes shared frame metadata.

Since: 0.1.0

Definition at line 424 of file policy_scanresist.c.

References cb_cache_t::frames, k_rrip_near, and cb_frame_t::meta.

◆ internal_srrip_deinit()

void internal_srrip_deinit ( cb_cache_t * c )

static

Release SRRIP state (the sweep hand).

Ends the SRRIP binding without releasing caller-owned storage.

Parameters

[in,out] c Cache whose SRRIP binding is ended.

Precondition: c is non-NULL.; c->policy_data is a internal_srrip_init hand or NULL.

Postcondition: The hand pointer is cleared; caller storage is untouched.; c->policy_data is left dangling; the caller discards the cache.

Note: Safe for distinct caller-owned cache bindings.

Since: 0.1.0

Definition at line 378 of file policy_scanresist.c.

References cb_cache_t::policy_data.

◆ internal_srrip_init()

int internal_srrip_init ( cb_cache_t * c )

static

Bind SRRIP state: a sweep hand over the frame ring.

Allocates one zeroed uint32_t aging hand in c->policy_data; each frame's 2-bit re-reference prediction value (RRPV) lives in meta[0], set on insert/access and aged toward the max during eviction.

Parameters

[in,out] c Cache whose policy_data receives the hand pointer.

Returns: int 0 on success, 1 when caller storage is absent.

Return values

0	c->policy_data holds a zeroed hand.
1	Caller storage is absent; c->policy_data is NULL.

Precondition: c is non-NULL and its policy_data is unset.; Called on the single benchmark thread.

Postcondition: On success c->policy_data points at a zero-initialized hand.; No frame contents are altered.

Note: Safe for distinct caller-owned cache bindings.

Since: 0.1.0

Definition at line 356 of file policy_scanresist.c.

References cb_cache_t::policy_data, and cb_cache_t::policy_workspace.

◆ internal_srrip_insert()

void internal_srrip_insert	(	cb_cache_t *	c,
		uint32_t	frame )

static

SRRIP insert hook: predict a distant re-reference for frame.

Sets frame's RRPV to k_rrip_long (max-1) in meta[0], so a scanned-once page sits one aging step from eviction and is reclaimed before any re-referenced page. Bound as on_insert.

Parameters

[in,out]	c	Cache whose frame RRPV is set.
[in]	frame	Frame that was just (re)populated.

Precondition: c is non-NULL and frame < capacity.; frame is currently resident.

Postcondition: frames[frame].meta[0] == k_rrip_long.; No other frame or policy state changes.

Note: Not thread-safe: writes shared frame metadata.

Since: 0.1.0

Definition at line 401 of file policy_scanresist.c.

References cb_cache_t::frames, k_rrip_long, and cb_frame_t::meta.

◆ internal_srrip_victim()

uint32_t internal_srrip_victim	(	cb_cache_t *	c,
		uint32_t *	scanned )

static

Choose the SRRIP victim by aging RRPVs to the maximum.

Sweeps the hand around the ring: the first frame at RRPV k_rrip_max is evicted; every frame below max is aged up by one on the way. Because inserts start at max-1, a victim is guaranteed within two ring passes. Reports the frames examined.

Parameters

[in,out]	c	Cache holding the sweep hand in policy_data.
[out]	scanned	Receives the frames examined this call (>= 1).

Returns: uint32_t The victim frame index (< capacity).

Return values

<capacity The first frame reached at RRPV k_rrip_max.

Precondition: c->policy_data is a valid internal_srrip_init hand and capacity > 0.; scanned is non-NULL.

Postcondition: *scanned equals the frames inspected and the hand advanced past them.; Frames passed over below max had their RRPV incremented.

Note: Not thread-safe: advances the hand and ages RRPVs.

Since: 0.1.0

Definition at line 451 of file policy_scanresist.c.

References cb_cache_t::capacity, cb_cache_t::frames, k_rrip_max, cb_frame_t::meta, and cb_cache_t::policy_data.

Variable Documentation

◆ g_cb_policy_slru

const cache_policy_t g_cb_policy_slru

Initial value:

                                      = {
  .name              = "SLRU",
  .meta_bytes        = (size_t)k_slru_meta_bytes,
  .state_base_bytes  = sizeof(slru_t),
  .state_frame_bytes = 2U * sizeof(int32_t),
  .init              = internal_slru_init,
  .deinit            = internal_slru_deinit,
  .on_access         = internal_slru_access,
  .on_insert         = internal_slru_insert,
  .pick_victim       = internal_slru_victim,
}

Segmented-LRU: the scan-resistant candidate (src/policy_scanresist.c).

A probationary + protected LRU pair; one-time scans churn only the probationary segment, so the re-referenced hot set survives.

Note: Read-only after load; registered in g_cb_policies.

Since: 0.1.0

Definition at line 312 of file policy_scanresist.c.

◆ g_cb_policy_srrip

const cache_policy_t g_cb_policy_srrip

Initial value:

                                       = {
  .name              = "SRRIP",
  .meta_bytes        = 1U,
  .state_base_bytes  = sizeof(uint32_t),
  .state_frame_bytes = 0U,
  .init              = internal_srrip_init,
  .deinit            = internal_srrip_deinit,
  .on_access         = internal_srrip_access,
  .on_insert         = internal_srrip_insert,
  .pick_victim       = internal_srrip_victim,
}

SRRIP: the 2-bit re-reference-interval candidate (src/policy_scanresist.c).

Inserts predict a distant re-reference so scanned-once pages are evicted before re-referenced ones; a hit predicts immediate reuse.

Note: Read-only after load; registered in g_cb_policies.

Since: 0.1.0

Definition at line 470 of file policy_scanresist.c.

Data Structures

Enumerations

Functions

Variables

Detailed Description

Enumeration Type Documentation

◆ rrip_rrpv_t

◆ slru_dim_t

◆ slru_seg_t

Function Documentation

◆ internal_slru_access()

◆ internal_slru_deinit()

◆ internal_slru_init()

◆ internal_slru_insert()

◆ internal_slru_push_head()

◆ internal_slru_unlink()

◆ internal_slru_victim()

◆ internal_srrip_access()

◆ internal_srrip_deinit()

◆ internal_srrip_init()

◆ internal_srrip_insert()

◆ internal_srrip_victim()

Variable Documentation

◆ g_cb_policy_slru

◆ g_cb_policy_srrip