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