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.mask = (size << 1) -1;
  22   pflookup.numelements = 0; // Initial number of elements in the hash
  23   pflookup.loadfactor = loadfactor;
  24
  25   //Intiliaze and set prefetch table mutex attribute
  26   pthread_mutexattr_init(&pflookup.prefetchmutexattr);
  27   //NOTE:PTHREAD_MUTEX_RECURSIVE is currently inside a #if_def UNIX98 in the pthread.h file
  28   //Therefore use PTHREAD_MUTEX_RECURSIVE_NP instead
  29   pthread_mutexattr_settype(&pflookup.prefetchmutexattr, PTHREAD_MUTEX_RECURSIVE_NP);
  30
  31   //Initialize mutex var
  32   pthread_mutex_init(&pflookup.lock, &pflookup.prefetchmutexattr);
  33   //pthread_mutex_init(&pflookup.lock, NULL);
  34   pthread_cond_init(&pflookup.cond, NULL);
  35   return 0;
  36 }
  37
  38 //Assign keys to bins inside hash table
  39 unsigned int prehashFunction(unsigned int key) {
  40   return ( key & pflookup.mask) >> 1;
  41 }
  42
  43 //Store oids and their pointers into hash
  44 unsigned int prehashInsert(unsigned int key, void *val) {
  45   unsigned int newsize;
  46   int index;
  47   prehashlistnode_t *ptr, *node;
  48
  49   if(pflookup.numelements > (pflookup.loadfactor * pflookup.size)) {
  50     //Resize
  51     newsize = pflookup.size << 1;
  52     pthread_mutex_lock(&pflookup.lock);
  53     prehashResize(newsize);
  54     pthread_mutex_unlock(&pflookup.lock);
  55   }
  56
  57   ptr = pflookup.table;
  58   pflookup.numelements++;
  59
  60   pthread_mutex_lock(&pflookup.lock);
  61   index = prehashFunction(key);
  62   if(ptr[index].next == NULL && ptr[index].key == 0) {  // Insert at the first position in the hashtable
  63     ptr[index].key = key;
  64     ptr[index].val = val;
  65   } else {                      // Insert in the beginning of linked list
  66     if ((node = calloc(1, sizeof(prehashlistnode_t))) == NULL) {
  67       printf("Calloc error %s, %d\n", __FILE__, __LINE__);
  68       pthread_mutex_unlock(&pflookup.lock);
  69       return 1;
  70     }
  71     node->key = key;
  72     node->val = val ;
  73     node->next = ptr[index].next;
  74     ptr[index].next = node;
  75   }
  76   pthread_mutex_unlock(&pflookup.lock);
  77   return 0;
  78 }
  79
  80 // Search for an address for a given oid
  81 void *prehashSearch(unsigned int key) {
  82   int index;
  83   prehashlistnode_t *ptr, *node;
  84
  85   pthread_mutex_lock(&pflookup.lock);
  86   node = & pflookup.table[(key & pflookup.mask)>>1];
  87   do {
  88     if(node->key == key) {
  89       void * tmp=node->val;
  90       pthread_mutex_unlock(&pflookup.lock);
  91       return tmp;
  92     }
  93     node = node->next;
  94   } while (node!=NULL);
  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.mask = (newsize << 1) -1;
 152   pflookup.numelements = 0;
 153
 154   for(i = 0; i < oldsize; i++) {                        //Outer loop for each bin in hash table
 155     curr = &ptr[i];
 156     isfirst = 1;
 157     while (curr != NULL) {                      //Inner loop to go through linked lists
 158       if (curr->key == 0) {             //Exit inner loop if there the first element for a given bin/index is NULL
 159         break;                  //key = val =0 for element if not present within the hash table
 160       }
 161       next = curr->next;
 162       index = prehashFunction(curr->key);
 163       // Insert into the new table
 164       if(pflookup.table[index].next == NULL && pflookup.table[index].key == 0) {
 165         pflookup.table[index].key = curr->key;
 166         pflookup.table[index].val = curr->val;
 167         pflookup.numelements++;
 168       } else {
 169         if((newnode = calloc(1, sizeof(prehashlistnode_t))) == NULL) {
 170           printf("Calloc error %s, %d\n", __FILE__, __LINE__);
 171           return 1;
 172         }
 173         newnode->key = curr->key;
 174         newnode->val = curr->val;
 175         newnode->next = pflookup.table[index].next;
 176         pflookup.table[index].next = newnode;
 177         pflookup.numelements++;
 178       }
 179
 180       //free the linked list of prehashlistnode_t if not the first element in the hash table
 181       if (isfirst != 1) {
 182         free(curr);
 183       }
 184
 185       isfirst = 0;
 186       curr = next;
 187     }
 188   }
 189
 190   free(ptr);            //Free the memory of the old hash table
 191   return 0;
 192 }
 193
 194 //Note: This is based on the implementation of the inserting a key in the first position of the hashtable
 195 void prehashClear() {
 196 #ifdef CACHE
 197   int i, isFirstBin;
 198   prehashlistnode_t *ptr, *prev, *curr;
 199
 200   pthread_mutex_lock(&pflookup.lock);
 201   ptr = pflookup.table;
 202   for(i = 0; i < pflookup.size; i++) {
 203     prev = &ptr[i];
 204     isFirstBin = 1;
 205     while(prev->next != NULL) {
 206       isFirstBin = 0;
 207       curr = prev->next;
 208       prev->next = curr->next;
 209       free(curr);
 210     }
 211     if(isFirstBin == 1) {
 212       prev->key = 0;
 213       prev->next = NULL;
 214     }
 215   }
 216   {
 217     int stale;
 218     pthread_mutex_unlock(&pflookup.lock);
 219     pthread_mutex_lock(&prefetchcache_mutex);
 220     if (pNodeInfo.newstale==NULL) {
 221       //transfer the list wholesale;
 222       pNodeInfo.oldstale=pNodeInfo.oldptr;
 223       pNodeInfo.newstale=pNodeInfo.newptr;
 224     } else {
 225       //merge the two lists
 226       pNodeInfo.newstale->prev=pNodeInfo.oldptr;
 227       pNodeInfo.newstale=pNodeInfo.newptr;
 228     }
 229     stale=STALL_THRESHOLD-pNodeInfo.stale_count;
 230
 231     if (stale>0&&stale>pNodeInfo.stall)
 232       pNodeInfo.stall=stale;
 233
 234     pNodeInfo.stale_count+=pNodeInfo.os_count;
 235     pNodeInfo.oldptr=getObjStr(DEFAULT_OBJ_STORE_SIZE);
 236     pNodeInfo.newptr=pNodeInfo.oldptr;
 237     pNodeInfo.os_count=1;
 238     pthread_mutex_unlock(&prefetchcache_mutex);
 239   }
 240 #endif
 241 }
 242