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 "extensions/browser/quota_service.h"
6
7#include "base/message_loop/message_loop.h"
8#include "base/stl_util.h"
9#include "extensions/browser/extension_function.h"
10#include "extensions/common/error_utils.h"
11
12namespace {
13
14// If the browser stays open long enough, we reset state once a day.
15// Whatever this value is, it should be an order of magnitude longer than
16// the longest interval in any of the QuotaLimitHeuristics in use.
17const int kPurgeIntervalInDays = 1;
18
19const char kOverQuotaError[] = "This request exceeds the * quota.";
20
21}  // namespace
22
23namespace extensions {
24
25QuotaService::QuotaService() {
26  if (base::MessageLoop::current() != NULL) {  // Null in unit tests.
27    purge_timer_.Start(FROM_HERE,
28                       base::TimeDelta::FromDays(kPurgeIntervalInDays),
29                       this,
30                       &QuotaService::Purge);
31  }
32}
33
34QuotaService::~QuotaService() {
35  DCHECK(CalledOnValidThread());
36  purge_timer_.Stop();
37  Purge();
38}
39
40std::string QuotaService::Assess(const std::string& extension_id,
41                                 ExtensionFunction* function,
42                                 const base::ListValue* args,
43                                 const base::TimeTicks& event_time) {
44  DCHECK(CalledOnValidThread());
45
46  if (function->ShouldSkipQuotaLimiting())
47    return std::string();
48
49  // Lookup function list for extension.
50  FunctionHeuristicsMap& functions = function_heuristics_[extension_id];
51
52  // Lookup heuristics for function, create if necessary.
53  QuotaLimitHeuristics& heuristics = functions[function->name()];
54  if (heuristics.empty())
55    function->GetQuotaLimitHeuristics(&heuristics);
56
57  if (heuristics.empty())
58    return std::string();  // No heuristic implies no limit.
59
60  ViolationErrorMap::iterator violation_error =
61      violation_errors_.find(extension_id);
62  if (violation_error != violation_errors_.end())
63    return violation_error->second;  // Repeat offender.
64
65  QuotaLimitHeuristic* failed_heuristic = NULL;
66  for (QuotaLimitHeuristics::iterator heuristic = heuristics.begin();
67       heuristic != heuristics.end();
68       ++heuristic) {
69    // Apply heuristic to each item (bucket).
70    if (!(*heuristic)->ApplyToArgs(args, event_time)) {
71      failed_heuristic = *heuristic;
72      break;
73    }
74  }
75
76  if (!failed_heuristic)
77    return std::string();
78
79  std::string error = failed_heuristic->GetError();
80  DCHECK_GT(error.length(), 0u);
81
82  PurgeFunctionHeuristicsMap(&functions);
83  function_heuristics_.erase(extension_id);
84  violation_errors_[extension_id] = error;
85  return error;
86}
87
88void QuotaService::PurgeFunctionHeuristicsMap(FunctionHeuristicsMap* map) {
89  FunctionHeuristicsMap::iterator heuristics = map->begin();
90  while (heuristics != map->end()) {
91    STLDeleteElements(&heuristics->second);
92    map->erase(heuristics++);
93  }
94}
95
96void QuotaService::Purge() {
97  DCHECK(CalledOnValidThread());
98  std::map<std::string, FunctionHeuristicsMap>::iterator it =
99      function_heuristics_.begin();
100  for (; it != function_heuristics_.end(); function_heuristics_.erase(it++))
101    PurgeFunctionHeuristicsMap(&it->second);
102}
103
104void QuotaLimitHeuristic::Bucket::Reset(const Config& config,
105                                        const base::TimeTicks& start) {
106  num_tokens_ = config.refill_token_count;
107  expiration_ = start + config.refill_interval;
108}
109
110void QuotaLimitHeuristic::SingletonBucketMapper::GetBucketsForArgs(
111    const base::ListValue* args,
112    BucketList* buckets) {
113  buckets->push_back(&bucket_);
114}
115
116QuotaLimitHeuristic::QuotaLimitHeuristic(const Config& config,
117                                         BucketMapper* map,
118                                         const std::string& name)
119    : config_(config), bucket_mapper_(map), name_(name) {}
120
121QuotaLimitHeuristic::~QuotaLimitHeuristic() {}
122
123bool QuotaLimitHeuristic::ApplyToArgs(const base::ListValue* args,
124                                      const base::TimeTicks& event_time) {
125  BucketList buckets;
126  bucket_mapper_->GetBucketsForArgs(args, &buckets);
127  for (BucketList::iterator i = buckets.begin(); i != buckets.end(); ++i) {
128    if ((*i)->expiration().is_null())  // A brand new bucket.
129      (*i)->Reset(config_, event_time);
130    if (!Apply(*i, event_time))
131      return false;  // It only takes one to spoil it for everyone.
132  }
133  return true;
134}
135
136std::string QuotaLimitHeuristic::GetError() const {
137  return extensions::ErrorUtils::FormatErrorMessage(kOverQuotaError, name_);
138}
139
140QuotaService::SustainedLimit::SustainedLimit(const base::TimeDelta& sustain,
141                                             const Config& config,
142                                             BucketMapper* map,
143                                             const std::string& name)
144    : QuotaLimitHeuristic(config, map, name),
145      repeat_exhaustion_allowance_(sustain.InSeconds() /
146                                   config.refill_interval.InSeconds()),
147      num_available_repeat_exhaustions_(repeat_exhaustion_allowance_) {}
148
149bool QuotaService::TimedLimit::Apply(Bucket* bucket,
150                                     const base::TimeTicks& event_time) {
151  if (event_time > bucket->expiration())
152    bucket->Reset(config(), event_time);
153
154  return bucket->DeductToken();
155}
156
157bool QuotaService::SustainedLimit::Apply(Bucket* bucket,
158                                         const base::TimeTicks& event_time) {
159  if (event_time > bucket->expiration()) {
160    // We reset state for this item and start over again if this request breaks
161    // the bad cycle that was previously being tracked.  This occurs if the
162    // state in the bucket expired recently (it has been long enough since the
163    // event that we don't care about the last event), but the bucket still has
164    // tokens (so pressure was not sustained over that time), OR we are more
165    // than 1 full refill interval away from the last event (so even if we used
166    // up all the tokens in the last bucket, nothing happened in the entire
167    // next refill interval, so it doesn't matter).
168    if (bucket->has_tokens() ||
169        event_time > bucket->expiration() + config().refill_interval) {
170      bucket->Reset(config(), event_time);
171      num_available_repeat_exhaustions_ = repeat_exhaustion_allowance_;
172    } else if (--num_available_repeat_exhaustions_ > 0) {
173      // The last interval was saturated with requests, and this is the first
174      // event in the next interval. If this happens
175      // repeat_exhaustion_allowance_ times, it's a violation. Reset the bucket
176      // state to start timing from the end of the last interval (and we'll
177      // deduct the token below) so we can detect this each time it happens.
178      bucket->Reset(config(), bucket->expiration());
179    } else {
180      // No allowances left; this request is a violation.
181      return false;
182    }
183  }
184
185  // We can go negative since we check has_tokens when we get to *next* bucket,
186  // and for the small interval all that matters is whether we used up all the
187  // tokens (which is true if num_tokens_ <= 0).
188  bucket->DeductToken();
189  return true;
190}
191
192}  // namespace extensions
193