The one reusable hash + pin + evict cache engine (#147, #345). More...

#include <stdint.h>
#include "ra8_err.h"

Include dependency graph for ra8_keycache.h:

This graph shows which files directly or indirectly include this file:

Data Structures
struct	ra8_keycache_cell_t
	Per-cell link metadata (one caller-owned array entry per cell). More...
struct	ra8_keycache_cfg_t
	Caller-supplied storage + policy + renderer for ra8_keycache_init. More...
struct	ra8_keycache_t
	Cache engine state (caller-owned; treat as private). More...
struct	ra8_keycache_view_t
	A pinned view of a cached cell returned by ra8_keycache_get. More...

Typedefs
typedef uint32_t(*	ra8_keycache_hash_fn) (const void key, uint32_t key_bytes, void ctx)
	Hash a key blob to a raw 32-bit value (the engine folds to a bucket).
typedef ra8_err_t(*	ra8_keycache_render_fn) (void ctx, const void key, uint8_t cell, uint32_t cell_bytes, void user)
	Fill a cell with the rendered bytes for `key` (render-on-miss seam).

Enumerations
enum	ra8_keycache_evict_t : uint8_t { k_ra8_keycache_evict_lru = 0U , k_ra8_keycache_evict_slru = 1U }
	Eviction policy selected in ra8_keycache_cfg_t::evict. More...

Functions
ra8_err_t	ra8_keycache_init (ra8_keycache_t kc, const ra8_keycache_cfg_t cfg)
	Initialise a cache engine over caller-supplied storage.
ra8_err_t	ra8_keycache_get (ra8_keycache_t kc, const void key, ra8_keycache_view_t *out_view)
	Get (and pin) the cell for `key`, rendering it on a miss.
ra8_err_t	ra8_keycache_prefetch (ra8_keycache_t kc, const void key)
	Warm the cell for `key` into the cache without holding a pin.
ra8_err_t	ra8_keycache_put (ra8_keycache_t kc, const uint8_t data)
	Release one pin on a cell previously returned by ra8_keycache_get.
ra8_err_t	ra8_keycache_stats (const ra8_keycache_t kc, uint32_t out_hits, uint32_t out_misses, uint32_t out_evictions)
	Report the cache hit / miss / eviction counters.

Detailed Description

The one reusable hash + pin + evict cache engine (#147, #345).

Tag: [Ring 2 / Core] {World: NS}

The single hash + pin + evict engine every reader cache is built on. #345 folded ::ra8_vmem's once-duplicate SLRU/hash/pin machinery into this one implementation, so the eviction policy is now a config choice rather than a second copy of the code. A keycache maps a fixed-size opaque key to a fixed-size opaque cell of filled bytes: a hit returns a pinned view of the cell; a miss evicts an unpinned victim, fills the cell through a caller-supplied render-on-miss callback, inserts it, and pins it. The caller releases the pin with ra8_keycache_put once it is done reading the cell.

Selectable eviction policy (cfg.evict)

The victim is always an unpinned cell (pinned cells are skipped); which one depends on the policy the caller selects:

LRU (k_ra8_keycache_evict_lru, the default). A single recency list: the victim is the least-recently-used unpinned cell. Right for caches with strong per-entry reuse locality and no linear-scan floods – the glyph atlas (::ra8_glyph_atlas) and the image-tile cache (::ra8_tile_cache), whose on-screen working set is re-touched every frame.
SLRU / 2Q (k_ra8_keycache_evict_slru). Two segments – a probationary scan absorber and a protected hot set (cfg.protected_pct, 0 selects 75%). Cold cells enter probation; a re-reference promotes to protected (demoting the protected LRU back to probation when it is full); the victim is the probationary LRU first, then the protected LRU. This is the only scan-resistant policy with deterministic O(1) (WCET = 1) victim selection: a page-turn flood ages out in probation without evicting the hot set. The byte-range page cache (::ra8_vmem) selects it, so a linear file scan does not thrash re-read metadata.

The policy changes which cell is evicted, never how many are resident: the bounded-RAM guarantee (residency <= cell_count) holds at every setting.

Keys and hashing

Keys are compared byte-wise (memcmp over key_bytes), so a key struct must be fully initialised (zero-filled, no indeterminate padding) before use. The hash is injectable (cfg.hash, cfg.hash_ctx); a NULL hash selects the built-in FNV-1a over the key bytes. A facade whose key carries structure (::ra8_vmem hashes on the derived page number) supplies its own; the folding to [0, bucket_count) is always the engine's, so the hash callback returns a raw 32-bit value.

Per-cell user descriptor (user_bytes, may be 0)

The render callback writes per-entry metadata there (e.g. the rendered glyph or tile width/height) and ra8_keycache_get hands the descriptor back alongside the cell data. This is how a typed facade (::ra8_glyph_atlas, ::ra8_tile_cache) recovers its dimensions without a parallel side table.

Zero allocation (NASA P10 Rule 3): the caller provides every array – the cell storage, the key storage, the optional user-descriptor storage, the per-cell link metadata, and the hash buckets – carved once from a tier ::ra8_arena / ::ra8_slab at init (hot tier = SRAM/DTCM).

Note: Not thread-safe; the renderer and the cache are single-threaded.

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

Since: 0.1.0

Definition in file ra8_keycache.h.

Typedef Documentation

◆ ra8_keycache_hash_fn

typedef uint32_t(* ra8_keycache_hash_fn) (const void *key, uint32_t key_bytes, void *ctx)

Hash a key blob to a raw 32-bit value (the engine folds to a bucket).

Called on every lookup, insert, and evict to place a key in a hash bucket. Returns a raw 32-bit hash; the engine reduces it to [0, bucket_count). A NULL callback in the config selects the built-in FNV-1a over the key_bytes. Must be a pure function of the key bytes (and any immutable ctx) so a stored key rehashes to the same bucket it was inserted under.

Parameters

[in]	key	The key_bytes-wide key blob to hash.
[in]	key_bytes	Key width in bytes.
[in]	ctx	Opaque context (hash_ctx from the config), or NULL.

Returns: A raw 32-bit hash of the key.

Since: 0.1.0

Definition at line 119 of file ra8_keycache.h.

◆ ra8_keycache_render_fn

typedef ra8_err_t(* ra8_keycache_render_fn) (void *ctx, const void *key, uint8_t *cell, uint32_t cell_bytes, void *user)

Fill a cell with the rendered bytes for key (render-on-miss seam).

Called on a cache miss to populate cell with the content keyed by key, and (when the cache has a user descriptor) to write that entry's metadata into user. The glyph atlas rasterises a glyph here; the tile cache decodes an image tile; ::ra8_vmem loads a page; tests use a synthetic generator.

Parameters

[in]	ctx	Opaque render context (render_ctx from the config).
[in]	key	The key_bytes-wide key being filled.
[out]	cell	Destination cell buffer (cell_bytes writable).
[in]	cell_bytes	Cell capacity in bytes.
[out]	user	Per-cell user descriptor (user_bytes), or NULL when the cache was configured with user_bytes == 0.

Returns: ra8_err_t k_ra8_ok on success; any error aborts the get with that code and leaves the victim cell cold (no stale entry survives).

Since: 0.1.0

Definition at line 143 of file ra8_keycache.h.

Enumeration Type Documentation

◆ ra8_keycache_evict_t

enum ra8_keycache_evict_t : uint8_t

Eviction policy selected in ra8_keycache_cfg_t::evict.

Chooses how the engine orders victims. LRU keeps a single recency list; SLRU keeps a probationary + protected pair for scan resistance. Both skip pinned cells and both guarantee residency <= cell_count.

Invariant: The two policies share every other config field; only the on-access promotion and the victim scan differ.

See also: ra8_keycache_cfg_t::protected_pct Sizes the SLRU protected segment.

Since: 0.1.0

Enumerator
k_ra8_keycache_evict_lru	Single-list LRU (the default when 0).
k_ra8_keycache_evict_slru	Segmented LRU / 2Q (scan-resistant).

Definition at line 95 of file ra8_keycache.h.

Function Documentation

◆ ra8_keycache_get()

ra8_err_t ra8_keycache_get	(	ra8_keycache_t *	kc,
		const void *	key,
		ra8_keycache_view_t *	out_view )

nodiscard

Get (and pin) the cell for key, rendering it on a miss.

On a hit the cell is re-referenced (LRU: moved to the MRU; SLRU: promoted toward the protected segment) and pinned. On a miss an unpinned victim is evicted (LRU: the LRU cell; SLRU: the probationary LRU first, then the protected LRU), the cell is filled through the configured render callback, inserted, and pinned. The returned view stays valid until ra8_keycache_put.

Parameters

[in]	kc	Initialised cache.
[in]	key	key_bytes-wide key to fetch (fully initialised).
[out]	out_view	Receives the pinned cell view.

Returns: ra8_err_t Error code.

Return values

k_ra8_ok	Cell resident and pinned; *out_view set.
k_ra8_err_null_ptr	kc, key, or out_view was NULL.
k_ra8_err_no_mem	Every cell is pinned (cannot evict for the miss).
k_ra8_err_*	The render callback failed (returned verbatim).

Precondition: kc was populated by ra8_keycache_init.; The caller will ra8_keycache_put the returned cell.

Postcondition: On success the cell's pin count increased by one.; On any non-ok return no new pin is held.

Note: Not thread-safe.

Since: 0.1.0

Definition at line 865 of file ra8_keycache.c.

References ra8_keycache_t::cfg, ra8_keycache_t::hits, internal_access(), internal_cell_ptr(), internal_hash_lookup(), internal_miss(), internal_user_ptr(), k_ra8_ok, ra8_keycache_cfg_t::meta, ra8_keycache_t::misses, ra8_keycache_cell_t::pin_count, RA8_CHECK_NULL_PTR, and s_tag.

Referenced by ra8_glyph_atlas_get(), ra8_keycache_prefetch(), ra8_tile_cache_get(), and ra8_vmem_get().

◆ ra8_keycache_init()

ra8_err_t ra8_keycache_init	(	ra8_keycache_t *	kc,
		const ra8_keycache_cfg_t *	cfg )

nodiscard

Initialise a cache engine over caller-supplied storage.

Parameters

[out]	kc	Cache state to populate (zero-initialised by the caller).
[in]	cfg	Storage + policy + renderer configuration (see ra8_keycache_cfg_t).

Returns: ra8_err_t Error code.

Return values

k_ra8_ok	Cache ready; all cells cold.
k_ra8_err_null_ptr	kc, cfg, or a required cfg pointer is NULL.
k_ra8_err_invalid_size	cell_count, cell_bytes, key_bytes, or bucket_count was zero.
k_ra8_err_invalid_arg	cfg->protected_pct exceeds 100 (SLRU).

Precondition: cfg's arrays cover their declared sizes and out-live the cache.; cfg->render is non-NULL, and cfg->user_mem is non-NULL when cfg->user_bytes > 0.

Postcondition: On success the cache is empty and the buckets are cleared.; On any non-ok return kc is left unbound.

Note: Not thread-safe.

Since: 0.1.0

Definition at line 778 of file ra8_keycache.c.

References ra8_keycache_cfg_t::evict, internal_protected_cap(), internal_seed_cells(), internal_validate_cfg_policy(), internal_validate_cfg_ptrs(), internal_validate_cfg_sizes(), k_ra8_keycache_evict_slru, k_ra8_ok, ra8_keycache_t::protected_cap, RA8_CHECK_NULL_PTR, and s_tag.

Referenced by ra8_glyph_atlas_init(), ra8_tile_cache_init(), and ra8_vmem_init().

◆ ra8_keycache_prefetch()

ra8_err_t ra8_keycache_prefetch	(	ra8_keycache_t *	kc,
		const void *	key )

nodiscard

Warm the cell for key into the cache without holding a pin.

The read-ahead / prefetch primitive: a ra8_keycache_get immediately followed by a ra8_keycache_put, so on return the cell is resident but unpinned (evictable). A hit is a no-op refresh; a miss renders the cell through the configured callback and inserts it. Warming changes only residency – never the bytes a later ra8_keycache_get returns – so it is transparent to the caller. This is the image-tile analogue of ra8_vmem_prefetch (which warms a page-cache frame). The cell is inserted at the MRU (single-list LRU), so a wrong read-ahead guess can age out hot data before itself; the scan-resistant probationary insert is tracked by the cache-consolidation work (#345).

Parameters

[in,out]	kc	Initialised cache.
[in]	key	key_bytes-wide key to warm (fully initialised).

Returns: ra8_err_t Error code.

Return values

k_ra8_ok	The cell is resident and unpinned (warmed or hit).
k_ra8_err_null_ptr	kc or key was NULL.
k_ra8_err_no_mem	Every cell is pinned (cannot evict to warm).
k_ra8_err_*	The render callback failed (returned verbatim).

Precondition: kc was populated by ra8_keycache_init.; key is fully initialised (no indeterminate padding bytes).

Postcondition: On success the entry is resident with pin count zero.; On any non-ok return no pin is held and no entry was warmed.

Note: Not thread-safe. Single-threaded read-ahead only.; A warmed-but-unused cell is evicted before any pinned cell.

See also: ra8_keycache_get()

Since: 0.1.0

Definition at line 883 of file ra8_keycache.c.

References ra8_keycache_view_t::data, k_ra8_ok, RA8_CHECK_NULL_PTR, ra8_keycache_get(), ra8_keycache_put(), and s_tag.

Referenced by ra8_tile_cache_prefetch().

◆ ra8_keycache_put()

ra8_err_t ra8_keycache_put	(	ra8_keycache_t *	kc,
		const uint8_t *	data )

nodiscard

Release one pin on a cell previously returned by ra8_keycache_get.

Parameters

[in]	kc	Initialised cache.
[in]	data	The data pointer from a returned ra8_keycache_view_t.

Returns: ra8_err_t Error code.

Return values

k_ra8_ok	Pin released.
k_ra8_err_null_ptr	kc or data was NULL.
k_ra8_err_invalid_arg	data is not a cell of this cache, or the cell was not pinned.

Precondition: data came from ra8_keycache_get on this cache and is still pinned.; kc was populated by ra8_keycache_init.

Postcondition: On success the cell's pin count decreased by one.; On any non-ok return no state changed.

Note: Not thread-safe.

Since: 0.1.0

Definition at line 897 of file ra8_keycache.c.

References ra8_keycache_cfg_t::cell_bytes, ra8_keycache_cfg_t::cell_count, ra8_keycache_cfg_t::cell_mem, ra8_keycache_t::cfg, k_ra8_err_invalid_arg, k_ra8_ok, ra8_keycache_cfg_t::meta, ra8_keycache_cell_t::pin_count, RA8_CHECK_NULL_PTR, and s_tag.

Referenced by ra8_glyph_atlas_put(), ra8_keycache_prefetch(), ra8_tile_cache_put(), and ra8_vmem_put().

◆ ra8_keycache_stats()

ra8_err_t ra8_keycache_stats	(	const ra8_keycache_t *	kc,
		uint32_t *	out_hits,
		uint32_t *	out_misses,
		uint32_t *	out_evictions )

nodiscard

Report the cache hit / miss / eviction counters.

Parameters

[in]	kc	Initialised cache.
[out]	out_hits	Hits so far (may be NULL).
[out]	out_misses	Misses so far (may be NULL).
[out]	out_evictions	Evictions so far (may be NULL).

Returns: ra8_err_t Error code.

Return values

k_ra8_ok	Counters reported.
k_ra8_err_null_ptr	kc was NULL.
k_ra8_err_invalid_state	The cache was not initialised.

Precondition: kc was populated by ra8_keycache_init.; At least one output pointer is non-NULL to be useful.

Postcondition: On success the requested counters are written.; No cache state is mutated.

Note: Thread-safe with respect to a quiescent cache (pure read).

Since: 0.1.0

Definition at line 922 of file ra8_keycache.c.

References ra8_keycache_cfg_t::cell_mem, ra8_keycache_t::cfg, ra8_keycache_t::evictions, ra8_keycache_t::hits, k_ra8_err_invalid_state, k_ra8_ok, ra8_keycache_t::misses, RA8_CHECK_NULL_PTR, and s_tag.

Referenced by ra8_glyph_atlas_stats(), ra8_tile_cache_stats(), and ra8_vmem_stats().

Data Structures

Typedefs

Enumerations

Functions

Detailed Description

Selectable eviction policy (cfg.evict)

Keys and hashing

Per-cell user descriptor (user_bytes, may be 0)

Typedef Documentation

◆ ra8_keycache_hash_fn

◆ ra8_keycache_render_fn

Enumeration Type Documentation

◆ ra8_keycache_evict_t

Function Documentation

◆ ra8_keycache_get()

◆ ra8_keycache_init()

◆ ra8_keycache_prefetch()

◆ ra8_keycache_put()

◆ ra8_keycache_stats()