xref: /minix/external/bsd/bind/dist/lib/dns/compress.c (revision fb9c64b2) 
1 /*	$NetBSD: compress.c,v 1.4 2014/12/10 04:37:58 christos Exp $	*/
2 
3 /*
4  * Copyright (C) 2004-2007  Internet Systems Consortium, Inc. ("ISC")
5  * Copyright (C) 1999-2001  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: compress.c,v 1.59 2007/06/19 23:47:16 tbox Exp  */
21 
22 /*! \file */
23 
24 #define DNS_NAME_USEINLINE 1
25 
26 #include <config.h>
27 
28 #include <isc/mem.h>
29 #include <isc/string.h>
30 #include <isc/util.h>
31 
32 #include <dns/compress.h>
33 #include <dns/fixedname.h>
34 #include <dns/rbt.h>
35 #include <dns/result.h>
36 
37 #define CCTX_MAGIC	ISC_MAGIC('C', 'C', 'T', 'X')
38 #define VALID_CCTX(x)	ISC_MAGIC_VALID(x, CCTX_MAGIC)
39 
40 #define DCTX_MAGIC	ISC_MAGIC('D', 'C', 'T', 'X')
41 #define VALID_DCTX(x)	ISC_MAGIC_VALID(x, DCTX_MAGIC)
42 
43 /***
44  ***	Compression
45  ***/
46 
47 isc_result_t
48 dns_compress_init(dns_compress_t *cctx, int edns, isc_mem_t *mctx) {
49 	unsigned int i;
50 
51 	REQUIRE(cctx != NULL);
52 	REQUIRE(mctx != NULL);	/* See: rdataset.c:towiresorted(). */
53 
54 	cctx->allowed = 0;
55 	cctx->edns = edns;
56 	for (i = 0; i < DNS_COMPRESS_TABLESIZE; i++)
57 		cctx->table[i] = NULL;
58 	cctx->mctx = mctx;
59 	cctx->count = 0;
60 	cctx->magic = CCTX_MAGIC;
61 	return (ISC_R_SUCCESS);
62 }
63 
64 void
65 dns_compress_invalidate(dns_compress_t *cctx) {
66 	dns_compressnode_t *node;
67 	unsigned int i;
68 
69 	REQUIRE(VALID_CCTX(cctx));
70 
71 	cctx->magic = 0;
72 	for (i = 0; i < DNS_COMPRESS_TABLESIZE; i++) {
73 		while (cctx->table[i] != NULL) {
74 			node = cctx->table[i];
75 			cctx->table[i] = cctx->table[i]->next;
76 			if (node->count < DNS_COMPRESS_INITIALNODES)
77 				continue;
78 			isc_mem_put(cctx->mctx, node, sizeof(*node));
79 		}
80 	}
81 	cctx->allowed = 0;
82 	cctx->edns = -1;
83 }
84 
85 void
86 dns_compress_setmethods(dns_compress_t *cctx, unsigned int allowed) {
87 	REQUIRE(VALID_CCTX(cctx));
88 
89 	cctx->allowed &= ~DNS_COMPRESS_ALL;
90 	cctx->allowed |= (allowed & DNS_COMPRESS_ALL);
91 }
92 
93 unsigned int
94 dns_compress_getmethods(dns_compress_t *cctx) {
95 	REQUIRE(VALID_CCTX(cctx));
96 	return (cctx->allowed & DNS_COMPRESS_ALL);
97 }
98 
99 void
100 dns_compress_setsensitive(dns_compress_t *cctx, isc_boolean_t sensitive) {
101 	REQUIRE(VALID_CCTX(cctx));
102 
103 	if (sensitive)
104 		cctx->allowed |= DNS_COMPRESS_CASESENSITIVE;
105 	else
106 		cctx->allowed &= ~DNS_COMPRESS_CASESENSITIVE;
107 }
108 
109 isc_boolean_t
110 dns_compress_getsensitive(dns_compress_t *cctx) {
111 	REQUIRE(VALID_CCTX(cctx));
112 
113 	return (ISC_TF((cctx->allowed & DNS_COMPRESS_CASESENSITIVE) != 0));
114 }
115 
116 int
117 dns_compress_getedns(dns_compress_t *cctx) {
118 	REQUIRE(VALID_CCTX(cctx));
119 	return (cctx->edns);
120 }
121 
122 #define NODENAME(node, name) \
123 do { \
124 	(name)->length = (node)->r.length; \
125 	(name)->labels = (node)->labels; \
126 	(name)->ndata = (node)->r.base; \
127 	(name)->attributes = DNS_NAMEATTR_ABSOLUTE; \
128 } while (/*CONSTCOND*/0)
129 
130 /*
131  * Find the longest match of name in the table.
132  * If match is found return ISC_TRUE. prefix, suffix and offset are updated.
133  * If no match is found return ISC_FALSE.
134  */
135 isc_boolean_t
136 dns_compress_findglobal(dns_compress_t *cctx, const dns_name_t *name,
137 			dns_name_t *prefix, isc_uint16_t *offset)
138 {
139 	dns_name_t tname, nname;
140 	dns_compressnode_t *node = NULL;
141 	unsigned int labels, hash, n;
142 
143 	REQUIRE(VALID_CCTX(cctx));
144 	REQUIRE(dns_name_isabsolute(name) == ISC_TRUE);
145 	REQUIRE(offset != NULL);
146 
147 	if (cctx->count == 0)
148 		return (ISC_FALSE);
149 
150 	labels = dns_name_countlabels(name);
151 	INSIST(labels > 0);
152 
153 	dns_name_init(&tname, NULL);
154 	dns_name_init(&nname, NULL);
155 
156 	for (n = 0; n < labels - 1; n++) {
157 		dns_name_getlabelsequence(name, n, labels - n, &tname);
158 		hash = dns_name_hash(&tname, ISC_FALSE) %
159 		       DNS_COMPRESS_TABLESIZE;
160 		for (node = cctx->table[hash]; node != NULL; node = node->next)
161 		{
162 			NODENAME(node, &nname);
163 			if ((cctx->allowed & DNS_COMPRESS_CASESENSITIVE) != 0) {
164 				if (dns_name_caseequal(&nname, &tname))
165 					break;
166 			} else {
167 				if (dns_name_equal(&nname, &tname))
168 					break;
169 			}
170 		}
171 		if (node != NULL)
172 			break;
173 	}
174 
175 	/*
176 	 * If node == NULL, we found no match at all.
177 	 */
178 	if (node == NULL)
179 		return (ISC_FALSE);
180 
181 	if (n == 0)
182 		dns_name_reset(prefix);
183 	else
184 		dns_name_getlabelsequence(name, 0, n, prefix);
185 
186 	*offset = node->offset;
187 	return (ISC_TRUE);
188 }
189 
190 static inline unsigned int
191 name_length(const dns_name_t *name) {
192 	isc_region_t r;
193 	dns_name_toregion(name, &r);
194 	return (r.length);
195 }
196 
197 void
198 dns_compress_add(dns_compress_t *cctx, const dns_name_t *name,
199 		 const dns_name_t *prefix, isc_uint16_t offset)
200 {
201 	dns_name_t tname;
202 	unsigned int start;
203 	unsigned int n;
204 	unsigned int count;
205 	unsigned int hash;
206 	dns_compressnode_t *node;
207 	unsigned int length;
208 	unsigned int tlength;
209 	isc_uint16_t toffset;
210 
211 	REQUIRE(VALID_CCTX(cctx));
212 	REQUIRE(dns_name_isabsolute(name));
213 
214 	dns_name_init(&tname, NULL);
215 
216 	n = dns_name_countlabels(name);
217 	count = dns_name_countlabels(prefix);
218 	if (dns_name_isabsolute(prefix))
219 		count--;
220 	start = 0;
221 	length = name_length(name);
222 	while (count > 0) {
223 		if (offset >= 0x4000)
224 			break;
225 		dns_name_getlabelsequence(name, start, n, &tname);
226 		hash = dns_name_hash(&tname, ISC_FALSE) %
227 		       DNS_COMPRESS_TABLESIZE;
228 		tlength = name_length(&tname);
229 		toffset = (isc_uint16_t)(offset + (length - tlength));
230 		/*
231 		 * Create a new node and add it.
232 		 */
233 		if (cctx->count < DNS_COMPRESS_INITIALNODES)
234 			node = &cctx->initialnodes[cctx->count];
235 		else {
236 			node = isc_mem_get(cctx->mctx,
237 					   sizeof(dns_compressnode_t));
238 			if (node == NULL)
239 				return;
240 		}
241 		node->count = cctx->count++;
242 		node->offset = toffset;
243 		dns_name_toregion(&tname, &node->r);
244 		node->labels = (isc_uint8_t)dns_name_countlabels(&tname);
245 		node->next = cctx->table[hash];
246 		cctx->table[hash] = node;
247 		start++;
248 		n--;
249 		count--;
250 	}
251 }
252 
253 void
254 dns_compress_rollback(dns_compress_t *cctx, isc_uint16_t offset) {
255 	unsigned int i;
256 	dns_compressnode_t *node;
257 
258 	REQUIRE(VALID_CCTX(cctx));
259 
260 	for (i = 0; i < DNS_COMPRESS_TABLESIZE; i++) {
261 		node = cctx->table[i];
262 		/*
263 		 * This relies on nodes with greater offsets being
264 		 * closer to the beginning of the list, and the
265 		 * items with the greatest offsets being at the end
266 		 * of the initialnodes[] array.
267 		 */
268 		while (node != NULL && node->offset >= offset) {
269 			cctx->table[i] = node->next;
270 			if (node->count >= DNS_COMPRESS_INITIALNODES)
271 				isc_mem_put(cctx->mctx, node, sizeof(*node));
272 			cctx->count--;
273 			node = cctx->table[i];
274 		}
275 	}
276 }
277 
278 /***
279  ***	Decompression
280  ***/
281 
282 void
283 dns_decompress_init(dns_decompress_t *dctx, int edns,
284 		    dns_decompresstype_t type) {
285 
286 	REQUIRE(dctx != NULL);
287 	REQUIRE(edns >= -1 && edns <= 255);
288 
289 	dctx->allowed = DNS_COMPRESS_NONE;
290 	dctx->edns = edns;
291 	dctx->type = type;
292 	dctx->magic = DCTX_MAGIC;
293 }
294 
295 void
296 dns_decompress_invalidate(dns_decompress_t *dctx) {
297 
298 	REQUIRE(VALID_DCTX(dctx));
299 
300 	dctx->magic = 0;
301 }
302 
303 void
304 dns_decompress_setmethods(dns_decompress_t *dctx, unsigned int allowed) {
305 
306 	REQUIRE(VALID_DCTX(dctx));
307 
308 	switch (dctx->type) {
309 	case DNS_DECOMPRESS_ANY:
310 		dctx->allowed = DNS_COMPRESS_ALL;
311 		break;
312 	case DNS_DECOMPRESS_NONE:
313 		dctx->allowed = DNS_COMPRESS_NONE;
314 		break;
315 	case DNS_DECOMPRESS_STRICT:
316 		dctx->allowed = allowed;
317 		break;
318 	}
319 }
320 
321 unsigned int
322 dns_decompress_getmethods(dns_decompress_t *dctx) {
323 
324 	REQUIRE(VALID_DCTX(dctx));
325 
326 	return (dctx->allowed);
327 }
328 
329 int
330 dns_decompress_edns(dns_decompress_t *dctx) {
331 
332 	REQUIRE(VALID_DCTX(dctx));
333 
334 	return (dctx->edns);
335 }
336 
337 dns_decompresstype_t
338 dns_decompress_type(dns_decompress_t *dctx) {
339 
340 	REQUIRE(VALID_DCTX(dctx));
341 
342 	return (dctx->type);
343 }
344