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