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