DNS: Retain stale entries in HostCache and return when requested

net/dns/host_cache.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.
 
 #include "net/dns/host_cache.h"
 
 #include "base/logging.h"
 #include "base/memory/ptr_util.h"
 #include "base/metrics/field_trial.h"
 #include "base/metrics/histogram_macros.h"
 #include "base/strings/string_number_conversions.h"
 #include "base/trace_event/trace_event.h"
 #include "net/base/net_errors.h"
+#include "net/dns/dns_util.h"
 
 namespace net {
 
-//-----------------------------------------------------------------------------
+namespace {
+
+#define CACHE_HISTOGRAM_TIME(name, time) \
+  UMA_HISTOGRAM_LONG_TIMES("DNS.HostCache" name, time)
+
+#define CACHE_HISTOGRAM_COUNT(name, count) \
+  UMA_HISTOGRAM_COUNTS_1000("DNS.HostCache" name, count)
+
+#define CACHE_HISTOGRAM_ENUM(name, value, max) \
+  UMA_HISTOGRAM_ENUMERATION("DNS.HostCache" name, value, max)
+
+void HistogramUpdateStale(const HostCache::EntryInternal& old_entry,
+                          const HostCache::Entry& new_entry,
+                          base::TimeDelta expired_by,
+                          unsigned network_changes,
+                          unsigned stale_hits) {
+  AddressListDeltaType delta =
+      FindAddressListDeltaType(old_entry.addrlist, new_entry.addrlist);
+  CACHE_HISTOGRAM_ENUM("UpdateStaleDelta", delta, MAX_DELTA_TYPE);
+  switch (delta) {
+    case DELTA_IDENTICAL:
+      CACHE_HISTOGRAM_TIME("UpdateStaleExpiredBy_Identical", expired_by);
+      CACHE_HISTOGRAM_COUNT("UpdateStaleNetworkChanges_Identical",
+                            network_changes);
+      break;
+    case DELTA_REORDERED:
+      CACHE_HISTOGRAM_TIME("UpdateStaleExpiredBy_Reordered", expired_by);
+      CACHE_HISTOGRAM_COUNT("UpdateStaleNetworkChanges_Reordered",
+                            network_changes);
+      break;
+    case DELTA_OVERLAP:
+      CACHE_HISTOGRAM_TIME("UpdateStaleExpiredBy_Overlap", expired_by);
+      CACHE_HISTOGRAM_COUNT("UpdateStaleNetworkChanges_Overlap",
+                            network_changes);
+      break;
+    case DELTA_DISJOINT:
+      CACHE_HISTOGRAM_TIME("UpdateStaleExpiredBy_Disjoint", expired_by);
+      CACHE_HISTOGRAM_COUNT("UpdateStaleNetworkChanges_Dijsoint",
+                            network_changes);
+      break;
+    case MAX_DELTA_TYPE:
+      NOTREACHED();
+      break;
+  }
+}
+
+// Used in histograms; please only insert new entries before MAX.
+enum SetOutcome {
+  SET_INSERT,
+  SET_UPDATE_VALID,
+  SET_UPDATE_STALE,
+  MAX_SET_OUTCOME
+};
+
+void HistogramSet(SetOutcome outcome,
+                  base::TimeTicks now,
+                  unsigned network_changes,
+                  const HostCache::EntryInternal* old_entry,
+                  const HostCache::Entry& new_entry) {
+  CACHE_HISTOGRAM_ENUM("Set", outcome, MAX_SET_OUTCOME);
+  switch (outcome) {
+    case SET_INSERT:
+      // Nothing to log here.
+      break;
+    case SET_UPDATE_VALID:
+      break;
+    case SET_UPDATE_STALE: {
+      base::TimeDelta expired_by = now - old_entry->expires;
+      network_changes = network_changes - old_entry->network_changes;
+      unsigned stale_hits = old_entry->stale_hits;
+      CACHE_HISTOGRAM_TIME("UpdateStaleExpiredBy", expired_by);
+      CACHE_HISTOGRAM_COUNT("UpdateStaleNetworkChanges", network_changes);
+      CACHE_HISTOGRAM_COUNT("UpdateStaleHits", stale_hits);
+      if (old_entry->error == OK && new_entry.error == OK) {
+        HistogramUpdateStale(*old_entry, new_entry, expired_by, network_changes,
+                             stale_hits);
+      }
+      break;
+    }
+    case MAX_SET_OUTCOME:
+      NOTREACHED();
+      break;
+  }
+}
+
+// Used in histograms; please only insert new entries before MAX.
+enum LookupOutcome {
+  LOOKUP_MISS_ABSENT,
+  LOOKUP_MISS_STALE,
+  LOOKUP_HIT_VALID,
+  LOOKUP_HIT_STALE,
+  MAX_LOOKUP_OUTCOME
+};
+
+void HistogramLookup(LookupOutcome outcome,
+                     base::TimeTicks now,
+                     unsigned network_changes,
+                     const HostCache::EntryInternal* entry) {
+  CACHE_HISTOGRAM_ENUM("Lookup", outcome, MAX_LOOKUP_OUTCOME);
+  switch (outcome) {
+    case LOOKUP_MISS_ABSENT:
+      // Nothing to log here.
+      break;
+    case LOOKUP_MISS_STALE:
+    case LOOKUP_HIT_VALID:
+      break;
+    case LOOKUP_HIT_STALE:
+      CACHE_HISTOGRAM_TIME("LookupStaleExpiredBy", now - entry->expires);
+      CACHE_HISTOGRAM_COUNT("LookupStaleNetworkChanges",
+                            network_changes - entry->network_changes);
+      CACHE_HISTOGRAM_COUNT("LookupStaleHits", entry->stale_hits);
+      break;
+    case MAX_LOOKUP_OUTCOME:
+      NOTREACHED();
+      break;
+  }
+}
+
+// Used in histograms; please only insert new entries before MAX.
+enum EraseReason { ERASE_EVICT, ERASE_CLEAR, ERASE_DESTRUCT, MAX_ERASE_REASON };
+
+void HistogramErase(EraseReason reason,
+                    base::TimeTicks now,
+                    unsigned network_changes,
+                    const HostCache::EntryInternal& entry) {
+  HostCache::StaleEntryInfo stale;
+  entry.CheckStale(now, network_changes, &stale);
+  CACHE_HISTOGRAM_ENUM("Erase", reason, MAX_ERASE_REASON);
+  switch (reason) {
+    case ERASE_EVICT:
+      if (stale.is_stale()) {
+        CACHE_HISTOGRAM_TIME("EvictStaleExpiredBy", stale.expired_by);
+        CACHE_HISTOGRAM_COUNT("EvictStaleNetworkChanges",
+                              stale.network_changes);
+        CACHE_HISTOGRAM_COUNT("EvictStaleHits", entry.stale_hits);
+      } else {
+        CACHE_HISTOGRAM_TIME("EvictValidFor", -stale.expired_by);
+      }
+      break;
+    case ERASE_CLEAR:
+      // TODO(juliatuttle): Remove these once we stop clearing the cache on
+      // network change.
+      if (stale.is_stale()) {
+        CACHE_HISTOGRAM_TIME("ClearStaleExpiredBy", stale.expired_by);
+        CACHE_HISTOGRAM_COUNT("ClearStaleNetworkChanges",
+                              stale.network_changes);
+        CACHE_HISTOGRAM_COUNT("ClearStaleHits", entry.stale_hits);
+      } else {
+        CACHE_HISTOGRAM_TIME("ClearValidFor", -stale.expired_by);
+      }
+      break;
+    case ERASE_DESTRUCT:
+      break;
+    default:
+      NOTREACHED();
+      break;
+  }
+}
+
+void HistogramEraseAll(EraseReason reason,
+                       base::TimeTicks now,
+                       unsigned network_changes,
+                       const HostCache::EntryMap& entries) {
+  for (const auto& it : entries)
+    HistogramErase(reason, now, network_changes, it.second);
+}
+
+}  // namespace
 
 HostCache::Entry::Entry(int error, const AddressList& addrlist,
                         base::TimeDelta ttl)
     : error(error),
       addrlist(addrlist),
       ttl(ttl) {
   DCHECK(ttl >= base::TimeDelta());
 }
 
 HostCache::Entry::Entry(int error, const AddressList& addrlist)
     : error(error),
       addrlist(addrlist),
       ttl(base::TimeDelta::FromSeconds(-1)) {
 }
 
-HostCache::Entry::~Entry() {
-}
-
-//-----------------------------------------------------------------------------
+HostCache::Entry::~Entry() {}
 
 HostCache::HostCache(size_t max_entries)
-    : entries_(max_entries) {
-}
+    : max_entries_(max_entries), network_changes_(0u) {}
 
 HostCache::~HostCache() {
+  HistogramEraseAll(ERASE_DESTRUCT, base::TimeTicks::Now(), network_changes_,
+                    entries_);
 }
 
 const HostCache::Entry* HostCache::Lookup(const Key& key,
                                           base::TimeTicks now) {
+  return LookupStale(key, now, nullptr);
+}
+
+const HostCache::Entry* HostCache::LookupStale(
+    const Key& key,
+    base::TimeTicks now,
+    HostCache::StaleEntryInfo* stale_out) {
   DCHECK(CalledOnValidThread());
   if (caching_is_disabled())
-    return NULL;
+    return nullptr;
 
-  return entries_.Get(key, now);
+  auto it = entries_.find(key);
+  if (it == entries_.end()) {
+    HistogramLookup(LOOKUP_MISS_ABSENT, now, network_changes_, nullptr);
+    return nullptr;
+  }
+
+  bool is_stale = it->second.CheckStale(now, network_changes_, stale_out);
+  if (is_stale && !stale_out) {
+    HistogramLookup(LOOKUP_MISS_STALE, now, network_changes_, &it->second);
+    return nullptr;
+  }
+
+  if (is_stale) {
+    HistogramLookup(LOOKUP_HIT_STALE, now, network_changes_, &it->second);
+    stale_out->stale_hits = ++it->second.stale_hits;
+  } else {
+    HistogramLookup(LOOKUP_HIT_VALID, now, network_changes_, &it->second);
+  }
+  ++it->second.total_hits;
+
+  return &it->second;
 }
 
 void HostCache::Set(const Key& key,
                     const Entry& entry,
                     base::TimeTicks now,
                     base::TimeDelta ttl) {
   TRACE_EVENT0("net", "HostCache::Set");
   DCHECK(CalledOnValidThread());
   if (caching_is_disabled())
     return;
 
-  entries_.Put(key, entry, now, now + ttl);
+  auto it = entries_.find(key);
+  if (it != entries_.end()) {
+    bool is_stale = it->second.CheckStale(now, network_changes_, nullptr);
+    if (is_stale)
+      HistogramSet(SET_UPDATE_STALE, now, network_changes_, &it->second, entry);
+    else
+      HistogramSet(SET_UPDATE_VALID, now, network_changes_, &it->second, entry);
+    // TODO: Remember some old metadata, if it's useful?
+    entries_.erase(it);
+  } else {
+    if (size() == max_entries_)
+      Evict(now);
+    HistogramSet(SET_INSERT, now, network_changes_, nullptr, entry);
+  }
+
+  DCHECK_GT(max_entries_, size());
+  DCHECK_EQ(0u, entries_.count(key));
+  entries_.insert(std::make_pair(
+      Key(key), EntryInternal(entry, now, ttl, network_changes_)));
+  DCHECK_GE(max_entries_, size());
+}
+
+void HostCache::OnNetworkChange() {
+  ++network_changes_;
 }
 
 void HostCache::clear() {
   DCHECK(CalledOnValidThread());
-  entries_.Clear();
+  HistogramEraseAll(ERASE_CLEAR, base::TimeTicks::Now(), network_changes_,
+                    entries_);
+  entries_.clear();
 }
 
 size_t HostCache::size() const {
   DCHECK(CalledOnValidThread());
   return entries_.size();
 }
 
 size_t HostCache::max_entries() const {
   DCHECK(CalledOnValidThread());
-  return entries_.max_entries();
+  return max_entries_;
+}
+
+std::unique_ptr<base::Value> HostCache::GetEntriesAsValue() const {
+  base::ListValue* entry_list = new base::ListValue();
+
+  for (auto& pair : entries_) {
+    const Key& key = pair.first;
+    const EntryInternal& entry = pair.second;
+
+    base::DictionaryValue* entry_dict = new base::DictionaryValue();
+
+    entry_dict->SetString("hostname", key.hostname);
+    entry_dict->SetInteger("address_family",
+                           static_cast<int>(key.address_family));
+    entry_dict->SetString("expiration",
+                          NetLog::TickCountToString(entry.expires));
+
+    if (entry.error != OK) {
+      entry_dict->SetInteger("error", entry.error);
+    } else {
+      base::ListValue* address_list = new base::ListValue();
+      for (size_t i = 0; i < entry.addrlist.size(); ++i)
+        address_list->AppendString(entry.addrlist[i].ToStringWithoutPort());
+      entry_dict->Set("addresses", address_list);
+    }
+
+    entry_list->Append(entry_dict);
+  }
+
+  return base::WrapUnique(entry_list);
 }
 
 // Note that this map may contain expired entries.
-const HostCache::EntryMap& HostCache::entries() const {
+/* const HostCache::EntryMap& HostCache::entries() const {
   DCHECK(CalledOnValidThread());
   return entries_;
-}
+} */
 
 // static
 std::unique_ptr<HostCache> HostCache::CreateDefaultCache() {
 // Cache capacity is determined by the field trial.
 #if defined(ENABLE_BUILT_IN_DNS)
   const size_t kDefaultMaxEntries = 1000;
 #else
   const size_t kDefaultMaxEntries = 100;
 #endif
   const size_t kSaneMaxEntries = 1 << 20;
   size_t max_entries = 0;
   base::StringToSizeT(base::FieldTrialList::FindFullName("HostCacheSize"),
                       &max_entries);
   if ((max_entries == 0) || (max_entries > kSaneMaxEntries))
     max_entries = kDefaultMaxEntries;
   return base::WrapUnique(new HostCache(max_entries));
 }
 
-void HostCache::EvictionHandler::Handle(
-    const Key& key,
-    const Entry& entry,
-    const base::TimeTicks& expiration,
-    const base::TimeTicks& now,
-    bool on_get) const {
-  if (on_get) {
-    DCHECK(now >= expiration);
-    UMA_HISTOGRAM_CUSTOM_TIMES("DNS.CacheExpiredOnGet", now - expiration,
-        base::TimeDelta::FromSeconds(1), base::TimeDelta::FromDays(1), 100);
-    return;
+HostCache::EntryInternal::EntryInternal(const HostCache::Entry& entry,
+                                        base::TimeTicks now,
+                                        base::TimeDelta ttl,
+                                        unsigned network_changes)
+    : HostCache::Entry(entry),
+      added(now),
+      expires(now + ttl),
+      network_changes(network_changes),
+      total_hits(0u),
+      stale_hits(0u) {}
+
+bool HostCache::EntryInternal::CheckStale(
+    base::TimeTicks now,
+    unsigned network_changes,
+    HostCache::StaleEntryInfo* out) const {
+  StaleEntryInfo stale;
+  stale.expired_by = now - expires;
+  stale.network_changes = network_changes - this->network_changes;
+  stale.stale_hits = stale_hits;
+
+  if (out)
+    *out = stale;
+  return stale.is_stale();
+}
+
+void HostCache::Evict(base::TimeTicks now) {
+  DCHECK_LT(0u, entries_.size());
+
+  EntryMap::iterator it = SelectEntryToEvict();
+  HistogramErase(ERASE_EVICT, now, network_changes_, it->second);
+  entries_.erase(it);
+}
+
+HostCache::EntryMap::iterator HostCache::SelectEntryToEvict() {
+  DCHECK_LT(0u, entries_.size());
+
+  auto oldest_it = entries_.begin();
+  for (auto it = entries_.begin(); it != entries_.end(); ++it) {
+    if (it->second.expires < oldest_it->second.expires)
+      oldest_it = it;
   }
-  if (expiration > now) {
-    UMA_HISTOGRAM_CUSTOM_TIMES("DNS.CacheEvicted", expiration - now,
-        base::TimeDelta::FromSeconds(1), base::TimeDelta::FromDays(1), 100);
-  } else {
-    UMA_HISTOGRAM_CUSTOM_TIMES("DNS.CacheExpired", now - expiration,
-        base::TimeDelta::FromSeconds(1), base::TimeDelta::FromDays(1), 100);
-  }
+  return oldest_it;
 }
 
 }  // namespace net