# HeapManager: high-level design

[Repository overview](../README.md) | [Low-level design](HeapManager_LLD.md) | [Complexity](HeapManager_COMPLEXITY.md)

## Original design used

This document adapts the original material under `C:\Temp\EE Intern - Himanshu`:

- `Study Guides/Heap Manager Designs/2/High-level-design.md` — main reference for the one-region, first-fit backend and LFH-style frontend.
- `Study Guides/Heap Manager Designs/1/HLDSteps.md` — the incremental design explanation.
- `VS_EE_Intern_Solution/MyHeap/LFH-Bucket-Policy.md` — why cached blocks need caps and reclamation.

These are source-location records, not dependencies or links required to use this repository. Version 2 supplies the backend/frontend architecture. The portfolio release strengthens its alignment and validation contracts, so original draft layouts are historical examples, not current binary layouts.

## Purpose

HeapManager is a Windows DLL that manages allocations inside one reserved memory region per heap. It provides malloc-like functions without using the process heap to manage its individual blocks.

The main source is [HeapManager.cpp](HeapManager.cpp). Public declarations, block structures, and policy constants are in [HeapManager.h](HeapManager.h).

## Requirements from the original design

| Requirement | How this implementation addresses it |
| --- | --- |
| Allocate and free bytes | The public `my_malloc` and `my_free` functions manage blocks in one heap. |
| Resize and preserve existing data | `my_realloc` keeps existing capacity or allocates, copies, and frees. It does not merge into a neighboring free block in place. |
| Return zero-filled memory | `my_calloc` checks multiplication and clears the requested bytes after allocation. |
| Reuse memory | Splitting limits unused tails; coalescing combines adjacent backend-free blocks; buckets reuse fixed-size blocks. |
| Grow when necessary | Commit additional pages inside the original reservation; return `NULL` when the implemented allocation paths cannot satisfy a request. |
| Support independent heaps | Each `HHEAP` has its own region, lists, counters, and lock. |
| Make behavior observable | Debug guards, layout validation, reports, and logger messages help investigate problems, but are not complete corruption protection. |

The design does not promise any-type alignment, unlimited growth, or production-grade invalid-pointer handling. Those were broader goals in some original drafts, not guarantees of this code.

## First principles: alignment, flags, and minimum size

Alignment describes a **starting address**, not just a payload's length. The allocator uses `MEMORY_ALLOCATION_ALIGNMENT`: 16 bytes on x64 and 8 bytes on Win32. Headers, block sizes, and the first-block offset use that boundary, so stepping through blocks preserves payload alignment.

Alignment leaves low bits available in `BLOCK_HEADER.Size`. Bit 0 is `MH_USED`, bit 1 is `MH_PREV_USED`, and bit 2 is `MH_CACHED`. The cached flag distinguishes idle bucket ownership from a live caller allocation while preserving the physical used flag required by coalescing.

This supports the normal native allocation boundary, not arbitrarily over-aligned types. Asking for a larger payload does not guarantee a stronger starting address.

Every block must also be large enough to become free later. On **x64 Release**, the aligned header is 16 bytes, node storage is 16 bytes, and footer storage is 16 bytes: a 48-byte minimum. On **x64 Debug**, the header is 32 bytes and the minimum is 64. Requested payload length is recorded in both builds; Debug adds magic, allocation ID, and an eight-byte guard. The aligned footer occupies space only when free. Minimum sizes and class rounding create real overhead for tiny requests.

## Incremental design explained in the source

The original notes introduce one idea at a time. This repository contains the combined implementation, not separate runnable programs for every stage.

```mermaid
flowchart LR
	A["Reserve a region and find a fit"] --> B["Split useful remainders"]
	B --> C["Free and merge neighbors"]
	C --> D["Commit more when needed"]
	D --> E["Cache repeated small sizes"]
	E --> F["Protect heap metadata with a lock"]
	F --> G["Validate, report, and exercise through ClientApp"]
```

Each idea addresses a weakness: whole-block allocation wastes space; unmerged free blocks fragment it; fixed committed capacity fills; repeated small requests repeat searches; concurrent metadata changes need synchronization; integration needs observable checks.

