From 772a54057836f99d94f528d77e8f446d7af2226e Mon Sep 17 00:00:00 2001 From: bdemsky Date: Sun, 24 Oct 2010 08:36:22 +0000 Subject: [PATCH] changes...handle races between coarse and fine grained conflict resolution --- Robust/src/IR/Flat/BuildCode.java | 43 ++++--- .../src/IR/Flat/RuntimeConflictResolver.java | 38 +++---- Robust/src/Runtime/mlp_runtime.h | 3 +- Robust/src/Runtime/oooJava/hashStructure.c | 107 +++++++++++------- Robust/src/Runtime/oooJava/hashStructure.h | 16 +-- Robust/src/Runtime/oooJava/rcr_runtime.h | 1 + 6 files changed, 119 insertions(+), 89 deletions(-) diff --git a/Robust/src/IR/Flat/BuildCode.java b/Robust/src/IR/Flat/BuildCode.java index 113b0ec9..e047e48a 100644 --- a/Robust/src/IR/Flat/BuildCode.java +++ b/Robust/src/IR/Flat/BuildCode.java @@ -3285,7 +3285,7 @@ public class BuildCode { if(state.RCR) { //no need to enqueue parent effect if coarse grained conflict clears us output.println(" while(stallrecord.common.rcrstatus) ;"); - output.println(" BARRIER();"); + output.println(" BARRIER();"); output.println(" stallrecord.common.parentsStallSem=&rentry->parentStallSem;"); output.println(" stallrecord.tag=rentry->tag;"); output.println(" stallrecord.___obj___=(struct ___Object___ *)"+generateTemp(fm, waitingElement.getTempDesc(), null)+";"); @@ -3940,6 +3940,11 @@ public class BuildCode { output.println(" struct garbagelist * gl= (struct garbagelist *)&(((SESEcommon*)(seseToIssue))[1]);"); output.println(" gl->size="+calculateSizeOfSESEParamList(fsen)+";"); output.println(" gl->next = NULL;"); + + if(state.RCR) { + //flag the SESE status as 1...it will be reset + output.println(" seseToIssue->rcrstatus=1;"); + } // there are pointers to SESE records the newly-issued SESE // will use to get values it depends on them for--how many @@ -4564,24 +4569,30 @@ public class BuildCode { // eom // clean up its lock element from waiting queue, and decrement dependency count for next SESE block - if( (state.MLP && fsen != mlpa.getMainSESE()) || - (state.OOOJAVA && fsen != oooa.getMainSESE()) - ) { - - output.println(); - output.println(" /* check memory dependency*/"); - output.println(" {"); - output.println(" int idx;"); - output.println(" for(idx=0;idx<___params___->common.rentryIdx;idx++){"); - output.println(" REntry* re=___params___->common.rentryArray[idx];"); - output.println(" RETIRERENTRY(re->queue,re);"); - output.println(" }"); - output.println(" }"); - + if((state.MLP && fsen != mlpa.getMainSESE()) || + (state.OOOJAVA && fsen != oooa.getMainSESE())) { + output.println(); + output.println(" /* check memory dependency*/"); + output.println(" {"); + output.println(" int idx;"); + output.println(" for(idx=0;idx<___params___->common.rentryIdx;idx++){"); + output.println(" REntry* re=___params___->common.rentryArray[idx];"); + output.println(" RETIRERENTRY(re->queue,re);"); + output.println(" }"); + output.println(" }"); } if (state.RCR&&fsen.getDynamicInVarSet().size()>0) { + /* Make sure the running SESE is finished */ + output.println(" if (unlikely(runningSESE->rcrstatus!=0)) {"); + output.println(" if(!CAS(&runningSESE->rcrstatus,1,0)) {"); + output.println(" while(runningSESE->rcrstatus) {"); + output.println(" BARRIER();"); + output.println(" sched_yield();"); + output.println(" }"); + output.println(" }"); + output.println(" }"); output.println("{"); output.println(" int idx,idx2;"); if (fsen.getDynamicInVarSet().size()==1) { @@ -4592,7 +4603,7 @@ public class BuildCode { output.println(" struct rcrRecord *rec="+paramsprefix+"->rcrRecords[idx];"); output.println(" while(rec!=NULL) {"); output.println(" for(idx2=0;idx2index;idx2++) {"); - output.println(" rcr_RETIREHASHTABLE(allHashStructures[0],rec,rec->array[idx2]);"); + output.println(" rcr_RETIREHASHTABLE(allHashStructures[0],rec,rec->array[idx2], rcr->ptrarray[idx2]);"); output.println(" }");//exit idx2 for loop output.println(" rec=rec->next;"); output.println(" }");//exit rec while loop diff --git a/Robust/src/IR/Flat/RuntimeConflictResolver.java b/Robust/src/IR/Flat/RuntimeConflictResolver.java index 24428558..bf2da26c 100644 --- a/Robust/src/IR/Flat/RuntimeConflictResolver.java +++ b/Robust/src/IR/Flat/RuntimeConflictResolver.java @@ -395,6 +395,7 @@ public class RuntimeConflictResolver { private void printMasterTraverserInvocation() { headerFile.println("\nint tasktraverse(SESEcommon * record);"); cFile.println("\nint tasktraverse(SESEcommon * record) {"); + cFile.println(" if(!CAS(&record->rcrstatus,1,2)) return;"); cFile.println(" switch(record->classID) {"); for(Iterator seseit=oooa.getAllSESEs().iterator();seseit.hasNext();) { @@ -721,7 +722,12 @@ public class RuntimeConflictResolver { //Casts the ptr to a generic object struct so we can get to the ptr->allocsite field. cFile.println("struct ___Object___ * ptr = (struct ___Object___ *) InVar;\nif (InVar != NULL) {\n " + queryVistedHashtable + "(ptr);\n do {"); - + if (taint.isRBlockTaint()) { + cFile.println(" if(unlikely(record->doneExecuting)) {"); + cFile.println(" record->rcrstatus=0;"); + cFile.println(" return;"); + cFile.println(" }"); + } cFile.println(" switch(ptr->allocsite) {"); for(AllocSite singleCase: cases.keySet()) @@ -744,7 +750,8 @@ public class RuntimeConflictResolver { //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.println(" record->common.rcrstatus=0;"); } } cFile.println("}"); @@ -801,6 +808,8 @@ public class RuntimeConflictResolver { index=fsese.getInVarsForDynamicCoarseConflictResolution().indexOf(tmp); } + String strrcr=taint.isRBlockTaint()?"&record->rcrRecords["+index+"], ":"NULL, "; + //Do call if we need it. if(primConfWrite||objConfWrite) { int heaprootNum = connectedHRHash.get(taint).id; @@ -809,9 +818,9 @@ public class RuntimeConflictResolver { int traverserID = doneTaints.get(taint); currCase.append(" int tmpkey"+depth+"=rcr_generateKey("+prefix+");\n"); if (objConfRead) - currCase.append(" int tmpvar"+depth+"=rcr_WTWRITEBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+index+");\n"); + currCase.append(" int tmpvar"+depth+"=rcr_WTWRITEBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+strrcr+index+");\n"); else - currCase.append(" int tmpvar"+depth+"=rcr_WRITEBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+index+");\n"); + currCase.append(" int tmpvar"+depth+"=rcr_WRITEBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+strrcr+index+");\n"); } else if (primConfRead||objConfRead) { int heaprootNum = connectedHRHash.get(taint).id; assert heaprootNum != -1; @@ -819,30 +828,13 @@ public class RuntimeConflictResolver { int traverserID = doneTaints.get(taint); currCase.append(" int tmpkey"+depth+"=rcr_generateKey("+prefix+");\n"); if (objConfRead) - currCase.append(" int tmpvar"+depth+"=rcr_WTREADBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+index+");\n"); + currCase.append(" int tmpvar"+depth+"=rcr_WTREADBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+strrcr+index+");\n"); else - currCase.append(" int tmpvar"+depth+"=rcr_READBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+index+");\n"); + currCase.append(" int tmpvar"+depth+"=rcr_READBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+strrcr+index+");\n"); } if(primConfWrite||objConfWrite||primConfRead||objConfRead) { currCase.append("if (!(tmpvar"+depth+"&READYMASK)) totalcount--;\n"); - currCase.append("if (!(tmpvar"+depth+"&SPEC)) {\n"); - if (taint.isStallSiteTaint()) { - currCase.append(" struct rcrRecord * rcrrec=&record->rcrRecords["+index+"];\n"); - currCase.append(" struct rcrRecord * tmprec;\n"); - currCase.append(" if(likely(rcrrec->indexarray[rcrrec->index++]=tmpkey"+depth+";\n"); - currCase.append("} else if(likely((tmprec=rcrrec->next)!=NULL)&&likely(tmprec->indexarray[tmprec->index++]=tmpkey"+depth+";\n"); - currCase.append("} else {\n"); - currCase.append(" struct rcrRecord *trec=RUNMALLOC(sizeof(struct rcrRecord));"); - currCase.append(" trec->array[0]=tmpkey"+depth+";\n"); - currCase.append(" trec->index=1;\n"); - currCase.append(" trec->next=tmprec;\n"); - currCase.append(" rcrrec->next=trec;\n"); - currCase.append("}\n"); - } - currCase.append("}\n"); } int pdepth=depth+1; diff --git a/Robust/src/Runtime/mlp_runtime.h b/Robust/src/Runtime/mlp_runtime.h index ffd4548a..6a79d80d 100644 --- a/Robust/src/Runtime/mlp_runtime.h +++ b/Robust/src/Runtime/mlp_runtime.h @@ -103,7 +103,7 @@ typedef struct SESEcommon_t { volatile int unresolvedDependencies; pthread_cond_t doneCond; - int doneExecuting; + volatile int doneExecuting; pthread_cond_t runningChildrenCond; int numRunningChildren; @@ -122,6 +122,7 @@ typedef struct SESEcommon_t { #ifdef RCR int offsetToParamRecords; volatile int rcrstatus; + volatile int retired; #endif // for determining when task records can be returned diff --git a/Robust/src/Runtime/oooJava/hashStructure.c b/Robust/src/Runtime/oooJava/hashStructure.c index 55d6af0d..2c8922e9 100644 --- a/Robust/src/Runtime/oooJava/hashStructure.c +++ b/Robust/src/Runtime/oooJava/hashStructure.c @@ -14,6 +14,28 @@ HashStructure ** allHashStructures; //__builtin_popcountll +inline enqueuerecord(struct rcrRecord *rcrrec, int tmpkey, BinItem_rcr *item) { + if (likely(rcrrec!=NULL)) { + struct rcrRecord * tmprec; + if(likely(rcrrec->indexindex++; + rcrrec->ptrarray[index]=item; + rcrrec->array[index]=tmpkey; + } else if(likely((tmprec=rcrrec->next)!=NULL)&&likely(tmprec->indexindex++; + tmprec->ptrarray[index]=item; + tmprec->array[index]=tmpkey; + } else { + struct rcrRecord *trec=RUNMALLOC(sizeof(struct rcrRecord)); + trec->ptrarray[0]=item; + trec->array[0]=tmpkey; + trec->index=1; + trec->next=tmprec; + rcrrec->next=trec; + } + } +} + //NOTE: only temporary void rcr_createMasterHashTableArray(int maxSize){ } @@ -46,7 +68,7 @@ inline int rcr_generateKey(void * ptr){ return (((struct ___Object___ *) ptr)->oid)&RH_MASK; } -inline int rcr_BWRITEBINCASE(HashStructure *T, int key, SESEcommon *task, int index, int mode) { +inline int rcr_BWRITEBINCASE(HashStructure *T, int key, SESEcommon *task, struct rcrRecord *rcrrec, int index, int mode) { //chain of bins exists => tail is valid //if there is something in front of us, then we are not ready BinItem_rcr * val; @@ -71,6 +93,7 @@ inline int rcr_BWRITEBINCASE(HashStructure *T, int key, SESEcommon *task, int in //release lock be->head=b; + enqueuerecord(rcrrec, key, b); return READY; } @@ -92,13 +115,13 @@ inline int rcr_BWRITEBINCASE(HashStructure *T, int key, SESEcommon *task, int in while(bintail->status!=READY) { BARRIER(); } - return SPECREADY; + return READY; } else { - return (bintail->status==READY)?SPECREADY:SPECNOTREADY; + return bintail->status; } } else { be->head=val; - return SPECREADY; + return READY; } } } else { @@ -135,10 +158,12 @@ inline int rcr_BWRITEBINCASE(HashStructure *T, int key, SESEcommon *task, int in if (val==((BinItem_rcr *)b)) { b->item.status=READY; be->head=val; - if (status&SPEC) - return SPECREADY; - else + if (status&SPEC) { + return READY; + } else { + enqueuerecord(rcrrec, key, b); return READY; + } } val=val->next; } @@ -150,13 +175,15 @@ inline int rcr_BWRITEBINCASE(HashStructure *T, int key, SESEcommon *task, int in while(b->item.status==NOTREADY) { BARRIER(); } - return status&SPEC; + return status&READY; } else { - return status; + if (!(status&SPEC)) + enqueuerecord(rcrrec, key, b); + return status&READY; } } -inline int rcr_BREADBINCASE(HashStructure *T, int key, SESEcommon *task, int index, int mode) { +inline int rcr_BREADBINCASE(HashStructure *T, int key, SESEcommon *task, struct rcrRecord *rcrrec, int index, int mode) { BinItem_rcr * val; BinElement_rcr * be = &(T->array[key]); @@ -180,7 +207,7 @@ inline int rcr_BREADBINCASE(HashStructure *T, int key, SESEcommon *task, int ind //release lock be->head=b; - + enqueuerecord(rcrrec, key, b); return READY; } @@ -197,19 +224,17 @@ inline int rcr_BREADBINCASE(HashStructure *T, int key, SESEcommon *task, int ind if (!(td->bitindexrd & bit)) { td->bitindexrd|=bit; td->bitindexwr|=bit; - status=status|SPEC; } else - status=SPECREADY; + status=READY; be->head=val; if (mode) { while(bintail->status!=READY) { BARRIER(); } - return SPECREADY; + return READY; } else { return status; } - } } else { TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1]; if (unlikely(td->task==task)) { @@ -218,23 +243,20 @@ inline int rcr_BREADBINCASE(HashStructure *T, int key, SESEcommon *task, int ind int status=bintail->status; if (!(td->bitindex & bit)) { td->bitindex|=bit; - status=status|SPEC; } else - status=SPECREADY; + status=READY; be->head=val; if (mode) { while(bintail->status!=READY) { BARRIER(); } - return status&SPEC; - } else { - return status; } + return status; } } if (ISREADBIN(bintail->type)) { - int stat=rcr_TAILREADCASE(T, val, bintail, key, task, index); + int stat=rcr_TAILREADCASE(T, val, bintail, key, task, rcrrec, index); if (mode) { struct BinItem_rcr * bt=be->tail; while(bt->status!=READY) { @@ -245,7 +267,7 @@ inline int rcr_BREADBINCASE(HashStructure *T, int key, SESEcommon *task, int ind return stat; } } else { - rcr_TAILWRITECASE(T, val, bintail, key, task, index); + rcr_TAILWRITECASE(T, val, bintail, key, task, rcrrec, index); if (mode) { struct BinItem_rcr * bt=be->tail; while(bt->status!=READY) { @@ -259,22 +281,22 @@ inline int rcr_BREADBINCASE(HashStructure *T, int key, SESEcommon *task, int ind } -int rcr_WRITEBINCASE(HashStructure *T, int key, SESEcommon *task, int index) { - return rcr_BWRITEBINCASE(T, key, task, index, 0); +int rcr_WRITEBINCASE(HashStructure *T, int key, SESEcommon *task, struct rcrRecord *rcrrec, int index) { + return rcr_BWRITEBINCASE(T, key, task, rcrrec, index, 0); } -int rcr_READBINCASE(HashStructure *T, int key, SESEcommon * task, int index) { - return rcr_BREADBINCASE(T, key, task, index, 0); +int rcr_READBINCASE(HashStructure *T, int key, SESEcommon * task, struct rcrRecord *rcrrec, int index) { + return rcr_BREADBINCASE(T, key, task, rcrrec, index, 0); } -int rcr_WTWRITEBINCASE(HashStructure *T, int key, SESEcommon *task, int index) { - return rcr_BWRITEBINCASE(T, key, task, index, 1); +int rcr_WTWRITEBINCASE(HashStructure *T, int key, SESEcommon *task, struct rcrRecord *rcrrec, int index) { + return rcr_BWRITEBINCASE(T, key, task, rcrrec, index, 1); } -int rcr_WTREADBINCASE(HashStructure *T, int key, SESEcommon * task, int index) { - return rcr_BREADBINCASE(T, key, task, index, 1); +int rcr_WTREADBINCASE(HashStructure *T, int key, SESEcommon * task, struct rcrRecord *rcrrec, int index) { + return rcr_BREADBINCASE(T, key, task, rcrrec, index, 1); } -int rcr_TAILREADCASE(HashStructure *T, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index) { + int rcr_TAILREADCASE(HashStructure *T, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, struct rcrRecord * rcrrec, int index) { ReadBinItem_rcr * readbintail=(ReadBinItem_rcr*)T->array[key].tail; int status, retval; TraverserData *td; @@ -294,9 +316,11 @@ int rcr_TAILREADCASE(HashStructure *T, BinItem_rcr *val, BinItem_rcr *bintail, i rb->item.status=status; T->array[key].tail->next=(BinItem_rcr*)rb; T->array[key].tail=(BinItem_rcr*)rb; + enqueuerecord(rcrrec, key, rb); } else { // group into old tail td = &readbintail->array[readbintail->index++]; atomic_inc(&readbintail->item.total); + enqueuerecord(rcrrec, key, readbintail); } td->task=task; @@ -306,7 +330,7 @@ int rcr_TAILREADCASE(HashStructure *T, BinItem_rcr *val, BinItem_rcr *bintail, i return retval; } -void rcr_TAILWRITECASE(HashStructure *T, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index) { +void rcr_TAILWRITECASE(HashStructure *T, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, struct rcrRecord *rcrrec, int index) { ReadBinItem_rcr* rb=rcr_createReadBinItem(); TraverserData * td = &(rb->array[rb->index++]); rb->item.total=1; @@ -314,24 +338,23 @@ void rcr_TAILWRITECASE(HashStructure *T, BinItem_rcr *val, BinItem_rcr *bintail, 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 } -void rcr_RETIREHASHTABLE(HashStructure *T, SESEcommon *task, int key) { - BinElement_rcr * be = &(T->array[key]); - BinItem_rcr *b=be->head; - - if(ISREADBIN(READBIN)) { - atomic_dec(&b->total); +void rcr_RETIREHASHTABLE(HashStructure *T, SESEcommon *task, int key, BinItem_rcr *b) { + atomic_dec(&b->total); + if(ISREADBIN(b->type)) { if (b->next==NULL || b->total>0) { return; } } - //We either have a write bin or we are at the end of a read bin + //We either have a write bin or we are at the end of a read bin + BinElement_rcr * be = &(T->array[key]); { // CHECK FIRST IF next is nonnull to guarantee that b.total cannot change BinItem_rcr * val=(BinItem_rcr *)0x1; @@ -368,6 +391,10 @@ void rcr_RETIREHASHTABLE(HashStructure *T, SESEcommon *task, int key) { } else if (ptr==val) { val=val->next; } + } else if (ptr->total==0) { + //skip past retired item + if (ptr==val) + val=val->next; } else { //write bin case if (haveread) @@ -380,8 +407,6 @@ void rcr_RETIREHASHTABLE(HashStructure *T, SESEcommon *task, int key) { val=val->next; } else break; - } else { // write bin is already resolved - val=val->next; } } ptr=ptr->next; diff --git a/Robust/src/Runtime/oooJava/hashStructure.h b/Robust/src/Runtime/oooJava/hashStructure.h index e4136a68..eb47a0cf 100644 --- a/Robust/src/Runtime/oooJava/hashStructure.h +++ b/Robust/src/Runtime/oooJava/hashStructure.h @@ -84,12 +84,12 @@ inline int rcr_generateKey(void * ptr); //to store in each entry. void RESOLVE(SESEcommon *record, bitvt mask); -int rcr_WRITEBINCASE(HashStructure *T, int key, SESEcommon *task, int index); -int rcr_READBINCASE(HashStructure *T, int key, SESEcommon * task, int index); - -int rcr_WTWRITEBINCASE(HashStructure *T, int key, SESEcommon *task, int index); -int rcr_WTREADBINCASE(HashStructure *T, int key, SESEcommon * task, int index); -int rcr_TAILREADCASE(HashStructure *T, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index); -void rcr_TAILWRITECASE(HashStructure *T, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index); - +int rcr_WRITEBINCASE(HashStructure *T, int key, SESEcommon *task, struct rcrRecord *rcrrec, int index); +int rcr_READBINCASE(HashStructure *T, int key, SESEcommon * task, struct rcrRecord *rcrrec, int index); + +int rcr_WTWRITEBINCASE(HashStructure *T, int key, SESEcommon *task, struct rcrRecord *rcrrec, int index); +int rcr_WTREADBINCASE(HashStructure *T, int key, SESEcommon * task, struct rcrRecord *rcrrec, int index); +int rcr_TAILREADCASE(HashStructure *T, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, struct rcrRecord *rcrrec, int index); +void rcr_TAILWRITECASE(HashStructure *T, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, struct rcrRecord *rcrrec, int index); +void rcr_RETIREHASHTABLE(HashStructure *T, SESEcommon *task, int key, BinItem_rcr *b); #endif diff --git a/Robust/src/Runtime/oooJava/rcr_runtime.h b/Robust/src/Runtime/oooJava/rcr_runtime.h index 4f5f9c2a..cc341806 100644 --- a/Robust/src/Runtime/oooJava/rcr_runtime.h +++ b/Robust/src/Runtime/oooJava/rcr_runtime.h @@ -13,6 +13,7 @@ struct rcrRecord { int index; int flag; int array[RCRSIZE]; + BinItem_rcr *ptrarray[RCRSIZE]; struct rcrRecord *next; }; -- 2.34.1