Dynamic memory · about 50 min

Memory bugs and valgrind

Why this matters

Memory bugs are the defining hazard of C. Around 70 percent of serious security vulnerabilities in large C and C++ code bases (Microsoft and Google have both published this figure) are memory safety bugs: writing past the end of a buffer, using memory after freeing it, and their relatives. What makes them dangerous is that they usually do not crash where they happen. The program keeps running with corrupted memory and fails later, somewhere else, or never visibly, until an attacker finds the input that makes it do something useful for them. You cannot find these bugs by looking at output. You need a tool that watches memory, and the classic one is valgrind.

The bug catalog

There are five kinds of heap bugs to know by name. Here is a single program with one of each, selected by a command-line argument:

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

int main(int argc, char *argv[])
{
    int which = argc > 1 ? atoi(argv[1]) : 0;
    if (which == 1) {                     /* off by one */
        int *a = malloc(5 * sizeof *a);
        for (int i = 0; i <= 5; i++)
            a[i] = i;
        free(a);
    } else if (which == 2) {              /* use after free */
        char *name = malloc(16);
        strcpy(name, "Ada");
        free(name);
        printf("%c\n", name[0]);
    } else if (which == 3) {              /* uninitialized */
        int *count = malloc(sizeof *count);
        if (*count > 10)
            printf("big\n");
        free(count);
    } else if (which == 4) {              /* leak */
        char *buf = malloc(100);
        buf = malloc(200);
        free(buf);
    }
    return 0;
}

Run normally, every one of these runs to completion with exit status 0. Case 2 even prints A, the "right" answer. The bugs are invisible.

Heap buffer overflow (case 1): reading or writing outside the block. The loop runs to i <= 5, writing a sixth int into a five-int block. The write lands in padding or in the next chunk's header.
Use after free (case 2): accessing a block after free. The memory may still hold the old bytes, or may already belong to another allocation.
Uninitialized read (case 3): using the value of memory nobody wrote. malloc does not clear memory, so the branch depends on leftover bytes.
Memory leak (case 4): losing the last pointer to a block. The first malloc(100) can never be freed.
Invalid or double free: calling free on something that is not a live malloced block. glibc often catches this one itself and aborts with free(): double free detected in tcache 2 or free(): invalid pointer.

How valgrind works

valgrind (the tool is called Memcheck; it is the default) does not need a special build. It loads your program and translates its machine code, on the fly, into instrumented code that runs on a simulated CPU. For every byte of memory it tracks two extra facts:

addressable? Is this byte part of a live allocation, a stack frame, or a global? Heap blocks get unaddressable "red zones" around them, and freed blocks are marked unaddressable and kept out of circulation for a while.
defined? Has this byte been written since it was allocated? (It tracks this per bit.)

It also replaces malloc and free with its own versions that record where every block was allocated. Every load and store is checked. The price is speed: programs run 10 to 50 times slower. Compile with -g so reports can show file names and line numbers, and -O0 so the lines match your source.

Reading the reports

Case 1, the off-by-one:

$ valgrind ./bugs 1
==10== Invalid write of size 4
==10==    at 0x1091DF: main (bugs.c:11)
==10==  Address 0x4a55054 is 0 bytes after a block of size 20 alloc'd
==10==    at 0x4844818: malloc (vg_replace_malloc.c:446)
==10==    by 0x1091BA: main (bugs.c:9)

Every report has the same structure. (The ==10== prefix is the process id, and the hex addresses differ from run to run; ignore them.)

What: Invalid write of size 4, a 4-byte store (an int) to a bad address.
Where: a stack trace, innermost first. main (bugs.c:11) is the line a[i] = i;.
Which memory: 0 bytes after a block of size 20. The address is just past the end of a 20-byte block. "N bytes before" means an underflow; "inside a block ... free'd" means use-after-free.
Its history: where the block was allocated (bugs.c:9) and, for freed blocks, where it was freed.

Case 2, use after free:

==12== Invalid read of size 1
==12==    at 0x10922A: main (bugs.c:17)
==12==  Address 0x4a55040 is 0 bytes inside a block of size 16 free'd
==12==    at 0x484787F: free (vg_replace_malloc.c:989)
==12==    by 0x109225: main (bugs.c:16)
==12==  Block was alloc'd at
==12==    at 0x4844818: malloc (vg_replace_malloc.c:446)
==12==    by 0x10920B: main (bugs.c:14)

Three stack traces: the bad read, the free, and the original malloc. That is usually enough to see the whole story.

