1*62ac0c33Sjakob /* 2*62ac0c33Sjakob * namedb.c -- common namedb operations. 3*62ac0c33Sjakob * 4*62ac0c33Sjakob * Copyright (c) 2001-2006, NLnet Labs. All rights reserved. 5*62ac0c33Sjakob * 6*62ac0c33Sjakob * See LICENSE for the license. 7*62ac0c33Sjakob * 8*62ac0c33Sjakob */ 9*62ac0c33Sjakob 10*62ac0c33Sjakob #include <config.h> 11*62ac0c33Sjakob 12*62ac0c33Sjakob #include <sys/types.h> 13*62ac0c33Sjakob 14*62ac0c33Sjakob #include <assert.h> 15*62ac0c33Sjakob #include <ctype.h> 16*62ac0c33Sjakob #include <limits.h> 17*62ac0c33Sjakob #include <stdio.h> 18*62ac0c33Sjakob #include <string.h> 19*62ac0c33Sjakob 20*62ac0c33Sjakob #include "namedb.h" 21*62ac0c33Sjakob 22*62ac0c33Sjakob 23*62ac0c33Sjakob static domain_type * 24*62ac0c33Sjakob allocate_domain_info(domain_table_type *table, 25*62ac0c33Sjakob const dname_type *dname, 26*62ac0c33Sjakob domain_type *parent) 27*62ac0c33Sjakob { 28*62ac0c33Sjakob domain_type *result; 29*62ac0c33Sjakob 30*62ac0c33Sjakob assert(table); 31*62ac0c33Sjakob assert(dname); 32*62ac0c33Sjakob assert(parent); 33*62ac0c33Sjakob 34*62ac0c33Sjakob result = (domain_type *) region_alloc(table->region, 35*62ac0c33Sjakob sizeof(domain_type)); 36*62ac0c33Sjakob result->node.key = dname_partial_copy( 37*62ac0c33Sjakob table->region, dname, domain_dname(parent)->label_count + 1); 38*62ac0c33Sjakob result->parent = parent; 39*62ac0c33Sjakob result->wildcard_child_closest_match = result; 40*62ac0c33Sjakob result->rrsets = NULL; 41*62ac0c33Sjakob result->number = 0; 42*62ac0c33Sjakob #ifdef NSEC3 43*62ac0c33Sjakob result->nsec3_cover = NULL; 44*62ac0c33Sjakob result->nsec3_wcard_child_cover = NULL; 45*62ac0c33Sjakob result->nsec3_ds_parent_cover = NULL; 46*62ac0c33Sjakob result->nsec3_lookup = NULL; 47*62ac0c33Sjakob result->nsec3_is_exact = 0; 48*62ac0c33Sjakob result->nsec3_ds_parent_is_exact = 0; 49*62ac0c33Sjakob #endif 50*62ac0c33Sjakob result->is_existing = 0; 51*62ac0c33Sjakob result->is_apex = 0; 52*62ac0c33Sjakob 53*62ac0c33Sjakob return result; 54*62ac0c33Sjakob } 55*62ac0c33Sjakob 56*62ac0c33Sjakob domain_table_type * 57*62ac0c33Sjakob domain_table_create(region_type *region) 58*62ac0c33Sjakob { 59*62ac0c33Sjakob const dname_type *origin; 60*62ac0c33Sjakob domain_table_type *result; 61*62ac0c33Sjakob domain_type *root; 62*62ac0c33Sjakob 63*62ac0c33Sjakob assert(region); 64*62ac0c33Sjakob 65*62ac0c33Sjakob origin = dname_make(region, (uint8_t *) "", 0); 66*62ac0c33Sjakob 67*62ac0c33Sjakob root = (domain_type *) region_alloc(region, sizeof(domain_type)); 68*62ac0c33Sjakob root->node.key = origin; 69*62ac0c33Sjakob root->parent = NULL; 70*62ac0c33Sjakob root->wildcard_child_closest_match = root; 71*62ac0c33Sjakob root->rrsets = NULL; 72*62ac0c33Sjakob root->number = 1; /* 0 is used for after header */ 73*62ac0c33Sjakob root->is_existing = 0; 74*62ac0c33Sjakob root->is_apex = 0; 75*62ac0c33Sjakob #ifdef NSEC3 76*62ac0c33Sjakob root->nsec3_is_exact = 0; 77*62ac0c33Sjakob root->nsec3_ds_parent_is_exact = 0; 78*62ac0c33Sjakob root->nsec3_cover = NULL; 79*62ac0c33Sjakob root->nsec3_wcard_child_cover = NULL; 80*62ac0c33Sjakob root->nsec3_ds_parent_cover = NULL; 81*62ac0c33Sjakob root->nsec3_lookup = NULL; 82*62ac0c33Sjakob #endif 83*62ac0c33Sjakob 84*62ac0c33Sjakob result = (domain_table_type *) region_alloc(region, 85*62ac0c33Sjakob sizeof(domain_table_type)); 86*62ac0c33Sjakob result->region = region; 87*62ac0c33Sjakob result->names_to_domains = rbtree_create( 88*62ac0c33Sjakob region, (int (*)(const void *, const void *)) dname_compare); 89*62ac0c33Sjakob rbtree_insert(result->names_to_domains, (rbnode_t *) root); 90*62ac0c33Sjakob 91*62ac0c33Sjakob result->root = root; 92*62ac0c33Sjakob 93*62ac0c33Sjakob return result; 94*62ac0c33Sjakob } 95*62ac0c33Sjakob 96*62ac0c33Sjakob int 97*62ac0c33Sjakob domain_table_search(domain_table_type *table, 98*62ac0c33Sjakob const dname_type *dname, 99*62ac0c33Sjakob domain_type **closest_match, 100*62ac0c33Sjakob domain_type **closest_encloser) 101*62ac0c33Sjakob { 102*62ac0c33Sjakob int exact; 103*62ac0c33Sjakob uint8_t label_match_count; 104*62ac0c33Sjakob 105*62ac0c33Sjakob assert(table); 106*62ac0c33Sjakob assert(dname); 107*62ac0c33Sjakob assert(closest_match); 108*62ac0c33Sjakob assert(closest_encloser); 109*62ac0c33Sjakob 110*62ac0c33Sjakob exact = rbtree_find_less_equal(table->names_to_domains, dname, (rbnode_t **) closest_match); 111*62ac0c33Sjakob assert(*closest_match); 112*62ac0c33Sjakob 113*62ac0c33Sjakob *closest_encloser = *closest_match; 114*62ac0c33Sjakob 115*62ac0c33Sjakob if (!exact) { 116*62ac0c33Sjakob label_match_count = dname_label_match_count( 117*62ac0c33Sjakob domain_dname(*closest_encloser), 118*62ac0c33Sjakob dname); 119*62ac0c33Sjakob assert(label_match_count < dname->label_count); 120*62ac0c33Sjakob while (label_match_count < domain_dname(*closest_encloser)->label_count) { 121*62ac0c33Sjakob (*closest_encloser) = (*closest_encloser)->parent; 122*62ac0c33Sjakob assert(*closest_encloser); 123*62ac0c33Sjakob } 124*62ac0c33Sjakob } 125*62ac0c33Sjakob 126*62ac0c33Sjakob return exact; 127*62ac0c33Sjakob } 128*62ac0c33Sjakob 129*62ac0c33Sjakob domain_type * 130*62ac0c33Sjakob domain_table_find(domain_table_type *table, 131*62ac0c33Sjakob const dname_type *dname) 132*62ac0c33Sjakob { 133*62ac0c33Sjakob domain_type *closest_match; 134*62ac0c33Sjakob domain_type *closest_encloser; 135*62ac0c33Sjakob int exact; 136*62ac0c33Sjakob 137*62ac0c33Sjakob exact = domain_table_search( 138*62ac0c33Sjakob table, dname, &closest_match, &closest_encloser); 139*62ac0c33Sjakob return exact ? closest_encloser : NULL; 140*62ac0c33Sjakob } 141*62ac0c33Sjakob 142*62ac0c33Sjakob 143*62ac0c33Sjakob domain_type * 144*62ac0c33Sjakob domain_table_insert(domain_table_type *table, 145*62ac0c33Sjakob const dname_type *dname) 146*62ac0c33Sjakob { 147*62ac0c33Sjakob domain_type *closest_match; 148*62ac0c33Sjakob domain_type *closest_encloser; 149*62ac0c33Sjakob domain_type *result; 150*62ac0c33Sjakob int exact; 151*62ac0c33Sjakob 152*62ac0c33Sjakob assert(table); 153*62ac0c33Sjakob assert(dname); 154*62ac0c33Sjakob 155*62ac0c33Sjakob exact = domain_table_search( 156*62ac0c33Sjakob table, dname, &closest_match, &closest_encloser); 157*62ac0c33Sjakob if (exact) { 158*62ac0c33Sjakob result = closest_encloser; 159*62ac0c33Sjakob } else { 160*62ac0c33Sjakob assert(domain_dname(closest_encloser)->label_count < dname->label_count); 161*62ac0c33Sjakob 162*62ac0c33Sjakob /* Insert new node(s). */ 163*62ac0c33Sjakob do { 164*62ac0c33Sjakob result = allocate_domain_info(table, 165*62ac0c33Sjakob dname, 166*62ac0c33Sjakob closest_encloser); 167*62ac0c33Sjakob rbtree_insert(table->names_to_domains, (rbnode_t *) result); 168*62ac0c33Sjakob result->number = table->names_to_domains->count; 169*62ac0c33Sjakob 170*62ac0c33Sjakob /* 171*62ac0c33Sjakob * If the newly added domain name is larger 172*62ac0c33Sjakob * than the parent's current 173*62ac0c33Sjakob * wildcard_child_closest_match but smaller or 174*62ac0c33Sjakob * equal to the wildcard domain name, update 175*62ac0c33Sjakob * the parent's wildcard_child_closest_match 176*62ac0c33Sjakob * field. 177*62ac0c33Sjakob */ 178*62ac0c33Sjakob if (label_compare(dname_name(domain_dname(result)), 179*62ac0c33Sjakob (const uint8_t *) "\001*") <= 0 180*62ac0c33Sjakob && dname_compare(domain_dname(result), 181*62ac0c33Sjakob domain_dname(closest_encloser->wildcard_child_closest_match)) > 0) 182*62ac0c33Sjakob { 183*62ac0c33Sjakob closest_encloser->wildcard_child_closest_match 184*62ac0c33Sjakob = result; 185*62ac0c33Sjakob } 186*62ac0c33Sjakob closest_encloser = result; 187*62ac0c33Sjakob } while (domain_dname(closest_encloser)->label_count < dname->label_count); 188*62ac0c33Sjakob } 189*62ac0c33Sjakob 190*62ac0c33Sjakob return result; 191*62ac0c33Sjakob } 192*62ac0c33Sjakob 193*62ac0c33Sjakob int 194*62ac0c33Sjakob domain_table_iterate(domain_table_type *table, 195*62ac0c33Sjakob domain_table_iterator_type iterator, 196*62ac0c33Sjakob void *user_data) 197*62ac0c33Sjakob { 198*62ac0c33Sjakob const void *dname; 199*62ac0c33Sjakob void *node; 200*62ac0c33Sjakob int error = 0; 201*62ac0c33Sjakob 202*62ac0c33Sjakob assert(table); 203*62ac0c33Sjakob 204*62ac0c33Sjakob RBTREE_WALK(table->names_to_domains, dname, node) { 205*62ac0c33Sjakob error += iterator((domain_type *) node, user_data); 206*62ac0c33Sjakob } 207*62ac0c33Sjakob 208*62ac0c33Sjakob return error; 209*62ac0c33Sjakob } 210*62ac0c33Sjakob 211*62ac0c33Sjakob 212*62ac0c33Sjakob void 213*62ac0c33Sjakob domain_add_rrset(domain_type *domain, rrset_type *rrset) 214*62ac0c33Sjakob { 215*62ac0c33Sjakob #if 0 /* fast */ 216*62ac0c33Sjakob rrset->next = domain->rrsets; 217*62ac0c33Sjakob domain->rrsets = rrset; 218*62ac0c33Sjakob #else 219*62ac0c33Sjakob /* preserve ordering, add at end */ 220*62ac0c33Sjakob rrset_type** p = &domain->rrsets; 221*62ac0c33Sjakob while(*p) 222*62ac0c33Sjakob p = &((*p)->next); 223*62ac0c33Sjakob *p = rrset; 224*62ac0c33Sjakob rrset->next = 0; 225*62ac0c33Sjakob #endif 226*62ac0c33Sjakob 227*62ac0c33Sjakob while (domain && !domain->is_existing) { 228*62ac0c33Sjakob domain->is_existing = 1; 229*62ac0c33Sjakob domain = domain->parent; 230*62ac0c33Sjakob } 231*62ac0c33Sjakob } 232*62ac0c33Sjakob 233*62ac0c33Sjakob 234*62ac0c33Sjakob rrset_type * 235*62ac0c33Sjakob domain_find_rrset(domain_type *domain, zone_type *zone, uint16_t type) 236*62ac0c33Sjakob { 237*62ac0c33Sjakob rrset_type *result = domain->rrsets; 238*62ac0c33Sjakob 239*62ac0c33Sjakob while (result) { 240*62ac0c33Sjakob if (result->zone == zone && rrset_rrtype(result) == type) { 241*62ac0c33Sjakob return result; 242*62ac0c33Sjakob } 243*62ac0c33Sjakob result = result->next; 244*62ac0c33Sjakob } 245*62ac0c33Sjakob return NULL; 246*62ac0c33Sjakob } 247*62ac0c33Sjakob 248*62ac0c33Sjakob rrset_type * 249*62ac0c33Sjakob domain_find_any_rrset(domain_type *domain, zone_type *zone) 250*62ac0c33Sjakob { 251*62ac0c33Sjakob rrset_type *result = domain->rrsets; 252*62ac0c33Sjakob 253*62ac0c33Sjakob while (result) { 254*62ac0c33Sjakob if (result->zone == zone) { 255*62ac0c33Sjakob return result; 256*62ac0c33Sjakob } 257*62ac0c33Sjakob result = result->next; 258*62ac0c33Sjakob } 259*62ac0c33Sjakob return NULL; 260*62ac0c33Sjakob } 261*62ac0c33Sjakob 262*62ac0c33Sjakob zone_type * 263*62ac0c33Sjakob domain_find_zone(domain_type *domain) 264*62ac0c33Sjakob { 265*62ac0c33Sjakob rrset_type *rrset; 266*62ac0c33Sjakob while (domain) { 267*62ac0c33Sjakob for (rrset = domain->rrsets; rrset; rrset = rrset->next) { 268*62ac0c33Sjakob if (rrset_rrtype(rrset) == TYPE_SOA) { 269*62ac0c33Sjakob return rrset->zone; 270*62ac0c33Sjakob } 271*62ac0c33Sjakob } 272*62ac0c33Sjakob domain = domain->parent; 273*62ac0c33Sjakob } 274*62ac0c33Sjakob return NULL; 275*62ac0c33Sjakob } 276*62ac0c33Sjakob 277*62ac0c33Sjakob zone_type * 278*62ac0c33Sjakob domain_find_parent_zone(zone_type *zone) 279*62ac0c33Sjakob { 280*62ac0c33Sjakob rrset_type *rrset; 281*62ac0c33Sjakob 282*62ac0c33Sjakob assert(zone); 283*62ac0c33Sjakob 284*62ac0c33Sjakob for (rrset = zone->apex->rrsets; rrset; rrset = rrset->next) { 285*62ac0c33Sjakob if (rrset->zone != zone && rrset_rrtype(rrset) == TYPE_NS) { 286*62ac0c33Sjakob return rrset->zone; 287*62ac0c33Sjakob } 288*62ac0c33Sjakob } 289*62ac0c33Sjakob return NULL; 290*62ac0c33Sjakob } 291*62ac0c33Sjakob 292*62ac0c33Sjakob domain_type * 293*62ac0c33Sjakob domain_find_ns_rrsets(domain_type *domain, zone_type *zone, rrset_type **ns) 294*62ac0c33Sjakob { 295*62ac0c33Sjakob while (domain && domain != zone->apex) { 296*62ac0c33Sjakob *ns = domain_find_rrset(domain, zone, TYPE_NS); 297*62ac0c33Sjakob if (*ns) 298*62ac0c33Sjakob return domain; 299*62ac0c33Sjakob domain = domain->parent; 300*62ac0c33Sjakob } 301*62ac0c33Sjakob 302*62ac0c33Sjakob *ns = NULL; 303*62ac0c33Sjakob return NULL; 304*62ac0c33Sjakob } 305*62ac0c33Sjakob 306*62ac0c33Sjakob int 307*62ac0c33Sjakob domain_is_glue(domain_type *domain, zone_type *zone) 308*62ac0c33Sjakob { 309*62ac0c33Sjakob rrset_type *unused; 310*62ac0c33Sjakob domain_type *ns_domain = domain_find_ns_rrsets(domain, zone, &unused); 311*62ac0c33Sjakob return (ns_domain != NULL && 312*62ac0c33Sjakob domain_find_rrset(ns_domain, zone, TYPE_SOA) == NULL); 313*62ac0c33Sjakob } 314*62ac0c33Sjakob 315*62ac0c33Sjakob domain_type * 316*62ac0c33Sjakob domain_wildcard_child(domain_type *domain) 317*62ac0c33Sjakob { 318*62ac0c33Sjakob domain_type *wildcard_child; 319*62ac0c33Sjakob 320*62ac0c33Sjakob assert(domain); 321*62ac0c33Sjakob assert(domain->wildcard_child_closest_match); 322*62ac0c33Sjakob 323*62ac0c33Sjakob wildcard_child = domain->wildcard_child_closest_match; 324*62ac0c33Sjakob if (wildcard_child != domain 325*62ac0c33Sjakob && label_is_wildcard(dname_name(domain_dname(wildcard_child)))) 326*62ac0c33Sjakob { 327*62ac0c33Sjakob return wildcard_child; 328*62ac0c33Sjakob } else { 329*62ac0c33Sjakob return NULL; 330*62ac0c33Sjakob } 331*62ac0c33Sjakob } 332*62ac0c33Sjakob 333*62ac0c33Sjakob int 334*62ac0c33Sjakob zone_is_secure(zone_type *zone) 335*62ac0c33Sjakob { 336*62ac0c33Sjakob assert(zone); 337*62ac0c33Sjakob return zone->is_secure; 338*62ac0c33Sjakob } 339*62ac0c33Sjakob 340*62ac0c33Sjakob uint16_t 341*62ac0c33Sjakob rr_rrsig_type_covered(rr_type *rr) 342*62ac0c33Sjakob { 343*62ac0c33Sjakob assert(rr->type == TYPE_RRSIG); 344*62ac0c33Sjakob assert(rr->rdata_count > 0); 345*62ac0c33Sjakob assert(rdata_atom_size(rr->rdatas[0]) == sizeof(uint16_t)); 346*62ac0c33Sjakob 347*62ac0c33Sjakob return ntohs(* (uint16_t *) rdata_atom_data(rr->rdatas[0])); 348*62ac0c33Sjakob } 349*62ac0c33Sjakob 350*62ac0c33Sjakob zone_type * 351*62ac0c33Sjakob namedb_find_zone(namedb_type *db, domain_type *domain) 352*62ac0c33Sjakob { 353*62ac0c33Sjakob zone_type *zone; 354*62ac0c33Sjakob 355*62ac0c33Sjakob for (zone = db->zones; zone; zone = zone->next) { 356*62ac0c33Sjakob if (zone->apex == domain) 357*62ac0c33Sjakob break; 358*62ac0c33Sjakob } 359*62ac0c33Sjakob 360*62ac0c33Sjakob return zone; 361*62ac0c33Sjakob } 362*62ac0c33Sjakob 363*62ac0c33Sjakob rrset_type * 364*62ac0c33Sjakob domain_find_non_cname_rrset(domain_type *domain, zone_type *zone) 365*62ac0c33Sjakob { 366*62ac0c33Sjakob /* find any rrset type that is not allowed next to a CNAME */ 367*62ac0c33Sjakob /* nothing is allowed next to a CNAME, except RRSIG, NSEC, NSEC3 */ 368*62ac0c33Sjakob rrset_type *result = domain->rrsets; 369*62ac0c33Sjakob 370*62ac0c33Sjakob while (result) { 371*62ac0c33Sjakob if (result->zone == zone && /* here is the list of exceptions*/ 372*62ac0c33Sjakob rrset_rrtype(result) != TYPE_CNAME && 373*62ac0c33Sjakob rrset_rrtype(result) != TYPE_RRSIG && 374*62ac0c33Sjakob rrset_rrtype(result) != TYPE_NXT && 375*62ac0c33Sjakob rrset_rrtype(result) != TYPE_SIG && 376*62ac0c33Sjakob rrset_rrtype(result) != TYPE_NSEC && 377*62ac0c33Sjakob rrset_rrtype(result) != TYPE_NSEC3 ) { 378*62ac0c33Sjakob return result; 379*62ac0c33Sjakob } 380*62ac0c33Sjakob result = result->next; 381*62ac0c33Sjakob } 382*62ac0c33Sjakob return NULL; 383*62ac0c33Sjakob } 384