1 /* 2 * special zone file structures and functions for better dnssec handling 3 */ 4 5 #include <ldns/config.h> 6 7 #include <ldns/ldns.h> 8 9 ldns_dnssec_rrs * 10 ldns_dnssec_rrs_new() 11 { 12 ldns_dnssec_rrs *new_rrs; 13 new_rrs = LDNS_MALLOC(ldns_dnssec_rrs); 14 if(!new_rrs) return NULL; 15 new_rrs->rr = NULL; 16 new_rrs->next = NULL; 17 return new_rrs; 18 } 19 20 INLINE void 21 ldns_dnssec_rrs_free_internal(ldns_dnssec_rrs *rrs, int deep) 22 { 23 ldns_dnssec_rrs *next; 24 while (rrs) { 25 next = rrs->next; 26 if (deep) { 27 ldns_rr_free(rrs->rr); 28 } 29 LDNS_FREE(rrs); 30 rrs = next; 31 } 32 } 33 34 void 35 ldns_dnssec_rrs_free(ldns_dnssec_rrs *rrs) 36 { 37 ldns_dnssec_rrs_free_internal(rrs, 0); 38 } 39 40 void 41 ldns_dnssec_rrs_deep_free(ldns_dnssec_rrs *rrs) 42 { 43 ldns_dnssec_rrs_free_internal(rrs, 1); 44 } 45 46 ldns_status 47 ldns_dnssec_rrs_add_rr(ldns_dnssec_rrs *rrs, ldns_rr *rr) 48 { 49 int cmp; 50 ldns_dnssec_rrs *new_rrs; 51 if (!rrs || !rr) { 52 return LDNS_STATUS_ERR; 53 } 54 55 /* this could be done more efficiently; name and type should already 56 be equal */ 57 cmp = ldns_rr_compare(rrs->rr, 58 rr); 59 /* should we error on equal? */ 60 if (cmp <= 0) { 61 if (rrs->next) { 62 return ldns_dnssec_rrs_add_rr(rrs->next, rr); 63 } else { 64 new_rrs = ldns_dnssec_rrs_new(); 65 new_rrs->rr = rr; 66 rrs->next = new_rrs; 67 } 68 } else if (cmp > 0) { 69 /* put the current old rr in the new next, put the new 70 rr in the current container */ 71 new_rrs = ldns_dnssec_rrs_new(); 72 new_rrs->rr = rrs->rr; 73 new_rrs->next = rrs->next; 74 rrs->rr = rr; 75 rrs->next = new_rrs; 76 } 77 return LDNS_STATUS_OK; 78 } 79 80 void 81 ldns_dnssec_rrs_print(FILE *out, ldns_dnssec_rrs *rrs) 82 { 83 if (!rrs) { 84 fprintf(out, "<void>"); 85 } else { 86 if (rrs->rr) { 87 ldns_rr_print(out, rrs->rr); 88 } 89 if (rrs->next) { 90 ldns_dnssec_rrs_print(out, rrs->next); 91 } 92 } 93 } 94 95 ldns_dnssec_rrsets * 96 ldns_dnssec_rrsets_new() 97 { 98 ldns_dnssec_rrsets *new_rrsets; 99 new_rrsets = LDNS_MALLOC(ldns_dnssec_rrsets); 100 if(!new_rrsets) return NULL; 101 new_rrsets->rrs = NULL; 102 new_rrsets->type = 0; 103 new_rrsets->signatures = NULL; 104 new_rrsets->next = NULL; 105 return new_rrsets; 106 } 107 108 INLINE void 109 ldns_dnssec_rrsets_free_internal(ldns_dnssec_rrsets *rrsets, int deep) 110 { 111 if (rrsets) { 112 if (rrsets->rrs) { 113 ldns_dnssec_rrs_free_internal(rrsets->rrs, deep); 114 } 115 if (rrsets->next) { 116 ldns_dnssec_rrsets_free_internal(rrsets->next, deep); 117 } 118 if (rrsets->signatures) { 119 ldns_dnssec_rrs_free_internal(rrsets->signatures, deep); 120 } 121 LDNS_FREE(rrsets); 122 } 123 } 124 125 void 126 ldns_dnssec_rrsets_free(ldns_dnssec_rrsets *rrsets) 127 { 128 ldns_dnssec_rrsets_free_internal(rrsets, 0); 129 } 130 131 void 132 ldns_dnssec_rrsets_deep_free(ldns_dnssec_rrsets *rrsets) 133 { 134 ldns_dnssec_rrsets_free_internal(rrsets, 1); 135 } 136 137 ldns_rr_type 138 ldns_dnssec_rrsets_type(ldns_dnssec_rrsets *rrsets) 139 { 140 if (rrsets) { 141 return rrsets->type; 142 } else { 143 return 0; 144 } 145 } 146 147 ldns_status 148 ldns_dnssec_rrsets_set_type(ldns_dnssec_rrsets *rrsets, 149 ldns_rr_type type) 150 { 151 if (rrsets) { 152 rrsets->type = type; 153 return LDNS_STATUS_OK; 154 } 155 return LDNS_STATUS_ERR; 156 } 157 158 ldns_dnssec_rrsets * 159 ldns_dnssec_rrsets_new_frm_rr(ldns_rr *rr) 160 { 161 ldns_dnssec_rrsets *new_rrsets; 162 ldns_rr_type rr_type; 163 bool rrsig; 164 165 new_rrsets = ldns_dnssec_rrsets_new(); 166 rr_type = ldns_rr_get_type(rr); 167 if (rr_type == LDNS_RR_TYPE_RRSIG) { 168 rrsig = true; 169 rr_type = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr)); 170 } else { 171 rrsig = false; 172 } 173 if (!rrsig) { 174 new_rrsets->rrs = ldns_dnssec_rrs_new(); 175 new_rrsets->rrs->rr = rr; 176 } else { 177 new_rrsets->signatures = ldns_dnssec_rrs_new(); 178 new_rrsets->signatures->rr = rr; 179 } 180 new_rrsets->type = rr_type; 181 return new_rrsets; 182 } 183 184 ldns_status 185 ldns_dnssec_rrsets_add_rr(ldns_dnssec_rrsets *rrsets, ldns_rr *rr) 186 { 187 ldns_dnssec_rrsets *new_rrsets; 188 ldns_rr_type rr_type; 189 bool rrsig = false; 190 ldns_status result = LDNS_STATUS_OK; 191 192 if (!rrsets || !rr) { 193 return LDNS_STATUS_ERR; 194 } 195 196 rr_type = ldns_rr_get_type(rr); 197 198 if (rr_type == LDNS_RR_TYPE_RRSIG) { 199 rrsig = true; 200 rr_type = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr)); 201 } 202 203 if (!rrsets->rrs && rrsets->type == 0 && !rrsets->signatures) { 204 if (!rrsig) { 205 rrsets->rrs = ldns_dnssec_rrs_new(); 206 rrsets->rrs->rr = rr; 207 rrsets->type = rr_type; 208 } else { 209 rrsets->signatures = ldns_dnssec_rrs_new(); 210 rrsets->signatures->rr = rr; 211 rrsets->type = rr_type; 212 } 213 return LDNS_STATUS_OK; 214 } 215 216 if (rr_type > ldns_dnssec_rrsets_type(rrsets)) { 217 if (rrsets->next) { 218 result = ldns_dnssec_rrsets_add_rr(rrsets->next, rr); 219 } else { 220 new_rrsets = ldns_dnssec_rrsets_new_frm_rr(rr); 221 rrsets->next = new_rrsets; 222 } 223 } else if (rr_type < ldns_dnssec_rrsets_type(rrsets)) { 224 /* move the current one into the new next, 225 replace field of current with data from new rr */ 226 new_rrsets = ldns_dnssec_rrsets_new(); 227 new_rrsets->rrs = rrsets->rrs; 228 new_rrsets->type = rrsets->type; 229 new_rrsets->signatures = rrsets->signatures; 230 new_rrsets->next = rrsets->next; 231 if (!rrsig) { 232 rrsets->rrs = ldns_dnssec_rrs_new(); 233 rrsets->rrs->rr = rr; 234 rrsets->signatures = NULL; 235 } else { 236 rrsets->rrs = NULL; 237 rrsets->signatures = ldns_dnssec_rrs_new(); 238 rrsets->signatures->rr = rr; 239 } 240 rrsets->type = rr_type; 241 rrsets->next = new_rrsets; 242 } else { 243 /* equal, add to current rrsets */ 244 if (rrsig) { 245 if (rrsets->signatures) { 246 result = ldns_dnssec_rrs_add_rr(rrsets->signatures, rr); 247 } else { 248 rrsets->signatures = ldns_dnssec_rrs_new(); 249 rrsets->signatures->rr = rr; 250 } 251 } else { 252 if (rrsets->rrs) { 253 result = ldns_dnssec_rrs_add_rr(rrsets->rrs, rr); 254 } else { 255 rrsets->rrs = ldns_dnssec_rrs_new(); 256 rrsets->rrs->rr = rr; 257 } 258 } 259 } 260 261 return result; 262 } 263 264 void 265 ldns_dnssec_rrsets_print_soa(FILE *out, 266 ldns_dnssec_rrsets *rrsets, 267 bool follow, 268 bool show_soa) 269 { 270 if (!rrsets) { 271 fprintf(out, "<void>\n"); 272 } else { 273 if (rrsets->rrs && 274 (show_soa || 275 ldns_rr_get_type(rrsets->rrs->rr) != LDNS_RR_TYPE_SOA 276 ) 277 ) { 278 ldns_dnssec_rrs_print(out, rrsets->rrs); 279 if (rrsets->signatures) { 280 ldns_dnssec_rrs_print(out, rrsets->signatures); 281 } 282 } 283 if (follow && rrsets->next) { 284 ldns_dnssec_rrsets_print_soa(out, rrsets->next, follow, show_soa); 285 } 286 } 287 } 288 289 void 290 ldns_dnssec_rrsets_print(FILE *out, ldns_dnssec_rrsets *rrsets, bool follow) 291 { 292 ldns_dnssec_rrsets_print_soa(out, rrsets, follow, true); 293 } 294 295 ldns_dnssec_name * 296 ldns_dnssec_name_new() 297 { 298 ldns_dnssec_name *new_name; 299 300 new_name = LDNS_MALLOC(ldns_dnssec_name); 301 if (!new_name) { 302 return NULL; 303 } 304 305 new_name->name = NULL; 306 new_name->rrsets = NULL; 307 new_name->name_alloced = false; 308 new_name->nsec = NULL; 309 new_name->nsec_signatures = NULL; 310 311 new_name->is_glue = false; 312 new_name->hashed_name = NULL; 313 314 return new_name; 315 } 316 317 ldns_dnssec_name * 318 ldns_dnssec_name_new_frm_rr(ldns_rr *rr) 319 { 320 ldns_dnssec_name *new_name = ldns_dnssec_name_new(); 321 322 new_name->name = ldns_rr_owner(rr); 323 if(ldns_dnssec_name_add_rr(new_name, rr) != LDNS_STATUS_OK) { 324 ldns_dnssec_name_free(new_name); 325 return NULL; 326 } 327 328 return new_name; 329 } 330 331 INLINE void 332 ldns_dnssec_name_free_internal(ldns_dnssec_name *name, 333 int deep) 334 { 335 if (name) { 336 if (name->name_alloced) { 337 ldns_rdf_deep_free(name->name); 338 } 339 if (name->rrsets) { 340 ldns_dnssec_rrsets_free_internal(name->rrsets, deep); 341 } 342 if (name->nsec && deep) { 343 ldns_rr_free(name->nsec); 344 } 345 if (name->nsec_signatures) { 346 ldns_dnssec_rrs_free_internal(name->nsec_signatures, deep); 347 } 348 if (name->hashed_name) { 349 if (deep) { 350 ldns_rdf_deep_free(name->hashed_name); 351 } 352 } 353 LDNS_FREE(name); 354 } 355 } 356 357 void 358 ldns_dnssec_name_free(ldns_dnssec_name *name) 359 { 360 ldns_dnssec_name_free_internal(name, 0); 361 } 362 363 void 364 ldns_dnssec_name_deep_free(ldns_dnssec_name *name) 365 { 366 ldns_dnssec_name_free_internal(name, 1); 367 } 368 369 ldns_rdf * 370 ldns_dnssec_name_name(ldns_dnssec_name *name) 371 { 372 if (name) { 373 return name->name; 374 } 375 return NULL; 376 } 377 378 void 379 ldns_dnssec_name_set_name(ldns_dnssec_name *rrset, 380 ldns_rdf *dname) 381 { 382 if (rrset && dname) { 383 rrset->name = dname; 384 } 385 } 386 387 ldns_rr * 388 ldns_dnssec_name_nsec(ldns_dnssec_name *rrset) 389 { 390 if (rrset) { 391 return rrset->nsec; 392 } 393 return NULL; 394 } 395 396 void 397 ldns_dnssec_name_set_nsec(ldns_dnssec_name *rrset, ldns_rr *nsec) 398 { 399 if (rrset && nsec) { 400 rrset->nsec = nsec; 401 } 402 } 403 404 int 405 ldns_dnssec_name_cmp(const void *a, const void *b) 406 { 407 ldns_dnssec_name *na = (ldns_dnssec_name *) a; 408 ldns_dnssec_name *nb = (ldns_dnssec_name *) b; 409 410 if (na && nb) { 411 return ldns_dname_compare(ldns_dnssec_name_name(na), 412 ldns_dnssec_name_name(nb)); 413 } else if (na) { 414 return 1; 415 } else if (nb) { 416 return -1; 417 } else { 418 return 0; 419 } 420 } 421 422 ldns_status 423 ldns_dnssec_name_add_rr(ldns_dnssec_name *name, 424 ldns_rr *rr) 425 { 426 ldns_status result = LDNS_STATUS_OK; 427 ldns_rdf *name_name; 428 bool hashed_name = false; 429 ldns_rr_type rr_type; 430 ldns_rr_type typecovered = 0; 431 432 /* special handling for NSEC3 and NSECX covering RRSIGS */ 433 434 if (!name || !rr) { 435 return LDNS_STATUS_ERR; 436 } 437 438 rr_type = ldns_rr_get_type(rr); 439 440 if (rr_type == LDNS_RR_TYPE_RRSIG) { 441 typecovered = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr)); 442 } 443 444 #ifdef HAVE_SSL 445 if (rr_type == LDNS_RR_TYPE_NSEC3 || 446 typecovered == LDNS_RR_TYPE_NSEC3) { 447 name_name = ldns_nsec3_hash_name_frm_nsec3(rr, 448 ldns_dnssec_name_name(name)); 449 hashed_name = true; 450 } else { 451 name_name = ldns_dnssec_name_name(name); 452 } 453 #else 454 name_name = ldns_dnssec_name_name(name); 455 #endif /* HAVE_SSL */ 456 457 if (rr_type == LDNS_RR_TYPE_NSEC || 458 rr_type == LDNS_RR_TYPE_NSEC3) { 459 /* XX check if is already set (and error?) */ 460 name->nsec = rr; 461 } else if (typecovered == LDNS_RR_TYPE_NSEC || 462 typecovered == LDNS_RR_TYPE_NSEC3) { 463 if (name->nsec_signatures) { 464 result = ldns_dnssec_rrs_add_rr(name->nsec_signatures, rr); 465 } else { 466 name->nsec_signatures = ldns_dnssec_rrs_new(); 467 name->nsec_signatures->rr = rr; 468 } 469 } else { 470 /* it's a 'normal' RR, add it to the right rrset */ 471 if (name->rrsets) { 472 result = ldns_dnssec_rrsets_add_rr(name->rrsets, rr); 473 } else { 474 name->rrsets = ldns_dnssec_rrsets_new(); 475 result = ldns_dnssec_rrsets_add_rr(name->rrsets, rr); 476 } 477 } 478 479 if (hashed_name) { 480 ldns_rdf_deep_free(name_name); 481 } 482 483 return result; 484 } 485 486 ldns_dnssec_rrsets * 487 ldns_dnssec_name_find_rrset(ldns_dnssec_name *name, 488 ldns_rr_type type) { 489 ldns_dnssec_rrsets *result; 490 491 result = name->rrsets; 492 while (result) { 493 if (result->type == type) { 494 return result; 495 } else { 496 result = result->next; 497 } 498 } 499 return NULL; 500 } 501 502 ldns_dnssec_rrsets * 503 ldns_dnssec_zone_find_rrset(ldns_dnssec_zone *zone, 504 ldns_rdf *dname, 505 ldns_rr_type type) 506 { 507 ldns_rbnode_t *node; 508 509 if (!zone || !dname) { 510 return NULL; 511 } 512 513 node = ldns_rbtree_search(zone->names, dname); 514 if (node) { 515 return ldns_dnssec_name_find_rrset((ldns_dnssec_name *)node->data, 516 type); 517 } else { 518 return NULL; 519 } 520 } 521 522 void 523 ldns_dnssec_name_print_soa(FILE *out, ldns_dnssec_name *name, bool show_soa) 524 { 525 if (name) { 526 if(name->rrsets) { 527 ldns_dnssec_rrsets_print_soa(out, name->rrsets, true, show_soa); 528 } else { 529 fprintf(out, ";; Empty nonterminal: "); 530 ldns_rdf_print(out, name->name); 531 fprintf(out, "\n"); 532 } 533 if(name->nsec) { 534 ldns_rr_print(out, name->nsec); 535 } 536 if (name->nsec_signatures) { 537 ldns_dnssec_rrs_print(out, name->nsec_signatures); 538 } 539 } else { 540 fprintf(out, "<void>\n"); 541 } 542 } 543 544 void 545 ldns_dnssec_name_print(FILE *out, ldns_dnssec_name *name) 546 { 547 ldns_dnssec_name_print_soa(out, name, true); 548 } 549 550 ldns_dnssec_zone * 551 ldns_dnssec_zone_new() 552 { 553 ldns_dnssec_zone *zone = LDNS_MALLOC(ldns_dnssec_zone); 554 if(!zone) return NULL; 555 zone->soa = NULL; 556 zone->names = NULL; 557 558 return zone; 559 } 560 561 void 562 ldns_dnssec_name_node_free(ldns_rbnode_t *node, void *arg) { 563 (void) arg; 564 ldns_dnssec_name_free((ldns_dnssec_name *)node->data); 565 free(node); 566 } 567 568 void 569 ldns_dnssec_name_node_deep_free(ldns_rbnode_t *node, void *arg) { 570 (void) arg; 571 ldns_dnssec_name_deep_free((ldns_dnssec_name *)node->data); 572 free(node); 573 } 574 575 void 576 ldns_dnssec_zone_free(ldns_dnssec_zone *zone) 577 { 578 if (zone) { 579 if (zone->names) { 580 /* destroy all name structures within the tree */ 581 ldns_traverse_postorder(zone->names, 582 ldns_dnssec_name_node_free, 583 NULL); 584 free(zone->names); 585 } 586 LDNS_FREE(zone); 587 } 588 } 589 590 void 591 ldns_dnssec_zone_deep_free(ldns_dnssec_zone *zone) 592 { 593 if (zone) { 594 if (zone->names) { 595 /* destroy all name structures within the tree */ 596 ldns_traverse_postorder(zone->names, 597 ldns_dnssec_name_node_deep_free, 598 NULL); 599 free(zone->names); 600 } 601 LDNS_FREE(zone); 602 } 603 } 604 605 /* use for dname comparison in tree */ 606 int 607 ldns_dname_compare_v(const void *a, const void *b) { 608 return ldns_dname_compare((ldns_rdf *)a, (ldns_rdf *)b); 609 } 610 611 #ifdef HAVE_SSL 612 ldns_rbnode_t * 613 ldns_dnssec_zone_find_nsec3_original(ldns_dnssec_zone *zone, 614 ldns_rr *rr) { 615 ldns_rbnode_t *current_node = ldns_rbtree_first(zone->names); 616 ldns_dnssec_name *current_name; 617 ldns_rdf *hashed_name; 618 619 hashed_name = ldns_dname_label(ldns_rr_owner(rr), 0); 620 621 while (current_node != LDNS_RBTREE_NULL) { 622 current_name = (ldns_dnssec_name *) current_node->data; 623 if (!current_name->hashed_name) { 624 current_name->hashed_name = 625 ldns_nsec3_hash_name_frm_nsec3(rr, current_name->name); 626 } 627 if (ldns_dname_compare(hashed_name, 628 current_name->hashed_name) 629 == 0) { 630 ldns_rdf_deep_free(hashed_name); 631 return current_node; 632 } 633 current_node = ldns_rbtree_next(current_node); 634 } 635 ldns_rdf_deep_free(hashed_name); 636 return NULL; 637 } 638 639 ldns_status 640 ldns_dnssec_zone_add_rr(ldns_dnssec_zone *zone, ldns_rr *rr) 641 { 642 ldns_status result = LDNS_STATUS_OK; 643 ldns_dnssec_name *cur_name; 644 ldns_rbnode_t *cur_node; 645 ldns_rr_type type_covered = 0; 646 647 if (!zone || !rr) { 648 return LDNS_STATUS_ERR; 649 } 650 651 if (!zone->names) { 652 zone->names = ldns_rbtree_create(ldns_dname_compare_v); 653 if(!zone->names) return LDNS_STATUS_MEM_ERR; 654 } 655 656 /* we need the original of the hashed name if this is 657 an NSEC3, or an RRSIG that covers an NSEC3 */ 658 if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_RRSIG) { 659 type_covered = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr)); 660 } 661 if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_NSEC3 || 662 type_covered == LDNS_RR_TYPE_NSEC3) { 663 cur_node = ldns_dnssec_zone_find_nsec3_original(zone, 664 rr); 665 if (!cur_node) { 666 return LDNS_STATUS_DNSSEC_NSEC3_ORIGINAL_NOT_FOUND; 667 } 668 } else { 669 cur_node = ldns_rbtree_search(zone->names, ldns_rr_owner(rr)); 670 } 671 672 if (!cur_node) { 673 /* add */ 674 cur_name = ldns_dnssec_name_new_frm_rr(rr); 675 if(!cur_name) return LDNS_STATUS_MEM_ERR; 676 cur_node = LDNS_MALLOC(ldns_rbnode_t); 677 if(!cur_node) { 678 ldns_dnssec_name_free(cur_name); 679 return LDNS_STATUS_MEM_ERR; 680 } 681 cur_node->key = ldns_rr_owner(rr); 682 cur_node->data = cur_name; 683 (void)ldns_rbtree_insert(zone->names, cur_node); 684 } else { 685 cur_name = (ldns_dnssec_name *) cur_node->data; 686 result = ldns_dnssec_name_add_rr(cur_name, rr); 687 } 688 689 if (result != LDNS_STATUS_OK) { 690 fprintf(stderr, "error adding rr: "); 691 ldns_rr_print(stderr, rr); 692 } 693 694 /*TODO ldns_dnssec_name_print_names(stdout, zone->names, 0);*/ 695 if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_SOA) { 696 zone->soa = cur_name; 697 } 698 699 return result; 700 } 701 #endif /* HAVE_SSL */ 702 703 void 704 ldns_dnssec_zone_names_print(FILE *out, ldns_rbtree_t *tree, bool print_soa) 705 { 706 ldns_rbnode_t *node; 707 ldns_dnssec_name *name; 708 709 node = ldns_rbtree_first(tree); 710 while (node != LDNS_RBTREE_NULL) { 711 name = (ldns_dnssec_name *) node->data; 712 ldns_dnssec_name_print_soa(out, name, print_soa); 713 fprintf(out, ";\n"); 714 node = ldns_rbtree_next(node); 715 } 716 } 717 718 void 719 ldns_dnssec_zone_print(FILE *out, ldns_dnssec_zone *zone) 720 { 721 if (zone) { 722 if (zone->soa) { 723 fprintf(out, ";; Zone: "); 724 ldns_rdf_print(out, ldns_dnssec_name_name(zone->soa)); 725 fprintf(out, "\n;\n"); 726 ldns_dnssec_rrsets_print( 727 out, 728 ldns_dnssec_name_find_rrset(zone->soa, 729 LDNS_RR_TYPE_SOA), 730 false); 731 fprintf(out, ";\n"); 732 } 733 734 if (zone->names) { 735 ldns_dnssec_zone_names_print(out, zone->names, false); 736 } 737 } 738 } 739 740 ldns_status 741 ldns_dnssec_zone_add_empty_nonterminals(ldns_dnssec_zone *zone) 742 { 743 ldns_dnssec_name *new_name; 744 ldns_rdf *cur_name; 745 ldns_rdf *next_name; 746 ldns_rbnode_t *cur_node, *next_node, *new_node; 747 748 /* for the detection */ 749 uint16_t i, cur_label_count, next_label_count; 750 uint16_t soa_label_count = 0; 751 ldns_rdf *l1, *l2; 752 int lpos; 753 754 if (!zone) { 755 return LDNS_STATUS_ERR; 756 } 757 if (zone->soa && zone->soa->name) { 758 soa_label_count = ldns_dname_label_count(zone->soa->name); 759 } 760 761 cur_node = ldns_rbtree_first(zone->names); 762 while (cur_node != LDNS_RBTREE_NULL) { 763 next_node = ldns_rbtree_next(cur_node); 764 765 /* skip glue */ 766 while (next_node != LDNS_RBTREE_NULL && 767 next_node->data && 768 ((ldns_dnssec_name *)next_node->data)->is_glue 769 ) { 770 next_node = ldns_rbtree_next(next_node); 771 } 772 773 if (next_node == LDNS_RBTREE_NULL) { 774 next_node = ldns_rbtree_first(zone->names); 775 } 776 777 cur_name = ((ldns_dnssec_name *)cur_node->data)->name; 778 next_name = ((ldns_dnssec_name *)next_node->data)->name; 779 cur_label_count = ldns_dname_label_count(cur_name); 780 next_label_count = ldns_dname_label_count(next_name); 781 782 /* Since the names are in canonical order, we can 783 * recognize empty non-terminals by their labels; 784 * every label after the first one on the next owner 785 * name is a non-terminal if it either does not exist 786 * in the current name or is different from the same 787 * label in the current name (counting from the end) 788 */ 789 for (i = 1; i < next_label_count - soa_label_count; i++) { 790 lpos = (int)cur_label_count - (int)next_label_count + (int)i; 791 if (lpos >= 0) { 792 l1 = ldns_dname_label(cur_name, (uint8_t)lpos); 793 } else { 794 l1 = NULL; 795 } 796 l2 = ldns_dname_label(next_name, i); 797 798 if (!l1 || ldns_dname_compare(l1, l2) != 0) { 799 /* We have an empty nonterminal, add it to the 800 * tree 801 */ 802 new_name = ldns_dnssec_name_new(); 803 if (!new_name) { 804 return LDNS_STATUS_MEM_ERR; 805 } 806 new_name->name = ldns_dname_clone_from(next_name, 807 i); 808 if (!new_name) { 809 ldns_dnssec_name_free(new_name); 810 return LDNS_STATUS_MEM_ERR; 811 } 812 new_name->name_alloced = true; 813 new_node = LDNS_MALLOC(ldns_rbnode_t); 814 if (!new_node) { 815 ldns_dnssec_name_free(new_name); 816 return LDNS_STATUS_MEM_ERR; 817 } 818 new_node->key = new_name->name; 819 new_node->data = new_name; 820 (void)ldns_rbtree_insert(zone->names, new_node); 821 } 822 ldns_rdf_deep_free(l1); 823 ldns_rdf_deep_free(l2); 824 } 825 826 /* we might have inserted a new node after 827 * the current one so we can't just use next() 828 */ 829 if (next_node != ldns_rbtree_first(zone->names)) { 830 cur_node = next_node; 831 } else { 832 cur_node = LDNS_RBTREE_NULL; 833 } 834 } 835 return LDNS_STATUS_OK; 836 } 837