xref: /linux/security/selinux/ss/avtab.c (revision 2f0af91353cb64b54cfee5423820d2149039338d) 
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 
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 
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 
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 
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  */
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  */
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 
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 
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 
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 
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 
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 
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
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 
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 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 		/* Read five or more items: source type, target type,
331 		 * target class, AV type, and at least one datum.
332 		 */
333 		items2 = le32_to_cpu(buf32[0]);
334 		if (items2 < 5 || items2 > ARRAY_SIZE(buf32)) {
335 			pr_err("SELinux: avtab: invalid item count\n");
336 			return -EINVAL;
337 		}
338 		rc = next_entry(buf32, fp, sizeof(u32) * items2);
339 		if (rc) {
340 			pr_err("SELinux: avtab: truncated entry\n");
341 			return rc;
342 		}
343 		items = 0;
344 
345 		val = le32_to_cpu(buf32[items++]);
346 		key.source_type = (u16)val;
347 		if (key.source_type != val) {
348 			pr_err("SELinux: avtab: truncated source type\n");
349 			return -EINVAL;
350 		}
351 		val = le32_to_cpu(buf32[items++]);
352 		key.target_type = (u16)val;
353 		if (key.target_type != val) {
354 			pr_err("SELinux: avtab: truncated target type\n");
355 			return -EINVAL;
356 		}
357 		val = le32_to_cpu(buf32[items++]);
358 		key.target_class = (u16)val;
359 		if (key.target_class != val) {
360 			pr_err("SELinux: avtab: truncated target class\n");
361 			return -EINVAL;
362 		}
363 
364 		if (!policydb_type_isvalid(pol, key.source_type) ||
365 		    !policydb_type_isvalid(pol, key.target_type) ||
366 		    !policydb_class_isvalid(pol, key.target_class)) {
367 			pr_err("SELinux: avtab: invalid type or class\n");
368 			return -EINVAL;
369 		}
370 
371 		val = le32_to_cpu(buf32[items++]);
372 		enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0;
373 
374 		if (!(val & (AVTAB_AV | AVTAB_TYPE))) {
375 			pr_err("SELinux: avtab: null entry\n");
376 			return -EINVAL;
377 		}
378 		if ((val & AVTAB_AV) && (val & AVTAB_TYPE)) {
379 			pr_err("SELinux: avtab: entry has both access vectors and types\n");
380 			return -EINVAL;
381 		}
382 		if (val & AVTAB_XPERMS) {
383 			pr_err("SELinux: avtab: entry has extended permissions\n");
384 			return -EINVAL;
385 		}
386 
387 		for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
388 			if (val & spec_order[i]) {
389 				if (items >= items2) {
390 					pr_err("SELinux: avtab: entry has too many items (%d/%d)\n",
391 					       items + 1, items2);
392 					return -EINVAL;
393 				}
394 				key.specified = spec_order[i] | enabled;
395 				datum.u.data = le32_to_cpu(buf32[items++]);
396 
397 				if ((key.specified & AVTAB_TYPE) &&
398 				    !policydb_simpletype_isvalid(pol, datum.u.data)) {
399 					pr_err("SELinux: avtab: invalid type\n");
400 					return -EINVAL;
401 				}
402 
403 				rc = insertf(a, &key, &datum, p);
404 				if (rc)
405 					return rc;
406 			}
407 		}
408 
409 		if (items != items2) {
410 			pr_err("SELinux: avtab: entry only had %d items, expected %d\n",
411 			       items2, items);
412 			return -EINVAL;
413 		}
414 		return 0;
415 	}
416 
417 	rc = next_entry(buf16, fp, sizeof(u16) * 4);
418 	if (rc) {
419 		pr_err("SELinux: avtab: truncated entry\n");
420 		return rc;
421 	}
422 
423 	items = 0;
424 	key.source_type = le16_to_cpu(buf16[items++]);
425 	key.target_type = le16_to_cpu(buf16[items++]);
426 	key.target_class = le16_to_cpu(buf16[items++]);
427 	key.specified = le16_to_cpu(buf16[items++]);
428 
429 	if (!policydb_type_isvalid(pol, key.source_type) ||
430 	    !policydb_type_isvalid(pol, key.target_type) ||
431 	    !policydb_class_isvalid(pol, key.target_class)) {
432 		pr_err("SELinux: avtab: invalid type or class\n");
433 		return -EINVAL;
434 	}
435 
436 	if (hweight16(key.specified & ~AVTAB_ENABLED) != 1) {
437 		pr_err("SELinux:  avtab:  not exactly one specifier\n");
438 		return -EINVAL;
439 	}
440 
441 	if (key.specified & ~AVTAB_SPECIFIER_MASK) {
442 		pr_err("SELinux:  avtab:  invalid specifier\n");
443 		return -EINVAL;
444 	}
445 
446 	if ((vers < POLICYDB_VERSION_XPERMS_IOCTL) &&
447 	    (key.specified & AVTAB_XPERMS)) {
448 		pr_err("SELinux:  avtab:  policy version %u does not "
449 		       "support extended permissions rules and one "
450 		       "was specified\n",
451 		       vers);
452 		return -EINVAL;
453 	} else if ((vers < POLICYDB_VERSION_COND_XPERMS) &&
454 		   (key.specified & AVTAB_XPERMS) && conditional) {
455 		pr_err("SELinux:  avtab:  policy version %u does not "
456 		       "support extended permissions rules in conditional "
457 		       "policies and one was specified\n",
458 		       vers);
459 		return -EINVAL;
460 	} else if (key.specified & AVTAB_XPERMS) {
461 		memset(&xperms, 0, sizeof(struct avtab_extended_perms));
462 		rc = next_entry(&xperms.specified, fp, sizeof(u8));
463 		if (rc) {
464 			pr_err("SELinux: avtab: truncated entry\n");
465 			return rc;
466 		}
467 		if (!avtab_is_valid_xperm_specified(xperms.specified))
468 			pr_warn_once_policyload(pol,
469 						"SELinux: avtab: unsupported xperm specifier %#x\n",
470 						xperms.specified);
471 		rc = next_entry(&xperms.driver, fp, sizeof(u8));
472 		if (rc) {
473 			pr_err("SELinux: avtab: truncated entry\n");
474 			return rc;
475 		}
476 		rc = next_entry(buf32, fp,
477 				sizeof(u32) * ARRAY_SIZE(xperms.perms.p));
478 		if (rc) {
479 			pr_err("SELinux: avtab: truncated entry\n");
480 			return rc;
481 		}
482 		for (i = 0; i < ARRAY_SIZE(xperms.perms.p); i++)
483 			xperms.perms.p[i] = le32_to_cpu(buf32[i]);
484 		datum.u.xperms = &xperms;
485 	} else {
486 		rc = next_entry(buf32, fp, sizeof(u32));
487 		if (rc) {
488 			pr_err("SELinux: avtab: truncated entry\n");
489 			return rc;
490 		}
491 		datum.u.data = le32_to_cpu(*buf32);
492 	}
493 	if ((key.specified & AVTAB_TYPE) &&
494 	    !policydb_simpletype_isvalid(pol, datum.u.data)) {
495 		pr_err("SELinux: avtab: invalid type\n");
496 		return -EINVAL;
497 	}
498 	return insertf(a, &key, &datum, p);
499 }
500 
501 static int avtab_insertf(struct avtab *a, const struct avtab_key *k,
502 			 const struct avtab_datum *d, void *p)
503 {
504 	return avtab_insert(a, k, d);
505 }
506 
507 int avtab_read(struct avtab *a, struct policy_file *fp, struct policydb *pol)
508 {
509 	int rc;
510 	__le32 buf[1];
511 	u32 nel, i;
512 
513 	rc = next_entry(buf, fp, sizeof(u32));
514 	if (rc < 0) {
515 		pr_err("SELinux: avtab: truncated table\n");
516 		goto bad;
517 	}
518 	nel = le32_to_cpu(buf[0]);
519 	if (!nel) {
520 		pr_err("SELinux: avtab: table is empty\n");
521 		rc = -EINVAL;
522 		goto bad;
523 	}
524 
525 	/* avtab_read_item() reads at least 96 bytes for any valid entry */
526 	rc = size_check(3 * sizeof(u32), nel, fp);
527 	if (rc)
528 		goto bad;
529 
530 	rc = avtab_alloc(a, nel);
531 	if (rc)
532 		goto bad;
533 
534 	for (i = 0; i < nel; i++) {
535 		rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL, false);
536 		if (rc) {
537 			if (rc == -ENOMEM)
538 				pr_err("SELinux: avtab: out of memory\n");
539 			else if (rc == -EEXIST)
540 				pr_err("SELinux: avtab: duplicate entry\n");
541 
542 			goto bad;
543 		}
544 	}
545 
546 	rc = 0;
547 out:
548 	return rc;
549 
550 bad:
551 	avtab_destroy(a);
552 	goto out;
553 }
554 
555 int avtab_write_item(struct policydb *p, const struct avtab_node *cur, struct policy_file *fp)
556 {
557 	__le16 buf16[4];
558 	__le32 buf32[ARRAY_SIZE(cur->datum.u.xperms->perms.p)];
559 	int rc;
560 	unsigned int i;
561 
562 	buf16[0] = cpu_to_le16(cur->key.source_type);
563 	buf16[1] = cpu_to_le16(cur->key.target_type);
564 	buf16[2] = cpu_to_le16(cur->key.target_class);
565 	buf16[3] = cpu_to_le16(cur->key.specified);
566 	rc = put_entry(buf16, sizeof(u16), 4, fp);
567 	if (rc)
568 		return rc;
569 
570 	if (cur->key.specified & AVTAB_XPERMS) {
571 		rc = put_entry(&cur->datum.u.xperms->specified, sizeof(u8), 1,
572 			       fp);
573 		if (rc)
574 			return rc;
575 		rc = put_entry(&cur->datum.u.xperms->driver, sizeof(u8), 1, fp);
576 		if (rc)
577 			return rc;
578 		for (i = 0; i < ARRAY_SIZE(cur->datum.u.xperms->perms.p); i++)
579 			buf32[i] = cpu_to_le32(cur->datum.u.xperms->perms.p[i]);
580 		rc = put_entry(buf32, sizeof(u32),
581 			       ARRAY_SIZE(cur->datum.u.xperms->perms.p), fp);
582 	} else {
583 		buf32[0] = cpu_to_le32(cur->datum.u.data);
584 		rc = put_entry(buf32, sizeof(u32), 1, fp);
585 	}
586 	if (rc)
587 		return rc;
588 	return 0;
589 }
590 
591 int avtab_write(struct policydb *p, struct avtab *a, struct policy_file *fp)
592 {
593 	u32 i;
594 	int rc = 0;
595 	struct avtab_node *cur;
596 	__le32 buf[1];
597 
598 	buf[0] = cpu_to_le32(a->nel);
599 	rc = put_entry(buf, sizeof(u32), 1, fp);
600 	if (rc)
601 		return rc;
602 
603 	for (i = 0; i < a->nslot; i++) {
604 		for (cur = a->htable[i]; cur; cur = cur->next) {
605 			rc = avtab_write_item(p, cur, fp);
606 			if (rc)
607 				return rc;
608 		}
609 	}
610 
611 	return rc;
612 }
613 
614 void __init avtab_cache_init(void)
615 {
616 	avtab_node_cachep = KMEM_CACHE(avtab_node, SLAB_PANIC);
617 	avtab_xperms_cachep = KMEM_CACHE(avtab_extended_perms, SLAB_PANIC);
618 }
619