Home | History | Annotate | Download | only in video_engine 
      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 
     25 namespace webrtc {
     26 
     27 // TODO(mflodman) Test different values for all of these to trigger correctly,
     28 // avoid fluctuations etc.
     29 namespace {
     30 const int64_t kProcessIntervalMs = 5000;
     31 
     32 // Weight factor to apply to the standard deviation.
     33 const float kWeightFactor = 0.997f;
     34 // Weight factor to apply to the average.
     35 const float kWeightFactorMean = 0.98f;
     36 
     37 // Delay between consecutive rampups. (Used for quick recovery.)
     38 const int kQuickRampUpDelayMs = 10 * 1000;
     39 // Delay between rampup attempts. Initially uses standard, scales up to max.
     40 const int kStandardRampUpDelayMs = 40 * 1000;
     41 const int kMaxRampUpDelayMs = 240 * 1000;
     42 // Expontential back-off factor, to prevent annoying up-down behaviour.
     43 const double kRampUpBackoffFactor = 2.0;
     44 
     45 // Max number of overuses detected before always applying the rampup delay.
     46 const int kMaxOverusesBeforeApplyRampupDelay = 4;
     47 
     48 // The maximum exponent to use in VCMExpFilter.
     49 const float kSampleDiffMs = 33.0f;
     50 const float kMaxExp = 7.0f;
     51 
     52 }  // namespace
     53 
     54 Statistics::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 
     62 void Statistics::SetOptions(const CpuOveruseOptions& options) {
     63   options_ = options;
     64 }
     65 
     66 void Statistics::Reset() {
     67   sum_ =  0.0;
     68   count_ = 0;
     69   filtered_variance_->Reset(kWeightFactor);
     70   filtered_variance_->Apply(1.0f, InitialVariance());
     71 }
     72 
     73 void 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 
     91 float Statistics::InitialMean() const {
     92   if (count_ == 0)
     93     return 0.0;
     94   return sum_ / count_;
     95 }
     96 
     97 float 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 
    104 float Statistics::Mean() const { return filtered_samples_->filtered(); }
    105 
    106 float Statistics::StdDev() const {
    107   return sqrt(std::max(filtered_variance_->filtered(), 0.0f));
    108 }
    109 
    110 uint64_t Statistics::Count() const { return count_; }
    111 
    112 
    113 // Class for calculating the average encode time.
    114 class 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.
    141 class 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.
    213 class 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.
    318 class 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 
    374 OveruseFrameDetector::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 
    395 OveruseFrameDetector::~OveruseFrameDetector() {
    396 }
    397 
    398 void OveruseFrameDetector::SetObserver(CpuOveruseObserver* observer) {
    399   CriticalSectionScoped cs(crit_.get());
    400   observer_ = observer;
    401 }
    402 
    403 void 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 
    416 int OveruseFrameDetector::CaptureQueueDelayMsPerS() const {
    417   CriticalSectionScoped cs(crit_.get());
    418   return capture_queue_delay_->delay_ms();
    419 }
    420 
    421 void 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 
    431 int32_t OveruseFrameDetector::TimeUntilNextProcess() {
    432   CriticalSectionScoped cs(crit_.get());
    433   return next_process_time_ - clock_->TimeInMilliseconds();
    434 }
    435 
    436 bool OveruseFrameDetector::FrameSizeChanged(int num_pixels) const {
    437   if (num_pixels != num_pixels_) {
    438     return true;
    439   }
    440   return false;
    441 }
    442 
    443 bool 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 
    450 void 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 
    460 void 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 
    477 void OveruseFrameDetector::FrameProcessingStarted() {
    478   CriticalSectionScoped cs(crit_.get());
    479   capture_queue_delay_->FrameProcessingStarted(clock_->TimeInMilliseconds());
    480 }
    481 
    482 void 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 
    494 int32_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 
    558 bool 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 
    582 bool 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