/src/selinux/libsepol/cil/src/cil_tree.c
Line | Count | Source |
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 | | |
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 | 2.62M | { |
46 | 2.62M | int rc; |
47 | | |
48 | 2.62M | if (!node) { |
49 | 0 | goto exit; |
50 | 0 | } |
51 | | |
52 | 2.62M | node = node->parent; |
53 | | |
54 | 15.6M | while (node) { |
55 | 14.7M | if (node->flavor == CIL_NODE && node->data == NULL) { |
56 | 15.7k | if (node->cl_head && node->cl_head->data == CIL_KEY_SRC_INFO) { |
57 | 6.12k | if (!node->cl_head->next || !node->cl_head->next->next || !node->cl_head->next->next->next) { |
58 | 26 | goto exit; |
59 | 26 | } |
60 | | /* Parse Tree */ |
61 | 6.10k | *info_kind = node->cl_head->next->data; |
62 | 6.10k | rc = cil_string_to_uint32(node->cl_head->next->next->data, hll_line, 10); |
63 | 6.10k | if (rc != SEPOL_OK) { |
64 | 50 | goto exit; |
65 | 50 | } |
66 | 6.05k | *path = node->cl_head->next->next->next->data; |
67 | 6.05k | return node; |
68 | 6.10k | } |
69 | 9.64k | node = node->parent; |
70 | 14.7M | } else if (node->flavor == CIL_SRC_INFO) { |
71 | | /* AST */ |
72 | 1.69M | struct cil_src_info *info = node->data; |
73 | 1.69M | *info_kind = info->kind; |
74 | 1.69M | *hll_line = info->hll_line; |
75 | 1.69M | *path = info->path; |
76 | 1.69M | return node; |
77 | 13.0M | } else { |
78 | 13.0M | if (node->flavor == CIL_CALL) { |
79 | 634k | struct cil_call *call = node->data; |
80 | 634k | node = NODE(call->macro); |
81 | 12.4M | } else if (node->flavor == CIL_BLOCKINHERIT) { |
82 | 500k | struct cil_blockinherit *inherit = node->data; |
83 | 500k | node = NODE(inherit->block); |
84 | 11.9M | } else { |
85 | 11.9M | node = node->parent; |
86 | 11.9M | } |
87 | 13.0M | } |
88 | 14.7M | } |
89 | | |
90 | 918k | exit: |
91 | 918k | *info_kind = NULL; |
92 | 918k | *hll_line = 0; |
93 | 918k | *path = NULL; |
94 | 918k | return NULL; |
95 | 2.62M | } |
96 | | |
97 | | char *cil_tree_get_cil_path(struct cil_tree_node *node) |
98 | 874k | { |
99 | 874k | char *info_kind; |
100 | 874k | uint32_t hll_line; |
101 | 874k | char *path; |
102 | | |
103 | 919k | while (node) { |
104 | 875k | node = cil_tree_get_next_path(node, &info_kind, &hll_line, &path); |
105 | 875k | if (node && info_kind == CIL_KEY_SRC_CIL) { |
106 | 830k | return path; |
107 | 830k | } |
108 | 875k | } |
109 | | |
110 | 44.2k | return NULL; |
111 | 874k | } |
112 | | |
113 | | __attribute__((format (printf, 3, 4))) void cil_tree_log(struct cil_tree_node *node, enum cil_log_level lvl, const char* msg, ...) |
114 | 874k | { |
115 | 874k | va_list ap; |
116 | | |
117 | 874k | va_start(ap, msg); |
118 | 874k | cil_vlog(lvl, msg, ap); |
119 | 874k | va_end(ap); |
120 | | |
121 | 874k | if (node) { |
122 | 874k | char *path = NULL; |
123 | 874k | uint32_t hll_offset = node->hll_offset; |
124 | | |
125 | 874k | path = cil_tree_get_cil_path(node); |
126 | | |
127 | 874k | if (path != NULL) { |
128 | 830k | cil_log(lvl, " at %s:%u", path, node->line); |
129 | 830k | } |
130 | | |
131 | 2.57M | while (node) { |
132 | 1.70M | do { |
133 | 1.70M | char *info_kind; |
134 | 1.70M | uint32_t hll_line; |
135 | | |
136 | 1.70M | node = cil_tree_get_next_path(node, &info_kind, &hll_line, &path); |
137 | 1.70M | if (!node || info_kind == CIL_KEY_SRC_CIL) { |
138 | 1.70M | break; |
139 | 1.70M | } |
140 | 790 | if (info_kind == CIL_KEY_SRC_HLL_LMS) { |
141 | 239 | hll_line += hll_offset - node->hll_offset - 1; |
142 | 239 | } |
143 | | |
144 | 790 | cil_log(lvl," from %s:%u", path, hll_line); |
145 | 790 | } while (1); |
146 | 1.70M | } |
147 | 874k | } |
148 | | |
149 | 874k | cil_log(lvl,"\n"); |
150 | 874k | } |
151 | | |
152 | | int cil_tree_subtree_has_decl(struct cil_tree_node *node) |
153 | 3.40k | { |
154 | 3.40k | while (node) { |
155 | 3.40k | if (node->flavor >= CIL_MIN_DECLARATIVE) { |
156 | 3.40k | return CIL_TRUE; |
157 | 3.40k | } |
158 | 0 | if (node->cl_head != NULL) { |
159 | 0 | if (cil_tree_subtree_has_decl(node->cl_head)) |
160 | 0 | return CIL_TRUE; |
161 | 0 | } |
162 | 0 | node = node->next; |
163 | 0 | } |
164 | | |
165 | 0 | return CIL_FALSE; |
166 | 3.40k | } |
167 | | |
168 | | int cil_tree_init(struct cil_tree **tree) |
169 | 89.7k | { |
170 | 89.7k | struct cil_tree *new_tree = cil_malloc(sizeof(*new_tree)); |
171 | | |
172 | 89.7k | cil_tree_node_init(&new_tree->root); |
173 | | |
174 | 89.7k | *tree = new_tree; |
175 | | |
176 | 89.7k | return SEPOL_OK; |
177 | 89.7k | } |
178 | | |
179 | | void cil_tree_destroy(struct cil_tree **tree) |
180 | 103k | { |
181 | 103k | if (tree == NULL || *tree == NULL) { |
182 | 13.4k | return; |
183 | 13.4k | } |
184 | | |
185 | 89.7k | cil_tree_subtree_destroy((*tree)->root); |
186 | 89.7k | free(*tree); |
187 | 89.7k | *tree = NULL; |
188 | 89.7k | } |
189 | | |
190 | | void cil_tree_subtree_destroy(struct cil_tree_node *node) |
191 | 110k | { |
192 | 110k | cil_tree_children_destroy(node); |
193 | 110k | cil_tree_node_destroy(&node); |
194 | 110k | } |
195 | | |
196 | | void cil_tree_children_destroy(struct cil_tree_node *node) |
197 | 11.4M | { |
198 | 11.4M | struct cil_tree_node *curr, *next; |
199 | | |
200 | 11.4M | if (!node) { |
201 | 0 | return; |
202 | 0 | } |
203 | | |
204 | 11.4M | curr = node->cl_head; |
205 | 22.0M | while (curr) { |
206 | 10.6M | next = curr->next; |
207 | 10.6M | cil_tree_children_destroy(curr); |
208 | 10.6M | cil_tree_node_destroy(&curr); |
209 | 10.6M | curr = next; |
210 | 10.6M | } |
211 | 11.4M | node->cl_head = NULL; |
212 | 11.4M | node->cl_tail = NULL; |
213 | 11.4M | } |
214 | | |
215 | | void cil_tree_node_init(struct cil_tree_node **node) |
216 | 10.9M | { |
217 | 10.9M | struct cil_tree_node *new_node = cil_malloc(sizeof(*new_node)); |
218 | 10.9M | new_node->cl_head = NULL; |
219 | 10.9M | new_node->cl_tail = NULL; |
220 | 10.9M | new_node->parent = NULL; |
221 | 10.9M | new_node->data = NULL; |
222 | 10.9M | new_node->next = NULL; |
223 | 10.9M | new_node->flavor = CIL_ROOT; |
224 | 10.9M | new_node->line = 0; |
225 | 10.9M | new_node->hll_offset = 0; |
226 | | |
227 | 10.9M | *node = new_node; |
228 | 10.9M | } |
229 | | |
230 | | void cil_tree_node_destroy(struct cil_tree_node **node) |
231 | 10.9M | { |
232 | 10.9M | struct cil_symtab_datum *datum; |
233 | | |
234 | 10.9M | if (node == NULL || *node == NULL) { |
235 | 25 | return; |
236 | 25 | } |
237 | | |
238 | 10.9M | if ((*node)->flavor >= CIL_MIN_DECLARATIVE) { |
239 | 1.85M | datum = (*node)->data; |
240 | 1.85M | cil_symtab_datum_remove_node(datum, *node); |
241 | 1.85M | if (datum->nodes == NULL) { |
242 | 1.56M | cil_destroy_data(&(*node)->data, (*node)->flavor); |
243 | 1.56M | } |
244 | 9.10M | } else { |
245 | 9.10M | cil_destroy_data(&(*node)->data, (*node)->flavor); |
246 | 9.10M | } |
247 | 10.9M | free(*node); |
248 | 10.9M | *node = NULL; |
249 | 10.9M | } |
250 | | |
251 | | void cil_tree_node_remove(struct cil_tree_node *node) |
252 | 232k | { |
253 | 232k | struct cil_tree_node *parent, *curr; |
254 | | |
255 | 232k | if (node == NULL || node->parent == NULL) { |
256 | 0 | return; |
257 | 0 | } |
258 | | |
259 | 232k | parent = node->parent; |
260 | | |
261 | 232k | if (parent->cl_head == node) { |
262 | 4.90k | if (parent->cl_tail == node) { |
263 | 956 | parent->cl_tail = NULL; |
264 | 956 | } |
265 | 4.90k | parent->cl_head = node->next; |
266 | 4.90k | cil_tree_node_destroy(&node); |
267 | 4.90k | return; |
268 | 4.90k | } |
269 | | |
270 | 228k | curr = parent->cl_head; |
271 | 6.73M | while (curr && curr->next != node) { |
272 | 6.50M | curr = curr->next; |
273 | 6.50M | } |
274 | | |
275 | 228k | if (curr == NULL) { |
276 | 0 | return; |
277 | 0 | } |
278 | | |
279 | 228k | if (parent->cl_tail == node) { |
280 | 4.45k | parent->cl_tail = curr; |
281 | 4.45k | } |
282 | 228k | curr->next = node->next; |
283 | 228k | cil_tree_node_destroy(&node); |
284 | 228k | } |
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 | | |
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 | 60.2M | { |
308 | 60.2M | int rc = SEPOL_ERR; |
309 | | |
310 | 423M | while (node) { |
311 | 364M | uint32_t finished = CIL_TREE_SKIP_NOTHING; |
312 | | |
313 | 364M | if (process_node != NULL) { |
314 | 364M | rc = (*process_node)(node, &finished, extra_args); |
315 | 364M | if (rc != SEPOL_OK) { |
316 | 6.96k | cil_tree_log(node, CIL_INFO, "Problem"); |
317 | 6.96k | return rc; |
318 | 6.96k | } |
319 | 364M | } |
320 | | |
321 | 364M | if (finished & CIL_TREE_SKIP_NEXT) { |
322 | 527k | return SEPOL_OK; |
323 | 527k | } |
324 | | |
325 | 363M | if (node->cl_head != NULL && !(finished & CIL_TREE_SKIP_HEAD)) { |
326 | 59.0M | rc = cil_tree_walk(node, process_node, first_child, last_child, extra_args); |
327 | 59.0M | if (rc != SEPOL_OK) { |
328 | 14.1k | return rc; |
329 | 14.1k | } |
330 | 59.0M | } |
331 | | |
332 | 363M | node = node->next; |
333 | 363M | } |
334 | | |
335 | 59.6M | return SEPOL_OK; |
336 | 60.2M | } |
337 | | |
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 | 60.2M | { |
344 | 60.2M | int rc = SEPOL_ERR; |
345 | | |
346 | 60.2M | if (!node || !node->cl_head) { |
347 | 27.6k | return SEPOL_OK; |
348 | 27.6k | } |
349 | | |
350 | 60.2M | if (first_child != NULL) { |
351 | 14.9M | rc = (*first_child)(node->cl_head, extra_args); |
352 | 14.9M | if (rc != SEPOL_OK) { |
353 | 0 | cil_tree_log(node, CIL_INFO, "Problem"); |
354 | 0 | return rc; |
355 | 0 | } |
356 | 14.9M | } |
357 | | |
358 | 60.2M | rc = cil_tree_walk_core(node->cl_head, process_node, first_child, last_child, extra_args); |
359 | 60.2M | if (rc != SEPOL_OK) { |
360 | 21.0k | return rc; |
361 | 21.0k | } |
362 | | |
363 | 60.2M | if (last_child != NULL) { |
364 | 16.2M | rc = (*last_child)(node->cl_tail, extra_args); |
365 | 16.2M | if (rc != SEPOL_OK) { |
366 | 0 | cil_tree_log(node, CIL_INFO, "Problem"); |
367 | 0 | return rc; |
368 | 0 | } |
369 | 16.2M | } |
370 | | |
371 | 60.2M | return SEPOL_OK; |
372 | 60.2M | } |