From Documentation
Revision as of 12:11, 8 September 2015 by Tyson (Talk | contribs) (Add directions on tracking down uninitialized values)

Jump to: navigation, search
VALGRIND
Description: Memory debugger
SHARCNET Package information: see VALGRIND software page in web portal
Full list of SHARCNET supported software


Valgrind is a powerful tool for analyzing programs, memory debugging, memory leak detection and profiling. It is freely available under GNU license. Version 3.5.0 is available on most SHARCNET systems.

NOTE To avoid spurious warnings it is important to not use too new of a version of GCC or OpenMPI. We recommend

  • gcc/4.8.2
  • openmpi/gcc-debug/1.8.1 modules

Overview

Valgrind is a dynamic binary instrumentation framework that dynamically translates executables to add instrumentation and track all memory and register usages by a program. The advantages of this approach are that

  • it can be directly run on any executable, and
  • dynamic translation allows ultimate instrumentation

while the disadvantages are

  • 5-100 x slow down depending on tool,
  • 12-18 x increase in size of translated code, and
  • corner cases may exist between translated code and original.

Several tools have been built upon this framework. These include

  • memcheck - memory error detector
  • cachegrind - cache and branch-prediction profiler
  • callgrind - call-graph generating cache and branch prediction profiler
  • helgrind - thread error detector
  • DRD - thread error detector
  • Massif - heap profiler
  • DHAT - dynamic heap analysis tool
  • SGCheck - experimental stack and global array overrun detector
  • BBV - experimental basic block vector generation tool

You are welcome to use any or all of these, but we have only used memcheck and cachegrind and only support memcheck.

Usage

The primary used tool is memcheck. This is the default tool and the only one we discuss here. Documentation for other tools can be found on the valgrind website. The memcheck tool detects several common memory errors

  • overrunning and underrunning heap blocks,
  • overrunning top of stack,
  • continuing to access released memory,
  • using uninitialized values,
  • incorrectly using memory copying routines,
  • incorrectly paired allocation/release calls,
  • relasing unallocated memory, and
  • not releasing memory.

We recommend running all new code under valgrind on small test cases (small due to the aforementioned ~10x slowdown). This can save hours and hours of debugging. Running the program under valgrind can be as simple as compiling with debugging information (adding the -g flag) and running as valgrind <program> <arguements>.

Serial code

Consider the following bug.c code

#include <stdio.h>
 
int main() {
  double array[10];
 
  // Execution depends on uninitialized value
  if (array[4] < 0.0)
    printf("the results is negative\n");
  else if (array[4] == 0.0)
    printf("the results is zero\n");
  else if (array[4] > 0.0)
    printf("the results is positive\n");
  else
    printf("the results are special\n");
 
  return 0;
}

It has an uninitialized value bug. Running this under valgrind

cc -Wall -g bug.c -o bug
valgrind ./bug

reports this

==5955== Conditional jump or move depends on uninitialised value(s)
==5955==    at 0x400511: main (bug.c:7)
==5955== 
==5955== Conditional jump or move depends on uninitialised value(s)
==5955==    at 0x40052C: main (bug.c:9)
==5955== 
==5955== Conditional jump or move depends on uninitialised value(s)
==5955==    at 0x400536: main (bug.c:9)
==5955== 
==5955== Conditional jump or move depends on uninitialised value(s)
==5955==    at 0x400551: main (bug.c:11)

Note that valgrind only reports uninitialized values usage once they lead to non-determinism (i.e., when the program encounters a branch whose choice depends on the result of an uninitiated value). This means you the first report you get is frequently not in the calculation done on the uninitialized values but rather the convergence test or print statement at the end of calculations (print statements contains a bunch of branches in order to handling printing of each different digit).

Tracking down uninitialized values

More typically a program will be composed of multiple routines that all work on the data. To this end, consider the following bug.c code

#include <stdio.h>
 
void initialize_sequence(double* array, const int array_length) {
  int i;
 
  for (i=1; i<array_length+1; ++i)
    array[i] = i;
}
 
double sum(const double* array, const int array_length) {
  double array_sum;
  int i;
 
  for (i=0; i<array_length; ++i)
    array_sum += array[i];
 
  return array_sum;
}
 
