Relocatable Memory and UMR_Handle — Design Note

Status: Experimental / Future Work
Phase: 4 research deliverable (feeds Phase 5 / post-v1)
Author: UMR Engineering

1. Problem Statement

All UMR allocators (general, arena, pool, slab, buddy, fragment) return raw void* pointers. This is ergonomic and compatible with every C API, but it creates a fundamental constraint: allocated memory cannot be moved after the pointer is handed to the caller.

The consequence for the fragment engine is that true compaction — rearranging live blocks to eliminate external fragmentation — is impossible as long as callers hold direct pointers. A "compact" function could defragment the region, but it would invalidate every pointer the caller has cached, so it cannot be called safely.

2. The Raw-Pointer Limit

Heap region:
  [ LIVE A ][ FREE ][ LIVE B ][ FREE ][ LIVE C ][ FREE ]

Ideal compact:
  [ LIVE A ][ LIVE B ][ LIVE C ][ FREE (large) ]
  ^                             ^
  A's address unchanged         B now at A+sizeof(A) — callers crash

Any code that stored ptr_to_B is now pointing at invalid memory. There is no safe mechanism in standard C to notify all holders of a pointer that it has moved — the language has no pointer-update protocol.

3. The Handle Approach

The classical solution is to replace void* with an indirect handle:

typedef struct { uint32_t id; } UMR_Handle;

void* umr_handle_lock(UMR_Handle h);    /* pin, get pointer  */
void  umr_handle_unlock(UMR_Handle h);  /* unpin, allow move */

Between unlock and the next lock, the runtime is free to relocate the underlying block. The caller only accesses the pointer inside a locked section.

3.1 Implementation sketch

Handle table (separate from managed region):
  id → { current_ptr, pin_count }

umr_handle_alloc(heap, size) → UMR_Handle {
    ptr = fragment_alloc(heap, size)
    id  = handle_table_insert(ptr)
    return (UMR_Handle){ id }
}

umr_handle_lock(h) → void* {
    entry = handle_table[h.id]
    entry.pin_count++
    return entry.current_ptr
}

umr_handle_unlock(h) {
    entry.pin_count--
    if (entry.pin_count == 0 && compact_requested) {
        /* Safe to move this block on next compaction pass. */
    }
}

umr_compact(heap) {
    for each unpinned live block in address order:
        dst = earliest free gap that fits
        memmove(dst, src, block_size)
        update handle_table[block_id].current_ptr = dst
        mark src as free, merge
}

3.2 Complexity

Operation	Complexity
`handle_alloc`	O(1) + hash insert
`handle_lock`	O(1) hash lookup
`handle_unlock`	O(1)
`compact`	O(n) block walk + O(k) memmove calls

4. Limits and Trade-offs

Concern	Impact
Pin granularity	Every access requires a lock/unlock pair — ergonomic burden, not zero cost.
Interior pointers	Pointers into the middle of a block (array element, struct field) break the handle abstraction.
C ABI compatibility	Third-party APIs that accept `void*` cannot use handles without an adaptor.
Concurrent compaction	If any thread holds a lock, that block cannot move; compaction must walk all threads' pin sets.
Debug complexity	Dangling raw pointers obtained from a prior lock are impossible to detect without instrumentation.

These are the reasons handles are listed as future / experimental rather than implemented today. For most use cases, the fragment engine's immediate coalescing already reduces external fragmentation to a low level without requiring compaction.

5. When Compaction Is Actually Needed

The fragment engine (Phase 4) with immediate coalescing handles the common case well. Compaction becomes necessary only when:

The allocation pattern is highly adversarial (many small long-lived allocations interspersed with large short-lived ones that leave unpredictable holes).
The working set must fit within a hard memory budget (embedded, console, GPU VRAM).
Allocations are large relative to the region and a single large request must succeed even when fragmented.

For case 3, the buddy allocator (Phase 2) is often a better architectural choice because it avoids external fragmentation by design at the cost of internal fragmentation (power-of-two rounding).

6. Prototype Path toward UMR_Handle

A production-quality handle system would require:

Handle table module (fragment/handle_table.c):
- Open-addressing hash map: id → { ptr, pin_count, size }.
- Thread-safe under a dedicated mutex (separate from the region lock).
- IDs are monotonic 32-bit integers; recycled via a freelist.
Pin protocol (umr_handle_lock / umr_handle_unlock):
- Lock increments pin_count; unlock decrements.
- Unlock triggers a deferred compact if compact_pending is set.
Compaction pass (umr_fragment_compact):
- Walk the region in address order.
- For each unpinned live block: find the earliest free block that fits; memmove; update handle table; zero-fill old location in debug builds.
- After the pass: merge all remaining free blocks.
Experimental header (include/umr/experimental/umr_handle.h):
- Marked UMR_EXPERIMENTAL to signal unstable ABI.
- Separate from the stable umr.h.

7. Interaction with Phase 3 Tracker

The tracker (Phase 3) already stores ptr → { size, type, id }. For handle-based allocations the tracker's ptr field would need to be updated on every compaction move, or replaced by the handle ID as the key.

This is one of several reasons why the handle system is designed as a separate layer on top of the fragment engine rather than woven into it. The fragment engine itself remains pointer-based and tracker-compatible.

8. Summary

Approach	Fragmentation	Compaction	C compatible	Complexity
Fragment engine (Phase 4)	Reduced by coalescing	No	Yes	Low
Buddy allocator (Phase 2)	Bounded by pow2	No	Yes	Low
Handle system (future)	Eliminated	Yes	Adaptors needed	High

The Phase 4 fragment engine delivers the best balance for the initial release. The handle system is documented here as the forward path when applications need guaranteed zero external fragmentation.

This document is a design note, not a specification. API shapes shown above are illustrative and subject to change.

FilesExpand file tree

relocatable_memory.md

Latest commit

History