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