rpz.c 54.8 KB
Newer Older
1
/*
Tinderbox User's avatar
Tinderbox User committed
2
 * Copyright (C) 2011-2014  Internet Systems Consortium, Inc. ("ISC")
3
4
5
6
7
8
9
10
11
12
13
14
15
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
 */
Tinderbox User's avatar
Tinderbox User committed
16
17

/* $Id$ */
18
19
20
21
22
23
24
25
26
27


/*! \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
28
#include <isc/print.h>
29
30
31
32
33
34
35
36
37
38
39
#include <isc/stdlib.h>
#include <isc/string.h>
#include <isc/util.h>

#include <dns/db.h>
#include <dns/fixedname.h>
#include <dns/log.h>
#include <dns/rdata.h>
#include <dns/rdataset.h>
#include <dns/rdatastruct.h>
#include <dns/result.h>
40
#include <dns/rbt.h>
41
42
43
44
45
46
47
#include <dns/rpz.h>
#include <dns/view.h>


/*
 * Parallel radix trees for databases of response policy IP addresses
 *
48
49
50
51
52
53
54
 * 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.
55
56
57
58
59
60
61
62
 *
 * 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
 * response response zone.  The policy data such as a CNAME or an A record
 * 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.
 *
63
64
 *
 * The response policy zone canonical form of an IPv6 address is one of:
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
 *	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
 *
81
 * Names for IPv4 addresses are distinguished from IPv6 addresses by having
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 * 5 labels all of which are numbers, and a prefix between 1 and 32.
 */


/*
 * 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
99
100
101
102
103
104
#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))))
105

106
107
108
109
110
111
/*
 * 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))))
112

113
/*
Evan Hunt's avatar
Evan Hunt committed
114
115
 * A triplet of arrays of bits flagging the existence of
 * client-IP, IP, and NSIP policy triggers.
116
 */
Evan Hunt's avatar
Evan Hunt committed
117
118
119
120
121
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;
122
};
123

124
125
126
/*
 * A CIDR or radix tree node.
 */
127
struct dns_rpz_cidr_node {
128
129
130
131
	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
132
133
	dns_rpz_addr_zbits_t	set;
	dns_rpz_addr_zbits_t	sum;
134
135
};

136
137
138
139
140
/*
 * 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.
 */
Evan Hunt's avatar
Evan Hunt committed
141
142
143
144
145
146
147
148
149
150
/*
 * 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;
};

151
152
typedef struct dns_rpz_nm_data dns_rpz_nm_data_t;
struct dns_rpz_nm_data {
Evan Hunt's avatar
Evan Hunt committed
153
154
	dns_rpz_nm_zbits_t	set;
	dns_rpz_nm_zbits_t	wild;
155
156
};

157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#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
176
177

const char *
178
dns_rpz_type2str(dns_rpz_type_t type) {
179
	switch (type) {
Evan Hunt's avatar
Evan Hunt committed
180
181
	case DNS_RPZ_TYPE_CLIENT_IP:
		return ("CLIENT-IP");
182
183
184
185
186
187
188
189
190
191
192
	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;
	}
193
	FATAL_ERROR(__FILE__, __LINE__, "impossible rpz type %d", type);
194
195
196
197
	return ("impossible");
}

dns_rpz_policy_t
198
dns_rpz_str2policy(const char *str) {
Evan Hunt's avatar
Evan Hunt committed
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
	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;

215
216
	if (str == NULL)
		return (DNS_RPZ_POLICY_ERROR);
Evan Hunt's avatar
Evan Hunt committed
217
218
219
220
	for (n = 0; n < sizeof(tbl)/sizeof(tbl[0]); ++n) {
		if (!strcasecmp(tbl[n].str, str))
			return (tbl[n].policy);
	}
221
222
223
	return (DNS_RPZ_POLICY_ERROR);
}

224
225
226
const char *
dns_rpz_policy2str(dns_rpz_policy_t policy) {
	const char *str;
227

228
229
230
231
	switch (policy) {
	case DNS_RPZ_POLICY_PASSTHRU:
		str = "PASSTHRU";
		break;
Evan Hunt's avatar
Evan Hunt committed
232
233
234
235
236
237
	case DNS_RPZ_POLICY_DROP:
		str = "DROP";
		break;
	case DNS_RPZ_POLICY_TCP_ONLY:
		str = "TCP-ONLY";
		break;
238
239
240
241
242
243
244
	case DNS_RPZ_POLICY_NXDOMAIN:
		str = "NXDOMAIN";
		break;
	case DNS_RPZ_POLICY_NODATA:
		str = "NODATA";
		break;
	case DNS_RPZ_POLICY_RECORD:
245
		str = "Local-Data";
246
247
248
249
250
251
252
		break;
	case DNS_RPZ_POLICY_CNAME:
	case DNS_RPZ_POLICY_WILDCNAME:
		str = "CNAME";
		break;
	default:
		str = "";
Mark Andrews's avatar
Mark Andrews committed
253
		POST(str);
254
255
256
257
		INSIST(0);
	}
	return (str);
}
258

259
260
261
262
263
264
265
266
267
268
static int
zbit_to_num(dns_rpz_zbits_t zbit) {
	dns_rpz_num_t rpz_num;

	INSIST(zbit != 0);
	rpz_num = 0;
#if DNS_RPZ_MAX_ZONES > 32
	if ((zbit & 0xffffffff00000000L) != 0) {
		zbit >>= 32;
		rpz_num += 32;
269
	}
270
271
272
273
#endif
	if ((zbit & 0xffff0000) != 0) {
		zbit >>= 16;
		rpz_num += 16;
274
	}
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
	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);
290
291
}

Evan Hunt's avatar
Evan Hunt committed
292
293
294
295
296
297
/*
 * 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)
298
299
{
	switch (type) {
Evan Hunt's avatar
Evan Hunt committed
300
301
302
303
304
	case DNS_RPZ_TYPE_CLIENT_IP:
		tgt_set->client_ip = zbits;
		tgt_set->ip = 0;
		tgt_set->nsip = 0;
		break;
305
	case DNS_RPZ_TYPE_IP:
Evan Hunt's avatar
Evan Hunt committed
306
307
308
		tgt_set->client_ip = 0;
		tgt_set->ip = zbits;
		tgt_set->nsip = 0;
309
310
		break;
	case DNS_RPZ_TYPE_NSIP:
Evan Hunt's avatar
Evan Hunt committed
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
		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);
333
334
335
336
337
		break;
	default:
		INSIST(0);
		break;
	}
338
339
340
}

/*
Evan Hunt's avatar
Evan Hunt committed
341
 * Mark a node and all of its parents as having client-IP, IP, or NSIP data
342
 */
