1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#include <linux/kernel.h>
21#include <linux/slab.h>
22#include <linux/errno.h>
23#include "avtab.h"
24#include "policydb.h"
25
26static struct kmem_cache *avtab_node_cachep;
27static struct kmem_cache *avtab_xperms_cachep;
28
29static inline int avtab_hash(struct avtab_key *keyp, u16 mask)
30{
31 return ((keyp->target_class + (keyp->target_type << 2) +
32 (keyp->source_type << 9)) & mask);
33}
34
35static struct avtab_node*
36avtab_insert_node(struct avtab *h, int hvalue,
37 struct avtab_node *prev, struct avtab_node *cur,
38 struct avtab_key *key, struct avtab_datum *datum)
39{
40 struct avtab_node *newnode;
41 struct avtab_extended_perms *xperms;
42 newnode = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL);
43 if (newnode == NULL)
44 return NULL;
45 newnode->key = *key;
46
47 if (key->specified & AVTAB_XPERMS) {
48 xperms = kmem_cache_zalloc(avtab_xperms_cachep, GFP_KERNEL);
49 if (xperms == NULL) {
50 kmem_cache_free(avtab_node_cachep, newnode);
51 return NULL;
52 }
53 *xperms = *(datum->u.xperms);
54 newnode->datum.u.xperms = xperms;
55 } else {
56 newnode->datum.u.data = datum->u.data;
57 }
58
59 if (prev) {
60 newnode->next = prev->next;
61 prev->next = newnode;
62 } else {
63 newnode->next = h->htable[hvalue];
64 h->htable[hvalue] = newnode;
65 }
66
67 h->nel++;
68 return newnode;
69}
70
71static int avtab_insert(struct avtab *h, struct avtab_key *key, struct avtab_datum *datum)
72{
73 int hvalue;
74 struct avtab_node *prev, *cur, *newnode;
75 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
76
77 if (!h || !h->htable)
78 return -EINVAL;
79
80 hvalue = avtab_hash(key, h->mask);
81 for (prev = NULL, cur = h->htable[hvalue];
82 cur;
83 prev = cur, cur = cur->next) {
84 if (key->source_type == cur->key.source_type &&
85 key->target_type == cur->key.target_type &&
86 key->target_class == cur->key.target_class &&
87 (specified & cur->key.specified)) {
88
89 if (specified & AVTAB_XPERMS)
90 break;
91 return -EEXIST;
92 }
93 if (key->source_type < cur->key.source_type)
94 break;
95 if (key->source_type == cur->key.source_type &&
96 key->target_type < cur->key.target_type)
97 break;
98 if (key->source_type == cur->key.source_type &&
99 key->target_type == cur->key.target_type &&
100 key->target_class < cur->key.target_class)
101 break;
102 }
103
104 newnode = avtab_insert_node(h, hvalue, prev, cur, key, datum);
105 if (!newnode)
106 return -ENOMEM;
107
108 return 0;
109}
110
111
112
113
114
115struct avtab_node *
116avtab_insert_nonunique(struct avtab *h, struct avtab_key *key, struct avtab_datum *datum)
117{
118 int hvalue;
119 struct avtab_node *prev, *cur;
120 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
121
122 if (!h || !h->htable)
123 return NULL;
124 hvalue = avtab_hash(key, h->mask);
125 for (prev = NULL, cur = h->htable[hvalue];
126 cur;
127 prev = cur, cur = cur->next) {
128 if (key->source_type == cur->key.source_type &&
129 key->target_type == cur->key.target_type &&
130 key->target_class == cur->key.target_class &&
131 (specified & cur->key.specified))
132 break;
133 if (key->source_type < cur->key.source_type)
134 break;
135 if (key->source_type == cur->key.source_type &&
136 key->target_type < cur->key.target_type)
137 break;
138 if (key->source_type == cur->key.source_type &&
139 key->target_type == cur->key.target_type &&
140 key->target_class < cur->key.target_class)
141 break;
142 }
143 return avtab_insert_node(h, hvalue, prev, cur, key, datum);
144}
145
146struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key)
147{
148 int hvalue;
149 struct avtab_node *cur;
150 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
151
152 if (!h || !h->htable)
153 return NULL;
154
155 hvalue = avtab_hash(key, h->mask);
156 for (cur = h->htable[hvalue]; cur; cur = cur->next) {
157 if (key->source_type == cur->key.source_type &&
158 key->target_type == cur->key.target_type &&
159 key->target_class == cur->key.target_class &&
160 (specified & cur->key.specified))
161 return &cur->datum;
162
163 if (key->source_type < cur->key.source_type)
164 break;
165 if (key->source_type == cur->key.source_type &&
166 key->target_type < cur->key.target_type)
167 break;
168 if (key->source_type == cur->key.source_type &&
169 key->target_type == cur->key.target_type &&
170 key->target_class < cur->key.target_class)
171 break;
172 }
173
174 return NULL;
175}
176
177
178
179
180struct avtab_node*
181avtab_search_node(struct avtab *h, struct avtab_key *key)
182{
183 int hvalue;
184 struct avtab_node *cur;
185 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
186
187 if (!h || !h->htable)
188 return NULL;
189
190 hvalue = avtab_hash(key, h->mask);
191 for (cur = h->htable[hvalue]; cur; cur = cur->next) {
192 if (key->source_type == cur->key.source_type &&
193 key->target_type == cur->key.target_type &&
194 key->target_class == cur->key.target_class &&
195 (specified & cur->key.specified))
196 return cur;
197
198 if (key->source_type < cur->key.source_type)
199 break;
200 if (key->source_type == cur->key.source_type &&
201 key->target_type < cur->key.target_type)
202 break;
203 if (key->source_type == cur->key.source_type &&
204 key->target_type == cur->key.target_type &&
205 key->target_class < cur->key.target_class)
206 break;
207 }
208 return NULL;
209}
210
211struct avtab_node*
212avtab_search_node_next(struct avtab_node *node, int specified)
213{
214 struct avtab_node *cur;
215
216 if (!node)
217 return NULL;
218
219 specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
220 for (cur = node->next; cur; cur = cur->next) {
221 if (node->key.source_type == cur->key.source_type &&
222 node->key.target_type == cur->key.target_type &&
223 node->key.target_class == cur->key.target_class &&
224 (specified & cur->key.specified))
225 return cur;
226
227 if (node->key.source_type < cur->key.source_type)
228 break;
229 if (node->key.source_type == cur->key.source_type &&
230 node->key.target_type < cur->key.target_type)
231 break;
232 if (node->key.source_type == cur->key.source_type &&
233 node->key.target_type == cur->key.target_type &&
234 node->key.target_class < cur->key.target_class)
235 break;
236 }
237 return NULL;
238}
239
240void avtab_destroy(struct avtab *h)
241{
242 int i;
243 struct avtab_node *cur, *temp;
244
245 if (!h || !h->htable)
246 return;
247
248 for (i = 0; i < h->nslot; i++) {
249 cur = h->htable[i];
250 while (cur) {
251 temp = cur;
252 cur = cur->next;
253 if (temp->key.specified & AVTAB_XPERMS)
254 kmem_cache_free(avtab_xperms_cachep,
255 temp->datum.u.xperms);
256 kmem_cache_free(avtab_node_cachep, temp);
257 }
258 h->htable[i] = NULL;
259 }
260 kfree(h->htable);
261 h->htable = NULL;
262 h->nslot = 0;
263 h->mask = 0;
264}
265
266int avtab_init(struct avtab *h)
267{
268 h->htable = NULL;
269 h->nel = 0;
270 return 0;
271}
272
273int avtab_alloc(struct avtab *h, u32 nrules)
274{
275 u16 mask = 0;
276 u32 shift = 0;
277 u32 work = nrules;
278 u32 nslot = 0;
279
280 if (nrules == 0)
281 goto avtab_alloc_out;
282
283 while (work) {
284 work = work >> 1;
285 shift++;
286 }
287 if (shift > 2)
288 shift = shift - 2;
289 nslot = 1 << shift;
290 if (nslot > MAX_AVTAB_HASH_BUCKETS)
291 nslot = MAX_AVTAB_HASH_BUCKETS;
292 mask = nslot - 1;
293
294 h->htable = kcalloc(nslot, sizeof(*(h->htable)), GFP_KERNEL);
295 if (!h->htable)
296 return -ENOMEM;
297
298 avtab_alloc_out:
299 h->nel = 0;
300 h->nslot = nslot;
301 h->mask = mask;
302 printk(KERN_DEBUG "SELinux: %d avtab hash slots, %d rules.\n",
303 h->nslot, nrules);
304 return 0;
305}
306
307void avtab_hash_eval(struct avtab *h, char *tag)
308{
309 int i, chain_len, slots_used, max_chain_len;
310 unsigned long long chain2_len_sum;
311 struct avtab_node *cur;
312
313 slots_used = 0;
314 max_chain_len = 0;
315 chain2_len_sum = 0;
316 for (i = 0; i < h->nslot; i++) {
317 cur = h->htable[i];
318 if (cur) {
319 slots_used++;
320 chain_len = 0;
321 while (cur) {
322 chain_len++;
323 cur = cur->next;
324 }
325
326 if (chain_len > max_chain_len)
327 max_chain_len = chain_len;
328 chain2_len_sum += chain_len * chain_len;
329 }
330 }
331
332 printk(KERN_DEBUG "SELinux: %s: %d entries and %d/%d buckets used, "
333 "longest chain length %d sum of chain length^2 %llu\n",
334 tag, h->nel, slots_used, h->nslot, max_chain_len,
335 chain2_len_sum);
336}
337
338static uint16_t spec_order[] = {
339 AVTAB_ALLOWED,
340 AVTAB_AUDITDENY,
341 AVTAB_AUDITALLOW,
342 AVTAB_TRANSITION,
343 AVTAB_CHANGE,
344 AVTAB_MEMBER,
345 AVTAB_XPERMS_ALLOWED,
346 AVTAB_XPERMS_AUDITALLOW,
347 AVTAB_XPERMS_DONTAUDIT
348};
349
350int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
351 int (*insertf)(struct avtab *a, struct avtab_key *k,
352 struct avtab_datum *d, void *p),
353 void *p)
354{
355 __le16 buf16[4];
356 u16 enabled;
357 u32 items, items2, val, vers = pol->policyvers;
358 struct avtab_key key;
359 struct avtab_datum datum;
360 struct avtab_extended_perms xperms;
361 __le32 buf32[ARRAY_SIZE(xperms.perms.p)];
362 int i, rc;
363 unsigned set;
364
365 memset(&key, 0, sizeof(struct avtab_key));
366 memset(&datum, 0, sizeof(struct avtab_datum));
367
368 if (vers < POLICYDB_VERSION_AVTAB) {
369 rc = next_entry(buf32, fp, sizeof(u32));
370 if (rc) {
371 printk(KERN_ERR "SELinux: avtab: truncated entry\n");
372 return rc;
373 }
374 items2 = le32_to_cpu(buf32[0]);
375 if (items2 > ARRAY_SIZE(buf32)) {
376 printk(KERN_ERR "SELinux: avtab: entry overflow\n");
377 return -EINVAL;
378
379 }
380 rc = next_entry(buf32, fp, sizeof(u32)*items2);
381 if (rc) {
382 printk(KERN_ERR "SELinux: avtab: truncated entry\n");
383 return rc;
384 }
385 items = 0;
386
387 val = le32_to_cpu(buf32[items++]);
388 key.source_type = (u16)val;
389 if (key.source_type != val) {
390 printk(KERN_ERR "SELinux: avtab: truncated source type\n");
391 return -EINVAL;
392 }
393 val = le32_to_cpu(buf32[items++]);
394 key.target_type = (u16)val;
395 if (key.target_type != val) {
396 printk(KERN_ERR "SELinux: avtab: truncated target type\n");
397 return -EINVAL;
398 }
399 val = le32_to_cpu(buf32[items++]);
400 key.target_class = (u16)val;
401 if (key.target_class != val) {
402 printk(KERN_ERR "SELinux: avtab: truncated target class\n");
403 return -EINVAL;
404 }
405
406 val = le32_to_cpu(buf32[items++]);
407 enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0;
408
409 if (!(val & (AVTAB_AV | AVTAB_TYPE))) {
410 printk(KERN_ERR "SELinux: avtab: null entry\n");
411 return -EINVAL;
412 }
413 if ((val & AVTAB_AV) &&
414 (val & AVTAB_TYPE)) {
415 printk(KERN_ERR "SELinux: avtab: entry has both access vectors and types\n");
416 return -EINVAL;
417 }
418 if (val & AVTAB_XPERMS) {
419 printk(KERN_ERR "SELinux: avtab: entry has extended permissions\n");
420 return -EINVAL;
421 }
422
423 for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
424 if (val & spec_order[i]) {
425 key.specified = spec_order[i] | enabled;
426 datum.u.data = le32_to_cpu(buf32[items++]);
427 rc = insertf(a, &key, &datum, p);
428 if (rc)
429 return rc;
430 }
431 }
432
433 if (items != items2) {
434 printk(KERN_ERR "SELinux: avtab: entry only had %d items, expected %d\n", items2, items);
435 return -EINVAL;
436 }
437 return 0;
438 }
439
440 rc = next_entry(buf16, fp, sizeof(u16)*4);
441 if (rc) {
442 printk(KERN_ERR "SELinux: avtab: truncated entry\n");
443 return rc;
444 }
445
446 items = 0;
447 key.source_type = le16_to_cpu(buf16[items++]);
448 key.target_type = le16_to_cpu(buf16[items++]);
449 key.target_class = le16_to_cpu(buf16[items++]);
450 key.specified = le16_to_cpu(buf16[items++]);
451
452 if (!policydb_type_isvalid(pol, key.source_type) ||
453 !policydb_type_isvalid(pol, key.target_type) ||
454 !policydb_class_isvalid(pol, key.target_class)) {
455 printk(KERN_ERR "SELinux: avtab: invalid type or class\n");
456 return -EINVAL;
457 }
458
459 set = 0;
460 for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
461 if (key.specified & spec_order[i])
462 set++;
463 }
464 if (!set || set > 1) {
465 printk(KERN_ERR "SELinux: avtab: more than one specifier\n");
466 return -EINVAL;
467 }
468
469 if ((vers < POLICYDB_VERSION_XPERMS_IOCTL) &&
470 (key.specified & AVTAB_XPERMS)) {
471 printk(KERN_ERR "SELinux: avtab: policy version %u does not "
472 "support extended permissions rules and one "
473 "was specified\n", vers);
474 return -EINVAL;
475 } else if (key.specified & AVTAB_XPERMS) {
476 memset(&xperms, 0, sizeof(struct avtab_extended_perms));
477 rc = next_entry(&xperms.specified, fp, sizeof(u8));
478 if (rc) {
479 printk(KERN_ERR "SELinux: avtab: truncated entry\n");
480 return rc;
481 }
482 rc = next_entry(&xperms.driver, fp, sizeof(u8));
483 if (rc) {
484 printk(KERN_ERR "SELinux: avtab: truncated entry\n");
485 return rc;
486 }
487 rc = next_entry(buf32, fp, sizeof(u32)*ARRAY_SIZE(xperms.perms.p));
488 if (rc) {
489 printk(KERN_ERR "SELinux: avtab: truncated entry\n");
490 return rc;
491 }
492 for (i = 0; i < ARRAY_SIZE(xperms.perms.p); i++)
493 xperms.perms.p[i] = le32_to_cpu(buf32[i]);
494 datum.u.xperms = &xperms;
495 } else {
496 rc = next_entry(buf32, fp, sizeof(u32));
497 if (rc) {
498 printk(KERN_ERR "SELinux: avtab: truncated entry\n");
499 return rc;
500 }
501 datum.u.data = le32_to_cpu(*buf32);
502 }
503 if ((key.specified & AVTAB_TYPE) &&
504 !policydb_type_isvalid(pol, datum.u.data)) {
505 printk(KERN_ERR "SELinux: avtab: invalid type\n");
506 return -EINVAL;
507 }
508 return insertf(a, &key, &datum, p);
509}
510
511static int avtab_insertf(struct avtab *a, struct avtab_key *k,
512 struct avtab_datum *d, void *p)
513{
514 return avtab_insert(a, k, d);
515}
516
517int avtab_read(struct avtab *a, void *fp, struct policydb *pol)
518{
519 int rc;
520 __le32 buf[1];
521 u32 nel, i;
522
523
524 rc = next_entry(buf, fp, sizeof(u32));
525 if (rc < 0) {
526 printk(KERN_ERR "SELinux: avtab: truncated table\n");
527 goto bad;
528 }
529 nel = le32_to_cpu(buf[0]);
530 if (!nel) {
531 printk(KERN_ERR "SELinux: avtab: table is empty\n");
532 rc = -EINVAL;
533 goto bad;
534 }
535
536 rc = avtab_alloc(a, nel);
537 if (rc)
538 goto bad;
539
540 for (i = 0; i < nel; i++) {
541 rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL);
542 if (rc) {
543 if (rc == -ENOMEM)
544 printk(KERN_ERR "SELinux: avtab: out of memory\n");
545 else if (rc == -EEXIST)
546 printk(KERN_ERR "SELinux: avtab: duplicate entry\n");
547
548 goto bad;
549 }
550 }
551
552 rc = 0;
553out:
554 return rc;
555
556bad:
557 avtab_destroy(a);
558 goto out;
559}
560
561int avtab_write_item(struct policydb *p, struct avtab_node *cur, void *fp)
562{
563 __le16 buf16[4];
564 __le32 buf32[ARRAY_SIZE(cur->datum.u.xperms->perms.p)];
565 int rc;
566 unsigned int i;
567
568 buf16[0] = cpu_to_le16(cur->key.source_type);
569 buf16[1] = cpu_to_le16(cur->key.target_type);
570 buf16[2] = cpu_to_le16(cur->key.target_class);
571 buf16[3] = cpu_to_le16(cur->key.specified);
572 rc = put_entry(buf16, sizeof(u16), 4, fp);
573 if (rc)
574 return rc;
575
576 if (cur->key.specified & AVTAB_XPERMS) {
577 rc = put_entry(&cur->datum.u.xperms->specified, sizeof(u8), 1, fp);
578 if (rc)
579 return rc;
580 rc = put_entry(&cur->datum.u.xperms->driver, sizeof(u8), 1, fp);
581 if (rc)
582 return rc;
583 for (i = 0; i < ARRAY_SIZE(cur->datum.u.xperms->perms.p); i++)
584 buf32[i] = cpu_to_le32(cur->datum.u.xperms->perms.p[i]);
585 rc = put_entry(buf32, sizeof(u32),
586 ARRAY_SIZE(cur->datum.u.xperms->perms.p), fp);
587 } else {
588 buf32[0] = cpu_to_le32(cur->datum.u.data);
589 rc = put_entry(buf32, sizeof(u32), 1, fp);
590 }
591 if (rc)
592 return rc;
593 return 0;
594}
595
596int avtab_write(struct policydb *p, struct avtab *a, void *fp)
597{
598 unsigned int i;
599 int rc = 0;
600 struct avtab_node *cur;
601 __le32 buf[1];
602
603 buf[0] = cpu_to_le32(a->nel);
604 rc = put_entry(buf, sizeof(u32), 1, fp);
605 if (rc)
606 return rc;
607
608 for (i = 0; i < a->nslot; i++) {
609 for (cur = a->htable[i]; cur; cur = cur->next) {
610 rc = avtab_write_item(p, cur, fp);
611 if (rc)
612 return rc;
613 }
614 }
615
616 return rc;
617}
618void avtab_cache_init(void)
619{
620 avtab_node_cachep = kmem_cache_create("avtab_node",
621 sizeof(struct avtab_node),
622 0, SLAB_PANIC, NULL);
623 avtab_xperms_cachep = kmem_cache_create("avtab_extended_perms",
624 sizeof(struct avtab_extended_perms),
625 0, SLAB_PANIC, NULL);
626}
627
628void avtab_cache_destroy(void)
629{
630 kmem_cache_destroy(avtab_node_cachep);
631 kmem_cache_destroy(avtab_xperms_cachep);
632}
633
