Home | History | Annotate | Download | only in src
      1 /* Authors: Karl MacMillan <kmacmillan (at) mentalrootkit.com>
      2  *          Jason Tang <jtang (at) tresys.com>
      3  *	    Joshua Brindle <jbrindle (at) tresys.com>
      4  *
      5  * Copyright (C) 2004-2005 Tresys Technology, LLC
      6  * Copyright (C) 2007 Red Hat, Inc.
      7  *
      8  *  This library is free software; you can redistribute it and/or
      9  *  modify it under the terms of the GNU Lesser General Public
     10  *  License as published by the Free Software Foundation; either
     11  *  version 2.1 of the License, or (at your option) any later version.
     12  *
     13  *  This library is distributed in the hope that it will be useful,
     14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
     15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     16  *  Lesser General Public License for more details.
     17  *
     18  *  You should have received a copy of the GNU Lesser General Public
     19  *  License along with this library; if not, write to the Free Software
     20  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
     21  */
     22 
     23 #include "context.h"
     24 #include <sepol/policydb/policydb.h>
     25 #include <sepol/policydb/conditional.h>
     26 #include <sepol/policydb/hashtab.h>
     27 #include <sepol/policydb/expand.h>
     28 #include <sepol/policydb/hierarchy.h>
     29 #include <sepol/policydb/avrule_block.h>
     30 
     31 #include <stdlib.h>
     32 #include <stdarg.h>
     33 #include <stdio.h>
     34 #include <string.h>
     35 #include <assert.h>
     36 
     37 #include "debug.h"
     38 #include "private.h"
     39 
     40 typedef struct expand_state {
     41 	int verbose;
     42 	uint32_t *typemap;
     43 	uint32_t *boolmap;
     44 	uint32_t *rolemap;
     45 	uint32_t *usermap;
     46 	policydb_t *base;
     47 	policydb_t *out;
     48 	sepol_handle_t *handle;
     49 	int expand_neverallow;
     50 } expand_state_t;
     51 
     52 struct linear_probe {
     53 	filename_trans_t **table;	/* filename_trans chunks with same stype */
     54 	filename_trans_t **ends;	/* pointers to ends of **table chunks */
     55 	uint32_t length;		/* length of the table */
     56 };
     57 
     58 static int linear_probe_create(struct linear_probe *probe, uint32_t length)
     59 {
     60 	probe->table = calloc(length, sizeof(*probe->table));
     61 	if (probe->table == NULL)
     62 		return -1;
     63 
     64 	probe->ends = calloc(length, sizeof(*probe->ends));
     65 	if (probe->ends == NULL)
     66 		return -1;
     67 
     68 	probe->length = length;
     69 
     70 	return 0;
     71 }
     72 
     73 static void linear_probe_destroy(struct linear_probe *probe)
     74 {
     75 	if (probe->length == 0)
     76 		return;
     77 
     78 	free(probe->table);
     79 	free(probe->ends);
     80 	memset(probe, 0, sizeof(*probe));
     81 }
     82 
     83 static void linear_probe_insert(struct linear_probe *probe, uint32_t key,
     84 				filename_trans_t *data)
     85 {
     86 	assert(probe->length > key);
     87 
     88 	if (probe->table[key] != NULL) {
     89 		data->next = probe->table[key];
     90 		probe->table[key] = data;
     91 	} else {
     92 		probe->table[key] = probe->ends[key] = data;
     93 	}
     94 }
     95 
     96 static filename_trans_t *linear_probe_find(struct linear_probe *probe, uint32_t key)
     97 {
     98 	assert(probe->length > key);
     99 
    100 	return probe->table[key];
    101 }
    102 
    103 /* Returns all chunks stored in the *probe as single-linked list */
    104 static filename_trans_t *linear_probe_dump(struct linear_probe *probe,
    105 					   filename_trans_t **endp)
    106 {
    107 	uint32_t i;
    108 	filename_trans_t *result = NULL;
    109 	filename_trans_t *end = NULL;
    110 
    111 	for (i = 0; i < probe->length; i++) {
    112 		if (probe->table[i] != NULL) {
    113 			if (end == NULL)
    114 				end = probe->ends[i];
    115 			probe->ends[i]->next = result;
    116 			result = probe->table[i];
    117 			probe->table[i] = probe->ends[i] = NULL;
    118 		}
    119 	}
    120 
    121 	/* Incoherent result and end pointers indicates bug */
    122 	assert((result != NULL && end != NULL) || (result == NULL && end == NULL));
    123 
    124 	*endp = end;
    125 	return result;
    126 }
    127 
    128 static void expand_state_init(expand_state_t * state)
    129 {
    130 	memset(state, 0, sizeof(expand_state_t));
    131 }
    132 
    133 static int map_ebitmap(ebitmap_t * src, ebitmap_t * dst, uint32_t * map)
    134 {
    135 	unsigned int i;
    136 	ebitmap_node_t *tnode;
    137 	ebitmap_init(dst);
    138 
    139 	ebitmap_for_each_bit(src, tnode, i) {
    140 		if (!ebitmap_node_get_bit(tnode, i))
    141 			continue;
    142 		if (!map[i])
    143 			continue;
    144 		if (ebitmap_set_bit(dst, map[i] - 1, 1))
    145 			return -1;
    146 	}
    147 	return 0;
    148 }
    149 
    150 static int type_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
    151 			      void *data)
    152 {
    153 	int ret;
    154 	char *id, *new_id;
    155 	type_datum_t *type, *new_type;
    156 	expand_state_t *state;
    157 
    158 	id = (char *)key;
    159 	type = (type_datum_t *) datum;
    160 	state = (expand_state_t *) data;
    161 
    162 	if ((type->flavor == TYPE_TYPE && !type->primary)
    163 	    || type->flavor == TYPE_ALIAS) {
    164 		/* aliases are handled later */
    165 		return 0;
    166 	}
    167 	if (!is_id_enabled(id, state->base, SYM_TYPES)) {
    168 		/* identifier's scope is not enabled */
    169 		return 0;
    170 	}
    171 
    172 	if (state->verbose)
    173 		INFO(state->handle, "copying type or attribute %s", id);
    174 
    175 	new_id = strdup(id);
    176 	if (new_id == NULL) {
    177 		ERR(state->handle, "Out of memory!");
    178 		return -1;
    179 	}
    180 
    181 	new_type = (type_datum_t *) malloc(sizeof(type_datum_t));
    182 	if (!new_type) {
    183 		ERR(state->handle, "Out of memory!");
    184 		free(new_id);
    185 		return SEPOL_ENOMEM;
    186 	}
    187 	memset(new_type, 0, sizeof(type_datum_t));
    188 
    189 	new_type->flavor = type->flavor;
    190 	new_type->flags = type->flags;
    191 	new_type->s.value = ++state->out->p_types.nprim;
    192 	if (new_type->s.value > UINT16_MAX) {
    193 		free(new_id);
    194 		free(new_type);
    195 		ERR(state->handle, "type space overflow");
    196 		return -1;
    197 	}
    198 	new_type->primary = 1;
    199 	state->typemap[type->s.value - 1] = new_type->s.value;
    200 
    201 	ret = hashtab_insert(state->out->p_types.table,
    202 			     (hashtab_key_t) new_id,
    203 			     (hashtab_datum_t) new_type);
    204 	if (ret) {
    205 		free(new_id);
    206 		free(new_type);
    207 		ERR(state->handle, "hashtab overflow");
    208 		return -1;
    209 	}
    210 
    211 	if (new_type->flags & TYPE_FLAGS_PERMISSIVE)
    212 		if (ebitmap_set_bit(&state->out->permissive_map, new_type->s.value, 1)) {
    213 			ERR(state->handle, "Out of memory!\n");
    214 			return -1;
    215 		}
    216 
    217 	return 0;
    218 }
    219 
    220 static int attr_convert_callback(hashtab_key_t key, hashtab_datum_t datum,
    221 				 void *data)
    222 {
    223 	char *id;
    224 	type_datum_t *type, *new_type;
    225 	expand_state_t *state;
    226 	ebitmap_t tmp_union;
    227 
    228 	id = (char *)key;
    229 	type = (type_datum_t *) datum;
    230 	state = (expand_state_t *) data;
    231 
    232 	if (type->flavor != TYPE_ATTRIB)
    233 		return 0;
    234 
    235 	if (!is_id_enabled(id, state->base, SYM_TYPES)) {
    236 		/* identifier's scope is not enabled */
    237 		return 0;
    238 	}
    239 
    240 	if (state->verbose)
    241 		INFO(state->handle, "converting attribute %s", id);
    242 
    243 	new_type = hashtab_search(state->out->p_types.table, id);
    244 	if (!new_type) {
    245 		ERR(state->handle, "attribute %s vanished!", id);
    246 		return -1;
    247 	}
    248 	if (map_ebitmap(&type->types, &tmp_union, state->typemap)) {
    249 		ERR(state->handle, "out of memory");
    250 		return -1;
    251 	}
    252 
    253 	/* then union tmp_union onto &new_type->types */
    254 	if (ebitmap_union(&new_type->types, &tmp_union)) {
    255 		ERR(state->handle, "Out of memory!");
    256 		return -1;
    257 	}
    258 	ebitmap_destroy(&tmp_union);
    259 
    260 	return 0;
    261 }
    262 
    263 static int perm_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
    264 			      void *data)
    265 {
    266 	int ret;
    267 	char *id, *new_id;
    268 	symtab_t *s;
    269 	perm_datum_t *perm, *new_perm;
    270 
    271 	id = key;
    272 	perm = (perm_datum_t *) datum;
    273 	s = (symtab_t *) data;
    274 
    275 	new_perm = (perm_datum_t *) malloc(sizeof(perm_datum_t));
    276 	if (!new_perm) {
    277 		return -1;
    278 	}
    279 	memset(new_perm, 0, sizeof(perm_datum_t));
    280 
    281 	new_id = strdup(id);
    282 	if (!new_id) {
    283 		free(new_perm);
    284 		return -1;
    285 	}
    286 
    287 	new_perm->s.value = perm->s.value;
    288 	s->nprim++;
    289 
    290 	ret = hashtab_insert(s->table, new_id, (hashtab_datum_t *) new_perm);
    291 	if (ret) {
    292 		free(new_id);
    293 		free(new_perm);
    294 		return -1;
    295 	}
    296 
    297 	return 0;
    298 }
    299 
    300 static int common_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
    301 				void *data)
    302 {
    303 	int ret;
    304 	char *id, *new_id;
    305 	common_datum_t *common, *new_common;
    306 	expand_state_t *state;
    307 
    308 	id = (char *)key;
    309 	common = (common_datum_t *) datum;
    310 	state = (expand_state_t *) data;
    311 
    312 	if (state->verbose)
    313 		INFO(state->handle, "copying common %s", id);
    314 
    315 	new_common = (common_datum_t *) malloc(sizeof(common_datum_t));
    316 	if (!new_common) {
    317 		ERR(state->handle, "Out of memory!");
    318 		return -1;
    319 	}
    320 	memset(new_common, 0, sizeof(common_datum_t));
    321 	if (symtab_init(&new_common->permissions, PERM_SYMTAB_SIZE)) {
    322 		ERR(state->handle, "Out of memory!");
    323 		free(new_common);
    324 		return -1;
    325 	}
    326 
    327 	new_id = strdup(id);
    328 	if (!new_id) {
    329 		ERR(state->handle, "Out of memory!");
    330 		/* free memory created by symtab_init first, then free new_common */
    331 		symtab_destroy(&new_common->permissions);
    332 		free(new_common);
    333 		return -1;
    334 	}
    335 
    336 	new_common->s.value = common->s.value;
    337 	state->out->p_commons.nprim++;
    338 
    339 	ret =
    340 	    hashtab_insert(state->out->p_commons.table, new_id,
    341 			   (hashtab_datum_t *) new_common);
    342 	if (ret) {
    343 		ERR(state->handle, "hashtab overflow");
    344 		free(new_common);
    345 		free(new_id);
    346 		return -1;
    347 	}
    348 
    349 	if (hashtab_map
    350 	    (common->permissions.table, perm_copy_callback,
    351 	     &new_common->permissions)) {
    352 		ERR(state->handle, "Out of memory!");
    353 		return -1;
    354 	}
    355 
    356 	return 0;
    357 }
    358 
    359 static int constraint_node_clone(constraint_node_t ** dst,
    360 				 constraint_node_t * src,
    361 				 expand_state_t * state)
    362 {
    363 	constraint_node_t *new_con = NULL, *last_new_con = NULL;
    364 	constraint_expr_t *new_expr = NULL;
    365 	*dst = NULL;
    366 	while (src != NULL) {
    367 		constraint_expr_t *expr, *expr_l = NULL;
    368 		new_con =
    369 		    (constraint_node_t *) malloc(sizeof(constraint_node_t));
    370 		if (!new_con) {
    371 			goto out_of_mem;
    372 		}
    373 		memset(new_con, 0, sizeof(constraint_node_t));
    374 		new_con->permissions = src->permissions;
    375 		for (expr = src->expr; expr; expr = expr->next) {
    376 			if ((new_expr = calloc(1, sizeof(*new_expr))) == NULL) {
    377 				goto out_of_mem;
    378 			}
    379 			if (constraint_expr_init(new_expr) == -1) {
    380 				goto out_of_mem;
    381 			}
    382 			new_expr->expr_type = expr->expr_type;
    383 			new_expr->attr = expr->attr;
    384 			new_expr->op = expr->op;
    385 			if (new_expr->expr_type == CEXPR_NAMES) {
    386 				if (new_expr->attr & CEXPR_TYPE) {
    387 					/*
    388 					 * Copy over constraint policy source types and/or
    389 					 * attributes for sepol_compute_av_reason_buffer(3)
    390 					 * so that utilities can analyse constraint errors.
    391 					 */
    392 					if (map_ebitmap(&expr->type_names->types,
    393 							&new_expr->type_names->types,
    394 							state->typemap)) {
    395 						ERR(NULL, "Failed to map type_names->types");
    396 						goto out_of_mem;
    397 					}
    398 					/* Type sets require expansion and conversion. */
    399 					if (expand_convert_type_set(state->out,
    400 								    state->
    401 								    typemap,
    402 								    expr->
    403 								    type_names,
    404 								    &new_expr->
    405 								    names, 1)) {
    406 						goto out_of_mem;
    407 					}
    408 				} else if (new_expr->attr & CEXPR_ROLE) {
    409 					if (map_ebitmap(&expr->names, &new_expr->names, state->rolemap)) {
    410 						goto out_of_mem;
    411 					}
    412 				} else if (new_expr->attr & CEXPR_USER) {
    413 					if (map_ebitmap(&expr->names, &new_expr->names, state->usermap)) {
    414 						goto out_of_mem;
    415 					}
    416 				} else {
    417 					/* Other kinds of sets do not. */
    418 					if (ebitmap_cpy(&new_expr->names,
    419 							&expr->names)) {
    420 						goto out_of_mem;
    421 					}
    422 				}
    423 			}
    424 			if (expr_l) {
    425 				expr_l->next = new_expr;
    426 			} else {
    427 				new_con->expr = new_expr;
    428 			}
    429 			expr_l = new_expr;
    430 			new_expr = NULL;
    431 		}
    432 		if (last_new_con == NULL) {
    433 			*dst = new_con;
    434 		} else {
    435 			last_new_con->next = new_con;
    436 		}
    437 		last_new_con = new_con;
    438 		src = src->next;
    439 	}
    440 
    441 	return 0;
    442       out_of_mem:
    443 	ERR(state->handle, "Out of memory!");
    444 	if (new_con)
    445 		free(new_con);
    446 	constraint_expr_destroy(new_expr);
    447 	return -1;
    448 }
    449 
    450 static int class_copy_default_new_object(expand_state_t *state,
    451 					 class_datum_t *olddatum,
    452 					 class_datum_t *newdatum)
    453 {
    454 	if (olddatum->default_user) {
    455 		if (newdatum->default_user && olddatum->default_user != newdatum->default_user) {
    456 			ERR(state->handle, "Found conflicting default user definitions");
    457 			return SEPOL_ENOTSUP;
    458 		}
    459 		newdatum->default_user = olddatum->default_user;
    460 
    461 	}
    462 	if (olddatum->default_role) {
    463 		if (newdatum->default_role && olddatum->default_role != newdatum->default_role) {
    464 			ERR(state->handle, "Found conflicting default role definitions");
    465 			return SEPOL_ENOTSUP;
    466 		}
    467 		newdatum->default_role = olddatum->default_role;
    468 	}
    469 	if (olddatum->default_type) {
    470 		if (newdatum->default_type && olddatum->default_type != newdatum->default_type) {
    471 			ERR(state->handle, "Found conflicting default type definitions");
    472 			return SEPOL_ENOTSUP;
    473 		}
    474 		newdatum->default_type = olddatum->default_type;
    475 	}
    476 	if (olddatum->default_range) {
    477 		if (newdatum->default_range && olddatum->default_range != newdatum->default_range) {
    478 			ERR(state->handle, "Found conflicting default range definitions");
    479 			return SEPOL_ENOTSUP;
    480 		}
    481 		newdatum->default_range = olddatum->default_range;
    482 	}
    483 	return 0;
    484 }
    485 
    486 static int class_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
    487 			       void *data)
    488 {
    489 	int ret;
    490 	char *id, *new_id;
    491 	class_datum_t *class, *new_class;
    492 	expand_state_t *state;
    493 
    494 	id = (char *)key;
    495 	class = (class_datum_t *) datum;
    496 	state = (expand_state_t *) data;
    497 
    498 	if (!is_id_enabled(id, state->base, SYM_CLASSES)) {
    499 		/* identifier's scope is not enabled */
    500 		return 0;
    501 	}
    502 
    503 	if (state->verbose)
    504 		INFO(state->handle, "copying class %s", id);
    505 
    506 	new_class = (class_datum_t *) malloc(sizeof(class_datum_t));
    507 	if (!new_class) {
    508 		ERR(state->handle, "Out of memory!");
    509 		return -1;
    510 	}
    511 	memset(new_class, 0, sizeof(class_datum_t));
    512 	if (symtab_init(&new_class->permissions, PERM_SYMTAB_SIZE)) {
    513 		ERR(state->handle, "Out of memory!");
    514 		free(new_class);
    515 		return -1;
    516 	}
    517 
    518 	new_class->s.value = class->s.value;
    519 	state->out->p_classes.nprim++;
    520 
    521 	ret = class_copy_default_new_object(state, class, new_class);
    522 	if (ret) {
    523 		free(new_class);
    524 		return ret;
    525 	}
    526 
    527 	new_id = strdup(id);
    528 	if (!new_id) {
    529 		ERR(state->handle, "Out of memory!");
    530 		free(new_class);
    531 		return -1;
    532 	}
    533 
    534 	ret =
    535 	    hashtab_insert(state->out->p_classes.table, new_id,
    536 			   (hashtab_datum_t *) new_class);
    537 	if (ret) {
    538 		ERR(state->handle, "hashtab overflow");
    539 		free(new_class);
    540 		free(new_id);
    541 		return -1;
    542 	}
    543 
    544 	if (hashtab_map
    545 	    (class->permissions.table, perm_copy_callback,
    546 	     &new_class->permissions)) {
    547 		ERR(state->handle, "hashtab overflow");
    548 		return -1;
    549 	}
    550 
    551 	if (class->comkey) {
    552 		new_class->comkey = strdup(class->comkey);
    553 		if (!new_class->comkey) {
    554 			ERR(state->handle, "Out of memory!");
    555 			return -1;
    556 		}
    557 
    558 		new_class->comdatum =
    559 		    hashtab_search(state->out->p_commons.table,
    560 				   new_class->comkey);
    561 		if (!new_class->comdatum) {
    562 			ERR(state->handle, "could not find common datum %s",
    563 			    new_class->comkey);
    564 			return -1;
    565 		}
    566 		new_class->permissions.nprim +=
    567 		    new_class->comdatum->permissions.nprim;
    568 	}
    569 
    570 	return 0;
    571 }
    572 
    573 static int constraint_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
    574 				    void *data)
    575 {
    576 	char *id;
    577 	class_datum_t *class, *new_class;
    578 	expand_state_t *state;
    579 
    580 	id = (char *)key;
    581 	class = (class_datum_t *) datum;
    582 	state = (expand_state_t *) data;
    583 
    584 	new_class = hashtab_search(state->out->p_classes.table, id);
    585 	if (!new_class) {
    586 		ERR(state->handle, "class %s vanished", id);
    587 		return -1;
    588 	}
    589 
    590 	/* constraints */
    591 	if (constraint_node_clone
    592 	    (&new_class->constraints, class->constraints, state) == -1
    593 	    || constraint_node_clone(&new_class->validatetrans,
    594 				     class->validatetrans, state) == -1) {
    595 		return -1;
    596 	}
    597 	return 0;
    598 }
    599 
    600 /*
    601  * The boundaries have to be copied after the types/roles/users are copied,
    602  * because it refers hashtab to lookup destinated objects.
    603  */
    604 static int type_bounds_copy_callback(hashtab_key_t key,
    605 				     hashtab_datum_t datum, void *data)
    606 {
    607 	expand_state_t *state = (expand_state_t *) data;
    608 	type_datum_t *type = (type_datum_t *) datum;
    609 	type_datum_t *dest;
    610 	uint32_t bounds_val;
    611 
    612 	if (!type->bounds)
    613 		return 0;
    614 
    615 	if (!is_id_enabled((char *)key, state->base, SYM_TYPES))
    616 		return 0;
    617 
    618 	bounds_val = state->typemap[type->bounds - 1];
    619 
    620 	dest = hashtab_search(state->out->p_types.table, (char *)key);
    621 	if (!dest) {
    622 		ERR(state->handle, "Type lookup failed for %s", (char *)key);
    623 		return -1;
    624 	}
    625 	if (dest->bounds != 0 && dest->bounds != bounds_val) {
    626 		ERR(state->handle, "Inconsistent boundary for %s", (char *)key);
    627 		return -1;
    628 	}
    629 	dest->bounds = bounds_val;
    630 
    631 	return 0;
    632 }
    633 
    634 static int role_bounds_copy_callback(hashtab_key_t key,
    635 				     hashtab_datum_t datum, void *data)
    636 {
    637 	expand_state_t *state = (expand_state_t *) data;
    638 	role_datum_t *role = (role_datum_t *) datum;
    639 	role_datum_t *dest;
    640 	uint32_t bounds_val;
    641 
    642 	if (!role->bounds)
    643 		return 0;
    644 
    645 	if (!is_id_enabled((char *)key, state->base, SYM_ROLES))
    646 		return 0;
    647 
    648 	bounds_val = state->rolemap[role->bounds - 1];
    649 
    650 	dest = hashtab_search(state->out->p_roles.table, (char *)key);
    651 	if (!dest) {
    652 		ERR(state->handle, "Role lookup failed for %s", (char *)key);
    653 		return -1;
    654 	}
    655 	if (dest->bounds != 0 && dest->bounds != bounds_val) {
    656 		ERR(state->handle, "Inconsistent boundary for %s", (char *)key);
    657 		return -1;
    658 	}
    659 	dest->bounds = bounds_val;
    660 
    661 	return 0;
    662 }
    663 
    664 static int user_bounds_copy_callback(hashtab_key_t key,
    665 				     hashtab_datum_t datum, void *data)
    666 {
    667 	expand_state_t *state = (expand_state_t *) data;
    668 	user_datum_t *user = (user_datum_t *) datum;
    669 	user_datum_t *dest;
    670 	uint32_t bounds_val;
    671 
    672 	if (!user->bounds)
    673 		return 0;
    674 
    675 	if (!is_id_enabled((char *)key, state->base, SYM_USERS))
    676 		return 0;
    677 
    678 	bounds_val = state->usermap[user->bounds - 1];
    679 
    680 	dest = hashtab_search(state->out->p_users.table, (char *)key);
    681 	if (!dest) {
    682 		ERR(state->handle, "User lookup failed for %s", (char *)key);
    683 		return -1;
    684 	}
    685 	if (dest->bounds != 0 && dest->bounds != bounds_val) {
    686 		ERR(state->handle, "Inconsistent boundary for %s", (char *)key);
    687 		return -1;
    688 	}
    689 	dest->bounds = bounds_val;
    690 
    691 	return 0;
    692 }
    693 
    694 /* The aliases have to be copied after the types and attributes to be certain that
    695  * the out symbol table will have the type that the alias refers. Otherwise, we
    696  * won't be able to find the type value for the alias. We can't depend on the
    697  * declaration ordering because of the hash table.
    698  */
    699 static int alias_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
    700 			       void *data)
    701 {
    702 	int ret;
    703 	char *id, *new_id;
    704 	type_datum_t *alias, *new_alias;
    705 	expand_state_t *state;
    706 	uint32_t prival;
    707 
    708 	id = (char *)key;
    709 	alias = (type_datum_t *) datum;
    710 	state = (expand_state_t *) data;
    711 
    712 	/* ignore regular types */
    713 	if (alias->flavor == TYPE_TYPE && alias->primary)
    714 		return 0;
    715 
    716 	/* ignore attributes */
    717 	if (alias->flavor == TYPE_ATTRIB)
    718 		return 0;
    719 
    720 	if (alias->flavor == TYPE_ALIAS)
    721 		prival = alias->primary;
    722 	else
    723 		prival = alias->s.value;
    724 
    725 	if (!is_id_enabled(state->base->p_type_val_to_name[prival - 1],
    726 			state->base, SYM_TYPES)) {
    727 		/* The primary type for this alias is not enabled, the alias
    728  		 * shouldn't be either */
    729 		return 0;
    730 	}
    731 
    732 	if (state->verbose)
    733 		INFO(state->handle, "copying alias %s", id);
    734 
    735 	new_id = strdup(id);
    736 	if (!new_id) {
    737 		ERR(state->handle, "Out of memory!");
    738 		return -1;
    739 	}
    740 
    741 	new_alias = (type_datum_t *) malloc(sizeof(type_datum_t));
    742 	if (!new_alias) {
    743 		ERR(state->handle, "Out of memory!");
    744 		free(new_id);
    745 		return SEPOL_ENOMEM;
    746 	}
    747 	memset(new_alias, 0, sizeof(type_datum_t));
    748 	if (alias->flavor == TYPE_TYPE)
    749 		new_alias->s.value = state->typemap[alias->s.value - 1];
    750 	else if (alias->flavor == TYPE_ALIAS)
    751 		new_alias->s.value = state->typemap[alias->primary - 1];
    752 	else
    753 		assert(0);	/* unreachable */
    754 
    755 	new_alias->flags = alias->flags;
    756 
    757 	ret = hashtab_insert(state->out->p_types.table,
    758 			     (hashtab_key_t) new_id,
    759 			     (hashtab_datum_t) new_alias);
    760 
    761 	if (ret) {
    762 		ERR(state->handle, "hashtab overflow");
    763 		free(new_alias);
    764 		free(new_id);
    765 		return -1;
    766 	}
    767 
    768 	state->typemap[alias->s.value - 1] = new_alias->s.value;
    769 
    770 	if (new_alias->flags & TYPE_FLAGS_PERMISSIVE)
    771 		if (ebitmap_set_bit(&state->out->permissive_map, new_alias->s.value, 1)) {
    772 			ERR(state->handle, "Out of memory!");
    773 			return -1;
    774 		}
    775 
    776 	return 0;
    777 }
    778 
    779 static int role_remap_dominates(hashtab_key_t key __attribute__ ((unused)), hashtab_datum_t datum, void *data)
    780 {
    781 	ebitmap_t mapped_roles;
    782 	role_datum_t *role = (role_datum_t *) datum;
    783 	expand_state_t *state = (expand_state_t *) data;
    784 
    785 	if (map_ebitmap(&role->dominates, &mapped_roles, state->rolemap))
    786 		return -1;
    787 
    788 	ebitmap_destroy(&role->dominates);
    789 
    790 	if (ebitmap_cpy(&role->dominates, &mapped_roles))
    791 		return -1;
    792 
    793 	ebitmap_destroy(&mapped_roles);
    794 
    795 	return 0;
    796 }
    797 
    798 /* For the role attribute in the base module, escalate its counterpart's
    799  * types.types ebitmap in the out module to the counterparts of all the
    800  * regular role that belongs to the current role attribute. Note, must be
    801  * invoked after role_copy_callback so that state->rolemap is available.
    802  */
    803 static int role_fix_callback(hashtab_key_t key, hashtab_datum_t datum,
    804 			     void *data)
    805 {
    806 	char *id, *base_reg_role_id;
    807 	role_datum_t *role, *new_role, *regular_role;
    808 	expand_state_t *state;
    809 	ebitmap_node_t *rnode;
    810 	unsigned int i;
    811 	ebitmap_t mapped_roles;
    812 
    813 	id = key;
    814 	role = (role_datum_t *)datum;
    815 	state = (expand_state_t *)data;
    816 
    817 	if (strcmp(id, OBJECT_R) == 0) {
    818 		/* object_r is never a role attribute by far */
    819 		return 0;
    820 	}
    821 
    822 	if (!is_id_enabled(id, state->base, SYM_ROLES)) {
    823 		/* identifier's scope is not enabled */
    824 		return 0;
    825 	}
    826 
    827 	if (role->flavor != ROLE_ATTRIB)
    828 		return 0;
    829 
    830 	if (state->verbose)
    831 		INFO(state->handle, "fixing role attribute %s", id);
    832 
    833 	new_role =
    834 		(role_datum_t *)hashtab_search(state->out->p_roles.table, id);
    835 
    836 	assert(new_role != NULL && new_role->flavor == ROLE_ATTRIB);
    837 
    838 	ebitmap_init(&mapped_roles);
    839 	if (map_ebitmap(&role->roles, &mapped_roles, state->rolemap))
    840 		return -1;
    841 	if (ebitmap_union(&new_role->roles, &mapped_roles)) {
    842 		ERR(state->handle, "Out of memory!");
    843 		ebitmap_destroy(&mapped_roles);
    844 		return -1;
    845 	}
    846 	ebitmap_destroy(&mapped_roles);
    847 
    848 	ebitmap_for_each_bit(&role->roles, rnode, i) {
    849 		if (ebitmap_node_get_bit(rnode, i)) {
    850 			/* take advantage of sym_val_to_name[]
    851 			 * of the base module */
    852 			base_reg_role_id = state->base->p_role_val_to_name[i];
    853 			regular_role = (role_datum_t *)hashtab_search(
    854 						state->out->p_roles.table,
    855 						base_reg_role_id);
    856 			assert(regular_role != NULL &&
    857 			       regular_role->flavor == ROLE_ROLE);
    858 
    859 			if (ebitmap_union(&regular_role->types.types,
    860 					  &new_role->types.types)) {
    861 				ERR(state->handle, "Out of memory!");
    862 				return -1;
    863 			}
    864 		}
    865 	}
    866 
    867 	return 0;
    868 }
    869 
    870 static int role_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
    871 			      void *data)
    872 {
    873 	int ret;
    874 	char *id, *new_id;
    875 	role_datum_t *role;
    876 	role_datum_t *new_role;
    877 	expand_state_t *state;
    878 	ebitmap_t tmp_union_types;
    879 
    880 	id = key;
    881 	role = (role_datum_t *) datum;
    882 	state = (expand_state_t *) data;
    883 
    884 	if (strcmp(id, OBJECT_R) == 0) {
    885 		/* object_r is always value 1 */
    886 		state->rolemap[role->s.value - 1] = 1;
    887 		return 0;
    888 	}
    889 
    890 	if (!is_id_enabled(id, state->base, SYM_ROLES)) {
    891 		/* identifier's scope is not enabled */
    892 		return 0;
    893 	}
    894 
    895 	if (state->verbose)
    896 		INFO(state->handle, "copying role %s", id);
    897 
    898 	new_role =
    899 	    (role_datum_t *) hashtab_search(state->out->p_roles.table, id);
    900 	if (!new_role) {
    901 		new_role = (role_datum_t *) malloc(sizeof(role_datum_t));
    902 		if (!new_role) {
    903 			ERR(state->handle, "Out of memory!");
    904 			return -1;
    905 		}
    906 		memset(new_role, 0, sizeof(role_datum_t));
    907 
    908 		new_id = strdup(id);
    909 		if (!new_id) {
    910 			ERR(state->handle, "Out of memory!");
    911 			free(new_role);
    912 			return -1;
    913 		}
    914 
    915 		state->out->p_roles.nprim++;
    916 		new_role->flavor = role->flavor;
    917 		new_role->s.value = state->out->p_roles.nprim;
    918 		state->rolemap[role->s.value - 1] = new_role->s.value;
    919 		ret = hashtab_insert(state->out->p_roles.table,
    920 				     (hashtab_key_t) new_id,
    921 				     (hashtab_datum_t) new_role);
    922 
    923 		if (ret) {
    924 			ERR(state->handle, "hashtab overflow");
    925 			free(new_role);
    926 			free(new_id);
    927 			return -1;
    928 		}
    929 	}
    930 
    931 	/* The dominates bitmap is going to be wrong for the moment,
    932  	 * we'll come back later and remap them, after we are sure all
    933  	 * the roles have been added */
    934 	if (ebitmap_union(&new_role->dominates, &role->dominates)) {
    935 		ERR(state->handle, "Out of memory!");
    936 		return -1;
    937 	}
    938 
    939 	ebitmap_init(&tmp_union_types);
    940 
    941 	/* convert types in the role datum in the global symtab */
    942 	if (expand_convert_type_set
    943 	    (state->out, state->typemap, &role->types, &tmp_union_types, 1)) {
    944 		ebitmap_destroy(&tmp_union_types);
    945 		ERR(state->handle, "Out of memory!");
    946 		return -1;
    947 	}
    948 
    949 	if (ebitmap_union(&new_role->types.types, &tmp_union_types)) {
    950 		ERR(state->handle, "Out of memory!");
    951 		ebitmap_destroy(&tmp_union_types);
    952 		return -1;
    953 	}
    954 	ebitmap_destroy(&tmp_union_types);
    955 
    956 	return 0;
    957 }
    958 
    959 int mls_semantic_level_expand(mls_semantic_level_t * sl, mls_level_t * l,
    960 			      policydb_t * p, sepol_handle_t * h)
    961 {
    962 	mls_semantic_cat_t *cat;
    963 	level_datum_t *levdatum;
    964 	unsigned int i;
    965 
    966 	mls_level_init(l);
    967 
    968 	if (!p->mls)
    969 		return 0;
    970 
    971 	/* Required not declared. */
    972 	if (!sl->sens)
    973 		return 0;
    974 
    975 	l->sens = sl->sens;
    976 	levdatum = (level_datum_t *) hashtab_search(p->p_levels.table,
    977 						    p->p_sens_val_to_name[l->sens - 1]);
    978 	if (!levdatum) {
    979 		ERR(h, "%s: Impossible situation found, nothing in p_levels.table.\n",
    980 		    __func__);
    981 		errno = ENOENT;
    982 		return -1;
    983 	}
    984 	for (cat = sl->cat; cat; cat = cat->next) {
    985 		if (cat->low > cat->high) {
    986 			ERR(h, "Category range is not valid %s.%s",
    987 			    p->p_cat_val_to_name[cat->low - 1],
    988 			    p->p_cat_val_to_name[cat->high - 1]);
    989 			return -1;
    990 		}
    991 		for (i = cat->low - 1; i < cat->high; i++) {
    992 			if (!ebitmap_get_bit(&levdatum->level->cat, i)) {
    993 				ERR(h, "Category %s can not be associate with "
    994 				    "level %s",
    995 				    p->p_cat_val_to_name[i],
    996 				    p->p_sens_val_to_name[l->sens - 1]);
    997 			}
    998 			if (ebitmap_set_bit(&l->cat, i, 1)) {
    999 				ERR(h, "Out of memory!");
   1000 				return -1;
   1001 			}
   1002 		}
   1003 	}
   1004 
   1005 	return 0;
   1006 }
   1007 
   1008 int mls_semantic_range_expand(mls_semantic_range_t * sr, mls_range_t * r,
   1009 			      policydb_t * p, sepol_handle_t * h)
   1010 {
   1011 	if (mls_semantic_level_expand(&sr->level[0], &r->level[0], p, h) < 0)
   1012 		return -1;
   1013 
   1014 	if (mls_semantic_level_expand(&sr->level[1], &r->level[1], p, h) < 0) {
   1015 		mls_semantic_level_destroy(&sr->level[0]);
   1016 		return -1;
   1017 	}
   1018 
   1019 	if (!mls_level_dom(&r->level[1], &r->level[0])) {
   1020 		mls_range_destroy(r);
   1021 		ERR(h, "MLS range high level does not dominate low level");
   1022 		return -1;
   1023 	}
   1024 
   1025 	return 0;
   1026 }
   1027 
   1028 static int user_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
   1029 			      void *data)
   1030 {
   1031 	int ret;
   1032 	expand_state_t *state;
   1033 	user_datum_t *user;
   1034 	user_datum_t *new_user;
   1035 	char *id, *new_id;
   1036 	ebitmap_t tmp_union;
   1037 
   1038 	id = key;
   1039 	user = (user_datum_t *) datum;
   1040 	state = (expand_state_t *) data;
   1041 
   1042 	if (!is_id_enabled(id, state->base, SYM_USERS)) {
   1043 		/* identifier's scope is not enabled */
   1044 		return 0;
   1045 	}
   1046 
   1047 	if (state->verbose)
   1048 		INFO(state->handle, "copying user %s", id);
   1049 
   1050 	new_user =
   1051 	    (user_datum_t *) hashtab_search(state->out->p_users.table, id);
   1052 	if (!new_user) {
   1053 		new_user = (user_datum_t *) malloc(sizeof(user_datum_t));
   1054 		if (!new_user) {
   1055 			ERR(state->handle, "Out of memory!");
   1056 			return -1;
   1057 		}
   1058 		memset(new_user, 0, sizeof(user_datum_t));
   1059 
   1060 		state->out->p_users.nprim++;
   1061 		new_user->s.value = state->out->p_users.nprim;
   1062 		state->usermap[user->s.value - 1] = new_user->s.value;
   1063 
   1064 		new_id = strdup(id);
   1065 		if (!new_id) {
   1066 			ERR(state->handle, "Out of memory!");
   1067 			free(new_user);
   1068 			return -1;
   1069 		}
   1070 		ret = hashtab_insert(state->out->p_users.table,
   1071 				     (hashtab_key_t) new_id,
   1072 				     (hashtab_datum_t) new_user);
   1073 		if (ret) {
   1074 			ERR(state->handle, "hashtab overflow");
   1075 			user_datum_destroy(new_user);
   1076 			free(new_user);
   1077 			free(new_id);
   1078 			return -1;
   1079 		}
   1080 
   1081 		/* expand the semantic MLS info */
   1082 		if (mls_semantic_range_expand(&user->range,
   1083 					      &new_user->exp_range,
   1084 					      state->out, state->handle)) {
   1085 			return -1;
   1086 		}
   1087 		if (mls_semantic_level_expand(&user->dfltlevel,
   1088 					      &new_user->exp_dfltlevel,
   1089 					      state->out, state->handle)) {
   1090 			return -1;
   1091 		}
   1092 		if (!mls_level_between(&new_user->exp_dfltlevel,
   1093 				       &new_user->exp_range.level[0],
   1094 				       &new_user->exp_range.level[1])) {
   1095 			ERR(state->handle, "default level not within user "
   1096 			    "range");
   1097 			return -1;
   1098 		}
   1099 	} else {
   1100 		/* require that the MLS info match */
   1101 		mls_range_t tmp_range;
   1102 		mls_level_t tmp_level;
   1103 
   1104 		if (mls_semantic_range_expand(&user->range, &tmp_range,
   1105 					      state->out, state->handle)) {
   1106 			return -1;
   1107 		}
   1108 		if (mls_semantic_level_expand(&user->dfltlevel, &tmp_level,
   1109 					      state->out, state->handle)) {
   1110 			mls_range_destroy(&tmp_range);
   1111 			return -1;
   1112 		}
   1113 		if (!mls_range_eq(&new_user->exp_range, &tmp_range) ||
   1114 		    !mls_level_eq(&new_user->exp_dfltlevel, &tmp_level)) {
   1115 			mls_range_destroy(&tmp_range);
   1116 			mls_level_destroy(&tmp_level);
   1117 			return -1;
   1118 		}
   1119 		mls_range_destroy(&tmp_range);
   1120 		mls_level_destroy(&tmp_level);
   1121 	}
   1122 
   1123 	ebitmap_init(&tmp_union);
   1124 
   1125 	/* get global roles for this user */
   1126 	if (role_set_expand(&user->roles, &tmp_union, state->out, state->base, state->rolemap)) {
   1127 		ERR(state->handle, "Out of memory!");
   1128 		ebitmap_destroy(&tmp_union);
   1129 		return -1;
   1130 	}
   1131 
   1132 	if (ebitmap_union(&new_user->roles.roles, &tmp_union)) {
   1133 		ERR(state->handle, "Out of memory!");
   1134 		ebitmap_destroy(&tmp_union);
   1135 		return -1;
   1136 	}
   1137 	ebitmap_destroy(&tmp_union);
   1138 
   1139 	return 0;
   1140 }
   1141 
   1142 static int bool_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
   1143 			      void *data)
   1144 {
   1145 	int ret;
   1146 	expand_state_t *state;
   1147 	cond_bool_datum_t *bool, *new_bool;
   1148 	char *id, *new_id;
   1149 
   1150 	id = key;
   1151 	bool = (cond_bool_datum_t *) datum;
   1152 	state = (expand_state_t *) data;
   1153 
   1154 	if (!is_id_enabled(id, state->base, SYM_BOOLS)) {
   1155 		/* identifier's scope is not enabled */
   1156 		return 0;
   1157 	}
   1158 
   1159 	if (bool->flags & COND_BOOL_FLAGS_TUNABLE) {
   1160 		/* Skip tunables */
   1161 		return 0;
   1162 	}
   1163 
   1164 	if (state->verbose)
   1165 		INFO(state->handle, "copying boolean %s", id);
   1166 
   1167 	new_bool = (cond_bool_datum_t *) malloc(sizeof(cond_bool_datum_t));
   1168 	if (!new_bool) {
   1169 		ERR(state->handle, "Out of memory!");
   1170 		return -1;
   1171 	}
   1172 
   1173 	new_id = strdup(id);
   1174 	if (!new_id) {
   1175 		ERR(state->handle, "Out of memory!");
   1176 		free(new_bool);
   1177 		return -1;
   1178 	}
   1179 
   1180 	state->out->p_bools.nprim++;
   1181 	new_bool->s.value = state->out->p_bools.nprim;
   1182 
   1183 	ret = hashtab_insert(state->out->p_bools.table,
   1184 			     (hashtab_key_t) new_id,
   1185 			     (hashtab_datum_t) new_bool);
   1186 	if (ret) {
   1187 		ERR(state->handle, "hashtab overflow");
   1188 		free(new_bool);
   1189 		free(new_id);
   1190 		return -1;
   1191 	}
   1192 
   1193 	state->boolmap[bool->s.value - 1] = new_bool->s.value;
   1194 
   1195 	new_bool->state = bool->state;
   1196 	new_bool->flags = bool->flags;
   1197 
   1198 	return 0;
   1199 }
   1200 
   1201 static int sens_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
   1202 			      void *data)
   1203 {
   1204 	expand_state_t *state = (expand_state_t *) data;
   1205 	level_datum_t *level = (level_datum_t *) datum, *new_level = NULL;
   1206 	char *id = (char *)key, *new_id = NULL;
   1207 
   1208 	if (!is_id_enabled(id, state->base, SYM_LEVELS)) {
   1209 		/* identifier's scope is not enabled */
   1210 		return 0;
   1211 	}
   1212 
   1213 	if (state->verbose)
   1214 		INFO(state->handle, "copying sensitivity level %s", id);
   1215 
   1216 	new_level = (level_datum_t *) malloc(sizeof(level_datum_t));
   1217 	if (!new_level)
   1218 		goto out_of_mem;
   1219 	level_datum_init(new_level);
   1220 	new_level->level = (mls_level_t *) malloc(sizeof(mls_level_t));
   1221 	if (!new_level->level)
   1222 		goto out_of_mem;
   1223 	mls_level_init(new_level->level);
   1224 	new_id = strdup(id);
   1225 	if (!new_id)
   1226 		goto out_of_mem;
   1227 
   1228 	if (mls_level_cpy(new_level->level, level->level)) {
   1229 		goto out_of_mem;
   1230 	}
   1231 	new_level->isalias = level->isalias;
   1232 	state->out->p_levels.nprim++;
   1233 
   1234 	if (hashtab_insert(state->out->p_levels.table,
   1235 			   (hashtab_key_t) new_id,
   1236 			   (hashtab_datum_t) new_level)) {
   1237 		goto out_of_mem;
   1238 	}
   1239 	return 0;
   1240 
   1241       out_of_mem:
   1242 	ERR(state->handle, "Out of memory!");
   1243 	if (new_level != NULL && new_level->level != NULL) {
   1244 		mls_level_destroy(new_level->level);
   1245 		free(new_level->level);
   1246 	}
   1247 	level_datum_destroy(new_level);
   1248 	free(new_level);
   1249 	free(new_id);
   1250 	return -1;
   1251 }
   1252 
   1253 static int cats_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
   1254 			      void *data)
   1255 {
   1256 	expand_state_t *state = (expand_state_t *) data;
   1257 	cat_datum_t *cat = (cat_datum_t *) datum, *new_cat = NULL;
   1258 	char *id = (char *)key, *new_id = NULL;
   1259 
   1260 	if (!is_id_enabled(id, state->base, SYM_CATS)) {
   1261 		/* identifier's scope is not enabled */
   1262 		return 0;
   1263 	}
   1264 
   1265 	if (state->verbose)
   1266 		INFO(state->handle, "copying category attribute %s", id);
   1267 
   1268 	new_cat = (cat_datum_t *) malloc(sizeof(cat_datum_t));
   1269 	if (!new_cat)
   1270 		goto out_of_mem;
   1271 	cat_datum_init(new_cat);
   1272 	new_id = strdup(id);
   1273 	if (!new_id)
   1274 		goto out_of_mem;
   1275 
   1276 	new_cat->s.value = cat->s.value;
   1277 	new_cat->isalias = cat->isalias;
   1278 	state->out->p_cats.nprim++;
   1279 	if (hashtab_insert(state->out->p_cats.table,
   1280 			   (hashtab_key_t) new_id, (hashtab_datum_t) new_cat)) {
   1281 		goto out_of_mem;
   1282 	}
   1283 
   1284 	return 0;
   1285 
   1286       out_of_mem:
   1287 	ERR(state->handle, "Out of memory!");
   1288 	cat_datum_destroy(new_cat);
   1289 	free(new_cat);
   1290 	free(new_id);
   1291 	return -1;
   1292 }
   1293 
   1294 static int copy_role_allows(expand_state_t * state, role_allow_rule_t * rules)
   1295 {
   1296 	unsigned int i, j;
   1297 	role_allow_t *cur_allow, *n, *l;
   1298 	role_allow_rule_t *cur;
   1299 	ebitmap_t roles, new_roles;
   1300 	ebitmap_node_t *snode, *tnode;
   1301 
   1302 	/* start at the end of the list */
   1303 	for (l = state->out->role_allow; l && l->next; l = l->next) ;
   1304 
   1305 	cur = rules;
   1306 	while (cur) {
   1307 		ebitmap_init(&roles);
   1308 		ebitmap_init(&new_roles);
   1309 
   1310 		if (role_set_expand(&cur->roles, &roles, state->out, state->base, state->rolemap)) {
   1311 			ERR(state->handle, "Out of memory!");
   1312 			return -1;
   1313 		}
   1314 
   1315 		if (role_set_expand(&cur->new_roles, &new_roles, state->out, state->base, state->rolemap)) {
   1316 			ERR(state->handle, "Out of memory!");
   1317 			return -1;
   1318 		}
   1319 
   1320 		ebitmap_for_each_bit(&roles, snode, i) {
   1321 			if (!ebitmap_node_get_bit(snode, i))
   1322 				continue;
   1323 			ebitmap_for_each_bit(&new_roles, tnode, j) {
   1324 				if (!ebitmap_node_get_bit(tnode, j))
   1325 					continue;
   1326 				/* check for duplicates */
   1327 				cur_allow = state->out->role_allow;
   1328 				while (cur_allow) {
   1329 					if ((cur_allow->role == i + 1) &&
   1330 					    (cur_allow->new_role == j + 1))
   1331 						break;
   1332 					cur_allow = cur_allow->next;
   1333 				}
   1334 				if (cur_allow)
   1335 					continue;
   1336 				n = (role_allow_t *)
   1337 				    malloc(sizeof(role_allow_t));
   1338 				if (!n) {
   1339 					ERR(state->handle, "Out of memory!");
   1340 					return -1;
   1341 				}
   1342 				memset(n, 0, sizeof(role_allow_t));
   1343 				n->role = i + 1;
   1344 				n->new_role = j + 1;
   1345 				if (l) {
   1346 					l->next = n;
   1347 				} else {
   1348 					state->out->role_allow = n;
   1349 				}
   1350 				l = n;
   1351 			}
   1352 		}
   1353 
   1354 		ebitmap_destroy(&roles);
   1355 		ebitmap_destroy(&new_roles);
   1356 
   1357 		cur = cur->next;
   1358 	}
   1359 
   1360 	return 0;
   1361 }
   1362 
   1363 static int copy_role_trans(expand_state_t * state, role_trans_rule_t * rules)
   1364 {
   1365 	unsigned int i, j, k;
   1366 	role_trans_t *n, *l, *cur_trans;
   1367 	role_trans_rule_t *cur;
   1368 	ebitmap_t roles, types;
   1369 	ebitmap_node_t *rnode, *tnode, *cnode;
   1370 
   1371 	/* start at the end of the list */
   1372 	for (l = state->out->role_tr; l && l->next; l = l->next) ;
   1373 
   1374 	cur = rules;
   1375 	while (cur) {
   1376 		ebitmap_init(&roles);
   1377 		ebitmap_init(&types);
   1378 
   1379 		if (role_set_expand(&cur->roles, &roles, state->out, state->base, state->rolemap)) {
   1380 			ERR(state->handle, "Out of memory!");
   1381 			return -1;
   1382 		}
   1383 		if (expand_convert_type_set
   1384 		    (state->out, state->typemap, &cur->types, &types, 1)) {
   1385 			ERR(state->handle, "Out of memory!");
   1386 			return -1;
   1387 		}
   1388 		ebitmap_for_each_bit(&roles, rnode, i) {
   1389 			if (!ebitmap_node_get_bit(rnode, i))
   1390 				continue;
   1391 			ebitmap_for_each_bit(&types, tnode, j) {
   1392 				if (!ebitmap_node_get_bit(tnode, j))
   1393 					continue;
   1394 				ebitmap_for_each_bit(&cur->classes, cnode, k) {
   1395 					if (!ebitmap_node_get_bit(cnode, k))
   1396 						continue;
   1397 
   1398 					cur_trans = state->out->role_tr;
   1399 					while (cur_trans) {
   1400 						unsigned int mapped_role;
   1401 
   1402 						mapped_role = state->rolemap[cur->new_role - 1];
   1403 
   1404 						if ((cur_trans->role ==
   1405 								i + 1) &&
   1406 						    (cur_trans->type ==
   1407 								j + 1) &&
   1408 						    (cur_trans->tclass ==
   1409 								k + 1)) {
   1410 							if (cur_trans->new_role == mapped_role) {
   1411 								break;
   1412 							} else {
   1413 								ERR(state->handle,
   1414 									"Conflicting role trans rule %s %s : %s { %s vs %s }",
   1415 									state->out->p_role_val_to_name[i],
   1416 									state->out->p_type_val_to_name[j],
   1417 									state->out->p_class_val_to_name[k],
   1418 									state->out->p_role_val_to_name[mapped_role - 1],
   1419 									state->out->p_role_val_to_name[cur_trans->new_role - 1]);
   1420 								return -1;
   1421 							}
   1422 						}
   1423 						cur_trans = cur_trans->next;
   1424 					}
   1425 					if (cur_trans)
   1426 						continue;
   1427 
   1428 					n = (role_trans_t *)
   1429 						malloc(sizeof(role_trans_t));
   1430 					if (!n) {
   1431 						ERR(state->handle,
   1432 							"Out of memory!");
   1433 						return -1;
   1434 					}
   1435 					memset(n, 0, sizeof(role_trans_t));
   1436 					n->role = i + 1;
   1437 					n->type = j + 1;
   1438 					n->tclass = k + 1;
   1439 					n->new_role = state->rolemap
   1440 							[cur->new_role - 1];
   1441 					if (l)
   1442 						l->next = n;
   1443 					else
   1444 						state->out->role_tr = n;
   1445 
   1446 					l = n;
   1447 				}
   1448 			}
   1449 		}
   1450 
   1451 		ebitmap_destroy(&roles);
   1452 		ebitmap_destroy(&types);
   1453 
   1454 		cur = cur->next;
   1455 	}
   1456 	return 0;
   1457 }
   1458 
   1459 static int expand_filename_trans(expand_state_t *state, filename_trans_rule_t *rules)
   1460 {
   1461 	unsigned int i, j;
   1462 	filename_trans_t *new_trans, *cur_trans, *end;
   1463 	filename_trans_rule_t *cur_rule;
   1464 	ebitmap_t stypes, ttypes;
   1465 	ebitmap_node_t *snode, *tnode;
   1466 	struct linear_probe probe;
   1467 
   1468 	/*
   1469 	 * Linear probing speeds-up finding filename_trans rules with certain
   1470 	 * "stype" value.
   1471 	 */
   1472 	if (linear_probe_create(&probe, 4096)) { /* Assume 4096 is enough for most cases */
   1473 		ERR(state->handle, "Out of memory!");
   1474 		return -1;
   1475 	}
   1476 
   1477 	cur_rule = rules;
   1478 	while (cur_rule) {
   1479 		uint32_t mapped_otype;
   1480 
   1481 		ebitmap_init(&stypes);
   1482 		ebitmap_init(&ttypes);
   1483 
   1484 		if (expand_convert_type_set(state->out, state->typemap,
   1485 					    &cur_rule->stypes, &stypes, 1)) {
   1486 			ERR(state->handle, "Out of memory!");
   1487 			return -1;
   1488 		}
   1489 
   1490 		if (expand_convert_type_set(state->out, state->typemap,
   1491 					    &cur_rule->ttypes, &ttypes, 1)) {
   1492 			ERR(state->handle, "Out of memory!");
   1493 			return -1;
   1494 		}
   1495 
   1496 		mapped_otype = state->typemap[cur_rule->otype - 1];
   1497 
   1498 		if (ebitmap_length(&stypes) > probe.length) {
   1499 			linear_probe_destroy(&probe);
   1500 			if (linear_probe_create(&probe, ebitmap_length(&stypes))) {
   1501 				ERR(state->handle, "Out of memory!");
   1502 				return -1;
   1503 			}
   1504 		}
   1505 
   1506 		ebitmap_for_each_bit(&stypes, snode, i) {
   1507 			if (!ebitmap_node_get_bit(snode, i))
   1508 				continue;
   1509 			ebitmap_for_each_bit(&ttypes, tnode, j) {
   1510 				if (!ebitmap_node_get_bit(tnode, j))
   1511 					continue;
   1512 
   1513 				cur_trans = linear_probe_find(&probe, i);
   1514 				while (cur_trans != NULL) {
   1515 					if ((cur_trans->ttype == j + 1) &&
   1516 					    (cur_trans->tclass == cur_rule->tclass) &&
   1517 					    (!strcmp(cur_trans->name, cur_rule->name))) {
   1518 						/* duplicate rule, who cares */
   1519 						if (cur_trans->otype == mapped_otype)
   1520 							break;
   1521 						ERR(state->handle, "Conflicting filename trans rules %s %s %s : %s otype1:%s otype2:%s",
   1522 						    cur_trans->name,
   1523 						    state->out->p_type_val_to_name[i],
   1524 						    state->out->p_type_val_to_name[j],
   1525 						    state->out->p_class_val_to_name[cur_trans->tclass - 1],
   1526 						    state->out->p_type_val_to_name[cur_trans->otype - 1],
   1527 						    state->out->p_type_val_to_name[mapped_otype - 1]);
   1528 
   1529 						return -1;
   1530 					}
   1531 					cur_trans = cur_trans->next;
   1532 				}
   1533 				/* duplicate rule, who cares */
   1534 				if (cur_trans)
   1535 					continue;
   1536 
   1537 				new_trans = malloc(sizeof(*new_trans));
   1538 				if (!new_trans) {
   1539 					ERR(state->handle, "Out of memory!");
   1540 					return -1;
   1541 				}
   1542 				memset(new_trans, 0, sizeof(*new_trans));
   1543 
   1544 				new_trans->name = strdup(cur_rule->name);
   1545 				if (!new_trans->name) {
   1546 					ERR(state->handle, "Out of memory!");
   1547 					return -1;
   1548 				}
   1549 				new_trans->stype = i + 1;
   1550 				new_trans->ttype = j + 1;
   1551 				new_trans->tclass = cur_rule->tclass;
   1552 				new_trans->otype = mapped_otype;
   1553 				linear_probe_insert(&probe, i, new_trans);
   1554 			}
   1555 		}
   1556 
   1557 		cur_trans = linear_probe_dump(&probe, &end);
   1558 		if (cur_trans != NULL) {
   1559 			end->next = state->out->filename_trans;
   1560 			state->out->filename_trans = cur_trans;
   1561 		}
   1562 
   1563 		ebitmap_destroy(&stypes);
   1564 		ebitmap_destroy(&ttypes);
   1565 
   1566 		cur_rule = cur_rule->next;
   1567 	}
   1568 	return 0;
   1569 }
   1570 
   1571 static int exp_rangetr_helper(uint32_t stype, uint32_t ttype, uint32_t tclass,
   1572 			      mls_semantic_range_t * trange,
   1573 			      expand_state_t * state)
   1574 {
   1575 	range_trans_t *rt, *check_rt = state->out->range_tr;
   1576 	mls_range_t exp_range;
   1577 	int rc = -1;
   1578 
   1579 	if (mls_semantic_range_expand(trange, &exp_range, state->out,
   1580 				      state->handle))
   1581 		goto out;
   1582 
   1583 	/* check for duplicates/conflicts */
   1584 	while (check_rt) {
   1585 		if ((check_rt->source_type == stype) &&
   1586 		    (check_rt->target_type == ttype) &&
   1587 		    (check_rt->target_class == tclass)) {
   1588 			if (mls_range_eq(&check_rt->target_range, &exp_range)) {
   1589 				/* duplicate */
   1590 				break;
   1591 			} else {
   1592 				/* conflict */
   1593 				ERR(state->handle,
   1594 				    "Conflicting range trans rule %s %s : %s",
   1595 				    state->out->p_type_val_to_name[stype - 1],
   1596 				    state->out->p_type_val_to_name[ttype - 1],
   1597 				    state->out->p_class_val_to_name[tclass -
   1598 								    1]);
   1599 				goto out;
   1600 			}
   1601 		}
   1602 		check_rt = check_rt->next;
   1603 	}
   1604 	if (check_rt) {
   1605 		/* this is a dup - skip */
   1606 		rc = 0;
   1607 		goto out;
   1608 	}
   1609 
   1610 	rt = (range_trans_t *) calloc(1, sizeof(range_trans_t));
   1611 	if (!rt) {
   1612 		ERR(state->handle, "Out of memory!");
   1613 		goto out;
   1614 	}
   1615 
   1616 	rt->next = state->out->range_tr;
   1617 	state->out->range_tr = rt;
   1618 
   1619 	rt->source_type = stype;
   1620 	rt->target_type = ttype;
   1621 	rt->target_class = tclass;
   1622 	if (mls_range_cpy(&rt->target_range, &exp_range)) {
   1623 		ERR(state->handle, "Out of memory!");
   1624 		goto out;
   1625 	}
   1626 
   1627 	rc = 0;
   1628 
   1629       out:
   1630 	mls_range_destroy(&exp_range);
   1631 	return rc;
   1632 }
   1633 
   1634 static int expand_range_trans(expand_state_t * state,
   1635 			      range_trans_rule_t * rules)
   1636 {
   1637 	unsigned int i, j, k;
   1638 	range_trans_rule_t *rule;
   1639 
   1640 	ebitmap_t stypes, ttypes;
   1641 	ebitmap_node_t *snode, *tnode, *cnode;
   1642 
   1643 	if (state->verbose)
   1644 		INFO(state->handle, "expanding range transitions");
   1645 
   1646 	for (rule = rules; rule; rule = rule->next) {
   1647 		ebitmap_init(&stypes);
   1648 		ebitmap_init(&ttypes);
   1649 
   1650 		/* expand the type sets */
   1651 		if (expand_convert_type_set(state->out, state->typemap,
   1652 					    &rule->stypes, &stypes, 1)) {
   1653 			ERR(state->handle, "Out of memory!");
   1654 			return -1;
   1655 		}
   1656 		if (expand_convert_type_set(state->out, state->typemap,
   1657 					    &rule->ttypes, &ttypes, 1)) {
   1658 			ebitmap_destroy(&stypes);
   1659 			ERR(state->handle, "Out of memory!");
   1660 			return -1;
   1661 		}
   1662 
   1663 		/* loop on source type */
   1664 		ebitmap_for_each_bit(&stypes, snode, i) {
   1665 			if (!ebitmap_node_get_bit(snode, i))
   1666 				continue;
   1667 			/* loop on target type */
   1668 			ebitmap_for_each_bit(&ttypes, tnode, j) {
   1669 				if (!ebitmap_node_get_bit(tnode, j))
   1670 					continue;
   1671 				/* loop on target class */
   1672 				ebitmap_for_each_bit(&rule->tclasses, cnode, k) {
   1673 					if (!ebitmap_node_get_bit(cnode, k))
   1674 						continue;
   1675 
   1676 					if (exp_rangetr_helper(i + 1,
   1677 							       j + 1,
   1678 							       k + 1,
   1679 							       &rule->trange,
   1680 							       state)) {
   1681 						ebitmap_destroy(&stypes);
   1682 						ebitmap_destroy(&ttypes);
   1683 						return -1;
   1684 					}
   1685 				}
   1686 			}
   1687 		}
   1688 
   1689 		ebitmap_destroy(&stypes);
   1690 		ebitmap_destroy(&ttypes);
   1691 	}
   1692 
   1693 	return 0;
   1694 }
   1695 
   1696 /* Search for an AV tab node within a hash table with the given key.
   1697  * If the node does not exist, create it and return it; otherwise
   1698  * return the pre-existing one.
   1699 */
   1700 static avtab_ptr_t find_avtab_node(sepol_handle_t * handle,
   1701 				   avtab_t * avtab, avtab_key_t * key,
   1702 				   cond_av_list_t ** cond)
   1703 {
   1704 	avtab_ptr_t node;
   1705 	avtab_datum_t avdatum;
   1706 	cond_av_list_t *nl;
   1707 
   1708 	node = avtab_search_node(avtab, key);
   1709 
   1710 	/* If this is for conditional policies, keep searching in case
   1711 	   the node is part of my conditional avtab. */
   1712 	if (cond) {
   1713 		while (node) {
   1714 			if (node->parse_context == cond)
   1715 				break;
   1716 			node = avtab_search_node_next(node, key->specified);
   1717 		}
   1718 	}
   1719 
   1720 	if (!node) {
   1721 		memset(&avdatum, 0, sizeof avdatum);
   1722 		/* this is used to get the node - insertion is actually unique */
   1723 		node = avtab_insert_nonunique(avtab, key, &avdatum);
   1724 		if (!node) {
   1725 			ERR(handle, "hash table overflow");
   1726 			return NULL;
   1727 		}
   1728 		if (cond) {
   1729 			node->parse_context = cond;
   1730 			nl = (cond_av_list_t *) malloc(sizeof(cond_av_list_t));
   1731 			if (!nl) {
   1732 				ERR(handle, "Memory error");
   1733 				return NULL;
   1734 			}
   1735 			memset(nl, 0, sizeof(cond_av_list_t));
   1736 			nl->node = node;
   1737 			nl->next = *cond;
   1738 			*cond = nl;
   1739 		}
   1740 	}
   1741 
   1742 	return node;
   1743 }
   1744 
   1745 #define EXPAND_RULE_SUCCESS   1
   1746 #define EXPAND_RULE_CONFLICT  0
   1747 #define EXPAND_RULE_ERROR    -1
   1748 
   1749 static int expand_terule_helper(sepol_handle_t * handle,
   1750 				policydb_t * p, uint32_t * typemap,
   1751 				uint32_t specified, cond_av_list_t ** cond,
   1752 				cond_av_list_t ** other, uint32_t stype,
   1753 				uint32_t ttype, class_perm_node_t * perms,
   1754 				avtab_t * avtab, int enabled)
   1755 {
   1756 	avtab_key_t avkey;
   1757 	avtab_datum_t *avdatump;
   1758 	avtab_ptr_t node;
   1759 	class_perm_node_t *cur;
   1760 	int conflict;
   1761 	uint32_t oldtype = 0, spec = 0;
   1762 
   1763 	if (specified & AVRULE_TRANSITION) {
   1764 		spec = AVTAB_TRANSITION;
   1765 	} else if (specified & AVRULE_MEMBER) {
   1766 		spec = AVTAB_MEMBER;
   1767 	} else if (specified & AVRULE_CHANGE) {
   1768 		spec = AVTAB_CHANGE;
   1769 	} else {
   1770 		assert(0);	/* unreachable */
   1771 	}
   1772 
   1773 	cur = perms;
   1774 	while (cur) {
   1775 		uint32_t remapped_data =
   1776 		    typemap ? typemap[cur->data - 1] : cur->data;
   1777 		avkey.source_type = stype + 1;
   1778 		avkey.target_type = ttype + 1;
   1779 		avkey.target_class = cur->class;
   1780 		avkey.specified = spec;
   1781 
   1782 		conflict = 0;
   1783 		/* check to see if the expanded TE already exists --
   1784 		 * either in the global scope or in another
   1785 		 * conditional AV tab */
   1786 		node = avtab_search_node(&p->te_avtab, &avkey);
   1787 		if (node) {
   1788 			conflict = 1;
   1789 		} else {
   1790 			node = avtab_search_node(&p->te_cond_avtab, &avkey);
   1791 			if (node && node->parse_context != other) {
   1792 				conflict = 2;
   1793 			}
   1794 		}
   1795 
   1796 		if (conflict) {
   1797 			avdatump = &node->datum;
   1798 			if (specified & AVRULE_TRANSITION) {
   1799 				oldtype = avdatump->data;
   1800 			} else if (specified & AVRULE_MEMBER) {
   1801 				oldtype = avdatump->data;
   1802 			} else if (specified & AVRULE_CHANGE) {
   1803 				oldtype = avdatump->data;
   1804 			}
   1805 
   1806 			if (oldtype == remapped_data) {
   1807 				/* if the duplicate is inside the same scope (eg., unconditional
   1808 				 * or in same conditional then ignore it */
   1809 				if ((conflict == 1 && cond == NULL)
   1810 				    || node->parse_context == cond)
   1811 					return EXPAND_RULE_SUCCESS;
   1812 				ERR(handle, "duplicate TE rule for %s %s:%s %s",
   1813 				    p->p_type_val_to_name[avkey.source_type -
   1814 							  1],
   1815 				    p->p_type_val_to_name[avkey.target_type -
   1816 							  1],
   1817 				    p->p_class_val_to_name[avkey.target_class -
   1818 							   1],
   1819 				    p->p_type_val_to_name[oldtype - 1]);
   1820 				return EXPAND_RULE_CONFLICT;
   1821 			}
   1822 			ERR(handle,
   1823 			    "conflicting TE rule for (%s, %s:%s):  old was %s, new is %s",
   1824 			    p->p_type_val_to_name[avkey.source_type - 1],
   1825 			    p->p_type_val_to_name[avkey.target_type - 1],
   1826 			    p->p_class_val_to_name[avkey.target_class - 1],
   1827 			    p->p_type_val_to_name[oldtype - 1],
   1828 			    p->p_type_val_to_name[remapped_data - 1]);
   1829 			return EXPAND_RULE_CONFLICT;
   1830 		}
   1831 
   1832 		node = find_avtab_node(handle, avtab, &avkey, cond);
   1833 		if (!node)
   1834 			return -1;
   1835 		if (enabled) {
   1836 			node->key.specified |= AVTAB_ENABLED;
   1837 		} else {
   1838 			node->key.specified &= ~AVTAB_ENABLED;
   1839 		}
   1840 
   1841 		avdatump = &node->datum;
   1842 		if (specified & AVRULE_TRANSITION) {
   1843 			avdatump->data = remapped_data;
   1844 		} else if (specified & AVRULE_MEMBER) {
   1845 			avdatump->data = remapped_data;
   1846 		} else if (specified & AVRULE_CHANGE) {
   1847 			avdatump->data = remapped_data;
   1848 		} else {
   1849 			assert(0);	/* should never occur */
   1850 		}
   1851 
   1852 		cur = cur->next;
   1853 	}
   1854 
   1855 	return EXPAND_RULE_SUCCESS;
   1856 }
   1857 
   1858 static int expand_avrule_helper(sepol_handle_t * handle,
   1859 				uint32_t specified,
   1860 				cond_av_list_t ** cond,
   1861 				uint32_t stype, uint32_t ttype,
   1862 				class_perm_node_t * perms, avtab_t * avtab,
   1863 				int enabled)
   1864 {
   1865 	avtab_key_t avkey;
   1866 	avtab_datum_t *avdatump;
   1867 	avtab_ptr_t node;
   1868 	class_perm_node_t *cur;
   1869 	uint32_t spec = 0;
   1870 
   1871 	if (specified & AVRULE_ALLOWED) {
   1872 		spec = AVTAB_ALLOWED;
   1873 	} else if (specified & AVRULE_AUDITALLOW) {
   1874 		spec = AVTAB_AUDITALLOW;
   1875 	} else if (specified & AVRULE_AUDITDENY) {
   1876 		spec = AVTAB_AUDITDENY;
   1877 	} else if (specified & AVRULE_DONTAUDIT) {
   1878 		if (handle && handle->disable_dontaudit)
   1879 			return EXPAND_RULE_SUCCESS;
   1880 		spec = AVTAB_AUDITDENY;
   1881 	} else if (specified & AVRULE_NEVERALLOW) {
   1882 		spec = AVTAB_NEVERALLOW;
   1883 	} else {
   1884 		assert(0);	/* unreachable */
   1885 	}
   1886 
   1887 	cur = perms;
   1888 	while (cur) {
   1889 		avkey.source_type = stype + 1;
   1890 		avkey.target_type = ttype + 1;
   1891 		avkey.target_class = cur->class;
   1892 		avkey.specified = spec;
   1893 
   1894 		node = find_avtab_node(handle, avtab, &avkey, cond);
   1895 		if (!node)
   1896 			return EXPAND_RULE_ERROR;
   1897 		if (enabled) {
   1898 			node->key.specified |= AVTAB_ENABLED;
   1899 		} else {
   1900 			node->key.specified &= ~AVTAB_ENABLED;
   1901 		}
   1902 
   1903 		avdatump = &node->datum;
   1904 		if (specified & AVRULE_ALLOWED) {
   1905 			avdatump->data |= cur->data;
   1906 		} else if (specified & AVRULE_AUDITALLOW) {
   1907 			avdatump->data |= cur->data;
   1908 		} else if (specified & AVRULE_NEVERALLOW) {
   1909 			avdatump->data |= cur->data;
   1910 		} else if (specified & AVRULE_AUDITDENY) {
   1911 			/* Since a '0' in an auditdeny mask represents
   1912 			 * a permission we do NOT want to audit
   1913 			 * (dontaudit), we use the '&' operand to
   1914 			 * ensure that all '0's in the mask are
   1915 			 * retained (much unlike the allow and
   1916 			 * auditallow cases).
   1917 			 */
   1918 			avdatump->data &= cur->data;
   1919 		} else if (specified & AVRULE_DONTAUDIT) {
   1920 			if (avdatump->data)
   1921 				avdatump->data &= ~cur->data;
   1922 			else
   1923 				avdatump->data = ~cur->data;
   1924 		} else {
   1925 			assert(0);	/* should never occur */
   1926 		}
   1927 
   1928 		cur = cur->next;
   1929 	}
   1930 	return EXPAND_RULE_SUCCESS;
   1931 }
   1932 
   1933 static int expand_rule_helper(sepol_handle_t * handle,
   1934 			      policydb_t * p, uint32_t * typemap,
   1935 			      avrule_t * source_rule, avtab_t * dest_avtab,
   1936 			      cond_av_list_t ** cond, cond_av_list_t ** other,
   1937 			      int enabled,
   1938 			      ebitmap_t * stypes, ebitmap_t * ttypes)
   1939 {
   1940 	unsigned int i, j;
   1941 	int retval;
   1942 	ebitmap_node_t *snode, *tnode;
   1943 
   1944 	ebitmap_for_each_bit(stypes, snode, i) {
   1945 		if (!ebitmap_node_get_bit(snode, i))
   1946 			continue;
   1947 		if (source_rule->flags & RULE_SELF) {
   1948 			if (source_rule->specified & AVRULE_AV) {
   1949 				retval = expand_avrule_helper(handle, source_rule->specified,
   1950 							      cond, i, i, source_rule->perms,
   1951 							      dest_avtab, enabled);
   1952 				if (retval != EXPAND_RULE_SUCCESS)
   1953 					return retval;
   1954 			} else {
   1955 				retval = expand_terule_helper(handle, p, typemap,
   1956 							      source_rule->specified, cond,
   1957 							      other, i, i, source_rule->perms,
   1958 							      dest_avtab, enabled);
   1959 				if (retval != EXPAND_RULE_SUCCESS)
   1960 					return retval;
   1961 			}
   1962 		}
   1963 		ebitmap_for_each_bit(ttypes, tnode, j) {
   1964 			if (!ebitmap_node_get_bit(tnode, j))
   1965 				continue;
   1966 			if (source_rule->specified & AVRULE_AV) {
   1967 				retval = expand_avrule_helper(handle, source_rule->specified,
   1968 							      cond, i, j, source_rule->perms,
   1969 							      dest_avtab, enabled);
   1970 				if (retval != EXPAND_RULE_SUCCESS)
   1971 					return retval;
   1972 			} else {
   1973 				retval = expand_terule_helper(handle, p, typemap,
   1974 							      source_rule->specified, cond,
   1975 							      other, i, j, source_rule->perms,
   1976 							      dest_avtab, enabled);
   1977 				if (retval != EXPAND_RULE_SUCCESS)
   1978 					return retval;
   1979 			}
   1980 		}
   1981 	}
   1982 
   1983 	return EXPAND_RULE_SUCCESS;
   1984 }
   1985 
   1986 /*
   1987  * Expand a rule into a given avtab - checking for conflicting type
   1988  * rules in the destination policy.  Return EXPAND_RULE_SUCCESS on
   1989  * success, EXPAND_RULE_CONFLICT if the rule conflicts with something
   1990  * (and hence was not added), or EXPAND_RULE_ERROR on error.
   1991  */
   1992 static int convert_and_expand_rule(sepol_handle_t * handle,
   1993 				   policydb_t * dest_pol, uint32_t * typemap,
   1994 				   avrule_t * source_rule, avtab_t * dest_avtab,
   1995 				   cond_av_list_t ** cond,
   1996 				   cond_av_list_t ** other, int enabled,
   1997 				   int do_neverallow)
   1998 {
   1999 	int retval;
   2000 	ebitmap_t stypes, ttypes;
   2001 	unsigned char alwaysexpand;
   2002 
   2003 	if (!do_neverallow && source_rule->specified & AVRULE_NEVERALLOW)
   2004 		return EXPAND_RULE_SUCCESS;
   2005 
   2006 	ebitmap_init(&stypes);
   2007 	ebitmap_init(&ttypes);
   2008 
   2009 	/* Force expansion for type rules and for self rules. */
   2010 	alwaysexpand = ((source_rule->specified & AVRULE_TYPE) ||
   2011 			(source_rule->flags & RULE_SELF));
   2012 
   2013 	if (expand_convert_type_set
   2014 	    (dest_pol, typemap, &source_rule->stypes, &stypes, alwaysexpand))
   2015 		return EXPAND_RULE_ERROR;
   2016 	if (expand_convert_type_set
   2017 	    (dest_pol, typemap, &source_rule->ttypes, &ttypes, alwaysexpand))
   2018 		return EXPAND_RULE_ERROR;
   2019 
   2020 	retval = expand_rule_helper(handle, dest_pol, typemap,
   2021 				    source_rule, dest_avtab,
   2022 				    cond, other, enabled, &stypes, &ttypes);
   2023 	ebitmap_destroy(&stypes);
   2024 	ebitmap_destroy(&ttypes);
   2025 	return retval;
   2026 }
   2027 
   2028 static int cond_avrule_list_copy(policydb_t * dest_pol, avrule_t * source_rules,
   2029 				 avtab_t * dest_avtab, cond_av_list_t ** list,
   2030 				 cond_av_list_t ** other, uint32_t * typemap,
   2031 				 int enabled, expand_state_t * state)
   2032 {
   2033 	avrule_t *cur;
   2034 
   2035 	cur = source_rules;
   2036 	while (cur) {
   2037 		if (convert_and_expand_rule(state->handle, dest_pol,
   2038 					    typemap, cur, dest_avtab,
   2039 					    list, other, enabled,
   2040 					    0) != EXPAND_RULE_SUCCESS) {
   2041 			return -1;
   2042 		}
   2043 
   2044 		cur = cur->next;
   2045 	}
   2046 
   2047 	return 0;
   2048 }
   2049 
   2050 static int cond_node_map_bools(expand_state_t * state, cond_node_t * cn)
   2051 {
   2052 	cond_expr_t *cur;
   2053 	unsigned int i;
   2054 
   2055 	cur = cn->expr;
   2056 	while (cur) {
   2057 		if (cur->bool)
   2058 			cur->bool = state->boolmap[cur->bool - 1];
   2059 		cur = cur->next;
   2060 	}
   2061 
   2062 	for (i = 0; i < min(cn->nbools, COND_MAX_BOOLS); i++)
   2063 		cn->bool_ids[i] = state->boolmap[cn->bool_ids[i] - 1];
   2064 
   2065 	if (cond_normalize_expr(state->out, cn)) {
   2066 		ERR(state->handle, "Error while normalizing conditional");
   2067 		return -1;
   2068 	}
   2069 
   2070 	return 0;
   2071 }
   2072 
   2073 /* copy the nodes in *reverse* order -- the result is that the last
   2074  * given conditional appears first in the policy, so as to match the
   2075  * behavior of the upstream compiler */
   2076 static int cond_node_copy(expand_state_t * state, cond_node_t * cn)
   2077 {
   2078 	cond_node_t *new_cond, *tmp;
   2079 
   2080 	if (cn == NULL) {
   2081 		return 0;
   2082 	}
   2083 	if (cond_node_copy(state, cn->next)) {
   2084 		return -1;
   2085 	}
   2086 
   2087 	/* If current cond_node_t is of tunable, its effective branch
   2088 	 * has been appended to its home decl->avrules list during link
   2089 	 * and now we should just skip it. */
   2090 	if (cn->flags & COND_NODE_FLAGS_TUNABLE)
   2091 		return 0;
   2092 
   2093 	if (cond_normalize_expr(state->base, cn)) {
   2094 		ERR(state->handle, "Error while normalizing conditional");
   2095 		return -1;
   2096 	}
   2097 
   2098 	/* create a new temporary conditional node with the booleans
   2099 	 * mapped */
   2100 	tmp = cond_node_create(state->base, cn);
   2101 	if (!tmp) {
   2102 		ERR(state->handle, "Out of memory");
   2103 		return -1;
   2104 	}
   2105 
   2106 	if (cond_node_map_bools(state, tmp)) {
   2107 		cond_node_destroy(tmp);
   2108 		free(tmp);
   2109 		ERR(state->handle, "Error mapping booleans");
   2110 		return -1;
   2111 	}
   2112 
   2113 	new_cond = cond_node_search(state->out, state->out->cond_list, tmp);
   2114 	if (!new_cond) {
   2115 		cond_node_destroy(tmp);
   2116 		free(tmp);
   2117 		ERR(state->handle, "Out of memory!");
   2118 		return -1;
   2119 	}
   2120 	cond_node_destroy(tmp);
   2121 	free(tmp);
   2122 
   2123 	if (cond_avrule_list_copy
   2124 	    (state->out, cn->avtrue_list, &state->out->te_cond_avtab,
   2125 	     &new_cond->true_list, &new_cond->false_list, state->typemap,
   2126 	     new_cond->cur_state, state))
   2127 		return -1;
   2128 	if (cond_avrule_list_copy
   2129 	    (state->out, cn->avfalse_list, &state->out->te_cond_avtab,
   2130 	     &new_cond->false_list, &new_cond->true_list, state->typemap,
   2131 	     !new_cond->cur_state, state))
   2132 		return -1;
   2133 
   2134 	return 0;
   2135 }
   2136 
   2137 static int context_copy(context_struct_t * dst, context_struct_t * src,
   2138 			expand_state_t * state)
   2139 {
   2140 	dst->user = state->usermap[src->user - 1];
   2141 	dst->role = state->rolemap[src->role - 1];
   2142 	dst->type = state->typemap[src->type - 1];
   2143 	return mls_context_cpy(dst, src);
   2144 }
   2145 
   2146 static int ocontext_copy_xen(expand_state_t *state)
   2147 {
   2148 	unsigned int i;
   2149 	ocontext_t *c, *n, *l;
   2150 
   2151 	for (i = 0; i < OCON_NUM; i++) {
   2152 		l = NULL;
   2153 		for (c = state->base->ocontexts[i]; c; c = c->next) {
   2154 			n = malloc(sizeof(ocontext_t));
   2155 			if (!n) {
   2156 				ERR(state->handle, "Out of memory!");
   2157 				return -1;
   2158 			}
   2159 			memset(n, 0, sizeof(ocontext_t));
   2160 			if (l)
   2161 				l->next = n;
   2162 			else
   2163 				state->out->ocontexts[i] = n;
   2164 			l = n;
   2165 			switch (i) {
   2166 			case OCON_XEN_ISID:
   2167 				if (c->context[0].user == 0) {
   2168 					ERR(state->handle,
   2169 					    "Missing context for %s initial sid",
   2170 					    c->u.name);
   2171 					return -1;
   2172 				}
   2173 				n->sid[0] = c->sid[0];
   2174 				break;
   2175 			case OCON_XEN_PIRQ:
   2176 				n->u.pirq = c->u.pirq;
   2177 				break;
   2178 			case OCON_XEN_IOPORT:
   2179 				n->u.ioport.low_ioport = c->u.ioport.low_ioport;
   2180 				n->u.ioport.high_ioport =
   2181 					c->u.ioport.high_ioport;
   2182 				break;
   2183 			case OCON_XEN_IOMEM:
   2184 				n->u.iomem.low_iomem  = c->u.iomem.low_iomem;
   2185 				n->u.iomem.high_iomem = c->u.iomem.high_iomem;
   2186 				break;
   2187 			case OCON_XEN_PCIDEVICE:
   2188 				n->u.device = c->u.device;
   2189 				break;
   2190 			default:
   2191 				/* shouldn't get here */
   2192 				ERR(state->handle, "Unknown ocontext");
   2193 				return -1;
   2194 			}
   2195 			if (context_copy(&n->context[0], &c->context[0],
   2196 				state)) {
   2197 				ERR(state->handle, "Out of memory!");
   2198 				return -1;
   2199 			}
   2200 		}
   2201 	}
   2202 	return 0;
   2203 }
   2204 
   2205 static int ocontext_copy_selinux(expand_state_t *state)
   2206 {
   2207 	unsigned int i, j;
   2208 	ocontext_t *c, *n, *l;
   2209 
   2210 	for (i = 0; i < OCON_NUM; i++) {
   2211 		l = NULL;
   2212 		for (c = state->base->ocontexts[i]; c; c = c->next) {
   2213 			n = malloc(sizeof(ocontext_t));
   2214 			if (!n) {
   2215 				ERR(state->handle, "Out of memory!");
   2216 				return -1;
   2217 			}
   2218 			memset(n, 0, sizeof(ocontext_t));
   2219 			if (l)
   2220 				l->next = n;
   2221 			else
   2222 				state->out->ocontexts[i] = n;
   2223 			l = n;
   2224 			switch (i) {
   2225 			case OCON_ISID:
   2226 				if (c->context[0].user == 0) {
   2227 					ERR(state->handle,
   2228 					    "Missing context for %s initial sid",
   2229 					    c->u.name);
   2230 					return -1;
   2231 				}
   2232 				n->sid[0] = c->sid[0];
   2233 				break;
   2234 			case OCON_FS:	/* FALLTHROUGH */
   2235 			case OCON_NETIF:
   2236 				n->u.name = strdup(c->u.name);
   2237 				if (!n->u.name) {
   2238 					ERR(state->handle, "Out of memory!");
   2239 					return -1;
   2240 				}
   2241 				if (context_copy
   2242 				    (&n->context[1], &c->context[1], state)) {
   2243 					ERR(state->handle, "Out of memory!");
   2244 					return -1;
   2245 				}
   2246 				break;
   2247 			case OCON_PORT:
   2248 				n->u.port.protocol = c->u.port.protocol;
   2249 				n->u.port.low_port = c->u.port.low_port;
   2250 				n->u.port.high_port = c->u.port.high_port;
   2251 				break;
   2252 			case OCON_NODE:
   2253 				n->u.node.addr = c->u.node.addr;
   2254 				n->u.node.mask = c->u.node.mask;
   2255 				break;
   2256 			case OCON_FSUSE:
   2257 				n->v.behavior = c->v.behavior;
   2258 				n->u.name = strdup(c->u.name);
   2259 				if (!n->u.name) {
   2260 					ERR(state->handle, "Out of memory!");
   2261 					return -1;
   2262 				}
   2263 				break;
   2264 			case OCON_NODE6:
   2265 				for (j = 0; j < 4; j++)
   2266 					n->u.node6.addr[j] = c->u.node6.addr[j];
   2267 				for (j = 0; j < 4; j++)
   2268 					n->u.node6.mask[j] = c->u.node6.mask[j];
   2269 				break;
   2270 			default:
   2271 				/* shouldn't get here */
   2272 				ERR(state->handle, "Unknown ocontext");
   2273 				return -1;
   2274 			}
   2275 			if (context_copy(&n->context[0], &c->context[0], state)) {
   2276 				ERR(state->handle, "Out of memory!");
   2277 				return -1;
   2278 			}
   2279 		}
   2280 	}
   2281 	return 0;
   2282 }
   2283 
   2284 static int ocontext_copy(expand_state_t *state, uint32_t target)
   2285 {
   2286 	int rc = -1;
   2287 	switch (target) {
   2288 	case SEPOL_TARGET_SELINUX:
   2289 		rc = ocontext_copy_selinux(state);
   2290 		break;
   2291 	case SEPOL_TARGET_XEN:
   2292 		rc = ocontext_copy_xen(state);
   2293 		break;
   2294 	default:
   2295 		ERR(state->handle, "Unknown target");
   2296 		return -1;
   2297 	}
   2298 	return rc;
   2299 }
   2300 
   2301 static int genfs_copy(expand_state_t * state)
   2302 {
   2303 	ocontext_t *c, *newc, *l;
   2304 	genfs_t *genfs, *newgenfs, *end;
   2305 
   2306 	end = NULL;
   2307 	for (genfs = state->base->genfs; genfs; genfs = genfs->next) {
   2308 		newgenfs = malloc(sizeof(genfs_t));
   2309 		if (!newgenfs) {
   2310 			ERR(state->handle, "Out of memory!");
   2311 			return -1;
   2312 		}
   2313 		memset(newgenfs, 0, sizeof(genfs_t));
   2314 		newgenfs->fstype = strdup(genfs->fstype);
   2315 		if (!newgenfs->fstype) {
   2316 			free(newgenfs);
   2317 			ERR(state->handle, "Out of memory!");
   2318 			return -1;
   2319 		}
   2320 		if (!end)
   2321 			state->out->genfs = newgenfs;
   2322 		else
   2323 			end->next = newgenfs;
   2324 		end = newgenfs;
   2325 
   2326 		l = NULL;
   2327 		for (c = genfs->head; c; c = c->next) {
   2328 			newc = malloc(sizeof(ocontext_t));
   2329 			if (!newc) {
   2330 				ERR(state->handle, "Out of memory!");
   2331 				return -1;
   2332 			}
   2333 			memset(newc, 0, sizeof(ocontext_t));
   2334 			newc->u.name = strdup(c->u.name);
   2335 			if (!newc->u.name) {
   2336 				ERR(state->handle, "Out of memory!");
   2337 				free(newc);
   2338 				return -1;
   2339 			}
   2340 			newc->v.sclass = c->v.sclass;
   2341 			context_copy(&newc->context[0], &c->context[0], state);
   2342 			if (l)
   2343 				l->next = newc;
   2344 			else
   2345 				newgenfs->head = newc;
   2346 			l = newc;
   2347 		}
   2348 	}
   2349 	return 0;
   2350 }
   2351 
   2352 static int type_attr_map(hashtab_key_t key
   2353 			 __attribute__ ((unused)), hashtab_datum_t datum,
   2354 			 void *ptr)
   2355 {
   2356 	type_datum_t *type;
   2357 	expand_state_t *state = ptr;
   2358 	policydb_t *p = state->out;
   2359 	unsigned int i;
   2360 	ebitmap_node_t *tnode;
   2361 
   2362 	type = (type_datum_t *) datum;
   2363 	if (type->flavor == TYPE_ATTRIB) {
   2364 		if (ebitmap_cpy(&p->attr_type_map[type->s.value - 1],
   2365 				&type->types)) {
   2366 			ERR(state->handle, "Out of memory!");
   2367 			return -1;
   2368 		}
   2369 		ebitmap_for_each_bit(&type->types, tnode, i) {
   2370 			if (!ebitmap_node_get_bit(tnode, i))
   2371 				continue;
   2372 			if (ebitmap_set_bit(&p->type_attr_map[i],
   2373 					    type->s.value - 1, 1)) {
   2374 				ERR(state->handle, "Out of memory!");
   2375 				return -1;
   2376 			}
   2377 		}
   2378 	}
   2379 	return 0;
   2380 }
   2381 
   2382 /* converts typeset using typemap and expands into ebitmap_t types using the attributes in the passed in policy.
   2383  * this should not be called until after all the blocks have been processed and the attributes in target policy
   2384  * are complete. */
   2385 int expand_convert_type_set(policydb_t * p, uint32_t * typemap,
   2386 			    type_set_t * set, ebitmap_t * types,
   2387 			    unsigned char alwaysexpand)
   2388 {
   2389 	type_set_t tmpset;
   2390 
   2391 	type_set_init(&tmpset);
   2392 
   2393 	if (map_ebitmap(&set->types, &tmpset.types, typemap))
   2394 		return -1;
   2395 
   2396 	if (map_ebitmap(&set->negset, &tmpset.negset, typemap))
   2397 		return -1;
   2398 
   2399 	tmpset.flags = set->flags;
   2400 
   2401 	if (type_set_expand(&tmpset, types, p, alwaysexpand))
   2402 		return -1;
   2403 
   2404 	type_set_destroy(&tmpset);
   2405 
   2406 	return 0;
   2407 }
   2408 
   2409 /* Expand a rule into a given avtab - checking for conflicting type
   2410  * rules.  Return 1 on success, 0 if the rule conflicts with something
   2411  * (and hence was not added), or -1 on error. */
   2412 int expand_rule(sepol_handle_t * handle,
   2413 		policydb_t * source_pol,
   2414 		avrule_t * source_rule, avtab_t * dest_avtab,
   2415 		cond_av_list_t ** cond, cond_av_list_t ** other, int enabled)
   2416 {
   2417 	int retval;
   2418 	ebitmap_t stypes, ttypes;
   2419 
   2420 	if (source_rule->specified & AVRULE_NEVERALLOW)
   2421 		return 1;
   2422 
   2423 	ebitmap_init(&stypes);
   2424 	ebitmap_init(&ttypes);
   2425 
   2426 	if (type_set_expand(&source_rule->stypes, &stypes, source_pol, 1))
   2427 		return -1;
   2428 	if (type_set_expand(&source_rule->ttypes, &ttypes, source_pol, 1))
   2429 		return -1;
   2430 	retval = expand_rule_helper(handle, source_pol, NULL,
   2431 				    source_rule, dest_avtab,
   2432 				    cond, other, enabled, &stypes, &ttypes);
   2433 	ebitmap_destroy(&stypes);
   2434 	ebitmap_destroy(&ttypes);
   2435 	return retval;
   2436 }
   2437 
   2438 /* Expand a role set into an ebitmap containing the roles.
   2439  * This handles the attribute and flags.
   2440  * Attribute expansion depends on if the rolemap is available.
   2441  * During module compile the rolemap is not available, the
   2442  * possible duplicates of a regular role and the role attribute
   2443  * the regular role belongs to could be properly handled by
   2444  * copy_role_trans and copy_role_allow.
   2445  */
   2446 int role_set_expand(role_set_t * x, ebitmap_t * r, policydb_t * out, policydb_t * base, uint32_t * rolemap)
   2447 {
   2448 	unsigned int i;
   2449 	ebitmap_node_t *rnode;
   2450 	ebitmap_t mapped_roles, roles;
   2451 	policydb_t *p = out;
   2452 	role_datum_t *role;
   2453 
   2454 	ebitmap_init(r);
   2455 
   2456 	if (x->flags & ROLE_STAR) {
   2457 		for (i = 0; i < p->p_roles.nprim++; i++)
   2458 			if (ebitmap_set_bit(r, i, 1))
   2459 				return -1;
   2460 		return 0;
   2461 	}
   2462 
   2463 	ebitmap_init(&mapped_roles);
   2464 	ebitmap_init(&roles);
   2465 
   2466 	if (rolemap) {
   2467 		assert(base != NULL);
   2468 		ebitmap_for_each_bit(&x->roles, rnode, i) {
   2469 			if (ebitmap_node_get_bit(rnode, i)) {
   2470 				/* take advantage of p_role_val_to_struct[]
   2471 				 * of the base module */
   2472 				role = base->role_val_to_struct[i];
   2473 				assert(role != NULL);
   2474 				if (role->flavor == ROLE_ATTRIB) {
   2475 					if (ebitmap_union(&roles,
   2476 							  &role->roles))
   2477 						goto bad;
   2478 				} else {
   2479 					if (ebitmap_set_bit(&roles, i, 1))
   2480 						goto bad;
   2481 				}
   2482 			}
   2483 		}
   2484 		if (map_ebitmap(&roles, &mapped_roles, rolemap))
   2485 			goto bad;
   2486 	} else {
   2487 		if (ebitmap_cpy(&mapped_roles, &x->roles))
   2488 			goto bad;
   2489 	}
   2490 
   2491 	ebitmap_for_each_bit(&mapped_roles, rnode, i) {
   2492 		if (ebitmap_node_get_bit(rnode, i)) {
   2493 			if (ebitmap_set_bit(r, i, 1))
   2494 				goto bad;
   2495 		}
   2496 	}
   2497 
   2498 	ebitmap_destroy(&mapped_roles);
   2499 	ebitmap_destroy(&roles);
   2500 
   2501 	/* if role is to be complimented, invert the entire bitmap here */
   2502 	if (x->flags & ROLE_COMP) {
   2503 		for (i = 0; i < ebitmap_length(r); i++) {
   2504 			if (ebitmap_get_bit(r, i)) {
   2505 				if (ebitmap_set_bit(r, i, 0))
   2506 					return -1;
   2507 			} else {
   2508 				if (ebitmap_set_bit(r, i, 1))
   2509 					return -1;
   2510 			}
   2511 		}
   2512 	}
   2513 	return 0;
   2514 
   2515 bad:
   2516 	ebitmap_destroy(&mapped_roles);
   2517 	ebitmap_destroy(&roles);
   2518 	return -1;
   2519 }
   2520 
   2521 /* Expand a type set into an ebitmap containing the types. This
   2522  * handles the negset, attributes, and flags.
   2523  * Attribute expansion depends on several factors:
   2524  * - if alwaysexpand is 1, then they will be expanded,
   2525  * - if the type set has a negset or flags, then they will be expanded,
   2526  * - otherwise, they will not be expanded.
   2527  */
   2528 int type_set_expand(type_set_t * set, ebitmap_t * t, policydb_t * p,
   2529 		    unsigned char alwaysexpand)
   2530 {
   2531 	unsigned int i;
   2532 	ebitmap_t types, neg_types;
   2533 	ebitmap_node_t *tnode;
   2534 
   2535 	ebitmap_init(&types);
   2536 	ebitmap_init(t);
   2537 
   2538 	if (alwaysexpand || ebitmap_length(&set->negset) || set->flags) {
   2539 		/* First go through the types and OR all the attributes to types */
   2540 		ebitmap_for_each_bit(&set->types, tnode, i) {
   2541 			if (ebitmap_node_get_bit(tnode, i)) {
   2542 				if (p->type_val_to_struct[i]->flavor ==
   2543 				    TYPE_ATTRIB) {
   2544 					if (ebitmap_union
   2545 					    (&types,
   2546 					     &p->type_val_to_struct[i]->
   2547 					     types)) {
   2548 						return -1;
   2549 					}
   2550 				} else {
   2551 					if (ebitmap_set_bit(&types, i, 1)) {
   2552 						return -1;
   2553 					}
   2554 				}
   2555 			}
   2556 		}
   2557 	} else {
   2558 		/* No expansion of attributes, just copy the set as is. */
   2559 		if (ebitmap_cpy(&types, &set->types))
   2560 			return -1;
   2561 	}
   2562 
   2563 	/* Now do the same thing for negset */
   2564 	ebitmap_init(&neg_types);
   2565 	ebitmap_for_each_bit(&set->negset, tnode, i) {
   2566 		if (ebitmap_node_get_bit(tnode, i)) {
   2567 			if (p->type_val_to_struct[i] &&
   2568 			    p->type_val_to_struct[i]->flavor == TYPE_ATTRIB) {
   2569 				if (ebitmap_union
   2570 				    (&neg_types,
   2571 				     &p->type_val_to_struct[i]->types)) {
   2572 					return -1;
   2573 				}
   2574 			} else {
   2575 				if (ebitmap_set_bit(&neg_types, i, 1)) {
   2576 					return -1;
   2577 				}
   2578 			}
   2579 		}
   2580 	}
   2581 
   2582 	if (set->flags & TYPE_STAR) {
   2583 		/* set all types not in neg_types */
   2584 		for (i = 0; i < p->p_types.nprim; i++) {
   2585 			if (ebitmap_get_bit(&neg_types, i))
   2586 				continue;
   2587 			if (p->type_val_to_struct[i] &&
   2588 			    p->type_val_to_struct[i]->flavor == TYPE_ATTRIB)
   2589 				continue;
   2590 			if (ebitmap_set_bit(t, i, 1))
   2591 				return -1;
   2592 		}
   2593 		goto out;
   2594 	}
   2595 
   2596 	ebitmap_for_each_bit(&types, tnode, i) {
   2597 		if (ebitmap_node_get_bit(tnode, i)
   2598 		    && (!ebitmap_get_bit(&neg_types, i)))
   2599 			if (ebitmap_set_bit(t, i, 1))
   2600 				return -1;
   2601 	}
   2602 
   2603 	if (set->flags & TYPE_COMP) {
   2604 		for (i = 0; i < p->p_types.nprim; i++) {
   2605 			if (p->type_val_to_struct[i] &&
   2606 			    p->type_val_to_struct[i]->flavor == TYPE_ATTRIB) {
   2607 				assert(!ebitmap_get_bit(t, i));
   2608 				continue;
   2609 			}
   2610 			if (ebitmap_get_bit(t, i)) {
   2611 				if (ebitmap_set_bit(t, i, 0))
   2612 					return -1;
   2613 			} else {
   2614 				if (ebitmap_set_bit(t, i, 1))
   2615 					return -1;
   2616 			}
   2617 		}
   2618 	}
   2619 
   2620       out:
   2621 
   2622 	ebitmap_destroy(&types);
   2623 	ebitmap_destroy(&neg_types);
   2624 
   2625 	return 0;
   2626 }
   2627 
   2628 static int copy_neverallow(policydb_t * dest_pol, uint32_t * typemap,
   2629 			   avrule_t * source_rule)
   2630 {
   2631 	ebitmap_t stypes, ttypes;
   2632 	avrule_t *avrule;
   2633 	class_perm_node_t *cur_perm, *new_perm, *tail_perm;
   2634 
   2635 	ebitmap_init(&stypes);
   2636 	ebitmap_init(&ttypes);
   2637 
   2638 	if (expand_convert_type_set
   2639 	    (dest_pol, typemap, &source_rule->stypes, &stypes, 1))
   2640 		return -1;
   2641 	if (expand_convert_type_set
   2642 	    (dest_pol, typemap, &source_rule->ttypes, &ttypes, 1))
   2643 		return -1;
   2644 
   2645 	avrule = (avrule_t *) malloc(sizeof(avrule_t));
   2646 	if (!avrule)
   2647 		return -1;
   2648 
   2649 	avrule_init(avrule);
   2650 	avrule->specified = AVRULE_NEVERALLOW;
   2651 	avrule->line = source_rule->line;
   2652 	avrule->flags = source_rule->flags;
   2653 	avrule->source_line = source_rule->source_line;
   2654 	if (source_rule->source_filename) {
   2655 		avrule->source_filename = strdup(source_rule->source_filename);
   2656 		if (!avrule->source_filename)
   2657 			goto err;
   2658 	}
   2659 
   2660 	if (ebitmap_cpy(&avrule->stypes.types, &stypes))
   2661 		goto err;
   2662 
   2663 	if (ebitmap_cpy(&avrule->ttypes.types, &ttypes))
   2664 		goto err;
   2665 
   2666 	cur_perm = source_rule->perms;
   2667 	tail_perm = NULL;
   2668 	while (cur_perm) {
   2669 		new_perm =
   2670 		    (class_perm_node_t *) malloc(sizeof(class_perm_node_t));
   2671 		if (!new_perm)
   2672 			goto err;
   2673 		class_perm_node_init(new_perm);
   2674 		new_perm->class = cur_perm->class;
   2675 		assert(new_perm->class);
   2676 
   2677 		/* once we have modules with permissions we'll need to map the permissions (and classes) */
   2678 		new_perm->data = cur_perm->data;
   2679 
   2680 		if (!avrule->perms)
   2681 			avrule->perms = new_perm;
   2682 
   2683 		if (tail_perm)
   2684 			tail_perm->next = new_perm;
   2685 		tail_perm = new_perm;
   2686 		cur_perm = cur_perm->next;
   2687 	}
   2688 
   2689 	/* just prepend the avrule to the first branch; it'll never be
   2690 	   written to disk */
   2691 	if (!dest_pol->global->branch_list->avrules)
   2692 		dest_pol->global->branch_list->avrules = avrule;
   2693 	else {
   2694 		avrule->next = dest_pol->global->branch_list->avrules;
   2695 		dest_pol->global->branch_list->avrules = avrule;
   2696 	}
   2697 
   2698 	ebitmap_destroy(&stypes);
   2699 	ebitmap_destroy(&ttypes);
   2700 
   2701 	return 0;
   2702 
   2703       err:
   2704 	ebitmap_destroy(&stypes);
   2705 	ebitmap_destroy(&ttypes);
   2706 	ebitmap_destroy(&avrule->stypes.types);
   2707 	ebitmap_destroy(&avrule->ttypes.types);
   2708 	cur_perm = avrule->perms;
   2709 	while (cur_perm) {
   2710 		tail_perm = cur_perm->next;
   2711 		free(cur_perm);
   2712 		cur_perm = tail_perm;
   2713 	}
   2714 	free(avrule);
   2715 	return -1;
   2716 }
   2717 
   2718 /*
   2719  * Expands the avrule blocks for a policy. RBAC rules are copied. Neverallow
   2720  * rules are copied or expanded as per the settings in the state object; all
   2721  * other AV rules are expanded.  If neverallow rules are expanded, they are not
   2722  * copied, otherwise they are copied for later use by the assertion checker.
   2723  */
   2724 static int copy_and_expand_avrule_block(expand_state_t * state)
   2725 {
   2726 	avrule_block_t *curblock = state->base->global;
   2727 	avrule_block_t *prevblock;
   2728 	int retval = -1;
   2729 
   2730 	if (avtab_alloc(&state->out->te_avtab, MAX_AVTAB_SIZE)) {
   2731  		ERR(state->handle, "Out of Memory!");
   2732  		return -1;
   2733  	}
   2734 
   2735  	if (avtab_alloc(&state->out->te_cond_avtab, MAX_AVTAB_SIZE)) {
   2736  		ERR(state->handle, "Out of Memory!");
   2737  		return -1;
   2738  	}
   2739 
   2740 	while (curblock) {
   2741 		avrule_decl_t *decl = curblock->enabled;
   2742 		avrule_t *cur_avrule;
   2743 
   2744 		if (decl == NULL) {
   2745 			/* nothing was enabled within this block */
   2746 			goto cont;
   2747 		}
   2748 
   2749 		/* copy role allows and role trans */
   2750 		if (copy_role_allows(state, decl->role_allow_rules) != 0 ||
   2751 		    copy_role_trans(state, decl->role_tr_rules) != 0) {
   2752 			goto cleanup;
   2753 		}
   2754 
   2755 		if (expand_filename_trans(state, decl->filename_trans_rules))
   2756 			goto cleanup;
   2757 
   2758 		/* expand the range transition rules */
   2759 		if (expand_range_trans(state, decl->range_tr_rules))
   2760 			goto cleanup;
   2761 
   2762 		/* copy rules */
   2763 		cur_avrule = decl->avrules;
   2764 		while (cur_avrule != NULL) {
   2765 			if (!(state->expand_neverallow)
   2766 			    && cur_avrule->specified & AVRULE_NEVERALLOW) {
   2767 				/* copy this over directly so that assertions are checked later */
   2768 				if (copy_neverallow
   2769 				    (state->out, state->typemap, cur_avrule))
   2770 					ERR(state->handle,
   2771 					    "Error while copying neverallow.");
   2772 			} else {
   2773 				if (cur_avrule->specified & AVRULE_NEVERALLOW) {
   2774 					state->out->unsupported_format = 1;
   2775 				}
   2776 				if (convert_and_expand_rule
   2777 				    (state->handle, state->out, state->typemap,
   2778 				     cur_avrule, &state->out->te_avtab, NULL,
   2779 				     NULL, 0,
   2780 				     state->expand_neverallow) !=
   2781 				    EXPAND_RULE_SUCCESS) {
   2782 					goto cleanup;
   2783 				}
   2784 			}
   2785 			cur_avrule = cur_avrule->next;
   2786 		}
   2787 
   2788 		/* copy conditional rules */
   2789 		if (cond_node_copy(state, decl->cond_list))
   2790 			goto cleanup;
   2791 
   2792       cont:
   2793 		prevblock = curblock;
   2794 		curblock = curblock->next;
   2795 
   2796 		if (state->handle && state->handle->expand_consume_base) {
   2797 			/* set base top avrule block in case there
   2798  			 * is an error condition and the policy needs
   2799  			 * to be destroyed */
   2800 			state->base->global = curblock;
   2801 			avrule_block_destroy(prevblock);
   2802 		}
   2803 	}
   2804 
   2805 	retval = 0;
   2806 
   2807       cleanup:
   2808 	return retval;
   2809 }
   2810 
   2811 /*
   2812  * This function allows external users of the library (such as setools) to
   2813  * expand only the avrules and optionally perform expansion of neverallow rules
   2814  * or expand into the same policy for analysis purposes.
   2815  */
   2816 int expand_module_avrules(sepol_handle_t * handle, policydb_t * base,
   2817 			  policydb_t * out, uint32_t * typemap,
   2818 			  uint32_t * boolmap, uint32_t * rolemap,
   2819 			  uint32_t * usermap, int verbose,
   2820 			  int expand_neverallow)
   2821 {
   2822 	expand_state_t state;
   2823 
   2824 	expand_state_init(&state);
   2825 
   2826 	state.base = base;
   2827 	state.out = out;
   2828 	state.typemap = typemap;
   2829 	state.boolmap = boolmap;
   2830 	state.rolemap = rolemap;
   2831 	state.usermap = usermap;
   2832 	state.handle = handle;
   2833 	state.verbose = verbose;
   2834 	state.expand_neverallow = expand_neverallow;
   2835 
   2836 	return copy_and_expand_avrule_block(&state);
   2837 }
   2838 
   2839 static void discard_tunables(sepol_handle_t *sh, policydb_t *pol)
   2840 {
   2841 	avrule_block_t *block;
   2842 	avrule_decl_t *decl;
   2843 	cond_node_t *cur_node;
   2844 	cond_expr_t *cur_expr;
   2845 	int cur_state, preserve_tunables = 0;
   2846 	avrule_t *tail, *to_be_appended;
   2847 
   2848 	if (sh && sh->preserve_tunables)
   2849 		preserve_tunables = 1;
   2850 
   2851 	/* Iterate through all cond_node of all enabled decls, if a cond_node
   2852 	 * is about tunable, calculate its state value and concatenate one of
   2853 	 * its avrule list to the current decl->avrules list. On the other
   2854 	 * hand, the disabled unused branch of a tunable would be discarded.
   2855 	 *
   2856 	 * Note, such tunable cond_node would be skipped over in expansion,
   2857 	 * so we won't have to worry about removing it from decl->cond_list
   2858 	 * here :-)
   2859 	 *
   2860 	 * If tunables are requested to be preserved then they would be
   2861 	 * "transformed" as booleans by having their TUNABLE flag cleared.
   2862 	 */
   2863 	for (block = pol->global; block != NULL; block = block->next) {
   2864 		decl = block->enabled;
   2865 		if (decl == NULL || decl->enabled == 0)
   2866 			continue;
   2867 
   2868 		tail = decl->avrules;
   2869 		while (tail && tail->next)
   2870 			tail = tail->next;
   2871 
   2872 		for (cur_node = decl->cond_list; cur_node != NULL;
   2873 		     cur_node = cur_node->next) {
   2874 			int booleans, tunables, i;
   2875 			cond_bool_datum_t *booldatum;
   2876 			cond_bool_datum_t *tmp[COND_EXPR_MAXDEPTH];
   2877 
   2878 			booleans = tunables = 0;
   2879 			memset(tmp, 0, sizeof(cond_bool_datum_t *) * COND_EXPR_MAXDEPTH);
   2880 
   2881 			for (cur_expr = cur_node->expr; cur_expr != NULL;
   2882 			     cur_expr = cur_expr->next) {
   2883 				if (cur_expr->expr_type != COND_BOOL)
   2884 					continue;
   2885 				booldatum = pol->bool_val_to_struct[cur_expr->bool - 1];
   2886 				if (booldatum->flags & COND_BOOL_FLAGS_TUNABLE)
   2887 					tmp[tunables++] = booldatum;
   2888 				else
   2889 					booleans++;
   2890 			}
   2891 
   2892 			/* bool_copy_callback() at link phase has ensured
   2893 			 * that no mixture of tunables and booleans in one
   2894 			 * expression. However, this would be broken by the
   2895 			 * request to preserve tunables */
   2896 			if (!preserve_tunables)
   2897 				assert(!(booleans && tunables));
   2898 
   2899 			if (booleans || preserve_tunables) {
   2900 				cur_node->flags &= ~COND_NODE_FLAGS_TUNABLE;
   2901 				if (tunables) {
   2902 					for (i = 0; i < tunables; i++)
   2903 						tmp[i]->flags &= ~COND_BOOL_FLAGS_TUNABLE;
   2904 				}
   2905 			} else {
   2906 				cur_node->flags |= COND_NODE_FLAGS_TUNABLE;
   2907 				cur_state = cond_evaluate_expr(pol, cur_node->expr);
   2908 				if (cur_state == -1) {
   2909 					printf("Expression result was "
   2910 					       "undefined, skipping all"
   2911 					       "rules\n");
   2912 					continue;
   2913 				}
   2914 
   2915 				to_be_appended = (cur_state == 1) ?
   2916 					cur_node->avtrue_list : cur_node->avfalse_list;
   2917 
   2918 				if (tail)
   2919 					tail->next = to_be_appended;
   2920 				else
   2921 					tail = decl->avrules = to_be_appended;
   2922 
   2923 				/* Now that the effective branch has been
   2924 				 * appended, neutralize its original pointer */
   2925 				if (cur_state == 1)
   2926 					cur_node->avtrue_list = NULL;
   2927 				else
   2928 					cur_node->avfalse_list = NULL;
   2929 
   2930 				/* Update the tail of decl->avrules for
   2931 				 * further concatenation */
   2932 				while (tail && tail->next)
   2933 					tail = tail->next;
   2934 			}
   2935 		}
   2936 	}
   2937 }
   2938 
   2939 /* Linking should always be done before calling expand, even if
   2940  * there is only a base since all optionals are dealt with at link time
   2941  * the base passed in should be indexed and avrule blocks should be
   2942  * enabled.
   2943  */
   2944 int expand_module(sepol_handle_t * handle,
   2945 		  policydb_t * base, policydb_t * out, int verbose, int check)
   2946 {
   2947 	int retval = -1;
   2948 	unsigned int i;
   2949 	expand_state_t state;
   2950 	avrule_block_t *curblock;
   2951 
   2952 	/* Append tunable's avtrue_list or avfalse_list to the avrules list
   2953 	 * of its home decl depending on its state value, so that the effect
   2954 	 * rules of a tunable would be added to te_avtab permanently. Whereas
   2955 	 * the disabled unused branch would be discarded.
   2956 	 *
   2957 	 * Originally this function is called at the very end of link phase,
   2958 	 * however, we need to keep the linked policy intact for analysis
   2959 	 * purpose. */
   2960 	discard_tunables(handle, base);
   2961 
   2962 	expand_state_init(&state);
   2963 
   2964 	state.verbose = verbose;
   2965 	state.typemap = NULL;
   2966 	state.base = base;
   2967 	state.out = out;
   2968 	state.handle = handle;
   2969 
   2970 	if (base->policy_type != POLICY_BASE) {
   2971 		ERR(handle, "Target of expand was not a base policy.");
   2972 		return -1;
   2973 	}
   2974 
   2975 	state.out->policy_type = POLICY_KERN;
   2976 	state.out->policyvers = POLICYDB_VERSION_MAX;
   2977 
   2978 	/* Copy mls state from base to out */
   2979 	out->mls = base->mls;
   2980 	out->handle_unknown = base->handle_unknown;
   2981 
   2982 	/* Copy target from base to out */
   2983 	out->target_platform = base->target_platform;
   2984 
   2985 	/* Copy policy capabilities */
   2986 	if (ebitmap_cpy(&out->policycaps, &base->policycaps)) {
   2987 		ERR(handle, "Out of memory!");
   2988 		goto cleanup;
   2989 	}
   2990 
   2991 	if ((state.typemap =
   2992 	     (uint32_t *) calloc(state.base->p_types.nprim,
   2993 				 sizeof(uint32_t))) == NULL) {
   2994 		ERR(handle, "Out of memory!");
   2995 		goto cleanup;
   2996 	}
   2997 
   2998 	state.boolmap = (uint32_t *)calloc(state.base->p_bools.nprim, sizeof(uint32_t));
   2999 	if (!state.boolmap) {
   3000 		ERR(handle, "Out of memory!");
   3001 		goto cleanup;
   3002 	}
   3003 
   3004 	state.rolemap = (uint32_t *)calloc(state.base->p_roles.nprim, sizeof(uint32_t));
   3005 	if (!state.rolemap) {
   3006 		ERR(handle, "Out of memory!");
   3007 		goto cleanup;
   3008 	}
   3009 
   3010 	state.usermap = (uint32_t *)calloc(state.base->p_users.nprim, sizeof(uint32_t));
   3011 	if (!state.usermap) {
   3012 		ERR(handle, "Out of memory!");
   3013 		goto cleanup;
   3014 	}
   3015 
   3016 	/* order is important - types must be first */
   3017 
   3018 	/* copy types */
   3019 	if (hashtab_map(state.base->p_types.table, type_copy_callback, &state)) {
   3020 		goto cleanup;
   3021 	}
   3022 
   3023 	/* convert attribute type sets */
   3024 	if (hashtab_map
   3025 	    (state.base->p_types.table, attr_convert_callback, &state)) {
   3026 		goto cleanup;
   3027 	}
   3028 
   3029 	/* copy commons */
   3030 	if (hashtab_map
   3031 	    (state.base->p_commons.table, common_copy_callback, &state)) {
   3032 		goto cleanup;
   3033 	}
   3034 
   3035 	/* copy classes, note, this does not copy constraints, constraints can't be
   3036 	 * copied until after all the blocks have been processed and attributes are complete */
   3037 	if (hashtab_map
   3038 	    (state.base->p_classes.table, class_copy_callback, &state)) {
   3039 		goto cleanup;
   3040 	}
   3041 
   3042 	/* copy type bounds */
   3043 	if (hashtab_map(state.base->p_types.table,
   3044 			type_bounds_copy_callback, &state))
   3045 		goto cleanup;
   3046 
   3047 	/* copy aliases */
   3048 	if (hashtab_map(state.base->p_types.table, alias_copy_callback, &state))
   3049 		goto cleanup;
   3050 
   3051 	/* index here so that type indexes are available for role_copy_callback */
   3052 	if (policydb_index_others(handle, out, verbose)) {
   3053 		ERR(handle, "Error while indexing out symbols");
   3054 		goto cleanup;
   3055 	}
   3056 
   3057 	/* copy roles */
   3058 	if (hashtab_map(state.base->p_roles.table, role_copy_callback, &state))
   3059 		goto cleanup;
   3060 	if (hashtab_map(state.base->p_roles.table,
   3061 			role_bounds_copy_callback, &state))
   3062 		goto cleanup;
   3063 	/* escalate the type_set_t in a role attribute to all regular roles
   3064 	 * that belongs to it. */
   3065 	if (hashtab_map(state.base->p_roles.table, role_fix_callback, &state))
   3066 		goto cleanup;
   3067 
   3068 	/* copy MLS's sensitivity level and categories - this needs to be done
   3069 	 * before expanding users (they need to be indexed too) */
   3070 	if (hashtab_map(state.base->p_levels.table, sens_copy_callback, &state))
   3071 		goto cleanup;
   3072 	if (hashtab_map(state.base->p_cats.table, cats_copy_callback, &state))
   3073 		goto cleanup;
   3074 	if (policydb_index_others(handle, out, verbose)) {
   3075 		ERR(handle, "Error while indexing out symbols");
   3076 		goto cleanup;
   3077 	}
   3078 
   3079 	/* copy users */
   3080 	if (hashtab_map(state.base->p_users.table, user_copy_callback, &state))
   3081 		goto cleanup;
   3082 	if (hashtab_map(state.base->p_users.table,
   3083 			user_bounds_copy_callback, &state))
   3084 		goto cleanup;
   3085 
   3086 	/* copy bools */
   3087 	if (hashtab_map(state.base->p_bools.table, bool_copy_callback, &state))
   3088 		goto cleanup;
   3089 
   3090 	if (policydb_index_classes(out)) {
   3091 		ERR(handle, "Error while indexing out classes");
   3092 		goto cleanup;
   3093 	}
   3094 	if (policydb_index_others(handle, out, verbose)) {
   3095 		ERR(handle, "Error while indexing out symbols");
   3096 		goto cleanup;
   3097 	}
   3098 
   3099 	/* loop through all decls and union attributes, roles, users */
   3100 	for (curblock = state.base->global; curblock != NULL;
   3101 	     curblock = curblock->next) {
   3102 		avrule_decl_t *decl = curblock->enabled;
   3103 
   3104 		if (decl == NULL) {
   3105 			/* nothing was enabled within this block */
   3106 			continue;
   3107 		}
   3108 
   3109 		/* convert attribute type sets */
   3110 		if (hashtab_map
   3111 		    (decl->p_types.table, attr_convert_callback, &state)) {
   3112 			goto cleanup;
   3113 		}
   3114 
   3115 		/* copy roles */
   3116 		if (hashtab_map
   3117 		    (decl->p_roles.table, role_copy_callback, &state))
   3118 			goto cleanup;
   3119 
   3120 		/* copy users */
   3121 		if (hashtab_map
   3122 		    (decl->p_users.table, user_copy_callback, &state))
   3123 			goto cleanup;
   3124 
   3125 	}
   3126 
   3127 	/* remap role dominates bitmaps */
   3128 	 if (hashtab_map(state.out->p_roles.table, role_remap_dominates, &state)) {
   3129 		goto cleanup;
   3130 	}
   3131 
   3132 	if (copy_and_expand_avrule_block(&state) < 0) {
   3133 		ERR(handle, "Error during expand");
   3134 		goto cleanup;
   3135 	}
   3136 
   3137 	/* copy constraints */
   3138 	if (hashtab_map
   3139 	    (state.base->p_classes.table, constraint_copy_callback, &state)) {
   3140 		goto cleanup;
   3141 	}
   3142 
   3143 	cond_optimize_lists(state.out->cond_list);
   3144 	if (evaluate_conds(state.out))
   3145 		goto cleanup;
   3146 
   3147 	/* copy ocontexts */
   3148 	if (ocontext_copy(&state, out->target_platform))
   3149 		goto cleanup;
   3150 
   3151 	/* copy genfs */
   3152 	if (genfs_copy(&state))
   3153 		goto cleanup;
   3154 
   3155 	/* Build the type<->attribute maps and remove attributes. */
   3156 	state.out->attr_type_map = malloc(state.out->p_types.nprim *
   3157 					  sizeof(ebitmap_t));
   3158 	state.out->type_attr_map = malloc(state.out->p_types.nprim *
   3159 					  sizeof(ebitmap_t));
   3160 	if (!state.out->attr_type_map || !state.out->type_attr_map) {
   3161 		ERR(handle, "Out of memory!");
   3162 		goto cleanup;
   3163 	}
   3164 	for (i = 0; i < state.out->p_types.nprim; i++) {
   3165 		ebitmap_init(&state.out->type_attr_map[i]);
   3166 		ebitmap_init(&state.out->attr_type_map[i]);
   3167 		/* add the type itself as the degenerate case */
   3168 		if (ebitmap_set_bit(&state.out->type_attr_map[i], i, 1)) {
   3169 			ERR(handle, "Out of memory!");
   3170 			goto cleanup;
   3171 		}
   3172 	}
   3173 	if (hashtab_map(state.out->p_types.table, type_attr_map, &state))
   3174 		goto cleanup;
   3175 	if (check) {
   3176 		if (hierarchy_check_constraints(handle, state.out))
   3177 			goto cleanup;
   3178 
   3179 		if (check_assertions
   3180 		    (handle, state.out,
   3181 		     state.out->global->branch_list->avrules))
   3182 			 goto cleanup;
   3183 	}
   3184 
   3185 	retval = 0;
   3186 
   3187       cleanup:
   3188 	free(state.typemap);
   3189 	free(state.boolmap);
   3190 	free(state.rolemap);
   3191 	free(state.usermap);
   3192 	return retval;
   3193 }
   3194 
   3195 static int expand_avtab_insert(avtab_t * a, avtab_key_t * k, avtab_datum_t * d)
   3196 {
   3197 	avtab_ptr_t node;
   3198 	avtab_datum_t *avd;
   3199 	int rc;
   3200 
   3201 	node = avtab_search_node(a, k);
   3202 	if (!node) {
   3203 		rc = avtab_insert(a, k, d);
   3204 		if (rc)
   3205 			ERR(NULL, "Out of memory!");
   3206 		return rc;
   3207 	}
   3208 
   3209 	if ((k->specified & AVTAB_ENABLED) !=
   3210 	    (node->key.specified & AVTAB_ENABLED)) {
   3211 		node = avtab_insert_nonunique(a, k, d);
   3212 		if (!node) {
   3213 			ERR(NULL, "Out of memory!");
   3214 			return -1;
   3215 		}
   3216 		return 0;
   3217 	}
   3218 
   3219 	avd = &node->datum;
   3220 	switch (k->specified & ~AVTAB_ENABLED) {
   3221 	case AVTAB_ALLOWED:
   3222 	case AVTAB_AUDITALLOW:
   3223 		avd->data |= d->data;
   3224 		break;
   3225 	case AVTAB_AUDITDENY:
   3226 		avd->data &= d->data;
   3227 		break;
   3228 	default:
   3229 		ERR(NULL, "Type conflict!");
   3230 		return -1;
   3231 	}
   3232 
   3233 	return 0;
   3234 }
   3235 
   3236 struct expand_avtab_data {
   3237 	avtab_t *expa;
   3238 	policydb_t *p;
   3239 
   3240 };
   3241 
   3242 static int expand_avtab_node(avtab_key_t * k, avtab_datum_t * d, void *args)
   3243 {
   3244 	struct expand_avtab_data *ptr = args;
   3245 	avtab_t *expa = ptr->expa;
   3246 	policydb_t *p = ptr->p;
   3247 	type_datum_t *stype = p->type_val_to_struct[k->source_type - 1];
   3248 	type_datum_t *ttype = p->type_val_to_struct[k->target_type - 1];
   3249 	ebitmap_t *sattr = &p->attr_type_map[k->source_type - 1];
   3250 	ebitmap_t *tattr = &p->attr_type_map[k->target_type - 1];
   3251 	ebitmap_node_t *snode, *tnode;
   3252 	unsigned int i, j;
   3253 	avtab_key_t newkey;
   3254 	int rc;
   3255 
   3256 	newkey.target_class = k->target_class;
   3257 	newkey.specified = k->specified;
   3258 
   3259 	if (stype->flavor != TYPE_ATTRIB && ttype->flavor != TYPE_ATTRIB) {
   3260 		/* Both are individual types, no expansion required. */
   3261 		return expand_avtab_insert(expa, k, d);
   3262 	}
   3263 
   3264 	if (stype->flavor != TYPE_ATTRIB) {
   3265 		/* Source is an individual type, target is an attribute. */
   3266 		newkey.source_type = k->source_type;
   3267 		ebitmap_for_each_bit(tattr, tnode, j) {
   3268 			if (!ebitmap_node_get_bit(tnode, j))
   3269 				continue;
   3270 			newkey.target_type = j + 1;
   3271 			rc = expand_avtab_insert(expa, &newkey, d);
   3272 			if (rc)
   3273 				return -1;
   3274 		}
   3275 		return 0;
   3276 	}
   3277 
   3278 	if (ttype->flavor != TYPE_ATTRIB) {
   3279 		/* Target is an individual type, source is an attribute. */
   3280 		newkey.target_type = k->target_type;
   3281 		ebitmap_for_each_bit(sattr, snode, i) {
   3282 			if (!ebitmap_node_get_bit(snode, i))
   3283 				continue;
   3284 			newkey.source_type = i + 1;
   3285 			rc = expand_avtab_insert(expa, &newkey, d);
   3286 			if (rc)
   3287 				return -1;
   3288 		}
   3289 		return 0;
   3290 	}
   3291 
   3292 	/* Both source and target type are attributes. */
   3293 	ebitmap_for_each_bit(sattr, snode, i) {
   3294 		if (!ebitmap_node_get_bit(snode, i))
   3295 			continue;
   3296 		ebitmap_for_each_bit(tattr, tnode, j) {
   3297 			if (!ebitmap_node_get_bit(tnode, j))
   3298 				continue;
   3299 			newkey.source_type = i + 1;
   3300 			newkey.target_type = j + 1;
   3301 			rc = expand_avtab_insert(expa, &newkey, d);
   3302 			if (rc)
   3303 				return -1;
   3304 		}
   3305 	}
   3306 
   3307 	return 0;
   3308 }
   3309 
   3310 int expand_avtab(policydb_t * p, avtab_t * a, avtab_t * expa)
   3311 {
   3312 	struct expand_avtab_data data;
   3313 
   3314 	if (avtab_alloc(expa, MAX_AVTAB_SIZE)) {
   3315 		ERR(NULL, "Out of memory!");
   3316 		return -1;
   3317 	}
   3318 
   3319 	data.expa = expa;
   3320 	data.p = p;
   3321 	return avtab_map(a, expand_avtab_node, &data);
   3322 }
   3323 
   3324 static int expand_cond_insert(cond_av_list_t ** l,
   3325 			      avtab_t * expa,
   3326 			      avtab_key_t * k, avtab_datum_t * d)
   3327 {
   3328 	avtab_ptr_t node;
   3329 	avtab_datum_t *avd;
   3330 	cond_av_list_t *nl;
   3331 
   3332 	node = avtab_search_node(expa, k);
   3333 	if (!node ||
   3334 	    (k->specified & AVTAB_ENABLED) !=
   3335 	    (node->key.specified & AVTAB_ENABLED)) {
   3336 		node = avtab_insert_nonunique(expa, k, d);
   3337 		if (!node) {
   3338 			ERR(NULL, "Out of memory!");
   3339 			return -1;
   3340 		}
   3341 		node->parse_context = (void *)1;
   3342 		nl = (cond_av_list_t *) malloc(sizeof(*nl));
   3343 		if (!nl) {
   3344 			ERR(NULL, "Out of memory!");
   3345 			return -1;
   3346 		}
   3347 		memset(nl, 0, sizeof(*nl));
   3348 		nl->node = node;
   3349 		nl->next = *l;
   3350 		*l = nl;
   3351 		return 0;
   3352 	}
   3353 
   3354 	avd = &node->datum;
   3355 	switch (k->specified & ~AVTAB_ENABLED) {
   3356 	case AVTAB_ALLOWED:
   3357 	case AVTAB_AUDITALLOW:
   3358 		avd->data |= d->data;
   3359 		break;
   3360 	case AVTAB_AUDITDENY:
   3361 		avd->data &= d->data;
   3362 		break;
   3363 	default:
   3364 		ERR(NULL, "Type conflict!");
   3365 		return -1;
   3366 	}
   3367 
   3368 	return 0;
   3369 }
   3370 
   3371 int expand_cond_av_node(policydb_t * p,
   3372 			avtab_ptr_t node,
   3373 			cond_av_list_t ** newl, avtab_t * expa)
   3374 {
   3375 	avtab_key_t *k = &node->key;
   3376 	avtab_datum_t *d = &node->datum;
   3377 	type_datum_t *stype = p->type_val_to_struct[k->source_type - 1];
   3378 	type_datum_t *ttype = p->type_val_to_struct[k->target_type - 1];
   3379 	ebitmap_t *sattr = &p->attr_type_map[k->source_type - 1];
   3380 	ebitmap_t *tattr = &p->attr_type_map[k->target_type - 1];
   3381 	ebitmap_node_t *snode, *tnode;
   3382 	unsigned int i, j;
   3383 	avtab_key_t newkey;
   3384 	int rc;
   3385 
   3386 	newkey.target_class = k->target_class;
   3387 	newkey.specified = k->specified;
   3388 
   3389 	if (stype->flavor != TYPE_ATTRIB && ttype->flavor != TYPE_ATTRIB) {
   3390 		/* Both are individual types, no expansion required. */
   3391 		return expand_cond_insert(newl, expa, k, d);
   3392 	}
   3393 
   3394 	if (stype->flavor != TYPE_ATTRIB) {
   3395 		/* Source is an individual type, target is an attribute. */
   3396 		newkey.source_type = k->source_type;
   3397 		ebitmap_for_each_bit(tattr, tnode, j) {
   3398 			if (!ebitmap_node_get_bit(tnode, j))
   3399 				continue;
   3400 			newkey.target_type = j + 1;
   3401 			rc = expand_cond_insert(newl, expa, &newkey, d);
   3402 			if (rc)
   3403 				return -1;
   3404 		}
   3405 		return 0;
   3406 	}
   3407 
   3408 	if (ttype->flavor != TYPE_ATTRIB) {
   3409 		/* Target is an individual type, source is an attribute. */
   3410 		newkey.target_type = k->target_type;
   3411 		ebitmap_for_each_bit(sattr, snode, i) {
   3412 			if (!ebitmap_node_get_bit(snode, i))
   3413 				continue;
   3414 			newkey.source_type = i + 1;
   3415 			rc = expand_cond_insert(newl, expa, &newkey, d);
   3416 			if (rc)
   3417 				return -1;
   3418 		}
   3419 		return 0;
   3420 	}
   3421 
   3422 	/* Both source and target type are attributes. */
   3423 	ebitmap_for_each_bit(sattr, snode, i) {
   3424 		if (!ebitmap_node_get_bit(snode, i))
   3425 			continue;
   3426 		ebitmap_for_each_bit(tattr, tnode, j) {
   3427 			if (!ebitmap_node_get_bit(tnode, j))
   3428 				continue;
   3429 			newkey.source_type = i + 1;
   3430 			newkey.target_type = j + 1;
   3431 			rc = expand_cond_insert(newl, expa, &newkey, d);
   3432 			if (rc)
   3433 				return -1;
   3434 		}
   3435 	}
   3436 
   3437 	return 0;
   3438 }
   3439 
   3440 int expand_cond_av_list(policydb_t * p, cond_av_list_t * l,
   3441 			cond_av_list_t ** newl, avtab_t * expa)
   3442 {
   3443 	cond_av_list_t *cur;
   3444 	avtab_ptr_t node;
   3445 	int rc;
   3446 
   3447 	if (avtab_alloc(expa, MAX_AVTAB_SIZE)) {
   3448 		ERR(NULL, "Out of memory!");
   3449 		return -1;
   3450 	}
   3451 
   3452 	*newl = NULL;
   3453 	for (cur = l; cur; cur = cur->next) {
   3454 		node = cur->node;
   3455 		rc = expand_cond_av_node(p, node, newl, expa);
   3456 		if (rc)
   3457 			return rc;
   3458 	}
   3459 
   3460 	return 0;
   3461 }
   3462