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