contents.c 37.6 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 "common/debug.h"
21
#include "common/macros.h"
Jan Kadlec's avatar
Jan Kadlec committed
22
#include "libknot/rrset.h"
23
#include "common/base32hex.h"
24
#include "libknot/descriptor.h"
25
#include "common/trie/hat-trie.h"
26 27
#include "knot/dnssec/zone-nsec.h"
#include "knot/dnssec/zone-sign.h"
28
#include "knot/zone/zone-tree.h"
29
#include "libknot/packet/wire.h"
30
#include "libknot/consts.h"
31 32 33 34
#include "libknot/rrtype/rrsig.h"
#include "libknot/rrtype/nsec3.h"
#include "libknot/rrtype/soa.h"
#include "libknot/rrtype/rdname.h"
35 36 37 38

/*----------------------------------------------------------------------------*/
/* Non-API functions                                                          */
/*----------------------------------------------------------------------------*/
39 40

typedef struct {
41
	zone_contents_apply_cb_t func;
42
	void *data;
43
} zone_tree_func_t;
44

45
typedef struct {
46
	zone_node_t *first_node;
47
	zone_contents_t *zone;
48
	zone_node_t *previous_node;
49
} zone_adjust_arg_t;
50

51 52
/*----------------------------------------------------------------------------*/

53
static int tree_apply_cb(zone_node_t **node, void *data)
54 55
{
	if (node == NULL || data == NULL) {
56
		return KNOT_EINVAL;
57 58
	}

59
	zone_tree_func_t *f = (zone_tree_func_t *)data;
60
	return f->func(*node, f->data);
61 62 63
}

/*----------------------------------------------------------------------------*/
64 65 66 67 68 69 70 71 72
/*!
 * \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
73
 * \retval KNOT_EOK if both arguments are non-NULL and the node belongs to the
74
 *         zone.
Marek Vavrusa's avatar
Marek Vavrusa committed
75
 * \retval KNOT_EINVAL if either of the arguments is NULL.
76
 * \retval KNOT_EOUTOFZONE if the node does not belong to the zone.
77
 */
78
static int zone_contents_check_node(
79
	const zone_contents_t *contents, const zone_node_t *node)
80 81
{
	if (contents == NULL || node == NULL) {
Marek Vavrusa's avatar
Marek Vavrusa committed
82
		return KNOT_EINVAL;
83 84 85 86 87
	}

	// assert or just check??
	assert(contents->apex != NULL);

88
	if (!knot_dname_is_sub(node->owner,
89
				       contents->apex->owner)) {
90
		return KNOT_EOUTOFZONE;
91
	}
Lubos Slovak's avatar
Lubos Slovak committed
92
	return KNOT_EOK;
93 94 95 96 97 98 99 100 101 102 103
}

/*----------------------------------------------------------------------------*/
/*!
 * \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.
 */
104
static int zone_contents_destroy_node_rrsets_from_tree(
105
	zone_node_t **tnode, void *data)
106
{
107
	UNUSED(data);
108
	assert(tnode != NULL);
109
	if (*tnode != NULL) {
110
		node_free_rrsets(*tnode, NULL);
111
		node_free(tnode, NULL);
112
	}
113

114
	return KNOT_EOK;
115 116
}

117 118
/*----------------------------------------------------------------------------*/

119
static int zone_contents_nsec3_name(const zone_contents_t *zone,
120 121 122 123 124 125 126
                                         const knot_dname_t *name,
                                         knot_dname_t **nsec3_name)
{
	assert(nsec3_name != NULL);
	*nsec3_name = NULL;

	const knot_nsec3_params_t *nsec3_params =
127
		zone_contents_nsec3params(zone);
128 129 130 131 132

	if (nsec3_params == NULL) {
		return KNOT_ENSEC3PAR;
	}

133 134
	*nsec3_name = knot_create_nsec3_owner(name, zone->apex->owner,
	                                      nsec3_params);
135
	if (*nsec3_name == NULL) {
136 137 138 139 140 141
		return KNOT_ERROR;
	}

	return KNOT_EOK;
}

142
/*! \brief Link pointers to additional nodes for this RRSet. */
143
static int discover_additionals(struct rr_data *rr_data,
144
                                zone_contents_t *zone)
