Add ExtensionsQuotaService to limit abusive amounts of requests

to mutating extension functions, as discussed on chromium-dev and
in Extensions quotaserver design doc.

Add a hook in the dispatcher to have the quota service assess the request.

Wire up bookmarks.{create, move, remove, update} to the service.

BUG=19899
TEST=ExtensionsQuotaServiceTest, QuotaLimitHeuristicTest (both new)

Review URL: http://codereview.chromium.org/441006

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@33770 0039d316-1c4b-4281-b951-d872f2087c98

16 files changed, 1146 insertions, 59 deletions

diff --git a/chrome/browser/extensions/extension_bookmarks_module.cc b/chrome/browser/extensions/extension_bookmarks_module.cc
index 0029702..9ae6ff9 100644
--- a/chrome/browser/extensions/extension_bookmarks_module.cc
+++ b/chrome/browser/extensions/extension_bookmarks_module.cc
@@ -5,6 +5,8 @@
 #include "chrome/browser/extensions/extension_bookmarks_module.h"
 
 #include "base/json/json_writer.h"
+#include "base/sha1.h"
+#include "base/stl_util-inl.h"
 #include "base/string_util.h"
 #include "chrome/browser/bookmarks/bookmark_codec.h"
 #include "chrome/browser/bookmarks/bookmark_model.h"
@@ -12,6 +14,7 @@
 #include "chrome/browser/browser_list.h"
 #include "chrome/browser/extensions/extension_bookmarks_module_constants.h"
 #include "chrome/browser/extensions/extension_message_service.h"
+#include "chrome/browser/extensions/extensions_quota_service.h"
 #include "chrome/browser/profile.h"
 #include "chrome/common/notification_service.h"
 #include "chrome/common/pref_names.h"
@@ -19,6 +22,14 @@
 
 namespace keys = extension_bookmarks_module_constants;
 
