1 /*
2  * Copyright (C) 2017 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #pragma once
18 
19 #include <stdlib.h>
20 
21 #include <gtest/gtest_prod.h>
22 #include <utils/RefBase.h>
23 
24 #include "AlarmMonitor.h"
25 #include "config/ConfigKey.h"
26 #include "frameworks/base/cmds/statsd/src/statsd_config.pb.h"  // Alert
27 #include "stats_util.h"  // HashableDimensionKey and DimToValMap
28 
29 namespace android {
30 namespace os {
31 namespace statsd {
32 
33 using std::shared_ptr;
34 using std::unordered_map;
35 
36 // Does NOT allow negative values.
37 class AnomalyTracker : public virtual RefBase {
38 public:
39     AnomalyTracker(const Alert& alert, const ConfigKey& configKey);
40 
41     virtual ~AnomalyTracker();
42 
43     // Add subscriptions that depend on this alert.
addSubscription(const Subscription & subscription)44     void addSubscription(const Subscription& subscription) {
45         mSubscriptions.push_back(subscription);
46     }
47 
48     // Adds a bucket for the given bucketNum (index starting at 0).
49     // If a bucket for bucketNum already exists, it will be replaced.
50     // Also, advances to bucketNum (if not in the past), effectively filling any intervening
51     // buckets with 0s.
52     void addPastBucket(std::shared_ptr<DimToValMap> bucket, const int64_t& bucketNum);
53 
54     // Inserts (or replaces) the bucket entry for the given bucketNum at the given key to be the
55     // given bucketValue. If the bucket does not exist, it will be created.
56     // Also, advances to bucketNum (if not in the past), effectively filling any intervening
57     // buckets with 0s.
58     void addPastBucket(const MetricDimensionKey& key, const int64_t& bucketValue,
59                        const int64_t& bucketNum);
60 
61     // Returns true if, based on past buckets plus the new currentBucketValue (which generally
62     // represents the partially-filled current bucket), an anomaly has happened.
63     // Also advances to currBucketNum-1.
64     bool detectAnomaly(const int64_t& currBucketNum, const MetricDimensionKey& key,
65                        const int64_t& currentBucketValue);
66 
67     // Informs incidentd about the detected alert.
68     void declareAnomaly(const int64_t& timestampNs, int64_t metricId, const MetricDimensionKey& key,
69                         int64_t metricValue);
70 
71     // Detects if, based on past buckets plus the new currentBucketValue (which generally
72     // represents the partially-filled current bucket), an anomaly has happened, and if so,
73     // declares an anomaly and informs relevant subscribers.
74     // Also advances to currBucketNum-1.
75     void detectAndDeclareAnomaly(const int64_t& timestampNs, const int64_t& currBucketNum,
76                                  int64_t metricId, const MetricDimensionKey& key,
77                                  const int64_t& currentBucketValue);
78 
79     // Init the AlarmMonitor which is shared across anomaly trackers.
setAlarmMonitor(const sp<AlarmMonitor> & alarmMonitor)80     virtual void setAlarmMonitor(const sp<AlarmMonitor>& alarmMonitor) {
81         return; // Base AnomalyTracker class has no need for the AlarmMonitor.
82     }
83 
84     // Returns the sum of all past bucket values for the given dimension key.
85     int64_t getSumOverPastBuckets(const MetricDimensionKey& key) const;
86 
87     // Returns the value for a past bucket, or 0 if that bucket doesn't exist.
88     int64_t getPastBucketValue(const MetricDimensionKey& key, const int64_t& bucketNum) const;
89 
90     // Returns the anomaly threshold set in the configuration.
getAnomalyThreshold()91     inline int64_t getAnomalyThreshold() const {
92         return mAlert.trigger_if_sum_gt();
93     }
94 
95     // Returns the refractory period ending timestamp (in seconds) for the given key.
96     // Before this moment, any detected anomaly will be ignored.
97     // If there is no stored refractory period ending timestamp, returns 0.
getRefractoryPeriodEndsSec(const MetricDimensionKey & key)98     uint32_t getRefractoryPeriodEndsSec(const MetricDimensionKey& key) const {
99         const auto& it = mRefractoryPeriodEndsSec.find(key);
100         return it != mRefractoryPeriodEndsSec.end() ? it->second : 0;
101     }
102 
103     // Returns the (constant) number of past buckets this anomaly tracker can store.
getNumOfPastBuckets()104     inline int getNumOfPastBuckets() const {
105         return mNumOfPastBuckets;
106     }
107 
108     // Declares an anomaly for each alarm in firedAlarms that belongs to this AnomalyTracker,
109     // and removes it from firedAlarms. Does NOT remove the alarm from the AlarmMonitor.
informAlarmsFired(const int64_t & timestampNs,unordered_set<sp<const InternalAlarm>,SpHash<InternalAlarm>> & firedAlarms)110     virtual void informAlarmsFired(const int64_t& timestampNs,
111             unordered_set<sp<const InternalAlarm>, SpHash<InternalAlarm>>& firedAlarms) {
112         return; // The base AnomalyTracker class doesn't have alarms.
113     }
114 
115 protected:
116     // For testing only.
117     // Returns the alarm timestamp in seconds for the query dimension if it exists. Otherwise
118     // returns 0.
getAlarmTimestampSec(const MetricDimensionKey & dimensionKey)119     virtual uint32_t getAlarmTimestampSec(const MetricDimensionKey& dimensionKey) const {
120         return 0;   // The base AnomalyTracker class doesn't have alarms.
121     }
122 
123     // statsd_config.proto Alert message that defines this tracker.
124     const Alert mAlert;
125 
126     // The subscriptions that depend on this alert.
127     std::vector<Subscription> mSubscriptions;
128 
129     // A reference to the Alert's config key.
130     const ConfigKey mConfigKey;
131 
132     // Number of past buckets. One less than the total number of buckets needed
133     // for the anomaly detection (since the current bucket is not in the past).
134     const int mNumOfPastBuckets;
135 
136     // Values for each of the past mNumOfPastBuckets buckets. Always of size mNumOfPastBuckets.
137     // mPastBuckets[i] can be null, meaning that no data is present in that bucket.
138     std::vector<shared_ptr<DimToValMap>> mPastBuckets;
139 
140     // Cached sum over all existing buckets in mPastBuckets.
141     // Its buckets never contain entries of 0.
142     DimToValMap mSumOverPastBuckets;
143 
144     // The bucket number of the last added bucket.
145     int64_t mMostRecentBucketNum = -1;
146 
147     // Map from each dimension to the timestamp that its refractory period (if this anomaly was
148     // declared for that dimension) ends, in seconds. From this moment and onwards, anomalies
149     // can be declared again.
150     // Entries may be, but are not guaranteed to be, removed after the period is finished.
151     unordered_map<MetricDimensionKey, uint32_t> mRefractoryPeriodEndsSec;
152 
153     // Advances mMostRecentBucketNum to bucketNum, deleting any data that is now too old.
154     // Specifically, since it is now too old, removes the data for
155     //   [mMostRecentBucketNum - mNumOfPastBuckets + 1, bucketNum - mNumOfPastBuckets].
156     void advanceMostRecentBucketTo(const int64_t& bucketNum);
157 
158     // Add the information in the given bucket to mSumOverPastBuckets.
159     void addBucketToSum(const shared_ptr<DimToValMap>& bucket);
160 
161     // Subtract the information in the given bucket from mSumOverPastBuckets
162     // and remove any items with value 0.
163     void subtractBucketFromSum(const shared_ptr<DimToValMap>& bucket);
164 
165     // From mSumOverPastBuckets[key], subtracts bucketValue, removing it if it is now 0.
166     void subtractValueFromSum(const MetricDimensionKey& key, const int64_t& bucketValue);
167 
168     // Returns true if in the refractory period, else false.
169     bool isInRefractoryPeriod(const int64_t& timestampNs, const MetricDimensionKey& key) const;
170 
171     // Calculates the corresponding bucket index within the circular array.
172     // Requires bucketNum >= 0.
173     size_t index(int64_t bucketNum) const;
174 
175     // Resets all bucket data. For use when all the data gets stale.
176     virtual void resetStorage();
177 
178     // Informs the subscribers (incidentd, perfetto, broadcasts, etc) that an anomaly has occurred.
179     void informSubscribers(const MetricDimensionKey& key, int64_t metricId, int64_t metricValue);
180 
181     FRIEND_TEST(AnomalyTrackerTest, TestConsecutiveBuckets);
182     FRIEND_TEST(AnomalyTrackerTest, TestSparseBuckets);
183     FRIEND_TEST(GaugeMetricProducerTest, TestAnomalyDetection);
184     FRIEND_TEST(CountMetricProducerTest, TestAnomalyDetectionUnSliced);
185     FRIEND_TEST(AnomalyDetectionE2eTest, TestDurationMetric_SUM_single_bucket);
186     FRIEND_TEST(AnomalyDetectionE2eTest, TestDurationMetric_SUM_multiple_buckets);
187     FRIEND_TEST(AnomalyDetectionE2eTest, TestDurationMetric_SUM_long_refractory_period);
188 };
189 
190 }  // namespace statsd
191 }  // namespace os
192 }  // namespace android
193