/src/selinux/libsepol/cil/src/cil_symtab.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 <stdlib.h>
#include <string.h>
#include <stdarg.h>

#include <sepol/errcodes.h>
#include <sepol/policydb/hashtab.h>
#include <sepol/policydb/symtab.h>

#include "cil_internal.h"
#include "cil_tree.h"
#include "cil_symtab.h"
#include "cil_mem.h"
#include "cil_strpool.h"
#include "cil_log.h"

__attribute__((noreturn)) __attribute__((format(printf, 1, 2))) static void
cil_symtab_error(const char *msg, ...)
{
  va_list ap;
  va_start(ap, msg);
  cil_vlog(CIL_ERR, msg, ap);
  va_end(ap);
  exit(1);
}

void cil_symtab_init(symtab_t *symtab, unsigned int size)
{
  int rc = symtab_init(symtab, size);
  if (rc != SEPOL_OK) {
    cil_symtab_error("Failed to create symtab\n");
  }
}

void cil_symtab_datum_init(struct cil_symtab_datum *datum)
{
  datum->name = NULL;
  datum->fqn = NULL;
  datum->symtab = NULL;
  cil_list_init(&datum->nodes, CIL_LIST_ITEM);
}

void cil_symtab_datum_destroy(struct cil_symtab_datum *datum)
{
  cil_list_destroy(&datum->nodes, 0);
  cil_symtab_remove_datum(datum);
}

void cil_symtab_datum_remove_node(struct cil_symtab_datum *datum,
          struct cil_tree_node *node)
{
  if (datum && datum->nodes != NULL) {
    cil_list_remove(datum->nodes, CIL_NODE, node, 0);
    if (datum->nodes->head == NULL) {
      cil_symtab_datum_destroy(datum);
    }
  }
}

/* This both initializes the datum and inserts it into the symtab.
   Note that cil_symtab_datum_destroy() is the analog to the initializer portion */
int cil_symtab_insert(symtab_t *symtab, hashtab_key_t key,
          struct cil_symtab_datum *datum,
          struct cil_tree_node *node)
{
  int rc = hashtab_insert(symtab->table, key, (hashtab_datum_t)datum);
  if (rc == SEPOL_OK) {
    datum->name = key;
    datum->fqn = key;
    datum->symtab = symtab;
    symtab->nprim++;
    if (node) {
      cil_list_append(datum->nodes, CIL_NODE, node);
    }
  } else if (rc != SEPOL_EEXIST) {
    cil_symtab_error("Failed to insert datum into hashtab\n");
  }

  return rc;
}

void cil_symtab_remove_datum(struct cil_symtab_datum *datum)
{
  symtab_t *symtab = datum->symtab;

  if (symtab == NULL) {
    return;
  }

  hashtab_remove(symtab->table, datum->name, NULL, NULL);
  symtab->nprim--;
  datum->symtab = NULL;
}

int cil_symtab_get_datum(symtab_t *symtab, char *key,
       struct cil_symtab_datum **datum)
{
  *datum = (struct cil_symtab_datum *)hashtab_search(symtab->table,
                 (hashtab_key_t)key);
  if (*datum == NULL) {
    return SEPOL_ENOENT;
  }

  return SEPOL_OK;
}

int cil_symtab_map(symtab_t *symtab,
       int (*apply)(hashtab_key_t k, hashtab_datum_t d, void *args),
       void *args)
{
  return hashtab_map(symtab->table, apply, args);
}

static int __cil_symtab_destroy_helper(__attribute__((unused)) hashtab_key_t k,
               hashtab_datum_t d,
               __attribute__((unused)) void *args)
{
  struct cil_symtab_datum *datum = d;
  datum->symtab = NULL;
  return SEPOL_OK;
}

void cil_symtab_destroy(symtab_t *symtab)
{
  if (symtab->table != NULL) {
    cil_symtab_map(symtab, __cil_symtab_destroy_helper, NULL);
    hashtab_destroy(symtab->table);
    symtab->table = NULL;
  }
}

static void cil_complex_symtab_hash(struct cil_complex_symtab_key *ckey,
            int mask, intptr_t *hash)
{
  intptr_t sum = ckey->key1 + ckey->key2 + ckey->key3 + ckey->key4;
  *hash = (intptr_t)((sum >> 2) & mask);
}

void cil_complex_symtab_init(struct cil_complex_symtab *symtab,
           unsigned int size)
{
  symtab->htable = cil_calloc(size, sizeof(struct cil_complex_symtab *));

  symtab->nelems = 0;
  symtab->nslots = size;
  symtab->mask = size - 1;
}

