From: bdemsky <bdemsky>
Date: Tue, 13 Jul 2004 05:02:25 +0000 (+0000)
Subject: improved structure layout generation
X-Git-Url: http://plrg.eecs.uci.edu/git/?p=repair.git;a=commitdiff_plain;h=644e30039caa4b85d95cc3e6ce6e85158f33bf44

improved structure layout generation
---

diff --git a/Repair/RepairCompiler/structextract/GenericHashtable.c b/Repair/RepairCompiler/structextract/GenericHashtable.c
new file mode 100755
index 0000000..c7569ba
--- /dev/null
+++ b/Repair/RepairCompiler/structextract/GenericHashtable.c
@@ -0,0 +1,201 @@
+#include <stdio.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <stdlib.h>
+#include <values.h>
+#include "GenericHashtable.h"
+//#include "dmalloc.h"
+
+int genputtable(struct genhashtable *ht, void * key, void * object) {
+  unsigned int bin=genhashfunction(ht,key);
+  struct genpointerlist * newptrlist=(struct genpointerlist *) calloc(1,sizeof(struct genpointerlist));
+  newptrlist->src=key;
+  newptrlist->object=object;
+  newptrlist->next=ht->bins[bin];
+  newptrlist->inext=NULL;
+  /* maintain linked list of ht entries for iteration*/
+  if (ht->last==NULL) {
+    ht->last=newptrlist;
+    ht->list=newptrlist;
+    newptrlist->iprev=NULL;
+  } else {
+    ht->last->inext=newptrlist;
+    newptrlist->iprev=ht->last;
+    ht->last=newptrlist;
+  }
+  ht->bins[bin]=newptrlist;
+  ht->counter++;
+  if(ht->counter>ht->currentsize&&ht->currentsize!=MAXINT) {
+    /* Expand hashtable */
+    long newcurrentsize=(ht->currentsize<(MAXINT/2))?ht->currentsize*2:MAXINT;
+    long oldcurrentsize=ht->currentsize;
+    struct genpointerlist **newbins=(struct genpointerlist **) calloc(1,sizeof (struct genpointerlist *)*newcurrentsize);
+    struct genpointerlist **oldbins=ht->bins;
+    long j,i;
+    for(j=0;j<newcurrentsize;j++) newbins[j]=NULL;
+    ht->currentsize=newcurrentsize;
+    for(i=0;i<oldcurrentsize;i++) {
+      struct genpointerlist * tmpptr=oldbins[i];
+      while(tmpptr!=NULL) {
+        int hashcode=genhashfunction(ht, tmpptr->src);
+        struct genpointerlist *nextptr=tmpptr->next;
+        tmpptr->next=newbins[hashcode];
+        newbins[hashcode]=tmpptr;
+        tmpptr=nextptr;
+      }
+    }
+    ht->bins=newbins;
+    free(oldbins);
+  }
+  return 1;
+}
+
+int hashsize(struct genhashtable *ht) {
+  return ht->counter;
+}
+
+void * gengettable(struct genhashtable *ht, void * key) {
+  struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
+  while(ptr!=NULL) {
+    if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
+      return ptr->object;
+    ptr=ptr->next;
+  }
+  printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p\n",key);
+  return NULL;
+}
+
+void * getnext(struct genhashtable *ht, void * key) {
+  struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
+  while(ptr!=NULL) {
+    if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
+      if (ptr->inext!=NULL) {
+	return ptr->inext->src;
+      } else
+	return NULL;
+    ptr=ptr->next;
+  }
+  printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p...\n Likely concurrent removal--bad user!!!\n",key);
+  return NULL;
+}
+
+int gencontains(struct genhashtable *ht, void * key) {
+  struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
+  //printf("In gencontains2\n");fflush(NULL);
+  while(ptr!=NULL) {
+    if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key)))
+      return 1;
+    ptr=ptr->next;
+  }
+  return 0;
+}
+
+
+void genfreekey(struct genhashtable *ht, void * key) {
+  struct genpointerlist * ptr=ht->bins[genhashfunction(ht,key)];
+
+  if (((ht->comp_function==NULL)&&(ptr->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->src,key))) {
+    ht->bins[genhashfunction(ht,key)]=ptr->next;
+
+    if (ptr==ht->last)
+      ht->last=ptr->iprev;
+
+    if (ptr==ht->list)
+      ht->list=ptr->inext;
+
+    if (ptr->iprev!=NULL)
+      ptr->iprev->inext=ptr->inext;
+    if (ptr->inext!=NULL)
+      ptr->inext->iprev=ptr->iprev;
+    
+    free(ptr);
+    ht->counter--;
+    return;
+  }
+  while(ptr->next!=NULL) {
+    if (((ht->comp_function==NULL)&&(ptr->next->src==key))||((ht->comp_function!=NULL)&&(*ht->comp_function)(ptr->next->src,key))) {
+      struct genpointerlist *tmpptr=ptr->next;
+      ptr->next=tmpptr->next;
+      if (tmpptr==ht->list)
+	ht->list=tmpptr->inext;
+      if (tmpptr==ht->last)
+	ht->last=tmpptr->iprev;
+      if (tmpptr->iprev!=NULL)
+	tmpptr->iprev->inext=tmpptr->inext;
+      if (tmpptr->inext!=NULL)
+	tmpptr->inext->iprev=tmpptr->iprev;
+      free(tmpptr);
+      ht->counter--;
+      return;
+    }
+    ptr=ptr->next;
+  }
+  printf("XXXXXXXXX: COULDN'T FIND ENTRY FOR KEY %p\n",key);
+}
+
+unsigned int genhashfunction(struct genhashtable *ht, void * key) {
+  if (ht->hash_function==NULL)
+    return ((long unsigned int)key) % ht->currentsize;
+  else
+    return ((*ht->hash_function)(key)) % ht->currentsize;
+}
+
+struct genhashtable * genallocatehashtable(unsigned int (*hash_function)(void *),int (*comp_function)(void *, void *)) {
+  struct genhashtable *ght=(struct genhashtable *) calloc(1,sizeof(struct genhashtable));
+  struct genpointerlist **gpl=(struct genpointerlist **) calloc(1,sizeof(struct genpointerlist *)*geninitialnumbins);
+  int i;
+  for(i=0;i<geninitialnumbins;i++)
+    gpl[i]=NULL;
+  ght->hash_function=hash_function;
+  ght->comp_function=comp_function;
+  ght->currentsize=geninitialnumbins;
+  ght->bins=gpl;
+  ght->counter=0;
+  ght->list=NULL;
+  ght->last=NULL;
+  return ght;
+}
+
+void genfreehashtable(struct genhashtable * ht) {
+  int i;
+  for (i=0;i<ht->currentsize;i++) {
+    if (ht->bins[i]!=NULL) {
+      struct genpointerlist *genptr=ht->bins[i];
+      while(genptr!=NULL) {
+	struct genpointerlist *tmpptr=genptr->next;
+	free(genptr);
+	genptr=tmpptr;
+      }
+    }
+  }
+  free(ht->bins);
+  free(ht);
+}
+
+struct geniterator * gengetiterator(struct genhashtable *ht) {
+  struct geniterator *gi=(struct geniterator*)calloc(1,sizeof(struct geniterator));
+  gi->ptr=ht->list;
+  return gi;
+}
+
+void * gennext(struct geniterator *it) {
+  struct genpointerlist *curr=it->ptr;
+  if (curr==NULL)
+    return NULL;
+  if (it->finished&&(curr->inext==NULL))
+    return NULL;
+  if (it->finished) {
+    it->ptr=curr->inext;
+    return it->ptr->src;
+  }
+  if(curr->inext!=NULL)
+    it->ptr=curr->inext;
+  else
+    it->finished=1; /* change offsetting scheme */
+  return curr->src;
+}
+
+void genfreeiterator(struct geniterator *it) {
+  free(it);
+}
diff --git a/Repair/RepairCompiler/structextract/GenericHashtable.h b/Repair/RepairCompiler/structextract/GenericHashtable.h
new file mode 100755
index 0000000..eb7d984
--- /dev/null
+++ b/Repair/RepairCompiler/structextract/GenericHashtable.h
@@ -0,0 +1,51 @@
+// implements a generic hash table
+
+#ifndef GENHASHTABLE
+#define GENHASHTABLE
+#define geninitialnumbins 10
+#define bool int
+
+struct genhashtable {
+  unsigned int (*hash_function)(void *);
+  int (*comp_function)(void *,void *);
+  struct genpointerlist ** bins;
+  long counter;
+  int currentsize;
+  struct genpointerlist *list;
+  struct genpointerlist *last;
+};
+
+
+struct genpointerlist {
+  void * src;
+  void * object;
+  struct genpointerlist * next;
+
+  struct genpointerlist * inext;
+  struct genpointerlist * iprev;
+};
+
+
+struct geniterator {
+  struct genpointerlist * ptr;
+  bool finished;
+};
+
+struct genhashtable * genallocatehashtable(unsigned int (*hash_function)(void *),int (*comp_function)(void *,void *));
+void genfreehashtable(struct genhashtable * ht);
+
+void * getnext(struct genhashtable *,void *);
+int genputtable(struct genhashtable *, void *, void *);
+void * gengettable(struct genhashtable *, void *);
+int gencontains(struct genhashtable *, void *);
+unsigned int genhashfunction(struct genhashtable *,void *);
+
+int hashsize(struct genhashtable * ht);
+void genfreekey(struct genhashtable *ht, void *);
+struct geniterator * gengetiterator(struct genhashtable *ht);
+void * gennext(struct geniterator *it);
+void genfreeiterator(struct geniterator *it);
+#endif
+
+
+
diff --git a/Repair/RepairCompiler/structextract/build b/Repair/RepairCompiler/structextract/build
index 67ae82f..77358f5 100755
--- a/Repair/RepairCompiler/structextract/build
+++ b/Repair/RepairCompiler/structextract/build
@@ -2,4 +2,6 @@
 gcc -gdwarf-2 -c readelf.c -Iinclude
 gcc -gdwarf-2 -c unwind-ia64.c -Iinclude
 gcc -gdwarf-2 -c typedata.c -Iinclude
