Sage: Ticket #10319: segmentation fault in sparse rational matrix manipulations
https://trac.sagemath.org/ticket/10319
<p>
See attachment. The following program crashes with segmentation fault on Sage 4.6 / Linux Ubuntu 10.04 x86 32-bit
</p>
<p>
$ sage essai1.sage
[...]
block 1
is not sdp
echelonizing
echelonized
</p>
<hr />
<p>
Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component
of Sage has a bug in it (typically accessing invalid memory)
or 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 (sorry).
</p>
<hr />
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/10319
Trac 1.2David MonniauxWed, 24 Nov 2010 11:58:11 GMTattachment set
https://trac.sagemath.org/ticket/10319
https://trac.sagemath.org/ticket/10319
<ul>
<li><strong>attachment</strong>
set to <em>sage_crash.tgz</em>
</li>
</ul>
<p>
tarball of sage scripts; run sage essai1.sage for crash
</p>
TicketDavid MonniauxWed, 24 Nov 2010 11:59:41 GMTdescription changed
https://trac.sagemath.org/ticket/10319#comment:1
https://trac.sagemath.org/ticket/10319#comment:1
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/10319?action=diff&version=1">diff</a>)
</li>
</ul>
TicketDavid MonniauxThu, 25 Nov 2010 22:11:29 GMTpriority, owner, component changed
https://trac.sagemath.org/ticket/10319#comment:2
https://trac.sagemath.org/ticket/10319#comment:2
<ul>
<li><strong>priority</strong>
changed from <em>major</em> to <em>critical</em>
</li>
<li><strong>owner</strong>
changed from <em>tbd</em> to <em>jason, was</em>
</li>
<li><strong>component</strong>
changed from <em>PLEASE CHANGE</em> to <em>linear algebra</em>
</li>
</ul>
TicketD.S. McNeilWed, 09 Mar 2011 16:23:50 GMT
https://trac.sagemath.org/ticket/10319#comment:3
https://trac.sagemath.org/ticket/10319#comment:3
<p>
Running the code under 4.6.2 on OS X doesn't segfault but generates a <a class="missing wiki">TypeError?</a> for me:
</p>
<pre class="wiki">Traceback (most recent call last):
File "essai1.py", line 21, in <module>
solution = solve_sos_equation(polynomial_ring, positive_polynomials, positive_monomial_lists, equality_polynomials, equality_monomial_lists, rhs_polynomial)
File "<string>", line 181, in solve_sos_equation
File "<string>", line 28, in left_near_kernel
File "/Applications/sage_devel/local/lib/python2.6/site-packages/sage/matrix/constructor.py", line 2079, in block_matrix
raise TypeError("invalid block_matrix invocation")
TypeError: invalid block_matrix invocation
</pre><p>
However, if you load the code *again*, it crashes: the second time's the strange.
</p>
<p>
This is the smallest test case I can come up with:
</p>
<pre class="wiki">sage: m = Matrix(QQ, [1], sparse=True)
sage: m.echelonize()
sage: m
[1]
sage: m = Matrix(QQ, [1], sparse=True)
sage: m.echelonize()
sage: m
------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component
of Sage has a bug in it (typically accessing invalid memory)
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 (sorry).
------------------------------------------------------------
</pre>
TicketJohan BosmanFri, 08 Apr 2011 18:29:31 GMT
https://trac.sagemath.org/ticket/10319#comment:4
https://trac.sagemath.org/ticket/10319#comment:4
<p>
The problem is in /sage/matrix/matrix_rational_sparse.pyx in the function _echelonize_multimodular:
</p>
<pre class="wiki">def _echelonize_multimodular(self, height_guess=None, proof=True, **kwds):
cdef Matrix_rational_sparse E
E = self._echelon_form_multimodular(height_guess, proof=proof, **kwds)
# Get rid of self's data
self._dealloc()
# Change self's data to point to E's.
self._matrix = E._matrix
# Make sure that E's destructor doesn't delete self's data.
E._matrix = NULL
E._initialized = False
return E.pivots()
</pre><p>
E._matrix is set to NULL, while E may be a matrix that is in use somewhere else. In the example given, it will be the identity matrix, which is cached in its parent. During the first m.echelonize(), E._matrix is set to NULL where E is the cached identity matrix. This will cause segfaults. During the second m.echelonize() in the example, m._matrix is set to E._matrix and thus to NULL.
</p>
TicketJohan BosmanFri, 08 Apr 2011 18:39:15 GMTmilestone set
https://trac.sagemath.org/ticket/10319#comment:5
https://trac.sagemath.org/ticket/10319#comment:5
<ul>
<li><strong>milestone</strong>
set to <em>sage-4.7</em>
</li>
</ul>
TicketJohan BosmanSun, 10 Apr 2011 15:48:01 GMTattachment set
https://trac.sagemath.org/ticket/10319
https://trac.sagemath.org/ticket/10319
<ul>
<li><strong>attachment</strong>
set to <em>trac_10319_sparse_echelon_fix.patch</em>
</li>
</ul>
TicketJohan BosmanSun, 10 Apr 2011 15:48:28 GMTstatus changed; author set
https://trac.sagemath.org/ticket/10319#comment:6
https://trac.sagemath.org/ticket/10319#comment:6
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
set to <em>Johan Bosman</em>
</li>
</ul>
TicketD.S. McNeilSun, 10 Apr 2011 16:58:05 GMT
https://trac.sagemath.org/ticket/10319#comment:7
https://trac.sagemath.org/ticket/10319#comment:7
<p>
The patch fixes the reduced case for me, and doesn't segfault in the original test case even under multiple invocations. (I think the <a class="missing wiki">TypeError?</a> is unrelated.)
</p>
<p>
I think there should be two colons at the end of "Trac <a class="closed ticket" href="https://trac.sagemath.org/ticket/10319" title="#10319: defect: segmentation fault in sparse rational matrix manipulations (closed: fixed)">#10319</a> has been fixed:", but I seem to get this wrong every time..
</p>
TicketJohan BosmanSun, 10 Apr 2011 17:27:54 GMT
https://trac.sagemath.org/ticket/10319#comment:8
https://trac.sagemath.org/ticket/10319#comment:8
<p>
Yes, I focussed on the segfault given by the minimum example. The <a class="missing wiki">TypeError?</a> might not even be a bug.
</p>
<p>
I must admit that I haven't really understood the docstring formatting either. Probably it is only relevant for the html output, which isn't generated for this file anyway.
</p>
TicketRob BeezerWed, 27 Jul 2011 17:16:40 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/10319#comment:9
https://trac.sagemath.org/ticket/10319#comment:9
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Rob Beezer</em>
</li>
</ul>
<p>
This looks real good. I have the symptom (the reproducible segfault) on my machine and this is a cure. And the code looks sound. Passes all long tests on 4.7.1.alpha4.
</p>
<p>
Yes, a double-colon would be needed to set off the code block for the bug-fix-verification addition. <code>sage/matrix/matrix_rational_sparse.pyx</code> is a total mess with regard to documentation and is not even being included in the PDF or HTML versions right now. So I see little point in messing around with an additional patch to clean that up -- the whole file needs work. I've put it on my to-do list.
</p>
<p>
So: positive review.
</p>
TicketJeroen DemeyerThu, 28 Jul 2011 10:27:18 GMTmilestone changed
https://trac.sagemath.org/ticket/10319#comment:10
https://trac.sagemath.org/ticket/10319#comment:10
<ul>
<li><strong>milestone</strong>
changed from <em>sage-4.7.1</em> to <em>sage-4.7.2</em>
</li>
</ul>
TicketJeroen DemeyerTue, 02 Aug 2011 19:44:57 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/10319#comment:11
https://trac.sagemath.org/ticket/10319#comment:11
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.7.2.alpha1</em>
</li>
</ul>
Ticket