1/* Authors: Karl MacMillan <kmacmillan@mentalrootkit.com>
2 *
3 * Copyright (C) 2006 Tresys Technology, LLC
4 * Copyright (C) 2006-2007 Red Hat, Inc.
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, version 2.
9 *
10 */
11
12/* Because we _must_ muck around in the internal representation of
13 * the policydb (and include the internal header below) this program
14 * must be statically linked to libsepol like checkpolicy. It is
15 * not clear if it is worthwhile to fix this, as exposing the details
16 * of avrule_blocks - even in an ABI safe way - seems undesirable.
17 */
18#include <sepol/module.h>
19#include <sepol/errcodes.h>
20#include <sepol/policydb/policydb.h>
21
22#include <getopt.h>
23#include <fcntl.h>
24#include <stdio.h>
25#include <errno.h>
26#include <sys/mman.h>
27#include <sys/types.h>
28#include <sys/stat.h>
29#include <stdlib.h>
30#include <unistd.h>
31#include <string.h>
32#include <assert.h>
33
34/* for getopt */
35extern char *optarg;
36extern int optind;
37
38/* This is really a horrible hack, but the base module
39 * is referred to with the following name. The same
40 * thing is done in the linker for displaying error
41 * messages.
42 */
43#define BASE_NAME "BASE"
44
45static void usage(char *program_name)
46{
47	printf("usage: %s [-v -g -b] basemodpkg modpkg1 [modpkg2 ... ]\n",
48	       program_name);
49	exit(1);
50}
51
52/* Basic string hash and compare for the hashtables used in
53 * generate_requires. Copied from symtab.c.
54 */
55static unsigned int reqsymhash(hashtab_t h, hashtab_key_t key)
56{
57	char *p, *keyp;
58	size_t size;
59	unsigned int val;
60
61	val = 0;
62	keyp = (char *)key;
63	size = strlen(keyp);
64	for (p = keyp; ((size_t) (p - keyp)) < size; p++)
65		val =
66		    (val << 4 | (val >> (8 * sizeof(unsigned int) - 4))) ^ (*p);
67	return val & (h->size - 1);
68}
69
70static int reqsymcmp(hashtab_t h
71		     __attribute__ ((unused)), hashtab_key_t key1,
72		     hashtab_key_t key2)
73{
74	char *keyp1, *keyp2;
75
76	keyp1 = (char *)key1;
77	keyp2 = (char *)key2;
78	return strcmp(keyp1, keyp2);
79}
80
81/* Load a policy package from the given filename. Progname is used for
82 * error reporting.
83 */
84static sepol_module_package_t *load_module(char *filename, char *progname)
85{
86	int ret;
87	FILE *fp = NULL;
88	struct sepol_policy_file *pf = NULL;
89	sepol_module_package_t *p = NULL;
90
91	if (sepol_module_package_create(&p)) {
92		fprintf(stderr, "%s:  Out of memory\n", progname);
93		goto bad;
94	}
95	if (sepol_policy_file_create(&pf)) {
96		fprintf(stderr, "%s:  Out of memory\n", progname);
97		goto bad;
98	}
99	fp = fopen(filename, "r");
100	if (!fp) {
101		fprintf(stderr, "%s:  Could not open package %s:  %s", progname,
102			filename, strerror(errno));
103		goto bad;
104	}
105	sepol_policy_file_set_fp(pf, fp);
106
107	ret = sepol_module_package_read(p, pf, 0);
108	if (ret) {
109		fprintf(stderr, "%s:  Error while reading package from %s\n",
110			progname, filename);
111		goto bad;
112	}
113	fclose(fp);
114	sepol_policy_file_free(pf);
115	return p;
116      bad:
117	sepol_module_package_free(p);
118	sepol_policy_file_free(pf);
119	if (fp)
120		fclose(fp);
121	return NULL;
122}
123
124/* This function generates the requirements graph and stores it in
125 * a set of nested hashtables. The top level hash table stores modules
126 * keyed by name. The value of that module is a hashtable storing all
127 * of the requirements keyed by name. There is no value for the requirements
128 * hashtable.
129 *
130 * This only tracks symbols that are _required_ - optional symbols
131 * are completely ignored. A future version might look at this.
132 *
133 * This requirement generation only looks at booleans and types because:
134 *  - object classes: (for now) only present in bases
135 *  - roles: since they are multiply declared it is not clear how
136 *           to present these requirements as they will be satisfied
137 *           by multiple modules.
138 *  - users: same problem as roles plus they are usually defined outside
139 *           of the policy.
140 *  - levels / cats: can't be required or used in modules.
141 */
142static hashtab_t generate_requires(policydb_t * p)
143{
144	avrule_block_t *block;
145	avrule_decl_t *decl;
146	char *mod_name, *req_name, *id;
147	ebitmap_t *b;
148	ebitmap_node_t *node;
149	uint32_t i, j;
150	int ret;
151	scope_datum_t *scope;
152	hashtab_t mods;
153	hashtab_t reqs;
154
155	mods = hashtab_create(reqsymhash, reqsymcmp, 64);
156	if (mods == NULL)
157		return NULL;
158
159	for (block = p->global; block != NULL; block = block->next) {
160		if (block->flags & AVRULE_OPTIONAL)
161			continue;
162		for (decl = block->branch_list; decl != NULL; decl = decl->next) {
163			mod_name =
164			    decl->module_name ? decl->module_name : BASE_NAME;
165			for (i = 0; i < SYM_NUM; i++) {
166				if (!(i == SYM_TYPES || i == SYM_BOOLS))
167					continue;
168				b = &decl->required.scope[i];
169				ebitmap_for_each_bit(b, node, j) {
170					if (!ebitmap_node_get_bit(node, j))
171						continue;
172					id = p->sym_val_to_name[i][j];
173					scope =
174					    (scope_datum_t *) hashtab_search(p->
175									     scope
176									     [i].
177									     table,
178									     id);
179					/* since this is only called after a successful link,
180					 * this should never happen */
181					assert(scope->scope == SCOPE_DECL);
182					req_name =
183					    p->decl_val_to_struct[scope->
184								  decl_ids[0]]->
185					    module_name ? p->
186					    decl_val_to_struct[scope->
187							       decl_ids[0]]->
188					    module_name : BASE_NAME;
189
190					reqs =
191					    (hashtab_t) hashtab_search(mods,
192								       mod_name);
193					if (!reqs) {
194						reqs =
195						    hashtab_create(reqsymhash,
196								   reqsymcmp,
197								   64);
198						if (reqs == NULL) {
199							return NULL;
200						}
201						ret =
202						    hashtab_insert(mods,
203								   mod_name,
204								   reqs);
205						if (ret != SEPOL_OK)
206							return NULL;
207					}
208					ret =
209					    hashtab_insert(reqs, req_name,
210							   NULL);
211					if (!
212					    (ret == SEPOL_EEXIST
213					     || ret == SEPOL_OK))
214						return NULL;
215				}
216			}
217
218		}
219	}
220
221	return mods;
222}
223
224static void free_requires(hashtab_t req)
225{
226	unsigned int i;
227	hashtab_ptr_t cur;
228
229	/* We steal memory for everything stored in the hash tables
230	 * from the policydb, so this only looks like it leaks.
231	 */
232	for (i = 0; i < req->size; i++) {
233		cur = req->htable[i];
234		while (cur != NULL) {
235			hashtab_destroy((hashtab_t) cur->datum);
236			cur = cur->next;
237		}
238	}
239	hashtab_destroy(req);
240}
241
242static void output_graphviz(hashtab_t mods, int exclude_base, FILE * f)
243{
244	unsigned int i, j;
245	hashtab_ptr_t cur, cur2;
246	hashtab_t reqs;
247
248	fprintf(f, "digraph mod_deps {\n");
249	fprintf(f, "\toverlap=false\n");
250
251	for (i = 0; i < mods->size; i++) {
252		cur = mods->htable[i];
253		while (cur != NULL) {
254			reqs = (hashtab_t) cur->datum;
255			assert(reqs);
256			for (j = 0; j < reqs->size; j++) {
257				cur2 = reqs->htable[j];
258				while (cur2 != NULL) {
259					if (exclude_base
260					    && strcmp(cur2->key,
261						      BASE_NAME) == 0) {
262						cur2 = cur2->next;
263						continue;
264					}
265					fprintf(f, "\t%s -> %s\n", cur->key,
266						cur2->key);
267					cur2 = cur2->next;
268				}
269			}
270			cur = cur->next;
271		}
272	}
273	fprintf(f, "}\n");
274}
275
276static void output_requirements(hashtab_t mods, int exclude_base, FILE * f)
277{
278	unsigned int i, j;
279	hashtab_ptr_t cur, cur2;
280	hashtab_t reqs;
281	int found_req;
282
283	for (i = 0; i < mods->size; i++) {
284		cur = mods->htable[i];
285		while (cur != NULL) {
286			reqs = (hashtab_t) cur->datum;
287			assert(reqs);
288			fprintf(f, "module: %s\n", cur->key);
289			found_req = 0;
290			for (j = 0; j < reqs->size; j++) {
291				cur2 = reqs->htable[j];
292				while (cur2 != NULL) {
293					if (exclude_base
294					    && strcmp(cur2->key,
295						      BASE_NAME) == 0) {
296						cur2 = cur2->next;
297						continue;
298					}
299					found_req = 1;
300					fprintf(f, "\t%s\n", cur2->key);
301					cur2 = cur2->next;
302				}
303			}
304			if (!found_req)
305				fprintf(f, "\t[no dependencies]\n");
306			cur = cur->next;
307		}
308	}
309	fprintf(f, "}\n");
310}
311
312/* Possible commands - see the command variable in
313 * main below and the man page for more info.
314 */
315#define SHOW_DEPS    1
316#define GEN_GRAPHVIZ 2
317
318int main(int argc, char **argv)
319{
320	int ch, i, num_mods;
321	int verbose = 0, exclude_base = 1, command = SHOW_DEPS;
322	char *basename;
323	sepol_module_package_t *base, **mods;
324	policydb_t *p;
325	hashtab_t req;
326
327	while ((ch = getopt(argc, argv, "vgb")) != EOF) {
328		switch (ch) {
329		case 'v':
330			verbose = 1;
331			break;
332		case 'g':
333			command = GEN_GRAPHVIZ;
334			break;
335		case 'b':
336			exclude_base = 0;
337			break;
338		default:
339			usage(argv[0]);
340		}
341	}
342
343	/* check args */
344	if (argc < 3 || !(optind != (argc - 1))) {
345		fprintf(stderr,
346			"%s:  You must provide the base module package and at least one other module package\n",
347			argv[0]);
348		usage(argv[0]);
349	}
350
351	basename = argv[optind++];
352	base = load_module(basename, argv[0]);
353	if (!base) {
354		fprintf(stderr,
355			"%s:  Could not load base module from file %s\n",
356			argv[0], basename);
357		exit(1);
358	}
359
360	num_mods = argc - optind;
361	mods =
362	    (sepol_module_package_t **) malloc(sizeof(sepol_module_package_t *)
363					       * num_mods);
364	if (!mods) {
365		fprintf(stderr, "%s:  Out of memory\n", argv[0]);
366		exit(1);
367	}
368	memset(mods, 0, sizeof(sepol_module_package_t *) * num_mods);
369
370	for (i = 0; optind < argc; optind++, i++) {
371		mods[i] = load_module(argv[optind], argv[0]);
372		if (!mods[i]) {
373			fprintf(stderr,
374				"%s:  Could not load module from file %s\n",
375				argv[0], argv[optind]);
376			exit(1);
377		}
378	}
379
380	if (sepol_link_packages(NULL, base, mods, num_mods, verbose)) {
381		fprintf(stderr, "%s:  Error while linking packages\n", argv[0]);
382		exit(1);
383	}
384
385	p = (policydb_t *) sepol_module_package_get_policy(base);
386	if (p == NULL)
387		exit(1);
388
389	req = generate_requires(p);
390	if (req == NULL)
391		exit(1);
392
393	if (command == SHOW_DEPS)
394		output_requirements(req, exclude_base, stdout);
395	else
396		output_graphviz(req, exclude_base, stdout);
397
398	sepol_module_package_free(base);
399	for (i = 0; i < num_mods; i++)
400		sepol_module_package_free(mods[i]);
401
402	free_requires(req);
403
404	exit(0);
405}
406