1 // Copyright 2016 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 #ifndef NET_NQE_OBSERVATION_BUFFER_H_ 6 #define NET_NQE_OBSERVATION_BUFFER_H_ 7 8 #include <stdint.h> 9 10 #include <map> 11 #include <memory> 12 #include <optional> 13 #include <set> 14 #include <vector> 15 16 #include "base/containers/circular_deque.h" 17 #include "base/memory/raw_ptr.h" 18 #include "base/time/tick_clock.h" 19 #include "net/base/net_export.h" 20 #include "net/nqe/network_quality_estimator_util.h" 21 #include "net/nqe/network_quality_observation.h" 22 #include "net/nqe/network_quality_observation_source.h" 23 24 namespace base { 25 26 class TimeTicks; 27 28 } // namespace base 29 30 namespace net { 31 32 class NetworkQualityEstimatorParams; 33 34 namespace nqe::internal { 35 36 struct WeightedObservation; 37 38 // Stores observations sorted by time and provides utility functions for 39 // computing weighted and non-weighted summary statistics. 40 class NET_EXPORT_PRIVATE ObservationBuffer { 41 public: 42 ObservationBuffer(const NetworkQualityEstimatorParams* params, 43 const base::TickClock* tick_clock, 44 double weight_multiplier_per_second, 45 double weight_multiplier_per_signal_level); 46 47 // This constructor does not copy the |observations_| from |other| to |this|. 48 // As such, this constructor should only be called before adding any 49 // observations to |other|. 50 ObservationBuffer(const ObservationBuffer& other); 51 52 ObservationBuffer& operator=(const ObservationBuffer&) = delete; 53 54 ~ObservationBuffer(); 55 56 // Adds |observation| to the buffer. The oldest observation in the buffer 57 // will be evicted to make room if the buffer is already full. 58 // In that case, an evicted observation will be returned. 59 std::optional<Observation> AddObservation(const Observation& observation); 60 61 // Returns the number of observations in this buffer. Size()62 size_t Size() const { return static_cast<size_t>(observations_.size()); } 63 64 // Returns the capacity of this buffer. 65 size_t Capacity() const; 66 67 // Clears the observations stored in this buffer. Clear()68 void Clear() { observations_.clear(); } 69 70 // Returns true iff the |percentile| value of the observations in this 71 // buffer is available. Sets |result| to the computed |percentile| 72 // value of all observations made on or after |begin_timestamp|. If the 73 // value is unavailable, false is returned and |result| is not modified. 74 // Percentile value is unavailable if all the values in observation buffer are 75 // older than |begin_timestamp|. |current_signal_strength| is the current 76 // signal strength. |result| must not be null. If |observations_count| is not 77 // null, then it is set to the number of observations that were available 78 // in the observation buffer for computing the percentile. 79 std::optional<int32_t> GetPercentile(base::TimeTicks begin_timestamp, 80 int32_t current_signal_strength, 81 int percentile, 82 size_t* observations_count) const; 83 SetTickClockForTesting(const base::TickClock * tick_clock)84 void SetTickClockForTesting(const base::TickClock* tick_clock) { 85 tick_clock_ = tick_clock; 86 } 87 88 // Removes all observations from the buffer whose corresponding entry in 89 // |deleted_observation_sources| is set to true. For example, if index 1 and 90 // 3 in |deleted_observation_sources| are set to true, then all observations 91 // in the buffer that have source set to either 1 or 3 would be removed. 92 void RemoveObservationsWithSource( 93 bool deleted_observation_sources[NETWORK_QUALITY_OBSERVATION_SOURCE_MAX]); 94 95 private: 96 // Computes the weighted observations and stores them in 97 // |weighted_observations| sorted by ascending |WeightedObservation.value|. 98 // Only the observations with timestamp later than |begin_timestamp| are 99 // considered. |current_signal_strength| is the current signal strength 100 // when the observation was taken. This method also sets |total_weight| to 101 // the total weight of all observations. Should be called only when there is 102 // at least one observation in the buffer. 103 void ComputeWeightedObservations( 104 const base::TimeTicks& begin_timestamp, 105 int32_t current_signal_strength, 106 std::vector<WeightedObservation>* weighted_observations, 107 double* total_weight) const; 108 109 raw_ptr<const NetworkQualityEstimatorParams> params_; 110 111 // Holds observations sorted by time, with the oldest observation at the 112 // front of the queue. 113 base::circular_deque<Observation> observations_; 114 115 // The factor by which the weight of an observation reduces every second. 116 // For example, if an observation is 6 seconds old, its weight would be: 117 // weight_multiplier_per_second_ ^ 6 118 // Calculated from |kHalfLifeSeconds| by solving the following equation: 119 // weight_multiplier_per_second_ ^ kHalfLifeSeconds = 0.5 120 const double weight_multiplier_per_second_; 121 122 // The factor by which the weight of an observation reduces for every unit 123 // difference in the current signal strength, and the signal strength at 124 // which the observation was taken. 125 // For example, if the observation was taken at 1 unit, and current signal 126 // strength is 4 units, the weight of the observation would be: 127 // |weight_multiplier_per_signal_level_| ^ 3. 128 const double weight_multiplier_per_signal_level_; 129 130 raw_ptr<const base::TickClock> tick_clock_; 131 }; 132 133 } // namespace nqe::internal 134 135 } // namespace net 136 137 #endif // NET_NQE_OBSERVATION_BUFFER_H_ 138