A program's memory

Three areas

A program's data lives in three areas of memory, which differ in their lifetime:

The following program prints an address from each area, and that of the code:

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

int globale = 1;
const char *litteral = "une chaine";

int main(void)
{
    int locale = 2;
    int *tas = malloc(sizeof *tas);

    printf("code    (main)     : %p\n", (void *)main);
    printf("littéral           : %p\n", (void *)litteral);
    printf("globale            : %p\n", (void *)&globale);
    printf("tas                : %p\n", (void *)tas);
    printf("pile    (locale)   : %p\n", (void *)&locale);
    free(tas);
    return 0;
}

code    (main)     : 0x5b46218291a9
littéral           : 0x5b462182a004
globale            : 0x5b462182c010
tas                : 0x5b464f80e2a0
pile    (locale)   : 0x7ffefd7043fc

The code is at the bottom, followed by the literals (read-only), then the global variables. The heap (tas) comes next, and grows upwards. The stack (pile) is right at the top of the address space, and grows downwards. (Converting the address of a function into a void * is not allowed by the standard, -pedantic flags it; it is accepted on Linux, and handy for this demonstration.)

The static area

String literals

Static data is described in the executable file itself, organised in sections: .rodata for constants, .data for initialised variables, .bss for those that are zero (chapter 1). At start-up, the loader puts them in place. You can see it in the assembly produced by gcc -S for this one-line file:

char *s = "une chaine";

        .section        .rodata
.LC0:
        .string "une chaine"
        .section        .data.rel.local,"aw"
        .align 8
        .type   s, @object
        .size   s, 8
s:
        .quad   .LC0

There are two objects. The string itself, under the label .LC0, in the .rodata (read-only data) section: the system will load it into read-only pages. And the variable s, in a section of modifiable data: 8 bytes (.quad) that contain the address .LC0.

We find again what we saw in chapter 2: writing into a literal is undefined behaviour. Here, the page is protected, and the system kills the program:

#include <stdio.h>

int main(void)
{
    const char *s = "chaine";
    char *t = (char *)s;
    t[0] = 'C';
    printf("%s\n", s);
    return 0;
}

Segmentation fault (core dumped)

The (char *) cast silences the compiler; it does not make the memory writable.

Macros

#define gives a name to a value, for the whole file:

#define TAILLE 100

It is the preprocessor that replaces each TAILLE with 100, before compilation (chapter 1). It reserves no memory: for the compiler, TAILLE never existed. But it is a text replacement, which respects neither the precedences nor the scope of C.

#include <stdio.h>

#define CARRE(x) x * x
#define CARRE_BIEN(x) ((x) * (x))

int main(void)
{
    printf("%d\n", CARRE(1 + 2));
    printf("%d\n", CARRE_BIEN(1 + 2));
    printf("%d\n", 100 / CARRE_BIEN(5));
    printf("%d\n", 100 / CARRE(5));
    return 0;
}

5
9
4
100

CARRE(1 + 2) becomes 1 + 2 * 1 + 2, which is 5. 100 / CARRE(5) becomes 100 / 5 * 5, which is 100.

Initialisers

An array or a structure is initialised with a list between braces, whose values are stored in order:

#include <stdio.h>

struct contact {
    const char *nom, *prenom;
    int age;
};

struct contact moi = {"Ritchie", "Dennis", 70};
struct contact lui = {.prenom = "Ken", .nom = "Thompson"};
int tab[5] = {4, 3, 2, 1, 0};
int zeros[100] = {0};
int debut[5] = {7, 8};

int main(void)
{
    char s[] = {'H', 'e', 'l', 'l', 'o', '\0'};
    char s2[] = "Hello";

    printf("s = \"%s\", sizeof s = %zu, sizeof s2 = %zu\n", s, sizeof s, sizeof s2);
    printf("%s %s, %d ans\n", moi.prenom, moi.nom, moi.age);
    printf("%s %s, %d ans\n", lui.prenom, lui.nom, lui.age);
    for (int i = 0; i < 5; i++)
        printf("%d ", debut[i]);
    printf("\n");
    printf("%d %d\n", tab[0], zeros[99]);
    return 0;
}

s = "Hello", sizeof s = 6, sizeof s2 = 6
Dennis Ritchie, 70 ans
Ken Thompson, 0 ans
7 8 0 0 0 
4 0

