contrib/bind-9.3/lib/dns/dispatch.c

   1 /*
   2  * Copyright (C) 2004, 2006  Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (C) 1999-2003  Internet Software Consortium.
   4  *
   5  * Permission to use, copy, modify, and distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
  10  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  11  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  12  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  13  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  14  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  15  * PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 /* $Id: dispatch.c,v 1.101.2.6.2.13.6.4 2007/06/27 04:19:50 marka Exp $ */
  19
  20 #include <config.h>
  21
  22 #include <stdlib.h>
  23 #include <sys/types.h>
  24 #include <unistd.h>
  25
  26 #include <isc/entropy.h>
  27 #include <isc/mem.h>
  28 #include <isc/mutex.h>
  29 #include <isc/print.h>
  30 #include <isc/string.h>
  31 #include <isc/task.h>
  32 #include <isc/time.h>
  33 #include <isc/util.h>
  34
  35 #include <dns/acl.h>
  36 #include <dns/dispatch.h>
  37 #include <dns/events.h>
  38 #include <dns/log.h>
  39 #include <dns/message.h>
  40 #include <dns/portlist.h>
  41 #include <dns/tcpmsg.h>
  42 #include <dns/types.h>
  43
  44 typedef ISC_LIST(dns_dispentry_t)       dns_displist_t;
  45
  46 typedef struct dns_nsid {
  47         isc_uint16_t    nsid_state;
  48         isc_uint16_t    *nsid_vtable;
  49         isc_uint16_t    *nsid_pool;
  50         isc_uint16_t    nsid_a1, nsid_a2, nsid_a3;
  51         isc_uint16_t    nsid_c1, nsid_c2, nsid_c3;
  52         isc_uint16_t    nsid_state2;
  53         isc_boolean_t   nsid_usepool;
  54 } dns_nsid_t;
  55
  56 typedef struct dns_qid {
  57         unsigned int    magic;
  58         unsigned int    qid_nbuckets;   /* hash table size */
  59         unsigned int    qid_increment;  /* id increment on collision */
  60         isc_mutex_t     lock;
  61         dns_nsid_t      nsid;
  62         dns_displist_t  *qid_table;     /* the table itself */
  63 } dns_qid_t;
  64
  65 struct dns_dispatchmgr {
  66         /* Unlocked. */
  67         unsigned int                    magic;
  68         isc_mem_t                      *mctx;
  69         dns_acl_t                      *blackhole;
  70         dns_portlist_t                 *portlist;
  71
  72         /* Locked by "lock". */
  73         isc_mutex_t                     lock;
  74         unsigned int                    state;
  75         ISC_LIST(dns_dispatch_t)        list;
  76
  77         /* locked by buffer lock */
  78         dns_qid_t                       *qid;
  79         isc_mutex_t                     buffer_lock;
  80         unsigned int                    buffers;    /* allocated buffers */
  81         unsigned int                    buffersize; /* size of each buffer */
  82         unsigned int                    maxbuffers; /* max buffers */
  83
  84         /* Locked internally. */
  85         isc_mutex_t                     pool_lock;
  86         isc_mempool_t                  *epool;  /* memory pool for events */
  87         isc_mempool_t                  *rpool;  /* memory pool for replies */
  88         isc_mempool_t                  *dpool;  /* dispatch allocations */
  89         isc_mempool_t                  *bpool;  /* memory pool for buffers */
  90
  91         isc_entropy_t                  *entropy; /* entropy source */
  92 };
  93
  94 #define MGR_SHUTTINGDOWN                0x00000001U
  95 #define MGR_IS_SHUTTINGDOWN(l)  (((l)->state & MGR_SHUTTINGDOWN) != 0)
  96
  97 #define IS_PRIVATE(d)   (((d)->attributes & DNS_DISPATCHATTR_PRIVATE) != 0)
  98
  99 struct dns_dispentry {
 100         unsigned int                    magic;
 101         dns_dispatch_t                 *disp;
 102         dns_messageid_t                 id;
 103         unsigned int                    bucket;
 104         isc_sockaddr_t                  host;
 105         isc_task_t                     *task;
 106         isc_taskaction_t                action;
 107         void                           *arg;
 108         isc_boolean_t                   item_out;
 109         ISC_LIST(dns_dispatchevent_t)   items;
 110         ISC_LINK(dns_dispentry_t)       link;
 111 };
 112
 113 #define INVALID_BUCKET          (0xffffdead)
 114
 115 struct dns_dispatch {
 116         /* Unlocked. */
 117         unsigned int            magic;          /* magic */
 118         dns_dispatchmgr_t      *mgr;            /* dispatch manager */
 119         isc_task_t             *task;           /* internal task */
 120         isc_socket_t           *socket;         /* isc socket attached to */
 121         isc_sockaddr_t          local;          /* local address */
 122         unsigned int            maxrequests;    /* max requests */
 123         isc_event_t            *ctlevent;
 124
 125         /* Locked by mgr->lock. */
 126         ISC_LINK(dns_dispatch_t) link;
 127
 128         /* Locked by "lock". */
 129         isc_mutex_t             lock;           /* locks all below */
 130         isc_sockettype_t        socktype;
 131         unsigned int            attributes;
 132         unsigned int            refcount;       /* number of users */
 133         dns_dispatchevent_t    *failsafe_ev;    /* failsafe cancel event */
 134         unsigned int            shutting_down : 1,
 135                                 shutdown_out : 1,
 136                                 connected : 1,
 137                                 tcpmsg_valid : 1,
 138                                 recv_pending : 1; /* is a recv() pending? */
 139         isc_result_t            shutdown_why;
 140         unsigned int            requests;       /* how many requests we have */
 141         unsigned int            tcpbuffers;     /* allocated buffers */
 142         dns_tcpmsg_t            tcpmsg;         /* for tcp streams */
 143         dns_qid_t               *qid;
 144 };
 145
 146 #define QID_MAGIC               ISC_MAGIC('Q', 'i', 'd', ' ')
 147 #define VALID_QID(e)            ISC_MAGIC_VALID((e), QID_MAGIC)
 148
 149 #define RESPONSE_MAGIC          ISC_MAGIC('D', 'r', 's', 'p')
 150 #define VALID_RESPONSE(e)       ISC_MAGIC_VALID((e), RESPONSE_MAGIC)
 151
 152 #define DISPATCH_MAGIC          ISC_MAGIC('D', 'i', 's', 'p')
 153 #define VALID_DISPATCH(e)       ISC_MAGIC_VALID((e), DISPATCH_MAGIC)
 154
 155 #define DNS_DISPATCHMGR_MAGIC   ISC_MAGIC('D', 'M', 'g', 'r')
 156 #define VALID_DISPATCHMGR(e)    ISC_MAGIC_VALID((e), DNS_DISPATCHMGR_MAGIC)
 157
 158 #define DNS_QID(disp) ((disp)->socktype == isc_sockettype_tcp) ? \
 159                        (disp)->qid : (disp)->mgr->qid
 160 /*
 161  * Statics.
 162  */
 163 static dns_dispentry_t *bucket_search(dns_qid_t *, isc_sockaddr_t *,
 164                                       dns_messageid_t, unsigned int);
 165 static isc_boolean_t destroy_disp_ok(dns_dispatch_t *);
 166 static void destroy_disp(isc_task_t *task, isc_event_t *event);
 167 static void udp_recv(isc_task_t *, isc_event_t *);
 168 static void tcp_recv(isc_task_t *, isc_event_t *);
 169 static void startrecv(dns_dispatch_t *);
 170 static dns_messageid_t dns_randomid(dns_nsid_t *);
 171 static isc_uint32_t dns_hash(dns_qid_t *, isc_sockaddr_t *, dns_messageid_t);
 172 static void free_buffer(dns_dispatch_t *disp, void *buf, unsigned int len);
 173 static void *allocate_udp_buffer(dns_dispatch_t *disp);
 174 static inline void free_event(dns_dispatch_t *disp, dns_dispatchevent_t *ev);
 175 static inline dns_dispatchevent_t *allocate_event(dns_dispatch_t *disp);
 176 static void do_cancel(dns_dispatch_t *disp);
 177 static dns_dispentry_t *linear_first(dns_qid_t *disp);
 178 static dns_dispentry_t *linear_next(dns_qid_t *disp,
 179                                     dns_dispentry_t *resp);
 180 static void dispatch_free(dns_dispatch_t **dispp);
 181 static isc_result_t dispatch_createudp(dns_dispatchmgr_t *mgr,
 182                                        isc_socketmgr_t *sockmgr,
 183                                        isc_taskmgr_t *taskmgr,
 184                                        isc_sockaddr_t *localaddr,
 185                                        unsigned int maxrequests,
 186                                        unsigned int attributes,
 187                                        dns_dispatch_t **dispp);
 188 static isc_boolean_t destroy_mgr_ok(dns_dispatchmgr_t *mgr);
 189 static void destroy_mgr(dns_dispatchmgr_t **mgrp);
 190 static isc_result_t qid_allocate(dns_dispatchmgr_t *mgr, unsigned int buckets,
 191                                  unsigned int increment, isc_boolean_t usepool,
 192                                  dns_qid_t **qidp);
 193 static void qid_destroy(isc_mem_t *mctx, dns_qid_t **qidp);
 194 static isc_uint16_t nsid_next(dns_nsid_t *nsid);
 195 static isc_result_t nsid_init(isc_mem_t *mctx, dns_nsid_t *nsid, isc_boolean_t usepool);
 196 static void nsid_destroy(isc_mem_t *mctx, dns_nsid_t *nsid);
 197
 198 #define LVL(x) ISC_LOG_DEBUG(x)
 199
 200 static void
 201 mgr_log(dns_dispatchmgr_t *mgr, int level, const char *fmt, ...)
 202      ISC_FORMAT_PRINTF(3, 4);
 203
 204 static void
 205 mgr_log(dns_dispatchmgr_t *mgr, int level, const char *fmt, ...) {
 206         char msgbuf[2048];
 207         va_list ap;
 208
 209         if (! isc_log_wouldlog(dns_lctx, level))
 210                 return;
 211
 212         va_start(ap, fmt);
 213         vsnprintf(msgbuf, sizeof(msgbuf), fmt, ap);
 214         va_end(ap);
 215
 216         isc_log_write(dns_lctx,
 217                       DNS_LOGCATEGORY_DISPATCH, DNS_LOGMODULE_DISPATCH,
 218                       level, "dispatchmgr %p: %s", mgr, msgbuf);
 219 }
 220
 221 static void
 222 dispatch_log(dns_dispatch_t *disp, int level, const char *fmt, ...)
 223      ISC_FORMAT_PRINTF(3, 4);
 224
 225 static void
 226 dispatch_log(dns_dispatch_t *disp, int level, const char *fmt, ...) {
 227         char msgbuf[2048];
 228         va_list ap;
 229
 230         if (! isc_log_wouldlog(dns_lctx, level))
 231                 return;
 232
 233         va_start(ap, fmt);
 234         vsnprintf(msgbuf, sizeof(msgbuf), fmt, ap);
 235         va_end(ap);
 236
 237         isc_log_write(dns_lctx,
 238                       DNS_LOGCATEGORY_DISPATCH, DNS_LOGMODULE_DISPATCH,
 239                       level, "dispatch %p: %s", disp, msgbuf);
 240 }
 241
 242 static void
 243 request_log(dns_dispatch_t *disp, dns_dispentry_t *resp,
 244             int level, const char *fmt, ...)
 245      ISC_FORMAT_PRINTF(4, 5);
 246
 247 static void
 248 request_log(dns_dispatch_t *disp, dns_dispentry_t *resp,
 249             int level, const char *fmt, ...)
 250 {
 251         char msgbuf[2048];
 252         char peerbuf[256];
 253         va_list ap;
 254
 255         if (! isc_log_wouldlog(dns_lctx, level))
 256                 return;
 257
 258         va_start(ap, fmt);
 259         vsnprintf(msgbuf, sizeof(msgbuf), fmt, ap);
 260         va_end(ap);
 261
 262         if (VALID_RESPONSE(resp)) {
 263                 isc_sockaddr_format(&resp->host, peerbuf, sizeof(peerbuf));
 264                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DISPATCH,
 265                               DNS_LOGMODULE_DISPATCH, level,
 266                               "dispatch %p response %p %s: %s", disp, resp,
 267                               peerbuf, msgbuf);
 268         } else {
 269                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DISPATCH,
 270                               DNS_LOGMODULE_DISPATCH, level,
 271                               "dispatch %p req/resp %p: %s", disp, resp,
 272                               msgbuf);
 273         }
 274 }
 275
 276 /*
 277  * Return an unpredictable message ID.
 278  */
 279 static dns_messageid_t
 280 dns_randomid(dns_nsid_t *nsid) {
 281         isc_uint32_t id;
 282
 283         id = nsid_next(nsid);
 284
 285         return ((dns_messageid_t)id);
 286 }
 287
 288 /*
 289  * Return a hash of the destination and message id.
 290  */
 291 static isc_uint32_t
 292 dns_hash(dns_qid_t *qid, isc_sockaddr_t *dest, dns_messageid_t id) {
 293         unsigned int ret;
 294
 295         ret = isc_sockaddr_hash(dest, ISC_TRUE);
 296         ret ^= id;
 297         ret %= qid->qid_nbuckets;
 298
 299         INSIST(ret < qid->qid_nbuckets);
 300
 301         return (ret);
 302 }
 303
 304 /*
 305  * Find the first entry in 'qid'.  Returns NULL if there are no entries.
 306  */
 307 static dns_dispentry_t *
 308 linear_first(dns_qid_t *qid) {
 309         dns_dispentry_t *ret;
 310         unsigned int bucket;
 311
 312         bucket = 0;
 313
 314         while (bucket < qid->qid_nbuckets) {
 315                 ret = ISC_LIST_HEAD(qid->qid_table[bucket]);
 316                 if (ret != NULL)
 317                         return (ret);
 318                 bucket++;
 319         }
 320
 321         return (NULL);
 322 }
 323
 324 /*
 325  * Find the next entry after 'resp' in 'qid'.  Return NULL if there are
 326  * no more entries.
 327  */
 328 static dns_dispentry_t *
 329 linear_next(dns_qid_t *qid, dns_dispentry_t *resp) {
 330         dns_dispentry_t *ret;
 331         unsigned int bucket;
 332
 333         ret = ISC_LIST_NEXT(resp, link);
 334         if (ret != NULL)
 335                 return (ret);
 336
 337         bucket = resp->bucket;
 338         bucket++;
 339         while (bucket < qid->qid_nbuckets) {
 340                 ret = ISC_LIST_HEAD(qid->qid_table[bucket]);
 341                 if (ret != NULL)
 342                         return (ret);
 343                 bucket++;
 344         }
 345
 346         return (NULL);
 347 }
 348
 349 /*
 350  * The dispatch must be locked.
 351  */
 352 static isc_boolean_t
 353 destroy_disp_ok(dns_dispatch_t *disp)
 354 {
 355         if (disp->refcount != 0)
 356                 return (ISC_FALSE);
 357
 358         if (disp->recv_pending != 0)
 359                 return (ISC_FALSE);
 360
 361         if (disp->shutting_down == 0)
 362                 return (ISC_FALSE);
 363
 364         return (ISC_TRUE);
 365 }
 366
 367
 368 /*
 369  * Called when refcount reaches 0 (and safe to destroy).
 370  *
 371  * The dispatcher must not be locked.
 372  * The manager must be locked.
 373  */
 374 static void
 375 destroy_disp(isc_task_t *task, isc_event_t *event) {
 376         dns_dispatch_t *disp;
 377         dns_dispatchmgr_t *mgr;
 378         isc_boolean_t killmgr;
 379
 380         INSIST(event->ev_type == DNS_EVENT_DISPATCHCONTROL);
 381
 382         UNUSED(task);
 383
 384         disp = event->ev_arg;
 385         mgr = disp->mgr;
 386
 387         LOCK(&mgr->lock);
 388         ISC_LIST_UNLINK(mgr->list, disp, link);
 389
 390         dispatch_log(disp, LVL(90),
 391                      "shutting down; detaching from sock %p, task %p",
 392                      disp->socket, disp->task);
 393
 394         isc_socket_detach(&disp->socket);
 395         isc_task_detach(&disp->task);
 396         isc_event_free(&event);
 397
 398         dispatch_free(&disp);
 399
 400         killmgr = destroy_mgr_ok(mgr);
 401         UNLOCK(&mgr->lock);
 402         if (killmgr)
 403                 destroy_mgr(&mgr);
 404 }
 405
 406
 407 /*
 408  * Find an entry for query ID 'id' and socket address 'dest' in 'qid'.
 409  * Return NULL if no such entry exists.
 410  */
 411 static dns_dispentry_t *
 412 bucket_search(dns_qid_t *qid, isc_sockaddr_t *dest, dns_messageid_t id,
 413               unsigned int bucket)
 414 {
 415         dns_dispentry_t *res;
 416
 417         REQUIRE(bucket < qid->qid_nbuckets);
 418
 419         res = ISC_LIST_HEAD(qid->qid_table[bucket]);
 420
 421         while (res != NULL) {
 422                 if ((res->id == id) && isc_sockaddr_equal(dest, &res->host))
 423                         return (res);
 424                 res = ISC_LIST_NEXT(res, link);
 425         }
 426
 427         return (NULL);
 428 }
 429
 430 static void
 431 free_buffer(dns_dispatch_t *disp, void *buf, unsigned int len) {
 432         INSIST(buf != NULL && len != 0);
 433
 434
 435         switch (disp->socktype) {
 436         case isc_sockettype_tcp:
 437                 INSIST(disp->tcpbuffers > 0);
 438                 disp->tcpbuffers--;
 439                 isc_mem_put(disp->mgr->mctx, buf, len);
 440                 break;
 441         case isc_sockettype_udp:
 442                 LOCK(&disp->mgr->buffer_lock);
 443                 INSIST(disp->mgr->buffers > 0);
 444                 INSIST(len == disp->mgr->buffersize);
 445                 disp->mgr->buffers--;
 446                 isc_mempool_put(disp->mgr->bpool, buf);
 447                 UNLOCK(&disp->mgr->buffer_lock);
 448                 break;
 449         default:
 450                 INSIST(0);
 451                 break;
 452         }
 453 }
 454
 455 static void *
 456 allocate_udp_buffer(dns_dispatch_t *disp) {
 457         void *temp;
 458
 459         LOCK(&disp->mgr->buffer_lock);
 460         temp = isc_mempool_get(disp->mgr->bpool);
 461
 462         if (temp != NULL)
 463                 disp->mgr->buffers++;
 464         UNLOCK(&disp->mgr->buffer_lock);
 465
 466         return (temp);
 467 }
 468
 469 static inline void
 470 free_event(dns_dispatch_t *disp, dns_dispatchevent_t *ev) {
 471         if (disp->failsafe_ev == ev) {
 472                 INSIST(disp->shutdown_out == 1);
 473                 disp->shutdown_out = 0;
 474
 475                 return;
 476         }
 477
 478         isc_mempool_put(disp->mgr->epool, ev);
 479 }
 480
 481 static inline dns_dispatchevent_t *
 482 allocate_event(dns_dispatch_t *disp) {
 483         dns_dispatchevent_t *ev;
 484
 485         ev = isc_mempool_get(disp->mgr->epool);
 486         if (ev == NULL)
 487                 return (NULL);
 488         ISC_EVENT_INIT(ev, sizeof(*ev), 0, NULL, 0,
 489                        NULL, NULL, NULL, NULL, NULL);
 490
 491         return (ev);
 492 }
 493
 494 /*
 495  * General flow:
 496  *
 497  * If I/O result == CANCELED or error, free the buffer.
 498  *
 499  * If query, free the buffer, restart.
 500  *
 501  * If response:
 502  *      Allocate event, fill in details.
 503  *              If cannot allocate, free buffer, restart.
 504  *      find target.  If not found, free buffer, restart.
 505  *      if event queue is not empty, queue.  else, send.
 506  *      restart.
 507  */
 508 static void
 509 udp_recv(isc_task_t *task, isc_event_t *ev_in) {
 510         isc_socketevent_t *ev = (isc_socketevent_t *)ev_in;
 511         dns_dispatch_t *disp = ev_in->ev_arg;
 512         dns_messageid_t id;
 513         isc_result_t dres;
 514         isc_buffer_t source;
 515         unsigned int flags;
 516         dns_dispentry_t *resp;
 517         dns_dispatchevent_t *rev;
 518         unsigned int bucket;
 519         isc_boolean_t killit;
 520         isc_boolean_t queue_response;
 521         dns_dispatchmgr_t *mgr;
 522         dns_qid_t *qid;
 523         isc_netaddr_t netaddr;
 524         int match;
 525
 526         UNUSED(task);
 527
 528         LOCK(&disp->lock);
 529
 530         mgr = disp->mgr;
 531         qid = mgr->qid;
 532
 533         dispatch_log(disp, LVL(90),
 534                      "got packet: requests %d, buffers %d, recvs %d",
 535                      disp->requests, disp->mgr->buffers, disp->recv_pending);
 536
 537         if (ev->ev_type == ISC_SOCKEVENT_RECVDONE) {
 538                 /*
 539                  * Unless the receive event was imported from a listening
 540                  * interface, in which case the event type is
 541                  * DNS_EVENT_IMPORTRECVDONE, receive operation must be pending.
 542                  */
 543                 INSIST(disp->recv_pending != 0);
 544                 disp->recv_pending = 0;
 545         }
 546
 547         if (disp->shutting_down) {
 548                 /*
 549                  * This dispatcher is shutting down.
 550                  */
 551                 free_buffer(disp, ev->region.base, ev->region.length);
 552
 553                 isc_event_free(&ev_in);
 554                 ev = NULL;
 555
 556                 killit = destroy_disp_ok(disp);
 557                 UNLOCK(&disp->lock);
 558                 if (killit)
 559                         isc_task_send(disp->task, &disp->ctlevent);
 560
 561                 return;
 562         }
 563
 564         if (ev->result != ISC_R_SUCCESS) {
 565                 free_buffer(disp, ev->region.base, ev->region.length);
 566
 567                 if (ev->result != ISC_R_CANCELED)
 568                         dispatch_log(disp, ISC_LOG_ERROR,
 569                                      "odd socket result in udp_recv(): %s",
 570                                      isc_result_totext(ev->result));
 571
 572                 UNLOCK(&disp->lock);
 573                 isc_event_free(&ev_in);
 574                 return;
 575         }
 576
 577         /*
 578          * If this is from a blackholed address, drop it.
 579          */
 580         isc_netaddr_fromsockaddr(&netaddr, &ev->address);
 581         if (disp->mgr->blackhole != NULL &&
 582             dns_acl_match(&netaddr, NULL, disp->mgr->blackhole,
 583                           NULL, &match, NULL) == ISC_R_SUCCESS &&
 584             match > 0)
 585         {
 586                 if (isc_log_wouldlog(dns_lctx, LVL(10))) {
 587                         char netaddrstr[ISC_NETADDR_FORMATSIZE];
 588                         isc_netaddr_format(&netaddr, netaddrstr,
 589                                            sizeof(netaddrstr));
 590                         dispatch_log(disp, LVL(10),
 591                                      "blackholed packet from %s",
 592                                      netaddrstr);
 593                 }
 594                 free_buffer(disp, ev->region.base, ev->region.length);
 595                 goto restart;
 596         }
 597
 598         /*
 599          * Peek into the buffer to see what we can see.
 600          */
 601         isc_buffer_init(&source, ev->region.base, ev->region.length);
 602         isc_buffer_add(&source, ev->n);
 603         dres = dns_message_peekheader(&source, &id, &flags);
 604         if (dres != ISC_R_SUCCESS) {
 605                 free_buffer(disp, ev->region.base, ev->region.length);
 606                 dispatch_log(disp, LVL(10), "got garbage packet");
 607                 goto restart;
 608         }
 609
 610         dispatch_log(disp, LVL(92),
 611                      "got valid DNS message header, /QR %c, id %u",
 612                      ((flags & DNS_MESSAGEFLAG_QR) ? '1' : '0'), id);
 613
 614         /*
 615          * Look at flags.  If query, drop it. If response,
 616          * look to see where it goes.
 617          */
 618         queue_response = ISC_FALSE;
 619         if ((flags & DNS_MESSAGEFLAG_QR) == 0) {
 620                 /* query */
 621                 free_buffer(disp, ev->region.base, ev->region.length);
 622                 goto restart;
 623         }
 624
 625         dns_dispatch_hash(&ev->timestamp, sizeof(&ev->timestamp));
 626         dns_dispatch_hash(ev->region.base, ev->region.length);
 627
 628         /* response */
 629         bucket = dns_hash(qid, &ev->address, id);
 630         LOCK(&qid->lock);
 631         resp = bucket_search(qid, &ev->address, id, bucket);
 632         dispatch_log(disp, LVL(90),
 633                      "search for response in bucket %d: %s",
 634                      bucket, (resp == NULL ? "not found" : "found"));
 635
 636         if (resp == NULL) {
 637                 free_buffer(disp, ev->region.base, ev->region.length);
 638                 goto unlock;
 639         }
 640
 641         /*
 642          * Now that we have the original dispatch the query was sent
 643          * from check that the address and port the response was
 644          * sent to make sense.
 645          */
 646         if (disp != resp->disp) {
 647                 isc_sockaddr_t a1;
 648                 isc_sockaddr_t a2;
 649
 650                 /*
 651                  * Check that the socket types and ports match.
 652                  */
 653                 if (disp->socktype != resp->disp->socktype ||
 654                     isc_sockaddr_getport(&disp->local) !=
 655                     isc_sockaddr_getport(&resp->disp->local)) {
 656                         free_buffer(disp, ev->region.base, ev->region.length);
 657                         goto unlock;
 658                 }
 659
 660                 /*
 661                  * If both dispatches are bound to an address then fail as
 662                  * the addresses can't be equal (enforced by the IP stack).
 663                  *
 664                  * Note under Linux a packet can be sent out via IPv4 socket
 665                  * and the response be received via a IPv6 socket.
 666                  *
 667                  * Requests sent out via IPv6 should always come back in
 668                  * via IPv6.
 669                  */
 670                 if (isc_sockaddr_pf(&resp->disp->local) == PF_INET6 &&
 671                     isc_sockaddr_pf(&disp->local) != PF_INET6) {
 672                         free_buffer(disp, ev->region.base, ev->region.length);
 673                         goto unlock;
 674                 }
 675                 isc_sockaddr_anyofpf(&a1, isc_sockaddr_pf(&resp->disp->local));
 676                 isc_sockaddr_anyofpf(&a2, isc_sockaddr_pf(&disp->local));
 677                 if (!isc_sockaddr_eqaddr(&a1, &resp->disp->local) &&
 678                     !isc_sockaddr_eqaddr(&a2, &disp->local)) {
 679                         free_buffer(disp, ev->region.base, ev->region.length);
 680                         goto unlock;
 681                 }
 682         }
 683
 684         queue_response = resp->item_out;
 685         rev = allocate_event(resp->disp);
 686         if (rev == NULL) {
 687                 free_buffer(disp, ev->region.base, ev->region.length);
 688                 goto unlock;
 689         }
 690
 691         /*
 692          * At this point, rev contains the event we want to fill in, and
 693          * resp contains the information on the place to send it to.
 694          * Send the event off.
 695          */
 696         isc_buffer_init(&rev->buffer, ev->region.base, ev->region.length);
 697         isc_buffer_add(&rev->buffer, ev->n);
 698         rev->result = ISC_R_SUCCESS;
 699         rev->id = id;
 700         rev->addr = ev->address;
 701         rev->pktinfo = ev->pktinfo;
 702         rev->attributes = ev->attributes;
 703         if (queue_response) {
 704                 ISC_LIST_APPEND(resp->items, rev, ev_link);
 705         } else {
 706                 ISC_EVENT_INIT(rev, sizeof(*rev), 0, NULL,
 707                                DNS_EVENT_DISPATCH,
 708                                resp->action, resp->arg, resp, NULL, NULL);
 709                 request_log(disp, resp, LVL(90),
 710                             "[a] Sent event %p buffer %p len %d to task %p",
 711                             rev, rev->buffer.base, rev->buffer.length,
 712                             resp->task);
 713                 resp->item_out = ISC_TRUE;
 714                 isc_task_send(resp->task, ISC_EVENT_PTR(&rev));
 715         }
 716  unlock:
 717         UNLOCK(&qid->lock);
 718
 719         /*
 720          * Restart recv() to get the next packet.
 721          */
 722  restart:
 723         startrecv(disp);
 724
 725         UNLOCK(&disp->lock);
 726
 727         isc_event_free(&ev_in);
 728 }
 729
 730 /*
 731  * General flow:
 732  *
 733  * If I/O result == CANCELED, EOF, or error, notify everyone as the
 734  * various queues drain.
 735  *
 736  * If query, restart.
 737  *
 738  * If response:
 739  *      Allocate event, fill in details.
 740  *              If cannot allocate, restart.
 741  *      find target.  If not found, restart.
 742  *      if event queue is not empty, queue.  else, send.
 743  *      restart.
 744  */
 745 static void
 746 tcp_recv(isc_task_t *task, isc_event_t *ev_in) {
 747         dns_dispatch_t *disp = ev_in->ev_arg;
 748         dns_tcpmsg_t *tcpmsg = &disp->tcpmsg;
 749         dns_messageid_t id;
 750         isc_result_t dres;
 751         unsigned int flags;
 752         dns_dispentry_t *resp;
 753         dns_dispatchevent_t *rev;
 754         unsigned int bucket;
 755         isc_boolean_t killit;
 756         isc_boolean_t queue_response;
 757         dns_qid_t *qid;
 758         int level;
 759         char buf[ISC_SOCKADDR_FORMATSIZE];
 760
 761         UNUSED(task);
 762
 763         REQUIRE(VALID_DISPATCH(disp));
 764
 765         qid = disp->qid;
 766
 767         dispatch_log(disp, LVL(90),
 768                      "got TCP packet: requests %d, buffers %d, recvs %d",
 769                      disp->requests, disp->tcpbuffers, disp->recv_pending);
 770
 771         LOCK(&disp->lock);
 772
 773         INSIST(disp->recv_pending != 0);
 774         disp->recv_pending = 0;
 775
 776         if (disp->refcount == 0) {
 777                 /*
 778                  * This dispatcher is shutting down.  Force cancelation.
 779                  */
 780                 tcpmsg->result = ISC_R_CANCELED;
 781         }
 782
 783         if (tcpmsg->result != ISC_R_SUCCESS) {
 784                 switch (tcpmsg->result) {
 785                 case ISC_R_CANCELED:
 786                         break;
 787
 788                 case ISC_R_EOF:
 789                         dispatch_log(disp, LVL(90), "shutting down on EOF");
 790                         do_cancel(disp);
 791                         break;
 792
 793                 case ISC_R_CONNECTIONRESET:
 794                         level = ISC_LOG_INFO;
 795                         goto logit;
 796
 797                 default:
 798                         level = ISC_LOG_ERROR;
 799                 logit:
 800                         isc_sockaddr_format(&tcpmsg->address, buf, sizeof(buf));
 801                         dispatch_log(disp, level, "shutting down due to TCP "
 802                                      "receive error: %s: %s", buf,
 803                                      isc_result_totext(tcpmsg->result));
 804                         do_cancel(disp);
 805                         break;
 806                 }
 807
 808                 /*
 809                  * The event is statically allocated in the tcpmsg
 810                  * structure, and destroy_disp() frees the tcpmsg, so we must
 811                  * free the event *before* calling destroy_disp().
 812                  */
 813                 isc_event_free(&ev_in);
 814
 815                 disp->shutting_down = 1;
 816                 disp->shutdown_why = tcpmsg->result;
 817
 818                 /*
 819                  * If the recv() was canceled pass the word on.
 820                  */
 821                 killit = destroy_disp_ok(disp);
 822                 UNLOCK(&disp->lock);
 823                 if (killit)
 824                         isc_task_send(disp->task, &disp->ctlevent);
 825                 return;
 826         }
 827
 828         dispatch_log(disp, LVL(90), "result %d, length == %d, addr = %p",
 829                      tcpmsg->result,
 830                      tcpmsg->buffer.length, tcpmsg->buffer.base);
 831
 832         /*
 833          * Peek into the buffer to see what we can see.
 834          */
 835         dres = dns_message_peekheader(&tcpmsg->buffer, &id, &flags);
 836         if (dres != ISC_R_SUCCESS) {
 837                 dispatch_log(disp, LVL(10), "got garbage packet");
 838                 goto restart;
 839         }
 840
 841         dispatch_log(disp, LVL(92),
 842                      "got valid DNS message header, /QR %c, id %u",
 843                      ((flags & DNS_MESSAGEFLAG_QR) ? '1' : '0'), id);
 844
 845         /*
 846          * Allocate an event to send to the query or response client, and
 847          * allocate a new buffer for our use.
 848          */
 849
 850         /*
 851          * Look at flags.  If query, drop it. If response,
 852          * look to see where it goes.
 853          */
 854         queue_response = ISC_FALSE;
 855         if ((flags & DNS_MESSAGEFLAG_QR) == 0) {
 856                 /*
 857                  * Query.
 858                  */
 859                 goto restart;
 860         }
 861
 862         dns_dispatch_hash(tcpmsg->buffer.base, tcpmsg->buffer.length);
 863
 864         /*
 865          * Response.
 866          */
 867         bucket = dns_hash(qid, &tcpmsg->address, id);
 868         LOCK(&qid->lock);
 869         resp = bucket_search(qid, &tcpmsg->address, id, bucket);
 870         dispatch_log(disp, LVL(90),
 871                      "search for response in bucket %d: %s",
 872                      bucket, (resp == NULL ? "not found" : "found"));
 873
 874         if (resp == NULL)
 875                 goto unlock;
 876         queue_response = resp->item_out;
 877         rev = allocate_event(disp);
 878         if (rev == NULL)
 879                 goto unlock;
 880
 881         /*
 882          * At this point, rev contains the event we want to fill in, and
 883          * resp contains the information on the place to send it to.
 884          * Send the event off.
 885          */
 886         dns_tcpmsg_keepbuffer(tcpmsg, &rev->buffer);
 887         disp->tcpbuffers++;
 888         rev->result = ISC_R_SUCCESS;
 889         rev->id = id;
 890         rev->addr = tcpmsg->address;
 891         if (queue_response) {
 892                 ISC_LIST_APPEND(resp->items, rev, ev_link);
 893         } else {
 894                 ISC_EVENT_INIT(rev, sizeof(*rev), 0, NULL, DNS_EVENT_DISPATCH,
 895                                resp->action, resp->arg, resp, NULL, NULL);
 896                 request_log(disp, resp, LVL(90),
 897                             "[b] Sent event %p buffer %p len %d to task %p",
 898                             rev, rev->buffer.base, rev->buffer.length,
 899                             resp->task);
 900                 resp->item_out = ISC_TRUE;
 901                 isc_task_send(resp->task, ISC_EVENT_PTR(&rev));
 902         }
 903  unlock:
 904         UNLOCK(&qid->lock);
 905
 906         /*
 907          * Restart recv() to get the next packet.
 908          */
 909  restart:
 910         startrecv(disp);
 911
 912         UNLOCK(&disp->lock);
 913
 914         isc_event_free(&ev_in);
 915 }
 916
 917 /*
 918  * disp must be locked.
 919  */
 920 static void
 921 startrecv(dns_dispatch_t *disp) {
 922         isc_result_t res;
 923         isc_region_t region;
 924
 925         if (disp->shutting_down == 1)
 926                 return;
 927
 928         if ((disp->attributes & DNS_DISPATCHATTR_NOLISTEN) != 0)
 929                 return;
 930
 931         if (disp->recv_pending != 0)
 932                 return;
 933
 934         if (disp->mgr->buffers >= disp->mgr->maxbuffers)
 935                 return;
 936
 937         switch (disp->socktype) {
 938                 /*
 939                  * UDP reads are always maximal.
 940                  */
 941         case isc_sockettype_udp:
 942                 region.length = disp->mgr->buffersize;
 943                 region.base = allocate_udp_buffer(disp);
 944                 if (region.base == NULL)
 945                         return;
 946                 res = isc_socket_recv(disp->socket, &region, 1,
 947                                       disp->task, udp_recv, disp);
 948                 if (res != ISC_R_SUCCESS) {
 949                         free_buffer(disp, region.base, region.length);
 950                         disp->shutdown_why = res;
 951                         disp->shutting_down = 1;
 952                         do_cancel(disp);
 953                         return;
 954                 }
 955                 INSIST(disp->recv_pending == 0);
 956                 disp->recv_pending = 1;
 957                 break;
 958
 959         case isc_sockettype_tcp:
 960                 res = dns_tcpmsg_readmessage(&disp->tcpmsg, disp->task,
 961                                              tcp_recv, disp);
 962                 if (res != ISC_R_SUCCESS) {
 963                         disp->shutdown_why = res;
 964                         disp->shutting_down = 1;
 965                         do_cancel(disp);
 966                         return;
 967                 }
 968                 INSIST(disp->recv_pending == 0);
 969                 disp->recv_pending = 1;
 970                 break;
 971         }
 972 }
 973
 974 /*
 975  * Mgr must be locked when calling this function.
 976  */
 977 static isc_boolean_t
 978 destroy_mgr_ok(dns_dispatchmgr_t *mgr) {
 979         mgr_log(mgr, LVL(90),
 980                 "destroy_mgr_ok: shuttingdown=%d, listnonempty=%d, "
 981                 "epool=%d, rpool=%d, dpool=%d",
 982                 MGR_IS_SHUTTINGDOWN(mgr), !ISC_LIST_EMPTY(mgr->list),
 983                 isc_mempool_getallocated(mgr->epool),
 984                 isc_mempool_getallocated(mgr->rpool),
 985                 isc_mempool_getallocated(mgr->dpool));
 986         if (!MGR_IS_SHUTTINGDOWN(mgr))
 987                 return (ISC_FALSE);
 988         if (!ISC_LIST_EMPTY(mgr->list))
 989                 return (ISC_FALSE);
 990         if (isc_mempool_getallocated(mgr->epool) != 0)
 991                 return (ISC_FALSE);
 992         if (isc_mempool_getallocated(mgr->rpool) != 0)
 993                 return (ISC_FALSE);
 994         if (isc_mempool_getallocated(mgr->dpool) != 0)
 995                 return (ISC_FALSE);
 996
 997         return (ISC_TRUE);
 998 }
 999
