libsa/dgraph.c

   1 #ifdef KERNEL
   2 #include <libsa/vers_rsrc.h>
   3 #else
   4 #include <libc.h>
   5 #include <stdlib.h>
   6 #include <stdarg.h>
   7 #include <stdio.h>
   8 #include <string.h>
   9 #include <unistd.h>
  10
  11 #include "KXKext.h"
  12 #include "vers_rsrc.h"
  13 #endif /* KERNEL */
  14
  15 #include "dgraph.h"
  16 #include "load.h"
  17
  18
  19 static void __dgraph_entry_free(dgraph_entry_t * entry);
  20
  21 #ifdef KERNEL
  22 /*******************************************************************************
  23 *
  24 *******************************************************************************/
  25 char * strdup(const char * string)
  26 {
  27     char * dup = 0;
  28     unsigned int length;
  29
  30     length = strlen(string);
  31     dup = (char *)malloc((1+length) * sizeof(char));
  32     if (!dup) {
  33         return NULL;
  34     }
  35     strcpy(dup, string);
  36     return dup;
  37 }
  38
  39 #endif /* KERNEL */
  40
  41 /*******************************************************************************
  42 *
  43 *******************************************************************************/
  44 dgraph_error_t dgraph_init(dgraph_t * dgraph)
  45 {
  46     bzero(dgraph, sizeof(dgraph_t));
  47
  48     dgraph->capacity = (5);  // pulled from a hat
  49
  50    /* Make sure list is big enough & graph has a good start size.
  51     */
  52     dgraph->graph = (dgraph_entry_t **)malloc(
  53         dgraph->capacity * sizeof(dgraph_entry_t *));
  54
  55     if (!dgraph->graph) {
  56         return dgraph_error;
  57     }
  58
  59     return dgraph_valid;
  60 }
  61
  62 #ifndef KERNEL
  63 /*******************************************************************************
  64 *
  65 *******************************************************************************/
  66 dgraph_error_t dgraph_init_with_arglist(
  67     dgraph_t * dgraph,
  68     int expect_addresses,
  69     const char * dependency_delimiter,
  70     const char * kernel_dependency_delimiter,
  71     int argc,
  72     char * argv[])
  73 {
  74     dgraph_error_t result = dgraph_valid;
  75     unsigned int i;
  76     int found_zero_load_address = 0;
  77     int found_nonzero_load_address = 0;
  78     dgraph_entry_t * current_dependent = NULL;
  79     char kernel_dependencies = 0;
  80
  81     result = dgraph_init(dgraph);
  82     if (result != dgraph_valid) {
  83         return result;
  84     }
  85
  86     for (i = 0; i < argc; i++) {
  87         vm_address_t load_address = 0;
  88
  89         if (0 == strcmp(argv[i], dependency_delimiter)) {
  90             kernel_dependencies = 0;
  91             current_dependent = NULL;
  92             continue;
  93         } else if (0 == strcmp(argv[i], kernel_dependency_delimiter)) {
  94             kernel_dependencies = 1;
  95             current_dependent = NULL;
  96             continue;
  97         }
  98
  99         if (expect_addresses) {
 100             char * address = rindex(argv[i], '@');
 101             if (address) {
 102                 *address++ = 0;  // snip the address from the filename
 103                 load_address = strtoul(address, NULL, 0);
 104             }
 105         }
 106
 107         if (!current_dependent) {
 108            current_dependent = dgraph_add_dependent(dgraph, argv[i],
 109                /* expected kmod name */ NULL, /* expected vers */ 0,
 110                load_address, 0);
 111            if (!current_dependent) {
 112                return dgraph_error;
 113            }
 114         } else {
 115             if (!dgraph_add_dependency(dgraph, current_dependent, argv[i],
 116                /* expected kmod name */ NULL, /* expected vers */ 0,
 117                load_address, kernel_dependencies)) {
 118
 119                return dgraph_error;
 120             }
 121         }
 122     }
 123
 124     dgraph->root = dgraph_find_root(dgraph);
 125     dgraph_establish_load_order(dgraph);
 126
 127     if (!dgraph->root) {
 128         kload_log_error("dependency graph has no root" KNL);
 129         return dgraph_invalid;
 130     }
 131
 132     if (dgraph->root->is_kernel_component && !dgraph->root->is_symbol_set) {
 133         kload_log_error("dependency graph root is a kernel component" KNL);
 134         return dgraph_invalid;
 135     }
 136
 137     for (i = 0; i < dgraph->length; i++) {
 138         if (dgraph->graph[i]->loaded_address == 0) {
 139             found_zero_load_address = 1;
 140         } else {
 141             found_nonzero_load_address = 1;
 142         }
 143         if ( (i > 0) &&
 144              (found_zero_load_address && found_nonzero_load_address)) {
 145
 146             kload_log_error(
 147                 "load addresses must be specified for all module files" KNL);
 148             return dgraph_invalid;
 149         }
 150     }
 151
 152     return dgraph_valid;
 153 }
 154 #endif /* not KERNEL */
 155
 156 /*******************************************************************************
 157 *
 158 *******************************************************************************/
 159 static void __dgraph_entry_free(dgraph_entry_t * entry)
 160 {
 161     if (entry->name) {
 162         free(entry->name);
 163         entry->name = NULL;
 164     }
 165     if (entry->expected_kmod_name) {
 166         free(entry->expected_kmod_name);
 167         entry->expected_kmod_name = NULL;
 168     }
 169     if (entry->expected_kmod_vers) {
 170         free(entry->expected_kmod_vers);
 171         entry->expected_kmod_vers = NULL;
 172     }
 173     if (entry->dependencies) {
 174         free(entry->dependencies);
 175         entry->dependencies = NULL;
 176     }
 177     if (entry->symbols_malloc) {
 178         free((void *) entry->symbols_malloc);
 179         entry->symbols_malloc = NULL;
 180     }
 181     free(entry);
 182     return;
 183 }
 184
 185 /*******************************************************************************
 186 *
 187 *******************************************************************************/
 188 void dgraph_free(
 189     dgraph_t * dgraph,
 190     int free_graph)
 191 {
 192     unsigned int entry_index;
 193
 194     if (!dgraph) {
 195         return;
 196     }
 197
 198     for (entry_index = 0; entry_index < dgraph->length; entry_index++) {
 199         dgraph_entry_t * current = dgraph->graph[entry_index];
 200         __dgraph_entry_free(current);
 201     }
 202
 203     if (dgraph->graph) {
 204         free(dgraph->graph);
 205         dgraph->graph = NULL;
 206     }
 207
 208     if (dgraph->load_order) {
 209         free(dgraph->load_order);
 210         dgraph->load_order = NULL;
 211     }
 212
 213     if (free_graph && dgraph) {
 214         free(dgraph);
 215     }
 216
 217     return;
 218 }
 219
 220
 221 /*******************************************************************************
 222 *
 223 *******************************************************************************/
 224 dgraph_entry_t * dgraph_find_root(dgraph_t * dgraph) {
 225     dgraph_entry_t * root = NULL;
 226     dgraph_entry_t * candidate = NULL;
 227     unsigned int candidate_index;
 228     unsigned int scan_index;
 229     unsigned int dep_index;
 230
 231
 232    /* Scan each entry in the graph for one that isn't in any other entry's
 233     * dependencies.
 234     */
 235     for (candidate_index = 0; candidate_index < dgraph->length;
 236          candidate_index++) {
 237
 238         candidate = dgraph->graph[candidate_index];
 239
 240         for (scan_index = 0; scan_index < dgraph->length; scan_index++) {
 241
 242             dgraph_entry_t * scan_entry = dgraph->graph[scan_index];
 243             if (candidate == scan_entry) {
 244                 // don't check yourself
 245                 continue;
 246             }
 247             for (dep_index = 0; dep_index < scan_entry->num_dependencies;
 248                  dep_index++) {
 249
 250                /* If the dependency being checked is the candidate,
 251                 *  then the candidate can't be the root.
 252                 */
 253                 dgraph_entry_t * check = scan_entry->dependencies[dep_index];
 254
 255                 if (check == candidate) {
 256                     candidate = NULL;
 257                     break;
 258                 }
 259             }
 260
 261            /* If the candidate was rejected, then hop out of this loop.
 262             */
 263             if (!candidate) {
 264                 break;
 265             }
 266         }
 267
 268        /* If we got here, the candidate is a valid one. However, if we already
 269         * found another, that means we have two possible roots (or more), which
 270         * is NOT ALLOWED.
 271         */
 272         if (candidate) {
 273             if (root) {
 274                 kload_log_error("dependency graph has multiple roots "
 275                     "(%s and %s)" KNL, root->name, candidate->name);
 276                 return NULL;  // two valid roots, illegal
 277             } else {
 278                 root = candidate;
 279             }
 280         }
 281     }
 282
 283     if (!root) {
 284         kload_log_error("dependency graph has no root node" KNL);
 285     }
 286
 287     return root;
 288 }
 289
 290 /*******************************************************************************
 291 *
 292 *******************************************************************************/
 293 dgraph_entry_t ** fill_backward_load_order(
 294     dgraph_entry_t ** backward_load_order,
 295     unsigned int * list_length,
 296     dgraph_entry_t * first_entry,
 297     unsigned int * last_index /* out param */)
 298 {
 299     int i;
 300     unsigned int scan_index = 0;
 301     unsigned int add_index = 0;
 302     dgraph_entry_t * scan_entry;
 303
 304     if (*list_length == 0) {
 305         if (backward_load_order) {
 306             free(backward_load_order);
 307             backward_load_order = NULL;
 308         }
 309         goto finish;
 310     }
 311
 312     backward_load_order[add_index++] = first_entry;
 313
 314     while (scan_index < add_index) {
 315
 316         if (add_index > 255) {
 317             kload_log_error(
 318                 "dependency list for %s ridiculously long; probably a loop" KNL,
 319                 first_entry->name);
 320             if (backward_load_order) {
 321                 free(backward_load_order);
 322                 backward_load_order = NULL;
 323             }
 324             goto finish;
 325         }
 326
 327         scan_entry = backward_load_order[scan_index++];
 328
 329        /* Increase the load order list if needed.
 330         */
 331         if (add_index + scan_entry->num_dependencies > (*list_length)) {
 332             (*list_length) *= 2;
 333             backward_load_order = (dgraph_entry_t **)realloc(
 334                 backward_load_order,
 335                 (*list_length) * sizeof(dgraph_entry_t *));
 336             if (!backward_load_order) {
 337                 goto finish;
 338             }
 339         }
 340
 341        /* Put the dependencies of the scanning entry into the list.
 342         */
 343         for (i = 0; i < scan_entry->num_dependencies; i++) {
 344             backward_load_order[add_index++] =
 345                 scan_entry->dependencies[i];
 346         }
 347     }
 348
 349 finish:
 350
 351     if (last_index) {
 352         *last_index = add_index;
 353     }
 354     return backward_load_order;
 355 }
 356
 357 /*******************************************************************************
 358 *
 359 *******************************************************************************/
 360 int dgraph_establish_load_order(dgraph_t * dgraph) {
 361     unsigned int total_dependencies;
 362     unsigned int entry_index;
 363     unsigned int list_index;
 364     unsigned int backward_index;
 365     unsigned int forward_index;
 366     size_t load_order_size;
 367     size_t backward_load_order_size;
 368     dgraph_entry_t ** backward_load_order;
 369
 370    /* Lose the old load_order list. Size can change, so it's easier to just
 371     * recreate from scratch.
 372     */
 373     if (dgraph->load_order) {
 374         free(dgraph->load_order);
 375         dgraph->load_order = NULL;
 376     }
 377
 378    /* Figure how long the list needs to be to accommodate the max possible
 379     * entries from the graph. Duplicates get weeded out, but the list
 380     * initially has to accommodate them all.
 381     */
 382     total_dependencies = dgraph->length;
 383
 384     for (entry_index = 0; entry_index < dgraph->length; entry_index ++) {
 385         dgraph_entry_t * curdep = dgraph->graph[entry_index];
 386         total_dependencies += curdep->num_dependencies;
 387     }
 388
 389    /* Hmm, nothing to do!
 390     */
 391     if (!total_dependencies) {
 392         return 1;
 393     }
 394
 395     backward_load_order_size = total_dependencies * sizeof(dgraph_entry_t *);
 396
 397     backward_load_order = (dgraph_entry_t **)malloc(backward_load_order_size);
 398     if (!backward_load_order) {
 399         kload_log_error("malloc failure" KNL);
 400         return 0;
 401     }
 402     bzero(backward_load_order, backward_load_order_size);
 403
 404     backward_load_order = fill_backward_load_order(backward_load_order,
 405         &total_dependencies, dgraph->root, &list_index);
 406     if (!backward_load_order) {
 407         kload_log_error("error establishing load order" KNL);
 408         return 0;
 409     }
 410
 411     load_order_size = dgraph->length * sizeof(dgraph_entry_t *);
 412     dgraph->load_order = (dgraph_entry_t **)malloc(load_order_size);
 413     if (!dgraph->load_order) {
 414         kload_log_error("malloc failure" KNL);
 415         return 0;
 416     }
 417     bzero(dgraph->load_order, load_order_size);
 418
 419
 420    /* Reverse the list into the dgraph's load_order list,
 421     * removing any duplicates.
 422     */
 423     backward_index = list_index;
 424     //
 425     // the required 1 is taken off in loop below!
 426
 427     forward_index = 0;
 428     do {
 429         dgraph_entry_t * current_entry;
 430         unsigned int already_got_it = 0;
 431
 432         backward_index--;
 433
 434        /* Get the entry to check.
 435         */
 436         current_entry = backward_load_order[backward_index];
 437
 438        /* Did we already get it?
 439         */
 440         for (list_index = 0; list_index < forward_index; list_index++) {
 441             if (current_entry == dgraph->load_order[list_index]) {
 442                 already_got_it = 1;
 443                 break;
 444             }
 445         }
 446
 447         if (already_got_it) {
 448             continue;
 449         }
 450
 451        /* Haven't seen it before; tack it onto the load-order list.
 452         */
 453         dgraph->load_order[forward_index++] = current_entry;
 454
 455     } while (backward_index > 0);
 456
 457     free(backward_load_order);
 458
 459     return 1;
 460 }
 461
 462 /*******************************************************************************
 463 *
 464 *******************************************************************************/
 465 void dgraph_log(dgraph_t * depgraph)
 466 {
 467     unsigned int i, j;
 468
 469     kload_log_message("flattened dependency list: " KNL);
 470     for (i = 0; i < depgraph->length; i++) {
 471         dgraph_entry_t * current = depgraph->graph[i];
 472
 473         kload_log_message("    %s" KNL, current->name);
 474         kload_log_message("      is kernel component: %s" KNL,
 475             current->is_kernel_component ? "yes" : "no");
 476         kload_log_message("      expected kmod name: [%s]" KNL,
 477             current->expected_kmod_name);
 478         kload_log_message("      expected kmod vers: [%s]" KNL,
 479             current->expected_kmod_vers);
 480     }
 481     kload_log_message("" KNL);
 482
 483     kload_log_message("load order dependency list: " KNL);
 484     for (i = 0; i < depgraph->length; i++) {
 485         dgraph_entry_t * current = depgraph->load_order[i];
 486         kload_log_message("    %s" KNL, current->name);
 487     }
 488     kload_log_message("" KNL);
 489
 490     kload_log_message("dependency graph: " KNL);
 491     for (i = 0; i < depgraph->length; i++) {
 492         dgraph_entry_t * current = depgraph->graph[i];
 493         for (j = 0; j < current->num_dependencies; j++) {
 494             dgraph_entry_t * cdep = current->dependencies[j];
 495             kload_log_message("  %s -> %s" KNL, current->name, cdep->name);
 496         }
 497     }
 498     kload_log_message("" KNL);
 499
 500     return;
 501 }
 502
 503 /*******************************************************************************
 504 *
 505 *******************************************************************************/
 506 dgraph_entry_t * dgraph_find_dependent(dgraph_t * dgraph, const char * name)
 507 {
 508     unsigned int i;
 509
 510     for (i = 0; i < dgraph->length; i++) {
 511         dgraph_entry_t * current_entry = dgraph->graph[i];
 512         if (0 == strcmp(name, current_entry->name)) {
 513             return current_entry;
 514         }
 515     }
 516
 517     return NULL;
 518 }
 519
 520 /*******************************************************************************
 521 *
 522 *******************************************************************************/
 523 dgraph_entry_t * dgraph_add_dependent(
 524     dgraph_t * dgraph,
 525     const char * name,
 526 #ifdef KERNEL
 527     void * object,
 528     size_t object_length,
 529     bool   object_is_kmem,
 530 #endif /* KERNEL */
 531     const char * expected_kmod_name,
 532     const char * expected_kmod_vers,
 533     vm_address_t load_address,
 534     char is_kernel_component)
 535 {
 536     int error = 0;
 537     dgraph_entry_t * found_entry = NULL;
 538     dgraph_entry_t * new_entry = NULL;    // free on error
 539     dgraph_entry_t * the_entry = NULL;    // returned
 540
 541    /* Already got it? Great!
 542     */
 543     found_entry = dgraph_find_dependent(dgraph, name);
 544     if (found_entry) {
 545         if (found_entry->is_kernel_component != is_kernel_component) {
 546             kload_log_error(
 547                 "%s is already defined as a %skernel component" KNL,
 548                 name, found_entry->is_kernel_component ? "" : "non-");
 549             error = 1;
 550             goto finish;
 551         }
 552
 553         if (load_address != 0) {
 554             if (found_entry->loaded_address == 0) {
 555                 found_entry->do_load = 0;
 556                 found_entry->loaded_address = load_address;
 557             } else if (found_entry->loaded_address != load_address) {
 558                 kload_log_error(
 559                    "%s has been assigned two different addresses (0x%x, 0x%x) KNL",
 560                     found_entry->name,
 561                     found_entry->loaded_address,
 562                     load_address);
 563                 error = 1;
 564                 goto finish;
 565             }
 566         }
 567         the_entry = found_entry;
 568         goto finish;
 569     }
 570
 571    /* If the graph is full, make it bigger.
 572     */
 573     if (dgraph->length == dgraph->capacity) {
 574         unsigned int old_capacity = dgraph->capacity;
 575         dgraph_entry_t ** newgraph;
 576
 577         dgraph->capacity *= 2;
 578         newgraph = (dgraph_entry_t **)malloc(dgraph->capacity *
 579             sizeof(dgraph_entry_t *));
 580         if (!newgraph) {
 581             return NULL;
 582         }
 583         memcpy(newgraph, dgraph->graph, old_capacity * sizeof(dgraph_entry_t *));
 584         free(dgraph->graph);
 585         dgraph->graph = newgraph;
 586     }
 587
 588     if (strlen(expected_kmod_name) > KMOD_MAX_NAME - 1) {
 589         kload_log_error("expected kmod name \"%s\" is too long" KNL,
 590             expected_kmod_name);
 591         error = 1;
 592         goto finish;
 593     }
 594
 595    /* Fill it.
 596     */
 597     new_entry = (dgraph_entry_t *)malloc(sizeof(dgraph_entry_t));
 598     if (!new_entry) {
 599         error = 1;
 600         goto finish;
 601     }
 602     bzero(new_entry, sizeof(dgraph_entry_t));
 603     new_entry->expected_kmod_name = strdup(expected_kmod_name);
 604     if (!new_entry->expected_kmod_name) {
 605         error = 1;
 606         goto finish;
 607     }
 608     new_entry->expected_kmod_vers = strdup(expected_kmod_vers);
 609     if (!new_entry->expected_kmod_vers) {
 610         error = 1;
 611         goto finish;
 612     }
 613     new_entry->is_kernel_component = is_kernel_component;
 614
 615     // /hacks
 616     new_entry->is_symbol_set = (2 & is_kernel_component);
 617     new_entry->opaques = !strncmp(new_entry->expected_kmod_name,
 618                                     "com.apple.kpi", strlen("com.apple.kpi"));
 619     // hacks/
 620
 621     dgraph->has_symbol_sets |= new_entry->is_symbol_set;
 622
 623     new_entry->do_load = !is_kernel_component;
 624
 625 #ifndef KERNEL
 626     new_entry->object = NULL;   // provided elswehere in userland
 627     new_entry->object_length = 0;
 628 #else
 629     new_entry->object = object;
 630     new_entry->object_length = object_length;
 631     new_entry->object_is_kmem = object_is_kmem;
 632 #endif /* KERNEL */
 633     new_entry->name = strdup(name);
 634     if (!new_entry->name) {
 635         error = 1;
 636         goto finish;
 637     }
 638     dgraph->graph[dgraph->length++] = new_entry;
 639
 640
 641    /* Create a dependency list for the entry. Start with 5 slots.
 642     */
 643     new_entry->dependencies_capacity = 5;
 644     new_entry->num_dependencies = 0;
 645     new_entry->dependencies = (dgraph_entry_t **)malloc(
 646         new_entry->dependencies_capacity * sizeof(dgraph_entry_t *));
 647     if (!new_entry->dependencies) {
 648         error = 1;
 649         goto finish;
 650     }
 651
 652     if (new_entry->loaded_address == 0) {
 653         new_entry->loaded_address = load_address;
 654         if (load_address != 0) {
 655             new_entry->do_load = 0;
 656         }
 657     }
 658
 659     the_entry = new_entry;
 660
 661 finish:
 662     if (error) {
 663         if (new_entry) __dgraph_entry_free(new_entry);
 664         the_entry = new_entry = NULL;
 665     }
 666     return the_entry;
 667 }
 668
 669 /*******************************************************************************
 670 *
 671 *******************************************************************************/
 672 dgraph_entry_t * dgraph_add_dependency(
 673     dgraph_t * dgraph,
 674     dgraph_entry_t * current_dependent,
 675     const char * name,
 676 #ifdef KERNEL
 677     void * object,
 678     size_t object_length,
 679     bool   object_is_kmem,
 680 #endif /* KERNEL */
 681     const char * expected_kmod_name,
 682     const char * expected_kmod_vers,
 683     vm_address_t load_address,
 684     char is_kernel_component)
 685 {
 686     dgraph_entry_t * dependency = NULL;
 687     unsigned int i = 0;
 688
 689    /* If the dependent's dependency list is full, make it bigger.
 690     */
 691     if (current_dependent->num_dependencies ==
 692         current_dependent->dependencies_capacity) {
 693
 694         unsigned int old_capacity = current_dependent->dependencies_capacity;
 695         dgraph_entry_t ** newlist;
 696
 697         current_dependent->dependencies_capacity *= 2;
 698         newlist = (dgraph_entry_t **)malloc(
 699             (current_dependent->dependencies_capacity *
 700              sizeof(dgraph_entry_t *)) );
 701
 702         if (!newlist) {
 703             return NULL;
 704         }
 705         memcpy(newlist, current_dependent->dependencies,
 706             old_capacity * sizeof(dgraph_entry_t *));
 707         free(current_dependent->dependencies);
 708         current_dependent->dependencies = newlist;
 709     }
 710
 711
 712    /* Find or add the entry for the new dependency.
 713     */
 714     dependency = dgraph_add_dependent(dgraph, name,
 715 #ifdef KERNEL
 716          object, object_length, object_is_kmem,
 717 #endif /* KERNEL */
 718          expected_kmod_name, expected_kmod_vers, load_address,
 719          is_kernel_component);
 720     if (!dependency) {
 721        return NULL;
 722     }
 723
 724     if (dependency == current_dependent) {
 725         kload_log_error("attempt to set dependency on itself: %s" KNL,
 726             current_dependent->name);
 727         return NULL;
 728     }
 729
 730     for (i = 0; i < current_dependent->num_dependencies; i++) {
 731         dgraph_entry_t * this_dependency = current_dependent->dependencies[i];
 732         if (this_dependency == dependency) {
 733             return dependency;
 734         }
 735     }
 736
 737    /* Fill in the dependency.
 738     */
 739     current_dependent->dependencies[current_dependent->num_dependencies] =
 740         dependency;
 741     current_dependent->num_dependencies++;
 742
 743     current_dependent->opaque_link |= dependency->opaques;
 744     dgraph->has_opaque_links       |= current_dependent->opaque_link;
 745
 746     return dependency;
 747 }