host_cache.h 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535
  1. // Copyright (c) 2012 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef NET_DNS_HOST_CACHE_H_
  5. #define NET_DNS_HOST_CACHE_H_
  6. #include <stddef.h>
  7. #include <functional>
  8. #include <map>
  9. #include <memory>
  10. #include <ostream>
  11. #include <set>
  12. #include <string>
  13. #include <tuple>
  14. #include <utility>
  15. #include <vector>
  16. #include "base/check.h"
  17. #include "base/gtest_prod_util.h"
  18. #include "base/memory/raw_ptr.h"
  19. #include "base/numerics/clamped_math.h"
  20. #include "base/stl_util.h"
  21. #include "base/threading/thread_checker.h"
  22. #include "base/time/time.h"
  23. #include "base/values.h"
  24. #include "net/base/address_family.h"
  25. #include "net/base/connection_endpoint_metadata.h"
  26. #include "net/base/expiring_cache.h"
  27. #include "net/base/host_port_pair.h"
  28. #include "net/base/ip_endpoint.h"
  29. #include "net/base/net_errors.h"
  30. #include "net/base/net_export.h"
  31. #include "net/base/network_isolation_key.h"
  32. #include "net/dns/host_resolver_results.h"
  33. #include "net/dns/public/dns_query_type.h"
  34. #include "net/dns/public/host_resolver_source.h"
  35. #include "net/log/net_log_capture_mode.h"
  36. #include "third_party/abseil-cpp/absl/types/optional.h"
  37. #include "third_party/abseil-cpp/absl/types/variant.h"
  38. #include "url/scheme_host_port.h"
  39. namespace base {
  40. class TickClock;
  41. } // namespace base
  42. namespace net {
  43. // Cache used by HostResolver to map hostnames to their resolved result.
  44. class NET_EXPORT HostCache {
  45. public:
  46. struct NET_EXPORT Key {
  47. // Hostnames in `host` must not be IP literals. IP literals should be
  48. // resolved directly to the IP address and not be stored/queried in
  49. // HostCache.
  50. Key(absl::variant<url::SchemeHostPort, std::string> host,
  51. DnsQueryType dns_query_type,
  52. HostResolverFlags host_resolver_flags,
  53. HostResolverSource host_resolver_source,
  54. const NetworkIsolationKey& network_isolation_key);
  55. Key();
  56. Key(const Key& key);
  57. Key(Key&& key);
  58. ~Key();
  59. // This is a helper used in comparing keys. The order of comparisons of
  60. // `Key` fields is arbitrary, but the tuple is constructed with
  61. // `dns_query_type` and `host_resolver_flags` before `host` under the
  62. // assumption that integer comparisons are faster than string comparisons.
  63. static auto GetTuple(const Key* key) {
  64. return std::tie(key->dns_query_type, key->host_resolver_flags, key->host,
  65. key->host_resolver_source, key->network_isolation_key,
  66. key->secure);
  67. }
  68. bool operator==(const Key& other) const {
  69. return GetTuple(this) == GetTuple(&other);
  70. }
  71. bool operator!=(const Key& other) const {
  72. return GetTuple(this) != GetTuple(&other);
  73. }
  74. bool operator<(const Key& other) const {
  75. return GetTuple(this) < GetTuple(&other);
  76. }
  77. absl::variant<url::SchemeHostPort, std::string> host;
  78. DnsQueryType dns_query_type = DnsQueryType::UNSPECIFIED;
  79. HostResolverFlags host_resolver_flags = 0;
  80. HostResolverSource host_resolver_source = HostResolverSource::ANY;
  81. NetworkIsolationKey network_isolation_key;
  82. bool secure = false;
  83. };
  84. struct NET_EXPORT EntryStaleness {
  85. // Time since the entry's TTL has expired. Negative if not expired.
  86. base::TimeDelta expired_by;
  87. // Number of network changes since this result was cached.
  88. int network_changes;
  89. // Number of hits to the cache entry while stale (expired or past-network).
  90. int stale_hits;
  91. bool is_stale() const {
  92. return network_changes > 0 || expired_by >= base::TimeDelta();
  93. }
  94. };
  95. // Stores the latest address list that was looked up for a hostname.
  96. class NET_EXPORT Entry {
  97. public:
  98. enum Source : int {
  99. // Address list was obtained from an unknown source.
  100. SOURCE_UNKNOWN,
  101. // Address list was obtained via a DNS lookup.
  102. SOURCE_DNS,
  103. // Address list was obtained by searching a HOSTS file.
  104. SOURCE_HOSTS,
  105. // Address list was a preset from the DnsConfig.
  106. SOURCE_CONFIG,
  107. };
  108. // |ttl=absl::nullopt| for unknown TTL.
  109. template <typename T>
  110. Entry(int error,
  111. T&& results,
  112. Source source,
  113. absl::optional<base::TimeDelta> ttl)
  114. : error_(error),
  115. source_(source),
  116. ttl_(ttl ? ttl.value() : base::Seconds(-1)) {
  117. DCHECK(!ttl || ttl.value() >= base::TimeDelta());
  118. SetResult(std::forward<T>(results));
  119. }
  120. // Use when |ttl| is unknown.
  121. template <typename T>
  122. Entry(int error, T&& results, Source source)
  123. : Entry(error, std::forward<T>(results), source, absl::nullopt) {}
  124. // Use for address entries.
  125. Entry(int error,
  126. std::vector<IPEndPoint> ip_endpoints,
  127. std::set<std::string> aliases,
  128. Source source,
  129. absl::optional<base::TimeDelta> ttl = absl::nullopt);
  130. // For errors with no |results|.
  131. Entry(int error,
  132. Source source,
  133. absl::optional<base::TimeDelta> ttl = absl::nullopt);
  134. Entry(const Entry& entry);
  135. Entry(Entry&& entry);
  136. ~Entry();
  137. Entry& operator=(const Entry& entry);
  138. Entry& operator=(Entry&& entry);
  139. bool operator==(const Entry& other) const {
  140. return ContentsEqual(other) &&
  141. std::tie(source_, pinning_, ttl_, expires_, network_changes_,
  142. total_hits_, stale_hits_) ==
  143. std::tie(other.source_, other.pinning_, other.ttl_,
  144. other.expires_, other.network_changes_,
  145. other.total_hits_, other.stale_hits_);
  146. }
  147. bool ContentsEqual(const Entry& other) const {
  148. return std::tie(error_, ip_endpoints_, endpoint_metadatas_, aliases_,
  149. text_records_, hostnames_, https_record_compatibility_,
  150. canonical_names_) ==
  151. std::tie(
  152. other.error_, other.ip_endpoints_, other.endpoint_metadatas_,
  153. other.aliases_, other.text_records_, other.hostnames_,
  154. other.https_record_compatibility_, other.canonical_names_);
  155. }
  156. int error() const { return error_; }
  157. bool did_complete() const {
  158. return error_ != ERR_NETWORK_CHANGED &&
  159. error_ != ERR_HOST_RESOLVER_QUEUE_TOO_LARGE;
  160. }
  161. void set_error(int error) { error_ = error; }
  162. absl::optional<std::vector<HostResolverEndpointResult>> GetEndpoints()
  163. const;
  164. const std::vector<IPEndPoint>* ip_endpoints() const {
  165. return base::OptionalOrNullptr(ip_endpoints_);
  166. }
  167. void set_ip_endpoints(
  168. absl::optional<std::vector<IPEndPoint>> ip_endpoints) {
  169. ip_endpoints_ = std::move(ip_endpoints);
  170. }
  171. absl::optional<std::vector<ConnectionEndpointMetadata>> GetMetadatas()
  172. const;
  173. void ClearMetadatas() { endpoint_metadatas_.reset(); }
  174. const std::set<std::string>* aliases() const {
  175. return base::OptionalOrNullptr(aliases_);
  176. }
  177. void set_aliases(std::set<std::string> aliases) {
  178. aliases_ = std::move(aliases);
  179. }
  180. const absl::optional<std::vector<std::string>>& text_records() const {
  181. return text_records_;
  182. }
  183. void set_text_records(
  184. absl::optional<std::vector<std::string>> text_records) {
  185. text_records_ = std::move(text_records);
  186. }
  187. const absl::optional<std::vector<HostPortPair>>& hostnames() const {
  188. return hostnames_;
  189. }
  190. void set_hostnames(absl::optional<std::vector<HostPortPair>> hostnames) {
  191. hostnames_ = std::move(hostnames);
  192. }
  193. const std::vector<bool>* https_record_compatibility() const {
  194. return base::OptionalOrNullptr(https_record_compatibility_);
  195. }
  196. void set_https_record_compatibility(
  197. absl::optional<std::vector<bool>> https_record_compatibility) {
  198. https_record_compatibility_ = std::move(https_record_compatibility);
  199. }
  200. absl::optional<bool> pinning() const { return pinning_; }
  201. void set_pinning(absl::optional<bool> pinning) { pinning_ = pinning; }
  202. const absl::optional<std::set<std::string>>& canonical_names() const {
  203. return canonical_names_;
  204. }
  205. void set_canonical_names(
  206. absl::optional<std::set<std::string>> canonical_names) {
  207. canonical_names_ = std::move(canonical_names);
  208. }
  209. Source source() const { return source_; }
  210. bool has_ttl() const { return ttl_ >= base::TimeDelta(); }
  211. base::TimeDelta ttl() const { return ttl_; }
  212. absl::optional<base::TimeDelta> GetOptionalTtl() const;
  213. void set_ttl(base::TimeDelta ttl) { ttl_ = ttl; }
  214. base::TimeTicks expires() const { return expires_; }
  215. // Public for the net-internals UI.
  216. int network_changes() const { return network_changes_; }
  217. // Merge |front| and |back|, representing results from multiple transactions
  218. // for the same overall host resolution query.
  219. //
  220. // Merges lists, placing elements from |front| before elements from |back|.
  221. // Further, dedupes legacy address lists and moves IPv6 addresses before
  222. // IPv4 addresses (maintaining stable order otherwise).
  223. //
  224. // Fields that cannot be merged take precedence from |front|.
  225. static Entry MergeEntries(Entry front, Entry back);
  226. // Creates a value representation of the entry for use with NetLog.
  227. base::Value NetLogParams() const;
  228. // Creates a copy of |this| with the port of all address and hostname values
  229. // set to |port| if the current port is 0. Preserves any non-zero ports.
  230. HostCache::Entry CopyWithDefaultPort(uint16_t port) const;
  231. private:
  232. using HttpsRecordPriority = uint16_t;
  233. friend class HostCache;
  234. Entry(const Entry& entry,
  235. base::TimeTicks now,
  236. base::TimeDelta ttl,
  237. int network_changes);
  238. Entry(int error,
  239. absl::optional<std::vector<IPEndPoint>> ip_endpoints,
  240. absl::optional<
  241. std::multimap<HttpsRecordPriority, ConnectionEndpointMetadata>>
  242. endpoint_metadatas,
  243. absl::optional<std::set<std::string>> aliases,
  244. absl::optional<std::vector<std::string>>&& text_results,
  245. absl::optional<std::vector<HostPortPair>>&& hostnames,
  246. absl::optional<std::vector<bool>>&& https_record_compatibility,
  247. Source source,
  248. base::TimeTicks expires,
  249. int network_changes);
  250. void PrepareForCacheInsertion();
  251. void SetResult(
  252. std::multimap<HttpsRecordPriority, ConnectionEndpointMetadata>
  253. endpoint_metadatas) {
  254. endpoint_metadatas_ = std::move(endpoint_metadatas);
  255. }
  256. void SetResult(std::vector<std::string> text_records) {
  257. text_records_ = std::move(text_records);
  258. }
  259. void SetResult(std::vector<HostPortPair> hostnames) {
  260. hostnames_ = std::move(hostnames);
  261. }
  262. void SetResult(std::vector<bool> https_record_compatibility) {
  263. https_record_compatibility_ = std::move(https_record_compatibility);
  264. }
  265. int total_hits() const { return total_hits_; }
  266. int stale_hits() const { return stale_hits_; }
  267. bool IsStale(base::TimeTicks now, int network_changes) const;
  268. void CountHit(bool hit_is_stale);
  269. void GetStaleness(base::TimeTicks now,
  270. int network_changes,
  271. EntryStaleness* out) const;
  272. base::Value::Dict GetAsValue(bool include_staleness) const;
  273. // The resolve results for this entry.
  274. int error_ = ERR_FAILED;
  275. absl::optional<std::vector<IPEndPoint>> ip_endpoints_;
  276. absl::optional<
  277. std::multimap<HttpsRecordPriority, ConnectionEndpointMetadata>>
  278. endpoint_metadatas_;
  279. absl::optional<std::set<std::string>> aliases_;
  280. absl::optional<std::vector<std::string>> text_records_;
  281. absl::optional<std::vector<HostPortPair>> hostnames_;
  282. // Bool of whether each HTTPS record received is compatible
  283. // (draft-ietf-dnsop-svcb-https-08#section-8), considering alias records to
  284. // always be compatible.
  285. //
  286. // This field may be reused for experimental query types to record
  287. // successfully received records of that experimental type.
  288. //
  289. // For either usage, cleared before inserting in cache.
  290. absl::optional<std::vector<bool>> https_record_compatibility_;
  291. // Where results were obtained (e.g. DNS lookup, hosts file, etc).
  292. Source source_ = SOURCE_UNKNOWN;
  293. // If true, this entry cannot be evicted from the cache until after the next
  294. // network change. When an Entry is replaced by one whose pinning flag
  295. // is not set, HostCache will copy this flag to the replacement.
  296. // If this flag is null, HostCache will set it to false for simplicity.
  297. // Note: This flag is not yet used, and should be removed if the proposals
  298. // for followup queries after insecure/expired bootstrap are abandoned (see
  299. // TODO(crbug.com/1200908) in HostResolverManager).
  300. absl::optional<bool> pinning_;
  301. // The final name at the end of the alias chain that was the record name for
  302. // the A/AAAA records.
  303. absl::optional<std::set<std::string>> canonical_names_;
  304. // TTL obtained from the nameserver. Negative if unknown.
  305. base::TimeDelta ttl_ = base::Seconds(-1);
  306. base::TimeTicks expires_;
  307. // Copied from the cache's network_changes_ when the entry is set; can
  308. // later be compared to it to see if the entry was received on the current
  309. // network.
  310. int network_changes_ = -1;
  311. // Use clamped math to cap hit counts at INT_MAX.
  312. base::ClampedNumeric<int> total_hits_ = 0;
  313. base::ClampedNumeric<int> stale_hits_ = 0;
  314. };
  315. // Interface for interacting with persistent storage, to be provided by the
  316. // embedder. Does not include support for writes that must happen immediately.
  317. class PersistenceDelegate {
  318. public:
  319. // Calling ScheduleWrite() signals that data has changed and should be
  320. // written to persistent storage. The write might be delayed.
  321. virtual void ScheduleWrite() = 0;
  322. };
  323. using EntryMap = std::map<Key, Entry>;
  324. // The two ways to serialize the cache to a value.
  325. enum class SerializationType {
  326. // Entries with transient NetworkIsolationKeys are not serialized, and
  327. // RestoreFromListValue() can load the returned value.
  328. kRestorable,
  329. // Entries with transient NetworkIsolationKeys are serialized, and
  330. // RestoreFromListValue() cannot load the returned value, since the debug
  331. // serialization of NetworkIsolationKeys is used instead of the
  332. // deserializable representation.
  333. kDebug,
  334. };
  335. // A HostCache::EntryStaleness representing a non-stale (fresh) cache entry.
  336. static const HostCache::EntryStaleness kNotStale;
  337. // Constructs a HostCache that stores up to |max_entries|.
  338. explicit HostCache(size_t max_entries);
  339. HostCache(const HostCache&) = delete;
  340. HostCache& operator=(const HostCache&) = delete;
  341. ~HostCache();
  342. // Returns a pointer to the matching (key, entry) pair, which is valid at time
  343. // |now|. If |ignore_secure| is true, ignores the secure field in |key| when
  344. // looking for a match. If there is no matching entry, returns NULL.
  345. const std::pair<const Key, Entry>* Lookup(const Key& key,
  346. base::TimeTicks now,
  347. bool ignore_secure = false);
  348. // Returns a pointer to the matching (key, entry) pair, whether it is valid or
  349. // stale at time |now|. Fills in |stale_out| with information about how stale
  350. // it is. If |ignore_secure| is true, ignores the secure field in |key| when
  351. // looking for a match. If there is no matching entry, returns NULL.
  352. const std::pair<const Key, Entry>* LookupStale(const Key& key,
  353. base::TimeTicks now,
  354. EntryStaleness* stale_out,
  355. bool ignore_secure = false);
  356. // Overwrites or creates an entry for |key|.
  357. // |entry| is the value to set, |now| is the current time
  358. // |ttl| is the "time to live".
  359. void Set(const Key& key,
  360. const Entry& entry,
  361. base::TimeTicks now,
  362. base::TimeDelta ttl);
  363. // Checks whether an entry exists for `hostname`.
  364. // If so, returns the matching key and writes the source (e.g. DNS, HOSTS
  365. // file, etc.) to `source_out` and the staleness to `stale_out` (if they are
  366. // not null). If no entry exists, returns nullptr.
  367. //
  368. // For testing use only and not very performant. Production code should only
  369. // do lookups by precise Key.
  370. const HostCache::Key* GetMatchingKeyForTesting(
  371. base::StringPiece hostname,
  372. HostCache::Entry::Source* source_out = nullptr,
  373. HostCache::EntryStaleness* stale_out = nullptr) const;
  374. // Marks all entries as stale on account of a network change.
  375. void Invalidate();
  376. void set_persistence_delegate(PersistenceDelegate* delegate);
  377. void set_tick_clock_for_testing(const base::TickClock* tick_clock) {
  378. tick_clock_ = tick_clock;
  379. }
  380. // Empties the cache.
  381. void clear();
  382. // Clears hosts matching |host_filter| from the cache.
  383. void ClearForHosts(
  384. const base::RepeatingCallback<bool(const std::string&)>& host_filter);
  385. // Fills the provided base::Value with the contents of the cache for
  386. // serialization. `entry_list` must be non-null list, and will be cleared
  387. // before adding the cache contents.
  388. void GetList(base::Value::List& entry_list,
  389. bool include_staleness,
  390. SerializationType serialization_type) const;
  391. // Takes a base::Value list representing cache entries and stores them in the
  392. // cache, skipping any that already have entries. Returns true on success,
  393. // false on failure.
  394. bool RestoreFromListValue(const base::Value::List& old_cache);
  395. // Returns the number of entries that were restored in the last call to
  396. // RestoreFromListValue().
  397. size_t last_restore_size() const { return restore_size_; }
  398. // Returns the number of entries in the cache.
  399. size_t size() const;
  400. // Following are used by net_internals UI.
  401. size_t max_entries() const;
  402. int network_changes() const { return network_changes_; }
  403. const EntryMap& entries() const { return entries_; }
  404. // Creates a default cache.
  405. static std::unique_ptr<HostCache> CreateDefaultCache();
  406. private:
  407. FRIEND_TEST_ALL_PREFIXES(HostCacheTest, NoCache);
  408. enum SetOutcome : int;
  409. enum LookupOutcome : int;
  410. enum EraseReason : int;
  411. // Returns the result that is least stale, based on the number of network
  412. // changes since the result was cached. If the results are equally stale,
  413. // prefers a securely retrieved result. Returns nullptr if both results are
  414. // nullptr.
  415. static std::pair<const HostCache::Key, HostCache::Entry>*
  416. GetLessStaleMoreSecureResult(
  417. base::TimeTicks now,
  418. std::pair<const HostCache::Key, HostCache::Entry>* result1,
  419. std::pair<const HostCache::Key, HostCache::Entry>* result2);
  420. // Returns matching key and entry from cache and nullptr if no match. Ignores
  421. // the secure field in |initial_key| if |ignore_secure| is true.
  422. std::pair<const Key, Entry>* LookupInternalIgnoringFields(
  423. const Key& initial_key,
  424. base::TimeTicks now,
  425. bool ignore_secure);
  426. // Returns matching key and entry from cache and nullptr if no match. An exact
  427. // match for |key| is required.
  428. std::pair<const Key, Entry>* LookupInternal(const Key& key);
  429. // Returns true if this HostCache can contain no entries.
  430. bool caching_is_disabled() const { return max_entries_ == 0; }
  431. // Returns true if an entry was removed.
  432. bool EvictOneEntry(base::TimeTicks now);
  433. // Helper to check if an Entry is currently pinned in the cache.
  434. bool HasActivePin(const Entry& entry);
  435. // Helper to insert an Entry into the cache.
  436. void AddEntry(const Key& key, Entry&& entry);
  437. // Map from hostname (presumably in lowercase canonicalized format) to
  438. // a resolved result entry.
  439. EntryMap entries_;
  440. size_t max_entries_;
  441. int network_changes_ = 0;
  442. // Number of cache entries that were restored in the last call to
  443. // RestoreFromListValue(). Used in histograms.
  444. size_t restore_size_ = 0;
  445. raw_ptr<PersistenceDelegate> delegate_ = nullptr;
  446. // Shared tick clock, overridden for testing.
  447. raw_ptr<const base::TickClock> tick_clock_;
  448. THREAD_CHECKER(thread_checker_);
  449. };
  450. } // namespace net
  451. // Debug logging support
  452. std::ostream& operator<<(std::ostream& out,
  453. const net::HostCache::EntryStaleness& s);
  454. #endif // NET_DNS_HOST_CACHE_H_