/src/selinux/libsepol/cil/src/cil_tree.c

Source
/*
 * Copyright 2011 Tresys Technology, LLC. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 *    1. Redistributions of source code must retain the above copyright notice,
 *       this list of conditions and the following disclaimer.
 * 
 *    2. Redistributions in binary form must reproduce the above copyright notice,
 *       this list of conditions and the following disclaimer in the documentation
 *       and/or other materials provided with the distribution.
 * 
 * THIS SOFTWARE IS PROVIDED BY TRESYS TECHNOLOGY, LLC ``AS IS'' AND ANY EXPRESS
 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
 * EVENT SHALL TRESYS TECHNOLOGY, LLC OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * 
 * The views and conclusions contained in the software and documentation are those
 * of the authors and should not be interpreted as representing official policies,
 * either expressed or implied, of Tresys Technology, LLC.
 */

#include <stdio.h>
#include <stdarg.h>
#include <inttypes.h>

#include <sepol/policydb/conditional.h>

#include "cil_internal.h"
#include "cil_flavor.h"
#include "cil_log.h"
#include "cil_tree.h"
#include "cil_list.h"
#include "cil_parser.h"
#include "cil_strpool.h"

struct cil_tree_node *cil_tree_get_next_path(struct cil_tree_node *node,
               char **info_kind,
               uint32_t *hll_line, char **path)
{
  int rc;

  if (!node) {
    goto exit;
  }

  node = node->parent;

  while (node) {
    if (node->flavor == CIL_NODE && node->data == NULL) {
      if (node->cl_head &&
          node->cl_head->data == CIL_KEY_SRC_INFO) {
        if (!node->cl_head->next ||
            !node->cl_head->next->next ||
            !node->cl_head->next->next->next) {
          goto exit;
        }
        /* Parse Tree */
        *info_kind = node->cl_head->next->data;
        rc = cil_string_to_uint32(
          node->cl_head->next->next->data,
          hll_line, 10);
        if (rc != SEPOL_OK) {
          goto exit;
        }
        *path = node->cl_head->next->next->next->data;
        return node;
      }
      node = node->parent;
    } else if (node->flavor == CIL_SRC_INFO) {
      /* AST */
      struct cil_src_info *info = node->data;
      *info_kind = info->kind;
      *hll_line = info->hll_line;
      *path = info->path;
      return node;
    } else {
      if (node->flavor == CIL_CALL) {
        struct cil_call *call = node->data;
        node = NODE(call->macro);
      } else if (node->flavor == CIL_BLOCKINHERIT) {
        struct cil_blockinherit *inherit = node->data;
        node = NODE(inherit->block);
      } else {
        node = node->parent;
      }
    }
  }

exit:
  *info_kind = NULL;
  *hll_line = 0;
  *path = NULL;
  return NULL;
}

char *cil_tree_get_cil_path(struct cil_tree_node *node)
{
  char *info_kind;
  uint32_t hll_line;
  char *path;

  while (node) {
    node = cil_tree_get_next_path(node, &info_kind, &hll_line,
                &path);
    if (node && info_kind == CIL_KEY_SRC_CIL) {
      return path;
    }
  }

  return NULL;
}

__attribute__((format(printf, 3, 4))) void
cil_tree_log(struct cil_tree_node *node, enum cil_log_level lvl,
       const char *msg, ...)
{
  va_list ap;

  va_start(ap, msg);
  cil_vlog(lvl, msg, ap);
  va_end(ap);

  if (node) {
    char *path = NULL;
    uint32_t hll_offset = node->hll_offset;

    path = cil_tree_get_cil_path(node);

    if (path != NULL) {
      cil_log(lvl, " at %s:%u", path, node->line);
    }

    while (node) {
      do {
        char *info_kind;
        uint32_t hll_line;

        node = cil_tree_get_next_path(node, &info_kind,
                    &hll_line, &path);
        if (!node || info_kind == CIL_KEY_SRC_CIL) {
          break;
        }
        if (info_kind == CIL_KEY_SRC_HLL_LMS) {
          hll_line += hll_offset -
                node->hll_offset - 1;
        }

        cil_log(lvl, " from %s:%u", path, hll_line);
      } while (1);
    }
  }

  cil_log(lvl, "\n");
}

int cil_tree_subtree_has_decl(struct cil_tree_node *node)
{
  while (node) {
    if (node->flavor >= CIL_MIN_DECLARATIVE) {
      return CIL_TRUE;
    }
    if (node->cl_head != NULL) {
      if (cil_tree_subtree_has_decl(node->cl_head))
        return CIL_TRUE;
    }
    node = node->next;
  }

  return CIL_FALSE;
}

int cil_tree_init(struct cil_tree **tree)
{
  struct cil_tree *new_tree = cil_malloc(sizeof(*new_tree));

  cil_tree_node_init(&new_tree->root);

  *tree = new_tree;

  return SEPOL_OK;
}

