From 7ded17b4d1ebfec7e1b615a3c625f41144f54a79 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Thu, 21 Oct 2010 04:39:03 +0000 Subject: [PATCH] changes --- Robust/src/IR/Flat/BuildCode.java | 2 +- .../src/IR/Flat/RuntimeConflictResolver.java | 55 ++++-- Robust/src/Runtime/mlp_lock.h | 18 +- Robust/src/Runtime/oooJava/hashStructure.c | 25 ++- Robust/src/Runtime/oooJava/hashStructure.h | 186 +++++++++--------- Robust/src/Runtime/oooJava/rcr_runtime.h | 1 + 6 files changed, 159 insertions(+), 128 deletions(-) diff --git a/Robust/src/IR/Flat/BuildCode.java b/Robust/src/IR/Flat/BuildCode.java index d549aa3d..5b30f743 100644 --- a/Robust/src/IR/Flat/BuildCode.java +++ b/Robust/src/IR/Flat/BuildCode.java @@ -3851,7 +3851,7 @@ public class BuildCode { } if (state.RCR&&fsen.getInVarsForDynamicCoarseConflictResolution().size()>0) { - output.println(" seseToIssue->common.offsetToParamRecords=(INTPTR)sizeof("+fsen.getSESErecordName()+") - (INTPTR) & ((("+fsen.getSESErecordName()+"*)0)->rcrRecords);"); + output.println(" seseToIssue->common.offsetToParamRecords=(INTPTR) & ((("+fsen.getSESErecordName()+"*)0)->rcrRecords);"); } // fill in common data diff --git a/Robust/src/IR/Flat/RuntimeConflictResolver.java b/Robust/src/IR/Flat/RuntimeConflictResolver.java index dee52e16..cc839f2f 100644 --- a/Robust/src/IR/Flat/RuntimeConflictResolver.java +++ b/Robust/src/IR/Flat/RuntimeConflictResolver.java @@ -654,23 +654,34 @@ public class RuntimeConflictResolver { } //IMPORTANT: remember to change getTraverserInvocation if you change the line below String methodName; + int index=-1; + if (taint.isStallSiteTaint()) { methodName= "void traverse___" + removeInvalidChars(inVar) + removeInvalidChars(rBlock) + "___(void * InVar, SESEcommon *record)"; } else { methodName= "void traverse___" + removeInvalidChars(inVar) + removeInvalidChars(rBlock) + "___(void * InVar, "+taint.getSESE().getSESErecordName() +" *record)"; + FlatSESEEnterNode fsese=taint.getSESE(); + TempDescriptor tmp=taint.getVar(); + index=fsese.getInVarsForDynamicCoarseConflictResolution().indexOf(tmp); } cFile.println(methodName + " {"); headerFile.println(methodName + ";"); + cFile.println(" int totalcount=RUNBIAS;\n"); + if (taint.isStallSiteTaint()) { + //need to add this + } else { + cFile.println(" record->rcrRecords["+index+"].count=RUNBIAS;\n"); + } if(cSideDebug) { cFile.println("printf(\"The traverser ran for " + methodName + "\\n\");"); } if(cases.size() == 0) { - cFile.println(" return; }"); + cFile.println(" return;"); } else { //clears queue and hashtable that keeps track of where we've been. cFile.println(clearQueue + ";\n" + resetVisitedHashTable + ";"); @@ -684,8 +695,20 @@ public class RuntimeConflictResolver { cFile.append(cases.get(singleCase)); cFile.println(" default:\n break; "); - cFile.println(" }\n } while((ptr = " + dequeueFromQueueInC + ") != NULL);\n}\n}\n"); + cFile.println(" }\n } while((ptr = " + dequeueFromQueueInC + ") != NULL);\n}"); } + if (taint.isStallSiteTaint()) { + //need to add this + } else { + cFile.println(" if(atomic_sub_and_test(RUNBIAS-totalcount,&(record->rcrRecords["+index+"].count))) {"); + cFile.println(" int flag=LOCKXCHG(&(record->rcrRecords["+index+"].flag),0);"); + cFile.println(" if(flag) {"); + //we have resolved a heap root...see if this was the last dependence + cFile.println(" if(atomic_sub_and_test(1, &(record->common.unresolvedDependencies))) workScheduleSubmit((void *)record);"); + cFile.println(" }"); + cFile.println("}"); + } + cFile.println("}"); cFile.flush(); } @@ -729,13 +752,6 @@ public class RuntimeConflictResolver { objConfRead|=effect.hasReadConflict; objConfWrite|=effect.hasWriteConflict; } - currCase.append(" int tmpvar;"); - - if (objConfRead) { - currCase.append(" if("); - checkWaitingQueue(currCase, taint, node); - currCase.append("||!"); - } int index=-1; if (taint.isRBlockTaint()) { @@ -750,24 +766,23 @@ public class RuntimeConflictResolver { assert heaprootNum != -1; int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node); int traverserID = doneTaints.get(taint); - currCase.append(" (tmpvar=rcr_WRITEBINCASE(allHashStructures["+heaprootNum+"],"+prefix+", (SESEcommon *) record, "+index+"))"); + if (objConfRead) + currCase.append(" int tmpvar=rcr_WTWRITEBINCASE(allHashStructures["+heaprootNum+"],"+prefix+", (SESEcommon *) record, "+index+");\n"); + else + currCase.append(" int tmpvar=rcr_WRITEBINCASE(allHashStructures["+heaprootNum+"],"+prefix+", (SESEcommon *) record, "+index+");\n"); } else if (primConfRead||objConfRead) { int heaprootNum = connectedHRHash.get(taint).id; assert heaprootNum != -1; int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node); int traverserID = doneTaints.get(taint); - currCase.append(" (tmpvar=rcr_READBINCASE(allHashStructures["+heaprootNum+"],"+prefix+", (SESEcommon *) record, "+index+"))"); - } - - if(objConfRead) { - currCase.append("&READYMASK) {\n"); - putIntoWaitingQueue(currCase, taint, node, prefix); - currCase.append(" break;\n"); - currCase.append(" }\n"); - } else if(primConfRead||primConfWrite||objConfWrite) { - currCase.append(";\n"); + if (objConfRead) + currCase.append(" int tmpvar=rcr_WTREADBINCASE(allHashStructures["+heaprootNum+"],"+prefix+", (SESEcommon *) record, "+index+");\n"); + else + currCase.append(" int tmpvar=rcr_READBINCASE(allHashStructures["+heaprootNum+"],"+prefix+", (SESEcommon *) record, "+index+");\n"); } + currCase.append("if (!(tmpvar&READYMASK)) totalcount--;\n"); + currCase.append("if (!(tmpvar&SPEC)) ; //add record\n"); //Conflicts diff --git a/Robust/src/Runtime/mlp_lock.h b/Robust/src/Runtime/mlp_lock.h index 3eb341ea..c5f6ac0b 100644 --- a/Robust/src/Runtime/mlp_lock.h +++ b/Robust/src/Runtime/mlp_lock.h @@ -43,28 +43,30 @@ static inline int atomic_sub_and_test(int i, volatile int *v) { return c; } -#ifdef BIT64 -static inline INTPTR LOCKXCHG(volatile INTPTR * ptr, INTPTR val){ - INTPTR retval; +static inline int LOCKXCHG32(volatile int* ptr, int val){ + int retval; //note: xchgl always implies lock - __asm__ __volatile__("xchgq %0,%1" + __asm__ __volatile__("xchgl %0,%1" : "=r"(retval) : "m"(*ptr), "0"(val) : "memory"); return retval; } -#else -static inline int LOCKXCHG(volatile int* ptr, int val){ - int retval; + +#ifdef BIT64 +static inline INTPTR LOCKXCHG(volatile INTPTR * ptr, INTPTR val){ + INTPTR retval; //note: xchgl always implies lock - __asm__ __volatile__("xchgl %0,%1" + __asm__ __volatile__("xchgq %0,%1" : "=r"(retval) : "m"(*ptr), "0"(val) : "memory"); return retval; } +#else +#define LOCKXCHG LOCKXCHG32 #endif /* diff --git a/Robust/src/Runtime/oooJava/hashStructure.c b/Robust/src/Runtime/oooJava/hashStructure.c index b66ca0f1..0eb089f8 100644 --- a/Robust/src/Runtime/oooJava/hashStructure.c +++ b/Robust/src/Runtime/oooJava/hashStructure.c @@ -47,7 +47,6 @@ inline int rcr_generateKey(void * ptr){ } //consider SPEC flag - 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 @@ -261,7 +260,7 @@ void rcr_TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *val, BinItem_rc T->array[key].head=val;//released lock } -rcr_RETIREHASHTABLE(HashStructure *T, SESEcommon *task, int key) { +void rcr_RETIREHASHTABLE(HashStructure *T, SESEcommon *task, int key) { BinElement_rcr * be = &(T->array[key]); BinItem_rcr *b=be->head; @@ -289,7 +288,8 @@ rcr_RETIREHASHTABLE(HashStructure *T, SESEcommon *task, int key) { if (ptr->status==NOTREADY) { ReadBinItem_rcr* rptr=(ReadBinItem_rcr*)ptr; for (i=0;iindex;i++) { - RESOLVE(rptr->array[i]); + TaskDescriptor * td=&rptr->array[i]; + RESOLVE(td->task, td->bitindex); if (((INTPTR)rptr->array[i].task)&PARENTBIN) { //parents go immediately atomic_dec(&rptr->item.total); @@ -311,7 +311,7 @@ rcr_RETIREHASHTABLE(HashStructure *T, SESEcommon *task, int key) { break; if(ptr->status==NOTREADY) { WriteBinItem_rcr* wptr=(WriteBinItem_rcr*)ptr; - RESOLVE(wptr); + RESOLVE(wptr->task, wptr->bitindexwr); ptr->status=READY; if(((INTPTR)wptr->task)&PARENTBIN) { val=val->next; @@ -326,3 +326,20 @@ rcr_RETIREHASHTABLE(HashStructure *T, SESEcommon *task, int key) { be->head=val; // release lock } } + +void RESOLVE(SESEcommon *record, bitvt mask) { + int index=-1; + struct rcrRecord * array=(struct rcrRecord *)(((char *)record)+record->common.offsetToParamRecords); + while(mask!=0) { + int shift=__builtin_ctzll(mask)+1; + index+=shift; + if (atomic_sub_and_test(1,&array[index].count)) { + inf flag=LOCKXCHG(&array[index].flag,0); + if (flag) { + if(atomic_sub_and_test(1, &(record->common.unresolvedDependencies))) + workScheduleSubmit((void *)record); + } + } + mask=mask>>shift; + } +} diff --git a/Robust/src/Runtime/oooJava/hashStructure.h b/Robust/src/Runtime/oooJava/hashStructure.h index 65dd9a42..479a6276 100644 --- a/Robust/src/Runtime/oooJava/hashStructure.h +++ b/Robust/src/Runtime/oooJava/hashStructure.h @@ -1,95 +1,91 @@ -#ifndef HASHSTRUCTURE_H_ -#define HASHSTRUCTURE_H_ - -#include "mlp_runtime.h" -//#include "WaitingQueue.h" - -#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. -#define READEFFECT 0 -#define WRITEEFFECT 1 -#define WAITINGQUEUENOTE 2 - -#define READBIN 0 -#define WRITEBIN 1 -#define BINMASK 1 -#define PARENTBIN 1 - -#define SPEC 2 -#define READY 1 //Item is ready and we haven't seen this bin before -#define NOTREADY 0 //Item is not ready and we haven't seen this bin before -#define SPECREADY (SPEC|READY) //Item is ready and we've seen this bin before -#define SPECNOTREADY (SPEC|NOTREADY) //Item is not ready and we've seen this bin before -#define READYMASK 1 - - -#define TRUE 1 -#define FALSE 0 - -#define RNUMBINS 64 -#define RNUMREAD 64 -#define RNUMRENTRY 256 -#define RH_MASK (RNUMBINS)-1 - -//Note: put resolved things at the end and unresolved at the front. -typedef struct BinItem_rcr { - int total; - int status; - int type; - //TODO keep track of record ptr here - struct BinItem_rcr * next; -} BinItem_rcr; - -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 { - SESEcommon * task; - bitvt bitindex; -} TraverserData; - -typedef struct WriteBinItem_rcr { - BinItem_rcr item; - SESEcommon * task; - bitvt bitindexwr; - bitvt bitindexrd; -} WriteBinItem_rcr; - -typedef struct ReadBinItem_rcr { - BinItem_rcr item; - 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; - -extern HashStructure ** allHashStructures; - -void rcr_createMasterHashTableArray(int maxSize); //temporary -HashStructure* rcr_createHashtable(int sizeofWaitingQueue); -WriteBinItem_rcr* rcr_createWriteBinItem(); -ReadBinItem_rcr* rcr_createReadBinItem(); -int rcr_isReadBinItem(BinItem_rcr* b); -int rcr_isWriteBinItem(BinItem_rcr* b); -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, SESEcommon *task, int index); -int rcr_READBINCASE(HashStructure *T, void *ptr, SESEcommon * task, int index); -int rcr_TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index); -void rcr_TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index); - -#endif +#ifndef HASHSTRUCTURE_H_ +#define HASHSTRUCTURE_H_ + +#include "mlp_runtime.h" +//#include "WaitingQueue.h" + +#define bitvt unsigned long long + +//Note READEFFECT = READBIN and WRITEEFFECT=WRITEBIN. They mean the same thing +//but are named differently for clarity in code. +#define READEFFECT 0 +#define WRITEEFFECT 1 +#define WAITINGQUEUENOTE 2 + +#define READBIN 0 +#define WRITEBIN 1 +#define BINMASK 1 +#define PARENTBIN 1 + +#define SPEC 2 +#define READY 1 //Item is ready and we haven't seen this bin before +#define NOTREADY 0 //Item is not ready and we haven't seen this bin before +#define SPECREADY (SPEC|READY) //Item is ready and we've seen this bin before +#define SPECNOTREADY (SPEC|NOTREADY) //Item is not ready and we've seen this bin before +#define READYMASK 1 + + +#define TRUE 1 +#define FALSE 0 + +#define RNUMBINS 64 +#define RNUMREAD 64 +#define RNUMRENTRY 256 +#define RH_MASK (RNUMBINS)-1 + +//Note: put resolved things at the end and unresolved at the front. +typedef struct BinItem_rcr { + int total; + int status; + int type; + //TODO keep track of record ptr here + struct BinItem_rcr * next; +} BinItem_rcr; + +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 { + SESEcommon * task; + bitvt bitindex; +} TraverserData; + +typedef struct WriteBinItem_rcr { + BinItem_rcr item; + SESEcommon * task; + bitvt bitindexwr; + bitvt bitindexrd; +} WriteBinItem_rcr; + +typedef struct ReadBinItem_rcr { + BinItem_rcr item; + 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; + +extern HashStructure ** allHashStructures; + +void rcr_createMasterHashTableArray(int maxSize); //temporary +HashStructure* rcr_createHashtable(int sizeofWaitingQueue); +WriteBinItem_rcr* rcr_createWriteBinItem(); +ReadBinItem_rcr* rcr_createReadBinItem(); +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, SESEcommon *task, int index); +int rcr_READBINCASE(HashStructure *T, void *ptr, SESEcommon * task, int index); +int rcr_TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index); +void rcr_TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index); + +#endif diff --git a/Robust/src/Runtime/oooJava/rcr_runtime.h b/Robust/src/Runtime/oooJava/rcr_runtime.h index e7c188d6..f5ef312f 100644 --- a/Robust/src/Runtime/oooJava/rcr_runtime.h +++ b/Robust/src/Runtime/oooJava/rcr_runtime.h @@ -6,6 +6,7 @@ extern __thread struct trQueue * TRqueue; void * workerTR(void *); #define RCRSIZE 32 +#define RUNBIAS 1000000 struct rcrRecord { int count; -- 2.34.1