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)

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

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

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by lachlan (Updated the item)
  • -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 4 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Sat 16 Jan 2016 03:31:03 AM UTClachlanAttached File-=>Added bug_42850.cset, #36055
    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