xref: /openbmc/linux/security/selinux/ss/avtab.c (revision 93dc544c) 
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 
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*
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 
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 *
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, *newnode;
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 	newnode = avtab_insert_node(h, hvalue, prev, cur, key, datum);
126 
127 	return newnode;
128 }
129 
130 struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key)
131 {
132 	int hvalue;
133 	struct avtab_node *cur;
134 	u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
135 
136 	if (!h || !h->htable)
137 		return NULL;
138 
139 	hvalue = avtab_hash(key, h->mask);
140 	for (cur = h->htable[hvalue]; cur; cur = cur->next) {
141 		if (key->source_type == cur->key.source_type &&
142 		    key->target_type == cur->key.target_type &&
143 		    key->target_class == cur->key.target_class &&
144 		    (specified & cur->key.specified))
145 			return &cur->datum;
146 
147 		if (key->source_type < cur->key.source_type)
148 			break;
149 		if (key->source_type == cur->key.source_type &&
150 		    key->target_type < cur->key.target_type)
151 			break;
152 		if (key->source_type == cur->key.source_type &&
153 		    key->target_type == cur->key.target_type &&
154 		    key->target_class < cur->key.target_class)
155 			break;
156 	}
157 
158 	return NULL;
159 }
160 
161 /* This search function returns a node pointer, and can be used in
162  * conjunction with avtab_search_next_node()
163  */
164 struct avtab_node*
165 avtab_search_node(struct avtab *h, struct avtab_key *key)
166 {
167 	int hvalue;
168 	struct avtab_node *cur;
169 	u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
170 
171 	if (!h || !h->htable)
172 		return NULL;
173 
174 	hvalue = avtab_hash(key, h->mask);
175 	for (cur = h->htable[hvalue]; cur; cur = cur->next) {
176 		if (key->source_type == cur->key.source_type &&
177 		    key->target_type == cur->key.target_type &&
178 		    key->target_class == cur->key.target_class &&
179 		    (specified & cur->key.specified))
180 			return cur;
181 
182 		if (key->source_type < cur->key.source_type)
183 			break;
184 		if (key->source_type == cur->key.source_type &&
185 		    key->target_type < cur->key.target_type)
186 			break;
187 		if (key->source_type == cur->key.source_type &&
188 		    key->target_type == cur->key.target_type &&
189 		    key->target_class < cur->key.target_class)
190 			break;
191 	}
192 	return NULL;
193 }
194 
195 struct avtab_node*
196 avtab_search_node_next(struct avtab_node *node, int specified)
197 {
198 	struct avtab_node *cur;
199 
200 	if (!node)
201 		return NULL;
202 
203 	specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
204 	for (cur = node->next; cur; cur = cur->next) {
205 		if (node->key.source_type == cur->key.source_type &&
206 		    node->key.target_type == cur->key.target_type &&
207 		    node->key.target_class == cur->key.target_class &&
208 		    (specified & cur->key.specified))
209 			return cur;
210 
211 		if (node->key.source_type < cur->key.source_type)
212 			break;
213 		if (node->key.source_type == cur->key.source_type &&
214 		    node->key.target_type < cur->key.target_type)
215 			break;
216 		if (node->key.source_type == cur->key.source_type &&
217 		    node->key.target_type == cur->key.target_type &&
218 		    node->key.target_class < cur->key.target_class)
219 			break;
220 	}
221 	return NULL;
222 }
223 
224 void avtab_destroy(struct avtab *h)
225 {
226 	int i;
227 	struct avtab_node *cur, *temp;
228 
229 	if (!h || !h->htable)
230 		return;
231 
232 	for (i = 0; i < h->nslot; i++) {
233 		cur = h->htable[i];
234 		while (cur != NULL) {
235 			temp = cur;
236 			cur = cur->next;
237 			kmem_cache_free(avtab_node_cachep, temp);
238 		}
239 		h->htable[i] = NULL;
240 	}
241 	kfree(h->htable);
242 	h->htable = NULL;
243 	h->nslot = 0;
244 	h->mask = 0;
245 }
246 
247 int avtab_init(struct avtab *h)
248 {
249 	h->htable = NULL;
250 	h->nel = 0;
251 	return 0;
252 }
253 
254 int avtab_alloc(struct avtab *h, u32 nrules)
255 {
256 	u16 mask = 0;
257 	u32 shift = 0;
258 	u32 work = nrules;
259 	u32 nslot = 0;
260 
261 	if (nrules == 0)
262 		goto avtab_alloc_out;
263 
264 	while (work) {
265 		work  = work >> 1;
266 		shift++;
267 	}
268 	if (shift > 2)
269 		shift = shift - 2;
270 	nslot = 1 << shift;
271 	if (nslot > MAX_AVTAB_SIZE)
272 		nslot = MAX_AVTAB_SIZE;
273 	mask = nslot - 1;
274 
275 	h->htable = kcalloc(nslot, sizeof(*(h->htable)), GFP_KERNEL);
276 	if (!h->htable)
277 		return -ENOMEM;
278 
279  avtab_alloc_out:
280 	h->nel = 0;
281 	h->nslot = nslot;
282 	h->mask = mask;
283 	printk(KERN_DEBUG "SELinux: %d avtab hash slots, %d rules.\n",
284 	       h->nslot, nrules);
285 	return 0;
286 }
287 
288 void avtab_hash_eval(struct avtab *h, char *tag)
289 {
290 	int i, chain_len, slots_used, max_chain_len;
291 	unsigned long long chain2_len_sum;
292 	struct avtab_node *cur;
293 
294 	slots_used = 0;
295 	max_chain_len = 0;
296 	chain2_len_sum = 0;
297 	for (i = 0; i < h->nslot; i++) {
298 		cur = h->htable[i];
299 		if (cur) {
300 			slots_used++;
301 			chain_len = 0;
302 			while (cur) {
303 				chain_len++;
304 				cur = cur->next;
305 			}
306 
307 			if (chain_len > max_chain_len)
308 				max_chain_len = chain_len;
309 			chain2_len_sum += chain_len * chain_len;
310 		}
311 	}
312 
313 	printk(KERN_DEBUG "SELinux: %s:  %d entries and %d/%d buckets used, "
314 	       "longest chain length %d sum of chain length^2 %llu\n",
315 	       tag, h->nel, slots_used, h->nslot, max_chain_len,
316 	       chain2_len_sum);
317 }
318 
319 static uint16_t spec_order[] = {
320 	AVTAB_ALLOWED,
321 	AVTAB_AUDITDENY,
322 	AVTAB_AUDITALLOW,
323 	AVTAB_TRANSITION,
324 	AVTAB_CHANGE,
325 	AVTAB_MEMBER
326 };
327 
328 int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
329 		    int (*insertf)(struct avtab *a, struct avtab_key *k,
330 				   struct avtab_datum *d, void *p),
331 		    void *p)
332 {
333 	__le16 buf16[4];
334 	u16 enabled;
335 	__le32 buf32[7];
336 	u32 items, items2, val, vers = pol->policyvers;
337 	struct avtab_key key;
338 	struct avtab_datum datum;
339 	int i, rc;
340 	unsigned set;
341 
342 	memset(&key, 0, sizeof(struct avtab_key));
343 	memset(&datum, 0, sizeof(struct avtab_datum));
344 
345 	if (vers < POLICYDB_VERSION_AVTAB) {
346 		rc = next_entry(buf32, fp, sizeof(u32));
347 		if (rc < 0) {
348 			printk(KERN_ERR "SELinux: avtab: truncated entry\n");
349 			return -1;
350 		}
351 		items2 = le32_to_cpu(buf32[0]);
352 		if (items2 > ARRAY_SIZE(buf32)) {
353 			printk(KERN_ERR "SELinux: avtab: entry overflow\n");
354 			return -1;
355 
356 		}
357 		rc = next_entry(buf32, fp, sizeof(u32)*items2);
358 		if (rc < 0) {
359 			printk(KERN_ERR "SELinux: avtab: truncated entry\n");
360 			return -1;
361 		}
362 		items = 0;
363 
364 		val = le32_to_cpu(buf32[items++]);
365 		key.source_type = (u16)val;
366 		if (key.source_type != val) {
367 			printk(KERN_ERR "SELinux: avtab: truncated source type\n");
368 			return -1;
369 		}
370 		val = le32_to_cpu(buf32[items++]);
371 		key.target_type = (u16)val;
372 		if (key.target_type != val) {
373 			printk(KERN_ERR "SELinux: avtab: truncated target type\n");
374 			return -1;
375 		}
376 		val = le32_to_cpu(buf32[items++]);
377 		key.target_class = (u16)val;
378 		if (key.target_class != val) {
379 			printk(KERN_ERR "SELinux: avtab: truncated target class\n");
380 			return -1;
381 		}
382 
383 		val = le32_to_cpu(buf32[items++]);
384 		enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0;
385 
386 		if (!(val & (AVTAB_AV | AVTAB_TYPE))) {
387 			printk(KERN_ERR "SELinux: avtab: null entry\n");
388 			return -1;
389 		}
390 		if ((val & AVTAB_AV) &&
391 		    (val & AVTAB_TYPE)) {
392 			printk(KERN_ERR "SELinux: avtab: entry has both access vectors and types\n");
393 			return -1;
394 		}
395 
396 		for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
397 			if (val & spec_order[i]) {
398 				key.specified = spec_order[i] | enabled;
399 				datum.data = le32_to_cpu(buf32[items++]);
400 				rc = insertf(a, &key, &datum, p);
401 				if (rc)
402 					return rc;
403 			}
404 		}
405 
406 		if (items != items2) {
407 			printk(KERN_ERR "SELinux: avtab: entry only had %d items, expected %d\n", items2, items);
408 			return -1;
409 		}
410 		return 0;
411 	}
412 
413 	rc = next_entry(buf16, fp, sizeof(u16)*4);
414 	if (rc < 0) {
415 		printk(KERN_ERR "SELinux: avtab: truncated entry\n");
416 		return -1;
417 	}
418 
419 	items = 0;
420 	key.source_type = le16_to_cpu(buf16[items++]);
421 	key.target_type = le16_to_cpu(buf16[items++]);
422 	key.target_class = le16_to_cpu(buf16[items++]);
423 	key.specified = le16_to_cpu(buf16[items++]);
424 
425 	if (!policydb_type_isvalid(pol, key.source_type) ||
426 	    !policydb_type_isvalid(pol, key.target_type) ||
427 	    !policydb_class_isvalid(pol, key.target_class)) {
428 		printk(KERN_ERR "SELinux: avtab: invalid type or class\n");
429 		return -1;
430 	}
431 
432 	set = 0;
433 	for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
434 		if (key.specified & spec_order[i])
435 			set++;
436 	}
437 	if (!set || set > 1) {
438 		printk(KERN_ERR "SELinux:  avtab:  more than one specifier\n");
439 		return -1;
440 	}
441 
442 	rc = next_entry(buf32, fp, sizeof(u32));
443 	if (rc < 0) {
444 		printk(KERN_ERR "SELinux: avtab: truncated entry\n");
445 		return -1;
446 	}
447 	datum.data = le32_to_cpu(*buf32);
448 	if ((key.specified & AVTAB_TYPE) &&
449 	    !policydb_type_isvalid(pol, datum.data)) {
450 		printk(KERN_ERR "SELinux: avtab: invalid type\n");
451 		return -1;
452 	}
453 	return insertf(a, &key, &datum, p);
454 }
455 
456 static int avtab_insertf(struct avtab *a, struct avtab_key *k,
457 			 struct avtab_datum *d, void *p)
458 {
459 	return avtab_insert(a, k, d);
460 }
461 
462 int avtab_read(struct avtab *a, void *fp, struct policydb *pol)
463 {
464 	int rc;
465 	__le32 buf[1];
466 	u32 nel, i;
467 
468 
469 	rc = next_entry(buf, fp, sizeof(u32));
470 	if (rc < 0) {
471 		printk(KERN_ERR "SELinux: avtab: truncated table\n");
472 		goto bad;
473 	}
474 	nel = le32_to_cpu(buf[0]);
475 	if (!nel) {
476 		printk(KERN_ERR "SELinux: avtab: table is empty\n");
477 		rc = -EINVAL;
478 		goto bad;
479 	}
480 
481 	rc = avtab_alloc(a, nel);
482 	if (rc)
483 		goto bad;
484 
485 	for (i = 0; i < nel; i++) {
486 		rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL);
487 		if (rc) {
488 			if (rc == -ENOMEM)
489 				printk(KERN_ERR "SELinux: avtab: out of memory\n");
490 			else if (rc == -EEXIST)
491 				printk(KERN_ERR "SELinux: avtab: duplicate entry\n");
492 			else
493 				rc = -EINVAL;
494 			goto bad;
495 		}
496 	}
497 
498 	rc = 0;
499 out:
500 	return rc;
501 
502 bad:
503 	avtab_destroy(a);
504 	goto out;
505 }
506 
507 void avtab_cache_init(void)
508 {
509 	avtab_node_cachep = kmem_cache_create("avtab_node",
510 					      sizeof(struct avtab_node),
511 					      0, SLAB_PANIC, NULL);
512 }
513 
514 void avtab_cache_destroy(void)
515 {
516 	kmem_cache_destroy(avtab_node_cachep);
517 }
518