contents.c 27.1 KB
Newer Older
Daniel Salzman's avatar
Daniel Salzman committed
1
/*  Copyright (C) 2016 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>
Lubos Slovak's avatar
Lubos Slovak committed
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

17 18
#include <assert.h>

19
#include "knot/zone/contents.h"
20
#include "knot/common/log.h"
21
#include "knot/dnssec/zone-nsec.h"
22
#include "libknot/libknot.h"
23
#include "contrib/hat-trie/hat-trie.h"
24
#include "contrib/macros.h"
25

26
typedef struct {
27
	zone_contents_apply_cb_t func;
28
	void *data;
29
} zone_tree_func_t;
30

31
typedef struct {
32
	zone_node_t *first_node;
33
	zone_contents_t *zone;
34
	zone_node_t *previous_node;
35
} zone_adjust_arg_t;
36

37
static int tree_apply_cb(zone_node_t **node, void *data)
38 39
{
	if (node == NULL || data == NULL) {
40
		return KNOT_EINVAL;
41 42
	}

43
	zone_tree_func_t *f = (zone_tree_func_t *)data;
44
	return f->func(*node, f->data);
45 46
}

47 48 49 50 51 52 53 54 55
/*!
 * \brief Checks if the given node can be inserted into the given zone.
 *
 * Checks if both the arguments are non-NULL and if the owner of the node
 * belongs to the zone (i.e. is a subdomain of the zone apex).
 *
 * \param zone Zone to which the node is going to be inserted.
 * \param node Node to check.
 *
Lubos Slovak's avatar
Lubos Slovak committed
56
 * \retval KNOT_EOK if both arguments are non-NULL and the node belongs to the
57
 *         zone.
Marek Vavrusa's avatar
Marek Vavrusa committed
58
 * \retval KNOT_EINVAL if either of the arguments is NULL.
59
 * \retval KNOT_EOUTOFZONE if the node does not belong to the zone.
60
 */
Daniel Salzman's avatar
Daniel Salzman committed
61
static int check_node(const zone_contents_t *contents, const zone_node_t *node)
62
{
Daniel Salzman's avatar
Daniel Salzman committed
63
	assert(contents);
64
	assert(contents->apex != NULL);
Daniel Salzman's avatar
Daniel Salzman committed
65 66
	assert(node);

Daniel Salzman's avatar
Daniel Salzman committed
67
	if (!knot_dname_is_sub(node->owner, contents->apex->owner)) {
68
		return KNOT_EOUTOFZONE;
69
	}
Daniel Salzman's avatar
Daniel Salzman committed
70

Lubos Slovak's avatar
Lubos Slovak committed
71
	return KNOT_EOK;
72 73 74 75 76 77 78 79 80 81
}

/*!
 * \brief Destroys all RRSets in a node.
 *
 * This function is designed to be used in the tree-iterating functions.
 *
 * \param node Node to destroy RRSets from.
 * \param data Unused parameter.
 */
Daniel Salzman's avatar
Daniel Salzman committed
82
static int destroy_node_rrsets_from_tree(zone_node_t **node, void *data)
83
{
Daniel Salzman's avatar
Daniel Salzman committed
84
	assert(node);
Daniel Salzman's avatar
Daniel Salzman committed
85 86
	UNUSED(data);

Daniel Salzman's avatar
Daniel Salzman committed
87 88 89
	if (*node != NULL) {
		node_free_rrsets(*node, NULL);
		node_free(node, NULL);
90
	}
91

92
	return KNOT_EOK;
93 94
}

95
static int create_nsec3_name(const zone_contents_t *zone,
Daniel Salzman's avatar
Daniel Salzman committed
96 97
                             const knot_dname_t *name,
                             knot_dname_t **nsec3_name)
98
{
Daniel Salzman's avatar
Daniel Salzman committed
99 100
	assert(zone);
	assert(nsec3_name);
101

Daniel Salzman's avatar
Daniel Salzman committed
102
	if (!knot_is_nsec3_enabled(zone)) {
103 104 105
		return KNOT_ENSEC3PAR;
	}

Daniel Salzman's avatar
Daniel Salzman committed
106 107
	*nsec3_name = knot_create_nsec3_owner(name, zone->apex->owner,
	                                      &zone->nsec3_params);
108
	if (*nsec3_name == NULL) {
109 110 111 112 113 114
		return KNOT_ERROR;
	}

	return KNOT_EOK;
}

115
/*! \brief Link pointers to additional nodes for this RRSet. */
Daniel Salzman's avatar
Daniel Salzman committed
116
static int discover_additionals(struct rr_data *rr_data, zone_contents_t *zone)
117
{
Daniel Salzman's avatar
Daniel Salzman committed
118 119
	assert(rr_data != NULL);

120
	const knot_rdataset_t *rrs = &rr_data->rrs;
121 122

	/* Create new additional nodes. */
123
	uint16_t rdcount = rrs->rr_count;
124 125 126
	if (rr_data->additional) {
		free(rr_data->additional);
	}
127
	rr_data->additional = malloc(rdcount * sizeof(zone_node_t *));
128
	if (rr_data->additional == NULL) {
129 130 131 132
		return KNOT_ENOMEM;
	}

	for (uint16_t i = 0; i < rdcount; i++) {
Daniel Salzman's avatar
Daniel Salzman committed
133 134
		const knot_dname_t *dname = knot_rdata_name(rrs, i, rr_data->type);
		const zone_node_t *node = NULL, *encloser = NULL, *prev = NULL;
135

136
		/* Try to find node for the dname in the RDATA. */
137
		zone_contents_find_dname(zone, dname, &node, &encloser, &prev);
Daniel Salzman's avatar
Daniel Salzman committed
138
		if (node == NULL && encloser != NULL
139
		    && (encloser->flags & NODE_FLAGS_WILDCARD_CHILD)) {
140
			/* Find wildcard child in the zone. */
Daniel Salzman's avatar
Daniel Salzman committed
141
			node = zone_contents_find_wildcard_child(zone, encloser);
142
			assert(node != NULL);
143 144
		}

145
		rr_data->additional[i] = (zone_node_t *)node;
146 147 148 149
	}

	return KNOT_EOK;
}
150

