rdataslab.c 24.9 KB
Newer Older
1
/*
Automatic Updater's avatar
Automatic Updater committed
2
 * Copyright (C) 2004-2011  Internet Systems Consortium, Inc. ("ISC")
Mark Andrews's avatar
Mark Andrews committed
3
 * Copyright (C) 1999-2003  Internet Software Consortium.
4
 *
Automatic Updater's avatar
Automatic Updater committed
5
 * Permission to use, copy, modify, and/or distribute this software for any
6 7
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
8
 *
Mark Andrews's avatar
Mark Andrews committed
9 10 11 12 13 14 15
 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
16 17
 */

Mark Andrews's avatar
Mark Andrews committed
18
/* $Id$ */
19 20

/*! \file */
21 22 23

#include <config.h>

24 25
#include <stdlib.h>

26
#include <isc/mem.h>
27
#include <isc/region.h>
28
#include <isc/string.h>		/* Required for HP/UX (and others?) */
Bob Halley's avatar
Bob Halley committed
29
#include <isc/util.h>
30 31 32 33 34 35

#include <dns/result.h>
#include <dns/rdata.h>
#include <dns/rdataset.h>
#include <dns/rdataslab.h>

36 37 38 39 40 41 42 43 44 45
/*
 * The rdataslab structure allows iteration to occur in both load order
 * and DNSSEC order.  The structure is as follows:
 *
 *	header		(reservelen bytes)
 *	record count	(2 bytes)
 *	offset table	(4 x record count bytes in load order)
 *	data records
 *		data length	(2 bytes)
 *		order		(2 bytes)
46
 *		meta data	(1 byte for RRSIG's)
47 48
 *		data		(data length bytes)
 *
49 50 51 52 53 54 55
 * If DNS_RDATASET_FIXED is defined to be zero (0) the format of a
 * rdataslab is as follows:
 *
 *	header		(reservelen bytes)
 *	record count	(2 bytes)
 *	data records
 *		data length	(2 bytes)
56
 *		meta data	(1 byte for RRSIG's)
57 58
 *		data		(data length bytes)
 *
59 60 61
 * Offsets are from the end of the header.
 *
 * Load order traversal is performed by walking the offset table to find
62
 * the start of the record (DNS_RDATASET_FIXED = 1).
63 64 65
 *
 * DNSSEC order traversal is performed by walking the data records.
 *
Francis Dupont's avatar
Francis Dupont committed
66
 * The order is stored with record to allow for efficient reconstruction
67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
 * of the offset table following a merge or subtraction.
 *
 * The iterator methods here currently only support DNSSEC order iteration.
 *
 * The iterator methods in rbtdb support both load order and DNSSEC order
 * iteration.
 *
 * WARNING:
 *	rbtdb.c directly interacts with the slab's raw structures.  If the
 *	structure changes then rbtdb.c also needs to be updated to reflect
 *	the changes.  See the areas tagged with "RDATASLAB".
 */

struct xrdata {
	dns_rdata_t	rdata;
	unsigned int	order;
};

85
/*% Note: the "const void *" are just to make qsort happy.  */
86 87
static int
compare_rdata(const void *p1, const void *p2) {
88 89 90 91 92
	const struct xrdata *x1 = p1;
	const struct xrdata *x2 = p2;
	return (dns_rdata_compare(&x1->rdata, &x2->rdata));
}

93
#if DNS_RDATASET_FIXED
94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121
static void
fillin_offsets(unsigned char *offsetbase, unsigned int *offsettable,
	       unsigned length)
{
	unsigned int i, j;
	unsigned char *raw;

	for (i = 0, j = 0; i < length; i++) {

		if (offsettable[i] == 0)
			continue;

		/*
		 * Fill in offset table.
		 */
		raw = &offsetbase[j*4 + 2];
		*raw++ = (offsettable[i] & 0xff000000) >> 24;
		*raw++ = (offsettable[i] & 0xff0000) >> 16;
		*raw++ = (offsettable[i] & 0xff00) >> 8;
		*raw = offsettable[i] & 0xff;

		/*
		 * Fill in table index.
		 */
		raw = offsetbase + offsettable[i] + 2;
		*raw++ = (j & 0xff00) >> 8;
		*raw = j++ & 0xff;
	}
122
}
123
#endif
124

