Home | History | Annotate | Download | only in src
      1 
      2 /* Author : Stephen Smalley, <sds (at) epoch.ncsc.mil> */
      3 
      4 /*
      5  * Updated: Yuichi Nakamura <ynakam (at) hitachisoft.jp>
      6  * 	Tuned number of hash slots for avtab to reduce memory usage
      7  */
      8 
      9 /* Updated: Frank Mayer <mayerf (at) tresys.com>
     10  *          and Karl MacMillan <kmacmillan (at) mentalrootkit.com>
     11  *
     12  * 	Added conditional policy language extensions
     13  *
     14  * Updated: Red Hat, Inc.  James Morris <jmorris (at) redhat.com>
     15  *
     16  *      Code cleanup
     17  *
     18  * Updated: Karl MacMillan <kmacmillan (at) 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  */
     55 static 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 
     91 static avtab_ptr_t
     92 avtab_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 
    135 int 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  */
    179 avtab_ptr_t
    180 avtab_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 
    212 avtab_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  */
    247 avtab_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 
    278 avtab_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 
    306 void 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 
    332 int 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 
    355 int avtab_init(avtab_t * h)
    356 {
    357 	h->htable = NULL;
    358 	h->nel = 0;
    359 	return 0;
    360 }
    361 
    362 int 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;
    386 out:
    387 	h->nel = 0;
    388 	h->nslot = nslot;
    389 	h->mask = mask;
    390 	return 0;
    391 }
    392 
    393 void 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. */
    421 static 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 
    433 int 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 
    579 static 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 
    585 int 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