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#define DEBUG false  // STOPSHIP if true
18#include "Log.h"
19
20#include "AnomalyTracker.h"
21#include "subscriber_util.h"
22#include "external/Perfetto.h"
23#include "guardrail/StatsdStats.h"
24#include "subscriber/IncidentdReporter.h"
25#include "subscriber/SubscriberReporter.h"
26
27#include <statslog.h>
28#include <time.h>
29
30namespace android {
31namespace os {
32namespace statsd {
33
34AnomalyTracker::AnomalyTracker(const Alert& alert, const ConfigKey& configKey)
35        : mAlert(alert), mConfigKey(configKey), mNumOfPastBuckets(mAlert.num_buckets() - 1) {
36    VLOG("AnomalyTracker() called");
37    if (mAlert.num_buckets() <= 0) {
38        ALOGE("Cannot create AnomalyTracker with %lld buckets", (long long)mAlert.num_buckets());
39        return;
40    }
41    if (!mAlert.has_trigger_if_sum_gt()) {
42        ALOGE("Cannot create AnomalyTracker without threshold");
43        return;
44    }
45    resetStorage();  // initialization
46}
47
48AnomalyTracker::~AnomalyTracker() {
49    VLOG("~AnomalyTracker() called");
50}
51
52void AnomalyTracker::resetStorage() {
53    VLOG("resetStorage() called.");
54    mPastBuckets.clear();
55    // Excludes the current bucket.
56    mPastBuckets.resize(mNumOfPastBuckets);
57    mSumOverPastBuckets.clear();
58}
59
60size_t AnomalyTracker::index(int64_t bucketNum) const {
61    if (bucketNum < 0) {
62        ALOGE("index() was passed a negative bucket number (%lld)!", (long long)bucketNum);
63    }
64    return bucketNum % mNumOfPastBuckets;
65}
66
67void AnomalyTracker::advanceMostRecentBucketTo(const int64_t& bucketNum) {
68    VLOG("advanceMostRecentBucketTo() called.");
69    if (mNumOfPastBuckets <= 0) {
70        return;
71    }
72    if (bucketNum <= mMostRecentBucketNum) {
73        ALOGW("Cannot advance buckets backwards (bucketNum=%lld but mMostRecentBucketNum=%lld)",
74              (long long)bucketNum, (long long)mMostRecentBucketNum);
75        return;
76    }
77    // If in the future (i.e. buckets are ancient), just empty out all past info.
78    if (bucketNum >= mMostRecentBucketNum + mNumOfPastBuckets) {
79        resetStorage();
80        mMostRecentBucketNum = bucketNum;
81        return;
82    }
83
84    // Clear out space by emptying out old mPastBuckets[i] values and update mSumOverPastBuckets.
85    for (int64_t i = mMostRecentBucketNum + 1; i <= bucketNum; i++) {
86        const int idx = index(i);
87        subtractBucketFromSum(mPastBuckets[idx]);
88        mPastBuckets[idx] = nullptr;  // release (but not clear) the old bucket.
89    }
90    mMostRecentBucketNum = bucketNum;
91}
92
93void AnomalyTracker::addPastBucket(const MetricDimensionKey& key,
94                                   const int64_t& bucketValue,
95                                   const int64_t& bucketNum) {
96    VLOG("addPastBucket(bucketValue) called.");
97    if (mNumOfPastBuckets == 0 ||
98        bucketNum < 0 || bucketNum <= mMostRecentBucketNum - mNumOfPastBuckets) {
99        return;
100    }
101
102    const int bucketIndex = index(bucketNum);
103    if (bucketNum <= mMostRecentBucketNum && (mPastBuckets[bucketIndex] != nullptr)) {
104        // We need to insert into an already existing past bucket.
105        std::shared_ptr<DimToValMap>& bucket = mPastBuckets[bucketIndex];
106        auto itr = bucket->find(key);
107        if (itr != bucket->end()) {
108            // Old entry already exists; update it.
109            subtractValueFromSum(key, itr->second);
110            itr->second = bucketValue;
111        } else {
112            bucket->insert({key, bucketValue});
113        }
114        mSumOverPastBuckets[key] += bucketValue;
115    } else {
116        // Bucket does not exist yet (in future or was never made), so we must make it.
117        std::shared_ptr<DimToValMap> bucket = std::make_shared<DimToValMap>();
118        bucket->insert({key, bucketValue});
119        addPastBucket(bucket, bucketNum);
120    }
121}
122
123void AnomalyTracker::addPastBucket(std::shared_ptr<DimToValMap> bucket,
124                                   const int64_t& bucketNum) {
125    VLOG("addPastBucket(bucket) called.");
126    if (mNumOfPastBuckets == 0 ||
127            bucketNum < 0 || bucketNum <= mMostRecentBucketNum - mNumOfPastBuckets) {
128        return;
129    }
130
131    if (bucketNum <= mMostRecentBucketNum) {
132        // We are updating an old bucket, not adding a new one.
133        subtractBucketFromSum(mPastBuckets[index(bucketNum)]);
134    } else {
135        // Clear space for the new bucket to be at bucketNum.
136        advanceMostRecentBucketTo(bucketNum);
137    }
138    mPastBuckets[index(bucketNum)] = bucket;
139    addBucketToSum(bucket);
140}
141
142void AnomalyTracker::subtractBucketFromSum(const shared_ptr<DimToValMap>& bucket) {
143    if (bucket == nullptr) {
144        return;
145    }
146    for (const auto& keyValuePair : *bucket) {
147        subtractValueFromSum(keyValuePair.first, keyValuePair.second);
148    }
149}
150
151
152void AnomalyTracker::subtractValueFromSum(const MetricDimensionKey& key,
153                                          const int64_t& bucketValue) {
154    auto itr = mSumOverPastBuckets.find(key);
155    if (itr == mSumOverPastBuckets.end()) {
156        return;
157    }
158    itr->second -= bucketValue;
159    if (itr->second == 0) {
160        mSumOverPastBuckets.erase(itr);
161    }
162}
163
164void AnomalyTracker::addBucketToSum(const shared_ptr<DimToValMap>& bucket) {
165    if (bucket == nullptr) {
166        return;
167    }
168    // For each dimension present in the bucket, add its value to its corresponding sum.
169    for (const auto& keyValuePair : *bucket) {
170        mSumOverPastBuckets[keyValuePair.first] += keyValuePair.second;
171    }
172}
173
174int64_t AnomalyTracker::getPastBucketValue(const MetricDimensionKey& key,
175                                           const int64_t& bucketNum) const {
176    if (bucketNum < 0 || mMostRecentBucketNum < 0
177            || bucketNum <= mMostRecentBucketNum - mNumOfPastBuckets
178            || bucketNum > mMostRecentBucketNum) {
179        return 0;
180    }
181
182    const auto& bucket = mPastBuckets[index(bucketNum)];
183    if (bucket == nullptr) {
184        return 0;
185    }
186    const auto& itr = bucket->find(key);
187    return itr == bucket->end() ? 0 : itr->second;
188}
189
190int64_t AnomalyTracker::getSumOverPastBuckets(const MetricDimensionKey& key) const {
191    const auto& itr = mSumOverPastBuckets.find(key);
192    if (itr != mSumOverPastBuckets.end()) {
193        return itr->second;
194    }
195    return 0;
196}
197
198bool AnomalyTracker::detectAnomaly(const int64_t& currentBucketNum,
199                                   const MetricDimensionKey& key,
200                                   const int64_t& currentBucketValue) {
201
202    // currentBucketNum should be the next bucket after pastBuckets. If not, advance so that it is.
203    if (currentBucketNum > mMostRecentBucketNum + 1) {
204        advanceMostRecentBucketTo(currentBucketNum - 1);
205    }
206    return mAlert.has_trigger_if_sum_gt() &&
207           getSumOverPastBuckets(key) + currentBucketValue > mAlert.trigger_if_sum_gt();
208}
209
210void AnomalyTracker::declareAnomaly(const int64_t& timestampNs, const MetricDimensionKey& key) {
211    // TODO: Why receive timestamp? RefractoryPeriod should always be based on real time right now.
212    if (isInRefractoryPeriod(timestampNs, key)) {
213        VLOG("Skipping anomaly declaration since within refractory period");
214        return;
215    }
216    if (mAlert.has_refractory_period_secs()) {
217        mRefractoryPeriodEndsSec[key] = ((timestampNs + NS_PER_SEC - 1) / NS_PER_SEC) // round up
218                                        + mAlert.refractory_period_secs();
219        // TODO: If we had access to the bucket_size_millis, consider calling resetStorage()
220        // if (mAlert.refractory_period_secs() > mNumOfPastBuckets * bucketSizeNs) {resetStorage();}
221    }
222
223    if (!mSubscriptions.empty()) {
224        ALOGI("An anomaly (%lld) %s has occurred! Informing subscribers.",
225                mAlert.id(), key.toString().c_str());
226        informSubscribers(key);
227    } else {
228        ALOGI("An anomaly has occurred! (But no subscriber for that alert.)");
229    }
230
231    StatsdStats::getInstance().noteAnomalyDeclared(mConfigKey, mAlert.id());
232
233    // TODO: This should also take in the const MetricDimensionKey& key?
234    android::util::stats_write(android::util::ANOMALY_DETECTED, mConfigKey.GetUid(),
235                               mConfigKey.GetId(), mAlert.id());
236}
237
238void AnomalyTracker::detectAndDeclareAnomaly(const int64_t& timestampNs,
239                                             const int64_t& currBucketNum,
240                                             const MetricDimensionKey& key,
241                                             const int64_t& currentBucketValue) {
242    if (detectAnomaly(currBucketNum, key, currentBucketValue)) {
243        declareAnomaly(timestampNs, key);
244    }
245}
246
247bool AnomalyTracker::isInRefractoryPeriod(const int64_t& timestampNs,
248                                          const MetricDimensionKey& key) const {
249    const auto& it = mRefractoryPeriodEndsSec.find(key);
250    if (it != mRefractoryPeriodEndsSec.end()) {
251        return timestampNs < (it->second *  (int64_t)NS_PER_SEC);
252    }
253    return false;
254}
255
256void AnomalyTracker::informSubscribers(const MetricDimensionKey& key) {
257    triggerSubscribers(mAlert.id(), key, mConfigKey, mSubscriptions);
258}
259
260}  // namespace statsd
261}  // namespace os
262}  // namespace android
263