1 /* Copyright 2005,2013 Tresys Technology
2 *
3 * Some parts of this came from matchpathcon.c in libselinux
4 */
5
6 /* PURPOSE OF THIS PROGRAM
7 * The original setfiles sorting algorithm did not take into
8 * account regular expression specificity. With the current
9 * strict and targeted policies this is not an issue because
10 * the file contexts are partially hand sorted and concatenated
11 * in the right order so that the matches are generally correct.
12 * The way reference policy and loadable policy modules handle
13 * file contexts makes them come out in an unpredictable order
14 * and therefore setfiles (or this standalone tool) need to sort
15 * the regular expressions in a deterministic and stable way.
16 */
17
18 #define BUF_SIZE 4096;
19 #define _GNU_SOURCE
20
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <string.h>
24 #include <ctype.h>
25
26 typedef unsigned char bool_t;
27
28 /* file_context_node
29 * A node used in a linked list of file contexts.c
30 * Each node contains the regular expression, the type and
31 * the context, as well as information about the regular
32 * expression. The regular expression data (meta, stem_len
33 * and str_len) can be filled in by using the fc_fill_data
34 * function after the regular expression has been loaded.
35 * next points to the next node in the linked list.
36 */
37 typedef struct file_context_node {
38 char *path;
39 char *file_type;
40 char *context;
41 bool_t meta;
42 int stem_len;
43 int str_len;
44 struct file_context_node *next;
45 } file_context_node_t;
46
file_context_node_destroy(file_context_node_t * x)47 void file_context_node_destroy(file_context_node_t *x)
48 {
49 free(x->path);
50 free(x->file_type);
51 free(x->context);
52 }
53
54
55
56 /* file_context_bucket
57 * A node used in a linked list of buckets that contain
58 * file_context_node's.
59 * Each node contains a pointer to a file_context_node which
60 * is the header of its linked list. This linked list is the
61 * content of this bucket.
62 * next points to the next bucket in the linked list.
63 */
64 typedef struct file_context_bucket {
65 file_context_node_t *data;
66 struct file_context_bucket *next;
67 } file_context_bucket_t;
68
69
70
71 /* fc_compare
72 * Compares two file contexts' regular expressions and returns:
73 * -1 if a is less specific than b
74 * 0 if a and be are equally specific
75 * 1 if a is more specific than b
76 * The comparison is based on the following statements,
77 * in order from most important to least important, given a and b:
78 * If a is a regular expression and b is not,
79 * -> a is less specific than b.
80 * If a's stem length is shorter than b's stem length,
81 * -> a is less specific than b.
82 * If a's string length is shorter than b's string length,
83 * -> a is less specific than b.
84 * If a does not have a specified type and b does,
85 * -> a is less specific than b.
86 */
fc_compare(file_context_node_t * a,file_context_node_t * b)87 int fc_compare(file_context_node_t *a, file_context_node_t *b)
88 {
89 /* Check to see if either a or b have meta characters
90 * and the other doesn't. */
91 if (a->meta && !b->meta)
92 return -1;
93 if (b->meta && !a->meta)
94 return 1;
95
96 /* Check to see if either a or b have a shorter stem
97 * length than the other. */
98 if (a->stem_len < b->stem_len)
99 return -1;
100 if (b->stem_len < a->stem_len)
101 return 1;
102
103 /* Check to see if either a or b have a shorter string
104 * length than the other. */
105 if (a->str_len < b->str_len)
106 return -1;
107 if (b->str_len < a->str_len)
108 return 1;
109
110 /* Check to see if either a or b has a specified type
111 * and the other doesn't. */
112 if (!a->file_type && b->file_type)
113 return -1;
114 if (!b->file_type && a->file_type)
115 return 1;
116
117 /* If none of the above conditions were satisfied,
118 * then a and b are equally specific. */
119 return 0;
120 }
121
122
123
124 /* fc_merge
125 * Merges two sorted file context linked lists into one
126 * sorted one.
127 * Pass two lists a and b, and after the completion of fc_merge,
128 * the final list is contained in a, and b is empty.
129 */
fc_merge(file_context_node_t * a,file_context_node_t * b)130 file_context_node_t *fc_merge(file_context_node_t *a,
131 file_context_node_t *b)
132 {
133 file_context_node_t *a_current;
134 file_context_node_t *b_current;
135 file_context_node_t *temp;
136 file_context_node_t *jumpto;
137
138
139
140 /* If a is a empty list, and b is not,
141 * set a as b and proceed to the end. */
142 if (!a && b)
143 a = b;
144 /* If b is an empty list, leave a as it is. */
145 else if (!b) {
146 } else {
147 /* Make it so the list a has the lesser
148 * first element always. */
149 if (fc_compare(a, b) == 1) {
150 temp = a;
151 a = b;
152 b = temp;
153 }
154 a_current = a;
155 b_current = b;
156
157 /* Merge by inserting b's nodes in between a's nodes. */
158 while (a_current->next && b_current) {
159 jumpto = a_current->next;
160
161 /* Insert b's nodes in between the current a node
162 * and the next a node.*/
163 while (b_current && a_current->next &&
164 fc_compare(a_current->next,
165 b_current) != -1) {
166
167
168 temp = a_current->next;
169 a_current->next = b_current;
170 b_current = b_current->next;
171 a_current->next->next = temp;
172 a_current = a_current->next;
173 }
174
175 /* Skip all the inserted node from b to the
176 * next node in the original a. */
177 a_current = jumpto;
178 }
179
180
181 /* if there is anything left in b to be inserted,
182 put it on the end */
183 if (b_current) {
184 a_current->next = b_current;
185 }
186 }
187
188 return a;
189 }
190
191
192
193 /* fc_merge_sort
194 * Sorts file contexts from least specific to more specific.
195 * The bucket linked list is passed and after the completion
196 * of the fc_merge_sort function, there is only one bucket
197 * (pointed to by master) that contains a linked list
198 * of all the file contexts, in sorted order.
199 * Explanation of the algorithm:
200 * The algorithm implemented in fc_merge_sort is an iterative
201 * implementation of merge sort.
202 * At first, each bucket has a linked list of file contexts
203 * that are 1 element each.
204 * Each pass, each odd numbered bucket is merged into the bucket
205 * before it. This halves the number of buckets each pass.
206 * It will continue passing over the buckets (as described above)
207 * until there is only one bucket left, containing the list of
208 * file contexts, sorted.
209 */
fc_merge_sort(file_context_bucket_t * master)210 void fc_merge_sort(file_context_bucket_t *master)
211 {
212
213
214 file_context_bucket_t *current;
215 file_context_bucket_t *temp;
216
217 /* Loop until master is the only bucket left
218 * so that this will stop when master contains
219 * the sorted list. */
220 while (master->next) {
221 current = master;
222
223 /* This loop merges buckets two-by-two. */
224 while (current) {
225
226 if (current->next) {
227
228 current->data =
229 fc_merge(current->data,
230 current->next->data);
231
232
233
234 temp = current->next;
235 current->next = current->next->next;
236
237 free(temp);
238
239 }
240
241
242 current = current->next;
243 }
244 }
245
246
247 }
248
249
250
251 /* fc_fill_data
252 * This processes a regular expression in a file context
253 * and sets the data held in file_context_node, namely
254 * meta, str_len and stem_len.
255 * The following changes are made to fc_node after the
256 * the completion of the function:
257 * fc_node->meta = 1 if path has a meta character, 0 if not.
258 * fc_node->str_len = The string length of the entire path
259 * fc_node->stem_len = The number of characters up until
260 * the first meta character.
261 */
fc_fill_data(file_context_node_t * fc_node)262 void fc_fill_data(file_context_node_t *fc_node)
263 {
264 int c = 0;
265
266 fc_node->meta = 0;
267 fc_node->stem_len = 0;
268 fc_node->str_len = 0;
269
270 /* Process until the string termination character
271 * has been reached.
272 * Note: this while loop has been adapted from
273 * spec_hasMetaChars in matchpathcon.c from
274 * libselinux-1.22. */
275 while (fc_node->path[c] != '\0') {
276 switch (fc_node->path[c]) {
277 case '.':
278 case '^':
279 case '$':
280 case '?':
281 case '*':
282 case '+':
283 case '|':
284 case '[':
285 case '(':
286 case '{':
287 /* If a meta character is found,
288 * set meta to one */
289 fc_node->meta = 1;
290 break;
291 case '\\':
292 /* If a escape character is found,
293 * skip the next character. */
294 c++;
295 default:
296 /* If no meta character has been found yet,
297 * add one to the stem length. */
298 if (!fc_node->meta)
299 fc_node->stem_len++;
300 break;
301 }
302
303 fc_node->str_len++;
304 c++;
305 }
306 }
307
308 /* main
309 * This program takes in two arguments, the input filename and the
310 * output filename. The input file should be syntactically correct.
311 * Overall what is done in the main is read in the file and store each
312 * line of code, sort it, then output it to the output file.
313 */
main(int argc,char * argv[])314 int main(int argc, char *argv[])
315 {
316 int lines;
317 size_t start, finish, regex_len, context_len;
318 size_t line_len, buf_len, i, j;
319 char *input_name, *output_name, *line_buf;
320
321 file_context_node_t *temp;
322 file_context_node_t *head;
323 file_context_node_t *current;
324 file_context_bucket_t *master;
325 file_context_bucket_t *bcurrent;
326
327 FILE *in_file, *out_file;
328
329
330 /* Check for the correct number of command line arguments. */
331 if (argc < 2 || argc > 3) {
332 fprintf(stderr, "Usage: %s <infile> [<outfile>]\n",argv[0]);
333 return 1;
334 }
335
336 input_name = argv[1];
337 output_name = (argc >= 3) ? argv[2] : NULL;
338
339 i = j = lines = 0;
340
341 /* Open the input file. */
342 if (!(in_file = fopen(input_name, "r"))) {
343 fprintf(stderr, "Error: failure opening input file for read.\n");
344 return 1;
345 }
346
347 /* Initialize the head of the linked list. */
348 head = current = (file_context_node_t*)malloc(sizeof(file_context_node_t));
349 head->next = NULL;
350
351 /* Parse the file into a file_context linked list. */
352 line_buf = NULL;
353
354 while ( getline(&line_buf, &buf_len, in_file) != -1 ){
355 line_len = strlen(line_buf);
356 if( line_len == 0 || line_len == 1)
357 continue;
358 /* Get rid of whitespace from the front of the line. */
359 for (i = 0; i < line_len; i++) {
360 if (!isspace(line_buf[i]))
361 break;
362 }
363
364
365 if (i >= line_len)
366 continue;
367 /* Check if the line isn't empty and isn't a comment */
368 if (line_buf[i] == '#')
369 continue;
370
371 /* We have a valid line - allocate a new node. */
372 temp = (file_context_node_t *)malloc(sizeof(file_context_node_t));
373 if (!temp) {
374 fprintf(stderr, "Error: failure allocating memory.\n");
375 return 1;
376 }
377 temp->next = NULL;
378 memset(temp, 0, sizeof(file_context_node_t));
379
380 /* Parse out the regular expression from the line. */
381 start = i;
382
383
384 while (i < line_len && (!isspace(line_buf[i])))
385 i++;
386 finish = i;
387
388
389 regex_len = finish - start;
390
391 if (regex_len == 0) {
392 file_context_node_destroy(temp);
393 free(temp);
394
395
396 continue;
397 }
398
399 temp->path = (char*)strndup(&line_buf[start], regex_len);
400 if (!temp->path) {
401 file_context_node_destroy(temp);
402 free(temp);
403 fprintf(stderr, "Error: failure allocating memory.\n");
404 return 1;
405 }
406
407 /* Get rid of whitespace after the regular expression. */
408 for (; i < line_len; i++) {
409
410 if (!isspace(line_buf[i]))
411 break;
412 }
413
414 if (i == line_len) {
415 file_context_node_destroy(temp);
416 free(temp);
417 continue;
418 }
419
420 /* Parse out the type from the line (if it
421 * is there). */
422 if (line_buf[i] == '-') {
423 temp->file_type = (char *)malloc(sizeof(char) * 3);
424 if (!(temp->file_type)) {
425 fprintf(stderr, "Error: failure allocating memory.\n");
426 return 1;
427 }
428
429 if( i + 2 >= line_len ) {
430 file_context_node_destroy(temp);
431 free(temp);
432
433 continue;
434 }
435
436 /* Fill the type into the array. */
437 temp->file_type[0] = line_buf[i];
438 temp->file_type[1] = line_buf[i + 1];
439 i += 2;
440 temp->file_type[2] = 0;
441
442 /* Get rid of whitespace after the type. */
443 for (; i < line_len; i++) {
444 if (!isspace(line_buf[i]))
445 break;
446 }
447
448 if (i == line_len) {
449
450 file_context_node_destroy(temp);
451 free(temp);
452 continue;
453 }
454 }
455
456 /* Parse out the context from the line. */
457 start = i;
458 while (i < line_len && (!isspace(line_buf[i])))
459 i++;
460 finish = i;
461
462 context_len = finish - start;
463
464 temp->context = (char*)strndup(&line_buf[start], context_len);
465 if (!temp->context) {
466 file_context_node_destroy(temp);
467 free(temp);
468 fprintf(stderr, "Error: failure allocating memory.\n");
469 return 1;
470 }
471
472 /* Set all the data about the regular
473 * expression. */
474 fc_fill_data(temp);
475
476 /* Link this line of code at the end of
477 * the linked list. */
478 current->next = temp;
479 current = current->next;
480 lines++;
481
482
483 free(line_buf);
484 line_buf = NULL;
485 }
486 fclose(in_file);
487
488 /* Create the bucket linked list from the earlier linked list. */
489 current = head->next;
490 bcurrent = master =
491 (file_context_bucket_t *)
492 malloc(sizeof(file_context_bucket_t));
493 bcurrent->next = NULL;
494 bcurrent->data = NULL;
495
496 /* Go until all the nodes have been put in individual buckets. */
497 while (current) {
498 /* Copy over the file context line into the bucket. */
499 bcurrent->data = current;
500 current = current->next;
501
502 /* Detach the node in the bucket from the old list. */
503 bcurrent->data->next = NULL;
504
505 /* If there should be another bucket, put one at the end. */
506 if (current) {
507 bcurrent->next =
508 (file_context_bucket_t *)
509 malloc(sizeof(file_context_bucket_t));
510 if (!(bcurrent->next)) {
511 printf
512 ("Error: failure allocating memory.\n");
513 return -1;
514 }
515
516 /* Make sure the new bucket thinks it's the end of the
517 * list. */
518 bcurrent->next->next = NULL;
519
520 bcurrent = bcurrent->next;
521 }
522
523 }
524
525 /* Sort the bucket list. */
526 fc_merge_sort(master);
527
528 /* Open the output file. */
529 if (output_name) {
530 if (!(out_file = fopen(output_name, "w"))) {
531 printf("Error: failure opening output file for write.\n");
532 return -1;
533 }
534 } else {
535 out_file = stdout;
536 }
537
538 /* Output the sorted file_context linked list to the output file. */
539 current = master->data;
540 while (current) {
541 /* Output the path. */
542 fprintf(out_file, "%s\t\t", current->path);
543
544 /* Output the type, if there is one. */
545 if (current->file_type) {
546 fprintf(out_file, "%s\t", current->file_type);
547 }
548
549 /* Output the context. */
550 fprintf(out_file, "%s\n", current->context);
551
552 /* Remove the node. */
553 temp = current;
554 current = current->next;
555
556 file_context_node_destroy(temp);
557 free(temp);
558
559 }
560 free(master);
561
562 if (output_name) {
563 fclose(out_file);
564 }
565
566 return 0;
567 }
568