Dynamic Memory: malloc, free & the Heap

Before touching a single malloc, you need to know where heap memory actually lives. A running Linux process sees a virtual address space — a private, contiguous range of addresses that the kernel maps to physical RAM on demand. This space is divided into distinct regions:

• Text segment: your compiled code (read-only, executable)
• Data/BSS segment: global and static variables
• Heap: starts just above BSS, grows upward toward higher addresses
• Memory-mapped region: mmap-allocated areas (also used by malloc for large requests)
• Stack: starts near the top of the address space, grows downward

The heap's upper boundary is called the program break (brk). The C library's allocator expands the heap by calling the brk() or sbrk() system call, which asks the kernel to extend the program break upward, giving the allocator more virtual pages to manage. For large allocations (typically >128 KB in glibc), malloc instead calls mmap(MAP_ANONYMOUS) to get a fresh page directly, bypassing the heap entirely.

You can observe this layout live:

# Run a program, then look at its memory map
cat /proc/$(pgrep my_program)/maps

You'll see lines tagged [heap], [stack], and unnamed regions from mmap. This visualization — the stack at the top going down, the heap in the middle going up — is not just academic. It explains why stack overflow (growing the stack too far down) and heap overflow (corrupting data beyond an allocation) collide in catastrophic ways.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int global_var = 42;          // data segment

int main(void) {
    int stack_var = 1;        // stack
    int *heap_var = malloc(4); // heap

    printf("text  (main):   %p\n", (void*)main);
    printf("data  (global): %p\n", (void*)&global_var);
    printf("heap  (malloc): %p\n", (void*)heap_var);
    printf("stack (local):  %p\n", (void*)&stack_var);

    free(heap_var);
    return 0;
}
// On x86-64 Linux you will see addresses that confirm
// text < data < heap < stack (roughly).

malloc(size_t n) allocates at least n bytes and returns a void* pointer to the first byte. The contents are uninitialized — they contain whatever garbage was in that memory before. This is a deliberate design choice for performance: clearing memory costs time, and the programmer often overwrites it immediately anyway.

calloc(size_t nmemb, size_t size) allocates nmemb * size bytes and zero-initializes every byte. It also has an important subtlety: it performs the multiplication safely and checks for overflow. malloc(nmemb * size) can silently wrap around on 32-bit systems if the product overflows size_t. For arrays of structs, always prefer calloc.

Return value contract: On success, the returned pointer is aligned to _Alignof(max_align_t) — at least 8 bytes on 32-bit, 16 bytes on 64-bit systems. This guarantees the pointer is safe to cast to any C type. On failure (out of memory), malloc returns NULL. You must check for NULL; failing to do so and then dereferencing the pointer is undefined behavior that typically causes a segfault.

The analogy: malloc is like asking a hotel for a room. The hotel (allocator) finds a vacant room, marks it occupied, and hands you a key (pointer). The room might be messy from the previous guest (uninitialized data). calloc is like asking for a room that's been cleaned first.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
    /* malloc: uninitialized */
    int *a = malloc(5 * sizeof(int));
    if (!a) { perror("malloc"); return 1; }
    /* a[0]..a[4] contain garbage here */
    a[0] = 10; a[1] = 20; /* must initialize before reading */

    /* calloc: zero-initialized, overflow-safe */
    int *b = calloc(5, sizeof(int));
    if (!b) { perror("calloc"); free(a); return 1; }
    /* b[0]..b[4] are guaranteed 0 */

    printf("a[0]=%d  b[0]=%d\n", a[0], b[0]); // 10  0

    free(a);
    free(b);
    return 0;
}

realloc(void *ptr, size_t new_size) asks the allocator to resize an existing allocation. Its behavior has several important cases:

1. If the block can grow in place (there is free memory immediately after it), the allocator expands it and returns the same pointer.
2. If not, the allocator allocates a fresh block, copies the old data into it, frees the old block, and returns the new pointer. The old pointer is now invalid — you must not use it.
3. If ptr is NULL, realloc behaves exactly like malloc(new_size).
4. If new_size is 0, behavior is implementation-defined (may free and return NULL, or return a unique non-null pointer that must be freed).

The classic bug with realloc: assigning the result back to the same pointer. If realloc fails (returns NULL), you've lost the original pointer and created a memory leak.

// WRONG:
buf = realloc(buf, new_size); // if this returns NULL, original buf is lost!

// CORRECT:
void *tmp = realloc(buf, new_size);
if (!tmp) { /* handle error */ free(buf); return -1; }
buf = tmp;

Think of realloc like asking your hotel for a bigger room. If the room next door is empty, they knock down the wall. If not, they move you to a bigger room elsewhere and give you a new key. If they're fully booked, you stay put and get NULL back — but you still have your old key (old pointer) that you must not lose.

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    /* Build a dynamic array that grows on demand */
    size_t cap = 4, len = 0;
    int *arr = malloc(cap * sizeof(int));
    if (!arr) return 1;

    for (int i = 0; i < 10; i++) {
        if (len == cap) {
            cap *= 2;
            int *tmp = realloc(arr, cap * sizeof(int));
            if (!tmp) { free(arr); return 1; }
            arr = tmp;
        }
        arr[len++] = i * i;
    }

    for (size_t i = 0; i < len; i++)
        printf("%d ", arr[i]); // 0 1 4 9 16 25 36 49 64 81
    printf("\n");

    free(arr);
    return 0;
}

free(void *ptr) returns memory to the allocator's pool. It does not clear the memory, does not change the pointer variable (which still holds the old address), and does not talk to the kernel (usually — the allocator keeps a private pool and only occasionally returns pages to the OS via brk/munmap).

Free establishes the ownership contract, which is the central discipline of C memory management:

• Every malloc/calloc/realloc result must be freed exactly once.
• After free(p), the pointer p is a dangling pointer — it points to memory that may be reused for something else. Reading or writing through it is undefined behavior.
• The pointer passed to free must be the exact pointer returned by malloc (or NULL, which free silently ignores). Passing a pointer into the middle of an allocation, or a stack address, or a double-free of the same pointer, is all undefined behavior.

A useful idiom after freeing: set the pointer to NULL immediately. Dereferencing NULL crashes loudly and reproducibly (segfault), which is far better than a silent corruption from a dangling pointer access. Some style guides mandate this. Modern sanitizers (AddressSanitizer) will catch use-after-free regardless, but the NULL-after-free habit is good discipline.

free(p);
p = NULL; // now any accidental use will segfault loudly

#include <stdlib.h>

int main(void) {
    int *p = malloc(sizeof(int));
    if (!p) return 1;
    *p = 42;

    free(p);
    p = NULL; // good habit: poison the dangling pointer

    // free(p);  // safe: free(NULL) is a no-op
    // *p = 1;   // would crash immediately (NULL deref) rather
    //           // than silently corrupt memory
    return 0;
}

A memory leak occurs when allocated memory is never freed. The allocator has marked those bytes as in-use, but your program has lost all pointers to them — they can never be freed. Over time, a leaking program consumes more and more RAM until the system OOM-killer (out-of-memory killer) terminates it, or the machine slows to a crawl.

Leaks can be subtle:

• Lost pointer: the only pointer to an allocation is overwritten before freeing.
• Early return: a function allocates, then returns early on an error path without freeing.
• Leaked containers: freeing a linked-list's head node without freeing the nodes it points to.

The standard tool for catching leaks is Valgrind (valgrind --leak-check=full ./myprog). It instruments every allocation and reports anything not freed at program exit, including a stack trace of where the allocation happened. On Linux you can also use AddressSanitizer (-fsanitize=address) which is faster and catches more bug types.