151
static int adjust_pointers(zone_node_t **tnode, void *data)
152
{
153
	assert(tnode != NULL);
Daniel Salzman's avatar
Daniel Salzman committed
154 155
	assert(data != NULL);

156
	zone_adjust_arg_t *args = (zone_adjust_arg_t *)data;
157
	zone_node_t *node = *tnode;
158

159
	// remember first node
160
	if (args->first_node == NULL) {
161
		args->first_node = node;
162
	}
163

164
	// clear Removed NSEC flag so that no relicts remain
165
	node->flags &= ~NODE_FLAGS_REMOVED_NSEC;
Lubos Slovak's avatar
Lubos Slovak committed
166

167
	// check if this node is not a wildcard child of its parent
168 169
	if (knot_dname_is_wildcard(node->owner)) {
		assert(node->parent != NULL);
170
		node->parent->flags |= NODE_FLAGS_WILDCARD_CHILD;
Jan Kadlec's avatar
Jan Kadlec committed
171
	}
172

173
	// set flags (delegation point, non-authoritative)
174
	if (node->parent &&
Daniel Salzman's avatar
Daniel Salzman committed
175
	    (node->parent->flags & NODE_FLAGS_DELEG ||
176 177 178 179
	     node->parent->flags & NODE_FLAGS_NONAUTH)) {
		node->flags |= NODE_FLAGS_NONAUTH;
	} else if (node_rrtype_exists(node, KNOT_RRTYPE_NS) && node != args->zone->apex) {
		node->flags |= NODE_FLAGS_DELEG;
Jan Kadlec's avatar
Jan Kadlec committed
180
	} else {
181 182
		// Default.
		node->flags = NODE_FLAGS_AUTH;
Jan Kadlec's avatar
Jan Kadlec committed
183 184
	}

185
	// set pointer to previous node
186
	node->prev = args->previous_node;
187

188
	// update remembered previous pointer only if authoritative
189
	if (!(node->flags & NODE_FLAGS_NONAUTH) && node->rrset_count > 0) {
190 191
		args->previous_node = node;
	}
192

193 194 195
	return KNOT_EOK;
}

196
static int adjust_nsec3_pointers(zone_node_t **tnode, void *data)
197 198 199
{
	assert(data != NULL);
	assert(tnode != NULL);
Daniel Salzman's avatar
Daniel Salzman committed
200

201
	zone_adjust_arg_t *args = (zone_adjust_arg_t *)data;
202
	zone_node_t *node = *tnode;
Daniel Salzman's avatar
Daniel Salzman committed
203

204
	// Connect to NSEC3 node (only if NSEC3 tree is not empty)
205
	zone_node_t *nsec3 = NULL;
206
	knot_dname_t *nsec3_name = NULL;
207
	int ret = create_nsec3_name(args->zone, node->owner, &nsec3_name);
208 209
	if (ret == KNOT_EOK) {
		assert(nsec3_name);
210
		zone_tree_get(args->zone->nsec3_nodes, nsec3_name, &nsec3);
211
		node->nsec3_node = nsec3;
212
	} else if (ret == KNOT_ENSEC3PAR) {
213
		node->nsec3_node = NULL;
214
		ret = KNOT_EOK;
215 216
	}

217
	knot_dname_free(&nsec3_name, NULL);
Daniel Salzman's avatar
Daniel Salzman committed
218

219
	return ret;
220 221
}

222 223 224 225 226 227 228 229 230 231
/*!
 * \brief Adjust normal (non NSEC3) node.
 *
 * Set:
 * - pointer to wildcard childs in parent nodes if applicable
 * - flags (delegation point, non-authoritative)
 * - pointer to previous node
 * - parent pointers
 *
 * \param tnode  Zone node to adjust.
232
 * \param data   Adjusting parameters (zone_adjust_arg_t *).
233
 */
234
static int adjust_normal_node(zone_node_t **tnode, void *data)
235 236
{
	assert(tnode != NULL && *tnode);
Daniel Salzman's avatar
Daniel Salzman committed
237 238
	assert(data != NULL);

239 240 241 242 243 244 245 246 247 248
	// Do cheap operations first
	int ret = adjust_pointers(tnode, data);
	if (ret != KNOT_EOK) {
		return ret;
	}

	// Connect nodes to their NSEC3 nodes
	return adjust_nsec3_pointers(tnode, data);
}

249
/*!
250
 * \brief Adjust NSEC3 node.
251
 *
252 253 254
 * Set:
 * - pointer to previous node
 * - pointer to node stored in owner dname
255
 *
256
 * \param tnode  Zone node to adjust.
257
 * \param data   Adjusting parameters (zone_adjust_arg_t *).
258
 */
259
static int adjust_nsec3_node(zone_node_t **tnode, void *data)
260 261
{
	assert(data != NULL);
262 263
	assert(tnode != NULL);

264
	zone_adjust_arg_t *args = (zone_adjust_arg_t *)data;
265
	zone_node_t *node = *tnode;
266

267
	// remember first node
268
	if (args->first_node == NULL) {
269
		args->first_node = node;
270
	}
271 272

	// set previous node
273
	node->prev = args->previous_node;
274
	args->previous_node = node;
275 276

	return KNOT_EOK;
277
}
278 279

