# Windows Heap Manager — Inside the Allocator

A custom heap allocator written in C++ using Windows APIs. It reserves a region of virtual address space, commits memory as needed, and manages blocks inside that region.

This project demonstrates memory layout, pointer arithmetic, intrusive linked lists, block splitting and merging, small-block caching, synchronization, and diagnostic logging. It is a learning and portfolio implementation, not a drop-in replacement for the C runtime allocator.

**Explore real allocator state:** open [index.html](index.html) through a local HTTP server or GitHub Pages. The page replays snapshots exported by the Windows DLL; it does not simulate or run the allocator in JavaScript.

![Native heap snapshot showing cached blocks and backend free space](assets/preview.png)

Highlights: native allocation alignment, explicit live/cached state, checked size arithmetic, bounded integrity checks, five named scenarios, local-only JSON loading, and Windows CI. No frontend framework or npm installation is required.

## The four projects

| Project | Output | Responsibility |
| --- | --- | --- |
| [HeapManager](HeapManager/HeapManager.cpp) | `HeapManager.dll` and its import library | Owns the reserved region and implements the `my_*` allocation API. |
| [Intrusive_LinkedList](Intrusive_LinkedList/Intrusive_LinkedList.h) | `Intrusive_LinkedList.lib` | Defines embedded list nodes and provides a reusable, locked doubly linked list. |
| [Debugger](Debugger/Debugger.cpp) | `Debugger.lib` | Provides logging macros, source-location information, assertions, and manual timing helpers. |
| [ClientApp](ClientApp/ClientApp.cpp) | `ClientApp.exe` | Exercises allocation, data preservation, reuse, and concurrent access. |

All four projects are part of [HeapManager/HeapManager.slnx](HeapManager/HeapManager.slnx). No original assignment directory or extra project is needed to build them.

### How they work together

```mermaid
flowchart LR
	C["ClientApp: tests and reports"] -->|"my_* API calls"| H["HeapManager DLL"]
	H -->|"Reserve, commit, release"| W["Windows virtual memory"]
	H -.->|"Uses the NODE layout"| L["Intrusive_LinkedList header"]
	H -->|"LOG_INFO and LOG_ERROR"| D["Debugger static library"]
	D --> O["Console and debugger output"]
	D -.->|"Only when initialized with a path"| F["Optional log file"]
```

The arrows describe runtime use. The project references also link ClientApp to both static libraries and HeapManager to both static libraries. A build reference does not mean every library function is called.

**Important distinction:** HeapManager reuses the list library's `NODE` structure, but does not call its `AddHead`, `RemoveHead`, or other `LIST_HEAD` operations. It has its own free-list and bucket helpers, protected by the heap's lock. The original client workload exercises that integration; `--test` also runs direct list and logger regression checks in [Portfolio.cpp](ClientApp/Portfolio.cpp).

## How the heap works

### 1. Reserve an address range

`my_heap_create` reserves at least 64 KiB, rounded up to a 64 KiB boundary. It commits the first 64 KiB, puts the `HEAP` bookkeeping structure at the beginning, and makes the remaining space one free block.

Reserving address space is not the same as using that much physical RAM. Committing makes pages available for use; Windows still manages their physical backing.

### 2. Find or create a suitable block

For `my_malloc`, the heap adds its header and optional Debug guard bytes to the requested size. It rounds the result and ensures the block is large enough to hold free-list data later.

- **Small-block frontend:** 51 size classes cover total block sizes from 32 bytes through 16 KiB. Frequently used classes can cache freed blocks for reuse.
- **General backend:** a first-fit search walks the free list and takes the first block large enough. A large enough remainder becomes another free block.
- **Memory pressure:** if no block fits, the heap tries to reclaim cached blocks before committing more of its reserved region.

The size-class limits refer to the **whole block**, not just the caller's data. This is a custom LFH-style cache, not the Windows Low Fragmentation Heap API.

### 3. Free or cache a block

