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 <limits>
+#include <queue>
+#include <vector>
+
+#include "base/metrics/histogram.h"
+#include "base/rand_util.h"
+#include "base/stl_util.h"
+#include "base/string_util.h"
+#include "net/base/registry_controlled_domains/registry_controlled_domain.h"
+
+namespace net {
+
+using base::Time;
+using base::TimeDelta;
+
+namespace {
+
+const int kSecondsInWeek = 7 * 24 * 60 * 60;
+
+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;
+
+ private:
+  void InitializeHistograms();
+
+  // Histogram variables; see CookieMonster::InitializeHistograms() in

[erikwright (departed), 2013/03/21 19:22:19]

Please read the comment in InitializeHistograms that this refers to. You don't
need to store these members or Initialize anything because you don't have the
same threading constraints.

[huangs, 2013/03/21 22:08:09]

Done.

+  // cookie_monster.cc for details.
+  base::HistogramBase* histogram_reinstated_cookies_google_;
+  base::HistogramBase* histogram_reinstated_cookies_other_;
+};
+
+DelegateImpl::DelegateImpl() {
+  InitializeHistograms();
+}
+
+void DelegateImpl::Report(const EvictedDomainCookieCounter::EvictedCookie& ec,
+                          const Time& reinstatement_time) {
+  TimeDelta reinstatement_delay(reinstatement_time - ec.eviction_time_);
+  if (ec.is_google_)
+    histogram_reinstated_cookies_google_->AddTime(reinstatement_delay);
+  else
+    histogram_reinstated_cookies_other_->AddTime(reinstatement_delay);
+}
+
+Time DelegateImpl::CurrentTime() {
+  return Time::Now();
+}
+
+// Initialize all histogram counter variables used in this class.
+// See CookieMonster::InitializeHistograms() for more details.
+void DelegateImpl::InitializeHistograms() {
+  // From UMA_HISTOGRAM_CUSTOM_COUNTS
+  histogram_reinstated_cookies_google_ = base::Histogram::FactoryGet(
+      "Cookie.ReinstatedCookiesGoogle",
+      1, kSecondsInWeek, 50,
+      base::Histogram::kUmaTargetedHistogramFlag);
+  histogram_reinstated_cookies_other_ = base::Histogram::FactoryGet(
+      "Cookie.ReinstatedCookiesOther",
+      1, kSecondsInWeek, 50,
+      base::Histogram::kUmaTargetedHistogramFlag);
+}
+
+}  // namespace
+
+EvictedDomainCookieCounter::EvictedDomainCookieCounter(
+    CookieMonster::Delegate* next_delegate)
+    : next_delegate_(next_delegate),
+      reporter_(new DelegateImpl),
+      max_size_(kMaxEvictedDomainCookies),
+      purge_count_(kPurgeEvictedDomainCookies) {
+}
+
+EvictedDomainCookieCounter::EvictedDomainCookieCounter(
+    scoped_refptr<CookieMonster::Delegate> next_delegate,
+    scoped_ptr<Delegate> reporter,
+    size_t max_size,
+    size_t purge_count)
+    : next_delegate_(next_delegate),
+      reporter_(reporter.Pass()),
+      max_size_(max_size),
+      purge_count_(purge_count) {
+}
+
+EvictedDomainCookieCounter::~EvictedDomainCookieCounter() {
+  STLDeleteContainerPairSecondPointers(evicted_cookies_.begin(),
+                                       evicted_cookies_.end());
+}
+
+// static
+// Simplified from google_util.cc: IsGoogleHostname().
+bool EvictedDomainCookieCounter::IsGoogleCookie(const CanonicalCookie& cc) {

[erikwright (departed), 2013/03/21 19:22:19]

This implementation is probably fine for the purposes here, but would be unsafe
if used in other ways. I'd suggest adding "Unsafe" to the method name and adding
a comment that it's only used for the non-security-sensitive purpose of
segregating metrics.

[huangs, 2013/03/21 22:08:09]

Done.

+  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(reporter_->CurrentTime());
+  if (removed) {
+    if (cause == CookieMonster::Delegate::CHANGE_COOKIE_EVICTED)
+      StoreEvictedCookie(key, cc, current);
+    else  // Explicit deletion, so stop tracking.
+      FreeEvictedCookie(key);
+  } else {  // Including adds or updates.
+    if (ProcessCookieReinstatement(key, cc, current))
+      FreeEvictedCookie(key);
+  }
+
+  if (next_delegate_)
+    next_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/21 19:22:19]

