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)); 36*c1e73312Sflorian #ifdef USE_RADIX_TREE 37*c1e73312Sflorian result->dname 38*c1e73312Sflorian #else 39*c1e73312Sflorian result->node.key 40*c1e73312Sflorian #endif 41*c1e73312Sflorian = 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; 76d3fecca9Ssthen result->nsec3->have_nsec3_hash = 0; 77d3fecca9Ssthen result->nsec3->have_nsec3_wc_hash = 0; 78d3fecca9Ssthen result->nsec3->have_nsec3_ds_parent_hash = 0; 79d3fecca9Ssthen result->nsec3->prehash_prev = NULL; 80d3fecca9Ssthen result->nsec3->prehash_next = NULL; 81d3fecca9Ssthen result->nsec3->nsec3_node.key = NULL; 82d3fecca9Ssthen result->nsec3->hash_node.key = NULL; 83d3fecca9Ssthen result->nsec3->wchash_node.key = NULL; 84d3fecca9Ssthen result->nsec3->dshash_node.key = NULL; 85d3fecca9Ssthen } 86d3fecca9Ssthen #endif /* NSEC3 */ 87d3fecca9Ssthen 88d3fecca9Ssthen /** make the domain last in the numlist, changes numbers of domains */ 89d3fecca9Ssthen static void 90d3fecca9Ssthen numlist_make_last(domain_table_type* table, domain_type* domain) 91d3fecca9Ssthen { 92d3fecca9Ssthen size_t sw; 93d3fecca9Ssthen domain_type* last = table->numlist_last; 94d3fecca9Ssthen if(domain == last) 95d3fecca9Ssthen return; 96d3fecca9Ssthen /* swap numbers with the last element */ 97d3fecca9Ssthen sw = domain->number; 98d3fecca9Ssthen domain->number = last->number; 99d3fecca9Ssthen last->number = sw; 100d3fecca9Ssthen /* swap list position with the last element */ 101d3fecca9Ssthen assert(domain->numlist_next); 102d3fecca9Ssthen assert(last->numlist_prev); 103d3fecca9Ssthen if(domain->numlist_next != last) { 104d3fecca9Ssthen /* case 1: there are nodes between domain .. last */ 105d3fecca9Ssthen domain_type* span_start = domain->numlist_next; 106d3fecca9Ssthen domain_type* span_end = last->numlist_prev; 107d3fecca9Ssthen /* these assignments walk the new list from start to end */ 108d3fecca9Ssthen if(domain->numlist_prev) 109d3fecca9Ssthen domain->numlist_prev->numlist_next = last; 110d3fecca9Ssthen last->numlist_prev = domain->numlist_prev; 111d3fecca9Ssthen last->numlist_next = span_start; 112d3fecca9Ssthen span_start->numlist_prev = last; 113d3fecca9Ssthen span_end->numlist_next = domain; 114d3fecca9Ssthen domain->numlist_prev = span_end; 115d3fecca9Ssthen domain->numlist_next = NULL; 116d3fecca9Ssthen } else { 117d3fecca9Ssthen /* case 2: domain and last are neighbors */ 118d3fecca9Ssthen /* these assignments walk the new list from start to end */ 119d3fecca9Ssthen if(domain->numlist_prev) 120d3fecca9Ssthen domain->numlist_prev->numlist_next = last; 121d3fecca9Ssthen last->numlist_prev = domain->numlist_prev; 122d3fecca9Ssthen last->numlist_next = domain; 123d3fecca9Ssthen domain->numlist_prev = last; 124d3fecca9Ssthen domain->numlist_next = NULL; 125d3fecca9Ssthen } 126d3fecca9Ssthen table->numlist_last = domain; 127d3fecca9Ssthen } 128d3fecca9Ssthen 129d3fecca9Ssthen /** pop the biggest domain off the numlist */ 130d3fecca9Ssthen static domain_type* 131d3fecca9Ssthen numlist_pop_last(domain_table_type* table) 132d3fecca9Ssthen { 133d3fecca9Ssthen domain_type* d = table->numlist_last; 134d3fecca9Ssthen table->numlist_last = table->numlist_last->numlist_prev; 135d3fecca9Ssthen if(table->numlist_last) 136d3fecca9Ssthen table->numlist_last->numlist_next = NULL; 137d3fecca9Ssthen return d; 138d3fecca9Ssthen } 139d3fecca9Ssthen 140d3fecca9Ssthen /** see if a domain is eligible to be deleted, and thus is not used */ 141d3fecca9Ssthen static int 142d3fecca9Ssthen domain_can_be_deleted(domain_type* domain) 143d3fecca9Ssthen { 144d3fecca9Ssthen domain_type* n; 145d3fecca9Ssthen /* it has data or it has usage, do not delete it */ 146d3fecca9Ssthen if(domain->rrsets) return 0; 147d3fecca9Ssthen if(domain->usage) return 0; 148d3fecca9Ssthen n = domain_next(domain); 149d3fecca9Ssthen /* it has children domains, do not delete it */ 150d3fecca9Ssthen if(n && domain_is_subdomain(n, domain)) 151d3fecca9Ssthen return 0; 152d3fecca9Ssthen return 1; 153d3fecca9Ssthen } 154d3fecca9Ssthen 155d3fecca9Ssthen #ifdef NSEC3 156d3fecca9Ssthen /** see if domain is on the prehash list */ 157d3fecca9Ssthen int domain_is_prehash(domain_table_type* table, domain_type* domain) 158d3fecca9Ssthen { 159d3fecca9Ssthen if(domain->nsec3 160d3fecca9Ssthen && (domain->nsec3->prehash_prev || domain->nsec3->prehash_next)) 161d3fecca9Ssthen return 1; 162d3fecca9Ssthen return (table->prehash_list == domain); 163d3fecca9Ssthen } 164d3fecca9Ssthen 165d3fecca9Ssthen /** remove domain node from NSEC3 tree in hash space */ 166d3fecca9Ssthen void 167d3fecca9Ssthen zone_del_domain_in_hash_tree(rbtree_t* tree, rbnode_t* node) 168d3fecca9Ssthen { 169d3fecca9Ssthen if(!node->key) 170d3fecca9Ssthen return; 171d3fecca9Ssthen rbtree_delete(tree, node->key); 172d3fecca9Ssthen /* note that domain is no longer in the tree */ 173d3fecca9Ssthen node->key = NULL; 174d3fecca9Ssthen } 175d3fecca9Ssthen 176d3fecca9Ssthen /** clear the prehash list */ 177d3fecca9Ssthen void prehash_clear(domain_table_type* table) 178d3fecca9Ssthen { 179d3fecca9Ssthen domain_type* d = table->prehash_list, *n; 180d3fecca9Ssthen while(d) { 181d3fecca9Ssthen n = d->nsec3->prehash_next; 182d3fecca9Ssthen d->nsec3->prehash_prev = NULL; 183d3fecca9Ssthen d->nsec3->prehash_next = NULL; 184d3fecca9Ssthen d = n; 185d3fecca9Ssthen } 186d3fecca9Ssthen table->prehash_list = NULL; 187d3fecca9Ssthen } 188d3fecca9Ssthen 189d3fecca9Ssthen /** add domain to prehash list */ 190d3fecca9Ssthen void 191d3fecca9Ssthen prehash_add(domain_table_type* table, domain_type* domain) 192d3fecca9Ssthen { 193d3fecca9Ssthen if(domain_is_prehash(table, domain)) 194d3fecca9Ssthen return; 195d3fecca9Ssthen allocate_domain_nsec3(table, domain); 196d3fecca9Ssthen domain->nsec3->prehash_next = table->prehash_list; 197d3fecca9Ssthen if(table->prehash_list) 198d3fecca9Ssthen table->prehash_list->nsec3->prehash_prev = domain; 199d3fecca9Ssthen table->prehash_list = domain; 200d3fecca9Ssthen } 201d3fecca9Ssthen 202d3fecca9Ssthen /** remove domain from prehash list */ 203d3fecca9Ssthen void 204d3fecca9Ssthen prehash_del(domain_table_type* table, domain_type* domain) 205d3fecca9Ssthen { 206d3fecca9Ssthen if(domain->nsec3->prehash_next) 207d3fecca9Ssthen domain->nsec3->prehash_next->nsec3->prehash_prev = 208d3fecca9Ssthen domain->nsec3->prehash_prev; 209d3fecca9Ssthen if(domain->nsec3->prehash_prev) 210d3fecca9Ssthen domain->nsec3->prehash_prev->nsec3->prehash_next = 211d3fecca9Ssthen domain->nsec3->prehash_next; 212d3fecca9Ssthen else table->prehash_list = domain->nsec3->prehash_next; 213d3fecca9Ssthen domain->nsec3->prehash_next = NULL; 214d3fecca9Ssthen domain->nsec3->prehash_prev = NULL; 215d3fecca9Ssthen } 216d3fecca9Ssthen #endif /* NSEC3 */ 217d3fecca9Ssthen 218d3fecca9Ssthen /** perform domain name deletion */ 219d3fecca9Ssthen static void 220d3fecca9Ssthen do_deldomain(namedb_type* db, domain_type* domain) 221d3fecca9Ssthen { 222d3fecca9Ssthen assert(domain && domain->parent); /* exists and not root */ 223d3fecca9Ssthen /* first adjust the number list so that domain is the last one */ 224d3fecca9Ssthen numlist_make_last(db->domains, domain); 225d3fecca9Ssthen /* pop off the domain from the number list */ 226d3fecca9Ssthen (void)numlist_pop_last(db->domains); 227d3fecca9Ssthen 228d3fecca9Ssthen #ifdef NSEC3 229d3fecca9Ssthen /* if on prehash list, remove from prehash */ 230d3fecca9Ssthen if(domain_is_prehash(db->domains, domain)) 231d3fecca9Ssthen prehash_del(db->domains, domain); 232d3fecca9Ssthen 233d3fecca9Ssthen /* see if nsec3-nodes are used */ 234d3fecca9Ssthen if(domain->nsec3) { 235d3fecca9Ssthen if(domain->nsec3->nsec3_node.key) 236d3fecca9Ssthen zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain) 237d3fecca9Ssthen ->nsec3tree, &domain->nsec3->nsec3_node); 238d3fecca9Ssthen if(domain->nsec3->hash_node.key) 239d3fecca9Ssthen zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain) 240d3fecca9Ssthen ->hashtree, &domain->nsec3->hash_node); 241d3fecca9Ssthen if(domain->nsec3->wchash_node.key) 242d3fecca9Ssthen zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain) 243d3fecca9Ssthen ->wchashtree, &domain->nsec3->wchash_node); 244d3fecca9Ssthen if(domain->nsec3->dshash_node.key) 245d3fecca9Ssthen zone_del_domain_in_hash_tree(nsec3_tree_dszone(db, domain) 246d3fecca9Ssthen ->dshashtree, &domain->nsec3->dshash_node); 247d3fecca9Ssthen region_recycle(db->domains->region, domain->nsec3, 248d3fecca9Ssthen sizeof(struct nsec3_domain_data)); 249d3fecca9Ssthen } 250d3fecca9Ssthen #endif /* NSEC3 */ 251d3fecca9Ssthen 252d3fecca9Ssthen /* see if this domain is someones wildcard-child-closest-match, 253d3fecca9Ssthen * which can only be the parent, and then it should use the 254d3fecca9Ssthen * one-smaller than this domain as closest-match. */ 255d3fecca9Ssthen if(domain->parent->wildcard_child_closest_match == domain) 256d3fecca9Ssthen domain->parent->wildcard_child_closest_match = 25703739794Sbrad domain_previous_existing_child(domain); 258d3fecca9Ssthen 259d3fecca9Ssthen /* actual removal */ 260*c1e73312Sflorian #ifdef USE_RADIX_TREE 261d3fecca9Ssthen radix_delete(db->domains->nametree, domain->rnode); 262*c1e73312Sflorian #else 263*c1e73312Sflorian rbtree_delete(db->domains->names_to_domains, domain->node.key); 264*c1e73312Sflorian #endif 265*c1e73312Sflorian region_recycle(db->domains->region, domain_dname(domain), 266*c1e73312Sflorian dname_total_size(domain_dname(domain))); 267d3fecca9Ssthen region_recycle(db->domains->region, domain, sizeof(domain_type)); 268d3fecca9Ssthen } 269d3fecca9Ssthen 270d3fecca9Ssthen void 271d3fecca9Ssthen domain_table_deldomain(namedb_type* db, domain_type* domain) 272d3fecca9Ssthen { 273d3fecca9Ssthen while(domain_can_be_deleted(domain)) { 274d3fecca9Ssthen /* delete it */ 275d3fecca9Ssthen do_deldomain(db, domain); 276d3fecca9Ssthen /* test parent */ 277d3fecca9Ssthen domain = domain->parent; 278d3fecca9Ssthen } 279d3fecca9Ssthen } 280d3fecca9Ssthen 281d3fecca9Ssthen /** clear hash tree */ 282d3fecca9Ssthen void 283d3fecca9Ssthen hash_tree_clear(rbtree_t* tree) 284d3fecca9Ssthen { 285d3fecca9Ssthen rbnode_t* n; 286d3fecca9Ssthen if(!tree) return; 287d3fecca9Ssthen 288d3fecca9Ssthen /* note that elements are no longer in the tree */ 289d3fecca9Ssthen for(n=rbtree_first(tree); n!=RBTREE_NULL; n=rbtree_next(n)) { 290d3fecca9Ssthen n->key = NULL; 291d3fecca9Ssthen } 292d3fecca9Ssthen tree->count = 0; 293d3fecca9Ssthen tree->root = RBTREE_NULL; 294d3fecca9Ssthen } 295d3fecca9Ssthen 296d3fecca9Ssthen void hash_tree_delete(region_type* region, rbtree_t* tree) 297d3fecca9Ssthen { 298d3fecca9Ssthen region_recycle(region, tree, sizeof(rbtree_t)); 299d3fecca9Ssthen } 300d3fecca9Ssthen 301d3fecca9Ssthen /** add domain nsec3 node to hashedspace tree */ 302d3fecca9Ssthen void zone_add_domain_in_hash_tree(region_type* region, rbtree_t** tree, 303d3fecca9Ssthen int (*cmpf)(const void*, const void*), 304d3fecca9Ssthen domain_type* domain, rbnode_t* node) 305d3fecca9Ssthen { 306d3fecca9Ssthen if(!*tree) 307d3fecca9Ssthen *tree = rbtree_create(region, cmpf); 308d3fecca9Ssthen memset(node, 0, sizeof(rbnode_t)); 309d3fecca9Ssthen node->key = domain; 310d3fecca9Ssthen rbtree_insert(*tree, node); 311d3fecca9Ssthen } 312d3fecca9Ssthen 31362ac0c33Sjakob domain_table_type * 31462ac0c33Sjakob domain_table_create(region_type* region) 31562ac0c33Sjakob { 31662ac0c33Sjakob const dname_type* origin; 31762ac0c33Sjakob domain_table_type* result; 31862ac0c33Sjakob domain_type* root; 31962ac0c33Sjakob 32062ac0c33Sjakob assert(region); 32162ac0c33Sjakob 32262ac0c33Sjakob origin = dname_make(region, (uint8_t *) "", 0); 32362ac0c33Sjakob 32462ac0c33Sjakob root = (domain_type *) region_alloc(region, sizeof(domain_type)); 325*c1e73312Sflorian #ifdef USE_RADIX_TREE 326*c1e73312Sflorian root->dname 327*c1e73312Sflorian #else 328*c1e73312Sflorian root->node.key 329*c1e73312Sflorian #endif 330*c1e73312Sflorian = origin; 33162ac0c33Sjakob root->parent = NULL; 33262ac0c33Sjakob root->wildcard_child_closest_match = root; 33362ac0c33Sjakob root->rrsets = NULL; 33462ac0c33Sjakob root->number = 1; /* 0 is used for after header */ 335d3fecca9Ssthen root->usage = 1; /* do not delete root, ever */ 33662ac0c33Sjakob root->is_existing = 0; 33762ac0c33Sjakob root->is_apex = 0; 338d3fecca9Ssthen root->numlist_prev = NULL; 339d3fecca9Ssthen root->numlist_next = NULL; 34062ac0c33Sjakob #ifdef NSEC3 341d3fecca9Ssthen root->nsec3 = NULL; 342d3fecca9Ssthen #endif 34362ac0c33Sjakob 34462ac0c33Sjakob result = (domain_table_type *) region_alloc(region, 34562ac0c33Sjakob sizeof(domain_table_type)); 34662ac0c33Sjakob result->region = region; 347*c1e73312Sflorian #ifdef USE_RADIX_TREE 348d3fecca9Ssthen result->nametree = radix_tree_create(region); 349d3fecca9Ssthen root->rnode = radname_insert(result->nametree, dname_name(root->dname), 350d3fecca9Ssthen root->dname->name_size, root); 351*c1e73312Sflorian #else 352*c1e73312Sflorian result->names_to_domains = rbtree_create( 353*c1e73312Sflorian region, (int (*)(const void *, const void *)) dname_compare); 354*c1e73312Sflorian rbtree_insert(result->names_to_domains, (rbnode_t *) root); 355*c1e73312Sflorian #endif 35662ac0c33Sjakob 35762ac0c33Sjakob result->root = root; 358d3fecca9Ssthen result->numlist_last = root; 359d3fecca9Ssthen #ifdef NSEC3 360d3fecca9Ssthen result->prehash_list = NULL; 361d3fecca9Ssthen #endif 36262ac0c33Sjakob 36362ac0c33Sjakob return result; 36462ac0c33Sjakob } 36562ac0c33Sjakob 36662ac0c33Sjakob int 36762ac0c33Sjakob domain_table_search(domain_table_type *table, 36862ac0c33Sjakob const dname_type *dname, 36962ac0c33Sjakob domain_type **closest_match, 37062ac0c33Sjakob domain_type **closest_encloser) 37162ac0c33Sjakob { 37262ac0c33Sjakob int exact; 37362ac0c33Sjakob uint8_t label_match_count; 37462ac0c33Sjakob 37562ac0c33Sjakob assert(table); 37662ac0c33Sjakob assert(dname); 37762ac0c33Sjakob assert(closest_match); 37862ac0c33Sjakob assert(closest_encloser); 37962ac0c33Sjakob 380*c1e73312Sflorian #ifdef USE_RADIX_TREE 381d3fecca9Ssthen exact = radname_find_less_equal(table->nametree, dname_name(dname), 382d3fecca9Ssthen dname->name_size, (struct radnode**)closest_match); 383d3fecca9Ssthen *closest_match = (domain_type*)((*(struct radnode**)closest_match)->elem); 384*c1e73312Sflorian #else 385*c1e73312Sflorian exact = rbtree_find_less_equal(table->names_to_domains, dname, (rbnode_t **) closest_match); 386*c1e73312Sflorian #endif 38762ac0c33Sjakob assert(*closest_match); 38862ac0c33Sjakob 38962ac0c33Sjakob *closest_encloser = *closest_match; 39062ac0c33Sjakob 39162ac0c33Sjakob if (!exact) { 39262ac0c33Sjakob label_match_count = dname_label_match_count( 39362ac0c33Sjakob domain_dname(*closest_encloser), 39462ac0c33Sjakob dname); 39562ac0c33Sjakob assert(label_match_count < dname->label_count); 39662ac0c33Sjakob while (label_match_count < domain_dname(*closest_encloser)->label_count) { 39762ac0c33Sjakob (*closest_encloser) = (*closest_encloser)->parent; 39862ac0c33Sjakob assert(*closest_encloser); 39962ac0c33Sjakob } 40062ac0c33Sjakob } 40162ac0c33Sjakob 40262ac0c33Sjakob return exact; 40362ac0c33Sjakob } 40462ac0c33Sjakob 40562ac0c33Sjakob domain_type * 40662ac0c33Sjakob domain_table_find(domain_table_type* table, 40762ac0c33Sjakob const dname_type* dname) 40862ac0c33Sjakob { 40962ac0c33Sjakob domain_type* closest_match; 41062ac0c33Sjakob domain_type* closest_encloser; 41162ac0c33Sjakob int exact; 41262ac0c33Sjakob 41362ac0c33Sjakob exact = domain_table_search( 41462ac0c33Sjakob table, dname, &closest_match, &closest_encloser); 41562ac0c33Sjakob return exact ? closest_encloser : NULL; 41662ac0c33Sjakob } 41762ac0c33Sjakob 41862ac0c33Sjakob 41962ac0c33Sjakob domain_type * 42062ac0c33Sjakob domain_table_insert(domain_table_type* table, 42162ac0c33Sjakob const dname_type* dname) 42262ac0c33Sjakob { 42362ac0c33Sjakob domain_type* closest_match; 42462ac0c33Sjakob domain_type* closest_encloser; 42562ac0c33Sjakob domain_type* result; 42662ac0c33Sjakob int exact; 42762ac0c33Sjakob 42862ac0c33Sjakob assert(table); 42962ac0c33Sjakob assert(dname); 43062ac0c33Sjakob 43162ac0c33Sjakob exact = domain_table_search( 43262ac0c33Sjakob table, dname, &closest_match, &closest_encloser); 43362ac0c33Sjakob if (exact) { 43462ac0c33Sjakob result = closest_encloser; 43562ac0c33Sjakob } else { 43662ac0c33Sjakob assert(domain_dname(closest_encloser)->label_count < dname->label_count); 43762ac0c33Sjakob 43862ac0c33Sjakob /* Insert new node(s). */ 43962ac0c33Sjakob do { 44062ac0c33Sjakob result = allocate_domain_info(table, 44162ac0c33Sjakob dname, 44262ac0c33Sjakob closest_encloser); 443*c1e73312Sflorian #ifdef USE_RADIX_TREE 444d3fecca9Ssthen result->rnode = radname_insert(table->nametree, 445d3fecca9Ssthen dname_name(result->dname), 446d3fecca9Ssthen result->dname->name_size, result); 447*c1e73312Sflorian #else 448*c1e73312Sflorian rbtree_insert(table->names_to_domains, (rbnode_t *) result); 449*c1e73312Sflorian #endif 45062ac0c33Sjakob 45162ac0c33Sjakob /* 45262ac0c33Sjakob * If the newly added domain name is larger 45362ac0c33Sjakob * than the parent's current 45462ac0c33Sjakob * wildcard_child_closest_match but smaller or 45562ac0c33Sjakob * equal to the wildcard domain name, update 45662ac0c33Sjakob * the parent's wildcard_child_closest_match 45762ac0c33Sjakob * field. 45862ac0c33Sjakob */ 45962ac0c33Sjakob if (label_compare(dname_name(domain_dname(result)), 46062ac0c33Sjakob (const uint8_t *) "\001*") <= 0 46162ac0c33Sjakob && dname_compare(domain_dname(result), 46262ac0c33Sjakob domain_dname(closest_encloser->wildcard_child_closest_match)) > 0) 46362ac0c33Sjakob { 46462ac0c33Sjakob closest_encloser->wildcard_child_closest_match 46562ac0c33Sjakob = result; 46662ac0c33Sjakob } 46762ac0c33Sjakob closest_encloser = result; 46862ac0c33Sjakob } while (domain_dname(closest_encloser)->label_count < dname->label_count); 46962ac0c33Sjakob } 47062ac0c33Sjakob 47162ac0c33Sjakob return result; 47262ac0c33Sjakob } 47362ac0c33Sjakob 47403739794Sbrad domain_type *domain_previous_existing_child(domain_type* domain) 47503739794Sbrad { 47603739794Sbrad domain_type* parent = domain->parent; 47703739794Sbrad domain = domain_previous(domain); 47803739794Sbrad while(domain && !domain->is_existing) { 47903739794Sbrad if(domain == parent) /* do not walk back above parent */ 48003739794Sbrad return parent; 48103739794Sbrad domain = domain_previous(domain); 48203739794Sbrad } 48303739794Sbrad return domain; 48403739794Sbrad } 48562ac0c33Sjakob 48662ac0c33Sjakob void 48762ac0c33Sjakob domain_add_rrset(domain_type* domain, rrset_type* rrset) 48862ac0c33Sjakob { 48962ac0c33Sjakob #if 0 /* fast */ 49062ac0c33Sjakob rrset->next = domain->rrsets; 49162ac0c33Sjakob domain->rrsets = rrset; 49262ac0c33Sjakob #else 49362ac0c33Sjakob /* preserve ordering, add at end */ 49462ac0c33Sjakob rrset_type** p = &domain->rrsets; 49562ac0c33Sjakob while(*p) 49662ac0c33Sjakob p = &((*p)->next); 49762ac0c33Sjakob *p = rrset; 49862ac0c33Sjakob rrset->next = 0; 49962ac0c33Sjakob #endif 50062ac0c33Sjakob 50162ac0c33Sjakob while (domain && !domain->is_existing) { 50262ac0c33Sjakob domain->is_existing = 1; 50303739794Sbrad /* does this name in existance update the parent's 50403739794Sbrad * wildcard closest match? */ 50503739794Sbrad if(domain->parent 50603739794Sbrad && label_compare(dname_name(domain_dname(domain)), 50703739794Sbrad (const uint8_t *) "\001*") <= 0 50803739794Sbrad && dname_compare(domain_dname(domain), 50903739794Sbrad domain_dname(domain->parent->wildcard_child_closest_match)) > 0) { 51003739794Sbrad domain->parent->wildcard_child_closest_match = domain; 51103739794Sbrad } 51262ac0c33Sjakob domain = domain->parent; 51362ac0c33Sjakob } 51462ac0c33Sjakob } 51562ac0c33Sjakob 51662ac0c33Sjakob 51762ac0c33Sjakob rrset_type * 51862ac0c33Sjakob domain_find_rrset(domain_type* domain, zone_type* zone, uint16_t type) 51962ac0c33Sjakob { 52062ac0c33Sjakob rrset_type* result = domain->rrsets; 52162ac0c33Sjakob 52262ac0c33Sjakob while (result) { 52362ac0c33Sjakob if (result->zone == zone && rrset_rrtype(result) == type) { 52462ac0c33Sjakob return result; 52562ac0c33Sjakob } 52662ac0c33Sjakob result = result->next; 52762ac0c33Sjakob } 52862ac0c33Sjakob return NULL; 52962ac0c33Sjakob } 53062ac0c33Sjakob 53162ac0c33Sjakob rrset_type * 53262ac0c33Sjakob domain_find_any_rrset(domain_type* domain, zone_type* zone) 53362ac0c33Sjakob { 53462ac0c33Sjakob rrset_type* result = domain->rrsets; 53562ac0c33Sjakob 53662ac0c33Sjakob while (result) { 53762ac0c33Sjakob if (result->zone == zone) { 53862ac0c33Sjakob return result; 53962ac0c33Sjakob } 54062ac0c33Sjakob result = result->next; 54162ac0c33Sjakob } 54262ac0c33Sjakob return NULL; 54362ac0c33Sjakob } 54462ac0c33Sjakob 54562ac0c33Sjakob zone_type * 546cbbc2d6cSbrad domain_find_zone(namedb_type* db, domain_type* domain) 54762ac0c33Sjakob { 54862ac0c33Sjakob rrset_type* rrset; 54962ac0c33Sjakob while (domain) { 550cbbc2d6cSbrad if(domain->is_apex) { 55162ac0c33Sjakob for (rrset = domain->rrsets; rrset; rrset = rrset->next) { 55262ac0c33Sjakob if (rrset_rrtype(rrset) == TYPE_SOA) { 55362ac0c33Sjakob return rrset->zone; 55462ac0c33Sjakob } 55562ac0c33Sjakob } 556cbbc2d6cSbrad return namedb_find_zone(db, domain_dname(domain)); 557cbbc2d6cSbrad } 55862ac0c33Sjakob domain = domain->parent; 55962ac0c33Sjakob } 56062ac0c33Sjakob return NULL; 56162ac0c33Sjakob } 56262ac0c33Sjakob 56362ac0c33Sjakob zone_type * 5646e9bf1eeSflorian domain_find_parent_zone(namedb_type* db, zone_type* zone) 56562ac0c33Sjakob { 56662ac0c33Sjakob rrset_type* rrset; 56762ac0c33Sjakob 56862ac0c33Sjakob assert(zone); 56962ac0c33Sjakob 57062ac0c33Sjakob for (rrset = zone->apex->rrsets; rrset; rrset = rrset->next) { 57162ac0c33Sjakob if (rrset->zone != zone && rrset_rrtype(rrset) == TYPE_NS) { 57262ac0c33Sjakob return rrset->zone; 57362ac0c33Sjakob } 57462ac0c33Sjakob } 5756e9bf1eeSflorian /* the NS record in the parent zone above this zone is not present, 5766e9bf1eeSflorian * workaround to find that parent zone anyway */ 5776e9bf1eeSflorian if(zone->apex->parent) 5786e9bf1eeSflorian return domain_find_zone(db, zone->apex->parent); 57962ac0c33Sjakob return NULL; 58062ac0c33Sjakob } 58162ac0c33Sjakob 58262ac0c33Sjakob domain_type * 58362ac0c33Sjakob domain_find_ns_rrsets(domain_type* domain, zone_type* zone, rrset_type **ns) 58462ac0c33Sjakob { 58562ac0c33Sjakob while (domain && domain != zone->apex) { 58662ac0c33Sjakob *ns = domain_find_rrset(domain, zone, TYPE_NS); 58762ac0c33Sjakob if (*ns) 58862ac0c33Sjakob return domain; 58962ac0c33Sjakob domain = domain->parent; 59062ac0c33Sjakob } 59162ac0c33Sjakob 59262ac0c33Sjakob *ns = NULL; 59362ac0c33Sjakob return NULL; 59462ac0c33Sjakob } 59562ac0c33Sjakob 596275a8d89Sflorian domain_type * 597275a8d89Sflorian find_dname_above(domain_type* domain, zone_type* zone) 598275a8d89Sflorian { 599275a8d89Sflorian domain_type* d = domain->parent; 600275a8d89Sflorian while(d && d != zone->apex) { 601275a8d89Sflorian if(domain_find_rrset(d, zone, TYPE_DNAME)) 602275a8d89Sflorian return d; 603275a8d89Sflorian d = d->parent; 604275a8d89Sflorian } 605275a8d89Sflorian return NULL; 606275a8d89Sflorian } 607275a8d89Sflorian 60862ac0c33Sjakob int 60962ac0c33Sjakob domain_is_glue(domain_type* domain, zone_type* zone) 61062ac0c33Sjakob { 61162ac0c33Sjakob rrset_type* unused; 61262ac0c33Sjakob domain_type* ns_domain = domain_find_ns_rrsets(domain, zone, &unused); 61362ac0c33Sjakob return (ns_domain != NULL && 61462ac0c33Sjakob domain_find_rrset(ns_domain, zone, TYPE_SOA) == NULL); 61562ac0c33Sjakob } 61662ac0c33Sjakob 61762ac0c33Sjakob domain_type * 61862ac0c33Sjakob domain_wildcard_child(domain_type* domain) 61962ac0c33Sjakob { 62062ac0c33Sjakob domain_type* wildcard_child; 62162ac0c33Sjakob 62262ac0c33Sjakob assert(domain); 62362ac0c33Sjakob assert(domain->wildcard_child_closest_match); 62462ac0c33Sjakob 62562ac0c33Sjakob wildcard_child = domain->wildcard_child_closest_match; 62662ac0c33Sjakob if (wildcard_child != domain 62762ac0c33Sjakob && label_is_wildcard(dname_name(domain_dname(wildcard_child)))) 62862ac0c33Sjakob { 62962ac0c33Sjakob return wildcard_child; 63062ac0c33Sjakob } else { 63162ac0c33Sjakob return NULL; 63262ac0c33Sjakob } 63362ac0c33Sjakob } 63462ac0c33Sjakob 63562ac0c33Sjakob int 63662ac0c33Sjakob zone_is_secure(zone_type* zone) 63762ac0c33Sjakob { 63862ac0c33Sjakob assert(zone); 63962ac0c33Sjakob return zone->is_secure; 64062ac0c33Sjakob } 64162ac0c33Sjakob 64262ac0c33Sjakob uint16_t 64362ac0c33Sjakob rr_rrsig_type_covered(rr_type* rr) 64462ac0c33Sjakob { 64562ac0c33Sjakob assert(rr->type == TYPE_RRSIG); 64662ac0c33Sjakob assert(rr->rdata_count > 0); 64762ac0c33Sjakob assert(rdata_atom_size(rr->rdatas[0]) == sizeof(uint16_t)); 64862ac0c33Sjakob 64962ac0c33Sjakob return ntohs(* (uint16_t *) rdata_atom_data(rr->rdatas[0])); 65062ac0c33Sjakob } 65162ac0c33Sjakob 65262ac0c33Sjakob zone_type * 653d3fecca9Ssthen namedb_find_zone(namedb_type* db, const dname_type* dname) 65462ac0c33Sjakob { 655d3fecca9Ssthen struct radnode* n = radname_search(db->zonetree, dname_name(dname), 656d3fecca9Ssthen dname->name_size); 657d3fecca9Ssthen if(n) return (zone_type*)n->elem; 658d3fecca9Ssthen return NULL; 65962ac0c33Sjakob } 66062ac0c33Sjakob 66162ac0c33Sjakob rrset_type * 66262ac0c33Sjakob domain_find_non_cname_rrset(domain_type* domain, zone_type* zone) 66362ac0c33Sjakob { 66462ac0c33Sjakob /* find any rrset type that is not allowed next to a CNAME */ 66562ac0c33Sjakob /* nothing is allowed next to a CNAME, except RRSIG, NSEC, NSEC3 */ 66662ac0c33Sjakob rrset_type *result = domain->rrsets; 66762ac0c33Sjakob 66862ac0c33Sjakob while (result) { 66962ac0c33Sjakob if (result->zone == zone && /* here is the list of exceptions*/ 67062ac0c33Sjakob rrset_rrtype(result) != TYPE_CNAME && 67162ac0c33Sjakob rrset_rrtype(result) != TYPE_RRSIG && 67262ac0c33Sjakob rrset_rrtype(result) != TYPE_NXT && 67362ac0c33Sjakob rrset_rrtype(result) != TYPE_SIG && 67462ac0c33Sjakob rrset_rrtype(result) != TYPE_NSEC && 67562ac0c33Sjakob rrset_rrtype(result) != TYPE_NSEC3 ) { 67662ac0c33Sjakob return result; 67762ac0c33Sjakob } 67862ac0c33Sjakob result = result->next; 67962ac0c33Sjakob } 68062ac0c33Sjakob return NULL; 68162ac0c33Sjakob } 6820c2b6c02Sjakob 6830c2b6c02Sjakob int 684d3fecca9Ssthen namedb_lookup(struct namedb* db, 685d3fecca9Ssthen const dname_type* dname, 686d3fecca9Ssthen domain_type **closest_match, 687d3fecca9Ssthen domain_type **closest_encloser) 6880c2b6c02Sjakob { 689d3fecca9Ssthen return domain_table_search( 690d3fecca9Ssthen db->domains, dname, closest_match, closest_encloser); 6910c2b6c02Sjakob } 692