162ac0c33Sjakob /* 262ac0c33Sjakob * namedb.c -- common namedb operations. 362ac0c33Sjakob * 4d3fecca9Ssthen * Copyright (c) 2001-2006, NLnet Labs. All rights reserved. 562ac0c33Sjakob * 662ac0c33Sjakob * See LICENSE for the license. 762ac0c33Sjakob * 862ac0c33Sjakob */ 962ac0c33Sjakob 10aee1b7aaSsthen #include "config.h" 1162ac0c33Sjakob 1262ac0c33Sjakob #include <sys/types.h> 1362ac0c33Sjakob 1462ac0c33Sjakob #include <assert.h> 1562ac0c33Sjakob #include <ctype.h> 1662ac0c33Sjakob #include <limits.h> 1762ac0c33Sjakob #include <stdio.h> 1862ac0c33Sjakob #include <string.h> 1962ac0c33Sjakob 2062ac0c33Sjakob #include "namedb.h" 21d3fecca9Ssthen #include "nsec3.h" 2262ac0c33Sjakob 2362ac0c33Sjakob static domain_type * 2462ac0c33Sjakob allocate_domain_info(domain_table_type* table, 2562ac0c33Sjakob const dname_type* dname, 2662ac0c33Sjakob domain_type* parent) 2762ac0c33Sjakob { 2862ac0c33Sjakob domain_type *result; 2962ac0c33Sjakob 3062ac0c33Sjakob assert(table); 3162ac0c33Sjakob assert(dname); 3262ac0c33Sjakob assert(parent); 3362ac0c33Sjakob 3462ac0c33Sjakob result = (domain_type *) region_alloc(table->region, 3562ac0c33Sjakob sizeof(domain_type)); 36c1e73312Sflorian #ifdef USE_RADIX_TREE 37c1e73312Sflorian result->dname 38c1e73312Sflorian #else 39c1e73312Sflorian result->node.key 40c1e73312Sflorian #endif 41c1e73312Sflorian = dname_partial_copy( 4262ac0c33Sjakob table->region, dname, domain_dname(parent)->label_count + 1); 4362ac0c33Sjakob result->parent = parent; 4462ac0c33Sjakob result->wildcard_child_closest_match = result; 4562ac0c33Sjakob result->rrsets = NULL; 46d3fecca9Ssthen result->usage = 0; 4762ac0c33Sjakob #ifdef NSEC3 48d3fecca9Ssthen result->nsec3 = NULL; 49d3fecca9Ssthen #endif 5062ac0c33Sjakob result->is_existing = 0; 5162ac0c33Sjakob result->is_apex = 0; 52d3fecca9Ssthen assert(table->numlist_last); /* it exists because root exists */ 53d3fecca9Ssthen /* push this domain at the end of the numlist */ 54d3fecca9Ssthen result->number = table->numlist_last->number+1; 55d3fecca9Ssthen result->numlist_next = NULL; 56d3fecca9Ssthen result->numlist_prev = table->numlist_last; 57d3fecca9Ssthen table->numlist_last->numlist_next = result; 58d3fecca9Ssthen table->numlist_last = result; 5962ac0c33Sjakob 6062ac0c33Sjakob return result; 6162ac0c33Sjakob } 6262ac0c33Sjakob 63d3fecca9Ssthen #ifdef NSEC3 64d3fecca9Ssthen void 65d3fecca9Ssthen allocate_domain_nsec3(domain_table_type* table, domain_type* result) 66d3fecca9Ssthen { 67d3fecca9Ssthen if(result->nsec3) 68d3fecca9Ssthen return; 69d3fecca9Ssthen result->nsec3 = (struct nsec3_domain_data*) region_alloc(table->region, 70d3fecca9Ssthen sizeof(struct nsec3_domain_data)); 71d3fecca9Ssthen result->nsec3->nsec3_cover = NULL; 72d3fecca9Ssthen result->nsec3->nsec3_wcard_child_cover = NULL; 73d3fecca9Ssthen result->nsec3->nsec3_ds_parent_cover = NULL; 74d3fecca9Ssthen result->nsec3->nsec3_is_exact = 0; 75d3fecca9Ssthen result->nsec3->nsec3_ds_parent_is_exact = 0; 76ee5153b7Sflorian result->nsec3->hash_wc = NULL; 77ee5153b7Sflorian result->nsec3->ds_parent_hash = NULL; 78d3fecca9Ssthen result->nsec3->prehash_prev = NULL; 79d3fecca9Ssthen result->nsec3->prehash_next = NULL; 80d3fecca9Ssthen result->nsec3->nsec3_node.key = NULL; 81d3fecca9Ssthen } 82d3fecca9Ssthen #endif /* NSEC3 */ 83d3fecca9Ssthen 84d3fecca9Ssthen /** make the domain last in the numlist, changes numbers of domains */ 85d3fecca9Ssthen static void 86d3fecca9Ssthen numlist_make_last(domain_table_type* table, domain_type* domain) 87d3fecca9Ssthen { 88ee5153b7Sflorian uint32_t sw; 89d3fecca9Ssthen domain_type* last = table->numlist_last; 90d3fecca9Ssthen if(domain == last) 91d3fecca9Ssthen return; 92d3fecca9Ssthen /* swap numbers with the last element */ 93d3fecca9Ssthen sw = domain->number; 94d3fecca9Ssthen domain->number = last->number; 95d3fecca9Ssthen last->number = sw; 96d3fecca9Ssthen /* swap list position with the last element */ 97d3fecca9Ssthen assert(domain->numlist_next); 98d3fecca9Ssthen assert(last->numlist_prev); 99d3fecca9Ssthen if(domain->numlist_next != last) { 100d3fecca9Ssthen /* case 1: there are nodes between domain .. last */ 101d3fecca9Ssthen domain_type* span_start = domain->numlist_next; 102d3fecca9Ssthen domain_type* span_end = last->numlist_prev; 103d3fecca9Ssthen /* these assignments walk the new list from start to end */ 104d3fecca9Ssthen if(domain->numlist_prev) 105d3fecca9Ssthen domain->numlist_prev->numlist_next = last; 106d3fecca9Ssthen last->numlist_prev = domain->numlist_prev; 107d3fecca9Ssthen last->numlist_next = span_start; 108d3fecca9Ssthen span_start->numlist_prev = last; 109d3fecca9Ssthen span_end->numlist_next = domain; 110d3fecca9Ssthen domain->numlist_prev = span_end; 111d3fecca9Ssthen domain->numlist_next = NULL; 112d3fecca9Ssthen } else { 113d3fecca9Ssthen /* case 2: domain and last are neighbors */ 114d3fecca9Ssthen /* these assignments walk the new list from start to end */ 115d3fecca9Ssthen if(domain->numlist_prev) 116d3fecca9Ssthen domain->numlist_prev->numlist_next = last; 117d3fecca9Ssthen last->numlist_prev = domain->numlist_prev; 118d3fecca9Ssthen last->numlist_next = domain; 119d3fecca9Ssthen domain->numlist_prev = last; 120d3fecca9Ssthen domain->numlist_next = NULL; 121d3fecca9Ssthen } 122d3fecca9Ssthen table->numlist_last = domain; 123d3fecca9Ssthen } 124d3fecca9Ssthen 125d3fecca9Ssthen /** pop the biggest domain off the numlist */ 126d3fecca9Ssthen static domain_type* 127d3fecca9Ssthen numlist_pop_last(domain_table_type* table) 128d3fecca9Ssthen { 129d3fecca9Ssthen domain_type* d = table->numlist_last; 130d3fecca9Ssthen table->numlist_last = table->numlist_last->numlist_prev; 131d3fecca9Ssthen if(table->numlist_last) 132d3fecca9Ssthen table->numlist_last->numlist_next = NULL; 133d3fecca9Ssthen return d; 134d3fecca9Ssthen } 135d3fecca9Ssthen 136d3fecca9Ssthen /** see if a domain is eligible to be deleted, and thus is not used */ 137d3fecca9Ssthen static int 138d3fecca9Ssthen domain_can_be_deleted(domain_type* domain) 139d3fecca9Ssthen { 140d3fecca9Ssthen domain_type* n; 141d3fecca9Ssthen /* it has data or it has usage, do not delete it */ 142d3fecca9Ssthen if(domain->rrsets) return 0; 143d3fecca9Ssthen if(domain->usage) return 0; 144d3fecca9Ssthen n = domain_next(domain); 145d3fecca9Ssthen /* it has children domains, do not delete it */ 146d3fecca9Ssthen if(n && domain_is_subdomain(n, domain)) 147d3fecca9Ssthen return 0; 148d3fecca9Ssthen return 1; 149d3fecca9Ssthen } 150d3fecca9Ssthen 151d3fecca9Ssthen #ifdef NSEC3 152d3fecca9Ssthen /** see if domain is on the prehash list */ 153d3fecca9Ssthen int domain_is_prehash(domain_table_type* table, domain_type* domain) 154d3fecca9Ssthen { 155d3fecca9Ssthen if(domain->nsec3 156d3fecca9Ssthen && (domain->nsec3->prehash_prev || domain->nsec3->prehash_next)) 157d3fecca9Ssthen return 1; 158d3fecca9Ssthen return (table->prehash_list == domain); 159d3fecca9Ssthen } 160d3fecca9Ssthen 161d3fecca9Ssthen /** remove domain node from NSEC3 tree in hash space */ 162d3fecca9Ssthen void 163fe5fe5f6Sflorian zone_del_domain_in_hash_tree(rbtree_type* tree, rbnode_type* node) 164d3fecca9Ssthen { 165d3fecca9Ssthen if(!node->key) 166d3fecca9Ssthen return; 167d3fecca9Ssthen rbtree_delete(tree, node->key); 168d3fecca9Ssthen /* note that domain is no longer in the tree */ 169d3fecca9Ssthen node->key = NULL; 170d3fecca9Ssthen } 171d3fecca9Ssthen 172d3fecca9Ssthen /** clear the prehash list */ 173d3fecca9Ssthen void prehash_clear(domain_table_type* table) 174d3fecca9Ssthen { 175d3fecca9Ssthen domain_type* d = table->prehash_list, *n; 176d3fecca9Ssthen while(d) { 177d3fecca9Ssthen n = d->nsec3->prehash_next; 178d3fecca9Ssthen d->nsec3->prehash_prev = NULL; 179d3fecca9Ssthen d->nsec3->prehash_next = NULL; 180d3fecca9Ssthen d = n; 181d3fecca9Ssthen } 182d3fecca9Ssthen table->prehash_list = NULL; 183d3fecca9Ssthen } 184d3fecca9Ssthen 185d3fecca9Ssthen /** add domain to prehash list */ 186d3fecca9Ssthen void 187d3fecca9Ssthen prehash_add(domain_table_type* table, domain_type* domain) 188d3fecca9Ssthen { 189d3fecca9Ssthen if(domain_is_prehash(table, domain)) 190d3fecca9Ssthen return; 191d3fecca9Ssthen allocate_domain_nsec3(table, domain); 192d3fecca9Ssthen domain->nsec3->prehash_next = table->prehash_list; 193d3fecca9Ssthen if(table->prehash_list) 194d3fecca9Ssthen table->prehash_list->nsec3->prehash_prev = domain; 195d3fecca9Ssthen table->prehash_list = domain; 196d3fecca9Ssthen } 197d3fecca9Ssthen 198d3fecca9Ssthen /** remove domain from prehash list */ 199d3fecca9Ssthen void 200d3fecca9Ssthen prehash_del(domain_table_type* table, domain_type* domain) 201d3fecca9Ssthen { 202d3fecca9Ssthen if(domain->nsec3->prehash_next) 203d3fecca9Ssthen domain->nsec3->prehash_next->nsec3->prehash_prev = 204d3fecca9Ssthen domain->nsec3->prehash_prev; 205d3fecca9Ssthen if(domain->nsec3->prehash_prev) 206d3fecca9Ssthen domain->nsec3->prehash_prev->nsec3->prehash_next = 207d3fecca9Ssthen domain->nsec3->prehash_next; 208d3fecca9Ssthen else table->prehash_list = domain->nsec3->prehash_next; 209d3fecca9Ssthen domain->nsec3->prehash_next = NULL; 210d3fecca9Ssthen domain->nsec3->prehash_prev = NULL; 211d3fecca9Ssthen } 212d3fecca9Ssthen #endif /* NSEC3 */ 213d3fecca9Ssthen 214d3fecca9Ssthen /** perform domain name deletion */ 215d3fecca9Ssthen static void 216d3fecca9Ssthen do_deldomain(namedb_type* db, domain_type* domain) 217d3fecca9Ssthen { 218d3fecca9Ssthen assert(domain && domain->parent); /* exists and not root */ 219d3fecca9Ssthen /* first adjust the number list so that domain is the last one */ 220d3fecca9Ssthen numlist_make_last(db->domains, domain); 221d3fecca9Ssthen /* pop off the domain from the number list */ 222d3fecca9Ssthen (void)numlist_pop_last(db->domains); 223d3fecca9Ssthen 224d3fecca9Ssthen #ifdef NSEC3 225d3fecca9Ssthen /* if on prehash list, remove from prehash */ 226d3fecca9Ssthen if(domain_is_prehash(db->domains, domain)) 227d3fecca9Ssthen prehash_del(db->domains, domain); 228d3fecca9Ssthen 229d3fecca9Ssthen /* see if nsec3-nodes are used */ 230d3fecca9Ssthen if(domain->nsec3) { 231d3fecca9Ssthen if(domain->nsec3->nsec3_node.key) 232d3fecca9Ssthen zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain) 233d3fecca9Ssthen ->nsec3tree, &domain->nsec3->nsec3_node); 234ee5153b7Sflorian if(domain->nsec3->hash_wc) { 235ee5153b7Sflorian if(domain->nsec3->hash_wc->hash.node.key) 236d3fecca9Ssthen zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain) 237ee5153b7Sflorian ->hashtree, &domain->nsec3->hash_wc->hash.node); 238ee5153b7Sflorian if(domain->nsec3->hash_wc->wc.node.key) 239d3fecca9Ssthen zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain) 240ee5153b7Sflorian ->wchashtree, &domain->nsec3->hash_wc->wc.node); 241ee5153b7Sflorian } 242ee5153b7Sflorian if(domain->nsec3->ds_parent_hash && domain->nsec3->ds_parent_hash->node.key) 243d3fecca9Ssthen zone_del_domain_in_hash_tree(nsec3_tree_dszone(db, domain) 244ee5153b7Sflorian ->dshashtree, &domain->nsec3->ds_parent_hash->node); 245b90bb40eSsthen if(domain->nsec3->hash_wc) { 246b90bb40eSsthen region_recycle(db->domains->region, 247b90bb40eSsthen domain->nsec3->hash_wc, 248b90bb40eSsthen sizeof(nsec3_hash_wc_node_type)); 249b90bb40eSsthen } 250b90bb40eSsthen if(domain->nsec3->ds_parent_hash) { 251b90bb40eSsthen region_recycle(db->domains->region, 252b90bb40eSsthen domain->nsec3->ds_parent_hash, 253b90bb40eSsthen sizeof(nsec3_hash_node_type)); 254b90bb40eSsthen } 255d3fecca9Ssthen region_recycle(db->domains->region, domain->nsec3, 256d3fecca9Ssthen sizeof(struct nsec3_domain_data)); 257d3fecca9Ssthen } 258d3fecca9Ssthen #endif /* NSEC3 */ 259d3fecca9Ssthen 260d3fecca9Ssthen /* see if this domain is someones wildcard-child-closest-match, 261d3fecca9Ssthen * which can only be the parent, and then it should use the 262d3fecca9Ssthen * one-smaller than this domain as closest-match. */ 263d3fecca9Ssthen if(domain->parent->wildcard_child_closest_match == domain) 264d3fecca9Ssthen domain->parent->wildcard_child_closest_match = 26503739794Sbrad domain_previous_existing_child(domain); 266d3fecca9Ssthen 267d3fecca9Ssthen /* actual removal */ 268c1e73312Sflorian #ifdef USE_RADIX_TREE 269d3fecca9Ssthen radix_delete(db->domains->nametree, domain->rnode); 270c1e73312Sflorian #else 271c1e73312Sflorian rbtree_delete(db->domains->names_to_domains, domain->node.key); 272c1e73312Sflorian #endif 273c1e73312Sflorian region_recycle(db->domains->region, domain_dname(domain), 274c1e73312Sflorian dname_total_size(domain_dname(domain))); 275d3fecca9Ssthen region_recycle(db->domains->region, domain, sizeof(domain_type)); 276d3fecca9Ssthen } 277d3fecca9Ssthen 278d3fecca9Ssthen void 279d3fecca9Ssthen domain_table_deldomain(namedb_type* db, domain_type* domain) 280d3fecca9Ssthen { 281*a1bac035Sflorian domain_type* parent; 282*a1bac035Sflorian 283d3fecca9Ssthen while(domain_can_be_deleted(domain)) { 284*a1bac035Sflorian parent = domain->parent; 285d3fecca9Ssthen /* delete it */ 286d3fecca9Ssthen do_deldomain(db, domain); 287d3fecca9Ssthen /* test parent */ 288*a1bac035Sflorian domain = parent; 289d3fecca9Ssthen } 290d3fecca9Ssthen } 291d3fecca9Ssthen 292d3fecca9Ssthen /** clear hash tree */ 293d3fecca9Ssthen void 294fe5fe5f6Sflorian hash_tree_clear(rbtree_type* tree) 295d3fecca9Ssthen { 296fe5fe5f6Sflorian rbnode_type* n; 297d3fecca9Ssthen if(!tree) return; 298d3fecca9Ssthen 299d3fecca9Ssthen /* note that elements are no longer in the tree */ 300d3fecca9Ssthen for(n=rbtree_first(tree); n!=RBTREE_NULL; n=rbtree_next(n)) { 301d3fecca9Ssthen n->key = NULL; 302d3fecca9Ssthen } 303d3fecca9Ssthen tree->count = 0; 304d3fecca9Ssthen tree->root = RBTREE_NULL; 305d3fecca9Ssthen } 306d3fecca9Ssthen 307fe5fe5f6Sflorian void hash_tree_delete(region_type* region, rbtree_type* tree) 308d3fecca9Ssthen { 309fe5fe5f6Sflorian region_recycle(region, tree, sizeof(rbtree_type)); 310d3fecca9Ssthen } 311d3fecca9Ssthen 312d3fecca9Ssthen /** add domain nsec3 node to hashedspace tree */ 313fe5fe5f6Sflorian void zone_add_domain_in_hash_tree(region_type* region, rbtree_type** tree, 314d3fecca9Ssthen int (*cmpf)(const void*, const void*), 315fe5fe5f6Sflorian domain_type* domain, rbnode_type* node) 316d3fecca9Ssthen { 317d3fecca9Ssthen if(!*tree) 318d3fecca9Ssthen *tree = rbtree_create(region, cmpf); 319fb800cb5Sflorian if(node->key) return; 320fe5fe5f6Sflorian memset(node, 0, sizeof(rbnode_type)); 321d3fecca9Ssthen node->key = domain; 322d3fecca9Ssthen rbtree_insert(*tree, node); 323d3fecca9Ssthen } 324d3fecca9Ssthen 32562ac0c33Sjakob domain_table_type * 32662ac0c33Sjakob domain_table_create(region_type* region) 32762ac0c33Sjakob { 32862ac0c33Sjakob const dname_type* origin; 32962ac0c33Sjakob domain_table_type* result; 33062ac0c33Sjakob domain_type* root; 33162ac0c33Sjakob 33262ac0c33Sjakob assert(region); 33362ac0c33Sjakob 33462ac0c33Sjakob origin = dname_make(region, (uint8_t *) "", 0); 33562ac0c33Sjakob 33662ac0c33Sjakob root = (domain_type *) region_alloc(region, sizeof(domain_type)); 337c1e73312Sflorian #ifdef USE_RADIX_TREE 338c1e73312Sflorian root->dname 339c1e73312Sflorian #else 340c1e73312Sflorian root->node.key 341c1e73312Sflorian #endif 342c1e73312Sflorian = origin; 34362ac0c33Sjakob root->parent = NULL; 34462ac0c33Sjakob root->wildcard_child_closest_match = root; 34562ac0c33Sjakob root->rrsets = NULL; 34662ac0c33Sjakob root->number = 1; /* 0 is used for after header */ 347d3fecca9Ssthen root->usage = 1; /* do not delete root, ever */ 34862ac0c33Sjakob root->is_existing = 0; 34962ac0c33Sjakob root->is_apex = 0; 350d3fecca9Ssthen root->numlist_prev = NULL; 351d3fecca9Ssthen root->numlist_next = NULL; 35262ac0c33Sjakob #ifdef NSEC3 353d3fecca9Ssthen root->nsec3 = NULL; 354d3fecca9Ssthen #endif 35562ac0c33Sjakob 35662ac0c33Sjakob result = (domain_table_type *) region_alloc(region, 35762ac0c33Sjakob sizeof(domain_table_type)); 35862ac0c33Sjakob result->region = region; 359c1e73312Sflorian #ifdef USE_RADIX_TREE 360d3fecca9Ssthen result->nametree = radix_tree_create(region); 361d3fecca9Ssthen root->rnode = radname_insert(result->nametree, dname_name(root->dname), 362d3fecca9Ssthen root->dname->name_size, root); 363c1e73312Sflorian #else 364c1e73312Sflorian result->names_to_domains = rbtree_create( 365c1e73312Sflorian region, (int (*)(const void *, const void *)) dname_compare); 366fe5fe5f6Sflorian rbtree_insert(result->names_to_domains, (rbnode_type *) root); 367c1e73312Sflorian #endif 36862ac0c33Sjakob 36962ac0c33Sjakob result->root = root; 370d3fecca9Ssthen result->numlist_last = root; 371d3fecca9Ssthen #ifdef NSEC3 372d3fecca9Ssthen result->prehash_list = NULL; 373d3fecca9Ssthen #endif 37462ac0c33Sjakob 37562ac0c33Sjakob return result; 37662ac0c33Sjakob } 37762ac0c33Sjakob 37862ac0c33Sjakob int 37962ac0c33Sjakob domain_table_search(domain_table_type *table, 38062ac0c33Sjakob const dname_type *dname, 38162ac0c33Sjakob domain_type **closest_match, 38262ac0c33Sjakob domain_type **closest_encloser) 38362ac0c33Sjakob { 38462ac0c33Sjakob int exact; 38562ac0c33Sjakob uint8_t label_match_count; 38662ac0c33Sjakob 38762ac0c33Sjakob assert(table); 38862ac0c33Sjakob assert(dname); 38962ac0c33Sjakob assert(closest_match); 39062ac0c33Sjakob assert(closest_encloser); 39162ac0c33Sjakob 392c1e73312Sflorian #ifdef USE_RADIX_TREE 393d3fecca9Ssthen exact = radname_find_less_equal(table->nametree, dname_name(dname), 394d3fecca9Ssthen dname->name_size, (struct radnode**)closest_match); 395d3fecca9Ssthen *closest_match = (domain_type*)((*(struct radnode**)closest_match)->elem); 396c1e73312Sflorian #else 397fe5fe5f6Sflorian exact = rbtree_find_less_equal(table->names_to_domains, dname, (rbnode_type **) closest_match); 398c1e73312Sflorian #endif 39962ac0c33Sjakob assert(*closest_match); 40062ac0c33Sjakob 40162ac0c33Sjakob *closest_encloser = *closest_match; 40262ac0c33Sjakob 40362ac0c33Sjakob if (!exact) { 40462ac0c33Sjakob label_match_count = dname_label_match_count( 40562ac0c33Sjakob domain_dname(*closest_encloser), 40662ac0c33Sjakob dname); 40762ac0c33Sjakob assert(label_match_count < dname->label_count); 40862ac0c33Sjakob while (label_match_count < domain_dname(*closest_encloser)->label_count) { 40962ac0c33Sjakob (*closest_encloser) = (*closest_encloser)->parent; 41062ac0c33Sjakob assert(*closest_encloser); 41162ac0c33Sjakob } 41262ac0c33Sjakob } 41362ac0c33Sjakob 41462ac0c33Sjakob return exact; 41562ac0c33Sjakob } 41662ac0c33Sjakob 41762ac0c33Sjakob domain_type * 41862ac0c33Sjakob domain_table_find(domain_table_type* table, 41962ac0c33Sjakob const dname_type* dname) 42062ac0c33Sjakob { 42162ac0c33Sjakob domain_type* closest_match; 42262ac0c33Sjakob domain_type* closest_encloser; 42362ac0c33Sjakob int exact; 42462ac0c33Sjakob 42562ac0c33Sjakob exact = domain_table_search( 42662ac0c33Sjakob table, dname, &closest_match, &closest_encloser); 42762ac0c33Sjakob return exact ? closest_encloser : NULL; 42862ac0c33Sjakob } 42962ac0c33Sjakob 43062ac0c33Sjakob 43162ac0c33Sjakob domain_type * 43262ac0c33Sjakob domain_table_insert(domain_table_type* table, 43362ac0c33Sjakob const dname_type* dname) 43462ac0c33Sjakob { 43562ac0c33Sjakob domain_type* closest_match; 43662ac0c33Sjakob domain_type* closest_encloser; 43762ac0c33Sjakob domain_type* result; 43862ac0c33Sjakob int exact; 43962ac0c33Sjakob 44062ac0c33Sjakob assert(table); 44162ac0c33Sjakob assert(dname); 44262ac0c33Sjakob 44362ac0c33Sjakob exact = domain_table_search( 44462ac0c33Sjakob table, dname, &closest_match, &closest_encloser); 44562ac0c33Sjakob if (exact) { 44662ac0c33Sjakob result = closest_encloser; 44762ac0c33Sjakob } else { 44862ac0c33Sjakob assert(domain_dname(closest_encloser)->label_count < dname->label_count); 44962ac0c33Sjakob 45062ac0c33Sjakob /* Insert new node(s). */ 45162ac0c33Sjakob do { 45262ac0c33Sjakob result = allocate_domain_info(table, 45362ac0c33Sjakob dname, 45462ac0c33Sjakob closest_encloser); 455c1e73312Sflorian #ifdef USE_RADIX_TREE 456d3fecca9Ssthen result->rnode = radname_insert(table->nametree, 457d3fecca9Ssthen dname_name(result->dname), 458d3fecca9Ssthen result->dname->name_size, result); 459c1e73312Sflorian #else 460fe5fe5f6Sflorian rbtree_insert(table->names_to_domains, (rbnode_type *) result); 461c1e73312Sflorian #endif 46262ac0c33Sjakob 46362ac0c33Sjakob /* 46462ac0c33Sjakob * If the newly added domain name is larger 46562ac0c33Sjakob * than the parent's current 46662ac0c33Sjakob * wildcard_child_closest_match but smaller or 46762ac0c33Sjakob * equal to the wildcard domain name, update 46862ac0c33Sjakob * the parent's wildcard_child_closest_match 46962ac0c33Sjakob * field. 47062ac0c33Sjakob */ 47162ac0c33Sjakob if (label_compare(dname_name(domain_dname(result)), 47262ac0c33Sjakob (const uint8_t *) "\001*") <= 0 47362ac0c33Sjakob && dname_compare(domain_dname(result), 47462ac0c33Sjakob domain_dname(closest_encloser->wildcard_child_closest_match)) > 0) 47562ac0c33Sjakob { 47662ac0c33Sjakob closest_encloser->wildcard_child_closest_match 47762ac0c33Sjakob = result; 47862ac0c33Sjakob } 47962ac0c33Sjakob closest_encloser = result; 48062ac0c33Sjakob } while (domain_dname(closest_encloser)->label_count < dname->label_count); 48162ac0c33Sjakob } 48262ac0c33Sjakob 48362ac0c33Sjakob return result; 48462ac0c33Sjakob } 48562ac0c33Sjakob 48603739794Sbrad domain_type *domain_previous_existing_child(domain_type* domain) 48703739794Sbrad { 48803739794Sbrad domain_type* parent = domain->parent; 48903739794Sbrad domain = domain_previous(domain); 49003739794Sbrad while(domain && !domain->is_existing) { 49103739794Sbrad if(domain == parent) /* do not walk back above parent */ 49203739794Sbrad return parent; 49303739794Sbrad domain = domain_previous(domain); 49403739794Sbrad } 49503739794Sbrad return domain; 49603739794Sbrad } 49762ac0c33Sjakob 49862ac0c33Sjakob void 49962ac0c33Sjakob domain_add_rrset(domain_type* domain, rrset_type* rrset) 50062ac0c33Sjakob { 50162ac0c33Sjakob #if 0 /* fast */ 50262ac0c33Sjakob rrset->next = domain->rrsets; 50362ac0c33Sjakob domain->rrsets = rrset; 50462ac0c33Sjakob #else 50562ac0c33Sjakob /* preserve ordering, add at end */ 50662ac0c33Sjakob rrset_type** p = &domain->rrsets; 50762ac0c33Sjakob while(*p) 50862ac0c33Sjakob p = &((*p)->next); 50962ac0c33Sjakob *p = rrset; 51062ac0c33Sjakob rrset->next = 0; 51162ac0c33Sjakob #endif 51262ac0c33Sjakob 51362ac0c33Sjakob while (domain && !domain->is_existing) { 51462ac0c33Sjakob domain->is_existing = 1; 51503739794Sbrad /* does this name in existance update the parent's 51603739794Sbrad * wildcard closest match? */ 51703739794Sbrad if(domain->parent 51803739794Sbrad && label_compare(dname_name(domain_dname(domain)), 51903739794Sbrad (const uint8_t *) "\001*") <= 0 52003739794Sbrad && dname_compare(domain_dname(domain), 52103739794Sbrad domain_dname(domain->parent->wildcard_child_closest_match)) > 0) { 52203739794Sbrad domain->parent->wildcard_child_closest_match = domain; 52303739794Sbrad } 52462ac0c33Sjakob domain = domain->parent; 52562ac0c33Sjakob } 52662ac0c33Sjakob } 52762ac0c33Sjakob 52862ac0c33Sjakob 52962ac0c33Sjakob rrset_type * 53062ac0c33Sjakob domain_find_rrset(domain_type* domain, zone_type* zone, uint16_t type) 53162ac0c33Sjakob { 53262ac0c33Sjakob rrset_type* result = domain->rrsets; 53362ac0c33Sjakob 53462ac0c33Sjakob while (result) { 53562ac0c33Sjakob if (result->zone == zone && rrset_rrtype(result) == type) { 53662ac0c33Sjakob return result; 53762ac0c33Sjakob } 53862ac0c33Sjakob result = result->next; 53962ac0c33Sjakob } 54062ac0c33Sjakob return NULL; 54162ac0c33Sjakob } 54262ac0c33Sjakob 54362ac0c33Sjakob rrset_type * 54462ac0c33Sjakob domain_find_any_rrset(domain_type* domain, zone_type* zone) 54562ac0c33Sjakob { 54662ac0c33Sjakob rrset_type* result = domain->rrsets; 54762ac0c33Sjakob 54862ac0c33Sjakob while (result) { 54962ac0c33Sjakob if (result->zone == zone) { 55062ac0c33Sjakob return result; 55162ac0c33Sjakob } 55262ac0c33Sjakob result = result->next; 55362ac0c33Sjakob } 55462ac0c33Sjakob return NULL; 55562ac0c33Sjakob } 55662ac0c33Sjakob 55762ac0c33Sjakob zone_type * 558cbbc2d6cSbrad domain_find_zone(namedb_type* db, domain_type* domain) 55962ac0c33Sjakob { 56062ac0c33Sjakob rrset_type* rrset; 56162ac0c33Sjakob while (domain) { 562cbbc2d6cSbrad if(domain->is_apex) { 56362ac0c33Sjakob for (rrset = domain->rrsets; rrset; rrset = rrset->next) { 56462ac0c33Sjakob if (rrset_rrtype(rrset) == TYPE_SOA) { 56562ac0c33Sjakob return rrset->zone; 56662ac0c33Sjakob } 56762ac0c33Sjakob } 568cbbc2d6cSbrad return namedb_find_zone(db, domain_dname(domain)); 569cbbc2d6cSbrad } 57062ac0c33Sjakob domain = domain->parent; 57162ac0c33Sjakob } 57262ac0c33Sjakob return NULL; 57362ac0c33Sjakob } 57462ac0c33Sjakob 57562ac0c33Sjakob zone_type * 5766e9bf1eeSflorian domain_find_parent_zone(namedb_type* db, zone_type* zone) 57762ac0c33Sjakob { 57862ac0c33Sjakob rrset_type* rrset; 57962ac0c33Sjakob 58062ac0c33Sjakob assert(zone); 58162ac0c33Sjakob 58262ac0c33Sjakob for (rrset = zone->apex->rrsets; rrset; rrset = rrset->next) { 58362ac0c33Sjakob if (rrset->zone != zone && rrset_rrtype(rrset) == TYPE_NS) { 58462ac0c33Sjakob return rrset->zone; 58562ac0c33Sjakob } 58662ac0c33Sjakob } 5876e9bf1eeSflorian /* the NS record in the parent zone above this zone is not present, 5886e9bf1eeSflorian * workaround to find that parent zone anyway */ 5896e9bf1eeSflorian if(zone->apex->parent) 5906e9bf1eeSflorian return domain_find_zone(db, zone->apex->parent); 59162ac0c33Sjakob return NULL; 59262ac0c33Sjakob } 59362ac0c33Sjakob 59462ac0c33Sjakob domain_type * 59562ac0c33Sjakob domain_find_ns_rrsets(domain_type* domain, zone_type* zone, rrset_type **ns) 59662ac0c33Sjakob { 59762ac0c33Sjakob while (domain && domain != zone->apex) { 59862ac0c33Sjakob *ns = domain_find_rrset(domain, zone, TYPE_NS); 59962ac0c33Sjakob if (*ns) 60062ac0c33Sjakob return domain; 60162ac0c33Sjakob domain = domain->parent; 60262ac0c33Sjakob } 60362ac0c33Sjakob 60462ac0c33Sjakob *ns = NULL; 60562ac0c33Sjakob return NULL; 60662ac0c33Sjakob } 60762ac0c33Sjakob 608275a8d89Sflorian domain_type * 609275a8d89Sflorian find_dname_above(domain_type* domain, zone_type* zone) 610275a8d89Sflorian { 611275a8d89Sflorian domain_type* d = domain->parent; 612275a8d89Sflorian while(d && d != zone->apex) { 613275a8d89Sflorian if(domain_find_rrset(d, zone, TYPE_DNAME)) 614275a8d89Sflorian return d; 615275a8d89Sflorian d = d->parent; 616275a8d89Sflorian } 617275a8d89Sflorian return NULL; 618275a8d89Sflorian } 619275a8d89Sflorian 62062ac0c33Sjakob int 62162ac0c33Sjakob domain_is_glue(domain_type* domain, zone_type* zone) 62262ac0c33Sjakob { 62362ac0c33Sjakob rrset_type* unused; 62462ac0c33Sjakob domain_type* ns_domain = domain_find_ns_rrsets(domain, zone, &unused); 62562ac0c33Sjakob return (ns_domain != NULL && 62662ac0c33Sjakob domain_find_rrset(ns_domain, zone, TYPE_SOA) == NULL); 62762ac0c33Sjakob } 62862ac0c33Sjakob 62962ac0c33Sjakob domain_type * 63062ac0c33Sjakob domain_wildcard_child(domain_type* domain) 63162ac0c33Sjakob { 63262ac0c33Sjakob domain_type* wildcard_child; 63362ac0c33Sjakob 63462ac0c33Sjakob assert(domain); 63562ac0c33Sjakob assert(domain->wildcard_child_closest_match); 63662ac0c33Sjakob 63762ac0c33Sjakob wildcard_child = domain->wildcard_child_closest_match; 63862ac0c33Sjakob if (wildcard_child != domain 63962ac0c33Sjakob && label_is_wildcard(dname_name(domain_dname(wildcard_child)))) 64062ac0c33Sjakob { 64162ac0c33Sjakob return wildcard_child; 64262ac0c33Sjakob } else { 64362ac0c33Sjakob return NULL; 64462ac0c33Sjakob } 64562ac0c33Sjakob } 64662ac0c33Sjakob 64762ac0c33Sjakob int 64862ac0c33Sjakob zone_is_secure(zone_type* zone) 64962ac0c33Sjakob { 65062ac0c33Sjakob assert(zone); 65162ac0c33Sjakob return zone->is_secure; 65262ac0c33Sjakob } 65362ac0c33Sjakob 65462ac0c33Sjakob uint16_t 65562ac0c33Sjakob rr_rrsig_type_covered(rr_type* rr) 65662ac0c33Sjakob { 65762ac0c33Sjakob assert(rr->type == TYPE_RRSIG); 65862ac0c33Sjakob assert(rr->rdata_count > 0); 65962ac0c33Sjakob assert(rdata_atom_size(rr->rdatas[0]) == sizeof(uint16_t)); 66062ac0c33Sjakob 66162ac0c33Sjakob return ntohs(* (uint16_t *) rdata_atom_data(rr->rdatas[0])); 66262ac0c33Sjakob } 66362ac0c33Sjakob 66462ac0c33Sjakob zone_type * 665d3fecca9Ssthen namedb_find_zone(namedb_type* db, const dname_type* dname) 66662ac0c33Sjakob { 667d3fecca9Ssthen struct radnode* n = radname_search(db->zonetree, dname_name(dname), 668d3fecca9Ssthen dname->name_size); 669d3fecca9Ssthen if(n) return (zone_type*)n->elem; 670d3fecca9Ssthen return NULL; 67162ac0c33Sjakob } 67262ac0c33Sjakob 67362ac0c33Sjakob rrset_type * 67462ac0c33Sjakob domain_find_non_cname_rrset(domain_type* domain, zone_type* zone) 67562ac0c33Sjakob { 67662ac0c33Sjakob /* find any rrset type that is not allowed next to a CNAME */ 67762ac0c33Sjakob /* nothing is allowed next to a CNAME, except RRSIG, NSEC, NSEC3 */ 67862ac0c33Sjakob rrset_type *result = domain->rrsets; 67962ac0c33Sjakob 68062ac0c33Sjakob while (result) { 68162ac0c33Sjakob if (result->zone == zone && /* here is the list of exceptions*/ 68262ac0c33Sjakob rrset_rrtype(result) != TYPE_CNAME && 68362ac0c33Sjakob rrset_rrtype(result) != TYPE_RRSIG && 68462ac0c33Sjakob rrset_rrtype(result) != TYPE_NXT && 68562ac0c33Sjakob rrset_rrtype(result) != TYPE_SIG && 68662ac0c33Sjakob rrset_rrtype(result) != TYPE_NSEC && 68762ac0c33Sjakob rrset_rrtype(result) != TYPE_NSEC3 ) { 68862ac0c33Sjakob return result; 68962ac0c33Sjakob } 69062ac0c33Sjakob result = result->next; 69162ac0c33Sjakob } 69262ac0c33Sjakob return NULL; 69362ac0c33Sjakob } 6940c2b6c02Sjakob 6950c2b6c02Sjakob int 696d3fecca9Ssthen namedb_lookup(struct namedb* db, 697d3fecca9Ssthen const dname_type* dname, 698d3fecca9Ssthen domain_type **closest_match, 699d3fecca9Ssthen domain_type **closest_encloser) 7000c2b6c02Sjakob { 701d3fecca9Ssthen return domain_table_search( 702d3fecca9Ssthen db->domains, dname, closest_match, closest_encloser); 7030c2b6c02Sjakob } 704