125
isc_result_t
126 127 128
dns_rdataslab_fromrdataset(dns_rdataset_t *rdataset, isc_mem_t *mctx,
			   isc_region_t *region, unsigned int reservelen)
{
129
	struct xrdata  *x;
130
	unsigned char  *rawbuf;
131
#if DNS_RDATASET_FIXED
132
	unsigned char  *offsetbase;
133
#endif
134
	unsigned int	buflen;
135
	isc_result_t	result;
136
	unsigned int	nitems;
137 138
	unsigned int	nalloc;
	unsigned int	i;
139
#if DNS_RDATASET_FIXED
140
	unsigned int   *offsettable;
141
#endif
142
	unsigned int	length;
143 144

	buflen = reservelen + 2;
145 146 147

	nalloc = dns_rdataset_count(rdataset);
	nitems = nalloc;
148
	if (nitems == 0 && rdataset->type != 0)
149
		return (ISC_R_FAILURE);
150

151 152 153
	if (nalloc > 0xffff)
		return (ISC_R_NOSPACE);

Automatic Updater's avatar
Automatic Updater committed
154

155 156 157 158 159 160
	if (nalloc != 0) {
		x = isc_mem_get(mctx, nalloc * sizeof(struct xrdata));
		if (x == NULL)
			return (ISC_R_NOMEMORY);
	} else
		x = NULL;
161 162 163 164

	/*
	 * Save all of the rdata members into an array.
	 */
165
	result = dns_rdataset_first(rdataset);
166
	if (result != ISC_R_SUCCESS && result != ISC_R_NOMORE)
167 168
		goto free_rdatas;
	for (i = 0; i < nalloc && result == ISC_R_SUCCESS; i++) {
169
		INSIST(result == ISC_R_SUCCESS);
170 171
		dns_rdata_init(&x[i].rdata);
		dns_rdataset_current(rdataset, &x[i].rdata);
172
#if DNS_RDATASET_FIXED
173
		x[i].order = i;
174
#endif
175 176
		result = dns_rdataset_next(rdataset);
	}
177 178 179 180 181 182 183 184 185 186
	if (result != ISC_R_NOMORE)
		goto free_rdatas;
	if (i != nalloc) {
		/*
		 * Somehow we iterated over fewer rdatas than
		 * dns_rdataset_count() said there were!
		 */
		result = ISC_R_FAILURE;
		goto free_rdatas;
	}
187

188 189 190 191
	/*
	 * Put into DNSSEC order.
	 */
	qsort(x, nalloc, sizeof(struct xrdata), compare_rdata);
192 193

	/*
194 195 196 197 198
	 * Remove duplicates and compute the total storage required.
	 *
	 * If an rdata is not a duplicate, accumulate the storage size
	 * required for the rdata.  We do not store the class, type, etc,
	 * just the rdata, so our overhead is 2 bytes for the number of
199 200
	 * records, and 8 for each rdata, (length(2), offset(4) and order(2))
	 * and then the rdata itself.
201 202
	 */
	for (i = 1; i < nalloc; i++) {
203 204 205
		if (compare_rdata(&x[i-1].rdata, &x[i].rdata) == 0) {
			x[i-1].rdata.data = NULL;
			x[i-1].rdata.length = 0;
206
#if DNS_RDATASET_FIXED
207 208 209 210 211 212
			/*
			 * Preserve the least order so A, B, A -> A, B
			 * after duplicate removal.
			 */
			if (x[i-1].order < x[i].order)
				x[i].order = x[i-1].order;
213
#endif
214
			nitems--;
215
		} else {
216
#if DNS_RDATASET_FIXED
217
			buflen += (8 + x[i-1].rdata.length);
218 219 220
#else
			buflen += (2 + x[i-1].rdata.length);
#endif
221 222 223 224 225 226
			/*
			 * Provide space to store the per RR meta data.
			 */
			if (rdataset->type == dns_rdatatype_rrsig)
				buflen++;
		}
227
	}
228
	/*
229
	 * Don't forget the last item!
230
	 */
231
	if (nalloc != 0) {
232
#if DNS_RDATASET_FIXED
233
		buflen += (8 + x[i-1].rdata.length);
234
#else
235
		buflen += (2 + x[i-1].rdata.length);
236
#endif
237 238
	}

239 240 241 242 243
	/*
	 * Provide space to store the per RR meta data.
	 */
	if (rdataset->type == dns_rdatatype_rrsig)
		buflen++;
244

245
	/*
246
	 * Ensure that singleton types are actually singletons.
247 248 249 250 251 252 253 254
	 */
	if (nitems > 1 && dns_rdatatype_issingleton(rdataset->type)) {
		/*
		 * We have a singleton type, but there's more than one
		 * RR in the rdataset.
		 */
		result = DNS_R_SINGLETON;
		goto free_rdatas;
255
	}
256 257 258 259 260 261

	/*
	 * Allocate the memory, set up a buffer, start copying in
	 * data.
	 */
	rawbuf = isc_mem_get(mctx, buflen);
262
	if (rawbuf == NULL) {
263 264
		result = ISC_R_NOMEMORY;
		goto free_rdatas;
265
	}
Automatic Updater's avatar
Automatic Updater committed
266

267
#if DNS_RDATASET_FIXED
268 269 270 271 272 273 274 275
	/* Allocate temporary offset table. */
	offsettable = isc_mem_get(mctx, nalloc * sizeof(unsigned int));
	if (offsettable == NULL) {
		isc_mem_put(mctx, rawbuf, buflen);
		result = ISC_R_NOMEMORY;
		goto free_rdatas;
	}
	memset(offsettable, 0, nalloc * sizeof(unsigned int));
276
#endif
277 278 279 280 281

	region->base = rawbuf;
	region->length = buflen;

	rawbuf += reservelen;
282
#if DNS_RDATASET_FIXED
283
	offsetbase = rawbuf;
284
#endif
285 286 287

	*rawbuf++ = (nitems & 0xff00) >> 8;
	*rawbuf++ = (nitems & 0x00ff);
288

289
#if DNS_RDATASET_FIXED
290 291
	/* Skip load order table.  Filled in later. */
	rawbuf += nitems * 4;
292
#endif
293

294
	for (i = 0; i < nalloc; i++) {
295
		if (x[i].rdata.data == NULL)
296
			continue;
297
#if DNS_RDATASET_FIXED
298
		offsettable[x[i].order] = rawbuf - offsetbase;
299
#endif
300 301 302 303 304
		length = x[i].rdata.length;
		if (rdataset->type == dns_rdatatype_rrsig)
			length++;
		*rawbuf++ = (length & 0xff00) >> 8;
		*rawbuf++ = (length & 0x00ff);
305
#if DNS_RDATASET_FIXED
306
		rawbuf += 2;	/* filled in later */
307
#endif
308 309 310 311 312 313 314
		/*
		 * Store the per RR meta data.
		 */
		if (rdataset->type == dns_rdatatype_rrsig) {
			*rawbuf++ |= (x[i].rdata.flags & DNS_RDATA_OFFLINE) ?
					    DNS_RDATASLAB_OFFLINE : 0;
		}
315 316
		memcpy(rawbuf, x[i].rdata.data, x[i].rdata.length);
		rawbuf += x[i].rdata.length;
317
	}
Automatic Updater's avatar
Automatic Updater committed
318

319
#if DNS_RDATASET_FIXED
320 321
	fillin_offsets(offsetbase, offsettable, nalloc);
	isc_mem_put(mctx, offsettable, nalloc * sizeof(unsigned int));
322
#endif
323

324
	result = ISC_R_SUCCESS;
325

326
 free_rdatas:
327 328
	if (x != NULL)
		isc_mem_put(mctx, x, nalloc * sizeof(struct xrdata));
329
	return (result);
330 331
}

