dnssec_zone.c
Go to the documentation of this file.
00001 /*
00002  * special zone file structures and functions for better dnssec handling
00003  */
00004 
00005 #include <ldns/config.h>
00006 
00007 #include <ldns/ldns.h>
00008 
00009 ldns_dnssec_rrs *
00010 ldns_dnssec_rrs_new(void)
00011 {
00012         ldns_dnssec_rrs *new_rrs;
00013         new_rrs = LDNS_MALLOC(ldns_dnssec_rrs);
00014         if(!new_rrs) return NULL;
00015         new_rrs->rr = NULL;
00016         new_rrs->next = NULL;
00017         return new_rrs;
00018 }
00019 
00020 INLINE void
00021 ldns_dnssec_rrs_free_internal(ldns_dnssec_rrs *rrs, int deep)
00022 {
00023         ldns_dnssec_rrs *next;
00024         while (rrs) {
00025                 next = rrs->next;
00026                 if (deep) {
00027                         ldns_rr_free(rrs->rr);
00028                 }
00029                 LDNS_FREE(rrs);
00030                 rrs = next;
00031         }
00032 }
00033 
00034 void
00035 ldns_dnssec_rrs_free(ldns_dnssec_rrs *rrs)
00036 {
00037         ldns_dnssec_rrs_free_internal(rrs, 0);
00038 }
00039 
00040 void
00041 ldns_dnssec_rrs_deep_free(ldns_dnssec_rrs *rrs)
00042 {
00043         ldns_dnssec_rrs_free_internal(rrs, 1);
00044 }
00045 
00046 ldns_status
00047 ldns_dnssec_rrs_add_rr(ldns_dnssec_rrs *rrs, ldns_rr *rr)
00048 {
00049         int cmp;
00050         ldns_dnssec_rrs *new_rrs;
00051         if (!rrs || !rr) {
00052                 return LDNS_STATUS_ERR;
00053         }
00054 
00055         /* this could be done more efficiently; name and type should already
00056            be equal */
00057         cmp = ldns_rr_compare(rrs->rr, rr);
00058         if (cmp < 0) {
00059                 if (rrs->next) {
00060                         return ldns_dnssec_rrs_add_rr(rrs->next, rr);
00061                 } else {
00062                         new_rrs = ldns_dnssec_rrs_new();
00063                         new_rrs->rr = rr;
00064                         rrs->next = new_rrs;
00065                 }
00066         } else if (cmp > 0) {
00067                 /* put the current old rr in the new next, put the new
00068                    rr in the current container */
00069                 new_rrs = ldns_dnssec_rrs_new();
00070                 new_rrs->rr = rrs->rr;
00071                 new_rrs->next = rrs->next;
00072                 rrs->rr = rr;
00073                 rrs->next = new_rrs;
00074         }
00075         /* Silently ignore equal rr's */
00076         return LDNS_STATUS_OK;
00077 }
00078 
00079 void
00080 ldns_dnssec_rrs_print_fmt(FILE *out, const ldns_output_format *fmt,
00081                ldns_dnssec_rrs *rrs)
00082 {
00083         if (!rrs) {
00084                 if ((fmt->flags & LDNS_COMMENT_LAYOUT))
00085                         fprintf(out, "; <void>");
00086         } else {
00087                 if (rrs->rr) {
00088                         ldns_rr_print_fmt(out, fmt, rrs->rr);
00089                 }
00090                 if (rrs->next) {
00091                         ldns_dnssec_rrs_print_fmt(out, fmt, rrs->next);
00092                 }
00093         }
00094 }
00095 
00096 void
00097 ldns_dnssec_rrs_print(FILE *out, ldns_dnssec_rrs *rrs)
00098 {
00099         ldns_dnssec_rrs_print_fmt(out, ldns_output_format_default, rrs);
00100 }
00101 
00102 
00103 ldns_dnssec_rrsets *
00104 ldns_dnssec_rrsets_new(void)
00105 {
00106         ldns_dnssec_rrsets *new_rrsets;
00107         new_rrsets = LDNS_MALLOC(ldns_dnssec_rrsets);
00108         if(!new_rrsets) return NULL;
00109         new_rrsets->rrs = NULL;
00110         new_rrsets->type = 0;
00111         new_rrsets->signatures = NULL;
00112         new_rrsets->next = NULL;
00113         return new_rrsets;
00114 }
00115 
00116 INLINE void
00117 ldns_dnssec_rrsets_free_internal(ldns_dnssec_rrsets *rrsets, int deep)
00118 {
00119         if (rrsets) {
00120                 if (rrsets->rrs) {
00121                         ldns_dnssec_rrs_free_internal(rrsets->rrs, deep);
00122                 }
00123                 if (rrsets->next) {
00124                         ldns_dnssec_rrsets_free_internal(rrsets->next, deep);
00125                 }
00126                 if (rrsets->signatures) {
00127                         ldns_dnssec_rrs_free_internal(rrsets->signatures, deep);
00128                 }
00129                 LDNS_FREE(rrsets);
00130         }
00131 }
00132 
00133 void
00134 ldns_dnssec_rrsets_free(ldns_dnssec_rrsets *rrsets)
00135 {
00136         ldns_dnssec_rrsets_free_internal(rrsets, 0);
00137 }
00138 
00139 void
00140 ldns_dnssec_rrsets_deep_free(ldns_dnssec_rrsets *rrsets)
00141 {
00142         ldns_dnssec_rrsets_free_internal(rrsets, 1);
00143 }
00144 
00145 ldns_rr_type
00146 ldns_dnssec_rrsets_type(ldns_dnssec_rrsets *rrsets)
00147 {
00148         if (rrsets) {
00149                 return rrsets->type;
00150         } else {
00151                 return 0;
00152         }
00153 }
00154 
00155 ldns_status
00156 ldns_dnssec_rrsets_set_type(ldns_dnssec_rrsets *rrsets,
00157                                            ldns_rr_type type)
00158 {
00159         if (rrsets) {
00160                 rrsets->type = type;
00161                 return LDNS_STATUS_OK;
00162         }
00163         return LDNS_STATUS_ERR;
00164 }
00165 
00166 static ldns_dnssec_rrsets *
00167 ldns_dnssec_rrsets_new_frm_rr(ldns_rr *rr)
00168 {
00169         ldns_dnssec_rrsets *new_rrsets;
00170         ldns_rr_type rr_type;
00171         bool rrsig;
00172 
00173         new_rrsets = ldns_dnssec_rrsets_new();
00174         rr_type = ldns_rr_get_type(rr);
00175         if (rr_type == LDNS_RR_TYPE_RRSIG) {
00176                 rrsig = true;
00177                 rr_type = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr));
00178         } else {
00179                 rrsig = false;
00180         }
00181         if (!rrsig) {
00182                 new_rrsets->rrs = ldns_dnssec_rrs_new();
00183                 new_rrsets->rrs->rr = rr;
00184         } else {
00185                 new_rrsets->signatures = ldns_dnssec_rrs_new();
00186                 new_rrsets->signatures->rr = rr;
00187         }
00188         new_rrsets->type = rr_type;
00189         return new_rrsets;
00190 }
00191 
00192 ldns_status
00193 ldns_dnssec_rrsets_add_rr(ldns_dnssec_rrsets *rrsets, ldns_rr *rr)
00194 {
00195         ldns_dnssec_rrsets *new_rrsets;
00196         ldns_rr_type rr_type;
00197         bool rrsig = false;
00198         ldns_status result = LDNS_STATUS_OK;
00199 
00200         if (!rrsets || !rr) {
00201                 return LDNS_STATUS_ERR;
00202         }
00203 
00204         rr_type = ldns_rr_get_type(rr);
00205 
00206         if (rr_type == LDNS_RR_TYPE_RRSIG) {
00207                 rrsig = true;
00208                 rr_type = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr));
00209         }
00210 
00211         if (!rrsets->rrs && rrsets->type == 0 && !rrsets->signatures) {
00212                 if (!rrsig) {
00213                         rrsets->rrs = ldns_dnssec_rrs_new();
00214                         rrsets->rrs->rr = rr;
00215                         rrsets->type = rr_type;
00216                 } else {
00217                         rrsets->signatures = ldns_dnssec_rrs_new();
00218                         rrsets->signatures->rr = rr;
00219                         rrsets->type = rr_type;
00220                 }
00221                 return LDNS_STATUS_OK;
00222         }
00223 
00224         if (rr_type > ldns_dnssec_rrsets_type(rrsets)) {
00225                 if (rrsets->next) {
00226                         result = ldns_dnssec_rrsets_add_rr(rrsets->next, rr);
00227                 } else {
00228                         new_rrsets = ldns_dnssec_rrsets_new_frm_rr(rr);
00229                         rrsets->next = new_rrsets;
00230                 }
00231         } else if (rr_type < ldns_dnssec_rrsets_type(rrsets)) {
00232                 /* move the current one into the new next, 
00233                    replace field of current with data from new rr */
00234                 new_rrsets = ldns_dnssec_rrsets_new();
00235                 new_rrsets->rrs = rrsets->rrs;
00236                 new_rrsets->type = rrsets->type;
00237                 new_rrsets->signatures = rrsets->signatures;
00238                 new_rrsets->next = rrsets->next;
00239                 if (!rrsig) {
00240                         rrsets->rrs = ldns_dnssec_rrs_new();
00241                         rrsets->rrs->rr = rr;
00242                         rrsets->signatures = NULL;
00243                 } else {
00244                         rrsets->rrs = NULL;
00245                         rrsets->signatures = ldns_dnssec_rrs_new();
00246                         rrsets->signatures->rr = rr;
00247                 }
00248                 rrsets->type = rr_type;
00249                 rrsets->next = new_rrsets;
00250         } else {
00251                 /* equal, add to current rrsets */
00252                 if (rrsig) {
00253                         if (rrsets->signatures) {
00254                                 result = ldns_dnssec_rrs_add_rr(rrsets->signatures, rr);
00255                         } else {
00256                                 rrsets->signatures = ldns_dnssec_rrs_new();
00257                                 rrsets->signatures->rr = rr;
00258                         }
00259                 } else {
00260                         if (rrsets->rrs) {
00261                                 result = ldns_dnssec_rrs_add_rr(rrsets->rrs, rr);
00262                         } else {
00263                                 rrsets->rrs = ldns_dnssec_rrs_new();
00264                                 rrsets->rrs->rr = rr;
00265                         }
00266                 }
00267         }
00268 
00269         return result;
00270 }
00271 
00272 static void
00273 ldns_dnssec_rrsets_print_soa_fmt(FILE *out, const ldns_output_format *fmt,
00274                 ldns_dnssec_rrsets *rrsets,
00275                 bool follow,
00276                 bool show_soa)
00277 {
00278         if (!rrsets) {
00279                 if ((fmt->flags & LDNS_COMMENT_LAYOUT))
00280                         fprintf(out, "; <void>\n");
00281         } else {
00282                 if (rrsets->rrs &&
00283                     (show_soa ||
00284                         ldns_rr_get_type(rrsets->rrs->rr) != LDNS_RR_TYPE_SOA
00285                     )
00286                    ) {
00287                         ldns_dnssec_rrs_print_fmt(out, fmt, rrsets->rrs);
00288                         if (rrsets->signatures) {
00289                                 ldns_dnssec_rrs_print_fmt(out, fmt, 
00290                                                 rrsets->signatures);
00291                         }
00292                 }
00293                 if (follow && rrsets->next) {
00294                         ldns_dnssec_rrsets_print_soa_fmt(out, fmt, 
00295                                         rrsets->next, follow, show_soa);
00296                 }
00297         }
00298 }
00299 
00300 
00301 void
00302 ldns_dnssec_rrsets_print_fmt(FILE *out, const ldns_output_format *fmt,
00303                 ldns_dnssec_rrsets *rrsets, 
00304                 bool follow)
00305 {
00306         ldns_dnssec_rrsets_print_soa_fmt(out, fmt, rrsets, follow, true);
00307 }
00308 
00309 void
00310 ldns_dnssec_rrsets_print(FILE *out, ldns_dnssec_rrsets *rrsets, bool follow)
00311 {
00312         ldns_dnssec_rrsets_print_fmt(out, ldns_output_format_default, 
00313                         rrsets, follow);
00314 }
00315 
00316 ldns_dnssec_name *
00317 ldns_dnssec_name_new(void)
00318 {
00319         ldns_dnssec_name *new_name;
00320 
00321         new_name = LDNS_CALLOC(ldns_dnssec_name, 1);
00322         if (!new_name) {
00323                 return NULL;
00324         }
00325         /*
00326          * not needed anymore because CALLOC initalizes everything to zero.
00327 
00328         new_name->name = NULL;
00329         new_name->rrsets = NULL;
00330         new_name->name_alloced = false;
00331         new_name->nsec = NULL;
00332         new_name->nsec_signatures = NULL;
00333 
00334         new_name->is_glue = false;
00335         new_name->hashed_name = NULL;
00336 
00337          */
00338         return new_name;
00339 }
00340 
00341 ldns_dnssec_name *
00342 ldns_dnssec_name_new_frm_rr(ldns_rr *rr)
00343 {
00344         ldns_dnssec_name *new_name = ldns_dnssec_name_new();
00345 
00346         new_name->name = ldns_rr_owner(rr);
00347         if(ldns_dnssec_name_add_rr(new_name, rr) != LDNS_STATUS_OK) {
00348                 ldns_dnssec_name_free(new_name);
00349                 return NULL;
00350         }
00351 
00352         return new_name;
00353 }
00354 
00355 INLINE void
00356 ldns_dnssec_name_free_internal(ldns_dnssec_name *name,
00357                                int deep)
00358 {
00359         if (name) {
00360                 if (name->name_alloced) {
00361                         ldns_rdf_deep_free(name->name);
00362                 }
00363                 if (name->rrsets) {
00364                         ldns_dnssec_rrsets_free_internal(name->rrsets, deep);
00365                 }
00366                 if (name->nsec && deep) {
00367                         ldns_rr_free(name->nsec);
00368                 }
00369                 if (name->nsec_signatures) {
00370                         ldns_dnssec_rrs_free_internal(name->nsec_signatures, deep);
00371                 }
00372                 if (name->hashed_name) {
00373                         if (deep) {
00374                                 ldns_rdf_deep_free(name->hashed_name);
00375                         }
00376                 }
00377                 LDNS_FREE(name);
00378         }
00379 }
00380 
00381 void
00382 ldns_dnssec_name_free(ldns_dnssec_name *name)
00383 {
00384   ldns_dnssec_name_free_internal(name, 0);
00385 }
00386 
00387 void
00388 ldns_dnssec_name_deep_free(ldns_dnssec_name *name)
00389 {
00390   ldns_dnssec_name_free_internal(name, 1);
00391 }
00392 
00393 ldns_rdf *
00394 ldns_dnssec_name_name(ldns_dnssec_name *name)
00395 {
00396         if (name) {
00397                 return name->name;
00398         }
00399         return NULL;
00400 }
00401 
00402 bool
00403 ldns_dnssec_name_is_glue(ldns_dnssec_name *name)
00404 {
00405         if (name) {
00406                 return name->is_glue;
00407         }
00408         return false;
00409 }
00410 
00411 void
00412 ldns_dnssec_name_set_name(ldns_dnssec_name *rrset,
00413                                          ldns_rdf *dname)
00414 {
00415         if (rrset && dname) {
00416                 rrset->name = dname;
00417         }
00418 }
00419 
00420 
00421 void
00422 ldns_dnssec_name_set_nsec(ldns_dnssec_name *rrset, ldns_rr *nsec)
00423 {
00424         if (rrset && nsec) {
00425                 rrset->nsec = nsec;
00426         }
00427 }
00428 
00429 int
00430 ldns_dnssec_name_cmp(const void *a, const void *b)
00431 {
00432         ldns_dnssec_name *na = (ldns_dnssec_name *) a;
00433         ldns_dnssec_name *nb = (ldns_dnssec_name *) b;
00434 
00435         if (na && nb) {
00436                 return ldns_dname_compare(ldns_dnssec_name_name(na),
00437                                                          ldns_dnssec_name_name(nb));
00438         } else if (na) {
00439                 return 1;
00440         } else if (nb) {
00441                 return -1;
00442         } else {
00443                 return 0;
00444         }
00445 }
00446 
00447 ldns_status
00448 ldns_dnssec_name_add_rr(ldns_dnssec_name *name,
00449                                     ldns_rr *rr)
00450 {
00451         ldns_status result = LDNS_STATUS_OK;
00452         ldns_rr_type rr_type;
00453         ldns_rr_type typecovered = 0;
00454 
00455         /* special handling for NSEC3 and NSECX covering RRSIGS */
00456 
00457         if (!name || !rr) {
00458                 return LDNS_STATUS_ERR;
00459         }
00460 
00461         rr_type = ldns_rr_get_type(rr);
00462 
00463         if (rr_type == LDNS_RR_TYPE_RRSIG) {
00464                 typecovered = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr));
00465         }
00466 
00467         if (rr_type == LDNS_RR_TYPE_NSEC ||
00468             rr_type == LDNS_RR_TYPE_NSEC3) {
00469                 /* XX check if is already set (and error?) */
00470                 name->nsec = rr;
00471         } else if (typecovered == LDNS_RR_TYPE_NSEC ||
00472                          typecovered == LDNS_RR_TYPE_NSEC3) {
00473                 if (name->nsec_signatures) {
00474                         result = ldns_dnssec_rrs_add_rr(name->nsec_signatures, rr);
00475                 } else {
00476                         name->nsec_signatures = ldns_dnssec_rrs_new();
00477                         name->nsec_signatures->rr = rr;
00478                 }
00479         } else {
00480                 /* it's a 'normal' RR, add it to the right rrset */
00481                 if (name->rrsets) {
00482                         result = ldns_dnssec_rrsets_add_rr(name->rrsets, rr);
00483                 } else {
00484                         name->rrsets = ldns_dnssec_rrsets_new();
00485                         result = ldns_dnssec_rrsets_add_rr(name->rrsets, rr);
00486                 }
00487         }
00488         return result;
00489 }
00490 
00491 ldns_dnssec_rrsets *
00492 ldns_dnssec_name_find_rrset(ldns_dnssec_name *name,
00493                                            ldns_rr_type type) {
00494         ldns_dnssec_rrsets *result;
00495 
00496         result = name->rrsets;
00497         while (result) {
00498                 if (result->type == type) {
00499                         return result;
00500                 } else {
00501                         result = result->next;
00502                 }
00503         }
00504         return NULL;
00505 }
00506 
00507 ldns_dnssec_rrsets *
00508 ldns_dnssec_zone_find_rrset(ldns_dnssec_zone *zone,
00509                                            ldns_rdf *dname,
00510                                            ldns_rr_type type)
00511 {
00512         ldns_rbnode_t *node;
00513 
00514         if (!zone || !dname) {
00515                 return NULL;
00516         }
00517 
00518         node = ldns_rbtree_search(zone->names, dname);
00519         if (node) {
00520                 return ldns_dnssec_name_find_rrset((ldns_dnssec_name *)node->data,
00521                                                                         type);
00522         } else {
00523                 return NULL;
00524         }
00525 }
00526 
00527 static void
00528 ldns_dnssec_name_print_soa_fmt(FILE *out, const ldns_output_format *fmt,
00529                 ldns_dnssec_name *name, 
00530                 bool show_soa)
00531 {
00532         if (name) {
00533                 if(name->rrsets) {
00534                         ldns_dnssec_rrsets_print_soa_fmt(out, fmt, 
00535                                         name->rrsets, true, show_soa);
00536                 } else if ((fmt->flags & LDNS_COMMENT_LAYOUT)) {
00537                         fprintf(out, ";; Empty nonterminal: ");
00538                         ldns_rdf_print(out, name->name);
00539                         fprintf(out, "\n");
00540                 }
00541                 if(name->nsec) {
00542                         ldns_rr_print_fmt(out, fmt, name->nsec);
00543                 }
00544                 if (name->nsec_signatures) {
00545                         ldns_dnssec_rrs_print_fmt(out, fmt, 
00546                                         name->nsec_signatures);
00547                 }
00548         } else if ((fmt->flags & LDNS_COMMENT_LAYOUT)) {
00549                 fprintf(out, "; <void>\n");
00550         }
00551 }
00552 
00553 
00554 void
00555 ldns_dnssec_name_print_fmt(FILE *out, const ldns_output_format *fmt,
00556                 ldns_dnssec_name *name)
00557 {
00558         ldns_dnssec_name_print_soa_fmt(out, fmt, name, true);
00559 }
00560 
00561 void
00562 ldns_dnssec_name_print(FILE *out, ldns_dnssec_name *name)
00563 {
00564         ldns_dnssec_name_print_fmt(out, ldns_output_format_default, name);
00565 }
00566 
00567 
00568 ldns_dnssec_zone *
00569 ldns_dnssec_zone_new(void)
00570 {
00571         ldns_dnssec_zone *zone = LDNS_MALLOC(ldns_dnssec_zone);
00572         if(!zone) return NULL;
00573         zone->soa = NULL;
00574         zone->names = NULL;
00575         zone->hashed_names = NULL;
00576         zone->_nsec3params = NULL;
00577 
00578         return zone;
00579 }
00580 
00581 static bool
00582 rr_is_rrsig_covering(ldns_rr* rr, ldns_rr_type t)
00583 {
00584         return     ldns_rr_get_type(rr) == LDNS_RR_TYPE_RRSIG
00585                 && ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr)) == t;
00586 }
00587 
00588 /* When the zone is first read into an list and then inserted into an
00589  * ldns_dnssec_zone (rbtree) the nodes of the rbtree are allocated close (next)
00590  * to each other. Because ldns-verify-zone (the only program that uses this
00591  * function) uses the rbtree mostly for sequentual walking, this results
00592  * in a speed increase (of 15% on linux) because we have less CPU-cache misses.
00593  */
00594 #define FASTER_DNSSEC_ZONE_NEW_FRM_FP 1 /* Because of L2 cache efficiency */
00595 
00596 ldns_status
00597 ldns_dnssec_zone_new_frm_fp_l(ldns_dnssec_zone** z, FILE* fp, ldns_rdf* origin,
00598                 uint32_t ttl, ldns_rr_class ATTR_UNUSED(c), int* line_nr)
00599 {
00600         ldns_rr* cur_rr;
00601         size_t i;
00602 
00603         ldns_rdf *my_origin = NULL;
00604         ldns_rdf *my_prev = NULL;
00605 
00606         ldns_dnssec_zone *newzone = ldns_dnssec_zone_new();
00607         /* when reading NSEC3s, there is a chance that we encounter nsecs
00608            for empty nonterminals, whose nonterminals we cannot derive yet
00609            because the needed information is to be read later. in that case
00610            we keep a list of those nsec3's and retry to add them later */
00611         ldns_rr_list* todo_nsec3s = ldns_rr_list_new();
00612         ldns_rr_list* todo_nsec3_rrsigs = ldns_rr_list_new();
00613 
00614         ldns_status status = LDNS_STATUS_MEM_ERR;
00615 
00616 #ifdef FASTER_DNSSEC_ZONE_NEW_FRM_FP
00617         ldns_zone* zone = NULL;
00618         if (ldns_zone_new_frm_fp_l(&zone, fp, origin,ttl, c, line_nr)
00619                         != LDNS_STATUS_OK) goto error;
00620 #else
00621         uint32_t  my_ttl = ttl;
00622 #endif
00623 
00624         if (!newzone || !todo_nsec3s || !todo_nsec3_rrsigs ) goto error;
00625 
00626         if (origin) {
00627                 if (!(my_origin = ldns_rdf_clone(origin))) goto error;
00628                 if (!(my_prev   = ldns_rdf_clone(origin))) goto error;
00629         }
00630 
00631 #ifdef FASTER_DNSSEC_ZONE_NEW_FRM_FP
00632         if (ldns_dnssec_zone_add_rr(newzone, ldns_zone_soa(zone))
00633                         != LDNS_STATUS_OK) goto error;
00634 
00635         for (i = 0; i < ldns_rr_list_rr_count(ldns_zone_rrs(zone)); i++) {
00636                 cur_rr = ldns_rr_list_rr(ldns_zone_rrs(zone), i);
00637                 status = LDNS_STATUS_OK;
00638 #else
00639         while (!feof(fp)) {
00640                 status = ldns_rr_new_frm_fp_l(&cur_rr, fp, &my_ttl, &my_origin,
00641                                 &my_prev, line_nr);
00642 
00643 #endif
00644                 switch (status) {
00645                 case LDNS_STATUS_OK:
00646 
00647                         status = ldns_dnssec_zone_add_rr(newzone, cur_rr);
00648                         if (status ==
00649                                 LDNS_STATUS_DNSSEC_NSEC3_ORIGINAL_NOT_FOUND) {
00650 
00651                                 if (rr_is_rrsig_covering(cur_rr,
00652                                                         LDNS_RR_TYPE_NSEC3)){
00653                                         ldns_rr_list_push_rr(todo_nsec3_rrsigs,
00654                                                         cur_rr);
00655                                 } else {
00656                                         ldns_rr_list_push_rr(todo_nsec3s,
00657                                                         cur_rr);
00658                                 }
00659                                 status = LDNS_STATUS_OK;
00660 
00661                         } else if (status != LDNS_STATUS_OK)
00662                                 goto error;
00663 
00664                         break;
00665 
00666 
00667                 case LDNS_STATUS_SYNTAX_EMPTY:  /* empty line was seen */
00668                 case LDNS_STATUS_SYNTAX_TTL:    /* the ttl was set*/
00669                 case LDNS_STATUS_SYNTAX_ORIGIN: /* the origin was set*/
00670                         status = LDNS_STATUS_OK;
00671                         break;
00672 
00673                 case LDNS_STATUS_SYNTAX_INCLUDE:/* $include not implemented */
00674                         status =  LDNS_STATUS_SYNTAX_INCLUDE_ERR_NOTIMPL;
00675                         break;
00676 
00677                 default:
00678                         goto error;
00679                 }
00680         }
00681 
00682         if (ldns_rr_list_rr_count(todo_nsec3s) > 0) {
00683                 (void) ldns_dnssec_zone_add_empty_nonterminals(newzone);
00684                 for (i = 0; status == LDNS_STATUS_OK &&
00685                                 i < ldns_rr_list_rr_count(todo_nsec3s); i++) {
00686                         cur_rr = ldns_rr_list_rr(todo_nsec3s, i);
00687                         status = ldns_dnssec_zone_add_rr(newzone, cur_rr);
00688                 }
00689         } 
00690         if (ldns_rr_list_rr_count(todo_nsec3_rrsigs) > 0) {
00691                 for (i = 0; status == LDNS_STATUS_OK &&
00692                                 i < ldns_rr_list_rr_count(todo_nsec3_rrsigs);
00693                                 i++){
00694                         cur_rr = ldns_rr_list_rr(todo_nsec3_rrsigs, i);
00695                         status = ldns_dnssec_zone_add_rr(newzone, cur_rr);
00696                 }
00697         }
00698 
00699         if (z) {
00700                 *z = newzone;
00701                 newzone = NULL;
00702         } else {
00703                 ldns_dnssec_zone_free(newzone);
00704         }
00705 
00706 error:
00707 #ifdef FASTER_DNSSEC_ZONE_NEW_FRM_FP
00708         if (zone) {
00709                 ldns_zone_free(zone);
00710         }
00711 #endif
00712         ldns_rr_list_free(todo_nsec3_rrsigs);
00713         ldns_rr_list_free(todo_nsec3s);
00714 
00715         if (my_origin) {
00716                 ldns_rdf_deep_free(my_origin);
00717         }
00718         if (my_prev) {
00719                 ldns_rdf_deep_free(my_prev);
00720         }
00721         if (newzone) {
00722                 ldns_dnssec_zone_free(newzone);
00723         }
00724         return status;
00725 }
00726 
00727 ldns_status
00728 ldns_dnssec_zone_new_frm_fp(ldns_dnssec_zone** z, FILE* fp, ldns_rdf* origin,
00729                 uint32_t ttl, ldns_rr_class ATTR_UNUSED(c))
00730 {
00731         return ldns_dnssec_zone_new_frm_fp_l(z, fp, origin, ttl, c, NULL);
00732 }
00733 
00734 static void
00735 ldns_dnssec_name_node_free(ldns_rbnode_t *node, void *arg) {
00736         (void) arg;
00737         ldns_dnssec_name_free((ldns_dnssec_name *)node->data);
00738         LDNS_FREE(node);
00739 }
00740 
00741 static void
00742 ldns_dnssec_name_node_deep_free(ldns_rbnode_t *node, void *arg) {
00743         (void) arg;
00744         ldns_dnssec_name_deep_free((ldns_dnssec_name *)node->data);
00745         LDNS_FREE(node);
00746 }
00747 
00748 void
00749 ldns_dnssec_zone_free(ldns_dnssec_zone *zone)
00750 {
00751         if (zone) {
00752                 if (zone->names) {
00753                         /* destroy all name structures within the tree */
00754                         ldns_traverse_postorder(zone->names,
00755                                                     ldns_dnssec_name_node_free,
00756                                                     NULL);
00757                         LDNS_FREE(zone->names);
00758                 }
00759                 LDNS_FREE(zone);
00760         }
00761 }
00762 
00763 void
00764 ldns_dnssec_zone_deep_free(ldns_dnssec_zone *zone)
00765 {
00766         if (zone) {
00767                 if (zone->names) {
00768                         /* destroy all name structures within the tree */
00769                         ldns_traverse_postorder(zone->names,
00770                                                     ldns_dnssec_name_node_deep_free,
00771                                                     NULL);
00772                         LDNS_FREE(zone->names);
00773                 }
00774                 LDNS_FREE(zone);
00775         }
00776 }
00777 
00778 /* use for dname comparison in tree */
00779 int
00780 ldns_dname_compare_v(const void *a, const void *b) {
00781         return ldns_dname_compare((ldns_rdf *)a, (ldns_rdf *)b);
00782 }
00783 
00784 static void
00785 ldns_dnssec_name_make_hashed_name(ldns_dnssec_zone *zone,
00786                 ldns_dnssec_name* name, ldns_rr* nsec3rr);
00787 
00788 static void
00789 ldns_hashed_names_node_free(ldns_rbnode_t *node, void *arg) {
00790         (void) arg;
00791         LDNS_FREE(node);
00792 }
00793 
00794 static void
00795 ldns_dnssec_zone_hashed_names_from_nsec3(
00796                 ldns_dnssec_zone* zone, ldns_rr* nsec3rr)
00797 {
00798         ldns_rbnode_t* current_node;
00799         ldns_dnssec_name* current_name;
00800 
00801         assert(zone != NULL);
00802         assert(nsec3rr != NULL);
00803 
00804         if (zone->hashed_names) {
00805                 ldns_traverse_postorder(zone->hashed_names,
00806                                 ldns_hashed_names_node_free, NULL);
00807                 LDNS_FREE(zone->hashed_names);
00808         }
00809         zone->_nsec3params = nsec3rr;
00810 
00811         /* So this is a NSEC3 zone.
00812         * Calculate hashes for all names already in the zone
00813         */
00814         zone->hashed_names = ldns_rbtree_create(ldns_dname_compare_v);
00815         if (zone->hashed_names == NULL) {
00816                 return;
00817         }
00818         for ( current_node  = ldns_rbtree_first(zone->names)
00819             ; current_node != LDNS_RBTREE_NULL
00820             ; current_node  = ldns_rbtree_next(current_node)
00821             ) {
00822                 current_name = (ldns_dnssec_name *) current_node->data;
00823                 ldns_dnssec_name_make_hashed_name(zone, current_name, nsec3rr);
00824 
00825         }
00826 }
00827 
00828 static void
00829 ldns_dnssec_name_make_hashed_name(ldns_dnssec_zone *zone,
00830                 ldns_dnssec_name* name, ldns_rr* nsec3rr)
00831 {
00832         ldns_rbnode_t* new_node;
00833 
00834         assert(name != NULL);
00835         if (! zone->_nsec3params) {
00836                 if (! nsec3rr) {
00837                         return;
00838                 }
00839                 ldns_dnssec_zone_hashed_names_from_nsec3(zone, nsec3rr);
00840 
00841         } else if (! nsec3rr) {
00842                 nsec3rr = zone->_nsec3params;
00843         }
00844         name->hashed_name = ldns_nsec3_hash_name_frm_nsec3(nsec3rr, name->name);
00845 
00846         /* Also store in zone->hashed_names */
00847         if ((new_node = LDNS_MALLOC(ldns_rbnode_t))) {
00848 
00849                 new_node->key  = name->hashed_name;
00850                 new_node->data = name;
00851 
00852                 if (ldns_rbtree_insert(zone->hashed_names, new_node) == NULL) {
00853 
00854                                 LDNS_FREE(new_node);
00855                 }
00856         }
00857 }
00858 
00859 
00860 static ldns_rbnode_t *
00861 ldns_dnssec_zone_find_nsec3_original(ldns_dnssec_zone *zone, ldns_rr *rr) {
00862         ldns_rdf *hashed_name;
00863 
00864         hashed_name = ldns_dname_label(ldns_rr_owner(rr), 0);
00865         if (hashed_name == NULL) {
00866                 return NULL;
00867         }
00868         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_NSEC3 && ! zone->_nsec3params){
00869 
00870                 ldns_dnssec_zone_hashed_names_from_nsec3(zone, rr);
00871         }
00872         if (zone->hashed_names == NULL) {
00873                 ldns_rdf_deep_free(hashed_name);
00874                 return NULL;
00875         }
00876         return  ldns_rbtree_search(zone->hashed_names, hashed_name);
00877 }
00878 
00879 ldns_status
00880 ldns_dnssec_zone_add_rr(ldns_dnssec_zone *zone, ldns_rr *rr)
00881 {
00882         ldns_status result = LDNS_STATUS_OK;
00883         ldns_dnssec_name *cur_name;
00884         ldns_rbnode_t *cur_node;
00885         ldns_rr_type type_covered = 0;
00886 
00887         if (!zone || !rr) {
00888                 return LDNS_STATUS_ERR;
00889         }
00890 
00891         if (!zone->names) {
00892                 zone->names = ldns_rbtree_create(ldns_dname_compare_v);
00893                 if(!zone->names) return LDNS_STATUS_MEM_ERR;
00894         }
00895 
00896         /* we need the original of the hashed name if this is
00897            an NSEC3, or an RRSIG that covers an NSEC3 */
00898         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_RRSIG) {
00899                 type_covered = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr));
00900         }
00901         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_NSEC3 ||
00902             type_covered == LDNS_RR_TYPE_NSEC3) {
00903                 cur_node = ldns_dnssec_zone_find_nsec3_original(zone, rr);
00904                 if (!cur_node) {
00905                         return LDNS_STATUS_DNSSEC_NSEC3_ORIGINAL_NOT_FOUND;
00906                 }
00907         } else {
00908                 cur_node = ldns_rbtree_search(zone->names, ldns_rr_owner(rr));
00909         }
00910         if (!cur_node) {
00911                 /* add */
00912                 cur_name = ldns_dnssec_name_new_frm_rr(rr);
00913                 if(!cur_name) return LDNS_STATUS_MEM_ERR;
00914                 cur_node = LDNS_MALLOC(ldns_rbnode_t);
00915                 if(!cur_node) {
00916                         ldns_dnssec_name_free(cur_name);
00917                         return LDNS_STATUS_MEM_ERR;
00918                 }
00919                 cur_node->key = ldns_rr_owner(rr);
00920                 cur_node->data = cur_name;
00921                 (void)ldns_rbtree_insert(zone->names, cur_node);
00922                 ldns_dnssec_name_make_hashed_name(zone, cur_name, NULL);
00923         } else {
00924                 cur_name = (ldns_dnssec_name *) cur_node->data;
00925                 result = ldns_dnssec_name_add_rr(cur_name, rr);
00926         }
00927         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_SOA) {
00928                 zone->soa = cur_name;
00929         }
00930         return result;
00931 }
00932 
00933 void
00934 ldns_dnssec_zone_names_print_fmt(FILE *out, const ldns_output_format *fmt,
00935                 ldns_rbtree_t *tree, 
00936                 bool print_soa)
00937 {
00938         ldns_rbnode_t *node;
00939         ldns_dnssec_name *name;
00940 
00941         node = ldns_rbtree_first(tree);
00942         while (node != LDNS_RBTREE_NULL) {
00943                 name = (ldns_dnssec_name *) node->data;
00944                 ldns_dnssec_name_print_soa_fmt(out, fmt, name, print_soa);
00945                 if ((fmt->flags & LDNS_COMMENT_LAYOUT))
00946                         fprintf(out, ";\n");
00947                 node = ldns_rbtree_next(node);
00948         }
00949 }
00950 
00951 void
00952 ldns_dnssec_zone_names_print(FILE *out, ldns_rbtree_t *tree, bool print_soa)
00953 {
00954         ldns_dnssec_zone_names_print_fmt(out, ldns_output_format_default,
00955                        tree, print_soa);
00956 }
00957 
00958 void
00959 ldns_dnssec_zone_print_fmt(FILE *out, const ldns_output_format *fmt,
00960                ldns_dnssec_zone *zone)
00961 {
00962         if (zone) {
00963                 if (zone->soa) {
00964                         if ((fmt->flags & LDNS_COMMENT_LAYOUT)) {
00965                                 fprintf(out, ";; Zone: ");
00966                                 ldns_rdf_print(out, ldns_dnssec_name_name(
00967                                                         zone->soa));
00968                                 fprintf(out, "\n;\n");
00969                         }
00970                         ldns_dnssec_rrsets_print_fmt(out, fmt,
00971                                         ldns_dnssec_name_find_rrset(
00972                                                 zone->soa, 
00973                                                 LDNS_RR_TYPE_SOA), 
00974                                         false);
00975                         if ((fmt->flags & LDNS_COMMENT_LAYOUT))
00976                                 fprintf(out, ";\n");
00977                 }
00978 
00979                 if (zone->names) {
00980                         ldns_dnssec_zone_names_print_fmt(out, fmt, 
00981                                         zone->names, false);
00982                 }
00983         }
00984 }
00985 
00986 void
00987 ldns_dnssec_zone_print(FILE *out, ldns_dnssec_zone *zone)
00988 {
00989         ldns_dnssec_zone_print_fmt(out, ldns_output_format_default, zone);
00990 }
00991 
00992 ldns_status
00993 ldns_dnssec_zone_add_empty_nonterminals(ldns_dnssec_zone *zone)
00994 {
00995         ldns_dnssec_name *new_name;
00996         ldns_rdf *cur_name;
00997         ldns_rdf *next_name;
00998         ldns_rbnode_t *cur_node, *next_node, *new_node;
00999 
01000         /* for the detection */
01001         uint16_t i, cur_label_count, next_label_count;
01002         uint16_t soa_label_count = 0;
01003         ldns_rdf *l1, *l2;
01004         int lpos;
01005 
01006         if (!zone) {
01007                 return LDNS_STATUS_ERR;
01008         }
01009         if (zone->soa && zone->soa->name) {
01010                 soa_label_count = ldns_dname_label_count(zone->soa->name);
01011         }
01012         
01013         cur_node = ldns_rbtree_first(zone->names);
01014         while (cur_node != LDNS_RBTREE_NULL) {
01015                 next_node = ldns_rbtree_next(cur_node);
01016                 
01017                 /* skip glue */
01018                 while (next_node != LDNS_RBTREE_NULL && 
01019                        next_node->data &&
01020                        ((ldns_dnssec_name *)next_node->data)->is_glue
01021                 ) {
01022                         next_node = ldns_rbtree_next(next_node);
01023                 }
01024 
01025                 if (next_node == LDNS_RBTREE_NULL) {
01026                         next_node = ldns_rbtree_first(zone->names);
01027                 }
01028                 if (! cur_node->data || ! next_node->data) {
01029                         return LDNS_STATUS_ERR;
01030                 }
01031                 cur_name = ((ldns_dnssec_name *)cur_node->data)->name;
01032                 next_name = ((ldns_dnssec_name *)next_node->data)->name;
01033                 cur_label_count = ldns_dname_label_count(cur_name);
01034                 next_label_count = ldns_dname_label_count(next_name);
01035 
01036                 /* Since the names are in canonical order, we can
01037                  * recognize empty non-terminals by their labels;
01038                  * every label after the first one on the next owner
01039                  * name is a non-terminal if it either does not exist
01040                  * in the current name or is different from the same
01041                  * label in the current name (counting from the end)
01042                  */
01043                 for (i = 1; i < next_label_count - soa_label_count; i++) {
01044                         lpos = (int)cur_label_count - (int)next_label_count + (int)i;
01045                         if (lpos >= 0) {
01046                                 l1 = ldns_dname_clone_from(cur_name, (uint8_t)lpos);
01047                         } else {
01048                                 l1 = NULL;
01049                         }
01050                         l2 = ldns_dname_clone_from(next_name, i);
01051 
01052                         if (!l1 || ldns_dname_compare(l1, l2) != 0) {
01053                                 /* We have an empty nonterminal, add it to the
01054                                  * tree
01055                                  */
01056                                 new_name = ldns_dnssec_name_new();
01057                                 if (!new_name) {
01058                                         return LDNS_STATUS_MEM_ERR;
01059                                 }
01060                                 new_name->name = ldns_dname_clone_from(next_name,
01061                                                                        i);
01062                                 if (!new_name->name) {
01063                                         ldns_dnssec_name_free(new_name);
01064                                         return LDNS_STATUS_MEM_ERR;
01065                                 }
01066                                 new_name->name_alloced = true;
01067                                 new_node = LDNS_MALLOC(ldns_rbnode_t);
01068                                 if (!new_node) {
01069                                         ldns_dnssec_name_free(new_name);
01070                                         return LDNS_STATUS_MEM_ERR;
01071                                 }
01072                                 new_node->key = new_name->name;
01073                                 new_node->data = new_name;
01074                                 (void)ldns_rbtree_insert(zone->names, new_node);
01075                                 ldns_dnssec_name_make_hashed_name(
01076                                                 zone, new_name, NULL);
01077                         }
01078                         ldns_rdf_deep_free(l1);
01079                         ldns_rdf_deep_free(l2);
01080                 }
01081                 
01082                 /* we might have inserted a new node after
01083                  * the current one so we can't just use next()
01084                  */
01085                 if (next_node != ldns_rbtree_first(zone->names)) {
01086                         cur_node = next_node;
01087                 } else {
01088                         cur_node = LDNS_RBTREE_NULL;
01089                 }
01090         }
01091         return LDNS_STATUS_OK;
01092 }
01093 
01094 bool
01095 ldns_dnssec_zone_is_nsec3_optout(ldns_dnssec_zone* zone)
01096 {
01097         ldns_rr* nsec3;
01098         ldns_rbnode_t* node;
01099 
01100         if (ldns_dnssec_name_find_rrset(zone->soa, LDNS_RR_TYPE_NSEC3PARAM)) {
01101                 node = ldns_rbtree_first(zone->names);
01102                 while (node != LDNS_RBTREE_NULL) {
01103                         nsec3 = ((ldns_dnssec_name*)node->data)->nsec;
01104                         if (nsec3 &&ldns_rr_get_type(nsec3) 
01105                                         == LDNS_RR_TYPE_NSEC3 &&
01106                                         ldns_nsec3_optout(nsec3)) {
01107                                 return true;
01108                         }
01109                         node = ldns_rbtree_next(node);
01110                 }
01111         }
01112         return false;
01113 }