1e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac/* 2e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * Copyright (C) 2017 The Android Open Source Project 3e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * 4e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * Licensed under the Apache License, Version 2.0 (the "License"); 5e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * you may not use this file except in compliance with the License. 6e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * You may obtain a copy of the License at 7e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * 8e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * http://www.apache.org/licenses/LICENSE-2.0 9e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * 10e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * Unless required by applicable law or agreed to in writing, software 11e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * distributed under the License is distributed on an "AS IS" BASIS, 12e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * See the License for the specific language governing permissions and 14e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac * limitations under the License. 15e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac */ 16e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 17e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac#pragma once 18e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 19afb36062d5e6d36700147226b5776b4ca8abf922Yi Jin#include <memory> // unique_ptr 20afb36062d5e6d36700147226b5776b4ca8abf922Yi Jin 21afb36062d5e6d36700147226b5776b4ca8abf922Yi Jin#include <stdlib.h> 22afb36062d5e6d36700147226b5776b4ca8abf922Yi Jin 23e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac#include <gtest/gtest_prod.h> 24afb36062d5e6d36700147226b5776b4ca8abf922Yi Jin#include <utils/RefBase.h> 25afb36062d5e6d36700147226b5776b4ca8abf922Yi Jin 26932ececa1674c59a8da9f3e32d2651e781b86fc4Yangster-mac#include "AlarmMonitor.h" 278f2f3d82053693b0dac828e848e2bb238e1db2d2Bookatz#include "config/ConfigKey.h" 28e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac#include "frameworks/base/cmds/statsd/src/statsd_config.pb.h" // Alert 29e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac#include "stats_util.h" // HashableDimensionKey and DimToValMap 30e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 31e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-macnamespace android { 32e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-macnamespace os { 33e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-macnamespace statsd { 34e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 35e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-macusing std::shared_ptr; 36afb36062d5e6d36700147226b5776b4ca8abf922Yi Jinusing std::unordered_map; 37e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 38cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz// Does NOT allow negative values. 39e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-macclass AnomalyTracker : public virtual RefBase { 40e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-macpublic: 418f2f3d82053693b0dac828e848e2bb238e1db2d2Bookatz AnomalyTracker(const Alert& alert, const ConfigKey& configKey); 42e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 43e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac virtual ~AnomalyTracker(); 44e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 4594e197cceb2ba7df13ff8de04f60bfeec64015d9Yangster-mac // Add subscriptions that depend on this alert. 4694e197cceb2ba7df13ff8de04f60bfeec64015d9Yangster-mac void addSubscription(const Subscription& subscription) { 4794e197cceb2ba7df13ff8de04f60bfeec64015d9Yangster-mac mSubscriptions.push_back(subscription); 4894e197cceb2ba7df13ff8de04f60bfeec64015d9Yangster-mac } 4994e197cceb2ba7df13ff8de04f60bfeec64015d9Yangster-mac 506bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Adds a bucket for the given bucketNum (index starting at 0). 516bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // If a bucket for bucketNum already exists, it will be replaced. 526bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Also, advances to bucketNum (if not in the past), effectively filling any intervening 536bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // buckets with 0s. 546bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz void addPastBucket(std::shared_ptr<DimToValMap> bucket, const int64_t& bucketNum); 556bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz 566bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Inserts (or replaces) the bucket entry for the given bucketNum at the given key to be the 576bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // given bucketValue. If the bucket does not exist, it will be created. 586bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Also, advances to bucketNum (if not in the past), effectively filling any intervening 596bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // buckets with 0s. 609369446f0b04945d6674550728ae81196d6fb5c2Yangster-mac void addPastBucket(const MetricDimensionKey& key, const int64_t& bucketValue, 61e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac const int64_t& bucketNum); 62e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 636bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Returns true if, based on past buckets plus the new currentBucketValue (which generally 646bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // represents the partially-filled current bucket), an anomaly has happened. 653e8cd35b551827234aa115700e50abb6c4721597Bookatz // Also advances to currBucketNum-1. 669369446f0b04945d6674550728ae81196d6fb5c2Yangster-mac bool detectAnomaly(const int64_t& currBucketNum, const MetricDimensionKey& key, 67e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac const int64_t& currentBucketValue); 68e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 69e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // Informs incidentd about the detected alert. 70b142cc8add29c8c97f6134d35873d23db666027cYangster-mac void declareAnomaly(const int64_t& timestampNs, const MetricDimensionKey& key); 71e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 726bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Detects if, based on past buckets plus the new currentBucketValue (which generally 736bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // represents the partially-filled current bucket), an anomaly has happened, and if so, 746bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // declares an anomaly and informs relevant subscribers. 753e8cd35b551827234aa115700e50abb6c4721597Bookatz // Also advances to currBucketNum-1. 76b142cc8add29c8c97f6134d35873d23db666027cYangster-mac void detectAndDeclareAnomaly(const int64_t& timestampNs, const int64_t& currBucketNum, 77afb36062d5e6d36700147226b5776b4ca8abf922Yi Jin const MetricDimensionKey& key, const int64_t& currentBucketValue); 78e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 79932ececa1674c59a8da9f3e32d2651e781b86fc4Yangster-mac // Init the AlarmMonitor which is shared across anomaly trackers. 80932ececa1674c59a8da9f3e32d2651e781b86fc4Yangster-mac virtual void setAlarmMonitor(const sp<AlarmMonitor>& alarmMonitor) { 81932ececa1674c59a8da9f3e32d2651e781b86fc4Yangster-mac return; // Base AnomalyTracker class has no need for the AlarmMonitor. 82e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac } 83e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 846bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Returns the sum of all past bucket values for the given dimension key. 859369446f0b04945d6674550728ae81196d6fb5c2Yangster-mac int64_t getSumOverPastBuckets(const MetricDimensionKey& key) const; 86e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 876bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Returns the value for a past bucket, or 0 if that bucket doesn't exist. 889369446f0b04945d6674550728ae81196d6fb5c2Yangster-mac int64_t getPastBucketValue(const MetricDimensionKey& key, const int64_t& bucketNum) const; 89e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 906bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Returns the anomaly threshold set in the configuration. 91e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac inline int64_t getAnomalyThreshold() const { 92e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac return mAlert.trigger_if_sum_gt(); 93e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac } 94e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 956bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Returns the refractory period ending timestamp (in seconds) for the given key. 966bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Before this moment, any detected anomaly will be ignored. 971bf94382d036fa8d61258205c5f4e18cd53cb61dBookatz // If there is no stored refractory period ending timestamp, returns 0. 989369446f0b04945d6674550728ae81196d6fb5c2Yangster-mac uint32_t getRefractoryPeriodEndsSec(const MetricDimensionKey& key) const { 991bf94382d036fa8d61258205c5f4e18cd53cb61dBookatz const auto& it = mRefractoryPeriodEndsSec.find(key); 1001bf94382d036fa8d61258205c5f4e18cd53cb61dBookatz return it != mRefractoryPeriodEndsSec.end() ? it->second : 0; 101e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac } 102e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 1036bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Returns the (constant) number of past buckets this anomaly tracker can store. 104cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz inline int getNumOfPastBuckets() const { 105cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz return mNumOfPastBuckets; 106e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac } 107e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 108cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz // Declares an anomaly for each alarm in firedAlarms that belongs to this AnomalyTracker, 109932ececa1674c59a8da9f3e32d2651e781b86fc4Yangster-mac // and removes it from firedAlarms. Does NOT remove the alarm from the AlarmMonitor. 110b142cc8add29c8c97f6134d35873d23db666027cYangster-mac virtual void informAlarmsFired(const int64_t& timestampNs, 111932ececa1674c59a8da9f3e32d2651e781b86fc4Yangster-mac unordered_set<sp<const InternalAlarm>, SpHash<InternalAlarm>>& firedAlarms) { 112932ececa1674c59a8da9f3e32d2651e781b86fc4Yangster-mac return; // The base AnomalyTracker class doesn't have alarms. 113857aaa520804d846a050e1eeb85d82977c983666Bookatz } 114cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz 115e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-macprotected: 116be10ddfe46ba6371bcd02cb57a06782e6b18d371Yangster-mac // For testing only. 117be10ddfe46ba6371bcd02cb57a06782e6b18d371Yangster-mac // Returns the alarm timestamp in seconds for the query dimension if it exists. Otherwise 118be10ddfe46ba6371bcd02cb57a06782e6b18d371Yangster-mac // returns 0. 119be10ddfe46ba6371bcd02cb57a06782e6b18d371Yangster-mac virtual uint32_t getAlarmTimestampSec(const MetricDimensionKey& dimensionKey) const { 120be10ddfe46ba6371bcd02cb57a06782e6b18d371Yangster-mac return 0; // The base AnomalyTracker class doesn't have alarms. 121be10ddfe46ba6371bcd02cb57a06782e6b18d371Yangster-mac } 122be10ddfe46ba6371bcd02cb57a06782e6b18d371Yangster-mac 123e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // statsd_config.proto Alert message that defines this tracker. 124e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac const Alert mAlert; 125e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 12694e197cceb2ba7df13ff8de04f60bfeec64015d9Yangster-mac // The subscriptions that depend on this alert. 12794e197cceb2ba7df13ff8de04f60bfeec64015d9Yangster-mac std::vector<Subscription> mSubscriptions; 12894e197cceb2ba7df13ff8de04f60bfeec64015d9Yangster-mac 1298f2f3d82053693b0dac828e848e2bb238e1db2d2Bookatz // A reference to the Alert's config key. 130c04feba805c5acde92638a062cc13030fc4d3308Yangster-mac const ConfigKey mConfigKey; 1318f2f3d82053693b0dac828e848e2bb238e1db2d2Bookatz 132cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz // Number of past buckets. One less than the total number of buckets needed 133cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz // for the anomaly detection (since the current bucket is not in the past). 1342fb5653b9761dba5fa29d9abd84e938e59932075Bookatz const int mNumOfPastBuckets; 135e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 1366bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Values for each of the past mNumOfPastBuckets buckets. Always of size mNumOfPastBuckets. 1376bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // mPastBuckets[i] can be null, meaning that no data is present in that bucket. 138e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac std::vector<shared_ptr<DimToValMap>> mPastBuckets; 139e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 1406bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Cached sum over all existing buckets in mPastBuckets. 1416bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Its buckets never contain entries of 0. 142e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac DimToValMap mSumOverPastBuckets; 143e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 144e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // The bucket number of the last added bucket. 145e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac int64_t mMostRecentBucketNum = -1; 146e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 1471bf94382d036fa8d61258205c5f4e18cd53cb61dBookatz // Map from each dimension to the timestamp that its refractory period (if this anomaly was 1486bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // declared for that dimension) ends, in seconds. From this moment and onwards, anomalies 1496bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // can be declared again. 1501bf94382d036fa8d61258205c5f4e18cd53cb61dBookatz // Entries may be, but are not guaranteed to be, removed after the period is finished. 1519369446f0b04945d6674550728ae81196d6fb5c2Yangster-mac unordered_map<MetricDimensionKey, uint32_t> mRefractoryPeriodEndsSec; 152857aaa520804d846a050e1eeb85d82977c983666Bookatz 1536bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Advances mMostRecentBucketNum to bucketNum, deleting any data that is now too old. 1546bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Specifically, since it is now too old, removes the data for 1556bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // [mMostRecentBucketNum - mNumOfPastBuckets + 1, bucketNum - mNumOfPastBuckets]. 1566bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz void advanceMostRecentBucketTo(const int64_t& bucketNum); 157e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 158e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // Add the information in the given bucket to mSumOverPastBuckets. 159e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac void addBucketToSum(const shared_ptr<DimToValMap>& bucket); 160e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 161e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // Subtract the information in the given bucket from mSumOverPastBuckets 162e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // and remove any items with value 0. 163e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac void subtractBucketFromSum(const shared_ptr<DimToValMap>& bucket); 164e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 1656bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // From mSumOverPastBuckets[key], subtracts bucketValue, removing it if it is now 0. 1666bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz void subtractValueFromSum(const MetricDimensionKey& key, const int64_t& bucketValue); 1676bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz 1686bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Returns true if in the refractory period, else false. 169b142cc8add29c8c97f6134d35873d23db666027cYangster-mac bool isInRefractoryPeriod(const int64_t& timestampNs, const MetricDimensionKey& key) const; 170cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz 171e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac // Calculates the corresponding bucket index within the circular array. 1726bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Requires bucketNum >= 0. 173e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac size_t index(int64_t bucketNum) const; 174e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 175cc5adef2d0c5f96a225fd69517fd1eecb557f46dBookatz // Resets all bucket data. For use when all the data gets stale. 176857aaa520804d846a050e1eeb85d82977c983666Bookatz virtual void resetStorage(); 177e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 1786bf9825b1575bfc3c62ef0a5129f94b6a776ef66Bookatz // Informs the subscribers (incidentd, perfetto, broadcasts, etc) that an anomaly has occurred. 1799369446f0b04945d6674550728ae81196d6fb5c2Yangster-mac void informSubscribers(const MetricDimensionKey& key); 180d1fd2425f744ab46a87dec4ed4d3f0680e819dbcBookatz 181e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac FRIEND_TEST(AnomalyTrackerTest, TestConsecutiveBuckets); 182e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac FRIEND_TEST(AnomalyTrackerTest, TestSparseBuckets); 183e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac FRIEND_TEST(GaugeMetricProducerTest, TestAnomalyDetection); 1841bf94382d036fa8d61258205c5f4e18cd53cb61dBookatz FRIEND_TEST(CountMetricProducerTest, TestAnomalyDetectionUnSliced); 185be10ddfe46ba6371bcd02cb57a06782e6b18d371Yangster-mac FRIEND_TEST(AnomalyDetectionE2eTest, TestDurationMetric_SUM_single_bucket); 186be10ddfe46ba6371bcd02cb57a06782e6b18d371Yangster-mac FRIEND_TEST(AnomalyDetectionE2eTest, TestDurationMetric_SUM_multiple_buckets); 187be10ddfe46ba6371bcd02cb57a06782e6b18d371Yangster-mac FRIEND_TEST(AnomalyDetectionE2eTest, TestDurationMetric_SUM_long_refractory_period); 188e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac}; 189e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac 190e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac} // namespace statsd 191e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac} // namespace os 192e2cd6d509b17894b95d14523ae3e7c4c7a9a74e3Yangster-mac} // namespace android 193