diff options
Diffstat (limited to 'services/surfaceflinger/CompositionEngine/src/planner/Predictor.cpp')
| -rw-r--r-- | services/surfaceflinger/CompositionEngine/src/planner/Predictor.cpp | 481 |
1 files changed, 481 insertions, 0 deletions
diff --git a/services/surfaceflinger/CompositionEngine/src/planner/Predictor.cpp b/services/surfaceflinger/CompositionEngine/src/planner/Predictor.cpp new file mode 100644 index 0000000000..8226ef7b4c --- /dev/null +++ b/services/surfaceflinger/CompositionEngine/src/planner/Predictor.cpp @@ -0,0 +1,481 @@ +/* + * 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 |