• The size of an initialised array may be omitted: the compiler counts it. s and s2 are identical, "Hello" is just a shorter way of writing the list of characters.
• You can name the fields of a structure (.prenom = …), in any order.
• Everything that is not initialised is zero, as soon as part of it is: debut ends with three zeros, lui.age is 0, and {0} sets a whole array to zero.
• Global (and static) variables without an initialiser are zero as well. Local variables without an initialiser, however, contain anything at all.

The stack

A function's frame

On each function call, a frame (stack frame) is pushed: it contains the parameters, the local variables, the address to return to at the end of the call, and a few saved registers. On return, the frame is popped, and its space will be reused by the next call. Reserving and freeing stack space costs almost nothing: the stack pointer just has to be moved.

int t[5];

therefore reserves 20 bytes in the current frame, for the duration of the call. No more, no less.

Never return the address of a local variable

int *f(void)
{
    int x = 1;
    return &x;
}

When f returns, x no longer exists: its frame has been popped. The returned address designates a cell that the next function call will reuse. gcc flags it:

local.c:6:12: warning: function returns address of local variable [-Wreturn-local-addr]

and, since it is undefined behaviour, it even allows itself to return NULL instead: printf("%p", f()) prints (nil). Another compiler will return the real address, and the program will seem to work… until the next call.

A structure on the stack

Conversely, when a piece of data is only used during the call, the stack is the ideal place: no malloc, no free, no possible leak. The following example walks through a linked list up to the first occurrence of a value. To stop the printing loop, it temporarily inserts into the list a sentinel link, which is a local variable:

typedef struct s_list *t_list;
struct s_list {
    int data;
    t_list next;
};

/* prints the elements of l up to the first occurrence of bound, included */
void afficher_jusqua(t_list l, int bound)
{
    t_list tmp, save_pos;
    struct s_list sentinel;

    for (tmp = l; tmp != NULL && tmp->data != bound; tmp = tmp->next)
        ;
    if (tmp == NULL)
        return;
    save_pos = tmp;
    sentinel.data = -42;
    sentinel.next = tmp->next;
    tmp->next = &sentinel;
    for (tmp = l; tmp != &sentinel; tmp = tmp->next)
        printf("%d ", tmp->data);
    printf("\n");
    save_pos->next = sentinel.next;
}

On the list 1 2 3 4 5, afficher_jusqua(l, 3) prints 1 2 3. The sentinel is identified by its address, &sentinel: no allocated link can have the same one. And the list is restored before returning, before the sentinel disappears: otherwise the list would point to a dead stack cell.

(The example is deliberately artificial: a simple test tmp->data != bound would do the job. It shows that an address on the stack is an address like any other, as long as the function has not finished.)

The heap

malloc, calloc, realloc, free

When a piece of data must outlive the function that creates it, or its size is only known at run time, it is placed on the heap, with the functions of stdlib.h:

void *malloc(size_t size);
void *calloc(size_t nmemb, size_t size);
void *realloc(void *ptr, size_t size);
void free(void *ptr);

• malloc(n) reserves a block of n bytes, uninitialised, and returns its address.
• calloc(nb, taille) reserves an array of nb elements of taille bytes, set to zero.
• realloc(p, n) changes the size of block p to n bytes. If the block can grow in place, it does; otherwise, realloc reserves a new block, copies the old contents into it, frees the old one and returns the new address.
• free(p) frees block p, which must come from one of the three previous functions. free(NULL) does nothing.

Each block returned is disjoint from all the others. If there is no room left, the three functions return NULL.

The size is written with sizeof applied to the variable itself, which stays correct if its type changes:

int *t = malloc(n * sizeof *t);
if (t == NULL) {
    /* handle the error */
}

realloc may move the block:

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

int main(void)
{
    char *p1 = malloc(32);
    printf("p1 = %p\n", (void *)p1);
    char *p2 = realloc(p1, 256);
    printf("p2 = %p\n", (void *)p2);
    free(p2);
    return 0;
}

p1 = 0x62491eae42a0
p2 = 0x62491eae52e0

After the call, p1 must no longer be used: the block has been freed.

Alignment

The processor reads faster (and sometimes can only read) data stored at an address that is a multiple of its size: a double at an address that is a multiple of 8, for example. malloc does not know what will be stored in the block: so it returns an address suitable for any type. This maximal alignment is given by _Alignof(max_align_t): 16 bytes on a current 64-bit PC.

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

