Context Navigation

← Previous Ticket
Next Ticket →

Ticket #11814 (new defect)

Last modified 9 months ago

Segmentation fault in dlx_solver

Reported by:	jdemeyer	Owned by:	sage-combinat
Priority:	critical	Milestone:	sage-5.10
Component:	combinatorics	Keywords:
Cc:	slabbe	Work issues:
Report Upstream:	N/A	Reviewers:
Authors:		Merged in:
Dependencies:		Stopgaps:

Description (last modified by jdemeyer) (diff)

On a 64-bit Gentoo Linux system running sage-4.7.2.alpha2:

sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: rows = []
sage: x = dlx_solver(rows)
sage: x.search()
/usr/local/src/sage-4.7.2.alpha2/local/lib/libcsage.so(print_backtrace+0x31)[0x7f6c37015e02]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libcsage.so(sigdie+0x14)[0x7f6c37015e34]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libcsage.so(sage_signal_handler+0x20c)[0x7f6c37015a82]
/lib/libpthread.so.0(+0xf400)[0x7f6c3c26e400]
/usr/local/src/sage-4.7.2.alpha2/local/lib/python2.6/site-packages/sage/combinat/matrices/dancing_links.so(+0x738b)[0x7f6c1612f38b]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x4c32)[0x7f6c3c55d842]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCode+0x32)[0x7f6c3c55f912]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x4ccb)[0x7f6c3c55d8db]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x5364)[0x7f6c3c55df74]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x5364)[0x7f6c3c55df74]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x5a8a)[0x7f6c3c55e69a]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x5364)[0x7f6c3c55df74]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x5364)[0x7f6c3c55df74]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x5364)[0x7f6c3c55df74]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCodeEx+0x879)[0x7f6c3c55f819]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalCode+0x32)[0x7f6c3c55f912]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyRun_FileExFlags+0xb0)[0x7f6c3c581d20]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyRun_SimpleFileExFlags+0xdf)[0x7f6c3c58275f]
/usr/local/src/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(Py_Main+0xb23)[0x7f6c3c58fa23]
/lib/libc.so.6(__libc_start_main+0xe6)[0x7f6c3b897ba6]
python[0x4006e9]

------------------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component of Sage has a bug
in it and is not properly wrapped with sig_on(), sig_off(). You might
want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate.
------------------------------------------------------------------------

