OffsetPtr<T> and SharedRegion<T>

A 4-byte position-independent pointer to a typed slot inside a memory-mapped file. Resolves to the same logical value in any process that has the file mapped, regardless of where the OS places each process’s mapping in its address space.

The foundational primitive. Every other cross-process pointer in this crate composes on top of OffsetPtr<T> plus its host SharedRegion<T>. Once this pair is understood, the rest of the family is the same shape with extra metadata bytes bolted on.

Constraints (read first):

• Cross-process / MMF-backed. Requires a writable backing file path. For in-process workloads that never cross a process boundary, prefer a typed-arena crate; the offset encoding buys nothing without a second address space.
• T: Copy + 'static. No Drop glue runs on free. Types with destructors (String, Vec, Box) cannot live in a slot directly.
• Capacity fixed at create. No auto-grow. Size the region for the workload upfront; allocation past capacity returns Err(Full).
• Maximum u32::MAX - 1 slots per region (the 4-byte index plus the reserved NIL sentinel). For larger workloads, partition across regions.
• clear() is not thread-safe. Intended for single-threaded bench setup and test teardown only; calling it concurrent with allocate / free corrupts the free list. All other ops are lock-free.
• Pointer is meaningful only with the region that issued it. An OffsetPtr<T> from region A passed to region B silently resolves to wrong bytes (or returns Err(InvalidPtr) if the index exceeds B’s capacity).

Table of contents

• What it is
• When to reach for it
• Memory layout
• Allocation protocol
• API at a glance
• Worked example
• Benchmark results
• Concurrency and safety
• Known limitations (verified)
• Common pitfalls
• Composition with other primitives

What it is

OffsetPtr<T> is a #[repr(C)] struct with one field:

pub struct OffsetPtr<T> {
    pub index: u32,
    _phantom: PhantomData<T>,
}

Four bytes. Plain old data. Copy. Hash. Equality on the index field. A sentinel OffsetPtr::NIL whose index is u32::MAX.

SharedRegion<T> is the host. It owns the memory-mapped file, the allocator’s bump cursor, and the lock-free free list. An OffsetPtr is meaningful only when paired with the region that issued it. The region resolves the pointer by reading slot[index] out of its mmap.

The position-independent property is the whole point. A raw *const T in one process’s heap is a virtual address that the OS chose at mmap time; another process mapping the same file gets a different base address and the raw pointer dangles as a wild pointer. The 4-byte index does not have that problem: every process resolves index to base_ptr + slots_offset + index * size_of::<T>(), where base_ptr is that process’s own mapping.

When to reach for it

Reach for OffsetPtr<T> + SharedRegion<T> when all of these hold:

• The pointer or the value it points to needs to be visible to more than one process, OR persisted to disk and reloaded later.
• The payload T is Copy + 'static (no Drop glue, no lifetimes).
• The slot count can be picked at allocation time (capacity is fixed at create; it does not auto-grow).
• You want a typed arena with one slot type, not a heterogeneous bump allocator.

Reach for something else when:

• Your data lives in one process and never crosses the boundary. A plain Vec<T> or a typed-arena crate is smaller and faster.
• T has Drop glue. The region does not run drop on free.
• The slot count is unknown and may exceed u32::MAX - 1. The 4-byte index caps total slots at u32::MAX - 1 (one value is reserved for NIL).

Memory layout

The MMF backing file is laid out in three contiguous regions:

    flowchart LR
    H[RegionHeader<br/>64 bytes aligned]
    N["next array<br/>capacity x u32 free-list links"]
    S["slots array<br/>capacity x T payloads"]
    H --> N
    N --> S

    classDef hdr fill:#1e3a8a,stroke:#1e40af,color:#ffffff
    classDef links fill:#7c3aed,stroke:#5b21b6,color:#ffffff
    classDef payload fill:#059669,stroke:#065f46,color:#ffffff
    class H hdr
    class N links
    class S payload
  

The header is a #[repr(C, align(64))] struct that fits in one cache line:

The next[] array sits between header and payloads. Each entry is an AtomicU32 that holds the free-list link when its matching slot is on the free list (and is unused otherwise). Keeping the link out of the payload bytes means T is free to choose any alignment without colliding with allocator metadata.

The slots[] array is just capacity consecutive T values, byte- identical to a Vec<T> of the same length. Resolving an OffsetPtr is one pointer add and one read.

Allocation protocol

Two paths exist: a lock-free Treiber-stack pop from the free list, falling back to an atomic bump-pointer allocation.

    flowchart TD
    Start([allocate value]) --> CheckFree{free_head<br/>has slot?}
    CheckFree -->|yes| LoadHead[Load packed head<br/>counter and index]
    LoadHead --> ReadNext[Read next index<br/>from next array]
    ReadNext --> CASFree[CAS free_head to<br/>counter+1, next_index]
    CASFree -->|win| WriteSlotF[Write value to slot]
    WriteSlotF --> RetFree([Return OffsetPtr index])
    CASFree -->|lose| LoadHead

    CheckFree -->|no| Bump[bump_next.fetch_add 1]
    Bump --> CheckCap{idx less than<br/>capacity?}
    CheckCap -->|yes| WriteSlotB[Write value to slot]
    WriteSlotB --> RetBump([Return OffsetPtr index])
    CheckCap -->|no| Rollback[Rollback bump_next]
    Rollback --> ErrFull([Return Err Full])

    classDef startend fill:#0e7490,stroke:#0e7490,color:#ffffff
    classDef decision fill:#fbbf24,stroke:#92400e,color:#1f2937
    classDef action fill:#1e40af,stroke:#1e3a8a,color:#ffffff
    classDef errpath fill:#b91c1c,stroke:#7f1d1d,color:#ffffff
    class Start,RetFree,RetBump,ErrFull startend
    class CheckFree,CheckCap decision
    class LoadHead,ReadNext,CASFree,WriteSlotF,Bump,WriteSlotB action
    class Rollback errpath
  

