libsa/dgraph.c

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