avtab.c revision 255e72915d4cbddceb435e13d81601755714e9f3 
1
2/* Author : Stephen Smalley, <sds@epoch.ncsc.mil> */
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
52static inline int avtab_hash(struct avtab_key *keyp, uint16_t mask)
53{
54	return ((keyp->target_class + (keyp->target_type << 2) +
55		 (keyp->source_type << 9)) & mask);
56}
57
58static avtab_ptr_t
59avtab_insert_node(avtab_t * h, int hvalue, avtab_ptr_t prev, avtab_key_t * key,
60		  avtab_datum_t * datum)
61{
62	avtab_ptr_t newnode;
63	newnode = (avtab_ptr_t) malloc(sizeof(struct avtab_node));
64	if (newnode == NULL)
65		return NULL;
66	memset(newnode, 0, sizeof(struct avtab_node));
67	newnode->key = *key;
68	newnode->datum = *datum;
69	if (prev) {
70		newnode->next = prev->next;
71		prev->next = newnode;
72	} else {
73		newnode->next = h->htable[hvalue];
74		h->htable[hvalue] = newnode;
75	}
76
77	h->nel++;
78	return newnode;
79}
80
81int avtab_insert(avtab_t * h, avtab_key_t * key, avtab_datum_t * datum)
82{
83	int hvalue;
84	avtab_ptr_t prev, cur, newnode;
85	uint16_t specified =
86	    key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
87
88	if (!h || !h->htable)
89		return SEPOL_ENOMEM;
90
91	hvalue = avtab_hash(key, h->mask);
92	for (prev = NULL, cur = h->htable[hvalue];
93	     cur; prev = cur, cur = cur->next) {
94		if (key->source_type == cur->key.source_type &&
95		    key->target_type == cur->key.target_type &&
96		    key->target_class == cur->key.target_class &&
97		    (specified & cur->key.specified))
98			return SEPOL_EEXIST;
99		if (key->source_type < cur->key.source_type)
100			break;
101		if (key->source_type == cur->key.source_type &&
102		    key->target_type < cur->key.target_type)
103			break;
104		if (key->source_type == cur->key.source_type &&
105		    key->target_type == cur->key.target_type &&
106		    key->target_class < cur->key.target_class)
107			break;
108	}
109
110	newnode = avtab_insert_node(h, hvalue, prev, key, datum);
111	if (!newnode)
112		return SEPOL_ENOMEM;
113
114	return 0;
115}
116
117/* Unlike avtab_insert(), this function allow multiple insertions of the same
118 * key/specified mask into the table, as needed by the conditional avtab.
119 * It also returns a pointer to the node inserted.
120 */
121avtab_ptr_t
122avtab_insert_nonunique(avtab_t * h, avtab_key_t * key, avtab_datum_t * datum)
123{
124	int hvalue;
125	avtab_ptr_t prev, cur, newnode;
126	uint16_t specified =
127	    key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
128
129	if (!h || !h->htable)
130		return NULL;
131	hvalue = avtab_hash(key, h->mask);
132	for (prev = NULL, cur = h->htable[hvalue];
133	     cur; prev = cur, cur = cur->next) {
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		    (specified & cur->key.specified))
138			break;
139		if (key->source_type < cur->key.source_type)
140			break;
141		if (key->source_type == cur->key.source_type &&
142		    key->target_type < cur->key.target_type)
143			break;
144		if (key->source_type == cur->key.source_type &&
145		    key->target_type == cur->key.target_type &&
146		    key->target_class < cur->key.target_class)
147			break;
148	}
149	newnode = avtab_insert_node(h, hvalue, prev, key, datum);
150
151	return newnode;
152}
153
154avtab_datum_t *avtab_search(avtab_t * h, avtab_key_t * key)
155{
156	int hvalue;
157	avtab_ptr_t cur;
158	uint16_t specified =
159	    key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
160
161	if (!h || !h->htable)
162		return NULL;
163
164	hvalue = avtab_hash(key, h->mask);
165	for (cur = h->htable[hvalue]; cur; cur = cur->next) {
166		if (key->source_type == cur->key.source_type &&
167		    key->target_type == cur->key.target_type &&
168		    key->target_class == cur->key.target_class &&
169		    (specified & cur->key.specified))
170			return &cur->datum;
171
172		if (key->source_type < cur->key.source_type)
173			break;
174		if (key->source_type == cur->key.source_type &&
175		    key->target_type < cur->key.target_type)
176			break;
177		if (key->source_type == cur->key.source_type &&
178		    key->target_type == cur->key.target_type &&
179		    key->target_class < cur->key.target_class)
180			break;
181	}
182
183	return NULL;
184}
185
186/* This search function returns a node pointer, and can be used in
187 * conjunction with avtab_search_next_node()
188 */
189avtab_ptr_t avtab_search_node(avtab_t * h, avtab_key_t * key)
190{
191	int hvalue;
192	avtab_ptr_t cur;
193	uint16_t specified =
194	    key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
195
196	if (!h || !h->htable)
197		return NULL;
198
199	hvalue = avtab_hash(key, h->mask);
200	for (cur = h->htable[hvalue]; cur; cur = cur->next) {
201		if (key->source_type == cur->key.source_type &&
202		    key->target_type == cur->key.target_type &&
203		    key->target_class == cur->key.target_class &&
204		    (specified & cur->key.specified))
205			return cur;
206
207		if (key->source_type < cur->key.source_type)
208			break;
209		if (key->source_type == cur->key.source_type &&
210		    key->target_type < cur->key.target_type)
211			break;
212		if (key->source_type == cur->key.source_type &&
213		    key->target_type == cur->key.target_type &&
214		    key->target_class < cur->key.target_class)
215			break;
216	}
217	return NULL;
218}
219
220avtab_ptr_t avtab_search_node_next(avtab_ptr_t node, int specified)
221{
222	avtab_ptr_t cur;
223
224	if (!node)
225		return NULL;
226
227	specified &= ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
228	for (cur = node->next; cur; cur = cur->next) {
229		if (node->key.source_type == cur->key.source_type &&
230		    node->key.target_type == cur->key.target_type &&
231		    node->key.target_class == cur->key.target_class &&
232		    (specified & cur->key.specified))
233			return cur;
234
235		if (node->key.source_type < cur->key.source_type)
236			break;
237		if (node->key.source_type == cur->key.source_type &&
238		    node->key.target_type < cur->key.target_type)
239			break;
240		if (node->key.source_type == cur->key.source_type &&
241		    node->key.target_type == cur->key.target_type &&
242		    node->key.target_class < cur->key.target_class)
243			break;
244	}
245	return NULL;
246}
247
248void avtab_destroy(avtab_t * h)
249{
250	unsigned int i;
251	avtab_ptr_t cur, temp;
252
253	if (!h || !h->htable)
254		return;
255
256	for (i = 0; i < h->nslot; i++) {
257		cur = h->htable[i];
258		while (cur != NULL) {
259			temp = cur;
260			cur = cur->next;
261			free(temp);
262		}
263		h->htable[i] = NULL;
264	}
265	free(h->htable);
266	h->htable = NULL;
267	h->nslot = 0;
268	h->mask = 0;
269}
270
271int avtab_map(avtab_t * h,
272	      int (*apply) (avtab_key_t * k,
273			    avtab_datum_t * d, void *args), void *args)
274{
275	unsigned int i;
276	int ret;
277	avtab_ptr_t cur;
278
279	if (!h)
280		return 0;
281
282	for (i = 0; i < h->nslot; i++) {
283		cur = h->htable[i];
284		while (cur != NULL) {
285			ret = apply(&cur->key, &cur->datum, args);
286			if (ret)
287				return ret;
288			cur = cur->next;
289		}
290	}
291	return 0;
292}
293
294int avtab_init(avtab_t * h)
295{
296	h->htable = NULL;
297	h->nel = 0;
298	return 0;
299}
300
301int avtab_alloc(avtab_t *h, uint32_t nrules)
302{
303	uint16_t mask = 0;
304	uint32_t shift = 0;
305	uint32_t work = nrules;
306	uint32_t nslot = 0;
307
308	if (nrules == 0)
309		goto out;
310
311	while (work) {
312		work  = work >> 1;
313		shift++;
314	}
315	if (shift > 2)
316		shift = shift - 2;
317	nslot = 1 << shift;
318	if (nslot > MAX_AVTAB_SIZE)
319		nslot = MAX_AVTAB_SIZE;
320	mask = nslot - 1;
321
322	h->htable = calloc(nslot, sizeof(avtab_ptr_t));
323	if (!h->htable)
324		return -1;
325out:
326	h->nel = 0;
327	h->nslot = nslot;
328	h->mask = mask;
329	return 0;
330}
331
332void avtab_hash_eval(avtab_t * h, char *tag)
333{
334	unsigned int i, chain_len, slots_used, max_chain_len;
335	avtab_ptr_t cur;
336
337	slots_used = 0;
338	max_chain_len = 0;
339	for (i = 0; i < h->nslot; i++) {
340		cur = h->htable[i];
341		if (cur) {
342			slots_used++;
343			chain_len = 0;
344			while (cur) {
345				chain_len++;
346				cur = cur->next;
347			}
348
349			if (chain_len > max_chain_len)
350				max_chain_len = chain_len;
351		}
352	}
353
354	printf
355	    ("%s:  %d entries and %d/%d buckets used, longest chain length %d\n",
356	     tag, h->nel, slots_used, h->nslot, max_chain_len);
357}
358
359/* Ordering of datums in the original avtab format in the policy file. */
360static uint16_t spec_order[] = {
361	AVTAB_ALLOWED,
362	AVTAB_AUDITDENY,
363	AVTAB_AUDITALLOW,
364	AVTAB_TRANSITION,
365	AVTAB_CHANGE,
366	AVTAB_MEMBER
367};
368
369int avtab_read_item(struct policy_file *fp, uint32_t vers, avtab_t * a,
370		    int (*insertf) (avtab_t * a, avtab_key_t * k,
371				    avtab_datum_t * d, void *p), void *p)
372{
373	uint16_t buf16[4], enabled;
374	uint32_t buf32[7], items, items2, val;
375	avtab_key_t key;
376	avtab_datum_t datum;
377	unsigned set;
378	unsigned int i;
379	int rc;
380
381	memset(&key, 0, sizeof(avtab_key_t));
382	memset(&datum, 0, sizeof(avtab_datum_t));
383
384	if (vers < POLICYDB_VERSION_AVTAB) {
385		rc = next_entry(buf32, fp, sizeof(uint32_t));
386		if (rc < 0) {
387			ERR(fp->handle, "truncated entry");
388			return -1;
389		}
390		items2 = le32_to_cpu(buf32[0]);
391
392		if (items2 < 5 || items2 > ARRAY_SIZE(buf32)) {
393			ERR(fp->handle, "invalid item count");
394			return -1;
395		}
396
397		rc = next_entry(buf32, fp, sizeof(uint32_t) * items2);
398		if (rc < 0) {
399			ERR(fp->handle, "truncated entry");
400			return -1;
401		}
402
403		items = 0;
404		val = le32_to_cpu(buf32[items++]);
405		key.source_type = (uint16_t) val;
406		if (key.source_type != val) {
407			ERR(fp->handle, "truncated source type");
408			return -1;
409		}
410		val = le32_to_cpu(buf32[items++]);
411		key.target_type = (uint16_t) val;
412		if (key.target_type != val) {
413			ERR(fp->handle, "truncated target type");
414			return -1;
415		}
416		val = le32_to_cpu(buf32[items++]);
417		key.target_class = (uint16_t) val;
418		if (key.target_class != val) {
419			ERR(fp->handle, "truncated target class");
420			return -1;
421		}
422
423		val = le32_to_cpu(buf32[items++]);
424		enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0;
425
426		if (!(val & (AVTAB_AV | AVTAB_TYPE))) {
427			ERR(fp->handle, "null entry");
428			return -1;
429		}
430		if ((val & AVTAB_AV) && (val & AVTAB_TYPE)) {
431			ERR(fp->handle, "entry has both access "
432			    "vectors and types");
433			return -1;
434		}
435
436		for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
437			if (val & spec_order[i]) {
438				key.specified = spec_order[i] | enabled;
439				datum.data = le32_to_cpu(buf32[items++]);
440				rc = insertf(a, &key, &datum, p);
441				if (rc)
442					return rc;
443			}
444		}
445
446		if (items != items2) {
447			ERR(fp->handle, "entry only had %d items, "
448			    "expected %d", items2, items);
449			return -1;
450		}
451		return 0;
452	}
453
454	rc = next_entry(buf16, fp, sizeof(uint16_t) * 4);
455	if (rc < 0) {
456		ERR(fp->handle, "truncated entry");
457		return -1;
458	}
459	items = 0;
460	key.source_type = le16_to_cpu(buf16[items++]);
461	key.target_type = le16_to_cpu(buf16[items++]);
462	key.target_class = le16_to_cpu(buf16[items++]);
463	key.specified = le16_to_cpu(buf16[items++]);
464
465	set = 0;
466	for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
467		if (key.specified & spec_order[i])
468			set++;
469	}
470	if (!set || set > 1) {
471		ERR(fp->handle, "more than one specifier");
472		return -1;
473	}
474
475	rc = next_entry(buf32, fp, sizeof(uint32_t));
476	if (rc < 0) {
477		ERR(fp->handle, "truncated entry");
478		return -1;
479	}
480	datum.data = le32_to_cpu(*buf32);
481	return insertf(a, &key, &datum, p);
482}
483
484static int avtab_insertf(avtab_t * a, avtab_key_t * k, avtab_datum_t * d,
485			 void *p __attribute__ ((unused)))
486{
487	return avtab_insert(a, k, d);
488}
489
490int avtab_read(avtab_t * a, struct policy_file *fp, uint32_t vers)
491{
492	unsigned int i;
493	int rc;
494	uint32_t buf[1];
495	uint32_t nel;
496
497	rc = next_entry(buf, fp, sizeof(uint32_t));
498	if (rc < 0) {
499		ERR(fp->handle, "truncated table");
500		goto bad;
501	}
502	nel = le32_to_cpu(buf[0]);
503	if (!nel) {
504		ERR(fp->handle, "table is empty");
505		goto bad;
506	}
507
508	rc = avtab_alloc(a, nel);
509	if (rc) {
510		ERR(fp->handle, "out of memory");
511		goto bad;
512	}
513
514	for (i = 0; i < nel; i++) {
515		rc = avtab_read_item(fp, vers, a, avtab_insertf, NULL);
516		if (rc) {
517			if (rc == SEPOL_ENOMEM)
518				ERR(fp->handle, "out of memory");
519			if (rc == SEPOL_EEXIST)
520				ERR(fp->handle, "duplicate entry");
521			ERR(fp->handle, "failed on entry %d of %u", i, nel);
522			goto bad;
523		}
524	}
525
526	return 0;
527
528      bad:
529	avtab_destroy(a);
530	return -1;
531}
532