The free-list path is a classic Treiber stack with one twist: a 32-bit counter is packed into the high half of free_head alongside the 32-bit index. Every push increments the counter, which makes the packed 64-bit word distinct even when the same index repeats. The counter exists to close the ABA race: without it, a thread that reads head = A, sleeps, then races on a CAS may see “A” again even though A has been popped, repushed with a different next link, and the link it remembered is stale. With the counter, the second view of A is a different (counter, A) pair and the CAS fails correctly. A 32-bit counter spans 4 billion pushes before it wraps, which exceeds any realistic concrete race window.

The bump path is fetch_add plus a capacity check. On overflow the bump cursor is rolled back with fetch_sub so a subsequent allocation does not see a stale bump_next > capacity.

API at a glance

Worked example

use subetha_cxc::{OffsetPtr, SharedRegion};

let region: SharedRegion<u64> = SharedRegion::create("/tmp/example.bin", 1024)?;

// Allocate two slots.
let a = region.allocate(42).expect("region full");
let b = region.allocate(99).expect("region full");

// Read them back.
assert_eq!(region.get(a)?, 42);
assert_eq!(region.get(b)?, 99);

// Free a, then allocate again. The free-list LIFO returns the same slot.
let v = region.free(a)?;
assert_eq!(v, 42);
let c = region.allocate(777).expect("region full");
assert_eq!(c.index, a.index);  // slot reused

// A second process can open the same file and resolve the same OffsetPtr.
// (run in a separate process)
// let reader: SharedRegion<u64> = SharedRegion::open("/tmp/example.bin", 1024)?;
// assert_eq!(reader.get(OffsetPtr::new(c.index))?, 777);

Benchmark results

Comparison baseline: MutexArena<T> = { Mutex<Vec<T>>, Mutex<Vec<usize>> }, the textbook in-process typed-arena + free-list pattern. The baseline takes one parking_lot::Mutex lock per allocate and per free. The SharedRegion path uses lock-free fetch_add on the bump cursor or a Treiber CAS on the free list.

Numbers are median of 10 samples, 2-second measurement window, on Windows x86-64. Each iteration is one operation. Lower is faster.

Why each result lands where it does

Concurrency and safety

Known limitations (verified)

These are limitations that exist in the shipped code as of this writing. Each is observable in the source.

1. Capacity is fixed at create and never grows. The MMF file length is set once. An attempt to allocate beyond capacity returns Err(Full). Callers must size the region for the workload upfront.

2. Maximum slot count is u32::MAX - 1. The 4-byte index plus the reserved NIL_INDEX = u32::MAX sentinel caps a single region at 4 294 967 294 slots. For workloads beyond this, partition across multiple regions.

3. T: Copy + 'static. Drop glue is not run on free. Types with destructors (e.g. String, Vec, Box) cannot live in a SharedRegion directly. For variable-length data, store an OffsetPtr into a separate SharedRegion<u8> or SharedStringArena.

4. clear() is not thread-safe. See the table above. Concurrent ops with clear will corrupt the free-list invariant.

5. No drop integration with the file lifecycle. When the last SharedRegion is dropped, the file is unmapped but not deleted. Callers manage file cleanup explicitly.

6. The free-list link array costs 4 * capacity extra bytes compared to a union’d-link allocator. The design trade is layout simplicity for any T alignment versus the extra storage.

7. Re-opening a region does not validate the free-list. open checks magic, capacity, and slot_size from the header. If the next[] array is corrupt, allocation will still proceed but may return overlapping pointers. There is no integrity check on the free chain at open time.

8. clear does not zero the slot payloads. Subsequent allocate writes overwrite each slot before returning the pointer, so callers never observe stale payload bytes via the normal allocate then get path. A stray reader holding a stale OffsetPtr after clear will read whatever bytes happened to be in that slot at clear time.

Common pitfalls

let ptr = region.allocate(42)?;
region.free(ptr)?;
// At this point ptr.index may be sitting on the free list. If
// another thread reallocates into the same slot before this thread
// calls get, the get sees the new value, not 42.
let _ = region.get(ptr);  // races with concurrent allocate

Composition with other primitives

OffsetPtr + SharedRegion is the base of these other primitives in this crate:

Every pointer-graph data structure in the crate uses some variant of this pattern. The OffsetPtr index is the universal way to talk about a slot, and the SharedRegion is the universal way to host slots that other processes can see.

back to subetha docs