How malloc and free Work: Inside Dynamic Memory Allocation

malloc / free Overview

void *malloc(size_t size)

allocates a memory block of the requested size (in bytes) and returns a pointer to the usable space. The returned pointer is of type void* and must be cast to the appropriate type before use. void free(void *ptr) releases a memory block previously allocated by malloc. The ptr argument must be the exact pointer returned by malloc.

Example usage:

int *ptr;
ptr = (int *)malloc(10 * sizeof(int));
/* use ptr */
free(ptr);

System Calls for Dynamic Memory Allocation: brk / sbrk

Dynamic memory resides in the heap, which grows upward in address space. Linux provides two system calls:

int brk(void *addr);
void *sbrk(intptr_t increment);

brk

returns the current top of the heap. sbrk expands the heap by the specified increment and returns the previous break address. In practice, user‑level allocators first use sbrk to grow the heap and then manage the memory with malloc / free, reducing the number of system calls.

Implementation Idea of malloc / free

malloc

typically maintains a free list of unused blocks. Each free block starts with a memory control block (MCB) that stores metadata such as availability, size, and links to other blocks. The MCB is invisible to the user; malloc returns the address immediately after the MCB.

When allocating, the allocator searches the free list for a block large enough, marks it as used, and returns the usable portion. If no suitable block exists, the allocator requests more heap memory via sbrk. free marks the block as available and inserts it back into the free list, possibly merging adjacent free blocks.

Implementation Method 1: Explicit Free List + Whole‑Block Allocation

This simple approach stores both allocated and free blocks in a single linked list. The MCB structure is:

struct mem_control_block {
    int is_available; // 1 if free, 0 if allocated
    int size;           // size of the usable space
};

Allocation uses a first‑fit search. If a suitable block is found, it is marked unavailable and the pointer after the MCB is returned. If not, the heap is expanded with sbrk. The corresponding free implementation:

void free(void *ptr) {
    struct mem_control_block *mcb = ptr - sizeof(struct mem_control_block);
    mcb->is_available = 1;
}

Drawbacks:

The list contains both allocated and free blocks, requiring a full traversal on each allocation.

First‑fit with whole‑block allocation leads to significant internal fragmentation.

Implementation Method 2: Explicit Free List + On‑Demand Allocation

Here the free list contains only unallocated blocks. When allocating, the allocator finds a block large enough, splits off the requested size from the tail, and keeps the remainder in the free list. If the remainder is too small to hold an MCB, the whole block is removed from the list.

Advantages:

Traversal is faster because only free blocks are examined.

Only the exact required size is allocated, reducing waste.

Disadvantage: repeated allocations can fragment the free space into many small pieces, causing external fragmentation and requiring occasional compaction, which is costly.

Implementation Method 3: Segregated Free Lists

Instead of a single list, multiple free lists are maintained, each for blocks of a specific size class (often powers of two). Allocation selects the appropriate size class and searches that list; if none is found, a larger class is consulted or the heap is expanded.

Benefits include O(1) allocation and deallocation when using the head of a list, and reduced metadata overhead because block size is implicit. However, internal and external fragmentation can still occur.

Simple Segregated Storage

Each size class contains blocks of identical size. Allocation takes the first block from the appropriate list or splits a newly obtained chunk. Freeing simply inserts the block at the head of its class list.

Segregated Fit

Similar to simple segregation but each class covers a range of sizes (e.g., 1‑2, 3‑4, 5‑8 bytes, etc.). The allocator chooses the smallest class that can satisfy the request, possibly splitting a block and returning the remainder to the appropriate class.

Buddy System

The buddy system is a special case of segregated fit where each class size is a power of two. The allocator starts with a single large free block. To satisfy a request, it repeatedly splits the smallest larger block until a block of the exact power‑of‑two size is obtained. On free, a block is merged with its buddy if the buddy is also free, propagating upward.

Advantages: fast search and merge. Disadvantage: mandatory power‑of‑two block sizes cause considerable internal fragmentation, making it unsuitable for general workloads.

tcmalloc

Google’s Thread‑Caching malloc (tcmalloc) uses per‑thread caches of small objects to avoid contention. Small allocations are served from a thread‑local cache; larger requests fall back to a global arena. This design eliminates locking for most thread‑local allocations, improving multithreaded performance.

Summary

malloc manages heap memory using linked structures. Various implementations—single free list, segregated lists, buddy system, and tcmalloc—offer different trade‑offs between speed, fragmentation, and complexity. All allocators store a hidden control block before the user‑visible memory, ensure proper alignment (8‑byte on 32‑bit, 16‑byte on 64‑bit), and rely on system calls like sbrk to grow the heap when needed.