145
{
146
	const zone_node_t *node = NULL, *encloser = NULL, *prev = NULL;
147
	const knot_dname_t *dname = NULL;
148
	const knot_rdataset_t *rrs = &rr_data->rrs;
149 150

	/* Create new additional nodes. */
151
	uint16_t rdcount = rrs->rr_count;
152 153 154
	if (rr_data->additional) {
		free(rr_data->additional);
	}
155
	rr_data->additional = malloc(rdcount * sizeof(zone_node_t *));
156
	if (rr_data->additional == NULL) {
157 158 159 160 161
		return KNOT_ENOMEM;
	}

	for (uint16_t i = 0; i < rdcount; i++) {

162
		/* Try to find node for the dname in the RDATA. */
163
		dname = knot_rdata_name(rrs, i, rr_data->type);
164
		zone_contents_find_dname(zone, dname, &node, &encloser, &prev);
165
		if (node == NULL && encloser
166
		    && (encloser->flags & NODE_FLAGS_WILDCARD_CHILD)) {
167
			/* Find wildcard child in the zone. */
168
			node = zone_contents_find_wildcard_child(zone,
169 170
			                                              encloser);
			assert(node != NULL);
171 172
		}

173
		rr_data->additional[i] = (zone_node_t *)node;
174 175 176 177
	}

	return KNOT_EOK;
}
178

179 180
/*----------------------------------------------------------------------------*/

181
static int adjust_pointers(zone_node_t **tnode, void *data)
182 183
{
	assert(data != NULL);
184
	assert(tnode != NULL);
185
	zone_adjust_arg_t *args = (zone_adjust_arg_t *)data;
186
	zone_node_t *node = *tnode;
187

188
	// remember first node
189
	if (args->first_node == NULL) {
190
		args->first_node = node;
191
	}
192

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

196
	// check if this node is not a wildcard child of its parent
197 198
	if (knot_dname_is_wildcard(node->owner)) {
		assert(node->parent != NULL);
199
		node->parent->flags |= NODE_FLAGS_WILDCARD_CHILD;
Jan Kadlec's avatar
Jan Kadlec committed
200
	}
201

202
	// set flags (delegation point, non-authoritative)
203 204 205 206 207 208
	if (node->parent &&
	    ((node->parent->flags & NODE_FLAGS_DELEG) ||
	     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
209
	} else {
210 211
		// Default.
		node->flags = NODE_FLAGS_AUTH;
Jan Kadlec's avatar
Jan Kadlec committed
212 213
	}

214
	// set pointer to previous node
215
	node->prev = args->previous_node;
216

217
	// update remembered previous pointer only if authoritative
218
	if (!(node->flags & NODE_FLAGS_NONAUTH) && node->rrset_count > 0) {
219 220
		args->previous_node = node;
	}
221

222 223 224
	return KNOT_EOK;
}

225
static int adjust_nsec3_pointers(zone_node_t **tnode, void *data)
226 227 228
{
	assert(data != NULL);
	assert(tnode != NULL);
229
	zone_adjust_arg_t *args = (zone_adjust_arg_t *)data;
230
	zone_node_t *node = *tnode;
231
	// Connect to NSEC3 node (only if NSEC3 tree is not empty)
232
	zone_node_t *nsec3 = NULL;
233
	knot_dname_t *nsec3_name = NULL;
234
	int ret = zone_contents_nsec3_name(args->zone, node->owner, &nsec3_name);
235 236
	if (ret == KNOT_EOK) {
		assert(nsec3_name);
237
		zone_tree_get(args->zone->nsec3_nodes, nsec3_name, &nsec3);
238
		node->nsec3_node = nsec3;
239
	} else if (ret == KNOT_ENSEC3PAR) {
240
		node->nsec3_node = NULL;
241
		ret = KNOT_EOK;
242 243
	}

244
	knot_dname_free(&nsec3_name, NULL);
245
	return ret;
246 247
}

248 249 250 251 252 253 254 255 256 257
/*!
 * \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.
258
 * \param data   Adjusting parameters (zone_adjust_arg_t *).
259
 */
260
static int zone_contents_adjust_normal_node(zone_node_t **tnode, void *data)
261 262 263 264 265 266 267 268 269 270 271 272 273
{
	assert(data != NULL);
	assert(tnode != NULL && *tnode);
	// 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);
}

274
/*----------------------------------------------------------------------------*/
275

276
/*!
277
 * \brief Adjust NSEC3 node.
278
 *
279 280 281
 * Set:
 * - pointer to previous node
 * - pointer to node stored in owner dname
282
 *
283
 * \param tnode  Zone node to adjust.
284
 * \param data   Adjusting parameters (zone_adjust_arg_t *).
285
 */
286
static int zone_contents_adjust_nsec3_node(zone_node_t **tnode, void *data)
287 288
{
	assert(data != NULL);
289 290
	assert(tnode != NULL);

291
	zone_adjust_arg_t *args = (zone_adjust_arg_t *)data;
292
	zone_node_t *node = *tnode;
293

294
	// remember first node
295

296
	if (args->first_node == NULL) {
297
		args->first_node = node;
298
	}
299 300

	// set previous node
301

302
	node->prev = args->previous_node;
303
	args->previous_node = node;
304 305

	return KNOT_EOK;
306
}
307 308

/*! \brief Discover additional records for affected nodes. */
309
static int adjust_additional(zone_node_t **tnode, void *data)
310 311 312 313 314
{
	assert(data != NULL);
	assert(tnode != NULL);

	int ret = KNOT_EOK;
315
	zone_adjust_arg_t *args = (zone_adjust_arg_t *)data;
316
	zone_node_t *node = *tnode;
317 318 319

	/* Lookup additional records for specific nodes. */
	for(uint16_t i = 0; i < node->rrset_count; ++i) {
320
		struct rr_data *rr_data = &node->rrs[i];
321
		if (knot_rrtype_additional_needed(rr_data->type)) {
322
			ret = discover_additionals(rr_data, args->zone);
323 324 325 326 327 328 329 330 331
			if (ret != KNOT_EOK) {
				break;
			}
		}
	}

	return ret;
}

332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348
/*----------------------------------------------------------------------------*/
/*!
 * \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.
 */
349
static int zone_contents_find_in_tree(zone_tree_t *tree,
350
                                           const knot_dname_t *name,
351 352
                                           zone_node_t **node,
                                           zone_node_t **previous)
353
{
354
	assert(tree != NULL);
355 356 357 358
	assert(name != NULL);
	assert(node != NULL);
	assert(previous != NULL);

359
	zone_node_t *found = NULL, *prev = NULL;
360

361
	int exact_match = zone_tree_get_less_or_equal(tree, name, &found,
Jan Včelák's avatar
Jan Včelák committed
362
							   &prev);
363

Lubos Slovak's avatar
Lubos Slovak committed
364
	assert(exact_match >= 0);
365
	*node = found;
Lubos Slovak's avatar
Lubos Slovak committed
366
	*previous = prev;
367 368 369 370 371 372

	return exact_match;
}

/*----------------------------------------------------------------------------*/

373
static int knot_zc_nsec3_parameters_match(const knot_rdataset_t *rrs,
374 375
                                          const knot_nsec3_params_t *params,
                                          size_t rdata_pos)
376
{
377
	assert(rrs != NULL && params != NULL);
Jan Včelák's avatar
Jan Včelák committed
378

379
	dbg_zone_detail("RDATA algo: %u, iterations: %u, salt length: %u, salt:"
Jan Včelák's avatar
Jan Včelák committed
380
			" %.*s\n",
381 382 383 384 385
			knot_nsec3_algorithm(rrs, rdata_pos),
			knot_nsec3_iterations(rrs, rdata_pos),
			knot_nsec3_salt_length(rrs, rdata_pos),
			knot_nsec3_salt_length(rrs, rdata_pos),
			knot_nsec3_salt(rrs, rdata_pos));
386
	dbg_zone_detail("NSEC3PARAM algo: %u, iterations: %u, salt length: %u, "
Jan Včelák's avatar
Jan Včelák committed
387 388
			"salt: %.*s\n",  params->algorithm, params->iterations,
			params->salt_length, params->salt_length, params->salt);
389

390 391 392
	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
393 394
		&& memcmp(knot_nsec3_salt(rrs, rdata_pos), params->salt,
		          params->salt_length) == 0);
395 396
}

