//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){
newTable->array[i].tail=NULL;
}
- // newTable->waitingQueue=mallocWaitingQueue(sizeofWaitingQueue);
return newTable;
}
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;
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<<index;
be->tail=b;
//release lock
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<<index;
+ if (!(bit & td->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<<index;
+ if (wrmask&bit) {
+ //count already includes this
+ status=READY;
+ }
+ b->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]);
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<<index;
be->tail=b;
//release lock
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<<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 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<<index;
+ int status=bintail->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;
} 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<<index;
T->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<<index;
T->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;i<rptr->index;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;i<rptr->index;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;
}
-
-*/
\r
#define ITEM_NOT_AT_FRONT_OF_WAITINGQ 3\r
#define TRAVERSER_FINISHED 2\r
-\r
+#define bitvt unsigned long long\r
\r
//Note READEFFECT = READBIN and WRITEEFFECT=WRITEBIN. They mean the same thing\r
//but are named differently for clarity in code.\r
\r
#define READBIN 0\r
#define WRITEBIN 1\r
+#define BINMASK 1\r
+#define PARENTBIN 1\r
\r
+#define SPECNOTREADY 2\r
#define READY 1\r
#define NOTREADY 0\r
\r
struct BinItem_rcr * next;\r
} BinItem_rcr;\r
\r
-typedef struct trackerElement {\r
- BinItem_rcr * item;\r
- struct trackerElement * next;\r
-} TrackerElement;\r
-\r
-typedef struct tracker {\r
- TrackerElement * head;\r
- TrackerElement * tail;\r
-} VariableTracker;\r
-\r
-//TODO more closely tie this in with Jim's stuff\r
-struct genericObjectStruct {\r
- int type;\r
- int oid;\r
- int allocsite;\r
- int ___cachedCode___;\r
- int ___cachedHash___;\r
-};\r
-\r
-\r
typedef struct BinElement_rcr {\r
BinItem_rcr * head;\r
BinItem_rcr * tail;\r
} BinElement_rcr;\r
\r
-\r
typedef struct Hashtable_rcr {\r
BinElement_rcr array[RNUMBINS];\r
// WaitingQueueBin * waitingQueue;\r
} HashStructure;\r
\r
//Todo this is a clone of REntry, remove data fields as necessary\r
-typedef struct entry_rcr{\r
- //fields to handle next item.\r
- struct Hashtable_rcr* hashtable;\r
- BinItem_rcr* binitem; //stores binItem so we can get access to the next ptr in the queue\r
-\r
- //fields to help resume traverser\r
- struct genericObjectStruct * resumePtr;\r
-// int allocsite; //not needed since we can get it form ptr later\r
- int traverserID;\r
+typedef struct Entry_rcr {\r
SESEcommon * task;\r
- struct genericObjectStruct * heaproot;\r
+ bitv bitindex;\r
} TraverserData;\r
\r
typedef struct WriteBinItem_rcr {\r
BinItem_rcr item;\r
- TraverserData val;\r
+ SESEcommon * task;\r
+ bitv bitindexwr;\r
+ bitv bitindexrd;\r
} WriteBinItem_rcr;\r
\r
typedef struct ReadBinItem_rcr {\r
TraverserData array[RNUMREAD];\r
//We don't need a head index since if the item before it was freed, then all these would be considered ready as well.\r
int index;\r
- \r
} ReadBinItem_rcr;\r
\r
-typedef struct WQNote_rcr {\r
- BinItem_rcr item;\r
- int allocSiteID;\r
-} WaitingQueueNote;\r
-\r
extern HashStructure ** allHashStructures;\r
\r
void rcr_createMasterHashTableArray(int maxSize); //temporary\r
//Method signatures are not in their final form since I have still not decided what is the optimum amount of data\r
//to store in each entry.\r
\r
-int rcr_WRITEBINCASE(HashStructure *T, void *ptr, int traverserID, SESEcommon *task, void *heaproot);\r
-int rcr_READBINCASE(HashStructure *T, void *ptr, int traverserID, SESEcommon * task, void *heaproot);\r
-int rcr_TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, int traverserID, SESEcommon * task, void *heaproot);\r
-void rcr_TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, int traverserID, SESEcommon * task, void *heaproot);\r
-int rcr_REMOVETABLEITEM(HashStructure* table, void * ptr, int traverserID, SESEcommon *task, void * heaproot);\r
+int rcr_WRITEBINCASE(HashStructure *T, void *ptr, SESEcommon *task, void *heaproot);\r
+int rcr_READBINCASE(HashStructure *T, void *ptr, SESEcommon * task, void *heaproot);\r
+int rcr_TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, void *heaproot);\r
+void rcr_TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, void *heaproot);\r
\r
#endif\r
projects / IRC.git / commitdiff