7. Memory Management

Every C program is a story about memory: where objects live, how long they last, and who is responsible for reclaiming them. C gives you direct control over all three, which is why C programs can be fast and small — and why the majority of security vulnerabilities in C code are memory bugs. This chapter maps the regions of a running process, teaches the dynamic allocation API precisely, catalogues the classic memory errors with the tools that catch them, and finishes with the allocation strategies experienced C programmers reach for when malloc per object is not good enough.

<a id="71-memory-model"></a>

7.1 Memory Model

Before allocating anything you need a mental picture of where memory comes from. This section walks through the address space of a running process, the fundamental stack/heap distinction, the storage that exists for the whole program run, the read-only regions, and the rule that ties it all together: object lifetime.

Process Memory Layout

Theory

When you run a program, the operating system does not hand your code a flat undifferentiated pile of bytes. It builds an address space: a range of virtual addresses divided into regions, each with different contents, different permissions, and a different growth behaviour. Knowing which region an address belongs to tells you almost everything you need to know about it — whether you may write to it, how long it will remain valid, and who is going to clean it up.

The classic layout, from low addresses to high, looks like this on a typical Unix-like system:

• Text (code) segment — the machine instructions of your program, plus (usually) string literals and other constants. Read-only and executable. Writing here traps.
• Initialized data (.data) — global and static variables with a non-zero initializer. Read/write, and their initial values are stored in the executable file itself.
• Uninitialized data (.bss) — global and static variables that are zero or have no initializer. Read/write, and not stored in the file: the loader simply maps a zeroed region, which is why a program with a 100 MB global array can have a tiny executable. ("bss" is a historical assembler mnemonic; treat it as a name.)
• Heap — the region malloc carves allocations out of. It grows upward, toward higher addresses, as the allocator asks the kernel for more space.
• Memory-mapped region — shared libraries, large malloc blocks, and anything you map with mmap. Sits between the heap and the stack.
• Stack — one region per thread, holding function call frames. It grows downward, toward lower addresses, as calls nest.

Two properties are essential. First, these are virtual addresses: the address you print is a per-process fiction that the MMU translates to physical memory. Two processes can both hold address 0x601040 and be looking at entirely different physical bytes. Second, the regions have permissions enforced by hardware. A write to the text segment or a jump into a non-executable stack raises a fault, which the kernel usually turns into SIGSEGV.

A useful analogy: the address space is a warehouse. The text segment is the sealed blueprint cabinet — readable, never modified. Static storage is the permanent shelving, allocated when the warehouse opens and cleared when it closes. The stack is a stack of pallets by the door: last on, first off, and everything on it disappears when the shift ends. The heap is the open floor where you can claim any patch of any size, keep it as long as you like, and must remember to release it.

Modern systems also randomize the base addresses of these regions on every run (ASLR), so exact addresses are never reproducible and must never be hard-coded or compared for anything but equality with pointers from the same region.

Examples

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

int initialized_global = 42;      /* .data : value stored in the binary   */
int uninitialized_global;         /* .bss  : zero-filled by the loader    */
const char *literal = "hello";    /* pointer in .data, chars in .rodata   */

void f(void) { }                  /* code lives in .text                  */

int main(void)
{
    int local = 1;                        /* stack */
    static int function_static = 7;       /* .data, despite being in a function */
    void *heap = malloc(64);              /* heap  */

    /* %p expects void*; the cast is required for correctness, not style. */
    printf("text   (function f)   : %p\n", (void *)(size_t)f);
    printf("rodata (string lit)   : %p\n", (void *)literal);
    printf("data   (init global)  : %p\n", (void *)&initialized_global);
    printf("data   (func static)  : %p\n", (void *)&function_static);
    printf("bss    (uninit global): %p\n", (void *)&uninitialized_global);
    printf("heap   (malloc)       : %p\n", heap);
    printf("stack  (local)        : %p\n", (void *)&local);

    free(heap);
    return 0;
}

Typical output on x86-64 Linux (addresses vary every run because of ASLR):

text   (function f)   : 0x5591b4a0d169
rodata (string lit)   : 0x5591b4a0e004
data   (init global)  : 0x5591b4a10010
data   (func static)  : 0x5591b4a10014
bss    (uninit global): 0x5591b4a1001c
heap   (malloc)       : 0x5591b5c2f2a0     <- above the data segment
stack  (local)        : 0x7ffd3a4f1abc     <- far higher, separate region

        HIGH ADDRESSES
        +-------------------------------+
        | environment / argv strings    |
        +-------------------------------+
        | STACK                         |  one per thread
        |   main's frame                |
        |   caller's frame              |
        |   callee's frame              |
        |            |                  |
        |            v  grows DOWN      |
        +-------------------------------+
        |                               |
        |        (unmapped gap)         |  touching this = SIGSEGV
        |                               |
        +-------------------------------+
        |            ^  grows UP        |
        |            |                  |
        | HEAP  (malloc / free)         |
        +-------------------------------+
        | .bss   uninitialized globals  |  zero-filled, not in the file
        +-------------------------------+
        | .data  initialized globals    |  values come from the file
        +-------------------------------+
        | .rodata string literals, const|  READ-ONLY
        +-------------------------------+
        | .text  machine code           |  READ-ONLY + EXECUTABLE
        +-------------------------------+
        LOW ADDRESSES  (page 0 unmapped, which is why *NULL traps)

You can see the segments in a real binary without running it:

$ size ./a.out
   text    data     bss     dec     hex filename
   1867     620       8    2495     9bf a.out

Key Takeaways

• A process address space is divided into regions with distinct contents, permissions, and lifetimes: text, rodata, data, bss, heap, mapped files, and stack.
• Globals with non-zero initializers occupy .data and are stored in the executable; zero/uninitialized globals occupy .bss and cost no file space.
• The heap grows upward and is managed by you; each thread's stack grows downward and is managed automatically.
• Addresses are virtual and randomized per run — never hard-code them, and only compare pointers within the same object.
• Page zero is deliberately unmapped, which is why dereferencing NULL reliably faults instead of silently corrupting memory.

🧪 Practice

1. Write a program that prints the address of a global, a static local, a stack local, and a malloc result, and order them from lowest to highest.
2. Add a 10 MB uninitialized global array to a program, rebuild, and compare the on-disk size with the same array initialized to {1}. Explain the difference using size.
3. Recurse a function that prints the address of its own local variable, and determine the direction and per-frame size of stack growth.
4. Interview-style: "Two runs of the same program print different addresses for the same global. Is that a bug?" Hint: think about what layer maps virtual addresses, and what security feature deliberately perturbs the mapping.

Stack vs Heap

Theory

The two regions you actively allocate from are the stack and the heap, and choosing between them is one of the most consequential decisions in a C program. They differ in almost every dimension.

The stack is a contiguous region managed by a single register (the stack pointer). Entering a function subtracts from it to make a frame holding parameters, locals, saved registers, and the return address; returning adds it back. That is the entire allocation algorithm: one arithmetic instruction. It is therefore extremely fast, perfectly cache-friendly (the top of the stack is nearly always in L1), and impossible to leak — the frame is reclaimed by the return whether you planned it or not.

Its cost is rigidity. The lifetime of a stack object is exactly the enclosing block, no longer. The size is fixed at compile time (unless you use a VLA), and the total space is small and bounded — commonly 8 MB for the main thread on Linux and often just 512 KB to 1 MB for other threads. Overflow it and you get a fault, not an error code.

The heap is a general-purpose pool managed by library code (malloc and friends), which in turn asks the kernel for large chunks via brk or mmap. Allocation means searching bookkeeping structures for a suitable free block, splitting it, and updating metadata — dramatically more work than adjusting a register, and each block carries hidden overhead (typically 8–16 bytes of header plus rounding to a 16-byte boundary). In exchange you get what the stack cannot give: lifetime you control, sizes determined at run time, and capacity limited by system memory rather than by a fixed frame budget.

The decision rule that covers most real code:

Question	Stack	Heap
Size known at compile time?	required (or a small VLA)	not required
Size large (say > 100 KB)?	avoid — overflow risk	yes
Must outlive the creating function?	impossible	yes
Allocation cost	~1 instruction	tens to hundreds of instructions
Reclamation	automatic on return	manual free, or it leaks
Failure mode	crash on overflow	NULL return you can handle
Fragmentation	none	possible over long runs

The single most common beginner error in C follows directly from the stack's lifetime rule: returning a pointer to a local. The address stays numerically valid and the bytes may even look right for a while, but the frame is gone, and the next call reuses it.

Examples

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

/* WRONG: 'buf' dies when make_greeting_broken returns.
   The returned pointer refers to a frame that no longer exists. */
char *make_greeting_broken(const char *name)
{
    char buf[64];
    snprintf(buf, sizeof buf, "Hello, %s!", name);
    return buf;                    /* dangling: undefined behaviour */
}

/* RIGHT (option A): allocate on the heap; the CALLER frees. */
char *make_greeting_heap(const char *name)
{
    size_t n = strlen(name) + 9;   /* "Hello, " + name + "!" + NUL */
    char *s = malloc(n);
    if (!s) return NULL;
    snprintf(s, n, "Hello, %s!", name);
    return s;                      /* valid until the caller frees it */
}

/* RIGHT (option B): the caller supplies the buffer -- no allocation at all.
   This is the classic C idiom: it works with stack, heap or static memory. */
int make_greeting_into(char *dst, size_t cap, const char *name)
{
    int n = snprintf(dst, cap, "Hello, %s!", name);
    return (n >= 0 && (size_t)n < cap) ? 0 : -1;   /* -1 means truncated */
}

int main(void)
{
    char stack_buf[64];
    if (make_greeting_into(stack_buf, sizeof stack_buf, "Ada") == 0)
        puts(stack_buf);

    char *heap_str = make_greeting_heap("Grace");
    if (heap_str) {
        puts(heap_str);
        free(heap_str);            /* caller owns it, caller frees it */
    }
    return 0;
}

   A CALL IN PROGRESS
                                   HEAP
   STACK (grows down)              +--------------------------+
   +---------------------+         | header | "Hello, Grace!" |
   | main frame          |         +--------------------------+
   |   stack_buf[64] ....|              ^
   |   heap_str  --------+--------------+
   +---------------------+
   | make_greeting frame |   <- exists only while the call is active
   |   name, n, s        |      pop on return; reused by the NEXT call
   +---------------------+
   |         v           |
   |   (unallocated)     |

   Returning &stack_buf from a callee hands out an address in a frame
   that the next call will overwrite. Returning a heap pointer is fine:
   the block outlives every frame until someone calls free().

Key Takeaways

• Stack allocation is a register adjustment: fastest possible, automatically reclaimed, but lifetime-bound to the enclosing block and limited to a few megabytes.
• Heap allocation costs real work and per-block overhead, but gives run-time sizes, caller-controlled lifetime, and a recoverable NULL on failure.
• Prefer the stack for small, short-lived, fixed-size objects; use the heap when the object must outlive its creator, is large, or has a run-time size.
• Never return a pointer to a local object — the frame is reclaimed on return regardless of what the bytes still contain.
• The "caller supplies the buffer" idiom sidesteps the choice entirely and is the most reusable interface shape in C.

🧪 Practice

1. Write char *bad(void) returning a pointer to a local array; call it, then call an unrelated function, and print the buffer. Compile with -Wall and read the warning.
2. Benchmark one million 64-byte stack allocations against one million malloc/free pairs and report the ratio.
3. Write a recursive function with a 1 MB local array and find how many frames deep it gets before crashing. Compare with ulimit -s.
4. Interview-style: "When would you deliberately choose heap allocation for an object that easily fits on the stack?" Hint: think about lifetime, ownership transfer, and the size of the object relative to the thread's stack limit.

Static and Global Storage

Theory

Between the stack (too short-lived) and the heap (manually managed) sits a third storage duration: static. An object with static storage duration is created before main runs and destroyed after it returns — it exists for the entire execution of the program, at a fixed address, in .data or .bss.

Three declarations produce static storage:

1. A variable declared at file scope (a "global"), with or without static.
2. A variable inside a function declared static.
3. A variable declared static at file scope — same storage, but with internal linkage.

Note the keyword static does two unrelated jobs in C, which is a genuine wart worth stating plainly:

• Inside a function, static changes storage duration: the variable persists across calls instead of being recreated.
• At file scope, static changes linkage: the name becomes invisible to other translation units. The storage duration was already static.

Three rules make static storage predictable:

Zero initialization is guaranteed. Unlike automatic variables, a static object with no initializer is zero-initialized — every scalar to 0, every pointer to NULL, recursively through arrays and structs. This is free, done by the loader mapping a zeroed page.

Initializers must be constant expressions. static int x = 5; is fine; static int x = get_value(); is not, because the value has to be known at link time. (C++ allows dynamic initialization here; C does not.)

The address is fixed and stable for the whole run, which makes static objects safe to return pointers to — the one storage class where returning &local is legal.

Static locals are excellent for things like one-time initialization flags, call counters, and caches. They come with two serious caveats. They are not thread-safe: every thread shares the one object, so any mutation needs synchronization or _Thread_local (C11), which gives each thread its own copy. And they make functions non-reentrant, which is exactly why strtok cannot be used from two places at once and why strtok_r exists.

Also remember that static objects consume memory for the entire run. A 64 MB static buffer costs 64 MB from process start to exit, whether used or not.

Examples

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

int    g_initialized = 10;    /* .data, external linkage  */
int    g_zero;                /* .bss,  external linkage, guaranteed 0 */
static int g_private = 3;     /* .data, INTERNAL linkage: file-local */

/* A static local: one object shared by every call. */
int next_id(void)
{
    static int counter = 0;   /* initialized ONCE, before main() */
    return ++counter;         /* the value survives between calls */
}

/* Contrast: an automatic local is recreated (and here, re-initialized)
   on every call, so it can never accumulate anything. */
int broken_next_id(void)
{
    int counter = 0;
    return ++counter;         /* always 1 */
}

/* Legal to return: the array's lifetime is the whole program.
   NOT thread-safe and NOT reentrant -- a second call clobbers the first
   result while the caller may still be holding it. */
const char *month_name(int m)
{
    static const char *names[] = {
        "Jan","Feb","Mar","Apr","May","Jun",
        "Jul","Aug","Sep","Oct","Nov","Dec"
    };
    return (m >= 1 && m <= 12) ? names[m - 1] : "???";
}

/* One-time initialization guarded by a static flag (single-threaded only). */
static int *lookup_table(void)
{
    static int table[256];
    static int ready = 0;              /* zero-initialized for free */
    if (!ready) {
        for (int i = 0; i < 256; i++)
            table[i] = i * i;
        ready = 1;
    }
    return table;                      /* fixed address, always valid */
}

int main(void)
{
    printf("%d %d %d\n", next_id(), next_id(), next_id());   /* order unspecified! */
    printf("static local again: %d\n", next_id());
    printf("broken: %d %d\n", broken_next_id(), broken_next_id());
    printf("g_zero = %d (guaranteed zero)\n", g_zero);
    printf("month 3 = %s\n", month_name(3));
    printf("table[16] = %d\n", lookup_table()[16]);
    (void)g_private;
    return 0;
}

Note the deliberate trap in the first printf: the evaluation order of function arguments is unspecified, so three calls to a counter inside one call is exactly the kind of code that prints 3 2 1 on one compiler and 1 2 3 on another.

Declaration	Storage duration	Linkage	Initial value if omitted
int x; at file scope	static	external	zero
static int x; at file scope	static	internal	zero
int x; inside a function	automatic	none	indeterminate
static int x; inside a function	static	none	zero
_Thread_local static int x;	thread	none	zero, per thread

Key Takeaways

