#include "mem.h"
#include "mlp_runtime.h"
#include "workschedule.h"
+#include "methodheaders.h"
-/*
-__thread struct Queue* seseCallStack;
-__thread pthread_once_t mlpOnceObj = PTHREAD_ONCE_INIT;
-void mlpInitOncePerThread() {
- seseCallStack = createQueue();
-}
-*/
-__thread SESEcommon_p seseCaller;
+__thread SESEcommon* runningSESE;
void* mlpAllocSESErecord( int size ) {
return newrec;
}
-
-void mlpFreeSESErecord( void* seseRecord ) {
+void mlpFreeSESErecord( SESEcommon* seseRecord ) {
RUNFREE( seseRecord );
}
return newREntryArray;
}
-REntry* mlpCreateFineREntry(int type, void* seseToIssue, void* dynID){
+REntry* mlpCreateFineREntry(int type, SESEcommon* seseToIssue, void* dynID){
REntry* newREntry=(REntry*)RUNMALLOC(sizeof(REntry));
newREntry->type=type;
newREntry->seseRec=seseToIssue;
- newREntry->dynID=dynID;
+ newREntry->pointer=dynID;
return newREntry;
}
-REntry* mlpCreateREntry(int type, void* seseToIssue){
+REntry* mlpCreateREntry(int type, SESEcommon* seseToIssue){
REntry* newREntry=(REntry*)RUNMALLOC(sizeof(REntry));
newREntry->type=type;
newREntry->seseRec=seseToIssue;
}
int isParent(REntry *r) {
- if (r->type==PARENTREAD || r->type==PARENTWRITE) {
+ if (r->type==PARENTREAD || r->type==PARENTWRITE || r->type==PARENTCOARSE) {
return TRUE;
} else {
return FALSE;
}
int generateKey(unsigned int data){
- return (data&H_MASK)>> 4;
+ return (data&H_MASK);
}
Hashtable* createHashtable(){
newTable->array[i]->head=NULL;
newTable->array[i]->tail=NULL;
}
+ newTable->unresolvedQueue=NULL;
return newTable;
}
//at this point, have table
Hashtable* table=(Hashtable*)q->tail;
+ r->hashtable=table; // set rentry's hashtable
+ if( *(r->pointer)==0 ||
+ ( *(r->pointer)!=0 &&
+ BARRIER() &&
+ table->unresolvedQueue!=NULL
+ )
+ ){
+ struct Queue* val;
+ // grab lock on the queue
+ do {
+ val=(struct Queue*)0x1;
+ val=(struct Queue*)LOCKXCHG((unsigned INTPTR*)&(table->unresolvedQueue), (unsigned INTPTR)val);
+ } while(val==(struct Queue*)0x1);
+ if(val==NULL){
+ //queue is null, first case
+ if(*(r->pointer)!=0){
+ // check whether pointer is already resolved, or not.
+ table->unresolvedQueue=NULL; //released lock;
+ return ADDTABLEITEM(table,r,TRUE);
+ }
+ struct Queue* queue=createQueue();
+ addNewItemBack(queue,r);
+ atomic_inc(&table->item.total);
+ table->unresolvedQueue=queue; // expose new queue
+ }else{
+ // add unresolved rentry at the end of the queue.
+ addNewItemBack(val,r);
+ atomic_inc(&table->item.total);
+ table->unresolvedQueue=val; // released lock
+ }
+ return NOTREADY;
+ }
+ BinItem * val;
+
+ // leave this--its a helpful test when things are going bonkers
+ //if( OBJPTRPTR_2_OBJOID( r->pointer ) == 0 ) {
+ // // we started numbering object ID's at 1, if we try to
+ // // hash a zero oid, something BAD is about to happen!
+ // printf( "Tried to insert invalid object type=%d into mem Q hashtable!\n",
+ // OBJPTRPTR_2_OBJTYPE( r->pointer ) );
+ // exit( -1 );
+ //}
+ int key=generateKey( OBJPTRPTR_2_OBJOID( r->pointer ) );
+ do {
+ val=(BinItem*)0x1;
+ BinElement* bin=table->array[key];
+ val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(bin->head), (unsigned INTPTR)val);//note...talk to me about optimizations here.
+ } while(val==(BinItem*)0x1);
+ //at this point have locked bin
+ if (val==NULL) {
+ return EMPTYBINCASE(table, table->array[key], r, TRUE);
+ } else {
+ if (isFineWrite(r)) {
+ return WRITEBINCASE(table, r, val, key, TRUE);
+ } else if (isFineRead(r)) {
+ return READBINCASE(table, r, val, key, TRUE);
+ }
+ }
+}
+
+int ADDTABLEITEM(Hashtable* table, REntry* r, int inc){
+
BinItem * val;
- int key=generateKey((unsigned int)r->dynID);
+ int key=generateKey( OBJPTRPTR_2_OBJOID( r->pointer ) );
do {
val=(BinItem*)0x1;
BinElement* bin=table->array[key];
- val=(BinItem*)LOCKXCHG((unsigned int*)&(bin->head), (unsigned int)val);//note...talk to me about optimizations here.
+ val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(bin->head), (unsigned INTPTR)val);
} while(val==(BinItem*)0x1);
//at this point have locked bin
if (val==NULL) {
- return EMPTYBINCASE(table, table->array[key], r);
+ return EMPTYBINCASE(table, table->array[key], r, inc);
} else {
if (isFineWrite(r)) {
- return WRITEBINCASE(table, r, val, key);
+ return WRITEBINCASE(table, r, val, key, inc);
} else if (isFineRead(r)) {
- return READBINCASE(table, r, val, key);
+ return READBINCASE(table, r, val, key, inc);
}
}
}
-int EMPTYBINCASE(Hashtable *T, BinElement* be, REntry *r) {
+int EMPTYBINCASE(Hashtable *T, BinElement* be, REntry *r, int inc) {
int retval;
BinItem* b;
if (isFineWrite(r)) {
retval=NOTREADY;
}
- atomic_inc(&T->item.total);
+ if(inc){
+ atomic_inc(&T->item.total);
+ }
r->hashtable=T;
r->binitem=b;
be->tail=b;
return retval;
}
-int WRITEBINCASE(Hashtable *T, REntry *r, BinItem *val, int key) {
+int WRITEBINCASE(Hashtable *T, REntry *r, BinItem *val, int key, int inc) {
//chain of bins exists => tail is valid
//if there is something in front of us, then we are not ready
- int retval;
+ int retval=NOTREADY;
BinElement* be=T->array[key];
BinItem *bintail=be->tail;
b->item.total=1;
// note: If current table clears all dependencies, then write bin is ready
- if (T->item.total==0){
- retval=READY;
- }else{
- retval=NOTREADY;
- }
- b->item.status=retval;
- // b->item.status=NOTREADY;
- atomic_inc(&T->item.total);
+
+ if(inc){
+ atomic_inc(&T->item.total);
+ }
r->hashtable=T;
r->binitem=(BinItem*)b;
be->tail->next=(BinItem*)b;
+ //need to check if we can go...
+ BARRIER();
+ if (T->item.status==READY) {
+ for(;val!=NULL;val=val->next) {
+ if (val==((BinItem *)b)) {
+ //ready to retire
+ retval=READY;
+ if (isParent(r)) {
+ b->item.status=retval;//unsure if really needed at this point..
+ be->head=NULL; // released lock
+ return retval;
+ }
+ break;
+ } else if (val->total!=0) {
+ break;
+ }
+ }
+ }
+
+ b->item.status=retval;
be->tail=(BinItem*)b;
be->head=val;
return retval;
}
-READBINCASE(Hashtable *T, REntry *r, BinItem *val, int key) {
+READBINCASE(Hashtable *T, REntry *r, BinItem *val, int key, int inc) {
BinItem * bintail=T->array[key]->tail;
if (isReadBinItem(bintail)) {
- return TAILREADCASE(T, r, val, bintail, key);
+ return TAILREADCASE(T, r, val, bintail, key, inc);
} else if (!isReadBinItem(bintail)) {
- TAILWRITECASE(T, r, val, bintail, key);
+ TAILWRITECASE(T, r, val, bintail, key, inc);
return NOTREADY;
}
}
-int TAILREADCASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key) {
+int TAILREADCASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key, int inc) {
ReadBinItem * readbintail=(ReadBinItem*)T->array[key]->tail;
int status, retval;
- if (readbintail->item.status=READY) {
+ if (readbintail->item.status==READY) {
status=READY;
retval=READY;
if (isParent(r)) {
readbintail->array[readbintail->index++]=r;
atomic_inc(&readbintail->item.total);
r->binitem=(BinItem*)readbintail;
- //printf("grouping with %d\n",readbintail->index);
}
- atomic_inc(&T->item.total);
+ if(inc){
+ atomic_inc(&T->item.total);
+ }
r->hashtable=T;
T->array[key]->head=val;//released lock
return retval;
}
-TAILWRITECASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key) {
+TAILWRITECASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key, int inc) {
// WriteBinItem* wb=createWriteBinItem();
//wb->val=r;
//wb->item.total=1;//safe because item could not have started
rb->array[rb->index++]=r;
rb->item.total=1;//safe because item could not have started
rb->item.status=NOTREADY;
- atomic_inc(&T->item.total);
+ if(inc){
+ atomic_inc(&T->item.total);
+ }
r->hashtable=T;
r->binitem=(BinItem*)rb;
T->array[key]->tail->next=(BinItem*)rb;
r->vector=V;
if (BARRIER() && V->item.status==READY) {
void* flag=NULL;
- flag=(void*)LOCKXCHG((unsigned int*)&(V->array[index]), (unsigned int)flag);
+ flag=(void*)LOCKXCHG((unsigned INTPTR*)&(V->array[index]), (unsigned INTPTR)flag);
if (flag!=NULL) {
- if (isParent(r)) { //parent's retire immediately
+ if (isParentCoarse(r)) { //parent's retire immediately
atomic_dec(&V->item.total);
+ V->index--;
}
return READY;
} else {
Q->head=(MemoryQueueItem*)S;
}
void* flag=NULL;
- flag=(void*)LOCKXCHG((unsigned int*)&(S->val), (unsigned int)flag);
+ flag=(void*)LOCKXCHG((unsigned INTPTR*)&(S->val), (unsigned INTPTR)flag);
if (flag!=NULL) {
return READY;
} else {
}
RETIREBIN(Hashtable *T, REntry *r, BinItem *b) {
- int key=generateKey((unsigned int)r->dynID);
+ int key=generateKey( OBJPTRPTR_2_OBJOID( r->pointer ) );
if(isFineRead(r)) {
atomic_dec(&b->total);
}
// CHECK FIRST IF next is nonnull to guarantee that b.total cannot change
BinItem * val;
do {
- val=(BinItem*)1;
- val=(BinItem*)LOCKXCHG((unsigned int*)&(T->array[key]->head), (unsigned int)val);
- } while(val==(BinItem*)1);
+ val=(BinItem*)0x1;
+ val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(T->array[key]->head), (unsigned INTPTR)val);
+ } while(val==(BinItem*)0x1);
// at this point have locked bin
BinItem *ptr=val;
int haveread=FALSE;
-
int i;
while (ptr!=NULL) {
- if (isReadBinItem(ptr)) {
+ if (isReadBinItem(ptr)) {
ReadBinItem* rptr=(ReadBinItem*)ptr;
if (rptr->item.status==NOTREADY) {
for (i=0;i<rptr->index;i++) {
break;
}
MemoryQueueItem* nextitem=head->next;
- CAS32((unsigned int*)&(Q->head), (unsigned int)head, (unsigned int)nextitem);
+ CAS((unsigned INTPTR*)&(Q->head), (unsigned INTPTR)head, (unsigned INTPTR)nextitem);
//oldvalue not needed... if we fail we just repeat
}
}
BinItem* val;
do {
val=(BinItem*)1;
- val=(BinItem*)LOCKXCHG((unsigned int*)&(bin->head), (unsigned int)val);
+ val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(bin->head), (unsigned INTPTR)val);
} while (val==(BinItem*)1);
//at this point have locked bin
int haveread=FALSE;
} else if((BinItem*)rptr==val) {
val=val->next;
}
- rptr->item.status=READY; {
- }
- ptr=ptr->next;
+ rptr->item.status=READY;
}
+ ptr=ptr->next;
}while(ptr!=NULL);
}
bin->head=val; // released lock;
//enqueue everything
for (i=0;i<NUMITEMS;i++) {
REntry* val=NULL;
- val=(REntry*)LOCKXCHG((unsigned int*)&(tmp->array[i]), (unsigned int)val);
+ val=(REntry*)LOCKXCHG((unsigned INTPTR*)&(tmp->array[i]), (unsigned INTPTR)val);
if (val!=NULL) {
resolveDependencies(val);
if (isParent(val)) {
RESOLVESCC(SCC *S) {
//precondition: SCC's state is READY
void* flag=NULL;
- flag=(void*)LOCKXCHG((unsigned int*)&(S->val), (unsigned int)flag);
+ flag=(void*)LOCKXCHG((unsigned INTPTR*)&(S->val), (unsigned INTPTR)flag);
if (flag!=NULL) {
resolveDependencies(flag);
}
resolveDependencies(REntry* rentry){
SESEcommon* seseCommon=(SESEcommon*)rentry->seseRec;
- if(rentry->type==READ || rentry->type==WRITE || rentry->type==COARSE || rentry->type==SCCITEM){
+ if(rentry->type==READ || rentry->type==WRITE || rentry->type==COARSE || rentry->type==SCCITEM){
if( atomic_sub_and_test(1, &(seseCommon->unresolvedDependencies)) ){
workScheduleSubmit(seseCommon);
}
psem_give(&(rentry->parentStallSem));
}
}
+
+void INITIALIZEBUF(MemoryQueue * q){
+ int i=0;
+ for(i=0; i<NUMBINS; i++){
+ q->binbuf[i]=NULL;
+ }
+ q->bufcount=0;
+}
+
+void ADDRENTRYTOBUF(MemoryQueue * q, REntry * r){
+ q->buf[q->bufcount]=r;
+ q->bufcount++;
+}
+
+int RESOLVEBUFFORHASHTABLE(MemoryQueue * q, Hashtable* table, SESEcommon *seseCommon){
+ int i;
+ // first phase: only consider write rentry
+ for(i=0; i<q->bufcount;i++){
+ REntry *r=q->buf[i];
+ if(r->type==WRITE){
+ int key=generateKey( OBJPTRPTR_2_OBJOID( r->pointer ) );
+ if(q->binbuf[key]==NULL){
+ // for multiple writes, add only the first write that hashes to the same bin
+ q->binbuf[key]=r;
+ }else{
+ q->buf[i]=NULL;
+ }
+ }
+ }
+ // second phase: enqueue read items if it is eligible
+ for(i=0; i<q->bufcount;i++){
+ REntry *r=q->buf[i];
+ if(r!=NULL && r->type==READ){
+ int key=generateKey( OBJPTRPTR_2_OBJOID( r->pointer ) );
+ if(q->binbuf[key]==NULL){
+ // read item that hashes to the bin which doen't contain any write
+ seseCommon->rentryArray[seseCommon->rentryIdx++]=r;
+ if(ADDTABLEITEM(table, r, FALSE)==READY){
+ resolveDependencies(r);
+ }
+ }
+ q->buf[i]=NULL;
+ }
+ }
+
+ // then, add only one of write items that hashes to the same bin
+ for(i=0; i<q->bufcount;i++){
+ REntry *r=q->buf[i];
+ if(r!=NULL){
+ seseCommon->rentryArray[seseCommon->rentryIdx++]=r;
+ if(ADDTABLEITEM(table, r, FALSE)==READY){
+ resolveDependencies(r);
+ }
+ }
+ }
+}
+
+int RESOLVEBUF(MemoryQueue * q, SESEcommon *seseCommon){
+ int localCount=0;
+ int i;
+ // check if every waiting entry is resolved
+ // if not, defer every items for hashtable until it is resolved.
+ int unresolved=FALSE;
+ for(i=0; i<q->bufcount;i++){
+ REntry *r=q->buf[i];
+ if(*(r->pointer)==0){
+ unresolved=TRUE;
+ }
+ }
+ if(unresolved==TRUE){
+ for(i=0; i<q->bufcount;i++){
+ REntry *r=q->buf[i];
+ r->queue=q;
+ r->isBufMode=TRUE;
+ if(ADDRENTRY(q,r)==NOTREADY){
+ localCount++;
+ }
+ }
+ return localCount;
+ }
+
+ // first phase: only consider write rentry
+ for(i=0; i<q->bufcount;i++){
+ REntry *r=q->buf[i];
+ if(r->type==WRITE){
+ int key=generateKey( OBJPTRPTR_2_OBJOID( r->pointer ) );
+ if(q->binbuf[key]==NULL){
+ // for multiple writes, add only the first write that hashes to the same bin
+ q->binbuf[key]=r;
+ }else{
+ q->buf[i]=NULL;
+ }
+ }
+ }
+ // second phase: enqueue read items if it is eligible
+ for(i=0; i<q->bufcount;i++){
+ REntry *r=q->buf[i];
+ if(r!=NULL && r->type==READ){
+ int key=generateKey( OBJPTRPTR_2_OBJOID( r->pointer ) );
+ if(q->binbuf[key]==NULL){
+ // read item that hashes to the bin which doen't contain any write
+ seseCommon->rentryArray[seseCommon->rentryIdx++]=r;
+ if(ADDRENTRY(q,r)==NOTREADY){
+ localCount++;
+ }
+ }
+ q->buf[i]=NULL;
+ }
+ }
+
+ // then, add only one of write items that hashes to the same bin
+ for(i=0; i<q->bufcount;i++){
+ REntry *r=q->buf[i];
+ if(r!=NULL){
+ seseCommon->rentryArray[seseCommon->rentryIdx++]=r;
+ if(ADDRENTRY(q,r)==NOTREADY){
+ localCount++;
+ }
+ }
+ }
+ return localCount;
+}
+
+
+resolvePointer(REntry* rentry){
+
+ Hashtable* table=rentry->hashtable;
+ MemoryQueue* queue;
+ if(table==NULL){
+ //resolved already before related rentry is enqueued to the waiting queue
+ return;
+ }
+ struct Queue* val;
+ do {
+ val=(struct Queue*)0x1;
+ val=(struct Queue*)LOCKXCHG((unsigned INTPTR*)&(table->unresolvedQueue), (unsigned INTPTR)val);
+ } while(val==(struct Queue*)0x1);
+ if(val!=NULL && getHead(val)->objectptr==rentry){
+ // handling pointer is the first item of the queue
+ // start to resolve until it reaches unresolved pointer or end of queue
+ INTPTR currentSESE=0;
+ do{
+ struct QueueItem* head=getHead(val);
+ if(head!=NULL){
+ REntry* rentry=(REntry*)head->objectptr;
+ if(*(rentry->pointer)==0){
+ // encounters following unresolved pointer
+ table->unresolvedQueue=val;//released lock
+ break;
+ }
+ removeItem(val,head);
+
+ //now, address is resolved
+
+ //check if rentry is buffer mode
+ if(rentry->isBufMode==TRUE){
+ if(currentSESE==0){
+ queue=rentry->queue;
+ INITIALIZEBUF(queue);
+ currentSESE=(INTPTR)rentry;
+ ADDRENTRYTOBUF(queue,rentry);
+ } else if(currentSESE==(INTPTR)rentry){
+ ADDRENTRYTOBUF(queue,rentry);
+ } else if(currentSESE!=(INTPTR)rentry){
+ RESOLVEBUFFORHASHTABLE(queue,table,(SESEcommon*)rentry->seseRec);
+ currentSESE=(INTPTR)rentry;
+ INITIALIZEBUF(queue);
+ ADDRENTRYTOBUF(rentry->queue,rentry);
+ }
+ }else{
+ if(currentSESE!=0){
+ //previous SESE has buf mode, need to invoke resolve buffer
+ RESOLVEBUFFORHASHTABLE(queue,table,(SESEcommon*)rentry->seseRec);
+ currentSESE=0;
+ }
+ //normal mode
+ if(ADDTABLEITEM(table, rentry, FALSE)==READY){
+ resolveDependencies(rentry);
+ }
+ }
+ }else{
+ table->unresolvedQueue=NULL; // set hashtable as normal-mode.
+ break;
+ }
+ }while(TRUE);
+ }else{
+ // resolved rentry is not head of queue
+ table->unresolvedQueue=val;//released lock;
+ }
+}
+
+void rehashMemoryQueue(SESEcommon* seseParent){
+#if 0
+ // update memory queue
+ int i,binidx;
+ for(i=0; i<seseParent->numMemoryQueue; i++){
+ MemoryQueue *memoryQueue=seseParent->memoryQueueArray[i];
+ MemoryQueueItem *memoryItem=memoryQueue->head;
+ MemoryQueueItem *prevItem=NULL;
+ while(memoryItem!=NULL){
+ if(memoryItem->type==HASHTABLE){
+ //do re-hash!
+ Hashtable* ht=(Hashtable*)memoryItem;
+ Hashtable* newht=createHashtable();
+ int binidx;
+ for(binidx=0; binidx<NUMBINS; binidx++){
+ BinElement *bin=ht->array[binidx];
+ BinItem *binItem=bin->head;
+ //traverse over the list of each bin
+ while(binItem!=NULL){
+ if(binItem->type==READBIN){
+ ReadBinItem* readBinItem=(ReadBinItem*)binItem;
+ int ridx;
+ for(ridx=0; ridx<readBinItem->index; ridx++){
+ REntry *rentry=readBinItem->array[ridx];
+ int newkey=generateKey((unsigned int)(unsigned INTPTR)*(rentry->pointer));
+ int status=rentry->binitem->status;
+ ADDTABLEITEM(newht,rentry,TRUE);
+ rentry->binitem->status=status; // update bin status as before rehash
+ }
+ }else{//write bin
+ REntry *rentry=((WriteBinItem*)binItem)->val;
+ int newkey=generateKey((unsigned int)(unsigned INTPTR)*(rentry->pointer));
+ int status=rentry->binitem->status;
+ ADDTABLEITEM(newht,rentry,TRUE);
+ int newstatus=rentry->binitem->status;
+ //printf("[%d]old status=%d new status=%d\n",i,status,newstatus);
+ rentry->binitem->status=status; // update bin status as before rehash
+ }
+ binItem=binItem->next;
+ }
+ }
+ newht->item.status=ht->item.status; // update hashtable status
+ if(prevItem!=NULL){
+ prevItem->next=(MemoryQueueItem*)newht;
+ }else{
+ if(memoryQueue->head==memoryQueue->tail){
+ memoryQueue->tail=(MemoryQueueItem*)newht;
+ }
+ memoryQueue->head=(MemoryQueueItem*)newht;
+ }
+ newht->item.next=ht->item.next;
+ }
+ prevItem=memoryItem;
+ memoryItem=memoryItem->next;
+ }
+ }
+#endif
+}
projects / IRC.git / blobdiff