xref: /third_party/selinux/libsepol/src/sidtab.c (revision 6cd6a6ac) 
1
2/* Author : Stephen Smalley, <sds@tycho.nsa.gov> */
3
4/* FLASK */
5
6/*
7 * Implementation of the SID table type.
8 */
9
10#include <stdlib.h>
11#include <errno.h>
12#include <limits.h>
13#include <stdio.h>
14
15#include <sepol/policydb/sidtab.h>
16
17#include "flask.h"
18#include "private.h"
19
20#define SIDTAB_HASH(sid) \
21(sid & SIDTAB_HASH_MASK)
22
23#define INIT_SIDTAB_LOCK(s)
24#define SIDTAB_LOCK(s)
25#define SIDTAB_UNLOCK(s)
26
27int sepol_sidtab_init(sidtab_t * s)
28{
29	s->htable = calloc(SIDTAB_SIZE, sizeof(sidtab_ptr_t));
30	if (!s->htable)
31		return -ENOMEM;
32	s->nel = 0;
33	s->next_sid = 1;
34	s->shutdown = 0;
35	INIT_SIDTAB_LOCK(s);
36	return 0;
37}
38
39int sepol_sidtab_insert(sidtab_t * s, sepol_security_id_t sid,
40			context_struct_t * context)
41{
42	int hvalue;
43	sidtab_node_t *prev, *cur, *newnode;
44
45	if (!s || !s->htable)
46		return -ENOMEM;
47
48	hvalue = SIDTAB_HASH(sid);
49	prev = NULL;
50	cur = s->htable[hvalue];
51	while (cur != NULL && sid > cur->sid) {
52		prev = cur;
53		cur = cur->next;
54	}
55
56	if (cur && sid == cur->sid) {
57		errno = EEXIST;
58		return -EEXIST;
59	}
60
61	newnode = (sidtab_node_t *) malloc(sizeof(sidtab_node_t));
62	if (newnode == NULL)
63		return -ENOMEM;
64	newnode->sid = sid;
65	if (context_cpy(&newnode->context, context)) {
66		free(newnode);
67		return -ENOMEM;
68	}
69
70	if (prev) {
71		newnode->next = prev->next;
72		prev->next = newnode;
73	} else {
74		newnode->next = s->htable[hvalue];
75		s->htable[hvalue] = newnode;
76	}
77
78	s->nel++;
79	if (sid >= s->next_sid)
80		s->next_sid = sid + 1;
81	return 0;
82}
83
84context_struct_t *sepol_sidtab_search(sidtab_t * s, sepol_security_id_t sid)
85{
86	int hvalue;
87	sidtab_node_t *cur;
88
89	if (!s || !s->htable)
90		return NULL;
91
92	hvalue = SIDTAB_HASH(sid);
93	cur = s->htable[hvalue];
94	while (cur != NULL && sid > cur->sid)
95		cur = cur->next;
96
97	if (cur == NULL || sid != cur->sid) {
98		/* Remap invalid SIDs to the unlabeled SID. */
99		sid = SECINITSID_UNLABELED;
100		hvalue = SIDTAB_HASH(sid);
101		cur = s->htable[hvalue];
102		while (cur != NULL && sid > cur->sid)
103			cur = cur->next;
104		if (!cur || sid != cur->sid)
105			return NULL;
106	}
107
108	return &cur->context;
109}
110
111int sepol_sidtab_map(sidtab_t * s,
112		     int (*apply) (sepol_security_id_t sid,
113				   context_struct_t * context,
114				   void *args), void *args)
115{
116	int i, ret;
117	sidtab_node_t *cur;
118
119	if (!s || !s->htable)
120		return 0;
121
122	for (i = 0; i < SIDTAB_SIZE; i++) {
123		cur = s->htable[i];
124		while (cur != NULL) {
125			ret = apply(cur->sid, &cur->context, args);
126			if (ret)
127				return ret;
128			cur = cur->next;
129		}
130	}
131	return 0;
132}
133
134void sepol_sidtab_map_remove_on_error(sidtab_t * s,
135				      int (*apply) (sepol_security_id_t sid,
136						    context_struct_t * context,
137						    void *args), void *args)
138{
139	int i, ret;
140	sidtab_node_t *last, *cur, *temp;
141
142	if (!s || !s->htable)
143		return;
144
145	for (i = 0; i < SIDTAB_SIZE; i++) {
146		last = NULL;
147		cur = s->htable[i];
148		while (cur != NULL) {
149			ret = apply(cur->sid, &cur->context, args);
150			if (ret) {
151				if (last) {
152					last->next = cur->next;
153				} else {
154					s->htable[i] = cur->next;
155				}
156
157				temp = cur;
158				cur = cur->next;
159				context_destroy(&temp->context);
160				free(temp);
161				s->nel--;
162			} else {
163				last = cur;
164				cur = cur->next;
165			}
166		}
167	}
168
169	return;
170}
171
172static inline sepol_security_id_t sepol_sidtab_search_context(sidtab_t * s,
173							      context_struct_t *
174							      context)
175{
176	int i;
177	sidtab_node_t *cur;
178
179	for (i = 0; i < SIDTAB_SIZE; i++) {
180		cur = s->htable[i];
181		while (cur != NULL) {
182			if (context_cmp(&cur->context, context))
183				return cur->sid;
184			cur = cur->next;
185		}
186	}
187	return 0;
188}
189
190int sepol_sidtab_context_to_sid(sidtab_t * s,
191				context_struct_t * context,
192				sepol_security_id_t * out_sid)
193{
194	sepol_security_id_t sid;
195	int ret = 0;
196
197	*out_sid = SEPOL_SECSID_NULL;
198
199	sid = sepol_sidtab_search_context(s, context);
200	if (!sid) {
201		SIDTAB_LOCK(s);
202		/* Rescan now that we hold the lock. */
203		sid = sepol_sidtab_search_context(s, context);
204		if (sid)
205			goto unlock_out;
206		/* No SID exists for the context.  Allocate a new one. */
207		if (s->next_sid == UINT_MAX || s->shutdown) {
208			ret = -ENOMEM;
209			goto unlock_out;
210		}
211		sid = s->next_sid++;
212		ret = sepol_sidtab_insert(s, sid, context);
213		if (ret)
214			s->next_sid--;
215	      unlock_out:
216		SIDTAB_UNLOCK(s);
217	}
218
219	if (ret)
220		return ret;
221
222	*out_sid = sid;
223	return 0;
224}
225
226void sepol_sidtab_hash_eval(sidtab_t * h, char *tag)
227{
228	int i, chain_len, slots_used, max_chain_len;
229	sidtab_node_t *cur;
230
231	slots_used = 0;
232	max_chain_len = 0;
233	for (i = 0; i < SIDTAB_SIZE; i++) {
234		cur = h->htable[i];
235		if (cur) {
236			slots_used++;
237			chain_len = 0;
238			while (cur) {
239				chain_len++;
240				cur = cur->next;
241			}
242
243			if (chain_len > max_chain_len)
244				max_chain_len = chain_len;
245		}
246	}
247
248	printf
249	    ("%s:  %d entries and %d/%d buckets used, longest chain length %d\n",
250	     tag, h->nel, slots_used, SIDTAB_SIZE, max_chain_len);
251}
252
253void sepol_sidtab_destroy(sidtab_t * s)
254{
255	int i;
256	sidtab_ptr_t cur, temp;
257
258	if (!s || !s->htable)
259		return;
260
261	for (i = 0; i < SIDTAB_SIZE; i++) {
262		cur = s->htable[i];
263		while (cur != NULL) {
264			temp = cur;
265			cur = cur->next;
266			context_destroy(&temp->context);
267			free(temp);
268		}
269		s->htable[i] = NULL;
270	}
271	free(s->htable);
272	s->htable = NULL;
273	s->nel = 0;
274	s->next_sid = 1;
275}
276
277void sepol_sidtab_set(sidtab_t * dst, sidtab_t * src)
278{
279	SIDTAB_LOCK(src);
280	dst->htable = src->htable;
281	dst->nel = src->nel;
282	dst->next_sid = src->next_sid;
283	dst->shutdown = 0;
284	SIDTAB_UNLOCK(src);
285}
286
287void sepol_sidtab_shutdown(sidtab_t * s)
288{
289	SIDTAB_LOCK(s);
290	s->shutdown = 1;
291	SIDTAB_UNLOCK(s);
292}
293
294/* FLASK */
295