#11814: Segmentation fault in dlx_solver
---------------------------------+-----------------------------
Reporter: jdemeyer | Owner: sage-combinat
Type: defect | Status: new
Priority: critical | Milestone: sage-5.13
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
---------------------------------+-----------------------------
Description changed by boothby:
Old description:
> 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]
> }}}
New description:
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]
}}}
Additionally, we can segfault with a different kind of trivial problem,
{{{
sage: from sage.combinat.matrices.dancing_links import dlx_solver
sage: d = dlx([[]])
sage: d.search()
*boom!*
}}}
And even adding rows can be a problem... this doesn't always go boom
{{{
sage: d = dlx_solver([[0,1],[2]])
sage: d.add_rows([[0,1],[1]])
*boom!*
}}}
Actually... *why the hell* would we ever support the following:
{{{
sage: d = dlx_solver(anything)
sage: d.search()
sage: d.add_rows(anything else)
}}}
--
--
Ticket URL: <http://trac.sagemath.org/ticket/11814#comment:6>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