Note: in short-lived programs, the OS reclaims all memory on process exit, so leaks only matter during program execution. But in long-running daemons (web servers, the kernel itself), leaks are fatal. The Linux kernel uses kmemleak for exactly this purpose.

#include <stdlib.h>
#include <stdio.h>

char *make_greeting(const char *name) {
    // Caller is responsible for freeing this!
    char *buf = malloc(64);
    if (!buf) return NULL;
    snprintf(buf, 64, "Hello, %s!", name);
    return buf;
}

int main(void) {
    char *g = make_greeting("kernel hacker");
    if (!g) return 1;
    puts(g);
    free(g);   // <-- must free; omitting this is a leak
    g = NULL;
    return 0;
}
// Compile and check:
// gcc -g leak.c -o leak
// valgrind --leak-check=full ./leak

Use-after-free (UAF) is accessing memory through a pointer after that memory has been freed. It is one of the most dangerous bugs in systems code and is responsible for a large fraction of Linux kernel CVEs.

Why is it so dangerous? After free(p), the allocator may immediately hand that memory to the next malloc call. So another part of your program now owns those bytes. When you read through the old p, you might read the new owner's data. When you write through p, you corrupt the new owner's data — potentially overwriting a function pointer, a length field, or a next-pointer in a data structure. An attacker who can trigger a UAF and control what gets allocated next can often exploit this to gain arbitrary code execution (the heap spray technique).

The timeline:

ptr = malloc(64)   →  allocator marks block USED
free(ptr)          →  allocator marks block FREE
new_ptr = malloc(64)  →  allocator hands same block to someone else
*ptr = 0xdeadbeef  →  corrupts new_ptr's data! (UAF write)
val = *ptr         →  reads new_ptr's data (UAF read)

AddressSanitizer (-fsanitize=address) poisons freed memory so any access is caught immediately with a detailed report. In the kernel, KASAN (Kernel Address SANitizer) does the same thing. When working on kernel code, always test with CONFIG_KASAN=y.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
    char *a = malloc(32);
    strcpy(a, "secret data");
    free(a);
    // a is now dangling. This is USE-AFTER-FREE:
    printf("%s\n", a); // undefined behavior — may print garbage,
                       // may crash, may print someone else's data
    return 0;
}
// Detect with AddressSanitizer:
// gcc -fsanitize=address -g uaf.c -o uaf && ./uaf
// Output will show: heap-use-after-free on address ...

Double-free means calling free(p) twice on the same non-NULL pointer. After the first free, the allocator has inserted that block into its free list. The second free sees the block again and inserts it a second time — now the same block appears twice in the free list. The next two malloc calls may both return pointers to the same block, giving two different parts of your program aliased access to the same memory. Both think they own it exclusively. Chaos follows.

Worse, in older versions of glibc's ptmalloc2, double-free was directly exploitable: an attacker could craft a sequence of allocations/frees that caused the allocator's unlink macro to write an attacker-controlled value to an attacker-controlled address — an arbitrary write primitive. Modern glibc has mitigations (safe-unlinking, tcache double-free detection), but double-free is still undefined behavior and still dangerous.

The NULL-after-free idiom completely prevents accidental double-frees, because free(NULL) is defined to do nothing:

free(p);
p = NULL;
// ... some code ...
free(p); // no-op, safe

This is why that one-line idiom matters so much in practice.

#include <stdlib.h>

int main(void) {
    int *p = malloc(sizeof(int));
    if (!p) return 1;
    *p = 99;
    free(p);
    free(p); // DOUBLE FREE: undefined behavior
             // In glibc: likely "free(): double free detected"
             // then SIGABRT (program crash)
    return 0;
}
// Compile with ASAN to get a clean, actionable report:
// gcc -fsanitize=address -g double_free.c -o df && ./df

A dangling pointer is any pointer that no longer refers to valid memory. There are two common sources:

1. Heap dangling pointer: freeing the memory a pointer refers to (covered above).
2. Stack dangling pointer: returning a pointer to a local variable. When the function returns, its stack frame is deallocated; the pointer now points into no-man's-land.