397
/*----------------------------------------------------------------------------*/
398
/* API functions                                                              */
399 400
/*----------------------------------------------------------------------------*/

401
zone_contents_t *zone_contents_new(const knot_dname_t *apex_name)
402
{
403 404 405 406 407
	dbg_zone("%s(%p)\n", __func__, apex_name);
	if (apex_name == NULL) {
		return NULL;
	}

408
	zone_contents_t *contents = malloc(sizeof(zone_contents_t));
409 410 411 412
	if (contents == NULL) {
		return NULL;
	}

413
	memset(contents, 0, sizeof(zone_contents_t));
414
	contents->apex = node_new(apex_name, NULL);
415 416 417
	if (contents->apex == NULL) {
		goto cleanup;
	}
418

419
	contents->nodes = zone_tree_create();
420 421 422 423
	if (contents->nodes == NULL) {
		goto cleanup;
	}

424
	if (zone_tree_insert(contents->nodes, contents->apex) != KNOT_EOK) {
425 426 427 428 429 430
		goto cleanup;
	}

	return contents;

cleanup:
431
	dbg_zone("%s: failure to initialize contents %p\n", __func__, contents);
432 433 434 435 436 437 438 439
	free(contents->nodes);
	free(contents->nsec3_nodes);
	free(contents);
	return NULL;
}

/*----------------------------------------------------------------------------*/

440
static zone_node_t *zone_contents_get_node(const zone_contents_t *zone,
441
                                           const knot_dname_t *name)
442
{
443 444
	if (zone == NULL || name == NULL) {
		return NULL;
445 446
	}

447
	zone_node_t *n;
448
	int ret = zone_tree_get(zone->nodes, name, &n);
449 450 451 452 453 454
	if (ret != KNOT_EOK) {
		dbg_zone("Failed to find name in the zone tree.\n");
		return NULL;
	}

	return n;
455 456 457 458
}

/*----------------------------------------------------------------------------*/

