contents.c 29.7 KB
Newer Older
1
/*  Copyright (C) 2011 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 "libknot/internal/trie/hat-trie.h"
24
#include "libknot/internal/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 63
{
	if (contents == NULL || node == NULL) {
Marek Vavrusa's avatar
Marek Vavrusa committed
64
		return KNOT_EINVAL;
65 66 67
	}

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

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

/*!
 * \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
83
static int destroy_node_rrsets_from_tree(zone_node_t **tnode, void *data)
84
{
85
	assert(tnode != NULL);
Daniel Salzman's avatar
Daniel Salzman committed
86 87
	UNUSED(data);

88
	if (*tnode != NULL) {
89
		node_free_rrsets(*tnode, NULL);
90
		node_free(tnode, NULL);
91
	}
92

93
	return KNOT_EOK;
94 95
}

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

Daniel Salzman's avatar
Daniel Salzman committed
103
	*nsec3_name = NULL;
104

Daniel Salzman's avatar
Daniel Salzman committed
105
	const knot_nsec3_params_t *nsec3_params = zone_contents_nsec3params(zone);
106 107 108 109
	if (nsec3_params == NULL) {
		return KNOT_ENSEC3PAR;
	}

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

	return KNOT_EOK;
}

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

123
	const knot_rdataset_t *rrs = &rr_data->rrs;
124 125

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

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

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

148
		rr_data->additional[i] = (zone_node_t *)node;
149 150 151 152
	}

	return KNOT_EOK;
}
153

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

159
	zone_adjust_arg_t *args = (zone_adjust_arg_t *)data;
160
	zone_node_t *node = *tnode;
161

162
	// remember first node
163
	if (args->first_node == NULL) {
164
		args->first_node = node;
165
	}
166

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

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

176
	// set flags (delegation point, non-authoritative)
177
	if (node->parent &&
Daniel Salzman's avatar
Daniel Salzman committed
178
	    (node->parent->flags & NODE_FLAGS_DELEG ||
179 180 181 182
	     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
183
	} else {
184 185
		// Default.
		node->flags = NODE_FLAGS_AUTH;
Jan Kadlec's avatar
Jan Kadlec committed
186 187
	}

188
	// set pointer to previous node
189
	node->prev = args->previous_node;
190

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

196 197 198
	return KNOT_EOK;
}

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

204
	zone_adjust_arg_t *args = (zone_adjust_arg_t *)data;
205
	zone_node_t *node = *tnode;
Daniel Salzman's avatar
Daniel Salzman committed
206

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

220
	knot_dname_free(&nsec3_name, NULL);
Daniel Salzman's avatar
Daniel Salzman committed
221

222
	return ret;
223 224
}

225 226 227 228 229 230 231 232 233 234
/*!
 * \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.
235
 * \param data   Adjusting parameters (zone_adjust_arg_t *).
236
 */
237
static int adjust_normal_node(zone_node_t **tnode, void *data)
238 239
{
	assert(tnode != NULL && *tnode);
Daniel Salzman's avatar
Daniel Salzman committed
240 241
	assert(data != NULL);

242 243 244 245 246 247 248 249 250 251
	// 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);
}

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

267
	zone_adjust_arg_t *args = (zone_adjust_arg_t *)data;
268
	zone_node_t *node = *tnode;
269

270
	// remember first node
271
	if (args->first_node == NULL) {
272
		args->first_node = node;
273
	}
274 275

	// set previous node
276
	node->prev = args->previous_node;
277
	args->previous_node = node;
278 279

	return KNOT_EOK;
280
}
281 282

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

288
	zone_adjust_arg_t *args = (zone_adjust_arg_t *)data;
289
	zone_node_t *node = *tnode;
290 291 292

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

Daniel Salzman's avatar
Daniel Salzman committed
302
	return KNOT_EOK;
303 304
}

305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320
/*!
 * \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).
 *
 * \retval <> 0 if the domain name was found. In such case \a node holds the
 *              zone node with \a name as its owner. \a previous is set
 *              properly.
 * \retval 0 if the domain name was not found. \a node may hold any (or none)
 *           node. \a previous is set properly.
 */
Daniel Salzman's avatar
Daniel Salzman committed
321 322
static int find_in_tree(zone_tree_t *tree, const knot_dname_t *name,
                        zone_node_t **node, zone_node_t **previous)
