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