contrib/ldns/dnssec_zone.c

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