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, rr);
  58         if (cmp < 0) {
  59                 if (rrs->next) {
  60                         return ldns_dnssec_rrs_add_rr(rrs->next, rr);
  61                 } else {
  62                         new_rrs = ldns_dnssec_rrs_new();
  63                         new_rrs->rr = rr;
  64                         rrs->next = new_rrs;
  65                 }
  66         } else if (cmp > 0) {
  67                 /* put the current old rr in the new next, put the new
  68                    rr in the current container */
  69                 new_rrs = ldns_dnssec_rrs_new();
  70                 new_rrs->rr = rrs->rr;
  71                 new_rrs->next = rrs->next;
  72                 rrs->rr = rr;
  73                 rrs->next = new_rrs;
  74         }
  75         /* Silently ignore equal rr's */
  76         return LDNS_STATUS_OK;
  77 }
  78
  79 void
  80 ldns_dnssec_rrs_print_fmt(FILE *out, const ldns_output_format *fmt,
  81                const ldns_dnssec_rrs *rrs)
  82 {
  83         if (!rrs) {
  84                 if ((fmt->flags & LDNS_COMMENT_LAYOUT))
  85                         fprintf(out, "; <void>");
  86         } else {
  87                 if (rrs->rr) {
  88                         ldns_rr_print_fmt(out, fmt, rrs->rr);
  89                 }
  90                 if (rrs->next) {
  91                         ldns_dnssec_rrs_print_fmt(out, fmt, rrs->next);
  92                 }
  93         }
  94 }
  95
  96 void
  97 ldns_dnssec_rrs_print(FILE *out, const ldns_dnssec_rrs *rrs)
  98 {
  99         ldns_dnssec_rrs_print_fmt(out, ldns_output_format_default, rrs);
 100 }
 101
 102
 103 ldns_dnssec_rrsets *
 104 ldns_dnssec_rrsets_new(void)
 105 {
 106         ldns_dnssec_rrsets *new_rrsets;
 107         new_rrsets = LDNS_MALLOC(ldns_dnssec_rrsets);
 108         if(!new_rrsets) return NULL;
 109         new_rrsets->rrs = NULL;
 110         new_rrsets->type = 0;
 111         new_rrsets->signatures = NULL;
 112         new_rrsets->next = NULL;
 113         return new_rrsets;
 114 }
 115
 116 INLINE void
 117 ldns_dnssec_rrsets_free_internal(ldns_dnssec_rrsets *rrsets, int deep)
 118 {
 119         if (rrsets) {
 120                 if (rrsets->rrs) {
 121                         ldns_dnssec_rrs_free_internal(rrsets->rrs, deep);
 122                 }
 123                 if (rrsets->next) {
 124                         ldns_dnssec_rrsets_free_internal(rrsets->next, deep);
 125                 }
 126                 if (rrsets->signatures) {
 127                         ldns_dnssec_rrs_free_internal(rrsets->signatures, deep);
 128                 }
 129                 LDNS_FREE(rrsets);
 130         }
 131 }
 132
 133 void
 134 ldns_dnssec_rrsets_free(ldns_dnssec_rrsets *rrsets)
 135 {
 136         ldns_dnssec_rrsets_free_internal(rrsets, 0);
 137 }
 138
 139 void
 140 ldns_dnssec_rrsets_deep_free(ldns_dnssec_rrsets *rrsets)
 141 {
 142         ldns_dnssec_rrsets_free_internal(rrsets, 1);
 143 }
 144
 145 ldns_rr_type
 146 ldns_dnssec_rrsets_type(const ldns_dnssec_rrsets *rrsets)
 147 {
 148         if (rrsets) {
 149                 return rrsets->type;
 150         } else {
 151                 return 0;
 152         }
 153 }
 154
 155 ldns_status
 156 ldns_dnssec_rrsets_set_type(ldns_dnssec_rrsets *rrsets,
 157                                            ldns_rr_type type)
 158 {
 159         if (rrsets) {
 160                 rrsets->type = type;
 161                 return LDNS_STATUS_OK;
 162         }
 163         return LDNS_STATUS_ERR;
 164 }
 165
 166 static ldns_dnssec_rrsets *
 167 ldns_dnssec_rrsets_new_frm_rr(ldns_rr *rr)
 168 {
 169         ldns_dnssec_rrsets *new_rrsets;
 170         ldns_rr_type rr_type;
 171         bool rrsig;
 172
 173         new_rrsets = ldns_dnssec_rrsets_new();
 174         rr_type = ldns_rr_get_type(rr);
 175         if (rr_type == LDNS_RR_TYPE_RRSIG) {
 176                 rrsig = true;
 177                 rr_type = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr));
 178         } else {
 179                 rrsig = false;
 180         }
 181         if (!rrsig) {
 182                 new_rrsets->rrs = ldns_dnssec_rrs_new();
 183                 new_rrsets->rrs->rr = rr;
 184         } else {
 185                 new_rrsets->signatures = ldns_dnssec_rrs_new();
 186                 new_rrsets->signatures->rr = rr;
 187         }
 188         new_rrsets->type = rr_type;
 189         return new_rrsets;
 190 }
 191
 192 ldns_status
 193 ldns_dnssec_rrsets_add_rr(ldns_dnssec_rrsets *rrsets, ldns_rr *rr)
 194 {
 195         ldns_dnssec_rrsets *new_rrsets;
 196         ldns_rr_type rr_type;
 197         bool rrsig = false;
 198         ldns_status result = LDNS_STATUS_OK;
 199
 200         if (!rrsets || !rr) {
 201                 return LDNS_STATUS_ERR;
 202         }
 203
 204         rr_type = ldns_rr_get_type(rr);
 205
 206         if (rr_type == LDNS_RR_TYPE_RRSIG) {
 207                 rrsig = true;
 208                 rr_type = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr));
 209         }
 210
 211         if (!rrsets->rrs && rrsets->type == 0 && !rrsets->signatures) {
 212                 if (!rrsig) {
 213                         rrsets->rrs = ldns_dnssec_rrs_new();
 214                         rrsets->rrs->rr = rr;
 215                         rrsets->type = rr_type;
 216                 } else {
 217                         rrsets->signatures = ldns_dnssec_rrs_new();
 218                         rrsets->signatures->rr = rr;
 219                         rrsets->type = rr_type;
 220                 }
 221                 return LDNS_STATUS_OK;
 222         }
 223
 224         if (rr_type > ldns_dnssec_rrsets_type(rrsets)) {
 225                 if (rrsets->next) {
 226                         result = ldns_dnssec_rrsets_add_rr(rrsets->next, rr);
 227                 } else {
 228                         new_rrsets = ldns_dnssec_rrsets_new_frm_rr(rr);
 229                         rrsets->next = new_rrsets;
 230                 }
 231         } else if (rr_type < ldns_dnssec_rrsets_type(rrsets)) {
 232                 /* move the current one into the new next,
 233                    replace field of current with data from new rr */
 234                 new_rrsets = ldns_dnssec_rrsets_new();
 235                 new_rrsets->rrs = rrsets->rrs;
 236                 new_rrsets->type = rrsets->type;
 237                 new_rrsets->signatures = rrsets->signatures;
 238                 new_rrsets->next = rrsets->next;
 239                 if (!rrsig) {
 240                         rrsets->rrs = ldns_dnssec_rrs_new();
 241                         rrsets->rrs->rr = rr;
 242                         rrsets->signatures = NULL;
 243                 } else {
 244                         rrsets->rrs = NULL;
 245                         rrsets->signatures = ldns_dnssec_rrs_new();
 246                         rrsets->signatures->rr = rr;
 247                 }
 248                 rrsets->type = rr_type;
 249                 rrsets->next = new_rrsets;
 250         } else {
 251                 /* equal, add to current rrsets */
 252                 if (rrsig) {
 253                         if (rrsets->signatures) {
 254                                 result = ldns_dnssec_rrs_add_rr(rrsets->signatures, rr);
 255                         } else {
 256                                 rrsets->signatures = ldns_dnssec_rrs_new();
 257                                 rrsets->signatures->rr = rr;
 258                         }
 259                 } else {
 260                         if (rrsets->rrs) {
 261                                 result = ldns_dnssec_rrs_add_rr(rrsets->rrs, rr);
 262                         } else {
 263                                 rrsets->rrs = ldns_dnssec_rrs_new();
 264                                 rrsets->rrs->rr = rr;
 265                         }
 266                 }
 267         }
 268
 269         return result;
 270 }
 271
 272 static void
 273 ldns_dnssec_rrsets_print_soa_fmt(FILE *out, const ldns_output_format *fmt,
 274                 const ldns_dnssec_rrsets *rrsets,
 275                 bool follow,
 276                 bool show_soa)
 277 {
 278         if (!rrsets) {
 279                 if ((fmt->flags & LDNS_COMMENT_LAYOUT))
 280                         fprintf(out, "; <void>\n");
 281         } else {
 282                 if (rrsets->rrs &&
 283                     (show_soa ||
 284                         ldns_rr_get_type(rrsets->rrs->rr) != LDNS_RR_TYPE_SOA
 285                     )
 286                    ) {
 287                         ldns_dnssec_rrs_print_fmt(out, fmt, rrsets->rrs);
 288                         if (rrsets->signatures) {
 289                                 ldns_dnssec_rrs_print_fmt(out, fmt,
 290                                                 rrsets->signatures);
 291                         }
 292                 }
 293                 if (follow && rrsets->next) {
 294                         ldns_dnssec_rrsets_print_soa_fmt(out, fmt,
 295                                         rrsets->next, follow, show_soa);
 296                 }
 297         }
 298 }
 299
 300
 301 void
 302 ldns_dnssec_rrsets_print_fmt(FILE *out, const ldns_output_format *fmt,
 303                 const ldns_dnssec_rrsets *rrsets,
 304                 bool follow)
 305 {
 306         ldns_dnssec_rrsets_print_soa_fmt(out, fmt, rrsets, follow, true);
 307 }
 308
 309 void
 310 ldns_dnssec_rrsets_print(FILE *out, const ldns_dnssec_rrsets *rrsets, bool follow)
 311 {
 312         ldns_dnssec_rrsets_print_fmt(out, ldns_output_format_default,
 313                         rrsets, follow);
 314 }
 315
 316 ldns_dnssec_name *
 317 ldns_dnssec_name_new(void)
 318 {
 319         ldns_dnssec_name *new_name;
 320
 321         new_name = LDNS_CALLOC(ldns_dnssec_name, 1);
 322         if (!new_name) {
 323                 return NULL;
 324         }
 325         /*
 326          * not needed anymore because CALLOC initalizes everything to zero.
 327
 328         new_name->name = NULL;
 329         new_name->rrsets = NULL;
 330         new_name->name_alloced = false;
 331         new_name->nsec = NULL;
 332         new_name->nsec_signatures = NULL;
 333
 334         new_name->is_glue = false;
 335         new_name->hashed_name = NULL;
 336
 337          */
 338         return new_name;
 339 }
 340
 341 ldns_dnssec_name *
 342 ldns_dnssec_name_new_frm_rr(ldns_rr *rr)
 343 {
 344         ldns_dnssec_name *new_name = ldns_dnssec_name_new();
 345
 346         new_name->name = ldns_rr_owner(rr);
 347         if(ldns_dnssec_name_add_rr(new_name, rr) != LDNS_STATUS_OK) {
 348                 ldns_dnssec_name_free(new_name);
 349                 return NULL;
 350         }
 351
 352         return new_name;
 353 }
 354
 355 INLINE void
 356 ldns_dnssec_name_free_internal(ldns_dnssec_name *name,
 357                                int deep)
 358 {
 359         if (name) {
 360                 if (name->name_alloced) {
 361                         ldns_rdf_deep_free(name->name);
 362                 }
 363                 if (name->rrsets) {
 364                         ldns_dnssec_rrsets_free_internal(name->rrsets, deep);
 365                 }
 366                 if (name->nsec && deep) {
 367                         ldns_rr_free(name->nsec);
 368                 }
 369                 if (name->nsec_signatures) {
 370                         ldns_dnssec_rrs_free_internal(name->nsec_signatures, deep);
 371                 }
 372                 if (name->hashed_name) {
 373                         if (deep) {
 374                                 ldns_rdf_deep_free(name->hashed_name);
 375                         }
 376                 }
 377                 LDNS_FREE(name);
 378         }
 379 }
 380
 381 void
 382 ldns_dnssec_name_free(ldns_dnssec_name *name)
 383 {
 384   ldns_dnssec_name_free_internal(name, 0);
 385 }
 386
 387 void
 388 ldns_dnssec_name_deep_free(ldns_dnssec_name *name)
 389 {
 390   ldns_dnssec_name_free_internal(name, 1);
 391 }
 392
 393 ldns_rdf *
 394 ldns_dnssec_name_name(const ldns_dnssec_name *name)
 395 {
 396         if (name) {
 397                 return name->name;
 398         }
 399         return NULL;
 400 }
 401
 402 bool
 403 ldns_dnssec_name_is_glue(const ldns_dnssec_name *name)
 404 {
 405         if (name) {
 406                 return name->is_glue;
 407         }
 408         return false;
 409 }
 410
 411 void
 412 ldns_dnssec_name_set_name(ldns_dnssec_name *rrset,
 413                                          ldns_rdf *dname)
 414 {
 415         if (rrset && dname) {
 416                 rrset->name = dname;
 417         }
 418 }
 419
 420
 421 void
 422 ldns_dnssec_name_set_nsec(ldns_dnssec_name *rrset, ldns_rr *nsec)
 423 {
 424         if (rrset && nsec) {
 425                 rrset->nsec = nsec;
 426         }
 427 }
 428
 429 int
 430 ldns_dnssec_name_cmp(const void *a, const void *b)
 431 {
 432         ldns_dnssec_name *na = (ldns_dnssec_name *) a;
 433         ldns_dnssec_name *nb = (ldns_dnssec_name *) b;
 434
 435         if (na && nb) {
 436                 return ldns_dname_compare(ldns_dnssec_name_name(na),
 437                                                          ldns_dnssec_name_name(nb));
 438         } else if (na) {
 439                 return 1;
 440         } else if (nb) {
 441                 return -1;
 442         } else {
 443                 return 0;
 444         }
 445 }
 446
 447 ldns_status
 448 ldns_dnssec_name_add_rr(ldns_dnssec_name *name,
 449                                     ldns_rr *rr)
 450 {
 451         ldns_status result = LDNS_STATUS_OK;
 452         ldns_rr_type rr_type;
 453         ldns_rr_type typecovered = 0;
 454
 455         /* special handling for NSEC3 and NSECX covering RRSIGS */
 456
 457         if (!name || !rr) {
 458                 return LDNS_STATUS_ERR;
 459         }
 460
 461         rr_type = ldns_rr_get_type(rr);
 462
 463         if (rr_type == LDNS_RR_TYPE_RRSIG) {
 464                 typecovered = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr));
 465         }
 466
 467         if (rr_type == LDNS_RR_TYPE_NSEC ||
 468             rr_type == LDNS_RR_TYPE_NSEC3) {
 469                 /* XX check if is already set (and error?) */
 470                 name->nsec = rr;
 471         } else if (typecovered == LDNS_RR_TYPE_NSEC ||
 472                          typecovered == LDNS_RR_TYPE_NSEC3) {
 473                 if (name->nsec_signatures) {
 474                         result = ldns_dnssec_rrs_add_rr(name->nsec_signatures, rr);
 475                 } else {
 476                         name->nsec_signatures = ldns_dnssec_rrs_new();
 477                         name->nsec_signatures->rr = rr;
 478                 }
 479         } else {
 480                 /* it's a 'normal' RR, add it to the right rrset */
 481                 if (name->rrsets) {
 482                         result = ldns_dnssec_rrsets_add_rr(name->rrsets, rr);
 483                 } else {
 484                         name->rrsets = ldns_dnssec_rrsets_new();
 485                         result = ldns_dnssec_rrsets_add_rr(name->rrsets, rr);
 486                 }
 487         }
 488         return result;
 489 }
 490
 491 ldns_dnssec_rrsets *
 492 ldns_dnssec_name_find_rrset(const ldns_dnssec_name *name,
 493                                            ldns_rr_type type) {
 494         ldns_dnssec_rrsets *result;
 495
 496         result = name->rrsets;
 497         while (result) {
 498                 if (result->type == type) {
 499                         return result;
 500                 } else {
 501                         result = result->next;
 502                 }
 503         }
 504         return NULL;
 505 }
 506
 507 ldns_dnssec_rrsets *
 508 ldns_dnssec_zone_find_rrset(const ldns_dnssec_zone *zone,
 509                                            const ldns_rdf *dname,
 510                                            ldns_rr_type type)
 511 {
 512         ldns_rbnode_t *node;
 513
 514         if (!zone || !dname || !zone->names) {
 515                 return NULL;
 516         }
 517
 518         node = ldns_rbtree_search(zone->names, dname);
 519         if (node) {
 520                 return ldns_dnssec_name_find_rrset((ldns_dnssec_name *)node->data,
 521                                                                         type);
 522         } else {
 523                 return NULL;
 524         }
 525 }
 526
 527 static void
 528 ldns_dnssec_name_print_soa_fmt(FILE *out, const ldns_output_format *fmt,
 529                 const ldns_dnssec_name *name,
 530                 bool show_soa)
 531 {
 532         if (name) {
 533                 if(name->rrsets) {
 534                         ldns_dnssec_rrsets_print_soa_fmt(out, fmt,
 535                                         name->rrsets, true, show_soa);
 536                 } else if ((fmt->flags & LDNS_COMMENT_LAYOUT)) {
 537                         fprintf(out, ";; Empty nonterminal: ");
 538                         ldns_rdf_print(out, name->name);
 539                         fprintf(out, "\n");
 540                 }
 541                 if(name->nsec) {
 542                         ldns_rr_print_fmt(out, fmt, name->nsec);
 543                 }
 544                 if (name->nsec_signatures) {
 545                         ldns_dnssec_rrs_print_fmt(out, fmt,
 546                                         name->nsec_signatures);
 547                 }
 548         } else if ((fmt->flags & LDNS_COMMENT_LAYOUT)) {
 549                 fprintf(out, "; <void>\n");
 550         }
 551 }
 552
 553
 554 void
 555 ldns_dnssec_name_print_fmt(FILE *out, const ldns_output_format *fmt,
 556                 const ldns_dnssec_name *name)
 557 {
 558         ldns_dnssec_name_print_soa_fmt(out, fmt, name, true);
 559 }
 560
 561 void
 562 ldns_dnssec_name_print(FILE *out, const ldns_dnssec_name *name)
 563 {
 564         ldns_dnssec_name_print_fmt(out, ldns_output_format_default, name);
 565 }
 566
 567
 568 ldns_dnssec_zone *
 569 ldns_dnssec_zone_new(void)
 570 {
 571         ldns_dnssec_zone *zone = LDNS_MALLOC(ldns_dnssec_zone);
 572         if(!zone) return NULL;
 573         zone->soa = NULL;
 574         zone->names = NULL;
 575         zone->hashed_names = NULL;
 576         zone->_nsec3params = NULL;
 577
 578         return zone;
 579 }
 580
 581 static bool
 582 rr_is_rrsig_covering(ldns_rr* rr, ldns_rr_type t)
 583 {
 584         return     ldns_rr_get_type(rr) == LDNS_RR_TYPE_RRSIG
 585                 && ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr)) == t;
 586 }
 587
 588 /* When the zone is first read into an list and then inserted into an
 589  * ldns_dnssec_zone (rbtree) the nodes of the rbtree are allocated close (next)
 590  * to each other. Because ldns-verify-zone (the only program that uses this
 591  * function) uses the rbtree mostly for sequentual walking, this results
 592  * in a speed increase (of 15% on linux) because we have less CPU-cache misses.
 593  */
 594 #define FASTER_DNSSEC_ZONE_NEW_FRM_FP 1 /* Because of L2 cache efficiency */
 595
 596 static ldns_status
 597 ldns_dnssec_zone_add_empty_nonterminals_nsec3(
 598                 ldns_dnssec_zone *zone, ldns_rbtree_t *nsec3s);
 599
 600 static void
 601 ldns_todo_nsec3_ents_node_free(ldns_rbnode_t *node, void *arg) {
 602         (void) arg;
 603         ldns_rdf_deep_free((ldns_rdf *)node->key);
 604         LDNS_FREE(node);
 605 }
 606
 607 ldns_status
 608 ldns_dnssec_zone_new_frm_fp_l(ldns_dnssec_zone** z, FILE* fp, const ldns_rdf* origin,
 609                 uint32_t ttl, ldns_rr_class ATTR_UNUSED(c), int* line_nr)
 610 {
 611         ldns_rr* cur_rr;
 612         size_t i;
 613
 614         ldns_rdf *my_origin = NULL;
 615         ldns_rdf *my_prev = NULL;
 616
 617         ldns_dnssec_zone *newzone = ldns_dnssec_zone_new();
 618         /* NSEC3s may occur before the names they refer to. We must remember
 619            them and add them to the name later on, after the name is read.
 620            We track not yet  matching NSEC3s*n the todo_nsec3s list */
 621         ldns_rr_list* todo_nsec3s = ldns_rr_list_new();
 622         /* when reading NSEC3s, there is a chance that we encounter nsecs
 623            for empty nonterminals, whose nonterminals we cannot derive yet
 624            because the needed information is to be read later.
 625
 626            nsec3_ents (where ent is e.n.t.; i.e. empty non terminal) will
 627            hold the NSEC3s that still didn't have a matching name in the
 628            zone tree, even after all names were read.  They can only match
 629            after the zone is equiped with all the empty non terminals. */
 630         ldns_rbtree_t todo_nsec3_ents;
 631         ldns_rbnode_t *new_node;
 632         ldns_rr_list* todo_nsec3_rrsigs = ldns_rr_list_new();
 633
 634         ldns_status status;
 635
 636 #ifdef FASTER_DNSSEC_ZONE_NEW_FRM_FP
 637         ldns_zone* zone = NULL;
 638 #else
 639         uint32_t  my_ttl = ttl;
 640 #endif
 641
 642         ldns_rbtree_init(&todo_nsec3_ents, ldns_dname_compare_v);
 643
 644 #ifdef FASTER_DNSSEC_ZONE_NEW_FRM_FP
 645         status = ldns_zone_new_frm_fp_l(&zone, fp, origin,ttl, c, line_nr);
 646         if (status != LDNS_STATUS_OK)
 647                 goto error;
 648 #endif
 649         if (!newzone || !todo_nsec3s || !todo_nsec3_rrsigs ) {
 650                 status = LDNS_STATUS_MEM_ERR;
 651                 goto error;
 652         }
 653         if (origin) {
 654                 if (!(my_origin = ldns_rdf_clone(origin))) {
 655                         status = LDNS_STATUS_MEM_ERR;
 656                         goto error;
 657                 }
 658                 if (!(my_prev   = ldns_rdf_clone(origin))) {
 659                         status = LDNS_STATUS_MEM_ERR;
 660                         goto error;
 661                 }
 662         }
 663
 664 #ifdef FASTER_DNSSEC_ZONE_NEW_FRM_FP
 665         if (ldns_zone_soa(zone)) {
 666                 status = ldns_dnssec_zone_add_rr(newzone, ldns_zone_soa(zone));
 667                 if (status != LDNS_STATUS_OK)
 668                         goto error;
 669         }
 670         for (i = 0; i < ldns_rr_list_rr_count(ldns_zone_rrs(zone)); i++) {
 671                 cur_rr = ldns_rr_list_rr(ldns_zone_rrs(zone), i);
 672                 status = LDNS_STATUS_OK;
 673 #else
 674         while (!feof(fp)) {
 675                 status = ldns_rr_new_frm_fp_l(&cur_rr, fp, &my_ttl, &my_origin,
 676                                 &my_prev, line_nr);
 677
 678 #endif
 679                 switch (status) {
 680                 case LDNS_STATUS_OK:
 681
 682                         status = ldns_dnssec_zone_add_rr(newzone, cur_rr);
 683                         if (status ==
 684                                 LDNS_STATUS_DNSSEC_NSEC3_ORIGINAL_NOT_FOUND) {
 685
 686                                 if (rr_is_rrsig_covering(cur_rr,
 687                                                         LDNS_RR_TYPE_NSEC3)){
 688                                         ldns_rr_list_push_rr(todo_nsec3_rrsigs,
 689                                                         cur_rr);
 690                                 } else {
 691                                         ldns_rr_list_push_rr(todo_nsec3s,
 692                                                         cur_rr);
 693                                 }
 694                                 status = LDNS_STATUS_OK;
 695
 696                         } else if (status != LDNS_STATUS_OK)
 697                                 goto error;
 698
 699                         break;
 700
 701
 702                 case LDNS_STATUS_SYNTAX_EMPTY:  /* empty line was seen */
 703                 case LDNS_STATUS_SYNTAX_TTL:    /* the ttl was set*/
 704                 case LDNS_STATUS_SYNTAX_ORIGIN: /* the origin was set*/
 705                         status = LDNS_STATUS_OK;
 706                         break;
 707
 708                 case LDNS_STATUS_SYNTAX_INCLUDE:/* $include not implemented */
 709                         status =  LDNS_STATUS_SYNTAX_INCLUDE_ERR_NOTIMPL;
 710                         break;
 711
 712                 default:
 713                         goto error;
 714                 }
 715         }
 716
 717         for (i = 0; status == LDNS_STATUS_OK &&
 718                         i < ldns_rr_list_rr_count(todo_nsec3s); i++) {
 719                 cur_rr = ldns_rr_list_rr(todo_nsec3s, i);
 720                 status = ldns_dnssec_zone_add_rr(newzone, cur_rr);
 721                 if (status == LDNS_STATUS_DNSSEC_NSEC3_ORIGINAL_NOT_FOUND) {
 722                         if (!(new_node = LDNS_MALLOC(ldns_rbnode_t))) {
 723                                 status = LDNS_STATUS_MEM_ERR;
 724                                 break;
 725                         }
 726                         new_node->key  = ldns_dname_label(ldns_rr_owner(cur_rr), 0);
 727                         new_node->data = cur_rr;
 728                         if (!ldns_rbtree_insert(&todo_nsec3_ents, new_node)) {
 729                                 LDNS_FREE(new_node);
 730                                 status = LDNS_STATUS_MEM_ERR;
 731                                 break;
 732                         }
 733                         status = LDNS_STATUS_OK;
 734                 }
 735         }
 736         if (todo_nsec3_ents.count > 0)
 737                 (void) ldns_dnssec_zone_add_empty_nonterminals_nsec3(
 738                                 newzone, &todo_nsec3_ents);
 739         for (i = 0; status == LDNS_STATUS_OK &&
 740                         i < ldns_rr_list_rr_count(todo_nsec3_rrsigs); i++) {
 741                 cur_rr = ldns_rr_list_rr(todo_nsec3_rrsigs, i);
 742                 status = ldns_dnssec_zone_add_rr(newzone, cur_rr);
 743         }
 744         if (z) {
 745                 *z = newzone;
 746                 newzone = NULL;
 747         } else {
 748                 ldns_dnssec_zone_free(newzone);
 749         }
 750
 751 error:
 752 #ifdef FASTER_DNSSEC_ZONE_NEW_FRM_FP
 753         if (zone) {
 754                 ldns_zone_free(zone);
 755         }
 756 #endif
 757         ldns_rr_list_free(todo_nsec3_rrsigs);
 758         ldns_traverse_postorder(&todo_nsec3_ents,
 759                         ldns_todo_nsec3_ents_node_free, NULL);
 760         ldns_rr_list_free(todo_nsec3s);
 761
 762         if (my_origin) {
 763                 ldns_rdf_deep_free(my_origin);
 764         }
 765         if (my_prev) {
 766                 ldns_rdf_deep_free(my_prev);
 767         }
 768         if (newzone) {
 769                 ldns_dnssec_zone_free(newzone);
 770         }
 771         return status;
 772 }
 773
 774 ldns_status
 775 ldns_dnssec_zone_new_frm_fp(ldns_dnssec_zone** z, FILE* fp, const ldns_rdf* origin,
 776                 uint32_t ttl, ldns_rr_class ATTR_UNUSED(c))
 777 {
 778         return ldns_dnssec_zone_new_frm_fp_l(z, fp, origin, ttl, c, NULL);
 779 }
 780
 781 static void
 782 ldns_dnssec_name_node_free(ldns_rbnode_t *node, void *arg) {
 783         (void) arg;
 784         ldns_dnssec_name_free((ldns_dnssec_name *)node->data);
 785         LDNS_FREE(node);
 786 }
 787
 788 static void
 789 ldns_dnssec_name_node_deep_free(ldns_rbnode_t *node, void *arg) {
 790         (void) arg;
 791         ldns_dnssec_name_deep_free((ldns_dnssec_name *)node->data);
 792         LDNS_FREE(node);
 793 }
 794
 795 void
 796 ldns_dnssec_zone_free(ldns_dnssec_zone *zone)
 797 {
 798         if (zone) {
 799                 if (zone->names) {
 800                         /* destroy all name structures within the tree */
 801                         ldns_traverse_postorder(zone->names,
 802                                                     ldns_dnssec_name_node_free,
 803                                                     NULL);
 804                         LDNS_FREE(zone->names);
 805                 }
 806                 LDNS_FREE(zone);
 807         }
 808 }
 809
 810 void
 811 ldns_dnssec_zone_deep_free(ldns_dnssec_zone *zone)
 812 {
 813         if (zone) {
 814                 if (zone->names) {
 815                         /* destroy all name structures within the tree */
 816                         ldns_traverse_postorder(zone->names,
 817                                                     ldns_dnssec_name_node_deep_free,
 818                                                     NULL);
 819                         LDNS_FREE(zone->names);
 820                 }
 821                 LDNS_FREE(zone);
 822         }
 823 }
 824
 825 /* use for dname comparison in tree */
 826 int
 827 ldns_dname_compare_v(const void *a, const void *b) {
 828         return ldns_dname_compare((ldns_rdf *)a, (ldns_rdf *)b);
 829 }
 830
 831 static void
 832 ldns_dnssec_name_make_hashed_name(ldns_dnssec_zone *zone,
 833                 ldns_dnssec_name* name, ldns_rr* nsec3rr);
 834
 835 static void
 836 ldns_hashed_names_node_free(ldns_rbnode_t *node, void *arg) {
 837         (void) arg;
 838         LDNS_FREE(node);
 839 }
 840
 841 static void
 842 ldns_dnssec_zone_hashed_names_from_nsec3(
 843                 ldns_dnssec_zone* zone, ldns_rr* nsec3rr)
 844 {
 845         ldns_rbnode_t* current_node;
 846         ldns_dnssec_name* current_name;
 847
 848         assert(zone != NULL);
 849         assert(nsec3rr != NULL);
 850
 851         if (zone->hashed_names) {
 852                 ldns_traverse_postorder(zone->hashed_names,
 853                                 ldns_hashed_names_node_free, NULL);
 854                 LDNS_FREE(zone->hashed_names);
 855         }
 856         zone->_nsec3params = nsec3rr;
 857
 858         /* So this is a NSEC3 zone.
 859         * Calculate hashes for all names already in the zone
 860         */
 861         zone->hashed_names = ldns_rbtree_create(ldns_dname_compare_v);
 862         if (zone->hashed_names == NULL) {
 863                 return;
 864         }
 865         for ( current_node  = ldns_rbtree_first(zone->names)
 866             ; current_node != LDNS_RBTREE_NULL
 867             ; current_node  = ldns_rbtree_next(current_node)
 868             ) {
 869                 current_name = (ldns_dnssec_name *) current_node->data;
 870                 ldns_dnssec_name_make_hashed_name(zone, current_name, nsec3rr);
 871
 872         }
 873 }
 874
 875 static void
 876 ldns_dnssec_name_make_hashed_name(ldns_dnssec_zone *zone,
 877                 ldns_dnssec_name* name, ldns_rr* nsec3rr)
 878 {
 879         ldns_rbnode_t* new_node;
 880
 881         assert(name != NULL);
 882         if (! zone->_nsec3params) {
 883                 if (! nsec3rr) {
 884                         return;
 885                 }
 886                 ldns_dnssec_zone_hashed_names_from_nsec3(zone, nsec3rr);
 887
 888         } else if (! nsec3rr) {
 889                 nsec3rr = zone->_nsec3params;
 890         }
 891         name->hashed_name = ldns_nsec3_hash_name_frm_nsec3(nsec3rr, name->name);
 892
 893         /* Also store in zone->hashed_names */
 894         if ((new_node = LDNS_MALLOC(ldns_rbnode_t))) {
 895
 896                 new_node->key  = name->hashed_name;
 897                 new_node->data = name;
 898
 899                 if (ldns_rbtree_insert(zone->hashed_names, new_node) == NULL) {
 900
 901                                 LDNS_FREE(new_node);
 902                 }
 903         }
 904 }
 905
 906
 907 static ldns_rbnode_t *
 908 ldns_dnssec_zone_find_nsec3_original(ldns_dnssec_zone *zone, ldns_rr *rr) {
 909         ldns_rdf *hashed_name;
 910
 911         hashed_name = ldns_dname_label(ldns_rr_owner(rr), 0);
 912         if (hashed_name == NULL) {
 913                 return NULL;
 914         }
 915         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_NSEC3 && ! zone->_nsec3params){
 916
 917                 ldns_dnssec_zone_hashed_names_from_nsec3(zone, rr);
 918         }
 919         if (zone->hashed_names == NULL) {
 920                 ldns_rdf_deep_free(hashed_name);
 921                 return NULL;
 922         }
 923         return  ldns_rbtree_search(zone->hashed_names, hashed_name);
 924 }
 925
 926 ldns_status
 927 ldns_dnssec_zone_add_rr(ldns_dnssec_zone *zone, ldns_rr *rr)
 928 {
 929         ldns_status result = LDNS_STATUS_OK;
 930         ldns_dnssec_name *cur_name;
 931         ldns_rbnode_t *cur_node;
 932         ldns_rr_type type_covered = 0;
 933
 934         if (!zone || !rr) {
 935                 return LDNS_STATUS_ERR;
 936         }
 937
 938         if (!zone->names) {
 939                 zone->names = ldns_rbtree_create(ldns_dname_compare_v);
 940                 if(!zone->names) return LDNS_STATUS_MEM_ERR;
 941         }
 942
 943         /* we need the original of the hashed name if this is
 944            an NSEC3, or an RRSIG that covers an NSEC3 */
 945         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_RRSIG) {
 946                 type_covered = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr));
 947         }
 948         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_NSEC3 ||
 949             type_covered == LDNS_RR_TYPE_NSEC3) {
 950                 cur_node = ldns_dnssec_zone_find_nsec3_original(zone, rr);
 951                 if (!cur_node) {
 952                         return LDNS_STATUS_DNSSEC_NSEC3_ORIGINAL_NOT_FOUND;
 953                 }
 954         } else {
 955                 cur_node = ldns_rbtree_search(zone->names, ldns_rr_owner(rr));
 956         }
 957         if (!cur_node) {
 958                 /* add */
 959                 cur_name = ldns_dnssec_name_new_frm_rr(rr);
 960                 if(!cur_name) return LDNS_STATUS_MEM_ERR;
 961                 cur_node = LDNS_MALLOC(ldns_rbnode_t);
 962                 if(!cur_node) {
 963                         ldns_dnssec_name_free(cur_name);
 964                         return LDNS_STATUS_MEM_ERR;
 965                 }
 966                 cur_node->key = ldns_rr_owner(rr);
 967                 cur_node->data = cur_name;
 968                 (void)ldns_rbtree_insert(zone->names, cur_node);
 969                 ldns_dnssec_name_make_hashed_name(zone, cur_name, NULL);
 970         } else {
 971                 cur_name = (ldns_dnssec_name *) cur_node->data;
 972                 result = ldns_dnssec_name_add_rr(cur_name, rr);
 973         }
 974         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_SOA) {
 975                 zone->soa = cur_name;
 976         }
 977         return result;
 978 }
 979
 980 void
 981 ldns_dnssec_zone_names_print_fmt(FILE *out, const ldns_output_format *fmt,
 982                 const ldns_rbtree_t *tree,
 983                 bool print_soa)
 984 {
 985         ldns_rbnode_t *node;
 986         ldns_dnssec_name *name;
 987
 988         node = ldns_rbtree_first(tree);
 989         while (node != LDNS_RBTREE_NULL) {
 990                 name = (ldns_dnssec_name *) node->data;
 991                 ldns_dnssec_name_print_soa_fmt(out, fmt, name, print_soa);
 992                 if ((fmt->flags & LDNS_COMMENT_LAYOUT))
 993                         fprintf(out, ";\n");
 994                 node = ldns_rbtree_next(node);
 995         }
 996 }
 997
 998 void
 999 ldns_dnssec_zone_names_print(FILE *out, const ldns_rbtree_t *tree, bool print_soa)
