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