extensions/browser/quota_service.h

   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 // The QuotaService uses heuristics to limit abusive requests
   6 // made by extensions.  In this model 'items' (e.g individual bookmarks) are
   7 // represented by a 'Bucket' that holds state for that item for one single
   8 // interval of time.  The interval of time is defined as 'how long we need to
   9 // watch an item (for a particular heuristic) before making a decision about
  10 // quota violations'.  A heuristic is two functions: one mapping input
  11 // arguments to a unique Bucket (the BucketMapper), and another to determine
  12 // if a new request involving such an item at a given time is a violation.
  13
  14 #ifndef EXTENSIONS_BROWSER_QUOTA_SERVICE_H_
  15 #define EXTENSIONS_BROWSER_QUOTA_SERVICE_H_
  16
  17 #include <list>
  18 #include <map>
  19 #include <string>
  20
  21 #include "base/compiler_specific.h"
  22 #include "base/containers/hash_tables.h"
  23 #include "base/memory/scoped_ptr.h"
  24 #include "base/threading/non_thread_safe.h"
  25 #include "base/time/time.h"
  26 #include "base/timer/timer.h"
  27 #include "base/values.h"
  28
  29 class ExtensionFunction;
  30
  31 namespace extensions {
  32 class QuotaLimitHeuristic;
  33
  34 typedef std::list<QuotaLimitHeuristic*> QuotaLimitHeuristics;
  35
  36 // The QuotaService takes care that calls to certain extension
  37 // functions do not exceed predefined quotas.
  38 //
  39 // The QuotaService needs to live entirely on one thread, i.e. be created,
  40 // called and destroyed on the same thread, due to its use of a RepeatingTimer.
  41 // It is not a KeyedService because instances exist on both the UI
  42 // and IO threads.
  43 class QuotaService : public base::NonThreadSafe {
  44  public:
  45   // Some concrete heuristics (declared below) that ExtensionFunctions can
  46   // use to help the service make decisions about quota violations.
  47   class TimedLimit;
  48
  49   QuotaService();
  50   virtual ~QuotaService();
  51
  52   // Decide whether the invocation of |function| with argument |args| by the
  53   // extension specified by |extension_id| results in a quota limit violation.
  54   // Returns an error message representing the failure if quota was exceeded,
  55   // or empty-string if the request is fine and can proceed.
  56   std::string Assess(const std::string& extension_id,
  57                      ExtensionFunction* function,
  58                      const base::ListValue* args,
  59                      const base::TimeTicks& event_time);
  60
  61  private:
  62   typedef std::string ExtensionId;
  63   typedef std::string FunctionName;
  64   // All QuotaLimitHeuristic instances in this map are owned by us.
  65   typedef std::map<FunctionName, QuotaLimitHeuristics> FunctionHeuristicsMap;
  66
  67   // Purge resets all accumulated data as if the service was just created.
  68   // Called periodically so we don't consume an unbounded amount of memory
  69   // while tracking quota.
  70   void Purge();
  71   void PurgeFunctionHeuristicsMap(FunctionHeuristicsMap* map);
  72   base::RepeatingTimer<QuotaService> purge_timer_;
  73
  74   // Our quota tracking state for extensions that have invoked quota limited
  75   // functions.  Each extension is treated separately, so extension ids are the
  76   // key for the mapping.  As an extension invokes functions, the map keeps
  77   // track of which functions it has invoked and the heuristics for each one.
  78   // Each heuristic will be evaluated and ANDed together to get a final answer.
  79   std::map<ExtensionId, FunctionHeuristicsMap> function_heuristics_;
  80
  81   DISALLOW_COPY_AND_ASSIGN(QuotaService);
  82 };
  83
  84 // A QuotaLimitHeuristic is two things: 1, A heuristic to map extension
  85 // function arguments to corresponding Buckets for each input arg, and 2) a
  86 // heuristic for determining if a new event involving a particular item
  87 // (represented by its Bucket) constitutes a quota violation.
  88 class QuotaLimitHeuristic {
  89  public:
  90   // Parameters to configure the amount of tokens allotted to individual
  91   // Bucket objects (see Below) and how often they are replenished.
  92   struct Config {
  93     // The maximum number of tokens a bucket can contain, and is refilled to
  94     // every epoch.
  95     int64 refill_token_count;
  96
  97     // Specifies how frequently the bucket is logically refilled with tokens.
  98     base::TimeDelta refill_interval;
  99   };
 100
 101   // A Bucket is how the heuristic portrays an individual item (since quota
 102   // limits are per item) and all associated state for an item that needs to
 103   // carry through multiple calls to Apply.  It "holds" tokens, which are
 104   // debited and credited in response to new events involving the item being
 105   // being represented.  For convenience, instead of actually periodically
 106   // refilling buckets they are just 'Reset' on-demand (e.g. when new events
 107   // come in). So, a bucket has an expiration to denote it has becomes stale.
 108   class Bucket {
 109    public:
 110     Bucket() : num_tokens_(0) {}
 111     // Removes a token from this bucket, and returns true if the bucket had
 112     // any tokens in the first place.
 113     bool DeductToken() { return num_tokens_-- > 0; }
 114
 115     // Returns true if this bucket has tokens to deduct.
 116     bool has_tokens() const { return num_tokens_ > 0; }
 117
 118     // Reset this bucket to specification (from internal configuration), to be
 119     // valid from |start| until the first refill interval elapses and it needs
 120     // to be reset again.
 121     void Reset(const Config& config, const base::TimeTicks& start);
 122
 123     // The time at which the token count and next expiration should be reset,
 124     // via a call to Reset.
 125     const base::TimeTicks& expiration() { return expiration_; }
 126
 127    private:
 128     base::TimeTicks expiration_;
 129     int64 num_tokens_;
 130     DISALLOW_COPY_AND_ASSIGN(Bucket);
 131   };
 132   typedef std::list<Bucket*> BucketList;
 133
 134   // A helper interface to retrieve the bucket corresponding to |args| from
 135   // the set of buckets (which is typically stored in the BucketMapper itself)
 136   // for this QuotaLimitHeuristic.
 137   class BucketMapper {
 138    public:
 139     virtual ~BucketMapper() {}
 140     // In most cases, this should simply extract item IDs from the arguments
 141     // (e.g for bookmark operations involving an existing item). If a problem
 142     // occurs while parsing |args|, the function aborts - buckets may be non-
 143     // empty). The expectation is that invalid args and associated errors are
 144     // handled by the ExtensionFunction itself so we don't concern ourselves.
 145     virtual void GetBucketsForArgs(const base::ListValue* args,
 146                                    BucketList* buckets) = 0;
 147   };
 148
 149   // Maps all calls to the same bucket, regardless of |args|, for this
 150   // QuotaLimitHeuristic.
 151   class SingletonBucketMapper : public BucketMapper {
 152    public:
 153     SingletonBucketMapper() {}
 154     ~SingletonBucketMapper() override {}
 155     void GetBucketsForArgs(const base::ListValue* args,
 156                            BucketList* buckets) override;
 157
 158    private:
 159     Bucket bucket_;
 160     DISALLOW_COPY_AND_ASSIGN(SingletonBucketMapper);
 161   };
 162
 163   // Ownership of |map| is given to the new QuotaLimitHeuristic.
 164   QuotaLimitHeuristic(const Config& config,
 165                       BucketMapper* map,
 166                       const std::string& name);
 167   virtual ~QuotaLimitHeuristic();
 168
 169   // Determines if sufficient quota exists (according to the Apply
 170   // implementation of a derived class) to perform an operation with |args|,
 171   // based on the history of similar operations with similar arguments (which
 172   // is retrieved using the BucketMapper).
 173   bool ApplyToArgs(const base::ListValue* args,
 174                    const base::TimeTicks& event_time);
 175
 176   // Returns an error formatted according to this heuristic.
 177   std::string GetError() const;
 178
 179  protected:
 180   const Config& config() { return config_; }
 181
 182   // Determine if the new event occurring at |event_time| involving |bucket|
 183   // constitutes a quota violation according to this heuristic.
 184   virtual bool Apply(Bucket* bucket, const base::TimeTicks& event_time) = 0;
 185
 186  private:
 187   friend class QuotaLimitHeuristicTest;
 188
 189   const Config config_;
 190
 191   // The mapper used in Map. Cannot be NULL.
 192   scoped_ptr<BucketMapper> bucket_mapper_;
 193
 194   // The name of the heuristic for formatting error messages.
 195   std::string name_;
 196
 197   DISALLOW_COPY_AND_ASSIGN(QuotaLimitHeuristic);
 198 };
 199
 200 // A simple per-item heuristic to limit the number of events that can occur in
 201 // a given period of time; e.g "no more than 100 events in an hour".
 202 class QuotaService::TimedLimit : public QuotaLimitHeuristic {
 203  public:
 204   TimedLimit(const Config& config, BucketMapper* map, const std::string& name)
 205       : QuotaLimitHeuristic(config, map, name) {}
 206   bool Apply(Bucket* bucket, const base::TimeTicks& event_time) override;
 207 };
 208
 209 }  // namespace extensions
 210
 211 #endif  // EXTENSIONS_BROWSER_QUOTA_SERVICE_H_