changesets.c 9.76 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 <stdlib.h>
#include <assert.h>
19
#include <stdarg.h>
20

21
#include "knot/updates/changesets.h"
22
#include "libknot/rrset.h"
23
#include "libknot/internal/macros.h"
24

25 26 27
/* -------------------- Changeset iterator helpers -------------------------- */

/*! \brief Adds RRSet to given zone. */
28
static int add_rr_to_zone(zone_contents_t *z, knot_rrset_t **soa, const knot_rrset_t *rrset)
29
{
30 31 32 33 34 35 36 37 38 39 40
	if (rrset->type == KNOT_RRTYPE_SOA) {
		if (*soa == NULL) {
			*soa = knot_rrset_copy(rrset, NULL);
			if (*soa == NULL) {
				return KNOT_ENOMEM;
			}
		}
		// Do not add SOAs into actual contents.
		return KNOT_EOK;
	}

41 42
	zone_node_t *n = NULL;
	int ret = zone_contents_add_rr(z, rrset, &n);
43
	UNUSED(n);
44
	return ret;
45 46
}

47
/*! \brief Cleans up trie iterations. */
48
static void cleanup_iter_list(list_t *l)
49
{
50 51 52 53 54 55 56 57 58 59
	ptrnode_t *n, *nxt;
	WALK_LIST_DELSAFE(n, nxt, *l) {
		hattrie_iter_t *it = (hattrie_iter_t *)n->d;
		hattrie_iter_free(it);
		rem_node(&n->n);
		free(n);
	}
	init_list(l);
}

60
/*! \brief Inits changeset iterator with given HAT-tries. */
61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
static int changeset_iter_init(changeset_iter_t *ch_it,
                               const changeset_t *ch, bool sorted, size_t tries, ...)
{
	memset(ch_it, 0, sizeof(*ch_it));
	init_list(&ch_it->iters);

	va_list args;
	va_start(args, tries);

	for (size_t i = 0; i < tries; ++i) {
		hattrie_t *t = va_arg(args, hattrie_t *);
		if (t) {
			if (sorted) {
				hattrie_build_index(t);
			}
			hattrie_iter_t *it = hattrie_iter_begin(t, sorted);
			if (it == NULL) {
				cleanup_iter_list(&ch_it->iters);
				return KNOT_ENOMEM;
			}
			if (ptrlist_add(&ch_it->iters, it, NULL) == NULL) {
				cleanup_iter_list(&ch_it->iters);
				return KNOT_ENOMEM;
			}
		}
	}

	va_end(args);

	return KNOT_EOK;
}

93
/*! \brief Gets next node from trie iterators. */
94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
static void iter_next_node(changeset_iter_t *ch_it, hattrie_iter_t *t_it)
{
	assert(!hattrie_iter_finished(t_it));
	// Get next node, but not for the very first call.
	if (ch_it->node) {
		hattrie_iter_next(t_it);
	}
	if (hattrie_iter_finished(t_it)) {
		ch_it->node = NULL;
		return;
	}

	ch_it->node = (zone_node_t *)*hattrie_iter_val(t_it);
	assert(ch_it->node);
	while (ch_it->node && ch_it->node->rrset_count == 0) {
		// Skip empty non-terminals.
		hattrie_iter_next(t_it);
		if (hattrie_iter_finished(t_it)) {
			ch_it->node = NULL;
		} else {
			ch_it->node = (zone_node_t *)*hattrie_iter_val(t_it);
			assert(ch_it->node);
		}
	}
118

119 120 121
	ch_it->node_pos = 0;
}

122
/*! \brief Gets next RRSet from trie iterators. */
123 124 125 126 127 128 129 130 131 132 133 134 135 136 137
static knot_rrset_t get_next_rr(changeset_iter_t *ch_it, hattrie_iter_t *t_it) // pun intented
{
	if (ch_it->node == NULL || ch_it->node_pos == ch_it->node->rrset_count) {
		iter_next_node(ch_it, t_it);
		if (ch_it->node == NULL) {
			assert(hattrie_iter_finished(t_it));
			knot_rrset_t rr;
			knot_rrset_init_empty(&rr);
			return rr;
		}
	}

	return node_rrset_at(ch_it->node, ch_it->node_pos++);
}

138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180
static bool intersection_exists(const knot_rrset_t *node_rr, const knot_rrset_t *inc_rr)
{
	knot_rdataset_t intersection;
	knot_rdataset_init(&intersection);
	int ret = knot_rdataset_intersect(&node_rr->rrs, &inc_rr->rrs, &intersection, NULL);
	if (ret != KNOT_EOK) {
		return false;
	}
	const uint16_t rr_count = intersection.rr_count;
	knot_rdataset_clear(&intersection, NULL);

	return rr_count > 0;
}

static bool need_to_insert(zone_contents_t *counterpart, const knot_rrset_t *rr)
{
	zone_node_t *node = zone_contents_find_node_for_rr(counterpart, rr);
	if (node == NULL) {
		return true;
	}

	if (!node_rrtype_exists(node, rr->type)) {
		return true;
	}

	knot_rrset_t node_rr = node_rrset(node, rr->type);
	if (!intersection_exists(&node_rr, rr)) {
		return true;
	}

	// Subtract the data from node's RRSet.
	int ret = knot_rdataset_subtract(&node->rrs->rrs, &rr->rrs, NULL);
	if (ret != KNOT_EOK) {
		return true;
	}

	if (knot_rrset_empty(&node_rr)) {
		// Remove empty type.
		node_remove_rdataset(node, rr->type);
	}

	if (node->rrset_count == 0) {
		// Remove empty node.
181 182
		zone_tree_t *t = knot_rrset_is_nsec3rel(rr) ?
		                     counterpart->nsec3_nodes : counterpart->nodes;
183 184 185 186 187 188
		zone_contents_delete_empty_node(counterpart, t, node);
	}

	return false;
}

189 190
/* ------------------------------- API -------------------------------------- */

191 192 193
int changeset_init(changeset_t *ch, const knot_dname_t *apex)
{
	memset(ch, 0, sizeof(changeset_t));
194

195 196
	// Init local changes
	ch->add = zone_contents_new(apex);
197 198 199
	if (ch->add == NULL) {
		return KNOT_ENOMEM;
	}
200
	ch->remove = zone_contents_new(apex);
201 202 203 204
	if (ch->remove == NULL) {
		zone_contents_free(&ch->add);
		return KNOT_ENOMEM;
	}
Jan Kadlec's avatar
Jan Kadlec committed
205

206
	return KNOT_EOK;
207 208
}

209
changeset_t *changeset_new(const knot_dname_t *apex)
210
{
211
	changeset_t *ret = malloc(sizeof(changeset_t));
212
	if (ret == NULL) {
213 214 215
		return NULL;
	}

216 217 218 219 220 221
	if (changeset_init(ret, apex) == KNOT_EOK) {
		return ret;
	} else {
		free(ret);
		return NULL;
	}
222 223
}

224
bool changeset_empty(const changeset_t *ch)
225
{
226
	if (ch == NULL || ch->add == NULL || ch->remove == NULL) {
227
		return true;
228 229
	}

230 231 232
	if (ch->soa_to) {
		return false;
	}
233

234 235
	changeset_iter_t itt;
	changeset_iter_all(&itt, ch, false);
236

237 238
	knot_rrset_t rr = changeset_iter_next(&itt);
	changeset_iter_clear(&itt);
239 240

	return knot_rrset_empty(&rr);
241 242
}

243
size_t changeset_size(const changeset_t *ch)
244
{
245
	if (ch == NULL) {
246 247
		return 0;
	}
248

249 250
	changeset_iter_t itt;
	changeset_iter_all(&itt, ch, false);
251 252

	size_t size = 0;
253
	knot_rrset_t rr = changeset_iter_next(&itt);
254 255
	while(!knot_rrset_empty(&rr)) {
		++size;
256
		rr = changeset_iter_next(&itt);
257
	}
258
	changeset_iter_clear(&itt);
259

Jan Kadlec's avatar
Jan Kadlec committed
260 261 262 263 264 265 266
	if (!knot_rrset_empty(ch->soa_from)) {
		size += 1;
	}
	if (!knot_rrset_empty(ch->soa_to)) {
		size += 1;
	}

267
	return size;
268 269
}

270
int changeset_add_rrset(changeset_t *ch, const knot_rrset_t *rrset, bool check_redundancy)
271
{
272 273
	/* Check if there's any removal and remove that, then add this
	 * addition anyway. Required to change TTLs. */
274 275 276
	if(check_redundancy) {
		need_to_insert(ch->remove, rrset);
	}
277 278

	return add_rr_to_zone(ch->add, &ch->soa_to, rrset);
279 280
}

281
int changeset_rem_rrset(changeset_t *ch, const knot_rrset_t *rrset, bool check_redundancy)
282
{
283
	if ((check_redundancy && need_to_insert(ch->add, rrset)) || !check_redundancy) {
284 285 286 287
		return add_rr_to_zone(ch->remove, &ch->soa_from, rrset);
	} else {
		return KNOT_EOK;
	}
288 289 290
}

