3  Memcheck: a heavyweight memory checker

To use this tool, you must specify --tool=memcheck on the Valgrind command line.

3.1  Kinds of bugs that memcheck can find

Memcheck is Valgrind-1.0.X's checking mechanism bundled up into a tool. All reads and writes of memory are checked, and calls to malloc/new/free/delete are intercepted. As a result, memcheck can detect the following problems:

3.2  Command-line flags specific to memcheck

3.3  Explanation of error messages from Memcheck

Despite considerable sophistication under the hood, Memcheck can only really detect two kinds of errors, use of illegal addresses, and use of undefined values. Nevertheless, this is enough to help you discover all sorts of memory-management nasties in your code. This section presents a quick summary of what error messages mean. The precise behaviour of the error-checking machinery is described in this section.

3.3.1  Illegal read / Illegal write errors

For example: 
  Invalid read of size 4
     at 0x40F6BBCC: (within /usr/lib/libpng.so.2.1.0.9)
     by 0x40F6B804: (within /usr/lib/libpng.so.2.1.0.9)
     by 0x40B07FF4: read_png_image__FP8QImageIO (kernel/qpngio.cpp:326)
     by 0x40AC751B: QImageIO::read() (kernel/qimage.cpp:3621)
   Address 0xBFFFF0E0 is not stack'd, malloc'd or free'd

This happens when your program reads or writes memory at a place which Memcheck reckons it shouldn't. In this example, the program did a 4-byte read at address 0xBFFFF0E0, somewhere within the system-supplied library libpng.so.2.1.0.9, which was called from somewhere else in the same library, called from line 326 of qpngio.cpp, and so on.

Memcheck tries to establish what the illegal address might relate to, since that's often useful. So, if it points into a block of memory which has already been freed, you'll be informed of this, and also where the block was free'd at. Likewise, if it should turn out to be just off the end of a malloc'd block, a common result of off-by-one-errors in array subscripting, you'll be informed of this fact, and also where the block was malloc'd.

In this example, Memcheck can't identify the address. Actually the address is on the stack, but, for some reason, this is not a valid stack address -- it is below the stack pointer, %esp, and that isn't allowed. In this particular case it's probably caused by gcc generating invalid code, a known bug in various flavours of gcc.

Note that Memcheck only tells you that your program is about to access memory at an illegal address. It can't stop the access from happening. So, if your program makes an access which normally would result in a segmentation fault, you program will still suffer the same fate -- but you will get a message from Memcheck immediately prior to this. In this particular example, reading junk on the stack is non-fatal, and the program stays alive.

3.3.2  Use of uninitialised values

For example: 
  Conditional jump or move depends on uninitialised value(s)
     at 0x402DFA94: _IO_vfprintf (_itoa.h:49)
     by 0x402E8476: _IO_printf (printf.c:36)
     by 0x8048472: main (tests/manuel1.c:8)
     by 0x402A6E5E: __libc_start_main (libc-start.c:129)

An uninitialised-value use error is reported when your program uses a value which hasn't been initialised -- in other words, is undefined. Here, the undefined value is used somewhere inside the printf() machinery of the C library. This error was reported when running the following small program: 

  int main()
  {
    int x;
    printf ("x = %d\n", x);
  }

It is important to understand that your program can copy around junk (uninitialised) data to its heart's content. Memcheck observes this and keeps track of the data, but does not complain. A complaint is issued only when your program attempts to make use of uninitialised data. In this example, x is uninitialised. Memcheck observes the value being passed to _IO_printf and thence to _IO_vfprintf, but makes no comment. However, _IO_vfprintf has to examine the value of x so it can turn it into the corresponding ASCII string, and it is at this point that Memcheck complains.

Sources of uninitialised data tend to be:

3.3.3  Illegal frees

For example: 
  Invalid free()
     at 0x4004FFDF: free (vg_clientmalloc.c:577)
     by 0x80484C7: main (tests/doublefree.c:10)
     by 0x402A6E5E: __libc_start_main (libc-start.c:129)
     by 0x80483B1: (within tests/doublefree)
   Address 0x3807F7B4 is 0 bytes inside a block of size 177 free'd
     at 0x4004FFDF: free (vg_clientmalloc.c:577)
     by 0x80484C7: main (tests/doublefree.c:10)
     by 0x402A6E5E: __libc_start_main (libc-start.c:129)
     by 0x80483B1: (within tests/doublefree)

