1 // Copyright 2013 The Chromium Authors. All rights reserved.
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 "content/browser/download/rate_estimator.h"
6
7 #include "base/logging.h"
8
9 using base::TimeDelta;
10 using base::TimeTicks;
11
12 namespace content {
13
14 namespace {
15
16 static const int kDefaultBucketTimeSeconds = 1;
17 static const size_t kDefaultNumBuckets = 10;
18
19 } // namespace
20
RateEstimator()21 RateEstimator::RateEstimator()
22 : history_(kDefaultNumBuckets),
23 bucket_time_(TimeDelta::FromSeconds(kDefaultBucketTimeSeconds)),
24 oldest_index_(0),
25 bucket_count_(1) {
26 ResetBuckets(TimeTicks::Now());
27 }
28
RateEstimator(TimeDelta bucket_time,size_t num_buckets,TimeTicks now)29 RateEstimator::RateEstimator(TimeDelta bucket_time,
30 size_t num_buckets,
31 TimeTicks now)
32 : history_(num_buckets),
33 bucket_time_(bucket_time),
34 oldest_index_(0),
35 bucket_count_(1) {
36 DCHECK(bucket_time_.InSeconds() > 0);
37 ResetBuckets(now);
38 }
39
~RateEstimator()40 RateEstimator::~RateEstimator() {
41 }
42
Increment(uint32 count)43 void RateEstimator::Increment(uint32 count) {
44 Increment(count, TimeTicks::Now());
45 }
46
Increment(uint32 count,TimeTicks now)47 void RateEstimator::Increment(uint32 count, TimeTicks now) {
48 ClearOldBuckets(now);
49 int64 seconds_since_oldest = (now - oldest_time_).InSeconds();
50 DCHECK(seconds_since_oldest >= 0);
51 int64 delta_buckets = seconds_since_oldest / bucket_time_.InSeconds();
52 DCHECK(delta_buckets >= 0);
53 size_t index_offset = static_cast<size_t>(delta_buckets);
54 DCHECK(index_offset <= history_.size());
55 int current_index = (oldest_index_ + delta_buckets) % history_.size();
56 history_[current_index] += count;
57 }
58
GetCountPerSecond() const59 uint64 RateEstimator::GetCountPerSecond() const {
60 return GetCountPerSecond(TimeTicks::Now());
61 }
62
GetCountPerSecond(TimeTicks now) const63 uint64 RateEstimator::GetCountPerSecond(TimeTicks now) const {
64 const_cast<RateEstimator*>(this)->ClearOldBuckets(now);
65 // TODO(cbentzel): Support fractional seconds for active bucket?
66 // We explicitly don't check for overflow here. If it happens, unsigned
67 // arithmetic at least guarantees behavior by wrapping around. The estimate
68 // will be off, but the code will still be valid.
69 uint64 total_count = 0;
70 for (size_t i = 0; i < bucket_count_; ++i) {
71 size_t index = (oldest_index_ + i) % history_.size();
72 total_count += history_[index];
73 }
74 return total_count / (bucket_count_ * bucket_time_.InSeconds());
75 }
76
ClearOldBuckets(TimeTicks now)77 void RateEstimator::ClearOldBuckets(TimeTicks now) {
78 int64 seconds_since_oldest = (now - oldest_time_).InSeconds();
79
80 int64 delta_buckets = seconds_since_oldest / bucket_time_.InSeconds();
81
82 // It's possible (although unlikely) for there to be rollover with TimeTicks.
83 // If that's the case, just reset the history.
84 if (delta_buckets < 0) {
85 ResetBuckets(now);
86 return;
87 }
88 size_t delta_index = static_cast<size_t>(delta_buckets);
89
90 // If we are within the current window, keep the existing data.
91 if (delta_index < history_.size()) {
92 bucket_count_ = delta_index + 1;
93 return;
94 }
95
96 // If it's been long enough that all history data is too stale, just
97 // clear all the buckets.
98 size_t extra_buckets = delta_index - history_.size() + 1;
99 if (extra_buckets > history_.size()) {
100 ResetBuckets(now);
101 return;
102 }
103
104 // Clear out stale buckets in the history.
105 bucket_count_ = history_.size();
106 for (size_t i = 0; i < extra_buckets; ++i) {
107 history_[oldest_index_] = 0;
108 oldest_index_ = (oldest_index_ + 1) % history_.size();
109 oldest_time_ = oldest_time_ + bucket_time_;
110 }
111 }
112
ResetBuckets(TimeTicks now)113 void RateEstimator::ResetBuckets(TimeTicks now) {
114 for (size_t i = 0; i < history_.size(); ++i) {
115 history_[i] = 0;
116 }
117 oldest_index_ = 0;
118 bucket_count_ = 1;
119 oldest_time_ = now;
120 }
121
122 } // namespace content
123