Implementing EvictedDomainCookieCounter to keep user metrics on cookie eviction and reinstatement.

net/cookies/evicted_domain_cookie_counter.cc

+// Copyright 2013 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.
+
+#include "net/cookies/evicted_domain_cookie_counter.h"
+
+#include <queue>
+#include <vector>
+
+#include "base/metrics/histogram.h"
+#include "base/stl_util.h"
+#include "base/string_util.h"
+#include "net/base/registry_controlled_domains/registry_controlled_domain.h"
+#include "net/cookies/canonical_cookie.h"
+
+namespace net {
+
+using base::Time;
+using base::TimeDelta;
+
+namespace {
+
+const size_t kMaxEvictedDomainCookies = 500;
+const size_t kPurgeEvictedDomainCookies = 100;
+
+class DelegateImpl : public EvictedDomainCookieCounter::Delegate {
+ public:
+  DelegateImpl();
+
+  // EvictedDomainCookieCounter::Delegate implementation.
+  virtual void Report(const EvictedDomainCookieCounter::EvictedCookie& ec,
+                      const Time& reinstatement_time) OVERRIDE;
+  virtual Time CurrentTime() OVERRIDE;
+};
+
+DelegateImpl::DelegateImpl() {}
+
+void DelegateImpl::Report(const EvictedDomainCookieCounter::EvictedCookie& ec,
+                          const Time& reinstatement_time) {
+  TimeDelta reinstatement_delay(reinstatement_time - ec.eviction_time_);
+  // Need to duplicate HISTOGRAM_CUSTOM_TIMES(), since it is a macro that
+  // defines a static variable.
+  if (ec.is_google_) {
+    HISTOGRAM_CUSTOM_TIMES("Cookie.ReinstatedCookiesGoogle",
+                           reinstatement_delay,
+                           TimeDelta::FromSeconds(1),
+                           TimeDelta::FromDays(7),
+                           50);
+  } else {
+    HISTOGRAM_CUSTOM_TIMES("Cookie.ReinstatedCookiesOther",
+                           reinstatement_delay,
+                           TimeDelta::FromSeconds(1),
+                           TimeDelta::FromDays(7),
+                           50);
+  }
+}
+
+Time DelegateImpl::CurrentTime() {
+  return Time::Now();
+}
+
+}  // namespace
+
+EvictedDomainCookieCounter::EvictedDomainCookieCounter(
+    scoped_refptr<CookieMonster::Delegate> next_cookie_monster_delegate)
+    : next_cookie_monster_delegate_(next_cookie_monster_delegate),
+      delegate_(new DelegateImpl),
+      max_size_(kMaxEvictedDomainCookies),
+      purge_count_(kPurgeEvictedDomainCookies) {
+}
+
+EvictedDomainCookieCounter::EvictedDomainCookieCounter(
+    scoped_refptr<CookieMonster::Delegate> next_cookie_monster_delegate,
+    scoped_ptr<Delegate> delegate,
+    size_t max_size,
+    size_t purge_count)
+    : next_cookie_monster_delegate_(next_cookie_monster_delegate),
+      delegate_(delegate.Pass()),
+      max_size_(max_size),
+      purge_count_(purge_count) {
+  DCHECK(delegate_);
+  DCHECK(purge_count < max_size_);
+}
+
+EvictedDomainCookieCounter::~EvictedDomainCookieCounter() {
+  STLDeleteContainerPairSecondPointers(evicted_cookies_.begin(),
+                                       evicted_cookies_.end());
+}
+
+// static
+// Simplified from google_util.cc: IsGoogleHostname().
+bool EvictedDomainCookieCounter::UnsafeIsGoogleCookie(
+    const CanonicalCookie& cc) {
+  const std::string& host(cc.Domain());
+  size_t tld_length =
+      RegistryControlledDomainService::GetRegistryLength(host, false);
+  if ((tld_length == 0) || (tld_length == std::string::npos))
+    return false;
+
+  std::string host_minus_tld(host, 0, host.length() - tld_length);
+  return LowerCaseEqualsASCII(host_minus_tld, "google.") ||
+      EndsWith(host_minus_tld, ".google.", false);
+}
+
+size_t EvictedDomainCookieCounter::GetStorageSize() const {
+  return evicted_cookies_.size();
+}
+
+void EvictedDomainCookieCounter::OnCookieChanged(const CanonicalCookie& cc,
+                                                 bool removed,
+                                                 ChangeCause cause) {
+  EvictedDomainCookieCounter::EvictedCookieKey key(GetKey(cc));
+  Time current(delegate_->CurrentTime());
+  if (removed) {
+    if (cause == CookieMonster::Delegate::CHANGE_COOKIE_EVICTED)
+      StoreEvictedCookie(key, cc, current);
+    else  // Explicit deletion, so stop tracking.
+      FreeEvictedCookie(key);

[erikwright (departed), 2013/03/26 16:38:13]

On the surface, it would seem like this should never happen.

After all, if it is in your map, it was previously evicted. Ergo, you should not
expect to receive any subsequent notifications about it being removed unless
there was an intervening reinstatement.

[huangs, 2013/03/27 00:40:26]

Removed. I was being paranoid by assuming some semi-arbitrary input stream. :)

+  } else {  // Includes adds or updates.
+    ProcessNewCookie(key, cc, current);
+  }
+
+  if (next_cookie_monster_delegate_)
+    next_cookie_monster_delegate_->OnCookieChanged(cc, removed, cause);
+}
+
+// static
+EvictedDomainCookieCounter::EvictedCookieKey
+    EvictedDomainCookieCounter::GetKey(const CanonicalCookie& cc) {
+  return cc.Domain() + ";" + cc.Path() + ";" + cc.Name();
+}
+
+void EvictedDomainCookieCounter::FreeEvictedCookie(
+    const EvictedCookieKey& key) {
+  EvictedCookieMap::iterator it = evicted_cookies_.find(key);
+  if (it != evicted_cookies_.end()) {
+    delete it->second;
+    evicted_cookies_.erase(it);
+  }
+}
+
+// |current| is passed by value, in case it came from a to-be-deleted element.

