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