int main(void)
{
    void *p[5];

    printf("alignement maximal : %zu\n", _Alignof(max_align_t));
    for (size_t i = 0; i < 5; i++) {
        p[i] = malloc(i * 8 + 1);
        printf("malloc(%2zu) = %p, reste %zu\n", i * 8 + 1, p[i],
               (size_t)((uintptr_t)p[i] % _Alignof(max_align_t)));
    }
    for (size_t i = 0; i < 5; i++)
        free(p[i]);
    return 0;
}

alignement maximal : 16
malloc( 1) = 0x5857714852b0, reste 0
malloc( 9) = 0x5857714852d0, reste 0
malloc(17) = 0x5857714852f0, reste 0
malloc(25) = 0x585771485310, reste 0
malloc(33) = 0x585771485340, reste 0

All the addresses are multiples of 16 (the remainder, reste, is 0). Notice also that a one-byte block takes up 32: malloc keeps, just before each block, a few bytes for itself (the size of the block, in particular), and rounds up.

A vector that grows

realloc makes it possible to write an array whose size adapts to its contents. We keep the number of elements (taille) and the reserved space (capacite). When the array is full, we double its capacity:

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

typedef struct s_vect *t_vect;
struct s_vect {
    size_t taille, capacite;
    int *tab;
};

t_vect vect_nouveau(void)
{
    t_vect v = malloc(sizeof *v);
    if (v == NULL)
        return NULL;
    v->taille = 0;
    v->capacite = 1;
    v->tab = malloc(v->capacite * sizeof *v->tab);
    if (v->tab == NULL) {
        free(v);
        return NULL;
    }
    return v;
}

/* appends x to v; returns 0, or -1 if memory runs out */
int vect_ajouter(t_vect v, int x)
{
    if (v->taille == v->capacite) {
        size_t cap = 2 * v->capacite;
        int *t = realloc(v->tab, cap * sizeof *t);
        if (t == NULL)
            return -1;
        v->tab = t;
        v->capacite = cap;
    }
    v->tab[v->taille++] = x;
    return 0;
}

void vect_detruire(t_vect v)
{
    free(v->tab);
    free(v);
}

Adding 1000 elements takes the capacity through 2 4 8 16 32 64 128 256 512 1024: only ten calls to realloc. Why double, rather than add one cell each time? Each realloc may copy the whole array. Adding one cell at a time, $n$ additions would cost up to $1 + 2 + \dots + n$ copies, of the order of $n^2$. By doubling, the copies come to at most $1 + 2 + 4 + \dots + n < 2n$: an addition costs constant time on average.

Under malloc: virtual memory

Addresses that are not physical

Several programs run at the same time on the machine. Yet each one sees its stack at roughly the same address, and none can read the memory of the others. That is because the addresses a program handles are not those of the memory modules: they are virtual addresses.

A component of the processor, the MMU (Memory Management Unit), translates on the fly each virtual address into a physical address, according to a table that the system keeps up to date for each process. This solves several problems at once:

• each process has its own address space, always organised the same way, whatever the space it actually occupies;
• this space looks contiguous to the program, even if the physical memory holding it is scattered;
• an area can grow (the heap, the stack): translations just have to be added;
• a process cannot reach the memory of another: the addresses that do not belong to it have no translation. Accessing them causes a fault, and the system kills the program: this is the “segmentation fault”.

Paging

Translating addresses one by one would require a huge table. On a 32-bit machine, there are $2^{32}$ addresses; with 4 bytes per entry, the table would take up $4 \times 2^{32} = 2^{34}$ bytes, that is 16 GiB, for each process.

So memory is cut into blocks of fixed size, generally 4 KiB ($2^{12}$ bytes): pages for virtual memory, frames for physical memory. The table now only translates page numbers. A 32-bit address is split in two:

The MMU replaces the page number with the frame number, and keeps the position. There remain $2^{20}$ pages, that is a table of $4 \times 2^{20}$ bytes = 4 MiB per process: much better, but still too much for a program that only uses a few pages. So the table is itself cut into a tree: on 32 bits, a first level of 1024 entries, each pointing to a second-level table of 1024 entries, which are only created for the areas actually in use. Each table fits exactly in one page (1024 × 4 bytes). 64-bit machines use four or five levels.