Note that this behaviour is actually documented in sage/combinat/tiling.py:

    def is_suitable(self):
        r"""
        Return whether the volume of the box is equal to sum of the volume
        of the polyominoes and the number of rows sent to the DLX solver is
        larger than zero.

        If these conditions are not verified, then the problem is not suitable
        in the sense that there are no solution.

        .. NOTE::

            The DLX solver throws a Segmentation Fault when the
            number of rows is zero::

                sage: from sage.combinat.matrices.dancing_links import dlx_solver
                sage: rows = []
                sage: x = dlx_solver(rows)
                sage: x.search()        # not tested
                BOOM !!!

For sage-on-gentoo, there is an assertion failure:

sage:  x = dlx_solver(rows)
python2.7: sage/combinat/matrices/dancing_links_c.h:217: void dancing_links::setup_columns(): Assertion `nr_columns > 0' failed.
/usr/lib64/libcsage.so(print_backtrace+0x24)[0x7fea73a945f7]
/usr/lib64/libcsage.so(sigdie+0x1d)[0x7fea73a94687]
/usr/lib64/libcsage.so(sage_signal_handler+0x157)[0x7fea73a94822]
/lib64/libpthread.so.0(+0xfee0)[0x7fea79206ee0]
/lib64/libc.so.6(gsignal+0x35)[0x7fea78ea5ee5]
/lib64/libc.so.6(abort+0x186)[0x7fea78ea7896]
/lib64/libc.so.6(__assert_fail+0xf5)[0x7fea78e9e7a5]
/usr/lib64/python2.7/site-packages/sage/combinat/matrices/dancing_links.so(+0x855d)[0x7fea4e73255d]

Change History

comment:1 Changed 20 months ago by leif

A bit more information on the platform, or did you try this on different systems?

On Ubuntu 10.04.3 x86_64 I get:

...
sage: sage: from sage.combinat.matrices.dancing_links import dlx_solver
==27537== Invalid read of size 4
==27537==    at 0x4EB5E83: PyObject_Free (obmalloc.c:931)
==27537==    by 0x4EDBE00: unicode_dealloc (unicodeobject.c:369)
==27537==    by 0x4E9C8E0: frame_dealloc (frameobject.c:420)
==27537==    by 0x4F1562E: PyEval_EvalCodeEx (ceval.c:2979)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==  Address 0x6156020 is 2,256 bytes inside a block of size 4,400 free'd
==27537==    at 0x4C27058: realloc (vg_replace_malloc.c:525)
==27537==    by 0x9F13E6A: xrealloc (xmalloc.c:74)
==27537==    by 0x9F1442E: add_history (history.c:302)
==27537==    by 0x9F1761F: read_history_range (histfile.c:270)
==27537==    by 0x9CE3089: read_history_file (readline.c:102)
==27537==    by 0x4F13E19: PyEval_EvalFrameEx (ceval.c:3706)
==27537==    by 0x4F14CEE: PyEval_EvalFrameEx (ceval.c:3792)
==27537==    by 0x4F14CEE: PyEval_EvalFrameEx (ceval.c:3792)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4E9DC2A: function_call (funcobject.c:524)
==27537== 
==27537== Invalid read of size 4
==27537==    at 0x4EB5E83: PyObject_Free (obmalloc.c:931)
==27537==    by 0x4E68C66: freechildren (node.c:135)
==27537==    by 0x4E68FAD: PyNode_Free (node.c:123)
==27537==    by 0x4F370C8: PyParser_ASTFromString (pythonrun.c:1439)
==27537==    by 0x4F37221: Py_CompileStringFlags (pythonrun.c:1382)
==27537==    by 0x4F0CE6B: builtin_compile (bltinmodule.c:546)
==27537==    by 0x4F13E19: PyEval_EvalFrameEx (ceval.c:3706)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4E9DB2E: function_call (funcobject.c:524)
==27537==    by 0x4E741A1: PyObject_Call (abstract.c:2492)
==27537==    by 0x4E868BC: instancemethod_call (classobject.c:2579)
==27537==    by 0x4E741A1: PyObject_Call (abstract.c:2492)
==27537==  Address 0xa73d020 is not stack'd, malloc'd or (recently) free'd
==27537== 
sage: sage: rows = []
sage: sage: x = dlx_solver(rows)
sage: sage: x.search()
==27537== Conditional jump or move depends on uninitialised value(s)
==27537==    at 0x2F2C3281: __pyx_pf_4sage_8combinat_8matrices_13dancing_links_20dancing_linksWrapper_9search(_object*, _object*) (dancing_links_c.h:75)
==27537==    by 0x4F13B46: PyEval_EvalFrameEx (ceval.c:3690)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F15A21: PyEval_EvalCode (ceval.c:522)
==27537==    by 0x4F14510: PyEval_EvalFrameEx (ceval.c:4401)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F14CEE: PyEval_EvalFrameEx (ceval.c:3792)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537== 
==27537== Use of uninitialised value of size 8
==27537==    at 0x2F2C32AA: __pyx_pf_4sage_8combinat_8matrices_13dancing_links_20dancing_linksWrapper_9search(_object*, _object*) (dancing_links_c.h:76)
==27537==    by 0x4F13B46: PyEval_EvalFrameEx (ceval.c:3690)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F15A21: PyEval_EvalCode (ceval.c:522)
==27537==    by 0x4F14510: PyEval_EvalFrameEx (ceval.c:4401)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F14CEE: PyEval_EvalFrameEx (ceval.c:3792)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537== 
==27537== Conditional jump or move depends on uninitialised value(s)
==27537==    at 0x2F2C32A8: __pyx_pf_4sage_8combinat_8matrices_13dancing_links_20dancing_linksWrapper_9search(_object*, _object*) (dancing_links_c.h:76)
==27537==    by 0x4F13B46: PyEval_EvalFrameEx (ceval.c:3690)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F15A21: PyEval_EvalCode (ceval.c:522)
==27537==    by 0x4F14510: PyEval_EvalFrameEx (ceval.c:4401)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F14CEE: PyEval_EvalFrameEx (ceval.c:3792)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537== 
==27537== Conditional jump or move depends on uninitialised value(s)
==27537==    at 0x2F2C3291: __pyx_pf_4sage_8combinat_8matrices_13dancing_links_20dancing_linksWrapper_9search(_object*, _object*) (dancing_links_c.h:76)
==27537==    by 0x4F13B46: PyEval_EvalFrameEx (ceval.c:3690)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F15A21: PyEval_EvalCode (ceval.c:522)
==27537==    by 0x4F14510: PyEval_EvalFrameEx (ceval.c:4401)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F14CEE: PyEval_EvalFrameEx (ceval.c:3792)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537== 
==27537== Invalid read of size 4
==27537==    at 0x2F2C328C: __pyx_pf_4sage_8combinat_8matrices_13dancing_links_20dancing_linksWrapper_9search(_object*, _object*) (dancing_links_c.h:76)
==27537==    by 0x4F13B46: PyEval_EvalFrameEx (ceval.c:3690)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F15A21: PyEval_EvalCode (ceval.c:522)
==27537==    by 0x4F14510: PyEval_EvalFrameEx (ceval.c:4401)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==    by 0x4F14CEE: PyEval_EvalFrameEx (ceval.c:3792)
==27537==    by 0x4F15947: PyEval_EvalCodeEx (ceval.c:2968)
==27537==    by 0x4F13BF3: PyEval_EvalFrameEx (ceval.c:3802)
==27537==  Address 0x30 is not stack'd, malloc'd or (recently) free'd
==27537== 
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libcsage.so(print_backtrace+0x31)[0xbfa6817]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libcsage.so(sigdie+0x14)[0xbfa6849]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libcsage.so(sage_signal_handler+0x20e)[0xbfa6474]
/lib/libpthread.so.0(+0xf8f0)[0x52018f0]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/python2.6/site-packages/sage/combinat/matrices/dancing_links.so(+0x828c)[0x2f2c328c]
/tmp/Sage/sage-4.7.2.alpha2/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x4af7)[0x4f13b47]
... (same backtrace)

comment:2 Changed 20 months ago by jdemeyer

Description modified (diff)

comment:3 Changed 9 months ago by slabbe

Cc slabbe added

Note: See TracTickets for help on using tickets.

Download in other formats: