Closed Bug 939157 Opened 6 years ago Closed 4 years ago

RotateLeft/RotateRight has undefined behavior for shift == 0

Categories

(Core :: MFBT, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla45
Tracking Status
firefox44 --- fixed
firefox45 --- fixed

People

(Reporter: Waldo, Assigned: sstangl)

References

Details

Attachments

(1 file)

template<typename T>
inline T
RotateLeft(const T t, uint_fast8_t shift)
{
  MOZ_ASSERT(shift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
  static_assert(IsUnsigned<T>::value, "Rotates require unsigned values");
  return (t << shift) | (t >> (sizeof(T) * CHAR_BIT - shift));
}

RotateLeft(uint32_t(5), 0) will invoke undefined behavior, because "The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand."

I happened across this through serendipitously-timed discovery of <http://blog.regehr.org/archives/1054> just now.  :-)
The two options to fix this case are to check for the zero case, or to assert that the zero case is invalid.

RotateLeft/RotateRight are mostly used in hash functions with a fixed positive shift. Across the entire codebase, the only callsite with a possible zero shift is in the ARM integer encoding logic, recently refactored "to be more obviously correct".

Additionally, Waldo verified that compilers are not yet smart enough to optimize away a zero-test branch.

So to keep the hash code as compact as possible, this patch asserts that RotateLeft/RotateRight may not be called with a zero shift. It also then fixes the one troublesome callsite in the ARM code.
Attachment #8682770 - Flags: review?(jwalden+bmo)
Comment on attachment 8682770 [details] [diff] [review]
0001-Bug-939157-RotateLeft-with-shift-of-zero-gives-undef.patch

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

::: mfbt/MathAlgorithms.h
@@ +484,4 @@
>  RotateLeft(const T aValue, uint_fast8_t aShift)
>  {
>    MOZ_ASSERT(aShift < sizeof(T) * CHAR_BIT, "Shift value is too large!");
> +  MOZ_ASSERT(aShift > 0, "Right shift by value size undefined (See Bug 939157).");

This is a bit terse, and it doesn't leave obvious markers telling people to fix this eventually.  How about:

  MOZ_ASSERT(aShift > 0,
             "no known C++ algorithm will perform rotations (even by zero) "
             "without undefined behavior, and be optimized to a rotate "
             "instruction by every compiler, per "
             "<http://blog.regehr.org/archives/1063>; when compiler "
             "improvements make an algorithm possible, please remove this "
             "restriction (<https://gcc.godbolt.org/> to test)");

and same for the other case.
Attachment #8682770 - Flags: review?(jwalden+bmo) → review+
https://hg.mozilla.org/mozilla-central/rev/980aebe436cf
Status: NEW → RESOLVED
Closed: 4 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla45
Duplicate of this bug: 1220275
Duplicate of this bug: 1220915
Duplicate of this bug: 1221299
Assignee: nobody → sstangl
Comment on attachment 8682770 [details] [diff] [review]
0001-Bug-939157-RotateLeft-with-shift-of-zero-gives-undef.patch

Approval Request Comment
[Feature/regressing bug #]: 1207843
[User impact if declined]: ARM jitcode will be invalid if compiled by certain compilers (currently only OSX Clang).
[Describe test coverage new/current, TreeHerder]: Most jit-tests will fail on ARM if that compiler optimizes away the undefined behavior.
[Risks and why]: No risk.
Attachment #8682770 - Flags: approval-mozilla-aurora?
Comment on attachment 8682770 [details] [diff] [review]
0001-Bug-939157-RotateLeft-with-shift-of-zero-gives-undef.patch

Aurora44+
Attachment #8682770 - Flags: approval-mozilla-aurora? → approval-mozilla-aurora+
(In reply to Ritu Kothari (:ritu) from comment #9)
> Comment on attachment 8682770 [details] [diff] [review]
> 0001-Bug-939157-RotateLeft-with-shift-of-zero-gives-undef.patch
> 
> Aurora44+

landed as https://hg.mozilla.org/releases/mozilla-aurora/rev/52c158ae0178
You need to log in before you can comment on or make changes to this bug.