1000 /*
1001  * Mgr must be unlocked when calling this function.
1002  */
1003 static void
1004 destroy_mgr(dns_dispatchmgr_t **mgrp) {
1005         isc_mem_t *mctx;
1006         dns_dispatchmgr_t *mgr;
1007
1008         mgr = *mgrp;
1009         *mgrp = NULL;
1010
1011         mctx = mgr->mctx;
1012
1013         mgr->magic = 0;
1014         mgr->mctx = NULL;
1015         DESTROYLOCK(&mgr->lock);
1016         mgr->state = 0;
1017
1018         isc_mempool_destroy(&mgr->epool);
1019         isc_mempool_destroy(&mgr->rpool);
1020         isc_mempool_destroy(&mgr->dpool);
1021         isc_mempool_destroy(&mgr->bpool);
1022
1023         DESTROYLOCK(&mgr->pool_lock);
1024
1025         if (mgr->entropy != NULL)
1026                 isc_entropy_detach(&mgr->entropy);
1027         if (mgr->qid != NULL)
1028                 qid_destroy(mctx, &mgr->qid);
1029
1030         DESTROYLOCK(&mgr->buffer_lock);
1031
1032         if (mgr->blackhole != NULL)
1033                 dns_acl_detach(&mgr->blackhole);
1034
1035         if (mgr->portlist != NULL)
1036                 dns_portlist_detach(&mgr->portlist);
1037
1038         isc_mem_put(mctx, mgr, sizeof(dns_dispatchmgr_t));
1039         isc_mem_detach(&mctx);
1040 }
1041
1042 static isc_result_t
1043 create_socket(isc_socketmgr_t *mgr, isc_sockaddr_t *local,
1044               isc_socket_t **sockp)
1045 {
1046         isc_socket_t *sock;
1047         isc_result_t result;
1048
1049         sock = NULL;
1050         result = isc_socket_create(mgr, isc_sockaddr_pf(local),
1051                                    isc_sockettype_udp, &sock);
1052         if (result != ISC_R_SUCCESS)
1053                 return (result);
1054
1055 #ifndef ISC_ALLOW_MAPPED
1056         isc_socket_ipv6only(sock, ISC_TRUE);
1057 #endif
1058         result = isc_socket_bind(sock, local);
1059         if (result != ISC_R_SUCCESS) {
1060                 isc_socket_detach(&sock);
1061                 return (result);
1062         }
1063
1064         *sockp = sock;
1065         return (ISC_R_SUCCESS);
1066 }
1067
1068 /*
1069  * Publics.
1070  */
1071
1072 isc_result_t
1073 dns_dispatchmgr_create(isc_mem_t *mctx, isc_entropy_t *entropy,
1074                        dns_dispatchmgr_t **mgrp)
1075 {
1076         dns_dispatchmgr_t *mgr;
1077         isc_result_t result;
1078
1079         REQUIRE(mctx != NULL);
1080         REQUIRE(mgrp != NULL && *mgrp == NULL);
1081
1082         mgr = isc_mem_get(mctx, sizeof(dns_dispatchmgr_t));
1083         if (mgr == NULL)
1084                 return (ISC_R_NOMEMORY);
1085
1086         mgr->mctx = NULL;
1087         isc_mem_attach(mctx, &mgr->mctx);
1088
1089         mgr->blackhole = NULL;
1090         mgr->portlist = NULL;
1091
1092         result = isc_mutex_init(&mgr->lock);
1093         if (result != ISC_R_SUCCESS)
1094                 goto deallocate;
1095
1096         result = isc_mutex_init(&mgr->buffer_lock);
1097         if (result != ISC_R_SUCCESS)
1098                 goto kill_lock;
1099
1100         result = isc_mutex_init(&mgr->pool_lock);
1101         if (result != ISC_R_SUCCESS)
1102                 goto kill_buffer_lock;
1103
1104         mgr->epool = NULL;
1105         if (isc_mempool_create(mgr->mctx, sizeof(dns_dispatchevent_t),
1106                                &mgr->epool) != ISC_R_SUCCESS) {
1107                 result = ISC_R_NOMEMORY;
1108                 goto kill_pool_lock;
1109         }
1110
1111         mgr->rpool = NULL;
1112         if (isc_mempool_create(mgr->mctx, sizeof(dns_dispentry_t),
1113                                &mgr->rpool) != ISC_R_SUCCESS) {
1114                 result = ISC_R_NOMEMORY;
1115                 goto kill_epool;
1116         }
1117
1118         mgr->dpool = NULL;
1119         if (isc_mempool_create(mgr->mctx, sizeof(dns_dispatch_t),
1120                                &mgr->dpool) != ISC_R_SUCCESS) {
1121                 result = ISC_R_NOMEMORY;
1122                 goto kill_rpool;
1123         }
1124
1125         isc_mempool_setname(mgr->epool, "dispmgr_epool");
1126         isc_mempool_setfreemax(mgr->epool, 1024);
1127         isc_mempool_associatelock(mgr->epool, &mgr->pool_lock);
1128
1129         isc_mempool_setname(mgr->rpool, "dispmgr_rpool");
1130         isc_mempool_setfreemax(mgr->rpool, 1024);
1131         isc_mempool_associatelock(mgr->rpool, &mgr->pool_lock);
1132
1133         isc_mempool_setname(mgr->dpool, "dispmgr_dpool");
1134         isc_mempool_setfreemax(mgr->dpool, 1024);
1135         isc_mempool_associatelock(mgr->dpool, &mgr->pool_lock);
1136
1137         mgr->buffers = 0;
1138         mgr->buffersize = 0;
1139         mgr->maxbuffers = 0;
1140         mgr->bpool = NULL;
1141         mgr->entropy = NULL;
1142         mgr->qid = NULL;
1143         mgr->state = 0;
1144         ISC_LIST_INIT(mgr->list);
1145         mgr->magic = DNS_DISPATCHMGR_MAGIC;
1146
1147         if (entropy != NULL)
1148                 isc_entropy_attach(entropy, &mgr->entropy);
1149
1150         *mgrp = mgr;
1151         return (ISC_R_SUCCESS);
1152
1153  kill_rpool:
1154         isc_mempool_destroy(&mgr->rpool);
1155  kill_epool:
1156         isc_mempool_destroy(&mgr->epool);
1157  kill_pool_lock:
1158         DESTROYLOCK(&mgr->pool_lock);
1159  kill_buffer_lock:
1160         DESTROYLOCK(&mgr->buffer_lock);
1161  kill_lock:
1162         DESTROYLOCK(&mgr->lock);
1163  deallocate:
1164         isc_mem_put(mctx, mgr, sizeof(dns_dispatchmgr_t));
1165         isc_mem_detach(&mctx);
1166
1167         return (result);
1168 }
1169
1170 void
1171 dns_dispatchmgr_setblackhole(dns_dispatchmgr_t *mgr, dns_acl_t *blackhole) {
1172         REQUIRE(VALID_DISPATCHMGR(mgr));
1173         if (mgr->blackhole != NULL)
1174                 dns_acl_detach(&mgr->blackhole);
1175         dns_acl_attach(blackhole, &mgr->blackhole);
1176 }
1177
1178 dns_acl_t *
1179 dns_dispatchmgr_getblackhole(dns_dispatchmgr_t *mgr) {
1180         REQUIRE(VALID_DISPATCHMGR(mgr));
1181         return (mgr->blackhole);
1182 }
1183
1184 void
1185 dns_dispatchmgr_setblackportlist(dns_dispatchmgr_t *mgr,
1186                                  dns_portlist_t *portlist)
1187 {
1188         REQUIRE(VALID_DISPATCHMGR(mgr));
1189         if (mgr->portlist != NULL)
1190                 dns_portlist_detach(&mgr->portlist);
1191         if (portlist != NULL)
1192                 dns_portlist_attach(portlist, &mgr->portlist);
1193 }
1194
1195 dns_portlist_t *
1196 dns_dispatchmgr_getblackportlist(dns_dispatchmgr_t *mgr) {
1197         REQUIRE(VALID_DISPATCHMGR(mgr));
1198         return (mgr->portlist);
1199 }
1200
1201 static isc_result_t
1202 dns_dispatchmgr_setudp(dns_dispatchmgr_t *mgr,
1203                         unsigned int buffersize, unsigned int maxbuffers,
1204                         unsigned int buckets, unsigned int increment)
1205 {
1206         isc_result_t result;
1207
1208         REQUIRE(VALID_DISPATCHMGR(mgr));
1209         REQUIRE(buffersize >= 512 && buffersize < (64 * 1024));
1210         REQUIRE(maxbuffers > 0);
1211         REQUIRE(buckets < 2097169);  /* next prime > 65536 * 32 */
1212         REQUIRE(increment > buckets);
1213
1214         /*
1215          * Keep some number of items around.  This should be a config
1216          * option.  For now, keep 8, but later keep at least two even
1217          * if the caller wants less.  This allows us to ensure certain
1218          * things, like an event can be "freed" and the next allocation
1219          * will always succeed.
1220          *
1221          * Note that if limits are placed on anything here, we use one
1222          * event internally, so the actual limit should be "wanted + 1."
1223          *
1224          * XXXMLG
1225          */
1226
1227         if (maxbuffers < 8)
1228                 maxbuffers = 8;
1229
1230         LOCK(&mgr->buffer_lock);
1231         if (mgr->bpool != NULL) {
1232                 isc_mempool_setmaxalloc(mgr->bpool, maxbuffers);
1233                 mgr->maxbuffers = maxbuffers;
1234                 UNLOCK(&mgr->buffer_lock);
1235                 return (ISC_R_SUCCESS);
1236         }
1237
1238         if (isc_mempool_create(mgr->mctx, buffersize,
1239                                &mgr->bpool) != ISC_R_SUCCESS) {
1240                 return (ISC_R_NOMEMORY);
1241         }
1242
1243         isc_mempool_setname(mgr->bpool, "dispmgr_bpool");
1244         isc_mempool_setmaxalloc(mgr->bpool, maxbuffers);
1245         isc_mempool_associatelock(mgr->bpool, &mgr->pool_lock);
1246
1247         result = qid_allocate(mgr, buckets, increment, ISC_TRUE, &mgr->qid);
1248         if (result != ISC_R_SUCCESS)
1249                 goto cleanup;
1250
1251         mgr->buffersize = buffersize;
1252         mgr->maxbuffers = maxbuffers;
1253         UNLOCK(&mgr->buffer_lock);
1254         return (ISC_R_SUCCESS);
1255
1256  cleanup:
1257         isc_mempool_destroy(&mgr->bpool);
1258         UNLOCK(&mgr->buffer_lock);
1259         return (ISC_R_NOMEMORY);
1260 }
1261
1262 void
1263 dns_dispatchmgr_destroy(dns_dispatchmgr_t **mgrp) {
1264         dns_dispatchmgr_t *mgr;
1265         isc_boolean_t killit;
1266
1267         REQUIRE(mgrp != NULL);
1268         REQUIRE(VALID_DISPATCHMGR(*mgrp));
1269
1270         mgr = *mgrp;
1271         *mgrp = NULL;
1272
1273         LOCK(&mgr->lock);
1274         mgr->state |= MGR_SHUTTINGDOWN;
1275
1276         killit = destroy_mgr_ok(mgr);
1277         UNLOCK(&mgr->lock);
1278
1279         mgr_log(mgr, LVL(90), "destroy: killit=%d", killit);
1280
1281         if (killit)
1282                 destroy_mgr(&mgr);
1283 }
1284
1285 static isc_boolean_t
1286 blacklisted(dns_dispatchmgr_t *mgr, isc_socket_t *sock) {
1287         isc_sockaddr_t sockaddr;
1288         isc_result_t result;
1289
1290         if (mgr->portlist == NULL)
1291                 return (ISC_FALSE);
1292
1293         result = isc_socket_getsockname(sock, &sockaddr);
1294         if (result != ISC_R_SUCCESS)
1295                 return (ISC_FALSE);
1296
1297         if (mgr->portlist != NULL &&
1298             dns_portlist_match(mgr->portlist, isc_sockaddr_pf(&sockaddr),
1299                                isc_sockaddr_getport(&sockaddr)))
1300                 return (ISC_TRUE);
1301         return (ISC_FALSE);
1302 }
1303
1304 #define ATTRMATCH(_a1, _a2, _mask) (((_a1) & (_mask)) == ((_a2) & (_mask)))
1305
1306 static isc_boolean_t
1307 local_addr_match(dns_dispatch_t *disp, isc_sockaddr_t *addr) {
1308         isc_sockaddr_t sockaddr;
1309         isc_result_t result;
1310
1311         if (addr == NULL)
1312                 return (ISC_TRUE);
1313
1314         /*
1315          * Don't match wildcard ports against newly blacklisted ports.
1316          */
1317         if (disp->mgr->portlist != NULL &&
1318             isc_sockaddr_getport(addr) == 0 &&
1319             isc_sockaddr_getport(&disp->local) == 0 &&
1320             blacklisted(disp->mgr, disp->socket))
1321                 return (ISC_FALSE);
1322
1323         /*
1324          * Check if we match the binding <address,port>.
1325          * Wildcard ports match/fail here.
1326          */
1327         if (isc_sockaddr_equal(&disp->local, addr))
1328                 return (ISC_TRUE);
1329         if (isc_sockaddr_getport(addr) == 0)
1330                 return (ISC_FALSE);
1331
1332         /*
1333          * Check if we match a bound wildcard port <address,port>.
1334          */
1335         if (!isc_sockaddr_eqaddr(&disp->local, addr))
1336                 return (ISC_FALSE);
1337         result = isc_socket_getsockname(disp->socket, &sockaddr);
1338         if (result != ISC_R_SUCCESS)
1339                 return (ISC_FALSE);
1340
1341         return (isc_sockaddr_equal(&sockaddr, addr));
1342 }
1343
1344 /*
1345  * Requires mgr be locked.
1346  *
1347  * No dispatcher can be locked by this thread when calling this function.
1348  *
1349  *
1350  * NOTE:
1351  *      If a matching dispatcher is found, it is locked after this function
1352  *      returns, and must be unlocked by the caller.
1353  */
1354 static isc_result_t
1355 dispatch_find(dns_dispatchmgr_t *mgr, isc_sockaddr_t *local,
1356               unsigned int attributes, unsigned int mask,
1357               dns_dispatch_t **dispp)
1358 {
1359         dns_dispatch_t *disp;
1360         isc_result_t result;
1361
1362         /*
1363          * Make certain that we will not match a private dispatch.
1364          */
1365         attributes &= ~DNS_DISPATCHATTR_PRIVATE;
1366         mask |= DNS_DISPATCHATTR_PRIVATE;
1367
1368         disp = ISC_LIST_HEAD(mgr->list);
1369         while (disp != NULL) {
1370                 LOCK(&disp->lock);
1371                 if ((disp->shutting_down == 0)
1372                     && ATTRMATCH(disp->attributes, attributes, mask)
1373                     && local_addr_match(disp, local))
1374                         break;
1375                 UNLOCK(&disp->lock);
1376                 disp = ISC_LIST_NEXT(disp, link);
1377         }
1378
1379         if (disp == NULL) {
1380                 result = ISC_R_NOTFOUND;
1381                 goto out;
1382         }
1383
1384         *dispp = disp;
1385         result = ISC_R_SUCCESS;
1386  out:
1387
1388         return (result);
1389 }
1390
1391 static isc_result_t
1392 qid_allocate(dns_dispatchmgr_t *mgr, unsigned int buckets,
1393              unsigned int increment, isc_boolean_t usepool, dns_qid_t **qidp)
1394 {
1395         dns_qid_t *qid;
1396         unsigned int i;
1397
1398         REQUIRE(VALID_DISPATCHMGR(mgr));
1399         REQUIRE(buckets < 2097169);  /* next prime > 65536 * 32 */
1400         REQUIRE(increment > buckets);
1401         REQUIRE(qidp != NULL && *qidp == NULL);
1402
1403         qid = isc_mem_get(mgr->mctx, sizeof(*qid));
1404         if (qid == NULL)
1405                 return (ISC_R_NOMEMORY);
1406
1407         qid->qid_table = isc_mem_get(mgr->mctx,
1408                                      buckets * sizeof(dns_displist_t));
1409         if (qid->qid_table == NULL) {
1410                 isc_mem_put(mgr->mctx, qid, sizeof(*qid));
1411                 return (ISC_R_NOMEMORY);
1412         }
1413
1414         if (nsid_init(mgr->mctx, &qid->nsid, usepool) != ISC_R_SUCCESS) {
1415                 isc_mem_put(mgr->mctx, qid->qid_table,
1416                             buckets * sizeof(dns_displist_t));
1417                 isc_mem_put(mgr->mctx, qid, sizeof(*qid));
1418                 return (ISC_R_NOMEMORY);
1419         }
1420
1421         if (isc_mutex_init(&qid->lock) != ISC_R_SUCCESS) {
1422                 UNEXPECTED_ERROR(__FILE__, __LINE__, "isc_mutex_init failed");
1423                 nsid_destroy(mgr->mctx, &qid->nsid);
1424                 isc_mem_put(mgr->mctx, qid->qid_table,
1425                             buckets * sizeof(dns_displist_t));
1426                 isc_mem_put(mgr->mctx, qid, sizeof(*qid));
1427                 return (ISC_R_UNEXPECTED);
1428         }
1429
1430         for (i = 0; i < buckets; i++)
1431                 ISC_LIST_INIT(qid->qid_table[i]);
1432
1433         qid->qid_nbuckets = buckets;
1434         qid->qid_increment = increment;
1435         qid->magic = QID_MAGIC;
1436         *qidp = qid;
1437         return (ISC_R_SUCCESS);
1438 }
1439
1440 static void
1441 qid_destroy(isc_mem_t *mctx, dns_qid_t **qidp) {
1442         dns_qid_t *qid;
1443
1444         REQUIRE(qidp != NULL);
1445         qid = *qidp;
1446
1447         REQUIRE(VALID_QID(qid));
1448
1449         *qidp = NULL;
1450         qid->magic = 0;
1451         nsid_destroy(mctx, &qid->nsid);
1452         isc_mem_put(mctx, qid->qid_table,
1453                     qid->qid_nbuckets * sizeof(dns_displist_t));
1454         DESTROYLOCK(&qid->lock);
1455         isc_mem_put(mctx, qid, sizeof(*qid));
1456 }
1457
1458 /*
1459  * Allocate and set important limits.
1460  */
1461 static isc_result_t
1462 dispatch_allocate(dns_dispatchmgr_t *mgr, unsigned int maxrequests,
1463                   dns_dispatch_t **dispp)
1464 {
1465         dns_dispatch_t *disp;
1466         isc_result_t res;
1467
1468         REQUIRE(VALID_DISPATCHMGR(mgr));
1469         REQUIRE(dispp != NULL && *dispp == NULL);
1470
1471         /*
1472          * Set up the dispatcher, mostly.  Don't bother setting some of
1473          * the options that are controlled by tcp vs. udp, etc.
1474          */
1475
1476         disp = isc_mempool_get(mgr->dpool);
1477         if (disp == NULL)
1478                 return (ISC_R_NOMEMORY);
1479
1480         disp->magic = 0;
1481         disp->mgr = mgr;
1482         disp->maxrequests = maxrequests;
1483         disp->attributes = 0;
1484         ISC_LINK_INIT(disp, link);
1485         disp->refcount = 1;
1486         disp->recv_pending = 0;
1487         memset(&disp->local, 0, sizeof(disp->local));
1488         disp->shutting_down = 0;
1489         disp->shutdown_out = 0;
1490         disp->connected = 0;
1491         disp->tcpmsg_valid = 0;
1492         disp->shutdown_why = ISC_R_UNEXPECTED;
1493         disp->requests = 0;
1494         disp->tcpbuffers = 0;
1495         disp->qid = NULL;
1496
1497         if (isc_mutex_init(&disp->lock) != ISC_R_SUCCESS) {
1498                 res = ISC_R_UNEXPECTED;
1499                 UNEXPECTED_ERROR(__FILE__, __LINE__, "isc_mutex_init failed");
1500                 goto deallocate;
1501         }
1502
1503         disp->failsafe_ev = allocate_event(disp);
1504         if (disp->failsafe_ev == NULL) {
1505                 res = ISC_R_NOMEMORY;
1506                 goto kill_lock;
1507         }
1508
1509         disp->magic = DISPATCH_MAGIC;
1510
1511         *dispp = disp;
1512         return (ISC_R_SUCCESS);
1513
1514         /*
1515          * error returns
1516          */
1517  kill_lock:
1518         DESTROYLOCK(&disp->lock);
1519  deallocate:
1520         isc_mempool_put(mgr->dpool, disp);
1521
1522         return (res);
1523 }
1524
1525
1526 /*
1527  * MUST be unlocked, and not used by anthing.
1528  */
1529 static void
1530 dispatch_free(dns_dispatch_t **dispp)
1531 {
1532         dns_dispatch_t *disp;
1533         dns_dispatchmgr_t *mgr;
1534
1535         REQUIRE(VALID_DISPATCH(*dispp));
1536         disp = *dispp;
1537         *dispp = NULL;
1538
1539         mgr = disp->mgr;
1540         REQUIRE(VALID_DISPATCHMGR(mgr));
1541
1542         if (disp->tcpmsg_valid) {
1543                 dns_tcpmsg_invalidate(&disp->tcpmsg);
1544                 disp->tcpmsg_valid = 0;
1545         }
1546
1547         INSIST(disp->tcpbuffers == 0);
1548         INSIST(disp->requests == 0);
1549         INSIST(disp->recv_pending == 0);
1550
1551         isc_mempool_put(mgr->epool, disp->failsafe_ev);
1552         disp->failsafe_ev = NULL;
1553
1554         if (disp->qid != NULL)
1555                 qid_destroy(mgr->mctx, &disp->qid);
1556         disp->mgr = NULL;
1557         DESTROYLOCK(&disp->lock);
1558         disp->magic = 0;
1559         isc_mempool_put(mgr->dpool, disp);
1560 }
1561
1562 isc_result_t
1563 dns_dispatch_createtcp(dns_dispatchmgr_t *mgr, isc_socket_t *sock,
1564                        isc_taskmgr_t *taskmgr, unsigned int buffersize,
1565                        unsigned int maxbuffers, unsigned int maxrequests,
1566                        unsigned int buckets, unsigned int increment,
1567                        unsigned int attributes, dns_dispatch_t **dispp)
1568 {
1569         isc_result_t result;
1570         dns_dispatch_t *disp;
1571
1572         UNUSED(maxbuffers);
1573         UNUSED(buffersize);
1574
1575         REQUIRE(VALID_DISPATCHMGR(mgr));
1576         REQUIRE(isc_socket_gettype(sock) == isc_sockettype_tcp);
1577         REQUIRE((attributes & DNS_DISPATCHATTR_TCP) != 0);
1578         REQUIRE((attributes & DNS_DISPATCHATTR_UDP) == 0);
1579
1580         attributes |= DNS_DISPATCHATTR_PRIVATE;  /* XXXMLG */
1581
1582         LOCK(&mgr->lock);
1583
1584         /*
1585          * dispatch_allocate() checks mgr for us.
1586          * qid_allocate() checks buckets and increment for us.
1587          */
1588         disp = NULL;
1589         result = dispatch_allocate(mgr, maxrequests, &disp);
1590         if (result != ISC_R_SUCCESS) {
1591                 UNLOCK(&mgr->lock);
1592                 return (result);
1593         }
1594
1595         result = qid_allocate(mgr, buckets, increment, ISC_FALSE, &disp->qid);
1596         if (result != ISC_R_SUCCESS)
1597                 goto deallocate_dispatch;
1598
1599         disp->socktype = isc_sockettype_tcp;
1600         disp->socket = NULL;
1601         isc_socket_attach(sock, &disp->socket);
1602
1603         disp->task = NULL;
1604         result = isc_task_create(taskmgr, 0, &disp->task);
1605         if (result != ISC_R_SUCCESS)
1606                 goto kill_socket;
1607
1608         disp->ctlevent = isc_event_allocate(mgr->mctx, disp,
1609                                             DNS_EVENT_DISPATCHCONTROL,
1610                                             destroy_disp, disp,
1611                                             sizeof(isc_event_t));
1612         if (disp->ctlevent == NULL)
1613                 goto kill_task;
1614
1615         isc_task_setname(disp->task, "tcpdispatch", disp);
1616
1617         dns_tcpmsg_init(mgr->mctx, disp->socket, &disp->tcpmsg);
1618         disp->tcpmsg_valid = 1;
1619
1620         disp->attributes = attributes;
1621
1622         /*
1623          * Append it to the dispatcher list.
1624          */
1625         ISC_LIST_APPEND(mgr->list, disp, link);
1626         UNLOCK(&mgr->lock);
1627
1628         mgr_log(mgr, LVL(90), "created TCP dispatcher %p", disp);
1629         dispatch_log(disp, LVL(90), "created task %p", disp->task);
1630
1631         *dispp = disp;
1632
1633         return (ISC_R_SUCCESS);
1634
1635         /*
1636          * Error returns.
1637          */
1638  kill_task:
1639         isc_task_detach(&disp->task);
1640  kill_socket:
1641         isc_socket_detach(&disp->socket);
1642  deallocate_dispatch:
1643         dispatch_free(&disp);
1644
1645         UNLOCK(&mgr->lock);
1646
1647         return (result);
1648 }
1649
1650 isc_result_t
1651 dns_dispatch_getudp(dns_dispatchmgr_t *mgr, isc_socketmgr_t *sockmgr,
1652                     isc_taskmgr_t *taskmgr, isc_sockaddr_t *localaddr,
1653                     unsigned int buffersize,
1654                     unsigned int maxbuffers, unsigned int maxrequests,
1655                     unsigned int buckets, unsigned int increment,
1656                     unsigned int attributes, unsigned int mask,
1657                     dns_dispatch_t **dispp)
1658 {
1659         isc_result_t result;
1660         dns_dispatch_t *disp;
1661
1662         REQUIRE(VALID_DISPATCHMGR(mgr));
1663         REQUIRE(sockmgr != NULL);
1664         REQUIRE(localaddr != NULL);
1665         REQUIRE(taskmgr != NULL);
1666         REQUIRE(buffersize >= 512 && buffersize < (64 * 1024));
1667         REQUIRE(maxbuffers > 0);
1668         REQUIRE(buckets < 2097169);  /* next prime > 65536 * 32 */
1669         REQUIRE(increment > buckets);
1670         REQUIRE(dispp != NULL && *dispp == NULL);
1671         REQUIRE((attributes & DNS_DISPATCHATTR_TCP) == 0);
1672
1673         result = dns_dispatchmgr_setudp(mgr, buffersize, maxbuffers,
1674                                         buckets, increment);
1675         if (result != ISC_R_SUCCESS)
1676                 return (result);
1677
1678         LOCK(&mgr->lock);
1679
1680         /*
1681          * First, see if we have a dispatcher that matches.
1682          */
1683         disp = NULL;
1684         result = dispatch_find(mgr, localaddr, attributes, mask, &disp);
1685         if (result == ISC_R_SUCCESS) {
1686                 disp->refcount++;
1687
1688                 if (disp->maxrequests < maxrequests)
1689                         disp->maxrequests = maxrequests;
1690
1691                 if ((disp->attributes & DNS_DISPATCHATTR_NOLISTEN) == 0 &&
1692                     (attributes & DNS_DISPATCHATTR_NOLISTEN) != 0)
1693                 {
1694                         disp->attributes |= DNS_DISPATCHATTR_NOLISTEN;
1695                         if (disp->recv_pending != 0)
1696                                 isc_socket_cancel(disp->socket, disp->task,
1697                                                   ISC_SOCKCANCEL_RECV);
1698                 }
1699
1700                 UNLOCK(&disp->lock);
1701                 UNLOCK(&mgr->lock);
1702
1703                 *dispp = disp;
1704
1705                 return (ISC_R_SUCCESS);
1706         }
1707
1708         /*
1709          * Nope, create one.
1710          */
1711         result = dispatch_createudp(mgr, sockmgr, taskmgr, localaddr,
1712                                     maxrequests, attributes, &disp);
1713         if (result != ISC_R_SUCCESS) {
1714                 UNLOCK(&mgr->lock);
1715                 return (result);
1716         }
1717
1718         UNLOCK(&mgr->lock);
1719         *dispp = disp;
1720         return (ISC_R_SUCCESS);
1721 }
1722
1723 /*
1724  * mgr should be locked.
1725  */
1726
1727 #ifndef DNS_DISPATCH_HELD
1728 #define DNS_DISPATCH_HELD 20U
1729 #endif
1730
1731 static isc_result_t
1732 dispatch_createudp(dns_dispatchmgr_t *mgr, isc_socketmgr_t *sockmgr,
1733                    isc_taskmgr_t *taskmgr,
1734                    isc_sockaddr_t *localaddr,
1735                    unsigned int maxrequests,
1736                    unsigned int attributes,
1737                    dns_dispatch_t **dispp)
1738 {
1739         isc_result_t result;
1740         dns_dispatch_t *disp;
1741         isc_socket_t *sock = NULL;
1742         isc_socket_t *held[DNS_DISPATCH_HELD];
1743         unsigned int i = 0, j = 0;
1744
1745         /*
1746          * dispatch_allocate() checks mgr for us.
1747          */
1748         disp = NULL;
1749         result = dispatch_allocate(mgr, maxrequests, &disp);
1750         if (result != ISC_R_SUCCESS)
1751                 return (result);
1752
1753         /*
1754          * Try to allocate a socket that is not on the blacklist.
1755          * Hold up to DNS_DISPATCH_HELD sockets to prevent the OS
1756          * from returning the same port to us too quickly.
1757          */
1758         memset(held, 0, sizeof(held));
1759  getsocket:
1760         result = create_socket(sockmgr, localaddr, &sock);
1761         if (result != ISC_R_SUCCESS)
1762                 goto deallocate_dispatch;
1763         if (isc_sockaddr_getport(localaddr) == 0 && blacklisted(mgr, sock)) {
1764                 if (held[i] != NULL)
1765                         isc_socket_detach(&held[i]);
1766                 held[i++] = sock;
1767                 sock = NULL;
1768                 if (i == DNS_DISPATCH_HELD)
1769                         i = 0;
1770                 if (j++ == 0xffffU) {
1771                         mgr_log(mgr, ISC_LOG_ERROR, "avoid-v%s-udp-ports: "
1772                                 "unable to allocate a non-blacklisted port",
1773                                 isc_sockaddr_pf(localaddr) == AF_INET ?
1774                                         "4" : "6");
1775                         result = ISC_R_FAILURE;
1776                         goto deallocate_dispatch;
1777                 }
1778                 goto getsocket;
1779         }
1780
1781         disp->socktype = isc_sockettype_udp;
1782         disp->socket = sock;
1783         disp->local = *localaddr;
1784
1785         disp->task = NULL;
1786         result = isc_task_create(taskmgr, 0, &disp->task);
1787         if (result != ISC_R_SUCCESS)
1788                 goto kill_socket;
1789
1790         disp->ctlevent = isc_event_allocate(mgr->mctx, disp,
1791                                             DNS_EVENT_DISPATCHCONTROL,
1792                                             destroy_disp, disp,
1793                                             sizeof(isc_event_t));
1794         if (disp->ctlevent == NULL)
1795                 goto kill_task;
1796
1797         isc_task_setname(disp->task, "udpdispatch", disp);
1798
1799         attributes &= ~DNS_DISPATCHATTR_TCP;
1800         attributes |= DNS_DISPATCHATTR_UDP;
1801         disp->attributes = attributes;
1802
1803         /*
1804          * Append it to the dispatcher list.
1805          */
1806         ISC_LIST_APPEND(mgr->list, disp, link);
1807
1808         mgr_log(mgr, LVL(90), "created UDP dispatcher %p", disp);
1809         dispatch_log(disp, LVL(90), "created task %p", disp->task);
1810         dispatch_log(disp, LVL(90), "created socket %p", disp->socket);
1811
1812         *dispp = disp;
1813
1814         goto cleanheld;
1815
1816         /*
1817          * Error returns.
1818          */
1819  kill_task:
1820         isc_task_detach(&disp->task);
1821  kill_socket:
1822         isc_socket_detach(&disp->socket);
1823  deallocate_dispatch:
1824         dispatch_free(&disp);
1825  cleanheld:
1826         for (i = 0; i < DNS_DISPATCH_HELD; i++)
1827                 if (held[i] != NULL)
1828                         isc_socket_detach(&held[i]);
1829         return (result);
1830 }
1831
1832 void
1833 dns_dispatch_attach(dns_dispatch_t *disp, dns_dispatch_t **dispp) {
1834         REQUIRE(VALID_DISPATCH(disp));
1835         REQUIRE(dispp != NULL && *dispp == NULL);
1836
1837         LOCK(&disp->lock);
1838         disp->refcount++;
1839         UNLOCK(&disp->lock);
1840
1841         *dispp = disp;
1842 }
1843
1844 /*
1845  * It is important to lock the manager while we are deleting the dispatch,
1846  * since dns_dispatch_getudp will call dispatch_find, which returns to
1847  * the caller a dispatch but does not attach to it until later.  _getudp
1848  * locks the manager, however, so locking it here will keep us from attaching
1849  * to a dispatcher that is in the process of going away.
1850  */
1851 void
1852 dns_dispatch_detach(dns_dispatch_t **dispp) {
1853         dns_dispatch_t *disp;
1854         isc_boolean_t killit;
1855
1856         REQUIRE(dispp != NULL && VALID_DISPATCH(*dispp));
1857
1858         disp = *dispp;
1859         *dispp = NULL;
1860
1861         LOCK(&disp->lock);
1862
1863         INSIST(disp->refcount > 0);
1864         disp->refcount--;
1865         killit = ISC_FALSE;
1866         if (disp->refcount == 0) {
1867                 if (disp->recv_pending > 0)
1868                         isc_socket_cancel(disp->socket, disp->task,
1869                                           ISC_SOCKCANCEL_RECV);
1870                 disp->shutting_down = 1;
1871         }
1872
1873         dispatch_log(disp, LVL(90), "detach: refcount %d", disp->refcount);
1874
1875         killit = destroy_disp_ok(disp);
1876         UNLOCK(&disp->lock);
1877         if (killit)
1878                 isc_task_send(disp->task, &disp->ctlevent);
1879 }
1880
1881 isc_result_t
1882 dns_dispatch_addresponse(dns_dispatch_t *disp, isc_sockaddr_t *dest,
1883                          isc_task_t *task, isc_taskaction_t action, void *arg,
1884                          dns_messageid_t *idp, dns_dispentry_t **resp)
1885 {
1886         dns_dispentry_t *res;
1887         unsigned int bucket;
1888         dns_messageid_t id;
1889         int i;
1890         isc_boolean_t ok;
1891         dns_qid_t *qid;
1892
1893         REQUIRE(VALID_DISPATCH(disp));
1894         REQUIRE(task != NULL);
1895         REQUIRE(dest != NULL);
1896         REQUIRE(resp != NULL && *resp == NULL);
1897         REQUIRE(idp != NULL);
1898
1899         LOCK(&disp->lock);
1900
1901         if (disp->shutting_down == 1) {
1902                 UNLOCK(&disp->lock);
1903                 return (ISC_R_SHUTTINGDOWN);
1904         }
1905
1906         if (disp->requests >= disp->maxrequests) {
1907                 UNLOCK(&disp->lock);
1908                 return (ISC_R_QUOTA);
1909         }
1910
1911         /*
1912          * Try somewhat hard to find an unique ID.
1913          */
1914         qid = DNS_QID(disp);
1915         LOCK(&qid->lock);
1916         id = dns_randomid(&qid->nsid);
1917         bucket = dns_hash(qid, dest, id);
1918         ok = ISC_FALSE;
1919         for (i = 0; i < 64; i++) {
1920                 if (bucket_search(qid, dest, id, bucket) == NULL) {
1921                         ok = ISC_TRUE;
1922                         break;
1923                 }
1924                 id += qid->qid_increment;
1925                 id &= 0x0000ffff;
1926                 bucket = dns_hash(qid, dest, id);
1927         }
1928
1929         if (!ok) {
1930                 UNLOCK(&qid->lock);
1931                 UNLOCK(&disp->lock);
1932                 return (ISC_R_NOMORE);
1933         }
1934
1935         res = isc_mempool_get(disp->mgr->rpool);
1936         if (res == NULL) {
1937                 UNLOCK(&qid->lock);
1938                 UNLOCK(&disp->lock);
1939                 return (ISC_R_NOMEMORY);
1940         }
1941
1942         disp->refcount++;
1943         disp->requests++;
1944         res->task = NULL;
1945         isc_task_attach(task, &res->task);
1946         res->disp = disp;
1947         res->id = id;
1948         res->bucket = bucket;
1949         res->host = *dest;
1950         res->action = action;
1951         res->arg = arg;
1952         res->item_out = ISC_FALSE;
1953         ISC_LIST_INIT(res->items);
1954         ISC_LINK_INIT(res, link);
1955         res->magic = RESPONSE_MAGIC;
1956         ISC_LIST_APPEND(qid->qid_table[bucket], res, link);
1957         UNLOCK(&qid->lock);
1958
1959         request_log(disp, res, LVL(90),
1960                     "attached to task %p", res->task);
1961
1962         if (((disp->attributes & DNS_DISPATCHATTR_UDP) != 0) ||
1963             ((disp->attributes & DNS_DISPATCHATTR_CONNECTED) != 0))
1964                 startrecv(disp);
1965
1966         UNLOCK(&disp->lock);
1967
1968         *idp = id;
1969         *resp = res;
1970
1971         return (ISC_R_SUCCESS);
1972 }
1973
1974 void
1975 dns_dispatch_starttcp(dns_dispatch_t *disp) {
1976
1977         REQUIRE(VALID_DISPATCH(disp));
1978
1979         dispatch_log(disp, LVL(90), "starttcp %p", disp->task);
1980
1981         LOCK(&disp->lock);
1982         disp->attributes |= DNS_DISPATCHATTR_CONNECTED;
1983         startrecv(disp);
1984         UNLOCK(&disp->lock);
1985 }
1986
1987 void
1988 dns_dispatch_removeresponse(dns_dispentry_t **resp,
1989                             dns_dispatchevent_t **sockevent)
1990 {
1991         dns_dispatchmgr_t *mgr;
1992         dns_dispatch_t *disp;
1993         dns_dispentry_t *res;
1994         dns_dispatchevent_t *ev;
1995         unsigned int bucket;
1996         isc_boolean_t killit;
1997         unsigned int n;
1998         isc_eventlist_t events;
1999         dns_qid_t *qid;
2000
2001         REQUIRE(resp != NULL);
2002         REQUIRE(VALID_RESPONSE(*resp));
2003
2004         res = *resp;
2005         *resp = NULL;
2006
2007         disp = res->disp;
2008         REQUIRE(VALID_DISPATCH(disp));
2009         mgr = disp->mgr;
2010         REQUIRE(VALID_DISPATCHMGR(mgr));
2011
2012         qid = DNS_QID(disp);
2013
2014         if (sockevent != NULL) {
2015                 REQUIRE(*sockevent != NULL);
2016                 ev = *sockevent;
2017                 *sockevent = NULL;
2018         } else {
2019                 ev = NULL;
2020         }
2021
2022         LOCK(&disp->lock);
2023
2024         INSIST(disp->requests > 0);
2025         disp->requests--;
2026         INSIST(disp->refcount > 0);
2027         disp->refcount--;
2028         killit = ISC_FALSE;
2029         if (disp->refcount == 0) {
2030                 if (disp->recv_pending > 0)
2031                         isc_socket_cancel(disp->socket, disp->task,
2032                                           ISC_SOCKCANCEL_RECV);
2033                 disp->shutting_down = 1;
2034         }
2035
2036         bucket = res->bucket;
2037
2038         LOCK(&qid->lock);
2039         ISC_LIST_UNLINK(qid->qid_table[bucket], res, link);
2040         UNLOCK(&qid->lock);
2041
2042         if (ev == NULL && res->item_out) {
2043                 /*
2044                  * We've posted our event, but the caller hasn't gotten it
2045                  * yet.  Take it back.
2046                  */
2047                 ISC_LIST_INIT(events);
2048                 n = isc_task_unsend(res->task, res, DNS_EVENT_DISPATCH,
2049                                     NULL, &events);
2050                 /*
2051                  * We had better have gotten it back.
2052                  */
2053                 INSIST(n == 1);
2054                 ev = (dns_dispatchevent_t *)ISC_LIST_HEAD(events);
2055         }
2056
2057         if (ev != NULL) {
2058                 REQUIRE(res->item_out == ISC_TRUE);
2059                 res->item_out = ISC_FALSE;
2060                 if (ev->buffer.base != NULL)
2061                         free_buffer(disp, ev->buffer.base, ev->buffer.length);
2062                 free_event(disp, ev);
2063         }
2064
2065         request_log(disp, res, LVL(90), "detaching from task %p", res->task);
2066         isc_task_detach(&res->task);
2067
2068         /*
2069          * Free any buffered requests as well
2070          */
2071         ev = ISC_LIST_HEAD(res->items);
2072         while (ev != NULL) {
2073                 ISC_LIST_UNLINK(res->items, ev, ev_link);
2074                 if (ev->buffer.base != NULL)
2075                         free_buffer(disp, ev->buffer.base, ev->buffer.length);
2076                 free_event(disp, ev);
2077                 ev = ISC_LIST_HEAD(res->items);
2078         }
2079         res->magic = 0;
2080         isc_mempool_put(disp->mgr->rpool, res);
2081         if (disp->shutting_down == 1)
2082                 do_cancel(disp);
2083         else
2084                 startrecv(disp);
2085
2086         killit = destroy_disp_ok(disp);
2087         UNLOCK(&disp->lock);
2088         if (killit)
2089                 isc_task_send(disp->task, &disp->ctlevent);
2090 }
2091
2092 static void
2093 do_cancel(dns_dispatch_t *disp) {
2094         dns_dispatchevent_t *ev;
2095         dns_dispentry_t *resp;
2096         dns_qid_t *qid;
2097
2098         if (disp->shutdown_out == 1)
2099                 return;
2100
2101         qid = DNS_QID(disp);
2102
2103         /*
2104          * Search for the first response handler without packets outstanding.
2105          */
2106         LOCK(&qid->lock);
2107         for (resp = linear_first(qid);
2108              resp != NULL && resp->item_out != ISC_FALSE;
2109              /* Empty. */)
2110                 resp = linear_next(qid, resp);
2111         /*
2112          * No one to send the cancel event to, so nothing to do.
2113          */
2114         if (resp == NULL)
2115                 goto unlock;
2116
2117         /*
2118          * Send the shutdown failsafe event to this resp.
2119          */
2120         ev = disp->failsafe_ev;
2121         ISC_EVENT_INIT(ev, sizeof(*ev), 0, NULL, DNS_EVENT_DISPATCH,
2122                        resp->action, resp->arg, resp, NULL, NULL);
2123         ev->result = disp->shutdown_why;
2124         ev->buffer.base = NULL;
2125         ev->buffer.length = 0;
2126         disp->shutdown_out = 1;
2127         request_log(disp, resp, LVL(10),
2128                     "cancel: failsafe event %p -> task %p",
2129                     ev, resp->task);
2130         resp->item_out = ISC_TRUE;
2131         isc_task_send(resp->task, ISC_EVENT_PTR(&ev));
2132  unlock:
2133         UNLOCK(&qid->lock);
2134 }
2135
2136 isc_socket_t *
2137 dns_dispatch_getsocket(dns_dispatch_t *disp) {
2138         REQUIRE(VALID_DISPATCH(disp));
2139
2140         return (disp->socket);
2141 }
2142
2143 isc_result_t
2144 dns_dispatch_getlocaladdress(dns_dispatch_t *disp, isc_sockaddr_t *addrp) {
2145
2146         REQUIRE(VALID_DISPATCH(disp));
2147         REQUIRE(addrp != NULL);
2148
2149         if (disp->socktype == isc_sockettype_udp) {
2150                 *addrp = disp->local;
2151                 return (ISC_R_SUCCESS);
2152         }
2153         return (ISC_R_NOTIMPLEMENTED);
2154 }
2155
2156 void
2157 dns_dispatch_cancel(dns_dispatch_t *disp) {
2158         REQUIRE(VALID_DISPATCH(disp));
2159
2160         LOCK(&disp->lock);
2161
2162         if (disp->shutting_down == 1) {
2163                 UNLOCK(&disp->lock);
2164                 return;
2165         }
2166
2167         disp->shutdown_why = ISC_R_CANCELED;
2168         disp->shutting_down = 1;
2169         do_cancel(disp);
2170
2171         UNLOCK(&disp->lock);
2172
2173         return;
2174 }
2175
2176 void
2177 dns_dispatch_changeattributes(dns_dispatch_t *disp,
2178                               unsigned int attributes, unsigned int mask)
2179 {
2180         REQUIRE(VALID_DISPATCH(disp));
2181
2182         /* XXXMLG
2183          * Should check for valid attributes here!
2184          */
2185
2186         LOCK(&disp->lock);
2187
2188         if ((mask & DNS_DISPATCHATTR_NOLISTEN) != 0) {
2189                 if ((disp->attributes & DNS_DISPATCHATTR_NOLISTEN) != 0 &&
2190                     (attributes & DNS_DISPATCHATTR_NOLISTEN) == 0) {
2191                         disp->attributes &= ~DNS_DISPATCHATTR_NOLISTEN;
2192                         startrecv(disp);
2193                 } else if ((disp->attributes & DNS_DISPATCHATTR_NOLISTEN)
2194                            == 0 &&
2195                            (attributes & DNS_DISPATCHATTR_NOLISTEN) != 0) {
2196                         disp->attributes |= DNS_DISPATCHATTR_NOLISTEN;
2197                         if (disp->recv_pending != 0)
2198                                 isc_socket_cancel(disp->socket, disp->task,
2199                                                   ISC_SOCKCANCEL_RECV);
2200                 }
2201         }
2202
2203         disp->attributes &= ~mask;
2204         disp->attributes |= (attributes & mask);
2205         UNLOCK(&disp->lock);
2206 }
2207
2208 void
2209 dns_dispatch_importrecv(dns_dispatch_t *disp, isc_event_t *event) {
2210         void *buf;
2211         isc_socketevent_t *sevent, *newsevent;
2212
2213         REQUIRE(VALID_DISPATCH(disp));
2214         REQUIRE((disp->attributes & DNS_DISPATCHATTR_NOLISTEN) != 0);
2215         REQUIRE(event != NULL);
2216
2217         sevent = (isc_socketevent_t *)event;
2218
2219         INSIST(sevent->n <= disp->mgr->buffersize);
2220         newsevent = (isc_socketevent_t *)
2221                     isc_event_allocate(disp->mgr->mctx, NULL,
2222                                       DNS_EVENT_IMPORTRECVDONE, udp_recv,
2223                                       disp, sizeof(isc_socketevent_t));
2224         if (newsevent == NULL)
2225                 return;
2226
2227         buf = allocate_udp_buffer(disp);
2228         if (buf == NULL) {
2229                 isc_event_free(ISC_EVENT_PTR(&newsevent));
2230                 return;
2231         }
2232         memcpy(buf, sevent->region.base, sevent->n);
2233         newsevent->region.base = buf;
2234         newsevent->region.length = disp->mgr->buffersize;
2235         newsevent->n = sevent->n;
2236         newsevent->result = sevent->result;
2237         newsevent->address = sevent->address;
2238         newsevent->timestamp = sevent->timestamp;
2239         newsevent->pktinfo = sevent->pktinfo;
2240         newsevent->attributes = sevent->attributes;
2241
2242         isc_task_send(disp->task, ISC_EVENT_PTR(&newsevent));
2243 }
2244
2245 #if 0
2246 void
2247 dns_dispatchmgr_dump(dns_dispatchmgr_t *mgr) {
2248         dns_dispatch_t *disp;
2249         char foo[1024];
2250
2251         disp = ISC_LIST_HEAD(mgr->list);
2252         while (disp != NULL) {
2253                 isc_sockaddr_format(&disp->local, foo, sizeof(foo));
2254                 printf("\tdispatch %p, addr %s\n", disp, foo);
2255                 disp = ISC_LIST_NEXT(disp, link);
2256         }
2257 }
2258 #endif
2259
2260 /*
2261  * Allow the user to pick one of two ID randomization algorithms.
2262  *
2263  * The first algorithm is an adaptation of the sequence shuffling
2264  * algorithm discovered by Carter Bays and S. D. Durham [ACM Trans. Math.
2265  * Software 2 (1976), 59-64], as documented as Algorithm B in Chapter
2266  * 3.2.2 in Volume 2 of Knuth's "The Art of Computer Programming".  We use
2267  * a randomly selected linear congruential random number generator with a
2268  * modulus of 2^16, whose increment is a randomly picked odd number, and
2269  * whose multiplier is picked from a set which meets the following
2270  * criteria:
2271  *     Is of the form 8*n+5, which ensures "high potency" according to
2272  *     principle iii in the summary chapter 3.6.  This form also has a
2273  *     gcd(a-1,m) of 4 which is good according to principle iv.
2274  *
2275  *     Is between 0.01 and 0.99 times the modulus as specified by
2276  *     principle iv.
2277  *
2278  *     Passes the spectral test "with flying colors" (ut >= 1) in
2279  *     dimensions 2 through 6 as calculated by Algorithm S in Chapter
2280  *     3.3.4 and the ratings calculated by formula 35 in section E.
2281  *
2282  *     Of the multipliers that pass this test, pick the set that is
2283  *     best according to the theoretical bounds of the serial
2284  *     correlation test.  This was calculated using a simplified
2285  *     version of Knuth's Theorem K in Chapter 3.3.3.
2286  *
2287  * These criteria may not be important for this use, but we might as well
2288  * pick from the best generators since there are so many possible ones and
2289  * we don't have that many random bits to do the picking.
2290  *
2291  * We use a modulus of 2^16 instead of something bigger so that we will
2292  * tend to cycle through all the possible IDs before repeating any,
2293  * however the shuffling will perturb this somewhat.  Theoretically there
2294  * is no minimimum interval between two uses of the same ID, but in
2295  * practice it seems to be >64000.
2296  *
2297  * Our adaptatation  of Algorithm B mixes the hash state which has
2298  * captured various random events into the shuffler to perturb the
2299  * sequence.
2300  *
2301  * One disadvantage of this algorithm is that if the generator parameters
2302  * were to be guessed, it would be possible to mount a limited brute force
2303  * attack on the ID space since the IDs are only shuffled within a limited
2304  * range.
2305  *
2306  * The second algorithm uses the same random number generator to populate
2307  * a pool of 65536 IDs.  The hash state is used to pick an ID from a window
2308  * of 4096 IDs in this pool, then the chosen ID is swapped with the ID
2309  * at the beginning of the window and the window position is advanced.
2310  * This means that the interval between uses of the ID will be no less
2311  * than 65536-4096.  The ID sequence in the pool will become more random
2312  * over time.
2313  *
2314  * For both algorithms, two more linear congruential random number generators
2315  * are selected.  The ID from the first part of algorithm is used to seed
2316  * the first of these generators, and its output is used to seed the second.
2317  * The strategy is use these generators as 1 to 1 hashes to obfuscate the
2318  * properties of the generator used in the first part of either algorithm.
2319  *
2320  * The first algorithm may be suitable for use in a client resolver since
2321  * its memory requirements are fairly low and it's pretty random out of
2322  * the box.  It is somewhat succeptible to a limited brute force attack,
2323  * so the second algorithm is probably preferable for a longer running
2324  * program that issues a large number of queries and has time to randomize
2325  * the pool.
2326  */
2327
2328 #define NSID_SHUFFLE_TABLE_SIZE 100 /* Suggested by Knuth */
2329 /*
2330  * Pick one of the next 4096 IDs in the pool.
2331  * There is a tradeoff here between randomness and how often and ID is reused.
2332  */
2333 #define NSID_LOOKAHEAD 4096     /* Must be a power of 2 */
2334 #define NSID_SHUFFLE_ONLY 1     /* algorithm 1 */
2335 #define NSID_USE_POOL 2         /* algorithm 2 */
2336 #define NSID_HASHSHIFT       3
2337 #define NSID_HASHROTATE(v) \
2338         (((v) << NSID_HASHSHIFT) | ((v) >> ((sizeof(v) * 8) - NSID_HASHSHIFT)))
2339
2340 static isc_uint32_t     nsid_hash_state;
2341
2342 /*
2343  * Keep a running hash of various bits of data that we'll use to
2344  * stir the ID pool or perturb the ID generator
2345  */
2346 static void
2347 nsid_hash(void *data, size_t len) {
2348         unsigned char *p = data;
2349         /*
2350          * Hash function similar to the one we use for hashing names.
2351          * We don't fold case or toss the upper bit here, though.
2352          * This hash doesn't do much interesting when fed binary zeros,
2353          * so there may be a better hash function.
2354          * This function doesn't need to be very strong since we're
2355          * only using it to stir the pool, but it should be reasonably
2356          * fast.
2357          */
2358         /*
2359          * We don't care about locking access to nsid_hash_state.
2360          * In fact races make the result even more non deteministic.
2361          */
2362         while (len-- > 0U) {
2363                 nsid_hash_state = NSID_HASHROTATE(nsid_hash_state);
2364                 nsid_hash_state += *p++;
2365         }
2366 }
2367
2368 /*
2369  * Table of good linear congruential multipliers for modulus 2^16
2370  * in order of increasing serial correlation bounds (so trim from
2371  * the end).
2372  */
2373 static const isc_uint16_t nsid_multiplier_table[] = {
2374         17565, 25013, 11733, 19877, 23989, 23997, 24997, 25421,
2375         26781, 27413, 35901, 35917, 35973, 36229, 38317, 38437,
2376         39941, 40493, 41853, 46317, 50581, 51429, 53453, 53805,
2377         11317, 11789, 12045, 12413, 14277, 14821, 14917, 18989,
2378         19821, 23005, 23533, 23573, 23693, 27549, 27709, 28461,
2379         29365, 35605, 37693, 37757, 38309, 41285, 45261, 47061,
2380         47269, 48133, 48597, 50277, 50717, 50757, 50805, 51341,
2381         51413, 51581, 51597, 53445, 11493, 14229, 20365, 20653,
2382         23485, 25541, 27429, 29421, 30173, 35445, 35653, 36789,
2383         36797, 37109, 37157, 37669, 38661, 39773, 40397, 41837,
2384         41877, 45293, 47277, 47845, 49853, 51085, 51349, 54085,
2385         56933,  8877,  8973,  9885, 11365, 11813, 13581, 13589,
2386         13613, 14109, 14317, 15765, 15789, 16925, 17069, 17205,
2387         17621, 17941, 19077, 19381, 20245, 22845, 23733, 24869,
2388         25453, 27213, 28381, 28965, 29245, 29997, 30733, 30901,
2389         34877, 35485, 35613, 36133, 36661, 36917, 38597, 40285,
2390         40693, 41413, 41541, 41637, 42053, 42349, 45245, 45469,
2391         46493, 48205, 48613, 50861, 51861, 52877, 53933, 54397,
2392         55669, 56453, 56965, 58021,  7757,  7781,  8333,  9661,
2393         12229, 14373, 14453, 17549, 18141, 19085, 20773, 23701,
2394         24205, 24333, 25261, 25317, 27181, 30117, 30477, 34757,
2395         34885, 35565, 35885, 36541, 37957, 39733, 39813, 41157,
2396         41893, 42317, 46621, 48117, 48181, 49525, 55261, 55389,
2397         56845,  7045,  7749,  7965,  8469,  9133,  9549,  9789,
2398         10173, 11181, 11285, 12253, 13453, 13533, 13757, 14477,
2399         15053, 16901, 17213, 17269, 17525, 17629, 18605, 19013,
2400         19829, 19933, 20069, 20093, 23261, 23333, 24949, 25309,
2401         27613, 28453, 28709, 29301, 29541, 34165, 34413, 37301,
2402         37773, 38045, 38405, 41077, 41781, 41925, 42717, 44437,
2403         44525, 44613, 45933, 45941, 47077, 50077, 50893, 52117,
2404          5293, 55069, 55989, 58125, 59205,  6869, 14685, 15453,
2405         16821, 17045, 17613, 18437, 21029, 22773, 22909, 25445,
2406         25757, 26541, 30709, 30909, 31093, 31149, 37069, 37725,
2407         37925, 38949, 39637, 39701, 40765, 40861, 42965, 44813,
2408         45077, 45733, 47045, 50093, 52861, 52957, 54181, 56325,
2409         56365, 56381, 56877, 57013,  5741, 58101, 58669,  8613,
2410         10045, 10261, 10653, 10733, 11461, 12261, 14069, 15877,
2411         17757, 21165, 23885, 24701, 26429, 26645, 27925, 28765,
2412         29197, 30189, 31293, 39781, 39909, 40365, 41229, 41453,
2413         41653, 42165, 42365, 47421, 48029, 48085, 52773,  5573,
2414         57037, 57637, 58341, 58357, 58901,  6357,  7789,  9093,
2415         10125, 10709, 10765, 11957, 12469, 13437, 13509, 14773,
2416         15437, 15773, 17813, 18829, 19565, 20237, 23461, 23685,
2417         23725, 23941, 24877, 25461, 26405, 29509, 30285, 35181,
2418         37229, 37893, 38565, 40293, 44189, 44581, 45701, 47381,
2419         47589, 48557,  4941, 51069,  5165, 52797, 53149,  5341,
2420         56301, 56765, 58581, 59493, 59677,  6085,  6349,  8293,
2421          8501,  8517, 11597, 11709, 12589, 12693, 13517, 14909,
2422         17397, 18085, 21101, 21269, 22717, 25237, 25661, 29189,
2423         30101, 31397, 33933, 34213, 34661, 35533, 36493, 37309,
2424         40037,  4189, 42909, 44309, 44357, 44389,  4541, 45461,
2425         46445, 48237, 54149, 55301, 55853, 56621, 56717, 56901,
2426          5813, 58437, 12493, 15365, 15989, 17829, 18229, 19341,
2427         21013, 21357, 22925, 24885, 26053, 27581, 28221, 28485,
2428         30605, 30613, 30789, 35437, 36285, 37189,  3941, 41797,
2429          4269, 42901, 43293, 44645, 45221, 46893,  4893, 50301,
2430         50325,  5189, 52109, 53517, 54053, 54485,  5525, 55949,
2431         56973, 59069, 59421, 60733, 61253,  6421,  6701,  6709,
2432          7101,  8669, 15797, 19221, 19837, 20133, 20957, 21293,
2433         21461, 22461, 29085, 29861, 30869, 34973, 36469, 37565,
2434         38125, 38829, 39469, 40061, 40117, 44093, 47429, 48341,
2435         50597, 51757,  5541, 57629, 58405, 59621, 59693, 59701,
2436         61837,  7061, 10421, 11949, 15405, 20861, 25397, 25509,
2437         25893, 26037, 28629, 28869, 29605, 30213, 34205, 35637,
2438         36365, 37285,  3773, 39117,  4021, 41061, 42653, 44509,
2439          4461, 44829,  4725,  5125, 52269, 56469, 59085,  5917,
2440         60973,  8349, 17725, 18637, 19773, 20293, 21453, 22533,
2441         24285, 26333, 26997, 31501, 34541, 34805, 37509, 38477,
2442         41333, 44125, 46285, 46997, 47637, 48173,  4925, 50253,
2443         50381, 50917, 51205, 51325, 52165, 52229,  5253,  5269,
2444         53509, 56253, 56341,  5821, 58373, 60301, 61653, 61973,
2445         62373,  8397, 11981, 14341, 14509, 15077, 22261, 22429,
2446         24261, 28165, 28685, 30661, 34021, 34445, 39149,  3917,
2447         43013, 43317, 44053, 44101,  4533, 49541, 49981,  5277,
2448         54477, 56357, 57261, 57765, 58573, 59061, 60197, 61197,
2449         62189,  7725,  8477,  9565, 10229, 11437, 14613, 14709,
2450         16813, 20029, 20677, 31445,  3165, 31957,  3229, 33541,
2451         36645,  3805, 38973,  3965,  4029, 44293, 44557, 46245,
2452         48917,  4909, 51749, 53709, 55733, 56445,  5925,  6093,
2453         61053, 62637,  8661,  9109, 10821, 11389, 13813, 14325,
2454         15501, 16149, 18845, 22669, 26437, 29869, 31837, 33709,
2455         33973, 34173,  3677,  3877,  3981, 39885, 42117,  4421,
2456         44221, 44245, 44693, 46157, 47309,  5005, 51461, 52037,
2457         55333, 55693, 56277, 58949,  6205, 62141, 62469,  6293,
2458         10101, 12509, 14029, 17997, 20469, 21149, 25221, 27109,
2459          2773,  2877, 29405, 31493, 31645,  4077, 42005, 42077,
2460         42469, 42501, 44013, 48653, 49349,  4997, 50101, 55405,
2461         56957, 58037, 59429, 60749, 61797, 62381, 62837,  6605,
2462         10541, 23981, 24533,  2701, 27333, 27341, 31197, 33805,
2463          3621, 37381,  3749,  3829, 38533, 42613, 44381, 45901,
2464         48517, 51269, 57725, 59461, 60045, 62029, 13805, 14013,
2465         15461, 16069, 16157, 18573,  2309, 23501, 28645,  3077,
2466         31541, 36357, 36877,  3789, 39429, 39805, 47685, 47949,
2467         49413,  5485, 56757, 57549, 57805, 58317, 59549, 62213,
2468         62613, 62853, 62933,  8909, 12941, 16677, 20333, 21541,
2469         24429, 26077, 26421,  2885, 31269, 33381,  3661, 40925,
2470         42925, 45173,  4525,  4709, 53133, 55941, 57413, 57797,
2471         62125, 62237, 62733,  6773, 12317, 13197, 16533, 16933,
2472         18245,  2213,  2477, 29757, 33293, 35517, 40133, 40749,
2473          4661, 49941, 62757,  7853,  8149,  8573, 11029, 13421,
2474         21549, 22709, 22725, 24629,  2469, 26125,  2669, 34253,
2475         36709, 41013, 45597, 46637, 52285, 52333, 54685, 59013,
2476         60997, 61189, 61981, 62605, 62821,  7077,  7525,  8781,
2477         10861, 15277,  2205, 22077, 28517, 28949, 32109, 33493,
2478          4661, 49941, 62757,  7853,  8149,  8573, 11029, 13421,
2479         21549, 22709, 22725, 24629,  2469, 26125,  2669, 34253,
2480         36709, 41013, 45597, 46637, 52285, 52333, 54685, 59013,
2481         60997, 61189, 61981, 62605, 62821,  7077,  7525,  8781,
2482         10861, 15277,  2205, 22077, 28517, 28949, 32109, 33493,
2483          3685, 39197, 39869, 42621, 44997, 48565,  5221, 57381,
2484         61749, 62317, 63245, 63381, 23149,  2549, 28661, 31653,
2485         33885, 36341, 37053, 39517, 42805, 45853, 48997, 59349,
2486         60053, 62509, 63069,  6525,  1893, 20181,  2365, 24893,
2487         27397, 31357, 32277, 33357, 34437, 36677, 37661, 43469,
2488         43917, 50997, 53869,  5653, 13221, 16741, 17893,  2157,
2489         28653, 31789, 35301, 35821, 61613, 62245, 12405, 14517,
2490         17453, 18421,  3149,  3205, 40341,  4109, 43941, 46869,
2491         48837, 50621, 57405, 60509, 62877,  8157, 12933, 12957,
2492         16501, 19533,  3461, 36829, 52357, 58189, 58293, 63053,
2493         17109,  1933, 32157, 37701, 59005, 61621, 13029, 15085,
2494         16493, 32317, 35093,  5061, 51557, 62221, 20765, 24613,
2495          2629, 30861, 33197, 33749, 35365, 37933, 40317, 48045,
2496         56229, 61157, 63797,  7917, 17965,  1917,  1973, 20301,
2497          2253, 33157, 58629, 59861, 61085, 63909,  8141,  9221,
2498         14757,  1581, 21637, 26557, 33869, 34285, 35733, 40933,
2499         42517, 43501, 53653, 61885, 63805,  7141, 21653, 54973,
2500         31189, 60061, 60341, 63357, 16045,  2053, 26069, 33997,
2501         43901, 54565, 63837,  8949, 17909, 18693, 32349, 33125,
2502         37293, 48821, 49053, 51309, 64037,  7117,  1445, 20405,
2503         23085, 26269, 26293, 27349, 32381, 33141, 34525, 36461,
2504         37581, 43525,  4357, 43877,  5069, 55197, 63965,  9845,
2505         12093,  2197,  2229, 32165, 33469, 40981, 42397,  8749,
2506         10853,  1453, 18069, 21693, 30573, 36261, 37421, 42533
2507 };
2508
2509 #define NSID_MULT_TABLE_SIZE \
2510         ((sizeof nsid_multiplier_table)/(sizeof nsid_multiplier_table[0]))
2511 #define NSID_RANGE_MASK (NSID_LOOKAHEAD - 1)
2512 #define NSID_POOL_MASK 0xFFFF /* used to wrap the pool index */
2513 #define NSID_SHUFFLE_ONLY 1
2514 #define NSID_USE_POOL 2
2515
2516 static isc_uint16_t
2517 nsid_next(dns_nsid_t *nsid) {
2518         isc_uint16_t id, compressed_hash;
2519         isc_uint16_t j;
2520
2521         compressed_hash = ((nsid_hash_state >> 16) ^
2522                            (nsid_hash_state)) & 0xFFFF;
2523
2524         if (nsid->nsid_usepool) {
2525                 isc_uint16_t pick;
2526
2527                 pick = compressed_hash & NSID_RANGE_MASK;
2528                 pick = (nsid->nsid_state + pick) & NSID_POOL_MASK;
2529                 id = nsid->nsid_pool[pick];
2530                 if (pick != 0) {
2531                         /* Swap two IDs to stir the pool */
2532                         nsid->nsid_pool[pick] =
2533                                 nsid->nsid_pool[nsid->nsid_state];
2534                         nsid->nsid_pool[nsid->nsid_state] = id;
2535                 }
2536
2537                 /* increment the base pointer into the pool */
2538                 if (nsid->nsid_state == 65535)
2539                         nsid->nsid_state = 0;
2540                 else
2541                         nsid->nsid_state++;
2542         } else {
2543                 /*
2544                  * This is the original Algorithm B
2545                  * j = ((u_long) NSID_SHUFFLE_TABLE_SIZE * nsid_state2) >> 16;
2546                  *
2547                  * We'll perturb it with some random stuff  ...
2548                  */
2549                 j = ((isc_uint32_t) NSID_SHUFFLE_TABLE_SIZE *
2550                      (nsid->nsid_state2 ^ compressed_hash)) >> 16;
2551                 nsid->nsid_state2 = id = nsid->nsid_vtable[j];
2552                 nsid->nsid_state = (((isc_uint32_t) nsid->nsid_a1 * nsid->nsid_state) +
2553                                       nsid->nsid_c1) & 0xFFFF;
2554                 nsid->nsid_vtable[j] = nsid->nsid_state;
2555         }
2556
2557         /* Now lets obfuscate ... */
2558         id = (((isc_uint32_t) nsid->nsid_a2 * id) + nsid->nsid_c2) & 0xFFFF;
2559         id = (((isc_uint32_t) nsid->nsid_a3 * id) + nsid->nsid_c3) & 0xFFFF;
2560
2561         return (id);
2562 }
2563
2564 static isc_result_t
2565 nsid_init(isc_mem_t *mctx, dns_nsid_t *nsid, isc_boolean_t usepool) {
2566         isc_time_t now;
2567         pid_t mypid;
2568         isc_uint16_t a1ndx, a2ndx, a3ndx, c1ndx, c2ndx, c3ndx;
2569         int i;
2570
2571         isc_time_now(&now);
2572         mypid = getpid();
2573
2574         /* Initialize the state */
2575         memset(nsid, 0, sizeof(*nsid));
2576         nsid_hash(&now, sizeof now);
2577         nsid_hash(&mypid, sizeof mypid);
2578
2579         /*
2580          * Select our random number generators and initial seed.
2581          * We could really use more random bits at this point,
2582          * but we'll try to make a silk purse out of a sows ear ...
2583          */
2584         /* generator 1 */
2585         a1ndx = ((isc_uint32_t) NSID_MULT_TABLE_SIZE *
2586                  (nsid_hash_state & 0xFFFF)) >> 16;
2587         nsid->nsid_a1 = nsid_multiplier_table[a1ndx];
2588         c1ndx = (nsid_hash_state >> 9) & 0x7FFF;
2589         nsid->nsid_c1 = 2 * c1ndx + 1;
2590
2591         /* generator 2, distinct from 1 */
2592         a2ndx = ((isc_uint32_t) (NSID_MULT_TABLE_SIZE - 1) *
2593                  ((nsid_hash_state >> 10) & 0xFFFF)) >> 16;
2594         if (a2ndx >= a1ndx)
2595                 a2ndx++;
2596         nsid->nsid_a2 = nsid_multiplier_table[a2ndx];
2597         c2ndx = nsid_hash_state % 32767;
2598         if (c2ndx >= c1ndx)
2599                 c2ndx++;
2600         nsid->nsid_c2 = 2*c2ndx + 1;
2601
2602         /* generator 3, distinct from 1 and 2 */
2603         a3ndx = ((isc_uint32_t) (NSID_MULT_TABLE_SIZE - 2) *
2604                  ((nsid_hash_state >> 20) & 0xFFFF)) >> 16;
2605         if (a3ndx >= a1ndx || a3ndx >= a2ndx)
2606                 a3ndx++;
2607         if (a3ndx >= a1ndx && a3ndx >= a2ndx)
2608                 a3ndx++;
2609         nsid->nsid_a3 = nsid_multiplier_table[a3ndx];
2610         c3ndx = nsid_hash_state % 32766;
2611         if (c3ndx >= c1ndx || c3ndx >= c2ndx)
2612                 c3ndx++;
2613         if (c3ndx >= c1ndx && c3ndx >= c2ndx)
2614                 c3ndx++;
2615         nsid->nsid_c3 = 2*c3ndx + 1;
2616
2617         nsid->nsid_state =
2618                 ((nsid_hash_state >> 16) ^ (nsid_hash_state)) & 0xFFFF;
2619
2620         nsid->nsid_usepool = usepool;
2621         if (nsid->nsid_usepool) {
2622                 nsid->nsid_pool = isc_mem_get(mctx, 0x10000 * sizeof(isc_uint16_t));
2623                 if (nsid->nsid_pool == NULL)
2624                         return (ISC_R_NOMEMORY);
2625                 for (i = 0; ; i++) {
2626                         nsid->nsid_pool[i] = nsid->nsid_state;
2627                         nsid->nsid_state =
2628                                  (((u_long) nsid->nsid_a1 * nsid->nsid_state) +
2629                                    nsid->nsid_c1) & 0xFFFF;
2630                         if (i == 0xFFFF)
2631                                 break;
2632                 }
2633         } else {
2634                 nsid->nsid_vtable = isc_mem_get(mctx, NSID_SHUFFLE_TABLE_SIZE *
2635                                                 (sizeof(isc_uint16_t)) );
2636                 if (nsid->nsid_vtable == NULL)
2637                         return (ISC_R_NOMEMORY);
2638
2639                 for (i = 0; i < NSID_SHUFFLE_TABLE_SIZE; i++) {
2640                         nsid->nsid_vtable[i] = nsid->nsid_state;
2641                         nsid->nsid_state =
2642                                    (((isc_uint32_t) nsid->nsid_a1 * nsid->nsid_state) +
2643                                          nsid->nsid_c1) & 0xFFFF;
2644                 }
2645                 nsid->nsid_state2 = nsid->nsid_state;
2646         }
2647         return (ISC_R_SUCCESS);
2648 }
2649
2650 static void
2651 nsid_destroy(isc_mem_t *mctx, dns_nsid_t *nsid) {
2652         if (nsid->nsid_usepool)
2653                 isc_mem_put(mctx, nsid->nsid_pool,
2654                             0x10000 * sizeof(isc_uint16_t));
2655         else
2656                 isc_mem_put(mctx, nsid->nsid_vtable,
2657                             NSID_SHUFFLE_TABLE_SIZE * (sizeof(isc_uint16_t)) );
2658         memset(nsid, 0, sizeof(*nsid));
2659 }
2660
2661 void
2662 dns_dispatch_hash(void *data, size_t len) {
2663         nsid_hash(data, len);
2664 }