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