bugGNU Octave - Bugs: bug #54405, octave_idx_type index integer...

 
 

bug #54405: octave_idx_type index integer overflow math check doesn't work correctly

Submitted by:  Dan Sebald <sebald>
Submitted on:  Sun 29 Jul 2018 06:52:38 PM UTC  
 
Category:  Interpreter Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Ready For Test Assigned to:  None
Originator Name:  Open/Closed:  Open
Release:  dev Operating System:  Any

Add a New Comment(Rich Markup)
   

You are not logged in

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

 

( Jump to the original submission)

Wed 01 Aug 2018 11:42:14 AM UTC, comment #32:

I agree with Rik's comment #22. This bug report has gone off the rails.

Please isolate the individual issues, open separate reports about them, close this one, and try to keep some focus.

We already know that numbers like

in Octave and Matlab will lose precision because they are doubles. If you want them to be correct int64, then you can write

in Matlab, but in Octave, this is bug #45945. Unless the behavior of Matlab has changed recently, these numbers can not be automatically recognized as int64 without breaking compatibility.

That I/O and other functions may not handle int64 values as files sizes or dimensions is another issue that could have a separate report if one is not already open.

Properly catching dimension overflow in array constructors is another issue. If we don't have a bug report for that, then open a separate one.

Whatever the "try-catch double error problem" is, open a separate bug report for just that issue if we don't already have one.

Whether Octave should use an unsigned type for array dimensions is another issue that could have a separate bug report if we do not already have one.

John W. Eaton <jwe>
Project Administrator
Wed 01 Aug 2018 08:16:21 AM UTC, comment #31:

It wouldn't surprise me if std::abs() is set up to use the appropriate abs() function based on variable type. I'll use that instead.

What you've done is effectively treat the octave_idx_type as a 63-bit unsigned number, i.e., if nc > 0 and nr > 0. I was sort of aiming for a general overflow test (whether that be signed or unsigned) so that it can be replaced by one of the GNULIB routines from here:

https://gcc.gnu.org/onlinedocs/gcc-6.2.0/gcc/Integer-Overflow-Builtins.html

These are already compiled into the Octave executable, so why not use them? They are much nicer routines because they make use of the CPU's overflow flags if readily available. That is, they simply carry out the multiplication, then check the CPU's overflow bit in some ALU register or do some conditional jump on overflow; one machine cycle.

On the other hand, the division, even if it is built in to the processor, probably takes many machine cycles. It all depends on the CPU of course: CISC, RISC, DSP.