343
344
345
static void
set_sum_pair(dns_rpz_cidr_node_t *cnode) {
	dns_rpz_cidr_node_t *child;
Evan Hunt's avatar
Evan Hunt committed
346
	dns_rpz_addr_zbits_t sum;
347

348
	do {
Evan Hunt's avatar
Evan Hunt committed
349
		sum = cnode->set;
350

351
352
		child = cnode->child[0];
		if (child != NULL) {
Evan Hunt's avatar
Evan Hunt committed
353
354
355
			sum.client_ip |= child->sum.client_ip;
			sum.ip |= child->sum.ip;
			sum.nsip |= child->sum.nsip;
356
		}
357

358
359
		child = cnode->child[1];
		if (child != NULL) {
Evan Hunt's avatar
Evan Hunt committed
360
361
362
			sum.client_ip |= child->sum.client_ip;
			sum.ip |= child->sum.ip;
			sum.nsip |= child->sum.nsip;
363
		}
364

Evan Hunt's avatar
Evan Hunt committed
365
366
367
		if (cnode->sum.client_ip == sum.client_ip &&
		    cnode->sum.ip == sum.ip &&
		    cnode->sum.nsip == sum.nsip)
368
369
370
371
			break;
		cnode->sum = sum;
		cnode = cnode->parent;
	} while (cnode != NULL);
372
373
}

374
375
376
static void
fix_qname_skip_recurse(dns_rpz_zones_t *rpzs) {
	dns_rpz_zbits_t zbits;
377

378
379
380
381
382
383
384
	/*
	 * 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.
	 */
	if (rpzs->p.qname_wait_recurse) {
		zbits = 0;
385
	} else {
386
387
388
389
390
391
392
393
		zbits = (rpzs->have.ipv4 || rpzs->have.ipv6 ||
			 rpzs->have.nsdname ||
			 rpzs->have.nsipv4 || rpzs->have.nsipv6);
		if (zbits == 0) {
			zbits = DNS_RPZ_ALL_ZBITS;
		} else {
			zbits = DNS_RPZ_ZMASK(zbit_to_num(zbits));
		}
394
	}
395
396
	rpzs->have.qname_skip_recurse = zbits;

Evan Hunt's avatar
Evan Hunt committed
397
	rpzs->have.client_ip = rpzs->have.client_ipv4 | rpzs->have.client_ipv6;
398
399
	rpzs->have.ip = rpzs->have.ipv4 | rpzs->have.ipv6;
	rpzs->have.nsip = rpzs->have.nsipv4 | rpzs->have.nsipv6;
400
401
402
}

