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 18 19 #include "Log.h" 20 #include "MaxDurationTracker.h" 21 #include "guardrail/StatsdStats.h" 22 23 namespace android { 24 namespace os { 25 namespace statsd { 26 27 MaxDurationTracker::MaxDurationTracker(const ConfigKey& key, const int64_t& id, 28 const MetricDimensionKey& eventKey, 29 sp<ConditionWizard> wizard, int conditionIndex, 30 const vector<Matcher>& dimensionInCondition, bool nesting, 31 int64_t currentBucketStartNs, int64_t currentBucketNum, 32 int64_t startTimeNs, int64_t bucketSizeNs, 33 bool conditionSliced, bool fullLink, 34 const vector<sp<DurationAnomalyTracker>>& anomalyTrackers) 35 : DurationTracker(key, id, eventKey, wizard, conditionIndex, dimensionInCondition, nesting, 36 currentBucketStartNs, currentBucketNum, startTimeNs, bucketSizeNs, 37 conditionSliced, fullLink, anomalyTrackers) { 38 if (mWizard != nullptr) { 39 mSameConditionDimensionsInTracker = 40 mWizard->equalOutputDimensions(conditionIndex, mDimensionInCondition); 41 } 42 } 43 44 unique_ptr<DurationTracker> MaxDurationTracker::clone(const int64_t eventTime) { 45 auto clonedTracker = make_unique<MaxDurationTracker>(*this); 46 for (auto it = clonedTracker->mInfos.begin(); it != clonedTracker->mInfos.end();) { 47 if (it->second.state != kStopped) { 48 it->second.lastStartTime = eventTime; 49 it->second.lastDuration = 0; 50 it++; 51 } else { 52 it = clonedTracker->mInfos.erase(it); 53 } 54 } 55 if (clonedTracker->mInfos.empty()) { 56 return nullptr; 57 } else { 58 return clonedTracker; 59 } 60 } 61 62 bool MaxDurationTracker::hitGuardRail(const HashableDimensionKey& newKey) { 63 // ===========GuardRail============== 64 if (mInfos.find(newKey) != mInfos.end()) { 65 // if the key existed, we are good! 66 return false; 67 } 68 // 1. Report the tuple count if the tuple count > soft limit 69 if (mInfos.size() > StatsdStats::kDimensionKeySizeSoftLimit - 1) { 70 size_t newTupleCount = mInfos.size() + 1; 71 StatsdStats::getInstance().noteMetricDimensionSize(mConfigKey, mTrackerId, newTupleCount); 72 // 2. Don't add more tuples, we are above the allowed threshold. Drop the data. 73 if (newTupleCount > StatsdStats::kDimensionKeySizeHardLimit) { 74 ALOGE("MaxDurTracker %lld dropping data for dimension key %s", 75 (long long)mTrackerId, newKey.toString().c_str()); 76 return true; 77 } 78 } 79 return false; 80 } 81 82 void MaxDurationTracker::noteStart(const HashableDimensionKey& key, bool condition, 83 const int64_t eventTime, const ConditionKey& conditionKey) { 84 // this will construct a new DurationInfo if this key didn't exist. 85 if (hitGuardRail(key)) { 86 return; 87 } 88 89 DurationInfo& duration = mInfos[key]; 90 if (mConditionSliced) { 91 duration.conditionKeys = conditionKey; 92 } 93 VLOG("MaxDuration: key %s start condition %d", key.toString().c_str(), condition); 94 95 switch (duration.state) { 96 case kStarted: 97 duration.startCount++; 98 break; 99 case kPaused: 100 duration.startCount++; 101 break; 102 case kStopped: 103 if (!condition) { 104 // event started, but we need to wait for the condition to become true. 105 duration.state = DurationState::kPaused; 106 } else { 107 duration.state = DurationState::kStarted; 108 duration.lastStartTime = eventTime; 109 startAnomalyAlarm(eventTime); 110 } 111 duration.startCount = 1; 112 break; 113 } 114 } 115 116 117 void MaxDurationTracker::noteStop(const HashableDimensionKey& key, const int64_t eventTime, 118 bool forceStop) { 119 VLOG("MaxDuration: key %s stop", key.toString().c_str()); 120 if (mInfos.find(key) == mInfos.end()) { 121 // we didn't see a start event before. do nothing. 122 return; 123 } 124 DurationInfo& duration = mInfos[key]; 125 126 switch (duration.state) { 127 case DurationState::kStopped: 128 // already stopped, do nothing. 129 break; 130 case DurationState::kStarted: { 131 duration.startCount--; 132 if (forceStop || !mNested || duration.startCount <= 0) { 133 stopAnomalyAlarm(eventTime); 134 duration.state = DurationState::kStopped; 135 int64_t durationTime = eventTime - duration.lastStartTime; 136 VLOG("Max, key %s, Stop %lld %lld %lld", key.toString().c_str(), 137 (long long)duration.lastStartTime, (long long)eventTime, 138 (long long)durationTime); 139 duration.lastDuration += durationTime; 140 if (anyStarted()) { 141 // In case any other dimensions are still started, we need to keep the alarm 142 // set. 143 startAnomalyAlarm(eventTime); 144 } 145 VLOG(" record duration: %lld ", (long long)duration.lastDuration); 146 } 147 break; 148 } 149 case DurationState::kPaused: { 150 duration.startCount--; 151 if (forceStop || !mNested || duration.startCount <= 0) { 152 duration.state = DurationState::kStopped; 153 } 154 break; 155 } 156 } 157 158 if (duration.lastDuration > mDuration) { 159 mDuration = duration.lastDuration; 160 VLOG("Max: new max duration: %lld", (long long)mDuration); 161 } 162 // Once an atom duration ends, we erase it. Next time, if we see another atom event with the 163 // same name, they are still considered as different atom durations. 164 if (duration.state == DurationState::kStopped) { 165 mInfos.erase(key); 166 } 167 } 168 169 bool MaxDurationTracker::anyStarted() { 170 for (auto& pair : mInfos) { 171 if (pair.second.state == kStarted) { 172 return true; 173 } 174 } 175 return false; 176 } 177 178 void MaxDurationTracker::noteStopAll(const int64_t eventTime) { 179 std::set<HashableDimensionKey> keys; 180 for (const auto& pair : mInfos) { 181 keys.insert(pair.first); 182 } 183 for (auto& key : keys) { 184 noteStop(key, eventTime, true); 185 } 186 } 187 188 bool MaxDurationTracker::flushCurrentBucket( 189 const int64_t& eventTimeNs, 190 std::unordered_map<MetricDimensionKey, std::vector<DurationBucket>>* output) { 191 VLOG("MaxDurationTracker flushing....."); 192 193 // adjust the bucket start time 194 int numBucketsForward = 0; 195 int64_t fullBucketEnd = getCurrentBucketEndTimeNs(); 196 int64_t currentBucketEndTimeNs; 197 if (eventTimeNs >= fullBucketEnd) { 198 numBucketsForward = 1 + (eventTimeNs - fullBucketEnd) / mBucketSizeNs; 199 currentBucketEndTimeNs = fullBucketEnd; 200 } else { 201 // This must be a partial bucket. 202 currentBucketEndTimeNs = eventTimeNs; 203 } 204 205 bool hasPendingEvent = 206 false; // has either a kStarted or kPaused event across bucket boundaries 207 // meaning we need to carry them over to the new bucket. 208 for (auto it = mInfos.begin(); it != mInfos.end();) { 209 if (it->second.state == DurationState::kStopped) { 210 // No need to keep buckets for events that were stopped before. 211 it = mInfos.erase(it); 212 } else { 213 ++it; 214 hasPendingEvent = true; 215 } 216 } 217 218 // mDuration is updated in noteStop to the maximum duration that ended in the current bucket. 219 if (mDuration != 0) { 220 DurationBucket info; 221 info.mBucketStartNs = mCurrentBucketStartTimeNs; 222 info.mBucketEndNs = currentBucketEndTimeNs; 223 info.mDuration = mDuration; 224 (*output)[mEventKey].push_back(info); 225 VLOG(" final duration for last bucket: %lld", (long long)mDuration); 226 } 227 228 if (numBucketsForward > 0) { 229 mCurrentBucketStartTimeNs = fullBucketEnd + (numBucketsForward - 1) * mBucketSizeNs; 230 mCurrentBucketNum += numBucketsForward; 231 } else { // We must be forming a partial bucket. 232 mCurrentBucketStartTimeNs = eventTimeNs; 233 } 234 235 mDuration = 0; 236 // If this tracker has no pending events, tell owner to remove. 237 return !hasPendingEvent; 238 } 239 240 bool MaxDurationTracker::flushIfNeeded( 241 int64_t eventTimeNs, unordered_map<MetricDimensionKey, vector<DurationBucket>>* output) { 242 if (eventTimeNs < getCurrentBucketEndTimeNs()) { 243 return false; 244 } 245 return flushCurrentBucket(eventTimeNs, output); 246 } 247 248 void MaxDurationTracker::onSlicedConditionMayChange(bool overallCondition, 249 const int64_t timestamp) { 250 // Now for each of the on-going event, check if the condition has changed for them. 251 for (auto& pair : mInfos) { 252 if (pair.second.state == kStopped) { 253 continue; 254 } 255 std::unordered_set<HashableDimensionKey> conditionDimensionKeySet; 256 ConditionState conditionState = mWizard->query( 257 mConditionTrackerIndex, pair.second.conditionKeys, mDimensionInCondition, 258 !mSameConditionDimensionsInTracker, 259 !mHasLinksToAllConditionDimensionsInTracker, 260 &conditionDimensionKeySet); 261 bool conditionMet = 262 (conditionState == ConditionState::kTrue) && 263 (mDimensionInCondition.size() == 0 || 264 conditionDimensionKeySet.find(mEventKey.getDimensionKeyInCondition()) != 265 conditionDimensionKeySet.end()); 266 VLOG("key: %s, condition: %d", pair.first.toString().c_str(), conditionMet); 267 noteConditionChanged(pair.first, conditionMet, timestamp); 268 } 269 } 270 271 void MaxDurationTracker::onConditionChanged(bool condition, const int64_t timestamp) { 272 for (auto& pair : mInfos) { 273 noteConditionChanged(pair.first, condition, timestamp); 274 } 275 } 276 277 void MaxDurationTracker::noteConditionChanged(const HashableDimensionKey& key, bool conditionMet, 278 const int64_t timestamp) { 279 auto it = mInfos.find(key); 280 if (it == mInfos.end()) { 281 return; 282 } 283 284 switch (it->second.state) { 285 case kStarted: 286 // If condition becomes false, kStarted -> kPaused. Record the current duration and 287 // stop anomaly alarm. 288 if (!conditionMet) { 289 stopAnomalyAlarm(timestamp); 290 it->second.state = DurationState::kPaused; 291 it->second.lastDuration += (timestamp - it->second.lastStartTime); 292 if (anyStarted()) { 293 // In case any other dimensions are still started, we need to set the alarm. 294 startAnomalyAlarm(timestamp); 295 } 296 VLOG("MaxDurationTracker Key: %s Started->Paused ", key.toString().c_str()); 297 } 298 break; 299 case kStopped: 300 // Nothing to do if it's stopped. 301 break; 302 case kPaused: 303 // If condition becomes true, kPaused -> kStarted. and the start time is the condition 304 // change time. 305 if (conditionMet) { 306 it->second.state = DurationState::kStarted; 307 it->second.lastStartTime = timestamp; 308 startAnomalyAlarm(timestamp); 309 VLOG("MaxDurationTracker Key: %s Paused->Started", key.toString().c_str()); 310 } 311 break; 312 } 313 // Note that we don't update mDuration here since it's only updated during noteStop. 314 } 315 316 int64_t MaxDurationTracker::predictAnomalyTimestampNs(const DurationAnomalyTracker& anomalyTracker, 317 const int64_t currentTimestamp) const { 318 // The allowed time we can continue in the current state is the 319 // (anomaly threshold) - max(elapsed time of the started mInfos). 320 int64_t maxElapsed = 0; 321 for (auto it = mInfos.begin(); it != mInfos.end(); ++it) { 322 if (it->second.state == DurationState::kStarted) { 323 int64_t duration = 324 it->second.lastDuration + (currentTimestamp - it->second.lastStartTime); 325 if (duration > maxElapsed) { 326 maxElapsed = duration; 327 } 328 } 329 } 330 int64_t anomalyTimeNs = currentTimestamp + anomalyTracker.getAnomalyThreshold() - maxElapsed; 331 int64_t refractoryEndNs = anomalyTracker.getRefractoryPeriodEndsSec(mEventKey) * NS_PER_SEC; 332 return std::max(anomalyTimeNs, refractoryEndNs); 333 } 334 335 void MaxDurationTracker::dumpStates(FILE* out, bool verbose) const { 336 fprintf(out, "\t\t sub-durations %lu\n", (unsigned long)mInfos.size()); 337 fprintf(out, "\t\t current duration %lld\n", (long long)mDuration); 338 } 339 340 } // namespace statsd 341 } // namespace os 342 } // namespace android 343