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