[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 #201 (comment), 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 #201 (comment), or mute the thread https://github.com/notifications/unsubscribe-auth/ACtWzwJ-ZOOzbItJUH9xQ8B4oWiLoDwqks5q37SpgaJpZM4JEm9w.