diff options
author | Bernard Gorman <bernard.gorman@mongodb.com> | 2019-10-07 02:03:48 +0000 |
---|---|---|
committer | evergreen <evergreen@mongodb.com> | 2019-10-07 02:03:48 +0000 |
commit | e865364752da4262e605b92bf8c13e134e7539d3 (patch) | |
tree | 4c03edd1ffe7806526d8b0183ae07c553f7c974d | |
parent | b1e94ad7bc13524358199fc1909c356085cf7bcf (diff) | |
download | mongo-e865364752da4262e605b92bf8c13e134e7539d3.tar.gz |
SERVER-43699 $mod should not overflow for large negative values
(cherry picked from commit 21d8699ed6c517b45e1613e20231cd8eba894985)
-rw-r--r-- | jstests/core/mod_overflow.js | 45 | ||||
-rw-r--r-- | src/mongo/db/matcher/expression_leaf.cpp | 2 | ||||
-rw-r--r-- | src/mongo/db/pipeline/expression.cpp | 8 | ||||
-rw-r--r-- | src/mongo/platform/overflow_arithmetic.h | 15 | ||||
-rw-r--r-- | src/mongo/platform/overflow_arithmetic_test.cpp | 12 |
5 files changed, 78 insertions, 4 deletions
diff --git a/jstests/core/mod_overflow.js b/jstests/core/mod_overflow.js new file mode 100644 index 00000000000..2ec33300ce7 --- /dev/null +++ b/jstests/core/mod_overflow.js @@ -0,0 +1,45 @@ +/** + * Tests that modding the smallest representable integer values by -1 does not result in integer + * overflow. Exercises the fix for SERVER-43699. + */ +(function() { +"use strict"; + +const testDB = db.getSiblingDB(jsTestName()); +const testColl = testDB.test; +testColl.drop(); + +// Insert two documents, one with a value of -2^63 and the other with a value of -2^31. +const insertedDocs = + [{_id: 0, val: NumberLong("-9223372036854775808")}, {_id: 1, val: NumberInt("-2147483648")}]; +assert.commandWorked(testColl.insert(insertedDocs)); + +// For each possible integral representation of -1, confirm that overflow does not occur. +for (let divisor of [-1.0, NumberInt("-1"), NumberLong("-1"), NumberDecimal("-1")]) { + assert.docEq(testColl.find({val: {$mod: [divisor, 0]}}).sort({_id: 1}).toArray(), insertedDocs); + assert.docEq( + testColl + .aggregate( + [{$match: {$expr: {$eq: [0, {$mod: ["$val", divisor]}]}}}, {$sort: {_id: 1}}]) + .toArray(), + insertedDocs); + + // Confirm that overflow does not occur during agg expression evaluation. Also confirm that the + // correct type is returned for each combination of input types. + const expectedResults = [ + Object.merge( + insertedDocs[0], + {modVal: (divisor instanceof NumberDecimal ? NumberDecimal("-0") : NumberLong("0"))}), + Object.merge(insertedDocs[1], { + modVal: (divisor instanceof NumberLong + ? NumberLong("0") + : divisor instanceof NumberDecimal ? NumberDecimal("-0") : 0) + }) + ]; + assert.docEq( + testColl + .aggregate([{$project: {val: 1, modVal: {$mod: ["$val", divisor]}}}, {$sort: {_id: 1}}]) + .toArray(), + expectedResults); +} +})();
\ No newline at end of file diff --git a/src/mongo/db/matcher/expression_leaf.cpp b/src/mongo/db/matcher/expression_leaf.cpp index 67b67dad77d..9be27d3cc78 100644 --- a/src/mongo/db/matcher/expression_leaf.cpp +++ b/src/mongo/db/matcher/expression_leaf.cpp @@ -299,7 +299,7 @@ ModMatchExpression::ModMatchExpression(StringData path, int divisor, int remaind bool ModMatchExpression::matchesSingleElement(const BSONElement& e, MatchDetails* details) const { if (!e.isNumber()) return false; - return e.numberLong() % _divisor == _remainder; + return mongoSafeMod(e.numberLong(), static_cast<long long>(_divisor)) == _remainder; } void ModMatchExpression::debugString(StringBuilder& debug, int indentationLevel) const { diff --git a/src/mongo/db/pipeline/expression.cpp b/src/mongo/db/pipeline/expression.cpp index 78b25008863..689dcf21e84 100644 --- a/src/mongo/db/pipeline/expression.cpp +++ b/src/mongo/db/pipeline/expression.cpp @@ -2630,17 +2630,19 @@ Value ExpressionMod::evaluate(const Document& root, Variables* variables) const double left = lhs.coerceToDouble(); return Value(fmod(left, right)); - } else if (leftType == NumberLong || rightType == NumberLong) { + } + + if (leftType == NumberLong || rightType == NumberLong) { // if either is long, return long long long left = lhs.coerceToLong(); long long rightLong = rhs.coerceToLong(); - return Value(left % rightLong); + return Value(mongoSafeMod(left, rightLong)); } // lastly they must both be ints, return int int left = lhs.coerceToInt(); int rightInt = rhs.coerceToInt(); - return Value(left % rightInt); + return Value(mongoSafeMod(left, rightInt)); } else if (lhs.nullish() || rhs.nullish()) { return Value(BSONNULL); } else { diff --git a/src/mongo/platform/overflow_arithmetic.h b/src/mongo/platform/overflow_arithmetic.h index 0306023916a..5b8701e6b26 100644 --- a/src/mongo/platform/overflow_arithmetic.h +++ b/src/mongo/platform/overflow_arithmetic.h @@ -35,6 +35,8 @@ #include <SafeInt.hpp> #endif +#include "mongo/util/assert_util.h" + namespace mongo { /** @@ -154,4 +156,17 @@ constexpr bool mongoUnsignedSubtractOverflow64(unsigned long long lhs, #endif +/** + * Safe mod function which throws if the divisor is 0 and avoids potential overflow in cases where + * the divisor is -1. If the absolute value of the divisor is 1, mod will always return 0. We fast- + * path this to avoid the scenario where the dividend is the smallest negative long or int value and + * the divisor is -1. Naively performing this % may result in an overflow when the -2^N value is + * divided and becomes 2^N. See SERVER-43699. + */ +template <typename T> +constexpr T mongoSafeMod(T dividend, T divisor) { + uassert(51259, "can't mod by zero", divisor != 0); + return (divisor == 1 || divisor == -1 ? 0 : dividend % divisor); +} + } // namespace mongo diff --git a/src/mongo/platform/overflow_arithmetic_test.cpp b/src/mongo/platform/overflow_arithmetic_test.cpp index 19571203e3c..cd2a44a972a 100644 --- a/src/mongo/platform/overflow_arithmetic_test.cpp +++ b/src/mongo/platform/overflow_arithmetic_test.cpp @@ -180,5 +180,17 @@ TEST(OverflowArithmetic, UnsignedSubtractionTests) { assertUnsignedSubtractWithOverflow(0, limits::max()); } +TEST(OverflowArithmetic, SafeModTests) { + // Mod -1 should not overflow for LLONG_MIN or INT_MIN. + auto minLong = std::numeric_limits<long long>::min(); + auto minInt = std::numeric_limits<int>::min(); + ASSERT_EQ(mongoSafeMod(minLong, -1LL), 0); + ASSERT_EQ(mongoSafeMod(minInt, -1), 0); + + // A divisor of 0 throws a user assertion. + ASSERT_THROWS_CODE(mongoSafeMod(minLong, 0LL), AssertionException, 51259); + ASSERT_THROWS_CODE(mongoSafeMod(minInt, 0), AssertionException, 51259); +} + } // namespace } // namespace mongo |