Stack dangling pointers are surprisingly easy to make:

int *bad(void) {
    int x = 42;
    return &x; // x lives on the stack frame of bad()
               // which is gone when bad() returns
}

The compiler will warn about this (-Wall enables -Wreturn-local-addr), but only for simple cases. More complex cases (returning a pointer to a struct field, returning a reference through multiple levels of indirection) can slip through.

The general rule is: a pointer's lifetime must not exceed the object it points to. In C, tracking this is entirely the programmer's responsibility — there is no borrow checker, no ownership type. This is precisely the gap that Rust's borrow checker fills, and why Rust is being added to the Linux kernel.

#include <stdio.h>

/* WRONG: returns pointer to stack variable */
int *make_int_bad(int val) {
    int x = val;  // x is on the stack of make_int_bad
    return &x;   // dangling after return!
}

/* RIGHT: returns pointer to heap variable */
int *make_int_good(int val) {
    int *p = malloc(sizeof(int));
    if (p) *p = val;
    return p;   // caller must free this
}

int main(void) {
    int *bad  = make_int_bad(42);  // undefined behavior to use
    int *good = make_int_good(42); // valid until free()
    if (good) {
        printf("%d\n", *good); // 42
        free(good);
    }
    return 0;
}

Fragmentation occurs when the heap has enough total free memory to satisfy a request, but not enough contiguous free memory. Imagine you've done a long sequence of alternating allocations and frees, leaving a checkerboard of small free blocks interspersed with live allocations. A large malloc(1MB) fails even though you have 2 MB free — because no single free block is 1 MB.

There are two kinds:

• External fragmentation: free space is split into many small non-contiguous chunks.
• Internal fragmentation: the allocator gives you more bytes than you asked for (to align the next block, or to avoid managing tiny leftover chunks), so some bytes inside an allocated block are wasted.

Allocators fight external fragmentation primarily through coalescing: when a block is freed, immediately merge it with adjacent free blocks if possible. This is why the allocator stores metadata (size and free/used flags) adjacent to each block — it needs to find neighbors quickly. Glibc's ptmalloc2 stores a header before each block (containing size and flags) and a footer at the end of each free block (a copy of the header, for backward merging — the boundary-tag technique).

Fragmentation is why slab allocator exists in the kernel: for objects of a fixed size (like task_struct, which is always the same size), a slab keeps a cache of same-size objects, which never fragment because every hole is exactly the right size for the next allocation.

/* Illustrate the boundary-tag layout that allocators use.
 * Real glibc malloc_chunk looks roughly like this: */

#include <stddef.h>

typedef struct chunk {
    size_t prev_size;  /* size of previous chunk if free
                          (footer of prev chunk, for coalescing) */
    size_t size;       /* size of this chunk + flags in low bits:
                          bit 0 = PREV_INUSE
                          bit 1 = IS_MMAPED
                          bit 2 = NON_MAIN_ARENA */
    /* When FREE, the user data area holds:
       struct chunk *fd;  forward pointer to next free chunk
       struct chunk *bk;  backward pointer to prev free chunk
       When IN USE, user data starts here. */
} malloc_chunk;

/* The pointer malloc() returns is:
   (malloc_chunk*) p + offsetof(malloc_chunk, size) + sizeof(size_t)
   i.e., just past the size field — user data starts right there */

Now the payoff: how does malloc actually work internally? Understanding this makes you a far better systems programmer.

The core data structure is the free list: a linked list of free memory blocks. When you call free(p), the allocator inserts the block into this list. When you call malloc(n), the allocator searches the free list for a block of at least n bytes.

glibc ptmalloc2 (used on virtually all Linux systems) uses a more sophisticated structure called bins, organized by size for O(1) or O(log n) allocation:

