cache_bench.c File Reference

#147 eviction-policy benchmark: the exact-accounting replay engine. More...

#include "cache_bench.h"
#include <string.h>
#include "cache_bench_io.h"
#include "ra8_attributes.h"
#include "trace.h"

Include dependency graph for cache_bench.c:

Go to the source code of this file.

Data Structures
struct	cb_index_t
	Exact key->frame lookup over the resident set (chained hash). More...

Enumerations
enum	cb_hash_mul_t : uint64_t { k_hash_mix_mul = 0xFF51AFD7ED558CCDULL }
	Murmur3 finalizer constants used in internal_hash. More...
enum	cb_hash_shift_t : uint8_t { k_hash_shift = 33U }
	Murmur3 finalizer bit-shift amounts used in internal_hash. More...
enum	cb_hash_limit_t : uint32_t { k_cb_max_hash_capacity = UINT32_C(1) << 29U }

Functions
static uint32_t	internal_pow2_ceil (uint32_t v)
	Round v up to a power of two (>= 1).
static uint32_t	internal_hash (cb_key_t k)
	Mix an (object,page) key into a 32-bit hash for bucket selection.
static bool	internal_key_eq (cb_key_t a, cb_key_t b)
	Report whether two cache keys name the same (object, page).
static int32_t	internal_index_find (const cb_index_t *idx, const cb_frame_t *frames, cb_key_t key)
	Find the resident frame currently holding key, or -1.
static void	internal_index_remove (cb_index_t *idx, const cb_frame_t *frames, uint32_t frame)
	Unlink frame's current key from its bucket chain before eviction.
static void	internal_index_push (cb_index_t *idx, uint32_t frame, cb_key_t key)
	Link frame into the bucket chain for key after a fresh insert.
static uint32_t	internal_replay_take_frame (const cache_policy_t *pol, cb_cache_t *cache, cb_index_t *idx, uint32_t *filled, cb_result_t *out)
	Pick the frame that receives key: a free frame while the cache fills, else the policy's victim (accounted + unlinked).
static size_t	internal_align_size (size_t value)
	Round a byte count to the next maximum fundamental alignment.
static bool	internal_size_multiply (size_t left, size_t right, size_t *result)
	Multiply byte factors without overflowing size_t.
size_t	cb_replay_workspace_required (const cache_policy_t *pol, uint32_t capacity)
	Return the exact caller workspace required by one replay.
static void *	internal_workspace_take (cb_workspace_t *workspace, size_t *used, size_t bytes)
static bool	internal_replay_open (cb_index_t *idx, cb_frame_t **frames, void **policy_data, const cache_policy_t *pol, uint32_t capacity, cb_workspace_t *workspace)
	Carve and initialize one replay's exact caller-owned storage.
static void	internal_replay_close (cb_index_t *idx, cb_frame_t *frames)
	End the borrowed workspace bindings made by internal_replay_open.
static int	internal_replay_stream (const cache_policy_t *pol, const cb_trace_t *trace, cb_cache_t *cache, cb_index_t *index, cb_result_t *out)
	Drive one resettable trace through an already-bound cache and index.
int	cb_replay (const cache_policy_t *pol, const cb_trace_t *trace, uint32_t capacity, cb_workspace_t *workspace, cb_result_t *out)
	Replay an access trace through one policy at a fixed capacity.

Detailed Description

#147 eviction-policy benchmark: the exact-accounting replay engine.

Replays one access trace through one registered cache_policy_t at one cache capacity. The resident-set lookup is an exact key->frame chained hash (one node per frame, no tombstones) so hit accounting is precise; only eviction ordering is delegated to the policy under test, and every byte of replay state is carved from a caller-owned workspace.

This unit is the replay ENGINE and carries no command line: the swept- capacity markdown report, the --sweep-block mode dispatch (see inc/sweep_block.h) and main live in src/cache_bench_report.c, which reaches the engine only through the public inc/cache_bench.h surface.

[Ring 7 / Tooling] {World: NS}

Copyright

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

Since

0.1.0

Definition in file cache_bench.c.

Enumeration Type Documentation

cb_hash_limit_t

enum cb_hash_limit_t : uint32_t

Enumerator
k_cb_max_hash_capacity	Largest safe fourfold hash input.

Definition at line 329 of file cache_bench.c.

cb_hash_mul_t

