768538 - Fix undefined behavior in CheckedInt

Status: RESOLVED FIXED

(Core :: MFBT, defect)

Description

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: fix undefined behavior in CheckedInt

According to IOC,

 http://embed.cs.utah.edu/ioc/

while running TestCheckedInt, we are relying on undefined behavior in CheckedInt's +, -, * operators. Sample error:

CLANG ARITHMETIC UNDEFINED at <./mozilla/CheckedInt.h, (690:1)> : Op: *, Reason : Signed Multiplication Overflow, BINARY OPERATION: left (int32): 65535 right (int32): 65535 


The precise issue is in the operators generated by the MOZ_CHECKEDINT_BASIC_BINARY_OPERATOR macro:

#define MOZ_CHECKEDINT_BASIC_BINARY_OPERATOR(NAME, OP)                \
template<typename T>                                                  \
inline CheckedInt<T> operator OP(const CheckedInt<T> &lhs,            \
                                 const CheckedInt<T> &rhs)            \
{                                                                     \
  T x = lhs.mValue;                                                   \
  T y = rhs.mValue;                                                   \
  T result = x OP y;                                                  \
  T isOpValid = detail::Is##NAME##Valid(x, y);                        \
  /* Help the compiler perform RVO (return value optimization). */    \
  return CheckedInt<T>(result,                                        \
                       lhs.mIsValid && rhs.mIsValid && isOpValid);    \
}

The problem is that |result| is unconditionally computed, regardless of |isOpValid|.

The fix is to rewrite this as:

#define MOZ_CHECKEDINT_BASIC_BINARY_OPERATOR(NAME, OP)                \
template<typename T>                                                  \
inline CheckedInt<T> operator OP(const CheckedInt<T> &lhs,            \
                                 const CheckedInt<T> &rhs)            \
{                                                                     \
  T x = lhs.mValue;                                                   \
  T y = rhs.mValue;                                                   \
  T isOpValid = detail::Is##NAME##Valid(x, y);                        \
  if (isOpValid) {                                                    \
    T result = x OP y;                                                \
    return CheckedInt<T>(result, lhs.mIsValid && rhs.mIsValid);       \
  } else {                                                            \
    return CheckedInt<T>(T(0), false);                                \
  }                                                                   \
}

Comment 1

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: another fix in the unit test

This was also found by IOC. Now it runs cleanly without errors.

The issue was that for signed types of size >= the size of |int|, computing x<<1 for x = the minimum representable value is undefined behavior. (This is not an issue for smaller types due to implicit conversion to int). Anyway, I fixed this part of the unit test by switching to unsigned types since this is purely bit-field manipulation.

Comment 2

[Benoit Jacob [:bjacob] (mostly away)]

Ken, Mo, you'll probably want to sync WebKit's copy with this. It might be easiest to wait for this to land in mozilla-central and then copy the files, unless you have substantial local changes.

Comment 3

[Zhenyao Mo]

Noted.  I'll do the sync.  Thanks for the heads up

Comment 4

[Jeff Walden [:Waldo]]

Comment on attachment 636770 [details] [diff] [review]
fix undefined behavior in CheckedInt

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

::: mfbt/CheckedInt.h
@@ +683,5 @@
> +    T result = x OP y;                                                \
> +    return CheckedInt<T>(result, lhs.mIsValid && rhs.mIsValid);       \
> +  } else {                                                            \
> +    return CheckedInt<T>(T(0), false);                                \
> +  }                                                                   \

