Opened 12 years ago

Closed 11 years ago

#10319 closed defect (fixed)

segmentation fault in sparse rational matrix manipulations

Reported by: David Monniaux Owned by: jason, was
Priority: critical Milestone: sage-4.7.2
Component: linear algebra Keywords:
Cc: Merged in: sage-4.7.2.alpha1
Authors: Johan Bosman Reviewers: Rob Beezer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by David Monniaux)

See attachment. The following program crashes with segmentation fault on Sage 4.6 / Linux Ubuntu 10.04 x86 32-bit

$ sage essai1.sage [...] block 1 is not sdp echelonizing echelonized


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).


Attachments (2)

sage_crash.tgz (5.8 KB) - added by David Monniaux 12 years ago.
tarball of sage scripts; run sage essai1.sage for crash
trac_10319_sparse_echelon_fix.patch (2.1 KB) - added by Johan Bosman 11 years ago.

Download all attachments as: .zip

Change History (13)

Changed 12 years ago by David Monniaux

Attachment: sage_crash.tgz added

tarball of sage scripts; run sage essai1.sage for crash

comment:1 Changed 12 years ago by David Monniaux

Description: modified (diff)

comment:2 Changed 12 years ago by David Monniaux

Component: PLEASE CHANGElinear algebra
Owner: changed from tbd to jason, was
Priority: majorcritical

comment:3 Changed 12 years ago by D.S. McNeil

Running the code under 4.6.2 on OS X doesn't segfault but generates a TypeError? for me:

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

However, if you load the code *again*, it crashes: the second time's the strange.

This is the smallest test case I can come up with:

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).
------------------------------------------------------------

comment:4 Changed 11 years ago by Johan Bosman

The problem is in /sage/matrix/matrix_rational_sparse.pyx in the function _echelonize_multimodular:

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()

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.

comment:5 Changed 11 years ago by Johan Bosman

Milestone: sage-4.7

Changed 11 years ago by Johan Bosman

comment:6 Changed 11 years ago by Johan Bosman

Authors: Johan Bosman
Status: newneeds_review

comment:7 Changed 11 years ago by D.S. McNeil

The patch fixes the reduced case for me, and doesn't segfault in the original test case even under multiple invocations. (I think the TypeError? is unrelated.)

I think there should be two colons at the end of "Trac #10319 has been fixed:", but I seem to get this wrong every time..

comment:8 Changed 11 years ago by Johan Bosman

Yes, I focussed on the segfault given by the minimum example. The TypeError? might not even be a bug.

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.

comment:9 Changed 11 years ago by Rob Beezer

Reviewers: Rob Beezer
Status: needs_reviewpositive_review

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.

Yes, a double-colon would be needed to set off the code block for the bug-fix-verification addition. sage/matrix/matrix_rational_sparse.pyx 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.

So: positive review.

comment:10 Changed 11 years ago by Jeroen Demeyer

Milestone: sage-4.7.1sage-4.7.2

comment:11 Changed 11 years ago by Jeroen Demeyer

Merged in: sage-4.7.2.alpha1
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.