stratum

A single-header C99 string arena for constrained environments.

Packs variable-length strings into 64-byte cache-line blocks with zero null terminators in the data region. String boundaries are encoded in a parallel uint64_t bitmask, enabling O(1) length lookup via a single hardware CTZ instruction rather than a byte scan.

Standard malloc() on microcontrollers fragments SRAM over time. After thousands of variable-length allocations and frees (MQTT topic parsing, JSON field buffering, UART log interning), the heap holds enough total free bytes but no single contiguous block large enough for the next request. The device crashes.

Fixed-size block allocators solve fragmentation but waste space on short strings. stratum packs strings of any length back-to-back within each 64-byte block, wasting zero bytes to alignment within the block while maintaining O(1) allocation via a two-level availability bitmap.

Measured on x86-64, GCC 12 -O2. Embedded results will differ.

The speedup comes entirely from replacing strlen's byte scan with a single __builtin_ctzll instruction on a pre-computed boundary bitmask.

Allocation throughput is competitive with malloc() for pools under 64 blocks (4 KB data region), where the two-level bitmap provides O(1) worst-case block search. Larger pools have O(1) for the first 64 blocks and O(N-64) linear fallback for the remainder.

#define STRATUM_IMPLEMENTATION   /* in exactly one translation unit */
#include "stratum.h"

/* Supply your own memory: no internal malloc() for the data region */
static uint8_t pool_buf[2048];
stratum_pool_t pool;
stratum_init(&pool, pool_buf, sizeof(pool_buf));

/* Store a string -- not null-terminated in the pool */
stratum_handle_t h = stratum_store(&pool, "hello", 5);
/* h == STRATUM_INVALID_HANDLE on OOM */

/* Read: returns a direct pointer for single-block strings */
size_t len = 0;
const char *p = stratum_read(&pool, h, &len);
/* p is NOT null-terminated. Use len. */

/* Safe null-terminated copy */
char dest[64];
size_t dest_len = sizeof(dest);
stratum_read_copy(&pool, h, dest, &dest_len);

/* Free */
stratum_free(&pool, h);

/* Pool statistics */
stratum_stats_t s = stratum_stats(&pool);

/* Offline compaction to eliminate fragmentation */
static uint8_t compact_buf[2048];
stratum_handle_t old_h[N], new_h[N];
stratum_compact(&pool, compact_buf, sizeof(compact_buf), old_h, new_h, N);
/* Update your stored handles from new_h[] */

stratum_destroy(&pool);

Chain mode allows strings longer than one cache line. Default mode rejects them at the API boundary, keeping metadata small.

Debug mode adds handle-validity assertions to stratum_read, stratum_free, and stratum_compact. Use during development; remove for release.

/* Initialise a pool over a caller-supplied buffer.
   Returns 0 on success, -1 if buffer_size < 64. */
int stratum_init(stratum_pool_t *pool, void *buffer, size_t buffer_size);

/* Store len bytes from str. Binary-safe (embedded NUL bytes allowed).
   Returns STRATUM_INVALID_HANDLE on OOM or string-too-long. */
stratum_handle_t stratum_store(stratum_pool_t *pool,
                                const char *str, size_t len);

/* Return a direct pointer into pool memory for single-block strings.
   Sets *out_len. Returns NULL for multi-block strings (use stratum_read_copy).
   The pointer is valid until stratum_free(h) or stratum_destroy(). */
const char *stratum_read(const stratum_pool_t *pool,
                          stratum_handle_t h, size_t *out_len);

/* Copy string at h into dest. Writes null terminator.
   Returns 0 on success, -1 if dest is too small (sets *buf_len to
   the required size), -2 on invalid arguments. */
int stratum_read_copy(const stratum_pool_t *pool, stratum_handle_t h,
                       char *dest, size_t *buf_len);

/* Mark handle h's bytes as dead. Space is reclaimed when the entire
   block dies (live_mask == 0), or via stratum_compact(). */
void stratum_free(stratum_pool_t *pool, stratum_handle_t h);

/* Pool utilisation statistics. */
stratum_stats_t stratum_stats(const stratum_pool_t *pool);

/* Offline compaction. Rebuilds the pool into new_buf (caller-supplied,
   must be >= pool->block_count * 64 bytes). Remaps old_handles[i] to
   new_handles[i]. Freed handles map to STRATUM_INVALID_HANDLE.
   Returns 0 on success, -1 if new_buf is too small, -2 on bad args.
   Caller must update stored handles from new_handles[] after this call. */
int stratum_compact(stratum_pool_t *pool,
                     void *new_buf, size_t new_buf_size,
                     const stratum_handle_t *old_handles,
                     stratum_handle_t *new_handles,
                     size_t handle_count);

/* Free the internally-allocated metadata array.
   The caller owns the data buffer passed to stratum_init. */
void stratum_destroy(stratum_pool_t *pool);

These are not caveats to be minimised. They are architectural decisions with specific consequences.

Metadata overhead. 24 bytes per 64-byte block in default mode (37.5% overhead). This is the cost of storing out-of-band boundary information. For a 2 KB pool (32 blocks) the metadata array is 768 bytes, allocated via calloc during stratum_init. If your environment has no heap at all, you can supply a static metadata array by modifying stratum_init; the data structure is fully documented in the header.

No inline compaction. Handles encode block_index << 6 | byte_offset directly. Shifting bytes within a block would invalidate those offsets with no way to notify the caller. In-place compaction is architecturally incompatible with direct-offset handles. Use stratum_compact() during idle periods for long-running workloads.

Phase 1 fallback for large pools. For pools with more than 64 blocks (more than 4 KB data), the O(1) two-level bitmap covers blocks 0-63. Blocks 64+ use a linear scan with a dedicated cursor. If hard O(1) allocation is required for pools larger than 4 KB, split into multiple 4 KB pools and round-robin between them.

Not thread-safe. All API functions access shared pool state. Protect with a mutex or restrict to a single thread.

Append-only per block. Dead bytes from freed strings within a block are not compacted inline. They are reclaimed only when the entire block becomes dead (live_mask == 0). stratum_compact() is the explicit escape valve.

Duplicate handles in stratum_compact are not detected. Passing the same handle twice results in the string being stored twice in the compacted pool. O(N^2) detection is not worth the cost for an offline operation; this is caller responsibility.

The boundary encoding is the same primitive used in vectorised databases (Apache Arrow's offset buffer for StringArray) and fast JSON parsers (simdjson's structural bitmasks). This library applies it as a dynamic, append-friendly arena rather than a static storage format.

The two-level availability bitmap (avail_summary) is a standard technique from OS page allocators. One uint64_t covers 64 blocks; finding any free block in that range is a single CTZ instruction.

The handle format (block_index << 6 | byte_offset) is intentional. Six bits for offset (0-63, matching the 64-byte block size) leaves 26 bits for block index, addressing up to 67 million blocks.

See example_mqtt_parser.c for a complete walkthrough using stratum as a drop-in replacement for malloc() in an MQTT topic subscription table, including subscribe/unsubscribe churn and pool compaction.

gcc -O2 -std=c99 -o test_stratum test_stratum.c && ./test_stratum

With sanitisers:

gcc -O2 -std=c99 -fsanitize=address,undefined -o test_stratum test_stratum.c
./test_stratum

MIT. See bottom of stratum.h.