Ticket #4509 (new defect)

Opened 2 months ago

Last modified 2 months ago

doctests for planarity code

Reported by: jason Assigned to: ekirkman
Priority: blocker Milestone: sage-3.4
Component: graph theory Keywords:
Cc:

Description

I'm still seeing the same segfault that I worked around in the patch on #4505. Here is code that triggers it for me. 

        sage: import networkx.generators.atlas  # long time
        sage: atlas_graphs = [Graph(i) for i in networkx.generators.atlas.graph_atlas_g()] # long time
        sage: a = [i for i in [1..1252] if atlas_graphs[i].is_planar()] # long time
        sage: b = [i for i in [1..1252] if atlas_graphs[i].is_planar()] # long time

I've added that as a doctest to the planarity code.

For me, the segfault usually happens on the second run (the "b =" line), but occasionally happens on the first run.

Attachments

long-doctest-segfault.patch (1.4 kB) - added by jason on 11/12/2008 10:00:29 PM.
planarity-segfault-trip-gdb.patch (0.7 kB) - added by jason on 11/12/2008 10:14:36 PM.

Change History

11/12/2008 10:00:29 PM changed by jason

  • attachment long-doctest-segfault.patch added.

11/12/2008 10:01:22 PM changed by jason

I think this might depend on one or more of #4505 or #4506.

11/12/2008 10:04:49 PM changed by mabshoff

With #4505, #4506 and #4507 applied I get the following for the first run only, i.e. no need to run the doctests twice: 

