Skip to content

01_spec_cpp_memory_pool.md

Latest commit

 

History

History
239 lines (164 loc) · 16.3 KB

01_spec_cpp_memory_pool.md

File metadata and controls

239 lines (164 loc) · 16.3 KB
Raw

Software Specification: Purpose-built reference High-Performance Memory Pool Manager (C/C++)

Status — reconciled with the as-built system. This document was originally a short greenfield brief. The library has since shipped (public API frozen at v1.0.0) and every non-trivial decision is recorded in an Architecture Decision Record. Each requirement below now cross-links the ADR(s) that realize it; Section 7 maps the whole specification to its ADRs and lists the explicitly deferred items.

1. Objective & Business Context

Many high-performance systems (e.g. graphics engines, financial trading servers, databases) suffer from memory fragmentation and the overhead generated by frequent malloc/free or new/delete calls. This component provides a custom memory allocator (Memory Pool) that pre-allocates a contiguous block of memory, handling the allocation and deallocation of fixed-size blocks in constant time $O(1)$ with zero external fragmentation.

Fragmentation scope (precise claim). Fixed-size blocks eliminate external fragmentation within a pool: any free block satisfies any request, so free memory never degrades into unusable holes. The pool does not eliminate internal fragmentation — a caller that stores an object smaller than block_size wastes the difference. Choosing block_size to match the dominant object size is the caller's responsibility; the pool trades internal fragmentation for $O(1)$ determinism and zero external fragmentation by design.

2. Functional Requirements

2.1 Initialization

The system pre-allocates a memory pool, specifying the block size (block_size) and the maximum number of blocks (block_count). The block_size * block_count product must not overflow size_t; the constructor rejects overflow and degenerate arguments. See ADR-0009.

2.2 Allocation ($O(1)$)

Return a pointer to a free block in constant time. When the pool is exhausted the behaviour depends on the growth mode:

  • Fixed pool (default): return NULL (C) or throw (C++ wrapper, ADR-0016).
  • Dynamic pool: acquire a new, separate contiguous chunk and satisfy the request from it. The growth strategy is non-contiguous chunked expansion via a linked chunk list — the pool is not a single contiguous region once it has grown, and it never relocates: every previously returned pointer stays valid across growth (no realloc-style invalidation). Growth is geometric (a configurable factor). Consequently, pointer-range validation (Section 6.1) is a multi-chunk membership test, not a single range check. This resolves the original brief's ambiguity in favour of chunk-linking over address-space reserve-and-commit. See ADR-0022, ADR-0023, ADR-0024.

2.3 Deallocation ($O(1)$)

Mark a previously allocated block available again in constant time, without returning it to the operating system immediately. Freeing NULL or a pointer foreign to the pool is a defined, silent no-op; see Section 5.3 and ADR-0012.

2.4 Thread Safety

Concurrent access is governed by a compile-time policy knob (PBR_MEMORY_POOL_THREAD_SAFETY) selecting one of three strategies, so single-thread users pay nothing:

  • NONE — single-threaded fast path (intentionally racy; never share such a pool across threads);
  • MUTEX — a mutex guards the free list;
  • LOCKFREE — a Treiber-stack free list whose head is an ABA-tagged pointer ({pointer, tag}, the tag incremented on every CAS) so the classic ABA hazard on a LIFO free list cannot mis-link.

See ADR-0020. A contended, multi-thread benchmark exists (Section 6.3).

3. Non-Functional Requirements

3.1 No Memory Leaks

When the pool is destroyed, all pre-allocated memory (every chunk, for a grown pool) is returned to the operating system. Verified under Valgrind and the sanitizers (Section 6).

3.2 Minimal Memory Overhead

Free blocks carry zero per-block metadata — the free-list next-pointer is stored in-band inside the free block (Section 4). The only fixed cost is one pool-header struct plus, for dynamic pools, one small descriptor per chunk. The per-pool metadata budget is quantified and guarded in ADR-0015.

3.3 Compatibility

Written to standard ANSI C ABI (the four-function surface) with an idiomatic C++17 wrapper layer, no external runtime dependencies. Toolchain matrix and supported platforms: ADR-0005.

4. Logical Architecture & Algorithm (Free List)

The pool manages free memory using a Free List implicit within the blocks themselves. When a block is free, its first bytes store a pointer to the next free block. This zeroes the metadata overhead for unused blocks.

