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 char *extra; 42 bool_t meta; 43 int stem_len; 44 int str_len; 45 struct file_context_node *next; 46 } file_context_node_t; 47 48 void file_context_node_destroy(file_context_node_t *x) 49 { 50 if (!x) 51 return; 52 53 free(x->path); 54 free(x->file_type); 55 free(x->context); 56 } 57 58 59 60 /* file_context_bucket 61 * A node used in a linked list of buckets that contain 62 * file_context_node's. 63 * Each node contains a pointer to a file_context_node which 64 * is the header of its linked list. This linked list is the 65 * content of this bucket. 66 * next points to the next bucket in the linked list. 67 */ 68 typedef struct file_context_bucket { 69 file_context_node_t *data; 70 struct file_context_bucket *next; 71 } file_context_bucket_t; 72 73 74 75 /* fc_compare 76 * Compares two file contexts' regular expressions and returns: 77 * -1 if a is less specific than b 78 * 0 if a and be are equally specific 79 * 1 if a is more specific than b 80 * The comparison is based on the following statements, 81 * in order from most important to least important, given a and b: 82 * If a is a regular expression and b is not, 83 * -> a is less specific than b. 84 * If a's stem length is shorter than b's stem length, 85 * -> a is less specific than b. 86 * If a's string length is shorter than b's string length, 87 * -> a is less specific than b. 88 * If a does not have a specified type and b does, 89 * -> a is less specific than b. 90 */ 91 int fc_compare(file_context_node_t *a, file_context_node_t *b) 92 { 93 /* Check to see if either a or b have meta characters 94 * and the other doesn't. */ 95 if (a->meta && !b->meta) 96 return -1; 97 if (b->meta && !a->meta) 98 return 1; 99 100 /* Check to see if either a or b have a shorter stem 101 * length than the other. */ 102 if (a->stem_len < b->stem_len) 103 return -1; 104 if (b->stem_len < a->stem_len) 105 return 1; 106 107 /* Check to see if either a or b have a shorter string 108 * length than the other. */ 109 if (a->str_len < b->str_len) 110 return -1; 111 if (b->str_len < a->str_len) 112 return 1; 113 114 /* Check to see if either a or b has a specified type 115 * and the other doesn't. */ 116 if (!a->file_type && b->file_type) 117 return -1; 118 if (!b->file_type && a->file_type) 119 return 1; 120 121 /* If none of the above conditions were satisfied, 122 * then a and b are equally specific. */ 123 return 0; 124 } 125 126 127 128 /* fc_merge 129 * Merges two sorted file context linked lists into one 130 * sorted one. 131 * Pass two lists a and b, and after the completion of fc_merge, 132 * the final list is contained in a, and b is empty. 133 */ 134 file_context_node_t *fc_merge(file_context_node_t *a, 135 file_context_node_t *b) 136 { 137 file_context_node_t *a_current; 138 file_context_node_t *b_current; 139 file_context_node_t *temp; 140 file_context_node_t *jumpto; 141 142 /* If a is a empty list, and b is not, 143 * set a as b and proceed to the end. */ 144 if (!a && b) 145 a = b; 146 /* If b is an empty list, leave a as it is. */ 147 else if (!b) { 148 } else { 149 /* Make it so the list a has the lesser 150 * first element always. */ 151 if (fc_compare(a, b) == 1) { 152 temp = a; 153 a = b; 154 b = temp; 155 } 156 a_current = a; 157 b_current = b; 158 159 /* Merge by inserting b's nodes in between a's nodes. */ 160 while (a_current->next && b_current) { 161 jumpto = a_current->next; 162 163 /* Insert b's nodes in between the current a node 164 * and the next a node.*/ 165 while (b_current && a_current->next && 166 fc_compare(a_current->next, 167 b_current) != -1) { 168 169 temp = a_current->next; 170 a_current->next = b_current; 171 b_current = b_current->next; 172 a_current->next->next = temp; 173 a_current = a_current->next; 174 } 175 176 /* Skip all the inserted node from b to the 177 * next node in the original a. */ 178 a_current = jumpto; 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 */ 210 void fc_merge_sort(file_context_bucket_t *master) 211 { 212 file_context_bucket_t *current; 213 file_context_bucket_t *temp; 214 215 if (!master) 216 return; 217 218 /* Loop until master is the only bucket left 219 * so that this will stop when master contains 220 * the sorted list. */ 221 while (master->next) { 222 current = master; 223 224 /* This loop merges buckets two-by-two. */ 225 while (current) { 226 if (current->next) { 227 current->data = 228 fc_merge(current->data, 229 current->next->data); 230 231 temp = current->next; 232 current->next = current->next->next; 233 234 free(temp); 235 } 236 237 current = current->next; 238 } 239 } 240 } 241 242 243 244 /* fc_fill_data 245 * This processes a regular expression in a file context 246 * and sets the data held in file_context_node, namely 247 * meta, str_len and stem_len. 248 * The following changes are made to fc_node after the 249 * the completion of the function: 250 * fc_node->meta = 1 if path has a meta character, 0 if not. 251 * fc_node->str_len = The string length of the entire path 252 * fc_node->stem_len = The number of characters up until 253 * the first meta character. 254 */ 255 void fc_fill_data(file_context_node_t *fc_node) 256 { 257 int c = 0; 258 259 fc_node->meta = 0; 260 fc_node->stem_len = 0; 261 fc_node->str_len = 0; 262 263 /* Process until the string termination character 264 * has been reached. 265 * Note: this while loop has been adapted from 266 * spec_hasMetaChars in matchpathcon.c from 267 * libselinux-1.22. */ 268 while (fc_node->path[c] != '\0') { 269 switch (fc_node->path[c]) { 270 case '.': 271 case '^': 272 case '$': 273 case '?': 274 case '*': 275 case '+': 276 case '|': 277 case '[': 278 case '(': 279 case '{': 280 /* If a meta character is found, 281 * set meta to one */ 282 fc_node->meta = 1; 283 break; 284 case '\\': 285 /* If a escape character is found, 286 * skip the next character. */ 287 c++; 288 break; 289 default: 290 break; 291 } 292 293 /* If no meta character has been found yet, 294 * add one to the stem length. */ 295 if (!fc_node->meta) 296 fc_node->stem_len++; 297 298 fc_node->str_len++; 299 c++; 300 } 301 } 302 303 304 305 /* fc_free_file_context_node_list 306 * Free the memory allocated to the linked list and its elements. 307 */ 308 void fc_free_file_context_node_list(struct file_context_node *node) 309 { 310 struct file_context_node *next; 311 312 while (node) { 313 next = node->next; 314 file_context_node_destroy(node); 315 free(node); 316 node = next; 317 } 318 } 319 320 321 322 /* main 323 * This program takes in two arguments, the input filename and the 324 * output filename. The input file should be syntactically correct. 325 * Overall what is done in the main is read in the file and store each 326 * line of code, sort it, then output it to the output file. 327 */ 328 int main(int argc, char *argv[]) 329 { 330 int lines; 331 size_t start, finish, regex_len, context_len; 332 size_t line_len, buf_len, i; 333 char *input_name, *output_name, *line_buf; 334 335 file_context_node_t *temp; 336 file_context_node_t *head; 337 file_context_node_t *current; 338 file_context_bucket_t *master; 339 file_context_bucket_t *bcurrent; 340 341 FILE *in_file, *out_file; 342 343 /* Check for the correct number of command line arguments. */ 344 if (argc < 2 || argc > 3) { 345 fprintf(stderr, "Usage: %s <infile> [<outfile>]\n",argv[0]); 346 return 1; 347 } 348 349 input_name = argv[1]; 350 output_name = (argc >= 3) ? argv[2] : NULL; 351 352 lines = 0; 353 354 /* Open the input file. */ 355 if (!(in_file = fopen(input_name, "r"))) { 356 fprintf(stderr, "Error: failure opening input file for read.\n"); 357 return 1; 358 } 359 360 /* Initialize the head of the linked list. */ 361 head = current = (file_context_node_t*)calloc(1, sizeof(file_context_node_t)); 362 if (!head) { 363 fprintf(stderr, "Error: failure allocating memory.\n"); 364 return 1; 365 } 366 367 /* Parse the file into a file_context linked list. */ 368 line_buf = NULL; 369 370 while ( getline(&line_buf, &buf_len, in_file) != -1 ){ 371 line_len = strlen(line_buf); 372 373 if( line_len == 0 || line_len == 1) 374 continue; 375 376 /* Get rid of whitespace from the front of the line. */ 377 for (i = 0; i < line_len; i++) { 378 if (!isspace(line_buf[i])) 379 break; 380 } 381 382 if (i >= line_len) 383 continue; 384 385 /* Check if the line isn't empty and isn't a comment */ 386 if (line_buf[i] == '#') 387 continue; 388 389 /* We have a valid line - allocate a new node. */ 390 temp = (file_context_node_t *)calloc(1, sizeof(file_context_node_t)); 391 if (!temp) { 392 free(line_buf); 393 fprintf(stderr, "Error: failure allocating memory.\n"); 394 fc_free_file_context_node_list(head); 395 return 1; 396 } 397 398 /* Parse out the regular expression from the line. */ 399 start = i; 400 401 while (i < line_len && (!isspace(line_buf[i]))) 402 i++; 403 finish = i; 404 405 regex_len = finish - start; 406 407 if (regex_len == 0) { 408 file_context_node_destroy(temp); 409 free(temp); 410 continue; 411 } 412 413 temp->path = (char*)strndup(&line_buf[start], regex_len); 414 if (!temp->path) { 415 file_context_node_destroy(temp); 416 free(temp); 417 free(line_buf); 418 fprintf(stderr, "Error: failure allocating memory.\n"); 419 fc_free_file_context_node_list(head); 420 return 1; 421 } 422 423 /* Get rid of whitespace after the regular expression. */ 424 for (; i < line_len; i++) { 425 if (!isspace(line_buf[i])) 426 break; 427 } 428 429 if (i == line_len) { 430 file_context_node_destroy(temp); 431 free(temp); 432 continue; 433 } 434 435 /* Parse out the type from the line (if it 436 * is there). */ 437 if (line_buf[i] == '-') { 438 temp->file_type = (char *)malloc(sizeof(char) * 3); 439 if (!(temp->file_type)) { 440 file_context_node_destroy(temp); 441 free(temp); 442 free(line_buf); 443 fprintf(stderr, "Error: failure allocating memory.\n"); 444 fc_free_file_context_node_list(head); 445 return 1; 446 } 447 448 if( i + 2 >= line_len ) { 449 file_context_node_destroy(temp); 450 free(temp); 451 continue; 452 } 453 454 /* Fill the type into the array. */ 455 temp->file_type[0] = line_buf[i]; 456 temp->file_type[1] = line_buf[i + 1]; 457 i += 2; 458 temp->file_type[2] = 0; 459 460 /* Get rid of whitespace after the type. */ 461 for (; i < line_len; i++) { 462 if (!isspace(line_buf[i])) 463 break; 464 } 465 466 if (i == line_len) { 467 file_context_node_destroy(temp); 468 free(temp); 469 continue; 470 } 471 } 472 473 /* Parse out the context from the line. */ 474 start = i; 475 while (i < line_len && (!isspace(line_buf[i]))) 476 i++; 477 finish = i; 478 479 context_len = finish - start; 480 481 temp->context = (char*)strndup(&line_buf[start], context_len); 482 if (!temp->context) { 483 file_context_node_destroy(temp); 484 free(temp); 485 free(line_buf); 486 fprintf(stderr, "Error: failure allocating memory.\n"); 487 fc_free_file_context_node_list(head); 488 return 1; 489 } 490 491 /* Get rid of whitespace after the context. */ 492 for (; i < line_len; i++) { 493 if (!isspace(line_buf[i])) 494 break; 495 } 496 497 /* Parse out the extra from the line. */ 498 start = i; 499 finish = line_len; 500 while (start < finish && (!isspace(line_buf[i - 1]))) 501 finish--; 502 503 if (start < finish && line_buf[start] != '#') { 504 temp->extra = (char*)strndup(&line_buf[start], finish - start); 505 if (!(temp->extra)) { 506 file_context_node_destroy(temp); 507 free(temp); 508 free(line_buf); 509 fprintf(stderr, "Error: failure allocating memory.\n"); 510 fc_free_file_context_node_list(head); 511 return 1; 512 } 513 } 514 515 /* Set all the data about the regular 516 * expression. */ 517 fc_fill_data(temp); 518 519 /* Link this line of code at the end of 520 * the linked list. */ 521 current->next = temp; 522 current = current->next; 523 lines++; 524 } 525 free(line_buf); 526 fclose(in_file); 527 528 /* Create the bucket linked list from the earlier linked list. */ 529 current = head->next; 530 bcurrent = master = 531 (file_context_bucket_t *) 532 malloc(sizeof(file_context_bucket_t)); 533 if (!bcurrent) { 534 printf 535 ("Error: failure allocating memory.\n"); 536 fc_free_file_context_node_list(head); 537 return -1; 538 } 539 bcurrent->next = NULL; 540 bcurrent->data = NULL; 541 542 /* Go until all the nodes have been put in individual buckets. */ 543 while (current) { 544 /* Copy over the file context line into the bucket. */ 545 bcurrent->data = current; 546 current = current->next; 547 548 /* Detach the node in the bucket from the old list. */ 549 bcurrent->data->next = NULL; 550 551 /* If there should be another bucket, put one at the end. */ 552 if (current) { 553 bcurrent->next = 554 (file_context_bucket_t *) 555 malloc(sizeof(file_context_bucket_t)); 556 if (!(bcurrent->next)) { 557 printf 558 ("Error: failure allocating memory.\n"); 559 free(head); 560 fc_free_file_context_node_list(current); 561 fc_merge_sort(master); 562 fc_free_file_context_node_list(master->data); 563 free(master); 564 return -1; 565 } 566 567 /* Make sure the new bucket thinks it's the end of the 568 * list. */ 569 bcurrent->next->next = NULL; 570 571 bcurrent = bcurrent->next; 572 } 573 } 574 575 /* Sort the bucket list. */ 576 fc_merge_sort(master); 577 578 free(head); 579 580 /* Open the output file. */ 581 if (output_name) { 582 if (!(out_file = fopen(output_name, "w"))) { 583 printf("Error: failure opening output file for write.\n"); 584 fc_free_file_context_node_list(master->data); 585 free(master); 586 return -1; 587 } 588 } else { 589 out_file = stdout; 590 } 591 592 /* Output the sorted file_context linked list to the output file. */ 593 current = master->data; 594 595 while (current) { 596 /* Output the path. */ 597 fprintf(out_file, "%s\t\t", current->path); 598 599 /* Output the type, if there is one. */ 600 if (current->file_type) { 601 fprintf(out_file, "%s\t", current->file_type); 602 } 603 604 /* Output the context. */ 605 fprintf(out_file, "%s", current->context); 606 607 /* Output the extra, if there is one. */ 608 if (current->extra) { 609 fprintf(out_file, "\t%s", current->extra); 610 } 611 612 fprintf(out_file, "\n"); 613 614 current = current->next; 615 } 616 617 fc_free_file_context_node_list(master->data); 618 free(master); 619 620 if (output_name) { 621 fclose(out_file); 622 } 623 624 return 0; 625 } 626