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)); 36d3fecca9Ssthen result->dname = dname_partial_copy( 3762ac0c33Sjakob table->region, dname, domain_dname(parent)->label_count + 1); 3862ac0c33Sjakob result->parent = parent; 3962ac0c33Sjakob result->wildcard_child_closest_match = result; 4062ac0c33Sjakob result->rrsets = NULL; 41d3fecca9Ssthen result->usage = 0; 4262ac0c33Sjakob #ifdef NSEC3 43d3fecca9Ssthen result->nsec3 = NULL; 44d3fecca9Ssthen #endif 4562ac0c33Sjakob result->is_existing = 0; 4662ac0c33Sjakob result->is_apex = 0; 47d3fecca9Ssthen assert(table->numlist_last); /* it exists because root exists */ 48d3fecca9Ssthen /* push this domain at the end of the numlist */ 49d3fecca9Ssthen result->number = table->numlist_last->number+1; 50d3fecca9Ssthen result->numlist_next = NULL; 51d3fecca9Ssthen result->numlist_prev = table->numlist_last; 52d3fecca9Ssthen table->numlist_last->numlist_next = result; 53d3fecca9Ssthen table->numlist_last = result; 5462ac0c33Sjakob 5562ac0c33Sjakob return result; 5662ac0c33Sjakob } 5762ac0c33Sjakob 58d3fecca9Ssthen #ifdef NSEC3 59d3fecca9Ssthen void 60d3fecca9Ssthen allocate_domain_nsec3(domain_table_type* table, domain_type* result) 61d3fecca9Ssthen { 62d3fecca9Ssthen if(result->nsec3) 63d3fecca9Ssthen return; 64d3fecca9Ssthen result->nsec3 = (struct nsec3_domain_data*) region_alloc(table->region, 65d3fecca9Ssthen sizeof(struct nsec3_domain_data)); 66d3fecca9Ssthen result->nsec3->nsec3_cover = NULL; 67d3fecca9Ssthen result->nsec3->nsec3_wcard_child_cover = NULL; 68d3fecca9Ssthen result->nsec3->nsec3_ds_parent_cover = NULL; 69d3fecca9Ssthen result->nsec3->nsec3_is_exact = 0; 70d3fecca9Ssthen result->nsec3->nsec3_ds_parent_is_exact = 0; 71d3fecca9Ssthen result->nsec3->have_nsec3_hash = 0; 72d3fecca9Ssthen result->nsec3->have_nsec3_wc_hash = 0; 73d3fecca9Ssthen result->nsec3->have_nsec3_ds_parent_hash = 0; 74d3fecca9Ssthen result->nsec3->prehash_prev = NULL; 75d3fecca9Ssthen result->nsec3->prehash_next = NULL; 76d3fecca9Ssthen result->nsec3->nsec3_node.key = NULL; 77d3fecca9Ssthen result->nsec3->hash_node.key = NULL; 78d3fecca9Ssthen result->nsec3->wchash_node.key = NULL; 79d3fecca9Ssthen result->nsec3->dshash_node.key = NULL; 80d3fecca9Ssthen } 81d3fecca9Ssthen #endif /* NSEC3 */ 82d3fecca9Ssthen 83d3fecca9Ssthen /** make the domain last in the numlist, changes numbers of domains */ 84d3fecca9Ssthen static void 85d3fecca9Ssthen numlist_make_last(domain_table_type* table, domain_type* domain) 86d3fecca9Ssthen { 87d3fecca9Ssthen size_t sw; 88d3fecca9Ssthen domain_type* last = table->numlist_last; 89d3fecca9Ssthen if(domain == last) 90d3fecca9Ssthen return; 91d3fecca9Ssthen /* swap numbers with the last element */ 92d3fecca9Ssthen sw = domain->number; 93d3fecca9Ssthen domain->number = last->number; 94d3fecca9Ssthen last->number = sw; 95d3fecca9Ssthen /* swap list position with the last element */ 96d3fecca9Ssthen assert(domain->numlist_next); 97d3fecca9Ssthen assert(last->numlist_prev); 98d3fecca9Ssthen if(domain->numlist_next != last) { 99d3fecca9Ssthen /* case 1: there are nodes between domain .. last */ 100d3fecca9Ssthen domain_type* span_start = domain->numlist_next; 101d3fecca9Ssthen domain_type* span_end = last->numlist_prev; 102d3fecca9Ssthen /* these assignments walk the new list from start to end */ 103d3fecca9Ssthen if(domain->numlist_prev) 104d3fecca9Ssthen domain->numlist_prev->numlist_next = last; 105d3fecca9Ssthen last->numlist_prev = domain->numlist_prev; 106d3fecca9Ssthen last->numlist_next = span_start; 107d3fecca9Ssthen span_start->numlist_prev = last; 108d3fecca9Ssthen span_end->numlist_next = domain; 109d3fecca9Ssthen domain->numlist_prev = span_end; 110d3fecca9Ssthen domain->numlist_next = NULL; 111d3fecca9Ssthen } else { 112d3fecca9Ssthen /* case 2: domain and last are neighbors */ 113d3fecca9Ssthen /* these assignments walk the new list from start to end */ 114d3fecca9Ssthen if(domain->numlist_prev) 115d3fecca9Ssthen domain->numlist_prev->numlist_next = last; 116d3fecca9Ssthen last->numlist_prev = domain->numlist_prev; 117d3fecca9Ssthen last->numlist_next = domain; 118d3fecca9Ssthen domain->numlist_prev = last; 119d3fecca9Ssthen domain->numlist_next = NULL; 120d3fecca9Ssthen } 121d3fecca9Ssthen table->numlist_last = domain; 122d3fecca9Ssthen } 123d3fecca9Ssthen 124d3fecca9Ssthen /** pop the biggest domain off the numlist */ 125d3fecca9Ssthen static domain_type* 126d3fecca9Ssthen numlist_pop_last(domain_table_type* table) 127d3fecca9Ssthen { 128d3fecca9Ssthen domain_type* d = table->numlist_last; 129d3fecca9Ssthen table->numlist_last = table->numlist_last->numlist_prev; 130d3fecca9Ssthen if(table->numlist_last) 131d3fecca9Ssthen table->numlist_last->numlist_next = NULL; 132d3fecca9Ssthen return d; 133d3fecca9Ssthen } 134d3fecca9Ssthen 135d3fecca9Ssthen /** see if a domain is eligible to be deleted, and thus is not used */ 136d3fecca9Ssthen static int 137d3fecca9Ssthen domain_can_be_deleted(domain_type* domain) 138d3fecca9Ssthen { 139d3fecca9Ssthen domain_type* n; 140d3fecca9Ssthen /* it has data or it has usage, do not delete it */ 141d3fecca9Ssthen if(domain->rrsets) return 0; 142d3fecca9Ssthen if(domain->usage) return 0; 143d3fecca9Ssthen n = domain_next(domain); 144d3fecca9Ssthen /* it has children domains, do not delete it */ 145d3fecca9Ssthen if(n && domain_is_subdomain(n, domain)) 146d3fecca9Ssthen return 0; 147d3fecca9Ssthen return 1; 148d3fecca9Ssthen } 149d3fecca9Ssthen 150d3fecca9Ssthen #ifdef NSEC3 151d3fecca9Ssthen /** see if domain is on the prehash list */ 152d3fecca9Ssthen int domain_is_prehash(domain_table_type* table, domain_type* domain) 153d3fecca9Ssthen { 154d3fecca9Ssthen if(domain->nsec3 155d3fecca9Ssthen && (domain->nsec3->prehash_prev || domain->nsec3->prehash_next)) 156d3fecca9Ssthen return 1; 157d3fecca9Ssthen return (table->prehash_list == domain); 158d3fecca9Ssthen } 159d3fecca9Ssthen 160d3fecca9Ssthen /** remove domain node from NSEC3 tree in hash space */ 161d3fecca9Ssthen void 162d3fecca9Ssthen zone_del_domain_in_hash_tree(rbtree_t* tree, rbnode_t* node) 163d3fecca9Ssthen { 164d3fecca9Ssthen if(!node->key) 165d3fecca9Ssthen return; 166d3fecca9Ssthen rbtree_delete(tree, node->key); 167d3fecca9Ssthen /* note that domain is no longer in the tree */ 168d3fecca9Ssthen node->key = NULL; 169d3fecca9Ssthen } 170d3fecca9Ssthen 171d3fecca9Ssthen /** clear the prehash list */ 172d3fecca9Ssthen void prehash_clear(domain_table_type* table) 173d3fecca9Ssthen { 174d3fecca9Ssthen domain_type* d = table->prehash_list, *n; 175d3fecca9Ssthen while(d) { 176d3fecca9Ssthen n = d->nsec3->prehash_next; 177d3fecca9Ssthen d->nsec3->prehash_prev = NULL; 178d3fecca9Ssthen d->nsec3->prehash_next = NULL; 179d3fecca9Ssthen d = n; 180d3fecca9Ssthen } 181d3fecca9Ssthen table->prehash_list = NULL; 182d3fecca9Ssthen } 183d3fecca9Ssthen 184d3fecca9Ssthen /** add domain to prehash list */ 185d3fecca9Ssthen void 186d3fecca9Ssthen prehash_add(domain_table_type* table, domain_type* domain) 187d3fecca9Ssthen { 188d3fecca9Ssthen if(domain_is_prehash(table, domain)) 189d3fecca9Ssthen return; 190d3fecca9Ssthen allocate_domain_nsec3(table, domain); 191d3fecca9Ssthen domain->nsec3->prehash_next = table->prehash_list; 192d3fecca9Ssthen if(table->prehash_list) 193d3fecca9Ssthen table->prehash_list->nsec3->prehash_prev = domain; 194d3fecca9Ssthen table->prehash_list = domain; 195d3fecca9Ssthen } 196d3fecca9Ssthen 197d3fecca9Ssthen /** remove domain from prehash list */ 198d3fecca9Ssthen void 199d3fecca9Ssthen prehash_del(domain_table_type* table, domain_type* domain) 200d3fecca9Ssthen { 201d3fecca9Ssthen if(domain->nsec3->prehash_next) 202d3fecca9Ssthen domain->nsec3->prehash_next->nsec3->prehash_prev = 203d3fecca9Ssthen domain->nsec3->prehash_prev; 204d3fecca9Ssthen if(domain->nsec3->prehash_prev) 205d3fecca9Ssthen domain->nsec3->prehash_prev->nsec3->prehash_next = 206d3fecca9Ssthen domain->nsec3->prehash_next; 207d3fecca9Ssthen else table->prehash_list = domain->nsec3->prehash_next; 208d3fecca9Ssthen domain->nsec3->prehash_next = NULL; 209d3fecca9Ssthen domain->nsec3->prehash_prev = NULL; 210d3fecca9Ssthen } 211d3fecca9Ssthen #endif /* NSEC3 */ 212d3fecca9Ssthen 213d3fecca9Ssthen /** perform domain name deletion */ 214d3fecca9Ssthen static void 215d3fecca9Ssthen do_deldomain(namedb_type* db, domain_type* domain) 216d3fecca9Ssthen { 217d3fecca9Ssthen assert(domain && domain->parent); /* exists and not root */ 218d3fecca9Ssthen /* first adjust the number list so that domain is the last one */ 219d3fecca9Ssthen numlist_make_last(db->domains, domain); 220d3fecca9Ssthen /* pop off the domain from the number list */ 221d3fecca9Ssthen (void)numlist_pop_last(db->domains); 222d3fecca9Ssthen 223d3fecca9Ssthen #ifdef NSEC3 224d3fecca9Ssthen /* if on prehash list, remove from prehash */ 225d3fecca9Ssthen if(domain_is_prehash(db->domains, domain)) 226d3fecca9Ssthen prehash_del(db->domains, domain); 227d3fecca9Ssthen 228d3fecca9Ssthen /* see if nsec3-nodes are used */ 229d3fecca9Ssthen if(domain->nsec3) { 230d3fecca9Ssthen if(domain->nsec3->nsec3_node.key) 231d3fecca9Ssthen zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain) 232d3fecca9Ssthen ->nsec3tree, &domain->nsec3->nsec3_node); 233d3fecca9Ssthen if(domain->nsec3->hash_node.key) 234d3fecca9Ssthen zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain) 235d3fecca9Ssthen ->hashtree, &domain->nsec3->hash_node); 236d3fecca9Ssthen if(domain->nsec3->wchash_node.key) 237d3fecca9Ssthen zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain) 238d3fecca9Ssthen ->wchashtree, &domain->nsec3->wchash_node); 239d3fecca9Ssthen if(domain->nsec3->dshash_node.key) 240d3fecca9Ssthen zone_del_domain_in_hash_tree(nsec3_tree_dszone(db, domain) 241d3fecca9Ssthen ->dshashtree, &domain->nsec3->dshash_node); 242d3fecca9Ssthen region_recycle(db->domains->region, domain->nsec3, 243d3fecca9Ssthen sizeof(struct nsec3_domain_data)); 244d3fecca9Ssthen } 245d3fecca9Ssthen #endif /* NSEC3 */ 246d3fecca9Ssthen 247d3fecca9Ssthen /* see if this domain is someones wildcard-child-closest-match, 248d3fecca9Ssthen * which can only be the parent, and then it should use the 249d3fecca9Ssthen * one-smaller than this domain as closest-match. */ 250d3fecca9Ssthen if(domain->parent->wildcard_child_closest_match == domain) 251d3fecca9Ssthen domain->parent->wildcard_child_closest_match = 252*03739794Sbrad domain_previous_existing_child(domain); 253d3fecca9Ssthen 254d3fecca9Ssthen /* actual removal */ 255d3fecca9Ssthen radix_delete(db->domains->nametree, domain->rnode); 256d3fecca9Ssthen region_recycle(db->domains->region, (dname_type*)domain->dname, 257d3fecca9Ssthen dname_total_size(domain->dname)); 258d3fecca9Ssthen region_recycle(db->domains->region, domain, sizeof(domain_type)); 259d3fecca9Ssthen } 260d3fecca9Ssthen 261d3fecca9Ssthen void 262d3fecca9Ssthen domain_table_deldomain(namedb_type* db, domain_type* domain) 263d3fecca9Ssthen { 264d3fecca9Ssthen while(domain_can_be_deleted(domain)) { 265d3fecca9Ssthen /* delete it */ 266d3fecca9Ssthen do_deldomain(db, domain); 267d3fecca9Ssthen /* test parent */ 268d3fecca9Ssthen domain = domain->parent; 269d3fecca9Ssthen } 270d3fecca9Ssthen } 271d3fecca9Ssthen 272d3fecca9Ssthen /** clear hash tree */ 273d3fecca9Ssthen void 274d3fecca9Ssthen hash_tree_clear(rbtree_t* tree) 275d3fecca9Ssthen { 276d3fecca9Ssthen rbnode_t* n; 277d3fecca9Ssthen if(!tree) return; 278d3fecca9Ssthen 279d3fecca9Ssthen /* note that elements are no longer in the tree */ 280d3fecca9Ssthen for(n=rbtree_first(tree); n!=RBTREE_NULL; n=rbtree_next(n)) { 281d3fecca9Ssthen n->key = NULL; 282d3fecca9Ssthen } 283d3fecca9Ssthen tree->count = 0; 284d3fecca9Ssthen tree->root = RBTREE_NULL; 285d3fecca9Ssthen } 286d3fecca9Ssthen 287d3fecca9Ssthen void hash_tree_delete(region_type* region, rbtree_t* tree) 288d3fecca9Ssthen { 289d3fecca9Ssthen region_recycle(region, tree, sizeof(rbtree_t)); 290d3fecca9Ssthen } 291d3fecca9Ssthen 292d3fecca9Ssthen /** add domain nsec3 node to hashedspace tree */ 293d3fecca9Ssthen void zone_add_domain_in_hash_tree(region_type* region, rbtree_t** tree, 294d3fecca9Ssthen int (*cmpf)(const void*, const void*), 295d3fecca9Ssthen domain_type* domain, rbnode_t* node) 296d3fecca9Ssthen { 297d3fecca9Ssthen if(!*tree) 298d3fecca9Ssthen *tree = rbtree_create(region, cmpf); 299d3fecca9Ssthen memset(node, 0, sizeof(rbnode_t)); 300d3fecca9Ssthen node->key = domain; 301d3fecca9Ssthen rbtree_insert(*tree, node); 302d3fecca9Ssthen } 303d3fecca9Ssthen 30462ac0c33Sjakob domain_table_type * 30562ac0c33Sjakob domain_table_create(region_type* region) 30662ac0c33Sjakob { 30762ac0c33Sjakob const dname_type* origin; 30862ac0c33Sjakob domain_table_type* result; 30962ac0c33Sjakob domain_type* root; 31062ac0c33Sjakob 31162ac0c33Sjakob assert(region); 31262ac0c33Sjakob 31362ac0c33Sjakob origin = dname_make(region, (uint8_t *) "", 0); 31462ac0c33Sjakob 31562ac0c33Sjakob root = (domain_type *) region_alloc(region, sizeof(domain_type)); 316d3fecca9Ssthen root->dname = origin; 31762ac0c33Sjakob root->parent = NULL; 31862ac0c33Sjakob root->wildcard_child_closest_match = root; 31962ac0c33Sjakob root->rrsets = NULL; 32062ac0c33Sjakob root->number = 1; /* 0 is used for after header */ 321d3fecca9Ssthen root->usage = 1; /* do not delete root, ever */ 32262ac0c33Sjakob root->is_existing = 0; 32362ac0c33Sjakob root->is_apex = 0; 324d3fecca9Ssthen root->numlist_prev = NULL; 325d3fecca9Ssthen root->numlist_next = NULL; 32662ac0c33Sjakob #ifdef NSEC3 327d3fecca9Ssthen root->nsec3 = NULL; 328d3fecca9Ssthen #endif 32962ac0c33Sjakob 33062ac0c33Sjakob result = (domain_table_type *) region_alloc(region, 33162ac0c33Sjakob sizeof(domain_table_type)); 33262ac0c33Sjakob result->region = region; 333d3fecca9Ssthen result->nametree = radix_tree_create(region); 334d3fecca9Ssthen root->rnode = radname_insert(result->nametree, dname_name(root->dname), 335d3fecca9Ssthen root->dname->name_size, root); 33662ac0c33Sjakob 33762ac0c33Sjakob result->root = root; 338d3fecca9Ssthen result->numlist_last = root; 339d3fecca9Ssthen #ifdef NSEC3 340d3fecca9Ssthen result->prehash_list = NULL; 341d3fecca9Ssthen #endif 34262ac0c33Sjakob 34362ac0c33Sjakob return result; 34462ac0c33Sjakob } 34562ac0c33Sjakob 34662ac0c33Sjakob int 34762ac0c33Sjakob domain_table_search(domain_table_type *table, 34862ac0c33Sjakob const dname_type *dname, 34962ac0c33Sjakob domain_type **closest_match, 35062ac0c33Sjakob domain_type **closest_encloser) 35162ac0c33Sjakob { 35262ac0c33Sjakob int exact; 35362ac0c33Sjakob uint8_t label_match_count; 35462ac0c33Sjakob 35562ac0c33Sjakob assert(table); 35662ac0c33Sjakob assert(dname); 35762ac0c33Sjakob assert(closest_match); 35862ac0c33Sjakob assert(closest_encloser); 35962ac0c33Sjakob 360d3fecca9Ssthen exact = radname_find_less_equal(table->nametree, dname_name(dname), 361d3fecca9Ssthen dname->name_size, (struct radnode**)closest_match); 362d3fecca9Ssthen *closest_match = (domain_type*)((*(struct radnode**)closest_match)->elem); 36362ac0c33Sjakob assert(*closest_match); 36462ac0c33Sjakob 36562ac0c33Sjakob *closest_encloser = *closest_match; 36662ac0c33Sjakob 36762ac0c33Sjakob if (!exact) { 36862ac0c33Sjakob label_match_count = dname_label_match_count( 36962ac0c33Sjakob domain_dname(*closest_encloser), 37062ac0c33Sjakob dname); 37162ac0c33Sjakob assert(label_match_count < dname->label_count); 37262ac0c33Sjakob while (label_match_count < domain_dname(*closest_encloser)->label_count) { 37362ac0c33Sjakob (*closest_encloser) = (*closest_encloser)->parent; 37462ac0c33Sjakob assert(*closest_encloser); 37562ac0c33Sjakob } 37662ac0c33Sjakob } 37762ac0c33Sjakob 37862ac0c33Sjakob return exact; 37962ac0c33Sjakob } 38062ac0c33Sjakob 38162ac0c33Sjakob domain_type * 38262ac0c33Sjakob domain_table_find(domain_table_type* table, 38362ac0c33Sjakob const dname_type* dname) 38462ac0c33Sjakob { 38562ac0c33Sjakob domain_type* closest_match; 38662ac0c33Sjakob domain_type* closest_encloser; 38762ac0c33Sjakob int exact; 38862ac0c33Sjakob 38962ac0c33Sjakob exact = domain_table_search( 39062ac0c33Sjakob table, dname, &closest_match, &closest_encloser); 39162ac0c33Sjakob return exact ? closest_encloser : NULL; 39262ac0c33Sjakob } 39362ac0c33Sjakob 39462ac0c33Sjakob 39562ac0c33Sjakob domain_type * 39662ac0c33Sjakob domain_table_insert(domain_table_type* table, 39762ac0c33Sjakob const dname_type* dname) 39862ac0c33Sjakob { 39962ac0c33Sjakob domain_type* closest_match; 40062ac0c33Sjakob domain_type* closest_encloser; 40162ac0c33Sjakob domain_type* result; 40262ac0c33Sjakob int exact; 40362ac0c33Sjakob 40462ac0c33Sjakob assert(table); 40562ac0c33Sjakob assert(dname); 40662ac0c33Sjakob 40762ac0c33Sjakob exact = domain_table_search( 40862ac0c33Sjakob table, dname, &closest_match, &closest_encloser); 40962ac0c33Sjakob if (exact) { 41062ac0c33Sjakob result = closest_encloser; 41162ac0c33Sjakob } else { 41262ac0c33Sjakob assert(domain_dname(closest_encloser)->label_count < dname->label_count); 41362ac0c33Sjakob 41462ac0c33Sjakob /* Insert new node(s). */ 41562ac0c33Sjakob do { 41662ac0c33Sjakob result = allocate_domain_info(table, 41762ac0c33Sjakob dname, 41862ac0c33Sjakob closest_encloser); 419d3fecca9Ssthen result->rnode = radname_insert(table->nametree, 420d3fecca9Ssthen dname_name(result->dname), 421d3fecca9Ssthen result->dname->name_size, result); 42262ac0c33Sjakob 42362ac0c33Sjakob /* 42462ac0c33Sjakob * If the newly added domain name is larger 42562ac0c33Sjakob * than the parent's current 42662ac0c33Sjakob * wildcard_child_closest_match but smaller or 42762ac0c33Sjakob * equal to the wildcard domain name, update 42862ac0c33Sjakob * the parent's wildcard_child_closest_match 42962ac0c33Sjakob * field. 43062ac0c33Sjakob */ 43162ac0c33Sjakob if (label_compare(dname_name(domain_dname(result)), 43262ac0c33Sjakob (const uint8_t *) "\001*") <= 0 43362ac0c33Sjakob && dname_compare(domain_dname(result), 43462ac0c33Sjakob domain_dname(closest_encloser->wildcard_child_closest_match)) > 0) 43562ac0c33Sjakob { 43662ac0c33Sjakob closest_encloser->wildcard_child_closest_match 43762ac0c33Sjakob = result; 43862ac0c33Sjakob } 43962ac0c33Sjakob closest_encloser = result; 44062ac0c33Sjakob } while (domain_dname(closest_encloser)->label_count < dname->label_count); 44162ac0c33Sjakob } 44262ac0c33Sjakob 44362ac0c33Sjakob return result; 44462ac0c33Sjakob } 44562ac0c33Sjakob 44662ac0c33Sjakob int 44762ac0c33Sjakob domain_table_iterate(domain_table_type* table, 44862ac0c33Sjakob domain_table_iterator_type iterator, 44962ac0c33Sjakob void* user_data) 45062ac0c33Sjakob { 45162ac0c33Sjakob int error = 0; 452d3fecca9Ssthen struct radnode* n; 453d3fecca9Ssthen for(n = radix_first(table->nametree); n; n = radix_next(n)) { 454d3fecca9Ssthen error += iterator((domain_type*)n->elem, user_data); 45562ac0c33Sjakob } 45662ac0c33Sjakob return error; 45762ac0c33Sjakob } 45862ac0c33Sjakob 459*03739794Sbrad domain_type *domain_previous_existing_child(domain_type* domain) 460*03739794Sbrad { 461*03739794Sbrad domain_type* parent = domain->parent; 462*03739794Sbrad domain = domain_previous(domain); 463*03739794Sbrad while(domain && !domain->is_existing) { 464*03739794Sbrad if(domain == parent) /* do not walk back above parent */ 465*03739794Sbrad return parent; 466*03739794Sbrad domain = domain_previous(domain); 467*03739794Sbrad } 468*03739794Sbrad return domain; 469*03739794Sbrad } 47062ac0c33Sjakob 47162ac0c33Sjakob void 47262ac0c33Sjakob domain_add_rrset(domain_type* domain, rrset_type* rrset) 47362ac0c33Sjakob { 47462ac0c33Sjakob #if 0 /* fast */ 47562ac0c33Sjakob rrset->next = domain->rrsets; 47662ac0c33Sjakob domain->rrsets = rrset; 47762ac0c33Sjakob #else 47862ac0c33Sjakob /* preserve ordering, add at end */ 47962ac0c33Sjakob rrset_type** p = &domain->rrsets; 48062ac0c33Sjakob while(*p) 48162ac0c33Sjakob p = &((*p)->next); 48262ac0c33Sjakob *p = rrset; 48362ac0c33Sjakob rrset->next = 0; 48462ac0c33Sjakob #endif 48562ac0c33Sjakob 48662ac0c33Sjakob while (domain && !domain->is_existing) { 48762ac0c33Sjakob domain->is_existing = 1; 488*03739794Sbrad /* does this name in existance update the parent's 489*03739794Sbrad * wildcard closest match? */ 490*03739794Sbrad if(domain->parent 491*03739794Sbrad && label_compare(dname_name(domain_dname(domain)), 492*03739794Sbrad (const uint8_t *) "\001*") <= 0 493*03739794Sbrad && dname_compare(domain_dname(domain), 494*03739794Sbrad domain_dname(domain->parent->wildcard_child_closest_match)) > 0) { 495*03739794Sbrad domain->parent->wildcard_child_closest_match = domain; 496*03739794Sbrad } 49762ac0c33Sjakob domain = domain->parent; 49862ac0c33Sjakob } 49962ac0c33Sjakob } 50062ac0c33Sjakob 50162ac0c33Sjakob 50262ac0c33Sjakob rrset_type * 50362ac0c33Sjakob domain_find_rrset(domain_type* domain, zone_type* zone, uint16_t type) 50462ac0c33Sjakob { 50562ac0c33Sjakob rrset_type* result = domain->rrsets; 50662ac0c33Sjakob 50762ac0c33Sjakob while (result) { 50862ac0c33Sjakob if (result->zone == zone && rrset_rrtype(result) == type) { 50962ac0c33Sjakob return result; 51062ac0c33Sjakob } 51162ac0c33Sjakob result = result->next; 51262ac0c33Sjakob } 51362ac0c33Sjakob return NULL; 51462ac0c33Sjakob } 51562ac0c33Sjakob 51662ac0c33Sjakob rrset_type * 51762ac0c33Sjakob domain_find_any_rrset(domain_type* domain, zone_type* zone) 51862ac0c33Sjakob { 51962ac0c33Sjakob rrset_type* result = domain->rrsets; 52062ac0c33Sjakob 52162ac0c33Sjakob while (result) { 52262ac0c33Sjakob if (result->zone == zone) { 52362ac0c33Sjakob return result; 52462ac0c33Sjakob } 52562ac0c33Sjakob result = result->next; 52662ac0c33Sjakob } 52762ac0c33Sjakob return NULL; 52862ac0c33Sjakob } 52962ac0c33Sjakob 53062ac0c33Sjakob zone_type * 531cbbc2d6cSbrad domain_find_zone(namedb_type* db, domain_type* domain) 53262ac0c33Sjakob { 53362ac0c33Sjakob rrset_type* rrset; 53462ac0c33Sjakob while (domain) { 535cbbc2d6cSbrad if(domain->is_apex) { 53662ac0c33Sjakob for (rrset = domain->rrsets; rrset; rrset = rrset->next) { 53762ac0c33Sjakob if (rrset_rrtype(rrset) == TYPE_SOA) { 53862ac0c33Sjakob return rrset->zone; 53962ac0c33Sjakob } 54062ac0c33Sjakob } 541cbbc2d6cSbrad return namedb_find_zone(db, domain_dname(domain)); 542cbbc2d6cSbrad } 54362ac0c33Sjakob domain = domain->parent; 54462ac0c33Sjakob } 54562ac0c33Sjakob return NULL; 54662ac0c33Sjakob } 54762ac0c33Sjakob 54862ac0c33Sjakob zone_type * 54962ac0c33Sjakob domain_find_parent_zone(zone_type* zone) 55062ac0c33Sjakob { 55162ac0c33Sjakob rrset_type* rrset; 55262ac0c33Sjakob 55362ac0c33Sjakob assert(zone); 55462ac0c33Sjakob 55562ac0c33Sjakob for (rrset = zone->apex->rrsets; rrset; rrset = rrset->next) { 55662ac0c33Sjakob if (rrset->zone != zone && rrset_rrtype(rrset) == TYPE_NS) { 55762ac0c33Sjakob return rrset->zone; 55862ac0c33Sjakob } 55962ac0c33Sjakob } 56062ac0c33Sjakob return NULL; 56162ac0c33Sjakob } 56262ac0c33Sjakob 56362ac0c33Sjakob domain_type * 56462ac0c33Sjakob domain_find_ns_rrsets(domain_type* domain, zone_type* zone, rrset_type **ns) 56562ac0c33Sjakob { 56662ac0c33Sjakob while (domain && domain != zone->apex) { 56762ac0c33Sjakob *ns = domain_find_rrset(domain, zone, TYPE_NS); 56862ac0c33Sjakob if (*ns) 56962ac0c33Sjakob return domain; 57062ac0c33Sjakob domain = domain->parent; 57162ac0c33Sjakob } 57262ac0c33Sjakob 57362ac0c33Sjakob *ns = NULL; 57462ac0c33Sjakob return NULL; 57562ac0c33Sjakob } 57662ac0c33Sjakob 57762ac0c33Sjakob int 57862ac0c33Sjakob domain_is_glue(domain_type* domain, zone_type* zone) 57962ac0c33Sjakob { 58062ac0c33Sjakob rrset_type* unused; 58162ac0c33Sjakob domain_type* ns_domain = domain_find_ns_rrsets(domain, zone, &unused); 58262ac0c33Sjakob return (ns_domain != NULL && 58362ac0c33Sjakob domain_find_rrset(ns_domain, zone, TYPE_SOA) == NULL); 58462ac0c33Sjakob } 58562ac0c33Sjakob 58662ac0c33Sjakob domain_type * 58762ac0c33Sjakob domain_wildcard_child(domain_type* domain) 58862ac0c33Sjakob { 58962ac0c33Sjakob domain_type* wildcard_child; 59062ac0c33Sjakob 59162ac0c33Sjakob assert(domain); 59262ac0c33Sjakob assert(domain->wildcard_child_closest_match); 59362ac0c33Sjakob 59462ac0c33Sjakob wildcard_child = domain->wildcard_child_closest_match; 59562ac0c33Sjakob if (wildcard_child != domain 59662ac0c33Sjakob && label_is_wildcard(dname_name(domain_dname(wildcard_child)))) 59762ac0c33Sjakob { 59862ac0c33Sjakob return wildcard_child; 59962ac0c33Sjakob } else { 60062ac0c33Sjakob return NULL; 60162ac0c33Sjakob } 60262ac0c33Sjakob } 60362ac0c33Sjakob 60462ac0c33Sjakob int 60562ac0c33Sjakob zone_is_secure(zone_type* zone) 60662ac0c33Sjakob { 60762ac0c33Sjakob assert(zone); 60862ac0c33Sjakob return zone->is_secure; 60962ac0c33Sjakob } 61062ac0c33Sjakob 61162ac0c33Sjakob uint16_t 61262ac0c33Sjakob rr_rrsig_type_covered(rr_type* rr) 61362ac0c33Sjakob { 61462ac0c33Sjakob assert(rr->type == TYPE_RRSIG); 61562ac0c33Sjakob assert(rr->rdata_count > 0); 61662ac0c33Sjakob assert(rdata_atom_size(rr->rdatas[0]) == sizeof(uint16_t)); 61762ac0c33Sjakob 61862ac0c33Sjakob return ntohs(* (uint16_t *) rdata_atom_data(rr->rdatas[0])); 61962ac0c33Sjakob } 62062ac0c33Sjakob 62162ac0c33Sjakob zone_type * 622d3fecca9Ssthen namedb_find_zone(namedb_type* db, const dname_type* dname) 62362ac0c33Sjakob { 624d3fecca9Ssthen struct radnode* n = radname_search(db->zonetree, dname_name(dname), 625d3fecca9Ssthen dname->name_size); 626d3fecca9Ssthen if(n) return (zone_type*)n->elem; 627d3fecca9Ssthen return NULL; 62862ac0c33Sjakob } 62962ac0c33Sjakob 63062ac0c33Sjakob rrset_type * 63162ac0c33Sjakob domain_find_non_cname_rrset(domain_type* domain, zone_type* zone) 63262ac0c33Sjakob { 63362ac0c33Sjakob /* find any rrset type that is not allowed next to a CNAME */ 63462ac0c33Sjakob /* nothing is allowed next to a CNAME, except RRSIG, NSEC, NSEC3 */ 63562ac0c33Sjakob rrset_type *result = domain->rrsets; 63662ac0c33Sjakob 63762ac0c33Sjakob while (result) { 63862ac0c33Sjakob if (result->zone == zone && /* here is the list of exceptions*/ 63962ac0c33Sjakob rrset_rrtype(result) != TYPE_CNAME && 64062ac0c33Sjakob rrset_rrtype(result) != TYPE_RRSIG && 64162ac0c33Sjakob rrset_rrtype(result) != TYPE_NXT && 64262ac0c33Sjakob rrset_rrtype(result) != TYPE_SIG && 64362ac0c33Sjakob rrset_rrtype(result) != TYPE_NSEC && 64462ac0c33Sjakob rrset_rrtype(result) != TYPE_NSEC3 ) { 64562ac0c33Sjakob return result; 64662ac0c33Sjakob } 64762ac0c33Sjakob result = result->next; 64862ac0c33Sjakob } 64962ac0c33Sjakob return NULL; 65062ac0c33Sjakob } 6510c2b6c02Sjakob 6520c2b6c02Sjakob int 653d3fecca9Ssthen namedb_lookup(struct namedb* db, 654d3fecca9Ssthen const dname_type* dname, 655d3fecca9Ssthen domain_type **closest_match, 656d3fecca9Ssthen domain_type **closest_encloser) 6570c2b6c02Sjakob { 658d3fecca9Ssthen return domain_table_search( 659d3fecca9Ssthen db->domains, dname, closest_match, closest_encloser); 6600c2b6c02Sjakob } 661