# HeapManager: low-level design [Repository overview](../README.md) | [High-level design](HeapManager_HLD.md) | [Complexity](HeapManager_COMPLEXITY.md) Source: [HeapManager.h](HeapManager.h) and [HeapManager.cpp](HeapManager.cpp). ## Original design used and adaptation rules The main references under `C:\Temp\EE Intern - Himanshu` are `Study Guides/Heap Manager Designs/2/Low-level-design.md` and `VS_EE_Intern_Solution/MyHeap/LFH-Bucket-Policy.md`. The companion version 2 HLD explains the alignment, minimum-block, and physical-neighbor rationale. The source contains design sketches as well as implementation descriptions. The following differences are important when reading those sketches alongside this repository: | Original sketch or statement | Current behavior documented here | | --- | --- | | `BlockHeader`, lowercase helper names, and `HeapHandle` | Use `BLOCK_HEADER`, helpers such as `BlkSize`, and `HHEAP`. `HEAP` is exposed in the header. | | `FREE_BLOCK.Entry` and `CONTAINING_RECORD` recover a block | The heap overlays `NODE` at `header + MH_HEADER`; `BlockFromNode` subtracts `MH_HEADER`. There is no `FREE_BLOCK` type in this implementation. | | An allocated header is always 8 bytes | Historical layout only. Requested length is now always stored; aligned headers are 16/32 bytes on x64 Release/Debug and 8/16 bytes on Win32. | | Realloc merges with the next free block or trims a tail | Neither path is implemented. It retains current capacity or allocates, copies, and frees. | | One free-flow sketch clears `USED` before putting a block in a bucket | The bucket path sets both `USED` and `CACHED`. Returning to the backend clears both. | | A drained class must earn 16 new requests | Draining clears activation, not the activation counter, which saturates at 16. It can reactivate on its next request. | | A 64 KiB chunk is the minimum Windows commit size | 64 KiB is this allocator's growth policy. Reservation granularity and page-sized commitment are different OS concepts. | | Exhausting the fallback paths proves all memory is live | Failure can also reflect fragmentation, retained cache blocks, or an OS commit failure. | The paths above record where the design came from; the source directory is not a runtime or documentation-link dependency. ## Data structures | Structure or field | Meaning | | --- | --- | | `BLOCK_HEADER.Size` | Total block size combined with low-bit state flags. | | `MH_USED` | Bit 0: this block is physically in use, including a parked bucket block. | | `MH_PREV_USED` | Bit 1: the preceding physical block is in use. | | `MH_CACHED` | Bit 2: the block belongs to a size-class cache, not a live caller. | | `BLOCK_HEADER.UserSize` | Exact requested payload length in every build; zero for backend-free and cached blocks. | | Debug header fields | `Magic` identifies a header and `AllocId` identifies an allocation for reports. | | `BLOCK_FOOTER.Size` | Copy of a backend free block's packed size word, stored at the end of that block. | | `NODE` | `pPrev` and `pNext`, placed at the start of a free or parked block's payload. | | `HEAP.Base`, `Reserved`, `Committed` | Region address, reserved capacity, and committed extent. | | `HEAP.FreeHead` | Head of the backend free list. | | Bucket arrays | Heads, request counts, activation flags, parked lengths, recency, and window demand for each class. | | `HEAP.Lock` | Protects the heap's shared bookkeeping. | | Counters | Live block bytes, live blocks, successful allocations, and accepted frees. | `BytesInUse` counts total live **block** sizes, including overhead and rounding, not just requested payload bytes. Parked blocks are excluded from live counters. Reports and validation use the explicit cached flag rather than relying on an allocation ID to determine ownership. ### Block layout `MH_HEADER`, `MH_FOOTER`, and `MH_LINKS` round structure sizes to `MH_ALIGN`, which is 16 bytes on x64 and 8 on Win32. `MH_MIN_BLOCK` is their sum, ensuring a block can hold free-list metadata when freed. Request/header/guard addition and reservation rounding are checked before rounding arithmetic. ```mermaid flowchart TD A["Allocated block"] --> AH["Header: packed size and optional Debug fields"] AH --> AP["Caller payload"] AP --> AG["Debug only: 8 guard bytes, then any slack"] F["Backend free block"] --> FH["Header"] FH --> FN["NODE in former payload"] FN --> FS["Remaining free space"] FS --> FF["Footer at block end"] P["Parked bucket block"] --> PH["Header remains marked used"] PH --> PN["NODE in former payload; no valid caller data"] ``` An allocated block does not need a valid footer. The footer becomes meaningful when the block enters the backend free list. | Build | Aligned header | Aligned node storage | Aligned footer storage | Minimum block | | --- | --- | --- | --- | --- | | x64 Release | 16 | 16 | 16 | 48 | | x64 Debug | 32 | 16 | 16 | 64 | | Win32 Release | 8 | 8 | 8 | 24 | | Win32 Debug | 16 | 8 | 8 | 32 | These sizes are bytes, not guaranteed payload lengths. The footer's actual size word is one `SIZE_T`; the storage above includes alignment padding. Class rounding can raise the smallest served allocation further, such as Win32 Release requests rounding to the 32-byte class. ### Worked example: flags share the size word Consider a 48-byte block whose preceding physical block is used. Setting this block used gives the packed value `48 | 1 | 2 = 51`. - `51 & MH_SIZE_MASK` gives 48: the distance to the next block. - `51 & MH_USED` is nonzero: the current block is physically used. - `51 & MH_PREV_USED` is nonzero: the predecessor is physically used. ```mermaid flowchart LR P["Packed Size = 51"] --> S["Mask off alignment bits: size = 48"] P --> U["Bit 0: USED = 1"] P --> V["Bit 1: PREV_USED = 1"] ``` Parking the example block additionally sets bit 2: `51 | MH_CACHED = 55`. The size mask still recovers 48. Unknown low flag bits are rejected by validation. Alignment satisfies the native 16/8-byte contract, not arbitrarily over-aligned types. ### Worked example: request size is not block size These examples assume **x64 Release** and a backend free block large enough to split. Class rounding happens even before a class becomes active. | Requested payload | Header plus payload | Sixteen-byte rounding, then 48-byte minimum | Selected total size after class rounding | | --- | --- | --- | --- | | 2 bytes | 18 | 48 | 48 | | 24 bytes | 40 | 48 | 48 | | 25 bytes | 41 | 48 | 48 | | 40 bytes | 56 | 64 | 64 | | 20,000 bytes | 20,016 | 20,016 | 20,016; too large for a bucket class | The original four-byte-layout examples no longer describe the binary layout. These values follow the current header and alignment. If a remainder is too small to split, the actual allocated block can be larger still. In **x64 Debug**, a 25-byte payload needs `32 + 25 + 8 = 65` bytes before rounding. It rounds to the 80-byte class. Guards begin directly after the requested payload, not after the rounded capacity. ### Pointer helpers - `BlkSize`, `BlkUsed`, `BlkCached`, `PrevUsed`: read the packed size and flags. - `PayloadFromHdr`, `HdrFromPayload`: move between a header and its payload. - `NodeOfBlock`, `BlockFromNode`: move between a block and its embedded node. - `NextBlock`: advance by the current total block size. - `FooterOf`: find the current block's final footer-sized space. - `FirstBlock`: skip the aligned `HEAP` structure. - `SetSize`, `WriteFreeFooter`, `SetNextPrevUsed`: maintain size and neighbor metadata. - `BlockShapeValid`: check remaining-region bounds, minimum size, flags, requested length, and Debug magic before advancing. - `FindPayloadBlock`: scan valid physical boundaries and compare offsets before accepting a caller-supplied pointer. Free/realloc do not blindly dereference a header derived from that pointer. - `RequestSizeValid`: reject overflow before adding header, guard, and alignment padding. For an illustrative x64 Release block starting at byte offset 4,096 with a total size of 48: | Address calculation | Result | | --- | --- | | Payload or embedded free-node address | `4096 + MH_HEADER = 4112` | | Recover header from that node | `4112 - MH_HEADER = 4096` | | Next physical header | `4096 + 48 = 4144` | | Footer location while backend-free | `4096 + 48 - MH_FOOTER = 4128` | These are illustrative offsets, not required addresses. For a free predecessor, read its footer immediately before the current header and subtract the recovered size. Only do that when `PrevUsed` says the predecessor is free and the heap metadata is valid. ## Splitting and coalescing examples from the design Suppose the backend finds a 256-byte free block for a selected total need of 48 bytes. `SplitBlock` makes a 48-byte used block and a 208-byte free remainder. The remainder is large enough for its own header, node, and footer, so it is inserted into the free list. ```mermaid flowchart LR A["Backend free block: 256 bytes"] --> B["Used block: 48 bytes"] A --> C["Free remainder: 208 bytes"] C --> D["Write footer and insert remainder"] ``` If instead the free block were 64 bytes, the leftover would be only 16 bytes. That is below the x64 Release minimum of 48, so the whole 64-byte block is handed out. It is better to retain a small amount of slack than create an unusable free block. For a **backend free**, suppose physical A is 64 bytes and free, B is 48 bytes and being freed, and C is 80 bytes and free. `BackendFree` unlinks C and merges forward, then finds A using its footer, unlinks A, and merges backward. The result is one 192-byte free block with a new footer and one free-list entry. This example assumes B is not parked in a bucket. The free predecessor and successor are found from physical metadata, not by scanning list order. Updating the successor's `MH_PREV_USED` bit is essential: the next free must know whether it can safely interpret a preceding footer. ## Creating and growing a heap `my_heap_create` rounds the requested reservation to 64 KiB, with a minimum of one chunk. It reserves with `VirtualAlloc(MEM_RESERVE)`, commits the first chunk with `MEM_COMMIT`, zeroes the heap metadata, builds one initial free block, initializes the lock, and logs the result. If the first commit fails, it releases the reservation. `GrowHeap` requests a 64 KiB-rounded amount large enough for the needed block, limited using the remaining reservation rather than an unchecked size addition. `FreePredecessorAtSeam` walks physical blocks to the old committed boundary; it no longer guesses a predecessor from arbitrary bytes at the end of a used payload. If a validated free block ends there, growth extends it; otherwise, it inserts a new free block. The reservation never moves or expands. No function decommits pages. `my_heap_destroy` deletes the lock and releases the whole region with `VirtualFree(MEM_RELEASE)`. The original design chooses 64 KiB chunks to batch OS calls instead of requesting backing for every small allocation. This is a policy tradeoff, not a claim that Windows cannot commit page-sized ranges. `MEM_RESERVE` claims addresses; `MEM_COMMIT` makes pages usable, while Windows controls their physical residency. For example, an 8 KiB backend-free tail followed by a successful 64 KiB commit can become one 72 KiB free block across the old boundary. If that tail is a live or parked block, the new committed span remains a separate free block. `FreePredecessorAtSeam` is the implementation's boundary check before attempting the merge. ## Size classes and cache policy Classes apply to total block size **after header, guard, alignment, and minimum-size handling**. | Bucket indices | Total sizes | Step | | --- | --- | --- | | 0–14 | 32–256 bytes | 16 bytes | | 15–26 | 320–1,024 bytes | 64 bytes | | 27–38 | 1,280–4,096 bytes | 256 bytes | | 39–50 | 5,120–16,384 bytes | 1,024 bytes | `SizeClassOf` returns the next suitable class, or `-1` for a larger block. `BucketClassSize` turns the index back into its size. - `BucketCount` increments on class allocation requests, before allocation success is known, and saturates at 16. Reaching 16 activates the class for future frees. - `BucketWindowAllocs` records class request demand since the last periodic reset, saturating at 256 because further demand cannot increase the cap. - The parked-block cap is `clamp(4 + windowDemand, 4, 256)`. - The warm-drain keep count is integer `cap / 8`; it can be zero. - `HeapTick` is `TotalAllocs + TotalFrees`. - A bucket is cold after at least 4,096 ticks since its last push or pop. - At `my_malloc` entry, a tick value divisible by 4,096 triggers cold retirement and a reset of all window-demand counters. This is an allocation-entry check, not a timer or background thread. - Backend failure can trigger cold retirement and warm draining independently of that periodic check. - Fully draining a bucket clears its active flag, but does not reset `BucketCount`. A previously busy class can reactivate on its next request; it does not necessarily need 16 new requests. `BucketPush` and `BucketPop` change links only. Their callers maintain bucket length, recency, and live-allocation counters. ### Worked policy example: cap, keep, and cold retirement The original policy describes three different quantities. Occupancy (`BucketLen`) says how many blocks are parked. Recency (`BucketLastUse`) says when the last bucket push/pop happened. Demand (`BucketWindowAllocs`) says how many class requests have occurred in this window. Do not use the lifetime activation counter as the parked length. | Window demand | Computed cap | Warm-drain keep count | | --- | --- | --- | | 0 | 4 | 0 | | 12 | 16 | 2 | | 100 | 104 | 13 | | 256, saturated | 256, after clamping | 32 | If demand is 12 and 10 blocks are parked, a warm drain returns eight blocks to the backend and leaves two. A cold retirement returns all ten instead. The keep count is a warm-drain target, not a promise that every class always has that many spare blocks. After window demand resets, the computed cap can drop below the existing parked length. That does not instantly evict every excess block: the cap gates subsequent pushes, while draining or reuse reduces occupancy. The absolute configured cap is 256 blocks per class; it is a block-count limit, not a byte limit. ```mermaid flowchart TD A["Backend cannot satisfy a request"] --> B["Cold classes: drain to zero"] B --> C{"Suitable block reclaimed?"} C -->|"Yes"| R["Allocate from backend"] C -->|"No"| D["Warm classes: trim toward cap divided by 8"] D --> E{"Suitable block reclaimed?"} E -->|"Yes"| R E -->|"No"| F["Commit more within reservation and search"] F --> G{"Suitable block available?"} G -->|"Yes"| R G -->|"No"| N["Return NULL; not all cached bytes must be gone"] ``` Dividing by eight is a simple tuning choice from the original policy: retaining less favors reclamation; retaining more favors immediate reuse. The code has no background timer, no per-block age tracking, and no separate OS allocation for a bucket. ## `my_malloc` flow ```mermaid flowchart TD A["my_malloc"] --> B{"Invalid input, overflow, or request beyond reservation?"} B -->|"Yes"| N["Return NULL"] B -->|"No"| C["Lock; perform periodic retirement if due"] C --> D["Compute total need and size class; update class demand"] D --> E{"Active bucket has a block?"} E -->|"Yes"| P["Pop block and update bucket state"] E -->|"No"| F["Activate eligible class; find first backend fit"] F --> G{"Fit found?"} G -->|"No"| H["Retire cold buckets; retry if anything drained"] H --> I{"Fit found?"} I -->|"No"| J["Trim warm buckets to keep counts; retry if drained"] J --> K{"Fit found?"} K -->|"No"| L["Try GrowHeap and search again"] L --> M{"Growth succeeded and fit found?"} M -->|"No"| X["Unlock; return NULL"] G -->|"Yes"| S["Unlink block; split if remainder is large enough"] I -->|"Yes"| S K -->|"Yes"| S M -->|"Yes"| S P --> U["Clear cached flag; record requested size and counters; stamp Debug guard"] S --> U U --> R["Unlock; return payload"] ``` `FindFit` scans from `FreeHead`. `SplitBlock` creates a remainder only if it is at least `MH_MIN_BLOCK`; otherwise, the caller gets the whole block. Both paths update the next physical block's previous-used flag. ## `my_free` and coalescing ```mermaid flowchart TD A["my_free"] --> B{"Null heap or pointer?"} B -->|"Yes"| R["Return"] B -->|"No"| C["Lock; scan for a valid payload boundary"] C --> D{"Live and not cached?"} D -->|"No"| E["Log rejection; unlock"] E --> R D -->|"Yes"| F{"Debug guard intact, or Release build?"} F -->|"No"| E F -->|"Yes"| G["Reduce live counters; clear requested size; increment frees"] G --> H{"Exact class size, active bucket, below cap?"} H -->|"Yes"| I["Push to bucket; set used and cached flags; clear Debug allocation ID"] H -->|"No"| J["BackendFree: mark free and merge neighbors"] I --> U["Unlock"] J --> U U --> R ``` `BackendFree` first marks the block free. If the next physical block is free, it unlinks and merges it. If the previous-used flag is clear, it reads the preceding footer, finds the previous block, and merges backward. It writes the resulting footer, inserts the merged block at `FreeHead`, and clears the following block's previous-used flag. There is no full-list search for these neighbors. `FlRemove` unlinks a known node using its links. `DrainBucket` pops parked blocks and sends them through `BackendFree` without changing the caller-allocation counters again. ## `my_calloc` and `my_realloc` `my_calloc` rejects a null heap, zero factors, and multiplication overflow. It calls `my_malloc` for `count * size`, then zeroes exactly that many bytes on success. `my_realloc` follows these cases: 1. Null heap: return `NULL`. 2. Null pointer: behave like `my_malloc`. 3. Zero new size: free the old block and return `NULL`. 4. Check size arithmetic and locate a live, non-cached physical payload; reject invalid pointers or damaged Debug guards. If existing capacity fits, update requested length and guard and return the same pointer without splitting spare space. 5. Otherwise: allocate a new block, copy data, and free the old one. On allocation failure, return `NULL` and leave the old allocation intact. The copy length is `min(old requested size, new requested size)`. Padding and old guard bytes are not copied as caller data. Newly added bytes are not promised to be initialized. Copying happens outside the heap lock, so callers must own the payload exclusively. ## Validation and reports `ValidateHeapLocked`, used by validation, reports, and snapshots, checks physical block bounds and flags, requested lengths, predecessor-used flags, Debug magic/guards, free footers, absence of adjacent free blocks, and full coverage of the committed region. It recomputes live counts/bytes and checks allocation/free totals. `ValidateListLocked` bounds list traversal by the expected physical count and validates each node as a known payload boundary before reading links. It checks previous links, ownership state, exact bucket sizes, cached lengths, activation, and the absolute cap. Cycles, missing membership, invalid links, and counter mismatches are rejected. Because each node lookup can scan physical blocks, full validation can be `O(B²)`; it is not a cheap per-allocation check. `my_heap_report` first validates. It refuses an invalid heap; otherwise it prints counters and, in Debug, live non-cached blocks. Destruction does not automatically validate or report. ## Read-only snapshot API `my_heap_snapshot(heap, snapshot, blocks, capacity)` validates and copies one consistent view under `HEAP.Lock`. Both output buffers belong to the caller and must be outside this heap, non-overlapping, and alive for the call. The DLL neither allocates output buffers nor performs file I/O. - `MH_SNAPSHOT` contains reserved/committed extents, metadata/alignment/header/guard/minimum sizes, live/requested counters, totals, required block count, and 51 size/length/cap/active bucket records. - `MH_BLOCK_INFO` contains relative `Offset`, total `Size`, exact `Requested` bytes, `State`, and `BucketIndex`. State is free, live, or cached; non-cached blocks use bucket index `-1`. - A call with `blocks = NULL` and capacity 0 reports `ERROR_INSUFFICIENT_BUFFER` and fills the summary with the required count. On this error the block array is untouched. - Retry with enough caller-owned space. Concurrent changes can require another retry; a successful call is consistent, not permanently frozen heap state. - Null required arguments return `ERROR_INVALID_PARAMETER`; invalid heap integrity returns `ERROR_INVALID_DATA`. - No process addresses or payload contents are exported. Header and output structure layouts changed in this release, so rebuild the DLL and clients together; do not mix old binaries. ClientApp retries sizing up to four times, limits capture to 4,096 block records, and writes JSON only after the lock has been released. See [ClientApp LLD](../ClientApp/ClientApp_LLD.md) for schema version 1 and the static viewer boundary. ## Caller rules and known gaps Use live handles and pointers from the same heap and free each allocation only once. Boundary scans reject interior, foreign, and still-cached pointers without dereferencing them. They cannot identify an old alias after its address has been reused for a new live allocation. Valid handles and intact region ownership are prerequisites; this is not a security boundary for arbitrary writes to exposed heap metadata. Alignment is 16/8 bytes, not a general over-aligned allocator interface. Arithmetic checks prevent oversized wrapping requests; they do not make every OS failure recoverable. Debug guard failure rejects free/realloc and leaves the allocation owned by the caller. Release has no payload guard. The first-fit path does not run full validation before every list update; corruption must not be treated as a supported input state.