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