support/fc_sort.c

   1 /* Copyright 2005, 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
  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 not,
  85  *      -> a is less specific than b.
  86  */
  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  */
 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  */
 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  */
 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  */
 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 != 3) {
 332                 fprintf(stderr, "Usage: %s <infile> <outfile>\n",argv[0]);
 333                 return 1;
 334         }
 335
 336         input_name = argv[1];
 337         output_name = argv[2];
 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
 350         /* Parse the file into a file_context linked list. */
 351         line_buf = NULL;
 352
 353         while ( getline(&line_buf, &buf_len, in_file) != -1 ){
 354                 line_len = strlen(line_buf);
 355                 if( line_len == 0 || line_len == 1)
 356                         continue;
 357                 /* Get rid of whitespace from the front of the line. */
 358                 for (i = 0; i < line_len; i++) {
 359                         if (!isspace(line_buf[i]))
 360                                 break;
 361                 }
 362
 363
 364                 if (i >= line_len)
 365                         continue;
 366                 /* Check if the line isn't empty and isn't a comment */
 367                 if (line_buf[i] == '#')
 368                         continue;
 369
 370                 /* We have a valid line - allocate a new node. */
 371                 temp = (file_context_node_t *)malloc(sizeof(file_context_node_t));
 372                 if (!temp) {
 373                         fprintf(stderr, "Error: failure allocating memory.\n");
 374                         return 1;
 375                 }
 376                 temp->next = NULL;
 377                 memset(temp, 0, sizeof(file_context_node_t));
 378
 379                 /* Parse out the regular expression from the line. */
 380                 start = i;
 381
 382
 383                 while (i < line_len && (!isspace(line_buf[i])))
 384                         i++;
 385                 finish = i;
 386
 387
 388                 regex_len = finish - start;
 389
 390                 if (regex_len == 0) {
 391                         file_context_node_destroy(temp);
 392                         free(temp);
 393
 394
 395                         continue;
 396                 }
 397
 398                 temp->path = (char*)strndup(&line_buf[start], regex_len);
 399                 if (!temp->path) {
 400                         file_context_node_destroy(temp);
 401                         free(temp);
 402                         fprintf(stderr, "Error: failure allocating memory.\n");
 403                         return 1;
 404                 }
 405
 406                 /* Get rid of whitespace after the regular expression. */
 407                 for (; i < line_len; i++) {
 408
 409                         if (!isspace(line_buf[i]))
 410                                 break;
 411                 }
 412
 413                 if (i == line_len) {
 414                         file_context_node_destroy(temp);
 415                         free(temp);
 416                         continue;
 417                 }
 418
 419                 /* Parse out the type from the line (if it
 420                         *  is there). */
 421                 if (line_buf[i] == '-') {
 422                         temp->file_type = (char *)malloc(sizeof(char) * 3);
 423                         if (!(temp->file_type)) {
 424                                 fprintf(stderr, "Error: failure allocating memory.\n");
 425                                 return 1;
 426                         }
 427
 428                         if( i + 2 >= line_len ) {
 429                                 file_context_node_destroy(temp);
 430                                 free(temp);
 431
 432                                 continue;
 433                         }
 434
 435                         /* Fill the type into the array. */
 436                         temp->file_type[0] = line_buf[i];
 437                         temp->file_type[1] = line_buf[i + 1];
 438                         i += 2;
 439                         temp->file_type[2] = 0;
 440
 441                         /* Get rid of whitespace after the type. */
 442                         for (; i < line_len; i++) {
 443                                 if (!isspace(line_buf[i]))
 444                                         break;
 445                         }
 446
 447                         if (i == line_len) {
 448
 449                                 file_context_node_destroy(temp);
 450                                 free(temp);
 451                                 continue;
 452                         }
 453                 }
 454
 455                 /* Parse out the context from the line. */
 456                 start = i;
 457                 while (i < line_len && (!isspace(line_buf[i])))
 458                         i++;
 459                 finish = i;
 460
 461                 context_len = finish - start;
 462
 463                 temp->context = (char*)strndup(&line_buf[start], context_len);
 464                 if (!temp->context) {
 465                         file_context_node_destroy(temp);
 466                         free(temp);
 467                         fprintf(stderr, "Error: failure allocating memory.\n");
 468                         return 1;
 469                 }
 470
 471                 /* Set all the data about the regular
 472                         *  expression. */
 473                 fc_fill_data(temp);
 474
 475                 /* Link this line of code at the end of
 476                         *  the linked list. */
 477                 current->next = temp;
 478                 current = current->next;
 479                 lines++;
 480
 481
 482                 free(line_buf);
 483                 line_buf = NULL;
 484         }
 485         fclose(in_file);
 486
 487         /* Create the bucket linked list from the earlier linked list. */
 488         current = head->next;
 489         bcurrent = master =
 490             (file_context_bucket_t *)
 491             malloc(sizeof(file_context_bucket_t));
 492
 493         /* Go until all the nodes have been put in individual buckets. */
 494         while (current) {
 495                 /* Copy over the file context line into the bucket. */
 496                 bcurrent->data = current;
 497                 current = current->next;
 498
 499                 /* Detatch the node in the bucket from the old list. */
 500                 bcurrent->data->next = NULL;
 501
 502                 /* If there should be another bucket, put one at the end. */
 503                 if (current) {
 504                         bcurrent->next =
 505                             (file_context_bucket_t *)
 506                             malloc(sizeof(file_context_bucket_t));
 507                         if (!(bcurrent->next)) {
 508                                 printf
 509                                     ("Error: failure allocating memory.\n");
 510                                 return -1;
 511                         }
 512
 513                         /* Make sure the new bucket thinks it's the end of the
 514                          *  list. */
 515                         bcurrent->next->next = NULL;
 516
 517                         bcurrent = bcurrent->next;
 518                 }
 519
 520         }
 521
 522         /* Sort the bucket list. */
 523         fc_merge_sort(master);
 524
 525         /* Open the output file. */
 526         if (!(out_file = fopen(argv[2], "w"))) {
 527                 printf("Error: failure opening output file for write.\n");
 528                 return -1;
 529         }
 530
 531         /* Output the sorted file_context linked list to the output file. */
 532         current = master->data;
 533         while (current) {
 534                 /* Output the path. */
 535                 fprintf(out_file, "%s\t\t", current->path);
 536
 537                 /* Output the type, if there is one. */
 538                 if (current->file_type) {
 539                         fprintf(out_file, "%s\t", current->file_type);
 540                 }
 541
 542                 /* Output the context. */
 543                 fprintf(out_file, "%s\n", current->context);
 544
 545                 /* Remove the node. */
 546                 temp = current;
 547                 current = current->next;
 548
 549                 file_context_node_destroy(temp);
 550                 free(temp);
 551
 552         }
 553         free(master);
 554
 555         fclose(out_file);
 556
 557         return 0;
 558 }