Memcheck keeps track of the blocks allocated by your program with malloc/new, so it can know exactly whether or not the argument to free/delete is legitimate or not. Here, this test program has freed the same block twice. As with the illegal read/write errors, Memcheck attempts to make sense of the address free'd. If, as here, the address is one which has previously been freed, you wil be told that -- making duplicate frees of the same block easy to spot.

3.3.4  When a block is freed with an inappropriate deallocation function

In the following example, a block allocated with new[] has wrongly been deallocated with free: 
  Mismatched free() / delete / delete []
     at 0x40043249: free (vg_clientfuncs.c:171)
     by 0x4102BB4E: QGArray::~QGArray(void) (tools/qgarray.cpp:149)
     by 0x4C261C41: PptDoc::~PptDoc(void) (include/qmemarray.h:60)
     by 0x4C261F0E: PptXml::~PptXml(void) (pptxml.cc:44)
   Address 0x4BB292A8 is 0 bytes inside a block of size 64 alloc'd
     at 0x4004318C: __builtin_vec_new (vg_clientfuncs.c:152)
     by 0x4C21BC15: KLaola::readSBStream(int) const (klaola.cc:314)
     by 0x4C21C155: KLaola::stream(KLaola::OLENode const *) (klaola.cc:416)
     by 0x4C21788F: OLEFilter::convert(QCString const &) (olefilter.cc:272)
The following was told to me be the KDE 3 developers. I didn't know any of it myself. They also implemented the check itself.

In C++ it's important to deallocate memory in a way compatible with how it was allocated. The deal is:

The worst thing is that on Linux apparently it doesn't matter if you do muddle these up, and it all seems to work ok, but the same program may then crash on a different platform, Solaris for example. So it's best to fix it properly. According to the KDE folks "it's amazing how many C++ programmers don't know this".

Pascal Massimino adds the following clarification: delete[] must be called associated with a new[] because the compiler stores the size of the array and the pointer-to-member to the destructor of the array's content just before the pointer actually returned. This implies a variable-sized overhead in what's returned by new or new[]. It rather surprising how compilers [Ed: runtime-support libraries?] are robust to mismatch in new/delete new[]/delete[].

3.3.5  Passing system call parameters with inadequate read/write permissions

Memcheck checks all parameters to system calls, i.e: After the system call, Memcheck updates its administrative information to precisely reflect any changes in memory permissions caused by the system call.

Here's an example of two system calls with invalid parameters: 

  #include <stdlib.h>
  #include <unistd.h>
  int main( void )
  {
    char* arr  = malloc(10);
    int*  arr2 = malloc(sizeof(int));
    write( 1 /* stdout */, arr, 10 );
    exit(arr2[0]);
  }

You get these complaints ... 

  Syscall param write(buf) points to uninitialised byte(s)
     at 0x25A48723: __write_nocancel (in /lib/tls/libc-2.3.3.so)
     by 0x259AFAD3: __libc_start_main (in /lib/tls/libc-2.3.3.so)
     by 0x8048348: (within /auto/homes/njn25/grind/head4/a.out)
   Address 0x25AB8028 is 0 bytes inside a block of size 10 alloc'd
     at 0x259852B0: malloc (vg_replace_malloc.c:130)
     by 0x80483F1: main (a.c:5)
  
  Syscall param exit(error_code) contains uninitialised byte(s)
     at 0x25A21B44: __GI__exit (in /lib/tls/libc-2.3.3.so)
     by 0x8048426: main (a.c:8)

... because the program has (a) tried to write uninitialised junk from the malloc'd block to the standard output, and (b) passed an uninitialised value to exit. Note that the first error refers to the memory pointed to by buf (not buf itself), but the second error refers to the argument error_code itself.

3.3.6  Overlapping source and destination blocks

The following C library functions copy some data from one memory block to another (or something similar): memcpy(), strcpy(), strncpy(), strcat(), strncat(). The blocks pointed to by their src and dst pointers aren't allowed to overlap. Memcheck checks for this.

For example: 