323
{
324
	assert(tree != NULL);
325 326 327 328
	assert(name != NULL);
	assert(node != NULL);
	assert(previous != NULL);

329
	zone_node_t *found = NULL, *prev = NULL;
330

Daniel Salzman's avatar
Daniel Salzman committed
331
	int exact_match = zone_tree_get_less_or_equal(tree, name, &found, &prev);
Lubos Slovak's avatar
Lubos Slovak committed
332
	assert(exact_match >= 0);
Daniel Salzman's avatar
Daniel Salzman committed
333

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

	return exact_match;
}

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 successfull??
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 (z == NULL || knot_rrset_empty(rr) || n == NULL) {
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
static int recreate_normal_tree(const zone_contents_t *z, zone_contents_t *out)
557
{
558 559 560
	out->nodes = hattrie_dup(z->nodes, NULL);
	if (out->nodes == NULL) {
		return KNOT_ENOMEM;
561 562
	}

563
	// Insert APEX first.
564
	zone_node_t *apex_cpy = node_shallow_copy(z->apex, NULL);
565 566
	if (apex_cpy == NULL) {
		return KNOT_ENOMEM;
567 568
	}

569
	// Normal additions need apex ... so we need to insert directly.
570
	int ret = zone_tree_insert(out->nodes, apex_cpy);
571
	if (ret != KNOT_EOK) {
572
		node_free(&apex_cpy, NULL);
573
		return ret;
574 575
	}

576
	out->apex = apex_cpy;
577

578 579 580
	hattrie_iter_t *itt = hattrie_iter_begin(z->nodes, true);
	if (itt == NULL) {
		return KNOT_ENOMEM;
581
	}
Daniel Salzman's avatar
Daniel Salzman committed
582

583
	while (!hattrie_iter_finished(itt)) {
584
		const zone_node_t *to_cpy = (zone_node_t *)*hattrie_iter_val(itt);
585 586 587 588 589
		if (to_cpy == z->apex) {
			// Inserted already.
			hattrie_iter_next(itt);
			continue;
		}
590
		zone_node_t *to_add = node_shallow_copy(to_cpy, NULL);
591
		if (to_add == NULL) {
592
			hattrie_iter_free(itt);
593
			return KNOT_ENOMEM;
594
		}
595

596
		int ret = add_node(out, to_add, true);
597
		if (ret != KNOT_EOK) {
598
			node_free(&to_add, NULL);
599 600 601 602
			hattrie_iter_free(itt);
			return ret;
		}
		hattrie_iter_next(itt);
603 604
	}

605 606
	hattrie_iter_free(itt);
	hattrie_build_index(out->nodes);
607

608
	return KNOT_EOK;
609 610
}

611
static int recreate_nsec3_tree(const zone_contents_t *z, zone_contents_t *out)
612
{
613 614 615
	out->nsec3_nodes = hattrie_dup(z->nsec3_nodes, NULL);
	if (out->nsec3_nodes == NULL) {
		return KNOT_ENOMEM;
616 617
	}

618 619 620
	hattrie_iter_t *itt = hattrie_iter_begin(z->nsec3_nodes, false);
	if (itt == NULL) {
		return KNOT_ENOMEM;
621
	}
622
	while (!hattrie_iter_finished(itt)) {
623
		const zone_node_t *to_cpy = (zone_node_t *)*hattrie_iter_val(itt);
624
		zone_node_t *to_add = node_shallow_copy(to_cpy, NULL);
625
		if (to_add == NULL) {
626
			hattrie_iter_free(itt);
627
			return KNOT_ENOMEM;
628
		}
Daniel Salzman's avatar
Daniel Salzman committed
629

630
		int ret = add_nsec3_node(out, to_add);
631 632
		if (ret != KNOT_EOK) {
			hattrie_iter_free(itt);
633
			node_free(&to_add, NULL);
634 635
			return ret;
		}
Daniel Salzman's avatar
Daniel Salzman committed
636

637
		hattrie_iter_next(itt);
638
	}
639

640 641
	hattrie_iter_free(itt);
	hattrie_build_index(out->nsec3_nodes);
642

Lubos Slovak's avatar
Lubos Slovak committed
643
	return KNOT_EOK;
644 645
}

646 647
static zone_node_t *get_previous(const zone_contents_t *zone,
                                 const knot_dname_t *name)
648
{
649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673
	if (zone == NULL || name == NULL) {
		return NULL;
	}

	zone_node_t *found = NULL, *prev = NULL;

	int exact_match = find_in_tree(zone->nodes, name, &found, &prev);
	assert(exact_match >= 0);
	//assert(prev != NULL);

	return prev;
}

static zone_node_t *zone_contents_get_greatest_child(const zone_contents_t *zone, const knot_dname_t *parent)
{
	if (knot_dname_size(parent) + 2 > KNOT_DNAME_MAXLEN) {
		// Not enough space for children.
		return NULL;
	}

	knot_dname_t dn[KNOT_DNAME_MAXLEN] = { 0x01, 0xff };
	knot_dname_to_wire(dn + 2, parent, KNOT_DNAME_MAXLEN);
	zone_node_t *child = get_node(zone, dn);
	if (child) {
		return child;
674 675
	}

676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696
	child = get_previous(zone, dn);
	if (!child) {
		return NULL;
	}
	//assert(child);
	const int parent_labels = knot_dname_labels(parent, NULL);
	const int child_labels = knot_dname_labels(child->owner, NULL);
	if (child_labels <= parent_labels) {
		return NULL;
	}

	if (knot_dname_matched_labels(parent, child->owner) != parent_labels) {
		return NULL;
	}

	return child;
}

static bool contents_has_children(const zone_contents_t *zone, const knot_dname_t *owner)
{
	return zone_contents_get_greatest_child(zone, owner) != NULL;
697 698
}

699 700
// Public API

701 702
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
703
{
704 705 706 707
	if (z == NULL || rr == NULL) {
		return KNOT_EINVAL;
	}

708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765
	return insert_rr(z, rr, n, knot_rrset_is_nsec3rel(rr));
}

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);
		int ret = nsec3 ? add_nsec3_node(zone, node) : add_node(zone, node, 1);
		if (ret != KNOT_EOK) {
			node_free(&node, NULL);
			return NULL;
		}

		return node;
	} else {
		return node;
	}
}