459 460
static int zone_contents_add_node(zone_contents_t *zone, zone_node_t *node,
                                  bool create_parents)
461 462
{
	if (zone == NULL || node == NULL) {
Marek Vavrusa's avatar
Marek Vavrusa committed
463
		return KNOT_EINVAL;
464 465 466
	}

	int ret = 0;
467
	if ((ret = zone_contents_check_node(zone, node)) != 0) {
468
		dbg_zone("Node check failed.\n");
469 470 471
		return ret;
	}

472
	ret = zone_tree_insert(zone->nodes, node);
Lubos Slovak's avatar
Lubos Slovak committed
473
	if (ret != KNOT_EOK) {
474
		dbg_zone("Failed to insert node into zone tree.\n");
475 476 477 478
		return ret;
	}

	if (!create_parents) {
Lubos Slovak's avatar
Lubos Slovak committed
479
		return KNOT_EOK;
480 481
	}

482
	dbg_zone_detail("Creating parents of the node.\n");
483

484 485
	/* No parents for root domain. */
	if (*node->owner == '\0')
Jan Kadlec's avatar
Jan Kadlec committed
486
		return KNOT_EOK;
Jan Včelák's avatar
Jan Včelák committed
487

488
	zone_node_t *next_node = NULL;
489
	const uint8_t *parent = knot_wire_next_label(node->owner, NULL);
490

491
	if (knot_dname_cmp(zone->apex->owner, parent) == 0) {
492
		dbg_zone_detail("Zone apex is the parent.\n");
493
		node_set_parent(node, zone->apex);
Lubos Slovak's avatar
Lubos Slovak committed
494 495

		// check if the node is not wildcard child of the parent
496
		if (knot_dname_is_wildcard(node->owner)) {
497
			zone->apex->flags |= NODE_FLAGS_WILDCARD_CHILD;
Lubos Slovak's avatar
Lubos Slovak committed
498
		}
499
	} else {
500
		while (parent != NULL &&
501
		       !(next_node = zone_contents_get_node(zone, parent))) {
502 503

			/* Create a new node. */
504
			dbg_zone_detail("Creating new node.\n");
505
			next_node = node_new(parent, NULL);
506
			if (next_node == NULL) {
Lubos Slovak's avatar
Lubos Slovak committed
507
				return KNOT_ENOMEM;
508 509
			}

510
			/* Insert node to a tree. */
511
			dbg_zone_detail("Inserting new node to zone tree.\n");
512
			ret = zone_tree_insert(zone->nodes, next_node);
Lubos Slovak's avatar
Lubos Slovak committed
513
			if (ret != KNOT_EOK) {
514
				node_free(&next_node, NULL);
515 516 517
				return ret;
			}

518
			/* Update node pointers. */
519
			node_set_parent(node, next_node);
520
			if (knot_dname_is_wildcard(node->owner)) {
521
				next_node->flags |= NODE_FLAGS_WILDCARD_CHILD;
522
			}
Lubos Slovak's avatar
Lubos Slovak committed
523

524
			dbg_zone_detail("Next parent.\n");
525
			node = next_node;
526
			parent = knot_wire_next_label(parent, NULL);
527
		}
528

529 530
		// set the found parent (in the zone) as the parent of the last
		// inserted node
531
		assert(node->parent == NULL);
532
		node_set_parent(node, next_node);
533

534
		dbg_zone_detail("Created all parents.\n");
535
	}
536

Lubos Slovak's avatar
Lubos Slovak committed
537
	return KNOT_EOK;
538 539 540 541
}

/*----------------------------------------------------------------------------*/

542
static int zone_contents_add_nsec3_node(zone_contents_t *zone, zone_node_t *node)
Marek Vavrusa's avatar
Marek Vavrusa committed
543
{
544
	if (zone == NULL || node == NULL) {
Marek Vavrusa's avatar
Marek Vavrusa committed
545 546 547
		return KNOT_EINVAL;
	}

548
	int ret = 0;
549
	if ((ret = zone_contents_check_node(zone, node)) != 0) {
550 551
		dbg_zone("Failed node check: %s\n", knot_strerror(ret));
		return ret;
Marek Vavrusa's avatar
Marek Vavrusa committed
552 553
	}

554 555
	/* Create NSEC3 tree if not exists. */
	if (zone->nsec3_nodes == NULL) {
556
		zone->nsec3_nodes = zone_tree_create();
557 558 559
		if (zone->nsec3_nodes == NULL) {
			return KNOT_ENOMEM;
		}
Marek Vavrusa's avatar
Marek Vavrusa committed
560 561
	}

562
	// how to know if this is successfull??
563
	ret = zone_tree_insert(zone->nsec3_nodes, node);
Marek Vavrusa's avatar
Marek Vavrusa committed
564
	if (ret != KNOT_EOK) {
565 566
		dbg_zone("Failed to insert node into NSEC3 tree: %s.\n",
			 knot_strerror(ret));
Marek Vavrusa's avatar
Marek Vavrusa committed
567 568 569
		return ret;
	}

570 571
	// no parents to be created, the only parent is the zone apex
	// set the apex as the parent of the node
572
	node_set_parent(node, zone->apex);
573 574 575 576

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

	return KNOT_EOK;
Marek Vavrusa's avatar
Marek Vavrusa committed
577 578
}

579
static zone_node_t *zone_contents_get_nsec3_node(const zone_contents_t *zone,
580
                                                 const knot_dname_t *name)
581 582 583 584
{
	if (zone == NULL || name == NULL) {
		return NULL;
	}
Marek Vavrusa's avatar
Marek Vavrusa committed
585

586
	zone_node_t *n;
587
	int ret = zone_tree_get(zone->nsec3_nodes, name, &n);
588 589 590 591 592 593 594 595
	if (ret != KNOT_EOK) {
		dbg_zone("Failed to find NSEC3 name in the zone tree."
				  "\n");
		return NULL;
	}

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

597
static int insert_rr(zone_contents_t *z,
598
                     const knot_rrset_t *rr, zone_node_t **n,
599
                     bool nsec3)
Jan Kadlec's avatar
Jan Kadlec committed
600
{
601
	if (z == NULL || knot_rrset_empty(rr) || n == NULL) {
Jan Kadlec's avatar
Jan Kadlec committed
602 603 604 605
		return KNOT_EINVAL;
	}

	// check if the RRSet belongs to the zone
606 607
	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
608 609 610 611 612
		return KNOT_EOUTOFZONE;
	}

	int ret = KNOT_EOK;
	if (*n == NULL) {
613 614
		*n = nsec3 ? zone_contents_get_nsec3_node(z, rr->owner) :
		             zone_contents_get_node(z, rr->owner);
Jan Kadlec's avatar
Jan Kadlec committed
615 616
		if (*n == NULL) {
			// Create new, insert
617
			*n = node_new(rr->owner, NULL);
Jan Kadlec's avatar
Jan Kadlec committed
618 619 620
			if (*n == NULL) {
				return KNOT_ENOMEM;
			}
621
			ret = nsec3 ? zone_contents_add_nsec3_node(z, *n) :
622
			              zone_contents_add_node(z, *n, true);
Jan Kadlec's avatar
Jan Kadlec committed
623
			if (ret != KNOT_EOK) {
624
				node_free(n, NULL);
Jan Kadlec's avatar
Jan Kadlec committed
625 626 627 628
			}
		}
	}

629
	return node_add_rrset(*n, rr, NULL);
Jan Kadlec's avatar
Jan Kadlec committed
630 631
}

632
static int recreate_normal_tree(const zone_contents_t *z, zone_contents_t *out)
633
{
634 635 636
	out->nodes = hattrie_dup(z->nodes, NULL);
	if (out->nodes == NULL) {
		return KNOT_ENOMEM;
637 638
	}

639
	// Insert APEX first.
640
	zone_node_t *apex_cpy = node_shallow_copy(z->apex, NULL);
641 642
	if (apex_cpy == NULL) {
		return KNOT_ENOMEM;
643 644
	}

645
	// Normal additions need apex ... so we need to insert directly.
646
	int ret = zone_tree_insert(out->nodes, apex_cpy);
647
	if (ret != KNOT_EOK) {
648
		node_free(&apex_cpy, NULL);
649
		return ret;
650 651
	}

652
	out->apex = apex_cpy;
653

654 655 656
	hattrie_iter_t *itt = hattrie_iter_begin(z->nodes, true);
	if (itt == NULL) {
		return KNOT_ENOMEM;
657
	}
658
	while (!hattrie_iter_finished(itt)) {
659
		const zone_node_t *to_cpy = (zone_node_t *)*hattrie_iter_val(itt);
660 661 662 663 664
		if (to_cpy == z->apex) {
			// Inserted already.
			hattrie_iter_next(itt);
			continue;
		}
665
		zone_node_t *to_add = node_shallow_copy(to_cpy, NULL);
666
		if (to_add == NULL) {
667
			hattrie_iter_free(itt);
668
			return KNOT_ENOMEM;
669
		}
670 671

		int ret = zone_contents_add_node(out, to_add, true);
672
		if (ret != KNOT_EOK) {
673
			node_free(&to_add, NULL);
674 675 676 677
			hattrie_iter_free(itt);
			return ret;
		}
		hattrie_iter_next(itt);
678 679
	}

680 681
	hattrie_iter_free(itt);
	hattrie_build_index(out->nodes);
682

683
	return KNOT_EOK;
684 685
}

