Making cookies eviction quotas match spec

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 295 matching lines @@
               const CookieStore::CookieChangedCallback& callback,
               const CanonicalCookie& cookie,
               bool removed) {
   proxy->PostTask(FROM_HERE, base::Bind(callback, cookie, removed));
 }
 
 size_t CountProtectedSecureCookiesAtPriority(
     CookiePriority priority,
     CookieMonster::CookieItVector* cookies) {
   size_t num_protected_secure_cookies = 0;
   for (const auto& cookie : *cookies) {

[jww, 2016/05/23 23:19:03]

Can't this loop be simplified now to just:
if (cookie->second->IsSecure() && cookie_priority == cookie->second->Priority())
  num_protected_secure_cookies++;

And, assuming that's true, the comments below should also be updated
accordingly.

[maksims (do not use this acc), 2016/05/24 06:24:57]

Right. Done.

     if (!cookie->second->IsSecure())
       continue;
     // 1) At low-priority, only low-priority secure cookies are protected as
     //    part of the quota.
     // 2) At medium-priority, only medium-priority secure cookies are protected
     //    as part of the quota (low-priority secure cookies may be deleted).
     // 3) At high-priority, medium-priority and high-priority secure cookies are
     //    protected as part of the quota (low-priority secure cookies may be
     //    deleted).
     CookiePriority cookie_priority = cookie->second->Priority();
     switch (cookie_priority) {
       case COOKIE_PRIORITY_LOW:
-        if (priority == COOKIE_PRIORITY_LOW)
-          num_protected_secure_cookies++;
+        num_protected_secure_cookies++;
         break;
       case COOKIE_PRIORITY_MEDIUM:
+        num_protected_secure_cookies++;
+        break;
       case COOKIE_PRIORITY_HIGH:
-        if (cookie_priority <= priority)
-          num_protected_secure_cookies++;
+        num_protected_secure_cookies++;
         break;
     }
   }
 
   return num_protected_secure_cookies;
 }
 
 bool IsCookieEligibleForEviction(CookiePriority current_priority_level,
                                  bool protect_secure_cookies,
                                  const CanonicalCookie* cookie) {
-  if (!cookie->IsSecure() || !protect_secure_cookies)
-    return cookie->Priority() <= current_priority_level;
+  if (cookie->Priority() == current_priority_level && cookie->IsSecure() &&

[jww, 2016/05/23 23:19:03]

These two conditionals can be simplified to:

if (cookie->Priority() == current_priority_level && protect_secure_cookies)
  return !cookie->IsSecure();

[maksims (do not use this acc), 2016/05/24 06:24:57]

Done.

+      protect_secure_cookies)
+    return false;
+  if (cookie->Priority() == current_priority_level && !cookie->IsSecure() &&
+      protect_secure_cookies)
+    return true;
 
-  // Special consideration has to be given for low-priority secure cookies since
-  // they are given lower prority than non-secure medium-priority and non-secure
-  // high-priority cookies. Thus, low-priority secure cookies may be evicted at
-  // a medium and high value of |current_priority_level|. Put another way,
-  // low-priority secure cookies are only protected when the current priority
-  // level is low.
-  if (current_priority_level == COOKIE_PRIORITY_LOW)
-    return false;
+  return cookie->Priority() == current_priority_level;
+}
 
