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