Graphviz Issue Tracker
Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0000373graphvizDotpublic2004-04-21 00:002011-04-28 04:02
ReporterIgor Tebelev 
Assigned Toellson 
PrioritynormalSeverityminorReproducibilityalways
StatusclosedResolutionfixed 
PlatformOSwindowsOS Version
Summary0000373: Crash in dot cleanup
Description



My name is Igor Tebelev and I currently work for SoHaR Inc...



I've spend sometime playing with DOT and modifying it a little to possibly use it as a DLL in our system.



I've found a BUG: on very large diagrams in Release builds I'm having crashes in the function:



void cleanup1(graph_t* g) in rank.c...



It happens at the following line:



<CD>
...
for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
  for (e = agfstout(g,n); e; e = agnxtout(g,e))
  {
    f = ED_to_virt(e);
    if ( f && (e == ED_to_orig(f))) free(f); <=ยง here access violation and crash
...
</CD>



It's not happening all the time, just sometime.



I've managed to fix it by providing one extra iteration, because looks like several objects are referencing same ED_to_virt(e) pointer and setting it to NULL in one is not enough.



Additional Information

[north] We were a little surprised that it is possible for two original edges
to point to the same virtual edge, just because the graph is large.
(Maybe there are concentrators or some multi-edges here?)

Please send us a test graph.

I did confirm that the patch doesn't break any of the graphs in
our regression test suite, and dotmemtest is still rock solid.
So I put it in the current cvs code base

[igor]
Stephen,
I'm wondering: attached is the file produced by Maria Petri Net.
Somehow, it takes forever for dot.exe to process it. Looks very simple file
with around 200 nodes having 7 edges each... Somehow it takes a lot of time
to generate diagram... And this is not very big case... Is it because dot
has trouble assigning ranks? I'm confused...
On the other hand, I have found possible Stack Overflow in recursive call
to:
void search_component(graph_t* g, node_t* n) in decomp.c...

I've managed to get in there Stack Overflow on not very big diagrams in
Debug cases... So, I rewrote it a little and here is my new search_component
that require less stack:
<CD>
// TIG -- Now how it is to avoid Stack Overflow, or make it less likely {
static graph_t* gLessRecursion = NULL;
static node_t* otherLessRecursion = NULL;
static edge_t* eLessRecursion = NULL;
static void search_component_lessRecursion(node_t* n)
{
    int i;

    add_to_component(n);

    if (ND_out(n).list)
    {
        for (i = 0; (eLessRecursion = ND_out(n).list[i]); i++)
        {
            if ((otherLessRecursion = eLessRecursion->head) ==
n) otherLessRecursion = eLessRecursion->tail;
            if ((ND_mark(otherLessRecursion) != Cmark) &&
(otherLessRecursion == UF_find(otherLessRecursion)))
    
search_component_lessRecursion(otherLessRecursion);
        }
    }
    if (ND_in(n).list)
    {
        for (i = 0; (eLessRecursion = ND_in(n).list[i]); i++)
        {
            if ((otherLessRecursion = eLessRecursion->head) ==
n) otherLessRecursion = eLessRecursion->tail;
            if ((ND_mark(otherLessRecursion) != Cmark) &&
(otherLessRecursion == UF_find(otherLessRecursion)))
    
search_component_lessRecursion(otherLessRecursion);
        }
    }
    if (ND_flat_out(n).list)
    {
        for (i = 0; (eLessRecursion = ND_flat_out(n).list[i]); i++)
        {
            if ((otherLessRecursion = eLessRecursion->head) ==
n) otherLessRecursion = eLessRecursion->tail;
            if ((ND_mark(otherLessRecursion) != Cmark) &&
(otherLessRecursion == UF_find(otherLessRecursion)))
    
search_component_lessRecursion(otherLessRecursion);
        }
    }
    if (ND_flat_in(n).list)
    {
        for (i = 0; (eLessRecursion = ND_flat_in(n).list[i]); i++)
        {
            if ((otherLessRecursion = eLessRecursion->head) ==
n) otherLessRecursion = eLessRecursion->tail;
            if ((ND_mark(otherLessRecursion) != Cmark) &&
(otherLessRecursion == UF_find(otherLessRecursion)))
    
search_component_lessRecursion(otherLessRecursion);
        }
    }
}
// TIG -- Now how it is to avoid Stack Overflow, or make it less likely }

void search_component(graph_t* g, node_t* n)
{
/* TIG: Original -- how it was
    int c,i;
    elist vec[4];
    node_t *other;
    edge_t *e;

    add_to_component(n);

    vec[0] = ND_out(n); vec[1] = ND_in(n);
    vec[2] = ND_flat_out(n); vec[3] = ND_flat_in(n);

    for (c = 0; c <= 3; c++) {
        if (vec[c].list) for (i = 0; (e = vec[c].list[i]); i++) {
            if ((other = e->head) == n) other = e->tail;
            if ((ND_mark(other) != Cmark) && (other ==
UF_find(other)))
                search_component(g,other);
        }
    }
*/
// TIG -- Now how it is to avoid Stack Overflow, or make it less likely
    gLessRecursion = g;
    search_component_lessRecursion(n);
}
</CD>


TagsNo tags attached.
AUXILLARY-FILES
DATE-FIXED
FIX-COMMENT
Replace offending line with
<CD>
if ( f && (e == ED_to_orig(f))) {
  edge_t *e1, *f1;

  for (e1 = agfstout(g,n); e1; e1 = agnxtout(g,e1))
  {
    if(e != e1)
    {
      f1 = ED_to_virt(e1);
      if(f1 && (f == f1))
      {
        ED_to_vi
FORMER-ID436
INPUT-FILEhttp://www.graphviz.org/bugs/b436.dot [^]
OUTPUT-FILE
STATUS-COMMENTFixed
VERSION 1.12
Attached Files

- Relationships

-  Notes
There are no notes attached to this issue.

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


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