[Dot] Double free bug in dot layout plugin

[GadgetSteve]

Ported Issue from Mantis
Original ID: 2061
Reported By: Torsten Landschoff

SEVERITY: MINOR
Submitted: 2011-03-13 19:20:40

OS: X86-LINUX-DEBIAN UNSTABLE

VERSION: CVS-20110313

DESCRIPTION

Using dot via the gv python module, I see a number of segfaults.
I traced the calls to the gv library and the attached file reproduces the problem:

torsten@sharokan:~$ valgrind lua gvtrace.lua
==19073== Memcheck, a memory error detector
..
==19073== ERROR SUMMARY: 18 errors from 14 contexts (suppressed: 43 from 7)

When using neato instead of dot, there are no errors reported by valgrind.
This seems to get triggered by removing nodes from the graph. Keeping
the nodes also makes the problem go away.

Here is the backtrace for the first duplicate free:
0x000000000b3414c5 in free_virtual_node_list (vn=0x5af31a0) at dotinit.c:128
128 next_vn = ND_next(vn);
(gdb) where
#0 0x000000000b3414c5 in free_virtual_node_list (vn=0x5af31a0) at dotinit.c:128
#1 0x000000000b3416fd in dot_cleanup (g=0x5af03a0) at dotinit.c:176
#2 0x00000000060fe149 in gvFreeLayout (gvc=0x5addf00, g=0x5af03a0) at gvlayout.c:110
#3 0x0000000005ec1f1a in layout (g=0x5af03a0, engine=0x5acc458 "dot") at gv.cpp:881

## ADDITIONAL INFORMATION

[erg]
Before doing another layout, you need to call gvFreeLayout() to free the memory used in the first layout.
As it says in section 2.4 of the library manual:

A given graph can be laid out multiple times. The application, however, must clean up the earlier
layout's information with a call to gvFreeLayout before invoking a new layout function.

Please try this and see if the leak goes away. If you are still seeing leaks, let us know. By the way, there
is a known leak relating to dot and clusters.

[torsten]
sorry for not coming back to you earlier. I forgot what I supplied with
the bug report and wanted to reply as soon as it goes online. I only
noticed today that the report is now available at

http://www.graphviz.org/bugs/b2149.html

The bug form has the real draw back that the submitter does not get a
copy of the report which I would have expected.

Please try this and see if the leak goes away. If you are still seeing

Sorry to tell you but I can't. I am using the Python wrappers to drive
GraphViz. The wrapper API does not expose the gvFreeLayout function.

In fact, all what I can call is the layout function in tclpkg/gv/gv.cpp
which has the following source code:

bool layout(Agraph_t *g, const char *engine)
{
int err;

if (!g)
    return false;
err = gvFreeLayout(gvc, g);  /* ignore errors */
err = gvLayout(gvc, g, engine);
return (! err);

}

AFAICT this should be fine as gvFreeLayout is called before doing a new
layout. Note especially that the problem I was reporting is actually
inside a call of gvFreeLayout:

(gdb) where
#0 0x000000000b3414c5 in free_virtual_node_list (vn=0x5af31a0) at dotinit.c:128
#1 0x000000000b3416fd in dot_cleanup (g=0x5af03a0) at dotinit.c:176
#2 0x00000000060fe149 in gvFreeLayout (gvc=0x5addf00, g=0x5af03a0) at gvlayout.c:110
#3 0x0000000005ec1f1a in layout (g=0x5af03a0, engine=0x5acc458 "dot") at gv.cpp:881

So your suggestiong to call gvFreeLayout does not help in any way as
this is where the problem occurrs.

I just updated to the current CVS version of GraphViz and this is what I
get out of valgrind:

$ valgrind lua b2149.lua
==26693== Invalid read of size 8
==26693== at 0xB3414C5: free_virtual_node_list (dotinit.c:128)
==26693== by 0xB3416FC: dot_cleanup (dotinit.c:176)
==26693== by 0x60FE148: gvFreeLayout (gvlayout.c:110)
==26693== by 0x5EC1F59: layout(Agraph_t_, char const_) (gv.cpp:884)
==26693== by 0x5ED4242: _wrap_layout (gv_lua.cpp:5444)
==26693== by 0x408868: ??? (in /usr/bin/lua5.1)
==26693== by 0x411F78: ??? (in /usr/bin/lua5.1)
==26693== by 0x408D2C: ??? (in /usr/bin/lua5.1)
==26693== by 0x408406: ??? (in /usr/bin/lua5.1)
==26693== by 0x408481: ??? (in /usr/bin/lua5.1)
==26693== by 0x405B4E: lua_pcall (in /usr/bin/lua5.1)
==26693== by 0x404395: ??? (in /usr/bin/lua5.1)

$ valgrind --db-attach=yes lua b2149.lua
==26803== Invalid read of size 8
==26803== at 0xB3414C5: free_virtual_node_list (dotinit.c:128)
==26803== by 0xB3416FC: dot_cleanup (dotinit.c:176)
==26803== by 0x60FE148: gvFreeLayout (gvlayout.c:110)
==26803== by 0x5EC1F59: layout(Agraph_t_, char const_) (gv.cpp:884)
==26803== by 0x5ED4242: _wrap_layout (gv_lua.cpp:5444)
...
==26803== by 0x405B4E: lua_pcall (in /usr/bin/lua5.1)
==26803== by 0x404395: ??? (in /usr/bin/lua5.1)
==26803== Address 0x5af3008 is 216 bytes inside a block of size 464
free'd
==26803== at 0x4C270BD: free (vg_replace_malloc.c:366)
==26803== by 0x6BE23F1: agFREEnode (node.c:149)
==26803== by 0x6BE2089: agDELnode (node.c:85)
==26803== by 0x6BDE7B2: agdelete (graph.c:430)
==26803== by 0x5EC1E70: rm(Agnode_t*) (gv.cpp:862)
==26803== by 0x5ED3BE4: _wrap_rm__SWIG_1 (gv_lua.cpp:5334)
==26803== by 0x5ED3F46: _wrap_rm (gv_lua.cpp:5402)
...

The traceback is still the same. It seems like removing a node somehow
causes the memory corruption. Maybe it would help to free the layout
first, but as I said - it is not available from lua/python.