Reference eviction policies + the registry for the #147 benchmark. More...

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

Include dependency graph for policies.c:

Data Structures
struct	cb_lru_t
	LRU recency list threaded through prev/next frame-index arrays. More...

Enumerations
enum	cb_rand_seed_t : uint64_t { k_rand_seed = 0x123456789ABCDEF0ULL }
	Initial PRNG seed for the Random eviction policy. More...
enum	cb_rand_shift_t : uint8_t { k_rand_shift_a = 13U , k_rand_shift_b = 7U , k_rand_shift_c = 17U }
	xorshift64 shift-amount triple used in the Random policy's PRNG step. More...

Functions
static int	internal_fifo_init (cb_cache_t *c)
	Bind FIFO state: a single round-robin hand over the frame ring.
static void	internal_fifo_deinit (cb_cache_t *c)
	Release FIFO state (the insertion hand).
static uint32_t	internal_fifo_victim (cb_cache_t c, uint32_t scanned)
	Choose the FIFO victim: the frame the hand currently points at.
static int	internal_rand_init (cb_cache_t *c)
	Bind Random-policy state: a deterministic xorshift64 seed.
static void	internal_rand_deinit (cb_cache_t *c)
	Release Random-policy state (the PRNG seed).
static uint32_t	internal_rand_victim (cb_cache_t c, uint32_t scanned)
	Choose a uniformly random victim frame.
static int	internal_lru_init (cb_cache_t *c)
	Bind true-LRU state: a doubly-linked recency list over frames.
static void	internal_lru_deinit (cb_cache_t *c)
	Release true-LRU state (control block + index arrays).
static void	internal_lru_unlink (cb_lru_t *l, int32_t f)
	Unlink frame `f` from the recency list.
static void	internal_lru_to_head (cb_lru_t *l, int32_t f)
	Splice frame `f` to the MRU (most-recently-used) head.
static void	internal_lru_touch (cb_cache_t *c, uint32_t frame)
	LRU hit hook: move the just-accessed `frame` to the MRU head.
static void	internal_lru_insert (cb_cache_t *c, uint32_t frame)
	LRU insert hook: place a freshly-loaded `frame` at the MRU head.
static uint32_t	internal_lru_victim (cb_cache_t c, uint32_t scanned)
	Choose the LRU victim: the frame at the list tail.
static int	internal_clock_init (cb_cache_t *c)
	Bind CLOCK state: one reference bit per frame + a sweep hand.
static void	internal_clock_deinit (cb_cache_t *c)
	Release CLOCK state (the sweep hand).
static void	internal_clock_set (cb_cache_t *c, uint32_t frame)
	CLOCK reference hook: set `frame's` reference bit.
static uint32_t	internal_clock_victim (cb_cache_t c, uint32_t scanned)
	Choose the CLOCK victim by second-chance sweep.

Variables
static const cache_policy_t	s_cb_policy_fifo
static const cache_policy_t	s_cb_policy_random
static const cache_policy_t	s_cb_policy_lru
static const cache_policy_t	s_cb_policy_clock
const cache_policy_t *const	g_cb_policies []
	The registered policy table (defined in src/policies.c).
const uint32_t	g_cb_policy_count = (uint32_t)(sizeof(g_cb_policies) / sizeof(g_cb_policies[0]))
	Number of entries in g_cb_policies.

Detailed Description

Reference eviction policies + the registry for the #147 benchmark.

Baselines the scan-resistant candidates must beat: FIFO and Random (no recency), true LRU (good on locality, thrashes on linear scan), and CLOCK (the standard embedded second-chance LRU approximation). The scan-resistant policies (2Q / Segmented-LRU, CLOCK-Pro, CAR) live in their own TUs and are appended to g_cb_policies.

[Ring 7 / Tooling] {World: NS}

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

Since: 0.1.0

Definition in file policies.c.

Enumeration Type Documentation

◆ cb_rand_seed_t

enum cb_rand_seed_t : uint64_t

Initial PRNG seed for the Random eviction policy.

A fixed non-zero 64-bit value that initialises the xorshift64 state so benchmark runs are reproducible. Any non-zero odd value would work; this one is the splitmix64 gamma constant, chosen for good bit-distribution as a starting state.

Since: 0.1.0

Enumerator
k_rand_seed	Reproducible non-zero xorshift seed.

Definition at line 124 of file policies.c.

◆ cb_rand_shift_t

enum cb_rand_shift_t : uint8_t

xorshift64 shift-amount triple used in the Random policy's PRNG step.

The triple (13, 7, 17) is one of the parameter sets listed in Marsaglia (2003) for a full-period 64-bit xorshift generator. Changing any value breaks the period guarantee.

Since: 0.1.0

Enumerator
k_rand_shift_a	First xorshift64 shift.
k_rand_shift_b	Second xorshift64 shift.
k_rand_shift_c	Third xorshift64 shift.

