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