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