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