1/*
2 *  Copyright (c) 2013 The WebRTC project authors. All Rights Reserved.
3 *
4 *  Use of this source code is governed by a BSD-style license
5 *  that can be found in the LICENSE file in the root of the source
6 *  tree. An additional intellectual property rights grant can be found
7 *  in the file PATENTS.  All contributing project authors may
8 *  be found in the AUTHORS file in the root of the source tree.
9 */
10
11#include "webrtc/video_engine/overuse_frame_detector.h"
12
13#include <assert.h>
14#include <math.h>
15
16#include <algorithm>
17#include <list>
18#include <map>
19
20#include "webrtc/base/exp_filter.h"
21#include "webrtc/system_wrappers/interface/clock.h"
22#include "webrtc/system_wrappers/interface/critical_section_wrapper.h"
23#include "webrtc/system_wrappers/interface/logging.h"
24
25namespace webrtc {
26
27// TODO(mflodman) Test different values for all of these to trigger correctly,
28// avoid fluctuations etc.
29namespace {
30const int64_t kProcessIntervalMs = 5000;
31
32// Weight factor to apply to the standard deviation.
33const float kWeightFactor = 0.997f;
34// Weight factor to apply to the average.
35const float kWeightFactorMean = 0.98f;
36
37// Delay between consecutive rampups. (Used for quick recovery.)
38const int kQuickRampUpDelayMs = 10 * 1000;
39// Delay between rampup attempts. Initially uses standard, scales up to max.
40const int kStandardRampUpDelayMs = 40 * 1000;
41const int kMaxRampUpDelayMs = 240 * 1000;
42// Expontential back-off factor, to prevent annoying up-down behaviour.
43const double kRampUpBackoffFactor = 2.0;
44
45// Max number of overuses detected before always applying the rampup delay.
46const int kMaxOverusesBeforeApplyRampupDelay = 4;
47
48// The maximum exponent to use in VCMExpFilter.
49const float kSampleDiffMs = 33.0f;
50const float kMaxExp = 7.0f;
51
52}  // namespace
53
54Statistics::Statistics() :
55    sum_(0.0),
56    count_(0),
57    filtered_samples_(new rtc::ExpFilter(kWeightFactorMean)),
58    filtered_variance_(new rtc::ExpFilter(kWeightFactor)) {
59  Reset();
60}
61
62void Statistics::SetOptions(const CpuOveruseOptions& options) {
63  options_ = options;
64}
65
66void Statistics::Reset() {
67  sum_ =  0.0;
68  count_ = 0;
69  filtered_variance_->Reset(kWeightFactor);
70  filtered_variance_->Apply(1.0f, InitialVariance());
71}
72
73void Statistics::AddSample(float sample_ms) {
74  sum_ += sample_ms;
75  ++count_;
76
77  if (count_ < static_cast<uint32_t>(options_.min_frame_samples)) {
78    // Initialize filtered samples.
79    filtered_samples_->Reset(kWeightFactorMean);
80    filtered_samples_->Apply(1.0f, InitialMean());
81    return;
82  }
83
84  float exp = sample_ms / kSampleDiffMs;
85  exp = std::min(exp, kMaxExp);
86  filtered_samples_->Apply(exp, sample_ms);
87  filtered_variance_->Apply(exp, (sample_ms - filtered_samples_->filtered()) *
88                                 (sample_ms - filtered_samples_->filtered()));
89}
90
91float Statistics::InitialMean() const {
92  if (count_ == 0)
93    return 0.0;
94  return sum_ / count_;
95}
96
97float Statistics::InitialVariance() const {
98  // Start in between the underuse and overuse threshold.
99  float average_stddev = (options_.low_capture_jitter_threshold_ms +
100                          options_.high_capture_jitter_threshold_ms) / 2.0f;
101  return average_stddev * average_stddev;
102}
103
104float Statistics::Mean() const { return filtered_samples_->filtered(); }
105
106float Statistics::StdDev() const {
107  return sqrt(std::max(filtered_variance_->filtered(), 0.0f));
108}
109
110uint64_t Statistics::Count() const { return count_; }
111
112
113// Class for calculating the average encode time.
114class OveruseFrameDetector::EncodeTimeAvg {
115 public:
116  EncodeTimeAvg()
117      : kWeightFactor(0.5f),
118        kInitialAvgEncodeTimeMs(5.0f),
119        filtered_encode_time_ms_(new rtc::ExpFilter(kWeightFactor)) {
120    filtered_encode_time_ms_->Apply(1.0f, kInitialAvgEncodeTimeMs);
121  }
122  ~EncodeTimeAvg() {}
123
124  void AddEncodeSample(float encode_time_ms, int64_t diff_last_sample_ms) {
125    float exp =  diff_last_sample_ms / kSampleDiffMs;
126    exp = std::min(exp, kMaxExp);
127    filtered_encode_time_ms_->Apply(exp, encode_time_ms);
128  }
129
130  int Value() const {
131    return static_cast<int>(filtered_encode_time_ms_->filtered() + 0.5);
132  }
133
134 private:
135  const float kWeightFactor;
136  const float kInitialAvgEncodeTimeMs;
137  scoped_ptr<rtc::ExpFilter> filtered_encode_time_ms_;
138};
139
140// Class for calculating the encode usage.
141class OveruseFrameDetector::EncodeUsage {
142 public:
143  EncodeUsage()
144      : kWeightFactorFrameDiff(0.998f),
145        kWeightFactorEncodeTime(0.995f),
146        kInitialSampleDiffMs(40.0f),
147        kMaxSampleDiffMs(45.0f),
148        count_(0),
149        filtered_encode_time_ms_(new rtc::ExpFilter(kWeightFactorEncodeTime)),
150        filtered_frame_diff_ms_(new rtc::ExpFilter(kWeightFactorFrameDiff)) {
151    Reset();
152  }
153  ~EncodeUsage() {}
154
155  void SetOptions(const CpuOveruseOptions& options) {
156    options_ = options;
157  }
158
159  void Reset() {
160    count_ = 0;
161    filtered_frame_diff_ms_->Reset(kWeightFactorFrameDiff);
162    filtered_frame_diff_ms_->Apply(1.0f, kInitialSampleDiffMs);
163    filtered_encode_time_ms_->Reset(kWeightFactorEncodeTime);
164    filtered_encode_time_ms_->Apply(1.0f, InitialEncodeTimeMs());
165  }
166
167  void AddSample(float sample_ms) {
168    float exp = sample_ms / kSampleDiffMs;
169    exp = std::min(exp, kMaxExp);
170    filtered_frame_diff_ms_->Apply(exp, sample_ms);
171  }
172
173  void AddEncodeSample(float encode_time_ms, int64_t diff_last_sample_ms) {
174    ++count_;
175    float exp = diff_last_sample_ms / kSampleDiffMs;
176    exp = std::min(exp, kMaxExp);
177    filtered_encode_time_ms_->Apply(exp, encode_time_ms);
178  }
179
180  int Value() const {
181    if (count_ < static_cast<uint32_t>(options_.min_frame_samples)) {
182      return static_cast<int>(InitialUsageInPercent() + 0.5f);
183    }
184    float frame_diff_ms = std::max(filtered_frame_diff_ms_->filtered(), 1.0f);
185    frame_diff_ms = std::min(frame_diff_ms, kMaxSampleDiffMs);
186    float encode_usage_percent =
187        100.0f * filtered_encode_time_ms_->filtered() / frame_diff_ms;
188    return static_cast<int>(encode_usage_percent + 0.5);
189  }
190
191 private:
192  float InitialUsageInPercent() const {
193    // Start in between the underuse and overuse threshold.
194    return (options_.low_encode_usage_threshold_percent +
195            options_.high_encode_usage_threshold_percent) / 2.0f;
196  }
197
198  float InitialEncodeTimeMs() const {
199    return InitialUsageInPercent() * kInitialSampleDiffMs / 100;
200  }
201
202  const float kWeightFactorFrameDiff;
203  const float kWeightFactorEncodeTime;
204  const float kInitialSampleDiffMs;
205  const float kMaxSampleDiffMs;
206  uint64_t count_;
207  CpuOveruseOptions options_;
208  scoped_ptr<rtc::ExpFilter> filtered_encode_time_ms_;
209  scoped_ptr<rtc::ExpFilter> filtered_frame_diff_ms_;
210};
211
212// Class for calculating the relative standard deviation of encode times.
213class OveruseFrameDetector::EncodeTimeRsd {
214 public:
215  EncodeTimeRsd(Clock* clock)
216      : kWeightFactor(0.6f),
217        count_(0),
218        filtered_rsd_(new rtc::ExpFilter(kWeightFactor)),
219        hist_samples_(0),
220        hist_sum_(0.0f),
221        last_process_time_ms_(clock->TimeInMilliseconds()) {
222    Reset();
223  }
224  ~EncodeTimeRsd() {}
225
226  void SetOptions(const CpuOveruseOptions& options) {
227    options_ = options;
228  }
229
230  void Reset() {
231    count_ = 0;
232    filtered_rsd_->Reset(kWeightFactor);
233    filtered_rsd_->Apply(1.0f, InitialValue());
234    hist_.clear();
235    hist_samples_ = 0;
236    hist_sum_ = 0.0f;
237  }
238
239  void AddEncodeSample(float encode_time_ms) {
240    int bin = static_cast<int>(encode_time_ms + 0.5f);
241    if (bin <= 0) {
242      // The frame was probably not encoded, skip possible dropped frame.
243      return;
244    }
245    ++count_;
246    ++hist_[bin];
247    ++hist_samples_;
248    hist_sum_ += bin;
249  }
250
251  void Process(int64_t now) {
252    if (count_ < static_cast<uint32_t>(options_.min_frame_samples)) {
253      // Have not received min number of frames since last reset.
254      return;
255    }
256    const int kMinHistSamples = 20;
257    if (hist_samples_ < kMinHistSamples) {
258      return;
259    }
260    const int64_t kMinDiffSinceLastProcessMs = 1000;
261    int64_t diff_last_process_ms = now - last_process_time_ms_;
262    if (now - last_process_time_ms_ <= kMinDiffSinceLastProcessMs) {
263      return;
264    }
265    last_process_time_ms_ = now;
266
267    // Calculate variance (using samples above the mean).
268    // Checks for a larger encode time of some frames while there is a small
269    // increase in the average time.
270    int mean = hist_sum_ / hist_samples_;
271    float variance = 0.0f;
272    int total_count = 0;
273    for (std::map<int,int>::iterator it = hist_.begin();
274         it != hist_.end(); ++it) {
275      int time = it->first;
276      int count = it->second;
277      if (time > mean) {
278        total_count += count;
279        for (int i = 0; i < count; ++i) {
280          variance += ((time - mean) * (time - mean));
281        }
282      }
283    }
284    variance /= std::max(total_count, 1);
285    float cov = sqrt(variance) / mean;
286
287    hist_.clear();
288    hist_samples_ = 0;
289    hist_sum_ = 0.0f;
290
291    float exp = static_cast<float>(diff_last_process_ms) / kProcessIntervalMs;
292    exp = std::min(exp, kMaxExp);
293    filtered_rsd_->Apply(exp, 100.0f * cov);
294  }
295
296  int Value() const {
297    return static_cast<int>(filtered_rsd_->filtered() + 0.5);
298  }
299
300 private:
301  float InitialValue() const {
302    // Start in between the underuse and overuse threshold.
303    return std::max(((options_.low_encode_time_rsd_threshold +
304                      options_.high_encode_time_rsd_threshold) / 2.0f), 0.0f);
305  }
306
307  const float kWeightFactor;
308  uint32_t count_;  // Number of encode samples since last reset.
309  CpuOveruseOptions options_;
310  scoped_ptr<rtc::ExpFilter> filtered_rsd_;
311  int hist_samples_;
312  float hist_sum_;
313  std::map<int,int> hist_;  // Histogram of encode time of frames.
314  int64_t last_process_time_ms_;
315};
316
317// Class for calculating the capture queue delay change.
318class OveruseFrameDetector::CaptureQueueDelay {
319 public:
320  CaptureQueueDelay()
321      : kWeightFactor(0.5f),
322        delay_ms_(0),
323        filtered_delay_ms_per_s_(new rtc::ExpFilter(kWeightFactor)) {
324    filtered_delay_ms_per_s_->Apply(1.0f, 0.0f);
325  }
326  ~CaptureQueueDelay() {}
327
328  void FrameCaptured(int64_t now) {
329    const size_t kMaxSize = 200;
330    if (frames_.size() > kMaxSize) {
331      frames_.pop_front();
332    }
333    frames_.push_back(now);
334  }
335
336  void FrameProcessingStarted(int64_t now) {
337    if (frames_.empty()) {
338      return;
339    }
340    delay_ms_ = now - frames_.front();
341    frames_.pop_front();
342  }
343
344  void CalculateDelayChange(int64_t diff_last_sample_ms) {
345    if (diff_last_sample_ms <= 0) {
346      return;
347    }
348    float exp = static_cast<float>(diff_last_sample_ms) / kProcessIntervalMs;
349    exp = std::min(exp, kMaxExp);
350    filtered_delay_ms_per_s_->Apply(exp,
351                                    delay_ms_ * 1000.0f / diff_last_sample_ms);
352    ClearFrames();
353  }
354
355  void ClearFrames() {
356    frames_.clear();
357  }
358
359  int delay_ms() const {
360    return delay_ms_;
361  }
362
363  int Value() const {
364    return static_cast<int>(filtered_delay_ms_per_s_->filtered() + 0.5);
365  }
366
367 private:
368  const float kWeightFactor;
369  std::list<int64_t> frames_;
370  int delay_ms_;
371  scoped_ptr<rtc::ExpFilter> filtered_delay_ms_per_s_;
372};
373
374OveruseFrameDetector::OveruseFrameDetector(Clock* clock)
375    : crit_(CriticalSectionWrapper::CreateCriticalSection()),
376      observer_(NULL),
377      clock_(clock),
378      next_process_time_(clock_->TimeInMilliseconds()),
379      num_process_times_(0),
380      last_capture_time_(0),
381      last_overuse_time_(0),
382      checks_above_threshold_(0),
383      num_overuse_detections_(0),
384      last_rampup_time_(0),
385      in_quick_rampup_(false),
386      current_rampup_delay_ms_(kStandardRampUpDelayMs),
387      num_pixels_(0),
388      last_encode_sample_ms_(0),
389      encode_time_(new EncodeTimeAvg()),
390      encode_rsd_(new EncodeTimeRsd(clock)),
391      encode_usage_(new EncodeUsage()),
392      capture_queue_delay_(new CaptureQueueDelay()) {
393}
394
395OveruseFrameDetector::~OveruseFrameDetector() {
396}
397
398void OveruseFrameDetector::SetObserver(CpuOveruseObserver* observer) {
399  CriticalSectionScoped cs(crit_.get());
400  observer_ = observer;
401}
402
403void OveruseFrameDetector::SetOptions(const CpuOveruseOptions& options) {
404  assert(options.min_frame_samples > 0);
405  CriticalSectionScoped cs(crit_.get());
406  if (options_.Equals(options)) {
407    return;
408  }
409  options_ = options;
410  capture_deltas_.SetOptions(options);
411  encode_usage_->SetOptions(options);
412  encode_rsd_->SetOptions(options);
413  ResetAll(num_pixels_);
414}
415
416int OveruseFrameDetector::CaptureQueueDelayMsPerS() const {
417  CriticalSectionScoped cs(crit_.get());
418  return capture_queue_delay_->delay_ms();
419}
420
421void OveruseFrameDetector::GetCpuOveruseMetrics(
422    CpuOveruseMetrics* metrics) const {
423  CriticalSectionScoped cs(crit_.get());
424  metrics->capture_jitter_ms = static_cast<int>(capture_deltas_.StdDev() + 0.5);
425  metrics->avg_encode_time_ms = encode_time_->Value();
426  metrics->encode_rsd = encode_rsd_->Value();
427  metrics->encode_usage_percent = encode_usage_->Value();
428  metrics->capture_queue_delay_ms_per_s = capture_queue_delay_->Value();
429}
430
431int32_t OveruseFrameDetector::TimeUntilNextProcess() {
432  CriticalSectionScoped cs(crit_.get());
433  return next_process_time_ - clock_->TimeInMilliseconds();
434}
435
436bool OveruseFrameDetector::FrameSizeChanged(int num_pixels) const {
437  if (num_pixels != num_pixels_) {
438    return true;
439  }
440  return false;
441}
442
443bool OveruseFrameDetector::FrameTimeoutDetected(int64_t now) const {
444  if (last_capture_time_ == 0) {
445    return false;
446  }
447  return (now - last_capture_time_) > options_.frame_timeout_interval_ms;
448}
449
450void OveruseFrameDetector::ResetAll(int num_pixels) {
451  num_pixels_ = num_pixels;
452  capture_deltas_.Reset();
453  encode_usage_->Reset();
454  encode_rsd_->Reset();
455  capture_queue_delay_->ClearFrames();
456  last_capture_time_ = 0;
457  num_process_times_ = 0;
458}
459
460void OveruseFrameDetector::FrameCaptured(int width, int height) {
461  CriticalSectionScoped cs(crit_.get());
462
463  int64_t now = clock_->TimeInMilliseconds();
464  if (FrameSizeChanged(width * height) || FrameTimeoutDetected(now)) {
465    ResetAll(width * height);
466  }
467
468  if (last_capture_time_ != 0) {
469    capture_deltas_.AddSample(now - last_capture_time_);
470    encode_usage_->AddSample(now - last_capture_time_);
471  }
472  last_capture_time_ = now;
473
474  capture_queue_delay_->FrameCaptured(now);
475}
476
477void OveruseFrameDetector::FrameProcessingStarted() {
478  CriticalSectionScoped cs(crit_.get());
479  capture_queue_delay_->FrameProcessingStarted(clock_->TimeInMilliseconds());
480}
481
482void OveruseFrameDetector::FrameEncoded(int encode_time_ms) {
483  CriticalSectionScoped cs(crit_.get());
484  int64_t time = clock_->TimeInMilliseconds();
485  if (last_encode_sample_ms_ != 0) {
486    int64_t diff_ms = time - last_encode_sample_ms_;
487    encode_time_->AddEncodeSample(encode_time_ms, diff_ms);
488    encode_usage_->AddEncodeSample(encode_time_ms, diff_ms);
489    encode_rsd_->AddEncodeSample(encode_time_ms);
490  }
491  last_encode_sample_ms_ = time;
492}
493
494int32_t OveruseFrameDetector::Process() {
495  CriticalSectionScoped cs(crit_.get());
496
497  int64_t now = clock_->TimeInMilliseconds();
498
499  // Used to protect against Process() being called too often.
500  if (now < next_process_time_)
501    return 0;
502
503  int64_t diff_ms = now - next_process_time_ + kProcessIntervalMs;
504  next_process_time_ = now + kProcessIntervalMs;
505  ++num_process_times_;
506
507  encode_rsd_->Process(now);
508  capture_queue_delay_->CalculateDelayChange(diff_ms);
509
510  if (num_process_times_ <= options_.min_process_count) {
511    return 0;
512  }
513
514  if (IsOverusing()) {
515    // If the last thing we did was going up, and now have to back down, we need
516    // to check if this peak was short. If so we should back off to avoid going
517    // back and forth between this load, the system doesn't seem to handle it.
518    bool check_for_backoff = last_rampup_time_ > last_overuse_time_;
519    if (check_for_backoff) {
520      if (now - last_rampup_time_ < kStandardRampUpDelayMs ||
521          num_overuse_detections_ > kMaxOverusesBeforeApplyRampupDelay) {
522        // Going up was not ok for very long, back off.
523        current_rampup_delay_ms_ *= kRampUpBackoffFactor;
524        if (current_rampup_delay_ms_ > kMaxRampUpDelayMs)
525          current_rampup_delay_ms_ = kMaxRampUpDelayMs;
526      } else {
527        // Not currently backing off, reset rampup delay.
528        current_rampup_delay_ms_ = kStandardRampUpDelayMs;
529      }
530    }
531
532    last_overuse_time_ = now;
533    in_quick_rampup_ = false;
534    checks_above_threshold_ = 0;
535    ++num_overuse_detections_;
536
537    if (observer_ != NULL)
538      observer_->OveruseDetected();
539  } else if (IsUnderusing(now)) {
540    last_rampup_time_ = now;
541    in_quick_rampup_ = true;
542
543    if (observer_ != NULL)
544      observer_->NormalUsage();
545  }
546
547  int rampup_delay =
548      in_quick_rampup_ ? kQuickRampUpDelayMs : current_rampup_delay_ms_;
549  LOG(LS_VERBOSE) << " Frame stats: capture avg: " << capture_deltas_.Mean()
550                  << " capture stddev " << capture_deltas_.StdDev()
551                  << " encode usage " << encode_usage_->Value()
552                  << " encode rsd " << encode_rsd_->Value()
553                  << " overuse detections " << num_overuse_detections_
554                  << " rampup delay " << rampup_delay;
555  return 0;
556}
557
558bool OveruseFrameDetector::IsOverusing() {
559  bool overusing = false;
560  if (options_.enable_capture_jitter_method) {
561    overusing = capture_deltas_.StdDev() >=
562        options_.high_capture_jitter_threshold_ms;
563  } else if (options_.enable_encode_usage_method) {
564    bool encode_usage_overuse =
565        encode_usage_->Value() >= options_.high_encode_usage_threshold_percent;
566    bool encode_rsd_overuse = false;
567    if (options_.high_encode_time_rsd_threshold > 0) {
568      encode_rsd_overuse =
569          (encode_rsd_->Value() >= options_.high_encode_time_rsd_threshold);
570    }
571    overusing = encode_usage_overuse || encode_rsd_overuse;
572  }
573
574  if (overusing) {
575    ++checks_above_threshold_;
576  } else {
577    checks_above_threshold_ = 0;
578  }
579  return checks_above_threshold_ >= options_.high_threshold_consecutive_count;
580}
581
582bool OveruseFrameDetector::IsUnderusing(int64_t time_now) {
583  int delay = in_quick_rampup_ ? kQuickRampUpDelayMs : current_rampup_delay_ms_;
584  if (time_now < last_rampup_time_ + delay)
585    return false;
586
587  bool underusing = false;
588  if (options_.enable_capture_jitter_method) {
589    underusing = capture_deltas_.StdDev() <
590        options_.low_capture_jitter_threshold_ms;
591  } else if (options_.enable_encode_usage_method) {
592    bool encode_usage_underuse =
593        encode_usage_->Value() < options_.low_encode_usage_threshold_percent;
594    bool encode_rsd_underuse = true;
595    if (options_.low_encode_time_rsd_threshold > 0) {
596      encode_rsd_underuse =
597          (encode_rsd_->Value() < options_.low_encode_time_rsd_threshold);
598    }
599    underusing = encode_usage_underuse && encode_rsd_underuse;
600  }
601  return underusing;
602}
603}  // namespace webrtc
604