void cil_tree_destroy(struct cil_tree **tree)
{
  if (tree == NULL || *tree == NULL) {
    return;
  }

  cil_tree_subtree_destroy((*tree)->root);
  free(*tree);
  *tree = NULL;
}

void cil_tree_subtree_destroy(struct cil_tree_node *node)
{
  cil_tree_children_destroy(node);
  cil_tree_node_destroy(&node);
}

void cil_tree_children_destroy(struct cil_tree_node *node)
{
  struct cil_tree_node *curr, *next;

  if (!node) {
    return;
  }

  curr = node->cl_head;
  while (curr) {
    next = curr->next;
    cil_tree_children_destroy(curr);
    cil_tree_node_destroy(&curr);
    curr = next;
  }
  node->cl_head = NULL;
  node->cl_tail = NULL;
}

void cil_tree_node_init(struct cil_tree_node **node)
{
  struct cil_tree_node *new_node = cil_malloc(sizeof(*new_node));
  new_node->cl_head = NULL;
  new_node->cl_tail = NULL;
  new_node->parent = NULL;
  new_node->data = NULL;
  new_node->next = NULL;
  new_node->flavor = CIL_ROOT;
  new_node->line = 0;
  new_node->hll_offset = 0;

  *node = new_node;
}

void cil_tree_node_destroy(struct cil_tree_node **node)
{
  struct cil_symtab_datum *datum;

  if (node == NULL || *node == NULL) {
    return;
  }

  if ((*node)->flavor >= CIL_MIN_DECLARATIVE) {
    datum = (*node)->data;
    cil_symtab_datum_remove_node(datum, *node);
    if (datum->nodes == NULL) {
      cil_destroy_data(&(*node)->data, (*node)->flavor);
    }
  } else {
    cil_destroy_data(&(*node)->data, (*node)->flavor);
  }
  free(*node);
  *node = NULL;
}

void cil_tree_node_remove(struct cil_tree_node *node)
{
  struct cil_tree_node *parent, *curr;

  if (node == NULL || node->parent == NULL) {
    return;
  }

  parent = node->parent;

  if (parent->cl_head == node) {
    if (parent->cl_tail == node) {
      parent->cl_tail = NULL;
    }
    parent->cl_head = node->next;
    cil_tree_node_destroy(&node);
    return;
  }

  curr = parent->cl_head;
  while (curr && curr->next != node) {
    curr = curr->next;
  }

  if (curr == NULL) {
    return;
  }

  if (parent->cl_tail == node) {
    parent->cl_tail = curr;
  }
  curr->next = node->next;
  cil_tree_node_destroy(&node);
}

/* Perform depth-first walk of the tree
   Parameters:
   start_node:          root node to start walking from
   process_node:        function to call when visiting a node
                        Takes parameters:
                            node:     node being visited
                            finished: boolean indicating to the tree walker that it should move on from this branch
                            extra_args:    additional data
   first_child:   Function to call before entering list of children
                        Takes parameters:
                            node:     node of first child
                            extra args:     additional data
   last_child:    Function to call when finished with the last child of a node's children
   extra_args:               any additional data to be passed to the helper functions
*/

static int 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)
{
  int rc = SEPOL_ERR;

  while (node) {
    uint32_t finished = CIL_TREE_SKIP_NOTHING;

    if (process_node != NULL) {
      rc = (*process_node)(node, &finished, extra_args);
      if (rc != SEPOL_OK) {
        cil_tree_log(node, CIL_INFO, "Problem");
        return rc;
      }
    }

    if (finished & CIL_TREE_SKIP_NEXT) {
      return SEPOL_OK;
    }

    if (node->cl_head != NULL && !(finished & CIL_TREE_SKIP_HEAD)) {
      rc = cil_tree_walk(node, process_node, first_child,
             last_child, extra_args);
      if (rc != SEPOL_OK) {
        return rc;
      }
    }

    node = node->next;
  }

  return SEPOL_OK;
}

int 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)
{
  int rc = SEPOL_ERR;

  if (!node || !node->cl_head) {
    return SEPOL_OK;
  }

  if (first_child != NULL) {
    rc = (*first_child)(node->cl_head, extra_args);
    if (rc != SEPOL_OK) {
      cil_tree_log(node, CIL_INFO, "Problem");
      return rc;
    }
  }

  rc = cil_tree_walk_core(node->cl_head, process_node, first_child,
        last_child, extra_args);
  if (rc != SEPOL_OK) {
    return rc;
  }

  if (last_child != NULL) {
    rc = (*last_child)(node->cl_tail, extra_args);
    if (rc != SEPOL_OK) {
      cil_tree_log(node, CIL_INFO, "Problem");
      return rc;
    }
  }

  return SEPOL_OK;
}

Coverage Report

Created: 2026-07-15 06:40

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