rdataslab.c 24.8 KB
Newer Older
1
/*
Automatic Updater's avatar
Automatic Updater committed
2
 * Copyright (C) 2004-2008  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
 */

Francis Dupont's avatar
Francis Dupont committed
18
/* $Id: rdataslab.c,v 1.49 2009/01/17 14:55:03 fdupont Exp $ */
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 56 57
 * 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)
 *		data		(data length bytes)
 *
58 59 60
 * Offsets are from the end of the header.
 *
 * Load order traversal is performed by walking the offset table to find
61
 * the start of the record (DNS_RDATASET_FIXED = 1).
62 63 64
 *
 * DNSSEC order traversal is performed by walking the data records.
 *
Francis Dupont's avatar
Francis Dupont committed
65
 * The order is stored with record to allow for efficient reconstruction
66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
 * 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;
};

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

92
#if DNS_RDATASET_FIXED
93 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
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;
	}
121
}
122
#endif
123

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

	buflen = reservelen + 2;
144 145 146

	nalloc = dns_rdataset_count(rdataset);
	nitems = nalloc;
147 148
	if (nitems == 0)
		return (ISC_R_FAILURE);
149

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

	x = isc_mem_get(mctx, nalloc * sizeof(struct xrdata));
	if (x == NULL)
155 156 157 158 159
		return (ISC_R_NOMEMORY);

	/*
	 * Save all of the rdata members into an array.
	 */
160
	result = dns_rdataset_first(rdataset);
161 162 163
	if (result != ISC_R_SUCCESS)
		goto free_rdatas;
	for (i = 0; i < nalloc && result == ISC_R_SUCCESS; i++) {
164
		INSIST(result == ISC_R_SUCCESS);
165 166
		dns_rdata_init(&x[i].rdata);
		dns_rdataset_current(rdataset, &x[i].rdata);
167
#if DNS_RDATASET_FIXED
168
		x[i].order = i;
169
#endif
170 171
		result = dns_rdataset_next(rdataset);
	}
172 173 174 175 176 177 178 179 180 181
	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;
	}
182

183 184 185 186
	/*
	 * Put into DNSSEC order.
	 */
	qsort(x, nalloc, sizeof(struct xrdata), compare_rdata);
187 188

	/*
189 190 191 192 193
	 * 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
194 195
	 * records, and 8 for each rdata, (length(2), offset(4) and order(2))
	 * and then the rdata itself.
196 197
	 */
	for (i = 1; i < nalloc; i++) {
198 199 200
		if (compare_rdata(&x[i-1].rdata, &x[i].rdata) == 0) {
			x[i-1].rdata.data = NULL;
			x[i-1].rdata.length = 0;
201
#if DNS_RDATASET_FIXED
202 203 204 205 206 207
			/*
			 * 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;
208
#endif
209
			nitems--;
210
		} else {
211
#if DNS_RDATASET_FIXED
212
			buflen += (8 + x[i-1].rdata.length);
213 214 215
#else
			buflen += (2 + x[i-1].rdata.length);
#endif
216 217 218 219 220 221
			/*
			 * Provide space to store the per RR meta data.
			 */
			if (rdataset->type == dns_rdatatype_rrsig)
				buflen++;
		}
222
	}
223
	/*
224
	 * Don't forget the last item!
225
	 */
226
#if DNS_RDATASET_FIXED
227
	buflen += (8 + x[i-1].rdata.length);
228 229 230
#else
	buflen += (2 + x[i-1].rdata.length);
#endif
231 232 233 234 235
	/*
	 * Provide space to store the per RR meta data.
	 */
	if (rdataset->type == dns_rdatatype_rrsig)
		buflen++;
236

237
	/*
238
	 * Ensure that singleton types are actually singletons.
239 240 241 242 243 244 245 246
	 */
	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;
247
	}
248 249 250 251 252 253

	/*
	 * Allocate the memory, set up a buffer, start copying in
	 * data.
	 */
	rawbuf = isc_mem_get(mctx, buflen);
254
	if (rawbuf == NULL) {
255 256
		result = ISC_R_NOMEMORY;
		goto free_rdatas;
257
	}
Automatic Updater's avatar
Automatic Updater committed
258

259
#if DNS_RDATASET_FIXED
260 261 262 263 264 265 266 267
	/* 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));
268
#endif
269 270 271 272 273

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

	rawbuf += reservelen;
274
#if DNS_RDATASET_FIXED
275
	offsetbase = rawbuf;
276
#endif
277 278 279

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

281
#if DNS_RDATASET_FIXED
282 283
	/* Skip load order table.  Filled in later. */
	rawbuf += nitems * 4;
