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