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