[Nauty] Memory leaks

Sun Aug 12 22:38:28 AEST 2018

Hi Matthias,

What you see is not a memory leak even though valgrind is suspicious of it.

I'm appending mail I sent to Marco a short time ago which explains it.

To check there is really no leak, I compiled nautyex3.c exactly as 
distributed except for disabling the output to stdout, (i.e. without the 
DYNFREE insertions that you made), and I ran it like this:

%%%   (for n in `seq 1 1000000` ; do echo 1000 ; done) | nautyex3

After about 15 minutes the memory usage is still exactly the same as it 
was after the first few seconds, according to both 'top' and 
/proc/PID/statm .  So the program is reusing the allocated memory as 
intended, and never losing any of it.

Hope that helps.
Brendan.

--------------------------------------------------

The thing about those allocations is that if you call the same functions 
again, the same memory will be reused.  So they aren't strictly leaks, 
though they are problematic.

The problem being addressed is that for very simple functions with 
dynamic allocation, the time will be dominated by the cost of allocation 
and freeing.  Also, in practice the same functions tend to be called 
multiple times with the same graph size.  So a long time (decades) ago I 
got the idea of doing the allocation once and keeping the memory for 
future calls.  When I first implemented this, some things got much faster.

Today with multi-thread programming being normal, this method is not so 
great.  I have detailed plans for a new scheme which uses the stack for 
small arrays and malloc/free for large arrays, but I didn't have time to 
implement it yet.

Of course, if you find a case where the memory in use keeps growing 
without limit, that's an error and I'd appreciate knowing about it.

