Closed Bug 1441657 Opened 2 years ago Closed 2 years ago

Implement mfbt/WrappingOperations.h for wraparound math operations and conversions

Categories

(Core :: MFBT, enhancement)

enhancement
Not set

Tracking

()

RESOLVED FIXED
mozilla60
Tracking Status
firefox60 --- fixed

People

(Reporter: Waldo, Assigned: Waldo)

Details

Attachments

(2 files, 1 obsolete file)

If we're to get a handle on various forms of signed overflow, we probably will have to have forms of them that wrap *safely*.  This header will be where those can be defined.
If you can point at other depends-on-wrapping places that demand implementation of the other basic math operations, I'd love to know so they can be implemented and people can be pointed at them.  In advance of that, tho, it's hard to justify just implementing without identified users.
Attachment #8954512 - Flags: review?(nfroyd)
Let's add a few more uses/remove a couple blacklist entries.
Attachment #8954642 - Flags: review?(nfroyd)
Attachment #8954512 - Attachment is obsolete: true
Attachment #8954512 - Flags: review?(nfroyd)
Hrm:

https://developercommunity.visualstudio.com/content/problem/55671/c4307-issued-for-unsigned.html

Might be the patch needs to be augmented with some MSVC-specific #pragmas to disable that warning in WrappingMultiply.  Or then again, https://stackoverflow.com/questions/37658794/integer-constant-overflow-warning-in-constexpr claims even that doesn't work.  Will do some more futzing.
Comment on attachment 8954510 [details] [diff] [review]
Create a new mozilla/WrappingOperations.h header, move WrapToSigned to it

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

::: js/src/jsmath.cpp
@@ -490,5 @@
>  
>      uint32_t product = a * b;
> -    res.setInt32(product > INT32_MAX
> -                 ? int32_t(INT32_MIN + (product - INT32_MAX - 1))
> -                 : int32_t(product));

o.O
Attachment #8954510 - Flags: review?(nfroyd) → review+
Comment on attachment 8954642 [details] [diff] [review]
Implement mozilla::WrappingMultiply

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

r=me with some changes below.

::: mfbt/WrappingOperations.h
@@ +125,5 @@
> +} // namespace detail
> +
> +/**
> + * Multiply two integers of the same type, and return that result converted to
> + * that type using wraparound semantics.

Do we want to say something here about "this is what you get normally with unsigned types, but this operator both makes it more explicit that this behavior is expected and desired, and also prevents ubsan from complaining about it" (as well as handling the signed integer case with aplomb)?  It's not immediately obvious to me why you would want to use this otherwise.

Maybe such a comment belongs at the head of WrappingOperations.h instead?  Not sure.

@@ +131,5 @@
> + * For N-bit unsigned integer types, this is equivalent to multiplying the two
> + * numbers, then taking the result mod 2**N:
> + *
> + *   WrappingMultiply(uint8_t(16), uint8_t(24)) is 128 (384 mod 2**8);
> + *   WrappingMultiply(int32_t(16), int32_t(255)) is 240 (4080 mod 2*32);

This example refers to `mod 2*32`, but the above comment refers to `mod 2**N`; it's not really obvious to me where the 2*32 comes in...  Did you mean `mod 2**8` here, and to cast the constants to `uint8_t`?
Attachment #8954642 - Flags: review?(nfroyd) → review+
MSVC #pragmas don't work, unfortunately, I guess because constexpr causes the warnings to be emitted *for call sites* and pragmas can't touch that.  So I removed all the constexpr and used MOZ_RELEASE_ASSERT for tests.

(In reply to Nathan Froyd [:froydnj] from comment #6)
> Do we want to say something here about "this is what you get normally with
> unsigned types, but this operator both makes it more explicit that this
> behavior is expected and desired, and also prevents ubsan from complaining
> about it" (as well as handling the signed integer case with aplomb)?  It's
> not immediately obvious to me why you would want to use this otherwise.

Seems fair.

There is one additional reason to use this function: uint16_t*uint16_t can invoke undefined behavior, *if* the operands are big enough that when promoted to |int|, the now-signed multiplication overflows |int|.  See http://kqueue.org/blog/2013/09/17/cltq/ for more.  (The same is instead possible with uint32_t if |int| is a signed 64-bit integer, although I'm not sure we compile with anything like that now.)

I added a bunch of comments along these lines and others to lay out the reasons for the function and why to use it.

> This example refers to `mod 2*32`, but the above comment refers to `mod
> 2**N`; it's not really obvious to me where the 2*32 comes in...  Did you
> mean `mod 2**8` here, and to cast the constants to `uint8_t`?

Yeah, this is a bit off.  I've beefed up the examples here and fixed the boogs in them.

Will probably land the whole thing tomorrow after a try-run today.
Pushed by jwalden@mit.edu:
https://hg.mozilla.org/integration/mozilla-inbound/rev/bc01e52c16d7
Create a new mozilla/WrappingOperations.h header to contain implementations of common math operations with well-defined wraparound semantics.  r=froydnj
https://hg.mozilla.org/integration/mozilla-inbound/rev/cf32e82edfb7
Implement mozilla::WrappingMultiply.  r=froydnj
https://hg.mozilla.org/mozilla-central/rev/bc01e52c16d7
https://hg.mozilla.org/mozilla-central/rev/cf32e82edfb7
Status: ASSIGNED → RESOLVED
Closed: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla60
I filed https://developercommunity.visualstudio.com/content/problem/211134/unsigned-integer-overflows-in-constexpr-functionsa.html as an MSVC bug on the unsigned overflow warning.  Will note it in comments in WrappingOperations.h either in passing at some point, or as part of a future patch.
You need to log in before you can comment on or make changes to this bug.