2 * Copyright (C) 2004, 2006 Internet Systems Consortium, Inc. ("ISC")
3 * Copyright (C) 1999-2003 Internet Software Consortium.
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.
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.
18 /* $Id: dispatch.c,v 1.101.2.6.2.13.6.4 2007/06/27 04:19:50 marka Exp $ */
23 #include <sys/types.h>
26 #include <isc/entropy.h>
28 #include <isc/mutex.h>
29 #include <isc/print.h>
30 #include <isc/string.h>
36 #include <dns/dispatch.h>
37 #include <dns/events.h>
39 #include <dns/message.h>
40 #include <dns/portlist.h>
41 #include <dns/tcpmsg.h>
42 #include <dns/types.h>
44 typedef ISC_LIST(dns_dispentry_t) dns_displist_t;
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;
56 typedef struct dns_qid {
58 unsigned int qid_nbuckets; /* hash table size */
59 unsigned int qid_increment; /* id increment on collision */
62 dns_displist_t *qid_table; /* the table itself */
65 struct dns_dispatchmgr {
70 dns_portlist_t *portlist;
72 /* Locked by "lock". */
75 ISC_LIST(dns_dispatch_t) list;
77 /* locked by buffer lock */
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 */
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 */
91 isc_entropy_t *entropy; /* entropy source */
94 #define MGR_SHUTTINGDOWN 0x00000001U
95 #define MGR_IS_SHUTTINGDOWN(l) (((l)->state & MGR_SHUTTINGDOWN) != 0)
97 #define IS_PRIVATE(d) (((d)->attributes & DNS_DISPATCHATTR_PRIVATE) != 0)
99 struct dns_dispentry {
101 dns_dispatch_t *disp;
106 isc_taskaction_t action;
108 isc_boolean_t item_out;
109 ISC_LIST(dns_dispatchevent_t) items;
110 ISC_LINK(dns_dispentry_t) link;
113 #define INVALID_BUCKET (0xffffdead)
115 struct dns_dispatch {
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;
125 /* Locked by mgr->lock. */
126 ISC_LINK(dns_dispatch_t) link;
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,
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 */
146 #define QID_MAGIC ISC_MAGIC('Q', 'i', 'd', ' ')
147 #define VALID_QID(e) ISC_MAGIC_VALID((e), QID_MAGIC)
149 #define RESPONSE_MAGIC ISC_MAGIC('D', 'r', 's', 'p')
150 #define VALID_RESPONSE(e) ISC_MAGIC_VALID((e), RESPONSE_MAGIC)
152 #define DISPATCH_MAGIC ISC_MAGIC('D', 'i', 's', 'p')
153 #define VALID_DISPATCH(e) ISC_MAGIC_VALID((e), DISPATCH_MAGIC)
155 #define DNS_DISPATCHMGR_MAGIC ISC_MAGIC('D', 'M', 'g', 'r')
156 #define VALID_DISPATCHMGR(e) ISC_MAGIC_VALID((e), DNS_DISPATCHMGR_MAGIC)
158 #define DNS_QID(disp) ((disp)->socktype == isc_sockettype_tcp) ? \
159 (disp)->qid : (disp)->mgr->qid
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,
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);
198 #define LVL(x) ISC_LOG_DEBUG(x)
201 mgr_log(dns_dispatchmgr_t *mgr, int level, const char *fmt, ...)
202 ISC_FORMAT_PRINTF(3, 4);
205 mgr_log(dns_dispatchmgr_t *mgr, int level, const char *fmt, ...) {
209 if (! isc_log_wouldlog(dns_lctx, level))
213 vsnprintf(msgbuf, sizeof(msgbuf), fmt, ap);
216 isc_log_write(dns_lctx,
217 DNS_LOGCATEGORY_DISPATCH, DNS_LOGMODULE_DISPATCH,
218 level, "dispatchmgr %p: %s", mgr, msgbuf);
222 dispatch_log(dns_dispatch_t *disp, int level, const char *fmt, ...)
223 ISC_FORMAT_PRINTF(3, 4);
226 dispatch_log(dns_dispatch_t *disp, int level, const char *fmt, ...) {
230 if (! isc_log_wouldlog(dns_lctx, level))
234 vsnprintf(msgbuf, sizeof(msgbuf), fmt, ap);
237 isc_log_write(dns_lctx,
238 DNS_LOGCATEGORY_DISPATCH, DNS_LOGMODULE_DISPATCH,
239 level, "dispatch %p: %s", disp, msgbuf);
243 request_log(dns_dispatch_t *disp, dns_dispentry_t *resp,
244 int level, const char *fmt, ...)
245 ISC_FORMAT_PRINTF(4, 5);
248 request_log(dns_dispatch_t *disp, dns_dispentry_t *resp,
249 int level, const char *fmt, ...)
255 if (! isc_log_wouldlog(dns_lctx, level))
259 vsnprintf(msgbuf, sizeof(msgbuf), fmt, ap);
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,
269 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DISPATCH,
270 DNS_LOGMODULE_DISPATCH, level,
271 "dispatch %p req/resp %p: %s", disp, resp,
277 * Return an unpredictable message ID.
279 static dns_messageid_t
280 dns_randomid(dns_nsid_t *nsid) {
283 id = nsid_next(nsid);
285 return ((dns_messageid_t)id);
289 * Return a hash of the destination and message id.
292 dns_hash(dns_qid_t *qid, isc_sockaddr_t *dest, dns_messageid_t id) {
295 ret = isc_sockaddr_hash(dest, ISC_TRUE);
297 ret %= qid->qid_nbuckets;
299 INSIST(ret < qid->qid_nbuckets);
305 * Find the first entry in 'qid'. Returns NULL if there are no entries.
307 static dns_dispentry_t *
308 linear_first(dns_qid_t *qid) {
309 dns_dispentry_t *ret;
314 while (bucket < qid->qid_nbuckets) {
315 ret = ISC_LIST_HEAD(qid->qid_table[bucket]);
325 * Find the next entry after 'resp' in 'qid'. Return NULL if there are
328 static dns_dispentry_t *
329 linear_next(dns_qid_t *qid, dns_dispentry_t *resp) {
330 dns_dispentry_t *ret;
333 ret = ISC_LIST_NEXT(resp, link);
337 bucket = resp->bucket;
339 while (bucket < qid->qid_nbuckets) {
340 ret = ISC_LIST_HEAD(qid->qid_table[bucket]);
350 * The dispatch must be locked.
353 destroy_disp_ok(dns_dispatch_t *disp)
355 if (disp->refcount != 0)
358 if (disp->recv_pending != 0)
361 if (disp->shutting_down == 0)
369 * Called when refcount reaches 0 (and safe to destroy).
371 * The dispatcher must not be locked.
372 * The manager must be locked.
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;
380 INSIST(event->ev_type == DNS_EVENT_DISPATCHCONTROL);
384 disp = event->ev_arg;
388 ISC_LIST_UNLINK(mgr->list, disp, link);
390 dispatch_log(disp, LVL(90),
391 "shutting down; detaching from sock %p, task %p",
392 disp->socket, disp->task);
394 isc_socket_detach(&disp->socket);
395 isc_task_detach(&disp->task);
396 isc_event_free(&event);
398 dispatch_free(&disp);
400 killmgr = destroy_mgr_ok(mgr);
408 * Find an entry for query ID 'id' and socket address 'dest' in 'qid'.
409 * Return NULL if no such entry exists.
411 static dns_dispentry_t *
412 bucket_search(dns_qid_t *qid, isc_sockaddr_t *dest, dns_messageid_t id,
415 dns_dispentry_t *res;
417 REQUIRE(bucket < qid->qid_nbuckets);
419 res = ISC_LIST_HEAD(qid->qid_table[bucket]);
421 while (res != NULL) {
422 if ((res->id == id) && isc_sockaddr_equal(dest, &res->host))
424 res = ISC_LIST_NEXT(res, link);
431 free_buffer(dns_dispatch_t *disp, void *buf, unsigned int len) {
432 INSIST(buf != NULL && len != 0);
435 switch (disp->socktype) {
436 case isc_sockettype_tcp:
437 INSIST(disp->tcpbuffers > 0);
439 isc_mem_put(disp->mgr->mctx, buf, len);
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);
456 allocate_udp_buffer(dns_dispatch_t *disp) {
459 LOCK(&disp->mgr->buffer_lock);
460 temp = isc_mempool_get(disp->mgr->bpool);
463 disp->mgr->buffers++;
464 UNLOCK(&disp->mgr->buffer_lock);
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;
478 isc_mempool_put(disp->mgr->epool, ev);
481 static inline dns_dispatchevent_t *
482 allocate_event(dns_dispatch_t *disp) {
483 dns_dispatchevent_t *ev;
485 ev = isc_mempool_get(disp->mgr->epool);
488 ISC_EVENT_INIT(ev, sizeof(*ev), 0, NULL, 0,
489 NULL, NULL, NULL, NULL, NULL);
497 * If I/O result == CANCELED or error, free the buffer.
499 * If query, free the buffer, restart.
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.
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;
516 dns_dispentry_t *resp;
517 dns_dispatchevent_t *rev;
519 isc_boolean_t killit;
520 isc_boolean_t queue_response;
521 dns_dispatchmgr_t *mgr;
523 isc_netaddr_t netaddr;
533 dispatch_log(disp, LVL(90),
534 "got packet: requests %d, buffers %d, recvs %d",
535 disp->requests, disp->mgr->buffers, disp->recv_pending);
537 if (ev->ev_type == ISC_SOCKEVENT_RECVDONE) {
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.
543 INSIST(disp->recv_pending != 0);
544 disp->recv_pending = 0;
547 if (disp->shutting_down) {
549 * This dispatcher is shutting down.
551 free_buffer(disp, ev->region.base, ev->region.length);
553 isc_event_free(&ev_in);
556 killit = destroy_disp_ok(disp);
559 isc_task_send(disp->task, &disp->ctlevent);
564 if (ev->result != ISC_R_SUCCESS) {
565 free_buffer(disp, ev->region.base, ev->region.length);
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));
573 isc_event_free(&ev_in);
578 * If this is from a blackholed address, drop it.
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 &&
586 if (isc_log_wouldlog(dns_lctx, LVL(10))) {
587 char netaddrstr[ISC_NETADDR_FORMATSIZE];
588 isc_netaddr_format(&netaddr, netaddrstr,
590 dispatch_log(disp, LVL(10),
591 "blackholed packet from %s",
594 free_buffer(disp, ev->region.base, ev->region.length);
599 * Peek into the buffer to see what we can see.
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");
610 dispatch_log(disp, LVL(92),
611 "got valid DNS message header, /QR %c, id %u",
612 ((flags & DNS_MESSAGEFLAG_QR) ? '1' : '0'), id);
615 * Look at flags. If query, drop it. If response,
616 * look to see where it goes.
618 queue_response = ISC_FALSE;
619 if ((flags & DNS_MESSAGEFLAG_QR) == 0) {
621 free_buffer(disp, ev->region.base, ev->region.length);
625 dns_dispatch_hash(&ev->timestamp, sizeof(&ev->timestamp));
626 dns_dispatch_hash(ev->region.base, ev->region.length);
629 bucket = dns_hash(qid, &ev->address, id);
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"));
637 free_buffer(disp, ev->region.base, ev->region.length);
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.
646 if (disp != resp->disp) {
651 * Check that the socket types and ports match.
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);
661 * If both dispatches are bound to an address then fail as
662 * the addresses can't be equal (enforced by the IP stack).
664 * Note under Linux a packet can be sent out via IPv4 socket
665 * and the response be received via a IPv6 socket.
667 * Requests sent out via IPv6 should always come back in
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);
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);
684 queue_response = resp->item_out;
685 rev = allocate_event(resp->disp);
687 free_buffer(disp, ev->region.base, ev->region.length);
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.
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;
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);
706 ISC_EVENT_INIT(rev, sizeof(*rev), 0, NULL,
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,
713 resp->item_out = ISC_TRUE;
714 isc_task_send(resp->task, ISC_EVENT_PTR(&rev));
720 * Restart recv() to get the next packet.
727 isc_event_free(&ev_in);
733 * If I/O result == CANCELED, EOF, or error, notify everyone as the
734 * various queues drain.
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.
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;
752 dns_dispentry_t *resp;
753 dns_dispatchevent_t *rev;
755 isc_boolean_t killit;
756 isc_boolean_t queue_response;
759 char buf[ISC_SOCKADDR_FORMATSIZE];
763 REQUIRE(VALID_DISPATCH(disp));
767 dispatch_log(disp, LVL(90),
768 "got TCP packet: requests %d, buffers %d, recvs %d",
769 disp->requests, disp->tcpbuffers, disp->recv_pending);
773 INSIST(disp->recv_pending != 0);
774 disp->recv_pending = 0;
776 if (disp->refcount == 0) {
778 * This dispatcher is shutting down. Force cancelation.
780 tcpmsg->result = ISC_R_CANCELED;
783 if (tcpmsg->result != ISC_R_SUCCESS) {
784 switch (tcpmsg->result) {
789 dispatch_log(disp, LVL(90), "shutting down on EOF");
793 case ISC_R_CONNECTIONRESET:
794 level = ISC_LOG_INFO;
798 level = ISC_LOG_ERROR;
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));
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().
813 isc_event_free(&ev_in);
815 disp->shutting_down = 1;
816 disp->shutdown_why = tcpmsg->result;
819 * If the recv() was canceled pass the word on.
821 killit = destroy_disp_ok(disp);
824 isc_task_send(disp->task, &disp->ctlevent);
828 dispatch_log(disp, LVL(90), "result %d, length == %d, addr = %p",
830 tcpmsg->buffer.length, tcpmsg->buffer.base);
833 * Peek into the buffer to see what we can see.
835 dres = dns_message_peekheader(&tcpmsg->buffer, &id, &flags);
836 if (dres != ISC_R_SUCCESS) {
837 dispatch_log(disp, LVL(10), "got garbage packet");
841 dispatch_log(disp, LVL(92),
842 "got valid DNS message header, /QR %c, id %u",
843 ((flags & DNS_MESSAGEFLAG_QR) ? '1' : '0'), id);
846 * Allocate an event to send to the query or response client, and
847 * allocate a new buffer for our use.
851 * Look at flags. If query, drop it. If response,
852 * look to see where it goes.
854 queue_response = ISC_FALSE;
855 if ((flags & DNS_MESSAGEFLAG_QR) == 0) {
862 dns_dispatch_hash(tcpmsg->buffer.base, tcpmsg->buffer.length);
867 bucket = dns_hash(qid, &tcpmsg->address, id);
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"));
876 queue_response = resp->item_out;
877 rev = allocate_event(disp);
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.
886 dns_tcpmsg_keepbuffer(tcpmsg, &rev->buffer);
888 rev->result = ISC_R_SUCCESS;
890 rev->addr = tcpmsg->address;
891 if (queue_response) {
892 ISC_LIST_APPEND(resp->items, rev, ev_link);
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,
900 resp->item_out = ISC_TRUE;
901 isc_task_send(resp->task, ISC_EVENT_PTR(&rev));
907 * Restart recv() to get the next packet.
914 isc_event_free(&ev_in);
918 * disp must be locked.
921 startrecv(dns_dispatch_t *disp) {
925 if (disp->shutting_down == 1)
928 if ((disp->attributes & DNS_DISPATCHATTR_NOLISTEN) != 0)
931 if (disp->recv_pending != 0)
934 if (disp->mgr->buffers >= disp->mgr->maxbuffers)
937 switch (disp->socktype) {
939 * UDP reads are always maximal.
941 case isc_sockettype_udp:
942 region.length = disp->mgr->buffersize;
943 region.base = allocate_udp_buffer(disp);
944 if (region.base == NULL)
946 res = isc_socket_recv(disp->socket, ®ion, 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;
955 INSIST(disp->recv_pending == 0);
956 disp->recv_pending = 1;
959 case isc_sockettype_tcp:
960 res = dns_tcpmsg_readmessage(&disp->tcpmsg, disp->task,
962 if (res != ISC_R_SUCCESS) {
963 disp->shutdown_why = res;
964 disp->shutting_down = 1;
968 INSIST(disp->recv_pending == 0);
969 disp->recv_pending = 1;
975 * Mgr must be locked when calling this function.
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))
988 if (!ISC_LIST_EMPTY(mgr->list))
990 if (isc_mempool_getallocated(mgr->epool) != 0)
992 if (isc_mempool_getallocated(mgr->rpool) != 0)
994 if (isc_mempool_getallocated(mgr->dpool) != 0)
1001 * Mgr must be unlocked when calling this function.
1004 destroy_mgr(dns_dispatchmgr_t **mgrp) {
1006 dns_dispatchmgr_t *mgr;
1015 DESTROYLOCK(&mgr->lock);
1018 isc_mempool_destroy(&mgr->epool);
1019 isc_mempool_destroy(&mgr->rpool);
1020 isc_mempool_destroy(&mgr->dpool);
1021 isc_mempool_destroy(&mgr->bpool);
1023 DESTROYLOCK(&mgr->pool_lock);
1025 if (mgr->entropy != NULL)
1026 isc_entropy_detach(&mgr->entropy);
1027 if (mgr->qid != NULL)
1028 qid_destroy(mctx, &mgr->qid);
1030 DESTROYLOCK(&mgr->buffer_lock);
1032 if (mgr->blackhole != NULL)
1033 dns_acl_detach(&mgr->blackhole);
1035 if (mgr->portlist != NULL)
1036 dns_portlist_detach(&mgr->portlist);
1038 isc_mem_put(mctx, mgr, sizeof(dns_dispatchmgr_t));
1039 isc_mem_detach(&mctx);
1043 create_socket(isc_socketmgr_t *mgr, isc_sockaddr_t *local,
1044 isc_socket_t **sockp)
1047 isc_result_t result;
1050 result = isc_socket_create(mgr, isc_sockaddr_pf(local),
1051 isc_sockettype_udp, &sock);
1052 if (result != ISC_R_SUCCESS)
1055 #ifndef ISC_ALLOW_MAPPED
1056 isc_socket_ipv6only(sock, ISC_TRUE);
1058 result = isc_socket_bind(sock, local);
1059 if (result != ISC_R_SUCCESS) {
1060 isc_socket_detach(&sock);
1065 return (ISC_R_SUCCESS);
1073 dns_dispatchmgr_create(isc_mem_t *mctx, isc_entropy_t *entropy,
1074 dns_dispatchmgr_t **mgrp)
1076 dns_dispatchmgr_t *mgr;
1077 isc_result_t result;
1079 REQUIRE(mctx != NULL);
1080 REQUIRE(mgrp != NULL && *mgrp == NULL);
1082 mgr = isc_mem_get(mctx, sizeof(dns_dispatchmgr_t));
1084 return (ISC_R_NOMEMORY);
1087 isc_mem_attach(mctx, &mgr->mctx);
1089 mgr->blackhole = NULL;
1090 mgr->portlist = NULL;
1092 result = isc_mutex_init(&mgr->lock);
1093 if (result != ISC_R_SUCCESS)
1096 result = isc_mutex_init(&mgr->buffer_lock);
1097 if (result != ISC_R_SUCCESS)
1100 result = isc_mutex_init(&mgr->pool_lock);
1101 if (result != ISC_R_SUCCESS)
1102 goto kill_buffer_lock;
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;
1112 if (isc_mempool_create(mgr->mctx, sizeof(dns_dispentry_t),
1113 &mgr->rpool) != ISC_R_SUCCESS) {
1114 result = ISC_R_NOMEMORY;
1119 if (isc_mempool_create(mgr->mctx, sizeof(dns_dispatch_t),
1120 &mgr->dpool) != ISC_R_SUCCESS) {
1121 result = ISC_R_NOMEMORY;
1125 isc_mempool_setname(mgr->epool, "dispmgr_epool");
1126 isc_mempool_setfreemax(mgr->epool, 1024);
1127 isc_mempool_associatelock(mgr->epool, &mgr->pool_lock);
1129 isc_mempool_setname(mgr->rpool, "dispmgr_rpool");
1130 isc_mempool_setfreemax(mgr->rpool, 1024);
1131 isc_mempool_associatelock(mgr->rpool, &mgr->pool_lock);
1133 isc_mempool_setname(mgr->dpool, "dispmgr_dpool");
1134 isc_mempool_setfreemax(mgr->dpool, 1024);
1135 isc_mempool_associatelock(mgr->dpool, &mgr->pool_lock);
1138 mgr->buffersize = 0;
1139 mgr->maxbuffers = 0;
1141 mgr->entropy = NULL;
1144 ISC_LIST_INIT(mgr->list);
1145 mgr->magic = DNS_DISPATCHMGR_MAGIC;
1147 if (entropy != NULL)
1148 isc_entropy_attach(entropy, &mgr->entropy);
1151 return (ISC_R_SUCCESS);
1154 isc_mempool_destroy(&mgr->rpool);
1156 isc_mempool_destroy(&mgr->epool);
1158 DESTROYLOCK(&mgr->pool_lock);
1160 DESTROYLOCK(&mgr->buffer_lock);
1162 DESTROYLOCK(&mgr->lock);
1164 isc_mem_put(mctx, mgr, sizeof(dns_dispatchmgr_t));
1165 isc_mem_detach(&mctx);
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);
1179 dns_dispatchmgr_getblackhole(dns_dispatchmgr_t *mgr) {
1180 REQUIRE(VALID_DISPATCHMGR(mgr));
1181 return (mgr->blackhole);
1185 dns_dispatchmgr_setblackportlist(dns_dispatchmgr_t *mgr,
1186 dns_portlist_t *portlist)
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);
1196 dns_dispatchmgr_getblackportlist(dns_dispatchmgr_t *mgr) {
1197 REQUIRE(VALID_DISPATCHMGR(mgr));
1198 return (mgr->portlist);
1202 dns_dispatchmgr_setudp(dns_dispatchmgr_t *mgr,
1203 unsigned int buffersize, unsigned int maxbuffers,
1204 unsigned int buckets, unsigned int increment)
1206 isc_result_t result;
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);
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.
1221 * Note that if limits are placed on anything here, we use one
1222 * event internally, so the actual limit should be "wanted + 1."
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);
1238 if (isc_mempool_create(mgr->mctx, buffersize,
1239 &mgr->bpool) != ISC_R_SUCCESS) {
1240 return (ISC_R_NOMEMORY);
1243 isc_mempool_setname(mgr->bpool, "dispmgr_bpool");
1244 isc_mempool_setmaxalloc(mgr->bpool, maxbuffers);
1245 isc_mempool_associatelock(mgr->bpool, &mgr->pool_lock);
1247 result = qid_allocate(mgr, buckets, increment, ISC_TRUE, &mgr->qid);
1248 if (result != ISC_R_SUCCESS)
1251 mgr->buffersize = buffersize;
1252 mgr->maxbuffers = maxbuffers;
1253 UNLOCK(&mgr->buffer_lock);
1254 return (ISC_R_SUCCESS);
1257 isc_mempool_destroy(&mgr->bpool);
1258 UNLOCK(&mgr->buffer_lock);
1259 return (ISC_R_NOMEMORY);
1263 dns_dispatchmgr_destroy(dns_dispatchmgr_t **mgrp) {
1264 dns_dispatchmgr_t *mgr;
1265 isc_boolean_t killit;
1267 REQUIRE(mgrp != NULL);
1268 REQUIRE(VALID_DISPATCHMGR(*mgrp));
1274 mgr->state |= MGR_SHUTTINGDOWN;
1276 killit = destroy_mgr_ok(mgr);
1279 mgr_log(mgr, LVL(90), "destroy: killit=%d", killit);
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;
1290 if (mgr->portlist == NULL)
1293 result = isc_socket_getsockname(sock, &sockaddr);
1294 if (result != ISC_R_SUCCESS)
1297 if (mgr->portlist != NULL &&
1298 dns_portlist_match(mgr->portlist, isc_sockaddr_pf(&sockaddr),
1299 isc_sockaddr_getport(&sockaddr)))
1304 #define ATTRMATCH(_a1, _a2, _mask) (((_a1) & (_mask)) == ((_a2) & (_mask)))
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;
1315 * Don't match wildcard ports against newly blacklisted ports.
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))
1324 * Check if we match the binding <address,port>.
1325 * Wildcard ports match/fail here.
1327 if (isc_sockaddr_equal(&disp->local, addr))
1329 if (isc_sockaddr_getport(addr) == 0)
1333 * Check if we match a bound wildcard port <address,port>.
1335 if (!isc_sockaddr_eqaddr(&disp->local, addr))
1337 result = isc_socket_getsockname(disp->socket, &sockaddr);
1338 if (result != ISC_R_SUCCESS)
1341 return (isc_sockaddr_equal(&sockaddr, addr));
1345 * Requires mgr be locked.
1347 * No dispatcher can be locked by this thread when calling this function.
1351 * If a matching dispatcher is found, it is locked after this function
1352 * returns, and must be unlocked by the caller.
1355 dispatch_find(dns_dispatchmgr_t *mgr, isc_sockaddr_t *local,
1356 unsigned int attributes, unsigned int mask,
1357 dns_dispatch_t **dispp)
1359 dns_dispatch_t *disp;
1360 isc_result_t result;
1363 * Make certain that we will not match a private dispatch.
1365 attributes &= ~DNS_DISPATCHATTR_PRIVATE;
1366 mask |= DNS_DISPATCHATTR_PRIVATE;
1368 disp = ISC_LIST_HEAD(mgr->list);
1369 while (disp != NULL) {
1371 if ((disp->shutting_down == 0)
1372 && ATTRMATCH(disp->attributes, attributes, mask)
1373 && local_addr_match(disp, local))
1375 UNLOCK(&disp->lock);
1376 disp = ISC_LIST_NEXT(disp, link);
1380 result = ISC_R_NOTFOUND;
1385 result = ISC_R_SUCCESS;
1392 qid_allocate(dns_dispatchmgr_t *mgr, unsigned int buckets,
1393 unsigned int increment, isc_boolean_t usepool, dns_qid_t **qidp)
1398 REQUIRE(VALID_DISPATCHMGR(mgr));
1399 REQUIRE(buckets < 2097169); /* next prime > 65536 * 32 */
1400 REQUIRE(increment > buckets);
1401 REQUIRE(qidp != NULL && *qidp == NULL);
1403 qid = isc_mem_get(mgr->mctx, sizeof(*qid));
1405 return (ISC_R_NOMEMORY);
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);
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);
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);
1430 for (i = 0; i < buckets; i++)
1431 ISC_LIST_INIT(qid->qid_table[i]);
1433 qid->qid_nbuckets = buckets;
1434 qid->qid_increment = increment;
1435 qid->magic = QID_MAGIC;
1437 return (ISC_R_SUCCESS);
1441 qid_destroy(isc_mem_t *mctx, dns_qid_t **qidp) {
1444 REQUIRE(qidp != NULL);
1447 REQUIRE(VALID_QID(qid));
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));
1459 * Allocate and set important limits.
1462 dispatch_allocate(dns_dispatchmgr_t *mgr, unsigned int maxrequests,
1463 dns_dispatch_t **dispp)
1465 dns_dispatch_t *disp;
1468 REQUIRE(VALID_DISPATCHMGR(mgr));
1469 REQUIRE(dispp != NULL && *dispp == NULL);
1472 * Set up the dispatcher, mostly. Don't bother setting some of
1473 * the options that are controlled by tcp vs. udp, etc.
1476 disp = isc_mempool_get(mgr->dpool);
1478 return (ISC_R_NOMEMORY);
1482 disp->maxrequests = maxrequests;
1483 disp->attributes = 0;
1484 ISC_LINK_INIT(disp, link);
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;
1494 disp->tcpbuffers = 0;
1497 if (isc_mutex_init(&disp->lock) != ISC_R_SUCCESS) {
1498 res = ISC_R_UNEXPECTED;
1499 UNEXPECTED_ERROR(__FILE__, __LINE__, "isc_mutex_init failed");
1503 disp->failsafe_ev = allocate_event(disp);
1504 if (disp->failsafe_ev == NULL) {
1505 res = ISC_R_NOMEMORY;
1509 disp->magic = DISPATCH_MAGIC;
1512 return (ISC_R_SUCCESS);
1518 DESTROYLOCK(&disp->lock);
1520 isc_mempool_put(mgr->dpool, disp);
1527 * MUST be unlocked, and not used by anthing.
1530 dispatch_free(dns_dispatch_t **dispp)
1532 dns_dispatch_t *disp;
1533 dns_dispatchmgr_t *mgr;
1535 REQUIRE(VALID_DISPATCH(*dispp));
1540 REQUIRE(VALID_DISPATCHMGR(mgr));
1542 if (disp->tcpmsg_valid) {
1543 dns_tcpmsg_invalidate(&disp->tcpmsg);
1544 disp->tcpmsg_valid = 0;
1547 INSIST(disp->tcpbuffers == 0);
1548 INSIST(disp->requests == 0);
1549 INSIST(disp->recv_pending == 0);
1551 isc_mempool_put(mgr->epool, disp->failsafe_ev);
1552 disp->failsafe_ev = NULL;
1554 if (disp->qid != NULL)
1555 qid_destroy(mgr->mctx, &disp->qid);
1557 DESTROYLOCK(&disp->lock);
1559 isc_mempool_put(mgr->dpool, disp);
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)
1569 isc_result_t result;
1570 dns_dispatch_t *disp;
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);
1580 attributes |= DNS_DISPATCHATTR_PRIVATE; /* XXXMLG */
1585 * dispatch_allocate() checks mgr for us.
1586 * qid_allocate() checks buckets and increment for us.
1589 result = dispatch_allocate(mgr, maxrequests, &disp);
1590 if (result != ISC_R_SUCCESS) {
1595 result = qid_allocate(mgr, buckets, increment, ISC_FALSE, &disp->qid);
1596 if (result != ISC_R_SUCCESS)
1597 goto deallocate_dispatch;
1599 disp->socktype = isc_sockettype_tcp;
1600 disp->socket = NULL;
1601 isc_socket_attach(sock, &disp->socket);
1604 result = isc_task_create(taskmgr, 0, &disp->task);
1605 if (result != ISC_R_SUCCESS)
1608 disp->ctlevent = isc_event_allocate(mgr->mctx, disp,
1609 DNS_EVENT_DISPATCHCONTROL,
1611 sizeof(isc_event_t));
1612 if (disp->ctlevent == NULL)
1615 isc_task_setname(disp->task, "tcpdispatch", disp);
1617 dns_tcpmsg_init(mgr->mctx, disp->socket, &disp->tcpmsg);
1618 disp->tcpmsg_valid = 1;
1620 disp->attributes = attributes;
1623 * Append it to the dispatcher list.
1625 ISC_LIST_APPEND(mgr->list, disp, link);
1628 mgr_log(mgr, LVL(90), "created TCP dispatcher %p", disp);
1629 dispatch_log(disp, LVL(90), "created task %p", disp->task);
1633 return (ISC_R_SUCCESS);
1639 isc_task_detach(&disp->task);
1641 isc_socket_detach(&disp->socket);
1642 deallocate_dispatch:
1643 dispatch_free(&disp);
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)
1659 isc_result_t result;
1660 dns_dispatch_t *disp;
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);
1673 result = dns_dispatchmgr_setudp(mgr, buffersize, maxbuffers,
1674 buckets, increment);
1675 if (result != ISC_R_SUCCESS)
1681 * First, see if we have a dispatcher that matches.
1684 result = dispatch_find(mgr, localaddr, attributes, mask, &disp);
1685 if (result == ISC_R_SUCCESS) {
1688 if (disp->maxrequests < maxrequests)
1689 disp->maxrequests = maxrequests;
1691 if ((disp->attributes & DNS_DISPATCHATTR_NOLISTEN) == 0 &&
1692 (attributes & DNS_DISPATCHATTR_NOLISTEN) != 0)
1694 disp->attributes |= DNS_DISPATCHATTR_NOLISTEN;
1695 if (disp->recv_pending != 0)
1696 isc_socket_cancel(disp->socket, disp->task,
1697 ISC_SOCKCANCEL_RECV);
1700 UNLOCK(&disp->lock);
1705 return (ISC_R_SUCCESS);
1711 result = dispatch_createudp(mgr, sockmgr, taskmgr, localaddr,
1712 maxrequests, attributes, &disp);
1713 if (result != ISC_R_SUCCESS) {
1720 return (ISC_R_SUCCESS);
1724 * mgr should be locked.
1727 #ifndef DNS_DISPATCH_HELD
1728 #define DNS_DISPATCH_HELD 20U
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)
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;
1746 * dispatch_allocate() checks mgr for us.
1749 result = dispatch_allocate(mgr, maxrequests, &disp);
1750 if (result != ISC_R_SUCCESS)
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.
1758 memset(held, 0, sizeof(held));
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]);
1768 if (i == DNS_DISPATCH_HELD)
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 ?
1775 result = ISC_R_FAILURE;
1776 goto deallocate_dispatch;
1781 disp->socktype = isc_sockettype_udp;
1782 disp->socket = sock;
1783 disp->local = *localaddr;
1786 result = isc_task_create(taskmgr, 0, &disp->task);
1787 if (result != ISC_R_SUCCESS)
1790 disp->ctlevent = isc_event_allocate(mgr->mctx, disp,
1791 DNS_EVENT_DISPATCHCONTROL,
1793 sizeof(isc_event_t));
1794 if (disp->ctlevent == NULL)
1797 isc_task_setname(disp->task, "udpdispatch", disp);
1799 attributes &= ~DNS_DISPATCHATTR_TCP;
1800 attributes |= DNS_DISPATCHATTR_UDP;
1801 disp->attributes = attributes;
1804 * Append it to the dispatcher list.
1806 ISC_LIST_APPEND(mgr->list, disp, link);
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);
1820 isc_task_detach(&disp->task);
1822 isc_socket_detach(&disp->socket);
1823 deallocate_dispatch:
1824 dispatch_free(&disp);
1826 for (i = 0; i < DNS_DISPATCH_HELD; i++)
1827 if (held[i] != NULL)
1828 isc_socket_detach(&held[i]);
1833 dns_dispatch_attach(dns_dispatch_t *disp, dns_dispatch_t **dispp) {
1834 REQUIRE(VALID_DISPATCH(disp));
1835 REQUIRE(dispp != NULL && *dispp == NULL);
1839 UNLOCK(&disp->lock);
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.
1852 dns_dispatch_detach(dns_dispatch_t **dispp) {
1853 dns_dispatch_t *disp;
1854 isc_boolean_t killit;
1856 REQUIRE(dispp != NULL && VALID_DISPATCH(*dispp));
1863 INSIST(disp->refcount > 0);
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;
1873 dispatch_log(disp, LVL(90), "detach: refcount %d", disp->refcount);
1875 killit = destroy_disp_ok(disp);
1876 UNLOCK(&disp->lock);
1878 isc_task_send(disp->task, &disp->ctlevent);
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)
1886 dns_dispentry_t *res;
1887 unsigned int bucket;
1893 REQUIRE(VALID_DISPATCH(disp));
1894 REQUIRE(task != NULL);
1895 REQUIRE(dest != NULL);
1896 REQUIRE(resp != NULL && *resp == NULL);
1897 REQUIRE(idp != NULL);
1901 if (disp->shutting_down == 1) {
1902 UNLOCK(&disp->lock);
1903 return (ISC_R_SHUTTINGDOWN);
1906 if (disp->requests >= disp->maxrequests) {
1907 UNLOCK(&disp->lock);
1908 return (ISC_R_QUOTA);
1912 * Try somewhat hard to find an unique ID.
1914 qid = DNS_QID(disp);
1916 id = dns_randomid(&qid->nsid);
1917 bucket = dns_hash(qid, dest, id);
1919 for (i = 0; i < 64; i++) {
1920 if (bucket_search(qid, dest, id, bucket) == NULL) {
1924 id += qid->qid_increment;
1926 bucket = dns_hash(qid, dest, id);
1931 UNLOCK(&disp->lock);
1932 return (ISC_R_NOMORE);
1935 res = isc_mempool_get(disp->mgr->rpool);
1938 UNLOCK(&disp->lock);
1939 return (ISC_R_NOMEMORY);
1945 isc_task_attach(task, &res->task);
1948 res->bucket = bucket;
1950 res->action = action;
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);
1959 request_log(disp, res, LVL(90),
1960 "attached to task %p", res->task);
1962 if (((disp->attributes & DNS_DISPATCHATTR_UDP) != 0) ||
1963 ((disp->attributes & DNS_DISPATCHATTR_CONNECTED) != 0))
1966 UNLOCK(&disp->lock);
1971 return (ISC_R_SUCCESS);
1975 dns_dispatch_starttcp(dns_dispatch_t *disp) {
1977 REQUIRE(VALID_DISPATCH(disp));
1979 dispatch_log(disp, LVL(90), "starttcp %p", disp->task);
1982 disp->attributes |= DNS_DISPATCHATTR_CONNECTED;
1984 UNLOCK(&disp->lock);
1988 dns_dispatch_removeresponse(dns_dispentry_t **resp,
1989 dns_dispatchevent_t **sockevent)
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;
1998 isc_eventlist_t events;
2001 REQUIRE(resp != NULL);
2002 REQUIRE(VALID_RESPONSE(*resp));
2008 REQUIRE(VALID_DISPATCH(disp));
2010 REQUIRE(VALID_DISPATCHMGR(mgr));
2012 qid = DNS_QID(disp);
2014 if (sockevent != NULL) {
2015 REQUIRE(*sockevent != NULL);
2024 INSIST(disp->requests > 0);
2026 INSIST(disp->refcount > 0);
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;
2036 bucket = res->bucket;
2039 ISC_LIST_UNLINK(qid->qid_table[bucket], res, link);
2042 if (ev == NULL && res->item_out) {
2044 * We've posted our event, but the caller hasn't gotten it
2045 * yet. Take it back.
2047 ISC_LIST_INIT(events);
2048 n = isc_task_unsend(res->task, res, DNS_EVENT_DISPATCH,
2051 * We had better have gotten it back.
2054 ev = (dns_dispatchevent_t *)ISC_LIST_HEAD(events);
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);
2065 request_log(disp, res, LVL(90), "detaching from task %p", res->task);
2066 isc_task_detach(&res->task);
2069 * Free any buffered requests as well
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);
2080 isc_mempool_put(disp->mgr->rpool, res);
2081 if (disp->shutting_down == 1)
2086 killit = destroy_disp_ok(disp);
2087 UNLOCK(&disp->lock);
2089 isc_task_send(disp->task, &disp->ctlevent);
2093 do_cancel(dns_dispatch_t *disp) {
2094 dns_dispatchevent_t *ev;
2095 dns_dispentry_t *resp;
2098 if (disp->shutdown_out == 1)
2101 qid = DNS_QID(disp);
2104 * Search for the first response handler without packets outstanding.
2107 for (resp = linear_first(qid);
2108 resp != NULL && resp->item_out != ISC_FALSE;
2110 resp = linear_next(qid, resp);
2112 * No one to send the cancel event to, so nothing to do.
2118 * Send the shutdown failsafe event to this resp.
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",
2130 resp->item_out = ISC_TRUE;
2131 isc_task_send(resp->task, ISC_EVENT_PTR(&ev));
2137 dns_dispatch_getsocket(dns_dispatch_t *disp) {
2138 REQUIRE(VALID_DISPATCH(disp));
2140 return (disp->socket);
2144 dns_dispatch_getlocaladdress(dns_dispatch_t *disp, isc_sockaddr_t *addrp) {
2146 REQUIRE(VALID_DISPATCH(disp));
2147 REQUIRE(addrp != NULL);
2149 if (disp->socktype == isc_sockettype_udp) {
2150 *addrp = disp->local;
2151 return (ISC_R_SUCCESS);
2153 return (ISC_R_NOTIMPLEMENTED);
2157 dns_dispatch_cancel(dns_dispatch_t *disp) {
2158 REQUIRE(VALID_DISPATCH(disp));
2162 if (disp->shutting_down == 1) {
2163 UNLOCK(&disp->lock);
2167 disp->shutdown_why = ISC_R_CANCELED;
2168 disp->shutting_down = 1;
2171 UNLOCK(&disp->lock);
2177 dns_dispatch_changeattributes(dns_dispatch_t *disp,
2178 unsigned int attributes, unsigned int mask)
2180 REQUIRE(VALID_DISPATCH(disp));
2183 * Should check for valid attributes here!
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;
2193 } else if ((disp->attributes & DNS_DISPATCHATTR_NOLISTEN)
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);
2203 disp->attributes &= ~mask;
2204 disp->attributes |= (attributes & mask);
2205 UNLOCK(&disp->lock);
2209 dns_dispatch_importrecv(dns_dispatch_t *disp, isc_event_t *event) {
2211 isc_socketevent_t *sevent, *newsevent;
2213 REQUIRE(VALID_DISPATCH(disp));
2214 REQUIRE((disp->attributes & DNS_DISPATCHATTR_NOLISTEN) != 0);
2215 REQUIRE(event != NULL);
2217 sevent = (isc_socketevent_t *)event;
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)
2227 buf = allocate_udp_buffer(disp);
2229 isc_event_free(ISC_EVENT_PTR(&newsevent));
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;
2242 isc_task_send(disp->task, ISC_EVENT_PTR(&newsevent));
2247 dns_dispatchmgr_dump(dns_dispatchmgr_t *mgr) {
2248 dns_dispatch_t *disp;
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);
2261 * Allow the user to pick one of two ID randomization algorithms.
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
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.
2275 * Is between 0.01 and 0.99 times the modulus as specified by
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.
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.
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.
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.
2297 * Our adaptatation of Algorithm B mixes the hash state which has
2298 * captured various random events into the shuffler to perturb the
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
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
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.
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
2328 #define NSID_SHUFFLE_TABLE_SIZE 100 /* Suggested by Knuth */
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.
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)))
2340 static isc_uint32_t nsid_hash_state;
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
2347 nsid_hash(void *data, size_t len) {
2348 unsigned char *p = data;
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
2359 * We don't care about locking access to nsid_hash_state.
2360 * In fact races make the result even more non deteministic.
2362 while (len-- > 0U) {
2363 nsid_hash_state = NSID_HASHROTATE(nsid_hash_state);
2364 nsid_hash_state += *p++;
2369 * Table of good linear congruential multipliers for modulus 2^16
2370 * in order of increasing serial correlation bounds (so trim from
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
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
2517 nsid_next(dns_nsid_t *nsid) {
2518 isc_uint16_t id, compressed_hash;
2521 compressed_hash = ((nsid_hash_state >> 16) ^
2522 (nsid_hash_state)) & 0xFFFF;
2524 if (nsid->nsid_usepool) {
2527 pick = compressed_hash & NSID_RANGE_MASK;
2528 pick = (nsid->nsid_state + pick) & NSID_POOL_MASK;
2529 id = nsid->nsid_pool[pick];
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;
2537 /* increment the base pointer into the pool */
2538 if (nsid->nsid_state == 65535)
2539 nsid->nsid_state = 0;
2544 * This is the original Algorithm B
2545 * j = ((u_long) NSID_SHUFFLE_TABLE_SIZE * nsid_state2) >> 16;
2547 * We'll perturb it with some random stuff ...
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;
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;
2565 nsid_init(isc_mem_t *mctx, dns_nsid_t *nsid, isc_boolean_t usepool) {
2568 isc_uint16_t a1ndx, a2ndx, a3ndx, c1ndx, c2ndx, c3ndx;
2574 /* Initialize the state */
2575 memset(nsid, 0, sizeof(*nsid));
2576 nsid_hash(&now, sizeof now);
2577 nsid_hash(&mypid, sizeof mypid);
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 ...
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;
2591 /* generator 2, distinct from 1 */
2592 a2ndx = ((isc_uint32_t) (NSID_MULT_TABLE_SIZE - 1) *
2593 ((nsid_hash_state >> 10) & 0xFFFF)) >> 16;
2596 nsid->nsid_a2 = nsid_multiplier_table[a2ndx];
2597 c2ndx = nsid_hash_state % 32767;
2600 nsid->nsid_c2 = 2*c2ndx + 1;
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)
2607 if (a3ndx >= a1ndx && a3ndx >= a2ndx)
2609 nsid->nsid_a3 = nsid_multiplier_table[a3ndx];
2610 c3ndx = nsid_hash_state % 32766;
2611 if (c3ndx >= c1ndx || c3ndx >= c2ndx)
2613 if (c3ndx >= c1ndx && c3ndx >= c2ndx)
2615 nsid->nsid_c3 = 2*c3ndx + 1;
2618 ((nsid_hash_state >> 16) ^ (nsid_hash_state)) & 0xFFFF;
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;
2628 (((u_long) nsid->nsid_a1 * nsid->nsid_state) +
2629 nsid->nsid_c1) & 0xFFFF;
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);
2639 for (i = 0; i < NSID_SHUFFLE_TABLE_SIZE; i++) {
2640 nsid->nsid_vtable[i] = nsid->nsid_state;
2642 (((isc_uint32_t) nsid->nsid_a1 * nsid->nsid_state) +
2643 nsid->nsid_c1) & 0xFFFF;
2645 nsid->nsid_state2 = nsid->nsid_state;
2647 return (ISC_R_SUCCESS);
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));
2656 isc_mem_put(mctx, nsid->nsid_vtable,
2657 NSID_SHUFFLE_TABLE_SIZE * (sizeof(isc_uint16_t)) );
2658 memset(nsid, 0, sizeof(*nsid));
2662 dns_dispatch_hash(void *data, size_t len) {
2663 nsid_hash(data, len);