On 12/8/18 9:43 pm, Matthias Walter wrote:
> Dear developers,
>
> we are using nauty (27b11) for a project and observed several memory 
> leaks occuring in the densenauty() call. Is there a way to free this 
> memory? To reproduce this bug we considered the nautyex3.c example and 
> added
>
>   DYNFREE(g,g_sz);
>   DYNFREE(lab,lab_sz);
>   DYNFREE(ptn,ptn_sz);
>   DYNFREE(orbits,orbits_sz);
>
> after the allgroup() call to free the memory that we allocated 
> explicitly. Using valgrind, we observe the following leaks after 
> running it with n=1 and aborting with n=-1 afterwards.
>
> Best,
> Matthias
>
> ==26840==
> ==26840== HEAP SUMMARY:
> ==26840==     in use at exit: 1,124 bytes in 19 blocks
> ==26840==   total heap usage: 25 allocs, 6 frees, 3,192 bytes allocated
> ==26840==
> ==26840== 4 bytes in 1 blocks are still reachable in loss record 1 of 19
> ==26840==    at 0x4C2DB8F: malloc (in 
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==26840==    by 0x402B17: nauty (nauty.c:358)
> ==26840==    by 0x405CD2: densenauty (naugraph.c:657)
> ==26840==    by 0x400C7F: main (nautyex3.c:57)
> ==26840==
> ==26840== 4 bytes in 1 blocks are still reachable in loss record 2 of 19
> ==26840==    at 0x4C2DB8F: malloc (in 
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==26840==    by 0x402B65: nauty (nauty.c:359)
> ==26840==    by 0x405CD2: densenauty (naugraph.c:657)
> ==26840==    by 0x400C7F: main (nautyex3.c:57)
> ==26840==
> ==26840== 4 bytes in 1 blocks are still reachable in loss record 3 of 19
> ==26840==    at 0x4C2DB8F: malloc (in 
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==26840==    by 0x402BB3: nauty (nauty.c:360)
> ==26840==    by 0x405CD2: densenauty (naugraph.c:657)
> ==26840==    by 0x400C7F: main (nautyex3.c:57)
> ==26840==
> ==26840== 4 bytes in 1 blocks are still reachable in loss record 4 of 19
> ==26840==    at 0x4C2DB8F: malloc (in 
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==26840==    by 0x404216: doref (nautil.c:492)
> ==26840==    by 0x401C74: firstpathnode0 (nauty.c:591)
> ==26840==    by 0x4031D5: nauty (nauty.c:498)
> ==26840==    by 0x405CD2: densenauty (naugraph.c:657)
> ==26840==    by 0x400C7F: main (nautyex3.c:57)
> ==26840==
> ==26840== 4 bytes in 1 blocks are still reachable in loss record 5 of 19
> ==26840==    at 0x4C2DB8F: malloc (in 
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==26840==    by 0x4055A2: refine1 (naugraph.c:352)
> ==26840==    by 0x40428C: doref (nautil.c:497)
> ==26840==    by 0x401C74: firstpathnode0 (nauty.c:591)
> ==26840==    by 0x4031D5: nauty (nauty.c:498)
> ==26840==    by 0x405CD2: densenauty (naugraph.c:657)
> ==26840==    by 0x400C7F: main (nautyex3.c:57)
> ==26840==
> ==26840== 4 bytes in 1 blocks are still reachable in loss record 6 of 19
> ==26840==    at 0x4C2DB8F: malloc (in 
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==26840==    by 0x408773: makecosetreps (naugroup.c:222)
> ==26840==    by 0x400C98: main (nautyex3.c:71)
> ==26840==
> ==26840== 4 bytes in 1 blocks are still reachable in loss record 7 of 19
> ==26840==    at 0x4C2DB8F: malloc (in 
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==26840==    by 0x4087BA: makecosetreps (naugroup.c:223)
> ==26840==    by 0x400C98: main (nautyex3.c:71)
> ==26840==
> ==26840== 4 bytes in 1 blocks are still reachable in loss record 8 of 19
> ==26840==    at 0x4C2DB8F: malloc (in 
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==26840==    by 0x408C69: allgroup (naugroup.c:376)
> ==26840==    by 0x400CA5: main (nautyex3.c:76)
> ==26840==
> ==26840== 6 bytes in 1 blocks are still reachable in loss record 9 of 19
> ==26840==    at 0x4C2DB8F: malloc (in 
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==26840==    by 0x402C03: nauty (nauty.c:361)
> ==26840==    by 0x405CD2: densenauty (naugraph.c:657)
> ==26840==    by 0x400C7F: main (nautyex3.c:57)
> ==26840==
> ==26840== 6 bytes in 1 blocks are still reachable in loss record 10 of 19
> ==26840==    at 0x4C2DB8F: malloc (in 
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==26840==    by 0x402C53: nauty (nauty.c:362)
> ==26840==    by 0x405CD2: densenauty (naugraph.c:657)
> ==26840==    by 0x400C7F: main (nautyex3.c:57)
> ==26840==
> ==26840== 8 bytes in 1 blocks are still reachable in loss record 11 of 19
> ==26840==    at 0x4C2DB8F: malloc (in 
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==26840==    by 0x402A7B: nauty (nauty.c:356)
> ==26840==    by 0x405CD2: densenauty (naugraph.c:657)
> ==26840==    by 0x400C7F: main (nautyex3.c:57)
> ==26840==
> ==26840== 8 bytes in 1 blocks are still reachable in loss record 12 of 19
> ==26840==    at 0x4C2DB8F: malloc (in 
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==26840==    by 0x402AC9: nauty (nauty.c:357)
> ==26840==    by 0x405CD2: densenauty (naugraph.c:657)
> ==26840==    by 0x400C7F: main (nautyex3.c:57)
> ==26840==
> ==26840== 8 bytes in 1 blocks are still reachable in loss record 13 of 19
> ==26840==    at 0x4C2DB8F: malloc (in 
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==26840==    by 0x401BC2: firstpathnode0 (nauty.c:578)
> ==26840==    by 0x4031D5: nauty (nauty.c:498)
> ==26840==    by 0x405CD2: densenauty (naugraph.c:657)
> ==26840==    by 0x400C7F: main (nautyex3.c:57)
> ==26840==
> ==26840== 12 bytes in 1 blocks are still reachable in loss record 14 
> of 19
> ==26840==    at 0x4C2DB8F: malloc (in 
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==26840==    by 0x402CA7: nauty (nauty.c:363)
> ==26840==    by 0x405CD2: densenauty (naugraph.c:657)
> ==26840==    by 0x400C7F: main (nautyex3.c:57)
> ==26840==
> ==26840== 12 bytes in 1 blocks are still reachable in loss record 15 
> of 19
> ==26840==    at 0x4C2DB8F: malloc (in 
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==26840==    by 0x4055F6: refine1 (naugraph.c:353)
> ==26840==    by 0x40428C: doref (nautil.c:497)
> ==26840==    by 0x401C74: firstpathnode0 (nauty.c:591)
> ==26840==    by 0x4031D5: nauty (nauty.c:498)
> ==26840==    by 0x405CD2: densenauty (naugraph.c:657)
> ==26840==    by 0x400C7F: main (nautyex3.c:57)
> ==26840==
> ==26840== 16 bytes in 1 blocks are still reachable in loss record 16 
> of 19
> ==26840==    at 0x4C2DB8F: malloc (in 
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==26840==    by 0x402A2D: nauty (nauty.c:355)
> ==26840==    by 0x405CD2: densenauty (naugraph.c:657)
> ==26840==    by 0x400C7F: main (nautyex3.c:57)
> ==26840==
> ==26840== 16 bytes in 1 blocks are still reachable in loss record 17 
> of 19
> ==26840==    at 0x4C2DB8F: malloc (in 
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==26840==    by 0x401BA5: firstpathnode0 (nauty.c:576)
> ==26840==    by 0x4031D5: nauty (nauty.c:498)
> ==26840==    by 0x405CD2: densenauty (naugraph.c:657)
> ==26840==    by 0x400C7F: main (nautyex3.c:57)
> ==26840==
> ==26840== 40 bytes in 1 blocks are still reachable in loss record 18 
> of 19
> ==26840==    at 0x4C2DB8F: malloc (in 
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==26840==    by 0x408667: grouplevelproc (naugroup.c:181)
> ==26840==    by 0x401EC2: firstpathnode0 (nauty.c:625)
> ==26840==    by 0x4031D5: nauty (nauty.c:498)
> ==26840==    by 0x405CD2: densenauty (naugraph.c:657)
> ==26840==    by 0x400C7F: main (nautyex3.c:57)
> ==26840==
> ==26840== 960 bytes in 1 blocks are still reachable in loss record 19 
> of 19
> ==26840==    at 0x4C2DB8F: malloc (in 
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
> ==26840==    by 0x405C89: densenauty (naugraph.c:654)
> ==26840==    by 0x400C7F: main (nautyex3.c:57)
> ==26840==
> ==26840== LEAK SUMMARY:
> ==26840==    definitely lost: 0 bytes in 0 blocks
> ==26840==    indirectly lost: 0 bytes in 0 blocks
> ==26840==      possibly lost: 0 bytes in 0 blocks
> ==26840==    still reachable: 1,124 bytes in 19 blocks
> ==26840==         suppressed: 0 bytes in 0 blocks
> ==26840==
> ==26840== For counts of detected and suppressed errors, rerun with: -v
> ==26840== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
>
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> http://mailman.anu.edu.au/mailman/listinfo/nauty