trace.c File Reference

Deterministic synthetic cursors and bounded captured-trace parsing. More...

#include "trace.h"
#include <errno.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include "ra8_attributes.h"

Include dependency graph for trace.c:

Go to the source code of this file.

Enumerations
enum	cb_workload_dim_t : uint32_t {   k_cb_obj_book = 1U ,   k_cb_obj_comic = 2U ,   k_cb_footprint = 8192U ,   k_cb_accesses = 120000U ,   k_cb_hot_pages = 96U ,   k_cb_reread_pct = 82U ,   k_cb_jump_pct = 4U ,   k_cb_tile_span = 6144U ,   k_cb_sr_hot = 192U ,   k_cb_sr_hot_pass = 3U ,   k_cb_sr_scan = 1500U ,   k_cb_pct_full = 100U ,   k_cb_mixed_phase = 2048U ,   k_cb_huge_footprint = 1835008U ,   k_cb_huge_hot = 256U ,   k_cb_huge_hot_pass = 3U ,   k_cb_huge_scan = 4000U }
enum	cb_trace_math_t : uint8_t {   k_rng_shift_a = 13U ,   k_rng_shift_b = 7U ,   k_rng_shift_c = 17U ,   k_cb_base_dec = 10U ,   k_cb_key_high_shift = 24U }
enum	cb_trace_seed_t : uint64_t {   k_rng_seed_random = 0x9E3779B97F4A7C15ULL ,   k_rng_seed_reread = 0xD1B54A32D192ED03ULL ,   k_rng_seed_toc = 0x2545F4914F6CDD1DULL ,   k_rng_seed_mixed_a = 0x9E3779B97F4A7C15ULL ,   k_rng_seed_mixed_b = 0xABCDEF1234567890ULL ,   k_cb_hash_offset = 0xCBF29CE484222325ULL ,   k_cb_hash_prime = 0x100000001B3ULL }

Functions
static uint64_t	internal_rng (uint64_t *state)
	Advance a deterministic trace pseudo-random generator.
static uint32_t	internal_rand_below (uint64_t *state, uint32_t span)
	Select a deterministic pseudo-random value below a bound.
static uint64_t	internal_trace_hash (uint64_t hash, cb_key_t key)
	Fold one cache key into the captured-trace fingerprint.
void	cb_traces_synthetic (cb_trace_t out[k_cb_synthetic_trace_count])
	Populate the fixed built-in corpus without acquiring storage.
static cb_io_status_t	internal_trace_read_byte (cb_trace_cursor_t *cursor, uint8_t *out, bool *eof)
	Pull one byte through the captured-source read-ahead buffer.
static bool	internal_parse_trace_line (const char *line, uint32_t *object_id, uint32_t *page)
	Parse one captured decimal object/page record.
static cb_io_status_t	internal_trace_captured_next (cb_trace_cursor_t *cursor, cb_key_t *key, bool *done)
	Emit the next key from a captured decimal trace.
static cb_key_t	internal_trace_scan_key (uint64_t index, bool huge)
	Generate one scan-resistant hot-set-plus-scan workload key.
static cb_key_t	internal_trace_synthetic_next (cb_trace_cursor_t *cursor)
	Emit one key from the selected synthetic workload generator.
cb_io_status_t	cb_trace_cursor_open (const cb_trace_t *trace, cb_trace_cursor_t *cursor)
	Reset a cursor for an independent pass over a trace.
cb_io_status_t	cb_trace_cursor_next (cb_trace_cursor_t *cursor, cb_key_t *key, bool *done)
	Emit the next key.
cb_io_status_t	cb_trace_cursor_finish (const cb_trace_cursor_t *cursor)
	Validate a captured pass against its bound count and fingerprint.
cb_io_status_t	cb_trace_bind (const cb_source_t *source, const char *name, size_t name_length, cb_trace_t *out)
	Validate and bind one captured decimal <object> <page> source.

Detailed Description

Deterministic synthetic cursors and bounded captured-trace parsing.

Implements resettable generators plus injected, fingerprinted captured reads without materializing any complete access trace.

[Ring 7 / Tooling] {World: NS}

Copyright

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

Since

0.1.0

Definition in file trace.c.

Enumeration Type Documentation

cb_trace_math_t

enum cb_trace_math_t : uint8_t

Enumerator
k_rng_shift_a	First xorshift distance.
k_rng_shift_b	Middle xorshift distance.
k_rng_shift_c	Final xorshift distance.
k_cb_base_dec	Captured decimal parser radix.
k_cb_key_high_shift	Object-key high-word shift.

Definition at line 42 of file trace.c.

cb_trace_seed_t

enum cb_trace_seed_t : uint64_t

Enumerator
k_rng_seed_random	Random workload seed.
k_rng_seed_reread	Reread workload seed.
k_rng_seed_toc	Jump workload seed.
k_rng_seed_mixed_a	Mixed hot-phase seed.
k_rng_seed_mixed_b	Mixed scan-phase seed.
k_cb_hash_offset	FNV-1a offset basis.
k_cb_hash_prime	FNV-1a multiplication.

Definition at line 50 of file trace.c.

cb_workload_dim_t

enum cb_workload_dim_t : uint32_t

Enumerator
k_cb_obj_book	Synthetic book object key.
k_cb_obj_comic	Synthetic comic object key.
k_cb_footprint	Ordinary working-set pages.
k_cb_accesses	Ordinary workload access count.
k_cb_hot_pages	Ordinary reread hot-set pages.
k_cb_reread_pct	Reread hot-set percentage.
k_cb_jump_pct	Random-jump percentage.
k_cb_tile_span	Scroll workload page span.
k_cb_sr_hot	Scan-resistant hot-set pages.
k_cb_sr_hot_pass	Hot passes per scan-resistant run.
k_cb_sr_scan	Scan pages per resistant run.
k_cb_pct_full	Complete percentage denominator.
k_cb_mixed_phase	Accesses per mixed phase.
k_cb_huge_footprint	Huge workload working-set pages.
k_cb_huge_hot	Huge workload hot-set pages.
k_cb_huge_hot_pass	Huge workload hot passes.
k_cb_huge_scan	Huge workload scan pages.

Definition at line 22 of file trace.c.

Function Documentation

cb_trace_bind()

cb_io_status_t cb_trace_bind	(	const cb_source_t *	source,
		const char *	name,
		size_t	name_length,
		cb_trace_t *	out )

Validate and bind one captured decimal <object> <page> source.

Copies the bounded display name, validates a complete pass through the injected source, and snapshots its count plus fingerprint.

Parameters

[in]	source	Borrowed immutable byte source.
[in]	name	Display name bytes (need not be NUL-terminated).
[in]	name_length	Display-name byte count.
[out]	out	Bound trace on success; zeroed on failure.

Returns

I/O, capacity, or success status.

Return values

k_cb_io_ok	out contains a validated captured trace.
k_cb_io_capacity	The display name exceeds fixed storage.
k_cb_io_fault	A binding, parser, or source contract failed.
k_cb_io_mutated	The source changed during validation.

Precondition

source has a non-NULL read callback and stable size snapshot.

name and out are non-NULL.

Postcondition

On success, out borrows source and owns its copied name only.

On failure, out is all-zero.

Note

Caller must keep the source context alive through every replay.

Since

0.1.0

Definition at line 473 of file trace.c.

References cb_trace_cursor_next(), cb_trace_cursor_open(), cb_trace::fingerprint, cb_trace_cursor_t::fingerprint, cb_trace_cursor_t::index, k_cb_io_capacity, k_cb_io_fault, k_cb_io_ok, k_cb_trace_captured, k_cb_trace_name_capacity, memcpy(), cb_trace::n, cb_trace::name, cb_trace::name_storage, and cb_source_t::read.

Referenced by internal_load_argv_traces().

cb_trace_cursor_finish()

cb_io_status_t cb_trace_cursor_finish

(

const cb_trace_cursor_t *

cursor

)

Validate a captured pass against its bound count and fingerprint.

Compares emitted count and accumulated fingerprint with the values snapshotted by cb_trace_bind; synthetic passes require count only.

Parameters

[in]

cursor

Finished trace cursor.

Returns

Tool-local I/O status.

Return values

k_cb_io_ok	Count and, for captured traces, fingerprint match.
k_cb_io_fault	A binding or count check failed.
k_cb_io_mutated	Captured content changed between passes.

Precondition

cursor and cursor->trace are non-NULL.

Iteration reached clean completion before this call.

Postcondition