/*! \brief Discover additional records for affected nodes. */
280
static int adjust_additional(zone_node_t **tnode, void *data)
281 282 283 284
{
	assert(data != NULL);
	assert(tnode != NULL);

285
	zone_adjust_arg_t *args = (zone_adjust_arg_t *)data;
286
	zone_node_t *node = *tnode;
287 288 289

	/* Lookup additional records for specific nodes. */
	for(uint16_t i = 0; i < node->rrset_count; ++i) {
290
		struct rr_data *rr_data = &node->rrs[i];
291
		if (knot_rrtype_additional_needed(rr_data->type)) {
Daniel Salzman's avatar
Daniel Salzman committed
292
			int ret = discover_additionals(rr_data, args->zone);
293
			if (ret != KNOT_EOK) {
Daniel Salzman's avatar
Daniel Salzman committed
294
				return ret;
295 296 297 298
			}
		}
	}

Daniel Salzman's avatar
Daniel Salzman committed
299
	return KNOT_EOK;
300 301
}

302 303 304 305 306 307 308 309 310 311
/*!
 * \brief Tries to find the given domain name in the zone tree.
 *
 * \param zone Zone to search in.
 * \param name Domain name to find.
 * \param node Found node.
 * \param previous Previous node in canonical order (i.e. the one directly
 *                 preceding \a name in canonical order, regardless if the name
 *                 is in the zone or not).
 *
312
 * \retval true if the domain name was found. In such case \a node holds the
313 314
 *              zone node with \a name as its owner. \a previous is set
 *              properly.
315 316
 * \retval false if the domain name was not found. \a node may hold any (or none)
 *               node. \a previous is set properly.
317
 */
318 319
static bool find_in_tree(zone_tree_t *tree, const knot_dname_t *name,
                         zone_node_t **node, zone_node_t **previous)
320
{
321
	assert(tree != NULL);
322 323 324 325
	assert(name != NULL);
	assert(node != NULL);
	assert(previous != NULL);

326
	zone_node_t *found = NULL, *prev = NULL;
327

328 329 330 331 332
	int match = zone_tree_get_less_or_equal(tree, name, &found, &prev);
	if (match < 0) {
		assert(0);
		return false;
	}
Daniel Salzman's avatar
Daniel Salzman committed
333

334
	*node = found;
Lubos Slovak's avatar
Lubos Slovak committed
335
	*previous = prev;
336

337
	return match > 0;
338 339
}

Daniel Salzman's avatar
Daniel Salzman committed
340 341 342
static bool nsec3_params_match(const knot_rdataset_t *rrs,
                               const knot_nsec3_params_t *params,
                               size_t rdata_pos)
343
{
Daniel Salzman's avatar
Daniel Salzman committed
344 345
	assert(rrs != NULL);
	assert(params != NULL);
Jan Včelák's avatar
Jan Včelák committed
346

347 348 349
	return (knot_nsec3_algorithm(rrs, rdata_pos) == params->algorithm
		&& knot_nsec3_iterations(rrs, rdata_pos) == params->iterations
		&& knot_nsec3_salt_length(rrs, rdata_pos) == params->salt_length
350 351
		&& memcmp(knot_nsec3_salt(rrs, rdata_pos), params->salt,
		          params->salt_length) == 0);
352 353
}

354
zone_contents_t *zone_contents_new(const knot_dname_t *apex_name)
355
{
356 357 358 359
	if (apex_name == NULL) {
		return NULL;
	}

360
	zone_contents_t *contents = malloc(sizeof(zone_contents_t));
361 362 363 364
	if (contents == NULL) {
		return NULL;
	}

365
	memset(contents, 0, sizeof(zone_contents_t));
366
	contents->apex = node_new(apex_name, NULL);
367 368 369
	if (contents->apex == NULL) {
		goto cleanup;
	}
370

371
	contents->nodes = zone_tree_create();
372 373 374 375
	if (contents->nodes == NULL) {
		goto cleanup;
	}

376
	if (zone_tree_insert(contents->nodes, contents->apex) != KNOT_EOK) {
377 378 379 380 381 382 383 384 385 386 387 388
		goto cleanup;
	}

	return contents;

cleanup:
	free(contents->nodes);
	free(contents->nsec3_nodes);
	free(contents);
	return NULL;
}

Daniel Salzman's avatar
Daniel Salzman committed
389
static zone_node_t *get_node(const zone_contents_t *zone, const knot_dname_t *name)
390
{
391 392
	if (zone == NULL || name == NULL) {
		return NULL;
393 394
	}

395
	zone_node_t *n;
396
	int ret = zone_tree_get(zone->nodes, name, &n);
397 398 399 400 401
	if (ret != KNOT_EOK) {
		return NULL;
	}

	return n;
402 403
}