Definition at line 136 of file policies.c.

Function Documentation

◆ internal_clock_deinit()

void internal_clock_deinit ( cb_cache_t * c )

static

Release CLOCK state (the sweep hand).

Ends the CLOCK binding without releasing caller-owned storage.

Parameters

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

Precondition: c is non-NULL.; c->policy_data is a internal_clock_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 506 of file policies.c.

References cb_cache_t::policy_data.

◆ internal_clock_init()

int internal_clock_init ( cb_cache_t * c )

static

Bind CLOCK state: one reference bit per frame + a sweep hand.

Allocates one zeroed uint32_t sweep hand in c->policy_data; the reference bit lives in each frame's meta[0], set on access/insert and cleared as the hand gives a frame its second chance.

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 484 of file policies.c.

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

◆ internal_clock_set()

void internal_clock_set	(	cb_cache_t *	c,
		uint32_t	frame )

static

CLOCK reference hook: set frame's reference bit.

Writes 1 to frames[frame].meta[0], marking the frame as recently used so the sweep hand grants it one second chance before eviction. Bound as both on_access and on_insert.

Parameters

[in,out]	c	Cache whose frame reference bit is set.
[in]	frame	Frame just accessed or inserted.

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

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

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

Since: 0.1.0

Definition at line 529 of file policies.c.

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

◆ internal_clock_victim()

uint32_t internal_clock_victim	(	cb_cache_t *	c,
		uint32_t *	scanned )

static

Choose the CLOCK victim by second-chance sweep.

Advances the hand around the ring: a frame with its reference bit set is spared once (the bit is cleared) and skipped; the first frame found with a clear bit is evicted. Reports the number of frames examined, so a full ring of set bits costs one extra pass at most.

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 with a clear reference bit.

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

Postcondition: *scanned equals the frames inspected and the hand advanced past them.; Every spared frame's reference bit was cleared.

Note: Not thread-safe: advances the hand and clears reference bits.

Since: 0.1.0

Definition at line 556 of file policies.c.

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

◆ internal_fifo_deinit()

void internal_fifo_deinit ( cb_cache_t * c )

static

Release FIFO state (the insertion hand).

Ends the FIFO binding without releasing caller-owned storage.

Parameters

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

Precondition: c is non-NULL.; c->policy_data is a internal_fifo_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 67 of file policies.c.

References cb_cache_t::policy_data.

◆ internal_fifo_init()

int internal_fifo_init ( cb_cache_t * c )

static

Bind FIFO state: a single round-robin hand over the frame ring.

Allocates one zeroed uint32_t insertion hand and stores it in c->policy_data; the hand advances modulo capacity on each victim pick, giving pure first-in-first-out order with no recency bits.

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 45 of file policies.c.

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

◆ internal_fifo_victim()

uint32_t internal_fifo_victim	(	cb_cache_t *	c,
		uint32_t *	scanned )

static

Choose the FIFO victim: the frame the hand currently points at.

Returns the frame under the round-robin hand, then advances the hand modulo capacity, so frames are evicted in insertion order. Reports a scan depth of exactly one (O(1), the ideal WCET).

Parameters

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

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

Return values

<capacity The frame the hand pointed at on entry.

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

Postcondition: *scanned == 1.; The hand has advanced by one (mod capacity).

Note: Not thread-safe: advances the shared hand.

Since: 0.1.0

Definition at line 93 of file policies.c.

References cb_cache_t::capacity, and cb_cache_t::policy_data.

◆ internal_lru_deinit()

void internal_lru_deinit ( cb_cache_t * c )

static

Release true-LRU state (control block + index arrays).

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

Parameters

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

Precondition: c is non-NULL.; c->policy_data is a internal_lru_init list 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 302 of file policies.c.

References cb_cache_t::policy_data.

◆ internal_lru_init()

int internal_lru_init ( cb_cache_t * c )

static

Bind true-LRU state: a doubly-linked recency list over frames.

Allocates the cb_lru_t control block plus prev/next index arrays (one entry per frame) and marks the list empty (head/tail -1). The control block and arrays occupy one exact caller slab.

Parameters

[in,out] c Cache whose policy_data receives the list; capacity sizes the prev/next arrays.

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

Return values

0	c->policy_data holds an empty recency list.
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 c->policy_data is a list with head == tail == -1.; 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 271 of file policies.c.

References cb_cache_t::capacity, cb_lru_t::head, cb_lru_t::next, cb_cache_t::policy_data, cb_cache_t::policy_workspace, cb_cache_t::policy_workspace_bytes, cb_lru_t::prev, and cb_lru_t::tail.

◆ internal_lru_insert()

void internal_lru_insert	(	cb_cache_t *	c,
		uint32_t	frame )

static