Cursor and trace state are not modified.

A captured mismatch is distinguishable from an ordinary fault.

Note

This closes logical validation only; it owns no host descriptor.

Since

0.1.0

Definition at line 459 of file trace.c.

References cb_trace::fingerprint, cb_trace_cursor_t::fingerprint, cb_trace_cursor_t::index, k_cb_io_fault, k_cb_io_mutated, k_cb_io_ok, k_cb_trace_captured, cb_trace::kind, cb_trace::n, and cb_trace_cursor_t::trace.

Referenced by internal_replay_stream().

cb_trace_cursor_next()

cb_io_status_t cb_trace_cursor_next	(	cb_trace_cursor_t *	cursor,
		cb_key_t *	key,
		bool *	done )

Emit the next key.

Dispatches to the captured parser or selected deterministic generator, then advances count and fingerprint for emitted keys.

Parameters

[in,out]	cursor	Open cursor.
[out]	key	Next key when done is false.
[out]	done	True at a clean end.

Returns

Source/parser status.

Return values

k_cb_io_ok	A key or clean end was produced.
k_cb_io_fault	A cursor, generator, parser, or source contract failed.
k_cb_io_mutated	The injected source reported mutation.

Precondition

All pointers are non-NULL and cursor is open.

key and done point to writable storage.

Postcondition

When done is false, cursor count advances and key is initialized.

Once the declared count is reached, done is true.

Note

Call cb_trace_cursor_finish after termination to validate stability.

Since

0.1.0

Definition at line 438 of file trace.c.

References cb_trace_cursor_t::fingerprint, cb_trace_cursor_t::index, internal_trace_captured_next(), internal_trace_hash(), internal_trace_synthetic_next(), k_cb_io_fault, k_cb_io_ok, k_cb_trace_captured, cb_trace::kind, cb_trace::n, and cb_trace_cursor_t::trace.

Referenced by cb_trace_bind(), and internal_replay_stream().

cb_trace_cursor_open()

cb_io_status_t cb_trace_cursor_open	(	const cb_trace_t *	trace,
		cb_trace_cursor_t *	cursor )

Reset a cursor for an independent pass over a trace.

Clears cursor state, binds trace, and selects the deterministic seed required by its workload kind.

Parameters

[in]	trace	Immutable trace descriptor.
[out]	cursor	Cursor to initialize.

Returns

Tool-local I/O status.

Return values

k_cb_io_ok	The cursor is ready for its first key.
k_cb_io_fault	An argument or trace kind is invalid.

Precondition

trace and cursor are non-NULL.

trace was initialized by a published trace binder.

Postcondition

On success, cursor index and fingerprint are at their initial values.

trace is not modified and remains borrowed.

Note

Distinct cursors may replay the same immutable trace independently.

Since

0.1.0

Definition at line 418 of file trace.c.

References cb_trace::fingerprint, k_cb_hash_offset, k_cb_io_fault, k_cb_io_ok, k_cb_trace_captured, k_cb_trace_jumps, k_cb_trace_mixed, k_cb_trace_random, k_cb_trace_reread, k_rng_seed_mixed_a, k_rng_seed_mixed_b, k_rng_seed_random, k_rng_seed_reread, k_rng_seed_toc, cb_trace::kind, cb_source_t::read, cb_trace_cursor_t::rng, and cb_trace::source.

Referenced by cb_trace_bind(), and internal_replay_stream().

cb_traces_synthetic()

void cb_traces_synthetic

(

cb_trace_t

out[k_cb_synthetic_trace_count]

)

Populate the fixed built-in corpus without acquiring storage.

Initializes all names, counts, footprints, and generator kinds in stable report order.

Parameters

[out]

out

Array of k_cb_synthetic_trace_count descriptors.

Precondition

out is non-NULL and has the declared array capacity.

Static corpus geometry fits the published descriptor fields.

Postcondition

Every output descriptor is initialized and resettable.

No external storage or ownership is acquired.

Note

Descriptor names point to read-only static strings.

Since

0.1.0

Definition at line 141 of file trace.c.

References k_cb_accesses, k_cb_footprint, k_cb_huge_footprint, k_cb_synthetic_trace_count, and k_cb_tile_span.

Referenced by internal_run_capacity().

internal_parse_trace_line()

bool internal_parse_trace_line ( const char * line, uint32_t * object_id, uint32_t * page )

