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