Evict non-secure cookies less agressively.

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 9c507eabe9607b7a0a9afde97c828ee7c4d40b04..f6c86f08cdb0d920eead3f2968e5765bf6fa93a6 100644
--- a/net/cookies/cookie_monster.cc
+++ b/net/cookies/cookie_monster.cc
@@ -111,11 +111,10 @@ 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 =
-    kDomainMaxCookies - kDomainPurgeCookies - kDomainCookiesQuotaLow -
-    kDomainCookiesQuotaMedium;
+const float CookieMonster::kDomainCookiesQuotaLow = 0.2;
+const float CookieMonster::kDomainCookiesQuotaMedium = 0.3333333333333333333333;
+const float CookieMonster::kDomainCookiesQuotaHigh =
+    1 - kDomainCookiesQuotaLow - kDomainCookiesQuotaMedium;
 
 const int CookieMonster::kSafeFromGlobalPurgeDays = 30;
 
@@ -250,19 +249,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
@@ -271,7 +257,11 @@ 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));
+  return std::partition(
+      it_begin, it_end,
+      [priority](const CookieMonster::CookieMap::iterator& it) {
+        return it->second->Priority() == priority;
+      });
 }
 
 bool LowerBoundAccessDateComparator(const CookieMonster::CookieMap::iterator it,
@@ -1940,77 +1930,115 @@ size_t CookieMonster::GarbageCollect(const Time& current,
   if (cookies_.count(key) > kDomainMaxCookies) {
     VLOG(kVlogGarbageCollection) << "GarbageCollect() key: " << key;
 
-    CookieItVector* cookie_its;
+    CookieItVector cookie_its;
 
-    CookieItVector non_expired_cookie_its;
-    cookie_its = &non_expired_cookie_its;
+    // First, we purge all expired cookies for this key (regardless of our
+    // target number of cookies, as we have no need to keep expired cookies
+    // around).
     num_deleted +=
-        GarbageCollectExpired(current, cookies_.equal_range(key), cookie_its);
-
-    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;
-    }
+        GarbageCollectExpired(current, cookies_.equal_range(key), &cookie_its);
+
+    if (cookie_its.size() > kDomainMaxCookies) {
+      // Then, if we're over the maximum allowed for this key, we'll remove
+      // cookies in the following order:
+      //
+      // 1.  Low-priority non-secure cookies.
+      // 2.  Medium-priority non-secure cookies.
+      // 3.  High-priority non-secure cookies.
+      // 4.  Low-priority secure cookies.
+      // 5.  Medium-priority secure cookies.
+      // 6.  High-priority secure cookies.
+      //
+      // Note that this implies that _all_ non-secure cookies will be removed
+      // before _any_ secure cookie is removed, in accordance with
+      // https://tools.ietf.org/html/draft-west-leave-secure-cookies-alone-05

[jww, 2016/02/18 01:05:19]

Should this link really have the '-05' at the end?

 
-    if (cookie_its->size() > kDomainMaxCookies) {
       VLOG(kVlogGarbageCollection) << "Deep Garbage Collect domain.";
       size_t purge_goal =
-          cookie_its->size() - (kDomainMaxCookies - kDomainPurgeCookies);
+          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|.
+      // To execute the above removals, we'll divide |cookies_its| into 6
+      // partitions, using 7 boundaries (note that the last boundary is off the
+      // end of the list):
+      //
+      // If both non-secure and secure cookies are present, the list will look
+      // like this:
+      //
+      // LLLLMMMMHHHHHLLLLMMMMHHHH
+      // ^   ^   ^    ^   ^   ^   ^
+      // 0   1   2    3   4   5   6
+      //
+      // If only secure cookies are present, the list will look like this:
+      //
+      // LLLLMMMMHHHHH
+      // ^   ^   ^    ^
+      // 0   4   5    6
+      // 1
+      // 2
+      // 3
+      //
+      // If only non-secure cookies are present, the list will look like this:
+      //
+      // LLLLMMMMHHHHH
+      // ^   ^   ^    ^
+      // 0   1   2    3
+      //              4
+      //              5
+      //              6
+      CookieItVector::iterator it_bdd[7];
+      it_bdd[0] = cookie_its.begin();
+      it_bdd[1] = it_bdd[0];
+      it_bdd[2] = it_bdd[0];
+      it_bdd[3] = cookie_its.end();
+      it_bdd[4] = it_bdd[3];
+      it_bdd[5] = it_bdd[3];
+      it_bdd[6] = it_bdd[3];
+
+      size_t num_secure = 0;
+      size_t num_nonsecure = 0;
+
+      // Move all non-secure cookies to the front of the list, and set boundary
+      // #3 to the first secure cookie (or off the end of the list, in the case
+      // where no secure cookies are present).
+      it_bdd[3] = std::partition(it_bdd[0], it_bdd[6],
+                                 [](const CookieMap::iterator& it) {
+                                   return !it->second->IsSecure();
+                                 });
+
+      // If we have non-secure cookies, partition them into priorities:
+      if (it_bdd[3] > it_bdd[0]) {
+        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);

[mmenke, 2016/02/17 18:41:31]

This seems so much more complicated than necessary.

Why can't we just sort them in the order we want to delete them in, once (First
by secure, then by priority), and then just delete the first how many ever
cookies we want to purge?  Is the issue safe_date?

+        num_nonsecure = it_bdd[3] - it_bdd[0];
+      }
+
+      // Likewise, if we have secure cookies, partition them into priorities:
+      if (it_bdd[3] < it_bdd[6]) {
+        it_bdd[4] = PartitionCookieByPriority(it_bdd[3], it_bdd[6],
+                                              COOKIE_PRIORITY_LOW);
+        it_bdd[5] = PartitionCookieByPriority(it_bdd[4], it_bdd[6],
+                                              COOKIE_PRIORITY_MEDIUM);
+        num_secure = it_bdd[6] - it_bdd[3];
+      }
+
+      // Start with the non-secure cookies.
+      if (purge_goal >= num_nonsecure) {
+        // If we need to purge more cookies than we have non-secure, remove
+        // them all, update |purge_goal| then purge the new |purge_goal| from
+        // the secure cookies.
         num_deleted += GarbageCollectDeleteRange(
-            current, DELETE_COOKIE_EVICTED_DOMAIN_POST_SAFE, it_purge_middle,
-            it_purge_end);
-        it_purge_begin = it_purge_end;
+            current, DELETE_COOKIE_NON_SECURE, it_bdd[0], it_bdd[3]);
+        num_deleted += GarbageCollectNumFromRangeWithQuota(
+            current, safe_date, purge_goal - num_deleted, it_bdd, GC_SECURE);
+      } else {
+        num_deleted += GarbageCollectNumFromRangeWithQuota(
+            current, safe_date, purge_goal, it_bdd, GC_NONSECURE);
       }
+      purge_goal -= num_deleted;
+
       DCHECK_EQ(0U, purge_goal);
     }
   }