A suitable block can be parked in its active size-class bucket. Otherwise, it goes back to the backend and is merged with free physical neighbors. Merging adjacent blocks is also called **coalescing**.

Parked blocks keep `MH_USED` set so the backend cannot merge through them, and also set `MH_CACHED` to distinguish them from live allocations. Repeated frees and realloc of a still-cached block are rejected. Draining returns the block to the backend. Requested payload sizes are recorded in both Debug and Release.

### 4. Grow or destroy the heap

Growth commits more memory within the original reservation, normally in 64 KiB multiples. The reservation itself never expands. Freed memory stays committed until `my_heap_destroy` releases the entire region.

```mermaid
flowchart TD
	A["Caller asks for memory"] --> B["Lock heap and calculate block size"]
	B --> C{"Reusable block in active bucket?"}
	C -->|"Yes"| D["Pop cached block"]
	C -->|"No"| E["Search backend free list"]
	E --> F{"Suitable block found?"}
	F -->|"No"| G["Reclaim cached blocks, then try growth"]
	G --> H{"Block available now?"}
	H -->|"No"| I["Unlock and return NULL"]
	H -->|"Yes"| J["Remove block and split if useful"]
	F -->|"Yes"| J
	D --> K["Update counters and Debug guard"]
	J --> K
	K --> L["Unlock and return payload pointer"]
```

See the [heap LLD](HeapManager/HeapManager_LLD.md) for the exact retry order and cache policy.

## Why an intrusive linked list?

An intrusive list stores links inside the object being tracked, instead of allocating a separate wrapper node.

For a free heap block, the start of the unused payload holds `NODE`, which contains `pPrev` and `pNext`. Once the block is allocated, the caller can use that payload again.

This avoids allocating memory just to record free memory. It also allows a known free block to be unlinked with a few pointer updates. Finding a block by size still requires a scan of the backend list.

A list neighbor and a physical memory neighbor are not necessarily the same thing. List links track membership; block headers, sizes, and free-block footers locate physical neighbors for merging.

## Public heap API

Include [HeapManager/HeapManager.h](HeapManager/HeapManager.h) and link against the matching `HeapManager.lib`. Keep `HeapManager.dll` beside the executable.

| Function | What it does |
| --- | --- |
| `my_heap_create(reserveBytes)` | Creates a heap; returns `NULL` if reservation or initial commit fails. |
| `my_heap_destroy(heap)` | Releases the heap and invalidates every pointer from it. |
| `my_malloc(heap, size)` | Allocates an uninitialized payload; a zero-size request returns `NULL`. |
| `my_calloc(heap, count, size)` | Checks multiplication overflow, allocates, and zeroes the requested bytes. |
| `my_realloc(heap, pointer, size)` | Reuses existing capacity or allocates, copies, and frees the old block. |
| `my_free(heap, pointer)` | Returns a block to a bucket or the backend; a null pointer is ignored. |
| `my_heap_validate(heap)` | Checks block shape, neighbor flags, counters, lists, buckets, and Debug guards using bounded walks. |
| `my_heap_report(heap)` | Prints counters and, in Debug, information about live allocations. |
| `my_heap_snapshot(heap, snapshot, blocks, capacity)` | Copies one validated, lock-consistent view into caller-owned buffers; returns required capacity if the block array is too small. |

Use the heap that originally allocated the pointer. Stop all users before destroying a heap. Different threads may allocate and free their own blocks on the same heap, but the heap lock does not make simultaneous access to the same user payload safe.

## What the debugger library adds

The library writes timestamped messages with severity, process ID, thread ID, source file, line, and function. Messages go to the console and `OutputDebugStringA`. File logging is optional.

HeapManager uses it for heap creation and error messages. Logger locking initializes automatically through `INIT_ONCE`; logging, file switching, and shutdown are synchronized. Redirected output does not attempt to restore console colors. The regression suite exercises file reopening, concurrent logging/lifecycle calls, and a timer smoke check. It does not deliberately execute a debugger-breaking assertion.

