939157 - RotateLeft/RotateRight has undefined behavior for shift == 0

Status: RESOLVED FIXED

(Core :: MFBT, defect)

Description

[Jeff Walden [:Waldo]]

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.  :-)

Comment 1

[Sean Stangl [:sstangl]]

Attachment: 0001-Bug-939157-RotateLeft-with-shift-of-zero-gives-undef.patch

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.

Comment 2

[Jeff Walden [:Waldo]]

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.

Comment 3

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/980aebe436cf

Comment 4

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/980aebe436cf

Comment 8

[Sean Stangl [: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.

Comment 9

[Ritu Kothari (:ritu) (Inactive, please n-i to RyanVM, jcristau, or pascal)]

Comment on attachment 8682770 [details] [diff] [review]
0001-Bug-939157-RotateLeft-with-shift-of-zero-gives-undef.patch

Aurora44+

Comment 10

[Carsten Book [:Tomcat]]

(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