1432642 - UBSan: signed integer overflow in [@ quorem2]

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Tyson Smith [:tsmith]]

Found with changeset: 400421:c5461973d6ee
Built with -fsanitize=signed-integer-overflow

/js/src/jsdtoa.cpp:263:19: runtime error: signed integer overflow: -2147483648 - 1 cannot be represented in type 'int'
    #0 0x7f8a542ba23e in quorem2(Bigint*, int) /js/src/jsdtoa.cpp:263:19
    #1 0x7f8a542b7e48 in js_dtobasestr(DtoaState*, int, double) /js/src/jsdtoa.cpp:443:21
    #2 0x7f8a535ef458 in FracNumberToCString(JSContext*, js::ToCStringBuf*, double, int) /js/src/jsnum.cpp:1319:31
    #3 0x7f8a535ef700 in JSString* NumberToStringWithBase<(js::AllowGC)1>(JSContext*, double, int) /js/src/jsnum.cpp:1375:18
    #4 0x7f8a535ec18d in num_toString_impl /js/src/jsnum.cpp:734:21
    #5 0x7f8a535ec18d in CallNonGenericMethod<&IsNumber, &num_toString_impl> /objdir-ff-ubsan/dist/include/js/CallNonGenericMethod.h:100
    #6 0x7f8a535ec18d in js::num_toString(JSContext*, unsigned int, JS::Value*) /js/src/jsnum.cpp:747
    #7 0x7f8a52a0177e in CallJSNative /js/src/jscntxtinlines.h:291:15
    #8 0x7f8a52a0177e in js::InternalCallOrConstruct(JSContext*, JS::CallArgs const&, js::MaybeConstruct) /js/src/vm/Interpreter.cpp:473
    #9 0x7f8a52a023bf in InternalCall(JSContext*, js::AnyInvokeArgs const&) /js/src/vm/Interpreter.cpp:522:12
    #10 0x7f8a529e777f in Interpret(JSContext*, js::RunState&) /js/src/vm/Interpreter.cpp:3096:18
    #11 0x7f8a529ca318 in js::RunScript(JSContext*, js::RunState&) /js/src/vm/Interpreter.cpp:423:12
    #12 0x7f8a52a01669 in js::InternalCallOrConstruct(JSContext*, JS::CallArgs const&, js::MaybeConstruct) /js/src/vm/Interpreter.cpp:495:15
    #13 0x7f8a52a023bf in InternalCall(JSContext*, js::AnyInvokeArgs const&) /js/src/vm/Interpreter.cpp:522:12
    #14 0x7f8a52a0259a in js::Call(JSContext*, JS::Handle<JS::Value>, JS::Handle<JS::Value>, js::AnyInvokeArgs const&, JS::MutableHandle<JS::Value>) /js/src/vm/Interpreter.cpp:541:10
    #15 0x7f8a532128fe in js::jit::InvokeFunction(JSContext*, JS::Handle<JSObject*>, bool, bool, unsigned int, JS::Value*, JS::MutableHandle<JS::Value>) /js/src/jit/VMFunctions.cpp:112:12
    #16 0x7f8a532133d5 in js::jit::InvokeFromInterpreterStub(JSContext*, js::jit::InterpreterStubExitFrameLayout*) /js/src/jit/VMFunctions.cpp:141:10
    #17 0x1b6f2e0e4f76  (<unknown module>)

Comment 1

[Jeff Walden [:Waldo]]

The code in js_dtobasestr, that feeds a number with its lowest five bits set to quorem2, is as abstruse as one would expect.  It is not at all immediately apparent what the code is doing, what the variables represent, etc. to say exactly how this can happen.  Is there any chance I could get a testcase that triggered this?  That would be a much more effective use of time than me trying to reverse-engineer how we got into this state, although maybe I'll have to do that eventually.

Comment 2

[Tyson Smith [:tsmith]]

(In reply to Jeff Walden [:Waldo] from comment #1)
> Is there any chance I could get a testcase that triggered this?

I found this with regular web surfing. At the moment opening https://weather.com/en-CA/ will trigger the issue.

Comment 3

[Jeff Walden [:Waldo]]

Thanks a ton!  That did the trick.

Also, ye gods:

[jwalden@find-waldo-now src]$ dbg/js/src/js -e '(0.0012947733354370383).toString(16)'
/home/jwalden/moz/after/js/src/jsdtoa.cpp:263:19: runtime error: signed integer overflow: -2147483648 - 1 cannot be represented in type 'int'

Hexadecimal printing of floating-point numbers with fractional components.  Could it get any worse...

Comment 4

[Jeff Walden [:Waldo]]

Actually, hexadecimal printing of floating-point numbers with fractional components really *should* be very simple: read four significant bits at a time out of the significand/potential implicit one bit in the number and straightforwardly translate to hexadecimal.  Similar ease of use should apply for the other binary-power radixes.  Of course, dtoa.c{,pp} don't perform such special-casing right now.  (And even if they did, there's no guarantee yet that the problem here doesn't manifest with exponents that aren't 10 or a power of two.)

