我正在尝试调试 http://www.cs.cmu.edu/~pbbs/benchmarks/maximalIndependentSet.html 提供的一些图形生成代码.
对于大约 20,000,000 个节点大小的图，该代码可以正常工作，之后我会遇到段错误。我一直在尝试使用 Valgrind 调试这个问题，但在解释它给我的输出时遇到了困难，因为我对 Valgrind 的经验很少(我也不是 C++ 专家)。
下面是 Valgrind 输出和 C++ 代码的相关部分，如果您能提供有关如何解决此问题的建议，我将不胜感激。我通过 SSH 连接的机器非常强大，我在尝试制作大小为 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 (<a href="https://stackoverflow.com/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="0e63616d656c7b67626a4e7d623823656164677d626f786b3e3f2068606f6220696178" rel="noreferrer noopener nofollow">[email protected]</a>) (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)
然后是相关的 C++ 代码:
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);
}
最佳答案
这个特定的 valgrind 输出中您应该关注的部分如下:
==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
这告诉您，您正在尝试写入 makeSymmetric 中 nullptr 指向的对象(因此“地址 0x0”)。
似乎您正在尝试分配一个太大的对象，但分配失败。首先，您应该编写代码来处理失败的分配。例如，我注意到您在很多地方使用了malloc(这在C++ 中是不受欢迎的)。如果您要使用 malloc，您应该使用的模式如下所示:
whatever_type *identifier = malloc(count * sizeof *identifier);
if (identifier == NULL) {
puts("ERROR ALLOCATING MEMORY!");
exit(0);
}
您是否注意到代码中缺少任何内容？ hintedy-hint -coughs- 看最后四行代码hintedy-hint -coughs-
您的计算机可能没有内存不足，但大多数标准库不会让您在一次分配中分配所有计算机内存。您可能需要将内存使用分散到多个分配中，或者尝试以某种方式压缩节点。
关于c++ - 解释 Valgrind 输出 C++，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31102670/