From f684d3e869489f0cf8fbcadd8000e659199dff2e Mon Sep 17 00:00:00 2001
From: yeom <yeom>
Date: Fri, 4 Dec 2009 19:18:00 +0000
Subject: [PATCH] changes on alt-prefetch lookup and gCollect

---
 .../src/Runtime/DSTM/interface/altprelookup.c | 40 ++++++---
 .../src/Runtime/DSTM/interface/altprelookup.h |  6 +-
 Robust/src/Runtime/DSTM/interface/gCollect.c  | 86 ++++++++++++++++++-
 3 files changed, 113 insertions(+), 19 deletions(-)

diff --git a/Robust/src/Runtime/DSTM/interface/altprelookup.c b/Robust/src/Runtime/DSTM/interface/altprelookup.c
index 72a34011..87afbe89 100644
--- a/Robust/src/Runtime/DSTM/interface/altprelookup.c
+++ b/Robust/src/Runtime/DSTM/interface/altprelookup.c
@@ -24,10 +24,23 @@ unsigned int prehashCreate(unsigned int size, float loadfactor) {
   pflookup.threshold=loadfactor*size;
   
   //Initilize 
-  for(i=0;i<NUMLOCKS;i++){
+  for(i=0;i<PRENUMLOCKS;i++){
     pflookup.larray[i].lock=RW_LOCK_BIAS;
   }
 
+  /*
+  //Intiliaze and set prefetch table mutex attribute
+  pthread_mutexattr_init(&pflookup.prefetchmutexattr);
+  //NOTE:PTHREAD_MUTEX_RECURSIVE is currently inside a #if_def UNIX98 in the pthread.h file
+  //Therefore use PTHREAD_MUTEX_RECURSIVE_NP instead
+  pthread_mutexattr_settype(&pflookup.prefetchmutexattr, PTHREAD_MUTEX_RECURSIVE_NP);
+
+  //Initialize mutex var
+  pthread_mutex_init(&pflookup.lock, &pflookup.prefetchmutexattr);
+  //pthread_mutex_init(&pflookup.lock, NULL);
+  pthread_cond_init(&pflookup.cond, NULL);
+  */
+
   return 0;
 }
 
@@ -49,14 +62,14 @@ void prehashInsert(unsigned int key, void *val) {
   }
 
   unsigned int keyindex=key>>1;
-  volatile unsigned int * lockptr=&pflookup.larray[keyindex&LOCKMASK].lock;
+  volatile unsigned int * lockptr=&pflookup.larray[keyindex&PRELOCKMASK].lock;
   while(!write_trylock(lockptr)) {
     sched_yield();
   }
 
   ptr = &pflookup.table[keyindex&pflookup.mask];
 
-  if((ptr->key==0) && (ptr->next== NULL)) { //Insert at the first bin of the table
+  if(ptr->key==0) { //Insert at the first bin of the table
     ptr->key = key;
     ptr->val = val;
     atomic_inc(&pflookup.numelements);
@@ -67,7 +80,6 @@ void prehashInsert(unsigned int key, void *val) {
         isFound=1;
         tmp->val = val;//Replace value for an exsisting key
         write_unlock(lockptr);
-
         return;
       }
       tmp=tmp->next;
@@ -86,11 +98,11 @@ void prehashInsert(unsigned int key, void *val) {
 }
 
 // Search for an address for a given oid
-INLINE void *prehashSearch(unsigned int key) {
+void *prehashSearch(unsigned int key) {
   int index;
  
   unsigned int keyindex=key>>1;
-  volatile unsigned int * lockptr=&pflookup.larray[keyindex&LOCKMASK].lock;
+  volatile unsigned int * lockptr=&pflookup.larray[keyindex&PRELOCKMASK].lock;
   while(!read_trylock(lockptr)) {
     sched_yield();
   }
@@ -113,15 +125,17 @@ unsigned int prehashRemove(unsigned int key) {
   prehashlistnode_t *prev;
   prehashlistnode_t *ptr, *node;
 
+  //eom
   unsigned int keyindex=key>>1;
-  volatile unsigned int * lockptr=&pflookup.larray[keyindex&LOCKMASK].lock;
+  volatile unsigned int * lockptr=&pflookup.larray[keyindex&PRELOCKMASK].lock;
 
   while(!write_trylock(lockptr)) {
     sched_yield();
   }
   
   prehashlistnode_t *curr = &pflookup.table[keyindex&pflookup.mask];
-  
+  //eom
+
   for (; curr != NULL; curr = curr->next) {
     if (curr->key == key) {        
       // Find a match in the hash table
@@ -161,7 +175,7 @@ unsigned int prehashResize(unsigned int newsize) {
   int i,index;
   unsigned int mask;
 
-  for(i=0;i<NUMLOCKS;i++) {
+  for(i=0;i<PRENUMLOCKS;i++) {
     volatile unsigned int * lockptr=&pflookup.larray[i].lock;
     
     while(!write_trylock(lockptr)) {
@@ -171,7 +185,7 @@ unsigned int prehashResize(unsigned int newsize) {
   
   if (pflookup.numelements < pflookup.threshold) {
     //release lock and return
-    for(i=0;i<NUMLOCKS;i++) {
+    for(i=0;i<PRENUMLOCKS;i++) {
       volatile unsigned int * lockptr=&pflookup.larray[i].lock;
       write_unlock(lockptr);
     }
@@ -189,7 +203,7 @@ unsigned int prehashResize(unsigned int newsize) {
   pflookup.table = node;                //Update the global hashtable upon resize()
   pflookup.size = newsize;
   pflookup.threshold=newsize*pflookup.loadfactor;
-  mask=pflookup.mask = (newsize << 1) -1;
+  mask=pflookup.mask = newsize -1;
 
   for(i = 0; i < oldsize; i++) {                        //Outer loop for each bin in hash table
     prehashlistnode_t * curr = &ptr[i];
@@ -231,11 +245,11 @@ else if (isfirst) {
   }
 
   free(ptr);            //Free the memory of the old hash table
-  for(i=0;i<NUMLOCKS;i++) {
+  for(i=0;i<PRENUMLOCKS;i++) {
     volatile unsigned int * lockptr=&pflookup.larray[i].lock;
     write_unlock(lockptr);
   }
-  return ;
+  return 0;
 }
 
 //Note: This is based on the implementation of the inserting a key in the first position of the hashtable
diff --git a/Robust/src/Runtime/DSTM/interface/altprelookup.h b/Robust/src/Runtime/DSTM/interface/altprelookup.h
index 2c34f372..d6796d7a 100644
--- a/Robust/src/Runtime/DSTM/interface/altprelookup.h
+++ b/Robust/src/Runtime/DSTM/interface/altprelookup.h
@@ -21,8 +21,8 @@ struct prelockarray {
    int buf[15];
 };
 
-#define NUMLOCKS 16
-#define LOCKMASK (NUMLOCKS-1)
+#define PRENUMLOCKS 16
+#define PRELOCKMASK (PRENUMLOCKS-1)
 
 
 struct objstr;
@@ -34,7 +34,7 @@ typedef struct prehashtable {
   unsigned int numelements;
   unsigned int threshold;
   double loadfactor;
-  struct prelockarray larray[NUMLOCKS];
+  struct prelockarray larray[PRENUMLOCKS];
 } prehashtable_t;
 
 /* Prototypes for hash*/
diff --git a/Robust/src/Runtime/DSTM/interface/gCollect.c b/Robust/src/Runtime/DSTM/interface/gCollect.c
index a6c115aa..0be92327 100644
--- a/Robust/src/Runtime/DSTM/interface/gCollect.c
+++ b/Robust/src/Runtime/DSTM/interface/gCollect.c
@@ -1,5 +1,9 @@
 #include "gCollect.h"
-#include "prelookup.h"
+#if 0
+#include "altprelookup.h"
+#else
+#inlcude "prelookup.h"
+#endif
 
 
 extern pthread_mutex_t prefetchcache_mutex; //Mutex to lock Prefetch Cache
@@ -62,7 +66,7 @@ void *prefetchobjstrAlloc(unsigned int size) {
   pNodeInfo.newptr->prev=tmp;
   pNodeInfo.newptr=tmp;
   pNodeInfo.os_count++;
-  
+
   if (pNodeInfo.os_count>PREFETCH_FLUSH_THRESHOLD) {
     //remove oldest from linked list
     objstr_t *tofree=pNodeInfo.oldptr;
@@ -95,15 +99,33 @@ void *prefetchobjstrAlloc(unsigned int size) {
   return ptr;
 }
 
+#if 0
 void clearBlock(objstr_t *block) {
+
   unsigned long int tmpbegin=(unsigned int)block;
   unsigned long int tmpend=(unsigned int)block->top;
   int i, j;
   prehashlistnode_t *ptr;
-  pthread_mutex_lock(&pflookup.lock);
+  //pthread_mutex_lock(&pflookup.lock);
+  /*
+  for(i=0;i<PRENUMLOCKS;i++) {
+    volatile unsigned int * lockptr=&pflookup.larray[i].lock;
+    
+    while(!write_trylock(lockptr)) {
+      sched_yield();
+    }
+  }
+  */
 
+  int lockindex=0;
   ptr = pflookup.table;
+  volatile unsigned int * lockptr_current=&pflookup.larray[lockindex].lock;
+  while(!write_trylock(lockptr_current)) {
+    sched_yield();
+  }
+
   for(i = 0; i<pflookup.size; i++) {
+
     prehashlistnode_t *orig=&ptr[i];
     prehashlistnode_t *curr = orig;
     prehashlistnode_t *next=curr->next;
@@ -133,9 +155,67 @@ void clearBlock(objstr_t *block) {
 	}
       }
     }
+
+    if(((i+1)&(pflookup.mask>>4))==0 && (i+1)<pflookup.size){
+      // try to grab new lock
+      lockindex++;
+      volatile unsigned int * lockptr_new=&pflookup.larray[lockindex].lock;
+      while(!write_trylock(lockptr_new)){
+        sched_yield();
+      }
+      //printf("grab new lock id=%d for %d\n",lockindex,i);
+      write_unlock(lockptr_current);
+      lockptr_current=lockptr_new;      
+    }
+    
+  }// end of for (pflokup)
+  
+  write_unlock(lockptr_current);
+ 
+}
+#else
+void clearBlock(objstr_t *block) {
+  unsigned long int tmpbegin=(unsigned int)block;
+  unsigned long int tmpend=(unsigned int)block->top;
+  int i, j;
+  prehashlistnode_t *ptr;
+  pthread_mutex_lock(&pflookup.lock);
+
+  ptr = pflookup.table;
+  for(i = 0; i<pflookup.size; i++) {
+    prehashlistnode_t *orig=&ptr[i];
+    prehashlistnode_t *curr = orig;
+    prehashlistnode_t *next=curr->next;
+    for(; next != NULL; curr=next, next = next->next) {
+      unsigned int val=(unsigned int)next->val;
+      if ((val>=tmpbegin)&(val<tmpend)) {
+	prehashlistnode_t *tmp=curr->next=next->next;
+	free(next);
+	next=curr;
+	//loop condition is broken now...need to check before incrementing
+	//if (next==NULL)
+	// break;
+      }
+    }
+    {
+      unsigned int val=(unsigned int)orig->val;
+      if ((val>=tmpbegin)&(val<tmpend)) {
+	if (orig->next==NULL) {
+	  orig->key=0;
+	  orig->val=NULL;
+	} else {
+	  next=orig->next;
+	  orig->val=next->val;
+	  orig->key=next->key;
+	  orig->next=next->next;
+	  free(next);
+	}
+      }
+    }
   }
   pthread_mutex_unlock(&pflookup.lock);
 }
+#endif
 
 objstr_t *allocateNew(unsigned int size) {
   objstr_t *tmp;
-- 
2.34.1