static void
403
404
405
406
407
408
409
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)
{
	int *cnt;
	dns_rpz_zbits_t *have;
410

411
	switch (rpz_type) {
Evan Hunt's avatar
Evan Hunt committed
412
413
414
415
416
417
418
419
420
421
	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;
422
	case DNS_RPZ_TYPE_QNAME:
Evan Hunt's avatar
Evan Hunt committed
423
		cnt = &rpzs->triggers[rpz_num].qname;
424
425
426
427
428
		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
429
			cnt = &rpzs->triggers[rpz_num].ipv4;
430
431
			have = &rpzs->have.ipv4;
		} else {
Evan Hunt's avatar
Evan Hunt committed
432
			cnt = &rpzs->triggers[rpz_num].ipv6;
433
434
435
436
			have = &rpzs->have.ipv6;
		}
		break;
	case DNS_RPZ_TYPE_NSDNAME:
Evan Hunt's avatar
Evan Hunt committed
437
		cnt = &rpzs->triggers[rpz_num].nsdname;
438
439
440
441
442
		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
443
			cnt = &rpzs->triggers[rpz_num].nsipv4;
444
445
			have = &rpzs->have.nsipv4;
		} else {
Evan Hunt's avatar
Evan Hunt committed
446
			cnt = &rpzs->triggers[rpz_num].nsipv6;
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
			have = &rpzs->have.nsipv6;
		}
		break;
	default:
		INSIST(0);
	}

	if (inc) {
		if (++*cnt == 1) {
			*have |= DNS_RPZ_ZBIT(rpz_num);
			fix_qname_skip_recurse(rpzs);
		}
	} else {
		REQUIRE(*cnt > 0);
		if (--*cnt == 0) {
			*have &= ~DNS_RPZ_ZBIT(rpz_num);
			fix_qname_skip_recurse(rpzs);
		}
465
466
467
468
	}
}

static dns_rpz_cidr_node_t *
469
470
471
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)
472
{
473
	dns_rpz_cidr_node_t *new;
474
475
	int i, words, wlen;

476
477
	new = isc_mem_get(rpzs->mctx, sizeof(*new));
	if (new == NULL)
478
		return (NULL);
479
	memset(new, 0, sizeof(*new));
480

481
482
	if (child != NULL)
		new->sum = child->sum;
483

484
485
486
	new->prefix = prefix;
	words = prefix / DNS_RPZ_CIDR_WORD_BITS;
	wlen = prefix % DNS_RPZ_CIDR_WORD_BITS;
487
488
	i = 0;
	while (i < words) {
489
		new->ip.w[i] = ip->w[i];
490
491
492
		++i;
	}
	if (wlen != 0) {
493
		new->ip.w[i] = ip->w[i] & DNS_RPZ_WORD_MASK(wlen);
494
495
496
		++i;
	}
	while (i < DNS_RPZ_CIDR_WORDS)
497
		new->ip.w[i++] = 0;
498

499
	return (new);
500
501
502
}

static void
503
badname(int level, dns_name_t *name, const char *str1, const char *str2) {
504
	char namebuf[DNS_NAME_FORMATSIZE];
505

506
507
508
	/*
	 * bin/tests/system/rpz/tests.sh looks for "invalid rpz".
	 */
Evan Hunt's avatar
Evan Hunt committed
509
510
	if (level < DNS_RPZ_DEBUG_QUIET &&
	    isc_log_wouldlog(dns_lctx, level)) {
511
		dns_name_format(name, namebuf, sizeof(namebuf));
512
		isc_log_write(dns_lctx, DNS_LOGCATEGORY_RPZ,
513
			      DNS_LOGMODULE_RBTDB, level,
514
			      "invalid rpz IP address \"%s\"%s%s",
515
			      namebuf, str1, str2);
516
517
518
519
520
	}
}

/*
 * Convert an IP address from radix tree binary (host byte order) to
521
 * to its canonical response policy domain name without the origin of the
522
523
524
 * policy zone.
 */
static isc_result_t
525
526
ip2name(const dns_rpz_cidr_key_t *tgt_ip, dns_rpz_prefix_t tgt_prefix,
	dns_name_t *base_name, dns_name_t *ip_name)
527
528
529
530
531
532
533
534
535
536
537
{
#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;

538
	if (KEY_IS_IPV4(tgt_prefix, tgt_ip)) {
539
540
541
542
543
544
		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);
545
		if (len < 0 || len > (int)sizeof(str))
546
547
548
549
550
551
552
553
554
555
556
557
558
			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
559
560
561
			if (w[i] != 0 || zeros ||
			    i >= DNS_RPZ_CIDR_WORDS * 2 - 1 ||
			    w[i+1] != 0) {
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
				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
580
			if (len >= (int)sizeof(str))
581
582
583
584
				return (ISC_R_FAILURE);
		}
	}

585
586
	isc_buffer_init(&buffer, str, sizeof(str));
	isc_buffer_add(&buffer, len);