enum cb_hash_mul_t : uint64_t

Murmur3 finalizer constants used in internal_hash.

These are the canonical Murmur3 64-bit finalization mix constants (Austin Appleby, 2011). They are algorithm-specified bit patterns chosen for avalanche quality and must not be renamed to hide their origin; the typed enum documents that origin.

See also

https://github.com/aappleby/smhasher

Since

0.1.0

Enumerator
k_hash_mix_mul	Murmur3 64-bit finalizer multiplier.

Definition at line 69 of file cache_bench.c.

cb_hash_shift_t

enum cb_hash_shift_t : uint8_t

Murmur3 finalizer bit-shift amounts used in internal_hash.

The value 33 is mandated by the Murmur3 64-bit finalization algorithm. It must equal exactly 33 for the required avalanche properties; the typed enum documents this constraint.

Since

0.1.0

Enumerator
k_hash_shift	Murmur3 64-bit finalizer shift.

Definition at line 81 of file cache_bench.c.

Function Documentation

cb_replay()

int cb_replay	(	const cache_policy_t *	pol,
		const cb_trace_t *	trace,
		uint32_t	capacity,
		cb_workspace_t *	workspace,
		cb_result_t *	out )

Replay an access trace through one policy at a fixed capacity.

Drives trace through an exact resident-set hash while delegating only eviction ordering to pol: hits update recency/frequency via the policy callbacks, misses evict the policy's victim and load the new key into that frame. Fills out with hit/miss and worst-case scan accounting for one (policy, trace, capacity) sweep point.

Parameters

[in]	pol	Policy to exercise.
[in]	trace	Resettable access stream.
[in]	capacity	Frame count (the swept RAM budget).
[in,out]	workspace	Caller-provided exact replay storage.
[out]	out	Receives the metrics for this run.

Returns

int 0 on success, non-zero on capacity, source, or argument failure.

Return values

0	The replay completed and out holds the metrics.
1	A NULL/zero argument, policy bind, source, or workspace check failed.

Precondition

pol has pick_victim bound and trace is resettable.

out is non-NULL and writable.

Postcondition

On success, out->accesses == trace->n and hits do not exceed accesses.

No storage ownership changes; exact demand is recorded in workspace.

Note

Independent calls are safe when their traces and workspaces are distinct.

Since

0.1.0

Definition at line 523 of file cache_bench.c.

References cache_policy_t::deinit, cache_policy_t::init, internal_replay_close(), internal_replay_open(), internal_replay_stream(), cache_policy_t::state_base_bytes, and cache_policy_t::state_frame_bytes.

Referenced by internal_report_summary(), and internal_report_trace_row().

cb_replay_workspace_required()

size_t cb_replay_workspace_required	(	const cache_policy_t *	pol,
		uint32_t	capacity )

Return the exact caller workspace required by one replay.

Sums aligned frame, resident-index, link, and policy-state regions with overflow guards, without touching caller storage.

Parameters

[in]	pol	Policy whose private state is included.
[in]	capacity	Frame count.

Returns

Exact bytes, or zero for invalid/overflowing input.

Return values

0	A policy/capacity check or size calculation failed.
other	Exact aligned workspace bytes required by cb_replay.

Precondition

pol is NULL or points to readable policy geometry.

capacity is an intended fixed cache-frame count.

Postcondition

A non-zero result covers every replay workspace region.

No policy or caller storage is modified.

Note

Thread-safe: this function reads immutable policy geometry only.

Since

0.1.0

Definition at line 333 of file cache_bench.c.

References internal_align_size(), internal_pow2_ceil(), internal_size_multiply(), k_cb_max_hash_capacity, cache_policy_t::state_base_bytes, and cache_policy_t::state_frame_bytes.

Referenced by internal_replay_open().

internal_align_size()

size_t internal_align_size ( size_t value )

static

Round a byte count to the next maximum fundamental alignment.

Adds the alignment-minus-one bias with an overflow guard, then clears the low bits required by ::max_align_t.

Parameters

[in]

value

Unaligned byte count.

Returns

The aligned byte count, or zero when rounding would overflow.

Return values

0	value cannot be represented after alignment.
other	Smallest aligned byte count not less than value.

Precondition

alignof(max_align_t) is a non-zero power of two.

value is an ordinary object-size request.

Postcondition

