1 // Copyright 2012 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifdef UNSAFE_BUFFERS_BUILD
6 // TODO(crbug.com/40284755): Remove this and spanify to fix the errors.
7 #pragma allow_unsafe_buffers
8 #endif
9
10 #include "net/dns/address_sorter_posix.h"
11
12 #include <netinet/in.h>
13
14 #include <memory>
15 #include <utility>
16 #include <vector>
17
18 #include "base/memory/raw_ptr.h"
19 #include "build/build_config.h"
20
21 #if BUILDFLAG(IS_APPLE) || BUILDFLAG(IS_BSD)
22 #include <sys/socket.h> // Must be included before ifaddrs.h.
23 #include <ifaddrs.h>
24 #include <net/if.h>
25 #include <string.h>
26 #include <sys/ioctl.h>
27 #if BUILDFLAG(IS_IOS)
28 // The code in the following header file is copied from [1]. This file has the
29 // minimum definitions needed to retrieve the IP attributes, since iOS SDK
30 // doesn't include a necessary header <netinet/in_var.h>.
31 // [1] https://chromium.googlesource.com/external/webrtc/+/master/rtc_base/mac_ifaddrs_converter.cc
32 #include "net/dns/netinet_in_var_ios.h"
33 #else
34 #include <netinet/in_var.h>
35 #endif // BUILDFLAG(IS_IOS)
36 #endif
37 #include <vector>
38
39 #include "base/containers/unique_ptr_adapters.h"
40 #include "base/logging.h"
41 #include "net/base/ip_endpoint.h"
42 #include "net/base/net_errors.h"
43 #include "net/log/net_log_source.h"
44 #include "net/socket/client_socket_factory.h"
45 #include "net/socket/datagram_client_socket.h"
46
47 #if BUILDFLAG(IS_LINUX) || BUILDFLAG(IS_CHROMEOS)
48 #include "net/base/address_tracker_linux.h"
49 #endif
50
51 namespace net {
52 namespace {
53 // Address sorting is performed according to RFC3484 with revisions.
54 // http://tools.ietf.org/html/draft-ietf-6man-rfc3484bis-06
55 // Precedence and label are separate to support override through
56 // /etc/gai.conf.
57
58 // Returns true if |p1| should precede |p2| in the table.
59 // Sorts table by decreasing prefix size to allow longest prefix matching.
ComparePolicy(const AddressSorterPosix::PolicyEntry & p1,const AddressSorterPosix::PolicyEntry & p2)60 bool ComparePolicy(const AddressSorterPosix::PolicyEntry& p1,
61 const AddressSorterPosix::PolicyEntry& p2) {
62 return p1.prefix_length > p2.prefix_length;
63 }
64
65 // Creates sorted PolicyTable from |table| with |size| entries.
LoadPolicy(const AddressSorterPosix::PolicyEntry * table,size_t size)66 AddressSorterPosix::PolicyTable LoadPolicy(
67 const AddressSorterPosix::PolicyEntry* table,
68 size_t size) {
69 AddressSorterPosix::PolicyTable result(table, table + size);
70 std::sort(result.begin(), result.end(), ComparePolicy);
71 return result;
72 }
73
74 // Search |table| for matching prefix of |address|. |table| must be sorted by
75 // descending prefix (prefix of another prefix must be later in table).
GetPolicyValue(const AddressSorterPosix::PolicyTable & table,const IPAddress & address)76 unsigned GetPolicyValue(const AddressSorterPosix::PolicyTable& table,
77 const IPAddress& address) {
78 if (address.IsIPv4())
79 return GetPolicyValue(table, ConvertIPv4ToIPv4MappedIPv6(address));
80 for (const auto& entry : table) {
81 IPAddress prefix(entry.prefix);
82 if (IPAddressMatchesPrefix(address, prefix, entry.prefix_length))
83 return entry.value;
84 }
85 NOTREACHED();
86 }
87
IsIPv6Multicast(const IPAddress & address)88 bool IsIPv6Multicast(const IPAddress& address) {
89 DCHECK(address.IsIPv6());
90 return address.bytes()[0] == 0xFF;
91 }
92
GetIPv6MulticastScope(const IPAddress & address)93 AddressSorterPosix::AddressScope GetIPv6MulticastScope(
94 const IPAddress& address) {
95 DCHECK(address.IsIPv6());
96 return static_cast<AddressSorterPosix::AddressScope>(address.bytes()[1] &
97 0x0F);
98 }
99
IsIPv6Loopback(const IPAddress & address)100 bool IsIPv6Loopback(const IPAddress& address) {
101 DCHECK(address.IsIPv6());
102 return address == IPAddress::IPv6Localhost();
103 }
104
IsIPv6LinkLocal(const IPAddress & address)105 bool IsIPv6LinkLocal(const IPAddress& address) {
106 DCHECK(address.IsIPv6());
107 // IN6_IS_ADDR_LINKLOCAL
108 return (address.bytes()[0] == 0xFE) && ((address.bytes()[1] & 0xC0) == 0x80);
109 }
110
IsIPv6SiteLocal(const IPAddress & address)111 bool IsIPv6SiteLocal(const IPAddress& address) {
112 DCHECK(address.IsIPv6());
113 // IN6_IS_ADDR_SITELOCAL
114 return (address.bytes()[0] == 0xFE) && ((address.bytes()[1] & 0xC0) == 0xC0);
115 }
116
GetScope(const AddressSorterPosix::PolicyTable & ipv4_scope_table,const IPAddress & address)117 AddressSorterPosix::AddressScope GetScope(
118 const AddressSorterPosix::PolicyTable& ipv4_scope_table,
119 const IPAddress& address) {
120 if (address.IsIPv6()) {
121 if (IsIPv6Multicast(address)) {
122 return GetIPv6MulticastScope(address);
123 } else if (IsIPv6Loopback(address) || IsIPv6LinkLocal(address)) {
124 return AddressSorterPosix::SCOPE_LINKLOCAL;
125 } else if (IsIPv6SiteLocal(address)) {
126 return AddressSorterPosix::SCOPE_SITELOCAL;
127 } else {
128 return AddressSorterPosix::SCOPE_GLOBAL;
129 }
130 } else if (address.IsIPv4()) {
131 return static_cast<AddressSorterPosix::AddressScope>(
132 GetPolicyValue(ipv4_scope_table, address));
133 } else {
134 NOTREACHED();
135 }
136 }
137
138 // Default policy table. RFC 3484, Section 2.1.
139 const AddressSorterPosix::PolicyEntry kDefaultPrecedenceTable[] = {
140 // ::1/128 -- loopback
141 {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}, 128, 50},
142 // ::/0 -- any
143 {{}, 0, 40},
144 // ::ffff:0:0/96 -- IPv4 mapped
145 {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF}, 96, 35},
146 // 2002::/16 -- 6to4
147 {{
148 0x20,
149 0x02,
150 },
151 16,
152 30},
153 // 2001::/32 -- Teredo
154 {{0x20, 0x01, 0, 0}, 32, 5},
155 // fc00::/7 -- unique local address
156 {{0xFC}, 7, 3},
157 // ::/96 -- IPv4 compatible
158 {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 96, 1},
159 // fec0::/10 -- site-local expanded scope
160 {{0xFE, 0xC0}, 10, 1},
161 // 3ffe::/16 -- 6bone
162 {{0x3F, 0xFE}, 16, 1},
163 };
164
165 const AddressSorterPosix::PolicyEntry kDefaultLabelTable[] = {
166 // ::1/128 -- loopback
167 {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}, 128, 0},
168 // ::/0 -- any
169 {{}, 0, 1},
170 // ::ffff:0:0/96 -- IPv4 mapped
171 {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF}, 96, 4},
172 // 2002::/16 -- 6to4
173 {{
174 0x20,
175 0x02,
176 },
177 16,
178 2},
179 // 2001::/32 -- Teredo
180 {{0x20, 0x01, 0, 0}, 32, 5},
181 // fc00::/7 -- unique local address
182 {{0xFC}, 7, 13},
183 // ::/96 -- IPv4 compatible
184 {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 96, 3},
185 // fec0::/10 -- site-local expanded scope
186 {{0xFE, 0xC0}, 10, 11},
187 // 3ffe::/16 -- 6bone
188 {{0x3F, 0xFE}, 16, 12},
189 };
190
191 // Default mapping of IPv4 addresses to scope.
192 const AddressSorterPosix::PolicyEntry kDefaultIPv4ScopeTable[] = {
193 {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF, 0x7F},
194 104,
195 AddressSorterPosix::SCOPE_LINKLOCAL},
196 {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF, 0xA9, 0xFE},
197 112,
198 AddressSorterPosix::SCOPE_LINKLOCAL},
199 {{}, 0, AddressSorterPosix::SCOPE_GLOBAL},
200 };
201
202 struct DestinationInfo {
203 IPEndPoint endpoint;
204 AddressSorterPosix::AddressScope scope;
205 unsigned precedence;
206 unsigned label;
207 AddressSorterPosix::SourceAddressInfo src;
208 std::unique_ptr<DatagramClientSocket> socket;
209 size_t common_prefix_length;
210 bool failed = false;
211 };
212
213 // Returns true iff |dst_a| should precede |dst_b| in the address list.
214 // RFC 3484, section 6.
CompareDestinations(const DestinationInfo & dst_a,const DestinationInfo & dst_b)215 bool CompareDestinations(const DestinationInfo& dst_a,
216 const DestinationInfo& dst_b) {
217 // Rule 1: Avoid unusable destinations.
218 // Nothing to do here because unusable destinations are already filtered out.
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
231 // Rule 4: Prefer home addresses.
232 if (dst_a.src.home != dst_b.src.home) {
233 return dst_a.src.home;
234 }
235
236 // Rule 5: Prefer matching label.
237 bool label_match1 = (dst_a.src.label == dst_a.label);
238 bool label_match2 = (dst_b.src.label == dst_b.label);
239 if (label_match1 != label_match2)
240 return label_match1;
241
242 // Rule 6: Prefer higher precedence.
243 if (dst_a.precedence != dst_b.precedence)
244 return dst_a.precedence > dst_b.precedence;
245
246 // Rule 7: Prefer native transport.
247 if (dst_a.src.native != dst_b.src.native) {
248 return dst_a.src.native;
249 }
250
251 // Rule 8: Prefer smaller scope.
252 if (dst_a.scope != dst_b.scope)
253 return dst_a.scope < dst_b.scope;
254
255 // Rule 9: Use longest matching prefix. Only for matching address families.
256 if (dst_a.endpoint.address().size() == dst_b.endpoint.address().size()) {
257 if (dst_a.common_prefix_length != dst_b.common_prefix_length)
258 return dst_a.common_prefix_length > dst_b.common_prefix_length;
259 }
260
261 // Rule 10: Leave the order unchanged.
262 // stable_sort takes care of that.
263 return false;
264 }
265
266 } // namespace
267
268 class AddressSorterPosix::SortContext {
269 public:
SortContext(size_t in_num_endpoints,AddressSorter::CallbackType callback,const AddressSorterPosix * sorter)270 SortContext(size_t in_num_endpoints,
271 AddressSorter::CallbackType callback,
272 const AddressSorterPosix* sorter)
273 : num_endpoints_(in_num_endpoints),
274 callback_(std::move(callback)),
275 sorter_(sorter) {}
276 ~SortContext() = default;
DidCompleteConnect(IPEndPoint dest,size_t info_index,int rv)277 void DidCompleteConnect(IPEndPoint dest, size_t info_index, int rv) {
278 ++num_completed_;
279 if (rv != OK) {
280 VLOG(1) << "Could not connect to " << dest.ToStringWithoutPort()
281 << " reason " << rv;
282 sort_list_[info_index].failed = true;
283 }
284
285 MaybeFinishSort();
286 }
287
sort_list()288 std::vector<DestinationInfo>& sort_list() { return sort_list_; }
289
290 private:
MaybeFinishSort()291 void MaybeFinishSort() {
292 // Sort the list of endpoints only after each Connect call has been made.
293 if (num_completed_ != num_endpoints_) {
294 return;
295 }
296 for (auto& info : sort_list_) {
297 if (info.failed) {
298 continue;
299 }
300
301 IPEndPoint src;
302 // Filter out unusable destinations.
303 int rv = info.socket->GetLocalAddress(&src);
304 if (rv != OK) {
305 LOG(WARNING) << "Could not get local address for "
306 << info.endpoint.ToStringWithoutPort() << " reason " << rv;
307 info.failed = true;
308 continue;
309 }
310
311 auto iter = sorter_->source_map_.find(src.address());
312 if (iter == sorter_->source_map_.end()) {
313 // |src.address| may not be in the map if |source_info_| has not been
314 // updated from the OS yet. It will be updated and HostCache cleared
315 // soon, but we still want to sort, so fill in an empty
316 info.src = AddressSorterPosix::SourceAddressInfo();
317 } else {
318 info.src = iter->second;
319 }
320
321 if (info.src.scope == AddressSorterPosix::SCOPE_UNDEFINED) {
322 sorter_->FillPolicy(src.address(), &info.src);
323 }
324
325 if (info.endpoint.address().size() == src.address().size()) {
326 info.common_prefix_length =
327 std::min(CommonPrefixLength(info.endpoint.address(), src.address()),
328 info.src.prefix_length);
329 }
330 }
331 std::erase_if(sort_list_, [](auto& element) { return element.failed; });
332 std::stable_sort(sort_list_.begin(), sort_list_.end(), CompareDestinations);
333
334 std::vector<IPEndPoint> sorted_result;
335 for (const auto& info : sort_list_)
336 sorted_result.push_back(info.endpoint);
337
338 CallbackType callback = std::move(callback_);
339 sorter_->FinishedSort(this); // deletes this
340 std::move(callback).Run(true, std::move(sorted_result));
341 }
342
343 const size_t num_endpoints_;
344 size_t num_completed_ = 0;
345 std::vector<DestinationInfo> sort_list_;
346 AddressSorter::CallbackType callback_;
347
348 raw_ptr<const AddressSorterPosix> sorter_;
349 };
350
AddressSorterPosix(ClientSocketFactory * socket_factory)351 AddressSorterPosix::AddressSorterPosix(ClientSocketFactory* socket_factory)
352 : socket_factory_(socket_factory),
353 precedence_table_(LoadPolicy(kDefaultPrecedenceTable,
354 std::size(kDefaultPrecedenceTable))),
355 label_table_(
356 LoadPolicy(kDefaultLabelTable, std::size(kDefaultLabelTable))),
357 ipv4_scope_table_(LoadPolicy(kDefaultIPv4ScopeTable,
358 std::size(kDefaultIPv4ScopeTable))) {
359 NetworkChangeNotifier::AddIPAddressObserver(this);
360 OnIPAddressChanged();
361 }
362
~AddressSorterPosix()363 AddressSorterPosix::~AddressSorterPosix() {
364 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
365 NetworkChangeNotifier::RemoveIPAddressObserver(this);
366 }
367
Sort(const std::vector<IPEndPoint> & endpoints,CallbackType callback) const368 void AddressSorterPosix::Sort(const std::vector<IPEndPoint>& endpoints,
369 CallbackType callback) const {
370 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
371 sort_contexts_.insert(std::make_unique<SortContext>(
372 endpoints.size(), std::move(callback), this));
373 auto* sort_context = sort_contexts_.rbegin()->get();
374 for (const IPEndPoint& endpoint : endpoints) {
375 DestinationInfo info;
376 info.endpoint = endpoint;
377 info.scope = GetScope(ipv4_scope_table_, info.endpoint.address());
378 info.precedence =
379 GetPolicyValue(precedence_table_, info.endpoint.address());
380 info.label = GetPolicyValue(label_table_, info.endpoint.address());
381
382 // Each socket can only be bound once.
383 info.socket = socket_factory_->CreateDatagramClientSocket(
384 DatagramSocket::DEFAULT_BIND, nullptr /* NetLog */, NetLogSource());
385 IPEndPoint dest = info.endpoint;
386 // Even though no packets are sent, cannot use port 0 in Connect.
387 if (dest.port() == 0) {
388 dest = IPEndPoint(dest.address(), /*port=*/80);
389 }
390 sort_context->sort_list().push_back(std::move(info));
391 size_t info_index = sort_context->sort_list().size() - 1;
392 // Destroying a SortContext destroys the underlying socket.
393 int rv = sort_context->sort_list().back().socket->ConnectAsync(
394 dest,
395 base::BindOnce(&AddressSorterPosix::SortContext::DidCompleteConnect,
396 base::Unretained(sort_context), dest, info_index));
397 if (rv != ERR_IO_PENDING) {
398 sort_context->DidCompleteConnect(dest, info_index, rv);
399 }
400 }
401 }
402
OnIPAddressChanged()403 void AddressSorterPosix::OnIPAddressChanged() {
404 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
405 source_map_.clear();
406 #if BUILDFLAG(IS_LINUX) || BUILDFLAG(IS_CHROMEOS)
407 // TODO(crbug.com/40263501): This always returns nullptr on ChromeOS.
408 const AddressMapOwnerLinux* address_map_owner =
409 NetworkChangeNotifier::GetAddressMapOwner();
410 if (!address_map_owner) {
411 return;
412 }
413 AddressMapOwnerLinux::AddressMap map = address_map_owner->GetAddressMap();
414 for (const auto& [address, msg] : map) {
415 SourceAddressInfo& info = source_map_[address];
416 info.native = false; // TODO(szym): obtain this via netlink.
417 info.deprecated = msg.ifa_flags & IFA_F_DEPRECATED;
418 info.home = msg.ifa_flags & IFA_F_HOMEADDRESS;
419 info.prefix_length = msg.ifa_prefixlen;
420 FillPolicy(address, &info);
421 }
422 #elif BUILDFLAG(IS_APPLE) || BUILDFLAG(IS_BSD)
423 // It's not clear we will receive notification when deprecated flag changes.
424 // Socket for ioctl.
425 int ioctl_socket = socket(AF_INET6, SOCK_DGRAM, 0);
426 if (ioctl_socket < 0)
427 return;
428
429 struct ifaddrs* addrs;
430 int rv = getifaddrs(&addrs);
431 if (rv < 0) {
432 LOG(WARNING) << "getifaddrs failed " << rv;
433 close(ioctl_socket);
434 return;
435 }
436
437 for (struct ifaddrs* ifa = addrs; ifa != nullptr; ifa = ifa->ifa_next) {
438 IPEndPoint src;
439 if (!src.FromSockAddr(ifa->ifa_addr, ifa->ifa_addr->sa_len))
440 continue;
441 SourceAddressInfo& info = source_map_[src.address()];
442 // Note: no known way to fill in |native| and |home|.
443 info.native = info.home = info.deprecated = false;
444 if (ifa->ifa_addr->sa_family == AF_INET6) {
445 struct in6_ifreq ifr = {};
446 strncpy(ifr.ifr_name, ifa->ifa_name, sizeof(ifr.ifr_name) - 1);
447 DCHECK_LE(ifa->ifa_addr->sa_len, sizeof(ifr.ifr_ifru.ifru_addr));
448 memcpy(&ifr.ifr_ifru.ifru_addr, ifa->ifa_addr, ifa->ifa_addr->sa_len);
449 rv = ioctl(ioctl_socket, SIOCGIFAFLAG_IN6, &ifr);
450 if (rv >= 0) {
451 info.deprecated = ifr.ifr_ifru.ifru_flags & IN6_IFF_DEPRECATED;
452 } else {
453 LOG(WARNING) << "SIOCGIFAFLAG_IN6 failed " << rv;
454 }
455 }
456 if (ifa->ifa_netmask) {
457 IPEndPoint netmask;
458 if (netmask.FromSockAddr(ifa->ifa_netmask, ifa->ifa_addr->sa_len)) {
459 info.prefix_length = MaskPrefixLength(netmask.address());
460 } else {
461 LOG(WARNING) << "FromSockAddr failed on netmask";
462 }
463 }
464 FillPolicy(src.address(), &info);
465 }
466 freeifaddrs(addrs);
467 close(ioctl_socket);
468 #endif
469 }
470
FillPolicy(const IPAddress & address,SourceAddressInfo * info) const471 void AddressSorterPosix::FillPolicy(const IPAddress& address,
472 SourceAddressInfo* info) const {
473 DCHECK_CALLED_ON_VALID_THREAD(thread_checker_);
474 info->scope = GetScope(ipv4_scope_table_, address);
475 info->label = GetPolicyValue(label_table_, address);
476 }
477
FinishedSort(SortContext * sort_context) const478 void AddressSorterPosix::FinishedSort(SortContext* sort_context) const {
479 auto it = sort_contexts_.find(sort_context);
480 sort_contexts_.erase(it);
481 }
482
483 // static
CreateAddressSorter()484 std::unique_ptr<AddressSorter> AddressSorter::CreateAddressSorter() {
485 return std::make_unique<AddressSorterPosix>(
486 ClientSocketFactory::GetDefaultFactory());
487 }
488
489 } // namespace net
490