Number: 875
Title: memory corrupt when doing gvFreeLayout after agdelete of some nodes
Submitter: Ludo Van Put
Date: Tue Jan 31 09:07:48 2006
Subsys: Lib(a)graph
Version: 2.6
System: x86-Linux-
Severity: major
Problem:
I use the libgvc library in a GUI for a link-time program rewriter, Diablo (Lancet) http://www.elis.ugent.be/diablo/?q=lancet_book The control flow graphs of the functions in a program are shown and can be navigated. We use gnomecanvas to actually draw the graphs, but the layout is computed using the graphviz library. From our internal graphs we build a graphviz-graph, compute a layout and then build a gnomecanvas graph to display the result. A user can remove edges and nodes in the graph. In some cases, when some of the nodes and incoming and outgoing edges are deleted (using agdelete), gvFreeLayout crashes when it is called afterwards. Not sure if we are using the lib in a wrong way, or if it is a bug. I will give some relevant code snippets below, followed by valgrind output, indicating where thing go wrong:

/*-------------code snippets-----------------*/
CW_GVC(canvas_window) = gvContext();

CW_GRAPH(canvas_window)=agopen("no_name",AGDIGRAPH);

...

/* make it possible to set graph attributes */ attrib_node_label = agnodeattr(CW_GRAPH(canvas_window),"label",""); /* ... some more of these attributes */

/* add some nodes using agnode and edges using agedge, set the attributes using agxset */

/* compute the layout (context was alloced previously, is stored in CW_GVC(canvas_window) */ gvLayout(CW_GVC(canvas_window), CW_GRAPH(canvas_window), "dot");

/* Some gtk and gnomecanvas code to display the graph, set some callback to be able to delete edges and nodes */

/* delete a node and all incoming and outgoing edges */ edge_graphviz1 = agfstout(CW_GRAPH(canvas_window),trv_node); while(edge_graphviz1) { tmp_copy = edge_graphviz1; edge_graphviz1 = agnxtout(CW_GRAPH(canvas_window),edge_graphviz1); agdelete(CW_GRAPH(canvas_window),tmp_copy); } edge_graphviz1 = agfstin(CW_GRAPH(canvas_window),trv_node); while() { /* same as above */ } /* delete the node as well */ agdelete(CW_GRAPH(canvas_window),trv_node);

/* Free memory, clean up */ gvFreeLayout(CW_GVC(canvas_window),CW_GRAPH(canvas_window));

agclose(CW_GRAPH(canvas_window));

/*--------valgrind output-------------*/