1000 {
1001         ldns_dnssec_zone_names_print_fmt(out, ldns_output_format_default,
1002                        tree, print_soa);
1003 }
1004
1005 void
1006 ldns_dnssec_zone_print_fmt(FILE *out, const ldns_output_format *fmt,
1007                const ldns_dnssec_zone *zone)
1008 {
1009         if (zone) {
1010                 if (zone->soa) {
1011                         if ((fmt->flags & LDNS_COMMENT_LAYOUT)) {
1012                                 fprintf(out, ";; Zone: ");
1013                                 ldns_rdf_print(out, ldns_dnssec_name_name(
1014                                                         zone->soa));
1015                                 fprintf(out, "\n;\n");
1016                         }
1017                         ldns_dnssec_rrsets_print_fmt(out, fmt,
1018                                         ldns_dnssec_name_find_rrset(
1019                                                 zone->soa,
1020                                                 LDNS_RR_TYPE_SOA),
1021                                         false);
1022                         if ((fmt->flags & LDNS_COMMENT_LAYOUT))
1023                                 fprintf(out, ";\n");
1024                 }
1025
1026                 if (zone->names) {
1027                         ldns_dnssec_zone_names_print_fmt(out, fmt,
1028                                         zone->names, false);
1029                 }
1030         }
1031 }
1032
1033 void
1034 ldns_dnssec_zone_print(FILE *out, const ldns_dnssec_zone *zone)
1035 {
1036         ldns_dnssec_zone_print_fmt(out, ldns_output_format_default, zone);
1037 }
1038
1039 static ldns_status
1040 ldns_dnssec_zone_add_empty_nonterminals_nsec3(
1041                 ldns_dnssec_zone *zone, ldns_rbtree_t *nsec3s)
1042 {
1043         ldns_dnssec_name *new_name;
1044         ldns_rdf *cur_name;
1045         ldns_rdf *next_name;
1046         ldns_rbnode_t *cur_node, *next_node, *new_node;
1047
1048         /* for the detection */
1049         uint16_t i, cur_label_count, next_label_count;
1050         uint16_t soa_label_count = 0;
1051         ldns_rdf *l1, *l2;
1052         int lpos;
1053
1054         if (!zone) {
1055                 return LDNS_STATUS_ERR;
1056         }
1057         if (zone->soa && zone->soa->name) {
1058                 soa_label_count = ldns_dname_label_count(zone->soa->name);
1059         }
1060
1061         cur_node = ldns_rbtree_first(zone->names);
1062         while (cur_node != LDNS_RBTREE_NULL) {
1063                 next_node = ldns_rbtree_next(cur_node);
1064
1065                 /* skip glue */
1066                 while (next_node != LDNS_RBTREE_NULL &&
1067                        next_node->data &&
1068                        ((ldns_dnssec_name *)next_node->data)->is_glue
1069                 ) {
1070                         next_node = ldns_rbtree_next(next_node);
1071                 }
1072
1073                 if (next_node == LDNS_RBTREE_NULL) {
1074                         next_node = ldns_rbtree_first(zone->names);
1075                 }
1076                 if (! cur_node->data || ! next_node->data) {
1077                         return LDNS_STATUS_ERR;
1078                 }
1079                 cur_name = ((ldns_dnssec_name *)cur_node->data)->name;
1080                 next_name = ((ldns_dnssec_name *)next_node->data)->name;
1081                 cur_label_count = ldns_dname_label_count(cur_name);
1082                 next_label_count = ldns_dname_label_count(next_name);
1083
1084                 /* Since the names are in canonical order, we can
1085                  * recognize empty non-terminals by their labels;
1086                  * every label after the first one on the next owner
1087                  * name is a non-terminal if it either does not exist
1088                  * in the current name or is different from the same
1089                  * label in the current name (counting from the end)
1090                  */
1091                 for (i = 1; i < next_label_count - soa_label_count; i++) {
1092                         lpos = (int)cur_label_count - (int)next_label_count + (int)i;
1093                         if (lpos >= 0) {
1094                                 l1 = ldns_dname_clone_from(cur_name, (uint8_t)lpos);
1095                         } else {
1096                                 l1 = NULL;
1097                         }
1098                         l2 = ldns_dname_clone_from(next_name, i);
1099
1100                         if (!l1 || ldns_dname_compare(l1, l2) != 0) {
1101                                 /* We have an empty nonterminal, add it to the
1102                                  * tree
1103                                  */
1104                                 ldns_rbnode_t *node = NULL;
1105                                 ldns_rdf *ent_name;
1106
1107                                 if (!(ent_name = ldns_dname_clone_from(
1108                                                 next_name, i)))
1109                                         return LDNS_STATUS_MEM_ERR;
1110
1111                                 if (nsec3s && zone->_nsec3params) {
1112                                         ldns_rdf *ent_hashed_name;
1113
1114                                         if (!(ent_hashed_name =
1115                                             ldns_nsec3_hash_name_frm_nsec3(
1116                                                         zone->_nsec3params,
1117                                                         ent_name)))
1118                                                 return LDNS_STATUS_MEM_ERR;
1119                                         node = ldns_rbtree_search(nsec3s,
1120                                                         ent_hashed_name);
1121                                         if (!node) {
1122                                                 ldns_rdf_deep_free(l1);
1123                                                 ldns_rdf_deep_free(l2);
1124                                                 continue;
1125                                         }
1126                                 }
1127                                 new_name = ldns_dnssec_name_new();
1128                                 if (!new_name) {
1129                                         return LDNS_STATUS_MEM_ERR;
1130                                 }
1131                                 new_name->name = ent_name;
1132                                 if (!new_name->name) {
1133                                         ldns_dnssec_name_free(new_name);
1134                                         return LDNS_STATUS_MEM_ERR;
1135                                 }
1136                                 new_name->name_alloced = true;
1137                                 new_node = LDNS_MALLOC(ldns_rbnode_t);
1138                                 if (!new_node) {
1139                                         ldns_dnssec_name_free(new_name);
1140                                         return LDNS_STATUS_MEM_ERR;
1141                                 }
1142                                 new_node->key = new_name->name;
1143                                 new_node->data = new_name;
1144                                 (void)ldns_rbtree_insert(zone->names, new_node);
1145                                 ldns_dnssec_name_make_hashed_name(
1146                                                 zone, new_name, NULL);
1147                                 if (node)
1148                                         (void) ldns_dnssec_zone_add_rr(zone,
1149                                                         (ldns_rr *)node->data);
1150                         }
1151                         ldns_rdf_deep_free(l1);
1152                         ldns_rdf_deep_free(l2);
1153                 }
1154
1155                 /* we might have inserted a new node after
1156                  * the current one so we can't just use next()
1157                  */
1158                 if (next_node != ldns_rbtree_first(zone->names)) {
1159                         cur_node = next_node;
1160                 } else {
1161                         cur_node = LDNS_RBTREE_NULL;
1162                 }
1163         }
1164         return LDNS_STATUS_OK;
1165 }
1166
1167 ldns_status
1168 ldns_dnssec_zone_add_empty_nonterminals(ldns_dnssec_zone *zone)
1169 {
1170         return ldns_dnssec_zone_add_empty_nonterminals_nsec3(zone, NULL);
1171 }
1172
1173 bool
1174 ldns_dnssec_zone_is_nsec3_optout(const ldns_dnssec_zone* zone)
1175 {
1176         ldns_rr* nsec3;
1177         ldns_rbnode_t* node;
1178
1179         if (ldns_dnssec_name_find_rrset(zone->soa, LDNS_RR_TYPE_NSEC3PARAM)) {
1180                 node = ldns_rbtree_first(zone->names);
1181                 while (node != LDNS_RBTREE_NULL) {
1182                         nsec3 = ((ldns_dnssec_name*)node->data)->nsec;
1183                         if (nsec3 &&ldns_rr_get_type(nsec3)
1184                                         == LDNS_RR_TYPE_NSEC3 &&
1185                                         ldns_nsec3_optout(nsec3)) {
1186                                 return true;
1187                         }
1188                         node = ldns_rbtree_next(node);
1189                 }
1190         }
1191         return false;
1192 }