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