Evict non-secure cookies less agressively.

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 93 matching lines @@
 
 namespace net {
 
 // See comments at declaration of these variables in cookie_monster.h
 // for details.
 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 =
-    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;
 
 namespace {
 
 bool ContainsControlCharacter(const std::string& s) {
   for (std::string::const_iterator i = s.begin(); i != s.end(); ++i) {
     if ((*i >= 0) && (*i <= 31))
       return true;
   }
@@ skipping 114 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));
+  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,
                                     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
@@ skipping 1648 matching lines @@
                                      bool enforce_strict_secure) {
   lock_.AssertAcquired();
 
   size_t num_deleted = 0;
   Time safe_date(Time::Now() - TimeDelta::FromDays(kSafeFromGlobalPurgeDays));
 
   // Collect garbage for this key, minding cookie priorities.
   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);
+        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;
-    }
+    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};
+      // 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];
 
-      // 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_secure = 0;
+      size_t num_nonsecure = 0;
 
-        size_t num_considered = it_bdd[i + 1] - it_purge_begin;
-        if (num_considered <= accumulated_quota)
-          continue;
+      // 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();
+                                 });
 
-        // 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;
+      // 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];
+      }
 
-        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|.
+      // 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_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;
+            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);
     }
   }
 
   // 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::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) {
   lock_.AssertAcquired();
 
   int num_deleted = 0;
   for (CookieMap::iterator it = itpair.first, end = itpair.second; it != end;) {
     CookieMap::iterator curit = it;
     ++it;
 
@@ skipping 300 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