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 
cil_symtab_error(const char * msg,...)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 
cil_symtab_init(symtab_t * symtab,unsigned int size)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 
cil_symtab_datum_init(struct cil_symtab_datum * datum)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 
cil_symtab_datum_destroy(struct cil_symtab_datum * datum)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 
cil_symtab_datum_remove_node(struct cil_symtab_datum * datum,struct cil_tree_node * node)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 */
cil_symtab_insert(symtab_t * symtab,hashtab_key_t key,struct cil_symtab_datum * datum,struct cil_tree_node * node)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 
cil_symtab_remove_datum(struct cil_symtab_datum * datum)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 
cil_symtab_get_datum(symtab_t * symtab,char * key,struct cil_symtab_datum ** datum)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 
cil_symtab_map(symtab_t * symtab,int (* apply)(hashtab_key_t k,hashtab_datum_t d,void * args),void * args)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 
__cil_symtab_destroy_helper(hashtab_key_t k,hashtab_datum_t d,void * args)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 
cil_symtab_destroy(symtab_t * symtab)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 
cil_complex_symtab_hash(struct cil_complex_symtab_key * ckey,int mask,intptr_t * hash)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 
cil_complex_symtab_init(struct cil_complex_symtab * symtab,unsigned int size)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 
cil_complex_symtab_insert(struct cil_complex_symtab * symtab,struct cil_complex_symtab_key * ckey,struct cil_complex_symtab_datum * datum)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 
cil_complex_symtab_search(struct cil_complex_symtab * symtab,struct cil_complex_symtab_key * ckey,struct cil_complex_symtab_datum ** out)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 
cil_complex_symtab_destroy(struct cil_complex_symtab * symtab)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