bugGNU Octave - Bugs: bug #54414, Not recognizing that indices...

 
 

bug #54414: Not recognizing that indices greater than (roughly) 2^63 or 20 digits are too large

Submitter:  Dan Sebald <sebald>
Submitted:  Wed 01 Aug 2018 02:38:47 AM UTC
   
 
Category:  Interpreter Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Patch Submitted 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

Mon 21 Sep 2020 11:38:13 PM UTC, comment #9: 

Unfortunately not.  I fixed the original problem, but Dan is correct that there are duplicate code paths and not everywhere do we get this right.

This example still produces an empty matrix


 fn = "ramp10by11.dat";
 fid = fopen(fn, "w+");
 fwrite (fid, ones(10,1)*[1:11], "single");
 frewind (fid);
 x = fread (fid, [9223372036854775807, 9223372036854775807], 'single');


Rik <rik5>
Group administrator
Mon 21 Sep 2020 04:25:16 PM UTC, comment #8: 

With Octave 6.0.90, I get either of the two:

>> __octave_config_info__ ('ENABLE_64')
ans = 1
>> zeros(9223372036854775807)

error: conversion of 9.22337e+18 to octave_idx_type value failed
>> zeros(922337203685477580)

error: out of memory or dimension too large for Octave's index type


That looks ok to me.

The other points seem to be covered by the (in the meantime fixed) bug #45945.

Can this report be closed?

Markus Mützel <mmuetzel>
Group administrator
Wed 01 Aug 2018 10:04:31 PM UTC, comment #7: 

"Yes" and "no".  The same phenomenon is the core issue in both instances, but these are different pieces of code.  Bug #45945 is discussing that LONG_INT -> DOUBLE -> LONG_INT issue in the interpreter.  Here in the fread() and get_size() routines, it is the fact that the index is being stored as a double.  If Bug #45945 is fixed, it isn't going to fix the fread problem, unless the indices are kept as octave_idx_type the whole way.

This is why I'm suggesting the hunk of code for that region of numbers for which the double loses resolution:


+#if 1
+        // FIXME: The size specification involves the use of double
+        //        representation, so roughly any typed-in index values from
+        //        2^53 (mantissa size of double) to 2^63 can create aliased
+        //        nr and nc, i.e., they turn out negative from wrap-around
+        //        effect.  (See Bug #54405.)  Is this necessary given huge
+        //        size?  Should this be done in interpretter?
+        if (d >= 9007199254740992)
+          ::warning ("%s: possible loss of resolution converting from float to octave_idx_type",
+                   who.c_str ());
+#endif


and it is noted as a FIXME for the simple fact the situation may be avoidable.  Basically, the above is just a warning that things are on shaky ground with the float to long int conversion.

But, as I look at this, the above doesn't seem to cover all the issues.  The above is a loss of resolution, sure, but why the strange wrapping effect when the numbers are supposedly greater than std::numeric_limits<octave_idx_type>::max ()?

So, we know that the following is dodgy:


        if (d > std::numeric_limits<octave_idx_type>::max ())
          ::error ("%s: dimension too large for Octave's index type",
                   who.c_str ());


d, a double, could have been entered with a string, say, one greater than


octave:12> int64(inf)
ans = 9223372036854775807


i.e., [9223372036854775808, 9223372036854775808] and that string gets translated to float and consequently becomes


octave:13> x = 9223372036854775808
x =    9.2234e+18
octave:14> x < int64(inf)
ans = 1


That's the loss of resolution at work.  Eventually as we increase x's string value, the double will test greater than std::numeric_limits<octave_idx_type>::max ().

But why is the following:


        retval = math::nint_big (d);


returning something zero or negative?  It should still be returning some rather large number which will cause the "too big of index" error.

Let's take a look at that nint_big() routine from lo-mappers.cc.  There are several of them:


    octave_idx_type
    nint_big (double x)
    {
      if (x > std::numeric_limits<octave_idx_type>::max ())
        return std::numeric_limits<octave_idx_type>::max ();
      else if (x < std::numeric_limits<octave_idx_type>::min ())
        return std::numeric_limits<octave_idx_type>::min ();
      else
        return static_cast<octave_idx_type> ((x > 0.0) ? (x + 0.5)
                                                       : (x - 0.5));
    }


Two things should be considered.  1) Could adding the 0.5 prior to the cast cause an issue?  2) I believe the promotion rules means that the size comparison is done by converting the integer to double, then compare.  But perhaps what really should be done is convert the floating point to integer then test.  Hold on, let me tweak the nbig_int...

Yes, that looks to have fixed the problem.  Take a look at the attached changeset and see if you agree with it.  We still need to address the float value being grossly larger than, but then there also needs to be a subtle analysis at that decreased resolution boundary region.

Do we need to cover the


    int
    nint (double x)


case?  The double mantissa is adequate resolution for 32-bit int, but can there be some value, say 1234.56789, that causes problems, i.e., the fraction part takes away integer resolution?

