[Dot] Dot.exe crashes

[GadgetSteve]

Ported Issue from Mantis Original ID: 1843 Referenced attachment(s) only available in original Mantis DB Reported By: Bernhard Seybold

SEVERITY: MAJOR Submitted: 2010-03-22 08:13:11

OS: X86-WINDOWS-WIN7 X64

VERSION: 2.26.3

DESCRIPTION

dot.exe -v -Tjpg -O routes.dot

crashes (same happens with graphviz 2.27.20100201.0545) Similar files work ok. Neato can process the file.

ADDITIONAL INFORMATION

[erg] It's a fairly large graph for dot. Here is the trace log.

[erg] The stack is being blown in the recursive use of treesearch() in ns.c. The graph in that phase has 752011 nodes and 1128201 edges.

[bulldozier]

I am seeing this crash too, using the latest code. The stack trace is 100k deep.

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff0f7acec in add_tree_edge (e=Cannot access memory at address 0x7fffff3fefe8
) at ns.c:46
(gdb) bt
#0  0x00007ffff0f7acec in add_tree_edge (e=Cannot access memory at address 0x7fffff3fefe8
) at ns.c:46
#1  0x00007ffff0f7c36c in treesearch (v=0x11e21900) at ns.c:277
#2  0x00007ffff0f7c3b0 in treesearch (v=0x8b6e020) at ns.c:278
#3  0x00007ffff0f7c3b0 in treesearch (v=0x11e49730) at ns.c:278
#4  0x00007ffff0f7c3b0 in treesearch (v=0x8b96690) at ns.c:278
#5  0x00007ffff0f7c3b0 in treesearch (v=0x11e71da0) at ns.c:278
#6  0x00007ffff0f7c3b0 in treesearch (v=0x8bbf590) at ns.c:278
#7  0x00007ffff0f7c3b0 in treesearch (v=0x11e9aca0) at ns.c:278
#8  0x00007ffff0f7c3b0 in treesearch (v=0x8be8cc0) at ns.c:278
#9  0x00007ffff0f7c3b0 in treesearch (v=0x11ec43d0) at ns.c:278
#10 0x00007ffff0f7c3b0 in treesearch (v=0x8c12c60) at ns.c:278
#11 0x00007ffff0f7c3b0 in treesearch (v=0x11eee370) at ns.c:278
#12 0x00007ffff0f7c3b0 in treesearch (v=0x8c3d450) at ns.c:278
#13 0x00007ffff0f7c3b0 in treesearch (v=0x11f18b60) at ns.c:278
#14 0x00007ffff0f7c3b0 in treesearch (v=0x8c684c0) at ns.c:278
#15 0x00007ffff0f7c3b0 in treesearch (v=0x11f43bd0) at ns.c:278
#16 0x00007ffff0f7c3b0 in treesearch (v=0x8c93d70) at ns.c:278
#17 0x00007ffff0f7c3b0 in treesearch (v=0x11f6f480) at ns.c:278
#18 0x00007ffff0f7c3b0 in treesearch (v=0x8cbfeb0) at ns.c:278
#19 0x00007ffff0f7c3b0 in treesearch (v=0x11f9b5c0) at ns.c:278
#20 0x00007ffff0f7c3b0 in treesearch (v=0x8cec820) at ns.c:278
#21 0x00007ffff0f7c3b0 in treesearch (v=0x11fc7f30) at ns.c:278
#22 0x00007ffff0f7c3b0 in treesearch (v=0x8d19a00) at ns.c:278
...
#98095 0x00007ffff0f7c24c in treesearch (v=0x28d90e0) at ns.c:271
#98096 0x00007ffff0f7c24c in treesearch (v=0xbbb24a0) at ns.c:271
#98097 0x00007ffff0f7c24c in treesearch (v=0x28d6dc0) at ns.c:271
#98098 0x00007ffff0f7c24c in treesearch (v=0x18a6820) at ns.c:271
#98099 0x00007ffff0f7c24c in treesearch (v=0x1816820) at ns.c:271
#98100 0x00007ffff0f7c24c in treesearch (v=0x18a55a0) at ns.c:271
#98101 0x00007ffff0f7c24c in treesearch (v=0x18155a0) at ns.c:271
#98102 0x00007ffff0f7c24c in treesearch (v=0x18a4bb0) at ns.c:271
#98103 0x00007ffff0f7c24c in treesearch (v=0x1814bb0) at ns.c:271
#98104 0x00007ffff0f7c24c in treesearch (v=0x1d98940) at ns.c:271
#98105 0x00007ffff0f7c24c in treesearch (v=0x1e0e3bc0) at ns.c:271
#98106 0x00007ffff0f7c3b0 in treesearch (v=0x1f7baa0) at ns.c:278
#98107 0x00007ffff0f7c24c in treesearch (v=0x37f32500) at ns.c:271
#98108 0x00007ffff0f7c3b0 in treesearch (v=0x1d1ed00) at ns.c:278
#98109 0x00007ffff0f7c24c in treesearch (v=0x381fbfb0) at ns.c:271
#98110 0x00007ffff0f7c50c in tight_tree () at ns.c:300
#98111 0x00007ffff0f7c8d5 in feasible_tree () at ns.c:318
#98112 0x00007ffff0f7de3e in rank2 (g=0x1d91280, balance=2, maxiter=2866, search_size=1) at ns.c:643
#98113 0x00007ffff0f7e131 in rank (g=0x1d91280, balance=2, maxiter=2866) at ns.c:716
#98114 0x00007ffff00a0407 in dot_position (g=0x1d91280, asp=0x0) at position.c:132
#98115 0x00007ffff00982e5 in dotLayout (g=0x1d91280) at dotinit.c:344
#98116 0x00007ffff00989e3 in doDot (g=0x1d91280) at dotinit.c:484
#98117 0x00007ffff0098b65 in dot_layout (g=0x1d91280) at dotinit.c:530
#98118 0x00007ffff0f3d8e0 in gvLayoutJobs (gvc=0x16c11c0, g=0x1d91280) at gvlayout.c:87
#98119 0x00007ffff0f47241 in gvLayout (gvc=0x16c11c0, g=0x1d91280, engine=0x8fbb82 "neato") at gvc.c:78