332 333 334 335 336 337 338 339 340 341 342 343 344 345 346
static void
rdataset_disassociate(dns_rdataset_t *rdataset) {
	UNUSED(rdataset);
}

static isc_result_t
rdataset_first(dns_rdataset_t *rdataset) {
	unsigned char *raw = rdataset->private3;
	unsigned int count;

	count = raw[0] * 256 + raw[1];
	if (count == 0) {
		rdataset->private5 = NULL;
		return (ISC_R_NOMORE);
	}
347
#if DNS_RDATASET_FIXED
348
	raw += 2 + (4 * count);
349 350 351
#else
	raw += 2;
#endif
352
	/*
353
	 * The privateuint4 field is the number of rdata beyond the cursor
354 355 356 357
	 * position, so we decrement the total count by one before storing
	 * it.
	 */
	count--;
358
	rdataset->privateuint4 = count;
359 360 361 362 363 364 365 366 367 368 369
	rdataset->private5 = raw;

	return (ISC_R_SUCCESS);
}

static isc_result_t
rdataset_next(dns_rdataset_t *rdataset) {
	unsigned int count;
	unsigned int length;
	unsigned char *raw;

370
	count = rdataset->privateuint4;
371 372 373
	if (count == 0)
		return (ISC_R_NOMORE);
	count--;
374
	rdataset->privateuint4 = count;
375 376
	raw = rdataset->private5;
	length = raw[0] * 256 + raw[1];
377
#if DNS_RDATASET_FIXED
378
	raw += length + 4;
379 380 381
#else
	raw += length + 2;
#endif
382 383 384 385 386 387 388 389 390
	rdataset->private5 = raw;

	return (ISC_R_SUCCESS);
}

