runtime/libtrace/tracelib.c

   1 /*===-- tracelib.c - Runtime routines for tracing ---------------*- C++ -*-===*
   2  *
   3  * Runtime routines for supporting tracing of execution for code generated by
   4  * LLVM.
   5  *
   6  *===----------------------------------------------------------------------===*/
   7
   8 #include "tracelib.h"
   9 #include <assert.h>
  10 #include <stdlib.h>
  11 #include <stdio.h>
  12 #include <string.h>
  13 #include "Support/DataTypes.h"
  14
  15 /*===---------------------------------------------------------------------=====
  16  * HASH FUNCTIONS
  17  *===---------------------------------------------------------------------===*/
  18
  19 /* use #defines until we have inlining */
  20 typedef uintptr_t Index;                 /* type of keys, size for hash table */
  21 typedef uint32_t  Generic;               /* type of values stored in table */
  22
  23 /* Index IntegerHashFunc(const Generic value, const Index size) */
  24 #define IntegerHashFunc(value, size) \
  25   ( ((((Index) value) << 3) ^ (((Index) value) >> 3)) % size )
  26
  27 /* Index IntegerRehashFunc(const Generic oldHashValue, const Index size) */
  28 #define IntegerRehashFunc(oldHashValue, size) \
  29   ((Index) ((oldHashValue+16) % size)) /* 16 is relatively prime to a Mersenne prime! */
  30
  31 /* Index PointerHashFunc(const void* value, const Index size) */
  32 #define PointerHashFunc(value, size) \
  33   IntegerHashFunc((Index) value, size)
  34
  35 /* Index PointerRehashFunc(const void* value, const Index size) */
  36 #define PointerRehashFunc(value, size) \
  37   IntegerRehashFunc((Index) value, size)
  38
  39 /*===---------------------------------------------------------------------=====
  40  * POINTER-TO-GENERIC HASH TABLE.
  41  * These should be moved to a separate location: HashTable.[ch]
  42  *===---------------------------------------------------------------------===*/
  43
  44 typedef enum { FIND, ENTER } ACTION;
  45 typedef char FULLEMPTY;
  46 const FULLEMPTY EMPTY = '\0';
  47 const FULLEMPTY FULL  = '\1';
  48
  49 const uint MAX_NUM_PROBES = 4;
  50
  51 typedef struct PtrValueHashEntry_struct {
  52   void*   key;
  53   Generic value;
  54 } PtrValueHashEntry;
  55
  56 typedef struct PtrValueHashTable_struct {
  57   PtrValueHashEntry* table;
  58   FULLEMPTY* fullEmptyFlags;
  59   Index capacity;
  60   Index size;
  61 } PtrValueHashTable;
  62
  63
  64 extern Generic LookupOrInsertPtr(PtrValueHashTable* ptrTable,
  65                                  void* ptr, ACTION action);
  66
  67 extern void Insert(PtrValueHashTable* ptrTable, void* ptr, Generic value);
  68
  69 extern void Delete(PtrValueHashTable* ptrTable, void* ptr);
  70
  71 /* Returns NULL if the item is not found. */
  72 /* void* LookupPtr(PtrValueHashTable* ptrTable, void* ptr) */
  73 #define LookupPtr(ptrTable, ptr) \
  74   LookupOrInsertPtr(ptrTable, ptr, FIND)
  75
  76 void
  77 InitializeTable(PtrValueHashTable* ptrTable, Index newSize)
  78 {
  79   ptrTable->table = (PtrValueHashEntry*) calloc(newSize,
  80                                                 sizeof(PtrValueHashEntry));
  81   ptrTable->fullEmptyFlags = (FULLEMPTY*) calloc(newSize, sizeof(FULLEMPTY));
  82   ptrTable->capacity = newSize;
  83   ptrTable->size = 0;
  84 }
  85
  86 PtrValueHashTable*
  87 CreateTable(Index initialSize)
  88 {
  89   PtrValueHashTable* ptrTable =
  90     (PtrValueHashTable*) malloc(sizeof(PtrValueHashTable));
  91   InitializeTable(ptrTable, initialSize);
  92   return ptrTable;
  93 }
  94
  95 void
  96 ReallocTable(PtrValueHashTable* ptrTable, Index newSize)
  97 {
  98   if (newSize <= ptrTable->capacity)
  99     return;
 100
 101 #ifndef NDEBUG
 102   printf("\n***\n*** REALLOCATING SPACE FOR POINTER HASH TABLE.\n");
 103   printf("*** oldSize = %ld, oldCapacity = %ld\n***\n\n",
 104          (long) ptrTable->size, (long) ptrTable->capacity);
 105 #endif
 106
 107   unsigned int i;
 108   PtrValueHashEntry* oldTable = ptrTable->table;
 109   FULLEMPTY* oldFlags = ptrTable->fullEmptyFlags;
 110   Index oldSize = ptrTable->size;
 111   Index oldCapacity = ptrTable->capacity;
 112
 113   /* allocate the new storage and flags and re-insert the old entries */
 114   InitializeTable(ptrTable, newSize);
 115   for (i=0; i < oldCapacity; ++i)
 116     if (oldFlags[i] == FULL)
 117       Insert(ptrTable, oldTable[i].key, oldTable[i].value);
 118
 119   assert(ptrTable->size == oldSize && "Incorrect number of entries copied?");
 120
 121 #ifndef NDEBUG
 122   for (i=0; i < oldCapacity; ++i)
 123     if (! oldFlags[i])
 124       assert(LookupPtr(ptrTable, oldTable[i].key) == oldTable[i].value);
 125 #endif
 126
 127   free(oldTable);
 128   free(oldFlags);
 129 }
 130
 131 void
 132 DeleteTable(PtrValueHashTable* ptrTable)
 133 {
 134   free(ptrTable->table);
 135   free(ptrTable->fullEmptyFlags);
 136   memset(ptrTable, '\0', sizeof(PtrValueHashTable));
 137   free(ptrTable);
 138 }
 139
 140 void
 141 InsertAtIndex(PtrValueHashTable* ptrTable, void* ptr, Generic value, Index index)
 142 {
 143   assert(ptrTable->fullEmptyFlags[index] == EMPTY && "Slot is in use!");
 144   ptrTable->table[index].key = ptr;
 145   ptrTable->table[index].value = value;
 146   ptrTable->fullEmptyFlags[index] = FULL;
 147   ptrTable->size++;
 148 }
 149
 150 void
 151 DeleteAtIndex(PtrValueHashTable* ptrTable, Index index)
 152 {
 153   assert(ptrTable->fullEmptyFlags[index] == FULL && "Deleting empty slot!");
 154   ptrTable->table[index].key = NULL;
 155   ptrTable->table[index].value = (Generic) NULL;
 156   ptrTable->fullEmptyFlags[index] = EMPTY;
 157   ptrTable->size--;
 158 }
 159
 160 Index
 161 FindIndex(PtrValueHashTable* ptrTable, void* ptr)
 162 {
 163   uint numProbes = 1;
 164   Index index = PointerHashFunc(ptr, ptrTable->capacity);
 165   if (ptrTable->fullEmptyFlags[index] == FULL)
 166     {
 167       if (ptrTable->table[index].key == ptr)
 168         return index;
 169
 170       /* First lookup failed on non-empty slot: probe further */
 171       while (numProbes < MAX_NUM_PROBES)
 172         {
 173           index = PointerRehashFunc(index, ptrTable->capacity);
 174           if (ptrTable->fullEmptyFlags[index] == EMPTY)
 175             break;
 176           else if (ptrTable->table[index].key == ptr)
 177             return index;
 178           ++numProbes;
 179         }
 180     }
 181
 182   /* Lookup failed: item is not in the table. */
 183   /* If last slot is empty, use that slot. */
 184   /* Otherwise, table must have been reallocated, so search again. */
 185
 186   if (numProbes == MAX_NUM_PROBES)
 187     { /* table is too full: reallocate and search again */
 188       ReallocTable(ptrTable, 1 + 2*ptrTable->capacity);
 189       return FindIndex(ptrTable, ptr);
 190     }
 191   else
 192     {
 193       assert(ptrTable->fullEmptyFlags[index] == EMPTY &&
 194              "Stopped before finding an empty slot and before MAX probes!");
 195       return index;
 196     }
 197 }
 198
 199 Generic
 200 LookupOrInsertPtr(PtrValueHashTable* ptrTable, void* ptr, ACTION action)
 201 {
 202   Index index = FindIndex(ptrTable, ptr);
 203   if (ptrTable->fullEmptyFlags[index] == FULL &&
 204       ptrTable->table[index].key == ptr)
 205     return ptrTable->table[index].value;
 206
 207   /* Lookup failed: item is not in the table */
 208   if (action != ENTER)
 209     return (Generic) NULL;
 210
 211   /* Insert item into the table and return its index */
 212   InsertAtIndex(ptrTable, ptr, (Generic) NULL, index);
 213   return (Generic) NULL;
 214 }
 215
 216 void
 217 Insert(PtrValueHashTable* ptrTable, void* ptr, Generic value)
 218 {
 219   Index index = FindIndex(ptrTable, ptr);
 220   assert(ptrTable->fullEmptyFlags[index] == EMPTY &&
 221          "ptr is already in the table: delete it first!");
 222   InsertAtIndex(ptrTable, ptr, value, index);
 223 }
 224
 225 void
 226 Delete(PtrValueHashTable* ptrTable, void* ptr)
 227 {
 228   Index index = FindIndex(ptrTable, ptr);
 229   if (ptrTable->fullEmptyFlags[index] == FULL &&
 230       ptrTable->table[index].key == ptr)
 231     {
 232       DeleteAtIndex(ptrTable, index);
 233     }
 234 }
 235
 236 /*===---------------------------------------------------------------------=====
 237  * RUNTIME ROUTINES TO MAP POINTERS TO SEQUENCE NUMBERS
 238  *===---------------------------------------------------------------------===*/
 239
 240 PtrValueHashTable* SequenceNumberTable = NULL;
 241 Index INITIAL_SIZE = 1 << 22;
 242
 243 #define MAX_NUM_SAVED 1024
 244
 245 typedef struct PointerSet_struct {
 246   char* savedPointers[MAX_NUM_SAVED];   /* 1024 alloca'd ptrs shd suffice */
 247   unsigned int numSaved;
 248   struct PointerSet_struct* nextOnStack;     /* implement a cheap stack */
 249 } PointerSet;
 250
 251 PointerSet* topOfStack = NULL;
 252
 253 SequenceNumber
 254 HashPointerToSeqNum(char* ptr)
 255 {
 256   static SequenceNumber count = 0;
 257   SequenceNumber seqnum;
 258   if (SequenceNumberTable == NULL) {
 259     assert(MAX_NUM_PROBES < INITIAL_SIZE+1 && "Initial size too small");
 260     SequenceNumberTable = CreateTable(INITIAL_SIZE);
 261   }
 262   seqnum = (SequenceNumber) LookupPtr(SequenceNumberTable, ptr);
 263   if (seqnum == 0)
 264     {
 265       Insert(SequenceNumberTable, ptr, ++count);
 266       seqnum = count;
 267     }
 268   return seqnum;
 269 }
 270
 271 void
 272 ReleasePointerSeqNum(char* ptr)
 273 { /* if a sequence number was assigned to this ptr, release it */
 274   if (SequenceNumberTable != NULL)
 275     Delete(SequenceNumberTable, ptr);
 276 }
 277
 278 void
 279 PushPointerSet()
 280 {
 281   PointerSet* newSet = (PointerSet*) malloc(sizeof(PointerSet));
 282   newSet->numSaved = 0;
 283   newSet->nextOnStack = topOfStack;
 284   topOfStack = newSet;
 285 }
 286
 287 void
 288 PopPointerSet()
 289 {
 290   PointerSet* oldSet;
 291   assert(topOfStack != NULL && "popping from empty stack!");
 292   oldSet = topOfStack;
 293   topOfStack = oldSet->nextOnStack;
 294   assert(oldSet->numSaved == 0);
 295   free(oldSet);
 296 }
 297
 298 /* free the pointers! */
 299 static void
 300 ReleaseRecordedPointers(char* savedPointers[MAX_NUM_SAVED],
 301                         unsigned int numSaved)
 302 {
 303   unsigned int i;
 304   for (i=0; i < topOfStack->numSaved; ++i)
 305     ReleasePointerSeqNum(topOfStack->savedPointers[i]);
 306 }
 307
 308 void
 309 ReleasePointersPopSet()
 310 {
 311   ReleaseRecordedPointers(topOfStack->savedPointers, topOfStack->numSaved);
 312   topOfStack->numSaved = 0;
 313   PopPointerSet();
 314 }
 315
 316 void
 317 RecordPointer(char* ptr)
 318 { /* record pointers for release later */
 319   if (topOfStack->numSaved == MAX_NUM_SAVED) {
 320     printf("***\n*** WARNING: OUT OF ROOM FOR SAVED POINTERS."
 321            " ALL POINTERS ARE BEING FREED.\n"
 322            "*** THE SEQUENCE NUMBERS OF SAVED POINTERS WILL CHANGE!\n*** \n");
 323     ReleaseRecordedPointers(topOfStack->savedPointers, topOfStack->numSaved);
 324     topOfStack->numSaved = 0;
 325   }
 326   topOfStack->savedPointers[topOfStack->numSaved++] = ptr;
 327 }
 328
 329 /*===---------------------------------------------------------------------=====
 330  * TEST DRIVER FOR INSTRUMENTATION LIBRARY
 331  *===---------------------------------------------------------------------===*/
 332
 333 #ifndef TEST_INSTRLIB
 334 #undef  TEST_INSTRLIB /* #define this to turn on by default */
 335 #endif
 336
 337 #ifdef TEST_INSTRLIB
 338 int
 339 main(int argc, char** argv)
 340 {
 341   int i, j;
 342   int doRelease = 0;
 343
 344   INITIAL_SIZE = 5; /* start with small table to test realloc's*/
 345
 346   if (argc > 1 && ! strcmp(argv[1], "-r"))
 347     {
 348       PushPointerSet();
 349       doRelease = 1;
 350     }
 351
 352   for (i=0; i < argc; ++i)
 353     for (j=0; argv[i][j]; ++j)
 354       {
 355         printf("Sequence number for argc[%d][%d] (%c) = Hash(%p) = %d\n",
 356                i, j, argv[i][j], argv[i]+j, HashPointerToSeqNum(argv[i]+j));
 357
 358         if (doRelease)
 359           RecordPointer(argv[i]+j);
 360       }
 361
 362   if (doRelease)
 363     ReleasePointersPopSet();
 364
 365   /* print sequence numbers out again to compare with (-r) and w/o release */
 366   for (i=argc-1; i >= 0; --i)
 367     for (j=0; argv[i][j]; ++j)
 368       printf("Sequence number for argc[%d][%d] (%c) = %d\n",
 369              i, j, argv[i][j], argv[i]+j, HashPointerToSeqNum(argv[i]+j));
 370
 371   return 0;
 372 }
 373 #endif