686
static int recreate_nsec3_tree(const zone_contents_t *z, zone_contents_t *out)
687
{
688 689 690
	out->nsec3_nodes = hattrie_dup(z->nsec3_nodes, NULL);
	if (out->nsec3_nodes == NULL) {
		return KNOT_ENOMEM;
691 692
	}

693 694 695
	hattrie_iter_t *itt = hattrie_iter_begin(z->nsec3_nodes, false);
	if (itt == NULL) {
		return KNOT_ENOMEM;
696
	}
697
	while (!hattrie_iter_finished(itt)) {
698
		const zone_node_t *to_cpy = (zone_node_t *)*hattrie_iter_val(itt);
699
		zone_node_t *to_add = node_shallow_copy(to_cpy, NULL);
700
		if (to_add == NULL) {
701
			hattrie_iter_free(itt);
702
			return KNOT_ENOMEM;
703
		}
704
		int ret = zone_contents_add_nsec3_node(out, to_add);
705 706
		if (ret != KNOT_EOK) {
			hattrie_iter_free(itt);
707
			node_free(&to_add, NULL);
708 709 710
			return ret;
		}
		hattrie_iter_next(itt);
711
	}
712

713 714
	hattrie_iter_free(itt);
	hattrie_build_index(out->nsec3_nodes);
715

Lubos Slovak's avatar
Lubos Slovak committed
716
	return KNOT_EOK;
717 718
}

719 720 721 722 723 724 725 726 727
static bool rrset_is_nsec3rel(const knot_rrset_t *rr)
{
	if (rr == NULL) {
		return false;
	}

	/* Is NSEC3 or non-empty RRSIG covering NSEC3. */
	return ((rr->type == KNOT_RRTYPE_NSEC3)
	        || (rr->type == KNOT_RRTYPE_RRSIG
728
	            && knot_rrsig_type_covered(&rr->rrs, 0)
729 730 731
	            == KNOT_RRTYPE_NSEC3));
}

732 733
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
734
{
735 736 737 738
	if (z == NULL || rr == NULL) {
		return KNOT_EINVAL;
	}

739
	return insert_rr(z, rr, n, rrset_is_nsec3rel(rr));
740 741 742 743
}

/*----------------------------------------------------------------------------*/

744
int zone_contents_remove_node(zone_contents_t *contents, const knot_dname_t *owner)
745
{
746
	if (contents == NULL || owner == NULL) {
Marek Vavrusa's avatar
Marek Vavrusa committed
747
		return KNOT_EINVAL;
748
	}
749

750
dbg_zone_exec_verb(
751
	char *name = knot_dname_to_str_alloc(owner);
752
	dbg_zone_verb("Removing zone node: %s\n", name);
Lubos Slovak's avatar
Lubos Slovak committed
753
	free(name);
754
);
755
	zone_node_t *removed_node = NULL;
756
	int ret = zone_tree_remove(contents->nodes, owner, &removed_node);
Lubos Slovak's avatar
Lubos Slovak committed
757
	if (ret != KNOT_EOK) {
758
		return KNOT_ENONODE;
759
	}
Jan Kadlec's avatar
Jan Kadlec committed
760
	assert(removed_node);
761

762
	return KNOT_EOK;
763 764 765 766
}

/*----------------------------------------------------------------------------*/

767
int zone_contents_remove_nsec3_node(zone_contents_t *contents, const knot_dname_t *owner)
768
{
769
	if (contents == NULL || owner == NULL) {
Marek Vavrusa's avatar
Marek Vavrusa committed
770
		return KNOT_EINVAL;
771
	}
772

773
	// remove the node from the zone tree
774
	zone_node_t *removed_node = NULL;
775
	int ret = zone_tree_remove(contents->nsec3_nodes, owner,
776
	                                &removed_node);
Lubos Slovak's avatar
Lubos Slovak committed
777
	if (ret != KNOT_EOK) {
778
		return KNOT_ENONODE;
779
	}
Jan Kadlec's avatar
Jan Kadlec committed
780
	assert(removed_node);
Jan Včelák's avatar
Jan Včelák committed
781

782
	return KNOT_EOK;
783 784 785 786
}

/*----------------------------------------------------------------------------*/

787
const zone_node_t *zone_contents_find_node(const zone_contents_t *zone,
788
                                           const knot_dname_t *name)
789
{
790
	return zone_contents_get_node(zone, name);
791 792 793 794
}

/*----------------------------------------------------------------------------*/

795
int zone_contents_find_dname(const zone_contents_t *zone,
796 797 798 799
                             const knot_dname_t *name,
                             const zone_node_t **node,
                             const zone_node_t **closest_encloser,
                             const zone_node_t **previous)
800 801 802 803
{
	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
804
		return KNOT_EINVAL;
805 806
	}

807
dbg_zone_exec_verb(
808 809
	char *name_str = knot_dname_to_str_alloc(name);
	char *zone_str = knot_dname_to_str_alloc(zone->apex->owner);
810
	dbg_zone_verb("Searching for name %s in zone %s...\n",
Jan Včelák's avatar
Jan Včelák committed
811
		      name_str, zone_str);
812 813 814 815
	free(name_str);
	free(zone_str);
);

