1 /*
2 * Copyright 2019 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 // TODO(b/129481165): remove the #pragma below and fix conversion issues
18 #pragma clang diagnostic push
19 #pragma clang diagnostic ignored "-Wconversion"
20
21 #define ATRACE_TAG ATRACE_TAG_GRAPHICS
22 //#define LOG_NDEBUG 0
23 #include "VSyncPredictor.h"
24 #include <android-base/logging.h>
25 #include <android-base/stringprintf.h>
26 #include <cutils/compiler.h>
27 #include <cutils/properties.h>
28 #include <utils/Log.h>
29 #include <utils/Trace.h>
30 #include <algorithm>
31 #include <chrono>
32 #include <sstream>
33
34 namespace android::scheduler {
35 using base::StringAppendF;
36
37 static auto constexpr kMaxPercent = 100u;
38
39 VSyncPredictor::~VSyncPredictor() = default;
40
VSyncPredictor(nsecs_t idealPeriod,size_t historySize,size_t minimumSamplesForPrediction,uint32_t outlierTolerancePercent)41 VSyncPredictor::VSyncPredictor(nsecs_t idealPeriod, size_t historySize,
42 size_t minimumSamplesForPrediction, uint32_t outlierTolerancePercent)
43 : mTraceOn(property_get_bool("debug.sf.vsp_trace", true)),
44 kHistorySize(historySize),
45 kMinimumSamplesForPrediction(minimumSamplesForPrediction),
46 kOutlierTolerancePercent(std::min(outlierTolerancePercent, kMaxPercent)),
47 mIdealPeriod(idealPeriod) {
48 resetModel();
49 }
50
traceInt64If(const char * name,int64_t value) const51 inline void VSyncPredictor::traceInt64If(const char* name, int64_t value) const {
52 if (CC_UNLIKELY(mTraceOn)) {
53 ATRACE_INT64(name, value);
54 }
55 }
56
next(int i) const57 inline size_t VSyncPredictor::next(int i) const {
58 return (i + 1) % mTimestamps.size();
59 }
60
validate(nsecs_t timestamp) const61 bool VSyncPredictor::validate(nsecs_t timestamp) const {
62 if (mLastTimestampIndex < 0 || mTimestamps.empty()) {
63 return true;
64 }
65
66 auto const aValidTimestamp = mTimestamps[mLastTimestampIndex];
67 auto const percent = (timestamp - aValidTimestamp) % mIdealPeriod * kMaxPercent / mIdealPeriod;
68 return percent < kOutlierTolerancePercent || percent > (kMaxPercent - kOutlierTolerancePercent);
69 }
70
currentPeriod() const71 nsecs_t VSyncPredictor::currentPeriod() const {
72 std::lock_guard<std::mutex> lk(mMutex);
73 return std::get<0>(mRateMap.find(mIdealPeriod)->second);
74 }
75
addVsyncTimestamp(nsecs_t timestamp)76 bool VSyncPredictor::addVsyncTimestamp(nsecs_t timestamp) {
77 std::lock_guard<std::mutex> lk(mMutex);
78
79 if (!validate(timestamp)) {
80 // VSR could elect to ignore the incongruent timestamp or resetModel(). If ts is ignored,
81 // don't insert this ts into mTimestamps ringbuffer.
82 if (!mTimestamps.empty()) {
83 mKnownTimestamp =
84 std::max(timestamp, *std::max_element(mTimestamps.begin(), mTimestamps.end()));
85 } else {
86 mKnownTimestamp = timestamp;
87 }
88 return false;
89 }
90
91 if (mTimestamps.size() != kHistorySize) {
92 mTimestamps.push_back(timestamp);
93 mLastTimestampIndex = next(mLastTimestampIndex);
94 } else {
95 mLastTimestampIndex = next(mLastTimestampIndex);
96 mTimestamps[mLastTimestampIndex] = timestamp;
97 }
98
99 if (mTimestamps.size() < kMinimumSamplesForPrediction) {
100 mRateMap[mIdealPeriod] = {mIdealPeriod, 0};
101 return true;
102 }
103
104 // This is a 'simple linear regression' calculation of Y over X, with Y being the
105 // vsync timestamps, and X being the ordinal of vsync count.
106 // The calculated slope is the vsync period.
107 // Formula for reference:
108 // Sigma_i: means sum over all timestamps.
109 // mean(variable): statistical mean of variable.
110 // X: snapped ordinal of the timestamp
111 // Y: vsync timestamp
112 //
113 // Sigma_i( (X_i - mean(X)) * (Y_i - mean(Y) )
114 // slope = -------------------------------------------
115 // Sigma_i ( X_i - mean(X) ) ^ 2
116 //
117 // intercept = mean(Y) - slope * mean(X)
118 //
119 std::vector<nsecs_t> vsyncTS(mTimestamps.size());
120 std::vector<nsecs_t> ordinals(mTimestamps.size());
121
122 // normalizing to the oldest timestamp cuts down on error in calculating the intercept.
123 auto const oldest_ts = *std::min_element(mTimestamps.begin(), mTimestamps.end());
124 auto it = mRateMap.find(mIdealPeriod);
125 auto const currentPeriod = std::get<0>(it->second);
126 // TODO (b/144707443): its important that there's some precision in the mean of the ordinals
127 // for the intercept calculation, so scale the ordinals by 1000 to continue
128 // fixed point calculation. Explore expanding
129 // scheduler::utils::calculate_mean to have a fixed point fractional part.
130 static constexpr int64_t kScalingFactor = 1000;
131
132 for (auto i = 0u; i < mTimestamps.size(); i++) {
133 traceInt64If("VSP-ts", mTimestamps[i]);
134
135 vsyncTS[i] = mTimestamps[i] - oldest_ts;
136 ordinals[i] = ((vsyncTS[i] + (currentPeriod / 2)) / currentPeriod) * kScalingFactor;
137 }
138
139 auto meanTS = scheduler::calculate_mean(vsyncTS);
140 auto meanOrdinal = scheduler::calculate_mean(ordinals);
141 for (auto i = 0; i < vsyncTS.size(); i++) {
142 vsyncTS[i] -= meanTS;
143 ordinals[i] -= meanOrdinal;
144 }
145
146 auto top = 0ll;
147 auto bottom = 0ll;
148 for (auto i = 0; i < vsyncTS.size(); i++) {
149 top += vsyncTS[i] * ordinals[i];
150 bottom += ordinals[i] * ordinals[i];
151 }
152
153 if (CC_UNLIKELY(bottom == 0)) {
154 it->second = {mIdealPeriod, 0};
155 clearTimestamps();
156 return false;
157 }
158
159 nsecs_t const anticipatedPeriod = top * kScalingFactor / bottom;
160 nsecs_t const intercept = meanTS - (anticipatedPeriod * meanOrdinal / kScalingFactor);
161
162 auto const percent = std::abs(anticipatedPeriod - mIdealPeriod) * kMaxPercent / mIdealPeriod;
163 if (percent >= kOutlierTolerancePercent) {
164 it->second = {mIdealPeriod, 0};
165 clearTimestamps();
166 return false;
167 }
168
169 traceInt64If("VSP-period", anticipatedPeriod);
170 traceInt64If("VSP-intercept", intercept);
171
172 it->second = {anticipatedPeriod, intercept};
173
174 ALOGV("model update ts: %" PRId64 " slope: %" PRId64 " intercept: %" PRId64, timestamp,
175 anticipatedPeriod, intercept);
176 return true;
177 }
178
nextAnticipatedVSyncTimeFrom(nsecs_t timePoint) const179 nsecs_t VSyncPredictor::nextAnticipatedVSyncTimeFrom(nsecs_t timePoint) const {
180 std::lock_guard<std::mutex> lk(mMutex);
181
182 auto const [slope, intercept] = getVSyncPredictionModel(lk);
183
184 if (mTimestamps.empty()) {
185 traceInt64If("VSP-mode", 1);
186 auto const knownTimestamp = mKnownTimestamp ? *mKnownTimestamp : timePoint;
187 auto const numPeriodsOut = ((timePoint - knownTimestamp) / mIdealPeriod) + 1;
188 return knownTimestamp + numPeriodsOut * mIdealPeriod;
189 }
190
191 auto const oldest = *std::min_element(mTimestamps.begin(), mTimestamps.end());
192
193 // See b/145667109, the ordinal calculation must take into account the intercept.
194 auto const zeroPoint = oldest + intercept;
195 auto const ordinalRequest = (timePoint - zeroPoint + slope) / slope;
196 auto const prediction = (ordinalRequest * slope) + intercept + oldest;
197
198 traceInt64If("VSP-mode", 0);
199 traceInt64If("VSP-timePoint", timePoint);
200 traceInt64If("VSP-prediction", prediction);
201
202 auto const printer = [&, slope = slope, intercept = intercept] {
203 std::stringstream str;
204 str << "prediction made from: " << timePoint << "prediction: " << prediction << " (+"
205 << prediction - timePoint << ") slope: " << slope << " intercept: " << intercept
206 << "oldestTS: " << oldest << " ordinal: " << ordinalRequest;
207 return str.str();
208 };
209
210 ALOGV("%s", printer().c_str());
211 LOG_ALWAYS_FATAL_IF(prediction < timePoint, "VSyncPredictor: model miscalculation: %s",
212 printer().c_str());
213
214 return prediction;
215 }
216
getVSyncPredictionModel() const217 std::tuple<nsecs_t, nsecs_t> VSyncPredictor::getVSyncPredictionModel() const {
218 std::lock_guard<std::mutex> lk(mMutex);
219 return VSyncPredictor::getVSyncPredictionModel(lk);
220 }
221
getVSyncPredictionModel(std::lock_guard<std::mutex> const &) const222 std::tuple<nsecs_t, nsecs_t> VSyncPredictor::getVSyncPredictionModel(
223 std::lock_guard<std::mutex> const&) const {
224 return mRateMap.find(mIdealPeriod)->second;
225 }
226
setPeriod(nsecs_t period)227 void VSyncPredictor::setPeriod(nsecs_t period) {
228 ATRACE_CALL();
229
230 std::lock_guard<std::mutex> lk(mMutex);
231 static constexpr size_t kSizeLimit = 30;
232 if (CC_UNLIKELY(mRateMap.size() == kSizeLimit)) {
233 mRateMap.erase(mRateMap.begin());
234 }
235
236 mIdealPeriod = period;
237 if (mRateMap.find(period) == mRateMap.end()) {
238 mRateMap[mIdealPeriod] = {period, 0};
239 }
240
241 clearTimestamps();
242 }
243
clearTimestamps()244 void VSyncPredictor::clearTimestamps() {
245 if (!mTimestamps.empty()) {
246 auto const maxRb = *std::max_element(mTimestamps.begin(), mTimestamps.end());
247 if (mKnownTimestamp) {
248 mKnownTimestamp = std::max(*mKnownTimestamp, maxRb);
249 } else {
250 mKnownTimestamp = maxRb;
251 }
252
253 mTimestamps.clear();
254 mLastTimestampIndex = 0;
255 }
256 }
257
needsMoreSamples() const258 bool VSyncPredictor::needsMoreSamples() const {
259 std::lock_guard<std::mutex> lk(mMutex);
260 return mTimestamps.size() < kMinimumSamplesForPrediction;
261 }
262
resetModel()263 void VSyncPredictor::resetModel() {
264 std::lock_guard<std::mutex> lk(mMutex);
265 mRateMap[mIdealPeriod] = {mIdealPeriod, 0};
266 clearTimestamps();
267 }
268
dump(std::string & result) const269 void VSyncPredictor::dump(std::string& result) const {
270 std::lock_guard<std::mutex> lk(mMutex);
271 StringAppendF(&result, "\tmIdealPeriod=%.2f\n", mIdealPeriod / 1e6f);
272 StringAppendF(&result, "\tRefresh Rate Map:\n");
273 for (const auto& [idealPeriod, periodInterceptTuple] : mRateMap) {
274 StringAppendF(&result,
275 "\t\tFor ideal period %.2fms: period = %.2fms, intercept = %" PRId64 "\n",
276 idealPeriod / 1e6f, std::get<0>(periodInterceptTuple) / 1e6f,
277 std::get<1>(periodInterceptTuple));
278 }
279 }
280
281 } // namespace android::scheduler
282
283 // TODO(b/129481165): remove the #pragma below and fix conversion issues
284 #pragma clang diagnostic pop // ignored "-Wconversion"
285