Dynamic memory: malloc, free and leaks

Why it exists

Arrays and local variables have a size fixed in the source and a lifetime tied to a block. Real programs often need neither: read $n$ numbers, where $n$ is typed by the user, or build a list that grows, or return a result that must outlive the function that made it. For this the language offers dynamic memory: the program asks the system for a block of a chosen size while it runs, uses it, and gives it back when it is done. The block lives in the heap (see the memory layout page) and its lifetime is chosen by the programmer, not by the block structure.

The price is responsibility. Nothing gives the block back automatically. A program that forgets, loses memory (a leak). A program that gives it back and then keeps using it breaks in ways that are hard to find.

Prerequisites

Precise definitions

All four functions are declared in <stdlib.h>.

Rules and definitions:

• Allocated storage duration. The block exists from the successful call to malloc, calloc or realloc until free or until a successful realloc replaces it. After a successful realloc the old pointer is indeterminate, even if the new address happens to be the same, and any other pointers into the old block dangle.
• The block has no name. It is reachable only through pointers that hold its address. The pointer variable itself is an ordinary local or global, with its own lifetime. Losing the last pointer means losing the block.
• malloc returns void *. In C it converts to any object pointer without a cast. Writing a cast is allowed but unnecessary (C++ is different: there the cast is required).
• Always check for NULL before using the result. A failed allocation returns NULL, and dereferencing it is undefined.
• Size idiom. p = malloc(n * sizeof *p); stays correct if the type of p changes. sizeof *p is the size of one pointee. sizeof p is the size of the pointer itself (8 bytes on a 64-bit machine), a classic mistake.
• Alignment. The returned address is suitably aligned for any type with a fundamental alignment requirement (up to max_align_t, 16 bytes on x86-64 gcc). Over-aligned types need aligned_alloc.
• calloc zero. The bits are all zero. For integers that is the value 0. For pointers and floating-point numbers, the standard does not promise that all-zero bits mean NULL or 0.0, although they do on common machines.
• After free. The block no longer belongs to the program. The value of the pointer becomes indeterminate (C11 6.2.4): using it, even only to compare it, is not allowed. Real machines leave the old address in the variable, which is what makes this bug dangerous (the animation shows it).
• Valid arguments to free. Only a pointer returned by malloc, calloc, realloc or aligned_alloc that has not been freed (or replaced by realloc) yet, or NULL. Anything else (a stack address, a pointer into the middle of a block, a block already freed) is undefined behaviour.
• Memory leak. A block that is still allocated but that the program can no longer reach: it cannot be found by starting from the live variables (globals and locals in scope) and following pointers. Overwriting the last pointer to a block, or letting the last pointer go out of scope, makes it unreachable. A block that is only referenced from inside other unreachable blocks (for example the second node of a list whose first node was lost) is also lost. A single leaked block does not crash anything and is reclaimed when the program ends, but leaks that repeat in a loop or a long-running program eventually use up memory. The C standard has no concept of a leak; it is a property that tools such as AddressSanitizer's leak checker report. Whether a block is unreachable can be decided by drawing the pointers.

Stack versus heap

How it works

One block, from birth to death

Step through the run. Notice (1) the heap block has no name of its own; the stack pointer p is its only handle. (2) q = p makes two pointers to one block. (3) free crosses out the block, but the pointers keep their old addresses and now point at freed memory. Writing p = NULL fixes p only; the copy q stays dangling.

How a leak happens

In this run the only pointer to block A is overwritten by a new malloc. The animation computes, from the program's real pointers, which live blocks nobody can reach, and flags block A. The block is still allocated, still holds 1, 2, and can never be freed.

The bug catalogue

Worked examples

#include <stdio.h>
#include <stdlib.h>
 
int main(void) {
    int n = 5;
    int *p = malloc(n * sizeof *p);
    if (p == NULL) return 1;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        p[i] = i * i;
        sum += p[i];
    }
    printf("%d\n", sum);
    free(p);
    return 0;
}

30

#include <stdio.h>
#include <stdlib.h>
 
int main(void) {
    int *p = calloc(4, sizeof *p);
    if (p == NULL) return 1;
    printf("%d %d %d %d\n", p[0], p[1], p[2], p[3]);
    free(p);
    return 0;
}

0 0 0 0

#include <stdio.h>
#include <stdlib.h>
 
int main(void) {
    int *p = malloc(3 * sizeof *p);
    if (p == NULL) return 1;
    for (int i = 0; i < 3; i++) p[i] = i + 1;
    int *t = realloc(p, 6 * sizeof *p);
    if (t == NULL) {
        free(p);
        return 1;
    }
    p = t;
    for (int i = 3; i < 6; i++) p[i] = i + 1;
    int s = 0;
    for (int i = 0; i < 6; i++) s += p[i];
    printf("%d %d\n", p[0], s);
    free(p);
    return 0;
}

1 21

#include <stdio.h>
#include <stdlib.h>
 
int main(void) {
    int *p = malloc(10 * sizeof *p);
    if (p == NULL) return 1;
    printf("%zu %zu %zu\n", sizeof p, sizeof *p, 10 * sizeof *p);
    free(p);
    return 0;
}

8 4 40

#include <stdio.h>
#include <stdlib.h>
 
static int live;
 
static int *grab(void) {
    live++;
    return malloc(sizeof(int));
}
 
static void drop(int *p) {
    live--;
    free(p);
}
 
int main(void) {
    int *p = NULL;
    for (int i = 0; i < 3; i++) {
        p = grab();
        if (p == NULL) return 1;
        *p = i;
    }
    drop(p);
    printf("%d\n", live);
    return 0;
}

2

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
static char *dup(const char *s) {
    char *d = malloc(strlen(s) + 1);
    if (d == NULL) return NULL;
    strcpy(d, s);
    return d;
}
 
int main(void) {
    char *c = dup("GATE");
    if (c == NULL) return 1;
    c[0] = 'g';
    printf("%s %zu\n", c, strlen(c));
    free(c);
    return 0;
}

gATE 4

int *make(int n) {
    int *p = malloc(n * sizeof *p);
    for (int i = 0; i < n; i++) p[i] = 0;
    return p;
}
 
void use(void) {
    int *a = make(10);
    a = make(5);
    free(a);
}

Cheat box

Traps and GATE patterns

Connections

The heap region and the other regions of a program are laid out on the memory layout page. The structure that makes dynamic memory essential is the singly linked list, where every node is a separate block. At the operating-system level, the heap manager faces the same questions as memory management (fragmentation, free lists), and the heap is one part of the process address space.

PYQs

Self-check

#include <stdio.h>
#include <stdlib.h>
 
static int live;
 
static void *get(size_t n) {
    live++;
    return malloc(n);
}
 
int main(void) {
    int *a = get(sizeof *a);
    int *b = get(sizeof *b);
    if (a == NULL || b == NULL) return 1;
    a = b;
    free(a);
    live--;
    printf("%d\n", live);
    return 0;
}

1

Revision card

References