Skip to content

plan.md

Latest commit

 

History

History
437 lines (319 loc) · 13.1 KB

plan.md

File metadata and controls

437 lines (319 loc) · 13.1 KB
Raw

UMR Development Plan

Universal Memory Runtime — Roadmap, Phases, and Delivery Plan

Field Value
Version 1.0
Status Implementation Hardening (v0.1)
Language C23
Build CMake + Ninja
CI GitHub Actions (Linux, Windows, macOS)

This document turns the product vision into an executable plan: phases, deliverables, tech stack, testing strategy, and exit criteria.

1. Planning Principles

  1. Foundation before intelligence — correct, portable core allocator and metadata before profilers and adaptive policies
  2. API stability early — freeze the public umr_* surface as soon as Phase 1 exits
  3. Measure everything — benchmarks vs mimalloc / jemalloc / glibc from Phase 1 onward
  4. Debug as a layer — release builds stay fast; debug/sanitizer features compile in
  5. Docs ship with code — each phase updates docs/ and examples

2. Tech Stack

Core runtime

Component Choice Rationale
Language C23 Performance, OS-level access, portable, same ecosystem as malloc
Public headers C11-compatible where practical Broader consumer support; C23 used internally

Build system

Tool Role
CMake Cross-platform project definition
Ninja Fast incremental builds
Presets Debug, Release, RelWithDebInfo, Sanitize

Testing

Framework Use
Criterion Optional; UMR ships a zero-dep harness in tests/
CTest Test runner in CI

Benchmarking

Tool Use
Custom microbenchmarks Primary shootouts in benchmarks/ (libc; optional external mimalloc)

Compare against:

  • glibc malloc (Linux)
  • jemalloc
  • mimalloc
  • tcmalloc (where available)
  • MSVCRT / UCRT heap (Windows baseline)

Debugging & sanitizers

Tool Detects
AddressSanitizer (ASan) Buffer overflow, use-after-free
UndefinedBehaviorSanitizer (UBSan) UB in C runtime
ThreadSanitizer (TSan) Data races on shared heap structures
Valgrind Leak / memcheck on platforms without ASan

Documentation

Tool Role
MkDocs Product docs (vision, plan, feature, architecture)
Doxygen Generated API reference from headers

CI/CD

GitHub Actions matrix:

OS Compilers (target)
Linux GCC, Clang
Windows MSVC, Clang-CL
macOS Apple Clang

Jobs: configure → build → unit tests → (release) benchmarks smoke → sanitizer job (Linux).

3. Repository Layout (Target)

UMR/
├── core/
├── allocator/
│   ├── general_allocator.c
│   ├── arena.c
│   ├── pool.c
│   ├── slab.c
│   ├── buddy.c
├── fragment/
│   ├── fragment_manager.c
│   ├── block_split.c
│   ├── block_merge.c
├── heap/
│   ├── heap_manager.c
│   ├── metadata.c
├── debug/
│   ├── leak_detector.c
│   ├── sanitizer.c
│   ├── guard_pages.c
├── profiler/
│   ├── statistics.c
│   ├── tracker.c
├── platform/
│   ├── linux.c
│   ├── windows.c
│   ├── macos.c
├── include/
├── tests/
├── benchmarks/
├── tools/
│   ├── umr-cli
│   ├── heap-viewer
├── docs/
│   ├── vision.md
│   ├── plan.md
│   ├── feature.md
│   ├── architecture.md
└── examples/

Phase 1 may start with a flatter tree and grow into this layout; the names above are the architectural targets.

4. Phase Roadmap Overview

Phase 1          Phase 2            Phase 3             Phase 4              Phase 5
Foundation  -->  Advanced      -->  Intelligence  -->  Fragment       -->  Developer
                 Allocators         Layer              Runtime             Ecosystem
1–2 months       1–2 months         1–2 months         2–3 months          ongoing

Total to a usable open-source v1 preview: roughly 6–9 months of focused work, depending on staffing.

