X-Git-Url: https://git.saurik.com/apple/security.git/blobdiff_plain/80e2389990082500d76eb566d4946be3e786c3ef..d8f41ccd20de16f8ebe2ccc84d47bf1cb2b26bbb:/Security/sec/securityd/policytree.c diff --git a/Security/sec/securityd/policytree.c b/Security/sec/securityd/policytree.c new file mode 100644 index 00000000..b6086a38 --- /dev/null +++ b/Security/sec/securityd/policytree.c @@ -0,0 +1,298 @@ +/* + * Copyright (c) 2009-2010,2012,2014 Apple Inc. All Rights Reserved. + * + * @APPLE_LICENSE_HEADER_START@ + * + * This file contains Original Code and/or Modifications of Original Code + * as defined in and that are subject to the Apple Public Source License + * Version 2.0 (the 'License'). You may not use this file except in + * compliance with the License. Please obtain a copy of the License at + * http://www.opensource.apple.com/apsl/ and read it before using this + * file. + * + * The Original Code and all software distributed under the License are + * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER + * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, + * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. + * Please see the License for the specific language governing rights and + * limitations under the License. + * + * @APPLE_LICENSE_HEADER_END@ + */ + +/* + * policytree.c - rfc5280 section 6.1.2 and later policy_tree implementation. + */ + +#include "policytree.h" +#include + +#include + +#include + +#define DUMP_POLICY_TREE 0 + +#if !defined(DUMP_POLICY_TREE) +#include +#endif + +static policy_set_t policy_set_create(const oid_t *p_oid) { + policy_set_t policy_set = + (policy_set_t)malloc(sizeof(*policy_set)); + policy_set->oid_next = NULL; + policy_set->oid = *p_oid; + secdebug("policy-set", "%p", policy_set); + return policy_set; +} + +void policy_set_add(policy_set_t *policy_set, const oid_t *p_oid) { + policy_set_t node = (policy_set_t)malloc(sizeof(*node)); + node->oid_next = *policy_set; + node->oid = *p_oid; + *policy_set = node; + secdebug("policy-set", "%p -> %p", node, node->oid_next); +} + +void policy_set_free(policy_set_t node) { + while (node) { + policy_set_t next = node->oid_next; + secdebug("policy-set", "%p -> %p", node, next); + free(node); + node = next; + } +} + +bool policy_set_contains(policy_set_t node, const oid_t *oid) { + for (; node; node = node->oid_next) { + if (oid_equal(node->oid, *oid)) + return true; + } + return false; +} + +void policy_set_intersect(policy_set_t *policy_set, policy_set_t other_set) { + bool other_has_any = policy_set_contains(other_set, &oidAnyPolicy); + if (policy_set_contains(*policy_set, &oidAnyPolicy)) { + policy_set_t node = other_set; + if (other_has_any) { + /* Both sets contain anyPolicy so the intersection is anyPolicy + plus all oids in either set. */ + while (node) { + if (!policy_set_contains(*policy_set, &node->oid)) { + policy_set_add(policy_set, &node->oid); + } + } + } else { + /* The result set contains anyPolicy and other_set doesn't. The + result set should be a copy of other_set. */ + policy_set_free(*policy_set); + *policy_set = NULL; + while (node) { + policy_set_add(policy_set, &node->oid); + } + } + } else if (!other_has_any) { + /* Neither set contains any policy oid so remove any values from the + result set that aren't in other_set. */ + policy_set_t *pnode = policy_set; + while (*pnode) { + policy_set_t node = *pnode; + if (policy_set_contains(other_set, &node->oid)) { + pnode = &node->oid_next; + } else { + *pnode = node->oid_next; + node->oid_next = NULL; + policy_set_free(node); + } + } + } +} + +policy_tree_t policy_tree_create(const oid_t *p_oid, policy_qualifier_t p_q) { + policy_tree_t node = malloc(sizeof(*node)); + node->valid_policy = *p_oid; + node->qualifier_set = p_q; + node->expected_policy_set = policy_set_create(p_oid); + node->children = NULL; + node->siblings = NULL; + secdebug("policy-node", "%p", node); + return node; +} + +/* Walk the nodes in a tree at depth and invoke callback for each one. */ +bool policy_tree_walk_depth(policy_tree_t root, int depth, + bool(*callback)(policy_tree_t, void *), void *ctx) { + policy_tree_t stack[depth + 1]; + int stack_ix = 0; + stack[stack_ix] = root; + policy_tree_t node; + bool match = false; + bool child_visited = false; + while (stack_ix >= 0) { + /* stack[stack_ix - 1] is the parent of the current node. */ + node = stack[stack_ix]; + policy_tree_t child = node->children; + if (!child_visited && stack_ix < depth && child ) { + /* If we have a child and we haven't reached the + required depth yet, we go depth first and proccess it. */ + stack[++stack_ix] = child; + } else { + if (stack_ix == depth) { + /* Proccess node. */ + match |= callback(node, ctx); + } + /* Move on to sibling of node. */ + policy_tree_t sibling = node->siblings; + if (sibling) { + /* Replace current node with it's sibling. */ + stack[stack_ix] = sibling; + child_visited = false; + } else { + /* No more siblings left, so pop the stack and backtrack. */ + stack_ix--; + /* We've handled the top of the stack's child already so + just look at it's siblings. */ + child_visited = true; + } + } + } + return match; +} + +static void policy_tree_free_node(policy_tree_t node) { + secdebug("policy-node", "%p children: %p siblngs: %p", node, + node->children, node->siblings); + if (node->expected_policy_set) { + policy_set_free(node->expected_policy_set); + node->expected_policy_set = NULL; + } + free(node); +} + +/* Prune nodes from node down. */ +void policy_tree_prune(policy_tree_t *node) { + /* Free all our children and siblings. */ + policy_tree_t *child = &(*node)->children; + if (*child) + policy_tree_prune(child); + policy_tree_t *sibling = &(*node)->siblings; + if (*sibling) + policy_tree_prune(sibling); + policy_tree_free_node(*node); + *node = NULL; +} + +/* Prune childless nodes at depth. */ +void policy_tree_prune_childless(policy_tree_t *root, int depth) { + policy_tree_t *stack[depth + 1]; + int stack_ix = 0; + stack[stack_ix] = root; + bool child_visited = false; + while (stack_ix >= 0) { + policy_tree_t *node; + node = stack[stack_ix]; + policy_tree_t *child = &(*node)->children; + if (!child_visited && stack_ix < depth && *child) { + /* If we have a child and we haven't reached the + required depth yet, we go depth first and proccess it. */ + stack[++stack_ix] = child; + } else if (!*child) { + /* Childless node found, nuke it. */ +#if !defined(DUMP_POLICY_TREE) + printf("# prune /<%.08lx<\\ |%.08lx| >%.08lx> :%s: depth %d\n", + (intptr_t)node, (intptr_t)*node, (intptr_t)(*node)->siblings, + (child_visited ? "v" : " "), stack_ix); +#endif + + policy_tree_t next = (*node)->siblings; + (*node)->siblings = NULL; + policy_tree_free_node(*node); + *node = next; + if (next) { + /* stack[stack_ix] (node) already points to next now. */ + child_visited = false; + } else { + /* No more siblings left, so pop the stack and backtrack. */ + stack_ix--; + child_visited = true; + } + } else { + policy_tree_t *sibling = &(*node)->siblings; + if (*sibling) { + /* Replace current node with it's sibling. */ + stack[stack_ix] = sibling; + child_visited = false; + } else { + /* No more siblings left, so pop the stack and backtrack. */ + stack_ix--; + child_visited = true; + } + } + } +} + +/* Add a new child to the tree. */ +static void policy_tree_add_child_explicit(policy_tree_t parent, + const oid_t *p_oid, policy_qualifier_t p_q, policy_set_t p_expected) { + policy_tree_t child = malloc(sizeof(*child)); + child->valid_policy = *p_oid; + child->qualifier_set = p_q; + child->expected_policy_set = p_expected; + child->children = NULL; + +#if 0 + printf("# /%.08lx\\ |%.08lx| \\%.08lx/ >%.08lx> \\>%.08lx>/\n", + (intptr_t)parent, (intptr_t)child, (intptr_t)parent->children, + (intptr_t)parent->siblings, + (intptr_t)(parent->children ? parent->children->siblings : NULL)); +#endif + + /* Previous child becomes new child's first sibling. */ + child->siblings = parent->children; + /* New child becomes parent's first child. */ + parent->children = child; + + secdebug("policy-node", "%p siblngs: %p", child, child->siblings); +} + +/* Add a new child to the tree parent setting valid_policy to p_oid, + qualifier_set to p_q and expected_policy_set to a set containing + just p_oid. */ +void policy_tree_add_child(policy_tree_t parent, + const oid_t *p_oid, policy_qualifier_t p_q) { + policy_set_t policy_set = policy_set_create(p_oid); + policy_tree_add_child_explicit(parent, p_oid, p_q, policy_set); +} + +void policy_tree_set_expected_policy(policy_tree_t node, + policy_set_t p_expected) { + if (node->expected_policy_set) + policy_set_free(node->expected_policy_set); + node->expected_policy_set = p_expected; +} + +#if !defined(DUMP_POLICY_TREE) +/* Dump a policy tree. */ +static void policy_tree_dump4(policy_tree_t node, policy_tree_t parent, + policy_tree_t prev_sibling, int depth) { + policy_tree_t child = node->children; + policy_tree_t sibling = node->siblings; + static const char *spaces = " "; + printf("# %.*s/%.08lx\\ |%.08lx| <%.08lx< >%.08lx> depth %d\n", + depth * 11, spaces, + (intptr_t)parent, (intptr_t)node, (intptr_t)prev_sibling, + (intptr_t)sibling, depth); + if (child) + policy_tree_dump4(child, node, NULL, depth + 1); + if (sibling) + policy_tree_dump4(sibling, parent, node, depth); +} +#endif /* !defined(DUMP_POLICY_TREE) */ + +void policy_tree_dump(policy_tree_t node) { +#if !defined(DUMP_POLICY_TREE) + policy_tree_dump4(node, NULL, NULL, 0); +#endif /* !defined(DUMP_POLICY_TREE) */ +}