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