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