587
588
	result = dns_name_fromtext(ip_name, &buffer, base_name, 0, NULL);
	return (result);
589
590
591
}

/*
592
 * Determine the type a of a name in a response policy zone.
593
594
 */
static dns_rpz_type_t
595
type_from_name(dns_rpz_zone_t *rpz, dns_name_t *name) {
596

597
	if (dns_name_issubdomain(name, &rpz->ip))
598
599
		return (DNS_RPZ_TYPE_IP);

Evan Hunt's avatar
Evan Hunt committed
600
601
602
	if (dns_name_issubdomain(name, &rpz->client_ip))
		return (DNS_RPZ_TYPE_CLIENT_IP);

603
#ifdef ENABLE_RPZ_NSIP
604
	if (dns_name_issubdomain(name, &rpz->nsip))
605
606
607
608
		return (DNS_RPZ_TYPE_NSIP);
#endif

#ifdef ENABLE_RPZ_NSDNAME
609
	if (dns_name_issubdomain(name, &rpz->nsdname))
610
611
612
613
614
615
616
617
		return (DNS_RPZ_TYPE_NSDNAME);
#endif

	return (DNS_RPZ_TYPE_QNAME);
}

/*
 * Convert an IP address from canonical response policy domain name form
618
619
 * to radix tree binary (host byte order) for adding or deleting IP or NSIP
 * data.
620
621
 */
static isc_result_t
622
623
624
625
name2ipkey(int log_level,
	   const dns_rpz_zones_t *rpzs, dns_rpz_num_t rpz_num,
	   dns_rpz_type_t rpz_type, dns_name_t *src_name,
	   dns_rpz_cidr_key_t *tgt_ip, dns_rpz_prefix_t *tgt_prefix,
Evan Hunt's avatar
Evan Hunt committed
626
	   dns_rpz_addr_zbits_t *new_set)
627
{
628
629
630
631
632
	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;
633
	const char *prefix_str, *cp, *end;
634
635
	char *cp2;
	int ip_labels;
636
637
638
	dns_rpz_prefix_t prefix;
	unsigned long prefix_num, l;
	isc_result_t result;
639
640
	int i;

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

Evan Hunt's avatar
Evan Hunt committed
645
	make_addr_set(new_set, DNS_RPZ_ZBIT(rpz_num), rpz_type);
646

647
	ip_labels = dns_name_countlabels(src_name);
648
649
650
651
652
653
	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", "");
654
655
		return (ISC_R_FAILURE);
	}
656
657
	dns_name_init(&ip_name, ip_name_offsets);
	dns_name_getlabelsequence(src_name, 0, ip_labels, &ip_name);
658
659

	/*
660
	 * Get text for the IP address
661
	 */
662
663
664
665
666
	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);
667
	if (*cp2 != '.') {
668
		badname(log_level, src_name,
669
670
671
672
			"; invalid leading prefix length", "");
		return (ISC_R_FAILURE);
	}
	*cp2 = '\0';
673
674
	if (prefix_num < 1U || prefix_num > 128U) {
		badname(log_level, src_name,
675
			"; invalid prefix length of ", prefix_str);
676
677
678
679
		return (ISC_R_FAILURE);
	}
	cp = cp2+1;

680
	if (--ip_labels == 4 && !strchr(cp, 'z')) {
681
682
683
684
		/*
		 * Convert an IPv4 address
		 * from the form "prefix.w.z.y.x"
		 */
685
686
		if (prefix_num > 32U) {
			badname(log_level, src_name,
687
				"; invalid IPv4 prefix length of ", prefix_str);
688
689
			return (ISC_R_FAILURE);
		}
690
691
		prefix_num += 96;
		*tgt_prefix = (dns_rpz_prefix_t)prefix_num;
692
693
694
695
696
697
		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
698
			if (l > 255U || (*cp2 != '.' && *cp2 != '\0')) {
699
700
				if (*cp2 == '.')
					*cp2 = '\0';
701
				badname(log_level, src_name,
702
					"; invalid IPv4 octet ", cp);
703
704
705
706
707
708
709
710
711
				return (ISC_R_FAILURE);
			}
			tgt_ip->w[3] |= l << i;
			cp = cp2 + 1;
		}
	} else {
		/*
		 * Convert a text IPv6 address.
		 */
712
		*tgt_prefix = (dns_rpz_prefix_t)prefix_num;
713
714
715
716
717
718
719
720
721
722
723
724
725
726
		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
727
				if (l > 0xffffu ||
728
				    (*cp2 != '.' && *cp2 != '\0')) {
729
730
					if (*cp2 == '.')
					    *cp2 = '\0';
731
					badname(log_level, src_name,
732
						"; invalid IPv6 word ", cp);
733
734
735
736
737
738
739
740
741
742
743
744
					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) {
745
		badname(log_level, src_name, "", "");
746
747
748
749
750
751
		return (ISC_R_FAILURE);
	}

	/*
	 * Check for 1s after the prefix length.
	 */
752
753
	prefix = (dns_rpz_prefix_t)prefix_num;
	while (prefix < DNS_RPZ_CIDR_KEY_BITS) {
754
755
		dns_rpz_cidr_word_t aword;

756
757
		i = prefix % DNS_RPZ_CIDR_WORD_BITS;
		aword = tgt_ip->w[prefix / DNS_RPZ_CIDR_WORD_BITS];
758
		if ((aword & ~DNS_RPZ_WORD_MASK(i)) != 0) {
759
			badname(log_level, src_name,
760
				"; too small prefix length of ", prefix_str);
761
762
			return (ISC_R_FAILURE);
		}
763
764
		prefix -= i;
		prefix += DNS_RPZ_CIDR_WORD_BITS;
765
766
767
	}

	/*
768
769
	 * Convert the address back to a canonical domain name
	 * to ensure that the original name is in canonical form.
770
	 */
771
772
773
774
775
	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", "");
776
777
778
779
780
781
782
		return (ISC_R_FAILURE);
	}

	return (ISC_R_SUCCESS);
}

