CODEWITHSUNDEEP
c++memoryvalgrind
Lance Strait
Lance Strait

Reputation: 4261

Interpreting Valgrind Output C++

I am attempting to debug some graph generation code provided from http://www.cs.cmu.edu/~pbbs/benchmarks/maximalIndependentSet.html.

The code works fine for graphs up to a size of about 20,000,000 nodes, after that I get a segmentation fault. I've been trying to debug this issue with Valgrind, but am having trouble interpreting the output it gives me as I have little experience with Valgrind (nor am I an expert with C++).

Below is the Valgrind output and the relevant sections of the C++ code, I would appreciate any advice in looking into how to go about solving this issue. The machine I am SSHing into is very powerful, and I shouldn't be running out of memory attempting to make graphs of size 50,000,000.

[lstrait2@i2pc3 graphData]$ cat valgrind.txt
==56442== Memcheck, a memory error detector
==56442== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==56442== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==56442== Command: ./randLocalGraph -j -d 3 -m 250000000 50000000 ran50mil.txt
==56442== 
--56442-- Valgrind options:
--56442--    -v
--56442-- Contents of /proc/version:
--56442--   Linux version 2.6.32-504.3.3.el6.x86_64 ([email protected]) (gcc version 4.4.7 20120313 (Red Hat 4.4.7-11) (GCC) ) #1 SMP Tue Dec 16 14:29:22 CST 2014
--56442-- Arch and hwcaps: AMD64, amd64-sse3-cx16
--56442-- Page sizes: currently 4096, max supported 4096
--56442-- Valgrind library directory: /usr/lib64/valgrind
--56442-- Reading syms from /home/lstrait2/twe/Benchmarks/MIS/graphData/randLocalGraph
--56442-- Reading syms from /usr/lib64/valgrind/memcheck-amd64-linux
--56442--    object doesn't have a dynamic symbol table
--56442-- Reading syms from /lib64/ld-2.12.so
--56442-- Scheduler: using generic scheduler lock implementation.
--56442-- Reading suppressions file: /usr/lib64/valgrind/default.supp
==56442== embedded gdbserver: reading from /tmp/vgdb-pipe-from-vgdb-to-56442-by-lstrait2-on-i2pc3.cs.illinois.edu
==56442== embedded gdbserver: writing to   /tmp/vgdb-pipe-to-vgdb-from-56442-by-lstrait2-on-i2pc3.cs.illinois.edu
==56442== embedded gdbserver: shared mem   /tmp/vgdb-pipe-shared-mem-vgdb-56442-by-lstrait2-on-i2pc3.cs.illinois.edu
==56442== 
==56442== TO CONTROL THIS PROCESS USING vgdb (which you probably
==56442== don't want to do, unless you know exactly what you're doing,
==56442== or are doing some strange experiment):
==56442==   /usr/lib64/valgrind/../../bin/vgdb --pid=56442 ...command...
==56442== 
==56442== TO DEBUG THIS PROCESS USING GDB: start GDB like this
==56442==   /path/to/gdb ./randLocalGraph
==56442== and then give GDB the following command
==56442==   target remote | /usr/lib64/valgrind/../../bin/vgdb --pid=56442
==56442== --pid is optional if only one valgrind process is running
==56442== 
--56442-- REDIR: 0x3afa2176d0 (strlen) redirected to 0x38049551 (vgPlain_amd64_linux_REDIR_FOR_strlen)
--56442-- Reading syms from /usr/lib64/valgrind/vgpreload_core-amd64-linux.so
--56442-- Reading syms from /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so
--56442-- REDIR: 0x3afa2174e0 (index) redirected to 0x4a07c30 (index)
--56442-- REDIR: 0x3afa217560 (strcmp) redirected to 0x4a08570 (strcmp)
--56442-- Reading syms from /usr/lib64/libstdc++.so.6.0.18
--56442-- Reading syms from /lib64/libm-2.12.so
--56442-- Reading syms from /lib64/libgcc_s-4.4.7-20120601.so.1
--56442--    object doesn't have a symbol table
--56442-- Reading syms from /lib64/libc-2.12.so
--56442-- REDIR: 0x3afa684cd0 (strcasecmp) redirected to 0x480155c (_vgnU_ifunc_wrapper)
--56442-- REDIR: 0x3afa686f90 (strncasecmp) redirected to 0x480155c (_vgnU_ifunc_wrapper)
--56442-- REDIR: 0x3afa682c40 (__GI_strrchr) redirected to 0x4a07ab0 (__GI_strrchr)
--56442-- REDIR: 0x3afa681160 (__GI_strlen) redirected to 0x4a07fb0 (__GI_strlen)
--56442-- REDIR: 0x3afa67f6e0 (strcmp) redirected to 0x480155c (_vgnU_ifunc_wrapper)
--56442-- REDIR: 0x3afa728350 (__strcmp_sse42) redirected to 0x4a084d0 (strcmp)
--56442-- REDIR: 0x3afa6780b0 (mallopt) redirected to 0x4a04dc8 (mallopt)
--56442-- REDIR: 0x3afa681120 (strlen) redirected to 0x480155c (_vgnU_ifunc_wrapper)
--56442-- REDIR: 0x3afa733620 (__strlen_sse42) redirected to 0x4a07f90 (strlen)
--56442-- REDIR: 0x3affa5e2e0 (operator new(unsigned long)) redirected to 0x4a0757a (operator new(unsigned long))
--56442-- REDIR: 0x3afa689670 (memcpy) redirected to 0x4a08b60 (memcpy)
--56442-- REDIR: 0x3afa6833d0 (bcmp) redirected to 0x480155c (_vgnU_ifunc_wrapper)
--56442-- REDIR: 0x3afa73e6d0 (__memcmp_sse4_1) redirected to 0x4a09670 (bcmp)
--56442-- REDIR: 0x3affa5c570 (operator delete(void*)) redirected to 0x4a05f8f (operator delete(void*))
--56442-- REDIR: 0x3afa67a640 (malloc) redirected to 0x4a069ac (malloc)
==56442== Warning: set address range perms: large range [0x3aeed040, 0xb2246440) (undefined)
==56442== Warning: set address range perms: large range [0xb2247040, 0x1a08f9840) (undefined)
--56442-- REDIR: 0x3afa67b520 (free) redirected to 0x4a063a9 (free)
==56442== Warning: set address range perms: large range [0x1a08fa040, 0x28efac840) (undefined)
==56442== Warning: set address range perms: large range [0x49ad82040, 0x69ad82040) (undefined)
==56442== Warning: set address range perms: large range [0x28efad040, 0x2cefad040) (undefined)
==56442== Warning: set address range perms: large range [0x2cefae040, 0x3b91bdc80) (undefined)
==56442== Warning: set address range perms: large range [0x28efad028, 0x2cefad058) (noaccess)
==56442== Warning: set address range perms: large range [0x49ad82028, 0x69ad82058) (noaccess)
==56442== Warning: set address range perms: large range [0x1a08fa028, 0x28efac858) (noaccess)
==56442== Invalid write of size 8
==56442==    at 0x407260: edgeArray<int> makeSymmetric<int>(edgeArray<int>) (in /home/lstrait2/twe/Benchmarks/MIS/graphData/randLocalGraph)
==56442==    by 0x407716: main (in /home/lstrait2/twe/Benchmarks/MIS/graphData/randLocalGraph)
==56442==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==56442== 
==56442== 
==56442== Process terminating with default action of signal 11 (SIGSEGV)
==56442==  Access not within mapped region at address 0x0
==56442==    at 0x407260: edgeArray<int> makeSymmetric<int>(edgeArray<int>) (in /home/lstrait2/twe/Benchmarks/MIS/graphData/randLocalGraph)
==56442==    by 0x407716: main (in /home/lstrait2/twe/Benchmarks/MIS/graphData/randLocalGraph)
==56442==  If you believe this happened as a result of a stack
==56442==  overflow in your program's main thread (unlikely but
==56442==  possible), you can try to increase the size of the
==56442==  main thread stack using the --main-stacksize= flag.
==56442==  The main thread stack size used in this run was 10485760.
==56442== 
==56442== HEAP SUMMARY:
==56442==     in use at exit: 9,928,030,497 bytes in 8 blocks
==56442==   total heap usage: 34 allocs, 26 frees, 23,846,394,584 bytes allocated
==56442== 
==56442== Searching for pointers to 8 not-freed blocks
==56442== Checked 9,928,211,840 bytes
==56442== 
==56442== LEAK SUMMARY:
==56442==    definitely lost: 0 bytes in 0 blocks
==56442==    indirectly lost: 0 bytes in 0 blocks
==56442==      possibly lost: 7,928,030,497 bytes in 7 blocks
==56442==    still reachable: 2,000,000,000 bytes in 1 blocks
==56442==         suppressed: 0 bytes in 0 blocks
==56442== Rerun with --leak-check=full to see details of leaked memory
==56442== 
==56442== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 6 from 6)
==56442== 
==56442== 1 errors in context 1 of 1:
==56442== Invalid write of size 8
==56442==    at 0x407260: edgeArray<int> makeSymmetric<int>(edgeArray<int>) (in /home/lstrait2/twe/Benchmarks/MIS/graphData/randLocalGraph)
==56442==    by 0x407716: main (in /home/lstrait2/twe/Benchmarks/MIS/graphData/randLocalGraph)
==56442==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==56442== 
--56442-- 
--56442-- used_suppression:      4 U1004-ARM-_dl_relocate_object
--56442-- used_suppression:      2 glibc-2.5.x-on-SUSE-10.2-(PPC)-2a
==56442== 
==56442== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 6 from 6)

