"Fossies" - the Fresh Open Source Software Archive

Member "c-ares-1.17.2/src/lib/ares__sortaddrinfo.c" (8 Aug 2021, 14026 Bytes) of package /linux/misc/dns/c-ares-1.17.2.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "ares__sortaddrinfo.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 1.17.1_vs_1.17.2.

    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 by 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 
   37 #include "ares_setup.h"
   38 
   39 #ifdef HAVE_NETINET_IN_H
   40 #  include <netinet/in.h>
   41 #endif
   42 #ifdef HAVE_NETDB_H
   43 #  include <netdb.h>
   44 #endif
   45 #ifdef HAVE_STRINGS_H
   46 #  include <strings.h>
   47 #endif
   48 
   49 #include <assert.h>
   50 #include <limits.h>
   51 
   52 #include "ares.h"
   53 #include "ares_private.h"
   54 
   55 struct addrinfo_sort_elem
   56 {
   57   struct ares_addrinfo_node *ai;
   58   int has_src_addr;
   59   ares_sockaddr src_addr;
   60   int original_order;
   61 };
   62 
   63 #define ARES_IPV6_ADDR_MC_SCOPE(a) ((a)->s6_addr[1] & 0x0f)
   64 
   65 #define ARES_IPV6_ADDR_SCOPE_NODELOCAL       0x01
   66 #define ARES_IPV6_ADDR_SCOPE_INTFACELOCAL    0x01
   67 #define ARES_IPV6_ADDR_SCOPE_LINKLOCAL       0x02
   68 #define ARES_IPV6_ADDR_SCOPE_SITELOCAL       0x05
   69 #define ARES_IPV6_ADDR_SCOPE_ORGLOCAL        0x08
   70 #define ARES_IPV6_ADDR_SCOPE_GLOBAL          0x0e
   71 
   72 #define ARES_IN_LOOPBACK(a) ((((long int)(a)) & 0xff000000) == 0x7f000000)
   73 
   74 /* RFC 4193. */
   75 #define ARES_IN6_IS_ADDR_ULA(a) (((a)->s6_addr[0] & 0xfe) == 0xfc)
   76 
   77 /* These macros are modelled after the ones in <netinet/in6.h>. */
   78 /* RFC 4380, section 2.6 */
   79 #define ARES_IN6_IS_ADDR_TEREDO(a)    \
   80         ((*(const unsigned int *)(const void *)(&(a)->s6_addr[0]) == 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 
   89 static int get_scope(const struct sockaddr *addr)
   90 {
   91   if (addr->sa_family == AF_INET6)
   92     {
   93       const struct sockaddr_in6 *addr6 = CARES_INADDR_CAST(const struct sockaddr_in6 *, addr);
   94       if (IN6_IS_ADDR_MULTICAST(&addr6->sin6_addr))
   95         {
   96           return ARES_IPV6_ADDR_MC_SCOPE(&addr6->sin6_addr);
   97         }
   98       else if (IN6_IS_ADDR_LOOPBACK(&addr6->sin6_addr) ||
   99                IN6_IS_ADDR_LINKLOCAL(&addr6->sin6_addr))
  100         {
  101           /*
  102            * RFC 4291 section 2.5.3 says loopback is to be treated as having
  103            * link-local scope.
  104            */
  105           return ARES_IPV6_ADDR_SCOPE_LINKLOCAL;
  106         }
  107       else if (IN6_IS_ADDR_SITELOCAL(&addr6->sin6_addr))
  108         {
  109           return ARES_IPV6_ADDR_SCOPE_SITELOCAL;
  110         }
  111       else
  112         {
  113           return ARES_IPV6_ADDR_SCOPE_GLOBAL;
  114         }
  115     }
  116   else if (addr->sa_family == AF_INET)
  117     {
  118       const struct sockaddr_in *addr4 = CARES_INADDR_CAST(const struct sockaddr_in *, addr);
  119       unsigned long int na = ntohl(addr4->sin_addr.s_addr);
  120       if (ARES_IN_LOOPBACK(na) || /* 127.0.0.0/8 */
  121           (na & 0xffff0000) == 0xa9fe0000) /* 169.254.0.0/16 */
  122         {
  123           return ARES_IPV6_ADDR_SCOPE_LINKLOCAL;
  124         }
  125       else
  126         {
  127           /*
  128            * RFC 6724 section 3.2. Other IPv4 addresses, including private
  129            * addresses and shared addresses (100.64.0.0/10), are assigned global
  130            * scope.
  131            */
  132           return ARES_IPV6_ADDR_SCOPE_GLOBAL;
  133         }
  134     }
  135   else
  136     {
  137       /*
  138        * This should never happen.
  139        * Return a scope with low priority as a last resort.
  140        */
  141       return ARES_IPV6_ADDR_SCOPE_NODELOCAL;
  142     }
  143 }
  144 
  145 static int get_label(const struct sockaddr *addr)
  146 {
  147   if (addr->sa_family == AF_INET)
  148     {
  149       return 4;
  150     }
  151   else if (addr->sa_family == AF_INET6)
  152     {
  153       const struct sockaddr_in6 *addr6 = CARES_INADDR_CAST(const struct sockaddr_in6 *, addr);
  154       if (IN6_IS_ADDR_LOOPBACK(&addr6->sin6_addr))
  155         {
  156           return 0;
  157         }
  158       else if (IN6_IS_ADDR_V4MAPPED(&addr6->sin6_addr))
  159         {
  160           return 4;
  161         }
  162       else if (ARES_IN6_IS_ADDR_6TO4(&addr6->sin6_addr))
  163         {
  164           return 2;
  165         }
  166       else if (ARES_IN6_IS_ADDR_TEREDO(&addr6->sin6_addr))
  167         {
  168           return 5;
  169         }
  170       else if (ARES_IN6_IS_ADDR_ULA(&addr6->sin6_addr))
  171         {
  172           return 13;
  173         }
  174       else if (IN6_IS_ADDR_V4COMPAT(&addr6->sin6_addr))
  175         {
  176           return 3;
  177         }
  178       else if (IN6_IS_ADDR_SITELOCAL(&addr6->sin6_addr))
  179         {
  180           return 11;
  181         }
  182       else if (ARES_IN6_IS_ADDR_6BONE(&addr6->sin6_addr))
  183         {
  184           return 12;
  185         }
  186       else
  187         {
  188           /* All other IPv6 addresses, including global unicast addresses. */
  189           return 1;
  190         }
  191     }
  192   else
  193     {
  194       /*
  195        * This should never happen.
  196        * Return a semi-random label as a last resort.
  197        */
  198       return 1;
  199     }
  200 }
  201 
  202 /*
  203  * Get the precedence for a given IPv4/IPv6 address.
  204  * RFC 6724, section 2.1.
  205  */
  206 static int get_precedence(const struct sockaddr *addr)
  207 {
  208   if (addr->sa_family == AF_INET)
  209     {
  210       return 35;
  211     }
  212   else if (addr->sa_family == AF_INET6)
  213     {
  214       const struct sockaddr_in6 *addr6 = CARES_INADDR_CAST(const struct sockaddr_in6 *, addr);
  215       if (IN6_IS_ADDR_LOOPBACK(&addr6->sin6_addr))
  216         {
  217           return 50;
  218         }
  219       else if (IN6_IS_ADDR_V4MAPPED(&addr6->sin6_addr))
  220         {
  221           return 35;
  222         }
  223       else if (ARES_IN6_IS_ADDR_6TO4(&addr6->sin6_addr))
  224         {
  225           return 30;
  226         }
  227       else if (ARES_IN6_IS_ADDR_TEREDO(&addr6->sin6_addr))
  228         {
  229           return 5;
  230         }
  231       else if (ARES_IN6_IS_ADDR_ULA(&addr6->sin6_addr))
  232         {
  233           return 3;
  234         }
  235       else if (IN6_IS_ADDR_V4COMPAT(&addr6->sin6_addr) ||
  236                IN6_IS_ADDR_SITELOCAL(&addr6->sin6_addr) ||
  237                ARES_IN6_IS_ADDR_6BONE(&addr6->sin6_addr))
  238         {
  239           return 1;
  240         }
  241       else
  242         {
  243           /* All other IPv6 addresses, including global unicast addresses. */
  244           return 40;
  245         }
  246     }
  247   else
  248     {
  249       return 1;
  250     }
  251 }
  252 
  253 /*
  254  * Find number of matching initial bits between the two addresses a1 and a2.
  255  */
  256 static int common_prefix_len(const struct in6_addr *a1,
  257                              const struct in6_addr *a2)
  258 {
  259   const char *p1 = (const char *)a1;
  260   const char *p2 = (const char *)a2;
  261   unsigned i;
  262   for (i = 0; i < sizeof(*a1); ++i)
  263     {
  264       int x, j;
  265       if (p1[i] == p2[i])
  266         {
  267           continue;
  268         }
  269       x = p1[i] ^ p2[i];
  270       for (j = 0; j < CHAR_BIT; ++j)
  271         {
  272           if (x & (1 << (CHAR_BIT - 1)))
  273             {
  274               return i * CHAR_BIT + j;
  275             }
  276           x <<= 1;
  277         }
  278     }
  279   return sizeof(*a1) * CHAR_BIT;
  280 }
  281 
  282 /*
  283  * Compare two source/destination address pairs.
  284  * RFC 6724, section 6.
  285  */
  286 static int rfc6724_compare(const void *ptr1, const void *ptr2)
  287 {
  288   const struct addrinfo_sort_elem *a1 = (const struct addrinfo_sort_elem *)ptr1;
  289   const struct addrinfo_sort_elem *a2 = (const struct addrinfo_sort_elem *)ptr2;
  290   int scope_src1, scope_dst1, scope_match1;
  291   int scope_src2, scope_dst2, scope_match2;
  292   int label_src1, label_dst1, label_match1;
  293   int label_src2, label_dst2, label_match2;
  294   int precedence1, precedence2;
  295   int prefixlen1, prefixlen2;
  296 
  297   /* Rule 1: Avoid unusable destinations. */
  298   if (a1->has_src_addr != a2->has_src_addr)
  299     {
  300       return a2->has_src_addr - a1->has_src_addr;
  301     }
  302 
  303   /* Rule 2: Prefer matching scope. */
  304   scope_src1 = get_scope(&a1->src_addr.sa);
  305   scope_dst1 = get_scope(a1->ai->ai_addr);
  306   scope_match1 = (scope_src1 == scope_dst1);
  307 
  308   scope_src2 = get_scope(&a2->src_addr.sa);
  309   scope_dst2 = get_scope(a2->ai->ai_addr);
  310   scope_match2 = (scope_src2 == scope_dst2);
  311 
  312   if (scope_match1 != scope_match2)
  313     {
  314       return scope_match2 - scope_match1;
  315     }
  316 
  317   /* Rule 3: Avoid deprecated addresses.  */
  318 
  319   /* Rule 4: Prefer home addresses.  */
  320 
  321   /* Rule 5: Prefer matching label. */
  322   label_src1 = get_label(&a1->src_addr.sa);
  323   label_dst1 = get_label(a1->ai->ai_addr);
  324   label_match1 = (label_src1 == label_dst1);
  325 
  326   label_src2 = get_label(&a2->src_addr.sa);
  327   label_dst2 = get_label(a2->ai->ai_addr);
  328   label_match2 = (label_src2 == label_dst2);
  329 
  330   if (label_match1 != label_match2)
  331     {
  332       return label_match2 - label_match1;
  333     }
  334 
  335   /* Rule 6: Prefer higher precedence. */
  336   precedence1 = get_precedence(a1->ai->ai_addr);
  337   precedence2 = get_precedence(a2->ai->ai_addr);
  338   if (precedence1 != precedence2)
  339     {
  340       return precedence2 - precedence1;
  341     }
  342 
  343   /* Rule 7: Prefer native transport.  */
  344 
  345   /* Rule 8: Prefer smaller scope. */
  346   if (scope_dst1 != scope_dst2)
  347     {
  348       return scope_dst1 - scope_dst2;
  349     }
  350 
  351   /* Rule 9: Use longest matching prefix. */
  352   if (a1->has_src_addr && a1->ai->ai_addr->sa_family == AF_INET6 &&
  353       a2->has_src_addr && a2->ai->ai_addr->sa_family == AF_INET6)
  354     {
  355       const struct sockaddr_in6 *a1_src = &a1->src_addr.sa6;
  356       const struct sockaddr_in6 *a1_dst =
  357           CARES_INADDR_CAST(const struct sockaddr_in6 *, a1->ai->ai_addr);
  358       const struct sockaddr_in6 *a2_src = &a2->src_addr.sa6;
  359       const struct sockaddr_in6 *a2_dst =
  360           CARES_INADDR_CAST(const struct sockaddr_in6 *, a2->ai->ai_addr);
  361       prefixlen1 = common_prefix_len(&a1_src->sin6_addr, &a1_dst->sin6_addr);
  362       prefixlen2 = common_prefix_len(&a2_src->sin6_addr, &a2_dst->sin6_addr);
  363       if (prefixlen1 != prefixlen2)
  364         {
  365           return prefixlen2 - prefixlen1;
  366         }
  367     }
  368 
  369   /*
  370    * Rule 10: Leave the order unchanged.
  371    * We need this since qsort() is not necessarily stable.
  372    */
  373   return a1->original_order - a2->original_order;
  374 }
  375 
  376 /*
  377  * Find the source address that will be used if trying to connect to the given
  378  * address.
  379  *
  380  * Returns 1 if a source address was found, 0 if the address is unreachable,
  381  * and -1 if a fatal error occurred. If 0 or 1, the contents of src_addr are
  382  * undefined.
  383  */
  384 static int find_src_addr(ares_channel channel,
  385                          const struct sockaddr *addr,
  386                          struct sockaddr *src_addr)
  387 {
  388   ares_socket_t sock;
  389   int ret;
  390   ares_socklen_t len;
  391 
  392   switch (addr->sa_family)
  393     {
  394     case AF_INET:
  395       len = sizeof(struct sockaddr_in);
  396       break;
  397     case AF_INET6:
  398       len = sizeof(struct sockaddr_in6);
  399       break;
  400     default:
  401       /* No known usable source address for non-INET families. */
  402       return 0;
  403     }
  404 
  405   sock = ares__open_socket(channel, addr->sa_family, SOCK_DGRAM, IPPROTO_UDP);
  406   if (sock == ARES_SOCKET_BAD)
  407     {
  408       if (errno == EAFNOSUPPORT)
  409         {
  410           return 0;
  411         }
  412       else
  413         {
  414           return -1;
  415         }
  416     }
  417 
  418   do
  419     {
  420       ret = ares__connect_socket(channel, sock, addr, len);
  421     }
  422   while (ret == -1 && errno == EINTR);
  423 
  424   if (ret == -1)
  425     {
  426       ares__close_socket(channel, sock);
  427       return 0;
  428     }
  429 
  430   if (getsockname(sock, src_addr, &len) != 0)
  431     {
  432       ares__close_socket(channel, sock);
  433       return -1;
  434     }
  435   ares__close_socket(channel, sock);
  436   return 1;
  437 }
  438 
  439 /*
  440  * Sort the linked list starting at sentinel->ai_next in RFC6724 order.
  441  * Will leave the list unchanged if an error occurs.
  442  */
  443 int ares__sortaddrinfo(ares_channel channel, struct ares_addrinfo_node *list_sentinel)
  444 {
  445   struct ares_addrinfo_node *cur;
  446   int nelem = 0, i;
  447   int has_src_addr;
  448   struct addrinfo_sort_elem *elems;
  449 
  450   cur = list_sentinel->ai_next;
  451   while (cur)
  452     {
  453       ++nelem;
  454       cur = cur->ai_next;
  455     }
  456 
  457   if (!nelem)
  458       return ARES_ENODATA;
  459 
  460   elems = (struct addrinfo_sort_elem *)ares_malloc(
  461       nelem * sizeof(struct addrinfo_sort_elem));
  462   if (!elems)
  463     {
  464       return ARES_ENOMEM;
  465     }
  466 
  467   /*
  468    * Convert the linked list to an array that also contains the candidate
  469    * source address for each destination address.
  470    */
  471   for (i = 0, cur = list_sentinel->ai_next; i < nelem; ++i, cur = cur->ai_next)
  472     {
  473       assert(cur != NULL);
  474       elems[i].ai = cur;
  475       elems[i].original_order = i;
  476       has_src_addr = find_src_addr(channel, cur->ai_addr, &elems[i].src_addr.sa);
  477       if (has_src_addr == -1)
  478         {
  479           ares_free(elems);
  480           return ARES_ENOTFOUND;
  481         }
  482       elems[i].has_src_addr = has_src_addr;
  483     }
  484 
  485   /* Sort the addresses, and rearrange the linked list so it matches the sorted
  486    * order. */
  487   qsort((void *)elems, nelem, sizeof(struct addrinfo_sort_elem),
  488         rfc6724_compare);
  489 
  490   list_sentinel->ai_next = elems[0].ai;
  491   for (i = 0; i < nelem - 1; ++i)
  492     {
  493       elems[i].ai->ai_next = elems[i + 1].ai;
  494     }
  495   elems[nelem - 1].ai->ai_next = NULL;
  496 
  497   ares_free(elems);
  498   return ARES_SUCCESS;
  499 }