diff options
Diffstat (limited to 'mfbt')
| -rw-r--r-- | mfbt/Attributes.h | 124 | ||||
| -rw-r--r-- | mfbt/FloatingPoint.h | 108 | ||||
| -rw-r--r-- | mfbt/HashFunctions.h | 8 | ||||
| -rw-r--r-- | mfbt/WrappingOperations.h | 188 | ||||
| -rw-r--r-- | mfbt/moz.build | 1 |
5 files changed, 393 insertions, 36 deletions
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/FloatingPoint.h b/mfbt/FloatingPoint.h index 7d73d7e848..a2846ce298 100644 --- a/mfbt/FloatingPoint.h +++ b/mfbt/FloatingPoint.h @@ -33,33 +33,38 @@ namespace mozilla { * compiler bustage, particularly PGO-specific bustage. */ -struct FloatTypeTraits +namespace detail { + +/* + * These implementations assume float/double are 32/64-bit single/double + * format number types compatible with the IEEE-754 standard. C++ doesn't + * require this, but we required it in implementations of these algorithms that + * preceded this header, so we shouldn't break anything to continue doing so. + */ +template<typename T> +struct FloatingPointTrait; + +template<> +struct FloatingPointTrait<float> { +protected: typedef uint32_t Bits; - static const unsigned kExponentBias = 127; - static const unsigned kExponentShift = 23; - - static const Bits kSignBit = 0x80000000UL; - static const Bits kExponentBits = 0x7F800000UL; - static const Bits kSignificandBits = 0x007FFFFFUL; + static constexpr unsigned kExponentWidth = 8; + static constexpr unsigned kSignificandWidth = 23; }; -struct DoubleTypeTraits +template<> +struct FloatingPointTrait<double> { +protected: typedef uint64_t Bits; - static const unsigned kExponentBias = 1023; - static const unsigned kExponentShift = 52; - - static const Bits kSignBit = 0x8000000000000000ULL; - static const Bits kExponentBits = 0x7ff0000000000000ULL; - static const Bits kSignificandBits = 0x000fffffffffffffULL; + static constexpr unsigned kExponentWidth = 11; + static constexpr unsigned kSignificandWidth = 52; }; -template<typename T> struct SelectTrait; -template<> struct SelectTrait<float> : public FloatTypeTraits {}; -template<> struct SelectTrait<double> : public DoubleTypeTraits {}; +} // namespace detail /* * This struct contains details regarding the encoding of floating-point @@ -88,30 +93,65 @@ template<> struct SelectTrait<double> : public DoubleTypeTraits {}; * http://en.wikipedia.org/wiki/Floating_point#IEEE_754:_floating_point_in_modern_computers */ template<typename T> -struct FloatingPoint : public SelectTrait<T> +struct FloatingPoint final : private detail::FloatingPointTrait<T> { - typedef SelectTrait<T> Base; - typedef typename Base::Bits Bits; +private: + using Base = detail::FloatingPointTrait<T>; + +public: + /** + * An unsigned integral type suitable for accessing the bitwise representation + * of T. + */ + using Bits = typename Base::Bits; + + static_assert(sizeof(T) == sizeof(Bits), "Bits must be same size as T"); - static_assert((Base::kSignBit & Base::kExponentBits) == 0, + /** The bit-width of the exponent component of T. */ + using Base::kExponentWidth; + + /** The bit-width of the significand component of T. */ + using Base::kSignificandWidth; + + static_assert(1 + kExponentWidth + kSignificandWidth == + CHAR_BIT * sizeof(T), + "sign bit plus bit widths should sum to overall bit width"); + + /** + * The exponent field in an IEEE-754 floating point number consists of bits + * encoding an unsigned number. The *actual* represented exponent (for all + * values finite and not denormal) is that value, minus a bias |kExponentBias| + * so that a useful range of numbers is represented. + */ + static constexpr unsigned kExponentBias = (1U << (kExponentWidth - 1)) - 1; + + /** + * The amount by which the bits of the exponent-field in an IEEE-754 floating + * point number are shifted from the LSB of the floating point type. + */ + static constexpr unsigned kExponentShift = kSignificandWidth; + + /** The sign bit in the floating point representation. */ + static constexpr Bits kSignBit = + static_cast<Bits>(1) << (CHAR_BIT * sizeof(Bits) - 1); + + /** The exponent bits in the floating point representation. */ + static constexpr Bits kExponentBits = + ((static_cast<Bits>(1) << kExponentWidth) - 1) << kSignificandWidth; + + /** The significand bits in the floating point representation. */ + static constexpr Bits kSignificandBits = + (static_cast<Bits>(1) << kSignificandWidth) - 1; + + static_assert((kSignBit & kExponentBits) == 0, "sign bit shouldn't overlap exponent bits"); - static_assert((Base::kSignBit & Base::kSignificandBits) == 0, + static_assert((kSignBit & kSignificandBits) == 0, "sign bit shouldn't overlap significand bits"); - static_assert((Base::kExponentBits & Base::kSignificandBits) == 0, + static_assert((kExponentBits & kSignificandBits) == 0, "exponent bits shouldn't overlap significand bits"); - static_assert((Base::kSignBit | Base::kExponentBits | Base::kSignificandBits) == - ~Bits(0), + static_assert((kSignBit | kExponentBits | kSignificandBits) == ~Bits(0), "all bits accounted for"); - - /* - * These implementations assume float/double are 32/64-bit single/double - * format number types compatible with the IEEE-754 standard. C++ don't - * require this to be the case. But we required this in implementations of - * these algorithms that preceded this header, so we shouldn't break anything - * if we keep doing so. - */ - static_assert(sizeof(T) == sizeof(Bits), "Bits must be same size as T"); }; /** Determines whether a float/double is NaN. */ 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', ] |