Also, I still think this isn't quite correct. By ignoring those negative numbers, it can't catch that troublesome conversion from 53-bit mantissa float to signed long. Check out this example (from the canonical version at changeset http://hg.savannah.gnu.org/hgweb/octave/rev/02fbbde15308

Notice how long INT_MAX (9223372036854775807) and greater are not being caught. When the size gets much bigger, though, the test starts catching the too-large index. There is this troublesome group of numbers I've been trying to illustrate which come about because of that conversion from float to long int. Even though they are positive as entered, they end up internally as negative numbers when converted. So, the code that checks

is overlooking that scenario. The out-of-range numbers really do end up negative at that point.

This fact is one of the reasons I've questioned if it might be better to utilize the octave_idx_type as unsigned and have them computed as soon as possible coming out of the interpreter rather than storing the indices as doubles until the moment before they are used.

Anyway, I don't think get_size() is the proper place to check NR * NC, but I'm fine with it. However, I'm attaching another changeset that incorporates the main ideas from my previous changeset. Look them over and see why they are there using the new BISTs of io.tst. After running the BISTs, revert all the changes except the io.tst file, recompile and run the io.tst test again.

The tests will also show the try-catch double-error problem. Do we want that to be a separate bug?

(file #44680)

Dan Sebald <sebald>
Wed 01 Aug 2018 04:10:07 AM UTC, comment #30:

An Inf value in fread size is converted to -1, so NR*NC will not be tested for overflow. The check is only done when NR > 0 && NC > 0.

Rik <rik5>
Project Administrator
Wed 01 Aug 2018 04:05:41 AM UTC, comment #29:

It turns out that we are catching some version of abs() which doesn't seem to work very well. If I specify std::abs explicitly things work. See the results of some printf debugging.

But now that I know what is going on I can get around it by avoiding abs() entirely. I re-coded to

I checked in this amendment here (https://hg.savannah.gnu.org/hgweb/octave/rev/02fbbde15308).

Rik <rik5>
Project Administrator
Wed 01 Aug 2018 03:22:04 AM UTC, comment #28:

Another issue which probably related to the 32-bit compilation, in the recent changeset, I changed "abs()" to "labs()". Doing an abs(INT64) is likely to cause strange errors.

Dan Sebald <sebald>
Wed 01 Aug 2018 02:49:48 AM UTC, comment #27:

Rik wrote: "First, the changeset I pushed is only about checking for an overflow in a dimension or overall number of elements."

That assumes the size specification will be used in an NR*NC fashion. If this size specification comes from, for example,

i.e., the [8,Inf] is treated internally as a size array, will that throw an error?

Dan Sebald <sebald>
Wed 01 Aug 2018 02:43:55 AM UTC, comment #26:

I created a new bug report for the zeros(LARGE_NUMBER) phenomenon:

https://savannah.gnu.org/bugs/?54414

Correct that I've added 8 tests to io.tst in the new patch. Keep in mind that I don't have changeset

http://hg.savannah.gnu.org/hgweb/octave/rev/39fd627b2c5d

on my system. We should probably create a separate bug report for that too. (I think it just never arose because those error conditions weren't being exercised until now.)

Dan Sebald <sebald>
Wed 01 Aug 2018 02:19:16 AM UTC, comment #25:

Really? Automatic casting to 64 bit math perhaps? What do you get when printing out

Dan Sebald <sebald>
Wed 01 Aug 2018 02:13:16 AM UTC, comment #24:

@Rik, There's probably some type of compiler flag different for your build that affect how try/catch behaves... My point from Comment #15 is that I don't think the overflow test can be moved inside of get_size() because that is only getting the two values and has no knowledge of how the sizes will be used. That is, so long as no multiplication of NR * NC is done, there can be valid cases where NR < INT_MAX and NC < INT_MAX, but not necessarily NR * NC < INT_MAX.

Dan Sebald <sebald>
Wed 01 Aug 2018 02:11:01 AM UTC, comment #23:

I can now reproduce the error. It depends on whether Octave was configured with --disable-64 or not. When using a 32-bit octave_idx_type the tests pass. That, at least, is a start.

Rik <rik5>
Project Administrator
Wed 01 Aug 2018 02:08:41 AM UTC, comment #22:

There are too many threads going on here.

First, the changeset I pushed is only about checking for an overflow in a dimension or overall number of elements.

Second, it is not addressing the fact that there can be aliasing when a dimension, represented as a double, is larger than 2^53 and converted in to a uint64 type. That is something separate.

Third, this can't be right

because there are only 157 tests in io.tst and no mention of 54405. Dan, I think your repository is running with your own patch applied from comment #12 which is not what the buildbots are running.

Fourth, there is some strangeness in zeros, but it should be reported as a different bug. Test code for that would be

Rik <rik5>
Project Administrator
Wed 01 Aug 2018 01:39:47 AM UTC, comment #21:

Weird. I wonder why my machine is okay with this.

Rik <rik5>
Project Administrator
Wed 01 Aug 2018 01:37:01 AM UTC, comment #20:

Ah, I'm looking at the changeset that Rik pushed:

http://hg.savannah.gnu.org/hgweb/octave/rev/39fd627b2c5d

and I do believe that is what the bots are seeing. That get_size is used in some try-catch blocks to the error doesn't throw and lingers, showing up in strange places. I think that is a pre-existing bug of its own.

In any case, the overflow check I proposed wasn't fully tested. It's incomplete regarding the -2^63 value. (The compiler doesn't like that number because it can't take the absolute value of it.) Plus, I found that GNULIB already has such a check using hardware-level features we can utilize. So, have a look at my recent changeset. Maybe it's best to revert changeset 39fd627b2c5d and apply the new changeset, then address the try-catch thing, or vice-versa.

Dan Sebald <sebald>
Wed 01 Aug 2018 01:27:12 AM UTC, comment #19:

@JWE, just a thought. Here's what gcc compiler does when trying to take the absolute value of minimum int64 value:

Somehow it's figuring out from the ASCII string that it won't work. Octave could do a similar check on a manually entered integer index value rather than convert it to float. That is, say the user types:

zeros(92233720368547758083333)

The error could be that the index is too large, rather than out of memory. Huh, I just tried this and

Possible bug?

Dan Sebald <sebald>
Wed 01 Aug 2018 01:18:20 AM UTC, comment #18:

Attached is another failing test.

Dmitri.
--

(file #44673)

Dmitri A. Sergatskov <dasergatskov>
Wed 01 Aug 2018 01:09:54 AM UTC, comment #17:

@Rik, @DAS, I think the BIST you are looking at is the one that is failing in the BISTs I added in the changeset. I think the issue is that get_size() is in a try-catch block and produces:

To illustrate:

Dan Sebald <sebald>
Wed 01 Aug 2018 01:09:06 AM UTC, comment #16:

I do not understand what is happening (and why):

File attached.

Dmitri.
--

(file #44672)

Dmitri A. Sergatskov <dasergatskov>
Wed 01 Aug 2018 01:06:15 AM UTC, comment #15:

@Rik, I don't think we can move the overflow test within get_size() because there is no multiplication done there. But as can be seen in the new changesets and some BIST, I added a warning within get_size:

octave:5> x = fread (fid, [2^53-1, 2^53], 'single');
warning: fread: possible loss of resolution converting from float to octave_idx_type
error: fread: dimension too large for Octave's index type

It's only the second size value of 2^53 that causes a warning. I based the logic for the choice on the following result:

Once again, is this necessary? Probably not, I like it though because it adds a bit of clarity. In the future this might be addressed, say, more precisely in the interpreter phase.

Dan Sebald <sebald>
Wed 01 Aug 2018 01:00:28 AM UTC, comment #14:

I will try. But all (dev) buildbots are failing...

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Wed 01 Aug 2018 12:59:03 AM UTC, comment #13:

Interesting, "test io.tst" works for me. This is with cset

Platform is Linux, x86_64.

You might try placing the failing test in its own file and then using debug_on_error(1) and execute the file.

Rik <rik5>
Project Administrator
Wed 01 Aug 2018 12:58:37 AM UTC, comment #12:

I did have a vague memory this was discussed within the past couple years. I was simply trying to gauge how big of an effort it would be to change to signed index; again, if it makes things easier somewhere else to have unsigned, then maybe it is worth it. JWE would have the best idea of this given the distribution of posts in that thread.

The cases where negative octave_idx_type has meaning don't concern me too much. Those could be weeded out pretty well with the BISTs. The main issue as I watched the code compile with unsigned octave_idx_type seems to be its use in a header file that is included everywhere. I think it is a header file that does a relational comparison on reference counting. That's probably where the immediate seg-fault comes from...

I wondered if it would be a good idea to make this a macro or inline, so then I just tried putting __builtin_smull_overflow() for fun, and it worked. Ha-ha, what we need is already present.

So, what I've done is written this change in the form of an inline function that will utilize the GNULIB hardware-supported routine if possible. That's kind of nice. But, JWE, perhaps you could place the changeset's top matter near the header file list in an appropriate header file with the right preprocessor definitions for inclusion. I don't follow the make process too closely.

Doing things this way also made me realize one other small detail that kind of clears things up. The __builtin_smull_overflow was more robust than what I had in the previous version. Because I was using

labs(long int)

the compiler does the following

labs(-9223372036854775808) = -9223372036854775808

That is, because of the two's complement number system there isn't symmetry for that most negative number. The result is that the number is unchanged for labs(). Hence, I had to make the test more complex and account for that situation; another consequence of using signed index instead of unsigned index.

Lastly, there are other occurrences of nr time nc in the oct-stream.cc file. Do we want to protect those by OCTAVE_IDX_OVERFLOW()? I'm thinking this function could find use in many places, even though they will be caught by "out of memory" or some other condition.

@Rik, I added some BIST tests. There are probably more that can be added. One of them fails though. You indicated that ::error() doesn't need a return, so I don't know why that second error message is appearing. I think it is because the get_size() is within a try-catch block. That's probably a bug of it's own, so I haven't addressed that.

(file #44671)

Dan Sebald <sebald>
Wed 01 Aug 2018 12:43:57 AM UTC, comment #11:

@Rik, I think you cset has a problem:

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Tue 31 Jul 2018 05:32:20 PM UTC, comment #10:

I think it is worthwhile to put the check for overflow within the get_size routine so that anyone that calls it (fread, sscanf) can get the benefit rather than just fread. Also, there is no need to call return after a call to the execption-based error function. See this cset https://hg.savannah.gnu.org/hgweb/octave/rev/39fd627b2c5d.

It might be nice to have some BIST tests in io.tst for these exception conditions like using Inf, NaN, or large index sizes.

Marking as "Ready for Test".

Rik <rik5>
Project Administrator
Tue 31 Jul 2018 04:31:55 PM UTC, comment #9:

I don't think its worth the switch. Even a cursory look in oct-stream.cc shows we are using special values, like octave_idx_type = -1, to communicate information through return values. Hunting all of those down seems of questionable worth when for the majority of users it will never be an issue (using 64-bit index vectors so 2^63 elements are possible).

Rik <rik5>
Project Administrator
Tue 31 Jul 2018 12:00:02 PM UTC, comment #8:

We discussed signed vs. unsigned for octave_idx_type in this thread:

http://lists.gnu.org/archive/html/octave-maintainers/2016-11/msg00183.html

decided to go with a signed type.

The check that attempts to ensure that the overall array size is valid given a set of individual array dimensions is in the function safe_numel in dim_vector.cc. Is that check wrong?

I'm not opposed to switching to using size_t for array sizes internally in Octave as it would make using the STL a bit easier. But does it really matter? Is it worth the effort to switch?

John W. Eaton <jwe>
Project Administrator
Tue 31 Jul 2018 09:29:02 AM UTC, comment #7:

FWIW, I'm attaching a real crude change of octave_idx_type from signed to unsigned. Yeah, it segfaults pretty easily.

(file #44664)

Dan Sebald <sebald>
Mon 30 Jul 2018 08:12:03 AM UTC, comment #6:

Here's the initial patch to illustrate the pre-multiply overflow check. Basically, one FIXME removed, but another one added.

(file #44657)

Dan Sebald <sebald>
Mon 30 Jul 2018 06:52:26 AM UTC, comment #5:

OK thanks. The ::error() variant is the one I want.

To change to sign. I don't know, maybe it isn't so bad. Can test by just changing the sign and see how many BIST fail. If it makes things easier to deal with, it could be worth it.

So, with the ::error in place now, let me illustrate that in fact it is the lost of precision because of the 53 bit mantissa that is being manifested here. I'll start out choosing the size to be the std::numeric_limits<octave_idx_type>::max (). That gets mapped to a negative number (when it shouldn't). Then I will repeat by replacing the least significant digits with zero:

One can see that in the 800 range the index starts to get mapped to the correct int64 quantity. So, 800, yeah I can believe that is roughly 9 or 10 bits loss in resolution. So that is what's going on.

Regardless of the signedness of octave_idx_type, I would think going directly to that from the index specification would be best. That is, the parser can detect a leading minus sign for indices and throw an error. The parser can also recognize the user typed a fractional portion in an index and given it is non-negative, just toss those numerals after the period when it is an index. What the parser can't do is recognize the user might be using a double variable as an index and there is a loss of resolution that comes with that. Internally one might be able to recognize such a thing is occurring, i.e., octave_idx_type greater than 2^53 (52?) from a double variable, and print out a warning message about loss of resolution. Does it matter that much? Probably not as its only these test cases with large-valued indices that causes problems. But still, I'm thinking if there is some way to simplify and correct these corner cases, it could be worth it.

Dan Sebald <sebald>
Mon 30 Jul 2018 04:50:19 AM UTC, comment #4:

You definitely don't want to define octave_idx_type as unsigned. It has been a signed quantity for a long time (maybe forever) and there is probably lots of code that depends on that fact.

Note that error for octave_stream objects is not the same function as error in the rest of the octave. In the rest of Octave the function error comes from libinterp/corefcn/error.[h|cc]. This prints an error message to stderr and immediately returns, through exceptions, to the command prompt.

For Octave streams see libinterp/corefcn/oct-stream.[h|cc]. Here, error sets the error bit on the stream and puts an error message into the last error message buffer. Here is the message I wrote in oct-stream.cc because it is tricky.

Rik <rik5>
Project Administrator
Mon 30 Jul 2018 03:59:15 AM UTC, comment #3:

Something else I just remembered: I think that both gcc and VCC have integer math overflow trap mechanism (-trapv in gcc or something similar).

Also, GNU has some builtin routines that will check for overflow:

https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html

These might be more efficient than the

approach because that division above could be wasteful for small matrix sizes. That is, C/C++ has no natural language elements for checking overflows, but GNU might have optimized routines at the machine code level that can easily check a status flag after the multiplication is done.

But Octave aims for all different platforms in a general sense, so using the traps or the GNU

is sort of out.

Otherwise, is there a more efficient pre-multiply check?

perhaps? The log2(MAX) part is just a constant. log2 might have a really efficient integer-based counterpart.

Or, one could do

Meaning that at least one of the nr and nc has to be greater than 2^(log2(MAX)/2) otherwise there will be no multiplication overflow. That is a very quick way of allowing a very large percentage of the most typical vector sizes, i.e., fairly small. Only when the dimension sizes start to get big would a division be done to check for overflow.

Dan Sebald <sebald>
Sun 29 Jul 2018 09:01:04 PM UTC, comment #2:

A complicating factor is that this octave_idx_type's sign is often used to carry information, such as in this fread() example:

Another variable for the Inf specification could be easily added, rather than using the sign of an octave_idx_type for meaning.

Then there is the float mantissa issue alluded to in Bug #54100. Note that the

and

appear to be converting the index size to double value, hence the mantissa can only hold 53 or 52 bits, unless

is doing something to account for larger mantissa.

The conversion to float and back and using the sign of octave_idx_type to mean something seems extraneous, complicating matters. Perhaps a check is missing somewhere.

The size specs come from:

Hence, the size starts out as a double, then is converted to octave_idx_type for nr and nc, then those are converted to float for the get_size() routines, then converted back to nr and nc octave_idx_type. It might be better if as soon as possible the size was converted to octave_idx_type, i.e., the fractional parts of

fractional parts are dropped immediately, say a new

routine. Difficult to follow; just trying to simplify.

Dan Sebald <sebald>
Sun 29 Jul 2018 07:53:43 PM UTC, comment #1:

In the Array.h file is stated:

so I guess that octave_idx_type is a signed integer then. That means what I had printed out with std::cerr is, in fact, how the NR and NC numbers are treated by the compiler.

I changed the overflow check in fread() to the following (note the extra return statement added):

and the error is caught as desired. But still, the message is now

I guess the error() message doesn't work the way I'm imagining. Or perhaps the large octave_idx_type values are causing strange problems elsewhere.

Nonetheless, the signed index value seems to make checking overflow a little more complex. I wonder if it would be better to change octave_idx_type to unsigned and use the

construct without the complicating signed math such as abs() in the location wherever that "out of memory or dimension too large for Octave's index type" determination is made.

Dan Sebald <sebald>
Sun 29 Jul 2018 06:52:38 PM UTC, original submission:

The octave_idx_type is checked somewhere internally (I think) to make sure that a user doesn't specify some matrix dimension for which the overall number of elements is greater than

std::numeric_limits<octave_idx_type>::max ()

E.g., say number of rows NR is less than ::max() and number of columns NC is less than ::max(), but maybe if one uses a x(:) to create a vector that has NR * NC elements which is greater than ::max() in common algebra, but in 32-bit or 64-bit integer math would create an overflow.

However, it doesn't appear that this check is quite correct. In reference to Bug #54100

https://savannah.gnu.org/bugs/?func=detailitem&item_id=54100

I put an overflow test in for the scenario where the user specifies a matrix size where the octave_idx_type would overflow. However, although that test seems to catch the situation and call the error() function, it is the more general error that appears. Here's the output where I've printed out some additional info using std::cerr:

To reiterate, I confirmed that the following overflow check I put in place is caught:

but the following more general error from libinterp/parse-tree/pt-eval.cc is appearing:

This could just be a consequence of the try-catch block, i.e., there are two errors, so the more broad error message is displayed.

This is an ancillary issue, but it seems to me the interpreter could be more specific about whether it is an "out of memory" error or a "dimension too large" error. The "dimension too large" could be checked in a constructor, where the std::bad_alloc could be reserved for just the system typical std::bad_alloc.

Anyway, the bigger issue is that the overflow check doesn't seem quite right with regard to large octave_idx_type that is in the unsigned integer range, such as in the following example:

I put in the octave_idx_type limit for the sizes:

std::numeric_limits<octave_idx_type>::max ()

and the overflow checks are not being caught; neither the one I added nor the existing more global check. I tried subtracting one or two from this value, and the same situation arises. Keep in mind that what is printed out with "std::cerr << nr" where nr is octave_idx_type is not necessarily the same as how the compiler is treating overflow check. So the minimum values of signed 64-bit, i.e., -9223372036854775808 could be misleading.

In summary, I'm not quite sure what is happening, but the overflow check doesn't seem quite right.

Indirectly related issues are:

https://savannah.gnu.org/bugs/?func=detailitem&item_id=54100
https://savannah.gnu.org/bugs/?func=detailitem&item_id=40812
https://savannah.gnu.org/bugs/?func=detailitem&item_id=47175

Dan Sebald <sebald>

 

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

Attach Files:
   
   
Comment:
   

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by dasergatskov (Posted a comment)
  • -email is unavailable- added by jwe (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by sebald (Submitted the item)
  •  

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

    Only project members can vote.

     

     

     

    Follow 7 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-08-01 sebald Attached File- => Added octave-fread_index_overflow_check-djs2018aug01.patch, #44680
    2018-08-01 dasergatskov Attached File- => Added t2.m, #44673
    2018-08-01 dasergatskov Attached File- => Added t1.m, #44672
    2018-08-01 sebald Attached File- => Added octave-fread_index_overflow_check-djs2018jul31.patch, #44671
    2018-07-31 rik5 StatusNone => Ready For Test
    2018-07-31 sebald Attached File- => Added attempt_unsigned_index_type-djs2018jul30.diff, #44664
    2018-07-30 sebald Attached File- => Added octave-fread_index_overflow_check-djs2018jul29.patch, #44657

    Back to the top


    Powered by Savane 3.3