and then the relevent C++ code:

template <class intT>
edgeArray<intT> edgeRandomWithDimension(intT dim, intT degree, intT numRows) {
  intT nonZeros = numRows*degree;
  edge<intT> *E = newA(edge<intT>,nonZeros);
  parallel_for (intT k=0; k < nonZeros; k++) {
    intT i = k / degree;
    intT j;
    if (dim==0) {
      intT h = k;
      do {
    j = ((h = dataGen::hash<intT>(h)) % numRows);
      } while (j == i);
    } else {
      intT pow = dim+2;
      intT h = k;
      do {
    while ((((h = dataGen::hash<intT>(h)) % 1000003) < 500001)) pow += dim;
    j = (i + ((h = dataGen::hash<intT>(h)) % (((long) 1) << pow))) % numRows;
      } while (j == i);
    }
    E[k].u = i;  E[k].v = j;
  }
  return edgeArray<intT>(E,numRows,numRows,nonZeros);
}

int parallel_main(int argc, char* argv[]) {
  commandLine P(argc,argv,"[-m <numedges>] [-d <dims>] [-o] [-j] n <outFile>");
  pair<intT,char*> in = P.sizeAndFileName();
  intT n = in.first;
  char* fname = in.second;
  int dim = P.getOptionIntValue("-d", 0);
  intT m = P.getOptionLongValue("-m", 10*n);
  bool ordered = P.getOption("-o");
  bool adjArray = P.getOption("-j");
  edgeArray<intT> EA = edgeRandomWithDimension<intT>(dim, m/n, n);
  int r;
  if (adjArray) {
    graph<intT> G = graphFromEdges<intT>(EA,1);
    EA.del();
    if (!ordered) G = graphReorder<intT>(G, NULL);
    r = writeGraphToFile<intT>(G, fname);
    G.del();
  } else {
    if (!ordered) std::random_shuffle(EA.E, EA.E + EA.nonZeros);
    r = writeEdgeArrayToFile<intT>(EA, fname);
    EA.del();
  }
  return r;
}

