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 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599
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;
	}

	int ret = KNOT_EOK;
	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.
	ret = knot_rdataset_subtract(node_rrs, &rr->rrs, NULL);
	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;
}

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

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

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

620
	out->apex = apex_cpy;
621

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

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

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

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

652
	return KNOT_EOK;
653 654
}

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

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

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

681
		hattrie_iter_next(itt);
682
	}
683

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

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

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

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

	return prev;
}

// Public API

706 707
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
708
{
709
	if (z == NULL || rr == NULL || n == NULL) {
710 711 712
		return KNOT_EINVAL;
	}

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

716 717 718 719 720 721 722 723 724 725
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));
}

726 727 728 729 730 731 732 733 734 735 736
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
737
		int ret = nsec3 ? add_nsec3_node(zone, node) : add_node(zone, node, true);
738 739 740 741 742 743 744 745 746 747 748 749
		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)
750
{
751
	return get_node(zone, name);
752 753
}

754 755 756 757 758 759 760 761 762 763 764
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);
}

765
int zone_contents_find_dname(const zone_contents_t *zone,
766 767 768 769
                             const knot_dname_t *name,
                             const zone_node_t **node,
                             const zone_node_t **closest_encloser,
                             const zone_node_t **previous)
770 771 772 773
{
	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
774
		return KNOT_EINVAL;
775 776
	}

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

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

	// 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
785
	if (*node == NULL && *previous == NULL) {
786
		return KNOT_EOUTOFZONE;
787 788
	}

Lubos Slovak's avatar
Lubos Slovak committed
789 790 791 792 793
	/* 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.
	 */

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

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

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

813
	return match ? ZONE_NAME_FOUND : ZONE_NAME_NOT_FOUND;
814 815
}

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

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

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

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

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

849 850
	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
851

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

	*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
860
		assert(match);
861
		assert(*nsec3_node != NULL);
862
		*nsec3_previous = (*nsec3_node)->prev;
863 864 865 866
	} else {
		*nsec3_previous = prev;
	}

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

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

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

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

893
	return ret;
894 895
}

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

903 904
	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
905

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

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

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

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

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

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

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

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

Daniel Salzman's avatar
Daniel Salzman committed
937 938 939 940 941 942 943 944
	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
945
}
946

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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