==25700== Invalid read of size 4 ==25700== at 0x1E8F5744: zapinlist (fastgr.c:107) ==25700== by 0x1E8F57B2: delete_fast_edge (fastgr.c:122) ==25700== by 0x1E8F6CF0: dot_cleanup (dotinit.c:131) ==25700== by 0x1BE31AD1: gvFreeLayout (gvlayout.c:74) ==25700== by 0x81465C6: GuiCanvasCleanUp (lancet_canvas_window.c:249) ==25700== by 0x1BD823AD: g_cclosure_marshal_VOID__VOID (in /usr/lib/libgobject-2.0.so.0.400.8) ==25700== Address 0x1E55C55C is not stack'd, malloc'd or (recently) free'd ==25700== ==25700== Invalid read of size 4 ==25700== at 0x1E8F5751: zapinlist (fastgr.c:107) ==25700== by 0x1E8F57B2: delete_fast_edge (fastgr.c:122) ==25700== by 0x1E8F6CF0: dot_cleanup (dotinit.c:131) ==25700== by 0x1BE31AD1: gvFreeLayout (gvlayout.c:74) ==25700== by 0x81465C6: GuiCanvasCleanUp (lancet_canvas_window.c:249) ==25700== by 0x1BD823AD: g_cclosure_marshal_VOID__VOID (in /usr/lib/libgobject-2.0.so.0.400.8) ==25700== Address 0x1E55C558 is not stack'd, malloc'd or (recently) free'd ==25700== ==25700== Invalid write of size 4 ==25700== at 0x1E8F5769: zapinlist (fastgr.c:109) ==25700== by 0x1E8F57B2: delete_fast_edge (fastgr.c:122) ==25700== by 0x1E8F6CF0: dot_cleanup (dotinit.c:131) ==25700== by 0x1BE31AD1: gvFreeLayout (gvlayout.c:74) ==25700== by 0x81465C6: GuiCanvasCleanUp (lancet_canvas_window.c:249) ==25700== by 0x1BD823AD: g_cclosure_marshal_VOID__VOID (in /usr/lib/libgobject-2.0.so.0.400.8) ==25700== Address 0x1E55C55C is not stack'd, malloc'd or (recently) free'd ==25700== ==25700== Invalid read of size 4 ==25700== at 0x1E8F6C9B: dot_cleanup (dotinit.c:141) ==25700== by 0x1BE31AD1: gvFreeLayout (gvlayout.c:74) ==25700== by 0x81465C6: GuiCanvasCleanUp (lancet_canvas_window.c:249) ==25700== by 0x1BD823AD: g_cclosure_marshal_VOID__VOID (in /usr/lib/libgobject-2.0.so.0.400.8) ==25700== by 0x1BD6A346: g_closure_invoke (in /usr/lib/libgobject-2.0.so.0.400.8) ==25700== by 0x1BD80AE0: (within /usr/lib/libgobject-2.0.so.0.400.8) ==25700== Address 0x1E55C550 is not stack'd, malloc'd or (recently) free'd ==25700== ==25700== Invalid read of size 4 ==25700== at 0x1E8F6CA1: dot_cleanup (dotinit.c:124) ==25700== by 0x1BE31AD1: gvFreeLayout (gvlayout.c:74) ==25700== by 0x81465C6: GuiCanvasCleanUp (lancet_canvas_window.c:249) ==25700== by 0x1BD823AD: g_cclosure_marshal_VOID__VOID (in /usr/lib/libgobject-2.0.so.0.400.8) ==25700== by 0x1BD6A346: g_closure_invoke (in /usr/lib/libgobject-2.0.so.0.400.8) ==25700== by 0x1BD80AE0: (within /usr/lib/libgobject-2.0.so.0.400.8) ==25700== Address 0x1E55C55C is not stack'd, malloc'd or (recently) free'd ==25700== ==25700== Invalid read of size 4 ==25700== at 0x1E8F6CD2: dot_cleanup (dotinit.c:129) ==25700== by 0x1BE31AD1: gvFreeLayout (gvlayout.c:74) ==25700== by 0x81465C6: GuiCanvasCleanUp (lancet_canvas_window.c:249) ==25700== by 0x1BD823AD: g_cclosure_marshal_VOID__VOID (in /usr/lib/libgobject-2.0.so.0.400.8) ==25700== by 0x1BD6A346: g_closure_invoke (in /usr/lib/libgobject-2.0.so.0.400.8) ==25700== by 0x1BD80AE0: (within /usr/lib/libgobject-2.0.so.0.400.8) ==25700== Address 0x1E55C564 is not stack'd, malloc'd or (recently) free'd ==25700== ==25700== Invalid read of size 4 ==25700== at 0x1E8F6CDF: dot_cleanup (dotinit.c:130) ==25700== by 0x1BE31AD1: gvFreeLayout (gvlayout.c:74) ==25700== by 0x81465C6: GuiCanvasCleanUp (lancet_canvas_window.c:249) ==25700== by 0x1BD823AD: g_cclosure_marshal_VOID__VOID (in /usr/lib/libgobject-2.0.so.0.400.8) ==25700== by 0x1BD6A346: g_closure_invoke (in /usr/lib/libgobject-2.0.so.0.400.8) ==25700== by 0x1BD80AE0: (within /usr/lib/libgobject-2.0.so.0.400.8) ==25700== Address 0x1E55C560 is not stack'd, malloc'd or (recently) free'd ==25700== ==25700== Invalid read of size 4 ==25700== at 0x1E8F5744: zapinlist (fastgr.c:107) ==25700== by 0x1E8F57A1: delete_fast_edge (fastgr.c:121) ==25700== by 0x1E8F6CF0: dot_cleanup (dotinit.c:131) ==25700== by 0x1BE31AD1: gvFreeLayout (gvlayout.c:74) ==25700== by 0x81465C6: GuiCanvasCleanUp (lancet_canvas_window.c:249) ==25700== by 0x1BD823AD: g_cclosure_marshal_VOID__VOID (in /usr/lib/libgobject-2.0.so.0.400.8) ==25700== Address 0x1E55C564 is not stack'd, malloc'd or (recently) free'd ==25700== ==25700== Invalid read of size 4 ==25700== at 0x1E8F5751: zapinlist (fastgr.c:107) ==25700== by 0x1E8F57A1: delete_fast_edge (fastgr.c:121) ==25700== by 0x1E8F6CF0: dot_cleanup (dotinit.c:131) ==25700== by 0x1BE31AD1: gvFreeLayout (gvlayout.c:74) ==25700== by 0x81465C6: GuiCanvasCleanUp (lancet_canvas_window.c:249) ==25700== by 0x1BD823AD: g_cclosure_marshal_VOID__VOID (in /usr/lib/libgobject-2.0.so.0.400.8) ==25700== Address 0x1E55C560 is not stack'd, malloc'd or (recently) free'd ==25700== ==25700== Invalid write of size 4 ==25700== at 0x1E8F5769: zapinlist (fastgr.c:109) ==25700== by 0x1E8F57A1: delete_fast_edge (fastgr.c:121) ==25700== by 0x1E8F6CF0: dot_cleanup (dotinit.c:131) ==25700== by 0x1BE31AD1: gvFreeLayout (gvlayout.c:74) ==25700== by 0x81465C6: GuiCanvasCleanUp (lancet_canvas_window.c:249) ==25700== by 0x1BD823AD: g_cclosure_marshal_VOID__VOID (in /usr/lib/libgobject-2.0.so.0.400.8) ==25700== Address 0x1E55C564 is not stack'd, malloc'd or (recently) free'd ==25700== ==25700== Invalid read of size 1 ==25700== at 0x1E8F6D02: dot_cleanup (dotinit.c:143) ==25700== by 0x1BE31AD1: gvFreeLayout (gvlayout.c:74) ==25700== by 0x81465C6: GuiCanvasCleanUp (lancet_canvas_window.c:249) ==25700== by 0x1BD823AD: g_cclosure_marshal_VOID__VOID (in /usr/lib/libgobject-2.0.so.0.400.8) ==25700== by 0x1BD6A346: g_closure_invoke (in /usr/lib/libgobject-2.0.so.0.400.8) ==25700== by 0x1BD80AE0: (within /usr/lib/libgobject-2.0.so.0.400.8) ==25700== Address 0x1E55C54A is not stack'd, malloc'd or (recently) free'd


