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

#include "ra8_keycache.h"
#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include "ra8_attributes.h"
#include "ra8_check.h"
#include "ra8_err.h"

Include dependency graph for ra8_keycache.c:

Enumerations
enum	ra8_keycache_const_t : uint32_t { k_keycache_fnv_offset = 2166136261U , k_keycache_fnv_prime = 16777619U , k_keycache_protected_pct_def = 75U , k_keycache_percent_full = 100U }
	Hashing constants and the SLRU split defaults / bounds. More...
enum	ra8_keycache_seg_t : uint8_t { k_keycache_seg_probation = 0U , k_keycache_seg_protected = 1U }
	SLRU segment tags stored in ra8_keycache_cell_t::seg. More...

Functions
static uint8_t *	internal_cell_ptr (const ra8_keycache_t *kc, uint32_t idx)
	Cell payload pointer for cell `idx`.
static uint8_t *	internal_key_ptr (const ra8_keycache_t *kc, uint32_t idx)
	Key-storage pointer for cell `idx`.
static void *	internal_user_ptr (const ra8_keycache_t *kc, uint32_t idx)
	User-descriptor pointer for cell `idx`, or NULL when unused.
static bool	internal_key_eq (const ra8_keycache_t kc, const void a, const void *b)
	Byte-wise key equality over key_bytes.
static uint32_t	internal_fnv1a (const void *key, uint32_t key_bytes)
	FNV-1a hash of a key blob (the built-in default hash).
static uint32_t	internal_hash (const ra8_keycache_t kc, const void key)
	Hash a key blob into a bucket index using the configured policy.
static void	internal_unlink (ra8_keycache_t kc, int32_t f, int32_t head, int32_t *tail)
	Detach cell `f` from the recency list owned by `head` / `tail`.
static void	internal_push_head (ra8_keycache_t kc, int32_t f, int32_t head, int32_t *tail)
	Push cell `f` onto the MRU head of a recency list.
static void	internal_hash_insert (ra8_keycache_t *kc, int32_t f)
	Insert cell `f` into its hash bucket chain.
static void	internal_hash_remove (ra8_keycache_t *kc, int32_t f)
	Remove cell `f` from its hash bucket chain.
static int32_t	internal_hash_lookup (const ra8_keycache_t kc, const void key)
	Find the valid cell holding `key`, or -1.
static int32_t	internal_first_unpinned (const ra8_keycache_t *kc, int32_t tail)
	Find the first unpinned cell walking from `tail` toward the MRU.
static int32_t	internal_pick_victim (const ra8_keycache_t *kc)
	Select an evictable victim: probationary LRU first, then protected LRU.
static void	internal_slru_access (ra8_keycache_t *kc, int32_t f)
	SLRU re-reference: promote / refresh cell `f` on a hit.
static void	internal_access (ra8_keycache_t *kc, int32_t f)
	Re-reference cell `f` on a hit under the configured policy.
static ra8_err_t	internal_validate_cfg_ptrs (const ra8_keycache_cfg_t *cfg)
	Validate that every required config pointer is non-NULL.
static ra8_err_t	internal_validate_cfg_sizes (const ra8_keycache_cfg_t *cfg)
	Validate that every config sizing field is non-zero.
static ra8_err_t	internal_validate_cfg_policy (const ra8_keycache_cfg_t *cfg)
	Validate the SLRU split knob when the SLRU policy is selected.
static uint32_t	internal_protected_cap (const ra8_keycache_cfg_t *cfg)
	Resolve the SLRU protected-segment capacity, in cells.
static void	internal_seed_cells (ra8_keycache_t kc, const ra8_keycache_cfg_t cfg)
	Seed a validated cache: clear buckets and link every cell cold.
ra8_err_t	ra8_keycache_init (ra8_keycache_t kc, const ra8_keycache_cfg_t cfg)
	Initialise a cache engine over caller-supplied storage.
static ra8_err_t	internal_miss (ra8_keycache_t kc, const void key, ra8_keycache_view_t *out_view)
	Handle a get miss: evict a victim, render the cell, insert + pin it.
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.

Variables
static const char *const	s_tag = "ra8_keycache"
	Module log tag.

Detailed Description

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

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