This comment makes no sense? Why can't it be const&?

[huangs, 2013/03/21 22:08:09]

For the current usage it's fine.  But if we pass by reference and have:

// |it| is some item in evicted_cookies_
FreeExpiredEvictedCookies(it->second.expiry_time);

then it->second will be deallocated in the loop, which means  the parameter is a
reference to a deallocated object in the memory => wrong.

+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) {

[erikwright (departed), 2013/03/21 19:22:19]

The current implementation seems very costly, since it GarbageCollects on every
eviction. Probably better to maintain the priority queue as a member and just
change it incrementally with each insert/delete in the map.

[huangs, 2013/03/21 22:08:09]

Per discussion, only executed when exceeding max_size_.

+  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);
+
+  // |rand_num| is a tie-breaker to prevent domain-dependent bias when choosing
+  // among evicted cookies that have the same eviction time.
+  struct EvictedCookiePriorityQueueEntry {
+    EvictedCookie* cookie_ptr;
+    int rand_num;
+
+    EvictedCookiePriorityQueueEntry(EvictedCookie* cookie_ptr)
+      : cookie_ptr(cookie_ptr),
+        rand_num(base::RandInt(0, std::numeric_limits<int>::max())) {}
+
+    bool operator < (const EvictedCookiePriorityQueueEntry& other) const {
+      return (cookie_ptr->eviction_time_ != other.cookie_ptr->eviction_time_) ?
+          cookie_ptr->eviction_time_ < other.cookie_ptr->eviction_time_ :
+          rand_num < other.rand_num;
+    }
+  };
+
+  // Use priority queue to store oldest cookies, resize as necessary.
+  std::priority_queue<EvictedCookiePriorityQueueEntry> oldest_set;
+  for (EvictedCookieMap::iterator it = evicted_cookies_.begin();
+      it != evicted_cookies_.end(); ++it) {
+    if (it->second->is_expired(current))  // Will be removed, so decrase quota.

[erikwright (departed), 2013/03/21 19:22:19]

typo

[erikwright (departed), 2013/03/21 19:22:19]

By definition the expired cookies will always be at the top of the
priority_queue, right? So instead of treating them specially here (and
manipulating remove_quota) why not just put them in the queue and then, after
removing 'remove_quota', continue removing expired cookies?

[huangs, 2013/03/21 22:08:09]

Done.

[huangs, 2013/03/21 22:08:09]

Per discussion, sort is done by eviction time, not expiry time. Also, we should
remove expired cookies first, since they MUST be removed.

+      remove_quota = remove_quota ? remove_quota - 1 : 0;  // Cap to 0 (size_t).
+    else
+      oldest_set.push(EvictedCookiePriorityQueueEntry(it->second));
+
+    if (oldest_set.size() > remove_quota)
+      oldest_set.pop();  // Spare the youngest element from deletion.
+  }
+  DCHECK(oldest_set.size() <= remove_quota);
+
+  // Mark oldest non-expired cookies as expired, for removal.
+  while (!oldest_set.empty()) {
+    oldest_set.top().cookie_ptr->set_expired();
+    oldest_set.pop();

[erikwright (departed), 2013/03/21 19:22:19]

Couldn't you just pop and then use the key to delete from the map?

[huangs, 2013/03/21 22:08:09]

priority_queue<T>::pop() returns void (STL weirdness).  Also, deletion from map
would incur look-up overhead.

+  }
+
+  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)) {
+    FreeEvictedCookie(key);  // Deallocate explicitly.
+
+    EvictedCookie* ec =
+        new EvictedCookie(current, cc.ExpiryDate(), IsGoogleCookie(cc));
+    evicted_cookies_.insert(EvictedCookieMap::value_type(key, ec));
+
+    GarbageCollect(current);
+  }
+}
+
+bool EvictedDomainCookieCounter::ProcessCookieReinstatement(
+    const EvictedCookieKey& key,
+    const CanonicalCookie& cc,
+    const Time& current) {
+  bool ret = false;
+  EvictedCookieMap::iterator it = evicted_cookies_.find(key);
+  if (it != evicted_cookies_.end()) {
+    DCHECK(reporter_);

[erikwright (departed), 2013/03/21 19:22:19]

I don't think this DCHECK is required here. But it should be in the
constructors.

[huangs, 2013/03/21 22:08:09]

Done.

+    if (!it->second->is_expired(current))
+      reporter_->Report(*it->second, current);
+    ret = true;
+  }
+  return ret;
+}
+
+}  // namespace net