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/address_sorter_posix.h"
6
7#include <netinet/in.h>
8
9#if defined(OS_MACOSX) || defined(OS_BSD)
10#include <sys/socket.h>  // Must be included before ifaddrs.h.
11#include <ifaddrs.h>
12#include <net/if.h>
13#include <netinet/in_var.h>
14#include <string.h>
15#include <sys/ioctl.h>
16#endif
17
18#include <algorithm>
19
20#include "base/logging.h"
21#include "base/memory/scoped_vector.h"
22#include "net/socket/client_socket_factory.h"
23#include "net/udp/datagram_client_socket.h"
24
25#if defined(OS_LINUX)
26#include "net/base/address_tracker_linux.h"
27#endif
28
29namespace net {
30
31namespace {
32
33// Address sorting is performed according to RFC3484 with revisions.
34// http://tools.ietf.org/html/draft-ietf-6man-rfc3484bis-06
35// Precedence and label are separate to support override through /etc/gai.conf.
36
37// Returns true if |p1| should precede |p2| in the table.
38// Sorts table by decreasing prefix size to allow longest prefix matching.
39bool ComparePolicy(const AddressSorterPosix::PolicyEntry& p1,
40                   const AddressSorterPosix::PolicyEntry& p2) {
41  return p1.prefix_length > p2.prefix_length;
42}
43
44// Creates sorted PolicyTable from |table| with |size| entries.
45AddressSorterPosix::PolicyTable LoadPolicy(
46    AddressSorterPosix::PolicyEntry* table,
47    size_t size) {
48  AddressSorterPosix::PolicyTable result(table, table + size);
49  std::sort(result.begin(), result.end(), ComparePolicy);
50  return result;
51}
52
53// Search |table| for matching prefix of |address|. |table| must be sorted by
54// descending prefix (prefix of another prefix must be later in table).
55unsigned GetPolicyValue(const AddressSorterPosix::PolicyTable& table,
56                        const IPAddressNumber& address) {
57  if (address.size() == kIPv4AddressSize)
58    return GetPolicyValue(table, ConvertIPv4NumberToIPv6Number(address));
59  for (unsigned i = 0; i < table.size(); ++i) {
60    const AddressSorterPosix::PolicyEntry& entry = table[i];
61    IPAddressNumber prefix(entry.prefix, entry.prefix + kIPv6AddressSize);
62    if (IPNumberMatchesPrefix(address, prefix, entry.prefix_length))
63      return entry.value;
64  }
65  NOTREACHED();
66  // The last entry is the least restrictive, so assume it's default.
67  return table.back().value;
68}
69
70bool IsIPv6Multicast(const IPAddressNumber& address) {
71  DCHECK_EQ(kIPv6AddressSize, address.size());
72  return address[0] == 0xFF;
73}
74
75AddressSorterPosix::AddressScope GetIPv6MulticastScope(
76    const IPAddressNumber& address) {
77  DCHECK_EQ(kIPv6AddressSize, address.size());
78  return static_cast<AddressSorterPosix::AddressScope>(address[1] & 0x0F);
79}
80
81bool IsIPv6Loopback(const IPAddressNumber& address) {
82  DCHECK_EQ(kIPv6AddressSize, address.size());
83  // IN6_IS_ADDR_LOOPBACK
84  unsigned char kLoopback[kIPv6AddressSize] = {
85    0, 0, 0, 0, 0, 0, 0, 0,
86    0, 0, 0, 0, 0, 0, 0, 1,
87  };
88  return address == IPAddressNumber(kLoopback, kLoopback + kIPv6AddressSize);
89}
90
91bool IsIPv6LinkLocal(const IPAddressNumber& address) {
92  DCHECK_EQ(kIPv6AddressSize, address.size());
93  // IN6_IS_ADDR_LINKLOCAL
94  return (address[0] == 0xFE) && ((address[1] & 0xC0) == 0x80);
95}
96
97bool IsIPv6SiteLocal(const IPAddressNumber& address) {
98  DCHECK_EQ(kIPv6AddressSize, address.size());
99  // IN6_IS_ADDR_SITELOCAL
100  return (address[0] == 0xFE) && ((address[1] & 0xC0) == 0xC0);
101}
102
103AddressSorterPosix::AddressScope GetScope(
104    const AddressSorterPosix::PolicyTable& ipv4_scope_table,
105    const IPAddressNumber& address) {
106  if (address.size() == kIPv6AddressSize) {
107    if (IsIPv6Multicast(address)) {
108      return GetIPv6MulticastScope(address);
109    } else if (IsIPv6Loopback(address) || IsIPv6LinkLocal(address)) {
110      return AddressSorterPosix::SCOPE_LINKLOCAL;
111    } else if (IsIPv6SiteLocal(address)) {
112      return AddressSorterPosix::SCOPE_SITELOCAL;
113    } else {
114      return AddressSorterPosix::SCOPE_GLOBAL;
115    }
116  } else if (address.size() == kIPv4AddressSize) {
117    return static_cast<AddressSorterPosix::AddressScope>(
118        GetPolicyValue(ipv4_scope_table, address));
119  } else {
120    NOTREACHED();
121    return AddressSorterPosix::SCOPE_NODELOCAL;
122  }
123}
124
125// Default policy table. RFC 3484, Section 2.1.
126AddressSorterPosix::PolicyEntry kDefaultPrecedenceTable[] = {
127  // ::1/128 -- loopback
128  { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, 128, 50 },
129  // ::/0 -- any
130  { { }, 0, 40 },
131  // ::ffff:0:0/96 -- IPv4 mapped
132  { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF }, 96, 35 },
133  // 2002::/16 -- 6to4
134  { { 0x20, 0x02, }, 16, 30 },
135  // 2001::/32 -- Teredo
136  { { 0x20, 0x01, 0, 0 }, 32, 5 },
137  // fc00::/7 -- unique local address
138  { { 0xFC }, 7, 3 },
139  // ::/96 -- IPv4 compatible
140  { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 96, 1 },
141  // fec0::/10 -- site-local expanded scope
142  { { 0xFE, 0xC0 }, 10, 1 },
143  // 3ffe::/16 -- 6bone
144  { { 0x3F, 0xFE }, 16, 1 },
145};
146
147AddressSorterPosix::PolicyEntry kDefaultLabelTable[] = {
148  // ::1/128 -- loopback
149  { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, 128, 0 },
150  // ::/0 -- any
151  { { }, 0, 1 },
152  // ::ffff:0:0/96 -- IPv4 mapped
153  { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF }, 96, 4 },
154  // 2002::/16 -- 6to4
155  { { 0x20, 0x02, }, 16, 2 },
156  // 2001::/32 -- Teredo
157  { { 0x20, 0x01, 0, 0 }, 32, 5 },
158  // fc00::/7 -- unique local address
159  { { 0xFC }, 7, 13 },
160  // ::/96 -- IPv4 compatible
161  { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 96, 3 },
162  // fec0::/10 -- site-local expanded scope
163  { { 0xFE, 0xC0 }, 10, 11 },
164  // 3ffe::/16 -- 6bone
165  { { 0x3F, 0xFE }, 16, 12 },
166};
167
168// Default mapping of IPv4 addresses to scope.
169AddressSorterPosix::PolicyEntry kDefaultIPv4ScopeTable[] = {
170  { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF, 0x7F }, 104,
171      AddressSorterPosix::SCOPE_LINKLOCAL },
172  { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF, 0xA9, 0xFE }, 112,
173      AddressSorterPosix::SCOPE_LINKLOCAL },
174  { { }, 0, AddressSorterPosix::SCOPE_GLOBAL },
175};
176
177struct DestinationInfo {
178  IPAddressNumber address;
179  AddressSorterPosix::AddressScope scope;
180  unsigned precedence;
181  unsigned label;
182  const AddressSorterPosix::SourceAddressInfo* src;
183  unsigned common_prefix_length;
184};
185
186// Returns true iff |dst_a| should precede |dst_b| in the address list.
187// RFC 3484, section 6.
188bool CompareDestinations(const DestinationInfo* dst_a,
189                         const DestinationInfo* dst_b) {
190  // Rule 1: Avoid unusable destinations.
191  // Unusable destinations are already filtered out.
192  DCHECK(dst_a->src);
193  DCHECK(dst_b->src);
194
195  // Rule 2: Prefer matching scope.
196  bool scope_match1 = (dst_a->src->scope == dst_a->scope);
197  bool scope_match2 = (dst_b->src->scope == dst_b->scope);
198  if (scope_match1 != scope_match2)
199    return scope_match1;
200
201  // Rule 3: Avoid deprecated addresses.
202  if (dst_a->src->deprecated != dst_b->src->deprecated)
203    return !dst_a->src->deprecated;
204
205  // Rule 4: Prefer home addresses.
206  if (dst_a->src->home != dst_b->src->home)
207    return dst_a->src->home;
208
209  // Rule 5: Prefer matching label.
210  bool label_match1 = (dst_a->src->label == dst_a->label);
211  bool label_match2 = (dst_b->src->label == dst_b->label);
212  if (label_match1 != label_match2)
213    return label_match1;
214
215  // Rule 6: Prefer higher precedence.
216  if (dst_a->precedence != dst_b->precedence)
217    return dst_a->precedence > dst_b->precedence;
218
219  // Rule 7: Prefer native transport.
220  if (dst_a->src->native != dst_b->src->native)
221    return dst_a->src->native;
222
223  // Rule 8: Prefer smaller scope.
224  if (dst_a->scope != dst_b->scope)
225    return dst_a->scope < dst_b->scope;
226
227  // Rule 9: Use longest matching prefix. Only for matching address families.
228  if (dst_a->address.size() == dst_b->address.size()) {
229    if (dst_a->common_prefix_length != dst_b->common_prefix_length)
230      return dst_a->common_prefix_length > dst_b->common_prefix_length;
231  }
232
233  // Rule 10: Leave the order unchanged.
234  // stable_sort takes care of that.
235  return false;
236}
237
238}  // namespace
239
240AddressSorterPosix::AddressSorterPosix(ClientSocketFactory* socket_factory)
241    : socket_factory_(socket_factory),
242      precedence_table_(LoadPolicy(kDefaultPrecedenceTable,
243                                   arraysize(kDefaultPrecedenceTable))),
244      label_table_(LoadPolicy(kDefaultLabelTable,
245                              arraysize(kDefaultLabelTable))),
246      ipv4_scope_table_(LoadPolicy(kDefaultIPv4ScopeTable,
247                              arraysize(kDefaultIPv4ScopeTable))) {
248  NetworkChangeNotifier::AddIPAddressObserver(this);
249  OnIPAddressChanged();
250}
251
252AddressSorterPosix::~AddressSorterPosix() {
253  NetworkChangeNotifier::RemoveIPAddressObserver(this);
254}
255
256void AddressSorterPosix::Sort(const AddressList& list,
257                              const CallbackType& callback) const {
258  DCHECK(CalledOnValidThread());
259  ScopedVector<DestinationInfo> sort_list;
260
261  for (size_t i = 0; i < list.size(); ++i) {
262    scoped_ptr<DestinationInfo> info(new DestinationInfo());
263    info->address = list[i].address();
264    info->scope = GetScope(ipv4_scope_table_, info->address);
265    info->precedence = GetPolicyValue(precedence_table_, info->address);
266    info->label = GetPolicyValue(label_table_, info->address);
267
268    // Each socket can only be bound once.
269    scoped_ptr<DatagramClientSocket> socket(
270        socket_factory_->CreateDatagramClientSocket(
271            DatagramSocket::DEFAULT_BIND,
272            RandIntCallback(),
273            NULL /* NetLog */,
274            NetLog::Source()));
275
276    // Even though no packets are sent, cannot use port 0 in Connect.
277    IPEndPoint dest(info->address, 80 /* port */);
278    int rv = socket->Connect(dest);
279    if (rv != OK) {
280      VLOG(1) << "Could not connect to " << dest.ToStringWithoutPort()
281              << " reason " << rv;
282      continue;
283    }
284    // Filter out unusable destinations.
285    IPEndPoint src;
286    rv = socket->GetLocalAddress(&src);
287    if (rv != OK) {
288      LOG(WARNING) << "Could not get local address for "
289                   << dest.ToStringWithoutPort() << " reason " << rv;
290      continue;
291    }
292
293    SourceAddressInfo& src_info = source_map_[src.address()];
294    if (src_info.scope == SCOPE_UNDEFINED) {
295      // If |source_info_| is out of date, |src| might be missing, but we still
296      // want to sort, even though the HostCache will be cleared soon.
297      FillPolicy(src.address(), &src_info);
298    }
299    info->src = &src_info;
300
301    if (info->address.size() == src.address().size()) {
302      info->common_prefix_length = std::min(
303          CommonPrefixLength(info->address, src.address()),
304          info->src->prefix_length);
305    }
306    sort_list.push_back(info.release());
307  }
308
309  std::stable_sort(sort_list.begin(), sort_list.end(), CompareDestinations);
310
311  AddressList result;
312  for (size_t i = 0; i < sort_list.size(); ++i)
313    result.push_back(IPEndPoint(sort_list[i]->address, 0 /* port */));
314
315  callback.Run(true, result);
316}
317
318void AddressSorterPosix::OnIPAddressChanged() {
319  DCHECK(CalledOnValidThread());
320  source_map_.clear();
321#if defined(OS_LINUX)
322  const internal::AddressTrackerLinux* tracker =
323      NetworkChangeNotifier::GetAddressTracker();
324  if (!tracker)
325    return;
326  typedef internal::AddressTrackerLinux::AddressMap AddressMap;
327  AddressMap map = tracker->GetAddressMap();
328  for (AddressMap::const_iterator it = map.begin(); it != map.end(); ++it) {
329    const IPAddressNumber& address = it->first;
330    const struct ifaddrmsg& msg = it->second;
331    SourceAddressInfo& info = source_map_[address];
332    info.native = false;  // TODO(szym): obtain this via netlink.
333    info.deprecated = msg.ifa_flags & IFA_F_DEPRECATED;
334    info.home = msg.ifa_flags & IFA_F_HOMEADDRESS;
335    info.prefix_length = msg.ifa_prefixlen;
336    FillPolicy(address, &info);
337  }
338#elif defined(OS_MACOSX) || defined(OS_BSD)
339  // It's not clear we will receive notification when deprecated flag changes.
340  // Socket for ioctl.
341  int ioctl_socket = socket(AF_INET6, SOCK_DGRAM, 0);
342  if (ioctl_socket < 0)
343    return;
344
345  struct ifaddrs* addrs;
346  int rv = getifaddrs(&addrs);
347  if (rv < 0) {
348    LOG(WARNING) << "getifaddrs failed " << rv;
349    close(ioctl_socket);
350    return;
351  }
352
353  for (struct ifaddrs* ifa = addrs; ifa != NULL; ifa = ifa->ifa_next) {
354    IPEndPoint src;
355    if (!src.FromSockAddr(ifa->ifa_addr, ifa->ifa_addr->sa_len))
356      continue;
357    SourceAddressInfo& info = source_map_[src.address()];
358    // Note: no known way to fill in |native| and |home|.
359    info.native = info.home = info.deprecated = false;
360    if (ifa->ifa_addr->sa_family == AF_INET6) {
361      struct in6_ifreq ifr = {};
362      strncpy(ifr.ifr_name, ifa->ifa_name, sizeof(ifr.ifr_name) - 1);
363      DCHECK_LE(ifa->ifa_addr->sa_len, sizeof(ifr.ifr_ifru.ifru_addr));
364      memcpy(&ifr.ifr_ifru.ifru_addr, ifa->ifa_addr, ifa->ifa_addr->sa_len);
365      int rv = ioctl(ioctl_socket, SIOCGIFAFLAG_IN6, &ifr);
366      if (rv >= 0) {
367        info.deprecated = ifr.ifr_ifru.ifru_flags & IN6_IFF_DEPRECATED;
368      } else {
369        LOG(WARNING) << "SIOCGIFAFLAG_IN6 failed " << rv;
370      }
371    }
372    if (ifa->ifa_netmask) {
373      IPEndPoint netmask;
374      if (netmask.FromSockAddr(ifa->ifa_netmask, ifa->ifa_addr->sa_len)) {
375        info.prefix_length = MaskPrefixLength(netmask.address());
376      } else {
377        LOG(WARNING) << "FromSockAddr failed on netmask";
378      }
379    }
380    FillPolicy(src.address(), &info);
381  }
382  freeifaddrs(addrs);
383  close(ioctl_socket);
384#endif
385}
386
387void AddressSorterPosix::FillPolicy(const IPAddressNumber& address,
388                                    SourceAddressInfo* info) const {
389  DCHECK(CalledOnValidThread());
390  info->scope = GetScope(ipv4_scope_table_, address);
391  info->label = GetPolicyValue(label_table_, address);
392}
393
394// static
395scoped_ptr<AddressSorter> AddressSorter::CreateAddressSorter() {
396  return scoped_ptr<AddressSorter>(
397      new AddressSorterPosix(ClientSocketFactory::GetDefaultFactory()));
398}
399
400}  // namespace net
401
402