• tcache (thread cache): Per-thread singly-linked lists for the 64 most common sizes (<=1032 bytes). malloc checks here first — no locking needed, very fast.
• fastbins: Small fixed-size bins for blocks up to ~80 bytes. LIFO (stack-like). No coalescing — fast, but can cause fragmentation.
• smallbins: 62 doubly-linked lists for sizes 16–512 bytes (in 8-byte increments). FIFO. Coalescing happens here.
• largebins: 63 bins for sizes >= 512 bytes, with each bin covering a range. Sorted within the bin for best-fit search.
• unsorted bin: newly freed chunks go here first, acting as a cache. On next malloc, they get sorted into proper bins.
• top chunk (wilderness): the big unexplored chunk at the top of the heap. If no bin can satisfy a request, ptmalloc carves from the top.

For allocations > ~128 KB, ptmalloc bypasses all of this and calls mmap() directly. On free, the memory is immediately returned to the OS via munmap(). This avoids one very large allocation permanently consuming heap address space.

The key insight: the allocator's job is to be fast (avoid syscalls, minimize searching) while being memory-efficient (minimize fragmentation). Every design choice in ptmalloc is a tradeoff between these goals. The kernel's slab allocator makes the same tradeoffs, just with the additional constraint of running in an interrupt context where you can't block.

/* You can observe allocator behavior with a simple experiment.
 * Notice how malloc returns pointers 16 or 32 bytes apart
 * (the minimum chunk size includes the header overhead): */
#include <stdio.h>
#include <stdlib.h>

int main(void) {
    void *a = malloc(1),  *b = malloc(1),  *c = malloc(1);
    void *d = malloc(100),*e = malloc(100),*f = malloc(100);

    printf("tiny:  %p %p %p (diff %ld)\n",
        a, b, c, (char*)b - (char*)a);
    printf("small: %p %p %p (diff %ld)\n",
        d, e, f, (char*)e - (char*)d);
    // On x86-64 glibc: tiny diff = 32 (min chunk = 32 bytes)
    // small diff = 112 (100 + 8-byte header, rounded to 16)
    free(a); free(b); free(c);
    free(d); free(e); free(f);
    return 0;
}

Dynamic memory bugs are hard to catch by code inspection alone — the corruption often manifests far from the cause. Two essential tools make them visible:

Valgrind (valgrind --leak-check=full --track-origins=yes ./prog) runs your program in a virtual machine that tracks every allocation and every memory access. It can report: illegal reads/writes, use of uninitialized values, memory leaks (with allocation stack traces), and double-frees. The cost is ~10-50x slowdown. Use it during testing on smaller inputs.

AddressSanitizer (ASan) (gcc -fsanitize=address -g prog.c) is a compile-time instrumentation that inserts shadow memory: for every 8 bytes of application memory, it keeps 1 byte recording whether those bytes are valid. On every memory access, a check is inserted. Much faster than Valgrind (2x overhead), with richer output. Also catches stack buffer overflows and global overflows. Combine with -fsanitize=undefined (UBSan) to catch integer overflow, null dereference, and other UB.

Workflow for writing correct C: compile with -Wall -Wextra -g -fsanitize=address,undefined during all development. Only remove the sanitizers for release builds. Run Valgrind on the full test suite before any commit. This is the discipline that serious kernel contributors apply.

In the kernel: CONFIG_KASAN (Kernel ASan), CONFIG_KMSAN (Kernel MSan for uninitialized reads), and CONFIG_KMEMLEAK (for kernel memory leaks) provide the same coverage at the kernel level.

# Compile with full sanitizer coverage
gcc -Wall -Wextra -g \
    -fsanitize=address,undefined \
    -fno-omit-frame-pointer \
    program.c -o program

# Run — any memory error prints to stderr with a stack trace
./program

# For leak detection specifically:
Asan_OPTIONS=detect_leaks=1 ./program

# Or with Valgrind for more thorough coverage:
valgrind --leak-check=full \
         --show-leak-kinds=all \
         --track-origins=yes \
         --verbose \
         ./program