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