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 void hash_tree_delete(region_type* region, rbtree_type* tree) 293 { 294 region_recycle(region, tree, sizeof(rbtree_type)); 295 } 296 297 /** add domain nsec3 node to hashedspace tree */ 298 void zone_add_domain_in_hash_tree(region_type* region, rbtree_type** tree, 299 int (*cmpf)(const void*, const void*), 300 domain_type* domain, rbnode_type* node) 301 { 302 if(!*tree) 303 *tree = rbtree_create(region, cmpf); 304 if(node->key && node->key == domain 305 && rbtree_search(*tree, domain) == node) 306 return; 307 memset(node, 0, sizeof(rbnode_type)); 308 node->key = domain; 309 rbtree_insert(*tree, node); 310 } 311 312 domain_table_type * 313 domain_table_create(region_type* region) 314 { 315 const dname_type* origin; 316 domain_table_type* result; 317 domain_type* root; 318 319 assert(region); 320 321 origin = dname_make(region, (uint8_t *) "", 0); 322 323 root = (domain_type *) region_alloc(region, sizeof(domain_type)); 324 #ifdef USE_RADIX_TREE 325 root->dname 326 #else 327 root->node.key 328 #endif 329 = origin; 330 root->parent = NULL; 331 root->wildcard_child_closest_match = root; 332 root->rrsets = NULL; 333 root->number = 1; /* 0 is used for after header */ 334 root->usage = 1; /* do not delete root, ever */ 335 root->is_existing = 0; 336 root->is_apex = 0; 337 root->numlist_prev = NULL; 338 root->numlist_next = NULL; 339 #ifdef NSEC3 340 root->nsec3 = NULL; 341 #endif 342 343 result = (domain_table_type *) region_alloc(region, 344 sizeof(domain_table_type)); 345 result->region = region; 346 #ifdef USE_RADIX_TREE 347 result->nametree = radix_tree_create(region); 348 root->rnode = radname_insert(result->nametree, dname_name(root->dname), 349 root->dname->name_size, root); 350 #else 351 result->names_to_domains = rbtree_create( 352 region, (int (*)(const void *, const void *)) dname_compare); 353 rbtree_insert(result->names_to_domains, (rbnode_type *) root); 354 #endif 355 356 result->root = root; 357 result->numlist_last = root; 358 #ifdef NSEC3 359 result->prehash_list = NULL; 360 #endif 361 362 return result; 363 } 364 365 int 366 domain_table_search(domain_table_type *table, 367 const dname_type *dname, 368 domain_type **closest_match, 369 domain_type **closest_encloser) 370 { 371 int exact; 372 uint8_t label_match_count; 373 374 assert(table); 375 assert(dname); 376 assert(closest_match); 377 assert(closest_encloser); 378 379 #ifdef USE_RADIX_TREE 380 exact = radname_find_less_equal(table->nametree, dname_name(dname), 381 dname->name_size, (struct radnode**)closest_match); 382 *closest_match = (domain_type*)((*(struct radnode**)closest_match)->elem); 383 #else 384 exact = rbtree_find_less_equal(table->names_to_domains, dname, (rbnode_type **) closest_match); 385 #endif 386 assert(*closest_match); 387 388 *closest_encloser = *closest_match; 389 390 if (!exact) { 391 label_match_count = dname_label_match_count( 392 domain_dname(*closest_encloser), 393 dname); 394 assert(label_match_count < dname->label_count); 395 while (label_match_count < domain_dname(*closest_encloser)->label_count) { 396 (*closest_encloser) = (*closest_encloser)->parent; 397 assert(*closest_encloser); 398 } 399 } 400 401 return exact; 402 } 403 404 domain_type * 405 domain_table_find(domain_table_type* table, 406 const dname_type* dname) 407 { 408 domain_type* closest_match; 409 domain_type* closest_encloser; 410 int exact; 411 412 exact = domain_table_search( 413 table, dname, &closest_match, &closest_encloser); 414 return exact ? closest_encloser : NULL; 415 } 416 417 418 domain_type * 419 domain_table_insert(domain_table_type* table, 420 const dname_type* dname) 421 { 422 domain_type* closest_match; 423 domain_type* closest_encloser; 424 domain_type* result; 425 int exact; 426 427 assert(table); 428 assert(dname); 429 430 exact = domain_table_search( 431 table, dname, &closest_match, &closest_encloser); 432 if (exact) { 433 result = closest_encloser; 434 } else { 435 assert(domain_dname(closest_encloser)->label_count < dname->label_count); 436 437 /* Insert new node(s). */ 438 do { 439 result = allocate_domain_info(table, 440 dname, 441 closest_encloser); 442 #ifdef USE_RADIX_TREE 443 result->rnode = radname_insert(table->nametree, 444 dname_name(result->dname), 445 result->dname->name_size, result); 446 #else 447 rbtree_insert(table->names_to_domains, (rbnode_type *) result); 448 #endif 449 450 /* 451 * If the newly added domain name is larger 452 * than the parent's current 453 * wildcard_child_closest_match but smaller or 454 * equal to the wildcard domain name, update 455 * the parent's wildcard_child_closest_match 456 * field. 457 */ 458 if (label_compare(dname_name(domain_dname(result)), 459 (const uint8_t *) "\001*") <= 0 460 && dname_compare(domain_dname(result), 461 domain_dname(closest_encloser->wildcard_child_closest_match)) > 0) 462 { 463 closest_encloser->wildcard_child_closest_match 464 = result; 465 } 466 closest_encloser = result; 467 } while (domain_dname(closest_encloser)->label_count < dname->label_count); 468 } 469 470 return result; 471 } 472 473 domain_type *domain_previous_existing_child(domain_type* domain) 474 { 475 domain_type* parent = domain->parent; 476 domain = domain_previous(domain); 477 while(domain && !domain->is_existing) { 478 if(domain == parent) /* do not walk back above parent */ 479 return parent; 480 domain = domain_previous(domain); 481 } 482 return domain; 483 } 484 485 void 486 domain_add_rrset(domain_type* domain, rrset_type* rrset) 487 { 488 #if 0 /* fast */ 489 rrset->next = domain->rrsets; 490 domain->rrsets = rrset; 491 #else 492 /* preserve ordering, add at end */ 493 rrset_type** p = &domain->rrsets; 494 while(*p) 495 p = &((*p)->next); 496 *p = rrset; 497 rrset->next = 0; 498 #endif 499 500 while (domain && !domain->is_existing) { 501 domain->is_existing = 1; 502 /* does this name in existance update the parent's 503 * wildcard closest match? */ 504 if(domain->parent 505 && label_compare(dname_name(domain_dname(domain)), 506 (const uint8_t *) "\001*") <= 0 507 && dname_compare(domain_dname(domain), 508 domain_dname(domain->parent->wildcard_child_closest_match)) > 0) { 509 domain->parent->wildcard_child_closest_match = domain; 510 } 511 domain = domain->parent; 512 } 513 } 514 515 516 rrset_type * 517 domain_find_rrset(domain_type* domain, zone_type* zone, uint16_t type) 518 { 519 rrset_type* result = domain->rrsets; 520 521 while (result) { 522 if (result->zone == zone && rrset_rrtype(result) == type) { 523 return result; 524 } 525 result = result->next; 526 } 527 return NULL; 528 } 529 530 rrset_type * 531 domain_find_any_rrset(domain_type* domain, zone_type* zone) 532 { 533 rrset_type* result = domain->rrsets; 534 535 while (result) { 536 if (result->zone == zone) { 537 return result; 538 } 539 result = result->next; 540 } 541 return NULL; 542 } 543 544 zone_type * 545 domain_find_zone(namedb_type* db, domain_type* domain) 546 { 547 rrset_type* rrset; 548 while (domain) { 549 if(domain->is_apex) { 550 for (rrset = domain->rrsets; rrset; rrset = rrset->next) { 551 if (rrset_rrtype(rrset) == TYPE_SOA) { 552 return rrset->zone; 553 } 554 } 555 return namedb_find_zone(db, domain_dname(domain)); 556 } 557 domain = domain->parent; 558 } 559 return NULL; 560 } 561 562 zone_type * 563 domain_find_parent_zone(namedb_type* db, zone_type* zone) 564 { 565 rrset_type* rrset; 566 567 assert(zone); 568 569 for (rrset = zone->apex->rrsets; rrset; rrset = rrset->next) { 570 if (rrset->zone != zone && rrset_rrtype(rrset) == TYPE_NS) { 571 return rrset->zone; 572 } 573 } 574 /* the NS record in the parent zone above this zone is not present, 575 * workaround to find that parent zone anyway */ 576 if(zone->apex->parent) 577 return domain_find_zone(db, zone->apex->parent); 578 return NULL; 579 } 580 581 domain_type * 582 domain_find_ns_rrsets(domain_type* domain, zone_type* zone, rrset_type **ns) 583 { 584 /* return highest NS RRset in the zone that is a delegation above */ 585 domain_type* result = NULL; 586 rrset_type* rrset = NULL; 587 while (domain && domain != zone->apex) { 588 rrset = domain_find_rrset(domain, zone, TYPE_NS); 589 if (rrset) { 590 *ns = rrset; 591 result = domain; 592 } 593 domain = domain->parent; 594 } 595 596 if(result) 597 return result; 598 599 *ns = NULL; 600 return NULL; 601 } 602 603 domain_type * 604 find_dname_above(domain_type* domain, zone_type* zone) 605 { 606 domain_type* d = domain->parent; 607 while(d && d != zone->apex) { 608 if(domain_find_rrset(d, zone, TYPE_DNAME)) 609 return d; 610 d = d->parent; 611 } 612 return NULL; 613 } 614 615 int 616 domain_is_glue(domain_type* domain, zone_type* zone) 617 { 618 rrset_type* unused; 619 domain_type* ns_domain = domain_find_ns_rrsets(domain, zone, &unused); 620 return (ns_domain != NULL && 621 domain_find_rrset(ns_domain, zone, TYPE_SOA) == NULL); 622 } 623 624 domain_type * 625 domain_wildcard_child(domain_type* domain) 626 { 627 domain_type* wildcard_child; 628 629 assert(domain); 630 assert(domain->wildcard_child_closest_match); 631 632 wildcard_child = domain->wildcard_child_closest_match; 633 if (wildcard_child != domain 634 && label_is_wildcard(dname_name(domain_dname(wildcard_child)))) 635 { 636 return wildcard_child; 637 } else { 638 return NULL; 639 } 640 } 641 642 int 643 zone_is_secure(zone_type* zone) 644 { 645 assert(zone); 646 return zone->is_secure; 647 } 648 649 uint16_t 650 rr_rrsig_type_covered(rr_type* rr) 651 { 652 assert(rr->type == TYPE_RRSIG); 653 assert(rr->rdata_count > 0); 654 assert(rdata_atom_size(rr->rdatas[0]) == sizeof(uint16_t)); 655 656 return ntohs(* (uint16_t *) rdata_atom_data(rr->rdatas[0])); 657 } 658 659 zone_type * 660 namedb_find_zone(namedb_type* db, const dname_type* dname) 661 { 662 struct radnode* n = radname_search(db->zonetree, dname_name(dname), 663 dname->name_size); 664 if(n) return (zone_type*)n->elem; 665 return NULL; 666 } 667 668 rrset_type * 669 domain_find_non_cname_rrset(domain_type* domain, zone_type* zone) 670 { 671 /* find any rrset type that is not allowed next to a CNAME */ 672 /* nothing is allowed next to a CNAME, except RRSIG, NSEC, NSEC3 */ 673 rrset_type *result = domain->rrsets; 674 675 while (result) { 676 if (result->zone == zone && /* here is the list of exceptions*/ 677 rrset_rrtype(result) != TYPE_CNAME && 678 rrset_rrtype(result) != TYPE_RRSIG && 679 rrset_rrtype(result) != TYPE_NXT && 680 rrset_rrtype(result) != TYPE_SIG && 681 rrset_rrtype(result) != TYPE_NSEC && 682 rrset_rrtype(result) != TYPE_NSEC3 ) { 683 return result; 684 } 685 result = result->next; 686 } 687 return NULL; 688 } 689 690 int 691 namedb_lookup(struct namedb* db, 692 const dname_type* dname, 693 domain_type **closest_match, 694 domain_type **closest_encloser) 695 { 696 return domain_table_search( 697 db->domains, dname, closest_match, closest_encloser); 698 } 699 700 void zone_rr_iter_init(struct zone_rr_iter *iter, struct zone *zone) 701 { 702 assert(iter != NULL); 703 assert(zone != NULL); 704 memset(iter, 0, sizeof(*iter)); 705 iter->zone = zone; 706 } 707 708 rr_type *zone_rr_iter_next(struct zone_rr_iter *iter) 709 { 710 assert(iter != NULL); 711 assert(iter->zone != NULL); 712 713 if(iter->index == -1) { 714 assert(iter->domain == NULL); 715 assert(iter->rrset == NULL); 716 return NULL; 717 } else if(iter->rrset == NULL) { 718 /* ensure SOA RR is returned first */ 719 assert(iter->domain == NULL); 720 assert(iter->index == 0); 721 iter->rrset = iter->zone->soa_rrset; 722 } 723 724 while(iter->rrset != NULL) { 725 if(iter->index < iter->rrset->rr_count) { 726 return &iter->rrset->rrs[iter->index++]; 727 } 728 iter->index = 0; 729 if(iter->domain == NULL) { 730 assert(iter->rrset == iter->zone->soa_rrset); 731 iter->domain = iter->zone->apex; 732 iter->rrset = iter->domain->rrsets; 733 } else { 734 iter->rrset = iter->rrset->next; 735 } 736 /* ensure SOA RR is not returned again and RR belongs to zone */ 737 while((iter->rrset == NULL && iter->domain != NULL) || 738 (iter->rrset != NULL && (iter->rrset == iter->zone->soa_rrset || 739 iter->rrset->zone != iter->zone))) 740 { 741 if(iter->rrset != NULL) { 742 iter->rrset = iter->rrset->next; 743 } else { 744 iter->domain = domain_next(iter->domain); 745 if(iter->domain != NULL && 746 dname_is_subdomain(domain_dname(iter->domain), 747 domain_dname(iter->zone->apex))) 748 { 749 iter->rrset = iter->domain->rrsets; 750 } 751 } 752 } 753 } 754 755 assert(iter->rrset == NULL); 756 assert(iter->domain == NULL); 757 iter->index = -1; 758 759 return NULL; 760 } 761