One keyed cache engine over fixed cells, selectable between plain LRU (a single recency list) and scan-resistant SLRU / 2Q (a probationary + protected pair). #345 folded ::ra8_vmem's once-duplicate machinery in here: the two policies now share one set of list, hash-chain, pin, and victim-selection primitives and differ only in the on-access promotion and the victim scan order. All cells start invalid in the probationary list, so cold misses and real evictions share one victim path; victim selection is read-only and skips pinned cells. Keys are stored out-of-line in a caller-supplied array and compared byte-wise; the hash is injectable (NULL selects FNV-1a); an optional per-cell user descriptor lets a typed facade recover its dimensions.

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

Definition in file ra8_keycache.c.

Enumeration Type Documentation

◆ ra8_keycache_const_t

enum ra8_keycache_const_t : uint32_t

Hashing constants and the SLRU split defaults / bounds.

Since: 0.1.0

Enumerator
k_keycache_fnv_offset	FNV-1a 32-bit offset basis.
k_keycache_fnv_prime	FNV-1a 32-bit prime.
k_keycache_protected_pct_def	Default SLRU protected share.
k_keycache_percent_full	Percent denominator / max split.

Definition at line 43 of file ra8_keycache.c.

◆ ra8_keycache_seg_t

enum ra8_keycache_seg_t : uint8_t

SLRU segment tags stored in ra8_keycache_cell_t::seg.

Under LRU every cell stays k_keycache_seg_probation and the tag is never consulted.

Since: 0.1.0

Enumerator
k_keycache_seg_probation	Probationary segment (scan absorber).
k_keycache_seg_protected	Protected segment (hot working set).

Definition at line 59 of file ra8_keycache.c.

Function Documentation

◆ internal_access()

void internal_access	(	ra8_keycache_t *	kc,
		int32_t	f )

static

Re-reference cell f on a hit under the configured policy.

LRU moves f to the single list's MRU; SLRU runs internal_slru_access to promote it toward the protected segment.

Parameters

[in,out]	kc	Cache providing the policy + segment lists.
[in]	f	Cell index just accessed.

Returns: Nothing.

Precondition: f is a valid, currently-linked cell.; kc is non-NULL with a populated config.

Postcondition: f is at the MRU of its (possibly new) segment.; The recency order otherwise reflects the access.

Note: Not thread-safe.

MC/DC:

Decision: if (kc->cfg.evict == k_ra8_keycache_evict_slru) (1 condition, no compound &&/||).

evict == SLRU -> internal_slru_access (exercised by the ::ra8_vmem tests).
evict == LRU -> single-list move-to-front (glyph/tile atlases + tests).

Since: 0.1.0

Definition at line 572 of file ra8_keycache.c.

References ra8_keycache_t::cfg, ra8_keycache_cfg_t::evict, internal_push_head(), internal_slru_access(), internal_unlink(), k_ra8_keycache_evict_slru, ra8_keycache_t::pb_head, ra8_keycache_t::pb_tail, and RA8_INTERNAL.

Referenced by ra8_keycache_get().

◆ internal_cell_ptr()

uint8_t * internal_cell_ptr	(	const ra8_keycache_t *	kc,
		uint32_t	idx )

static

Cell payload pointer for cell idx.

Indexes the contiguous cell storage by idx * cell_bytes.

Parameters

[in]	kc	Cache providing the cell storage + stride.
[in]	idx	Cell index in [0, cell_count).

Returns: Pointer to the start of cell idx's payload.

Return values

non-NULL Always (the storage pointer offset by the stride).

Precondition: kc is non-NULL with a populated config.; idx < cfg.cell_count.

Postcondition: No state is modified.; The result lies within the cell storage region.

Note: Pure; thread-safe.

Since: 0.1.0

Definition at line 84 of file ra8_keycache.c.

References ra8_keycache_cfg_t::cell_bytes, ra8_keycache_cfg_t::cell_mem, ra8_keycache_t::cfg, and RA8_INTERNAL.

Referenced by internal_miss(), and ra8_keycache_get().

◆ internal_first_unpinned()

int32_t internal_first_unpinned	(	const ra8_keycache_t *	kc,
		int32_t	tail )

static

Find the first unpinned cell walking from tail toward the MRU.