static

Parse one captured decimal object/page record.

Converts the two unsigned decimal fields and rejects missing, overflowing, or conversion-error values.

Parameters

[in]	line	NUL-terminated record bytes.
[out]	object_id	Receives the object identifier.
[out]	page	Receives the page index.

Returns

Whether both fields were converted.

Return values

true	Both outputs contain 32-bit values.
false	A field is absent, overflowing, or invalid.

Precondition

All pointers are non-NULL and outputs are writable.

line is NUL-terminated within the fixed line capacity.

Postcondition

On success, both outputs are initialized.

Input bytes are not modified.

Note

Trailing bytes preserve the historical permissive parser behavior.

Since

0.1.0

Definition at line 237 of file trace.c.

References k_cb_base_dec.

Referenced by internal_trace_captured_next().

internal_rand_below()

uint32_t internal_rand_below ( uint64_t * state, uint32_t span )

static

Select a deterministic pseudo-random value below a bound.

Advances state and reduces the result modulo span, with a defined zero result for an empty span.

Parameters

[in,out]	state	Generator state.
[in]	span	Exclusive upper bound.

Returns

Value in [0, span), or zero when span is zero.

Return values

0	The span is zero or the reduced value is zero.
other	Reduced pseudo-random value below span.

Precondition

state is non-NULL and initialized.

span is an ordinary synthetic-workload bound.

Postcondition

For non-zero span, the result is strictly less than span.

state advances exactly once.

Note

Modulo bias is acceptable for this deterministic benchmark corpus.

Since

0.1.0

Definition at line 101 of file trace.c.

References internal_rng().

Referenced by internal_trace_synthetic_next().

internal_rng()

uint64_t internal_rng ( uint64_t * state )

static

Advance a deterministic trace pseudo-random generator.

Applies the fixed xorshift sequence used by synthetic workloads.

Parameters

[in,out]

state

Non-zero generator state.

Returns

Updated 64-bit pseudo-random value.

Return values

other

Deterministic next value in the sequence.

Precondition

state is non-NULL and writable.

The initial state is non-zero.

Postcondition

*state equals the returned value.

No state outside state is modified.

Note

This generator provides reproducibility, not cryptographic entropy.

Since

0.1.0

Definition at line 74 of file trace.c.

References k_rng_shift_a, k_rng_shift_b, and k_rng_shift_c.

Referenced by internal_rand_below().

internal_trace_captured_next()

cb_io_status_t internal_trace_captured_next ( cb_trace_cursor_t * cursor, cb_key_t * key, bool * done )

static

Emit the next key from a captured decimal trace.

Assembles one bounded line through read-ahead, treats clean EOF as done, and preserves the historical stop-on-unparseable-line rule.

Parameters

[in,out]	cursor	Open captured trace cursor.
[out]	key	Receives the next parsed key.
[out]	done	Receives true at EOF or the first unparsable record.

Returns

Tool-local I/O status.

Return values

k_cb_io_ok	A key or clean termination was produced.
k_cb_io_fault	The injected source contract failed.
k_cb_io_mutated	The source reported mutation.

Precondition

All pointers are non-NULL and cursor is captured-kind.

Cursor line and read-ahead buffers are initialized.

Postcondition

When done is false, key contains one parsed record.

Cursor source position never moves backward.

Note

A line reaching the fixed bound is parsed from its bounded prefix.

Since

0.1.0

Definition at line 286 of file trace.c.

References internal_parse_trace_line(), internal_trace_read_byte(), k_cb_io_ok, cb_trace_cursor_t::line, cb_key_t::object_id, and cb_key_t::page.

Referenced by cb_trace_cursor_next().

internal_trace_hash()

uint64_t internal_trace_hash ( uint64_t hash, cb_key_t key )

static

Fold one cache key into the captured-trace fingerprint.

Serializes both 32-bit fields in fixed little-endian byte order and applies the benchmark's FNV-1a accumulator.

Parameters

[in]	hash	Current fingerprint accumulator.
[in]	key	Cache key to append.

Returns

Updated 64-bit fingerprint.

Return values

other

Fingerprint after all eight key bytes are folded.

Precondition

hash is the offset basis or a prior result from this helper.

key contains initialized object and page fields.

Postcondition

The result is independent of host structure padding and endianness.

