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