Case 3, uninitialized value:

==14== Conditional jump or move depends on uninitialised value(s)
==14==    at 0x109265: main (bugs.c:20)
==14==
==14== Use --track-origins=yes to see where uninitialised values come from

valgrind does not complain when you copy uninitialized bytes around (programs do that legitimately all the time, for example copying a struct with padding). It complains when the value is used to make a decision or passed to a system call. Rerun with --track-origins=yes and it adds where the memory came from.

Case 4, the leak. Leaks are reported at exit, and you need --leak-check=full to see where each leaked block was allocated:

==16== HEAP SUMMARY:
==16==     in use at exit: 100 bytes in 1 blocks
==16==   total heap usage: 2 allocs, 1 frees, 300 bytes allocated
==16==
==16== 100 bytes in 1 blocks are definitely lost in loss record 1 of 1
==16==    at 0x4844818: malloc (vg_replace_malloc.c:446)
==16==    by 0x109293: main (bugs.c:24)
==16==
==16== LEAK SUMMARY:
==16==    definitely lost: 100 bytes in 1 blocks
==16==    indirectly lost: 0 bytes in 0 blocks
==16==      possibly lost: 0 bytes in 0 blocks
==16==    still reachable: 0 bytes in 0 blocks

The trace shows where the leaked block was allocated, not where the pointer was lost. You then have to work out which path forgot to free it.

Using valgrind in scripts and tests

These options make valgrind useful as an automatic check, which is exactly how this track checks your exercises:

$ valgrind -q --error-exitcode=1 --leak-check=full ./prog < input.txt

-q prints only errors, not the banner and summaries.
--error-exitcode=1 makes valgrind exit with status 1 if it found any error, so scripts and make can detect it.
--leak-check=full reports each leak with its allocation trace, and counts definite leaks as errors.

Help from the compiler

gcc can spot some of these at compile time, when the bug is visible within one function. Building the catalog program with -Wall -Wextra gives:

bugs.c:20:13: warning: '*count' may be used uninitialized [-Wmaybe-uninitialized]
bugs.c:17:28: warning: pointer 'name' used after 'free' [-Wuse-after-free]

It caught two of the four, and only because each bug sat in one short block. Spread the same bugs over a few functions and the compiler sees nothing. The AddressSanitizer (gcc -fsanitize=address) is a second runtime tool that instruments code at compile time and runs much faster than valgrind; the debugging module covers it alongside gdb.

Common mistakes

Trusting a clean run. "It printed the right thing" says nothing about memory errors. Run valgrind on anything that allocates.
Fixing the reported line instead of the cause. The invalid write is where memory broke; the bug may be the size computation in the malloc call or a loop bound one line up.
Ignoring the first error. Like compiler errors, later valgrind reports can be consequences of the first one. Fix from the top.
Testing only small inputs. malloc(n) usually rounds up to a multiple of 16 bytes, so being one byte short often lands in harmless padding. valgrind catches it anyway; normal runs only fail with unlucky sizes.
Forgetting -g. Without debug info the traces show only addresses, such as at 0x1091DF: main (in /work/prog).

Recap

The five heap bugs: overflow, use after free, uninitialized read, leak, invalid or double free. Most do not crash where they happen.
valgrind runs your unmodified program on a simulated CPU, tracking which bytes are addressable and defined, and reports bad accesses with stack traces for the access, the free and the allocation.
Read reports as: what (read/write, size), where (trace), which memory (bytes before/after/inside a block), and its history.
valgrind -q --error-exitcode=1 --leak-check=full turns it into an automatic test.

Going further: valgrind --track-origins=yes ./prog for uninitialized values, and the Memcheck manual at man valgrind (search for "leak-check"). Try writing one more bug yourself, reading one int before the start of a block (a[-1]), and see how the report phrases it.

Exercises

Exercise 1 · quiz

What does this report mean?

valgrind prints:

==31== Invalid write of size 4
==31==    at 0x109199: fill (prog.c:12)
==31==    by 0x1091BE: main (prog.c:20)
==31==  Address 0x4a55068 is 0 bytes after a block of size 40 alloc'd
==31==    at 0x4844818: malloc (vg_replace_malloc.c:446)
==31==    by 0x109174: main (prog.c:18)

What is the most likely bug?

An int was written into memory that had already been freed
fill wrote one int just past the end of a 10-int array allocated in main, typically an off-by-one loop bound
main forgot to free a 40-byte block
fill read an uninitialized value

Answer

