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