• Static storage duration means the object lives from before main to after it returns, at a fixed address.
• Static objects are zero-initialized by default and can only be initialized with constant expressions.
• static inside a function controls lifetime; static at file scope controls linkage — same keyword, different jobs.
• Returning a pointer to a static object is legal, but the object is shared, so the function is neither reentrant nor thread-safe.
• Use _Thread_local (C11) when each thread needs its own persistent copy.

🧪 Practice

1. Write a counter() function using a static local and call it five times; then remove static and explain the change in output.
2. Write const char *to_string(int n) that formats into a static buffer, then call it twice inside one printf and explain the result.
3. Declare a file-scope static variable in two .c files with the same name, link them, and confirm they are distinct objects. Then remove static and read the linker error.
4. Interview-style: "Why is strtok considered dangerous in modern code?" Hint: ask what it must remember between calls, and where that state can possibly live.

Text and Read-Only Data

Theory

Not all of your program's memory is writable, and the parts that are not exist for good reasons. Two regions are mapped read-only by the loader:

• .text — the compiled machine instructions. Read and execute, no write. Making code read-only prevents accidental self-modification and, combined with W^X ("write xor execute") policies, blocks a large class of attacks that inject code into a data buffer and jump to it.
• .rodata — read-only data: string literals, const objects the compiler can prove are never modified, jump tables generated for switch, and floating-point constants.

The single most consequential practical consequence is the nature of string literals. A literal like "hello" is an array object of type char[6] with static storage duration, typically placed in .rodata. Two things follow:

Modifying a string literal is undefined behaviour. On hosted systems with a read-only .rodata mapping it is a segmentation fault; on some embedded targets it silently succeeds and corrupts a shared constant. There is no diagnostic required.

Identical literals may be shared. The compiler is permitted (and usually configured) to store one copy of "hello" and point every occurrence at it, so pointer comparisons between literals have unspecified results.

This creates C's most infamous type trap:

char *p = "hello";        /* pointer to READ-ONLY memory; p[0]='H' is UB */
char  a[] = "hello";      /* a MUTABLE COPY on the stack; a[0]='H' is fine */

Both lines contain the same literal, but the second uses it as an initializer for a local array, which copies the six bytes into writable storage. In C the literal's type is char[] rather than const char[] for historical compatibility, so char *p = "hello"; compiles without complaint — this is why -Wwrite-strings exists and why disciplined code always writes const char *p = "hello";.

const itself deserves a precise statement: it is a promise you make to the compiler, not a hardware guarantee. A const local on the stack lives in writable memory and can be modified through a cast (undefined behaviour, but it will physically work). A const object with static storage duration and a constant initializer is typically placed in .rodata, where the hardware does enforce it. The distinction matters when reasoning about what will crash versus what will silently corrupt.

Examples

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

const int  g_const = 100;        /* likely .rodata: hardware-enforced   */
const char g_msg[] = "constant"; /* .rodata                             */

int main(void)
{
    char *mutable_ptr  = "literal";        /* points INTO .rodata      */
    const char *good   = "literal";        /* same bytes, honest type  */
    char  copy[]       = "literal";        /* a WRITABLE stack copy    */

    printf("literal via ptr : %s  at %p\n", mutable_ptr, (void *)mutable_ptr);
    printf("stack copy      : %s  at %p\n", copy, (void *)copy);

    copy[0] = 'L';                 /* fine: 'copy' is a stack array */
    printf("after write     : %s\n", copy);

    /* mutable_ptr[0] = 'L';          <- CRASH: writing to .rodata      */
    /* strcpy(mutable_ptr, "boom");   <- same crash, less obvious       */

    /* sizeof reveals the difference between the array and the pointer. */
    printf("sizeof(copy)=%zu  sizeof(mutable_ptr)=%zu\n",
           sizeof copy,            /* 8: the array, including the NUL   */
           sizeof mutable_ptr);    /* 8 on x86-64: just a pointer       */

    /* Identical literals MAY be merged into one object -- unspecified. */
    const char *a = "shared";
    const char *b = "shared";
    printf("a==b ? %s (unspecified either way)\n", a == b ? "yes" : "no");

    printf("%d %s\n", g_const, g_msg);
    (void)good;
    return 0;
}

   char *p    = "hello";                char a[] = "hello";

   STACK                                STACK
   +---------+                          +---------------------+
   | p  o----+---+                      | a: h e l l o \0     |  writable
   +---------+   |                      +---------------------+
                 |
   .rodata       v                      .rodata
   +---------------------+              +---------------------+
   | h e l l o \0        |  READ-ONLY   | h e l l o \0        | (template
   +---------------------+              +---------------------+  copied in
                                                                 at startup)
   p[0] = 'H';  -> SIGSEGV              a[0] = 'H';  -> fine

Two compiler flags turn this class of bug into a build error:

# Give string literals the type 'const char[]' so assigning to char* warns.
gcc -Wwrite-strings -Wall -Wextra prog.c
# prog.c: warning: initialization discards 'const' qualifier

# Belt and braces: make every warning fatal in CI.
gcc -Wwrite-strings -Werror prog.c

Key Takeaways

• .text (code) and .rodata (literals and constants) are mapped read-only; writing to them faults on hosted systems.
• A string literal is a static array in read-only memory — modifying it is undefined behaviour, and identical literals may be merged.
• char *p = "x"; points at read-only bytes; char a[] = "x"; copies them into writable storage. The difference is the entire bug.
• Always declare pointers to literals as const char *, and build with -Wwrite-strings to enforce it.
• const is a compile-time promise; only static-storage const objects are typically protected by the hardware.

🧪 Practice

1. Write char *p = "hello"; p[0] = 'H'; and run it. Then change to char p[] = "hello"; and confirm it works. Explain both.
2. Print sizeof for a string literal, a char[] initialized from one, and a char * pointing at one. Account for every number.
3. Compile a file that assigns a literal to a char * with -Wwrite-strings and fix every diagnostic it produces.
4. Interview-style: "Two const char * variables in the same file are both initialized from the literal "x". Must they compare equal?" Hint: ask what the standard requires versus what the compiler is allowed to merge.

Object Lifetime and Validity

Theory

Everything in this chapter reduces to one concept: lifetime. An object's lifetime is the portion of program execution during which storage is guaranteed to be reserved for it. Inside its lifetime the object has a stable address and a determinate value (once you write one). Outside it, any use of a pointer to it — reading, writing, comparing, even just copying the pointer value in some readings of the standard — is undefined behaviour.

C defines four storage durations, and lifetime follows directly from which one an object has:

Storage duration	Lifetime begins	Lifetime ends	Example
static	before main	after main returns	globals, static locals
thread	thread creation	thread exit	_Thread_local objects
automatic	entering the block	leaving the block	ordinary locals, parameters
allocated	successful malloc	matching free	heap blocks

The critical insight for beginners is that a pointer does not extend a lifetime. In a garbage-collected language, holding a reference keeps the object alive. In C, the pointer is nothing but a number; the object's lifetime is decided entirely by its storage duration, and the pointer becomes "indeterminate" the instant the lifetime ends. A pointer in that state is called dangling, and the language does not detect it for you.

Three subtleties trip up even experienced programmers:

Block scope is finer than function scope. An automatic object declared inside { ... } or a for body dies at the closing brace, not at the function's return. A pointer stashed outside that block dangles immediately.

Compound literals follow the scope they appear in. (struct point){1, 2} at block scope has automatic storage duration and dies at the end of that block; at file scope it has static duration. Returning a pointer to a block-scope compound literal is the same bug as returning &local.

realloc ends the old object's lifetime. If it moves the block, every pointer into the old block dangles — including pointers you stored inside other structures.

The discipline that makes this manageable is to think about lifetime and ownership together, and to write it down. Every function that returns a pointer should document, in one line, who is responsible for the object and until when. "Returns a pointer into an internal buffer, valid until the next call" and "returns a malloc'd block the caller must free" are radically different contracts, and most memory bugs in real codebases come from a caller guessing wrong.

Examples

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

struct point { int x, y; };

/* Lifetime demonstration: the inner block's object dies at its closing brace. */
void block_scope_trap(void)
{
    int *p;
    {
        int inner = 42;
        p = &inner;               /* legal here */
        printf("inside block : %d\n", *p);
    }                             /* 'inner' lifetime ENDS here */
    /* printf("%d", *p);             <- UB: p dangles, even though we are
                                         still inside the same function */
    (void)p;
}

/* Compound literals: storage duration follows the enclosing scope. */
struct point *bad_literal(void)
{
    return &(struct point){1, 2};   /* automatic: dies on return -- UB */
}

static struct point *ok_literal(void)
{
    static struct point sp = {1, 2};  /* static: valid forever */
    return &sp;
}

/* Documented contracts make lifetime a caller-visible part of the API. */

/* Returns a pointer to an internal buffer.
   VALID UNTIL: the next call to this function. Do not free. */
const char *shared_format(int n)
{
    static char buf[32];
    snprintf(buf, sizeof buf, "<%d>", n);
    return buf;
}

/* Returns a newly allocated string, or NULL on failure.
   OWNERSHIP: transferred to the caller, who must free() it. */
char *owned_format(int n)
{
    char *s = malloc(32);
    if (!s) return NULL;
    snprintf(s, 32, "<%d>", n);
    return s;
}

int main(void)
{
    block_scope_trap();

    /* The shared-buffer contract in action: the second call invalidates
       the first result, so this prints the SAME string twice. */
    const char *a = shared_format(1);
    const char *b = shared_format(2);
    printf("shared: a=%s b=%s   <- a was clobbered\n", a, b);

    char *o1 = owned_format(1);
    char *o2 = owned_format(2);
    if (o1 && o2) printf("owned : o1=%s o2=%s  <- independent\n", o1, o2);
    free(o1);
    free(o2);

    printf("ok_literal: (%d,%d)\n", ok_literal()->x, ok_literal()->y);
    return 0;
}

   LIFETIME TIMELINE for one call to f()

   program start ----------------------------------------------> exit
   |                                                              |
   |== static objects (globals, static locals) ===================|
   |                                                              |
              |== f's frame: locals, parameters ==|
                    |== inner block object ==|
              |
              |==== malloc'd block ============================>  |
                                              |
                                            free()  <- YOU decide

   A pointer captured at any point remains a valid *pointer* only while
   the bar underneath it is still drawn. Past its end, the pointer value
   itself is indeterminate -- not merely "pointing at old data".

Key Takeaways

• Lifetime, not scope and not pointer count, decides when an object's storage is guaranteed to exist.
• The four storage durations — static, thread, automatic, allocated — each fix a lifetime you cannot negotiate with, except for allocated storage, which you control via free.
• Holding a pointer never extends a lifetime; when the lifetime ends, the pointer is dangling and any use is undefined behaviour.
• Automatic lifetime ends at the enclosing block, not the function, and block-scope compound literals follow the same rule.
• Document ownership and validity in one line above every pointer-returning function; most memory bugs are contract misunderstandings.

🧪 Practice

1. Write a function that saves the address of a variable declared in an inner block into an outer pointer, then reads it after the block. Run it under AddressSanitizer with -fsanitize=address and read the report.
2. Write two functions returning const char *: one using a static buffer, one using malloc. Document each contract in a comment, then write a caller that misuses both and explain the symptom.
3. Take a struct holding a char *, copy it, free through one copy, and use the other. Name the exact lifetime rule that was broken.
4. Interview-style: "A function returns &(struct point){1,2}. Is that valid?" Hint: compound literals have a storage duration too — ask which scope it was written in.

<a id="72-dynamic-allocation"></a>

7.2 Dynamic Allocation

The heap is reached through four functions declared in <stdlib.h>: malloc, calloc, realloc, and free. This section covers each precisely, the failure handling they demand, and the two patterns — allocating structures and growing buffers — that account for most heap code you will ever write.

malloc and calloc

Theory

malloc(size) asks the allocator for a block of at least size contiguous bytes and returns a pointer to it, or NULL if it cannot. That is the whole contract, but four details in it matter enormously.

The contents are indeterminate. malloc does not clear the block. Whatever bytes the allocator last had there — often data from a previously freed allocation — are what you get. Reading them before writing is undefined behaviour, not merely "getting garbage", because the compiler is entitled to assume it never happens.

The block is suitably aligned for any object type. The returned pointer is guaranteed to satisfy the strictest fundamental alignment on the platform (16 bytes on x86-64), so you may store any type in it. For over-aligned types — SIMD vectors, cache-line-aligned structures — use C11's aligned_alloc(alignment, size) or POSIX posix_memalign.

The return type is void *, and you should not cast it. void * converts implicitly to any object pointer type in C. Adding a cast is not merely redundant; before C99 it could hide a missing <stdlib.h> include, causing the return value to be treated as int and truncated. (In C++ the cast is required, which is where the habit comes from.)

malloc(0) is implementation-defined: it may return NULL or a unique pointer you must still free. Do not rely on either — treat a zero-size request as a bug in your own logic.

calloc(count, size) differs in two ways, and both are reasons to prefer it in specific situations:

• It zero-initializes the whole block. Every byte is 0, which for integers means zero, and on every mainstream platform means NULL for pointers and 0.0 for IEEE floats — though the standard technically guarantees only the byte pattern.
• It checks the multiplication for overflow. malloc(n * sizeof(T)) can wrap around on a large n, producing a small allocation followed by an enormous overflow — a well-known exploit primitive. calloc(n, sizeof(T)) is required to detect the overflow and return NULL.

The zeroing is not always free: for large blocks the allocator typically gets fresh pages from the kernel that are already zeroed, making calloc effectively free; for small blocks it must memset. The overflow check, however, is always worth having.

The canonical safe allocation idiom uses sizeof *ptr rather than repeating the type name, so the size can never drift out of sync with the declaration:

T *p = malloc(n * sizeof *p);   /* not sizeof(T) -- immune to type changes */

Examples

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>   /* SIZE_MAX */

