2 * Copyright (C) 2011 Internet Systems Consortium, Inc. ("ISC")
4 * Permission to use, copy, modify, and/or distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
8 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
9 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
10 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
11 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
12 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
13 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
14 * PERFORMANCE OF THIS SOFTWARE.
17 /* $Id: rpz.c,v 1.7 2011-01-17 04:27:23 marka Exp $ */
23 #include <isc/buffer.h>
26 #include <isc/netaddr.h>
27 #include <isc/print.h>
28 #include <isc/stdlib.h>
29 #include <isc/string.h>
33 #include <dns/fixedname.h>
35 #include <dns/rdata.h>
36 #include <dns/rdataset.h>
37 #include <dns/rdatastruct.h>
38 #include <dns/result.h>
44 * Parallel radix trees for databases of response policy IP addresses
46 * The radix or Patricia trees are somewhat specialized to handle response
47 * policy addresses by representing the two test of IP IP addresses and name
48 * server IP addresses in a single tree.
50 * Each leaf indicates that an IP address is listed in the IP address or the
51 * name server IP address policy sub-zone (or both) of the corresponding
52 * response response zone. The policy data such as a CNAME or an A record
53 * is kept in the policy zone. After an IP address has been found in a radix
54 * tree, the node in the policy zone's database is found by converting
55 * the IP address to a domain name in a canonical form.
57 * The response policy zone canonical form of IPv6 addresses is one of:
58 * prefix.W.W.W.W.W.W.W.W
60 * prefix.WORDS.zz.WORDS
63 * prefix is the prefix length of the IPv6 address between 1 and 128
64 * W is a number between 0 and 65535
65 * WORDS is one or more numbers W separated with "."
66 * zz corresponds to :: in the standard IPv6 text representation
68 * The canonical form of IPv4 addresses is:
71 * prefix is the prefix length of the address between 1 and 32
72 * B is a number between 0 and 255
74 * IPv4 addresses are distinguished from IPv6 addresses by having
75 * 5 labels all of which are numbers, and a prefix between 1 and 32.
80 * Use a private definition of IPv6 addresses because s6_addr32 is not
81 * always defined and our IPv6 addresses are in non-standard byte order
83 typedef isc_uint32_t dns_rpz_cidr_word_t;
84 #define DNS_RPZ_CIDR_WORD_BITS ((int)sizeof(dns_rpz_cidr_word_t)*8)
85 #define DNS_RPZ_CIDR_KEY_BITS ((int)sizeof(dns_rpz_cidr_key_t)*8)
86 #define DNS_RPZ_CIDR_WORDS (128/DNS_RPZ_CIDR_WORD_BITS)
88 dns_rpz_cidr_word_t w[DNS_RPZ_CIDR_WORDS];
91 #define ADDR_V4MAPPED 0xffff
93 #define DNS_RPZ_WORD_MASK(b) \
94 ((b) == 0 ? (dns_rpz_cidr_word_t)(-1) \
95 : ((dns_rpz_cidr_word_t)(-1) \
96 << (DNS_RPZ_CIDR_WORD_BITS - (b))))
98 #define DNS_RPZ_IP_BIT(ip, bitno) \
99 (1 & ((ip)->w[(bitno)/DNS_RPZ_CIDR_WORD_BITS] >> \
100 (DNS_RPZ_CIDR_WORD_BITS - 1 - ((bitno) % DNS_RPZ_CIDR_WORD_BITS))))
102 typedef struct dns_rpz_cidr_node dns_rpz_cidr_node_t;
103 typedef isc_uint8_t dns_rpz_cidr_flags_t;
104 struct dns_rpz_cidr_node {
105 dns_rpz_cidr_node_t *parent;
106 dns_rpz_cidr_node_t *child[2];
107 dns_rpz_cidr_key_t ip;
108 dns_rpz_cidr_bits_t bits;
109 dns_rpz_cidr_flags_t flags;
110 #define DNS_RPZ_CIDR_FG_IP 0x01 /* has IP data or is parent of IP */
111 #define DNS_RPZ_CIDR_FG_IP_DATA 0x02 /* has IP data */
112 #define DNS_RPZ_CIDR_FG_NSIPv4 0x04 /* has or is parent of NSIPv4 data */
113 #define DNS_RPZ_CIDR_FG_NSIPv6 0x08 /* has or is parent of NSIPv6 data */
114 #define DNS_RPZ_CIDR_FG_NSIP_DATA 0x10 /* has NSIP data */
117 struct dns_rpz_cidr {
119 isc_boolean_t had_nsdname;
120 dns_rpz_cidr_node_t *root;
121 dns_name_t ip_name; /* RPZ_IP_ZONE.LOCALHOST. */
122 dns_name_t nsip_name; /* RPZ_NSIP_ZONE.LOCALHOST. */
123 dns_name_t nsdname_name; /* RPZ_NSDNAME_ZONE.LOCALHOST */
127 static isc_boolean_t have_rpz_zones = ISC_FALSE;
131 dns_rpz_type2str(dns_rpz_type_t type)
134 case DNS_RPZ_TYPE_QNAME:
136 case DNS_RPZ_TYPE_IP:
138 case DNS_RPZ_TYPE_NSIP:
140 case DNS_RPZ_TYPE_NSDNAME:
142 case DNS_RPZ_TYPE_BAD:
145 FATAL_ERROR(__FILE__, __LINE__,
146 "impossible response policy zone type %d", type);
147 return ("impossible");
153 dns_rpz_str2policy(const char *str)
156 return (DNS_RPZ_POLICY_ERROR);
157 if (!strcasecmp(str, "given"))
158 return (DNS_RPZ_POLICY_GIVEN);
159 if (!strcasecmp(str, "no-op"))
160 return (DNS_RPZ_POLICY_NO_OP);
161 if (!strcasecmp(str, "nxdomain"))
162 return (DNS_RPZ_POLICY_NXDOMAIN);
163 if (!strcasecmp(str, "nodata"))
164 return (DNS_RPZ_POLICY_NODATA);
165 if (!strcasecmp(str, "cname"))
166 return (DNS_RPZ_POLICY_CNAME);
167 return (DNS_RPZ_POLICY_ERROR);
173 * Free the radix tree of a response policy database.
176 dns_rpz_cidr_free(dns_rpz_cidr_t **cidrp) {
177 dns_rpz_cidr_node_t *cur, *child, *parent;
178 dns_rpz_cidr_t *cidr;
180 REQUIRE(cidrp != NULL);
187 while (cur != NULL) {
189 child = cur->child[0];
194 child = cur->child[1];
200 /* Delete this leaf and go up. */
201 parent = cur->parent;
205 parent->child[parent->child[1] == cur] = NULL;
206 isc_mem_put(cidr->mctx, cur, sizeof(*cur));
210 dns_name_free(&cidr->ip_name, cidr->mctx);
211 dns_name_free(&cidr->nsip_name, cidr->mctx);
212 dns_name_free(&cidr->nsdname_name, cidr->mctx);
213 isc_mem_put(cidr->mctx, cidr, sizeof(*cidr));
220 * Forget a view's list of policy zones.
223 dns_rpz_view_destroy(dns_view_t *view) {
224 dns_rpz_zone_t *zone;
226 REQUIRE(view != NULL);
228 while (!ISC_LIST_EMPTY(view->rpz_zones)) {
229 zone = ISC_LIST_HEAD(view->rpz_zones);
230 ISC_LIST_UNLINK(view->rpz_zones, zone, link);
231 if (dns_name_dynamic(&zone->origin))
232 dns_name_free(&zone->origin, view->mctx);
233 if (dns_name_dynamic(&zone->nsdname))
234 dns_name_free(&zone->nsdname, view->mctx);
235 if (dns_name_dynamic(&zone->cname))
236 dns_name_free(&zone->cname, view->mctx);
237 isc_mem_put(view->mctx, zone, sizeof(*zone));
242 * Note that we have at least one response policy zone.
243 * It would be better for something to tell the rbtdb code that the
244 * zone is in at least one view's list of policy zones.
247 dns_rpz_set_need(isc_boolean_t need)
249 have_rpz_zones = need;
256 return (have_rpz_zones);
262 * Start a new radix tree for a response policy zone.
265 dns_rpz_new_cidr(isc_mem_t *mctx, dns_name_t *origin,
266 dns_rpz_cidr_t **rbtdb_cidr)
269 dns_rpz_cidr_t *cidr;
271 REQUIRE(rbtdb_cidr != NULL && *rbtdb_cidr == NULL);
274 * Only if there is at least one response policy zone.
277 return (ISC_R_SUCCESS);
279 cidr = isc_mem_get(mctx, sizeof(*cidr));
281 return (ISC_R_NOMEMORY);
282 memset(cidr, 0, sizeof(*cidr));
285 dns_name_init(&cidr->ip_name, NULL);
286 result = dns_name_fromstring2(&cidr->ip_name, DNS_RPZ_IP_ZONE, origin,
287 DNS_NAME_DOWNCASE, mctx);
288 if (result != ISC_R_SUCCESS) {
289 isc_mem_put(mctx, cidr, sizeof(*cidr));
293 dns_name_init(&cidr->nsip_name, NULL);
294 result = dns_name_fromstring2(&cidr->nsip_name, DNS_RPZ_NSIP_ZONE,
295 origin, DNS_NAME_DOWNCASE, mctx);
296 if (result != ISC_R_SUCCESS) {
297 dns_name_free(&cidr->ip_name, mctx);
298 isc_mem_put(mctx, cidr, sizeof(*cidr));
302 dns_name_init(&cidr->nsdname_name, NULL);
303 result = dns_name_fromstring2(&cidr->nsdname_name, DNS_RPZ_NSDNAME_ZONE,
304 origin, DNS_NAME_DOWNCASE, mctx);
305 if (result != ISC_R_SUCCESS) {
306 dns_name_free(&cidr->nsip_name, mctx);
307 dns_name_free(&cidr->ip_name, mctx);
308 isc_mem_put(mctx, cidr, sizeof(*cidr));
313 return (ISC_R_SUCCESS);
318 * See if a policy zone has IP, NSIP, or NSDNAME rules or records.
321 dns_rpz_enabled(dns_rpz_cidr_t *cidr, dns_rpz_st_t *st) {
322 if (cidr->root != NULL &&
323 (cidr->root->flags & DNS_RPZ_CIDR_FG_IP) != 0)
324 st->state |= DNS_RPZ_HAVE_IP;
325 if (cidr->root != NULL &&
326 (cidr->root->flags & DNS_RPZ_CIDR_FG_NSIPv4) != 0)
327 st->state |= DNS_RPZ_HAVE_NSIPv4;
328 if (cidr->root != NULL &&
329 (cidr->root->flags & DNS_RPZ_CIDR_FG_NSIPv6) != 0)
330 st->state |= DNS_RPZ_HAVE_NSIPv6;
331 if (cidr->had_nsdname)
332 st->state |= DNS_RPZ_HAD_NSDNAME;
335 static inline dns_rpz_cidr_flags_t
336 get_flags(const dns_rpz_cidr_key_t *ip, dns_rpz_cidr_bits_t prefix,
337 dns_rpz_type_t rpz_type)
339 if (rpz_type == DNS_RPZ_TYPE_NSIP) {
341 ip->w[0] == 0 && ip->w[1] == 0 &&
342 ip->w[2] == ADDR_V4MAPPED)
343 return (DNS_RPZ_CIDR_FG_NSIP_DATA |
344 DNS_RPZ_CIDR_FG_NSIPv4);
346 return (DNS_RPZ_CIDR_FG_NSIP_DATA |
347 DNS_RPZ_CIDR_FG_NSIPv6);
349 return (DNS_RPZ_CIDR_FG_IP | DNS_RPZ_CIDR_FG_IP_DATA);
356 * Mark a node as having IP or NSIP data and all of its parents
357 * as members of the IP or NSIP tree.
360 set_node_flags(dns_rpz_cidr_node_t *node, dns_rpz_type_t rpz_type) {
361 dns_rpz_cidr_flags_t flags;
363 flags = get_flags(&node->ip, node->bits, rpz_type);
364 node->flags |= flags;
365 flags &= ~(DNS_RPZ_CIDR_FG_NSIP_DATA | DNS_RPZ_CIDR_FG_IP_DATA);
370 node->flags |= flags;
377 * Make a radix tree node.
379 static dns_rpz_cidr_node_t *
380 new_node(dns_rpz_cidr_t *cidr, const dns_rpz_cidr_key_t *ip,
381 dns_rpz_cidr_bits_t bits, dns_rpz_cidr_flags_t flags)
383 dns_rpz_cidr_node_t *node;
386 node = isc_mem_get(cidr->mctx, sizeof(*node));
389 memset(node, 0, sizeof(*node));
391 node->flags = flags & ~(DNS_RPZ_CIDR_FG_IP_DATA |
392 DNS_RPZ_CIDR_FG_NSIP_DATA);
395 words = bits / DNS_RPZ_CIDR_WORD_BITS;
396 wlen = bits % DNS_RPZ_CIDR_WORD_BITS;
399 node->ip.w[i] = ip->w[i];
403 node->ip.w[i] = ip->w[i] & DNS_RPZ_WORD_MASK(wlen);
406 while (i < DNS_RPZ_CIDR_WORDS)
415 badname(int level, dns_name_t *name, const char *comment)
417 char printname[DNS_NAME_FORMATSIZE];
419 if (isc_log_wouldlog(dns_lctx, level)) {
420 dns_name_format(name, printname, sizeof(printname));
421 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
422 DNS_LOGMODULE_RBTDB, level,
423 "invalid response policy name \"%s\"%s",
431 * Convert an IP address from radix tree binary (host byte order) to
432 * to its canonical response policy domain name and its name in the
436 ip2name(dns_rpz_cidr_t *cidr, const dns_rpz_cidr_key_t *tgt_ip,
437 dns_rpz_cidr_bits_t tgt_prefix, dns_rpz_type_t type,
438 dns_name_t *canon_name, dns_name_t *search_name)
440 #ifndef INET6_ADDRSTRLEN
441 #define INET6_ADDRSTRLEN 46
443 int w[DNS_RPZ_CIDR_WORDS*2];
444 char str[1+8+1+INET6_ADDRSTRLEN+1];
451 if (tgt_prefix > 96 &&
454 tgt_ip->w[2] == ADDR_V4MAPPED) {
455 len = snprintf(str, sizeof(str), "%d.%d.%d.%d.%d",
458 (tgt_ip->w[3]>>8) & 0xff,
459 (tgt_ip->w[3]>>16) & 0xff,
460 (tgt_ip->w[3]>>24) & 0xff);
461 if (len == -1 || len > (int)sizeof(str))
462 return (ISC_R_FAILURE);
464 for (i = 0; i < DNS_RPZ_CIDR_WORDS; i++) {
465 w[i*2+1] = ((tgt_ip->w[DNS_RPZ_CIDR_WORDS-1-i] >> 16)
467 w[i*2] = tgt_ip->w[DNS_RPZ_CIDR_WORDS-1-i] & 0xffff;
470 len = snprintf(str, sizeof(str), "%d", tgt_prefix);
472 return (ISC_R_FAILURE);
474 while (i < DNS_RPZ_CIDR_WORDS * 2) {
475 if (w[i] != 0 || zeros
476 || i >= DNS_RPZ_CIDR_WORDS * 2 - 1
478 INSIST((size_t)len <= sizeof(str));
479 n = snprintf(&str[len], sizeof(str) - len,
482 return (ISC_R_FAILURE);
486 INSIST((size_t)len <= sizeof(str));
487 n = snprintf(&str[len], sizeof(str) - len,
490 return (ISC_R_FAILURE);
493 while (i < DNS_RPZ_CIDR_WORDS * 2 && w[i] == 0)
496 if (len > (int)sizeof(str))
497 return (ISC_R_FAILURE);
501 if (canon_name != NULL) {
502 isc__buffer_init(&buffer, str, sizeof(str));
503 isc__buffer_add(&buffer, len);
504 result = dns_name_fromtext(canon_name, &buffer,
505 dns_rootname, 0, NULL);
506 if (result != ISC_R_SUCCESS)
509 if (search_name != NULL) {
510 isc__buffer_init(&buffer, str, sizeof(str));
511 isc__buffer_add(&buffer, len);
512 if (type == DNS_RPZ_TYPE_NSIP)
513 name = &cidr->nsip_name;
515 name = &cidr->ip_name;
516 result = dns_name_fromtext(search_name, &buffer, name, 0, NULL);
517 if (result != ISC_R_SUCCESS)
520 return (ISC_R_SUCCESS);
526 * Decide which kind of IP address response policy zone a name is in.
528 static dns_rpz_type_t
529 set_type(dns_rpz_cidr_t *cidr, dns_name_t *name) {
531 if (dns_name_issubdomain(name, &cidr->ip_name))
532 return (DNS_RPZ_TYPE_IP);
535 * Require `./configure --enable-rpz-nsip` and nsdname
536 * until consistency problems are resolved.
538 #ifdef ENABLE_RPZ_NSIP
539 if (dns_name_issubdomain(name, &cidr->nsip_name))
540 return (DNS_RPZ_TYPE_NSIP);
543 #ifdef ENABLE_RPZ_NSDNAME
544 if (dns_name_issubdomain(name, &cidr->nsdname_name))
545 return (DNS_RPZ_TYPE_NSDNAME);
548 return (DNS_RPZ_TYPE_QNAME);
554 * Convert an IP address from canonical response policy domain name form
555 * to radix tree binary (host byte order).
558 name2ipkey(dns_rpz_cidr_t *cidr, int level, dns_name_t *src_name,
559 dns_rpz_type_t type, dns_rpz_cidr_key_t *tgt_ip,
560 dns_rpz_cidr_bits_t *tgt_prefix)
563 unsigned char data[DNS_NAME_MAXWIRE+1];
564 dns_fixedname_t fname;
566 const char *cp, *end;
569 dns_rpz_cidr_bits_t bits;
570 unsigned long prefix, l;
574 * Need at least enough labels for the shortest name,
575 * :: or 128.*.RPZ_x_ZONE.rpz.LOCALHOST.
577 ip_labels = dns_name_countlabels(src_name);
578 ip_labels -= dns_name_countlabels(&cidr->ip_name);
581 badname(level, src_name, ", too short");
582 return (ISC_R_FAILURE);
586 * Get text for the IP address without RPZ_x_ZONE.rpz.LOCALHOST.
588 dns_fixedname_init(&fname);
589 name = dns_fixedname_name(&fname);
590 dns_name_split(src_name, dns_name_countlabels(&cidr->ip_name),
592 isc_buffer_init(&buffer, data, sizeof(data));
593 dns_name_totext(name, ISC_TRUE, &buffer);
594 isc_buffer_putuint8(&buffer, '\0');
595 cp = isc_buffer_base(&buffer);
597 prefix = strtoul(cp, &cp2, 10);
598 if (prefix < 1U || prefix > 128U || *cp2 != '.') {
599 badname(level, src_name, ", bad prefix length");
600 return (ISC_R_FAILURE);
604 end = isc_buffer_used(&buffer);
605 if (ip_labels == 4 && !strchr(cp, 'z')) {
607 * Convert an IPv4 address
608 * from the form "prefix.w.z.y.x"
611 badname(level, src_name, "; bad IPv4 prefix length");
612 return (ISC_R_FAILURE);
615 *tgt_prefix = (dns_rpz_cidr_bits_t)prefix;
618 tgt_ip->w[2] = ADDR_V4MAPPED;
620 for (i = 0; i < 32; i += 8) {
621 l = strtoul(cp, &cp2, 10);
622 if (l > 255U || (*cp2 != '.' && *cp2 != '\0')) {
623 badname(level, src_name, "; bad IPv4 address");
624 return (ISC_R_FAILURE);
626 tgt_ip->w[3] |= l << i;
631 * Convert a text IPv6 address.
633 *tgt_prefix = (dns_rpz_cidr_bits_t)prefix;
635 ip_labels > 0 && i < DNS_RPZ_CIDR_WORDS * 2;
637 if (cp[0] == 'z' && cp[1] == 'z' &&
638 (cp[2] == '.' || cp[2] == '\0') &&
642 tgt_ip->w[3-i/2] = 0;
644 } while (ip_labels + i <= 8);
647 l = strtoul(cp, &cp2, 16);
649 (*cp2 != '.' && *cp2 != '\0')) {
650 badname(level, src_name, "");
651 return (ISC_R_FAILURE);
654 tgt_ip->w[3-i/2] = l;
656 tgt_ip->w[3-i/2] |= l << 16;
663 badname(level, src_name, "");
664 return (ISC_R_FAILURE);
668 * Check for 1s after the prefix length.
670 bits = (dns_rpz_cidr_bits_t)prefix;
671 while (bits < DNS_RPZ_CIDR_KEY_BITS) {
672 dns_rpz_cidr_word_t aword;
674 i = bits % DNS_RPZ_CIDR_WORD_BITS;
675 aword = tgt_ip->w[bits / DNS_RPZ_CIDR_WORD_BITS];
676 if ((aword & ~DNS_RPZ_WORD_MASK(i)) != 0) {
677 badname(level, src_name, "; wrong prefix length");
678 return (ISC_R_FAILURE);
681 bits += DNS_RPZ_CIDR_WORD_BITS;
685 * Convert the IPv6 address back to a canonical policy domain name
686 * to ensure that it is in canonical form.
688 if (ISC_R_SUCCESS != ip2name(cidr, tgt_ip, (dns_rpz_cidr_bits_t)prefix,
690 !dns_name_equal(src_name, name)) {
691 badname(level, src_name, "; not canonical");
692 return (ISC_R_FAILURE);
695 return (ISC_R_SUCCESS);
701 * find first differing bit
704 ffbit(dns_rpz_cidr_word_t w) {
708 return (DNS_RPZ_CIDR_WORD_BITS);
709 for (bit = 0; (w & (1U << (DNS_RPZ_CIDR_WORD_BITS-1))) == 0; bit++)
717 * find the first differing bit in two keys
720 diff_keys(const dns_rpz_cidr_key_t *key1, dns_rpz_cidr_bits_t bits1,
721 const dns_rpz_cidr_key_t *key2, dns_rpz_cidr_bits_t bits2)
723 dns_rpz_cidr_word_t delta;
724 dns_rpz_cidr_bits_t maxbit, bit;
727 maxbit = ISC_MIN(bits1, bits2);
730 * find the first differing words
734 i++, bit += DNS_RPZ_CIDR_WORD_BITS) {
735 delta = key1->w[i] ^ key2->w[i];
741 return (ISC_MIN(bit, maxbit));
747 * Search a radix tree for an IP address for ordinary lookup
748 * or for a CIDR block adding or deleting an entry
749 * The tree read (for simple search) or write lock must be held by the caller.
751 * return ISC_R_SUCCESS, ISC_R_NOTFOUND, DNS_R_PARTIALMATCH, ISC_R_EXISTS,
755 search(dns_rpz_cidr_t *cidr, const dns_rpz_cidr_key_t *tgt_ip,
756 dns_rpz_cidr_bits_t tgt_prefix, dns_rpz_type_t type,
757 isc_boolean_t create,
758 dns_rpz_cidr_node_t **found) /* NULL or longest match node */
760 dns_rpz_cidr_node_t *cur, *parent, *child, *new_parent, *sibling;
761 int cur_num, child_num;
762 dns_rpz_cidr_bits_t dbit;
763 dns_rpz_cidr_flags_t flags, data_flag;
764 isc_result_t find_result;
766 flags = get_flags(tgt_ip, tgt_prefix, type);
767 data_flag = flags & (DNS_RPZ_CIDR_FG_IP_DATA |
768 DNS_RPZ_CIDR_FG_NSIP_DATA);
770 find_result = ISC_R_NOTFOUND;
779 * No child so we cannot go down. Fail or
780 * add the target as a child of the current parent.
783 return (find_result);
784 child = new_node(cidr, tgt_ip, tgt_prefix, 0);
786 return (ISC_R_NOMEMORY);
790 parent->child[cur_num] = child;
791 child->parent = parent;
792 set_node_flags(child, type);
795 return (ISC_R_SUCCESS);
799 * Pretend a node not in the correct tree does not exist
800 * if we are not adding to the tree,
801 * If we are adding, then continue down to eventually
802 * add a node and mark/put this node in the correct tree.
804 if ((cur->flags & flags) == 0 && !create)
805 return (find_result);
807 dbit = diff_keys(tgt_ip, tgt_prefix, &cur->ip, cur->bits);
809 * dbit <= tgt_prefix and dbit <= cur->bits always.
810 * We are finished searching if we matched all of the target.
812 if (dbit == tgt_prefix) {
813 if (tgt_prefix == cur->bits) {
815 * The current node matches the target exactly.
816 * It is the answer if it has data.
818 if ((cur->flags & data_flag) != 0) {
820 return (ISC_R_EXISTS);
823 return (ISC_R_SUCCESS);
826 * The node had no data but does now.
828 set_node_flags(cur, type);
831 return (ISC_R_SUCCESS);
833 return (find_result);
837 * We know tgt_prefix < cur_bits which means that
838 * the target is shorter than the current node.
839 * Add the target as the current node's parent.
842 return (find_result);
844 new_parent = new_node(cidr, tgt_ip, tgt_prefix,
846 if (new_parent == NULL)
847 return (ISC_R_NOMEMORY);
848 new_parent->parent = parent;
850 cidr->root = new_parent;
852 parent->child[cur_num] = new_parent;
853 child_num = DNS_RPZ_IP_BIT(&cur->ip, tgt_prefix+1);
854 new_parent->child[child_num] = cur;
855 cur->parent = new_parent;
856 set_node_flags(new_parent, type);
859 return (ISC_R_SUCCESS);
862 if (dbit == cur->bits) {
864 * We have a partial match by matching of all of the
865 * current node but only part of the target.
868 if ((cur->flags & data_flag) != 0) {
869 find_result = DNS_R_PARTIALMATCH;
875 cur_num = DNS_RPZ_IP_BIT(tgt_ip, dbit);
876 cur = cur->child[cur_num];
882 * dbit < tgt_prefix and dbit < cur->bits,
883 * so we failed to match both the target and the current node.
884 * Insert a fork of a parent above the current node and
885 * add the target as a sibling of the current node
888 return (find_result);
890 sibling = new_node(cidr, tgt_ip, tgt_prefix, 0);
892 return (ISC_R_NOMEMORY);
893 new_parent = new_node(cidr, tgt_ip, dbit, cur->flags);
894 if (new_parent == NULL) {
895 isc_mem_put(cidr->mctx, sibling, sizeof(*sibling));
896 return (ISC_R_NOMEMORY);
898 new_parent->parent = parent;
900 cidr->root = new_parent;
902 parent->child[cur_num] = new_parent;
903 child_num = DNS_RPZ_IP_BIT(tgt_ip, dbit);
904 new_parent->child[child_num] = sibling;
905 new_parent->child[1-child_num] = cur;
906 cur->parent = new_parent;
907 sibling->parent = new_parent;
908 set_node_flags(sibling, type);
911 return (ISC_R_SUCCESS);
918 * Add an IP address to the radix tree of a response policy database.
919 * The tree write lock must be held by the caller.
922 dns_rpz_cidr_addip(dns_rpz_cidr_t *cidr, dns_name_t *name)
924 dns_rpz_cidr_key_t tgt_ip;
925 dns_rpz_cidr_bits_t tgt_prefix;
932 * no worries if the new name is not an IP address
934 type = set_type(cidr, name);
936 case DNS_RPZ_TYPE_IP:
937 case DNS_RPZ_TYPE_NSIP:
939 case DNS_RPZ_TYPE_NSDNAME:
940 cidr->had_nsdname = ISC_TRUE;
942 case DNS_RPZ_TYPE_QNAME:
943 case DNS_RPZ_TYPE_BAD:
946 if (ISC_R_SUCCESS != name2ipkey(cidr, DNS_RPZ_ERROR_LEVEL, name,
947 type, &tgt_ip, &tgt_prefix))
950 if (ISC_R_EXISTS == search(cidr, &tgt_ip, tgt_prefix, type,
952 isc_log_wouldlog(dns_lctx, DNS_RPZ_ERROR_LEVEL)) {
953 char printname[DNS_NAME_FORMATSIZE];
955 dns_name_format(name, printname, sizeof(printname));
956 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
957 DNS_LOGMODULE_RBTDB, DNS_RPZ_ERROR_LEVEL,
958 "duplicate response policy name \"%s\"",
966 * Delete an IP address from the radix tree of a response policy database.
967 * The tree write lock must be held by the caller.
970 dns_rpz_cidr_deleteip(dns_rpz_cidr_t *cidr, dns_name_t *name) {
971 dns_rpz_cidr_key_t tgt_ip;
972 dns_rpz_cidr_bits_t tgt_prefix;
974 dns_rpz_cidr_node_t *tgt = NULL, *parent, *child;
975 dns_rpz_cidr_flags_t flags, data_flag;
981 * Decide which kind of policy zone IP address it is, if either
982 * and then find its node.
984 type = set_type(cidr, name);
986 case DNS_RPZ_TYPE_IP:
987 case DNS_RPZ_TYPE_NSIP:
989 case DNS_RPZ_TYPE_NSDNAME:
991 * We cannot easily count nsdnames because
992 * internal rbt nodes get deleted.
995 case DNS_RPZ_TYPE_QNAME:
996 case DNS_RPZ_TYPE_BAD:
1001 * Do not get excited about the deletion of interior rbt nodes.
1003 if (ISC_R_SUCCESS != name2ipkey(cidr, DNS_RPZ_DEBUG_LEVEL2, name,
1004 type, &tgt_ip, &tgt_prefix))
1006 if (ISC_R_SUCCESS != search(cidr, &tgt_ip, tgt_prefix, type,
1008 if (isc_log_wouldlog(dns_lctx, DNS_RPZ_ERROR_LEVEL)) {
1009 char printname[DNS_NAME_FORMATSIZE];
1011 dns_name_format(name, printname, sizeof(printname));
1012 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
1013 DNS_LOGMODULE_RBTDB, DNS_RPZ_ERROR_LEVEL,
1014 "missing response policy node \"%s\"",
1021 * Mark the node and its parents to reflect the deleted IP address.
1023 flags = get_flags(&tgt_ip, tgt_prefix, type);
1024 data_flag = flags & (DNS_RPZ_CIDR_FG_IP_DATA |
1025 DNS_RPZ_CIDR_FG_NSIP_DATA);
1026 tgt->flags &= ~data_flag;
1027 for (parent = tgt; parent != NULL; parent = parent->parent) {
1028 if ((parent->flags & data_flag) != 0 ||
1029 (parent->child[0] != NULL &&
1030 (parent->child[0]->flags & flags) != 0) ||
1031 (parent->child[1] != NULL &&
1032 (parent->child[1]->flags & flags) != 0))
1034 parent->flags &= ~flags;
1038 * We might need to delete 2 nodes.
1042 * The node is now useless if it has no data of its own
1043 * and 0 or 1 children. We are finished if it is not useless.
1045 if ((child = tgt->child[0]) != NULL) {
1046 if (tgt->child[1] != NULL)
1049 child = tgt->child[1];
1051 if ((tgt->flags & (DNS_RPZ_CIDR_FG_IP_DATA |
1052 DNS_RPZ_CIDR_FG_NSIP_DATA)) != 0)
1056 * Replace the pointer to this node in the parent with
1057 * the remaining child or NULL.
1059 parent = tgt->parent;
1060 if (parent == NULL) {
1063 parent->child[parent->child[1] == tgt] = child;
1066 * If the child exists fix up its parent pointer.
1069 child->parent = parent;
1070 isc_mem_put(cidr->mctx, tgt, sizeof(*tgt));
1073 } while (tgt != NULL);
1079 * Caller must hold tree lock.
1080 * Return ISC_R_NOTFOUND
1081 * or ISC_R_SUCCESS and the found entry's canonical and search names
1082 * and its prefix length
1085 dns_rpz_cidr_find(dns_rpz_cidr_t *cidr, const isc_netaddr_t *netaddr,
1086 dns_rpz_type_t type, dns_name_t *canon_name,
1087 dns_name_t *search_name, dns_rpz_cidr_bits_t *prefix)
1089 dns_rpz_cidr_key_t tgt_ip;
1090 isc_result_t result;
1091 dns_rpz_cidr_node_t *found;
1095 * Convert IP address to CIDR tree key.
1097 if (netaddr->family == AF_INET) {
1100 tgt_ip.w[2] = ADDR_V4MAPPED;
1101 tgt_ip.w[3] = ntohl(netaddr->type.in.s_addr);
1102 } else if (netaddr->family == AF_INET6) {
1103 dns_rpz_cidr_key_t src_ip6;
1106 * Given the int aligned struct in_addr member of netaddr->type
1107 * one could cast netaddr->type.in6 to dns_rpz_cidr_key_t *,
1108 * but there are objections.
1110 memcpy(src_ip6.w, &netaddr->type.in6, sizeof(src_ip6.w));
1111 for (i = 0; i < 4; i++) {
1112 tgt_ip.w[i] = ntohl(src_ip6.w[i]);
1115 return (ISC_R_NOTFOUND);
1118 result = search(cidr, &tgt_ip, 128, type, ISC_FALSE, &found);
1119 if (result != ISC_R_SUCCESS && result != DNS_R_PARTIALMATCH)
1122 *prefix = found->bits;
1123 return (ip2name(cidr, &found->ip, found->bits, type,
1124 canon_name, search_name));
1130 * Translate CNAME rdata to a QNAME response policy action.
1133 dns_rpz_decode_cname(dns_rdataset_t *rdataset, dns_name_t *selfname) {
1134 dns_rdata_t rdata = DNS_RDATA_INIT;
1135 dns_rdata_cname_t cname;
1136 isc_result_t result;
1138 result = dns_rdataset_first(rdataset);
1139 RUNTIME_CHECK(result == ISC_R_SUCCESS);
1140 dns_rdataset_current(rdataset, &rdata);
1141 result = dns_rdata_tostruct(&rdata, &cname, NULL);
1142 RUNTIME_CHECK(result == ISC_R_SUCCESS);
1143 dns_rdata_reset(&rdata);
1146 * CNAME . means NXDOMAIN
1148 if (dns_name_equal(&cname.cname, dns_rootname))
1149 return (DNS_RPZ_POLICY_NXDOMAIN);
1152 * CNAME *. means NODATA
1154 if (dns_name_countlabels(&cname.cname) == 2
1155 && dns_name_iswildcard(&cname.cname))
1156 return (DNS_RPZ_POLICY_NODATA);
1159 * 128.1.0.127.rpz-ip CNAME 128.1.0.0.127. means "do not rewrite"
1161 if (selfname != NULL && dns_name_equal(&cname.cname, selfname))
1162 return (DNS_RPZ_POLICY_NO_OP);
1165 * evil.com CNAME garden.net rewrites www.evil.com to www.garden.net.
1167 return (DNS_RPZ_POLICY_RECORD);