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 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 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 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 181 dns_compress_getmethods(dns_compress_t *cctx) { 182 REQUIRE(VALID_CCTX(cctx)); 183 return (cctx->allowed & DNS_COMPRESS_ALL); 184 } 185 186 void 187 dns_compress_disable(dns_compress_t *cctx) { 188 REQUIRE(VALID_CCTX(cctx)); 189 cctx->allowed &= ~DNS_COMPRESS_ENABLED; 190 } 191 192 void 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 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 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 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 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 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 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 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 544 dns_decompress_invalidate(dns_decompress_t *dctx) { 545 REQUIRE(VALID_DCTX(dctx)); 546 547 dctx->magic = 0; 548 } 549 550 void 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 568 dns_decompress_getmethods(dns_decompress_t *dctx) { 569 REQUIRE(VALID_DCTX(dctx)); 570 571 return (dctx->allowed); 572 } 573 574 int 575 dns_decompress_edns(dns_decompress_t *dctx) { 576 REQUIRE(VALID_DCTX(dctx)); 577 578 return (dctx->edns); 579 } 580 581 dns_decompresstype_t 582 dns_decompress_type(dns_decompress_t *dctx) { 583 REQUIRE(VALID_DCTX(dctx)); 584 585 return (dctx->type); 586 } 587