Comments:
Things also go wrong when using older versions of the graphviz library, I've tried it with the 2.2 version as well.

[erg] There are two underlying parts in Graphviz: the basic graph library and the graph layout library built on the former by adding additional fields to nodes, edges and graphs. Once a layout is done, the additional fields contain, in addition to purely geometric and graphics information, pointers to nodes, edges and graphs. When you use agdelete(), you remove the object using the basic graph library. All the pointers to the object still exist in the layout fields of other. So when you call gvFreeLayout(), it's going to access a node or edge that you've deleted, causing the crash.

For now, then, the answer is that you don't want to allow the graph to be modified before calling gvFreeLayout(). If there is information from the layout you want to maintain, you'll have to make a deep copy of it elsewhere. I guess the idea is that, if you're going to modify the graph, the layout will no longer be valid, so free the layout first.

We'll have to consider whether this restriction can be loosened. Some of the auxiliary layout info with graph object pointers could be freed after the layout is done, but not all. For example, the layout info provides pointers to the clusters, which applications use in rendering. If these are still around, it would be dangerous to modify the graph. Maybe we can provide versions of delete sensitive to the additional layout information.

[ludo] thanks for your quick reply. I will be able to circumvent the problem by freeing the layout and recompute it afterwards. It would be nice though, if you're going to loosen the described restriction. In our case, it is undesired to recompute the layout because, when you're working with a graph and you are editing it (like removing nodes and so on) it would be confusing to change the layout each time. I could make a deep copy of the existing layout and call gvFreeLayout first, but then I loose the ability to export the graphs in some format to a file. Nevertheless, I really like the graphviz project. If you think it is worthwile, you can list our project on the graphviz website.
Owner: *
Status: Request