UMR Features

Universal Memory Runtime — Feature Specification

Field	Value
Version	1.0
Status	Implementation Hardening (v0.1)
Scope	Core features (v1) + future advanced features

This document specifies each product feature: purpose, behavior, API shape, and acceptance ideas. Implementation details live in architecture.md; scheduling lives in plan.md.

Feature Index

Core (Initial / v1 track)

ID	Feature
F1	Universal Allocation API
F2	Arena Memory System
F3	Memory Pools
F4	Slab Allocator
F5	Buddy Allocator
F6	Fragment Memory Engine
F7	Memory Metadata Engine
F8	Memory Profiler
F9	Leak Detector
F10	Heap Visualization
F11	Debug Runtime
F12	Memory Snapshot
F13	Thread Support
F14	Custom Allocation Policies

Future (Post-v1)

ID	Feature
F15	Relocatable Memory Handles
F16	Automatic Fragmentation Optimization
F17	Memory Compression
F18	Persistent Memory
F19	Remote Heap Debugger

F1 — Universal Allocation API

Description

Drop-in memory management interface compatible with the mental model of malloc / free / realloc / calloc.

API

void* umr_malloc(size_t size);
void  umr_free(void* ptr);
void* umr_realloc(void* ptr, size_t size);
void* umr_calloc(size_t count, size_t size);

Behavior

Call	Behavior
`umr_malloc(0)`	Implementation-defined; prefer return `NULL` or unique zero-size sentinel — document one and test it
`umr_free(NULL)`	No-op
`umr_realloc(NULL, n)`	Equivalent to `umr_malloc(n)`
`umr_realloc(ptr, 0)`	Prefer free-and-return-NULL semantics; document clearly
Alignment	At least `alignof(max_align_t)` for general allocations
Failure	Return `NULL`; do not abort unless user installs a failure handler (optional later)

Acceptance

Can replace typical stdlib.h heap usage in example apps
Debug build detects free of non-UMR pointers
Thread-safe when configured for shared heap

F2 — Arena Memory System

Purpose

Extremely fast temporary allocations with bulk lifetime (reset or destroy).

Primary use cases

Game frame memory
Per-request server scratch
Parser / compiler temporary nodes
Algorithm scratch space

Lifecycle

Frame Start
    → arena_alloc … arena_alloc
    → Render / Compute
    → arena_reset   (everything in arena invalidated)
Frame End

API (illustrative)

UMR_Arena* umr_arena_create(size_t initial_capacity /* 0 = default */);
void*      umr_arena_alloc(UMR_Arena* arena, size_t size);
void*      umr_arena_alloc_aligned(UMR_Arena* arena, size_t size, size_t align);
void       umr_arena_reset(UMR_Arena* arena);
void       umr_arena_destroy(UMR_Arena* arena);

Behavior

Bump-pointer allocation within reserved chunks
reset rewinds without returning pages to OS (optional shrink API later)
Individual frees are not supported (document as non-goal for arenas)
Optional growth via additional chunks when capacity exhausted

Acceptance

Alloc + reset of 100k small objects faster than malloc/free churn
Reset invalidates prior pointers (debug mode may poison)

F3 — Memory Pools

Purpose

Repeated allocation of same-sized objects with fast recycle.

Example

10,000 Enemy objects
    → pool_create(sizeof(Enemy))
    → pool_alloc / pool_free reuse
    → pool_destroy

API (illustrative)

UMR_Pool* umr_pool_create(size_t object_size, size_t objects_per_chunk);
void*     umr_pool_alloc(UMR_Pool* pool);
void      umr_pool_free(UMR_Pool* pool, void* ptr);
void      umr_pool_destroy(UMR_Pool* pool);

Behavior

Fixed object size (rounded up for alignment)
Freelist of released objects
Chunks grow as needed
Free of pointer not from pool → debug error

Acceptance

Steady-state alloc/free of fixed objects with low contention options
No unbounded growth when alloc/free balanced (chunk retention policy documented)

F4 — Slab Allocator

Purpose

Fixed-size, high-throughput allocation for hot object types.

Typical uses