int zone_contents_delete_empty_node(zone_contents_t *contents, zone_tree_t *tree, zone_node_t *node)
{
	if (!contents || !tree || !node) {
		return KNOT_EINVAL;
	}

	if (node->rrset_count == 0 && !contents_has_children(contents, node->owner)) {
		const knot_dname_t *parent_dname = knot_wire_next_label(node->owner, NULL);
		zone_node_t *parent_node = NULL;
		if (tree == contents->nsec3_nodes) {
			// Only one level in NSEC3 tree
			parent_node = (node == contents->apex) ? NULL : contents->apex;
		} else {
			parent_node = (zone_node_t *) zone_contents_find_node(contents, parent_dname);
		}

		if (parent_node && parent_node != contents->apex) {
			// Recurse using the parent node, do not delete possibly empty parent.
			int ret = zone_contents_delete_empty_node(contents, tree, parent_node);
			if (ret != KNOT_EOK) {
				return ret;
			}
		}

		// Delete node
		zone_node_t *removed_node = NULL;
		zone_tree_remove(tree, node->owner, &removed_node);
		UNUSED(removed_node);
		node_free(&node, NULL);
	}

	return KNOT_EOK;
766 767
}

768
const zone_node_t *zone_contents_find_node(const zone_contents_t *zone, const knot_dname_t *name)
769
{
770
	return get_node(zone, name);
771 772
}

773 774 775 776 777 778 779 780 781 782 783
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);
}

784
int zone_contents_find_dname(const zone_contents_t *zone,
785 786 787 788
                             const knot_dname_t *name,
                             const zone_node_t **node,
                             const zone_node_t **closest_encloser,
                             const zone_node_t **previous)
789 790 791 792
{
	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
793
		return KNOT_EINVAL;
794 795
	}

796
	zone_node_t *found = NULL, *prev = NULL;
797

Daniel Salzman's avatar
Daniel Salzman committed
798
	int exact_match = find_in_tree(zone->nodes, name, &found, &prev);
Lubos Slovak's avatar
Lubos Slovak committed
799
	assert(exact_match >= 0);
