selinux/libsepol/cil/src/cil_symtab.c - nest-cam/4320010/selinux - Git at Google

 /*
  * 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;
 }
	/*
	* 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;
	}