rpz.c 67.6 KB
Newer Older
1
/*
2
 * Copyright (C) 2011-2017  Internet Systems Consortium, Inc. ("ISC")
3
 *
4 5 6
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7
 */
Tinderbox User's avatar
Tinderbox User committed
8

9 10 11 12 13 14 15 16
/*! \file */

#include <config.h>

#include <isc/buffer.h>
#include <isc/mem.h>
#include <isc/net.h>
#include <isc/netaddr.h>
Mark Andrews's avatar
Mark Andrews committed
17
#include <isc/print.h>
Evan Hunt's avatar
Evan Hunt committed
18
#include <isc/rwlock.h>
19 20
#include <isc/stdlib.h>
#include <isc/string.h>
21
#include <isc/task.h>
22 23 24
#include <isc/util.h>

#include <dns/db.h>
25 26
#include <dns/dbiterator.h>
#include <dns/events.h>
27 28 29 30 31
#include <dns/fixedname.h>
#include <dns/log.h>
#include <dns/rdata.h>
#include <dns/rdataset.h>
#include <dns/rdatastruct.h>
32
#include <dns/rdatasetiter.h>
33
#include <dns/result.h>
34
#include <dns/rbt.h>
35 36 37 38 39 40 41
#include <dns/rpz.h>
#include <dns/view.h>


/*
 * Parallel radix trees for databases of response policy IP addresses
 *
42 43 44 45 46 47 48
 * The radix or patricia trees are somewhat specialized to handle response
 * policy addresses by representing the two sets of IP addresses and name
 * server IP addresses in a single tree.  One set of IP addresses is
 * for rpz-ip policies or policies triggered by addresses in A or
 * AAAA records in responses.
 * The second set is for rpz-nsip policies or policies triggered by addresses
 * in A or AAAA records for NS records that are authorities for responses.
49 50 51
 *
 * Each leaf indicates that an IP address is listed in the IP address or the
 * name server IP address policy sub-zone (or both) of the corresponding
52
 * response policy zone.  The policy data such as a CNAME or an A record
53 54 55 56
 * is kept in the policy zone.  After an IP address has been found in a radix
 * tree, the node in the policy zone's database is found by converting
 * the IP address to a domain name in a canonical form.
 *
57 58
 *
 * The response policy zone canonical form of an IPv6 address is one of:
59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
 *	prefix.W.W.W.W.W.W.W.W
 *	prefix.WORDS.zz
 *	prefix.WORDS.zz.WORDS
 *	prefix.zz.WORDS
 *  where
 *	prefix	is the prefix length of the IPv6 address between 1 and 128
 *	W	is a number between 0 and 65535
 *	WORDS	is one or more numbers W separated with "."
 *	zz	corresponds to :: in the standard IPv6 text representation
 *
 * The canonical form of IPv4 addresses is:
 *	prefix.B.B.B.B
 *  where
 *	prefix	is the prefix length of the address between 1 and 32
 *	B	is a number between 0 and 255
 *
75
 * Names for IPv4 addresses are distinguished from IPv6 addresses by having
76 77 78
 * 5 labels all of which are numbers, and a prefix between 1 and 32.
 */

79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
/*
 * Nodes hashtable calculation parameters
 */
#define DNS_RPZ_HTSIZE_MAX	24
#define DNS_RPZ_HTSIZE_DIV	3

/*
 * Maximum number of nodes to process per quantum
 */
#define DNS_RPZ_QUANTUM 1024

static void
dns_rpz_update_from_db(dns_rpz_zone_t *rpz);

static void
dns_rpz_update_taskaction(isc_task_t *task, isc_event_t *event);
95 96 97 98 99 100 101 102 103 104 105 106 107 108

/*
 * Use a private definition of IPv6 addresses because s6_addr32 is not
 * always defined and our IPv6 addresses are in non-standard byte order
 */
typedef isc_uint32_t		dns_rpz_cidr_word_t;
#define DNS_RPZ_CIDR_WORD_BITS	((int)sizeof(dns_rpz_cidr_word_t)*8)
#define DNS_RPZ_CIDR_KEY_BITS	((int)sizeof(dns_rpz_cidr_key_t)*8)
#define DNS_RPZ_CIDR_WORDS	(128/DNS_RPZ_CIDR_WORD_BITS)
typedef struct {
	dns_rpz_cidr_word_t	w[DNS_RPZ_CIDR_WORDS];
} dns_rpz_cidr_key_t;

#define ADDR_V4MAPPED		0xffff
109 110 111 112 113 114
#define KEY_IS_IPV4(prefix,ip) ((prefix) >= 96 && (ip)->w[0] == 0 &&	\
				(ip)->w[1] == 0 && (ip)->w[2] == ADDR_V4MAPPED)

#define DNS_RPZ_WORD_MASK(b) ((b) == 0 ? (dns_rpz_cidr_word_t)(-1)	\
			      : ((dns_rpz_cidr_word_t)(-1)		\
				 << (DNS_RPZ_CIDR_WORD_BITS - (b))))
115

116 117 118 119 120 121
/*
 * Get bit #n from the array of words of an IP address.
 */
#define DNS_RPZ_IP_BIT(ip, n) (1 & ((ip)->w[(n)/DNS_RPZ_CIDR_WORD_BITS] >>  \
				    (DNS_RPZ_CIDR_WORD_BITS		    \
				     - 1 - ((n) % DNS_RPZ_CIDR_WORD_BITS))))
122

123
/*
Evan Hunt's avatar
Evan Hunt committed
124 125
 * A triplet of arrays of bits flagging the existence of
 * client-IP, IP, and NSIP policy triggers.
126
 */
Evan Hunt's avatar
Evan Hunt committed
127 128 129 130 131
typedef struct dns_rpz_addr_zbits dns_rpz_addr_zbits_t;
struct dns_rpz_addr_zbits {
	dns_rpz_zbits_t		client_ip;
	dns_rpz_zbits_t		ip;
	dns_rpz_zbits_t		nsip;
132
};
133

134 135 136
/*
 * A CIDR or radix tree node.
 */
