8 files changed, 745 insertions, 3 deletions

diff --git a/chrome/browser/net/evicted_domain_cookie_counter.cc b/chrome/browser/net/evicted_domain_cookie_counter.cc
new file mode 100644
index 0000000..6925c57
--- /dev/null
+++ b/chrome/browser/net/evicted_domain_cookie_counter.cc
@@ -0,0 +1,202 @@
+// 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.
+
+#include "chrome/browser/net/evicted_domain_cookie_counter.h"
+
+#include <algorithm>
+#include <vector>
+
+#include "base/metrics/histogram.h"
+#include "base/stl_util.h"
+#include "base/string_util.h"
+#include "chrome/browser/google/google_util.h"
+#include "net/cookies/canonical_cookie.h"
+
+namespace chrome_browser_net {
+
+using base::Time;
+using base::TimeDelta;
+
+namespace {
+
+const size_t kMaxEvictedDomainCookies = 500;
+const size_t kPurgeEvictedDomainCookies = 100;
+
+class DelegateImpl : public EvictedDomainCookieCounter::Delegate {
+ public:
+  DelegateImpl();
+
+  // EvictedDomainCookieCounter::Delegate implementation.
+  virtual void Report(
+      const EvictedDomainCookieCounter::EvictedCookie& evicted_cookie,
+      const Time& reinstatement_time) OVERRIDE;
+  virtual Time CurrentTime() const OVERRIDE;
+};
+
+DelegateImpl::DelegateImpl() {}
+
+void DelegateImpl::Report(
+    const EvictedDomainCookieCounter::EvictedCookie& evicted_cookie,
+    const Time& reinstatement_time) {
+  TimeDelta reinstatement_delay(
+      reinstatement_time - evicted_cookie.eviction_time);
+  // Need to duplicate HISTOGRAM_CUSTOM_TIMES(), since it is a macro that
+  // defines a static variable.
+  if (evicted_cookie.is_google) {
+    HISTOGRAM_CUSTOM_TIMES("Cookie.ReinstatedCookiesGoogle",
+                           reinstatement_delay,
+                           TimeDelta::FromSeconds(1),
+                           TimeDelta::FromDays(7),
+                           50);
+  } else {
+    HISTOGRAM_CUSTOM_TIMES("Cookie.ReinstatedCookiesOther",
+                           reinstatement_delay,
+                           TimeDelta::FromSeconds(1),
+                           TimeDelta::FromDays(7),
+                           50);
+  }
+}
+
+Time DelegateImpl::CurrentTime() const {
+  return Time::Now();
+}
+
+}  // namespace
+
+EvictedDomainCookieCounter::EvictedDomainCookieCounter(
+    scoped_refptr<net::CookieMonster::Delegate> next_cookie_monster_delegate)
+    : next_cookie_monster_delegate_(next_cookie_monster_delegate),
+      cookie_counter_delegate_(new DelegateImpl),
+      max_size_(kMaxEvictedDomainCookies),
+      purge_count_(kPurgeEvictedDomainCookies) {
+}
+
+EvictedDomainCookieCounter::EvictedDomainCookieCounter(
+    scoped_refptr<net::CookieMonster::Delegate> next_cookie_monster_delegate,
+    scoped_ptr<Delegate> cookie_counter_delegate,
+    size_t max_size,
+    size_t purge_count)
+    : next_cookie_monster_delegate_(next_cookie_monster_delegate),
+      cookie_counter_delegate_(cookie_counter_delegate.Pass()),
+      max_size_(max_size),
+      purge_count_(purge_count) {
+  DCHECK(cookie_counter_delegate_);
+  DCHECK_LT(purge_count, max_size_);
+}
+
+EvictedDomainCookieCounter::~EvictedDomainCookieCounter() {
+  STLDeleteContainerPairSecondPointers(evicted_cookies_.begin(),
+                                       evicted_cookies_.end());
+}
+
+size_t EvictedDomainCookieCounter::GetStorageSize() const {
+  return evicted_cookies_.size();
+}
+
+void EvictedDomainCookieCounter::OnCookieChanged(
+    const net::CanonicalCookie& cookie,
+    bool removed,
+    ChangeCause cause) {
+  EvictedDomainCookieCounter::EvictedCookieKey key(GetKey(cookie));
+  Time current_time(cookie_counter_delegate_->CurrentTime());
+  if (removed) {
+    if (cause == net::CookieMonster::Delegate::CHANGE_COOKIE_EVICTED)
+      StoreEvictedCookie(key, cookie, current_time);
+  } else {  // Includes adds or updates.
+    ProcessNewCookie(key, cookie, current_time);
+  }
+
+  if (next_cookie_monster_delegate_)
+    next_cookie_monster_delegate_->OnCookieChanged(cookie, removed, cause);
+}
+
+// static
+EvictedDomainCookieCounter::EvictedCookieKey
+    EvictedDomainCookieCounter::GetKey(const net::CanonicalCookie& cookie) {
+  return cookie.Domain() + ";" + cookie.Path() + ";" + cookie.Name();
+}
+
+// static
+bool EvictedDomainCookieCounter::CompareEvictedCookie(
+    const EvictedCookieMap::iterator evicted_cookie1,
+    const EvictedCookieMap::iterator evicted_cookie2) {
+  return evicted_cookie1->second->eviction_time
+      < evicted_cookie2->second->eviction_time;
+}
+
+void EvictedDomainCookieCounter::GarbageCollect(const Time& current_time) {
+  if (evicted_cookies_.size() <= max_size_)
+    return;
+
+  // From |evicted_cookies_|, removed all expired cookies, and remove cookies
+  // with the oldest |eviction_time| so that |size_goal| is attained.
+  size_t size_goal = max_size_ - purge_count_;
+  // Bound on number of non-expired cookies to remove.
+  size_t remove_quota = evicted_cookies_.size() - size_goal;
+  DCHECK_GT(remove_quota, 0u);
+
+  std::vector<EvictedCookieMap::iterator> remove_list;
+  remove_list.reserve(evicted_cookies_.size());
+
+  EvictedCookieMap::iterator it = evicted_cookies_.begin();
+  while (it != evicted_cookies_.end()) {
+    if (it->second->is_expired(current_time)) {
+      delete it->second;
+      evicted_cookies_.erase(it++); // Post-increment idiom for in-loop removal.
+      if (remove_quota)
+        --remove_quota;
+    } else {
+      if (remove_quota)  // Don't bother storing if quota met.
+        remove_list.push_back(it);
+      ++it;
+    }
+  }
+
+  // Free the oldest |remove_quota| non-expired cookies.
+  std::partial_sort(remove_list.begin(), remove_list.begin() + remove_quota,
+                    remove_list.end(), CompareEvictedCookie);
+  for (size_t i = 0; i < remove_quota; ++i) {
+    delete remove_list[i]->second;
+    evicted_cookies_.erase(remove_list[i]);
+  }
+
+  // Apply stricter check if non-expired cookies were deleted.
+  DCHECK(remove_quota ? evicted_cookies_.size() == size_goal :
+         evicted_cookies_.size() <= size_goal);
+}
+
+void EvictedDomainCookieCounter::StoreEvictedCookie(
+    const EvictedCookieKey& key,
+    const net::CanonicalCookie& cookie,
+    const Time& current_time) {
+  bool is_google = google_util::IsGoogleHostname(
+      cookie.Domain(), google_util::ALLOW_SUBDOMAIN);
+  EvictedCookie* evicted_cookie =
+      new EvictedCookie(current_time, cookie.ExpiryDate(), is_google);
+  std::pair<EvictedCookieMap::iterator, bool> prev_entry =
+      evicted_cookies_.insert(
+          EvictedCookieMap::value_type(key, evicted_cookie));
+  if (!prev_entry.second) {
+    NOTREACHED();
+    delete prev_entry.first->second;
+    prev_entry.first->second = evicted_cookie;
+  }
+
+  GarbageCollect(current_time);
+}
+
+void EvictedDomainCookieCounter::ProcessNewCookie(
+    const EvictedCookieKey& key,
+    const net::CanonicalCookie& cc,
+    const Time& current_time) {
+  EvictedCookieMap::iterator it = evicted_cookies_.find(key);
+  if (it != evicted_cookies_.end()) {
+    if (!it->second->is_expired(current_time))  // Reinstatement.
+      cookie_counter_delegate_->Report(*it->second, current_time);
+    delete it->second;
+    evicted_cookies_.erase(it);
+  }
+}
+
+}  // namespace chrome_browser_net
diff --git a/chrome/browser/net/evicted_domain_cookie_counter.h b/chrome/browser/net/evicted_domain_cookie_counter.h
new file mode 100644
index 0000000..cd952c8
--- /dev/null
+++ b/chrome/browser/net/evicted_domain_cookie_counter.h
@@ -0,0 +1,146 @@
+// 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.
+
+#ifndef CHROME_BROWSER_NET_EVICTED_DOMAIN_COOKIE_COUNTER_H_
+#define CHROME_BROWSER_NET_EVICTED_DOMAIN_COOKIE_COUNTER_H_
+
+#include <map>
+#include <string>
+
+#include "base/basictypes.h"
+#include "base/compiler_specific.h"
+#include "base/memory/ref_counted.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/time.h"
+#include "net/cookies/cookie_monster.h"
+
+namespace net {
+class CanonicalCookie;
+}  // namespace net
+
+namespace chrome_browser_net {
+
+// The Evicted Domain Cookie Counter generates statistics on "wrongly evicted"
+// cookies, i.e., cookies that were "evicted" (on reaching domain cookie limit)
+// but are then "reinstated" later because they were important. A specific
+// scenario is as follows: a long-lived login session cookie gets evicted owing
+// to its age, thereby forcing the user to lose session, and is reinstated when
+// the user re-authenticates.
+//
+// A solution to the above problem is the Cookie Priority Field, which enables
+// servers to protect important cookies, thereby decreasing the chances that
+// these cookies are wrongly evicted. To measure the effectiveness of this
+// solution, we will compare eviction user metrics before vs. after the fix.
+//
+// Specifically, we wish to record user metrics on "reinstatement delay", i.e.,
+// the duration between eviction and reinstatement of cookie. We expect that
+// after the fix, average reinstatement delays will increase, since low priority
+// cookies are less likely to be reinstated after eviction.
+//
+// Metrics for Google domains are tracked separately.
+//
+class EvictedDomainCookieCounter : public net::CookieMonster::Delegate {
+ public:
+  // Structure to store sanitized data from CanonicalCookie.
+  struct EvictedCookie {
+    EvictedCookie(base::Time eviction_time_in,
+                  base::Time expiry_time_in,
+                  bool is_google_in)
+        : eviction_time(eviction_time_in),
+          expiry_time(expiry_time_in),
+          is_google(is_google_in) {}
+
+    bool is_expired(const base::Time& current_time) const {
+      return !expiry_time.is_null() && current_time >= expiry_time;
+    }
+
+    base::Time eviction_time;
+    base::Time expiry_time;
+    bool is_google;
+  };
+
+  class Delegate {
+   public:
+    virtual ~Delegate() {}
+
+    // Called when a stored evicted cookie is reinstated.
+    virtual void Report(const EvictedCookie& evicted_cookie,
+                        const base::Time& reinstatement_time) = 0;
+
+    // Getter of time is placed here to enable mocks.
+    virtual base::Time CurrentTime() const = 0;
+  };
+
+  // |next_cookie_monster_delegate| can be NULL.
+  explicit EvictedDomainCookieCounter(
+      scoped_refptr<net::CookieMonster::Delegate> next_cookie_monster_delegate);
+
+  // Constructor exposed for testing only.
+  EvictedDomainCookieCounter(
+      scoped_refptr<net::CookieMonster::Delegate> next_cookie_monster_delegate,
+      scoped_ptr<Delegate> cookie_counter_delegate,
+      size_t max_size,
+      size_t purge_count);
+
+  // Returns the number of evicted cookies stored.
+  size_t GetStorageSize() const;
+
+  // CookieMonster::Delegate implementation.
+  virtual void OnCookieChanged(const net::CanonicalCookie& cookie,
+                               bool removed,
+                               ChangeCause cause) OVERRIDE;
+
+ private:
+  // Identifier of an evicted cookie.
+  typedef std::string EvictedCookieKey;
+
+  // Storage class of evicted cookie.
+  typedef std::map<EvictedCookieKey, EvictedCookie*> EvictedCookieMap;
+
+  virtual ~EvictedDomainCookieCounter();
+
+  // Computes key for |cookie| compatible with CanonicalCookie::IsEquivalent(),
+  // i.e., IsEquivalent(a, b) ==> GetKey(a) == GetKey(b).
+  static EvictedCookieKey GetKey(const net::CanonicalCookie& cookie);
+
+  // Comparator for sorting, to make recently evicted cookies appear earlier.
+  static bool CompareEvictedCookie(
+      const EvictedCookieMap::iterator evicted_cookie1,
+      const EvictedCookieMap::iterator evicted_cookie2);
+
+  // If too many evicted cookies are stored, delete the expired ones, then
+  // delete cookies that were evicted the longest, until size limit reached.
+  void GarbageCollect(const base::Time& current_time);
+
+  // Called when a cookie is evicted. Adds the evicted cookie to storage,
+  // possibly replacing an existing equivalent cookie.
+  void StoreEvictedCookie(const EvictedCookieKey& key,
+                          const net::CanonicalCookie& cookie,
+                          const base::Time& current_time);
+
+  // Called when a new cookie is added. If reinstatement occurs, then notifies
+  // |cookie_counter_delegate_| and then removes the evicted cookie.
+  void ProcessNewCookie(const EvictedCookieKey& key,
+                        const net::CanonicalCookie& cookie,
+                        const base::Time& current_time);
+
+  // Another delegate to forward events to.
+  scoped_refptr<net::CookieMonster::Delegate> next_cookie_monster_delegate_;
+
+  scoped_ptr<Delegate> cookie_counter_delegate_;
+
+  EvictedCookieMap evicted_cookies_;
+
+  // Capacity of the evicted cookie storage, before garbage collection occurs.
+  const size_t max_size_;
+
+  // After garbage collection, size reduces to <= |max_size_| - |purge_count_|.
+  const size_t purge_count_;
+
+  DISALLOW_COPY_AND_ASSIGN(EvictedDomainCookieCounter);
+};
+
+}  // namespace chrome_browser_net
+
+#endif  // CHROME_BROWSER_NET_EVICTED_DOMAIN_COOKIE_COUNTER_H_
diff --git a/chrome/browser/net/evicted_domain_cookie_counter_unittest.cc b/chrome/browser/net/evicted_domain_cookie_counter_unittest.cc
new file mode 100644
index 0000000..b5831b0
--- /dev/null
+++ b/chrome/browser/net/evicted_domain_cookie_counter_unittest.cc
@@ -0,0 +1,389 @@
+// 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.
+
+#include <string>
+#include <vector>
+
+#include "base/logging.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/memory/scoped_vector.h"
+#include "base/strings/string_number_conversions.h"
+#include "base/time.h"
+#include "chrome/browser/net/evicted_domain_cookie_counter.h"
+#include "googleurl/src/gurl.h"
+#include "net/cookies/canonical_cookie.h"
+#include "net/cookies/cookie_monster.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace chrome_browser_net {
+
+using base::Time;
+using base::TimeDelta;
+
+namespace {
+
+const char* google_url1 = "http://www.google.com";
+const char* google_url2 = "http://mail.google.com";
+const char* other_url1 = "http://www.example.com";
+const char* other_url2 = "http://www.example.co.uk";
+
+class EvictedDomainCookieCounterTest : public testing::Test {
+ protected:
+  class MockDelegate : public EvictedDomainCookieCounter::Delegate {
+   public:
+    explicit MockDelegate(EvictedDomainCookieCounterTest* tester);
+
+    // EvictedDomainCookieCounter::Delegate implementation.
+    virtual void Report(
+        const EvictedDomainCookieCounter::EvictedCookie& evicted_cookie,
+        const Time& reinstatement_time) OVERRIDE;
+    virtual Time CurrentTime() const OVERRIDE;
+
+   private:
+    EvictedDomainCookieCounterTest* tester_;
+  };
+
+  EvictedDomainCookieCounterTest();
+  virtual ~EvictedDomainCookieCounterTest();
+
+  // testing::Test implementation.
+  virtual void SetUp() OVERRIDE;
+  virtual void TearDown() OVERRIDE;
+
+  // Initialization that allows parameters to be specified.
+  void InitCounter(size_t max_size, size_t purge_count);
+
+  // Wrapper to allocate new cookie and store it in |cookies_|.
+  // If |max_age| == 0, then the cookie does not expire.
+  void CreateNewCookie(
+      const char* url, const std::string& cookie_line, int64 max_age);
+
+  // Clears |cookies_| and creates common cookies for multiple tests.
+  void InitStockCookies();
+
+  // Sets simulation time to |rel_time|.
+  void GotoTime(int64 rel_time);
+
+  // Simulates time-passage by |delta_second|.
+  void StepTime(int64 delta_second);
+
+  // Simulates cookie addition or update.
+  void Add(net::CanonicalCookie* cookie);
+
+  // Simulates cookie removal.
+  void Remove(net::CanonicalCookie* cookie);
+
+  // Simulates cookie eviction.
+  void Evict(net::CanonicalCookie* cookie);
+
+  // For semi-realism, time considered are relative to |mock_time_base_|.
+  Time mock_time_base_;
+  Time mock_time_;
+
+  // To store allocated cookies for reuse.
+  ScopedVector<net::CanonicalCookie> cookies_;
+
+  scoped_refptr<EvictedDomainCookieCounter> cookie_counter_;
+
+  // Statistics as comma-separated string of duration (in seconds) between
+  // eviction and reinstatement for each cookie, in the order of eviction.
+  std::string google_stat_;
+  std::string other_stat_;
+};
+
+EvictedDomainCookieCounterTest::MockDelegate::MockDelegate(
+    EvictedDomainCookieCounterTest* tester)
+    : tester_(tester) {}
+
+void EvictedDomainCookieCounterTest::MockDelegate::Report(
+    const EvictedDomainCookieCounter::EvictedCookie& evicted_cookie,
+    const Time& reinstatement_time) {
+  std::string& dest = evicted_cookie.is_google ?
+      tester_->google_stat_ : tester_->other_stat_;
+  if (!dest.empty())
+    dest.append(",");
+  TimeDelta delta(reinstatement_time - evicted_cookie.eviction_time);
+  dest.append(base::Int64ToString(delta.InSeconds()));
+}
+
+Time EvictedDomainCookieCounterTest::MockDelegate::CurrentTime() const {
+  return tester_->mock_time_;
+}
+
+EvictedDomainCookieCounterTest::EvictedDomainCookieCounterTest() {}
+
+EvictedDomainCookieCounterTest::~EvictedDomainCookieCounterTest() {}
+
+void EvictedDomainCookieCounterTest::SetUp() {
+  mock_time_base_ = Time::Now() - TimeDelta::FromHours(1);
+  mock_time_ = mock_time_base_;
+}
+
+void EvictedDomainCookieCounterTest::TearDown() {
+}
+
+void EvictedDomainCookieCounterTest::InitCounter(size_t max_size,
+                                                 size_t purge_count) {
+  scoped_ptr<MockDelegate> cookie_counter_delegate(new MockDelegate(this));
+  cookie_counter_ = new EvictedDomainCookieCounter(
+      NULL,
+      cookie_counter_delegate.PassAs<EvictedDomainCookieCounter::Delegate>(),
+      max_size,
+      purge_count);
+}
+
+void EvictedDomainCookieCounterTest::CreateNewCookie(
+    const char* url, const std::string& cookie_line, int64 max_age) {
+  std::string line(cookie_line);
+  if (max_age)
+    line.append(";max-age=" + base::Int64ToString(max_age));
+  net::CanonicalCookie* cookie = net::CanonicalCookie::Create(
+      GURL(url), line, mock_time_, net::CookieOptions());
+  DCHECK(cookie);
+  cookies_.push_back(cookie);
+}
+
+void EvictedDomainCookieCounterTest::InitStockCookies() {
+  cookies_.clear();
+  CreateNewCookie(google_url1, "a1=1", 3000);           // cookies_[0].
+  CreateNewCookie(google_url2, "a2=1", 2000);           // cookies_[1].
+  CreateNewCookie(other_url1, "a1=1", 1000);            // cookies_[2].
+  CreateNewCookie(other_url1, "a2=1", 1001);            // cookies_[3].
+  CreateNewCookie(google_url1, "a1=1;Path=/sub", 999);  // cookies_[4].
+  CreateNewCookie(other_url2, "a2=1", 0);               // cookies_[5].
+}
+
+void EvictedDomainCookieCounterTest::GotoTime(int64 rel_time) {
+  mock_time_ = mock_time_base_ + TimeDelta::FromSeconds(rel_time);
+}
+
+void EvictedDomainCookieCounterTest::StepTime(int64 delta_second) {
+  mock_time_ += TimeDelta::FromSeconds(delta_second);
+}
+
+void EvictedDomainCookieCounterTest::Add(net::CanonicalCookie* cookie) {
+  cookie_counter_->OnCookieChanged(
+      *cookie, false, net::CookieMonster::Delegate::CHANGE_COOKIE_EXPLICIT);
+}
+
+void EvictedDomainCookieCounterTest::Remove(net::CanonicalCookie* cookie) {
+  cookie_counter_->OnCookieChanged(
+      *cookie, true, net::CookieMonster::Delegate::CHANGE_COOKIE_EXPLICIT);
+}
+
+void EvictedDomainCookieCounterTest::Evict(net::CanonicalCookie* cookie) {
+  cookie_counter_->OnCookieChanged(
+      *cookie, true, net::CookieMonster::Delegate::CHANGE_COOKIE_EVICTED);
+}
+
+// EvictedDomainCookieCounter takes (and owns) a CookieMonster::Delegate for
+// chaining. To ensure that the chaining indeed occurs, we implement a
+// dummy CookieMonster::Delegate to increment an integer.
+TEST_F(EvictedDomainCookieCounterTest, TestChain) {
+  int result = 0;
+
+  class ChangedDelegateDummy : public net::CookieMonster::Delegate {
+   public:
+    explicit ChangedDelegateDummy(int* result) : result_(result) {}
+
+    virtual void OnCookieChanged(const net::CanonicalCookie& cookie,
+                                 bool removed,
+                                 ChangeCause cause) OVERRIDE {
+      ++(*result_);
+    }
+
+   private:
+    virtual ~ChangedDelegateDummy() {}
+
+    int* result_;
+  };
+
+  scoped_ptr<MockDelegate> cookie_counter_delegate(new MockDelegate(this));
+  cookie_counter_ = new EvictedDomainCookieCounter(
+      new ChangedDelegateDummy(&result),
+      cookie_counter_delegate.PassAs<EvictedDomainCookieCounter::Delegate>(),
+      10,
+      5);
+  InitStockCookies();
+  // Perform 6 cookie transactions.
+  for (int i = 0; i < 6; ++i) {
+    Add(cookies_[i]);
+    StepTime(1);
+    Evict(cookies_[i]);
+    StepTime(1);
+    Remove(cookies_[i]);
+  }
+  EXPECT_EQ(18, result);  // 6 cookies x 3 operations each.
+}
+
+// Basic flow: add cookies, evict, then reinstate.
+TEST_F(EvictedDomainCookieCounterTest, TestBasicFlow) {
+  InitCounter(10, 4);
+  InitStockCookies();
+  // Add all cookies at (relative time) t = 0.
+  for (int i = 0; i < 6; ++i)
+    Add(cookies_[i]);
+  EXPECT_EQ(0u, cookie_counter_->GetStorageSize());  // No activities on add.
+  EXPECT_EQ(";", google_stat_ + ";" + other_stat_);
+  // Evict cookies at t = [1,3,6,10,15,21].
+  for (int i = 0; i < 6; ++i) {
+    StepTime(i + 1);
+    Evict(cookies_[i]);
+  }
+  EXPECT_EQ(6u, cookie_counter_->GetStorageSize());  // Storing all evictions.
+  EXPECT_EQ(";", google_stat_ + ";" + other_stat_);
+  // Reinstate cookies at t = [22,23,24,25,26,27].
+  for (int i = 0; i < 6; ++i) {
+    StepTime(1);
+    Add(cookies_[i]);
+  }
+  EXPECT_EQ(0u, cookie_counter_->GetStorageSize());  // Everything is removed.
+  // Expected reinstatement delays: [21,20,18,15,11,6].
+  EXPECT_EQ("21,20,11;18,15,6", google_stat_ + ";" + other_stat_);
+}
+
+// Removed cookies are ignored by EvictedDomainCookieCounter.
+TEST_F(EvictedDomainCookieCounterTest, TestRemove) {
+  InitCounter(10, 4);
+  InitStockCookies();
+  // Add all cookies at (relative time) t = 0.
+  for (int i = 0; i < 6; ++i)
+    Add(cookies_[i]);
+  // Remove cookies at t = [1,3,6,10,15,21].
+  for (int i = 0; i < 6; ++i) {
+    StepTime(i + 1);
+    Remove(cookies_[i]);
+  }
+  EXPECT_EQ(0u, cookie_counter_->GetStorageSize());
+  // Add cookies again at t = [22,23,24,25,26,27].
+  for (int i = 0; i < 5; ++i) {
+    StepTime(1);
+    Add(cookies_[i]);
+  }
+  EXPECT_EQ(0u, cookie_counter_->GetStorageSize());
+  // No cookies were evicted, so no reinstatement take place.
+  EXPECT_EQ(";", google_stat_ + ";" + other_stat_);
+}
+
+// Expired cookies should not be counted by EvictedDomainCookieCounter.
+TEST_F(EvictedDomainCookieCounterTest, TestExpired) {
+  InitCounter(10, 4);
+  InitStockCookies();
+  // Add all cookies at (relative time) t = 0.
+  for (int i = 0; i < 6; ++i)
+    Add(cookies_[i]);
+  // Evict cookies at t = [1,3,6,10,15,21].
+  for (int i = 0; i < 6; ++i) {
+    StepTime(i + 1);
+    Evict(cookies_[i]);
+  }
+  EXPECT_EQ(6u, cookie_counter_->GetStorageSize());
+  GotoTime(1000);  // t = 1000, so cookies_[2,4] expire.
+
+  // Reinstate cookies at t = [1000,1000,(1000),1000,(1000),1000].
+  InitStockCookies();  // Refresh cookies, so new cookies expire in the future.
+  for (int i = 0; i < 6; ++i)
+    Add(cookies_[i]);
+  EXPECT_EQ(0u, cookie_counter_->GetStorageSize());
+  // Reinstatement delays: [999,997,(994),990,(985),979].
+  EXPECT_EQ("999,997;990,979", google_stat_ + ";" + other_stat_);
+}
+
+// Garbage collection should remove the oldest evicted cookies.
+TEST_F(EvictedDomainCookieCounterTest, TestGarbageCollection) {
+  InitCounter(4, 2);  // Reduced capacity.
+  InitStockCookies();
+  // Add all cookies at (relative time) t = 0.
+  for (int i = 0; i < 6; ++i)
+    Add(cookies_[i]);
+  // Evict cookies at t = [1,3,6,10].
+  for (int i = 0; i < 4; ++i) {
+    StepTime(i + 1);
+    Evict(cookies_[i]);
+  }
+  EXPECT_EQ(4u, cookie_counter_->GetStorageSize());  // Reached capacity.
+  StepTime(5);
+  Evict(cookies_[4]);  // Evict at t = 15, garbage collection takes place.
+  EXPECT_EQ(2u, cookie_counter_->GetStorageSize());
+  StepTime(6);
+  Evict(cookies_[5]);  // Evict at t = 21.
+  EXPECT_EQ(3u, cookie_counter_->GetStorageSize());
+  EXPECT_EQ(";", google_stat_ + ";" + other_stat_);
+  // Reinstate cookies at t = [(100),(100),(100),100,100,100].
+  GotoTime(100);
+  for (int i = 0; i < 6; ++i)
+    Add(cookies_[i]);
+  // Expected reinstatement delays: [(99),(97),(94),90,85,79]
+  EXPECT_EQ("85;90,79", google_stat_ + ";" + other_stat_);
+}
+
+// Garbage collection should remove the specified number of evicted cookies
+// even when there are ties amongst oldest evicted cookies.
+TEST_F(EvictedDomainCookieCounterTest, TestGarbageCollectionTie) {
+  InitCounter(9, 3);
+  // Add 10 cookies at time [0,1,3,6,...,45]
+  for (int i = 0; i < 10; ++i) {
+    StepTime(i);
+    CreateNewCookie(google_url1, "a" + base::IntToString(i) + "=1", 3000);
+    Add(cookies_[i]);
+  }
+  // Evict 6 cookies at t = [100,...,100].
+  GotoTime(100);
+  for (int i = 0; i < 6; ++i)
+    Evict(cookies_[i]);
+  EXPECT_EQ(6u, cookie_counter_->GetStorageSize());
+  // Evict 3 cookies at t = [210,220,230].
+  GotoTime(200);
+  for (int i = 6; i < 9; ++i) {
+    StepTime(10);
+    Evict(cookies_[i]);
+  }
+  EXPECT_EQ(9u, cookie_counter_->GetStorageSize());  // Reached capacity.
+  // Evict 1 cookie at t = 300, and garbage collection takes place.
+  GotoTime(300);
+  Evict(cookies_[9]);
+  // Some arbitrary 4 out of 6 cookies evicted at t = 100 are gone from storage.
+  EXPECT_EQ(6u, cookie_counter_->GetStorageSize());  // 10 - 4.
+  // Reinstate cookies at t = [400,...,400].
+  GotoTime(400);
+  for (int i = 0; i < 10; ++i)
+    Add(cookies_[i]);
+  EXPECT_EQ(0u, cookie_counter_->GetStorageSize());
+  // Expected reinstatement delays:
+  // [300,300,300,300,300,300 <= keeping 2 only,190,180,170,100].
+  EXPECT_EQ("300,300,190,180,170,100;", google_stat_ + ";" + other_stat_);
+}
+
+// Garbage collection prioritize removal of expired cookies.
+TEST_F(EvictedDomainCookieCounterTest, TestGarbageCollectionWithExpiry) {
+  InitCounter(5, 1);
+  InitStockCookies();
+  // Add all cookies at (relative time) t = 0.
+  for (int i = 0; i < 6; ++i)
+    Add(cookies_[i]);
+  // Evict cookies at t = [1,3,6,10,15].
+  for (int i = 0; i < 5; ++i) {
+    StepTime(i + 1);
+    Evict(cookies_[i]);
+  }
+  EXPECT_EQ(5u, cookie_counter_->GetStorageSize());  // Reached capacity.
+  GotoTime(1200);  // t = 1200, so cookies_[2,3,4] expire.
+  // Evict cookies_[5] (not expired) at t = 1200.
+  Evict(cookies_[5]);
+  // Garbage collection would have taken place, removing 3 expired cookies,
+  // so that there's no need to remove more.
+  EXPECT_EQ(3u, cookie_counter_->GetStorageSize());
+  // Reinstate cookies at t = [1500,1500,(1500),(1500),(1500),1500].
+  GotoTime(1500);
+  InitStockCookies();  // Refresh cookies, so new cookies expire in the future.
+  for (int i = 0; i < 6; ++i)
+    Add(cookies_[i]);
+  EXPECT_EQ(0u, cookie_counter_->GetStorageSize());
+  // Reinstatement delays: [1499,1497,(1494),(1490),(1485),300].
+  EXPECT_EQ("1499,1497;300", google_stat_ + ";" + other_stat_);
+}
+
+}  // namespace
+
+}  // namespace chrome_browser_net
diff --git a/chrome/browser/profiles/profile_io_data.cc b/chrome/browser/profiles/profile_io_data.cc
index b4289ab..597f060 100644
--- a/chrome/browser/profiles/profile_io_data.cc
+++ b/chrome/browser/profiles/profile_io_data.cc
@@ -36,6 +36,7 @@
 #include "chrome/browser/net/chrome_http_user_agent_settings.h"
 #include "chrome/browser/net/chrome_net_log.h"
 #include "chrome/browser/net/chrome_network_delegate.h"
