#ifdef KERNEL
#include <libsa/vers_rsrc.h>
#else
#include <libc.h>
#include <stdlib.h>
#include <stdarg.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include "KXKext.h"
#include "vers_rsrc.h"
#endif
#include "dgraph.h"
#include "load.h"
static void __dgraph_entry_free(dgraph_entry_t * entry);
#ifdef KERNEL
char * strdup(const char * string)
{
char * dup = 0;
unsigned int length;
length = strlen(string);
dup = (char *)malloc((1+length) * sizeof(char));
if (!dup) {
return NULL;
}
strcpy(dup, string);
return dup;
}
#endif
dgraph_error_t dgraph_init(dgraph_t * dgraph)
{
bzero(dgraph, sizeof(dgraph_t));
dgraph->capacity = (5);
dgraph->graph = (dgraph_entry_t **)malloc(
dgraph->capacity * sizeof(dgraph_entry_t *));
if (!dgraph->graph) {
return dgraph_error;
}
return dgraph_valid;
}
static void __dgraph_entry_free(dgraph_entry_t * entry)
{
if (entry->name) {
free(entry->name);
entry->name = NULL;
}
if (entry->expected_kmod_name) {
free(entry->expected_kmod_name);
entry->expected_kmod_name = NULL;
}
if (entry->expected_kmod_vers) {
free(entry->expected_kmod_vers);
entry->expected_kmod_vers = NULL;
}
if (entry->dependencies) {
free(entry->dependencies);
entry->dependencies = NULL;
}
if (entry->symbols_malloc) {
free((void *) entry->symbols_malloc);
entry->symbols_malloc = NULL;
}
free(entry);
return;
}
void dgraph_free(
dgraph_t * dgraph,
int free_graph)
{
unsigned int entry_index;
if (!dgraph) {
return;
}
for (entry_index = 0; entry_index < dgraph->length; entry_index++) {
dgraph_entry_t * current = dgraph->graph[entry_index];
__dgraph_entry_free(current);
}
if (dgraph->graph) {
free(dgraph->graph);
dgraph->graph = NULL;
}
if (dgraph->load_order) {
free(dgraph->load_order);
dgraph->load_order = NULL;
}
if (free_graph && dgraph) {
free(dgraph);
}
return;
}
dgraph_entry_t * dgraph_find_root(dgraph_t * dgraph) {
dgraph_entry_t * root = NULL;
dgraph_entry_t * candidate = NULL;
unsigned int candidate_index;
unsigned int scan_index;
unsigned int dep_index;
for (candidate_index = 0; candidate_index < dgraph->length;
candidate_index++) {
candidate = dgraph->graph[candidate_index];
for (scan_index = 0; scan_index < dgraph->length; scan_index++) {
dgraph_entry_t * scan_entry = dgraph->graph[scan_index];
if (candidate == scan_entry) {
continue;
}
for (dep_index = 0; dep_index < scan_entry->num_dependencies;
dep_index++) {
dgraph_entry_t * check = scan_entry->dependencies[dep_index];
if (check == candidate) {
candidate = NULL;
break;
}
}
if (!candidate) {
break;
}
}
if (candidate) {
if (root) {
kload_log_error("dependency graph has multiple roots "
"(%s and %s)" KNL, root->name, candidate->name);
return NULL; } else {
root = candidate;
}
}
}
if (!root) {
kload_log_error("dependency graph has no root node" KNL);
}
return root;
}
dgraph_entry_t ** fill_backward_load_order(
dgraph_entry_t ** backward_load_order,
unsigned int * list_length,
dgraph_entry_t * first_entry,
unsigned int * last_index )
{
int i;
unsigned int scan_index = 0;
unsigned int add_index = 0;
dgraph_entry_t * scan_entry;
if (*list_length == 0) {
if (backward_load_order) {
free(backward_load_order);
backward_load_order = NULL;
}
goto finish;
}
backward_load_order[add_index++] = first_entry;
while (scan_index < add_index) {
if (add_index > 255) {
kload_log_error(
"dependency list for %s ridiculously long; probably a loop" KNL,
first_entry->name);
if (backward_load_order) {
free(backward_load_order);
backward_load_order = NULL;
}
goto finish;
}
scan_entry = backward_load_order[scan_index++];
if (add_index + scan_entry->num_dependencies > (*list_length)) {
(*list_length) *= 2;
backward_load_order = (dgraph_entry_t **)realloc(
backward_load_order,
(*list_length) * sizeof(dgraph_entry_t *));
if (!backward_load_order) {
goto finish;
}
}
for (i = 0; i < scan_entry->num_dependencies; i++) {
backward_load_order[add_index++] =
scan_entry->dependencies[i];
}
}
finish:
if (last_index) {
*last_index = add_index;
}
return backward_load_order;
}
int dgraph_establish_load_order(dgraph_t * dgraph) {
unsigned int total_dependencies;
unsigned int entry_index;
unsigned int list_index;
unsigned int backward_index;
unsigned int forward_index;
size_t load_order_size;
size_t backward_load_order_size;
dgraph_entry_t ** backward_load_order;
if (dgraph->load_order) {
free(dgraph->load_order);
dgraph->load_order = NULL;
}
total_dependencies = dgraph->length;
for (entry_index = 0; entry_index < dgraph->length; entry_index ++) {
dgraph_entry_t * curdep = dgraph->graph[entry_index];
total_dependencies += curdep->num_dependencies;
}
if (!total_dependencies) {
return 1;
}
backward_load_order_size = total_dependencies * sizeof(dgraph_entry_t *);
backward_load_order = (dgraph_entry_t **)malloc(backward_load_order_size);
if (!backward_load_order) {
kload_log_error("malloc failure" KNL);
return 0;
}
bzero(backward_load_order, backward_load_order_size);
backward_load_order = fill_backward_load_order(backward_load_order,
&total_dependencies, dgraph->root, &list_index);
if (!backward_load_order) {
kload_log_error("error establishing load order" KNL);
return 0;
}
load_order_size = dgraph->length * sizeof(dgraph_entry_t *);
dgraph->load_order = (dgraph_entry_t **)malloc(load_order_size);
if (!dgraph->load_order) {
kload_log_error("malloc failure" KNL);
return 0;
}
bzero(dgraph->load_order, load_order_size);
backward_index = list_index;
forward_index = 0;
do {
dgraph_entry_t * current_entry;
unsigned int already_got_it = 0;
backward_index--;
current_entry = backward_load_order[backward_index];
for (list_index = 0; list_index < forward_index; list_index++) {
if (current_entry == dgraph->load_order[list_index]) {
already_got_it = 1;
break;
}
}
if (already_got_it) {
continue;
}
dgraph->load_order[forward_index++] = current_entry;
} while (backward_index > 0);
free(backward_load_order);
return 1;
}
void dgraph_log(dgraph_t * depgraph)
{
unsigned int i, j;
kload_log_message("flattened dependency list: " KNL);
for (i = 0; i < depgraph->length; i++) {
dgraph_entry_t * current = depgraph->graph[i];
kload_log_message(" %s" KNL, current->name);
kload_log_message(" is kernel component: %s" KNL,
current->is_kernel_component ? "yes" : "no");
kload_log_message(" expected kmod name: [%s]" KNL,
current->expected_kmod_name);
kload_log_message(" expected kmod vers: [%s]" KNL,
current->expected_kmod_vers);
}
kload_log_message("" KNL);
kload_log_message("load order dependency list: " KNL);
for (i = 0; i < depgraph->length; i++) {
dgraph_entry_t * current = depgraph->load_order[i];
kload_log_message(" %s" KNL, current->name);
}
kload_log_message("" KNL);
kload_log_message("dependency graph: " KNL);
for (i = 0; i < depgraph->length; i++) {
dgraph_entry_t * current = depgraph->graph[i];
for (j = 0; j < current->num_dependencies; j++) {
dgraph_entry_t * cdep = current->dependencies[j];
kload_log_message(" %s -> %s" KNL, current->name, cdep->name);
}
}
kload_log_message("" KNL);
return;
}
dgraph_entry_t * dgraph_find_dependent(dgraph_t * dgraph, const char * name)
{
unsigned int i;
for (i = 0; i < dgraph->length; i++) {
dgraph_entry_t * current_entry = dgraph->graph[i];
if (0 == strcmp(name, current_entry->name)) {
return current_entry;
}
}
return NULL;
}
dgraph_entry_t * dgraph_add_dependent(
dgraph_t * dgraph,
const char * name,
#ifdef KERNEL
void * object,
size_t object_length,
bool object_is_kmem,
#endif
const char * expected_kmod_name,
const char * expected_kmod_vers,
vm_address_t load_address,
char is_kernel_component)
{
int error = 0;
dgraph_entry_t * found_entry = NULL;
dgraph_entry_t * new_entry = NULL; dgraph_entry_t * the_entry = NULL;
found_entry = dgraph_find_dependent(dgraph, name);
if (found_entry) {
if (found_entry->is_kernel_component != is_kernel_component) {
kload_log_error(
"%s is already defined as a %skernel component" KNL,
name, found_entry->is_kernel_component ? "" : "non-");
error = 1;
goto finish;
}
if (load_address != 0) {
if (found_entry->loaded_address == 0) {
found_entry->do_load = 0;
found_entry->loaded_address = load_address;
} else if (found_entry->loaded_address != load_address) {
kload_log_error(
"%s has been assigned two different addresses (0x%x, 0x%x) KNL",
found_entry->name,
found_entry->loaded_address,
load_address);
error = 1;
goto finish;
}
}
the_entry = found_entry;
goto finish;
}
if (dgraph->length == dgraph->capacity) {
unsigned int old_capacity = dgraph->capacity;
dgraph_entry_t ** newgraph;
dgraph->capacity *= 2;
newgraph = (dgraph_entry_t **)malloc(dgraph->capacity *
sizeof(dgraph_entry_t *));
if (!newgraph) {
return NULL;
}
memcpy(newgraph, dgraph->graph, old_capacity * sizeof(dgraph_entry_t *));
free(dgraph->graph);
dgraph->graph = newgraph;
}
if (strlen(expected_kmod_name) > KMOD_MAX_NAME - 1) {
kload_log_error("expected kmod name \"%s\" is too long" KNL,
expected_kmod_name);
error = 1;
goto finish;
}
new_entry = (dgraph_entry_t *)malloc(sizeof(dgraph_entry_t));
if (!new_entry) {
error = 1;
goto finish;
}
bzero(new_entry, sizeof(dgraph_entry_t));
new_entry->expected_kmod_name = strdup(expected_kmod_name);
if (!new_entry->expected_kmod_name) {
error = 1;
goto finish;
}
new_entry->expected_kmod_vers = strdup(expected_kmod_vers);
if (!new_entry->expected_kmod_vers) {
error = 1;
goto finish;
}
new_entry->is_kernel_component = is_kernel_component;
new_entry->is_symbol_set = (2 & is_kernel_component);
new_entry->opaques = 0;
if (!strncmp(new_entry->expected_kmod_name,
"com.apple.kpi", strlen("com.apple.kpi")))
new_entry->opaques |= kOpaqueLink;
if (!strcmp(new_entry->expected_kmod_name,
"com.apple.kernel"))
new_entry->opaques |= kOpaqueLink | kRawKernelLink;
dgraph->has_symbol_sets |= new_entry->is_symbol_set;
new_entry->do_load = !is_kernel_component;
#ifndef KERNEL
new_entry->object = NULL; new_entry->object_length = 0;
#else
new_entry->object = object;
new_entry->object_length = object_length;
new_entry->object_is_kmem = object_is_kmem;
#endif
new_entry->name = strdup(name);
if (!new_entry->name) {
error = 1;
goto finish;
}
dgraph->graph[dgraph->length++] = new_entry;
new_entry->dependencies_capacity = 5;
new_entry->num_dependencies = 0;
new_entry->dependencies = (dgraph_entry_t **)malloc(
new_entry->dependencies_capacity * sizeof(dgraph_entry_t *));
if (!new_entry->dependencies) {
error = 1;
goto finish;
}
if (new_entry->loaded_address == 0) {
new_entry->loaded_address = load_address;
if (load_address != 0) {
new_entry->do_load = 0;
}
}
the_entry = new_entry;
finish:
if (error) {
if (new_entry) __dgraph_entry_free(new_entry);
the_entry = new_entry = NULL;
}
return the_entry;
}
dgraph_entry_t * dgraph_add_dependency(
dgraph_t * dgraph,
dgraph_entry_t * current_dependent,
const char * name,
#ifdef KERNEL
void * object,
size_t object_length,
bool object_is_kmem,
#endif
const char * expected_kmod_name,
const char * expected_kmod_vers,
vm_address_t load_address,
char is_kernel_component)
{
dgraph_entry_t * dependency = NULL;
unsigned int i = 0;
if (current_dependent->num_dependencies ==
current_dependent->dependencies_capacity) {
unsigned int old_capacity = current_dependent->dependencies_capacity;
dgraph_entry_t ** newlist;
current_dependent->dependencies_capacity *= 2;
newlist = (dgraph_entry_t **)malloc(
(current_dependent->dependencies_capacity *
sizeof(dgraph_entry_t *)) );
if (!newlist) {
return NULL;
}
memcpy(newlist, current_dependent->dependencies,
old_capacity * sizeof(dgraph_entry_t *));
free(current_dependent->dependencies);
current_dependent->dependencies = newlist;
}
dependency = dgraph_add_dependent(dgraph, name,
#ifdef KERNEL
object, object_length, object_is_kmem,
#endif
expected_kmod_name, expected_kmod_vers, load_address,
is_kernel_component);
if (!dependency) {
return NULL;
}
if (dependency == current_dependent) {
kload_log_error("attempt to set dependency on itself: %s" KNL,
current_dependent->name);
return NULL;
}
for (i = 0; i < current_dependent->num_dependencies; i++) {
dgraph_entry_t * this_dependency = current_dependent->dependencies[i];
if (this_dependency == dependency) {
return dependency;
}
}
current_dependent->dependencies[current_dependent->num_dependencies] =
dependency;
current_dependent->num_dependencies++;
current_dependent->opaque_link |= dependency->opaques;
dgraph->has_opaque_links |= current_dependent->opaque_link;
return dependency;
}