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"
Daniel Salzman's avatar
Daniel Salzman committed
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);
Lubos Slovak's avatar
Lubos Slovak committed
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
	}
Lubos Slovak's avatar
Lubos Slovak committed
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
	}
Lubos Slovak's avatar
Lubos Slovak committed
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;
Lubos Slovak's avatar
Lubos Slovak committed
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
	}
Lubos Slovak's avatar
Lubos Slovak committed
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)
Lubos Slovak's avatar
Lubos Slovak committed
390
{
391 392
	if (zone == NULL || name == NULL) {
		return NULL;
Lubos Slovak's avatar
Lubos Slovak committed
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;
Lubos Slovak's avatar
Lubos Slovak committed
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
Fixes  
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
Fixes  
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
Fixes  
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
Jan Kadlec's avatar
Jan Kadlec committed
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