path: root/third_party/address_sorting/address_sorting.c

/*	$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;
}