Daniel Salzman's avatar
Daniel Salzman committed
404
static int add_node(zone_contents_t *zone, zone_node_t *node, bool create_parents)
405 406
{
	if (zone == NULL || node == NULL) {
Marek Vavrusa's avatar
Marek Vavrusa committed
407
		return KNOT_EINVAL;
408 409
	}

Daniel Salzman's avatar
Daniel Salzman committed
410 411
	int ret = check_node(zone, node);
	if (ret != KNOT_EOK) {
412 413 414
		return ret;
	}

415
	ret = zone_tree_insert(zone->nodes, node);
Lubos Slovak's avatar
Lubos Slovak committed
416
	if (ret != KNOT_EOK) {
417 418 419 420
		return ret;
	}

	if (!create_parents) {
Lubos Slovak's avatar
Lubos Slovak committed
421
		return KNOT_EOK;
422 423
	}

424
	/* No parents for root domain. */
Daniel Salzman's avatar
Daniel Salzman committed
425
	if (*node->owner == '\0') {
Jan Kadlec's avatar
Jan Kadlec committed
426
		return KNOT_EOK;
Daniel Salzman's avatar
Daniel Salzman committed
427
	}
Jan Včelák's avatar
Jan Včelák committed
428

429
	zone_node_t *next_node = NULL;
430
	const uint8_t *parent = knot_wire_next_label(node->owner, NULL);
431

432
	if (knot_dname_cmp(zone->apex->owner, parent) == 0) {
433
		node_set_parent(node, zone->apex);
Lubos Slovak's avatar
Lubos Slovak committed
434 435

		// check if the node is not wildcard child of the parent
436
		if (knot_dname_is_wildcard(node->owner)) {
437
			zone->apex->flags |= NODE_FLAGS_WILDCARD_CHILD;
Lubos Slovak's avatar
Lubos Slovak committed
438
		}
439
	} else {
Daniel Salzman's avatar
Daniel Salzman committed
440
		while (parent != NULL && !(next_node = get_node(zone, parent))) {
441 442

			/* Create a new node. */
443
			next_node = node_new(parent, NULL);
444
			if (next_node == NULL) {
Lubos Slovak's avatar
Lubos Slovak committed
445
				return KNOT_ENOMEM;
446 447
			}

448
			/* Insert node to a tree. */
449
			ret = zone_tree_insert(zone->nodes, next_node);
Lubos Slovak's avatar
Lubos Slovak committed
450
			if (ret != KNOT_EOK) {
451
				node_free(&next_node, NULL);
452 453 454
				return ret;
			}

455
			/* Update node pointers. */
456
			node_set_parent(node, next_node);
457
			if (knot_dname_is_wildcard(node->owner)) {
458
				next_node->flags |= NODE_FLAGS_WILDCARD_CHILD;
459
			}
Lubos Slovak's avatar
Lubos Slovak committed
460

461
			node = next_node;
462
			parent = knot_wire_next_label(parent, NULL);
463
		}
464

465 466
		// set the found parent (in the zone) as the parent of the last
		// inserted node
467
		assert(node->parent == NULL);
468
		node_set_parent(node, next_node);
469
	}
470

Lubos Slovak's avatar
Lubos Slovak committed
471
	return KNOT_EOK;
472 473
}

474
static int add_nsec3_node(zone_contents_t *zone, zone_node_t *node)
Marek Vavrusa's avatar
Marek Vavrusa committed
475
{
476
	if (zone == NULL || node == NULL) {
Marek Vavrusa's avatar
Marek Vavrusa committed
477 478 479
		return KNOT_EINVAL;
	}

Daniel Salzman's avatar
Daniel Salzman committed
480 481
	int ret = check_node(zone, node);
	if (ret != KNOT_EOK) {
482
		return ret;
Marek Vavrusa's avatar
Marek Vavrusa committed
483 484
	}

485 486
	/* Create NSEC3 tree if not exists. */
	if (zone->nsec3_nodes == NULL) {
487
		zone->nsec3_nodes = zone_tree_create();
488 489 490
		if (zone->nsec3_nodes == NULL) {
			return KNOT_ENOMEM;
		}
Marek Vavrusa's avatar
Marek Vavrusa committed
491 492
	}

493
	// how to know if this is successful??
494
	ret = zone_tree_insert(zone->nsec3_nodes, node);
Marek Vavrusa's avatar
Marek Vavrusa committed
495 496 497 498
	if (ret != KNOT_EOK) {
		return ret;
	}

499 500
	// no parents to be created, the only parent is the zone apex
	// set the apex as the parent of the node
501
	node_set_parent(node, zone->apex);
502 503 504 505

	// cannot be wildcard child, so nothing to be done

	return KNOT_EOK;
Marek Vavrusa's avatar
Marek Vavrusa committed
506 507
}

508
static zone_node_t *get_nsec3_node(const zone_contents_t *zone,
Daniel Salzman's avatar
Daniel Salzman committed
509
                                   const knot_dname_t *name)
510 511 512 513
{
	if (zone == NULL || name == NULL) {
		return NULL;
	}
Marek Vavrusa's avatar
Marek Vavrusa committed
514

515
	zone_node_t *n;
516
	int ret = zone_tree_get(zone->nsec3_nodes, name, &n);
517 518 519 520 521 522
	if (ret != KNOT_EOK) {
		return NULL;
	}

	return n;
}
Marek Vavrusa's avatar
Marek Vavrusa committed
523

Daniel Salzman's avatar
Daniel Salzman committed
524 525
static int insert_rr(zone_contents_t *z, const knot_rrset_t *rr,
                     zone_node_t **n, bool nsec3)
Jan Kadlec's avatar
Jan Kadlec committed
526
{
527
	if (knot_rrset_empty(rr)) {
Jan Kadlec's avatar
Jan Kadlec committed
528 529 530 531
		return KNOT_EINVAL;
	}

	// check if the RRSet belongs to the zone
532 533
	if (!knot_dname_is_sub(rr->owner, z->apex->owner) &&
	    !knot_dname_is_equal(rr->owner, z->apex->owner)) {
Jan Kadlec's avatar
Jan Kadlec committed
534 535 536 537 538
		return KNOT_EOUTOFZONE;
	}

	int ret = KNOT_EOK;
	if (*n == NULL) {
Daniel Salzman's avatar
Daniel Salzman committed
539
		*n = nsec3 ? get_nsec3_node(z, rr->owner) : get_node(z, rr->owner);
Jan Kadlec's avatar
Jan Kadlec committed
540 541
		if (*n == NULL) {
			// Create new, insert
542
			*n = node_new(rr->owner, NULL);
Jan Kadlec's avatar
Jan Kadlec committed
543 544 545
			if (*n == NULL) {
				return KNOT_ENOMEM;
			}
Daniel Salzman's avatar
Daniel Salzman committed
546
			ret = nsec3 ? add_nsec3_node(z, *n) : add_node(z, *n, true);
Jan Kadlec's avatar
Jan Kadlec committed
547
			if (ret != KNOT_EOK) {
548
				node_free(n, NULL);
Jan Kadlec's avatar
Jan Kadlec committed
549 550 551 552
			}
		}
	}

553
	return node_add_rrset(*n, rr, NULL);
Jan Kadlec's avatar
Jan Kadlec committed
554 555
}

