001/*
002 * Copyright 2015-2018 the original author or authors
003 *
004 * This software is licensed under the Apache License, Version 2.0,
005 * the GNU Lesser General Public License version 2 or later ("LGPL")
006 * and the WTFPL.
007 * You may choose either license to govern your use of this software only
008 * upon the condition that you accept all of the terms of either
009 * the Apache License 2.0, the LGPL 2.1+ or the WTFPL.
010 */
011package org.minidns.iterative;
012
013import org.minidns.AbstractDnsClient;
014import org.minidns.DnsCache;
015import org.minidns.dnsmessage.DnsMessage;
016import org.minidns.dnsmessage.Question;
017import org.minidns.dnsname.DnsName;
018import org.minidns.iterative.IterativeClientException.LoopDetected;
019import org.minidns.record.A;
020import org.minidns.record.AAAA;
021import org.minidns.record.RRWithTarget;
022import org.minidns.record.Record;
023import org.minidns.record.Record.TYPE;
024import org.minidns.record.Data;
025import org.minidns.record.InternetAddressRR;
026import org.minidns.record.NS;
027import org.minidns.util.MultipleIoException;
028
029import java.io.IOException;
030import java.net.Inet4Address;
031import java.net.Inet6Address;
032import java.net.InetAddress;
033import java.net.UnknownHostException;
034import java.util.ArrayList;
035import java.util.Collection;
036import java.util.Collections;
037import java.util.HashMap;
038import java.util.Iterator;
039import java.util.LinkedList;
040import java.util.List;
041import java.util.Map;
042import java.util.Random;
043import java.util.logging.Level;
044
045public class IterativeDnsClient extends AbstractDnsClient {
046
047    private static final Map<Character, InetAddress> IPV4_ROOT_SERVER_MAP = new HashMap<>();
048
049    private static final Map<Character, InetAddress> IPV6_ROOT_SERVER_MAP = new HashMap<>();
050
051    protected static final Inet4Address[] IPV4_ROOT_SERVERS = new Inet4Address[] {
052        rootServerInet4Address('a', 198,  41,   0,   4),
053        rootServerInet4Address('b', 192, 228,  79, 201),
054        rootServerInet4Address('c', 192,  33,   4,  12),
055        rootServerInet4Address('d', 199,   7,  91 , 13),
056        rootServerInet4Address('e', 192, 203, 230,  10),
057        rootServerInet4Address('f', 192,   5,   5, 241),
058        rootServerInet4Address('g', 192, 112,  36,   4),
059        rootServerInet4Address('h', 198,  97, 190,  53),
060        rootServerInet4Address('i', 192,  36, 148,  17),
061        rootServerInet4Address('j', 192,  58, 128,  30),
062        rootServerInet4Address('k', 193,   0,  14, 129),
063        rootServerInet4Address('l', 199,   7,  83,  42),
064        rootServerInet4Address('m', 202,  12,  27,  33),
065    };
066
067    protected static final Inet6Address[] IPV6_ROOT_SERVERS = new Inet6Address[] {
068        rootServerInet6Address('a', 0x2001, 0x0503, 0xba3e, 0x0000, 0x0000, 0x000, 0x0002, 0x0030),
069        rootServerInet6Address('b', 0x2001, 0x0500, 0x0084, 0x0000, 0x0000, 0x000, 0x0000, 0x000b),
070        rootServerInet6Address('c', 0x2001, 0x0500, 0x0002, 0x0000, 0x0000, 0x000, 0x0000, 0x000c),
071        rootServerInet6Address('d', 0x2001, 0x0500, 0x002d, 0x0000, 0x0000, 0x000, 0x0000, 0x000d),
072        rootServerInet6Address('f', 0x2001, 0x0500, 0x002f, 0x0000, 0x0000, 0x000, 0x0000, 0x000f),
073        rootServerInet6Address('h', 0x2001, 0x0500, 0x0001, 0x0000, 0x0000, 0x000, 0x0000, 0x0053),
074        rootServerInet6Address('i', 0x2001, 0x07fe, 0x0000, 0x0000, 0x0000, 0x000, 0x0000, 0x0053),
075        rootServerInet6Address('j', 0x2001, 0x0503, 0x0c27, 0x0000, 0x0000, 0x000, 0x0002, 0x0030),
076        rootServerInet6Address('l', 0x2001, 0x0500, 0x0003, 0x0000, 0x0000, 0x000, 0x0000, 0x0042),
077        rootServerInet6Address('m', 0x2001, 0x0dc3, 0x0000, 0x0000, 0x0000, 0x000, 0x0000, 0x0035),
078    };
079
080    int maxSteps = 128;
081
082    /**
083     * Create a new recursive DNS client using the global default cache.
084     */
085    public IterativeDnsClient() {
086        super();
087    }
088
089    /**
090     * Create a new recursive DNS client with the given DNS cache.
091     *
092     * @param cache The backend DNS cache.
093     */
094    public IterativeDnsClient(DnsCache cache) {
095        super(cache);
096    }
097
098    /**
099     * Recursively query the DNS system for one entry.
100     *
101     * @param queryBuilder The query DNS message builder.
102     * @return The response (or null on timeout/error).
103     * @throws IOException if an IO error occurs.
104     */
105    @Override
106    protected DnsMessage query(DnsMessage.Builder queryBuilder) throws IOException {
107        DnsMessage q = queryBuilder.build();
108        ResolutionState resolutionState = new ResolutionState(this);
109        DnsMessage message = queryRecursive(resolutionState, q);
110        return message;
111    }
112
113    private Inet4Address getRandomIpv4RootServer() {
114        return IPV4_ROOT_SERVERS[insecureRandom.nextInt(IPV4_ROOT_SERVERS.length)];
115    }
116
117    private Inet6Address getRandomIpv6RootServer() {
118        return IPV6_ROOT_SERVERS[insecureRandom.nextInt(IPV6_ROOT_SERVERS.length)];
119    }
120
121    private static InetAddress[] getTargets(Collection<? extends InternetAddressRR> primaryTargets,
122            Collection<? extends InternetAddressRR> secondaryTargets) {
123        InetAddress[] res = new InetAddress[2];
124
125        for (InternetAddressRR arr : primaryTargets) {
126            if (res[0] == null) {
127                res[0] = arr.getInetAddress();
128                // If secondaryTargets is empty, then try to get the second target out of the set of primaryTargets.
129                if (secondaryTargets.isEmpty()) {
130                    continue;
131                }
132            }
133            if (res[1] == null) {
134                res[1] = arr.getInetAddress();
135            }
136            break;
137        }
138
139        for (InternetAddressRR arr : secondaryTargets) {
140            if (res[0] == null) {
141                res[0] = arr.getInetAddress();
142                continue;
143            }
144            if (res[1] == null) {
145                res[1] = arr.getInetAddress();
146            }
147            break;
148        }
149
150        return res;
151    }
152
153    private DnsMessage queryRecursive(ResolutionState resolutionState, DnsMessage q) throws IOException {
154        InetAddress primaryTarget = null, secondaryTarget = null;
155
156        Question question = q.getQuestion();
157        DnsName parent = question.name.getParent();
158
159        switch (ipVersionSetting) {
160        case v4only:
161            for (A a : getCachedIPv4NameserverAddressesFor(parent)) {
162                if (primaryTarget == null) {
163                    primaryTarget = a.getInetAddress();
164                    continue;
165                }
166                secondaryTarget = a.getInetAddress();
167                break;
168            }
169            break;
170        case v6only:
171            for (AAAA aaaa : getCachedIPv6NameserverAddressesFor(parent)) {
172                if (primaryTarget == null) {
173                    primaryTarget = aaaa.getInetAddress();
174                    continue;
175                }
176                secondaryTarget = aaaa.getInetAddress();
177                break;
178            }
179            break;
180        case v4v6:
181            InetAddress[] v4v6targets = getTargets(getCachedIPv4NameserverAddressesFor(parent), getCachedIPv6NameserverAddressesFor(parent));
182            primaryTarget = v4v6targets[0];
183            secondaryTarget = v4v6targets[1];
184            break;
185        case v6v4:
186            InetAddress[] v6v4targets = getTargets(getCachedIPv6NameserverAddressesFor(parent), getCachedIPv4NameserverAddressesFor(parent));
187            primaryTarget = v6v4targets[0];
188            secondaryTarget = v6v4targets[1];
189            break;
190        default:
191            throw new AssertionError();
192        }
193
194        DnsName authoritativeZone = parent;
195        if (primaryTarget == null) {
196            authoritativeZone = DnsName.ROOT;
197            switch (ipVersionSetting) {
198            case v4only:
199                primaryTarget = getRandomIpv4RootServer();
200                break;
201            case v6only:
202                primaryTarget = getRandomIpv6RootServer();
203                break;
204            case v4v6:
205                primaryTarget = getRandomIpv4RootServer();
206                secondaryTarget = getRandomIpv6RootServer();
207                break;
208            case v6v4:
209                primaryTarget = getRandomIpv6RootServer();
210                secondaryTarget = getRandomIpv4RootServer();
211                break;
212            }
213        }
214
215        List<IOException> ioExceptions = new LinkedList<>();
216
217        try {
218            return queryRecursive(resolutionState, q, primaryTarget, authoritativeZone);
219        } catch (IOException ioException) {
220            abortIfFatal(ioException);
221            ioExceptions.add(ioException);
222        }
223
224        if (secondaryTarget != null) {
225            try {
226                return queryRecursive(resolutionState, q, secondaryTarget, authoritativeZone);
227            } catch (IOException ioException) {
228                ioExceptions.add(ioException);
229            }
230        }
231
232        MultipleIoException.throwIfRequired(ioExceptions);
233        return null;
234    }
235
236    private DnsMessage queryRecursive(ResolutionState resolutionState, DnsMessage q, InetAddress address, DnsName authoritativeZone) throws IOException {
237        resolutionState.recurse(address, q);
238
239        DnsMessage resMessage = query(q, address);
240
241        if (resMessage == null) {
242            // TODO throw exception here?
243            return null;
244        }
245
246        if (resMessage.authoritativeAnswer) {
247            return resMessage;
248        }
249
250        if (cache != null) {
251            cache.offer(q, resMessage, authoritativeZone);
252        }
253
254        List<Record<? extends Data>> authorities = resMessage.copyAuthority();
255
256        List<IOException> ioExceptions = new LinkedList<>();
257
258        // Glued NS first
259        for (Iterator<Record<? extends Data>> iterator = authorities.iterator(); iterator.hasNext(); ) {
260            Record<? extends Data> record = iterator.next();
261            if (record.type != TYPE.NS) {
262                iterator.remove();
263                continue;
264            }
265            DnsName name = ((NS) record.payloadData).target;
266            IpResultSet gluedNs = searchAdditional(resMessage, name);
267            for (Iterator<InetAddress> addressIterator = gluedNs.addresses.iterator(); addressIterator.hasNext(); ) {
268                InetAddress target = addressIterator.next();
269                DnsMessage recursive = null;
270                try {
271                    recursive = queryRecursive(resolutionState, q, target, record.name);
272                } catch (IOException e) {
273                   abortIfFatal(e);
274                   LOGGER.log(Level.FINER, "Exception while recursing", e);
275                   resolutionState.decrementSteps();
276                   ioExceptions.add(e);
277                   if (!addressIterator.hasNext()) {
278                       iterator.remove();
279                   }
280                   continue;
281                }
282                return recursive;
283            }
284        }
285
286        // Try non-glued NS
287        for (Record<? extends Data> record : authorities) {
288            final Question question = q.getQuestion();
289            DnsName name = ((NS) record.payloadData).target;
290
291            // Loop prevention: If this non-glued NS equals the name we question for and if the question is about a A or
292            // AAAA RR, then we should not continue here as it would result in an endless loop.
293            if (question.name.equals(name) && (question.type == TYPE.A || question.type == TYPE.AAAA))
294                continue;
295
296            IpResultSet res = null;
297            try {
298                res = resolveIpRecursive(resolutionState, name);
299            } catch (IOException e) {
300                resolutionState.decrementSteps();
301                ioExceptions.add(e);
302            }
303            if (res == null) {
304                continue;
305            }
306
307            for (InetAddress target : res.addresses) {
308                DnsMessage recursive = null;
309                try {
310                    recursive = queryRecursive(resolutionState, q, target, record.name);
311                } catch (IOException e) {
312                    resolutionState.decrementSteps();
313                    ioExceptions.add(e);
314                    continue;
315                }
316                return recursive;
317            }
318        }
319
320        MultipleIoException.throwIfRequired(ioExceptions);
321
322        // TODO throw exception here? Reaching this point would mean we did not receive an authoritative answer, nor
323        // where we able to find glue records or the IPs of the next nameservers.
324        return null;
325    }
326
327    private IpResultSet resolveIpRecursive(ResolutionState resolutionState, DnsName name) throws IOException {
328        IpResultSet.Builder res = newIpResultSetBuilder();
329
330        if (ipVersionSetting.v4) {
331            // TODO Try to retrieve A records for name out from cache.
332            Question question = new Question(name, TYPE.A);
333            final DnsMessage query = getQueryFor(question);
334            DnsMessage aMessage = queryRecursive(resolutionState, query);
335            if (aMessage != null) {
336                for (Record<? extends Data> answer : aMessage.answerSection) {
337                    if (answer.isAnswer(question)) {
338                        InetAddress inetAddress = inetAddressFromRecord(name.ace, (A) answer.payloadData);
339                        res.ipv4Addresses.add(inetAddress);
340                    } else if (answer.type == TYPE.CNAME && answer.name.equals(name)) {
341                        return resolveIpRecursive(resolutionState, ((RRWithTarget) answer.payloadData).target);
342                    }
343                }
344            }
345        }
346
347        if (ipVersionSetting.v6) {
348            // TODO Try to retrieve AAAA records for name out from cache.
349            Question question = new Question(name, TYPE.AAAA);
350            final DnsMessage query = getQueryFor(question);
351            DnsMessage aMessage = queryRecursive(resolutionState, query);
352            if (aMessage != null) {
353                for (Record<? extends Data> answer : aMessage.answerSection) {
354                    if (answer.isAnswer(question)) {
355                        InetAddress inetAddress = inetAddressFromRecord(name.ace, (AAAA) answer.payloadData);
356                        res.ipv6Addresses.add(inetAddress);
357                    } else if (answer.type == TYPE.CNAME && answer.name.equals(name)) {
358                        return resolveIpRecursive(resolutionState, ((RRWithTarget) answer.payloadData).target);
359                    }
360                }
361            }
362        }
363
364        return res.build();
365    }
366
367    @SuppressWarnings("incomplete-switch")
368    private IpResultSet searchAdditional(DnsMessage message, DnsName name) {
369        IpResultSet.Builder res = newIpResultSetBuilder();
370        for (Record<? extends Data> record : message.additionalSection) {
371            if (!record.name.equals(name)) {
372                continue;
373            }
374            switch (record.type) {
375            case A:
376                res.ipv4Addresses.add(inetAddressFromRecord(name.ace, ((A) record.payloadData)));
377                break;
378            case AAAA:
379                res.ipv6Addresses.add(inetAddressFromRecord(name.ace, ((AAAA) record.payloadData)));
380                break;
381            }
382        }
383        return res.build();
384    }
385
386    private static InetAddress inetAddressFromRecord(String name, A recordPayload) {
387        try {
388            return InetAddress.getByAddress(name, recordPayload.getIp());
389        } catch (UnknownHostException e) {
390            // This will never happen
391            throw new RuntimeException(e);
392        }
393    }
394
395    private static InetAddress inetAddressFromRecord(String name, AAAA recordPayload) {
396        try {
397            return InetAddress.getByAddress(name, recordPayload.getIp());
398        } catch (UnknownHostException e) {
399            // This will never happen
400            throw new RuntimeException(e);
401        }
402    }
403
404    public static List<InetAddress> getRootServer(char rootServerId) {
405        return getRootServer(rootServerId, DEFAULT_IP_VERSION_SETTING);
406    }
407
408    public static List<InetAddress> getRootServer(char rootServerId, IpVersionSetting setting) {
409        InetAddress ipv4Root = IPV4_ROOT_SERVER_MAP.get(rootServerId);
410        InetAddress ipv6Root = IPV6_ROOT_SERVER_MAP.get(rootServerId);
411        List<InetAddress> res = new ArrayList<>(2);
412        switch (setting) {
413        case v4only:
414            if (ipv4Root != null) {
415                res.add(ipv4Root);
416            }
417            break;
418        case v6only:
419            if (ipv6Root != null) {
420                res.add(ipv6Root);
421            }
422            break;
423        case v4v6:
424            if (ipv4Root != null) {
425                res.add(ipv4Root);
426            }
427            if (ipv6Root != null) {
428                res.add(ipv6Root);
429            }
430            break;
431        case v6v4:
432            if (ipv6Root != null) {
433                res.add(ipv6Root);
434            }
435            if (ipv4Root != null) {
436                res.add(ipv4Root);
437            }
438            break;
439        }
440        return res;
441    }
442
443    private static Inet4Address rootServerInet4Address(char rootServerId, int addr0, int addr1, int addr2, int addr3) {
444        Inet4Address inetAddress;
445        String name = rootServerId + ".root-servers.net";
446            try {
447                inetAddress = (Inet4Address) InetAddress.getByAddress(name, new byte[] { (byte) addr0, (byte) addr1, (byte) addr2,
448                        (byte) addr3 });
449                IPV4_ROOT_SERVER_MAP.put(rootServerId, inetAddress);
450            } catch (UnknownHostException e) {
451                // This should never happen, if it does it's our fault!
452                throw new RuntimeException(e);
453            }
454
455        return inetAddress;
456    }
457
458    private static Inet6Address rootServerInet6Address(char rootServerId, int addr0, int addr1, int addr2, int addr3, int addr4, int addr5, int addr6, int addr7) {
459        Inet6Address inetAddress;
460        String name = rootServerId + ".root-servers.net";
461            try {
462                inetAddress = (Inet6Address) InetAddress.getByAddress(name, new byte[]{
463                        // @formatter:off
464                        (byte) (addr0 >> 8), (byte) addr0, (byte) (addr1 >> 8), (byte) addr1,
465                        (byte) (addr2 >> 8), (byte) addr2, (byte) (addr3 >> 8), (byte) addr3,
466                        (byte) (addr4 >> 8), (byte) addr4, (byte) (addr5 >> 8), (byte) addr5,
467                        (byte) (addr6 >> 8), (byte) addr6, (byte) (addr7 >> 8), (byte) addr7
468                        // @formatter:on
469                });
470                IPV6_ROOT_SERVER_MAP.put(rootServerId, inetAddress);
471            } catch (UnknownHostException e) {
472                // This should never happen, if it does it's our fault!
473                throw new RuntimeException(e);
474            }
475        return inetAddress;
476    }
477
478    @Override
479    protected boolean isResponseCacheable(Question q, DnsMessage dnsMessage) {
480        return dnsMessage.authoritativeAnswer;
481    }
482
483    @Override
484    protected DnsMessage.Builder newQuestion(DnsMessage.Builder message) {
485        message.setRecursionDesired(false);
486        message.getEdnsBuilder().setUdpPayloadSize(dataSource.getUdpPayloadSize());
487        return message;
488    }
489
490    private IpResultSet.Builder newIpResultSetBuilder() {
491        return new IpResultSet.Builder(this.insecureRandom);
492    }
493
494    private static class IpResultSet {
495
496        final List<InetAddress> addresses;
497
498        private IpResultSet(List<InetAddress> ipv4Addresses, List<InetAddress> ipv6Addresses, Random random) {
499            int size;
500            switch (DEFAULT_IP_VERSION_SETTING) {
501            case v4only:
502                size = ipv4Addresses.size();
503                break;
504            case v6only:
505                size = ipv6Addresses.size();
506                break;
507            case v4v6:
508            case v6v4:
509            default:
510                size = ipv4Addresses.size() + ipv6Addresses.size();
511                break;
512            }
513
514            if (size == 0) {
515                // Fast-path in case there were no addresses, which could happen e.g., if the NS records where not
516                // glued.
517                addresses = Collections.emptyList();
518            } else {
519                // Shuffle the addresses first, so that the load is better balanced.
520                if (DEFAULT_IP_VERSION_SETTING.v4) {
521                    Collections.shuffle(ipv4Addresses, random);
522                }
523                if (DEFAULT_IP_VERSION_SETTING.v6) {
524                    Collections.shuffle(ipv6Addresses, random);
525                }
526
527                List<InetAddress> addresses = new ArrayList<>(size);
528
529                // Now add the shuffled addresses to the result list.
530                switch (DEFAULT_IP_VERSION_SETTING) {
531                case v4only:
532                    addresses.addAll(ipv4Addresses);
533                    break;
534                case v6only:
535                    addresses.addAll(ipv6Addresses);
536                    break;
537                case v4v6:
538                    addresses.addAll(ipv4Addresses);
539                    addresses.addAll(ipv6Addresses);
540                    break;
541                case v6v4:
542                    addresses.addAll(ipv6Addresses);
543                    addresses.addAll(ipv4Addresses);
544                    break;
545                }
546
547                this.addresses = Collections.unmodifiableList(addresses);
548            }
549        }
550
551        private static class Builder {
552            private final Random random;
553            private final List<InetAddress> ipv4Addresses = new ArrayList<>(8);
554            private final List<InetAddress> ipv6Addresses = new ArrayList<>(8);
555
556            private Builder(Random random) {
557                this.random = random;
558            }
559
560            public IpResultSet build() {
561                return new IpResultSet(ipv4Addresses, ipv6Addresses, random);
562            }
563        }
564    }
565
566    protected static void abortIfFatal(IOException ioException) throws IOException {
567        if (ioException instanceof LoopDetected) {
568            throw ioException;
569        }
570    }
571
572}