[erikwright (departed), 2013/03/26 16:38:13]

Since this is a private method and you know it doesn't happen, there is no
reason to pass by value here. In a class of this size, it is reasonable for the
caller to know that this method potentially deletes EvictedCookie records. For
example, they need to know that this method might invalidate iterators too.

[huangs, 2013/03/27 00:40:26]

Makes sense.  Changed to const base::Time.  Also, change name to |time_bound| to
per .h file.

+void EvictedDomainCookieCounter::FreeExpiredEvictedCookies(Time current) {
+  EvictedCookieMap::iterator it = evicted_cookies_.begin();
+  while (it != evicted_cookies_.end()) {
+    if (it->second->is_expired(current)) {
+      delete it->second;
+      evicted_cookies_.erase(it++);  // Post-increment idiom.
+    } else {
+      ++it;
+    }
+  }
+}
+
+void EvictedDomainCookieCounter::GarbageCollect(const Time& current) {
+  if (evicted_cookies_.size() <= max_size_)
+    return;
+
+  // From |evicted_cookies_|, removed all expired cookies, and remove cookies
+  // with the oldest |eviction_time_| until |size_goal| is attained.
+  size_t size_goal = max_size_ - purge_count_;
+  // Bound on number of non-expired cookies to remove.
+  size_t remove_quota = evicted_cookies_.size() - size_goal;
+  DCHECK(remove_quota > 0);
+
+  typedef EvictedDomainCookieCounter::EvictedCookie* EvictedCookiePtr;
+  // Comparator for a priority_queue<> whose top() element specifies the most
+  // recently evicted cookie.
+  struct EvictedCookieComparator {
+    bool operator() (EvictedCookiePtr ec1, EvictedCookiePtr ec2) {
+      return ec1->eviction_time_ < ec2->eviction_time_;
+    }
+  };
+
+  // Use priority queue to store oldest cookies, resize as necessary.
+  std::priority_queue<EvictedCookiePtr, std::vector<EvictedCookiePtr>,
+                      EvictedCookieComparator> oldest_set;
+  for (EvictedCookieMap::iterator it = evicted_cookies_.begin();
+      it != evicted_cookies_.end(); ++it) {
+    if (it->second->is_expired(current))  // Will be removed, so decrease quota.
+      remove_quota = remove_quota ? remove_quota - 1 : 0;  // Cap to 0 (size_t).
+    else
+      oldest_set.push(it->second);
+
+    if (oldest_set.size() > remove_quota)
+      oldest_set.pop();  // Spare the youngest element from deletion.

[erikwright (departed), 2013/03/26 16:38:13]

Alternatively, I suppose you could reverse the comparator (make top() return the
least recently evicted cookie) and then just loop through |remove_quota|
elements in the loop at line 191.

That would remove some number of logn operations at line 186 while increasing N
for the logn operations on line 191. My instincts tell me that it would be a net
win?

[huangs, 2013/03/27 00:40:26]

The old method saves more memory, but it turns out the factor of 2 is
significant...  Analysis:

Assume: No expired cookies; 1 + ... + log(n) = n log(n)

Let N = total # of elts, M = max # to remove.

Old algorithm (before full + after full + tag all):
  M lg(M) + (N-M) 2 lg(M) + M lg(M) = 2 N lg(M)

New algorithm (add all, tag top M):
  N lg(N) + M lg(N) = (M+N) lg(N)

Verdict: It depends.  For very small M, old is better.
For M = 100, N = 500, assuming negligible factors, new is better.

[huangs, 2013/03/27 00:40:26]

Simulation:
import math
def lg(n):
  return math.log(n)/math.log(2)
def lgsum(a,b):
  return sum([lg(i) for i in range(a,b+1)])
def f1(n,m):
  return lgsum(1,m) + 2*(n-m)*lg(m) + lgsum(1,m)
def f2(n,m):
  return lgsum(1,n) + lgsum(n-m+1,n)
def test(n,m):
  print "(n = %d, m = %d): old = %f vs. new = %f" % (n, m, f1(n,m), f2(n,m))
test(500,10)
test(500,100)

Output:
(n = 500, m = 10): old = 3299.071655 vs. new = 3856.880673
(n = 500, m = 100): old = 6364.614938 vs. new = 4648.594569

[huangs, 2013/03/27 00:40:26]

Instead of using priority_queue<>, may as well use partial_sort<>.  Not sure if
it will be more efficient -- but at least code looks simpler!

+  }
+  DCHECK(oldest_set.size() <= remove_quota);
+
+  // Mark oldest non-expired cookies as expired, for removal.
+  for (; !oldest_set.empty(); oldest_set.pop())
+    oldest_set.top()->set_expired();

[erikwright (departed), 2013/03/26 16:38:13]

Here (combined with FreeExpiredEvictedCookies) we are removing 100 out of 500
cookies by iterating through the 500 cookies.

Iteration is O(N), removal of an item using iterator is amortized O(1).

If you were to remove them in the loop through oldest_set, it would be 100
removals by key, which is O(logN). While we can't be sure without a benchmark, I
assume that the base cost of a lookup is comparable to the cost of doing
set_expired(), checking the expiry, and incrementing the iterator.

Also, taking the delete-by-key approach will remove a bunch of code :)

