1 /* $NetBSD: compress.c,v 1.9 2024/02/21 22:52:06 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/result.h> 25 #include <isc/string.h> 26 #include <isc/util.h> 27 28 #include <dns/compress.h> 29 #include <dns/fixedname.h> 30 #include <dns/rbt.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 ((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 ((cctx->allowed & DNS_COMPRESS_CASESENSITIVE) != 0) { 264 for (node = cctx->table[i]; node != NULL; 265 node = node->next) 266 { 267 if (node->name.length != length) { 268 continue; 269 } 270 271 if (memcmp(node->name.ndata, p, length) == 0) { 272 goto found; 273 } 274 } 275 } else { 276 for (node = cctx->table[i]; node != NULL; 277 node = node->next) 278 { 279 unsigned int l, count; 280 unsigned char c; 281 unsigned char *label1, *label2; 282 283 if (node->name.length != length) { 284 continue; 285 } 286 287 l = labels - n; 288 if (node->name.labels != l) { 289 continue; 290 } 291 292 label1 = node->name.ndata; 293 label2 = p; 294 while (l-- > 0) { 295 count = *label1++; 296 if (count != *label2++) { 297 goto cont1; 298 } 299 300 /* no bitstring support */ 301 INSIST(count <= 63); 302 303 /* Loop unrolled for performance */ 304 while (count > 3) { 305 c = maptolower[label1[0]]; 306 if (c != maptolower[label2[0]]) 307 { 308 goto cont1; 309 } 310 c = maptolower[label1[1]]; 311 if (c != maptolower[label2[1]]) 312 { 313 goto cont1; 314 } 315 c = maptolower[label1[2]]; 316 if (c != maptolower[label2[2]]) 317 { 318 goto cont1; 319 } 320 c = maptolower[label1[3]]; 321 if (c != maptolower[label2[3]]) 322 { 323 goto cont1; 324 } 325 count -= 4; 326 label1 += 4; 327 label2 += 4; 328 } 329 while (count-- > 0) { 330 c = maptolower[*label1++]; 331 if (c != maptolower[*label2++]) 332 { 333 goto cont1; 334 } 335 } 336 } 337 break; 338 cont1: 339 continue; 340 } 341 } 342 343 if (node != NULL) { 344 break; 345 } 346 347 llen = *p; 348 p += llen + 1; 349 } 350 351 found: 352 /* 353 * If node == NULL, we found no match at all. 354 */ 355 if (node == NULL) { 356 return (false); 357 } 358 359 if (n == 0) { 360 dns_name_reset(prefix); 361 } else { 362 dns_name_getlabelsequence(name, 0, n, prefix); 363 } 364 365 *offset = (node->offset & 0x7fff); 366 return (true); 367 } 368 369 static unsigned int 370 name_length(const dns_name_t *name) { 371 isc_region_t r; 372 dns_name_toregion(name, &r); 373 return (r.length); 374 } 375 376 void 377 dns_compress_add(dns_compress_t *cctx, const dns_name_t *name, 378 const dns_name_t *prefix, uint16_t offset) { 379 dns_name_t tname, xname; 380 unsigned int start; 381 unsigned int n; 382 unsigned int count; 383 unsigned int i; 384 dns_compressnode_t *node; 385 unsigned int length; 386 unsigned int tlength; 387 uint16_t toffset; 388 unsigned char *tmp; 389 isc_region_t r; 390 bool allocated = false; 391 392 REQUIRE(VALID_CCTX(cctx)); 393 REQUIRE(dns_name_isabsolute(name)); 394 395 if ((cctx->allowed & DNS_COMPRESS_ENABLED) == 0) { 396 return; 397 } 398 399 if (offset >= 0x4000) { 400 return; 401 } 402 dns_name_init(&tname, NULL); 403 dns_name_init(&xname, NULL); 404 405 n = dns_name_countlabels(name); 406 count = dns_name_countlabels(prefix); 407 if (dns_name_isabsolute(prefix)) { 408 count--; 409 } 410 if (count == 0) { 411 return; 412 } 413 start = 0; 414 dns_name_toregion(name, &r); 415 length = r.length; 416 if (cctx->arena_off + length < DNS_COMPRESS_ARENA_SIZE) { 417 tmp = &cctx->arena[cctx->arena_off]; 418 cctx->arena_off += length; 419 } else { 420 allocated = true; 421 tmp = isc_mem_get(cctx->mctx, length); 422 } 423 /* 424 * Copy name data to 'tmp' and make 'r' use 'tmp'. 425 */ 426 memmove(tmp, r.base, r.length); 427 r.base = tmp; 428 dns_name_fromregion(&xname, &r); 429 430 if (count > 2U) { 431 count = 2U; 432 } 433 434 while (count > 0) { 435 unsigned char ch; 436 437 dns_name_getlabelsequence(&xname, start, n, &tname); 438 /* 439 * We calculate the table index using the first 440 * character in the first label of tname. 441 */ 442 ch = tname.ndata[1]; 443 i = tableindex[ch]; 444 tlength = name_length(&tname); 445 toffset = (uint16_t)(offset + (length - tlength)); 446 if (toffset >= 0x4000) { 447 break; 448 } 449 /* 450 * Create a new node and add it. 451 */ 452 if (cctx->count < DNS_COMPRESS_INITIALNODES) { 453 node = &cctx->initialnodes[cctx->count]; 454 } else { 455 node = isc_mem_get(cctx->mctx, 456 sizeof(dns_compressnode_t)); 457 } 458 node->count = cctx->count++; 459 /* 460 * 'node->r.base' becomes 'tmp' when start == 0. 461 * Record this by setting 0x8000 so it can be freed later. 462 */ 463 if (start == 0 && allocated) { 464 toffset |= 0x8000; 465 } 466 node->offset = toffset; 467 dns_name_toregion(&tname, &node->r); 468 dns_name_init(&node->name, NULL); 469 node->name.length = node->r.length; 470 node->name.ndata = node->r.base; 471 node->name.labels = tname.labels; 472 node->name.attributes = DNS_NAMEATTR_ABSOLUTE; 473 node->next = cctx->table[i]; 474 cctx->table[i] = node; 475 start++; 476 n--; 477 count--; 478 } 479 480 if (start == 0) { 481 if (!allocated) { 482 cctx->arena_off -= length; 483 } else { 484 isc_mem_put(cctx->mctx, tmp, length); 485 } 486 } 487 } 488 489 void 490 dns_compress_rollback(dns_compress_t *cctx, uint16_t offset) { 491 unsigned int i; 492 dns_compressnode_t *node; 493 494 REQUIRE(VALID_CCTX(cctx)); 495 496 if ((cctx->allowed & DNS_COMPRESS_ENABLED) == 0) { 497 return; 498 } 499 500 for (i = 0; i < DNS_COMPRESS_TABLESIZE; i++) { 501 node = cctx->table[i]; 502 /* 503 * This relies on nodes with greater offsets being 504 * closer to the beginning of the list, and the 505 * items with the greatest offsets being at the end 506 * of the initialnodes[] array. 507 */ 508 while (node != NULL && (node->offset & 0x7fff) >= offset) { 509 cctx->table[i] = node->next; 510 if ((node->offset & 0x8000) != 0) { 511 isc_mem_put(cctx->mctx, node->r.base, 512 node->r.length); 513 } 514 if (node->count >= DNS_COMPRESS_INITIALNODES) { 515 isc_mem_put(cctx->mctx, node, sizeof(*node)); 516 } 517 cctx->count--; 518 node = cctx->table[i]; 519 } 520 } 521 } 522 523 /*** 524 *** Decompression 525 ***/ 526 527 void 528 dns_decompress_init(dns_decompress_t *dctx, int edns, 529 dns_decompresstype_t type) { 530 REQUIRE(dctx != NULL); 531 REQUIRE(edns >= -1 && edns <= 255); 532 533 dctx->allowed = DNS_COMPRESS_NONE; 534 dctx->edns = edns; 535 dctx->type = type; 536 dctx->magic = DCTX_MAGIC; 537 } 538 539 void 540 dns_decompress_invalidate(dns_decompress_t *dctx) { 541 REQUIRE(VALID_DCTX(dctx)); 542 543 dctx->magic = 0; 544 } 545 546 void 547 dns_decompress_setmethods(dns_decompress_t *dctx, unsigned int allowed) { 548 REQUIRE(VALID_DCTX(dctx)); 549 550 switch (dctx->type) { 551 case DNS_DECOMPRESS_ANY: 552 dctx->allowed = DNS_COMPRESS_ALL; 553 break; 554 case DNS_DECOMPRESS_NONE: 555 dctx->allowed = DNS_COMPRESS_NONE; 556 break; 557 case DNS_DECOMPRESS_STRICT: 558 dctx->allowed = allowed; 559 break; 560 } 561 } 562 563 unsigned int 564 dns_decompress_getmethods(dns_decompress_t *dctx) { 565 REQUIRE(VALID_DCTX(dctx)); 566 567 return (dctx->allowed); 568 } 569 570 int 571 dns_decompress_edns(dns_decompress_t *dctx) { 572 REQUIRE(VALID_DCTX(dctx)); 573 574 return (dctx->edns); 575 } 576 577 dns_decompresstype_t 578 dns_decompress_type(dns_decompress_t *dctx) { 579 REQUIRE(VALID_DCTX(dctx)); 580 581 return (dctx->type); 582 } 583