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

Submitter:  Philipp Kutin <pkutin>
Submitted:  Thu 28 Nov 2013 03:30:39 PM UTC
   
 
Category:  Interpreter Severity:  3 - Normal
Priority:  3 - Low Item Group:  Other
Status:  Confirmed Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * dev Operating System:  * GNU/Linux
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Wed 25 Aug 2021 03:01:21 PM UTC, comment #7: 

Re-opening bug report.  This bug is still present, but no longer encountered frequently because Octave has switched to using a default octave_idx_type of 64 bits.  The logic in the code, however, is still wrong.

To test, configure Octave with '--disable-64'.  Running the second example I get


octave:1> s = sparse(2^16,2^16,123)
s =

Compressed Column Sparse (rows = 65536, cols = 65536, nnz = 1 [2.3e-08%])

  (65536, 65536) -> 123

octave:2> find (s)
ans = 0


This is not right.  The smallest linear index in Octave is 1 corresponding to the first element in an array.

Could discuss over on Discourse what we want to do.  As I said, almost no one encounters this any more because the octave_idx_type is now huge.  Maybe the decision, therefore, is to just leave this bug open but not spend developer time on it.

Otherwise, there are ways to fix this including not allowing the creation of matrices that exceed a certain size, or switching to using doubles for large indexing (this would set the limit at flintmax [2^53]) for operations where we know the capacity of octave_idx_type would be exceeded.

Rik <rik5>
Group administrator
Wed 25 Aug 2021 06:43:28 AM UTC, comment #6: 

No trouble with Octave 6.3.0 either.  Closing as fixed.

Kai Torben Ohlhus <siko1056>
Group Member
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:


>> s = sparse(1,2^31, 123);
error: index (_,2.14748e+09): subscripts must be either integers 1 to (2^31)-1 or logicals
>> s = sparse(1,2^31-1, 123);
error: out of memory or dimension too large for Octave's index type
>> s=sparse(1,2^30,123)
s =

Compressed Column Sparse (rows = 1, cols = 1073741824, nnz = 1 [9.3e-08%])

  (1, 1073741824) ->  123


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


>> s = sparse(2^16,2^16,123)
s =

Compressed Column Sparse (rows = 65536, cols = 65536, nnz = 1 [2.3e-08%])

  (65536, 65536) ->  123

>> find(s)
ans = 0


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>
Group administrator
Thu 28 Nov 2013 07:54:16 PM UTC, comment #2: 

More sparse badness...


octave-cli:3> s = sparse(2^16,2^16,123)
s =

Compressed Column Sparse (rows = 65536, cols = 65536, nnz = 1 [2.3e-08%])

  (65536, 65536) ->  123

octave-cli:4> find(s)
../../libinterp/corefcn/find.cc:178:25: runtime error: signed integer overflow: 65535 * 65536 cannot be represented in type 'int'
ans = 0


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

----------


