d4b550e4cfdd2b2bf512edcb7eb2944532f0e0cd
[openssl.git] / crypto / x509v3 / pcy_tree.c
1 /* pcy_tree.c */
2 /*
3  * Written by Dr Stephen N Henson (steve@openssl.org) for the OpenSSL project
4  * 2004.
5  */
6 /* ====================================================================
7  * Copyright (c) 2004 The OpenSSL Project.  All rights reserved.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  *
13  * 1. Redistributions of source code must retain the above copyright
14  *    notice, this list of conditions and the following disclaimer.
15  *
16  * 2. Redistributions in binary form must reproduce the above copyright
17  *    notice, this list of conditions and the following disclaimer in
18  *    the documentation and/or other materials provided with the
19  *    distribution.
20  *
21  * 3. All advertising materials mentioning features or use of this
22  *    software must display the following acknowledgment:
23  *    "This product includes software developed by the OpenSSL Project
24  *    for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"
25  *
26  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
27  *    endorse or promote products derived from this software without
28  *    prior written permission. For written permission, please contact
29  *    licensing@OpenSSL.org.
30  *
31  * 5. Products derived from this software may not be called "OpenSSL"
32  *    nor may "OpenSSL" appear in their names without prior written
33  *    permission of the OpenSSL Project.
34  *
35  * 6. Redistributions of any form whatsoever must retain the following
36  *    acknowledgment:
37  *    "This product includes software developed by the OpenSSL Project
38  *    for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"
39  *
40  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
41  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
43  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
44  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
45  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
46  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
47  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
49  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
50  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
51  * OF THE POSSIBILITY OF SUCH DAMAGE.
52  * ====================================================================
53  *
54  * This product includes cryptographic software written by Eric Young
55  * (eay@cryptsoft.com).  This product includes software written by Tim
56  * Hudson (tjh@cryptsoft.com).
57  *
58  */
59
60 #include "cryptlib.h"
61 #include <openssl/x509.h>
62 #include <openssl/x509v3.h>
63
64 #include "pcy_int.h"
65
66 /*
67  * Enable this to print out the complete policy tree at various point during
68  * evaluation.
69  */
70
71 /*
72  * #define OPENSSL_POLICY_DEBUG
73  */
74
75 #ifdef OPENSSL_POLICY_DEBUG
76
77 static void expected_print(BIO *err, X509_POLICY_LEVEL *lev,
78                            X509_POLICY_NODE *node, int indent)
79 {
80     if ((lev->flags & X509_V_FLAG_INHIBIT_MAP)
81         || !(node->data->flags & POLICY_DATA_FLAG_MAP_MASK))
82         BIO_puts(err, "  Not Mapped\n");
83     else {
84         int i;
85         STACK_OF(ASN1_OBJECT) *pset = node->data->expected_policy_set;
86         ASN1_OBJECT *oid;
87         BIO_puts(err, "  Expected: ");
88         for (i = 0; i < sk_ASN1_OBJECT_num(pset); i++) {
89             oid = sk_ASN1_OBJECT_value(pset, i);
90             if (i)
91                 BIO_puts(err, ", ");
92             i2a_ASN1_OBJECT(err, oid);
93         }
94         BIO_puts(err, "\n");
95     }
96 }
97
98 static void tree_print(char *str, X509_POLICY_TREE *tree,
99                        X509_POLICY_LEVEL *curr)
100 {
101     X509_POLICY_LEVEL *plev;
102     X509_POLICY_NODE *node;
103     int i;
104     BIO *err;
105     err = BIO_new_fp(stderr, BIO_NOCLOSE);
106     if (err == NULL)
107         return;
108     if (!curr)
109         curr = tree->levels + tree->nlevel;
110     else
111         curr++;
112     BIO_printf(err, "Level print after %s\n", str);
113     BIO_printf(err, "Printing Up to Level %ld\n", curr - tree->levels);
114     for (plev = tree->levels; plev != curr; plev++) {
115         BIO_printf(err, "Level %ld, flags = %x\n",
116                    plev - tree->levels, plev->flags);
117         for (i = 0; i < sk_X509_POLICY_NODE_num(plev->nodes); i++) {
118             node = sk_X509_POLICY_NODE_value(plev->nodes, i);
119             X509_POLICY_NODE_print(err, node, 2);
120             expected_print(err, plev, node, 2);
121             BIO_printf(err, "  Flags: %x\n", node->data->flags);
122         }
123         if (plev->anyPolicy)
124             X509_POLICY_NODE_print(err, plev->anyPolicy, 2);
125     }
126
127     BIO_free(err);
128
129 }
130 #else
131
132 # define tree_print(a,b,c)      /* */
133
134 #endif
135
136 /*-
137  * Initialize policy tree. Return values:
138  *  0 Some internal error occurred.
139  * -1 Inconsistent or invalid extensions in certificates.
140  *  1 Tree initialized OK.
141  *  2 Policy tree is empty.
142  *  5 Tree OK and requireExplicitPolicy true.
143  *  6 Tree empty and requireExplicitPolicy true.
144  */
145
146 static int tree_init(X509_POLICY_TREE **ptree, STACK_OF(X509) *certs,
147                      unsigned int flags)
148 {
149     X509_POLICY_TREE *tree;
150     X509_POLICY_LEVEL *level;
151     const X509_POLICY_CACHE *cache;
152     X509_POLICY_DATA *data = NULL;
153     X509 *x;
154     int ret = 1;
155     int i, n;
156     int explicit_policy;
157     int any_skip;
158     int map_skip;
159     *ptree = NULL;
160     n = sk_X509_num(certs);
161
162 #if 0
163     /* Disable policy mapping for now... */
164     flags |= X509_V_FLAG_INHIBIT_MAP;
165 #endif
166
167     if (flags & X509_V_FLAG_EXPLICIT_POLICY)
168         explicit_policy = 0;
169     else
170         explicit_policy = n + 1;
171
172     if (flags & X509_V_FLAG_INHIBIT_ANY)
173         any_skip = 0;
174     else
175         any_skip = n + 1;
176
177     if (flags & X509_V_FLAG_INHIBIT_MAP)
178         map_skip = 0;
179     else
180         map_skip = n + 1;
181
182     /* Can't do anything with just a trust anchor */
183     if (n == 1)
184         return 1;
185     /*
186      * First setup policy cache in all certificates apart from the trust
187      * anchor. Note any bad cache results on the way. Also can calculate
188      * explicit_policy value at this point.
189      */
190     for (i = n - 2; i >= 0; i--) {
191         x = sk_X509_value(certs, i);
192         X509_check_purpose(x, -1, -1);
193         cache = policy_cache_set(x);
194         /* If cache NULL something bad happened: return immediately */
195         if (cache == NULL)
196             return 0;
197         /*
198          * If inconsistent extensions keep a note of it but continue
199          */
200         if (x->ex_flags & EXFLAG_INVALID_POLICY)
201             ret = -1;
202         /*
203          * Otherwise if we have no data (hence no CertificatePolicies) and
204          * haven't already set an inconsistent code note it.
205          */
206         else if ((ret == 1) && !cache->data)
207             ret = 2;
208         if (explicit_policy > 0) {
209             if (!(x->ex_flags & EXFLAG_SI))
210                 explicit_policy--;
211             if ((cache->explicit_skip != -1)
212                 && (cache->explicit_skip < explicit_policy))
213                 explicit_policy = cache->explicit_skip;
214         }
215     }
216
217     if (ret != 1) {
218         if (ret == 2 && !explicit_policy)
219             return 6;
220         return ret;
221     }
222
223     /* If we get this far initialize the tree */
224
225     tree = OPENSSL_malloc(sizeof(X509_POLICY_TREE));
226
227     if (!tree)
228         return 0;
229
230     tree->flags = 0;
231     tree->levels = OPENSSL_malloc(sizeof(X509_POLICY_LEVEL) * n);
232     tree->nlevel = 0;
233     tree->extra_data = NULL;
234     tree->auth_policies = NULL;
235     tree->user_policies = NULL;
236
237     if (!tree->levels) {
238         OPENSSL_free(tree);
239         return 0;
240     }
241
242     memset(tree->levels, 0, n * sizeof(X509_POLICY_LEVEL));
243
244     tree->nlevel = n;
245
246     level = tree->levels;
247
248     /* Root data: initialize to anyPolicy */
249
250     data = policy_data_new(NULL, OBJ_nid2obj(NID_any_policy), 0);
251
252     if (!data || !level_add_node(level, data, NULL, tree))
253         goto bad_tree;
254
255     for (i = n - 2; i >= 0; i--) {
256         level++;
257         x = sk_X509_value(certs, i);
258         cache = policy_cache_set(x);
259         CRYPTO_add(&x->references, 1, CRYPTO_LOCK_X509);
260         level->cert = x;
261
262         if (!cache->anyPolicy)
263             level->flags |= X509_V_FLAG_INHIBIT_ANY;
264
265         /* Determine inhibit any and inhibit map flags */
266         if (any_skip == 0) {
267             /*
268              * Any matching allowed if certificate is self issued and not the
269              * last in the chain.
270              */
271             if (!(x->ex_flags & EXFLAG_SI) || (i == 0))
272                 level->flags |= X509_V_FLAG_INHIBIT_ANY;
273         } else {
274             if (!(x->ex_flags & EXFLAG_SI))
275                 any_skip--;
276             if ((cache->any_skip >= 0)
277                 && (cache->any_skip < any_skip))
278                 any_skip = cache->any_skip;
279         }
280
281         if (map_skip == 0)
282             level->flags |= X509_V_FLAG_INHIBIT_MAP;
283         else {
284             if (!(x->ex_flags & EXFLAG_SI))
285                 map_skip--;
286             if ((cache->map_skip >= 0)
287                 && (cache->map_skip < map_skip))
288                 map_skip = cache->map_skip;
289         }
290
291     }
292
293     *ptree = tree;
294
295     if (explicit_policy)
296         return 1;
297     else
298         return 5;
299
300  bad_tree:
301
302     X509_policy_tree_free(tree);
303
304     return 0;
305
306 }
307
308 static int tree_link_matching_nodes(X509_POLICY_LEVEL *curr,
309                                     const X509_POLICY_DATA *data)
310 {
311     X509_POLICY_LEVEL *last = curr - 1;
312     X509_POLICY_NODE *node;
313     int i, matched = 0;
314     /* Iterate through all in nodes linking matches */
315     for (i = 0; i < sk_X509_POLICY_NODE_num(last->nodes); i++) {
316         node = sk_X509_POLICY_NODE_value(last->nodes, i);
317         if (policy_node_match(last, node, data->valid_policy)) {
318             if (!level_add_node(curr, data, node, NULL))
319                 return 0;
320             matched = 1;
321         }
322     }
323     if (!matched && last->anyPolicy) {
324         if (!level_add_node(curr, data, last->anyPolicy, NULL))
325             return 0;
326     }
327     return 1;
328 }
329
330 /*
331  * This corresponds to RFC3280 6.1.3(d)(1): link any data from
332  * CertificatePolicies onto matching parent or anyPolicy if no match.
333  */
334
335 static int tree_link_nodes(X509_POLICY_LEVEL *curr,
336                            const X509_POLICY_CACHE *cache)
337 {
338     int i;
339     X509_POLICY_DATA *data;
340
341     for (i = 0; i < sk_X509_POLICY_DATA_num(cache->data); i++) {
342         data = sk_X509_POLICY_DATA_value(cache->data, i);
343         /*
344          * If a node is mapped any it doesn't have a corresponding
345          * CertificatePolicies entry. However such an identical node would
346          * be created if anyPolicy matching is enabled because there would be
347          * no match with the parent valid_policy_set. So we create link
348          * because then it will have the mapping flags right and we can prune
349          * it later.
350          */
351 #if 0
352         if ((data->flags & POLICY_DATA_FLAG_MAPPED_ANY)
353             && !(curr->flags & X509_V_FLAG_INHIBIT_ANY))
354             continue;
355 #endif
356         /* Look for matching nodes in previous level */
357         if (!tree_link_matching_nodes(curr, data))
358             return 0;
359     }
360     return 1;
361 }
362
363 /*
364  * This corresponds to RFC3280 6.1.3(d)(2): Create new data for any unmatched
365  * policies in the parent and link to anyPolicy.
366  */
367
368 static int tree_add_unmatched(X509_POLICY_LEVEL *curr,
369                               const X509_POLICY_CACHE *cache,
370                               const ASN1_OBJECT *id,
371                               X509_POLICY_NODE *node, X509_POLICY_TREE *tree)
372 {
373     X509_POLICY_DATA *data;
374     if (id == NULL)
375         id = node->data->valid_policy;
376     /*
377      * Create a new node with qualifiers from anyPolicy and id from unmatched
378      * node.
379      */
380     data = policy_data_new(NULL, id, node_critical(node));
381
382     if (data == NULL)
383         return 0;
384     /* Curr may not have anyPolicy */
385     data->qualifier_set = cache->anyPolicy->qualifier_set;
386     data->flags |= POLICY_DATA_FLAG_SHARED_QUALIFIERS;
387     if (!level_add_node(curr, data, node, tree)) {
388         policy_data_free(data);
389         return 0;
390     }
391
392     return 1;
393 }
394
395 static int tree_link_unmatched(X509_POLICY_LEVEL *curr,
396                                const X509_POLICY_CACHE *cache,
397                                X509_POLICY_NODE *node, X509_POLICY_TREE *tree)
398 {
399     const X509_POLICY_LEVEL *last = curr - 1;
400     int i;
401
402     if ((last->flags & X509_V_FLAG_INHIBIT_MAP)
403         || !(node->data->flags & POLICY_DATA_FLAG_MAPPED)) {
404         /* If no policy mapping: matched if one child present */
405         if (node->nchild)
406             return 1;
407         if (!tree_add_unmatched(curr, cache, NULL, node, tree))
408             return 0;
409         /* Add it */
410     } else {
411         /* If mapping: matched if one child per expected policy set */
412         STACK_OF(ASN1_OBJECT) *expset = node->data->expected_policy_set;
413         if (node->nchild == sk_ASN1_OBJECT_num(expset))
414             return 1;
415         /* Locate unmatched nodes */
416         for (i = 0; i < sk_ASN1_OBJECT_num(expset); i++) {
417             ASN1_OBJECT *oid = sk_ASN1_OBJECT_value(expset, i);
418             if (level_find_node(curr, node, oid))
419                 continue;
420             if (!tree_add_unmatched(curr, cache, oid, node, tree))
421                 return 0;
422         }
423
424     }
425
426     return 1;
427
428 }
429
430 static int tree_link_any(X509_POLICY_LEVEL *curr,
431                          const X509_POLICY_CACHE *cache,
432                          X509_POLICY_TREE *tree)
433 {
434     int i;
435     /*
436      * X509_POLICY_DATA *data;
437      */
438     X509_POLICY_NODE *node;
439     X509_POLICY_LEVEL *last = curr - 1;
440
441     for (i = 0; i < sk_X509_POLICY_NODE_num(last->nodes); i++) {
442         node = sk_X509_POLICY_NODE_value(last->nodes, i);
443
444         if (!tree_link_unmatched(curr, cache, node, tree))
445             return 0;
446
447 #if 0
448
449         /*
450          * Skip any node with any children: we only want unmathced nodes.
451          * Note: need something better for policy mapping because each node
452          * may have multiple children
453          */
454         if (node->nchild)
455             continue;
456
457         /*
458          * Create a new node with qualifiers from anyPolicy and id from
459          * unmatched node.
460          */
461         data = policy_data_new(NULL, node->data->valid_policy,
462                                node_critical(node));
463
464         if (data == NULL)
465             return 0;
466         /* Curr may not have anyPolicy */
467         data->qualifier_set = cache->anyPolicy->qualifier_set;
468         data->flags |= POLICY_DATA_FLAG_SHARED_QUALIFIERS;
469         if (!level_add_node(curr, data, node, tree)) {
470             policy_data_free(data);
471             return 0;
472         }
473 #endif
474
475     }
476     /* Finally add link to anyPolicy */
477     if (last->anyPolicy) {
478         if (!level_add_node(curr, cache->anyPolicy, last->anyPolicy, NULL))
479             return 0;
480     }
481     return 1;
482 }
483
484 /*
485  * Prune the tree: delete any child mapped child data on the current level
486  * then proceed up the tree deleting any data with no children. If we ever
487  * have no data on a level we can halt because the tree will be empty.
488  */
489
490 static int tree_prune(X509_POLICY_TREE *tree, X509_POLICY_LEVEL *curr)
491 {
492     STACK_OF(X509_POLICY_NODE) *nodes;
493     X509_POLICY_NODE *node;
494     int i;
495     nodes = curr->nodes;
496     if (curr->flags & X509_V_FLAG_INHIBIT_MAP) {
497         for (i = sk_X509_POLICY_NODE_num(nodes) - 1; i >= 0; i--) {
498             node = sk_X509_POLICY_NODE_value(nodes, i);
499             /* Delete any mapped data: see RFC3280 XXXX */
500             if (node->data->flags & POLICY_DATA_FLAG_MAP_MASK) {
501                 node->parent->nchild--;
502                 OPENSSL_free(node);
503                 (void)sk_X509_POLICY_NODE_delete(nodes, i);
504             }
505         }
506     }
507
508     for (;;) {
509         --curr;
510         nodes = curr->nodes;
511         for (i = sk_X509_POLICY_NODE_num(nodes) - 1; i >= 0; i--) {
512             node = sk_X509_POLICY_NODE_value(nodes, i);
513             if (node->nchild == 0) {
514                 node->parent->nchild--;
515                 OPENSSL_free(node);
516                 (void)sk_X509_POLICY_NODE_delete(nodes, i);
517             }
518         }
519         if (curr->anyPolicy && !curr->anyPolicy->nchild) {
520             if (curr->anyPolicy->parent)
521                 curr->anyPolicy->parent->nchild--;
522             OPENSSL_free(curr->anyPolicy);
523             curr->anyPolicy = NULL;
524         }
525         if (curr == tree->levels) {
526             /* If we zapped anyPolicy at top then tree is empty */
527             if (!curr->anyPolicy)
528                 return 2;
529             return 1;
530         }
531     }
532
533     /* Unreachable */
534
535 }
536
537 static int tree_add_auth_node(STACK_OF(X509_POLICY_NODE) **pnodes,
538                               X509_POLICY_NODE *pcy)
539 {
540     if (!*pnodes) {
541         *pnodes = policy_node_cmp_new();
542         if (!*pnodes)
543             return 0;
544     } else if (sk_X509_POLICY_NODE_find(*pnodes, pcy) != -1)
545         return 1;
546
547     if (!sk_X509_POLICY_NODE_push(*pnodes, pcy))
548         return 0;
549
550     return 1;
551
552 }
553
554 /*
555  * Calculate the authority set based on policy tree. The 'pnodes' parameter
556  * is used as a store for the set of policy nodes used to calculate the user
557  * set. If the authority set is not anyPolicy then pnodes will just point to
558  * the authority set. If however the authority set is anyPolicy then the set
559  * of valid policies (other than anyPolicy) is store in pnodes. The return
560  * value of '2' is used in this case to indicate that pnodes should be freed.
561  */
562
563 static int tree_calculate_authority_set(X509_POLICY_TREE *tree,
564                                         STACK_OF(X509_POLICY_NODE) **pnodes)
565 {
566     X509_POLICY_LEVEL *curr;
567     X509_POLICY_NODE *node, *anyptr;
568     STACK_OF(X509_POLICY_NODE) **addnodes;
569     int i, j;
570     curr = tree->levels + tree->nlevel - 1;
571
572     /* If last level contains anyPolicy set is anyPolicy */
573     if (curr->anyPolicy) {
574         if (!tree_add_auth_node(&tree->auth_policies, curr->anyPolicy))
575             return 0;
576         addnodes = pnodes;
577     } else
578         /* Add policies to authority set */
579         addnodes = &tree->auth_policies;
580
581     curr = tree->levels;
582     for (i = 1; i < tree->nlevel; i++) {
583         /*
584          * If no anyPolicy node on this this level it can't appear on lower
585          * levels so end search.
586          */
587         if (!(anyptr = curr->anyPolicy))
588             break;
589         curr++;
590         for (j = 0; j < sk_X509_POLICY_NODE_num(curr->nodes); j++) {
591             node = sk_X509_POLICY_NODE_value(curr->nodes, j);
592             if ((node->parent == anyptr)
593                 && !tree_add_auth_node(addnodes, node))
594                 return 0;
595         }
596     }
597
598     if (addnodes == pnodes)
599         return 2;
600
601     *pnodes = tree->auth_policies;
602
603     return 1;
604 }
605
606 static int tree_calculate_user_set(X509_POLICY_TREE *tree,
607                                    STACK_OF(ASN1_OBJECT) *policy_oids,
608                                    STACK_OF(X509_POLICY_NODE) *auth_nodes)
609 {
610     int i;
611     X509_POLICY_NODE *node;
612     ASN1_OBJECT *oid;
613
614     X509_POLICY_NODE *anyPolicy;
615     X509_POLICY_DATA *extra;
616
617     /*
618      * Check if anyPolicy present in authority constrained policy set: this
619      * will happen if it is a leaf node.
620      */
621
622     if (sk_ASN1_OBJECT_num(policy_oids) <= 0)
623         return 1;
624
625     anyPolicy = tree->levels[tree->nlevel - 1].anyPolicy;
626
627     for (i = 0; i < sk_ASN1_OBJECT_num(policy_oids); i++) {
628         oid = sk_ASN1_OBJECT_value(policy_oids, i);
629         if (OBJ_obj2nid(oid) == NID_any_policy) {
630             tree->flags |= POLICY_FLAG_ANY_POLICY;
631             return 1;
632         }
633     }
634
635     for (i = 0; i < sk_ASN1_OBJECT_num(policy_oids); i++) {
636         oid = sk_ASN1_OBJECT_value(policy_oids, i);
637         node = tree_find_sk(auth_nodes, oid);
638         if (!node) {
639             if (!anyPolicy)
640                 continue;
641             /*
642              * Create a new node with policy ID from user set and qualifiers
643              * from anyPolicy.
644              */
645             extra = policy_data_new(NULL, oid, node_critical(anyPolicy));
646             if (!extra)
647                 return 0;
648             extra->qualifier_set = anyPolicy->data->qualifier_set;
649             extra->flags = POLICY_DATA_FLAG_SHARED_QUALIFIERS
650                 | POLICY_DATA_FLAG_EXTRA_NODE;
651             node = level_add_node(NULL, extra, anyPolicy->parent, tree);
652         }
653         if (!tree->user_policies) {
654             tree->user_policies = sk_X509_POLICY_NODE_new_null();
655             if (!tree->user_policies)
656                 return 1;
657         }
658         if (!sk_X509_POLICY_NODE_push(tree->user_policies, node))
659             return 0;
660     }
661     return 1;
662
663 }
664
665 static int tree_evaluate(X509_POLICY_TREE *tree)
666 {
667     int ret, i;
668     X509_POLICY_LEVEL *curr = tree->levels + 1;
669     const X509_POLICY_CACHE *cache;
670
671     for (i = 1; i < tree->nlevel; i++, curr++) {
672         cache = policy_cache_set(curr->cert);
673         if (!tree_link_nodes(curr, cache))
674             return 0;
675
676         if (!(curr->flags & X509_V_FLAG_INHIBIT_ANY)
677             && !tree_link_any(curr, cache, tree))
678             return 0;
679         tree_print("before tree_prune()", tree, curr);
680         ret = tree_prune(tree, curr);
681         if (ret != 1)
682             return ret;
683     }
684
685     return 1;
686
687 }
688
689 static void exnode_free(X509_POLICY_NODE *node)
690 {
691     if (node->data && (node->data->flags & POLICY_DATA_FLAG_EXTRA_NODE))
692         OPENSSL_free(node);
693 }
694
695 void X509_policy_tree_free(X509_POLICY_TREE *tree)
696 {
697     X509_POLICY_LEVEL *curr;
698     int i;
699
700     if (!tree)
701         return;
702
703     sk_X509_POLICY_NODE_free(tree->auth_policies);
704     sk_X509_POLICY_NODE_pop_free(tree->user_policies, exnode_free);
705
706     for (i = 0, curr = tree->levels; i < tree->nlevel; i++, curr++) {
707         if (curr->cert)
708             X509_free(curr->cert);
709         if (curr->nodes)
710             sk_X509_POLICY_NODE_pop_free(curr->nodes, policy_node_free);
711         if (curr->anyPolicy)
712             policy_node_free(curr->anyPolicy);
713     }
714
715     if (tree->extra_data)
716         sk_X509_POLICY_DATA_pop_free(tree->extra_data, policy_data_free);
717
718     OPENSSL_free(tree->levels);
719     OPENSSL_free(tree);
720
721 }
722
723 /*-
724  * Application policy checking function.
725  * Return codes:
726  *  0   Internal Error.
727  *  1   Successful.
728  * -1   One or more certificates contain invalid or inconsistent extensions
729  * -2   User constrained policy set empty and requireExplicit true.
730  */
731
732 int X509_policy_check(X509_POLICY_TREE **ptree, int *pexplicit_policy,
733                       STACK_OF(X509) *certs,
734                       STACK_OF(ASN1_OBJECT) *policy_oids, unsigned int flags)
735 {
736     int ret;
737     X509_POLICY_TREE *tree = NULL;
738     STACK_OF(X509_POLICY_NODE) *nodes, *auth_nodes = NULL;
739     *ptree = NULL;
740
741     *pexplicit_policy = 0;
742     ret = tree_init(&tree, certs, flags);
743
744     switch (ret) {
745
746         /* Tree empty requireExplicit False: OK */
747     case 2:
748         return 1;
749
750         /* Some internal error */
751     case -1:
752         return -1;
753
754         /* Some internal error */
755     case 0:
756         return 0;
757
758         /* Tree empty requireExplicit True: Error */
759
760     case 6:
761         *pexplicit_policy = 1;
762         return -2;
763
764         /* Tree OK requireExplicit True: OK and continue */
765     case 5:
766         *pexplicit_policy = 1;
767         break;
768
769         /* Tree OK: continue */
770
771     case 1:
772         if (!tree)
773             /*
774              * tree_init() returns success and a null tree
775              * if it's just looking at a trust anchor.
776              * I'm not sure that returning success here is
777              * correct, but I'm sure that reporting this
778              * as an internal error which our caller
779              * interprets as a malloc failure is wrong.
780              */
781             return 1;
782         break;
783     }
784
785     if (!tree)
786         goto error;
787     ret = tree_evaluate(tree);
788
789     tree_print("tree_evaluate()", tree, NULL);
790
791     if (ret <= 0)
792         goto error;
793
794     /* Return value 2 means tree empty */
795     if (ret == 2) {
796         X509_policy_tree_free(tree);
797         if (*pexplicit_policy)
798             return -2;
799         else
800             return 1;
801     }
802
803     /* Tree is not empty: continue */
804
805     ret = tree_calculate_authority_set(tree, &auth_nodes);
806
807     if (!ret)
808         goto error;
809
810     if (!tree_calculate_user_set(tree, policy_oids, auth_nodes))
811         goto error;
812
813     if (ret == 2)
814         sk_X509_POLICY_NODE_free(auth_nodes);
815
816     if (tree)
817         *ptree = tree;
818
819     if (*pexplicit_policy) {
820         nodes = X509_policy_tree_get0_user_policies(tree);
821         if (sk_X509_POLICY_NODE_num(nodes) <= 0)
822             return -2;
823     }
824
825     return 1;
826
827  error:
828
829     X509_policy_tree_free(tree);
830
831     return 0;
832
833 }