284
#endif
285

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

311
#if DNS_RDATASET_FIXED
312 313
	fillin_offsets(offsetbase, offsettable, nalloc);
	isc_mem_put(mctx, offsettable, nalloc * sizeof(unsigned int));
314
#endif
315

316
	result = ISC_R_SUCCESS;
317

318
 free_rdatas:
319
	isc_mem_put(mctx, x, nalloc * sizeof(struct xrdata));
320
	return (result);
321 322
}

323 324 325 326 327 328 329 330 331 332 333 334 335 336 337
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);
	}
338
#if DNS_RDATASET_FIXED
339
	raw += 2 + (4 * count);
340 341 342
#else
	raw += 2;
#endif
343
	/*
344
	 * The privateuint4 field is the number of rdata beyond the cursor
345 346 347 348
	 * position, so we decrement the total count by one before storing
	 * it.
	 */
	count--;
349
	rdataset->privateuint4 = count;
350 351 352 353 354 355 356 357 358 359 360
	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;

361
	count = rdataset->privateuint4;
362 363 364
	if (count == 0)
		return (ISC_R_NOMORE);
	count--;
365
	rdataset->privateuint4 = count;
366 367
	raw = rdataset->private5;
	length = raw[0] * 256 + raw[1];
368
#if DNS_RDATASET_FIXED
369
	raw += length + 4;
370 371 372
#else
	raw += length + 2;
#endif
373 374 375 376 377 378 379 380 381
	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;
382 383
	unsigned int length;
	unsigned int flags = 0;
384 385 386

	REQUIRE(raw != NULL);

387
	length = raw[0] * 256 + raw[1];
388
#if DNS_RDATASET_FIXED
389
	raw += 4;
390 391
#else
	raw += 2;
Automatic Updater's avatar
Automatic Updater committed
392
#endif
393 394 395 396 397 398 399
	if (rdataset->type == dns_rdatatype_rrsig) {
		if (*raw & DNS_RDATASLAB_OFFLINE)
			flags |= DNS_RDATA_OFFLINE;
		length--;
		raw++;
	}
	r.length = length;
400 401
	r.base = raw;
	dns_rdata_fromregion(rdata, rdataset->rdclass, rdataset->type, &r);
402
	rdata->flags |= flags;
403 404 405 406 407 408 409 410 411
}

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

	/*
	 * Reset iterator state.
	 */
412
	target->privateuint4 = 0;
413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431
	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,
432 433
	rdataset_count,
	NULL,
434 435 436
	NULL,
	NULL,
	NULL,
437 438
	NULL,
	NULL,
439
	NULL
440 441 442 443 444 445 446 447
};

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
448 449 450
	REQUIRE(slab != NULL);
	REQUIRE(!dns_rdataset_isassociated(rdataset));

451 452 453 454 455 456 457 458 459 460 461 462 463
	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.
	 */
464
	rdataset->privateuint4 = 0;
465 466 467
	rdataset->private5 = NULL;
}

468 469 470 471 472 473 474 475 476 477
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++;
478
#if DNS_RDATASET_FIXED
479
	current += (4 * count);
480
#endif
481 482 483 484
	while (count > 0) {
		count--;
		length = *current++ * 256;
		length += *current++;
485
#if DNS_RDATASET_FIXED
486
		current += length + 2;
487 488 489
#else
		current += length;
#endif
490
	}
491

492
	return ((unsigned int)(current - slab));
493
}
Bob Halley's avatar
Bob Halley committed
494

495 496 497 498 499 500 501 502 503 504 505 506 507
/*
 * 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;
508 509
	unsigned int length;
	isc_boolean_t offline = ISC_FALSE;
510

511 512 513 514 515 516 517 518 519 520
	length = *tcurrent++ * 256;
	length += *tcurrent++;

	if (type == dns_rdatatype_rrsig) {
		if ((*tcurrent & DNS_RDATASLAB_OFFLINE) != 0)
			offline = ISC_TRUE;
		length--;
		tcurrent++;
	}
	region.length = length;
521
#if DNS_RDATASET_FIXED
522
	tcurrent += 2;
523
#endif
524 525 526
	region.base = tcurrent;
	tcurrent += region.length;
	dns_rdata_fromregion(rdata, rdclass, type, &region);
527
	if (offline)
528
		rdata->flags |= DNS_RDATA_OFFLINE;
529 530 531 532 533 534 535 536
	*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.
 */
537 538 539 540 541 542 543
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;
544
	dns_rdata_t trdata = DNS_RDATA_INIT;
545
	int n;
546 547 548 549 550

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

551
#if DNS_RDATASET_FIXED
552
	current += (4 * count);