int main() {
  double array[10];
  const int array_length = sizeof(array)/sizeof(array[0]);
 
  double array_sum;
 
  initialize_sequence(array,array_length);
  array_sum = sum(array,array_length);
 
  printf("the sum of 0..%d is %f\n", array_length-1, array_sum);
 
  return 0;
}

It has both indexing and uninitialized value bugs. Despite this, directly running the code

cc -Wall -g bug.c -o bug
./bug

will mostly likely produce the correct answer on most machines most of the time

the sum of 0..9 is 45.000000

Running under valgrind

valgrind ./bug

however, reliably gives many warnings of the following form

==15930== Conditional jump or move depends on uninitialised value(s)
==15930==    at 0x5312CF0: __printf_fp (in /lib64/libc-2.12.so)
==15930==    by 0x530E89F: vfprintf (in /lib64/libc-2.12.so)
==15930==    by 0x5318189: printf (in /lib64/libc-2.12.so)
==15930==    by 0x400722: main (bug.c:29)

This is a typical numeric code example were the warnings first occur at a print statement because this is the first time the uninitialized value leads to non-determinism (i.e., the program's behaviour is altered as it takes or does not take a branch based on a result computed from something that was not set by the programmer).

We now know the problem is that something unset went into computing the value of array_sum. We can then trace each of the array_sum calculation backwards. This quickly gets difficult though as we then find ourselves also tracing back all variables that went into the array_sum calculation, and then all variables that went into those variables and so on.

Fortunately Valgrind provides a --track-origins=yes flag to ease our search by telling us which ones we can ignore. Re-running with this flag

valgrind --track-origins=yes ./bug

our warnings messages are augmented to include information on the source of the uninitialized value that went into the computation of array_sum

==17589== Conditional jump or move depends on uninitialised value(s)
==17589==    at 0x5312CF0: __printf_fp (in /lib64/libc-2.12.so)
==17589==    by 0x530E89F: vfprintf (in /lib64/libc-2.12.so)
==17589==    by 0x5318189: printf (in /lib64/libc-2.12.so)
==17589==    by 0x400722: main (bug.c:29)
==17589==  Uninitialised value was created by a stack allocation
==17589==    at 0x400632: sum (bug.c:10)

Now we know the source of our uninitialized value in the array_sum computation is a local variable in the sum routine. Looking into sum we hopefully figure out without too much difficulty that we forgot to initialize array_sum to zero. If our program is producing the correct answer, it is only because we are getting lucky and array_sum happens to be allocated from memory that is initially zero.

Correcting the sum routine

double sum(const double* array, const int array_length) {
  double array_sum;
  int i;
 
  array_sum = 0.0;
  for (i=0; i<array_length; ++i)
    array_sum += array[i];
 
  return array_sum;
}

and re-running under valgrind reveals we are still getting uninitialized values warnings associated with the array_sum computation. Now (using the --track-origins=yes) they are of the form

==18613== Conditional jump or move depends on uninitialised value(s)
==18613==    at 0x5312CF0: __printf_fp (in /lib64/libc-2.12.so)
==18613==    by 0x530E89F: vfprintf (in /lib64/libc-2.12.so)
==18613==    by 0x5318189: printf (in /lib64/libc-2.12.so)
==18613==    by 0x40072C: main (bug.c:30)
==18613==  Uninitialised value was created by a stack allocation
==18613==    at 0x400690: main (bug.c:21)

Valgrind is telling us that a local variable inside the main went into the computation of array_sum despite never being set. This means it must be array itself or array_length. It cannot be array_length as the former is clearly set to the compiler computed sizeof(array)/sizeof(array[0]) so it must be array itself.

It is clear the intent of the code is that array is initialized by the initialize_sequence routine. Careful examination of this routine reveals the final error. The initialization loop was done using Fortran indices (1...array_length) instead of C (0...array_length-1). Correcting this routine

void initialize_sequence(double* array, const int array_length) {
  int i;
 
  for (i=0; i<array_length; ++i)
    array[i] = i;
}

finally produces code the runs under valgrind without any warnings.

NOTE The Valgrind warnings were being generated because the array[0] value was not being initialized. The code was also incorrect in that it was initializing array[array_length] which is one past the end of array. If you put this later error back into the program and run under Valgrind you will discover it does not produce any warnings. This shows that even codes that successfully under Valgrind can still contain errors.

MPI code

Consider the following bug.c MPI code

#include <mpi.h>
 
int main(int argc,char *argv[]){
  int rank, size;
  int value;
 
  MPI_Init(&argc, &argv);
 
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  MPI_Comm_size(MPI_COMM_WORLD, &size);
 
  if (rank == 0 && size > 1) {
    MPI_Request request;
 
    MPI_Irecv(&value, 1, MPI_INT, 1, 0, MPI_COMM_WORLD, &request);
    value = 0;
    MPI_Wait (&request, MPI_STATUS_IGNORE);
  }
  else if (rank == 1) {
    MPI_Request request;
 
    MPI_Isend(&value, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &request);
    value = 1;
    MPI_Wait(&request, MPI_STATUS_IGNORE);
  } 
 
  MPI_Finalize();
 
  return 0;
}

It has an uninitialized value bug and two race condition bugs around the use of value.

  1. The first race condition is that rank==0 sets value=0 while at the same time doing a non-blocking receive into value (bug:16).
  2. The uninitialized value problem is that rank==1 starts a send of value to rank==0 without ever setting value (bug:22).
  3. The second race condition is that rank==1 sets value=1 while at the same time doing a non-blocking send of value (bug:23).

Basic Functionality

If you run this using the non-debug/valgrind openmpi valgrind

module unload intel openmpi
module load intel/12.1.3 openmpi/intel/1.6.2
mpicc -Wall -g bug.c -o bug
mpirun -np 2 valgrind ./bug

you are presumably getting a report about the uninitialized value, but it is burried in 55517 other bogus error messages.

This solution to this is to link against the valgrind openmpi debug wrapper library too.

mpicc -Wall -g bug.c -L/usr/lib64/valgrind -lmpiwrap-amd64-linux -Xlinker -rpath=/usr/lib64/valgrind -o bug
mpirun -np 2 valgrind ./bug

This now only reports one bogus error (a free on exit) and picks up the sending of the uninitialized value

==27638== Uninitialised byte(s) found during client check request
==27638==    at 0x4E3641D: check_mem_is_defined_untyped (libmpiwrap.c:952)
==27638==    by 0x4E5BBC5: generic_Isend (libmpiwrap.c:908)
==27638==    by 0x4E5BEE9: PMPI_Isend (libmpiwrap.c:1393)
==27638==    by 0x402713: main (bug.c:22)
==27638==  Address 0x7fefff734 is on thread 1's stack

Advanced Functionality

Now, if on top of this, you also bring in the valgrind enabled openmpi debug library, things get really sweet

module unload intel openmpi
module load intel/12.1.3 openmpi/intel-debug/1.6.2
mpicc -Wall -g bug.c -o bug
LD_PRELOAD=/usr/lib64/valgrind/libmpiwrap-amd64-linux.so mpirun -np 2 valgrind ./bug

You still only get one bogus error (a free on exit) and all the bugs in the code are detected and reported

==27774== Uninitialised byte(s) found during client check request
==27774==    at 0x4E3641D: check_mem_is_defined_untyped (libmpiwrap.c:952)
==27774==    by 0x4E5BBC5: generic_Isend (libmpiwrap.c:908)
==27774==    by 0x4E5BEE9: PMPI_Isend (libmpiwrap.c:1393)
==27774==    by 0x402713: main (bug.c:22)
==27774==  Address 0x7fefff6f4 is on thread 1's stack

==27773== Invalid write of size 4
==27773==    at 0x4026A0: main (bug.c:16)
==27773==  Address 0x7fefff6f4 is on thread 1's stack

==27774== Invalid write of size 4
==27774==    at 0x40271B: main (bug.c:23)
==27774==  Address 0x7fefff6f4 is on thread 1's stack

Suppression File

There is also a valgrind suppression option --suppressions=/opt/sharcnet/openmpi/1.6.2/intel-debug/share/openmpi/openmpi-valgrind.supp, however we have not observed any cases where this makes a difference yet.

References

o Package website
http://www.valgrind.org