Dynamic memory and the heap

So far every variable has had a size fixed when the program was written and a lifetime tied to a block or to the whole program. Real programs often need memory whose size is known only at run time, such as an array big enough for however many records a file contains, or data that must outlive the function that created it, such as the nodes of a linked list. For that C provides dynamic memory, allocated on request from a region called the heap and returned when no longer needed. Python does this for you invisibly; in C you call malloc to get memory and free to give it back, and you are responsible for doing both exactly right. This lesson describes the memory layout of a process, the allocation functions, the idea of ownership, and the four classic heap errors, leaks, use after free, double free and overflow, with the reports AddressSanitizer and Valgrind produce for each.

The memory layout of a process

A running C program's address space is divided into regions. The text segment holds the machine code and is read-only. Read-only data holds string literals and other constants. The data segment holds global and static variables that have initial values, and the bss segment holds those that start at zero. The stack, described in lesson 4, holds a frame for each active function call; it is limited in size, commonly 8 MB on Linux, and memory on it is released automatically when functions return. The heap is a large region managed by the C library's allocator, from which malloc hands out blocks of any size you ask for; memory there stays allocated until you free it, however many functions return in the meantime.

malloc, calloc, realloc and free

The allocation functions are declared in stdlib.h. malloc(size) allocates size bytes and returns a void * pointing to the start of the block, or NULL if it cannot. The contents are uninitialized. calloc(count, size) allocates an array of count elements of size bytes each, sets every byte to zero, and checks that count times size does not overflow, which makes it the safer choice for arrays. realloc(p, new_size) resizes a block, possibly moving it to a new address and copying the old contents; it returns the new pointer, or NULL if it fails, in which case the old block is untouched. free(p) returns a block to the allocator; p must be exactly a pointer obtained from one of these functions, and free(NULL) does nothing.

Two idioms prevent many mistakes. First, compute sizes from the pointer, not the type: int *v = malloc(n * sizeof *v); stays correct even if v's type later changes to long *. Second, never assign realloc's result straight back to the only pointer you have: if realloc fails it returns NULL and you lose the address of the original block, leaking it. Assign to a temporary, check it, then update the original.

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

int main(void) {
    size_t n = 5;
    int *v = malloc(n * sizeof *v);           /* room for 5 ints */
    if (v == NULL) {
        fprintf(stderr, "out of memory\n");
        return EXIT_FAILURE;
    }
    for (size_t i = 0; i < n; i++) v[i] = (int)(i * i);

    size_t bigger = 8;
    int *tmp = realloc(v, bigger * sizeof *v); /* grow to 8 ints */
    if (tmp == NULL) {
        free(v);                              /* old block still valid */
        return EXIT_FAILURE;
    }
    v = tmp;
    for (size_t i = n; i < bigger; i++) v[i] = -1;

    for (size_t i = 0; i < bigger; i++) printf("%d ", v[i]);
    printf("\n");

    double *zeros = calloc(4, sizeof *zeros);  /* zero-initialized array */
    if (zeros) printf("calloc gave %.1f %.1f %.1f %.1f\n", zeros[0], zeros[1], zeros[2], zeros[3]);

    free(zeros);
    free(v);
    v = NULL;                                 /* avoid a dangling pointer */
    return 0;
}

0 1 4 9 16 -1 -1 -1
calloc gave 0.0 0.0 0.0 0.0

On Linux, malloc rarely returns NULL in ordinary programs, because the kernel promises memory optimistically and only finds out it cannot deliver when the memory is first used. That does not excuse skipping the check: other systems, embedded devices and programs running under memory limits do return NULL, and a missing check turns an out-of-memory condition into a crash at some unrelated place. In small programs the simplest correct response is to print a message to stderr and exit with a failure status.

Ownership

Every heap block must be freed exactly once, after its last use. In a program of any size, the only way to achieve that is to decide, for every pointer to heap memory, who owns it, meaning which piece of code is responsible for freeing it. A function that allocates and returns memory transfers ownership to its caller, and its documentation must say so: the comment "the caller must free the result" is a vital part of the interface. A function that receives a pointer and only uses it borrows it and must not free it. Data structures own the memory of their elements, and provide a destroy function that frees everything. When you design a function, decide ownership first; most heap bugs come from two parts of a program each assuming the other will free a block, or both freeing it.

A common example is duplicating a string. POSIX provides strdup, and C23 added it to the standard library, but it is easy to write and shows the pattern clearly: allocate strlen + 1 bytes, copy, and return the new block, which the caller then owns.

/* Return a newly allocated copy of s, or NULL if memory runs out.
   The caller owns the result and must free it. */
char *copy_string(const char *s) {
    size_t n = strlen(s) + 1;
    char *copy = malloc(n);
    if (copy != NULL) {
        memcpy(copy, s, n);
    }
    return copy;
}

Memory leaks

A memory leak happens when a program loses every pointer to a heap block without freeing it. The block stays allocated until the program exits, because nothing can ever reach it again. A short program that leaks a little does no harm, since the operating system reclaims all of a process's memory when it ends, but servers, editors, games and embedded systems run for days or years, and a leak in a loop eventually exhausts memory. AddressSanitizer includes LeakSanitizer, which checks at exit for blocks that are no longer reachable and reports where each was allocated.

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

static char *make_greeting(const char *name) {
    size_t n = strlen("Hello, ") + strlen(name) + 1;
    char *s = malloc(n);
    if (s == NULL) return NULL;
    snprintf(s, n, "Hello, %s", name);
    return s;                      /* the caller now owns s */
}

int main(void) {
    for (int i = 0; i < 3; i++) {
        char *g = make_greeting("Ada");
        if (g) printf("%s\n", g);
        /* bug: missing free(g); */
    }
    return 0;
}

