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 "rtc_base/rate_statistics.h"
12
13 #include <algorithm>
14 #include <limits>
15 #include <memory>
16
17 #include "rtc_base/checks.h"
18 #include "rtc_base/logging.h"
19 #include "rtc_base/numerics/safe_conversions.h"
20
21 namespace webrtc {
22
Bucket(int64_t timestamp)23 RateStatistics::Bucket::Bucket(int64_t timestamp)
24 : sum(0), num_samples(0), timestamp(timestamp) {}
25
RateStatistics(int64_t window_size_ms,float scale)26 RateStatistics::RateStatistics(int64_t window_size_ms, float scale)
27 : accumulated_count_(0),
28 first_timestamp_(-1),
29 num_samples_(0),
30 scale_(scale),
31 max_window_size_ms_(window_size_ms),
32 current_window_size_ms_(max_window_size_ms_) {}
33
RateStatistics(const RateStatistics & other)34 RateStatistics::RateStatistics(const RateStatistics& other)
35 : buckets_(other.buckets_),
36 accumulated_count_(other.accumulated_count_),
37 first_timestamp_(other.first_timestamp_),
38 overflow_(other.overflow_),
39 num_samples_(other.num_samples_),
40 scale_(other.scale_),
41 max_window_size_ms_(other.max_window_size_ms_),
42 current_window_size_ms_(other.current_window_size_ms_) {}
43
44 RateStatistics::RateStatistics(RateStatistics&& other) = default;
45
~RateStatistics()46 RateStatistics::~RateStatistics() {}
47
Reset()48 void RateStatistics::Reset() {
49 accumulated_count_ = 0;
50 overflow_ = false;
51 num_samples_ = 0;
52 first_timestamp_ = -1;
53 current_window_size_ms_ = max_window_size_ms_;
54 buckets_.clear();
55 }
56
Update(int64_t count,int64_t now_ms)57 void RateStatistics::Update(int64_t count, int64_t now_ms) {
58 RTC_DCHECK_GE(count, 0);
59
60 EraseOld(now_ms);
61 if (first_timestamp_ == -1) {
62 first_timestamp_ = now_ms;
63 }
64
65 if (buckets_.empty() || now_ms != buckets_.back().timestamp) {
66 if (!buckets_.empty() && now_ms < buckets_.back().timestamp) {
67 RTC_LOG(LS_WARNING) << "Timestamp " << now_ms
68 << " is before the last added "
69 "timestamp in the rate window: "
70 << buckets_.back().timestamp << ", aligning to that.";
71 now_ms = buckets_.back().timestamp;
72 }
73 buckets_.emplace_back(now_ms);
74 }
75 Bucket& last_bucket = buckets_.back();
76 last_bucket.sum += count;
77 ++last_bucket.num_samples;
78
79 if (std::numeric_limits<int64_t>::max() - accumulated_count_ > count) {
80 accumulated_count_ += count;
81 } else {
82 overflow_ = true;
83 }
84 ++num_samples_;
85 }
86
Rate(int64_t now_ms) const87 absl::optional<int64_t> RateStatistics::Rate(int64_t now_ms) const {
88 // Yeah, this const_cast ain't pretty, but the alternative is to declare most
89 // of the members as mutable...
90 const_cast<RateStatistics*>(this)->EraseOld(now_ms);
91
92 int active_window_size = 0;
93 if (first_timestamp_ != -1) {
94 if (first_timestamp_ <= now_ms - current_window_size_ms_) {
95 // Count window as full even if no data points currently in view, if the
96 // data stream started before the window.
97 active_window_size = current_window_size_ms_;
98 } else {
99 // Size of a single bucket is 1ms, so even if now_ms == first_timestmap_
100 // the window size should be 1.
101 active_window_size = now_ms - first_timestamp_ + 1;
102 }
103 }
104
105 // If window is a single bucket or there is only one sample in a data set that
106 // has not grown to the full window size, or if the accumulator has
107 // overflowed, treat this as rate unavailable.
108 if (num_samples_ == 0 || active_window_size <= 1 ||
109 (num_samples_ <= 1 &&
110 rtc::SafeLt(active_window_size, current_window_size_ms_)) ||
111 overflow_) {
112 return absl::nullopt;
113 }
114
115 float scale = static_cast<float>(scale_) / active_window_size;
116 float result = accumulated_count_ * scale + 0.5f;
117
118 // Better return unavailable rate than garbage value (undefined behavior).
119 if (result > static_cast<float>(std::numeric_limits<int64_t>::max())) {
120 return absl::nullopt;
121 }
122 return rtc::dchecked_cast<int64_t>(result);
123 }
124
EraseOld(int64_t now_ms)125 void RateStatistics::EraseOld(int64_t now_ms) {
126 // New oldest time that is included in data set.
127 const int64_t new_oldest_time = now_ms - current_window_size_ms_ + 1;
128
129 // Loop over buckets and remove too old data points.
130 while (!buckets_.empty() && buckets_.front().timestamp < new_oldest_time) {
131 const Bucket& oldest_bucket = buckets_.front();
132 RTC_DCHECK_GE(accumulated_count_, oldest_bucket.sum);
133 RTC_DCHECK_GE(num_samples_, oldest_bucket.num_samples);
134 accumulated_count_ -= oldest_bucket.sum;
135 num_samples_ -= oldest_bucket.num_samples;
136 buckets_.pop_front();
137 // This does not clear overflow_ even when counter is empty.
138 // TODO(https://bugs.webrtc.org/11247): Consider if overflow_ can be reset.
139 }
140 }
141
SetWindowSize(int64_t window_size_ms,int64_t now_ms)142 bool RateStatistics::SetWindowSize(int64_t window_size_ms, int64_t now_ms) {
143 if (window_size_ms <= 0 || window_size_ms > max_window_size_ms_)
144 return false;
145 if (first_timestamp_ != -1) {
146 // If the window changes (e.g. decreases - removing data point, then
147 // increases again) we need to update the first timestamp mark as
148 // otherwise it indicates the window coveres a region of zeros, suddenly
149 // under-estimating the rate.
150 first_timestamp_ = std::max(first_timestamp_, now_ms - window_size_ms + 1);
151 }
152 current_window_size_ms_ = window_size_ms;
153 EraseOld(now_ms);
154 return true;
155 }
156
157 } // namespace webrtc
158