bugGNU Octave - Bugs: bug #42850, Reshape on sparse matrix leads to...

 
 

bug #42850: Reshape on sparse matrix leads to segfault

Submitter:  David Spies <dspyz>
Submitted:  Sat 26 Jul 2014 06:20:19 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Segfault, Bus Error, etc.
Status:  Fixed Assigned to:  lachlan
Originator Name:  Open/Closed:  * Closed
Release:  * dev Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Sun 14 Feb 2016 05:21:13 PM UTC, comment #8: 

I applied Lachlan's patch to the stable branch here (http://hg.savannah.gnu.org/hgweb/octave/rev/a93fa1b0796e).  Closing report.

Rik <rik5>
Group administrator
Sat 16 Jan 2016 03:31:03 AM UTC, comment #7: 

Rik had the right idea with pulling the division by new_nr in sooner.  The attached patch does that.  It keeps track of the quotient and remainder for  i*old_nr  divided by new_nr.  Because much of this is done in the outer loop, it should be even faster than using the cute floating point code on Wikipedia, as well as being easier to understand (IMHO).

(Just to check my understanding, why was jj calculated as (tmp - ii) / nr?  Isn't that equal to tmp/nr, since ii is by definition just the remainder?  If not, don't trust my patch :)

I've tested it on 10000 reshapes, and the results appear to be the same as for a full reshape.

This doesn't explain why David Spies was able to do the reshape without a crash in the first place.  Perhaps it was just pointing to some relatively safe wrong place initially.  I did print out the matrix just to make sure I didn't get the broken pipe that he did.

(file #36055)

Lachlan Andrew <lachlan>
Sun 17 Aug 2014 09:07:05 AM UTC, comment #6: 

Hi,

I think that the simplest and fastest way is to use float numbers for the intermediate results, as written here

http://en.wikipedia.org/wiki/Modular_arithmetic

(last algorithm).

Cheers,

Marco

Marco Caliari <caliari>
Group Member
Thu 14 Aug 2014 12:28:25 AM UTC, comment #5: 

Forget the last 3 sentences. Obviously the input matrix cannot have more elements than actually can be indexed so it has nothing to do with reshape. Sorry. Anyway the first two sentences stay valid.

Eduardo Ramos Fernández <edu159>
Thu 14 Aug 2014 12:19:42 AM UTC, comment #4: 

Yes, I have been thinking a bit about a solution but it did not came up. Matlab can handle those situations with no problem. Another thing is if nnz(b) > 2^30. In this case the reshape should not be success because at least cidx[end] will be always overflowed in a Sparse matrix. I have not tested that on Matlab.

Eduardo Ramos Fernández <edu159>
Wed 13 Aug 2014 09:10:48 PM UTC, comment #3: 

Maybe not a fix, but at a minimum Octave should detect that tmp has overflowed and error out rather than continuing on to segfault.  I made that change on the stable branch in this changeset (http://hg.savannah.gnu.org/hgweb/octave/rev/35097be5007c).

I think the long term fix is to see if the division by new_nr can be pulled in to the calculation sooner so that the full product of old_nc x old_nr is never seen.






Rik <rik5>
Group administrator
Wed 13 Aug 2014 05:33:27 PM UTC, comment #2: 

I have been taking a look at the problem and the issue is located within the reshape method of Sparse<T> class. In Sparse.cc around line 845:



 for (octave_idx_type i = 0; i < old_nc; i++)
            for (octave_idx_type j = cidx (i); j < cidx (i+1); j++)
              {
                *octave_idx_type tmp = i * old_nr + ridx (j);*
                octave_idx_type ii = tmp % new_nr;
                octave_idx_type jj = (tmp - ii) / new_nr;
                for (octave_idx_type k = kk; k < jj; k++)
                  retval.xcidx (k+1) = j;
                kk = jj;
                retval.xdata (j) = data (j);
                retval.xridx (j) = ii;
              }


With an example similar to the David's one, a segfault is obtained just by the time is executed.

b = logical(speye(1000000));
c = reshape(b,200000,5000000);

The problem is the variable tmp, that can become negative due to integer overflowing. In the example old_nr = 1000000 and i take values up to old_nc=1000000. So their product can be greater than 2^30 = 1.0737e+09.

I don't really know how to fix this in a proper way without using 64 bits. Maybe other knows a quick fix.



Eduardo Ramos Fernández <edu159>
Mon 28 Jul 2014 06:12:20 AM UTC, comment #1: 

Confirmed.  This has been a problem for quite a while because I checked versions of Octave back to 3.2.4 and they all exhibit the problem.

Rik <rik5>
Group administrator
Sat 26 Jul 2014 06:20:19 PM UTC, original submission:  

octave:1> b = logical(speye(100000));
octave:2> c = reshape(b,200000,50000);
octave:3> c
c =

Compressed Column Sparse (rows = 200000, cols = 50000, nnz = 100000 [0.001%])

  (-148694, 1) ->  1
  (-48693, 1) ->  1
  (51308, 1) ->  1
  (151309, 1) ->  1
  (51310, 2) ->  1
  (151311, 2) ->  1
  (51312, 3) ->  1
  (151313, 3) ->  1
  (51314, 4) ->  1
  (151315, 4) ->  1
  (51316, 5) ->  1
  (151317, 5) ->  1
  (51318, 6) ->  1
  (151319, 6) ->  1
  (51320, 7) ->  1
  (151321, 7) ->  1
  (51322, 8) ->  1
  (151323, 8) ->  1
  (51324, 9) ->  1
warning: broken pipe
octave:4> exit

attempting to save variables to 'octave-workspace'...
panic: Segmentation fault -- stopping myself...
attempting to save variables to 'octave-workspace'...
octave exited with signal 11

David Spies <dspyz>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #36055:  bug_42850.cset added by lachlan (2KiB - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by lachlan (Updated the item)
  • -email is unavailable- added by caliari (Posted a comment)
  • -email is unavailable- added by edu159 (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by dspyz (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 9 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2016-02-14 rik5 StatusReady For Test Fixed
        Open/ClosedOpen Closed
    2016-02-08 lachlan Assigned toNone lachlan
    2016-02-08 lachlan StatusConfirmed Ready For Test
        Operating SystemGNU/Linux Any
    2016-01-16 lachlan Attached File- Added bug_42850.cset, #36055
    2014-07-28 rik5 Item GroupIncorrect Result Segfault, Bus Error, etc.
        StatusNone Confirmed
        SummaryReshape does something weird with sparse matrix Reshape on sparse matrix leads to segfault

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code