[magneticnorth]

How big is this graph?

treesearch() in lib/dotgen2/ns.c is recursive, so on a large enough graph, it could run out of stack space. try ulimit -s and increase it, e.g. ulimit -s 32768

It’s not likely we would go to the trouble of recoding ns.c to use an explicit stack instead of recursion just for a few examples.

On Oct 25, 2016, at 2:50 PM, bulldozier notifications@github.com wrote:

I am seeing this crash too, using the latest code. The stack trace is 100k deep.

Program received signal SIGSEGV, Segmentation fault. 0x00007ffff0f7acec in add_tree_edge (e=Cannot access memory at address 0x7fffff3fefe8 ) at ns.c:46 (gdb) bt

0 0x00007ffff0f7acec in add_tree_edge (e=Cannot access memory at address 0x7fffff3fefe8

) at ns.c:46

1 0x00007ffff0f7c36c in treesearch (v=0x11e21900) at ns.c:277

2 0x00007ffff0f7c3b0 in treesearch (v=0x8b6e020) at ns.c:278

3 0x00007ffff0f7c3b0 in treesearch (v=0x11e49730) at ns.c:278

4 0x00007ffff0f7c3b0 in treesearch (v=0x8b96690) at ns.c:278

5 0x00007ffff0f7c3b0 in treesearch (v=0x11e71da0) at ns.c:278

6 0x00007ffff0f7c3b0 in treesearch (v=0x8bbf590) at ns.c:278

7 0x00007ffff0f7c3b0 in treesearch (v=0x11e9aca0) at ns.c:278

8 0x00007ffff0f7c3b0 in treesearch (v=0x8be8cc0) at ns.c:278

9 0x00007ffff0f7c3b0 in treesearch (v=0x11ec43d0) at ns.c:278

10 0x00007ffff0f7c3b0 in treesearch (v=0x8c12c60) at ns.c:278

11 0x00007ffff0f7c3b0 in treesearch (v=0x11eee370) at ns.c:278

12 0x00007ffff0f7c3b0 in treesearch (v=0x8c3d450) at ns.c:278

13 0x00007ffff0f7c3b0 in treesearch (v=0x11f18b60) at ns.c:278

14 0x00007ffff0f7c3b0 in treesearch (v=0x8c684c0) at ns.c:278

15 0x00007ffff0f7c3b0 in treesearch (v=0x11f43bd0) at ns.c:278

16 0x00007ffff0f7c3b0 in treesearch (v=0x8c93d70) at ns.c:278

17 0x00007ffff0f7c3b0 in treesearch (v=0x11f6f480) at ns.c:278

18 0x00007ffff0f7c3b0 in treesearch (v=0x8cbfeb0) at ns.c:278

19 0x00007ffff0f7c3b0 in treesearch (v=0x11f9b5c0) at ns.c:278

20 0x00007ffff0f7c3b0 in treesearch (v=0x8cec820) at ns.c:278

21 0x00007ffff0f7c3b0 in treesearch (v=0x11fc7f30) at ns.c:278

22 0x00007ffff0f7c3b0 in treesearch (v=0x8d19a00) at ns.c:278

...

98095 0x00007ffff0f7c24c in treesearch (v=0x28d90e0) at ns.c:271

98096 0x00007ffff0f7c24c in treesearch (v=0xbbb24a0) at ns.c:271

98097 0x00007ffff0f7c24c in treesearch (v=0x28d6dc0) at ns.c:271

98098 0x00007ffff0f7c24c in treesearch (v=0x18a6820) at ns.c:271

98099 0x00007ffff0f7c24c in treesearch (v=0x1816820) at ns.c:271

98100 0x00007ffff0f7c24c in treesearch (v=0x18a55a0) at ns.c:271

98101 0x00007ffff0f7c24c in treesearch (v=0x18155a0) at ns.c:271

98102 0x00007ffff0f7c24c in treesearch (v=0x18a4bb0) at ns.c:271

98103 0x00007ffff0f7c24c in treesearch (v=0x1814bb0) at ns.c:271