+gcc -gdwarf-2 -c GenericHashtable.c
+gcc -gdwarf-2 -c common.c
 gcc -gdwarf-2 dumpstructures.c *.o -Iinclude -o dumpstructures
\ No newline at end of file
diff --git a/Repair/RepairCompiler/structextract/common.c b/Repair/RepairCompiler/structextract/common.c
new file mode 100755
index 0000000..a047e8b
--- /dev/null
+++ b/Repair/RepairCompiler/structextract/common.c
@@ -0,0 +1,58 @@
+#include<string.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <stdlib.h>
+#include "common.h"
+
+char * copystr(const char *buf) {
+  int i;
+  if (buf==NULL)
+    return NULL;
+  for(i=0;;i++)
+    if (buf[i]==0) {
+      char *ptr=(char*)malloc(i+1);
+      memcpy(ptr,buf,i+1);
+      return ptr;
+    }
+}
+
+
+unsigned int hashstring(char *strptr) {
+  unsigned int hashcode=0;
+  int *intptr=(int *) strptr;
+  if(intptr==NULL)
+    return 0;
+  while(1) {
+    int copy1=*intptr;
+    if((copy1&0xFF000000)&&
+       (copy1&0xFF0000)&&
+       (copy1&0xFF00)&&
+       (copy1&0xFF)) {
+      hashcode^=*intptr;
+      intptr++;
+    } else {
+      if (!copy1&0xFF000000)
+	hashcode^=copy1&0xFF000000;
+      else if (!copy1&0xFF0000)
+	hashcode^=copy1&0xFF0000;
+      else if (!copy1&0xFF00)
+	hashcode^=copy1&0xFF00;
+      else if (!copy1&0xFF)
+	hashcode^=copy1&0xFF;
+      return hashcode;
+    }
+  }
+}
+
+int equivalentstrings(char *str1, char *str2) {
+  if ((str1!=NULL)&&(str2!=NULL)) {
+    if (strcmp(str1,str2)!=0)
+      return 0;
+    else
+      return 1;
+  } else if ((str1==NULL)&&(str2==NULL))
+    return 1;
+  else return 0;
+}
+
diff --git a/Repair/RepairCompiler/structextract/common.h b/Repair/RepairCompiler/structextract/common.h
new file mode 100755
index 0000000..e9b2034
--- /dev/null
+++ b/Repair/RepairCompiler/structextract/common.h
@@ -0,0 +1,7 @@
+#ifndef COMMON_H
+#define COMMON_H
+
+char * copystr(const char *buf);
+unsigned int hashstring(char *strptr);
+int equivalentstrings(char *str1, char *str2);
+#endif
diff --git a/Repair/RepairCompiler/structextract/dumpstructures.c b/Repair/RepairCompiler/structextract/dumpstructures.c
index c08eaef..2b51bdc 100755
--- a/Repair/RepairCompiler/structextract/dumpstructures.c
+++ b/Repair/RepairCompiler/structextract/dumpstructures.c
@@ -18,6 +18,8 @@
 #include "dumpstructures.h"
 #include "typedata.h"
 #include "elf/dwarf2.h"