No storage is modified.

Note

This fingerprint detects mutation; it is not a security hash.

Since

0.1.0

Definition at line 122 of file trace.c.

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

Referenced by cb_trace_cursor_next().

internal_trace_read_byte()

cb_io_status_t internal_trace_read_byte ( cb_trace_cursor_t * cursor, uint8_t * out, bool * eof )

static

Pull one byte through the captured-source read-ahead buffer.

Refills the bounded buffer through the injected source at EOF of the current grain and rejects zero-progress or over-count callbacks.

Parameters

[in,out]	cursor	Open captured trace cursor.
[out]	out	Receives one byte when eof is false.
[out]	eof	Receives true at clean source exhaustion.

Returns

Tool-local I/O status.

Return values

k_cb_io_ok	One byte or clean EOF was reported.
k_cb_io_fault	The source violated its progress/count contract.
k_cb_io_mutated	The injected source reported mutation.

Precondition

All pointers are non-NULL and cursor is open on a captured trace.

The cursor read-ahead indices are within their fixed buffer.

Postcondition

On a byte, the read cursor advances exactly once.

At EOF, out is not modified and eof is true.

Note

Short injected reads are accepted and buffered.

Since

0.1.0

Definition at line 190 of file trace.c.

References cb_source_t::ctx, k_cb_io_fault, k_cb_io_ok, cb_source_t::read, cb_trace_cursor_t::read_at, cb_trace_cursor_t::read_buffer, cb_trace_cursor_t::read_count, cb_source_t::size, cb_trace::source, cb_trace_cursor_t::source_offset, and cb_trace_cursor_t::trace.

Referenced by internal_trace_captured_next().

internal_trace_scan_key()

cb_key_t internal_trace_scan_key ( uint64_t index, bool huge )

static

Generate one scan-resistant hot-set-plus-scan workload key.

Alternates repeated hot-set passes with a moving cold scan and supports both normal and huge-book geometries.

Parameters

[in]	index	Zero-based access index.
[in]	huge	Selects the huge-book geometry when true.

Returns

Deterministic cache key for index.

Return values

other

Book-object key within the selected footprint.

Precondition

The selected footprint is larger than its hot set.

Fixed hot, pass, and scan constants define a non-zero cycle.

Postcondition

The returned page is less than the selected footprint.

No generator state is retained or modified.

Note

Thread-safe: this is a pure function of index and huge.

Since

0.1.0

Definition at line 334 of file trace.c.

References k_cb_footprint, k_cb_huge_footprint, k_cb_huge_hot, k_cb_huge_hot_pass, k_cb_huge_scan, k_cb_obj_book, k_cb_sr_hot, k_cb_sr_hot_pass, and k_cb_sr_scan.

Referenced by internal_trace_synthetic_next().

internal_trace_synthetic_next()

cb_key_t internal_trace_synthetic_next ( cb_trace_cursor_t * cursor )

static

Emit one key from the selected synthetic workload generator.

Dispatches by trace kind and advances only the cursor state required by that workload's locality pattern.

Parameters

[in,out]

cursor

Open synthetic trace cursor.

Returns

Next deterministic cache key.

Return values

other

Key within the selected workload geometry.

Precondition

cursor and cursor->trace are non-NULL.

cursor->trace->kind is a synthetic kind.

Postcondition

Returned object and page fields are initialized.

Any stateful generator fields advance consistently with one access.

Note

The public cursor function advances the common access index.

Since

0.1.0

Definition at line 366 of file trace.c.

References cb_trace_cursor_t::hot, cb_trace_cursor_t::index, internal_rand_below(), internal_trace_scan_key(), k_cb_footprint, k_cb_hot_pages, k_cb_jump_pct, k_cb_mixed_phase, k_cb_obj_book, k_cb_obj_comic, k_cb_pct_full, k_cb_reread_pct, k_cb_tile_span, k_cb_trace_captured, k_cb_trace_huge, k_cb_trace_jumps, k_cb_trace_mixed, k_cb_trace_random, k_cb_trace_reread, k_cb_trace_scan, k_cb_trace_scroll, k_cb_trace_seq, cb_trace::kind, cb_trace_cursor_t::page, cb_trace_cursor_t::rng, and cb_trace_cursor_t::trace.

Referenced by cb_trace_cursor_next().