Home | History | Annotate | Download | only in browser 
      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 
     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 namespace extensions {
     24 
     25 QuotaService::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 
     34 QuotaService::~QuotaService() {
     35   DCHECK(CalledOnValidThread());
     36   purge_timer_.Stop();
     37   Purge();
     38 }
     39 
     40 std::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 
     88 void 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 
     96 void 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 
    104 void 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 
    110 void QuotaLimitHeuristic::SingletonBucketMapper::GetBucketsForArgs(
    111     const base::ListValue* args,
    112     BucketList* buckets) {
    113   buckets->push_back(&bucket_);
    114 }
    115 
    116 QuotaLimitHeuristic::QuotaLimitHeuristic(const Config& config,
    117                                          BucketMapper* map,
    118                                          const std::string& name)
    119     : config_(config), bucket_mapper_(map), name_(name) {}
    120 
    121 QuotaLimitHeuristic::~QuotaLimitHeuristic() {}
    122 
    123 bool 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 
    136 std::string QuotaLimitHeuristic::GetError() const {
    137   return extensions::ErrorUtils::FormatErrorMessage(kOverQuotaError, name_);
    138 }
    139 
    140 QuotaService::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 
    149 bool 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 
    157 bool 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