SERVER-43699 $mod should not overflow for large negative values

(cherry picked from commit 21d8699ed6c517b45e1613e20231cd8eba894985)

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