556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580
static int remove_rr(zone_contents_t *z, const knot_rrset_t *rr,
                     zone_node_t **n, bool nsec3)
{
	if (knot_rrset_empty(rr)) {
		return KNOT_EINVAL;
	}

	// check if the RRSet belongs to the zone
	if (!knot_dname_is_sub(rr->owner, z->apex->owner) &&
	    !knot_dname_is_equal(rr->owner, z->apex->owner)) {
		return KNOT_EOUTOFZONE;
	}

	zone_node_t *node;
	if (*n == NULL) {
		node = nsec3 ? get_nsec3_node(z, rr->owner) : get_node(z, rr->owner);
		if (node == NULL) {
			return KNOT_ENONODE;
		}
	} else {
		node = *n;
	}

	knot_rdataset_t *node_rrs = node_rdataset(node, rr->type);
	// Subtract changeset RRS from node RRS.
581
	int ret = knot_rdataset_subtract(node_rrs, &rr->rrs, NULL);
582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598
	if (ret != KNOT_EOK) {
		return ret;
	}

	if (node_rrs->rr_count == 0) {
		// RRSet is empty now, remove it from node, all data freed.
		node_remove_rdataset(node, rr->type);
		// If node is empty now, delete it from zone tree.
		if (node->rrset_count == 0) {
			zone_tree_delete_empty_node(nsec3 ? z->nsec3_nodes : z->nodes, node);
		}
	}

	*n = node;
	return KNOT_EOK;
}

599
static int recreate_normal_tree(const zone_contents_t *z, zone_contents_t *out)
600
{
601 602 603
	out->nodes = hattrie_dup(z->nodes, NULL);
	if (out->nodes == NULL) {
		return KNOT_ENOMEM;
604 605
	}

606
	// Insert APEX first.
607
	zone_node_t *apex_cpy = node_shallow_copy(z->apex, NULL);
608 609
	if (apex_cpy == NULL) {
		return KNOT_ENOMEM;
610 611
	}

612
	// Normal additions need apex ... so we need to insert directly.
613
	int ret = zone_tree_insert(out->nodes, apex_cpy);
614
	if (ret != KNOT_EOK) {
615
		node_free(&apex_cpy, NULL);
616
		return ret;
617 618
	}

619
	out->apex = apex_cpy;
620

621 622 623
	hattrie_iter_t *itt = hattrie_iter_begin(z->nodes, true);
	if (itt == NULL) {
		return KNOT_ENOMEM;
624
	}
Daniel Salzman's avatar
Daniel Salzman committed
625

626
	while (!hattrie_iter_finished(itt)) {
627
		const zone_node_t *to_cpy = (zone_node_t *)*hattrie_iter_val(itt);
628 629 630 631 632
		if (to_cpy == z->apex) {
			// Inserted already.
			hattrie_iter_next(itt);
			continue;
		}
633
		zone_node_t *to_add = node_shallow_copy(to_cpy, NULL);
634
		if (to_add == NULL) {
635
			hattrie_iter_free(itt);
636
			return KNOT_ENOMEM;
637
		}
638

639
		int ret = add_node(out, to_add, true);
640
		if (ret != KNOT_EOK) {
641
			node_free(&to_add, NULL);
642 643 644 645
			hattrie_iter_free(itt);
			return ret;
		}
		hattrie_iter_next(itt);
646 647
	}

648 649
	hattrie_iter_free(itt);
	hattrie_build_index(out->nodes);
650

651
	return KNOT_EOK;
652 653
}

654
static int recreate_nsec3_tree(const zone_contents_t *z, zone_contents_t *out)
655
{
656 657 658
	out->nsec3_nodes = hattrie_dup(z->nsec3_nodes, NULL);
	if (out->nsec3_nodes == NULL) {
		return KNOT_ENOMEM;
659 660
	}

661 662 663
	hattrie_iter_t *itt = hattrie_iter_begin(z->nsec3_nodes, false);
	if (itt == NULL) {
		return KNOT_ENOMEM;
664
	}
665
	while (!hattrie_iter_finished(itt)) {
666
		const zone_node_t *to_cpy = (zone_node_t *)*hattrie_iter_val(itt);
667
		zone_node_t *to_add = node_shallow_copy(to_cpy, NULL);
668
		if (to_add == NULL) {
669
			hattrie_iter_free(itt);
670
			return KNOT_ENOMEM;
671
		}
Daniel Salzman's avatar
Daniel Salzman committed
672

673
		int ret = add_nsec3_node(out, to_add);
674 675
		if (ret != KNOT_EOK) {
			hattrie_iter_free(itt);
676
			node_free(&to_add, NULL);
677 678
			return ret;
		}
Daniel Salzman's avatar
Daniel Salzman committed
679

680
		hattrie_iter_next(itt);
681
	}
682

683 684
	hattrie_iter_free(itt);
	hattrie_build_index(out->nsec3_nodes);
685

Lubos Slovak's avatar
Lubos Slovak committed
686
	return KNOT_EOK;
687 688
}

689 690
static zone_node_t *get_previous(const zone_contents_t *zone,
                                 const knot_dname_t *name)
