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