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 symtab->nprim++;
96 if (node) {
97 cil_list_append(datum->nodes, CIL_NODE, node);
98 }
99 } else if (rc != SEPOL_EEXIST) {
100 cil_symtab_error("Failed to insert datum into hashtab\n");
101 }
102
103 return rc;
104 }
105
cil_symtab_remove_datum(struct cil_symtab_datum * datum)106 void cil_symtab_remove_datum(struct cil_symtab_datum *datum)
107 {
108 symtab_t *symtab = datum->symtab;
109
110 if (symtab == NULL) {
111 return;
112 }
113
114 hashtab_remove(symtab->table, datum->name, NULL, NULL);
115 symtab->nprim--;
116 datum->symtab = NULL;
117 }
118
cil_symtab_get_datum(symtab_t * symtab,char * key,struct cil_symtab_datum ** datum)119 int cil_symtab_get_datum(symtab_t *symtab, char *key, struct cil_symtab_datum **datum)
120 {
121 *datum = (struct cil_symtab_datum*)hashtab_search(symtab->table, (hashtab_key_t)key);
122 if (*datum == NULL) {
123 return SEPOL_ENOENT;
124 }
125
126 return SEPOL_OK;
127 }
128
cil_symtab_map(symtab_t * symtab,int (* apply)(hashtab_key_t k,hashtab_datum_t d,void * args),void * args)129 int cil_symtab_map(symtab_t *symtab,
130 int (*apply) (hashtab_key_t k, hashtab_datum_t d, void *args),
131 void *args)
132 {
133 return hashtab_map(symtab->table, apply, args);
134 }
135
__cil_symtab_destroy_helper(hashtab_key_t k,hashtab_datum_t d,void * args)136 static int __cil_symtab_destroy_helper(__attribute__((unused)) hashtab_key_t k, hashtab_datum_t d, __attribute__((unused)) void *args)
137 {
138 struct cil_symtab_datum *datum = d;
139 datum->symtab = NULL;
140 return SEPOL_OK;
141 }
142
cil_symtab_destroy(symtab_t * symtab)143 void cil_symtab_destroy(symtab_t *symtab)
144 {
145 if (symtab->table != NULL){
146 cil_symtab_map(symtab, __cil_symtab_destroy_helper, NULL);
147 hashtab_destroy(symtab->table);
148 symtab->table = NULL;
149 }
150 }
151
cil_complex_symtab_hash(struct cil_complex_symtab_key * ckey,int mask,intptr_t * hash)152 void cil_complex_symtab_hash(struct cil_complex_symtab_key *ckey, int mask, intptr_t *hash)
153 {
154 intptr_t sum = ckey->key1 + ckey->key2 + ckey->key3 + ckey->key4;
155 *hash = (intptr_t)((sum >> 2) & mask);
156 }
157
cil_complex_symtab_init(struct cil_complex_symtab * symtab,unsigned int size)158 void cil_complex_symtab_init(struct cil_complex_symtab *symtab, unsigned int size)
159 {
160 symtab->htable = cil_calloc(size, sizeof(struct cil_complex_symtab *));
161
162 symtab->nelems = 0;
163 symtab->nslots = size;
164 symtab->mask = size - 1;
165 }
166
cil_complex_symtab_insert(struct cil_complex_symtab * symtab,struct cil_complex_symtab_key * ckey,struct cil_complex_symtab_datum * datum)167 int cil_complex_symtab_insert(struct cil_complex_symtab *symtab,
168 struct cil_complex_symtab_key *ckey,
169 struct cil_complex_symtab_datum *datum)
170 {
171 intptr_t hash;
172 struct cil_complex_symtab_node *node = NULL;
173 struct cil_complex_symtab_node *prev = NULL;
174 struct cil_complex_symtab_node *curr = NULL;
175
176 node = cil_malloc(sizeof(*node));
177 memset(node, 0, sizeof(*node));
178
179 node->ckey = ckey;
180 node->datum = datum;
181
182 cil_complex_symtab_hash(ckey, symtab->mask, &hash);
183
184 for (prev = NULL, curr = symtab->htable[hash]; curr != NULL;
185 prev = curr, curr = curr->next) {
186 if (ckey->key1 == curr->ckey->key1 &&
187 ckey->key2 == curr->ckey->key2 &&
188 ckey->key3 == curr->ckey->key3 &&
189 ckey->key4 == curr->ckey->key4) {
190 free(node);
191 return SEPOL_EEXIST;
192 }
193
194 if (ckey->key1 == curr->ckey->key1 &&
195 ckey->key2 < curr->ckey->key2) {
196 break;
197 }
198
199 if (ckey->key1 == curr->ckey->key1 &&
200 ckey->key2 == curr->ckey->key2 &&
201 ckey->key3 < curr->ckey->key3) {
202 break;
203 }
204
205 if (ckey->key1 == curr->ckey->key1 &&
206 ckey->key2 == curr->ckey->key2 &&
207 ckey->key3 == curr->ckey->key3 &&
208 ckey->key4 < curr->ckey->key4) {
209 break;
210 }
211 }
212
213 if (prev != NULL) {
214 node->next = prev->next;
215 prev->next = node;
216 } else {
217 node->next = symtab->htable[hash];
218 symtab->htable[hash] = node;
219 }
220
221 symtab->nelems++;
222
223 return SEPOL_OK;
224 }
225
cil_complex_symtab_search(struct cil_complex_symtab * symtab,struct cil_complex_symtab_key * ckey,struct cil_complex_symtab_datum ** out)226 void cil_complex_symtab_search(struct cil_complex_symtab *symtab,
227 struct cil_complex_symtab_key *ckey,
228 struct cil_complex_symtab_datum **out)
229 {
230 intptr_t hash;
231 struct cil_complex_symtab_node *curr = NULL;
232
233 cil_complex_symtab_hash(ckey, symtab->mask, &hash);
234 for (curr = symtab->htable[hash]; curr != NULL; curr = curr->next) {
235 if (ckey->key1 == curr->ckey->key1 &&
236 ckey->key2 == curr->ckey->key2 &&
237 ckey->key3 == curr->ckey->key3 &&
238 ckey->key4 == curr->ckey->key4) {
239 *out = curr->datum;
240 return;
241 }
242
243 if (ckey->key1 == curr->ckey->key1 &&
244 ckey->key2 < curr->ckey->key2) {
245 break;
246 }
247
248 if (ckey->key1 == curr->ckey->key1 &&
249 ckey->key2 == curr->ckey->key2 &&
250 ckey->key3 < curr->ckey->key3) {
251 break;
252 }
253
254 if (ckey->key1 == curr->ckey->key1 &&
255 ckey->key2 == curr->ckey->key2 &&
256 ckey->key3 == curr->ckey->key3 &&
257 ckey->key4 < curr->ckey->key4) {
258 break;
259 }
260 }
261
262 *out = NULL;
263 }
264
cil_complex_symtab_destroy(struct cil_complex_symtab * symtab)265 void cil_complex_symtab_destroy(struct cil_complex_symtab *symtab)
266 {
267 struct cil_complex_symtab_node *curr = NULL;
268 struct cil_complex_symtab_node *temp = NULL;
269 unsigned int i;
270
271 if (symtab == NULL) {
272 return;
273 }
274
275 for (i = 0; i < symtab->nslots; i++) {
276 curr = symtab->htable[i];
277 while (curr != NULL) {
278 temp = curr;
279 curr = curr->next;
280 free(temp);
281 }
282 symtab->htable[i] = NULL;
283 }
284 free(symtab->htable);
285 symtab->htable = NULL;
286 symtab->nelems = 0;
287 symtab->nslots = 0;
288 symtab->mask = 0;
289 }
290