Clean up cookie eviction.

net/cookies/cookie_monster.cc

Index: net/cookies/cookie_monster.cc
diff --git a/net/cookies/cookie_monster.cc b/net/cookies/cookie_monster.cc
index bbec7b018deec16e0f1de01685f837fff165deb4..3489da34312e7c70fc0ad7e8a6670cd760b20667 100644
--- a/net/cookies/cookie_monster.cc
+++ b/net/cookies/cookie_monster.cc
@@ -162,13 +162,10 @@ bool CookieSorter(CanonicalCookie* cc1, CanonicalCookie* cc2) {
 
 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())
     return it1->second->LastAccessDate() < it2->second->LastAccessDate();
 
-  // In rare cases we might have two cookies with identical last access times.
-  // To preserve the stability of the sort, in these cases prefer to delete
-  // older cookies over newer ones.  CreationDate() is guaranteed to be unique.
+  // Ensure stability for == last access times by falling back to creation.
   return it1->second->CreationDate() < it2->second->CreationDate();
 }
 
@@ -250,30 +247,6 @@ void SplitCookieVectorIntoSecureAndNonSecure(
   }
 }
 
-// Predicate to support PartitionCookieByPriority().
-struct CookiePriorityEqualsTo
-    : std::unary_function<const CookieMonster::CookieMap::iterator, bool> {
-  explicit CookiePriorityEqualsTo(CookiePriority priority)
-      : priority_(priority) {}
-
-  bool operator()(const CookieMonster::CookieMap::iterator it) const {
-    return it->second->Priority() == priority_;
-  }
-
-  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;
@@ -1874,6 +1847,7 @@ size_t CookieMonster::GarbageCollect(const Time& current,
     num_deleted +=
         GarbageCollectExpired(current, cookies_.equal_range(key), cookie_its);
 
+    // TODO(mkwst): Soften this.
     CookieItVector secure_cookie_its;
     if (enforce_strict_secure && cookie_its->size() > kDomainMaxCookies) {
       VLOG(kVlogGarbageCollection) << "Garbage collecting non-Secure cookies.";
@@ -1888,56 +1862,26 @@ size_t CookieMonster::GarbageCollect(const Time& current,
           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];
-
-        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;
+      // Sort the cookies by access date, from least-recent to most-recent.
+      std::sort(cookie_its->begin(), cookie_its->end(), LRACookieSorter);
+
+      // Remove all but the kDomainCookiesQuotaLow most-recently accessed
+      // cookies with low-priority. Then, if we still need to remove cookies,

[mmenke, 2016/03/07 17:46:03]

nit:  Avoid we in comments (x2)

[Mike West, 2016/03/08 08:44:56]

Done.

+      // bump the quota and remove low- and medium-priority. Then, if we
+      // _still_ need to remove cookies, bump the quota and remove cookies
+      // with any priority.
+      size_t quotas[3] = {kDomainCookiesQuotaLow, kDomainCookiesQuotaMedium,
+                          kDomainCookiesQuotaHigh};
+      size_t quota = 0;
+      for (size_t i = 0; i < arraysize(quotas) && purge_goal; i++) {
+        quota += quotas[i];
+        size_t just_deleted =
+            PurgeLeastRecentMatches(cookie_its, static_cast<CookiePriority>(i),
+                                    quota, purge_goal, safe_date);
+        purge_goal -= just_deleted;
+        num_deleted += just_deleted;
       }
+
       DCHECK_EQ(0U, purge_goal);
     }
   }
@@ -1985,6 +1929,48 @@ size_t CookieMonster::GarbageCollect(const Time& current,
   return num_deleted;
 }
 
+size_t CookieMonster::PurgeLeastRecentMatches(CookieItVector* cookies,
+                                              CookiePriority priority,
+                                              size_t to_protect,
+                                              size_t purge_goal,
+                                              const base::Time& safe_date) {
+  DCHECK(thread_checker_.CalledOnValidThread());
+
+  // Find the first protected cookie by walking down from the end of the list
+  // cookie list (most-recently accessed) until |to_protect| cookies that match
+  // |priority| are found.
+  CookieItVector::iterator protection_boundary = cookies->end();
+  while (to_protect && protection_boundary > cookies->begin()) {

[mmenke, 2016/03/07 17:46:03]

comparing iterators with ">" instead of != seems weird.  Not sure if it's a
C++0x11 thing or always been allow on iterators to vectors, but seems best to
avoid it.

[mmenke, 2016/03/07 17:46:03]

Suggest to_protect -> to_protect > 0.  They're equivalent, but the latter makes
it a little more explicity what's happening.

[Mike West, 2016/03/08 08:44:56]

Dropped iterators to the extent possible, as below.

+    protection_boundary--;
+    if ((*protection_boundary)->second->Priority() <= priority)
+      to_protect--;
+  }
+
+  // Now, walk up from the beginning of the list (least-recently accessed) until
+  // |purge_goal| cookies are removed, or the iterator hits
+  // |protection_boundary|.
+  size_t removed = 0;
+  CookieItVector::iterator current = cookies->begin();
+  while (removed < purge_goal && current < protection_boundary) {
+    if ((*current)->second->Priority() <= priority) {
+      InternalDeleteCookie(*current, true,
+                           (*current)->second->LastAccessDate() > safe_date
+                               ? DELETE_COOKIE_EVICTED_DOMAIN_PRE_SAFE
+                               : DELETE_COOKIE_EVICTED_DOMAIN_POST_SAFE);
+      current = cookies->erase(current);
+      removed++;
+
+      // The call to 'erase' above shifts the contents of the vector, but
+      // doesn't shift |protection_boundary|. Decrement that here to ensure that
+      // the correct set of cookies is protected.
+      protection_boundary--;

[mmenke, 2016/03/07 17:46:03]

Is this guaranteed to be correct?  Can we just track indices instead, or even
just use the raw pointer to the cookie?

[Mike West, 2016/03/08 08:44:56]

I was pretty sure it was correct until you asked me about it. :) Skimming the
C++11 spec, it looks like I might be relying on undefined behavior (as any
iterator after the point passed to `erase()` ought to be considered
invalidated). :/

I'll rework this to be less clever. Just using indices is probably the right way
to go.

+    } else {
+      current++;
+    }
+  }
+  return removed;
+}
+
 size_t CookieMonster::GarbageCollectExpired(const Time& current,
                                             const CookieMapItPair& itpair,
                                             CookieItVector* cookie_its) {