cmds/statsd/src/HashableDimensionKey.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 <mutex>

#include "HashableDimensionKey.h"
#include "FieldValue.h"

namespace android {
namespace os {
namespace statsd {

using std::string;
using std::vector;

android::hash_t hashDimension(const HashableDimensionKey& value) {
    android::hash_t hash = 0;
    for (const auto& fieldValue : value.getValues()) {
        hash = android::JenkinsHashMix(hash, android::hash_type((int)fieldValue.mField.getField()));
        hash = android::JenkinsHashMix(hash, android::hash_type((int)fieldValue.mField.getTag()));
        hash = android::JenkinsHashMix(hash, android::hash_type((int)fieldValue.mValue.getType()));
        switch (fieldValue.mValue.getType()) {
            case INT:
                hash = android::JenkinsHashMix(hash,
                                               android::hash_type(fieldValue.mValue.int_value));
                break;
            case LONG:
                hash = android::JenkinsHashMix(hash,
                                               android::hash_type(fieldValue.mValue.long_value));
                break;
            case STRING:
                hash = android::JenkinsHashMix(hash, static_cast<uint32_t>(std::hash<std::string>()(
                                                             fieldValue.mValue.str_value)));
                break;
            case FLOAT: {
                hash = android::JenkinsHashMix(hash,
                                               android::hash_type(fieldValue.mValue.float_value));
                break;
            }
            default:
                break;
        }
    }
    return JenkinsHashWhiten(hash);
}

bool filterValues(const vector<Matcher>& matcherFields, const vector<FieldValue>& values,
                  HashableDimensionKey* output) {
    for (size_t i = 0; i < matcherFields.size(); ++i) {
        const auto& matcher = matcherFields[i];
        bool found = false;
        for (const auto& value : values) {
            // TODO: potential optimization here to break early because all fields are naturally
            // sorted.
            if (value.mField.matches(matcher)) {
                output->addValue(value);
                output->mutableValue(i)->mField.setTag(value.mField.getTag());
                output->mutableValue(i)->mField.setField(value.mField.getField() & matcher.mMask);
                found = true;
                break;
            }
        }

        if (!found) {
            VLOG("We can't find a dimension value for matcher (%d)%#x.", matcher.mMatcher.getTag(),
                   matcher.mMatcher.getField());
            return false;
        }
    }

    return true;
}

// Filter fields using the matchers and output the results as a HashableDimensionKey.
// Note: HashableDimensionKey is just a wrapper for vector<FieldValue>
bool filterValues(const vector<Matcher>& matcherFields, const vector<FieldValue>& values,
                  vector<HashableDimensionKey>* output) {
    output->push_back(HashableDimensionKey());
    // Top level is only tag id. Now take the real child matchers
    int prevAnyMatcherPrefix = 0;
    size_t prevPrevFanout = 0;
    size_t prevFanout = 0;

    // For each matcher get matched results.
    vector<FieldValue> matchedResults(2);
    for (const auto& matcher : matcherFields) {
        size_t num_matches = 0;
        for (const auto& value : values) {
            // TODO: potential optimization here to break early because all fields are naturally
            // sorted.
            if (value.mField.matches(matcher)) {
                if (num_matches >= matchedResults.size()) {
                    matchedResults.resize(num_matches * 2);
                }
                matchedResults[num_matches].mField.setTag(value.mField.getTag());
                matchedResults[num_matches].mField.setField(value.mField.getField() & matcher.mMask);
                matchedResults[num_matches].mValue = value.mValue;
                num_matches++;
            }
        }

        if (num_matches == 0) {
            VLOG("We can't find a dimension value for matcher (%d)%#x.", matcher.mMatcher.getTag(),
                   matcher.mMatcher.getField());
            continue;
        }

        if (num_matches == 1) {
            for (auto& dimension : *output) {
                dimension.addValue(matchedResults[0]);
            }
            prevAnyMatcherPrefix = 0;
            prevFanout = 0;
            continue;
        }

        // All the complexity below is because we support ANY in dimension.
        bool createFanout = true;
        // createFanout is true when the matcher doesn't need to follow the prev matcher's
        // order.
        // e.g., get (uid, tag) from any position in attribution. because we have translated
        // it as 2 matchers, they need to follow the same ordering, we can't create a cross
        // product of all uid and tags.
        // However, if the 2 matchers have different prefix, they will create a cross product
        // e.g., [any uid] [any some other repeated field], we will create a cross product for them
        if (prevAnyMatcherPrefix != 0) {
            int anyMatcherPrefix = 0;
            bool isAnyMatcher = matcher.hasAnyPositionMatcher(&anyMatcherPrefix);
            if (isAnyMatcher && anyMatcherPrefix == prevAnyMatcherPrefix) {
                createFanout = false;
            } else {
                prevAnyMatcherPrefix = anyMatcherPrefix;
            }
        }

        // Each matcher should match exact one field, unless position is ANY
        // When x number of fields matches a matcher, the returned dimension
        // size is multiplied by x.
        int oldSize;
        if (createFanout) {
            // First create fanout (fanout size is matchedResults.Size which could be one,
            // which means we do nothing here)
            oldSize = output->size();
            for (size_t i = 1; i < num_matches; i++) {
                output->insert(output->end(), output->begin(), output->begin() + oldSize);
            }
            prevPrevFanout = oldSize;
            prevFanout = num_matches;
        } else {
            // If we should not create fanout, e.g., uid tag from same position should be remain
            // together.
            oldSize = prevPrevFanout;
            if (prevFanout != num_matches) {
                // sanity check.
                ALOGE("2 Any matcher result in different output");
                return false;
            }
        }
        // now add the matched field value to output
        for (size_t i = 0; i < num_matches; i++) {
            for (int j = 0; j < oldSize; j++) {
                (*output)[i * oldSize + j].addValue(matchedResults[i]);
            }
        }
    }

    return output->size() > 0 && (*output)[0].getValues().size() > 0;
}

void filterGaugeValues(const std::vector<Matcher>& matcherFields,
                       const std::vector<FieldValue>& values, std::vector<FieldValue>* output) {
    for (const auto& field : matcherFields) {
        for (const auto& value : values) {
            if (value.mField.matches(field)) {
                output->push_back(value);
            }
        }
    }
}

void getDimensionForCondition(const std::vector<FieldValue>& eventValues,
                              const Metric2Condition& links,
                              HashableDimensionKey* conditionDimension) {
    // Get the dimension first by using dimension from what.
    filterValues(links.metricFields, eventValues, conditionDimension);

    size_t count = conditionDimension->getValues().size();
    if (count != links.conditionFields.size()) {
        // ALOGE("WTF condition link is bad");
        return;
    }

    for (size_t i = 0; i < count; i++) {
        conditionDimension->mutableValue(i)->mField.setField(
            links.conditionFields[i].mMatcher.getField());
        conditionDimension->mutableValue(i)->mField.setTag(
            links.conditionFields[i].mMatcher.getTag());
    }
}

bool LessThan(const vector<FieldValue>& s1, const vector<FieldValue>& s2) {
    if (s1.size() != s2.size()) {
        return s1.size() < s2.size();
    }

    size_t count = s1.size();
    for (size_t i = 0; i < count; i++) {
        if (s1[i] != s2[i]) {
            return s1[i] < s2[i];
        }
    }
    return false;
}

bool HashableDimensionKey::operator==(const HashableDimensionKey& that) const {
    if (mValues.size() != that.getValues().size()) {
        return false;
    }
    size_t count = mValues.size();
    for (size_t i = 0; i < count; i++) {
        if (mValues[i] != (that.getValues())[i]) {
            return false;
        }
    }
    return true;
};

bool HashableDimensionKey::operator<(const HashableDimensionKey& that) const {
    return LessThan(getValues(), that.getValues());
};

bool HashableDimensionKey::contains(const HashableDimensionKey& that) const {
    if (mValues.size() < that.getValues().size()) {
        return false;
    }

    if (mValues.size() == that.getValues().size()) {
        return (*this) == that;
    }

    for (const auto& value : that.getValues()) {
        bool found = false;
        for (const auto& myValue : mValues) {
            if (value.mField == myValue.mField && value.mValue == myValue.mValue) {
                found = true;
                break;
            }
        }
        if (!found) {
            return false;
        }
    }

    return true;
}

string HashableDimensionKey::toString() const {
    std::string output;
    for (const auto& value : mValues) {
        output += StringPrintf("(%d)%#x->%s ", value.mField.getTag(), value.mField.getField(),
                               value.mValue.toString().c_str());
    }
    return output;
}

bool MetricDimensionKey::operator==(const MetricDimensionKey& that) const {
    return mDimensionKeyInWhat == that.getDimensionKeyInWhat() &&
           mDimensionKeyInCondition == that.getDimensionKeyInCondition();
};

string MetricDimensionKey::toString() const {
    return mDimensionKeyInWhat.toString() + mDimensionKeyInCondition.toString();
}

bool MetricDimensionKey::operator<(const MetricDimensionKey& that) const {
    if (mDimensionKeyInWhat < that.getDimensionKeyInWhat()) {
        return true;
    } else if (that.getDimensionKeyInWhat() < mDimensionKeyInWhat) {
        return false;
    }

    return mDimensionKeyInCondition < that.getDimensionKeyInCondition();
}

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