Frequently allocated structs
Networking packets / buffer descriptors
Kernel-style object caches (userspace analogue)

Behavior

Maintains slabs of equal-sized slots
Tracks empty / partial / full slabs
Optionally colored or cache-line aware layout

API (illustrative)

UMR_SlabCache* umr_slab_create(const char* name, size_t object_size);
void*          umr_slab_alloc(UMR_SlabCache* cache);
void           umr_slab_free(UMR_SlabCache* cache, void* ptr);
void           umr_slab_destroy(UMR_SlabCache* cache);

Acceptance

Competitive with pool for fixed sizes; clearer multi-size-class story when multiple caches exist
Statistics per cache (allocs, frees, active slabs)

F5 — Buddy Allocator

Purpose

Manage medium/large power-of-two blocks with fast split and merge.

Features

Power-of-two block sizes
Fast splitting when satisfying a request
Fast merging (coalesce buddies) on free
Good fit for region backing and large object sub-management

API (illustrative)

UMR_Buddy* umr_buddy_create(void* base, size_t size); /* size power-of-two preferred */
void*      umr_buddy_alloc(UMR_Buddy* buddy, size_t size);
void       umr_buddy_free(UMR_Buddy* buddy, void* ptr);
void       umr_buddy_destroy(UMR_Buddy* buddy);

Acceptance

Correct buddy pairing under random alloc/free stress
Internal fragmentation bounded by power-of-two rounding (documented)

F6 — Fragment Memory Engine

Description

UMR’s unique differentiator for v1+: explicit internal fragment tracking, split, and merge to reduce fragmentation inside managed regions.

Motivation

Before (high fragmentation):

+----------------------+
|######################|  Used contiguous, then scattered frees leave holes
+----------------------+

After (tracked fragments):

+----+----+-----+------+
|Used|Free|Used |Free  |
+----+----+-----+------+

Capabilities

Operation	Purpose
Split blocks	Carve a free block into allocated + remainder
Merge blocks	Coalesce adjacent free fragments
Track fragments	Metadata for every free/used span
Reduce fragmentation	Policies for placement and coalescing

API (illustrative)

void* umr_fragment_alloc(UMR_FragmentHeap* heap, size_t size);
void  umr_fragment_release(UMR_FragmentHeap* heap, void* ptr);
int   umr_fragment_merge(UMR_FragmentHeap* heap, void* a, void* b); /* or automatic */
void* umr_fragment_split(UMR_FragmentHeap* heap, void* ptr, size_t new_size);

Metrics exposed

Fragmentation percentage
Free block count
Largest free contiguous span
External vs internal fragmentation estimates

Acceptance

Coalescing restores large free spans after interleaved free patterns
Profiler reports fragmentation consistently with heap dump

F7 — Memory Metadata Engine

Description

Every tracked allocation can store rich metadata for tooling and debugging.

Fields

Field	Purpose
Allocation ID	Unique monotonic or recycled ID
Address	Base pointer
Size	Usable size (and optionally capacity)
Thread	Allocating thread id / name
Timestamp	Alloc time (coarse or precise)
Source file	`__FILE__` via macro wrappers
Line number	`__LINE__`
Allocator type	General / arena / pool / slab / buddy / fragment
Status	Active / freed / quarantined

Example record

Block #1234
  Size:       512 bytes
  Created:    renderer.c:72
  Thread:     Main Thread
  Allocator:  general
  Status:     Active

API ergonomics

#define umr_malloc(sz) umr_malloc_debug((sz), __FILE__, __LINE__)
/* or separate umr_malloc_dbg macros in debug builds */

Release builds may omit file/line to save memory and cycles.

Acceptance

Debug build can answer “who allocated this pointer?”
Metadata overhead configurable

F8 — Memory Profiler

Description

Runtime and CLI statistics for live heap health.

CLI

umr stats

Example output

Total Memory:     512 MB
Active:           380 MB
Free:             132 MB
Fragmentation:    4%
Allocations:      12043
Peak Active:      410 MB

In-process API (illustrative)

