1 // Copyright 2017 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifdef UNSAFE_BUFFERS_BUILD
6 // TODO(crbug.com/40284755): Remove this and spanify to fix the errors.
7 #pragma allow_unsafe_buffers
8 #endif
9
10 #include "net/nqe/observation_buffer.h"
11
12 #include <float.h>
13
14 #include <algorithm>
15 #include <utility>
16
17 #include "base/time/default_tick_clock.h"
18 #include "base/time/time.h"
19 #include "net/nqe/network_quality_estimator_params.h"
20 #include "net/nqe/weighted_observation.h"
21
22 namespace net::nqe::internal {
23
ObservationBuffer(const NetworkQualityEstimatorParams * params,const base::TickClock * tick_clock,double weight_multiplier_per_second,double weight_multiplier_per_signal_level)24 ObservationBuffer::ObservationBuffer(
25 const NetworkQualityEstimatorParams* params,
26 const base::TickClock* tick_clock,
27 double weight_multiplier_per_second,
28 double weight_multiplier_per_signal_level)
29 : params_(params),
30 weight_multiplier_per_second_(weight_multiplier_per_second),
31 weight_multiplier_per_signal_level_(weight_multiplier_per_signal_level),
32 tick_clock_(tick_clock) {
33 DCHECK_LT(0u, params_->observation_buffer_size());
34 DCHECK_LE(0.0, weight_multiplier_per_second_);
35 DCHECK_GE(1.0, weight_multiplier_per_second_);
36 DCHECK_LE(0.0, weight_multiplier_per_signal_level_);
37 DCHECK_GE(1.0, weight_multiplier_per_signal_level_);
38 DCHECK(params_);
39 DCHECK(tick_clock_);
40 }
41
ObservationBuffer(const ObservationBuffer & other)42 ObservationBuffer::ObservationBuffer(const ObservationBuffer& other)
43 : params_(other.params_),
44 weight_multiplier_per_second_(other.weight_multiplier_per_second_),
45 weight_multiplier_per_signal_level_(
46 other.weight_multiplier_per_signal_level_),
47 tick_clock_(other.tick_clock_) {
48 DCHECK(other.observations_.empty());
49 }
50
51 ObservationBuffer::~ObservationBuffer() = default;
52
AddObservation(const Observation & observation)53 std::optional<Observation> ObservationBuffer::AddObservation(
54 const Observation& observation) {
55 DCHECK_LE(observations_.size(), params_->observation_buffer_size());
56
57 // Observations must be in the non-decreasing order of the timestamps.
58 DCHECK(observations_.empty() ||
59 observation.timestamp() >= observations_.back().timestamp());
60
61 DCHECK(observation.signal_strength() == INT32_MIN ||
62 (observation.signal_strength() >= 0 &&
63 observation.signal_strength() <= 4));
64
65 std::optional<Observation> evicted_observation;
66 // Evict the oldest element if the buffer is already full.
67 if (observations_.size() == params_->observation_buffer_size()) {
68 evicted_observation = observations_.front();
69 observations_.pop_front();
70 }
71
72 observations_.push_back(observation);
73 DCHECK_LE(observations_.size(), params_->observation_buffer_size());
74 return evicted_observation;
75 }
76
GetPercentile(base::TimeTicks begin_timestamp,int32_t current_signal_strength,int percentile,size_t * observations_count) const77 std::optional<int32_t> ObservationBuffer::GetPercentile(
78 base::TimeTicks begin_timestamp,
79 int32_t current_signal_strength,
80 int percentile,
81 size_t* observations_count) const {
82 DCHECK(current_signal_strength == INT32_MIN ||
83 (current_signal_strength >= 0 && current_signal_strength <= 4));
84
85 // Stores weighted observations in increasing order by value.
86 std::vector<WeightedObservation> weighted_observations;
87
88 // Total weight of all observations in |weighted_observations|.
89 double total_weight = 0.0;
90
91 ComputeWeightedObservations(begin_timestamp, current_signal_strength,
92 &weighted_observations, &total_weight);
93
94 if (observations_count) {
95 // |observations_count| may be null.
96 *observations_count = weighted_observations.size();
97 }
98
99 if (weighted_observations.empty())
100 return std::nullopt;
101
102 double desired_weight = percentile / 100.0 * total_weight;
103
104 double cumulative_weight_seen_so_far = 0.0;
105 for (const auto& weighted_observation : weighted_observations) {
106 cumulative_weight_seen_so_far += weighted_observation.weight;
107 if (cumulative_weight_seen_so_far >= desired_weight)
108 return weighted_observation.value;
109 }
110
111 // Computation may reach here due to floating point errors. This may happen
112 // if |percentile| was 100 (or close to 100), and |desired_weight| was
113 // slightly larger than |total_weight| (due to floating point errors).
114 // In this case, we return the highest |value| among all observations.
115 // This is same as value of the last observation in the sorted vector.
116 return weighted_observations.at(weighted_observations.size() - 1).value;
117 }
118
RemoveObservationsWithSource(bool deleted_observation_sources[NETWORK_QUALITY_OBSERVATION_SOURCE_MAX])119 void ObservationBuffer::RemoveObservationsWithSource(
120 bool deleted_observation_sources[NETWORK_QUALITY_OBSERVATION_SOURCE_MAX]) {
121 base::EraseIf(observations_,
122 [deleted_observation_sources](const Observation& observation) {
123 return deleted_observation_sources[static_cast<size_t>(
124 observation.source())];
125 });
126 }
127
ComputeWeightedObservations(const base::TimeTicks & begin_timestamp,int32_t current_signal_strength,std::vector<WeightedObservation> * weighted_observations,double * total_weight) const128 void ObservationBuffer::ComputeWeightedObservations(
129 const base::TimeTicks& begin_timestamp,
130 int32_t current_signal_strength,
131 std::vector<WeightedObservation>* weighted_observations,
132 double* total_weight) const {
133 DCHECK_GE(Capacity(), Size());
134
135 weighted_observations->clear();
136 double total_weight_observations = 0.0;
137 base::TimeTicks now = tick_clock_->NowTicks();
138
139 for (const auto& observation : observations_) {
140 if (observation.timestamp() < begin_timestamp)
141 continue;
142
143 base::TimeDelta time_since_sample_taken = now - observation.timestamp();
144 double time_weight =
145 pow(weight_multiplier_per_second_, time_since_sample_taken.InSeconds());
146
147 double signal_strength_weight = 1.0;
148 if (current_signal_strength >= 0 && observation.signal_strength() >= 0) {
149 int32_t signal_strength_weight_diff =
150 std::abs(current_signal_strength - observation.signal_strength());
151 signal_strength_weight =
152 pow(weight_multiplier_per_signal_level_, signal_strength_weight_diff);
153 }
154
155 double weight = time_weight * signal_strength_weight;
156 weight = std::clamp(weight, DBL_MIN, 1.0);
157
158 weighted_observations->push_back(
159 WeightedObservation(observation.value(), weight));
160 total_weight_observations += weight;
161 }
162
163 // Sort the samples by value in ascending order.
164 std::sort(weighted_observations->begin(), weighted_observations->end());
165 *total_weight = total_weight_observations;
166
167 DCHECK_LE(0.0, *total_weight);
168 DCHECK(weighted_observations->empty() || 0.0 < *total_weight);
169
170 // |weighted_observations| may have a smaller size than |observations_|
171 // since the former contains only the observations later than
172 // |begin_timestamp|.
173 DCHECK_GE(observations_.size(), weighted_observations->size());
174 }
175
Capacity() const176 size_t ObservationBuffer::Capacity() const {
177 return params_->observation_buffer_size();
178 }
179
180 } // namespace net::nqe::internal
181