1 /* $NetBSD: getaddrinfo.c,v 1.82 2006/03/25 12:09:40 rpaulo Exp $ */ 2 /* $KAME: getaddrinfo.c,v 1.29 2000/08/31 17:26:57 itojun Exp $ */ 3 /* 4 * Copyright (C) 1995, 1996, 1997, and 1998 WIDE Project. 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. Neither the name of the project nor the names of its contributors 16 * may be used to endorse or promote products derived from this software 17 * without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND 20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 * ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE 23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29 * SUCH DAMAGE. 30 * 31 */ 32 33 /* 34 * This is an adaptation of Android's implementation of RFC 6724 35 * (in Android's getaddrinfo.c). It has some cosmetic differences 36 * from Android's getaddrinfo.c, but Android's getaddrinfo.c was 37 * used as a guide or example of a way to implement the RFC 6724 spec when 38 * this was written. 39 */ 40 41 #include "address_sorting_internal.h" 42 43 #include <errno.h> 44 #include <inttypes.h> 45 #include <limits.h> 46 #include <stdlib.h> 47 #include <string.h> 48 #include <sys/types.h> 49 50 // Scope values increase with increase in scope. 51 static const int kIPv6AddrScopeLinkLocal = 1; 52 static const int kIPv6AddrScopeSiteLocal = 2; 53 static const int kIPv6AddrScopeGlobal = 3; 54 55 static address_sorting_source_addr_factory* g_current_source_addr_factory = 56 NULL; 57 58 static bool address_sorting_get_source_addr(const address_sorting_address* dest, 59 address_sorting_address* source) { 60 return g_current_source_addr_factory->vtable->get_source_addr( 61 g_current_source_addr_factory, dest, source); 62 } 63 64 bool address_sorting_get_source_addr_for_testing( 65 const address_sorting_address* dest, address_sorting_address* source) { 66 return address_sorting_get_source_addr(dest, source); 67 } 68 69 static int ipv6_prefix_match_length(const struct sockaddr_in6* sa, 70 const struct sockaddr_in6* sb) { 71 unsigned char* a = (unsigned char*)&sa->sin6_addr; 72 unsigned char* b = (unsigned char*)&sb->sin6_addr; 73 int cur_bit = 0; 74 while (cur_bit < 128) { 75 int high_bit = 1 << (CHAR_BIT - 1); 76 int a_val = a[cur_bit / CHAR_BIT] & (high_bit >> (cur_bit % CHAR_BIT)); 77 int b_val = b[cur_bit / CHAR_BIT] & (high_bit >> (cur_bit % CHAR_BIT)); 78 if (a_val == b_val) { 79 cur_bit++; 80 } else { 81 break; 82 } 83 } 84 return cur_bit; 85 } 86 87 static int in6_is_addr_loopback(const struct in6_addr* ipv6_address) { 88 uint32_t* bits32 = (uint32_t*)ipv6_address; 89 return bits32[0] == 0 && bits32[1] == 0 && bits32[2] == 0 && 90 bits32[3] == htonl(1); 91 } 92 93 static int in6_is_addr_v4mapped(const struct in6_addr* ipv6_address) { 94 uint32_t* bits32 = (uint32_t*)ipv6_address; 95 return bits32[0] == 0 && bits32[1] == 0 && bits32[2] == htonl(0x0000ffff); 96 } 97 98 static int in6_is_addr_v4compat(const struct in6_addr* ipv6_address) { 99 uint32_t* bits32 = (uint32_t*)ipv6_address; 100 return bits32[0] == 0 && bits32[1] == 0 && bits32[2] == 0 && bits32[3] != 0 && 101 bits32[3] != htonl(1); 102 } 103 104 static int in6_is_addr_sitelocal(const struct in6_addr* ipv6_address) { 105 uint8_t* bytes = (uint8_t*)ipv6_address; 106 return bytes[0] == 0xfe && (bytes[1] & 0xc0) == 0xc0; 107 } 108 109 static int in6_is_addr_linklocal(const struct in6_addr* ipv6_address) { 110 uint8_t* bytes = (uint8_t*)ipv6_address; 111 return bytes[0] == 0xfe && (bytes[1] & 0xc0) == 0x80; 112 } 113 114 static int in6_is_addr_6to4(const struct in6_addr* ipv6_address) { 115 uint8_t* bytes = (uint8_t*)ipv6_address; 116 return bytes[0] == 0x20 && bytes[1] == 0x02; 117 } 118 119 static int in6_is_addr_ula(const struct in6_addr* ipv6_address) { 120 uint8_t* bytes = (uint8_t*)ipv6_address; 121 return (bytes[0] & 0xfe) == 0xfc; 122 } 123 124 static int in6_is_addr_teredo(const struct in6_addr* ipv6_address) { 125 uint8_t* bytes = (uint8_t*)ipv6_address; 126 return bytes[0] == 0x20 && bytes[1] == 0x01 && bytes[2] == 0x00 && 127 bytes[3] == 0x00; 128 } 129 130 static int in6_is_addr_6bone(const struct in6_addr* ipv6_address) { 131 uint8_t* bytes = (uint8_t*)ipv6_address; 132 return bytes[0] == 0x3f && bytes[1] == 0xfe; 133 } 134 135 address_sorting_family address_sorting_abstract_get_family( 136 const address_sorting_address* address) { 137 switch (((struct sockaddr*)address)->sa_family) { 138 case AF_INET: 139 return ADDRESS_SORTING_AF_INET; 140 case AF_INET6: 141 return ADDRESS_SORTING_AF_INET6; 142 default: 143 return ADDRESS_SORTING_UNKNOWN_FAMILY; 144 } 145 } 146 147 static int get_label_value(const address_sorting_address* resolved_addr) { 148 if (address_sorting_abstract_get_family(resolved_addr) == 149 ADDRESS_SORTING_AF_INET) { 150 return 4; 151 } else if (address_sorting_abstract_get_family(resolved_addr) != 152 ADDRESS_SORTING_AF_INET6) { 153 return 1; 154 } 155 struct sockaddr_in6* ipv6_addr = (struct sockaddr_in6*)&resolved_addr->addr; 156 if (in6_is_addr_loopback(&ipv6_addr->sin6_addr)) { 157 return 0; 158 } else if (in6_is_addr_v4mapped(&ipv6_addr->sin6_addr)) { 159 return 4; 160 } else if (in6_is_addr_6to4(&ipv6_addr->sin6_addr)) { 161 return 2; 162 } else if (in6_is_addr_teredo(&ipv6_addr->sin6_addr)) { 163 return 5; 164 } else if (in6_is_addr_ula(&ipv6_addr->sin6_addr)) { 165 return 13; 166 } else if (in6_is_addr_v4compat(&ipv6_addr->sin6_addr)) { 167 return 3; 168 } else if (in6_is_addr_sitelocal(&ipv6_addr->sin6_addr)) { 169 return 11; 170 } else if (in6_is_addr_6bone(&ipv6_addr->sin6_addr)) { 171 return 12; 172 } 173 return 1; 174 } 175 176 static int get_precedence_value(const address_sorting_address* resolved_addr) { 177 if (address_sorting_abstract_get_family(resolved_addr) == 178 ADDRESS_SORTING_AF_INET) { 179 return 35; 180 } else if (address_sorting_abstract_get_family(resolved_addr) != 181 ADDRESS_SORTING_AF_INET6) { 182 return 1; 183 } 184 struct sockaddr_in6* ipv6_addr = (struct sockaddr_in6*)&resolved_addr->addr; 185 if (in6_is_addr_loopback(&ipv6_addr->sin6_addr)) { 186 return 50; 187 } else if (in6_is_addr_v4mapped(&ipv6_addr->sin6_addr)) { 188 return 35; 189 } else if (in6_is_addr_6to4(&ipv6_addr->sin6_addr)) { 190 return 30; 191 } else if (in6_is_addr_teredo(&ipv6_addr->sin6_addr)) { 192 return 5; 193 } else if (in6_is_addr_ula(&ipv6_addr->sin6_addr)) { 194 return 3; 195 } else if (in6_is_addr_v4compat(&ipv6_addr->sin6_addr) || 196 in6_is_addr_sitelocal(&ipv6_addr->sin6_addr) || 197 in6_is_addr_6bone(&ipv6_addr->sin6_addr)) { 198 return 1; 199 } 200 return 40; 201 } 202 203 static int sockaddr_get_scope(const address_sorting_address* resolved_addr) { 204 if (address_sorting_abstract_get_family(resolved_addr) == 205 ADDRESS_SORTING_AF_INET) { 206 return kIPv6AddrScopeGlobal; 207 } else if (address_sorting_abstract_get_family(resolved_addr) == 208 ADDRESS_SORTING_AF_INET6) { 209 struct sockaddr_in6* ipv6_addr = (struct sockaddr_in6*)&resolved_addr->addr; 210 if (in6_is_addr_loopback(&ipv6_addr->sin6_addr) || 211 in6_is_addr_linklocal(&ipv6_addr->sin6_addr)) { 212 return kIPv6AddrScopeLinkLocal; 213 } 214 if (in6_is_addr_sitelocal(&ipv6_addr->sin6_addr)) { 215 return kIPv6AddrScopeSiteLocal; 216 } 217 return kIPv6AddrScopeGlobal; 218 } 219 return 0; 220 } 221 222 static int compare_source_addr_exists(const address_sorting_sortable* first, 223 const address_sorting_sortable* second) { 224 if (first->source_addr_exists != second->source_addr_exists) { 225 return first->source_addr_exists ? -1 : 1; 226 } 227 return 0; 228 } 229 230 static int compare_source_dest_scope_matches( 231 const address_sorting_sortable* first, 232 const address_sorting_sortable* second) { 233 bool first_src_dst_scope_matches = false; 234 if (sockaddr_get_scope(&first->dest_addr) == 235 sockaddr_get_scope(&first->source_addr)) { 236 first_src_dst_scope_matches = true; 237 } 238 bool second_src_dst_scope_matches = false; 239 if (sockaddr_get_scope(&second->dest_addr) == 240 sockaddr_get_scope(&second->source_addr)) { 241 second_src_dst_scope_matches = true; 242 } 243 if (first_src_dst_scope_matches != second_src_dst_scope_matches) { 244 return first_src_dst_scope_matches ? -1 : 1; 245 } 246 return 0; 247 } 248 249 static int compare_source_dest_labels_match( 250 const address_sorting_sortable* first, 251 const address_sorting_sortable* second) { 252 bool first_label_matches = false; 253 if (get_label_value(&first->dest_addr) == 254 get_label_value(&first->source_addr)) { 255 first_label_matches = true; 256 } 257 bool second_label_matches = false; 258 if (get_label_value(&second->dest_addr) == 259 get_label_value(&second->source_addr)) { 260 second_label_matches = true; 261 } 262 if (first_label_matches != second_label_matches) { 263 return first_label_matches ? -1 : 1; 264 } 265 return 0; 266 } 267 268 static int compare_dest_precedence(const address_sorting_sortable* first, 269 const address_sorting_sortable* second) { 270 return get_precedence_value(&second->dest_addr) - 271 get_precedence_value(&first->dest_addr); 272 } 273 274 static int compare_dest_scope(const address_sorting_sortable* first, 275 const address_sorting_sortable* second) { 276 return sockaddr_get_scope(&first->dest_addr) - 277 sockaddr_get_scope(&second->dest_addr); 278 } 279 280 static int compare_source_dest_prefix_match_lengths( 281 const address_sorting_sortable* first, 282 const address_sorting_sortable* second) { 283 if (first->source_addr_exists && 284 address_sorting_abstract_get_family(&first->source_addr) == 285 ADDRESS_SORTING_AF_INET6 && 286 second->source_addr_exists && 287 address_sorting_abstract_get_family(&second->source_addr) == 288 ADDRESS_SORTING_AF_INET6) { 289 int first_match_length = 290 ipv6_prefix_match_length((struct sockaddr_in6*)&first->source_addr.addr, 291 (struct sockaddr_in6*)&first->dest_addr.addr); 292 int second_match_length = ipv6_prefix_match_length( 293 (struct sockaddr_in6*)&second->source_addr.addr, 294 (struct sockaddr_in6*)&second->dest_addr.addr); 295 return second_match_length - first_match_length; 296 } 297 return 0; 298 } 299 300 static int rfc_6724_compare(const void* a, const void* b) { 301 const address_sorting_sortable* first = (address_sorting_sortable*)a; 302 const address_sorting_sortable* second = (address_sorting_sortable*)b; 303 int out = 0; 304 if ((out = compare_source_addr_exists(first, second))) { 305 return out; 306 } 307 if ((out = compare_source_dest_scope_matches(first, second))) { 308 return out; 309 } 310 if ((out = compare_source_dest_labels_match(first, second))) { 311 return out; 312 } 313 // TODO: Implement rule 3; avoid deprecated addresses. 314 // TODO: Implement rule 4; avoid temporary addresses. 315 if ((out = compare_dest_precedence(first, second))) { 316 return out; 317 } 318 // TODO: Implement rule 7; prefer native transports. 319 if ((out = compare_dest_scope(first, second))) { 320 return out; 321 } 322 if ((out = compare_source_dest_prefix_match_lengths(first, second))) { 323 return out; 324 } 325 // Prefer that the sort be stable otherwise 326 return (int)(first->original_index - second->original_index); 327 } 328 329 void address_sorting_override_source_addr_factory_for_testing( 330 address_sorting_source_addr_factory* factory) { 331 if (g_current_source_addr_factory == NULL) { 332 abort(); 333 } 334 g_current_source_addr_factory->vtable->destroy(g_current_source_addr_factory); 335 g_current_source_addr_factory = factory; 336 } 337 338 static void sanity_check_private_fields_are_unused( 339 const address_sorting_sortable* sortable) { 340 address_sorting_address expected_source_addr; 341 memset(&expected_source_addr, 0, sizeof(expected_source_addr)); 342 if (memcmp(&expected_source_addr, &sortable->source_addr, 343 sizeof(address_sorting_address)) || 344 sortable->original_index || sortable->source_addr_exists) { 345 abort(); 346 } 347 } 348 349 void address_sorting_rfc_6724_sort(address_sorting_sortable* sortables, 350 size_t sortables_len) { 351 for (size_t i = 0; i < sortables_len; i++) { 352 sanity_check_private_fields_are_unused(&sortables[i]); 353 sortables[i].original_index = i; 354 sortables[i].source_addr_exists = address_sorting_get_source_addr( 355 &sortables[i].dest_addr, &sortables[i].source_addr); 356 } 357 qsort(sortables, sortables_len, sizeof(address_sorting_sortable), 358 rfc_6724_compare); 359 } 360 361 void address_sorting_init() { 362 if (g_current_source_addr_factory != NULL) { 363 abort(); 364 } 365 g_current_source_addr_factory = 366 address_sorting_create_source_addr_factory_for_current_platform(); 367 } 368 369 void address_sorting_shutdown() { 370 if (g_current_source_addr_factory == NULL) { 371 abort(); 372 } 373 g_current_source_addr_factory->vtable->destroy(g_current_source_addr_factory); 374 g_current_source_addr_factory = NULL; 375 } 376
