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
5#include "net/dns/host_resolver_impl.h"
6
7#if defined(OS_WIN)
8#include <Winsock2.h>
9#elif defined(OS_POSIX)
10#include <netdb.h>
11#endif
12
13#include <cmath>
14#include <utility>
15#include <vector>
16
17#include "base/basictypes.h"
18#include "base/bind.h"
19#include "base/bind_helpers.h"
20#include "base/callback.h"
21#include "base/compiler_specific.h"
22#include "base/debug/debugger.h"
23#include "base/debug/stack_trace.h"
24#include "base/message_loop/message_loop_proxy.h"
25#include "base/metrics/field_trial.h"
26#include "base/metrics/histogram.h"
27#include "base/stl_util.h"
28#include "base/strings/string_util.h"
29#include "base/strings/utf_string_conversions.h"
30#include "base/threading/worker_pool.h"
31#include "base/time/time.h"
32#include "base/values.h"
33#include "net/base/address_family.h"
34#include "net/base/address_list.h"
35#include "net/base/dns_reloader.h"
36#include "net/base/dns_util.h"
37#include "net/base/host_port_pair.h"
38#include "net/base/ip_endpoint.h"
39#include "net/base/net_errors.h"
40#include "net/base/net_log.h"
41#include "net/base/net_util.h"
42#include "net/dns/address_sorter.h"
43#include "net/dns/dns_client.h"
44#include "net/dns/dns_config_service.h"
45#include "net/dns/dns_protocol.h"
46#include "net/dns/dns_response.h"
47#include "net/dns/dns_transaction.h"
48#include "net/dns/host_resolver_proc.h"
49#include "net/socket/client_socket_factory.h"
50#include "net/udp/datagram_client_socket.h"
51
52#if defined(OS_WIN)
53#include "net/base/winsock_init.h"
54#endif
55
56namespace net {
57
58namespace {
59
60// Limit the size of hostnames that will be resolved to combat issues in
61// some platform's resolvers.
62const size_t kMaxHostLength = 4096;
63
64// Default TTL for successful resolutions with ProcTask.
65const unsigned kCacheEntryTTLSeconds = 60;
66
67// Default TTL for unsuccessful resolutions with ProcTask.
68const unsigned kNegativeCacheEntryTTLSeconds = 0;
69
70// Minimum TTL for successful resolutions with DnsTask.
71const unsigned kMinimumTTLSeconds = kCacheEntryTTLSeconds;
72
73// We use a separate histogram name for each platform to facilitate the
74// display of error codes by their symbolic name (since each platform has
75// different mappings).
76const char kOSErrorsForGetAddrinfoHistogramName[] =
77#if defined(OS_WIN)
78    "Net.OSErrorsForGetAddrinfo_Win";
79#elif defined(OS_MACOSX)
80    "Net.OSErrorsForGetAddrinfo_Mac";
81#elif defined(OS_LINUX)
82    "Net.OSErrorsForGetAddrinfo_Linux";
83#else
84    "Net.OSErrorsForGetAddrinfo";
85#endif
86
87// Gets a list of the likely error codes that getaddrinfo() can return
88// (non-exhaustive). These are the error codes that we will track via
89// a histogram.
90std::vector<int> GetAllGetAddrinfoOSErrors() {
91  int os_errors[] = {
92#if defined(OS_POSIX)
93#if !defined(OS_FREEBSD)
94#if !defined(OS_ANDROID)
95    // EAI_ADDRFAMILY has been declared obsolete in Android's and
96    // FreeBSD's netdb.h.
97    EAI_ADDRFAMILY,
98#endif
99    // EAI_NODATA has been declared obsolete in FreeBSD's netdb.h.
100    EAI_NODATA,
101#endif
102    EAI_AGAIN,
103    EAI_BADFLAGS,
104    EAI_FAIL,
105    EAI_FAMILY,
106    EAI_MEMORY,
107    EAI_NONAME,
108    EAI_SERVICE,
109    EAI_SOCKTYPE,
110    EAI_SYSTEM,
111#elif defined(OS_WIN)
112    // See: http://msdn.microsoft.com/en-us/library/ms738520(VS.85).aspx
113    WSA_NOT_ENOUGH_MEMORY,
114    WSAEAFNOSUPPORT,
115    WSAEINVAL,
116    WSAESOCKTNOSUPPORT,
117    WSAHOST_NOT_FOUND,
118    WSANO_DATA,
119    WSANO_RECOVERY,
120    WSANOTINITIALISED,
121    WSATRY_AGAIN,
122    WSATYPE_NOT_FOUND,
123    // The following are not in doc, but might be to appearing in results :-(.
124    WSA_INVALID_HANDLE,
125#endif
126  };
127
128  // Ensure all errors are positive, as histogram only tracks positive values.
129  for (size_t i = 0; i < arraysize(os_errors); ++i) {
130    os_errors[i] = std::abs(os_errors[i]);
131  }
132
133  return base::CustomHistogram::ArrayToCustomRanges(os_errors,
134                                                    arraysize(os_errors));
135}
136
137enum DnsResolveStatus {
138  RESOLVE_STATUS_DNS_SUCCESS = 0,
139  RESOLVE_STATUS_PROC_SUCCESS,
140  RESOLVE_STATUS_FAIL,
141  RESOLVE_STATUS_SUSPECT_NETBIOS,
142  RESOLVE_STATUS_MAX
143};
144
145void UmaAsyncDnsResolveStatus(DnsResolveStatus result) {
146  UMA_HISTOGRAM_ENUMERATION("AsyncDNS.ResolveStatus",
147                            result,
148                            RESOLVE_STATUS_MAX);
149}
150
151bool ResemblesNetBIOSName(const std::string& hostname) {
152  return (hostname.size() < 16) && (hostname.find('.') == std::string::npos);
153}
154
155// True if |hostname| ends with either ".local" or ".local.".
156bool ResemblesMulticastDNSName(const std::string& hostname) {
157  DCHECK(!hostname.empty());
158  const char kSuffix[] = ".local.";
159  const size_t kSuffixLen = sizeof(kSuffix) - 1;
160  const size_t kSuffixLenTrimmed = kSuffixLen - 1;
161  if (hostname[hostname.size() - 1] == '.') {
162    return hostname.size() > kSuffixLen &&
163        !hostname.compare(hostname.size() - kSuffixLen, kSuffixLen, kSuffix);
164  }
165  return hostname.size() > kSuffixLenTrimmed &&
166      !hostname.compare(hostname.size() - kSuffixLenTrimmed, kSuffixLenTrimmed,
167                        kSuffix, kSuffixLenTrimmed);
168}
169
170// Attempts to connect a UDP socket to |dest|:53.
171bool IsGloballyReachable(const IPAddressNumber& dest,
172                         const BoundNetLog& net_log) {
173  scoped_ptr<DatagramClientSocket> socket(
174      ClientSocketFactory::GetDefaultFactory()->CreateDatagramClientSocket(
175          DatagramSocket::DEFAULT_BIND,
176          RandIntCallback(),
177          net_log.net_log(),
178          net_log.source()));
179  int rv = socket->Connect(IPEndPoint(dest, 53));
180  if (rv != OK)
181    return false;
182  IPEndPoint endpoint;
183  rv = socket->GetLocalAddress(&endpoint);
184  if (rv != OK)
185    return false;
186  DCHECK_EQ(ADDRESS_FAMILY_IPV6, endpoint.GetFamily());
187  const IPAddressNumber& address = endpoint.address();
188  bool is_link_local = (address[0] == 0xFE) && ((address[1] & 0xC0) == 0x80);
189  if (is_link_local)
190    return false;
191  const uint8 kTeredoPrefix[] = { 0x20, 0x01, 0, 0 };
192  bool is_teredo = std::equal(kTeredoPrefix,
193                              kTeredoPrefix + arraysize(kTeredoPrefix),
194                              address.begin());
195  if (is_teredo)
196    return false;
197  return true;
198}
199
200// Provide a common macro to simplify code and readability. We must use a
201// macro as the underlying HISTOGRAM macro creates static variables.
202#define DNS_HISTOGRAM(name, time) UMA_HISTOGRAM_CUSTOM_TIMES(name, time, \
203    base::TimeDelta::FromMilliseconds(1), base::TimeDelta::FromHours(1), 100)
204
205// A macro to simplify code and readability.
206#define DNS_HISTOGRAM_BY_PRIORITY(basename, priority, time) \
207  do { \
208    switch (priority) { \
209      case HIGHEST: DNS_HISTOGRAM(basename "_HIGHEST", time); break; \
210      case MEDIUM: DNS_HISTOGRAM(basename "_MEDIUM", time); break; \
211      case LOW: DNS_HISTOGRAM(basename "_LOW", time); break; \
212      case LOWEST: DNS_HISTOGRAM(basename "_LOWEST", time); break; \
213      case IDLE: DNS_HISTOGRAM(basename "_IDLE", time); break; \
214      default: NOTREACHED(); break; \
215    } \
216    DNS_HISTOGRAM(basename, time); \
217  } while (0)
218
219// Record time from Request creation until a valid DNS response.
220void RecordTotalTime(bool had_dns_config,
221                     bool speculative,
222                     base::TimeDelta duration) {
223  if (had_dns_config) {
224    if (speculative) {
225      DNS_HISTOGRAM("AsyncDNS.TotalTime_speculative", duration);
226    } else {
227      DNS_HISTOGRAM("AsyncDNS.TotalTime", duration);
228    }
229  } else {
230    if (speculative) {
231      DNS_HISTOGRAM("DNS.TotalTime_speculative", duration);
232    } else {
233      DNS_HISTOGRAM("DNS.TotalTime", duration);
234    }
235  }
236}
237
238void RecordTTL(base::TimeDelta ttl) {
239  UMA_HISTOGRAM_CUSTOM_TIMES("AsyncDNS.TTL", ttl,
240                             base::TimeDelta::FromSeconds(1),
241                             base::TimeDelta::FromDays(1), 100);
242}
243
244bool ConfigureAsyncDnsNoFallbackFieldTrial() {
245  const bool kDefault = false;
246
247  // Configure the AsyncDns field trial as follows:
248  // groups AsyncDnsNoFallbackA and AsyncDnsNoFallbackB: return true,
249  // groups AsyncDnsA and AsyncDnsB: return false,
250  // groups SystemDnsA and SystemDnsB: return false,
251  // otherwise (trial absent): return default.
252  std::string group_name = base::FieldTrialList::FindFullName("AsyncDns");
253  if (!group_name.empty())
254    return StartsWithASCII(group_name, "AsyncDnsNoFallback", false);
255  return kDefault;
256}
257
258//-----------------------------------------------------------------------------
259
260AddressList EnsurePortOnAddressList(const AddressList& list, uint16 port) {
261  if (list.empty() || list.front().port() == port)
262    return list;
263  return AddressList::CopyWithPort(list, port);
264}
265
266// Returns true if |addresses| contains only IPv4 loopback addresses.
267bool IsAllIPv4Loopback(const AddressList& addresses) {
268  for (unsigned i = 0; i < addresses.size(); ++i) {
269    const IPAddressNumber& address = addresses[i].address();
270    switch (addresses[i].GetFamily()) {
271      case ADDRESS_FAMILY_IPV4:
272        if (address[0] != 127)
273          return false;
274        break;
275      case ADDRESS_FAMILY_IPV6:
276        return false;
277      default:
278        NOTREACHED();
279        return false;
280    }
281  }
282  return true;
283}
284
285// Creates NetLog parameters when the resolve failed.
286base::Value* NetLogProcTaskFailedCallback(uint32 attempt_number,
287                                          int net_error,
288                                          int os_error,
289                                          NetLog::LogLevel /* log_level */) {
290  base::DictionaryValue* dict = new base::DictionaryValue();
291  if (attempt_number)
292    dict->SetInteger("attempt_number", attempt_number);
293
294  dict->SetInteger("net_error", net_error);
295
296  if (os_error) {
297    dict->SetInteger("os_error", os_error);
298#if defined(OS_POSIX)
299    dict->SetString("os_error_string", gai_strerror(os_error));
300#elif defined(OS_WIN)
301    // Map the error code to a human-readable string.
302    LPWSTR error_string = NULL;
303    int size = FormatMessage(FORMAT_MESSAGE_ALLOCATE_BUFFER |
304                             FORMAT_MESSAGE_FROM_SYSTEM,
305                             0,  // Use the internal message table.
306                             os_error,
307                             0,  // Use default language.
308                             (LPWSTR)&error_string,
309                             0,  // Buffer size.
310                             0);  // Arguments (unused).
311    dict->SetString("os_error_string", base::WideToUTF8(error_string));
312    LocalFree(error_string);
313#endif
314  }
315
316  return dict;
317}
318
319// Creates NetLog parameters when the DnsTask failed.
320base::Value* NetLogDnsTaskFailedCallback(int net_error,
321                                         int dns_error,
322                                         NetLog::LogLevel /* log_level */) {
323  base::DictionaryValue* dict = new base::DictionaryValue();
324  dict->SetInteger("net_error", net_error);
325  if (dns_error)
326    dict->SetInteger("dns_error", dns_error);
327  return dict;
328};
329
330// Creates NetLog parameters containing the information in a RequestInfo object,
331// along with the associated NetLog::Source.
332base::Value* NetLogRequestInfoCallback(const NetLog::Source& source,
333                                       const HostResolver::RequestInfo* info,
334                                       NetLog::LogLevel /* log_level */) {
335  base::DictionaryValue* dict = new base::DictionaryValue();
336  source.AddToEventParameters(dict);
337
338  dict->SetString("host", info->host_port_pair().ToString());
339  dict->SetInteger("address_family",
340                   static_cast<int>(info->address_family()));
341  dict->SetBoolean("allow_cached_response", info->allow_cached_response());
342  dict->SetBoolean("is_speculative", info->is_speculative());
343  return dict;
344}
345
346// Creates NetLog parameters for the creation of a HostResolverImpl::Job.
347base::Value* NetLogJobCreationCallback(const NetLog::Source& source,
348                                       const std::string* host,
349                                       NetLog::LogLevel /* log_level */) {
350  base::DictionaryValue* dict = new base::DictionaryValue();
351  source.AddToEventParameters(dict);
352  dict->SetString("host", *host);
353  return dict;
354}
355
356// Creates NetLog parameters for HOST_RESOLVER_IMPL_JOB_ATTACH/DETACH events.
357base::Value* NetLogJobAttachCallback(const NetLog::Source& source,
358                                     RequestPriority priority,
359                                     NetLog::LogLevel /* log_level */) {
360  base::DictionaryValue* dict = new base::DictionaryValue();
361  source.AddToEventParameters(dict);
362  dict->SetString("priority", RequestPriorityToString(priority));
363  return dict;
364}
365
366// Creates NetLog parameters for the DNS_CONFIG_CHANGED event.
367base::Value* NetLogDnsConfigCallback(const DnsConfig* config,
368                                     NetLog::LogLevel /* log_level */) {
369  return config->ToValue();
370}
371
372// The logging routines are defined here because some requests are resolved
373// without a Request object.
374
375// Logs when a request has just been started.
376void LogStartRequest(const BoundNetLog& source_net_log,
377                     const BoundNetLog& request_net_log,
378                     const HostResolver::RequestInfo& info) {
379  source_net_log.BeginEvent(
380      NetLog::TYPE_HOST_RESOLVER_IMPL,
381      request_net_log.source().ToEventParametersCallback());
382
383  request_net_log.BeginEvent(
384      NetLog::TYPE_HOST_RESOLVER_IMPL_REQUEST,
385      base::Bind(&NetLogRequestInfoCallback, source_net_log.source(), &info));
386}
387
388// Logs when a request has just completed (before its callback is run).
389void LogFinishRequest(const BoundNetLog& source_net_log,
390                      const BoundNetLog& request_net_log,
391                      const HostResolver::RequestInfo& info,
392                      int net_error) {
393  request_net_log.EndEventWithNetErrorCode(
394      NetLog::TYPE_HOST_RESOLVER_IMPL_REQUEST, net_error);
395  source_net_log.EndEvent(NetLog::TYPE_HOST_RESOLVER_IMPL);
396}
397
398// Logs when a request has been cancelled.
399void LogCancelRequest(const BoundNetLog& source_net_log,
400                      const BoundNetLog& request_net_log,
401                      const HostResolverImpl::RequestInfo& info) {
402  request_net_log.AddEvent(NetLog::TYPE_CANCELLED);
403  request_net_log.EndEvent(NetLog::TYPE_HOST_RESOLVER_IMPL_REQUEST);
404  source_net_log.EndEvent(NetLog::TYPE_HOST_RESOLVER_IMPL);
405}
406
407//-----------------------------------------------------------------------------
408
409// Keeps track of the highest priority.
410class PriorityTracker {
411 public:
412  explicit PriorityTracker(RequestPriority initial_priority)
413      : highest_priority_(initial_priority), total_count_(0) {
414    memset(counts_, 0, sizeof(counts_));
415  }
416
417  RequestPriority highest_priority() const {
418    return highest_priority_;
419  }
420
421  size_t total_count() const {
422    return total_count_;
423  }
424
425  void Add(RequestPriority req_priority) {
426    ++total_count_;
427    ++counts_[req_priority];
428    if (highest_priority_ < req_priority)
429      highest_priority_ = req_priority;
430  }
431
432  void Remove(RequestPriority req_priority) {
433    DCHECK_GT(total_count_, 0u);
434    DCHECK_GT(counts_[req_priority], 0u);
435    --total_count_;
436    --counts_[req_priority];
437    size_t i;
438    for (i = highest_priority_; i > MINIMUM_PRIORITY && !counts_[i]; --i);
439    highest_priority_ = static_cast<RequestPriority>(i);
440
441    // In absence of requests, default to MINIMUM_PRIORITY.
442    if (total_count_ == 0)
443      DCHECK_EQ(MINIMUM_PRIORITY, highest_priority_);
444  }
445
446 private:
447  RequestPriority highest_priority_;
448  size_t total_count_;
449  size_t counts_[NUM_PRIORITIES];
450};
451
452}  // namespace
453
454//-----------------------------------------------------------------------------
455
456const unsigned HostResolverImpl::kMaximumDnsFailures = 16;
457
458// Holds the data for a request that could not be completed synchronously.
459// It is owned by a Job. Canceled Requests are only marked as canceled rather
460// than removed from the Job's |requests_| list.
461class HostResolverImpl::Request {
462 public:
463  Request(const BoundNetLog& source_net_log,
464          const BoundNetLog& request_net_log,
465          const RequestInfo& info,
466          RequestPriority priority,
467          const CompletionCallback& callback,
468          AddressList* addresses)
469      : source_net_log_(source_net_log),
470        request_net_log_(request_net_log),
471        info_(info),
472        priority_(priority),
473        job_(NULL),
474        callback_(callback),
475        addresses_(addresses),
476        request_time_(base::TimeTicks::Now()) {}
477
478  // Mark the request as canceled.
479  void MarkAsCanceled() {
480    job_ = NULL;
481    addresses_ = NULL;
482    callback_.Reset();
483  }
484
485  bool was_canceled() const {
486    return callback_.is_null();
487  }
488
489  void set_job(Job* job) {
490    DCHECK(job);
491    // Identify which job the request is waiting on.
492    job_ = job;
493  }
494
495  // Prepare final AddressList and call completion callback.
496  void OnComplete(int error, const AddressList& addr_list) {
497    DCHECK(!was_canceled());
498    if (error == OK)
499      *addresses_ = EnsurePortOnAddressList(addr_list, info_.port());
500    CompletionCallback callback = callback_;
501    MarkAsCanceled();
502    callback.Run(error);
503  }
504
505  Job* job() const {
506    return job_;
507  }
508
509  // NetLog for the source, passed in HostResolver::Resolve.
510  const BoundNetLog& source_net_log() {
511    return source_net_log_;
512  }
513
514  // NetLog for this request.
515  const BoundNetLog& request_net_log() {
516    return request_net_log_;
517  }
518
519  const RequestInfo& info() const {
520    return info_;
521  }
522
523  RequestPriority priority() const { return priority_; }
524
525  base::TimeTicks request_time() const { return request_time_; }
526
527 private:
528  BoundNetLog source_net_log_;
529  BoundNetLog request_net_log_;
530
531  // The request info that started the request.
532  const RequestInfo info_;
533
534  // TODO(akalin): Support reprioritization.
535  const RequestPriority priority_;
536
537  // The resolve job that this request is dependent on.
538  Job* job_;
539
540  // The user's callback to invoke when the request completes.
541  CompletionCallback callback_;
542
543  // The address list to save result into.
544  AddressList* addresses_;
545
546  const base::TimeTicks request_time_;
547
548  DISALLOW_COPY_AND_ASSIGN(Request);
549};
550
551//------------------------------------------------------------------------------
552
553// Calls HostResolverProc on the WorkerPool. Performs retries if necessary.
554//
555// Whenever we try to resolve the host, we post a delayed task to check if host
556// resolution (OnLookupComplete) is completed or not. If the original attempt
557// hasn't completed, then we start another attempt for host resolution. We take
558// the results from the first attempt that finishes and ignore the results from
559// all other attempts.
560//
561// TODO(szym): Move to separate source file for testing and mocking.
562//
563class HostResolverImpl::ProcTask
564    : public base::RefCountedThreadSafe<HostResolverImpl::ProcTask> {
565 public:
566  typedef base::Callback<void(int net_error,
567                              const AddressList& addr_list)> Callback;
568
569  ProcTask(const Key& key,
570           const ProcTaskParams& params,
571           const Callback& callback,
572           const BoundNetLog& job_net_log)
573      : key_(key),
574        params_(params),
575        callback_(callback),
576        origin_loop_(base::MessageLoopProxy::current()),
577        attempt_number_(0),
578        completed_attempt_number_(0),
579        completed_attempt_error_(ERR_UNEXPECTED),
580        had_non_speculative_request_(false),
581        net_log_(job_net_log) {
582    if (!params_.resolver_proc.get())
583      params_.resolver_proc = HostResolverProc::GetDefault();
584    // If default is unset, use the system proc.
585    if (!params_.resolver_proc.get())
586      params_.resolver_proc = new SystemHostResolverProc();
587  }
588
589  void Start() {
590    DCHECK(origin_loop_->BelongsToCurrentThread());
591    net_log_.BeginEvent(NetLog::TYPE_HOST_RESOLVER_IMPL_PROC_TASK);
592    StartLookupAttempt();
593  }
594
595  // Cancels this ProcTask. It will be orphaned. Any outstanding resolve
596  // attempts running on worker threads will continue running. Only once all the
597  // attempts complete will the final reference to this ProcTask be released.
598  void Cancel() {
599    DCHECK(origin_loop_->BelongsToCurrentThread());
600
601    if (was_canceled() || was_completed())
602      return;
603
604    callback_.Reset();
605    net_log_.EndEvent(NetLog::TYPE_HOST_RESOLVER_IMPL_PROC_TASK);
606  }
607
608  void set_had_non_speculative_request() {
609    DCHECK(origin_loop_->BelongsToCurrentThread());
610    had_non_speculative_request_ = true;
611  }
612
613  bool was_canceled() const {
614    DCHECK(origin_loop_->BelongsToCurrentThread());
615    return callback_.is_null();
616  }
617
618  bool was_completed() const {
619    DCHECK(origin_loop_->BelongsToCurrentThread());
620    return completed_attempt_number_ > 0;
621  }
622
623 private:
624  friend class base::RefCountedThreadSafe<ProcTask>;
625  ~ProcTask() {}
626
627  void StartLookupAttempt() {
628    DCHECK(origin_loop_->BelongsToCurrentThread());
629    base::TimeTicks start_time = base::TimeTicks::Now();
630    ++attempt_number_;
631    // Dispatch the lookup attempt to a worker thread.
632    if (!base::WorkerPool::PostTask(
633            FROM_HERE,
634            base::Bind(&ProcTask::DoLookup, this, start_time, attempt_number_),
635            true)) {
636      NOTREACHED();
637
638      // Since we could be running within Resolve() right now, we can't just
639      // call OnLookupComplete().  Instead we must wait until Resolve() has
640      // returned (IO_PENDING).
641      origin_loop_->PostTask(
642          FROM_HERE,
643          base::Bind(&ProcTask::OnLookupComplete, this, AddressList(),
644                     start_time, attempt_number_, ERR_UNEXPECTED, 0));
645      return;
646    }
647
648    net_log_.AddEvent(
649        NetLog::TYPE_HOST_RESOLVER_IMPL_ATTEMPT_STARTED,
650        NetLog::IntegerCallback("attempt_number", attempt_number_));
651
652    // If we don't get the results within a given time, RetryIfNotComplete
653    // will start a new attempt on a different worker thread if none of our
654    // outstanding attempts have completed yet.
655    if (attempt_number_ <= params_.max_retry_attempts) {
656      origin_loop_->PostDelayedTask(
657          FROM_HERE,
658          base::Bind(&ProcTask::RetryIfNotComplete, this),
659          params_.unresponsive_delay);
660    }
661  }
662
663  // WARNING: This code runs inside a worker pool. The shutdown code cannot
664  // wait for it to finish, so we must be very careful here about using other
665  // objects (like MessageLoops, Singletons, etc). During shutdown these objects
666  // may no longer exist. Multiple DoLookups() could be running in parallel, so
667  // any state inside of |this| must not mutate .
668  void DoLookup(const base::TimeTicks& start_time,
669                const uint32 attempt_number) {
670    AddressList results;
671    int os_error = 0;
672    // Running on the worker thread
673    int error = params_.resolver_proc->Resolve(key_.hostname,
674                                               key_.address_family,
675                                               key_.host_resolver_flags,
676                                               &results,
677                                               &os_error);
678
679    origin_loop_->PostTask(
680        FROM_HERE,
681        base::Bind(&ProcTask::OnLookupComplete, this, results, start_time,
682                   attempt_number, error, os_error));
683  }
684
685  // Makes next attempt if DoLookup() has not finished (runs on origin thread).
686  void RetryIfNotComplete() {
687    DCHECK(origin_loop_->BelongsToCurrentThread());
688
689    if (was_completed() || was_canceled())
690      return;
691
692    params_.unresponsive_delay *= params_.retry_factor;
693    StartLookupAttempt();
694  }
695
696  // Callback for when DoLookup() completes (runs on origin thread).
697  void OnLookupComplete(const AddressList& results,
698                        const base::TimeTicks& start_time,
699                        const uint32 attempt_number,
700                        int error,
701                        const int os_error) {
702    DCHECK(origin_loop_->BelongsToCurrentThread());
703    // If results are empty, we should return an error.
704    bool empty_list_on_ok = (error == OK && results.empty());
705    UMA_HISTOGRAM_BOOLEAN("DNS.EmptyAddressListAndNoError", empty_list_on_ok);
706    if (empty_list_on_ok)
707      error = ERR_NAME_NOT_RESOLVED;
708
709    bool was_retry_attempt = attempt_number > 1;
710
711    // Ideally the following code would be part of host_resolver_proc.cc,
712    // however it isn't safe to call NetworkChangeNotifier from worker threads.
713    // So we do it here on the IO thread instead.
714    if (error != OK && NetworkChangeNotifier::IsOffline())
715      error = ERR_INTERNET_DISCONNECTED;
716
717    // If this is the first attempt that is finishing later, then record data
718    // for the first attempt. Won't contaminate with retry attempt's data.
719    if (!was_retry_attempt)
720      RecordPerformanceHistograms(start_time, error, os_error);
721
722    RecordAttemptHistograms(start_time, attempt_number, error, os_error);
723
724    if (was_canceled())
725      return;
726
727    NetLog::ParametersCallback net_log_callback;
728    if (error != OK) {
729      net_log_callback = base::Bind(&NetLogProcTaskFailedCallback,
730                                    attempt_number,
731                                    error,
732                                    os_error);
733    } else {
734      net_log_callback = NetLog::IntegerCallback("attempt_number",
735                                                 attempt_number);
736    }
737    net_log_.AddEvent(NetLog::TYPE_HOST_RESOLVER_IMPL_ATTEMPT_FINISHED,
738                      net_log_callback);
739
740    if (was_completed())
741      return;
742
743    // Copy the results from the first worker thread that resolves the host.
744    results_ = results;
745    completed_attempt_number_ = attempt_number;
746    completed_attempt_error_ = error;
747
748    if (was_retry_attempt) {
749      // If retry attempt finishes before 1st attempt, then get stats on how
750      // much time is saved by having spawned an extra attempt.
751      retry_attempt_finished_time_ = base::TimeTicks::Now();
752    }
753
754    if (error != OK) {
755      net_log_callback = base::Bind(&NetLogProcTaskFailedCallback,
756                                    0, error, os_error);
757    } else {
758      net_log_callback = results_.CreateNetLogCallback();
759    }
760    net_log_.EndEvent(NetLog::TYPE_HOST_RESOLVER_IMPL_PROC_TASK,
761                      net_log_callback);
762
763    callback_.Run(error, results_);
764  }
765
766  void RecordPerformanceHistograms(const base::TimeTicks& start_time,
767                                   const int error,
768                                   const int os_error) const {
769    DCHECK(origin_loop_->BelongsToCurrentThread());
770    enum Category {  // Used in UMA_HISTOGRAM_ENUMERATION.
771      RESOLVE_SUCCESS,
772      RESOLVE_FAIL,
773      RESOLVE_SPECULATIVE_SUCCESS,
774      RESOLVE_SPECULATIVE_FAIL,
775      RESOLVE_MAX,  // Bounding value.
776    };
777    int category = RESOLVE_MAX;  // Illegal value for later DCHECK only.
778
779    base::TimeDelta duration = base::TimeTicks::Now() - start_time;
780    if (error == OK) {
781      if (had_non_speculative_request_) {
782        category = RESOLVE_SUCCESS;
783        DNS_HISTOGRAM("DNS.ResolveSuccess", duration);
784      } else {
785        category = RESOLVE_SPECULATIVE_SUCCESS;
786        DNS_HISTOGRAM("DNS.ResolveSpeculativeSuccess", duration);
787      }
788
789      // Log DNS lookups based on |address_family|. This will help us determine
790      // if IPv4 or IPv4/6 lookups are faster or slower.
791      switch(key_.address_family) {
792        case ADDRESS_FAMILY_IPV4:
793          DNS_HISTOGRAM("DNS.ResolveSuccess_FAMILY_IPV4", duration);
794          break;
795        case ADDRESS_FAMILY_IPV6:
796          DNS_HISTOGRAM("DNS.ResolveSuccess_FAMILY_IPV6", duration);
797          break;
798        case ADDRESS_FAMILY_UNSPECIFIED:
799          DNS_HISTOGRAM("DNS.ResolveSuccess_FAMILY_UNSPEC", duration);
800          break;
801      }
802    } else {
803      if (had_non_speculative_request_) {
804        category = RESOLVE_FAIL;
805        DNS_HISTOGRAM("DNS.ResolveFail", duration);
806      } else {
807        category = RESOLVE_SPECULATIVE_FAIL;
808        DNS_HISTOGRAM("DNS.ResolveSpeculativeFail", duration);
809      }
810      // Log DNS lookups based on |address_family|. This will help us determine
811      // if IPv4 or IPv4/6 lookups are faster or slower.
812      switch(key_.address_family) {
813        case ADDRESS_FAMILY_IPV4:
814          DNS_HISTOGRAM("DNS.ResolveFail_FAMILY_IPV4", duration);
815          break;
816        case ADDRESS_FAMILY_IPV6:
817          DNS_HISTOGRAM("DNS.ResolveFail_FAMILY_IPV6", duration);
818          break;
819        case ADDRESS_FAMILY_UNSPECIFIED:
820          DNS_HISTOGRAM("DNS.ResolveFail_FAMILY_UNSPEC", duration);
821          break;
822      }
823      UMA_HISTOGRAM_CUSTOM_ENUMERATION(kOSErrorsForGetAddrinfoHistogramName,
824                                       std::abs(os_error),
825                                       GetAllGetAddrinfoOSErrors());
826    }
827    DCHECK_LT(category, static_cast<int>(RESOLVE_MAX));  // Be sure it was set.
828
829    UMA_HISTOGRAM_ENUMERATION("DNS.ResolveCategory", category, RESOLVE_MAX);
830  }
831
832  void RecordAttemptHistograms(const base::TimeTicks& start_time,
833                               const uint32 attempt_number,
834                               const int error,
835                               const int os_error) const {
836    DCHECK(origin_loop_->BelongsToCurrentThread());
837    bool first_attempt_to_complete =
838        completed_attempt_number_ == attempt_number;
839    bool is_first_attempt = (attempt_number == 1);
840
841    if (first_attempt_to_complete) {
842      // If this was first attempt to complete, then record the resolution
843      // status of the attempt.
844      if (completed_attempt_error_ == OK) {
845        UMA_HISTOGRAM_ENUMERATION(
846            "DNS.AttemptFirstSuccess", attempt_number, 100);
847      } else {
848        UMA_HISTOGRAM_ENUMERATION(
849            "DNS.AttemptFirstFailure", attempt_number, 100);
850      }
851    }
852
853    if (error == OK)
854      UMA_HISTOGRAM_ENUMERATION("DNS.AttemptSuccess", attempt_number, 100);
855    else
856      UMA_HISTOGRAM_ENUMERATION("DNS.AttemptFailure", attempt_number, 100);
857
858    // If first attempt didn't finish before retry attempt, then calculate stats
859    // on how much time is saved by having spawned an extra attempt.
860    if (!first_attempt_to_complete && is_first_attempt && !was_canceled()) {
861      DNS_HISTOGRAM("DNS.AttemptTimeSavedByRetry",
862                    base::TimeTicks::Now() - retry_attempt_finished_time_);
863    }
864
865    if (was_canceled() || !first_attempt_to_complete) {
866      // Count those attempts which completed after the job was already canceled
867      // OR after the job was already completed by an earlier attempt (so in
868      // effect).
869      UMA_HISTOGRAM_ENUMERATION("DNS.AttemptDiscarded", attempt_number, 100);
870
871      // Record if job is canceled.
872      if (was_canceled())
873        UMA_HISTOGRAM_ENUMERATION("DNS.AttemptCancelled", attempt_number, 100);
874    }
875
876    base::TimeDelta duration = base::TimeTicks::Now() - start_time;
877    if (error == OK)
878      DNS_HISTOGRAM("DNS.AttemptSuccessDuration", duration);
879    else
880      DNS_HISTOGRAM("DNS.AttemptFailDuration", duration);
881  }
882
883  // Set on the origin thread, read on the worker thread.
884  Key key_;
885
886  // Holds an owning reference to the HostResolverProc that we are going to use.
887  // This may not be the current resolver procedure by the time we call
888  // ResolveAddrInfo, but that's OK... we'll use it anyways, and the owning
889  // reference ensures that it remains valid until we are done.
890  ProcTaskParams params_;
891
892  // The listener to the results of this ProcTask.
893  Callback callback_;
894
895  // Used to post ourselves onto the origin thread.
896  scoped_refptr<base::MessageLoopProxy> origin_loop_;
897
898  // Keeps track of the number of attempts we have made so far to resolve the
899  // host. Whenever we start an attempt to resolve the host, we increase this
900  // number.
901  uint32 attempt_number_;
902
903  // The index of the attempt which finished first (or 0 if the job is still in
904  // progress).
905  uint32 completed_attempt_number_;
906
907  // The result (a net error code) from the first attempt to complete.
908  int completed_attempt_error_;
909
910  // The time when retry attempt was finished.
911  base::TimeTicks retry_attempt_finished_time_;
912
913  // True if a non-speculative request was ever attached to this job
914  // (regardless of whether or not it was later canceled.
915  // This boolean is used for histogramming the duration of jobs used to
916  // service non-speculative requests.
917  bool had_non_speculative_request_;
918
919  AddressList results_;
920
921  BoundNetLog net_log_;
922
923  DISALLOW_COPY_AND_ASSIGN(ProcTask);
924};
925
926//-----------------------------------------------------------------------------
927
928// Wraps a call to HaveOnlyLoopbackAddresses to be executed on the WorkerPool as
929// it takes 40-100ms and should not block initialization.
930class HostResolverImpl::LoopbackProbeJob {
931 public:
932  explicit LoopbackProbeJob(const base::WeakPtr<HostResolverImpl>& resolver)
933      : resolver_(resolver),
934        result_(false) {
935    DCHECK(resolver.get());
936    const bool kIsSlow = true;
937    base::WorkerPool::PostTaskAndReply(
938        FROM_HERE,
939        base::Bind(&LoopbackProbeJob::DoProbe, base::Unretained(this)),
940        base::Bind(&LoopbackProbeJob::OnProbeComplete, base::Owned(this)),
941        kIsSlow);
942  }
943
944  virtual ~LoopbackProbeJob() {}
945
946 private:
947  // Runs on worker thread.
948  void DoProbe() {
949    result_ = HaveOnlyLoopbackAddresses();
950  }
951
952  void OnProbeComplete() {
953    if (!resolver_.get())
954      return;
955    resolver_->SetHaveOnlyLoopbackAddresses(result_);
956  }
957
958  // Used/set only on origin thread.
959  base::WeakPtr<HostResolverImpl> resolver_;
960
961  bool result_;
962
963  DISALLOW_COPY_AND_ASSIGN(LoopbackProbeJob);
964};
965
966//-----------------------------------------------------------------------------
967
968// Resolves the hostname using DnsTransaction.
969// TODO(szym): This could be moved to separate source file as well.
970class HostResolverImpl::DnsTask : public base::SupportsWeakPtr<DnsTask> {
971 public:
972  class Delegate {
973   public:
974    virtual void OnDnsTaskComplete(base::TimeTicks start_time,
975                                   int net_error,
976                                   const AddressList& addr_list,
977                                   base::TimeDelta ttl) = 0;
978
979    // Called when the first of two jobs succeeds.  If the first completed
980    // transaction fails, this is not called.  Also not called when the DnsTask
981    // only needs to run one transaction.
982    virtual void OnFirstDnsTransactionComplete() = 0;
983
984   protected:
985    Delegate() {}
986    virtual ~Delegate() {}
987  };
988
989  DnsTask(DnsClient* client,
990          const Key& key,
991          Delegate* delegate,
992          const BoundNetLog& job_net_log)
993      : client_(client),
994        key_(key),
995        delegate_(delegate),
996        net_log_(job_net_log),
997        num_completed_transactions_(0),
998        task_start_time_(base::TimeTicks::Now()) {
999    DCHECK(client);
1000    DCHECK(delegate_);
1001  }
1002
1003  bool needs_two_transactions() const {
1004    return key_.address_family == ADDRESS_FAMILY_UNSPECIFIED;
1005  }
1006
1007  bool needs_another_transaction() const {
1008    return needs_two_transactions() && !transaction_aaaa_;
1009  }
1010
1011  void StartFirstTransaction() {
1012    DCHECK_EQ(0u, num_completed_transactions_);
1013    net_log_.BeginEvent(NetLog::TYPE_HOST_RESOLVER_IMPL_DNS_TASK);
1014    if (key_.address_family == ADDRESS_FAMILY_IPV6) {
1015      StartAAAA();
1016    } else {
1017      StartA();
1018    }
1019  }
1020
1021  void StartSecondTransaction() {
1022    DCHECK(needs_two_transactions());
1023    StartAAAA();
1024  }
1025
1026 private:
1027  void StartA() {
1028    DCHECK(!transaction_a_);
1029    DCHECK_NE(ADDRESS_FAMILY_IPV6, key_.address_family);
1030    transaction_a_ = CreateTransaction(ADDRESS_FAMILY_IPV4);
1031    transaction_a_->Start();
1032  }
1033
1034  void StartAAAA() {
1035    DCHECK(!transaction_aaaa_);
1036    DCHECK_NE(ADDRESS_FAMILY_IPV4, key_.address_family);
1037    transaction_aaaa_ = CreateTransaction(ADDRESS_FAMILY_IPV6);
1038    transaction_aaaa_->Start();
1039  }
1040
1041  scoped_ptr<DnsTransaction> CreateTransaction(AddressFamily family) {
1042    DCHECK_NE(ADDRESS_FAMILY_UNSPECIFIED, family);
1043    return client_->GetTransactionFactory()->CreateTransaction(
1044        key_.hostname,
1045        family == ADDRESS_FAMILY_IPV6 ? dns_protocol::kTypeAAAA :
1046                                        dns_protocol::kTypeA,
1047        base::Bind(&DnsTask::OnTransactionComplete, base::Unretained(this),
1048                   base::TimeTicks::Now()),
1049        net_log_);
1050  }
1051
1052  void OnTransactionComplete(const base::TimeTicks& start_time,
1053                             DnsTransaction* transaction,
1054                             int net_error,
1055                             const DnsResponse* response) {
1056    DCHECK(transaction);
1057    base::TimeDelta duration = base::TimeTicks::Now() - start_time;
1058    if (net_error != OK) {
1059      DNS_HISTOGRAM("AsyncDNS.TransactionFailure", duration);
1060      OnFailure(net_error, DnsResponse::DNS_PARSE_OK);
1061      return;
1062    }
1063
1064    DNS_HISTOGRAM("AsyncDNS.TransactionSuccess", duration);
1065    switch (transaction->GetType()) {
1066      case dns_protocol::kTypeA:
1067        DNS_HISTOGRAM("AsyncDNS.TransactionSuccess_A", duration);
1068        break;
1069      case dns_protocol::kTypeAAAA:
1070        DNS_HISTOGRAM("AsyncDNS.TransactionSuccess_AAAA", duration);
1071        break;
1072    }
1073
1074    AddressList addr_list;
1075    base::TimeDelta ttl;
1076    DnsResponse::Result result = response->ParseToAddressList(&addr_list, &ttl);
1077    UMA_HISTOGRAM_ENUMERATION("AsyncDNS.ParseToAddressList",
1078                              result,
1079                              DnsResponse::DNS_PARSE_RESULT_MAX);
1080    if (result != DnsResponse::DNS_PARSE_OK) {
1081      // Fail even if the other query succeeds.
1082      OnFailure(ERR_DNS_MALFORMED_RESPONSE, result);
1083      return;
1084    }
1085
1086    ++num_completed_transactions_;
1087    if (num_completed_transactions_ == 1) {
1088      ttl_ = ttl;
1089    } else {
1090      ttl_ = std::min(ttl_, ttl);
1091    }
1092
1093    if (transaction->GetType() == dns_protocol::kTypeA) {
1094      DCHECK_EQ(transaction_a_.get(), transaction);
1095      // Place IPv4 addresses after IPv6.
1096      addr_list_.insert(addr_list_.end(), addr_list.begin(), addr_list.end());
1097    } else {
1098      DCHECK_EQ(transaction_aaaa_.get(), transaction);
1099      // Place IPv6 addresses before IPv4.
1100      addr_list_.insert(addr_list_.begin(), addr_list.begin(), addr_list.end());
1101    }
1102
1103    if (needs_two_transactions() && num_completed_transactions_ == 1) {
1104      // No need to repeat the suffix search.
1105      key_.hostname = transaction->GetHostname();
1106      delegate_->OnFirstDnsTransactionComplete();
1107      return;
1108    }
1109
1110    if (addr_list_.empty()) {
1111      // TODO(szym): Don't fallback to ProcTask in this case.
1112      OnFailure(ERR_NAME_NOT_RESOLVED, DnsResponse::DNS_PARSE_OK);
1113      return;
1114    }
1115
1116    // If there are multiple addresses, and at least one is IPv6, need to sort
1117    // them.  Note that IPv6 addresses are always put before IPv4 ones, so it's
1118    // sufficient to just check the family of the first address.
1119    if (addr_list_.size() > 1 &&
1120        addr_list_[0].GetFamily() == ADDRESS_FAMILY_IPV6) {
1121      // Sort addresses if needed.  Sort could complete synchronously.
1122      client_->GetAddressSorter()->Sort(
1123          addr_list_,
1124          base::Bind(&DnsTask::OnSortComplete,
1125                     AsWeakPtr(),
1126                     base::TimeTicks::Now()));
1127    } else {
1128      OnSuccess(addr_list_);
1129    }
1130  }
1131
1132  void OnSortComplete(base::TimeTicks start_time,
1133                      bool success,
1134                      const AddressList& addr_list) {
1135    if (!success) {
1136      DNS_HISTOGRAM("AsyncDNS.SortFailure",
1137                    base::TimeTicks::Now() - start_time);
1138      OnFailure(ERR_DNS_SORT_ERROR, DnsResponse::DNS_PARSE_OK);
1139      return;
1140    }
1141
1142    DNS_HISTOGRAM("AsyncDNS.SortSuccess",
1143                  base::TimeTicks::Now() - start_time);
1144
1145    // AddressSorter prunes unusable destinations.
1146    if (addr_list.empty()) {
1147      LOG(WARNING) << "Address list empty after RFC3484 sort";
1148      OnFailure(ERR_NAME_NOT_RESOLVED, DnsResponse::DNS_PARSE_OK);
1149      return;
1150    }
1151
1152    OnSuccess(addr_list);
1153  }
1154
1155  void OnFailure(int net_error, DnsResponse::Result result) {
1156    DCHECK_NE(OK, net_error);
1157    net_log_.EndEvent(
1158        NetLog::TYPE_HOST_RESOLVER_IMPL_DNS_TASK,
1159        base::Bind(&NetLogDnsTaskFailedCallback, net_error, result));
1160    delegate_->OnDnsTaskComplete(task_start_time_, net_error, AddressList(),
1161                                 base::TimeDelta());
1162  }
1163
1164  void OnSuccess(const AddressList& addr_list) {
1165    net_log_.EndEvent(NetLog::TYPE_HOST_RESOLVER_IMPL_DNS_TASK,
1166                      addr_list.CreateNetLogCallback());
1167    delegate_->OnDnsTaskComplete(task_start_time_, OK, addr_list, ttl_);
1168  }
1169
1170  DnsClient* client_;
1171  Key key_;
1172
1173  // The listener to the results of this DnsTask.
1174  Delegate* delegate_;
1175  const BoundNetLog net_log_;
1176
1177  scoped_ptr<DnsTransaction> transaction_a_;
1178  scoped_ptr<DnsTransaction> transaction_aaaa_;
1179
1180  unsigned num_completed_transactions_;
1181
1182  // These are updated as each transaction completes.
1183  base::TimeDelta ttl_;
1184  // IPv6 addresses must appear first in the list.
1185  AddressList addr_list_;
1186
1187  base::TimeTicks task_start_time_;
1188
1189  DISALLOW_COPY_AND_ASSIGN(DnsTask);
1190};
1191
1192//-----------------------------------------------------------------------------
1193
1194// Aggregates all Requests for the same Key. Dispatched via PriorityDispatch.
1195class HostResolverImpl::Job : public PrioritizedDispatcher::Job,
1196                              public HostResolverImpl::DnsTask::Delegate {
1197 public:
1198  // Creates new job for |key| where |request_net_log| is bound to the
1199  // request that spawned it.
1200  Job(const base::WeakPtr<HostResolverImpl>& resolver,
1201      const Key& key,
1202      RequestPriority priority,
1203      const BoundNetLog& request_net_log)
1204      : resolver_(resolver),
1205        key_(key),
1206        priority_tracker_(priority),
1207        had_non_speculative_request_(false),
1208        had_dns_config_(false),
1209        num_occupied_job_slots_(0),
1210        dns_task_error_(OK),
1211        creation_time_(base::TimeTicks::Now()),
1212        priority_change_time_(creation_time_),
1213        net_log_(BoundNetLog::Make(request_net_log.net_log(),
1214                                   NetLog::SOURCE_HOST_RESOLVER_IMPL_JOB)) {
1215    request_net_log.AddEvent(NetLog::TYPE_HOST_RESOLVER_IMPL_CREATE_JOB);
1216
1217    net_log_.BeginEvent(
1218        NetLog::TYPE_HOST_RESOLVER_IMPL_JOB,
1219        base::Bind(&NetLogJobCreationCallback,
1220                   request_net_log.source(),
1221                   &key_.hostname));
1222  }
1223
1224  virtual ~Job() {
1225    if (is_running()) {
1226      // |resolver_| was destroyed with this Job still in flight.
1227      // Clean-up, record in the log, but don't run any callbacks.
1228      if (is_proc_running()) {
1229        proc_task_->Cancel();
1230        proc_task_ = NULL;
1231      }
1232      // Clean up now for nice NetLog.
1233      KillDnsTask();
1234      net_log_.EndEventWithNetErrorCode(NetLog::TYPE_HOST_RESOLVER_IMPL_JOB,
1235                                        ERR_ABORTED);
1236    } else if (is_queued()) {
1237      // |resolver_| was destroyed without running this Job.
1238      // TODO(szym): is there any benefit in having this distinction?
1239      net_log_.AddEvent(NetLog::TYPE_CANCELLED);
1240      net_log_.EndEvent(NetLog::TYPE_HOST_RESOLVER_IMPL_JOB);
1241    }
1242    // else CompleteRequests logged EndEvent.
1243
1244    // Log any remaining Requests as cancelled.
1245    for (RequestsList::const_iterator it = requests_.begin();
1246         it != requests_.end(); ++it) {
1247      Request* req = *it;
1248      if (req->was_canceled())
1249        continue;
1250      DCHECK_EQ(this, req->job());
1251      LogCancelRequest(req->source_net_log(), req->request_net_log(),
1252                       req->info());
1253    }
1254  }
1255
1256  // Add this job to the dispatcher.  If "at_head" is true, adds at the front
1257  // of the queue.
1258  void Schedule(bool at_head) {
1259    DCHECK(!is_queued());
1260    PrioritizedDispatcher::Handle handle;
1261    if (!at_head) {
1262      handle = resolver_->dispatcher_->Add(this, priority());
1263    } else {
1264      handle = resolver_->dispatcher_->AddAtHead(this, priority());
1265    }
1266    // The dispatcher could have started |this| in the above call to Add, which
1267    // could have called Schedule again. In that case |handle| will be null,
1268    // but |handle_| may have been set by the other nested call to Schedule.
1269    if (!handle.is_null()) {
1270      DCHECK(handle_.is_null());
1271      handle_ = handle;
1272    }
1273  }
1274
1275  void AddRequest(scoped_ptr<Request> req) {
1276    DCHECK_EQ(key_.hostname, req->info().hostname());
1277
1278    req->set_job(this);
1279    priority_tracker_.Add(req->priority());
1280
1281    req->request_net_log().AddEvent(
1282        NetLog::TYPE_HOST_RESOLVER_IMPL_JOB_ATTACH,
1283        net_log_.source().ToEventParametersCallback());
1284
1285    net_log_.AddEvent(
1286        NetLog::TYPE_HOST_RESOLVER_IMPL_JOB_REQUEST_ATTACH,
1287        base::Bind(&NetLogJobAttachCallback,
1288                   req->request_net_log().source(),
1289                   priority()));
1290
1291    // TODO(szym): Check if this is still needed.
1292    if (!req->info().is_speculative()) {
1293      had_non_speculative_request_ = true;
1294      if (proc_task_.get())
1295        proc_task_->set_had_non_speculative_request();
1296    }
1297
1298    requests_.push_back(req.release());
1299
1300    UpdatePriority();
1301  }
1302
1303  // Marks |req| as cancelled. If it was the last active Request, also finishes
1304  // this Job, marking it as cancelled, and deletes it.
1305  void CancelRequest(Request* req) {
1306    DCHECK_EQ(key_.hostname, req->info().hostname());
1307    DCHECK(!req->was_canceled());
1308
1309    // Don't remove it from |requests_| just mark it canceled.
1310    req->MarkAsCanceled();
1311    LogCancelRequest(req->source_net_log(), req->request_net_log(),
1312                     req->info());
1313
1314    priority_tracker_.Remove(req->priority());
1315    net_log_.AddEvent(NetLog::TYPE_HOST_RESOLVER_IMPL_JOB_REQUEST_DETACH,
1316                      base::Bind(&NetLogJobAttachCallback,
1317                                 req->request_net_log().source(),
1318                                 priority()));
1319
1320    if (num_active_requests() > 0) {
1321      UpdatePriority();
1322    } else {
1323      // If we were called from a Request's callback within CompleteRequests,
1324      // that Request could not have been cancelled, so num_active_requests()
1325      // could not be 0. Therefore, we are not in CompleteRequests().
1326      CompleteRequestsWithError(OK /* cancelled */);
1327    }
1328  }
1329
1330  // Called from AbortAllInProgressJobs. Completes all requests and destroys
1331  // the job. This currently assumes the abort is due to a network change.
1332  void Abort() {
1333    DCHECK(is_running());
1334    CompleteRequestsWithError(ERR_NETWORK_CHANGED);
1335  }
1336
1337  // If DnsTask present, abort it and fall back to ProcTask.
1338  void AbortDnsTask() {
1339    if (dns_task_) {
1340      KillDnsTask();
1341      dns_task_error_ = OK;
1342      StartProcTask();
1343    }
1344  }
1345
1346  // Called by HostResolverImpl when this job is evicted due to queue overflow.
1347  // Completes all requests and destroys the job.
1348  void OnEvicted() {
1349    DCHECK(!is_running());
1350    DCHECK(is_queued());
1351    handle_.Reset();
1352
1353    net_log_.AddEvent(NetLog::TYPE_HOST_RESOLVER_IMPL_JOB_EVICTED);
1354
1355    // This signals to CompleteRequests that this job never ran.
1356    CompleteRequestsWithError(ERR_HOST_RESOLVER_QUEUE_TOO_LARGE);
1357  }
1358
1359  // Attempts to serve the job from HOSTS. Returns true if succeeded and
1360  // this Job was destroyed.
1361  bool ServeFromHosts() {
1362    DCHECK_GT(num_active_requests(), 0u);
1363    AddressList addr_list;
1364    if (resolver_->ServeFromHosts(key(),
1365                                  requests_.front()->info(),
1366                                  &addr_list)) {
1367      // This will destroy the Job.
1368      CompleteRequests(
1369          HostCache::Entry(OK, MakeAddressListForRequest(addr_list)),
1370          base::TimeDelta());
1371      return true;
1372    }
1373    return false;
1374  }
1375
1376  const Key key() const {
1377    return key_;
1378  }
1379
1380  bool is_queued() const {
1381    return !handle_.is_null();
1382  }
1383
1384  bool is_running() const {
1385    return is_dns_running() || is_proc_running();
1386  }
1387
1388 private:
1389  void KillDnsTask() {
1390    if (dns_task_) {
1391      ReduceToOneJobSlot();
1392      dns_task_.reset();
1393    }
1394  }
1395
1396  // Reduce the number of job slots occupied and queued in the dispatcher
1397  // to one. If the second Job slot is queued in the dispatcher, cancels the
1398  // queued job. Otherwise, the second Job has been started by the
1399  // PrioritizedDispatcher, so signals it is complete.
1400  void ReduceToOneJobSlot() {
1401    DCHECK_GE(num_occupied_job_slots_, 1u);
1402    if (is_queued()) {
1403      resolver_->dispatcher_->Cancel(handle_);
1404      handle_.Reset();
1405    } else if (num_occupied_job_slots_ > 1) {
1406      resolver_->dispatcher_->OnJobFinished();
1407      --num_occupied_job_slots_;
1408    }
1409    DCHECK_EQ(1u, num_occupied_job_slots_);
1410  }
1411
1412  void UpdatePriority() {
1413    if (is_queued()) {
1414      if (priority() != static_cast<RequestPriority>(handle_.priority()))
1415        priority_change_time_ = base::TimeTicks::Now();
1416      handle_ = resolver_->dispatcher_->ChangePriority(handle_, priority());
1417    }
1418  }
1419
1420  AddressList MakeAddressListForRequest(const AddressList& list) const {
1421    if (requests_.empty())
1422      return list;
1423    return AddressList::CopyWithPort(list, requests_.front()->info().port());
1424  }
1425
1426  // PriorityDispatch::Job:
1427  virtual void Start() OVERRIDE {
1428    DCHECK_LE(num_occupied_job_slots_, 1u);
1429
1430    handle_.Reset();
1431    ++num_occupied_job_slots_;
1432
1433    if (num_occupied_job_slots_ == 2) {
1434      StartSecondDnsTransaction();
1435      return;
1436    }
1437
1438    DCHECK(!is_running());
1439
1440    net_log_.AddEvent(NetLog::TYPE_HOST_RESOLVER_IMPL_JOB_STARTED);
1441
1442    had_dns_config_ = resolver_->HaveDnsConfig();
1443
1444    base::TimeTicks now = base::TimeTicks::Now();
1445    base::TimeDelta queue_time = now - creation_time_;
1446    base::TimeDelta queue_time_after_change = now - priority_change_time_;
1447
1448    if (had_dns_config_) {
1449      DNS_HISTOGRAM_BY_PRIORITY("AsyncDNS.JobQueueTime", priority(),
1450                                queue_time);
1451      DNS_HISTOGRAM_BY_PRIORITY("AsyncDNS.JobQueueTimeAfterChange", priority(),
1452                                queue_time_after_change);
1453    } else {
1454      DNS_HISTOGRAM_BY_PRIORITY("DNS.JobQueueTime", priority(), queue_time);
1455      DNS_HISTOGRAM_BY_PRIORITY("DNS.JobQueueTimeAfterChange", priority(),
1456                                queue_time_after_change);
1457    }
1458
1459    bool system_only =
1460        (key_.host_resolver_flags & HOST_RESOLVER_SYSTEM_ONLY) != 0;
1461
1462    // Caution: Job::Start must not complete synchronously.
1463    if (!system_only && had_dns_config_ &&
1464        !ResemblesMulticastDNSName(key_.hostname)) {
1465      StartDnsTask();
1466    } else {
1467      StartProcTask();
1468    }
1469  }
1470
1471  // TODO(szym): Since DnsTransaction does not consume threads, we can increase
1472  // the limits on |dispatcher_|. But in order to keep the number of WorkerPool
1473  // threads low, we will need to use an "inner" PrioritizedDispatcher with
1474  // tighter limits.
1475  void StartProcTask() {
1476    DCHECK(!is_dns_running());
1477    proc_task_ = new ProcTask(
1478        key_,
1479        resolver_->proc_params_,
1480        base::Bind(&Job::OnProcTaskComplete, base::Unretained(this),
1481                   base::TimeTicks::Now()),
1482        net_log_);
1483
1484    if (had_non_speculative_request_)
1485      proc_task_->set_had_non_speculative_request();
1486    // Start() could be called from within Resolve(), hence it must NOT directly
1487    // call OnProcTaskComplete, for example, on synchronous failure.
1488    proc_task_->Start();
1489  }
1490
1491  // Called by ProcTask when it completes.
1492  void OnProcTaskComplete(base::TimeTicks start_time,
1493                          int net_error,
1494                          const AddressList& addr_list) {
1495    DCHECK(is_proc_running());
1496
1497    if (!resolver_->resolved_known_ipv6_hostname_ &&
1498        net_error == OK &&
1499        key_.address_family == ADDRESS_FAMILY_UNSPECIFIED) {
1500      if (key_.hostname == "www.google.com") {
1501        resolver_->resolved_known_ipv6_hostname_ = true;
1502        bool got_ipv6_address = false;
1503        for (size_t i = 0; i < addr_list.size(); ++i) {
1504          if (addr_list[i].GetFamily() == ADDRESS_FAMILY_IPV6) {
1505            got_ipv6_address = true;
1506            break;
1507          }
1508        }
1509        UMA_HISTOGRAM_BOOLEAN("Net.UnspecResolvedIPv6", got_ipv6_address);
1510      }
1511    }
1512
1513    if (dns_task_error_ != OK) {
1514      base::TimeDelta duration = base::TimeTicks::Now() - start_time;
1515      if (net_error == OK) {
1516        DNS_HISTOGRAM("AsyncDNS.FallbackSuccess", duration);
1517        if ((dns_task_error_ == ERR_NAME_NOT_RESOLVED) &&
1518            ResemblesNetBIOSName(key_.hostname)) {
1519          UmaAsyncDnsResolveStatus(RESOLVE_STATUS_SUSPECT_NETBIOS);
1520        } else {
1521          UmaAsyncDnsResolveStatus(RESOLVE_STATUS_PROC_SUCCESS);
1522        }
1523        UMA_HISTOGRAM_CUSTOM_ENUMERATION("AsyncDNS.ResolveError",
1524                                         std::abs(dns_task_error_),
1525                                         GetAllErrorCodesForUma());
1526        resolver_->OnDnsTaskResolve(dns_task_error_);
1527      } else {
1528        DNS_HISTOGRAM("AsyncDNS.FallbackFail", duration);
1529        UmaAsyncDnsResolveStatus(RESOLVE_STATUS_FAIL);
1530      }
1531    }
1532
1533    base::TimeDelta ttl =
1534        base::TimeDelta::FromSeconds(kNegativeCacheEntryTTLSeconds);
1535    if (net_error == OK)
1536      ttl = base::TimeDelta::FromSeconds(kCacheEntryTTLSeconds);
1537
1538    // Don't store the |ttl| in cache since it's not obtained from the server.
1539    CompleteRequests(
1540        HostCache::Entry(net_error, MakeAddressListForRequest(addr_list)),
1541        ttl);
1542  }
1543
1544  void StartDnsTask() {
1545    DCHECK(resolver_->HaveDnsConfig());
1546    dns_task_.reset(new DnsTask(resolver_->dns_client_.get(), key_, this,
1547                                net_log_));
1548
1549    dns_task_->StartFirstTransaction();
1550    // Schedule a second transaction, if needed.
1551    if (dns_task_->needs_two_transactions())
1552      Schedule(true);
1553  }
1554
1555  void StartSecondDnsTransaction() {
1556    DCHECK(dns_task_->needs_two_transactions());
1557    dns_task_->StartSecondTransaction();
1558  }
1559
1560  // Called if DnsTask fails. It is posted from StartDnsTask, so Job may be
1561  // deleted before this callback. In this case dns_task is deleted as well,
1562  // so we use it as indicator whether Job is still valid.
1563  void OnDnsTaskFailure(const base::WeakPtr<DnsTask>& dns_task,
1564                        base::TimeDelta duration,
1565                        int net_error) {
1566    DNS_HISTOGRAM("AsyncDNS.ResolveFail", duration);
1567
1568    if (dns_task == NULL)
1569      return;
1570
1571    dns_task_error_ = net_error;
1572
1573    // TODO(szym): Run ServeFromHosts now if nsswitch.conf says so.
1574    // http://crbug.com/117655
1575
1576    // TODO(szym): Some net errors indicate lack of connectivity. Starting
1577    // ProcTask in that case is a waste of time.
1578    if (resolver_->fallback_to_proctask_) {
1579      KillDnsTask();
1580      StartProcTask();
1581    } else {
1582      UmaAsyncDnsResolveStatus(RESOLVE_STATUS_FAIL);
1583      CompleteRequestsWithError(net_error);
1584    }
1585  }
1586
1587
1588  // HostResolverImpl::DnsTask::Delegate implementation:
1589
1590  virtual void OnDnsTaskComplete(base::TimeTicks start_time,
1591                                 int net_error,
1592                                 const AddressList& addr_list,
1593                                 base::TimeDelta ttl) OVERRIDE {
1594    DCHECK(is_dns_running());
1595
1596    base::TimeDelta duration = base::TimeTicks::Now() - start_time;
1597    if (net_error != OK) {
1598      OnDnsTaskFailure(dns_task_->AsWeakPtr(), duration, net_error);
1599      return;
1600    }
1601    DNS_HISTOGRAM("AsyncDNS.ResolveSuccess", duration);
1602    // Log DNS lookups based on |address_family|.
1603    switch(key_.address_family) {
1604      case ADDRESS_FAMILY_IPV4:
1605        DNS_HISTOGRAM("AsyncDNS.ResolveSuccess_FAMILY_IPV4", duration);
1606        break;
1607      case ADDRESS_FAMILY_IPV6:
1608        DNS_HISTOGRAM("AsyncDNS.ResolveSuccess_FAMILY_IPV6", duration);
1609        break;
1610      case ADDRESS_FAMILY_UNSPECIFIED:
1611        DNS_HISTOGRAM("AsyncDNS.ResolveSuccess_FAMILY_UNSPEC", duration);
1612        break;
1613    }
1614
1615    UmaAsyncDnsResolveStatus(RESOLVE_STATUS_DNS_SUCCESS);
1616    RecordTTL(ttl);
1617
1618    resolver_->OnDnsTaskResolve(OK);
1619
1620    base::TimeDelta bounded_ttl =
1621        std::max(ttl, base::TimeDelta::FromSeconds(kMinimumTTLSeconds));
1622
1623    CompleteRequests(
1624        HostCache::Entry(net_error, MakeAddressListForRequest(addr_list), ttl),
1625        bounded_ttl);
1626  }
1627
1628  virtual void OnFirstDnsTransactionComplete() OVERRIDE {
1629    DCHECK(dns_task_->needs_two_transactions());
1630    DCHECK_EQ(dns_task_->needs_another_transaction(), is_queued());
1631    // No longer need to occupy two dispatcher slots.
1632    ReduceToOneJobSlot();
1633
1634    // We already have a job slot at the dispatcher, so if the second
1635    // transaction hasn't started, reuse it now instead of waiting in the queue
1636    // for the second slot.
1637    if (dns_task_->needs_another_transaction())
1638      dns_task_->StartSecondTransaction();
1639  }
1640
1641  // Performs Job's last rites. Completes all Requests. Deletes this.
1642  void CompleteRequests(const HostCache::Entry& entry,
1643                        base::TimeDelta ttl) {
1644    CHECK(resolver_.get());
1645
1646    // This job must be removed from resolver's |jobs_| now to make room for a
1647    // new job with the same key in case one of the OnComplete callbacks decides
1648    // to spawn one. Consequently, the job deletes itself when CompleteRequests
1649    // is done.
1650    scoped_ptr<Job> self_deleter(this);
1651
1652    resolver_->RemoveJob(this);
1653
1654    if (is_running()) {
1655      if (is_proc_running()) {
1656        DCHECK(!is_queued());
1657        proc_task_->Cancel();
1658        proc_task_ = NULL;
1659      }
1660      KillDnsTask();
1661
1662      // Signal dispatcher that a slot has opened.
1663      resolver_->dispatcher_->OnJobFinished();
1664    } else if (is_queued()) {
1665      resolver_->dispatcher_->Cancel(handle_);
1666      handle_.Reset();
1667    }
1668
1669    if (num_active_requests() == 0) {
1670      net_log_.AddEvent(NetLog::TYPE_CANCELLED);
1671      net_log_.EndEventWithNetErrorCode(NetLog::TYPE_HOST_RESOLVER_IMPL_JOB,
1672                                        OK);
1673      return;
1674    }
1675
1676    net_log_.EndEventWithNetErrorCode(NetLog::TYPE_HOST_RESOLVER_IMPL_JOB,
1677                                      entry.error);
1678
1679    DCHECK(!requests_.empty());
1680
1681    if (entry.error == OK) {
1682      // Record this histogram here, when we know the system has a valid DNS
1683      // configuration.
1684      UMA_HISTOGRAM_BOOLEAN("AsyncDNS.HaveDnsConfig",
1685                            resolver_->received_dns_config_);
1686    }
1687
1688    bool did_complete = (entry.error != ERR_NETWORK_CHANGED) &&
1689                        (entry.error != ERR_HOST_RESOLVER_QUEUE_TOO_LARGE);
1690    if (did_complete)
1691      resolver_->CacheResult(key_, entry, ttl);
1692
1693    // Complete all of the requests that were attached to the job.
1694    for (RequestsList::const_iterator it = requests_.begin();
1695         it != requests_.end(); ++it) {
1696      Request* req = *it;
1697
1698      if (req->was_canceled())
1699        continue;
1700
1701      DCHECK_EQ(this, req->job());
1702      // Update the net log and notify registered observers.
1703      LogFinishRequest(req->source_net_log(), req->request_net_log(),
1704                       req->info(), entry.error);
1705      if (did_complete) {
1706        // Record effective total time from creation to completion.
1707        RecordTotalTime(had_dns_config_, req->info().is_speculative(),
1708                        base::TimeTicks::Now() - req->request_time());
1709      }
1710      req->OnComplete(entry.error, entry.addrlist);
1711
1712      // Check if the resolver was destroyed as a result of running the
1713      // callback. If it was, we could continue, but we choose to bail.
1714      if (!resolver_.get())
1715        return;
1716    }
1717  }
1718
1719  // Convenience wrapper for CompleteRequests in case of failure.
1720  void CompleteRequestsWithError(int net_error) {
1721    CompleteRequests(HostCache::Entry(net_error, AddressList()),
1722                     base::TimeDelta());
1723  }
1724
1725  RequestPriority priority() const {
1726    return priority_tracker_.highest_priority();
1727  }
1728
1729  // Number of non-canceled requests in |requests_|.
1730  size_t num_active_requests() const {
1731    return priority_tracker_.total_count();
1732  }
1733
1734  bool is_dns_running() const {
1735    return dns_task_.get() != NULL;
1736  }
1737
1738  bool is_proc_running() const {
1739    return proc_task_.get() != NULL;
1740  }
1741
1742  base::WeakPtr<HostResolverImpl> resolver_;
1743
1744  Key key_;
1745
1746  // Tracks the highest priority across |requests_|.
1747  PriorityTracker priority_tracker_;
1748
1749  bool had_non_speculative_request_;
1750
1751  // Distinguishes measurements taken while DnsClient was fully configured.
1752  bool had_dns_config_;
1753
1754  // Number of slots occupied by this Job in resolver's PrioritizedDispatcher.
1755  unsigned num_occupied_job_slots_;
1756
1757  // Result of DnsTask.
1758  int dns_task_error_;
1759
1760  const base::TimeTicks creation_time_;
1761  base::TimeTicks priority_change_time_;
1762
1763  BoundNetLog net_log_;
1764
1765  // Resolves the host using a HostResolverProc.
1766  scoped_refptr<ProcTask> proc_task_;
1767
1768  // Resolves the host using a DnsTransaction.
1769  scoped_ptr<DnsTask> dns_task_;
1770
1771  // All Requests waiting for the result of this Job. Some can be canceled.
1772  RequestsList requests_;
1773
1774  // A handle used in |HostResolverImpl::dispatcher_|.
1775  PrioritizedDispatcher::Handle handle_;
1776};
1777
1778//-----------------------------------------------------------------------------
1779
1780HostResolverImpl::ProcTaskParams::ProcTaskParams(
1781    HostResolverProc* resolver_proc,
1782    size_t max_retry_attempts)
1783    : resolver_proc(resolver_proc),
1784      max_retry_attempts(max_retry_attempts),
1785      unresponsive_delay(base::TimeDelta::FromMilliseconds(6000)),
1786      retry_factor(2) {
1787  // Maximum of 4 retry attempts for host resolution.
1788  static const size_t kDefaultMaxRetryAttempts = 4u;
1789  if (max_retry_attempts == HostResolver::kDefaultRetryAttempts)
1790    max_retry_attempts = kDefaultMaxRetryAttempts;
1791}
1792
1793HostResolverImpl::ProcTaskParams::~ProcTaskParams() {}
1794
1795HostResolverImpl::HostResolverImpl(const Options& options, NetLog* net_log)
1796    : max_queued_jobs_(0),
1797      proc_params_(NULL, options.max_retry_attempts),
1798      net_log_(net_log),
1799      default_address_family_(ADDRESS_FAMILY_UNSPECIFIED),
1800      received_dns_config_(false),
1801      num_dns_failures_(0),
1802      probe_ipv6_support_(true),
1803      use_local_ipv6_(false),
1804      resolved_known_ipv6_hostname_(false),
1805      additional_resolver_flags_(0),
1806      fallback_to_proctask_(true),
1807      weak_ptr_factory_(this),
1808      probe_weak_ptr_factory_(this) {
1809  if (options.enable_caching)
1810    cache_ = HostCache::CreateDefaultCache();
1811
1812  PrioritizedDispatcher::Limits job_limits = options.GetDispatcherLimits();
1813  dispatcher_.reset(new PrioritizedDispatcher(job_limits));
1814  max_queued_jobs_ = job_limits.total_jobs * 100u;
1815
1816  DCHECK_GE(dispatcher_->num_priorities(), static_cast<size_t>(NUM_PRIORITIES));
1817
1818#if defined(OS_WIN)
1819  EnsureWinsockInit();
1820#endif
1821#if defined(OS_POSIX) && !defined(OS_MACOSX) && !defined(OS_ANDROID)
1822  new LoopbackProbeJob(weak_ptr_factory_.GetWeakPtr());
1823#endif
1824  NetworkChangeNotifier::AddIPAddressObserver(this);
1825  NetworkChangeNotifier::AddDNSObserver(this);
1826#if defined(OS_POSIX) && !defined(OS_MACOSX) && !defined(OS_OPENBSD) && \
1827    !defined(OS_ANDROID)
1828  EnsureDnsReloaderInit();
1829#endif
1830
1831  {
1832    DnsConfig dns_config;
1833    NetworkChangeNotifier::GetDnsConfig(&dns_config);
1834    received_dns_config_ = dns_config.IsValid();
1835    // Conservatively assume local IPv6 is needed when DnsConfig is not valid.
1836    use_local_ipv6_ = !dns_config.IsValid() || dns_config.use_local_ipv6;
1837  }
1838
1839  fallback_to_proctask_ = !ConfigureAsyncDnsNoFallbackFieldTrial();
1840}
1841
1842HostResolverImpl::~HostResolverImpl() {
1843  // Prevent the dispatcher from starting new jobs.
1844  dispatcher_->SetLimitsToZero();
1845  // It's now safe for Jobs to call KillDsnTask on destruction, because
1846  // OnJobComplete will not start any new jobs.
1847  STLDeleteValues(&jobs_);
1848
1849  NetworkChangeNotifier::RemoveIPAddressObserver(this);
1850  NetworkChangeNotifier::RemoveDNSObserver(this);
1851}
1852
1853void HostResolverImpl::SetMaxQueuedJobs(size_t value) {
1854  DCHECK_EQ(0u, dispatcher_->num_queued_jobs());
1855  DCHECK_GT(value, 0u);
1856  max_queued_jobs_ = value;
1857}
1858
1859int HostResolverImpl::Resolve(const RequestInfo& info,
1860                              RequestPriority priority,
1861                              AddressList* addresses,
1862                              const CompletionCallback& callback,
1863                              RequestHandle* out_req,
1864                              const BoundNetLog& source_net_log) {
1865  DCHECK(addresses);
1866  DCHECK(CalledOnValidThread());
1867  DCHECK_EQ(false, callback.is_null());
1868
1869  // Check that the caller supplied a valid hostname to resolve.
1870  std::string labeled_hostname;
1871  if (!DNSDomainFromDot(info.hostname(), &labeled_hostname))
1872    return ERR_NAME_NOT_RESOLVED;
1873
1874  // Make a log item for the request.
1875  BoundNetLog request_net_log = BoundNetLog::Make(net_log_,
1876      NetLog::SOURCE_HOST_RESOLVER_IMPL_REQUEST);
1877
1878  LogStartRequest(source_net_log, request_net_log, info);
1879
1880  // Build a key that identifies the request in the cache and in the
1881  // outstanding jobs map.
1882  Key key = GetEffectiveKeyForRequest(info, request_net_log);
1883
1884  int rv = ResolveHelper(key, info, addresses, request_net_log);
1885  if (rv != ERR_DNS_CACHE_MISS) {
1886    LogFinishRequest(source_net_log, request_net_log, info, rv);
1887    RecordTotalTime(HaveDnsConfig(), info.is_speculative(), base::TimeDelta());
1888    return rv;
1889  }
1890
1891  // Next we need to attach our request to a "job". This job is responsible for
1892  // calling "getaddrinfo(hostname)" on a worker thread.
1893
1894  JobMap::iterator jobit = jobs_.find(key);
1895  Job* job;
1896  if (jobit == jobs_.end()) {
1897    job =
1898        new Job(weak_ptr_factory_.GetWeakPtr(), key, priority, request_net_log);
1899    job->Schedule(false);
1900
1901    // Check for queue overflow.
1902    if (dispatcher_->num_queued_jobs() > max_queued_jobs_) {
1903      Job* evicted = static_cast<Job*>(dispatcher_->EvictOldestLowest());
1904      DCHECK(evicted);
1905      evicted->OnEvicted();  // Deletes |evicted|.
1906      if (evicted == job) {
1907        rv = ERR_HOST_RESOLVER_QUEUE_TOO_LARGE;
1908        LogFinishRequest(source_net_log, request_net_log, info, rv);
1909        return rv;
1910      }
1911    }
1912    jobs_.insert(jobit, std::make_pair(key, job));
1913  } else {
1914    job = jobit->second;
1915  }
1916
1917  // Can't complete synchronously. Create and attach request.
1918  scoped_ptr<Request> req(new Request(
1919      source_net_log, request_net_log, info, priority, callback, addresses));
1920  if (out_req)
1921    *out_req = reinterpret_cast<RequestHandle>(req.get());
1922
1923  job->AddRequest(req.Pass());
1924  // Completion happens during Job::CompleteRequests().
1925  return ERR_IO_PENDING;
1926}
1927
1928int HostResolverImpl::ResolveHelper(const Key& key,
1929                                    const RequestInfo& info,
1930                                    AddressList* addresses,
1931                                    const BoundNetLog& request_net_log) {
1932  // The result of |getaddrinfo| for empty hosts is inconsistent across systems.
1933  // On Windows it gives the default interface's address, whereas on Linux it
1934  // gives an error. We will make it fail on all platforms for consistency.
1935  if (info.hostname().empty() || info.hostname().size() > kMaxHostLength)
1936    return ERR_NAME_NOT_RESOLVED;
1937
1938  int net_error = ERR_UNEXPECTED;
1939  if (ResolveAsIP(key, info, &net_error, addresses))
1940    return net_error;
1941  if (ServeFromCache(key, info, &net_error, addresses)) {
1942    request_net_log.AddEvent(NetLog::TYPE_HOST_RESOLVER_IMPL_CACHE_HIT);
1943    return net_error;
1944  }
1945  // TODO(szym): Do not do this if nsswitch.conf instructs not to.
1946  // http://crbug.com/117655
1947  if (ServeFromHosts(key, info, addresses)) {
1948    request_net_log.AddEvent(NetLog::TYPE_HOST_RESOLVER_IMPL_HOSTS_HIT);
1949    return OK;
1950  }
1951  return ERR_DNS_CACHE_MISS;
1952}
1953
1954int HostResolverImpl::ResolveFromCache(const RequestInfo& info,
1955                                       AddressList* addresses,
1956                                       const BoundNetLog& source_net_log) {
1957  DCHECK(CalledOnValidThread());
1958  DCHECK(addresses);
1959
1960  // Make a log item for the request.
1961  BoundNetLog request_net_log = BoundNetLog::Make(net_log_,
1962      NetLog::SOURCE_HOST_RESOLVER_IMPL_REQUEST);
1963
1964  // Update the net log and notify registered observers.
1965  LogStartRequest(source_net_log, request_net_log, info);
1966
1967  Key key = GetEffectiveKeyForRequest(info, request_net_log);
1968
1969  int rv = ResolveHelper(key, info, addresses, request_net_log);
1970  LogFinishRequest(source_net_log, request_net_log, info, rv);
1971  return rv;
1972}
1973
1974void HostResolverImpl::CancelRequest(RequestHandle req_handle) {
1975  DCHECK(CalledOnValidThread());
1976  Request* req = reinterpret_cast<Request*>(req_handle);
1977  DCHECK(req);
1978  Job* job = req->job();
1979  DCHECK(job);
1980  job->CancelRequest(req);
1981}
1982
1983void HostResolverImpl::SetDefaultAddressFamily(AddressFamily address_family) {
1984  DCHECK(CalledOnValidThread());
1985  default_address_family_ = address_family;
1986  probe_ipv6_support_ = false;
1987}
1988
1989AddressFamily HostResolverImpl::GetDefaultAddressFamily() const {
1990  return default_address_family_;
1991}
1992
1993void HostResolverImpl::SetDnsClientEnabled(bool enabled) {
1994  DCHECK(CalledOnValidThread());
1995#if defined(ENABLE_BUILT_IN_DNS)
1996  if (enabled && !dns_client_) {
1997    SetDnsClient(DnsClient::CreateClient(net_log_));
1998  } else if (!enabled && dns_client_) {
1999    SetDnsClient(scoped_ptr<DnsClient>());
2000  }
2001#endif
2002}
2003
2004HostCache* HostResolverImpl::GetHostCache() {
2005  return cache_.get();
2006}
2007
2008base::Value* HostResolverImpl::GetDnsConfigAsValue() const {
2009  // Check if async DNS is disabled.
2010  if (!dns_client_.get())
2011    return NULL;
2012
2013  // Check if async DNS is enabled, but we currently have no configuration
2014  // for it.
2015  const DnsConfig* dns_config = dns_client_->GetConfig();
2016  if (dns_config == NULL)
2017    return new base::DictionaryValue();
2018
2019  return dns_config->ToValue();
2020}
2021
2022bool HostResolverImpl::ResolveAsIP(const Key& key,
2023                                   const RequestInfo& info,
2024                                   int* net_error,
2025                                   AddressList* addresses) {
2026  DCHECK(addresses);
2027  DCHECK(net_error);
2028  IPAddressNumber ip_number;
2029  if (!ParseIPLiteralToNumber(key.hostname, &ip_number))
2030    return false;
2031
2032  DCHECK_EQ(key.host_resolver_flags &
2033      ~(HOST_RESOLVER_CANONNAME | HOST_RESOLVER_LOOPBACK_ONLY |
2034        HOST_RESOLVER_DEFAULT_FAMILY_SET_DUE_TO_NO_IPV6),
2035            0) << " Unhandled flag";
2036
2037  *net_error = OK;
2038  AddressFamily family = GetAddressFamily(ip_number);
2039  if (family == ADDRESS_FAMILY_IPV6 &&
2040      !probe_ipv6_support_ &&
2041      default_address_family_ == ADDRESS_FAMILY_IPV4) {
2042    // Don't return IPv6 addresses if default address family is set to IPv4,
2043    // and probes are disabled.
2044    *net_error = ERR_NAME_NOT_RESOLVED;
2045  } else if (key.address_family != ADDRESS_FAMILY_UNSPECIFIED &&
2046             key.address_family != family) {
2047    // Don't return IPv6 addresses for IPv4 queries, and vice versa.
2048    *net_error = ERR_NAME_NOT_RESOLVED;
2049  } else {
2050    *addresses = AddressList::CreateFromIPAddress(ip_number, info.port());
2051    if (key.host_resolver_flags & HOST_RESOLVER_CANONNAME)
2052      addresses->SetDefaultCanonicalName();
2053  }
2054  return true;
2055}
2056
2057bool HostResolverImpl::ServeFromCache(const Key& key,
2058                                      const RequestInfo& info,
2059                                      int* net_error,
2060                                      AddressList* addresses) {
2061  DCHECK(addresses);
2062  DCHECK(net_error);
2063  if (!info.allow_cached_response() || !cache_.get())
2064    return false;
2065
2066  const HostCache::Entry* cache_entry = cache_->Lookup(
2067      key, base::TimeTicks::Now());
2068  if (!cache_entry)
2069    return false;
2070
2071  *net_error = cache_entry->error;
2072  if (*net_error == OK) {
2073    if (cache_entry->has_ttl())
2074      RecordTTL(cache_entry->ttl);
2075    *addresses = EnsurePortOnAddressList(cache_entry->addrlist, info.port());
2076  }
2077  return true;
2078}
2079
2080bool HostResolverImpl::ServeFromHosts(const Key& key,
2081                                      const RequestInfo& info,
2082                                      AddressList* addresses) {
2083  DCHECK(addresses);
2084  if (!HaveDnsConfig())
2085    return false;
2086  addresses->clear();
2087
2088  // HOSTS lookups are case-insensitive.
2089  std::string hostname = base::StringToLowerASCII(key.hostname);
2090
2091  const DnsHosts& hosts = dns_client_->GetConfig()->hosts;
2092
2093  // If |address_family| is ADDRESS_FAMILY_UNSPECIFIED other implementations
2094  // (glibc and c-ares) return the first matching line. We have more
2095  // flexibility, but lose implicit ordering.
2096  // We prefer IPv6 because "happy eyeballs" will fall back to IPv4 if
2097  // necessary.
2098  if (key.address_family == ADDRESS_FAMILY_IPV6 ||
2099      key.address_family == ADDRESS_FAMILY_UNSPECIFIED) {
2100    DnsHosts::const_iterator it = hosts.find(
2101        DnsHostsKey(hostname, ADDRESS_FAMILY_IPV6));
2102    if (it != hosts.end())
2103      addresses->push_back(IPEndPoint(it->second, info.port()));
2104  }
2105
2106  if (key.address_family == ADDRESS_FAMILY_IPV4 ||
2107      key.address_family == ADDRESS_FAMILY_UNSPECIFIED) {
2108    DnsHosts::const_iterator it = hosts.find(
2109        DnsHostsKey(hostname, ADDRESS_FAMILY_IPV4));
2110    if (it != hosts.end())
2111      addresses->push_back(IPEndPoint(it->second, info.port()));
2112  }
2113
2114  // If got only loopback addresses and the family was restricted, resolve
2115  // again, without restrictions. See SystemHostResolverCall for rationale.
2116  if ((key.host_resolver_flags &
2117          HOST_RESOLVER_DEFAULT_FAMILY_SET_DUE_TO_NO_IPV6) &&
2118      IsAllIPv4Loopback(*addresses)) {
2119    Key new_key(key);
2120    new_key.address_family = ADDRESS_FAMILY_UNSPECIFIED;
2121    new_key.host_resolver_flags &=
2122        ~HOST_RESOLVER_DEFAULT_FAMILY_SET_DUE_TO_NO_IPV6;
2123    return ServeFromHosts(new_key, info, addresses);
2124  }
2125  return !addresses->empty();
2126}
2127
2128void HostResolverImpl::CacheResult(const Key& key,
2129                                   const HostCache::Entry& entry,
2130                                   base::TimeDelta ttl) {
2131  if (cache_.get())
2132    cache_->Set(key, entry, base::TimeTicks::Now(), ttl);
2133}
2134
2135void HostResolverImpl::RemoveJob(Job* job) {
2136  DCHECK(job);
2137  JobMap::iterator it = jobs_.find(job->key());
2138  if (it != jobs_.end() && it->second == job)
2139    jobs_.erase(it);
2140}
2141
2142void HostResolverImpl::SetHaveOnlyLoopbackAddresses(bool result) {
2143  if (result) {
2144    additional_resolver_flags_ |= HOST_RESOLVER_LOOPBACK_ONLY;
2145  } else {
2146    additional_resolver_flags_ &= ~HOST_RESOLVER_LOOPBACK_ONLY;
2147  }
2148}
2149
2150HostResolverImpl::Key HostResolverImpl::GetEffectiveKeyForRequest(
2151    const RequestInfo& info, const BoundNetLog& net_log) const {
2152  HostResolverFlags effective_flags =
2153      info.host_resolver_flags() | additional_resolver_flags_;
2154  AddressFamily effective_address_family = info.address_family();
2155
2156  if (info.address_family() == ADDRESS_FAMILY_UNSPECIFIED) {
2157    if (probe_ipv6_support_ && !use_local_ipv6_) {
2158      base::TimeTicks start_time = base::TimeTicks::Now();
2159      // Google DNS address.
2160      const uint8 kIPv6Address[] =
2161          { 0x20, 0x01, 0x48, 0x60, 0x48, 0x60, 0x00, 0x00,
2162            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x88, 0x88 };
2163      IPAddressNumber address(kIPv6Address,
2164                              kIPv6Address + arraysize(kIPv6Address));
2165      BoundNetLog probe_net_log = BoundNetLog::Make(
2166          net_log.net_log(), NetLog::SOURCE_IPV6_REACHABILITY_CHECK);
2167      probe_net_log.BeginEvent(NetLog::TYPE_IPV6_REACHABILITY_CHECK,
2168                               net_log.source().ToEventParametersCallback());
2169      bool rv6 = IsGloballyReachable(address, probe_net_log);
2170      probe_net_log.EndEvent(NetLog::TYPE_IPV6_REACHABILITY_CHECK);
2171      if (rv6)
2172        net_log.AddEvent(NetLog::TYPE_HOST_RESOLVER_IMPL_IPV6_SUPPORTED);
2173
2174      UMA_HISTOGRAM_TIMES("Net.IPv6ConnectDuration",
2175                          base::TimeTicks::Now() - start_time);
2176      if (rv6) {
2177        UMA_HISTOGRAM_BOOLEAN("Net.IPv6ConnectSuccessMatch",
2178            default_address_family_ == ADDRESS_FAMILY_UNSPECIFIED);
2179      } else {
2180        UMA_HISTOGRAM_BOOLEAN("Net.IPv6ConnectFailureMatch",
2181            default_address_family_ != ADDRESS_FAMILY_UNSPECIFIED);
2182
2183        effective_address_family = ADDRESS_FAMILY_IPV4;
2184        effective_flags |= HOST_RESOLVER_DEFAULT_FAMILY_SET_DUE_TO_NO_IPV6;
2185      }
2186    } else {
2187      effective_address_family = default_address_family_;
2188    }
2189  }
2190
2191  return Key(info.hostname(), effective_address_family, effective_flags);
2192}
2193
2194void HostResolverImpl::AbortAllInProgressJobs() {
2195  // In Abort, a Request callback could spawn new Jobs with matching keys, so
2196  // first collect and remove all running jobs from |jobs_|.
2197  ScopedVector<Job> jobs_to_abort;
2198  for (JobMap::iterator it = jobs_.begin(); it != jobs_.end(); ) {
2199    Job* job = it->second;
2200    if (job->is_running()) {
2201      jobs_to_abort.push_back(job);
2202      jobs_.erase(it++);
2203    } else {
2204      DCHECK(job->is_queued());
2205      ++it;
2206    }
2207  }
2208
2209  // Pause the dispatcher so it won't start any new dispatcher jobs while
2210  // aborting the old ones.  This is needed so that it won't start the second
2211  // DnsTransaction for a job in |jobs_to_abort| if the DnsConfig just became
2212  // invalid.
2213  PrioritizedDispatcher::Limits limits = dispatcher_->GetLimits();
2214  dispatcher_->SetLimits(
2215      PrioritizedDispatcher::Limits(limits.reserved_slots.size(), 0));
2216
2217  // Life check to bail once |this| is deleted.
2218  base::WeakPtr<HostResolverImpl> self = weak_ptr_factory_.GetWeakPtr();
2219
2220  // Then Abort them.
2221  for (size_t i = 0; self.get() && i < jobs_to_abort.size(); ++i) {
2222    jobs_to_abort[i]->Abort();
2223    jobs_to_abort[i] = NULL;
2224  }
2225
2226  if (self)
2227    dispatcher_->SetLimits(limits);
2228}
2229
2230void HostResolverImpl::AbortDnsTasks() {
2231  // Pause the dispatcher so it won't start any new dispatcher jobs while
2232  // aborting the old ones.  This is needed so that it won't start the second
2233  // DnsTransaction for a job if the DnsConfig just changed.
2234  PrioritizedDispatcher::Limits limits = dispatcher_->GetLimits();
2235  dispatcher_->SetLimits(
2236      PrioritizedDispatcher::Limits(limits.reserved_slots.size(), 0));
2237
2238  for (JobMap::iterator it = jobs_.begin(); it != jobs_.end(); ++it)
2239    it->second->AbortDnsTask();
2240  dispatcher_->SetLimits(limits);
2241}
2242
2243void HostResolverImpl::TryServingAllJobsFromHosts() {
2244  if (!HaveDnsConfig())
2245    return;
2246
2247  // TODO(szym): Do not do this if nsswitch.conf instructs not to.
2248  // http://crbug.com/117655
2249
2250  // Life check to bail once |this| is deleted.
2251  base::WeakPtr<HostResolverImpl> self = weak_ptr_factory_.GetWeakPtr();
2252
2253  for (JobMap::iterator it = jobs_.begin(); self.get() && it != jobs_.end();) {
2254    Job* job = it->second;
2255    ++it;
2256    // This could remove |job| from |jobs_|, but iterator will remain valid.
2257    job->ServeFromHosts();
2258  }
2259}
2260
2261void HostResolverImpl::OnIPAddressChanged() {
2262  resolved_known_ipv6_hostname_ = false;
2263  // Abandon all ProbeJobs.
2264  probe_weak_ptr_factory_.InvalidateWeakPtrs();
2265  if (cache_.get())
2266    cache_->clear();
2267#if defined(OS_POSIX) && !defined(OS_MACOSX) && !defined(OS_ANDROID)
2268  new LoopbackProbeJob(probe_weak_ptr_factory_.GetWeakPtr());
2269#endif
2270  AbortAllInProgressJobs();
2271  // |this| may be deleted inside AbortAllInProgressJobs().
2272}
2273
2274void HostResolverImpl::OnDNSChanged() {
2275  DnsConfig dns_config;
2276  NetworkChangeNotifier::GetDnsConfig(&dns_config);
2277
2278  if (net_log_) {
2279    net_log_->AddGlobalEntry(
2280        NetLog::TYPE_DNS_CONFIG_CHANGED,
2281        base::Bind(&NetLogDnsConfigCallback, &dns_config));
2282  }
2283
2284  // TODO(szym): Remove once http://crbug.com/137914 is resolved.
2285  received_dns_config_ = dns_config.IsValid();
2286  // Conservatively assume local IPv6 is needed when DnsConfig is not valid.
2287  use_local_ipv6_ = !dns_config.IsValid() || dns_config.use_local_ipv6;
2288
2289  num_dns_failures_ = 0;
2290
2291  // We want a new DnsSession in place, before we Abort running Jobs, so that
2292  // the newly started jobs use the new config.
2293  if (dns_client_.get()) {
2294    dns_client_->SetConfig(dns_config);
2295    if (dns_client_->GetConfig())
2296      UMA_HISTOGRAM_BOOLEAN("AsyncDNS.DnsClientEnabled", true);
2297  }
2298
2299  // If the DNS server has changed, existing cached info could be wrong so we
2300  // have to drop our internal cache :( Note that OS level DNS caches, such
2301  // as NSCD's cache should be dropped automatically by the OS when
2302  // resolv.conf changes so we don't need to do anything to clear that cache.
2303  if (cache_.get())
2304    cache_->clear();
2305
2306  // Life check to bail once |this| is deleted.
2307  base::WeakPtr<HostResolverImpl> self = weak_ptr_factory_.GetWeakPtr();
2308
2309  // Existing jobs will have been sent to the original server so they need to
2310  // be aborted.
2311  AbortAllInProgressJobs();
2312
2313  // |this| may be deleted inside AbortAllInProgressJobs().
2314  if (self.get())
2315    TryServingAllJobsFromHosts();
2316}
2317
2318bool HostResolverImpl::HaveDnsConfig() const {
2319  // Use DnsClient only if it's fully configured and there is no override by
2320  // ScopedDefaultHostResolverProc.
2321  // The alternative is to use NetworkChangeNotifier to override DnsConfig,
2322  // but that would introduce construction order requirements for NCN and SDHRP.
2323  return (dns_client_.get() != NULL) && (dns_client_->GetConfig() != NULL) &&
2324         !(proc_params_.resolver_proc.get() == NULL &&
2325           HostResolverProc::GetDefault() != NULL);
2326}
2327
2328void HostResolverImpl::OnDnsTaskResolve(int net_error) {
2329  DCHECK(dns_client_);
2330  if (net_error == OK) {
2331    num_dns_failures_ = 0;
2332    return;
2333  }
2334  ++num_dns_failures_;
2335  if (num_dns_failures_ < kMaximumDnsFailures)
2336    return;
2337
2338  // Disable DnsClient until the next DNS change.  Must be done before aborting
2339  // DnsTasks, since doing so may start new jobs.
2340  dns_client_->SetConfig(DnsConfig());
2341
2342  // Switch jobs with active DnsTasks over to using ProcTasks.
2343  AbortDnsTasks();
2344
2345  UMA_HISTOGRAM_BOOLEAN("AsyncDNS.DnsClientEnabled", false);
2346  UMA_HISTOGRAM_CUSTOM_ENUMERATION("AsyncDNS.DnsClientDisabledReason",
2347                                   std::abs(net_error),
2348                                   GetAllErrorCodesForUma());
2349}
2350
2351void HostResolverImpl::SetDnsClient(scoped_ptr<DnsClient> dns_client) {
2352  // DnsClient and config must be updated before aborting DnsTasks, since doing
2353  // so may start new jobs.
2354  dns_client_ = dns_client.Pass();
2355  if (dns_client_ && !dns_client_->GetConfig() &&
2356      num_dns_failures_ < kMaximumDnsFailures) {
2357    DnsConfig dns_config;
2358    NetworkChangeNotifier::GetDnsConfig(&dns_config);
2359    dns_client_->SetConfig(dns_config);
2360    num_dns_failures_ = 0;
2361    if (dns_client_->GetConfig())
2362      UMA_HISTOGRAM_BOOLEAN("AsyncDNS.DnsClientEnabled", true);
2363  }
2364
2365  AbortDnsTasks();
2366}
2367
2368}  // namespace net
2369