fill wrote one int just past the end of a 10-int array allocated in main, typically an off-by-one loop bound

"Invalid write of size 4" is a store of 4 bytes (an int). "0 bytes after a block of size 40" means the address is immediately past the end of a 40-byte block (10 ints), and the block was allocated in main at line 18. The write happened in fill at line 12, called from main line 20. Look at line 12 for <= where < was meant. A use-after-free would say "inside a block of size 40 free'd"; a leak appears in the HEAP SUMMARY, not as an invalid write.

Exercise 2 · quiz

Find the line

1  #include <stdio.h>
2  #include <stdlib.h>
3
4  int *make_range(int n)
5  {
6      int *r = malloc(n * sizeof *r);
7      for (int i = 1; i <= n; i++)
8          r[i] = i;
9      return r;
10 }
11
12 int main(void)
13 {
14     int *r = make_range(4);
15     printf("%d\n", r[1] + r[2] + r[3]);
16     free(r);
17     return 0;
18 }

The program prints 6 and exits normally, but valgrind reports Invalid write of size 4 ... at make_range (prog.c:8). Which line has to change to fix the bug? Answer with the line number.

Answer

Line 8 is where the bad write happens, but the mistake is the loop bound on line 7: it runs i from 1 to n inclusive, so the last iteration writes r[4] in a 4-element array. Either loop for (int i = 0; i < n; i++) r[i] = i + 1; or allocate n + 1 elements if index n is really wanted. valgrind tells you where memory went wrong; the cause is often a line or two earlier. Note that the program printed the right answer: heap overflows usually do not crash on the spot, which is exactly why a tool is needed.

Exercise 3 · write code

Make valgrind happy

This program reads words and prints each one in uppercase with an exclamation mark, then the number of words. Its output is correct, but valgrind reports an invalid write, an invalid read and a leak.

Fix all the memory errors without changing the output. The check runs the program under valgrind and fails on any error or leak. For input hi there the output is:

HI!
THERE!
2 words

File: main.c

Starting point

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

/* Returns an uppercase copy of s. The caller must free it. */
char *shout(const char *s)
{
    size_t n = strlen(s);
    char *out = malloc(n);
    if (out == NULL)
        return NULL;
    for (size_t i = 0; i <= n; i++)
        out[i] = (char)toupper((unsigned char)s[i]);
    return out;
}

int main(void)
{
    char word[64];
    int count = 0;
    while (scanf("%63s", word) == 1) {
        char *loud = shout(word);
        if (loud == NULL)
            return 1;
        printf("%s!\n", loud);
        count++;
    }
    printf("%d words\n", count);
    return 0;
}

Example

input

hi there

expected output

HI!
THERE!
2 words

Example

input

C is fun

expected output

C!
IS!
FUN!
3 words

Hint 1

The loop in shout copies n + 1 characters (including the '\0'). How many bytes did it allocate?

Hint 2

The comment says the caller must free the result. Does main ever do that?

Hint 3

Allocate n + 1 bytes, and call free(loud); after printing it.

Reference solution

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

/* Returns an uppercase copy of s. The caller must free it. */
char *shout(const char *s)
{
    size_t n = strlen(s);
    char *out = malloc(n + 1);
    if (out == NULL)
        return NULL;
    for (size_t i = 0; i <= n; i++)
        out[i] = (char)toupper((unsigned char)s[i]);
    return out;
}

int main(void)
{
    char word[64];
    int count = 0;
    while (scanf("%63s", word) == 1) {
        char *loud = shout(word);
        if (loud == NULL)
            return 1;
        printf("%s!\n", loud);
        free(loud);
        count++;
    }
    printf("%d words\n", count);
    return 0;
}

Exercise 4 · quiz

Kinds of leaks

At exit, valgrind says a block is definitely lost. What does that mean?

The block was freed twice
No pointer to the block exists anywhere in the program's memory any more, so it can never be freed
A global variable still points at the block, but nobody freed it before exit
The block was allocated by the C library, not by your code

Answer

No pointer to the block exists anywhere in the program's memory any more, so it can never be freed

At exit valgrind scans memory (globals, stacks, registers, other heap blocks) for pointers to each unfreed block. Definitely lost: no pointer found, a true leak. Indirectly lost: only reachable through another lost block (lose the head of a linked list and every node behind it is indirectly lost). Possibly lost: only a pointer into the middle was found. Still reachable: a pointer still exists, for example in a global, at exit; often harmless, but in a long-running program it may be memory that grows forever.