A non-zero result is a multiple of alignof(max_align_t).

No storage is read or modified.

Note

Thread-safe: this is a pure arithmetic helper.

Since

0.1.0

Definition at line 293 of file cache_bench.c.

Referenced by cb_replay_workspace_required(), and internal_workspace_take().

internal_hash()

uint32_t internal_hash ( cb_key_t k )

static

Mix an (object,page) key into a 32-bit hash for bucket selection.

Packs k as (object_id << 32) | page and runs the canonical Murmur3 64-bit finalizer (k_hash_mix_mul, k_hash_shift) for avalanche, returning the low 32 bits. The caller masks the result with the (power-of-two) bucket count.

Parameters

[in]

k

The (object_id, page) key to hash (taken by value).

Returns

uint32_t The low 32 bits of the finalized hash.

Return values

0	Possible for some keys (0 is a valid bucket seed).
other	The mixed hash for k.

Precondition

k_hash_shift equals 33 (the Murmur3 finalizer shift).

Called on the single benchmark thread.

Postcondition

The same k always maps to the same value within a run.

No global or heap state is modified.

Note

Thread-safe: a pure function of k.

Since

0.1.0

Definition at line 103 of file cache_bench.c.

References k_hash_mix_mul, k_hash_shift, cb_key_t::object_id, and cb_key_t::page.

Referenced by internal_index_push(), and internal_index_remove().

internal_index_find()

int32_t internal_index_find ( const cb_index_t * idx, const cb_frame_t * frames, cb_key_t key )

static

Find the resident frame currently holding key, or -1.

Walks the bucket chain at hash(key) & mask, confirming each candidate with internal_key_eq, and returns the matching frame index. A -1 result is a cache miss; the harness then loads key.

Parameters

[in]	idx	Resident-set index (buckets + per-frame chain links).
[in]	frames	Frame array the chain indexes into.
[in]	key	The (object, page) key to look up.

Returns

int32_t The resident frame index, or -1 when key is absent.

Return values

-1	key is not resident (a miss).
other	The index of the frame holding key (a hit).

Precondition

idx was populated by internal_replay_open and the insert path.

frames has at least capacity initialized entries.

Postcondition

Neither idx nor frames is modified (pure read).

A non-negative result indexes a live frame whose key equals key.

Note

Not thread-safe: concurrent inserts would race the chain walk.

Since

0.1.0

Definition at line 168 of file cache_bench.c.

References cb_index_t::bucket, internal_hash(), internal_key_eq(), cb_index_t::mask, and cb_index_t::next.

Referenced by internal_replay_stream().

internal_index_push()

void internal_index_push ( cb_index_t * idx, uint32_t frame, cb_key_t key )

static

Link frame into the bucket chain for key after a fresh insert.

Prepends the frame to the chain at hash(key) & mask (an O(1) head insert), making key findable by internal_index_find. Pairs with internal_index_remove on the eviction path.

Parameters

[in,out]	idx	Resident-set index whose chain is extended.
[in]	frame	Index of the frame now holding key.
[in]	key	The key just written into that frame.

Precondition

frame is not currently linked in any chain.

frame is a valid index < capacity.

Postcondition

key is findable and resolves to frame.

Only the target bucket chain grows by one node.

Note

Not thread-safe: mutates the shared chain. Call on the benchmark thread.

Since

0.1.0

Definition at line 227 of file cache_bench.c.

References cb_index_t::bucket, internal_hash(), cb_index_t::mask, and cb_index_t::next.

Referenced by internal_replay_stream().

internal_index_remove()

void internal_index_remove ( cb_index_t * idx, const cb_frame_t * frames, uint32_t frame )

static

Unlink frame's current key from its bucket chain before eviction.

Recomputes the bucket from the frame's resident key and splices the frame out of that singly-linked chain (updating the bucket head or the predecessor's link). Must run before the frame is repopulated so the stale key stops being findable.

Parameters