691
{
692 693 694 695 696
	if (zone == NULL || name == NULL) {
		return NULL;
	}

	zone_node_t *found = NULL, *prev = NULL;
697
	(void)find_in_tree(zone->nodes, name, &found, &prev);
Dominik Taborsky's avatar
Dominik Taborsky committed
698
	assert(prev != NULL);
699 700 701 702 703 704

	return prev;
}

// Public API

705 706
int zone_contents_add_rr(zone_contents_t *z, const knot_rrset_t *rr,
                         zone_node_t **n)
Jan Kadlec's avatar
Jan Kadlec committed
707
{
708
	if (z == NULL || rr == NULL || n == NULL) {
709 710 711
		return KNOT_EINVAL;
	}

712 713 714
	return insert_rr(z, rr, n, knot_rrset_is_nsec3rel(rr));
}

715 716 717 718 719 720 721 722 723 724
int zone_contents_remove_rr(zone_contents_t *z, const knot_rrset_t *rr,
                            zone_node_t **n)
{
	if (z == NULL || rr == NULL || n == NULL) {
		return KNOT_EINVAL;
	}

	return remove_rr(z, rr, n, knot_rrset_is_nsec3rel(rr));
}

725 726 727 728 729 730 731 732 733 734 735
zone_node_t *zone_contents_get_node_for_rr(zone_contents_t *zone, const knot_rrset_t *rrset)
{
	if (zone == NULL || rrset == NULL) {
		return NULL;
	}

	const bool nsec3 = knot_rrset_is_nsec3rel(rrset);
	zone_node_t *node = nsec3 ? get_nsec3_node(zone, rrset->owner) :
	                            get_node(zone, rrset->owner);
	if (node == NULL) {
		node = node_new(rrset->owner, NULL);
Dominik Taborsky's avatar
Dominik Taborsky committed
736
		int ret = nsec3 ? add_nsec3_node(zone, node) : add_node(zone, node, true);
737 738 739 740 741 742 743 744 745 746 747 748
		if (ret != KNOT_EOK) {
			node_free(&node, NULL);
			return NULL;
		}

		return node;
	} else {
		return node;
	}
}

const zone_node_t *zone_contents_find_node(const zone_contents_t *zone, const knot_dname_t *name)
749
{
750
	return get_node(zone, name);
751 752
}

753 754 755 756 757 758 759 760 761 762 763
zone_node_t *zone_contents_find_node_for_rr(zone_contents_t *contents, const knot_rrset_t *rrset)
{
	if (contents == NULL || rrset == NULL) {
		return NULL;
	}

	const bool nsec3 = knot_rrset_is_nsec3rel(rrset);
	return nsec3 ? get_nsec3_node(contents, rrset->owner) :
	               get_node(contents, rrset->owner);
}

764
int zone_contents_find_dname(const zone_contents_t *zone,
765 766 767 768
                             const knot_dname_t *name,
                             const zone_node_t **node,
                             const zone_node_t **closest_encloser,
                             const zone_node_t **previous)
769 770 771 772
{
	if (zone == NULL || name == NULL || node == NULL
	    || closest_encloser == NULL || previous == NULL
	    || zone->apex == NULL || zone->apex->owner == NULL) {
Marek Vavrusa's avatar
Marek Vavrusa committed
773
		return KNOT_EINVAL;
774 775
	}

776
	zone_node_t *found = NULL, *prev = NULL;
777
	bool match = find_in_tree(zone->nodes, name, &found, &prev);
778 779 780

	*node = found;
	*previous = prev;
781 782 783

	// there must be at least one node with domain name less or equal to
	// the searched name if the name belongs to the zone (the root)
Lubos Slovak's avatar
Lubos Slovak committed
784
	if (*node == NULL && *previous == NULL) {
785
		return KNOT_EOUTOFZONE;
786 787
	}

Lubos Slovak's avatar
Lubos Slovak committed
788 789 790 791 792
	/* This function was quite out of date. The find_in_tree() function
	 * may return NULL in the 'found' field, so we cannot search for the
	 * closest encloser from this node.
	 */

793
	if (match) {
Lubos Slovak's avatar
Lubos Slovak committed
794 795
		*closest_encloser = *node;
	} else {
796 797 798 799 800 801
		if (!knot_dname_is_sub(name, zone->apex->owner)) {
			*node = NULL;
			*closest_encloser = NULL;
			return KNOT_EOUTOFZONE;
		}

Lubos Slovak's avatar
Lubos Slovak committed
802
		*closest_encloser = *previous;
Jan Kadlec's avatar
Jan Kadlec committed
803 804
		assert(*closest_encloser != NULL);

Daniel Salzman's avatar
Daniel Salzman committed
805
		int matched_labels = knot_dname_matched_labels((*closest_encloser)->owner, name);
806
		while (matched_labels < knot_dname_labels((*closest_encloser)->owner, NULL)) {
Daniel Salzman's avatar
Daniel Salzman committed
807
			*closest_encloser = (*closest_encloser)->parent;
Jan Kadlec's avatar
Jan Kadlec committed
808 809
			assert(*closest_encloser);
		}
810 811
	}

812
	return match ? ZONE_NAME_FOUND : ZONE_NAME_NOT_FOUND;
813 814
}

815 816
const zone_node_t *zone_contents_find_previous(const zone_contents_t *zone,
                                               const knot_dname_t *name)
817
{
818
	return get_previous(zone, name);
819 820
}

821
const zone_node_t *zone_contents_find_nsec3_node(const zone_contents_t *zone,
822
                                                 const knot_dname_t *name)
823
{
824
	return get_nsec3_node(zone, name);
825 826
}

827
int zone_contents_find_nsec3_for_name(const zone_contents_t *zone,
828 829 830
                                      const knot_dname_t *name,
                                      const zone_node_t **nsec3_node,
                                      const zone_node_t **nsec3_previous)
