emalloc_

A from-scratch memory allocator written in C++17, targeting embedded systems where heap fragmentation, non-deterministic allocation times, and silent memory corruption are not acceptable.

No STL. No heap. No exceptions. Fully testable on host (native GCC/Clang) and designed for bare-metal Cortex-M3.

---

Why this exists

Production embedded code — automotive ECUs, industrial controllers, medical devices — typically bans malloc and new entirely (MISRA C++ rule 18-4-1). The standard heap is unpredictable: allocation time varies, fragmentation builds up over hours of runtime, and a failed allocation deep in a control loop can be catastrophic.

emalloc_ implements the allocator primitives that replace the heap in these environments, built from first principles with no external dependencies.

Designed under embedded constraints: no heap allocation after init, no STL containers, no exceptions, no virtual dispatch.

---

Architecture

┌─────────────────────────────────────────────────────┐
│                   Application code                  │
│         new / delete  ·  alloc() / free()           │
└────────────────────┬────────────────────────────────┘
                     │
         ┌───────────┴───────────┐
         │                       │
┌────────▼────────┐   ┌──────────▼──────────┐
│  PoolAllocator  │   │   BlockAllocator     │
│                 │   │                      │
│ Fixed-size      │   │ Variable-size        │
│ blocks          │   │ blocks               │
│ O(1) alloc/free │   │ First-fit + split    │
│ Zero fragment.  │   │ Forward coalescing   │
│                 │   │ Canary protection    │
│                 │   │ Heap statistics      │
└────────┬────────┘   └──────────┬───────────┘
         │                       │
         └───────────┬───────────┘
                     │
┌────────────────────▼────────────────────────────────┐
│              Static SRAM buffer                     │
│   alignas(max_align_t) uint8_t heap_[HEAP_SIZE]     │
└─────────────────────────────────────────────────────┘

Pool allocator — include/pool_allocator.hpp

Carves a static buffer into N equal-sized blocks at compile time. A free-list threads through unused blocks so alloc() and free() are both O(1) with zero fragmentation possible.

When a block is free, its first bytes store a pointer to the next free block — zero extra bookkeeping memory.

static PoolAllocator<64, 8> pool;  // 8 blocks of 64 bytes

void* p = pool.alloc();   // O(1)
pool.free(p);             // O(1)

pool.free_count();        // currently available blocks
pool.used_count();        // currently allocated blocks
pool.peak_usage();        // high watermark

Block allocator — include/block_allocator.hpp

Manages a heap of variable-size allocations. Each allocation is preceded by a BlockHeader storing size, free status, a linked-list pointer, and a magic number for corruption detection. A canary value is written after every allocation and verified on free() and verify().

static BlockAllocator<4096> heap;

void* p = heap.alloc(24);   // first-fit, splits remainder
heap.free(p);               // coalesces with adjacent free blocks
heap.verify();              // walk entire heap, check all canaries
heap.print_stats();         // stream diagnostic report

Memory layout per allocation

[ BlockHeader (magic · size · is_free · next) ][ user data ][ CANARY ]
 ←──────── sizeof(BlockHeader) bytes ─────────→← size bytes→← 4B ──→

---

Fragmentation demo

The following output was captured by allocating four blocks then freeing the third, creating a hole between two live allocations:

── Heap Stats ───────────────────────
  total       : 1024 bytes
  used        : 684 bytes
  free        : 164 bytes
  largest free: 164 bytes
  allocations : 4
  fragmentation: 0.0%
─────────────────────────────────────
── Heap Stats ───────────────────────    ← after freeing middle block
  total       : 1024 bytes
  used        : 620 bytes
  free        : 228 bytes
  largest free: 164 bytes              ← 64 free bytes stranded in a hole
  allocations : 3
  fragmentation: 28.1%                 ← cannot satisfy a 200-byte request
─────────────────────────────────────

228 bytes are free but the largest contiguous block is only 164 bytes. A 200-byte allocation would fail despite there being sufficient total free memory. This is the problem backward coalescing (Day 6) will address.

---

Running on bare-metal Cortex-M3 (QEMU)

The allocator runs on a simulated ARM Cortex-M3 with no OS underneath — just a linker script, startup assembly, and a CMSDK UART driver.

cd bsp
make
make run        # Ctrl-A X to quit QEMU

Output from QEMU mps2-an385:

=== emalloc_ on Cortex-M3 (QEMU mps2-an385) ===