800 801
	*node = found;
	*previous = prev;
802 803 804

	// 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
805
	if (*node == NULL && *previous == NULL) {
806
		return KNOT_EOUTOFZONE;
807 808
	}

Lubos Slovak's avatar
Lubos Slovak committed
809 810 811 812 813 814 815 816
	/* 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.
	 */

	if (exact_match) {
		*closest_encloser = *node;
	} else {
817 818 819 820 821 822
		if (!knot_dname_is_sub(name, zone->apex->owner)) {
			*node = NULL;
			*closest_encloser = NULL;
			return KNOT_EOUTOFZONE;
		}

Lubos Slovak's avatar
Lubos Slovak committed
823
		*closest_encloser = *previous;
Jan Kadlec's avatar
Jan Kadlec committed
824 825
		assert(*closest_encloser != NULL);

Daniel Salzman's avatar
Daniel Salzman committed
826
		int matched_labels = knot_dname_matched_labels((*closest_encloser)->owner, name);
827
		while (matched_labels < knot_dname_labels((*closest_encloser)->owner, NULL)) {
Daniel Salzman's avatar
Daniel Salzman committed
828
			*closest_encloser = (*closest_encloser)->parent;
Jan Kadlec's avatar
Jan Kadlec committed
829 830
			assert(*closest_encloser);
		}
831 832
	}

Daniel Salzman's avatar
Daniel Salzman committed
833
	return exact_match ? ZONE_NAME_FOUND : ZONE_NAME_NOT_FOUND;
834 835
}

836 837
const zone_node_t *zone_contents_find_previous(const zone_contents_t *zone,
                                               const knot_dname_t *name)
838
{
839
	return get_previous(zone, name);
840 841
}

842
const zone_node_t *zone_contents_find_nsec3_node(const zone_contents_t *zone,
843
                                                 const knot_dname_t *name)
844
{
845
	return get_nsec3_node(zone, name);
846 847
}

848
int zone_contents_find_nsec3_for_name(const zone_contents_t *zone,
849 850 851
                                      const knot_dname_t *name,
                                      const zone_node_t **nsec3_node,
                                      const zone_node_t **nsec3_previous)
852
{
Daniel Salzman's avatar
Daniel Salzman committed
853 854
	if (zone == NULL || name == NULL || nsec3_node == NULL ||
	    nsec3_previous == NULL) {
Marek Vavrusa's avatar
Marek Vavrusa committed
855
		return KNOT_EINVAL;
856 857
	}

858
	// check if the NSEC3 tree is not empty
859
	if (zone_tree_is_empty(zone->nsec3_nodes)) {
860 861 862
		return KNOT_ENSEC3CHAIN;
	}

863
	knot_dname_t *nsec3_name = NULL;
864
	int ret = create_nsec3_name(zone, name, &nsec3_name);
Lubos Slovak's avatar
Lubos Slovak committed
865
	if (ret != KNOT_EOK) {
866 867 868
		return ret;
	}

869
	const zone_node_t *found = NULL, *prev = NULL;
870

Daniel Salzman's avatar
Daniel Salzman committed
871 872
	int exact_match = zone_tree_find_less_or_equal(zone->nsec3_nodes, nsec3_name,
	                                               &found, &prev);
Lubos Slovak's avatar
Lubos Slovak committed
873
	assert(exact_match >= 0);
Lubos Slovak's avatar
Lubos Slovak committed
874

875
	knot_dname_free(&nsec3_name, NULL);
876 877 878 879 880 881 882

	*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
883
		assert(exact_match > 0);
884
		assert(*nsec3_node != NULL);
885
		*nsec3_previous = (*nsec3_node)->prev;
886 887 888 889
	} else {
		*nsec3_previous = prev;
	}

Jan Včelák's avatar
Jan Včelák committed
890 891
	/* The previous may be from wrong NSEC3 chain. Search for previous
	 * from the right chain. Check iterations, hash algorithm and salt
892 893
	 * values and compare them to the ones from NSEC3PARAM.
	 */
Daniel Salzman's avatar
Daniel Salzman committed
894
	const knot_rdataset_t *nsec3_rrs = node_rdataset(*nsec3_previous, KNOT_RRTYPE_NSEC3);
