[Nauty] Memory leaks

[Brendan McKay]

Yes, it would be feasible to use a system of free lists instead of the 
present system.

I should have mentioned that despite improvements in memory allocation 
code since the Good Old Days, there has also been a loss due to the need 
for malloc/free to be thread-safe.

I'm hoping that my new design the stack for small arrays will mostly 
avoid that and also give some caching improvement from address 
proximity.  It will also give re-entrance without thread-local 
variables. I plan to start testing it fairly soon.

Brendan.

On 13/08/18 16:43, Matthias Walter wrote:
> Hi Brendan,
>
> thank you for the (quick!) clarification. Good to hear that there is 
> no real leak. Your explanation sounds like one could in principle add 
> a method to clean-up all these helper structures such as free lists, 
> etc., right?
>
> Best,
> Matthias
>
> On 12.08.2018 14:38, Brendan McKay wrote:
>>
>> 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
>
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> http://mailman.anu.edu.au/mailman/listinfo/nauty