=================================================================
==4242==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 22 byte(s) in 2 object(s) allocated from:
    #0 0x7fddc2afd9c7 in malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:69
    #1 0x55ad2ead22ae in make_greeting leak.c:7
    #2 0x55ad2ead230e in main leak.c:15
    #3 0x7fddc1e2a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    ...

SUMMARY: AddressSanitizer: 22 byte(s) leaked in 2 allocation(s).

The report lists blocks that nothing points to any more: 22 bytes in 2 allocations of 11 bytes each ("Hello, Ada" is 10 characters plus the terminator), both allocated by malloc in make_greeting at line 7, called from main at line 15. The third block was still reachable through the variable g when main returned, so LeakSanitizer did not count it; Valgrind, below, reports all three. The fix is to call free(g) after printing, which is exactly what make_greeting's ownership comment told the caller to do.

Use after free and double free

After free(p), the block may be reused for a later allocation, but p still holds the old address; it has become a dangling pointer. Reading through it may return stale data or another allocation's data, and writing through it corrupts whatever now lives there. Calling free twice on the same block, a double free, corrupts the allocator's own bookkeeping. Both are serious security vulnerabilities, because an attacker who can control what is allocated in the freed space can often take control of the program. A simple habit helps: set a pointer to NULL immediately after freeing it, so that a later accidental use crashes predictably and a second free(NULL) is harmless.

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

int main(void) {
    int *scores = malloc(3 * sizeof *scores);
    if (scores == NULL) return 1;
    scores[0] = 90;
    free(scores);
    printf("reading freed memory...\n");
    fflush(stdout);
    printf("%d\n", scores[0]);          /* use after free */
    return 0;
}

$ gcc -std=c17 -Wall -Wextra uaf.c -o prog
uaf.c: In function 'main':
uaf.c:11:5: warning: pointer 'scores' used after 'free' [-Wuse-after-free]
   11 |     printf("%d\n", scores[0]);          /* use after free */
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~
uaf.c:8:5: note: call to 'free' here
    8 |     free(scores);
      |     ^~~~~~~~~~~~
$ ./prog
reading freed memory...
=================================================================
==4242==ERROR: AddressSanitizer: heap-use-after-free on address 0x502000000010 at pc 0x55cbf91e840a bp 0x7fff8221b6e0 sp 0x7fff8221b6d0
READ of size 4 at 0x502000000010 thread T0
    #0 0x55cbf91e8409 in main uaf.c:11
    #1 0x7fa7f3e2a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #2 0x7fa7f3e2a28a in __libc_start_main_impl ../csu/libc-start.c:360
    #3 0x55cbf91e8204 in _start (prog+0x1204) (BuildId: 54745f6d23fa484cdfe58b79193bdcb6034c02d3)

0x502000000010 is located 0 bytes inside of 12-byte region [0x502000000010,0x50200000001c)
freed by thread T0 here:
    #0 0x7fa7f4afc4d8 in free ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:52
    #1 0x55cbf91e8368 in main uaf.c:8
    #2 0x7fa7f3e2a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #3 0x7fa7f3e2a28a in __libc_start_main_impl ../csu/libc-start.c:360
    ...

previously allocated by thread T0 here:
    #0 0x7fa7f4afd9c7 in malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:69
    #1 0x55cbf91e82de in main uaf.c:5
    #2 0x7fa7f3e2a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #3 0x7fa7f3e2a28a in __libc_start_main_impl ../csu/libc-start.c:360
    ...

SUMMARY: AddressSanitizer: heap-use-after-free uaf.c:11 in main
(shadow memory map omitted)

Recent versions of GCC spot this simple case at compile time with -Wuse-after-free, enabled by -Wall, but in real programs the free and the use are usually in different functions, where only a run-time tool can see them. AddressSanitizer's report gives three stack traces: where the bad READ happened, where the block was freed, and where it was originally allocated. Together they usually point straight at the ownership mistake.

Valgrind

Valgrind's Memcheck tool finds the same kinds of errors in a different way: it runs your unmodified executable on a simulated processor and checks every memory access, so you do not need to recompile with special options, though -g gives better reports. It is slower than AddressSanitizer, often 20 to 50 times slower than normal, but it also detects the use of uninitialized values, which AddressSanitizer does not (MemorySanitizer, available in Clang, does). Do not combine the two: run Valgrind on a build without -fsanitize. Its summary at exit lists heap usage and classifies leaks; "definitely lost" means no pointer to the block remains.

gcc -std=c17 -Wall -Wextra -g leak.c -o leak     # no sanitizers
valgrind --leak-check=full ./leak

==4242== Memcheck, a memory error detector
Hello, Ada
Hello, Ada
Hello, Ada
==4242== HEAP SUMMARY:
==4242==     in use at exit: 33 bytes in 3 blocks
==4242==   total heap usage: 4 allocs, 1 frees, 4,129 bytes allocated
==4242== 33 bytes in 3 blocks are definitely lost in loss record 1 of 1
==4242==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==4242==    by 0x1091D8: make_greeting (leak.c:7)
==4242==    by 0x109237: main (leak.c:15)
==4242== LEAK SUMMARY:
==4242==    definitely lost: 33 bytes in 3 blocks
==4242==    indirectly lost: 0 bytes in 0 blocks
==4242==      possibly lost: 0 bytes in 0 blocks
==4242==    still reachable: 0 bytes in 0 blocks
==4242==         suppressed: 0 bytes in 0 blocks
==4242== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

A clean program ends with "All heap blocks were freed -- no leaks are possible" and an error summary of 0 errors. Make that your standard for every program you submit: build with the sanitizers while developing, and run your tests under Valgrind as a second check.