------------------------------

Furthermore, couldn't you store EvictedCookieMap::iterators in the
priority_queue? Then you could do erase-by-iterator which is O(1). Obviously
this requires adjusting your comparator slightly to dereference the iterator.

-------------------------------

So delete on line 192 instead of doing set_expired and
FreeExpiredEvictedCookies.

That will also require you to delete expired cookies during the garbage
collection loop, but that should be OK.

[huangs, 2013/03/27 00:40:26]

Cool. Doing this, except I'm now using vector<T>!

+
+  FreeExpiredEvictedCookies(current);
+  // Apply stricter check if non-expired cookies were deleted.
+  DCHECK(remove_quota ? evicted_cookies_.size() == size_goal :
+         evicted_cookies_.size() <= size_goal);
+}
+
+void EvictedDomainCookieCounter::StoreEvictedCookie(const EvictedCookieKey& key,
+                                                    const CanonicalCookie& cc,
+                                                    const Time& current) {
+  if (!cc.IsExpired(current)) {

[erikwright (departed), 2013/03/26 16:38:13]

This should also only happen if the cause is CHANGE_COOKIE_EXPIRED, which never
lands here.

So the same comments apply as for ProcessNewCookie.

[huangs, 2013/03/27 00:40:26]

Removed.

+    FreeEvictedCookie(key);  // Deallocate explicitly.

[erikwright (departed), 2013/03/26 16:38:13]

std::map::insert returns a pair of iterator/bool. If there was already an
equivalent element in the map the bool is false and the iterator points to it.

So instead of FreeEvictedCookie here, just check the return value and, if it is
not successful, you can use the returned iterator to delete the previous entry
and replace it with the new one. I would put a NOTREACHED in that block as well.

In combination with a previous comment, FreeEvictedCookie can now be deleted.

[huangs, 2013/03/27 00:40:26]

Ah, neat. :) Done.

+
+    EvictedCookie* ec =
+        new EvictedCookie(current, cc.ExpiryDate(), UnsafeIsGoogleCookie(cc));
+    evicted_cookies_.insert(EvictedCookieMap::value_type(key, ec));
+
+    GarbageCollect(current);
+  }
+}
+
+void EvictedDomainCookieCounter::ProcessNewCookie(const EvictedCookieKey& key,
+                                                  const CanonicalCookie& cc,
+                                                  const Time& current) {
+  EvictedCookieMap::iterator it = evicted_cookies_.find(key);
+  if (it != evicted_cookies_.end()) {
+    if (!it->second->is_expired(current))
+      delegate_->Report(*it->second, current);  // Reinstatement.
+    delete it->second;
+    evicted_cookies_.erase(it);
+  }
+}
+
+}  // namespace net