553
#endif
554

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

558 559
		n = dns_rdata_compare(&trdata, rdata);
		if (n == 0)
560
			return (ISC_TRUE);
561 562
		if (n > 0)	/* In DNSSEC order. */
			break;
563
		dns_rdata_reset(&trdata);
564 565 566 567
	}
	return (ISC_FALSE);
}

568
isc_result_t
Bob Halley's avatar
Bob Halley committed
569 570 571
dns_rdataslab_merge(unsigned char *oslab, unsigned char *nslab,
		    unsigned int reservelen, isc_mem_t *mctx,
		    dns_rdataclass_t rdclass, dns_rdatatype_t type,
572
		    unsigned int flags, unsigned char **tslabp)
Bob Halley's avatar
Bob Halley committed
573
{
574
	unsigned char *ocurrent, *ostart, *ncurrent, *tstart, *tcurrent, *data;
Bob Halley's avatar
Bob Halley committed
575
	unsigned int ocount, ncount, count, olength, tlength, tcount, length;
576 577
	dns_rdata_t ordata = DNS_RDATA_INIT;
	dns_rdata_t nrdata = DNS_RDATA_INIT;
578
	isc_boolean_t added_something = ISC_FALSE;
579 580 581
	unsigned int oadded = 0;
	unsigned int nadded = 0;
	unsigned int nncount = 0;
582
#if DNS_RDATASET_FIXED
583 584 585 586 587
	unsigned int oncount;
	unsigned int norder = 0;
	unsigned int oorder = 0;
	unsigned char *offsetbase;
	unsigned int *offsettable;
588
#endif
Bob Halley's avatar
Bob Halley committed
589 590 591 592 593

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

Bob Halley's avatar
Bob Halley committed
595 596 597 598 599 600
	REQUIRE(tslabp != NULL && *tslabp == NULL);
	REQUIRE(oslab != NULL && nslab != NULL);

	ocurrent = oslab + reservelen;
	ocount = *ocurrent++ * 256;
	ocount += *ocurrent++;
601
#if DNS_RDATASET_FIXED
602
	ocurrent += (4 * ocount);
603
#endif
Bob Halley's avatar
Bob Halley committed
604 605 606 607
	ostart = ocurrent;
	ncurrent = nslab + reservelen;
	ncount = *ncurrent++ * 256;
	ncount += *ncurrent++;
608
#if DNS_RDATASET_FIXED
609
	ncurrent += (4 * ncount);
610
#endif
Bob Halley's avatar
Bob Halley committed
611 612
	INSIST(ocount > 0 && ncount > 0);

613
#if DNS_RDATASET_FIXED
614
	oncount = ncount;
615
#endif
616

Bob Halley's avatar
Bob Halley committed
617 618 619 620 621 622 623 624 625 626 627
	/*
	 * 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++;
628
#if DNS_RDATASET_FIXED
629 630
		olength += length + 8;
		ocurrent += length + 2;
631 632 633 634
#else
		olength += length + 2;
		ocurrent += length;
#endif
Bob Halley's avatar
Bob Halley committed
635 636 637 638 639 640 641 642 643 644 645 646 647
	}

	/*
	 * 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 {
648
		dns_rdata_init(&nrdata);
649
		rdata_from_slab(&ncurrent, rdclass, type, &nrdata);
650 651
		if (!rdata_in_slab(oslab, reservelen, rdclass, type, &nrdata))
		{
Bob Halley's avatar
Bob Halley committed
652 653 654
			/*
			 * This rdata isn't in the old slab.
			 */
655
#if DNS_RDATASET_FIXED
656
			tlength += nrdata.length + 8;
657
#else
658
			tlength += nrdata.length + 2;
659
#endif
660 661
			if (type == dns_rdatatype_rrsig)
				tlength++;
Bob Halley's avatar
Bob Halley committed
662
			tcount++;
663
			nncount++;
664
			added_something = ISC_TRUE;
Bob Halley's avatar
Bob Halley committed
665 666 667
		}
		ncount--;
	} while (ncount > 0);
668
	ncount = nncount;
Bob Halley's avatar
Bob Halley committed
669

670 671
	if (((flags & DNS_RDATASLAB_EXACT) != 0) &&
	    (tcount != ncount + ocount))
672 673 674
		return (DNS_R_NOTEXACT);

	if (!added_something && (flags & DNS_RDATASLAB_FORCE) == 0)
675 676
		return (DNS_R_UNCHANGED);