+#include "common.h"
+#include "GenericHashtable.h"
 
 #define GETTYPE 1
 #define POSTNAME 2
@@ -40,15 +42,15 @@ void daikon_preprocess_entry_array()
 }
 
 int typecount=0;
-
+int assigntype=0;
 int entry_is_type(dwarf_entry *entry) {
   if (entry->tag_name==DW_TAG_structure_type||
       entry->tag_name==DW_TAG_union_type) {
     collection_type* collection_ptr = (collection_type*)(entry->entry_ptr);
-    if (collection_ptr->name==0) {
+    /*    if (collection_ptr->name==0&&assigntype) {
       collection_ptr->name=(char*)malloc(100);
       sprintf(collection_ptr->name,"TYPE%ld",typecount++);
-    }
+      }*/
     return 1;
   }
   return 0;
@@ -68,13 +70,52 @@ int entry_is_valid_function(dwarf_entry *entry) {
   return 0;
 }
 
-// Finds the number of function entries in the dwarf_entry_array
-// and creates the DaikonFunctionInfo array to match that size
+struct valuepair {
+  int index;
+  int value;
+};
 
 void initializeTypeArray()
 {
   int i;
   dwarf_entry * cur_entry;
+  struct genhashtable * ght=genallocatehashtable((unsigned int (*)(void *)) & hashstring,(int (*)(void *,void *)) &equivalentstrings);
+  
+  for (i = 0; i < dwarf_entry_array_size; i++)
+    {
+      cur_entry = &dwarf_entry_array[i];
+      if (entry_is_type(cur_entry))
+        {
+	  collection_type* collection_ptr = (collection_type*)(cur_entry->entry_ptr);
+	  int j=0;
+	  int offset=0;
+	  int value=0;
+	  for(j=0;j<collection_ptr->num_members;j++) {
+	    dwarf_entry *entry=collection_ptr->members[j];
+	    member * member_ptr=(member *)entry->entry_ptr;
+	    char *name=member_ptr->name;
+	    dwarf_entry *type=member_ptr->type_ptr;
+	    char *typestr=printname(type,GETTYPE);
+	    char *poststr=printname(type,POSTNAME);
+
+	    if (typestr!=NULL)
+	      value++;
+	  }
+	  if (collection_ptr->name!=NULL) {
+	    struct valuepair *vp=NULL;
+	    if (gencontains(ght,collection_ptr->name))
+	      vp=(struct valuepair *)gengettable(ght,collection_ptr->name);
+	    if (vp==NULL||vp->value<value) {
+	      vp=(struct valuepair*)calloc(1,sizeof(struct valuepair));
+	      vp->value=value;
+	      vp->index=i;
+	      genputtable(ght,collection_ptr->name,vp);
+	    }
+	  }
+        }
+    }
+
+  assigntype=1;
   for (i = 0; i < dwarf_entry_array_size; i++)
     {
       cur_entry = &dwarf_entry_array[i];
@@ -83,6 +124,13 @@ void initializeTypeArray()
 	  collection_type* collection_ptr = (collection_type*)(cur_entry->entry_ptr);
 	  int j=0;
 	  int offset=0;
+	  if (collection_ptr->name==NULL)
+	    continue;
+	  if (gencontains(ght,collection_ptr->name)) {
+	    struct valuepair *vp=(struct valuepair*)gengettable(ght,collection_ptr->name);
+	    if (vp->index!=i)
+	      continue;
+	  }
 	  printf("structure %s {\n",collection_ptr->name);
 	  
 	  for(j=0;j<collection_ptr->num_members;j++) {
@@ -157,6 +205,27 @@ char * printname(dwarf_entry * type,int op) {
     }
   }
     break;
+  case DW_TAG_const_type:
+    {
+      consttype * ctype_ptr=(consttype*)type->entry_ptr;
+      if (op==GETTYPE) {
+	char *typename=printname(ctype_ptr->target_ptr,op);
+	return typename;
+      }
+    }
+    break;
+  case DW_TAG_subroutine_type: {
+    return "void";
+  }
+  case DW_TAG_typedef: 
+    {
+      tdef * tdef_ptr=(tdef*)type->entry_ptr;
+      if (op==GETTYPE) {
+	char *typename=printname(tdef_ptr->target_ptr,op);
+	return typename;
+      }
+    }
+    break;
   case DW_TAG_base_type: {
     base_type *base=(base_type*)type->entry_ptr;
     if (op==GETTYPE)
@@ -190,9 +259,10 @@ char * printname(dwarf_entry * type,int op) {
     }
   }
     break;
+  case DW_TAG_union_type:
   case DW_TAG_structure_type: {
     collection_type *ctype=(collection_type*)type->entry_ptr;
-    if (op==GETTYPE&&ctype->name==NULL) {
+    if (op==GETTYPE&&ctype->name==NULL&&assigntype) {
       ctype->name=(char*)malloc(100);
       sprintf(ctype->name,"TYPE%ld",typecount++);
     }
@@ -201,8 +271,15 @@ char * printname(dwarf_entry * type,int op) {
   }
     break;
   default:
-    if (op==GETTYPE)
-      return "unknown";
+    if (op==GETTYPE) {
+      if (!assigntype)
+	return NULL;
+      else {
+	char * p=(char *)malloc(100);
+	sprintf(p,"0x%x",type->tag_name);
+	return p;
+      }
+    }
   }
   if (op==POSTNAME)
     return "";
diff --git a/Repair/RepairCompiler/structextract/typedata.c b/Repair/RepairCompiler/structextract/typedata.c
index 5601a3a..9491146 100755
--- a/Repair/RepairCompiler/structextract/typedata.c
+++ b/Repair/RepairCompiler/structextract/typedata.c
@@ -70,6 +70,7 @@ char tag_is_relevant_entry(unsigned long tag)
     case DW_TAG_structure_type:
     case DW_TAG_union_type:
     case DW_TAG_base_type:
+    case DW_TAG_typedef:
     case DW_TAG_const_type:
     case DW_TAG_enumerator:
     case DW_TAG_subprogram:
@@ -223,7 +224,9 @@ char entry_is_listening_for_attribute(dwarf_entry* e, unsigned long attr)
               tag_is_member(tag) ||
               tag_is_function(tag) ||
               tag_is_formal_parameter(tag) ||
-              tag_is_function_type(tag));
+              tag_is_function_type(tag)||
+	      tag==DW_TAG_typedef||
+	      tag==DW_TAG_const_type);
     case DW_AT_upper_bound:
       return (tag==DW_TAG_subrange_type);
     case DW_AT_encoding:
@@ -257,6 +260,12 @@ char harvest_type_value(dwarf_entry* e, unsigned long value)
   if (tag ==DW_TAG_subrange_type) {
     ((array_bound*)e->entry_ptr)->target_ID = value;
     return 1;
+  } else if (tag==DW_TAG_typedef) {
+    ((tdef*)e->entry_ptr)->target_ID = value;
+    return 1;
+  } else if (tag==DW_TAG_const_type) {
+    ((consttype*)e->entry_ptr)->target_ID = value;
+    return 1;
   } else if (tag_is_modifier_type(tag))
     {
       ((modifier_type*)e->entry_ptr)->target_ID = value;
@@ -731,6 +740,34 @@ void link_entries_to_type_entries()
               bound_ptr->target_ptr=&dwarf_entry_array[target_index];
             }
       }
+      else if (tag==DW_TAG_typedef) {
+          char success = 0;
+          unsigned long target_index = 0;
+          tdef* bound_ptr = (tdef*)(cur_entry->entry_ptr);
+          unsigned long target_ID = bound_ptr->target_ID;
+
+          // Use a binary search to try to find the index of the entry in the
+          // array with the corresponding target_ID
+          success = binary_search_dwarf_entry_array(target_ID, &target_index);
+          if (success)
+            {
+              bound_ptr->target_ptr=&dwarf_entry_array[target_index];
+            }
+      }
+      else if (tag==DW_TAG_const_type) {
+          char success = 0;
+          unsigned long target_index = 0;
+          consttype* bound_ptr = (consttype*)(cur_entry->entry_ptr);
+          unsigned long target_ID = bound_ptr->target_ID;
+
+          // Use a binary search to try to find the index of the entry in the
+          // array with the corresponding target_ID
+          success = binary_search_dwarf_entry_array(target_ID, &target_index);
+          if (success)
+            {
+              bound_ptr->target_ptr=&dwarf_entry_array[target_index];
+            }
+      }
       else if (tag_is_function(tag))
         {
           char success = 0;
@@ -1175,6 +1212,12 @@ void initialize_dwarf_entry_ptr(dwarf_entry* e)
       else if (e->tag_name==DW_TAG_subrange_type) {
 	e->entry_ptr=calloc(1,sizeof(array_bound));
       }
+      else if (e->tag_name==DW_TAG_typedef) {
+	e->entry_ptr=calloc(1,sizeof(tdef));
+      }
+      else if (e->tag_name==DW_TAG_const_type) {
+	e->entry_ptr=calloc(1,sizeof(consttype));
+      }
       else if (tag_is_modifier_type(e->tag_name))
         {
           e->entry_ptr = calloc(1, sizeof(modifier_type));
diff --git a/Repair/RepairCompiler/structextract/typedata.h b/Repair/RepairCompiler/structextract/typedata.h
index 053c549..76326c5 100755
--- a/Repair/RepairCompiler/structextract/typedata.h
+++ b/Repair/RepairCompiler/structextract/typedata.h
@@ -67,6 +67,18 @@ typedef struct
   dwarf_entry* target_ptr; // Type that this entry modifies (DW_AT_type)
 } array_bound;
 
+typedef struct
+{ 
+  unsigned long target_ID; // ID of the entry that contains the type that this modifies
+  dwarf_entry* target_ptr; // Type that this entry modifies (DW_AT_type)
+} tdef;
+
+typedef struct
+{ 
+  unsigned long target_ID; // ID of the entry that contains the type that this modifies
+  dwarf_entry* target_ptr; // Type that this entry modifies (DW_AT_type)
+} consttype;
+
 // collection_type = {structure_type, union_type, enumeration_type}
 typedef struct
 {