1 /* 2 * util/data/dname.h - domain name handling 3 * 4 * Copyright (c) 2007, NLnet Labs. All rights reserved. 5 * 6 * This software is open source. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * Redistributions of source code must retain the above copyright notice, 13 * this list of conditions and the following disclaimer. 14 * 15 * Redistributions in binary form must reproduce the above copyright notice, 16 * this list of conditions and the following disclaimer in the documentation 17 * and/or other materials provided with the distribution. 18 * 19 * Neither the name of the NLNET LABS nor the names of its contributors may 20 * be used to endorse or promote products derived from this software without 21 * specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 25 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 26 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE 27 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 28 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 29 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 30 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 31 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 32 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 33 * POSSIBILITY OF SUCH DAMAGE. 34 */ 35 36 /** 37 * \file 38 * 39 * This file contains domain name handling functions. 40 */ 41 42 #include "config.h" 43 #include <ctype.h> 44 #include "util/data/dname.h" 45 #include "util/data/msgparse.h" 46 #include "util/log.h" 47 #include "util/storage/lookup3.h" 48 49 /* determine length of a dname in buffer, no compression pointers allowed */ 50 size_t 51 query_dname_len(ldns_buffer* query) 52 { 53 size_t len = 0; 54 size_t labellen; 55 while(1) { 56 if(ldns_buffer_remaining(query) < 1) 57 return 0; /* parse error, need label len */ 58 labellen = ldns_buffer_read_u8(query); 59 if(labellen&0xc0) 60 return 0; /* no compression allowed in queries */ 61 len += labellen + 1; 62 if(len > LDNS_MAX_DOMAINLEN) 63 return 0; /* too long */ 64 if(labellen == 0) 65 return len; 66 if(ldns_buffer_remaining(query) < labellen) 67 return 0; /* parse error, need content */ 68 ldns_buffer_skip(query, (ssize_t)labellen); 69 } 70 } 71 72 size_t 73 dname_valid(uint8_t* dname, size_t maxlen) 74 { 75 size_t len = 0; 76 size_t labellen; 77 labellen = *dname++; 78 while(labellen) { 79 if(labellen&0xc0) 80 return 0; /* no compression ptrs allowed */ 81 len += labellen + 1; 82 if(len >= LDNS_MAX_DOMAINLEN) 83 return 0; /* too long */ 84 if(len > maxlen) 85 return 0; /* does not fit in memory allocation */ 86 dname += labellen; 87 labellen = *dname++; 88 } 89 len += 1; 90 if(len > maxlen) 91 return 0; /* does not fit in memory allocation */ 92 return len; 93 } 94 95 /** compare uncompressed, noncanonical, registers are hints for speed */ 96 int 97 query_dname_compare(register uint8_t* d1, register uint8_t* d2) 98 { 99 register uint8_t lab1, lab2; 100 log_assert(d1 && d2); 101 lab1 = *d1++; 102 lab2 = *d2++; 103 while( lab1 != 0 || lab2 != 0 ) { 104 /* compare label length */ 105 /* if one dname ends, it has labellength 0 */ 106 if(lab1 != lab2) { 107 if(lab1 < lab2) 108 return -1; 109 return 1; 110 } 111 log_assert(lab1 == lab2 && lab1 != 0); 112 /* compare lowercased labels. */ 113 while(lab1--) { 114 /* compare bytes first for speed */ 115 if(*d1 != *d2 && 116 tolower((int)*d1) != tolower((int)*d2)) { 117 if(tolower((int)*d1) < tolower((int)*d2)) 118 return -1; 119 return 1; 120 } 121 d1++; 122 d2++; 123 } 124 /* next pair of labels. */ 125 lab1 = *d1++; 126 lab2 = *d2++; 127 } 128 return 0; 129 } 130 131 void 132 query_dname_tolower(uint8_t* dname) 133 { 134 /* the dname is stored uncompressed */ 135 uint8_t labellen; 136 labellen = *dname; 137 while(labellen) { 138 dname++; 139 while(labellen--) { 140 *dname = (uint8_t)tolower((int)*dname); 141 dname++; 142 } 143 labellen = *dname; 144 } 145 } 146 147 void 148 pkt_dname_tolower(ldns_buffer* pkt, uint8_t* dname) 149 { 150 uint8_t lablen; 151 int count = 0; 152 if(dname >= ldns_buffer_end(pkt)) 153 return; 154 lablen = *dname++; 155 while(lablen) { 156 if(LABEL_IS_PTR(lablen)) { 157 if((size_t)PTR_OFFSET(lablen, *dname) 158 >= ldns_buffer_limit(pkt)) 159 return; 160 dname = ldns_buffer_at(pkt, PTR_OFFSET(lablen, *dname)); 161 lablen = *dname++; 162 if(count++ > MAX_COMPRESS_PTRS) 163 return; 164 continue; 165 } 166 if(dname+lablen >= ldns_buffer_end(pkt)) 167 return; 168 while(lablen--) { 169 *dname = (uint8_t)tolower((int)*dname); 170 dname++; 171 } 172 if(dname >= ldns_buffer_end(pkt)) 173 return; 174 lablen = *dname++; 175 } 176 } 177 178 179 size_t 180 pkt_dname_len(ldns_buffer* pkt) 181 { 182 size_t len = 0; 183 int ptrcount = 0; 184 uint8_t labellen; 185 size_t endpos = 0; 186 187 /* read dname and determine length */ 188 /* check compression pointers, loops, out of bounds */ 189 while(1) { 190 /* read next label */ 191 if(ldns_buffer_remaining(pkt) < 1) 192 return 0; 193 labellen = ldns_buffer_read_u8(pkt); 194 if(LABEL_IS_PTR(labellen)) { 195 /* compression ptr */ 196 uint16_t ptr; 197 if(ldns_buffer_remaining(pkt) < 1) 198 return 0; 199 ptr = PTR_OFFSET(labellen, ldns_buffer_read_u8(pkt)); 200 if(ptrcount++ > MAX_COMPRESS_PTRS) 201 return 0; /* loop! */ 202 if(ldns_buffer_limit(pkt) <= ptr) 203 return 0; /* out of bounds! */ 204 if(!endpos) 205 endpos = ldns_buffer_position(pkt); 206 ldns_buffer_set_position(pkt, ptr); 207 } else { 208 /* label contents */ 209 if(labellen > 0x3f) 210 return 0; /* label too long */ 211 len += 1 + labellen; 212 if(len > LDNS_MAX_DOMAINLEN) 213 return 0; 214 if(labellen == 0) { 215 /* end of dname */ 216 break; 217 } 218 if(ldns_buffer_remaining(pkt) < labellen) 219 return 0; 220 ldns_buffer_skip(pkt, (ssize_t)labellen); 221 } 222 } 223 if(endpos) 224 ldns_buffer_set_position(pkt, endpos); 225 226 return len; 227 } 228 229 int 230 dname_pkt_compare(ldns_buffer* pkt, uint8_t* d1, uint8_t* d2) 231 { 232 uint8_t len1, len2; 233 log_assert(pkt && d1 && d2); 234 len1 = *d1++; 235 len2 = *d2++; 236 while( len1 != 0 || len2 != 0 ) { 237 /* resolve ptrs */ 238 if(LABEL_IS_PTR(len1)) { 239 d1 = ldns_buffer_at(pkt, PTR_OFFSET(len1, *d1)); 240 len1 = *d1++; 241 continue; 242 } 243 if(LABEL_IS_PTR(len2)) { 244 d2 = ldns_buffer_at(pkt, PTR_OFFSET(len2, *d2)); 245 len2 = *d2++; 246 continue; 247 } 248 /* check label length */ 249 log_assert(len1 <= LDNS_MAX_LABELLEN); 250 log_assert(len2 <= LDNS_MAX_LABELLEN); 251 if(len1 != len2) { 252 if(len1 < len2) return -1; 253 return 1; 254 } 255 log_assert(len1 == len2 && len1 != 0); 256 /* compare labels */ 257 while(len1--) { 258 if(tolower((int)*d1++) != tolower((int)*d2++)) { 259 if(tolower((int)d1[-1]) < tolower((int)d2[-1])) 260 return -1; 261 return 1; 262 } 263 } 264 len1 = *d1++; 265 len2 = *d2++; 266 } 267 return 0; 268 } 269 270 hashvalue_t 271 dname_query_hash(uint8_t* dname, hashvalue_t h) 272 { 273 uint8_t labuf[LDNS_MAX_LABELLEN+1]; 274 uint8_t lablen; 275 int i; 276 277 /* preserve case of query, make hash label by label */ 278 lablen = *dname++; 279 while(lablen) { 280 log_assert(lablen <= LDNS_MAX_LABELLEN); 281 labuf[0] = lablen; 282 i=0; 283 while(lablen--) 284 labuf[++i] = (uint8_t)tolower((int)*dname++); 285 h = hashlittle(labuf, labuf[0] + 1, h); 286 lablen = *dname++; 287 } 288 289 return h; 290 } 291 292 hashvalue_t 293 dname_pkt_hash(ldns_buffer* pkt, uint8_t* dname, hashvalue_t h) 294 { 295 uint8_t labuf[LDNS_MAX_LABELLEN+1]; 296 uint8_t lablen; 297 int i; 298 299 /* preserve case of query, make hash label by label */ 300 lablen = *dname++; 301 while(lablen) { 302 if(LABEL_IS_PTR(lablen)) { 303 /* follow pointer */ 304 dname = ldns_buffer_at(pkt, PTR_OFFSET(lablen, *dname)); 305 lablen = *dname++; 306 continue; 307 } 308 log_assert(lablen <= LDNS_MAX_LABELLEN); 309 labuf[0] = lablen; 310 i=0; 311 while(lablen--) 312 labuf[++i] = (uint8_t)tolower((int)*dname++); 313 h = hashlittle(labuf, labuf[0] + 1, h); 314 lablen = *dname++; 315 } 316 317 return h; 318 } 319 320 void dname_pkt_copy(ldns_buffer* pkt, uint8_t* to, uint8_t* dname) 321 { 322 /* copy over the dname and decompress it at the same time */ 323 size_t len = 0; 324 uint8_t lablen; 325 lablen = *dname++; 326 while(lablen) { 327 if(LABEL_IS_PTR(lablen)) { 328 /* follow pointer */ 329 dname = ldns_buffer_at(pkt, PTR_OFFSET(lablen, *dname)); 330 lablen = *dname++; 331 continue; 332 } 333 log_assert(lablen <= LDNS_MAX_LABELLEN); 334 len += (size_t)lablen+1; 335 if(len >= LDNS_MAX_DOMAINLEN) { 336 *to = 0; /* end the result prematurely */ 337 log_err("bad dname in dname_pkt_copy"); 338 return; 339 } 340 *to++ = lablen; 341 memmove(to, dname, lablen); 342 dname += lablen; 343 to += lablen; 344 lablen = *dname++; 345 } 346 /* copy last \0 */ 347 *to = 0; 348 } 349 350 void dname_print(FILE* out, ldns_buffer* pkt, uint8_t* dname) 351 { 352 uint8_t lablen; 353 if(!out) out = stdout; 354 if(!dname) return; 355 356 lablen = *dname++; 357 if(!lablen) 358 fputc('.', out); 359 while(lablen) { 360 if(LABEL_IS_PTR(lablen)) { 361 /* follow pointer */ 362 if(!pkt) { 363 fputs("??compressionptr??", out); 364 return; 365 } 366 dname = ldns_buffer_at(pkt, PTR_OFFSET(lablen, *dname)); 367 lablen = *dname++; 368 continue; 369 } 370 if(lablen > LDNS_MAX_LABELLEN) { 371 fputs("??extendedlabel??", out); 372 return; 373 } 374 while(lablen--) 375 fputc((int)*dname++, out); 376 fputc('.', out); 377 lablen = *dname++; 378 } 379 } 380 381 int 382 dname_count_labels(uint8_t* dname) 383 { 384 uint8_t lablen; 385 int labs = 1; 386 387 lablen = *dname++; 388 while(lablen) { 389 labs++; 390 dname += lablen; 391 lablen = *dname++; 392 } 393 return labs; 394 } 395 396 int 397 dname_count_size_labels(uint8_t* dname, size_t* size) 398 { 399 uint8_t lablen; 400 int labs = 1; 401 size_t sz = 1; 402 403 lablen = *dname++; 404 while(lablen) { 405 labs++; 406 sz += lablen+1; 407 dname += lablen; 408 lablen = *dname++; 409 } 410 *size = sz; 411 return labs; 412 } 413 414 /** 415 * Compare labels in memory, lowercase while comparing. 416 * @param p1: label 1 417 * @param p2: label 2 418 * @param len: number of bytes to compare. 419 * @return: 0, -1, +1 comparison result. 420 */ 421 static int 422 memlowercmp(uint8_t* p1, uint8_t* p2, uint8_t len) 423 { 424 while(len--) { 425 if(*p1 != *p2 && tolower((int)*p1) != tolower((int)*p2)) { 426 if(tolower((int)*p1) < tolower((int)*p2)) 427 return -1; 428 return 1; 429 } 430 p1++; 431 p2++; 432 } 433 return 0; 434 } 435 436 int 437 dname_lab_cmp(uint8_t* d1, int labs1, uint8_t* d2, int labs2, int* mlabs) 438 { 439 uint8_t len1, len2; 440 int atlabel = labs1; 441 int lastmlabs; 442 int lastdiff = 0; 443 /* first skip so that we compare same label. */ 444 if(labs1 > labs2) { 445 while(atlabel > labs2) { 446 len1 = *d1++; 447 d1 += len1; 448 atlabel--; 449 } 450 log_assert(atlabel == labs2); 451 } else if(labs1 < labs2) { 452 atlabel = labs2; 453 while(atlabel > labs1) { 454 len2 = *d2++; 455 d2 += len2; 456 atlabel--; 457 } 458 log_assert(atlabel == labs1); 459 } 460 lastmlabs = atlabel+1; 461 /* now at same label in d1 and d2, atlabel */ 462 /* www.example.com. */ 463 /* 4 3 2 1 atlabel number */ 464 /* repeat until at root label (which is always the same) */ 465 while(atlabel > 1) { 466 len1 = *d1++; 467 len2 = *d2++; 468 if(len1 != len2) { 469 log_assert(len1 != 0 && len2 != 0); 470 if(len1<len2) 471 lastdiff = -1; 472 else lastdiff = 1; 473 lastmlabs = atlabel; 474 d1 += len1; 475 d2 += len2; 476 } else { 477 /* memlowercmp is inlined here; or just like 478 * if((c=memlowercmp(d1, d2, len1)) != 0) { 479 * lastdiff = c; 480 * lastmlabs = atlabel; } apart from d1++,d2++ */ 481 while(len1) { 482 if(*d1 != *d2 && tolower((int)*d1) 483 != tolower((int)*d2)) { 484 if(tolower((int)*d1) < 485 tolower((int)*d2)) { 486 lastdiff = -1; 487 lastmlabs = atlabel; 488 d1 += len1; 489 d2 += len1; 490 break; 491 } 492 lastdiff = 1; 493 lastmlabs = atlabel; 494 d1 += len1; 495 d2 += len1; 496 break; /* out of memlowercmp */ 497 } 498 d1++; 499 d2++; 500 len1--; 501 } 502 } 503 atlabel--; 504 } 505 /* last difference atlabel number, so number of labels matching, 506 * at the right side, is one less. */ 507 *mlabs = lastmlabs-1; 508 if(lastdiff == 0) { 509 /* all labels compared were equal, check if one has more 510 * labels, so that example.com. > com. */ 511 if(labs1 > labs2) 512 return 1; 513 else if(labs1 < labs2) 514 return -1; 515 } 516 return lastdiff; 517 } 518 519 int 520 dname_buffer_write(ldns_buffer* pkt, uint8_t* dname) 521 { 522 uint8_t lablen; 523 524 if(ldns_buffer_remaining(pkt) < 1) 525 return 0; 526 lablen = *dname++; 527 ldns_buffer_write_u8(pkt, lablen); 528 while(lablen) { 529 if(ldns_buffer_remaining(pkt) < (size_t)lablen+1) 530 return 0; 531 ldns_buffer_write(pkt, dname, lablen); 532 dname += lablen; 533 lablen = *dname++; 534 ldns_buffer_write_u8(pkt, lablen); 535 } 536 return 1; 537 } 538 539 void dname_str(uint8_t* dname, char* str) 540 { 541 size_t len = 0; 542 uint8_t lablen = 0; 543 char* s = str; 544 if(!dname || !*dname) { 545 *s++ = '.'; 546 *s = 0; 547 return; 548 } 549 lablen = *dname++; 550 while(lablen) { 551 if(lablen > LDNS_MAX_LABELLEN) { 552 *s++ = '#'; 553 *s = 0; 554 return; 555 } 556 len += lablen+1; 557 if(len >= LDNS_MAX_DOMAINLEN-1) { 558 *s++ = '&'; 559 *s = 0; 560 return; 561 } 562 while(lablen--) { 563 if(isalnum((int)*dname) 564 || *dname == '-' || *dname == '_' 565 || *dname == '*') 566 *s++ = *(char*)dname++; 567 else { 568 *s++ = '?'; 569 dname++; 570 } 571 } 572 *s++ = '.'; 573 lablen = *dname++; 574 } 575 *s = 0; 576 } 577 578 int 579 dname_strict_subdomain(uint8_t* d1, int labs1, uint8_t* d2, int labs2) 580 { 581 int m; 582 /* check subdomain: d1: www.example.com. and d2: example.com. */ 583 if(labs2 >= labs1) 584 return 0; 585 if(dname_lab_cmp(d1, labs1, d2, labs2, &m) > 0) { 586 /* subdomain if all labels match */ 587 return (m == labs2); 588 } 589 return 0; 590 } 591 592 int 593 dname_strict_subdomain_c(uint8_t* d1, uint8_t* d2) 594 { 595 return dname_strict_subdomain(d1, dname_count_labels(d1), d2, 596 dname_count_labels(d2)); 597 } 598 599 int 600 dname_subdomain_c(uint8_t* d1, uint8_t* d2) 601 { 602 int m; 603 /* check subdomain: d1: www.example.com. and d2: example.com. */ 604 /* or d1: example.com. and d2: example.com. */ 605 int labs1 = dname_count_labels(d1); 606 int labs2 = dname_count_labels(d2); 607 if(labs2 > labs1) 608 return 0; 609 if(dname_lab_cmp(d1, labs1, d2, labs2, &m) < 0) { 610 /* must have been example.com , www.example.com - wrong */ 611 /* or otherwise different dnames */ 612 return 0; 613 } 614 return (m == labs2); 615 } 616 617 int 618 dname_is_root(uint8_t* dname) 619 { 620 uint8_t len; 621 log_assert(dname); 622 len = dname[0]; 623 log_assert(!LABEL_IS_PTR(len)); 624 return (len == 0); 625 } 626 627 void 628 dname_remove_label(uint8_t** dname, size_t* len) 629 { 630 size_t lablen; 631 log_assert(dname && *dname && len); 632 lablen = (*dname)[0]; 633 log_assert(!LABEL_IS_PTR(lablen)); 634 log_assert(*len > lablen); 635 if(lablen == 0) 636 return; /* do not modify root label */ 637 *len -= lablen+1; 638 *dname += lablen+1; 639 } 640 641 void 642 dname_remove_labels(uint8_t** dname, size_t* len, int n) 643 { 644 int i; 645 for(i=0; i<n; i++) 646 dname_remove_label(dname, len); 647 } 648 649 int 650 dname_signame_label_count(uint8_t* dname) 651 { 652 uint8_t lablen; 653 int count = 0; 654 if(!*dname) 655 return 0; 656 if(dname[0] == 1 && dname[1] == '*') 657 dname += 2; 658 lablen = dname[0]; 659 while(lablen) { 660 count++; 661 dname += lablen; 662 dname += 1; 663 lablen = dname[0]; 664 } 665 return count; 666 } 667 668 int 669 dname_is_wild(uint8_t* dname) 670 { 671 return (dname[0] == 1 && dname[1] == '*'); 672 } 673 674 /** 675 * Compare labels in memory, lowercase while comparing. 676 * Returns canonical order for labels. If all is equal, the 677 * shortest is first. 678 * 679 * @param p1: label 1 680 * @param len1: length of label 1. 681 * @param p2: label 2 682 * @param len2: length of label 2. 683 * @return: 0, -1, +1 comparison result. 684 */ 685 static int 686 memcanoncmp(uint8_t* p1, uint8_t len1, uint8_t* p2, uint8_t len2) 687 { 688 uint8_t min = (len1<len2)?len1:len2; 689 int c = memlowercmp(p1, p2, min); 690 if(c != 0) 691 return c; 692 /* equal, see who is shortest */ 693 if(len1 < len2) 694 return -1; 695 if(len1 > len2) 696 return 1; 697 return 0; 698 } 699 700 701 int 702 dname_canon_lab_cmp(uint8_t* d1, int labs1, uint8_t* d2, int labs2, int* mlabs) 703 { 704 /* like dname_lab_cmp, but with different label comparison, 705 * empty character sorts before \000. 706 * So ylyly is before z. */ 707 uint8_t len1, len2; 708 int atlabel = labs1; 709 int lastmlabs; 710 int lastdiff = 0; 711 int c; 712 /* first skip so that we compare same label. */ 713 if(labs1 > labs2) { 714 while(atlabel > labs2) { 715 len1 = *d1++; 716 d1 += len1; 717 atlabel--; 718 } 719 log_assert(atlabel == labs2); 720 } else if(labs1 < labs2) { 721 atlabel = labs2; 722 while(atlabel > labs1) { 723 len2 = *d2++; 724 d2 += len2; 725 atlabel--; 726 } 727 log_assert(atlabel == labs1); 728 } 729 lastmlabs = atlabel+1; 730 /* now at same label in d1 and d2, atlabel */ 731 /* www.example.com. */ 732 /* 4 3 2 1 atlabel number */ 733 /* repeat until at root label (which is always the same) */ 734 while(atlabel > 1) { 735 len1 = *d1++; 736 len2 = *d2++; 737 738 if((c=memcanoncmp(d1, len1, d2, len2)) != 0) { 739 if(c<0) 740 lastdiff = -1; 741 else lastdiff = 1; 742 lastmlabs = atlabel; 743 } 744 745 d1 += len1; 746 d2 += len2; 747 atlabel--; 748 } 749 /* last difference atlabel number, so number of labels matching, 750 * at the right side, is one less. */ 751 *mlabs = lastmlabs-1; 752 if(lastdiff == 0) { 753 /* all labels compared were equal, check if one has more 754 * labels, so that example.com. > com. */ 755 if(labs1 > labs2) 756 return 1; 757 else if(labs1 < labs2) 758 return -1; 759 } 760 return lastdiff; 761 } 762 763 int 764 dname_canonical_compare(uint8_t* d1, uint8_t* d2) 765 { 766 int labs1, labs2, m; 767 labs1 = dname_count_labels(d1); 768 labs2 = dname_count_labels(d2); 769 return dname_canon_lab_cmp(d1, labs1, d2, labs2, &m); 770 } 771 772 uint8_t* dname_get_shared_topdomain(uint8_t* d1, uint8_t* d2) 773 { 774 int labs1, labs2, m; 775 size_t len = LDNS_MAX_DOMAINLEN; 776 labs1 = dname_count_labels(d1); 777 labs2 = dname_count_labels(d2); 778 (void)dname_lab_cmp(d1, labs1, d2, labs2, &m); 779 dname_remove_labels(&d1, &len, labs1-m); 780 return d1; 781 } 782