| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375 | /*	$NetBSD: getaddrinfo.c,v 1.82 2006/03/25 12:09:40 rpaulo Exp $	*//*	$KAME: getaddrinfo.c,v 1.29 2000/08/31 17:26:57 itojun Exp $	*//* * Copyright (C) 1995, 1996, 1997, and 1998 WIDE Project. * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright *    notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright *    notice, this list of conditions and the following disclaimer in the *    documentation and/or other materials provided with the distribution. * 3. Neither the name of the project nor the names of its contributors *    may be used to endorse or promote products derived from this software *    without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED.  IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * *//* * This is an adaptation of Android's implementation of RFC 6724 * (in Android's getaddrinfo.c). It has some cosmetic differences * from Android's getaddrinfo.c, but Android's getaddrinfo.c was * used as a guide or example of a way to implement the RFC 6724 spec when * this was written. */#include "address_sorting_internal.h"#include <errno.h>#include <inttypes.h>#include <limits.h>#include <stdlib.h>#include <string.h>#include <sys/types.h>// Scope values increase with increase in scope.static const int kIPv6AddrScopeLinkLocal = 1;static const int kIPv6AddrScopeSiteLocal = 2;static const int kIPv6AddrScopeGlobal = 3;static address_sorting_source_addr_factory* g_current_source_addr_factory =    NULL;static bool address_sorting_get_source_addr(const address_sorting_address* dest,                                            address_sorting_address* source) {  return g_current_source_addr_factory->vtable->get_source_addr(      g_current_source_addr_factory, dest, source);}bool address_sorting_get_source_addr_for_testing(    const address_sorting_address* dest, address_sorting_address* source) {  return address_sorting_get_source_addr(dest, source);}static int ipv6_prefix_match_length(const struct sockaddr_in6* sa,                                    const struct sockaddr_in6* sb) {  unsigned char* a = (unsigned char*)&sa->sin6_addr;  unsigned char* b = (unsigned char*)&sb->sin6_addr;  int cur_bit = 0;  while (cur_bit < 128) {    int high_bit = 1 << (CHAR_BIT - 1);    int a_val = a[cur_bit / CHAR_BIT] & (high_bit >> (cur_bit % CHAR_BIT));    int b_val = b[cur_bit / CHAR_BIT] & (high_bit >> (cur_bit % CHAR_BIT));    if (a_val == b_val) {      cur_bit++;    } else {      break;    }  }  return cur_bit;}static int in6_is_addr_loopback(const struct in6_addr* ipv6_address) {  uint32_t* bits32 = (uint32_t*)ipv6_address;  return bits32[0] == 0 && bits32[1] == 0 && bits32[2] == 0 &&         bits32[3] == htonl(1);}static int in6_is_addr_v4mapped(const struct in6_addr* ipv6_address) {  uint32_t* bits32 = (uint32_t*)ipv6_address;  return bits32[0] == 0 && bits32[1] == 0 && bits32[2] == htonl(0x0000ffff);}static int in6_is_addr_v4compat(const struct in6_addr* ipv6_address) {  uint32_t* bits32 = (uint32_t*)ipv6_address;  return bits32[0] == 0 && bits32[1] == 0 && bits32[2] == 0 && bits32[3] != 0 &&         bits32[3] != htonl(1);}static int in6_is_addr_sitelocal(const struct in6_addr* ipv6_address) {  uint8_t* bytes = (uint8_t*)ipv6_address;  return bytes[0] == 0xfe && (bytes[1] & 0xc0) == 0xc0;}static int in6_is_addr_linklocal(const struct in6_addr* ipv6_address) {  uint8_t* bytes = (uint8_t*)ipv6_address;  return bytes[0] == 0xfe && (bytes[1] & 0xc0) == 0x80;}static int in6_is_addr_6to4(const struct in6_addr* ipv6_address) {  uint8_t* bytes = (uint8_t*)ipv6_address;  return bytes[0] == 0x20 && bytes[1] == 0x02;}static int in6_is_addr_ula(const struct in6_addr* ipv6_address) {  uint8_t* bytes = (uint8_t*)ipv6_address;  return (bytes[0] & 0xfe) == 0xfc;}static int in6_is_addr_teredo(const struct in6_addr* ipv6_address) {  uint8_t* bytes = (uint8_t*)ipv6_address;  return bytes[0] == 0x20 && bytes[1] == 0x01 && bytes[2] == 0x00 &&         bytes[3] == 0x00;}static int in6_is_addr_6bone(const struct in6_addr* ipv6_address) {  uint8_t* bytes = (uint8_t*)ipv6_address;  return bytes[0] == 0x3f && bytes[1] == 0xfe;}address_sorting_family address_sorting_abstract_get_family(    const address_sorting_address* address) {  switch (((struct sockaddr*)address)->sa_family) {    case AF_INET:      return ADDRESS_SORTING_AF_INET;    case AF_INET6:      return ADDRESS_SORTING_AF_INET6;    default:      return ADDRESS_SORTING_UNKNOWN_FAMILY;  }}static int get_label_value(const address_sorting_address* resolved_addr) {  if (address_sorting_abstract_get_family(resolved_addr) ==      ADDRESS_SORTING_AF_INET) {    return 4;  } else if (address_sorting_abstract_get_family(resolved_addr) !=             ADDRESS_SORTING_AF_INET6) {    return 1;  }  struct sockaddr_in6* ipv6_addr = (struct sockaddr_in6*)&resolved_addr->addr;  if (in6_is_addr_loopback(&ipv6_addr->sin6_addr)) {    return 0;  } else if (in6_is_addr_v4mapped(&ipv6_addr->sin6_addr)) {    return 4;  } else if (in6_is_addr_6to4(&ipv6_addr->sin6_addr)) {    return 2;  } else if (in6_is_addr_teredo(&ipv6_addr->sin6_addr)) {    return 5;  } else if (in6_is_addr_ula(&ipv6_addr->sin6_addr)) {    return 13;  } else if (in6_is_addr_v4compat(&ipv6_addr->sin6_addr)) {    return 3;  } else if (in6_is_addr_sitelocal(&ipv6_addr->sin6_addr)) {    return 11;  } else if (in6_is_addr_6bone(&ipv6_addr->sin6_addr)) {    return 12;  }  return 1;}static int get_precedence_value(const address_sorting_address* resolved_addr) {  if (address_sorting_abstract_get_family(resolved_addr) ==      ADDRESS_SORTING_AF_INET) {    return 35;  } else if (address_sorting_abstract_get_family(resolved_addr) !=             ADDRESS_SORTING_AF_INET6) {    return 1;  }  struct sockaddr_in6* ipv6_addr = (struct sockaddr_in6*)&resolved_addr->addr;  if (in6_is_addr_loopback(&ipv6_addr->sin6_addr)) {    return 50;  } else if (in6_is_addr_v4mapped(&ipv6_addr->sin6_addr)) {    return 35;  } else if (in6_is_addr_6to4(&ipv6_addr->sin6_addr)) {    return 30;  } else if (in6_is_addr_teredo(&ipv6_addr->sin6_addr)) {    return 5;  } else if (in6_is_addr_ula(&ipv6_addr->sin6_addr)) {    return 3;  } else if (in6_is_addr_v4compat(&ipv6_addr->sin6_addr) ||             in6_is_addr_sitelocal(&ipv6_addr->sin6_addr) ||             in6_is_addr_6bone(&ipv6_addr->sin6_addr)) {    return 1;  }  return 40;}static int sockaddr_get_scope(const address_sorting_address* resolved_addr) {  if (address_sorting_abstract_get_family(resolved_addr) ==      ADDRESS_SORTING_AF_INET) {    return kIPv6AddrScopeGlobal;  } else if (address_sorting_abstract_get_family(resolved_addr) ==             ADDRESS_SORTING_AF_INET6) {    struct sockaddr_in6* ipv6_addr = (struct sockaddr_in6*)&resolved_addr->addr;    if (in6_is_addr_loopback(&ipv6_addr->sin6_addr) ||        in6_is_addr_linklocal(&ipv6_addr->sin6_addr)) {      return kIPv6AddrScopeLinkLocal;    }    if (in6_is_addr_sitelocal(&ipv6_addr->sin6_addr)) {      return kIPv6AddrScopeSiteLocal;    }    return kIPv6AddrScopeGlobal;  }  return 0;}static int compare_source_addr_exists(const address_sorting_sortable* first,                                      const address_sorting_sortable* second) {  if (first->source_addr_exists != second->source_addr_exists) {    return first->source_addr_exists ? -1 : 1;  }  return 0;}static int compare_source_dest_scope_matches(    const address_sorting_sortable* first,    const address_sorting_sortable* second) {  bool first_src_dst_scope_matches = false;  if (sockaddr_get_scope(&first->dest_addr) ==      sockaddr_get_scope(&first->source_addr)) {    first_src_dst_scope_matches = true;  }  bool second_src_dst_scope_matches = false;  if (sockaddr_get_scope(&second->dest_addr) ==      sockaddr_get_scope(&second->source_addr)) {    second_src_dst_scope_matches = true;  }  if (first_src_dst_scope_matches != second_src_dst_scope_matches) {    return first_src_dst_scope_matches ? -1 : 1;  }  return 0;}static int compare_source_dest_labels_match(    const address_sorting_sortable* first,    const address_sorting_sortable* second) {  bool first_label_matches = false;  if (get_label_value(&first->dest_addr) ==      get_label_value(&first->source_addr)) {    first_label_matches = true;  }  bool second_label_matches = false;  if (get_label_value(&second->dest_addr) ==      get_label_value(&second->source_addr)) {    second_label_matches = true;  }  if (first_label_matches != second_label_matches) {    return first_label_matches ? -1 : 1;  }  return 0;}static int compare_dest_precedence(const address_sorting_sortable* first,                                   const address_sorting_sortable* second) {  return get_precedence_value(&second->dest_addr) -         get_precedence_value(&first->dest_addr);}static int compare_dest_scope(const address_sorting_sortable* first,                              const address_sorting_sortable* second) {  return sockaddr_get_scope(&first->dest_addr) -         sockaddr_get_scope(&second->dest_addr);}static int compare_source_dest_prefix_match_lengths(    const address_sorting_sortable* first,    const address_sorting_sortable* second) {  if (first->source_addr_exists &&      address_sorting_abstract_get_family(&first->source_addr) ==          ADDRESS_SORTING_AF_INET6 &&      second->source_addr_exists &&      address_sorting_abstract_get_family(&second->source_addr) ==          ADDRESS_SORTING_AF_INET6) {    int first_match_length =        ipv6_prefix_match_length((struct sockaddr_in6*)&first->source_addr.addr,                                 (struct sockaddr_in6*)&first->dest_addr.addr);    int second_match_length = ipv6_prefix_match_length(        (struct sockaddr_in6*)&second->source_addr.addr,        (struct sockaddr_in6*)&second->dest_addr.addr);    return second_match_length - first_match_length;  }  return 0;}static int rfc_6724_compare(const void* a, const void* b) {  const address_sorting_sortable* first = (address_sorting_sortable*)a;  const address_sorting_sortable* second = (address_sorting_sortable*)b;  int out = 0;  if ((out = compare_source_addr_exists(first, second))) {    return out;  }  if ((out = compare_source_dest_scope_matches(first, second))) {    return out;  }  if ((out = compare_source_dest_labels_match(first, second))) {    return out;  }  // TODO: Implement rule 3; avoid deprecated addresses.  // TODO: Implement rule 4; avoid temporary addresses.  if ((out = compare_dest_precedence(first, second))) {    return out;  }  // TODO: Implement rule 7; prefer native transports.  if ((out = compare_dest_scope(first, second))) {    return out;  }  if ((out = compare_source_dest_prefix_match_lengths(first, second))) {    return out;  }  // Prefer that the sort be stable otherwise  return (int)(first->original_index - second->original_index);}void address_sorting_override_source_addr_factory_for_testing(    address_sorting_source_addr_factory* factory) {  if (g_current_source_addr_factory == NULL) {    abort();  }  g_current_source_addr_factory->vtable->destroy(g_current_source_addr_factory);  g_current_source_addr_factory = factory;}static void sanity_check_private_fields_are_unused(    const address_sorting_sortable* sortable) {  address_sorting_address expected_source_addr;  memset(&expected_source_addr, 0, sizeof(expected_source_addr));  if (memcmp(&expected_source_addr, &sortable->source_addr,             sizeof(address_sorting_address)) ||      sortable->original_index || sortable->source_addr_exists) {    abort();  }}void address_sorting_rfc_6724_sort(address_sorting_sortable* sortables,                                   size_t sortables_len) {  for (size_t i = 0; i < sortables_len; i++) {    sanity_check_private_fields_are_unused(&sortables[i]);    sortables[i].original_index = i;    sortables[i].source_addr_exists = address_sorting_get_source_addr(        &sortables[i].dest_addr, &sortables[i].source_addr);  }  qsort(sortables, sortables_len, sizeof(address_sorting_sortable),        rfc_6724_compare);}void address_sorting_init() {  if (g_current_source_addr_factory != NULL) {    abort();  }  g_current_source_addr_factory =      address_sorting_create_source_addr_factory_for_current_platform();}void address_sorting_shutdown() {  if (g_current_source_addr_factory == NULL) {    abort();  }  g_current_source_addr_factory->vtable->destroy(g_current_source_addr_factory);  g_current_source_addr_factory = NULL;}
 |