#include "hashStructure.h"
-#include "tm.h"
+//#include "WaitingQueue.h"
+#include "mlp_lock.h"
+#include "mem.h"
-//TODO since hashtables can be shared amongst traversers and there's a finite number,
-//have a structure to keep track of all the hash tables for HRs.
+//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
-Hashtable* createHashtable(){
+//NOTE: only temporary
+void rcr_createMasterHashTableArray(int maxSize){
+}
+
+HashStructure* rcr_createHashtable(int sizeofWaitingQueue){
int i=0;
- Hashtable* newTable=(Hashtable*)RUNMALLOC(sizeof(Hashtable));
- for(i=0;i<NUMBINS;i++){
- newTable->array[i]=(BinElement*)RUNMALLOC(sizeof(BinElement));
- newTable->array[i]->head=NULL;
- newTable->array[i]->tail=NULL;
+ HashStructure* newTable=(HashStructure*)RUNMALLOC(sizeof(HashStructure));
+ for(i=0;i<RNUMBINS;i++){
+ newTable->array[i].head=NULL;
+ newTable->array[i].tail=NULL;
}
- //Todo edit here to make this be pointed to a generated waitingQueue
- newTable->unresolvedQueue=NULL;
return newTable;
}
-
-WriteBinItem* createWriteBinItem(){
- WriteBinItem* binitem=(WriteBinItem*)RUNMALLOC(sizeof(WriteBinItem));
+WriteBinItem_rcr* rcr_createWriteBinItem(){
+ WriteBinItem_rcr* binitem=(WriteBinItem_rcr*)RUNMALLOC(sizeof(WriteBinItem_rcr));
binitem->item.type=WRITEBIN;
return binitem;
}
-ReadBinItem* createReadBinItem(){
- ReadBinItem* binitem=(ReadBinItem*)RUNMALLOC(sizeof(ReadBinItem));
+ReadBinItem_rcr* rcr_createReadBinItem(){
+ ReadBinItem_rcr* binitem=(ReadBinItem_rcr*)RUNMALLOC(sizeof(ReadBinItem_rcr));
binitem->index=0;
binitem->item.type=READBIN;
return binitem;
}
-int isReadBinItem(BinItem* b){
- if(b->type==READBIN){
- return TRUE;
- }else{
- return FALSE;
- }
+inline int rcr_generateKey(void * ptr){
+ return (((struct ___Object___ *) ptr)->oid)&RH_MASK;
}
-int isWriteBinItem(BinItem* b){
- if(b->type==WRITEBIN){
- return TRUE;
- }else{
- return FALSE;
- }
-}
+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;
+ int key=rcr_generateKey(ptr);
+ BinElement_rcr* be= &(T->array[key]); //do not grab head from here since it's locked (i.e. = 0x1)
-inline int generateKey(void * ptr){
- return ((struct genericObjectStruct *) ptr)->oid&H_MASK;
-}
+ //LOCK is still needed as different threads will remove items...
+ do {
+ val=(BinItem_rcr *)0x1;
+ val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
+ } while(val==(BinItem_rcr*)0x1);
-//TODO handle logic for waiting Queues separately
-//TODO pass in task to traverser
-int ADDTABLEITEM(Hashtable* table, void * ptr, int type, int traverserID, SESEcommon *task, void * heaproot){
- BinItem * val;
- int key=generateKey(ptr);
- do {
- val=(BinItem*)0x1;
- BinElement* bin=table->array[key];
- 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], ptr, type, traverserID, task, heaproot);
- } else {
- //else create item
- if (type == WRITEEFFECT) {
- return WRITEBINCASE(table, ptr, val, key, traverserID, task, heaproot);
- } else if (type == READEFFECT) {
- return READBINCASE(table, ptr, val, key, traverserID, task, heaproot);
- }
+ BinItem_rcr * b=(BinItem_rcr*)rcr_createWriteBinItem();
+ TraverserData * td = &((WriteBinItem_rcr*)b)->val;
+ b->total=1;
+ b->status=READY;
+
+ //common to both types
+ td->task=task;
+ td->bitindex=1<<index;
+ be->tail=b;
+
+ //release lock
+ be->head=b;
+ return READY;
}
-}
-int EMPTYBINCASE(Hashtable *T, BinElement* be, void *ptr, int type, int traverserId, SESEcommon * task, void *heaproot) {
- BinItem* b;
- TraverserData * td;
- if (type == WRITEEFFECT) {
- b=(BinItem*)createWriteBinItem();
- td = &((WriteBinItem*)b)->val;
- }
- else if (type == READEFFECT) {
- b=(BinItem*)createReadBinItem();
- ReadBinItem* readbin=(ReadBinItem*)b;
- td = &(readbin->array[readbin->index++]);
- }
- b->total=1;
- b->type= type;
- b->status = READY;
-
- //common to both types
- td->binitem = b;
- td->hashtable=T;
- td->pointer = ptr;
- td->task= task;
- td->traverserID = traverserId;
- td->heaproot = heaproot;
-
- be->tail=b;
- be->head=b;//released lock
-
- return READY;
-}
-
-
-int WRITEBINCASE(Hashtable *T, void *ptr, BinItem *originalHead, int key, int traverserID, SESEcommon *task, void *heaproot) {
- //chain of bins exists => tail is valid
- //if there is something in front of us, then we are not ready
+ BinItem_rcr *bintail=be->tail;
+ bitv rdmask=0,wrmask=0;
int status=NOTREADY;
- BinElement* be=T->array[key]; //do not grab head from here since it's locked (i.e. = 0x1)
- if(be->tail->type == WRITEBIN) {
- TraverserData * td = &(((WriteBinItem *)be->tail)->val);
- if(unlikely(td->pointer == ptr) && td->traverserID == traverserID) {
- be->head = originalHead; //lock released
- return be->tail->status;
+ 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;
+ bitv bit=1<<index;
+ if (!(bit & td->bitindexwr)) {
+ td->bitindexwr|=bit;
+ td->bitindexrd|=bit;
+ return (bintail->status==READY)?READY:SPECNOTREADY;
+ } else
+ return READY;
}
- } else if(be->tail->type == READBIN) {
- TraverserData * td = &((ReadBinItem *)be->tail)->array[((ReadBinItem *)be->tail)->index - 1];
- if(unlikely(td->pointer == ptr) && td->traverserID == traverserID) {
+ } 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 *)be->tail)->index--;
- be->tail->total--;
+ ((ReadBinItem_rcr *)bintail)->index--;
+ atomic_dec(&bintail->total);
+ rdmask=tr->bitindex;
+ if (bintail->status!=READY)
+ wrmask=rdmask;
+ status=SPECNOTREADY;
}
}
- WriteBinItem *b=createWriteBinItem();
- TraverserData * td = &b->val;
+ WriteBinItem_rcr *b=rcr_createWriteBinItem();
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 = b;
- td->hashtable=T;
- td->pointer = ptr;
- td->task= task;
- td->traverserID = traverserID;
- td->heaproot = heaproot;
-
+ bitv bit=1<<index;
+ if (wrmask&bit) {
+ //count already includes this
+ status=READY;
+ }
+ b->bitindexwr=bit|wrmask;
+ b->bitindexrd=bit|rdmask;
b->item.status=status;
- be->tail->next=(BinItem*)b;
- be->tail=(BinItem*)b;
- be->head=originalHead; // lock released
+ 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 READBINCASE(Hashtable *T, void *ptr, BinItem *originalHead, int key, int traverserID, SESEcommon * task, void *heaproot) {
- BinElement * be = T->array[key];
- BinItem * bintail=be->tail;
+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]);
+
+ //LOCK is still needed as different threads will remove items...
+ do {
+ val=(BinItem_rcr *)0x1;
+ val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
+ } while(val==(BinItem_rcr*)0x1);
+
+ if (val==NULL) {
+ BinItem_rcr * b=(BinItem_rcr*)rcr_createReadBinItem();
+ ReadBinItem_rcr* readbin=(ReadBinItem_rcr*)b;
+ TraverserData * td = &(readbin->array[readbin->index++]);
+ b->total=1;
+ b->status=READY;
+
+ //common to both types
+ td->task=task;
+ td->bitindex=1<<index;
+ be->tail=b;
+
+ //release lock
+ be->head=b;
+
+ return READY;
+ }
+
+
+ BinItem_rcr * bintail=be->tail;
+
//check if already added item or not.
- if(bintail->type == WRITEBIN) {
- TraverserData * td = &(((WriteBinItem *)bintail)->val);
- if(unlikely(td->pointer == ptr) && td->traverserID == traverserID) {
- be->head = originalHead; //lock released
- return bintail->status;
+ if (ISWRITEBIN(bintail->type)) {
+ WriteBinItem_rcr td = (WriteBinItem_rcr *)bintail;
+ if(unlikely(td->task==task)) {
+ //RELEASE LOCK
+ bitv bit=1<<index;
+ int status=bintail->status;
+ if (!(td->bitindexrd & bit)) {
+ td->bitindexrd|=bit;
+ td->bitindexwr|=bit;
+ if (status==NOTREADY)
+ status=SNOTREADY;
+ } else
+ status=READY;
+ be->head=val;
+ return status;
+ }
+ } else {
+ TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
+ if (unlikely(td->task==task)) {
+ //RELEASE LOCK
+ bitv bit=1<<index;
+ int status=bintail->status;
+ if (!(td->bitindex & bit)) {
+ td->bitindex|=bit;
+ if (status==NOTREADY)
+ status=SNOTREADY;
+ } else
+ status=READY;
+ be->head=val;
+ return status;
}
- }
- else if(bintail->type == READEFFECT) {
- TraverserData * td = &((ReadBinItem *)bintail)->array[((ReadBinItem *)bintail)->index - 1];
- if(unlikely(td->pointer == ptr) && td->traverserID == traverserID) {
- return bintail->status;
}
- if (isReadBinItem(bintail)) {
- return TAILREADCASE(T, ptr, originalHead, bintail, key, traverserID, task, heaproot);
- } else if (!isReadBinItem(bintail)) {
- TAILWRITECASE(T, ptr, originalHead, 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 TAILREADCASE(Hashtable *T, void * ptr, BinItem *originalHead, BinItem *bintail, int key, int traverserID, SESEcommon * task, void *heaproot) {
- ReadBinItem * readbintail=(ReadBinItem*)T->array[key]->tail;
+
+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;
if (readbintail->item.status==READY) {
retval=NOTREADY;
}
- if (readbintail->index==NUMREAD) { // create new read group
- ReadBinItem* rb=createReadBinItem();
+ if (readbintail->index==RNUMREAD) { // create new read group
+ ReadBinItem_rcr* rb=rcr_createReadBinItem();
td = &rb->array[rb->index++];
rb->item.total=1;
rb->item.status=status;
- T->array[key]->tail->next=(BinItem*)rb;
- T->array[key]->tail=(BinItem*)rb;
+ T->array[key].tail->next=(BinItem_rcr*)rb;
+ T->array[key].tail=(BinItem_rcr*)rb;
} 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->pointer = ptr;
- td->task= task;
- td->traverserID = traverserID;
- td->heaproot = heaproot;
+ td->task=task;
+ td->bitindex=1<<index;
- T->array[key]->head=originalHead;//released lock
+ T->array[key].head=val;//released lock
return retval;
}
-void TAILWRITECASE(Hashtable *T, void *ptr, BinItem *val, BinItem *bintail, int key, int traverserID, SESEcommon * task, void *heaproot) {
- // WriteBinItem* wb=createWriteBinItem();
- //wb->val=r;
- //wb->item.total=1;//safe because item could not have started
- //wb->item.status=NOTREADY;
- ReadBinItem* rb=createReadBinItem();
+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;//safe because item could not have started
+ rb->item.total=1;
rb->item.status=NOTREADY;
- td->binitem = rb;
- td->hashtable=T;
- td->pointer = ptr;
- td->task= task;
- td->traverserID = traverserID;
- td->heaproot = heaproot;
+ td->binitem = (BinItem_rcr *) rb;
+ td->task=task;
+ td->bitindex=1<<index;
- T->array[key]->tail->next=(BinItem*)rb;
- T->array[key]->tail=(BinItem*)rb;
- T->array[key]->head=val;//released lock
+ T->array[key].tail->next=(BinItem_rcr*)rb;
+ T->array[key].tail=(BinItem_rcr*)rb;
+ T->array[key].head=val;//released lock
}
+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);
+ if (b->next==NULL || b->total>0) {
+ return;
+ }
+ }
+ //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=(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 (ISREADBIN(ptr->type)) {
+ if (ptr->status==NOTREADY) {
+ ReadBinItem_rcr* rptr=(ReadBinItem_rcr*)ptr;
+ for (i=0;i<rptr->index;i++) {
+ RESOLVE(rptr->array[i]);
+ if (((INTPTR)rptr->array[i]->task)&PARENTBIN) {
+ //parents go immediately
+ atomic_dec(&rptr->item.total);
+ }
+ }
+ ptr->status=READY;
+ }
+ if (ptr->next==NULL) {
+ break;
+ }
+ if (ptr->total!=0) {
+ haveread=TRUE;
+ } else if (ptr==val) {
+ val=val->next;
+ }
+ } else {
+ //write bin case
+ if (haveread)
+ break;
+ if(ptr->status==NOTREADY) {
+ WriteBinItem_rcr* wptr=(WriteBinItem_rcr*)ptr;
+ RESOLVE(wptr->val);
+ ptr->status=READY;
+ if(((INTPTR)wptr->task)&PARENTBIN) {
+ val=val->next;
+ } else
+ break;
+ } else { // write bin is already resolved
+ val=val->next;
+ }
+ }
+ ptr=ptr->next;
+ }
+ be->head=val; // release lock
+ }
+}
projects / IRC.git / blobdiff