/*
783
784
 * Get trigger name and data bits for adding or deleting summary NSDNAME
 * or QNAME data.
785
 */
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
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
807
808
		memset(&new_data->set, 0, sizeof(new_data->set));
		make_nm_set(&new_data->wild, rpz_num, rpz_type);
809
810
	} else {
		prefix_len = 0;
Evan Hunt's avatar
Evan Hunt committed
811
812
		make_nm_set(&new_data->set, rpz_num, rpz_type);
		memset(&new_data->wild, 0, sizeof(new_data->wild));
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
	}

	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);
}

/*
 * Find the first differing bit in a key (IP address) word.
 */
static inline int
ffs_keybit(dns_rpz_cidr_word_t w) {
831
832
	int bit;

833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
	bit = DNS_RPZ_CIDR_WORD_BITS-1;
	if ((w & 0xffff0000) != 0) {
		w >>= 16;
		bit -= 16;
	}
	if ((w & 0xff00) != 0) {
		w >>= 8;
		bit -= 8;
	}
	if ((w & 0xf0) != 0) {
		w >>= 4;
		bit -= 4;
	}
	if ((w & 0xc) != 0) {
		w >>= 2;
		bit -= 2;
	}
	if ((w & 2) != 0)
		--bit;
852
853
854
855
	return (bit);
}

/*
856
 * Find the first differing bit in two keys (IP addresses).
857
858
 */
static int
859
860
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)
861
862
{
	dns_rpz_cidr_word_t delta;
863
	dns_rpz_prefix_t maxbit, bit;
864
865
	int i;

866
	maxbit = ISC_MIN(prefix1, prefix2);
867
868
869
870
871
872
873
874
875

	/*
	 * find the first differing words
	 */
	for (i = 0, bit = 0;
	     bit <= maxbit;
	     i++, bit += DNS_RPZ_CIDR_WORD_BITS) {
		delta = key1->w[i] ^ key2->w[i];
		if (delta != 0) {
876
			bit += ffs_keybit(delta);
877
878
879
880
881
882
			break;
		}
	}
	return (ISC_MIN(bit, maxbit));
}

883
884
885
886
887
888
889
890
891
892
893
894
895
/*
 * 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;
896
	x &= (~x + 1);
897
898
899
900
	x = (x << 1) - 1;
	return (zbits &= x);
}

901
902
903
904
/*
 * Search a radix tree for an IP address for ordinary lookup
 *	or for a CIDR block adding or deleting an entry
 *
905
906
907
 * 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
908
909
 */
static isc_result_t
910
911
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
912
       const dns_rpz_addr_zbits_t *tgt_set, isc_boolean_t create,
913
       dns_rpz_cidr_node_t **found)