static void
rdataset_current(dns_rdataset_t *rdataset, dns_rdata_t *rdata) {
	unsigned char *raw = rdataset->private5;
	isc_region_t r;
391 392
	unsigned int length;
	unsigned int flags = 0;
393 394 395

	REQUIRE(raw != NULL);

396
	length = raw[0] * 256 + raw[1];
397
#if DNS_RDATASET_FIXED
398
	raw += 4;
399 400
#else
	raw += 2;
Automatic Updater's avatar
Automatic Updater committed
401
#endif
402 403 404 405 406 407 408
	if (rdataset->type == dns_rdatatype_rrsig) {
		if (*raw & DNS_RDATASLAB_OFFLINE)
			flags |= DNS_RDATA_OFFLINE;
		length--;
		raw++;
	}
	r.length = length;
409 410
	r.base = raw;
	dns_rdata_fromregion(rdata, rdataset->rdclass, rdataset->type, &r);
411
	rdata->flags |= flags;
412 413 414 415 416 417 418 419 420
}

static void
rdataset_clone(dns_rdataset_t *source, dns_rdataset_t *target) {
	*target = *source;

	/*
	 * Reset iterator state.
	 */
421
	target->privateuint4 = 0;
422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440
	target->private5 = NULL;
}

static unsigned int
rdataset_count(dns_rdataset_t *rdataset) {
	unsigned char *raw = rdataset->private3;
	unsigned int count;

	count = raw[0] * 256 + raw[1];

	return (count);
}

static dns_rdatasetmethods_t rdataset_methods = {
	rdataset_disassociate,
	rdataset_first,
	rdataset_next,
	rdataset_current,
	rdataset_clone,
441 442
	rdataset_count,
	NULL,
443 444 445
	NULL,
	NULL,
	NULL,
446 447
	NULL,
	NULL,
448 449
	NULL,
	NULL,
450
	NULL
451 452 453 454 455 456 457 458
};

void
dns_rdataslab_tordataset(unsigned char *slab, unsigned int reservelen,
			 dns_rdataclass_t rdclass, dns_rdatatype_t rdtype,
			 dns_rdatatype_t covers, dns_ttl_t ttl,
			 dns_rdataset_t *rdataset)
{
Brian Wellington's avatar
Brian Wellington committed
459 460 461
	REQUIRE(slab != NULL);
	REQUIRE(!dns_rdataset_isassociated(rdataset));

462 463 464 465 466 467 468 469 470 471 472 473 474
	rdataset->methods = &rdataset_methods;
	rdataset->rdclass = rdclass;
	rdataset->type = rdtype;
	rdataset->covers = covers;
	rdataset->ttl = ttl;
	rdataset->trust = 0;
	rdataset->private1 = NULL;
	rdataset->private2 = NULL;
	rdataset->private3 = slab + reservelen;

	/*
	 * Reset iterator state.
	 */
475
	rdataset->privateuint4 = 0;
476 477 478
	rdataset->private5 = NULL;
}

