xref: /linux/security/selinux/ss/avtab.c (revision a619fe35ab41fded440d3762d4fbad84ff86a4d4) 
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 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 
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 
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 
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 
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 
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