]> git.saurik.com Git - apple/security.git/blob - OSX/sec/securityd/policytree.c
Security-58286.200.222.tar.gz
[apple/security.git] / OSX / sec / securityd / policytree.c
1 /*
2 * Copyright (c) 2009-2010,2012,2014 Apple Inc. All Rights Reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
11 * file.
12 *
13 * The Original Code and all software distributed under the License are
14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
20 *
21 * @APPLE_LICENSE_HEADER_END@
22 */
23
24 /*
25 * policytree.c - rfc5280 section 6.1.2 and later policy_tree implementation.
26 */
27
28 #include "policytree.h"
29 #include <libDER/oids.h>
30
31 #include <utilities/debugging.h>
32
33 #include <stdlib.h>
34
35 #define DUMP_POLICY_TREE 0
36
37 #if !defined(DUMP_POLICY_TREE)
38 #include <stdio.h>
39 #endif
40
41 static policy_set_t policy_set_create(const oid_t *p_oid) {
42 policy_set_t policy_set =
43 (policy_set_t)malloc(sizeof(*policy_set));
44 policy_set->oid_next = NULL;
45 policy_set->oid = *p_oid;
46 secdebug("policy-set", "%p", policy_set);
47 return policy_set;
48 }
49
50 void policy_set_add(policy_set_t *policy_set, const oid_t *p_oid) {
51 policy_set_t node = (policy_set_t)malloc(sizeof(*node));
52 node->oid_next = *policy_set;
53 node->oid = *p_oid;
54 *policy_set = node;
55 secdebug("policy-set", "%p -> %p", node, node->oid_next);
56 }
57
58 void policy_set_free(policy_set_t node) {
59 while (node) {
60 policy_set_t next = node->oid_next;
61 secdebug("policy-set", "%p -> %p", node, next);
62 free(node);
63 node = next;
64 }
65 }
66
67 bool policy_set_contains(policy_set_t node, const oid_t *oid) {
68 for (; node; node = node->oid_next) {
69 if (oid_equal(node->oid, *oid))
70 return true;
71 }
72 return false;
73 }
74
75 void policy_set_intersect(policy_set_t *policy_set, policy_set_t other_set) {
76 bool other_has_any = policy_set_contains(other_set, &oidAnyPolicy);
77 if (policy_set_contains(*policy_set, &oidAnyPolicy)) {
78 policy_set_t node = other_set;
79 if (other_has_any) {
80 /* Both sets contain anyPolicy so the intersection is anyPolicy
81 plus all oids in either set. */
82 while (node) {
83 if (!policy_set_contains(*policy_set, &node->oid)) {
84 policy_set_add(policy_set, &node->oid);
85 }
86 }
87 } else {
88 /* The result set contains anyPolicy and other_set doesn't. The
89 result set should be a copy of other_set. */
90 policy_set_free(*policy_set);
91 *policy_set = NULL;
92 while (node) {
93 policy_set_add(policy_set, &node->oid);
94 }
95 }
96 } else if (!other_has_any) {
97 /* Neither set contains any policy oid so remove any values from the
98 result set that aren't in other_set. */
99 policy_set_t *pnode = policy_set;
100 while (*pnode) {
101 policy_set_t node = *pnode;
102 if (policy_set_contains(other_set, &node->oid)) {
103 pnode = &node->oid_next;
104 } else {
105 *pnode = node->oid_next;
106 node->oid_next = NULL;
107 policy_set_free(node);
108 }
109 }
110 }
111 }
112
113 policy_tree_t policy_tree_create(const oid_t *p_oid, policy_qualifier_t p_q) {
114 policy_tree_t node = malloc(sizeof(*node));
115 memset(node, 0, sizeof(*node));
116 node->valid_policy = *p_oid;
117 node->qualifier_set = p_q;
118 node->expected_policy_set = policy_set_create(p_oid);
119 secdebug("policy-node", "%p", node);
120 return node;
121 }
122
123 /* Walk the nodes in a tree at depth and invoke callback for each one. */
124 bool policy_tree_walk_depth(policy_tree_t root, int depth,
125 bool(*callback)(policy_tree_t, void *), void *ctx) {
126 policy_tree_t *stack = (policy_tree_t *)malloc(sizeof(policy_tree_t) * (depth + 1));
127 if (!stack) {
128 return false;
129 }
130 int stack_ix = 0;
131 stack[stack_ix] = root;
132 policy_tree_t node;
133 bool match = false;
134 bool child_visited = false;
135 while (stack_ix >= 0) {
136 /* stack[stack_ix - 1] is the parent of the current node. */
137 node = stack[stack_ix];
138 policy_tree_t child = node->children;
139 if (!child_visited && stack_ix < depth && child ) {
140 /* If we have a child and we haven't reached the
141 required depth yet, we go depth first and proccess it. */
142 stack[++stack_ix] = child;
143 } else {
144 /* Get the sibling now in case we delete the node in the callback */
145 policy_tree_t sibling = node->siblings;
146 if (stack_ix == depth) {
147 /* Proccess node. */
148 match |= callback(node, ctx);
149 }
150
151 /* Move on to sibling of node. */
152 if (sibling) {
153 /* Replace current node with it's sibling. */
154 stack[stack_ix] = sibling;
155 child_visited = false;
156 } else {
157 /* No more siblings left, so pop the stack and backtrack. */
158 stack_ix--;
159 /* We've handled the top of the stack's child already so
160 just look at it's siblings. */
161 child_visited = true;
162 }
163 }
164 }
165 free(stack);
166 return match;
167 }
168
169 static void policy_tree_free_node(policy_tree_t node) {
170 secdebug("policy-node", "%p children: %p siblngs: %p", node,
171 node->children, node->siblings);
172 if (node->expected_policy_set) {
173 policy_set_free(node->expected_policy_set);
174 node->expected_policy_set = NULL;
175 }
176 free(node);
177 }
178
179 void policy_tree_remove_node(policy_tree_t *node) {
180 /* Free node's children */
181 policy_tree_t *child = &(*node)->children;
182 if (*child)
183 policy_tree_prune(child);
184
185 /* Remove node from parent */
186 policy_tree_t parent = (*node)->parent;
187 parent->children = (*node)->siblings;
188
189 /* Free node */
190 policy_tree_free_node(*node);
191 *node = NULL;
192 }
193
194 /* Prune nodes from node down. */
195 void policy_tree_prune(policy_tree_t *node) {
196 /* Free all our children and siblings. */
197 policy_tree_t *child = &(*node)->children;
198 if (*child)
199 policy_tree_prune(child);
200 policy_tree_t *sibling = &(*node)->siblings;
201 if (*sibling)
202 policy_tree_prune(sibling);
203 policy_tree_free_node(*node);
204 *node = NULL;
205 }
206
207 /* Prune childless nodes at depth. */
208 void policy_tree_prune_childless(policy_tree_t *root, int depth) {
209 policy_tree_t *stack[depth + 1];
210 int stack_ix = 0;
211 stack[stack_ix] = root;
212 bool child_visited = false;
213 while (stack_ix >= 0) {
214 policy_tree_t *node;
215 node = stack[stack_ix];
216 policy_tree_t *child = &(*node)->children;
217 if (!child_visited && stack_ix < depth && *child) {
218 /* If we have a child and we haven't reached the
219 required depth yet, we go depth first and proccess it. */
220 stack[++stack_ix] = child;
221 } else if (!*child) {
222 /* Childless node found, nuke it. */
223 #if !defined(DUMP_POLICY_TREE)
224 printf("# prune /<%.08lx<\\ |%.08lx| >%.08lx> :%s: depth %d\n",
225 (intptr_t)node, (intptr_t)*node, (intptr_t)(*node)->siblings,
226 (child_visited ? "v" : " "), stack_ix);
227 #endif
228
229 policy_tree_t next = (*node)->siblings;
230 (*node)->siblings = NULL;
231 policy_tree_free_node(*node);
232 *node = next;
233 if (next) {
234 /* stack[stack_ix] (node) already points to next now. */
235 child_visited = false;
236 } else {
237 /* No more siblings left, so pop the stack and backtrack. */
238 stack_ix--;
239 child_visited = true;
240 }
241 } else {
242 policy_tree_t *sibling = &(*node)->siblings;
243 if (*sibling) {
244 /* Replace current node with it's sibling. */
245 stack[stack_ix] = sibling;
246 child_visited = false;
247 } else {
248 /* No more siblings left, so pop the stack and backtrack. */
249 stack_ix--;
250 child_visited = true;
251 }
252 }
253 }
254 }
255
256 /* Add a new child to the tree. */
257 static void policy_tree_add_child_explicit(policy_tree_t parent,
258 const oid_t *p_oid, policy_qualifier_t p_q, policy_set_t p_expected) {
259 policy_tree_t child = malloc(sizeof(*child));
260 memset(child, 0, sizeof(*child));
261 child->valid_policy = *p_oid;
262 child->qualifier_set = p_q;
263 child->expected_policy_set = p_expected;
264 child->parent = parent;
265
266 #if 0
267 printf("# /%.08lx\\ |%.08lx| \\%.08lx/ >%.08lx> \\>%.08lx>/\n",
268 (intptr_t)parent, (intptr_t)child, (intptr_t)parent->children,
269 (intptr_t)parent->siblings,
270 (intptr_t)(parent->children ? parent->children->siblings : NULL));
271 #endif
272
273 /* Previous child becomes new child's first sibling. */
274 child->siblings = parent->children;
275 /* New child becomes parent's first child. */
276 parent->children = child;
277
278 secdebug("policy-node", "%p siblngs: %p", child, child->siblings);
279 }
280
281 /* Add a new child to the tree parent setting valid_policy to p_oid,
282 qualifier_set to p_q and expected_policy_set to a set containing
283 just p_oid. */
284 void policy_tree_add_child(policy_tree_t parent,
285 const oid_t *p_oid, policy_qualifier_t p_q) {
286 policy_set_t policy_set = policy_set_create(p_oid);
287 policy_tree_add_child_explicit(parent, p_oid, p_q, policy_set);
288 }
289
290 /* Add a new sibling to the tree setting valid_policy to p_oid,
291 qualifier set to p_q and expected_policy_set to p_expected */
292 void policy_tree_add_sibling(policy_tree_t sibling, const oid_t *p_oid,
293 policy_qualifier_t p_q, policy_set_t p_expected) {
294 policy_tree_add_child_explicit(sibling->parent, p_oid, p_q, p_expected);
295 }
296
297 void policy_tree_set_expected_policy(policy_tree_t node,
298 policy_set_t p_expected) {
299 if (node->expected_policy_set)
300 policy_set_free(node->expected_policy_set);
301 node->expected_policy_set = p_expected;
302 }
303
304 #if !defined(DUMP_POLICY_TREE)
305 /* Dump a policy tree. */
306 static void policy_tree_dump4(policy_tree_t node, policy_tree_t parent,
307 policy_tree_t prev_sibling, int depth) {
308 policy_tree_t child = node->children;
309 policy_tree_t sibling = node->siblings;
310 static const char *spaces = " ";
311 printf("# %.*s/%.08lx\\ |%.08lx| <%.08lx< >%.08lx> depth %d\n",
312 depth * 11, spaces,
313 (intptr_t)parent, (intptr_t)node, (intptr_t)prev_sibling,
314 (intptr_t)sibling, depth);
315 if (child)
316 policy_tree_dump4(child, node, NULL, depth + 1);
317 if (sibling)
318 policy_tree_dump4(sibling, parent, node, depth);
319 }
320 #endif /* !defined(DUMP_POLICY_TREE) */
321
322 void policy_tree_dump(policy_tree_t node) {
323 #if !defined(DUMP_POLICY_TREE)
324 policy_tree_dump4(node, NULL, NULL, 0);
325 #endif /* !defined(DUMP_POLICY_TREE) */
326 }