AnomalyMonitor can get alarms based on timestamp

When StatsCompanion informs statsd that an anomaly alarm has fired,
statsd will need to check to see whether an anomaly has indeed occurred.
This will require determining which anomaly alarms have times in the
past (since that indicates that the anomaly did indeed occur). This
capability is now added.

Test: adb shell data/nativetest64/statsd_test/statsd_test
Change-Id: I5464c94634df70832d2723d8c4718277776d58aa

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