The break: brk and sbrk

The address space of a Unix process is organised as follows, from low addresses to high ones:

  low addresses
  ┌─────────────────────┐
  │ code (.text)        │  read and execute
  │ literals (.rodata)  │  read-only
  │ globals (.data)     │  initialised
  │ globals (.bss)      │  zeroed
  ├─────────────────────┤
  │ heap        ↓ grows
  ├─────────────────────┤ ← the break
  │                     │
  │   (not mapped)      │
  │                     │
  │ stack       ↑ grows
  └─────────────────────┘
  high addresses

The end of the heap is called the break: beyond it, addresses no longer have a translation. Two system calls move it:

#include <unistd.h>
int brk(void *addr);
void *sbrk(intptr_t increment);

brk(addr) places the break at address addr. sbrk(n) moves it by n bytes, and returns its old position: which is precisely the address of the start of the area gained. sbrk(0) gives the current position. These functions are no longer part of the POSIX standard; the Linux C library still provides them, and you must compile with -D_DEFAULT_SOURCE to see them.

A minimal malloc fits in three lines:

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

void *mon_malloc(size_t n)
{
    void *p = sbrk(n);
    if (p == (void *)-1)
        return NULL;
    return p;
}

int main(void)
{
    printf("break initial : %p\n", sbrk(0));
    int *a = mon_malloc(4 * sizeof (int));
    int *b = mon_malloc(4 * sizeof (int));
    a[0] = 1;
    b[0] = 2;
    printf("a = %p, b = %p\n", (void *)a, (void *)b);
    printf("break final   : %p\n", sbrk(0));
    return 0;
}

$ gcc -std=c11 -Wall -Wextra -Werror -D_DEFAULT_SOURCE sbrk.c -o sbrk
$ ./sbrk
break initial : 0x64e15d379000
a = 0x64e15d39a000, b = 0x64e15d39a010
break final   : 0x64e15d39a020

a and b follow each other, 16 bytes apart. But a is not at the initial break: in between, the first printf itself called malloc for its buffer (chapter 5), and malloc moved the break forward by 132 KiB in one go. mon_malloc has no free, and does not care about alignment.

mmap

The mmap system call is used to map a file into memory: its bytes become accessible like those of an array. But in anonymous mode, without a file, it simply reserves fresh pages, filled with zeros:

#include <stdio.h>
#include <sys/mman.h>
#include <unistd.h>