831
{
Daniel Salzman's avatar
Daniel Salzman committed
832 833
	if (zone == NULL || name == NULL || nsec3_node == NULL ||
	    nsec3_previous == NULL) {
Marek Vavrusa's avatar
Marek Vavrusa committed
834
		return KNOT_EINVAL;
835 836
	}

837
	// check if the NSEC3 tree is not empty
838
	if (zone_tree_is_empty(zone->nsec3_nodes)) {
839 840 841
		return KNOT_ENSEC3CHAIN;
	}

842
	knot_dname_t *nsec3_name = NULL;
843
	int ret = create_nsec3_name(zone, name, &nsec3_name);
Lubos Slovak's avatar
Lubos Slovak committed
844
	if (ret != KNOT_EOK) {
845 846 847
		return ret;
	}

848 849
	zone_node_t *found = NULL, *prev = NULL;
	bool match = find_in_tree(zone->nsec3_nodes, nsec3_name, &found, &prev);
Lubos Slovak's avatar
Lubos Slovak committed
850

851
	knot_dname_free(&nsec3_name, NULL);
852 853 854 855 856 857 858

	*nsec3_node = found;

	if (prev == NULL) {
		// either the returned node is the root of the tree, or it is
		// the leftmost node in the tree; in both cases node was found
		// set the previous node of the found node
859
		assert(match);
860
		assert(*nsec3_node != NULL);
861
		*nsec3_previous = (*nsec3_node)->prev;
862 863 864 865
	} else {
		*nsec3_previous = prev;
	}

Jan Včelák's avatar
Jan Včelák committed
866 867
	/* The previous may be from wrong NSEC3 chain. Search for previous
	 * from the right chain. Check iterations, hash algorithm and salt
868 869
	 * values and compare them to the ones from NSEC3PARAM.
	 */
Daniel Salzman's avatar
Daniel Salzman committed
870
	const knot_rdataset_t *nsec3_rrs = node_rdataset(*nsec3_previous, KNOT_RRTYPE_NSEC3);
871
	const zone_node_t *original_prev = *nsec3_previous;
Jan Včelák's avatar
Jan Včelák committed
872

873
	ret = match ? ZONE_NAME_FOUND : ZONE_NAME_NOT_FOUND;
Jan Včelák's avatar
Jan Včelák committed
874

875 876
	while (nsec3_rrs) {
		for (uint16_t i = 0; i < nsec3_rrs->rr_count; i++) {
Daniel Salzman's avatar
Daniel Salzman committed
877
			if (nsec3_params_match(nsec3_rrs, &zone->nsec3_params, i)) {
878
				return ret;
879
			}
880
		}
Jan Včelák's avatar
Jan Včelák committed
881

882
		/* This RRSET was not a match, try the one from previous node. */
883
		*nsec3_previous = (*nsec3_previous)->prev;
884
		nsec3_rrs = node_rdataset(*nsec3_previous, KNOT_RRTYPE_NSEC3);
885
		if (*nsec3_previous == original_prev || nsec3_rrs == NULL) {
886 887 888 889
			// cycle
			*nsec3_previous = NULL;
			break;
		}
890
	}
Jan Včelák's avatar
Jan Včelák committed
891

892
	return ret;
893 894
}

895 896
const zone_node_t *zone_contents_find_wildcard_child(const zone_contents_t *contents,
                                                     const zone_node_t *parent)
897
{
898
	if (contents == NULL || parent == NULL || parent->owner == NULL) {
899 900 901
		return NULL;
	}

902 903
	knot_dname_t wildcard[KNOT_DNAME_MAXLEN] = { 0x01, '*' };
	knot_dname_to_wire(wildcard + 2, parent->owner, KNOT_DNAME_MAXLEN - 2);
Daniel Salzman's avatar
Daniel Salzman committed
904

905
	return zone_contents_find_node(contents, wildcard);
906 907
}

Daniel Salzman's avatar
Daniel Salzman committed
908 909
static int adjust_nodes(zone_tree_t *nodes, zone_adjust_arg_t *adjust_arg,
                        zone_tree_apply_cb_t callback)
910 911 912 913
{
	assert(adjust_arg);
	assert(callback);

Daniel Salzman's avatar
Daniel Salzman committed
914 915 916 917
	if (zone_tree_is_empty(nodes)) {
		return KNOT_EOK;
	}

918 919 920
	adjust_arg->first_node = NULL;
	adjust_arg->previous_node = NULL;

921
	hattrie_build_index(nodes);
Daniel Salzman's avatar
Daniel Salzman committed
922
	int ret = zone_tree_apply_inorder(nodes, callback, adjust_arg);
923

924 925 926
	if (adjust_arg->first_node) {
		adjust_arg->first_node->prev = adjust_arg->previous_node;
	}
927

Daniel Salzman's avatar
Daniel Salzman committed
928
	return ret;
929 930
}

Daniel Salzman's avatar
Daniel Salzman committed
931
static int load_nsec3param(zone_contents_t *contents)
932
{
Daniel Salzman's avatar
Daniel Salzman committed
933 934
	assert(contents);
	assert(contents->apex);
935

Daniel Salzman's avatar
Daniel Salzman committed
936 937 938 939 940 941 942 943
	const knot_rdataset_t *rrs = node_rdataset(contents->apex,
	                                           KNOT_RRTYPE_NSEC3PARAM);
	if (rrs == NULL) {
		memset(&contents->nsec3_params, 0, sizeof(knot_nsec3_params_t));
		return KNOT_EOK;
	}

	return knot_nsec3param_from_wire(&contents->nsec3_params, rrs);
Daniel Salzman's avatar
Daniel Salzman committed
944
}
945