The library is statically linked: an executable and a DLL that both use it can have separate logger state. Initializing an executable's copy does not initialize the DLL's copy. See the [debugger LLD](Debugger/Debugger_LLD.md).

## Visualize the real heap

```mermaid
flowchart LR
	N["Native scenario"] --> S["Validated snapshot under heap lock"]
	S --> J["ClientApp JSON export"]
	J --> V["Static HTML viewer"]
	V --> M["Replay, memory map, buckets, and block details"]
```

The schema records relative offsets, block sizes, requested lengths, states, and counters—not payload contents or process addresses. Each frame is a consistent snapshot; the heap can change between frames. The concurrent scenario captures a barrier after all workers have allocated their private blocks.

The viewer supports bundled examples and local JSON files. Uploaded files never leave the browser. Imports are limited to 8 MiB, 16 scenarios, 256 total frames, 4,096 blocks per frame, and 65,536 total block records. Unsupported layouts, overlapping blocks, inconsistent counters, and invalid bucket membership are rejected. This is structural validation, not authentication of the file's claimed producer.

### Technical write-up first

The [site](index.html) starts with a short implementation summary, the problem, and a simple flow diagram. It then explains architecture, allocation/free lifecycle, native memory layouts, LFH-style buckets, fragmentation/free-list decisions, debugging, and test scenarios before the interactive explorer. It finishes with benchmark methodology, limitations/future work, and technical takeaways under “What I learned.”

The dark cyan/amber dashboard supports the explanation rather than replacing it. The terminal-style overview reports counts from the loaded trace; it is not a fake execution console. A heap-state screenshot is available alongside the test scenarios.

| Control | Behavior |
| --- | --- |
| Scenario cards and selector | Choose any scenario in the loaded file, including uploaded traces. |
| Timeline, range slider, previous/next | Jump to a recorded frame with keyboard-accessible controls. |
| Playback pace | Advance every 2 seconds, 1 second, or 0.5 seconds; these are UI timings, not native execution timings. |
| Focus filter | Dim nonmatching map ranges and filter the block table without rescaling memory or changing global counters. |
| What changed? | Compare with the preceding recorded frame in the same scenario: counter deltas, cached/committed bytes, changed ranges, and visible boundary changes. |
| Local file selection or drag/drop | Validate one JSON trace locally; invalid input leaves the previous valid trace available. |
| Copy commands | Copy the native test/export commands, with a manual-copy fallback when clipboard access is unavailable. |

Snapshot transitions use short fades, not invented intermediate allocation states. Reduced-motion preferences disable those animations; changing to reduced motion also pauses active playback. A baseline has no earlier comparison. Matching offsets do not establish allocation identity, and unchanged endpoints do not prove no activity occurred between captures.

The LFH section also contains a **formula-only cap/keep calculator**. It illustrates `cap = clamp(4 + demand, 4, 256)` and `keep = floor(cap / 8)` for a selected request count. It neither reads nor modifies the captured heap.