[in,out]	idx	Resident-set index whose chain is edited.
[in]	frames	Frame array (read for the victim's current key).
[in]	frame	Index of the frame being evicted.

Precondition

frame is currently linked under hash(frames[frame].key).

frame is a valid index < capacity.

Postcondition

frame no longer appears in any bucket chain.

Only the affected bucket chain is altered; frames is unchanged.

Note

Not thread-safe: mutates the shared chain. Call on the benchmark thread.

Since

0.1.0

Definition at line 195 of file cache_bench.c.

References cb_index_t::bucket, internal_hash(), cb_index_t::mask, and cb_index_t::next.

Referenced by internal_replay_take_frame().

internal_key_eq()

bool internal_key_eq ( cb_key_t a, cb_key_t b )

static

Report whether two cache keys name the same (object, page).

Compares both fields; equal hashes are necessary but not sufficient, so the chained-hash lookup calls this to confirm a bucket match is a true key match (no tombstones, so hit accounting stays exact).

Parameters

[in]	a	First key (by value).
[in]	b	Second key (by value).

Returns

bool true when both fields are equal, false otherwise.

Return values

true	a and b have equal object_id and page.
false	The keys differ in at least one field.

Precondition

a and b are fully initialized keys.

Called on the single benchmark thread.

Postcondition

Neither argument is modified.

The comparison is symmetric: eq(a,b) == eq(b,a).

Note

Thread-safe: a pure comparison of its arguments.

Since

0.1.0

Definition at line 130 of file cache_bench.c.

References cb_key_t::object_id, and cb_key_t::page.

Referenced by internal_index_find().

internal_pow2_ceil()

uint32_t internal_pow2_ceil ( uint32_t v )

static

Round v up to a power of two (>= 1).

Starts at 1 and left-shifts until the running value reaches or exceeds v, yielding the smallest power of two not less than v. Used to size the resident-set hash table at four buckets per frame so bucket masking is a single AND.

Parameters

[in]

v

Target to round up; both 0 and 1 map to 1.

Returns

uint32_t The smallest power of two that is >= v (never 0).

Return values

1	v was 0 or 1.
other	The next power of two at or above v.

Precondition

v <= 2^31 so the next power of two is representable in 32 bits.

Called on the single benchmark thread.

Postcondition

The result is an exact power of two.

The result is >= v and >= 1; no shared state is touched.

Note

Thread-safe: a pure function of v with no shared state.

Since

0.1.0

Definition at line 50 of file cache_bench.c.

Referenced by cb_replay_workspace_required(), and internal_replay_open().

internal_replay_close()

void internal_replay_close ( cb_index_t * idx, cb_frame_t * frames )

static

End the borrowed workspace bindings made by internal_replay_open.

Zeroes the borrowed index binding. The workspace itself remains caller-owned and immediately reusable on every replay exit path.

Parameters

[in,out]	idx	Index whose borrowed pointers are zeroed.
[in]	frames	Borrowed frame array (NULL tolerated).

Precondition

idx is non-NULL (its buffers may individually be NULL).

Any non-NULL pointers came from internal_replay_open.

Postcondition

idx is all-zero; caller-owned bytes remain available for reuse.

frames is not accessed or modified.

Note

Thread-safe for distinct caller-owned bindings.

Since

0.1.0

Definition at line 457 of file cache_bench.c.

Referenced by cb_replay().

internal_replay_open()

bool internal_replay_open ( cb_index_t * idx, cb_frame_t ** frames, void ** policy_data, const cache_policy_t * pol, uint32_t capacity, cb_workspace_t * workspace )

static

Carve and initialize one replay's exact caller-owned storage.

Validates the aligned workspace capacity, partitions it into frame, hash, link, and policy regions, then initializes every borrowed binding without acquiring ownership.

Parameters

[out]	idx	Receives the resident-index binding.
[out]	frames	Receives the frame-array binding.
[out]	policy_data	Receives the policy-state binding.
[in]	pol	Policy whose storage geometry is applied.
[in]	capacity	Number of cache frames.
[in,out]	workspace	Caller-owned aligned workspace and diagnostics.

Returns

Whether every required region was bound and initialized.

Return values

true	All output bindings are valid for one replay.
false	An argument, alignment, overflow, or capacity check failed.

Precondition

idx, frames, policy_data, and workspace are writable.

pol and capacity satisfy cb_replay_workspace_required.

Postcondition

workspace->required records the exact request on every path.

On success, frames and policy bytes are zeroed and index buckets are empty.

Note

Thread-safe for distinct caller-owned workspaces.

Since

0.1.0

Definition at line 401 of file cache_bench.c.

References cb_index_t::bucket, cb_workspace_t::capacity, cb_replay_workspace_required(), cb_workspace_t::data, cb_workspace_t::high_water, internal_pow2_ceil(), internal_workspace_take(), cb_index_t::mask, memset(), cb_index_t::next, cb_workspace_t::required, cache_policy_t::state_base_bytes, and cache_policy_t::state_frame_bytes.

Referenced by cb_replay().

internal_replay_stream()

int internal_replay_stream ( const cache_policy_t * pol, const cb_trace_t * trace, cb_cache_t * cache, cb_index_t * index, cb_result_t * out )

static

Drive one resettable trace through an already-bound cache and index.

Opens an independent cursor, accounts hits directly, and delegates miss-victim ordering to pol while maintaining the exact index.

Parameters

[in]	pol	Bound replacement policy.
[in]	trace	Immutable resettable trace.
[in,out]	cache	Initialized cache binding.
[in,out]	index	Initialized resident index.
[out]	out	Receives replay counters.

Returns

Zero on a complete stable replay, otherwise one.

Return values

0	Every key was replayed and the captured source remained stable.
1	Cursor I/O, parser, or stability validation failed.

Precondition

All pointers are non-NULL and cache is initialized for pol.

index indexes the same frame array held by cache.

Postcondition

On success, out->accesses equals the emitted trace count.

No ownership changes occur; cache and index remain caller-bound.

Note

Not thread-safe when bindings are shared.

Since

0.1.0

Definition at line 483 of file cache_bench.c.

References cb_result_t::accesses, cb_trace_cursor_finish(), cb_trace_cursor_next(), cb_trace_cursor_open(), cb_cache_t::frames, cb_result_t::hits, internal_index_find(), internal_index_push(), internal_replay_take_frame(), k_cb_io_ok, cb_frame_t::key, cb_frame_t::live, cache_policy_t::on_access, and cache_policy_t::on_insert.

Referenced by cb_replay().

internal_replay_take_frame()

uint32_t internal_replay_take_frame ( const cache_policy_t * pol, cb_cache_t * cache, cb_index_t * idx, uint32_t * filled, cb_result_t * out )

static

Pick the frame that receives key: a free frame while the cache fills, else the policy's victim (accounted + unlinked).

Charges eviction stats (count, total/worst scan) to out and unlinks an evicted frame's old key from the index, so the caller only relinks the new key.

Parameters

[in]	pol	Policy under test (its pick_victim may run).
[in,out]	cache	The frame cache (frames + policy state).
[in,out]	idx	Resident-set index (victim unlinked in place).
[in,out]	filled	Frames used so far; grows while cold.
[in,out]	out	Metrics row receiving eviction accounting.

Returns

uint32_t Frame index to (re)populate (always < capacity).

Return values

<capacity

Always: a still-free frame while cold, else the victim.

Precondition

The cache is missing the current key (lookup already failed).

pol->pick_victim is bound (every registered policy binds it).

Postcondition

On the eviction path, the victim's old key is no longer findable.

*filled <= cache->capacity.

Note

Not thread-safe.

Since

0.1.0

Definition at line 255 of file cache_bench.c.

References cb_result_t::evictions, cb_cache_t::frames, internal_index_remove(), cache_policy_t::pick_victim, cb_result_t::total_scan, and cb_result_t::worst_scan.

Referenced by internal_replay_stream().

internal_size_multiply()

bool internal_size_multiply ( size_t left, size_t right, size_t * result )

static

Multiply byte factors without overflowing size_t.

Checks the division bound before evaluating the product so caller sizing cannot wrap to a smaller workspace request.

Parameters

[in]	left	First factor.
[in]	right	Second factor.
[out]	result	Receives the product on success.

Returns

Whether the product was written.

Return values

true	result contains left * right.
false	result is NULL or the product would overflow.

Precondition

left and right describe byte-count factors.

result is NULL or points to writable size_t storage.

Postcondition

On success, result contains the exact mathematical product.

On failure, result is not modified.

Note

Thread-safe for distinct result bindings.

Since

0.1.0

Definition at line 320 of file cache_bench.c.

Referenced by cb_replay_workspace_required().

internal_workspace_take()

void * internal_workspace_take ( cb_workspace_t * workspace, size_t * used, size_t bytes )

static

Definition at line 368 of file cache_bench.c.

References cb_workspace_t::capacity, cb_workspace_t::data, and internal_align_size().

Referenced by internal_replay_open().