octave-cli:2> s = sparse(1,2^32, 123);
/home/pk/dl/octave-default/build/liboctave/../../liboctave/array/idx-vector.cc:237: runtime error: value 4.29497e+09 is outside the range of representable values of type 'int'
../../liboctave/array/idx-vector.cc:231:12: runtime error: signed integer overflow: -2147483648 - 1 cannot be represented in type 'int'
error: sparse: subscript indices must be either positive integers less than 2^31 or logicals
octave-cli:2> s = sparse(1,2^32-1, 123);
/home/pk/dl/octave-default/build/liboctave/../../liboctave/array/idx-vector.cc:237: runtime error: value 4.29497e+09 is outside the range of representable values of type 'int'
error: sparse: subscript indices must be either positive integers less than 2^31 or logicals
octave-cli:2> s = sparse(1,2^32-2, 123);
/home/pk/dl/octave-default/build/liboctave/../../liboctave/array/idx-vector.cc:237: runtime error: value 4.29497e+09 is outside the range of representable values of type 'int'
error: sparse: subscript indices must be either positive integers less than 2^31 or logicals
octave-cli:2> s = sparse(1,2^31, 123);
/home/pk/dl/octave-default/build/liboctave/../../liboctave/array/idx-vector.cc:237: runtime error: value 2.14748e+09 is outside the range of representable values of type 'int'
error: sparse: subscript indices must be either positive integers less than 2^31 or logicals
octave-cli:2> s = sparse(1,2^31-1, 123);
../../liboctave/array/Sparse.h:92:35: runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type 'int'
==2093==WARNING: AddressSanitizer failed to allocate 0xffffffffffffffff bytes
==2093==AddressSanitizer's allocator is terminating the process instead of returning 0
==2093==If you don't like this behavior set allocator_may_return_null=1
==2093==AddressSanitizer CHECK failed: /home/pk/dl/llvm/llvm/projects/compiler-rt/lib/sanitizer_common/sanitizer_allocator.cc:149 "((0)) != (0)" (0x0, 0x0)
    #0 0x46c2ff in __asan::AsanCheckFailed(char const*, int, char const*, unsigned long long, unsigned long long) /home/pk/dl/llvm/llvm/projects/compiler-rt/lib/asan/asan_rtl.cc:66
    #1 0x471b51 in __sanitizer::CheckFailed(char const*, int, char const*, unsigned long long, unsigned long long) /home/pk/dl/llvm/llvm/projects/compiler-rt/lib/sanitizer_common/sanitizer_common.cc:69
    #2 0x470890 in __sanitizer::AllocatorReturnNull() /home/pk/dl/llvm/llvm/projects/compiler-rt/lib/sanitizer_common/sanitizer_allocator.cc:149
    #3 0x466f7d in operator new[](unsigned long) /home/pk/dl/llvm/llvm/projects/compiler-rt/lib/asan/asan_new_delete.cc:54
    #4 0x7fcba4f9d9b6 in Sparse<double>::SparseRep::SparseRep(int, int, int) /home/pk/dl/octave-default/build/libinterp/../../liboctave/array/Sparse.h:94
    #5 0x7fcb8fddb868 in Sparse<double>::SparseRep::SparseRep(int, int, int) /home/pk/dl/octave-default/build/liboctave/../../liboctave/array/Sparse.h:97
    #6 0x7fcb8fdf5852 in Sparse<double>::Sparse(Array<double> const&, idx_vector const&, idx_vector const&, int, int, bool, int) /home/pk/dl/octave-default/build/liboctave/../../liboctave/array/Sparse.cc:320
    #7 0x7fcba817b584 in MSparse<double>::MSparse(Array<double> const&, idx_vector const&, idx_vector const&, int, int, bool, int) /home/pk/dl/octave-default/build/libinterp/../../liboctave/array/MSparse.h:64
    #8 0x7fcba817a634 in SparseMatrix::SparseMatrix(Array<double> const&, idx_vector const&, idx_vector const&, int, int, bool, int) /home/pk/dl/octave-default/build/libinterp/../../liboctave/array/dSparse.h:82
    #9 0x7fcba90f6e49 in Fsparse(octave_value_list const&, int) /home/pk/dl/octave-default/build/libinterp/../../libinterp/corefcn/sparse.cc:199
    #10 0x7fcba3ed54c9 in octave_builtin::do_multi_index_op(int, octave_value_list const&, std::list<octave_lvalue, std::allocator<octave_lvalue> > const*) /home/pk/dl/octave-default/build/libinterp/../../libinterp/octave-value/ov-builtin.cc:132
    #11 0x7fcba3ed28d6 in octave_builtin::subsref(std::string const&, std::list<octave_value_list, std::allocator<octave_value_list> > const&, int, std::list<octave_lvalue, std::allocator<octave_lvalue> > const*) /home/pk/dl/octave-default/build/libinterp/../../libinterp/octave-value/ov-builtin.cc:64
    #12 0x7fcba3ed1965 in octave_builtin::subsref(std::string const&, std::list<octave_value_list, std::allocator<octave_value_list> > const&, int) /home/pk/dl/octave-default/build/libinterp/../../libinterp/octave-value/ov-builtin.cc:47
    #13 0x7fcba3edb2d5 in octave_builtin::subsref(std::string const&, std::list<octave_value_list, std::allocator<octave_value_list> > const&) /home/pk/dl/octave-default/build/libinterp/../../libinterp/octave-value/ov-builtin.h:62
    #14 0x7fcba4a4307b in octave_value::subsref(std::string const&, std::list<octave_value_list, std::allocator<octave_value_list> > const&, int) /home/pk/dl/octave-default/build/libinterp/../../libinterp/octave-value/ov.cc:1267
    #15 0x7fcba4a4475b in octave_value::subsref(std::string const&, std::list<octave_value_list, std::allocator<octave_value_list> > const&, int, std::list<octave_lvalue, std::allocator<octave_lvalue> > const*) /home/pk/dl/octave-default/build/libinterp/../../libinterp/octave-value/ov.cc:1280
    #16 0x7fcba52138e0 in tree_index_expression::rvalue(int, std::list<octave_lvalue, std::allocator<octave_lvalue> > const*) /home/pk/dl/octave-default/build/libinterp/../../libinterp/parse-tree/pt-idx.cc:415
    #17 0x7fcba520a4f8 in tree_index_expression::rvalue(int) /home/pk/dl/octave-default/build/libinterp/../../libinterp/parse-tree/pt-idx.cc:284
    #18 0x7fcba52161d0 in tree_index_expression::rvalue1(int) /home/pk/dl/octave-default/build/libinterp/../../libinterp/parse-tree/pt-idx.cc:427
    #19 0x7fcba50cc85f in tree_simple_assignment::rvalue1(int) /home/pk/dl/octave-default/build/libinterp/../../libinterp/parse-tree/pt-assign.cc:85
    #20 0x7fcba51a5393 in tree_evaluator::visit_statement(tree_statement&) /home/pk/dl/octave-default/build/libinterp/../../libinterp/parse-tree/pt-eval.cc:747
    #21 0x7fcba53e552d in tree_statement::accept(tree_walker&) /home/pk/dl/octave-default/build/libinterp/../../libinterp/parse-tree/pt-stmt.cc:178
    #22 0x7fcba51a707f in tree_evaluator::visit_statement_list(tree_statement_list&) /home/pk/dl/octave-default/build/libinterp/../../libinterp/parse-tree/pt-eval.cc:797
    #23 0x7fcba53e658d in tree_statement_list::accept(tree_walker&) /home/pk/dl/octave-default/build/libinterp/../../libinterp/parse-tree/pt-stmt.cc:291
    #24 0x7fcba9526aea in main_loop() /home/pk/dl/octave-default/build/libinterp/../../libinterp/corefcn/toplev.cc:569
    #25 0x7fcba0b7167c in octave_execute_interpreter /home/pk/dl/octave-default/build/libinterp/../../libinterp/octave.cc:883
    #26 0x47bb8b in main /home/pk/dl/octave-default/build/src/../../src/main-cli.cc:42
    #27 0x7fcb855ffde4 in __libc_start_main /build/buildd/eglibc-2.17/csu/libc-start.c:260
    #28 0x47b7cc in _start (/home/pk/dl/octave-default/build/src/.libs/lt-octave-cli+0x47b7cc)


Philipp Kutin <pkutin>

 

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

Attach Files:
   
   
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
  • -email is unavailable- added by siko1056 (Posted a comment)
  • -email is unavailable- added by hardy (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by pkutin (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 7 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2021-08-25 rik5 Priority5 - Normal 3 - Low
        StatusFixed Confirmed
        Open/ClosedClosed Open
    2021-08-25 siko1056 StatusConfirmed Fixed
        Open/ClosedOpen Closed
    2013-12-02 rik5 StatusNone Confirmed
    2013-11-28 pkutin Attached File- Added alloc_minus_one.log, #29728

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code