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 continue; 382 SourceAddressInfo& info = source_map_[src.address()]; 383 // Note: no known way to fill in |native| and |home|. 384 info.native = info.home = info.deprecated = false; 385 if (ifa->ifa_addr->sa_family == AF_INET6) { 386 struct in6_ifreq ifr = {}; 387 strncpy(ifr.ifr_name, ifa->ifa_name, sizeof(ifr.ifr_name) - 1); 388 DCHECK_LE(ifa->ifa_addr->sa_len, sizeof(ifr.ifr_ifru.ifru_addr)); 389 memcpy(&ifr.ifr_ifru.ifru_addr, ifa->ifa_addr, ifa->ifa_addr->sa_len); 390 int rv = ioctl(ioctl_socket, SIOCGIFAFLAG_IN6, &ifr); 391 if (rv >= 0) { 392 info.deprecated = ifr.ifr_ifru.ifru_flags & IN6_IFF_DEPRECATED; 393 } else { 394 LOG(WARNING) << "SIOCGIFAFLAG_IN6 failed " << rv; 395 } 396 } 397 if (ifa->ifa_netmask) { 398 IPEndPoint netmask; 399 if (netmask.FromSockAddr(ifa->ifa_netmask, ifa->ifa_addr->sa_len)) { 400 info.prefix_length = MaskPrefixLength(netmask.address()); 401 } else { 402 LOG(WARNING) << "FromSockAddr failed on netmask"; 403 } 404 } 405 FillPolicy(src.address(), &info); 406 } 407 freeifaddrs(addrs); 408 close(ioctl_socket); 409 #endif 410 } 411 412 void AddressSorterPosix::FillPolicy(const IPAddressNumber& address, 413 SourceAddressInfo* info) const { 414 DCHECK(CalledOnValidThread()); 415 info->scope = GetScope(ipv4_scope_table_, address); 416 info->label = GetPolicyValue(label_table_, address); 417 } 418 419 // static 420 scoped_ptr<AddressSorter> AddressSorter::CreateAddressSorter() { 421 return scoped_ptr<AddressSorter>( 422 new AddressSorterPosix(ClientSocketFactory::GetDefaultFactory())); 423 } 424 425 } // namespace net 426 427