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