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