gweb/gresolv.c

   1 /*
   2  *
   3  *  Resolver library with GLib integration
   4  *
   5  *  Copyright (C) 2009-2010  Intel Corporation. All rights reserved.
   6  *
   7  *  This program is free software; you can redistribute it and/or modify
   8  *  it under the terms of the GNU General Public License version 2 as
   9  *  published by the Free Software Foundation.
  10  *
  11  *  This program is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  *  GNU General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU General Public License
  17  *  along with this program; if not, write to the Free Software
  18  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19  *
  20  */
  21
  22 #ifdef HAVE_CONFIG_H
  23 #include <config.h>
  24 #endif
  25
  26 #include <errno.h>
  27 #include <unistd.h>
  28 #include <stdarg.h>
  29 #include <string.h>
  30 #include <stdlib.h>
  31 #include <resolv.h>
  32 #include <sys/types.h>
  33 #include <sys/socket.h>
  34 #include <netdb.h>
  35 #include <arpa/inet.h>
  36 #include <arpa/nameser.h>
  37
  38 #include "gresolv.h"
  39
  40 struct sort_result {
  41         int precedence;
  42         int src_scope;
  43         int dst_scope;
  44         int src_label;
  45         int dst_label;
  46         gboolean reachable;
  47         union {
  48                 struct sockaddr sa;
  49                 struct sockaddr_in sin;
  50                 struct sockaddr_in6 sin6;
  51         } src;
  52         union {
  53                 struct sockaddr sa;
  54                 struct sockaddr_in sin;
  55                 struct sockaddr_in6 sin6;
  56         } dst;
  57 };
  58
  59 struct resolv_query;
  60
  61 struct resolv_lookup {
  62         GResolv *resolv;
  63         guint id;
  64
  65         int nr_results;
  66         struct sort_result *results;
  67
  68         struct resolv_query *ipv4_query;
  69         struct resolv_query *ipv6_query;
  70
  71         guint ipv4_status;
  72         guint ipv6_status;
  73
  74         GResolvResultFunc result_func;
  75         gpointer result_data;
  76 };
  77
  78 struct resolv_query {
  79         GResolv *resolv;
  80
  81         guint timeout;
  82
  83         uint16_t msgid;
  84
  85         struct resolv_lookup *lookup;
  86 };
  87
  88 struct resolv_nameserver {
  89         GResolv *resolv;
  90
  91         char *address;
  92         uint16_t port;
  93         unsigned long flags;
  94
  95         GIOChannel *udp_channel;
  96         guint udp_watch;
  97 };
  98
  99 struct _GResolv {
 100         gint ref_count;
 101
 102         guint next_lookup_id;
 103         GQueue *lookup_queue;
 104         GQueue *query_queue;
 105
 106         int index;
 107         GList *nameserver_list;
 108
 109         struct __res_state res;
 110
 111         GResolvDebugFunc debug_func;
 112         gpointer debug_data;
 113 };
 114
 115 static void sort_and_return_results(struct resolv_lookup *lookup);
 116 static void rfc3484_sort_results(struct resolv_lookup *lookup);
 117
 118 static inline void debug(GResolv *resolv, const char *format, ...)
 119 {
 120         char str[256];
 121         va_list ap;
 122
 123         if (resolv->debug_func == NULL)
 124                 return;
 125
 126         va_start(ap, format);
 127
 128         if (vsnprintf(str, sizeof(str), format, ap) > 0)
 129                 resolv->debug_func(str, resolv->debug_data);
 130
 131         va_end(ap);
 132 }
 133
 134 static void destroy_query(struct resolv_query *query)
 135 {
 136         if (query->timeout > 0)
 137                 g_source_remove(query->timeout);
 138
 139         g_free(query);
 140 }
 141
 142 static void destroy_lookup(struct resolv_lookup *lookup)
 143 {
 144         if (lookup->ipv4_query) {
 145                 destroy_query(lookup->ipv4_query);
 146                 g_queue_remove(lookup->resolv->query_queue, lookup->ipv4_query);
 147         }
 148         if (lookup->ipv6_query) {
 149                 destroy_query(lookup->ipv6_query);
 150                 g_queue_remove(lookup->resolv->query_queue, lookup->ipv6_query);
 151         }
 152         g_free(lookup->results);
 153         g_free(lookup);
 154 }
 155
 156 static gboolean query_timeout(gpointer user_data)
 157 {
 158         struct resolv_query *query = user_data;
 159         struct resolv_lookup *lookup = query->lookup;
 160         GResolv *resolv = query->resolv;
 161
 162         query->timeout = 0;
 163
 164         if (query == lookup->ipv4_query) {
 165                 lookup->ipv4_status = G_RESOLV_RESULT_STATUS_NO_RESPONSE;
 166                 lookup->ipv4_query = NULL;
 167         } else if (query == lookup->ipv6_query) {
 168                 lookup->ipv6_status = G_RESOLV_RESULT_STATUS_NO_RESPONSE;
 169                 lookup->ipv6_query = NULL;
 170         }
 171         if (!lookup->ipv4_query && !lookup->ipv4_query)
 172                 sort_and_return_results(lookup);
 173
 174         destroy_query(query);
 175         g_queue_remove(resolv->query_queue, query);
 176
 177         return FALSE;
 178 }
 179
 180 static void free_nameserver(struct resolv_nameserver *nameserver)
 181 {
 182         if (nameserver == NULL)
 183                 return;
 184
 185         if (nameserver->udp_watch > 0)
 186                 g_source_remove(nameserver->udp_watch);
 187
 188         if (nameserver->udp_channel != NULL)
 189                 g_io_channel_unref(nameserver->udp_channel);
 190
 191         g_free(nameserver->address);
 192         g_free(nameserver);
 193 }
 194
 195 static void flush_nameservers(GResolv *resolv)
 196 {
 197         GList *list;
 198
 199         for (list = g_list_first(resolv->nameserver_list);
 200                                         list; list = g_list_next(list))
 201                 free_nameserver(list->data);
 202
 203         g_list_free(resolv->nameserver_list);
 204         resolv->nameserver_list = NULL;
 205 }
 206
 207 static int send_query(GResolv *resolv, const unsigned char *buf, int len)
 208 {
 209         GList *list;
 210
 211         if (resolv->nameserver_list == NULL)
 212                 return -ENOENT;
 213
 214         for (list = g_list_first(resolv->nameserver_list);
 215                                         list; list = g_list_next(list)) {
 216                 struct resolv_nameserver *nameserver = list->data;
 217                 int sk, sent;
 218
 219                 if (nameserver->udp_channel == NULL)
 220                         continue;
 221
 222                 sk = g_io_channel_unix_get_fd(nameserver->udp_channel);
 223
 224                 sent = send(sk, buf, len, 0);
 225         }
 226
 227         return 0;
 228 }
 229
 230 static gint compare_lookup_id(gconstpointer a, gconstpointer b)
 231 {
 232         const struct resolv_lookup *lookup = a;
 233         guint id = GPOINTER_TO_UINT(b);
 234
 235         if (lookup->id < id)
 236                 return -1;
 237
 238         if (lookup->id > id)
 239                 return 1;
 240
 241         return 0;
 242 }
 243
 244 static gint compare_query_msgid(gconstpointer a, gconstpointer b)
 245 {
 246         const struct resolv_query *query = a;
 247         uint16_t msgid = GPOINTER_TO_UINT(b);
 248
 249         if (query->msgid < msgid)
 250                 return -1;
 251
 252         if (query->msgid > msgid)
 253                 return 1;
 254
 255         return 0;
 256 }
 257
 258 static void add_result(struct resolv_lookup *lookup, int family, const void *data)
 259 {
 260         int n = lookup->nr_results++;
 261         lookup->results = g_realloc(lookup->results,
 262                                     sizeof(struct sort_result) * (n+1));
 263
 264         memset(&lookup->results[n], 0, sizeof(struct sort_result));
 265
 266         lookup->results[n].dst.sa.sa_family = family;
 267         if (family == AF_INET)
 268                 memcpy(&lookup->results[n].dst.sin.sin_addr, data, NS_INADDRSZ);
 269         else
 270                 memcpy(&lookup->results[n].dst.sin6.sin6_addr, data, NS_IN6ADDRSZ);
 271 }
 272
 273 static void parse_response(struct resolv_nameserver *nameserver,
 274                                         const unsigned char *buf, int len)
 275 {
 276         GResolv *resolv = nameserver->resolv;
 277         GResolvResultStatus status;
 278         struct resolv_query *query;
 279         struct resolv_lookup *lookup;
 280         GList *list;
 281         ns_msg msg;
 282         ns_rr rr;
 283         int i, n, rcode, count;
 284
 285         debug(resolv, "response from %s", nameserver->address);
 286
 287         ns_initparse(buf, len, &msg);
 288
 289         rcode = ns_msg_getflag(msg, ns_f_rcode);
 290         count = ns_msg_count(msg, ns_s_an);
 291
 292         debug(resolv, "msg id: 0x%04x rcode: %d count: %d",
 293                                         ns_msg_id(msg), rcode, count);
 294
 295         switch (rcode) {
 296         case 0:
 297                 status = G_RESOLV_RESULT_STATUS_SUCCESS;
 298                 break;
 299         case 1:
 300                 status = G_RESOLV_RESULT_STATUS_FORMAT_ERROR;
 301                 break;
 302         case 2:
 303                 status = G_RESOLV_RESULT_STATUS_SERVER_FAILURE;
 304                 break;
 305         case 3:
 306                 status = G_RESOLV_RESULT_STATUS_NAME_ERROR;
 307                 break;
 308         case 4:
 309                 status = G_RESOLV_RESULT_STATUS_NOT_IMPLEMENTED;
 310                 break;
 311         case 5:
 312                 status = G_RESOLV_RESULT_STATUS_REFUSED;
 313                 break;
 314         default:
 315                 status = G_RESOLV_RESULT_STATUS_ERROR;
 316                 break;
 317         }
 318
 319         list = g_queue_find_custom(resolv->query_queue,
 320                         GUINT_TO_POINTER(ns_msg_id(msg)), compare_query_msgid);
 321         if (!list)
 322                 return;
 323
 324         query = list->data;
 325         lookup = query->lookup;
 326
 327         if (query == lookup->ipv6_query) {
 328                 lookup->ipv6_status = status;
 329                 lookup->ipv6_query = NULL;
 330         } else if (query == lookup->ipv4_query) {
 331                 lookup->ipv4_status = status;
 332                 lookup->ipv4_query = NULL;
 333         }
 334
 335         for (i = 0, n = 0; i < count; i++) {
 336                 ns_parserr(&msg, ns_s_an, i, &rr);
 337
 338                 if (ns_rr_class(rr) != ns_c_in)
 339                         continue;
 340
 341                 g_assert(offsetof(struct sockaddr_in, sin_addr) ==
 342                          offsetof(struct sockaddr_in6, sin6_flowinfo));
 343
 344                 if (ns_rr_type(rr) == ns_t_a &&
 345                     ns_rr_rdlen(rr) == NS_INADDRSZ) {
 346                         add_result(lookup, AF_INET, ns_rr_rdata(rr));
 347                 } else if (ns_rr_type(rr) == ns_t_aaaa &&
 348                            ns_rr_rdlen(rr) == NS_IN6ADDRSZ) {
 349                         add_result(lookup, AF_INET6, ns_rr_rdata(rr));
 350                 }
 351         }
 352
 353         if (!lookup->ipv4_query && !lookup->ipv6_query)
 354                 sort_and_return_results(lookup);
 355
 356         destroy_query(query);
 357         g_queue_remove(resolv->query_queue, query);
 358 }
 359
 360 static gboolean received_udp_data(GIOChannel *channel, GIOCondition cond,
 361                                                         gpointer user_data)
 362 {
 363         struct resolv_nameserver *nameserver = user_data;
 364         unsigned char buf[4096];
 365         int sk, len;
 366
 367         if (cond & (G_IO_NVAL | G_IO_ERR | G_IO_HUP)) {
 368                 nameserver->udp_watch = 0;
 369                 return FALSE;
 370         }
 371
 372         sk = g_io_channel_unix_get_fd(nameserver->udp_channel);
 373
 374         len = recv(sk, buf, sizeof(buf), 0);
 375         if (len < 12)
 376                 return TRUE;
 377
 378         parse_response(nameserver, buf, len);
 379
 380         return TRUE;
 381 }
 382
 383 static int connect_udp_channel(struct resolv_nameserver *nameserver)
 384 {
 385         struct addrinfo hints, *rp;
 386         char portnr[6];
 387         int err, sk;
 388
 389         memset(&hints, 0, sizeof(hints));
 390         hints.ai_family = AF_UNSPEC;
 391         hints.ai_socktype = SOCK_DGRAM;
 392         hints.ai_flags = AI_PASSIVE | AI_NUMERICSERV | AI_NUMERICHOST;
 393
 394         sprintf(portnr, "%d", nameserver->port);
 395         err = getaddrinfo(nameserver->address, portnr, &hints, &rp);
 396         if (err)
 397                 return -EINVAL;
 398
 399         /* Do not blindly copy this code elsewhere; it doesn't loop over the
 400            results using ->ai_next as it should. That's OK in *this* case
 401            because it was a numeric lookup; we *know* there's only one. */
 402         if (!rp)
 403                 return -EINVAL;
 404
 405         sk = socket(rp->ai_family, rp->ai_socktype, rp->ai_protocol);
 406         if (sk < 0) {
 407                 freeaddrinfo(rp);
 408                 return -EIO;
 409         }
 410
 411         if (connect(sk, rp->ai_addr, rp->ai_addrlen) < 0) {
 412                 close(sk);
 413                 freeaddrinfo(rp);
 414                 return -EIO;
 415         }
 416
 417         freeaddrinfo(rp);
 418
 419         nameserver->udp_channel = g_io_channel_unix_new(sk);
 420         if (nameserver->udp_channel == NULL) {
 421                 close(sk);
 422                 return -ENOMEM;
 423         }
 424
 425         g_io_channel_set_close_on_unref(nameserver->udp_channel, TRUE);
 426
 427         nameserver->udp_watch = g_io_add_watch(nameserver->udp_channel,
 428                                G_IO_IN | G_IO_NVAL | G_IO_ERR | G_IO_HUP,
 429                                received_udp_data, nameserver);
 430
 431         return 0;
 432 }
 433
 434 GResolv *g_resolv_new(int index)
 435 {
 436         GResolv *resolv;
 437
 438         if (index < 0)
 439                 return NULL;
 440
 441         resolv = g_try_new0(GResolv, 1);
 442         if (resolv == NULL)
 443                 return NULL;
 444
 445         resolv->ref_count = 1;
 446
 447         resolv->next_lookup_id = 1;
 448
 449         resolv->query_queue = g_queue_new();
 450         if (resolv->query_queue == NULL) {
 451                 g_free(resolv);
 452                 return NULL;
 453         }
 454
 455         resolv->lookup_queue = g_queue_new();
 456         if (resolv->lookup_queue == NULL) {
 457                 g_queue_free(resolv->query_queue);
 458                 g_free(resolv);
 459                 return NULL;
 460         }
 461
 462         resolv->index = index;
 463         resolv->nameserver_list = NULL;
 464
 465         res_ninit(&resolv->res);
 466
 467         return resolv;
 468 }
 469
 470 GResolv *g_resolv_ref(GResolv *resolv)
 471 {
 472         if (resolv == NULL)
 473                 return NULL;
 474
 475         g_atomic_int_inc(&resolv->ref_count);
 476
 477         return resolv;
 478 }
 479
 480 void g_resolv_unref(GResolv *resolv)
 481 {
 482         struct resolv_query *query;
 483
 484         if (resolv == NULL)
 485                 return;
 486
 487         if (g_atomic_int_dec_and_test(&resolv->ref_count) == FALSE)
 488                 return;
 489
 490         while ((query = g_queue_pop_head(resolv->query_queue)))
 491                 destroy_query(query);
 492
 493         g_queue_free(resolv->query_queue);
 494         g_queue_free(resolv->lookup_queue);
 495
 496         flush_nameservers(resolv);
 497
 498         res_nclose(&resolv->res);
 499
 500         g_free(resolv);
 501 }
 502
 503 void g_resolv_set_debug(GResolv *resolv,
 504                                 GResolvDebugFunc func, gpointer user_data)
 505 {
 506         if (resolv == NULL)
 507                 return;
 508
 509         resolv->debug_func = func;
 510         resolv->debug_data = user_data;
 511 }
 512
 513 gboolean g_resolv_add_nameserver(GResolv *resolv, const char *address,
 514                                         uint16_t port, unsigned long flags)
 515 {
 516         struct resolv_nameserver *nameserver;
 517
 518         if (resolv == NULL)
 519                 return FALSE;
 520
 521         nameserver = g_try_new0(struct resolv_nameserver, 1);
 522         if (nameserver == NULL)
 523                 return FALSE;
 524
 525         nameserver->address = g_strdup(address);
 526         nameserver->port = port;
 527         nameserver->flags = flags;
 528
 529         if (connect_udp_channel(nameserver) < 0) {
 530                 free_nameserver(nameserver);
 531                 return FALSE;
 532         }
 533
 534         nameserver->resolv = resolv;
 535
 536         resolv->nameserver_list = g_list_append(resolv->nameserver_list,
 537                                                                 nameserver);
 538
 539         debug(resolv, "setting nameserver %s", address);
 540
 541         return TRUE;
 542 }
 543
 544 void g_resolv_flush_nameservers(GResolv *resolv)
 545 {
 546         if (resolv == NULL)
 547                 return;
 548
 549         flush_nameservers(resolv);
 550 }
 551
 552 static void sort_and_return_results(struct resolv_lookup *lookup)
 553 {
 554         char buf[100];
 555         GResolvResultStatus status;
 556         char **results = g_try_new0(char *, lookup->nr_results + 1);
 557         int i, n = 0;
 558
 559         if (!results)
 560                 return;
 561
 562         rfc3484_sort_results(lookup);
 563
 564         for (i = 0; i < lookup->nr_results; i++) {
 565                 if (lookup->results[i].dst.sa.sa_family == AF_INET) {
 566                         if (!inet_ntop(AF_INET, &lookup->results[i].dst.sin.sin_addr,
 567                                        buf, sizeof(buf)))
 568                                 continue;
 569                 } else if (lookup->results[i].dst.sa.sa_family == AF_INET6) {
 570                         if (!inet_ntop(AF_INET6, &lookup->results[i].dst.sin6.sin6_addr,
 571                                        buf, sizeof(buf)))
 572                                 continue;
 573                 } else
 574                         continue;
 575
 576                 results[n++] = strdup(buf);
 577         }
 578         results[n++] = NULL;
 579
 580         status = lookup->ipv4_status;
 581         if (status == G_RESOLV_RESULT_STATUS_SUCCESS)
 582                 status = lookup->ipv6_status;
 583
 584         lookup->result_func(status, results, lookup->result_data);
 585
 586         g_strfreev(results);
 587         g_queue_remove(lookup->resolv->lookup_queue, lookup);
 588         destroy_lookup(lookup);
 589 }
 590
 591 static gint add_query(struct resolv_lookup *lookup, const char *hostname, int type)
 592 {
 593         struct resolv_query *query = g_try_new0(struct resolv_query, 1);
 594         unsigned char buf[4096];
 595         int len;
 596
 597         if (query == NULL)
 598                 return -ENOMEM;
 599
 600         len = res_mkquery(ns_o_query, hostname, ns_c_in, type,
 601                                         NULL, 0, NULL, buf, sizeof(buf));
 602
 603         query->msgid = buf[0] << 8 | buf[1];
 604
 605         if (send_query(lookup->resolv, buf, len) < 0)
 606                 return -EIO;
 607
 608         query->resolv = lookup->resolv;
 609         query->lookup = lookup;
 610
 611         g_queue_push_tail(lookup->resolv->query_queue, query);
 612
 613         query->timeout = g_timeout_add_seconds(5, query_timeout, query);
 614
 615         if (type == ns_t_aaaa)
 616                 lookup->ipv6_query = query;
 617         else
 618                 lookup->ipv4_query = query;
 619
 620         return 0;
 621 }
 622
 623 guint g_resolv_lookup_hostname(GResolv *resolv, const char *hostname,
 624                                 GResolvResultFunc func, gpointer user_data)
 625 {
 626         struct resolv_lookup *lookup;
 627
 628         debug(resolv, "lookup hostname %s", hostname);
 629
 630         if (resolv == NULL)
 631                 return 0;
 632
 633         if (resolv->nameserver_list == NULL) {
 634                 int i;
 635
 636                 for (i = 0; i < resolv->res.nscount; i++) {
 637                         char buf[100];
 638                         int family = resolv->res.nsaddr_list[i].sin_family;
 639                         void *sa_addr = &resolv->res.nsaddr_list[i].sin_addr;
 640
 641                         if (family != AF_INET && resolv->res._u._ext.nsaddrs[i]) {
 642                                 family = AF_INET6;
 643                                 sa_addr = &resolv->res._u._ext.nsaddrs[i]->sin6_addr;
 644                         }
 645                         if (family != AF_INET && family != AF_INET6)
 646                                 continue;
 647
 648                         if (inet_ntop(family, sa_addr, buf, sizeof(buf)))
 649                                 g_resolv_add_nameserver(resolv, buf, 53, 0);
 650                 }
 651
 652                 if (resolv->nameserver_list == NULL)
 653                         g_resolv_add_nameserver(resolv, "127.0.0.1", 53, 0);
 654         }
 655
 656         lookup = g_try_new0(struct resolv_lookup, 1);
 657         if (!lookup)
 658                 return 0;
 659
 660         lookup->resolv = resolv;
 661         lookup->result_func = func;
 662         lookup->result_data = user_data;
 663         lookup->id = resolv->next_lookup_id++;
 664
 665         if (add_query(lookup, hostname, ns_t_a)) {
 666                 g_free(lookup);
 667                 return -EIO;
 668         }
 669         if (add_query(lookup, hostname, ns_t_aaaa)) {
 670                 destroy_query(lookup->ipv4_query);
 671                 g_queue_remove(resolv->query_queue, lookup->ipv4_query);
 672                 g_free(lookup);
 673                 return -EIO;
 674         }
 675
 676         g_queue_push_tail(resolv->lookup_queue, lookup);
 677         return lookup->id;
 678 }
 679
 680 gboolean g_resolv_cancel_lookup(GResolv *resolv, guint id)
 681 {
 682         GList *list;
 683
 684         list = g_queue_find_custom(resolv->lookup_queue,
 685                                 GUINT_TO_POINTER(id), compare_lookup_id);
 686
 687         if (list == NULL)
 688                 return FALSE;
 689
 690         destroy_lookup(list->data);
 691         g_queue_remove(resolv->query_queue, list->data);
 692
 693         return TRUE;
 694 }
 695
 696 static void find_srcaddr(struct sort_result *res)
 697 {
 698         int fd;
 699         socklen_t sl = sizeof(res->src);
 700
 701         fd = socket(res->dst.sa.sa_family, SOCK_DGRAM, IPPROTO_IP);
 702         if (fd < 0)
 703                 return;
 704
 705         if (connect(fd, &res->dst.sa, sizeof(res->dst))) {
 706                 close(fd);
 707                 return;
 708         }
 709         if (getsockname(fd, &res->src.sa, &sl)) {
 710                 close(fd);
 711                 return;
 712         }
 713         res->reachable = TRUE;
 714         close(fd);
 715 }
 716
 717 struct gai_table
 718 {
 719         unsigned char addr[NS_IN6ADDRSZ];
 720         int mask;
 721         int value;
 722 };
 723
 724 static const struct gai_table gai_labels[] = {
 725         {
 726                 .addr = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 727                           0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01 },
 728                 .mask = 128,
 729                 .value = 0,
 730         }, {
 731                 .addr = { 0x20, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 732                           0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
 733                 .mask = 16,
 734                 .value = 2,
 735         }, {
 736                 .addr = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 737                           0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
 738                 .mask = 96,
 739                 .value = 3,
 740         }, {
 741                 .addr = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 742                           0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00 },
 743                 .mask = 96,
 744                 .value = 4,
 745         }, {
 746                 /* Variations from RFC 3484, matching glibc behaviour */
 747                 .addr = { 0xfe, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 748                           0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
 749                 .mask = 10,
 750                 .value = 5,
 751         }, {
 752                 .addr = { 0xfc, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 753                           0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
 754                 .mask = 7,
 755                 .value = 6,
 756         }, {
 757                 .addr = { 0x20, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 758                           0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
 759                 .mask = 32,
 760                 .value = 7,
 761         }, {
 762                 /* catch-all */
 763                 .addr = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 764                           0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
 765                 .mask = 0,
 766                 .value = 1,
 767         }
 768 };
 769
 770 static const struct gai_table gai_precedences[] = {
 771         {
 772                 .addr = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 773                           0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01 },
 774                 .mask = 128,
 775                 .value = 50,
 776         }, {
 777                 .addr = { 0x20, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 778                           0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
 779                 .mask = 16,
 780                 .value = 30,
 781         }, {
 782                 .addr = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 783                           0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
 784                 .mask = 96,
 785                 .value = 20,
 786         }, {
 787                 .addr = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 788                           0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00 },
 789                 .mask = 96,
 790                 .value = 10,
 791         }, {
 792                 .addr = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 793                           0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
 794                 .mask = 0,
 795                 .value = 40,
 796         }
 797 };
 798
 799 static unsigned char v4mapped[] = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 800                                     0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00 };
 801
 802 static gboolean mask_compare(const unsigned char *one, const unsigned char *two, int mask)
 803 {
 804         if (mask > 8) {
 805                 if (memcmp(one, two, mask / 8))
 806                         return FALSE;
 807                 one += mask / 8;
 808                 two += mask / 8;
 809                 mask %= 8;
 810         }
 811         if (mask && ((*one ^ *two) >> (8-mask)))
 812             return FALSE;
 813
 814         return TRUE;
 815 }
 816
 817 static int match_gai_table(struct sockaddr *sa, const struct gai_table *tbl)
 818 {
 819         struct sockaddr_in *sin = (void *)sa;
 820         struct sockaddr_in6 *sin6 = (void *)sa;
 821         void *addr;
 822
 823         if (sa->sa_family == AF_INET) {
 824                 addr = v4mapped;
 825                 memcpy(v4mapped+12, &sin->sin_addr, NS_INADDRSZ);
 826         } else
 827                 addr = &sin6->sin6_addr;
 828
 829         while (1) {
 830                 if (mask_compare(addr, tbl->addr, tbl->mask))
 831                         return tbl->value;
 832                 tbl++;
 833         }
 834 }
 835
 836 #define DQUAD(_a,_b,_c,_d) ( ((_a)<<24) | ((_b)<<16) | ((_c)<<8) | (_d) )
 837 #define V4MATCH(addr, a,b,c,d, m) ( ((addr) ^ DQUAD(a,b,c,d)) >> (32 - (m)) )
 838
 839 #define RFC3484_SCOPE_LINK      2
 840 #define RFC3484_SCOPE_SITE      5
 841 #define RFC3484_SCOPE_GLOBAL    14
 842
 843 static int addr_scope(struct sockaddr *sa)
 844 {
 845         if (sa->sa_family == AF_INET) {
 846                 struct sockaddr_in *sin = (void *)sa;
 847                 guint32 addr = ntohl(sin->sin_addr.s_addr);
 848
 849                 if (V4MATCH(addr, 169,254,0,0, 16) ||
 850                     V4MATCH(addr, 127,0,0,0,   8))
 851                         return RFC3484_SCOPE_LINK;
 852
 853                 /* Site-local */
 854                 if (V4MATCH(addr, 10,0,0,0,    8) ||
 855                     V4MATCH(addr, 172,16,0,0,  12) ||
 856                     V4MATCH(addr, 192,168,0,0, 16))
 857                         return RFC3484_SCOPE_SITE;
 858
 859                 /* Global */
 860                 return RFC3484_SCOPE_GLOBAL;
 861         } else {
 862                 struct sockaddr_in6 *sin6 = (void *)sa;
 863
 864                 /* Multicast addresses have a 4-bit scope field */
 865                 if (IN6_IS_ADDR_MULTICAST(&sin6->sin6_addr))
 866                         return sin6->sin6_addr.s6_addr[1] & 0xf;
 867
 868                 if (IN6_IS_ADDR_LINKLOCAL(&sin6->sin6_addr) ||
 869                     IN6_IS_ADDR_LOOPBACK(&sin6->sin6_addr))
 870                         return RFC3484_SCOPE_LINK;
 871
 872                 if (IN6_IS_ADDR_SITELOCAL(&sin6->sin6_addr))
 873                         return RFC3484_SCOPE_SITE;
 874
 875                 return RFC3484_SCOPE_GLOBAL;
 876         }
 877 }
 878
 879 static int rfc3484_compare(const void *__one, const void *__two)
 880 {
 881         const struct sort_result *one = __one;
 882         const struct sort_result *two = __two;
 883
 884         /* Rule 1: Avoid unusable destinations */
 885         if (one->reachable && !two->reachable)
 886                 return -1;
 887         else if (two->reachable && !one->reachable)
 888                 return 1;
 889
 890         /* Rule 2: Prefer matching scope */
 891         if (one->dst_scope == one->src_scope &&
 892             two->dst_scope != two->src_scope)
 893                 return -1;
 894         else if (two->dst_scope == two->src_scope &&
 895                  one->dst_scope != one->src_scope)
 896                 return 1;
 897
 898         /* Rule 3: Avoid deprecated addresses */
 899
 900         /* Rule 4: Prefer home addresses */
 901
 902         /* Rule 5: Prefer matching label */
 903         if (one->dst_label == one->src_label &&
 904             two->dst_label != two->src_label)
 905                 return -1;
 906         else if (two->dst_label == two->src_label &&
 907                  one->dst_label != one->src_label)
 908                 return 1;
 909
 910         /* Rule 6: Prefer higher precedence */
 911         if (one->precedence > two->precedence)
 912                 return -1;
 913         else if (two->precedence > one->precedence)
 914                 return 1;
 915
 916         /* Rule 7: Prefer native transport */
 917
 918         /* Rule 8: Prefer smaller scope */
 919         if (one->dst_scope != two->dst_scope)
 920                 return one->dst_scope - two->dst_scope;
 921
 922         /* Rule 9: Use longest matching prefix */
 923         if (one->dst.sa.sa_family == AF_INET) {
 924                 /* Rule 9 is meaningless and counterproductive for Legacy IP
 925                    unless perhaps we can tell that it's actually on the local
 926                    subnet. But we don't (yet) have local interface config
 927                    information, so do nothing here for Legacy IP for now. */
 928         } else {
 929                 int i;
 930
 931                 for (i = 0; i < 4; i++) {
 932                         guint32 cmp_one, cmp_two;
 933
 934                         cmp_one = one->src.sin6.sin6_addr.s6_addr32[i] ^
 935                                 one->dst.sin6.sin6_addr.s6_addr32[i];
 936                         cmp_two = two->src.sin6.sin6_addr.s6_addr32[i] ^
 937                                 two->dst.sin6.sin6_addr.s6_addr32[i];
 938
 939                         if (!cmp_two && !cmp_one)
 940                                 continue;
 941
 942                         if (cmp_one && !cmp_two)
 943                                 return 1;
 944                         if (cmp_two && !cmp_one)
 945                                 return -1;
 946
 947                         /* g_bit_storage() is effectively fls() */
 948                         cmp_one = g_bit_storage(ntohl(cmp_one));
 949                         cmp_two = g_bit_storage(ntohl(cmp_two));
 950
 951                         if (cmp_one == cmp_two)
 952                                 break;
 953
 954                         return cmp_one - cmp_two;
 955                 }
 956         }
 957
 958
 959         /* Rule 10: Otherwise, leave the order unchanged */
 960         if (one < two)
 961                 return -1;
 962         else
 963                 return 1;
 964 }
 965
 966 static void rfc3484_sort_results(struct resolv_lookup *lookup)
 967 {
 968         int i;
 969
 970         for (i = 0; i < lookup->nr_results; i++) {
 971                 struct sort_result *res = &lookup->results[i];
 972                 find_srcaddr(res);
 973                 res->precedence = match_gai_table(&res->dst.sa, gai_precedences);
 974                 res->dst_label = match_gai_table(&res->dst.sa, gai_labels);
 975                 res->src_label = match_gai_table(&res->src.sa, gai_labels);
 976                 res->dst_scope = addr_scope(&res->dst.sa);
 977                 res->src_scope = addr_scope(&res->src.sa);
 978         }
 979
 980         qsort(lookup->results, lookup->nr_results, sizeof(struct sort_result),
 981               rfc3484_compare);
 982 }