1/**
2 * $Revision: 1456 $
3 * $Date: 2005-06-01 22:04:54 -0700 (Wed, 01 Jun 2005) $
4 *
5 * Copyright 2003-2005 Jive Software.
6 *
7 * All rights reserved. Licensed under the Apache License, Version 2.0 (the "License");
8 * you may not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 *     http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 */
19
20package org.jivesoftware.smack.util;
21
22import java.util.ArrayList;
23import java.util.Collections;
24import java.util.LinkedList;
25import java.util.List;
26import java.util.Map;
27import java.util.SortedMap;
28import java.util.TreeMap;
29
30import org.jivesoftware.smack.util.dns.DNSResolver;
31import org.jivesoftware.smack.util.dns.HostAddress;
32import org.jivesoftware.smack.util.dns.SRVRecord;
33
34/**
35 * Utility class to perform DNS lookups for XMPP services.
36 *
37 * @author Matt Tucker
38 */
39public class DNSUtil {
40
41    /**
42     * Create a cache to hold the 100 most recently accessed DNS lookups for a period of
43     * 10 minutes.
44     */
45    private static Map<String, List<HostAddress>> cache = new Cache<String, List<HostAddress>>(100, 1000*60*10);
46
47    private static DNSResolver dnsResolver = null;
48
49    /**
50     * Set the DNS resolver that should be used to perform DNS lookups.
51     *
52     * @param resolver
53     */
54    public static void setDNSResolver(DNSResolver resolver) {
55        dnsResolver = resolver;
56    }
57
58    /**
59     * Returns the current DNS resolved used to perform DNS lookups.
60     *
61     * @return
62     */
63    public static DNSResolver getDNSResolver() {
64        return dnsResolver;
65    }
66
67    /**
68     * Returns a list of HostAddresses under which the specified XMPP server can be
69     * reached at for client-to-server communication. A DNS lookup for a SRV
70     * record in the form "_xmpp-client._tcp.example.com" is attempted, according
71     * to section 14.4 of RFC 3920. If that lookup fails, a lookup in the older form
72     * of "_jabber._tcp.example.com" is attempted since servers that implement an
73     * older version of the protocol may be listed using that notation. If that
74     * lookup fails as well, it's assumed that the XMPP server lives at the
75     * host resolved by a DNS lookup at the specified domain on the default port
76     * of 5222.<p>
77     *
78     * As an example, a lookup for "example.com" may return "im.example.com:5269".
79     *
80     * @param domain the domain.
81     * @return List of HostAddress, which encompasses the hostname and port that the
82     *      XMPP server can be reached at for the specified domain.
83     */
84    public static List<HostAddress> resolveXMPPDomain(String domain) {
85        return resolveDomain(domain, 'c');
86    }
87
88    /**
89     * Returns a list of HostAddresses under which the specified XMPP server can be
90     * reached at for server-to-server communication. A DNS lookup for a SRV
91     * record in the form "_xmpp-server._tcp.example.com" is attempted, according
92     * to section 14.4 of RFC 3920. If that lookup fails, a lookup in the older form
93     * of "_jabber._tcp.example.com" is attempted since servers that implement an
94     * older version of the protocol may be listed using that notation. If that
95     * lookup fails as well, it's assumed that the XMPP server lives at the
96     * host resolved by a DNS lookup at the specified domain on the default port
97     * of 5269.<p>
98     *
99     * As an example, a lookup for "example.com" may return "im.example.com:5269".
100     *
101     * @param domain the domain.
102     * @return List of HostAddress, which encompasses the hostname and port that the
103     *      XMPP server can be reached at for the specified domain.
104     */
105    public static List<HostAddress> resolveXMPPServerDomain(String domain) {
106        return resolveDomain(domain, 's');
107    }
108
109    private static List<HostAddress> resolveDomain(String domain, char keyPrefix) {
110        // Prefix the key with 's' to distinguish him from the client domain lookups
111        String key = keyPrefix + domain;
112        // Return item from cache if it exists.
113        if (cache.containsKey(key)) {
114            List<HostAddress> addresses = cache.get(key);
115            if (addresses != null) {
116                return addresses;
117            }
118        }
119
120        if (dnsResolver == null)
121            throw new IllegalStateException("No DNS resolver active.");
122
123        List<HostAddress> addresses = new ArrayList<HostAddress>();
124
125        // Step one: Do SRV lookups
126        String srvDomain;
127        if (keyPrefix == 's') {
128            srvDomain = "_xmpp-server._tcp." + domain;
129        } else if (keyPrefix == 'c') {
130            srvDomain = "_xmpp-client._tcp." + domain;
131        } else {
132            srvDomain = domain;
133        }
134        List<SRVRecord> srvRecords = dnsResolver.lookupSRVRecords(srvDomain);
135        List<HostAddress> sortedRecords = sortSRVRecords(srvRecords);
136        if (sortedRecords != null)
137            addresses.addAll(sortedRecords);
138
139        // Step two: Add the hostname to the end of the list
140        addresses.add(new HostAddress(domain));
141
142        // Add item to cache.
143        cache.put(key, addresses);
144
145        return addresses;
146    }
147
148    /**
149     * Sort a given list of SRVRecords as described in RFC 2782
150     * Note that we follow the RFC with one exception. In a group of the same priority, only the first entry
151     * is calculated by random. The others are ore simply ordered by their priority.
152     *
153     * @param records
154     * @return
155     */
156    protected static List<HostAddress> sortSRVRecords(List<SRVRecord> records) {
157        // RFC 2782, Usage rules: "If there is precisely one SRV RR, and its Target is "."
158        // (the root domain), abort."
159        if (records.size() == 1 && records.get(0).getFQDN().equals("."))
160            return null;
161
162        // sorting the records improves the performance of the bisection later
163        Collections.sort(records);
164
165        // create the priority buckets
166        SortedMap<Integer, List<SRVRecord>> buckets = new TreeMap<Integer, List<SRVRecord>>();
167        for (SRVRecord r : records) {
168            Integer priority = r.getPriority();
169            List<SRVRecord> bucket = buckets.get(priority);
170            // create the list of SRVRecords if it doesn't exist
171            if (bucket == null) {
172                bucket = new LinkedList<SRVRecord>();
173                buckets.put(priority, bucket);
174            }
175            bucket.add(r);
176        }
177
178        List<HostAddress> res = new ArrayList<HostAddress>(records.size());
179
180        for (Integer priority : buckets.keySet()) {
181            List<SRVRecord> bucket = buckets.get(priority);
182            int bucketSize;
183            while ((bucketSize = bucket.size()) > 0) {
184                int[] totals = new int[bucket.size()];
185                int running_total = 0;
186                int count = 0;
187                int zeroWeight = 1;
188
189                for (SRVRecord r : bucket) {
190                    if (r.getWeight() > 0)
191                        zeroWeight = 0;
192                }
193
194                for (SRVRecord r : bucket) {
195                    running_total += (r.getWeight() + zeroWeight);
196                    totals[count] = running_total;
197                    count++;
198                }
199                int selectedPos;
200                if (running_total == 0) {
201                    // If running total is 0, then all weights in this priority
202                    // group are 0. So we simply select one of the weights randomly
203                    // as the other 'normal' algorithm is unable to handle this case
204                    selectedPos = (int) (Math.random() * bucketSize);
205                } else {
206                    double rnd = Math.random() * running_total;
207                    selectedPos = bisect(totals, rnd);
208                }
209                // add the SRVRecord that was randomly chosen on it's weight
210                // to the start of the result list
211                SRVRecord chosenSRVRecord = bucket.remove(selectedPos);
212                res.add(chosenSRVRecord);
213            }
214        }
215
216        return res;
217    }
218
219    // TODO this is not yet really bisection just a stupid linear search
220    private static int bisect(int[] array, double value) {
221        int pos = 0;
222        for (int element : array) {
223            if (value < element)
224                break;
225            pos++;
226        }
227        return pos;
228    }
229}