137
struct dns_rpz_cidr_node {
138 139 140 141
	dns_rpz_cidr_node_t	*parent;
	dns_rpz_cidr_node_t	*child[2];
	dns_rpz_cidr_key_t	ip;
	dns_rpz_prefix_t	prefix;
Evan Hunt's avatar
Evan Hunt committed
142 143
	dns_rpz_addr_zbits_t	set;
	dns_rpz_addr_zbits_t	sum;
144 145
};

Evan Hunt's avatar
Evan Hunt committed
146 147 148 149 150 151 152 153 154 155
/*
 * A pair of arrays of bits flagging the existence of
 * QNAME and NSDNAME policy triggers.
 */
typedef struct dns_rpz_nm_zbits dns_rpz_nm_zbits_t;
struct dns_rpz_nm_zbits {
	dns_rpz_zbits_t		qname;
	dns_rpz_zbits_t		ns;
};

156 157 158 159 160
/*
 * The data in a RBT node has two pairs of bits for policy zones.
 * One pair is for the corresponding name of the node such as example.com
 * and the other pair is for a wildcard child such as *.example.com.
 */
161 162
typedef struct dns_rpz_nm_data dns_rpz_nm_data_t;
struct dns_rpz_nm_data {
Evan Hunt's avatar
Evan Hunt committed
163 164
	dns_rpz_nm_zbits_t	set;
	dns_rpz_nm_zbits_t	wild;
165 166
};

167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185
#if 0
/*
 * Catch a name while debugging.
 */
static void
catch_name(const dns_name_t *src_name, const char *tgt, const char *str) {
	dns_fixedname_t tgt_namef;
	dns_name_t *tgt_name;

	dns_fixedname_init(&tgt_namef);
	tgt_name = dns_fixedname_name(&tgt_namef);
	dns_name_fromstring(tgt_name, tgt, DNS_NAME_DOWNCASE, NULL);
	if (dns_name_equal(src_name, tgt_name)) {
		isc_log_write(dns_lctx, DNS_LOGCATEGORY_RPZ,
			      DNS_LOGMODULE_RBTDB, DNS_RPZ_ERROR_LEVEL,
			      "rpz hit failed: %s %s", str, tgt);
	}
}
#endif
186 187

const char *
188
dns_rpz_type2str(dns_rpz_type_t type) {
189
	switch (type) {
Evan Hunt's avatar
Evan Hunt committed
190 191
	case DNS_RPZ_TYPE_CLIENT_IP:
		return ("CLIENT-IP");
192 193 194 195 196 197 198 199 200 201 202
	case DNS_RPZ_TYPE_QNAME:
		return ("QNAME");
	case DNS_RPZ_TYPE_IP:
		return ("IP");
	case DNS_RPZ_TYPE_NSIP:
		return ("NSIP");
	case DNS_RPZ_TYPE_NSDNAME:
		return ("NSDNAME");
	case DNS_RPZ_TYPE_BAD:
		break;
	}
203
	FATAL_ERROR(__FILE__, __LINE__, "impossible rpz type %d", type);
204 205 206 207
	return ("impossible");
}

dns_rpz_policy_t
208
dns_rpz_str2policy(const char *str) {
Evan Hunt's avatar
Evan Hunt committed
209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224
	static struct {
		const char *str;
		dns_rpz_policy_t policy;
	} tbl[] = {
		{"given",	DNS_RPZ_POLICY_GIVEN},
		{"disabled",	DNS_RPZ_POLICY_DISABLED},
		{"passthru",	DNS_RPZ_POLICY_PASSTHRU},
		{"drop",	DNS_RPZ_POLICY_DROP},
		{"tcp-only",	DNS_RPZ_POLICY_TCP_ONLY},
		{"nxdomain",	DNS_RPZ_POLICY_NXDOMAIN},
		{"nodata",	DNS_RPZ_POLICY_NODATA},
		{"cname",	DNS_RPZ_POLICY_CNAME},
		{"no-op",	DNS_RPZ_POLICY_PASSTHRU},   /* old passthru */
	};
	unsigned int n;

225 226
	if (str == NULL)
		return (DNS_RPZ_POLICY_ERROR);
Evan Hunt's avatar
Evan Hunt committed
227 228 229 230
	for (n = 0; n < sizeof(tbl)/sizeof(tbl[0]); ++n) {
		if (!strcasecmp(tbl[n].str, str))
			return (tbl[n].policy);
	}
231 232 233
	return (DNS_RPZ_POLICY_ERROR);
}

234 235 236
const char *
dns_rpz_policy2str(dns_rpz_policy_t policy) {
	const char *str;
237

238 239 240 241
	switch (policy) {
	case DNS_RPZ_POLICY_PASSTHRU:
		str = "PASSTHRU";
		break;
Evan Hunt's avatar
Evan Hunt committed
242 243 244 245 246 247
	case DNS_RPZ_POLICY_DROP:
		str = "DROP";
		break;
	case DNS_RPZ_POLICY_TCP_ONLY:
		str = "TCP-ONLY";
		break;
248 249 250 251 252 253 254
	case DNS_RPZ_POLICY_NXDOMAIN:
		str = "NXDOMAIN";
		break;
	case DNS_RPZ_POLICY_NODATA:
		str = "NODATA";
		break;
	case DNS_RPZ_POLICY_RECORD:
255
		str = "Local-Data";
256 257 258 259 260
		break;
	case DNS_RPZ_POLICY_CNAME:
	case DNS_RPZ_POLICY_WILDCNAME:
		str = "CNAME";
		break;
261 262 263
	case DNS_RPZ_POLICY_MISS:
		str = "MISS";
		break;
264 265
	default:
		str = "";
Mark Andrews's avatar
Mark Andrews committed
266
		POST(str);
267 268 269 270
		INSIST(0);
	}
	return (str);
}
271

272 273 274 275
/*
 * Return the bit number of the highest set bit in 'zbit'.
 * (for example, 0x01 returns 0, 0xFF returns 7, etc.)
 */
