Add ExtendedAccumulator Utility
Often, we need to accumulate a smaller sized counter which wraps
around into a larger type. This utility class does that.
Test: atest extended_accumulator_tests
Change-Id: Ibc0da37c04b537aaec8a1f12f0ad5c0d44a27f5b
diff --git a/media/utils/include/mediautils/ExtendedAccumulator.h b/media/utils/include/mediautils/ExtendedAccumulator.h
new file mode 100644
index 0000000..7e3e170
--- /dev/null
+++ b/media/utils/include/mediautils/ExtendedAccumulator.h
@@ -0,0 +1,90 @@
+/*
+ * Copyright (C) 2022 The Android Open Source Project
+ *
+ * Licensed 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 <atomic>
+#include <cstdint>
+#include <tuple>
+#include <type_traits>
+
+#include <log/log.h>
+
+namespace android::mediautils {
+
+// The goal of this class is to detect and accumulate wraparound occurrences on a
+// lower sized integer.
+
+// This class assumes that the underlying unsigned type is either incremented or
+// decremented by at most the underlying signed type between any two subsequent
+// polls (or construction). This is well-defined as the modular nature of
+// unsigned arithmetic ensures that every new value maps 1-1 to an
+// increment/decrement over the same sized signed type. It also ensures that our
+// counter will be equivalent mod the size of the integer even if the underlying
+// type is modified outside of this range.
+//
+// For convenience, this class is thread compatible. Additionally, it is safe
+// as long as there is only one writer.
+template <typename Integral = uint32_t, typename AccumulatingType = uint64_t>
+class ExtendedAccumulator {
+ static_assert(sizeof(Integral) < sizeof(AccumulatingType),
+ "Accumulating type should be larger than underlying type");
+ static_assert(std::is_integral_v<Integral> && std::is_unsigned_v<Integral>,
+ "Wraparound behavior is only well-defiend for unsigned ints");
+ static_assert(std::is_integral_v<AccumulatingType>);
+
+ public:
+ enum class Wrap {
+ NORMAL = 0,
+ UNDERFLOW = 1,
+ OVERFLOW = 2,
+ };
+
+ using UnsignedInt = Integral;
+ using SignedInt = std::make_signed_t<UnsignedInt>;
+
+ explicit ExtendedAccumulator(AccumulatingType initial = 0) : mAccumulated(initial) {}
+
+ // Returns a pair of the calculated change on the accumulating value, and a
+ // Wrap type representing the type of wraparound (if any) which occurred.
+ std::pair<SignedInt, Wrap> poll(UnsignedInt value) {
+ auto acc = mAccumulated.load(std::memory_order_relaxed);
+ const auto bottom_bits = static_cast<UnsignedInt>(acc);
+ std::pair<SignedInt, Wrap> res = {0, Wrap::NORMAL};
+ const bool overflow = __builtin_sub_overflow(value, bottom_bits, &res.first);
+
+ if (overflow) {
+ res.second = (res.first > 0) ? Wrap::OVERFLOW : Wrap::UNDERFLOW;
+ }
+
+ const bool acc_overflow = __builtin_add_overflow(acc, res.first, &acc);
+ // If our *accumulating* type overflows or underflows (depending on its
+ // signedness), we should abort.
+ if (acc_overflow) LOG_ALWAYS_FATAL("Unexpected overflow/underflow in %s", __func__);
+
+ mAccumulated.store(acc, std::memory_order_relaxed);
+ return res;
+ }
+
+ AccumulatingType getValue() const { return mAccumulated.load(std::memory_order_relaxed); }
+
+ private:
+ // Invariant - the bottom underlying bits of accumulated are the same as the
+ // last value provided to poll.
+ std::atomic<AccumulatingType> mAccumulated;
+};
+
+} // namespace android::mediautils
diff --git a/media/utils/tests/Android.bp b/media/utils/tests/Android.bp
index 1024018..82dd0dc 100644
--- a/media/utils/tests/Android.bp
+++ b/media/utils/tests/Android.bp
@@ -15,11 +15,11 @@
"-Wextra",
],
- sanitize:{
- address: true,
- cfi: true,
- integer_overflow: true,
- memtag_heap: true,
+ sanitize: {
+ address: true,
+ cfi: true,
+ integer_overflow: true,
+ memtag_heap: true,
},
shared_libs: [
@@ -28,7 +28,7 @@
srcs: [
"sharedtest.cpp",
- ]
+ ],
}
cc_test {
@@ -40,11 +40,11 @@
"-Wextra",
],
- sanitize:{
- address: true,
- cfi: true,
- integer_overflow: true,
- memtag_heap: true,
+ sanitize: {
+ address: true,
+ cfi: true,
+ integer_overflow: true,
+ memtag_heap: true,
},
shared_libs: [
@@ -174,11 +174,11 @@
"-Wextra",
],
- sanitize:{
- address: true,
- cfi: true,
- integer_overflow: true,
- memtag_heap: true,
+ sanitize: {
+ address: true,
+ cfi: true,
+ integer_overflow: true,
+ memtag_heap: true,
},
shared_libs: [
@@ -191,3 +191,30 @@
"timecheck_tests.cpp",
],
}
+
+cc_test {
+ name: "extended_accumulator_tests",
+ cflags: [
+ "-Wall",
+ "-Werror",
+ "-Wextra",
+ ],
+
+ sanitize: {
+ address: true,
+ cfi: true,
+ integer_overflow: true,
+ memtag_heap: true,
+ },
+
+ shared_libs: [
+ "libbase",
+ "liblog",
+ "libmediautils",
+ "libutils",
+ ],
+
+ srcs: [
+ "extended_accumulator_tests.cpp",
+ ],
+}
diff --git a/media/utils/tests/extended_accumulator_tests.cpp b/media/utils/tests/extended_accumulator_tests.cpp
new file mode 100644
index 0000000..e243e7e
--- /dev/null
+++ b/media/utils/tests/extended_accumulator_tests.cpp
@@ -0,0 +1,101 @@
+/*
+ * Copyright (C) 2022 The Android Open Source Project
+ *
+ * Licensed 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.
+ */
+
+#define LOG_TAG "extended_accumulator_tests"
+
+#include <mediautils/ExtendedAccumulator.h>
+
+#include <type_traits>
+#include <cstdint>
+#include <limits.h>
+
+#include <gtest/gtest.h>
+#include <log/log.h>
+
+using namespace android;
+using namespace android::mediautils;
+
+// Conditionally choose a base accumulating counter value in order to prevent
+// unsigned underflow on the accumulator from aborting the tests.
+template <typename TType, typename CType>
+static constexpr CType getBase() {
+ static_assert(sizeof(TType) < sizeof(CType));
+ if constexpr (std::is_unsigned_v<CType>) {
+ return std::numeric_limits<TType>::max() + 1;
+ } else {
+ return 0;
+ }
+}
+
+// Since the entire state of this utility is the previous value, and the
+// behavior is isomorphic mod the underlying type on the previous value, we can
+// test combinations of the previous value of the underlying type and a
+// hypothetical signed update to that type and ensure the accumulator moves
+// correctly and reports overflow correctly.
+template <typename TestUInt, typename CType>
+void testPair(TestUInt prevVal, std::make_signed_t<TestUInt> delta) {
+ using TestDetect = ExtendedAccumulator<TestUInt, CType>;
+ using TestInt = typename TestDetect::SignedInt;
+ static_assert(std::is_same_v<typename TestDetect::UnsignedInt, TestUInt>);
+ static_assert(std::is_same_v<TestInt, std::make_signed_t<TestUInt>>);
+ static_assert(sizeof(TestUInt) < sizeof(CType));
+
+ // To safely detect underflow/overflow for testing
+ // Should be 0 mod TestUInt, max + 1 is convenient
+ static constexpr CType base = getBase<TestUInt, CType>();
+ const CType prev = base + prevVal;
+ TestDetect test{prev};
+ EXPECT_EQ(test.getValue(), prev);
+ // Prevent unsigned wraparound abort
+ CType next;
+ const auto err = __builtin_add_overflow(prev, delta, &next);
+ LOG_ALWAYS_FATAL_IF(err, "Unexpected wrap in tests");
+ const auto [result, status] = test.poll(static_cast<TestUInt>(next));
+ EXPECT_EQ(test.getValue(), next);
+ EXPECT_EQ(result, delta);
+
+ // Test overflow/underflow event reporting.
+ if (next < base) EXPECT_EQ(TestDetect::Wrap::UNDERFLOW, status);
+ else if (next > base + std::numeric_limits<TestUInt>::max())
+ EXPECT_EQ(TestDetect::Wrap::OVERFLOW, status);
+ else EXPECT_EQ(TestDetect::Wrap::NORMAL, status);
+}
+
+// Test this utility on every combination of prior and update value for the
+// type uint8_t, with an unsigned containing type.
+TEST(wraparound_tests, cover_u8_u64) {
+ using TType = uint8_t;
+ using CType = uint64_t;
+ static constexpr CType max = std::numeric_limits<TType>::max();
+ for (CType i = 0; i <= max; i++) {
+ for (CType j = 0; j <= max; j++) {
+ testPair<TType, CType>(i, static_cast<int64_t>(j));
+ }
+ }
+}
+
+// Test this utility on every combination of prior and update value for the
+// type uint8_t, with a signed containing type.
+TEST(wraparound_tests, cover_u8_s64) {
+ using TType = uint8_t;
+ using CType = int64_t;
+ static constexpr CType max = std::numeric_limits<TType>::max();
+ for (CType i = 0; i <= max; i++) {
+ for (CType j = 0; j <= max; j++) {
+ testPair<TType, CType>(i, static_cast<int64_t>(j));
+ }
+ }
+}