914
915
{
	dns_rpz_cidr_node_t *cur, *parent, *child, *new_parent, *sibling;
Evan Hunt's avatar
Evan Hunt committed
916
	dns_rpz_addr_zbits_t set;
917
	int cur_num, child_num;
918
	dns_rpz_prefix_t dbit;
919
920
	isc_result_t find_result;

Evan Hunt's avatar
Evan Hunt committed
921
	set = *tgt_set;
922
	find_result = ISC_R_NOTFOUND;
923
924
	*found = NULL;
	cur = rpzs->cidr;
925
926
927
928
929
	parent = NULL;
	cur_num = 0;
	for (;;) {
		if (cur == NULL) {
			/*
930
931
932
			 * No child so we cannot go down.
			 * Quit with whatever we already found
			 * or add the target as a child of the current parent.
933
934
935
			 */
			if (!create)
				return (find_result);
936
			child = new_node(rpzs, tgt_ip, tgt_prefix, NULL);
937
938
939
			if (child == NULL)
				return (ISC_R_NOMEMORY);
			if (parent == NULL)
940
				rpzs->cidr = child;
941
942
943
			else
				parent->child[cur_num] = child;
			child->parent = parent;
Evan Hunt's avatar
Evan Hunt committed
944
945
946
			child->set.client_ip |= tgt_set->client_ip;
			child->set.ip |= tgt_set->ip;
			child->set.nsip |= tgt_set->nsip;
947
948
			set_sum_pair(child);
			*found = cur;
949
950
951
			return (ISC_R_SUCCESS);
		}

Evan Hunt's avatar
Evan Hunt committed
952
953
954
		if ((cur->sum.client_ip & set.client_ip) == 0 &&
		    (cur->sum.ip & set.ip) == 0 &&
		    (cur->sum.nsip & set.nsip) == 0) {
955
956
957
958
959
960
961
962
963
964
965
			/*
			 * 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);
		}
966

967
		dbit = diff_keys(tgt_ip, tgt_prefix, &cur->ip, cur->prefix);
968
		/*
969
		 * dbit <= tgt_prefix and dbit <= cur->prefix always.
970
971
972
		 * We are finished searching if we matched all of the target.
		 */
		if (dbit == tgt_prefix) {
973
			if (tgt_prefix == cur->prefix) {
974
				/*
975
				 * The node's key matches the target exactly.
976
				 */
Evan Hunt's avatar
Evan Hunt committed
977
978
979
				if ((cur->set.client_ip & set.client_ip) != 0 ||
				    (cur->set.ip & set.ip) != 0 ||
				    (cur->set.nsip & set.nsip) != 0) {
980
981
982
983
984
985
986
987
988
					/*
					 * It is the answer if it has data.
					 */
					*found = cur;
					if (create) {
					    find_result = ISC_R_EXISTS;
					} else {
					    find_result = ISC_R_SUCCESS;
					}
989
990
				} else if (create) {
					/*
991
992
					 * The node lacked relevant data,
					 * but will have it now.
993
					 */
Evan Hunt's avatar
Evan Hunt committed
994
995
996
					cur->set.client_ip |= tgt_set->client_ip;
					cur->set.ip |= tgt_set->ip;
					cur->set.nsip |= tgt_set->nsip;
997
998
999
					set_sum_pair(cur);
					*found = cur;
					find_result = ISC_R_SUCCESS;
1000
1001
1002
1003
1004
				}
				return (find_result);
			}

			/*
1005
			 * We know tgt_prefix < cur->prefix which means that
1006
1007
1008
1009
1010
1011
			 * the target is shorter than the current node.
			 * Add the target as the current node's parent.
			 */
			if (!create)
				return (find_result);

1012
			new_parent = new_node(rpzs, tgt_ip, tgt_prefix, cur);
1013
1014
1015
1016
			if (new_parent == NULL)
				return (ISC_R_NOMEMORY);
			new_parent->parent = parent;
			if (parent == NULL)
1017
				rpzs->cidr = new_parent;
1018
1019
1020
1021
1022
			else
				parent->child[cur_num] = new_parent;
			child_num = DNS_RPZ_IP_BIT(&cur->ip, tgt_prefix+1);
			new_parent->child[child_num] = cur;
			cur->parent = new_parent;
Evan Hunt's avatar
Evan Hunt committed
1023
			new_parent->set = *tgt_set;
1024
1025
			set_sum_pair(new_parent);
			*found = new_parent;
1026
1027
1028
			return (ISC_R_SUCCESS);
		}

1029
		if (dbit == cur->prefix) {
Evan Hunt's avatar
Evan Hunt committed
1030
1031
1032
			if ((cur->set.client_ip & set.client_ip) != 0 ||
			    (cur->set.ip & set.ip) != 0 ||
			    (cur->set.nsip & set.nsip) != 0) {
1033
1034
1035
1036
1037
1038
				/*
				 * We have a partial match between of all of the
				 * current node but only part of the target.
				 * Continue searching for other hits in the
				 * same or lower numbered trees.
				 */
1039
				find_result = DNS_R_PARTIALMATCH;
1040
				*found = cur;
Evan Hunt's avatar
Evan Hunt committed
1041
1042
1043
1044
1045
1046
				set.client_ip = trim_zbits(set.ip,
							cur->set.client_ip);
				set.ip = trim_zbits(set.ip,
						    cur->set.ip);
				set.nsip = trim_zbits(set.nsip,
						      cur->set.nsip);
1047
1048
1049
1050
1051
1052
1053
1054
1055
			}
			parent = cur;
			cur_num = DNS_RPZ_IP_BIT(tgt_ip, dbit);
			cur = cur->child[cur_num];
			continue;
		}


		/*
1056
		 * dbit < tgt_prefix and dbit < cur->prefix,
1057
1058
1059
1060
1061
1062
1063
		 * so we failed to match both the target and the current node.
		 * Insert a fork of a parent above the current node and
		 * add the target as a sibling of the current node
		 */
		if (!create)
			return (find_result);

1064
		sibling = new_node(rpzs, tgt_ip, tgt_prefix, NULL);
1065
1066
		if (sibling == NULL)
			return (ISC_R_NOMEMORY);
1067
		new_parent = new_node(rpzs, tgt_ip, dbit, cur);
1068
		if (new_parent == NULL) {
1069
			isc_mem_put(rpzs->mctx, sibling, sizeof(*sibling));
1070
1071
1072
1073
			return (ISC_R_NOMEMORY);
		}
		new_parent->parent = parent;
		if (parent == NULL)
1074
			rpzs->cidr = new_parent;
1075
1076
1077
1078
1079
1080
1081
		else
			parent->child[cur_num] = new_parent;
		child_num = DNS_RPZ_IP_BIT(tgt_ip, dbit);
		new_parent->child[child_num] = sibling;
		new_parent->child[1-child_num] = cur;
		cur->parent = new_parent;
		sibling->parent = new_parent;
Evan Hunt's avatar
Evan Hunt committed
1082
		sibling->set = *tgt_set;
1083
1084
		set_sum_pair(sibling);
		*found = sibling;
1085
1086
1087
1088
1089
		return (ISC_R_SUCCESS);
	}
}

/*
1090
 * Add an IP address to the radix tree.
1091
 */
1092
1093
1094
1095
static isc_result_t
add_cidr(dns_rpz_zones_t *rpzs, dns_rpz_num_t rpz_num,
	 dns_rpz_type_t rpz_type, dns_name_t *src_name)
{
1096
	dns_rpz_cidr_key_t tgt_ip;
1097
	dns_rpz_prefix_t tgt_prefix;
Evan Hunt's avatar
Evan Hunt committed
1098
	dns_rpz_addr_zbits_t set;
1099
1100
	dns_rpz_cidr_node_t *found;
	isc_result_t result;
1101

1102
	result = name2ipkey(DNS_RPZ_ERROR_LEVEL, rpzs, rpz_num, rpz_type,
Evan Hunt's avatar
Evan Hunt committed
1103
			    src_name, &tgt_ip, &tgt_prefix, &set);
1104
	/*
1105
	 * Log complaints about bad owner names but let the zone load.
1106
	 */
1107
	if (result != ISC_R_SUCCESS)
1108
		return (ISC_R_SUCCESS);
1109

Evan Hunt's avatar
Evan Hunt committed
1110
	result = search(rpzs, &tgt_ip, tgt_prefix, &set, ISC_TRUE, &found);
1111
1112
	if (result != ISC_R_SUCCESS) {
		char namebuf[DNS_NAME_FORMATSIZE];
1113

1114
1115
1116
1117
		/*
		 * bin/tests/system/rpz/tests.sh looks for "rpz.*failed".
		 */
		dns_name_format(src_name, namebuf, sizeof(namebuf));
1118
		isc_log_write(dns_lctx, DNS_LOGCATEGORY_RPZ,
1119
			      DNS_LOGMODULE_RBTDB, DNS_RPZ_ERROR_LEVEL,
1120
1121
1122
			      "rpz add_cidr(%s) failed: %s",
			      namebuf, isc_result_totext(result));
		return (result);
1123
	}
1124
1125
1126

	adj_trigger_cnt(rpzs, rpz_num, rpz_type, &tgt_ip, tgt_prefix, ISC_TRUE);
	return (result);
1127
1128
}

1129
1130
1131
1132
1133
1134
static isc_result_t
add_nm(dns_rpz_zones_t *rpzs, dns_name_t *trig_name,
	 const dns_rpz_nm_data_t *new_data)
{
	dns_rbtnode_t *nmnode;
	dns_rpz_nm_data_t *nm_data;
1135
	isc_result_t result;
1136

1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
	nmnode = NULL;
	result = dns_rbt_addnode(rpzs->rbt, trig_name, &nmnode);
	switch (result) {
	case ISC_R_SUCCESS:
	case ISC_R_EXISTS:
		nm_data = nmnode->data;
		if (nm_data == NULL) {
			nm_data = isc_mem_get(rpzs->mctx, sizeof(*nm_data));
			if (nm_data == NULL)
				return (ISC_R_NOMEMORY);
			*nm_data = *new_data;
			nmnode->data = nm_data;
			return (ISC_R_SUCCESS);
		}
		break;
	default:
		return (result);
	}
1155
1156

	/*
1157
	 * Do not count bits that are already present
1158
	 */
Evan Hunt's avatar
Evan Hunt committed
1159
1160
1161
	if ((nm_data->set.qname & new_data->set.qname) != 0 ||
	    (nm_data->set.ns & new_data->set.ns) != 0 ||
	    (nm_data->wild.qname & new_data->wild.qname) != 0 ||
1162
1163
1164
	    (nm_data->wild.ns & new_data->wild.ns) != 0) {
		char namebuf[DNS_NAME_FORMATSIZE];

1165
		/*
1166
		 * bin/tests/system/rpz/tests.sh looks for "rpz.*failed".
1167
		 */
1168
1169
1170
1171
1172
		dns_name_format(trig_name, namebuf, sizeof(namebuf));
		isc_log_write(dns_lctx, DNS_LOGCATEGORY_RPZ,
			      DNS_LOGMODULE_RBTDB, DNS_RPZ_ERROR_LEVEL,
			      "rpz add_nm(%s): bits already set", namebuf);
		return (ISC_R_EXISTS);
1173
1174
	}

Evan Hunt's avatar
Evan Hunt committed
1175
1176
1177
	nm_data->set.qname |= new_data->set.qname;
	nm_data->set.ns |= new_data->set.ns;
	nm_data->wild.qname |= new_data->wild.qname;
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
	nm_data->wild.ns |= new_data->wild.ns;
	return (ISC_R_SUCCESS);
}

static isc_result_t
add_name(dns_rpz_zones_t *rpzs, dns_rpz_num_t rpz_num,
	 dns_rpz_type_t rpz_type, dns_name_t *src_name)
{
	dns_rpz_nm_data_t new_data;
	dns_fixedname_t trig_namef;
	dns_name_t *trig_name;
	isc_result_t result;

	dns_fixedname_init(&trig_namef);
	trig_name = dns_fixedname_name(&trig_namef);
	name2data(rpzs, rpz_num, rpz_type, src_name, trig_name, &new_data);

	result = add_nm(rpzs, trig_name, &new_data);
	if (result == ISC_R_SUCCESS)
		adj_trigger_cnt(rpzs, rpz_num, rpz_type, NULL, 0, ISC_TRUE);
	return (result);
}

/*
 * Callback to free the data for a node in the summary RBT database.
 */
static void
rpz_node_deleter(void *nm_data, void *mctx) {
	isc_mem_put(mctx, nm_data, sizeof(dns_rpz_nm_data_t));
}

/*
 * Get ready for a new set of policy zones.
 */
isc_result_t
dns_rpz_new_zones(dns_rpz_zones_t **rpzsp, isc_mem_t *mctx) {
	dns_rpz_zones_t *new;
	isc_result_t result;

	REQUIRE(rpzsp != NULL && *rpzsp == NULL);

	*rpzsp = NULL;

	new = isc_mem_get(mctx, sizeof(*new));
	if (new == NULL)
		return (ISC_R_NOMEMORY);
	memset(new, 0, sizeof(*new));

	result = isc_mutex_init(&new->search_lock);
1227
	if (result != ISC_R_SUCCESS) {
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
		isc_mem_put(mctx, new, sizeof(*new));
		return (result);
	}

	result = isc_mutex_init(&new->maint_lock);
	if (result != ISC_R_SUCCESS) {
		DESTROYLOCK(&new->search_lock);
		isc_mem_put(mctx, new, sizeof(*new));
		return (result);
	}

	result = isc_refcount_init(&new->refs, 1);
	if (result != ISC_R_SUCCESS) {
		DESTROYLOCK(&new->maint_lock);
		DESTROYLOCK(&new->search_lock);
		isc_mem_put(mctx, new, sizeof(*new));
		return (result);
	}

	result = dns_rbt_create(mctx, rpz_node_deleter, mctx, &new->rbt);
	if (result != ISC_R_SUCCESS) {
		isc_refcount_decrement(&new->refs, NULL);
		isc_refcount_destroy(&new->refs);
		DESTROYLOCK(&new->maint_lock);
		DESTROYLOCK(&new->search_lock);
		isc_mem_put(mctx, new, sizeof(*new));
		return (result);
	}

	isc_mem_attach(mctx, &new->mctx);

	*rpzsp = new;
	return (ISC_R_SUCCESS);
}

/*
 * Free the radix tree of a response policy database.
 */
static void
cidr_free(dns_rpz_zones_t *rpzs) {
	dns_rpz_cidr_node_t *cur, *child, *parent;

	cur = rpzs->cidr;
	while (cur != NULL) {
		/* Depth first. */
		child = cur->child[0];
		if (child !=