## Main parts

| Part | Responsibility |
| --- | --- |
| Public `my_*` API | Creates heaps, allocates and frees payloads, and exposes validation and reporting. |
| Small-block frontend | Groups total block sizes into 51 classes and reuses parked blocks. |
| Backend free list | Finds a large enough block, splits it, and merges adjacent free blocks. |
| Windows memory layer | Reserves address space, commits usable pages, and releases the entire heap. |
| Heap lock | Protects shared metadata, list links, bucket state, and counters. |
| Diagnostics and snapshots | Validates metadata, list membership, counters, and Debug guards; reports live blocks and copies read-only snapshots. |

```mermaid
flowchart TD
	A["Client: my_* calls"] --> B["Public heap API"]
	B --> C["One critical section per heap"]
	C --> D["51 size-class buckets"]
	C --> E["First-fit backend free list"]
	D -->|"Drain parked blocks"| E
	E --> F["Split and coalesce blocks"]
	E --> G["Commit more reserved pages"]
	G --> W["Windows VirtualAlloc"]
	B --> R["Validation and reports"]
	B --> L["Debugger logging"]
```

The buckets and backend are two ways to organize blocks in the **same memory region**. They do not own separate Windows heaps.

The source's client → library → Windows layering maps to these actual files:

| Original design role | Location here |
| --- | --- |
| Client harness | `ClientApp/ClientApp.cpp` |
| Public heap interface | `HeapManager/HeapManager.h`; `HHEAP` points to the exposed `HEAP` structure, not an opaque private type. |
| Backend, frontend, OS calls, and validation | Functions in `HeapManager/HeapManager.cpp`; there are no separate `os_win32.c` or `myheap_debug.c` modules here. |
| Intrusive links | `Intrusive_LinkedList/Intrusive_LinkedList.h` supplies `NODE`. |
| Diagnostic logging | The separate Debugger static library. |

## Memory ownership

`my_heap_create` puts the `HEAP` object at the beginning of the reserved region. Physical blocks follow it. The first 64 KiB is committed immediately; later growth commits more pages without moving existing payloads.

```mermaid
flowchart LR
	H["HEAP metadata"] --> A["Allocated block"]
	A --> F["Backend free block"]
	F --> P["Parked bucket block"]
	P --> U["Reserved but uncommitted space"]
```

This diagram shows a possible physical order, not a list traversal order.

The caller owns the requested bytes of a live allocation. The allocator owns its header, any Debug guard, and unused space. After `my_free`, the caller must not touch the pointer: the payload may now hold list links.

## Why intrusive nodes fit this design

The [Intrusive_LinkedList](../Intrusive_LinkedList/Intrusive_LinkedList_HLD.md) project defines `NODE`, containing a previous pointer and a next pointer. HeapManager places this node at the start of a free or parked block's payload. It therefore needs no separate node allocation to track that block.

HeapManager does **not** use the library's `LIST_HEAD` object or its locked list functions. Its internal `FlInsert`, `FlRemove`, `BucketPush`, and `BucketPop` helpers work under the heap's existing lock. This keeps splitting, merging, counters, and list changes within one protected operation.

### Physical neighbors are not list neighbors

This distinction is emphasized in the original HLD. Suppose physical blocks A and C are free, but live block B sits between them. The free list can link C directly to A because it contains no live blocks. That does **not** allow A and C to merge through B.

```mermaid
flowchart LR
	PA["Physical: A free"] --> PB["B used"]
	PB --> PC["C free"]
	H["FreeHead"] --> LC["List node for C"]
	LC --> LA["List node for A"]
	LA --> N["NULL"]
```

The backend inserts at the list head; it is not sorted by address or size. `NextBlock` uses a physical size to move forward. A free predecessor's footer provides the distance to move backward. The intrusive links are used only to update list membership.

## Allocation strategy

1. Add metadata and any guard bytes to the requested size.
2. Round to the configured alignment and minimum block size.
3. For a small enough total block, choose a size class and try its active cache.
4. Otherwise, use a first-fit search of the backend free list.
5. If nothing fits, retire cold caches, then trim warm caches, retrying when blocks were reclaimed.
6. If still necessary, commit more of the reserved region and retry.
7. Return `NULL` if a suitable block still cannot be obtained.