-- initial state --
── Heap Stats ───────────────────────
  total       : 2048 bytes
  used        : 0 bytes
  free        : 2024 bytes
  largest free: 2024 bytes
  allocations : 0
  fragmentation: 0.0%
─────────────────────────────────────
-- after 3 allocations (64, 128, 64 bytes) --
── Heap Stats ───────────────────────
  total       : 2048 bytes
  used        : 256 bytes
  free        : 1696 bytes
  largest free: 1696 bytes
  allocations : 3
  fragmentation: 0.0%
─────────────────────────────────────
-- after freeing middle block --
── Heap Stats ───────────────────────
  total       : 2048 bytes
  used        : 128 bytes
  free        : 1824 bytes
  largest free: 1696 bytes
  allocations : 2
  fragmentation: 7.0%
─────────────────────────────────────
-- after freeing all blocks --
── Heap Stats ───────────────────────
  total       : 2048 bytes
  used        : 0 bytes
  free        : 2016 bytes
  largest free: 2016 bytes
  allocations : 0
  fragmentation: 0.0%
─────────────────────────────────────

The firmware binary is 17KB of ARM Thumb-2 code running in 18KB of SRAM on a 25 MHz Cortex-M3. No OS. No dynamic linker. No runtime support beyond a minimal C library stub.

Corruption detection

Every allocation gets a 0xCAFEBABE canary written immediately after its data region. free() checks the canary before returning the block to the free list. verify() walks the entire heap and reports every corrupted block:

[emalloc] CORRUPTION DETECTED at 0x10034c020 size=8

The BlockHeader magic number (0xDEADBEEF) guards against freeing a pointer that did not come from this allocator.

---

Benchmarks

Measured on Apple M2 (native Clang, -O0, host build):

Operation	Pool allocator	Block allocator
alloc()	~3.2 ns	~86.7 ns
free()	~3.2 ns	~5.0 ns

The block allocator's alloc() is ~27x slower than the pool allocator because it walks the free list to find a fitting block — O(n) vs O(1). free() is close in both cases since both are O(1) pointer operations.

Use the pool allocator for frequently allocated fixed-size objects (CAN frames, FSM state buffers). Use the block allocator for general-purpose variable-size allocation where pool sizing is impractical.

---

Build & run

Requires cmake >= 3.20 and g++ >= 11 (C++17).

git clone https://github.com/DennisVNilsson/emalloc_.git
cd emalloc_
mkdir build && cd build
cmake ..
make

Run the demo:

./demo

Run all test suites:

ctest --output-on-failure

Or run individual suites:

./tests          # pool allocator — 11 tests
./tests_block    # block allocator — 8 tests
./tests_stats    # heap statistics — 3 tests
./tests_stress   # stress test — 1 test

---

Project structure

emalloc_/
├── include/
│   ├── pool_allocator.hpp       # Pool allocator (templated)
│   ├── block_allocator.hpp      # Block allocator with canary protection
│   └── emalloc_overrides.hpp    # new/delete override declarations
├── src/
│   ├── main.cpp                 # Demo — fragmentation walkthrough
│   ├── pool_allocator.cpp       # Translation unit stub
│   └── emalloc_overrides.cpp    # operator new/delete overrides
├── tests/
│   ├── test_pool_allocator.cpp  # 11 unit tests
│   ├── test_block_allocator.cpp # 8 unit tests
│   ├── test_stats.cpp           # 3 unit tests
│   └── test_stress.cpp          # Stress test — 100 alloc/free cycles
├── bsp/
│   ├── startup.s            # ARM Thumb-2 vector table and reset handler
│   ├── mps2_an385.ld        # Linker script — flash/SRAM memory map
│   ├── uart.hpp / uart.cpp  # CMSDK APB UART driver
│   ├── Makefile             # Bare-metal build + QEMU launch
│   └── arm-none-eabi.cmake  # Toolchain file (optional CMake path)
├── CMakeLists.txt
└── .github/workflows/
    └── c-cpp.yml                # CI — builds and tests on every push

---

Roadmap

	Feature	Status
Day 1	Pool allocator — O(1), fixed-size blocks	✅
Day 2	Block allocator — variable-size, splitting, coalescing	✅
Day 3	Corruption detector — canary bytes, verify()	✅
Day 4	Heap statistics — fragmentation analysis	✅
Day 5	Override new/delete — stress test	✅
Day 6	Backward coalescing — doubly-linked list	✅
Day 7	QEMU port — bare-metal Cortex-M3	✅

---

License

MIT