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 1d3814649ac9781444b8d54e0808a4cce547eef7..79a29bc9912b9d9f68b3884d6ebf20457fd37918 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;
@@ -1875,6 +1848,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.";
@@ -1889,56 +1863,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,
+      // 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);
     }
   }
@@ -1986,6 +1930,38 @@ size_t CookieMonster::GarbageCollect(const Time& current,
   return num_deleted;
 }
 
+size_t CookieMonster::PurgeLeastRecentMatches(CookieItVector* cookies,

[mmenke, 2016/03/04 16:17:57]

Do we still need the CookieItVector, or could we just use cookies_?

[mmenke, 2016/03/04 16:20:19]

If we take enum that indicates the secure value we care about, at least.

[Mike West, 2016/03/04 16:34:23]

We'd need to scope it to the key involved, but we could certainly do that here
rather than in the caller.

[Mike West, 2016/03/07 10:22:28]

Looking at this again, if we use `cookies_` we'll need to do something like
`cookies_.equal_range(key)` here on every pass. I think it's worth the marginal
complexity to pass in the vector that we're working with instead of grabbing it
again on every run.

+                                              CookiePriority priority,
+                                              size_t to_protect,
+                                              size_t purge_goal,
+                                              const base::Time& safe_date) {
+  DCHECK(thread_checker_.CalledOnValidThread());
+
+  size_t matches = std::count_if(cookies->begin(), cookies->end(),
+                                 [priority](const CookieMap::iterator& it) {
+                                   return it->second->Priority() <= priority;
+                                 });
+  if (to_protect > matches)
+    return 0;
+
+  size_t to_remove = std::min(purge_goal, matches - to_protect);
+  size_t removed = 0;
+  for (auto it = cookies->begin();
+       it != cookies->end() && removed < to_remove;) {
+    if ((*it)->second->Priority() <= priority) {
+      InternalDeleteCookie(*it, true,
+                           (*it)->second->LastAccessDate() > safe_date
+                               ? DELETE_COOKIE_EVICTED_DOMAIN_PRE_SAFE
+                               : DELETE_COOKIE_EVICTED_DOMAIN_POST_SAFE);

[Mike West, 2016/03/04 16:34:23]

Is anyone looking at these metrics? If not (and I'm not), do we need them
anymore? Dropping them would simplify the code further, both here and in
`GarbageCollect()`.

[mmenke, 2016/03/04 16:47:44]

You mean the deletion cause?  We pass that on to the delegate...And one of the
delegates is for extensions, and it's now part of the extensions API.  :(

I'm all for deleting the histograms themselves, though, if no one is using them.

https://code.google.com/p/chromium/codesearch#chromium/src/chrome/browser/ext...

[Mike West, 2016/03/07 10:22:28]

I was more specifically referring to the distinction between
"DELETE_COOKIE_EVICTED_DOMAIN_PRE_SAFE" and
"DELETE_COOKIE_EVICTED_DOMAIN_PRE_SAFE" eviction. Both of those map to
CHANGE_COOKIE_EVICTED in observers.

I don't think anyone is looking at that distinction, and since it's been in
place for years, it's unlikely that we're going to do anything the the
additional detail. I think I'll put together a CL to investigate dropping this
distinction in a subsequent CL.

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

Ah, right, didn't realize we're pushing a simpler notion of cause to observers. 
Probably best to ask Randy, since he owns that histogram, but I'm certainly fine
with getting rid of it.

[Mike West, 2016/03/08 08:58:28]

https://codereview.chromium.org/1769023003

+      it = cookies->erase(it);
+      removed++;
+    } else {
+      it++;
+    }
+  }
+  return removed;

[mmenke, 2016/03/04 16:17:57]

I think this entire method can be simpler:

for (auto it = cookies->r_begin(); it = cookies->r_end();) {
  if ((*it)->second->Priority() > priority) {
    ++it;
    continue;
  }
  if (protected < to_protect) {
    protected++;
  } else {
    ...
  }
}

No need for the count_if, or running twice through the vector.

[Mike West, 2016/03/04 16:34:23]

We need to protect the X most-recently used cookies, while deleting the Y
least-recently used cookies. It's not clear to me that we can do that without
walking through the list to see how many cookies we have that match the
predicate. The code you've written would walk through from least-recently-used
to most-recently-used, and protect the X least-recently used from deletion.

If we reversed the vector and protected the X most-recently used, we'd end up
deleting the X+1th most-recently used cookie, rather than the X least-recently
used cookies.

Assume we have 181 low-priority cookies: we want to lock in the most recent 30
cookies, and remove the least-recent 31 cookies. I think we need to walk through
twice if we're working from both ends like that (but I'm totally open to better
ideas!).

[mmenke, 2016/03/04 16:40:51]

Oh, right, I forgot about purge_goal...So we'd need to count down to_protect
cookies with one iterator, and then count up with another other until we reached
purge_goal, or the other iterator.

So no less code complexity, but we could save ourselves having to walk through
|cookies| a second time.

[Mike West, 2016/03/04 16:46:28]

Oh, that's clever. So we'd walk down to the |to_protect|th cookie that matched
the predicate, and then walk up |purge_goal| cookies from the other end?

I think I have a new interview question, because that totally didn't occur to
me. :)

[mmenke, 2016/03/04 16:48:29]

Yes, that's exactly what I mean.

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