Clean up cookie eviction.

net/cookies/cookie_monster.cc

 // Copyright (c) 2012 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.
 
 // Portions of this code based on Mozilla:
 //   (netwerk/cookie/src/nsCookieService.cpp)
 /* ***** BEGIN LICENSE BLOCK *****
  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
  *
  * The contents of this file are subject to the Mozilla Public License Version
@@ skipping 144 matching lines @@
 // sorts by creation time (oldest first).
 // The RFC says the sort order for the domain attribute is undefined.
 bool CookieSorter(CanonicalCookie* cc1, CanonicalCookie* cc2) {
   if (cc1->Path().length() == cc2->Path().length())
     return cc1->CreationDate() < cc2->CreationDate();
   return cc1->Path().length() > cc2->Path().length();
 }
 
 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();
 }
 
 // Compare cookies using name, domain and path, so that "equivalent" cookies
 // (per RFC 2965) are equal to each other.
 bool PartialDiffCookieSorter(const CanonicalCookie& a,
                              const CanonicalCookie& b) {
   return a.PartialCompare(b);
 }
 
@@ skipping 61 matching lines @@
     CookieMonster::CookieItVector* non_secure_cookie_its) {
   DCHECK(secure_cookie_its && non_secure_cookie_its);
   for (const auto& curit : cookie_its) {
     if (curit->second->IsSecure())
       secure_cookie_its->push_back(curit);
     else
       non_secure_cookie_its->push_back(curit);
   }
 }
 
-// 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;
 }
 
 // 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(
@@ skipping 1581 matching lines @@
   if (cookies_.count(key) > kDomainMaxCookies) {
     VLOG(kVlogGarbageCollection) << "GarbageCollect() key: " << key;
 
     CookieItVector* cookie_its;
 
     CookieItVector non_expired_cookie_its;
     cookie_its = &non_expired_cookie_its;
     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.";
       num_deleted +=
           GarbageCollectNonSecure(non_expired_cookie_its, &secure_cookie_its);
       cookie_its = &secure_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};
+      // Sort the cookies by access date, from least-recent to most-recent.
+      std::sort(cookie_its->begin(), cookie_its->end(), LRACookieSorter);
 
-      // 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];
+      // 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;
+      }
 
-        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 accessed in kSafeFromGlobalPurgeDays, otherwise evict.
   if (cookies_.size() > kMaxCookies && earliest_access_time_ < safe_date) {
     VLOG(kVlogGarbageCollection) << "GarbageCollect() everything";
     CookieItVector cookie_its;
 
@@ skipping 27 matching lines @@
       } else {
         num_deleted += GarbageCollectLeastRecentlyAccessed(
             current, safe_date, purge_goal, cookie_its);
       }
     }
   }
 
   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) {
   DCHECK(thread_checker_.CalledOnValidThread());
 
   int num_deleted = 0;
   for (CookieMap::iterator it = itpair.first, end = itpair.second; it != end;) {
     CookieMap::iterator curit = it;
     ++it;
 
@@ skipping 319 matching lines @@
        it != hook_map_.end(); ++it) {
     std::pair<GURL, std::string> key = it->first;
     if (cookie.IncludeForRequestURL(key.first, opts) &&
         cookie.Name() == key.second) {
       it->second->Notify(cookie, removed);
     }
   }
 }
 
 }  // namespace net