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