int main(void)
{
    /* --- malloc: uninitialized --------------------------------------- */
    int *a = malloc(5 * sizeof *a);      /* sizeof *a, not sizeof(int) */
    if (!a) { perror("malloc"); return EXIT_FAILURE; }

    /* Reading a[i] here would be UB. Write first. */
    for (int i = 0; i < 5; i++) a[i] = i * i;

    /* --- calloc: zeroed, with an overflow-checked size ---------------- */
    int *b = calloc(5, sizeof *b);       /* all five elements are 0 */
    if (!b) { perror("calloc"); free(a); return EXIT_FAILURE; }

    printf("malloc: ");
    for (int i = 0; i < 5; i++) printf("%d ", a[i]);
    printf("\ncalloc: ");
    for (int i = 0; i < 5; i++) printf("%d ", b[i]);   /* 0 0 0 0 0 */
    putchar('\n');

    /* --- why calloc's overflow check matters -------------------------- */
    size_t huge = SIZE_MAX / sizeof(int) + 2;
    int *danger = malloc(huge * sizeof(int));  /* the product WRAPS: tiny block */
    int *safe   = calloc(huge, sizeof(int));   /* detects overflow -> NULL     */
    printf("malloc(wrapped) = %p   calloc(checked) = %p\n",
           (void *)danger, (void *)safe);
    free(danger);

    /* --- over-aligned allocation (C11) -------------------------------- */
    /* size must be a multiple of the alignment. */
    void *aligned = aligned_alloc(64, 64 * 4);
    if (aligned) {
        printf("aligned_alloc(64,...) -> %p (%% 64 == %zu)\n",
               aligned, (size_t)aligned % 64);
        free(aligned);                    /* freed with plain free() */
    }

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

	malloc(n)	calloc(c, n)
Contents	indeterminate	all bytes zero
Overflow-checked size	no	yes
Cost for large blocks	cheap	usually as cheap (kernel pages arrive zeroed)
Cost for small blocks	cheap	extra memset
Use when	you overwrite the whole block immediately	you need zeros, or the size is a product

   WHAT malloc(24) ACTUALLY RESERVES

   returned pointer
        |
        v
   +----------+------------------------------+----------+
   | header   | your 24 usable bytes         | padding  |
   | (size,   |                              | to the   |
   |  flags)  |                              | next 16B |
   +----------+------------------------------+----------+
   ^                                                    ^
   |------------- the allocator's real chunk ----------- |

   The header sits BEHIND your pointer. Writing before p[0] or past
   p[23] corrupts allocator metadata, which is why heap overflows
   often crash later, inside free(), far from the real bug.

Key Takeaways

• malloc returns uninitialized memory suitably aligned for any type, or NULL on failure; reading before writing is undefined behaviour.
• calloc zero-fills and checks count * size for overflow — prefer it whenever the size is a product or zeros are wanted.
• Write malloc(n * sizeof *p), never sizeof(T), so the size follows the declaration automatically.
• Do not cast the result of malloc in C; the implicit void * conversion is correct and the cast can mask a missing header.
• Use aligned_alloc (C11) when you need alignment stricter than the fundamental one, and free it with ordinary free.

🧪 Practice

1. Allocate a 10-element int array with malloc and print it before writing; then do the same with calloc and compare. Run both under valgrind.
2. Rewrite int *p = (int *)malloc(10 * sizeof(int)); in the safest idiomatic form and list every improvement.
3. Write a function void *xmalloc_array(size_t count, size_t size) that detects multiplication overflow itself and returns NULL, then verify it against calloc.
4. Interview-style: "When is calloc(n, size) strictly better than malloc(n * size) plus memset?" Hint: think about arithmetic that can wrap, and about pages the kernel has already zeroed.

realloc Semantics

Theory

realloc(ptr, new_size) resizes an existing allocation. It is the most useful and the most misused function in the allocation API, because its behaviour depends on circumstances you cannot observe.

The contract: realloc returns a pointer to a block of new_size bytes whose contents are the same as the old block up to the smaller of the two sizes. To do that it may either grow the block in place (if free space happens to follow it) or allocate a new block, copy the data, and free the old one. You do not get to know which happened, and you must write code that is correct either way. That single rule generates all the others:

• The old pointer must be treated as invalid after a successful call. If the block moved, the old pointer dangles. Any other pointer into the old block — an interior pointer, a cached element address, a pointer stored in another structure — also dangles.

• On failure it returns NULL and leaves the original block untouched and still allocated. This is why the classic mistake

  p = realloc(p, n);   /* if this returns NULL, the old block is LEAKED */
  

  is a leak: you have overwritten the only pointer to a block that was not freed. Always assign to a temporary first.

• New bytes when growing are uninitialized, exactly like malloc.

• Two special cases fold the rest of the API into realloc: realloc(NULL, n) behaves as malloc(n), and realloc(p, 0) is, since C23, undefined behaviour — historically it freed the block and returned NULL or a unique pointer, so never use it as a way to free. Call free instead.

Performance deserves a warning. Growing a buffer by a constant amount — realloc(p, n + 1) in a loop — is quadratic, because most calls copy the entire buffer. Growth must be geometric: multiply the capacity (typically by 1.5 or 2) so that the amortized cost per element is constant. This is exactly what std::vector, Python lists, and Go slices do internally, and it is covered in detail under Growable Buffers.

Examples

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

int main(void)
{
    size_t cap = 4;
    int *a = malloc(cap * sizeof *a);
    if (!a) return EXIT_FAILURE;
    for (size_t i = 0; i < cap; i++) a[i] = (int)i;

    printf("before: ptr=%p cap=%zu\n", (void *)a, cap);

    /* CORRECT resize: assign to a temporary so a failure does not lose 'a'. */
    size_t new_cap = cap * 2;
    int *tmp = realloc(a, new_cap * sizeof *a);
    if (!tmp) {
        free(a);                 /* 'a' is still valid: clean up properly */
        return EXIT_FAILURE;
    }
    a = tmp;                     /* commit only after success */
    cap = new_cap;

    /* The new bytes are UNINITIALIZED -- fill them before reading. */
    for (size_t i = 4; i < cap; i++) a[i] = (int)i;

    printf("after : ptr=%p cap=%zu  (same address or not -- you cannot know)\n",
           (void *)a, cap);
    for (size_t i = 0; i < cap; i++) printf("%d ", a[i]);
    putchar('\n');

    /* THE INTERIOR-POINTER TRAP -------------------------------------- */
    int *third = &a[2];                    /* cached pointer into the block */
    tmp = realloc(a, cap * 4 * sizeof *a); /* may MOVE the block */
    if (tmp) {
        a = tmp;
        /* printf("%d", *third);   <- UB if the block moved: 'third'
                                      points into the freed old block. */
        third = &a[2];                     /* recompute AFTER every realloc */
        printf("recomputed third = %d\n", *third);
    }

    /* realloc(NULL, n) == malloc(n): lets one code path handle first use. */
    int *fresh = realloc(NULL, 8 * sizeof *fresh);
    free(fresh);

    free(a);
    return 0;
}

   CASE 1: grown IN PLACE (free space followed the block)

   before:  [ 0 1 2 3 ][ free space  ]
                 ^ a
   after:   [ 0 1 2 3 | ? ? ? ? ]
                 ^ a   (same address; old pointer still happens to work)

   CASE 2: MOVED (no room to grow)

   before:  [ 0 1 2 3 ][ other allocation ]
                 ^ a
   after:   [  freed  ][ other allocation ] ...... [ 0 1 2 3 | ? ? ? ? ]
                 ^ a (DANGLING)                         ^ returned pointer

   Your code cannot tell the two cases apart, so it must be written for
   CASE 2 always: reassign the pointer, and recompute every pointer that
   aimed into the old block.

Key Takeaways

• realloc may grow in place or move the block; correct code assumes it moved and uses only the returned pointer.
• Never write p = realloc(p, n) — a NULL return leaks the still-valid original. Use a temporary and commit on success.
• Every pointer into the old block, including interior and stored pointers, is invalidated by a successful realloc.
• Bytes added when growing are uninitialized; realloc(NULL, n) is malloc(n); realloc(p, 0) is not a way to free.
• Grow geometrically, not by a constant, or the total cost of building a buffer becomes quadratic.

🧪 Practice

1. Build an array by realloc-ing one element at a time to 100,000 elements, printing the pointer whenever it changes. Count the moves.
2. Time the previous loop against a doubling strategy for one million elements and report the ratio.
3. Write a resize helper int grow(int **buf, size_t *cap) that returns 0/-1 and never leaks on failure; use it in a loop.
4. Interview-style: "What is wrong with p = realloc(p, size);?" Hint: describe the state of the heap and of p in the failure branch.

free and Ownership

Theory

free(ptr) returns a block to the allocator. Its contract is short and unforgiving:

• The pointer must be exactly what a previous malloc, calloc, realloc, or aligned_alloc returned — not an interior pointer, not an adjusted one.
• Each block must be freed at most once. A second free is undefined behaviour and, on modern allocators, a classic exploitation primitive.
• free(NULL) is guaranteed to do nothing. This is a genuine convenience: cleanup paths never need if (p) guards.
• After free, the pointer's value is indeterminate. Using it is undefined behaviour; so, formally, is even reading it.

Notice what free does not do: it does not modify your pointer variable (it cannot, it receives a copy), it does not zero the memory, and it usually does not return anything to the operating system — the allocator keeps the block on a free list for reuse, which is why a process's resident size rarely shrinks after freeing.

The hard part of free is not the call, it is deciding who calls it. C has no destructors and no garbage collector, so ownership is a convention your code must express and your documentation must state. Three conventions cover nearly everything:

1. The allocator frees. The function that allocates also frees, and callers only borrow. Simple and safe, but limits the object's lifetime.
2. Ownership transfers to the caller. A "constructor" returns a pointer that the caller must eventually free — or, better, pass to a matching destructor.
3. A container owns its elements. The container's destroy function frees each element. Callers must not free elements they merely obtained a pointer to.

The practical discipline that makes this work is paired create/destroy functions. Instead of exposing malloc and free at the API boundary, expose thing_create and thing_destroy. The destroy function knows the internal structure, frees members in the right order, and can be extended later (adding a new heap member requires no change at any call site). Setting the pointer to NULL after freeing — often via a small macro or a destroy function taking Thing ** — turns a would-be use-after-free into a clean NULL dereference that crashes immediately at the real location.

Examples

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

typedef struct {
    char   *name;     /* owned: allocated separately */
    int    *scores;   /* owned */
    size_t  n;
} Student;

/* Constructor: returns ownership to the caller, or NULL on failure.
   Cleans up partial allocations so a failure never leaks. */
Student *student_create(const char *name, size_t n)
{
    Student *s = calloc(1, sizeof *s);      /* zeroed: members start NULL */
    if (!s) return NULL;

    s->name = malloc(strlen(name) + 1);
    if (!s->name) goto fail;                /* single cleanup path */
    strcpy(s->name, name);

    s->scores = calloc(n, sizeof *s->scores);
    if (!s->scores) goto fail;
    s->n = n;
    return s;

fail:
    free(s->name);                          /* free(NULL) is safe */
    free(s);
    return NULL;
}

/* Destructor: frees members first, then the struct. Takes Student**
   so it can NULL the caller's pointer -- no dangling pointer survives. */
void student_destroy(Student **sp)
{
    if (!sp || !*sp) return;
    free((*sp)->name);
    free((*sp)->scores);
    free(*sp);
    *sp = NULL;              /* the caller's variable is now safely NULL */
}

int main(void)
{
    Student *s = student_create("Ada", 3);
    if (!s) return EXIT_FAILURE;

    s->scores[0] = 95;
    printf("%s scored %d\n", s->name, s->scores[0]);

    student_destroy(&s);
    printf("after destroy, s = %p\n", (void *)s);   /* (nil) */

    student_destroy(&s);   /* idempotent: safe because s is NULL */

    /* free(NULL) is always a no-op -- cleanup code needs no guards. */
    char *never_allocated = NULL;
    free(never_allocated);
    return 0;
}

   OWNERSHIP OF A Student

   Student *s ---> +----------------+
                   | name   o-------+---> "Ada\0"       (owned block 2)
                   | scores o-------+---> [95][0][0]    (owned block 3)
                   | n = 3          |
                   +----------------+   (owned block 1)

   student_destroy must free 2 and 3 BEFORE 1 -- once block 1 is freed,
   the pointers to 2 and 3 are unreachable and the memory is leaked.
   Freeing "outside-in" is one of the most common leak patterns.

Key Takeaways

• free requires the exact pointer returned by the allocator, exactly once; free(NULL) is always a safe no-op.
• Freeing does not change your pointer variable, does not clear the memory, and usually does not return pages to the OS.
• Ownership is a convention, not a language feature — document for every pointer who frees it and when.
• Prefer paired x_create/x_destroy functions over raw malloc/free at API boundaries.
• Free inner members before the containing struct, and have destroy take a T ** so it can null the caller's pointer.

🧪 Practice

1. Implement create/destroy for a struct with two heap members and verify with valgrind --leak-check=full that nothing leaks.
2. Deliberately free the struct before its members, run under Valgrind, and interpret the "definitely lost" report.
3. Write a SAFE_FREE(p) macro that frees and nulls in one statement (use the do { } while (0) idiom from Chapter 8.3) and explain what it cannot protect against.
4. Interview-style: "After free(p), why is setting p = NULL recommended but not sufficient?" Hint: consider every other variable that may hold the same address.

Checking Allocation Failure

Theory

malloc can return NULL. The question is what your program should do about it, and the answer is genuinely different depending on the kind of program you are writing — which is why this deserves its own topic rather than a line of boilerplate.

First, when does allocation actually fail? Less often than you might think on Linux, which by default overcommits: the kernel grants address space optimistically and only allocates physical pages on first touch, so malloc succeeds and the process may later be killed by the OOM killer instead. But failure is entirely real when the request is huge or corrupted by an integer overflow, when a 32-bit process exhausts its 4 GB address space, when RLIMIT_AS or a container memory limit is in force, or on embedded systems with no virtual memory at all. Attacker-controlled sizes are the common thread in the security-relevant cases.

Second, what should happen on failure? Three strategies, each appropriate somewhere:

Strategy	Shape	Fits
Abort	check, print, exit(EXIT_FAILURE)	command-line tools, batch jobs
Propagate	return NULL/-1 up the call chain	libraries, reusable modules
Recover	free caches, retry, degrade	long-running servers, databases, embedded

Whichever you choose, the checking itself is non-negotiable, because an unchecked NULL does not stay a local problem: strcpy(NULL, s) or p->field = 1 on a null pointer is a crash at best and, when the offset is large enough to land on a mapped page, memory corruption at worst.

The pattern that keeps abort-style code readable is a small wrapper, conventionally named xmalloc, that never returns NULL. It removes the check from every call site while keeping the behaviour explicit in one place. For libraries the opposite discipline applies: never call exit from library code — return an error and let the application decide.

The genuinely difficult part is cleaning up correctly when a failure happens halfway through a multi-step construction. C's answer is the goto cleanup ladder: a single set of labels in reverse allocation order, each falling through to the next. It is one of the few places where goto is unambiguously the clearest tool, and it is standard practice throughout the Linux kernel.

Examples

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

/* Strategy 1: abort. Never returns NULL, so call sites stay clean.
   Appropriate for applications, NEVER for library code. */
void *xmalloc(size_t n)
{
    void *p = malloc(n);
    if (!p) {
        fprintf(stderr, "fatal: out of memory allocating %zu bytes\n", n);
        exit(EXIT_FAILURE);
    }
    return p;
}

/* Strategy 2: propagate, with a goto cleanup ladder.
   Labels appear in REVERSE allocation order and fall through. */
struct resource {
    char *buf_a;
    char *buf_b;
    FILE *fp;
};

int resource_init(struct resource *r, const char *path, size_t n)
{
    r->buf_a = NULL; r->buf_b = NULL; r->fp = NULL;

    r->buf_a = malloc(n);
    if (!r->buf_a) goto err;                 /* nothing acquired yet */

    r->buf_b = malloc(n);
    if (!r->buf_b) goto err_free_a;

    r->fp = fopen(path, "r");
    if (!r->fp) goto err_free_b;

    return 0;                                 /* success: keep everything */

err_free_b:
    free(r->buf_b);
    r->buf_b = NULL;
err_free_a:
    free(r->buf_a);
    r->buf_a = NULL;
err:
    return -1;                                /* caller decides what to do */
}

/* Strategy 3: recover -- shed a cache and retry once. */
static char *cache = NULL;

void *malloc_or_shrink(size_t n)
{
    void *p = malloc(n);
    if (!p && cache) {
        free(cache);                          /* release reclaimable memory */
        cache = NULL;
        p = malloc(n);                        /* one retry */
    }
    return p;                                 /* still may be NULL */
}

int main(void)
{
    char *s = xmalloc(32);
    strcpy(s, "checked at one place");
    puts(s);
    free(s);

    struct resource r;
    if (resource_init(&r, "/nonexistent", 128) != 0)
        fprintf(stderr, "init failed cleanly, nothing leaked\n");

    /* A request large enough to fail even with overcommit. */
    void *huge = malloc((size_t)-1 / 2);
    printf("huge malloc -> %s\n", huge ? "succeeded" : "NULL (as expected)");
    free(huge);
    return 0;
}

   THE goto CLEANUP LADDER

   acquire A ---> acquire B ---> acquire C ---> return 0 (success)
       |              |              |
       | fail         | fail         | fail
       v              v              v
      err        err_free_a     err_free_b
                      ^              |
                      +--------------+   (falls through, releasing
                      |                   resources newest-first)
                      v
                   return -1

   One exit path per acquisition point, each releasing exactly what was
   already acquired. Adding a fourth resource means adding one label,
   not editing four error branches.

Key Takeaways

• Always check the result of every allocation; an unchecked NULL becomes a crash or a corruption far from the real cause.
• Choose a strategy deliberately: abort in applications, propagate errors in libraries, recover in long-running or embedded systems.
• Library code must never call exit — return an error code and let the application decide.
• An xmalloc-style wrapper concentrates abort-on-failure logic in one place and keeps call sites readable.
• Use a goto cleanup ladder for multi-step initialization so partial failures release exactly what was acquired, in reverse order.

🧪 Practice

1. Write xmalloc and xcalloc, use them in a small program, and force failure with ulimit -v 10000 to see the message.
2. Write a function that allocates three buffers and opens a file, using a goto ladder, then verify with Valgrind that each failure point leaks nothing.
3. Wrap malloc with a version that fails randomly one time in ten, run your program repeatedly, and fix every crash it exposes.
4. Interview-style: "Why does malloc almost never return NULL on Linux even when memory is exhausted?" Hint: name the kernel policy involved and the process that cleans up afterwards.

Allocating Structs and Arrays

Theory

Two shapes account for most heap use: a single structure, and an array of elements. Both are straightforward once a few idioms are internalized.

A single struct. T *p = malloc(sizeof *p); allocates exactly one. Using sizeof *p rather than sizeof(T) means changing the declared type requires no edit here — a small habit that prevents a serious class of bug. If the struct has pointer members, calloc(1, sizeof *p) is often better, because it starts every member NULL, which makes a cleanup path safe even after a partial failure.

An array. T *a = malloc(n * sizeof *a); gives n contiguous elements you index normally: a[i]. This is exactly the layout of a real array, so pointer arithmetic, memcpy, and functions taking T * all work unchanged. Guard the multiplication: use calloc(n, sizeof *a) or check n <= SIZE_MAX / sizeof *a first.

Arrays of structs versus arrays of pointers. This is a genuine design decision:

	T *arr (array of structs)	T **arr (array of pointers)
Allocations	1	1 + n
Memory locality	excellent — one contiguous run	poor — each element elsewhere
Element size	must be uniform and known	may vary (polymorphism)
Moving/growing	copies whole elements	copies pointers only
Cleanup	one free	loop, then free the array

For plain data, the contiguous array wins decisively on performance. Arrays of pointers earn their keep when elements are large, must not move, or are of varying concrete types.

2D arrays have three usual encodings. The flat one — a single block of rows * cols with manual index arithmetic a[r * cols + c] — is one allocation, cache-friendly, and the one to reach for by default. The array-of-row-pointers gives a[r][c] syntax at the cost of rows + 1 allocations and an extra indirection per access. C99's pointer-to-VLA (int (*a)[cols] = malloc(rows * sizeof *a);) gives you both: one allocation and a[r][c] syntax, when the column count is a run-time value.

Finally, the flexible array member (C99) lets a struct end with an unsized array so that a header and its payload live in one allocation — one malloc, one free, and perfect locality. It is the idiomatic way to represent a variable-length record in modern C.

Examples

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

typedef struct { int x, y; } Point;

/* Flexible array member: header and payload in ONE allocation. */
typedef struct {
    size_t len;
    char   data[];       /* C99 FAM: must be last, has no size of its own */
} Buffer;

Buffer *buffer_create(size_t len)
{
    Buffer *b = malloc(sizeof *b + len);     /* header + payload together */
    if (!b) return NULL;
    b->len = len;
    memset(b->data, 0, len);
    return b;                                 /* one block -> one free() */
}

int main(void)
{
    /* --- one struct ---------------------------------------------------- */
    Point *p = malloc(sizeof *p);            /* sizeof *p, not sizeof(Point) */
    if (!p) return EXIT_FAILURE;
    *p = (Point){3, 4};
    printf("point (%d,%d)\n", p->x, p->y);
    free(p);

    /* --- contiguous array of structs (preferred for plain data) -------- */
    size_t n = 4;
    Point *arr = calloc(n, sizeof *arr);     /* overflow-checked product */
    if (!arr) return EXIT_FAILURE;
    for (size_t i = 0; i < n; i++) arr[i] = (Point){(int)i, (int)i * 2};
    printf("arr[2] = (%d,%d)  stride = %zu bytes\n",
           arr[2].x, arr[2].y, sizeof *arr);
    free(arr);                                /* ONE free for all elements */

    /* --- array of pointers: n+1 allocations, n+1 frees ---------------- */
    Point **parr = calloc(n, sizeof *parr);
    if (!parr) return EXIT_FAILURE;
    for (size_t i = 0; i < n; i++) {
        parr[i] = malloc(sizeof **parr);
        if (!parr[i]) break;
        *parr[i] = (Point){(int)i, 0};
    }
    for (size_t i = 0; i < n; i++) free(parr[i]);   /* elements first */
    free(parr);                                     /* then the array  */

    /* --- 2D, flat: one allocation, manual indexing -------------------- */
    size_t rows = 3, cols = 4;
    int *grid = calloc(rows * cols, sizeof *grid);
    if (!grid) return EXIT_FAILURE;
    grid[1 * cols + 2] = 99;                  /* row 1, column 2 */
    printf("grid[1][2] = %d\n", grid[1 * cols + 2]);
    free(grid);

    /* --- 2D via pointer-to-VLA (C99): one allocation AND a[r][c] ------ */
    int (*vla)[cols] = malloc(rows * sizeof *vla);
    if (vla) {
        vla[1][2] = 77;
        printf("vla[1][2]  = %d\n", vla[1][2]);
        free(vla);
    }

    /* --- flexible array member ---------------------------------------- */
    Buffer *b = buffer_create(16);
    if (b) {
        strcpy(b->data, "one allocation");
        printf("%s (len=%zu)\n", b->data, b->len);
        free(b);                              /* frees header and payload */
    }
    return 0;
}

   ARRAY OF STRUCTS                 ARRAY OF POINTERS

   arr -> [x y][x y][x y][x y]      parr -> [p0][p1][p2][p3]
          one contiguous block                |   |   |   |
          1 malloc, 1 free                    v   v   v   v
          sequential scan = 1 cache        [x y][x y] ... scattered
          line per few elements            5 mallocs, 5 frees
                                           a pointer chase per element

   FLEXIBLE ARRAY MEMBER

   Buffer *b -> +--------+---------------------------+
                | len    | data[len]                 |   ONE block
                +--------+---------------------------+
                sizeof *b        len bytes

Key Takeaways

• Use malloc(sizeof *p) for one object and calloc(n, sizeof *a) for n — both track the declaration and the latter checks the product.
• A contiguous array of structs beats an array of pointers for plain data: fewer allocations, one free, far better locality.
• Flat 2D arrays with a[r * cols + c] are the safe default; pointer-to-VLA gives a[r][c] syntax with a single allocation.
• With arrays of pointers, free the elements before the array itself, or the element blocks become unreachable.
• A flexible array member packs a header and a variable-length payload into one allocation with one matching free.

🧪 Practice

1. Allocate an array of 1000 Point structs and an array of 1000 Point *, fill both, and compare the total number of malloc calls and the time to sum all x values.
2. Implement a 2D matrix three ways (flat, row pointers, pointer-to-VLA) with matching create/destroy functions, and verify all three with Valgrind.
3. Write a Packet struct with a flexible array member holding a payload, plus create/destroy functions, and confirm one allocation per packet.
4. Interview-style: "You need one million small records that are scanned repeatedly. Array of structs or array of pointers?" Hint: count allocations, then count cache lines touched per pass.

Growable Buffers

Theory

The dynamic array — a buffer that grows as you append — is the most useful data structure in C and the one every C programmer eventually writes. Getting it right teaches the whole allocation API at once.

The structure holds three things: a pointer to the elements, the number of elements in use (len), and the number of elements the block can hold (cap). The invariant len <= cap is what makes appending cheap: most appends just write at data[len++], and only when len == cap does the buffer grow.

Why growth must be geometric. Suppose you grow by one element each time. Appending n elements performs n reallocations, and each one may copy the entire buffer, giving 1 + 2 + ... + n = O(n^2) element copies. Now suppose you double: growth happens only at capacities 1, 2, 4, 8, ..., and the total copying is 1 + 2 + 4 + ... + n < 2n — linear overall, so amortized O(1) per append. The difference for a million appends is roughly a trillion operations versus two million.

The growth factor is a real trade-off. Doubling wastes up to 50% of the allocated space in the worst case but reallocates rarely. A factor of 1.5 wastes less and has a theoretical advantage: the sum of previous blocks can eventually exceed the next request, letting the allocator reuse freed space, which doubling never allows. Most C code uses 2 for simplicity; cap = cap + cap / 2 is the 1.5 version.

Three details separate a toy implementation from a correct one:

• Overflow. cap * 2 * sizeof(T) can wrap on 32-bit systems or with an attacker-controlled length. Check before multiplying.
• Failure safety. A failed realloc must leave the vector exactly as it was — same pointer, same length, same capacity — so the caller can handle the error and keep using it.
• Pointer invalidation. Every append can move the buffer, so any pointer or index-derived pointer obtained before an append may dangle afterwards. Indices survive reallocation; pointers do not. This is the same rule that makes C++ iterator invalidation famous, and it is why storing indices is often the better design.

When you know the final size in advance, calling a reserve function once eliminates all intermediate reallocation and copying — the single cheapest optimization available for this structure.

Examples

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>   /* SIZE_MAX */

typedef struct {
    int    *data;
    size_t  len;      /* elements in use          */
    size_t  cap;      /* elements the block holds */
} Vec;

/* Ensure room for at least 'want' elements. Returns 0 on success, -1 on
   failure WITHOUT disturbing the existing contents. */
static int vec_reserve(Vec *v, size_t want)
{
    if (want <= v->cap) return 0;

    size_t new_cap = v->cap ? v->cap : 4;
    while (new_cap < want) {
        /* Overflow guards BEFORE the arithmetic that could wrap. */
        if (new_cap > SIZE_MAX / 2) return -1;
        new_cap *= 2;                                  /* geometric growth */
    }
    if (new_cap > SIZE_MAX / sizeof *v->data) return -1;

    int *tmp = realloc(v->data, new_cap * sizeof *v->data);
    if (!tmp) return -1;          /* v is untouched: still perfectly usable */

    v->data = tmp;                /* commit only after success */
    v->cap  = new_cap;
    return 0;
}

static int vec_push(Vec *v, int value)
{
    if (vec_reserve(v, v->len + 1) != 0) return -1;
    v->data[v->len++] = value;
    return 0;
}

static void vec_free(Vec *v)
{
    free(v->data);
    v->data = NULL;               /* leave the struct in a reusable state */
    v->len = v->cap = 0;
}

int main(void)
{
    Vec v = {0};                  /* NULL, 0, 0 -- realloc(NULL,n) == malloc */
    size_t last_cap = 0;

    for (int i = 0; i < 20; i++) {
        if (vec_push(&v, i * i) != 0) { vec_free(&v); return EXIT_FAILURE; }
        if (v.cap != last_cap) {                 /* observe the growth curve */
            printf("len=%2zu grew to cap=%2zu at %p\n", v.len, v.cap, (void *)v.data);
            last_cap = v.cap;
        }
    }

    printf("contents:");
    for (size_t i = 0; i < v.len; i++) printf(" %d", v.data[i]);
    putchar('\n');

    /* THE INVALIDATION RULE: indices survive growth, pointers do not. */
    int *third_ptr = &v.data[2];
    size_t third_idx = 2;
    vec_push(&v, 999);                   /* may move the whole block */
    /* printf("%d", *third_ptr);            <- UB if the block moved */
    printf("by index (always safe): %d\n", v.data[third_idx]);
    (void)third_ptr;

    /* Knowing the size up front removes every intermediate copy. */
    Vec big = {0};
    if (vec_reserve(&big, 1000000) == 0) {
        for (int i = 0; i < 1000000; i++) big.data[big.len++] = i;
        printf("filled %zu elements with ONE allocation\n", big.len);
    }
    vec_free(&big);
    vec_free(&v);
    return 0;
}

   DOUBLING: total copies stay linear

   cap:  4        8            16                  32
        [....]  [........]   [................]  [...............]
   copy:  -       4            8                  16          = 28 copies
                                                                for 32 pushes

   GROWING BY ONE: total copies are quadratic

   cap:  1  2  3  4  5 ... 32
   copy: 0 +1 +2 +3 +4 ... +31                                = 496 copies
                                                                for 32 pushes

   At 1,000,000 pushes the gap is ~2 million versus ~500 billion copies.

Key Takeaways

• A growable buffer is data + len + cap with the invariant len <= cap; only a full buffer triggers a reallocation.
• Growth must be geometric (typically 1.5x or 2x) for amortized O(1) appends; growing by a constant is quadratic.
• Check capacity arithmetic for overflow before multiplying, especially when the length is attacker-influenced.
• On realloc failure, leave the structure untouched so the caller can recover; commit the new pointer only after success.
• Any append may move the buffer: store indices rather than pointers, and call reserve up front when the size is known.

🧪 Practice

1. Implement Vec with push, pop, get, and free, printing the capacity every time it changes for 100 pushes.
2. Add a growth-factor parameter and measure total time and peak memory for 1.5x versus 2x over ten million appends.
3. Make vec_push fail on the tenth call (via a fake allocator) and prove with assertions that len, cap, and the contents are unchanged.
4. Interview-style: "Why do dynamic arrays double instead of growing by a fixed amount?" Hint: total the copies for both strategies over n appends and compare the growth rates.

<a id="73-memory-errors"></a>

7.3 Memory Errors

Memory bugs are C's defining hazard: they are easy to write, often symptom-free for a long time, and responsible for the majority of serious security vulnerabilities in C code. This section catalogues the six classic errors, shows what each looks like, and pairs every one with the tool that finds it automatically.

Memory Leaks

Theory

A memory leak is allocated memory that is no longer reachable but has not been freed. The block stays reserved for the process's whole lifetime because nothing holds its address any more, so nothing can ever free it.

Leaks are the mildest memory bug in the sense that they do not corrupt anything — a leaking program produces correct output. That mildness is also why they are dangerous: a short-lived program's leaks are invisible (the OS reclaims everything at exit), so leaky habits go unnoticed until the same code runs inside a server that serves requests for weeks. There the leak becomes memory exhaustion, then swapping, then an OOM kill.

The recurring causes are worth memorizing, because they are recognizable patterns rather than random mistakes:

• Overwriting the only pointer. p = malloc(...) twice without an intervening free.
• p = realloc(p, n) on failure, discussed earlier: the original block is still allocated and its address is gone.
• Early returns. A function with one malloc and four return statements typically frees on only one of them. This is the leak the goto cleanup ladder exists to eliminate.
• Losing a container's contents. Freeing an array of pointers without freeing the elements; freeing a struct before its heap members; forgetting to walk a linked list.
• Error paths nobody tests. The success path is exercised constantly and the failure path almost never, so that is where leaks accumulate.

A related and more insidious problem is the logical leak: memory that is still reachable but will never be used again — an unbounded cache, a list of completed jobs nobody removes, an event log that only grows. Leak detectors report nothing because the pointers are live. Only monitoring resident memory over time reveals it.

Detection is fully automated and you should never hunt for a leak by reading code first. Valgrind's Memcheck reports leaks with the allocating stack trace, and LeakSanitizer (bundled with AddressSanitizer) does the same much faster.

Examples

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

/* LEAK 1: the only pointer to the first block is overwritten. */
void leak_overwrite(void)
{
    char *p = malloc(100);
    p = malloc(200);          /* the 100-byte block is now unreachable */
    free(p);                  /* frees only the second */
}

/* LEAK 2: an early return skips the cleanup. */
int leak_early_return(int n)
{
    int *buf = malloc(n * sizeof *buf);
    if (!buf) return -1;
    if (n > 100) return -2;   /* LEAK: 'buf' is never freed on this path */
    free(buf);
    return 0;
}

/* FIXED: one exit path, cleanup guaranteed. */
int no_leak(int n)
{
    int rc = 0;
    int *buf = malloc(n * sizeof *buf);
    if (!buf) return -1;
    if (n > 100) { rc = -2; goto out; }
    /* ... work ... */
out:
    free(buf);
    return rc;
}

/* LEAK 3: freeing the container but not its contents. */
void leak_container(void)
{
    char **rows = malloc(3 * sizeof *rows);
    for (int i = 0; i < 3; i++) {
        rows[i] = malloc(32);
        snprintf(rows[i], 32, "row %d", i);
    }
    free(rows);               /* the three 32-byte blocks are lost */
}

/* FIXED: elements first, container second. */
void no_leak_container(void)
{
    char **rows = malloc(3 * sizeof *rows);
    if (!rows) return;
    for (int i = 0; i < 3; i++) rows[i] = malloc(32);
    for (int i = 0; i < 3; i++) free(rows[i]);   /* inside-out */
    free(rows);
}

int main(void)
{
    leak_overwrite();
    leak_early_return(200);
    leak_container();
    no_leak(200);
    no_leak_container();
    return 0;
}

Finding them takes one command:

$ gcc -g -O0 leaks.c -o leaks
$ valgrind --leak-check=full --show-leak-kinds=all ./leaks
==12345== HEAP SUMMARY:
==12345==     in use at exit: 996 bytes in 5 blocks
==12345== 100 bytes in 1 blocks are definitely lost in loss record 1 of 3
==12345==    at 0x4C2FB0F: malloc (vg_replace_malloc.c:299)
==12345==    by 0x40064B: leak_overwrite (leaks.c:7)      <- exact line
==12345==    by 0x4006F2: main (leaks.c:56)

# Faster alternative, built into the compiler:
$ gcc -g -fsanitize=address leaks.c -o leaks && ./leaks
# ==12345==ERROR: LeakSanitizer: detected memory leaks

Valgrind category	Meaning
definitely lost	no pointer to the block exists — a real leak, fix it
indirectly lost	reachable only from a definitely-lost block (e.g. list nodes)
possibly lost	only an interior pointer remains — usually a real leak
still reachable	a pointer exists at exit; not a leak, but often untidy

Key Takeaways

• A leak is unreachable allocated memory; it never corrupts data, which is exactly why it survives testing and kills long-running processes.
• The usual causes are overwritten pointers, untested early-return paths, and containers freed without their contents.
• Free inside-out: elements before the container, members before the struct.
• Logical leaks (reachable but never reused, such as unbounded caches) are invisible to leak detectors — watch resident memory over time.
• Run valgrind --leak-check=full or build with -fsanitize=address routinely; never hunt leaks by reading code first.

🧪 Practice

1. Write a program with three distinct leaks and find all of them with Valgrind, mapping each report to its source line.
2. Refactor a function with four return statements and two allocations into a single-exit goto ladder, and prove with Valgrind that no path leaks.
3. Build a linked list of 1000 nodes, free only the head, and explain the "indirectly lost" figure in the report.
4. Interview-style: "A server's memory grows steadily but the leak checker reports nothing. What is happening?" Hint: distinguish unreachable memory from memory that is reachable but never used again.

Dangling Pointers and Use-After-Free

Theory

A dangling pointer holds the address of an object whose lifetime has ended. Dereferencing one is a use-after-free (or use-after-scope for stack objects), and it is among the most severe bugs in C — severe because of how it behaves, not just because it is wrong.

The behaviour is what makes it dangerous. Freed memory is not erased and not unmapped; the allocator keeps it on a free list for reuse. So a use-after-free typically:

1. Works perfectly at first. The bytes are still there. Tests pass.
2. Starts returning wrong data once that block is handed out to a different allocation and overwritten.
3. Corrupts unrelated state if you write through the dangling pointer, damaging whatever now owns those bytes — including allocator metadata.

The symptom therefore appears far away in space and time from the cause, which is why these bugs consume days of debugging. In security terms, an attacker who can control which allocation reuses the freed block ("heap grooming") can turn a use-after-free into arbitrary code execution; this class is behind a large share of browser and kernel exploits.

Dangling pointers arise in five recognizable ways:

• Using a pointer after free.
• Keeping a second copy of a pointer and freeing through the first (aliasing).
• Returning or storing the address of a local variable.
• Using an interior pointer after realloc moved the block.
• Holding a pointer to an element of a container that was resized or destroyed.

The defences are layered. Null after free — ideally through a destroy function taking T ** — converts a silent use-after-free into an immediate, obvious NULL dereference at the correct location. It does not help with aliases, which is why the second defence is single, documented ownership: one owner per object, and borrowers that never outlive the owner. The third is tooling: AddressSanitizer quarantines freed blocks and poisons them so any access reports instantly, with both the allocation and the free stack traces.

Examples

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

int main(void)
{
    /* --- classic use-after-free --------------------------------------- */
    char *p = malloc(32);
    strcpy(p, "still here");
    free(p);
    /* printf("%s\n", p);      <- UB. Often prints correctly, which is the
                                  worst possible outcome: it hides the bug. */

    /* The block gets reused, and the "old" data silently changes. */
    char *q = malloc(32);           /* very likely the SAME address as p */
    strcpy(q, "different data");
    printf("p == q ? %s\n", (void *)p == (void *)q ? "yes -- reused" : "no");

    /* --- the aliasing trap: nulling one copy does not help ------------ */
    char *owner = malloc(16);
    char *alias = owner;            /* second pointer to the same block   */
    free(owner);
    owner = NULL;                   /* only THIS variable is now safe     */
    /* alias[0] = 'x';                 <- still dangling: UB              */
    (void)alias;

    /* --- use-after-scope ---------------------------------------------- */
    int *dangler;
    {
        int local = 5;
        dangler = &local;
    }                               /* 'local' lifetime ends here */
    /* printf("%d\n", *dangler);      <- UB; the slot is reused by the
                                         next call made from this frame */
    (void)dangler;

    free(q);
    return 0;
}

A destroy function that nulls the caller's pointer removes the most common case entirely:

void thing_destroy(Thing **t)
{
    if (!t || !*t) return;
    free((*t)->buf);
    free(*t);
    *t = NULL;              /* the caller's variable cannot dangle */
}

$ gcc -g -fsanitize=address uaf.c -o uaf && ./uaf
==4242==ERROR: AddressSanitizer: heap-use-after-free on address 0x602000000010
READ of size 1 at 0x602000000010 thread T0
    #0 0x4f2a1b in main uaf.c:12                <- where you used it
0x602000000010 is located 0 bytes inside of 32-byte region
freed by thread T0 here:
    #1 0x4f29c4 in main uaf.c:11                <- where you freed it
previously allocated by thread T0 here:
    #2 0x4f2986 in main uaf.c:9                 <- where you allocated it

Three stack traces in one report — use, free, and allocation — is why AddressSanitizer turns a multi-day hunt into a two-minute fix.

   TIMELINE OF A USE-AFTER-FREE

   malloc -> [ "still here" ]      p valid
                  ^ p
   free   -> [ "still here" ]      p DANGLING (bytes unchanged: the trap)
                  ^ p                          allocator owns the block
   malloc -> [ "different data" ]  p aliases someone else's object
                  ^ p ^ q
   *p = 'X' -> corrupts q's object, and the crash appears in q's code,
               possibly minutes later, with no trace of the real culprit.

Key Takeaways

• A dangling pointer refers to an object whose lifetime has ended; using it is undefined behaviour with delayed, misleading symptoms.
• Freed memory keeps its contents until reused, so a use-after-free often appears to work — the most dangerous failure mode there is.
• Writing through a dangling pointer corrupts whatever now owns the block, including allocator metadata, and is a prime exploitation target.
• Null the pointer after freeing, preferably inside a destroy function taking T **; note this does not protect aliases.
• AddressSanitizer reports use, free, and allocation stack traces together — make it your default debug build.

🧪 Practice

1. Free a buffer, allocate another the same size, and show that the first pointer now aliases the second allocation.
2. Write a destroy(T **) function that nulls the caller's pointer, then demonstrate an alias it still cannot protect.
3. Build the same program with and without -fsanitize=address and compare what each run reports.
4. Interview-style: "Why is use-after-free considered more dangerous than a memory leak?" Hint: compare what each one does to data owned by other parts of the program.

Double Free

Theory

A double free calls free twice on the same block. It is undefined behaviour, and unlike a leak it attacks the allocator itself.

Understanding why requires knowing a little about how allocators work. When you free a block, the allocator writes bookkeeping into the block's own memory — typically linking it into a free list by storing pointers in the first bytes of the now-unused space. Freeing a second time links an already-linked block again, producing a corrupted or cyclic free list. The consequences range from an immediate abort (glibc detects many cases and prints double free or corruption), to a later crash inside an innocent malloc, to the allocator handing out the same block to two different callers — which is a use-after-free by construction, and a classic route to arbitrary code execution.

The causes are almost always structural rather than careless:

• Two owners. Two data structures each believe they own the same object, and both clean up.
• Aliased pointers. free(a); free(b); where a == b.
• Error paths that free, followed by a caller that also frees. A function that frees on failure and returns an error, whose caller then frees its copy too.
• Retry loops that call cleanup twice.
• Shallow struct copies where both copies' destructors free the same inner pointer.

The defences follow directly:

Null after free, again via a destroy function that takes T **. free(NULL) is a guaranteed no-op, so a second call becomes harmless. This handles the "same variable freed twice" case completely.

Define ownership precisely. For every heap object, exactly one owner is responsible for freeing it, and that fact belongs in a comment on the type. Aliases are borrows and must never free.

Make error-path ownership explicit. State in the documentation whether a function frees its argument on failure. "On error, this function takes ownership and frees the buffer" is a legitimate contract, and so is "on error, the caller retains ownership" — but the caller has to know which.

For structs whose members are heap pointers, remember that assignment copies shallowly: after b = a;, two structs point at the same buffers, and destroying both is a double free. Either write a deep-copy function or make the type non-copyable by convention.

Examples

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

typedef struct { char *name; } Item;

/* Safe destroy: idempotent because free(NULL) is a no-op. */
static void item_destroy(Item **ip)
{
    if (!ip || !*ip) return;
    free((*ip)->name);
    (*ip)->name = NULL;
    free(*ip);
    *ip = NULL;
}

static Item *item_create(const char *name)
{
    Item *i = calloc(1, sizeof *i);
    if (!i) return NULL;
    i->name = malloc(strlen(name) + 1);
    if (!i->name) { free(i); return NULL; }
    strcpy(i->name, name);
    return i;
}

int main(void)
{
    /* --- the direct form --------------------------------------------- */
    char *p = malloc(16);
    free(p);
    /* free(p);            <- DOUBLE FREE: glibc aborts, ASan reports */
    p = NULL;
    free(p);               /* harmless: free(NULL) does nothing */

    /* --- the aliasing form: harder to see ---------------------------- */
    char *a = malloc(16);
    char *b = a;           /* an alias, not a copy of the data */
    free(a);
    /* free(b);            <- SAME BLOCK: double free */
    a = b = NULL;

    /* --- the shallow-copy form: hardest to see ----------------------- */
    Item *x = item_create("shared");
    if (x) {
        Item y = *x;              /* shallow copy: y.name aliases x->name */
        /* free(y.name);             <- would double-free with item_destroy */
        (void)y;
        item_destroy(&x);         /* frees name and struct exactly once */
        item_destroy(&x);         /* idempotent: x is NULL, nothing happens */
    }
    return 0;
}

   WHAT THE ALLOCATOR SEES

   free(p) once:      free list: HEAD -> [p] -> [older] -> NULL
   free(p) again:     free list: HEAD -> [p] -> [p] -> ...  (cycle!)

   Later:  q1 = malloc(16);   -> returns p
           q2 = malloc(16);   -> returns p AGAIN
           Two "independent" objects now share one block; writing q1
           silently rewrites q2. This is the primitive attackers use.

Detection is immediate with either tool:

$ ./prog
free(): double free detected in tcache 2       # glibc's own check
Aborted (core dumped)

$ gcc -g -fsanitize=address prog.c -o prog && ./prog
==777==ERROR: AddressSanitizer: attempting double-free on 0x602000000010
    #0 free
    #1 main prog.c:14              <- the second free
freed by thread T0 here:
    #1 main prog.c:12              <- the first free

Key Takeaways

• Freeing the same block twice corrupts allocator metadata and can cause the same block to be handed to two callers.
• The realistic causes are ambiguous ownership, aliased pointers, error paths that free, and shallow struct copies.
• Null the pointer after freeing so a repeat call becomes a no-op — free(NULL) is always safe.
• Assign exactly one owner per heap object and document whether a function takes ownership on failure.
• glibc detects many double frees at run time; AddressSanitizer reports both free sites precisely.

🧪 Practice

1. Trigger a double free deliberately and compare the plain glibc message with the AddressSanitizer report.
2. Write a struct with a heap member, copy it by assignment, and destroy both copies. Explain the failure and then implement a deep copy.
3. Design an API where a function takes ownership of its argument on failure; document the contract and write a caller that respects it.
4. Interview-style: "Why can a double free lead to code execution, while a leak cannot?" Hint: think about what the allocator stores inside freed blocks and what it does with that data later.

Buffer Overflows

Theory

A buffer overflow writes (or reads) outside the bounds of an object. C performs no bounds checking — a[i] compiles to "add i * sizeof(T) to the base address and access it", with no validation whatsoever — so the language will happily let you scribble over whatever follows your array.

What gets damaged depends on where the buffer lives:

• Stack overflow — the frame contains locals, the saved frame pointer, and the return address. Overwriting the return address redirects execution when the function returns, which is the original "smashing the stack" attack. Compilers now insert stack canaries (-fstack-protector-strong), which detect the corruption at return time and abort.
• Heap overflow — the bytes after your block are another allocation or the allocator's chunk header. Corrupting a header typically produces a crash inside a later, unrelated malloc or free, hiding the real cause.
• Global overflow — damages neighbouring globals, usually producing baffling action-at-a-distance bugs.

The recurring sources are a short list, and nearly all of them are string functions:

Dangerous	Why	Safer choice
gets(buf)	no length parameter at all	fgets(buf, sizeof buf, stdin)
strcpy(d, s)	copies until NUL, whatever the size	snprintf, or a bounded copy
strcat(d, s)	appends without checking room	snprintf with an explicit length
sprintf(buf, ...)	output length is unbounded	snprintf(buf, sizeof buf, ...)
scanf("%s", buf)	unbounded field	scanf("%31s", buf) or fgets

gets was removed from the language in C11 — that is how bad it is.

Off-by-one errors deserve special mention because they are so easy to make: for (i = 0; i <= n; i++) writes one element past the end, and forgetting the NUL terminator's byte makes char buf[N] hold only N - 1 characters. A one-byte overflow is not a minor overflow; on the stack it can overwrite the least significant byte of a saved pointer, and on the heap it can flip an allocator flag bit.

Two habits prevent most of this. First, always compute the size from the object: sizeof buf for arrays (never for pointers, where it gives the pointer size), and carry an explicit length alongside every pointer parameter. Second, prefer snprintf for all string building — it bounds the output, always NUL-terminates (given a non-zero size), and returns the length it would have written, which lets you detect truncation.

Examples

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

/* UNSAFE: no bound at all. The caller's input decides how far we write. */
void unsafe_copy(const char *input)
{
    char buf[16];
    strcpy(buf, input);            /* overflows for input longer than 15 */
    printf("%s\n", buf);
}

/* SAFE: bounded, always terminated, and truncation is detectable. */
int safe_copy(const char *input)
{
    char buf[16];
    int n = snprintf(buf, sizeof buf, "%s", input);
    if (n < 0 || (size_t)n >= sizeof buf) {
        fprintf(stderr, "input truncated (%d chars needed)\n", n);
        return -1;
    }
    printf("%s\n", buf);
    return 0;
}

/* The classic off-by-one: <= instead of <. */
void off_by_one(void)
{
    int a[5];
    for (int i = 0; i <= 5; i++)   /* writes a[5]: one past the end */
        a[i] = i;
}

/* sizeof does NOT work through a pointer -- a very common overflow cause. */
void sizeof_trap(char *heap_buf)
{
    printf("sizeof(pointer) = %zu  <- the POINTER, not the buffer\n",
           sizeof heap_buf);       /* 8 on x86-64, regardless of the size */
    /* memset(heap_buf, 0, sizeof heap_buf);  would clear only 8 bytes */
}

/* Correct heap-buffer handling: carry the length with the pointer. */
typedef struct { char *data; size_t cap; } Buf;

int buf_append(Buf *b, size_t used, const char *s)
{
    size_t need = strlen(s);
    if (used + need + 1 > b->cap) return -1;   /* explicit bounds check */
    memcpy(b->data + used, s, need + 1);
    return 0;
}

int main(void)
{
    safe_copy("short");
    safe_copy("a string that is definitely longer than fifteen characters");

    /* unsafe_copy("a string that is definitely longer than fifteen chars"); */
    (void)unsafe_copy;

    char *h = malloc(64);
    if (h) { sizeof_trap(h); free(h); }
    off_by_one();
    return 0;
}

   STACK FRAME BEING OVERFLOWED BY strcpy(buf, long_input)

   low addresses
   +-----------------+
   | buf[0..15]      | <- the write starts here
   +-----------------+
   | other locals    | <- clobbered next
   +-----------------+
   | saved rbp       | <- clobbered
   +-----------------+
   | canary (with    | <- -fstack-protector-strong puts a random value
   |  -fstack-prot.) |    here; a mismatch at return aborts the program
   +-----------------+
   | RETURN ADDRESS  | <- clobbering this hijacks control flow
   +-----------------+
   high addresses     (writes proceed toward higher addresses)

# Catch overflows at run time, on the stack, heap and globals:
$ gcc -g -fsanitize=address -fno-omit-frame-pointer prog.c -o prog && ./prog
# ==999==ERROR: AddressSanitizer: stack-buffer-overflow ... WRITE of size 1

# Cheap production hardening (no ASan required):
$ gcc -O2 -D_FORTIFY_SOURCE=3 -fstack-protector-strong -Wall -Wextra prog.c
# _FORTIFY_SOURCE turns many str*/mem* calls into length-checked variants

Key Takeaways

• C never checks bounds; an out-of-range index simply computes an address and accesses it.
• Stack overflows can overwrite the return address; heap overflows corrupt allocator metadata and crash elsewhere later.
• Replace gets, strcpy, strcat, and sprintf with fgets and snprintf, and always check snprintf's return value for truncation.
• sizeof gives the object size only for arrays — through a pointer it gives the pointer's size, which is a classic overflow cause.
• Build debug with -fsanitize=address and release with -D_FORTIFY_SOURCE=3 -fstack-protector-strong.

🧪 Practice

1. Write a 16-byte stack buffer, strcpy a 40-character string into it, and run it under AddressSanitizer. Then rewrite with snprintf.
2. Write a loop with <= over a 5-element array and find it with both -fsanitize=address and valgrind.
3. Write a function taking char *buf that uses sizeof buf for its bound; show the bug, then fix the signature to take an explicit length.
4. Interview-style: "What does a stack canary protect against, and what does it not?" Hint: consider the order of writes and which corruptions happen before the function returns.

Uninitialized Reads

Theory

An automatic (stack) variable with no initializer holds an indeterminate value: whatever bytes were left in that memory by earlier code. Likewise, malloc returns uninitialized bytes. Reading either before writing is undefined behaviour.

It is worth being precise about why this is worse than "you get a random number". The standard says such values are indeterminate, which — for objects that could be trap representations, and for anything the compiler can prove is uninitialized — allows the compiler to assume the read never happens. Real optimizers act on this: they may propagate contradictory assumptions, delete a branch that depends on the uninitialized value, or produce different values for two reads of the same variable. Treating it as "just garbage that varies" underestimates the risk.

Practically, the symptoms are what make it maddening. Uninitialized stack memory often contains the leftovers of the previous call, so a variable can be reliably 0 in a debug build (fresh stack pages arrive zeroed from the kernel) and reliably wrong in a release build, or work until you add an unrelated function call before it. This is the archetypal "works in debug, fails in release" bug.

Uninitialized memory is also a security problem independent of correctness: if a struct with padding or an unfilled buffer is written to a file, socket, or log, previously freed data — passwords, keys, other users' data — leaks out. The Heartbleed vulnerability was, in essence, a large uninitialized-and-overread buffer being sent to a remote peer.

Prevention is easy and cheap:

• Initialize at declaration. int count = 0;, char *p = NULL;, struct config c = {0};. Declaring variables at first use (C99) makes this natural, because you usually know the value by then.
• Use calloc when a heap block should start zeroed, or memset immediately after malloc.
• Do not forget struct padding. struct s x = {0}; zeroes every member, but padding bytes remain indeterminate. Use memset(&x, 0, sizeof x) before serializing a struct byte-for-byte.
• Turn on the warnings: -Wall -Wextra enables -Wmaybe-uninitialized, which catches many cases at compile time (though not all — the analysis is necessarily incomplete).
• Use MemorySanitizer (-fsanitize=memory, Clang) or Valgrind, which track initialization at the bit level and report the exact read.

Examples

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

/* UB: 'sum' starts with whatever was in that stack slot. */
int broken_sum(const int *a, size_t n)
{
    int sum;                       /* indeterminate */
    for (size_t i = 0; i < n; i++)
        sum += a[i];               /* reads an indeterminate value */
    return sum;
}

int fixed_sum(const int *a, size_t n)
{
    int sum = 0;                   /* one character fixes it */
    for (size_t i = 0; i < n; i++)
        sum += a[i];
    return sum;
}

/* A function that leaves stack garbage for the NEXT call to inherit. */
static void dirty_the_stack(void)
{
    volatile int junk[32];
    for (int i = 0; i < 32; i++) junk[i] = 0xDEADBEEF;
}

static void observe_garbage(void)
{
    int uninitialized[4];          /* same stack region as junk[] above */
    printf("leftover values: %d %d\n", uninitialized[0], uninitialized[1]);
}

/* Padding is NOT covered by {0} -- relevant whenever bytes leave the process. */
struct record {
    char  tag;      /* 1 byte  */
    /* 3 padding bytes here */
    int   value;    /* 4 bytes */
};

int main(void)
{
    int data[] = {1, 2, 3, 4};
    printf("fixed_sum  = %d\n", fixed_sum(data, 4));
    printf("broken_sum = %d (indeterminate; may differ per build)\n",
           broken_sum(data, 4));

    dirty_the_stack();
    observe_garbage();             /* often prints 0xDEADBEEF as -559038737 */

    /* malloc gives indeterminate bytes; calloc gives zeros. */
    int *m = malloc(4 * sizeof *m);
    int *c = calloc(4, sizeof *c);
    if (m && c) printf("malloc[0]=%d (garbage)  calloc[0]=%d\n", m[0], c[0]);
    free(m); free(c);

    /* Member-wise zeroing leaves padding indeterminate. */
    struct record r1 = {0};                 /* members zeroed, padding not */
    struct record r2;
    memset(&r2, 0, sizeof r2);              /* every BYTE zeroed */
    r1.tag = r2.tag = 'A';
    printf("use memset before writing a struct to a file or socket\n");
    return 0;
}

$ valgrind ./prog
==7777== Conditional jump or move depends on uninitialised value(s)
==7777==    at 0x40067A: broken_sum (prog.c:8)
==7777==  Uninitialised value was created by a stack allocation
==7777==    at 0x400666: broken_sum (prog.c:6)     <- the declaration

$ clang -g -fsanitize=memory prog.c -o prog && ./prog
# ==8888==WARNING: MemorySanitizer: use-of-uninitialized-value

Key Takeaways

• Automatic variables and malloc'd memory start indeterminate; reading before writing is undefined behaviour, not merely unpredictable.
• Optimizers exploit the undefinedness, so symptoms differ between debug and release builds — the classic "works with -O0" bug.
• Initialize at declaration, use calloc for zeroed heap memory, and declare variables at first use.
• struct s x = {0}; zeroes members but not padding — memset before serializing a struct to a file or the network.
• Enable -Wall -Wextra for compile-time detection, and use Valgrind or MemorySanitizer for the cases static analysis cannot see.

🧪 Practice

1. Write broken_sum and run it under -O0 and -O2; report both results and explain why they may differ.
2. Write a function that fills a large local array, return, then call another function with an uninitialized local array of the same size and print it.
3. Serialize a struct with padding using fwrite twice — once after {0} and once after memset — and compare the bytes with xxd.
4. Interview-style: "Why can reading an uninitialized variable be worse than reading a random value?" Hint: consider what the optimizer is permitted to assume about code paths that would be undefined.

Alignment and Aliasing Violations

Theory

Two rules constrain how you may reinterpret memory in C. Both are invisible in ordinary code and both bite hard in low-level code that casts pointers.

Alignment. Every type has an alignment requirement: an int typically must sit at an address divisible by 4, a double by 8. malloc always returns memory suitably aligned for any fundamental type, so ordinary heap use is safe. Trouble comes from reinterpreting a pointer: taking a char * at an arbitrary offset into a buffer and casting it to int *. On x86 the unaligned access usually works (a little slower); on ARMv7, SPARC, and many microcontrollers it raises a bus error; and even on x86 the cast itself is undefined behaviour, so the compiler may transform the code in ways that break it — for example by using an SSE instruction that does require alignment. The portable fix is memcpy, which has no alignment requirement and which every modern compiler turns into a single unaligned load when the target permits.

Strict aliasing. The compiler is allowed to assume that two pointers of incompatible types never refer to the same object. That assumption is what lets it keep a value in a register across a store through an unrelated pointer — a significant optimization. Violating it (writing through a float * and reading through an int *, say) makes the compiler's assumption false, and the generated code can silently ignore your write. The exceptions the standard grants are worth memorizing:

• A character type (char, unsigned char, signed char) may alias anything. This is why memcpy and byte-level inspection are always legal.
• Types that differ only in signedness or qualifiers may alias.
• A union member access is the sanctioned way to reinterpret bytes: writing one member and reading another is well-defined in C (unlike C++), though the result depends on representation.

The practical rules that follow are short: use memcpy to reinterpret bytes, use a union when you want an explicit, named reinterpretation, and reserve -fno-strict-aliasing for legacy code you cannot fix. C11's _Alignof and alignas let you query and request alignment explicitly, and aligned_alloc gives over-aligned heap blocks when SIMD or cache-line separation demands them.

Examples

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stdalign.h>    /* alignas, alignof (C11) */

/* WRONG: violates strict aliasing AND may be misaligned.
   Compiled with -O2, the read may not observe the write at all. */
float bad_bit_cast(uint32_t bits)
{
    return *(float *)&bits;         /* type-punning through a cast */
}

/* RIGHT: memcpy has no alignment or aliasing constraints, and every
   modern compiler optimizes this to a single register move. */
float good_bit_cast(uint32_t bits)
{
    float f;
    memcpy(&f, &bits, sizeof f);
    return f;
}

/* Also right, and self-documenting: a union member access. */
float union_bit_cast(uint32_t bits)
{
    union { uint32_t u; float f; } conv;   /* both members, one storage */
    conv.u = bits;
    return conv.f;                          /* well-defined in C */
}

/* Parsing a byte stream: NEVER cast the cursor to a wider pointer type. */
int parse_be32(const unsigned char *p, size_t len, uint32_t *out)
{
    if (len < 4) return -1;
    /* Portable, alignment-free, endian-explicit. */
    *out = (uint32_t)p[0] << 24 | (uint32_t)p[1] << 16
         | (uint32_t)p[2] <<  8 | (uint32_t)p[3];
    return 0;
}

int main(void)
{
    printf("alignof(char)=%zu int=%zu double=%zu\n",
           alignof(char), alignof(int), alignof(double));

    printf("good  = %f\n", good_bit_cast(0x40490FDBu));   /* ~3.14159 */
    printf("union = %f\n", union_bit_cast(0x40490FDBu));
    (void)bad_bit_cast;

    /* Unaligned access via a cast: undefined, and a bus error on ARM. */
    unsigned char raw[16] = {0};
    /* int *bad = (int *)(raw + 1);  *bad = 42;   <- UB */
    int value = 42;
    memcpy(raw + 1, &value, sizeof value);        /* always correct */
    int back;
    memcpy(&back, raw + 1, sizeof back);
    printf("round-tripped through an unaligned offset: %d\n", back);

    uint32_t n;
    unsigned char stream[] = {0x00, 0x00, 0x01, 0x00};
    if (parse_be32(stream, sizeof stream, &n) == 0)
        printf("parsed big-endian value = %u\n", n);

    /* Over-aligned allocation for SIMD or cache-line isolation. */
    alignas(64) static int cache_line_isolated[16];
    void *simd = aligned_alloc(32, 32 * 8);
    printf("static alignas(64) at %% 64 == %zu\n",
           (size_t)(void *)cache_line_isolated % 64);
    free(simd);
    return 0;
}

   ALIGNMENT

   ok:   addr 0x1000  [ int ][ int ][ int ]      0x1000 % 4 == 0
   bad:  addr 0x1001  [  i n t  ] spans two 4-byte units
                       ^ cast to int* is UB; bus error on strict CPUs

   STRICT ALIASING: what the optimizer is allowed to do

     void f(int *i, float *g) {
         *i = 1;            // compiler: 'g' cannot alias 'i' (different types)
         *g = 2.0f;         // so it may keep *i == 1 in a register
         return *i;         // and return 1 WITHOUT reloading from memory
     }

   If you actually passed the same address for both, the returned 1 is
   "wrong" -- but your program was already undefined.

Key Takeaways

• Casting a pointer to a stricter-aligned type is undefined behaviour, works by luck on x86, and faults on many other architectures.
• Strict aliasing lets the compiler assume incompatible pointer types never overlap; violating it can make stores vanish under optimization.
• Character types may alias anything, which is why memcpy and byte-wise inspection are always legal.
• Use memcpy for type punning (compilers optimize it away) or a union member access; avoid *(T *)&x casts entirely.
• Use alignof/alignas and aligned_alloc when you need explicit or over-strict alignment, and parse byte streams byte by byte.

🧪 Practice

1. Print alignof for char, short, int, double, and a struct containing all of them, and explain each value.
2. Write both bad_bit_cast and good_bit_cast, compile at -O2 with -Wstrict-aliasing=2, and compare the generated assembly with -S.
3. Parse a 4-byte big-endian integer out of an unaligned offset in a byte array using shifts, and again using memcpy, and verify both give the same result.
4. Interview-style: "Why is *(float *)&some_int unsafe even when the sizes match?" Hint: name the two separate rules it can break, and describe what the optimizer is permitted to assume about each.

<a id="74-allocation-strategies"></a>

7.4 Allocation Strategies

Calling malloc for every object is correct but rarely optimal. This section covers the strategies experienced C programmers use instead: arenas and pools that make deallocation trivial, stack allocation of run-time sizes, pluggable allocator interfaces, reference counting for shared ownership, and the fragmentation problem that motivates most of it.

Arena and Pool Allocators

Theory

General-purpose malloc solves a hard problem: arbitrary sizes, arbitrary lifetimes, arbitrary order of release. That generality costs bookkeeping on every call. Most programs do not need it, because their allocations fall into patterns — and two custom allocators exploit those patterns to be both dramatically faster and far harder to leak.

Arena (region, bump) allocator. The insight is that many allocations share a lifetime: everything created while parsing one request, compiling one function, or rendering one frame dies together. So allocate one large block up front and satisfy each request by advancing an offset — a single addition and a bounds check. There is no per-allocation header, no free list, and no free at all: you release the entire arena in one operation when the phase ends.

The consequences are striking. Allocation is a handful of instructions. Allocations are contiguous, so traversing them is cache-perfect. Individual objects cannot be leaked, because nothing is individually owned. And the whole class of double-free and use-after-free-of-one-object bugs disappears — replaced, honestly, by a new one: using a pointer after the arena is reset.

Pool (free-list, slab) allocator. The other common pattern is many objects of one size with individual lifetimes — list nodes, particles, connection records. Carve a block into fixed-size slots and thread the free ones onto a singly linked list, storing each next pointer inside the free slot itself (it is unused space, so the list costs zero extra memory). Allocation pops the head; freeing pushes it back. Both are O(1) with a couple of instructions, there is no size arithmetic, no fragmentation is possible (every slot is interchangeable), and objects can be freed in any order.

	malloc/free	Arena	Pool
Sizes	any	any	one fixed size
Free granularity	per object	whole arena at once	per object
Alloc cost	tens of instructions	~3 instructions	~3 instructions
Per-object overhead	8–16 bytes	0 (plus padding)	0
Fragmentation	possible	none	none
Typical use	general code	request/frame/parse phases	many same-size nodes

Both need care with alignment: a bump allocator must round the offset up to the required alignment, or it will hand out addresses that break double or SIMD accesses. Rounding to alignof(max_align_t) is the simple, always-correct choice.

Examples

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stddef.h>     /* max_align_t */
#include <stdalign.h>   /* alignof (C11) */

/* ---------------- Arena: bump-pointer allocation ------------------- */
typedef struct {
    unsigned char *base;
    size_t         cap;
    size_t         used;
} Arena;

static int arena_init(Arena *a, size_t cap)
{
    a->base = malloc(cap);
    if (!a->base) return -1;
    a->cap = cap;
    a->used = 0;
    return 0;
}

/* Round 'n' up to the next multiple of 'align' (a power of two). */
static size_t align_up(size_t n, size_t align)
{
    return (n + align - 1) & ~(align - 1);
}

static void *arena_alloc(Arena *a, size_t size)
{
    size_t offset = align_up(a->used, alignof(max_align_t));  /* never skip */
    if (offset > a->cap || size > a->cap - offset) return NULL;  /* overflow-safe */
    void *p = a->base + offset;
    a->used = offset + size;          /* the entire allocation algorithm */
    return p;
}

static void arena_reset(Arena *a) { a->used = 0; }   /* frees EVERYTHING */
static void arena_free(Arena *a)  { free(a->base); a->base = NULL; a->cap = a->used = 0; }

/* ---------------- Pool: fixed-size free list ------------------------ */
typedef struct PoolNode { struct PoolNode *next; } PoolNode;

typedef struct {
    unsigned char *block;
    PoolNode      *free_list;
    size_t         slot;      /* bytes per slot */
} Pool;

static int pool_init(Pool *p, size_t slot_size, size_t count)
{
    /* Each slot must be able to hold a 'next' pointer while free. */
    p->slot = align_up(slot_size < sizeof(PoolNode) ? sizeof(PoolNode) : slot_size,
                       alignof(max_align_t));
    p->block = malloc(p->slot * count);
    if (!p->block) return -1;

    p->free_list = NULL;
    for (size_t i = count; i-- > 0; ) {          /* thread every slot on */
        PoolNode *n = (PoolNode *)(p->block + i * p->slot);
        n->next = p->free_list;
        p->free_list = n;
    }
    return 0;
}

static void *pool_alloc(Pool *p)
{
    PoolNode *n = p->free_list;
    if (!n) return NULL;                 /* pool exhausted */
    p->free_list = n->next;              /* pop the head: O(1) */
    return n;
}

static void pool_free(Pool *p, void *ptr)
{
    PoolNode *n = ptr;
    n->next = p->free_list;              /* push onto the head: O(1) */
    p->free_list = n;
}

static void pool_destroy(Pool *p) { free(p->block); p->block = NULL; p->free_list = NULL; }

/* ---------------- Using them --------------------------------------- */
typedef struct { int id; double score; } Record;

int main(void)
{
    /* Arena: everything created for one "request" dies together. */
    Arena a;
    if (arena_init(&a, 64 * 1024) != 0) return EXIT_FAILURE;

    for (int request = 0; request < 3; request++) {
        char   *name = arena_alloc(&a, 32);
        Record *r    = arena_alloc(&a, sizeof *r);
        if (!name || !r) break;
        snprintf(name, 32, "request-%d", request);
        *r = (Record){request, request * 1.5};
        printf("%s -> id=%d score=%.1f  (arena used %zu bytes)\n",
               name, r->id, r->score, a.used);
        arena_reset(&a);          /* one instruction frees BOTH allocations */
    }
    arena_free(&a);

    /* Pool: many same-size objects with individual lifetimes. */
    Pool pool;
    if (pool_init(&pool, sizeof(Record), 100) != 0) return EXIT_FAILURE;

    Record *rs[5];
    for (int i = 0; i < 5; i++) {
        rs[i] = pool_alloc(&pool);
        *rs[i] = (Record){i, i * 0.5};
    }
    pool_free(&pool, rs[2]);                 /* out-of-order free is fine */
    Record *reused = pool_alloc(&pool);      /* gets slot 2 straight back */
    printf("pool reused the freed slot: %s\n", reused == rs[2] ? "yes" : "no");
    pool_destroy(&pool);
    return 0;
}

   ARENA                              POOL

   base                               block
   |                                  |
   [name][rec][name][rec][ free  ]    [ A ][ B ][ C ][ D ][ E ]
                    ^ used             free_list -> C -> E -> NULL
   alloc: used += size                          (next pointers live
   reset: used  = 0   (frees all)                INSIDE the free slots)

   No per-object header, no free list.  alloc: pop head.  free: push head.
   Cannot free one object.             Any order, no fragmentation.

Key Takeaways

• An arena allocates by bumping an offset and frees everything at once — ideal when many objects share one lifetime (a request, a frame, a parse).
• A pool serves fixed-size slots from a free list threaded through the free slots themselves: O(1) allocate and free, zero overhead, no fragmentation.
• Both eliminate per-object headers and dramatically outperform malloc for their patterns, while removing whole classes of leak and double-free bugs.
• The new failure mode is lifetime confusion: a pointer used after arena_reset is a use-after-free with no allocator to detect it.
• Always align the bump offset (to alignof(max_align_t) if in doubt) and size pool slots to hold at least a next pointer.

🧪 Practice

1. Implement the arena above and benchmark 100,000 small allocations against 100,000 malloc calls; report the ratio and the peak memory.
2. Extend the arena with a "checkpoint/rollback" API (size_t arena_mark(Arena*), void arena_release(Arena*, size_t)) and use it for nested scopes.
3. Add an assertion to pool_free that the pointer lies within the pool block and on a slot boundary, then test it with a deliberately bad pointer.
4. Interview-style: "When would you choose an arena over malloc, and what do you give up?" Hint: describe the lifetime pattern that makes it a win, and the bug class it introduces.

Stack Allocation with alloca

Theory

alloca(size) allocates memory on the stack — in the current function's frame — and it is automatically released when the function returns. It is not standard C (it comes from <alloca.h> on glibc, <malloc.h> on Windows), but it appears often enough in real code to need understanding.

The appeal is genuine: allocation is a single stack-pointer adjustment, there is no free to forget, and no leak is possible even on an early return or a longjmp. For a run-time-sized scratch buffer in a hot function, it is the fastest thing available.

The problems are equally genuine, and they are why most style guides ban it:

• There is no failure indication. If the size exceeds the remaining stack, you do not get NULL; you get stack overflow — a crash, or worse, a silently corrupted frame. Since the available stack depends on call depth, the same alloca may work in one caller and crash in another.
• A size derived from input is a vulnerability. alloca(user_supplied_length) lets an attacker move the stack pointer arbitrarily.
• The lifetime is the whole function, not the block. alloca inside a loop accumulates until the function returns — a loop of alloca calls is effectively a stack leak.
• It does not compose. alloca in a function argument list has unspecified behaviour on some compilers, and it interacts badly with inlining and with setjmp/longjmp.

C99's variable-length arrays (VLAs) provide the same capability with better semantics: int buf[n]; has block scope (so a loop reclaims each iteration), respects normal array typing, and works with sizeof. They inherit the fatal flaw — no failure mode when n is large — which is why VLAs became optional in C11 and why the Linux kernel removed them entirely. The __STDC_NO_VLA__ macro tells you whether an implementation supports them.

The sound rule: use a fixed-size stack buffer for the common small case and fall back to malloc above a threshold. This gives you the speed of the stack for typical inputs and the safety of the heap for outliers, with a bounded, auditable worst case.

Examples

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifndef _WIN32
#  include <alloca.h>
#endif

/* DANGEROUS: no failure path. A large 'n' overflows the stack and crashes,
   and 'n' derived from untrusted input is a security hole. */
void risky(size_t n)
{
    char *buf = alloca(n);        /* no NULL check is possible */
    memset(buf, 0, n);
    /* released automatically when the function returns */
}

/* VLA: same speed, better scoping -- but the same missing failure mode. */
void vla_version(size_t n)
{
#ifndef __STDC_NO_VLA__
    char buf[n];                  /* block scope: reclaimed at the brace */
    memset(buf, 0, n);
    printf("VLA of %zu bytes, sizeof works: %zu\n", n, sizeof buf);
#else
    (void)n;
#endif
}

/* THE RECOMMENDED PATTERN: small-size optimization with a heap fallback.
   Fast and allocation-free for the common case, safe for any size. */
#define STACK_THRESHOLD 256

int process(const char *input, size_t len)
{
    char  stack_buf[STACK_THRESHOLD];
    char *buf   = stack_buf;
    char *owned = NULL;                       /* non-NULL only if we malloc'd */

    if (len + 1 > sizeof stack_buf) {
        owned = malloc(len + 1);
        if (!owned) return -1;                /* a real, checkable failure */
        buf = owned;
    }

    memcpy(buf, input, len);
    buf[len] = '\0';
    printf("processed %zu bytes using the %s\n",
           len, owned ? "heap" : "stack");

    free(owned);                              /* free(NULL) is a no-op */
    return 0;
}

int main(void)
{
    risky(64);
    vla_version(10);

    char small[100], big[1000];
    memset(small, 'a', sizeof small);
    memset(big,   'b', sizeof big);
    process(small, sizeof small);   /* stack path */
    process(big,   sizeof big);     /* heap path  */
    return 0;
}

	alloca	VLA	fixed buffer + heap fallback
Standard	no	C99, optional since C11	yes
Failure detectable	no	no	yes (NULL)
Lifetime	whole function	enclosing block	explicit
sizeof works	no	yes	yes
Safe with untrusted sizes	no	no	yes

Key Takeaways

• alloca allocates in the current stack frame and is freed on return: extremely fast, but non-standard and with no way to detect failure.
• Its lifetime is the whole function, so alloca in a loop accumulates until return.
• VLAs give the same capability with proper block scope and typing, but share the fatal lack of a failure path and are optional since C11.
• Never size either from untrusted input — it is a direct route to stack overflow.
• Prefer a fixed-size stack buffer for the common case with a malloc fallback above a threshold: fast, safe, and standard.

🧪 Practice

1. Write a function using alloca in a loop and print the stack pointer each iteration to show the accumulation.
2. Implement the threshold pattern with a 128-byte buffer and verify with Valgrind that the heap path never leaks, including on the error return.
3. Compile a VLA-using program with -Wvla and with -std=c11 -Wall, and explain each diagnostic.
4. Interview-style: "Why do the Linux kernel and many style guides ban VLAs and alloca?" Hint: consider what happens when the size is large and what the code can do about it.

Custom Allocator Interfaces

Theory

Once you have more than one allocation strategy, the next step is to stop hard-coding which one your data structures use. A custom allocator interface lets a module allocate through a caller-supplied policy: the heap in production, an arena in a request handler, a pool in an embedded system, and an instrumented allocator in tests.

The idiomatic C shape is a struct of function pointers plus an opaque context:

typedef struct {
    void *(*alloc)(void *ctx, size_t size);
    void *(*realloc)(void *ctx, void *ptr, size_t size);
    void  (*free)(void *ctx, void *ptr);
    void  *ctx;                 /* the arena, pool, or NULL for malloc */
} Allocator;

The ctx pointer is what makes this work: it carries the allocator's state, so the same function-pointer signature serves a stateless malloc wrapper and a stateful arena. This is the same pattern as qsort's comparison function, SQLite's sqlite3_mem_methods, and Zig's std.mem.Allocator — and it is the standard way to express polymorphism in C.

Three design points are worth getting right the first time:

Take the allocator by parameter, not by global. A global "current allocator" seems convenient but breaks under threading and nesting. Structures that allocate should store the allocator they were created with, so their destroy function releases through the same one.

Decide the failure convention once. Either every alloc may return NULL and every caller checks, or the interface guarantees non-NULL and aborts. Mixing the two is where bugs live.

Keep it minimal. Three functions cover essentially everything. Adding calloc, alignment parameters, or size-passing free (which lets pool allocators skip a lookup) is a real design choice, not an automatic improvement.

The immediate payoff beyond flexibility is testability. A wrapper allocator that counts live allocations turns "does this function leak?" into an assertion. One that fails on the nth call lets you exercise every error path deterministically — the single most effective technique for making error handling actually correct, since those paths are otherwise never executed.

Examples

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

typedef struct {
    void *(*alloc)(void *ctx, size_t size);
    void  (*free)(void *ctx, void *ptr);
    void  *ctx;
} Allocator;

/* --- Backend 1: plain malloc (stateless: ctx is unused) -------------- */
static void *sys_alloc(void *ctx, size_t size) { (void)ctx; return malloc(size); }
static void  sys_free (void *ctx, void *ptr)   { (void)ctx; free(ptr); }

static const Allocator SYSTEM_ALLOCATOR = { sys_alloc, sys_free, NULL };

/* --- Backend 2: a counting wrapper, for tests ----------------------- */
typedef struct {
    const Allocator *inner;
    size_t live;          /* outstanding allocations */
    size_t total;         /* allocations ever made   */
    size_t fail_after;    /* fail once this many succeed (SIZE_MAX = never) */
} CountingCtx;

static void *counting_alloc(void *ctx, size_t size)
{
    CountingCtx *c = ctx;
    if (c->total >= c->fail_after) return NULL;     /* deterministic failure */
    void *p = c->inner->alloc(c->inner->ctx, size);
    if (p) { c->live++; c->total++; }
    return p;
}

static void counting_free(void *ctx, void *ptr)
{
    CountingCtx *c = ctx;
    if (ptr) c->live--;
    c->inner->free(c->inner->ctx, ptr);
}

/* --- A data structure parameterized by its allocator ---------------- */
typedef struct {
    const Allocator *a;      /* remembered so destroy uses the SAME one */
    char            *data;
    size_t           len;
} String;

static String *string_create(const Allocator *a, const char *s)
{
    size_t n = strlen(s) + 1;
    String *str = a->alloc(a->ctx, sizeof *str);
    if (!str) return NULL;

    str->data = a->alloc(a->ctx, n);
    if (!str->data) { a->free(a->ctx, str); return NULL; }   /* no leak */

    memcpy(str->data, s, n);
    str->len = n - 1;
    str->a = a;
    return str;
}

static void string_destroy(String *s)
{
    if (!s) return;
    const Allocator *a = s->a;     /* release through the creating allocator */
    a->free(a->ctx, s->data);
    a->free(a->ctx, s);
}

int main(void)
{
    /* Production path: the system allocator. */
    String *s = string_create(&SYSTEM_ALLOCATOR, "hello");
    if (s) { printf("%s (len %zu)\n", s->data, s->len); string_destroy(s); }

    /* Test path 1: assert that create/destroy is leak-free. */
    CountingCtx ctx = { &SYSTEM_ALLOCATOR, 0, 0, (size_t)-1 };
    Allocator counting = { counting_alloc, counting_free, &ctx };

    String *t = string_create(&counting, "counted");
    printf("live during use : %zu\n", ctx.live);      /* 2 */
    string_destroy(t);
    printf("live after free : %zu (0 means no leak)\n", ctx.live);

    /* Test path 2: force the SECOND allocation to fail and prove the
       error path releases the first one. */
    ctx.live = ctx.total = 0;
    ctx.fail_after = 1;
    String *u = string_create(&counting, "will fail");
    printf("create under injected failure -> %s, live = %zu\n",
           u ? "unexpected success" : "NULL as expected", ctx.live);
    return 0;
}

   ONE INTERFACE, MANY BACKENDS

                    +---------------------------+
   your module ---> | Allocator { alloc, free,  |
   (String, Vec,    |             ctx }         |
    parser, ...)    +------------+--------------+
                                 |
              +------------------+-----------------+---------------+
              v                  v                 v               v
         malloc/free          Arena              Pool         Counting /
         (ctx = NULL)      (ctx = &arena)   (ctx = &pool)   fault-injecting
                                                             (ctx = &stats)

   The module's code never changes; the policy is chosen at the call site.

Key Takeaways

• An allocator interface is a struct of function pointers plus an opaque ctx, the standard way to express policy polymorphism in C.
• Pass the allocator explicitly and store it in objects that own memory, so destruction uses the allocator that created them.
• Fix the failure convention (returns NULL versus never fails) once for the whole interface.
• A counting wrapper turns leak checks into assertions; a fault-injecting wrapper makes every error path testable and deterministic.
• Keep the interface minimal — alloc, realloc, free covers nearly all real use.

🧪 Practice

1. Implement the Allocator interface with two backends (system and arena) and run the same String code through both.
2. Add a realloc slot to the interface and implement it for the arena (hint: it can only grow the most recent allocation in place).
3. Use the fault-injecting allocator to fail the nth allocation for every n in a function that makes five allocations, and verify no path leaks.
4. Interview-style: "Why does the allocator interface need a void *ctx when malloc needs no state?" Hint: think about what an arena or pool must remember between calls, and about testability.

Reference Counting Patterns

Theory

Single ownership — one owner frees the object — covers most C code. But sometimes an object is genuinely shared: a texture used by several sprites, a configuration read by several subsystems, a buffer passed to a queue while the producer still holds it. Nobody knows who will finish last, so nobody can be the sole owner.

Reference counting answers this: the object carries a counter of how many owners it has. retain increments it, release decrements it, and the object is destroyed when the count reaches zero. The last owner out turns off the lights, and no single piece of code needs to know the global picture.

The rules are simple and must be followed exactly:

• Creation returns the object with a count of 1 — the creator is an owner.
• Anyone who stores a pointer for later use calls retain.
• Anyone who is finished with their pointer calls release, and must treat the pointer as invalid afterwards.
• Every retain is matched by exactly one release. One missing release leaks the object forever; one extra destroys it while others are still using it.

Two limitations are fundamental rather than implementation defects. Cycles leak: if A holds a reference to B and B to A, both counts stay at 1 even when nothing else refers to either, and neither is ever freed. The standard remedy is a weak reference — a raw pointer that does not participate in counting — for the "back" direction (parent pointers, observer links), with a rule for handling the case where the target is gone.

Thread safety needs atomics. A plain count++ is a read-modify-write; two threads can interleave and lose an increment, causing a premature free. Use C11 <stdatomic.h>: atomic_fetch_add(&count, 1) for retain, and atomic_fetch_sub(&count, 1) == 1 to detect the last release. Note the atomics protect only the count, not the object's contents — sharing mutable data still needs a lock.

Reference counting also has a real cost: an increment and decrement on every ownership change, cache-line contention when many threads touch the same counter, and destruction happening at an unpredictable point in the program. Use it where sharing is genuine, not as a default.

Examples

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

typedef struct {
    atomic_int refcount;      /* atomic: safe to share across threads */
    char      *data;
    size_t     len;
} SharedBuf;

/* Creation returns the object with refcount == 1: the caller is an owner. */
SharedBuf *sb_create(const char *s)
{
    SharedBuf *b = malloc(sizeof *b);
    if (!b) return NULL;
    b->len  = strlen(s);
    b->data = malloc(b->len + 1);
    if (!b->data) { free(b); return NULL; }
    memcpy(b->data, s, b->len + 1);
    atomic_init(&b->refcount, 1);
    return b;
}

/* Claim shared ownership. Returns the same pointer for convenient chaining. */
SharedBuf *sb_retain(SharedBuf *b)
{
    if (b) atomic_fetch_add(&b->refcount, 1);
    return b;
}

/* Give up ownership. Destroys the object when the LAST owner releases.
   fetch_sub returns the value BEFORE the subtraction, so 1 means "was the
   last reference". */
void sb_release(SharedBuf *b)
{
    if (!b) return;
    if (atomic_fetch_sub(&b->refcount, 1) == 1) {
        free(b->data);
        free(b);                     /* nobody else can reach it now */
    }
}

/* A consumer that stores the pointer must retain it. */
typedef struct { SharedBuf *buf; } Consumer;

void consumer_attach(Consumer *c, SharedBuf *b) { c->buf = sb_retain(b); }
void consumer_detach(Consumer *c) { sb_release(c->buf); c->buf = NULL; }

int main(void)
{
    SharedBuf *b = sb_create("shared payload");     /* count = 1 */
    if (!b) return EXIT_FAILURE;

    Consumer c1, c2;
    consumer_attach(&c1, b);                        /* count = 2 */
    consumer_attach(&c2, b);                        /* count = 3 */
    printf("count = %d, data = %s\n",
           atomic_load(&b->refcount), b->data);

    sb_release(b);                                  /* count = 2 */
    b = NULL;                    /* the creator's pointer is now invalid */

    printf("creator released; consumers still work: %s\n", c1.buf->data);

    consumer_detach(&c1);                           /* count = 1 */
    consumer_detach(&c2);                           /* count = 0 -> destroyed */
    printf("all owners released; object destroyed exactly once\n");
    return 0;
}

   REFERENCE COUNT OVER TIME

   sb_create   -> [count=1]  creator
   attach c1   -> [count=2]  creator, c1
   attach c2   -> [count=3]  creator, c1, c2
   release     -> [count=2]  c1, c2          (creator's pointer now invalid)
   detach c1   -> [count=1]  c2
   detach c2   -> [count=0]  -> free(data); free(object)

   A REFERENCE CYCLE (the failure mode counting cannot solve)

        +-------+  strong   +-------+
        |   A   |---------->|   B   |     external references: none
        |count=1|<----------|count=1|     both counts stay 1 forever
        +-------+  strong   +-------+     -> leaked

   Fix: make one direction WEAK (a raw pointer, no retain), typically the
   child->parent or observer->subject link.

Key Takeaways

• Reference counting suits genuinely shared objects whose last user is not known in advance.
• Creation yields count 1; store means retain, finish means release; every retain needs exactly one matching release.
• One missing release leaks the object; one extra causes a use-after-free for every remaining owner.
• Cycles are never collected — break them with weak (non-counting) references in the back direction.
• Use <stdatomic.h> counters when the object crosses threads; atomics protect the count, not the contents.

🧪 Practice

1. Implement sb_create/sb_retain/sb_release and print the count after every operation for three owners.
2. Build a deliberate two-object cycle, confirm with Valgrind that both objects leak, then break it with a weak pointer.
3. Share one counted object across four threads that each retain, sleep, and release; run with -fsanitize=thread using a plain int count and then an atomic_int.
4. Interview-style: "What can reference counting never reclaim, and how do real systems cope?" Hint: draw two objects pointing at each other and total the counts.

Fragmentation

Theory

A long-running program can fail to allocate 1 MB while holding 500 MB of free memory. That is fragmentation: free memory exists, but not in the shape you need.

Two kinds, with different causes and different remedies:

External fragmentation — free memory is split into many small non-contiguous holes. A request larger than any single hole fails even though the total free space is ample. This is the classic problem, caused by allocating and freeing blocks of varied sizes in varied orders over a long period.

Internal fragmentation — memory wasted inside allocated blocks. Allocators round sizes up to size classes and add headers, so a 100-byte request may consume 128 bytes. Requesting many small blocks (malloc(1) a million times) can waste more memory than it uses.

   EXTERNAL: total free = 300 bytes, but a 200-byte request FAILS

   [ used 100 ][ free 100 ][ used 50 ][ free 100 ][ used 80 ][ free 100 ]
                    ^^^                    ^^^                    ^^^
                    no single hole is large enough

   INTERNAL: you asked for 100, the allocator reserved 128

   [ hdr 16 | your 100 bytes | 12 wasted ]

Modern allocators (glibc's ptmalloc, jemalloc, tcmalloc, mimalloc) fight this hard: size classes group similar requests so freed blocks are reusable by like-sized ones, adjacent free chunks are coalesced, per-thread caches avoid contention, and large requests are served by mmap and returned directly to the kernel on free. As a result, catastrophic fragmentation is rare in ordinary desktop and server programs — but it remains a genuine risk in long-running processes with irregular allocation patterns, and in embedded systems with no virtual memory, where it is often the reason dynamic allocation is banned outright.

The strategies that actually help, roughly in order of effectiveness:

1. Use pools for fixed-size objects. Interchangeable slots make external fragmentation structurally impossible.
2. Use arenas for phase-scoped work. Freeing everything at once returns one large contiguous region, not a spray of holes.
3. Allocate long-lived objects early, before the heap becomes irregular, so they do not sit in the middle of otherwise-free space.
4. Batch small allocations. One block of 1000 records fragments far less than 1000 blocks, and saves 1000 headers.
5. Reserve capacity up front for growable buffers, avoiding the trail of abandoned intermediate blocks that doubling leaves behind.
6. Reuse rather than reallocate. Keep a free list of objects instead of returning them to the allocator.

A measurement caveat that saves a lot of confusion: RSS not falling after you free is usually not a leak and not fragmentation. free returns memory to the allocator, which keeps it for reuse; only large mmap-backed blocks go straight back to the kernel. Compare allocator statistics (malloc_info, mallinfo2, or jemalloc's stats) across time, not process RSS, before concluding anything.

Examples

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

/* Pattern 1: a fragmenting workload -- alternate sizes, free every other. */
static void fragmenting_pattern(void)
{
    enum { N = 1000 };
    void *blocks[N];

    for (int i = 0; i < N; i++)
        blocks[i] = malloc(i % 2 ? 64 : 1024);      /* alternating sizes */

    for (int i = 0; i < N; i += 2)
        free(blocks[i]);                            /* holes everywhere */

    /* The heap now looks like: [free][used][free][used]... */
    void *big = malloc(512 * 1024);
    printf("large request after fragmenting: %s\n", big ? "ok" : "FAILED");
    free(big);

    for (int i = 1; i < N; i += 2) free(blocks[i]);
}

/* Pattern 2: batching -- one allocation instead of N. */
typedef struct { int id; char name[28]; } Record;

static void batched(size_t n)
{
    Record *all = malloc(n * sizeof *all);   /* ONE block, ONE header */
    if (!all) return;
    for (size_t i = 0; i < n; i++) {
        all[i].id = (int)i;
        snprintf(all[i].name, sizeof all[i].name, "rec%zu", i);
    }
    printf("batched  : 1 allocation, %zu bytes, contiguous\n",
           n * sizeof *all);
    free(all);                                /* ONE free */
}

static void unbatched(size_t n)
{
    Record **all = malloc(n * sizeof *all);
    if (!all) return;
    for (size_t i = 0; i < n; i++) all[i] = malloc(sizeof **all);
    /* n+1 allocations, n headers (~16 bytes each), scattered addresses */
    printf("unbatched: %zu allocations, ~%zu bytes of headers alone\n",
           n + 1, n * 16);
    for (size_t i = 0; i < n; i++) free(all[i]);
    free(all);
}

/* Pattern 3: reuse instead of churn -- a tiny free list. */
typedef struct FreeNode { struct FreeNode *next; } FreeNode;
static FreeNode *recycled = NULL;

static Record *record_get(void)
{
    if (recycled) {                    /* reuse: no allocator involvement */
        FreeNode *n = recycled;
        recycled = n->next;
        return (Record *)n;
    }
    return malloc(sizeof(Record));
}

static void record_put(Record *r)
{
    FreeNode *n = (FreeNode *)r;       /* the slot is free: store 'next' in it */
    n->next = recycled;
    recycled = n;
}

int main(void)
{
    fragmenting_pattern();
    batched(1000);
    unbatched(1000);

    Record *a = record_get();
    record_put(a);
    Record *b = record_get();          /* the same block, no malloc call */
    printf("recycled the same block: %s\n", a == b ? "yes" : "no");
    record_put(b);
    while (recycled) { FreeNode *n = recycled; recycled = n->next; free(n); }
    return 0;
}

# Inspect what the allocator is actually holding (glibc):
$ MALLOC_STATS=1 ./prog      # or call malloc_stats() / mallinfo2() in code

# Try a different allocator without changing your program:
$ LD_PRELOAD=/usr/lib/libjemalloc.so ./prog

Key Takeaways

• External fragmentation is free memory split into unusable holes; internal fragmentation is space wasted inside allocated blocks by headers and rounding.
• Modern allocators mitigate both with size classes, coalescing, and thread caches, so severe fragmentation is mostly a long-running or embedded concern.
• Pools and arenas eliminate fragmentation structurally for their patterns — the strongest fix available.
• Batch small allocations, reserve capacity up front, allocate long-lived objects early, and recycle objects rather than churning the heap.
• Process RSS not shrinking after free is normal allocator behaviour, not proof of a leak — measure with allocator statistics instead.

🧪 Practice

1. Allocate 10,000 alternating 64-byte and 1 MB blocks, free every other one, then attempt a large allocation and report the result and the process RSS.
2. Compare total memory used by 100,000 individual malloc(32) calls against one malloc(100000 * 32), and account for the difference.
3. Run a fragmenting workload under the default allocator and again under jemalloc via LD_PRELOAD, comparing peak RSS.
4. Interview-style: "A server's memory usage plateaus at 3 GB and never drops despite freeing everything. Is that a leak?" Hint: distinguish what free returns to the allocator from what the allocator returns to the kernel.

---