View Javadoc
1   /*
2    * Copyright 2014 The Netty Project
3    *
4    * The Netty Project licenses this file to you under the Apache License,
5    * version 2.0 (the "License"); you may not use this file except in compliance
6    * with the License. You may obtain a copy of the License at:
7    *
8    *   http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13   * License for the specific language governing permissions and limitations
14   * under the License.
15   */
16  
17  package io.netty.resolver.dns;
18  
19  import io.netty.buffer.ByteBuf;
20  import io.netty.buffer.ByteBufHolder;
21  import io.netty.channel.AddressedEnvelope;
22  import io.netty.channel.ChannelPromise;
23  import io.netty.channel.socket.InternetProtocolFamily;
24  import io.netty.handler.codec.CorruptedFrameException;
25  import io.netty.handler.codec.dns.DefaultDnsQuestion;
26  import io.netty.handler.codec.dns.DefaultDnsRecordDecoder;
27  import io.netty.handler.codec.dns.DnsQuestion;
28  import io.netty.handler.codec.dns.DnsRawRecord;
29  import io.netty.handler.codec.dns.DnsRecord;
30  import io.netty.handler.codec.dns.DnsRecordType;
31  import io.netty.handler.codec.dns.DnsResponse;
32  import io.netty.handler.codec.dns.DnsResponseCode;
33  import io.netty.handler.codec.dns.DnsSection;
34  import io.netty.util.ReferenceCountUtil;
35  import io.netty.util.concurrent.Future;
36  import io.netty.util.concurrent.FutureListener;
37  import io.netty.util.concurrent.Promise;
38  import io.netty.util.internal.ObjectUtil;
39  import io.netty.util.internal.PlatformDependent;
40  import io.netty.util.internal.StringUtil;
41  import io.netty.util.internal.ThrowableUtil;
42  
43  import java.net.IDN;
44  import java.net.InetAddress;
45  import java.net.InetSocketAddress;
46  import java.net.UnknownHostException;
47  import java.util.ArrayList;
48  import java.util.Collections;
49  import java.util.HashMap;
50  import java.util.IdentityHashMap;
51  import java.util.Iterator;
52  import java.util.List;
53  import java.util.Locale;
54  import java.util.Map;
55  import java.util.Set;
56  
57  import static java.lang.Math.min;
58  import static java.util.Collections.unmodifiableList;
59  
60  abstract class DnsNameResolverContext<T> {
61  
62      private static final int INADDRSZ4 = 4;
63      private static final int INADDRSZ6 = 16;
64  
65      private static final FutureListener<AddressedEnvelope<DnsResponse, InetSocketAddress>> RELEASE_RESPONSE =
66              new FutureListener<AddressedEnvelope<DnsResponse, InetSocketAddress>>() {
67                  @Override
68                  public void operationComplete(Future<AddressedEnvelope<DnsResponse, InetSocketAddress>> future) {
69                      if (future.isSuccess()) {
70                          future.getNow().release();
71                      }
72                  }
73              };
74      private static final RuntimeException NXDOMAIN_QUERY_FAILED_EXCEPTION = ThrowableUtil.unknownStackTrace(
75              new RuntimeException("No answer found and NXDOMAIN response code returned"),
76              DnsNameResolverContext.class,
77              "onResponse(..)");
78      private static final RuntimeException CNAME_NOT_FOUND_QUERY_FAILED_EXCEPTION = ThrowableUtil.unknownStackTrace(
79              new RuntimeException("No matching CNAME record found"),
80              DnsNameResolverContext.class,
81              "onResponseCNAME(..)");
82      private static final RuntimeException NO_MATCHING_RECORD_QUERY_FAILED_EXCEPTION = ThrowableUtil.unknownStackTrace(
83              new RuntimeException("No matching record type found"),
84              DnsNameResolverContext.class,
85              "onResponseAorAAAA(..)");
86      private static final RuntimeException UNRECOGNIZED_TYPE_QUERY_FAILED_EXCEPTION = ThrowableUtil.unknownStackTrace(
87              new RuntimeException("Response type was unrecognized"),
88              DnsNameResolverContext.class,
89              "onResponse(..)");
90      private static final RuntimeException NAME_SERVERS_EXHAUSTED_EXCEPTION = ThrowableUtil.unknownStackTrace(
91              new RuntimeException("No name servers returned an answer"),
92              DnsNameResolverContext.class,
93              "tryToFinishResolve(..)");
94  
95      private final DnsNameResolver parent;
96      private final DnsServerAddressStream nameServerAddrs;
97      private final String hostname;
98      private final DnsCache resolveCache;
99      private final int maxAllowedQueries;
100     private final InternetProtocolFamily[] resolvedInternetProtocolFamilies;
101     private final DnsRecord[] additionals;
102 
103     private final Set<Future<AddressedEnvelope<DnsResponse, InetSocketAddress>>> queriesInProgress =
104             Collections.newSetFromMap(
105                     new IdentityHashMap<Future<AddressedEnvelope<DnsResponse, InetSocketAddress>>, Boolean>());
106 
107     private List<DnsCacheEntry> resolvedEntries;
108     private int allowedQueries;
109     private boolean triedCNAME;
110 
111     DnsNameResolverContext(DnsNameResolver parent,
112                            String hostname,
113                            DnsRecord[] additionals,
114                            DnsCache resolveCache,
115                            DnsServerAddressStream nameServerAddrs) {
116         this.parent = parent;
117         this.hostname = hostname;
118         this.additionals = additionals;
119         this.resolveCache = resolveCache;
120 
121         this.nameServerAddrs = ObjectUtil.checkNotNull(nameServerAddrs, "nameServerAddrs");
122         maxAllowedQueries = parent.maxQueriesPerResolve();
123         resolvedInternetProtocolFamilies = parent.resolvedInternetProtocolFamiliesUnsafe();
124         allowedQueries = maxAllowedQueries;
125     }
126 
127     void resolve(final Promise<T> promise) {
128         final String[] searchDomains = parent.searchDomains();
129         if (searchDomains.length == 0 || parent.ndots() == 0 || StringUtil.endsWith(hostname, '.')) {
130             internalResolve(promise);
131         } else {
132             final boolean startWithoutSearchDomain = hasNDots();
133             final String initialHostname = startWithoutSearchDomain ? hostname : hostname + '.' + searchDomains[0];
134             final int initialSearchDomainIdx = startWithoutSearchDomain ? 0 : 1;
135 
136             doSearchDomainQuery(initialHostname, new FutureListener<T>() {
137                 private int searchDomainIdx = initialSearchDomainIdx;
138                 @Override
139                 public void operationComplete(Future<T> future) throws Exception {
140                     Throwable cause = future.cause();
141                     if (cause == null) {
142                         promise.trySuccess(future.getNow());
143                     } else {
144                         if (DnsNameResolver.isTransportOrTimeoutError(cause)) {
145                             promise.tryFailure(new SearchDomainUnknownHostException(cause, hostname));
146                         } else if (searchDomainIdx < searchDomains.length) {
147                             doSearchDomainQuery(hostname + '.' + searchDomains[searchDomainIdx++], this);
148                         } else if (!startWithoutSearchDomain) {
149                             internalResolve(promise);
150                         } else {
151                             promise.tryFailure(new SearchDomainUnknownHostException(cause, hostname));
152                         }
153                     }
154                 }
155             });
156         }
157     }
158 
159     private boolean hasNDots() {
160         for (int idx = hostname.length() - 1, dots = 0; idx >= 0; idx--) {
161             if (hostname.charAt(idx) == '.' && ++dots >= parent.ndots()) {
162                 return true;
163             }
164         }
165         return false;
166     }
167 
168     private static final class SearchDomainUnknownHostException extends UnknownHostException {
169         private static final long serialVersionUID = -8573510133644997085L;
170 
171         SearchDomainUnknownHostException(Throwable cause, String originalHostname) {
172             super("Search domain query failed. Original hostname: '" + originalHostname + "' " + cause.getMessage());
173             setStackTrace(cause.getStackTrace());
174 
175             // Preserve the cause
176             initCause(cause.getCause());
177         }
178 
179         @Override
180         public Throwable fillInStackTrace() {
181             return this;
182         }
183     }
184 
185     private void doSearchDomainQuery(String hostname, FutureListener<T> listener) {
186         DnsNameResolverContext<T> nextContext = newResolverContext(parent, hostname, additionals, resolveCache,
187                 nameServerAddrs);
188         Promise<T> nextPromise = parent.executor().newPromise();
189         nextContext.internalResolve(nextPromise);
190         nextPromise.addListener(listener);
191     }
192 
193     private void internalResolve(Promise<T> promise) {
194         DnsServerAddressStream nameServerAddressStream = getNameServers(hostname);
195 
196         DnsRecordType[] recordTypes = parent.resolveRecordTypes();
197         assert recordTypes.length > 0;
198         final int end = recordTypes.length - 1;
199         for (int i = 0; i < end; ++i) {
200             if (!query(hostname, recordTypes[i], nameServerAddressStream.duplicate(), promise, null)) {
201                 return;
202             }
203         }
204         query(hostname, recordTypes[end], nameServerAddressStream, promise, null);
205     }
206 
207     /**
208      * Add an authoritative nameserver to the cache if its not a root server.
209      */
210     private void addNameServerToCache(
211             AuthoritativeNameServer name, InetAddress resolved, long ttl) {
212         if (!name.isRootServer()) {
213             // Cache NS record if not for a root server as we should never cache for root servers.
214             parent.authoritativeDnsServerCache().cache(name.domainName(),
215                     additionals, resolved, ttl, parent.ch.eventLoop());
216         }
217     }
218 
219     /**
220      * Returns the {@link DnsServerAddressStream} that was cached for the given hostname or {@code null} if non
221      *  could be found.
222      */
223     private DnsServerAddressStream getNameServersFromCache(String hostname) {
224         int len = hostname.length();
225 
226         if (len == 0) {
227             // We never cache for root servers.
228             return null;
229         }
230 
231         // We always store in the cache with a trailing '.'.
232         if (hostname.charAt(len - 1) != '.') {
233             hostname += ".";
234         }
235 
236         int idx = hostname.indexOf('.');
237         if (idx == hostname.length() - 1) {
238             // We are not interested in handling '.' as we should never serve the root servers from cache.
239             return null;
240         }
241 
242         // We start from the closed match and then move down.
243         for (;;) {
244             // Skip '.' as well.
245             hostname = hostname.substring(idx + 1);
246 
247             int idx2 = hostname.indexOf('.');
248             if (idx2 <= 0 || idx2 == hostname.length() - 1) {
249                 // We are not interested in handling '.TLD.' as we should never serve the root servers from cache.
250                 return null;
251             }
252             idx = idx2;
253 
254             List<? extends DnsCacheEntry> entries = parent.authoritativeDnsServerCache().get(hostname, additionals);
255             if (entries != null && !entries.isEmpty()) {
256                 return DnsServerAddresses.sequential(new DnsCacheIterable(entries)).stream();
257             }
258         }
259     }
260 
261     private final class DnsCacheIterable implements Iterable<InetSocketAddress> {
262         private final List<? extends DnsCacheEntry> entries;
263 
264         DnsCacheIterable(List<? extends DnsCacheEntry> entries) {
265             this.entries = entries;
266         }
267 
268         @Override
269         public Iterator<InetSocketAddress> iterator() {
270             return new Iterator<InetSocketAddress>() {
271                 Iterator<? extends DnsCacheEntry> entryIterator = entries.iterator();
272 
273                 @Override
274                 public boolean hasNext() {
275                     return entryIterator.hasNext();
276                 }
277 
278                 @Override
279                 public InetSocketAddress next() {
280                     InetAddress address = entryIterator.next().address();
281                     return new InetSocketAddress(address, parent.dnsRedirectPort(address));
282                 }
283 
284                 @Override
285                 public void remove() {
286                     entryIterator.remove();
287                 }
288             };
289         }
290     }
291 
292     private void query(final DnsServerAddressStream nameServerAddrStream, final int nameServerAddrStreamIndex,
293                        final DnsQuestion question,
294                        final Promise<T> promise, Throwable cause) {
295         query(nameServerAddrStream, nameServerAddrStreamIndex, question,
296                 parent.dnsQueryLifecycleObserverFactory().newDnsQueryLifecycleObserver(question), promise, cause);
297     }
298 
299     private void query(final DnsServerAddressStream nameServerAddrStream,
300                        final int nameServerAddrStreamIndex,
301                        final DnsQuestion question,
302                        final DnsQueryLifecycleObserver queryLifecycleObserver,
303                        final Promise<T> promise,
304                        final Throwable cause) {
305         if (nameServerAddrStreamIndex >= nameServerAddrStream.size() || allowedQueries == 0 || promise.isCancelled()) {
306             tryToFinishResolve(nameServerAddrStream, nameServerAddrStreamIndex, question, queryLifecycleObserver,
307                                promise, cause);
308             return;
309         }
310 
311         --allowedQueries;
312         final InetSocketAddress nameServerAddr = nameServerAddrStream.next();
313         final ChannelPromise writePromise = parent.ch.newPromise();
314         final Future<AddressedEnvelope<DnsResponse, InetSocketAddress>> f = parent.query0(
315                 nameServerAddr, question, additionals, writePromise,
316                 parent.ch.eventLoop().<AddressedEnvelope<? extends DnsResponse, InetSocketAddress>>newPromise());
317         queriesInProgress.add(f);
318 
319         queryLifecycleObserver.queryWritten(nameServerAddr, writePromise);
320 
321         f.addListener(new FutureListener<AddressedEnvelope<DnsResponse, InetSocketAddress>>() {
322             @Override
323             public void operationComplete(Future<AddressedEnvelope<DnsResponse, InetSocketAddress>> future) {
324                 queriesInProgress.remove(future);
325 
326                 if (promise.isDone() || future.isCancelled()) {
327                     queryLifecycleObserver.queryCancelled(allowedQueries);
328                     return;
329                 }
330 
331                 final Throwable queryCause = future.cause();
332                 try {
333                     if (queryCause == null) {
334                         onResponse(nameServerAddrStream, nameServerAddrStreamIndex, question, future.getNow(),
335                                    queryLifecycleObserver, promise);
336                     } else {
337                         // Server did not respond or I/O error occurred; try again.
338                         queryLifecycleObserver.queryFailed(queryCause);
339                         query(nameServerAddrStream, nameServerAddrStreamIndex + 1, question, promise, queryCause);
340                     }
341                 } finally {
342                     tryToFinishResolve(nameServerAddrStream, nameServerAddrStreamIndex, question,
343                                        // queryLifecycleObserver has already been terminated at this point so we must
344                                        // not allow it to be terminated again by tryToFinishResolve.
345                                        NoopDnsQueryLifecycleObserver.INSTANCE,
346                                        promise, queryCause);
347                 }
348             }
349         });
350     }
351 
352     void onResponse(final DnsServerAddressStream nameServerAddrStream, final int nameServerAddrStreamIndex,
353                     final DnsQuestion question, AddressedEnvelope<DnsResponse, InetSocketAddress> envelope,
354                     final DnsQueryLifecycleObserver queryLifecycleObserver,
355                     Promise<T> promise) {
356         try {
357             final DnsResponse res = envelope.content();
358             final DnsResponseCode code = res.code();
359             if (code == DnsResponseCode.NOERROR) {
360                 if (handleRedirect(question, envelope, queryLifecycleObserver, promise)) {
361                     // Was a redirect so return here as everything else is handled in handleRedirect(...)
362                     return;
363                 }
364                 final DnsRecordType type = question.type();
365 
366                 if (type == DnsRecordType.A || type == DnsRecordType.AAAA) {
367                     onResponseAorAAAA(type, question, envelope, queryLifecycleObserver, promise);
368                 } else if (type == DnsRecordType.CNAME) {
369                     onResponseCNAME(question, envelope, queryLifecycleObserver, promise);
370                 } else {
371                     queryLifecycleObserver.queryFailed(UNRECOGNIZED_TYPE_QUERY_FAILED_EXCEPTION);
372                 }
373                 return;
374             }
375 
376             // Retry with the next server if the server did not tell us that the domain does not exist.
377             if (code != DnsResponseCode.NXDOMAIN) {
378                 query(nameServerAddrStream, nameServerAddrStreamIndex + 1, question,
379                       queryLifecycleObserver.queryNoAnswer(code), promise, null);
380             } else {
381                 queryLifecycleObserver.queryFailed(NXDOMAIN_QUERY_FAILED_EXCEPTION);
382             }
383         } finally {
384             ReferenceCountUtil.safeRelease(envelope);
385         }
386     }
387 
388     /**
389      * Handles a redirect answer if needed and returns {@code true} if a redirect query has been made.
390      */
391     private boolean handleRedirect(
392             DnsQuestion question, AddressedEnvelope<DnsResponse, InetSocketAddress> envelope,
393             final DnsQueryLifecycleObserver queryLifecycleObserver, Promise<T> promise) {
394         final DnsResponse res = envelope.content();
395 
396         // Check if we have answers, if not this may be an non authority NS and so redirects must be handled.
397         if (res.count(DnsSection.ANSWER) == 0) {
398             AuthoritativeNameServerList serverNames = extractAuthoritativeNameServers(question.name(), res);
399 
400             if (serverNames != null) {
401                 List<InetSocketAddress> nameServers = new ArrayList<InetSocketAddress>(serverNames.size());
402                 int additionalCount = res.count(DnsSection.ADDITIONAL);
403 
404                 for (int i = 0; i < additionalCount; i++) {
405                     final DnsRecord r = res.recordAt(DnsSection.ADDITIONAL, i);
406 
407                     if (r.type() == DnsRecordType.A && !parent.supportsARecords() ||
408                         r.type() == DnsRecordType.AAAA && !parent.supportsAAAARecords()) {
409                         continue;
410                     }
411 
412                     final String recordName = r.name();
413                     AuthoritativeNameServer authoritativeNameServer =
414                             serverNames.remove(recordName);
415 
416                     if (authoritativeNameServer == null) {
417                         // Not a server we are interested in.
418                         continue;
419                     }
420 
421                     InetAddress resolved = parseAddress(r, recordName);
422                     if (resolved == null) {
423                         // Could not parse it, move to the next.
424                         continue;
425                     }
426 
427                     nameServers.add(new InetSocketAddress(resolved, parent.dnsRedirectPort(resolved)));
428                     addNameServerToCache(authoritativeNameServer, resolved, r.timeToLive());
429                 }
430 
431                 if (!nameServers.isEmpty()) {
432                     query(parent.uncachedRedirectDnsServerStream(nameServers), 0, question,
433                           queryLifecycleObserver.queryRedirected(unmodifiableList(nameServers)), promise, null);
434                     return true;
435                 }
436             }
437         }
438         return false;
439     }
440 
441     /**
442      * Returns the {@code {@link AuthoritativeNameServerList} which were included in {@link DnsSection#AUTHORITY}
443      * or {@code null} if non are found.
444      */
445     private static AuthoritativeNameServerList extractAuthoritativeNameServers(String questionName, DnsResponse res) {
446         int authorityCount = res.count(DnsSection.AUTHORITY);
447         if (authorityCount == 0) {
448             return null;
449         }
450 
451         AuthoritativeNameServerList serverNames = new AuthoritativeNameServerList(questionName);
452         for (int i = 0; i < authorityCount; i++) {
453             serverNames.add(res.recordAt(DnsSection.AUTHORITY, i));
454         }
455         return serverNames;
456     }
457 
458     private void onResponseAorAAAA(
459             DnsRecordType qType, DnsQuestion question, AddressedEnvelope<DnsResponse, InetSocketAddress> envelope,
460             final DnsQueryLifecycleObserver queryLifecycleObserver,
461             Promise<T> promise) {
462 
463         // We often get a bunch of CNAMES as well when we asked for A/AAAA.
464         final DnsResponse response = envelope.content();
465         final Map<String, String> cnames = buildAliasMap(response);
466         final int answerCount = response.count(DnsSection.ANSWER);
467 
468         boolean found = false;
469         for (int i = 0; i < answerCount; i ++) {
470             final DnsRecord r = response.recordAt(DnsSection.ANSWER, i);
471             final DnsRecordType type = r.type();
472             if (type != DnsRecordType.A && type != DnsRecordType.AAAA) {
473                 continue;
474             }
475 
476             final String questionName = question.name().toLowerCase(Locale.US);
477             final String recordName = r.name().toLowerCase(Locale.US);
478 
479             // Make sure the record is for the questioned domain.
480             if (!recordName.equals(questionName)) {
481                 // Even if the record's name is not exactly same, it might be an alias defined in the CNAME records.
482                 String resolved = questionName;
483                 do {
484                     resolved = cnames.get(resolved);
485                     if (recordName.equals(resolved)) {
486                         break;
487                     }
488                 } while (resolved != null);
489 
490                 if (resolved == null) {
491                     continue;
492                 }
493             }
494 
495             InetAddress resolved = parseAddress(r, hostname);
496             if (resolved == null) {
497                 continue;
498             }
499 
500             if (resolvedEntries == null) {
501                 resolvedEntries = new ArrayList<DnsCacheEntry>(8);
502             }
503 
504             resolvedEntries.add(
505                     resolveCache.cache(hostname, additionals, resolved, r.timeToLive(), parent.ch.eventLoop()));
506             found = true;
507 
508             // Note that we do not break from the loop here, so we decode/cache all A/AAAA records.
509         }
510 
511         if (found) {
512             queryLifecycleObserver.querySucceed();
513             return;
514         }
515 
516         if (cnames.isEmpty()) {
517             queryLifecycleObserver.queryFailed(NO_MATCHING_RECORD_QUERY_FAILED_EXCEPTION);
518         } else {
519             // We asked for A/AAAA but we got only CNAME.
520             onResponseCNAME(question, envelope, cnames, queryLifecycleObserver, promise);
521         }
522     }
523 
524     private InetAddress parseAddress(DnsRecord r, String name) {
525         if (!(r instanceof DnsRawRecord)) {
526             return null;
527         }
528         final ByteBuf content = ((ByteBufHolder) r).content();
529         final int contentLen = content.readableBytes();
530         if (contentLen != INADDRSZ4 && contentLen != INADDRSZ6) {
531             return null;
532         }
533 
534         final byte[] addrBytes = new byte[contentLen];
535         content.getBytes(content.readerIndex(), addrBytes);
536 
537         try {
538             return InetAddress.getByAddress(
539                     parent.isDecodeIdn() ? IDN.toUnicode(name) : name, addrBytes);
540         } catch (UnknownHostException e) {
541             // Should never reach here.
542             throw new Error(e);
543         }
544     }
545 
546     private void onResponseCNAME(DnsQuestion question, AddressedEnvelope<DnsResponse, InetSocketAddress> envelope,
547                                  final DnsQueryLifecycleObserver queryLifecycleObserver,
548                                  Promise<T> promise) {
549         onResponseCNAME(question, envelope, buildAliasMap(envelope.content()), queryLifecycleObserver, promise);
550     }
551 
552     private void onResponseCNAME(
553             DnsQuestion question, AddressedEnvelope<DnsResponse, InetSocketAddress> response,
554             Map<String, String> cnames, final DnsQueryLifecycleObserver queryLifecycleObserver,
555             Promise<T> promise) {
556 
557         // Resolve the host name in the question into the real host name.
558         final String name = question.name().toLowerCase(Locale.US);
559         String resolved = name;
560         boolean found = false;
561         while (!cnames.isEmpty()) { // Do not attempt to call Map.remove() when the Map is empty
562                                     // because it can be Collections.emptyMap()
563                                     // whose remove() throws a UnsupportedOperationException.
564             final String next = cnames.remove(resolved);
565             if (next != null) {
566                 found = true;
567                 resolved = next;
568             } else {
569                 break;
570             }
571         }
572 
573         if (found) {
574             followCname(resolved, queryLifecycleObserver, promise);
575         } else {
576             queryLifecycleObserver.queryFailed(CNAME_NOT_FOUND_QUERY_FAILED_EXCEPTION);
577         }
578     }
579 
580     private static Map<String, String> buildAliasMap(DnsResponse response) {
581         final int answerCount = response.count(DnsSection.ANSWER);
582         Map<String, String> cnames = null;
583         for (int i = 0; i < answerCount; i ++) {
584             final DnsRecord r = response.recordAt(DnsSection.ANSWER, i);
585             final DnsRecordType type = r.type();
586             if (type != DnsRecordType.CNAME) {
587                 continue;
588             }
589 
590             if (!(r instanceof DnsRawRecord)) {
591                 continue;
592             }
593 
594             final ByteBuf recordContent = ((ByteBufHolder) r).content();
595             final String domainName = decodeDomainName(recordContent);
596             if (domainName == null) {
597                 continue;
598             }
599 
600             if (cnames == null) {
601                 cnames = new HashMap<String, String>(min(8, answerCount));
602             }
603 
604             cnames.put(r.name().toLowerCase(Locale.US), domainName.toLowerCase(Locale.US));
605         }
606 
607         return cnames != null? cnames : Collections.<String, String>emptyMap();
608     }
609 
610     void tryToFinishResolve(final DnsServerAddressStream nameServerAddrStream,
611                             final int nameServerAddrStreamIndex,
612                             final DnsQuestion question,
613                             final DnsQueryLifecycleObserver queryLifecycleObserver,
614                             final Promise<T> promise,
615                             final Throwable cause) {
616         // There are no queries left to try.
617         if (!queriesInProgress.isEmpty()) {
618             queryLifecycleObserver.queryCancelled(allowedQueries);
619 
620             // There are still some queries we did not receive responses for.
621             if (gotPreferredAddress()) {
622                 // But it's OK to finish the resolution process if we got a resolved address of the preferred type.
623                 finishResolve(promise, cause);
624             }
625 
626             // We did not get any resolved address of the preferred type, so we can't finish the resolution process.
627             return;
628         }
629 
630         // There are no queries left to try.
631         if (resolvedEntries == null) {
632             if (nameServerAddrStreamIndex < nameServerAddrStream.size()) {
633                 if (queryLifecycleObserver == NoopDnsQueryLifecycleObserver.INSTANCE) {
634                     // If the queryLifecycleObserver has already been terminated we should create a new one for this
635                     // fresh query.
636                     query(nameServerAddrStream, nameServerAddrStreamIndex + 1, question, promise, cause);
637                 } else {
638                     query(nameServerAddrStream, nameServerAddrStreamIndex + 1, question, queryLifecycleObserver,
639                           promise, cause);
640                 }
641                 return;
642             }
643 
644             queryLifecycleObserver.queryFailed(NAME_SERVERS_EXHAUSTED_EXCEPTION);
645 
646             // .. and we could not find any A/AAAA records.
647 
648             // If cause != null we know this was caused by a timeout / cancel / transport exception. In this case we
649             // won't try to resolve the CNAME as we only should do this if we could not get the A/AAAA records because
650             // these not exists and the DNS server did probably signal it.
651             if (cause == null && !triedCNAME) {
652                 // As the last resort, try to query CNAME, just in case the name server has it.
653                 triedCNAME = true;
654 
655                 query(hostname, DnsRecordType.CNAME, getNameServers(hostname), promise, null);
656                 return;
657             }
658         } else {
659             queryLifecycleObserver.queryCancelled(allowedQueries);
660         }
661 
662         // We have at least one resolved address or tried CNAME as the last resort..
663         finishResolve(promise, cause);
664     }
665 
666     private boolean gotPreferredAddress() {
667         if (resolvedEntries == null) {
668             return false;
669         }
670 
671         final int size = resolvedEntries.size();
672         final Class<? extends InetAddress> inetAddressType = parent.preferredAddressType().addressType();
673         for (int i = 0; i < size; i++) {
674             InetAddress address = resolvedEntries.get(i).address();
675             if (inetAddressType.isInstance(address)) {
676                 return true;
677             }
678         }
679         return false;
680     }
681 
682     private void finishResolve(Promise<T> promise, Throwable cause) {
683         if (!queriesInProgress.isEmpty()) {
684             // If there are queries in progress, we should cancel it because we already finished the resolution.
685             for (Iterator<Future<AddressedEnvelope<DnsResponse, InetSocketAddress>>> i = queriesInProgress.iterator();
686                  i.hasNext();) {
687                 Future<AddressedEnvelope<DnsResponse, InetSocketAddress>> f = i.next();
688                 i.remove();
689 
690                 if (!f.cancel(false)) {
691                     f.addListener(RELEASE_RESPONSE);
692                 }
693             }
694         }
695 
696         if (resolvedEntries != null) {
697             // Found at least one resolved address.
698             for (InternetProtocolFamily f: resolvedInternetProtocolFamilies) {
699                 if (finishResolve(f.addressType(), resolvedEntries, promise)) {
700                     return;
701                 }
702             }
703         }
704 
705         // No resolved address found.
706         final int tries = maxAllowedQueries - allowedQueries;
707         final StringBuilder buf = new StringBuilder(64);
708 
709         buf.append("failed to resolve '").append(hostname).append('\'');
710         if (tries > 1) {
711             if (tries < maxAllowedQueries) {
712                 buf.append(" after ")
713                    .append(tries)
714                    .append(" queries ");
715             } else {
716                 buf.append(". Exceeded max queries per resolve ")
717                 .append(maxAllowedQueries)
718                 .append(' ');
719             }
720         }
721         final UnknownHostException unknownHostException = new UnknownHostException(buf.toString());
722         if (cause == null) {
723             // Only cache if the failure was not because of an IO error / timeout that was caused by the query
724             // itself.
725             resolveCache.cache(hostname, additionals, unknownHostException, parent.ch.eventLoop());
726         } else {
727             unknownHostException.initCause(cause);
728         }
729         promise.tryFailure(unknownHostException);
730     }
731 
732     abstract boolean finishResolve(Class<? extends InetAddress> addressType, List<DnsCacheEntry> resolvedEntries,
733                                    Promise<T> promise);
734 
735     abstract DnsNameResolverContext<T> newResolverContext(DnsNameResolver parent, String hostname,
736                                                           DnsRecord[] additionals, DnsCache resolveCache,
737                                                           DnsServerAddressStream nameServerAddrs);
738 
739     static String decodeDomainName(ByteBuf in) {
740         in.markReaderIndex();
741         try {
742             return DefaultDnsRecordDecoder.decodeName(in);
743         } catch (CorruptedFrameException e) {
744             // In this case we just return null.
745             return null;
746         } finally {
747             in.resetReaderIndex();
748         }
749     }
750 
751     private DnsServerAddressStream getNameServers(String hostname) {
752         DnsServerAddressStream stream = getNameServersFromCache(hostname);
753         return stream == null ? nameServerAddrs : stream;
754     }
755 
756     private void followCname(String cname, final DnsQueryLifecycleObserver queryLifecycleObserver, Promise<T> promise) {
757         // Use the same server for both CNAME queries
758         DnsServerAddressStream stream = DnsServerAddresses.singleton(getNameServers(cname).next()).stream();
759 
760         DnsQuestion cnameQuestion = null;
761         if (parent.supportsARecords()) {
762             try {
763                 if ((cnameQuestion = newQuestion(cname, DnsRecordType.A)) == null) {
764                     return;
765                 }
766             } catch (Throwable cause) {
767                 queryLifecycleObserver.queryFailed(cause);
768                 PlatformDependent.throwException(cause);
769             }
770             query(stream, 0, cnameQuestion, queryLifecycleObserver.queryCNAMEd(cnameQuestion), promise, null);
771         }
772         if (parent.supportsAAAARecords()) {
773             try {
774                 if ((cnameQuestion = newQuestion(cname, DnsRecordType.AAAA)) == null) {
775                     return;
776                 }
777             } catch (Throwable cause) {
778                 queryLifecycleObserver.queryFailed(cause);
779                 PlatformDependent.throwException(cause);
780             }
781             query(stream, 0, cnameQuestion, queryLifecycleObserver.queryCNAMEd(cnameQuestion), promise, null);
782         }
783     }
784 
785     private boolean query(String hostname, DnsRecordType type, DnsServerAddressStream dnsServerAddressStream,
786                           Promise<T> promise, Throwable cause) {
787         final DnsQuestion question = newQuestion(hostname, type);
788         if (question == null) {
789             return false;
790         }
791         query(dnsServerAddressStream, 0, question, promise, cause);
792         return true;
793     }
794 
795     private static DnsQuestion newQuestion(String hostname, DnsRecordType type) {
796         try {
797             return new DefaultDnsQuestion(hostname, type);
798         } catch (IllegalArgumentException e) {
799             // java.net.IDN.toASCII(...) may throw an IllegalArgumentException if it fails to parse the hostname
800             return null;
801         }
802     }
803 
804     /**
805      * Holds the closed DNS Servers for a domain.
806      */
807     private static final class AuthoritativeNameServerList {
808 
809         private final String questionName;
810 
811         // We not expect the linked-list to be very long so a double-linked-list is overkill.
812         private AuthoritativeNameServer head;
813         private int count;
814 
815         AuthoritativeNameServerList(String questionName) {
816             this.questionName = questionName.toLowerCase(Locale.US);
817         }
818 
819         void add(DnsRecord r) {
820             if (r.type() != DnsRecordType.NS || !(r instanceof DnsRawRecord)) {
821                 return;
822             }
823 
824             // Only include servers that serve the correct domain.
825             if (questionName.length() <  r.name().length()) {
826                 return;
827             }
828 
829             String recordName = r.name().toLowerCase(Locale.US);
830 
831             int dots = 0;
832             for (int a = recordName.length() - 1, b = questionName.length() - 1; a >= 0; a--, b--) {
833                 char c = recordName.charAt(a);
834                 if (questionName.charAt(b) != c) {
835                     return;
836                 }
837                 if (c == '.') {
838                     dots++;
839                 }
840             }
841 
842             if (head != null && head.dots > dots) {
843                 // We already have a closer match so ignore this one, no need to parse the domainName etc.
844                 return;
845             }
846 
847             final ByteBuf recordContent = ((ByteBufHolder) r).content();
848             final String domainName = decodeDomainName(recordContent);
849             if (domainName == null) {
850                 // Could not be parsed, ignore.
851                 return;
852             }
853 
854             // We are only interested in preserving the nameservers which are the closest to our qName, so ensure
855             // we drop servers that have a smaller dots count.
856             if (head == null || head.dots < dots) {
857                 count = 1;
858                 head = new AuthoritativeNameServer(dots, recordName, domainName);
859             } else if (head.dots == dots) {
860                 AuthoritativeNameServer serverName = head;
861                 while (serverName.next != null) {
862                     serverName = serverName.next;
863                 }
864                 serverName.next = new AuthoritativeNameServer(dots, recordName, domainName);
865                 count++;
866             }
867         }
868 
869         // Just walk the linked-list and mark the entry as removed when matched, so next lookup will need to process
870         // one node less.
871         AuthoritativeNameServer remove(String nsName) {
872             AuthoritativeNameServer serverName = head;
873 
874             while (serverName != null) {
875                 if (!serverName.removed && serverName.nsName.equalsIgnoreCase(nsName)) {
876                     serverName.removed = true;
877                     return serverName;
878                 }
879                 serverName = serverName.next;
880             }
881             return null;
882         }
883 
884         int size() {
885             return count;
886         }
887     }
888 
889     static final class AuthoritativeNameServer {
890         final int dots;
891         final String nsName;
892         final String domainName;
893 
894         AuthoritativeNameServer next;
895         boolean removed;
896 
897         AuthoritativeNameServer(int dots, String domainName, String nsName) {
898             this.dots = dots;
899             this.nsName = nsName;
900             this.domainName = domainName;
901         }
902 
903         /**
904          * Returns {@code true} if its a root server.
905          */
906         boolean isRootServer() {
907             return dots == 1;
908         }
909 
910         /**
911          * The domain for which the {@link AuthoritativeNameServer} is responsible.
912          */
913         String domainName() {
914             return domainName;
915         }
916     }
917 }