sidtab.c revision dbc74c65b3fd841985935f676388c82d6b85c485 
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 inline u32 sidtab_search_context(struct sidtab *s,
151						  struct context *context)
152{
153	int i;
154	struct sidtab_node *cur;
155
156	for (i = 0; i < SIDTAB_SIZE; i++) {
157		cur = s->htable[i];
158		while (cur) {
159			if (context_cmp(&cur->context, context))
160				return cur->sid;
161			cur = cur->next;
162		}
163	}
164	return 0;
165}
166
167int sidtab_context_to_sid(struct sidtab *s,
168			  struct context *context,
169			  u32 *out_sid)
170{
171	u32 sid;
172	int ret = 0;
173	unsigned long flags;
174
175	*out_sid = SECSID_NULL;
176
177	sid = sidtab_search_context(s, context);
178	if (!sid) {
179		spin_lock_irqsave(&s->lock, flags);
180		/* Rescan now that we hold the lock. */
181		sid = sidtab_search_context(s, context);
182		if (sid)
183			goto unlock_out;
184		/* No SID exists for the context.  Allocate a new one. */
185		if (s->next_sid == UINT_MAX || s->shutdown) {
186			ret = -ENOMEM;
187			goto unlock_out;
188		}
189		sid = s->next_sid++;
190		if (context->len)
191			printk(KERN_INFO
192		       "SELinux:  Context %s is not valid (left unmapped).\n",
193			       context->str);
194		ret = sidtab_insert(s, sid, context);
195		if (ret)
196			s->next_sid--;
197unlock_out:
198		spin_unlock_irqrestore(&s->lock, flags);
199	}
200
201	if (ret)
202		return ret;
203
204	*out_sid = sid;
205	return 0;
206}
207
208void sidtab_hash_eval(struct sidtab *h, char *tag)
209{
210	int i, chain_len, slots_used, max_chain_len;
211	struct sidtab_node *cur;
212
213	slots_used = 0;
214	max_chain_len = 0;
215	for (i = 0; i < SIDTAB_SIZE; i++) {
216		cur = h->htable[i];
217		if (cur) {
218			slots_used++;
219			chain_len = 0;
220			while (cur) {
221				chain_len++;
222				cur = cur->next;
223			}
224
225			if (chain_len > max_chain_len)
226				max_chain_len = chain_len;
227		}
228	}
229
230	printk(KERN_DEBUG "%s:  %d entries and %d/%d buckets used, longest "
231	       "chain length %d\n", tag, h->nel, slots_used, SIDTAB_SIZE,
232	       max_chain_len);
233}
234
235void sidtab_destroy(struct sidtab *s)
236{
237	int i;
238	struct sidtab_node *cur, *temp;
239
240	if (!s)
241		return;
242
243	for (i = 0; i < SIDTAB_SIZE; i++) {
244		cur = s->htable[i];
245		while (cur) {
246			temp = cur;
247			cur = cur->next;
248			context_destroy(&temp->context);
249			kfree(temp);
250		}
251		s->htable[i] = NULL;
252	}
253	kfree(s->htable);
254	s->htable = NULL;
255	s->nel = 0;
256	s->next_sid = 1;
257}
258
259void sidtab_set(struct sidtab *dst, struct sidtab *src)
260{
261	unsigned long flags;
262
263	spin_lock_irqsave(&src->lock, flags);
264	dst->htable = src->htable;
265	dst->nel = src->nel;
266	dst->next_sid = src->next_sid;
267	dst->shutdown = 0;
268	spin_unlock_irqrestore(&src->lock, flags);
269}
270
271void sidtab_shutdown(struct sidtab *s)
272{
273	unsigned long flags;
274
275	spin_lock_irqsave(&s->lock, flags);
276	s->shutdown = 1;
277	spin_unlock_irqrestore(&s->lock, flags);
278}
279