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
dns_compress_init(dns_compress_t * cctx,int edns,isc_mem_t * mctx)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
dns_compress_invalidate(dns_compress_t * cctx)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
dns_compress_setmethods(dns_compress_t * cctx,unsigned int allowed)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
dns_compress_getmethods(dns_compress_t * cctx)94 dns_compress_getmethods(dns_compress_t *cctx) {
95 REQUIRE(VALID_CCTX(cctx));
96 return (cctx->allowed & DNS_COMPRESS_ALL);
97 }
98
99 void
dns_compress_setsensitive(dns_compress_t * cctx,isc_boolean_t sensitive)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
dns_compress_getsensitive(dns_compress_t * cctx)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
dns_compress_getedns(dns_compress_t * cctx)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
dns_compress_findglobal(dns_compress_t * cctx,const dns_name_t * name,dns_name_t * prefix,isc_uint16_t * offset)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
name_length(const dns_name_t * name)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
dns_compress_add(dns_compress_t * cctx,const dns_name_t * name,const dns_name_t * prefix,isc_uint16_t offset)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
dns_compress_rollback(dns_compress_t * cctx,isc_uint16_t offset)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
dns_decompress_init(dns_decompress_t * dctx,int edns,dns_decompresstype_t type)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
dns_decompress_invalidate(dns_decompress_t * dctx)296 dns_decompress_invalidate(dns_decompress_t *dctx) {
297
298 REQUIRE(VALID_DCTX(dctx));
299
300 dctx->magic = 0;
301 }
302
303 void
dns_decompress_setmethods(dns_decompress_t * dctx,unsigned int allowed)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
dns_decompress_getmethods(dns_decompress_t * dctx)322 dns_decompress_getmethods(dns_decompress_t *dctx) {
323
324 REQUIRE(VALID_DCTX(dctx));
325
326 return (dctx->allowed);
327 }
328
329 int
dns_decompress_edns(dns_decompress_t * dctx)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
dns_decompress_type(dns_decompress_t * dctx)338 dns_decompress_type(dns_decompress_t *dctx) {
339
340 REQUIRE(VALID_DCTX(dctx));
341
342 return (dctx->type);
343 }
344