895
	const zone_node_t *original_prev = *nsec3_previous;
Jan Včelák's avatar
Jan Včelák committed
896

897
	ret = exact_match ? ZONE_NAME_FOUND : ZONE_NAME_NOT_FOUND;
Jan Včelák's avatar
Jan Včelák committed
898

899 900
	while (nsec3_rrs) {
		for (uint16_t i = 0; i < nsec3_rrs->rr_count; i++) {
Daniel Salzman's avatar
Daniel Salzman committed
901
			if (nsec3_params_match(nsec3_rrs, &zone->nsec3_params, i)) {
902
				return ret;
903
			}
904
		}
Jan Včelák's avatar
Jan Včelák committed
905

906
		/* This RRSET was not a match, try the one from previous node. */
907
		*nsec3_previous = (*nsec3_previous)->prev;
908
		nsec3_rrs = node_rdataset(*nsec3_previous, KNOT_RRTYPE_NSEC3);
909
		if (*nsec3_previous == original_prev || nsec3_rrs == NULL) {
910 911 912 913
			// cycle
			*nsec3_previous = NULL;
			break;
		}
914
	}
Jan Včelák's avatar
Jan Včelák committed
915

916
	return ret;
917 918
}

919 920
const zone_node_t *zone_contents_find_wildcard_child(const zone_contents_t *contents,
                                                     const zone_node_t *parent)
921
{
922
	if (contents == NULL || parent == NULL || parent->owner == NULL) {
923 924 925
		return NULL;
	}

926 927
	knot_dname_t wildcard[KNOT_DNAME_MAXLEN] = { 0x01, '*' };
	knot_dname_to_wire(wildcard + 2, parent->owner, KNOT_DNAME_MAXLEN - 2);
928
	return zone_contents_find_node(contents, wildcard);
929 930
}

Daniel Salzman's avatar
Daniel Salzman committed
931 932
static int adjust_nodes(zone_tree_t *nodes, zone_adjust_arg_t *adjust_arg,
                        zone_tree_apply_cb_t callback)
933
{
934
	if (zone_tree_is_empty(nodes)) {
935 936 937
		return KNOT_EOK;
	}

938 939 940 941
	assert(nodes);
	assert(adjust_arg);
	assert(callback);

942 943 944
	adjust_arg->first_node = NULL;
	adjust_arg->previous_node = NULL;

945
	hattrie_build_index(nodes);
946
	int result = zone_tree_apply_inorder(nodes, callback, adjust_arg);
947

948 949 950
	if (adjust_arg->first_node) {
		adjust_arg->first_node->prev = adjust_arg->previous_node;
	}
951

952
	return result;
953 954
}

955
static int adjust_nsec3_tree(zone_contents_t *contents)
956 957
{
	// adjusting parameters
958 959 960
	zone_adjust_arg_t adjust_arg = { .first_node = NULL,
	                                 .previous_node = NULL,
	                                 .zone = contents };
961

Daniel Salzman's avatar
Daniel Salzman committed
962 963
	return adjust_nodes(contents->nsec3_nodes, &adjust_arg, adjust_nsec3_node);
}
964

965
int zone_contents_adjust_pointers(zone_contents_t *contents)
966
{
967
	int ret = zone_contents_load_nsec3param(contents);
968
	if (ret != KNOT_EOK) {
969
		log_zone_error(contents->apex->owner,
Daniel Salzman's avatar
Daniel Salzman committed
970 971
		               "failed to load NSEC3 parameters (%s)",
		               knot_strerror(ret));
972 973
		return ret;
	}
974

975
	// adjusting parameters
976 977 978
	zone_adjust_arg_t adjust_arg = { .first_node = NULL,
	                                 .previous_node = NULL,
	                                 .zone = contents };
Daniel Salzman's avatar
Daniel Salzman committed
979 980

	ret =  adjust_nodes(contents->nodes, &adjust_arg, adjust_pointers);
981 982
	if (ret != KNOT_EOK) {
		return ret;
983
	}
984

985
	ret = adjust_nsec3_tree(contents);
986 987 988 989
	if (ret != KNOT_EOK) {
		return ret;
	}

Daniel Salzman's avatar
Daniel Salzman committed
990
	return adjust_nodes(contents->nodes, &adjust_arg, adjust_additional);
991 992
}

