net/dns/address_sorter_posix.cc

   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
  29 namespace net {
  30
  31 namespace {
  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.
  39 bool 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.
  45 AddressSorterPosix::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).
  55 unsigned 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
  70 bool IsIPv6Multicast(const IPAddressNumber& address) {
  71   DCHECK_EQ(kIPv6AddressSize, address.size());
  72   return address[0] == 0xFF;
  73 }
  74
  75 AddressSorterPosix::AddressScope GetIPv6MulticastScope(
  76     const IPAddressNumber& address) {
  77   DCHECK_EQ(kIPv6AddressSize, address.size());
  78   return static_cast<AddressSorterPosix::AddressScope>(address[1] & 0x0F);
  79 }
  80
  81 bool 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
  91 bool 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
  97 bool 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
 103 AddressSorterPosix::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.
 126 AddressSorterPosix::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
 147 AddressSorterPosix::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.
 169 AddressSorterPosix::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
 177 struct 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.
 188 bool 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
 240 AddressSorterPosix::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
 252 AddressSorterPosix::~AddressSorterPosix() {
 253   NetworkChangeNotifier::RemoveIPAddressObserver(this);
 254 }
 255
 256 void 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
 318 void 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
 387 void 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
 395 scoped_ptr<AddressSorter> AddressSorter::CreateAddressSorter() {
 396   return scoped_ptr<AddressSorter>(
 397       new AddressSorterPosix(ClientSocketFactory::GetDefaultFactory()));
 398 }
 399
 400 }  // namespace net
 401