segmentation fault in sparse rational matrix manipulations

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

---

[David Monniaux]

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

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

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

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

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

[Rob Beezer]

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.