816
	zone_node_t *found = NULL, *prev = NULL;
817

818
	int exact_match = zone_contents_find_in_tree(zone->nodes, name,
Jan Včelák's avatar
Jan Včelák committed
819
							    &found, &prev);
Lubos Slovak's avatar
Lubos Slovak committed
820
	assert(exact_match >= 0);
821 822
	*node = found;
	*previous = prev;
823

824
dbg_zone_exec_detail(
825
	char *name_str = (*node) ? knot_dname_to_str_alloc((*node)->owner)
Jan Včelák's avatar
Jan Včelák committed
826
				 : "(nil)";
827
	char *name_str2 = (*previous != NULL)
828
			  ? knot_dname_to_str_alloc((*previous)->owner)
Jan Včelák's avatar
Jan Včelák committed
829
			  : "(nil)";
830
dbg_zone_detail("Search function returned %d, node %s (%p) and prev: %s (%p)\n",
Jan Včelák's avatar
Jan Včelák committed
831
			exact_match, name_str, *node, name_str2, *previous);
832 833 834 835 836 837 838 839 840 841

	if (*node) {
		free(name_str);
	}
	if (*previous != NULL) {
		free(name_str2);
	}
);
	// 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
842
	if (*node == NULL && *previous == NULL) {
843
		return KNOT_EOUTOFZONE;
844 845
	}

Lubos Slovak's avatar
Lubos Slovak committed
846 847 848 849 850 851 852 853
	/* 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 {
854 855 856 857 858 859
		if (!knot_dname_is_sub(name, zone->apex->owner)) {
			*node = NULL;
			*closest_encloser = NULL;
			return KNOT_EOUTOFZONE;
		}

Lubos Slovak's avatar
Lubos Slovak committed
860
		*closest_encloser = *previous;
Jan Kadlec's avatar
Jan Kadlec committed
861 862
		assert(*closest_encloser != NULL);

863 864 865
		int matched_labels = knot_dname_matched_labels((*closest_encloser)->owner,
							       name);
		while (matched_labels < knot_dname_labels((*closest_encloser)->owner, NULL)) {
Jan Kadlec's avatar
Jan Kadlec committed
866
			(*closest_encloser) =
867
				(*closest_encloser)->parent;
Jan Kadlec's avatar
Jan Kadlec committed
868 869
			assert(*closest_encloser);
		}
870 871
	}

872
	dbg_zone_verb("find_dname() returning %d\n", exact_match);
873 874

	return (exact_match)
875 876
	       ? ZONE_NAME_FOUND
	       : ZONE_NAME_NOT_FOUND;
877 878 879 880
}

/*----------------------------------------------------------------------------*/

881 882
zone_node_t *zone_contents_get_previous(const zone_contents_t *zone,
                                        const knot_dname_t *name)
883 884 885 886 887
{
	if (zone == NULL || name == NULL) {
		return NULL;
	}

888
	zone_node_t *found = NULL, *prev = NULL;
889

890
	int exact_match = zone_contents_find_in_tree(zone->nodes, name,
Jan Včelák's avatar
Jan Včelák committed
891
							    &found, &prev);
Lubos Slovak's avatar
Lubos Slovak committed
892
	assert(exact_match >= 0);
893 894 895 896 897 898 899
	assert(prev != NULL);

	return prev;
}

/*----------------------------------------------------------------------------*/

900 901
const zone_node_t *zone_contents_find_previous(const zone_contents_t *zone,
                                               const knot_dname_t *name)
902
{
903
	return zone_contents_get_previous(zone, name);
904 905 906
}

/*----------------------------------------------------------------------------*/
907 908

const zone_node_t *zone_contents_find_nsec3_node(const zone_contents_t *zone,
909
                                                 const knot_dname_t *name)
910
{
911
	return zone_contents_get_nsec3_node(zone, name);
912 913 914 915
}

/*----------------------------------------------------------------------------*/

916
int zone_contents_find_nsec3_for_name(const zone_contents_t *zone,
917 918 919
                                      const knot_dname_t *name,
                                      const zone_node_t **nsec3_node,
                                      const zone_node_t **nsec3_previous)
