1/*	$NetBSD$	*/
2
3/*
4 * Copyright (C) 2004-2012  Internet Systems Consortium, Inc. ("ISC")
5 * Copyright (C) 1999-2003  Internet Software Consortium.
6 *
7 * Permission to use, copy, modify, and/or distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
12 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
13 * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
14 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
15 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
16 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
17 * PERFORMANCE OF THIS SOFTWARE.
18 */
19
20/* Id */
21
22/*! \file */
23
24#include <config.h>
25
26#include <stdlib.h>
27
28#include <isc/mem.h>
29#include <isc/region.h>
30#include <isc/string.h>		/* Required for HP/UX (and others?) */
31#include <isc/util.h>
32
33#include <dns/result.h>
34#include <dns/rdata.h>
35#include <dns/rdataset.h>
36#include <dns/rdataslab.h>
37
38/*
39 * The rdataslab structure allows iteration to occur in both load order
40 * and DNSSEC order.  The structure is as follows:
41 *
42 *	header		(reservelen bytes)
43 *	record count	(2 bytes)
44 *	offset table	(4 x record count bytes in load order)
45 *	data records
46 *		data length	(2 bytes)
47 *		order		(2 bytes)
48 *		meta data	(1 byte for RRSIG's)
49 *		data		(data length bytes)
50 *
51 * If DNS_RDATASET_FIXED is defined to be zero (0) the format of a
52 * rdataslab is as follows:
53 *
54 *	header		(reservelen bytes)
55 *	record count	(2 bytes)
56 *	data records
57 *		data length	(2 bytes)
58 *		meta data	(1 byte for RRSIG's)
59 *		data		(data length bytes)
60 *
61 * Offsets are from the end of the header.
62 *
63 * Load order traversal is performed by walking the offset table to find
64 * the start of the record (DNS_RDATASET_FIXED = 1).
65 *
66 * DNSSEC order traversal is performed by walking the data records.
67 *
68 * The order is stored with record to allow for efficient reconstruction
69 * of the offset table following a merge or subtraction.
70 *
71 * The iterator methods here currently only support DNSSEC order iteration.
72 *
73 * The iterator methods in rbtdb support both load order and DNSSEC order
74 * iteration.
75 *
76 * WARNING:
77 *	rbtdb.c directly interacts with the slab's raw structures.  If the
78 *	structure changes then rbtdb.c also needs to be updated to reflect
79 *	the changes.  See the areas tagged with "RDATASLAB".
80 */
81
82struct xrdata {
83	dns_rdata_t	rdata;
84	unsigned int	order;
85};
86
87/*% Note: the "const void *" are just to make qsort happy.  */
88static int
89compare_rdata(const void *p1, const void *p2) {
90	const struct xrdata *x1 = p1;
91	const struct xrdata *x2 = p2;
92	return (dns_rdata_compare(&x1->rdata, &x2->rdata));
93}
94
95#if DNS_RDATASET_FIXED
96static void
97fillin_offsets(unsigned char *offsetbase, unsigned int *offsettable,
98	       unsigned length)
99{
100	unsigned int i, j;
101	unsigned char *raw;
102
103	for (i = 0, j = 0; i < length; i++) {
104
105		if (offsettable[i] == 0)
106			continue;
107
108		/*
109		 * Fill in offset table.
110		 */
111		raw = &offsetbase[j*4 + 2];
112		*raw++ = (offsettable[i] & 0xff000000) >> 24;
113		*raw++ = (offsettable[i] & 0xff0000) >> 16;
114		*raw++ = (offsettable[i] & 0xff00) >> 8;
115		*raw = offsettable[i] & 0xff;
116
117		/*
118		 * Fill in table index.
119		 */
120		raw = offsetbase + offsettable[i] + 2;
121		*raw++ = (j & 0xff00) >> 8;
122		*raw = j++ & 0xff;
123	}
124}
125#endif
126
127isc_result_t
128dns_rdataslab_fromrdataset(dns_rdataset_t *rdataset, isc_mem_t *mctx,
129			   isc_region_t *region, unsigned int reservelen)
130{
131	/*
132	 * Use &removed as a sentinal pointer for duplicate
133	 * rdata as rdata.data == NULL is valid.
134	 */
135	static unsigned char removed;
136	struct xrdata  *x;
137	unsigned char  *rawbuf;
138#if DNS_RDATASET_FIXED
139	unsigned char  *offsetbase;
140#endif
141	unsigned int	buflen;
142	isc_result_t	result;
143	unsigned int	nitems;
144	unsigned int	nalloc;
145	unsigned int	i;
146#if DNS_RDATASET_FIXED
147	unsigned int   *offsettable;
148#endif
149	unsigned int	length;
150
151	buflen = reservelen + 2;
152
153	nalloc = dns_rdataset_count(rdataset);
154	nitems = nalloc;
155	if (nitems == 0 && rdataset->type != 0)
156		return (ISC_R_FAILURE);
157
158	if (nalloc > 0xffff)
159		return (ISC_R_NOSPACE);
160
161
162	if (nalloc != 0) {
163		x = isc_mem_get(mctx, nalloc * sizeof(struct xrdata));
164		if (x == NULL)
165			return (ISC_R_NOMEMORY);
166	} else
167		x = NULL;
168
169	/*
170	 * Save all of the rdata members into an array.
171	 */
172	result = dns_rdataset_first(rdataset);
173	if (result != ISC_R_SUCCESS && result != ISC_R_NOMORE)
174		goto free_rdatas;
175	for (i = 0; i < nalloc && result == ISC_R_SUCCESS; i++) {
176		INSIST(result == ISC_R_SUCCESS);
177		dns_rdata_init(&x[i].rdata);
178		dns_rdataset_current(rdataset, &x[i].rdata);
179		INSIST(x[i].rdata.data != &removed);
180#if DNS_RDATASET_FIXED
181		x[i].order = i;
182#endif
183		result = dns_rdataset_next(rdataset);
184	}
185	if (result != ISC_R_NOMORE)
186		goto free_rdatas;
187	if (i != nalloc) {
188		/*
189		 * Somehow we iterated over fewer rdatas than
190		 * dns_rdataset_count() said there were!
191		 */
192		result = ISC_R_FAILURE;
193		goto free_rdatas;
194	}
195
196	/*
197	 * Put into DNSSEC order.
198	 */
199	qsort(x, nalloc, sizeof(struct xrdata), compare_rdata);
200
201	/*
202	 * Remove duplicates and compute the total storage required.
203	 *
204	 * If an rdata is not a duplicate, accumulate the storage size
205	 * required for the rdata.  We do not store the class, type, etc,
206	 * just the rdata, so our overhead is 2 bytes for the number of
207	 * records, and 8 for each rdata, (length(2), offset(4) and order(2))
208	 * and then the rdata itself.
209	 */
210	for (i = 1; i < nalloc; i++) {
211		if (compare_rdata(&x[i-1].rdata, &x[i].rdata) == 0) {
212			x[i-1].rdata.data = &removed;
213#if DNS_RDATASET_FIXED
214			/*
215			 * Preserve the least order so A, B, A -> A, B
216			 * after duplicate removal.
217			 */
218			if (x[i-1].order < x[i].order)
219				x[i].order = x[i-1].order;
220#endif
221			nitems--;
222		} else {
223#if DNS_RDATASET_FIXED
224			buflen += (8 + x[i-1].rdata.length);
225#else
226			buflen += (2 + x[i-1].rdata.length);
227#endif
228			/*
229			 * Provide space to store the per RR meta data.
230			 */
231			if (rdataset->type == dns_rdatatype_rrsig)
232				buflen++;
233		}
234	}
235	/*
236	 * Don't forget the last item!
237	 */
238	if (nalloc != 0) {
239#if DNS_RDATASET_FIXED
240		buflen += (8 + x[i-1].rdata.length);
241#else
242		buflen += (2 + x[i-1].rdata.length);
243#endif
244	}
245
246	/*
247	 * Provide space to store the per RR meta data.
248	 */
249	if (rdataset->type == dns_rdatatype_rrsig)
250		buflen++;
251
252	/*
253	 * Ensure that singleton types are actually singletons.
254	 */
255	if (nitems > 1 && dns_rdatatype_issingleton(rdataset->type)) {
256		/*
257		 * We have a singleton type, but there's more than one
258		 * RR in the rdataset.
259		 */
260		result = DNS_R_SINGLETON;
261		goto free_rdatas;
262	}
263
264	/*
265	 * Allocate the memory, set up a buffer, start copying in
266	 * data.
267	 */
268	rawbuf = isc_mem_get(mctx, buflen);
269	if (rawbuf == NULL) {
270		result = ISC_R_NOMEMORY;
271		goto free_rdatas;
272	}
273
274#if DNS_RDATASET_FIXED
275	/* Allocate temporary offset table. */
276	offsettable = isc_mem_get(mctx, nalloc * sizeof(unsigned int));
277	if (offsettable == NULL) {
278		isc_mem_put(mctx, rawbuf, buflen);
279		result = ISC_R_NOMEMORY;
280		goto free_rdatas;
281	}
282	memset(offsettable, 0, nalloc * sizeof(unsigned int));
283#endif
284
285	region->base = rawbuf;
286	region->length = buflen;
287
288	rawbuf += reservelen;
289#if DNS_RDATASET_FIXED
290	offsetbase = rawbuf;
291#endif
292
293	*rawbuf++ = (nitems & 0xff00) >> 8;
294	*rawbuf++ = (nitems & 0x00ff);
295
296#if DNS_RDATASET_FIXED
297	/* Skip load order table.  Filled in later. */
298	rawbuf += nitems * 4;
299#endif
300
301	for (i = 0; i < nalloc; i++) {
302		if (x[i].rdata.data == &removed)
303			continue;
304#if DNS_RDATASET_FIXED
305		offsettable[x[i].order] = rawbuf - offsetbase;
306#endif
307		length = x[i].rdata.length;
308		if (rdataset->type == dns_rdatatype_rrsig)
309			length++;
310		INSIST(length <= 0xffff);
311		*rawbuf++ = (length & 0xff00) >> 8;
312		*rawbuf++ = (length & 0x00ff);
313#if DNS_RDATASET_FIXED
314		rawbuf += 2;	/* filled in later */
315#endif
316		/*
317		 * Store the per RR meta data.
318		 */
319		if (rdataset->type == dns_rdatatype_rrsig) {
320			*rawbuf++ |= (x[i].rdata.flags & DNS_RDATA_OFFLINE) ?
321					    DNS_RDATASLAB_OFFLINE : 0;
322		}
323		memcpy(rawbuf, x[i].rdata.data, x[i].rdata.length);
324		rawbuf += x[i].rdata.length;
325	}
326
327#if DNS_RDATASET_FIXED
328	fillin_offsets(offsetbase, offsettable, nalloc);
329	isc_mem_put(mctx, offsettable, nalloc * sizeof(unsigned int));
330#endif
331
332	result = ISC_R_SUCCESS;
333
334 free_rdatas:
335	if (x != NULL)
336		isc_mem_put(mctx, x, nalloc * sizeof(struct xrdata));
337	return (result);
338}
339
340static void
341rdataset_disassociate(dns_rdataset_t *rdataset) {
342	UNUSED(rdataset);
343}
344
345static isc_result_t
346rdataset_first(dns_rdataset_t *rdataset) {
347	unsigned char *raw = rdataset->private3;
348	unsigned int count;
349
350	count = raw[0] * 256 + raw[1];
351	if (count == 0) {
352		rdataset->private5 = NULL;
353		return (ISC_R_NOMORE);
354	}
355#if DNS_RDATASET_FIXED
356	raw += 2 + (4 * count);
357#else
358	raw += 2;
359#endif
360	/*
361	 * The privateuint4 field is the number of rdata beyond the cursor
362	 * position, so we decrement the total count by one before storing
363	 * it.
364	 */
365	count--;
366	rdataset->privateuint4 = count;
367	rdataset->private5 = raw;
368
369	return (ISC_R_SUCCESS);
370}
371
372static isc_result_t
373rdataset_next(dns_rdataset_t *rdataset) {
374	unsigned int count;
375	unsigned int length;
376	unsigned char *raw;
377
378	count = rdataset->privateuint4;
379	if (count == 0)
380		return (ISC_R_NOMORE);
381	count--;
382	rdataset->privateuint4 = count;
383	raw = rdataset->private5;
384	length = raw[0] * 256 + raw[1];
385#if DNS_RDATASET_FIXED
386	raw += length + 4;
387#else
388	raw += length + 2;
389#endif
390	rdataset->private5 = raw;
391
392	return (ISC_R_SUCCESS);
393}
394
395static void
396rdataset_current(dns_rdataset_t *rdataset, dns_rdata_t *rdata) {
397	unsigned char *raw = rdataset->private5;
398	isc_region_t r;
399	unsigned int length;
400	unsigned int flags = 0;
401
402	REQUIRE(raw != NULL);
403
404	length = raw[0] * 256 + raw[1];
405#if DNS_RDATASET_FIXED
406	raw += 4;
407#else
408	raw += 2;
409#endif
410	if (rdataset->type == dns_rdatatype_rrsig) {
411		if (*raw & DNS_RDATASLAB_OFFLINE)
412			flags |= DNS_RDATA_OFFLINE;
413		length--;
414		raw++;
415	}
416	r.length = length;
417	r.base = raw;
418	dns_rdata_fromregion(rdata, rdataset->rdclass, rdataset->type, &r);
419	rdata->flags |= flags;
420}
421
422static void
423rdataset_clone(dns_rdataset_t *source, dns_rdataset_t *target) {
424	*target = *source;
425
426	/*
427	 * Reset iterator state.
428	 */
429	target->privateuint4 = 0;
430	target->private5 = NULL;
431}
432
433static unsigned int
434rdataset_count(dns_rdataset_t *rdataset) {
435	unsigned char *raw = rdataset->private3;
436	unsigned int count;
437
438	count = raw[0] * 256 + raw[1];
439
440	return (count);
441}
442
443static dns_rdatasetmethods_t rdataset_methods = {
444	rdataset_disassociate,
445	rdataset_first,
446	rdataset_next,
447	rdataset_current,
448	rdataset_clone,
449	rdataset_count,
450	NULL,
451	NULL,
452	NULL,
453	NULL,
454	NULL,
455	NULL,
456	NULL,
457	NULL,
458	NULL
459};
460
461void
462dns_rdataslab_tordataset(unsigned char *slab, unsigned int reservelen,
463			 dns_rdataclass_t rdclass, dns_rdatatype_t rdtype,
464			 dns_rdatatype_t covers, dns_ttl_t ttl,
465			 dns_rdataset_t *rdataset)
466{
467	REQUIRE(slab != NULL);
468	REQUIRE(!dns_rdataset_isassociated(rdataset));
469
470	rdataset->methods = &rdataset_methods;
471	rdataset->rdclass = rdclass;
472	rdataset->type = rdtype;
473	rdataset->covers = covers;
474	rdataset->ttl = ttl;
475	rdataset->trust = 0;
476	rdataset->private1 = NULL;
477	rdataset->private2 = NULL;
478	rdataset->private3 = slab + reservelen;
479
480	/*
481	 * Reset iterator state.
482	 */
483	rdataset->privateuint4 = 0;
484	rdataset->private5 = NULL;
485}
486
487unsigned int
488dns_rdataslab_size(unsigned char *slab, unsigned int reservelen) {
489	unsigned int count, length;
490	unsigned char *current;
491
492	REQUIRE(slab != NULL);
493
494	current = slab + reservelen;
495	count = *current++ * 256;
496	count += *current++;
497#if DNS_RDATASET_FIXED
498	current += (4 * count);
499#endif
500	while (count > 0) {
501		count--;
502		length = *current++ * 256;
503		length += *current++;
504#if DNS_RDATASET_FIXED
505		current += length + 2;
506#else
507		current += length;
508#endif
509	}
510
511	return ((unsigned int)(current - slab));
512}
513
514/*
515 * Make the dns_rdata_t 'rdata' refer to the slab item
516 * beginning at '*current', which is part of a slab of type
517 * 'type' and class 'rdclass', and advance '*current' to
518 * point to the next item in the slab.
519 */
520static inline void
521rdata_from_slab(unsigned char **current,
522	      dns_rdataclass_t rdclass, dns_rdatatype_t type,
523	      dns_rdata_t *rdata)
524{
525	unsigned char *tcurrent = *current;
526	isc_region_t region;
527	unsigned int length;
528	isc_boolean_t offline = ISC_FALSE;
529
530	length = *tcurrent++ * 256;
531	length += *tcurrent++;
532
533	if (type == dns_rdatatype_rrsig) {
534		if ((*tcurrent & DNS_RDATASLAB_OFFLINE) != 0)
535			offline = ISC_TRUE;
536		length--;
537		tcurrent++;
538	}
539	region.length = length;
540#if DNS_RDATASET_FIXED
541	tcurrent += 2;
542#endif
543	region.base = tcurrent;
544	tcurrent += region.length;
545	dns_rdata_fromregion(rdata, rdclass, type, &region);
546	if (offline)
547		rdata->flags |= DNS_RDATA_OFFLINE;
548	*current = tcurrent;
549}
550
551/*
552 * Return true iff 'slab' (slab data of type 'type' and class 'rdclass')
553 * contains an rdata identical to 'rdata'.  This does case insensitive
554 * comparisons per DNSSEC.
555 */
556static inline isc_boolean_t
557rdata_in_slab(unsigned char *slab, unsigned int reservelen,
558	      dns_rdataclass_t rdclass, dns_rdatatype_t type,
559	      dns_rdata_t *rdata)
560{
561	unsigned int count, i;
562	unsigned char *current;
563	dns_rdata_t trdata = DNS_RDATA_INIT;
564	int n;
565
566	current = slab + reservelen;
567	count = *current++ * 256;
568	count += *current++;
569
570#if DNS_RDATASET_FIXED
571	current += (4 * count);
572#endif
573
574	for (i = 0; i < count; i++) {
575		rdata_from_slab(&current, rdclass, type, &trdata);
576
577		n = dns_rdata_compare(&trdata, rdata);
578		if (n == 0)
579			return (ISC_TRUE);
580		if (n > 0)	/* In DNSSEC order. */
581			break;
582		dns_rdata_reset(&trdata);
583	}
584	return (ISC_FALSE);
585}
586
587isc_result_t
588dns_rdataslab_merge(unsigned char *oslab, unsigned char *nslab,
589		    unsigned int reservelen, isc_mem_t *mctx,
590		    dns_rdataclass_t rdclass, dns_rdatatype_t type,
591		    unsigned int flags, unsigned char **tslabp)
592{
593	unsigned char *ocurrent, *ostart, *ncurrent, *tstart, *tcurrent, *data;
594	unsigned int ocount, ncount, count, olength, tlength, tcount, length;
595	dns_rdata_t ordata = DNS_RDATA_INIT;
596	dns_rdata_t nrdata = DNS_RDATA_INIT;
597	isc_boolean_t added_something = ISC_FALSE;
598	unsigned int oadded = 0;
599	unsigned int nadded = 0;
600	unsigned int nncount = 0;
601#if DNS_RDATASET_FIXED
602	unsigned int oncount;
603	unsigned int norder = 0;
604	unsigned int oorder = 0;
605	unsigned char *offsetbase;
606	unsigned int *offsettable;
607#endif
608
609	/*
610	 * XXX  Need parameter to allow "delete rdatasets in nslab" merge,
611	 * or perhaps another merge routine for this purpose.
612	 */
613
614	REQUIRE(tslabp != NULL && *tslabp == NULL);
615	REQUIRE(oslab != NULL && nslab != NULL);
616
617	ocurrent = oslab + reservelen;
618	ocount = *ocurrent++ * 256;
619	ocount += *ocurrent++;
620#if DNS_RDATASET_FIXED
621	ocurrent += (4 * ocount);
622#endif
623	ostart = ocurrent;
624	ncurrent = nslab + reservelen;
625	ncount = *ncurrent++ * 256;
626	ncount += *ncurrent++;
627#if DNS_RDATASET_FIXED
628	ncurrent += (4 * ncount);
629#endif
630	INSIST(ocount > 0 && ncount > 0);
631
632#if DNS_RDATASET_FIXED
633	oncount = ncount;
634#endif
635
636	/*
637	 * Yes, this is inefficient!
638	 */
639
640	/*
641	 * Figure out the length of the old slab's data.
642	 */
643	olength = 0;
644	for (count = 0; count < ocount; count++) {
645		length = *ocurrent++ * 256;
646		length += *ocurrent++;
647#if DNS_RDATASET_FIXED
648		olength += length + 8;
649		ocurrent += length + 2;
650#else
651		olength += length + 2;
652		ocurrent += length;
653#endif
654	}
655
656	/*
657	 * Start figuring out the target length and count.
658	 */
659	tlength = reservelen + 2 + olength;
660	tcount = ocount;
661
662	/*
663	 * Add in the length of rdata in the new slab that aren't in
664	 * the old slab.
665	 */
666	do {
667		dns_rdata_init(&nrdata);
668		rdata_from_slab(&ncurrent, rdclass, type, &nrdata);
669		if (!rdata_in_slab(oslab, reservelen, rdclass, type, &nrdata))
670		{
671			/*
672			 * This rdata isn't in the old slab.
673			 */
674#if DNS_RDATASET_FIXED
675			tlength += nrdata.length + 8;
676#else
677			tlength += nrdata.length + 2;
678#endif
679			if (type == dns_rdatatype_rrsig)
680				tlength++;
681			tcount++;
682			nncount++;
683			added_something = ISC_TRUE;
684		}
685		ncount--;
686	} while (ncount > 0);
687	ncount = nncount;
688
689	if (((flags & DNS_RDATASLAB_EXACT) != 0) &&
690	    (tcount != ncount + ocount))
691		return (DNS_R_NOTEXACT);
692
693	if (!added_something && (flags & DNS_RDATASLAB_FORCE) == 0)
694		return (DNS_R_UNCHANGED);
695
696	/*
697	 * Ensure that singleton types are actually singletons.
698	 */
699	if (tcount > 1 && dns_rdatatype_issingleton(type)) {
700		/*
701		 * We have a singleton type, but there's more than one
702		 * RR in the rdataset.
703		 */
704		return (DNS_R_SINGLETON);
705	}
706
707	if (tcount > 0xffff)
708		return (ISC_R_NOSPACE);
709
710	/*
711	 * Copy the reserved area from the new slab.
712	 */
713	tstart = isc_mem_get(mctx, tlength);
714	if (tstart == NULL)
715		return (ISC_R_NOMEMORY);
716	memcpy(tstart, nslab, reservelen);
717	tcurrent = tstart + reservelen;
718#if DNS_RDATASET_FIXED
719	offsetbase = tcurrent;
720#endif
721
722	/*
723	 * Write the new count.
724	 */
725	*tcurrent++ = (tcount & 0xff00) >> 8;
726	*tcurrent++ = (tcount & 0x00ff);
727
728#if DNS_RDATASET_FIXED
729	/*
730	 * Skip offset table.
731	 */
732	tcurrent += (tcount * 4);
733
734	offsettable = isc_mem_get(mctx,
735				  (ocount + oncount) * sizeof(unsigned int));
736	if (offsettable == NULL) {
737		isc_mem_put(mctx, tstart, tlength);
738		return (ISC_R_NOMEMORY);
739	}
740	memset(offsettable, 0, (ocount + oncount) * sizeof(unsigned int));
741#endif
742
743	/*
744	 * Merge the two slabs.
745	 */
746	ocurrent = ostart;
747	INSIST(ocount != 0);
748#if DNS_RDATASET_FIXED
749	oorder = ocurrent[2] * 256 + ocurrent[3];
750	INSIST(oorder < ocount);
751#endif
752	rdata_from_slab(&ocurrent, rdclass, type, &ordata);
753
754	ncurrent = nslab + reservelen + 2;
755#if DNS_RDATASET_FIXED
756	ncurrent += (4 * oncount);
757#endif
758
759	if (ncount > 0) {
760		do {
761			dns_rdata_reset(&nrdata);
762#if DNS_RDATASET_FIXED
763			norder = ncurrent[2] * 256 + ncurrent[3];
764
765			INSIST(norder < oncount);
766#endif
767			rdata_from_slab(&ncurrent, rdclass, type, &nrdata);
768		} while (rdata_in_slab(oslab, reservelen, rdclass,
769				       type, &nrdata));
770	}
771
772	while (oadded < ocount || nadded < ncount) {
773		isc_boolean_t fromold;
774		if (oadded == ocount)
775			fromold = ISC_FALSE;
776		else if (nadded == ncount)
777			fromold = ISC_TRUE;
778		else
779			fromold = ISC_TF(compare_rdata(&ordata, &nrdata) < 0);
780		if (fromold) {
781#if DNS_RDATASET_FIXED
782			offsettable[oorder] = tcurrent - offsetbase;
783#endif
784			length = ordata.length;
785			data = ordata.data;
786			if (type == dns_rdatatype_rrsig) {
787				length++;
788				data--;
789			}
790			*tcurrent++ = (length & 0xff00) >> 8;
791			*tcurrent++ = (length & 0x00ff);
792#if DNS_RDATASET_FIXED
793			tcurrent += 2;	/* fill in later */
794#endif
795			memcpy(tcurrent, data, length);
796			tcurrent += length;
797			oadded++;
798			if (oadded < ocount) {
799				dns_rdata_reset(&ordata);
800#if DNS_RDATASET_FIXED
801				oorder = ocurrent[2] * 256 + ocurrent[3];
802				INSIST(oorder < ocount);
803#endif
804				rdata_from_slab(&ocurrent, rdclass, type,
805						&ordata);
806			}
807		} else {
808#if DNS_RDATASET_FIXED
809			offsettable[ocount + norder] = tcurrent - offsetbase;
810#endif
811			length = nrdata.length;
812			data = nrdata.data;
813			if (type == dns_rdatatype_rrsig) {
814				length++;
815				data--;
816			}
817			*tcurrent++ = (length & 0xff00) >> 8;
818			*tcurrent++ = (length & 0x00ff);
819#if DNS_RDATASET_FIXED
820			tcurrent += 2;	/* fill in later */
821#endif
822			memcpy(tcurrent, data, length);
823			tcurrent += length;
824			nadded++;
825			if (nadded < ncount) {
826				do {
827					dns_rdata_reset(&nrdata);
828#if DNS_RDATASET_FIXED
829					norder = ncurrent[2] * 256 + ncurrent[3];
830					INSIST(norder < oncount);
831#endif
832					rdata_from_slab(&ncurrent, rdclass,
833							type, &nrdata);
834				} while (rdata_in_slab(oslab, reservelen,
835						       rdclass, type,
836						       &nrdata));
837			}
838		}
839	}
840
841#if DNS_RDATASET_FIXED
842	fillin_offsets(offsetbase, offsettable, ocount + oncount);
843
844	isc_mem_put(mctx, offsettable,
845		    (ocount + oncount) * sizeof(unsigned int));
846#endif
847
848	INSIST(tcurrent == tstart + tlength);
849
850	*tslabp = tstart;
851
852	return (ISC_R_SUCCESS);
853}
854
855isc_result_t
856dns_rdataslab_subtract(unsigned char *mslab, unsigned char *sslab,
857		       unsigned int reservelen, isc_mem_t *mctx,
858		       dns_rdataclass_t rdclass, dns_rdatatype_t type,
859		       unsigned int flags, unsigned char **tslabp)
860{
861	unsigned char *mcurrent, *sstart, *scurrent, *tstart, *tcurrent;
862	unsigned int mcount, scount, rcount ,count, tlength, tcount, i;
863	dns_rdata_t srdata = DNS_RDATA_INIT;
864	dns_rdata_t mrdata = DNS_RDATA_INIT;
865#if DNS_RDATASET_FIXED
866	unsigned char *offsetbase;
867	unsigned int *offsettable;
868	unsigned int order;
869#endif
870
871	REQUIRE(tslabp != NULL && *tslabp == NULL);
872	REQUIRE(mslab != NULL && sslab != NULL);
873
874	mcurrent = mslab + reservelen;
875	mcount = *mcurrent++ * 256;
876	mcount += *mcurrent++;
877	scurrent = sslab + reservelen;
878	scount = *scurrent++ * 256;
879	scount += *scurrent++;
880	INSIST(mcount > 0 && scount > 0);
881
882	/*
883	 * Yes, this is inefficient!
884	 */
885
886	/*
887	 * Start figuring out the target length and count.
888	 */
889	tlength = reservelen + 2;
890	tcount = 0;
891	rcount = 0;
892
893#if DNS_RDATASET_FIXED
894	mcurrent += 4 * mcount;
895	scurrent += 4 * scount;
896#endif
897	sstart = scurrent;
898
899	/*
900	 * Add in the length of rdata in the mslab that aren't in
901	 * the sslab.
902	 */
903	for (i = 0; i < mcount; i++) {
904		unsigned char *mrdatabegin = mcurrent;
905		rdata_from_slab(&mcurrent, rdclass, type, &mrdata);
906		scurrent = sstart;
907		for (count = 0; count < scount; count++) {
908			dns_rdata_reset(&srdata);
909			rdata_from_slab(&scurrent, rdclass, type, &srdata);
910			if (dns_rdata_compare(&mrdata, &srdata) == 0)
911				break;
912		}
913		if (count == scount) {
914			/*
915			 * This rdata isn't in the sslab, and thus isn't
916			 * being subtracted.
917			 */
918			tlength += mcurrent - mrdatabegin;
919			tcount++;
920		} else
921			rcount++;
922		dns_rdata_reset(&mrdata);
923	}
924
925#if DNS_RDATASET_FIXED
926	tlength += (4 * tcount);
927#endif
928
929	/*
930	 * Check that all the records originally existed.  The numeric
931	 * check only works as rdataslabs do not contain duplicates.
932	 */
933	if (((flags & DNS_RDATASLAB_EXACT) != 0) && (rcount != scount))
934		return (DNS_R_NOTEXACT);
935
936	/*
937	 * Don't continue if the new rdataslab would be empty.
938	 */
939	if (tcount == 0)
940		return (DNS_R_NXRRSET);
941
942	/*
943	 * If nothing is going to change, we can stop.
944	 */
945	if (rcount == 0)
946		return (DNS_R_UNCHANGED);
947
948	/*
949	 * Copy the reserved area from the mslab.
950	 */
951	tstart = isc_mem_get(mctx, tlength);
952	if (tstart == NULL)
953		return (ISC_R_NOMEMORY);
954	memcpy(tstart, mslab, reservelen);
955	tcurrent = tstart + reservelen;
956#if DNS_RDATASET_FIXED
957	offsetbase = tcurrent;
958
959	offsettable = isc_mem_get(mctx, mcount * sizeof(unsigned int));
960	if (offsettable == NULL) {
961		isc_mem_put(mctx, tstart, tlength);
962		return (ISC_R_NOMEMORY);
963	}
964	memset(offsettable, 0, mcount * sizeof(unsigned int));
965#endif
966
967	/*
968	 * Write the new count.
969	 */
970	*tcurrent++ = (tcount & 0xff00) >> 8;
971	*tcurrent++ = (tcount & 0x00ff);
972
973#if DNS_RDATASET_FIXED
974	tcurrent += (4 * tcount);
975#endif
976
977	/*
978	 * Copy the parts of mslab not in sslab.
979	 */
980	mcurrent = mslab + reservelen;
981	mcount = *mcurrent++ * 256;
982	mcount += *mcurrent++;
983#if DNS_RDATASET_FIXED
984	mcurrent += (4 * mcount);
985#endif
986	for (i = 0; i < mcount; i++) {
987		unsigned char *mrdatabegin = mcurrent;
988#if DNS_RDATASET_FIXED
989		order = mcurrent[2] * 256 + mcurrent[3];
990		INSIST(order < mcount);
991#endif
992		rdata_from_slab(&mcurrent, rdclass, type, &mrdata);
993		scurrent = sstart;
994		for (count = 0; count < scount; count++) {
995			dns_rdata_reset(&srdata);
996			rdata_from_slab(&scurrent, rdclass, type, &srdata);
997			if (dns_rdata_compare(&mrdata, &srdata) == 0)
998				break;
999		}
1000		if (count == scount) {
1001			/*
1002			 * This rdata isn't in the sslab, and thus should be
1003			 * copied to the tslab.
1004			 */
1005			unsigned int length = mcurrent - mrdatabegin;
1006#if DNS_RDATASET_FIXED
1007			offsettable[order] = tcurrent - offsetbase;
1008#endif
1009			memcpy(tcurrent, mrdatabegin, length);
1010			tcurrent += length;
1011		}
1012		dns_rdata_reset(&mrdata);
1013	}
1014
1015#if DNS_RDATASET_FIXED
1016	fillin_offsets(offsetbase, offsettable, mcount);
1017
1018	isc_mem_put(mctx, offsettable, mcount * sizeof(unsigned int));
1019#endif
1020
1021	INSIST(tcurrent == tstart + tlength);
1022
1023	*tslabp = tstart;
1024
1025	return (ISC_R_SUCCESS);
1026}
1027
1028isc_boolean_t
1029dns_rdataslab_equal(unsigned char *slab1, unsigned char *slab2,
1030		    unsigned int reservelen)
1031{
1032	unsigned char *current1, *current2;
1033	unsigned int count1, count2;
1034	unsigned int length1, length2;
1035
1036	current1 = slab1 + reservelen;
1037	count1 = *current1++ * 256;
1038	count1 += *current1++;
1039
1040	current2 = slab2 + reservelen;
1041	count2 = *current2++ * 256;
1042	count2 += *current2++;
1043
1044	if (count1 != count2)
1045		return (ISC_FALSE);
1046
1047#if DNS_RDATASET_FIXED
1048	current1 += (4 * count1);
1049	current2 += (4 * count2);
1050#endif
1051
1052	while (count1 > 0) {
1053		length1 = *current1++ * 256;
1054		length1 += *current1++;
1055
1056		length2 = *current2++ * 256;
1057		length2 += *current2++;
1058
1059#if DNS_RDATASET_FIXED
1060		current1 += 2;
1061		current2 += 2;
1062#endif
1063
1064		if (length1 != length2 ||
1065		    memcmp(current1, current2, length1) != 0)
1066			return (ISC_FALSE);
1067
1068		current1 += length1;
1069		current2 += length1;
1070
1071		count1--;
1072	}
1073	return (ISC_TRUE);
1074}
1075
1076isc_boolean_t
1077dns_rdataslab_equalx(unsigned char *slab1, unsigned char *slab2,
1078		     unsigned int reservelen, dns_rdataclass_t rdclass,
1079		     dns_rdatatype_t type)
1080{
1081	unsigned char *current1, *current2;
1082	unsigned int count1, count2;
1083	dns_rdata_t rdata1 = DNS_RDATA_INIT;
1084	dns_rdata_t rdata2 = DNS_RDATA_INIT;
1085
1086	current1 = slab1 + reservelen;
1087	count1 = *current1++ * 256;
1088	count1 += *current1++;
1089
1090	current2 = slab2 + reservelen;
1091	count2 = *current2++ * 256;
1092	count2 += *current2++;
1093
1094	if (count1 != count2)
1095		return (ISC_FALSE);
1096
1097#if DNS_RDATASET_FIXED
1098	current1 += (4 * count1);
1099	current2 += (4 * count2);
1100#endif
1101
1102	while (count1-- > 0) {
1103		rdata_from_slab(&current1, rdclass, type, &rdata1);
1104		rdata_from_slab(&current2, rdclass, type, &rdata2);
1105		if (dns_rdata_compare(&rdata1, &rdata2) != 0)
1106			return (ISC_FALSE);
1107		dns_rdata_reset(&rdata1);
1108		dns_rdata_reset(&rdata2);
1109	}
1110	return (ISC_TRUE);
1111}
1112