1f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)// Copyright 2013 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)#include "extensions/browser/quota_service.h" 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch#include "base/message_loop/message_loop.h" 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/stl_util.h" 9f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)#include "extensions/browser/extension_function.h" 102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "extensions/common/error_utils.h" 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// If the browser stays open long enough, we reset state once a day. 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Whatever this value is, it should be an order of magnitude longer than 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the longest interval in any of the QuotaLimitHeuristics in use. 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const int kPurgeIntervalInDays = 1; 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const char kOverQuotaError[] = "This request exceeds the * quota."; 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 23f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)namespace extensions { 24f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 25f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)QuotaService::QuotaService() { 2690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (base::MessageLoop::current() != NULL) { // Null in unit tests. 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) purge_timer_.Start(FROM_HERE, 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::TimeDelta::FromDays(kPurgeIntervalInDays), 29f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) this, 30f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) &QuotaService::Purge); 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 34f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)QuotaService::~QuotaService() { 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(CalledOnValidThread()); 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) purge_timer_.Stop(); 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Purge(); 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 40f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)std::string QuotaService::Assess(const std::string& extension_id, 41f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) ExtensionFunction* function, 42f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) const base::ListValue* args, 43f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) const base::TimeTicks& event_time) { 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(CalledOnValidThread()); 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (function->ShouldSkipQuotaLimiting()) 47c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return std::string(); 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Lookup function list for extension. 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FunctionHeuristicsMap& functions = function_heuristics_[extension_id]; 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Lookup heuristics for function, create if necessary. 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) QuotaLimitHeuristics& heuristics = functions[function->name()]; 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (heuristics.empty()) 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) function->GetQuotaLimitHeuristics(&heuristics); 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (heuristics.empty()) 58c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return std::string(); // No heuristic implies no limit. 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ViolationErrorMap::iterator violation_error = 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) violation_errors_.find(extension_id); 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (violation_error != violation_errors_.end()) 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return violation_error->second; // Repeat offender. 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) QuotaLimitHeuristic* failed_heuristic = NULL; 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (QuotaLimitHeuristics::iterator heuristic = heuristics.begin(); 67f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) heuristic != heuristics.end(); 68f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) ++heuristic) { 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Apply heuristic to each item (bucket). 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!(*heuristic)->ApplyToArgs(args, event_time)) { 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) failed_heuristic = *heuristic; 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!failed_heuristic) 77c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return std::string(); 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::string error = failed_heuristic->GetError(); 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_GT(error.length(), 0u); 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PurgeFunctionHeuristicsMap(&functions); 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) function_heuristics_.erase(extension_id); 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) violation_errors_[extension_id] = error; 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return error; 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 88f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)void QuotaService::PurgeFunctionHeuristicsMap(FunctionHeuristicsMap* map) { 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FunctionHeuristicsMap::iterator heuristics = map->begin(); 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (heuristics != map->end()) { 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) STLDeleteElements(&heuristics->second); 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) map->erase(heuristics++); 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 96f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)void QuotaService::Purge() { 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(CalledOnValidThread()); 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::map<std::string, FunctionHeuristicsMap>::iterator it = 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) function_heuristics_.begin(); 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (; it != function_heuristics_.end(); function_heuristics_.erase(it++)) 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PurgeFunctionHeuristicsMap(&it->second); 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void QuotaLimitHeuristic::Bucket::Reset(const Config& config, 105f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) const base::TimeTicks& start) { 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) num_tokens_ = config.refill_token_count; 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) expiration_ = start + config.refill_interval; 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void QuotaLimitHeuristic::SingletonBucketMapper::GetBucketsForArgs( 111eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch const base::ListValue* args, 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BucketList* buckets) { 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) buckets->push_back(&bucket_); 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)QuotaLimitHeuristic::QuotaLimitHeuristic(const Config& config, 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BucketMapper* map, 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const std::string& name) 119f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) : config_(config), bucket_mapper_(map), name_(name) {} 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)QuotaLimitHeuristic::~QuotaLimitHeuristic() {} 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 123eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdochbool QuotaLimitHeuristic::ApplyToArgs(const base::ListValue* args, 124f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) const base::TimeTicks& event_time) { 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BucketList buckets; 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bucket_mapper_->GetBucketsForArgs(args, &buckets); 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (BucketList::iterator i = buckets.begin(); i != buckets.end(); ++i) { 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((*i)->expiration().is_null()) // A brand new bucket. 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (*i)->Reset(config_, event_time); 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!Apply(*i, event_time)) 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; // It only takes one to spoil it for everyone. 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)std::string QuotaLimitHeuristic::GetError() const { 1372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return extensions::ErrorUtils::FormatErrorMessage(kOverQuotaError, name_); 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 140f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)QuotaService::SustainedLimit::SustainedLimit(const base::TimeDelta& sustain, 141f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) const Config& config, 142f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) BucketMapper* map, 143f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) const std::string& name) 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : QuotaLimitHeuristic(config, map, name), 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) repeat_exhaustion_allowance_(sustain.InSeconds() / 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) config.refill_interval.InSeconds()), 147f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) num_available_repeat_exhaustions_(repeat_exhaustion_allowance_) {} 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 149f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)bool QuotaService::TimedLimit::Apply(Bucket* bucket, 150f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) const base::TimeTicks& event_time) { 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (event_time > bucket->expiration()) 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bucket->Reset(config(), event_time); 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return bucket->DeductToken(); 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 157f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)bool QuotaService::SustainedLimit::Apply(Bucket* bucket, 158f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) const base::TimeTicks& event_time) { 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (event_time > bucket->expiration()) { 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We reset state for this item and start over again if this request breaks 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the bad cycle that was previously being tracked. This occurs if the 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // state in the bucket expired recently (it has been long enough since the 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // event that we don't care about the last event), but the bucket still has 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // tokens (so pressure was not sustained over that time), OR we are more 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // than 1 full refill interval away from the last event (so even if we used 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // up all the tokens in the last bucket, nothing happened in the entire 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // next refill interval, so it doesn't matter). 168f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) if (bucket->has_tokens() || 169f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) event_time > bucket->expiration() + config().refill_interval) { 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bucket->Reset(config(), event_time); 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) num_available_repeat_exhaustions_ = repeat_exhaustion_allowance_; 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (--num_available_repeat_exhaustions_ > 0) { 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The last interval was saturated with requests, and this is the first 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // event in the next interval. If this happens 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // repeat_exhaustion_allowance_ times, it's a violation. Reset the bucket 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // state to start timing from the end of the last interval (and we'll 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // deduct the token below) so we can detect this each time it happens. 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bucket->Reset(config(), bucket->expiration()); 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // No allowances left; this request is a violation. 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We can go negative since we check has_tokens when we get to *next* bucket, 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and for the small interval all that matters is whether we used up all the 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // tokens (which is true if num_tokens_ <= 0). 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bucket->DeductToken(); 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 191f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 192f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)} // namespace extensions 193