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