1 /* $NetBSD: compress.c,v 1.8 2023/01/25 21:43:30 christos Exp $ */
2
3 /*
4 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
5 *
6 * SPDX-License-Identifier: MPL-2.0
7 *
8 * This Source Code Form is subject to the terms of the Mozilla Public
9 * License, v. 2.0. If a copy of the MPL was not distributed with this
10 * file, you can obtain one at https://mozilla.org/MPL/2.0/.
11 *
12 * See the COPYRIGHT file distributed with this work for additional
13 * information regarding copyright ownership.
14 */
15
16 /*! \file */
17
18 #define DNS_NAME_USEINLINE 1
19
20 #include <inttypes.h>
21 #include <stdbool.h>
22
23 #include <isc/mem.h>
24 #include <isc/string.h>
25 #include <isc/util.h>
26
27 #include <dns/compress.h>
28 #include <dns/fixedname.h>
29 #include <dns/rbt.h>
30 #include <dns/result.h>
31
32 #define CCTX_MAGIC ISC_MAGIC('C', 'C', 'T', 'X')
33 #define VALID_CCTX(x) ISC_MAGIC_VALID(x, CCTX_MAGIC)
34
35 #define DCTX_MAGIC ISC_MAGIC('D', 'C', 'T', 'X')
36 #define VALID_DCTX(x) ISC_MAGIC_VALID(x, DCTX_MAGIC)
37
38 static unsigned char maptolower[] = {
39 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b,
40 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
41 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 0x21, 0x22, 0x23,
42 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
43 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x3b,
44 0x3c, 0x3d, 0x3e, 0x3f, 0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
45 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73,
46 0x74, 0x75, 0x76, 0x77, 0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
47 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b,
48 0x6c, 0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
49 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83,
50 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
51 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 0x9a, 0x9b,
52 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
53 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 0xb0, 0xb1, 0xb2, 0xb3,
54 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
55 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb,
56 0xcc, 0xcd, 0xce, 0xcf, 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
57 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3,
58 0xe4, 0xe5, 0xe6, 0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
59 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb,
60 0xfc, 0xfd, 0xfe, 0xff
61 };
62
63 /*
64 * The tableindex array below is of size 256, one entry for each
65 * unsigned char value. The tableindex array elements are dependent on
66 * DNS_COMPRESS_TABLESIZE. The table was created using the following
67 * function.
68 *
69 * static void
70 * gentable(unsigned char *table) {
71 * unsigned int i;
72 * const unsigned int left = DNS_COMPRESS_TABLESIZE - 38;
73 * long r;
74 *
75 * for (i = 0; i < 26; i++) {
76 * table['A' + i] = i;
77 * table['a' + i] = i;
78 * }
79 *
80 * for (i = 0; i <= 9; i++)
81 * table['0' + i] = i + 26;
82 *
83 * table['-'] = 36;
84 * table['_'] = 37;
85 *
86 * for (i = 0; i < 256; i++) {
87 * if ((i >= 'a' && i <= 'z') ||
88 * (i >= 'A' && i <= 'Z') ||
89 * (i >= '0' && i <= '9') ||
90 * (i == '-') ||
91 * (i == '_'))
92 * continue;
93 * r = random() % left;
94 * table[i] = 38 + r;
95 * }
96 * }
97 */
98 static unsigned char tableindex[256] = {
99 0x3e, 0x3e, 0x33, 0x2d, 0x30, 0x38, 0x31, 0x3c, 0x2b, 0x33, 0x30, 0x3f,
100 0x2d, 0x3c, 0x36, 0x3a, 0x28, 0x2c, 0x2a, 0x37, 0x3d, 0x34, 0x35, 0x2d,
101 0x39, 0x2b, 0x2f, 0x2c, 0x3b, 0x32, 0x2b, 0x39, 0x30, 0x38, 0x28, 0x3c,
102 0x32, 0x33, 0x39, 0x38, 0x27, 0x2b, 0x39, 0x30, 0x27, 0x24, 0x2f, 0x2b,
103 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 0x21, 0x22, 0x3a, 0x29, 0x36,
104 0x31, 0x3c, 0x35, 0x26, 0x31, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06,
105 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12,
106 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x3e, 0x3b, 0x39, 0x2f, 0x25,
107 0x27, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a,
108 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16,
109 0x17, 0x18, 0x19, 0x36, 0x3b, 0x2f, 0x2f, 0x2e, 0x29, 0x33, 0x2a, 0x36,
110 0x28, 0x3f, 0x2e, 0x29, 0x2c, 0x29, 0x36, 0x2d, 0x32, 0x3d, 0x33, 0x2a,
111 0x2e, 0x2f, 0x3b, 0x30, 0x3d, 0x39, 0x2b, 0x36, 0x2a, 0x2f, 0x2c, 0x26,
112 0x3a, 0x37, 0x30, 0x3d, 0x2a, 0x36, 0x33, 0x2c, 0x38, 0x3d, 0x32, 0x3e,
113 0x26, 0x2a, 0x2c, 0x35, 0x27, 0x39, 0x3b, 0x31, 0x2a, 0x37, 0x3c, 0x27,
114 0x32, 0x29, 0x39, 0x37, 0x34, 0x3f, 0x39, 0x2e, 0x38, 0x2b, 0x2c, 0x3e,
115 0x3b, 0x3b, 0x2d, 0x33, 0x3b, 0x3b, 0x32, 0x3d, 0x3f, 0x3a, 0x34, 0x26,
116 0x35, 0x30, 0x31, 0x39, 0x27, 0x2f, 0x3d, 0x35, 0x35, 0x36, 0x2e, 0x29,
117 0x38, 0x27, 0x34, 0x32, 0x2c, 0x3c, 0x31, 0x28, 0x37, 0x38, 0x37, 0x34,
118 0x33, 0x29, 0x32, 0x34, 0x3f, 0x26, 0x34, 0x34, 0x32, 0x27, 0x30, 0x33,
119 0x33, 0x2d, 0x2b, 0x28, 0x3f, 0x33, 0x2b, 0x39, 0x37, 0x39, 0x2c, 0x3d,
120 0x35, 0x39, 0x27, 0x2f
121 };
122
123 /***
124 *** Compression
125 ***/
126
127 isc_result_t
dns_compress_init(dns_compress_t * cctx,int edns,isc_mem_t * mctx)128 dns_compress_init(dns_compress_t *cctx, int edns, isc_mem_t *mctx) {
129 REQUIRE(cctx != NULL);
130 REQUIRE(mctx != NULL); /* See: rdataset.c:towiresorted(). */
131
132 cctx->edns = edns;
133 cctx->mctx = mctx;
134 cctx->count = 0;
135 cctx->allowed = DNS_COMPRESS_ENABLED;
136 cctx->arena_off = 0;
137
138 memset(&cctx->table[0], 0, sizeof(cctx->table));
139
140 cctx->magic = CCTX_MAGIC;
141
142 return (ISC_R_SUCCESS);
143 }
144
145 void
dns_compress_invalidate(dns_compress_t * cctx)146 dns_compress_invalidate(dns_compress_t *cctx) {
147 dns_compressnode_t *node;
148 unsigned int i;
149
150 REQUIRE(VALID_CCTX(cctx));
151
152 for (i = 0; i < DNS_COMPRESS_TABLESIZE; i++) {
153 while (cctx->table[i] != NULL) {
154 node = cctx->table[i];
155 cctx->table[i] = cctx->table[i]->next;
156 if ((node->offset & 0x8000) != 0) {
157 isc_mem_put(cctx->mctx, node->r.base,
158 node->r.length);
159 }
160 if (node->count < DNS_COMPRESS_INITIALNODES) {
161 continue;
162 }
163 isc_mem_put(cctx->mctx, node, sizeof(*node));
164 }
165 }
166
167 cctx->magic = 0;
168 cctx->allowed = 0;
169 cctx->edns = -1;
170 }
171
172 void
dns_compress_setmethods(dns_compress_t * cctx,unsigned int allowed)173 dns_compress_setmethods(dns_compress_t *cctx, unsigned int allowed) {
174 REQUIRE(VALID_CCTX(cctx));
175
176 cctx->allowed &= ~DNS_COMPRESS_ALL;
177 cctx->allowed |= (allowed & DNS_COMPRESS_ALL);
178 }
179
180 unsigned int
dns_compress_getmethods(dns_compress_t * cctx)181 dns_compress_getmethods(dns_compress_t *cctx) {
182 REQUIRE(VALID_CCTX(cctx));
183 return (cctx->allowed & DNS_COMPRESS_ALL);
184 }
185
186 void
dns_compress_disable(dns_compress_t * cctx)187 dns_compress_disable(dns_compress_t *cctx) {
188 REQUIRE(VALID_CCTX(cctx));
189 cctx->allowed &= ~DNS_COMPRESS_ENABLED;
190 }
191
192 void
dns_compress_setsensitive(dns_compress_t * cctx,bool sensitive)193 dns_compress_setsensitive(dns_compress_t *cctx, bool sensitive) {
194 REQUIRE(VALID_CCTX(cctx));
195
196 if (sensitive) {
197 cctx->allowed |= DNS_COMPRESS_CASESENSITIVE;
198 } else {
199 cctx->allowed &= ~DNS_COMPRESS_CASESENSITIVE;
200 }
201 }
202
203 bool
dns_compress_getsensitive(dns_compress_t * cctx)204 dns_compress_getsensitive(dns_compress_t *cctx) {
205 REQUIRE(VALID_CCTX(cctx));
206
207 return (cctx->allowed & DNS_COMPRESS_CASESENSITIVE);
208 }
209
210 int
dns_compress_getedns(dns_compress_t * cctx)211 dns_compress_getedns(dns_compress_t *cctx) {
212 REQUIRE(VALID_CCTX(cctx));
213 return (cctx->edns);
214 }
215
216 /*
217 * Find the longest match of name in the table.
218 * If match is found return true. prefix, suffix and offset are updated.
219 * If no match is found return false.
220 */
221 bool
dns_compress_findglobal(dns_compress_t * cctx,const dns_name_t * name,dns_name_t * prefix,uint16_t * offset)222 dns_compress_findglobal(dns_compress_t *cctx, const dns_name_t *name,
223 dns_name_t *prefix, uint16_t *offset) {
224 dns_name_t tname;
225 dns_compressnode_t *node = NULL;
226 unsigned int labels, i, n;
227 unsigned int numlabels;
228 unsigned char *p;
229
230 REQUIRE(VALID_CCTX(cctx));
231 REQUIRE(dns_name_isabsolute(name));
232 REQUIRE(offset != NULL);
233
234 if (ISC_UNLIKELY((cctx->allowed & DNS_COMPRESS_ENABLED) == 0)) {
235 return (false);
236 }
237
238 if (cctx->count == 0) {
239 return (false);
240 }
241
242 labels = dns_name_countlabels(name);
243 INSIST(labels > 0);
244
245 dns_name_init(&tname, NULL);
246
247 numlabels = labels > 3U ? 3U : labels;
248 p = name->ndata;
249
250 for (n = 0; n < numlabels - 1; n++) {
251 unsigned char ch, llen;
252 unsigned int firstoffset, length;
253
254 firstoffset = (unsigned int)(p - name->ndata);
255 length = name->length - firstoffset;
256
257 /*
258 * We calculate the table index using the first
259 * character in the first label of the suffix name.
260 */
261 ch = p[1];
262 i = tableindex[ch];
263 if (ISC_LIKELY((cctx->allowed & DNS_COMPRESS_CASESENSITIVE) !=
264 0))
265 {
266 for (node = cctx->table[i]; node != NULL;
267 node = node->next)
268 {
269 if (ISC_UNLIKELY(node->name.length != length)) {
270 continue;
271 }
272
273 if (ISC_LIKELY(memcmp(node->name.ndata, p,
274 length) == 0))
275 {
276 goto found;
277 }
278 }
279 } else {
280 for (node = cctx->table[i]; node != NULL;
281 node = node->next)
282 {
283 unsigned int l, count;
284 unsigned char c;
285 unsigned char *label1, *label2;
286
287 if (ISC_UNLIKELY(node->name.length != length)) {
288 continue;
289 }
290
291 l = labels - n;
292 if (ISC_UNLIKELY(node->name.labels != l)) {
293 continue;
294 }
295
296 label1 = node->name.ndata;
297 label2 = p;
298 while (ISC_LIKELY(l-- > 0)) {
299 count = *label1++;
300 if (count != *label2++) {
301 goto cont1;
302 }
303
304 /* no bitstring support */
305 INSIST(count <= 63);
306
307 /* Loop unrolled for performance */
308 while (ISC_LIKELY(count > 3)) {
309 c = maptolower[label1[0]];
310 if (c != maptolower[label2[0]])
311 {
312 goto cont1;
313 }
314 c = maptolower[label1[1]];
315 if (c != maptolower[label2[1]])
316 {
317 goto cont1;
318 }
319 c = maptolower[label1[2]];
320 if (c != maptolower[label2[2]])
321 {
322 goto cont1;
323 }
324 c = maptolower[label1[3]];
325 if (c != maptolower[label2[3]])
326 {
327 goto cont1;
328 }
329 count -= 4;
330 label1 += 4;
331 label2 += 4;
332 }
333 while (ISC_LIKELY(count-- > 0)) {
334 c = maptolower[*label1++];
335 if (c != maptolower[*label2++])
336 {
337 goto cont1;
338 }
339 }
340 }
341 break;
342 cont1:
343 continue;
344 }
345 }
346
347 if (node != NULL) {
348 break;
349 }
350
351 llen = *p;
352 p += llen + 1;
353 }
354
355 found:
356 /*
357 * If node == NULL, we found no match at all.
358 */
359 if (node == NULL) {
360 return (false);
361 }
362
363 if (n == 0) {
364 dns_name_reset(prefix);
365 } else {
366 dns_name_getlabelsequence(name, 0, n, prefix);
367 }
368
369 *offset = (node->offset & 0x7fff);
370 return (true);
371 }
372
373 static unsigned int
name_length(const dns_name_t * name)374 name_length(const dns_name_t *name) {
375 isc_region_t r;
376 dns_name_toregion(name, &r);
377 return (r.length);
378 }
379
380 void
dns_compress_add(dns_compress_t * cctx,const dns_name_t * name,const dns_name_t * prefix,uint16_t offset)381 dns_compress_add(dns_compress_t *cctx, const dns_name_t *name,
382 const dns_name_t *prefix, uint16_t offset) {
383 dns_name_t tname, xname;
384 unsigned int start;
385 unsigned int n;
386 unsigned int count;
387 unsigned int i;
388 dns_compressnode_t *node;
389 unsigned int length;
390 unsigned int tlength;
391 uint16_t toffset;
392 unsigned char *tmp;
393 isc_region_t r;
394 bool allocated = false;
395
396 REQUIRE(VALID_CCTX(cctx));
397 REQUIRE(dns_name_isabsolute(name));
398
399 if (ISC_UNLIKELY((cctx->allowed & DNS_COMPRESS_ENABLED) == 0)) {
400 return;
401 }
402
403 if (offset >= 0x4000) {
404 return;
405 }
406 dns_name_init(&tname, NULL);
407 dns_name_init(&xname, NULL);
408
409 n = dns_name_countlabels(name);
410 count = dns_name_countlabels(prefix);
411 if (dns_name_isabsolute(prefix)) {
412 count--;
413 }
414 if (count == 0) {
415 return;
416 }
417 start = 0;
418 dns_name_toregion(name, &r);
419 length = r.length;
420 if (cctx->arena_off + length < DNS_COMPRESS_ARENA_SIZE) {
421 tmp = &cctx->arena[cctx->arena_off];
422 cctx->arena_off += length;
423 } else {
424 allocated = true;
425 tmp = isc_mem_get(cctx->mctx, length);
426 }
427 /*
428 * Copy name data to 'tmp' and make 'r' use 'tmp'.
429 */
430 memmove(tmp, r.base, r.length);
431 r.base = tmp;
432 dns_name_fromregion(&xname, &r);
433
434 if (count > 2U) {
435 count = 2U;
436 }
437
438 while (count > 0) {
439 unsigned char ch;
440
441 dns_name_getlabelsequence(&xname, start, n, &tname);
442 /*
443 * We calculate the table index using the first
444 * character in the first label of tname.
445 */
446 ch = tname.ndata[1];
447 i = tableindex[ch];
448 tlength = name_length(&tname);
449 toffset = (uint16_t)(offset + (length - tlength));
450 if (toffset >= 0x4000) {
451 break;
452 }
453 /*
454 * Create a new node and add it.
455 */
456 if (cctx->count < DNS_COMPRESS_INITIALNODES) {
457 node = &cctx->initialnodes[cctx->count];
458 } else {
459 node = isc_mem_get(cctx->mctx,
460 sizeof(dns_compressnode_t));
461 }
462 node->count = cctx->count++;
463 /*
464 * 'node->r.base' becomes 'tmp' when start == 0.
465 * Record this by setting 0x8000 so it can be freed later.
466 */
467 if (start == 0 && allocated) {
468 toffset |= 0x8000;
469 }
470 node->offset = toffset;
471 dns_name_toregion(&tname, &node->r);
472 dns_name_init(&node->name, NULL);
473 node->name.length = node->r.length;
474 node->name.ndata = node->r.base;
475 node->name.labels = tname.labels;
476 node->name.attributes = DNS_NAMEATTR_ABSOLUTE;
477 node->next = cctx->table[i];
478 cctx->table[i] = node;
479 start++;
480 n--;
481 count--;
482 }
483
484 if (start == 0) {
485 if (!allocated) {
486 cctx->arena_off -= length;
487 } else {
488 isc_mem_put(cctx->mctx, tmp, length);
489 }
490 }
491 }
492
493 void
dns_compress_rollback(dns_compress_t * cctx,uint16_t offset)494 dns_compress_rollback(dns_compress_t *cctx, uint16_t offset) {
495 unsigned int i;
496 dns_compressnode_t *node;
497
498 REQUIRE(VALID_CCTX(cctx));
499
500 if (ISC_UNLIKELY((cctx->allowed & DNS_COMPRESS_ENABLED) == 0)) {
501 return;
502 }
503
504 for (i = 0; i < DNS_COMPRESS_TABLESIZE; i++) {
505 node = cctx->table[i];
506 /*
507 * This relies on nodes with greater offsets being
508 * closer to the beginning of the list, and the
509 * items with the greatest offsets being at the end
510 * of the initialnodes[] array.
511 */
512 while (node != NULL && (node->offset & 0x7fff) >= offset) {
513 cctx->table[i] = node->next;
514 if ((node->offset & 0x8000) != 0) {
515 isc_mem_put(cctx->mctx, node->r.base,
516 node->r.length);
517 }
518 if (node->count >= DNS_COMPRESS_INITIALNODES) {
519 isc_mem_put(cctx->mctx, node, sizeof(*node));
520 }
521 cctx->count--;
522 node = cctx->table[i];
523 }
524 }
525 }
526
527 /***
528 *** Decompression
529 ***/
530
531 void
dns_decompress_init(dns_decompress_t * dctx,int edns,dns_decompresstype_t type)532 dns_decompress_init(dns_decompress_t *dctx, int edns,
533 dns_decompresstype_t type) {
534 REQUIRE(dctx != NULL);
535 REQUIRE(edns >= -1 && edns <= 255);
536
537 dctx->allowed = DNS_COMPRESS_NONE;
538 dctx->edns = edns;
539 dctx->type = type;
540 dctx->magic = DCTX_MAGIC;
541 }
542
543 void
dns_decompress_invalidate(dns_decompress_t * dctx)544 dns_decompress_invalidate(dns_decompress_t *dctx) {
545 REQUIRE(VALID_DCTX(dctx));
546
547 dctx->magic = 0;
548 }
549
550 void
dns_decompress_setmethods(dns_decompress_t * dctx,unsigned int allowed)551 dns_decompress_setmethods(dns_decompress_t *dctx, unsigned int allowed) {
552 REQUIRE(VALID_DCTX(dctx));
553
554 switch (dctx->type) {
555 case DNS_DECOMPRESS_ANY:
556 dctx->allowed = DNS_COMPRESS_ALL;
557 break;
558 case DNS_DECOMPRESS_NONE:
559 dctx->allowed = DNS_COMPRESS_NONE;
560 break;
561 case DNS_DECOMPRESS_STRICT:
562 dctx->allowed = allowed;
563 break;
564 }
565 }
566
567 unsigned int
dns_decompress_getmethods(dns_decompress_t * dctx)568 dns_decompress_getmethods(dns_decompress_t *dctx) {
569 REQUIRE(VALID_DCTX(dctx));
570
571 return (dctx->allowed);
572 }
573
574 int
dns_decompress_edns(dns_decompress_t * dctx)575 dns_decompress_edns(dns_decompress_t *dctx) {
576 REQUIRE(VALID_DCTX(dctx));
577
578 return (dctx->edns);
579 }
580
581 dns_decompresstype_t
dns_decompress_type(dns_decompress_t * dctx)582 dns_decompress_type(dns_decompress_t *dctx) {
583 REQUIRE(VALID_DCTX(dctx));
584
585 return (dctx->type);
586 }
587