Implementing priority-aware cookie eviction algorithm.

This is the final step in the cookie priority project.

If garbage collection occurs due to cookies exceeding domain  limits (even after clearing expired cookies), previously cookies are evicted by the least-recent accessed first.

In the new scheme, a cookie can have a priority in {low, medium, high}. These priorities are associated with quotas {L, M, H} (with L + M + H = 150), to specify priority-protection from eviction.

When then number cookies exceed domain limit, purging is done in 3 rounds.
- Round 1: consider low-priority cookies only: evict least-recently accessed, while protecting L of these from deletion.
- Round 2: consider {low, medium}-priority cookies, evict least-recently accessed, while protecting L + M.
- Round 3: consider all cookies, evict least-recently accessed, effectively protecting L + M + H.

Much restructuring is done to the existing cookie eviction algorithm. This affects the eviction code (but not functionality) for global cookie eviction

We wish to use Finch measure the effect of this change on cookie eviction and reinstatement. Therefore the feature is off by default. The switch to activate the feature is:

CookieMonster::SetPriorityAwareGarbageCollection().

BUG=232693

Review URL: https://chromiumcodereview.appspot.com/14060018

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

3 files changed, 380 insertions, 139 deletions

diff --git a/net/cookies/cookie_monster.cc b/net/cookies/cookie_monster.cc
index c9b386a..0b0bb68 100644
--- a/net/cookies/cookie_monster.cc
+++ b/net/cookies/cookie_monster.cc
@@ -45,6 +45,7 @@
 #include "net/cookies/cookie_monster.h"
 
 #include <algorithm>
+#include <functional>
 #include <set>
 
 #include "base/basictypes.h"
@@ -97,6 +98,14 @@ const size_t CookieMonster::kDomainMaxCookies           = 180;
 const size_t CookieMonster::kDomainPurgeCookies         = 30;
 const size_t CookieMonster::kMaxCookies                 = 3300;
 const size_t CookieMonster::kPurgeCookies               = 300;
