bugGNU Octave - Bugs: bug #40739, Attempt to allocate (size_t)-1...

 
 

bug #40739: Attempt to allocate (size_t)-1 bytes when trying to length-INT_MAX create sparse vector

Submitted by:  Philipp Kutin <pkutin>
Submitted on:  Thu 28 Nov 2013 03:30:39 PM UTC  
 
Category: InterpreterSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Other
Status: ConfirmedAssigned to: None
Originator Name: Open/Closed: Open
Release: devOperating System: GNU/Linux

Add a New Comment(Rich Markup)
   

You are not logged in

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

 

Fri 25 Nov 2016 10:10:37 PM UTC, comment #5:

I am not sure if this behavior is still present in Octave 4.2.0. It might well be FIXED already.

  • The original code sample now works like this:
  • The code sample from comment #2 now works like this:

I don't recognize any buggy behavior in the above, but I'm no sparse matrix expert either...

Hartmut <hardy>
Fri 06 Dec 2013 08:31:12 PM UTC, comment #4:

Gotta take a step back here, my initial report was posted a bit in a hurry. The reason I sounded so alert was because I had a wrong mental model of sparse matrices. I though that they were implemented using basically a list (as an abstract, not implementation data type) to hold pairs of [column, row] indices. But it seems the structure is that you have one array of length #columns, and that one carries arrays of sparse-data indices, indexing SparseRep.d[].

So, rows/colums aren't "symmetrical" as I have thought and the 2^31-1 case is a bit cornerly: creating very long row vectors is conceptually fine, but probably isn't that useful anyway.
(For example, issuing "s=sparse(1,2^30,123)" creates such a "sparse vector", but allocates 4 GiB and takes a while to run (well, on the sanitized build, which doesn't say much).

So corner cases at the limits of the allocation maximum indices are one thing, but now, it's the earlier second comment (https://savannah.gnu.org/bugs/?40739#comment2) that I consider more severe: after all, that one means you silently get wrong indices and Octave doesn't tell you. Should a new bug be opened for that one?

Philipp Kutin <pkutin>
Mon 02 Dec 2013 10:04:41 PM UTC, comment #3:

Confirmed. I didn't use an address sanitizer and the behavior seems to be that Octave really does try and allocate 2^31-1 entries; This threw my computer into a swap disaster and I was lucky to be able to get to a shell prompt eventually and kill the process.

Rik <rik5>
Project Administrator
Thu 28 Nov 2013 07:54:16 PM UTC, comment #2:

More sparse badness...

Need to sort my thoughts to write a larger rant about these (or rather, reply to bug #40712), but for now it seems that linear indices should be avoided for sparse arrays whose #cols*#rows product overflows an int.

On the positive side, it sure is nice that stuff works even for say, 300k-by-300k sparse matrices, as long as you take care not to deal with linear indices.

Philipp Kutin <pkutin>
Thu 28 Nov 2013 03:33:23 PM UTC, comment #1:

Attaching the same transcript as a file, since the bug tracker formatting inserts linebreaks...

(file #29728)

Philipp Kutin <pkutin>
Thu 28 Nov 2013 03:30:39 PM UTC, original submission:

Just stubled on this one when I was attempting to reproduce the failures described at
https://savannah.gnu.org/bugs/?40712

I'm trying to create a sparse vector of overlong length. 2^32 gives integer UBs. But the interesting case is 2^31-1. It seems that 1 is added to this number, and the result is attempted to be used as an allocation count!!!

Prompt transcript follows. Note that because I compiled with AddressSanitizer, its replacement allocator chose to bail out; I haven't tested what would happen in a normal build. But in any case, overflows in indexes and the like is not clean.

Running this on a x86_64 machine, but with the default Octave index type (32-bit signed int, as it seems).

----------

Philipp Kutin <pkutin>

 

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

Attach File(s):
   
   
Comment:
   

Attached Files
file #29728:  alloc_minus_one.log added by pkutin (7KiB - text/x-log)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by hardy (Posted a comment)
  • -unavailable- added by rik5 (Posted a comment)
  • -unavailable- added by pkutin (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 2 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Mon 02 Dec 2013 10:04:41 PM UTCrik5StatusNone=>Confirmed
    Thu 28 Nov 2013 03:33:23 PM UTCpkutinAttached File-=>Added alloc_minus_one.log, #29728

    Back to the top


    Powered by Savane 3.1-cleanup1