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 402