The [benchmark section](index.html#benchmarks) is explicitly **not measured yet**. It proposes comparable Release workloads against the CRT and Windows heap, with repeatable seeds, reported environment/settings, failures, latency/throughput, and clearly defined memory metrics. There are no fabricated results or speedup claims.

| Scenario name | Demonstration and checked property |
| --- | --- |
| `split-merge` | Three large allocations; freeing neighbors ends with one backend-free block. |
| `bucket-reuse` | Repeated small requests activate a class; the next allocation reuses the cached offset. |
| `changing-workload` | A larger request trims 24 cached blocks to 3 without growth; later activity retires the cold cache. |
| `growth` | A 96,000-byte request increases commitment; freeing does not decommit pages. |
| `concurrent` | Four native workers each own 16 blocks at a barrier, then verify and release them. Exact interleaving can vary. |

## Build and run

### Requirements

- Windows with Visual Studio 2026 and the **Desktop development with C++** workload.
- MSVC platform toolset **v145**; the projects select C++20.
- Windows SDK **10.0.26100.0**, which is the version selected in all four project files.

### Visual Studio

1. Open `HeapManager/HeapManager.slnx`.
2. Set **ClientApp** as the startup project.
3. Select Debug or Release and x64 or x86. The C++ projects call the 32-bit platform `Win32`.
4. Build the solution and run ClientApp with **Ctrl+F5**.

### Developer PowerShell

From the repository root, in a Visual Studio Developer PowerShell:

```powershell
msbuild .\ClientApp\ClientApp.vcxproj /m /p:Configuration=Debug /p:Platform=x64
.\bin\x64\Debug\ClientApp.exe
```

Building the client also builds its referenced projects. For 32-bit builds use `/p:Platform=Win32`; for Release use `/p:Configuration=Release`.

[Directory.Build.props](Directory.Build.props) puts outputs in `bin/<Platform>/<Configuration>/` and intermediates in `obj/<Project>/<Platform>/<Configuration>/`. The executable and DLL land in the same output directory. Do not mix architectures or Debug/Release headers and binaries: Debug changes the heap's block layout.

The SDK is pinned because the previously selected 10.0.28000.0 manifest tool failed to start on the development machine. Manifest generation remains enabled.

### Portfolio commands

```powershell
.\bin\x64\Debug\ClientApp.exe --test
.\bin\x64\Debug\ClientApp.exe --scenario changing-workload
.\bin\x64\Debug\ClientApp.exe --export trace.json
.\bin\x64\Debug\ClientApp.exe --export split.json split-merge
python -m http.server 8000 --bind 127.0.0.1
```

Then open `http://127.0.0.1:8000/index.html`. Opening the HTML directly also supports local JSON selection; browsers generally block bundled `fetch` requests from a `file:` page. `--help` lists the commands; invalid arguments return exit code 2.

Export uses a temporary file in the destination directory and publishes it only after all selected scenarios and writes succeed. A failed export does not replace an existing destination. Export paths currently use Windows ANSI APIs and the `MAX_PATH` limit. The bundled [demo-trace.json](assets/demo-trace.json) was generated from a successful x64 Release run, not handwritten. Regenerate it with the Release client's `--export assets/demo-trace.json` command.

### Publish with GitHub Pages

Commit the source, docs, root `index.html`, `.nojekyll`, and `assets/`. In repository **Settings → Pages**, choose **Deploy from a branch**, your publishing branch, and **/(root)**. All viewer asset URLs are repository-relative, so it works under a project Pages subpath. No DLL runs on GitHub Pages. Publishing is a repository setting; this change does not enable it automatically.

## What ClientApp checks

- Nine allocation sizes, from 1 through 20,000 bytes, with write/read-back checks.
- `my_calloc` zero-filling 1,024 bytes.
- `my_realloc` growing 64 bytes to 512 bytes while preserving the old data.
- 5,000 rounds of 128-byte block reuse across 32 slots.
- Eight Windows threads, each performing 20,000 random slot operations, with up to 64 live blocks per worker and sizes from 1 to 2,048 bytes.
- Heap validation and a report after each test phase.

A worker operation is **one allocation or one verification/free**, not a complete allocation/free pair. Workers also release their remaining blocks after the loop.

A no-argument run retains these original scenarios and ends with `RESULT: ALL TESTS PASSED` and exit code `0` on success. Final live-byte/block counters and allocation/free totals are now asserted, not only printed. These are console tests, not a Visual Studio Test Explorer suite.

`--test` additionally checks alignment, overflow, realloc preservation/failure, interior/foreign pointers, cached and backend double frees, snapshot sizing/counters, exhaustion, used commit seams, list integrity, direct list operations, logger lifecycle, and all five portfolio scenarios. Debug also deliberately damages and restores a guard to verify rejection. Expected invalid-input log messages can appear in a passing regression run; the exit code and assertions determine success.

The local validation matrix passed on x64 and Win32 in both Debug and Release. [Windows CI](.github/workflows/windows.yml) repeats native tests, export/schema checks, and browser/document checks. It uses the runner's VS 2022 `v143` toolset and installed SDK through command-line overrides; local project defaults stay unchanged. The workflow must run on GitHub before its remote status can be claimed.

```powershell
python tests/run_native.py --exe bin/x64/Debug/ClientApp.exe --trace obj/checks/trace.json
node --test tests/trace.test.js tests/export.test.js
node tests/browser-smoke.js
python tests/check_docs.py
```

Native child processes have a 180-second default timeout. Browser checks require Node 22+ and installed Chrome/Edge (`BROWSER` can select the executable); they use an isolated profile under `obj/`. No npm dependencies are required. Logs, native traces, and screenshots are saved as CI artifacts. Passing these checks is evidence for tested cases, not proof of all possible workloads.

The native runner separately exercises the default command, full regressions, direct scenario dispatch, and both all-scenario and single-scenario exports. It forces a late publication failure against an owned temporary read-only destination, checking original-content preservation and temporary-file cleanup, and checks a missing output directory. Browser checks cover both an HTTP repository subpath and direct `file:` loading with a selected local trace; startup waits for a readable DevTools port and ready page instead of racing browser initialization.

## Current limits

- Alignment follows `MEMORY_ALLOCATION_ALIGNMENT`: **16 bytes on x64 and 8 on Win32**. Over-aligned types needing stronger boundaries are not supported by this API.
- Size multiplication, header/guard addition, and reservation rounding are checked. Heap handles and output buffers must still be valid and alive; this is not a security boundary against arbitrary metadata writes.
- Free/realloc perform a physical-boundary scan before accepting payload pointers. A raw stale pointer cannot be distinguished from a valid new allocation if the same address has already been reused.
- Debug guard damage is rejected without freeing the allocation. Reports and snapshots refuse invalid heaps. Release does not include payload guards, and allocation does not perform a full integrity audit before every pointer update.
- One critical section serializes heap metadata operations. There are no per-thread caches or lock-free paths.
- The heap does not decommit freed pages, compact live allocations, or grow beyond the initial reservation.
- Stronger checks have a cost: free/realloc pointer lookup is `O(B)` and full validation/snapshots can be `O(B²)` for `B` physical blocks. The intrusive unlink/merge operations themselves remain constant-time. See the complexity documents.
- The client and viewer are correctness/teaching tools, not benchmarks. Benchmark comparisons, production-hardening claims, and licensing decisions are deferred.

## Design documents

HLD means **high-level design**: the main parts and their responsibilities. LLD means **low-level design**: the data, functions, and detailed flows. Complexity documents explain how work and storage grow as inputs grow.

| Project | HLD | LLD | Complexity |
| --- | --- | --- | --- |
| HeapManager | [Overview](HeapManager/HeapManager_HLD.md) | [Function flows](HeapManager/HeapManager_LLD.md) | [Time and space](HeapManager/HeapManager_COMPLEXITY.md) |
| Intrusive_LinkedList | [Overview](Intrusive_LinkedList/Intrusive_LinkedList_HLD.md) | [Node operations](Intrusive_LinkedList/Intrusive_LinkedList_LLD.md) | [Time and space](Intrusive_LinkedList/Intrusive_LinkedList_COMPLEXITY.md) |
| Debugger | [Overview](Debugger/Debugger_HLD.md) | [Logging flow](Debugger/Debugger_LLD.md) | [Time and space](Debugger/Debugger_COMPLEXITY.md) |
| ClientApp | [Overview](ClientApp/ClientApp_HLD.md) | [Test flows](ClientApp/ClientApp_LLD.md) | [Workload costs](ClientApp/ClientApp_COMPLEXITY.md) |

Mermaid diagrams render in compatible Markdown viewers, including GitHub. If a local viewer shows diagram text instead, enable Mermaid support or read the numbered explanation beside it.