276 277 278 279
static int
zbit_to_num(dns_rpz_zbits_t zbit) {
	dns_rpz_num_t rpz_num;

280
	REQUIRE(zbit != 0);
281 282 283 284 285
	rpz_num = 0;
#if DNS_RPZ_MAX_ZONES > 32
	if ((zbit & 0xffffffff00000000L) != 0) {
		zbit >>= 32;
		rpz_num += 32;
286
	}
287 288 289 290
#endif
	if ((zbit & 0xffff0000) != 0) {
		zbit >>= 16;
		rpz_num += 16;
291
	}
292 293 294 295 296 297 298 299 300 301 302 303 304 305 306
	if ((zbit & 0xff00) != 0) {
		zbit >>= 8;
		rpz_num += 8;
	}
	if ((zbit & 0xf0) != 0) {
		zbit >>= 4;
		rpz_num += 4;
	}
	if ((zbit & 0xc) != 0) {
		zbit >>= 2;
		rpz_num += 2;
	}
	if ((zbit & 2) != 0)
		++rpz_num;
	return (rpz_num);
307 308
}

Evan Hunt's avatar
Evan Hunt committed
309 310 311 312 313 314
/*
 * Make a set of bit masks given one or more bits and their type.
 */
static void
make_addr_set(dns_rpz_addr_zbits_t *tgt_set, dns_rpz_zbits_t zbits,
	      dns_rpz_type_t type)
315 316
{
	switch (type) {
Evan Hunt's avatar
Evan Hunt committed
317 318 319 320 321
	case DNS_RPZ_TYPE_CLIENT_IP:
		tgt_set->client_ip = zbits;
		tgt_set->ip = 0;
		tgt_set->nsip = 0;
		break;
322
	case DNS_RPZ_TYPE_IP:
Evan Hunt's avatar
Evan Hunt committed
323 324 325
		tgt_set->client_ip = 0;
		tgt_set->ip = zbits;
		tgt_set->nsip = 0;
326 327
		break;
	case DNS_RPZ_TYPE_NSIP:
Evan Hunt's avatar
Evan Hunt committed
328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349
		tgt_set->client_ip = 0;
		tgt_set->ip = 0;
		tgt_set->nsip = zbits;
		break;
	default:
		INSIST(0);
		break;
	}
}

static void
make_nm_set(dns_rpz_nm_zbits_t *tgt_set,
	    dns_rpz_num_t rpz_num, dns_rpz_type_t type)
{
	switch (type) {
	case DNS_RPZ_TYPE_QNAME:
		tgt_set->qname = DNS_RPZ_ZBIT(rpz_num);
		tgt_set->ns = 0;
		break;
	case DNS_RPZ_TYPE_NSDNAME:
		tgt_set->qname = 0;
		tgt_set->ns = DNS_RPZ_ZBIT(rpz_num);
350 351 352 353 354
		break;
	default:
		INSIST(0);
		break;
	}
355 356 357
}

/*
Evan Hunt's avatar
Evan Hunt committed
358
 * Mark a node and all of its parents as having client-IP, IP, or NSIP data
359
 */
360 361 362
static void
set_sum_pair(dns_rpz_cidr_node_t *cnode) {
	dns_rpz_cidr_node_t *child;
Evan Hunt's avatar
Evan Hunt committed
363
	dns_rpz_addr_zbits_t sum;
364

365
	do {
Evan Hunt's avatar
Evan Hunt committed
366
		sum = cnode->set;
367

368 369
		child = cnode->child[0];
		if (child != NULL) {
Evan Hunt's avatar
Evan Hunt committed
370 371 372
			sum.client_ip |= child->sum.client_ip;
			sum.ip |= child->sum.ip;
			sum.nsip |= child->sum.nsip;
373
		}
374

375 376
		child = cnode->child[1];
		if (child != NULL) {
Evan Hunt's avatar
Evan Hunt committed
377 378 379
			sum.client_ip |= child->sum.client_ip;
			sum.ip |= child->sum.ip;
			sum.nsip |= child->sum.nsip;
380
		}
381

Evan Hunt's avatar
Evan Hunt committed
382 383 384
		if (cnode->sum.client_ip == sum.client_ip &&
		    cnode->sum.ip == sum.ip &&
		    cnode->sum.nsip == sum.nsip)
385 386 387 388
			break;
		cnode->sum = sum;
		cnode = cnode->parent;
	} while (cnode != NULL);
389 390
}

