This is an automated email from the ASF dual-hosted git repository.
wangdan pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/incubator-pegasus.git
The following commit(s) were added to refs/heads/master by this push:
new a987da91b fix: fix undefined behavior due to overflow or underflow
when handling `incr` requests (#2269)
a987da91b is described below
commit a987da91b694e3949bac89494dacdaa33eeb6ea4
Author: Dan Wang <[email protected]>
AuthorDate: Tue Jul 15 12:47:31 2025 +0800
fix: fix undefined behavior due to overflow or underflow when handling
`incr` requests (#2269)
Fix https://github.com/apache/incubator-pegasus/issues/2270.
Performing direct addition on two integer variables of the same type can
lead to
undefined behavior due to overflow or underflow. Thus introduces a
`safe_add()`
function template that supports safe addition for both signed and unsigned
integers:
it checks for potential overflow or underflow before performing the
addition. If an
overflow or underflow would occur, it returns `false`; otherwise, it
performs the addition
and returns `true`.
Both the non-idempotent and idempotent implementations of `incr` are
updated to use
`safe_add()` to safely compute the result of adding the base value and the
increment.
---
src/server/pegasus_write_service_impl.h | 10 +-
.../test/pegasus_write_service_impl_test.cpp | 38 +++-
src/utils/safe_arithmetic.h | 76 ++++++++
src/utils/test/safe_arithmetic_test.cpp | 192 +++++++++++++++++++++
4 files changed, 302 insertions(+), 14 deletions(-)
diff --git a/src/server/pegasus_write_service_impl.h
b/src/server/pegasus_write_service_impl.h
index 8bdf0d976..a0ff7d63f 100644
--- a/src/server/pegasus_write_service_impl.h
+++ b/src/server/pegasus_write_service_impl.h
@@ -31,6 +31,7 @@
#include "utils/defer.h"
#include "utils/env.h"
#include "utils/filesystem.h"
+#include "utils/safe_arithmetic.h"
#include "utils/string_conv.h"
#include "utils/strings.h"
@@ -213,9 +214,7 @@ public:
return make_error_response(rocksdb::Status::kInvalidArgument,
err_resp);
}
- new_int = base_int + req.increment;
- if (dsn_unlikely((req.increment > 0 && new_int < base_int) ||
- (req.increment < 0 && new_int > base_int))) {
+ if (dsn_unlikely(!dsn::safe_add(base_int, req.increment,
new_int))) {
// New value overflows, just respond with the base value.
LOG_ERROR_PREFIX("incr failed: error = new value is out of
range, "
"base_value = {}, increment = {}, new_value =
{}",
@@ -305,9 +304,8 @@ public:
// we should write empty record to update rocksdb's last
flushed decree
return empty_put(decree);
}
- new_value = old_value_int + update.increment;
- if ((update.increment > 0 && new_value < old_value_int) ||
- (update.increment < 0 && new_value > old_value_int)) {
+
+ if (dsn_unlikely(!dsn::safe_add(old_value_int,
update.increment, new_value))) {
// new value is out of range, return old value by
'new_value'
LOG_ERROR_PREFIX("incr failed: decree = {}, error = "
"new value is out of range, old_value =
{}, increment = {}",
diff --git a/src/server/test/pegasus_write_service_impl_test.cpp
b/src/server/test/pegasus_write_service_impl_test.cpp
index 70ba2199d..29580e7a5 100644
--- a/src/server/test/pegasus_write_service_impl_test.cpp
+++ b/src/server/test/pegasus_write_service_impl_test.cpp
@@ -45,11 +45,13 @@
// IWYU pragma: no_forward_declare
pegasus::server::IdempotentIncrTest_FailOnGet_Test
// IWYU pragma: no_forward_declare
pegasus::server::IdempotentIncrTest_FailOnPut_Test
// IWYU pragma: no_forward_declare
pegasus::server::IdempotentIncrTest_IncrOnNonNumericRecord_Test
-// IWYU pragma: no_forward_declare
pegasus::server::IdempotentIncrTest_IncrOverflowed_Test
+// IWYU pragma: no_forward_declare
pegasus::server::IdempotentIncrTest_IncrOverflow_Test
+// IWYU pragma: no_forward_declare
pegasus::server::IdempotentIncrTest_IncrUnderflow_Test
// IWYU pragma: no_forward_declare
pegasus::server::NonIdempotentIncrTest_FailOnGet_Test
// IWYU pragma: no_forward_declare
pegasus::server::NonIdempotentIncrTest_FailOnPut_Test
// IWYU pragma: no_forward_declare
pegasus::server::NonIdempotentIncrTest_IncrOnNonNumericRecord_Test
-// IWYU pragma: no_forward_declare
pegasus::server::NonIdempotentIncrTest_IncrOverflowed_Test
+// IWYU pragma: no_forward_declare
pegasus::server::NonIdempotentIncrTest_IncrOverflow_Test
+// IWYU pragma: no_forward_declare
pegasus::server::NonIdempotentIncrTest_IncrUnderflow_Test
namespace pegasus::server {
@@ -133,6 +135,8 @@ public:
INIT_BASE_VALUE_AND_CHECKER(int64_t, val);
\
single_set(req.key, dsn::blob::create_from_numeric(kBaseValue))
+#define CHECK_BASE_VALUE_AS_EXPECTED(actual_value) ASSERT_EQ(kBaseValue,
actual_value)
+
class IncrTest : public PegasusWriteServiceImplTest
{
protected:
@@ -255,14 +259,24 @@ TEST_P(NonIdempotentIncrTest, IncrOnNonNumericRecord)
test_non_idempotent_incr(1, rocksdb::Status::kOk,
rocksdb::Status::kInvalidArgument);
}
-TEST_P(NonIdempotentIncrTest, IncrOverflowed)
+TEST_P(NonIdempotentIncrTest, IncrOverflow)
{
- PUT_BASE_VALUE_INT64(100);
+ PUT_BASE_VALUE_INT64(1);
test_non_idempotent_incr(std::numeric_limits<int64_t>::max(),
rocksdb::Status::kOk,
rocksdb::Status::kInvalidArgument);
- ASSERT_EQ(kBaseValue, resp.new_value);
+ CHECK_BASE_VALUE_AS_EXPECTED(resp.new_value);
+}
+
+TEST_P(NonIdempotentIncrTest, IncrUnderflow)
+{
+ PUT_BASE_VALUE_INT64(-1);
+
+ test_non_idempotent_incr(std::numeric_limits<int64_t>::min(),
+ rocksdb::Status::kOk,
+ rocksdb::Status::kInvalidArgument);
+ CHECK_BASE_VALUE_AS_EXPECTED(resp.new_value);
}
TEST_P(NonIdempotentIncrTest, FailOnGet)
@@ -375,12 +389,20 @@ TEST_P(IdempotentIncrTest, IncrOnNonNumericRecord)
test_make_idempotent(1, rocksdb::Status::kInvalidArgument);
}
-TEST_P(IdempotentIncrTest, IncrOverflowed)
+TEST_P(IdempotentIncrTest, IncrOverflow)
{
- PUT_BASE_VALUE_INT64(100);
+ PUT_BASE_VALUE_INT64(1);
test_make_idempotent(std::numeric_limits<int64_t>::max(),
rocksdb::Status::kInvalidArgument);
- ASSERT_EQ(kBaseValue, err_resp.new_value);
+ CHECK_BASE_VALUE_AS_EXPECTED(err_resp.new_value);
+}
+
+TEST_P(IdempotentIncrTest, IncrUnderflow)
+{
+ PUT_BASE_VALUE_INT64(-1);
+
+ test_make_idempotent(std::numeric_limits<int64_t>::min(),
rocksdb::Status::kInvalidArgument);
+ CHECK_BASE_VALUE_AS_EXPECTED(err_resp.new_value);
}
TEST_P(IdempotentIncrTest, FailOnGet)
diff --git a/src/utils/safe_arithmetic.h b/src/utils/safe_arithmetic.h
new file mode 100644
index 000000000..c9784ee23
--- /dev/null
+++ b/src/utils/safe_arithmetic.h
@@ -0,0 +1,76 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#pragma once
+
+#include <limits>
+#include <type_traits>
+
+namespace dsn {
+
+// This function performs safe addition of two signed integers `a` and `b`: if
it returns true,
+// then `a + b` is safe and `result` holds the sum; otherwise, an overflow or
underflow has
+// occurred.
+//
+// Directly adding two integers may lead to undefined behavior if an overflow
occurs. Therefore,
+// in our implementation, we avoid performing the addition directly when
checking for potential
+// overflow. Also see the following links for more details:
+// * https://github.com/apache/incubator-pegasus/issues/2270
+// * https://en.cppreference.com/w/cpp/language/ub.html
+//
+// To ensure that `a + b` does not cause overflow or underflow, the result
must satisfy
+// `min <= a + b <= max`, which implies `min - b <= a <= max - b`:
+// - When `b = 0`, overflow or underflow cannot occur.
+// - When `b > 0`, `a` is necessarily greater than `min - b`, so we only need
to ensure that
+// `a <= max - b`.
+// - When `b < 0`, `a` is necessarily less than `max - b`, so we only need to
ensure that
+// `a >= min - b`.
+template <typename TInt>
+typename std::enable_if_t<std::conjunction_v<std::is_integral<TInt>,
std::is_signed<TInt>>, bool>
+safe_add(TInt a, TInt b, TInt &result)
+{
+ if ((b > 0) && (a > std::numeric_limits<TInt>::max() - b)) {
+ return false;
+ }
+
+ if ((b < 0) && (a < std::numeric_limits<TInt>::min() - b)) {
+ return false;
+ }
+
+ result = a + b;
+ return true;
+}
+
+// This function performs safe addition of two unsigned integers `a` and `b`:
if it returns true,
+// then `a + b` is safe and `result` holds the sum; otherwise, an overflow has
occurred.
+//
+// Similar to the signed version of safe_add(), the unsigned safe_add() also
does not directly
+// add the two integers to check for overflow. Since the unsigned integer `b`
is always greater
+// than or equal to 0, we only need to ensure that `a <= max - b`.
+template <typename TInt>
+typename std::enable_if_t<std::conjunction_v<std::is_integral<TInt>,
std::is_unsigned<TInt>>, bool>
+safe_add(TInt a, TInt b, TInt &result)
+{
+ if (a > std::numeric_limits<TInt>::max() - b) {
+ return false;
+ }
+
+ result = a + b;
+ return true;
+}
+
+} // namespace dsn
diff --git a/src/utils/test/safe_arithmetic_test.cpp
b/src/utils/test/safe_arithmetic_test.cpp
new file mode 100644
index 000000000..149abd94c
--- /dev/null
+++ b/src/utils/test/safe_arithmetic_test.cpp
@@ -0,0 +1,192 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include <cstdint>
+#include <limits>
+#include <type_traits>
+#include <vector>
+
+#include "gtest/gtest.h"
+#include "utils/safe_arithmetic.h"
+
+namespace dsn {
+
+template <typename TInt, std::enable_if_t<std::is_integral_v<TInt>, int> = 0>
+struct safe_int_add_case
+{
+ TInt a;
+ TInt b;
+ TInt expected_result;
+ bool expected_safe;
+};
+
+template <typename TInt, std::enable_if_t<std::is_integral_v<TInt>, int> = 0>
+class SafeIntAddTest : public testing::TestWithParam<safe_int_add_case<TInt>>
+{
+protected:
+ void test_safe_add(const safe_int_add_case<TInt> &test_case) const
+ {
+ TInt actual_result{0};
+ ASSERT_EQ(test_case.expected_safe, safe_add(test_case.a, test_case.b,
actual_result));
+
+ if (!test_case.expected_safe) {
+ return;
+ }
+
+ EXPECT_EQ(test_case.expected_result, actual_result);
+ }
+};
+
+class SafeSignedInt64AddTest : public SafeIntAddTest<int64_t>
+{
+};
+
+TEST_P(SafeSignedInt64AddTest, SafeAdd) { test_safe_add(GetParam()); }
+
+const std::vector<safe_int_add_case<int64_t>> safe_signed_int64_add_tests = {
+ // Common cases: both a and b are non-zero.
+ {271828, 314159, 585987, true},
+ {-271828, 314159, 42331, true},
+ {271828, -314159, -42331, true},
+ {-271828, -314159, -585987, true},
+
+ // Common cases: either a or b is zero.
+ {271828, 0, 271828, true},
+ {0, 271828, 271828, true},
+ {-314159, 0, -314159, true},
+ {0, -314159, -314159, true},
+
+ // Common case: both a and b are zero.
+ {0, 0, 0, true},
+
+ // Common cases: the result is zero.
+ {271828, -271828, 0, true},
+ {-271828, 271828, 0, true},
+
+ // Eage cases: both a and b are non-zero and the result is max.
+ {std::numeric_limits<int64_t>::max() / 2,
+ (std::numeric_limits<int64_t>::max() - 1) / 2 + 1,
+ std::numeric_limits<int64_t>::max(),
+ true},
+ {(std::numeric_limits<int64_t>::max() - 1) / 2 + 1,
+ std::numeric_limits<int64_t>::max() / 2,
+ std::numeric_limits<int64_t>::max(),
+ true},
+
+ // Eage cases: both a and b are non-zero and the result is min.
+ {std::numeric_limits<int64_t>::min() / 2,
+ (std::numeric_limits<int64_t>::min() + 1) / 2 - 1,
+ std::numeric_limits<int64_t>::min(),
+ true},
+ {(std::numeric_limits<int64_t>::min() + 1) / 2 - 1,
+ std::numeric_limits<int64_t>::min() / 2,
+ std::numeric_limits<int64_t>::min(),
+ true},
+
+ // Eage cases: either a or b is zero and the result is max.
+ {0, std::numeric_limits<int64_t>::max(),
std::numeric_limits<int64_t>::max(), true},
+ {std::numeric_limits<int64_t>::max(), 0,
std::numeric_limits<int64_t>::max(), true},
+
+ // Eage cases: either a or b is zero and the result is min.
+ {0, std::numeric_limits<int64_t>::min(),
std::numeric_limits<int64_t>::min(), true},
+ {std::numeric_limits<int64_t>::min(), 0,
std::numeric_limits<int64_t>::min(), true},
+
+ // Eage cases: the result overflows.
+ {1, std::numeric_limits<int64_t>::max(), 0, false},
+ {std::numeric_limits<int64_t>::max(), 1, 0, false},
+ {10, std::numeric_limits<int64_t>::max(), 0, false},
+ {std::numeric_limits<int64_t>::max(), 10, 0, false},
+ {std::numeric_limits<int64_t>::max() / 2 + 1,
+ (std::numeric_limits<int64_t>::max() - 1) / 2 + 1,
+ 0,
+ false},
+ {(std::numeric_limits<int64_t>::max() - 1) / 2 + 1,
+ std::numeric_limits<int64_t>::max() / 2 + 1,
+ 0,
+ false},
+
+ // Eage cases: the result underflows.
+ {-1, std::numeric_limits<int64_t>::min(), 0, false},
+ {std::numeric_limits<int64_t>::min(), -1, 0, false},
+ {-10, std::numeric_limits<int64_t>::min(), 0, false},
+ {std::numeric_limits<int64_t>::min(), -10, 0, false},
+ {std::numeric_limits<int64_t>::min() / 2 - 1,
+ (std::numeric_limits<int64_t>::min() + 1) / 2 - 1,
+ 0,
+ false},
+ {(std::numeric_limits<int64_t>::min() + 1) / 2 - 1,
+ std::numeric_limits<int64_t>::min() / 2 - 1,
+ 0,
+ false},
+};
+
+INSTANTIATE_TEST_SUITE_P(SafeArithmeticTest,
+ SafeSignedInt64AddTest,
+ testing::ValuesIn(safe_signed_int64_add_tests));
+
+class SafeUnsignedInt64AddTest : public SafeIntAddTest<uint64_t>
+{
+};
+
+TEST_P(SafeUnsignedInt64AddTest, SafeAdd) { test_safe_add(GetParam()); }
+
+const std::vector<safe_int_add_case<uint64_t>> safe_unsigned_int64_add_tests =
{
+ // Common cases: both a and b are non-zero.
+ {271828, 314159, 585987, true},
+ {314159, 271828, 585987, true},
+
+ // Common cases: either a or b is zero.
+ {271828, 0, 271828, true},
+ {0, 314159, 314159, true},
+
+ // Common case: both a and b are zero.
+ {0, 0, 0, true},
+
+ // Eage cases: both a and b are non-zero and the result is max.
+ {std::numeric_limits<uint64_t>::max() / 2,
+ (std::numeric_limits<uint64_t>::max() - 1) / 2 + 1,
+ std::numeric_limits<uint64_t>::max(),
+ true},
+ {(std::numeric_limits<uint64_t>::max() - 1) / 2 + 1,
+ std::numeric_limits<uint64_t>::max() / 2,
+ std::numeric_limits<uint64_t>::max(),
+ true},
+
+ // Eage cases: either a or b is zero and the result is max.
+ {0, std::numeric_limits<uint64_t>::max(),
std::numeric_limits<uint64_t>::max(), true},
+ {std::numeric_limits<uint64_t>::max(), 0,
std::numeric_limits<uint64_t>::max(), true},
+
+ // Eage cases: the result overflows.
+ {1, std::numeric_limits<uint64_t>::max(), 0, false},
+ {std::numeric_limits<uint64_t>::max(), 1, 0, false},
+ {10, std::numeric_limits<uint64_t>::max(), 0, false},
+ {std::numeric_limits<uint64_t>::max(), 10, 0, false},
+ {std::numeric_limits<uint64_t>::max() / 2 + 1,
+ (std::numeric_limits<uint64_t>::max() - 1) / 2 + 1,
+ 0,
+ false},
+ {(std::numeric_limits<uint64_t>::max() - 1) / 2 + 1,
+ std::numeric_limits<uint64_t>::max() / 2 + 1,
+ 0,
+ false},
+};
+
+INSTANTIATE_TEST_SUITE_P(SafeArithmeticTest,
+ SafeUnsignedInt64AddTest,
+ testing::ValuesIn(safe_unsigned_int64_add_tests));
+
+} // namespace dsn
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
