Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 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 | |
Yi Jin | afb3606 | 2018-01-31 19:14:25 -0800 | [diff] [blame] | 19 | #include <memory> // unique_ptr |
| 20 | |
| 21 | #include <stdlib.h> |
| 22 | |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 23 | #include <gtest/gtest_prod.h> |
Yi Jin | afb3606 | 2018-01-31 19:14:25 -0800 | [diff] [blame] | 24 | #include <utils/RefBase.h> |
| 25 | |
Yangster-mac | 932ecec | 2018-02-01 10:23:52 -0800 | [diff] [blame] | 26 | #include "AlarmMonitor.h" |
Bookatz | 8f2f3d8 | 2017-12-07 13:53:21 -0800 | [diff] [blame] | 27 | #include "config/ConfigKey.h" |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 28 | #include "frameworks/base/cmds/statsd/src/statsd_config.pb.h" // Alert |
| 29 | #include "stats_util.h" // HashableDimensionKey and DimToValMap |
| 30 | |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 31 | namespace android { |
| 32 | namespace os { |
| 33 | namespace statsd { |
| 34 | |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 35 | using std::shared_ptr; |
Yi Jin | afb3606 | 2018-01-31 19:14:25 -0800 | [diff] [blame] | 36 | using std::unordered_map; |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 37 | |
Bookatz | cc5adef | 2017-11-21 14:36:23 -0800 | [diff] [blame] | 38 | // Does NOT allow negative values. |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 39 | class AnomalyTracker : public virtual RefBase { |
| 40 | public: |
Bookatz | 8f2f3d8 | 2017-12-07 13:53:21 -0800 | [diff] [blame] | 41 | AnomalyTracker(const Alert& alert, const ConfigKey& configKey); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 42 | |
| 43 | virtual ~AnomalyTracker(); |
| 44 | |
Yangster-mac | 94e197c | 2018-01-02 16:03:03 -0800 | [diff] [blame] | 45 | // Add subscriptions that depend on this alert. |
| 46 | void addSubscription(const Subscription& subscription) { |
| 47 | mSubscriptions.push_back(subscription); |
| 48 | } |
| 49 | |
Bookatz | 6bf9825 | 2018-03-14 10:44:24 -0700 | [diff] [blame] | 50 | // Adds a bucket for the given bucketNum (index starting at 0). |
| 51 | // If a bucket for bucketNum already exists, it will be replaced. |
| 52 | // Also, advances to bucketNum (if not in the past), effectively filling any intervening |
| 53 | // buckets with 0s. |
| 54 | void addPastBucket(std::shared_ptr<DimToValMap> bucket, const int64_t& bucketNum); |
| 55 | |
| 56 | // Inserts (or replaces) the bucket entry for the given bucketNum at the given key to be the |
| 57 | // given bucketValue. If the bucket does not exist, it will be created. |
| 58 | // Also, advances to bucketNum (if not in the past), effectively filling any intervening |
| 59 | // buckets with 0s. |
Yangster-mac | 9369446 | 2018-01-22 20:49:31 -0800 | [diff] [blame] | 60 | void addPastBucket(const MetricDimensionKey& key, const int64_t& bucketValue, |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 61 | const int64_t& bucketNum); |
| 62 | |
Bookatz | 6bf9825 | 2018-03-14 10:44:24 -0700 | [diff] [blame] | 63 | // Returns true if, based on past buckets plus the new currentBucketValue (which generally |
| 64 | // represents the partially-filled current bucket), an anomaly has happened. |
Bookatz | 3e8cd35 | 2018-03-16 10:09:59 -0700 | [diff] [blame] | 65 | // Also advances to currBucketNum-1. |
Yangster-mac | 9369446 | 2018-01-22 20:49:31 -0800 | [diff] [blame] | 66 | bool detectAnomaly(const int64_t& currBucketNum, const MetricDimensionKey& key, |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 67 | const int64_t& currentBucketValue); |
| 68 | |
| 69 | // Informs incidentd about the detected alert. |
Yangster-mac | 9369446 | 2018-01-22 20:49:31 -0800 | [diff] [blame] | 70 | void declareAnomaly(const uint64_t& timestampNs, const MetricDimensionKey& key); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 71 | |
Bookatz | 6bf9825 | 2018-03-14 10:44:24 -0700 | [diff] [blame] | 72 | // Detects if, based on past buckets plus the new currentBucketValue (which generally |
| 73 | // represents the partially-filled current bucket), an anomaly has happened, and if so, |
| 74 | // declares an anomaly and informs relevant subscribers. |
Bookatz | 3e8cd35 | 2018-03-16 10:09:59 -0700 | [diff] [blame] | 75 | // Also advances to currBucketNum-1. |
Bookatz | cc5adef | 2017-11-21 14:36:23 -0800 | [diff] [blame] | 76 | void detectAndDeclareAnomaly(const uint64_t& timestampNs, const int64_t& currBucketNum, |
Yi Jin | afb3606 | 2018-01-31 19:14:25 -0800 | [diff] [blame] | 77 | const MetricDimensionKey& key, const int64_t& currentBucketValue); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 78 | |
Yangster-mac | 932ecec | 2018-02-01 10:23:52 -0800 | [diff] [blame] | 79 | // Init the AlarmMonitor which is shared across anomaly trackers. |
| 80 | virtual void setAlarmMonitor(const sp<AlarmMonitor>& alarmMonitor) { |
| 81 | return; // Base AnomalyTracker class has no need for the AlarmMonitor. |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 82 | } |
| 83 | |
Bookatz | 6bf9825 | 2018-03-14 10:44:24 -0700 | [diff] [blame] | 84 | // Returns the sum of all past bucket values for the given dimension key. |
Yangster-mac | 9369446 | 2018-01-22 20:49:31 -0800 | [diff] [blame] | 85 | int64_t getSumOverPastBuckets(const MetricDimensionKey& key) const; |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 86 | |
Bookatz | 6bf9825 | 2018-03-14 10:44:24 -0700 | [diff] [blame] | 87 | // Returns the value for a past bucket, or 0 if that bucket doesn't exist. |
Yangster-mac | 9369446 | 2018-01-22 20:49:31 -0800 | [diff] [blame] | 88 | int64_t getPastBucketValue(const MetricDimensionKey& key, const int64_t& bucketNum) const; |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 89 | |
Bookatz | 6bf9825 | 2018-03-14 10:44:24 -0700 | [diff] [blame] | 90 | // Returns the anomaly threshold set in the configuration. |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 91 | inline int64_t getAnomalyThreshold() const { |
| 92 | return mAlert.trigger_if_sum_gt(); |
| 93 | } |
| 94 | |
Bookatz | 6bf9825 | 2018-03-14 10:44:24 -0700 | [diff] [blame] | 95 | // Returns the refractory period ending timestamp (in seconds) for the given key. |
| 96 | // Before this moment, any detected anomaly will be ignored. |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 97 | // If there is no stored refractory period ending timestamp, returns 0. |
Yangster-mac | 9369446 | 2018-01-22 20:49:31 -0800 | [diff] [blame] | 98 | uint32_t getRefractoryPeriodEndsSec(const MetricDimensionKey& key) const { |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 99 | const auto& it = mRefractoryPeriodEndsSec.find(key); |
| 100 | return it != mRefractoryPeriodEndsSec.end() ? it->second : 0; |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 101 | } |
| 102 | |
Bookatz | 6bf9825 | 2018-03-14 10:44:24 -0700 | [diff] [blame] | 103 | // Returns the (constant) number of past buckets this anomaly tracker can store. |
Bookatz | cc5adef | 2017-11-21 14:36:23 -0800 | [diff] [blame] | 104 | inline int getNumOfPastBuckets() const { |
| 105 | return mNumOfPastBuckets; |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 106 | } |
| 107 | |
Bookatz | cc5adef | 2017-11-21 14:36:23 -0800 | [diff] [blame] | 108 | // Declares an anomaly for each alarm in firedAlarms that belongs to this AnomalyTracker, |
Yangster-mac | 932ecec | 2018-02-01 10:23:52 -0800 | [diff] [blame] | 109 | // and removes it from firedAlarms. Does NOT remove the alarm from the AlarmMonitor. |
| 110 | virtual void informAlarmsFired(const uint64_t& timestampNs, |
| 111 | unordered_set<sp<const InternalAlarm>, SpHash<InternalAlarm>>& firedAlarms) { |
| 112 | return; // The base AnomalyTracker class doesn't have alarms. |
Bookatz | 857aaa5 | 2017-12-19 15:29:06 -0800 | [diff] [blame] | 113 | } |
Bookatz | cc5adef | 2017-11-21 14:36:23 -0800 | [diff] [blame] | 114 | |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 115 | protected: |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 116 | // statsd_config.proto Alert message that defines this tracker. |
| 117 | const Alert mAlert; |
| 118 | |
Yangster-mac | 94e197c | 2018-01-02 16:03:03 -0800 | [diff] [blame] | 119 | // The subscriptions that depend on this alert. |
| 120 | std::vector<Subscription> mSubscriptions; |
| 121 | |
Bookatz | 8f2f3d8 | 2017-12-07 13:53:21 -0800 | [diff] [blame] | 122 | // A reference to the Alert's config key. |
| 123 | const ConfigKey& mConfigKey; |
| 124 | |
Bookatz | cc5adef | 2017-11-21 14:36:23 -0800 | [diff] [blame] | 125 | // Number of past buckets. One less than the total number of buckets needed |
| 126 | // for the anomaly detection (since the current bucket is not in the past). |
Bookatz | 2fb5653 | 2018-03-08 11:16:48 -0800 | [diff] [blame] | 127 | const int mNumOfPastBuckets; |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 128 | |
Bookatz | 6bf9825 | 2018-03-14 10:44:24 -0700 | [diff] [blame] | 129 | // Values for each of the past mNumOfPastBuckets buckets. Always of size mNumOfPastBuckets. |
| 130 | // mPastBuckets[i] can be null, meaning that no data is present in that bucket. |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 131 | std::vector<shared_ptr<DimToValMap>> mPastBuckets; |
| 132 | |
Bookatz | 6bf9825 | 2018-03-14 10:44:24 -0700 | [diff] [blame] | 133 | // Cached sum over all existing buckets in mPastBuckets. |
| 134 | // Its buckets never contain entries of 0. |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 135 | DimToValMap mSumOverPastBuckets; |
| 136 | |
| 137 | // The bucket number of the last added bucket. |
| 138 | int64_t mMostRecentBucketNum = -1; |
| 139 | |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 140 | // Map from each dimension to the timestamp that its refractory period (if this anomaly was |
Bookatz | 6bf9825 | 2018-03-14 10:44:24 -0700 | [diff] [blame] | 141 | // declared for that dimension) ends, in seconds. From this moment and onwards, anomalies |
| 142 | // can be declared again. |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 143 | // Entries may be, but are not guaranteed to be, removed after the period is finished. |
Yangster-mac | 9369446 | 2018-01-22 20:49:31 -0800 | [diff] [blame] | 144 | unordered_map<MetricDimensionKey, uint32_t> mRefractoryPeriodEndsSec; |
Bookatz | 857aaa5 | 2017-12-19 15:29:06 -0800 | [diff] [blame] | 145 | |
Bookatz | 6bf9825 | 2018-03-14 10:44:24 -0700 | [diff] [blame] | 146 | // Advances mMostRecentBucketNum to bucketNum, deleting any data that is now too old. |
| 147 | // Specifically, since it is now too old, removes the data for |
| 148 | // [mMostRecentBucketNum - mNumOfPastBuckets + 1, bucketNum - mNumOfPastBuckets]. |
| 149 | void advanceMostRecentBucketTo(const int64_t& bucketNum); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 150 | |
| 151 | // Add the information in the given bucket to mSumOverPastBuckets. |
| 152 | void addBucketToSum(const shared_ptr<DimToValMap>& bucket); |
| 153 | |
| 154 | // Subtract the information in the given bucket from mSumOverPastBuckets |
| 155 | // and remove any items with value 0. |
| 156 | void subtractBucketFromSum(const shared_ptr<DimToValMap>& bucket); |
| 157 | |
Bookatz | 6bf9825 | 2018-03-14 10:44:24 -0700 | [diff] [blame] | 158 | // From mSumOverPastBuckets[key], subtracts bucketValue, removing it if it is now 0. |
| 159 | void subtractValueFromSum(const MetricDimensionKey& key, const int64_t& bucketValue); |
| 160 | |
| 161 | // Returns true if in the refractory period, else false. |
| 162 | // If there is a stored refractory period but it ended prior to timestampNs, it is removed. |
Yangster-mac | 9369446 | 2018-01-22 20:49:31 -0800 | [diff] [blame] | 163 | bool isInRefractoryPeriod(const uint64_t& timestampNs, const MetricDimensionKey& key); |
Bookatz | cc5adef | 2017-11-21 14:36:23 -0800 | [diff] [blame] | 164 | |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 165 | // Calculates the corresponding bucket index within the circular array. |
Bookatz | 6bf9825 | 2018-03-14 10:44:24 -0700 | [diff] [blame] | 166 | // Requires bucketNum >= 0. |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 167 | size_t index(int64_t bucketNum) const; |
| 168 | |
Bookatz | cc5adef | 2017-11-21 14:36:23 -0800 | [diff] [blame] | 169 | // Resets all bucket data. For use when all the data gets stale. |
Bookatz | 857aaa5 | 2017-12-19 15:29:06 -0800 | [diff] [blame] | 170 | virtual void resetStorage(); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 171 | |
Bookatz | 6bf9825 | 2018-03-14 10:44:24 -0700 | [diff] [blame] | 172 | // Informs the subscribers (incidentd, perfetto, broadcasts, etc) that an anomaly has occurred. |
Yangster-mac | 9369446 | 2018-01-22 20:49:31 -0800 | [diff] [blame] | 173 | void informSubscribers(const MetricDimensionKey& key); |
Bookatz | d1fd242 | 2017-11-22 15:21:03 -0800 | [diff] [blame] | 174 | |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 175 | FRIEND_TEST(AnomalyTrackerTest, TestConsecutiveBuckets); |
| 176 | FRIEND_TEST(AnomalyTrackerTest, TestSparseBuckets); |
| 177 | FRIEND_TEST(GaugeMetricProducerTest, TestAnomalyDetection); |
Bookatz | 1bf9438 | 2018-01-04 11:43:20 -0800 | [diff] [blame] | 178 | FRIEND_TEST(CountMetricProducerTest, TestAnomalyDetectionUnSliced); |
Yangster-mac | e2cd6d5 | 2017-11-09 20:38:30 -0800 | [diff] [blame] | 179 | }; |
| 180 | |
| 181 | } // namespace statsd |
| 182 | } // namespace os |
| 183 | } // namespace android |