391
/* Caller must hold rpzs->maint_lock */
392 393
static void
fix_qname_skip_recurse(dns_rpz_zones_t *rpzs) {
394 395
	dns_rpz_zbits_t mask;

Evan Hunt's avatar
Evan Hunt committed
396 397
	/*
	 * qname_wait_recurse and qname_skip_recurse are used to
398 399 400 401 402 403 404 405 406 407 408
	 * implement the "qname-wait-recurse" config option.
	 *
	 * By default, "qname-wait-recurse" is yes, so no
	 * processing happens without recursion. In this case,
	 * qname_wait_recurse is true, and qname_skip_recurse
	 * (a bit field indicating which policy zones can be
	 * processed without recursion) is set to all 0's by
	 * fix_qname_skip_recurse().
	 *
	 * When "qname-wait-recurse" is no, qname_skip_recurse may be
	 * set to a non-zero value by fix_qname_skip_recurse(). The mask
Evan Hunt's avatar
Evan Hunt committed
409
	 * has to have bits set for the policy zones for which
410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460
	 * processing may continue without recursion, and bits cleared
	 * for the rest.
	 *
	 * (1) The ARM says:
	 *
	 *   The "qname-wait-recurse no" option overrides that default
	 *   behavior when recursion cannot change a non-error
	 *   response. The option does not affect QNAME or client-IP
	 *   triggers in policy zones listed after other zones
	 *   containing IP, NSIP and NSDNAME triggers, because those may
	 *   depend on the A, AAAA, and NS records that would be found
	 *   during recursive resolution.
	 *
	 * Let's consider the following:
	 *
	 *     zbits_req = (rpzs->have.ipv4 | rpzs->have.ipv6 |
	 *		    rpzs->have.nsdname |
	 *		    rpzs->have.nsipv4 | rpzs->have.nsipv6);
	 *
	 * zbits_req now contains bits set for zones which require
	 * recursion.
	 *
	 * But going by the description in the ARM, if the first policy
	 * zone requires recursion, then all zones after that (higher
	 * order bits) have to wait as well.  If the Nth zone requires
	 * recursion, then (N+1)th zone onwards all need to wait.
	 *
	 * So mapping this, examples:
	 *
	 * zbits_req = 0b000  mask = 0xffffffff (no zones have to wait for
	 *					 recursion)
	 * zbits_req = 0b001  mask = 0x00000000 (all zones have to wait)
	 * zbits_req = 0b010  mask = 0x00000001 (the first zone doesn't have to
	 *					 wait, second zone onwards need
	 *					 to wait)
	 * zbits_req = 0b011  mask = 0x00000000 (all zones have to wait)
	 * zbits_req = 0b100  mask = 0x00000011 (the 1st and 2nd zones don't
	 *					 have to wait, third zone
	 *					 onwards need to wait)
	 *
	 * More generally, we have to count the number of trailing 0
	 * bits in zbits_req and only these can be processed without
	 * recursion. All the rest need to wait.
	 *
	 * (2) The ARM says that "qname-wait-recurse no" option
	 * overrides the default behavior when recursion cannot change a
	 * non-error response. So, in the order of listing of policy
	 * zones, within the first policy zone where recursion may be
	 * required, we should first allow CLIENT-IP and QNAME policy
	 * records to be attempted without recursion.
	 */
461

462 463 464 465 466
	/*
	 * Get a mask covering all policy zones that are not subordinate to
	 * other policy zones containing triggers that require that the
	 * qname be resolved before they can be checked.
	 */
467 468 469 470
	rpzs->have.client_ip = rpzs->have.client_ipv4 | rpzs->have.client_ipv6;
	rpzs->have.ip = rpzs->have.ipv4 | rpzs->have.ipv6;
	rpzs->have.nsip = rpzs->have.nsipv4 | rpzs->have.nsipv6;

471
	if (rpzs->p.qname_wait_recurse) {
472
		mask = 0;
473
	} else {
474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491
		dns_rpz_zbits_t zbits_req;
		dns_rpz_zbits_t zbits_notreq;
		dns_rpz_zbits_t mask2;
		dns_rpz_zbits_t req_mask;

		/*
		 * Get the masks of zones with policies that
		 * do/don't require recursion
		 */

		zbits_req = (rpzs->have.ipv4 | rpzs->have.ipv6 |
			     rpzs->have.nsdname |
			     rpzs->have.nsipv4 | rpzs->have.nsipv6);
		zbits_notreq = (rpzs->have.client_ip | rpzs->have.qname);

		if (zbits_req == 0) {
			mask = DNS_RPZ_ALL_ZBITS;
			goto set;
492
		}
493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526

		/*
		 * req_mask is a mask covering used bits in
		 * zbits_req. (For instance, 0b1 => 0b1, 0b101 => 0b111,
		 * 0b11010101 => 0b11111111).
		 */
		req_mask = zbits_req;
		req_mask |= req_mask >> 1;
		req_mask |= req_mask >> 2;
		req_mask |= req_mask >> 4;
		req_mask |= req_mask >> 8;
		req_mask |= req_mask >> 16;
#if DNS_RPZ_MAX_ZONES > 32
		req_mask |= req_mask >> 32;
#endif

		/*
		 * There's no point in skipping recursion for a later
		 * zone if it is required in a previous zone.
		 */
		if ((zbits_notreq & req_mask) == 0) {
			mask = 0;
			goto set;
		}

		/*
		 * This bit arithmetic creates a mask of zones in which
		 * it is okay to skip recursion. After the first zone
		 * that has to wait for recursion, all the others have
		 * to wait as well, so we want to create a mask in which
		 * all the trailing zeroes in zbits_req are are 1, and
		 * more significant bits are 0. (For instance,
		 * 0x0700 => 0x00ff, 0x0007 => 0x0000)
		 */
527
		mask = ~(zbits_req | ((~zbits_req) + 1));
528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552

		/*
		 * As mentioned in (2) above, the zone corresponding to
		 * the least significant zero could have its CLIENT-IP
		 * and QNAME policies checked before recursion, if it
		 * has any of those policies.  So if it does, we
		 * can set its 0 to 1.
		 *
		 * Locate the least significant 0 bit in the mask (for
		 * instance, 0xff => 0x100)...
		 */
		mask2 = (mask << 1) & ~mask;

		/*
		 * Also set the bit for zone 0, because if it's in
		 * zbits_notreq then it's definitely okay to attempt to
		 * skip recursion for zone 0...
		 */
		mask2 |= 1;

		/* Clear any bits *not* in zbits_notreq... */
		mask2 &= zbits_notreq;

		/* And merge the result into the skip-recursion mask */
		mask |= mask2;
553
	}
554

555 556 557 558 559 560
 set:
	isc_log_write(dns_lctx, DNS_LOGCATEGORY_RPZ, DNS_LOGMODULE_RBTDB,
		      DNS_RPZ_DEBUG_QUIET,
		      "computed RPZ qname_skip_recurse mask=0x%llx",
		      (isc_uint64_t) mask);
	rpzs->have.qname_skip_recurse = mask;
561 562 563
}

