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