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->ipv4_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
 924         /* Rule 10: Otherwise, leave the order unchanged */
 925         if (one < two)
 926                 return -1;
 927         else
 928                 return 1;
 929 }
 930
 931 static void rfc3484_sort_results(struct resolv_lookup *lookup)
 932 {
 933         int i;
 934
 935         for (i = 0; i < lookup->nr_results; i++) {
 936                 struct sort_result *res = &lookup->results[i];
 937                 find_srcaddr(res);
 938                 res->precedence = match_gai_table(&res->dst.sa, gai_precedences);
 939                 res->dst_label = match_gai_table(&res->dst.sa, gai_labels);
 940                 res->src_label = match_gai_table(&res->src.sa, gai_labels);
 941                 res->dst_scope = addr_scope(&res->dst.sa);
 942                 res->src_scope = addr_scope(&res->src.sa);
 943         }
 944
 945         qsort(lookup->results, lookup->nr_results, sizeof(struct sort_result),
 946               rfc3484_compare);
 947 }