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   unsigned int keyindex = key >> 1;
 125   volatile unsigned int * lockptr=&pflookup.larray[keyindex&PRELOCKMASK].lock;
 126   prehashlistnode_t *node, *prev;
 127
 128   while(!write_trylock(lockptr)) {
 129     sched_yield();
 130   }
 131   prehashlistnode_t *curr = &pflookup.table[keyindex&pflookup.mask];
 132   // If there are no elements
 133   //delete from first bin of table
 134   if (curr->next == NULL && curr->key == key) {
 135     curr->key = 0;
 136     //TODO free(val) ?
 137     curr->val = NULL;
 138     atomic_dec(&(pflookup.numelements));
 139     write_unlock(lockptr);
 140     return 0;
 141   }
 142   //delete from first bin of table but elements follow in linked list
 143   if (curr->next != NULL && curr->key == key) {
 144     curr->key = curr->next->key;
 145     curr->val = curr->next->val;
 146     node = curr->next;
 147     curr->next = node->next;
 148     free(node);
 149     atomic_dec(&(pflookup.numelements));
 150     write_unlock(lockptr);
 151     return 0;
 152   }
 153   prev = curr;
 154   curr = curr->next;
 155   //delete from elements in the linked list
 156   for(; curr != NULL; curr = curr->next) {
 157     if (curr->key == key) {
 158       prev->next = curr->next;
 159       free(curr);
 160       atomic_dec(&(pflookup.numelements));
 161       write_unlock(lockptr);
 162       return 0;
 163     }
 164     prev = curr;
 165   }
 166   write_unlock(lockptr);
 167   return 1;
 168 }
 169
 170 unsigned int prehashResize(unsigned int newsize) {
 171   prehashlistnode_t *node, *ptr;  // curr and next keep track of the current and the next chashlistnodes in a linked list
 172   unsigned int oldsize;
 173   int i,index;
 174   unsigned int mask;
 175
 176   for(i=0; i<PRENUMLOCKS; i++) {
 177     volatile unsigned int * lockptr=&pflookup.larray[i].lock;
 178
 179     while(!write_trylock(lockptr)) {
 180       sched_yield();
 181     }
 182   }
 183
 184   if (pflookup.numelements < pflookup.threshold) {
 185     //release lock and return
 186     for(i=0; i<PRENUMLOCKS; i++) {
 187       volatile unsigned int * lockptr=&pflookup.larray[i].lock;
 188       write_unlock(lockptr);
 189     }
 190     return;
 191   }
 192
 193   ptr = pflookup.table;
 194   oldsize = pflookup.size;
 195
 196   if((node = calloc(newsize, sizeof(prehashlistnode_t))) == NULL) {
 197     printf("Calloc error %s %d\n", __FILE__, __LINE__);
 198     return 1;
 199   }
 200
 201   pflookup.table = node;                //Update the global hashtable upon resize()
 202   pflookup.size = newsize;
 203   pflookup.threshold=newsize*pflookup.loadfactor;
 204   mask=pflookup.mask = newsize -1;
 205
 206   for(i = 0; i < oldsize; i++) {                        //Outer loop for each bin in hash table
 207     prehashlistnode_t * curr = &ptr[i];
 208     prehashlistnode_t *tmp, *next;
 209     int isfirst = 1;
 210     do {
 211       unsigned int key;
 212       if ((key=curr->key) == 0) {             //Exit inner loop if there the first element for a given bin/index is NULL
 213         break;                  //key = val =0 for element if not present within the hash table
 214       }
 215       next = curr->next;
 216       //index = (key & mask)>>1;
 217       index = (key >> 1) & mask;
 218       tmp=&pflookup.table[index];
 219       // Insert into the new table
 220       if(tmp->key==0) {
 221         tmp->key=curr->key;
 222         tmp->val=curr->val;
 223         if (!isfirst)
 224           free(curr);
 225       } /*
 226            NOTE:  Add this case if you change this...
 227            This case currently never happens because of the way things rehash....
 228            else if (isfirst) {
 229            prehashlistnode_t * newnode = calloc(1, sizeof(prehashlistnode_t));
 230            newnode->key = curr->key;
 231            newnode->val = curr->val;
 232            newnode->next = tmp->next;
 233            tmp->next=newnode;
 234            } */
 235       else {
 236         curr->next=tmp->next;
 237         tmp->next=curr;
 238       }
 239
 240       isfirst = 0;
 241       curr = next;
 242     } while(curr!=NULL);
 243   }
 244
 245   free(ptr);            //Free the memory of the old hash table
 246   for(i=0; i<PRENUMLOCKS; i++) {
 247     volatile unsigned int * lockptr=&pflookup.larray[i].lock;
 248     write_unlock(lockptr);
 249   }
 250   return 0;
 251 }
 252
 253 //Note: This is based on the implementation of the inserting a key in the first position of the hashtable
 254 void prehashClear() {
 255   /*
 256    #ifdef CACHE
 257      int i, isFirstBin;
 258      prehashlistnode_t *ptr, *prev, *curr;
 259
 260      pthread_mutex_lock(&pflookup.lock);
 261
 262      ptr = pflookup.table;
 263      for(i = 0; i < pflookup.size; i++) {
 264      prev = &ptr[i];
 265      isFirstBin = 1;
 266      while(prev->next != NULL) {
 267       isFirstBin = 0;
 268       curr = prev->next;
 269       prev->next = curr->next;
 270       free(curr);
 271      }
 272      if(isFirstBin == 1) {
 273       prev->key = 0;
 274       prev->next = NULL;
 275      }
 276      }
 277      {
 278      int stale;
 279      pthread_mutex_unlock(&pflookup.lock);
 280      pthread_mutex_lock(&prefetchcache_mutex);
 281      if (pNodeInfo.newstale==NULL) {
 282       //transfer the list wholesale;
 283       pNodeInfo.oldstale=pNodeInfo.oldptr;
 284       pNodeInfo.newstale=pNodeInfo.newptr;
 285      } else {
 286       //merge the two lists
 287       pNodeInfo.newstale->prev=pNodeInfo.oldptr;
 288       pNodeInfo.newstale=pNodeInfo.newptr;
 289      }
 290      stale=STALL_THRESHOLD-pNodeInfo.stale_count;
 291
 292      if (stale>0&&stale>pNodeInfo.stall)
 293       pNodeInfo.stall=stale;
 294
 295      pNodeInfo.stale_count+=pNodeInfo.os_count;
 296      pNodeInfo.oldptr=getObjStr(DEFAULT_OBJ_STORE_SIZE);
 297      pNodeInfo.newptr=pNodeInfo.oldptr;
 298      pNodeInfo.os_count=1;
 299      pthread_mutex_unlock(&prefetchcache_mutex);
 300      }
 301    #endif
 302    */
 303 }
 304