cmds/statsd/src/condition/SimpleConditionTracker.cpp

/*
 * Copyright (C) 2017 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#define DEBUG false  // STOPSHIP if true
#include "Log.h"

#include "SimpleConditionTracker.h"
#include "guardrail/StatsdStats.h"

namespace android {
namespace os {
namespace statsd {

using std::map;
using std::string;
using std::unique_ptr;
using std::unordered_map;
using std::vector;

SimpleConditionTracker::SimpleConditionTracker(
        const ConfigKey& key, const int64_t& id, const int index,
        const SimplePredicate& simplePredicate,
        const unordered_map<int64_t, int>& trackerNameIndexMap)
    : ConditionTracker(id, index), mConfigKey(key) {
    VLOG("creating SimpleConditionTracker %lld", (long long)mConditionId);
    mCountNesting = simplePredicate.count_nesting();

    if (simplePredicate.has_start()) {
        auto pair = trackerNameIndexMap.find(simplePredicate.start());
        if (pair == trackerNameIndexMap.end()) {
            ALOGW("Start matcher %lld not found in the config", (long long)simplePredicate.start());
            return;
        }
        mStartLogMatcherIndex = pair->second;
        mTrackerIndex.insert(mStartLogMatcherIndex);
    } else {
        mStartLogMatcherIndex = -1;
    }

    if (simplePredicate.has_stop()) {
        auto pair = trackerNameIndexMap.find(simplePredicate.stop());
        if (pair == trackerNameIndexMap.end()) {
            ALOGW("Stop matcher %lld not found in the config", (long long)simplePredicate.stop());
            return;
        }
        mStopLogMatcherIndex = pair->second;
        mTrackerIndex.insert(mStopLogMatcherIndex);
    } else {
        mStopLogMatcherIndex = -1;
    }

    if (simplePredicate.has_stop_all()) {
        auto pair = trackerNameIndexMap.find(simplePredicate.stop_all());
        if (pair == trackerNameIndexMap.end()) {
            ALOGW("Stop all matcher %lld found in the config", (long long)simplePredicate.stop_all());
            return;
        }
        mStopAllLogMatcherIndex = pair->second;
        mTrackerIndex.insert(mStopAllLogMatcherIndex);
    } else {
        mStopAllLogMatcherIndex = -1;
    }

    if (simplePredicate.has_dimensions()) {
        translateFieldMatcher(simplePredicate.dimensions(), &mOutputDimensions);
        if (mOutputDimensions.size() > 0) {
            mSliced = true;
            mDimensionTag = mOutputDimensions[0].mMatcher.getTag();
        }
    }

    if (simplePredicate.initial_value() == SimplePredicate_InitialValue_FALSE) {
        mInitialValue = ConditionState::kFalse;
    } else {
        mInitialValue = ConditionState::kUnknown;
    }

    mNonSlicedConditionState = mInitialValue;

    mInitialized = true;
}

SimpleConditionTracker::~SimpleConditionTracker() {
    VLOG("~SimpleConditionTracker()");
}

bool SimpleConditionTracker::init(const vector<Predicate>& allConditionConfig,
                                  const vector<sp<ConditionTracker>>& allConditionTrackers,
                                  const unordered_map<int64_t, int>& conditionIdIndexMap,
                                  vector<bool>& stack) {
    // SimpleConditionTracker does not have dependency on other conditions, thus we just return
    // if the initialization was successful.
    return mInitialized;
}

void SimpleConditionTracker::dumpState() {
    VLOG("%lld DUMP:", (long long)mConditionId);
    for (const auto& pair : mSlicedConditionState) {
        VLOG("\t%s : %d", pair.first.c_str(), pair.second);
    }

    VLOG("Changed to true keys: \n");
    for (const auto& key : mLastChangedToTrueDimensions) {
        VLOG("%s", key.toString().c_str());
    }
    VLOG("Changed to false keys: \n");
    for (const auto& key : mLastChangedToFalseDimensions) {
        VLOG("%s", key.toString().c_str());
    }
}

void SimpleConditionTracker::handleStopAll(std::vector<ConditionState>& conditionCache,
                                           std::vector<bool>& conditionChangedCache) {
    // Unless the default condition is false, and there was nothing started, otherwise we have
    // triggered a condition change.
    conditionChangedCache[mIndex] =
            (mInitialValue == ConditionState::kFalse && mSlicedConditionState.empty()) ? false
                                                                                           : true;

    for (const auto& cond : mSlicedConditionState) {
        if (cond.second > 0) {
            mLastChangedToFalseDimensions.insert(cond.first);
        }
    }

    // After StopAll, we know everything has stopped. From now on, default condition is false.
    mInitialValue = ConditionState::kFalse;
    mSlicedConditionState.clear();
    conditionCache[mIndex] = ConditionState::kFalse;
}

bool SimpleConditionTracker::hitGuardRail(const HashableDimensionKey& newKey) {
    if (!mSliced || mSlicedConditionState.find(newKey) != mSlicedConditionState.end()) {
        // if the condition is not sliced or the key is not new, we are good!
        return false;
    }
    // 1. Report the tuple count if the tuple count > soft limit
    if (mSlicedConditionState.size() > StatsdStats::kDimensionKeySizeSoftLimit - 1) {
        size_t newTupleCount = mSlicedConditionState.size() + 1;
        StatsdStats::getInstance().noteConditionDimensionSize(mConfigKey, mConditionId, newTupleCount);
        // 2. Don't add more tuples, we are above the allowed threshold. Drop the data.
        if (newTupleCount > StatsdStats::kDimensionKeySizeHardLimit) {
            ALOGE("Predicate %lld dropping data for dimension key %s",
                (long long)mConditionId, newKey.c_str());
            return true;
        }
    }
    return false;
}

void SimpleConditionTracker::handleConditionEvent(const HashableDimensionKey& outputKey,
                                                  bool matchStart, ConditionState* conditionCache,
                                                  bool* conditionChangedCache) {
    bool changed = false;
    auto outputIt = mSlicedConditionState.find(outputKey);
    ConditionState newCondition;
    if (hitGuardRail(outputKey)) {
        (*conditionChangedCache) = false;
        // Tells the caller it's evaluated.
        (*conditionCache) = ConditionState::kUnknown;
        return;
    }
    if (outputIt == mSlicedConditionState.end()) {
        // We get a new output key.
        newCondition = matchStart ? ConditionState::kTrue : ConditionState::kFalse;
        if (matchStart && mInitialValue != ConditionState::kTrue) {
            mSlicedConditionState.insert(std::make_pair(outputKey, 1));
            changed = true;
            mLastChangedToTrueDimensions.insert(outputKey);
        } else if (mInitialValue != ConditionState::kFalse) {
            // it's a stop and we don't have history about it.
            // If the default condition is not false, it means this stop is valuable to us.
            mSlicedConditionState.insert(std::make_pair(outputKey, 0));
            mLastChangedToFalseDimensions.insert(outputKey);
            changed = true;
        }
    } else {
        // we have history about this output key.
        auto& startedCount = outputIt->second;
        // assign the old value first.
        newCondition = startedCount > 0 ? ConditionState::kTrue : ConditionState::kFalse;
        if (matchStart) {
            if (startedCount == 0) {
                mLastChangedToTrueDimensions.insert(outputKey);
                // This condition for this output key will change from false -> true
                changed = true;
            }

            // it's ok to do ++ here, even if we don't count nesting. The >1 counts will be treated
            // as 1 if not counting nesting.
            startedCount++;
            newCondition = ConditionState::kTrue;
        } else {
            // This is a stop event.
            if (startedCount > 0) {
                if (mCountNesting) {
                    startedCount--;
                    if (startedCount == 0) {
                        newCondition = ConditionState::kFalse;
                    }
                } else {
                    // not counting nesting, so ignore the number of starts, stop now.
                    startedCount = 0;
                    newCondition = ConditionState::kFalse;
                }
                // if everything has stopped for this output key, condition true -> false;
                if (startedCount == 0) {
                    mLastChangedToFalseDimensions.insert(outputKey);
                    changed = true;
                }
            }

            // if default condition is false, it means we don't need to keep the false values.
            if (mInitialValue == ConditionState::kFalse && startedCount == 0) {
                mSlicedConditionState.erase(outputIt);
                VLOG("erase key %s", outputKey.c_str());
            }
        }
    }

    // dump all dimensions for debugging
    if (DEBUG) {
        dumpState();
    }

    (*conditionChangedCache) = changed;
    (*conditionCache) = newCondition;
    VLOG("SimplePredicate %lld nonSlicedChange? %d", (long long)mConditionId,
         conditionChangedCache[mIndex] == true);
}

void SimpleConditionTracker::evaluateCondition(
        const LogEvent& event,
        const vector<MatchingState>& eventMatcherValues,
        const vector<sp<ConditionTracker>>& mAllConditions,
        vector<ConditionState>& conditionCache,
        vector<bool>& conditionChangedCache) {
    if (conditionCache[mIndex] != ConditionState::kNotEvaluated) {
        // it has been evaluated.
        VLOG("Yes, already evaluated, %lld %d",
            (long long)mConditionId, conditionCache[mIndex]);
        return;
    }
    mLastChangedToTrueDimensions.clear();
    mLastChangedToFalseDimensions.clear();

    if (mStopAllLogMatcherIndex >= 0 && mStopAllLogMatcherIndex < int(eventMatcherValues.size()) &&
        eventMatcherValues[mStopAllLogMatcherIndex] == MatchingState::kMatched) {
        handleStopAll(conditionCache, conditionChangedCache);
        return;
    }

    int matchedState = -1;
    // Note: The order to evaluate the following start, stop, stop_all matters.
    // The priority of overwrite is stop_all > stop > start.
    if (mStartLogMatcherIndex >= 0 &&
        eventMatcherValues[mStartLogMatcherIndex] == MatchingState::kMatched) {
        matchedState = 1;
    }

    if (mStopLogMatcherIndex >= 0 &&
        eventMatcherValues[mStopLogMatcherIndex] == MatchingState::kMatched) {
        matchedState = 0;
    }

    if (matchedState < 0) {
        // The event doesn't match this condition. So we just report existing condition values.
        conditionChangedCache[mIndex] = false;
        if (mSliced) {
            // if the condition result is sliced. metrics won't directly get value from the
            // cache, so just set any value other than kNotEvaluated.
            conditionCache[mIndex] = mInitialValue;
        } else {
            const auto& itr = mSlicedConditionState.find(DEFAULT_DIMENSION_KEY);
            if (itr == mSlicedConditionState.end()) {
                // condition not sliced, but we haven't seen the matched start or stop yet. so
                // return initial value.
                conditionCache[mIndex] = mInitialValue;
            } else {
                // return the cached condition.
                conditionCache[mIndex] =
                        itr->second > 0 ? ConditionState::kTrue : ConditionState::kFalse;
            }
        }

        return;
    }

    ConditionState overallState = mInitialValue;
    bool overallChanged = false;

    if (mOutputDimensions.size() == 0) {
        handleConditionEvent(DEFAULT_DIMENSION_KEY, matchedState == 1, &overallState,
                             &overallChanged);
    } else {
        std::vector<HashableDimensionKey> outputValues;
        filterValues(mOutputDimensions, event.getValues(), &outputValues);

        // If this event has multiple nodes in the attribution chain,  this log event probably will
        // generate multiple dimensions. If so, we will find if the condition changes for any
        // dimension and ask the corresponding metric producer to verify whether the actual sliced
        // condition has changed or not.
        // A high level assumption is that a predicate is either sliced or unsliced. We will never
        // have both sliced and unsliced version of a predicate.
        for (const HashableDimensionKey& outputValue : outputValues) {
            ConditionState tempState;
            bool tempChanged = false;
            handleConditionEvent(outputValue, matchedState == 1, &tempState, &tempChanged);
            if (tempChanged) {
                overallChanged = true;
            }
            // ConditionState's | operator is overridden
            overallState = overallState | tempState;
        }
    }
    conditionCache[mIndex] = overallState;
    conditionChangedCache[mIndex] = overallChanged;
}

void SimpleConditionTracker::isConditionMet(
        const ConditionKey& conditionParameters, const vector<sp<ConditionTracker>>& allConditions,
        const vector<Matcher>& dimensionFields, vector<ConditionState>& conditionCache,
        std::unordered_set<HashableDimensionKey>& dimensionsKeySet) const {

    if (conditionCache[mIndex] != ConditionState::kNotEvaluated) {
        // it has been evaluated.
        VLOG("Yes, already evaluated, %lld %d",
            (long long)mConditionId, conditionCache[mIndex]);
        return;
    }
    const auto pair = conditionParameters.find(mConditionId);

    if (pair == conditionParameters.end()) {
        ConditionState conditionState = ConditionState::kNotEvaluated;
        if (dimensionFields.size() > 0 && dimensionFields[0].mMatcher.getTag() == mDimensionTag) {
            conditionState = conditionState | getMetConditionDimension(
                allConditions, dimensionFields, dimensionsKeySet);
        } else {
            conditionState = conditionState | mInitialValue;
            if (!mSliced) {
                const auto& itr = mSlicedConditionState.find(DEFAULT_DIMENSION_KEY);
                if (itr != mSlicedConditionState.end()) {
                    ConditionState sliceState =
                        itr->second > 0 ? ConditionState::kTrue : ConditionState::kFalse;
                    conditionState = conditionState | sliceState;
                }
            }
        }
        conditionCache[mIndex] = conditionState;
        return;
    }
    std::vector<HashableDimensionKey> defaultKeys = { DEFAULT_DIMENSION_KEY };
    const std::vector<HashableDimensionKey> &keys =
            (pair == conditionParameters.end()) ? defaultKeys : pair->second;

    ConditionState conditionState = ConditionState::kNotEvaluated;
    for (size_t i = 0; i < keys.size(); ++i) {
        const HashableDimensionKey& key = keys[i];
        auto startedCountIt = mSlicedConditionState.find(key);
        if (startedCountIt != mSlicedConditionState.end()) {
            ConditionState sliceState =
                startedCountIt->second > 0 ? ConditionState::kTrue : ConditionState::kFalse;
            conditionState = conditionState | sliceState;
            if (sliceState == ConditionState::kTrue && dimensionFields.size() > 0) {
                vector<HashableDimensionKey> dimensionKeys;
                filterValues(dimensionFields, startedCountIt->first.getValues(), &dimensionKeys);
                dimensionsKeySet.insert(dimensionKeys.begin(), dimensionKeys.end());
            }
        } else {
            // For unseen key, check whether the require dimensions are subset of sliced condition
            // output.
            conditionState = conditionState | mInitialValue;
            for (const auto& slice : mSlicedConditionState) {
                ConditionState sliceState =
                    slice.second > 0 ? ConditionState::kTrue : ConditionState::kFalse;
                if (slice.first.contains(key)) {
                    conditionState = conditionState | sliceState;
                    if (sliceState == ConditionState::kTrue && dimensionFields.size() > 0) {
                        vector<HashableDimensionKey> dimensionKeys;
                        filterValues(dimensionFields, slice.first.getValues(), &dimensionKeys);

                        dimensionsKeySet.insert(dimensionKeys.begin(), dimensionKeys.end());
                    }
                    }
                }
            }
        }
    conditionCache[mIndex] = conditionState;
    VLOG("Predicate %lld return %d", (long long)mConditionId, conditionCache[mIndex]);
}

ConditionState SimpleConditionTracker::getMetConditionDimension(
        const std::vector<sp<ConditionTracker>>& allConditions,
        const vector<Matcher>& dimensionFields,
        std::unordered_set<HashableDimensionKey>& dimensionsKeySet) const {
    ConditionState conditionState = mInitialValue;
    if (dimensionFields.size() == 0 || mOutputDimensions.size() == 0 ||
        dimensionFields[0].mMatcher.getTag() != mOutputDimensions[0].mMatcher.getTag()) {
        const auto& itr = mSlicedConditionState.find(DEFAULT_DIMENSION_KEY);
        if (itr != mSlicedConditionState.end()) {
            ConditionState sliceState =
                itr->second > 0 ? ConditionState::kTrue : ConditionState::kFalse;
            conditionState = conditionState | sliceState;
        }
        return conditionState;
    }

    for (const auto& slice : mSlicedConditionState) {
        ConditionState sliceState =
            slice.second > 0 ? ConditionState::kTrue : ConditionState::kFalse;
        conditionState = conditionState | sliceState;

        if (sliceState == ConditionState::kTrue && dimensionFields.size() > 0) {
            vector<HashableDimensionKey> dimensionKeys;
            filterValues(dimensionFields, slice.first.getValues(), &dimensionKeys);

            dimensionsKeySet.insert(dimensionKeys.begin(), dimensionKeys.end());
        }
    }
    return conditionState;
}

}  // namespace statsd
}  // namespace os
}  // namespace android