1 /* 2 * namedb.c -- common namedb operations. 3 * 4 * Copyright (c) 2001-2006, NLnet Labs. All rights reserved. 5 * 6 * See LICENSE for the license. 7 * 8 */ 9 10 #include "config.h" 11 12 #include <sys/types.h> 13 14 #include <assert.h> 15 #include <ctype.h> 16 #include <limits.h> 17 #include <stdio.h> 18 #include <string.h> 19 20 #include "namedb.h" 21 #include "nsec3.h" 22 23 static domain_type * 24 allocate_domain_info(domain_table_type* table, 25 const dname_type* dname, 26 domain_type* parent) 27 { 28 domain_type *result; 29 30 assert(table); 31 assert(dname); 32 assert(parent); 33 34 result = (domain_type *) region_alloc(table->region, 35 sizeof(domain_type)); 36 #ifdef USE_RADIX_TREE 37 result->dname 38 #else 39 result->node.key 40 #endif 41 = dname_partial_copy( 42 table->region, dname, domain_dname(parent)->label_count + 1); 43 result->parent = parent; 44 result->wildcard_child_closest_match = result; 45 result->rrsets = NULL; 46 result->usage = 0; 47 #ifdef NSEC3 48 result->nsec3 = NULL; 49 #endif 50 result->is_existing = 0; 51 result->is_apex = 0; 52 assert(table->numlist_last); /* it exists because root exists */ 53 /* push this domain at the end of the numlist */ 54 result->number = table->numlist_last->number+1; 55 result->numlist_next = NULL; 56 result->numlist_prev = table->numlist_last; 57 table->numlist_last->numlist_next = result; 58 table->numlist_last = result; 59 60 return result; 61 } 62 63 #ifdef NSEC3 64 void 65 allocate_domain_nsec3(domain_table_type* table, domain_type* result) 66 { 67 if(result->nsec3) 68 return; 69 result->nsec3 = (struct nsec3_domain_data*) region_alloc(table->region, 70 sizeof(struct nsec3_domain_data)); 71 result->nsec3->nsec3_cover = NULL; 72 result->nsec3->nsec3_wcard_child_cover = NULL; 73 result->nsec3->nsec3_ds_parent_cover = NULL; 74 result->nsec3->nsec3_is_exact = 0; 75 result->nsec3->nsec3_ds_parent_is_exact = 0; 76 result->nsec3->hash_wc = NULL; 77 result->nsec3->ds_parent_hash = NULL; 78 result->nsec3->prehash_prev = NULL; 79 result->nsec3->prehash_next = NULL; 80 result->nsec3->nsec3_node.key = NULL; 81 } 82 #endif /* NSEC3 */ 83 84 /** make the domain last in the numlist, changes numbers of domains */ 85 static void 86 numlist_make_last(domain_table_type* table, domain_type* domain) 87 { 88 uint32_t sw; 89 domain_type* last = table->numlist_last; 90 if(domain == last) 91 return; 92 /* swap numbers with the last element */ 93 sw = domain->number; 94 domain->number = last->number; 95 last->number = sw; 96 /* swap list position with the last element */ 97 assert(domain->numlist_next); 98 assert(last->numlist_prev); 99 if(domain->numlist_next != last) { 100 /* case 1: there are nodes between domain .. last */ 101 domain_type* span_start = domain->numlist_next; 102 domain_type* span_end = last->numlist_prev; 103 /* these assignments walk the new list from start to end */ 104 if(domain->numlist_prev) 105 domain->numlist_prev->numlist_next = last; 106 last->numlist_prev = domain->numlist_prev; 107 last->numlist_next = span_start; 108 span_start->numlist_prev = last; 109 span_end->numlist_next = domain; 110 domain->numlist_prev = span_end; 111 domain->numlist_next = NULL; 112 } else { 113 /* case 2: domain and last are neighbors */ 114 /* these assignments walk the new list from start to end */ 115 if(domain->numlist_prev) 116 domain->numlist_prev->numlist_next = last; 117 last->numlist_prev = domain->numlist_prev; 118 last->numlist_next = domain; 119 domain->numlist_prev = last; 120 domain->numlist_next = NULL; 121 } 122 table->numlist_last = domain; 123 } 124 125 /** pop the biggest domain off the numlist */ 126 static domain_type* 127 numlist_pop_last(domain_table_type* table) 128 { 129 domain_type* d = table->numlist_last; 130 table->numlist_last = table->numlist_last->numlist_prev; 131 if(table->numlist_last) 132 table->numlist_last->numlist_next = NULL; 133 return d; 134 } 135 136 /** see if a domain is eligible to be deleted, and thus is not used */ 137 static int 138 domain_can_be_deleted(domain_type* domain) 139 { 140 domain_type* n; 141 /* it has data or it has usage, do not delete it */ 142 if(domain->rrsets) return 0; 143 if(domain->usage) return 0; 144 n = domain_next(domain); 145 /* it has children domains, do not delete it */ 146 if(n && domain_is_subdomain(n, domain)) 147 return 0; 148 return 1; 149 } 150 151 #ifdef NSEC3 152 /** see if domain is on the prehash list */ 153 int domain_is_prehash(domain_table_type* table, domain_type* domain) 154 { 155 if(domain->nsec3 156 && (domain->nsec3->prehash_prev || domain->nsec3->prehash_next)) 157 return 1; 158 return (table->prehash_list == domain); 159 } 160 161 /** remove domain node from NSEC3 tree in hash space */ 162 void 163 zone_del_domain_in_hash_tree(rbtree_type* tree, rbnode_type* node) 164 { 165 if(!node->key) 166 return; 167 rbtree_delete(tree, node->key); 168 /* note that domain is no longer in the tree */ 169 node->key = NULL; 170 } 171 172 /** clear the prehash list */ 173 void prehash_clear(domain_table_type* table) 174 { 175 domain_type* d = table->prehash_list, *n; 176 while(d) { 177 n = d->nsec3->prehash_next; 178 d->nsec3->prehash_prev = NULL; 179 d->nsec3->prehash_next = NULL; 180 d = n; 181 } 182 table->prehash_list = NULL; 183 } 184 185 /** add domain to prehash list */ 186 void 187 prehash_add(domain_table_type* table, domain_type* domain) 188 { 189 if(domain_is_prehash(table, domain)) 190 return; 191 allocate_domain_nsec3(table, domain); 192 domain->nsec3->prehash_next = table->prehash_list; 193 if(table->prehash_list) 194 table->prehash_list->nsec3->prehash_prev = domain; 195 table->prehash_list = domain; 196 } 197 198 /** remove domain from prehash list */ 199 void 200 prehash_del(domain_table_type* table, domain_type* domain) 201 { 202 if(domain->nsec3->prehash_next) 203 domain->nsec3->prehash_next->nsec3->prehash_prev = 204 domain->nsec3->prehash_prev; 205 if(domain->nsec3->prehash_prev) 206 domain->nsec3->prehash_prev->nsec3->prehash_next = 207 domain->nsec3->prehash_next; 208 else table->prehash_list = domain->nsec3->prehash_next; 209 domain->nsec3->prehash_next = NULL; 210 domain->nsec3->prehash_prev = NULL; 211 } 212 #endif /* NSEC3 */ 213 214 /** perform domain name deletion */ 215 static void 216 do_deldomain(namedb_type* db, domain_type* domain) 217 { 218 assert(domain && domain->parent); /* exists and not root */ 219 /* first adjust the number list so that domain is the last one */ 220 numlist_make_last(db->domains, domain); 221 /* pop off the domain from the number list */ 222 (void)numlist_pop_last(db->domains); 223 224 #ifdef NSEC3 225 /* if on prehash list, remove from prehash */ 226 if(domain_is_prehash(db->domains, domain)) 227 prehash_del(db->domains, domain); 228 229 /* see if nsec3-nodes are used */ 230 if(domain->nsec3) { 231 if(domain->nsec3->nsec3_node.key) 232 zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain) 233 ->nsec3tree, &domain->nsec3->nsec3_node); 234 if(domain->nsec3->hash_wc) { 235 if(domain->nsec3->hash_wc->hash.node.key) 236 zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain) 237 ->hashtree, &domain->nsec3->hash_wc->hash.node); 238 if(domain->nsec3->hash_wc->wc.node.key) 239 zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain) 240 ->wchashtree, &domain->nsec3->hash_wc->wc.node); 241 } 242 if(domain->nsec3->ds_parent_hash && domain->nsec3->ds_parent_hash->node.key) 243 zone_del_domain_in_hash_tree(nsec3_tree_dszone(db, domain) 244 ->dshashtree, &domain->nsec3->ds_parent_hash->node); 245 if(domain->nsec3->hash_wc) { 246 region_recycle(db->domains->region, 247 domain->nsec3->hash_wc, 248 sizeof(nsec3_hash_wc_node_type)); 249 } 250 if(domain->nsec3->ds_parent_hash) { 251 region_recycle(db->domains->region, 252 domain->nsec3->ds_parent_hash, 253 sizeof(nsec3_hash_node_type)); 254 } 255 region_recycle(db->domains->region, domain->nsec3, 256 sizeof(struct nsec3_domain_data)); 257 } 258 #endif /* NSEC3 */ 259 260 /* see if this domain is someones wildcard-child-closest-match, 261 * which can only be the parent, and then it should use the 262 * one-smaller than this domain as closest-match. */ 263 if(domain->parent->wildcard_child_closest_match == domain) 264 domain->parent->wildcard_child_closest_match = 265 domain_previous_existing_child(domain); 266 267 /* actual removal */ 268 #ifdef USE_RADIX_TREE 269 radix_delete(db->domains->nametree, domain->rnode); 270 #else 271 rbtree_delete(db->domains->names_to_domains, domain->node.key); 272 #endif 273 region_recycle(db->domains->region, domain_dname(domain), 274 dname_total_size(domain_dname(domain))); 275 region_recycle(db->domains->region, domain, sizeof(domain_type)); 276 } 277 278 void 279 domain_table_deldomain(namedb_type* db, domain_type* domain) 280 { 281 domain_type* parent; 282 283 while(domain_can_be_deleted(domain)) { 284 parent = domain->parent; 285 /* delete it */ 286 do_deldomain(db, domain); 287 /* test parent */ 288 domain = parent; 289 } 290 } 291 292 /** clear hash tree */ 293 void 294 hash_tree_clear(rbtree_type* tree) 295 { 296 rbnode_type* n; 297 if(!tree) return; 298 299 /* note that elements are no longer in the tree */ 300 for(n=rbtree_first(tree); n!=RBTREE_NULL; n=rbtree_next(n)) { 301 n->key = NULL; 302 } 303 tree->count = 0; 304 tree->root = RBTREE_NULL; 305 } 306 307 void hash_tree_delete(region_type* region, rbtree_type* tree) 308 { 309 region_recycle(region, tree, sizeof(rbtree_type)); 310 } 311 312 /** add domain nsec3 node to hashedspace tree */ 313 void zone_add_domain_in_hash_tree(region_type* region, rbtree_type** tree, 314 int (*cmpf)(const void*, const void*), 315 domain_type* domain, rbnode_type* node) 316 { 317 if(!*tree) 318 *tree = rbtree_create(region, cmpf); 319 if(node->key) return; 320 memset(node, 0, sizeof(rbnode_type)); 321 node->key = domain; 322 rbtree_insert(*tree, node); 323 } 324 325 domain_table_type * 326 domain_table_create(region_type* region) 327 { 328 const dname_type* origin; 329 domain_table_type* result; 330 domain_type* root; 331 332 assert(region); 333 334 origin = dname_make(region, (uint8_t *) "", 0); 335 336 root = (domain_type *) region_alloc(region, sizeof(domain_type)); 337 #ifdef USE_RADIX_TREE 338 root->dname 339 #else 340 root->node.key 341 #endif 342 = origin; 343 root->parent = NULL; 344 root->wildcard_child_closest_match = root; 345 root->rrsets = NULL; 346 root->number = 1; /* 0 is used for after header */ 347 root->usage = 1; /* do not delete root, ever */ 348 root->is_existing = 0; 349 root->is_apex = 0; 350 root->numlist_prev = NULL; 351 root->numlist_next = NULL; 352 #ifdef NSEC3 353 root->nsec3 = NULL; 354 #endif 355 356 result = (domain_table_type *) region_alloc(region, 357 sizeof(domain_table_type)); 358 result->region = region; 359 #ifdef USE_RADIX_TREE 360 result->nametree = radix_tree_create(region); 361 root->rnode = radname_insert(result->nametree, dname_name(root->dname), 362 root->dname->name_size, root); 363 #else 364 result->names_to_domains = rbtree_create( 365 region, (int (*)(const void *, const void *)) dname_compare); 366 rbtree_insert(result->names_to_domains, (rbnode_type *) root); 367 #endif 368 369 result->root = root; 370 result->numlist_last = root; 371 #ifdef NSEC3 372 result->prehash_list = NULL; 373 #endif 374 375 return result; 376 } 377 378 int 379 domain_table_search(domain_table_type *table, 380 const dname_type *dname, 381 domain_type **closest_match, 382 domain_type **closest_encloser) 383 { 384 int exact; 385 uint8_t label_match_count; 386 387 assert(table); 388 assert(dname); 389 assert(closest_match); 390 assert(closest_encloser); 391 392 #ifdef USE_RADIX_TREE 393 exact = radname_find_less_equal(table->nametree, dname_name(dname), 394 dname->name_size, (struct radnode**)closest_match); 395 *closest_match = (domain_type*)((*(struct radnode**)closest_match)->elem); 396 #else 397 exact = rbtree_find_less_equal(table->names_to_domains, dname, (rbnode_type **) closest_match); 398 #endif 399 assert(*closest_match); 400 401 *closest_encloser = *closest_match; 402 403 if (!exact) { 404 label_match_count = dname_label_match_count( 405 domain_dname(*closest_encloser), 406 dname); 407 assert(label_match_count < dname->label_count); 408 while (label_match_count < domain_dname(*closest_encloser)->label_count) { 409 (*closest_encloser) = (*closest_encloser)->parent; 410 assert(*closest_encloser); 411 } 412 } 413 414 return exact; 415 } 416 417 domain_type * 418 domain_table_find(domain_table_type* table, 419 const dname_type* dname) 420 { 421 domain_type* closest_match; 422 domain_type* closest_encloser; 423 int exact; 424 425 exact = domain_table_search( 426 table, dname, &closest_match, &closest_encloser); 427 return exact ? closest_encloser : NULL; 428 } 429 430 431 domain_type * 432 domain_table_insert(domain_table_type* table, 433 const dname_type* dname) 434 { 435 domain_type* closest_match; 436 domain_type* closest_encloser; 437 domain_type* result; 438 int exact; 439 440 assert(table); 441 assert(dname); 442 443 exact = domain_table_search( 444 table, dname, &closest_match, &closest_encloser); 445 if (exact) { 446 result = closest_encloser; 447 } else { 448 assert(domain_dname(closest_encloser)->label_count < dname->label_count); 449 450 /* Insert new node(s). */ 451 do { 452 result = allocate_domain_info(table, 453 dname, 454 closest_encloser); 455 #ifdef USE_RADIX_TREE 456 result->rnode = radname_insert(table->nametree, 457 dname_name(result->dname), 458 result->dname->name_size, result); 459 #else 460 rbtree_insert(table->names_to_domains, (rbnode_type *) result); 461 #endif 462 463 /* 464 * If the newly added domain name is larger 465 * than the parent's current 466 * wildcard_child_closest_match but smaller or 467 * equal to the wildcard domain name, update 468 * the parent's wildcard_child_closest_match 469 * field. 470 */ 471 if (label_compare(dname_name(domain_dname(result)), 472 (const uint8_t *) "\001*") <= 0 473 && dname_compare(domain_dname(result), 474 domain_dname(closest_encloser->wildcard_child_closest_match)) > 0) 475 { 476 closest_encloser->wildcard_child_closest_match 477 = result; 478 } 479 closest_encloser = result; 480 } while (domain_dname(closest_encloser)->label_count < dname->label_count); 481 } 482 483 return result; 484 } 485 486 domain_type *domain_previous_existing_child(domain_type* domain) 487 { 488 domain_type* parent = domain->parent; 489 domain = domain_previous(domain); 490 while(domain && !domain->is_existing) { 491 if(domain == parent) /* do not walk back above parent */ 492 return parent; 493 domain = domain_previous(domain); 494 } 495 return domain; 496 } 497 498 void 499 domain_add_rrset(domain_type* domain, rrset_type* rrset) 500 { 501 #if 0 /* fast */ 502 rrset->next = domain->rrsets; 503 domain->rrsets = rrset; 504 #else 505 /* preserve ordering, add at end */ 506 rrset_type** p = &domain->rrsets; 507 while(*p) 508 p = &((*p)->next); 509 *p = rrset; 510 rrset->next = 0; 511 #endif 512 513 while (domain && !domain->is_existing) { 514 domain->is_existing = 1; 515 /* does this name in existance update the parent's 516 * wildcard closest match? */ 517 if(domain->parent 518 && label_compare(dname_name(domain_dname(domain)), 519 (const uint8_t *) "\001*") <= 0 520 && dname_compare(domain_dname(domain), 521 domain_dname(domain->parent->wildcard_child_closest_match)) > 0) { 522 domain->parent->wildcard_child_closest_match = domain; 523 } 524 domain = domain->parent; 525 } 526 } 527 528 529 rrset_type * 530 domain_find_rrset(domain_type* domain, zone_type* zone, uint16_t type) 531 { 532 rrset_type* result = domain->rrsets; 533 534 while (result) { 535 if (result->zone == zone && rrset_rrtype(result) == type) { 536 return result; 537 } 538 result = result->next; 539 } 540 return NULL; 541 } 542 543 rrset_type * 544 domain_find_any_rrset(domain_type* domain, zone_type* zone) 545 { 546 rrset_type* result = domain->rrsets; 547 548 while (result) { 549 if (result->zone == zone) { 550 return result; 551 } 552 result = result->next; 553 } 554 return NULL; 555 } 556 557 zone_type * 558 domain_find_zone(namedb_type* db, domain_type* domain) 559 { 560 rrset_type* rrset; 561 while (domain) { 562 if(domain->is_apex) { 563 for (rrset = domain->rrsets; rrset; rrset = rrset->next) { 564 if (rrset_rrtype(rrset) == TYPE_SOA) { 565 return rrset->zone; 566 } 567 } 568 return namedb_find_zone(db, domain_dname(domain)); 569 } 570 domain = domain->parent; 571 } 572 return NULL; 573 } 574 575 zone_type * 576 domain_find_parent_zone(namedb_type* db, zone_type* zone) 577 { 578 rrset_type* rrset; 579 580 assert(zone); 581 582 for (rrset = zone->apex->rrsets; rrset; rrset = rrset->next) { 583 if (rrset->zone != zone && rrset_rrtype(rrset) == TYPE_NS) { 584 return rrset->zone; 585 } 586 } 587 /* the NS record in the parent zone above this zone is not present, 588 * workaround to find that parent zone anyway */ 589 if(zone->apex->parent) 590 return domain_find_zone(db, zone->apex->parent); 591 return NULL; 592 } 593 594 domain_type * 595 domain_find_ns_rrsets(domain_type* domain, zone_type* zone, rrset_type **ns) 596 { 597 while (domain && domain != zone->apex) { 598 *ns = domain_find_rrset(domain, zone, TYPE_NS); 599 if (*ns) 600 return domain; 601 domain = domain->parent; 602 } 603 604 *ns = NULL; 605 return NULL; 606 } 607 608 domain_type * 609 find_dname_above(domain_type* domain, zone_type* zone) 610 { 611 domain_type* d = domain->parent; 612 while(d && d != zone->apex) { 613 if(domain_find_rrset(d, zone, TYPE_DNAME)) 614 return d; 615 d = d->parent; 616 } 617 return NULL; 618 } 619 620 int 621 domain_is_glue(domain_type* domain, zone_type* zone) 622 { 623 rrset_type* unused; 624 domain_type* ns_domain = domain_find_ns_rrsets(domain, zone, &unused); 625 return (ns_domain != NULL && 626 domain_find_rrset(ns_domain, zone, TYPE_SOA) == NULL); 627 } 628 629 domain_type * 630 domain_wildcard_child(domain_type* domain) 631 { 632 domain_type* wildcard_child; 633 634 assert(domain); 635 assert(domain->wildcard_child_closest_match); 636 637 wildcard_child = domain->wildcard_child_closest_match; 638 if (wildcard_child != domain 639 && label_is_wildcard(dname_name(domain_dname(wildcard_child)))) 640 { 641 return wildcard_child; 642 } else { 643 return NULL; 644 } 645 } 646 647 int 648 zone_is_secure(zone_type* zone) 649 { 650 assert(zone); 651 return zone->is_secure; 652 } 653 654 uint16_t 655 rr_rrsig_type_covered(rr_type* rr) 656 { 657 assert(rr->type == TYPE_RRSIG); 658 assert(rr->rdata_count > 0); 659 assert(rdata_atom_size(rr->rdatas[0]) == sizeof(uint16_t)); 660 661 return ntohs(* (uint16_t *) rdata_atom_data(rr->rdatas[0])); 662 } 663 664 zone_type * 665 namedb_find_zone(namedb_type* db, const dname_type* dname) 666 { 667 struct radnode* n = radname_search(db->zonetree, dname_name(dname), 668 dname->name_size); 669 if(n) return (zone_type*)n->elem; 670 return NULL; 671 } 672 673 rrset_type * 674 domain_find_non_cname_rrset(domain_type* domain, zone_type* zone) 675 { 676 /* find any rrset type that is not allowed next to a CNAME */ 677 /* nothing is allowed next to a CNAME, except RRSIG, NSEC, NSEC3 */ 678 rrset_type *result = domain->rrsets; 679 680 while (result) { 681 if (result->zone == zone && /* here is the list of exceptions*/ 682 rrset_rrtype(result) != TYPE_CNAME && 683 rrset_rrtype(result) != TYPE_RRSIG && 684 rrset_rrtype(result) != TYPE_NXT && 685 rrset_rrtype(result) != TYPE_SIG && 686 rrset_rrtype(result) != TYPE_NSEC && 687 rrset_rrtype(result) != TYPE_NSEC3 ) { 688 return result; 689 } 690 result = result->next; 691 } 692 return NULL; 693 } 694 695 int 696 namedb_lookup(struct namedb* db, 697 const dname_type* dname, 698 domain_type **closest_match, 699 domain_type **closest_encloser) 700 { 701 return domain_table_search( 702 db->domains, dname, closest_match, closest_encloser); 703 } 704