// Copyright 2013 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

// The QuotaService uses heuristics to limit abusive requests
// made by extensions.  In this model 'items' (e.g individual bookmarks) are
// represented by a 'Bucket' that holds state for that item for one single
// interval of time.  The interval of time is defined as 'how long we need to
// watch an item (for a particular heuristic) before making a decision about
// quota violations'.  A heuristic is two functions: one mapping input
// arguments to a unique Bucket (the BucketMapper), and another to determine
// if a new request involving such an item at a given time is a violation.

#ifndef EXTENSIONS_BROWSER_QUOTA_SERVICE_H_
#define EXTENSIONS_BROWSER_QUOTA_SERVICE_H_

#include <list>
#include <map>
#include <string>

#include "base/compiler_specific.h"
#include "base/containers/hash_tables.h"
#include "base/memory/scoped_ptr.h"
#include "base/threading/non_thread_safe.h"
#include "base/time/time.h"
#include "base/timer/timer.h"
#include "base/values.h"

class ExtensionFunction;

namespace extensions {
class QuotaLimitHeuristic;
class TestResetQuotaFunction;

typedef std::list<QuotaLimitHeuristic*> QuotaLimitHeuristics;

// The QuotaService takes care that calls to certain extension
// functions do not exceed predefined quotas.
//
// The QuotaService needs to live entirely on one thread, i.e. be created,
// called and destroyed on the same thread, due to its use of a RepeatingTimer.
// It is not a KeyedService because instances exist on both the UI
// and IO threads.
class QuotaService : public base::NonThreadSafe {
 public:
  // Some concrete heuristics (declared below) that ExtensionFunctions can
  // use to help the service make decisions about quota violations.
  class TimedLimit;
  class SustainedLimit;

  QuotaService();
  virtual ~QuotaService();

  // Decide whether the invocation of |function| with argument |args| by the
  // extension specified by |extension_id| results in a quota limit violation.
  // Returns an error message representing the failure if quota was exceeded,
  // or empty-string if the request is fine and can proceed.
  std::string Assess(const std::string& extension_id,
                     ExtensionFunction* function,
                     const base::ListValue* args,
                     const base::TimeTicks& event_time);

 private:
  friend class extensions::TestResetQuotaFunction;
  typedef std::string ExtensionId;
  typedef std::string FunctionName;
  // All QuotaLimitHeuristic instances in this map are owned by us.
  typedef std::map<FunctionName, QuotaLimitHeuristics> FunctionHeuristicsMap;

  // Purge resets all accumulated data (except |violation_errors_|) as if the
  // service was just created. Called periodically so we don't consume an
  // unbounded amount of memory while tracking quota.  Yes, this could mean an
  // extension gets away with murder if it is timed right, but the extensions
  // we are trying to limit are ones that consistently violate, so we'll
  // converge to the correct set.
  void Purge();
  void PurgeFunctionHeuristicsMap(FunctionHeuristicsMap* map);
  base::RepeatingTimer<QuotaService> purge_timer_;

  // Our quota tracking state for extensions that have invoked quota limited
  // functions.  Each extension is treated separately, so extension ids are the
  // key for the mapping.  As an extension invokes functions, the map keeps
  // track of which functions it has invoked and the heuristics for each one.
  // Each heuristic will be evaluated and ANDed together to get a final answer.
  std::map<ExtensionId, FunctionHeuristicsMap> function_heuristics_;

  // For now, as soon as an extension violates quota, we don't allow it to
  // make any more requests to quota limited functions.  This provides a quick
  // lookup for these extensions that is only stored in memory.
  typedef std::map<std::string, std::string> ViolationErrorMap;
  ViolationErrorMap violation_errors_;

  DISALLOW_COPY_AND_ASSIGN(QuotaService);
};

// A QuotaLimitHeuristic is two things: 1, A heuristic to map extension
// function arguments to corresponding Buckets for each input arg, and 2) a
// heuristic for determining if a new event involving a particular item
// (represented by its Bucket) constitutes a quota violation.
class QuotaLimitHeuristic {
 public:
  // Parameters to configure the amount of tokens allotted to individual
  // Bucket objects (see Below) and how often they are replenished.
  struct Config {
    // The maximum number of tokens a bucket can contain, and is refilled to
    // every epoch.
    int64 refill_token_count;

    // Specifies how frequently the bucket is logically refilled with tokens.
    base::TimeDelta refill_interval;
  };