typedef struct UMR_Stats {
    size_t total_bytes;
    size_t active_bytes;
    size_t free_bytes;
    double fragmentation_ratio;
    uint64_t allocation_count;
    uint64_t free_count;
    size_t peak_active_bytes;
} UMR_Stats;

void umr_stats_get(UMR_Stats* out);

Acceptance

Numbers reconcile with sum of live allocations ± documented accounting rules
Low overhead in sampling mode

F9 — Leak Detector

Description

Detect forgotten frees, unbounded growth, and dead allocations still marked live.

Detects

Allocations never freed at shutdown (or at checkpoint)
Suspicious growth trends (optional)
Dead allocations (allocated, never used — heuristic / future)

Example report

LEAK FOUND
  Address:  0xFFFF12
  Size:     2048 bytes
  Location: texture.c:120
  Thread:   Main
  Allocator: general

API (illustrative)

void umr_leak_check(void);           /* report to stderr / callback */
size_t umr_leak_count(void);
void umr_leak_set_callback(...);

Acceptance

Intentional leak in tests is reported with correct file/line when macros used
Arenas: only report arena itself if not destroyed, not every bump pointer

F10 — Heap Visualization

Description

Human-readable view of used vs free spans.

CLI

umr visualize

Example output

█████░░████████░░███
Used = █  Free = ░

Region 0 @ 0x10000000 size 64MiB
  [0x10000000 +0x0000) used  4KiB
  [0x10001000 +0x1000) free 12KiB
  ...

Acceptance

Visualization matches metadata and fragment maps
Works for multi-region heaps

F11 — Debug Runtime

Description

Hardening checks for incorrect memory API use.

Detects

Bug	Example / note
Double free	`free(ptr); free(ptr);`
Buffer overflow	Canaries / guard pages / sized memcpy hooks
Memory corruption	Metadata checksum / redzones
Invalid pointer	Pointer not belonging to any UMR heap
Use after free	Quarantine freelist (debug)

Modes

Fast debug: canaries + freelist validation
Strict: guard pages, quarantine, full tracking
Release: checks compiled out or minimal

Acceptance

Double free aborts or calls user error handler with diagnostics
Cross-allocator free detected in debug

F12 — Memory Snapshot

Description

Capture and restore (or inspect) runtime heap state for debugging and tools.

API (illustrative)

int umr_snapshot_save(const char* path);
int umr_snapshot_load(const char* path); /* inspect or advanced restore — scope carefully */

Behavior notes

Save: serialize metadata + optional content pages
Load for analysis: tools read snapshot without mutating live process
Load for restore: experimental; full process restore is hard — document as best-effort / debug-only

Acceptance

Saved snapshot can be rendered by umr visualize offline
Format versioned for forward compatibility

F13 — Thread Support

Description

Scale allocation across threads without global lock bottlenecks.

Features

Feature	Benefit
Thread-local heaps	Reduce contention
Lock-free allocation paths	Hot size classes
Per-thread cache	Magazines / thread caches of free objects
Shared heap fallback	Cross-thread free handling

Acceptance

Multi-threaded stress test (N threads alloc/free) without TSan races
Throughput scales with threads up to a documented plateau

F14 — Custom Allocation Policies

Description

Preset policies tuning the runtime for different operational goals.

Policy	Intent
`UMR_POLICY_FAST_MODE`	Maximize throughput; keep caches warm; defer returning memory to OS
`UMR_POLICY_LOW_MEMORY_MODE`	Aggressively release pages; tighter caches; prefer denser packing
`UMR_POLICY_REALTIME_MODE`	Bound worst-case alloc latency; avoid unpredictable syscalls on hot path
`UMR_POLICY_DEBUG_MODE`	Max checking, poisoning, quarantine, full metadata

API (illustrative)

void umr_set_policy(UMR_Policy policy);
UMR_Policy umr_get_policy(void);

Acceptance

Switching policy changes observable behavior (e.g., RSS growth vs reclaim)
DEBUG_MODE enables leak + double-free checks by default

Future Advanced Features

F15 — Relocatable Memory Handles

Instead of raw void*, UMR provides:

typedef struct UMR_Handle { uint64_t id; } UMR_Handle;