LRU insert hook: place a freshly-loaded frame at the MRU head.

Links the newly populated frame in at the head (it is not yet in the list), so it becomes the most-recently-used. Bound as the policy's on_insert.

Parameters

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

Precondition: c->policy_data is a valid internal_lru_init list.; frame is detached (its old key was unlinked on eviction).

Postcondition: frame is at the MRU head of the list.; The list grows by one member.

Note: Not thread-safe: mutates the shared list.

Since: 0.1.0

Definition at line 413 of file policies.c.

References internal_lru_to_head(), and cb_cache_t::policy_data.

◆ internal_lru_to_head()

void internal_lru_to_head	(	cb_lru_t *	l,
		int32_t	f )

static

Splice frame f to the MRU (most-recently-used) head.

Makes f the new head, linking the former head behind it and setting the tail to f when the list was empty. f must already be detached (see internal_lru_unlink).

Parameters

[in,out]	l	The recency list to edit.
[in]	f	Frame index to place at the head.

Precondition: l is a valid list and f is currently detached.; f is a valid frame index < capacity.

Postcondition: l->head == f and f precedes the former head.; l->tail names f iff the list was previously empty.

Note: Not thread-safe: mutates the shared list.

Since: 0.1.0

Definition at line 357 of file policies.c.

References cb_lru_t::head, cb_lru_t::next, cb_lru_t::prev, and cb_lru_t::tail.

Referenced by internal_lru_insert(), and internal_lru_touch().

◆ internal_lru_touch()

void internal_lru_touch	(	cb_cache_t *	c,
		uint32_t	frame )

static

LRU hit hook: move the just-accessed frame to the MRU head.

Unlinks frame from its current position and re-inserts it at the head, so the least-recently-used frame stays at the tail (the next victim). Bound as the policy's on_access.

Parameters

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

Precondition: c->policy_data is a valid internal_lru_init list.; frame is currently resident and linked.

Postcondition: frame is at the MRU head of the list.; The list length is unchanged.

Note: Not thread-safe: mutates the shared list.

Since: 0.1.0

Definition at line 388 of file policies.c.

References internal_lru_to_head(), internal_lru_unlink(), and cb_cache_t::policy_data.

◆ internal_lru_unlink()

void internal_lru_unlink	(	cb_lru_t *	l,
		int32_t	f )

static

Unlink frame f from the recency list.

Repairs its neighbours' prev/next links and, when f was the head or tail, advances that endpoint inward, leaving the list consistent with f detached.

Parameters

[in,out]	l	The recency list to edit.
[in]	f	Frame index to detach (must be a member).

Precondition: l is a valid list and f is currently linked in it.; f is a valid frame index < capacity.

Postcondition: f is absent from the list; neighbour links stay consistent.; l->head/l->tail still name real members (or -1 if now empty).

Note: Not thread-safe: mutates the shared list.

Since: 0.1.0

Definition at line 325 of file policies.c.

References cb_lru_t::head, cb_lru_t::next, cb_lru_t::prev, and cb_lru_t::tail.

Referenced by internal_lru_touch(), and internal_lru_victim().

◆ internal_lru_victim()

uint32_t internal_lru_victim	(	cb_cache_t *	c,
		uint32_t *	scanned )

static

Choose the LRU victim: the frame at the list tail.

Returns the least-recently-used frame (the tail) and unlinks it so the caller can repopulate it. Reports a scan depth of one – true LRU finds its victim in O(1).

Parameters

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

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

Return values

<capacity The least-recently-used resident frame.

Precondition: c->policy_data is a valid, non-empty internal_lru_init list.; scanned is non-NULL.

Postcondition: *scanned == 1 and the victim is unlinked from the list.; The list shrinks by one member.

Note: Not thread-safe: mutates the shared list.

Since: 0.1.0

Definition at line 440 of file policies.c.

References internal_lru_unlink(), cb_cache_t::policy_data, and cb_lru_t::tail.

◆ internal_rand_deinit()

void internal_rand_deinit ( cb_cache_t * c )

static

Release Random-policy state (the PRNG seed).

Ends the Random binding without releasing caller-owned storage.

Parameters

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

Precondition: c is non-NULL.; c->policy_data is a internal_rand_init seed or NULL.

Postcondition: The seed 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 189 of file policies.c.

References cb_cache_t::policy_data.

◆ internal_rand_init()

int internal_rand_init ( cb_cache_t * c )

static

Bind Random-policy state: a deterministic xorshift64 seed.

Allocates one uint64_t seeded with the fixed k_rand_seed so eviction choices are pseudo-random yet reproducible across runs and hosts. Stored in c->policy_data.

Parameters

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

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

Return values

0	c->policy_data holds the seeded PRNG state.
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 state seeded with k_rand_seed.; No frame contents are altered.

Note: Safe for distinct caller-owned cache bindings.