5. Phase 1 — Foundation

Duration: 1–2 months
Goal: A correct, portable, observable general allocator with a stable public API.

Build

Deliverable Description
Core allocator Size-class aware general heap (baseline engine)
malloc/free replacement umr_malloc, umr_free, umr_realloc, umr_calloc
Metadata tracking Allocation ID, size, address, optional source location
OS memory provider mmap / VirtualAlloc abstraction in platform/
Unit tests Allocate, free, realloc, calloc, stress free-list correctness
CMake skeleton Library + tests + optional shared/static

Detailed tasks

  1. Define include/umr.h public API and error/null semantics
  2. Implement platform page allocator (umr_os_alloc / umr_os_free)
  3. Implement heap manager + block metadata
  4. Implement general allocator (split/merge free blocks or size classes)
  5. Wire metadata (compile-time toggle for file/line capture)
  6. Criterion tests + ASan CI job
  7. First microbenchmark vs system malloc

Exit criteria

  • All basic API tests pass on Linux, Windows, macOS
  • No known memory corruption under ASan stress tests
  • Documented build instructions in README
  • Public API frozen for Phase 2 consumers

Risks

Risk Mitigation
Platform differences in alignment / page size Centralize in platform/ with tests
Metadata overhead hurts perf Make rich metadata debug-only; lean path for release

6. Phase 2 — Advanced Allocators

Duration: 1–2 months
Goal: Specialized engines available through dedicated APIs and optional routing.

Build

Allocator Primary use
Arena Frame / region bump allocation + reset
Pool Fixed-size object reuse
Slab High-rate fixed-size structs / packets
Buddy Power-of-two large / medium management

Detailed tasks

  1. Arena: create / alloc / reset / destroy; nested arenas optional
  2. Pool: create(object_size) / alloc / free; freelist
  3. Slab: cache of equal-sized objects; partial/full slab lists
  4. Buddy: split/merge orders; integrate with large-object path
  5. Allocation Manager hooks to select engine by size or explicit handle
  6. Tests per allocator + isolation (destroying one must not corrupt others)
  7. Benchmarks: arena reset vs malloc churn; pool vs malloc for N fixed objects

Exit criteria

  • Each allocator has Criterion coverage and an example program
  • Documented when to use which allocator (feature.md updated)
  • No cross-heap free without detection in debug builds

7. Phase 3 — Intelligence Layer

Duration: 1–2 months
Goal: Observability tools that make UMR more than “another malloc.”

Build

Component Capability
Profiler Counters: total, active, free, alloc count, peak
Heap visualization ASCII / structured dump of used vs free spans
Leak detection Live allocation set; report on shutdown or on demand
Statistics API umr_stats_* + CLI umr stats

Detailed tasks

  1. Thread-safe (or thread-local aggregated) statistics
  2. Tracker map: pointer → metadata
  3. Leak report format (address, size, location, allocator type)
  4. umr visualize textual heatmap
  5. Optional sampling profiler mode for low overhead
  6. Examples demonstrating leak detection

Exit criteria

  • umr stats prints meaningful live process stats (via tools or in-process API)
  • Intentional leak tests assert detector output
  • Visualization works on a non-trivial heap dump

8. Phase 4 — Fragment Runtime

Duration: 2–3 months
Goal: UMR’s differentiating capability — explicit fragment management and experiments toward defragmentation.

Build

Component Capability
Fragment allocator Track used/free fragments inside regions
Block split Carve free blocks
Block merge Coalesce adjacent free blocks
Memory regions Contiguous managed spans
Defrag experiments Research APIs; may require handles for true compaction

Detailed tasks

  1. Fragment manager data structures (boundary tags, free lists, or trees)
  2. fragment_alloc / fragment_release / fragment_split / fragment_merge
  3. Metrics: fragmentation ratio, largest free block, external vs internal frag
  4. Experiments: best-fit / first-fit / segregated free lists
  5. Document limits of raw void* for moving memory
  6. Prototype path toward UMR_Handle (may land as experimental header)

