summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--js/public/Conversions.h1
-rw-r--r--js/public/Utility.h3
-rw-r--r--js/src/jsmath.cpp13
-rw-r--r--mfbt/Attributes.h124
-rw-r--r--mfbt/HashFunctions.h8
-rw-r--r--mfbt/WrappingOperations.h188
-rw-r--r--mfbt/moz.build1
7 files changed, 328 insertions, 10 deletions
diff --git a/js/public/Conversions.h b/js/public/Conversions.h
index 1850a42f0e..200fc030fb 100644
--- a/js/public/Conversions.h
+++ b/js/public/Conversions.h
@@ -11,6 +11,7 @@
#include "mozilla/Casting.h"
#include "mozilla/FloatingPoint.h"
#include "mozilla/TypeTraits.h"
+#include "mozilla/WrappingOperations.h"
#include <math.h>
diff --git a/js/public/Utility.h b/js/public/Utility.h
index cadcef7000..dbe69e18c0 100644
--- a/js/public/Utility.h
+++ b/js/public/Utility.h
@@ -14,6 +14,7 @@
#include "mozilla/Scoped.h"
#include "mozilla/TemplateLib.h"
#include "mozilla/UniquePtr.h"
+#include "mozilla/WrappingOperations.h"
#include <stdlib.h>
#include <string.h>
@@ -539,7 +540,7 @@ ScrambleHashCode(HashNumber h)
* are stored in a hash table; see Knuth for details.
*/
static const HashNumber goldenRatio = 0x9E3779B9U;
- return h * goldenRatio;
+ return mozilla::WrappingMultiply(h, goldenRatio);
}
} /* namespace detail */
diff --git a/js/src/jsmath.cpp b/js/src/jsmath.cpp
index 75ab8fcb29..b98dba57cd 100644
--- a/js/src/jsmath.cpp
+++ b/js/src/jsmath.cpp
@@ -13,6 +13,7 @@
#include "mozilla/MathAlgorithms.h"
#include "mozilla/MemoryReporting.h"
#include "mozilla/Unused.h"
+#include "mozilla/WrappingOperations.h"
#include <algorithm> // for std::max
#include <fcntl.h>
@@ -103,6 +104,7 @@ using mozilla::IsNegative;
using mozilla::IsNegativeZero;
using mozilla::PositiveInfinity;
using mozilla::NegativeInfinity;
+using mozilla::WrappingMultiply;
using JS::ToNumber;
using JS::GenericNaN;
@@ -458,16 +460,13 @@ js::math_floor(JSContext* cx, unsigned argc, Value* vp)
bool
js::math_imul_handle(JSContext* cx, HandleValue lhs, HandleValue rhs, MutableHandleValue res)
{
- uint32_t a = 0, b = 0;
- if (!lhs.isUndefined() && !ToUint32(cx, lhs, &a))
+ int32_t a = 0, b = 0;
+ if (!lhs.isUndefined() && !ToInt32(cx, lhs, &a))
return false;
- if (!rhs.isUndefined() && !ToUint32(cx, rhs, &b))
+ if (!rhs.isUndefined() && !ToInt32(cx, rhs, &b))
return false;
- uint32_t product = a * b;
- res.setInt32(product > INT32_MAX
- ? int32_t(INT32_MIN + (product - INT32_MAX - 1))
- : int32_t(product));
+ res.setInt32(WrappingMultiply(a, b));
return true;
}
diff --git a/mfbt/Attributes.h b/mfbt/Attributes.h
index 9bce9a128a..f5572e1861 100644
--- a/mfbt/Attributes.h
+++ b/mfbt/Attributes.h
@@ -301,6 +301,130 @@
#else
# define MOZ_FALLTHROUGH /* FALLTHROUGH */
#endif
+/*
+ * MOZ_ASAN_BLACKLIST is a macro to tell AddressSanitizer (a compile-time
+ * instrumentation shipped with Clang and GCC) to not instrument the annotated
+ * function. Furthermore, it will prevent the compiler from inlining the
+ * function because inlining currently breaks the blacklisting mechanism of
+ * AddressSanitizer.
+ */
+#if defined(__has_feature)
+# if __has_feature(address_sanitizer)
+# define MOZ_HAVE_ASAN_BLACKLIST
+# endif
+#elif defined(__GNUC__)
+# if defined(__SANITIZE_ADDRESS__)
+# define MOZ_HAVE_ASAN_BLACKLIST
+# endif
+#endif
+
+#if defined(MOZ_HAVE_ASAN_BLACKLIST)
+# define MOZ_ASAN_BLACKLIST \
+ MOZ_NEVER_INLINE __attribute__((no_sanitize_address))
+#else
+# define MOZ_ASAN_BLACKLIST /* nothing */
+#endif
+
+/*
+ * MOZ_TSAN_BLACKLIST is a macro to tell ThreadSanitizer (a compile-time
+ * instrumentation shipped with Clang) to not instrument the annotated function.
+ * Furthermore, it will prevent the compiler from inlining the function because
+ * inlining currently breaks the blacklisting mechanism of ThreadSanitizer.
+ */
+#if defined(__has_feature)
+# if __has_feature(thread_sanitizer)
+# define MOZ_TSAN_BLACKLIST \
+ MOZ_NEVER_INLINE __attribute__((no_sanitize_thread))
+# else
+# define MOZ_TSAN_BLACKLIST /* nothing */
+# endif
+#else
+# define MOZ_TSAN_BLACKLIST /* nothing */
+#endif
+
+#if defined(__has_attribute)
+# if __has_attribute(no_sanitize)
+# define MOZ_HAVE_NO_SANITIZE_ATTR
+# endif
+#endif
+
+#ifdef __clang__
+# ifdef MOZ_HAVE_NO_SANITIZE_ATTR
+# define MOZ_HAVE_UNSIGNED_OVERFLOW_SANITIZE_ATTR
+# define MOZ_HAVE_SIGNED_OVERFLOW_SANITIZE_ATTR
+# endif
+#endif
+
+/*
+ * MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW disables *un*signed integer overflow
+ * checking on the function it annotates, in builds configured to perform it.
+ * (Currently this is only Clang using -fsanitize=unsigned-integer-overflow, or
+ * via --enable-unsigned-overflow-sanitizer in Mozilla's build system.) It has
+ * no effect in other builds.
+ *
+ * Place this attribute at the very beginning of a function declaration.
+ *
+ * Unsigned integer overflow isn't *necessarily* a bug. It's well-defined in
+ * C/C++, and code may reasonably depend upon it. For example,
+ *
+ * MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW inline bool
+ * IsDecimal(char aChar)
+ * {
+ * // For chars less than '0', unsigned integer underflow occurs, to a value
+ * // much greater than 10, so the overall test is false.
+ * // For chars greater than '0', no overflow occurs, and only '0' to '9'
+ * // pass the overall test.
+ * return static_cast<unsigned int>(aChar) - '0' < 10;
+ * }
+ *
+ * But even well-defined unsigned overflow often causes bugs when it occurs, so
+ * it should be restricted to functions annotated with this attribute.
+ *
+ * The compiler instrumentation to detect unsigned integer overflow has costs
+ * both at compile time and at runtime. Functions that are repeatedly inlined
+ * at compile time will also implicitly inline the necessary instrumentation,
+ * increasing compile time. Similarly, frequently-executed functions that
+ * require large amounts of instrumentation will also notice significant runtime
+ * slowdown to execute that instrumentation. Use this attribute to eliminate
+ * those costs -- but only after carefully verifying that no overflow can occur.
+ */
+#ifdef MOZ_HAVE_UNSIGNED_OVERFLOW_SANITIZE_ATTR
+# define MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW \
+ __attribute__((no_sanitize("unsigned-integer-overflow")))
+#else
+# define MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW /* nothing */
+#endif
+
+/*
+ * MOZ_NO_SANITIZE_SIGNED_OVERFLOW disables *signed* integer overflow checking
+ * on the function it annotates, in builds configured to perform it. (Currently
+ * this is only Clang using -fsanitize=signed-integer-overflow, or via
+ * --enable-signed-overflow-sanitizer in Mozilla's build system. GCC support
+ * will probably be added in the future.) It has no effect in other builds.
+ *
+ * Place this attribute at the very beginning of a function declaration.
+ *
+ * Signed integer overflow is undefined behavior in C/C++: *anything* can happen
+ * when it occurs. *Maybe* wraparound behavior will occur, but maybe also the
+ * compiler will assume no overflow happens and will adversely optimize the rest
+ * of your code. Code that contains signed integer overflow needs to be fixed.
+ *
+ * The compiler instrumentation to detect signed integer overflow has costs both
+ * at compile time and at runtime. Functions that are repeatedly inlined at
+ * compile time will also implicitly inline the necessary instrumentation,
+ * increasing compile time. Similarly, frequently-executed functions that
+ * require large amounts of instrumentation will also notice significant runtime
+ * slowdown to execute that instrumentation. Use this attribute to eliminate
+ * those costs -- but only after carefully verifying that no overflow can occur.
+ */
+#ifdef MOZ_HAVE_SIGNED_OVERFLOW_SANITIZE_ATTR
+# define MOZ_NO_SANITIZE_SIGNED_OVERFLOW \
+ __attribute__((no_sanitize("signed-integer-overflow")))
+#else
+# define MOZ_NO_SANITIZE_SIGNED_OVERFLOW /* nothing */
+#endif
+
+#undef MOZ_HAVE_NO_SANITIZE_ATTR
/*
* The following macros are attributes that support the static analysis plugin
diff --git a/mfbt/HashFunctions.h b/mfbt/HashFunctions.h
index cc9a1d68c1..d287081174 100644
--- a/mfbt/HashFunctions.h
+++ b/mfbt/HashFunctions.h
@@ -51,6 +51,7 @@
#include "mozilla/Char16.h"
#include "mozilla/MathAlgorithms.h"
#include "mozilla/Types.h"
+#include "mozilla/WrappingOperations.h"
#include <stdint.h>
@@ -95,7 +96,9 @@ AddU32ToHash(uint32_t aHash, uint32_t aValue)
* Otherwise, if |aHash| is 0 (as it often is for the beginning of a
* message), the expression
*
- * (kGoldenRatioU32 * RotateBitsLeft(aHash, 5)) |xor| aValue
+ * mozilla::WrappingMultiply(kGoldenRatioU32, RotateBitsLeft(aHash, 5))
+ * |xor|
+ * aValue
*
* evaluates to |aValue|.
*
@@ -113,7 +116,8 @@ AddU32ToHash(uint32_t aHash, uint32_t aValue)
* multiplicative effect. Our golden ratio constant has order 2^29, which is
* more than enough for our purposes.)
*/
- return kGoldenRatioU32 * (RotateBitsLeft32(aHash, 5) ^ aValue);
+ return mozilla::WrappingMultiply(kGoldenRatioU32,
+ (RotateBitsLeft32(aHash, 5) ^ aValue));
}
/**
diff --git a/mfbt/WrappingOperations.h b/mfbt/WrappingOperations.h
new file mode 100644
index 0000000000..c93626f653
--- /dev/null
+++ b/mfbt/WrappingOperations.h
@@ -0,0 +1,188 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+/*
+ * Math operations that implement wraparound semantics on overflow or underflow
+ * without performing C++ undefined behavior or tripping up compiler-based
+ * integer-overflow sanitizers.
+ */
+
+#ifndef mozilla_WrappingOperations_h
+#define mozilla_WrappingOperations_h
+
+#include "mozilla/Attributes.h"
+#include "mozilla/TypeTraits.h"
+
+#include <limits.h>
+
+namespace mozilla {
+
+namespace detail {
+
+template<typename UnsignedType>
+struct WrapToSignedHelper
+{
+ static_assert(mozilla::IsUnsigned<UnsignedType>::value,
+ "WrapToSigned must be passed an unsigned type");
+
+ using SignedType = typename mozilla::MakeSigned<UnsignedType>::Type;
+
+ static constexpr SignedType MaxValue =
+ (UnsignedType(1) << (CHAR_BIT * sizeof(SignedType) - 1)) - 1;
+ static constexpr SignedType MinValue = -MaxValue - 1;
+
+ static constexpr UnsignedType MinValueUnsigned =
+ static_cast<UnsignedType>(MinValue);
+ static constexpr UnsignedType MaxValueUnsigned =
+ static_cast<UnsignedType>(MaxValue);
+
+ // Overflow-correctness was proven in bug 1432646 and is explained in the
+ // comment below. This function is very hot, both at compile time and
+ // runtime, so disable all overflow checking in it.
+ MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW MOZ_NO_SANITIZE_SIGNED_OVERFLOW
+ static constexpr SignedType compute(UnsignedType aValue)
+ {
+ // This algorithm was originally provided here:
+ // https://stackoverflow.com/questions/13150449/efficient-unsigned-to-signed-cast-avoiding-implementation-defined-behavior
+ //
+ // If the value is in the non-negative signed range, just cast.
+ //
+ // If the value will be negative, compute its delta from the first number
+ // past the max signed integer, then add that to the minimum signed value.
+ //
+ // At the low end: if |u| is the maximum signed value plus one, then it has
+ // the same mathematical value as |MinValue| cast to unsigned form. The
+ // delta is zero, so the signed form of |u| is |MinValue| -- exactly the
+ // result of adding zero delta to |MinValue|.
+ //
+ // At the high end: if |u| is the maximum *unsigned* value, then it has all
+ // bits set. |MinValue| cast to unsigned form is purely the high bit set.
+ // So the delta is all bits but high set -- exactly |MaxValue|. And as
+ // |MinValue = -MaxValue - 1|, we have |MaxValue + (-MaxValue - 1)| to
+ // equal -1.
+ //
+ // Thus the delta below is in signed range, the corresponding cast is safe,
+ // and this computation produces values spanning [MinValue, 0): exactly the
+ // desired range of all negative signed integers.
+ return (aValue <= MaxValueUnsigned)
+ ? static_cast<SignedType>(aValue)
+ : static_cast<SignedType>(aValue - MinValueUnsigned) + MinValue;
+ }
+};
+
+} // namespace detail
+
+/**
+ * Convert an unsigned value to signed, if necessary wrapping around.
+ *
+ * This is the behavior normal C++ casting will perform in most implementations
+ * these days -- but this function makes explicit that such conversion is
+ * happening.
+ */
+template<typename UnsignedType>
+inline constexpr typename detail::WrapToSignedHelper<UnsignedType>::SignedType
+WrapToSigned(UnsignedType aValue)
+{
+ return detail::WrapToSignedHelper<UnsignedType>::compute(aValue);
+}
+
+namespace detail {
+
+template<typename T>
+struct WrappingMultiplyHelper
+{
+private:
+ using UnsignedT = typename MakeUnsigned<T>::Type;
+
+ MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
+ static UnsignedT
+ multiply(UnsignedT aX, UnsignedT aY)
+ {
+ // |mozilla::WrappingMultiply| isn't constexpr because MSVC warns about well-
+ // defined unsigned integer overflows that may happen here.
+ // https://msdn.microsoft.com/en-us/library/4kze989h.aspx And constexpr
+ // seems to cause the warning to be emitted at |WrappingMultiply| call *sites*
+ // instead of here, so these #pragmas are ineffective.
+ //
+ // https://stackoverflow.com/questions/37658794/integer-constant-overflow-warning-in-constexpr
+ //
+ // If/when MSVC fix this bug, we should make these functions constexpr.
+
+ // Begin with |1U| to ensure the overall operation chain is never promoted
+ // to signed integer operations that might have *signed* integer overflow.
+ return static_cast<UnsignedT>(1U * aX * aY);
+ }
+
+ static T
+ toResult(UnsignedT aX, UnsignedT aY)
+ {
+ // We could always return WrapToSigned and rely on unsigned conversion
+ // undoing the wrapping when |T| is unsigned, but this seems clearer.
+ return IsSigned<T>::value
+ ? WrapToSigned(multiply(aX, aY))
+ : multiply(aX, aY);
+ }
+
+public:
+ MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
+ static T compute(T aX, T aY)
+ {
+ return toResult(static_cast<UnsignedT>(aX), static_cast<UnsignedT>(aY));
+ }
+};
+
+} // namespace detail
+
+/**
+ * Multiply two integers of the same type, and return the result converted to
+ * that type using wraparound semantics. This function:
+ *
+ * 1) makes explicit the desire for and dependence upon wraparound semantics,
+ * 2) provides wraparound semantics *safely* with no signed integer overflow
+ * that would have undefined behavior, and
+ * 3) won't trip up {,un}signed-integer overflow sanitizers (see
+ * build/autoconf/sanitize.m4) at runtime.
+ *
+ * For N-bit unsigned integer types, this is equivalent to multiplying the two
+ * numbers, then taking the result mod 2**N:
+ *
+ * WrappingMultiply(uint32_t(42), uint32_t(17)) is 714 (714 mod 2**32);
+ * WrappingMultiply(uint8_t(16), uint8_t(24)) is 128 (384 mod 2**8);
+ * WrappingMultiply(uint16_t(3), uint16_t(32768)) is 32768 (98304 mod 2*16).
+ *
+ * Use this function for any unsigned multiplication that can wrap (instead of
+ * normal C++ multiplication) to play nice with the sanitizers. But it's
+ * especially important to use it for uint16_t multiplication: in most compilers
+ * for uint16_t*uint16_t some operand values will trigger signed integer
+ * overflow with undefined behavior! http://kqueue.org/blog/2013/09/17/cltq/
+ * has the grody details. Other than that one weird case, WrappingMultiply on
+ * unsigned types is the same as C++ multiplication.
+ *
+ * For N-bit signed integer types, this is equivalent to multiplying the two
+ * numbers wrapped to unsigned, taking the product mod 2**N, then wrapping that
+ * number to the signed range:
+ *
+ * WrappingMultiply(int16_t(-456), int16_t(123)) is 9448 ((-56088 mod 2**16) + 2**16);
+ * WrappingMultiply(int32_t(-7), int32_t(-9)) is 63 (63 mod 2**32);
+ * WrappingMultiply(int8_t(16), int8_t(24)) is -128 ((384 mod 2**8) - 2**8);
+ * WrappingMultiply(int8_t(16), int8_t(255)) is -16 ((4080 mod 2**8) - 2**8).
+ *
+ * There is no ready equivalent to this operation in C++, as applying C++
+ * multiplication to signed integer types in ways that trigger overflow has
+ * undefined behavior. However, it's how multiplication *tends* to behave with
+ * most compilers in most situations, even though it's emphatically not required
+ * to do so.
+ */
+template<typename T>
+inline T
+WrappingMultiply(T aX, T aY)
+{
+ return detail::WrappingMultiplyHelper<T>::compute(aX, aY);
+}
+
+} /* namespace mozilla */
+
+#endif /* mozilla_WrappingOperations_h */
diff --git a/mfbt/moz.build b/mfbt/moz.build
index 20c7234dd3..54b13f21b9 100644
--- a/mfbt/moz.build
+++ b/mfbt/moz.build
@@ -101,6 +101,7 @@ EXPORTS.mozilla = [
'Variant.h',
'Vector.h',
'WeakPtr.h',
+ 'WrappingOperations.h',
'XorShift128PlusRNG.h',
]
generated by cgit v1.2.3 (git 2.26.2) at 2024-11-10 06:41:40 +0000