static void
564 565 566 567 568
adj_trigger_cnt(dns_rpz_zones_t *rpzs, dns_rpz_num_t rpz_num,
		dns_rpz_type_t rpz_type,
		const dns_rpz_cidr_key_t *tgt_ip, dns_rpz_prefix_t tgt_prefix,
		isc_boolean_t inc)
{
569
	dns_rpz_trigger_counter_t *cnt;
570
	dns_rpz_zbits_t *have;
571

572
	switch (rpz_type) {
Evan Hunt's avatar
Evan Hunt committed
573 574 575 576 577 578 579 580 581 582
	case DNS_RPZ_TYPE_CLIENT_IP:
		REQUIRE(tgt_ip != NULL);
		if (KEY_IS_IPV4(tgt_prefix, tgt_ip)) {
			cnt = &rpzs->triggers[rpz_num].client_ipv4;
			have = &rpzs->have.client_ipv4;
		} else {
			cnt = &rpzs->triggers[rpz_num].client_ipv6;
			have = &rpzs->have.client_ipv6;
		}
		break;
583
	case DNS_RPZ_TYPE_QNAME:
Evan Hunt's avatar
Evan Hunt committed
584
		cnt = &rpzs->triggers[rpz_num].qname;
585 586 587 588 589
		have = &rpzs->have.qname;
		break;
	case DNS_RPZ_TYPE_IP:
		REQUIRE(tgt_ip != NULL);
		if (KEY_IS_IPV4(tgt_prefix, tgt_ip)) {
Evan Hunt's avatar
Evan Hunt committed
590
			cnt = &rpzs->triggers[rpz_num].ipv4;
591 592
			have = &rpzs->have.ipv4;
		} else {
Evan Hunt's avatar
Evan Hunt committed
593
			cnt = &rpzs->triggers[rpz_num].ipv6;
594 595 596 597
			have = &rpzs->have.ipv6;
		}
		break;
	case DNS_RPZ_TYPE_NSDNAME:
Evan Hunt's avatar
Evan Hunt committed
598
		cnt = &rpzs->triggers[rpz_num].nsdname;
599 600 601 602 603
		have = &rpzs->have.nsdname;
		break;
	case DNS_RPZ_TYPE_NSIP:
		REQUIRE(tgt_ip != NULL);
		if (KEY_IS_IPV4(tgt_prefix, tgt_ip)) {
Evan Hunt's avatar
Evan Hunt committed
604
			cnt = &rpzs->triggers[rpz_num].nsipv4;
605 606
			have = &rpzs->have.nsipv4;
		} else {
Evan Hunt's avatar
Evan Hunt committed
607
			cnt = &rpzs->triggers[rpz_num].nsipv6;
608 609 610 611 612 613 614 615
			have = &rpzs->have.nsipv6;
		}
		break;
	default:
		INSIST(0);
	}

	if (inc) {
Mark Andrews's avatar
Mark Andrews committed
616
		if (++*cnt == 1U) {
617 618 619 620
			*have |= DNS_RPZ_ZBIT(rpz_num);
			fix_qname_skip_recurse(rpzs);
		}
	} else {
Mark Andrews's avatar
Mark Andrews committed
621 622
		REQUIRE(*cnt != 0U);
		if (--*cnt == 0U) {
623 624 625
			*have &= ~DNS_RPZ_ZBIT(rpz_num);
			fix_qname_skip_recurse(rpzs);
		}
626 627 628 629
	}
}

static dns_rpz_cidr_node_t *
630 631 632
new_node(dns_rpz_zones_t *rpzs,
	 const dns_rpz_cidr_key_t *ip, dns_rpz_prefix_t prefix,
	 const dns_rpz_cidr_node_t *child)
633
{
634
	dns_rpz_cidr_node_t *new;
635 636
	int i, words, wlen;

637 638
	new = isc_mem_get(rpzs->mctx, sizeof(*new));
	if (new == NULL)
639
		return (NULL);
640
	memset(new, 0, sizeof(*new));
641

642 643
	if (child != NULL)
		new->sum = child->sum;
644

645 646 647
	new->prefix = prefix;
	words = prefix / DNS_RPZ_CIDR_WORD_BITS;
	wlen = prefix % DNS_RPZ_CIDR_WORD_BITS;
648 649
	i = 0;
	while (i < words) {
650
		new->ip.w[i] = ip->w[i];
651 652 653
		++i;
	}
	if (wlen != 0) {
654
		new->ip.w[i] = ip->w[i] & DNS_RPZ_WORD_MASK(wlen);
655 656 657
		++i;
	}
	while (i < DNS_RPZ_CIDR_WORDS)
658
		new->ip.w[i++] = 0;
659

660
	return (new);
661 662 663
}

static void
664
badname(int level, const dns_name_t *name, const char *str1, const char *str2) {
665
	char namebuf[DNS_NAME_FORMATSIZE];
666

667 668 669
	/*
	 * bin/tests/system/rpz/tests.sh looks for "invalid rpz".
	 */
Evan Hunt's avatar
Evan Hunt committed
670 671
	if (level < DNS_RPZ_DEBUG_QUIET &&
	    isc_log_wouldlog(dns_lctx, level)) {
672
		dns_name_format(name, namebuf, sizeof(namebuf));
673
		isc_log_write(dns_lctx, DNS_LOGCATEGORY_RPZ,
674
			      DNS_LOGMODULE_RBTDB, level,
675
			      "invalid rpz IP address \"%s\"%s%s",
676
			      namebuf, str1, str2);
677 678 679 680 681
	}
}

/*
 * Convert an IP address from radix tree binary (host byte order) to
682
 * to its canonical response policy domain name without the origin of the
683 684 685
 * policy zone.
 */
static isc_result_t
686
ip2name(const dns_rpz_cidr_key_t *tgt_ip, dns_rpz_prefix_t tgt_prefix,
687
	const dns_name_t *base_name, dns_name_t *ip_name)
