Home | History | Annotate | Download | only in extensions 
      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.
     14 static const int kPurgeIntervalInDays = 1;
     15 
     16 const char QuotaLimitHeuristic::kGenericOverQuotaError[] =
     17     "This request exceeds available quota.";
     18 
     19 ExtensionsQuotaService::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 
     26 ExtensionsQuotaService::~ExtensionsQuotaService() {
     27   purge_timer_.Stop();
     28   Purge();
     29 }
     30 
     31 bool 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 
     64 void 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 
     73 void 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 
     80 void 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 
     86 QuotaLimitHeuristic::QuotaLimitHeuristic(const Config& config,
     87                                          BucketMapper* map)
     88     : config_(config), bucket_mapper_(map) {
     89 }
     90 
     91 QuotaLimitHeuristic::~QuotaLimitHeuristic() {}
     92 
     93 bool 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 
    106 ExtensionsQuotaService::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 
    114 bool 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 
    122 bool 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