Daniel Salzman's avatar
Daniel Salzman committed
946
static int contents_adjust(zone_contents_t *contents, bool normal)
947
{
Daniel Salzman's avatar
Daniel Salzman committed
948 949 950 951 952
	if (contents == NULL || contents->apex == NULL) {
		return KNOT_EINVAL;
	}

	int ret = load_nsec3param(contents);
953
	if (ret != KNOT_EOK) {
954
		log_zone_error(contents->apex->owner,
Daniel Salzman's avatar
Daniel Salzman committed
955 956
		               "failed to load NSEC3 parameters (%s)",
		               knot_strerror(ret));
957 958
		return ret;
	}
959

Daniel Salzman's avatar
Daniel Salzman committed
960 961 962
	zone_adjust_arg_t arg = {
		.zone = contents
	};
Daniel Salzman's avatar
Daniel Salzman committed
963

Daniel Salzman's avatar
Daniel Salzman committed
964 965
	ret = adjust_nodes(contents->nodes, &arg,
	                   normal ? adjust_normal_node : adjust_pointers);
966 967
	if (ret != KNOT_EOK) {
		return ret;
968
	}
969

Daniel Salzman's avatar
Daniel Salzman committed
970
	ret = adjust_nodes(contents->nsec3_nodes, &arg, adjust_nsec3_node);
971 972 973 974
	if (ret != KNOT_EOK) {
		return ret;
	}

Daniel Salzman's avatar
Daniel Salzman committed
975
	return adjust_nodes(contents->nodes, &arg, adjust_additional);
976
}
977

Daniel Salzman's avatar
Daniel Salzman committed
978
int zone_contents_adjust_pointers(zone_contents_t *contents)
979
{
Daniel Salzman's avatar
Daniel Salzman committed
980
	return contents_adjust(contents, false);
981 982
}

Daniel Salzman's avatar
Daniel Salzman committed
983
int zone_contents_adjust_full(zone_contents_t *contents)
984
{
Daniel Salzman's avatar
Daniel Salzman committed
985
	return contents_adjust(contents, true);
986 987
}

988
int zone_contents_tree_apply_inorder(zone_contents_t *zone,
989
                                     zone_contents_apply_cb_t function, void *data)
990 991
{
	if (zone == NULL) {
Marek Vavrusa's avatar
Marek Vavrusa committed
992
		return KNOT_EINVAL;
993 994
	}

Daniel Salzman's avatar
Daniel Salzman committed
995 996 997 998
	zone_tree_func_t f = {
		.func = function,
		.data = data
	};
999

1000
	return zone_tree_apply_inorder(zone->nodes, tree_apply_cb, &f);
1001 1002
}

1003
int zone_contents_nsec3_apply_inorder(zone_contents_t *zone,
1004
                                      zone_contents_apply_cb_t function, void *data)
1005 1006
{
	if (zone == NULL) {
Marek Vavrusa's avatar
Marek Vavrusa committed
1007
		return KNOT_EINVAL;
1008 1009
	}

Daniel Salzman's avatar
Daniel Salzman committed
1010 1011 1012 1013
	zone_tree_func_t f = {
		.func = function,
		.data = data
	};
1014

Daniel Salzman's avatar
Daniel Salzman committed
1015
	return zone_tree_apply_inorder(zone->nsec3_nodes, tree_apply_cb, &f);
1016 1017
}

1018
int zone_contents_shallow_copy(const zone_contents_t *from, zone_contents_t **to)
1019
{
1020 1021 1022
	if (from == NULL || to == NULL) {
		return KNOT_EINVAL;
	}
1023

1024 1025 1026 1027
	/* Copy to same destination as source. */
	if (from == *to) {
		return KNOT_EINVAL;
	}
1028

1029
	zone_contents_t *contents = calloc(1, sizeof(zone_contents_t));
1030 1031 1032
	if (contents == NULL) {
		return KNOT_ENOMEM;
	}
1033

1034 1035
	int ret = recreate_normal_tree(from, contents);
	if (ret != KNOT_EOK) {
1036
		zone_tree_free(&contents->nodes);
1037 1038
		free(contents);
		return ret;
1039
	}
1040

1041
	if (from->nsec3_nodes) {
1042 1043
		ret = recreate_nsec3_tree(from, contents);
		if (ret != KNOT_EOK) {
1044 1045
			zone_tree_free(&contents->nodes);
			zone_tree_free(&contents->nsec3_nodes);
1046 1047 1048 1049 1050 1051
			free(contents);
			return ret;
		}
	} else {
		contents->nsec3_nodes = NULL;
	}
1052

1053 1054 1055
	*to = contents;
	return KNOT_EOK;
}
1056

1057
void zone_contents_free(zone_contents_t **contents)
1058 1059 1060 1061 1062 1063
{
	if (contents == NULL || *contents == NULL) {
		return;
	}

	// free the zone tree, but only the structure
1064 1065
	zone_tree_free(&(*contents)->nodes);
	zone_tree_free(&(*contents)->nsec3_nodes);
1066

1067
	knot_nsec3param_free(&(*contents)->nsec3_params);
Jan Včelák's avatar
Jan Včelák committed
1068

1069 1070 1071 1072
	free(*contents);
	*contents = NULL;
}

1073
void zone_contents_deep_free(zone_contents_t **contents)
1074 1075 1076 1077 1078
{
	if (contents == NULL || *contents == NULL) {
		return;
	}

Daniel Salzman's avatar
Daniel Salzman committed
1079
	if (*contents != NULL) {
1080
		// Delete NSEC3 tree
Daniel Salzman's avatar
Daniel Salzman committed
1081
		zone_tree_apply((*contents)->nsec3_nodes, destroy_node_rrsets_from_tree, NULL);
Lubos Slovak's avatar