1 /*
2  * Copyright 2021 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 #pragma once
18 
19 #include <ftl/flags.h>
20 
21 #include <compositionengine/impl/planner/LayerState.h>
22 
23 namespace android::compositionengine::impl::planner {
24 
25 class LayerStack {
26 public:
LayerStack(const std::vector<const LayerState * > & layers)27     LayerStack(const std::vector<const LayerState*>& layers) : mLayers(copyLayers(layers)) {}
28 
29     // Describes an approximate match between two layer stacks
30     struct ApproximateMatch {
31         bool operator==(const ApproximateMatch& other) const {
32             return differingIndex == other.differingIndex &&
33                     differingFields == other.differingFields;
34         }
35 
36         // The index of the single differing layer between the two stacks.
37         // This implies that only one layer is allowed to differ in an approximate match.
38         size_t differingIndex;
39         // Set of fields that differ for the differing layer in the approximate match.
40         ftl::Flags<LayerStateField> differingFields;
41     };
42 
43     // Returns an approximate match when comparing this layer stack with the provided list of
44     // layers, for the purposes of scoring how closely the two layer stacks will match composition
45     // strategies.
46     //
47     // If the two layer stacks are identical, then an approximate match is still returned, but the
48     // differing fields will be empty to represent an exact match.
49     //
50     // If the two layer stacks differ by too much, then an empty optional is returned.
51     std::optional<ApproximateMatch> getApproximateMatch(
52             const std::vector<const LayerState*>& other) const;
53 
compare(const LayerStack & other,std::string & result)54     void compare(const LayerStack& other, std::string& result) const {
55         if (mLayers.size() != other.mLayers.size()) {
56             base::StringAppendF(&result, "Cannot compare stacks of different sizes (%zd vs. %zd)\n",
57                                 mLayers.size(), other.mLayers.size());
58             return;
59         }
60 
61         for (size_t l = 0; l < mLayers.size(); ++l) {
62             const auto& thisLayer = mLayers[l];
63             const auto& otherLayer = other.mLayers[l];
64             base::StringAppendF(&result, "\n+ - - - - - - - - - Layer %d [%s]\n", thisLayer.getId(),
65                                 thisLayer.getName().c_str());
66             auto comparisonOpt = thisLayer.compare(otherLayer);
67             base::StringAppendF(&result,
68                                 "    %s     + - - - - - - - - - - - - - - - - - - - - - - - "
69                                 "- Layer %d [%s]\n",
70                                 comparisonOpt ? "         " : "Identical", otherLayer.getId(),
71                                 otherLayer.getName().c_str());
72             if (comparisonOpt) {
73                 result.append(*comparisonOpt);
74             }
75         }
76     }
77 
dump(std::string & result)78     void dump(std::string& result) const {
79         for (const LayerState& layer : mLayers) {
80             base::StringAppendF(&result, "+ - - - - - - - - - Layer %d [%s]\n", layer.getId(),
81                                 layer.getName().c_str());
82             layer.dump(result);
83         }
84     }
85 
86     void dumpLayerNames(std::string& result, const std::string& prefix = "  ") const {
87         for (const LayerState& layer : mLayers) {
88             result.append(prefix);
89             result.append(layer.getName());
90             result.append("\n");
91         }
92     }
93 
94 private:
copyLayers(const std::vector<const LayerState * > & layers)95     std::vector<const LayerState> copyLayers(const std::vector<const LayerState*>& layers) {
96         std::vector<const LayerState> copiedLayers;
97         copiedLayers.reserve(layers.size());
98         std::transform(layers.cbegin(), layers.cend(), std::back_inserter(copiedLayers),
99                        [](const LayerState* layerState) { return *layerState; });
100         return copiedLayers;
101     }
102 
103     std::vector<const LayerState> mLayers;
104 
105     // TODO(b/180976743): Tune kMaxDifferingFields
106     constexpr static int kMaxDifferingFields = 6;
107 };
108 
109 class Plan {
110 public:
111     static std::optional<Plan> fromString(const std::string&);
112 
reset()113     void reset() { mLayerTypes.clear(); }
addLayerType(aidl::android::hardware::graphics::composer3::Composition type)114     void addLayerType(aidl::android::hardware::graphics::composer3::Composition type) {
115         mLayerTypes.emplace_back(type);
116     }
117 
118     friend std::string to_string(const Plan& plan);
119 
120     friend bool operator==(const Plan& lhs, const Plan& rhs) {
121         return lhs.mLayerTypes == rhs.mLayerTypes;
122     }
123     friend bool operator!=(const Plan& lhs, const Plan& rhs) { return !(lhs == rhs); }
124 
125     friend std::ostream& operator<<(std::ostream& os, const Plan& plan) {
126         return os << to_string(plan);
127     }
128 
129 private:
130     std::vector<aidl::android::hardware::graphics::composer3::Composition> mLayerTypes;
131 };
132 
133 } // namespace android::compositionengine::impl::planner
134 
135 namespace std {
136 template <>
137 struct hash<android::compositionengine::impl::planner::Plan> {
138     size_t operator()(const android::compositionengine::impl::planner::Plan& plan) const {
139         return std::hash<std::string>{}(to_string(plan));
140     }
141 };
142 } // namespace std
143 
144 namespace android::compositionengine::impl::planner {
145 
146 class Prediction {
147 public:
148     enum class Type {
149         Exact,
150         Approximate,
151         Total,
152     };
153 
154     friend std::string to_string(Type type) {
155         using namespace std::string_literals;
156 
157         switch (type) {
158             case Type::Exact:
159                 return "Exact";
160             case Type::Approximate:
161                 return "Approximate";
162             case Type::Total:
163                 return "Total";
164         }
165     }
166 
167     friend std::ostream& operator<<(std::ostream& os, const Type& type) {
168         return os << to_string(type);
169     }
170 
171     Prediction(const std::vector<const LayerState*>& layers, Plan plan)
172           : mExampleLayerStack(layers), mPlan(std::move(plan)) {}
173 
174     const LayerStack& getExampleLayerStack() const { return mExampleLayerStack; }
175     const Plan& getPlan() const { return mPlan; }
176 
177     size_t getHitCount(Type type) const {
178         if (type == Type::Total) {
179             return getHitCount(Type::Exact) + getHitCount(Type::Approximate);
180         }
181         return getStatsForType(type).hitCount;
182     }
183 
184     size_t getMissCount(Type type) const {
185         if (type == Type::Total) {
186             return getMissCount(Type::Exact) + getMissCount(Type::Approximate);
187         }
188         return getStatsForType(type).missCount;
189     }
190 
191     void recordHit(Type type) { ++getStatsForType(type).hitCount; }
192 
193     void recordMiss(Type type) { ++getStatsForType(type).missCount; }
194 
195     void dump(std::string&) const;
196 
197 private:
198     struct Stats {
199         void dump(std::string& result) const {
200             const size_t totalAttempts = hitCount + missCount;
201             base::StringAppendF(&result, "%.2f%% (%zd/%zd)", 100.0f * hitCount / totalAttempts,
202                                 hitCount, totalAttempts);
203         }
204 
205         size_t hitCount = 0;
206         size_t missCount = 0;
207     };
208 
209     const Stats& getStatsForType(Type type) const {
210         return (type == Type::Exact) ? mExactStats : mApproximateStats;
211     }
212 
213     Stats& getStatsForType(Type type) {
214         return const_cast<Stats&>(const_cast<const Prediction*>(this)->getStatsForType(type));
215     }
216 
217     LayerStack mExampleLayerStack;
218     Plan mPlan;
219 
220     Stats mExactStats;
221     Stats mApproximateStats;
222 };
223 
224 class Predictor {
225 public:
226     struct PredictedPlan {
227         NonBufferHash hash;
228         Plan plan;
229         Prediction::Type type;
230 
231         friend bool operator==(const PredictedPlan& lhs, const PredictedPlan& rhs) {
232             return lhs.hash == rhs.hash && lhs.plan == rhs.plan && lhs.type == rhs.type;
233         }
234     };
235 
236     // Retrieves the predicted plan based on a layer stack alongside its hash.
237     //
238     // If the exact layer stack has previously been seen by the predictor, then report the plan used
239     // for that layer stack.
240     //
241     // Otherwise, try to match to the best approximate stack to retireve the most likely plan.
242     std::optional<PredictedPlan> getPredictedPlan(const std::vector<const LayerState*>& layers,
243                                                   NonBufferHash hash) const;
244 
245     // Records a comparison between the predicted plan and the resulting plan, alongside the layer
246     // stack we used.
247     //
248     // This method is intended to help with scoring how effective the prediction engine is.
249     void recordResult(std::optional<PredictedPlan> predictedPlan, NonBufferHash flattenedHash,
250                       const std::vector<const LayerState*>&, bool hasSkippedLayers, Plan result);
251 
252     void dump(std::string&) const;
253 
254     void compareLayerStacks(NonBufferHash leftHash, NonBufferHash rightHash, std::string&) const;
255     void describeLayerStack(NonBufferHash, std::string&) const;
256     void listSimilarStacks(Plan, std::string&) const;
257 
258 private:
259     // Retrieves a prediction from either the main prediction list or from the candidate list
260     const Prediction& getPrediction(NonBufferHash) const;
261     Prediction& getPrediction(NonBufferHash);
262 
263     std::optional<Plan> getExactMatch(NonBufferHash) const;
264     std::optional<NonBufferHash> getApproximateMatch(
265             const std::vector<const LayerState*>& layers) const;
266 
267     void promoteIfCandidate(NonBufferHash);
268     void recordPredictedResult(PredictedPlan, const std::vector<const LayerState*>& layers,
269                                Plan result);
270     bool findSimilarPrediction(const std::vector<const LayerState*>& layers, Plan result);
271 
272     void dumpPredictionsByFrequency(std::string&) const;
273 
274     struct PromotionCandidate {
275         PromotionCandidate(NonBufferHash hash, Prediction&& prediction)
276               : hash(hash), prediction(std::move(prediction)) {}
277 
278         NonBufferHash hash;
279         Prediction prediction;
280     };
281 
282     static constexpr const size_t MAX_CANDIDATES = 4;
283     std::deque<PromotionCandidate> mCandidates;
284     decltype(mCandidates)::const_iterator getCandidateEntryByHash(NonBufferHash hash) const {
285         const auto candidateMatches = [&](const PromotionCandidate& candidate) {
286             return candidate.hash == hash;
287         };
288 
289         return std::find_if(mCandidates.cbegin(), mCandidates.cend(), candidateMatches);
290     }
291 
292     std::unordered_map<NonBufferHash, Prediction> mPredictions;
293     std::unordered_map<Plan, std::vector<NonBufferHash>> mSimilarStacks;
294 
295     struct ApproximateStack {
296         ApproximateStack(NonBufferHash hash, LayerStack::ApproximateMatch match)
297               : hash(hash), match(match) {}
298 
299         bool operator==(const ApproximateStack& other) const {
300             return hash == other.hash && match == other.match;
301         }
302 
303         NonBufferHash hash;
304         LayerStack::ApproximateMatch match;
305     };
306 
307     std::vector<ApproximateStack> mApproximateStacks;
308 
309     mutable size_t mExactHitCount = 0;
310     mutable size_t mApproximateHitCount = 0;
311     mutable size_t mMissCount = 0;
312 };
313 
314 // Defining PrintTo helps with Google Tests.
315 inline void PrintTo(Predictor::PredictedPlan plan, ::std::ostream* os) {
316     *os << "PredictedPlan {";
317     *os << "\n    .hash = " << plan.hash;
318     *os << "\n    .plan = " << plan.plan;
319     *os << "\n    .type = " << plan.type;
320     *os << "\n}";
321 }
322 
323 } // namespace android::compositionengine::impl::planner
324