(file #44686)

Dan Sebald <sebald>
Wed 01 Aug 2018 07:23:51 PM UTC, comment #6: 

But isn't this just bug #45945 again?  In Octave there is no way to enter the number in the interpreter and not have it lose precision with respect to (u)int64 because the interpreter always reads doubles.


x = 9223372036854775807
x =    9.2234e+18
sprintf ("%20f\n", x)
ans = 9223372036854775808.000000


The number has already lost one digit of precision.  Now find out what eps is.


eps (x)
ans =  2048


And if I try and read a number that is distinguishable from the max octave_idx_type then I do get an error.


fread (fid, [x+eps(x), x+eps(x)], 'single')
error: fread: dimension too large for Octave's index type



Rik <rik5>
Group administrator
Wed 01 Aug 2018 06:06:06 PM UTC, comment #5: 

I have the most recent, but it's a 64-bit build.

Dan Sebald <sebald>
Wed 01 Aug 2018 04:54:26 PM UTC, comment #4: 

I don't think you're running from the most recent development tip.  When I try your code I get


octave:2> fn = "ramp10by11.dat";
octave:3> fid = fopen(fn, "w+");
octave:4> fwrite (fid, ones(10,1)*[1:11], "single");
octave:5> frewind (fid);
octave:6> x = fread (fid, [9223372036854775807, 9223372036854775807], 'single');
error: fread: dimension too large for Octave's index type
error: value on right hand side of assignment is undefined
octave:6> x
error: 'x' undefined near line 1 column 1
octave:6> diary off


The fix here is only about the zeros() (and friends) functions.

Rik <rik5>
Group administrator
Wed 01 Aug 2018 04:46:29 PM UTC, comment #3: 

That fixes this case, nice:


octave:2> zeros(9223372036854775807)
error: zeros: conversion to integer value failed


Yes, the error message could maybe be a little more helpful, but a little thought and it should be evident what's wrong.  Here's the sort of hint the gcc compiler displays:


  CXX      libinterp/corefcn/libinterp_corefcn_libcorefcn_la-oct-stream.lo
/linux/octave/octave/octave/libinterp/corefcn/oct-stream.cc:6610:55: warning: integer constant is so large that it is unsigned
 std::cerr << "labs(-9223372036854775808) = " << labs(-9223372036854775808) << "


However, this change doesn't fix this example:


octave:2> fn = "ramp10by11.dat";
octave:3> fid = fopen(fn, "w+");
octave:4> fwrite (fid, ones(10,1)*[1:11], "single");frewind (fid);
octave:5> x = fread (fid, [9223372036854775807, 9223372036854775807], 'single');
octave:6> x
x = [](0x0)


The get_size() routine, after the recent change of Bug #54405, is doing its own overflow check.  It's repetitive code, with conversions in both get_size() and octave_idx_type_vector_value().  I feel the sooner test in the interpreter is the better place to catch these.  However, that could mean noticeable change in the variable holding that index information.

Dan Sebald <sebald>
Wed 01 Aug 2018 04:07:17 PM UTC, comment #2: 

For testing, I've been finding it easier to configure with --disable-64 and use 32-bit indices.  2^31 is a lot smaller than 2^63 and makes the issues apparent at more approachable sizes.

Rik <rik5>
Group administrator
Wed 01 Aug 2018 03:45:35 PM UTC, comment #1: 

Tracing this down.  The zeros function is in data.cc which calls the fill_matrix function which is also in data.cc.  The fill_matrix command calls get_dimensions in libinterp/corefcn/utils.cc.  Within get_dimensions there is this line of code


    const Array<octave_idx_type> v = a.octave_idx_type_vector_value ();


The octave_idx_type_vector_value function is defined for octave_value objects in ov.cc.  The prototype for that function is



Array<octave_idx_type>
octave_value::octave_idx_type_vector_value (bool require_int,
                                            bool force_string_conv,
                                            bool force_vector_conversion) const


For converting doubles to octave_idx_type the following code is used.


      const NDArray a = array_value (force_string_conv);

      if (require_int)
        {
          retval.resize (a.dims ());
          for (octave_idx_type i = 0; i < a.numel (); i++)
            {
              double ai = a.elem (i);
              octave_idx_type v = static_cast<octave_idx_type> (ai);
              if (ai == v)
                retval.xelem (i) = v;
              else
                {
                  error_with_cfn ("conversion to integer value failed");
                  break;
                }
            }
        }
      else
        retval = Array<octave_idx_type> (a);


If the require_int boolean is true then octave checks for overflow during conversion.  The default, however, is false which means results aren't checked and the constructor Array<octave_idx_type> is invoked which can map doubles to negative values.

Attached is a small diff which sets the require_int bool to true when called from get_dimensions.  It works, but there may be a better option for the fix.  In particular, the error message isn't very informative


octave:1> zeros (1e31)
error: zeros: conversion to integer value failed


Running 'make check' passes though with this small change.

A grep through libinterp shows get_dimensions used 40 times, but some of these seem to be for a mex function of the same name which can probably be ignored.


corefcn/mxarray.in.h:205:  virtual mwSize * get_dimensions (void) const = 0;
corefcn/mxarray.in.h:426:  mwSize * get_dimensions (void) const { return rep->get_dimensions (); }
corefcn/utils.h:87:  get_dimensions (const octave_value& a, const char *warn_for,
corefcn/utils.h:91:  get_dimensions (const octave_value& a, const octave_value& b,
corefcn/utils.h:96:  get_dimensions (const octave_value& a, const char *warn_for,
corefcn/utils.h:199:OCTAVE_DEPRECATED (5, "use 'octave::get_dimensions' instead")
corefcn/utils.h:201:get_dimensions (const octave_value& a, const char *warn_for,
corefcn/utils.h:204:OCTAVE_DEPRECATED (5, "use 'octave::get_dimensions' instead")
corefcn/utils.h:206:get_dimensions (const octave_value& a, const octave_value& b,
corefcn/utils.h:210:OCTAVE_DEPRECATED (5, "use 'octave::get_dimensions' instead")
corefcn/utils.h:212:get_dimensions (const octave_value& a, const char *warn_for,
corefcn/data.cc:3875:      octave::get_dimensions (args(0), fcn, dims);
corefcn/data.cc:3985:      octave::get_dimensions (args(0), fcn, dims);
corefcn/data.cc:4049:      octave::get_dimensions (args(0), fcn, dims);
corefcn/data.cc:4114:      octave::get_dimensions (args(0), fcn, dims);
corefcn/data.cc:4169:      octave::get_dimensions (args(0), fcn, dims);
corefcn/data.cc:5013:      octave::get_dimensions (args(0), "eye", nr, nc);
corefcn/data.cc:5020:      octave::get_dimensions (args(0), args(1), "eye", nr, nc);
corefcn/mex.cc:196:            mwSize *xdims = retval->get_dimensions ();
corefcn/mex.cc:269:    get_dimensions ();
corefcn/mex.cc:277:  mwSize * get_dimensions (void) const
corefcn/mex.cc:298:    get_dimensions ();
corefcn/mex.cc:321:    get_dimensions ();
corefcn/mex.cc:584:    get_dimensions ();
corefcn/mex.cc:811:  mwSize * get_dimensions (void) const { return dims; }
corefcn/mex.cc:1044:    mwSize *d = get_dimensions ();
corefcn/mex.cc:1153:    mwSize *dv = get_dimensions ();
corefcn/mex.cc:2864:  return ptr->get_dimensions ();
corefcn/sparse.cc:154:      octave::get_dimensions (args(0), args(1), "sparse", m, n);
corefcn/sparse.cc:187:          octave::get_dimensions (args(3), args(4), "sparse", m, n);
corefcn/utils.cc:1078:  void get_dimensions (const octave_value& a, const char *warn_for,
corefcn/utils.cc:1108:  void get_dimensions (const octave_value& a, const char *warn_for,
corefcn/utils.cc:1131:  void get_dimensions (const octave_value& a, const octave_value& b,
corefcn/utils.cc:1604:get_dimensions (const octave_value& a, const char *warn_for,
corefcn/utils.cc:1607:  return octave::get_dimensions (a, warn_for, dim);
corefcn/utils.cc:1611:get_dimensions (const octave_value& a, const octave_value& b,
corefcn/utils.cc:1615:  return octave::get_dimensions (a, b, warn_for, nr, nc);
corefcn/utils.cc:1619:get_dimensions (const octave_value& a, const char *warn_for,
corefcn/utils.cc:1622:  return octave::get_dimensions (a, warn_for, nr, nc);
octave-value/ov-cell.cc:1254:      octave::get_dimensions (args(0), "cell", dims);


Ignoring the mex functions it is only data.cc, sparse.cc, and ov-cell.cc that use get_dimensions.

Or, maybe this should be tackled in the Array constructor?


(file #44685)

Rik <rik5>
Group administrator
Wed 01 Aug 2018 02:38:47 AM UTC, original submission:  

When a value input to zeros is larger than approximately 2^63, or maybe it is 20 digits, there is no warning about too big and instead the value is treated as 0.  E.g.,


octave:1> int64(inf)
ans = 9223372036854775807
octave:2> zeros(9223372036854775807)
ans = [](0x0)
octave:3> # Drop a digit
octave:3> zeros(922337203685477580)
error: out of memory or dimension too large for Octave's index type
octave:3>


Dan Sebald <sebald>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #44685:  54114.diff added by rik5 (582B - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by mmuetzel (Posted a comment)
  • -email is unavailable- added by rik5 (Updated the item)
  • -email is unavailable- added by rik5
  • -email is unavailable- added by sebald (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 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-08-01 sebald Attached File- Added octave-nint_math_wrap_around-djs2018aug01.patch, #44686
    2018-08-01 rik5 Attached File- Added 54114.diff, #44685
        StatusNone Patch Submitted
        Carbon-Copy- Added jwe

    Back to the top

    Powered by Savane 3.13-758e.
    Corresponding source code