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 { 281a1bac035Sflorian domain_type* parent; 282a1bac035Sflorian 283d3fecca9Ssthen while(domain_can_be_deleted(domain)) { 284a1bac035Sflorian parent = domain->parent; 285d3fecca9Ssthen /* delete it */ 286d3fecca9Ssthen do_deldomain(db, domain); 287d3fecca9Ssthen /* test parent */ 288a1bac035Sflorian domain = parent; 289d3fecca9Ssthen } 290d3fecca9Ssthen } 291d3fecca9Ssthen 292fe5fe5f6Sflorian void hash_tree_delete(region_type* region, rbtree_type* tree) 293d3fecca9Ssthen { 294fe5fe5f6Sflorian region_recycle(region, tree, sizeof(rbtree_type)); 295d3fecca9Ssthen } 296d3fecca9Ssthen 297d3fecca9Ssthen /** add domain nsec3 node to hashedspace tree */ 298fe5fe5f6Sflorian void zone_add_domain_in_hash_tree(region_type* region, rbtree_type** tree, 299d3fecca9Ssthen int (*cmpf)(const void*, const void*), 300fe5fe5f6Sflorian domain_type* domain, rbnode_type* node) 301d3fecca9Ssthen { 302d3fecca9Ssthen if(!*tree) 303d3fecca9Ssthen *tree = rbtree_create(region, cmpf); 304*ac5517e4Sflorian if(node->key && node->key == domain 305*ac5517e4Sflorian && rbtree_search(*tree, domain) == node) 306*ac5517e4Sflorian return; 307fe5fe5f6Sflorian memset(node, 0, sizeof(rbnode_type)); 308d3fecca9Ssthen node->key = domain; 309d3fecca9Ssthen rbtree_insert(*tree, node); 310d3fecca9Ssthen } 311d3fecca9Ssthen 31262ac0c33Sjakob domain_table_type * 31362ac0c33Sjakob domain_table_create(region_type* region) 31462ac0c33Sjakob { 31562ac0c33Sjakob const dname_type* origin; 31662ac0c33Sjakob domain_table_type* result; 31762ac0c33Sjakob domain_type* root; 31862ac0c33Sjakob 31962ac0c33Sjakob assert(region); 32062ac0c33Sjakob 32162ac0c33Sjakob origin = dname_make(region, (uint8_t *) "", 0); 32262ac0c33Sjakob 32362ac0c33Sjakob root = (domain_type *) region_alloc(region, sizeof(domain_type)); 324c1e73312Sflorian #ifdef USE_RADIX_TREE 325c1e73312Sflorian root->dname 326c1e73312Sflorian #else 327c1e73312Sflorian root->node.key 328c1e73312Sflorian #endif 329c1e73312Sflorian = origin; 33062ac0c33Sjakob root->parent = NULL; 33162ac0c33Sjakob root->wildcard_child_closest_match = root; 33262ac0c33Sjakob root->rrsets = NULL; 33362ac0c33Sjakob root->number = 1; /* 0 is used for after header */ 334d3fecca9Ssthen root->usage = 1; /* do not delete root, ever */ 33562ac0c33Sjakob root->is_existing = 0; 33662ac0c33Sjakob root->is_apex = 0; 337d3fecca9Ssthen root->numlist_prev = NULL; 338d3fecca9Ssthen root->numlist_next = NULL; 33962ac0c33Sjakob #ifdef NSEC3 340d3fecca9Ssthen root->nsec3 = NULL; 341d3fecca9Ssthen #endif 34262ac0c33Sjakob 34362ac0c33Sjakob result = (domain_table_type *) region_alloc(region, 34462ac0c33Sjakob sizeof(domain_table_type)); 34562ac0c33Sjakob result->region = region; 346c1e73312Sflorian #ifdef USE_RADIX_TREE 347d3fecca9Ssthen result->nametree = radix_tree_create(region); 348d3fecca9Ssthen root->rnode = radname_insert(result->nametree, dname_name(root->dname), 349d3fecca9Ssthen root->dname->name_size, root); 350c1e73312Sflorian #else 351c1e73312Sflorian result->names_to_domains = rbtree_create( 352c1e73312Sflorian region, (int (*)(const void *, const void *)) dname_compare); 353fe5fe5f6Sflorian rbtree_insert(result->names_to_domains, (rbnode_type *) root); 354c1e73312Sflorian #endif 35562ac0c33Sjakob 35662ac0c33Sjakob result->root = root; 357d3fecca9Ssthen result->numlist_last = root; 358d3fecca9Ssthen #ifdef NSEC3 359d3fecca9Ssthen result->prehash_list = NULL; 360d3fecca9Ssthen #endif 36162ac0c33Sjakob 36262ac0c33Sjakob return result; 36362ac0c33Sjakob } 36462ac0c33Sjakob 36562ac0c33Sjakob int 36662ac0c33Sjakob domain_table_search(domain_table_type *table, 36762ac0c33Sjakob const dname_type *dname, 36862ac0c33Sjakob domain_type **closest_match, 36962ac0c33Sjakob domain_type **closest_encloser) 37062ac0c33Sjakob { 37162ac0c33Sjakob int exact; 37262ac0c33Sjakob uint8_t label_match_count; 37362ac0c33Sjakob 37462ac0c33Sjakob assert(table); 37562ac0c33Sjakob assert(dname); 37662ac0c33Sjakob assert(closest_match); 37762ac0c33Sjakob assert(closest_encloser); 37862ac0c33Sjakob 379c1e73312Sflorian #ifdef USE_RADIX_TREE 380d3fecca9Ssthen exact = radname_find_less_equal(table->nametree, dname_name(dname), 381d3fecca9Ssthen dname->name_size, (struct radnode**)closest_match); 382d3fecca9Ssthen *closest_match = (domain_type*)((*(struct radnode**)closest_match)->elem); 383c1e73312Sflorian #else 384fe5fe5f6Sflorian exact = rbtree_find_less_equal(table->names_to_domains, dname, (rbnode_type **) closest_match); 385c1e73312Sflorian #endif 38662ac0c33Sjakob assert(*closest_match); 38762ac0c33Sjakob 38862ac0c33Sjakob *closest_encloser = *closest_match; 38962ac0c33Sjakob 39062ac0c33Sjakob if (!exact) { 39162ac0c33Sjakob label_match_count = dname_label_match_count( 39262ac0c33Sjakob domain_dname(*closest_encloser), 39362ac0c33Sjakob dname); 39462ac0c33Sjakob assert(label_match_count < dname->label_count); 39562ac0c33Sjakob while (label_match_count < domain_dname(*closest_encloser)->label_count) { 39662ac0c33Sjakob (*closest_encloser) = (*closest_encloser)->parent; 39762ac0c33Sjakob assert(*closest_encloser); 39862ac0c33Sjakob } 39962ac0c33Sjakob } 40062ac0c33Sjakob 40162ac0c33Sjakob return exact; 40262ac0c33Sjakob } 40362ac0c33Sjakob 40462ac0c33Sjakob domain_type * 40562ac0c33Sjakob domain_table_find(domain_table_type* table, 40662ac0c33Sjakob const dname_type* dname) 40762ac0c33Sjakob { 40862ac0c33Sjakob domain_type* closest_match; 40962ac0c33Sjakob domain_type* closest_encloser; 41062ac0c33Sjakob int exact; 41162ac0c33Sjakob 41262ac0c33Sjakob exact = domain_table_search( 41362ac0c33Sjakob table, dname, &closest_match, &closest_encloser); 41462ac0c33Sjakob return exact ? closest_encloser : NULL; 41562ac0c33Sjakob } 41662ac0c33Sjakob 41762ac0c33Sjakob 41862ac0c33Sjakob domain_type * 41962ac0c33Sjakob domain_table_insert(domain_table_type* table, 42062ac0c33Sjakob const dname_type* dname) 42162ac0c33Sjakob { 42262ac0c33Sjakob domain_type* closest_match; 42362ac0c33Sjakob domain_type* closest_encloser; 42462ac0c33Sjakob domain_type* result; 42562ac0c33Sjakob int exact; 42662ac0c33Sjakob 42762ac0c33Sjakob assert(table); 42862ac0c33Sjakob assert(dname); 42962ac0c33Sjakob 43062ac0c33Sjakob exact = domain_table_search( 43162ac0c33Sjakob table, dname, &closest_match, &closest_encloser); 43262ac0c33Sjakob if (exact) { 43362ac0c33Sjakob result = closest_encloser; 43462ac0c33Sjakob } else { 43562ac0c33Sjakob assert(domain_dname(closest_encloser)->label_count < dname->label_count); 43662ac0c33Sjakob 43762ac0c33Sjakob /* Insert new node(s). */ 43862ac0c33Sjakob do { 43962ac0c33Sjakob result = allocate_domain_info(table, 44062ac0c33Sjakob dname, 44162ac0c33Sjakob closest_encloser); 442c1e73312Sflorian #ifdef USE_RADIX_TREE 443d3fecca9Ssthen result->rnode = radname_insert(table->nametree, 444d3fecca9Ssthen dname_name(result->dname), 445d3fecca9Ssthen result->dname->name_size, result); 446c1e73312Sflorian #else 447fe5fe5f6Sflorian rbtree_insert(table->names_to_domains, (rbnode_type *) result); 448c1e73312Sflorian #endif 44962ac0c33Sjakob 45062ac0c33Sjakob /* 45162ac0c33Sjakob * If the newly added domain name is larger 45262ac0c33Sjakob * than the parent's current 45362ac0c33Sjakob * wildcard_child_closest_match but smaller or 45462ac0c33Sjakob * equal to the wildcard domain name, update 45562ac0c33Sjakob * the parent's wildcard_child_closest_match 45662ac0c33Sjakob * field. 45762ac0c33Sjakob */ 45862ac0c33Sjakob if (label_compare(dname_name(domain_dname(result)), 45962ac0c33Sjakob (const uint8_t *) "\001*") <= 0 46062ac0c33Sjakob && dname_compare(domain_dname(result), 46162ac0c33Sjakob domain_dname(closest_encloser->wildcard_child_closest_match)) > 0) 46262ac0c33Sjakob { 46362ac0c33Sjakob closest_encloser->wildcard_child_closest_match 46462ac0c33Sjakob = result; 46562ac0c33Sjakob } 46662ac0c33Sjakob closest_encloser = result; 46762ac0c33Sjakob } while (domain_dname(closest_encloser)->label_count < dname->label_count); 46862ac0c33Sjakob } 46962ac0c33Sjakob 47062ac0c33Sjakob return result; 47162ac0c33Sjakob } 47262ac0c33Sjakob 47303739794Sbrad domain_type *domain_previous_existing_child(domain_type* domain) 47403739794Sbrad { 47503739794Sbrad domain_type* parent = domain->parent; 47603739794Sbrad domain = domain_previous(domain); 47703739794Sbrad while(domain && !domain->is_existing) { 47803739794Sbrad if(domain == parent) /* do not walk back above parent */ 47903739794Sbrad return parent; 48003739794Sbrad domain = domain_previous(domain); 48103739794Sbrad } 48203739794Sbrad return domain; 48303739794Sbrad } 48462ac0c33Sjakob 48562ac0c33Sjakob void 48662ac0c33Sjakob domain_add_rrset(domain_type* domain, rrset_type* rrset) 48762ac0c33Sjakob { 48862ac0c33Sjakob #if 0 /* fast */ 48962ac0c33Sjakob rrset->next = domain->rrsets; 49062ac0c33Sjakob domain->rrsets = rrset; 49162ac0c33Sjakob #else 49262ac0c33Sjakob /* preserve ordering, add at end */ 49362ac0c33Sjakob rrset_type** p = &domain->rrsets; 49462ac0c33Sjakob while(*p) 49562ac0c33Sjakob p = &((*p)->next); 49662ac0c33Sjakob *p = rrset; 49762ac0c33Sjakob rrset->next = 0; 49862ac0c33Sjakob #endif 49962ac0c33Sjakob 50062ac0c33Sjakob while (domain && !domain->is_existing) { 50162ac0c33Sjakob domain->is_existing = 1; 50203739794Sbrad /* does this name in existance update the parent's 50303739794Sbrad * wildcard closest match? */ 50403739794Sbrad if(domain->parent 50503739794Sbrad && label_compare(dname_name(domain_dname(domain)), 50603739794Sbrad (const uint8_t *) "\001*") <= 0 50703739794Sbrad && dname_compare(domain_dname(domain), 50803739794Sbrad domain_dname(domain->parent->wildcard_child_closest_match)) > 0) { 50903739794Sbrad domain->parent->wildcard_child_closest_match = domain; 51003739794Sbrad } 51162ac0c33Sjakob domain = domain->parent; 51262ac0c33Sjakob } 51362ac0c33Sjakob } 51462ac0c33Sjakob 51562ac0c33Sjakob 51662ac0c33Sjakob rrset_type * 51762ac0c33Sjakob domain_find_rrset(domain_type* domain, zone_type* zone, uint16_t type) 51862ac0c33Sjakob { 51962ac0c33Sjakob rrset_type* result = domain->rrsets; 52062ac0c33Sjakob 52162ac0c33Sjakob while (result) { 52262ac0c33Sjakob if (result->zone == zone && rrset_rrtype(result) == type) { 52362ac0c33Sjakob return result; 52462ac0c33Sjakob } 52562ac0c33Sjakob result = result->next; 52662ac0c33Sjakob } 52762ac0c33Sjakob return NULL; 52862ac0c33Sjakob } 52962ac0c33Sjakob 53062ac0c33Sjakob rrset_type * 53162ac0c33Sjakob domain_find_any_rrset(domain_type* domain, zone_type* zone) 53262ac0c33Sjakob { 53362ac0c33Sjakob rrset_type* result = domain->rrsets; 53462ac0c33Sjakob 53562ac0c33Sjakob while (result) { 53662ac0c33Sjakob if (result->zone == zone) { 53762ac0c33Sjakob return result; 53862ac0c33Sjakob } 53962ac0c33Sjakob result = result->next; 54062ac0c33Sjakob } 54162ac0c33Sjakob return NULL; 54262ac0c33Sjakob } 54362ac0c33Sjakob 54462ac0c33Sjakob zone_type * 545cbbc2d6cSbrad domain_find_zone(namedb_type* db, domain_type* domain) 54662ac0c33Sjakob { 54762ac0c33Sjakob rrset_type* rrset; 54862ac0c33Sjakob while (domain) { 549cbbc2d6cSbrad if(domain->is_apex) { 55062ac0c33Sjakob for (rrset = domain->rrsets; rrset; rrset = rrset->next) { 55162ac0c33Sjakob if (rrset_rrtype(rrset) == TYPE_SOA) { 55262ac0c33Sjakob return rrset->zone; 55362ac0c33Sjakob } 55462ac0c33Sjakob } 555cbbc2d6cSbrad return namedb_find_zone(db, domain_dname(domain)); 556cbbc2d6cSbrad } 55762ac0c33Sjakob domain = domain->parent; 55862ac0c33Sjakob } 55962ac0c33Sjakob return NULL; 56062ac0c33Sjakob } 56162ac0c33Sjakob 56262ac0c33Sjakob zone_type * 5636e9bf1eeSflorian domain_find_parent_zone(namedb_type* db, zone_type* zone) 56462ac0c33Sjakob { 56562ac0c33Sjakob rrset_type* rrset; 56662ac0c33Sjakob 56762ac0c33Sjakob assert(zone); 56862ac0c33Sjakob 56962ac0c33Sjakob for (rrset = zone->apex->rrsets; rrset; rrset = rrset->next) { 57062ac0c33Sjakob if (rrset->zone != zone && rrset_rrtype(rrset) == TYPE_NS) { 57162ac0c33Sjakob return rrset->zone; 57262ac0c33Sjakob } 57362ac0c33Sjakob } 5746e9bf1eeSflorian /* the NS record in the parent zone above this zone is not present, 5756e9bf1eeSflorian * workaround to find that parent zone anyway */ 5766e9bf1eeSflorian if(zone->apex->parent) 5776e9bf1eeSflorian return domain_find_zone(db, zone->apex->parent); 57862ac0c33Sjakob return NULL; 57962ac0c33Sjakob } 58062ac0c33Sjakob 58162ac0c33Sjakob domain_type * 58262ac0c33Sjakob domain_find_ns_rrsets(domain_type* domain, zone_type* zone, rrset_type **ns) 58362ac0c33Sjakob { 58462ac0c33Sjakob while (domain && domain != zone->apex) { 58562ac0c33Sjakob *ns = domain_find_rrset(domain, zone, TYPE_NS); 58662ac0c33Sjakob if (*ns) 58762ac0c33Sjakob return domain; 58862ac0c33Sjakob domain = domain->parent; 58962ac0c33Sjakob } 59062ac0c33Sjakob 59162ac0c33Sjakob *ns = NULL; 59262ac0c33Sjakob return NULL; 59362ac0c33Sjakob } 59462ac0c33Sjakob 595275a8d89Sflorian domain_type * 596275a8d89Sflorian find_dname_above(domain_type* domain, zone_type* zone) 597275a8d89Sflorian { 598275a8d89Sflorian domain_type* d = domain->parent; 599275a8d89Sflorian while(d && d != zone->apex) { 600275a8d89Sflorian if(domain_find_rrset(d, zone, TYPE_DNAME)) 601275a8d89Sflorian return d; 602275a8d89Sflorian d = d->parent; 603275a8d89Sflorian } 604275a8d89Sflorian return NULL; 605275a8d89Sflorian } 606275a8d89Sflorian 60762ac0c33Sjakob int 60862ac0c33Sjakob domain_is_glue(domain_type* domain, zone_type* zone) 60962ac0c33Sjakob { 61062ac0c33Sjakob rrset_type* unused; 61162ac0c33Sjakob domain_type* ns_domain = domain_find_ns_rrsets(domain, zone, &unused); 61262ac0c33Sjakob return (ns_domain != NULL && 61362ac0c33Sjakob domain_find_rrset(ns_domain, zone, TYPE_SOA) == NULL); 61462ac0c33Sjakob } 61562ac0c33Sjakob 61662ac0c33Sjakob domain_type * 61762ac0c33Sjakob domain_wildcard_child(domain_type* domain) 61862ac0c33Sjakob { 61962ac0c33Sjakob domain_type* wildcard_child; 62062ac0c33Sjakob 62162ac0c33Sjakob assert(domain); 62262ac0c33Sjakob assert(domain->wildcard_child_closest_match); 62362ac0c33Sjakob 62462ac0c33Sjakob wildcard_child = domain->wildcard_child_closest_match; 62562ac0c33Sjakob if (wildcard_child != domain 62662ac0c33Sjakob && label_is_wildcard(dname_name(domain_dname(wildcard_child)))) 62762ac0c33Sjakob { 62862ac0c33Sjakob return wildcard_child; 62962ac0c33Sjakob } else { 63062ac0c33Sjakob return NULL; 63162ac0c33Sjakob } 63262ac0c33Sjakob } 63362ac0c33Sjakob 63462ac0c33Sjakob int 63562ac0c33Sjakob zone_is_secure(zone_type* zone) 63662ac0c33Sjakob { 63762ac0c33Sjakob assert(zone); 63862ac0c33Sjakob return zone->is_secure; 63962ac0c33Sjakob } 64062ac0c33Sjakob 64162ac0c33Sjakob uint16_t 64262ac0c33Sjakob rr_rrsig_type_covered(rr_type* rr) 64362ac0c33Sjakob { 64462ac0c33Sjakob assert(rr->type == TYPE_RRSIG); 64562ac0c33Sjakob assert(rr->rdata_count > 0); 64662ac0c33Sjakob assert(rdata_atom_size(rr->rdatas[0]) == sizeof(uint16_t)); 64762ac0c33Sjakob 64862ac0c33Sjakob return ntohs(* (uint16_t *) rdata_atom_data(rr->rdatas[0])); 64962ac0c33Sjakob } 65062ac0c33Sjakob 65162ac0c33Sjakob zone_type * 652d3fecca9Ssthen namedb_find_zone(namedb_type* db, const dname_type* dname) 65362ac0c33Sjakob { 654d3fecca9Ssthen struct radnode* n = radname_search(db->zonetree, dname_name(dname), 655d3fecca9Ssthen dname->name_size); 656d3fecca9Ssthen if(n) return (zone_type*)n->elem; 657d3fecca9Ssthen return NULL; 65862ac0c33Sjakob } 65962ac0c33Sjakob 66062ac0c33Sjakob rrset_type * 66162ac0c33Sjakob domain_find_non_cname_rrset(domain_type* domain, zone_type* zone) 66262ac0c33Sjakob { 66362ac0c33Sjakob /* find any rrset type that is not allowed next to a CNAME */ 66462ac0c33Sjakob /* nothing is allowed next to a CNAME, except RRSIG, NSEC, NSEC3 */ 66562ac0c33Sjakob rrset_type *result = domain->rrsets; 66662ac0c33Sjakob 66762ac0c33Sjakob while (result) { 66862ac0c33Sjakob if (result->zone == zone && /* here is the list of exceptions*/ 66962ac0c33Sjakob rrset_rrtype(result) != TYPE_CNAME && 67062ac0c33Sjakob rrset_rrtype(result) != TYPE_RRSIG && 67162ac0c33Sjakob rrset_rrtype(result) != TYPE_NXT && 67262ac0c33Sjakob rrset_rrtype(result) != TYPE_SIG && 67362ac0c33Sjakob rrset_rrtype(result) != TYPE_NSEC && 67462ac0c33Sjakob rrset_rrtype(result) != TYPE_NSEC3 ) { 67562ac0c33Sjakob return result; 67662ac0c33Sjakob } 67762ac0c33Sjakob result = result->next; 67862ac0c33Sjakob } 67962ac0c33Sjakob return NULL; 68062ac0c33Sjakob } 6810c2b6c02Sjakob 6820c2b6c02Sjakob int 683d3fecca9Ssthen namedb_lookup(struct namedb* db, 684d3fecca9Ssthen const dname_type* dname, 685d3fecca9Ssthen domain_type **closest_match, 686d3fecca9Ssthen domain_type **closest_encloser) 6870c2b6c02Sjakob { 688d3fecca9Ssthen return domain_table_search( 689d3fecca9Ssthen db->domains, dname, closest_match, closest_encloser); 6900c2b6c02Sjakob } 691308d2509Sflorian 692308d2509Sflorian void zone_rr_iter_init(struct zone_rr_iter *iter, struct zone *zone) 693308d2509Sflorian { 694308d2509Sflorian assert(iter != NULL); 695308d2509Sflorian assert(zone != NULL); 696308d2509Sflorian memset(iter, 0, sizeof(*iter)); 697308d2509Sflorian iter->zone = zone; 698308d2509Sflorian } 699308d2509Sflorian 700308d2509Sflorian rr_type *zone_rr_iter_next(struct zone_rr_iter *iter) 701308d2509Sflorian { 702308d2509Sflorian assert(iter != NULL); 703308d2509Sflorian assert(iter->zone != NULL); 704308d2509Sflorian 705308d2509Sflorian if(iter->index == -1) { 706308d2509Sflorian assert(iter->domain == NULL); 707308d2509Sflorian assert(iter->rrset == NULL); 708308d2509Sflorian return NULL; 709308d2509Sflorian } else if(iter->rrset == NULL) { 710308d2509Sflorian /* ensure SOA RR is returned first */ 711308d2509Sflorian assert(iter->domain == NULL); 712308d2509Sflorian assert(iter->index == 0); 713308d2509Sflorian iter->rrset = iter->zone->soa_rrset; 714308d2509Sflorian } 715308d2509Sflorian 716308d2509Sflorian while(iter->rrset != NULL) { 717308d2509Sflorian if(iter->index < iter->rrset->rr_count) { 718308d2509Sflorian return &iter->rrset->rrs[iter->index++]; 719308d2509Sflorian } 720308d2509Sflorian iter->index = 0; 721308d2509Sflorian if(iter->domain == NULL) { 722308d2509Sflorian assert(iter->rrset == iter->zone->soa_rrset); 723308d2509Sflorian iter->domain = iter->zone->apex; 724308d2509Sflorian iter->rrset = iter->domain->rrsets; 725308d2509Sflorian } else { 726308d2509Sflorian iter->rrset = iter->rrset->next; 727308d2509Sflorian } 728308d2509Sflorian /* ensure SOA RR is not returned again and RR belongs to zone */ 729308d2509Sflorian while((iter->rrset == NULL && iter->domain != NULL) || 730308d2509Sflorian (iter->rrset != NULL && (iter->rrset == iter->zone->soa_rrset || 731308d2509Sflorian iter->rrset->zone != iter->zone))) 732308d2509Sflorian { 733308d2509Sflorian if(iter->rrset != NULL) { 734308d2509Sflorian iter->rrset = iter->rrset->next; 735308d2509Sflorian } else { 736308d2509Sflorian iter->domain = domain_next(iter->domain); 737308d2509Sflorian if(iter->domain != NULL && 738308d2509Sflorian dname_is_subdomain(domain_dname(iter->domain), 739308d2509Sflorian domain_dname(iter->zone->apex))) 740308d2509Sflorian { 741308d2509Sflorian iter->rrset = iter->domain->rrsets; 742308d2509Sflorian } 743308d2509Sflorian } 744308d2509Sflorian } 745308d2509Sflorian } 746308d2509Sflorian 747308d2509Sflorian assert(iter->rrset == NULL); 748308d2509Sflorian assert(iter->domain == NULL); 749308d2509Sflorian iter->index = -1; 750308d2509Sflorian 751308d2509Sflorian return NULL; 752308d2509Sflorian } 753