-  return cookie->Priority() == COOKIE_PRIORITY_LOW;
+size_t CountCookiesAtPriority(CookiePriority priority,
+                              CookieMonster::CookieItVector* cookies) {
+  size_t num_of_priority_cookies = 0;
+  size_t current = 0;
+  while (current < cookies->size()) {
+    if (cookies->at(current)->second->Priority() == priority)
+      num_of_priority_cookies++;
+    current++;
+  }
+  return num_of_priority_cookies;
 }
 
 }  // namespace
 
 CookieMonster::CookieMonster(PersistentCookieStore* store,
                              CookieMonsterDelegate* delegate)
     : CookieMonster(store, delegate, kDefaultAccessUpdateThresholdSeconds) {
 }
 
 CookieMonster::CookieMonster(PersistentCookieStore* store,
@@ skipping 1551 matching lines @@
 
     if (cookie_its->size() > kDomainMaxCookies) {
       VLOG(kVlogGarbageCollection) << "Deep Garbage Collect domain.";
       size_t purge_goal =
           cookie_its->size() - (kDomainMaxCookies - kDomainPurgeCookies);
       DCHECK(purge_goal > kDomainPurgeCookies);
 
       // Sort the cookies by access date, from least-recent to most-recent.
       std::sort(cookie_its->begin(), cookie_its->end(), LRACookieSorter);
 
-      size_t additional_quota_low = kDomainCookiesQuotaLow;
-      size_t additional_quota_medium = kDomainCookiesQuotaMedium;
-      size_t additional_quota_high = kDomainCookiesQuotaHigh;
-
       // Remove all but the kDomainCookiesQuotaLow most-recently accessed
       // cookies with low-priority. Then, if cookies still need to be removed,
       // bump the quota and remove low- and medium-priority. Then, if cookies
       // _still_ need to be removed, bump the quota and remove cookies with
       // any priority.
       //
       // 1.  Low-priority non-secure cookies.
       // 2.  Low-priority secure cookies.
       // 3.  Medium-priority non-secure cookies.
       // 4.  High-priority non-secure cookies.
@@ skipping 21 matching lines @@
       for (const auto& purge_round : purge_rounds) {
         // Only observe the non-secure purge rounds if strict secure cookies is
         // enabled.
         if (!enforce_strict_secure && purge_round.protect_secure_cookies)
           continue;
 
         // Only adjust the quota if the round is executing, otherwise it is
         // necesary to delay quota adjustments until a later round. This is
         // because if the high priority, non-secure round is skipped, its quota
         // should not count until the later high priority, full round later.
-        size_t* additional_quota = nullptr;
         switch (purge_round.priority) {
           case COOKIE_PRIORITY_LOW:
-            additional_quota = &additional_quota_low;
+            quota = kDomainCookiesQuotaLow;

[jww, 2016/05/23 23:19:03]

This is the change that I'm most confused about. Doesn't this mean that, for
example, in the second round where we're looking at low-priority, secure
cookies, the quota gets reset, so we potentially delete an entire new
quota-number of cookies? Or am I misunderstanding something?

For example, if I have 40 low-priority, non-secure cookies and 40 low-priority,
secure cookies, and 300 high-priority, secure cookies, wouldn't the rounds go:
1. Delete 10 low-priority, non-secure cookies
2. Delete 20 low-priority, secure cookies
3. Do nothing
4. Do nothing
5. Do nothing
6. Delete 130 high priority, secure cookies (or whatever it is to get down to
the final purge goal)

Hmm, looking below, I think I *may* have misunderstood how this works because I
*think* what you're going for is that you'll count the secure cookies as
"protected" already in Purge...(). Can you clarify?

At the very least, I think this comment needs updating.

[maksims (do not use this acc), 2016/05/24 06:24:57]

Not exactly. First, we take a quota at |priority| that we mustn't delete (30 for
low priority cookies, for example).
Then we count secure and non-secure cookies at |priority|.
If the total number of cookies at |priority| is lower than the quota, we skip
the round, which guarantees we will not go below than the quota and there will
be no starvation for cookies at the |priority|.
It is the line 2063, which does the trick:
if (cookies_count_possibly_to_be_deleted <= to_protect)
return 0u;

Then, if we should protect low-priority secure cookies, we count and subtract
them from the overall number of cookies that cannot be lower than 31 because we
have already checked the number of cookies at line 2063. Afterwards, we delete
the non-secure cookies till purge goal is hit or number of those cookies is 0.

Next round does the same and deletes low-priority secure cookies if removing
low-priority non-secure cookies has not been enough to hit the quota (30 for
low-priority cookies).
1. Delete 40 low-priority, non-secure cookies, 0 left
2. Delete 10 low-priority, secure cookies, 30 left
----> preserve quota of 30 low-priority cookies.
3. Do nothing
4. Do nothing
5. Do nothing
if total number of cookies shouldn't be less than 180, then
6. Delete 150 high priority secure cookies, which preserves 70 high-priority
cookies according to a quota of 70 high priority cookies.

As a result there are 30 low priority secure cookies and 150 high priority
secure cookies. 

[jww, 2016/05/26 03:46:39]

Ok, I've got it. As mentioned before, can you update the comment about the
comment here? I believe it's no longer accurate. At the very least, your
explanation you just gave was very helpful, and it would be useful to have a
shorter version of it somewhere in the comments :-)

             break;
           case COOKIE_PRIORITY_MEDIUM:
-            additional_quota = &additional_quota_medium;
+            quota = kDomainCookiesQuotaMedium;
             break;
           case COOKIE_PRIORITY_HIGH:
-            additional_quota = &additional_quota_high;
+            quota = kDomainCookiesQuotaHigh;
             break;
         }
-        quota += *additional_quota;
-        *additional_quota = 0u;
         size_t just_deleted = 0u;
-
         // Purge up to |purge_goal| for all cookies at the given priority. This
         // path will always execute if strict secure cookies is disabled since
         // |purge_goal| must be positive because of the for-loop guard. If
         // strict secure cookies is enabled, this path will be taken only if the
         // initial non-secure purge did not evict enough cookies.
         if (purge_goal > 0) {
           just_deleted = PurgeLeastRecentMatches(
               cookie_its, purge_round.priority, quota, purge_goal,
               purge_round.protect_secure_cookies);
           DCHECK_LE(just_deleted, purge_goal);
@@ skipping 48 matching lines @@
 
   return num_deleted;
 }
 
 size_t CookieMonster::PurgeLeastRecentMatches(CookieItVector* cookies,
                                               CookiePriority priority,
                                               size_t to_protect,
                                               size_t purge_goal,
                                               bool protect_secure_cookies) {
   DCHECK(thread_checker_.CalledOnValidThread());
+  // 1. Count number of the cookies at |priority|
+  size_t cookies_count_possibly_to_be_deleted =

[jww, 2016/05/23 23:19:03]

While this logic is generally sound, it might be good to simplify the
CountCookiesAtPriority() and CountProtectedSecureCookiesAtPriority() functions
into a single CountCookiesForPossibleDeletion() that takes
protect_secure_cookies as an argument.

[maksims (do not use this acc), 2016/05/24 06:24:57]

Hmm, ok!

+      CountCookiesAtPriority(priority, cookies);
+  // 2. If |cookies_count| at |priority| is less than or equal to_protect, skip.
+  // This involves secure and non-secure cookies at |priority|.
+  if (cookies_count_possibly_to_be_deleted <= to_protect)
+    return 0u;
 
-  // 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.
-  //
-  // If |protect_secure_cookies| is true, do a first pass that counts eligible
-  // secure cookies at the specified priority as protected.
+  // 3. Calculate number of secure cookies at |priority|
+  // and Count number of cookies at |priority| that can possibly be deleted.
+  // It is guaranteed we do not delete more than |purge_goal| even if
+  // |priority_cookies_might_be_deleted| is higher.

[jww, 2016/05/26 03:46:39]

This variable name changed, correct?

+  size_t secure_cookies = 0u;
   if (protect_secure_cookies) {
-    to_protect -= std::min(
-        to_protect, CountProtectedSecureCookiesAtPriority(priority, cookies));
+    secure_cookies = CountProtectedSecureCookiesAtPriority(priority, cookies);
+    cookies_count_possibly_to_be_deleted -= secure_cookies;

[jww, 2016/05/23 23:19:03]

What if secure_cookies < to_protect? Don't you still need to reduce
cookies_count_possibly_to_be_deleted to by to_protect - secure_cookies?

[maksims (do not use this acc), 2016/05/24 06:24:57]

It doesn't matter. |secure_cookies| are subtracted from the total number of
cookies in order to avoid removing them on the low priority non-secure cookies
round. For example, there are 90 low priority cookies: 55 low non-secure and 35
secure cookies. Line 2063 guarantees we will not go below than the quota, which
is 30 low priority cookies. 

cookies_count_possibly_to_be_deleted = 90
check cookies_count_possibly_to_be_deleted <= to_protect or quota
protect_secure_cookies is true,
then secure_cookies = CountProtectedSecureCookiesAtPriority(priority, cookies) =
35.
cookies_count_possibly_to_be_deleted = 90 - 35 = 55 low non-secure cookies.

The "while loop" deletes 55 low non-secure cookies.
Next round: 
cookies_count_possibly_to_be_deleted = 35.
check cookies_count_possibly_to_be_deleted <= to_protect or quota (35 <= 30)
then cookies_count_possibly_to_be_deleted = 35 - 30 = 5 low priority secure
cookies to be deleted.

[jww, 2016/05/26 03:46:39]

What if there are 90 low priority, non-secure cookies and 0 secure cookies? In
that case, in the first round:
cookies_count_possibly_to_be_deleted = 90
secure_cookies = CountProtectedSecureCookiesAtPriority(...), which is 0
cookies_count_possibly_to_be_deleted = 90 - 0

which sets up the round to delete 90 cookies, which is all of them, thus not
maintaining the quota. So I believe line 2073 should be:
cookies_count_possibly_to_be_deleted -= std::max(secure_cookies, to_protect -
secure_cookies)

Am I still misunderstanding?

+  } else {
+    cookies_count_possibly_to_be_deleted -= to_protect;
   }
 
-  size_t protection_boundary = cookies->size();
-  while (to_protect > 0 && protection_boundary > 0) {
-    protection_boundary--;
-    if (cookies->at(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;
-  size_t current = 0;
-  while (removed < purge_goal && current < protection_boundary) {
+  size_t removed = 0u;
+  size_t current = 0u;
+  while (removed < purge_goal && current < cookies->size()) {
     const CanonicalCookie* current_cookie = cookies->at(current)->second;
-    // Only delete the current cookie if the priority is less than or equal to
-    // the current level. If it is equal to the current level, and secure
-    // cookies are protected, only delete it if it is not secure.
+    // Only delete the current cookie if the priority is equal to
+    // the current level.
     if (IsCookieEligibleForEviction(priority, protect_secure_cookies,
-                                    current_cookie)) {
+                                    current_cookie) &&
+        cookies_count_possibly_to_be_deleted > 0) {
       InternalDeleteCookie(cookies->at(current), true,
                            DELETE_COOKIE_EVICTED_DOMAIN);
       cookies->erase(cookies->begin() + current);
       removed++;
-
+      cookies_count_possibly_to_be_deleted--;
       // 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--;
+      // the correct set of cookies is protected.;
     } else {
       current++;
     }
   }
   return removed;
 }
 
 size_t CookieMonster::GarbageCollectExpired(const Time& current,
                                             const CookieMapItPair& itpair,
                                             CookieItVector* cookie_its) {
@@ skipping 317 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