+using base::TimeDelta;
+typedef QuotaLimitHeuristic::Bucket Bucket;
+typedef QuotaLimitHeuristic::Config Config;
+typedef QuotaLimitHeuristic::BucketList BucketList;
+typedef ExtensionsQuotaService::TimedLimit TimedLimit;
+typedef ExtensionsQuotaService::SustainedLimit SustainedLimit;
+typedef QuotaLimitHeuristic::BucketMapper BucketMapper;
+
 // Helper functions.
 class ExtensionBookmarks {
  public:
@@ -360,32 +371,59 @@ bool SearchBookmarksFunction::RunImpl() {
   return true;
 }
 
+// static
+bool RemoveBookmarkFunction::ExtractIds(const Value* args,
+    std::list<int64>* ids, bool* invalid_id) {
+  std::string id_string;
+  if (args->IsType(Value::TYPE_STRING) &&
+      args->GetAsString(&id_string)) {
+    int64 id;
+    if (StringToInt64(id_string, &id))
+      ids->push_back(id);
+    else
+      *invalid_id = true;
+  } else {
+    if (!args->IsType(Value::TYPE_LIST))
+      return false;
+    const ListValue* ids_list = static_cast<const ListValue*>(args);
+    size_t count = ids_list->GetSize();
+    if (count <= 0)
+      return false;
+    for (size_t i = 0; i < count; ++i) {
+      if (!ids_list->GetString(i, &id_string))
+        return false;
+      int64 id;
+      if (StringToInt64(id_string, &id)) {
+        ids->push_back(id);
+      } else {
+        *invalid_id = true;
+        break;
+      }
+    }
+  }
+  return true;
+}
+
 bool RemoveBookmarkFunction::RunImpl() {
+  std::list<int64> ids;
+  bool invalid_id = false;
+  EXTENSION_FUNCTION_VALIDATE(ExtractIds(args_.get(), &ids, &invalid_id));
+  if (invalid_id) {
+    error_ = keys::kInvalidIdError;
+    return false;
+  }
   bool recursive = false;
   if (name() == RemoveTreeBookmarkFunction::function_name())
     recursive = true;
 
   BookmarkModel* model = profile()->GetBookmarkModel();
-  int64 id;
-  std::string id_string;
-  if (args_->IsType(Value::TYPE_STRING) &&
-      args_->GetAsString(&id_string) &&
-      StringToInt64(id_string, &id)) {
-    return ExtensionBookmarks::RemoveNode(model, id, recursive, &error_);
-  } else {
-    EXTENSION_FUNCTION_VALIDATE(args_->IsType(Value::TYPE_LIST));
-    const ListValue* ids = args_as_list();
-    size_t count = ids->GetSize();
-    EXTENSION_FUNCTION_VALIDATE(count > 0);
-    for (size_t i = 0; i < count; ++i) {
-      EXTENSION_FUNCTION_VALIDATE(ids->GetString(i, &id_string));
-      if (!GetBookmarkIdAsInt64(id_string, &id))
-        return false;
-      if (!ExtensionBookmarks::RemoveNode(model, id, recursive, &error_))
-        return false;
-    }
-    return true;
+  size_t count = ids.size();
+  EXTENSION_FUNCTION_VALIDATE(count > 0);
+  for (std::list<int64>::iterator it = ids.begin(); it != ids.end(); ++it) {
+    if (!ExtensionBookmarks::RemoveNode(model, *it, recursive, &error_))
+      return false;
   }
+  return true;
 }
 
 bool CreateBookmarkFunction::RunImpl() {
@@ -452,19 +490,30 @@ bool CreateBookmarkFunction::RunImpl() {
   return true;
 }
 
+// static
+bool MoveBookmarkFunction::ExtractIds(const Value* args,
+                                      std::list<int64>* ids,
+                                      bool* invalid_id) {
+  // For now, Move accepts ID parameters in the same way as an Update.
+  return UpdateBookmarkFunction::ExtractIds(args, ids, invalid_id);
+}
+
 bool MoveBookmarkFunction::RunImpl() {
-  EXTENSION_FUNCTION_VALIDATE(args_->IsType(Value::TYPE_LIST));
-  const ListValue* args = args_as_list();
-  int64 id;
-  std::string id_string;
-  EXTENSION_FUNCTION_VALIDATE(args->GetString(0, &id_string));
-  if (!GetBookmarkIdAsInt64(id_string, &id))
+  std::list<int64> ids;
+  bool invalid_id = false;
+  EXTENSION_FUNCTION_VALIDATE(ExtractIds(args_.get(), &ids, &invalid_id));
+  if (invalid_id) {
+    error_ = keys::kInvalidIdError;
     return false;
+  }
+  EXTENSION_FUNCTION_VALIDATE(ids.size() == 1);
+  const ListValue* args = args_as_list();
+
   DictionaryValue* destination;
   EXTENSION_FUNCTION_VALIDATE(args->GetDictionary(1, &destination));
 
   BookmarkModel* model = profile()->GetBookmarkModel();
-  const BookmarkNode* node = model->GetNodeByID(id);
+  const BookmarkNode* node = model->GetNodeByID(ids.front());
   if (!node) {
     error_ = keys::kNoNodeError;
     return false;
@@ -520,21 +569,42 @@ bool MoveBookmarkFunction::RunImpl() {
   return true;
 }
 
-bool UpdateBookmarkFunction::RunImpl() {
-  EXTENSION_FUNCTION_VALIDATE(args_->IsType(Value::TYPE_LIST));
-  const ListValue* args = args_as_list();
-  int64 id;
+// static
+bool UpdateBookmarkFunction::ExtractIds(const Value* args,
+                                        std::list<int64>* ids,
+                                        bool* invalid_id) {
   std::string id_string;
-  EXTENSION_FUNCTION_VALIDATE(args->GetString(0, &id_string));
-  if (!GetBookmarkIdAsInt64(id_string, &id))
+  if (!args->IsType(Value::TYPE_LIST))
+    return false;
+  const ListValue* args_list = static_cast<const ListValue*>(args);
+  if (!args_list->GetString(0, &id_string))
     return false;
+  int64 id;
+  if (StringToInt64(id_string, &id))
+    ids->push_back(id);
+  else
+    *invalid_id = true;
+  return true;
+}
+
+bool UpdateBookmarkFunction::RunImpl() {
+  std::list<int64> ids;
+  bool invalid_id = false;
+  EXTENSION_FUNCTION_VALIDATE(ExtractIds(args_.get(), &ids, &invalid_id));
+  if (invalid_id) {
+    error_ = keys::kInvalidIdError;
+    return false;
+  }
+  EXTENSION_FUNCTION_VALIDATE(ids.size() == 1);
+
+  const ListValue* args = args_as_list();
   DictionaryValue* updates;
   EXTENSION_FUNCTION_VALIDATE(args->GetDictionary(1, &updates));
   std::wstring title;
   updates->GetString(keys::kTitleKey, &title);  // Optional (empty is clear).
 
   BookmarkModel* model = profile()->GetBookmarkModel();
-  const BookmarkNode* node = model->GetNodeByID(id);
+  const BookmarkNode* node = model->GetNodeByID(ids.front());
   if (!node) {
     error_ = keys::kNoNodeError;
     return false;
@@ -552,3 +622,180 @@ bool UpdateBookmarkFunction::RunImpl() {
 
   return true;
 }
+
+// Mapper superclass for BookmarkFunctions.
+template <typename BucketIdType>
+class BookmarkBucketMapper : public BucketMapper {
+ public:
+  virtual ~BookmarkBucketMapper() { STLDeleteValues(&buckets_); }
+ protected:
+  Bucket* GetBucket(const BucketIdType& id) {
+    Bucket* b = buckets_[id];
+    if (b == NULL) {
+      b = new Bucket();
+      buckets_[id] = b;
+    }
+    return b;
+  }
+ private:
+  std::map<BucketIdType, Bucket*> buckets_;
+};
+
+// Mapper for 'bookmarks.create'.  Maps "same input to bookmarks.create" to a
+// unique bucket.
+class CreateBookmarkBucketMapper : public BookmarkBucketMapper<std::string> {
+ public:
+  explicit CreateBookmarkBucketMapper(Profile* profile) : profile_(profile) {}
+  // TODO(tim): This should share code with CreateBookmarkFunction::RunImpl,
+  // but I can't figure out a good way to do that with all the macros.
+  virtual void GetBucketsForArgs(const Value* args, BucketList* buckets) {
+    if (!args->IsType(Value::TYPE_DICTIONARY))
+      return;
+
+    std::string parent_id;
+    const DictionaryValue* json = static_cast<const DictionaryValue*>(args);
+    if (json->HasKey(keys::kParentIdKey)) {
+      if (!json->GetString(keys::kParentIdKey, &parent_id))
+        return;
+    }
+    BookmarkModel* model = profile_->GetBookmarkModel();
+    const BookmarkNode* parent = model->GetNodeByID(StringToInt64(parent_id));
+    if (!parent)
+      return;
+
+    std::string bucket_id = WideToUTF8(parent->GetTitle());
+    std::wstring title;
+    json->GetString(keys::kTitleKey, &title);
+    std::string url_string;
+    json->GetString(keys::kUrlKey, &url_string);
+
+    bucket_id += WideToUTF8(title);
+    bucket_id += url_string;
+    // 20 bytes (SHA1 hash length) is very likely less than most of the
+    // |bucket_id| strings we construct here, so we hash it to save space.
+    buckets->push_back(GetBucket(base::SHA1HashString(bucket_id)));
+  }
+ private:
+  Profile* profile_;
+};
+
+// Mapper for 'bookmarks.remove'.
+class RemoveBookmarksBucketMapper : public BookmarkBucketMapper<std::string> {
+ public:
+  explicit RemoveBookmarksBucketMapper(Profile* profile) : profile_(profile) {}
+  virtual void GetBucketsForArgs(const Value* args, BucketList* buckets) {
+    typedef std::list<int64> IdList;
+    IdList ids;
+    bool invalid_id = false;
+    if (!RemoveBookmarkFunction::ExtractIds(args, &ids, &invalid_id) ||
+        invalid_id) {
+      return;
+    }
+
+    for (IdList::iterator it = ids.begin(); it != ids.end(); ++it) {
+      BookmarkModel* model = profile_->GetBookmarkModel();
+      const BookmarkNode* node = model->GetNodeByID(*it);
+      if (!node || !node->GetParent())
+        return;
+
+      std::string bucket_id;
+      bucket_id += WideToUTF8(node->GetParent()->GetTitle());
+      bucket_id += WideToUTF8(node->GetTitle());
+      bucket_id += node->GetURL().spec();
+      buckets->push_back(GetBucket(base::SHA1HashString(bucket_id)));
+    }
+  }
+ private:
+  Profile* profile_;
+};
+
+// Mapper for any bookmark function accepting bookmark IDs as parameters, where
+// a distinct ID corresponds to a single item in terms of quota limiting.  This
+// is inappropriate for bookmarks.remove, for example, since repeated removals
+// of the same item will actually have a different ID each time.
+template <class FunctionType>
+class BookmarkIdMapper : public BookmarkBucketMapper<int64> {
+ public:
+  typedef std::list<int64> IdList;
+  virtual void GetBucketsForArgs(const Value* args, BucketList* buckets) {
+    IdList ids;
+    bool invalid_id = false;
+    if (!FunctionType::ExtractIds(args, &ids, &invalid_id) || invalid_id)
+      return;
+    for (IdList::iterator it = ids.begin(); it != ids.end(); ++it)
+      buckets->push_back(GetBucket(*it));
+  }
+};
+
+// Builds heuristics for all BookmarkFunctions using specialized BucketMappers.
+class BookmarksQuotaLimitFactory {
+ public:
+  // For id-based bookmark functions.
+  template <class FunctionType>
+  static void Build(QuotaLimitHeuristics* heuristics) {
+    BuildWithMappers(heuristics, new BookmarkIdMapper<FunctionType>(),
+                                 new BookmarkIdMapper<FunctionType>());
+  }
+
+  // For bookmarks.create.
+  static void BuildForCreate(QuotaLimitHeuristics* heuristics,
+                             Profile* profile) {
+    BuildWithMappers(heuristics, new CreateBookmarkBucketMapper(profile),
+                                 new CreateBookmarkBucketMapper(profile));
+  }
+
+  // For bookmarks.remove.
+  static void BuildForRemove(QuotaLimitHeuristics* heuristics,
+                             Profile* profile) {
+    BuildWithMappers(heuristics, new RemoveBookmarksBucketMapper(profile),
+                                 new RemoveBookmarksBucketMapper(profile));
+  }
+
+ private:
+  static void BuildWithMappers(QuotaLimitHeuristics* heuristics,
+      BucketMapper* short_mapper, BucketMapper* long_mapper) {
+    TimedLimit* timed = new TimedLimit(kLongLimitConfig, long_mapper);
+    // A max of two operations per minute, sustained over 10 minutes.
+    SustainedLimit* sustained = new SustainedLimit(TimeDelta::FromMinutes(10),
+        kShortLimitConfig, short_mapper);
+    heuristics->push_back(timed);
+    heuristics->push_back(sustained);
+  }
+
+  // The quota configurations used for all BookmarkFunctions.
+  static const Config kShortLimitConfig;
+  static const Config kLongLimitConfig;
+
+  DISALLOW_IMPLICIT_CONSTRUCTORS(BookmarksQuotaLimitFactory);
+};
+
+const Config BookmarksQuotaLimitFactory::kShortLimitConfig = {
+  2,                         // 2 tokens per interval.
+  TimeDelta::FromMinutes(1)  // 1 minute long refill interval.
+};
+
+const Config BookmarksQuotaLimitFactory::kLongLimitConfig = {
+  100,                       // 100 tokens per interval.
+  TimeDelta::FromHours(1)    // 1 hour long refill interval.
+};
+
+// And finally, building the individual heuristics for each function.
+void RemoveBookmarkFunction::GetQuotaLimitHeuristics(
+    QuotaLimitHeuristics* heuristics) const {
+  BookmarksQuotaLimitFactory::BuildForRemove(heuristics, profile());
+}
+
+void MoveBookmarkFunction::GetQuotaLimitHeuristics(
+    QuotaLimitHeuristics* heuristics) const {
+  BookmarksQuotaLimitFactory::Build<MoveBookmarkFunction>(heuristics);
+}
+
+void UpdateBookmarkFunction::GetQuotaLimitHeuristics(
+    QuotaLimitHeuristics* heuristics) const {
+  BookmarksQuotaLimitFactory::Build<UpdateBookmarkFunction>(heuristics);
+};
+
+void CreateBookmarkFunction::GetQuotaLimitHeuristics(
+    QuotaLimitHeuristics* heuristics) const {
+  BookmarksQuotaLimitFactory::BuildForCreate(heuristics, profile());
+}
diff --git a/chrome/browser/extensions/extension_bookmarks_module.h b/chrome/browser/extensions/extension_bookmarks_module.h
index acaf91d..42b780c 100644
--- a/chrome/browser/extensions/extension_bookmarks_module.h
+++ b/chrome/browser/extensions/extension_bookmarks_module.h
@@ -5,6 +5,7 @@
 #ifndef CHROME_BROWSER_EXTENSIONS_EXTENSION_BOOKMARKS_MODULE_H_
 #define CHROME_BROWSER_EXTENSIONS_EXTENSION_BOOKMARKS_MODULE_H_
 
+#include <list>
 #include <string>
 
 #include "base/singleton.h"
@@ -64,6 +65,7 @@ class ExtensionBookmarkEventRouter : public BookmarkModelObserver {
 
 class BookmarksFunction : public AsyncExtensionFunction,
                           public NotificationObserver {
+ public:
   virtual void Run();
   virtual bool RunImpl() = 0;
 
@@ -81,27 +83,43 @@ class BookmarksFunction : public AsyncExtensionFunction,
 };
 
 class GetBookmarksFunction : public BookmarksFunction {
+ public:
   virtual bool RunImpl();
+ private:
   DECLARE_EXTENSION_FUNCTION_NAME("bookmarks.get")
 };
 
 class GetBookmarkChildrenFunction : public BookmarksFunction {
+ public:
   virtual bool RunImpl();
+ private:
   DECLARE_EXTENSION_FUNCTION_NAME("bookmarks.getChildren")
 };
 
 class GetBookmarkTreeFunction : public BookmarksFunction {
+ public:
   virtual bool RunImpl();
+ private:
   DECLARE_EXTENSION_FUNCTION_NAME("bookmarks.getTree")
 };
 
 class SearchBookmarksFunction : public BookmarksFunction {
+ public:
   virtual bool RunImpl();
+ private:
   DECLARE_EXTENSION_FUNCTION_NAME("bookmarks.search")
 };
 
 class RemoveBookmarkFunction : public BookmarksFunction {
+ public:
+  // Returns true on successful parse and sets invalid_id to true if conversion
+  // from id string to int64 failed.
+  static bool ExtractIds(const Value* args, std::list<int64>* ids,
+                         bool* invalid_id);
   virtual bool RunImpl();
+  virtual void GetQuotaLimitHeuristics(
+      std::list<QuotaLimitHeuristic*>* heuristics) const;
+ private:
   DECLARE_EXTENSION_FUNCTION_NAME("bookmarks.remove")
 };
 
@@ -110,17 +128,33 @@ class RemoveTreeBookmarkFunction : public RemoveBookmarkFunction {
 };
 
 class CreateBookmarkFunction : public BookmarksFunction {
+ public:
+  virtual void GetQuotaLimitHeuristics(
+      std::list<QuotaLimitHeuristic*>* heuristics) const;
   virtual bool RunImpl();
+ private:
   DECLARE_EXTENSION_FUNCTION_NAME("bookmarks.create")
 };
 
 class MoveBookmarkFunction : public BookmarksFunction {
+ public:
+  static bool ExtractIds(const Value* args, std::list<int64>* ids,
+                         bool* invalid_id);
+  virtual void GetQuotaLimitHeuristics(
+      std::list<QuotaLimitHeuristic*>* heuristics) const;
   virtual bool RunImpl();
+ private:
   DECLARE_EXTENSION_FUNCTION_NAME("bookmarks.move")
 };
 
 class UpdateBookmarkFunction : public BookmarksFunction {
+ public:
+  static bool ExtractIds(const Value* args, std::list<int64>* ids,
+                         bool* invalid_id);
+  virtual void GetQuotaLimitHeuristics(
+      std::list<QuotaLimitHeuristic*>* heuristics) const;
   virtual bool RunImpl();
+ private:
   DECLARE_EXTENSION_FUNCTION_NAME("bookmarks.update")
 };
 
diff --git a/chrome/browser/extensions/extension_function.cc b/chrome/browser/extensions/extension_function.cc
index 27ce5eb..006fe99 100644
--- a/chrome/browser/extensions/extension_function.cc
+++ b/chrome/browser/extensions/extension_function.cc
@@ -36,7 +36,7 @@ std::string AsyncExtensionFunction::extension_id() {
   return dispatcher()->extension_id();
 }
 
-Profile* AsyncExtensionFunction::profile() {
+Profile* AsyncExtensionFunction::profile() const {
   DCHECK(dispatcher());
   return dispatcher()->profile();
 }
diff --git a/chrome/browser/extensions/extension_function.h b/chrome/browser/extensions/extension_function.h
index be74f36..6db6443 100644
--- a/chrome/browser/extensions/extension_function.h
+++ b/chrome/browser/extensions/extension_function.h
@@ -6,6 +6,7 @@
 #define CHROME_BROWSER_EXTENSIONS_EXTENSION_FUNCTION_H_
 
 #include <string>
+#include <list>
 
 #include "base/values.h"
 #include "base/scoped_ptr.h"
@@ -14,6 +15,7 @@
 
 class ExtensionFunctionDispatcher;
 class Profile;
+class QuotaLimitHeuristic;
 
 #define EXTENSION_FUNCTION_VALIDATE(test) do { \
     if (!(test)) { \
@@ -48,10 +50,15 @@ class ExtensionFunction : public base::RefCounted<ExtensionFunction> {
   // Retrieves any error string from the function.
   virtual const std::string GetError() = 0;
 
+  // Returns a quota limit heuristic suitable for this function.
+  // No quota limiting by default.
+  virtual void GetQuotaLimitHeuristics(
+      std::list<QuotaLimitHeuristic*>* heuristics) const {}
+
   void set_dispatcher_peer(ExtensionFunctionDispatcher::Peer* peer) {
     peer_ = peer;
   }
-  ExtensionFunctionDispatcher* dispatcher() {
+  ExtensionFunctionDispatcher* dispatcher() const {
     return peer_->dispatcher_;
   }
 
@@ -134,7 +141,7 @@ class AsyncExtensionFunction : public ExtensionFunction {
   // Note: After Run() returns, dispatcher() can be NULL.  Since these getters
   // rely on dispatcher(), make sure it is valid before using them.
   std::string extension_id();
-  Profile* profile();
+  Profile* profile() const;
 
   // The arguments to the API. Only non-null if argument were specified.
   scoped_ptr<Value> args_;
diff --git a/chrome/browser/extensions/extension_function_dispatcher.cc b/chrome/browser/extensions/extension_function_dispatcher.cc
index 3a99e37..071c6f1 100644
--- a/chrome/browser/extensions/extension_function_dispatcher.cc
+++ b/chrome/browser/extensions/extension_function_dispatcher.cc
@@ -24,6 +24,7 @@
 #include "chrome/browser/extensions/extension_tabs_module_constants.h"
 #include "chrome/browser/extensions/extension_test_api.h"
 #include "chrome/browser/extensions/extension_toolstrip_api.h"
+#include "chrome/browser/extensions/extensions_quota_service.h"
 #include "chrome/browser/extensions/extensions_service.h"
 #include "chrome/browser/profile.h"
 #include "chrome/browser/renderer_host/render_process_host.h"
@@ -149,6 +150,7 @@ void FactoryRegistry::ResetFunctions() {
   RegisterFunction<ExtensionTestPassFunction>();
   RegisterFunction<ExtensionTestFailFunction>();
   RegisterFunction<ExtensionTestLogFunction>();
+  RegisterFunction<ExtensionTestQuotaResetFunction>();
 }
 
 void FactoryRegistry::GetAllNames(std::vector<std::string>* names) {
@@ -281,7 +283,16 @@ void ExtensionFunctionDispatcher::HandleRequest(const std::string& name,
   function->SetArgs(args);
   function->set_request_id(request_id);
   function->set_has_callback(has_callback);
-  function->Run();
+
+  ExtensionsService* service = profile()->GetExtensionsService();
+  DCHECK(service);
+  ExtensionsQuotaService* quota = service->quota_service();
+  if (quota->Assess(extension_id(), function, args, base::TimeTicks::Now())) {
+    function->Run();
+  } else {
+    render_view_host_->SendExtensionResponse(function->request_id(), false,
+        std::string(), QuotaLimitHeuristic::kGenericOverQuotaError);
+  }
 }
 
 void ExtensionFunctionDispatcher::SendResponse(ExtensionFunction* function,
diff --git a/chrome/browser/extensions/extension_test_api.cc b/chrome/browser/extensions/extension_test_api.cc
index e3354e4..ac0a2eb 100644
--- a/chrome/browser/extensions/extension_test_api.cc
+++ b/chrome/browser/extensions/extension_test_api.cc
@@ -2,6 +2,9 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
+#include "chrome/browser/profile.h"
+#include "chrome/browser/extensions/extensions_service.h"
+#include "chrome/browser/extensions/extensions_quota_service.h"
 #include "chrome/browser/extensions/extension_test_api.h"
 #include "chrome/common/notification_service.h"
 
@@ -30,3 +33,11 @@ bool ExtensionTestLogFunction::RunImpl() {
   LOG(INFO) << message;
   return true;
 }
+
+bool ExtensionTestQuotaResetFunction::RunImpl() {
+  ExtensionsService* service = profile()->GetExtensionsService();
+  ExtensionsQuotaService* quota = service->quota_service();
+  quota->Purge();
+  quota->violators_.clear();
+  return true;
+}
diff --git a/chrome/browser/extensions/extension_test_api.h b/chrome/browser/extensions/extension_test_api.h
index 79adf13..3b89e53 100644
--- a/chrome/browser/extensions/extension_test_api.h
+++ b/chrome/browser/extensions/extension_test_api.h
@@ -25,4 +25,10 @@ class ExtensionTestLogFunction : public SyncExtensionFunction {
   DECLARE_EXTENSION_FUNCTION_NAME("test.log")
 };
 
+class ExtensionTestQuotaResetFunction : public SyncExtensionFunction {
+  ~ExtensionTestQuotaResetFunction() {}
+  virtual bool RunImpl();
+  DECLARE_EXTENSION_FUNCTION_NAME("test.resetQuota")
+};
+
 #endif  // CHROME_BROWSER_EXTENSIONS_EXTENSION_TEST_API_H_
diff --git a/chrome/browser/extensions/extensions_quota_service.cc b/chrome/browser/extensions/extensions_quota_service.cc
new file mode 100644
index 0000000..9005d8f
--- /dev/null
+++ b/chrome/browser/extensions/extensions_quota_service.cc
@@ -0,0 +1,148 @@
+// Copyright (c) 2009 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.
+
+#include "chrome/browser/extensions/extensions_quota_service.h"
+
+#include "base/message_loop.h"
+#include "base/stl_util-inl.h"
+#include "chrome/browser/extensions/extension_function.h"
+
+// If the browser stays open long enough, we reset state once a day.
+// Whatever this value is, it should be an order of magnitude longer than
+// the longest interval in any of the QuotaLimitHeuristics in use.
+static const int kPurgeIntervalInDays = 1;
+
+const char QuotaLimitHeuristic::kGenericOverQuotaError[] =
+    "This request exceeds available quota.";
+
+ExtensionsQuotaService::ExtensionsQuotaService() {
+  if (MessageLoop::current() != NULL) {  // Null in unit tests.
+    purge_timer_.Start(base::TimeDelta::FromDays(kPurgeIntervalInDays),
+                       this, &ExtensionsQuotaService::Purge);
+  }
+}
+
+ExtensionsQuotaService::~ExtensionsQuotaService() {
+  purge_timer_.Stop();
+  Purge();
+}
+
+bool ExtensionsQuotaService::Assess(const std::string& extension_id,
+    ExtensionFunction* function, const Value* args,
+    const base::TimeTicks& event_time) {
+  // Lookup function list for extension.
+  FunctionHeuristicsMap& functions = function_heuristics_[extension_id];
+
+  // Lookup heuristics for function, create if necessary.
+  QuotaLimitHeuristics& heuristics = functions[function->name()];
+  if (heuristics.empty())
+    function->GetQuotaLimitHeuristics(&heuristics);
+
+  if (heuristics.empty())
+    return true;  // No heuristic implies no limit.
+
+  if (violators_.find(extension_id) != violators_.end())
+    return false;  // Repeat offender.
+
+  bool global_decision = true;
+  for (QuotaLimitHeuristics::iterator heuristic = heuristics.begin();
+       heuristic != heuristics.end(); ++heuristic) {
+    // Apply heuristic to each item (bucket).
+    global_decision = (*heuristic)->ApplyToArgs(args, event_time) &&
+        global_decision;
+  }
+
+  if (!global_decision) {
+    PurgeFunctionHeuristicsMap(&functions);
+    function_heuristics_.erase(extension_id);
+    violators_.insert(extension_id);
+  }
+  return global_decision;
+}
+
+void ExtensionsQuotaService::PurgeFunctionHeuristicsMap(
+    FunctionHeuristicsMap* map) {
+  FunctionHeuristicsMap::iterator heuristics = map->begin();
+  while (heuristics != map->end()) {
+    STLDeleteElements(&heuristics->second);
+    map->erase(heuristics++);
+  }
+}
+
+void ExtensionsQuotaService::Purge() {
+  std::map<std::string, FunctionHeuristicsMap>::iterator it =
+      function_heuristics_.begin();
+  for (; it != function_heuristics_.end(); function_heuristics_.erase(it++))
+    PurgeFunctionHeuristicsMap(&it->second);
+}
+
+void QuotaLimitHeuristic::Bucket::Reset(const Config& config,
+    const base::TimeTicks& start) {
+  num_tokens_ = config.refill_token_count;
+  expiration_ = start + config.refill_interval;
+}
+
+bool QuotaLimitHeuristic::ApplyToArgs(const Value* args,
+    const base::TimeTicks& event_time) {
+  BucketList buckets;
+  bucket_mapper_->GetBucketsForArgs(args, &buckets);
+  for (BucketList::iterator i = buckets.begin(); i != buckets.end(); ++i) {
+    if ((*i)->expiration().is_null())  // A brand new bucket.
+      (*i)->Reset(config_, event_time);
+    if (!Apply(*i, event_time))
+      return false;  // It only takes one to spoil it for everyone.
+  }
+  return true;
+}
+
+ExtensionsQuotaService::SustainedLimit::SustainedLimit(
+    const base::TimeDelta& sustain, const Config& config, BucketMapper* map)
+    : QuotaLimitHeuristic(config, map),
+      repeat_exhaustion_allowance_(sustain.InSeconds() /
+                                   config.refill_interval.InSeconds()),
+      num_available_repeat_exhaustions_(repeat_exhaustion_allowance_) {
+}
+
+bool ExtensionsQuotaService::TimedLimit::Apply(Bucket* bucket,
+    const base::TimeTicks& event_time) {
+  if (event_time > bucket->expiration())
+    bucket->Reset(config(), event_time);
+
+  return bucket->DeductToken();
+}
+
+bool ExtensionsQuotaService::SustainedLimit::Apply(Bucket* bucket,
+    const base::TimeTicks& event_time) {
+  if (event_time > bucket->expiration()) {
+    // We reset state for this item and start over again if this request breaks
+    // the bad cycle that was previously being tracked.  This occurs if the
+    // state in the bucket expired recently (it has been long enough since the
+    // event that we don't care about the last event), but the bucket still has
+    // tokens (so pressure was not sustained over that time), OR we are more
+    // than 1 full refill interval away from the last event (so even if we used
+    // up all the tokens in the last bucket, nothing happened in the entire
+    // next refill interval, so it doesn't matter).
+    if (bucket->has_tokens() || event_time > bucket->expiration() +
+        config().refill_interval) {
+      bucket->Reset(config(), event_time);
+      num_available_repeat_exhaustions_ = repeat_exhaustion_allowance_;
+    } else if (--num_available_repeat_exhaustions_ > 0) {
+      // The last interval was saturated with requests, and this is the first
+      // event in the next interval. If this happens
+      // repeat_exhaustion_allowance_ times, it's a violation. Reset the bucket
+      // state to start timing from the end of the last interval (and we'll
+      // deduct the token below) so we can detect this each time it happens.
+      bucket->Reset(config(), bucket->expiration());
+    } else {
+      // No allowances left; this request is a violation.
+      return false;
+    }
+  }
+
+  // We can go negative since we check has_tokens when we get to *next* bucket,
+  // and for the small interval all that matters is whether we used up all the
+  // tokens (which is true if num_tokens_ <= 0).
+  bucket->DeductToken();
+  return true;
+}
diff --git a/chrome/browser/extensions/extensions_quota_service.h b/chrome/browser/extensions/extensions_quota_service.h
new file mode 100644
index 0000000..f68a763
--- /dev/null
+++ b/chrome/browser/extensions/extensions_quota_service.h
@@ -0,0 +1,195 @@
+// Copyright (c) 2009 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 ExtensionsQuotaService 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 CHROME_BROWSER_EXTENSIONS_EXTENSIONS_QUOTA_SERVICE_H_
+#define CHROME_BROWSER_EXTENSIONS_EXTENSIONS_QUOTA_SERVICE_H_
+
+#include <list>
+#include <map>
+#include <string>
+
+#include "base/hash_tables.h"
+#include "base/scoped_ptr.h"
+#include "base/time.h"
+#include "base/timer.h"
+#include "base/values.h"
+
+class ExtensionFunction;
+class QuotaLimitHeuristic;
+typedef std::list<QuotaLimitHeuristic*> QuotaLimitHeuristics;
+
+class ExtensionsQuotaService {
+ public:
+  // Some concrete heuristics (declared below) that ExtensionFunctions can
+  // use to help the service make decisions about quota violations.
+  class TimedLimit;
+  class SustainedLimit;
+
+  ExtensionsQuotaService();
+  ~ExtensionsQuotaService();
+
+  // Decide whether the invocation of |function| with argument |args| by the
+  // extension specified by |extension_id| results in a quota limit violation.
+  // Returns true if the request is fine and can proceed, false if the request
+  // should be throttled and an error returned to the extension.
+  bool Assess(const std::string& extension_id, ExtensionFunction* function,
+              const Value* args, const base::TimeTicks& event_time);
+ private:
+  friend class ExtensionTestQuotaResetFunction;
+  typedef std::map<std::string, QuotaLimitHeuristics> FunctionHeuristicsMap;
+
+  // Purge resets all accumulated data (except |violators_|) 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<ExtensionsQuotaService> 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<std::string, 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.
+  base::hash_set<std::string> violators_;
+
+  DISALLOW_COPY_AND_ASSIGN(ExtensionsQuotaService);
+};
+
+// 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:
+    explicit 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 generic error message for quota violating requests.
+  static const char kGenericOverQuotaError[];
+
+  // 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:
+    // 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 Value* args, BucketList* buckets) = 0;
+  };
+
+  // Ownership of |mapper| is given to the new QuotaLimitHeuristic.
+  explicit QuotaLimitHeuristic(const Config& config, BucketMapper* map)
+      : config_(config), bucket_mapper_(map) {}
+  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 Value* args, const base::TimeTicks& event_time);
+
+ 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_;
+
+  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 ExtensionsQuotaService::TimedLimit : public QuotaLimitHeuristic {
+ public:
+  explicit TimedLimit(const Config& config, BucketMapper* map)
+      : QuotaLimitHeuristic(config, map) {}
+  virtual bool Apply(Bucket* bucket, const base::TimeTicks& event_time);
+};
+
+// 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 ExtensionsQuotaService::SustainedLimit : public QuotaLimitHeuristic {
+ public:
+  SustainedLimit(const base::TimeDelta& sustain,
+                 const Config& config,
+                 BucketMapper* map);
+  virtual bool Apply(Bucket* bucket, const base::TimeTicks& event_time);
+ private:
+  // Specifies how long exhaustion of buckets is allowed to continue before
+  // denying requests.
+  const int64 repeat_exhaustion_allowance_;
+  int64 num_available_repeat_exhaustions_;
+};
+
+#endif  // CHROME_BROWSER_EXTENSIONS_EXTENSIONS_QUOTA_SERVICE_H_
diff --git a/chrome/browser/extensions/extensions_quota_service_unittest.cc b/chrome/browser/extensions/extensions_quota_service_unittest.cc
new file mode 100644
index 0000000..fae8d41
--- /dev/null
+++ b/chrome/browser/extensions/extensions_quota_service_unittest.cc
@@ -0,0 +1,308 @@
+// Copyright (c) 2009 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.
+
+#include "base/stl_util-inl.h"
+#include "base/string_util.h"
+#include "chrome/browser/extensions/extension_function.h"
+#include "chrome/browser/extensions/extensions_quota_service.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+using base::TimeDelta;
+using base::TimeTicks;
+
+typedef QuotaLimitHeuristic::Bucket Bucket;
+typedef QuotaLimitHeuristic::Config Config;
+typedef QuotaLimitHeuristic::BucketList BucketList;
+typedef ExtensionsQuotaService::TimedLimit TimedLimit;
+typedef ExtensionsQuotaService::SustainedLimit SustainedLimit;
+
+static const Config kFrozenConfig = { 0, TimeDelta::FromDays(0) };
+static const Config k2PerMinute = { 2, TimeDelta::FromMinutes(1) };
+static const Config k20PerHour = { 20, TimeDelta::FromHours(1) };
+static const TimeTicks kStartTime = TimeTicks();
+static const TimeTicks k1MinuteAfterStart =
+    kStartTime + TimeDelta::FromMinutes(1);
+
+namespace {
+class Mapper : public QuotaLimitHeuristic::BucketMapper {
+ public:
+  Mapper() {}
+  virtual ~Mapper() { STLDeleteValues(&buckets_); }
+  virtual void GetBucketsForArgs(const Value* args, BucketList* buckets) {
+    const ListValue* v = static_cast<const ListValue*>(args);
+    for (size_t i = 0; i < v->GetSize(); i++) {
+      int id;
+      ASSERT_TRUE(v->GetInteger(i, &id));
+      Bucket* bucket = buckets_[id];
+      if (bucket == NULL) {
+        bucket = new Bucket();
+        buckets_[id] = bucket;
+      }
+      buckets->push_back(bucket);
+    }
+  }
+ private:
+  typedef std::map<int, Bucket*> BucketMap;
+  BucketMap buckets_;
+  DISALLOW_COPY_AND_ASSIGN(Mapper);
+};
+
+class MockMapper : public QuotaLimitHeuristic::BucketMapper {
+ public:
+  virtual void GetBucketsForArgs(const Value* args, BucketList* buckets) {}
+};
+
+class MockFunction : public ExtensionFunction {
+ public:
+  explicit MockFunction(const std::string& name) { set_name(name); }
+  virtual void SetArgs(const Value* args) {}
+  virtual const std::string GetError() { return std::string(); }
+  virtual const std::string GetResult() { return std::string(); }
+  virtual void Run() {}
+};
+
+class TimedLimitMockFunction : public MockFunction {
+ public:
+  explicit TimedLimitMockFunction(const std::string& name)
+      : MockFunction(name) {}
+  virtual void GetQuotaLimitHeuristics(
+      QuotaLimitHeuristics* heuristics) const {
+    heuristics->push_back(new TimedLimit(k2PerMinute, new Mapper()));
+  }
+};
+
+class ChainedLimitsMockFunction : public MockFunction {
+ public:
+  explicit ChainedLimitsMockFunction(const std::string& name)
+      : MockFunction(name) {}
+  virtual void GetQuotaLimitHeuristics(
+      QuotaLimitHeuristics* heuristics) const {
+    // No more than 2 per minute sustained over 5 minutes.
+    heuristics->push_back(new SustainedLimit(TimeDelta::FromMinutes(5),
+        k2PerMinute, new Mapper()));
+    // No more than 20 per hour.
+    heuristics->push_back(new TimedLimit(k20PerHour, new Mapper()));
+  }
+};
+
+class FrozenMockFunction : public MockFunction {
+ public:
+  explicit FrozenMockFunction(const std::string& name) : MockFunction(name) {}
+  virtual void GetQuotaLimitHeuristics(
+      QuotaLimitHeuristics* heuristics) const {
+    heuristics->push_back(new TimedLimit(kFrozenConfig, new Mapper()));
+  }
+};
+}  // namespace
+
+class ExtensionsQuotaServiceTest : public testing::Test {
+ public:
+  ExtensionsQuotaServiceTest()
+      : extension_a_("a"), extension_b_("b"), extension_c_("c") {}
+  virtual void SetUp() {
+    service_.reset(new ExtensionsQuotaService());
+  }
+  virtual void TearDown() {
+    service_.reset();
+  }
+ protected:
+  std::string extension_a_;
+  std::string extension_b_;
+  std::string extension_c_;
+  scoped_ptr<ExtensionsQuotaService> service_;
+};
+
+class QuotaLimitHeuristicTest : public testing::Test {
+ public:
+  static void DoMoreThan2PerMinuteFor5Minutes(const TimeTicks& start_time,
+                                              QuotaLimitHeuristic* lim,
+                                              Bucket* b,
+                                              int an_unexhausted_minute) {
+    for (int i = 0; i < 5; i++) {
+      // Perform one operation in each minute.
+      int m = i * 60;
+      EXPECT_TRUE(lim->Apply(b, start_time + TimeDelta::FromSeconds(10 + m)));
+      EXPECT_TRUE(b->has_tokens());
+
+      if (i == an_unexhausted_minute)
+        continue;  // Don't exhaust all tokens this minute.
+
+      EXPECT_TRUE(lim->Apply(b, start_time + TimeDelta::FromSeconds(15 + m)));
+      EXPECT_FALSE(b->has_tokens());
+
+      // These are OK because we haven't exhausted all buckets.
+      EXPECT_TRUE(lim->Apply(b, start_time + TimeDelta::FromSeconds(20 + m)));
+      EXPECT_FALSE(b->has_tokens());
+      EXPECT_TRUE(lim->Apply(b, start_time + TimeDelta::FromSeconds(50 + m)));
+      EXPECT_FALSE(b->has_tokens());
+    }
+  }
+};
+
+TEST_F(QuotaLimitHeuristicTest, Timed) {
+  TimedLimit lim(k2PerMinute, new MockMapper());
+  Bucket b;
+
+  b.Reset(k2PerMinute, kStartTime);
+  EXPECT_TRUE(lim.Apply(&b, kStartTime));
+  EXPECT_TRUE(b.has_tokens());
+  EXPECT_TRUE(lim.Apply(&b, kStartTime + TimeDelta::FromSeconds(30)));
+  EXPECT_FALSE(b.has_tokens());
+  EXPECT_FALSE(lim.Apply(&b,  k1MinuteAfterStart));
+
+  b.Reset(k2PerMinute, kStartTime);
+  EXPECT_TRUE(lim.Apply(&b, k1MinuteAfterStart - TimeDelta::FromSeconds(1)));
+  EXPECT_TRUE(lim.Apply(&b, k1MinuteAfterStart));
+  EXPECT_TRUE(lim.Apply(&b, k1MinuteAfterStart + TimeDelta::FromSeconds(1)));
+  EXPECT_TRUE(lim.Apply(&b, k1MinuteAfterStart + TimeDelta::FromSeconds(2)));
+  EXPECT_FALSE(lim.Apply(&b, k1MinuteAfterStart + TimeDelta::FromSeconds(3)));
+}
+
+TEST_F(QuotaLimitHeuristicTest, Sustained) {
+  SustainedLimit lim(TimeDelta::FromMinutes(5), k2PerMinute, new MockMapper());
+  Bucket bucket;
+
+  bucket.Reset(k2PerMinute, kStartTime);
+  DoMoreThan2PerMinuteFor5Minutes(kStartTime, &lim, &bucket, -1);
+  // This straw breaks the camel's back.
+  EXPECT_FALSE(lim.Apply(&bucket, kStartTime + TimeDelta::FromMinutes(6)));
+
+  // The heuristic resets itself on a safe request.
+  EXPECT_TRUE(lim.Apply(&bucket, kStartTime + TimeDelta::FromDays(1)));
+
+  // Do the same as above except don't exhaust final bucket.
+  bucket.Reset(k2PerMinute, kStartTime);
+  DoMoreThan2PerMinuteFor5Minutes(kStartTime, &lim, &bucket, -1);
+  EXPECT_TRUE(lim.Apply(&bucket, kStartTime + TimeDelta::FromMinutes(7)));
+
+  // Do the same as above except don't exhaust the 3rd (w.l.o.g) bucket.
+  bucket.Reset(k2PerMinute, kStartTime);
+  DoMoreThan2PerMinuteFor5Minutes(kStartTime, &lim, &bucket, 3);
+  // If the 3rd bucket were exhausted, this would fail (see first test).
+  EXPECT_TRUE(lim.Apply(&bucket, kStartTime + TimeDelta::FromMinutes(6)));
+}
+
+TEST_F(ExtensionsQuotaServiceTest, NoHeuristic) {
+  scoped_refptr<MockFunction> f(new MockFunction("foo"));
+  ListValue args;
+  EXPECT_TRUE(service_->Assess(extension_a_, f, &args, kStartTime));
+}
+
+TEST_F(ExtensionsQuotaServiceTest, FrozenHeuristic) {
+  scoped_refptr<MockFunction> f(new FrozenMockFunction("foo"));
+  ListValue args;
+  args.Append(new FundamentalValue(1));
+  EXPECT_FALSE(service_->Assess(extension_a_, f, &args, kStartTime));
+}
+
+TEST_F(ExtensionsQuotaServiceTest, SingleHeuristic) {
+  scoped_refptr<MockFunction> f(new TimedLimitMockFunction("foo"));
+  ListValue args;
+  args.Append(new FundamentalValue(1));
+  EXPECT_TRUE(service_->Assess(extension_a_, f, &args, kStartTime));
+  EXPECT_TRUE(service_->Assess(extension_a_, f, &args,
+              kStartTime + TimeDelta::FromSeconds(10)));
+  EXPECT_FALSE(service_->Assess(extension_a_, f, &args,
+              kStartTime + TimeDelta::FromSeconds(15)));
+
+  ListValue args2;
+  args2.Append(new FundamentalValue(1));
+  args2.Append(new FundamentalValue(2));
+  EXPECT_TRUE(service_->Assess(extension_b_, f, &args2, kStartTime));
+  EXPECT_TRUE(service_->Assess(extension_b_, f, &args2,
+              kStartTime + TimeDelta::FromSeconds(10)));
+
+  TimeDelta peace = TimeDelta::FromMinutes(30);
+  EXPECT_TRUE(service_->Assess(extension_b_, f, &args, kStartTime + peace));
+  EXPECT_TRUE(service_->Assess(extension_b_, f, &args,
+              kStartTime + peace + TimeDelta::FromSeconds(10)));
+  EXPECT_FALSE(service_->Assess(extension_b_, f, &args2,
+               kStartTime + peace + TimeDelta::FromSeconds(15)));
+
+  // Test that items are independent.
+  ListValue args3;
+  args3.Append(new FundamentalValue(3));
+  EXPECT_TRUE(service_->Assess(extension_c_, f, &args, kStartTime));
+  EXPECT_TRUE(service_->Assess(extension_c_, f, &args3,
+              kStartTime + TimeDelta::FromSeconds(10)));
+  EXPECT_TRUE(service_->Assess(extension_c_, f, &args,
+              kStartTime + TimeDelta::FromSeconds(15)));
+  EXPECT_TRUE(service_->Assess(extension_c_, f, &args3,
+              kStartTime + TimeDelta::FromSeconds(20)));
+  EXPECT_FALSE(service_->Assess(extension_c_, f, &args,
+               kStartTime + TimeDelta::FromSeconds(25)));
+  EXPECT_FALSE(service_->Assess(extension_c_, f, &args3,
+               kStartTime + TimeDelta::FromSeconds(30)));
+}
+
+TEST_F(ExtensionsQuotaServiceTest, ChainedHeuristics) {
+  scoped_refptr<MockFunction> f(new ChainedLimitsMockFunction("foo"));
+  ListValue args;
+  args.Append(new FundamentalValue(1));
+
+  // First, test that the low limit can be avoided but the higher one is hit.
+  // One event per minute for 20 minutes comes in under the sustained limit,
+  // but is equal to the timed limit.
+  for (int i = 0; i < 20; i++) {
+    EXPECT_TRUE(service_->Assess(extension_a_, f, &args,
+                kStartTime + TimeDelta::FromSeconds(10 + i * 60)));
+  }
+
+  // This will bring us to 21 events in an hour, which is a violation.
+  EXPECT_FALSE(service_->Assess(extension_a_, f, &args,
+               kStartTime + TimeDelta::FromMinutes(30)));
+
+  // Now, check that we can still hit the lower limit.
+  for (int i = 0; i < 5; i++) {
+    EXPECT_TRUE(service_->Assess(extension_b_, f, &args,
+                kStartTime + TimeDelta::FromSeconds(10 + i * 60)));
+    EXPECT_TRUE(service_->Assess(extension_b_, f, &args,
+                kStartTime + TimeDelta::FromSeconds(15 + i * 60)));
+    EXPECT_TRUE(service_->Assess(extension_b_, f, &args,
+                kStartTime + TimeDelta::FromSeconds(20 + i * 60)));
+  }
+
+  EXPECT_FALSE(service_->Assess(extension_b_, f, &args,
+               kStartTime + TimeDelta::FromMinutes(6)));
+}
+
+TEST_F(ExtensionsQuotaServiceTest, MultipleFunctionsDontInterfere) {
+  scoped_refptr<MockFunction> f(new TimedLimitMockFunction("foo"));
+  scoped_refptr<MockFunction> g(new TimedLimitMockFunction("bar"));
+
+  ListValue args_f;
+  ListValue args_g;
+  args_f.Append(new FundamentalValue(1));
+  args_g.Append(new FundamentalValue(2));
+
+  EXPECT_TRUE(service_->Assess(extension_a_, f, &args_f, kStartTime));
+  EXPECT_TRUE(service_->Assess(extension_a_, g, &args_g, kStartTime));
+  EXPECT_TRUE(service_->Assess(extension_a_, f, &args_f,
+              kStartTime + TimeDelta::FromSeconds(10)));
+  EXPECT_TRUE(service_->Assess(extension_a_, g, &args_g,
+              kStartTime + TimeDelta::FromSeconds(10)));
+  EXPECT_FALSE(service_->Assess(extension_a_, f, &args_f,
+               kStartTime + TimeDelta::FromSeconds(15)));
+  EXPECT_FALSE(service_->Assess(extension_a_, g, &args_g,
+               kStartTime + TimeDelta::FromSeconds(15)));
+}
+
+TEST_F(ExtensionsQuotaServiceTest, ViolatorsWillBeViolators) {
+  scoped_refptr<MockFunction> f(new TimedLimitMockFunction("foo"));
+  scoped_refptr<MockFunction> g(new TimedLimitMockFunction("bar"));
+  ListValue arg;
+  arg.Append(new FundamentalValue(1));
+  EXPECT_TRUE(service_->Assess(extension_a_, f, &arg, kStartTime));
+  EXPECT_TRUE(service_->Assess(extension_a_, f, &arg,
+              kStartTime + TimeDelta::FromSeconds(10)));
+  EXPECT_FALSE(service_->Assess(extension_a_, f, &arg,
+               kStartTime + TimeDelta::FromSeconds(15)));
+
+  // We don't allow this extension to use quota limited functions even if they
+  // wait a while.
+  EXPECT_FALSE(service_->Assess(extension_a_, f, &arg,
+               kStartTime + TimeDelta::FromDays(1)));
+  EXPECT_FALSE(service_->Assess(extension_a_, g, &arg,
+               kStartTime + TimeDelta::FromDays(1)));
+}
diff --git a/chrome/browser/extensions/extensions_service.h b/chrome/browser/extensions/extensions_service.h
index 910a396..5b0252d 100644
--- a/chrome/browser/extensions/extensions_service.h
+++ b/chrome/browser/extensions/extensions_service.h
@@ -20,6 +20,7 @@
 #include "chrome/browser/chrome_thread.h"
 #include "chrome/browser/extensions/extension_prefs.h"
 #include "chrome/browser/extensions/extension_process_manager.h"
+#include "chrome/browser/extensions/extensions_quota_service.h"
 #include "chrome/browser/extensions/external_extension_provider.h"
 #include "chrome/browser/extensions/sandboxed_extension_unpacker.h"
 #include "chrome/browser/privacy_blacklist/blacklist_manager.h"
@@ -217,6 +218,8 @@ class ExtensionsService
   // Note that this may return NULL if autoupdate is not turned on.
   ExtensionUpdater* updater() { return updater_.get(); }
 
+  ExtensionsQuotaService* quota_service() { return &quota_service_; }
+
   // Notify the frontend that there was an error loading an extension.
   // This method is public because ExtensionsServiceBackend can post to here.
   void ReportExtensionLoadError(const FilePath& extension_path,
@@ -285,6 +288,9 @@ class ExtensionsService
   // The backend that will do IO on behalf of this instance.
   scoped_refptr<ExtensionsServiceBackend> backend_;
 
+  // Used by dispatchers to limit API quota for individual extensions.
+  ExtensionsQuotaService quota_service_;
+
   // Is the service ready to go?
   bool ready_;
 
diff --git a/chrome/chrome_browser.gypi b/chrome/chrome_browser.gypi
index 0e97269..244d6ba 100755
--- a/chrome/chrome_browser.gypi
+++ b/chrome/chrome_browser.gypi
@@ -687,6 +687,8 @@
         'browser/extensions/extension_toolstrip_api.h',
         'browser/extensions/extension_updater.cc',
         'browser/extensions/extension_updater.h',
+        'browser/extensions/extensions_quota_service.cc',
+        'browser/extensions/extensions_quota_service.h',
         'browser/extensions/extensions_service.cc',
         'browser/extensions/extensions_service.h',
         'browser/extensions/extensions_ui.cc',
diff --git a/chrome/chrome_tests.gypi b/chrome/chrome_tests.gypi
index 2aa5eac..9e95e40 100755
--- a/chrome/chrome_tests.gypi
+++ b/chrome/chrome_tests.gypi
@@ -620,6 +620,7 @@
         'browser/extensions/extension_process_manager_unittest.cc',
         'browser/extensions/extension_ui_unittest.cc',
         'browser/extensions/extension_updater_unittest.cc',
+        'browser/extensions/extensions_quota_service_unittest.cc',
         'browser/extensions/extensions_service_unittest.cc',
         'browser/extensions/file_reader_unittest.cc',
         'browser/extensions/sandboxed_extension_unpacker_unittest.cc',
diff --git a/chrome/common/extensions/api/extension_api.json b/chrome/common/extensions/api/extension_api.json
index 8797153..4765076 100755
--- a/chrome/common/extensions/api/extension_api.json
+++ b/chrome/common/extensions/api/extension_api.json
@@ -1747,6 +1747,12 @@
         ]
       },
       {
+        "name": "resetQuota",
+        "type": "function",
+        "description": "Reset all accumulated quota state for all extensions.  This is only used for internal unit testing.",
+        "parameters": []
+      },
+      {
         "name": "log",
         "type": "function",
         "description": "Logs a message during internal unit testing.",
diff --git a/chrome/common/extensions/docs/test.html b/chrome/common/extensions/docs/test.html
index 2c80d57..97d22ae 100644
--- a/chrome/common/extensions/docs/test.html
+++ b/chrome/common/extensions/docs/test.html
@@ -224,6 +224,8 @@
                         <a href="#method-notifyFail">notifyFail</a>
                       </li><li>
                         <a href="#method-notifyPass">notifyPass</a>
+                      </li><li>
+                        <a href="#method-resetQuota">resetQuota</a>
                       </li>
                     </ol>
                   </li>
@@ -573,6 +575,59 @@
 
               </div> <!-- /description -->
 
+            </div><div class="apiItem">
+              <a name="method-resetQuota"></a> <!-- method-anchor -->
+              <h4>resetQuota</h4>
+
+              <div class="summary"><span style="display: none; ">void</span>
+                  <!-- Note: intentionally longer 80 columns -->
+                  <span>chrome.test.resetQuota</span>(<span style="display: none; "><span>, </span><span></span>
+                      <var><span></span></var></span>)</div>
+
+              <div class="description">
+                <p class="todo" style="display: none; ">Undocumented.</p>
+                <p>Reset all accumulated quota state for all extensions.  This is only used for internal unit testing.</p>
+
+                <!-- PARAMETERS -->
+                <h4>Parameters</h4>
+                <dl>
+                  <div style="display: none; ">
+                    <div>
+                    </div>
+                  </div>
+                </dl>
+
+                <!-- RETURNS -->
+                <h4 style="display: none; ">Returns</h4>
+                <dl>
+                  <div style="display: none; ">
+                    <div>
+                    </div>
+                  </div>
+                </dl>
+
+                <!-- CALLBACK -->
+                <div style="display: none; ">
+                  <div>
+                  <h4>Callback function</h4>
+                  <p>
+                    If you specify the <em>callback</em> parameter,
+                    it should specify a function that looks like this:
+                  </p>
+
+                  <!-- Note: intentionally longer 80 columns -->
+                  <pre>function(<span>Type param1, Type param2</span>) <span class="subdued">{...}</span>);</pre>
+                  <dl>
+                    <div>
+                      <div>
+                      </div>
+                    </div>
+                  </dl>
+                  </div>
+                </div>
+
+              </div> <!-- /description -->
+
             </div>  <!-- /apiItem -->
 
           </div>  <!-- /apiGroup -->
diff --git a/chrome/test/data/extensions/api_test/bookmarks/test.js b/chrome/test/data/extensions/api_test/bookmarks/test.js
index 7f0a97a..eb32dcc 100644
--- a/chrome/test/data/extensions/api_test/bookmarks/test.js
+++ b/chrome/test/data/extensions/api_test/bookmarks/test.js
@@ -17,6 +17,12 @@ var node2 = {parentId:"1", title:"foo quux",
              url:"http://www.example.com/bar"};
 var node3 = {parentId:"1", title:"bar baz",
              url:"http://www.google.com/hello/quux"};
+var quota_node1 = {parentId:"1", title:"Dave",
+                   url:"http://www.dmband.com/"};
+var quota_node2 = {parentId:"1", title:"UW",
+                   url:"http://www.uwaterloo.ca/"};
+var quota_node3 = {parentId:"1", title:"Whistler",
+                   url:"http://www.whistlerblackcomb.com/"};
 
 var pass = chrome.test.callbackPass;
 var fail = chrome.test.callbackFail;
@@ -66,6 +72,30 @@ function compareTrees(left, right) {
   return true;
 }
 
+function createThreeNodes(one, two, three) {
+  var bookmarks_bar = expected[0].children[0];
+  chrome.bookmarks.create(one, pass(function(results) {
+    one.id = results.id;
+    one.index = results.index;
+    bookmarks_bar.children.push(one);
+  }));
+  chrome.bookmarks.create(two, pass(function(results) {
+    two.id = results.id;
+    two.index = results.index;
+    bookmarks_bar.children.push(two);
+  }));
+  chrome.bookmarks.create(three, pass(function(results) {
+    three.id = results.id;
+    three.index = results.index;
+    bookmarks_bar.children.push(three);
+  }));
+  chrome.bookmarks.getTree(pass(function(results) {
+    chrome.test.assertTrue(compareTrees(expected, results),
+                           "getTree() result != expected");
+    expected = results;
+  }));
+}
+
 chrome.test.runTests([
   function getTree() {
     chrome.bookmarks.getTree(pass(function(results) {
@@ -136,27 +166,7 @@ chrome.test.runTests([
   },
 
   function move_setup() {
-    var bookmarks_bar = expected[0].children[0];
-    chrome.bookmarks.create(node1, pass(function(results) {
-      node1.id = results.id;
-      node1.index = results.index;
-      bookmarks_bar.children.push(node1);
-    }));
-    chrome.bookmarks.create(node2, pass(function(results) {
-      node2.id = results.id;
-      node2.index = results.index;
-      bookmarks_bar.children.push(node2);
-    }));
-    chrome.bookmarks.create(node3, pass(function(results) {
-      node3.id = results.id;
-      node3.index = results.index;
-      bookmarks_bar.children.push(node3);
-    }));
-    chrome.bookmarks.getTree(pass(function(results) {
-      chrome.test.assertTrue(compareTrees(expected, results),
-                             "getTree() result != expected");
-      expected = results;
-    }));
+    createThreeNodes(node1, node2, node3);
   },
 
   function move() {
@@ -280,7 +290,7 @@ chrome.test.runTests([
       expected = results;
     }));
   },
-  
+
   function removeTree() {
     var parentId = node2.parentId;
     var folder = expected[0].children[1].children[0];
@@ -298,4 +308,44 @@ chrome.test.runTests([
       expected = results;
     }));
   },
+
+  function quotaLimitedCreate() {
+    var node = {parentId:"1", title:"quotacreate", url:"http://www.quota.com/"};
+    for (i = 0; i < 100; i++) {
+      chrome.bookmarks.create(node, pass(function(results) {
+        expected[0].children[0].children.push(results);
+      }));
+    }
+    chrome.bookmarks.create(node,
+                            fail("This request exceeds available quota."));
+
+    chrome.test.resetQuota();
+
+    // Also, test that > 100 creations of different items is fine.
+    for (i = 0; i < 101; i++) {
+      var changer = {parentId:"1", title:"" + i, url:"http://www.quota.com/"};
+      chrome.bookmarks.create(changer, pass(function(results) {
+        expected[0].children[0].children.push(results);
+      }));
+    }
+  },
+
+  function quota_setup() {
+    createThreeNodes(quota_node1, quota_node2, quota_node3);
+  },
+
+  function quotaLimitedUpdate() {
+    var title = "hello, world!";
+    for (i = 0; i < 100; i++) {
+      chrome.bookmarks.update(quota_node1.id, {"title": title},
+          pass(function(results) {
+                 chrome.test.assertEq(title, results.title);
+               }
+      ));
+    }
+    chrome.bookmarks.update(quota_node1.id, {"title": title},
+        fail("This request exceeds available quota."));
+
+    chrome.test.resetQuota();
+  },
 ]);