1c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// Copyright (c) 2009 The Chromium Authors. All rights reserved. 2c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// Use of this source code is governed by a BSD-style license that can be 3c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// found in the LICENSE file. 4c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 5c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include "chrome/browser/extensions/extensions_quota_service.h" 6c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 7c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include "base/message_loop.h" 8c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include "base/stl_util-inl.h" 9c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include "chrome/browser/extensions/extension_function.h" 10c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 11c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// If the browser stays open long enough, we reset state once a day. 12c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// Whatever this value is, it should be an order of magnitude longer than 13c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// the longest interval in any of the QuotaLimitHeuristics in use. 14c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochstatic const int kPurgeIntervalInDays = 1; 15c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 16c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochconst char QuotaLimitHeuristic::kGenericOverQuotaError[] = 17c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch "This request exceeds available quota."; 18c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 19c407dc5cd9bdc5668497f21b26b09d988ab439deBen MurdochExtensionsQuotaService::ExtensionsQuotaService() { 20c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (MessageLoop::current() != NULL) { // Null in unit tests. 21c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch purge_timer_.Start(base::TimeDelta::FromDays(kPurgeIntervalInDays), 22c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch this, &ExtensionsQuotaService::Purge); 23c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 24c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 25c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 26c407dc5cd9bdc5668497f21b26b09d988ab439deBen MurdochExtensionsQuotaService::~ExtensionsQuotaService() { 27c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch purge_timer_.Stop(); 28c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch Purge(); 29c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 30c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 31c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochbool ExtensionsQuotaService::Assess(const std::string& extension_id, 32c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch ExtensionFunction* function, const ListValue* args, 33c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch const base::TimeTicks& event_time) { 34c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Lookup function list for extension. 35c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch FunctionHeuristicsMap& functions = function_heuristics_[extension_id]; 36c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 37c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Lookup heuristics for function, create if necessary. 38c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch QuotaLimitHeuristics& heuristics = functions[function->name()]; 39c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (heuristics.empty()) 40c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch function->GetQuotaLimitHeuristics(&heuristics); 41c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 42c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (heuristics.empty()) 43c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return true; // No heuristic implies no limit. 44c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 45c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (violators_.find(extension_id) != violators_.end()) 46c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; // Repeat offender. 47c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 48c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch bool global_decision = true; 49c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch for (QuotaLimitHeuristics::iterator heuristic = heuristics.begin(); 50c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch heuristic != heuristics.end(); ++heuristic) { 51c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Apply heuristic to each item (bucket). 52c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch global_decision = (*heuristic)->ApplyToArgs(args, event_time) && 53c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch global_decision; 54c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 55c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 56c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!global_decision) { 57c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch PurgeFunctionHeuristicsMap(&functions); 58c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch function_heuristics_.erase(extension_id); 59c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch violators_.insert(extension_id); 60c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 61c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return global_decision; 62c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 63c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 64c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid ExtensionsQuotaService::PurgeFunctionHeuristicsMap( 65c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch FunctionHeuristicsMap* map) { 66c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch FunctionHeuristicsMap::iterator heuristics = map->begin(); 67c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch while (heuristics != map->end()) { 68c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch STLDeleteElements(&heuristics->second); 69c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch map->erase(heuristics++); 70c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 71c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 72c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 73c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid ExtensionsQuotaService::Purge() { 74c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch std::map<std::string, FunctionHeuristicsMap>::iterator it = 75c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch function_heuristics_.begin(); 76c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch for (; it != function_heuristics_.end(); function_heuristics_.erase(it++)) 77c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch PurgeFunctionHeuristicsMap(&it->second); 78c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 79c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 80c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid QuotaLimitHeuristic::Bucket::Reset(const Config& config, 81c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch const base::TimeTicks& start) { 82c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch num_tokens_ = config.refill_token_count; 83c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch expiration_ = start + config.refill_interval; 84c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 85c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 86731df977c0511bca2206b5f333555b1205ff1f43Iain MerrickQuotaLimitHeuristic::QuotaLimitHeuristic(const Config& config, 87731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick BucketMapper* map) 88731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick : config_(config), bucket_mapper_(map) { 89731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick} 90731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick 91731df977c0511bca2206b5f333555b1205ff1f43Iain MerrickQuotaLimitHeuristic::~QuotaLimitHeuristic() {} 92731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick 93c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochbool QuotaLimitHeuristic::ApplyToArgs(const ListValue* args, 94c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch const base::TimeTicks& event_time) { 95c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch BucketList buckets; 96c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch bucket_mapper_->GetBucketsForArgs(args, &buckets); 97c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch for (BucketList::iterator i = buckets.begin(); i != buckets.end(); ++i) { 98c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if ((*i)->expiration().is_null()) // A brand new bucket. 99c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch (*i)->Reset(config_, event_time); 100c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (!Apply(*i, event_time)) 101c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; // It only takes one to spoil it for everyone. 102c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 103c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return true; 104c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 105c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 106c407dc5cd9bdc5668497f21b26b09d988ab439deBen MurdochExtensionsQuotaService::SustainedLimit::SustainedLimit( 107c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch const base::TimeDelta& sustain, const Config& config, BucketMapper* map) 108c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch : QuotaLimitHeuristic(config, map), 109c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch repeat_exhaustion_allowance_(sustain.InSeconds() / 110c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch config.refill_interval.InSeconds()), 111c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch num_available_repeat_exhaustions_(repeat_exhaustion_allowance_) { 112c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 113c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 114c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochbool ExtensionsQuotaService::TimedLimit::Apply(Bucket* bucket, 115c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch const base::TimeTicks& event_time) { 116c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (event_time > bucket->expiration()) 117c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch bucket->Reset(config(), event_time); 118c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 119c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return bucket->DeductToken(); 120c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 121c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 122c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochbool ExtensionsQuotaService::SustainedLimit::Apply(Bucket* bucket, 123c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch const base::TimeTicks& event_time) { 124c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (event_time > bucket->expiration()) { 125c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // We reset state for this item and start over again if this request breaks 126c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // the bad cycle that was previously being tracked. This occurs if the 127c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // state in the bucket expired recently (it has been long enough since the 128c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // event that we don't care about the last event), but the bucket still has 129c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // tokens (so pressure was not sustained over that time), OR we are more 130c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // than 1 full refill interval away from the last event (so even if we used 131c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // up all the tokens in the last bucket, nothing happened in the entire 132c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // next refill interval, so it doesn't matter). 133c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (bucket->has_tokens() || event_time > bucket->expiration() + 134c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch config().refill_interval) { 135c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch bucket->Reset(config(), event_time); 136c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch num_available_repeat_exhaustions_ = repeat_exhaustion_allowance_; 137c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } else if (--num_available_repeat_exhaustions_ > 0) { 138c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // The last interval was saturated with requests, and this is the first 139c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // event in the next interval. If this happens 140c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // repeat_exhaustion_allowance_ times, it's a violation. Reset the bucket 141c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // state to start timing from the end of the last interval (and we'll 142c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // deduct the token below) so we can detect this each time it happens. 143c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch bucket->Reset(config(), bucket->expiration()); 144c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } else { 145c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // No allowances left; this request is a violation. 146c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return false; 147c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 148c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 149c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 150c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // We can go negative since we check has_tokens when we get to *next* bucket, 151c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // and for the small interval all that matters is whether we used up all the 152c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // tokens (which is true if num_tokens_ <= 0). 153c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch bucket->DeductToken(); 154c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch return true; 155c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 156