98104 0x00007ffff0f7c24c in treesearch (v=0x1d98940) at ns.c:271

98105 0x00007ffff0f7c24c in treesearch (v=0x1e0e3bc0) at ns.c:271

98106 0x00007ffff0f7c3b0 in treesearch (v=0x1f7baa0) at ns.c:278

98107 0x00007ffff0f7c24c in treesearch (v=0x37f32500) at ns.c:271

98108 0x00007ffff0f7c3b0 in treesearch (v=0x1d1ed00) at ns.c:278

98109 0x00007ffff0f7c24c in treesearch (v=0x381fbfb0) at ns.c:271

98110 0x00007ffff0f7c50c in tight_tree () at ns.c:300

98111 0x00007ffff0f7c8d5 in feasible_tree () at ns.c:318

98112 0x00007ffff0f7de3e in rank2 (g=0x1d91280, balance=2, maxiter=2866, search_size=1) at ns.c:643

98113 0x00007ffff0f7e131 in rank (g=0x1d91280, balance=2, maxiter=2866) at ns.c:716

98114 0x00007ffff00a0407 in dot_position (g=0x1d91280, asp=0x0) at position.c:132

98115 0x00007ffff00982e5 in dotLayout (g=0x1d91280) at dotinit.c:344

98116 0x00007ffff00989e3 in doDot (g=0x1d91280) at dotinit.c:484

98117 0x00007ffff0098b65 in dot_layout (g=0x1d91280) at dotinit.c:530

98118 0x00007ffff0f3d8e0 in gvLayoutJobs (gvc=0x16c11c0, g=0x1d91280) at gvlayout.c:87

98119 0x00007ffff0f47241 in gvLayout (gvc=0x16c11c0, g=0x1d91280, engine=0x8fbb82 "neato") at gvc.c:78

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/ellson/graphviz/issues/201#issuecomment-256137522, or mute the thread https://github.com/notifications/unsubscribe-auth/ACtWz-XZWPemsP8HpcXjANAzDjh-BLjFks5q3k98gaJpZM4JEm9w.

[bulldozier]

The graph that is crashing has 2866 nodes (the value of maxiter seen in the stack trace) and 5768 edges. Not that big.

By the way this is in lib/common/ns.c, not lib/dotgen2/ns.c.

[emden]

Your initial graph isn't that big, but given the recursion depth, this is treesearch being run during node positioning, which includes all of the dummy nodes (clearly, at least 98109 nodes). On ubuntu, each stack frame is 48 bytes, and my stack limit is 8192 kb, so I could probably get away with it (98109*48/1000 = 4709kb), but any increase frame or decrease in stack limit, and it's over.

Actually, I have been rewriting the various recursive algorithms over the years. treesearch must be one of the few remaining ones.

[bulldozier]

What would be the side effects of adding a recursion limit to treesearch? In my application, I am willing to sacrifice quality for stability.

By the way, I have made many local changes to sacrifice quality for speed as well. I will be working on some bottlenecks that showed up in profiling runs. I will search the issue list to see if they have been filed already.

[emden]

The trade-off here is not a straightforward one between speed and quality. It is conceivable that truncating the treesearch might cause real consistency problems. If one wants to speed things up, it should be done at a higher level. Note that Graphviz already provides nslimit and nslimit1 attributes which can be used to get a non-optimal ranking. (These won't help you unless you set them to 0, since any iteration will make a call to treesearch and blow your stack. And 0 iterations would probably be acceptable for the ranking phase, but I suspect it would be unacceptable for positioning.)

There are other approaches that could be used. The one that has been in our queue for a while is to use 2 dummy nodes per edge, rather than one for each rank the edge crosses. But any of these would require serious coding.

The quickest fix here would probably be to replace the recursion with iteration.

[bulldozier]

I set nslimit and nslimit1 to 0 and this particular graph no longer crashes. Thanks for the suggestion. I can't change the stack limit (ulimit -s) because the machines it runs on are out of my control.

[magneticnorth]

Also for now you could just raise the stack size limit. In Linux or Mac OSX you can do that with a shell command.

On Oct 26, 2016, at 4:14 PM, emden notifications@github.com wrote:

The trade-off here is not a straightforward one between speed and quality. It is conceivable that truncating the treesearch might cause real consistency problems. If one wants to speed things up, it should be done at a higher level. Note that Graphviz already provides nslimit and nslimit1 attributes which can be used to get a non-optimal ranking. (These won't help you unless you set them to 0, since any iteration will make a call to treesearch and blow your stack. And 0 iterations would probably be acceptable for the ranking phase, but I suspect it would be unacceptable for positioning.)

There are other approaches that could be used. The one that has been in our queue for a while is to use 2 dummy nodes per edge, rather than one for each rank the edge crosses. But any of these would require serious coding.

The quickest fix here would probably be to replace the recursion with iteration.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/ellson/graphviz/issues/201#issuecomment-256463633, or mute the thread https://github.com/notifications/unsubscribe-auth/ACtWzwJ-ZOOzbItJUH9xQ8B4oWiLoDwqks5q37SpgaJpZM4JEm9w.