479 480 481 482 483 484 485 486 487 488
unsigned int
dns_rdataslab_size(unsigned char *slab, unsigned int reservelen) {
	unsigned int count, length;
	unsigned char *current;

	REQUIRE(slab != NULL);

	current = slab + reservelen;
	count = *current++ * 256;
	count += *current++;
489
#if DNS_RDATASET_FIXED
490
	current += (4 * count);
491
#endif
492 493 494 495
	while (count > 0) {
		count--;
		length = *current++ * 256;
		length += *current++;
496
#if DNS_RDATASET_FIXED
497
		current += length + 2;
498 499 500
#else
		current += length;
#endif
501
	}
502

503
	return ((unsigned int)(current - slab));
504
}
Bob Halley's avatar
Bob Halley committed
505

506 507 508 509 510 511 512 513 514 515 516 517 518
/*
 * Make the dns_rdata_t 'rdata' refer to the slab item
 * beginning at '*current', which is part of a slab of type
 * 'type' and class 'rdclass', and advance '*current' to
 * point to the next item in the slab.
 */
static inline void
rdata_from_slab(unsigned char **current,
	      dns_rdataclass_t rdclass, dns_rdatatype_t type,
	      dns_rdata_t *rdata)
{
	unsigned char *tcurrent = *current;
	isc_region_t region;
519 520
	unsigned int length;
	isc_boolean_t offline = ISC_FALSE;
521

522 523 524 525 526 527 528 529 530 531
	length = *tcurrent++ * 256;
	length += *tcurrent++;

	if (type == dns_rdatatype_rrsig) {
		if ((*tcurrent & DNS_RDATASLAB_OFFLINE) != 0)
			offline = ISC_TRUE;
		length--;
		tcurrent++;
	}
	region.length = length;
532
#if DNS_RDATASET_FIXED
533
	tcurrent += 2;
534
#endif
535 536 537
	region.base = tcurrent;
	tcurrent += region.length;
	dns_rdata_fromregion(rdata, rdclass, type, &region);
538
	if (offline)
539
		rdata->flags |= DNS_RDATA_OFFLINE;
540 541 542 543 544 545 546 547
	*current = tcurrent;
}

/*
 * Return true iff 'slab' (slab data of type 'type' and class 'rdclass')
 * contains an rdata identical to 'rdata'.  This does case insensitive
 * comparisons per DNSSEC.
 */
548 549 550 551 552 553 554
static inline isc_boolean_t
rdata_in_slab(unsigned char *slab, unsigned int reservelen,
	      dns_rdataclass_t rdclass, dns_rdatatype_t type,
	      dns_rdata_t *rdata)
{
	unsigned int count, i;
	unsigned char *current;
555
	dns_rdata_t trdata = DNS_RDATA_INIT;
556
	int n;
557 558 559 560 561

	current = slab + reservelen;
	count = *current++ * 256;
	count += *current++;

562
#if DNS_RDATASET_FIXED
563
	current += (4 * count);
564
#endif
565

566
	for (i = 0; i < count; i++) {
567
		rdata_from_slab(&current, rdclass, type, &trdata);
Automatic Updater's avatar
Automatic Updater committed
568

569 570
		n = dns_rdata_compare(&trdata, rdata);
		if (n == 0)
571
			return (ISC_TRUE);
572 573
		if (n > 0)	/* In DNSSEC order. */
			break;
574
		dns_rdata_reset(&trdata);
575 576 577 578
	}
	return (ISC_FALSE);
}

579
isc_result_t
Bob Halley's avatar
Bob Halley committed
580 581 582
dns_rdataslab_merge(unsigned char *oslab, unsigned char *nslab,
		    unsigned int reservelen, isc_mem_t *mctx,
		    dns_rdataclass_t rdclass, dns_rdatatype_t type,
583
		    unsigned int flags, unsigned char **tslabp)
