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