@@ -2058,6 +2086,70 @@ size_t CookieMonster::GarbageCollect(const Time& current,
   return num_deleted;
 }
 
+size_t CookieMonster::GarbageCollectNumFromRangeWithQuota(
+    const Time& current,
+    const Time& safe_date,
+    size_t purge_goal,
+    CookieItVector::iterator* it_bdd,
+    GCType type) {
+  size_t num_deleted = 0;
+  size_t begin_partition = type == GC_SECURE ? 3 : 0;
+  size_t num_cookies = it_bdd[begin_partition + 3] - it_bdd[begin_partition];
+  size_t num_to_keep = num_cookies - purge_goal;
+  size_t quota[3] = {std::floor(num_to_keep * kDomainCookiesQuotaLow),
+                     std::floor(num_to_keep * kDomainCookiesQuotaMedium),
+                     std::floor(num_to_keep * kDomainCookiesQuotaHigh)};
+
+  // The quota calculation will be up to 3 fewer than the number of
+  // cookies we can keep. Bump up the numbers to get the right answer:
+  if (quota[0] + quota[1] + quota[2] < num_to_keep)
+    quota[2] += 1;
+  if (quota[0] + quota[1] + quota[2] < num_to_keep)
+    quota[1] += 1;
+  if (quota[0] + quota[1] + quota[2] < num_to_keep)
+    quota[0] += 1;
+  DCHECK_EQ(num_to_keep, quota[0] + quota[1] + quota[2]);
+
+  // 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[begin_partition];
+  for (int i = 0; i < 3 && purge_goal > 0; ++i) {

[jww, 2016/02/18 01:05:19]

'i < 3' -> 'i < ARRAY_SIZE(quota)' in case the length changes in the future
(doubtful as that might be).

+    accumulated_quota += quota[i];
+
+    size_t num_considered = it_bdd[i + begin_partition + 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 + begin_partition + 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;
+  }
+  return num_deleted;
+}
+
 size_t CookieMonster::GarbageCollectExpired(const Time& current,
                                             const CookieMapItPair& itpair,
                                             CookieItVector* cookie_its) {