Scans a segment's list from its LRU tail following prev links until an unpinned cell is found. Bounded by cfg.cell_count via an explicit guard counter (NASA P10 Rule 2): each cell appears once, so the guard never trips in well-formed state and caps a corrupted list.

Parameters

[in]	kc	Cache providing the cell metadata.
[in]	tail	Segment LRU tail to scan from (-1 for an empty segment).

Returns: The first unpinned cell index, or -1 if the segment is empty or all its cells are pinned.

Return values

-1	No evictable cell in this segment.

Precondition: kc is non-NULL with a populated config.; tail is -1 or a valid cell index in the segment.

Postcondition: No state is modified.; A non-negative result indexes an unpinned cell.

Note: Not thread-safe.

Since: 0.1.0

Definition at line 456 of file ra8_keycache.c.

References ra8_keycache_cfg_t::cell_count, ra8_keycache_t::cfg, ra8_keycache_cfg_t::meta, ra8_keycache_cell_t::pin_count, ra8_keycache_cell_t::prev, and RA8_INTERNAL.

Referenced by internal_pick_victim().

◆ internal_fnv1a()

uint32_t internal_fnv1a	(	const void *	key,
		uint32_t	key_bytes )

static

FNV-1a hash of a key blob (the built-in default hash).

Folds the key_bytes of key through the FNV-1a mix, returning the raw 32-bit value. Bounded by key_bytes (NASA P10 Rule 2). Used when the config supplies no hash callback.

Parameters

[in]	key	Key blob to hash.
[in]	key_bytes	Key width in bytes.

Returns: The raw 32-bit FNV-1a hash.

Return values

0	The bytes folded to zero (one possible result).

Precondition: key is at least key_bytes wide.; key_bytes is non-zero.

Postcondition: No state is modified.; The result depends only on the key bytes.

Note: Pure; thread-safe.

Since: 0.1.0

Definition at line 193 of file ra8_keycache.c.

References k_keycache_fnv_offset, k_keycache_fnv_prime, and RA8_INTERNAL.

Referenced by internal_hash(), and internal_key_matches().

◆ internal_hash()

uint32_t internal_hash	(	const ra8_keycache_t *	kc,
		const void *	key )

static

Hash a key blob into a bucket index using the configured policy.

Runs the injected cfg.hash (or the built-in internal_fnv1a when it is NULL) and folds the raw 32-bit result to [0, bucket_count).

Parameters

[in]	kc	Cache providing the bucket count, key width, and hash policy.
[in]	key	Key blob to hash.

Returns: Bucket index in [0, bucket_count).

Return values

0	The key folded into the first bucket (one possible result).

Precondition: kc is non-NULL with bucket_count > 0 and key_bytes > 0.; key is at least key_bytes wide.

Postcondition: No state is modified.; The result is strictly less than bucket_count.

Note: Pure; thread-safe.

MC/DC:

Decision: if (kc->cfg.hash != nullptr) (1 condition, no compound &&/||).

