Number: 996
Title: memory leak if directional graph contains cycles
Submitter: Willem Kokke
Date: Wed Aug 16 11:13:16 2006
Subsys: Dot
Version: 2.9
System: *-*-*
Severity: minor
Problem:
If a graph has cycles, graphviz tries to break the cycles by reversing the edge. The code to do this seems to cause a memory leak.

This can be easily demostrated by replacing the create_test_graph function in dot.c with


static graph_t *create_test_graph(void)
{
    Agnode_t *node[3];
    Agraph_t *g;

g = agopen("new_graph", AGDIGRAPH);

node[0] = agnode(g, "0"); node[1] = agnode(g, "1"); node[2] = agnode(g, "2");

agedge(g, node[0], node[1]); agedge(g, node[1], node[2]); agedge(g, node[2], node[0]);

return g; }

and then running it with the -m flag to observe the memory increase. With the original create_test_graph, the memory foot print did not increase

I've compiled graphviz and dot with visual studio 2003 and 2005, both exhibit the same behaviour. I've first detected it with my own modified version of graphviz, but later verified it with the stock development snapshot
Input:

digraph example{
    a -> b -> c -> a
}
Comments:
With the help of various tools, I've found out where this leak occurs exactly

it seems for each cycle in the graph it leaks 168 bytes per layout step The exact location of the memory leak and call stack at that time is as follows:


---------- Block 336 at 0x007DAFA0: 168 bytes ----------
  Call Stack:
    d:workgraphviz-buggraphviz-win-devellibcommonmemory.c (52): gmalloc
    d:workgraphviz-buggraphviz-win-devellibcommonmemory.c (30): zmalloc
    d:workgraphviz-buggraphviz-win-devellibdotgenfastgr.c (169): new_virtual_edge
    d:workgraphviz-buggraphviz-win-devellibdotgenfastgr.c (199): virtual_edge
    d:workgraphviz-buggraphviz-win-devellibdotgenacyclic.c (32): reverse_edge
    d:workgraphviz-buggraphviz-win-devellibdotgenacyclic.c (49): dfs
    d:workgraphviz-buggraphviz-win-devellibdotgenacyclic.c (53): dfs
    d:workgraphviz-buggraphviz-win-devellibdotgenacyclic.c (53): dfs
    d:workgraphviz-buggraphviz-win-devellibdotgenacyclic.c (70): acyclic
    d:workgraphviz-buggraphviz-win-devellibdotgenrank.c (473): dot_rank
    d:workgraphviz-buggraphviz-win-devellibdotgendotinit.c (226): dot_layout
    d:workgraphviz-buggraphviz-win-devellibgvcgvlayout.c (68): gvLayoutJobs
    d:workgraphviz-buggraphviz-win-develcmddotdot.c (155): main
    f:vs70builds3077vccrtbldcrtsrcc]

Owner: *
Status: *