==21687== Invalid read of size 4
==21687==    at 0x2221C301: _CreateFwdArcLists (graphEmbed.c:147)
==21687==    by 0x2221D7FD: gp_Embed (graphEmbed.c:976)
==21687==    by 0x22219199: __pyx_pf_4sage_6graphs_9planarity_is_planar (planarity.c:692)
==21687==    by 0x415832: PyObject_Call (abstract.c:1861)
==21687==    by 0x482DB9: PyEval_EvalFrameEx (ceval.c:3784)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x484AF1: PyEval_EvalFrameEx (ceval.c:494)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x48491B: PyEval_EvalFrameEx (ceval.c:3659)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x486051: PyEval_EvalCode (ceval.c:494)
==21687==    by 0x4A751D: PyRun_FileExFlags (pythonrun.c:1273)
==21687==    by 0x4A77AF: PyRun_SimpleFileExFlags (pythonrun.c:879)
==21687==    by 0x412379: Py_Main (main.c:134)
==21687==  Address 0xe2d9390 is 8 bytes before a block of size 192 alloc'd
==21687==    at 0x4A1BE1B: malloc (vg_replace_malloc.c:207)
==21687==    by 0x222220F0: gp_InitGraph (graphStructure.c:99)
==21687==    by 0x22217E00: __pyx_pf_4sage_6graphs_9planarity_is_planar (planarity.c:573)
==21687==    by 0x415832: PyObject_Call (abstract.c:1861)
==21687==    by 0x482DB9: PyEval_EvalFrameEx (ceval.c:3784)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x484AF1: PyEval_EvalFrameEx (ceval.c:494)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x48491B: PyEval_EvalFrameEx (ceval.c:3659)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x486051: PyEval_EvalCode (ceval.c:494)
==21687==    by 0x4A751D: PyRun_FileExFlags (pythonrun.c:1273)
==21687==    by 0x4A77AF: PyRun_SimpleFileExFlags (pythonrun.c:879)
==21687==    by 0x412379: Py_Main (main.c:134)
==21687== 
==21687== Invalid read of size 4
==21687==    at 0x2221C307: _CreateFwdArcLists (graphEmbed.c:153)
==21687==    by 0x2221D7FD: gp_Embed (graphEmbed.c:976)
==21687==    by 0x22219199: __pyx_pf_4sage_6graphs_9planarity_is_planar (planarity.c:692)
==21687==    by 0x415832: PyObject_Call (abstract.c:1861)
==21687==    by 0x482DB9: PyEval_EvalFrameEx (ceval.c:3784)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x484AF1: PyEval_EvalFrameEx (ceval.c:494)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x48491B: PyEval_EvalFrameEx (ceval.c:3659)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x486051: PyEval_EvalCode (ceval.c:494)
==21687==    by 0x4A751D: PyRun_FileExFlags (pythonrun.c:1273)
==21687==    by 0x4A77AF: PyRun_SimpleFileExFlags (pythonrun.c:879)
==21687==    by 0x412379: Py_Main (main.c:134)
==21687==  Address 0x21995e54 is 12 bytes before a block of size 1,344 alloc'd
==21687==    at 0x4A1BE1B: malloc (vg_replace_malloc.c:207)
==21687==    by 0x222220F0: gp_InitGraph (graphStructure.c:99)
==21687==    by 0x22217E00: __pyx_pf_4sage_6graphs_9planarity_is_planar (planarity.c:573)
==21687==    by 0x415832: PyObject_Call (abstract.c:1861)
==21687==    by 0x482DB9: PyEval_EvalFrameEx (ceval.c:3784)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x484AF1: PyEval_EvalFrameEx (ceval.c:494)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x48491B: PyEval_EvalFrameEx (ceval.c:3659)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x486051: PyEval_EvalCode (ceval.c:494)
==21687==    by 0x4A751D: PyRun_FileExFlags (pythonrun.c:1273)
==21687==    by 0x4A77AF: PyRun_SimpleFileExFlags (pythonrun.c:879)
==21687==    by 0x412379: Py_Main (main.c:134)
==21687== 
==21687== Invalid write of size 4
==21687==    at 0x2221C352: _CreateFwdArcLists (graphEmbed.c:164)
==21687==    by 0x2221D7FD: gp_Embed (graphEmbed.c:976)
==21687==    by 0x22219199: __pyx_pf_4sage_6graphs_9planarity_is_planar (planarity.c:692)
==21687==    by 0x415832: PyObject_Call (abstract.c:1861)
==21687==    by 0x482DB9: PyEval_EvalFrameEx (ceval.c:3784)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x484AF1: PyEval_EvalFrameEx (ceval.c:494)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x48491B: PyEval_EvalFrameEx (ceval.c:3659)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x486051: PyEval_EvalCode (ceval.c:494)
==21687==    by 0x4A751D: PyRun_FileExFlags (pythonrun.c:1273)
==21687==    by 0x4A77AF: PyRun_SimpleFileExFlags (pythonrun.c:879)
==21687==    by 0x412379: Py_Main (main.c:134)
==21687==  Address 0x21995e50 is 16 bytes before a block of size 1,344 alloc'd
==21687==    at 0x4A1BE1B: malloc (vg_replace_malloc.c:207)
==21687==    by 0x222220F0: gp_InitGraph (graphStructure.c:99)
==21687==    by 0x22217E00: __pyx_pf_4sage_6graphs_9planarity_is_planar (planarity.c:573)
==21687==    by 0x415832: PyObject_Call (abstract.c:1861)
==21687==    by 0x482DB9: PyEval_EvalFrameEx (ceval.c:3784)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x484AF1: PyEval_EvalFrameEx (ceval.c:494)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x48491B: PyEval_EvalFrameEx (ceval.c:3659)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x486051: PyEval_EvalCode (ceval.c:494)
==21687==    by 0x4A751D: PyRun_FileExFlags (pythonrun.c:1273)
==21687==    by 0x4A77AF: PyRun_SimpleFileExFlags (pythonrun.c:879)
==21687==    by 0x412379: Py_Main (main.c:134)
==21687== 
==21687== Invalid write of size 4
==21687==    at 0x2221C369: _CreateFwdArcLists (graphEmbed.c:165)
==21687==    by 0x2221D7FD: gp_Embed (graphEmbed.c:976)
==21687==    by 0x22219199: __pyx_pf_4sage_6graphs_9planarity_is_planar (planarity.c:692)
==21687==    by 0x415832: PyObject_Call (abstract.c:1861)
==21687==    by 0x482DB9: PyEval_EvalFrameEx (ceval.c:3784)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x484AF1: PyEval_EvalFrameEx (ceval.c:494)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x48491B: PyEval_EvalFrameEx (ceval.c:3659)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x486051: PyEval_EvalCode (ceval.c:494)
==21687==    by 0x4A751D: PyRun_FileExFlags (pythonrun.c:1273)
==21687==    by 0x4A77AF: PyRun_SimpleFileExFlags (pythonrun.c:879)
==21687==    by 0x412379: Py_Main (main.c:134)
==21687==  Address 0x21995e54 is 12 bytes before a block of size 1,344 alloc'd
==21687==    at 0x4A1BE1B: malloc (vg_replace_malloc.c:207)
==21687==    by 0x222220F0: gp_InitGraph (graphStructure.c:99)
==21687==    by 0x22217E00: __pyx_pf_4sage_6graphs_9planarity_is_planar (planarity.c:573)
==21687==    by 0x415832: PyObject_Call (abstract.c:1861)
==21687==    by 0x482DB9: PyEval_EvalFrameEx (ceval.c:3784)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x484AF1: PyEval_EvalFrameEx (ceval.c:494)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x48491B: PyEval_EvalFrameEx (ceval.c:3659)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x483F76: PyEval_EvalFrameEx (ceval.c:3669)
==21687==    by 0x485DB1: PyEval_EvalCodeEx (ceval.c:2836)
==21687==    by 0x486051: PyEval_EvalCode (ceval.c:494)
==21687==    by 0x4A751D: PyRun_FileExFlags (pythonrun.c:1273)
==21687==    by 0x4A77AF: PyRun_SimpleFileExFlags (pythonrun.c:879)
==21687==    by 0x412379: Py_Main (main.c:134)

I am now digging into which graphs cause the trouble.

Cheers,

Michael

11/12/2008 10:14:36 PM changed by jason

  • attachment planarity-segfault-trip-gdb.patch added.

11/12/2008 10:15:51 PM changed by jason

planarity-segfault-trip-gdb.patch is a patch which supplies a poor man's assert: we see the problem when Jfirst is -1 *and* when the random memory location happens to be 2. The patch causes a segfault whenever Jfirst is -1.

11/12/2008 10:37:32 PM changed by jason 

[00:30] <mabshoff> jason--: looks like there is nothing major in the planarity code leak wise.
[00:30] <jason--> that's good.
[00:30] <jason--> can you post a note to that effect?
[00:31] <mabshoff> Maybe 100 bytes or so for running all 1200 graphs five times.

11/12/2008 11:17:21 PM changed by mabshoff

The issue pops up seemingly randomly, i.e. under valgrind there are complete runs that are ok while with others some tests cause the problem, but seemingly never the same test, i.e. the order is seemingly random. Jason has a theory what needs to happen for the issue to be triggered.

Cheers,

Michael

11/13/2008 08:07:39 AM changed by jason

From an email to John Boyer:

Going back to the graphEmbed.c file, the _CreateFwdArcLists function, it seems that theGraph->G[I].link[1] is -1 (i.e., is NIL) exactly when the vertex I has degree 0. Do you assume that the input graph does not have any isolated vertices?

I think the reason we get random segfaults is because when Jfirst is -1, the if statement in this function is true depending on values associated with G[-1], which is a random value outside of our array.

I see two possible fixes. If you have a different fix, we would love to hear it.

1. insert the lines: 

if(Jfirst<0) {
    continue;
}

right after Jfirst is assigned (i.e., Jfirst = theGraph->G[I].link[1];)

I believe this skips vertices that have degree 0. Will the algorithm work correctly with this modification?

2. Delete any vertices of degree 0 from the graph before calling the algorithm. Of course, this does not change the planarity of the graph. However, I couldn't find this limitation documented anywhere, and your paper says that the algorithm works for disconnected graphs. Am I correct in assuming that incorrect handling of degree 0 vertices is the problem here?

Do you have any suggestions for which fix would be better? If fix #1 works, I prefer that one, as it is less preparation work before calling your code.

11/14/2008 06:57:30 PM changed by ekirkman

  • owner changed from rlm to ekirkman.

Hi. I just responded to Jason's email, but I'll post here too. The Boyer/Myrvold algorithm requires the graph be connected so for the workaround we need to look at each of the connected components of the graph. I can make a patch on Sunday, but I'd be happy to review anything you guys come up with before then.

11/15/2008 03:04:21 AM changed by mabshoff

  • milestone changed from sage-3.2 to sage-3.2.1.