int main(void)
{
    size_t n = 100;
    char *p = mmap(NULL, n, PROT_READ | PROT_WRITE,
                   MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (p == MAP_FAILED) {
        perror("mmap");
        return 1;
    }
    printf("p = %p, taille de page = %ld\n", (void *)p, sysconf(_SC_PAGESIZE));
    p[4095] = 'x';
    printf("p[4095] = %c\n", p[4095]);
    munmap(p, n);
    return 0;
}

$ gcc -std=c11 -Wall -Wextra -Werror -D_DEFAULT_SOURCE mmap.c -o mmap
$ ./mmap
p = 0x7e8b7d844000, taille de page = 4096
p[4095] = x

• The first argument is a desired address; NULL lets the system choose.
• PROT_READ | PROT_WRITE: the pages will be readable and writable.
• MAP_PRIVATE | MAP_ANONYMOUS: pages belonging to the process, which correspond to no file. The descriptor is then -1 and the offset 0.
• On failure, mmap does not return NULL but MAP_FAILED.
• munmap gives the pages back to the system.

mmap works in whole pages: the request for 100 bytes reserved a page of 4096, and p[4095] really is ours (you do not rely on this in a real program). So small blocks are reserved with malloc, and mmap is for large ones. That is in fact what Linux's malloc does: beyond 128 KiB, it goes through mmap. Unlike sbrk, mmap can safely be used alongside malloc.

Other ways of managing memory

malloc is general-purpose: it accepts any size, in any order. When you know your needs better, you can do something simpler and faster, by taking a big block from malloc once, and cutting it up yourself.

Recycling pools

A linked list, a tree, constantly allocates and frees small blocks all of the same size. You can reserve in one go an array of blocks (the pool), and keep the list of free blocks:

• allocating means taking the first block of the free list;
• freeing means putting it back at the head of that list;
• when the pool is full, a second one is reserved (not with realloc, which would move the blocks already handed out, and so invalidate the pointers to them).

Both operations take constant time, without ever searching.

Allocation in waves: arenas

A program often works in phases: read a request, process it, reply; everything reserved during the phase becomes useless at the end. It is the same logic as a function's local variables, which are born and die together. An arena reproduces this on the heap:

• a big block is reserved;
• each allocation simply moves a cursor forward in this block;
• a small block is never freed on its own: at the end of the phase, the cursor is put back at the start, and everything is freed at once.

#include <stdlib.h>
#include <stddef.h>

struct arene {
    char *debut;
    size_t taille, utilise;
};

int arene_creer(struct arene *a, size_t taille)
{
    a->debut = malloc(taille);
    a->taille = taille;
    a->utilise = 0;
    return a->debut == NULL ? -1 : 0;
}

void *arene_allouer(struct arene *a, size_t n)
{
    size_t al = _Alignof(max_align_t);
    size_t pos = (a->utilise + al - 1) / al * al;   /* rounded up to a multiple of al */
    if (pos + n > a->taille)
        return NULL;
    a->utilise = pos + n;
    return a->debut + pos;
}

void arene_vider(struct arene *a)
{
    a->utilise = 0;
}

void arene_detruire(struct arene *a)
{
    free(a->debut);
    a->debut = NULL;
}

arene_allouer rounds the position up to the next multiple of 16, so as to return addresses as well aligned as those of malloc. Three allocations of 40, 5 and 8 bytes thus occupy positions 0, 48 and 64, and utilise is 72; after arene_vider, the next phase reuses exactly the same addresses. An allocation costs one addition and one comparison. Compilers, web servers and game engines all use this technique.

Finding memory errors

Memory errors are insidious: an overflow of a few bytes does not necessarily crash the program, and a leak does not show in a program that runs for one second. Two tools make them visible. Here is a program that contains both:

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

char *dupliquer(const char *s)
{
    char *d = malloc(strlen(s));
    strcpy(d, s);
    return d;
}

int main(void)
{
    char *a = dupliquer("bonjour");
    char *b = dupliquer("au revoir");
    free(a);
    (void)b;
    return 0;
}

It compiles without warnings, runs without errors and returns 0. Yet malloc(strlen(s)) forgets the cell for the '\0': strcpy writes one byte too many. And b is never freed.

valgrind

valgrind runs the program in a simulated machine that watches every memory access. Compile with -g, so that it can quote line numbers:

$ gcc -std=c11 -Wall -Wextra -Werror -g fuite.c -o fuite
$ valgrind --leak-check=full ./fuite
Invalid write of size 1
   at 0x484F39E: strcpy (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
   by 0x1091E3: dupliquer (fuite.c:7)
   by 0x109204: main (fuite.c:13)
 Address 0x4a8c047 is 0 bytes after a block of size 7 alloc'd
   at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
   by 0x1091CC: dupliquer (fuite.c:6)
   by 0x109204: main (fuite.c:13)
…
9 bytes in 1 blocks are definitely lost in loss record 1 of 1
   at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
   by 0x1091CC: dupliquer (fuite.c:6)
   by 0x109217: main (fuite.c:14)

It is all there: a one-byte write “0 bytes after a block of size 7”, made by strcpy on line 7, into a block reserved on line 6; and 9 bytes lost, reserved on line 6 during the call on line 14. Under valgrind the program runs 20 to 50 times slower, but without recompiling anything.

-fsanitize=address

The compiler can also add checks itself around each memory access: this is AddressSanitizer. The program runs barely twice as slowly, and stops at the first error:

$ gcc -std=c11 -Wall -Wextra -Werror -g -fsanitize=address fuite.c -o fuite
$ ./fuite
==345136==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x502000000017
WRITE of size 8 at 0x502000000017 thread T0
    #0 0x79b3692a7922 in strcpy
    #1 0x5651c085a263 in dupliquer fuite.c:7
    #2 0x5651c085a284 in main fuite.c:13
0x502000000017 is located 0 bytes after 7-byte region [0x502000000010,0x502000000017)
allocated by thread T0 here:
    #0 0x79b3692fd9c7 in malloc
    #1 0x5651c085a24c in dupliquer fuite.c:6

It also detects overflows on the stack (the magic example of chapter 2), the use of a block after free, double frees, and, at the end of the program, leaks.