  // A Bucket is how the heuristic portrays an individual item (since quota
  // limits are per item) and all associated state for an item that needs to
  // carry through multiple calls to Apply.  It "holds" tokens, which are
  // debited and credited in response to new events involving the item being
  // being represented.  For convenience, instead of actually periodically
  // refilling buckets they are just 'Reset' on-demand (e.g. when new events
  // come in). So, a bucket has an expiration to denote it has becomes stale.
  class Bucket {
   public:
    Bucket() : num_tokens_(0) {}
    // Removes a token from this bucket, and returns true if the bucket had
    // any tokens in the first place.
    bool DeductToken() { return num_tokens_-- > 0; }

    // Returns true if this bucket has tokens to deduct.
    bool has_tokens() const { return num_tokens_ > 0; }

    // Reset this bucket to specification (from internal configuration), to be
    // valid from |start| until the first refill interval elapses and it needs
    // to be reset again.
    void Reset(const Config& config, const base::TimeTicks& start);

    // The time at which the token count and next expiration should be reset,
    // via a call to Reset.
    const base::TimeTicks& expiration() { return expiration_; }

   private:
    base::TimeTicks expiration_;
    int64 num_tokens_;
    DISALLOW_COPY_AND_ASSIGN(Bucket);
  };
  typedef std::list<Bucket*> BucketList;

  // A helper interface to retrieve the bucket corresponding to |args| from
  // the set of buckets (which is typically stored in the BucketMapper itself)
  // for this QuotaLimitHeuristic.
  class BucketMapper {
   public:
    virtual ~BucketMapper() {}
    // In most cases, this should simply extract item IDs from the arguments
    // (e.g for bookmark operations involving an existing item). If a problem
    // occurs while parsing |args|, the function aborts - buckets may be non-
    // empty). The expectation is that invalid args and associated errors are
    // handled by the ExtensionFunction itself so we don't concern ourselves.
    virtual void GetBucketsForArgs(const base::ListValue* args,
                                   BucketList* buckets) = 0;
  };

  // Maps all calls to the same bucket, regardless of |args|, for this
  // QuotaLimitHeuristic.
  class SingletonBucketMapper : public BucketMapper {
   public:
    SingletonBucketMapper() {}
    virtual ~SingletonBucketMapper() {}
    virtual void GetBucketsForArgs(const base::ListValue* args,
                                   BucketList* buckets) OVERRIDE;

   private:
    Bucket bucket_;
    DISALLOW_COPY_AND_ASSIGN(SingletonBucketMapper);
  };

  // Ownership of |map| is given to the new QuotaLimitHeuristic.
  QuotaLimitHeuristic(const Config& config,
                      BucketMapper* map,
                      const std::string& name);
  virtual ~QuotaLimitHeuristic();

  // Determines if sufficient quota exists (according to the Apply
  // implementation of a derived class) to perform an operation with |args|,
  // based on the history of similar operations with similar arguments (which
  // is retrieved using the BucketMapper).
  bool ApplyToArgs(const base::ListValue* args,
                   const base::TimeTicks& event_time);

  // Returns an error formatted according to this heuristic.
  std::string GetError() const;

 protected:
  const Config& config() { return config_; }

  // Determine if the new event occurring at |event_time| involving |bucket|
  // constitutes a quota violation according to this heuristic.
  virtual bool Apply(Bucket* bucket, const base::TimeTicks& event_time) = 0;

 private:
  friend class QuotaLimitHeuristicTest;

  const Config config_;

  // The mapper used in Map. Cannot be NULL.
  scoped_ptr<BucketMapper> bucket_mapper_;

  // The name of the heuristic for formatting error messages.
  std::string name_;

  DISALLOW_COPY_AND_ASSIGN(QuotaLimitHeuristic);
};

// A simple per-item heuristic to limit the number of events that can occur in
// a given period of time; e.g "no more than 100 events in an hour".
class QuotaService::TimedLimit : public QuotaLimitHeuristic {
 public:
  TimedLimit(const Config& config, BucketMapper* map, const std::string& name)
      : QuotaLimitHeuristic(config, map, name) {}
  virtual bool Apply(Bucket* bucket,
                     const base::TimeTicks& event_time) OVERRIDE;
};

// A per-item heuristic to limit the number of events that can occur in a
// period of time over a sustained longer interval. E.g "no more than two
// events per minute, sustained over 10 minutes".
class QuotaService::SustainedLimit : public QuotaLimitHeuristic {
 public:
  SustainedLimit(const base::TimeDelta& sustain,
                 const Config& config,
                 BucketMapper* map,
                 const std::string& name);
  virtual bool Apply(Bucket* bucket,
                     const base::TimeTicks& event_time) OVERRIDE;

 private:
  // Specifies how long exhaustion of buckets is allowed to continue before
  // denying requests.
  const int64 repeat_exhaustion_allowance_;
  int64 num_available_repeat_exhaustions_;
};

}  // namespace extensions

#endif  // EXTENSIONS_BROWSER_QUOTA_SERVICE_H_