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(void)
  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(void)
 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 static 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 static 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 #if 0
 302 static void
 303 ldns_dnssec_rrsets_print_soa(FILE *out,
 304                 ldns_dnssec_rrsets *rrsets,
 305                 bool follow,
 306                 bool show_soa)
 307 {
 308         ldns_dnssec_rrsets_print_soa_fmt(out, ldns_output_format_default,
 309                         rrsets, follow, show_soa);
 310 }
 311 #endif
 312
 313 void
 314 ldns_dnssec_rrsets_print_fmt(FILE *out, const ldns_output_format *fmt,
 315                 ldns_dnssec_rrsets *rrsets,
 316                 bool follow)
 317 {
 318         ldns_dnssec_rrsets_print_soa_fmt(out, fmt, rrsets, follow, true);
 319 }
 320
 321 void
 322 ldns_dnssec_rrsets_print(FILE *out, ldns_dnssec_rrsets *rrsets, bool follow)
 323 {
 324         ldns_dnssec_rrsets_print_fmt(out, ldns_output_format_default,
 325                         rrsets, follow);
 326 }
 327
 328 ldns_dnssec_name *
 329 ldns_dnssec_name_new(void)
 330 {
 331         ldns_dnssec_name *new_name;
 332
 333         new_name = LDNS_CALLOC(ldns_dnssec_name, 1);
 334         if (!new_name) {
 335                 return NULL;
 336         }
 337         /*
 338          * not needed anymore because CALLOC initalizes everything to zero.
 339
 340         new_name->name = NULL;
 341         new_name->rrsets = NULL;
 342         new_name->name_alloced = false;
 343         new_name->nsec = NULL;
 344         new_name->nsec_signatures = NULL;
 345
 346         new_name->is_glue = false;
 347         new_name->hashed_name = NULL;
 348
 349          */
 350         return new_name;
 351 }
 352
 353 ldns_dnssec_name *
 354 ldns_dnssec_name_new_frm_rr(ldns_rr *rr)
 355 {
 356         ldns_dnssec_name *new_name = ldns_dnssec_name_new();
 357
 358         new_name->name = ldns_rr_owner(rr);
 359         if(ldns_dnssec_name_add_rr(new_name, rr) != LDNS_STATUS_OK) {
 360                 ldns_dnssec_name_free(new_name);
 361                 return NULL;
 362         }
 363
 364         return new_name;
 365 }
 366
 367 INLINE void
 368 ldns_dnssec_name_free_internal(ldns_dnssec_name *name,
 369                                int deep)
 370 {
 371         if (name) {
 372                 if (name->name_alloced) {
 373                         ldns_rdf_deep_free(name->name);
 374                 }
 375                 if (name->rrsets) {
 376                         ldns_dnssec_rrsets_free_internal(name->rrsets, deep);
 377                 }
 378                 if (name->nsec && deep) {
 379                         ldns_rr_free(name->nsec);
 380                 }
 381                 if (name->nsec_signatures) {
 382                         ldns_dnssec_rrs_free_internal(name->nsec_signatures, deep);
 383                 }
 384                 if (name->hashed_name) {
 385                         if (deep) {
 386                                 ldns_rdf_deep_free(name->hashed_name);
 387                         }
 388                 }
 389                 LDNS_FREE(name);
 390         }
 391 }
 392
 393 void
 394 ldns_dnssec_name_free(ldns_dnssec_name *name)
 395 {
 396   ldns_dnssec_name_free_internal(name, 0);
 397 }
 398
 399 void
 400 ldns_dnssec_name_deep_free(ldns_dnssec_name *name)
 401 {
 402   ldns_dnssec_name_free_internal(name, 1);
 403 }
 404
 405 ldns_rdf *
 406 ldns_dnssec_name_name(ldns_dnssec_name *name)
 407 {
 408         if (name) {
 409                 return name->name;
 410         }
 411         return NULL;
 412 }
 413
 414 bool
 415 ldns_dnssec_name_is_glue(ldns_dnssec_name *name)
 416 {
 417         if (name) {
 418                 return name->is_glue;
 419         }
 420         return false;
 421 }
 422
 423 void
 424 ldns_dnssec_name_set_name(ldns_dnssec_name *rrset,
 425                                          ldns_rdf *dname)
 426 {
 427         if (rrset && dname) {
 428                 rrset->name = dname;
 429         }
 430 }
 431
 432 #if 0
 433 static ldns_rr *
 434 ldns_dnssec_name_nsec(ldns_dnssec_name *rrset)
 435 {
 436         if (rrset) {
 437                 return rrset->nsec;
 438         }
 439         return NULL;
 440 }
 441 #endif
 442
 443 void
 444 ldns_dnssec_name_set_nsec(ldns_dnssec_name *rrset, ldns_rr *nsec)
 445 {
 446         if (rrset && nsec) {
 447                 rrset->nsec = nsec;
 448         }
 449 }
 450
 451 int
 452 ldns_dnssec_name_cmp(const void *a, const void *b)
 453 {
 454         ldns_dnssec_name *na = (ldns_dnssec_name *) a;
 455         ldns_dnssec_name *nb = (ldns_dnssec_name *) b;
 456
 457         if (na && nb) {
 458                 return ldns_dname_compare(ldns_dnssec_name_name(na),
 459                                                          ldns_dnssec_name_name(nb));
 460         } else if (na) {
 461                 return 1;
 462         } else if (nb) {
 463                 return -1;
 464         } else {
 465                 return 0;
 466         }
 467 }
 468
 469 ldns_status
 470 ldns_dnssec_name_add_rr(ldns_dnssec_name *name,
 471                                     ldns_rr *rr)
 472 {
 473         ldns_status result = LDNS_STATUS_OK;
 474         ldns_rdf *name_name;
 475         bool hashed_name = false;
 476         ldns_rr_type rr_type;
 477         ldns_rr_type typecovered = 0;
 478
 479         /* special handling for NSEC3 and NSECX covering RRSIGS */
 480
 481         if (!name || !rr) {
 482                 return LDNS_STATUS_ERR;
 483         }
 484
 485         rr_type = ldns_rr_get_type(rr);
 486
 487         if (rr_type == LDNS_RR_TYPE_RRSIG) {
 488                 typecovered = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr));
 489         }
 490
 491 #ifdef HAVE_SSL
 492         if (rr_type == LDNS_RR_TYPE_NSEC3 ||
 493             typecovered == LDNS_RR_TYPE_NSEC3) {
 494                 name_name = ldns_nsec3_hash_name_frm_nsec3(rr,
 495                                                                                    ldns_dnssec_name_name(name));
 496                 hashed_name = true;
 497         } else {
 498                 name_name = ldns_dnssec_name_name(name);
 499         }
 500 #else
 501         name_name = ldns_dnssec_name_name(name);
 502 #endif /* HAVE_SSL */
 503
 504         if (rr_type == LDNS_RR_TYPE_NSEC ||
 505             rr_type == LDNS_RR_TYPE_NSEC3) {
 506                 /* XX check if is already set (and error?) */
 507                 name->nsec = rr;
 508         } else if (typecovered == LDNS_RR_TYPE_NSEC ||
 509                          typecovered == LDNS_RR_TYPE_NSEC3) {
 510                 if (name->nsec_signatures) {
 511                         result = ldns_dnssec_rrs_add_rr(name->nsec_signatures, rr);
 512                 } else {
 513                         name->nsec_signatures = ldns_dnssec_rrs_new();
 514                         name->nsec_signatures->rr = rr;
 515                 }
 516         } else {
 517                 /* it's a 'normal' RR, add it to the right rrset */
 518                 if (name->rrsets) {
 519                         result = ldns_dnssec_rrsets_add_rr(name->rrsets, rr);
 520                 } else {
 521                         name->rrsets = ldns_dnssec_rrsets_new();
 522                         result = ldns_dnssec_rrsets_add_rr(name->rrsets, rr);
 523                 }
 524         }
 525
 526         if (hashed_name) {
 527                 ldns_rdf_deep_free(name_name);
 528         }
 529
 530         return result;
 531 }
 532
 533 ldns_dnssec_rrsets *
 534 ldns_dnssec_name_find_rrset(ldns_dnssec_name *name,
 535                                            ldns_rr_type type) {
 536         ldns_dnssec_rrsets *result;
 537
 538         result = name->rrsets;
 539         while (result) {
 540                 if (result->type == type) {
 541                         return result;
 542                 } else {
 543                         result = result->next;
 544                 }
 545         }
 546         return NULL;
 547 }
 548
 549 ldns_dnssec_rrsets *
 550 ldns_dnssec_zone_find_rrset(ldns_dnssec_zone *zone,
 551                                            ldns_rdf *dname,
 552                                            ldns_rr_type type)
 553 {
 554         ldns_rbnode_t *node;
 555
 556         if (!zone || !dname) {
 557                 return NULL;
 558         }
 559
 560         node = ldns_rbtree_search(zone->names, dname);
 561         if (node) {
 562                 return ldns_dnssec_name_find_rrset((ldns_dnssec_name *)node->data,
 563                                                                         type);
 564         } else {
 565                 return NULL;
 566         }
 567 }
 568
 569 static void
 570 ldns_dnssec_name_print_soa_fmt(FILE *out, const ldns_output_format *fmt,
 571                 ldns_dnssec_name *name,
 572                 bool show_soa)
 573 {
 574         if (name) {
 575                 if(name->rrsets) {
 576                         ldns_dnssec_rrsets_print_soa_fmt(out, fmt,
 577                                         name->rrsets, true, show_soa);
 578                 } else if ((fmt->flags & LDNS_COMMENT_LAYOUT)) {
 579                         fprintf(out, ";; Empty nonterminal: ");
 580                         ldns_rdf_print(out, name->name);
 581                         fprintf(out, "\n");
 582                 }
 583                 if(name->nsec) {
 584                         ldns_rr_print_fmt(out, fmt, name->nsec);
 585                 }
 586                 if (name->nsec_signatures) {
 587                         ldns_dnssec_rrs_print_fmt(out, fmt,
 588                                         name->nsec_signatures);
 589                 }
 590         } else if ((fmt->flags & LDNS_COMMENT_LAYOUT)) {
 591                 fprintf(out, "; <void>\n");
 592         }
 593 }
 594
 595 #if 0
 596 static void
 597 ldns_dnssec_name_print_soa(FILE *out, ldns_dnssec_name *name, bool show_soa)
 598 {
 599         ldns_dnssec_name_print_soa_fmt(out, ldns_output_format_default,
 600                        name, show_soa);
 601 }
 602 #endif
 603
 604 void
 605 ldns_dnssec_name_print_fmt(FILE *out, const ldns_output_format *fmt,
 606                 ldns_dnssec_name *name)
 607 {
 608         ldns_dnssec_name_print_soa_fmt(out, fmt, name, true);
 609 }
 610
 611 void
 612 ldns_dnssec_name_print(FILE *out, ldns_dnssec_name *name)
 613 {
 614         ldns_dnssec_name_print_fmt(out, ldns_output_format_default, name);
 615 }
 616
 617
 618 ldns_dnssec_zone *
 619 ldns_dnssec_zone_new(void)
 620 {
 621         ldns_dnssec_zone *zone = LDNS_MALLOC(ldns_dnssec_zone);
 622         if(!zone) return NULL;
 623         zone->soa = NULL;
 624         zone->names = NULL;
 625
 626         return zone;
 627 }
 628
 629 static bool
 630 rr_is_rrsig_covering(ldns_rr* rr, ldns_rr_type t)
 631 {
 632         return     ldns_rr_get_type(rr) == LDNS_RR_TYPE_RRSIG
 633                 && ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr)) == t;
 634 }
 635
 636 /* When the zone is first read into an list and then inserted into an
 637  * ldns_dnssec_zone (rbtree) the nodes of the rbtree are allocated close (next)
 638  * to each other. Because ldns-verify-zone (the only program that uses this
 639  * function) uses the rbtree mostly for sequentual walking, this results
 640  * in a speed increase (of 15% on linux) because we have less CPU-cache misses.
 641  */
 642 #define FASTER_DNSSEC_ZONE_NEW_FRM_FP 1 /* Because of L2 cache efficiency */
 643
 644 ldns_status
 645 ldns_dnssec_zone_new_frm_fp_l(ldns_dnssec_zone** z, FILE* fp, ldns_rdf* origin,
 646                 uint32_t ttl, ldns_rr_class ATTR_UNUSED(c), int* line_nr)
 647 {
 648         ldns_rr* cur_rr;
 649         size_t i;
 650
 651         ldns_rdf *my_origin = NULL;
 652         ldns_rdf *my_prev = NULL;
 653
 654         ldns_dnssec_zone *newzone = ldns_dnssec_zone_new();
 655         /* when reading NSEC3s, there is a chance that we encounter nsecs
 656            for empty nonterminals, whose nonterminals we cannot derive yet
 657            because the needed information is to be read later. in that case
 658            we keep a list of those nsec3's and retry to add them later */
 659         ldns_rr_list* todo_nsec3s = ldns_rr_list_new();
 660         ldns_rr_list* todo_nsec3_rrsigs = ldns_rr_list_new();
 661
 662         ldns_status status = LDNS_STATUS_MEM_ERR;
 663
 664 #ifdef FASTER_DNSSEC_ZONE_NEW_FRM_FP
 665         ldns_zone* zone = NULL;
 666         if (ldns_zone_new_frm_fp_l(&zone, fp, origin,ttl, c, line_nr)
 667                         != LDNS_STATUS_OK) goto error;
 668 #else
 669         uint32_t  my_ttl = ttl;
 670 #endif
 671
 672         if (!newzone || !todo_nsec3s || !todo_nsec3_rrsigs ) goto error;
 673
 674         if (origin) {
 675                 if (!(my_origin = ldns_rdf_clone(origin))) goto error;
 676                 if (!(my_prev   = ldns_rdf_clone(origin))) goto error;
 677         }
 678
 679 #ifdef FASTER_DNSSEC_ZONE_NEW_FRM_FP
 680         if (ldns_dnssec_zone_add_rr(newzone, ldns_zone_soa(zone))
 681                         != LDNS_STATUS_OK) goto error;
 682
 683         for (i = 0; i < ldns_rr_list_rr_count(ldns_zone_rrs(zone)); i++) {
 684                 cur_rr = ldns_rr_list_rr(ldns_zone_rrs(zone), i);
 685                 status = LDNS_STATUS_OK;
 686 #else
 687         while (!feof(fp)) {
 688                 status = ldns_rr_new_frm_fp_l(&cur_rr, fp, &my_ttl, &my_origin,
 689                                 &my_prev, line_nr);
 690
 691 #endif
 692                 switch (status) {
 693                 case LDNS_STATUS_OK:
 694
 695                         status = ldns_dnssec_zone_add_rr(newzone, cur_rr);
 696                         if (status ==
 697                                 LDNS_STATUS_DNSSEC_NSEC3_ORIGINAL_NOT_FOUND) {
 698
 699                                 if (rr_is_rrsig_covering(cur_rr,
 700                                                         LDNS_RR_TYPE_NSEC3)){
 701                                         ldns_rr_list_push_rr(todo_nsec3_rrsigs,
 702                                                         cur_rr);
 703                                 } else {
 704                                         ldns_rr_list_push_rr(todo_nsec3s,
 705                                                         cur_rr);
 706                                 }
 707                         } else if (status != LDNS_STATUS_OK)
 708                                 goto error;
 709
 710                         break;
 711
 712
 713                 case LDNS_STATUS_SYNTAX_EMPTY:  /* empty line was seen */
 714                 case LDNS_STATUS_SYNTAX_TTL:    /* the ttl was set*/
 715                 case LDNS_STATUS_SYNTAX_ORIGIN: /* the origin was set*/
 716                         status = LDNS_STATUS_OK;
 717                         break;
 718
 719                 case LDNS_STATUS_SYNTAX_INCLUDE:/* $include not implemented */
 720                         status =  LDNS_STATUS_SYNTAX_INCLUDE_ERR_NOTIMPL;
 721                         break;
 722
 723                 default:
 724                         goto error;
 725                 }
 726         }
 727
 728         if (ldns_rr_list_rr_count(todo_nsec3s) > 0) {
 729                 (void) ldns_dnssec_zone_add_empty_nonterminals(newzone);
 730                 for (i = 0; status == LDNS_STATUS_OK &&
 731                                 i < ldns_rr_list_rr_count(todo_nsec3s); i++) {
 732                         cur_rr = ldns_rr_list_rr(todo_nsec3s, i);
 733                         status = ldns_dnssec_zone_add_rr(newzone, cur_rr);
 734                 }
 735                 for (i = 0; status == LDNS_STATUS_OK &&
 736                                 i < ldns_rr_list_rr_count(todo_nsec3_rrsigs);
 737                                 i++){
 738                         cur_rr = ldns_rr_list_rr(todo_nsec3_rrsigs, i);
 739                         status = ldns_dnssec_zone_add_rr(newzone, cur_rr);
 740                 }
 741         } else if (ldns_rr_list_rr_count(todo_nsec3_rrsigs) > 0) {
 742                 for (i = 0; status == LDNS_STATUS_OK &&
 743                                 i < ldns_rr_list_rr_count(todo_nsec3_rrsigs);
 744                                 i++){
 745                         cur_rr = ldns_rr_list_rr(todo_nsec3_rrsigs, i);
 746                         status = ldns_dnssec_zone_add_rr(newzone, cur_rr);
 747                 }
 748         }
 749
 750         if (z) {
 751                 *z = newzone;
 752                 newzone = NULL;
 753         } else {
 754                 ldns_dnssec_zone_free(newzone);
 755         }
 756
 757 error:
 758 #ifdef FASTER_DNSSEC_ZONE_NEW_FRM_FP
 759         if (zone) {
 760                 ldns_zone_free(zone);
 761         }
 762 #endif
 763         ldns_rr_list_free(todo_nsec3_rrsigs);
 764         ldns_rr_list_free(todo_nsec3s);
 765
 766         if (my_origin) {
 767                 ldns_rdf_deep_free(my_origin);
 768         }
 769         if (my_prev) {
 770                 ldns_rdf_deep_free(my_prev);
 771         }
 772         if (newzone) {
 773                 ldns_dnssec_zone_free(newzone);
 774         }
 775         return status;
 776 }
 777
 778 ldns_status
 779 ldns_dnssec_zone_new_frm_fp(ldns_dnssec_zone** z, FILE* fp, ldns_rdf* origin,
 780                 uint32_t ttl, ldns_rr_class ATTR_UNUSED(c))
 781 {
 782         return ldns_dnssec_zone_new_frm_fp_l(z, fp, origin, ttl, c, NULL);
 783 }
 784
 785 static void
 786 ldns_dnssec_name_node_free(ldns_rbnode_t *node, void *arg) {
 787         (void) arg;
 788         ldns_dnssec_name_free((ldns_dnssec_name *)node->data);
 789         LDNS_FREE(node);
 790 }
 791
 792 static void
 793 ldns_dnssec_name_node_deep_free(ldns_rbnode_t *node, void *arg) {
 794         (void) arg;
 795         ldns_dnssec_name_deep_free((ldns_dnssec_name *)node->data);
 796         LDNS_FREE(node);
 797 }
 798
 799 void
 800 ldns_dnssec_zone_free(ldns_dnssec_zone *zone)
 801 {
 802         if (zone) {
 803                 if (zone->names) {
 804                         /* destroy all name structures within the tree */
 805                         ldns_traverse_postorder(zone->names,
 806                                                     ldns_dnssec_name_node_free,
 807                                                     NULL);
 808                         LDNS_FREE(zone->names);
 809                 }
 810                 LDNS_FREE(zone);
 811         }
 812 }
 813
 814 void
 815 ldns_dnssec_zone_deep_free(ldns_dnssec_zone *zone)
 816 {
 817         if (zone) {
 818                 if (zone->names) {
 819                         /* destroy all name structures within the tree */
 820                         ldns_traverse_postorder(zone->names,
 821                                                     ldns_dnssec_name_node_deep_free,
 822                                                     NULL);
 823                         LDNS_FREE(zone->names);
 824                 }
 825                 LDNS_FREE(zone);
 826         }
 827 }
 828
 829 /* use for dname comparison in tree */
 830 static int
 831 ldns_dname_compare_v(const void *a, const void *b) {
 832         return ldns_dname_compare((ldns_rdf *)a, (ldns_rdf *)b);
 833 }
 834
 835 static ldns_rbnode_t *
 836 ldns_dnssec_zone_find_nsec3_original(ldns_dnssec_zone *zone,
 837                                      ldns_rr *rr) {
 838         ldns_rbnode_t *current_node = ldns_rbtree_first(zone->names);
 839         ldns_dnssec_name *current_name;
 840         ldns_rdf *hashed_name;
 841
 842         hashed_name = ldns_dname_label(ldns_rr_owner(rr), 0);
 843
 844         while (current_node != LDNS_RBTREE_NULL) {
 845                 current_name = (ldns_dnssec_name *) current_node->data;
 846                 if (!current_name->hashed_name) {
 847                         current_name->hashed_name =
 848                                 ldns_nsec3_hash_name_frm_nsec3(rr, current_name->name);
 849                 }
 850                 if (ldns_dname_compare(hashed_name,
 851                                                    current_name->hashed_name)
 852                     == 0) {
 853                         ldns_rdf_deep_free(hashed_name);
 854                         return current_node;
 855                 }
 856                 current_node = ldns_rbtree_next(current_node);
 857         }
 858         ldns_rdf_deep_free(hashed_name);
 859         return NULL;
 860 }
 861
 862 ldns_status
 863 ldns_dnssec_zone_add_rr(ldns_dnssec_zone *zone, ldns_rr *rr)
 864 {
 865         ldns_status result = LDNS_STATUS_OK;
 866         ldns_dnssec_name *cur_name;
 867         ldns_rbnode_t *cur_node;
 868         ldns_rr_type type_covered = 0;
 869
 870         if (!zone || !rr) {
 871                 return LDNS_STATUS_ERR;
 872         }
 873
 874         if (!zone->names) {
 875                 zone->names = ldns_rbtree_create(ldns_dname_compare_v);
 876                 if(!zone->names) return LDNS_STATUS_MEM_ERR;
 877         }
 878
 879         /* we need the original of the hashed name if this is
 880            an NSEC3, or an RRSIG that covers an NSEC3 */
 881         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_RRSIG) {
 882                 type_covered = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr));
 883         }
 884         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_NSEC3 ||
 885             type_covered == LDNS_RR_TYPE_NSEC3) {
 886                 cur_node = ldns_dnssec_zone_find_nsec3_original(zone,
 887                                                                                            rr);
 888                 if (!cur_node) {
 889                         return LDNS_STATUS_DNSSEC_NSEC3_ORIGINAL_NOT_FOUND;
 890                 }
 891         } else {
 892                 cur_node = ldns_rbtree_search(zone->names, ldns_rr_owner(rr));
 893         }
 894
 895         if (!cur_node) {
 896                 /* add */
 897                 cur_name = ldns_dnssec_name_new_frm_rr(rr);
 898                 if(!cur_name) return LDNS_STATUS_MEM_ERR;
 899                 cur_node = LDNS_MALLOC(ldns_rbnode_t);
 900                 if(!cur_node) {
 901                         ldns_dnssec_name_free(cur_name);
 902                         return LDNS_STATUS_MEM_ERR;
 903                 }
 904                 cur_node->key = ldns_rr_owner(rr);
 905                 cur_node->data = cur_name;
 906                 (void)ldns_rbtree_insert(zone->names, cur_node);
 907         } else {
 908                 cur_name = (ldns_dnssec_name *) cur_node->data;
 909                 result = ldns_dnssec_name_add_rr(cur_name, rr);
 910         }
 911
 912         if (result != LDNS_STATUS_OK) {
 913                 fprintf(stderr, "error adding rr: ");
 914                 ldns_rr_print(stderr, rr);
 915         }
 916
 917         /*TODO ldns_dnssec_name_print_names(stdout, zone->names, 0);*/
 918         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_SOA) {
 919                 zone->soa = cur_name;
 920         }
 921
 922         return result;
 923 }
 924
 925 void
 926 ldns_dnssec_zone_names_print_fmt(FILE *out, const ldns_output_format *fmt,
 927                 ldns_rbtree_t *tree,
 928                 bool print_soa)
 929 {
 930         ldns_rbnode_t *node;
 931         ldns_dnssec_name *name;
 932
 933         node = ldns_rbtree_first(tree);
 934         while (node != LDNS_RBTREE_NULL) {
 935                 name = (ldns_dnssec_name *) node->data;
 936                 ldns_dnssec_name_print_soa_fmt(out, fmt, name, print_soa);
 937                 if ((fmt->flags & LDNS_COMMENT_LAYOUT))
 938                         fprintf(out, ";\n");
 939                 node = ldns_rbtree_next(node);
 940         }
 941 }
 942
 943 void
 944 ldns_dnssec_zone_names_print(FILE *out, ldns_rbtree_t *tree, bool print_soa)
 945 {
 946         ldns_dnssec_zone_names_print_fmt(out, ldns_output_format_default,
 947                        tree, print_soa);
 948 }
 949
 950 void
 951 ldns_dnssec_zone_print_fmt(FILE *out, const ldns_output_format *fmt,
 952                ldns_dnssec_zone *zone)
 953 {
 954         if (zone) {
 955                 if (zone->soa) {
 956                         if ((fmt->flags & LDNS_COMMENT_LAYOUT)) {
 957                                 fprintf(out, ";; Zone: ");
 958                                 ldns_rdf_print(out, ldns_dnssec_name_name(
 959                                                         zone->soa));
 960                                 fprintf(out, "\n;\n");
 961                         }
 962                         ldns_dnssec_rrsets_print_fmt(out, fmt,
 963                                         ldns_dnssec_name_find_rrset(
 964                                                 zone->soa,
 965                                                 LDNS_RR_TYPE_SOA),
 966                                         false);
 967                         if ((fmt->flags & LDNS_COMMENT_LAYOUT))
 968                                 fprintf(out, ";\n");
 969                 }
 970
 971                 if (zone->names) {
 972                         ldns_dnssec_zone_names_print_fmt(out, fmt,
 973                                         zone->names, false);
 974                 }
 975         }
 976 }
 977
 978 void
 979 ldns_dnssec_zone_print(FILE *out, ldns_dnssec_zone *zone)
 980 {
 981         ldns_dnssec_zone_print_fmt(out, ldns_output_format_default, zone);
 982 }
 983
 984 ldns_status
 985 ldns_dnssec_zone_add_empty_nonterminals(ldns_dnssec_zone *zone)
 986 {
 987         ldns_dnssec_name *new_name;
 988         ldns_rdf *cur_name;
 989         ldns_rdf *next_name;
 990         ldns_rbnode_t *cur_node, *next_node, *new_node;
 991
 992         /* for the detection */
 993         uint16_t i, cur_label_count, next_label_count;
 994         uint16_t soa_label_count = 0;
 995         ldns_rdf *l1, *l2;
 996         int lpos;
 997
 998         if (!zone) {
 999                 return LDNS_STATUS_ERR;
1000         }
1001         if (zone->soa && zone->soa->name) {
1002                 soa_label_count = ldns_dname_label_count(zone->soa->name);
1003         }
1004
1005         cur_node = ldns_rbtree_first(zone->names);
1006         while (cur_node != LDNS_RBTREE_NULL) {
1007                 next_node = ldns_rbtree_next(cur_node);
1008
1009                 /* skip glue */
1010                 while (next_node != LDNS_RBTREE_NULL &&
1011                        next_node->data &&
1012                        ((ldns_dnssec_name *)next_node->data)->is_glue
1013                 ) {
1014                         next_node = ldns_rbtree_next(next_node);
1015                 }
1016
1017                 if (next_node == LDNS_RBTREE_NULL) {
1018                         next_node = ldns_rbtree_first(zone->names);
1019                 }
1020                 if (! cur_node->data || ! next_node->data) {
1021                         return LDNS_STATUS_ERR;
1022                 }
1023                 cur_name = ((ldns_dnssec_name *)cur_node->data)->name;
1024                 next_name = ((ldns_dnssec_name *)next_node->data)->name;
1025                 cur_label_count = ldns_dname_label_count(cur_name);
1026                 next_label_count = ldns_dname_label_count(next_name);
1027
1028                 /* Since the names are in canonical order, we can
1029                  * recognize empty non-terminals by their labels;
1030                  * every label after the first one on the next owner
1031                  * name is a non-terminal if it either does not exist
1032                  * in the current name or is different from the same
1033                  * label in the current name (counting from the end)
1034                  */
1035                 for (i = 1; i < next_label_count - soa_label_count; i++) {
1036                         lpos = (int)cur_label_count - (int)next_label_count + (int)i;
1037                         if (lpos >= 0) {
1038                                 l1 = ldns_dname_clone_from(cur_name, (uint8_t)lpos);
1039                         } else {
1040                                 l1 = NULL;
1041                         }
1042                         l2 = ldns_dname_clone_from(next_name, i);
1043
1044                         if (!l1 || ldns_dname_compare(l1, l2) != 0) {
1045                                 /* We have an empty nonterminal, add it to the
1046                                  * tree
1047                                  */
1048                                 new_name = ldns_dnssec_name_new();
1049                                 if (!new_name) {
1050                                         return LDNS_STATUS_MEM_ERR;
1051                                 }
1052                                 new_name->name = ldns_dname_clone_from(next_name,
1053                                                                        i);
1054                                 if (!new_name->name) {
1055                                         ldns_dnssec_name_free(new_name);
1056                                         return LDNS_STATUS_MEM_ERR;
1057                                 }
1058                                 new_name->name_alloced = true;
1059                                 new_node = LDNS_MALLOC(ldns_rbnode_t);
1060                                 if (!new_node) {
1061                                         ldns_dnssec_name_free(new_name);
1062                                         return LDNS_STATUS_MEM_ERR;
1063                                 }
1064                                 new_node->key = new_name->name;
1065                                 new_node->data = new_name;
1066                                 (void)ldns_rbtree_insert(zone->names, new_node);
1067                         }
1068                         ldns_rdf_deep_free(l1);
1069                         ldns_rdf_deep_free(l2);
1070                 }
1071
1072                 /* we might have inserted a new node after
1073                  * the current one so we can't just use next()
1074                  */
1075                 if (next_node != ldns_rbtree_first(zone->names)) {
1076                         cur_node = next_node;
1077                 } else {
1078                         cur_node = LDNS_RBTREE_NULL;
1079                 }
1080         }
1081         return LDNS_STATUS_OK;
1082 }
1083
1084 bool
1085 ldns_dnssec_zone_is_nsec3_optout(ldns_dnssec_zone* zone)
1086 {
1087         ldns_rr* nsec3;
1088         ldns_rbnode_t* node;
1089
1090         if (ldns_dnssec_name_find_rrset(zone->soa, LDNS_RR_TYPE_NSEC3PARAM)) {
1091                 node = ldns_rbtree_first(zone->names);
1092                 while (node != LDNS_RBTREE_NULL) {
1093                         nsec3 = ((ldns_dnssec_name*)node->data)->nsec;
1094                         if (nsec3 &&ldns_rr_get_type(nsec3)
1095                                         == LDNS_RR_TYPE_NSEC3 &&
1096                                         ldns_nsec3_optout(nsec3)) {
1097                                 return true;
1098                         }
1099                         node = ldns_rbtree_next(node);
1100                 }
1101         }
1102         return false;
1103 }