From ad9391442e6a6e51540fe5d0a1ae3e422da99e98 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Fri, 20 Feb 2009 04:49:31 +0000 Subject: [PATCH] Changes to prefetch object stores --- Robust/src/Runtime/DSTM/interface/dstm.h | 1 + Robust/src/Runtime/DSTM/interface/gCollect.c | 237 ++++++++---------- Robust/src/Runtime/DSTM/interface/gCollect.h | 33 ++- Robust/src/Runtime/DSTM/interface/prelookup.c | 37 ++- Robust/src/Runtime/DSTM/interface/trans.c | 3 - 5 files changed, 153 insertions(+), 158 deletions(-) diff --git a/Robust/src/Runtime/DSTM/interface/dstm.h b/Robust/src/Runtime/DSTM/interface/dstm.h index 8a458dc5..9a65fdb4 100644 --- a/Robust/src/Runtime/DSTM/interface/dstm.h +++ b/Robust/src/Runtime/DSTM/interface/dstm.h @@ -155,6 +155,7 @@ typedef struct objstr { unsigned int size; //this many bytes are allocated after this header void *top; struct objstr *next; + struct objstr *prev; } objstr_t; typedef struct oidmidpair { diff --git a/Robust/src/Runtime/DSTM/interface/gCollect.c b/Robust/src/Runtime/DSTM/interface/gCollect.c index 98b1fa80..1707b230 100644 --- a/Robust/src/Runtime/DSTM/interface/gCollect.c +++ b/Robust/src/Runtime/DSTM/interface/gCollect.c @@ -1,159 +1,135 @@ #include "gCollect.h" #include "prelookup.h" -extern objstr_t *prefetchcache; //Global Prefetch cache + extern pthread_mutex_t prefetchcache_mutex; //Mutex to lock Prefetch Cache extern prehashtable_t pflookup; //Global prefetch cache lookup table -prefetchNodeInfo_t *pNodeInfo; //Global prefetch holding metadata +prefetchNodeInfo_t pNodeInfo; //Global prefetch holding metadata + +#define OSUSED(x) (((unsigned int)(x)->top)-((unsigned int) (x+1))) +#define OSFREE(x) ((x)->size-OSUSED(x)) void initializePCache() { - pNodeInfo = calloc(1, sizeof(prefetchNodeInfo_t)); //Not freed yet - pNodeInfo->oldptr = prefetchcache; - pNodeInfo->newptr = NULL; - pNodeInfo->num_old_objstr = 1; //for prefetch cache allocated by objstralloc in trans.c file - pNodeInfo->maxsize = DEFAULT_OBJ_STORE_SIZE; + objstr_t * os=objstrCreate(DEFAULT_OBJ_STORE_SIZE); + pNodeInfo.oldptr = os; + pNodeInfo.newptr = os; + pNodeInfo.os_count = 1; //for prefetch cache allocated by objstralloc in trans.c file + pNodeInfo.oldstale=NULL; + pNodeInfo.newstale=NULL; + pNodeInfo.stale_count=0; + pNodeInfo.stall=0; } -void *prefetchobjstrAlloc(unsigned int size) { - void * ptr = NULL; - if(pNodeInfo->num_old_objstr <= PREFETCH_FLUSH_COUNT_THRESHOLD) { - //regular allocation - if((ptr = normalPrefetchAlloc(prefetchcache, size)) == NULL) { - printf("Error: %s() prefetch cache alloc error %s, %d\n", __func__, __FILE__, __LINE__); - return NULL; - } - return ptr; +objstr_t * getObjStr(unsigned int size) { + if (pNodeInfo.stall>0) + pNodeInfo.stall--; + if (size<=DEFAULT_OBJ_STORE_SIZE&&pNodeInfo.stale_count>STALE_MINTHRESHOLD&&pNodeInfo.stall==0) { + //recycle + objstr_t * tmp=pNodeInfo.oldstale; + pNodeInfo.oldstale=pNodeInfo.oldstale->prev; + if (pNodeInfo.oldstale==NULL) + pNodeInfo.newstale=NULL; + pNodeInfo.stale_count--; + tmp->top=tmp+1; + tmp->prev=NULL; + return tmp; } else { - // Iterate through available blocks to see if size can be allocated - if((ptr = lookUpFreeSpace(pNodeInfo->newptr, pNodeInfo->oldptr, size)) != NULL) { - return ptr; - } else { //allocate new block if size not available - if(size >= pNodeInfo->maxsize) { - if((ptr = allocateNew(size)) == NULL) { - printf("Error: %s() Calloc error %s %d\n", __func__, __FILE__, __LINE__); - return NULL; - } - return ptr; - } else { //If size less then reclaim old blocks - clearNBlocks(pNodeInfo->oldptr, pNodeInfo->newptr); - //update oldptr and newptr - updatePtrs(); - //look for free space if available in the free blocks - if((ptr = lookUpFreeSpace(pNodeInfo->newptr, pNodeInfo->oldptr, size)) != NULL) { - return ptr; - } else { - if((ptr = allocateNew(size)) == NULL) { - printf("Error: %s() Calloc error %s %d\n", __func__, __FILE__, __LINE__); - return NULL; - } - return ptr; - } - } - } + int allocsize=(size>DEFAULT_OBJ_STORE_SIZE)?size:DEFAULT_OBJ_STORE_SIZE; + return objstrCreate(allocsize); } } -void *normalPrefetchAlloc(objstr_t *store, unsigned int size) { - void *tmp; - while (1) { - if(((unsigned int)store->top - (((unsigned int)store) + sizeof(objstr_t)) + size) <= store->size) { //store not full - tmp = store->top; - store->top += size; - return tmp; - } - //store full - if(store->next == NULL) { - //end of list, all full - if(size > DEFAULT_OBJ_STORE_SIZE) { - //in case of large objects - if((store->next = (objstr_t *) calloc(1,(sizeof(objstr_t) + size))) == NULL) { - printf("%s() Calloc error at line %d, %s\n", __func__, __LINE__, __FILE__); - return NULL; - } - store = store->next; - store->size = size; +void *prefetchobjstrAlloc(unsigned int size) { + //try existing space in first two OS + objstr_t *os=pNodeInfo.newptr; + if (size<=OSFREE(os)) { + void *tmp=os->top; + os->top=((char *)os->top)+size; + return tmp; + } + if ((os=os->next)!=NULL&&(size<=OSFREE(os))) { + void *tmp=os->top; + os->top=((char *)os->top)+size; + return tmp; + } + //need to allocate new space + objstr_t *tmp=getObjStr(size);; + + //link new node in + tmp->next=pNodeInfo.newptr; + 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; + pNodeInfo.oldptr=tofree->prev; + pNodeInfo.os_count--; + //need to flush cache + clearBlock(tofree); + if (pNodeInfo.stale_count>STALE_MAXTHRESHOLD) { + //need to toss store + free(tofree); + } else { + if (pNodeInfo.newstale==NULL) { + //first store + pNodeInfo.newstale=pNodeInfo.oldstale=tofree; + tofree->prev=NULL; + pNodeInfo.stale_count++; } else { - if((store->next = (objstr_t *) calloc(1, (sizeof(objstr_t) + DEFAULT_OBJ_STORE_SIZE))) == NULL) { - printf("%s() Calloc error at line %d, %s\n", __func__, __LINE__, __FILE__); - return NULL; - } - store = store->next; - store->size = DEFAULT_OBJ_STORE_SIZE; + //just add it to the list + pNodeInfo.newstale->prev=tofree; + pNodeInfo.newstale=tofree; + pNodeInfo.stale_count++; } - //Update maxsize of objstr blocks, num of blocks and newptr - pNodeInfo->num_old_objstr++; - if(pNodeInfo->num_old_objstr <= PREFETCH_FLUSH_COUNT_THRESHOLD/2) - pNodeInfo->newptr = store; - if(pNodeInfo->maxsize < size) - pNodeInfo->maxsize = size; - store->top = (void *)(((unsigned int)store) + sizeof(objstr_t) + size); - return (void *)(((unsigned int)store) + sizeof(objstr_t)); - } else { - store = store->next; } } -} -void *lookUpFreeSpace(void *startAddr, void *endAddr, int size) { - objstr_t *ptr; - void *tmp; - ptr = (objstr_t *)(startAddr); - while(ptr != NULL && ((unsigned long int)ptr!= (unsigned long int)endAddr)) { - if(((unsigned int)ptr->top - (((unsigned int)ptr) + sizeof(objstr_t)) + size) <= ptr->size) { //store not full - tmp = ptr->top; - ptr->top += size; - return tmp; - } - ptr = ptr->next; - } - return NULL; + void *ptr=tmp->top; + tmp->top=((char *)tmp->top)+size; + return ptr; } -void clearNBlocks(void *oldaddr, void * newaddr) { - int count = 0; - objstr_t *tmp = (objstr_t *) oldaddr; +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); - while(((unsigned int) tmp != (unsigned int)newaddr) && (tmp != NULL)) { - void * begin = (void *)tmp+sizeof(objstr_t); - void * end = (void *)tmp+sizeof(objstr_t)+tmp->size; - tmp->top = (void *)tmp+sizeof(objstr_t); - clearPLookUpTable(begin, end); - //TODO only for testing purpose, remove later - memset(tmp->top, 0, tmp->size); - tmp = tmp->next; - } - pthread_mutex_unlock(&pflookup.lock); -} -void clearPLookUpTable(void *begin, void *end) { - unsigned long int tmpbegin; - unsigned long int tmpend; - tmpbegin = (unsigned long int) begin; - tmpend = (unsigned long int) end; - int i, j; - prehashlistnode_t *ptr = pflookup.table; + ptr = pflookup.table; for(i = 0; inext) { - if(((unsigned long int)(curr->val) >= tmpbegin) && ((unsigned long int)(curr->val) < tmpend)) { - unsigned int oid = curr->key; - objheader_t *objheader; - if((objheader = prehashSearch(oid)) != NULL) { - prehashRemove(oid); + 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)&(valnext=next->next; + free(next); + } + } + { + unsigned int val=(unsigned int)orig->val; + if ((val>=tmpbegin)&(valnext==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); } -void updatePtrs() { - void *ptr; - ptr = pNodeInfo->oldptr; - pNodeInfo->oldptr = pNodeInfo->newptr; - pNodeInfo->newptr = ptr; -} - -void *allocateNew(unsigned int size) { +objstr_t *allocateNew(unsigned int size) { objstr_t *tmp; if((tmp = (objstr_t *) calloc(1, (sizeof(objstr_t) +size))) == NULL) { printf("Error: %s() Calloc error %s %d\n", __func__, __FILE__, __LINE__); @@ -162,11 +138,6 @@ void *allocateNew(unsigned int size) { tmp->size = size; tmp->top = (void *)(((unsigned int)tmp) + sizeof(objstr_t) + size); //Insert newly allocated block into linked list of prefetch cache - tmp->next = ((objstr_t *)(pNodeInfo->newptr))->next; - ((objstr_t *)(pNodeInfo->newptr))->next = tmp; - pNodeInfo->num_old_objstr++; // Update maxsize of prefetch objstr blocks - if(pNodeInfo->maxsize < tmp->size) - pNodeInfo->maxsize = tmp->size; - return (void *)(((unsigned int)tmp) + sizeof(objstr_t)); + return tmp; } diff --git a/Robust/src/Runtime/DSTM/interface/gCollect.h b/Robust/src/Runtime/DSTM/interface/gCollect.h index 3bf6a71c..5a1b8e4a 100644 --- a/Robust/src/Runtime/DSTM/interface/gCollect.h +++ b/Robust/src/Runtime/DSTM/interface/gCollect.h @@ -6,27 +6,38 @@ /*********************************** ****** Global constants ********** **********************************/ -#define PREFETCH_FLUSH_COUNT_THRESHOLD 30 + +#define STALE_MINTHRESHOLD 30 + +#define STALE_MAXTHRESHOLD 40 //ugly hack..if you make this too small things +// will fail in odd subtle ways + +#define PREFETCH_FLUSH_THRESHOLD 20 +#define STALL_THRESHOLD 30 + + /********************************* ********* Global variables ****** ********************************/ typedef struct prefetchNodeInfo { - void *oldptr; - void *newptr; - int num_old_objstr; - int maxsize; + objstr_t *oldptr; + objstr_t *newptr; + int os_count; + + objstr_t *oldstale; + objstr_t *newstale; + int stale_count; + int stall; + } prefetchNodeInfo_t; /******************************** ******** Functions ************ *******************************/ void *prefetchobjstrAlloc(unsigned int size); -void *normalPrefetchAlloc(objstr_t *, unsigned int); void initializePCache(); -void *lookUpFreeSpace(void *, void *, int); -void clearNBlocks(void *, void *); -void clearPLookUpTable(void *, void *); -void updatePtrs(); -void *allocateNew(unsigned int size); +void clearBlock(objstr_t *); +objstr_t *allocateNew(unsigned int size); +objstr_t * getObjStr(unsigned int size); #endif diff --git a/Robust/src/Runtime/DSTM/interface/prelookup.c b/Robust/src/Runtime/DSTM/interface/prelookup.c index 79a616f4..0e3c17c9 100644 --- a/Robust/src/Runtime/DSTM/interface/prelookup.c +++ b/Robust/src/Runtime/DSTM/interface/prelookup.c @@ -1,6 +1,9 @@ /* LOCK THE ENTIRE HASH TABLE */ #include "prelookup.h" +#include "gCollect.h" extern objstr_t *prefetchcache; +extern pthread_mutex_t prefetchcache_mutex; //Mutex to lock Prefetch Cache +extern prefetchNodeInfo_t pNodeInfo; prehashtable_t pflookup; //Global prefetch cache table @@ -13,8 +16,6 @@ unsigned int prehashCreate(unsigned int size, float loadfactor) { printf("Calloc error %s %d\n", __FILE__, __LINE__); return 1; } - pflookup.hack=NULL; - pflookup.hack2=NULL; pflookup.table = nodes; pflookup.size = size; pflookup.numelements = 0; // Initial number of elements in the hash @@ -195,9 +196,6 @@ void prehashClear() { int i, isFirstBin; prehashlistnode_t *ptr, *prev, *curr; - objstr_t *oldcache=prefetchcache; - prefetchcache=objstrCreate(prefetchcache->size); - pthread_mutex_lock(&pflookup.lock); ptr = pflookup.table; for(i = 0; i < pflookup.size; i++) { @@ -214,13 +212,30 @@ void prehashClear() { prev->next = NULL; } } - pthread_mutex_unlock(&pflookup.lock); - - if (pflookup.hack2!=NULL) { - objstrDelete(pflookup.hack2); + { + int stale; + pthread_mutex_unlock(&pflookup.lock); + pthread_mutex_lock(&prefetchcache_mutex); + if (pNodeInfo.newstale==NULL) { + //transfer the list wholesale; + pNodeInfo.oldstale=pNodeInfo.oldptr; + pNodeInfo.newstale=pNodeInfo.newptr; + } else { + //merge the two lists + pNodeInfo.newstale->prev=pNodeInfo.oldptr; + pNodeInfo.newstale=pNodeInfo.newptr; + } + stale=STALL_THRESHOLD-pNodeInfo.stale_count; + + if (stale>0&&stale>pNodeInfo.stall) + pNodeInfo.stall=stale; + + pNodeInfo.stale_count+=pNodeInfo.os_count; + pNodeInfo.oldptr=getObjStr(DEFAULT_OBJ_STORE_SIZE); + pNodeInfo.newptr=pNodeInfo.oldptr; + pNodeInfo.os_count=1; + pthread_mutex_unlock(&prefetchcache_mutex); } - pflookup.hack2=pflookup.hack; - pflookup.hack=oldcache; #endif } diff --git a/Robust/src/Runtime/DSTM/interface/trans.c b/Robust/src/Runtime/DSTM/interface/trans.c index 528dafab..7c1b2fc5 100644 --- a/Robust/src/Runtime/DSTM/interface/trans.c +++ b/Robust/src/Runtime/DSTM/interface/trans.c @@ -20,7 +20,6 @@ #endif #define NUM_THREADS 1 -#define PREFETCH_CACHE_SIZE 1048576 //1MB #define CONFIG_FILENAME "dstm.conf" @@ -29,7 +28,6 @@ extern int classsize[]; pfcstats_t *evalPrefetch; extern int numprefetchsites; //Global variable containing number of prefetch sites extern pthread_mutex_t mainobjstore_mutex; // Mutex to lock main Object store -objstr_t *prefetchcache; //Global Prefetch cache pthread_mutex_t prefetchcache_mutex; // Mutex to lock Prefetch Cache pthread_mutexattr_t prefetchcache_mutex_attr; /* Attribute for lock to make it a recursive lock */ extern prehashtable_t pflookup; //Global Prefetch cache's lookup table @@ -258,7 +256,6 @@ void *pCacheAlloc(objstr_t *store, unsigned int size) { void transInit() { //Create and initialize prefetch cache structure #ifdef CACHE - prefetchcache = objstrCreate(PREFETCH_CACHE_SIZE); initializePCache(); if((evalPrefetch = initPrefetchStats()) == NULL) { printf("%s() Error allocating memory at %s, %d\n", __func__, __FILE__, __LINE__); -- 2.34.1