Exit criteria

  • Fragmentation metrics exposed in profiler
  • Workloads show improved free-block coalescing vs Phase 1 baseline
  • Written design note on relocatable memory (feeds future work)

9. Phase 5 — Developer Ecosystem

Duration: Ongoing after Phase 3/4
Goal: Make UMR adoptable by outsiders.

Build

Deliverable Description
CLI (umr-cli) stats, visualize, snapshot utilities
Documentation MkDocs site; Doxygen API
Examples Games-style frame arena, pool of enemies, server request arena
Benchmarks Published comparison suite vs mimalloc et al.
Policies FAST_MODE, LOW_MEMORY_MODE, REALTIME_MODE, DEBUG_MODE

Detailed tasks

  1. Policy presets configuring size classes, caching, and debug
  2. Snapshot save/load for offline heap analysis
  3. Thread-local heaps / per-thread cache (if not already in Phase 1–2)
  4. Packaging: CMake install, pkg-config / CMake package config
  5. Contribution guide and issue templates

Exit criteria

  • New user can build, link, and run an example in < 15 minutes
  • Benchmark report published in benchmarks/ or docs
  • v0.1 / v1.0-preview tagged release

10. Cross-Cutting Workstreams

These run across phases rather than belonging to one box.

Threading

Milestone Target phase
Mutex-protected shared heap Phase 1
Per-thread cache / free lists Phase 2–3
Lock-free fast paths (where justified) Phase 3–4
Thread-local heaps API Phase 5

Debug runtime

Check Target
Double free Phase 1 (debug)
Invalid pointer (not UMR heap) Phase 1–2
Guard pages / canaries Phase 3
Buffer overflow detection Phase 3

Policies

Introduce as enums/flags in Phase 2 stubs; fully wire in Phase 5.

11. Future Phases (Post-v1)

Not scheduled for initial release, but planned strategically:

Feature Dependency
Relocatable UMR_Handle Fragment runtime + API redesign
Automatic strategy switching Profiler intelligence + stable engines
Cold memory compression Region manager + OS advice (madvise, etc.)
Persistent memory regions Platform persistence APIs
Remote heap debugger Snapshot protocol + tools

See vision.md for the north-star narrative and feature.md for detailed future feature descriptions.

12. Testing & Quality Plan

Test pyramid

        /  Benchmarks  \          performance gates
       /  Integration   \         multi-allocator scenarios
      /    Unit tests    \        block math, freelists, APIs
     /   Platform smoke   \       mmap / VirtualAlloc wrappers

Mandatory CI gates

  1. Build Debug + Release
  2. Unit tests green
  3. ASan tests on Linux
  4. Format / tidy optional but encouraged

Performance gates (soft until Phase 5)

  • General allocator within 90–120% of mimalloc on agreed microbench set
  • No catastrophic regression (>2× slower) without documented reason

13. Release Plan

Tag Meaning
v0.1.0 Phase 1 complete — usable general allocator
v0.2.0 Phase 2 — specialized allocators
v0.3.0 Phase 3 — profiler + leak detector
v0.4.0 Phase 4 — fragment engine
v1.0.0 Ecosystem polish, policies, docs, stable API promise

SemVer policy: breaking changes to umr.h require major version bump after v1.0.0.

14. Team / Work Breakdown Suggestions

If working solo or small team, preferred order of focus:

  1. Platform + heap + general allocator
  2. Tests and CI
  3. Arena + pool (highest user value)
  4. Profiler + leaks
  5. Slab + buddy
  6. Fragment engine
  7. CLI and docs site

15. Success Checklist (Product-Level)

UMR’s plan is complete for a v1 claim when:

  • Drop-in API works across three desktop OS targets
  • At least four specialized allocators shipped
  • Profiler, leak detector, and visualization available
  • Fragmentation metrics and fragment engine present
  • Benchmarks published against mimalloc and glibc
  • MIT-licensed docs and examples sufficient for external contributors

Related Documents