Last Comment Bug 768538 - Fix undefined behavior in CheckedInt
: Fix undefined behavior in CheckedInt
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: MFBT (show other bugs)
: unspecified
: All All
: -- normal (vote)
: mozilla16
Assigned To: Benoit Jacob [:bjacob] (mostly away)
:
:
Mentors:
Depends on:
Blocks: 633560
  Show dependency treegraph
 
Reported: 2012-06-26 10:24 PDT by Benoit Jacob [:bjacob] (mostly away)
Modified: 2012-07-08 17:50 PDT (History)
8 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
fix undefined behavior in CheckedInt (1.68 KB, patch)
2012-06-26 10:24 PDT, Benoit Jacob [:bjacob] (mostly away)
jwalden+bmo: review+
Details | Diff | Splinter Review
another fix in the unit test (1.80 KB, patch)
2012-06-26 10:34 PDT, Benoit Jacob [:bjacob] (mostly away)
jwalden+bmo: review+
Details | Diff | Splinter Review
apply Jeff's review comment; further simplification; remove the separate operator/ implementation (2.64 KB, patch)
2012-07-08 08:00 PDT, Benoit Jacob [:bjacob] (mostly away)
Ms2ger: review+
Details | Diff | Splinter Review
HasSignBit should return bool (1.14 KB, patch)
2012-07-08 08:34 PDT, Benoit Jacob [:bjacob] (mostly away)
Ms2ger: review+
Details | Diff | Splinter Review

Description Benoit Jacob [:bjacob] (mostly away) 2012-06-26 10:24:41 PDT
Created attachment 636770 [details] [diff] [review]
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) 2012-06-26 10:34:57 PDT
Created attachment 636776 [details] [diff] [review]
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) 2012-06-26 10:39:18 PDT
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 2012-06-26 10:43:10 PDT
Noted.  I'll do the sync.  Thanks for the heads up
Comment 4 Jeff Walden [:Waldo] (remove +bmo to email) 2012-06-28 18:02:59 PDT
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 7 :Ms2ger (⌚ UTC+1/+2) 2012-07-07 12:07:40 PDT
(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) 2012-07-07 15:06:36 PDT
Oops. Sorry, doing it ASAP.
Comment 9 Benoit Jacob [:bjacob] (mostly away) 2012-07-08 08:00:06 PDT
Created attachment 640068 [details] [diff] [review]
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 (⌚ UTC+1/+2) 2012-07-08 08:10:54 PDT
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) 2012-07-08 08:19:51 PDT
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) 2012-07-08 08:26:51 PDT
http://hg.mozilla.org/integration/mozilla-inbound/rev/5a372bbee65c

(With blank line after the if)
Comment 13 Benoit Jacob [:bjacob] (mostly away) 2012-07-08 08:34:19 PDT
Created attachment 640070 [details] [diff] [review]
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 (⌚ UTC+1/+2) 2012-07-08 08:36:33 PDT
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) 2012-07-08 08:45:51 PDT
http://hg.mozilla.org/integration/mozilla-inbound/rev/3cfacdaa3438

Note You need to log in before you can comment on or make changes to this bug.