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