template <class intT>
edgeArray<intT> makeSymmetric(edgeArray<intT> A) {
  intT m = A.nonZeros;
  edge<intT> *E = A.E;
  edge<intT> *F = newA(edge<intT>,2*m);
  intT mm = sequence::filter(E,F,m,nEQF<intT>());
  parallel_for (intT i=0; i < mm; i++) {
    F[i+mm].u = F[i].v;
    F[i+mm].v = F[i].u;
  }
  edgeArray<intT> R = remDuplicates(edgeArray<intT>(F,A.numRows,A.numCols,2*mm));
  free(F);
  return R;
  //return edgeArray<intT>(F,A.numRows,A.numCols,2*mm);
}

template <class intT>
graph<intT> graphFromEdges(edgeArray<intT> EA, bool makeSym) {
  edgeArray<intT> A;
  if (makeSym) A = makeSymmetric<intT>(EA);
  else {  // should have copy constructor
    edge<intT> *E = newA(edge<intT>,EA.nonZeros);
    parallel_for (intT i=0; i < EA.nonZeros; i++) E[i] = EA.E[i];
    A = edgeArray<intT>(E,EA.numRows,EA.numCols,EA.nonZeros);
  }
  intT m = A.nonZeros;
  intT n = max<intT>(A.numCols,A.numRows);
  intT* offsets = newA(intT,n*2);
  intSort::iSort(A.E,offsets,m,n,getuF<intT>());
  intT *X = newA(intT,m);
  vertex<intT> *v = newA(vertex<intT>,n);
  parallel_for (intT i=0; i < n; i++) {
    intT o = offsets[i];
    intT l = ((i == n-1) ? m : offsets[i+1])-offsets[i];
    v[i].degree = l;
    v[i].Neighbors = X+o;
    for (intT j=0; j < l; j++) {
      v[i].Neighbors[j] = A.E[o+j].v;
    }
  }
  A.del();
  free(offsets);
  return graph<intT>(v,n,m,X);
}

Upvotes: 2

Views: 1409

Answers (1)

autistic
autistic

Reputation: 15632

The portion of this particular valgrind output that should take your focus is the following:

==56442== Invalid write of size 8
==56442==    at 0x407260: edgeArray<int> makeSymmetric<int>(edgeArray<int>) (in /home/lstrait2/twe/Benchmarks/MIS/graphData/randLocalGraph)
==56442==    by 0x407716: main (in /home/lstrait2/twe/Benchmarks/MIS/graphData/randLocalGraph)
==56442==  Address 0x0 is not stack'd, malloc'd or (recently) free'd

This is telling you that you're trying to write to an object pointed to by a nullptr (hence "Address 0x0") in makeSymmetric.

It seems as though you're trying to allocate an object that is too large, and the allocation is failing. You should write code to handle failed allocations, for a start. For example, I have noticed that you use malloc (which is frowned upon in C++) in numerous places. The pattern you should use, if you're going to use malloc, looks like this:

whatever_type *identifier = malloc(count * sizeof *identifier);
if (identifier == NULL) {
    puts("ERROR ALLOCATING MEMORY!");
    exit(0);
}

Have you noticed anything missing in your code? Hintedy-hint -coughs- look at the last four lines of code hintedy-hint -coughs-

Your computer may not be running out of memory, but most standard libraries won't let you allocate all of your computers memory in one allocation. You might need to spread your memory use over multiple allocations, or try to compress the nodes somehow.

Upvotes: 2

Related Questions