Robust/src/Runtime/DSTM/interface/prelookup.c

   1 /* LOCK THE ENTIRE HASH TABLE */
   2 #include "prelookup.h"
   3 #include "gCollect.h"
   4 extern objstr_t *prefetchcache;
   5 extern pthread_mutex_t prefetchcache_mutex; //Mutex to lock Prefetch Cache
   6 extern prefetchNodeInfo_t pNodeInfo;
   7
   8 prehashtable_t pflookup; //Global prefetch cache table
   9
  10 unsigned int prehashCreate(unsigned int size, float loadfactor) {
  11   prehashlistnode_t *nodes;
  12   int i;
  13
  14   // Allocate space for the hash table
  15   if((nodes = calloc(size, sizeof(prehashlistnode_t))) == NULL) {
  16     printf("Calloc error %s %d\n", __FILE__, __LINE__);
  17     return 1;
  18   }
  19   pflookup.table = nodes;
  20   pflookup.size = size;
  21   pflookup.numelements = 0; // Initial number of elements in the hash
  22   pflookup.loadfactor = loadfactor;
  23
  24   //Intiliaze and set prefetch table mutex attribute
  25   pthread_mutexattr_init(&pflookup.prefetchmutexattr);
  26   //NOTE:PTHREAD_MUTEX_RECURSIVE is currently inside a #if_def UNIX98 in the pthread.h file
  27   //Therefore use PTHREAD_MUTEX_RECURSIVE_NP instead
  28   pthread_mutexattr_settype(&pflookup.prefetchmutexattr, PTHREAD_MUTEX_RECURSIVE_NP);
  29
  30   //Initialize mutex var
  31   pthread_mutex_init(&pflookup.lock, &pflookup.prefetchmutexattr);
  32   //pthread_mutex_init(&pflookup.lock, NULL);
  33   pthread_cond_init(&pflookup.cond, NULL);
  34   return 0;
  35 }
  36
  37 //Assign keys to bins inside hash table
  38 unsigned int prehashFunction(unsigned int key) {
  39   return ( key % (pflookup.size));
  40 }
  41
  42 //Store oids and their pointers into hash
  43 unsigned int prehashInsert(unsigned int key, void *val) {
  44   unsigned int newsize;
  45   int index;
  46   prehashlistnode_t *ptr, *node;
  47
  48   if(pflookup.numelements > (pflookup.loadfactor * pflookup.size)) {
  49     //Resize
  50     newsize = 2 * pflookup.size + 1;
  51     pthread_mutex_lock(&pflookup.lock);
  52     prehashResize(newsize);
  53     pthread_mutex_unlock(&pflookup.lock);
  54   }
  55
  56   ptr = pflookup.table;
  57   pflookup.numelements++;
  58
  59   pthread_mutex_lock(&pflookup.lock);
  60   index = prehashFunction(key);
  61   if(ptr[index].next == NULL && ptr[index].key == 0) {  // Insert at the first position in the hashtable
  62     ptr[index].key = key;
  63     ptr[index].val = val;
  64   } else {                      // Insert in the beginning of linked list
  65     if ((node = calloc(1, sizeof(prehashlistnode_t))) == NULL) {
  66       printf("Calloc error %s, %d\n", __FILE__, __LINE__);
  67       pthread_mutex_unlock(&pflookup.lock);
  68       return 1;
  69     }
  70     node->key = key;
  71     node->val = val ;
  72     node->next = ptr[index].next;
  73     ptr[index].next = node;
  74   }
  75   pthread_mutex_unlock(&pflookup.lock);
  76   return 0;
  77 }
  78
  79 // Search for an address for a given oid
  80 void *prehashSearch(unsigned int key) {
  81   int index;
  82   prehashlistnode_t *ptr, *node;
  83
  84   pthread_mutex_lock(&pflookup.lock);
  85   ptr = pflookup.table;
  86   index = prehashFunction(key);
  87   node = &ptr[index];
  88   while(node != NULL) {
  89     if(node->key == key) {
  90       pthread_mutex_unlock(&pflookup.lock);
  91       return node->val;
  92     }
  93     node = node->next;
  94   }
  95   pthread_mutex_unlock(&pflookup.lock);
  96   return NULL;
  97 }
  98
  99 unsigned int prehashRemove(unsigned int key) {
 100   int index;
 101   prehashlistnode_t *curr, *prev;
 102   prehashlistnode_t *ptr, *node;
 103
 104   pthread_mutex_lock(&pflookup.lock);
 105   ptr = pflookup.table;
 106   index = prehashFunction(key);
 107   curr = &ptr[index];
 108
 109   for (; curr != NULL; curr = curr->next) {
 110     if (curr->key == key) {         // Find a match in the hash table
 111       pflookup.numelements--;  // Decrement the number of elements in the global hashtable
 112       if ((curr == &ptr[index]) && (curr->next == NULL)) {  // Delete the first item inside the hashtable with no linked list of prehashlistnode_t
 113         curr->key = 0;
 114         curr->val = NULL;
 115       } else if ((curr == &ptr[index]) && (curr->next != NULL)) { //Delete the first item with a linked list of prehashlistnode_t  connected
 116         curr->key = curr->next->key;
 117         curr->val = curr->next->val;
 118         node = curr->next;
 119         curr->next = curr->next->next;
 120         free(node);
 121       } else {                                          // Regular delete from linked listed
 122         prev->next = curr->next;
 123         free(curr);
 124       }
 125       pthread_mutex_unlock(&pflookup.lock);
 126       return 0;
 127     }
 128     prev = curr;
 129   }
 130   pthread_mutex_unlock(&pflookup.lock);
 131   return 1;
 132 }
 133
 134 unsigned int prehashResize(unsigned int newsize) {
 135   prehashlistnode_t *node, *ptr, *curr, *next;  // curr and next keep track of the current and the next chashlistnodes in a linked list
 136   unsigned int oldsize;
 137   int isfirst;    // Keeps track of the first element in the prehashlistnode_t for each bin in hashtable
 138   int i,index;
 139   prehashlistnode_t *newnode;
 140
 141   ptr = pflookup.table;
 142   oldsize = pflookup.size;
 143
 144   if((node = calloc(newsize, sizeof(prehashlistnode_t))) == NULL) {
 145     printf("Calloc error %s %d\n", __FILE__, __LINE__);
 146     return 1;
 147   }
 148
 149   pflookup.table = node;                //Update the global hashtable upon resize()
 150   pflookup.size = newsize;
 151   pflookup.numelements = 0;
 152
 153   for(i = 0; i < oldsize; i++) {                        //Outer loop for each bin in hash table
 154     curr = &ptr[i];
 155     isfirst = 1;
 156     while (curr != NULL) {                      //Inner loop to go through linked lists
 157       if (curr->key == 0) {             //Exit inner loop if there the first element for a given bin/index is NULL
 158         break;                  //key = val =0 for element if not present within the hash table
 159       }
 160       next = curr->next;
 161       index = prehashFunction(curr->key);
 162       // Insert into the new table
 163       if(pflookup.table[index].next == NULL && pflookup.table[index].key == 0) {
 164         pflookup.table[index].key = curr->key;
 165         pflookup.table[index].val = curr->val;
 166         pflookup.numelements++;
 167       } else {
 168         if((newnode = calloc(1, sizeof(prehashlistnode_t))) == NULL) {
 169           printf("Calloc error %s, %d\n", __FILE__, __LINE__);
 170           return 1;
 171         }
 172         newnode->key = curr->key;
 173         newnode->val = curr->val;
 174         newnode->next = pflookup.table[index].next;
 175         pflookup.table[index].next = newnode;
 176         pflookup.numelements++;
 177       }
 178
 179       //free the linked list of prehashlistnode_t if not the first element in the hash table
 180       if (isfirst != 1) {
 181         free(curr);
 182       }
 183
 184       isfirst = 0;
 185       curr = next;
 186     }
 187   }
 188
 189   free(ptr);            //Free the memory of the old hash table
 190   return 0;
 191 }
 192
 193 //Note: This is based on the implementation of the inserting a key in the first position of the hashtable
 194 void prehashClear() {
 195 #ifdef CACHE
 196   int i, isFirstBin;
 197   prehashlistnode_t *ptr, *prev, *curr;
 198
 199   pthread_mutex_lock(&pflookup.lock);
 200   ptr = pflookup.table;
 201   for(i = 0; i < pflookup.size; i++) {
 202     prev = &ptr[i];
 203     isFirstBin = 1;
 204     while(prev->next != NULL) {
 205       isFirstBin = 0;
 206       curr = prev->next;
 207       prev->next = curr->next;
 208       free(curr);
 209     }
 210     if(isFirstBin == 1) {
 211       prev->key = 0;
 212       prev->next = NULL;
 213     }
 214   }
 215   {
 216     int stale;
 217     pthread_mutex_unlock(&pflookup.lock);
 218     pthread_mutex_lock(&prefetchcache_mutex);
 219     if (pNodeInfo.newstale==NULL) {
 220       //transfer the list wholesale;
 221       pNodeInfo.oldstale=pNodeInfo.oldptr;
 222       pNodeInfo.newstale=pNodeInfo.newptr;
 223     } else {
 224       //merge the two lists
 225       pNodeInfo.newstale->prev=pNodeInfo.oldptr;
 226       pNodeInfo.newstale=pNodeInfo.newptr;
 227     }
 228     stale=STALL_THRESHOLD-pNodeInfo.stale_count;
 229
 230     if (stale>0&&stale>pNodeInfo.stall)
 231       pNodeInfo.stall=stale;
 232
 233     pNodeInfo.stale_count+=pNodeInfo.os_count;
 234     pNodeInfo.oldptr=getObjStr(DEFAULT_OBJ_STORE_SIZE);
 235     pNodeInfo.newptr=pNodeInfo.oldptr;
 236     pNodeInfo.os_count=1;
 237     pthread_mutex_unlock(&prefetchcache_mutex);
 238   }
 239 #endif
 240 }
 241