+
+const size_t CookieMonster::kDomainCookiesQuotaLow    = 30;
+const size_t CookieMonster::kDomainCookiesQuotaMedium = 50;
+const size_t CookieMonster::kDomainCookiesQuotaHigh   =
+    CookieMonster::kDomainMaxCookies - CookieMonster::kDomainPurgeCookies
+    - CookieMonster::kDomainCookiesQuotaLow
+    - CookieMonster::kDomainCookiesQuotaMedium;
+
 const int CookieMonster::kSafeFromGlobalPurgeDays       = 30;
 
 namespace {
@@ -132,7 +141,7 @@ bool CookieSorter(CanonicalCookie* cc1, CanonicalCookie* cc2) {
   return cc1->Path().length() > cc2->Path().length();
 }
 
-bool LRUCookieSorter(const CookieMonster::CookieMap::iterator& it1,
+bool LRACookieSorter(const CookieMonster::CookieMap::iterator& it1,
                      const CookieMonster::CookieMap::iterator& it2) {
   // Cookies accessed less recently should be deleted first.
   if (it1->second->LastAccessDate() != it2->second->LastAccessDate())
@@ -192,36 +201,57 @@ bool GetCookieDomain(const GURL& url,
   return cookie_util::GetCookieDomainWithString(url, domain_string, result);
 }
 
-// Helper for GarbageCollection.  If |cookie_its->size() > num_max|, remove the
-// |num_max - num_purge| most recently accessed cookies from cookie_its.
-// (In other words, leave the entries that are candidates for
-// eviction in cookie_its.)  The cookies returned will be in order sorted by
-// access time, least recently accessed first.  The access time of the least
-// recently accessed entry not returned will be placed in
-// |*lra_removed| if that pointer is set.  FindLeastRecentlyAccessed
-// returns false if no manipulation is done (because the list size is less
-// than num_max), true otherwise.
-bool FindLeastRecentlyAccessed(
-    size_t num_max,
-    size_t num_purge,
-    Time* lra_removed,
-    std::vector<CookieMonster::CookieMap::iterator>* cookie_its) {
-  DCHECK_LE(num_purge, num_max);
-  if (cookie_its->size() > num_max) {
-    VLOG(kVlogGarbageCollection)
-        << "FindLeastRecentlyAccessed() Deep Garbage Collect.";
-    num_purge += cookie_its->size() - num_max;
-    DCHECK_GT(cookie_its->size(), num_purge);
-
-    // Add 1 so that we can get the last time left in the store.
-    std::partial_sort(cookie_its->begin(), cookie_its->begin() + num_purge + 1,
-                      cookie_its->end(), LRUCookieSorter);
-    *lra_removed =
-        (*(cookie_its->begin() + num_purge))->second->LastAccessDate();
-    cookie_its->erase(cookie_its->begin() + num_purge, cookie_its->end());
-    return true;
+// For a CookieItVector iterator range [|it_begin|, |it_end|),
+// sorts the first |num_sort| + 1 elements by LastAccessDate().
+// The + 1 element exists so for any interval of length <= |num_sort| starting
+// from |cookies_its_begin|, a LastAccessDate() bound can be found.
+void SortLeastRecentlyAccessed(
+    CookieMonster::CookieItVector::iterator it_begin,
+    CookieMonster::CookieItVector::iterator it_end,
+    size_t num_sort) {
+  DCHECK_LT(static_cast<int>(num_sort), it_end - it_begin);
+  std::partial_sort(it_begin, it_begin + num_sort + 1, it_end, LRACookieSorter);
+}
+
+// Predicate to support PartitionCookieByPriority().
+struct CookiePriorityEqualsTo
+    : std::unary_function<const CookieMonster::CookieMap::iterator, bool> {
+  CookiePriorityEqualsTo(CookiePriority priority)
+    : priority_(priority) {}
+
+  bool operator()(const CookieMonster::CookieMap::iterator it) const {
+    return it->second->Priority() == priority_;
   }
-  return false;
+
+  const CookiePriority priority_;
+};
+
+// For a CookieItVector iterator range [|it_begin|, |it_end|),
+// moves all cookies with a given |priority| to the beginning of the list.
+// Returns: An iterator in [it_begin, it_end) to the first element with
+// priority != |priority|, or |it_end| if all have priority == |priority|.
+CookieMonster::CookieItVector::iterator PartitionCookieByPriority(
+    CookieMonster::CookieItVector::iterator it_begin,
+    CookieMonster::CookieItVector::iterator it_end,
+    CookiePriority priority) {
+  return std::partition(it_begin, it_end, CookiePriorityEqualsTo(priority));
+}
+
+bool LowerBoundAccessDateComparator(
+  const CookieMonster::CookieMap::iterator it, const Time& access_date) {
+  return it->second->LastAccessDate() < access_date;
+}
+
+// For a CookieItVector iterator range [|it_begin|, |it_end|)
+// from a CookieItVector sorted by LastAccessDate(), returns the
+// first iterator with access date >= |access_date|, or cookie_its_end if this
+// holds for all.
+CookieMonster::CookieItVector::iterator LowerBoundAccessDate(
+    const CookieMonster::CookieItVector::iterator its_begin,
+    const CookieMonster::CookieItVector::iterator its_end,
+    const Time& access_date) {
+  return std::lower_bound(its_begin, its_end, access_date,
+                          LowerBoundAccessDateComparator);
 }
 
 // Mapping between DeletionCause and Delegate::ChangeCause; the mapping also
@@ -288,7 +318,8 @@ CookieMonster::CookieMonster(PersistentCookieStore* store, Delegate* delegate)
       delegate_(delegate),
       last_statistic_record_time_(Time::Now()),
       keep_expired_cookies_(false),
-      persist_session_cookies_(false) {
+      persist_session_cookies_(false),
+      priority_aware_garbage_collection_(false) {
   InitializeHistograms();
   SetDefaultCookieableSchemes();
 }
@@ -304,7 +335,8 @@ CookieMonster::CookieMonster(PersistentCookieStore* store,
       delegate_(delegate),
       last_statistic_record_time_(base::Time::Now()),
       keep_expired_cookies_(false),
-      persist_session_cookies_(false) {
+      persist_session_cookies_(false),
+      priority_aware_garbage_collection_(false) {
   InitializeHistograms();
   SetDefaultCookieableSchemes();
 }
@@ -1293,12 +1325,19 @@ CookieMonster* CookieMonster::GetCookieMonster() {
   return this;
 }
 
+// This function must be called before the CookieMonster is used.
 void CookieMonster::SetPersistSessionCookies(bool persist_session_cookies) {
-  // This function must be called before the CookieMonster is used.
   DCHECK(!initialized_);
   persist_session_cookies_ = persist_session_cookies;
 }
 
+// This function must be called before the CookieMonster is used.
+void CookieMonster::SetPriorityAwareGarbageCollection(
+    bool priority_aware_garbage_collection) {
+  DCHECK(!initialized_);
+  priority_aware_garbage_collection_ = priority_aware_garbage_collection;
+}
+
 void CookieMonster::SetForceKeepSessionState() {
   if (store_) {
     store_->SetForceKeepSessionState();
@@ -1758,78 +1797,124 @@ void CookieMonster::InternalDeleteCookie(CookieMap::iterator it,
 }
 
 // Domain expiry behavior is unchanged by key/expiry scheme (the
-// meaning of the key is different, but that's not visible to this
-// routine).
+// meaning of the key is different, but that's not visible to this routine).
 int CookieMonster::GarbageCollect(const Time& current,
                                   const std::string& key) {
   lock_.AssertAcquired();
 
   int num_deleted = 0;
+  Time safe_date(
+      Time::Now() - TimeDelta::FromDays(kSafeFromGlobalPurgeDays));
 
-  // Collect garbage for this key.
+  // Collect garbage for this key, minding cookie priorities.
   if (cookies_.count(key) > kDomainMaxCookies) {
     VLOG(kVlogGarbageCollection) << "GarbageCollect() key: " << key;
 
-    std::vector<CookieMap::iterator> cookie_its;
+    CookieItVector cookie_its;
     num_deleted += GarbageCollectExpired(
         current, cookies_.equal_range(key), &cookie_its);
-    base::Time oldest_removed;
-    if (FindLeastRecentlyAccessed(kDomainMaxCookies, kDomainPurgeCookies,
-                                  &oldest_removed, &cookie_its)) {
-      // Delete in two passes so we can figure out what we're nuking
-      // that would be kept at the global level.
-      int num_subject_to_global_purge =
-          GarbageCollectDeleteList(
-              current,
-              Time::Now() - TimeDelta::FromDays(kSafeFromGlobalPurgeDays),
-              DELETE_COOKIE_EVICTED_DOMAIN_PRE_SAFE,
-              cookie_its);
-      num_deleted += num_subject_to_global_purge;
-      // Correct because FindLeastRecentlyAccessed returns a sorted list.
-      cookie_its.erase(cookie_its.begin(),
-                       cookie_its.begin() + num_subject_to_global_purge);
-      num_deleted +=
-          GarbageCollectDeleteList(
-              current,
-              Time(),
-              DELETE_COOKIE_EVICTED_DOMAIN_POST_SAFE,
-              cookie_its);
+    if (cookie_its.size() > kDomainMaxCookies) {
+      VLOG(kVlogGarbageCollection) << "Deep Garbage Collect domain.";
+      size_t purge_goal =
+          cookie_its.size() - (kDomainMaxCookies - kDomainPurgeCookies);
+      DCHECK(purge_goal > kDomainPurgeCookies);
+
+      // Boundary iterators into |cookie_its| for different priorities.
+      CookieItVector::iterator it_bdd[4];
+      // Intialize |it_bdd| while sorting |cookie_its| by priorities.
+      // Schematic: [MLLHMHHLMM] => [LLL|MMMM|HHH], with 4 boundaries.
+      it_bdd[0] = cookie_its.begin();
+      it_bdd[3] = cookie_its.end();
+      it_bdd[1] = PartitionCookieByPriority(it_bdd[0], it_bdd[3],
+                                            COOKIE_PRIORITY_LOW);
+      it_bdd[2] = PartitionCookieByPriority(it_bdd[1], it_bdd[3],
+                                            COOKIE_PRIORITY_MEDIUM);
+      size_t quota[3] = {
+        kDomainCookiesQuotaLow,
+        kDomainCookiesQuotaMedium,
+        kDomainCookiesQuotaHigh
+      };
+
+      // Purge domain cookies in 3 rounds.
+      // Round 1: consider low-priority cookies only: evict least-recently
+      //   accessed, while protecting quota[0] of these from deletion.
+      // Round 2: consider {low, medium}-priority cookies, evict least-recently
+      //   accessed, while protecting quota[0] + quota[1].
+      // Round 3: consider all cookies, evict least-recently accessed.
+      size_t accumulated_quota = 0;
+      CookieItVector::iterator it_purge_begin = it_bdd[0];
+      for (int i = 0; i < 3 && purge_goal > 0; ++i) {
+        accumulated_quota += quota[i];
+
+        // If we are not using priority, only do Round 3. This reproduces the
+        // old way of indiscriminately purging least-recently accessed cookies.
+        if (!priority_aware_garbage_collection_ && i < 2)
+          continue;
+
+        size_t num_considered = it_bdd[i + 1] - it_purge_begin;
+        if (num_considered <= accumulated_quota)
+          continue;
+
+        // Number of cookies that will be purged in this round.
+        size_t round_goal =
+            std::min(purge_goal, num_considered - accumulated_quota);
+        purge_goal -= round_goal;
+
+        SortLeastRecentlyAccessed(it_purge_begin, it_bdd[i + 1], round_goal);
+        // Cookies accessed on or after |safe_date| would have been safe from
+        // global purge, and we want to keep track of this.
+        CookieItVector::iterator it_purge_end = it_purge_begin + round_goal;
+        CookieItVector::iterator it_purge_middle =
+            LowerBoundAccessDate(it_purge_begin, it_purge_end, safe_date);
+        // Delete cookies accessed before |safe_date|.
+        num_deleted += GarbageCollectDeleteRange(
+            current,
+            DELETE_COOKIE_EVICTED_DOMAIN_PRE_SAFE,
+            it_purge_begin,
+            it_purge_middle);
+        // Delete cookies accessed on or after |safe_date|.
+        num_deleted += GarbageCollectDeleteRange(
+            current,
+            DELETE_COOKIE_EVICTED_DOMAIN_POST_SAFE,
+            it_purge_middle,
+            it_purge_end);
+        it_purge_begin = it_purge_end;
+      }
+      DCHECK_EQ(0U, purge_goal);
     }
   }
 
-  // Collect garbage for everything.  With firefox style we want to
-  // preserve cookies touched in kSafeFromGlobalPurgeDays, otherwise
-  // not.
+  // Collect garbage for everything. With firefox style we want to preserve
+  // cookies accessed in kSafeFromGlobalPurgeDays, otherwise evict.
   if (cookies_.size() > kMaxCookies &&
-      (earliest_access_time_ <
-       Time::Now() - TimeDelta::FromDays(kSafeFromGlobalPurgeDays))) {
+      earliest_access_time_ < safe_date) {
     VLOG(kVlogGarbageCollection) << "GarbageCollect() everything";
-    std::vector<CookieMap::iterator> cookie_its;
-    base::Time oldest_left;
+    CookieItVector cookie_its;
     num_deleted += GarbageCollectExpired(
         current, CookieMapItPair(cookies_.begin(), cookies_.end()),
         &cookie_its);
-    if (FindLeastRecentlyAccessed(kMaxCookies, kPurgeCookies,
-                                  &oldest_left, &cookie_its)) {
-      Time oldest_safe_cookie(
-          (Time::Now() - TimeDelta::FromDays(kSafeFromGlobalPurgeDays)));
-      int num_evicted = GarbageCollectDeleteList(
+    if (cookie_its.size() > kMaxCookies) {
+      VLOG(kVlogGarbageCollection) << "Deep Garbage Collect everything.";
+      size_t purge_goal = cookie_its.size() - (kMaxCookies - kPurgeCookies);
+      DCHECK(purge_goal > kPurgeCookies);
+      // Sorts up to *and including* |cookie_its[purge_goal]|, so
+      // |earliest_access_time| will be properly assigned even if
+      // |global_purge_it| == |cookie_its.begin() + purge_goal|.
+      SortLeastRecentlyAccessed(cookie_its.begin(), cookie_its.end(),
+                                purge_goal);
+      // Find boundary to cookies older than safe_date.
+      CookieItVector::iterator global_purge_it =
+          LowerBoundAccessDate(cookie_its.begin(),
+                               cookie_its.begin() + purge_goal,
+                               safe_date);
+      // Only delete the old cookies.
+      num_deleted += GarbageCollectDeleteRange(
           current,
-          oldest_safe_cookie,
           DELETE_COOKIE_EVICTED_GLOBAL,
-          cookie_its);
-
-      // If no cookies were preserved by the time limit, the global last
-      // access is set to the value returned from FindLeastRecentlyAccessed.
-      // If the time limit preserved some cookies, we use the last access of
-      // the oldest preserved cookie.
-      if (num_evicted == static_cast<int>(cookie_its.size())) {
-        earliest_access_time_ = oldest_left;
-      } else {
-        earliest_access_time_ =
-            (*(cookie_its.begin() + num_evicted))->second->LastAccessDate();
-      }
-      num_deleted += num_evicted;
+          cookie_its.begin(),
+          global_purge_it);
+      // Set access day to the oldest cookie that wasn't deleted.
+      earliest_access_time_ = (*global_purge_it)->second->LastAccessDate();
     }
   }
 
@@ -1839,7 +1924,7 @@ int CookieMonster::GarbageCollect(const Time& current,
 int CookieMonster::GarbageCollectExpired(
     const Time& current,
     const CookieMapItPair& itpair,
-    std::vector<CookieMap::iterator>* cookie_its) {
+    CookieItVector* cookie_its) {
   if (keep_expired_cookies_)
     return 0;
 
@@ -1861,23 +1946,17 @@ int CookieMonster::GarbageCollectExpired(
   return num_deleted;
 }
 
-int CookieMonster::GarbageCollectDeleteList(
+int CookieMonster::GarbageCollectDeleteRange(
     const Time& current,
-    const Time& keep_accessed_after,
     DeletionCause cause,
-    std::vector<CookieMap::iterator>& cookie_its) {
-  int num_deleted = 0;
-  for (std::vector<CookieMap::iterator>::iterator it = cookie_its.begin();
-       it != cookie_its.end(); it++) {
-    if (keep_accessed_after.is_null() ||
-        (*it)->second->LastAccessDate() < keep_accessed_after) {
-      histogram_evicted_last_access_minutes_->Add(
-          (current - (*it)->second->LastAccessDate()).InMinutes());
-      InternalDeleteCookie((*it), true, cause);
-      num_deleted++;
-    }
-  }
-  return num_deleted;
+    CookieMonster::CookieItVector::iterator it_begin,
+    CookieMonster::CookieItVector::iterator it_end) {
+  for (CookieItVector::iterator it = it_begin; it != it_end; it++) {
+    histogram_evicted_last_access_minutes_->Add(
+        (current - (*it)->second->LastAccessDate()).InMinutes());
+    InternalDeleteCookie((*it), true, cause);
+  }
+  return it_end - it_begin;
 }
 
 // A wrapper around RegistryControlledDomainService::GetDomainAndRegistry
diff --git a/net/cookies/cookie_monster.h b/net/cookies/cookie_monster.h
index bb7686e..c957539 100644
--- a/net/cookies/cookie_monster.h
+++ b/net/cookies/cookie_monster.h
@@ -106,6 +106,31 @@ class NET_EXPORT CookieMonster : public CookieStore {
   // subtantially more entries in the map.
   typedef std::multimap<std::string, CanonicalCookie*> CookieMap;
   typedef std::pair<CookieMap::iterator, CookieMap::iterator> CookieMapItPair;
+  typedef std::vector<CookieMap::iterator> CookieItVector;
+
+  // Cookie garbage collection thresholds.  Based off of the Mozilla defaults.
+  // When the number of cookies gets to k{Domain,}MaxCookies
+  // purge down to k{Domain,}MaxCookies - k{Domain,}PurgeCookies.
+  // It might seem scary to have a high purge value, but really it's not.
+  // You just make sure that you increase the max to cover the increase
+  // in purge, and we would have been purging the same number of cookies.
+  // We're just going through the garbage collection process less often.
+  // Note that the DOMAIN values are per eTLD+1; see comment for the
+  // CookieMap typedef.  So, e.g., the maximum number of cookies allowed for
+  // google.com and all of its subdomains will be 150-180.
+  //
+  // Any cookies accessed more recently than kSafeFromGlobalPurgeDays will not
+  // be evicted by global garbage collection, even if we have more than
+  // kMaxCookies.  This does not affect domain garbage collection.
+  static const size_t kDomainMaxCookies;
+  static const size_t kDomainPurgeCookies;
+  static const size_t kMaxCookies;
+  static const size_t kPurgeCookies;
+
+  // Quota for cookies with {low, medium, high} priorities within a domain.
+  static const size_t kDomainCookiesQuotaLow;
+  static const size_t kDomainCookiesQuotaMedium;
+  static const size_t kDomainCookiesQuotaHigh;
 
   // The store passed in should not have had Init() called on it yet. This
   // class will take care of initializing it. The backing store is NOT owned by
@@ -255,6 +280,11 @@ class NET_EXPORT CookieMonster : public CookieStore {
   // (i.e. as part of the instance initialization process).
   void SetPersistSessionCookies(bool persist_session_cookies);
 
+  // Enables the new garbage collection algorithm where domain cookie eviction
+  // uses cookie priorities to decide which cookies to purge and which to keep.
+  void SetPriorityAwareGarbageCollection(
+      bool priority_aware_garbage_collection);
+
   // Debugging method to perform various validation checks on the map.
   // Currently just checking that there are no null CanonicalCookie pointers
   // in the map.
@@ -340,28 +370,6 @@ class NET_EXPORT CookieMonster : public CookieStore {
     DELETE_COOKIE_LAST_ENTRY
   };
 
-  // Cookie garbage collection thresholds.  Based off of the Mozilla defaults.
-  // When the number of cookies gets to k{Domain,}MaxCookies
-  // purge down to k{Domain,}MaxCookies - k{Domain,}PurgeCookies.
-  // It might seem scary to have a high purge value, but really it's not.
-  // You just make sure that you increase the max to cover the increase
-  // in purge, and we would have been purging the same amount of cookies.
-  // We're just going through the garbage collection process less often.
-  // Note that the DOMAIN values are per eTLD+1; see comment for the
-  // CookieMap typedef.  So, e.g., the maximum number of cookies allowed for
-  // google.com and all of its subdomains will be 150-180.
-  //
-  // Any cookies accessed more recently than kSafeFromGlobalPurgeDays will not
-  // be evicted by global garbage collection, even if we have more than
-  // kMaxCookies.  This does not affect domain garbage collection.
-  //
-  // Present in .h file to make accessible to tests through FRIEND_TEST.
-  // Actual definitions are in cookie_monster.cc.
-  static const size_t kDomainMaxCookies;
-  static const size_t kDomainPurgeCookies;
-  static const size_t kMaxCookies;
-  static const size_t kPurgeCookies;
-
   // The number of days since last access that cookies will not be subject
   // to global garbage collection.
   static const int kSafeFromGlobalPurgeDays;
@@ -538,14 +546,12 @@ class NET_EXPORT CookieMonster : public CookieStore {
                             const CookieMapItPair& itpair,
                             std::vector<CookieMap::iterator>* cookie_its);
 
-  // Helper for GarbageCollect().  Deletes all cookies in the list
-  // that were accessed before |keep_accessed_after|, using DeletionCause
-  // |cause|.  If |keep_accessed_after| is null, deletes all cookies in the
-  // list.  Returns the number of cookies deleted.
-  int GarbageCollectDeleteList(const base::Time& current,
-                               const base::Time& keep_accessed_after,
-                               DeletionCause cause,
-                               std::vector<CookieMap::iterator>& cookie_its);
+  // Helper for GarbageCollect(). Deletes all cookies in the range specified by
+  // [|it_begin|, |it_end|). Returns the number of cookies deleted.
+  int GarbageCollectDeleteRange(const base::Time& current,
+                                DeletionCause cause,
+                                CookieItVector::iterator cookie_its_begin,
+                                CookieItVector::iterator cookie_its_end);
 
   // Find the key (for lookup in cookies_) based on the given domain.
   // See comment on keys before the CookieMap typedef.
@@ -650,6 +656,7 @@ class NET_EXPORT CookieMonster : public CookieStore {
 
   bool keep_expired_cookies_;
   bool persist_session_cookies_;
+  bool priority_aware_garbage_collection_;
 
   // Static setting for whether or not file scheme cookies are allows when
   // a new CookieMonster is created, or the accepted schemes on a CookieMonster
diff --git a/net/cookies/cookie_monster_unittest.cc b/net/cookies/cookie_monster_unittest.cc
index 9034975..df4fa9d 100644
--- a/net/cookies/cookie_monster_unittest.cc
+++ b/net/cookies/cookie_monster_unittest.cc
@@ -4,7 +4,9 @@
 
 #include "net/cookies/cookie_store_unittest.h"
 
+#include <algorithm>
 #include <string>
+#include <vector>
 
 #include "base/basictypes.h"
 #include "base/bind.h"
@@ -14,6 +16,9 @@
 #include "base/metrics/histogram.h"
 #include "base/metrics/histogram_samples.h"
 #include "base/stringprintf.h"
+#include "base/strings/string_number_conversions.h"
+#include "base/strings/string_piece.h"
+#include "base/strings/string_split.h"
 #include "base/strings/string_tokenizer.h"
 #include "base/threading/thread.h"
 #include "base/time.h"
@@ -357,9 +362,9 @@ class CookieMonsterTest : public CookieStoreTest<CookieMonsterTestTraits> {
     return std::count(str.begin(), str.end(), c);
   }
 
-  void TestHostGarbageCollectHelper(
-      int domain_max_cookies,
-      int domain_purge_cookies) {
+  void TestHostGarbageCollectHelper() {
+    int domain_max_cookies = CookieMonster::kDomainMaxCookies;
+    int domain_purge_cookies = CookieMonster::kDomainPurgeCookies;
     const int more_than_enough_cookies =
         (domain_max_cookies + domain_purge_cookies) * 2;
     // Add a bunch of cookies on a single host, should purge them.
@@ -402,12 +407,159 @@ class CookieMonsterTest : public CookieStoreTest<CookieMonsterTestTraits> {
       std::string cookies_specific = this->GetCookies(cm, url_google_specific);
       int total_cookies = (CountInString(cookies_general, '=') +
                            CountInString(cookies_specific, '='));
-      EXPECT_GE(total_cookies,
-                domain_max_cookies - domain_purge_cookies);
+      EXPECT_GE(total_cookies, domain_max_cookies - domain_purge_cookies);
       EXPECT_LE(total_cookies, domain_max_cookies);
     }
   }
 
+  CookiePriority CharToPriority(char ch) {
+    switch (ch) {
+      case 'L':
+        return COOKIE_PRIORITY_LOW;
+      case 'M':
+        return COOKIE_PRIORITY_MEDIUM;
+      case 'H':
+        return COOKIE_PRIORITY_HIGH;
+    }
+    NOTREACHED();
+    return COOKIE_PRIORITY_DEFAULT;
+  }
+
+  // Instantiates a CookieMonster, adds multiple cookies (to url_google_) with
+  // priorities specified by |coded_priority_str|, and tests priority-aware
+  // domain cookie eviction.
+  // |coded_priority_str| specifies a run-length-encoded string of priorities.
+  // Example: "2M 3L M 4H" means "MMLLLMHHHH", and speicifies sequential (i.e.,
+  // from least- to most-recently accessed) insertion of 2 medium-priority
+  // cookies, 3 low-priority cookies, 1 medium-priority cookie, and 4
+  // high-priority cookies.
+  // Within each priority, only the least-accessed cookies should be evicted.
+  // Thus, to describe expected suriving cookies, it suffices to specify the
+  // expected population of surviving cookies per priority, i.e.,
+  // |expected_low_count|, |expected_medium_count|, and |expected_high_count|.
+  void TestPriorityCookieCase(CookieMonster* cm,
+                              const std::string& coded_priority_str,
+                              size_t expected_low_count,
+                              size_t expected_medium_count,
+                              size_t expected_high_count) {
+    DeleteAll(cm);
+    int next_cookie_id = 0;
+    std::vector<CookiePriority> priority_list;
+    std::vector<int> id_list[3];  // Indexed by CookiePriority.
+
+    // Parse |coded_priority_str| and add cookies.
+    std::vector<std::string> priority_tok_list;
+    base::SplitString(coded_priority_str, ' ', &priority_tok_list);
+    for (std::vector<std::string>::iterator it = priority_tok_list.begin();
+         it != priority_tok_list.end(); ++it) {
+      size_t len = it->length();
+      DCHECK_NE(len, 0U);
+      // Take last character as priority.
+      CookiePriority priority = CharToPriority((*it)[len - 1]);
+      std::string priority_str = CookiePriorityToString(priority);
+      // The rest of the string (possibly empty) specifies repetition.
+      int rep = 1;
+      if (!it->empty()) {
+        bool result = base::StringToInt(
+            base::StringPiece(it->begin(), it->end() - 1), &rep);
+        DCHECK(result);
+      }
+      for (; rep > 0; --rep, ++next_cookie_id) {
+        std::string cookie = base::StringPrintf(
+            "a%d=b;priority=%s", next_cookie_id, priority_str.c_str());
+        EXPECT_TRUE(SetCookie(cm, url_google_, cookie));
+        priority_list.push_back(priority);
+        id_list[priority].push_back(next_cookie_id);
+      }
+    }
+
+    int num_cookies = static_cast<int>(priority_list.size());
+    std::vector<int> surviving_id_list[3];  // Indexed by CookiePriority.
+
+    // Parse the list of cookies
+    std::string cookie_str = this->GetCookies(cm, url_google_);
+    std::vector<std::string> cookie_tok_list;
+    base::SplitString(cookie_str, ';', &cookie_tok_list);
+    for (std::vector<std::string>::iterator it = cookie_tok_list.begin();
+         it != cookie_tok_list.end(); ++it) {
+      // Assuming *it is "a#=b", so extract and parse "#" portion.
+      int id = -1;
+      bool result = base::StringToInt(
+          base::StringPiece(it->begin() + 1, it->end() - 2), &id);
+      DCHECK(result);
+      DCHECK_GE(id, 0);
+      DCHECK_LT(id, num_cookies);
+      surviving_id_list[priority_list[id]].push_back(id);
+    }
+
+    // Validate each priority.
+    size_t expected_count[3] = {
+      expected_low_count, expected_medium_count, expected_high_count
+    };
+    for (int i = 0; i < 3; ++i) {
+      DCHECK_LE(surviving_id_list[i].size(), id_list[i].size());
+      EXPECT_EQ(expected_count[i], surviving_id_list[i].size());
+      // Verify that the remaining cookies are the most recent among those
+      // with the same priorities.
+      if (expected_count[i] == surviving_id_list[i].size()) {
+        std::sort(surviving_id_list[i].begin(), surviving_id_list[i].end());
+        EXPECT_TRUE(std::equal(surviving_id_list[i].begin(),
+                               surviving_id_list[i].end(),
+                               id_list[i].end() - expected_count[i]));
+      }
+    }
+  }
+
+  void TestPriorityAwareGarbageCollectHelper() {
+    // Hard-coding limits in the test, but use DCHECK_EQ to enforce constraint.
+    DCHECK_EQ(180U, CookieMonster::kDomainMaxCookies);
+    DCHECK_EQ(150U, CookieMonster::kDomainMaxCookies -
+              CookieMonster::kDomainPurgeCookies);
+    DCHECK_EQ(30U, CookieMonster::kDomainCookiesQuotaLow);
+    DCHECK_EQ(50U, CookieMonster::kDomainCookiesQuotaMedium);
+    DCHECK_EQ(70U, CookieMonster::kDomainCookiesQuotaHigh);
+
+    scoped_refptr<CookieMonster> cm(new CookieMonster(NULL, NULL));
+    cm->SetPriorityAwareGarbageCollection(true);
+
+    // Each test case adds 181 cookies, so 31 cookies are evicted.
+    // Cookie same priority, repeated for each priority.
+    TestPriorityCookieCase(cm, "181L", 150U, 0U, 0U);
+    TestPriorityCookieCase(cm, "181M", 0U, 150U, 0U);
+    TestPriorityCookieCase(cm, "181H", 0U, 0U, 150U);
+
+    // Pairwise scenarios.
+    // Round 1 => none; round2 => 31M; round 3 => none.
+    TestPriorityCookieCase(cm, "10H 171M", 0U, 140U, 10U);
+    // Round 1 => 10L; round2 => 21M; round 3 => none.
+    TestPriorityCookieCase(cm, "141M 40L", 30U, 120U, 0U);
+    // Round 1 => none; round2 => none; round 3 => 31H.
+    TestPriorityCookieCase(cm, "101H 80M", 0U, 80U, 70U);
+
+    // For {low, medium} priorities right on quota, different orders.
+    // Round 1 => 1L; round 2 => none, round3 => 30L.
+    TestPriorityCookieCase(cm, "31L 50M 100H", 0U, 50U, 100U);
+    // Round 1 => none; round 2 => 1M, round3 => 30M.
+    TestPriorityCookieCase(cm, "51M 100H 30L", 30U, 20U, 100U);
+    // Round 1 => none; round 2 => none; round3 => 31H.
+    TestPriorityCookieCase(cm, "101H 50M 30L", 30U, 50U, 70U);
+
+    // Round 1 => 10L; round 2 => 10M; round3 => 11H.
+    TestPriorityCookieCase(cm, "81H 60M 40L", 30U, 50U, 70U);
+
+    // More complex scenarios.
+    // Round 1 => 10L; round 2 => 10M; round 3 => 11H.
+    TestPriorityCookieCase(cm, "21H 60M 40L 60H", 30U, 50U, 70U);
+    // Round 1 => 10L; round 2 => 11M, 10L; round 3 => none.
+    TestPriorityCookieCase(cm, "11H 10M 20L 110M 20L 10H", 20U, 109U, 21U);
+    // Round 1 => none; round 2 => none; round 3 => 11L, 10M, 10H.
+    TestPriorityCookieCase(cm, "11L 10M 140H 10M 10L", 10U, 10U, 130U);
+    // Round 1 => none; round 2 => 1M; round 3 => 10L, 10M, 10H.
+    TestPriorityCookieCase(cm, "11M 10H 10L 60M 90H", 0U, 60U, 90U);
+    // Round 1 => none; round 2 => 10L, 21M; round 3 => none.
+    TestPriorityCookieCase(cm, "11M 10H 10L 90M 60H", 0U, 80U, 70U);
+  }
+
   // Function for creating a CM with a number of cookies in it,
   // no store (and hence no ability to affect access time).
   CookieMonster* CreateMonsterForGC(int num_cookies) {
@@ -561,8 +713,8 @@ class DeferredCookieTaskTest : public CookieMonsterTest {
 
   // Defines a cookie to be returned from PersistentCookieStore::Load
   void DeclareLoadedCookie(const std::string& key,
-                      const std::string& cookie_line,
-                      const base::Time& creation_time) {
+                           const std::string& cookie_line,
+                           const base::Time& creation_time) {
     AddCookieToList(key, cookie_line, creation_time, &loaded_cookies_);
   }
 
@@ -1011,8 +1163,11 @@ TEST_F(CookieMonsterTest, TestLastAccess) {
 }
 
 TEST_F(CookieMonsterTest, TestHostGarbageCollection) {
-  TestHostGarbageCollectHelper(
-      CookieMonster::kDomainMaxCookies, CookieMonster::kDomainPurgeCookies);
+  TestHostGarbageCollectHelper();
+}
+
+TEST_F(CookieMonsterTest, TestPriorityAwareGarbageCollection) {
+  TestPriorityAwareGarbageCollectHelper();
 }
 
 TEST_F(CookieMonsterTest, TestDeleteSingleCookie) {