1 /* 2 * Copyright 2011 Tresys Technology, LLC. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are met: 6 * 7 * 1. Redistributions of source code must retain the above copyright notice, 8 * this list of conditions and the following disclaimer. 9 * 10 * 2. Redistributions in binary form must reproduce the above copyright notice, 11 * this list of conditions and the following disclaimer in the documentation 12 * and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY TRESYS TECHNOLOGY, LLC ``AS IS'' AND ANY EXPRESS 15 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 16 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO 17 * EVENT SHALL TRESYS TECHNOLOGY, LLC OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 18 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 19 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 21 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE 22 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 23 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 * 25 * The views and conclusions contained in the software and documentation are those 26 * of the authors and should not be interpreted as representing official policies, 27 * either expressed or implied, of Tresys Technology, LLC. 28 */ 29 30 #include <stdlib.h> 31 #include <string.h> 32 #include <stdarg.h> 33 34 #include <sepol/errcodes.h> 35 #include <sepol/policydb/hashtab.h> 36 #include <sepol/policydb/symtab.h> 37 38 #include "cil_internal.h" 39 #include "cil_tree.h" 40 #include "cil_symtab.h" 41 #include "cil_mem.h" 42 #include "cil_strpool.h" 43 #include "cil_log.h" 44 45 __attribute__((noreturn)) __attribute__((format (printf, 1, 2))) void cil_symtab_error(const char* msg, ...) 46 { 47 va_list ap; 48 va_start(ap, msg); 49 cil_vlog(CIL_ERR, msg, ap); 50 va_end(ap); 51 exit(1); 52 } 53 54 void cil_symtab_init(symtab_t *symtab, unsigned int size) 55 { 56 int rc = symtab_init(symtab, size); 57 if (rc != SEPOL_OK) { 58 cil_symtab_error("Failed to create symtab\n"); 59 } 60 } 61 62 void cil_symtab_datum_init(struct cil_symtab_datum *datum) 63 { 64 datum->name = NULL; 65 datum->fqn = NULL; 66 datum->symtab = NULL; 67 cil_list_init(&datum->nodes, CIL_LIST_ITEM); 68 } 69 70 void cil_symtab_datum_destroy(struct cil_symtab_datum *datum) 71 { 72 cil_list_destroy(&datum->nodes, 0); 73 cil_symtab_remove_datum(datum); 74 } 75 76 void cil_symtab_datum_remove_node(struct cil_symtab_datum *datum, struct cil_tree_node *node) 77 { 78 if (datum && datum->nodes != NULL) { 79 cil_list_remove(datum->nodes, CIL_NODE, node, 0); 80 if (datum->nodes->head == NULL) { 81 cil_symtab_datum_destroy(datum); 82 } 83 } 84 } 85 86 /* This both initializes the datum and inserts it into the symtab. 87 Note that cil_symtab_datum_destroy() is the analog to the initializer portion */ 88 int cil_symtab_insert(symtab_t *symtab, hashtab_key_t key, struct cil_symtab_datum *datum, struct cil_tree_node *node) 89 { 90 int rc = hashtab_insert(symtab->table, key, (hashtab_datum_t)datum); 91 if (rc == SEPOL_OK) { 92 datum->name = key; 93 datum->fqn = key; 94 datum->symtab = symtab; 95 cil_list_append(datum->nodes, CIL_NODE, node); 96 } else if (rc == SEPOL_EEXIST) { 97 cil_list_append(datum->nodes, CIL_NODE, node); 98 } else { 99 cil_symtab_error("Failed to insert datum into hashtab\n"); 100 } 101 102 return rc; 103 } 104 105 void cil_symtab_remove_datum(struct cil_symtab_datum *datum) 106 { 107 symtab_t *symtab = datum->symtab; 108 109 if (symtab == NULL) { 110 return; 111 } 112 113 hashtab_remove(symtab->table, datum->name, NULL, NULL); 114 datum->symtab = NULL; 115 } 116 117 int cil_symtab_get_datum(symtab_t *symtab, char *key, struct cil_symtab_datum **datum) 118 { 119 *datum = (struct cil_symtab_datum*)hashtab_search(symtab->table, (hashtab_key_t)key); 120 if (*datum == NULL) { 121 return SEPOL_ENOENT; 122 } 123 124 return SEPOL_OK; 125 } 126 127 int cil_symtab_map(symtab_t *symtab, 128 int (*apply) (hashtab_key_t k, hashtab_datum_t d, void *args), 129 void *args) 130 { 131 return hashtab_map(symtab->table, apply, args); 132 } 133 134 static int __cil_symtab_destroy_helper(__attribute__((unused)) hashtab_key_t k, hashtab_datum_t d, __attribute__((unused)) void *args) 135 { 136 struct cil_symtab_datum *datum = d; 137 datum->symtab = NULL; 138 return SEPOL_OK; 139 } 140 141 void cil_symtab_destroy(symtab_t *symtab) 142 { 143 if (symtab->table != NULL){ 144 cil_symtab_map(symtab, __cil_symtab_destroy_helper, NULL); 145 hashtab_destroy(symtab->table); 146 symtab->table = NULL; 147 } 148 } 149 150 void cil_complex_symtab_hash(struct cil_complex_symtab_key *ckey, int mask, intptr_t *hash) 151 { 152 intptr_t sum = ckey->key1 + ckey->key2 + ckey->key3 + ckey->key4; 153 *hash = (intptr_t)((sum >> 2) & mask); 154 } 155 156 void cil_complex_symtab_init(struct cil_complex_symtab *symtab, unsigned int size) 157 { 158 symtab->htable = cil_calloc(size, sizeof(struct cil_complex_symtab *)); 159 160 symtab->nelems = 0; 161 symtab->nslots = size; 162 symtab->mask = size - 1; 163 } 164 165 int cil_complex_symtab_insert(struct cil_complex_symtab *symtab, 166 struct cil_complex_symtab_key *ckey, 167 struct cil_complex_symtab_datum *datum) 168 { 169 intptr_t hash; 170 struct cil_complex_symtab_node *node = NULL; 171 struct cil_complex_symtab_node *prev = NULL; 172 struct cil_complex_symtab_node *curr = NULL; 173 174 node = cil_malloc(sizeof(*node)); 175 memset(node, 0, sizeof(*node)); 176 177 node->ckey = ckey; 178 node->datum = datum; 179 180 cil_complex_symtab_hash(ckey, symtab->mask, &hash); 181 182 for (prev = NULL, curr = symtab->htable[hash]; curr != NULL; 183 prev = curr, curr = curr->next) { 184 if (ckey->key1 == curr->ckey->key1 && 185 ckey->key2 == curr->ckey->key2 && 186 ckey->key3 == curr->ckey->key3 && 187 ckey->key4 == curr->ckey->key4) { 188 return SEPOL_EEXIST; 189 } 190 191 if (ckey->key1 == curr->ckey->key1 && 192 ckey->key2 < curr->ckey->key2) { 193 break; 194 } 195 196 if (ckey->key1 == curr->ckey->key1 && 197 ckey->key2 == curr->ckey->key2 && 198 ckey->key3 < curr->ckey->key3) { 199 break; 200 } 201 202 if (ckey->key1 == curr->ckey->key1 && 203 ckey->key2 == curr->ckey->key2 && 204 ckey->key3 == curr->ckey->key3 && 205 ckey->key4 < curr->ckey->key4) { 206 break; 207 } 208 } 209 210 if (prev != NULL) { 211 node->next = prev->next; 212 prev->next = node; 213 } else { 214 node->next = symtab->htable[hash]; 215 symtab->htable[hash] = node; 216 } 217 218 symtab->nelems++; 219 220 return SEPOL_OK; 221 } 222 223 void cil_complex_symtab_search(struct cil_complex_symtab *symtab, 224 struct cil_complex_symtab_key *ckey, 225 struct cil_complex_symtab_datum **out) 226 { 227 intptr_t hash; 228 struct cil_complex_symtab_node *curr = NULL; 229 230 cil_complex_symtab_hash(ckey, symtab->mask, &hash); 231 for (curr = symtab->htable[hash]; curr != NULL; curr = curr->next) { 232 if (ckey->key1 == curr->ckey->key1 && 233 ckey->key2 == curr->ckey->key2 && 234 ckey->key3 == curr->ckey->key3 && 235 ckey->key4 == curr->ckey->key4) { 236 *out = curr->datum; 237 return; 238 } 239 240 if (ckey->key1 == curr->ckey->key1 && 241 ckey->key2 < curr->ckey->key2) { 242 break; 243 } 244 245 if (ckey->key1 == curr->ckey->key1 && 246 ckey->key2 == curr->ckey->key2 && 247 ckey->key3 < curr->ckey->key3) { 248 break; 249 } 250 251 if (ckey->key1 == curr->ckey->key1 && 252 ckey->key2 == curr->ckey->key2 && 253 ckey->key3 == curr->ckey->key3 && 254 ckey->key4 < curr->ckey->key4) { 255 break; 256 } 257 } 258 259 *out = NULL; 260 } 261 262 void cil_complex_symtab_destroy(struct cil_complex_symtab *symtab) 263 { 264 struct cil_complex_symtab_node *curr = NULL; 265 struct cil_complex_symtab_node *temp = NULL; 266 unsigned int i; 267 268 if (symtab == NULL) { 269 return; 270 } 271 272 for (i = 0; i < symtab->nslots; i++) { 273 curr = symtab->htable[i]; 274 while (curr != NULL) { 275 temp = curr; 276 curr = curr->next; 277 free(temp); 278 } 279 symtab->htable[i] = NULL; 280 } 281 free(symtab->htable); 282 symtab->htable = NULL; 283 symtab->nelems = 0; 284 symtab->nslots = 0; 285 symtab->mask = 0; 286 } 287