688 689 690 691 692 693 694 695 696 697 698
{
#ifndef INET6_ADDRSTRLEN
#define INET6_ADDRSTRLEN 46
#endif
	int w[DNS_RPZ_CIDR_WORDS*2];
	char str[1+8+1+INET6_ADDRSTRLEN+1];
	isc_buffer_t buffer;
	isc_result_t result;
	isc_boolean_t zeros;
	int i, n, len;

699
	if (KEY_IS_IPV4(tgt_prefix, tgt_ip)) {
700 701 702 703 704 705
		len = snprintf(str, sizeof(str), "%d.%d.%d.%d.%d",
			       tgt_prefix - 96,
			       tgt_ip->w[3] & 0xff,
			       (tgt_ip->w[3]>>8) & 0xff,
			       (tgt_ip->w[3]>>16) & 0xff,
			       (tgt_ip->w[3]>>24) & 0xff);
706
		if (len < 0 || len > (int)sizeof(str))
707 708 709 710 711 712 713 714 715 716 717 718 719
			return (ISC_R_FAILURE);
	} else {
		for (i = 0; i < DNS_RPZ_CIDR_WORDS; i++) {
			w[i*2+1] = ((tgt_ip->w[DNS_RPZ_CIDR_WORDS-1-i] >> 16)
				    & 0xffff);
			w[i*2] = tgt_ip->w[DNS_RPZ_CIDR_WORDS-1-i] & 0xffff;
		}
		zeros = ISC_FALSE;
		len = snprintf(str, sizeof(str), "%d", tgt_prefix);
		if (len == -1)
			return (ISC_R_FAILURE);
		i = 0;
		while (i < DNS_RPZ_CIDR_WORDS * 2) {
Evan Hunt's avatar
Evan Hunt committed
720 721 722
			if (w[i] != 0 || zeros ||
			    i >= DNS_RPZ_CIDR_WORDS * 2 - 1 ||
			    w[i+1] != 0) {
723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740
				INSIST((size_t)len <= sizeof(str));
				n = snprintf(&str[len], sizeof(str) - len,
					     ".%x", w[i++]);
				if (n < 0)
					return (ISC_R_FAILURE);
				len += n;
			} else {
				zeros = ISC_TRUE;
				INSIST((size_t)len <= sizeof(str));
				n = snprintf(&str[len], sizeof(str) - len,
					     ".zz");
				if (n < 0)
					return (ISC_R_FAILURE);
				len += n;
				i += 2;
				while (i < DNS_RPZ_CIDR_WORDS * 2 && w[i] == 0)
					++i;
			}
Evan Hunt's avatar
Evan Hunt committed
741
			if (len >= (int)sizeof(str))
742 743 744 745
				return (ISC_R_FAILURE);
		}
	}

746 747
	isc_buffer_init(&buffer, str, sizeof(str));
	isc_buffer_add(&buffer, len);
748 749
	result = dns_name_fromtext(ip_name, &buffer, base_name, 0, NULL);
	return (result);
750 751 752
}

/*
753
 * Determine the type a of a name in a response policy zone.
754 755
 */
static dns_rpz_type_t
756
type_from_name(dns_rpz_zone_t *rpz, const dns_name_t *name) {
757

758
	if (dns_name_issubdomain(name, &rpz->ip))
759 760
		return (DNS_RPZ_TYPE_IP);

Evan Hunt's avatar
Evan Hunt committed
761 762 763
	if (dns_name_issubdomain(name, &rpz->client_ip))
		return (DNS_RPZ_TYPE_CLIENT_IP);

764
#ifdef ENABLE_RPZ_NSIP
765
	if (dns_name_issubdomain(name, &rpz->nsip))
766 767 768 769
		return (DNS_RPZ_TYPE_NSIP);
#endif

#ifdef ENABLE_RPZ_NSDNAME
770
	if (dns_name_issubdomain(name, &rpz->nsdname))
771 772 773 774 775 776 777 778
		return (DNS_RPZ_TYPE_NSDNAME);
#endif

	return (DNS_RPZ_TYPE_QNAME);
}

/*
 * Convert an IP address from canonical response policy domain name form
779 780
 * to radix tree binary (host byte order) for adding or deleting IP or NSIP
 * data.
781 782
 */
static isc_result_t
783 784
name2ipkey(int log_level,
	   const dns_rpz_zones_t *rpzs, dns_rpz_num_t rpz_num,
785
	   dns_rpz_type_t rpz_type, const dns_name_t *src_name,
786
	   dns_rpz_cidr_key_t *tgt_ip, dns_rpz_prefix_t *tgt_prefix,
Evan Hunt's avatar
Evan Hunt committed
787
	   dns_rpz_addr_zbits_t *new_set)