677 678 679 680 681 682 683 684 685 686 687
	/*
	 * 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);
	}

688 689 690
	if (tcount > 0xffff)
		return (ISC_R_NOSPACE);

Bob Halley's avatar
Bob Halley committed
691 692 693 694 695
	/*
	 * Copy the reserved area from the new slab.
	 */
	tstart = isc_mem_get(mctx, tlength);
	if (tstart == NULL)
696
		return (ISC_R_NOMEMORY);
Bob Halley's avatar
Bob Halley committed
697 698
	memcpy(tstart, nslab, reservelen);
	tcurrent = tstart + reservelen;
699
#if DNS_RDATASET_FIXED
700
	offsetbase = tcurrent;
701
#endif
702

Bob Halley's avatar
Bob Halley committed
703 704 705 706 707 708
	/*
	 * Write the new count.
	 */
	*tcurrent++ = (tcount & 0xff00) >> 8;
	*tcurrent++ = (tcount & 0x00ff);

709
#if DNS_RDATASET_FIXED
710 711 712 713 714 715 716 717 718 719 720 721
	/*
	 * 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));
722
#endif
723

Bob Halley's avatar
Bob Halley committed
724
	/*
725
	 * Merge the two slabs.
Bob Halley's avatar
Bob Halley committed
726
	 */
727
	ocurrent = ostart;
728
	INSIST(ocount != 0);
729
#if DNS_RDATASET_FIXED
730 731
	oorder = ocurrent[2] * 256 + ocurrent[3];
	INSIST(oorder < ocount);
732
#endif
733
	rdata_from_slab(&ocurrent, rdclass, type, &ordata);
734 735

	ncurrent = nslab + reservelen + 2;
736
#if DNS_RDATASET_FIXED
737
	ncurrent += (4 * oncount);
738
#endif
739

740 741
	if (ncount > 0) {
		do {
742
			dns_rdata_reset(&nrdata);
743
#if DNS_RDATASET_FIXED
744
			norder = ncurrent[2] * 256 + ncurrent[3];
745

746
			INSIST(norder < oncount);
747 748
#endif
			rdata_from_slab(&ncurrent, rdclass, type, &nrdata);
749 750 751
		} while (rdata_in_slab(oslab, reservelen, rdclass,
				       type, &nrdata));
	}
Bob Halley's avatar
Bob Halley committed
752

753 754 755 756 757 758 759 760 761
	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) {
762
#if DNS_RDATASET_FIXED
763
			offsettable[oorder] = tcurrent - offsetbase;
764
#endif
765
			length = ordata.length;
766 767 768 769 770
			data = ordata.data;
			if (type == dns_rdatatype_rrsig) {
				length++;
				data--;
			}
771 772
			*tcurrent++ = (length & 0xff00) >> 8;
			*tcurrent++ = (length & 0x00ff);
773
#if DNS_RDATASET_FIXED
774
			tcurrent += 2;	/* fill in later */
775
#endif
776
			memcpy(tcurrent, data, length);
777 778 779
			tcurrent += length;
			oadded++;
			if (oadded < ocount) {
780
				dns_rdata_reset(&ordata);
781
#if DNS_RDATASET_FIXED
782 783
				oorder = ocurrent[2] * 256 + ocurrent[3];
				INSIST(oorder < ocount);
784 785
#endif
				rdata_from_slab(&ocurrent, rdclass, type,
786 787 788
						&ordata);
			}
		} else {
789
#if DNS_RDATASET_FIXED
790
			offsettable[ocount + norder] = tcurrent - offsetbase;
791
#endif
792
			length = nrdata.length;
793 794 795 796 797
			data = nrdata.data;
			if (type == dns_rdatatype_rrsig) {
				length++;
				data--;
			}
798 799
			*tcurrent++ = (length & 0xff00) >> 8;
			*tcurrent++ = (length & 0x00ff);
800
#if DNS_RDATASET_FIXED
801
			tcurrent += 2;	/* fill in later */
802
#endif
803
			memcpy(tcurrent, data, length);
804 805 806 807
			tcurrent += length;
			nadded++;
			if (nadded < ncount) {
				do {
808
					dns_rdata_reset(&nrdata);
809
#if DNS_RDATASET_FIXED
810 811
					norder = ncurrent[2] * 256 + ncurrent[3];
					INSIST(norder < oncount);
812 813
#endif
					rdata_from_slab(&ncurrent, rdclass,
814 815 816 817 818
							type, &nrdata);
				} while (rdata_in_slab(oslab, reservelen,
						       rdclass, type,
						       &nrdata));
			}
Bob Halley's avatar
Bob Halley committed
819
		}
820
	}
Bob Halley's avatar
Bob Halley committed
821

822
#if DNS_RDATASET_FIXED
823 824 825 826
	fillin_offsets(offsetbase, offsettable, ocount + oncount);

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