==27492== Source and destination overlap in memcpy(0xbffff294, 0xbffff280, 21)
==27492==    at 0x40026CDC: memcpy (mc_replace_strmem.c:71)
==27492==    by 0x804865A: main (overlap.c:40)
==27492==    by 0x40246335: __libc_start_main (../sysdeps/generic/libc-start.c:129)
==27492==    by 0x8048470: (within /auto/homes/njn25/grind/head6/memcheck/tests/overlap)
==27492==

You don't want the two blocks to overlap because one of them could get partially trashed by the copying.

3.4  Writing suppressions files

The basic suppression format was described in this section.

The suppression (2nd) line should have the form: 

Memcheck:suppression_type
Or, since some of the suppressions are shared with Addrcheck: 
Memcheck,Addrcheck:suppression_type

The Memcheck suppression types are as follows: Value1, Value2, Value4, Value8, Value16, meaning an uninitialised-value error when using a value of 1, 2, 4, 8 or 16 bytes. Or Cond (or its old name, Value0), meaning use of an uninitialised CPU condition code. Or: Addr1, Addr2, Addr4, Addr8, Addr16, meaning an invalid address during a memory access of 1, 2, 4, 8 or 16 bytes respectively. Or Param, meaning an invalid system call parameter error. Or Free, meaning an invalid or mismatching free. Overlap, meaning a src/dst overlap in memcpy() or a similar function. Last but not least, you can suppress leak reports with Leak. Leak suppression was added in valgrind-1.9.3, I believe.

The extra information line: for Param errors, is the name of the offending system call parameter. No other error kinds have this extra line.

The first line of the calling context: for Value and Addr errors, it is either the name of the function in which the error occurred, or, failing that, the full path of the .so file or executable containing the error location. For Free errors, is the name of the function doing the freeing (eg, free, __builtin_vec_delete, etc). For Overlap errors, is the name of the function with the overlapping arguments (eg. memcpy(), strcpy(), etc).

Lastly, there's the rest of the calling context.

3.5  Details of Memcheck's checking machinery

Read this section if you want to know, in detail, exactly what and how Memcheck is checking.

3.5.1  Valid-value (V) bits

It is simplest to think of Memcheck implementing a synthetic Intel x86 CPU which is identical to a real CPU, except for one crucial detail. Every bit (literally) of data processed, stored and handled by the real CPU has, in the synthetic CPU, an associated "valid-value" bit, which says whether or not the accompanying bit has a legitimate value. In the discussions which follow, this bit is referred to as the V (valid-value) bit.

Each byte in the system therefore has a 8 V bits which follow it wherever it goes. For example, when the CPU loads a word-size item (4 bytes) from memory, it also loads the corresponding 32 V bits from a bitmap which stores the V bits for the process' entire address space. If the CPU should later write the whole or some part of that value to memory at a different address, the relevant V bits will be stored back in the V-bit bitmap.

In short, each bit in the system has an associated V bit, which follows it around everywhere, even inside the CPU. Yes, the CPU's (integer and %eflags) registers have their own V bit vectors.

Copying values around does not cause Memcheck to check for, or report on, errors. However, when a value is used in a way which might conceivably affect the outcome of your program's computation, the associated V bits are immediately checked. If any of these indicate that the value is undefined, an error is reported.

Here's an (admittedly nonsensical) example: 

  int i, j;
  int a[10], b[10];
  for (i = 0; i < 10; i++) {
    j = a[i];
    b[i] = j;
  }

Memcheck emits no complaints about this, since it merely copies uninitialised values from a[] into b[], and doesn't use them in any way. However, if the loop is changed to 

  for (i = 0; i < 10; i++) {
    j += a[i];
  }
  if (j == 77) 
     printf("hello there\n");
then Valgrind will complain, at the if, that the condition depends on uninitialised values. Note that it doesn't complain at the j += a[i];, since at that point the undefinedness is not "observable". It's only when a decision has to be made as to whether or not to do the printf -- an observable action of your program -- that Memcheck complains.

Most low level operations, such as adds, cause Memcheck to use the V bits for the operands to calculate the V bits for the result. Even if the result is partially or wholly undefined, it does not complain.

Checks on definedness only occur in two places: when a value is used to generate a memory address, and where control flow decision needs to be made. Also, when a system call is detected, valgrind checks definedness of parameters as required.

If a check should detect undefinedness, an error message is issued. The resulting value is subsequently regarded as well-defined. To do otherwise would give long chains of error messages. In effect, we say that undefined values are non-infectious.

