Home | History | Annotate | Download | only in base 
      1 /*
      2  *  Copyright 2015 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/base/ratetracker.h"
     12 
     13 #include <stddef.h>
     14 
     15 #include <algorithm>
     16 
     17 #include "webrtc/base/checks.h"
     18 #include "webrtc/base/timeutils.h"
     19 
     20 namespace rtc {
     21 
     22 RateTracker::RateTracker(uint32_t bucket_milliseconds, size_t bucket_count)
     23     : bucket_milliseconds_(bucket_milliseconds),
     24       bucket_count_(bucket_count),
     25       sample_buckets_(new size_t[bucket_count + 1]),
     26       total_sample_count_(0u),
     27       bucket_start_time_milliseconds_(~0u) {
     28   RTC_CHECK(bucket_milliseconds > 0u);
     29   RTC_CHECK(bucket_count > 0u);
     30 }
     31 
     32 RateTracker::~RateTracker() {
     33   delete[] sample_buckets_;
     34 }
     35 
     36 double RateTracker::ComputeRateForInterval(
     37     uint32_t interval_milliseconds) const {
     38   if (bucket_start_time_milliseconds_ == ~0u) {
     39     return 0.0;
     40   }
     41   uint32_t current_time = Time();
     42   // Calculate which buckets to sum up given the current time.  If the time
     43   // has passed to a new bucket then we have to skip some of the oldest buckets.
     44   uint32_t available_interval_milliseconds = std::min<uint32_t>(
     45       interval_milliseconds,
     46       bucket_milliseconds_ * static_cast<uint32_t>(bucket_count_));
     47   // number of old buckets (i.e. after the current bucket in the ring buffer)
     48   // that are expired given our current time interval.
     49   size_t buckets_to_skip;
     50   // Number of milliseconds of the first bucket that are not a portion of the
     51   // current interval.
     52   uint32_t milliseconds_to_skip;
     53   if (current_time >
     54       initialization_time_milliseconds_ + available_interval_milliseconds) {
     55     uint32_t time_to_skip =
     56         current_time - bucket_start_time_milliseconds_ +
     57         static_cast<uint32_t>(bucket_count_) * bucket_milliseconds_ -
     58         available_interval_milliseconds;
     59     buckets_to_skip = time_to_skip / bucket_milliseconds_;
     60     milliseconds_to_skip = time_to_skip % bucket_milliseconds_;
     61   } else {
     62     buckets_to_skip = bucket_count_ - current_bucket_;
     63     milliseconds_to_skip = 0u;
     64     available_interval_milliseconds =
     65         TimeDiff(current_time, initialization_time_milliseconds_);
     66   }
     67   // If we're skipping all buckets that means that there have been no samples
     68   // within the sampling interval so report 0.
     69   if (buckets_to_skip > bucket_count_ ||
     70       available_interval_milliseconds == 0u) {
     71     return 0.0;
     72   }
     73   size_t start_bucket = NextBucketIndex(current_bucket_ + buckets_to_skip);
     74   // Only count a portion of the first bucket according to how much of the
     75   // first bucket is within the current interval.
     76   size_t total_samples = ((sample_buckets_[start_bucket] *
     77       (bucket_milliseconds_ - milliseconds_to_skip)) +
     78       (bucket_milliseconds_ >> 1)) /
     79       bucket_milliseconds_;
     80   // All other buckets in the interval are counted in their entirety.
     81   for (size_t i = NextBucketIndex(start_bucket);
     82       i != NextBucketIndex(current_bucket_);
     83       i = NextBucketIndex(i)) {
     84     total_samples += sample_buckets_[i];
     85   }
     86   // Convert to samples per second.
     87   return static_cast<double>(total_samples * 1000u) /
     88       static_cast<double>(available_interval_milliseconds);
     89 }
     90 
     91 double RateTracker::ComputeTotalRate() const {
     92   if (bucket_start_time_milliseconds_ == ~0u) {
     93     return 0.0;
     94   }
     95   uint32_t current_time = Time();
     96   if (TimeIsLaterOrEqual(current_time, initialization_time_milliseconds_)) {
     97     return 0.0;
     98   }
     99   return static_cast<double>(total_sample_count_ * 1000u) /
    100       static_cast<double>(
    101           TimeDiff(current_time, initialization_time_milliseconds_));
    102 }
    103 
    104 size_t RateTracker::TotalSampleCount() const {
    105   return total_sample_count_;
    106 }
    107 
    108 void RateTracker::AddSamples(size_t sample_count) {
    109   EnsureInitialized();
    110   uint32_t current_time = Time();
    111   // Advance the current bucket as needed for the current time, and reset
    112   // bucket counts as we advance.
    113   for (size_t i = 0u; i <= bucket_count_ &&
    114       current_time >= bucket_start_time_milliseconds_ + bucket_milliseconds_;
    115       ++i) {
    116     bucket_start_time_milliseconds_ += bucket_milliseconds_;
    117     current_bucket_ = NextBucketIndex(current_bucket_);
    118     sample_buckets_[current_bucket_] = 0u;
    119   }
    120   // Ensure that bucket_start_time_milliseconds_ is updated appropriately if
    121   // the entire buffer of samples has been expired.
    122   bucket_start_time_milliseconds_ += bucket_milliseconds_ *
    123       ((current_time - bucket_start_time_milliseconds_) / bucket_milliseconds_);
    124   // Add all samples in the bucket that includes the current time.
    125   sample_buckets_[current_bucket_] += sample_count;
    126   total_sample_count_ += sample_count;
    127 }
    128 
    129 uint32_t RateTracker::Time() const {
    130   return rtc::Time();
    131 }
    132 
    133 void RateTracker::EnsureInitialized() {
    134   if (bucket_start_time_milliseconds_ == ~0u) {
    135     initialization_time_milliseconds_ = Time();
    136     bucket_start_time_milliseconds_ = initialization_time_milliseconds_;
    137     current_bucket_ = 0u;
    138     // We only need to initialize the first bucket because we reset buckets when
    139     // current_bucket_ increments.
    140     sample_buckets_[current_bucket_] = 0u;
    141   }
    142 }
    143 
    144 size_t RateTracker::NextBucketIndex(size_t bucket_index) const {
    145   return (bucket_index + 1u) % (bucket_count_ + 1u);
    146 }
    147 
    148 }  // namespace rtc
    149