Bob Halley's avatar
Bob Halley committed
584
{
585
	unsigned char *ocurrent, *ostart, *ncurrent, *tstart, *tcurrent, *data;
Bob Halley's avatar
Bob Halley committed
586
	unsigned int ocount, ncount, count, olength, tlength, tcount, length;
587 588
	dns_rdata_t ordata = DNS_RDATA_INIT;
	dns_rdata_t nrdata = DNS_RDATA_INIT;
589
	isc_boolean_t added_something = ISC_FALSE;
590 591 592
	unsigned int oadded = 0;
	unsigned int nadded = 0;
	unsigned int nncount = 0;
593
#if DNS_RDATASET_FIXED
594 595 596 597 598
	unsigned int oncount;
	unsigned int norder = 0;
	unsigned int oorder = 0;
	unsigned char *offsetbase;
	unsigned int *offsettable;
599
#endif
Bob Halley's avatar
Bob Halley committed
600 601 602 603 604

	/*
	 * XXX  Need parameter to allow "delete rdatasets in nslab" merge,
	 * or perhaps another merge routine for this purpose.
	 */
605

Bob Halley's avatar
Bob Halley committed
606 607 608 609 610 611
	REQUIRE(tslabp != NULL && *tslabp == NULL);
	REQUIRE(oslab != NULL && nslab != NULL);

	ocurrent = oslab + reservelen;
	ocount = *ocurrent++ * 256;
	ocount += *ocurrent++;
612
#if DNS_RDATASET_FIXED
613
	ocurrent += (4 * ocount);
614
#endif
Bob Halley's avatar
Bob Halley committed
615 616 617 618
	ostart = ocurrent;
	ncurrent = nslab + reservelen;
	ncount = *ncurrent++ * 256;
	ncount += *ncurrent++;
619
#if DNS_RDATASET_FIXED
620
	ncurrent += (4 * ncount);
621
#endif
Bob Halley's avatar
Bob Halley committed
622 623
	INSIST(ocount > 0 && ncount > 0);

624
#if DNS_RDATASET_FIXED
625
	oncount = ncount;
626
#endif
627

Bob Halley's avatar
Bob Halley committed
628 629 630 631 632 633 634 635 636 637 638
	/*
	 * Yes, this is inefficient!
	 */

	/*
	 * Figure out the length of the old slab's data.
	 */
	olength = 0;
	for (count = 0; count < ocount; count++) {
		length = *ocurrent++ * 256;
		length += *ocurrent++;
639
#if DNS_RDATASET_FIXED
640 641
		olength += length + 8;
		ocurrent += length + 2;
642 643 644 645
#else
		olength += length + 2;
		ocurrent += length;
#endif
Bob Halley's avatar
Bob Halley committed
646 647 648 649 650 651 652 653 654 655 656 657 658
	}

	/*
	 * Start figuring out the target length and count.
	 */
	tlength = reservelen + 2 + olength;
	tcount = ocount;

	/*
	 * Add in the length of rdata in the new slab that aren't in
	 * the old slab.
	 */
	do {
659
		dns_rdata_init(&nrdata);
660
		rdata_from_slab(&ncurrent, rdclass, type, &nrdata);
661 662
		if (!rdata_in_slab(oslab, reservelen, rdclass, type, &nrdata))
		{
Bob Halley's avatar
Bob Halley committed
663 664 665
			/*
			 * This rdata isn't in the old slab.
			 */
666
#if DNS_RDATASET_FIXED
667
			tlength += nrdata.length + 8;
668
#else
669
			tlength += nrdata.length + 2;
670
#endif
671 672
			if (type == dns_rdatatype_rrsig)
				tlength++;
Bob Halley's avatar
Bob Halley committed
673
			tcount++;
674
			nncount++;
675
			added_something = ISC_TRUE;
Bob Halley's avatar
Bob Halley committed
676 677 678
		}
		ncount--;
	} while (ncount > 0);
679
	ncount = nncount;
Bob Halley's avatar
Bob Halley committed
680

681 682
	if (((flags & DNS_RDATASLAB_EXACT) != 0) &&
	    (tcount != ncount + ocount))
683 684 685
		return (DNS_R_NOTEXACT);

	if (!added_something && (flags & DNS_RDATASLAB_FORCE) == 0)
686 687
		return (DNS_R_UNCHANGED);

688 689 690 691 692 693 694 695 696 697 698
	/*
	 * Ensure that singleton types are actually singletons.
	 */
	if (tcount > 1 && dns_rdatatype_issingleton(type)) {
		/*
		 * We have a singleton type, but there's more than one
		 * RR in the rdataset.
		 */
		return (DNS_R_SINGLETON);
	}

699 700 701
	if (tcount > 0xffff)
		return (ISC_R_NOSPACE);

Bob Halley's avatar
Bob Halley committed
702 703 704 705 706
	/*
	 * Copy the reserved area from the new slab.
	 */
	tstart = isc_mem_get(mctx, tlength);
	if (tstart == NULL)
707
		return (ISC_R_NOMEMORY);
Bob Halley's avatar
Bob Halley committed
708 709
	memcpy(tstart, nslab, reservelen);
	tcurrent = tstart + reservelen;
710
#if DNS_RDATASET_FIXED
711
	offsetbase = tcurrent;
712
#endif
713

Bob Halley's avatar
Bob Halley committed
714 715 716 717 718 719
	/*
	 * Write the new count.
	 */
	*tcurrent++ = (tcount & 0xff00) >> 8;
	*tcurrent++ = (tcount & 0x00ff);

720
#if DNS_RDATASET_FIXED
721 722 723 724 725 726 727 728 729 730 731 732
	/*
	 * Skip offset table.
	 */
	tcurrent += (tcount * 4);

	offsettable = isc_mem_get(mctx,
				  (ocount + oncount) * sizeof(unsigned int));
	if (offsettable == NULL) {
		isc_mem_put(mctx, tstart, tlength);
		return (ISC_R_NOMEMORY);
	}
	memset(offsettable, 0, (ocount + oncount) * sizeof(unsigned int));
733
#endif
734

Bob Halley's avatar
Bob Halley committed
735
	/*
736
	 * Merge the two slabs.
Bob Halley's avatar
Bob Halley committed
737
	 */
738
	ocurrent = ostart;
739
	INSIST(ocount != 0);
740
#if DNS_RDATASET_FIXED
741 742
	oorder = ocurrent[2] * 256 + ocurrent[3];
	INSIST(oorder < ocount);
743
#endif
744
	rdata_from_slab(&ocurrent, rdclass, type, &ordata);
745 746

	ncurrent = nslab + reservelen + 2;
747
#if DNS_RDATASET_FIXED
748
	ncurrent += (4 * oncount);
749
#endif
750

751 752
	if (ncount > 0) {
		do {
753
			dns_rdata_reset(&nrdata);
754
#if DNS_RDATASET_FIXED
755
			norder = ncurrent[2] * 256 + ncurrent[3];
756

757
			INSIST(norder < oncount);
758 759
#endif
			rdata_from_slab(&ncurrent, rdclass, type, &nrdata);
760 761 762
		} while (rdata_in_slab(oslab, reservelen, rdclass,
				       type, &nrdata));
	}
Bob Halley's avatar
Bob Halley committed
763

764 765 766 767 768 769 770 771 772
	while (oadded < ocount || nadded < ncount) {
		isc_boolean_t fromold;
		if (oadded == ocount)
			fromold = ISC_FALSE;
		else if (nadded == ncount)
			fromold = ISC_TRUE;
		else
			fromold = ISC_TF(compare_rdata(&ordata, &nrdata) < 0);
		if (fromold) {
773
#if DNS_RDATASET_FIXED
774
			offsettable[oorder] = tcurrent - offsetbase;
775
#endif
776
			length = ordata.length;
777 778 779 780 781
			data = ordata.data;
			if (type == dns_rdatatype_rrsig) {
				length++;
				data--;
			}
782 783
			*tcurrent++ = (length & 0xff00) >> 8;
			*tcurrent++ = (length & 0x00ff);
784
#if DNS_RDATASET_FIXED
785
			tcurrent += 2;	/* fill in later */
786
#endif
787
			memcpy(tcurrent, data, length);
788 789 790
			tcurrent += length;
			oadded++;
			if (oadded < ocount) {
791
				dns_rdata_reset(&ordata);
792
#if DNS_RDATASET_FIXED
793 794
				oorder = ocurrent[2] * 256 + ocurrent[3];
				INSIST(oorder < ocount);
795 796
#endif
				rdata_from_slab(&ocurrent, rdclass, type,
797 798 799
						&ordata);
			}
		} else {
800
#if DNS_RDATASET_FIXED
801
			offsettable[ocount + norder] = tcurrent - offsetbase;
802
#endif
803
			length = nrdata.length;
804 805 806 807 808
			data = nrdata.data;
			if (type == dns_rdatatype_rrsig) {
				length++;
				data--;
			}
809 810
			*tcurrent++ = (length & 0xff00) >> 8;
			*tcurrent++ = (length & 0x00ff);
811
#if DNS_RDATASET_FIXED
812
			tcurrent += 2;	/* fill in later */
813
#endif
814
			memcpy(tcurrent, data, length);
815 816 817 818
			tcurrent += length;
			nadded++;
			if (nadded < ncount) {
				do {
819
					dns_rdata_reset(&nrdata);
820
#if DNS_RDATASET_FIXED
821 822
					norder = ncurrent[2] * 256 + ncurrent[3];
					INSIST(norder < oncount);
823 824
#endif
					rdata_from_slab(&ncurrent, rdclass,
825 826 827 828 829
							type, &nrdata);
				} while (rdata_in_slab(oslab, reservelen,
						       rdclass, type,
						       &nrdata));
			}
Bob Halley's avatar
Bob Halley committed
830
		}
831
	}
Bob Halley's avatar
Bob Halley committed
832

833
#if DNS_RDATASET_FIXED
834 835 836 837
	fillin_offsets(offsetbase, offsettable, ocount + oncount);

	isc_mem_put(mctx, offsettable,
		    (ocount + oncount) * sizeof(unsigned int));
838
#endif
839

840 841
	INSIST(tcurrent == tstart + tlength);

Bob Halley's avatar
Bob Halley committed
842 843
	*tslabp = tstart;

844
	return (ISC_R_SUCCESS);
Bob Halley's avatar
Bob Halley committed
845
}
846