hash set -> the injected callback runs (::ra8_vmem's page hash).
hash NULL -> the built-in FNV-1a runs (the glyph/tile atlases + tests). Both single-condition outcomes are exercised across the cache test suites.

Since: 0.1.0

Definition at line 232 of file ra8_keycache.c.

References ra8_keycache_cfg_t::bucket_count, ra8_keycache_t::cfg, ra8_keycache_cfg_t::hash, ra8_keycache_cfg_t::hash_ctx, internal_fnv1a(), ra8_keycache_cfg_t::key_bytes, and RA8_INTERNAL.

Referenced by internal_hash_insert(), internal_hash_lookup(), internal_hash_remove(), and internal_index_find().

◆ internal_hash_insert()

void internal_hash_insert	(	ra8_keycache_t *	kc,
		int32_t	f )

static

Insert cell f into its hash bucket chain.

Prepends f to the chain of the bucket its stored key hashes to.

Parameters

[in,out]	kc	Cache providing buckets + metadata.
[in]	f	Cell index (its stored key is set).

Returns: Nothing.

Precondition: f's stored key is set and it is not already chained.; kc is non-NULL with a populated config.

Postcondition: f is the head of its bucket chain.; The previous head follows f.

Note: Not thread-safe.

Since: 0.1.0

Definition at line 342 of file ra8_keycache.c.

References ra8_keycache_cfg_t::buckets, ra8_keycache_t::cfg, ra8_keycache_cell_t::hash_next, internal_hash(), internal_key_ptr(), ra8_keycache_cfg_t::meta, and RA8_INTERNAL.

Referenced by internal_miss().

◆ internal_hash_lookup()

int32_t internal_hash_lookup	(	const ra8_keycache_t *	kc,
		const void *	key )

static

Find the valid cell holding key, or -1.

Walks the key's bucket chain for a valid cell with a matching stored key. The chain walk is bounded by cfg.cell_count via an explicit guard counter (NASA P10 Rule 2).

Parameters

[in]	kc	Cache providing buckets + metadata.
[in]	key	Key blob to find.

Returns: The matching cell index, or -1 if not resident.

Return values

-1	No valid cell holds the key.

Precondition: kc and key are non-NULL.; kc has a populated config.

Postcondition: No state is modified.; A non-negative result indexes a valid cell with the key.

Note: Not thread-safe with respect to concurrent mutation.

Since: 0.1.0

Definition at line 413 of file ra8_keycache.c.

References ra8_keycache_cfg_t::buckets, ra8_keycache_cfg_t::cell_count, ra8_keycache_t::cfg, ra8_keycache_cell_t::hash_next, internal_hash(), internal_key_eq(), internal_key_ptr(), ra8_keycache_cfg_t::meta, RA8_INTERNAL, and ra8_keycache_cell_t::valid.

Referenced by ra8_keycache_get().

◆ internal_hash_remove()

void internal_hash_remove	(	ra8_keycache_t *	kc,
		int32_t	f )

static

Remove cell f from its hash bucket chain.

Unlinks f from its bucket, handling the head and mid-chain cases. The chain walk is bounded by cfg.cell_count via an explicit guard counter (NASA P10 Rule 2) – a corrupted chain cannot spin forever.

Parameters

[in,out]	kc	Cache providing buckets + metadata.
[in]	f	Cell index currently chained.

Returns: Nothing.

Precondition: f is currently present in its bucket chain.; kc is non-NULL with a populated config.

Postcondition: f is no longer reachable from the bucket.; f's hash_next is reset to -1.

Note: Not thread-safe.

Since: 0.1.0

Definition at line 370 of file ra8_keycache.c.

References ra8_keycache_cfg_t::buckets, ra8_keycache_cfg_t::cell_count, ra8_keycache_t::cfg, ra8_keycache_cell_t::hash_next, internal_hash(), internal_key_ptr(), ra8_keycache_cfg_t::meta, and RA8_INTERNAL.

Referenced by internal_miss().

◆ internal_key_eq()

bool internal_key_eq	(	const ra8_keycache_t *	kc,
		const void *	a,
		const void *	b )

static

Byte-wise key equality over key_bytes.

Compares the two key_bytes-wide blobs with memcmp; callers must fully initialise keys (no indeterminate padding) for this to be sound.

Parameters

[in]	kc	Cache providing key_bytes.
[in]	a	First key blob.
[in]	b	Second key blob.

Returns: true if the blobs are byte-identical, else false.

Return values

true	Every key byte matches.
false	Some key byte differs.

Precondition: kc, a, and b are non-NULL.; Both blobs are at least key_bytes wide.

Postcondition: No state is modified.; The result depends only on the key bytes.

Note: Pure; thread-safe.

Since: 0.1.0

Definition at line 166 of file ra8_keycache.c.

References ra8_keycache_t::cfg, ra8_keycache_cfg_t::key_bytes, memcmp(), and RA8_INTERNAL.

Referenced by internal_hash_lookup().

◆ internal_key_ptr()

uint8_t * internal_key_ptr	(	const ra8_keycache_t *	kc,
		uint32_t	idx )

static

Key-storage pointer for cell idx.

Indexes the contiguous key storage by idx * key_bytes.

Parameters

[in]	kc	Cache providing the key storage + stride.
[in]	idx	Cell index in [0, cell_count).

Returns: Pointer to the start of cell idx's stored key.

Return values

non-NULL Always (the storage pointer offset by the stride).

Precondition: kc is non-NULL with a populated config.; idx < cfg.cell_count.

Postcondition: No state is modified.; The result lies within the key storage region.

Note: Pure; thread-safe.

Since: 0.1.0

Definition at line 109 of file ra8_keycache.c.

References ra8_keycache_t::cfg, ra8_keycache_cfg_t::key_bytes, ra8_keycache_cfg_t::key_mem, and RA8_INTERNAL.

Referenced by internal_hash_insert(), internal_hash_lookup(), internal_hash_remove(), and internal_miss().

◆ internal_miss()

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

static

Handle a get miss: evict a victim, render the cell, insert + pin it.

Picks an unpinned victim, drops its old entry (hash remove + unlink from its segment), renders the requested cell, and on success stores the key, re-hashes, and pins it at the probationary MRU. A render failure leaves the cell cold (probationary, invalid) so no stale entry survives.

Parameters

[in,out]	kc	Initialised cache.
[in]	key	Key to render.
[out]	out_view	Receives the pinned cell view.

Returns: ra8_err_t Error code.

Return values

k_ra8_ok	Cell rendered, inserted, and pinned.
k_ra8_err_no_mem	Every cell is pinned.
k_ra8_err_*	The render callback's error (the victim is dropped).

Precondition: kc, key, out_view are non-NULL; the key is not resident.; A cell is evictable unless all are pinned.

Postcondition: On success one valid, pinned cell holds the entry at the probationary MRU.; On render failure the victim is invalidated (no stale entry survives).

Note: Not thread-safe.

Since: 0.1.0

Definition at line 827 of file ra8_keycache.c.

References ra8_keycache_cfg_t::cell_bytes, ra8_keycache_t::cfg, ra8_keycache_t::evictions, internal_cell_ptr(), internal_hash_insert(), internal_hash_remove(), internal_key_ptr(), internal_pick_victim(), internal_push_head(), internal_unlink(), internal_user_ptr(), k_keycache_seg_probation, k_keycache_seg_protected, k_ra8_err_no_mem, k_ra8_ok, ra8_keycache_cfg_t::key_bytes, memcpy(), ra8_keycache_cfg_t::meta, ra8_keycache_t::pb_head, ra8_keycache_t::pb_tail, ra8_keycache_cell_t::pin_count, ra8_keycache_t::protected_count, ra8_keycache_t::pt_head, ra8_keycache_t::pt_tail, ra8_keycache_cfg_t::render, ra8_keycache_cfg_t::render_ctx, ra8_keycache_cell_t::seg, and ra8_keycache_cell_t::valid.

Referenced by ra8_keycache_get().

◆ internal_pick_victim()

int32_t internal_pick_victim ( const ra8_keycache_t * kc )

static

Select an evictable victim: probationary LRU first, then protected LRU.

Read-only (the caller performs the eviction), skips pinned cells. Under LRU the protected segment is always empty, so this reduces to "the LRU cell"; under SLRU one-shot scanned entries in probation are evicted before the protected hot set.

Parameters

[in] kc Cache providing the segment lists + metadata.

Returns: The cell index to evict, or -1 if every cell is pinned.

Return values

-1	No evictable cell (cache fully pinned).

Precondition: kc is non-NULL with a populated config.; The segment lists are consistent.

Postcondition: No state is modified (selection only).; A non-negative result indexes an unpinned cell.

Note: Not thread-safe.

Since: 0.1.0

Definition at line 493 of file ra8_keycache.c.

References internal_first_unpinned(), ra8_keycache_t::pb_tail, ra8_keycache_t::pt_tail, and RA8_INTERNAL.

Referenced by internal_miss().

◆ internal_protected_cap()

uint32_t internal_protected_cap ( const ra8_keycache_cfg_t * cfg )

static

Resolve the SLRU protected-segment capacity, in cells.

Maps cfg->protected_pct (0 selects the 75% default; 1..100 verbatim) to an absolute cell count via cell_count * pct / 100. A small non-zero split can floor to zero protected cells – a valid degenerate policy where every re-reference stays probationary.

Parameters

[in] cfg Validated SLRU configuration (protected_pct <= 100).

Returns: Protected-segment capacity in [0, cell_count].

Return values

0	The split floored to no protected cells.

Precondition: cfg passed internal_validate_cfg_policy (so protected_pct <= 100).; cfg->cell_count is non-zero.

Postcondition: No state is modified.; The result is <= cfg->cell_count.

Note: Pure; thread-safe.

MC/DC:

Decision: protected_pct == 0 selector (1 condition, no compound &&/||).

pct == 0 -> 75% default (the ::ra8_vmem default config).
pct != 0 -> the given split (the vmem 25%/50% split-knob probes).

Since: 0.1.0

Definition at line 728 of file ra8_keycache.c.

References ra8_keycache_cfg_t::cell_count, k_keycache_percent_full, k_keycache_protected_pct_def, ra8_keycache_cfg_t::protected_pct, and RA8_INTERNAL.

Referenced by ra8_keycache_init().

◆ internal_push_head()

void internal_push_head	(	ra8_keycache_t *	kc,
		int32_t	f,
		int32_t *	head,
		int32_t *	tail )

static

Push cell f onto the MRU head of a recency list.

Links f as the new most-recently-used entry, updating the tail when the list was empty. Serves the LRU single list and either SLRU segment.

Parameters

[in,out]	kc	Cache providing the cell metadata.
[in]	f	Cell index to insert (must be detached).
[in,out]	head	Segment MRU head pointer.
[in,out]	tail	Segment LRU tail pointer.

Returns: Nothing.

Precondition: f is not currently linked into any list.; kc, head, tail are non-NULL.

Postcondition: f is the MRU head of the list.; The tail points at f iff the list was previously empty.

Note: Not thread-safe.

Since: 0.1.0

Definition at line 309 of file ra8_keycache.c.

References ra8_keycache_t::cfg, ra8_keycache_cfg_t::meta, ra8_keycache_cell_t::next, and ra8_keycache_cell_t::prev.

Referenced by internal_access(), internal_miss(), internal_seed_cells(), and internal_slru_access().

◆ internal_seed_cells()

void internal_seed_cells	(	ra8_keycache_t *	kc,
		const ra8_keycache_cfg_t *	cfg )

static

Seed a validated cache: clear buckets and link every cell cold.

Zero-fills kc, copies the (already-validated) config in, resets the segment endpoints, clears every hash bucket head to -1, and threads each cell – invalid, unpinned, unchained, probationary – onto the probationary list via internal_push_head. Both loops are bounded by config counts (NASA P10 Rule 2).

Parameters

[out]	kc	Cache state to populate (caller-owned).
[in]	cfg	Validated storage + policy + renderer configuration (non-NULL).

Returns: Nothing.

Precondition: cfg passed internal_validate_cfg_ptrs / _sizes / _policy.; kc is a writable cache-state object.

Postcondition: Every bucket head is -1 and every cell is a cold probationary member.; kc->cfg is a copy of cfg with empty segment endpoints established.

Note: Not thread-safe.

Since: 0.1.0

Definition at line 758 of file ra8_keycache.c.

References ra8_keycache_cfg_t::bucket_count, ra8_keycache_cfg_t::buckets, ra8_keycache_cfg_t::cell_count, ra8_keycache_t::cfg, ra8_keycache_cell_t::hash_next, internal_push_head(), k_keycache_seg_probation, memset(), ra8_keycache_cfg_t::meta, ra8_keycache_t::pb_head, ra8_keycache_t::pb_tail, ra8_keycache_cell_t::pin_count, ra8_keycache_t::pt_head, ra8_keycache_t::pt_tail, RA8_INTERNAL, ra8_keycache_cell_t::seg, and ra8_keycache_cell_t::valid.

Referenced by ra8_keycache_init().

◆ internal_slru_access()

void internal_slru_access	(	ra8_keycache_t *	kc,
		int32_t	f )

static

SLRU re-reference: promote / refresh cell f on a hit.

A protected cell moves to the protected MRU. A probationary cell is promoted to protected, demoting the protected LRU back to probationary if the protected segment is at capacity.

Parameters

[in,out]	kc	Cache providing the metadata + segment lists.
[in]	f	Cell index just accessed.

Returns: Nothing.

Precondition: f is a valid, currently-linked cell.; kc is non-NULL with a populated SLRU config.

Postcondition: f is at the MRU of the protected segment.; protected_count <= protected_cap.

Note: Not thread-safe.

Since: 0.1.0

Definition at line 523 of file ra8_keycache.c.

References ra8_keycache_t::cfg, internal_push_head(), internal_unlink(), k_keycache_seg_probation, k_keycache_seg_protected, ra8_keycache_cfg_t::meta, ra8_keycache_t::pb_head, ra8_keycache_t::pb_tail, ra8_keycache_t::protected_cap, ra8_keycache_t::protected_count, ra8_keycache_t::pt_head, ra8_keycache_t::pt_tail, RA8_INTERNAL, and ra8_keycache_cell_t::seg.

Referenced by internal_access().

◆ internal_unlink()

void internal_unlink	(	ra8_keycache_t *	kc,
		int32_t	f,
		int32_t *	head,
		int32_t *	tail )

static

Detach cell f from the recency list owned by head / tail.

Splices f out of the doubly-linked list, fixing the neighbours and the head/tail pointers as needed. The same primitive serves the LRU single list and either SLRU segment.

Parameters

[in,out]	kc	Cache providing the cell metadata.
[in]	f	Cell index to unlink.
[in,out]	head	Segment MRU head pointer.
[in,out]	tail	Segment LRU tail pointer.

Returns: Nothing.

Precondition: f is currently a member of the head / tail list.; kc, head, tail are non-NULL.

Postcondition: f's neighbours and the head/tail no longer reference f.; Other cells are unmodified.

Note: Not thread-safe.

Since: 0.1.0

Definition at line 267 of file ra8_keycache.c.

References ra8_keycache_t::cfg, ra8_keycache_cfg_t::meta, ra8_keycache_cell_t::next, and ra8_keycache_cell_t::prev.

Referenced by internal_access(), internal_miss(), and internal_slru_access().

◆ internal_user_ptr()

void * internal_user_ptr	(	const ra8_keycache_t *	kc,
		uint32_t	idx )

static

User-descriptor pointer for cell idx, or NULL when unused.

Indexes the contiguous user-descriptor storage by idx * user_bytes, or returns NULL when the cache was configured with no descriptor.

Parameters

[in]	kc	Cache providing the descriptor storage + stride.
[in]	idx	Cell index in [0, cell_count).

Returns: Pointer to cell idx's descriptor, or NULL when user_bytes == 0.

Return values

NULL	The cache carries no per-cell user descriptor.

Precondition: kc is non-NULL with a populated config.; idx < cfg.cell_count.

Postcondition: No state is modified.; A non-NULL result lies within the descriptor storage region.

Note: Pure; thread-safe.

Since: 0.1.0

Definition at line 135 of file ra8_keycache.c.

References ra8_keycache_t::cfg, RA8_INTERNAL, ra8_keycache_cfg_t::user_bytes, and ra8_keycache_cfg_t::user_mem.

Referenced by internal_miss(), and ra8_keycache_get().

◆ internal_validate_cfg_policy()

ra8_err_t internal_validate_cfg_policy ( const ra8_keycache_cfg_t * cfg )

static

Validate the SLRU split knob when the SLRU policy is selected.

An SLRU cache rejects a protected_pct above 100; every other value (0 selecting the 75% default) is accepted. Under LRU the knob is unused, so nothing is checked. Two nested single-condition decisions; no compound &&/||.

Parameters

[in] cfg Storage + policy configuration to validate (non-NULL).

Returns: ra8_err_t Error code.

Return values

k_ra8_ok	The policy knob is in range (or unused under LRU).
k_ra8_err_invalid_arg	SLRU with protected_pct above 100.

Precondition: cfg is non-NULL (the caller checked it).; The config passed internal_validate_cfg_ptrs / internal_validate_cfg_sizes.

Postcondition: No state is modified (pure validation).; A non-ok return means SLRU was selected with an out-of-range split.

Note: Not thread-safe with respect to concurrent config mutation.

MC/DC:

Decision A: if (cfg->evict == SLRU) (1 condition); Decision B: if (protected_pct > 100) (1 condition). Neither is compound.

LRU -> both skipped, k_ra8_ok (glyph/tile tests).
SLRU, pct == 101 -> A true, B true, k_ra8_err_invalid_arg (vmem).
SLRU, pct == 25/50 -> A true, B false, k_ra8_ok (vmem split knob).

Since: 0.1.0

Definition at line 690 of file ra8_keycache.c.

References ra8_keycache_cfg_t::evict, k_keycache_percent_full, k_ra8_err_invalid_arg, k_ra8_keycache_evict_slru, k_ra8_ok, ra8_keycache_cfg_t::protected_pct, and RA8_INTERNAL.

Referenced by ra8_keycache_init().

◆ internal_validate_cfg_ptrs()

ra8_err_t internal_validate_cfg_ptrs ( const ra8_keycache_cfg_t * cfg )

static

Validate that every required config pointer is non-NULL.

Runs the null-pointer preconditions for ra8_keycache_init: the cell, key, meta, bucket, and render pointers, plus user_mem when user_bytes > 0. Each check is an independent decision kept intact here (no compound decision is split across functions).

Parameters

[in] cfg Storage + renderer configuration to validate (non-NULL).

Returns: ra8_err_t Error code.

Return values

k_ra8_ok	Every required pointer is non-NULL.
k_ra8_err_null_ptr	A required cfg pointer is NULL.

Precondition: cfg is non-NULL (the caller checked it).; The config fields reflect the caller's intended storage layout.

Postcondition: No state is modified (pure validation).; A non-ok return means a required cfg pointer is NULL.

Note: Not thread-safe with respect to concurrent config mutation.

Since: 0.1.0

Definition at line 605 of file ra8_keycache.c.

References ra8_keycache_cfg_t::buckets, ra8_keycache_cfg_t::cell_mem, k_ra8_ok, ra8_keycache_cfg_t::key_mem, ra8_keycache_cfg_t::meta, RA8_CHECK_NULL_PTR, RA8_INTERNAL, ra8_keycache_cfg_t::render, s_tag, ra8_keycache_cfg_t::user_bytes, and ra8_keycache_cfg_t::user_mem.

Referenced by ra8_keycache_init().

◆ internal_validate_cfg_sizes()

ra8_err_t internal_validate_cfg_sizes ( const ra8_keycache_cfg_t * cfg )

static

Validate that every config sizing field is non-zero.

Rejects a zero cell_count, cell_bytes, key_bytes, or bucket_count – each would make the cache storage degenerate. Each check is an independent decision kept intact here (no compound decision is split across functions).

Parameters

[in] cfg Storage + renderer configuration to validate (non-NULL).

Returns: ra8_err_t Error code.

Return values

k_ra8_ok	Every sizing field is non-zero.
k_ra8_err_invalid_size	A sizing field (cell_count, cell_bytes, key_bytes, bucket_count) was zero.

Precondition: cfg is non-NULL (the caller checked it).; The config pointers passed internal_validate_cfg_ptrs.

Postcondition: No state is modified (pure validation).; A non-ok return means a sizing field was zero.

Note: Not thread-safe with respect to concurrent config mutation.

Since: 0.1.0

Definition at line 642 of file ra8_keycache.c.

References ra8_keycache_cfg_t::bucket_count, ra8_keycache_cfg_t::cell_bytes, ra8_keycache_cfg_t::cell_count, k_ra8_err_invalid_size, k_ra8_ok, ra8_keycache_cfg_t::key_bytes, and RA8_INTERNAL.

Referenced by ra8_keycache_init().

◆ 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().

Variable Documentation

◆ s_tag

const char* const s_tag = "ra8_keycache"

static

Module log tag.

Definition at line 35 of file ra8_keycache.c.

Enumerations

Functions

Variables

Detailed Description

Enumeration Type Documentation

◆ ra8_keycache_const_t

◆ ra8_keycache_seg_t

Function Documentation

◆ internal_access()

◆ internal_cell_ptr()

◆ internal_first_unpinned()

◆ internal_fnv1a()

◆ internal_hash()

◆ internal_hash_insert()

◆ internal_hash_lookup()

◆ internal_hash_remove()

◆ internal_key_eq()

◆ internal_key_ptr()

◆ internal_miss()

◆ internal_pick_victim()

◆ internal_protected_cap()

◆ internal_push_head()

◆ internal_seed_cells()

◆ internal_slru_access()

◆ internal_unlink()

◆ internal_user_ptr()

◆ internal_validate_cfg_policy()

◆ internal_validate_cfg_ptrs()

◆ internal_validate_cfg_sizes()

◆ ra8_keycache_get()

◆ ra8_keycache_init()

◆ ra8_keycache_prefetch()

◆ ra8_keycache_put()

◆ ra8_keycache_stats()

Variable Documentation

◆ s_tag