162ac0c33Sjakob /* 262ac0c33Sjakob * namedb.c -- common namedb operations. 362ac0c33Sjakob * 4*d3fecca9Ssthen * 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" 21*d3fecca9Ssthen #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*d3fecca9Ssthen 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; 41*d3fecca9Ssthen result->usage = 0; 4262ac0c33Sjakob #ifdef NSEC3 43*d3fecca9Ssthen result->nsec3 = NULL; 44*d3fecca9Ssthen #endif 4562ac0c33Sjakob result->is_existing = 0; 4662ac0c33Sjakob result->is_apex = 0; 47*d3fecca9Ssthen assert(table->numlist_last); /* it exists because root exists */ 48*d3fecca9Ssthen /* push this domain at the end of the numlist */ 49*d3fecca9Ssthen result->number = table->numlist_last->number+1; 50*d3fecca9Ssthen result->numlist_next = NULL; 51*d3fecca9Ssthen result->numlist_prev = table->numlist_last; 52*d3fecca9Ssthen table->numlist_last->numlist_next = result; 53*d3fecca9Ssthen table->numlist_last = result; 5462ac0c33Sjakob 5562ac0c33Sjakob return result; 5662ac0c33Sjakob } 5762ac0c33Sjakob 58*d3fecca9Ssthen #ifdef NSEC3 59*d3fecca9Ssthen void 60*d3fecca9Ssthen allocate_domain_nsec3(domain_table_type* table, domain_type* result) 61*d3fecca9Ssthen { 62*d3fecca9Ssthen if(result->nsec3) 63*d3fecca9Ssthen return; 64*d3fecca9Ssthen result->nsec3 = (struct nsec3_domain_data*) region_alloc(table->region, 65*d3fecca9Ssthen sizeof(struct nsec3_domain_data)); 66*d3fecca9Ssthen result->nsec3->nsec3_cover = NULL; 67*d3fecca9Ssthen result->nsec3->nsec3_wcard_child_cover = NULL; 68*d3fecca9Ssthen result->nsec3->nsec3_ds_parent_cover = NULL; 69*d3fecca9Ssthen result->nsec3->nsec3_is_exact = 0; 70*d3fecca9Ssthen result->nsec3->nsec3_ds_parent_is_exact = 0; 71*d3fecca9Ssthen result->nsec3->have_nsec3_hash = 0; 72*d3fecca9Ssthen result->nsec3->have_nsec3_wc_hash = 0; 73*d3fecca9Ssthen result->nsec3->have_nsec3_ds_parent_hash = 0; 74*d3fecca9Ssthen result->nsec3->prehash_prev = NULL; 75*d3fecca9Ssthen result->nsec3->prehash_next = NULL; 76*d3fecca9Ssthen result->nsec3->nsec3_node.key = NULL; 77*d3fecca9Ssthen result->nsec3->hash_node.key = NULL; 78*d3fecca9Ssthen result->nsec3->wchash_node.key = NULL; 79*d3fecca9Ssthen result->nsec3->dshash_node.key = NULL; 80*d3fecca9Ssthen } 81*d3fecca9Ssthen #endif /* NSEC3 */ 82*d3fecca9Ssthen 83*d3fecca9Ssthen /** make the domain last in the numlist, changes numbers of domains */ 84*d3fecca9Ssthen static void 85*d3fecca9Ssthen numlist_make_last(domain_table_type* table, domain_type* domain) 86*d3fecca9Ssthen { 87*d3fecca9Ssthen size_t sw; 88*d3fecca9Ssthen domain_type* last = table->numlist_last; 89*d3fecca9Ssthen if(domain == last) 90*d3fecca9Ssthen return; 91*d3fecca9Ssthen /* swap numbers with the last element */ 92*d3fecca9Ssthen sw = domain->number; 93*d3fecca9Ssthen domain->number = last->number; 94*d3fecca9Ssthen last->number = sw; 95*d3fecca9Ssthen /* swap list position with the last element */ 96*d3fecca9Ssthen assert(domain->numlist_next); 97*d3fecca9Ssthen assert(last->numlist_prev); 98*d3fecca9Ssthen if(domain->numlist_next != last) { 99*d3fecca9Ssthen /* case 1: there are nodes between domain .. last */ 100*d3fecca9Ssthen domain_type* span_start = domain->numlist_next; 101*d3fecca9Ssthen domain_type* span_end = last->numlist_prev; 102*d3fecca9Ssthen /* these assignments walk the new list from start to end */ 103*d3fecca9Ssthen if(domain->numlist_prev) 104*d3fecca9Ssthen domain->numlist_prev->numlist_next = last; 105*d3fecca9Ssthen last->numlist_prev = domain->numlist_prev; 106*d3fecca9Ssthen last->numlist_next = span_start; 107*d3fecca9Ssthen span_start->numlist_prev = last; 108*d3fecca9Ssthen span_end->numlist_next = domain; 109*d3fecca9Ssthen domain->numlist_prev = span_end; 110*d3fecca9Ssthen domain->numlist_next = NULL; 111*d3fecca9Ssthen } else { 112*d3fecca9Ssthen /* case 2: domain and last are neighbors */ 113*d3fecca9Ssthen /* these assignments walk the new list from start to end */ 114*d3fecca9Ssthen if(domain->numlist_prev) 115*d3fecca9Ssthen domain->numlist_prev->numlist_next = last; 116*d3fecca9Ssthen last->numlist_prev = domain->numlist_prev; 117*d3fecca9Ssthen last->numlist_next = domain; 118*d3fecca9Ssthen domain->numlist_prev = last; 119*d3fecca9Ssthen domain->numlist_next = NULL; 120*d3fecca9Ssthen } 121*d3fecca9Ssthen table->numlist_last = domain; 122*d3fecca9Ssthen } 123*d3fecca9Ssthen 124*d3fecca9Ssthen /** pop the biggest domain off the numlist */ 125*d3fecca9Ssthen static domain_type* 126*d3fecca9Ssthen numlist_pop_last(domain_table_type* table) 127*d3fecca9Ssthen { 128*d3fecca9Ssthen domain_type* d = table->numlist_last; 129*d3fecca9Ssthen table->numlist_last = table->numlist_last->numlist_prev; 130*d3fecca9Ssthen if(table->numlist_last) 131*d3fecca9Ssthen table->numlist_last->numlist_next = NULL; 132*d3fecca9Ssthen return d; 133*d3fecca9Ssthen } 134*d3fecca9Ssthen 135*d3fecca9Ssthen /** see if a domain is eligible to be deleted, and thus is not used */ 136*d3fecca9Ssthen static int 137*d3fecca9Ssthen domain_can_be_deleted(domain_type* domain) 138*d3fecca9Ssthen { 139*d3fecca9Ssthen domain_type* n; 140*d3fecca9Ssthen /* it has data or it has usage, do not delete it */ 141*d3fecca9Ssthen if(domain->rrsets) return 0; 142*d3fecca9Ssthen if(domain->usage) return 0; 143*d3fecca9Ssthen n = domain_next(domain); 144*d3fecca9Ssthen /* it has children domains, do not delete it */ 145*d3fecca9Ssthen if(n && domain_is_subdomain(n, domain)) 146*d3fecca9Ssthen return 0; 147*d3fecca9Ssthen return 1; 148*d3fecca9Ssthen } 149*d3fecca9Ssthen 150*d3fecca9Ssthen #ifdef NSEC3 151*d3fecca9Ssthen /** see if domain is on the prehash list */ 152*d3fecca9Ssthen int domain_is_prehash(domain_table_type* table, domain_type* domain) 153*d3fecca9Ssthen { 154*d3fecca9Ssthen if(domain->nsec3 155*d3fecca9Ssthen && (domain->nsec3->prehash_prev || domain->nsec3->prehash_next)) 156*d3fecca9Ssthen return 1; 157*d3fecca9Ssthen return (table->prehash_list == domain); 158*d3fecca9Ssthen } 159*d3fecca9Ssthen 160*d3fecca9Ssthen /** remove domain node from NSEC3 tree in hash space */ 161*d3fecca9Ssthen void 162*d3fecca9Ssthen zone_del_domain_in_hash_tree(rbtree_t* tree, rbnode_t* node) 163*d3fecca9Ssthen { 164*d3fecca9Ssthen if(!node->key) 165*d3fecca9Ssthen return; 166*d3fecca9Ssthen rbtree_delete(tree, node->key); 167*d3fecca9Ssthen /* note that domain is no longer in the tree */ 168*d3fecca9Ssthen node->key = NULL; 169*d3fecca9Ssthen } 170*d3fecca9Ssthen 171*d3fecca9Ssthen /** clear the prehash list */ 172*d3fecca9Ssthen void prehash_clear(domain_table_type* table) 173*d3fecca9Ssthen { 174*d3fecca9Ssthen domain_type* d = table->prehash_list, *n; 175*d3fecca9Ssthen while(d) { 176*d3fecca9Ssthen n = d->nsec3->prehash_next; 177*d3fecca9Ssthen d->nsec3->prehash_prev = NULL; 178*d3fecca9Ssthen d->nsec3->prehash_next = NULL; 179*d3fecca9Ssthen d = n; 180*d3fecca9Ssthen } 181*d3fecca9Ssthen table->prehash_list = NULL; 182*d3fecca9Ssthen } 183*d3fecca9Ssthen 184*d3fecca9Ssthen /** add domain to prehash list */ 185*d3fecca9Ssthen void 186*d3fecca9Ssthen prehash_add(domain_table_type* table, domain_type* domain) 187*d3fecca9Ssthen { 188*d3fecca9Ssthen if(domain_is_prehash(table, domain)) 189*d3fecca9Ssthen return; 190*d3fecca9Ssthen allocate_domain_nsec3(table, domain); 191*d3fecca9Ssthen domain->nsec3->prehash_next = table->prehash_list; 192*d3fecca9Ssthen if(table->prehash_list) 193*d3fecca9Ssthen table->prehash_list->nsec3->prehash_prev = domain; 194*d3fecca9Ssthen table->prehash_list = domain; 195*d3fecca9Ssthen } 196*d3fecca9Ssthen 197*d3fecca9Ssthen /** remove domain from prehash list */ 198*d3fecca9Ssthen void 199*d3fecca9Ssthen prehash_del(domain_table_type* table, domain_type* domain) 200*d3fecca9Ssthen { 201*d3fecca9Ssthen if(domain->nsec3->prehash_next) 202*d3fecca9Ssthen domain->nsec3->prehash_next->nsec3->prehash_prev = 203*d3fecca9Ssthen domain->nsec3->prehash_prev; 204*d3fecca9Ssthen if(domain->nsec3->prehash_prev) 205*d3fecca9Ssthen domain->nsec3->prehash_prev->nsec3->prehash_next = 206*d3fecca9Ssthen domain->nsec3->prehash_next; 207*d3fecca9Ssthen else table->prehash_list = domain->nsec3->prehash_next; 208*d3fecca9Ssthen domain->nsec3->prehash_next = NULL; 209*d3fecca9Ssthen domain->nsec3->prehash_prev = NULL; 210*d3fecca9Ssthen } 211*d3fecca9Ssthen #endif /* NSEC3 */ 212*d3fecca9Ssthen 213*d3fecca9Ssthen /** perform domain name deletion */ 214*d3fecca9Ssthen static void 215*d3fecca9Ssthen do_deldomain(namedb_type* db, domain_type* domain) 216*d3fecca9Ssthen { 217*d3fecca9Ssthen assert(domain && domain->parent); /* exists and not root */ 218*d3fecca9Ssthen /* first adjust the number list so that domain is the last one */ 219*d3fecca9Ssthen numlist_make_last(db->domains, domain); 220*d3fecca9Ssthen /* pop off the domain from the number list */ 221*d3fecca9Ssthen (void)numlist_pop_last(db->domains); 222*d3fecca9Ssthen 223*d3fecca9Ssthen #ifdef NSEC3 224*d3fecca9Ssthen /* if on prehash list, remove from prehash */ 225*d3fecca9Ssthen if(domain_is_prehash(db->domains, domain)) 226*d3fecca9Ssthen prehash_del(db->domains, domain); 227*d3fecca9Ssthen 228*d3fecca9Ssthen /* see if nsec3-nodes are used */ 229*d3fecca9Ssthen if(domain->nsec3) { 230*d3fecca9Ssthen if(domain->nsec3->nsec3_node.key) 231*d3fecca9Ssthen zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain) 232*d3fecca9Ssthen ->nsec3tree, &domain->nsec3->nsec3_node); 233*d3fecca9Ssthen if(domain->nsec3->hash_node.key) 234*d3fecca9Ssthen zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain) 235*d3fecca9Ssthen ->hashtree, &domain->nsec3->hash_node); 236*d3fecca9Ssthen if(domain->nsec3->wchash_node.key) 237*d3fecca9Ssthen zone_del_domain_in_hash_tree(nsec3_tree_zone(db, domain) 238*d3fecca9Ssthen ->wchashtree, &domain->nsec3->wchash_node); 239*d3fecca9Ssthen if(domain->nsec3->dshash_node.key) 240*d3fecca9Ssthen zone_del_domain_in_hash_tree(nsec3_tree_dszone(db, domain) 241*d3fecca9Ssthen ->dshashtree, &domain->nsec3->dshash_node); 242*d3fecca9Ssthen region_recycle(db->domains->region, domain->nsec3, 243*d3fecca9Ssthen sizeof(struct nsec3_domain_data)); 244*d3fecca9Ssthen } 245*d3fecca9Ssthen #endif /* NSEC3 */ 246*d3fecca9Ssthen 247*d3fecca9Ssthen /* see if this domain is someones wildcard-child-closest-match, 248*d3fecca9Ssthen * which can only be the parent, and then it should use the 249*d3fecca9Ssthen * one-smaller than this domain as closest-match. */ 250*d3fecca9Ssthen if(domain->parent->wildcard_child_closest_match == domain) 251*d3fecca9Ssthen domain->parent->wildcard_child_closest_match = 252*d3fecca9Ssthen domain_previous(domain); 253*d3fecca9Ssthen 254*d3fecca9Ssthen /* actual removal */ 255*d3fecca9Ssthen radix_delete(db->domains->nametree, domain->rnode); 256*d3fecca9Ssthen region_recycle(db->domains->region, (dname_type*)domain->dname, 257*d3fecca9Ssthen dname_total_size(domain->dname)); 258*d3fecca9Ssthen region_recycle(db->domains->region, domain, sizeof(domain_type)); 259*d3fecca9Ssthen } 260*d3fecca9Ssthen 261*d3fecca9Ssthen void 262*d3fecca9Ssthen domain_table_deldomain(namedb_type* db, domain_type* domain) 263*d3fecca9Ssthen { 264*d3fecca9Ssthen while(domain_can_be_deleted(domain)) { 265*d3fecca9Ssthen /* delete it */ 266*d3fecca9Ssthen do_deldomain(db, domain); 267*d3fecca9Ssthen /* test parent */ 268*d3fecca9Ssthen domain = domain->parent; 269*d3fecca9Ssthen } 270*d3fecca9Ssthen } 271*d3fecca9Ssthen 272*d3fecca9Ssthen /** clear hash tree */ 273*d3fecca9Ssthen void 274*d3fecca9Ssthen hash_tree_clear(rbtree_t* tree) 275*d3fecca9Ssthen { 276*d3fecca9Ssthen rbnode_t* n; 277*d3fecca9Ssthen if(!tree) return; 278*d3fecca9Ssthen 279*d3fecca9Ssthen /* note that elements are no longer in the tree */ 280*d3fecca9Ssthen for(n=rbtree_first(tree); n!=RBTREE_NULL; n=rbtree_next(n)) { 281*d3fecca9Ssthen n->key = NULL; 282*d3fecca9Ssthen } 283*d3fecca9Ssthen tree->count = 0; 284*d3fecca9Ssthen tree->root = RBTREE_NULL; 285*d3fecca9Ssthen } 286*d3fecca9Ssthen 287*d3fecca9Ssthen void hash_tree_delete(region_type* region, rbtree_t* tree) 288*d3fecca9Ssthen { 289*d3fecca9Ssthen region_recycle(region, tree, sizeof(rbtree_t)); 290*d3fecca9Ssthen } 291*d3fecca9Ssthen 292*d3fecca9Ssthen /** add domain nsec3 node to hashedspace tree */ 293*d3fecca9Ssthen void zone_add_domain_in_hash_tree(region_type* region, rbtree_t** tree, 294*d3fecca9Ssthen int (*cmpf)(const void*, const void*), 295*d3fecca9Ssthen domain_type* domain, rbnode_t* node) 296*d3fecca9Ssthen { 297*d3fecca9Ssthen if(!*tree) 298*d3fecca9Ssthen *tree = rbtree_create(region, cmpf); 299*d3fecca9Ssthen memset(node, 0, sizeof(rbnode_t)); 300*d3fecca9Ssthen node->key = domain; 301*d3fecca9Ssthen rbtree_insert(*tree, node); 302*d3fecca9Ssthen } 303*d3fecca9Ssthen 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)); 316*d3fecca9Ssthen 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 */ 321*d3fecca9Ssthen root->usage = 1; /* do not delete root, ever */ 32262ac0c33Sjakob root->is_existing = 0; 32362ac0c33Sjakob root->is_apex = 0; 324*d3fecca9Ssthen root->numlist_prev = NULL; 325*d3fecca9Ssthen root->numlist_next = NULL; 32662ac0c33Sjakob #ifdef NSEC3 327*d3fecca9Ssthen root->nsec3 = NULL; 328*d3fecca9Ssthen #endif 32962ac0c33Sjakob 33062ac0c33Sjakob result = (domain_table_type *) region_alloc(region, 33162ac0c33Sjakob sizeof(domain_table_type)); 33262ac0c33Sjakob result->region = region; 333*d3fecca9Ssthen result->nametree = radix_tree_create(region); 334*d3fecca9Ssthen root->rnode = radname_insert(result->nametree, dname_name(root->dname), 335*d3fecca9Ssthen root->dname->name_size, root); 33662ac0c33Sjakob 33762ac0c33Sjakob result->root = root; 338*d3fecca9Ssthen result->numlist_last = root; 339*d3fecca9Ssthen #ifdef NSEC3 340*d3fecca9Ssthen result->prehash_list = NULL; 341*d3fecca9Ssthen #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 360*d3fecca9Ssthen exact = radname_find_less_equal(table->nametree, dname_name(dname), 361*d3fecca9Ssthen dname->name_size, (struct radnode**)closest_match); 362*d3fecca9Ssthen *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); 419*d3fecca9Ssthen result->rnode = radname_insert(table->nametree, 420*d3fecca9Ssthen dname_name(result->dname), 421*d3fecca9Ssthen 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; 452*d3fecca9Ssthen struct radnode* n; 453*d3fecca9Ssthen for(n = radix_first(table->nametree); n; n = radix_next(n)) { 454*d3fecca9Ssthen error += iterator((domain_type*)n->elem, user_data); 45562ac0c33Sjakob } 45662ac0c33Sjakob return error; 45762ac0c33Sjakob } 45862ac0c33Sjakob 45962ac0c33Sjakob 46062ac0c33Sjakob void 46162ac0c33Sjakob domain_add_rrset(domain_type* domain, rrset_type* rrset) 46262ac0c33Sjakob { 46362ac0c33Sjakob #if 0 /* fast */ 46462ac0c33Sjakob rrset->next = domain->rrsets; 46562ac0c33Sjakob domain->rrsets = rrset; 46662ac0c33Sjakob #else 46762ac0c33Sjakob /* preserve ordering, add at end */ 46862ac0c33Sjakob rrset_type** p = &domain->rrsets; 46962ac0c33Sjakob while(*p) 47062ac0c33Sjakob p = &((*p)->next); 47162ac0c33Sjakob *p = rrset; 47262ac0c33Sjakob rrset->next = 0; 47362ac0c33Sjakob #endif 47462ac0c33Sjakob 47562ac0c33Sjakob while (domain && !domain->is_existing) { 47662ac0c33Sjakob domain->is_existing = 1; 47762ac0c33Sjakob domain = domain->parent; 47862ac0c33Sjakob } 47962ac0c33Sjakob } 48062ac0c33Sjakob 48162ac0c33Sjakob 48262ac0c33Sjakob rrset_type * 48362ac0c33Sjakob domain_find_rrset(domain_type* domain, zone_type* zone, uint16_t type) 48462ac0c33Sjakob { 48562ac0c33Sjakob rrset_type* result = domain->rrsets; 48662ac0c33Sjakob 48762ac0c33Sjakob while (result) { 48862ac0c33Sjakob if (result->zone == zone && rrset_rrtype(result) == type) { 48962ac0c33Sjakob return result; 49062ac0c33Sjakob } 49162ac0c33Sjakob result = result->next; 49262ac0c33Sjakob } 49362ac0c33Sjakob return NULL; 49462ac0c33Sjakob } 49562ac0c33Sjakob 49662ac0c33Sjakob rrset_type * 49762ac0c33Sjakob domain_find_any_rrset(domain_type* domain, zone_type* zone) 49862ac0c33Sjakob { 49962ac0c33Sjakob rrset_type* result = domain->rrsets; 50062ac0c33Sjakob 50162ac0c33Sjakob while (result) { 50262ac0c33Sjakob if (result->zone == zone) { 50362ac0c33Sjakob return result; 50462ac0c33Sjakob } 50562ac0c33Sjakob result = result->next; 50662ac0c33Sjakob } 50762ac0c33Sjakob return NULL; 50862ac0c33Sjakob } 50962ac0c33Sjakob 51062ac0c33Sjakob zone_type * 51162ac0c33Sjakob domain_find_zone(domain_type* domain) 51262ac0c33Sjakob { 51362ac0c33Sjakob rrset_type* rrset; 51462ac0c33Sjakob while (domain) { 51562ac0c33Sjakob for (rrset = domain->rrsets; rrset; rrset = rrset->next) { 51662ac0c33Sjakob if (rrset_rrtype(rrset) == TYPE_SOA) { 51762ac0c33Sjakob return rrset->zone; 51862ac0c33Sjakob } 51962ac0c33Sjakob } 52062ac0c33Sjakob domain = domain->parent; 52162ac0c33Sjakob } 52262ac0c33Sjakob return NULL; 52362ac0c33Sjakob } 52462ac0c33Sjakob 52562ac0c33Sjakob zone_type * 52662ac0c33Sjakob domain_find_parent_zone(zone_type* zone) 52762ac0c33Sjakob { 52862ac0c33Sjakob rrset_type* rrset; 52962ac0c33Sjakob 53062ac0c33Sjakob assert(zone); 53162ac0c33Sjakob 53262ac0c33Sjakob for (rrset = zone->apex->rrsets; rrset; rrset = rrset->next) { 53362ac0c33Sjakob if (rrset->zone != zone && rrset_rrtype(rrset) == TYPE_NS) { 53462ac0c33Sjakob return rrset->zone; 53562ac0c33Sjakob } 53662ac0c33Sjakob } 53762ac0c33Sjakob return NULL; 53862ac0c33Sjakob } 53962ac0c33Sjakob 54062ac0c33Sjakob domain_type * 54162ac0c33Sjakob domain_find_ns_rrsets(domain_type* domain, zone_type* zone, rrset_type **ns) 54262ac0c33Sjakob { 54362ac0c33Sjakob while (domain && domain != zone->apex) { 54462ac0c33Sjakob *ns = domain_find_rrset(domain, zone, TYPE_NS); 54562ac0c33Sjakob if (*ns) 54662ac0c33Sjakob return domain; 54762ac0c33Sjakob domain = domain->parent; 54862ac0c33Sjakob } 54962ac0c33Sjakob 55062ac0c33Sjakob *ns = NULL; 55162ac0c33Sjakob return NULL; 55262ac0c33Sjakob } 55362ac0c33Sjakob 55462ac0c33Sjakob int 55562ac0c33Sjakob domain_is_glue(domain_type* domain, zone_type* zone) 55662ac0c33Sjakob { 55762ac0c33Sjakob rrset_type* unused; 55862ac0c33Sjakob domain_type* ns_domain = domain_find_ns_rrsets(domain, zone, &unused); 55962ac0c33Sjakob return (ns_domain != NULL && 56062ac0c33Sjakob domain_find_rrset(ns_domain, zone, TYPE_SOA) == NULL); 56162ac0c33Sjakob } 56262ac0c33Sjakob 56362ac0c33Sjakob domain_type * 56462ac0c33Sjakob domain_wildcard_child(domain_type* domain) 56562ac0c33Sjakob { 56662ac0c33Sjakob domain_type* wildcard_child; 56762ac0c33Sjakob 56862ac0c33Sjakob assert(domain); 56962ac0c33Sjakob assert(domain->wildcard_child_closest_match); 57062ac0c33Sjakob 57162ac0c33Sjakob wildcard_child = domain->wildcard_child_closest_match; 57262ac0c33Sjakob if (wildcard_child != domain 57362ac0c33Sjakob && label_is_wildcard(dname_name(domain_dname(wildcard_child)))) 57462ac0c33Sjakob { 57562ac0c33Sjakob return wildcard_child; 57662ac0c33Sjakob } else { 57762ac0c33Sjakob return NULL; 57862ac0c33Sjakob } 57962ac0c33Sjakob } 58062ac0c33Sjakob 58162ac0c33Sjakob int 58262ac0c33Sjakob zone_is_secure(zone_type* zone) 58362ac0c33Sjakob { 58462ac0c33Sjakob assert(zone); 58562ac0c33Sjakob return zone->is_secure; 58662ac0c33Sjakob } 58762ac0c33Sjakob 58862ac0c33Sjakob uint16_t 58962ac0c33Sjakob rr_rrsig_type_covered(rr_type* rr) 59062ac0c33Sjakob { 59162ac0c33Sjakob assert(rr->type == TYPE_RRSIG); 59262ac0c33Sjakob assert(rr->rdata_count > 0); 59362ac0c33Sjakob assert(rdata_atom_size(rr->rdatas[0]) == sizeof(uint16_t)); 59462ac0c33Sjakob 59562ac0c33Sjakob return ntohs(* (uint16_t *) rdata_atom_data(rr->rdatas[0])); 59662ac0c33Sjakob } 59762ac0c33Sjakob 59862ac0c33Sjakob zone_type * 599*d3fecca9Ssthen namedb_find_zone(namedb_type* db, const dname_type* dname) 60062ac0c33Sjakob { 601*d3fecca9Ssthen struct radnode* n = radname_search(db->zonetree, dname_name(dname), 602*d3fecca9Ssthen dname->name_size); 603*d3fecca9Ssthen if(n) return (zone_type*)n->elem; 604*d3fecca9Ssthen return NULL; 60562ac0c33Sjakob } 60662ac0c33Sjakob 60762ac0c33Sjakob rrset_type * 60862ac0c33Sjakob domain_find_non_cname_rrset(domain_type* domain, zone_type* zone) 60962ac0c33Sjakob { 61062ac0c33Sjakob /* find any rrset type that is not allowed next to a CNAME */ 61162ac0c33Sjakob /* nothing is allowed next to a CNAME, except RRSIG, NSEC, NSEC3 */ 61262ac0c33Sjakob rrset_type *result = domain->rrsets; 61362ac0c33Sjakob 61462ac0c33Sjakob while (result) { 61562ac0c33Sjakob if (result->zone == zone && /* here is the list of exceptions*/ 61662ac0c33Sjakob rrset_rrtype(result) != TYPE_CNAME && 61762ac0c33Sjakob rrset_rrtype(result) != TYPE_RRSIG && 61862ac0c33Sjakob rrset_rrtype(result) != TYPE_NXT && 61962ac0c33Sjakob rrset_rrtype(result) != TYPE_SIG && 62062ac0c33Sjakob rrset_rrtype(result) != TYPE_NSEC && 62162ac0c33Sjakob rrset_rrtype(result) != TYPE_NSEC3 ) { 62262ac0c33Sjakob return result; 62362ac0c33Sjakob } 62462ac0c33Sjakob result = result->next; 62562ac0c33Sjakob } 62662ac0c33Sjakob return NULL; 62762ac0c33Sjakob } 6280c2b6c02Sjakob 6290c2b6c02Sjakob int 630*d3fecca9Ssthen namedb_lookup(struct namedb* db, 631*d3fecca9Ssthen const dname_type* dname, 632*d3fecca9Ssthen domain_type **closest_match, 633*d3fecca9Ssthen domain_type **closest_encloser) 6340c2b6c02Sjakob { 635*d3fecca9Ssthen return domain_table_search( 636*d3fecca9Ssthen db->domains, dname, closest_match, closest_encloser); 6370c2b6c02Sjakob } 638