829 830
	INSIST(tcurrent == tstart + tlength);

Bob Halley's avatar
Bob Halley committed
831 832
	*tslabp = tstart;

833
	return (ISC_R_SUCCESS);
Bob Halley's avatar
Bob Halley committed
834
}
835

836
isc_result_t
837 838 839
dns_rdataslab_subtract(unsigned char *mslab, unsigned char *sslab,
		       unsigned int reservelen, isc_mem_t *mctx,
		       dns_rdataclass_t rdclass, dns_rdatatype_t type,
840
		       unsigned int flags, unsigned char **tslabp)
841 842
{
	unsigned char *mcurrent, *sstart, *scurrent, *tstart, *tcurrent;
843
	unsigned int mcount, scount, rcount ,count, tlength, tcount, i;
844 845
	dns_rdata_t srdata = DNS_RDATA_INIT;
	dns_rdata_t mrdata = DNS_RDATA_INIT;
846
#if DNS_RDATASET_FIXED
847 848 849
	unsigned char *offsetbase;
	unsigned int *offsettable;
	unsigned int order;
850
#endif
851 852 853 854 855 856 857 858 859 860

	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++;
861
	INSIST(mcount > 0 && scount > 0);
862 863 864 865 866 867 868 869 870 871

	/*
	 * Yes, this is inefficient!
	 */

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

874
#if DNS_RDATASET_FIXED
875 876
	mcurrent += 4 * mcount;
	scurrent += 4 * scount;
877
#endif
878 879
	sstart = scurrent;

880 881 882 883
	/*
	 * Add in the length of rdata in the mslab that aren't in
	 * the sslab.
	 */
884
	for (i = 0; i < mcount; i++) {
885 886
		unsigned char *mrdatabegin = mcurrent;
		rdata_from_slab(&mcurrent, rdclass, type, &mrdata);
887 888
		scurrent = sstart;
		for (count = 0; count < scount; count++) {
889
			dns_rdata_reset(&srdata);
890
			rdata_from_slab(&scurrent, rdclass, type, &srdata);
891 892 893 894 895 896 897 898
			if (dns_rdata_compare(&mrdata, &srdata) == 0)
				break;
		}
		if (count == scount) {
			/*
			 * This rdata isn't in the sslab, and thus isn't
			 * being subtracted.
			 */
899
			tlength += mcurrent - mrdatabegin;
900
			tcount++;
901
		} else
902
			rcount++;
903
		dns_rdata_reset(&mrdata);
904 905
	}

906
#if DNS_RDATASET_FIXED
907
	tlength += (4 * tcount);
908
#endif
909

910 911
	/*
	 * Check that all the records originally existed.  The numeric
912
	 * check only works as rdataslabs do not contain duplicates.
913
	 */
914
	if (((flags & DNS_RDATASLAB_EXACT) != 0) && (rcount != scount))
915 916
		return (DNS_R_NOTEXACT);

917 918 919 920
	/*
	 * Don't continue if the new rdataslab would be empty.
	 */
	if (tcount == 0)
921
		return (DNS_R_NXRRSET);
922

923 924 925
	/*
	 * If nothing is going to change, we can stop.
	 */
926
	if (rcount == 0)
927 928
		return (DNS_R_UNCHANGED);

929 930 931 932 933
	/*
	 * Copy the reserved area from the mslab.
	 */
	tstart = isc_mem_get(mctx, tlength);
	if (tstart == NULL)
934
		return (ISC_R_NOMEMORY);
935 936
	memcpy(tstart, mslab, reservelen);
	tcurrent = tstart + reservelen;
937
#if DNS_RDATASET_FIXED
938 939 940 941 942 943 944 945
	offsetbase = tcurrent;

	offsettable = isc_mem_get(mctx, mcount * sizeof(unsigned int));
	if (offsettable == NULL) {
		isc_mem_put(mctx, tstart, tlength);
		return (ISC_R_NOMEMORY);
	}
	memset(offsettable, 0, mcount * sizeof(unsigned int));
946
#endif
947

948 949 950 951 952 953
	/*
	 * Write the new count.
	 */
	*tcurrent++ = (tcount & 0xff00) >> 8;
	*tcurrent++ = (tcount & 0x00ff);

954
#if DNS_RDATASET_FIXED
955
	tcurrent += (4 * tcount);
956
#endif
957

958 959 960
	/*
	 * Copy the parts of mslab not in sslab.
	 */
961
	mcurrent = mslab + reservelen;
962 963
	mcount = *mcurrent++ * 256;
	mcount += *mcurrent++;
964
#if DNS_RDATASET_FIXED