From 7a81d51b0905dee4c24a17069d84d431041e980b Mon Sep 17 00:00:00 2001
From: Bernard Gorman <bernard.gorman@mongodb.com>
Date: Mon, 7 Oct 2019 20:54:34 +0000
Subject: SERVER-43699 $mod should not overflow for large negative values

(cherry picked from commit 21d8699ed6c517b45e1613e20231cd8eba894985)
---
 src/mongo/db/matcher/expression_leaf.cpp        |  4 ++--
 src/mongo/db/pipeline/expression.cpp            |  8 +++++---
 src/mongo/platform/overflow_arithmetic.h        | 15 +++++++++++++++
 src/mongo/platform/overflow_arithmetic_test.cpp | 12 ++++++++++++
 4 files changed, 34 insertions(+), 5 deletions(-)

(limited to 'src')

diff --git a/src/mongo/db/matcher/expression_leaf.cpp b/src/mongo/db/matcher/expression_leaf.cpp
index 0b84c310b0d..1ec48ed1f8e 100644
--- a/src/mongo/db/matcher/expression_leaf.cpp
+++ b/src/mongo/db/matcher/expression_leaf.cpp
@@ -300,7 +300,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 level) const {
@@ -797,4 +797,4 @@ bool BitTestMatchExpression::equivalent(const MatchExpression* other) const {
 
     return path() == realOther->path() && myBitPositions == otherBitPositions;
 }
-}
+}  // namespace mongo
diff --git a/src/mongo/db/pipeline/expression.cpp b/src/mongo/db/pipeline/expression.cpp
index e1ef5d763fc..8dac3067d0e 100644
--- a/src/mongo/db/pipeline/expression.cpp
+++ b/src/mongo/db/pipeline/expression.cpp
@@ -2625,17 +2625,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 a8a88ce048d..a0deb0deb48 100644
--- a/src/mongo/platform/overflow_arithmetic.h
+++ b/src/mongo/platform/overflow_arithmetic.h
@@ -36,6 +36,8 @@
 #include <safeint.h>
 #endif
 
+#include "mongo/util/assert_util.h"
+
 namespace mongo {
 
 /**
@@ -178,4 +180,17 @@ inline 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 24f91a5bf57..4222daeb84b 100644
--- a/src/mongo/platform/overflow_arithmetic_test.cpp
+++ b/src/mongo/platform/overflow_arithmetic_test.cpp
@@ -181,5 +181,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
-- 
cgit v1.2.1