int cil_complex_symtab_insert(struct cil_complex_symtab *symtab,
            struct cil_complex_symtab_key *ckey,
            struct cil_complex_symtab_datum *datum)
{
  intptr_t hash;
  struct cil_complex_symtab_node *node = NULL;
  struct cil_complex_symtab_node *prev = NULL;
  struct cil_complex_symtab_node *curr = NULL;

  node = cil_malloc(sizeof(*node));
  memset(node, 0, sizeof(*node));

  node->ckey = ckey;
  node->datum = datum;

  cil_complex_symtab_hash(ckey, symtab->mask, &hash);

  for (prev = NULL, curr = symtab->htable[hash]; curr != NULL;
       prev = curr, curr = curr->next) {
    if (ckey->key1 == curr->ckey->key1 &&
        ckey->key2 == curr->ckey->key2 &&
        ckey->key3 == curr->ckey->key3 &&
        ckey->key4 == curr->ckey->key4) {
      free(node);
      return SEPOL_EEXIST;
    }

    if (ckey->key1 == curr->ckey->key1 &&
        ckey->key2 < curr->ckey->key2) {
      break;
    }

    if (ckey->key1 == curr->ckey->key1 &&
        ckey->key2 == curr->ckey->key2 &&
        ckey->key3 < curr->ckey->key3) {
      break;
    }

    if (ckey->key1 == curr->ckey->key1 &&
        ckey->key2 == curr->ckey->key2 &&
        ckey->key3 == curr->ckey->key3 &&
        ckey->key4 < curr->ckey->key4) {
      break;
    }
  }

  if (prev != NULL) {
    node->next = prev->next;
    prev->next = node;
  } else {
    node->next = symtab->htable[hash];
    symtab->htable[hash] = node;
  }

  symtab->nelems++;

  return SEPOL_OK;
}

void cil_complex_symtab_search(struct cil_complex_symtab *symtab,
             struct cil_complex_symtab_key *ckey,
             struct cil_complex_symtab_datum **out)
{
  intptr_t hash;
  struct cil_complex_symtab_node *curr = NULL;

  cil_complex_symtab_hash(ckey, symtab->mask, &hash);
  for (curr = symtab->htable[hash]; curr != NULL; curr = curr->next) {
    if (ckey->key1 == curr->ckey->key1 &&
        ckey->key2 == curr->ckey->key2 &&
        ckey->key3 == curr->ckey->key3 &&
        ckey->key4 == curr->ckey->key4) {
      *out = curr->datum;
      return;
    }

    if (ckey->key1 == curr->ckey->key1 &&
        ckey->key2 < curr->ckey->key2) {
      break;
    }

    if (ckey->key1 == curr->ckey->key1 &&
        ckey->key2 == curr->ckey->key2 &&
        ckey->key3 < curr->ckey->key3) {
      break;
    }

    if (ckey->key1 == curr->ckey->key1 &&
        ckey->key2 == curr->ckey->key2 &&
        ckey->key3 == curr->ckey->key3 &&
        ckey->key4 < curr->ckey->key4) {
      break;
    }
  }

  *out = NULL;
}

void cil_complex_symtab_destroy(struct cil_complex_symtab *symtab)
{
  struct cil_complex_symtab_node *curr = NULL;
  struct cil_complex_symtab_node *temp = NULL;
  unsigned int i;

  if (symtab == NULL) {
    return;
  }

  for (i = 0; i < symtab->nslots; i++) {
    curr = symtab->htable[i];
    while (curr != NULL) {
      temp = curr;
      curr = curr->next;
      free(temp);
    }
    symtab->htable[i] = NULL;
  }
  free(symtab->htable);
  symtab->htable = NULL;
  symtab->nelems = 0;
  symtab->nslots = 0;
  symtab->mask = 0;
}

Coverage Report

