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("UpdateStale.AddressListDelta", delta, MAX_DELTA_TYPE);
+  switch (delta) {
+    case DELTA_IDENTICAL:
+      CACHE_HISTOGRAM_TIME("UpdateStale.ExpiredBy_Identical", expired_by);
+      CACHE_HISTOGRAM_COUNT("UpdateStale.NetworkChanges_Identical",
+                            network_changes);
+      break;
+    case DELTA_REORDERED:
+      CACHE_HISTOGRAM_TIME("UpdateStale.ExpiredBy_Reordered", expired_by);
+      CACHE_HISTOGRAM_COUNT("UpdateStale.NetworkChanges_Reordered",
+                            network_changes);
+      break;
+    case DELTA_OVERLAP:
+      CACHE_HISTOGRAM_TIME("UpdateStale.ExpiredBy_Overlap", expired_by);
+      CACHE_HISTOGRAM_COUNT("UpdateStale.NetworkChanges_Overlap",
+                            network_changes);
+      break;
+    case DELTA_DISJOINT:
+      CACHE_HISTOGRAM_TIME("UpdateStale.ExpiredBy_Disjoint", expired_by);
+      CACHE_HISTOGRAM_COUNT("UpdateStale.NetworkChanges_Dijsoint",
+                            network_changes);
+      break;
+    case MAX_DELTA_TYPE:
+      NOTREACHED();
+      break;
+  }
+}
+
+// Used in histograms; do not modify existing values.
+enum SetOutcome {
+  SET_INSERT = 0,
+  SET_UPDATE_VALID = 1,
+  SET_UPDATE_STALE = 2,
+  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("UpdateStale.ExpiredBy", expired_by);
+      CACHE_HISTOGRAM_COUNT("UpdateStale.NetworkChanges", network_changes);
+      CACHE_HISTOGRAM_COUNT("UpdateStale.StaleHits", 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; do not modify existing values.
+enum LookupOutcome {
+  LOOKUP_MISS_ABSENT = 0,
+  LOOKUP_MISS_STALE = 1,
+  LOOKUP_HIT_VALID = 2,
+  LOOKUP_HIT_STALE = 3,
+  MAX_LOOKUP_OUTCOME
+};
+
+void HistogramLookup(LookupOutcome outcome,

[Randy Smith (Not in Mondays), 2016/04/28 16:24:16]

nit, suggestion: I'd rather have these functions named "HistorgramRecord*" (or
maybe just Record*) as what they're doing is recording info (rather than, e.g.,
HistogramErase erasing histograms).

[Julia Tuttle, 2016/04/29 17:33:52]

Done.

+                     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("LookupStale.ExpiredBy", now - entry->expires);
+      CACHE_HISTOGRAM_COUNT("LookupStale.NetworkChanges",
+                            network_changes - entry->network_changes);
+      CACHE_HISTOGRAM_COUNT("LookupStale.Hits", entry->stale_hits);
+      break;
+    case MAX_LOOKUP_OUTCOME:
+      NOTREACHED();
+      break;
+  }
+}
+
+// Used in histograms; do not modify existing values.
+enum EraseReason {
+  ERASE_EVICT = 0,
+  ERASE_CLEAR = 1,
+  ERASE_DESTRUCT = 2,
+  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("EvictStale.ExpiredBy", stale.expired_by);
+        CACHE_HISTOGRAM_COUNT("EvictStale.NetworkChanges",
+                              stale.network_changes);
+        CACHE_HISTOGRAM_COUNT("EvictStale.StaleHits", entry.stale_hits);
+      } else {
+        CACHE_HISTOGRAM_TIME("EvictValid.ValidFor", -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("ClearStale.ExpiredBy", stale.expired_by);
+        CACHE_HISTOGRAM_COUNT("ClearStale.NetworkChanges",
+                              stale.network_changes);
+        CACHE_HISTOGRAM_COUNT("ClearStale.StaleHits", entry.stale_hits);
+      } else {
+        CACHE_HISTOGRAM_TIME("ClearValid.ValidFor", -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(

[Randy Smith (Not in Mondays), 2016/04/28 16:24:16]

The implicit API contract of this function (return stale entries iff stale_out
is not null) seems questionable to me; I'd rather have an API contract where
stale_out's nullity only controlled what was written into the structure it
points to.

[Julia Tuttle, 2016/04/29 17:33:52]

Agreed. Changed.

+    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;

[Randy Smith (Not in Mondays), 2016/04/28 16:24:16]

It strikes me as really weird that we only update this single entry in
StaleEntryInfo and leave the rest untouched.  I could probably understand better
whether this made sense with documentation on the API contract for this
function; could you provide that?

(I'll say ahead of time I dislike having two separate return pathways, both
returning structures, from the same function; I'd rather have a function that
returns a single structure.  Maybe Make this void*, filling in StaleEntryInfo,
and have a const pointer to the Entry as a member of that structure?  But feel
free just to document answering my concern above, and I'll make suggestions or
not on what I'd like to see differently at that point.)

(I'm also bothered by setting different portions of a structure in different
locations; I like to have structures internally consistent all the time.  But I
don't yet understand well enough how you're using StaleEntryInfo to suggest
changes.)

[Julia Tuttle, 2016/04/29 17:33:52]

Agreed. Changed.

+  } 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(juliatuttle): Remember some old metadata, if it's useful?
+    entries_.erase(it);
+  } else {
+    if (size() == max_entries_)
+      Evict(now);

[Randy Smith (Not in Mondays), 2016/04/28 16:24:16]

(Throw out all stale entries when we reach max?  What about a more gradual, LRU
policy?)

[Julia Tuttle, 2016/04/29 17:33:51]

Wrong, it evicts the oldest. I've renamed Evict to EvictOneEntry to clarify.

We don't currently track LRU, but we could.

[Randy Smith (Not in Mondays), 2016/05/04 18:15:24]

Sorry, this was my bad--I'm trying an experiment in reviewing these CLs of
making my notes to myself as I go in parens to come back to, and I missed this
one.  In the future, if you see notes like this, feel free to call me on them or
ignore them--they shouldn't make it into the published comments.

+    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();

[Ryan Sleevi, 2016/04/28 01:44:24]

better to use

scoped_ptr<base::ListValue> entry_list(new base::ListValue());

and then for your return
return std::move(entry_list)


(which will convert to the base::Value).

Mostly, it keeps the memory safer if a short-circuit was ever added.

[Randy Smith (Not in Mondays), 2016/04/28 16:24:16]

+1 except use std::unique_ptr.

[Julia Tuttle, 2016/04/29 17:33:51]

Done.

+
+  for (auto& pair : entries_) {

[Ryan Sleevi, 2016/04/28 01:44:24]

const auto?

[Julia Tuttle, 2016/04/29 17:33:51]

Done.

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

[Ryan Sleevi, 2016/04/28 01:44:24]

Leftover to delete?

[Julia Tuttle, 2016/04/29 17:33:51]

Indeed. Deleted.

   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;

[Ryan Sleevi, 2016/04/28 01:44:24]

My Kingdom for C++14, he laments!

return std::min_element(entries_.begin(), entries_.end(), [](const auto& lhs,
const auto& rhs) -> bool { return lhs.second.expires < rhs.second.expires; });


generic lambdas aren't until C++14; otherwise, it'd have to be grossness like
[](const EntryMap::value_type& lhs, const EntryMap::value_type& rhs) -> bool {
return lhs.second.expires < rhs.second.expires; });

(Assuming you don't have to specify HostCache before EntryMap because the
lexical scoping of the lambda is within the HostCache itself)

 }
 
 }  // namespace net