Coverage Report

Created: 2025-10-10 06:16

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/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
}