Graphviz Issue Tracker
Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0001053graphvizGraph Librariespublic2006-01-31 09:072011-04-28 04:03
ReporterLudo Van Put 
Assigned Togviz 
PrioritynormalSeveritymajorReproducibilityalways
StatusacknowledgedResolutionno change required 
PlatformOSx86-Linux-OS Version
Summary0001053: memory corrupt when doing gvFreeLayout after agdelete of some nodes
Description



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:
<CD>
/*-------------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
</CD>
Additional Information

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.
TagsNo tags attached.
AUXILLARY-FILES
DATE-FIXED
FIX-COMMENT
FORMER-ID875
INPUT-FILE
OUTPUT-FILE
STATUS-COMMENTRequest
VERSION     2.6
Attached Files

- Relationships

-  Notes
There are no notes attached to this issue.

- Issue History
Date Modified Username Field Change
2011-04-28 04:03 user1 New Issue
2011-04-28 04:03 user1 Assigned To => user1


MantisBT 1.2.5[^]
Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker