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 <stdio.h>
31 #include <stdarg.h>
32 #include <inttypes.h>
33
34 #include <sepol/policydb/conditional.h>
35
36 #include "cil_internal.h"
37 #include "cil_flavor.h"
38 #include "cil_log.h"
39 #include "cil_tree.h"
40 #include "cil_list.h"
41 #include "cil_parser.h"
42 #include "cil_strpool.h"
43
cil_tree_get_next_path(struct cil_tree_node * node,char ** info_kind,uint32_t * hll_line,char ** path)44 struct cil_tree_node *cil_tree_get_next_path(struct cil_tree_node *node, char **info_kind, uint32_t *hll_line, char **path)
45 {
46 int rc;
47
48 if (!node) {
49 goto exit;
50 }
51
52 node = node->parent;
53
54 while (node) {
55 if (node->flavor == CIL_NODE && node->data == NULL) {
56 if (node->cl_head && node->cl_head->data == CIL_KEY_SRC_INFO) {
57 if (!node->cl_head->next || !node->cl_head->next->next || !node->cl_head->next->next->next) {
58 goto exit;
59 }
60 /* Parse Tree */
61 *info_kind = node->cl_head->next->data;
62 rc = cil_string_to_uint32(node->cl_head->next->next->data, hll_line, 10);
63 if (rc != SEPOL_OK) {
64 goto exit;
65 }
66 *path = node->cl_head->next->next->next->data;
67 return node;
68 }
69 node = node->parent;
70 } else if (node->flavor == CIL_SRC_INFO) {
71 /* AST */
72 struct cil_src_info *info = node->data;
73 *info_kind = info->kind;
74 *hll_line = info->hll_line;
75 *path = info->path;
76 return node;
77 } else {
78 if (node->flavor == CIL_CALL) {
79 struct cil_call *call = node->data;
80 node = NODE(call->macro);
81 } else if (node->flavor == CIL_BLOCKINHERIT) {
82 struct cil_blockinherit *inherit = node->data;
83 node = NODE(inherit->block);
84 } else {
85 node = node->parent;
86 }
87 }
88 }
89
90 exit:
91 *info_kind = NULL;
92 *hll_line = 0;
93 *path = NULL;
94 return NULL;
95 }
96
cil_tree_get_cil_path(struct cil_tree_node * node)97 char *cil_tree_get_cil_path(struct cil_tree_node *node)
98 {
99 char *info_kind;
100 uint32_t hll_line;
101 char *path;
102
103 while (node) {
104 node = cil_tree_get_next_path(node, &info_kind, &hll_line, &path);
105 if (node && info_kind == CIL_KEY_SRC_CIL) {
106 return path;
107 }
108 }
109
110 return NULL;
111 }
112
cil_tree_log(struct cil_tree_node * node,enum cil_log_level lvl,const char * msg,...)113 __attribute__((format (printf, 3, 4))) void cil_tree_log(struct cil_tree_node *node, enum cil_log_level lvl, const char* msg, ...)
114 {
115 va_list ap;
116
117 va_start(ap, msg);
118 cil_vlog(lvl, msg, ap);
119 va_end(ap);
120
121 if (node) {
122 char *path = NULL;
123 uint32_t hll_offset = node->hll_offset;
124
125 path = cil_tree_get_cil_path(node);
126
127 if (path != NULL) {
128 cil_log(lvl, " at %s:%u", path, node->line);
129 }
130
131 while (node) {
132 do {
133 char *info_kind;
134 uint32_t hll_line;
135
136 node = cil_tree_get_next_path(node, &info_kind, &hll_line, &path);
137 if (!node || info_kind == CIL_KEY_SRC_CIL) {
138 break;
139 }
140 if (info_kind == CIL_KEY_SRC_HLL_LMS) {
141 hll_line += hll_offset - node->hll_offset - 1;
142 }
143
144 cil_log(lvl," from %s:%u", path, hll_line);
145 } while (1);
146 }
147 }
148
149 cil_log(lvl,"\n");
150 }
151
cil_tree_subtree_has_decl(struct cil_tree_node * node)152 int cil_tree_subtree_has_decl(struct cil_tree_node *node)
153 {
154 while (node) {
155 if (node->flavor >= CIL_MIN_DECLARATIVE) {
156 return CIL_TRUE;
157 }
158 if (node->cl_head != NULL) {
159 if (cil_tree_subtree_has_decl(node->cl_head))
160 return CIL_TRUE;
161 }
162 node = node->next;
163 }
164
165 return CIL_FALSE;
166 }
167
cil_tree_init(struct cil_tree ** tree)168 int cil_tree_init(struct cil_tree **tree)
169 {
170 struct cil_tree *new_tree = cil_malloc(sizeof(*new_tree));
171
172 cil_tree_node_init(&new_tree->root);
173
174 *tree = new_tree;
175
176 return SEPOL_OK;
177 }
178
cil_tree_destroy(struct cil_tree ** tree)179 void cil_tree_destroy(struct cil_tree **tree)
180 {
181 if (tree == NULL || *tree == NULL) {
182 return;
183 }
184
185 cil_tree_subtree_destroy((*tree)->root);
186 free(*tree);
187 *tree = NULL;
188 }
189
cil_tree_subtree_destroy(struct cil_tree_node * node)190 void cil_tree_subtree_destroy(struct cil_tree_node *node)
191 {
192 cil_tree_children_destroy(node);
193 cil_tree_node_destroy(&node);
194 }
195
cil_tree_children_destroy(struct cil_tree_node * node)196 void cil_tree_children_destroy(struct cil_tree_node *node)
197 {
198 struct cil_tree_node *curr, *next;
199
200 if (!node) {
201 return;
202 }
203
204 curr = node->cl_head;
205 while (curr) {
206 next = curr->next;
207 cil_tree_children_destroy(curr);
208 cil_tree_node_destroy(&curr);
209 curr = next;
210 }
211 node->cl_head = NULL;
212 node->cl_tail = NULL;
213 }
214
cil_tree_node_init(struct cil_tree_node ** node)215 void cil_tree_node_init(struct cil_tree_node **node)
216 {
217 struct cil_tree_node *new_node = cil_malloc(sizeof(*new_node));
218 new_node->cl_head = NULL;
219 new_node->cl_tail = NULL;
220 new_node->parent = NULL;
221 new_node->data = NULL;
222 new_node->next = NULL;
223 new_node->flavor = CIL_ROOT;
224 new_node->line = 0;
225 new_node->hll_offset = 0;
226
227 *node = new_node;
228 }
229
cil_tree_node_destroy(struct cil_tree_node ** node)230 void cil_tree_node_destroy(struct cil_tree_node **node)
231 {
232 struct cil_symtab_datum *datum;
233
234 if (node == NULL || *node == NULL) {
235 return;
236 }
237
238 if ((*node)->flavor >= CIL_MIN_DECLARATIVE) {
239 datum = (*node)->data;
240 cil_symtab_datum_remove_node(datum, *node);
241 if (datum->nodes == NULL) {
242 cil_destroy_data(&(*node)->data, (*node)->flavor);
243 }
244 } else {
245 cil_destroy_data(&(*node)->data, (*node)->flavor);
246 }
247 free(*node);
248 *node = NULL;
249 }
250
cil_tree_node_remove(struct cil_tree_node * node)251 void cil_tree_node_remove(struct cil_tree_node *node)
252 {
253 struct cil_tree_node *parent, *curr;
254
255 if (node == NULL || node->parent == NULL) {
256 return;
257 }
258
259 parent = node->parent;
260
261 if (parent->cl_head == node) {
262 if (parent->cl_tail == node) {
263 parent->cl_tail = NULL;
264 }
265 parent->cl_head = node->next;
266 cil_tree_node_destroy(&node);
267 return;
268 }
269
270 curr = parent->cl_head;
271 while (curr && curr->next != node) {
272 curr = curr->next;
273 }
274
275 if (curr == NULL) {
276 return;
277 }
278
279 if (parent->cl_tail == node) {
280 parent->cl_tail = curr;
281 }
282 curr->next = node->next;
283 cil_tree_node_destroy(&node);
284 }
285
286 /* Perform depth-first walk of the tree
287 Parameters:
288 start_node: root node to start walking from
289 process_node: function to call when visiting a node
290 Takes parameters:
291 node: node being visited
292 finished: boolean indicating to the tree walker that it should move on from this branch
293 extra_args: additional data
294 first_child: Function to call before entering list of children
295 Takes parameters:
296 node: node of first child
297 extra args: additional data
298 last_child: Function to call when finished with the last child of a node's children
299 extra_args: any additional data to be passed to the helper functions
300 */
301
cil_tree_walk_core(struct cil_tree_node * node,int (* process_node)(struct cil_tree_node * node,uint32_t * finished,void * extra_args),int (* first_child)(struct cil_tree_node * node,void * extra_args),int (* last_child)(struct cil_tree_node * node,void * extra_args),void * extra_args)302 static int cil_tree_walk_core(struct cil_tree_node *node,
303 int (*process_node)(struct cil_tree_node *node, uint32_t *finished, void *extra_args),
304 int (*first_child)(struct cil_tree_node *node, void *extra_args),
305 int (*last_child)(struct cil_tree_node *node, void *extra_args),
306 void *extra_args)
307 {
308 int rc = SEPOL_ERR;
309
310 while (node) {
311 uint32_t finished = CIL_TREE_SKIP_NOTHING;
312
313 if (process_node != NULL) {
314 rc = (*process_node)(node, &finished, extra_args);
315 if (rc != SEPOL_OK) {
316 cil_tree_log(node, CIL_INFO, "Problem");
317 return rc;
318 }
319 }
320
321 if (finished & CIL_TREE_SKIP_NEXT) {
322 return SEPOL_OK;
323 }
324
325 if (node->cl_head != NULL && !(finished & CIL_TREE_SKIP_HEAD)) {
326 rc = cil_tree_walk(node, process_node, first_child, last_child, extra_args);
327 if (rc != SEPOL_OK) {
328 return rc;
329 }
330 }
331
332 node = node->next;
333 }
334
335 return SEPOL_OK;
336 }
337
cil_tree_walk(struct cil_tree_node * node,int (* process_node)(struct cil_tree_node * node,uint32_t * finished,void * extra_args),int (* first_child)(struct cil_tree_node * node,void * extra_args),int (* last_child)(struct cil_tree_node * node,void * extra_args),void * extra_args)338 int cil_tree_walk(struct cil_tree_node *node,
339 int (*process_node)(struct cil_tree_node *node, uint32_t *finished, void *extra_args),
340 int (*first_child)(struct cil_tree_node *node, void *extra_args),
341 int (*last_child)(struct cil_tree_node *node, void *extra_args),
342 void *extra_args)
343 {
344 int rc = SEPOL_ERR;
345
346 if (!node || !node->cl_head) {
347 return SEPOL_OK;
348 }
349
350 if (first_child != NULL) {
351 rc = (*first_child)(node->cl_head, extra_args);
352 if (rc != SEPOL_OK) {
353 cil_tree_log(node, CIL_INFO, "Problem");
354 return rc;
355 }
356 }
357
358 rc = cil_tree_walk_core(node->cl_head, process_node, first_child, last_child, extra_args);
359 if (rc != SEPOL_OK) {
360 return rc;
361 }
362
363 if (last_child != NULL) {
364 rc = (*last_child)(node->cl_tail, extra_args);
365 if (rc != SEPOL_OK) {
366 cil_tree_log(node, CIL_INFO, "Problem");
367 return rc;
368 }
369 }
370
371 return SEPOL_OK;
372 }
373