+-------------------------------------------------------------------+
|                           Memory Pool                             |
+-------------------------------------------------------------------+
| [Block 1 (Free)]      -> Holds a pointer to Block 2               |
| [Block 2 (Allocated)] -> Holds user data                         |
| [Block 3 (Free)]      -> Holds a pointer to Block 4               |
| [Block 4 (Free)]      -> Holds NULL (end of list)                 |
+-------------------------------------------------------------------+

4.1 Constraints & Guarantees

Storing a next-pointer in-band imposes constraints, all enforced by the implementation (ADR-0009):

  • Minimum block size: block_size >= sizeof(void*) — the constructor rejects smaller sizes.
  • Alignment: every returned pointer is aligned to alignof(std::max_align_t), uniformly. A weaker or caller-specified per-pool alignment was considered and deliberately rejected (the frozen C signature carries no alignment parameter; uniform strong alignment keeps TypedPool<T> a trivial cast).
  • Strict-aliasing-safe access: the in-band pointer is read/written through the canonical *static_cast<void**>(slot) idiom, not a type-punning cast of the user type.

The intrusive-free-list design was chosen over a bitmap allocator; the rejected alternative and its rationale are recorded in ADR-0009.

4.2 Component diagram (C4)

The C4-model Component view below relates the public surface, the core engine (which lives behind the opaque memory_pool_t handle / Pimpl), and the operating-system backing store. It is authored in Mermaid per ADR-0041; a viewer without Mermaid support sees the equivalent source. Solid arrows are runtime call / ownership paths; dashed arrows are optional or diagnostic relationships. Bracketed tags name the realizing technology or the design pattern applied.

%% C4 model — Component level for the pbr-cpp-memory-pool library.
%% Authored as a Mermaid flowchart with C4 boundary subgraphs (ADR-0041).
flowchart TB
    app["Consumer application<br/>[C or C++]<br/>fixed-size allocation on a hot path"]

    subgraph lib["pbr-cpp-memory-pool — static library"]
      direction TB
      subgraph surface["Public surface"]
        direction TB
        capi["C API — memory_pool.h [extern C]<br/>frozen 4-function ABI + create_dynamic + introspection"]
        cpp["Pool / PoolBuilder [C++ RAII]<br/>move-only owner; factory / builder construction"]
        adapters["TypedPool&lt;T&gt; · PoolAllocator&lt;T&gt; [templates]<br/>type-safe and STL-allocator adapters"]
        instr["InstrumentedPool [Decorator]<br/>counters + lifecycle Observers"]
        diag["FreeListView [diagnostics, gated]<br/>read-only free-list iterator"]
      end
      subgraph core["Core engine — behind the Pimpl / C ABI"]
        direction TB
        state["memory_pool [Pimpl struct]<br/>backing · head · sizes · chunk list · grow factor"]
        skel["alloc / free skeleton [Template Method]<br/>range-checks, dispatches to the sync policy"]
        policy["Sync policy [Strategy, compile-time]<br/>SingleThreaded / Mutex / LockFree (ABA-tagged Treiber)"]
        freelist["Intrusive free list [LIFO]<br/>in-band next-pointer, zero per-block metadata"]
        chunks["Chunk list [Composite]<br/>non-contiguous geometric growth; pointers stay valid"]
      end
    end

    os[("Backing storage<br/>[over-aligned operator new]<br/>alignof(max_align_t)")]

    app -->|"C ABI"| capi
    app -->|"idiomatic C++"| cpp
    adapters -->|"compose"| cpp
    instr -.->|"decorate"| cpp
    diag -.->|"iterate (gated)"| freelist
    cpp -->|"own via C core"| capi
    capi --> state
    state --> skel
    skel -->|"pop / push"| policy
    policy --> freelist
    skel -->|"grow on exhaustion"| chunks
    chunks -->|"seed a sub-list"| freelist
    chunks --> os
    state --> os
Loading

5. API / Public Interface

5.1 C core (frozen at v1.0.0)

typedef struct memory_pool memory_pool_t;

// Initialize a fixed-capacity memory pool
memory_pool_t* memory_pool_create(size_t block_size, size_t block_count);

// Initialize a dynamically-growing pool (geometric chunk expansion; ADR-0022)
memory_pool_t* memory_pool_create_dynamic(size_t block_size, size_t block_count,
                                           size_t growth_factor);

// Allocate a block from the pool (O(1)); NULL when a fixed pool is exhausted
void* memory_pool_alloc(memory_pool_t* pool);

// Release a block back into the pool (O(1))
void memory_pool_free(memory_pool_t* pool, void* block);

// Destroy the pool, releasing all memory (every chunk) back to the OS
void memory_pool_destroy(memory_pool_t* pool);

