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
  13   // Allocate space for the hash table
  14   if((nodes = calloc(size, sizeof(prehashlistnode_t))) == NULL) {
  15     printf("Calloc error %s %d\n", __FILE__, __LINE__);
  16     return 1;
  17   }
  18   pflookup.table = nodes;
  19   pflookup.size = size;
  20   pflookup.mask = (size << 1) -1;
  21   pflookup.numelements = 0; // Initial number of elements in the hash
  22   pflookup.loadfactor = loadfactor;
  23   pflookup.threshold=loadfactor*size;
  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 void prehashInsert(unsigned int key, void *val) {
  45   prehashlistnode_t *ptr,*node,*tmp;
  46   int index, isFound=0;
  47   if(key==0) {
  48     printf("Error: Trying to insert invalid key and value\n");
  49     return;
  50   }
  51   if(pflookup.numelements > (pflookup.threshold)) {
  52     //Resize
  53     unsigned int newsize = pflookup.size << 1;
  54     pthread_mutex_lock(&pflookup.lock);
  55     prehashResize(newsize);
  56     pthread_mutex_unlock(&pflookup.lock);
  57   }
  58
  59   ptr = &pflookup.table[(key & pflookup.mask)>>1];
  60   pthread_mutex_lock(&pflookup.lock);
  61   if((ptr->key==0) && (ptr->next== NULL)) { //Insert at the first bin of the table
  62     ptr->key = key;
  63     ptr->val = val;
  64     pflookup.numelements++;
  65   } else {
  66     tmp = ptr;
  67     while(tmp != NULL) {
  68       if(tmp->key == key) {
  69         isFound=1;
  70         tmp->val = val; //Replace value for an exsisting key
  71         pthread_mutex_unlock(&pflookup.lock);
  72         return;
  73       }
  74       tmp=tmp->next;
  75     }
  76     if(!isFound) { //Insert new key and value into the chain of linked list for the given bin
  77       node = calloc(1, sizeof(prehashlistnode_t));
  78       node->key = key;
  79       node->val = val;
  80       node->next = ptr->next;
  81       ptr->next=node;
  82       pflookup.numelements++;
  83     }
  84   }
  85   pthread_mutex_unlock(&pflookup.lock);
  86   return;
  87 }
  88
  89 /*
  90    void prehashInsert(unsigned int key, void *val) {
  91    prehashlistnode_t *ptr,*node;
  92    pthread_mutex_lock(&pflookup.lock);
  93
  94    if(pflookup.numelements > (pflookup.threshold)) {
  95     //Resize
  96     unsigned int newsize = pflookup.size << 1;
  97     prehashResize(newsize);
  98    }
  99
 100
 101    ptr = &pflookup.table[(key & pflookup.mask)>>1];
 102    pflookup.numelements++;
 103
 104    if(ptr->key==0) {
 105     ptr->key = key;
 106     ptr->val = val;
 107    } else {                      // Insert in the beginning of linked list
 108     node = calloc(1, sizeof(prehashlistnode_t));
 109     node->key = key;
 110     node->val = val ;
 111     node->next = ptr->next;
 112     ptr->next=node;
 113    }
 114    pthread_mutex_unlock(&pflookup.lock);
 115    }
 116  */
 117
 118 // Search for an address for a given oid
 119 INLINE void *prehashSearch(unsigned int key) {
 120   int index;
 121   prehashlistnode_t *ptr, *node;
 122
 123   pthread_mutex_lock(&pflookup.lock);
 124   node = &pflookup.table[(key & pflookup.mask)>>1];
 125   do {
 126     if(node->key == key) {
 127       void * tmp=node->val;
 128       pthread_mutex_unlock(&pflookup.lock);
 129       return tmp;
 130     }
 131     node = node->next;
 132   } while (node!=NULL);
 133   pthread_mutex_unlock(&pflookup.lock);
 134   return NULL;
 135 }
 136
 137 unsigned int prehashRemove(unsigned int key) {
 138   int index;
 139   prehashlistnode_t *curr, *prev;
 140   prehashlistnode_t *ptr, *node;
 141
 142   pthread_mutex_lock(&pflookup.lock);
 143   ptr = pflookup.table;
 144   index = prehashFunction(key);
 145   curr = &ptr[index];
 146
 147   for (; curr != NULL; curr = curr->next) {
 148     if (curr->key == key) {         // Find a match in the hash table
 149       pflookup.numelements--;  // Decrement the number of elements in the global hashtable
 150       if ((curr == &ptr[index]) && (curr->next == NULL)) {  // Delete the first item inside the hashtable with no linked list of prehashlistnode_t
 151         curr->key = 0;
 152         curr->val = NULL;
 153       } else if ((curr == &ptr[index]) && (curr->next != NULL)) { //Delete the first item with a linked list of prehashlistnode_t  connected
 154         curr->key = curr->next->key;
 155         curr->val = curr->next->val;
 156         node = curr->next;
 157         curr->next = curr->next->next;
 158         free(node);
 159       } else {                                          // Regular delete from linked listed
 160         prev->next = curr->next;
 161         free(curr);
 162       }
 163       pthread_mutex_unlock(&pflookup.lock);
 164       return 0;
 165     }
 166     prev = curr;
 167   }
 168   pthread_mutex_unlock(&pflookup.lock);
 169   return 1;
 170 }
 171
 172 unsigned int prehashResize(unsigned int newsize) {
 173   prehashlistnode_t *node, *ptr;  // curr and next keep track of the current and the next chashlistnodes in a linked list
 174   unsigned int oldsize;
 175   int i,index;
 176   unsigned int mask;
 177   ptr = pflookup.table;
 178   oldsize = pflookup.size;
 179
 180   if((node = calloc(newsize, sizeof(prehashlistnode_t))) == NULL) {
 181     printf("Calloc error %s %d\n", __FILE__, __LINE__);
 182     return 1;
 183   }
 184
 185   pflookup.table = node;                //Update the global hashtable upon resize()
 186   pflookup.size = newsize;
 187   pflookup.threshold=newsize*pflookup.loadfactor;
 188   mask=pflookup.mask = (newsize << 1) -1;
 189
 190   for(i = 0; i < oldsize; i++) {                        //Outer loop for each bin in hash table
 191     prehashlistnode_t * curr = &ptr[i];
 192     prehashlistnode_t *tmp, *next;
 193     int isfirst = 1;
 194     do {
 195       unsigned int key;
 196       if ((key=curr->key) == 0) {             //Exit inner loop if there the first element for a given bin/index is NULL
 197         break;                  //key = val =0 for element if not present within the hash table
 198       }
 199       next = curr->next;
 200       index = (key & mask)>>1;
 201       tmp=&pflookup.table[index];
 202       // Insert into the new table
 203       if(tmp->key==0) {
 204         tmp->key=curr->key;
 205         tmp->val=curr->val;
 206         if (!isfirst)
 207           free(curr);
 208       } /*
 209            NOTE:  Add this case if you change this...
 210            This case currently never happens because of the way things rehash....
 211            else if (isfirst) {
 212            prehashlistnode_t * newnode = calloc(1, sizeof(prehashlistnode_t));
 213            newnode->key = curr->key;
 214            newnode->val = curr->val;
 215            newnode->next = tmp->next;
 216            tmp->next=newnode;
 217            } */
 218       else {
 219         curr->next=tmp->next;
 220         tmp->next=curr;
 221       }
 222
 223       isfirst = 0;
 224       curr = next;
 225     } while(curr!=NULL);
 226   }
 227
 228   free(ptr);            //Free the memory of the old hash table
 229   return 0;
 230 }
 231
 232 //Note: This is based on the implementation of the inserting a key in the first position of the hashtable
 233 void prehashClear() {
 234 #ifdef CACHE
 235   int i, isFirstBin;
 236   prehashlistnode_t *ptr, *prev, *curr;
 237
 238   pthread_mutex_lock(&pflookup.lock);
 239   ptr = pflookup.table;
 240   for(i = 0; i < pflookup.size; i++) {
 241     prev = &ptr[i];
 242     isFirstBin = 1;
 243     while(prev->next != NULL) {
 244       isFirstBin = 0;
 245       curr = prev->next;
 246       prev->next = curr->next;
 247       free(curr);
 248     }
 249     if(isFirstBin == 1) {
 250       prev->key = 0;
 251       prev->next = NULL;
 252     }
 253   }
 254   {
 255     int stale;
 256     pthread_mutex_unlock(&pflookup.lock);
 257     pthread_mutex_lock(&prefetchcache_mutex);
 258     if (pNodeInfo.newstale==NULL) {
 259       //transfer the list wholesale;
 260       pNodeInfo.oldstale=pNodeInfo.oldptr;
 261       pNodeInfo.newstale=pNodeInfo.newptr;
 262     } else {
 263       //merge the two lists
 264       pNodeInfo.newstale->prev=pNodeInfo.oldptr;
 265       pNodeInfo.newstale=pNodeInfo.newptr;
 266     }
 267     stale=STALL_THRESHOLD-pNodeInfo.stale_count;
 268
 269     if (stale>0&&stale>pNodeInfo.stall)
 270       pNodeInfo.stall=stale;
 271
 272     pNodeInfo.stale_count+=pNodeInfo.os_count;
 273     pNodeInfo.oldptr=getObjStr(DEFAULT_OBJ_STORE_SIZE);
 274     pNodeInfo.newptr=pNodeInfo.oldptr;
 275     pNodeInfo.os_count=1;
 276     pthread_mutex_unlock(&prefetchcache_mutex);
 277   }
 278 #endif
 279 }
 280