920 921 922
{
	if (zone == NULL || name == NULL
	    || nsec3_node == NULL || nsec3_previous == NULL) {
Marek Vavrusa's avatar
Marek Vavrusa committed
923
		return KNOT_EINVAL;
924 925
	}

926
	// check if the NSEC3 tree is not empty
927
	if (zone_tree_is_empty(zone->nsec3_nodes)) {
928 929 930 931
		dbg_zone("NSEC3 tree is empty.\n");
		return KNOT_ENSEC3CHAIN;
	}

932
	knot_dname_t *nsec3_name = NULL;
933
	int ret = zone_contents_nsec3_name(zone, name, &nsec3_name);
934

Lubos Slovak's avatar
Lubos Slovak committed
935
	if (ret != KNOT_EOK) {
936 937 938
		return ret;
	}

939
dbg_zone_exec_verb(
940
	char *n = knot_dname_to_str_alloc(nsec3_name);
941
	dbg_zone_verb("NSEC3 node name: %s.\n", n);
942 943 944
	free(n);
);

945
	const zone_node_t *found = NULL, *prev = NULL;
946 947

	// create dummy node to use for lookup
948
	int exact_match = zone_tree_find_less_or_equal(
949
		zone->nsec3_nodes, nsec3_name, &found, &prev);
Lubos Slovak's avatar
Lubos Slovak committed
950
	assert(exact_match >= 0);
Lubos Slovak's avatar
Lubos Slovak committed
951

952
	knot_dname_free(&nsec3_name, NULL);
953

954
dbg_zone_exec_detail(
955
	if (found) {
956
		char *n = knot_dname_to_str_alloc(found->owner);
957
		dbg_zone_detail("Found NSEC3 node: %s.\n", n);
958 959
		free(n);
	} else {
960
		dbg_zone_detail("Found no NSEC3 node.\n");
961 962 963 964
	}

	if (prev) {
		assert(prev->owner);
965
		char *n = knot_dname_to_str_alloc(prev->owner);
966
		dbg_zone_detail("Found previous NSEC3 node: %s.\n", n);
967 968
		free(n);
	} else {
969
		dbg_zone_detail("Found no previous NSEC3 node.\n");
970 971 972 973 974 975 976 977 978 979
	}
);
	*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
		assert(exact_match);
		assert(*nsec3_node != NULL);
980
		*nsec3_previous = (*nsec3_node)->prev;
981 982 983 984
	} else {
		*nsec3_previous = prev;
	}

985
	dbg_zone_verb("find_nsec3_for_name() returning %d\n", exact_match);
Jan Včelák's avatar
Jan Včelák committed
986 987 988

	/* The previous may be from wrong NSEC3 chain. Search for previous
	 * from the right chain. Check iterations, hash algorithm and salt
989 990
	 * values and compare them to the ones from NSEC3PARAM.
	 */
991
	const knot_rdataset_t *nsec3_rrs =
992 993
		node_rdataset(*nsec3_previous, KNOT_RRTYPE_NSEC3);
	const zone_node_t *original_prev = *nsec3_previous;
Jan Včelák's avatar
Jan Včelák committed
994

995
	int match = 0;
Jan Včelák's avatar
Jan Včelák committed
996

997
	while (nsec3_rrs && !match) {
998
		for (uint16_t i = 0;
999
		     i < nsec3_rrs->rr_count && !match;
1000
		     i++) {
1001 1002 1003
			if (knot_zc_nsec3_parameters_match(nsec3_rrs,
			                                   &zone->nsec3_params,
			                                   i)) {
1004 1005
				/* Matching NSEC3PARAM match at position nr.: i. */
				match = 1;
1006
			}
1007
		}
Jan Včelák's avatar
Jan Včelák committed
1008

1009 1010 1011
		if (match) {
			break;
		}
Jan Včelák's avatar
Jan Včelák committed
1012

1013
		/* This RRSET was not a match, try the one from previous node. */
1014
		*nsec3_previous = (*nsec3_previous)->prev;
1015
		nsec3_rrs = node_rdataset(*nsec3_previous, KNOT_RRTYPE_NSEC3);
1016
		if (*nsec3_previous == original_prev || nsec3_rrs == NULL) {
1017 1018 1019 1020
			// cycle
			*nsec3_previous = NULL;
			break;
		}
1021
	}
Jan Včelák's avatar
Jan Včelák committed
1022

1023
	return (exact_match)
1024 1025
	       ? ZONE_NAME_FOUND
	       : ZONE_NAME_NOT_FOUND;
1026 1027 1028 1029
}

/*----------------------------------------------------------------------------*/

1030 1031
const zone_node_t *zone_contents_find_wildcard_child(const zone_contents_t *contents,
                                                     const zone_node_t *parent)
1032
{
1033
	if (contents == NULL || parent == NULL || parent->owner == NULL) {
1034 1035 1036
		return NULL;
	}

1037 1038
	knot_dname_t wildcard[KNOT_DNAME_MAXLEN] = { 0x01, '*' };
	knot_dname_to_wire(wildcard + 2, parent->owner, KNOT_DNAME_MAXLEN - 2);
1039
	return zone_contents_find_node(contents, wildcard);
1040 1041 1042 1043
}

/*----------------------------------------------------------------------------*/

1044
static int zone_contents_adjust_nodes(zone_tree_t *nodes,
1045
                                      zone_adjust_arg_t *adjust_arg,
1046
                                      zone_tree_apply_cb_t callback)
1047
{
1048
	if (zone_tree_is_empty(nodes)) {
1049