847
isc_result_t
848 849 850
dns_rdataslab_subtract(unsigned char *mslab, unsigned char *sslab,
		       unsigned int reservelen, isc_mem_t *mctx,
		       dns_rdataclass_t rdclass, dns_rdatatype_t type,
851
		       unsigned int flags, unsigned char **tslabp)
852 853
{
	unsigned char *mcurrent, *sstart, *scurrent, *tstart, *tcurrent;
854
	unsigned int mcount, scount, rcount ,count, tlength, tcount, i;
855 856
	dns_rdata_t srdata = DNS_RDATA_INIT;
	dns_rdata_t mrdata = DNS_RDATA_INIT;
857
#if DNS_RDATASET_FIXED
858 859 860
	unsigned char *offsetbase;
	unsigned int *offsettable;
	unsigned int order;
861
#endif
862 863 864 865 866 867 868 869 870 871

	REQUIRE(tslabp != NULL && *tslabp == NULL);
	REQUIRE(mslab != NULL && sslab != NULL);

	mcurrent = mslab + reservelen;
	mcount = *mcurrent++ * 256;
	mcount += *mcurrent++;
	scurrent = sslab + reservelen;
	scount = *scurrent++ * 256;
	scount += *scurrent++;
872
	INSIST(mcount > 0 && scount > 0);
873 874 875 876 877 878 879 880 881 882

	/*
	 * Yes, this is inefficient!
	 */

	/*
	 * Start figuring out the target length and count.
	 */
	tlength = reservelen + 2;
	tcount = 0;
883
	rcount = 0;
884

885
#if DNS_RDATASET_FIXED
886 887
	mcurrent += 4 * mcount;
	scurrent += 4 * scount;
888
#endif
889 890
	sstart = scurrent;

891 892 893 894
	/*
	 * Add in the length of rdata in the mslab that aren't in
	 * the sslab.
	 */
895
	for (i = 0; i < mcount; i++) {
896 897
		unsigned char *mrdatabegin = mcurrent;
		rdata_from_slab(&mcurrent, rdclass, type, &mrdata);
898 899
		scurrent = sstart;
		for (count = 0; count < scount; count++) {
900
			dns_rdata_reset(&srdata);
901
			rdata_from_slab(&scurrent, rdclass, type, &srdata);