ares_sortaddrinfo.c (14440B)
1 /* 2 * Original file name getaddrinfo.c 3 * Lifted from the 'Android Bionic' project with the BSD license. 4 */ 5 6 /* 7 * Copyright (C) 1995, 1996, 1997, and 1998 WIDE Project. 8 * Copyright (C) 2018 The Android Open Source Project 9 * Copyright (C) 2019 Andrew Selivanov 10 * All rights reserved. 11 * 12 * Redistribution and use in source and binary forms, with or without 13 * modification, are permitted provided that the following conditions 14 * are met: 15 * 1. Redistributions of source code must retain the above copyright 16 * notice, this list of conditions and the following disclaimer. 17 * 2. Redistributions in binary form must reproduce the above copyright 18 * notice, this list of conditions and the following disclaimer in the 19 * documentation and/or other materials provided with the distribution. 20 * 3. Neither the name of the project nor the names of its contributors 21 * may be used to endorse or promote products derived from this software 22 * without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND 25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 * ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE 28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 * 36 * SPDX-License-Identifier: BSD-3-Clause 37 */ 38 39 #include "ares_private.h" 40 41 #ifdef HAVE_NETINET_IN_H 42 # include <netinet/in.h> 43 #endif 44 #ifdef HAVE_NETDB_H 45 # include <netdb.h> 46 #endif 47 #ifdef HAVE_STRINGS_H 48 # include <strings.h> 49 #endif 50 51 #include <assert.h> 52 #include <limits.h> 53 54 struct addrinfo_sort_elem { 55 struct ares_addrinfo_node *ai; 56 ares_bool_t has_src_addr; 57 ares_sockaddr src_addr; 58 size_t original_order; 59 }; 60 61 #define ARES_IPV6_ADDR_MC_SCOPE(a) ((a)->s6_addr[1] & 0x0f) 62 63 #define ARES_IPV6_ADDR_SCOPE_NODELOCAL 0x01 64 #define ARES_IPV6_ADDR_SCOPE_INTFACELOCAL 0x01 65 #define ARES_IPV6_ADDR_SCOPE_LINKLOCAL 0x02 66 #define ARES_IPV6_ADDR_SCOPE_SITELOCAL 0x05 67 #define ARES_IPV6_ADDR_SCOPE_ORGLOCAL 0x08 68 #define ARES_IPV6_ADDR_SCOPE_GLOBAL 0x0e 69 70 #define ARES_IN_LOOPBACK(a) \ 71 ((((long unsigned int)(a)) & 0xff000000) == 0x7f000000) 72 73 /* RFC 4193. */ 74 #define ARES_IN6_IS_ADDR_ULA(a) (((a)->s6_addr[0] & 0xfe) == 0xfc) 75 76 /* These macros are modelled after the ones in <netinet/in6.h>. */ 77 /* RFC 4380, section 2.6 */ 78 #define ARES_IN6_IS_ADDR_TEREDO(a) \ 79 ((*(const unsigned int *)(const void *)(&(a)->s6_addr[0]) == \ 80 ntohl(0x20010000))) 81 /* RFC 3056, section 2. */ 82 #define ARES_IN6_IS_ADDR_6TO4(a) \ 83 (((a)->s6_addr[0] == 0x20) && ((a)->s6_addr[1] == 0x02)) 84 /* 6bone testing address area (3ffe::/16), deprecated in RFC 3701. */ 85 #define ARES_IN6_IS_ADDR_6BONE(a) \ 86 (((a)->s6_addr[0] == 0x3f) && ((a)->s6_addr[1] == 0xfe)) 87 88 static int get_scope(const struct sockaddr *addr) 89 { 90 if (addr->sa_family == AF_INET6) { 91 const struct sockaddr_in6 *addr6 = 92 CARES_INADDR_CAST(const struct sockaddr_in6 *, addr); 93 if (IN6_IS_ADDR_MULTICAST(&addr6->sin6_addr)) { 94 return ARES_IPV6_ADDR_MC_SCOPE(&addr6->sin6_addr); 95 } else if (IN6_IS_ADDR_LOOPBACK(&addr6->sin6_addr) || 96 IN6_IS_ADDR_LINKLOCAL(&addr6->sin6_addr)) { 97 /* 98 * RFC 4291 section 2.5.3 says loopback is to be treated as having 99 * link-local scope. 100 */ 101 return ARES_IPV6_ADDR_SCOPE_LINKLOCAL; 102 } else if (IN6_IS_ADDR_SITELOCAL(&addr6->sin6_addr)) { 103 return ARES_IPV6_ADDR_SCOPE_SITELOCAL; 104 } else { 105 return ARES_IPV6_ADDR_SCOPE_GLOBAL; 106 } 107 } else if (addr->sa_family == AF_INET) { 108 const struct sockaddr_in *addr4 = 109 CARES_INADDR_CAST(const struct sockaddr_in *, addr); 110 unsigned long int na = ntohl(addr4->sin_addr.s_addr); 111 if (ARES_IN_LOOPBACK(na) || /* 127.0.0.0/8 */ 112 (na & 0xffff0000) == 0xa9fe0000) /* 169.254.0.0/16 */ 113 { 114 return ARES_IPV6_ADDR_SCOPE_LINKLOCAL; 115 } else { 116 /* 117 * RFC 6724 section 3.2. Other IPv4 addresses, including private 118 * addresses and shared addresses (100.64.0.0/10), are assigned global 119 * scope. 120 */ 121 return ARES_IPV6_ADDR_SCOPE_GLOBAL; 122 } 123 } else { 124 /* 125 * This should never happen. 126 * Return a scope with low priority as a last resort. 127 */ 128 return ARES_IPV6_ADDR_SCOPE_NODELOCAL; 129 } 130 } 131 132 static int get_label(const struct sockaddr *addr) 133 { 134 if (addr->sa_family == AF_INET) { 135 return 4; 136 } else if (addr->sa_family == AF_INET6) { 137 const struct sockaddr_in6 *addr6 = 138 CARES_INADDR_CAST(const struct sockaddr_in6 *, addr); 139 if (IN6_IS_ADDR_LOOPBACK(&addr6->sin6_addr)) { 140 return 0; 141 } else if (IN6_IS_ADDR_V4MAPPED(&addr6->sin6_addr)) { 142 return 4; 143 } else if (ARES_IN6_IS_ADDR_6TO4(&addr6->sin6_addr)) { 144 return 2; 145 } else if (ARES_IN6_IS_ADDR_TEREDO(&addr6->sin6_addr)) { 146 return 5; 147 } else if (ARES_IN6_IS_ADDR_ULA(&addr6->sin6_addr)) { 148 return 13; 149 } else if (IN6_IS_ADDR_V4COMPAT(&addr6->sin6_addr)) { 150 return 3; 151 } else if (IN6_IS_ADDR_SITELOCAL(&addr6->sin6_addr)) { 152 return 11; 153 } else if (ARES_IN6_IS_ADDR_6BONE(&addr6->sin6_addr)) { 154 return 12; 155 } else { 156 /* All other IPv6 addresses, including global unicast addresses. */ 157 return 1; 158 } 159 } else { 160 /* 161 * This should never happen. 162 * Return a semi-random label as a last resort. 163 */ 164 return 1; 165 } 166 } 167 168 /* 169 * Get the precedence for a given IPv4/IPv6 address. 170 * RFC 6724, section 2.1. 171 */ 172 static int get_precedence(const struct sockaddr *addr) 173 { 174 if (addr->sa_family == AF_INET) { 175 return 35; 176 } else if (addr->sa_family == AF_INET6) { 177 const struct sockaddr_in6 *addr6 = 178 CARES_INADDR_CAST(const struct sockaddr_in6 *, addr); 179 if (IN6_IS_ADDR_LOOPBACK(&addr6->sin6_addr)) { 180 return 50; 181 } else if (IN6_IS_ADDR_V4MAPPED(&addr6->sin6_addr)) { 182 return 35; 183 } else if (ARES_IN6_IS_ADDR_6TO4(&addr6->sin6_addr)) { 184 return 30; 185 } else if (ARES_IN6_IS_ADDR_TEREDO(&addr6->sin6_addr)) { 186 return 5; 187 } else if (ARES_IN6_IS_ADDR_ULA(&addr6->sin6_addr)) { 188 return 3; 189 } else if (IN6_IS_ADDR_V4COMPAT(&addr6->sin6_addr) || 190 IN6_IS_ADDR_SITELOCAL(&addr6->sin6_addr) || 191 ARES_IN6_IS_ADDR_6BONE(&addr6->sin6_addr)) { 192 return 1; 193 } else { 194 /* All other IPv6 addresses, including global unicast addresses. */ 195 return 40; 196 } 197 } else { 198 return 1; 199 } 200 } 201 202 /* 203 * Find number of matching initial bits between the two addresses a1 and a2. 204 */ 205 static size_t common_prefix_len(const struct in6_addr *a1, 206 const struct in6_addr *a2) 207 { 208 const unsigned char *p1 = (const unsigned char *)a1; 209 const unsigned char *p2 = (const unsigned char *)a2; 210 size_t i; 211 for (i = 0; i < sizeof(*a1); ++i) { 212 unsigned char x; 213 size_t j; 214 if (p1[i] == p2[i]) { 215 continue; 216 } 217 x = p1[i] ^ p2[i]; 218 for (j = 0; j < CHAR_BIT; ++j) { 219 if (x & (1 << (CHAR_BIT - 1))) { 220 return i * CHAR_BIT + j; 221 } 222 x <<= 1; 223 } 224 } 225 return sizeof(*a1) * CHAR_BIT; 226 } 227 228 /* 229 * Compare two source/destination address pairs. 230 * RFC 6724, section 6. 231 */ 232 static int rfc6724_compare(const void *ptr1, const void *ptr2) 233 { 234 const struct addrinfo_sort_elem *a1 = (const struct addrinfo_sort_elem *)ptr1; 235 const struct addrinfo_sort_elem *a2 = (const struct addrinfo_sort_elem *)ptr2; 236 int scope_src1; 237 int scope_dst1; 238 int scope_match1; 239 int scope_src2; 240 int scope_dst2; 241 int scope_match2; 242 int label_src1; 243 int label_dst1; 244 int label_match1; 245 int label_src2; 246 int label_dst2; 247 int label_match2; 248 int precedence1; 249 int precedence2; 250 size_t prefixlen1; 251 size_t prefixlen2; 252 253 /* Rule 1: Avoid unusable destinations. */ 254 if (a1->has_src_addr != a2->has_src_addr) { 255 return ((int)a2->has_src_addr) - ((int)a1->has_src_addr); 256 } 257 258 /* Rule 2: Prefer matching scope. */ 259 scope_src1 = ARES_IPV6_ADDR_SCOPE_NODELOCAL; 260 if (a1->has_src_addr) { 261 scope_src1 = get_scope(&a1->src_addr.sa); 262 } 263 scope_dst1 = get_scope(a1->ai->ai_addr); 264 scope_match1 = (scope_src1 == scope_dst1); 265 266 scope_src2 = ARES_IPV6_ADDR_SCOPE_NODELOCAL; 267 if (a2->has_src_addr) { 268 scope_src2 = get_scope(&a2->src_addr.sa); 269 } 270 scope_dst2 = get_scope(a2->ai->ai_addr); 271 scope_match2 = (scope_src2 == scope_dst2); 272 273 if (scope_match1 != scope_match2) { 274 return scope_match2 - scope_match1; 275 } 276 277 /* Rule 3: Avoid deprecated addresses. */ 278 279 /* Rule 4: Prefer home addresses. */ 280 281 /* Rule 5: Prefer matching label. */ 282 label_src1 = 1; 283 if (a1->has_src_addr) { 284 label_src1 = get_label(&a1->src_addr.sa); 285 } 286 label_dst1 = get_label(a1->ai->ai_addr); 287 label_match1 = (label_src1 == label_dst1); 288 289 label_src2 = 1; 290 if (a2->has_src_addr) { 291 label_src2 = get_label(&a2->src_addr.sa); 292 } 293 label_dst2 = get_label(a2->ai->ai_addr); 294 label_match2 = (label_src2 == label_dst2); 295 296 if (label_match1 != label_match2) { 297 return label_match2 - label_match1; 298 } 299 300 /* Rule 6: Prefer higher precedence. */ 301 precedence1 = get_precedence(a1->ai->ai_addr); 302 precedence2 = get_precedence(a2->ai->ai_addr); 303 if (precedence1 != precedence2) { 304 return precedence2 - precedence1; 305 } 306 307 /* Rule 7: Prefer native transport. */ 308 309 /* Rule 8: Prefer smaller scope. */ 310 if (scope_dst1 != scope_dst2) { 311 return scope_dst1 - scope_dst2; 312 } 313 314 /* Rule 9: Use longest matching prefix. */ 315 if (a1->has_src_addr && a1->ai->ai_addr->sa_family == AF_INET6 && 316 a2->has_src_addr && a2->ai->ai_addr->sa_family == AF_INET6) { 317 const struct sockaddr_in6 *a1_src = &a1->src_addr.sa6; 318 const struct sockaddr_in6 *a1_dst = 319 CARES_INADDR_CAST(const struct sockaddr_in6 *, a1->ai->ai_addr); 320 const struct sockaddr_in6 *a2_src = &a2->src_addr.sa6; 321 const struct sockaddr_in6 *a2_dst = 322 CARES_INADDR_CAST(const struct sockaddr_in6 *, a2->ai->ai_addr); 323 prefixlen1 = common_prefix_len(&a1_src->sin6_addr, &a1_dst->sin6_addr); 324 prefixlen2 = common_prefix_len(&a2_src->sin6_addr, &a2_dst->sin6_addr); 325 if (prefixlen1 != prefixlen2) { 326 return (int)prefixlen2 - (int)prefixlen1; 327 } 328 } 329 330 /* 331 * Rule 10: Leave the order unchanged. 332 * We need this since qsort() is not necessarily stable. 333 */ 334 return ((int)a1->original_order) - ((int)a2->original_order); 335 } 336 337 /* 338 * Find the source address that will be used if trying to connect to the given 339 * address. 340 * 341 * Returns 1 if a source address was found, 0 if the address is unreachable 342 * and -1 if a fatal error occurred. If 0 or 1, the contents of src_addr are 343 * undefined. 344 */ 345 static int find_src_addr(ares_channel_t *channel, const struct sockaddr *addr, 346 struct sockaddr *src_addr) 347 { 348 ares_socket_t sock; 349 ares_socklen_t len; 350 ares_conn_err_t err; 351 352 switch (addr->sa_family) { 353 case AF_INET: 354 len = sizeof(struct sockaddr_in); 355 break; 356 case AF_INET6: 357 len = sizeof(struct sockaddr_in6); 358 break; 359 default: 360 /* No known usable source address for non-INET families. */ 361 return 0; 362 } 363 364 err = 365 ares_socket_open(&sock, channel, addr->sa_family, SOCK_DGRAM, IPPROTO_UDP); 366 if (err == ARES_CONN_ERR_AFNOSUPPORT) { 367 return 0; 368 } else if (err != ARES_CONN_ERR_SUCCESS) { 369 return -1; 370 } 371 372 err = ares_socket_connect(channel, sock, ARES_FALSE, addr, len); 373 if (err != ARES_CONN_ERR_SUCCESS && err != ARES_CONN_ERR_WOULDBLOCK) { 374 ares_socket_close(channel, sock); 375 return 0; 376 } 377 378 if (channel->sock_funcs.agetsockname == NULL || 379 channel->sock_funcs.agetsockname(sock, src_addr, &len, 380 channel->sock_func_cb_data) != 0) { 381 ares_socket_close(channel, sock); 382 return -1; 383 } 384 ares_socket_close(channel, sock); 385 return 1; 386 } 387 388 /* 389 * Sort the linked list starting at sentinel->ai_next in RFC6724 order. 390 * Will leave the list unchanged if an error occurs. 391 */ 392 ares_status_t ares_sortaddrinfo(ares_channel_t *channel, 393 struct ares_addrinfo_node *list_sentinel) 394 { 395 struct ares_addrinfo_node *cur; 396 size_t nelem = 0; 397 size_t i; 398 int has_src_addr; 399 struct addrinfo_sort_elem *elems; 400 401 cur = list_sentinel->ai_next; 402 while (cur) { 403 ++nelem; 404 cur = cur->ai_next; 405 } 406 407 if (!nelem) { 408 return ARES_ENODATA; 409 } 410 411 elems = (struct addrinfo_sort_elem *)ares_malloc( 412 nelem * sizeof(struct addrinfo_sort_elem)); 413 if (!elems) { 414 return ARES_ENOMEM; 415 } 416 417 /* 418 * Convert the linked list to an array that also contains the candidate 419 * source address for each destination address. 420 */ 421 for (i = 0, cur = list_sentinel->ai_next; i < nelem; 422 ++i, cur = cur->ai_next) { 423 assert(cur != NULL); 424 elems[i].ai = cur; 425 elems[i].original_order = i; 426 has_src_addr = find_src_addr(channel, cur->ai_addr, &elems[i].src_addr.sa); 427 if (has_src_addr == -1) { 428 ares_free(elems); 429 return ARES_ENOTFOUND; 430 } 431 elems[i].has_src_addr = (has_src_addr == 1) ? ARES_TRUE : ARES_FALSE; 432 } 433 434 /* Sort the addresses, and rearrange the linked list so it matches the sorted 435 * order. */ 436 qsort((void *)elems, nelem, sizeof(struct addrinfo_sort_elem), 437 rfc6724_compare); 438 439 list_sentinel->ai_next = elems[0].ai; 440 for (i = 0; i < nelem - 1; ++i) { 441 elems[i].ai->ai_next = elems[i + 1].ai; 442 } 443 elems[nelem - 1].ai->ai_next = NULL; 444 445 ares_free(elems); 446 return ARES_SUCCESS; 447 }