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

   1 #include "altprelookup.h"
   2 #include "dsmlock.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;
  22   pflookup.numelements = 0; // Initial number of elements in the hash
  23   pflookup.loadfactor = loadfactor;
  24   pflookup.threshold=loadfactor*size;
  25
  26   //Initilize
  27   for(i=0;i<PRENUMLOCKS;i++){
  28     pflookup.larray[i].lock=RW_LOCK_BIAS;
  29   }
  30
  31   /*
  32   //Intiliaze and set prefetch table mutex attribute
  33   pthread_mutexattr_init(&pflookup.prefetchmutexattr);
  34   //NOTE:PTHREAD_MUTEX_RECURSIVE is currently inside a #if_def UNIX98 in the pthread.h file
  35   //Therefore use PTHREAD_MUTEX_RECURSIVE_NP instead
  36   pthread_mutexattr_settype(&pflookup.prefetchmutexattr, PTHREAD_MUTEX_RECURSIVE_NP);
  37
  38   //Initialize mutex var
  39   pthread_mutex_init(&pflookup.lock, &pflookup.prefetchmutexattr);
  40   //pthread_mutex_init(&pflookup.lock, NULL);
  41   pthread_cond_init(&pflookup.cond, NULL);
  42   */
  43
  44   return 0;
  45 }
  46
  47 //Assign keys to bins inside hash table
  48 unsigned int prehashFunction(unsigned int key) {
  49   return ( key & pflookup.mask) >> 1;
  50 }
  51
  52 //Store oids and their pointers into hash
  53 void prehashInsert(unsigned int key, void *val) {
  54
  55   int isFound=0;
  56   prehashlistnode_t *ptr, *tmp, *node;
  57
  58   if(pflookup.numelements > (pflookup.threshold)) {
  59     //Resize
  60     unsigned int newsize = pflookup.size << 1;
  61     prehashResize(newsize);
  62   }
  63
  64   unsigned int keyindex=key>>1;
  65   volatile unsigned int * lockptr=&pflookup.larray[keyindex&PRELOCKMASK].lock;
  66   while(!write_trylock(lockptr)) {
  67     sched_yield();
  68   }
  69
  70   ptr = &pflookup.table[keyindex&pflookup.mask];
  71
  72   if(ptr->key==0) { //Insert at the first bin of the table
  73     ptr->key = key;
  74     ptr->val = val;
  75     atomic_inc(&pflookup.numelements);
  76   } else {
  77     tmp = ptr;
  78     while(tmp != NULL) {
  79       if(tmp->key == key) {
  80         isFound=1;
  81         tmp->val = val;//Replace value for an exsisting key
  82         write_unlock(lockptr);
  83         return;
  84       }
  85       tmp=tmp->next;
  86     }
  87     if(!isFound) { //Insert new key and value into the chain of linked list for the given bin
  88       node = calloc(1, sizeof(prehashlistnode_t));
  89       node->key = key;
  90       node->val = val ;
  91       node->next = ptr->next;
  92       ptr->next=node;
  93       atomic_inc(&pflookup.numelements);
  94     }
  95   }
  96   write_unlock(lockptr);
  97   return;
  98 }
  99
 100 // Search for an address for a given oid
 101 void *prehashSearch(unsigned int key) {
 102   int index;
 103
 104   unsigned int keyindex=key>>1;
 105   volatile unsigned int * lockptr=&pflookup.larray[keyindex&PRELOCKMASK].lock;
 106   while(!read_trylock(lockptr)) {
 107     sched_yield();
 108   }
 109   prehashlistnode_t *node = &pflookup.table[keyindex&pflookup.mask];
 110
 111   do {
 112     if(node->key == key) {
 113       void * tmp=node->val;
 114       read_unlock(lockptr);
 115       return tmp;
 116     }
 117     node = node->next;
 118   } while (node!=NULL);
 119   read_unlock(lockptr);
 120   return NULL;
 121 }
 122
 123 unsigned int prehashRemove(unsigned int key) {
 124   int index;
 125   prehashlistnode_t *prev;
 126   prehashlistnode_t *ptr, *node;
 127
 128   //eom
 129   unsigned int keyindex=key>>1;
 130   volatile unsigned int * lockptr=&pflookup.larray[keyindex&PRELOCKMASK].lock;
 131
 132   while(!write_trylock(lockptr)) {
 133     sched_yield();
 134   }
 135
 136   prehashlistnode_t *curr = &pflookup.table[keyindex&pflookup.mask];
 137   //eom
 138
 139   for (; curr != NULL; curr = curr->next) {
 140     if (curr->key == key) {
 141       // Find a match in the hash table
 142       //decrement the number of elements in the global hashtable
 143       atomic_dec(&(pflookup.numelements));
 144
 145      if ((curr == &ptr[index]) && (curr->next == NULL)) {
 146        // Delete the first item inside the hashtable with no linked list of prehashlistnode_t
 147         curr->key = 0;
 148         curr->val = NULL;
 149       } else if ((curr == &ptr[index]) && (curr->next != NULL)) {
 150        //Delete the first item with a linked list of prehashlistnode_t  connected
 151         curr->key = curr->next->key;
 152         curr->val = curr->next->val;
 153         node = curr->next;
 154         curr->next = curr->next->next;
 155         free(node);
 156       } else {
 157        // Regular delete from linked listed
 158         prev->next = curr->next;
 159         free(curr);
 160       }
 161       //pthread_mutex_unlock(&pflookup.lock);
 162      write_unlock(lockptr);
 163       return 0;
 164     }
 165     prev = curr;
 166   }
 167   write_unlock(lockptr);
 168
 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
 178   for(i=0;i<PRENUMLOCKS;i++) {
 179     volatile unsigned int * lockptr=&pflookup.larray[i].lock;
 180
 181     while(!write_trylock(lockptr)) {
 182       sched_yield();
 183     }
 184   }
 185
 186   if (pflookup.numelements < pflookup.threshold) {
 187     //release lock and return
 188     for(i=0;i<PRENUMLOCKS;i++) {
 189       volatile unsigned int * lockptr=&pflookup.larray[i].lock;
 190       write_unlock(lockptr);
 191     }
 192     return;
 193   }
 194
 195   ptr = pflookup.table;
 196   oldsize = pflookup.size;
 197
 198   if((node = calloc(newsize, sizeof(prehashlistnode_t))) == NULL) {
 199     printf("Calloc error %s %d\n", __FILE__, __LINE__);
 200     return 1;
 201   }
 202
 203   pflookup.table = node;                //Update the global hashtable upon resize()
 204   pflookup.size = newsize;
 205   pflookup.threshold=newsize*pflookup.loadfactor;
 206   mask=pflookup.mask = newsize -1;
 207
 208   for(i = 0; i < oldsize; i++) {                        //Outer loop for each bin in hash table
 209     prehashlistnode_t * curr = &ptr[i];
 210     prehashlistnode_t *tmp, *next;
 211     int isfirst = 1;
 212     do {
 213       unsigned int key;
 214       if ((key=curr->key) == 0) {             //Exit inner loop if there the first element for a given bin/index is NULL
 215         break;                  //key = val =0 for element if not present within the hash table
 216       }
 217       next = curr->next;
 218       //index = (key & mask)>>1;
 219       index = (key >> 1) & mask;
 220       tmp=&pflookup.table[index];
 221       // Insert into the new table
 222       if(tmp->key==0) {
 223         tmp->key=curr->key;
 224         tmp->val=curr->val;
 225         if (!isfirst)
 226           free(curr);
 227       } /*
 228          NOTE:  Add this case if you change this...
 229          This case currently never happens because of the way things rehash....
 230 else if (isfirst) {
 231         prehashlistnode_t * newnode = calloc(1, sizeof(prehashlistnode_t));
 232         newnode->key = curr->key;
 233         newnode->val = curr->val;
 234         newnode->next = tmp->next;
 235         tmp->next=newnode;
 236         } */
 237       else {
 238         curr->next=tmp->next;
 239         tmp->next=curr;
 240       }
 241
 242       isfirst = 0;
 243       curr = next;
 244     } while(curr!=NULL);
 245   }
 246
 247   free(ptr);            //Free the memory of the old hash table
 248   for(i=0;i<PRENUMLOCKS;i++) {
 249     volatile unsigned int * lockptr=&pflookup.larray[i].lock;
 250     write_unlock(lockptr);
 251   }
 252   return 0;
 253 }
 254
 255 //Note: This is based on the implementation of the inserting a key in the first position of the hashtable
 256 void prehashClear() {
 257   /*
 258 #ifdef CACHE
 259   int i, isFirstBin;
 260   prehashlistnode_t *ptr, *prev, *curr;
 261
 262   pthread_mutex_lock(&pflookup.lock);
 263
 264   ptr = pflookup.table;
 265   for(i = 0; i < pflookup.size; i++) {
 266     prev = &ptr[i];
 267     isFirstBin = 1;
 268     while(prev->next != NULL) {
 269       isFirstBin = 0;
 270       curr = prev->next;
 271       prev->next = curr->next;
 272       free(curr);
 273     }
 274     if(isFirstBin == 1) {
 275       prev->key = 0;
 276       prev->next = NULL;
 277     }
 278   }
 279   {
 280     int stale;
 281     pthread_mutex_unlock(&pflookup.lock);
 282     pthread_mutex_lock(&prefetchcache_mutex);
 283     if (pNodeInfo.newstale==NULL) {
 284       //transfer the list wholesale;
 285       pNodeInfo.oldstale=pNodeInfo.oldptr;
 286       pNodeInfo.newstale=pNodeInfo.newptr;
 287     } else {
 288       //merge the two lists
 289       pNodeInfo.newstale->prev=pNodeInfo.oldptr;
 290       pNodeInfo.newstale=pNodeInfo.newptr;
 291     }
 292     stale=STALL_THRESHOLD-pNodeInfo.stale_count;
 293
 294     if (stale>0&&stale>pNodeInfo.stall)
 295       pNodeInfo.stall=stale;
 296
 297     pNodeInfo.stale_count+=pNodeInfo.os_count;
 298     pNodeInfo.oldptr=getObjStr(DEFAULT_OBJ_STORE_SIZE);
 299     pNodeInfo.newptr=pNodeInfo.oldptr;
 300     pNodeInfo.os_count=1;
 301     pthread_mutex_unlock(&prefetchcache_mutex);
 302   }
 303 #endif
 304   */
 305 }
 306