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