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 54void 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 62void 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 70void 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 76void 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 */ 88int 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 105void 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 117int 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 127int 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 134static 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 141void 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 150void 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 156void 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 165int 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 223void 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 262void 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