+#include "chrome/browser/net/evicted_domain_cookie_counter.h"
 #include "chrome/browser/net/load_time_stats.h"
 #include "chrome/browser/net/proxy_service_factory.h"
 #include "chrome/browser/net/resource_prefetch_predictor_observer.h"
@@ -229,7 +230,8 @@ void ProfileIOData::InitializeOnUIThread(Profile* profile) {
       base::Bind(&GetProfileOnUI, g_browser_process->profile_manager(),
                  profile);
   params->cookie_monster_delegate =
-      new ChromeCookieMonsterDelegate(profile_getter);
+      new chrome_browser_net::EvictedDomainCookieCounter(
+          new ChromeCookieMonsterDelegate(profile_getter));
   params->extension_info_map =
       extensions::ExtensionSystem::Get(profile)->info_map();
 
diff --git a/chrome/chrome_browser.gypi b/chrome/chrome_browser.gypi
index c089aaa..2fbed22 100644
--- a/chrome/chrome_browser.gypi
+++ b/chrome/chrome_browser.gypi
@@ -1017,6 +1017,8 @@
         'browser/net/dns_probe_job.h',
         'browser/net/dns_probe_service.cc',
         'browser/net/dns_probe_service.h',
+        'browser/net/evicted_domain_cookie_counter.cc',
+        'browser/net/evicted_domain_cookie_counter.h',
         'browser/net/gaia/gaia_oauth_consumer.h',
         'browser/net/gaia/gaia_oauth_fetcher.cc',
         'browser/net/gaia/gaia_oauth_fetcher.h',
diff --git a/chrome/chrome_tests_unit.gypi b/chrome/chrome_tests_unit.gypi
index 2f0f749..5142f2d 100644
--- a/chrome/chrome_tests_unit.gypi
+++ b/chrome/chrome_tests_unit.gypi
@@ -895,6 +895,7 @@
         'browser/net/connection_tester_unittest.cc',
         'browser/net/dns_probe_job_unittest.cc',
         'browser/net/dns_probe_service_unittest.cc',
+        'browser/net/evicted_domain_cookie_counter_unittest.cc',
         'browser/net/gaia/gaia_oauth_fetcher_unittest.cc',
         'browser/net/http_pipelining_compatibility_client_unittest.cc',
         'browser/net/http_server_properties_manager_unittest.cc',
diff --git a/net/cookies/canonical_cookie.h b/net/cookies/canonical_cookie.h
index 88bc788..6c9a222 100644
--- a/net/cookies/canonical_cookie.h
+++ b/net/cookies/canonical_cookie.h
@@ -82,7 +82,7 @@ class NET_EXPORT CanonicalCookie {
     return !domain_.empty() && domain_[0] == '.'; }
   bool IsHostCookie() const { return !IsDomainCookie(); }
 
-  bool IsExpired(const base::Time& current) {
+  bool IsExpired(const base::Time& current) const {
     return !expiry_date_.is_null() && current >= expiry_date_;
   }
 
diff --git a/net/cookies/cookie_monster.h b/net/cookies/cookie_monster.h
index e39cfe1..9066b84 100644
--- a/net/cookies/cookie_monster.h
+++ b/net/cookies/cookie_monster.h
@@ -646,7 +646,7 @@ class NET_EXPORT CookieMonster : public CookieStore {
   DISALLOW_COPY_AND_ASSIGN(CookieMonster);
 };
 
-class CookieMonster::Delegate
+class NET_EXPORT CookieMonster::Delegate
     : public base::RefCountedThreadSafe<CookieMonster::Delegate> {
  public:
   // The publicly relevant reasons a cookie might be changed.