788
{
789 790 791 792 793
	dns_rpz_zone_t *rpz;
	char ip_str[DNS_NAME_FORMATSIZE];
	dns_offsets_t ip_name_offsets;
	dns_fixedname_t ip_name2f;
	dns_name_t ip_name, *ip_name2;
794
	const char *prefix_str, *cp, *end;
795 796
	char *cp2;
	int ip_labels;
797 798 799
	dns_rpz_prefix_t prefix;
	unsigned long prefix_num, l;
	isc_result_t result;
800 801
	int i;

802 803 804 805
	REQUIRE(rpzs != NULL && rpz_num < rpzs->p.num_zones);
	rpz = rpzs->zones[rpz_num];
	REQUIRE(rpz != NULL);

Evan Hunt's avatar
Evan Hunt committed
806
	make_addr_set(new_set, DNS_RPZ_ZBIT(rpz_num), rpz_type);
807

808
	ip_labels = dns_name_countlabels(src_name);
809 810 811 812 813 814
	if (rpz_type == DNS_RPZ_TYPE_QNAME)
		ip_labels -= dns_name_countlabels(&rpz->origin);
	else
		ip_labels -= dns_name_countlabels(&rpz->nsdname);
	if (ip_labels < 2) {
		badname(log_level, src_name, "; too short", "");
815 816
		return (ISC_R_FAILURE);
	}
817 818
	dns_name_init(&ip_name, ip_name_offsets);
	dns_name_getlabelsequence(src_name, 0, ip_labels, &ip_name);
819 820

	/*
821
	 * Get text for the IP address
822
	 */
823 824 825 826 827
	dns_name_format(&ip_name, ip_str, sizeof(ip_str));
	end = &ip_str[strlen(ip_str)+1];
	prefix_str = ip_str;

	prefix_num = strtoul(prefix_str, &cp2, 10);
828
	if (*cp2 != '.') {
829
		badname(log_level, src_name,
830 831 832 833
			"; invalid leading prefix length", "");
		return (ISC_R_FAILURE);
	}
	*cp2 = '\0';
834 835
	if (prefix_num < 1U || prefix_num > 128U) {
		badname(log_level, src_name,
836
			"; invalid prefix length of ", prefix_str);
837 838 839 840
		return (ISC_R_FAILURE);
	}
	cp = cp2+1;

841
	if (--ip_labels == 4 && !strchr(cp, 'z')) {
842 843
		/*
		 * Convert an IPv4 address
844
		 * from the form "prefix.z.y.x.w"
845
		 */
846 847
		if (prefix_num > 32U) {
			badname(log_level, src_name,
848
				"; invalid IPv4 prefix length of ", prefix_str);
849 850
			return (ISC_R_FAILURE);
		}
851 852
		prefix_num += 96;
		*tgt_prefix = (dns_rpz_prefix_t)prefix_num;
853 854 855 856 857 858
		tgt_ip->w[0] = 0;
		tgt_ip->w[1] = 0;
		tgt_ip->w[2] = ADDR_V4MAPPED;
		tgt_ip->w[3] = 0;
		for (i = 0; i < 32; i += 8) {
			l = strtoul(cp, &cp2, 10);
Mark Andrews's avatar
Mark Andrews committed
859
			if (l > 255U || (*cp2 != '.' && *cp2 != '\0')) {
860 861
				if (*cp2 == '.')
					*cp2 = '\0';
862
				badname(log_level, src_name,
863
					"; invalid IPv4 octet ", cp);
864 865 866 867 868 869 870 871 872
				return (ISC_R_FAILURE);
			}
			tgt_ip->w[3] |= l << i;
			cp = cp2 + 1;
		}
	} else {
		/*
		 * Convert a text IPv6 address.
		 */
873
		*tgt_prefix = (dns_rpz_prefix_t)prefix_num;
874 875 876 877 878 879 880 881 882 883 884 885 886 887
		for (i = 0;
		     ip_labels > 0 && i < DNS_RPZ_CIDR_WORDS * 2;
		     ip_labels--) {
			if (cp[0] == 'z' && cp[1] == 'z' &&
			    (cp[2] == '.' || cp[2] == '\0') &&
			    i <= 6) {
				do {
					if ((i & 1) == 0)
					    tgt_ip->w[3-i/2] = 0;
					++i;
				} while (ip_labels + i <= 8);
				cp += 3;
			} else {
				l = strtoul(cp, &cp2, 16);
Mark Andrews's avatar
Mark Andrews committed
888
				if (l > 0xffffu ||
889
				    (*cp2 != '.' && *cp2 != '\0')) {
890 891
					if (*cp2 == '.')
					    *cp2 = '\0';
892
					badname(log_level, src_name,
893
						"; invalid IPv6 word ", cp);
894 895 896 897 898 899 900 901 902 903 904 905
					return (ISC_R_FAILURE);
				}
				if ((i & 1) == 0)
					tgt_ip->w[3-i/2] = l;
				else
					tgt_ip->w[3-i/2] |= l << 16;
				i++;
				cp = cp2 + 1;
			}
		}
	}
	if (cp != end) {
906
		badname(log_level, src_name, "", "");
907 908 909 910 911 912
		return (ISC_R_FAILURE);
	}

	/*
	 * Check for 1s after the prefix length.
	 */
913 914
	prefix = (dns_rpz_prefix_t)prefix_num;
	while (prefix < DNS_RPZ_CIDR_KEY_BITS) {
915 916
		dns_rpz_cidr_word_t aword;

917 918
		i = prefix % DNS_RPZ_CIDR_WORD_BITS;
		aword = tgt_ip->w[prefix / DNS_RPZ_CIDR_WORD_BITS];
919
		if ((aword & ~DNS_RPZ_WORD_MASK(i)) != 0) {
920
			badname(log_level, src_name,
921
				"; too small prefix length of ", prefix_str);
922 923
			return (ISC_R_FAILURE);
		}
924 925
		prefix -= i;
		prefix += DNS_RPZ_CIDR_WORD_BITS;
926 927
	}

928 929 930 931 932 933
	/*
	 * XXXMUKS: Should the following check be enabled in a
	 * production build?  It can be expensive for large IP zones
	 * from 3rd parties.
	 */

934
	/*
935 936
	 * Convert the address back to a canonical domain name
	 * to ensure that the original name is in canonical form.
937
	 */
938 939 940 941 942
	dns_fixedname_init(&ip_name2f);
	ip_name2 = dns_fixedname_name(&ip_name2f);
	result = ip2name(tgt_ip, (dns_rpz_prefix_t)prefix_num, NULL, ip_name2);
	if (result != ISC_R_SUCCESS || !dns_name_equal(&ip_name, ip_name2)) {
		badname(log_level, src_name, "; not canonical", "");
943 944 945 946 947 948 949
		return (ISC_R_FAILURE);
	}

	return (ISC_R_SUCCESS);
}

/*
950 951
 * Get trigger name and data bits for adding or deleting summary NSDNAME
 * or QNAME data.
952
 */
953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973
static void
name2data(dns_rpz_zones_t *rpzs, dns_rpz_num_t rpz_num,
	  dns_rpz_type_t rpz_type, const dns_name_t *src_name,
	  dns_name_t *trig_name, dns_rpz_nm_data_t *new_data)
{
	dns_rpz_zone_t *rpz;
	dns_offsets_t tmp_name_offsets;
	dns_name_t tmp_name;
	unsigned int prefix_len, n;

	REQUIRE(rpzs != NULL && rpz_num < rpzs->p.num_zones);
	rpz = rpzs->zones[rpz_num];
	REQUIRE(rpz != NULL);

	/*
	 * Handle wildcards by putting only the parent into the
	 * summary RBT.  The summary database only causes a check of the
	 * real policy zone where wildcards will be handled.
	 */
	if (dns_name_iswildcard(src_name)) {
		prefix_len = 1;
Evan Hunt's avatar
Evan Hunt committed
974 975
		memset(&new_data->set, 0, sizeof(new_data->set));
		make_nm_set(&new_data->wild, rpz_num, rpz_type);
976 977
	} else {
		prefix_len = 0;
Evan Hunt's avatar
Evan Hunt committed
978 979
		make_nm_set(&new_data->set, rpz_num, rpz_type);
		memset(&new_data->wild, 0, sizeof(new_data->wild));
980 981 982 983 984 985 986 987 988 989 990 991 992
	}

	dns_name_init(&tmp_name, tmp_name_offsets);
	n = dns_name_countlabels(src_name);
	n -= prefix_len;
	if (rpz_type == DNS_RPZ_TYPE_QNAME)
		n -= dns_name_countlabels(&rpz->origin);
	else
		n -= dns_name_countlabels(&rpz->nsdname);
	dns_name_getlabelsequence(src_name, prefix_len, n, &tmp_name);
	(void)dns_name_concatenate(&tmp_name, dns_rootname, trig_name, NULL);
}