int changeset_merge(changeset_t *ch1, const changeset_t *ch2)
291
{
292 293
	changeset_iter_t itt;
	changeset_iter_add(&itt, ch2, false);
294

295
	knot_rrset_t rrset = changeset_iter_next(&itt);
296
	while (!knot_rrset_empty(&rrset)) {
297
		int ret = changeset_add_rrset(ch1, &rrset, true);
298
		if (ret != KNOT_EOK) {
299 300
			changeset_iter_clear(&itt);
			return ret;
301
		}
302
		rrset = changeset_iter_next(&itt);
303
	}
304
	changeset_iter_clear(&itt);
305

Jan Kadlec's avatar
Jan Kadlec committed
306
	changeset_iter_rem(&itt, ch2, false);
307

308
	rrset = changeset_iter_next(&itt);
309
	while (!knot_rrset_empty(&rrset)) {
310
		int ret = changeset_rem_rrset(ch1, &rrset, true);
311
		if (ret != KNOT_EOK) {
312 313
			changeset_iter_clear(&itt);
			return ret;
314
		}
315
		rrset = changeset_iter_next(&itt);
316
	}
317
	changeset_iter_clear(&itt);
318

319 320
	// Use soa_to and serial from the second changeset
	// soa_to from the first changeset is redundant, delete it
321
	knot_rrset_t *soa_copy = knot_rrset_copy(ch2->soa_to, NULL);
Jan Kadlec's avatar
Jan Kadlec committed
322
	if (soa_copy == NULL && ch2->soa_to) {
323 324
		return KNOT_ENOMEM;
	}
325
	knot_rrset_free(&ch1->soa_to, NULL);
326
	ch1->soa_to = soa_copy;
327 328

	return KNOT_EOK;
329 330
}

331 332 333 334 335 336 337 338 339 340 341 342 343
void changesets_clear(list_t *chgs)
{
	if (chgs) {
		changeset_t *chg, *nxt;
		WALK_LIST_DELSAFE(chg, nxt, *chgs) {
			changeset_clear(chg);
			rem_node(&chg->n);
		}
		init_list(chgs);
	}
}

void changesets_free(list_t *chgs)
344
{
345
	if (chgs) {
346 347
		changeset_t *chg, *nxt;
		WALK_LIST_DELSAFE(chg, nxt, *chgs) {
348
			rem_node(&chg->n);
349
			changeset_free(chg);
350
		}
351
		init_list(chgs);
352
	}
353 354
}

355
void changeset_clear(changeset_t *ch)
356
{
357 358
	if (ch == NULL) {
		return;
359
	}
360

361 362 363
	// Delete RRSets in lists, in case there are any left
	zone_contents_deep_free(&ch->add);
	zone_contents_deep_free(&ch->remove);
364

365 366
	knot_rrset_free(&ch->soa_from, NULL);
	knot_rrset_free(&ch->soa_to, NULL);
367

368 369 370
	// Delete binary data
	free(ch->data);
}
371

372 373 374 375
void changeset_free(changeset_t *ch)
{
	changeset_clear(ch);
	free(ch);
376 377
}

378
int changeset_iter_add(changeset_iter_t *itt, const changeset_t *ch, bool sorted)
379
{
380 381
	return changeset_iter_init(itt, ch, sorted, 2,
	                           ch->add->nodes, ch->add->nsec3_nodes);
382 383
}

384
int changeset_iter_rem(changeset_iter_t *itt, const changeset_t *ch, bool sorted)
385
{
386 387
	return changeset_iter_init(itt, ch, sorted, 2,
	                           ch->remove->nodes, ch->remove->nsec3_nodes);
388 389
}

390
int changeset_iter_all(changeset_iter_t *itt, const changeset_t *ch, bool sorted)
391
{
392 393 394
	return changeset_iter_init(itt, ch, sorted, 4,
	                           ch->add->nodes, ch->add->nsec3_nodes,
	                           ch->remove->nodes, ch->remove->nsec3_nodes);
395 396
}

397 398
knot_rrset_t changeset_iter_next(changeset_iter_t *it)
{
399
	assert(it);
400 401 402 403 404 405 406 407 408 409 410 411 412 413
	ptrnode_t *n = NULL;
	knot_rrset_t rr;
	knot_rrset_init_empty(&rr);
	WALK_LIST(n, it->iters) {
		hattrie_iter_t *t_it = (hattrie_iter_t *)n->d;
		if (hattrie_iter_finished(t_it)) {
			continue;
		}

		rr = get_next_rr(it, t_it);
		if (!knot_rrset_empty(&rr)) {
			// Got valid RRSet.
			return rr;
		}
414 415
	}

416
	return rr;
417 418
}

419
void changeset_iter_clear(changeset_iter_t *it)
420
{
421
	if (it) {
422
		cleanup_iter_list(&it->iters);
423 424
		it->node = NULL;
		it->node_pos = 0;
425
	}
426
}