Opened 12 years ago

Closed 11 years ago

#10319 closed defect (fixed)

segmentation fault in sparse rational matrix manipulations

Reported by: 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 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 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 johanbosman 11 years ago.

Download all attachments as: .zip

Change History (13)

Changed 12 years ago by monniaux

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

comment:1 Changed 12 years ago by monniaux

  • Description modified (diff)

comment:2 Changed 12 years ago by monniaux

  • Component changed from PLEASE CHANGE to linear algebra
  • Owner changed from tbd to jason, was
  • Priority changed from major to critical

comment:3 Changed 11 years ago by dsm

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 johanbosman

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 johanbosman

  • Milestone set to sage-4.7

Changed 11 years ago by johanbosman

comment:6 Changed 11 years ago by johanbosman

  • Authors set to Johan Bosman
  • Status changed from new to needs_review

comment:7 Changed 11 years ago by dsm

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 johanbosman

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 rbeezer

  • Reviewers set to Rob Beezer
  • Status changed from needs_review to positive_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 jdemeyer

  • Milestone changed from sage-4.7.1 to sage-4.7.2

comment:11 Changed 11 years ago by jdemeyer

  • Merged in set to sage-4.7.2.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.