993 994 995 996
#ifndef HAVE_BUILTIN_CLZ
/**
 * \brief Count Leading Zeros: Find the location of the left-most set
 * bit.
997
 */
998 999 1000
static inline unsigned int
clz(dns_rpz_cidr_word_t w) {
	unsigned int bit;
1001

1002
	bit = DNS_RPZ_CIDR_WORD_BITS-1;
1003

1004 1005 1006 1007
	if ((w & 0xffff0000) != 0) {
		w >>= 16;
		bit -= 16;
	}
1008

1009 1010 1011 1012
	if ((w & 0xff00) != 0) {
		w >>= 8;
		bit -= 8;
	}
1013

1014 1015 1016 1017
	if ((w & 0xf0) != 0) {
		w >>= 4;
		bit -= 4;
	}
1018

1019 1020 1021 1022
	if ((w & 0xc) != 0) {
		w >>= 2;
		bit -= 2;
	}
1023

1024 1025
	if ((w & 2) != 0)
		--bit;
1026

1027 1028
	return (bit);
}
1029
#endif
1030 1031

/*
1032
 * Find the first differing bit in two keys (IP addresses).
1033 1034
 */
static int
1035 1036
diff_keys(const dns_rpz_cidr_key_t *key1, dns_rpz_prefix_t prefix1,
	  const dns_rpz_cidr_key_t *key2, dns_rpz_prefix_t prefix2)
1037 1038
{
	dns_rpz_cidr_word_t delta;
1039
	dns_rpz_prefix_t maxbit, bit;
1040 1041
	int i;

1042
	bit = 0;
1043
	maxbit = ISC_MIN(prefix1, prefix2);
1044 1045 1046 1047

	/*
	 * find the first differing words
	 */
1048
	for (i = 0; bit < maxbit; i++, bit += DNS_RPZ_CIDR_WORD_BITS) {
1049
		delta = key1->w[i] ^ key2->w[i];
1050 1051 1052 1053 1054 1055
		if (ISC_UNLIKELY(delta != 0)) {
#ifdef HAVE_BUILTIN_CLZ
			bit += __builtin_clz(delta);
#else
			bit += clz(delta);
#endif
1056 1057 1058 1059 1060 1061
			break;
		}
	}
	return (ISC_MIN(bit, maxbit));
}

1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074
/*
 * Given a hit while searching the radix trees,
 * clear all bits for higher numbered zones.
 */
static inline dns_rpz_zbits_t
trim_zbits(dns_rpz_zbits_t zbits, dns_rpz_zbits_t found) {
	dns_rpz_zbits_t x;

	/*
	 * Isolate the first or smallest numbered hit bit.
	 * Make a mask of that bit and all smaller numbered bits.
	 */
	x = zbits & found;
1075
	x &= (~x + 1);
1076 1077 1078 1079
	x = (x << 1) - 1;
	return (zbits &= x);
}

1080 1081 1082 1083
/*
 * Search a radix tree for an IP address for ordinary lookup
 *	or for a CIDR block adding or deleting an entry
 *
1084 1085 1086
 * Return ISC_R_SUCCESS, DNS_R_PARTIALMATCH, ISC_R_NOTFOUND,
 *	    and *found=longest match node
 *	or with create==ISC_TRUE, ISC_R_EXISTS or ISC_R_NOMEMORY
1087 1088
 */
static isc_result_t
1089 1090
search(dns_rpz_zones_t *rpzs,
       const dns_rpz_cidr_key_t *tgt_ip, dns_rpz_prefix_t tgt_prefix,
Evan Hunt's avatar
Evan Hunt committed
1091
       const dns_rpz_addr_zbits_t *tgt_set, isc_boolean_t create,
1092
       dns_rpz_cidr_node_t **found)
1093 1094
{
	dns_rpz_cidr_node_t *cur, *parent, *child, *new_parent, *sibling;
Evan Hunt's avatar
Evan Hunt committed
1095
	dns_rpz_addr_zbits_t set;
1096
	int cur_num, child_num;
1097
	dns_rpz_prefix_t dbit;
1098 1099
	isc_result_t find_result;

Evan Hunt's avatar
Evan Hunt committed
1100
	set = *tgt_set;
1101
	find_result = ISC_R_NOTFOUND;
1102 1103
	*found = NULL;
	cur = rpzs->cidr;
1104 1105 1106 1107 1108
	parent = NULL;
	cur_num = 0;
	for (;;) {
		if (cur == NULL) {
			/*
1109 1110 1111
			 * No child so we cannot go down.
			 * Quit with whatever we already found
			 * or add the target as a child of the current parent.
1112 1113 1114
			 */
			if (!create)
				return (find_result);
1115
			child = new_node(rpzs, tgt_ip, tgt_prefix, NULL);
1116 1117 1118
			if (child == NULL)
				return (ISC_R_NOMEMORY);
			if (parent == NULL)
1119
				rpzs->cidr = child;
1120 1121 1122
			else
				parent->child[cur_num] = child;
			child->parent = parent;
Evan Hunt's avatar
Evan Hunt committed
1123 1124 1125
			child->set.client_ip |= tgt_set->client_ip;
			child->set.ip |= tgt_set->ip;
			child->set.nsip |= tgt_set->nsip;
1126
			set_sum_pair(child);
1127
			*found = child;
1128 1129 1130
			return (ISC_R_SUCCESS);
		}

Evan Hunt's avatar
Evan Hunt committed
1131 1132 1133
		if ((cur->sum.client_ip & set.client_ip) == 0 &&
		    (cur->sum.ip & set.ip) == 0 &&
		    (cur->sum.nsip & set.nsip) == 0) {
1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144
			/*
			 * This node has no relevant data
			 * and is in none of the target trees.
			 * Pretend it does not exist if we are not adding.
			 *
			 * If we are adding, continue down to eventually add
			 * a node and mark/put this node in the correct tree.
			 */
			if (!create)
				return (find_result);
		}
1145

1146
		dbit = diff_keys(tgt_ip, tgt_prefix, &cur->ip, cur->prefix);