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

 
 

bug #42850: Reshape on sparse matrix leads to segfault

Submitted by:  David Spies <dspyz>
Submitted on:  Sat 26 Jul 2014 06:20:19 PM UTC  
 
Category: Octave FunctionSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Crash
Status: ConfirmedAssigned to: None
Originator Name: Open/Closed: Open
Release: devOperating System: GNU/Linux

Add a New Comment (Rich MarkupRich Markup):
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission Jump to the original submission)

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>
Project 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>
Project 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:

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>
Project 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 File(s):
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 3 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Mon 28 Jul 2014 06:12:20 AM UTCrik5Item GroupIncorrect Result=>Crash
      StatusNone=>Confirmed
      SummaryReshape does something weird with sparse matrix=>Reshape on sparse matrix leads to segfault

    Back to the top


    Powered by Savane 3.1-cleanup