Introduced LogEventFilter to be used for socket optimization

- added LogEventFilter strategy & benchmarks implementation

Bug: 266520742
Test: statsd_test
Test: CtsStatsdHostTestCases
Ignore-AOSP-First: Android U feature
Change-Id: I55a546b3912f0ca6117113435833c8b384e0bd98

4 files changed, 462 insertions, 0 deletions

diff --git a/statsd/Android.bp b/statsd/Android.bp
index cf871708..c2167609 100644
--- a/statsd/Android.bp
+++ b/statsd/Android.bp
@@ -377,6 +377,7 @@ cc_test {
         "tests/metrics/parsing_utils/config_update_utils_test.cpp",
         "tests/metrics/parsing_utils/metrics_manager_util_test.cpp",
         "tests/subscriber/SubscriberReporter_test.cpp",
+        "tests/LogEventFilter_test.cpp",
         "tests/MetricsManager_test.cpp",
         "tests/shell/ShellSubscriber_test.cpp",
         "tests/state/StateTracker_test.cpp",
@@ -429,6 +430,7 @@ cc_benchmark {
         "benchmark/get_dimensions_for_condition_benchmark.cpp",
         "benchmark/hello_world_benchmark.cpp",
         "benchmark/log_event_benchmark.cpp",
+        "benchmark/log_event_filter_benchmark.cpp",
         "benchmark/main.cpp",
         "benchmark/metric_util.cpp",
         "benchmark/stats_write_benchmark.cpp",
diff --git a/statsd/benchmark/log_event_filter_benchmark.cpp b/statsd/benchmark/log_event_filter_benchmark.cpp
new file mode 100644
index 00000000..b65e88f5
--- /dev/null
+++ b/statsd/benchmark/log_event_filter_benchmark.cpp
@@ -0,0 +1,140 @@
+/*
+ * Copyright (C) 2023 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.
+ */
+#include <random>
+#include <vector>
+
+#include "benchmark/benchmark.h"
+#include "socket/LogEventFilter.h"
+
+namespace android {
+namespace os {
+namespace statsd {
+
+namespace {
+
+constexpr int kAtomIdsCount = 500;         //  Filter size setup
+constexpr int kAtomIdsSampleCount = 3000;  //  Queries number
+
+std::vector<int> generateSampleAtomIdsList() {
+    std::vector<int> atomIds(kAtomIdsSampleCount);
+
+    std::default_random_engine generator;
+
+    // Get atoms ids which are not in the filter to test behavior when set is searched for an
+    // an absent key
+    // Expected atoms ids are in a range 1..3000, random & evenly distributes
+    std::uniform_int_distribution<int> distribution(1, kAtomIdsSampleCount);
+
+    for (int i = 0; i < kAtomIdsSampleCount; ++i) {
+        atomIds[i] = distribution(generator);
+    }
+
+    return atomIds;
+}
+
+template <typename T>
+T generateAtomIds() {
+    T atomIds;
+
+    std::default_random_engine generator;
+    std::uniform_int_distribution<int> distribution(1, kAtomIdsCount);
+
+    for (int i = 0; i < kAtomIdsCount; ++i) {
+        atomIds.insert(distribution(generator));
+    }
+
+    return atomIds;
+}
+
+// Used to setup filter
+const std::set<int> kAtomIdsSet = generateAtomIds<std::set<int>>();
+const std::unordered_set<int> kAtomIdsUnorderedSet = generateAtomIds<std::unordered_set<int>>();
+
+const std::set<int> kAtomIdsSet2 = generateAtomIds<std::set<int>>();
+const std::unordered_set<int> kAtomIdsUnorderedSet2 = generateAtomIds<std::unordered_set<int>>();
+
+const std::set<int> kAtomIdsSet3 = generateAtomIds<std::set<int>>();
+const std::unordered_set<int> kAtomIdsUnorderedSet3 = generateAtomIds<std::unordered_set<int>>();
+
+const std::set<int> kAtomIdsSet4 = generateAtomIds<std::set<int>>();
+const std::unordered_set<int> kAtomIdsUnorderedSet4 = generateAtomIds<std::unordered_set<int>>();
+
+// Used to perform sample quieries
+const std::vector<int> kSampleIdsList = generateSampleAtomIdsList();
+
+}  // namespace
+
+static void BM_LogEventFilterUnorderedSet(benchmark::State& state) {
+    while (state.KeepRunning()) {
+        LogEventFilter eventFilter;
+        // populate
+        eventFilter.setAtomIds(kAtomIdsUnorderedSet, nullptr);
+        // many fetches
+        for (const auto& atomId : kSampleIdsList) {
+            benchmark::DoNotOptimize(eventFilter.isAtomInUse(atomId));
+        }
+    }
+}
+BENCHMARK(BM_LogEventFilterUnorderedSet);
+
+static void BM_LogEventFilterUnorderedSet2Consumers(benchmark::State& state) {
+    while (state.KeepRunning()) {
+        LogEventFilter eventFilter;
+        // populate
+        eventFilter.setAtomIds(kAtomIdsUnorderedSet, &kAtomIdsUnorderedSet);
+        eventFilter.setAtomIds(kAtomIdsUnorderedSet2, &kAtomIdsUnorderedSet2);
+        eventFilter.setAtomIds(kAtomIdsUnorderedSet3, &kAtomIdsUnorderedSet);
+        eventFilter.setAtomIds(kAtomIdsUnorderedSet4, &kAtomIdsUnorderedSet2);
+        // many fetches
+        for (const auto& atomId : kSampleIdsList) {
+            benchmark::DoNotOptimize(eventFilter.isAtomInUse(atomId));
+        }
+    }
+}
+BENCHMARK(BM_LogEventFilterUnorderedSet2Consumers);
+
+static void BM_LogEventFilterSet(benchmark::State& state) {
+    while (state.KeepRunning()) {
+        LogEventFilterGeneric<std::set<int>> eventFilter;
+        // populate
+        eventFilter.setAtomIds(kAtomIdsSet, nullptr);
+        // many fetches
+        for (const auto& atomId : kSampleIdsList) {
+            benchmark::DoNotOptimize(eventFilter.isAtomInUse(atomId));
+        }
+    }
+}
+BENCHMARK(BM_LogEventFilterSet);
+
+static void BM_LogEventFilterSet2Consumers(benchmark::State& state) {
+    while (state.KeepRunning()) {
+        LogEventFilterGeneric<std::set<int>> eventFilter;
+        // populate
+        eventFilter.setAtomIds(kAtomIdsSet, &kAtomIdsSet);
+        eventFilter.setAtomIds(kAtomIdsSet2, &kAtomIdsSet2);
+        eventFilter.setAtomIds(kAtomIdsSet3, &kAtomIdsSet);
+        eventFilter.setAtomIds(kAtomIdsSet4, &kAtomIdsSet2);
+        // many fetches
+        for (const auto& atomId : kSampleIdsList) {
+            benchmark::DoNotOptimize(eventFilter.isAtomInUse(atomId));
+        }
+    }
+}
+BENCHMARK(BM_LogEventFilterSet2Consumers);
+
+}  //  namespace statsd
+}  //  namespace os
+}  //  namespace android
diff --git a/statsd/src/socket/LogEventFilter.h b/statsd/src/socket/LogEventFilter.h
new file mode 100644
index 00000000..c6f7c935
--- /dev/null
+++ b/statsd/src/socket/LogEventFilter.h
@@ -0,0 +1,129 @@
+/*
+ * Copyright (C) 2023 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 <gtest/gtest_prod.h>
+
+#include <atomic>
+#include <mutex>
+#include <unordered_map>
+#include <unordered_set>
+
+namespace android {
+namespace os {
+namespace statsd {
+
+/**
+ * Templating is for benchmarks only
+ *
+ * Based on benchmarks the more fast container to be used for atom ids filtering
+ * is unordered_set<int>
+ * #BM_LogEventFilterUnorderedSet                       391208 ns     390086 ns         1793
+ * #BM_LogEventFilterUnorderedSet2Consumers            1293527 ns    1289326 ns          543
+ * #BM_LogEventFilterSet                                613362 ns     611259 ns         1146
+ * #BM_LogEventFilterSet2Consumers                     1859397 ns    1854193 ns          378
+ *
+ * See @LogEventFilter definition below
+ */
+template <typename T>
+class LogEventFilterGeneric {
+public:
+    virtual ~LogEventFilterGeneric() = default;
+
+    virtual void setFilteringEnabled(bool isEnabled) {
+        mLogsFilteringEnabled = isEnabled;
+    }
+
+    /**
+     * @brief Tests atom id with list of interesting atoms
+     *        If Logs filtering is disabled - assume all atoms in use
+     *        Most of the time should be non-blocking call - only in case when setAtomIds() was
+     *        called the call will be blocking due to atom list needs to be synced up
+     * @param atomId
+     * @return true if atom is used by any of consumer or filtering is disabled
+     */
+    virtual bool isAtomInUse(int atomId) const {
+        if (!mLogsFilteringEnabled) {
+            return true;
+        }
+
+        // check if there is an updated set of interesting atom ids
+        if (mLocalSetUpdateCounter != mSetUpdateCounter.load(std::memory_order_relaxed)) {
+            std::lock_guard<std::mutex> guard(mTagIdsMutex);
+            mLocalSetUpdateCounter = mSetUpdateCounter.load(std::memory_order_relaxed);
+            mLocalTagIds.swap(mTagIds);
+        }
+        return mLocalTagIds.find(atomId) != mLocalTagIds.end();
+    }
+
+    typedef const void* ConsumerId;
+
+    typedef T AtomIdSet;
+    /**
+     * @brief Set the Atom Ids object
+     *
+     * @param tagIds set of atoms ids
+     * @param consumer used to differentiate the consumers to form proper superset of ids
+     */
+    virtual void setAtomIds(AtomIdSet tagIds, ConsumerId consumer) {
+        std::lock_guard lock(mTagIdsMutex);
+        // update ids list from consumer
+        if (tagIds.size() == 0) {
+            mTagIdsPerConsumer.erase(consumer);
+        } else {
+            mTagIdsPerConsumer[consumer].swap(tagIds);
+        }
+        // populate the superset incorporating list of distinct atom ids from all consumers
+        mTagIds.clear();
+        for (const auto& [_, atomIds] : mTagIdsPerConsumer) {
+            mTagIds.insert(atomIds.begin(), atomIds.end());
+        }
+        mSetUpdateCounter.fetch_add(1, std::memory_order_relaxed);
+    }
+
+private:
+    std::atomic_bool mLogsFilteringEnabled = true;
+    std::atomic_int mSetUpdateCounter;
+    mutable int mLocalSetUpdateCounter;
+
+    mutable std::mutex mTagIdsMutex;
+    std::unordered_map<ConsumerId, AtomIdSet> mTagIdsPerConsumer;
+    mutable AtomIdSet mTagIds;
+    mutable AtomIdSet mLocalTagIds;
+
+    friend class LogEventFilterTest;
+
+    FRIEND_TEST(LogEventFilterTest, TestEmptyFilter);
+    FRIEND_TEST(LogEventFilterTest, TestRemoveNonExistingEmptyFilter);
+    FRIEND_TEST(LogEventFilterTest, TestEmptyFilterDisabled);
+    FRIEND_TEST(LogEventFilterTest, TestEmptyFilterDisabledSetter);
+    FRIEND_TEST(LogEventFilterTest, TestNonEmptyFilterFullOverlap);
+    FRIEND_TEST(LogEventFilterTest, TestNonEmptyFilterPartialOverlap);
+    FRIEND_TEST(LogEventFilterTest, TestNonEmptyFilterDisabled);
+    FRIEND_TEST(LogEventFilterTest, TestNonEmptyFilterDisabledPartialOverlap);
+    FRIEND_TEST(LogEventFilterTest, TestMultipleConsumerOverlapIds);
+    FRIEND_TEST(LogEventFilterTest, TestMultipleConsumerNonOverlapIds);
+    FRIEND_TEST(LogEventFilterTest, TestMultipleConsumerOverlapIdsRemoved);
+    FRIEND_TEST(LogEventFilterTest, TestMultipleConsumerNonOverlapIdsRemoved);
+    FRIEND_TEST(LogEventFilterTest, TestMultipleConsumerEmptyFilter);
+};
+
+typedef LogEventFilterGeneric<std::unordered_set<int>> LogEventFilter;
+
+}  // namespace statsd
+}  // namespace os
+}  // namespace android
diff --git a/statsd/tests/LogEventFilter_test.cpp b/statsd/tests/LogEventFilter_test.cpp
new file mode 100644
index 00000000..037f02d0
--- /dev/null
+++ b/statsd/tests/LogEventFilter_test.cpp
@@ -0,0 +1,191 @@
+/*
+ * Copyright (C) 2023, 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.
+ */
+#include "socket/LogEventFilter.h"
+
+#include <gtest/gtest.h>
+
+#include <algorithm>
+
+#ifdef __ANDROID__
+
+namespace android {
+namespace os {
+namespace statsd {
+
+namespace {
+
+constexpr int kAtomIdsCount = 100;  //  Filter size setup
+
+LogEventFilter::AtomIdSet generateAtomIds(int rangeStart, int rangeEndInclusive) {
+    LogEventFilter::AtomIdSet atomIds;
+    for (int i = rangeStart; i <= rangeEndInclusive; ++i) {
+        atomIds.insert(i);
+    }
+    return atomIds;
+}
+
+bool testGuaranteedUnusedAtomsNotInUse(const LogEventFilter& filter) {
+    const auto sampleIds = generateAtomIds(10000, 11000);
+    bool atLeastOneInUse = false;
+    for (const auto& atomId : sampleIds) {
+        atLeastOneInUse |= filter.isAtomInUse(atomId);
+    }
+    return !atLeastOneInUse;
+}
+
+}  // namespace
+
+TEST(LogEventFilterTest, TestEmptyFilter) {
+    LogEventFilter filter;
+    const auto sampleIds = generateAtomIds(1, kAtomIdsCount);
+    for (const auto& atomId : sampleIds) {
+        EXPECT_FALSE(filter.isAtomInUse(atomId));
+    }
+}
+
+TEST(LogEventFilterTest, TestRemoveNonExistingEmptyFilter) {
+    LogEventFilter filter;
+    EXPECT_FALSE(filter.isAtomInUse(1));
+    LogEventFilter::AtomIdSet emptyAtomIdsSet;
+    EXPECT_EQ(0, filter.mTagIdsPerConsumer.size());
+    EXPECT_EQ(0, filter.mLocalTagIds.size());
+    filter.setAtomIds(std::move(emptyAtomIdsSet), reinterpret_cast<LogEventFilter::ConsumerId>(0));
+    EXPECT_FALSE(filter.isAtomInUse(1));
+    EXPECT_EQ(0, filter.mLocalTagIds.size());
+    EXPECT_EQ(0, filter.mTagIdsPerConsumer.size());
+}
+
+TEST(LogEventFilterTest, TestEmptyFilterDisabled) {
+    LogEventFilter filter;
+    filter.setFilteringEnabled(false);
+    const auto sampleIds = generateAtomIds(1, kAtomIdsCount);
+    for (const auto& atomId : sampleIds) {
+        EXPECT_TRUE(filter.isAtomInUse(atomId));
+    }
+}
+
+TEST(LogEventFilterTest, TestNonEmptyFilterFullOverlap) {
+    LogEventFilter filter;
+    auto filterIds = generateAtomIds(1, kAtomIdsCount);
+    filter.setAtomIds(std::move(filterIds), reinterpret_cast<LogEventFilter::ConsumerId>(0));
+    EXPECT_EQ(1, filter.mTagIdsPerConsumer.size());
+
+    // inner copy updated only during fetch if required
+    EXPECT_EQ(0, filter.mLocalTagIds.size());
+    const auto sampleIds = generateAtomIds(1, kAtomIdsCount);
+    for (const auto& atomId : sampleIds) {
+        EXPECT_TRUE(filter.isAtomInUse(atomId));
+    }
+    EXPECT_EQ(kAtomIdsCount, filter.mLocalTagIds.size());
+}
+
+TEST(LogEventFilterTest, TestNonEmptyFilterPartialOverlap) {
+    LogEventFilter filter;
+    auto filterIds = generateAtomIds(1, kAtomIdsCount);
+    filter.setAtomIds(std::move(filterIds), reinterpret_cast<LogEventFilter::ConsumerId>(0));
+    // extra 100 atom ids should be filtered out
+    const auto sampleIds = generateAtomIds(1, kAtomIdsCount + 100);
+    for (const auto& atomId : sampleIds) {
+        bool const atomInUse = atomId <= kAtomIdsCount;
+        EXPECT_EQ(atomInUse, filter.isAtomInUse(atomId));
+    }
+}
+
+TEST(LogEventFilterTest, TestNonEmptyFilterDisabledPartialOverlap) {
+    LogEventFilter filter;
+    auto filterIds = generateAtomIds(1, kAtomIdsCount);
+    filter.setAtomIds(std::move(filterIds), reinterpret_cast<LogEventFilter::ConsumerId>(0));
+    filter.setFilteringEnabled(false);
+    // extra 100 atom ids should be in use due to filter is disabled
+    const auto sampleIds = generateAtomIds(1, kAtomIdsCount + 100);
+    for (const auto& atomId : sampleIds) {
+        EXPECT_TRUE(filter.isAtomInUse(atomId));
+    }
+}
+
+TEST(LogEventFilterTest, TestMultipleConsumerOverlapIdsRemoved) {
+    LogEventFilter filter;
+    auto filterIds1 = generateAtomIds(1, kAtomIdsCount);
+    // half of filterIds1 atom ids overlaps with filterIds2
+    auto filterIds2 = generateAtomIds(kAtomIdsCount / 2, kAtomIdsCount * 2);
+    filter.setAtomIds(std::move(filterIds1), reinterpret_cast<LogEventFilter::ConsumerId>(0));
+    filter.setAtomIds(std::move(filterIds2), reinterpret_cast<LogEventFilter::ConsumerId>(1));
+    // inner copy updated only during fetch if required
+    EXPECT_EQ(0, filter.mLocalTagIds.size());
+    const auto sampleIds = generateAtomIds(1, kAtomIdsCount * 2);
+    for (const auto& atomId : sampleIds) {
+        EXPECT_TRUE(filter.isAtomInUse(atomId));
+    }
+    EXPECT_EQ(kAtomIdsCount * 2, filter.mLocalTagIds.size());
+    EXPECT_TRUE(testGuaranteedUnusedAtomsNotInUse(filter));
+
+    // set empty filter for second consumer
+    LogEventFilter::AtomIdSet emptyAtomIdsSet;
+    filter.setAtomIds(std::move(emptyAtomIdsSet), reinterpret_cast<LogEventFilter::ConsumerId>(1));
+    EXPECT_EQ(kAtomIdsCount * 2, filter.mLocalTagIds.size());
+    for (const auto& atomId : sampleIds) {
+        bool const atomInUse = atomId <= kAtomIdsCount;
+        EXPECT_EQ(atomInUse, filter.isAtomInUse(atomId));
+    }
+    EXPECT_EQ(kAtomIdsCount, filter.mLocalTagIds.size());
+    EXPECT_TRUE(testGuaranteedUnusedAtomsNotInUse(filter));
+}
+
+TEST(LogEventFilterTest, TestMultipleConsumerEmptyFilter) {
+    LogEventFilter filter;
+    auto filterIds1 = generateAtomIds(1, kAtomIdsCount);
+    auto filterIds2 = generateAtomIds(kAtomIdsCount + 1, kAtomIdsCount * 2);
+    filter.setAtomIds(std::move(filterIds1), reinterpret_cast<LogEventFilter::ConsumerId>(0));
+    filter.setAtomIds(std::move(filterIds2), reinterpret_cast<LogEventFilter::ConsumerId>(1));
+    EXPECT_EQ(2, filter.mTagIdsPerConsumer.size());
+    // inner copy updated only during fetch if required
+    EXPECT_EQ(0, filter.mLocalTagIds.size());
+    const auto sampleIds = generateAtomIds(1, kAtomIdsCount * 2);
+    for (const auto& atomId : sampleIds) {
+        EXPECT_TRUE(filter.isAtomInUse(atomId));
+    }
+    EXPECT_EQ(kAtomIdsCount * 2, filter.mLocalTagIds.size());
+    EXPECT_TRUE(testGuaranteedUnusedAtomsNotInUse(filter));
+
+    // set empty filter for first consumer
+    LogEventFilter::AtomIdSet emptyAtomIdsSet;
+    filter.setAtomIds(emptyAtomIdsSet, reinterpret_cast<LogEventFilter::ConsumerId>(0));
+    EXPECT_EQ(1, filter.mTagIdsPerConsumer.size());
+    EXPECT_EQ(kAtomIdsCount * 2, filter.mLocalTagIds.size());
+    for (const auto& atomId : sampleIds) {
+        bool const atomInUse = atomId > kAtomIdsCount;
+        EXPECT_EQ(atomInUse, filter.isAtomInUse(atomId));
+    }
+    EXPECT_EQ(kAtomIdsCount, filter.mLocalTagIds.size());
+    EXPECT_TRUE(testGuaranteedUnusedAtomsNotInUse(filter));
+
+    // set empty filter for second consumer
+    filter.setAtomIds(emptyAtomIdsSet, reinterpret_cast<LogEventFilter::ConsumerId>(1));
+    EXPECT_EQ(0, filter.mTagIdsPerConsumer.size());
+    EXPECT_EQ(kAtomIdsCount, filter.mLocalTagIds.size());
+    for (const auto& atomId : sampleIds) {
+        EXPECT_FALSE(filter.isAtomInUse(atomId));
+    }
+    EXPECT_EQ(0, filter.mLocalTagIds.size());
+    EXPECT_TRUE(testGuaranteedUnusedAtomsNotInUse(filter));
+}
+
+}  // namespace statsd
+}  // namespace os
+}  // namespace android
+#else
+GTEST_LOG_(INFO) << "This test does nothing.\n";
+#endif