trust/trustd/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 }