Let's write this this way, to get rid of else-after-return oddities, to reduce indentation, and to make the invalidity case read as a mere side show:

  if (!detail::Is##NAME##Valid(x, y))
    return CheckedInt<T>(T(0), false);
  return CheckedInt<T>(T(x OP y), lhs.mIsValid && rhs.mIsValid);

(I'm only assuming the T() on x OP y is necessary, don't add it if it's not needed.)

Comment 5

[Benoit Jacob [:bjacob] (mostly away)]

http://hg.mozilla.org/integration/mozilla-inbound/rev/d0d426929fda
http://hg.mozilla.org/integration/mozilla-inbound/rev/79f74e4d885c

Comment 6

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/d0d426929fda
https://hg.mozilla.org/mozilla-central/rev/79f74e4d885c

Comment 7

[:Ms2ger (he/him; ⌚ UTC+1/+2)]

(In reply to Jeff Walden [:Waldo] (busy, try to prefer other reviewers if possible) from comment #4)
> Comment on attachment 636770 [details] [diff] [review]
> fix undefined behavior in CheckedInt
> 
> Review of attachment 636770 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: mfbt/CheckedInt.h
> @@ +683,5 @@
> > +    T result = x OP y;                                                \
> > +    return CheckedInt<T>(result, lhs.mIsValid && rhs.mIsValid);       \
> > +  } else {                                                            \
> > +    return CheckedInt<T>(T(0), false);                                \
> > +  }                                                                   \
> 
> Let's write this this way, to get rid of else-after-return oddities, to
> reduce indentation, and to make the invalidity case read as a mere side show:
> 
>   if (!detail::Is##NAME##Valid(x, y))
>     return CheckedInt<T>(T(0), false);
>   return CheckedInt<T>(T(x OP y), lhs.mIsValid && rhs.mIsValid);
> 
> (I'm only assuming the T() on x OP y is necessary, don't add it if it's not
> needed.)

This doesn't appear to have been addressed...

Comment 8

[Benoit Jacob [:bjacob] (mostly away)]

Oops. Sorry, doing it ASAP.

Comment 9

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: apply Jeff's review comment; further simplification; remove the separate operator/ implementation

So it turned out that while doing this fix, one could go a bit further, so there seems to be just enough here to ask for a new review.

Comment 10

[:Ms2ger (he/him; ⌚ UTC+1/+2)]

Comment on attachment 640068 [details] [diff] [review]
apply Jeff's review comment; further simplification; remove the separate operator/ implementation

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

LGTM with the braces added, thanks.

::: mfbt/CheckedInt.h
@@ +712,5 @@
>  inline CheckedInt<T> operator OP(const CheckedInt<T> &lhs,            \
>                                   const CheckedInt<T> &rhs)            \
>  {                                                                     \
> +  if (!detail::Is##NAME##Valid(lhs.mValue, rhs.mValue))               \
> +    return CheckedInt<T>(0, false);                                   \

{}

Comment 11

[Benoit Jacob [:bjacob] (mostly away)]

From mfbt/STYLE:

== Bracing ==

Don't brace single statements.

  if (y == 7)
    return 3;
  for (size_t i = 0; i < 5; i++)
    frob(i);

But do brace them if the statement (or condition(s) or any additional
consequents, if the braces would be associated with an if statement) occupies
multiple lines.


-> So I don't think that braces are needed here.

Comment 12

[Benoit Jacob [:bjacob] (mostly away)]

http://hg.mozilla.org/integration/mozilla-inbound/rev/5a372bbee65c

(With blank line after the if)

Comment 13

[Benoit Jacob [:bjacob] (mostly away)]

Attachment: HasSignBit should return bool

Just something I noticed while glancing at this code. This is a remnant of an earlier design where we tried to keep everything of sign T to avoid useless conversions. We're no longer doing that. This HasSignBit function is only used in 2 occurences in this file, where its return value is used as a bool anyway.

Comment 14

[:Ms2ger (he/him; ⌚ UTC+1/+2)]

Comment on attachment 640070 [details] [diff] [review]
HasSignBit should return bool

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

Thanks.

::: mfbt/CheckedInt.h
@@ +242,5 @@
>   * Ideas taken from IntegerLib, code different.
>   */
>  
>  // Bitwise ops may return a larger type, so it's good to use these inline
>  // helpers guaranteeing that the result is really of type T.

Move this down, I guess.

Comment 15

[Benoit Jacob [:bjacob] (mostly away)]

http://hg.mozilla.org/integration/mozilla-inbound/rev/3cfacdaa3438

Comment 16

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/5a372bbee65c
https://hg.mozilla.org/mozilla-central/rev/3cfacdaa3438