avtab.c

  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
 25static struct kmem_cache *avtab_node_cachep __ro_after_init;
 26static struct kmem_cache *avtab_xperms_cachep __ro_after_init;
 27
 28static 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
 34static 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
 65static 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
 87static 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 */
120struct 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 */
144struct 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
165struct 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
186void 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
212void avtab_init(struct avtab *h)
213{
214	h->htable = NULL;
215	h->nel = 0;
216	h->nslot = 0;
217	h->mask = 0;
218}
219
220static 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
234int 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
253int 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
259void 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 */
293static 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
306int 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
471static 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
477int 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;
512out:
513	return rc;
514
515bad:
516	avtab_destroy(a);
517	goto out;
518}
519
520int 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
556int 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
579void __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}