993
int zone_contents_adjust_full(zone_contents_t *zone,
994 995
                              zone_node_t **first_nsec3_node,
                              zone_node_t **last_nsec3_node)
996
{
997
	if (zone == NULL) {
Marek Vavrusa's avatar
Marek Vavrusa committed
998
		return KNOT_EINVAL;
999
	}
Jan Včelák's avatar
Jan Včelák committed
1000

1001
	int result = zone_contents_load_nsec3param(zone);
1002
	if (result != KNOT_EOK) {
1003
		log_zone_error(zone->apex->owner,
Daniel Salzman's avatar
Daniel Salzman committed
1004 1005
		               "failed to load NSEC3 parameters (%s)",
		               knot_strerror(result));
1006
		return result;
1007
	}
Jan Včelák's avatar
Jan Včelák committed
1008

1009
	// adjusting parameters
1010
	zone_adjust_arg_t adjust_arg = { 0 };
1011 1012
	adjust_arg.zone = zone;

1013
	// adjust NSEC3 nodes
Daniel Salzman's avatar
Daniel Salzman committed
1014
	result = adjust_nodes(zone->nsec3_nodes, &adjust_arg, adjust_nsec3_node);
1015 1016
	if (result != KNOT_EOK) {
		return result;
Lubos Slovak's avatar
Lubos Slovak committed
1017
	}
1018

1019
	// optional output for NSEC3 nodes
1020 1021 1022 1023 1024 1025
	if (first_nsec3_node) {
		*first_nsec3_node = adjust_arg.first_node;
	}
	if (last_nsec3_node) {
		*last_nsec3_node = adjust_arg.previous_node;
	}
1026

1027
	// adjust normal nodes
Daniel Salzman's avatar
Daniel Salzman committed
1028
	result = adjust_nodes(zone->nodes, &adjust_arg, adjust_normal_node);
1029 1030
	if (result != KNOT_EOK) {
		return result;
1031 1032
	}

1033
	assert(zone->apex == adjust_arg.first_node);
1034

1035 1036 1037 1038
	/* Discover additional records.
	 * \note This MUST be done after node adjusting because it needs to
	 *       do full lookup to see through wildcards. */

Daniel Salzman's avatar
Daniel Salzman committed
1039
	return adjust_nodes(zone->nodes, &adjust_arg, adjust_additional);
1040
}
1041

1042
int zone_contents_load_nsec3param(zone_contents_t *zone)
1043 1044
{
	if (zone == NULL || zone->apex == NULL) {
Marek Vavrusa's avatar
Marek Vavrusa committed
1045
		return KNOT_EINVAL;
1046 1047
	}

1048
	const knot_rdataset_t *rrs = node_rdataset(zone->apex, KNOT_RRTYPE_NSEC3PARAM);
1049
	if (rrs!= NULL) {
1050
		int r = knot_nsec3param_from_wire(&zone->nsec3_params, rrs);
1051 1052 1053
		if (r != KNOT_EOK) {
			return r;
		}
1054
	} else {
1055
		memset(&zone->nsec3_params, 0, sizeof(knot_nsec3_params_t));
1056 1057
	}

Lubos Slovak's avatar
Lubos Slovak committed
1058
	return KNOT_EOK;
1059 1060
}

1061
const knot_nsec3_params_t *zone_contents_nsec3params(const zone_contents_t *zone)
1062 1063 1064 1065 1066
{
	if (zone == NULL) {
		return NULL;
	}

1067
	if (knot_is_nsec3_enabled(zone)) {
1068 1069 1070 1071 1072 1073
		return &zone->nsec3_params;
	} else {
		return NULL;
	}
}

1074
int zone_contents_tree_apply_inorder(zone_contents_t *zone,
1075
                                     zone_contents_apply_cb_t function, void *data)
1076 1077
{
	if (zone == NULL) {
Marek Vavrusa's avatar
Marek Vavrusa committed
1078
		return KNOT_EINVAL;
1079 1080
	}

1081
	zone_tree_func_t f;
1082 1083 1084
	f.func = function;
	f.data = data;

1085
	return zone_tree_apply_inorder(zone->nodes, tree_apply_cb, &f);
1086 1087