This sounds overcomplicated. Why not just check all reads from memory, and complain if an undefined value is loaded into a CPU register? Well, that doesn't work well, because perfectly legitimate C programs routinely copy uninitialised values around in memory, and we don't want endless complaints about that. Here's the canonical example. Consider a struct like this: 

  struct S { int x; char c; };
  struct S s1, s2;
  s1.x = 42;
  s1.c = 'z';
  s2 = s1;

The question to ask is: how large is struct S, in bytes? An int is 4 bytes and a char one byte, so perhaps a struct S occupies 5 bytes? Wrong. All (non-toy) compilers we know of will round the size of struct S up to a whole number of words, in this case 8 bytes. Not doing this forces compilers to generate truly appalling code for subscripting arrays of struct S's.

So s1 occupies 8 bytes, yet only 5 of them will be initialised. For the assignment s2 = s1, gcc generates code to copy all 8 bytes wholesale into s2 without regard for their meaning. If Memcheck simply checked values as they came out of memory, it would yelp every time a structure assignment like this happened. So the more complicated semantics described above is necessary. This allows gcc to copy s1 into s2 any way it likes, and a warning will only be emitted if the uninitialised values are later used.

One final twist to this story. The above scheme allows garbage to pass through the CPU's integer registers without complaint. It does this by giving the integer registers V tags, passing these around in the expected way. This complicated and computationally expensive to do, but is necessary. Memcheck is more simplistic about floating-point loads and stores. In particular, V bits for data read as a result of floating-point loads are checked at the load instruction. So if your program uses the floating-point registers to do memory-to-memory copies, you will get complaints about uninitialised values. Fortunately, I have not yet encountered a program which (ab)uses the floating-point registers in this way.

3.5.2  Valid-address (A) bits

Notice that the previous subsection describes how the validity of values is established and maintained without having to say whether the program does or does not have the right to access any particular memory location. We now consider the latter issue.

As described above, every bit in memory or in the CPU has an associated valid-value (V) bit. In addition, all bytes in memory, but not in the CPU, have an associated valid-address (A) bit. This indicates whether or not the program can legitimately read or write that location. It does not give any indication of the validity or the data at that location -- that's the job of the V bits -- only whether or not the location may be accessed.

Every time your program reads or writes memory, Memcheck checks the A bits associated with the address. If any of them indicate an invalid address, an error is emitted. Note that the reads and writes themselves do not change the A bits, only consult them.

So how do the A bits get set/cleared? Like this:

3.5.3  Putting it all together

Memcheck's checking machinery can be summarised as follows: Memcheck intercepts calls to malloc, calloc, realloc, valloc, memalign, free, new and delete. The behaviour you get is:

3.6  Memory leak detection

Memcheck keeps track of all memory blocks issued in response to calls to malloc/calloc/realloc/new. So when the program exits, it knows which blocks are still outstanding -- have not been returned, in other words. Ideally, you want your program to have no blocks still in use at exit. But many programs do.

Technically, a leak is any allocated memory which won't be used again. Since Valgrind can't predict the future, it defines a leak as memory which has no pointers to it. Your program can't ever use such memory.

To find leaked blocks, Valgrind finds all the blocks which have not been leaked, by searching for pointers to them. Starting from the "root set" (static data, thread stacks and registers), it finds each immediately pointed-to block, and from those all the other blocks on the heap.

Once it has found all the unleaked blocks, the remaining blocks must be leaked. Rather than reporting on every single leaked block individually, it groups them into clusters of leaked blocks: leaked blocks which point to other leaked blocks. The blocks which it reports are the "heads" of each leaked cluster. There are two kinds of references to a block in memory:

Memcheck reports summaries about leaked and dubious blocks. For each such block, it will also tell you where the block was allocated. This should help you figure out why the pointer to it has been lost. In general, you should attempt to ensure your programs do not have any leaked or dubious blocks at exit.

The precise areas in which Memcheck searches for pointers in the root set are:

Within these areas, and within the heap, it inspects each naturally-aligned 4-byte word for which all A bits indicate addressibility and all V bits indicated that the stored value is actually valid, and checks to see if it is a valid heap pointer.

3.7  Client Requests

The following client requests are defined in memcheck.h. They also work for Addrcheck. See memcheck.h for exact details of their arguments.