path: root/services/surfaceflinger/CompositionEngine/src/planner/Predictor.cpp

/*
 * Copyright 2021 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 LOG_NDEBUG 0

#undef LOG_TAG
#define LOG_TAG "Planner"

#include <compositionengine/impl/planner/Predictor.h>

namespace android::compositionengine::impl::planner {

std::optional<LayerStack::ApproximateMatch> LayerStack::getApproximateMatch(
        const std::vector<const LayerState*>& other) const {
    // Differing numbers of layers are never an approximate match
    if (mLayers.size() != other.size()) {
        return std::nullopt;
    }

    std::optional<ApproximateMatch> approximateMatch = {};
    for (size_t i = 0; i < mLayers.size(); ++i) {
        // Skip identical layers
        if (mLayers[i].getHash() == other[i]->getHash()) {
            continue;
        }

        // Skip layers where both are client-composited, since that doesn't change the
        // composition plan
        if (mLayers[i].getCompositionType() == hal::Composition::CLIENT &&
            other[i]->getCompositionType() == hal::Composition::CLIENT) {
            continue;
        }

        // If layers differ in composition type, their stacks are too different
        if (mLayers[i].getCompositionType() != other[i]->getCompositionType()) {
            return std::nullopt;
        }

        // If layers are not identical, but we already detected a prior approximate match for a
        // previous layer, the LayerStacks differ by too much, so return nothing
        if (approximateMatch) {
            return std::nullopt;
        }

        Flags<LayerStateField> differingFields = mLayers[i].getDifferingFields(*other[i]);

        // If we don't find an approximate match on this layer, then the LayerStacks differ
        // by too much, so return nothing
        const int differingFieldCount = __builtin_popcount(differingFields.get());
        if (differingFieldCount <= kMaxDifferingFields) {
            approximateMatch = ApproximateMatch{
                    .differingIndex = i,
                    .differingFields = differingFields,
            };
        } else {
            return std::nullopt;
        }
    }

    if (approximateMatch) {
        return approximateMatch;
    }

    // If we make it through the layer-by-layer comparison without an approximate match,
    // it means that all layers were either identical or had client-composited layers in common,
    // which don't affect the composition strategy, so return a successful result with
    // no differences.
    return ApproximateMatch{
            .differingIndex = 0,
            .differingFields = {},
    };
}

std::optional<Plan> Plan::fromString(const std::string& string) {
    Plan plan;
    for (char c : string) {
        switch (c) {
            case 'C':
                plan.addLayerType(hal::Composition::CLIENT);
                continue;
            case 'U':
                plan.addLayerType(hal::Composition::CURSOR);
                continue;
            case 'D':
                plan.addLayerType(hal::Composition::DEVICE);
                continue;
            case 'I':
                plan.addLayerType(hal::Composition::INVALID);
                continue;
            case 'B':
                plan.addLayerType(hal::Composition::SIDEBAND);
                continue;
            case 'S':
                plan.addLayerType(hal::Composition::SOLID_COLOR);
                continue;
            default:
                return std::nullopt;
        }
    }
    return plan;
}

std::string to_string(const Plan& plan) {
    std::string result;
    for (auto type : plan.mLayerTypes) {
        switch (type) {
            case hal::Composition::CLIENT:
                result.append("C");
                break;
            case hal::Composition::CURSOR:
                result.append("U");
                break;
            case hal::Composition::DEVICE:
                result.append("D");
                break;
            case hal::Composition::INVALID:
                result.append("I");
                break;
            case hal::Composition::SIDEBAND:
                result.append("B");
                break;
            case hal::Composition::SOLID_COLOR:
                result.append("S");
                break;
        }
    }
    return result;
}

void Prediction::dump(std::string& result) const {
    result.append(to_string(mPlan));
    result.append(" [Exact ");
    mExactStats.dump(result);
    result.append("] [Approximate ");
    mApproximateStats.dump(result);
    result.append("]");
}

std::optional<Predictor::PredictedPlan> Predictor::getPredictedPlan(
        const std::vector<const LayerState*>& layers, NonBufferHash hash) const {
    // First check for an exact match
    if (std::optional<Plan> exactMatch = getExactMatch(hash); exactMatch) {
        ALOGV("[%s] Found an exact match for %zx", __func__, hash);
        return PredictedPlan{.hash = hash, .plan = *exactMatch, .type = Prediction::Type::Exact};
    }

    // If only a hash was passed in for a layer stack with a cached set, don't perform
    // approximate matches and return early
    if (layers.empty()) {
        ALOGV("[%s] Only hash was passed, but no exact match was found", __func__);
        return std::nullopt;
    }

    // Then check for approximate matches
    if (std::optional<NonBufferHash> approximateMatch = getApproximateMatch(layers);
        approximateMatch) {
        ALOGV("[%s] Found an approximate match for %zx", __func__, *approximateMatch);
        const Prediction& prediction = getPrediction(*approximateMatch);
        return PredictedPlan{.hash = *approximateMatch,
                             .plan = prediction.getPlan(),
                             .type = Prediction::Type::Approximate};
    }

    return std::nullopt;
}

void Predictor::recordResult(std::optional<PredictedPlan> predictedPlan,
                             NonBufferHash flattenedHash,
                             const std::vector<const LayerState*>& layers, bool hasSkippedLayers,
                             Plan result) {
    if (predictedPlan) {
        recordPredictedResult(*predictedPlan, layers, std::move(result));
        return;
    }

    ++mMissCount;

    if (!hasSkippedLayers && findSimilarPrediction(layers, result)) {
        return;
    }

    ALOGV("[%s] Adding novel candidate %zx", __func__, flattenedHash);
    mCandidates.emplace_front(flattenedHash, Prediction(layers, result));
    if (mCandidates.size() > MAX_CANDIDATES) {
        mCandidates.pop_back();
    }
}

void Predictor::dump(std::string& result) const {
    result.append("Predictor state:\n");

    const size_t hitCount = mExactHitCount + mApproximateHitCount;
    const size_t totalAttempts = hitCount + mMissCount;
    base::StringAppendF(&result, "Global non-skipped hit rate: %.2f%% (%zd/%zd)\n",
                        100.0f * hitCount / totalAttempts, hitCount, totalAttempts);
    base::StringAppendF(&result, "  Exact hits: %zd\n", mExactHitCount);
    base::StringAppendF(&result, "  Approximate hits: %zd\n", mApproximateHitCount);
    base::StringAppendF(&result, "  Misses: %zd\n\n", mMissCount);

    dumpPredictionsByFrequency(result);
}

void Predictor::compareLayerStacks(NonBufferHash leftHash, NonBufferHash rightHash,
                                   std::string& result) const {
    const auto& [leftPredictionEntry, rightPredictionEntry] =
            std::make_tuple(mPredictions.find(leftHash), mPredictions.find(rightHash));
    if (leftPredictionEntry == mPredictions.end()) {
        base::StringAppendF(&result, "No prediction found for %zx\n", leftHash);
        return;
    }
    if (rightPredictionEntry == mPredictions.end()) {
        base::StringAppendF(&result, "No prediction found for %zx\n", rightHash);
        return;
    }

    base::StringAppendF(&result,
                        "Comparing           %-16zx                                %-16zx\n",
                        leftHash, rightHash);

    const auto& [leftPrediction, rightPrediction] =
            std::make_tuple(leftPredictionEntry->second, rightPredictionEntry->second);
    const auto& [leftStack, rightStack] = std::make_tuple(leftPrediction.getExampleLayerStack(),
                                                          rightPrediction.getExampleLayerStack());
    leftStack.compare(rightStack, result);
}

void Predictor::describeLayerStack(NonBufferHash hash, std::string& result) const {
    base::StringAppendF(&result, "Describing %zx:\n\n", hash);

    if (const auto predictionsEntry = mPredictions.find(hash);
        predictionsEntry != mPredictions.cend()) {
        const auto& [hash, prediction] = *predictionsEntry;

        prediction.getExampleLayerStack().dump(result);

        result.append("Prediction: ");
        prediction.dump(result);
        result.append("\n");
    } else {
        result.append("No predictions found\n");
    }
}

void Predictor::listSimilarStacks(Plan plan, std::string& result) const {
    base::StringAppendF(&result, "Similar stacks for plan %s:\n", to_string(plan).c_str());

    if (const auto similarStacksEntry = mSimilarStacks.find(plan);
        similarStacksEntry != mSimilarStacks.end()) {
        const auto& [_, similarStacks] = *similarStacksEntry;
        for (NonBufferHash hash : similarStacks) {
            base::StringAppendF(&result, "\nPrediction hash %zx:\n", hash);
            const Prediction& prediction = mPredictions.at(hash);
            prediction.getExampleLayerStack().dumpLayerNames(result);
        }
    } else {
        result.append("No similar stacks found\n");
    }
}

const Prediction& Predictor::getPrediction(NonBufferHash hash) const {
    if (const auto predictionEntry = mPredictions.find(hash);
        predictionEntry != mPredictions.end()) {
        const auto& [_, prediction] = *predictionEntry;
        return prediction;
    } else {
        const auto candidateEntry = getCandidateEntryByHash(hash);
        ALOGE_IF(candidateEntry == mCandidates.cend(),
                 "Hash should have been found in either predictions or candidates");
        const auto& [_, prediction] = *candidateEntry;
        return prediction;
    }
}

Prediction& Predictor::getPrediction(NonBufferHash hash) {
    return const_cast<Prediction&>(const_cast<const Predictor*>(this)->getPrediction(hash));
}

std::optional<Plan> Predictor::getExactMatch(NonBufferHash hash) const {
    const Prediction* match = nullptr;
    if (const auto predictionEntry = mPredictions.find(hash);
        predictionEntry != mPredictions.end()) {
        const auto& [hash, prediction] = *predictionEntry;
        match = &prediction;
    } else if (const auto candidateEntry = getCandidateEntryByHash(hash);
               candidateEntry != mCandidates.cend()) {
        match = &(candidateEntry->prediction);
    }

    if (match == nullptr) {
        return std::nullopt;
    }

    if (match->getMissCount(Prediction::Type::Exact) != 0) {
        ALOGV("[%s] Skipping exact match for %zx because of prior miss", __func__, hash);
        return std::nullopt;
    }

    return match->getPlan();
}

std::optional<NonBufferHash> Predictor::getApproximateMatch(
        const std::vector<const LayerState*>& layers) const {
    const auto approximateStackMatches = [&](const ApproximateStack& approximateStack) {
        const auto& exampleStack = mPredictions.at(approximateStack.hash).getExampleLayerStack();
        if (const auto approximateMatchOpt = exampleStack.getApproximateMatch(layers);
            approximateMatchOpt) {
            return *approximateMatchOpt == approximateStack.match;
        }
        return false;
    };

    const auto candidateMatches = [&](const PromotionCandidate& candidate) {
        ALOGV("[getApproximateMatch] checking against %zx", candidate.hash);
        return candidate.prediction.getExampleLayerStack().getApproximateMatch(layers) !=
                std::nullopt;
    };

    const Prediction* match = nullptr;
    NonBufferHash hash;
    if (const auto approximateStackIter =
                std::find_if(mApproximateStacks.cbegin(), mApproximateStacks.cend(),
                             approximateStackMatches);
        approximateStackIter != mApproximateStacks.cend()) {
        match = &mPredictions.at(approximateStackIter->hash);
        hash = approximateStackIter->hash;
    } else if (const auto candidateEntry =
                       std::find_if(mCandidates.cbegin(), mCandidates.cend(), candidateMatches);
               candidateEntry != mCandidates.cend()) {
        match = &(candidateEntry->prediction);
        hash = candidateEntry->hash;
    }

    if (match == nullptr) {
        return std::nullopt;
    }

    if (match->getMissCount(Prediction::Type::Approximate) != 0) {
        ALOGV("[%s] Skipping approximate match for %zx because of prior miss", __func__, hash);
        return std::nullopt;
    }

    return hash;
}

void Predictor::promoteIfCandidate(NonBufferHash predictionHash) {
    // Return if the candidate has already been promoted
    if (mPredictions.count(predictionHash) != 0) {
        return;
    }

    ALOGV("[%s] Promoting %zx from candidate to prediction", __func__, predictionHash);

    auto candidateEntry = getCandidateEntryByHash(predictionHash);
    ALOGE_IF(candidateEntry == mCandidates.end(), "Expected to find candidate");

    mSimilarStacks[candidateEntry->prediction.getPlan()].push_back(predictionHash);
    mPredictions.emplace(predictionHash, std::move(candidateEntry->prediction));
    mCandidates.erase(candidateEntry);
}

void Predictor::recordPredictedResult(PredictedPlan predictedPlan,
                                      const std::vector<const LayerState*>& layers, Plan result) {
    Prediction& prediction = getPrediction(predictedPlan.hash);
    if (prediction.getPlan() != result) {
        ALOGV("[%s] %s prediction missed, expected %s, found %s", __func__,
              to_string(predictedPlan.type).c_str(), to_string(prediction.getPlan()).c_str(),
              to_string(result).c_str());
        prediction.recordMiss(predictedPlan.type);
        ++mMissCount;
        return;
    }

    switch (predictedPlan.type) {
        case Prediction::Type::Approximate:
            ++mApproximateHitCount;
            break;
        case Prediction::Type::Exact:
            ++mExactHitCount;
            break;
        default:
            break;
    }

    ALOGV("[%s] %s prediction hit", __func__, to_string(predictedPlan.type).c_str());
    ALOGV("[%s] Plan: %s", __func__, to_string(result).c_str());
    prediction.recordHit(predictedPlan.type);

    const auto stackMatchesHash = [hash = predictedPlan.hash](const ApproximateStack& stack) {
        return stack.hash == hash;
    };

    if (predictedPlan.type == Prediction::Type::Approximate) {
        // If this approximate match is not already in the list of approximate stacks, add it
        if (std::find_if(mApproximateStacks.cbegin(), mApproximateStacks.cend(),
                         stackMatchesHash) == mApproximateStacks.cend()) {
            ALOGV("[%s] Adding approximate match to list", __func__);
            const auto approximateMatchOpt =
                    prediction.getExampleLayerStack().getApproximateMatch(layers);
            ALOGE_IF(!approximateMatchOpt, "Expected an approximate match");
            mApproximateStacks.emplace_back(predictedPlan.hash, *approximateMatchOpt);
        }
    }

    promoteIfCandidate(predictedPlan.hash);
}

bool Predictor::findSimilarPrediction(const std::vector<const LayerState*>& layers, Plan result) {
    const auto stacksEntry = mSimilarStacks.find(result);
    if (stacksEntry == mSimilarStacks.end()) {
        return false;
    }

    std::optional<ApproximateStack> bestMatch;
    const auto& [plan, similarStacks] = *stacksEntry;
    for (NonBufferHash hash : similarStacks) {
        const Prediction& prediction = mPredictions.at(hash);
        auto approximateMatch = prediction.getExampleLayerStack().getApproximateMatch(layers);
        if (!approximateMatch) {
            continue;
        }

        const int differingFieldCount = __builtin_popcount(approximateMatch->differingFields.get());
        if (!bestMatch ||
            differingFieldCount < __builtin_popcount(bestMatch->match.differingFields.get())) {
            bestMatch = {hash, *approximateMatch};
        }
    }

    if (!bestMatch) {
        return false;
    }

    ALOGV("[%s] Adding %zx to approximate stacks", __func__, bestMatch->hash);

    mApproximateStacks.emplace_back(*bestMatch);
    return true;
}

void Predictor::dumpPredictionsByFrequency(std::string& result) const {
    struct HashFrequency {
        HashFrequency(NonBufferHash hash, size_t totalAttempts)
              : hash(hash), totalAttempts(totalAttempts) {}

        NonBufferHash hash;
        size_t totalAttempts;
    };

    std::vector<HashFrequency> hashFrequencies;
    for (const auto& [hash, prediction] : mPredictions) {
        hashFrequencies.emplace_back(hash,
                                     prediction.getHitCount(Prediction::Type::Total) +
                                             prediction.getMissCount(Prediction::Type::Total));
    }

    std::sort(hashFrequencies.begin(), hashFrequencies.end(),
              [](const HashFrequency& lhs, const HashFrequency& rhs) {
                  return lhs.totalAttempts > rhs.totalAttempts;
              });

    result.append("Predictions:\n");
    for (const auto& [hash, totalAttempts] : hashFrequencies) {
        base::StringAppendF(&result, "  %016zx ", hash);
        mPredictions.at(hash).dump(result);
        result.append("\n");
    }
}

} // namespace android::compositionengine::impl::planner