91e5651cf3a5fd64d6fb0be5779e93225a66950e
[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         new_rrs->rr = NULL;
15         new_rrs->next = NULL;
16         return new_rrs;
17 }
18
19 INLINE void
20 ldns_dnssec_rrs_free_internal(ldns_dnssec_rrs *rrs, int deep)
21 {
22         ldns_dnssec_rrs *next;
23         while (rrs) {
24                 next = rrs->next;
25                 if (deep) {
26                         ldns_rr_free(rrs->rr);
27                 }
28                 LDNS_FREE(rrs);
29                 rrs = next;
30         }
31 }
32
33 void
34 ldns_dnssec_rrs_free(ldns_dnssec_rrs *rrs)
35 {
36         ldns_dnssec_rrs_free_internal(rrs, 0);
37 }
38
39 void
40 ldns_dnssec_rrs_deep_free(ldns_dnssec_rrs *rrs)
41 {
42         ldns_dnssec_rrs_free_internal(rrs, 1);
43 }
44
45 ldns_status
46 ldns_dnssec_rrs_add_rr(ldns_dnssec_rrs *rrs, ldns_rr *rr)
47 {
48         int cmp;
49         ldns_dnssec_rrs *new_rrs;
50         if (!rrs || !rr) {
51                 return LDNS_STATUS_ERR;
52         }
53
54         /* this could be done more efficiently; name and type should already
55            be equal */
56         cmp = ldns_rr_compare(rrs->rr,
57                                           rr);
58         /* should we error on equal? */
59         if (cmp <= 0) {
60                 if (rrs->next) {
61                         return ldns_dnssec_rrs_add_rr(rrs->next, rr);
62                 } else {
63                         new_rrs = ldns_dnssec_rrs_new();
64                         new_rrs->rr = rr;
65                         rrs->next = new_rrs;
66                 }
67         } else if (cmp > 0) {
68                 /* put the current old rr in the new next, put the new
69                    rr in the current container */
70                 new_rrs = ldns_dnssec_rrs_new();
71                 new_rrs->rr = rrs->rr;
72                 new_rrs->next = rrs->next;
73                 rrs->rr = rr;
74                 rrs->next = new_rrs;
75         }
76         return LDNS_STATUS_OK;
77 }
78
79 void
80 ldns_dnssec_rrs_print(FILE *out, ldns_dnssec_rrs *rrs)
81 {
82         if (!rrs) {
83                 fprintf(out, "<void>");
84         } else {
85                 if (rrs->rr) {
86                         ldns_rr_print(out, rrs->rr);
87                 }
88                 if (rrs->next) {
89                         ldns_dnssec_rrs_print(out, rrs->next);
90                 }
91         }
92 }
93
94 ldns_dnssec_rrsets *
95 ldns_dnssec_rrsets_new()
96 {
97         ldns_dnssec_rrsets *new_rrsets;
98         new_rrsets = LDNS_MALLOC(ldns_dnssec_rrsets);
99         new_rrsets->rrs = NULL;
100         new_rrsets->type = 0;
101         new_rrsets->signatures = NULL;
102         new_rrsets->next = NULL;
103         return new_rrsets;
104 }
105
106 INLINE void
107 ldns_dnssec_rrsets_free_internal(ldns_dnssec_rrsets *rrsets, int deep)
108 {
109         if (rrsets) {
110                 if (rrsets->rrs) {
111                         ldns_dnssec_rrs_free_internal(rrsets->rrs, deep);
112                 }
113                 if (rrsets->next) {
114                         ldns_dnssec_rrsets_free_internal(rrsets->next, deep);
115                 }
116                 if (rrsets->signatures) {
117                         ldns_dnssec_rrs_free_internal(rrsets->signatures, deep);
118                 }
119                 LDNS_FREE(rrsets);
120         }
121 }
122
123 void
124 ldns_dnssec_rrsets_free(ldns_dnssec_rrsets *rrsets)
125 {
126         ldns_dnssec_rrsets_free_internal(rrsets, 0);
127 }
128
129 void
130 ldns_dnssec_rrsets_deep_free(ldns_dnssec_rrsets *rrsets)
131 {
132         ldns_dnssec_rrsets_free_internal(rrsets, 1);
133 }
134
135 ldns_rr_type
136 ldns_dnssec_rrsets_type(ldns_dnssec_rrsets *rrsets)
137 {
138         if (rrsets) {
139                 return rrsets->type;
140         } else {
141                 return 0;
142         }
143 }
144
145 ldns_status
146 ldns_dnssec_rrsets_set_type(ldns_dnssec_rrsets *rrsets,
147                                            ldns_rr_type type)
148 {
149         if (rrsets) {
150                 rrsets->type = type;
151                 return LDNS_STATUS_OK;
152         }
153         return LDNS_STATUS_ERR;
154 }
155
156 ldns_dnssec_rrsets *
157 ldns_dnssec_rrsets_new_frm_rr(ldns_rr *rr)
158 {
159         ldns_dnssec_rrsets *new_rrsets;
160         ldns_rr_type rr_type;
161         bool rrsig;
162
163         new_rrsets = ldns_dnssec_rrsets_new();
164         rr_type = ldns_rr_get_type(rr);
165         if (rr_type == LDNS_RR_TYPE_RRSIG) {
166                 rrsig = true;
167                 rr_type = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr));
168         } else {
169                 rrsig = false;
170         }
171         if (!rrsig) {
172                 new_rrsets->rrs = ldns_dnssec_rrs_new();
173                 new_rrsets->rrs->rr = rr;
174         } else {
175                 new_rrsets->signatures = ldns_dnssec_rrs_new();
176                 new_rrsets->signatures->rr = rr;
177         }
178         new_rrsets->type = rr_type;
179         return new_rrsets;
180 }
181
182 ldns_status
183 ldns_dnssec_rrsets_add_rr(ldns_dnssec_rrsets *rrsets, ldns_rr *rr)
184 {
185         ldns_dnssec_rrsets *new_rrsets;
186         ldns_rr_type rr_type;
187         bool rrsig = false;
188         ldns_status result = LDNS_STATUS_OK;
189
190         if (!rrsets || !rr) {
191                 return LDNS_STATUS_ERR;
192         }
193
194         rr_type = ldns_rr_get_type(rr);
195
196         if (rr_type == LDNS_RR_TYPE_RRSIG) {
197                 rrsig = true;
198                 rr_type = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr));
199         }
200
201         if (!rrsets->rrs && rrsets->type == 0 && !rrsets->signatures) {
202                 if (!rrsig) {
203                         rrsets->rrs = ldns_dnssec_rrs_new();
204                         rrsets->rrs->rr = rr;
205                         rrsets->type = rr_type;
206                 } else {
207                         rrsets->signatures = ldns_dnssec_rrs_new();
208                         rrsets->signatures->rr = rr;
209                         rrsets->type = rr_type;
210                 }
211                 return LDNS_STATUS_OK;
212         }
213
214         if (rr_type > ldns_dnssec_rrsets_type(rrsets)) {
215                 if (rrsets->next) {
216                         result = ldns_dnssec_rrsets_add_rr(rrsets->next, rr);
217                 } else {
218                         new_rrsets = ldns_dnssec_rrsets_new_frm_rr(rr);
219                         rrsets->next = new_rrsets;
220                 }
221         } else if (rr_type < ldns_dnssec_rrsets_type(rrsets)) {
222                 /* move the current one into the new next, 
223                    replace field of current with data from new rr */
224                 new_rrsets = ldns_dnssec_rrsets_new();
225                 new_rrsets->rrs = rrsets->rrs;
226                 new_rrsets->type = rrsets->type;
227                 new_rrsets->signatures = rrsets->signatures;
228                 new_rrsets->next = rrsets->next;
229                 if (!rrsig) {
230                         rrsets->rrs = ldns_dnssec_rrs_new();
231                         rrsets->rrs->rr = rr;
232                         rrsets->signatures = NULL;
233                 } else {
234                         rrsets->rrs = NULL;
235                         rrsets->signatures = ldns_dnssec_rrs_new();
236                         rrsets->signatures->rr = rr;
237                 }
238                 rrsets->type = rr_type;
239                 rrsets->next = new_rrsets;
240         } else {
241                 /* equal, add to current rrsets */
242                 if (rrsig) {
243                         if (rrsets->signatures) {
244                                 result = ldns_dnssec_rrs_add_rr(rrsets->signatures, rr);
245                         } else {
246                                 rrsets->signatures = ldns_dnssec_rrs_new();
247                                 rrsets->signatures->rr = rr;
248                         }
249                 } else {
250                         if (rrsets->rrs) {
251                                 result = ldns_dnssec_rrs_add_rr(rrsets->rrs, rr);
252                         } else {
253                                 rrsets->rrs = ldns_dnssec_rrs_new();
254                                 rrsets->rrs->rr = rr;
255                         }
256                 }
257         }
258
259         return result;
260 }
261
262 void
263 ldns_dnssec_rrsets_print_soa(FILE *out,
264                                             ldns_dnssec_rrsets *rrsets,
265                                             bool follow,
266                                             bool show_soa)
267 {
268         if (!rrsets) {
269                 fprintf(out, "<void>\n");
270         } else {
271                 if (rrsets->rrs &&
272                     (show_soa ||
273                         ldns_rr_get_type(rrsets->rrs->rr) != LDNS_RR_TYPE_SOA
274                     )
275                    ) {
276                         ldns_dnssec_rrs_print(out, rrsets->rrs);
277                         if (rrsets->signatures) {
278                                 ldns_dnssec_rrs_print(out, rrsets->signatures);
279                         }
280                 }
281                 if (follow && rrsets->next) {
282                         ldns_dnssec_rrsets_print_soa(out, rrsets->next, follow, show_soa);
283                 }
284         }
285 }
286
287 void
288 ldns_dnssec_rrsets_print(FILE *out, ldns_dnssec_rrsets *rrsets, bool follow)
289 {
290         ldns_dnssec_rrsets_print_soa(out, rrsets, follow, true);
291 }
292
293 ldns_dnssec_name *
294 ldns_dnssec_name_new()
295 {
296         ldns_dnssec_name *new_name;
297
298         new_name = LDNS_MALLOC(ldns_dnssec_name);
299         if (!new_name) {
300                 return NULL;
301         }
302
303         new_name->name = NULL;
304         new_name->rrsets = NULL;
305         new_name->name_alloced = false;
306         new_name->nsec = NULL;
307         new_name->nsec_signatures = NULL;
308
309         new_name->is_glue = false;
310         new_name->hashed_name = NULL;
311
312         return new_name;
313 }
314
315 ldns_dnssec_name *
316 ldns_dnssec_name_new_frm_rr(ldns_rr *rr)
317 {
318         ldns_dnssec_name *new_name = ldns_dnssec_name_new();
319
320         new_name->name = ldns_rr_owner(rr);
321         ldns_dnssec_name_add_rr(new_name, rr);
322
323         return new_name;
324 }
325
326 INLINE void
327 ldns_dnssec_name_free_internal(ldns_dnssec_name *name,
328                                int deep)
329 {
330         if (name) {
331                 if (name->name_alloced) {
332                         ldns_rdf_deep_free(name->name);
333                 }
334                 if (name->rrsets) {
335                         ldns_dnssec_rrsets_free_internal(name->rrsets, deep);
336                 }
337                 if (name->nsec && deep) {
338                         ldns_rr_free(name->nsec);
339                 }
340                 if (name->nsec_signatures) {
341                         ldns_dnssec_rrs_free_internal(name->nsec_signatures, deep);
342                 }
343                 if (name->hashed_name) {
344                         if (deep) {
345                                 ldns_rdf_deep_free(name->hashed_name);
346                         }
347                 }
348                 LDNS_FREE(name);
349         }
350 }
351
352 void
353 ldns_dnssec_name_free(ldns_dnssec_name *name)
354 {
355   ldns_dnssec_name_free_internal(name, 0);
356 }
357
358 void
359 ldns_dnssec_name_deep_free(ldns_dnssec_name *name)
360 {
361   ldns_dnssec_name_free_internal(name, 1);
362 }
363
364 ldns_rdf *
365 ldns_dnssec_name_name(ldns_dnssec_name *name)
366 {
367         if (name) {
368                 return name->name;
369         }
370         return NULL;
371 }
372
373 void
374 ldns_dnssec_name_set_name(ldns_dnssec_name *rrset,
375                                          ldns_rdf *dname)
376 {
377         if (rrset && dname) {
378                 rrset->name = dname;
379         }
380 }
381
382 ldns_rr *
383 ldns_dnssec_name_nsec(ldns_dnssec_name *rrset)
384 {
385         if (rrset) {
386                 return rrset->nsec;
387         }
388         return NULL;
389 }
390
391 void
392 ldns_dnssec_name_set_nsec(ldns_dnssec_name *rrset, ldns_rr *nsec)
393 {
394         if (rrset && nsec) {
395                 rrset->nsec = nsec;
396         }
397 }
398
399 int
400 ldns_dnssec_name_cmp(const void *a, const void *b)
401 {
402         ldns_dnssec_name *na = (ldns_dnssec_name *) a;
403         ldns_dnssec_name *nb = (ldns_dnssec_name *) b;
404
405         if (na && nb) {
406                 return ldns_dname_compare(ldns_dnssec_name_name(na),
407                                                          ldns_dnssec_name_name(nb));
408         } else if (na) {
409                 return 1;
410         } else if (nb) {
411                 return -1;
412         } else {
413                 return 0;
414         }
415 }
416
417 ldns_status
418 ldns_dnssec_name_add_rr(ldns_dnssec_name *name,
419                                     ldns_rr *rr)
420 {
421         ldns_status result = LDNS_STATUS_OK;
422         ldns_rdf *name_name;
423         bool hashed_name = false;
424         ldns_rr_type rr_type;
425         ldns_rr_type typecovered = 0;
426
427         /* special handling for NSEC3 and NSECX covering RRSIGS */
428
429         if (!name || !rr) {
430                 return LDNS_STATUS_ERR;
431         }
432
433         rr_type = ldns_rr_get_type(rr);
434
435         if (rr_type == LDNS_RR_TYPE_RRSIG) {
436                 typecovered = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr));
437         }
438
439 #ifdef HAVE_SSL
440         if (rr_type == LDNS_RR_TYPE_NSEC3 ||
441             typecovered == LDNS_RR_TYPE_NSEC3) {
442                 name_name = ldns_nsec3_hash_name_frm_nsec3(rr,
443                                                                                    ldns_dnssec_name_name(name));
444                 hashed_name = true;
445         } else {
446                 name_name = ldns_dnssec_name_name(name);
447         }
448 #else
449         name_name = ldns_dnssec_name_name(name);
450 #endif /* HAVE_SSL */
451
452         if (rr_type == LDNS_RR_TYPE_NSEC ||
453             rr_type == LDNS_RR_TYPE_NSEC3) {
454                 /* XX check if is already set (and error?) */
455                 name->nsec = rr;
456         } else if (typecovered == LDNS_RR_TYPE_NSEC ||
457                          typecovered == LDNS_RR_TYPE_NSEC3) {
458                 if (name->nsec_signatures) {
459                         ldns_dnssec_rrs_add_rr(name->nsec_signatures, rr);
460                 } else {
461                         name->nsec_signatures = ldns_dnssec_rrs_new();
462                         name->nsec_signatures->rr = rr;
463                 }
464         } else {
465                 /* it's a 'normal' RR, add it to the right rrset */
466                 if (name->rrsets) {
467                         result = ldns_dnssec_rrsets_add_rr(name->rrsets, rr);
468                 } else {
469                         name->rrsets = ldns_dnssec_rrsets_new();
470                         result = ldns_dnssec_rrsets_add_rr(name->rrsets, rr);
471                 }
472         }
473
474         if (hashed_name) {
475                 ldns_rdf_deep_free(name_name);
476         }
477
478         return result;
479 }
480
481 ldns_dnssec_rrsets *
482 ldns_dnssec_name_find_rrset(ldns_dnssec_name *name,
483                                            ldns_rr_type type) {
484         ldns_dnssec_rrsets *result;
485
486         result = name->rrsets;
487         while (result) {
488                 if (result->type == type) {
489                         return result;
490                 } else {
491                         result = result->next;
492                 }
493         }
494         return NULL;
495 }
496
497 ldns_dnssec_rrsets *
498 ldns_dnssec_zone_find_rrset(ldns_dnssec_zone *zone,
499                                            ldns_rdf *dname,
500                                            ldns_rr_type type)
501 {
502         ldns_rbnode_t *node;
503
504         if (!zone || !dname) {
505                 return NULL;
506         }
507
508         node = ldns_rbtree_search(zone->names, dname);
509         if (node) {
510                 return ldns_dnssec_name_find_rrset((ldns_dnssec_name *)node->data,
511                                                                         type);
512         } else {
513                 return NULL;
514         }
515 }
516
517 static inline void
518 print_indent(FILE *out, int c)
519 {
520         int i;
521         for (i=0; i<c; i++) {
522                 fprintf(out, "    ");
523         }
524 }
525
526 void
527 ldns_dnssec_name_print_soa(FILE *out, ldns_dnssec_name *name, bool show_soa)
528 {
529         if (name) {
530                 if(name->rrsets) {
531                         ldns_dnssec_rrsets_print_soa(out, name->rrsets, true, show_soa);
532                 } else {
533                         fprintf(out, ";; Empty nonterminal: ");
534                         ldns_rdf_print(out, name->name);
535                         fprintf(out, "\n");
536                 }
537                 if(name->nsec) {
538                         ldns_rr_print(out, name->nsec);
539                 }
540                 if (name->nsec_signatures) {
541                         ldns_dnssec_rrs_print(out, name->nsec_signatures);
542                 }
543         } else {
544                 fprintf(out, "<void>\n");
545         }
546 }
547
548 void
549 ldns_dnssec_name_print(FILE *out, ldns_dnssec_name *name)
550 {
551         ldns_dnssec_name_print_soa(out, name, true);
552 }
553
554 ldns_dnssec_zone *
555 ldns_dnssec_zone_new()
556 {
557         ldns_dnssec_zone *zone = LDNS_MALLOC(ldns_dnssec_zone);
558         zone->soa = NULL;
559         zone->names = NULL;
560
561         return zone;
562 }
563
564 void
565 ldns_dnssec_name_node_free(ldns_rbnode_t *node, void *arg) {
566         (void) arg;
567         ldns_dnssec_name_free((ldns_dnssec_name *)node->data);
568         free(node);
569 }
570
571 void
572 ldns_dnssec_name_node_deep_free(ldns_rbnode_t *node, void *arg) {
573         (void) arg;
574         ldns_dnssec_name_deep_free((ldns_dnssec_name *)node->data);
575         free(node);
576 }
577
578 void
579 ldns_dnssec_zone_free(ldns_dnssec_zone *zone)
580 {
581         if (zone) {
582                 if (zone->names) {
583                         /* destroy all name structures within the tree */
584                         ldns_traverse_postorder(zone->names,
585                                                     ldns_dnssec_name_node_free,
586                                                     NULL);
587                         free(zone->names);
588                 }
589                 LDNS_FREE(zone);
590         }
591 }
592
593 void
594 ldns_dnssec_zone_deep_free(ldns_dnssec_zone *zone)
595 {
596         if (zone) {
597                 if (zone->names) {
598                         /* destroy all name structures within the tree */
599                         ldns_traverse_postorder(zone->names,
600                                                     ldns_dnssec_name_node_deep_free,
601                                                     NULL);
602                         free(zone->names);
603                 }
604                 LDNS_FREE(zone);
605         }
606 }
607
608 /* use for dname comparison in tree */
609 int
610 ldns_dname_compare_v(const void *a, const void *b) {
611         return ldns_dname_compare((ldns_rdf *)a, (ldns_rdf *)b);
612 }
613
614 #ifdef HAVE_SSL
615 ldns_rbnode_t *
616 ldns_dnssec_zone_find_nsec3_original(ldns_dnssec_zone *zone,
617                                      ldns_rr *rr) {
618         ldns_rbnode_t *current_node = ldns_rbtree_first(zone->names);
619         ldns_dnssec_name *current_name;
620         ldns_rdf *hashed_name;
621
622         hashed_name = ldns_dname_label(ldns_rr_owner(rr), 0);
623
624         while (current_node != LDNS_RBTREE_NULL) {
625                 current_name = (ldns_dnssec_name *) current_node->data;
626                 if (!current_name->hashed_name) {
627                         current_name->hashed_name =
628                                 ldns_nsec3_hash_name_frm_nsec3(rr, current_name->name);
629                 }
630                 if (ldns_dname_compare(hashed_name,
631                                                    current_name->hashed_name)
632                     == 0) {
633                         ldns_rdf_deep_free(hashed_name);
634                         return current_node;
635                 }
636                 current_node = ldns_rbtree_next(current_node);
637         }
638         ldns_rdf_deep_free(hashed_name);
639         return NULL;
640 }
641
642 ldns_status
643 ldns_dnssec_zone_add_rr(ldns_dnssec_zone *zone, ldns_rr *rr)
644 {
645         ldns_status result = LDNS_STATUS_OK;
646         ldns_dnssec_name *cur_name;
647         ldns_rbnode_t *cur_node;
648         ldns_rr_type type_covered = 0;
649
650         if (!zone || !rr) {
651                 return LDNS_STATUS_ERR;
652         }
653
654         if (!zone->names) {
655                 zone->names = ldns_rbtree_create(ldns_dname_compare_v);
656         }
657
658         /* we need the original of the hashed name if this is
659            an NSEC3, or an RRSIG that covers an NSEC3 */
660         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_RRSIG) {
661                 type_covered = ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rr));
662         }
663         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_NSEC3 ||
664             type_covered == LDNS_RR_TYPE_NSEC3) {
665                 cur_node = ldns_dnssec_zone_find_nsec3_original(zone,
666                                                                                            rr);
667                 if (!cur_node) {
668                         return LDNS_STATUS_DNSSEC_NSEC3_ORIGINAL_NOT_FOUND;
669                 }
670         } else {
671                 cur_node = ldns_rbtree_search(zone->names, ldns_rr_owner(rr));
672         }
673
674         if (!cur_node) {
675                 /* add */
676                 cur_name = ldns_dnssec_name_new_frm_rr(rr);
677                 cur_node = LDNS_MALLOC(ldns_rbnode_t);
678                 cur_node->key = ldns_rr_owner(rr);
679                 cur_node->data = cur_name;
680                 ldns_rbtree_insert(zone->names, cur_node);
681         } else {
682                 cur_name = (ldns_dnssec_name *) cur_node->data;
683                 ldns_dnssec_name_add_rr(cur_name, rr);
684         }
685
686         if (result != LDNS_STATUS_OK) {
687                 fprintf(stderr, "error adding rr: ");
688                 ldns_rr_print(stderr, rr);
689         }
690
691         /*TODO ldns_dnssec_name_print_names(stdout, zone->names, 0);*/
692         if (ldns_rr_get_type(rr) == LDNS_RR_TYPE_SOA) {
693                 zone->soa = cur_name;
694         }
695
696         return result;
697 }
698 #endif /* HAVE_SSL */
699
700 void
701 ldns_dnssec_zone_names_print(FILE *out, ldns_rbtree_t *tree, bool print_soa)
702 {
703         ldns_rbnode_t *node;
704         ldns_dnssec_name *name;
705
706         node = ldns_rbtree_first(tree);
707         while (node != LDNS_RBTREE_NULL) {
708                 name = (ldns_dnssec_name *) node->data;
709                 ldns_dnssec_name_print_soa(out, name, print_soa);
710                 fprintf(out, ";\n");
711                 node = ldns_rbtree_next(node);
712         }
713 }
714
715 void
716 ldns_dnssec_zone_print(FILE *out, ldns_dnssec_zone *zone)
717 {
718         if (zone) {
719                 if (zone->soa) {
720                         fprintf(out, ";; Zone: ");
721                         ldns_rdf_print(out, ldns_dnssec_name_name(zone->soa));
722                         fprintf(out, "\n;\n");
723                         ldns_dnssec_rrsets_print(
724                             out,
725                             ldns_dnssec_name_find_rrset(zone->soa,
726                                                                           LDNS_RR_TYPE_SOA),
727                             false);
728                         fprintf(out, ";\n");
729                 }
730
731                 if (zone->names) {
732                         ldns_dnssec_zone_names_print(out, zone->names, false);
733                 }
734         }
735 }
736
737 ldns_status
738 ldns_dnssec_zone_add_empty_nonterminals(ldns_dnssec_zone *zone)
739 {
740         ldns_dnssec_name *new_name;
741         ldns_rdf *cur_name;
742         ldns_rdf *next_name;
743         ldns_rbnode_t *cur_node, *next_node, *new_node;
744
745         /* for the detection */
746         uint16_t i, cur_label_count, next_label_count;
747         uint16_t soa_label_count = 0;
748         ldns_rdf *l1, *l2;
749         int lpos;
750
751         if (!zone) {
752                 return LDNS_STATUS_ERR;
753         }
754         if (zone->soa && zone->soa->name) {
755                 soa_label_count = ldns_dname_label_count(zone->soa->name);
756         }
757         
758         cur_node = ldns_rbtree_first(zone->names);
759         while (cur_node != LDNS_RBTREE_NULL) {
760                 next_node = ldns_rbtree_next(cur_node);
761                 
762                 /* skip glue */
763                 while (next_node != LDNS_RBTREE_NULL && 
764                        next_node->data &&
765                        ((ldns_dnssec_name *)next_node->data)->is_glue
766                 ) {
767                         next_node = ldns_rbtree_next(next_node);
768                 }
769
770                 if (next_node == LDNS_RBTREE_NULL) {
771                         next_node = ldns_rbtree_first(zone->names);
772                 }
773
774                 cur_name = ((ldns_dnssec_name *)cur_node->data)->name;
775                 next_name = ((ldns_dnssec_name *)next_node->data)->name;
776                 cur_label_count = ldns_dname_label_count(cur_name);
777                 next_label_count = ldns_dname_label_count(next_name);
778
779                 /* Since the names are in canonical order, we can
780                  * recognize empty non-terminals by their labels;
781                  * every label after the first one on the next owner
782                  * name is a non-terminal if it either does not exist
783                  * in the current name or is different from the same
784                  * label in the current name (counting from the end)
785                  */
786                 for (i = 1; i < next_label_count - soa_label_count; i++) {
787                         lpos = cur_label_count - next_label_count + i;
788                         if (lpos >= 0) {
789                                 l1 = ldns_dname_label(cur_name, lpos);
790                         } else {
791                                 l1 = NULL;
792                         }
793                         l2 = ldns_dname_label(next_name, i);
794
795                         if (!l1 || ldns_dname_compare(l1, l2) != 0) {
796                                 /* We have an empty nonterminal, add it to the
797                                  * tree
798                                  */
799                                 new_name = ldns_dnssec_name_new();
800                                 if (!new_name) {
801                                         return LDNS_STATUS_MEM_ERR;
802                                 }
803                                 new_name->name = ldns_dname_clone_from(next_name,
804                                                                        i);
805                                 if (!new_name) {
806                                         ldns_dnssec_name_free(new_name);
807                                         return LDNS_STATUS_MEM_ERR;
808                                 }
809                                 new_name->name_alloced = true;
810                                 new_node = LDNS_MALLOC(ldns_rbnode_t);
811                                 if (!new_node) {
812                                         ldns_dnssec_name_free(new_name);
813                                         return LDNS_STATUS_MEM_ERR;
814                                 }
815                                 new_node->key = new_name->name;
816                                 new_node->data = new_name;
817                                 ldns_rbtree_insert(zone->names, new_node);
818                         }
819                         ldns_rdf_deep_free(l1);
820                         ldns_rdf_deep_free(l2);
821                 }
822                 
823                 /* we might have inserted a new node after
824                  * the current one so we can't just use next()
825                  */
826                 if (next_node != ldns_rbtree_first(zone->names)) {
827                         cur_node = next_node;
828                 } else {
829                         cur_node = LDNS_RBTREE_NULL;
830                 }
831         }
832         return LDNS_STATUS_OK;
833 }