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 static bool
 625 rr_is_rrsig_covering(ldns_rr* rr, ldns_rr_type t)
 626 {
 627         return     ldns_rr_get_type(rr) == LDNS_RR_TYPE_RRSIG
 628                 && ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr)) == t;
 629 }
 630
 631 /* When the zone is first read into an list and then inserted into an
 632  * ldns_dnssec_zone (rbtree) the nodes of the rbtree are allocated close (next)
 633  * to each other. Because ldns-verify-zone (the only program that uses this
 634  * function) uses the rbtree mostly for sequentual walking, this results
 635  * in a speed increase (of 15% on linux) because we have less CPU-cache misses.
 636  */
 637 #define FASTER_DNSSEC_ZONE_NEW_FRM_FP 1 /* Because of L2 cache efficiency */
 638
 639 ldns_status
 640 ldns_dnssec_zone_new_frm_fp_l(ldns_dnssec_zone** z, FILE* fp, ldns_rdf* origin,
 641                 uint32_t ttl, ldns_rr_class ATTR_UNUSED(c), int* line_nr)
 642 {
 643         ldns_rr* cur_rr;
 644         size_t i;
 645
 646         ldns_rdf *my_origin = NULL;
 647         ldns_rdf *my_prev = NULL;
 648
 649         ldns_dnssec_zone *newzone = ldns_dnssec_zone_new();
 650         /* when reading NSEC3s, there is a chance that we encounter nsecs
 651            for empty nonterminals, whose nonterminals we cannot derive yet
 652            because the needed information is to be read later. in that case
 653            we keep a list of those nsec3's and retry to add them later */
 654         ldns_rr_list* todo_nsec3s = ldns_rr_list_new();
 655         ldns_rr_list* todo_nsec3_rrsigs = ldns_rr_list_new();
 656
 657         ldns_status status = LDNS_STATUS_MEM_ERR;
 658
 659 #ifdef FASTER_DNSSEC_ZONE_NEW_FRM_FP
 660         ldns_zone* zone = NULL;
 661         if (ldns_zone_new_frm_fp_l(&zone, fp, origin,ttl, c, line_nr)
 662                         != LDNS_STATUS_OK) goto error;
 663 #else
 664         uint32_t  my_ttl = ttl;
 665 #endif
 666
 667         if (!newzone || !todo_nsec3s || !todo_nsec3_rrsigs ) goto error;
 668
 669         if (origin) {
 670                 if (!(my_origin = ldns_rdf_clone(origin))) goto error;
 671                 if (!(my_prev   = ldns_rdf_clone(origin))) goto error;
 672         }
 673
 674 #ifdef FASTER_DNSSEC_ZONE_NEW_FRM_FP
 675         if (ldns_dnssec_zone_add_rr(newzone, ldns_zone_soa(zone))
 676                         != LDNS_STATUS_OK) goto error;
 677
 678         for (i = 0; i < ldns_rr_list_rr_count(ldns_zone_rrs(zone)); i++) {
 679                 cur_rr = ldns_rr_list_rr(ldns_zone_rrs(zone), i);
 680                 status = LDNS_STATUS_OK;
 681 #else
 682         while (!feof(fp)) {
 683                 status = ldns_rr_new_frm_fp_l(&cur_rr, fp, &my_ttl, &my_origin,
 684                                 &my_prev, line_nr);
 685
 686 #endif
 687                 switch (status) {
 688                 case LDNS_STATUS_OK:
 689
 690                         status = ldns_dnssec_zone_add_rr(newzone, cur_rr);
 691                         if (status ==
 692                                 LDNS_STATUS_DNSSEC_NSEC3_ORIGINAL_NOT_FOUND) {
 693
 694                                 if (rr_is_rrsig_covering(cur_rr,
 695                                                         LDNS_RR_TYPE_NSEC3)){
 696                                         ldns_rr_list_push_rr(todo_nsec3_rrsigs,
 697                                                         cur_rr);
 698                                 } else {
 699                                         ldns_rr_list_push_rr(todo_nsec3s,
 700                                                         cur_rr);
 701                                 }
 702                         } else if (status != LDNS_STATUS_OK)
 703                                 goto error;
 704
 705                         break;
 706
 707
 708                 case LDNS_STATUS_SYNTAX_EMPTY:  /* empty line was seen */
 709                 case LDNS_STATUS_SYNTAX_TTL:    /* the ttl was set*/
 710                 case LDNS_STATUS_SYNTAX_ORIGIN: /* the origin was set*/
 711                         status = LDNS_STATUS_OK;
 712                         break;
 713
 714                 case LDNS_STATUS_SYNTAX_INCLUDE:/* $include not implemented */
 715                         status =  LDNS_STATUS_SYNTAX_INCLUDE_ERR_NOTIMPL;
 716                         break;
 717
 718                 default:
 719                         goto error;
 720                 }
 721         }
 722
 723         if (ldns_rr_list_rr_count(todo_nsec3s) > 0) {
 724                 (void) ldns_dnssec_zone_add_empty_nonterminals(newzone);
 725                 for (i = 0; status == LDNS_STATUS_OK &&
 726                                 i < ldns_rr_list_rr_count(todo_nsec3s); i++) {
 727                         cur_rr = ldns_rr_list_rr(todo_nsec3s, i);
 728                         status = ldns_dnssec_zone_add_rr(newzone, cur_rr);
 729                 }
 730                 for (i = 0; status == LDNS_STATUS_OK &&
 731                                 i < ldns_rr_list_rr_count(todo_nsec3_rrsigs);
 732                                 i++){
 733                         cur_rr = ldns_rr_list_rr(todo_nsec3_rrsigs, i);
 734                         status = ldns_dnssec_zone_add_rr(newzone, cur_rr);
 735                 }
 736         } else if (ldns_rr_list_rr_count(todo_nsec3_rrsigs) > 0) {
 737                 for (i = 0; status == LDNS_STATUS_OK &&
 738                                 i < ldns_rr_list_rr_count(todo_nsec3_rrsigs);
 739                                 i++){
 740                         cur_rr = ldns_rr_list_rr(todo_nsec3_rrsigs, i);
 741                         status = ldns_dnssec_zone_add_rr(newzone, cur_rr);
 742                 }
 743         }
 744
 745         if (z) {
 746                 *z = newzone;
 747                 newzone = NULL;
 748         } else {
 749                 ldns_dnssec_zone_free(newzone);
 750         }
 751
 752 error:
 753 #ifdef FASTER_DNSSEC_ZONE_NEW_FRM_FP
 754         if (zone) {
 755                 ldns_zone_free(zone);
 756         }
 757 #endif
 758         ldns_rr_list_free(todo_nsec3_rrsigs);
 759         ldns_rr_list_free(todo_nsec3s);
 760
 761         if (my_origin) {
 762                 ldns_rdf_deep_free(my_origin);
 763         }
 764         if (my_prev) {
 765                 ldns_rdf_deep_free(my_prev);
 766         }
 767         if (newzone) {
 768                 ldns_dnssec_zone_free(newzone);
 769         }
 770         return status;
 771 }
 772
 773 ldns_status
 774 ldns_dnssec_zone_new_frm_fp(ldns_dnssec_zone** z, FILE* fp, ldns_rdf* origin,
 775                 uint32_t ttl, ldns_rr_class ATTR_UNUSED(c))
 776 {
 777         return ldns_dnssec_zone_new_frm_fp_l(z, fp, origin, ttl, c, NULL);
 778 }
 779
 780 void
 781 ldns_dnssec_name_node_free(ldns_rbnode_t *node, void *arg) {
 782         (void) arg;
 783         ldns_dnssec_name_free((ldns_dnssec_name *)node->data);
 784         LDNS_FREE(node);
 785 }
 786
 787 void
 788 ldns_dnssec_name_node_deep_free(ldns_rbnode_t *node, void *arg) {
 789         (void) arg;
 790         ldns_dnssec_name_deep_free((ldns_dnssec_name *)node->data);
 791         LDNS_FREE(node);
 792 }
 793
 794 void
 795 ldns_dnssec_zone_free(ldns_dnssec_zone *zone)
 796 {
 797         if (zone) {
 798                 if (zone->names) {
 799                         /* destroy all name structures within the tree */
 800                         ldns_traverse_postorder(zone->names,
 801                                                     ldns_dnssec_name_node_free,
 802                                                     NULL);
 803                         LDNS_FREE(zone->names);
 804                 }
 805                 LDNS_FREE(zone);
 806         }
 807 }
 808
 809 void
 810 ldns_dnssec_zone_deep_free(ldns_dnssec_zone *zone)
 811 {
 812         if (zone) {
 813                 if (zone->names) {
 814                         /* destroy all name structures within the tree */
 815                         ldns_traverse_postorder(zone->names,
 816                                                     ldns_dnssec_name_node_deep_free,
 817                                                     NULL);
 818                         LDNS_FREE(zone->names);
 819                 }
 820                 LDNS_FREE(zone);
 821         }
 822 }
 823
 824 /* use for dname comparison in tree */
 825 int
 826 ldns_dname_compare_v(const void *a, const void *b) {
 827         return ldns_dname_compare((ldns_rdf *)a, (ldns_rdf *)b);
 828 }
 829
 830 ldns_rbnode_t *
 831 ldns_dnssec_zone_find_nsec3_original(ldns_dnssec_zone *zone,
 832                                      ldns_rr *rr) {
 833         ldns_rbnode_t *current_node = ldns_rbtree_first(zone->names);
 834         ldns_dnssec_name *current_name;
 835         ldns_rdf *hashed_name;
 836
 837         hashed_name = ldns_dname_label(ldns_rr_owner(rr), 0);
 838
 839         while (current_node != LDNS_RBTREE_NULL) {
 840                 current_name = (ldns_dnssec_name *) current_node->data;
 841                 if (!current_name->hashed_name) {
 842                         current_name->hashed_name =
 843                                 ldns_nsec3_hash_name_frm_nsec3(rr, current_name->name);
 844                 }
 845                 if (ldns_dname_compare(hashed_name,
 846                                                    current_name->hashed_name)
 847                     == 0) {
 848                         ldns_rdf_deep_free(hashed_name);
 849                         return current_node;
 850                 }
 851                 current_node = ldns_rbtree_next(current_node);
 852         }
 853         ldns_rdf_deep_free(hashed_name);
 854         return NULL;
 855 }
 856
 857 ldns_status
 858 ldns_dnssec_zone_add_rr(ldns_dnssec_zone *zone, ldns_rr *rr)
 859 {
 860         ldns_status result = LDNS_STATUS_OK;
 861         ldns_dnssec_name *cur_name;
 862         ldns_rbnode_t *cur_node;
 863         ldns_rr_type type_covered = 0;
 864
 865         if (!zone || !rr) {
 866                 return LDNS_STATUS_ERR;
 867         }
 868
 869         if (!zone->names) {
 870                 zone->names = ldns_rbtree_create(ldns_dname_compare_v);
 871                 if(!zone->names) return LDNS_STATUS_MEM_ERR;
 872         }
 873
 874         /* we need the original of the hashed name if this is
 875            an NSEC3, or an RRSIG that covers an NSEC3 */
 876         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_RRSIG) {
 877                 type_covered = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr));
 878         }
 879         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_NSEC3 ||
 880             type_covered == LDNS_RR_TYPE_NSEC3) {
 881                 cur_node = ldns_dnssec_zone_find_nsec3_original(zone,
 882                                                                                            rr);
 883                 if (!cur_node) {
 884                         return LDNS_STATUS_DNSSEC_NSEC3_ORIGINAL_NOT_FOUND;
 885                 }
 886         } else {
 887                 cur_node = ldns_rbtree_search(zone->names, ldns_rr_owner(rr));
 888         }
 889
 890         if (!cur_node) {
 891                 /* add */
 892                 cur_name = ldns_dnssec_name_new_frm_rr(rr);
 893                 if(!cur_name) return LDNS_STATUS_MEM_ERR;
 894                 cur_node = LDNS_MALLOC(ldns_rbnode_t);
 895                 if(!cur_node) {
 896                         ldns_dnssec_name_free(cur_name);
 897                         return LDNS_STATUS_MEM_ERR;
 898                 }
 899                 cur_node->key = ldns_rr_owner(rr);
 900                 cur_node->data = cur_name;
 901                 (void)ldns_rbtree_insert(zone->names, cur_node);
 902         } else {
 903                 cur_name = (ldns_dnssec_name *) cur_node->data;
 904                 result = ldns_dnssec_name_add_rr(cur_name, rr);
 905         }
 906
 907         if (result != LDNS_STATUS_OK) {
 908                 fprintf(stderr, "error adding rr: ");
 909                 ldns_rr_print(stderr, rr);
 910         }
 911
 912         /*TODO ldns_dnssec_name_print_names(stdout, zone->names, 0);*/
 913         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_SOA) {
 914                 zone->soa = cur_name;
 915         }
 916
 917         return result;
 918 }
 919
 920 void
 921 ldns_dnssec_zone_names_print_fmt(FILE *out, const ldns_output_format *fmt,
 922                 ldns_rbtree_t *tree,
 923                 bool print_soa)
 924 {
 925         ldns_rbnode_t *node;
 926         ldns_dnssec_name *name;
 927
 928         node = ldns_rbtree_first(tree);
 929         while (node != LDNS_RBTREE_NULL) {
 930                 name = (ldns_dnssec_name *) node->data;
 931                 ldns_dnssec_name_print_soa_fmt(out, fmt, name, print_soa);
 932                 if ((fmt->flags & LDNS_COMMENT_LAYOUT))
 933                         fprintf(out, ";\n");
 934                 node = ldns_rbtree_next(node);
 935         }
 936 }
 937
 938 void
 939 ldns_dnssec_zone_names_print(FILE *out, ldns_rbtree_t *tree, bool print_soa)
 940 {
 941         ldns_dnssec_zone_names_print_fmt(out, ldns_output_format_default,
 942                        tree, print_soa);
 943 }
 944
 945 void
 946 ldns_dnssec_zone_print_fmt(FILE *out, const ldns_output_format *fmt,
 947                ldns_dnssec_zone *zone)
 948 {
 949         if (zone) {
 950                 if (zone->soa) {
 951                         if ((fmt->flags & LDNS_COMMENT_LAYOUT)) {
 952                                 fprintf(out, ";; Zone: ");
 953                                 ldns_rdf_print(out, ldns_dnssec_name_name(
 954                                                         zone->soa));
 955                                 fprintf(out, "\n;\n");
 956                         }
 957                         ldns_dnssec_rrsets_print_fmt(out, fmt,
 958                                         ldns_dnssec_name_find_rrset(
 959                                                 zone->soa,
 960                                                 LDNS_RR_TYPE_SOA),
 961                                         false);
 962                         if ((fmt->flags & LDNS_COMMENT_LAYOUT))
 963                                 fprintf(out, ";\n");
 964                 }
 965
 966                 if (zone->names) {
 967                         ldns_dnssec_zone_names_print_fmt(out, fmt,
 968                                         zone->names, false);
 969                 }
 970         }
 971 }
 972
 973 void
 974 ldns_dnssec_zone_print(FILE *out, ldns_dnssec_zone *zone)
 975 {
 976         ldns_dnssec_zone_print_fmt(out, ldns_output_format_default, zone);
 977 }
 978
 979 ldns_status
 980 ldns_dnssec_zone_add_empty_nonterminals(ldns_dnssec_zone *zone)
 981 {
 982         ldns_dnssec_name *new_name;
 983         ldns_rdf *cur_name;
 984         ldns_rdf *next_name;
 985         ldns_rbnode_t *cur_node, *next_node, *new_node;
 986
 987         /* for the detection */
 988         uint16_t i, cur_label_count, next_label_count;
 989         uint16_t soa_label_count = 0;
 990         ldns_rdf *l1, *l2;
 991         int lpos;
 992
 993         if (!zone) {
 994                 return LDNS_STATUS_ERR;
 995         }
 996         if (zone->soa && zone->soa->name) {
 997                 soa_label_count = ldns_dname_label_count(zone->soa->name);
 998         }
 999
1000         cur_node = ldns_rbtree_first(zone->names);
1001         while (cur_node != LDNS_RBTREE_NULL) {
1002                 next_node = ldns_rbtree_next(cur_node);
1003
1004                 /* skip glue */
1005                 while (next_node != LDNS_RBTREE_NULL &&
1006                        next_node->data &&
1007                        ((ldns_dnssec_name *)next_node->data)->is_glue
1008                 ) {
1009                         next_node = ldns_rbtree_next(next_node);
1010                 }
1011
1012                 if (next_node == LDNS_RBTREE_NULL) {
1013                         next_node = ldns_rbtree_first(zone->names);
1014                 }
1015                 if (! cur_node->data || ! next_node->data) {
1016                         return LDNS_STATUS_ERR;
1017                 }
1018                 cur_name = ((ldns_dnssec_name *)cur_node->data)->name;
1019                 next_name = ((ldns_dnssec_name *)next_node->data)->name;
1020                 cur_label_count = ldns_dname_label_count(cur_name);
1021                 next_label_count = ldns_dname_label_count(next_name);
1022
1023                 /* Since the names are in canonical order, we can
1024                  * recognize empty non-terminals by their labels;
1025                  * every label after the first one on the next owner
1026                  * name is a non-terminal if it either does not exist
1027                  * in the current name or is different from the same
1028                  * label in the current name (counting from the end)
1029                  */
1030                 for (i = 1; i < next_label_count - soa_label_count; i++) {
1031                         lpos = (int)cur_label_count - (int)next_label_count + (int)i;
1032                         if (lpos >= 0) {
1033                                 l1 = ldns_dname_clone_from(cur_name, (uint8_t)lpos);
1034                         } else {
1035                                 l1 = NULL;
1036                         }
1037                         l2 = ldns_dname_clone_from(next_name, i);
1038
1039                         if (!l1 || ldns_dname_compare(l1, l2) != 0) {
1040                                 /* We have an empty nonterminal, add it to the
1041                                  * tree
1042                                  */
1043                                 new_name = ldns_dnssec_name_new();
1044                                 if (!new_name) {
1045                                         return LDNS_STATUS_MEM_ERR;
1046                                 }
1047                                 new_name->name = ldns_dname_clone_from(next_name,
1048                                                                        i);
1049                                 if (!new_name->name) {
1050                                         ldns_dnssec_name_free(new_name);
1051                                         return LDNS_STATUS_MEM_ERR;
1052                                 }
1053                                 new_name->name_alloced = true;
1054                                 new_node = LDNS_MALLOC(ldns_rbnode_t);
1055                                 if (!new_node) {
1056                                         ldns_dnssec_name_free(new_name);
1057                                         return LDNS_STATUS_MEM_ERR;
1058                                 }
1059                                 new_node->key = new_name->name;
1060                                 new_node->data = new_name;
1061                                 (void)ldns_rbtree_insert(zone->names, new_node);
1062                         }
1063                         ldns_rdf_deep_free(l1);
1064                         ldns_rdf_deep_free(l2);
1065                 }
1066
1067                 /* we might have inserted a new node after
1068                  * the current one so we can't just use next()
1069                  */
1070                 if (next_node != ldns_rbtree_first(zone->names)) {
1071                         cur_node = next_node;
1072                 } else {
1073                         cur_node = LDNS_RBTREE_NULL;
1074                 }
1075         }
1076         return LDNS_STATUS_OK;
1077 }
1078
1079 bool
1080 ldns_dnssec_zone_is_nsec3_optout(ldns_dnssec_zone* zone)
1081 {
1082         ldns_rr* nsec3;
1083         ldns_rbnode_t* node;
1084
1085         if (ldns_dnssec_name_find_rrset(zone->soa, LDNS_RR_TYPE_NSEC3PARAM)) {
1086                 node = ldns_rbtree_first(zone->names);
1087                 while (node != LDNS_RBTREE_NULL) {
1088                         nsec3 = ((ldns_dnssec_name*)node->data)->nsec;
1089                         if (nsec3 &&ldns_rr_get_type(nsec3)
1090                                         == LDNS_RR_TYPE_NSEC3 &&
1091                                         ldns_nsec3_optout(nsec3)) {
1092                                 return true;
1093                         }
1094                         node = ldns_rbtree_next(node);
1095                 }
1096         }
1097         return false;
1098 }