Repair/RepairCompiler/structextract/typedata.c

   1 /*
   2    This file is part of Kvasir, a Valgrind skin that implements the
   3    C language front-end for the Daikon Invariant Detection System
   4
   5    Copyright (C) 2004 Philip Guo, MIT CSAIL Program Analysis Group
   6
   7    This program is free software; you can redistribute it and/or
   8    modify it under the terms of the GNU General Public License as
   9    published by the Free Software Foundation; either version 2 of the
  10    License, or (at your option) any later version.
  11 */
  12
  13 /* typedata.c:
  14    This file contains functions that serve to complement readelf.c
  15    and arrange the DWARF2 debugging information in an orderly
  16    format within dwarf_entry_array
  17 */
  18
  19 #include <stdio.h>
  20 #include <stdlib.h>
  21 #include <string.h>
  22
  23 #include "typedata.h"
  24 #include "elf/dwarf2.h"
  25
  26 // Global array of all dwarf entries, sorted (hopefully) by dwarf_entry.ID
  27 // so that binary search is possible
  28 // DO NOT MODIFY THIS POINTER MANUALLY!!!
  29 // Representation invariants:
  30 // 1. Every entry in dwarf_entry_array is sorted by ascending ID
  31 //    (This makes binary search possible)
  32 // 2. dwarf_entry_array points to the beginning of the array
  33 // 3. The size of the array is specified by dwarf_entry_array_size
  34 // 4. All function entries are listed adjacent to their formal parameters
  35 // 5. All struct, union, and enumeration entries are listed adjacent
  36 //    to their members
  37 // 6. All entries in the array belong to the file specified by the first
  38 //    compile_unit entry to its left (lower indices) in the array
  39 dwarf_entry* dwarf_entry_array = 0;
  40
  41 // The size of this array
  42 unsigned long dwarf_entry_array_size = 0;
  43
  44
  45 /*----------------------------------------
  46 Extracting type information from DWARF tag
  47 -----------------------------------------*/
  48
  49
  50 /*
  51 Requires:
  52 Modifies:
  53 Returns: 1 if tag = {DW_TAG_base_type, _const_type, _enumerator,
  54                      _formal_parameter, _pointer_type, _array_type, _subprogram,
  55                      _union_type, _enumeration_type, _member,
  56                      _structure_type, _volatile_type, _compile_unit},
  57                      0 otherwise
  58 Effects: Used to determine which entries to record into a dwarf_entry structure;
  59          All relevant entries should be included here
  60 */
  61 char tag_is_relevant_entry(unsigned long tag)
  62 {
  63   return 1;
  64   switch (tag)
  65     {
  66     case DW_TAG_enumeration_type:
  67     case DW_TAG_formal_parameter:
  68     case DW_TAG_member:
  69     case DW_TAG_pointer_type:
  70     case DW_TAG_structure_type:
  71     case DW_TAG_union_type:
  72     case DW_TAG_base_type:
  73     case DW_TAG_const_type:
  74     case DW_TAG_enumerator:
  75     case DW_TAG_subprogram:
  76     case DW_TAG_volatile_type:
  77     case DW_TAG_compile_unit:
  78     case DW_TAG_array_type:
  79     case DW_TAG_subroutine_type:
  80     case DW_TAG_subrange_type:
  81       return 1;
  82     default:
  83       return 0;
  84     }
  85 }
  86
  87 /*
  88 Requires:
  89 Modifies:
  90 Returns: 1 if tag = {DW_TAG_pointer_type, _array_type, _const_type, _volatile_type},
  91                      0 otherwise
  92 Effects: Used to determine if the type is a modifier - modifier types
  93          refer to another type within the dwarf_entry_array after
  94          preprocessing
  95 */
  96 char tag_is_modifier_type(unsigned long tag)
  97 {
  98   switch (tag)
  99     {
 100     case DW_TAG_pointer_type:
 101     case DW_TAG_array_type:
 102     case DW_TAG_const_type:
 103     case DW_TAG_volatile_type:
 104       return 1;
 105     default:
 106       return 0;
 107     }
 108 }
 109
 110 /*
 111 Requires:
 112 Modifies:
 113 Returns: 1 if tag = {DW_TAG_enumeration_type, _structure_type, _union_type},
 114                      0 otherwise
 115 Effects: Used to determine if the type is a collection of some sort -
 116          collections have members and unique type names
 117 */
 118 char tag_is_collection_type(unsigned long tag)
 119 {
 120   switch (tag)
 121     {
 122     case DW_TAG_enumeration_type:
 123     case DW_TAG_structure_type:
 124     case DW_TAG_union_type:
 125       return 1;
 126     default:
 127       return 0;
 128     }
 129 }
 130
 131 // The rest of these should be self-explanatory:
 132 char tag_is_base_type(unsigned long tag)
 133 {
 134   return (tag == DW_TAG_base_type);
 135 }
 136
 137 char tag_is_member(unsigned long tag)
 138 {
 139   return (tag == DW_TAG_member);
 140 }
 141
 142 char tag_is_enumerator(unsigned long tag)
 143 {
 144   return (tag == DW_TAG_enumerator);
 145 }
 146
 147 char tag_is_function(unsigned long tag)
 148 {
 149   return (tag == DW_TAG_subprogram);
 150 }
 151
 152 char tag_is_formal_parameter(unsigned long tag)
 153 {
 154   return (tag == DW_TAG_formal_parameter);
 155 }
 156
 157 char tag_is_compile_unit(unsigned long tag)
 158 {
 159   return (tag == DW_TAG_compile_unit);
 160 }
 161
 162 char tag_is_function_type(unsigned long tag) {
 163   return (tag == DW_TAG_subroutine_type);
 164 }
 165
 166 /*------------------
 167  Attribute listeners
 168  ------------------*/
 169
 170 // Each type stored in dwarf_entry.entry_ptr listens for particular
 171 // attributes.  e.g. collection_type listens for DW_AT_name and DW_AT_byte_size
 172
 173 // DW_AT_location: formal_parameter
 174 // DW_AT_name: collection_type, member, enumerator, function, formal_parameter, compile_unit
 175 // DW_AT_byte_size: base_type, collection_type, member
 176 // DW_AT_bit_offset: base_type, member
 177 // DW_AT_bit_size: base_type, member
 178 // DW_AT_const_value: enumerator
 179 // DW_AT_data_member_location: member
 180 // DW_AT_type: modifier, member, function, formal_parameter
 181 // DW_AT_encoding: base_type
 182 // DW_AT_comp_dir: compile_unit
 183 // DW_AT_external: function
 184 // DW_AT_low_pc: function
 185
 186 // Returns: 1 if the entry has a type that is listening for the
 187 // given attribute (attr), 0 otherwise
 188 char entry_is_listening_for_attribute(dwarf_entry* e, unsigned long attr)
 189 {
 190   unsigned long tag;
 191
 192   if(e == 0)
 193     return 0;
 194
 195   tag = e->tag_name;
 196   switch(attr)
 197     {
 198     case DW_AT_location:
 199       return tag_is_formal_parameter(tag);
 200     case DW_AT_name:
 201       return (tag_is_collection_type(tag) ||
 202               tag_is_member(tag) ||
 203               tag_is_enumerator(tag) ||
 204               tag_is_function(tag) ||
 205               tag_is_formal_parameter(tag) ||
 206               tag_is_compile_unit(tag));
 207     case DW_AT_byte_size:
 208       return (tag_is_base_type(tag) ||
 209               tag_is_collection_type(tag) ||
 210               tag_is_member(tag));
 211     case DW_AT_bit_offset:
 212       return (tag_is_base_type(tag) ||
 213               tag_is_member(tag));
 214     case DW_AT_bit_size:
 215       return (tag_is_base_type(tag) ||
 216               tag_is_member(tag));
 217     case DW_AT_const_value:
 218       return tag_is_enumerator(tag);
 219     case DW_AT_data_member_location:
 220       return tag_is_member(tag);
 221     case DW_AT_type:
 222       return (tag_is_modifier_type(tag) ||
 223               tag_is_member(tag) ||
 224               tag_is_function(tag) ||
 225               tag_is_formal_parameter(tag) ||
 226               tag_is_function_type(tag));
 227     case DW_AT_upper_bound:
 228       return (tag==DW_TAG_subrange_type);
 229     case DW_AT_encoding:
 230       return tag_is_base_type(tag);
 231     case DW_AT_comp_dir:
 232       return tag_is_compile_unit(tag);
 233     case DW_AT_external:
 234       return tag_is_function(tag);
 235     case DW_AT_low_pc:
 236       return tag_is_function(tag);
 237     default:
 238       return 0;
 239     }
 240 }
 241
 242 /*--------
 243 Harvesters
 244 ---------*/
 245 // Harvest attribute values into the appropriate entry
 246 // Returns a boolean to signal success or failure
 247 // Remember to only harvest attribute value if the type is listening for it
 248
 249 char harvest_type_value(dwarf_entry* e, unsigned long value)
 250 {
 251   unsigned long tag;
 252   if ((e == 0) || (e->entry_ptr == 0))
 253     return 0;
 254
 255   tag = e->tag_name;
 256
 257   if (tag ==DW_TAG_subrange_type) {
 258     ((array_bound*)e->entry_ptr)->target_ID = value;
 259     return 1;
 260   } else if (tag_is_modifier_type(tag))
 261     {
 262       ((modifier_type*)e->entry_ptr)->target_ID = value;
 263       return 1;
 264     }
 265   else if (tag_is_member(tag))
 266     {
 267       ((member*)e->entry_ptr)->type_ID = value;
 268       return 1;
 269     }
 270   else if (tag_is_function(tag))
 271     {
 272       ((function*)e->entry_ptr)->return_type_ID = value;
 273       return 1;
 274     }
 275   else if (tag_is_formal_parameter(tag))
 276     {
 277       ((formal_parameter*)e->entry_ptr)->type_ID = value;
 278       return 1;
 279     }
 280   else if (tag_is_function_type(tag))
 281     {
 282       ((function_type *)e->entry_ptr)->return_type_ID = value;
 283       return 1;
 284     }
 285   else
 286     return 0;
 287 }
 288
 289 char harvest_byte_size_value(dwarf_entry* e, unsigned long value)
 290 {
 291   unsigned long tag;
 292   if ((e == 0) || (e->entry_ptr == 0))
 293     return 0;
 294
 295   tag = e->tag_name;
 296
 297   if (tag_is_base_type(tag))
 298     {
 299       ((base_type*)e->entry_ptr)->byte_size = value;
 300       return 1;
 301     }
 302   else if (tag_is_collection_type(tag))
 303     {
 304       ((collection_type*)e->entry_ptr)->byte_size = value;
 305       return 1;
 306     }
 307   else if (tag_is_member(tag))
 308     {
 309       ((member*)e->entry_ptr)->byte_size = value;
 310       return 1;
 311     }
 312   else
 313     return 0;
 314 }
 315
 316 char harvest_encoding_value(dwarf_entry* e, unsigned long value)
 317 {
 318   unsigned long tag;
 319   if ((e == 0) || (e->entry_ptr == 0))
 320     return 0;
 321
 322   tag = e->tag_name;
 323
 324   if (tag_is_base_type(tag))
 325     {
 326       ((base_type*)e->entry_ptr)->encoding = value;
 327       return 1;
 328     }
 329   else
 330     return 0;
 331 }
 332
 333 char harvest_bit_size_value(dwarf_entry* e, unsigned long value)
 334 {
 335   unsigned long tag;
 336   if ((e == 0) || (e->entry_ptr == 0))
 337     return 0;
 338
 339   tag = e->tag_name;
 340
 341   if (tag_is_base_type(tag))
 342     {
 343       ((base_type*)e->entry_ptr)->bit_size = value;
 344       return 1;
 345     }
 346   else if (tag_is_member(tag))
 347     {
 348       ((member*)e->entry_ptr)->bit_size = value;
 349       return 1;
 350     }
 351   else
 352     return 0;
 353 }
 354
 355
 356 char harvest_bit_offset_value(dwarf_entry* e, unsigned long value)
 357 {
 358   unsigned long tag;
 359   if ((e == 0) || (e->entry_ptr == 0))
 360     return 0;
 361
 362   tag = e->tag_name;
 363
 364   if (tag_is_base_type(tag))
 365     {
 366       ((base_type*)e->entry_ptr)->bit_offset = value;
 367       return 1;
 368     }
 369   else if (tag_is_member(tag))
 370     {
 371       ((member*)e->entry_ptr)->bit_offset = value;
 372       return 1;
 373     }
 374   else
 375     return 0;
 376 }
 377
 378 char harvest_const_value(dwarf_entry* e, unsigned long value)
 379 {
 380   unsigned long tag;
 381   if ((e == 0) || (e->entry_ptr == 0))
 382     return 0;
 383
 384   tag = e->tag_name;
 385
 386   if (tag_is_enumerator(tag))
 387     {
 388       ((enumerator*)e->entry_ptr)->const_value = value;
 389       return 1;
 390     }
 391   else
 392     return 0;
 393 }
 394
 395 char harvest_upper_bound(dwarf_entry* e, unsigned long value)
 396 {
 397   unsigned long tag;
 398   if ((e == 0) || (e->entry_ptr == 0))
 399     return 0;
 400
 401   tag = e->tag_name;
 402
 403   if (tag==DW_TAG_subrange_type)
 404     {
 405       ((array_bound*)e->entry_ptr)->upperbound = value;
 406       return 1;
 407     }
 408   else
 409     return 0;
 410 }
 411
 412 // REMEMBER to use strdup to make a COPY of the string
 413 // or else you will run into SERIOUS memory corruption
 414 // problems when readelf.c frees those strings from memory!!!
 415 char harvest_name(dwarf_entry* e, const char* str)
 416 {
 417   unsigned long tag;
 418   if ((e == 0) || (e->entry_ptr == 0))
 419     return 0;
 420
 421   tag = e->tag_name;
 422
 423   if (tag_is_enumerator(tag))
 424     {
 425       ((enumerator*)e->entry_ptr)->name = strdup(str);
 426       return 1;
 427     }
 428   else if (tag_is_collection_type(tag))
 429     {
 430       ((collection_type*)e->entry_ptr)->name = strdup(str);
 431       return 1;
 432     }
 433   else if (tag_is_member(tag))
 434     {
 435       ((member*)e->entry_ptr)->name = strdup(str);
 436       return 1;
 437     }
 438   else if (tag_is_function(tag))
 439     {
 440       ((function*)e->entry_ptr)->name = strdup(str);
 441       return 1;
 442     }
 443   else if (tag_is_formal_parameter(tag))
 444     {
 445       ((formal_parameter*)e->entry_ptr)->name = strdup(str);
 446       return 1;
 447     }
 448   else if (tag_is_compile_unit(tag))
 449     {
 450       ((compile_unit*)e->entry_ptr)->filename = strdup(str);
 451       return 1;
 452     }
 453   else
 454     return 0;
 455 }
 456
 457 char harvest_comp_dir(dwarf_entry* e, const char* str)
 458 {
 459   unsigned long tag;
 460   if ((e == 0) || (e->entry_ptr == 0))
 461     return 0;
 462
 463   tag = e->tag_name;
 464
 465   if (tag_is_compile_unit(tag))
 466     {
 467       ((compile_unit*)e->entry_ptr)->comp_dir = strdup(str);
 468       return 1;
 469     }
 470   else
 471     return 0;
 472 }
 473
 474 char harvest_location(dwarf_entry* e, long value)
 475 {
 476   unsigned long tag;
 477   if ((e == 0) || (e->entry_ptr == 0))
 478     return 0;
 479
 480   tag = e->tag_name;
 481
 482   if (tag_is_formal_parameter(tag))
 483     {
 484       ((formal_parameter*)e->entry_ptr)->location = value;
 485       return 1;
 486     }
 487   else
 488     return 0;
 489 }
 490
 491 char harvest_data_member_location(dwarf_entry* e, long value)
 492 {
 493   unsigned long tag;
 494   if ((e == 0) || (e->entry_ptr == 0))
 495     return 0;
 496
 497   tag = e->tag_name;
 498
 499   if (tag_is_member(tag))
 500     {
 501       ((member*)e->entry_ptr)->data_member_location = value;
 502       return 1;
 503     }
 504   else
 505     return 0;
 506 }
 507
 508 char harvest_string(dwarf_entry* e, unsigned long attr, const char* str)
 509 {
 510   if ((e == 0) || (e->entry_ptr == 0))
 511     return 0;
 512
 513   if (attr == DW_AT_name)
 514     return harvest_name(e, str);
 515   else if (attr == DW_AT_comp_dir)
 516     return harvest_comp_dir(e, str);
 517   else
 518     return 0;
 519 }
 520
 521 char harvest_external_flag_value(dwarf_entry *e, unsigned long value) {
 522   unsigned long tag;
 523   if ((e == 0) || (e->entry_ptr == 0))
 524     return 0;
 525
 526   tag = e->tag_name;
 527
 528   if (tag_is_function(tag))
 529     {
 530       ((function*)e->entry_ptr)->is_external = value;
 531       return 1;
 532     }
 533   else
 534     return 0;
 535 }
 536
 537 char harvest_address_value(dwarf_entry* e, unsigned long attr,
 538                            unsigned long value) {
 539   unsigned long tag;
 540   if ((e == 0) || (e->entry_ptr == 0))
 541     return 0;
 542
 543   tag = e->tag_name;
 544
 545   if (tag_is_function(tag) && attr == DW_AT_low_pc)
 546     {
 547       ((function*)e->entry_ptr)->start_pc = value;
 548       return 1;
 549     }
 550   else
 551     return 0;
 552 }
 553
 554
 555 char harvest_ordinary_unsigned_value(dwarf_entry* e, unsigned long attr, unsigned long value)
 556 {
 557   if ((e == 0) || (e->entry_ptr == 0))
 558     return 0;
 559
 560   // Multiplex since
 561   // DW_AT_byte_size, DW_AT_encoding, DW_AT_const_value,
 562   // DW_AT_bit_size, DW_AT_bit_offset and DW_AT_external
 563   // return ordinary unsigned data
 564   switch(attr)
 565     {
 566     case DW_AT_byte_size:
 567       return harvest_byte_size_value(e, value);
 568     case DW_AT_encoding:
 569       return harvest_encoding_value(e, value);
 570     case DW_AT_const_value:
 571       return harvest_const_value(e, value);
 572     case DW_AT_upper_bound:
 573       return harvest_upper_bound(e, value);
 574     case DW_AT_bit_size:
 575       return harvest_bit_size_value(e, value);
 576     case DW_AT_bit_offset:
 577       return harvest_bit_offset_value(e, value);
 578     case DW_AT_external:
 579       return harvest_external_flag_value(e, value);
 580     default:
 581       return 0;
 582     }
 583 }
 584
 585 /*
 586 Requires: dwarf_entry_array initialized
 587 Modifies:
 588 Returns: success
 589 Effects: Performs a binary search through dwarf_entry_array, looking for
 590          the entry with the matching ID field (target_ID).
 591          Stores the index of the matching entry in index_ptr
 592 */
 593 char binary_search_dwarf_entry_array(unsigned long target_ID, unsigned long* index_ptr)
 594 {
 595   unsigned long upper = dwarf_entry_array_size - 1;
 596   unsigned long lower = 0;
 597
 598   //  printf("--target_ID: 0x%x, index_ptr: 0x%x, upper.ID: 0x%x, lower.ID: 0x%x\n",
 599          //         target_ID,
 600          //         index_ptr,
 601          //         dwarf_entry_array[upper].ID,
 602          //         dwarf_entry_array[lower].ID);
 603
 604   // First do boundary sanity check to save ourselves lots of useless work:
 605   if ((target_ID > dwarf_entry_array[upper].ID) ||
 606       (target_ID < dwarf_entry_array[lower].ID))
 607     return 0;
 608
 609   while (upper > lower)
 610     {
 611       unsigned long mid = (upper + lower) / 2;
 612       unsigned long cur_ID = dwarf_entry_array[mid].ID;
 613
 614       //      printf("**lower: %d, mid: %d, upper: %d, target_ID: 0x%x, cur_ID: 0x%x\n",
 615       //             lower,
 616       //             mid,
 617       //             upper,
 618       //             target_ID,
 619       //             cur_ID);
 620
 621       // Special case - (upper == (lower + 1)) - that means only 2 entries left to check:
 622       if (upper == (lower + 1))
 623         {
 624           if (target_ID == dwarf_entry_array[lower].ID)
 625             {
 626               *index_ptr = lower;
 627               return 1;
 628             }
 629           else if (target_ID == dwarf_entry_array[upper].ID)
 630             {
 631               *index_ptr = upper;
 632               return 1;
 633             }
 634           else
 635             {
 636               // YOU LOSE!  The target_ID is BETWEEN the lower and upper entries
 637               return 0;
 638             }
 639         }
 640       else if (target_ID == cur_ID) // Right on!
 641         {
 642           *index_ptr = mid;
 643           return 1;
 644         }
 645       else if (target_ID < cur_ID)
 646         {
 647           upper = mid;
 648         }
 649       else if (target_ID > cur_ID)
 650         {
 651           lower = mid;
 652         }
 653     }
 654
 655   // Return 0 if no answer found
 656   return 0;
 657 }
 658
 659 /*
 660 Requires: dwarf_entry_array initialized
 661 Modifies: certain fields within certain entries within dwarf_entry_array
 662           (modifier_type::target_ptr, function::return_type,
 663            member::type_ptr, formal_parameter::type_ptr)
 664 Returns:
 665 Effects: Links every entry with a type_ID to the actual entry of that type
 666          within dwarf_entry_array.  Sets the appropriate type_ptr pointers to point
 667          to entries within dwarf_entry_array where that type resides
 668          (relevant for modifier_type, member, function, and formal_parameter entries)
 669 */
 670 void link_entries_to_type_entries()
 671 {
 672   unsigned long idx;
 673   dwarf_entry* cur_entry = 0;
 674
 675   for (idx = 0; idx < dwarf_entry_array_size; idx++)
 676     {
 677       unsigned long tag;
 678       cur_entry = &dwarf_entry_array[idx];
 679       tag = cur_entry->tag_name;
 680
 681       if (tag_is_modifier_type(tag))
 682         {
 683           char success = 0;
 684           unsigned long target_index = 0;
 685           modifier_type* modifier_ptr = (modifier_type*)(cur_entry->entry_ptr);
 686           unsigned long target_ID = modifier_ptr->target_ID;
 687
 688           // Use a binary search to try to find the index of the entry in the
 689           // array with the corresponding target_ID
 690           success = binary_search_dwarf_entry_array(target_ID, &target_index);
 691           if (success)
 692             {
 693               modifier_ptr->target_ptr=&dwarf_entry_array[target_index];
 694             }
 695           if (tag==DW_TAG_array_type) {
 696             int currentlevel=cur_entry->level;
 697             dwarf_entry* tmp_entry = cur_entry+1;
 698             int dist_to_end=dwarf_entry_array_size-idx;
 699             int member_count=0;
 700             while ((member_count < dist_to_end) // put this first! short-circuit eval.
 701                    && tmp_entry->level> currentlevel)
 702               {
 703                 if (tmp_entry->tag_name==DW_TAG_subrange_type&&(tmp_entry->level==(currentlevel+1)))
 704                   member_count++;
 705                 tmp_entry++;
 706               }
 707             modifier_ptr->array_ptr=(dwarf_entry**)calloc(1,member_count*sizeof(dwarf_entry*));
 708             modifier_ptr->num_array=member_count;
 709             member_count=0;
 710             tmp_entry=cur_entry+1;
 711             while ((member_count < dist_to_end) // put this first! short-circuit eval.
 712                    && tmp_entry->level> currentlevel)
 713               {
 714                 if (tmp_entry->tag_name==DW_TAG_subrange_type&&(tmp_entry->level==(currentlevel+1)))
 715                   modifier_ptr->array_ptr[member_count++]=tmp_entry;
 716                 tmp_entry++;
 717               }
 718           }
 719         }
 720       else if (tag==DW_TAG_subrange_type) {
 721           char success = 0;
 722           unsigned long target_index = 0;
 723           array_bound* bound_ptr = (array_bound*)(cur_entry->entry_ptr);
 724           unsigned long target_ID = bound_ptr->target_ID;
 725
 726           // Use a binary search to try to find the index of the entry in the
 727           // array with the corresponding target_ID
 728           success = binary_search_dwarf_entry_array(target_ID, &target_index);
 729           if (success)
 730             {
 731               bound_ptr->target_ptr=&dwarf_entry_array[target_index];
 732             }
 733       }
 734       else if (tag_is_function(tag))
 735         {
 736           char success = 0;
 737           unsigned long target_index = 0;
 738           function* function_ptr = (function*)(cur_entry->entry_ptr);
 739           unsigned long target_ID = function_ptr->return_type_ID;
 740
 741           // Use a binary search to try to find the index of the entry in the
 742           // array with the corresponding target_ID
 743           success = binary_search_dwarf_entry_array(target_ID, &target_index);
 744           if (success)
 745             {
 746               function_ptr->return_type=&dwarf_entry_array[target_index];
 747             }
 748         }
 749       else if (tag_is_function_type(tag))
 750         {
 751           char success = 0;
 752           unsigned long target_index = 0;
 753           function_type *function_ptr
 754             = (function_type *)(cur_entry->entry_ptr);
 755           unsigned long target_ID = function_ptr->return_type_ID;
 756
 757           // Use a binary search to try to find the index of the entry in the
 758           // array with the corresponding target_ID
 759           success = binary_search_dwarf_entry_array(target_ID, &target_index);
 760           if (success)
 761             {
 762               function_ptr->return_type=&dwarf_entry_array[target_index];
 763             }
 764         }
 765       else if (tag_is_member(tag))
 766         {
 767           char success = 0;
 768           unsigned long target_index = 0;
 769           member* member_ptr = (member*)(cur_entry->entry_ptr);
 770           unsigned long target_ID = member_ptr->type_ID;
 771
 772           // Use a binary search to try to find the index of the entry in the
 773           // array with the corresponding target_ID
 774           success = binary_search_dwarf_entry_array(target_ID, &target_index);
 775           if (success)
 776             {
 777               member_ptr->type_ptr=&dwarf_entry_array[target_index];
 778             }
 779         }
 780       else if (tag_is_formal_parameter(tag))
 781         {
 782           char success = 0;
 783           unsigned long target_index = 0;
 784           formal_parameter* formal_param_ptr = (formal_parameter*)(cur_entry->entry_ptr);
 785           unsigned long target_ID = formal_param_ptr->type_ID;
 786
 787           // Use a binary search to try to find the index of the entry in the
 788           // array with the corresponding target_ID
 789           success = binary_search_dwarf_entry_array(target_ID, &target_index);
 790           if (success)
 791             {
 792               formal_param_ptr->type_ptr=&dwarf_entry_array[target_index];
 793             }
 794         }
 795     }
 796 }
 797
 798 /*
 799 Requires: dist_to_end indicates distance from e until end of dwarf_entry_array,
 800           e points to an element of dwarf_entry_array
 801 Modifies: e->num_members, e->members
 802 Returns:
 803 Effects: Links the collection entry to its members, which are located
 804          adjacent to it in the dwarf_entry array, making sure not to
 805          accidentally segfault by indexing out of bounds
 806          (indicated by dist_to_end param
 807           which indicates distance until the end of the array)
 808 */
 809 void link_collection_to_members(dwarf_entry* e, unsigned long dist_to_end)
 810 {
 811   // 1. Figure out what kind of collection it is (struct, union, enumeration)
 812   // 2. Traverse through subsequent entries, checking if the type_ID
 813   //    is the appropriate member type for that collection
 814   // 3. Stop either when you hit a type_ID that is not a member OR
 815   //    when you are about to run out of array bounds
 816   // 4. Store the subsequent array entry (e + 1) as pointer to first member
 817   //    (as long as its not out of bounds) and store the number of entries
 818   //    you traversed as the number of members
 819
 820   unsigned long member_count = 0;
 821   unsigned int currentlevel=e->level;
 822   dwarf_entry* cur_entry = e;
 823   collection_type* collection_ptr = (collection_type*)(e->entry_ptr);
 824
 825   // If you are at the end of the array, you're screwed anyways
 826   if(dist_to_end == 0)
 827     return;
 828
 829   switch (e->tag_name)
 830     {
 831       // enumerations expect DW_TAG_enumerator as members
 832     case DW_TAG_enumeration_type:
 833       cur_entry++; // Move to the next entry - safe since dist_to_end > 0 by this point
 834       while ((member_count < dist_to_end) // put this first! short-circuit eval.
 835              && cur_entry->level> currentlevel)
 836         {
 837           if (cur_entry->tag_name==DW_TAG_enumerator&&(cur_entry->level==(currentlevel+1)))
 838             member_count++;
 839           cur_entry++;
 840         }
 841       break;
 842       // structs and unions expect DW_TAG_member as members
 843     case DW_TAG_structure_type:
 844     case DW_TAG_union_type:
 845       cur_entry++; // Move to the next entry - safe since dist_to_end > 0 by this point
 846       while ((member_count < dist_to_end) // put this first! short-circuit eval.
 847              && cur_entry->level>currentlevel)
 848         {
 849           if (cur_entry->tag_name==DW_TAG_member&&cur_entry->level==(currentlevel+1))
 850             member_count++;
 851           cur_entry++;
 852         }
 853       break;
 854     default:
 855       return;
 856     }
 857
 858   collection_ptr->num_members = member_count;
 859   collection_ptr->members = (dwarf_entry **)calloc(1,member_count*sizeof(dwarf_entry *));
 860
 861   cur_entry = e;
 862   member_count=0;
 863   switch (e->tag_name)
 864     {
 865       // enumerations expect DW_TAG_enumerator as members
 866     case DW_TAG_enumeration_type:
 867       cur_entry++; // Move to the next entry - safe since dist_to_end > 0 by this point
 868       while ((member_count < dist_to_end) // put this first! short-circuit eval.
 869              && cur_entry->level> currentlevel)
 870         {
 871           if (cur_entry->tag_name==DW_TAG_enumerator&&(cur_entry->level==(currentlevel+1)))
 872             collection_ptr->members[member_count++]=cur_entry;
 873           cur_entry++;
 874         }
 875       break;
 876       // structs and unions expect DW_TAG_member as members
 877     case DW_TAG_structure_type:
 878     case DW_TAG_union_type:
 879       cur_entry++; // Move to the next entry - safe since dist_to_end > 0 by this point
 880       while ((member_count < dist_to_end) // put this first! short-circuit eval.
 881              && cur_entry->level>currentlevel)
 882         {
 883           if (cur_entry->tag_name==DW_TAG_member&&cur_entry->level==(currentlevel+1))
 884             collection_ptr->members[member_count++]=cur_entry;
 885           cur_entry++;
 886         }
 887       break;
 888     default:
 889       return;
 890     }
 891 }
 892
 893 // Same as above except linking functions with formal parameters
 894 void link_function_to_params(dwarf_entry* e, unsigned long dist_to_end)
 895 {
 896   unsigned long param_count = 0;
 897   dwarf_entry* cur_entry = e;
 898   function* function_ptr = (function*)(e->entry_ptr);
 899
 900   // If you are at the end of the array, you're screwed anyways
 901   if(dist_to_end == 0)
 902     return;
 903
 904   cur_entry++; // Move to the next entry - safe since dist_to_end > 0 by this point
 905   // functions expect DW_TAG_formal_parameter as parameters
 906   while ((param_count < dist_to_end) // important that this is first! short-circuit eval.
 907          && cur_entry->tag_name == DW_TAG_formal_parameter)
 908     {
 909       param_count++;
 910       cur_entry++;
 911     }
 912
 913   function_ptr->num_formal_params = param_count;
 914   function_ptr->params = (e + 1);
 915 }
 916
 917 /*
 918 Requires: dwarf_entry_array is initialized
 919 Modifies: ((function*)cur_entry->entry_ptr)->filename for function entries
 920 Returns:
 921 Effects: Initialize the filename field of each function entry
 922          by linearly traversing dwarf_entry_array and noting that every compile_unit
 923          entry describes a file and all functions to the right of that entry
 924          (but to the left of the next entry) belong to that file
 925          e.g. [compile_unit foo.c][...][func1][...][func2][...][compile_unit bar.c][func3]
 926          func1 and func2 belong to foo.c and func3 belongs to bar.c
 927 */
 928 void initialize_function_filenames()
 929 {
 930   unsigned long idx;
 931   char* cur_file = 0;
 932   dwarf_entry* cur_entry = 0;
 933
 934   for (idx = 0; idx < dwarf_entry_array_size; idx++)
 935     {
 936       cur_entry = &dwarf_entry_array[idx];
 937
 938       if (tag_is_compile_unit(cur_entry->tag_name))
 939         cur_file = ((compile_unit*)cur_entry->entry_ptr)->filename;
 940       else if (tag_is_function(cur_entry->tag_name))
 941         ((function*)cur_entry->entry_ptr)->filename = cur_file;
 942     }
 943 }
 944
 945 /*
 946 Requires: dwarf_entry_array is initialized
 947 Modifies: function and collection entries within dwarf_entry_array
 948 Returns:
 949 Effects: Links function and collections entries to their respective members
 950          e.g. functions need to have a list of their formal parameters
 951          while structs, unions, and enumeration types need to have lists of members
 952          THIS ALGORITHM EXPLOITS THE FACT THAT MEMBERS/PARAMETERS ARE LISTED
 953          RIGHT AFTER THE RESPECTIVE FUNCTION OR STRUCT
 954          e.g. [function][param1][param2][param3][something_else]
 955 */
 956 void link_array_entries_to_members()
 957 {
 958   unsigned long idx;
 959   dwarf_entry* cur_entry = 0;
 960
 961   // Linearly traverse the array and pick off function or collections
 962   // (struct, union, enumeration) entries to link to members:
 963   for (idx = 0; idx < dwarf_entry_array_size; idx++)
 964     {
 965       cur_entry = &dwarf_entry_array[idx];
 966       if (tag_is_collection_type(cur_entry->tag_name))
 967         link_collection_to_members(cur_entry, dwarf_entry_array_size - idx - 1);
 968       else if (tag_is_function(cur_entry->tag_name))
 969         link_function_to_params(cur_entry, dwarf_entry_array_size - idx - 1);
 970     }
 971 }
 972
 973 // Prints the contents of the entry depending on its type
 974 void print_dwarf_entry(dwarf_entry* e)
 975 {
 976   if (e == 0)
 977     {
 978       printf("ERROR! Pointer e is null in print_dwarf_entry\n");
 979       return;
 980     }
 981
 982   printf("ID:0x%lx, TAG:%s\n", e->ID, get_TAG_name(e->tag_name));
 983
 984   switch(e->tag_name)
 985     {
 986     case DW_TAG_subprogram:
 987       {
 988         function* function_ptr = (function*)(e->entry_ptr);
 989         printf("  Name: %s, Filename: %s, Return Type ID (addr): 0x%lx (%p), Num. params: %ld, 1st param addr: %p\n",
 990                function_ptr->name,
 991                function_ptr->filename,
 992                function_ptr->return_type_ID,
 993                function_ptr->return_type,
 994                function_ptr->num_formal_params,
 995                function_ptr->params);
 996         break;
 997       }
 998     case DW_TAG_formal_parameter:
 999       {
1000         formal_parameter* formal_param_ptr = (formal_parameter*)(e->entry_ptr);
1001         printf("  Name: %s, Type ID (addr): 0x%lx (%p), Location: %ld\n",
1002                formal_param_ptr->name,
1003                formal_param_ptr->type_ID,
1004                formal_param_ptr->type_ptr,
1005                formal_param_ptr->location);
1006         break;
1007       }
1008     case DW_TAG_member:
1009       {
1010         member* member_ptr = (member*)(e->entry_ptr);
1011         printf("  Name: %s, Type ID (addr): 0x%lx (%p), Data member location: %ld, Byte size: %ld, Bit offset: %ld, Bit size: %ld\n",
1012                member_ptr->name,
1013                member_ptr->type_ID,
1014                member_ptr->type_ptr,
1015                member_ptr->data_member_location,
1016                member_ptr->byte_size,
1017                member_ptr->bit_offset,
1018                member_ptr->bit_size);
1019         break;
1020       }
1021     case DW_TAG_enumerator:
1022       {
1023         enumerator* enumerator_ptr = (enumerator*)(e->entry_ptr);
1024         printf("  Name: %s, Const value: %ld\n",
1025                enumerator_ptr->name,
1026                enumerator_ptr->const_value);
1027         break;
1028       }
1029
1030     case DW_TAG_structure_type:
1031     case DW_TAG_union_type:
1032     case DW_TAG_enumeration_type:
1033       {
1034         collection_type* collection_ptr = (collection_type*)(e->entry_ptr);
1035         printf("  Name: %s, Byte size: %ld, Num. members: %ld, 1st member addr: %p\n",
1036                collection_ptr->name,
1037                collection_ptr->byte_size,
1038                collection_ptr->num_members,
1039                collection_ptr->members);
1040         break;
1041       }
1042
1043     case DW_TAG_base_type:
1044       {
1045         base_type* base_ptr = (base_type*)(e->entry_ptr);
1046         printf("  Byte size: %ld, Encoding: %ld ",
1047                base_ptr->byte_size,
1048                base_ptr->encoding);
1049
1050         // More detailed encoding information
1051         switch (base_ptr->encoding)
1052           {
1053           case DW_ATE_void:             printf ("(void)"); break;
1054           case DW_ATE_address:          printf ("(machine address)"); break;
1055           case DW_ATE_boolean:          printf ("(boolean)"); break;
1056           case DW_ATE_complex_float:    printf ("(complex float)"); break;
1057           case DW_ATE_float:            printf ("(float)"); break;
1058           case DW_ATE_signed:           printf ("(signed)"); break;
1059           case DW_ATE_signed_char:      printf ("(signed char)"); break;
1060           case DW_ATE_unsigned:         printf ("(unsigned)"); break;
1061           case DW_ATE_unsigned_char:    printf ("(unsigned char)"); break;
1062             /* DWARF 2.1 value.  */
1063           case DW_ATE_imaginary_float:  printf ("(imaginary float)"); break;
1064           default:
1065             if (base_ptr->encoding >= DW_ATE_lo_user
1066                 && base_ptr->encoding <= DW_ATE_hi_user)
1067               {
1068                 printf ("(user defined type)");
1069               }
1070             else
1071               {
1072                 printf ("(unknown type)");
1073               }
1074             break;
1075           }
1076
1077         printf(", Bit size: %ld, Bit offset: %ld\n",
1078                base_ptr->bit_size,
1079                base_ptr->bit_offset);
1080
1081         break;
1082       }
1083     case DW_TAG_const_type:
1084     case DW_TAG_pointer_type:
1085     case DW_TAG_array_type:
1086     case DW_TAG_volatile_type:
1087       {
1088         modifier_type* modifier_ptr = (modifier_type*)(e->entry_ptr);
1089         printf("  Target ID (addr): 0x%lx (%p)\n",
1090                modifier_ptr->target_ID,
1091                modifier_ptr->target_ptr);
1092         break;
1093       }
1094
1095     case DW_TAG_compile_unit:
1096       {
1097         compile_unit* compile_ptr = (compile_unit*)(e->entry_ptr);
1098         printf("  Filename: %s, Compile dir: %s\n",
1099                compile_ptr->filename,
1100                compile_ptr->comp_dir);
1101       }
1102
1103     case DW_TAG_subroutine_type:
1104       {
1105         function_type * func_type = (function_type *)(e->entry_ptr);
1106         printf("  Return type ID (addr): 0x%lx (%p)\n",
1107                func_type->return_type_ID, func_type->return_type);
1108       }
1109
1110     default:
1111       return;
1112     }
1113 }
1114
1115 /*
1116 Requires:
1117 Modifies: dwarf_entry_array (initializes and blanks all entries to zero)
1118 Returns:
1119 Effects: Initializes sets up dwarf_entry_array to hold num_entries components
1120 */
1121 void initialize_dwarf_entry_array(unsigned long num_entries)
1122 {
1123   // use calloc to blank everything upon initialization
1124   dwarf_entry_array = calloc(num_entries, sizeof *dwarf_entry_array);
1125 }
1126
1127 /*
1128 Requires: dwarf_entry_array is initialized
1129 Modifies: dwarf_entry_array (free and set to 0)
1130 Returns:
1131 Effects: Destroys dwarf_entry_array and all entry_ptr fields of all entries
1132 */
1133 void destroy_dwarf_entry_array()
1134 {
1135   // Traverse the array and free the entry_ptr of all entries within array
1136
1137   unsigned long i;
1138   for (i = 0; i < dwarf_entry_array_size; i++)
1139     {
1140       free(dwarf_entry_array[i].entry_ptr);
1141     }
1142
1143   // Free the array itself
1144   free(dwarf_entry_array);
1145 }
1146
1147 void print_dwarf_entry_array()
1148 {
1149   unsigned long i;
1150   printf("--- BEGIN DWARF ENTRY ARRAY - size: %ld\n", dwarf_entry_array_size);
1151   for (i = 0; i < dwarf_entry_array_size; i++)
1152     {
1153       printf("array[%ld] (%p): ", i, dwarf_entry_array + i);
1154       print_dwarf_entry(&dwarf_entry_array[i]);
1155     }
1156   printf("--- END DWARF ENTRY ARRAY\n");
1157 }
1158
1159 /*
1160 Requires: e is initialized and has a e->tag_name
1161 Modifies: e->entry_ptr (initializes and set to 0)
1162 Returns:
1163 Effects: Initialize the value of e->entry_ptr to the appropriate sub-type
1164          based on the value of tag_name
1165          If tag_name is 0, then don't do anything
1166 */
1167 void initialize_dwarf_entry_ptr(dwarf_entry* e)
1168 {
1169   if (e->tag_name)
1170     {
1171       if (tag_is_base_type(e->tag_name))
1172         {
1173           e->entry_ptr = calloc(1, sizeof(base_type));
1174         }
1175       else if (e->tag_name==DW_TAG_subrange_type) {
1176         e->entry_ptr=calloc(1,sizeof(array_bound));
1177       }
1178       else if (tag_is_modifier_type(e->tag_name))
1179         {
1180           e->entry_ptr = calloc(1, sizeof(modifier_type));
1181         }
1182       else if (tag_is_collection_type(e->tag_name))
1183         {
1184           e->entry_ptr = calloc(1, sizeof(collection_type));
1185         }
1186       else if (tag_is_member(e->tag_name))
1187         {
1188           e->entry_ptr = calloc(1, sizeof(member));
1189         }
1190       else if (tag_is_enumerator(e->tag_name))
1191         {
1192           e->entry_ptr = calloc(1, sizeof(enumerator));
1193         }
1194       else if (tag_is_function(e->tag_name))
1195         {
1196           e->entry_ptr = calloc(1, sizeof(function));
1197         }
1198       else if (tag_is_formal_parameter(e->tag_name))
1199         {
1200           e->entry_ptr = calloc(1, sizeof(formal_parameter));
1201         }
1202       else if (tag_is_compile_unit(e->tag_name))
1203         {
1204           e->entry_ptr = calloc(1, sizeof(compile_unit));
1205         }
1206       else if (tag_is_function_type(e->tag_name))
1207         {
1208           e->entry_ptr = calloc(1, sizeof(function_type));
1209         }
1210     }
1211 }
1212
1213 // Now that dwarf_entry_array is initialized with values, we must link
1214 // the entries together in a coherent manner
1215 void finish_dwarf_entry_array_init(void)
1216 {
1217   // These must be done in this order or else things will go screwy!!!
1218   link_array_entries_to_members();
1219   initialize_function_filenames();
1220   link_entries_to_type_entries();
1221 }