The opaque memory_pool_t handle hides the implementation (Pimpl across the C/C++ boundary, ADR-0010).

5.2 C++17 surface

A layered, idiomatic C++ surface built on the C core:

  • Pool — move-only RAII owner; PoolBuilder / factory methods for construction (ADR-0010, ADR-0011).
  • TypedPool<T> — type-safe construct/destroy over the pool (ADR-0017).
  • PoolAllocator<T> — an STL Allocator adapter so the pool can back std::list, std::map, … (ADR-0018).
  • PoolMemoryResource — a std::pmr::memory_resource adapter so one pool can back any std::pmr container via std::pmr::polymorphic_allocator, without the per-type rebind. Header-only and gated behind PBR_MEMORY_POOL_HAS_PMR (compiled where <memory_resource> is available) (ADR-0042).
  • InstrumentedPool — a Decorator adding counters and lifecycle Observers (ADR-0025, ADR-0026).

5.3 Error semantics

  • Freeing NULL — no-op (mirrors C free(NULL)).
  • Freeing a foreign / out-of-range pointer — defined, silent no-op detected in $O(1)$; no corruption (ADR-0012).
  • Double-free — a double-free of an in-range, currently-free block is not detected by the default build (accepted trade-off, documented in ADR-0012); opt-in detection is tracked as future hardening (Section 7).
  • C++ exhaustion — throws per ADR-0016; exceptions never cross the C ABI.

5.4 Introspection

Observability is provided two ways: an optional debug diagnostics surface (compiled out of release, gated by PBR_MEMORY_POOL_DIAGNOSTICS) and the production-usable InstrumentedPool decorator, which exposes live-block count, capacity, and a high-water mark (ADR-0015, ADR-0025).

6. Verification & Test Strategy

6.1 Correctness Tests

Allocate all blocks until exhaustion; verify behaviour with null inputs and pointers foreign to the pool (defined no-op, Section 5.3). For dynamic pools, verify that pointers remain valid across a growth event and that foreign-pointer validation is a correct multi-chunk membership test.

6.2 Leak Verification (Valgrind)

gcc -g -O0 test_pool.c memory_pool.c -o test_pool
valgrind --leak-check=full --show-leak-kinds=all ./test_pool

Success criterion: ERROR SUMMARY: 0 errors from 0 contexts and definitely lost: 0 bytes in 0 blocks.

6.3 Performance Benchmark

memory_pool_alloc/free are compared against standard malloc/free. The methodology is fixed by ADR-0014: warm-up repeat discarded, min/median/mean/max/stddev reported (not a single wall-clock loop), anti-optimization barriers, disclosed compiler flags and host, per-release reports under docs/bench/, and a non-asserting CI smoke run. A concurrent scenario (T threads on a shared pool, MUTEX vs LOCKFREE) provides the contended baseline.

6.4 Sanitizers & CI

ASan, UBSan and TSan run via dedicated CMake presets; TSan covers the thread-safe configurations. All of the above is wired into a multi-OS CI matrix (warnings-as-errors, clang-tidy, Valgrind). A coverage-guided fuzz target is deferred (Section 7).

7. Implementation Status & Decision Records

Every requirement above is realized and recorded. The table maps the spec to its ADRs.

Spec area Realized by
§2.2 growth model ADR-0022, ADR-0023, ADR-0024
§2.4 thread safety (mutex / lock-free + ABA tag) ADR-0020
§3.2 overhead budget & introspection ADR-0015
§4 free-list layout, constraints, alignment, intrusive-vs-bitmap ADR-0009
§4.2 component (C4) diagram & diagram tooling ADR-0041
§5.1–5.2 API, RAII, Pimpl, builder, typed pool, STL adapter ADR-0010, ADR-0011, ADR-0017, ADR-0018
§5.2 std::pmr adapter (PoolMemoryResource) ADR-0042
§5.3 error semantics ADR-0012, ADR-0016
§5.4 instrumentation / observers ADR-0025, ADR-0026
§6.3 benchmark methodology ADR-0014
Spec-compliance acceptance audit ADR-0029

7.1 Deferred / tracked

These are explicitly out of the current build and tracked as issues:

  • Coverage-guided fuzzing harness (issue #108).
  • Opt-in debug hardening — freed-block poisoning, canaries, free-list safe-linking; would also add double-free detection (issue #109).
  • Benchmark extension — external baselines (jemalloc/tcmalloc) and p99 percentile reporting (issue #111).

The C4 component diagram of the pool internals, once deferred here, now ships in Section 4.2 (its tooling decision is ADR-0041).