1// Copyright (c) 2012 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 "net/url_request/url_request_throttler_entry.h"
6
7#include <cmath>
8
9#include "base/logging.h"
10#include "base/metrics/field_trial.h"
11#include "base/metrics/histogram.h"
12#include "base/rand_util.h"
13#include "base/strings/string_number_conversions.h"
14#include "base/values.h"
15#include "net/base/load_flags.h"
16#include "net/base/net_log.h"
17#include "net/url_request/url_request.h"
18#include "net/url_request/url_request_context.h"
19#include "net/url_request/url_request_throttler_header_interface.h"
20#include "net/url_request/url_request_throttler_manager.h"
21
22namespace net {
23
24const int URLRequestThrottlerEntry::kDefaultSlidingWindowPeriodMs = 2000;
25const int URLRequestThrottlerEntry::kDefaultMaxSendThreshold = 20;
26
27// This set of back-off parameters will (at maximum values, i.e. without
28// the reduction caused by jitter) add 0-41% (distributed uniformly
29// in that range) to the "perceived downtime" of the remote server, once
30// exponential back-off kicks in and is throttling requests for more than
31// about a second at a time.  Once the maximum back-off is reached, the added
32// perceived downtime decreases rapidly, percentage-wise.
33//
34// Another way to put it is that the maximum additional perceived downtime
35// with these numbers is a couple of seconds shy of 15 minutes, and such
36// a delay would not occur until the remote server has been actually
37// unavailable at the end of each back-off period for a total of about
38// 48 minutes.
39//
40// Ignoring the first couple of errors is just a conservative measure to
41// avoid false positives.  It should help avoid back-off from kicking in e.g.
42// on flaky connections.
43const int URLRequestThrottlerEntry::kDefaultNumErrorsToIgnore = 2;
44const int URLRequestThrottlerEntry::kDefaultInitialDelayMs = 700;
45const double URLRequestThrottlerEntry::kDefaultMultiplyFactor = 1.4;
46const double URLRequestThrottlerEntry::kDefaultJitterFactor = 0.4;
47const int URLRequestThrottlerEntry::kDefaultMaximumBackoffMs = 15 * 60 * 1000;
48const int URLRequestThrottlerEntry::kDefaultEntryLifetimeMs = 2 * 60 * 1000;
49const char URLRequestThrottlerEntry::kExponentialThrottlingHeader[] =
50    "X-Chrome-Exponential-Throttling";
51const char URLRequestThrottlerEntry::kExponentialThrottlingDisableValue[] =
52    "disable";
53
54// Returns NetLog parameters when a request is rejected by throttling.
55base::Value* NetLogRejectedRequestCallback(const std::string* url_id,
56                                           int num_failures,
57                                           int release_after_ms,
58                                           NetLog::LogLevel /* log_level */) {
59  base::DictionaryValue* dict = new base::DictionaryValue();
60  dict->SetString("url", *url_id);
61  dict->SetInteger("num_failures", num_failures);
62  dict->SetInteger("release_after_ms", release_after_ms);
63  return dict;
64}
65
66URLRequestThrottlerEntry::URLRequestThrottlerEntry(
67    URLRequestThrottlerManager* manager,
68    const std::string& url_id)
69    : sliding_window_period_(
70          base::TimeDelta::FromMilliseconds(kDefaultSlidingWindowPeriodMs)),
71      max_send_threshold_(kDefaultMaxSendThreshold),
72      is_backoff_disabled_(false),
73      backoff_entry_(&backoff_policy_),
74      manager_(manager),
75      url_id_(url_id),
76      net_log_(BoundNetLog::Make(
77          manager->net_log(), NetLog::SOURCE_EXPONENTIAL_BACKOFF_THROTTLING)) {
78  DCHECK(manager_);
79  Initialize();
80}
81
82URLRequestThrottlerEntry::URLRequestThrottlerEntry(
83    URLRequestThrottlerManager* manager,
84    const std::string& url_id,
85    int sliding_window_period_ms,
86    int max_send_threshold,
87    int initial_backoff_ms,
88    double multiply_factor,
89    double jitter_factor,
90    int maximum_backoff_ms)
91    : sliding_window_period_(
92          base::TimeDelta::FromMilliseconds(sliding_window_period_ms)),
93      max_send_threshold_(max_send_threshold),
94      is_backoff_disabled_(false),
95      backoff_entry_(&backoff_policy_),
96      manager_(manager),
97      url_id_(url_id) {
98  DCHECK_GT(sliding_window_period_ms, 0);
99  DCHECK_GT(max_send_threshold_, 0);
100  DCHECK_GE(initial_backoff_ms, 0);
101  DCHECK_GT(multiply_factor, 0);
102  DCHECK_GE(jitter_factor, 0.0);
103  DCHECK_LT(jitter_factor, 1.0);
104  DCHECK_GE(maximum_backoff_ms, 0);
105  DCHECK(manager_);
106
107  Initialize();
108  backoff_policy_.initial_delay_ms = initial_backoff_ms;
109  backoff_policy_.multiply_factor = multiply_factor;
110  backoff_policy_.jitter_factor = jitter_factor;
111  backoff_policy_.maximum_backoff_ms = maximum_backoff_ms;
112  backoff_policy_.entry_lifetime_ms = -1;
113  backoff_policy_.num_errors_to_ignore = 0;
114  backoff_policy_.always_use_initial_delay = false;
115}
116
117bool URLRequestThrottlerEntry::IsEntryOutdated() const {
118  // This function is called by the URLRequestThrottlerManager to determine
119  // whether entries should be discarded from its url_entries_ map.  We
120  // want to ensure that it does not remove entries from the map while there
121  // are clients (objects other than the manager) holding references to
122  // the entry, otherwise separate clients could end up holding separate
123  // entries for a request to the same URL, which is undesirable.  Therefore,
124  // if an entry has more than one reference (the map will always hold one),
125  // it should not be considered outdated.
126  //
127  // We considered whether to make URLRequestThrottlerEntry objects
128  // non-refcounted, but since any means of knowing whether they are
129  // currently in use by others than the manager would be more or less
130  // equivalent to a refcount, we kept them refcounted.
131  if (!HasOneRef())
132    return false;
133
134  // If there are send events in the sliding window period, we still need this
135  // entry.
136  if (!send_log_.empty() &&
137      send_log_.back() + sliding_window_period_ > ImplGetTimeNow()) {
138    return false;
139  }
140
141  return GetBackoffEntry()->CanDiscard();
142}
143
144void URLRequestThrottlerEntry::DisableBackoffThrottling() {
145  is_backoff_disabled_ = true;
146}
147
148void URLRequestThrottlerEntry::DetachManager() {
149  manager_ = NULL;
150}
151
152bool URLRequestThrottlerEntry::ShouldRejectRequest(
153    const URLRequest& request) const {
154  bool reject_request = false;
155  if (!is_backoff_disabled_ && !ExplicitUserRequest(request.load_flags()) &&
156      (!request.context()->network_delegate() ||
157       request.context()->network_delegate()->CanThrottleRequest(request)) &&
158      GetBackoffEntry()->ShouldRejectRequest()) {
159    int num_failures = GetBackoffEntry()->failure_count();
160    int release_after_ms =
161        GetBackoffEntry()->GetTimeUntilRelease().InMilliseconds();
162
163    net_log_.AddEvent(
164        NetLog::TYPE_THROTTLING_REJECTED_REQUEST,
165        base::Bind(&NetLogRejectedRequestCallback,
166                   &url_id_, num_failures, release_after_ms));
167
168    reject_request = true;
169  }
170
171  int reject_count = reject_request ? 1 : 0;
172  UMA_HISTOGRAM_ENUMERATION(
173      "Throttling.RequestThrottled", reject_count, 2);
174
175  return reject_request;
176}
177
178int64 URLRequestThrottlerEntry::ReserveSendingTimeForNextRequest(
179    const base::TimeTicks& earliest_time) {
180  base::TimeTicks now = ImplGetTimeNow();
181
182  // If a lot of requests were successfully made recently,
183  // sliding_window_release_time_ may be greater than
184  // exponential_backoff_release_time_.
185  base::TimeTicks recommended_sending_time =
186      std::max(std::max(now, earliest_time),
187               std::max(GetBackoffEntry()->GetReleaseTime(),
188                        sliding_window_release_time_));
189
190  DCHECK(send_log_.empty() ||
191         recommended_sending_time >= send_log_.back());
192  // Log the new send event.
193  send_log_.push(recommended_sending_time);
194
195  sliding_window_release_time_ = recommended_sending_time;
196
197  // Drop the out-of-date events in the event list.
198  // We don't need to worry that the queue may become empty during this
199  // operation, since the last element is sliding_window_release_time_.
200  while ((send_log_.front() + sliding_window_period_ <=
201          sliding_window_release_time_) ||
202         send_log_.size() > static_cast<unsigned>(max_send_threshold_)) {
203    send_log_.pop();
204  }
205
206  // Check if there are too many send events in recent time.
207  if (send_log_.size() == static_cast<unsigned>(max_send_threshold_))
208    sliding_window_release_time_ = send_log_.front() + sliding_window_period_;
209
210  return (recommended_sending_time - now).InMillisecondsRoundedUp();
211}
212
213base::TimeTicks
214    URLRequestThrottlerEntry::GetExponentialBackoffReleaseTime() const {
215  // If a site opts out, it's likely because they have problems that trigger
216  // the back-off mechanism when it shouldn't be triggered, in which case
217  // returning the calculated back-off release time would probably be the
218  // wrong thing to do (i.e. it would likely be too long).  Therefore, we
219  // return "now" so that retries are not delayed.
220  if (is_backoff_disabled_)
221    return ImplGetTimeNow();
222
223  return GetBackoffEntry()->GetReleaseTime();
224}
225
226void URLRequestThrottlerEntry::UpdateWithResponse(
227    const std::string& host,
228    const URLRequestThrottlerHeaderInterface* response) {
229  if (IsConsideredError(response->GetResponseCode())) {
230    GetBackoffEntry()->InformOfRequest(false);
231  } else {
232    GetBackoffEntry()->InformOfRequest(true);
233
234    std::string throttling_header = response->GetNormalizedValue(
235        kExponentialThrottlingHeader);
236    if (!throttling_header.empty())
237      HandleThrottlingHeader(throttling_header, host);
238  }
239}
240
241void URLRequestThrottlerEntry::ReceivedContentWasMalformed(int response_code) {
242  // A malformed body can only occur when the request to fetch a resource
243  // was successful.  Therefore, in such a situation, we will receive one
244  // call to ReceivedContentWasMalformed() and one call to
245  // UpdateWithResponse() with a response categorized as "good".  To end
246  // up counting one failure, we need to count two failures here against
247  // the one success in UpdateWithResponse().
248  //
249  // We do nothing for a response that is already being considered an error
250  // based on its status code (otherwise we would count 3 errors instead of 1).
251  if (!IsConsideredError(response_code)) {
252    GetBackoffEntry()->InformOfRequest(false);
253    GetBackoffEntry()->InformOfRequest(false);
254  }
255}
256
257URLRequestThrottlerEntry::~URLRequestThrottlerEntry() {
258}
259
260void URLRequestThrottlerEntry::Initialize() {
261  sliding_window_release_time_ = base::TimeTicks::Now();
262  backoff_policy_.num_errors_to_ignore = kDefaultNumErrorsToIgnore;
263  backoff_policy_.initial_delay_ms = kDefaultInitialDelayMs;
264  backoff_policy_.multiply_factor = kDefaultMultiplyFactor;
265  backoff_policy_.jitter_factor = kDefaultJitterFactor;
266  backoff_policy_.maximum_backoff_ms = kDefaultMaximumBackoffMs;
267  backoff_policy_.entry_lifetime_ms = kDefaultEntryLifetimeMs;
268  backoff_policy_.always_use_initial_delay = false;
269}
270
271bool URLRequestThrottlerEntry::IsConsideredError(int response_code) {
272  // We throttle only for the status codes most likely to indicate the server
273  // is failing because it is too busy or otherwise are likely to be
274  // because of DDoS.
275  //
276  // 500 is the generic error when no better message is suitable, and
277  //     as such does not necessarily indicate a temporary state, but
278  //     other status codes cover most of the permanent error states.
279  // 503 is explicitly documented as a temporary state where the server
280  //     is either overloaded or down for maintenance.
281  // 509 is the (non-standard but widely implemented) Bandwidth Limit Exceeded
282  //     status code, which might indicate DDoS.
283  //
284  // We do not back off on 502 or 504, which are reported by gateways
285  // (proxies) on timeouts or failures, because in many cases these requests
286  // have not made it to the destination server and so we do not actually
287  // know that it is down or busy.  One degenerate case could be a proxy on
288  // localhost, where you are not actually connected to the network.
289  return (response_code == 500 ||
290          response_code == 503 ||
291          response_code == 509);
292}
293
294base::TimeTicks URLRequestThrottlerEntry::ImplGetTimeNow() const {
295  return base::TimeTicks::Now();
296}
297
298void URLRequestThrottlerEntry::HandleThrottlingHeader(
299    const std::string& header_value,
300    const std::string& host) {
301  if (header_value == kExponentialThrottlingDisableValue) {
302    DisableBackoffThrottling();
303    if (manager_)
304      manager_->AddToOptOutList(host);
305  }
306}
307
308const BackoffEntry* URLRequestThrottlerEntry::GetBackoffEntry() const {
309  return &backoff_entry_;
310}
311
312BackoffEntry* URLRequestThrottlerEntry::GetBackoffEntry() {
313  return &backoff_entry_;
314}
315
316// static
317bool URLRequestThrottlerEntry::ExplicitUserRequest(const int load_flags) {
318  return (load_flags & LOAD_MAYBE_USER_GESTURE) != 0;
319}
320
321}  // namespace net
322