UMR_Handle umr_handle_alloc(size_t size);
void*      umr_handle_resolve(UMR_Handle h); /* pin / critical section semantics TBD */
void       umr_handle_free(UMR_Handle h);

Allows: memory movement, compaction, defragmentation without silent invalidation of unpinned pointers.

Constraint: Existing C code using raw pointers cannot be transparently relocated — this is an opt-in API.

F16 — Automatic Fragmentation Optimization

Fragmentation increasing
        ↓
Observe via profiler
        ↓
Change allocation strategy / compact handles
        ↓
Optimize memory layout

Runtime-driven policy adaptation based on live metrics.

F17 — Memory Compression

Compress cold pages or regions that have not been touched recently; decompress on access (fault / explicit pin). Targets large heaps with sparse hot sets (caches, editors, games with streamed worlds).

F18 — Persistent Memory

Regions that survive process restart (memory-mapped files, PMDK-style integration, or custom checkpoint formats). Useful for databases and long-lived services.

F19 — Remote Heap Debugger

Visualize and query another machine’s or process’s UMR heap over a secure debug channel (snapshot stream + metadata queries). Builds on F8–F12 tooling.

Feature Dependencies (Simplified)

F1 Universal API
 ├── F7 Metadata ──────────────┬── F8 Profiler
 │                            ├── F9 Leak Detector
 │                            ├── F10 Visualization
 │                            └── F12 Snapshot
 ├── F2 Arena
 ├── F3 Pool
 ├── F4 Slab
 ├── F5 Buddy
 ├── F6 Fragment ─────────────── F15 Handles / F16 Auto-optimize
 ├── F11 Debug Runtime
 ├── F13 Threads
 └── F14 Policies

Non-Features (Explicit)

These are not features of the initial UMR product:

Garbage collection
Automatic rewriting / moving of raw C pointers
Replacing the OS virtual memory subsystem
Requiring a custom compiler

See vision.md § Non-Goals.

Phase 2 — When to Use Which Allocator

This section provides practical guidance for choosing the right engine. All four allocators are independent; they can coexist in the same program without interfering with each other or with the general umr_malloc heap.

F2 — Arena: bulk temporary allocation

Use when:

Objects share a single logical lifetime (a request, a frame, a parse pass).
You allocate many small objects quickly and discard them all at once.
Individual free() calls are never needed (or would be error-prone).
You want the absolute lowest per-allocation overhead (a pointer bump).

Avoid when:

Objects have independent, unpredictable lifetimes.
You need to free a single object without invalidating others.
Total allocation volume across one reset cycle is unbounded (the arena retains its OS chunks across resets; use umr_arena_destroy + recreate if you need to shrink).

API quick-start:

umr_arena_t* arena = umr_arena_create(0);           // 0 = default 1 MiB chunk

void* p = umr_arena_alloc(arena, sizeof(MyNode));   // bump alloc
void* q = umr_arena_alloc_aligned(arena, 256, 64);  // SIMD-aligned alloc

umr_arena_reset(arena);    // invalidate all; retain OS memory for reuse
umr_arena_destroy(arena);  // release everything

Typical scenarios:

Game frame scratch memory (reset every frame).
Per-HTTP-request scratch heap in a server.
Compiler AST nodes (reset per compilation unit).
Temporary graph/tree nodes in algorithms.

F3 — Pool: fixed-size object recycling

Use when:

You repeatedly allocate and free objects of the exact same type/size.
You want O(1) alloc and free with a warm freelist (no OS calls after warm-up).
Object lifetime is per-instance (each object freed independently).
Object size is known at pool creation time.

Avoid when:

Objects come in multiple sizes (use separate pools or the slab cache).
The total number of live objects is completely unbounded and unpredictable (the pool only grows, never shrinks — use umr_pool_destroy to reclaim).

API quick-start:

umr_pool_t* pool = umr_pool_create(sizeof(Enemy), 256);  // 256 objects/chunk

Enemy* e = (Enemy*)umr_pool_alloc(pool);   // O(1) from freelist
// ... use e ...
umr_pool_free(pool, e);                    // O(1) back to freelist