A suitable backend block is split only when the remainder can itself form a valid free block.

## Free strategy

A free first verifies that the pointer is a physical payload boundary and belongs to a live, non-cached block. Debug guard damage is rejected without freeing. An accepted block is parked only when its actual total size exactly matches a class, that class is active, and its cache is below its demand-based cap.

Otherwise, the backend marks the block free and merges it with free physical neighbors. Headers and footers locate those neighbors; the intrusive links only locate list neighbors.

A parked block has both used and cached flags set and a zero requested length. Draining removes it from its bucket and passes it to the backend. Reusing it clears the cached flag and records the new requested length. This rejects a repeated free while the block is cached; it cannot detect an old pointer after the same address has been reallocated to a different caller.

## Why the original bucket policy adds cap, keep, and recency

A workload may allocate many blocks of size X, free them into X's cache, then request a different size Y. The heap still owns those bytes, but the backend cannot merge or reuse them for Y until X's blocks are drained.

- **Cap:** limit how many blocks a class accepts into its cache, based on recent request demand.
- **Keep:** during a warm drain, leave a small reserve of `cap / 8` blocks. This can be zero.
- **Recency:** reclaim an inactive class fully before trimming recently used classes.

The recovery order is cold retirement → warm trimming → commit growth → failure if no suitable block can be found. Cold retirement ignores the warm keep count and can empty a bucket. Warm retention and fragmentation mean failure is not proof that every byte of the reservation is occupied by live payloads.

All 51 bucket-state entries already exist in `HEAP`; activation changes flags and list membership. It does not allocate a separate bucket object or reserve another region. The policy's clock counts heap activity, not elapsed seconds.

## Threading and lifetime

- Each heap has its own Windows `CRITICAL_SECTION`.
- Threads can share a heap, but metadata operations on that heap serialize.
- The lock does not protect application reads and writes to payloads.
- The caller must prevent another thread from freeing or reallocating a payload while it is being used.
- Stop every heap user before `my_heap_destroy`; destruction does not join threads or wait for outstanding allocations.
- Creation and destruction own the lock's lifetime. The DLL entry point is only the standard stub, not a heap manager or logger initializer.

## Diagnostics and tradeoffs

Debug builds add a magic value, allocation ID, and an eight-byte guard; requested size is always recorded. Guard damage causes free/realloc rejection. `my_heap_validate` checks physical shape, predecessor flags, coalescing, free-list and bucket links/membership, and counters. Reports refuse invalid metadata rather than walking it blindly. The [Debugger library](../Debugger/Debugger_HLD.md) records diagnostic messages with automatically initialized synchronization.

This design favors understandable pointer operations over production-level hardening. Request arithmetic is checked, but valid heap handles, exclusive payload ownership, and intact allocator metadata remain caller obligations. The frontend still trades retained commitment and delayed coalescing for reuse. Physical pointer checks add linear work; comprehensive list validation can be quadratic. These are deliberate correctness/diagnostic tradeoffs, not performance improvements.

## Read-only visualization boundary

`my_heap_snapshot` copies a validated view while holding the heap lock. The caller supplies `MH_SNAPSHOT` and a block array outside this heap. A sizing call reports the required count; a retry handles growth between calls. No callbacks, file I/O, payload bytes, or raw process addresses cross this API.

```mermaid
flowchart LR
	H["Heap state under lock"] --> V["Bounded integrity validation"]
	V --> S["Caller-owned offsets and counters"]
	S --> E["ClientApp JSON writer after unlock"]
	E --> P["Static GitHub Pages viewer"]
```

Snapshots are observations, not replayable allocator commands. The page cannot invoke the DLL. Named scenarios assert split/merge, cache reuse/reclamation, growth, and concurrent ownership before an export is published.

See [LLD](HeapManager_LLD.md) for the exact policy and safety boundaries, and [COMPLEXITY](HeapManager_COMPLEXITY.md) for fast-path versus worst-case costs.