Since: 0.1.0

Definition at line 164 of file policies.c.

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

◆ internal_rand_victim()

uint32_t internal_rand_victim	(	cb_cache_t *	c,
		uint32_t *	scanned )

static

Choose a uniformly random victim frame.

Advances the xorshift64 state one step and returns x % capacity, so any resident frame is equally likely regardless of recency. Reports a scan depth of one (the choice is O(1)).

Parameters

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

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

Return values

<capacity A pseudo-random resident frame.

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

Postcondition: *scanned == 1 and the PRNG state has advanced one step.; No frame contents are altered.

Note: Not thread-safe: advances the shared PRNG state.

Since: 0.1.0

Definition at line 215 of file policies.c.

References cb_cache_t::capacity, k_rand_shift_a, k_rand_shift_b, k_rand_shift_c, and cb_cache_t::policy_data.

Variable Documentation

◆ g_cb_policies

const cache_policy_t* const g_cb_policies[]

Initial value:

                                         = {
  &s_cb_policy_fifo,
  &s_cb_policy_random,
  &s_cb_policy_lru,
  &s_cb_policy_clock,
  &g_cb_policy_slru,
  &g_cb_policy_srrip,
}

The registered policy table (defined in src/policies.c).

Definition at line 586 of file policies.c.

Referenced by internal_report_summary(), and internal_report_trace().

◆ g_cb_policy_count

const uint32_t g_cb_policy_count = (uint32_t)(sizeof(g_cb_policies) / sizeof(g_cb_policies[0]))

Number of entries in g_cb_policies.

Definition at line 594 of file policies.c.

Referenced by internal_report_summary(), and internal_report_trace().

◆ s_cb_policy_clock

const cache_policy_t s_cb_policy_clock

static

Initial value:

                                              = {
  .name              = "CLOCK",
  .meta_bytes        = 1U,
  .state_base_bytes  = sizeof(uint32_t),
  .state_frame_bytes = 0U,
  .init              = internal_clock_init,
  .deinit            = internal_clock_deinit,
  .on_access         = internal_clock_set,
  .on_insert         = internal_clock_set,
  .pick_victim       = internal_clock_victim,
}

Definition at line 572 of file policies.c.

◆ s_cb_policy_fifo

const cache_policy_t s_cb_policy_fifo

static

Initial value:

                                             = {
  .name              = "FIFO",
  .meta_bytes        = 0U,
  .state_base_bytes  = sizeof(uint32_t),
  .state_frame_bytes = 0U,
  .init              = internal_fifo_init,
  .deinit            = internal_fifo_deinit,
  .on_access         = nullptr,
  .on_insert         = nullptr,
  .pick_victim       = internal_fifo_victim,
}

Definition at line 101 of file policies.c.

◆ s_cb_policy_lru

const cache_policy_t s_cb_policy_lru

static

Initial value:

                                            = {
  .name              = "LRU",
  .meta_bytes        = 8U,
  .state_base_bytes  = sizeof(cb_lru_t),
  .state_frame_bytes = 2U * sizeof(int32_t),
  .init              = internal_lru_init,
  .deinit            = internal_lru_deinit,
  .on_access         = internal_lru_touch,
  .on_insert         = internal_lru_insert,
  .pick_victim       = internal_lru_victim,
}

Definition at line 448 of file policies.c.

◆ s_cb_policy_random

const cache_policy_t s_cb_policy_random

static

Initial value:

                                               = {
  .name              = "Random",
  .meta_bytes        = 0U,
  .state_base_bytes  = sizeof(uint64_t),
  .state_frame_bytes = 0U,
  .init              = internal_rand_init,
  .deinit            = internal_rand_deinit,
  .on_access         = nullptr,
  .on_insert         = nullptr,
  .pick_victim       = internal_rand_victim,
}

Definition at line 226 of file policies.c.

Data Structures

Enumerations

Functions

Variables

Detailed Description

Enumeration Type Documentation

◆ cb_rand_seed_t

◆ cb_rand_shift_t

Function Documentation

◆ internal_clock_deinit()

◆ internal_clock_init()

◆ internal_clock_set()

◆ internal_clock_victim()

◆ internal_fifo_deinit()

◆ internal_fifo_init()

◆ internal_fifo_victim()

◆ internal_lru_deinit()

◆ internal_lru_init()

◆ internal_lru_insert()

◆ internal_lru_to_head()

◆ internal_lru_touch()

◆ internal_lru_unlink()

◆ internal_lru_victim()

◆ internal_rand_deinit()

◆ internal_rand_init()

◆ internal_rand_victim()

Variable Documentation

◆ g_cb_policies

◆ g_cb_policy_count

◆ s_cb_policy_clock

◆ s_cb_policy_fifo

◆ s_cb_policy_lru

◆ s_cb_policy_random