umr_pool_destroy(pool);

Typical scenarios:

Game entity pools (enemies, bullets, particles).
Network connection / socket descriptor recycling.
Message / event object pools in message-passing systems.
Any hot allocation path where the type is fixed.

Pool vs Slab: Pool is simpler and slightly faster for a single object type. Slab adds named caches and partial/full/empty list management — prefer Slab when you have many object types, want per-cache statistics, or need the empty-slab reclamation behaviour.

F4 — Slab: named object caches with slab-level management

Use when:

You have multiple named object types that each benefit from their own pre-warmed slab (similar to Linux kernel kmem_cache).
You want automatic return of fully-empty slabs to the OS (bounded by UMR_SLAB_MAX_EMPTY_KEEP), balancing reuse against memory pressure.
Per-cache statistics (live count, slab count) are useful for observability.
You want partial/full slab tracking so allocation always hits a warm slab.

Avoid when:

You have a single hot object type and don't need the overhead of partial/full/empty list management — use Pool instead.
Object sizes vary widely — use the general umr_malloc heap.

API quick-start:

umr_slab_cache_t* cache = umr_slab_create("conn_state", sizeof(ConnState));

ConnState* c = (ConnState*)umr_slab_alloc(cache);   // from partial slab
// ... use c ...
umr_slab_free(cache, c);                            // returned to slab freelist

printf("live=%llu slabs=%llu\n",
       (unsigned long long)umr_slab_live_count(cache),
       (unsigned long long)umr_slab_count(cache));

umr_slab_destroy(cache);

Typical scenarios:

Kernel-style object caches (user-space analogue).
Network packet descriptors / buffer headers.
Database row / tuple descriptors.
Any workload needing per-type memory isolation and stats.

F5 — Buddy: power-of-two region management

Use when:

Allocations are variable-sized but known to be roughly powers of two (textures, GPU buffers, DMA descriptors, large OS-mapped regions).
You want fast split-and-merge with bounded internal fragmentation (worst case: 2× the requested size, best case: exact fit).
You are sub-allocating from a fixed-size backing region (GPU memory, NUMA-local pool, huge pages) that you manage separately.
You need a self-contained region allocator that does not touch the OS once created.

Avoid when:

Allocations are uniformly tiny and fixed-size — Pool or Slab are faster.
The workload has many small allocations with no predictable size pattern — the 2× worst-case rounding will waste significant memory.
You need zero fragmentation — Buddy cannot achieve this; use Arena instead.

API quick-start:

// Mode 1: buddy manages its own OS memory
umr_buddy_t* b = umr_buddy_create(8 * 1024 * 1024);  // 8 MiB pool

void* tex = umr_buddy_alloc(b, 512 * 1024);   // rounded to next pow2 order
void* buf = umr_buddy_alloc(b, 4   * 1024);
umr_buddy_free(b, tex);    // buddy pair merged if free
umr_buddy_free(b, buf);
umr_buddy_destroy(b);

// Mode 2: buddy over caller-supplied memory (must be power-of-two size)
void* region = mmap_gpu_memory(4 * 1024 * 1024);
umr_buddy_t* b2 = umr_buddy_create_from(region, 4 * 1024 * 1024);
// ... use b2 ...
umr_buddy_destroy(b2);   // does NOT free region

Typical scenarios:

GPU / graphics memory sub-allocator.
DMA coherent buffer management.
Large-object backing store (complement to the general allocator's large-object path).
NUMA-aware sub-heap carved from a large mmap reservation.

Summary: choosing an allocator

Scenario	Recommended allocator
Per-frame / per-request scratch, bulk lifetime	Arena
Single fixed-size type, hot recycle path	Pool
Multiple named fixed-size types, per-cache stats	Slab
Variable power-of-two regions, GPU/DMA sub-alloc	Buddy
Arbitrary sizes, general purpose	`umr_malloc` (general allocator)

All four Phase 2 allocators are fully thread-safe at the application level when each arena/pool/cache/buddy is accessed from a single thread, or when the caller provides external synchronisation. They do not share state with the global umr_malloc heap.

Phase 3 — Intelligence Layer Guide

This section describes when and how to use the Phase 3 observability tools.

Allocation Tracker (F7)

The tracker is a hash map (pointer → metadata) that records every live allocation. It is disabled by default so there is zero overhead in production builds unless you opt in.

When to enable:

Debugging a leak in development or CI.
Profiling hot allocation sites by type or call location.
Building observability dashboards via the JSON dump.

When to leave disabled:

Production steady-state where the overhead (hash map insert/remove per alloc/free) is unacceptable.
Very high-throughput workloads — use sampling mode instead.

API quick-start:

umr_tracker_enable();          // start recording
// ... run workload ...
umr_leak_print(stdout);        // show what's still live
umr_leak_clear();              // reset baseline
umr_tracker_disable();         // stop recording

Sampling mode — record only 1 in N allocations to reduce overhead:

umr_tracker_enable();
umr_tracker_set_sample_rate(16);  // 1-in-16
// ... high-throughput section ...
umr_tracker_set_sample_rate(1);   // back to full coverage

Sampling trades completeness for throughput. At rate=16 overhead drops to roughly 1/16 of full tracking. Leaks in the unsampled fraction will not be detected; use sampling only for profiling, not correctness checking.

Leak Detector (F9)

The leak detector scans the tracker's live set and reports allocations that were never freed.

Contract: anything in the tracker at report time is a leak. Use umr_leak_clear() to establish a "clean baseline" if your program has intentional long-lived allocations.

Automatic shutdown report: umr_shutdown() calls umr_leak_detector_on_shutdown() internally. If the tracker is enabled and the live count is > 0, it prints to stderr automatically — no extra code needed.

Programmatic check:

umr_leak_entry_t entries[64];
umr_leak_report_t report = {
    .entries  = entries,
    .capacity = 64,
};
size_t n = umr_leak_check(&report);
if (n > 0) {
    printf("%zu leaks, %zu bytes\n", report.count, report.total_bytes);
    for (size_t i = 0; i < report.count; ++i) {
        printf("  %p  %zu bytes\n",
               report.entries[i].ptr, report.entries[i].size);
    }
}

Baseline workflow (exclude intentional long-lived allocations):

umr_tracker_enable();
// allocate long-lived objects ...
umr_leak_clear();               // declare these as "expected"
// run the section under test ...
size_t n = umr_leak_check(NULL); // only sees allocations after clear

Heap Visualizer (F10)

Four output functions — all write to a FILE* (stdout if NULL):

Function	Output
`umr_viz_print_stats(f)`	Extended stats block with per-engine breakdown
`umr_viz_print_heatmap(f, cols)`	ASCII span occupancy map
`umr_viz_print_tracker(f)`	Chronological live allocation table
`umr_viz_dump_json(f)`	Machine-readable JSON snapshot

Heatmap legend:

'.' empty  'l' low(1-25%)  'm' mid(26-50%)  'h' high(51-75%)  'F' full  'L' large

A heatmap full of 'F' cells means spans are heavily occupied; many '.' cells mean fragmented but low-occupancy spans. Repeated 'F' followed by '.' after frees indicates good span reuse.

JSON snapshot is useful for tooling integration:

umr-cli json > heap-snapshot.json

Statistics API (`umr_stats_*`)

The stats API is always available regardless of tracker state.

Function	Description
`umr_stats_get(out)`	Copy current stats under heap lock
`umr_stats_reset()`	Zero counters (does not free memory)
`umr_stats_print(f)`	Print the basic stats table
`umr_viz_print_stats(f)`	Extended version with per-engine breakdown

Key fields:

active_bytes — bytes in live user allocations right now.
peak_active_bytes — high-water mark; never decreases.
live_count — number of currently live allocations.
allocation_count / free_count — cumulative totals (useful for rate calculation over a time window).
mmap_count / munmap_count — OS reservation operations; high ratios indicate span churn.

umr-cli Tool

The umr-cli binary links against libumr and exercises the in-process observability API. It is designed to be embedded in test harnesses and CI pipelines.

umr-cli stats                    # extended stats
umr-cli leaks --enable-tracker   # leak report (exit 2 if leaks found)
umr-cli heatmap 80               # ASCII heatmap at 80 columns
umr-cli tracker --enable-tracker # live allocation table
umr-cli json                     # JSON to stdout

Exit codes: 0 = success, 1 = usage error, 2 = leaks detected.

Performance notes

Mode	Overhead per alloc/free
Tracker disabled (default)	~0 ns (branch not taken)
Tracker enabled, full	~50–200 ns (hash map insert/remove)
Tracker enabled, rate=16	~5–15 ns (sampling guard + occasional insert)

The tracker table is backed entirely by umr_os_alloc() so it never interferes with the allocations it tracks. Rehashing (when load > 75%) doubles the table and discards tombstones; it is amortised O(1) per insertion.

Phase 4 — Fragment Runtime Guide

The fragment engine is UMR's differentiating capability: explicit fragment management with immediate coalescing and quantifiable fragmentation metrics.

F6 — Fragment Heap

The fragment heap manages a single contiguous region using boundary-tag blocks. Each block carries a header and a footer so that both the previous and next contiguous block can be found in O(1), enabling immediate coalescing on every release call.

When to use:

You have a fixed-size memory budget (embedded, GPU VRAM, network buffer pool) and need to sub-allocate from it with minimal waste.
Variable-sized allocations are made and freed in unpredictable order and you need explicit control over fragmentation.
You want to measure and compare fragmentation ratios under different search strategies.
You are building a custom memory region for a subsystem and want fine-grained observability.

When to avoid:

A single object type — use Pool or Slab instead.
Bulk-lifetime temporary allocations — use Arena.
You need true compaction with zero external fragmentation — see the Relocatable Memory design note.

Search strategies

Choose the strategy at creation time based on your workload:

Strategy	`umr_frag_strategy_t`	Best for	Fragmentation
First-fit	`UMR_FRAG_FIRST_FIT`	Fast alloc, low overhead	Tends to fragment the front of the region
Best-fit	`UMR_FRAG_BEST_FIT`	Minimise wasted space per alloc	Slower (full scan), better long-term
Segregated	`UMR_FRAG_SEGREGATED`	High-throughput mixed sizes	O(1) amortised, lowest average waste

For most workloads, segregated is the right default. Use best-fit when the allocation pattern is known to be irregular and minimising waste is the primary goal. Use first-fit when raw allocation speed is more important than fragmentation.

API quick-start

/* Create a 4 MiB region with segregated free-lists. */
umr_fragment_heap_t* heap =
    umr_fragment_heap_create(4 * 1024 * 1024, UMR_FRAG_SEGREGATED);

void* p = umr_fragment_alloc(heap, 1024);   /* O(1) amortised     */
void* q = umr_fragment_alloc(heap, 4096);

umr_fragment_release(heap, p);              /* immediate coalesce  */

/* Resize without copy when possible. */
q = umr_fragment_resize(heap, q, 8192);

/* Inspect fragmentation. */
umr_frag_metrics_t m;
umr_fragment_metrics_get(heap, &m);
printf("ext_frag=%.1f%%  largest_free=%zu\n",
       m.external_frag_ratio * 100.0, m.largest_free_block);

umr_fragment_metrics_print(heap, stdout);   /* full table          */
umr_fragment_release(heap, q);
umr_fragment_heap_destroy(heap);

/* Caller-supplied region (e.g. GPU-visible memory). */
void* gpu_mem = map_gpu_memory(2 * 1024 * 1024);
umr_fragment_heap_t* gpu_heap =
    umr_fragment_heap_create_from(gpu_mem, 2 * 1024 * 1024,
                                   UMR_FRAG_BEST_FIT);
/* ... use gpu_heap ... */
umr_fragment_heap_destroy(gpu_heap);   /* does NOT unmap gpu_mem */

Fragmentation metrics

umr_fragment_metrics_get() performs a full block walk to compute:

Field	Meaning
`live_bytes`	Sum of payload bytes in allocated blocks
`free_bytes`	Sum of payload bytes in free blocks
`overhead_bytes`	Sum of header + footer bytes across all blocks
`largest_free_block`	Payload size of the largest single free block
`free_block_count`	Number of separate free blocks
`external_frag_ratio`	`1 - (largest_free / total_free)`; 0 = no fragmentation
`internal_frag_ratio`	`overhead / region_size`; fixed cost of the boundary-tag scheme

Interpretation:

external_frag_ratio = 0.0 means all free space is one contiguous block (ideal after a full coalesce).
external_frag_ratio = 0.5 means half the free space is inaccessible to a request larger than largest_free_block.
internal_frag_ratio is roughly constant for a given region size and block count; it decreases as blocks are merged.

Coalescing behaviour

Every umr_fragment_release() immediately checks both neighbours:

Before:  [ A: LIVE ][ B: LIVE ][ C: FREE ][ D: LIVE ][ E: FREE ]
Release B:
After:   [ A: LIVE ][ B+C: FREE (merged) ][ D: LIVE ][ E: FREE ]
Release D:
After:   [ A: LIVE ][ B+C+D+E: FREE (fully merged) ]

This means external fragmentation is bounded by the number of live allocations rather than accumulated history. As long as you free all allocations, the region returns to a single free block with external_frag_ratio = 0.0.

resize semantics

umr_fragment_resize(heap, ptr, new_size) follows three paths in order:

Shrink or same size — updates user_size in place; O(1), no copy.
Grow by absorbing next free block — if the immediately adjacent block is free and large enough, it is absorbed; O(1), no copy.
Fallback — allocate a new block, memcpy, release old; O(n) copy.

This makes resize efficient for the common case of slightly growing a recent allocation.

Limits vs raw `void*`

The boundary-tag scheme cannot support true memory compaction as long as callers hold raw pointers. Once a pointer is returned by umr_fragment_alloc, the block cannot be moved without invalidating the caller's pointer.

This is a fundamental limitation of C's pointer model. The forward path is a handle-based API (UMR_Handle) documented in docs/relocatable_memory.md.

Performance notes

Operation	Complexity
`alloc` — segregated	O(1) amortised (bucket list scan)
`alloc` — first/best-fit	O(n) live blocks
`release` + coalesce	O(1) — constant neighbour checks
`resize` (shrink / grow-by-absorb)	O(1)
`metrics_get`	O(n) full block walk

The boundary-tag overhead is 2 × (sizeof(header) + sizeof(footer)) per block. On a 64-bit system with 16-byte alignment, this is typically 64–96 bytes per allocation, making the engine unsuitable for allocations smaller than ~128 bytes. For small fixed-size objects, Pool or Slab are better choices.

FilesExpand file tree

feature.md

Latest commit

History

feature.md

File metadata and controls

UMR Features

Feature Index

Core (Initial / v1 track)

Future (Post-v1)

F1 — Universal Allocation API

Description

API

Behavior

Acceptance

F2 — Arena Memory System

Purpose

Primary use cases

Lifecycle

API (illustrative)

Behavior

Acceptance

F3 — Memory Pools

Purpose

Example

API (illustrative)

Behavior

Acceptance

F4 — Slab Allocator

Purpose

Typical uses

Behavior

API (illustrative)

Acceptance

F5 — Buddy Allocator

Purpose

Features

API (illustrative)

Acceptance

F6 — Fragment Memory Engine

Description

Motivation

Capabilities

API (illustrative)

Metrics exposed

Acceptance

F7 — Memory Metadata Engine

Description

Fields

Example record

API ergonomics

Acceptance

F8 — Memory Profiler

Description

CLI

Example output

In-process API (illustrative)

Acceptance

F9 — Leak Detector

Description

Detects

Example report

API (illustrative)

Acceptance

F10 — Heap Visualization

Description

CLI

Example output

Acceptance

F11 — Debug Runtime

Description

Detects

Modes

Acceptance

F12 — Memory Snapshot

Description

API (illustrative)

Behavior notes

Acceptance

F13 — Thread Support

Statistics API (`umr_stats_*`)

Limits vs raw `void*`