Merge "AnomalyMonitor can get alarms based on timestamp"

6 files changed, 164 insertions, 0 deletions

diff --git a/cmds/statsd/Android.mk b/cmds/statsd/Android.mk
index c5b3b68a44b7..4c95007b0c44 100644
--- a/cmds/statsd/Android.mk
+++ b/cmds/statsd/Android.mk
@@ -112,6 +112,7 @@ LOCAL_SRC_FILES := \
     ../../core/java/android/os/IStatsCompanionService.aidl \
     ../../core/java/android/os/IStatsManager.aidl \
     src/StatsService.cpp \
+    src/AnomalyMonitor.cpp \
     src/stats_util.cpp \
     src/LogEntryPrinter.cpp \
     src/LogReader.cpp \
diff --git a/cmds/statsd/src/AnomalyMonitor.cpp b/cmds/statsd/src/AnomalyMonitor.cpp
index 92fe84487d4d..4fbbc7a2267f 100644
--- a/cmds/statsd/src/AnomalyMonitor.cpp
+++ b/cmds/statsd/src/AnomalyMonitor.cpp
@@ -90,6 +90,36 @@ void AnomalyMonitor::remove(sp<const AnomalyAlarm> alarm) {
     }
 }
 
+// More efficient than repeatedly calling remove(mPq.top()) since it batches the
+// updates to the registered alarm.
+unordered_set<sp<const AnomalyAlarm>, SpHash<AnomalyAlarm>>
+                AnomalyMonitor::popSoonerThan(uint32_t timestampSec) {
+
+    if (DEBUG) ALOGD("Removing alarms with time <= %u", timestampSec);
+    unordered_set<sp<const AnomalyAlarm>, SpHash<AnomalyAlarm>> oldAlarms;
+    std::lock_guard<std::mutex> lock(mLock);
+
+    for (sp<const AnomalyAlarm> t = mPq.top();
+                t != nullptr && t->timestampSec <= timestampSec; t = mPq.top()) {
+        oldAlarms.insert(t);
+        mPq.pop(); // remove t
+    }
+    // Always update registered alarm time (if anything has changed).
+    if (!oldAlarms.empty()) {
+        if (mPq.empty()) {
+            if (DEBUG) ALOGD("Queue is empty. Cancel any alarm.");
+            mRegisteredAlarmTimeSec = 0;
+            if (mStatsCompanionService != nullptr) {
+                mStatsCompanionService->cancelAnomalyAlarm();
+            }
+        } else {
+            // Always update the registered alarm in this case (unlike remove()).
+            updateRegisteredAlarmTime_l(mPq.top()->timestampSec);
+        }
+    }
+    return oldAlarms;
+}
+
 void AnomalyMonitor::updateRegisteredAlarmTime_l(uint32_t timestampSec) {
     if (DEBUG) ALOGD("Updating reg alarm time to %u", timestampSec);
     mRegisteredAlarmTimeSec = timestampSec;
diff --git a/cmds/statsd/src/AnomalyMonitor.h b/cmds/statsd/src/AnomalyMonitor.h
index d78be5460572..7c6e5e8945a7 100644
--- a/cmds/statsd/src/AnomalyMonitor.h
+++ b/cmds/statsd/src/AnomalyMonitor.h
@@ -21,12 +21,14 @@
 #include <indexed_priority_queue.h>
 #include <utils/RefBase.h>
 
+#include <unordered_set>
 #include <queue>
 #include <vector>
 
 using namespace android;
 
 using android::os::IStatsCompanionService;
+using std::unordered_set;
 
 namespace android {
 namespace os {
@@ -86,6 +88,13 @@ public:
     void remove(sp<const AnomalyAlarm> alarm);
 
     /**
+     * Returns and removes all alarms whose timestamp <= the given timestampSec.
+     * Always updates the registered alarm if return is non-empty.
+     */
+    unordered_set<sp<const AnomalyAlarm>, SpHash<AnomalyAlarm>>
+                    popSoonerThan(uint32_t timestampSec);
+
+    /**
      * Returns the projected alarm timestamp that is registered with
      * StatsCompanionService. This may not be equal to the soonest alarm,
      * but should be within minDiffToUpdateRegisteredAlarmTimeSec of it.
diff --git a/cmds/statsd/src/indexed_priority_queue.h b/cmds/statsd/src/indexed_priority_queue.h
index c749c3ee6d17..81e8b3d023ea 100644
--- a/cmds/statsd/src/indexed_priority_queue.h
+++ b/cmds/statsd/src/indexed_priority_queue.h
@@ -55,6 +55,8 @@ public:
     void push(sp<const AA> a);
     /** Removes a from the priority queue. If not present or a==nullptr, does nothing. */
     void remove(sp<const AA> a);
+    /** Removes the top element, if there is one. */
+    void pop();
     /** Removes all elements. */
     void clear();
     /** Returns whether priority queue contains a (not just a copy of a, but a itself). */
@@ -127,6 +129,28 @@ void indexed_priority_queue<AA, Comparator>::remove(sp<const AA> a) {
     sift_down(idx);
 }
 
+// The same as, but slightly more efficient than, remove(top()).
+template <class AA, class Comparator>
+void indexed_priority_queue<AA, Comparator>::pop() {
+  sp<const AA> a = top();
+  if (a == nullptr) return;
+  const size_t idx = 1;
+  if (idx == size()) {  // if a is the last element
+    pq.pop_back();
+    indices.erase(a);
+    return;
+  }
+  // move last element (guaranteed not to be at idx) to idx, then delete a
+  sp<const AA> last_a = pq.back();
+  pq[idx] = last_a;
+  pq.pop_back();
+  indices[last_a] = idx;
+  indices.erase(a);
+
+  // get the heap back in order (since the element at idx is not in order)
+  sift_down(idx);
+}
+
 template <class AA, class Comparator>
 void indexed_priority_queue<AA, Comparator>::clear() {
     pq.clear();
diff --git a/cmds/statsd/tests/AnomalyMonitor_test.cpp b/cmds/statsd/tests/AnomalyMonitor_test.cpp
new file mode 100644
index 000000000000..d5b68118d119
--- /dev/null
+++ b/cmds/statsd/tests/AnomalyMonitor_test.cpp
@@ -0,0 +1,66 @@
+// Copyright (C) 2017 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 "statsd_test"
+
+#include "../src/AnomalyMonitor.h"
+
+#include <gtest/gtest.h>
+
+using namespace android::os::statsd;
+
+#ifdef __ANDROID__
+TEST(AnomalyMonitor, popSoonerThan) {
+    unordered_set<sp<const AnomalyAlarm>, SpHash<AnomalyAlarm>> set;
+    AnomalyMonitor am(2);
+
+    set = am.popSoonerThan(5);
+    EXPECT_TRUE(set.empty());
+
+    sp<const AnomalyAlarm> a = new AnomalyAlarm{10};
+    sp<const AnomalyAlarm> b = new AnomalyAlarm{20};
+    sp<const AnomalyAlarm> c = new AnomalyAlarm{20};
+    sp<const AnomalyAlarm> d = new AnomalyAlarm{30};
+    sp<const AnomalyAlarm> e = new AnomalyAlarm{40};
+    sp<const AnomalyAlarm> f = new AnomalyAlarm{50};
+
+    am.add(a);
+    am.add(b);
+    am.add(c);
+    am.add(d);
+    am.add(e);
+    am.add(f);
+
+    set = am.popSoonerThan(5);
+    EXPECT_TRUE(set.empty());
+
+    set = am.popSoonerThan(30);
+    EXPECT_EQ(4u, set.size());
+    EXPECT_EQ(1u, set.count(a));
+    EXPECT_EQ(1u, set.count(b));
+    EXPECT_EQ(1u, set.count(c));
+    EXPECT_EQ(1u, set.count(d));
+
+    set = am.popSoonerThan(60);
+    EXPECT_EQ(2u, set.size());
+    EXPECT_EQ(1u, set.count(e));
+    EXPECT_EQ(1u, set.count(f));
+
+    set = am.popSoonerThan(80);
+    EXPECT_EQ(0u, set.size());
+}
+
+#else
+GTEST_LOG_(INFO) << "This test does nothing.\n";
+#endif
diff --git a/cmds/statsd/tests/indexed_priority_queue_test.cpp b/cmds/statsd/tests/indexed_priority_queue_test.cpp
index e4d4d25afe00..74a482eace58 100644
--- a/cmds/statsd/tests/indexed_priority_queue_test.cpp
+++ b/cmds/statsd/tests/indexed_priority_queue_test.cpp
@@ -182,6 +182,40 @@ TEST(indexed_priority_queue, nulls) {
     EXPECT_FALSE(ipq.contains(nullptr));
 }
 
+TEST(indexed_priority_queue, pop) {
+    indexed_priority_queue<AATest, AATest::Smaller> ipq;
+    sp<const AATest> a = new AATest{1};
+    sp<const AATest> b = new AATest{2};
+    sp<const AATest> c = new AATest{3};
+
+    ipq.push(c);
+    ipq.push(b);
+    ipq.push(a);
+    EXPECT_EQ(3u, ipq.size());
+
+    ipq.pop();
+    EXPECT_EQ(2u, ipq.size());
+    EXPECT_FALSE(ipq.contains(a));
+    EXPECT_TRUE(ipq.contains(b));
+    EXPECT_TRUE(ipq.contains(c));
+
+    ipq.pop();
+    EXPECT_EQ(1u, ipq.size());
+    EXPECT_FALSE(ipq.contains(a));
+    EXPECT_FALSE(ipq.contains(b));
+    EXPECT_TRUE(ipq.contains(c));
+
+    ipq.pop();
+    EXPECT_EQ(0u, ipq.size());
+    EXPECT_FALSE(ipq.contains(a));
+    EXPECT_FALSE(ipq.contains(b));
+    EXPECT_FALSE(ipq.contains(c));
+    EXPECT_TRUE(ipq.empty());
+
+    ipq.pop(); // pop an empty queue
+    EXPECT_TRUE(ipq.empty());
+}
+
 #else
 GTEST_LOG_(INFO) << "This test does nothing.\n";
 #endif