How Does malloc Actually Work? Inside a Simple Memory Allocator

Why a Memory Allocator Is Needed

Programs cannot know in advance how much memory they will need, so they rely on dynamic memory allocation (malloc, new) to request and release memory at runtime.

Modeling the Heap as a Parking Lot

The heap can be visualized as a long parking lot where each free block is a parking space; allocating memory is finding a suitable spot, and freeing memory is driving the car out.

Key Problems to Solve

Implement a malloc function that finds a suitable free block and returns its address.

Implement a free function that returns a used block to the heap.

Design of Free‑Block Management

Each block stores a 32‑bit header: the lower bit marks the block as free (0) or allocated (1), and the remaining 31 bits record the block size (up to 2 GB). The header occupies 4 bytes; the remaining bytes are the payload returned to the caller.

Allocation Strategies

First Fit

Scan from the beginning of the heap and return the first free block that satisfies the request. Simple but can leave many small fragments at the front of the heap.

Next Fit

Start the scan from the position of the last successful allocation. This reduces search time but may use memory less efficiently than First Fit.

Best Fit

Search all free blocks and return the smallest block that fits the request, minimizing internal fragmentation but requiring a full scan.

Choosing a Strategy

For the simple allocator presented, First Fit is selected because of its simplicity.

Splitting and Internal Fragmentation

If a free block is larger than needed, the allocator splits it: the first part (header + payload) is marked allocated, and the remainder becomes a new free block with its own header. This avoids wasting the entire block as internal fragmentation.

Freeing Memory and Coalescing

When a block is freed, adjacent free blocks must be merged (coalesced) to avoid external fragmentation. The allocator can merge immediately or defer merging until a later allocation fails to find a suitable block.

Efficient Coalescing with Footer

To quickly locate the previous block during coalescing, a footer identical to the header is placed at the end of each block. By reading the 4‑byte footer of the current block, the allocator can move backward to the previous block without scanning from the heap start.

Final Design Summary

The presented simple memory allocator uses a First Fit strategy, splits oversized blocks, immediately coalesces adjacent free blocks, and adds a footer to each block for fast backward traversal, providing a clear illustration of how malloc and free can be implemented.

Example of a repetitive allocation‑free pattern that stresses immediate coalescing:

free(ptr); obj* ptr = malloc(12); free(ptr); obj* ptr = malloc(12); ...