Created: 2026-09-03 06:28

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 <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
45		__attribute__((noreturn)) __attribute__((format(printf, 1, 2))) static void
46		cil_symtab_error(const char *msg, ...)
47	0	{
48	0	va_list ap;
49	0	va_start(ap, msg);
50	0	cil_vlog(CIL_ERR, msg, ap);
51	0	va_end(ap);
52	0	exit(1);
53	0	}
54
55		void cil_symtab_init(symtab_t *symtab, unsigned int size)
56	0	{
57	0	int rc = symtab_init(symtab, size);
58	0	if (rc != SEPOL_OK) {
59	0	cil_symtab_error("Failed to create symtab\n");
60	0	}
61	0	}
62
63		void cil_symtab_datum_init(struct cil_symtab_datum *datum)
64	0	{
65	0	datum->name = NULL;
66	0	datum->fqn = NULL;
67	0	datum->symtab = NULL;
68	0	cil_list_init(&datum->nodes, CIL_LIST_ITEM);
69	0	}
70
71		void cil_symtab_datum_destroy(struct cil_symtab_datum *datum)
72	0	{
73	0	cil_list_destroy(&datum->nodes, 0);
74	0	cil_symtab_remove_datum(datum);
75	0	}
76
77		void cil_symtab_datum_remove_node(struct cil_symtab_datum *datum,
78		struct cil_tree_node *node)
79	0	{
80	0	if (datum && datum->nodes != NULL) {
81	0	cil_list_remove(datum->nodes, CIL_NODE, node, 0);
82	0	if (datum->nodes->head == NULL) {
83	0	cil_symtab_datum_destroy(datum);
84	0	}
85	0	}
86	0	}
87
88		/* This both initializes the datum and inserts it into the symtab.
89		Note that cil_symtab_datum_destroy() is the analog to the initializer portion */
90		int cil_symtab_insert(symtab_t *symtab, hashtab_key_t key,
91		struct cil_symtab_datum *datum,
92		struct cil_tree_node *node)
93	0	{
94	0	int rc = hashtab_insert(symtab->table, key, (hashtab_datum_t)datum);
95	0	if (rc == SEPOL_OK) {
96	0	datum->name = key;
97	0	datum->fqn = key;
98	0	datum->symtab = symtab;
99	0	symtab->nprim++;
100	0	if (node) {
101	0	cil_list_append(datum->nodes, CIL_NODE, node);
102	0	}
103	0	} else if (rc != SEPOL_EEXIST) {
104	0	cil_symtab_error("Failed to insert datum into hashtab\n");
105	0	}
106
107	0	return rc;
108	0	}
109
110		void cil_symtab_remove_datum(struct cil_symtab_datum *datum)
111	0	{
112	0	symtab_t *symtab = datum->symtab;
113
114	0	if (symtab == NULL) {
115	0	return;
116	0	}
117
118	0	hashtab_remove(symtab->table, datum->name, NULL, NULL);
119	0	symtab->nprim--;
120	0	datum->symtab = NULL;
121	0	}
122
123		int cil_symtab_get_datum(symtab_t symtab, char key,
124		struct cil_symtab_datum **datum)
125	0	{
126	0	datum = (struct cil_symtab_datum )hashtab_search(symtab->table,
127	0	(hashtab_key_t)key);
128	0	if (*datum == NULL) {
129	0	return SEPOL_ENOENT;
130	0	}
131
132	0	return SEPOL_OK;
133	0	}
134
135		int cil_symtab_map(symtab_t *symtab,
136		int (apply)(hashtab_key_t k, hashtab_datum_t d, void args),
137		void *args)
138	0	{
139	0	return hashtab_map(symtab->table, apply, args);
140	0	}
141
142		static int __cil_symtab_destroy_helper(__attribute__((unused)) hashtab_key_t k,
143		hashtab_datum_t d,
144		__attribute__((unused)) void *args)
145	0	{
146	0	struct cil_symtab_datum *datum = d;
147	0	datum->symtab = NULL;
148	0	return SEPOL_OK;
149	0	}
150
151		void cil_symtab_destroy(symtab_t *symtab)
152	0	{
153	0	if (symtab->table != NULL) {
154	0	cil_symtab_map(symtab, __cil_symtab_destroy_helper, NULL);
155	0	hashtab_destroy(symtab->table);
156	0	symtab->table = NULL;
157	0	}
158	0	}
159
160		static void cil_complex_symtab_hash(struct cil_complex_symtab_key *ckey,
161		int mask, intptr_t *hash)
162	0	{
163	0	intptr_t sum = ckey->key1 + ckey->key2 + ckey->key3 + ckey->key4;
164	0	*hash = (intptr_t)((sum >> 2) & mask);
165	0	}
166
167		void cil_complex_symtab_init(struct cil_complex_symtab *symtab,
168		unsigned int size)
169	0	{
170	0	symtab->htable = cil_calloc(size, sizeof(struct cil_complex_symtab *));
171
172	0	symtab->nelems = 0;
173	0	symtab->nslots = size;
174	0	symtab->mask = size - 1;
175	0	}
176
177		int cil_complex_symtab_insert(struct cil_complex_symtab *symtab,
178		struct cil_complex_symtab_key *ckey,
179		struct cil_complex_symtab_datum *datum)
180	0	{
181	0	intptr_t hash;
182	0	struct cil_complex_symtab_node *node = NULL;
183	0	struct cil_complex_symtab_node *prev = NULL;
184	0	struct cil_complex_symtab_node *curr = NULL;
185
186	0	node = cil_malloc(sizeof(*node));
187	0	memset(node, 0, sizeof(*node));
188
189	0	node->ckey = ckey;
190	0	node->datum = datum;
191
192	0	cil_complex_symtab_hash(ckey, symtab->mask, &hash);
193
194	0	for (prev = NULL, curr = symtab->htable[hash]; curr != NULL;
195	0	prev = curr, curr = curr->next) {
196	0	if (ckey->key1 == curr->ckey->key1 &&
197	0	ckey->key2 == curr->ckey->key2 &&
198	0	ckey->key3 == curr->ckey->key3 &&
199	0	ckey->key4 == curr->ckey->key4) {
200	0	free(node);
201	0	return SEPOL_EEXIST;
202	0	}
203
204	0	if (ckey->key1 == curr->ckey->key1 &&
205	0	ckey->key2 < curr->ckey->key2) {
206	0	break;
207	0	}
208
209	0	if (ckey->key1 == curr->ckey->key1 &&
210	0	ckey->key2 == curr->ckey->key2 &&
211	0	ckey->key3 < curr->ckey->key3) {
212	0	break;
213	0	}
214
215	0	if (ckey->key1 == curr->ckey->key1 &&
216	0	ckey->key2 == curr->ckey->key2 &&
217	0	ckey->key3 == curr->ckey->key3 &&
218	0	ckey->key4 < curr->ckey->key4) {
219	0	break;
220	0	}
221	0	}
222
223	0	if (prev != NULL) {
224	0	node->next = prev->next;
225	0	prev->next = node;
226	0	} else {
227	0	node->next = symtab->htable[hash];
228	0	symtab->htable[hash] = node;
229	0	}
230
231	0	symtab->nelems++;
232
233	0	return SEPOL_OK;
234	0	}
235
236		void cil_complex_symtab_search(struct cil_complex_symtab *symtab,
237		struct cil_complex_symtab_key *ckey,
238		struct cil_complex_symtab_datum **out)
239	0	{
240	0	intptr_t hash;
241	0	struct cil_complex_symtab_node *curr = NULL;
242
243	0	cil_complex_symtab_hash(ckey, symtab->mask, &hash);
244	0	for (curr = symtab->htable[hash]; curr != NULL; curr = curr->next) {
245	0	if (ckey->key1 == curr->ckey->key1 &&
246	0	ckey->key2 == curr->ckey->key2 &&
247	0	ckey->key3 == curr->ckey->key3 &&
248	0	ckey->key4 == curr->ckey->key4) {
249	0	*out = curr->datum;
250	0	return;
251	0	}
252
253	0	if (ckey->key1 == curr->ckey->key1 &&
254	0	ckey->key2 < curr->ckey->key2) {
255	0	break;
256	0	}
257
258	0	if (ckey->key1 == curr->ckey->key1 &&
259	0	ckey->key2 == curr->ckey->key2 &&
260	0	ckey->key3 < curr->ckey->key3) {
261	0	break;
262	0	}
263
264	0	if (ckey->key1 == curr->ckey->key1 &&
265	0	ckey->key2 == curr->ckey->key2 &&
266	0	ckey->key3 == curr->ckey->key3 &&
267	0	ckey->key4 < curr->ckey->key4) {
268	0	break;
269	0	}
270	0	}
271
272	0	*out = NULL;
273	0	}
274
275		void cil_complex_symtab_destroy(struct cil_complex_symtab *symtab)
276	0	{
277	0	struct cil_complex_symtab_node *curr = NULL;
278	0	struct cil_complex_symtab_node *temp = NULL;
279	0	unsigned int i;
280
281	0	if (symtab == NULL) {
282	0	return;
283	0	}
284
285	0	for (i = 0; i < symtab->nslots; i++) {
286	0	curr = symtab->htable[i];
287	0	while (curr != NULL) {
288	0	temp = curr;
289	0	curr = curr->next;
290	0	free(temp);
291	0	}
292	0	symtab->htable[i] = NULL;
293	0	}
294	0	free(symtab->htable);
295		symtab->htable = NULL;
296	0	symtab->nelems = 0;
297	0	symtab->nslots = 0;
298	0	symtab->mask = 0;
299	0	}