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 free(node);
189 return SEPOL_EEXIST;
190 }
191
192 if (ckey->key1 == curr->ckey->key1 &&
193 ckey->key2 < curr->ckey->key2) {
194 break;
195 }
196
197 if (ckey->key1 == curr->ckey->key1 &&
198 ckey->key2 == curr->ckey->key2 &&
199 ckey->key3 < curr->ckey->key3) {
200 break;
201 }
202
203 if (ckey->key1 == curr->ckey->key1 &&
204 ckey->key2 == curr->ckey->key2 &&
205 ckey->key3 == curr->ckey->key3 &&
206 ckey->key4 < curr->ckey->key4) {
207 break;
208 }
209 }
210
211 if (prev != NULL) {
212 node->next = prev->next;
213 prev->next = node;
214 } else {
215 node->next = symtab->htable[hash];
216 symtab->htable[hash] = node;
217 }
218
219 symtab->nelems++;
220
221 return SEPOL_OK;
222 }
223
cil_complex_symtab_search(struct cil_complex_symtab * symtab,struct cil_complex_symtab_key * ckey,struct cil_complex_symtab_datum ** out)224 void cil_complex_symtab_search(struct cil_complex_symtab *symtab,
225 struct cil_complex_symtab_key *ckey,
226 struct cil_complex_symtab_datum **out)
227 {
228 intptr_t hash;
229 struct cil_complex_symtab_node *curr = NULL;
230
231 cil_complex_symtab_hash(ckey, symtab->mask, &hash);
232 for (curr = symtab->htable[hash]; curr != NULL; curr = curr->next) {
233 if (ckey->key1 == curr->ckey->key1 &&
234 ckey->key2 == curr->ckey->key2 &&
235 ckey->key3 == curr->ckey->key3 &&
236 ckey->key4 == curr->ckey->key4) {
237 *out = curr->datum;
238 return;
239 }
240
241 if (ckey->key1 == curr->ckey->key1 &&
242 ckey->key2 < curr->ckey->key2) {
243 break;
244 }
245
246 if (ckey->key1 == curr->ckey->key1 &&
247 ckey->key2 == curr->ckey->key2 &&
248 ckey->key3 < curr->ckey->key3) {
249 break;
250 }
251
252 if (ckey->key1 == curr->ckey->key1 &&
253 ckey->key2 == curr->ckey->key2 &&
254 ckey->key3 == curr->ckey->key3 &&
255 ckey->key4 < curr->ckey->key4) {
256 break;
257 }
258 }
259
260 *out = NULL;
261 }
262
cil_complex_symtab_destroy(struct cil_complex_symtab * symtab)263 void cil_complex_symtab_destroy(struct cil_complex_symtab *symtab)
264 {
265 struct cil_complex_symtab_node *curr = NULL;
266 struct cil_complex_symtab_node *temp = NULL;
267 unsigned int i;
268
269 if (symtab == NULL) {
270 return;
271 }
272
273 for (i = 0; i < symtab->nslots; i++) {
274 curr = symtab->htable[i];
275 while (curr != NULL) {
276 temp = curr;
277 curr = curr->next;
278 free(temp);
279 }
280 symtab->htable[i] = NULL;
281 }
282 free(symtab->htable);
283 symtab->htable = NULL;
284 symtab->nelems = 0;
285 symtab->nslots = 0;
286 symtab->mask = 0;
287 }
288