runtime/libtrace/tracelib.c

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