/* * Copyright 2011 Tresys Technology, LLC. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * 1. Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright notice, * this list of conditions and the following disclaimer in the documentation * and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY TRESYS TECHNOLOGY, LLC ``AS IS'' AND ANY EXPRESS * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO * EVENT SHALL TRESYS TECHNOLOGY, LLC OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * The views and conclusions contained in the software and documentation are those * of the authors and should not be interpreted as representing official policies, * either expressed or implied, of Tresys Technology, LLC. */ #include <stdlib.h> #include <string.h> #include <stdarg.h> #include <sepol/errcodes.h> #include <sepol/policydb/hashtab.h> #include <sepol/policydb/symtab.h> #include "cil_internal.h" #include "cil_tree.h" #include "cil_symtab.h" #include "cil_mem.h" #include "cil_strpool.h" #include "cil_log.h" __attribute__((noreturn)) __attribute__((format (printf, 1, 2))) void cil_symtab_error(const char* msg, ...) { va_list ap; va_start(ap, msg); cil_vlog(CIL_ERR, msg, ap); va_end(ap); exit(1); } void cil_symtab_init(symtab_t *symtab, unsigned int size) { int rc = symtab_init(symtab, size); if (rc != SEPOL_OK) { cil_symtab_error("Failed to create symtab\n"); } } void cil_symtab_datum_init(struct cil_symtab_datum *datum) { datum->name = NULL; datum->fqn = NULL; datum->symtab = NULL; cil_list_init(&datum->nodes, CIL_LIST_ITEM); } void cil_symtab_datum_destroy(struct cil_symtab_datum *datum) { cil_list_destroy(&datum->nodes, 0); cil_symtab_remove_datum(datum); } void cil_symtab_datum_remove_node(struct cil_symtab_datum *datum, struct cil_tree_node *node) { if (datum && datum->nodes != NULL) { cil_list_remove(datum->nodes, CIL_NODE, node, 0); if (datum->nodes->head == NULL) { cil_symtab_datum_destroy(datum); } } } /* This both initializes the datum and inserts it into the symtab. Note that cil_symtab_datum_destroy() is the analog to the initializer portion */ int cil_symtab_insert(symtab_t *symtab, hashtab_key_t key, struct cil_symtab_datum *datum, struct cil_tree_node *node) { int rc = hashtab_insert(symtab->table, key, (hashtab_datum_t)datum); if (rc == SEPOL_OK) { datum->name = key; datum->fqn = key; datum->symtab = symtab; cil_list_append(datum->nodes, CIL_NODE, node); } else if (rc == SEPOL_EEXIST) { cil_list_append(datum->nodes, CIL_NODE, node); } else { cil_symtab_error("Failed to insert datum into hashtab\n"); } return rc; } void cil_symtab_remove_datum(struct cil_symtab_datum *datum) { symtab_t *symtab = datum->symtab; if (symtab == NULL) { return; } hashtab_remove(symtab->table, datum->name, NULL, NULL); datum->symtab = NULL; } int cil_symtab_get_datum(symtab_t *symtab, char *key, struct cil_symtab_datum **datum) { *datum = (struct cil_symtab_datum*)hashtab_search(symtab->table, (hashtab_key_t)key); if (*datum == NULL) { return SEPOL_ENOENT; } return SEPOL_OK; } int cil_symtab_map(symtab_t *symtab, int (*apply) (hashtab_key_t k, hashtab_datum_t d, void *args), void *args) { return hashtab_map(symtab->table, apply, args); } static int __cil_symtab_destroy_helper(__attribute__((unused)) hashtab_key_t k, hashtab_datum_t d, __attribute__((unused)) void *args) { struct cil_symtab_datum *datum = d; datum->symtab = NULL; return SEPOL_OK; } void cil_symtab_destroy(symtab_t *symtab) { if (symtab->table != NULL){ cil_symtab_map(symtab, __cil_symtab_destroy_helper, NULL); hashtab_destroy(symtab->table); symtab->table = NULL; } } void cil_complex_symtab_hash(struct cil_complex_symtab_key *ckey, int mask, intptr_t *hash) { intptr_t sum = ckey->key1 + ckey->key2 + ckey->key3 + ckey->key4; *hash = (intptr_t)((sum >> 2) & mask); } void cil_complex_symtab_init(struct cil_complex_symtab *symtab, unsigned int size) { symtab->htable = cil_calloc(size, sizeof(struct cil_complex_symtab *)); symtab->nelems = 0; symtab->nslots = size; symtab->mask = size - 1; } int cil_complex_symtab_insert(struct cil_complex_symtab *symtab, struct cil_complex_symtab_key *ckey, struct cil_complex_symtab_datum *datum) { intptr_t hash; struct cil_complex_symtab_node *node = NULL; struct cil_complex_symtab_node *prev = NULL; struct cil_complex_symtab_node *curr = NULL; node = cil_malloc(sizeof(*node)); memset(node, 0, sizeof(*node)); node->ckey = ckey; node->datum = datum; cil_complex_symtab_hash(ckey, symtab->mask, &hash); for (prev = NULL, curr = symtab->htable[hash]; curr != NULL; prev = curr, curr = curr->next) { if (ckey->key1 == curr->ckey->key1 && ckey->key2 == curr->ckey->key2 && ckey->key3 == curr->ckey->key3 && ckey->key4 == curr->ckey->key4) { return SEPOL_EEXIST; } if (ckey->key1 == curr->ckey->key1 && ckey->key2 < curr->ckey->key2) { break; } if (ckey->key1 == curr->ckey->key1 && ckey->key2 == curr->ckey->key2 && ckey->key3 < curr->ckey->key3) { break; } if (ckey->key1 == curr->ckey->key1 && ckey->key2 == curr->ckey->key2 && ckey->key3 == curr->ckey->key3 && ckey->key4 < curr->ckey->key4) { break; } } if (prev != NULL) { node->next = prev->next; prev->next = node; } else { node->next = symtab->htable[hash]; symtab->htable[hash] = node; } symtab->nelems++; return SEPOL_OK; } void cil_complex_symtab_search(struct cil_complex_symtab *symtab, struct cil_complex_symtab_key *ckey, struct cil_complex_symtab_datum **out) { intptr_t hash; struct cil_complex_symtab_node *curr = NULL; cil_complex_symtab_hash(ckey, symtab->mask, &hash); for (curr = symtab->htable[hash]; curr != NULL; curr = curr->next) { if (ckey->key1 == curr->ckey->key1 && ckey->key2 == curr->ckey->key2 && ckey->key3 == curr->ckey->key3 && ckey->key4 == curr->ckey->key4) { *out = curr->datum; return; } if (ckey->key1 == curr->ckey->key1 && ckey->key2 < curr->ckey->key2) { break; } if (ckey->key1 == curr->ckey->key1 && ckey->key2 == curr->ckey->key2 && ckey->key3 < curr->ckey->key3) { break; } if (ckey->key1 == curr->ckey->key1 && ckey->key2 == curr->ckey->key2 && ckey->key3 == curr->ckey->key3 && ckey->key4 < curr->ckey->key4) { break; } } *out = NULL; } void cil_complex_symtab_destroy(struct cil_complex_symtab *symtab) { struct cil_complex_symtab_node *curr = NULL; struct cil_complex_symtab_node *temp = NULL; unsigned int i; if (symtab == NULL) { return; } for (i = 0; i < symtab->nslots; i++) { curr = symtab->htable[i]; while (curr != NULL) { temp = curr; curr = curr->next; free(temp); } symtab->htable[i] = NULL; } free(symtab->htable); symtab->htable = NULL; symtab->nelems = 0; symtab->nslots = 0; symtab->mask = 0; }