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