Comment 5

[Jeff Walden [:Waldo]]

This may or may not be a reduced testcase form of the original reported bug:

[jwalden@find-waldo-now after]$ js/src/dbg/js/src/js
js> (0b11 / 2**11).toString(2)
/home/jwalden/moz/after/js/src/jsdtoa.cpp:263:19: runtime error: signed integer overflow: -2147483648 - 1 cannot be represented in type 'int'
"0.00000000011"

In any event, I think I can say with 100% confidence that this testcase is at least worlds easier to investigate than the original one.  So I'll be looking into it and hoping it's adequate to diagnose the full problem here.

(My point in comment 4 that power-of-two exponent *should* be a simple special case remains, tho.)

Comment 6

[Jeff Walden [:Waldo]]

Simpler yet (only a single bit set!  and only exponent bits, no significand bits in sight):

[jwalden@find-waldo-now after]$ js/src/dbg/js/src/js -e '(1/512).toString(2)'
/home/jwalden/moz/after/js/src/jsdtoa.cpp:263:19: runtime error: signed integer overflow: -2147483648 - 1 cannot be represented in type 'int'

Comment 7

[Jeff Walden [:Waldo]]

Attachment: Patch

So, some background on this code from some light bedtime reading, 'cause otherwise this is gonna be even more a royal pain to understand/verify.

The dtoa code works in terms of Bigint structs and various sorts of maths on them.  Bigint stores a series of binary bits in Bigint::x[0..Bigint::wds], each a ULong=uint32_t, with bits of the integer in little-endian order.

The particular function here has this signature:

/* Return floor(b/2^k) and set b to be the remainder.  The returned quotient must be less than 2^32. */
static uint32_t quorem2(Bigint* b, int32_t k)

So the idea is you mutate-divide |b| by removing high-order binary bits -- no more than 32 of them -- in Bigint::x[0..Bigint::wds] and returning them.  Because |k| isn't limited to [0, 32) or similar, that shift is decomposed into two operations: removing N*32 bits at a time to start, then shifting and masking whatever bits remain in |b->x| and the returned quotient.  (It looks to be an invariant that |Bigint::x[Bigint::wds - 1]| is non-zero, which is to say the overall bigint is compact without any extraneous words of zero bits.)

The algorithm here is the best sort of C without any abstraction, and every user of the Bigint struct being very familiar with every field and being responsible for maintaining meaning of every field.  But if you look closely, you *can* see the ideas described above:

static uint32_t quorem2(Bigint* b, int32_t k)
{
    ULong mask;
    ULong result;
    ULong* bx;
    ULong* bxe;
    int32_t w;
    int32_t n = k >> 5;
    k &= 0x1F;
    mask = (ULong(1)<<k) - 1;

    w = b->wds - n; // REMOVING
    if (w <= 0)     // N*32
        return 0;   // BITS
    MOZ_ASSERT(w <= 2);
    bx = b->x;
    bxe = bx + n;
    result = *bxe >> k;
    *bxe &= mask;
...

The removing of N*32 bits at a time is in the commented lines.  (If N*32 > total bits, then |b| is left unchanged because there are no bits past 2**k in it, and the floordiv result returned is 0.)

That done, the most significant uint32_t of bits is 1) right-shifted to remove the lingering bits from |k| (note |k| has been reduced by N*32 already) to be returned as |result|, and 2) masked so only those |k| remaining bits are present in the remainder.

With this understanding, |mask| *is* appropriately named, it *is* a bit mask, and so constructing it by left-shifting 1 cast to mask-type is the right thing to do.

(...and the remaining unquoted code in the function merely addresses putting bits not in that now-highest uint32_t of bits into the result, and preserving the Bigint::x-is-compact invariant.)

Comment 8

[Jason Orendorff [:jorendorff]]

Comment on attachment 8951939 [details] [diff] [review]
Patch

Review of attachment 8951939 [details] [diff] [review]:
-----------------------------------------------------------------

Nice comment!

Comment 9

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/0dc87bc68608
When constructing a bit mask in jsdtoa.cpp:quorem2 using |(1 << shiftAmount) - 1|, cast the first |1| to the mask type to eliminate signed integer underflow when |shiftAmount| would make the shift equal the most-negative signed integer.  r=jorendorff

Comment 10

[Andreea Pavel [:apavel]]

https://hg.mozilla.org/mozilla-central/rev/0dc87bc68608