1/* Authors: Karl MacMillan <kmacmillan@mentalrootkit.com>
2 *	    Joshua Brindle <jbrindle@tresys.com>
3 *          Jason Tang <jtang@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 <sepol/policydb/policydb.h>
24#include <sepol/policydb/conditional.h>
25#include <sepol/policydb/hashtab.h>
26#include <sepol/policydb/avrule_block.h>
27#include <sepol/policydb/link.h>
28#include <sepol/policydb/util.h>
29
30#include <stdlib.h>
31#include <stdarg.h>
32#include <stdio.h>
33#include <string.h>
34#include <assert.h>
35
36#include "debug.h"
37
38#undef min
39#define min(a,b) (((a) < (b)) ? (a) : (b))
40
41typedef struct policy_module {
42	policydb_t *policy;
43	uint32_t num_decls;
44	uint32_t *map[SYM_NUM];
45	uint32_t *avdecl_map;
46	uint32_t **perm_map;
47	uint32_t *perm_map_len;
48
49	/* a pointer to within the base module's avrule_block chain to
50	 * where this module's global now resides */
51	avrule_block_t *base_global;
52} policy_module_t;
53
54typedef struct link_state {
55	int verbose;
56	policydb_t *base;
57	avrule_block_t *last_avrule_block, *last_base_avrule_block;
58	uint32_t next_decl_id, current_decl_id;
59
60	/* temporary variables, used during hashtab_map() calls */
61	policy_module_t *cur;
62	char *cur_mod_name;
63	avrule_decl_t *dest_decl;
64	class_datum_t *src_class, *dest_class;
65	char *dest_class_name;
66	char dest_class_req;	/* flag indicating the class was not declared */
67	uint32_t symbol_num;
68	/* used to report the name of the module if dependancy error occurs */
69	policydb_t **decl_to_mod;
70
71	/* error reporting fields */
72	sepol_handle_t *handle;
73} link_state_t;
74
75typedef struct missing_requirement {
76	uint32_t symbol_type;
77	uint32_t symbol_value;
78	uint32_t perm_value;
79} missing_requirement_t;
80
81static const char *symtab_names[SYM_NUM] = {
82	"common", "class", "role", "type/attribute", "user",
83	"bool", "level", "category"
84};
85
86/* Deallocates all elements within a module, but NOT the policydb_t
87 * structure within, as well as the pointer itself. */
88static void policy_module_destroy(policy_module_t * mod)
89{
90	unsigned int i;
91	if (mod == NULL) {
92		return;
93	}
94	for (i = 0; i < SYM_NUM; i++) {
95		free(mod->map[i]);
96	}
97	for (i = 0; mod->perm_map != NULL && i < mod->policy->p_classes.nprim;
98	     i++) {
99		free(mod->perm_map[i]);
100	}
101	free(mod->perm_map);
102	free(mod->perm_map_len);
103	free(mod->avdecl_map);
104	free(mod);
105}
106
107/***** functions that copy identifiers from a module to base *****/
108
109/* Note: there is currently no scoping for permissions, which causes some
110 * strange side-effects. The current approach is this:
111 *
112 * a) perm is required and the class _and_ perm are declared in base: only add a mapping.
113 * b) perm is required and the class and perm are _not_ declared in base: simply add the permissions
114 *    to the object class. This means that the requirements for the decl are the union of the permissions
115 *    required for all decls, but who cares.
116 * c) perm is required, the class is declared in base, but the perm is not present. Nothing we can do
117 *    here because we can't mark a single permission as required, so we bail with a requirement error
118 *    _even_ if we are in an optional.
119 *
120 * A is correct behavior, b is wrong but not too bad, c is totall wrong for optionals. Fixing this requires
121 * a format change.
122 */
123static int permission_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
124				    void *data)
125{
126	char *perm_id = key, *new_id = NULL;
127	perm_datum_t *perm, *new_perm = NULL, *dest_perm;
128	link_state_t *state = (link_state_t *) data;
129
130	class_datum_t *src_class = state->src_class;
131	class_datum_t *dest_class = state->dest_class;
132	policy_module_t *mod = state->cur;
133	uint32_t sclassi = src_class->s.value - 1;
134	int ret;
135
136	perm = (perm_datum_t *) datum;
137	dest_perm = hashtab_search(dest_class->permissions.table, perm_id);
138	if (dest_perm == NULL && dest_class->comdatum != NULL) {
139		dest_perm =
140		    hashtab_search(dest_class->comdatum->permissions.table,
141				   perm_id);
142	}
143
144	if (dest_perm == NULL) {
145		/* If the object class was not declared in the base, add the perm
146		 * to the object class. */
147		if (state->dest_class_req) {
148			/* If the class was required (not declared), insert the new permission */
149			new_id = strdup(perm_id);
150			if (new_id == NULL) {
151				ERR(state->handle, "Memory error");
152				ret = SEPOL_ERR;
153				goto err;
154			}
155			new_perm =
156			    (perm_datum_t *) calloc(1, sizeof(perm_datum_t));
157			if (new_perm == NULL) {
158				ERR(state->handle, "Memory error");
159				ret = SEPOL_ERR;
160				goto err;
161			}
162			ret = hashtab_insert(dest_class->permissions.table,
163					     (hashtab_key_t) new_id,
164					     (hashtab_datum_t) new_perm);
165			if (ret) {
166				ERR(state->handle,
167				    "could not insert permission into class\n");
168				goto err;
169			}
170			new_perm->s.value = dest_class->permissions.nprim + 1;
171			dest_perm = new_perm;
172		} else {
173			/* this is case c from above */
174			ERR(state->handle,
175			    "Module %s depends on permission %s in class %s, not satisfied",
176			    state->cur_mod_name, perm_id,
177			    state->dest_class_name);
178			return SEPOL_EREQ;
179		}
180	}
181
182	/* build the mapping for permissions encompassing this class.
183	 * unlike symbols, the permission map translates between
184	 * module permission bit to target permission bit.  that bit
185	 * may have originated from the class -or- it could be from
186	 * the class's common parent.*/
187	if (perm->s.value > mod->perm_map_len[sclassi]) {
188		uint32_t *newmap = calloc(perm->s.value, sizeof(*newmap));
189		if (newmap == NULL) {
190			ERR(state->handle, "Out of memory!");
191			return -1;
192		}
193		memcpy(newmap, mod->perm_map[sclassi],
194		       mod->perm_map_len[sclassi] * sizeof(*newmap));
195		free(mod->perm_map[sclassi]);
196		mod->perm_map[sclassi] = newmap;
197		mod->perm_map_len[sclassi] = perm->s.value;
198	}
199	mod->perm_map[sclassi][perm->s.value - 1] = dest_perm->s.value;
200
201	return 0;
202      err:
203	free(new_id);
204	free(new_perm);
205	return ret;
206}
207
208static int class_copy_default_new_object(link_state_t *state,
209					 class_datum_t *olddatum,
210					 class_datum_t *newdatum)
211{
212	if (olddatum->default_user) {
213		if (newdatum->default_user && olddatum->default_user != newdatum->default_user) {
214			ERR(state->handle, "Found conflicting default user definitions");
215			return SEPOL_ENOTSUP;
216		}
217		newdatum->default_user = olddatum->default_user;
218	}
219	if (olddatum->default_role) {
220		if (newdatum->default_role && olddatum->default_role != newdatum->default_role) {
221			ERR(state->handle, "Found conflicting default role definitions");
222			return SEPOL_ENOTSUP;
223		}
224		newdatum->default_role = olddatum->default_role;
225	}
226	if (olddatum->default_type) {
227		if (newdatum->default_type && olddatum->default_type != newdatum->default_type) {
228			ERR(state->handle, "Found conflicting default type definitions");
229			return SEPOL_ENOTSUP;
230		}
231		newdatum->default_type = olddatum->default_type;
232	}
233	if (olddatum->default_range) {
234		if (newdatum->default_range && olddatum->default_range != newdatum->default_range) {
235			ERR(state->handle, "Found conflicting default range definitions");
236			return SEPOL_ENOTSUP;
237		}
238		newdatum->default_range = olddatum->default_range;
239	}
240	return 0;
241}
242
243static int class_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
244			       void *data)
245{
246	char *id = key, *new_id = NULL;
247	class_datum_t *cladatum, *new_class = NULL;
248	link_state_t *state = (link_state_t *) data;
249	scope_datum_t *scope = NULL;
250	int ret;
251
252	cladatum = (class_datum_t *) datum;
253	state->dest_class_req = 0;
254
255	new_class = hashtab_search(state->base->p_classes.table, id);
256	/* If there is not an object class already in the base symtab that means
257	 * that either a) a module is trying to declare a new object class (which
258	 * the compiler should prevent) or b) an object class was required that is
259	 * not in the base.
260	 */
261	if (new_class == NULL) {
262		scope =
263		    hashtab_search(state->cur->policy->p_classes_scope.table,
264				   id);
265		if (scope == NULL) {
266			ret = SEPOL_ERR;
267			goto err;
268		}
269		if (scope->scope == SCOPE_DECL) {
270			/* disallow declarations in modules */
271			ERR(state->handle,
272			    "%s: Modules may not yet declare new classes.",
273			    state->cur_mod_name);
274			ret = SEPOL_ENOTSUP;
275			goto err;
276		} else {
277			/* It would be nice to error early here because the requirement is
278			 * not met, but we cannot because the decl might be optional (in which
279			 * case we should record the requirement so that it is just turned
280			 * off). Note: this will break horribly if modules can declare object
281			 * classes because the class numbers will be all wrong (i.e., they
282			 * might be assigned in the order they were required rather than the
283			 * current scheme which ensures correct numbering by ordering the
284			 * declarations properly). This can't be fixed until some infrastructure
285			 * for querying the object class numbers is in place. */
286			state->dest_class_req = 1;
287			new_class =
288			    (class_datum_t *) calloc(1, sizeof(class_datum_t));
289			if (new_class == NULL) {
290				ERR(state->handle, "Memory error\n");
291				ret = SEPOL_ERR;
292				goto err;
293			}
294			if (symtab_init
295			    (&new_class->permissions, PERM_SYMTAB_SIZE)) {
296				ret = SEPOL_ERR;
297				goto err;
298			}
299			new_id = strdup(id);
300			if (new_id == NULL) {
301				ERR(state->handle, "Memory error\n");
302				symtab_destroy(&new_class->permissions);
303				ret = SEPOL_ERR;
304				goto err;
305			}
306			ret = hashtab_insert(state->base->p_classes.table,
307					     (hashtab_key_t) new_id,
308					     (hashtab_datum_t) new_class);
309			if (ret) {
310				ERR(state->handle,
311				    "could not insert new class into symtab");
312				symtab_destroy(&new_class->permissions);
313				goto err;
314			}
315			new_class->s.value = ++(state->base->p_classes.nprim);
316		}
317	}
318
319	state->cur->map[SYM_CLASSES][cladatum->s.value - 1] =
320	    new_class->s.value;
321
322	/* copy permissions */
323	state->src_class = cladatum;
324	state->dest_class = new_class;
325	state->dest_class_name = (char *)key;
326
327	/* copy default new object rules */
328	ret = class_copy_default_new_object(state, cladatum, new_class);
329	if (ret)
330		return ret;
331
332	ret =
333	    hashtab_map(cladatum->permissions.table, permission_copy_callback,
334			state);
335	if (ret != 0) {
336		return ret;
337	}
338
339	return 0;
340      err:
341	free(new_class);
342	free(new_id);
343	return ret;
344}
345
346static int role_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
347			      void *data)
348{
349	int ret;
350	char *id = key, *new_id = NULL;
351	role_datum_t *role, *base_role, *new_role = NULL;
352	link_state_t *state = (link_state_t *) data;
353
354	role = (role_datum_t *) datum;
355
356	base_role = hashtab_search(state->base->p_roles.table, id);
357	if (base_role != NULL) {
358		/* role already exists.  check that it is what this
359		 * module expected.  duplicate declarations (e.g., two
360		 * modules both declare role foo_r) is checked during
361		 * scope_copy_callback(). */
362		if (role->flavor == ROLE_ATTRIB
363		    && base_role->flavor != ROLE_ATTRIB) {
364			ERR(state->handle,
365			    "%s: Expected %s to be a role attribute, but it was already declared as a regular role.",
366			    state->cur_mod_name, id);
367			return -1;
368		} else if (role->flavor != ROLE_ATTRIB
369			   && base_role->flavor == ROLE_ATTRIB) {
370			ERR(state->handle,
371			    "%s: Expected %s to be a regular role, but it was already declared as a role attribute.",
372			    state->cur_mod_name, id);
373			return -1;
374		}
375	} else {
376		if (state->verbose)
377			INFO(state->handle, "copying role %s", id);
378
379		if ((new_id = strdup(id)) == NULL) {
380			goto cleanup;
381		}
382
383		if ((new_role =
384		     (role_datum_t *) malloc(sizeof(*new_role))) == NULL) {
385			goto cleanup;
386		}
387		role_datum_init(new_role);
388
389		/* new_role's dominates, types and roles field will be copied
390		 * during role_fix_callback() */
391		new_role->flavor = role->flavor;
392		new_role->s.value = state->base->p_roles.nprim + 1;
393
394		ret = hashtab_insert(state->base->p_roles.table,
395				     (hashtab_key_t) new_id,
396				     (hashtab_datum_t) new_role);
397		if (ret) {
398			goto cleanup;
399		}
400		state->base->p_roles.nprim++;
401		base_role = new_role;
402	}
403
404	if (state->dest_decl) {
405		new_id = NULL;
406		if ((new_role = malloc(sizeof(*new_role))) == NULL) {
407			goto cleanup;
408		}
409		role_datum_init(new_role);
410		new_role->flavor = base_role->flavor;
411		new_role->s.value = base_role->s.value;
412		if ((new_id = strdup(id)) == NULL) {
413			goto cleanup;
414		}
415		if (hashtab_insert
416		    (state->dest_decl->p_roles.table, new_id, new_role)) {
417			goto cleanup;
418		}
419		state->dest_decl->p_roles.nprim++;
420	}
421
422	state->cur->map[SYM_ROLES][role->s.value - 1] = base_role->s.value;
423	return 0;
424
425      cleanup:
426	ERR(state->handle, "Out of memory!");
427	role_datum_destroy(new_role);
428	free(new_id);
429	free(new_role);
430	return -1;
431}
432
433/* Copy types and attributes from a module into the base module. The
434 * attributes are copied, but the types that make up this attribute
435 * are delayed type_fix_callback(). */
436static int type_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
437			      void *data)
438{
439	int ret;
440	char *id = key, *new_id = NULL;
441	type_datum_t *type, *base_type, *new_type = NULL;
442	link_state_t *state = (link_state_t *) data;
443
444	type = (type_datum_t *) datum;
445	if ((type->flavor == TYPE_TYPE && !type->primary)
446	    || type->flavor == TYPE_ALIAS) {
447		/* aliases are handled later, in alias_copy_callback() */
448		return 0;
449	}
450
451	base_type = hashtab_search(state->base->p_types.table, id);
452	if (base_type != NULL) {
453		/* type already exists.  check that it is what this
454		 * module expected.  duplicate declarations (e.g., two
455		 * modules both declare type foo_t) is checked during
456		 * scope_copy_callback(). */
457		if (type->flavor == TYPE_ATTRIB
458		    && base_type->flavor != TYPE_ATTRIB) {
459			ERR(state->handle,
460			    "%s: Expected %s to be an attribute, but it was already declared as a type.",
461			    state->cur_mod_name, id);
462			return -1;
463		} else if (type->flavor != TYPE_ATTRIB
464			   && base_type->flavor == TYPE_ATTRIB) {
465			ERR(state->handle,
466			    "%s: Expected %s to be a type, but it was already declared as an attribute.",
467			    state->cur_mod_name, id);
468			return -1;
469		}
470		/* permissive should pass to the base type */
471		base_type->flags |= (type->flags & TYPE_FLAGS_PERMISSIVE);
472	} else {
473		if (state->verbose)
474			INFO(state->handle, "copying type %s", id);
475
476		if ((new_id = strdup(id)) == NULL) {
477			goto cleanup;
478		}
479
480		if ((new_type =
481		     (type_datum_t *) calloc(1, sizeof(*new_type))) == NULL) {
482			goto cleanup;
483		}
484		new_type->primary = type->primary;
485		new_type->flags = type->flags;
486		new_type->flavor = type->flavor;
487		/* for attributes, the writing of new_type->types is
488		   done in type_fix_callback() */
489
490		new_type->s.value = state->base->p_types.nprim + 1;
491
492		ret = hashtab_insert(state->base->p_types.table,
493				     (hashtab_key_t) new_id,
494				     (hashtab_datum_t) new_type);
495		if (ret) {
496			goto cleanup;
497		}
498		state->base->p_types.nprim++;
499		base_type = new_type;
500	}
501
502	if (state->dest_decl) {
503		new_id = NULL;
504		if ((new_type = calloc(1, sizeof(*new_type))) == NULL) {
505			goto cleanup;
506		}
507		new_type->primary = type->primary;
508		new_type->flavor = type->flavor;
509		new_type->flags = type->flags;
510		new_type->s.value = base_type->s.value;
511		if ((new_id = strdup(id)) == NULL) {
512			goto cleanup;
513		}
514		if (hashtab_insert
515		    (state->dest_decl->p_types.table, new_id, new_type)) {
516			goto cleanup;
517		}
518		state->dest_decl->p_types.nprim++;
519	}
520
521	state->cur->map[SYM_TYPES][type->s.value - 1] = base_type->s.value;
522	return 0;
523
524      cleanup:
525	ERR(state->handle, "Out of memory!");
526	free(new_id);
527	free(new_type);
528	return -1;
529}
530
531static int user_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
532			      void *data)
533{
534	int ret;
535	char *id = key, *new_id = NULL;
536	user_datum_t *user, *base_user, *new_user = NULL;
537	link_state_t *state = (link_state_t *) data;
538
539	user = (user_datum_t *) datum;
540
541	base_user = hashtab_search(state->base->p_users.table, id);
542	if (base_user == NULL) {
543		if (state->verbose)
544			INFO(state->handle, "copying user %s", id);
545
546		if ((new_id = strdup(id)) == NULL) {
547			goto cleanup;
548		}
549
550		if ((new_user =
551		     (user_datum_t *) malloc(sizeof(*new_user))) == NULL) {
552			goto cleanup;
553		}
554		user_datum_init(new_user);
555		/* new_users's roles and MLS fields will be copied during
556		   user_fix_callback(). */
557
558		new_user->s.value = state->base->p_users.nprim + 1;
559
560		ret = hashtab_insert(state->base->p_users.table,
561				     (hashtab_key_t) new_id,
562				     (hashtab_datum_t) new_user);
563		if (ret) {
564			goto cleanup;
565		}
566		state->base->p_users.nprim++;
567		base_user = new_user;
568	}
569
570	if (state->dest_decl) {
571		new_id = NULL;
572		if ((new_user = malloc(sizeof(*new_user))) == NULL) {
573			goto cleanup;
574		}
575		user_datum_init(new_user);
576		new_user->s.value = base_user->s.value;
577		if ((new_id = strdup(id)) == NULL) {
578			goto cleanup;
579		}
580		if (hashtab_insert
581		    (state->dest_decl->p_users.table, new_id, new_user)) {
582			goto cleanup;
583		}
584		state->dest_decl->p_users.nprim++;
585	}
586
587	state->cur->map[SYM_USERS][user->s.value - 1] = base_user->s.value;
588	return 0;
589
590      cleanup:
591	ERR(state->handle, "Out of memory!");
592	user_datum_destroy(new_user);
593	free(new_id);
594	free(new_user);
595	return -1;
596}
597
598static int bool_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
599			      void *data)
600{
601	int ret;
602	char *id = key, *new_id = NULL;
603	cond_bool_datum_t *booldatum, *base_bool, *new_bool = NULL;
604	link_state_t *state = (link_state_t *) data;
605	scope_datum_t *scope;
606
607	booldatum = (cond_bool_datum_t *) datum;
608
609	base_bool = hashtab_search(state->base->p_bools.table, id);
610	if (base_bool == NULL) {
611		if (state->verbose)
612			INFO(state->handle, "copying boolean %s", id);
613
614		if ((new_id = strdup(id)) == NULL) {
615			goto cleanup;
616		}
617
618		if ((new_bool =
619		     (cond_bool_datum_t *) malloc(sizeof(*new_bool))) == NULL) {
620			goto cleanup;
621		}
622		new_bool->s.value = state->base->p_bools.nprim + 1;
623
624		ret = hashtab_insert(state->base->p_bools.table,
625				     (hashtab_key_t) new_id,
626				     (hashtab_datum_t) new_bool);
627		if (ret) {
628			goto cleanup;
629		}
630		state->base->p_bools.nprim++;
631		base_bool = new_bool;
632		base_bool->flags = booldatum->flags;
633		base_bool->state = booldatum->state;
634	} else if ((booldatum->flags & COND_BOOL_FLAGS_TUNABLE) !=
635		   (base_bool->flags & COND_BOOL_FLAGS_TUNABLE)) {
636			/* A mismatch between boolean/tunable declaration
637			 * and usage(for example a boolean used in the
638			 * tunable_policy() or vice versa).
639			 *
640			 * This is not allowed and bail out with errors */
641			ERR(state->handle,
642			    "%s: Mismatch between boolean/tunable definition "
643			    "and usage for %s", state->cur_mod_name, id);
644			return -1;
645	}
646
647	/* Get the scope info for this boolean to see if this is the declaration,
648 	 * if so set the state */
649	scope = hashtab_search(state->cur->policy->p_bools_scope.table, id);
650	if (!scope)
651		return SEPOL_ERR;
652	if (scope->scope == SCOPE_DECL) {
653		base_bool->state = booldatum->state;
654		/* Only the declaration rather than requirement
655		 * decides if it is a boolean or tunable. */
656		base_bool->flags = booldatum->flags;
657	}
658	state->cur->map[SYM_BOOLS][booldatum->s.value - 1] = base_bool->s.value;
659	return 0;
660
661      cleanup:
662	ERR(state->handle, "Out of memory!");
663	cond_destroy_bool(new_id, new_bool, NULL);
664	return -1;
665}
666
667static int sens_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
668			      void *data)
669{
670	char *id = key;
671	level_datum_t *level, *base_level;
672	link_state_t *state = (link_state_t *) data;
673	scope_datum_t *scope;
674
675	level = (level_datum_t *) datum;
676
677	base_level = hashtab_search(state->base->p_levels.table, id);
678	if (!base_level) {
679		scope =
680		    hashtab_search(state->cur->policy->p_sens_scope.table, id);
681		if (!scope)
682			return SEPOL_ERR;
683		if (scope->scope == SCOPE_DECL) {
684			/* disallow declarations in modules */
685			ERR(state->handle,
686			    "%s: Modules may not declare new sensitivities.",
687			    state->cur_mod_name);
688			return SEPOL_ENOTSUP;
689		} else if (scope->scope == SCOPE_REQ) {
690			/* unmet requirement */
691			ERR(state->handle,
692			    "%s: Sensitivity %s not declared by base.",
693			    state->cur_mod_name, id);
694			return SEPOL_ENOTSUP;
695		} else {
696			ERR(state->handle,
697			    "%s: has an unknown scope: %d\n",
698			    state->cur_mod_name, scope->scope);
699			return SEPOL_ENOTSUP;
700		}
701	}
702
703	state->cur->map[SYM_LEVELS][level->level->sens - 1] =
704	    base_level->level->sens;
705
706	return 0;
707}
708
709static int cat_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
710			     void *data)
711{
712	char *id = key;
713	cat_datum_t *cat, *base_cat;
714	link_state_t *state = (link_state_t *) data;
715	scope_datum_t *scope;
716
717	cat = (cat_datum_t *) datum;
718
719	base_cat = hashtab_search(state->base->p_cats.table, id);
720	if (!base_cat) {
721		scope = hashtab_search(state->cur->policy->p_cat_scope.table, id);
722		if (!scope)
723			return SEPOL_ERR;
724		if (scope->scope == SCOPE_DECL) {
725			/* disallow declarations in modules */
726			ERR(state->handle,
727			    "%s: Modules may not declare new categories.",
728			    state->cur_mod_name);
729			return SEPOL_ENOTSUP;
730		} else if (scope->scope == SCOPE_REQ) {
731			/* unmet requirement */
732			ERR(state->handle,
733			    "%s: Category %s not declared by base.",
734			    state->cur_mod_name, id);
735			return SEPOL_ENOTSUP;
736		} else {
737			/* unknown scope?  malformed policy? */
738			ERR(state->handle,
739			    "%s: has an unknown scope: %d\n",
740			    state->cur_mod_name, scope->scope);
741			return SEPOL_ENOTSUP;
742		}
743	}
744
745	state->cur->map[SYM_CATS][cat->s.value - 1] = base_cat->s.value;
746
747	return 0;
748}
749
750static int (*copy_callback_f[SYM_NUM]) (hashtab_key_t key,
751					hashtab_datum_t datum, void *datap) = {
752NULL, class_copy_callback, role_copy_callback, type_copy_callback,
753	    user_copy_callback, bool_copy_callback, sens_copy_callback,
754	    cat_copy_callback};
755
756/*
757 * The boundaries have to be copied after the types/roles/users are copied,
758 * because it refers hashtab to lookup destinated objects.
759 */
760static int type_bounds_copy_callback(hashtab_key_t key,
761				     hashtab_datum_t datum, void *data)
762{
763	link_state_t *state = (link_state_t *) data;
764	type_datum_t *type = (type_datum_t *) datum;
765	type_datum_t *dest;
766	uint32_t bounds_val;
767
768	if (!type->bounds)
769		return 0;
770
771	bounds_val = state->cur->map[SYM_TYPES][type->bounds - 1];
772
773	dest = hashtab_search(state->base->p_types.table, key);
774	if (!dest) {
775		ERR(state->handle,
776		    "Type lookup failed for %s", (char *)key);
777		return -1;
778	}
779	if (dest->bounds != 0 && dest->bounds != bounds_val) {
780		ERR(state->handle,
781		    "Inconsistent boundary for %s", (char *)key);
782		return -1;
783	}
784	dest->bounds = bounds_val;
785
786	return 0;
787}
788
789static int role_bounds_copy_callback(hashtab_key_t key,
790				     hashtab_datum_t datum, void *data)
791{
792	link_state_t *state = (link_state_t *) data;
793	role_datum_t *role = (role_datum_t *) datum;
794	role_datum_t *dest;
795	uint32_t bounds_val;
796
797	if (!role->bounds)
798		return 0;
799
800	bounds_val = state->cur->map[SYM_ROLES][role->bounds - 1];
801
802	dest = hashtab_search(state->base->p_roles.table, key);
803	if (!dest) {
804		ERR(state->handle,
805		    "Role lookup failed for %s", (char *)key);
806		return -1;
807	}
808	if (dest->bounds != 0 && dest->bounds != bounds_val) {
809		ERR(state->handle,
810		    "Inconsistent boundary for %s", (char *)key);
811		return -1;
812	}
813	dest->bounds = bounds_val;
814
815	return 0;
816}
817
818static int user_bounds_copy_callback(hashtab_key_t key,
819				     hashtab_datum_t datum, void *data)
820{
821	link_state_t *state = (link_state_t *) data;
822	user_datum_t *user = (user_datum_t *) datum;
823	user_datum_t *dest;
824	uint32_t bounds_val;
825
826	if (!user->bounds)
827		return 0;
828
829	bounds_val = state->cur->map[SYM_USERS][user->bounds - 1];
830
831	dest = hashtab_search(state->base->p_users.table, key);
832	if (!dest) {
833		ERR(state->handle,
834		    "User lookup failed for %s", (char *)key);
835		return -1;
836	}
837	if (dest->bounds != 0 && dest->bounds != bounds_val) {
838		ERR(state->handle,
839		    "Inconsistent boundary for %s", (char *)key);
840		return -1;
841	}
842	dest->bounds = bounds_val;
843
844	return 0;
845}
846
847/* The aliases have to be copied after the types and attributes to be
848 * certain that the base symbol table will have the type that the
849 * alias refers. Otherwise, we won't be able to find the type value
850 * for the alias. We can't depend on the declaration ordering because
851 * of the hash table.
852 */
853static int alias_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
854			       void *data)
855{
856	char *id = key, *new_id = NULL, *target_id;
857	type_datum_t *type, *base_type, *new_type = NULL, *target_type;
858	link_state_t *state = (link_state_t *) data;
859	policy_module_t *mod = state->cur;
860	int primval;
861
862	type = (type_datum_t *) datum;
863	/* there are 2 kinds of aliases. Ones with their own value (TYPE_ALIAS)
864	 * and ones with the value of their primary (TYPE_TYPE && type->primary = 0)
865	 */
866	if (!
867	    (type->flavor == TYPE_ALIAS
868	     || (type->flavor == TYPE_TYPE && !type->primary))) {
869		/* ignore types and attributes -- they were handled in
870		 * type_copy_callback() */
871		return 0;
872	}
873
874	if (type->flavor == TYPE_ALIAS)
875		primval = type->primary;
876	else
877		primval = type->s.value;
878
879	target_id = mod->policy->p_type_val_to_name[primval - 1];
880	target_type = hashtab_search(state->base->p_types.table, target_id);
881	if (target_type == NULL) {
882		ERR(state->handle, "%s: Could not find type %s for alias %s.",
883		    state->cur_mod_name, target_id, id);
884		return -1;
885	}
886
887	if (!strcmp(id, target_id)) {
888		ERR(state->handle, "%s: Self aliasing of %s.",
889		    state->cur_mod_name, id);
890		return -1;
891	}
892
893	target_type->flags |= (type->flags & TYPE_FLAGS_PERMISSIVE);
894
895	base_type = hashtab_search(state->base->p_types.table, id);
896	if (base_type == NULL) {
897		if (state->verbose)
898			INFO(state->handle, "copying alias %s", id);
899
900		if ((new_type =
901		     (type_datum_t *) calloc(1, sizeof(*new_type))) == NULL) {
902			goto cleanup;
903		}
904		/* the linked copy always has TYPE_ALIAS style aliases */
905		new_type->primary = target_type->s.value;
906		new_type->flags = target_type->flags;
907		new_type->flavor = TYPE_ALIAS;
908		new_type->s.value = state->base->p_types.nprim + 1;
909		if ((new_id = strdup(id)) == NULL) {
910			goto cleanup;
911		}
912		if (hashtab_insert
913		    (state->base->p_types.table, new_id, new_type)) {
914			goto cleanup;
915		}
916		state->base->p_types.nprim++;
917		base_type = new_type;
918	} else {
919
920		/* if this already exists and isn't an alias it was required by another module (or base)
921		 * and inserted into the hashtable as a type, fix it up now */
922
923		if (base_type->flavor == TYPE_ALIAS) {
924			/* error checking */
925			assert(base_type->primary == target_type->s.value);
926			assert(base_type->primary ==
927			       mod->map[SYM_TYPES][primval - 1]);
928			assert(mod->map[SYM_TYPES][type->s.value - 1] ==
929			       base_type->primary);
930			return 0;
931		}
932
933		if (base_type->flavor == TYPE_ATTRIB) {
934			ERR(state->handle,
935			    "%s is an alias of an attribute, not allowed", id);
936			return -1;
937		}
938
939		base_type->flavor = TYPE_ALIAS;
940		base_type->primary = target_type->s.value;
941		base_type->flags |= (target_type->flags & TYPE_FLAGS_PERMISSIVE);
942
943	}
944	/* the aliases map points from its value to its primary so when this module
945	 * references this type the value it gets back from the map is the primary */
946	mod->map[SYM_TYPES][type->s.value - 1] = base_type->primary;
947
948	return 0;
949
950      cleanup:
951	ERR(state->handle, "Out of memory!");
952	free(new_id);
953	free(new_type);
954	return -1;
955}
956
957/*********** callbacks that fix bitmaps ***********/
958
959static int type_set_convert(type_set_t * types, type_set_t * dst,
960			    policy_module_t * mod, link_state_t * state
961			    __attribute__ ((unused)))
962{
963	unsigned int i;
964	ebitmap_node_t *tnode;
965	ebitmap_for_each_bit(&types->types, tnode, i) {
966		if (ebitmap_node_get_bit(tnode, i)) {
967			assert(mod->map[SYM_TYPES][i]);
968			if (ebitmap_set_bit
969			    (&dst->types, mod->map[SYM_TYPES][i] - 1, 1)) {
970				goto cleanup;
971			}
972		}
973	}
974	ebitmap_for_each_bit(&types->negset, tnode, i) {
975		if (ebitmap_node_get_bit(tnode, i)) {
976			assert(mod->map[SYM_TYPES][i]);
977			if (ebitmap_set_bit
978			    (&dst->negset, mod->map[SYM_TYPES][i] - 1, 1)) {
979				goto cleanup;
980			}
981		}
982	}
983	dst->flags = types->flags;
984	return 0;
985
986      cleanup:
987	return -1;
988}
989
990/* OR 2 typemaps together and at the same time map the src types to
991 * the correct values in the dst typeset.
992 */
993static int type_set_or_convert(type_set_t * types, type_set_t * dst,
994			       policy_module_t * mod, link_state_t * state)
995{
996	type_set_t ts_tmp;
997
998	type_set_init(&ts_tmp);
999	if (type_set_convert(types, &ts_tmp, mod, state) == -1) {
1000		goto cleanup;
1001	}
1002	if (type_set_or_eq(dst, &ts_tmp)) {
1003		goto cleanup;
1004	}
1005	type_set_destroy(&ts_tmp);
1006	return 0;
1007
1008      cleanup:
1009	ERR(state->handle, "Out of memory!");
1010	type_set_destroy(&ts_tmp);
1011	return -1;
1012}
1013
1014static int role_set_or_convert(role_set_t * roles, role_set_t * dst,
1015			       policy_module_t * mod, link_state_t * state)
1016{
1017	unsigned int i;
1018	ebitmap_t tmp;
1019	ebitmap_node_t *rnode;
1020
1021	ebitmap_init(&tmp);
1022	ebitmap_for_each_bit(&roles->roles, rnode, i) {
1023		if (ebitmap_node_get_bit(rnode, i)) {
1024			assert(mod->map[SYM_ROLES][i]);
1025			if (ebitmap_set_bit
1026			    (&tmp, mod->map[SYM_ROLES][i] - 1, 1)) {
1027				goto cleanup;
1028			}
1029		}
1030	}
1031	if (ebitmap_union(&dst->roles, &tmp)) {
1032		goto cleanup;
1033	}
1034	dst->flags |= roles->flags;
1035	ebitmap_destroy(&tmp);
1036	return 0;
1037      cleanup:
1038	ERR(state->handle, "Out of memory!");
1039	ebitmap_destroy(&tmp);
1040	return -1;
1041}
1042
1043static int mls_level_convert(mls_semantic_level_t * src, mls_semantic_level_t * dst,
1044			     policy_module_t * mod, link_state_t * state)
1045{
1046	mls_semantic_cat_t *src_cat, *new_cat;
1047
1048	if (!mod->policy->mls)
1049		return 0;
1050
1051	/* Required not declared. */
1052	if (!src->sens)
1053		return 0;
1054
1055	assert(mod->map[SYM_LEVELS][src->sens - 1]);
1056	dst->sens = mod->map[SYM_LEVELS][src->sens - 1];
1057
1058	for (src_cat = src->cat; src_cat; src_cat = src_cat->next) {
1059		new_cat =
1060		    (mls_semantic_cat_t *) malloc(sizeof(mls_semantic_cat_t));
1061		if (!new_cat) {
1062			ERR(state->handle, "Out of memory");
1063			return -1;
1064		}
1065		mls_semantic_cat_init(new_cat);
1066
1067		new_cat->next = dst->cat;
1068		dst->cat = new_cat;
1069
1070		assert(mod->map[SYM_CATS][src_cat->low - 1]);
1071		dst->cat->low = mod->map[SYM_CATS][src_cat->low - 1];
1072		assert(mod->map[SYM_CATS][src_cat->high - 1]);
1073		dst->cat->high = mod->map[SYM_CATS][src_cat->high - 1];
1074	}
1075
1076	return 0;
1077}
1078
1079static int mls_range_convert(mls_semantic_range_t * src, mls_semantic_range_t * dst,
1080			     policy_module_t * mod, link_state_t * state)
1081{
1082	int ret;
1083	ret = mls_level_convert(&src->level[0], &dst->level[0], mod, state);
1084	if (ret)
1085		return ret;
1086	ret = mls_level_convert(&src->level[1], &dst->level[1], mod, state);
1087	if (ret)
1088		return ret;
1089	return 0;
1090}
1091
1092static int role_fix_callback(hashtab_key_t key, hashtab_datum_t datum,
1093			     void *data)
1094{
1095	unsigned int i;
1096	char *id = key;
1097	role_datum_t *role, *dest_role = NULL;
1098	link_state_t *state = (link_state_t *) data;
1099	ebitmap_t e_tmp;
1100	policy_module_t *mod = state->cur;
1101	ebitmap_node_t *rnode;
1102	hashtab_t role_tab;
1103
1104	role = (role_datum_t *) datum;
1105	if (state->dest_decl == NULL)
1106		role_tab = state->base->p_roles.table;
1107	else
1108		role_tab = state->dest_decl->p_roles.table;
1109
1110	dest_role = hashtab_search(role_tab, id);
1111	assert(dest_role != NULL);
1112
1113	if (state->verbose) {
1114		INFO(state->handle, "fixing role %s", id);
1115	}
1116
1117	ebitmap_init(&e_tmp);
1118	ebitmap_for_each_bit(&role->dominates, rnode, i) {
1119		if (ebitmap_node_get_bit(rnode, i)) {
1120			assert(mod->map[SYM_ROLES][i]);
1121			if (ebitmap_set_bit
1122			    (&e_tmp, mod->map[SYM_ROLES][i] - 1, 1)) {
1123				goto cleanup;
1124			}
1125		}
1126	}
1127	if (ebitmap_union(&dest_role->dominates, &e_tmp)) {
1128		goto cleanup;
1129	}
1130	if (type_set_or_convert(&role->types, &dest_role->types, mod, state)) {
1131		goto cleanup;
1132	}
1133	ebitmap_destroy(&e_tmp);
1134
1135	if (role->flavor == ROLE_ATTRIB) {
1136		ebitmap_init(&e_tmp);
1137		ebitmap_for_each_bit(&role->roles, rnode, i) {
1138			if (ebitmap_node_get_bit(rnode, i)) {
1139				assert(mod->map[SYM_ROLES][i]);
1140				if (ebitmap_set_bit
1141				    (&e_tmp, mod->map[SYM_ROLES][i] - 1, 1)) {
1142					goto cleanup;
1143				}
1144			}
1145		}
1146		if (ebitmap_union(&dest_role->roles, &e_tmp)) {
1147			goto cleanup;
1148		}
1149		ebitmap_destroy(&e_tmp);
1150	}
1151
1152	return 0;
1153
1154      cleanup:
1155	ERR(state->handle, "Out of memory!");
1156	ebitmap_destroy(&e_tmp);
1157	return -1;
1158}
1159
1160static int type_fix_callback(hashtab_key_t key, hashtab_datum_t datum,
1161			     void *data)
1162{
1163	unsigned int i;
1164	char *id = key;
1165	type_datum_t *type, *new_type = NULL;
1166	link_state_t *state = (link_state_t *) data;
1167	ebitmap_t e_tmp;
1168	policy_module_t *mod = state->cur;
1169	ebitmap_node_t *tnode;
1170	symtab_t *typetab;
1171
1172	type = (type_datum_t *) datum;
1173
1174	if (state->dest_decl == NULL)
1175		typetab = &state->base->p_types;
1176	else
1177		typetab = &state->dest_decl->p_types;
1178
1179	/* only fix attributes */
1180	if (type->flavor != TYPE_ATTRIB) {
1181		return 0;
1182	}
1183
1184	new_type = hashtab_search(typetab->table, id);
1185	assert(new_type != NULL && new_type->flavor == TYPE_ATTRIB);
1186
1187	if (state->verbose) {
1188		INFO(state->handle, "fixing attribute %s", id);
1189	}
1190
1191	ebitmap_init(&e_tmp);
1192	ebitmap_for_each_bit(&type->types, tnode, i) {
1193		if (ebitmap_node_get_bit(tnode, i)) {
1194			assert(mod->map[SYM_TYPES][i]);
1195			if (ebitmap_set_bit
1196			    (&e_tmp, mod->map[SYM_TYPES][i] - 1, 1)) {
1197				goto cleanup;
1198			}
1199		}
1200	}
1201	if (ebitmap_union(&new_type->types, &e_tmp)) {
1202		goto cleanup;
1203	}
1204	ebitmap_destroy(&e_tmp);
1205	return 0;
1206
1207      cleanup:
1208	ERR(state->handle, "Out of memory!");
1209	ebitmap_destroy(&e_tmp);
1210	return -1;
1211}
1212
1213static int user_fix_callback(hashtab_key_t key, hashtab_datum_t datum,
1214			     void *data)
1215{
1216	char *id = key;
1217	user_datum_t *user, *new_user = NULL;
1218	link_state_t *state = (link_state_t *) data;
1219	policy_module_t *mod = state->cur;
1220	symtab_t *usertab;
1221
1222	user = (user_datum_t *) datum;
1223
1224	if (state->dest_decl == NULL)
1225		usertab = &state->base->p_users;
1226	else
1227		usertab = &state->dest_decl->p_users;
1228
1229	new_user = hashtab_search(usertab->table, id);
1230	assert(new_user != NULL);
1231
1232	if (state->verbose) {
1233		INFO(state->handle, "fixing user %s", id);
1234	}
1235
1236	if (role_set_or_convert(&user->roles, &new_user->roles, mod, state)) {
1237		goto cleanup;
1238	}
1239
1240	if (mls_range_convert(&user->range, &new_user->range, mod, state))
1241		goto cleanup;
1242
1243	if (mls_level_convert(&user->dfltlevel, &new_user->dfltlevel, mod, state))
1244		goto cleanup;
1245
1246	return 0;
1247
1248      cleanup:
1249	ERR(state->handle, "Out of memory!");
1250	return -1;
1251}
1252
1253static int (*fix_callback_f[SYM_NUM]) (hashtab_key_t key, hashtab_datum_t datum,
1254				       void *datap) = {
1255NULL, NULL, role_fix_callback, type_fix_callback, user_fix_callback,
1256	    NULL, NULL, NULL};
1257
1258/*********** functions that copy AV rules ***********/
1259
1260static int copy_avrule_list(avrule_t * list, avrule_t ** dst,
1261			    policy_module_t * module, link_state_t * state)
1262{
1263	unsigned int i;
1264	avrule_t *cur, *new_rule = NULL, *tail;
1265	class_perm_node_t *cur_perm, *new_perm, *tail_perm = NULL;
1266
1267	tail = *dst;
1268	while (tail && tail->next) {
1269		tail = tail->next;
1270	}
1271
1272	cur = list;
1273	while (cur) {
1274		if ((new_rule = (avrule_t *) malloc(sizeof(avrule_t))) == NULL) {
1275			goto cleanup;
1276		}
1277		avrule_init(new_rule);
1278
1279		new_rule->specified = cur->specified;
1280		new_rule->flags = cur->flags;
1281		if (type_set_convert
1282		    (&cur->stypes, &new_rule->stypes, module, state) == -1
1283		    || type_set_convert(&cur->ttypes, &new_rule->ttypes, module,
1284					state) == -1) {
1285			goto cleanup;
1286		}
1287
1288		cur_perm = cur->perms;
1289		tail_perm = NULL;
1290		while (cur_perm) {
1291			if ((new_perm = (class_perm_node_t *)
1292			     malloc(sizeof(class_perm_node_t))) == NULL) {
1293				goto cleanup;
1294			}
1295			class_perm_node_init(new_perm);
1296
1297			new_perm->tclass =
1298			    module->map[SYM_CLASSES][cur_perm->tclass - 1];
1299			assert(new_perm->tclass);
1300
1301			if (new_rule->specified & AVRULE_AV) {
1302				for (i = 0;
1303				     i <
1304				     module->perm_map_len[cur_perm->tclass - 1];
1305				     i++) {
1306					if (!(cur_perm->data & (1U << i)))
1307						continue;
1308					new_perm->data |=
1309					    (1U <<
1310					     (module->
1311					      perm_map[cur_perm->tclass - 1][i] -
1312					      1));
1313				}
1314			} else {
1315				new_perm->data =
1316				    module->map[SYM_TYPES][cur_perm->data - 1];
1317			}
1318
1319			if (new_rule->perms == NULL) {
1320				new_rule->perms = new_perm;
1321			} else {
1322				assert(tail_perm);
1323				tail_perm->next = new_perm;
1324			}
1325			tail_perm = new_perm;
1326			cur_perm = cur_perm->next;
1327		}
1328		new_rule->line = cur->line;
1329		new_rule->source_line = cur->source_line;
1330		if (cur->source_filename) {
1331			new_rule->source_filename = strdup(cur->source_filename);
1332			if (!new_rule->source_filename)
1333				goto cleanup;
1334		}
1335
1336		cur = cur->next;
1337
1338		if (*dst == NULL) {
1339			*dst = new_rule;
1340		} else {
1341			tail->next = new_rule;
1342		}
1343		tail = new_rule;
1344	}
1345
1346	return 0;
1347      cleanup:
1348	ERR(state->handle, "Out of memory!");
1349	avrule_destroy(new_rule);
1350	free(new_rule);
1351	return -1;
1352}
1353
1354static int copy_role_trans_list(role_trans_rule_t * list,
1355				role_trans_rule_t ** dst,
1356				policy_module_t * module, link_state_t * state)
1357{
1358	role_trans_rule_t *cur, *new_rule = NULL, *tail;
1359	unsigned int i;
1360	ebitmap_node_t *cnode;
1361
1362	cur = list;
1363	tail = *dst;
1364	while (tail && tail->next) {
1365		tail = tail->next;
1366	}
1367	while (cur) {
1368		if ((new_rule =
1369		     (role_trans_rule_t *) malloc(sizeof(role_trans_rule_t))) ==
1370		    NULL) {
1371			goto cleanup;
1372		}
1373		role_trans_rule_init(new_rule);
1374
1375		if (role_set_or_convert
1376		    (&cur->roles, &new_rule->roles, module, state)
1377		    || type_set_or_convert(&cur->types, &new_rule->types,
1378					   module, state)) {
1379			goto cleanup;
1380		}
1381
1382		ebitmap_for_each_bit(&cur->classes, cnode, i) {
1383			if (ebitmap_node_get_bit(cnode, i)) {
1384				assert(module->map[SYM_CLASSES][i]);
1385				if (ebitmap_set_bit(&new_rule->classes,
1386						    module->
1387						    map[SYM_CLASSES][i] - 1,
1388						    1)) {
1389					goto cleanup;
1390				}
1391			}
1392		}
1393
1394		new_rule->new_role = module->map[SYM_ROLES][cur->new_role - 1];
1395
1396		if (*dst == NULL) {
1397			*dst = new_rule;
1398		} else {
1399			tail->next = new_rule;
1400		}
1401		tail = new_rule;
1402		cur = cur->next;
1403	}
1404	return 0;
1405      cleanup:
1406	ERR(state->handle, "Out of memory!");
1407	role_trans_rule_list_destroy(new_rule);
1408	return -1;
1409}
1410
1411static int copy_role_allow_list(role_allow_rule_t * list,
1412				role_allow_rule_t ** dst,
1413				policy_module_t * module, link_state_t * state)
1414{
1415	role_allow_rule_t *cur, *new_rule = NULL, *tail;
1416
1417	cur = list;
1418	tail = *dst;
1419	while (tail && tail->next) {
1420		tail = tail->next;
1421	}
1422
1423	while (cur) {
1424		if ((new_rule =
1425		     (role_allow_rule_t *) malloc(sizeof(role_allow_rule_t))) ==
1426		    NULL) {
1427			goto cleanup;
1428		}
1429		role_allow_rule_init(new_rule);
1430
1431		if (role_set_or_convert
1432		    (&cur->roles, &new_rule->roles, module, state)
1433		    || role_set_or_convert(&cur->new_roles,
1434					   &new_rule->new_roles, module,
1435					   state)) {
1436			goto cleanup;
1437		}
1438		if (*dst == NULL) {
1439			*dst = new_rule;
1440		} else {
1441			tail->next = new_rule;
1442		}
1443		tail = new_rule;
1444		cur = cur->next;
1445	}
1446	return 0;
1447      cleanup:
1448	ERR(state->handle, "Out of memory!");
1449	role_allow_rule_list_destroy(new_rule);
1450	return -1;
1451}
1452
1453static int copy_filename_trans_list(filename_trans_rule_t * list,
1454				    filename_trans_rule_t ** dst,
1455				    policy_module_t * module,
1456				    link_state_t * state)
1457{
1458	filename_trans_rule_t *cur, *new_rule, *tail;
1459
1460	cur = list;
1461	tail = *dst;
1462	while (tail && tail->next)
1463		tail = tail->next;
1464
1465	while (cur) {
1466		new_rule = malloc(sizeof(*new_rule));
1467		if (!new_rule)
1468			goto err;
1469
1470		filename_trans_rule_init(new_rule);
1471
1472		if (*dst == NULL)
1473			*dst = new_rule;
1474		else
1475			tail->next = new_rule;
1476		tail = new_rule;
1477
1478		new_rule->name = strdup(cur->name);
1479		if (!new_rule->name)
1480			goto err;
1481
1482		if (type_set_or_convert(&cur->stypes, &new_rule->stypes, module, state) ||
1483		    type_set_or_convert(&cur->ttypes, &new_rule->ttypes, module, state))
1484			goto err;
1485
1486		new_rule->tclass = module->map[SYM_CLASSES][cur->tclass - 1];
1487		new_rule->otype = module->map[SYM_TYPES][cur->otype - 1];
1488
1489		cur = cur->next;
1490	}
1491	return 0;
1492err:
1493	ERR(state->handle, "Out of memory!");
1494	return -1;
1495}
1496
1497static int copy_range_trans_list(range_trans_rule_t * rules,
1498				 range_trans_rule_t ** dst,
1499				 policy_module_t * mod, link_state_t * state)
1500{
1501	range_trans_rule_t *rule, *new_rule = NULL;
1502	unsigned int i;
1503	ebitmap_node_t *cnode;
1504
1505	for (rule = rules; rule; rule = rule->next) {
1506		new_rule =
1507		    (range_trans_rule_t *) malloc(sizeof(range_trans_rule_t));
1508		if (!new_rule)
1509			goto cleanup;
1510
1511		range_trans_rule_init(new_rule);
1512
1513		new_rule->next = *dst;
1514		*dst = new_rule;
1515
1516		if (type_set_convert(&rule->stypes, &new_rule->stypes,
1517				     mod, state))
1518			goto cleanup;
1519
1520		if (type_set_convert(&rule->ttypes, &new_rule->ttypes,
1521				     mod, state))
1522			goto cleanup;
1523
1524		ebitmap_for_each_bit(&rule->tclasses, cnode, i) {
1525			if (ebitmap_node_get_bit(cnode, i)) {
1526				assert(mod->map[SYM_CLASSES][i]);
1527				if (ebitmap_set_bit
1528				    (&new_rule->tclasses,
1529				     mod->map[SYM_CLASSES][i] - 1, 1)) {
1530					goto cleanup;
1531				}
1532			}
1533		}
1534
1535		if (mls_range_convert(&rule->trange, &new_rule->trange, mod, state))
1536			goto cleanup;
1537	}
1538	return 0;
1539
1540      cleanup:
1541	ERR(state->handle, "Out of memory!");
1542	range_trans_rule_list_destroy(new_rule);
1543	return -1;
1544}
1545
1546static int copy_cond_list(cond_node_t * list, cond_node_t ** dst,
1547			  policy_module_t * module, link_state_t * state)
1548{
1549	unsigned i;
1550	cond_node_t *cur, *new_node = NULL, *tail;
1551	cond_expr_t *cur_expr;
1552	tail = *dst;
1553	while (tail && tail->next)
1554		tail = tail->next;
1555
1556	cur = list;
1557	while (cur) {
1558		new_node = (cond_node_t *) malloc(sizeof(cond_node_t));
1559		if (!new_node) {
1560			goto cleanup;
1561		}
1562		memset(new_node, 0, sizeof(cond_node_t));
1563
1564		new_node->cur_state = cur->cur_state;
1565		new_node->expr = cond_copy_expr(cur->expr);
1566		if (!new_node->expr)
1567			goto cleanup;
1568		/* go back through and remap the expression */
1569		for (cur_expr = new_node->expr; cur_expr != NULL;
1570		     cur_expr = cur_expr->next) {
1571			/* expression nodes don't have a bool value of 0 - don't map them */
1572			if (cur_expr->expr_type != COND_BOOL)
1573				continue;
1574			assert(module->map[SYM_BOOLS][cur_expr->bool - 1] != 0);
1575			cur_expr->bool =
1576			    module->map[SYM_BOOLS][cur_expr->bool - 1];
1577		}
1578		new_node->nbools = cur->nbools;
1579		/* FIXME should COND_MAX_BOOLS be used here? */
1580		for (i = 0; i < min(cur->nbools, COND_MAX_BOOLS); i++) {
1581			uint32_t remapped_id =
1582			    module->map[SYM_BOOLS][cur->bool_ids[i] - 1];
1583			assert(remapped_id != 0);
1584			new_node->bool_ids[i] = remapped_id;
1585		}
1586		new_node->expr_pre_comp = cur->expr_pre_comp;
1587
1588		if (copy_avrule_list
1589		    (cur->avtrue_list, &new_node->avtrue_list, module, state)
1590		    || copy_avrule_list(cur->avfalse_list,
1591					&new_node->avfalse_list, module,
1592					state)) {
1593			goto cleanup;
1594		}
1595
1596		if (*dst == NULL) {
1597			*dst = new_node;
1598		} else {
1599			tail->next = new_node;
1600		}
1601		tail = new_node;
1602		cur = cur->next;
1603	}
1604	return 0;
1605      cleanup:
1606	ERR(state->handle, "Out of memory!");
1607	cond_node_destroy(new_node);
1608	free(new_node);
1609	return -1;
1610
1611}
1612
1613/*********** functions that copy avrule_decls from module to base ***********/
1614
1615static int copy_identifiers(link_state_t * state, symtab_t * src_symtab,
1616			    avrule_decl_t * dest_decl)
1617{
1618	int i, ret;
1619
1620	state->dest_decl = dest_decl;
1621	for (i = 0; i < SYM_NUM; i++) {
1622		if (copy_callback_f[i] != NULL) {
1623			ret =
1624			    hashtab_map(src_symtab[i].table, copy_callback_f[i],
1625					state);
1626			if (ret) {
1627				return ret;
1628			}
1629		}
1630	}
1631
1632	if (hashtab_map(src_symtab[SYM_TYPES].table,
1633			type_bounds_copy_callback, state))
1634		return -1;
1635
1636	if (hashtab_map(src_symtab[SYM_TYPES].table,
1637			alias_copy_callback, state))
1638		return -1;
1639
1640	if (hashtab_map(src_symtab[SYM_ROLES].table,
1641			role_bounds_copy_callback, state))
1642		return -1;
1643
1644	if (hashtab_map(src_symtab[SYM_USERS].table,
1645			user_bounds_copy_callback, state))
1646		return -1;
1647
1648	/* then fix bitmaps associated with those newly copied identifiers */
1649	for (i = 0; i < SYM_NUM; i++) {
1650		if (fix_callback_f[i] != NULL &&
1651		    hashtab_map(src_symtab[i].table, fix_callback_f[i],
1652				state)) {
1653			return -1;
1654		}
1655	}
1656	return 0;
1657}
1658
1659static int copy_scope_index(scope_index_t * src, scope_index_t * dest,
1660			    policy_module_t * module, link_state_t * state)
1661{
1662	unsigned int i, j;
1663	uint32_t largest_mapped_class_value = 0;
1664	ebitmap_node_t *node;
1665	/* copy the scoping information for this avrule decl block */
1666	for (i = 0; i < SYM_NUM; i++) {
1667		ebitmap_t *srcmap = src->scope + i;
1668		ebitmap_t *destmap = dest->scope + i;
1669		if (copy_callback_f[i] == NULL) {
1670			continue;
1671		}
1672		ebitmap_for_each_bit(srcmap, node, j) {
1673			if (ebitmap_node_get_bit(node, j)) {
1674				assert(module->map[i][j] != 0);
1675				if (ebitmap_set_bit
1676				    (destmap, module->map[i][j] - 1, 1) != 0) {
1677
1678					goto cleanup;
1679				}
1680				if (i == SYM_CLASSES &&
1681				    largest_mapped_class_value <
1682				    module->map[SYM_CLASSES][j]) {
1683					largest_mapped_class_value =
1684					    module->map[SYM_CLASSES][j];
1685				}
1686			}
1687		}
1688	}
1689
1690	/* next copy the enabled permissions data  */
1691	if ((dest->class_perms_map = malloc(largest_mapped_class_value *
1692					    sizeof(*dest->class_perms_map))) ==
1693	    NULL) {
1694		goto cleanup;
1695	}
1696	for (i = 0; i < largest_mapped_class_value; i++) {
1697		ebitmap_init(dest->class_perms_map + i);
1698	}
1699	dest->class_perms_len = largest_mapped_class_value;
1700	for (i = 0; i < src->class_perms_len; i++) {
1701		ebitmap_t *srcmap = src->class_perms_map + i;
1702		ebitmap_t *destmap =
1703		    dest->class_perms_map + module->map[SYM_CLASSES][i] - 1;
1704		ebitmap_for_each_bit(srcmap, node, j) {
1705			if (ebitmap_node_get_bit(node, j) &&
1706			    ebitmap_set_bit(destmap, module->perm_map[i][j] - 1,
1707					    1)) {
1708				goto cleanup;
1709			}
1710		}
1711	}
1712
1713	return 0;
1714
1715      cleanup:
1716	ERR(state->handle, "Out of memory!");
1717	return -1;
1718}
1719
1720static int copy_avrule_decl(link_state_t * state, policy_module_t * module,
1721			    avrule_decl_t * src_decl, avrule_decl_t * dest_decl)
1722{
1723	int ret;
1724
1725	/* copy all of the RBAC and TE rules */
1726	if (copy_avrule_list
1727	    (src_decl->avrules, &dest_decl->avrules, module, state) == -1
1728	    || copy_role_trans_list(src_decl->role_tr_rules,
1729				    &dest_decl->role_tr_rules, module,
1730				    state) == -1
1731	    || copy_role_allow_list(src_decl->role_allow_rules,
1732				    &dest_decl->role_allow_rules, module,
1733				    state) == -1
1734	    || copy_cond_list(src_decl->cond_list, &dest_decl->cond_list,
1735			      module, state) == -1) {
1736		return -1;
1737	}
1738
1739	if (copy_filename_trans_list(src_decl->filename_trans_rules,
1740				     &dest_decl->filename_trans_rules,
1741				     module, state))
1742		return -1;
1743
1744	if (copy_range_trans_list(src_decl->range_tr_rules,
1745				  &dest_decl->range_tr_rules, module, state))
1746		return -1;
1747
1748	/* finally copy any identifiers local to this declaration */
1749	ret = copy_identifiers(state, src_decl->symtab, dest_decl);
1750	if (ret < 0) {
1751		return ret;
1752	}
1753
1754	/* then copy required and declared scope indices here */
1755	if (copy_scope_index(&src_decl->required, &dest_decl->required,
1756			     module, state) == -1 ||
1757	    copy_scope_index(&src_decl->declared, &dest_decl->declared,
1758			     module, state) == -1) {
1759		return -1;
1760	}
1761
1762	return 0;
1763}
1764
1765static int copy_avrule_block(link_state_t * state, policy_module_t * module,
1766			     avrule_block_t * block)
1767{
1768	avrule_block_t *new_block = avrule_block_create();
1769	avrule_decl_t *decl, *last_decl = NULL;
1770	int ret;
1771
1772	if (new_block == NULL) {
1773		ERR(state->handle, "Out of memory!");
1774		ret = -1;
1775		goto cleanup;
1776	}
1777
1778	new_block->flags = block->flags;
1779
1780	for (decl = block->branch_list; decl != NULL; decl = decl->next) {
1781		avrule_decl_t *new_decl =
1782		    avrule_decl_create(state->next_decl_id);
1783		if (new_decl == NULL) {
1784			ERR(state->handle, "Out of memory!");
1785			ret = -1;
1786			goto cleanup;
1787		}
1788
1789		if (module->policy->name != NULL) {
1790			new_decl->module_name = strdup(module->policy->name);
1791			if (new_decl->module_name == NULL) {
1792				ERR(state->handle, "Out of memory\n");
1793				avrule_decl_destroy(new_decl);
1794				ret = -1;
1795				goto cleanup;
1796			}
1797		}
1798
1799		if (last_decl == NULL) {
1800			new_block->branch_list = new_decl;
1801		} else {
1802			last_decl->next = new_decl;
1803		}
1804		last_decl = new_decl;
1805		state->base->decl_val_to_struct[state->next_decl_id - 1] =
1806		    new_decl;
1807		state->decl_to_mod[state->next_decl_id] = module->policy;
1808
1809		module->avdecl_map[decl->decl_id] = new_decl->decl_id;
1810
1811		ret = copy_avrule_decl(state, module, decl, new_decl);
1812		if (ret) {
1813			avrule_decl_destroy(new_decl);
1814			goto cleanup;
1815		}
1816
1817		state->next_decl_id++;
1818	}
1819	state->last_avrule_block->next = new_block;
1820	state->last_avrule_block = new_block;
1821	return 0;
1822
1823      cleanup:
1824	avrule_block_list_destroy(new_block);
1825	return ret;
1826}
1827
1828static int scope_copy_callback(hashtab_key_t key, hashtab_datum_t datum,
1829			       void *data)
1830{
1831	unsigned int i;
1832	int ret;
1833	char *id = key, *new_id = NULL;
1834	scope_datum_t *scope, *base_scope;
1835	link_state_t *state = (link_state_t *) data;
1836	uint32_t symbol_num = state->symbol_num;
1837	uint32_t *avdecl_map = state->cur->avdecl_map;
1838
1839	scope = (scope_datum_t *) datum;
1840
1841	/* check if the base already has a scope entry */
1842	base_scope = hashtab_search(state->base->scope[symbol_num].table, id);
1843	if (base_scope == NULL) {
1844		scope_datum_t *new_scope;
1845		if ((new_id = strdup(id)) == NULL) {
1846			goto cleanup;
1847		}
1848
1849		if ((new_scope =
1850		     (scope_datum_t *) calloc(1, sizeof(*new_scope))) == NULL) {
1851			free(new_id);
1852			goto cleanup;
1853		}
1854		ret = hashtab_insert(state->base->scope[symbol_num].table,
1855				     (hashtab_key_t) new_id,
1856				     (hashtab_datum_t) new_scope);
1857		if (ret) {
1858			free(new_id);
1859			free(new_scope);
1860			goto cleanup;
1861		}
1862		new_scope->scope = SCOPE_REQ;	/* this is reset further down */
1863		base_scope = new_scope;
1864	}
1865	if (base_scope->scope == SCOPE_REQ && scope->scope == SCOPE_DECL) {
1866		/* this module declared symbol, so overwrite the old
1867		 * list with the new decl ids */
1868		base_scope->scope = SCOPE_DECL;
1869		free(base_scope->decl_ids);
1870		base_scope->decl_ids = NULL;
1871		base_scope->decl_ids_len = 0;
1872		for (i = 0; i < scope->decl_ids_len; i++) {
1873			if (add_i_to_a(avdecl_map[scope->decl_ids[i]],
1874				       &base_scope->decl_ids_len,
1875				       &base_scope->decl_ids) == -1) {
1876				goto cleanup;
1877			}
1878		}
1879	} else if (base_scope->scope == SCOPE_DECL && scope->scope == SCOPE_REQ) {
1880		/* this module depended on a symbol that now exists,
1881		 * so don't do anything */
1882	} else if (base_scope->scope == SCOPE_REQ && scope->scope == SCOPE_REQ) {
1883		/* symbol is still required, so add to the list */
1884		for (i = 0; i < scope->decl_ids_len; i++) {
1885			if (add_i_to_a(avdecl_map[scope->decl_ids[i]],
1886				       &base_scope->decl_ids_len,
1887				       &base_scope->decl_ids) == -1) {
1888				goto cleanup;
1889			}
1890		}
1891	} else {
1892		/* this module declared a symbol, and it was already
1893		 * declared.  only roles and users may be multiply
1894		 * declared; for all others this is an error. */
1895		if (symbol_num != SYM_ROLES && symbol_num != SYM_USERS) {
1896			ERR(state->handle,
1897			    "%s: Duplicate declaration in module: %s %s",
1898			    state->cur_mod_name,
1899			    symtab_names[state->symbol_num], id);
1900			return -1;
1901		}
1902		for (i = 0; i < scope->decl_ids_len; i++) {
1903			if (add_i_to_a(avdecl_map[scope->decl_ids[i]],
1904				       &base_scope->decl_ids_len,
1905				       &base_scope->decl_ids) == -1) {
1906				goto cleanup;
1907			}
1908		}
1909	}
1910	return 0;
1911
1912      cleanup:
1913	ERR(state->handle, "Out of memory!");
1914	return -1;
1915}
1916
1917/* Copy a module over to a base, remapping all values within.  After
1918 * all identifiers and rules are done, copy the scoping information.
1919 * This is when it checks for duplicate declarations. */
1920static int copy_module(link_state_t * state, policy_module_t * module)
1921{
1922	int i, ret;
1923	avrule_block_t *cur;
1924	state->cur = module;
1925	state->cur_mod_name = module->policy->name;
1926
1927	/* first copy all of the identifiers */
1928	ret = copy_identifiers(state, module->policy->symtab, NULL);
1929	if (ret) {
1930		return ret;
1931	}
1932
1933	/* next copy all of the avrule blocks */
1934	for (cur = module->policy->global; cur != NULL; cur = cur->next) {
1935		ret = copy_avrule_block(state, module, cur);
1936		if (ret) {
1937			return ret;
1938		}
1939	}
1940
1941	/* then copy the scoping tables */
1942	for (i = 0; i < SYM_NUM; i++) {
1943		state->symbol_num = i;
1944		if (hashtab_map
1945		    (module->policy->scope[i].table, scope_copy_callback,
1946		     state)) {
1947			return -1;
1948		}
1949	}
1950
1951	return 0;
1952}
1953
1954/***** functions that check requirements and enable blocks in a module ******/
1955
1956/* borrowed from checkpolicy.c */
1957
1958struct find_perm_arg {
1959	unsigned int valuep;
1960	hashtab_key_t key;
1961};
1962
1963static int find_perm(hashtab_key_t key, hashtab_datum_t datum, void *varg)
1964{
1965
1966	struct find_perm_arg *arg = varg;
1967
1968	perm_datum_t *perdatum = (perm_datum_t *) datum;
1969	if (arg->valuep == perdatum->s.value) {
1970		arg->key = key;
1971		return 1;
1972	}
1973
1974	return 0;
1975}
1976
1977/* Check if the requirements are met for a single declaration.  If all
1978 * are met return 1.  For the first requirement found to be missing,
1979 * if 'missing_sym_num' and 'missing_value' are both not NULL then
1980 * write to them the symbol number and value for the missing
1981 * declaration.  Then return 0 to indicate a missing declaration.
1982 * Note that if a declaration had no requirement at all (e.g., an ELSE
1983 * block) this returns 1. */
1984static int is_decl_requires_met(link_state_t * state,
1985				avrule_decl_t * decl,
1986				struct missing_requirement *req)
1987{
1988	/* (This algorithm is very unoptimized.  It performs many
1989	 * redundant checks.  A very obvious improvement is to cache
1990	 * which symbols have been verified, so that they do not need
1991	 * to be re-checked.) */
1992	unsigned int i, j;
1993	ebitmap_t *bitmap;
1994	char *id, *perm_id;
1995	policydb_t *pol = state->base;
1996	ebitmap_node_t *node;
1997
1998	/* check that all symbols have been satisfied */
1999	for (i = 0; i < SYM_NUM; i++) {
2000		if (i == SYM_CLASSES) {
2001			/* classes will be checked during permissions
2002			 * checking phase below */
2003			continue;
2004		}
2005		bitmap = &decl->required.scope[i];
2006		ebitmap_for_each_bit(bitmap, node, j) {
2007			if (!ebitmap_node_get_bit(node, j)) {
2008				continue;
2009			}
2010
2011			/* check base's scope table */
2012			id = pol->sym_val_to_name[i][j];
2013			if (!is_id_enabled(id, state->base, i)) {
2014				/* this symbol was not found */
2015				if (req != NULL) {
2016					req->symbol_type = i;
2017					req->symbol_value = j + 1;
2018				}
2019				return 0;
2020			}
2021		}
2022	}
2023	/* check that all classes and permissions have been satisfied */
2024	for (i = 0; i < decl->required.class_perms_len; i++) {
2025
2026		bitmap = decl->required.class_perms_map + i;
2027		ebitmap_for_each_bit(bitmap, node, j) {
2028			struct find_perm_arg fparg;
2029			class_datum_t *cladatum;
2030			uint32_t perm_value = j + 1;
2031			int rc;
2032			scope_datum_t *scope;
2033
2034			if (!ebitmap_node_get_bit(node, j)) {
2035				continue;
2036			}
2037			id = pol->p_class_val_to_name[i];
2038			cladatum = pol->class_val_to_struct[i];
2039
2040			scope =
2041			    hashtab_search(state->base->p_classes_scope.table,
2042					   id);
2043			if (scope == NULL) {
2044				ERR(state->handle,
2045				    "Could not find scope information for class %s",
2046				    id);
2047				return -1;
2048			}
2049
2050			fparg.valuep = perm_value;
2051			fparg.key = NULL;
2052
2053			(void)hashtab_map(cladatum->permissions.table, find_perm,
2054				    &fparg);
2055			if (fparg.key == NULL && cladatum->comdatum != NULL) {
2056				rc = hashtab_map(cladatum->comdatum->permissions.table,
2057						 find_perm, &fparg);
2058				assert(rc == 1);
2059			}
2060			perm_id = fparg.key;
2061
2062			assert(perm_id != NULL);
2063			if (!is_perm_enabled(id, perm_id, state->base)) {
2064				if (req != NULL) {
2065					req->symbol_type = SYM_CLASSES;
2066					req->symbol_value = i + 1;
2067					req->perm_value = perm_value;
2068				}
2069				return 0;
2070			}
2071		}
2072	}
2073
2074	/* all requirements have been met */
2075	return 1;
2076}
2077
2078static int debug_requirements(link_state_t * state, policydb_t * p)
2079{
2080	int ret;
2081	avrule_block_t *cur;
2082	missing_requirement_t req;
2083	memset(&req, 0, sizeof(req));
2084
2085	for (cur = p->global; cur != NULL; cur = cur->next) {
2086		if (cur->enabled != NULL)
2087			continue;
2088
2089		ret = is_decl_requires_met(state, cur->branch_list, &req);
2090		if (ret < 0) {
2091			return ret;
2092		} else if (ret == 0) {
2093			const char *mod_name = cur->branch_list->module_name ?
2094			    cur->branch_list->module_name : "BASE";
2095			if (req.symbol_type == SYM_CLASSES) {
2096				struct find_perm_arg fparg;
2097
2098				class_datum_t *cladatum;
2099				cladatum = p->class_val_to_struct[req.symbol_value - 1];
2100
2101				fparg.valuep = req.perm_value;
2102				fparg.key = NULL;
2103				(void)hashtab_map(cladatum->permissions.table,
2104						  find_perm, &fparg);
2105
2106				if (cur->flags & AVRULE_OPTIONAL) {
2107					ERR(state->handle,
2108					    "%s[%d]'s optional requirements were not met: class %s, permission %s",
2109					    mod_name, cur->branch_list->decl_id,
2110					    p->p_class_val_to_name[req.symbol_value - 1],
2111					    fparg.key);
2112				} else {
2113					ERR(state->handle,
2114					    "%s[%d]'s global requirements were not met: class %s, permission %s",
2115					    mod_name, cur->branch_list->decl_id,
2116					    p->p_class_val_to_name[req.symbol_value - 1],
2117					    fparg.key);
2118				}
2119			} else {
2120				if (cur->flags & AVRULE_OPTIONAL) {
2121					ERR(state->handle,
2122					    "%s[%d]'s optional requirements were not met: %s %s",
2123					    mod_name, cur->branch_list->decl_id,
2124					    symtab_names[req.symbol_type],
2125					    p->sym_val_to_name[req.
2126							       symbol_type][req.
2127									    symbol_value
2128									    -
2129									    1]);
2130				} else {
2131					ERR(state->handle,
2132					    "%s[%d]'s global requirements were not met: %s %s",
2133					    mod_name, cur->branch_list->decl_id,
2134					    symtab_names[req.symbol_type],
2135					    p->sym_val_to_name[req.
2136							       symbol_type][req.
2137									    symbol_value
2138									    -
2139									    1]);
2140				}
2141			}
2142		}
2143	}
2144	return 0;
2145}
2146
2147static void print_missing_requirements(link_state_t * state,
2148				       avrule_block_t * cur,
2149				       missing_requirement_t * req)
2150{
2151	policydb_t *p = state->base;
2152	const char *mod_name = cur->branch_list->module_name ?
2153	    cur->branch_list->module_name : "BASE";
2154
2155	if (req->symbol_type == SYM_CLASSES) {
2156
2157		struct find_perm_arg fparg;
2158
2159		class_datum_t *cladatum;
2160		cladatum = p->class_val_to_struct[req->symbol_value - 1];
2161
2162		fparg.valuep = req->perm_value;
2163		fparg.key = NULL;
2164		(void)hashtab_map(cladatum->permissions.table, find_perm, &fparg);
2165
2166		ERR(state->handle,
2167		    "%s's global requirements were not met: class %s, permission %s",
2168		    mod_name,
2169		    p->p_class_val_to_name[req->symbol_value - 1], fparg.key);
2170	} else {
2171		ERR(state->handle,
2172		    "%s's global requirements were not met: %s %s",
2173		    mod_name,
2174		    symtab_names[req->symbol_type],
2175		    p->sym_val_to_name[req->symbol_type][req->symbol_value - 1]);
2176	}
2177}
2178
2179/* Enable all of the avrule_decl blocks for the policy. This simple
2180 * algorithm is the following:
2181 *
2182 * 1) Enable all of the non-else avrule_decls for all blocks.
2183 * 2) Iterate through the non-else decls looking for decls whose requirements
2184 *    are not met.
2185 *    2a) If the decl is non-optional, return immediately with an error.
2186 *    2b) If the decl is optional, disable the block and mark changed = 1
2187 * 3) If changed == 1 goto 2.
2188 * 4) Iterate through all blocks looking for those that have no enabled
2189 *    decl. If the block has an else decl, enable.
2190 *
2191 * This will correctly handle all dependencies, including mutual and
2192 * cicular. The only downside is that it is slow.
2193 */
2194static int enable_avrules(link_state_t * state, policydb_t * pol)
2195{
2196	int changed = 1;
2197	avrule_block_t *block;
2198	avrule_decl_t *decl;
2199	missing_requirement_t req;
2200	int ret = 0, rc;
2201
2202	if (state->verbose) {
2203		INFO(state->handle, "Determining which avrules to enable.");
2204	}
2205
2206	/* 1) enable all of the non-else blocks */
2207	for (block = pol->global; block != NULL; block = block->next) {
2208		block->enabled = block->branch_list;
2209		block->enabled->enabled = 1;
2210		for (decl = block->branch_list->next; decl != NULL;
2211		     decl = decl->next)
2212			decl->enabled = 0;
2213	}
2214
2215	/* 2) Iterate */
2216	while (changed) {
2217		changed = 0;
2218		for (block = pol->global; block != NULL; block = block->next) {
2219			if (block->enabled == NULL) {
2220				continue;
2221			}
2222			decl = block->branch_list;
2223			if (state->verbose) {
2224				const char *mod_name = decl->module_name ?
2225				    decl->module_name : "BASE";
2226				INFO(state->handle, "check module %s decl %d\n",
2227				     mod_name, decl->decl_id);
2228			}
2229			rc = is_decl_requires_met(state, decl, &req);
2230			if (rc < 0) {
2231				ret = SEPOL_ERR;
2232				goto out;
2233			} else if (rc == 0) {
2234				decl->enabled = 0;
2235				block->enabled = NULL;
2236				changed = 1;
2237				if (!(block->flags & AVRULE_OPTIONAL)) {
2238					print_missing_requirements(state, block,
2239								   &req);
2240					ret = SEPOL_EREQ;
2241					goto out;
2242				}
2243			}
2244		}
2245	}
2246
2247	/* 4) else handling
2248	 *
2249	 * Iterate through all of the blocks skipping the first (which is the
2250	 * global block, is required to be present, and cannot have an else).
2251	 * If the block is disabled and has an else decl, enable that.
2252	 *
2253	 * This code assumes that the second block in the branch list is the else
2254	 * block. This is currently supported by the compiler.
2255	 */
2256	for (block = pol->global->next; block != NULL; block = block->next) {
2257		if (block->enabled == NULL) {
2258			if (block->branch_list->next != NULL) {
2259				block->enabled = block->branch_list->next;
2260				block->branch_list->next->enabled = 1;
2261			}
2262		}
2263	}
2264
2265      out:
2266	if (state->verbose)
2267		debug_requirements(state, pol);
2268
2269	return ret;
2270}
2271
2272/*********** the main linking functions ***********/
2273
2274/* Given a module's policy, normalize all conditional expressions
2275 * within.  Return 0 on success, -1 on error. */
2276static int cond_normalize(policydb_t * p)
2277{
2278	avrule_block_t *block;
2279	for (block = p->global; block != NULL; block = block->next) {
2280		avrule_decl_t *decl;
2281		for (decl = block->branch_list; decl != NULL; decl = decl->next) {
2282			cond_list_t *cond = decl->cond_list;
2283			while (cond) {
2284				if (cond_normalize_expr(p, cond) < 0)
2285					return -1;
2286				cond = cond->next;
2287			}
2288		}
2289	}
2290	return 0;
2291}
2292
2293/* Allocate space for the various remapping arrays. */
2294static int prepare_module(link_state_t * state, policy_module_t * module)
2295{
2296	int i;
2297	uint32_t items, num_decls = 0;
2298	avrule_block_t *cur;
2299
2300	/* allocate the maps */
2301	for (i = 0; i < SYM_NUM; i++) {
2302		items = module->policy->symtab[i].nprim;
2303		if ((module->map[i] =
2304		     (uint32_t *) calloc(items,
2305					 sizeof(*module->map[i]))) == NULL) {
2306			ERR(state->handle, "Out of memory!");
2307			return -1;
2308		}
2309	}
2310
2311	/* allocate the permissions remap here */
2312	items = module->policy->p_classes.nprim;
2313	if ((module->perm_map_len =
2314	     calloc(items, sizeof(*module->perm_map_len))) == NULL) {
2315		ERR(state->handle, "Out of memory!");
2316		return -1;
2317	}
2318	if ((module->perm_map =
2319	     calloc(items, sizeof(*module->perm_map))) == NULL) {
2320		ERR(state->handle, "Out of memory!");
2321		return -1;
2322	}
2323
2324	/* allocate a map for avrule_decls */
2325	for (cur = module->policy->global; cur != NULL; cur = cur->next) {
2326		avrule_decl_t *decl;
2327		for (decl = cur->branch_list; decl != NULL; decl = decl->next) {
2328			if (decl->decl_id > num_decls) {
2329				num_decls = decl->decl_id;
2330			}
2331		}
2332	}
2333	num_decls++;
2334	if ((module->avdecl_map = calloc(num_decls, sizeof(uint32_t))) == NULL) {
2335		ERR(state->handle, "Out of memory!");
2336		return -1;
2337	}
2338	module->num_decls = num_decls;
2339
2340	/* normalize conditionals within */
2341	if (cond_normalize(module->policy) < 0) {
2342		ERR(state->handle,
2343		    "Error while normalizing conditionals within the module %s.",
2344		    module->policy->name);
2345		return -1;
2346	}
2347	return 0;
2348}
2349
2350static int prepare_base(link_state_t * state, uint32_t num_mod_decls)
2351{
2352	avrule_block_t *cur = state->base->global;
2353	assert(cur != NULL);
2354	state->next_decl_id = 0;
2355
2356	/* iterate through all of the declarations in the base, to
2357	   determine what the next decl_id should be */
2358	while (cur != NULL) {
2359		avrule_decl_t *decl;
2360		for (decl = cur->branch_list; decl != NULL; decl = decl->next) {
2361			if (decl->decl_id > state->next_decl_id) {
2362				state->next_decl_id = decl->decl_id;
2363			}
2364		}
2365		state->last_avrule_block = cur;
2366		cur = cur->next;
2367	}
2368	state->last_base_avrule_block = state->last_avrule_block;
2369	state->next_decl_id++;
2370
2371	/* allocate the table mapping from base's decl_id to its
2372	 * avrule_decls and set the initial mappings */
2373	free(state->base->decl_val_to_struct);
2374	if ((state->base->decl_val_to_struct =
2375	     calloc(state->next_decl_id + num_mod_decls,
2376		    sizeof(*(state->base->decl_val_to_struct)))) == NULL) {
2377		ERR(state->handle, "Out of memory!");
2378		return -1;
2379	}
2380	/* This allocates the decl block to module mapping used for error reporting */
2381	if ((state->decl_to_mod = calloc(state->next_decl_id + num_mod_decls,
2382					 sizeof(*(state->decl_to_mod)))) ==
2383	    NULL) {
2384		ERR(state->handle, "Out of memory!");
2385		return -1;
2386	}
2387	cur = state->base->global;
2388	while (cur != NULL) {
2389		avrule_decl_t *decl = cur->branch_list;
2390		while (decl != NULL) {
2391			state->base->decl_val_to_struct[decl->decl_id - 1] =
2392			    decl;
2393			state->decl_to_mod[decl->decl_id] = state->base;
2394			decl = decl->next;
2395		}
2396		cur = cur->next;
2397	}
2398
2399	/* normalize conditionals within */
2400	if (cond_normalize(state->base) < 0) {
2401		ERR(state->handle,
2402		    "Error while normalizing conditionals within the base module.");
2403		return -1;
2404	}
2405	return 0;
2406}
2407
2408static int expand_role_attributes(hashtab_key_t key, hashtab_datum_t datum,
2409				  void * data)
2410{
2411	char *id;
2412	role_datum_t *role, *sub_attr;
2413	link_state_t *state;
2414	unsigned int i;
2415	ebitmap_node_t *rnode;
2416
2417	id = key;
2418	role = (role_datum_t *)datum;
2419	state = (link_state_t *)data;
2420
2421	if (strcmp(id, OBJECT_R) == 0){
2422		/* object_r is never a role attribute by far */
2423		return 0;
2424	}
2425
2426	if (role->flavor != ROLE_ATTRIB)
2427		return 0;
2428
2429	if (state->verbose)
2430		INFO(state->handle, "expanding role attribute %s", id);
2431
2432restart:
2433	ebitmap_for_each_bit(&role->roles, rnode, i) {
2434		if (ebitmap_node_get_bit(rnode, i)) {
2435			sub_attr = state->base->role_val_to_struct[i];
2436			if (sub_attr->flavor != ROLE_ATTRIB)
2437				continue;
2438
2439			/* remove the sub role attribute from the parent
2440			 * role attribute's roles ebitmap */
2441			if (ebitmap_set_bit(&role->roles, i, 0))
2442				return -1;
2443
2444			/* loop dependency of role attributes */
2445			if (sub_attr->s.value == role->s.value)
2446				continue;
2447
2448			/* now go on to expand a sub role attribute
2449			 * by escalating its roles ebitmap */
2450			if (ebitmap_union(&role->roles, &sub_attr->roles)) {
2451				ERR(state->handle, "Out of memory!");
2452				return -1;
2453			}
2454
2455			/* sub_attr->roles may contain other role attributes,
2456			 * re-scan the parent role attribute's roles ebitmap */
2457			goto restart;
2458		}
2459	}
2460
2461	return 0;
2462}
2463
2464/* For any role attribute in a declaration's local symtab[SYM_ROLES] table,
2465 * copy its roles ebitmap into its duplicate's in the base->p_roles.table.
2466 */
2467static int populate_decl_roleattributes(hashtab_key_t key,
2468					hashtab_datum_t datum,
2469					void *data)
2470{
2471	char *id = key;
2472	role_datum_t *decl_role, *base_role;
2473	link_state_t *state = (link_state_t *)data;
2474
2475	decl_role = (role_datum_t *)datum;
2476
2477	if (strcmp(id, OBJECT_R) == 0) {
2478		/* object_r is never a role attribute by far */
2479		return 0;
2480	}
2481
2482	if (decl_role->flavor != ROLE_ATTRIB)
2483		return 0;
2484
2485	base_role = (role_datum_t *)hashtab_search(state->base->p_roles.table,
2486						   id);
2487	assert(base_role != NULL && base_role->flavor == ROLE_ATTRIB);
2488
2489	if (ebitmap_union(&base_role->roles, &decl_role->roles)) {
2490		ERR(state->handle, "Out of memory!");
2491		return -1;
2492	}
2493
2494	return 0;
2495}
2496
2497static int populate_roleattributes(link_state_t *state, policydb_t *pol)
2498{
2499	avrule_block_t *block;
2500	avrule_decl_t *decl;
2501
2502	if (state->verbose)
2503		INFO(state->handle, "Populating role-attribute relationship "
2504			    "from enabled declarations' local symtab.");
2505
2506	/* Iterate through all of the blocks skipping the first(which is the
2507	 * global block, is required to be present and can't have an else).
2508	 * If the block is disabled or not having an enabled decl, skip it.
2509	 */
2510	for (block = pol->global->next; block != NULL; block = block->next)
2511	{
2512		decl = block->enabled;
2513		if (decl == NULL || decl->enabled == 0)
2514			continue;
2515
2516		if (hashtab_map(decl->symtab[SYM_ROLES].table,
2517				populate_decl_roleattributes, state))
2518			return -1;
2519	}
2520
2521	return 0;
2522}
2523
2524/* Link a set of modules into a base module. This process is somewhat
2525 * similar to an actual compiler: it requires a set of order dependent
2526 * steps.  The base and every module must have been indexed prior to
2527 * calling this function.
2528 */
2529int link_modules(sepol_handle_t * handle,
2530		 policydb_t * b, policydb_t ** mods, int len, int verbose)
2531{
2532	int i, ret, retval = -1;
2533	policy_module_t **modules = NULL;
2534	link_state_t state;
2535	uint32_t num_mod_decls = 0;
2536
2537	memset(&state, 0, sizeof(state));
2538	state.base = b;
2539	state.verbose = verbose;
2540	state.handle = handle;
2541
2542	if (b->policy_type != POLICY_BASE) {
2543		ERR(state.handle, "Target of link was not a base policy.");
2544		return -1;
2545	}
2546
2547	/* first allocate some space to hold the maps from module
2548	 * symbol's value to the destination symbol value; then do
2549	 * other preparation work */
2550	if ((modules =
2551	     (policy_module_t **) calloc(len, sizeof(*modules))) == NULL) {
2552		ERR(state.handle, "Out of memory!");
2553		return -1;
2554	}
2555	for (i = 0; i < len; i++) {
2556		if (mods[i]->policy_type != POLICY_MOD) {
2557			ERR(state.handle,
2558			    "Tried to link in a policy that was not a module.");
2559			goto cleanup;
2560		}
2561
2562		if (mods[i]->mls != b->mls) {
2563			if (b->mls)
2564				ERR(state.handle,
2565				    "Tried to link in a non-MLS module with an MLS base.");
2566			else
2567				ERR(state.handle,
2568				    "Tried to link in an MLS module with a non-MLS base.");
2569			goto cleanup;
2570		}
2571
2572		if ((modules[i] =
2573		     (policy_module_t *) calloc(1,
2574						sizeof(policy_module_t))) ==
2575		    NULL) {
2576			ERR(state.handle, "Out of memory!");
2577			goto cleanup;
2578		}
2579		modules[i]->policy = mods[i];
2580		if (prepare_module(&state, modules[i]) == -1) {
2581			goto cleanup;
2582		}
2583		num_mod_decls += modules[i]->num_decls;
2584	}
2585	if (prepare_base(&state, num_mod_decls) == -1) {
2586		goto cleanup;
2587	}
2588
2589	/* copy all types, declared and required */
2590	for (i = 0; i < len; i++) {
2591		state.cur = modules[i];
2592		state.cur_mod_name = modules[i]->policy->name;
2593		ret =
2594		    hashtab_map(modules[i]->policy->p_types.table,
2595				type_copy_callback, &state);
2596		if (ret) {
2597			retval = ret;
2598			goto cleanup;
2599		}
2600	}
2601
2602	/* then copy everything else, including aliases, and fixup attributes */
2603	for (i = 0; i < len; i++) {
2604		state.cur = modules[i];
2605		state.cur_mod_name = modules[i]->policy->name;
2606		ret =
2607		    copy_identifiers(&state, modules[i]->policy->symtab, NULL);
2608		if (ret) {
2609			retval = ret;
2610			goto cleanup;
2611		}
2612	}
2613
2614	if (policydb_index_others(state.handle, state.base, 0)) {
2615		ERR(state.handle, "Error while indexing others");
2616		goto cleanup;
2617	}
2618
2619	/* copy and remap the module's data over to base */
2620	for (i = 0; i < len; i++) {
2621		state.cur = modules[i];
2622		ret = copy_module(&state, modules[i]);
2623		if (ret) {
2624			retval = ret;
2625			goto cleanup;
2626		}
2627	}
2628
2629	/* re-index base, for symbols were added to symbol tables  */
2630	if (policydb_index_classes(state.base)) {
2631		ERR(state.handle, "Error while indexing classes");
2632		goto cleanup;
2633	}
2634	if (policydb_index_others(state.handle, state.base, 0)) {
2635		ERR(state.handle, "Error while indexing others");
2636		goto cleanup;
2637	}
2638
2639	if (enable_avrules(&state, state.base)) {
2640		retval = SEPOL_EREQ;
2641		goto cleanup;
2642	}
2643
2644	/* Now that all role attribute's roles ebitmap have been settled,
2645	 * escalate sub role attribute's roles ebitmap into that of parent.
2646	 *
2647	 * First, since some role-attribute relationships could be recorded
2648	 * in some decl's local symtab(see get_local_role()), we need to
2649	 * populate them up to the base.p_roles table. */
2650	if (populate_roleattributes(&state, state.base)) {
2651		retval = SEPOL_EREQ;
2652		goto cleanup;
2653	}
2654
2655	/* Now do the escalation. */
2656	if (hashtab_map(state.base->p_roles.table, expand_role_attributes,
2657			&state))
2658		goto cleanup;
2659
2660	retval = 0;
2661      cleanup:
2662	for (i = 0; modules != NULL && i < len; i++) {
2663		policy_module_destroy(modules[i]);
2664	}
2665	free(modules);
2666	free(state.decl_to_mod);
2667	return retval;
2668}
2669