From 77dc8937bc23ca333663d8301680a9939d9a6d1c Mon Sep 17 00:00:00 2001 From: bdemsky Date: Tue, 19 Oct 2010 21:33:43 +0000 Subject: [PATCH] changes --- Robust/src/Runtime/oooJava/hashStructure.c | 297 +++++++++------------ Robust/src/Runtime/oooJava/hashStructure.h | 57 +--- 2 files changed, 134 insertions(+), 220 deletions(-) diff --git a/Robust/src/Runtime/oooJava/hashStructure.c b/Robust/src/Runtime/oooJava/hashStructure.c index 872263b2..3d1e0303 100644 --- a/Robust/src/Runtime/oooJava/hashStructure.c +++ b/Robust/src/Runtime/oooJava/hashStructure.c @@ -6,6 +6,10 @@ //NOTE: this is only temporary (for testing) and will be removed in favor of thread local variables //It's basically an array of hashStructures so we can simulate what would happen in a many-threaded version HashStructure ** allHashStructures; +#define ISWRITEBIN(x) (x&BINMASK) +#define ISREADBIN(x) (!(x&BINMASK)) +//#define POPCOUNT(x) __builtin_popcountll(x) +//__builtin_popcountll //NOTE: only temporary void rcr_createMasterHashTableArray(int maxSize){ @@ -19,7 +23,6 @@ HashStructure* rcr_createHashtable(int sizeofWaitingQueue){ newTable->array[i].tail=NULL; } - // newTable->waitingQueue=mallocWaitingQueue(sizeofWaitingQueue); return newTable; } @@ -36,19 +39,11 @@ ReadBinItem_rcr* rcr_createReadBinItem(){ return binitem; } -int rcr_isReadBinItem(BinItem_rcr* b){ - return b->type==READBIN; -} - -int rcr_isWriteBinItem(BinItem_rcr* b){ - return b->type==WRITEBIN; -} - inline int rcr_generateKey(void * ptr){ - return (((struct genericObjectStruct *) ptr)->oid)&RH_MASK; + return (((struct ___Object___ *) ptr)->oid)&RH_MASK; } -int rcr_WRITEBINCASE(HashStructure *T, void *ptr, int traverserID, SESEcommon *task, void *heaproot) { +int rcr_WRITEBINCASE(HashStructure *T, void *ptr, SESEcommon *task, int index) { //chain of bins exists => tail is valid //if there is something in front of us, then we are not ready BinItem_rcr * val; @@ -68,12 +63,8 @@ int rcr_WRITEBINCASE(HashStructure *T, void *ptr, int traverserID, SESEcommon *t b->status=READY; //common to both types - td->binitem = b; - td->hashtable=T; - td->resumePtr = ptr; - td->task= task; - td->traverserID = traverserID; - td->heaproot = heaproot; + td->task=task; + td->bitindex=1<tail=b; //release lock @@ -81,48 +72,69 @@ int rcr_WRITEBINCASE(HashStructure *T, void *ptr, int traverserID, SESEcommon *t return READY; } - int status=NOTREADY; BinItem_rcr *bintail=be->tail; + bitv rdmask=0,wrmask=0; + int status=NOTREADY; - if (bintail->type == WRITEBIN) { - TraverserData * td = &(((WriteBinItem_rcr *)bintail)->val); + if (ISWRITEBIN(bintail->type)) { + WriteBinItem_rcr * td = (WriteBinItem_rcr *)bintail; //last one is to check for SESE blocks in a while loop. if(unlikely(td->task == task)) { be->head=val; - //return ready...this constraint is already handled - return READY; + bitv bit=1<bitindexwr)) { + td->bitindexwr|=bit; + td->bitindexrd|=bit; + return (bintail->status==READY)?READY:SPECNOTREADY; + } else + return READY; } - } else if (bintail->type == READBIN) { + } else { TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1]; if(unlikely(td->task == task)) { //if it matches, then we remove it and the code below will upgrade it to a write. ((ReadBinItem_rcr *)bintail)->index--; - bintail->total--; + atomic_dec(&bintail->total); + rdmask=tr->bitindex; + if (bintail->status!=READY) + wrmask=rdmask; + status=SPECNOTREADY; } } WriteBinItem_rcr *b=rcr_createWriteBinItem(); - TraverserData * td = &b->val; b->item.total=1; + b->task=task; - //fillout traverserData - //Note: this list could be smaller in the future, for now I'm just including all the info I may need. - td->binitem = (BinItem_rcr*)b; - td->hashtable=T; - td->resumePtr = ptr; - td->task= task; - td->traverserID = traverserID; - td->heaproot = heaproot; - + bitv bit=1<bitindexwr=bit|wrmask; + b->bitindexrd=bit|rdmask; b->item.status=status; bintail->next=(BinItem_rcr*)b; be->tail=(BinItem_rcr*)b; + + if (bintail->status==READY&&bintail->total==0) { + //we may have to set write as ready + while(val->total==0) { + if (val==b) { + b->item.status=READY; + be->head=val; + return READY; + } + val=val->next; + } + } + //RELEASE LOCK be->head=val; return status; } -int rcr_READBINCASE(HashStructure *T, void *ptr, int traverserID, SESEcommon * task, void *heaproot) { +int rcr_READBINCASE(HashStructure *T, void *ptr, SESEcommon * task, int index) { BinItem_rcr * val; int key=rcr_generateKey(ptr); BinElement_rcr * be = &(T->array[key]); @@ -138,15 +150,11 @@ int rcr_READBINCASE(HashStructure *T, void *ptr, int traverserID, SESEcommon * t ReadBinItem_rcr* readbin=(ReadBinItem_rcr*)b; TraverserData * td = &(readbin->array[readbin->index++]); b->total=1; - b->status = READY; + b->status=READY; //common to both types - td->binitem = b; - td->hashtable=T; - td->resumePtr = ptr; - td->task= task; - td->traverserID = traverserID; - td->heaproot = heaproot; + td->task=task; + td->bitindex=1<tail=b; //release lock @@ -159,32 +167,49 @@ int rcr_READBINCASE(HashStructure *T, void *ptr, int traverserID, SESEcommon * t BinItem_rcr * bintail=be->tail; //check if already added item or not. - if (bintail->type == WRITEBIN) { - TraverserData * td = &(((WriteBinItem_rcr *)bintail)->val); - if(unlikely(td->resumePtr == ptr) && td->traverserID == traverserID) { + if (ISWRITEBIN(bintail->type)) { + WriteBinItem_rcr td = (WriteBinItem_rcr *)bintail; + if(unlikely(td->task==task)) { //RELEASE LOCK + bitv bit=1<status; + if (!(td->bitindexrd & bit)) { + td->bitindexrd|=bit; + td->bitindexwr|=bit; + if (status==NOTREADY) + status=SNOTREADY; + } else + status=READY; be->head=val; - return bintail->status; + return status; } - } else if (bintail->type == READEFFECT) { + } else { TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1]; - if (unlikely(td->resumePtr == ptr) && td->traverserID == traverserID) { + if (unlikely(td->task==task)) { //RELEASE LOCK + bitv bit=1<status; + if (!(td->bitindex & bit)) { + td->bitindex|=bit; + if (status==NOTREADY) + status=SNOTREADY; + } else + status=READY; be->head=val; - return bintail->status; + return status; } } - if (isReadBinItem(bintail)) { - return rcr_TAILREADCASE(T, ptr, val, bintail, key, traverserID, task, heaproot); - } else if (!isReadBinItem(bintail)) { - rcr_TAILWRITECASE(T, ptr, val, bintail, key, traverserID, task, heaproot); + if (ISREADBIN(bintail->type)) { + return rcr_TAILREADCASE(T, ptr, val, bintail, key, task, index); + } else { + rcr_TAILWRITECASE(T, ptr, val, bintail, key, task, index); return NOTREADY; } } -int rcr_TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, int traverserID, SESEcommon * task, void *heaproot) { +int rcr_TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index) { ReadBinItem_rcr * readbintail=(ReadBinItem_rcr*)T->array[key].tail; int status, retval; TraverserData *td; @@ -207,172 +232,92 @@ int rcr_TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *val, BinItem_rcr } else { // group into old tail td = &readbintail->array[readbintail->index++]; atomic_inc(&readbintail->item.total); - //printf("grouping with %d\n",readbintail->index); } - td->binitem = bintail; - td->hashtable=T; - td->resumePtr = ptr; - td->task= task; - td->traverserID = traverserID; - td->heaproot = heaproot; + td->task=task; + td->bitindex=1<array[key].head=val;//released lock return retval; } -void rcr_TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, int traverserID, SESEcommon * task, void *heaproot) { +void rcr_TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index) { ReadBinItem_rcr* rb=rcr_createReadBinItem(); TraverserData * td = &(rb->array[rb->index++]); rb->item.total=1; rb->item.status=NOTREADY; td->binitem = (BinItem_rcr *) rb; - td->hashtable=T; - td->resumePtr = ptr; - td->task= task; - td->traverserID = traverserID; - td->heaproot = heaproot; + td->task=task; + td->bitindex=1<array[key].tail->next=(BinItem_rcr*)rb; T->array[key].tail=(BinItem_rcr*)rb; T->array[key].head=val;//released lock } -//TODO write deletion/removal methods - RETIREHASHTABLE(HashStructure *T, SESECommon *task, int key) { - BinItem_rcr *b=T->array[key].head; - if(isFineRead(r)) { + BinElement_rcr * be = &(T->array[key]); + BinItem_rcr *b=be->head; + + if(ISREADBIN(READBIN)) { atomic_dec(&b->total); + if (b->next==NULL || b->total>0) { + return; + } } - if (isFineWrite(r) || (isFineRead(r) && b->next!=NULL && b->total==0)) { + //We either have a write bin or we are at the end of a read bin + + { // CHECK FIRST IF next is nonnull to guarantee that b.total cannot change - BinItem_rcr * val; - do { - val=(BinItem_rcr*)0x1; - val=(BinItem_rcr*)LOCKXCHG((unsigned INTPTR*)&(T->array[key]->head), (unsigned INTPTR)val); + BinItem_rcr * val=(BinItem_rcr *)0x1; + do { + val=(BinItem_rcr*)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val); } while(val==(BinItem_rcr*)0x1); - + // at this point have locked bin BinItem_rcr *ptr=val; int haveread=FALSE; int i; while (ptr!=NULL) { - if (isReadBinItem(ptr)) { - ReadBinItem_rcr* rptr=(ReadBinItem_rcr*)ptr; - if (rptr->item.status==NOTREADY) { - for (i=0;iindex;i++) { - resolveDependencies(rptr->array[i]); - if (isParent(rptr->array[i])) { + if (ISREADBIN(ptr->type)) { + if (ptr->status==NOTREADY) { + ReadBinItem_rcr* rptr=(ReadBinItem_rcr*)ptr; + for (i=0;iindex;i++) { + RESOLVE(rptr->array[i]); + if (((INTPTR)rptr->array[i]->task)&PARENTBIN) { //parents go immediately atomic_dec(&rptr->item.total); - atomic_dec(&T->item.total); } } + ptr->status=READY; } - rptr->item.status=READY; - if (rptr->item.next==NULL) { + if (ptr->next==NULL) { break; } - if (rptr->item.total!=0) { - haveread=TRUE; - } else if ((BinItem_rcr*)rptr==val) { + if (ptr->total!=0) { + haveread=TRUE; + } else if (ptr==val) { val=val->next; } - } else if(isWriteBinItem(ptr)) { - if (haveread) + } else { + //write bin case + if (haveread) break; - if(ptr->status==NOTREADY){ - resolveDependencies(((WriteBinItem_rcr*)ptr)->val); + if(ptr->status==NOTREADY) { + WriteBinItem_rcr* wptr=(WriteBinItem_rcr*)ptr; + RESOLVE(wptr->val); ptr->status=READY; - if(isParent(((WriteBinItem_rcr*)ptr)->val)){ - atomic_dec(&T->item.total); - val=val->next; - }else + if(((INTPTR)wptr->task)&PARENTBIN) { + val=val->next; + } else break; - }else{ // write bin is already resolved + } else { // write bin is already resolved val=val->next; } - } - ptr=ptr->next; - } - T->array[key]->head=val; // release lock - } -} - - -/* -//Int will return success/fail. -1 indicates error (i.e. there's nothing there). -//0 = nothing removed, >0 something was removed -int REMOVETABLEITEM(HashStructure* table, void * ptr, int traverserID, SESEcommon *task, void * heaproot) { - int key = generateKey(ptr); - BinElement_rcr * bucket = table->array[key]; - - if(bucket->head == NULL) { - return -1; - //This can occur if we try to remove something that's in the waitingQueue directly from the hashtable. - } - - if(bucket->head->type == WRITEBIN) { - TraverserData * td = &(((WriteBinItem_rcr *) head)->val); - if(td->resumePtr == ptr && td->traverserID == traverserID && td->heaproot == heaproot) { - BinItem_rcr * temp = bucket->head; - bucket->head = bucket->head->next; - free(temp); //TODO perhaps implement a linked list of free BinElements as was done in WaitingQueue - - //Handle items behind write item - if(bucket->head == NULL) { - bucket->tail == NULL; - return 1; - } - - int type = bucket->head->type; - switch(bucket->head->type) { - case WRITEBIN: - bucket->head->status = READY; - //TODO Decrement dependency count - return 1; - case WAITINGQUEUENOTE: - int retval = removeFromWaitingQueue(table->waitingQueue, ((WaitingQueueNote *) bucket->head)->allocSiteID, traverserID); - if(retval >0) { - //we set both to NULL because the note should ALWAYS be the last item in the hashStructure. - bucket->head = NULL; - bucket->tail = NULL; - } - return retval; - default: - BinItem_rcr * temp = bucket->head; - while(temp != NULL && temp->type == READBIN) { - temp->status = READY; - temp = temp->next; - //TODO decrement dependency count - } - return 1; } - } else { - return 0; - } - } - - if(bucket->head->type == READBIN) { - //TODO There's an issue here; bins are groups of items that may be enqueued by different ids. - //I may have to search through them to find which one to remove but then there'd be a blank spot in an - //otherwise clean array. It wouldn't make sense to just check the first one since reads are reorderable. - //Nor does it make sense to lop off the reads since that may signal the next write to be ready even before it - //really is ready. - } - - if(bucket->head->type == WAITINGQUEUENOTE) { - int retval = removeFromWaitingQueue(table->waitingQueue, ((WaitingQueueNote *) bucket->head)->allocSiteID, traverserID); - if(retval >0) { - bucket->head = NULL; - bucket->tail = NULL; + ptr=ptr->next; } - return retval; + be->head=val; // release lock } - - return -1; } - -*/ diff --git a/Robust/src/Runtime/oooJava/hashStructure.h b/Robust/src/Runtime/oooJava/hashStructure.h index 1bcde9e7..a645502b 100644 --- a/Robust/src/Runtime/oooJava/hashStructure.h +++ b/Robust/src/Runtime/oooJava/hashStructure.h @@ -6,7 +6,7 @@ #define ITEM_NOT_AT_FRONT_OF_WAITINGQ 3 #define TRAVERSER_FINISHED 2 - +#define bitvt unsigned long long //Note READEFFECT = READBIN and WRITEEFFECT=WRITEBIN. They mean the same thing //but are named differently for clarity in code. @@ -16,7 +16,10 @@ #define READBIN 0 #define WRITEBIN 1 +#define BINMASK 1 +#define PARENTBIN 1 +#define SPECNOTREADY 2 #define READY 1 #define NOTREADY 0 @@ -37,54 +40,27 @@ typedef struct BinItem_rcr { struct BinItem_rcr * next; } BinItem_rcr; -typedef struct trackerElement { - BinItem_rcr * item; - struct trackerElement * next; -} TrackerElement; - -typedef struct tracker { - TrackerElement * head; - TrackerElement * tail; -} VariableTracker; - -//TODO more closely tie this in with Jim's stuff -struct genericObjectStruct { - int type; - int oid; - int allocsite; - int ___cachedCode___; - int ___cachedHash___; -}; - - typedef struct BinElement_rcr { BinItem_rcr * head; BinItem_rcr * tail; } BinElement_rcr; - typedef struct Hashtable_rcr { BinElement_rcr array[RNUMBINS]; // WaitingQueueBin * waitingQueue; } HashStructure; //Todo this is a clone of REntry, remove data fields as necessary -typedef struct entry_rcr{ - //fields to handle next item. - struct Hashtable_rcr* hashtable; - BinItem_rcr* binitem; //stores binItem so we can get access to the next ptr in the queue - - //fields to help resume traverser - struct genericObjectStruct * resumePtr; -// int allocsite; //not needed since we can get it form ptr later - int traverserID; +typedef struct Entry_rcr { SESEcommon * task; - struct genericObjectStruct * heaproot; + bitv bitindex; } TraverserData; typedef struct WriteBinItem_rcr { BinItem_rcr item; - TraverserData val; + SESEcommon * task; + bitv bitindexwr; + bitv bitindexrd; } WriteBinItem_rcr; typedef struct ReadBinItem_rcr { @@ -92,14 +68,8 @@ typedef struct ReadBinItem_rcr { TraverserData array[RNUMREAD]; //We don't need a head index since if the item before it was freed, then all these would be considered ready as well. int index; - } ReadBinItem_rcr; -typedef struct WQNote_rcr { - BinItem_rcr item; - int allocSiteID; -} WaitingQueueNote; - extern HashStructure ** allHashStructures; void rcr_createMasterHashTableArray(int maxSize); //temporary @@ -113,10 +83,9 @@ inline int rcr_generateKey(void * ptr); //Method signatures are not in their final form since I have still not decided what is the optimum amount of data //to store in each entry. -int rcr_WRITEBINCASE(HashStructure *T, void *ptr, int traverserID, SESEcommon *task, void *heaproot); -int rcr_READBINCASE(HashStructure *T, void *ptr, int traverserID, SESEcommon * task, void *heaproot); -int rcr_TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, int traverserID, SESEcommon * task, void *heaproot); -void rcr_TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, int traverserID, SESEcommon * task, void *heaproot); -int rcr_REMOVETABLEITEM(HashStructure* table, void * ptr, int traverserID, SESEcommon *task, void * heaproot); +int rcr_WRITEBINCASE(HashStructure *T, void *ptr, SESEcommon *task, void *heaproot); +int rcr_READBINCASE(HashStructure *T, void *ptr, SESEcommon * task, void *heaproot); +int rcr_TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, void *heaproot); +void rcr_TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, void *heaproot); #endif -- 2.34.1