From 9f300b75fc76620282347d9c61064db61c58d372 Mon Sep 17 00:00:00 2001 From: stephey Date: Mon, 11 Oct 2010 09:18:01 +0000 Subject: [PATCH] Added rough draft of how a remove from the hashStructure should work. Added method signature into the header file. The remove method needs insight on how to remove read bins. Details are in the comments. --- Robust/src/Runtime/oooJava/hashStructure.c | 103 ++++++++-- Robust/src/Runtime/oooJava/hashStructure.h | 215 ++++++++++++--------- 2 files changed, 208 insertions(+), 110 deletions(-) diff --git a/Robust/src/Runtime/oooJava/hashStructure.c b/Robust/src/Runtime/oooJava/hashStructure.c index e5ec373d..b13ec37c 100644 --- a/Robust/src/Runtime/oooJava/hashStructure.c +++ b/Robust/src/Runtime/oooJava/hashStructure.c @@ -8,7 +8,7 @@ HashStructure ** allHashStructures; //NOTE: only temporary -void createMasterHashTableArray(int maxSize) { +void createMasterHashTableArray(int maxSize){ int i; allHashTables = (HashTable**) malloc(sizeof(Hashtable) * maxSize); @@ -38,7 +38,8 @@ WriteBinItem_rcr* createWriteBinItem(){ ReadBinItem_rcr* createReadBinItem(){ ReadBinItem_rcr* binitem=(ReadBinItem_rcr*)RUNMALLOC(sizeof(ReadBinItem_rcr)); - binitem->index=0; + binitem->tail_Index=0; + binitem->head_Index=0; binitem->item.type=READBIN; return binitem; } @@ -82,7 +83,7 @@ int ADDTABLEITEM(HashStructure* table, void * ptr, int type, int traverserID, SE } } -int EMPTYBINCASE(HashStructure *T, BinElement_rcr* be, void *ptr, int type, int traverserId, SESEcommon * task, void *heaproot) { +int EMPTYBINCASE(HashStructure *T, BinElement_rcr* be, void *ptr, int type, int traverserId, SESEcommon * task, void *heaproot){ BinItem_rcr* b; TraverserData * td; if (type == WRITEEFFECT) { @@ -92,7 +93,7 @@ int EMPTYBINCASE(HashStructure *T, BinElement_rcr* be, void *ptr, int type, int else if (type == READEFFECT) { b=(BinItem_rcr*)createReadBinItem(); ReadBinItem_rcr* readbin=(ReadBinItem_rcr*)b; - td = &(readbin->array[readbin->index++]); + td = &(readbin->array[readbin->tail_Index++]); } b->total=1; b->type= type; @@ -113,7 +114,7 @@ int EMPTYBINCASE(HashStructure *T, BinElement_rcr* be, void *ptr, int type, int } -int WRITEBINCASE(HashStructure *T, void *ptr, int key, int traverserID, SESEcommon *task, void *heaproot) { +int WRITEBINCASE(HashStructure *T, void *ptr, 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 int status=NOTREADY; @@ -126,10 +127,10 @@ int WRITEBINCASE(HashStructure *T, void *ptr, int key, int traverserID, SESEcomm return be->tail->status; } } else if(be->tail->type == READBIN) { - TraverserData * td = &((ReadBinItem_rcr *)be->tail)->array[((ReadBinItem_rcr *)be->tail)->index - 1]; + TraverserData * td = &((ReadBinItem_rcr *)be->tail)->array[((ReadBinItem_rcr *)be->tail)->tail_Index - 1]; if(unlikely(td->resumePtr == ptr) && td->traverserID == traverserID) { //if it matches, then we remove it and the code below will upgrade it to a write. - ((ReadBinItem_rcr *)be->tail)->index--; + ((ReadBinItem_rcr *)be->tail)->tail_Index--; be->tail->total--; } } @@ -153,7 +154,7 @@ int WRITEBINCASE(HashStructure *T, void *ptr, int key, int traverserID, SESEcomm return status; } -int READBINCASE(HashStructure *T, void *ptr, int key, int traverserID, SESEcommon * task, void *heaproot) { +int READBINCASE(HashStructure *T, void *ptr, int key, int traverserID, SESEcommon * task, void *heaproot){ BinElement_rcr * be = &(T->array[key]); BinItem_rcr * bintail=be->tail; //check if already added item or not. @@ -164,7 +165,7 @@ int READBINCASE(HashStructure *T, void *ptr, int key, int traverserID, SESEcommo } } else if(bintail->type == READEFFECT) { - TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1]; + TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->tail_Index - 1]; if(unlikely(td->resumePtr == ptr) && td->traverserID == traverserID) { return bintail->status; } @@ -178,7 +179,7 @@ int READBINCASE(HashStructure *T, void *ptr, int key, int traverserID, SESEcommo } } -int TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *bintail, int key, int traverserID, SESEcommon * task, void *heaproot) { +int TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *bintail, int key, int traverserID, SESEcommon * task, void *heaproot){ ReadBinItem_rcr * readbintail=(ReadBinItem_rcr*)T->array[key].tail; int status, retval; TraverserData *td; @@ -190,16 +191,16 @@ int TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *bintail, int key, in retval=NOTREADY; } - if (readbintail->index==NUMREAD) { // create new read group + if (readbintail->tail_Index==NUMREAD) { // create new read group ReadBinItem_rcr* rb=createReadBinItem(); - td = &rb->array[rb->index++]; + td = &rb->array[rb->tail_Index++]; rb->item.total=1; rb->item.status=status; 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++]; + td = &readbintail->array[readbintail->tail_Index++]; atomic_inc(&readbintail->item.total); //printf("grouping with %d\n",readbintail->index); } @@ -214,13 +215,13 @@ int TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *bintail, int key, in return retval; } -void TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *bintail, int key, int traverserID, SESEcommon * task, void *heaproot) { +void TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *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_rcr* rb=createReadBinItem(); - TraverserData * td = &(rb->array[rb->index++]); + TraverserData * td = &(rb->array[rb->tail_Index++]); rb->item.total=1; rb->item.status=NOTREADY; @@ -235,4 +236,74 @@ void TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *bintail, int key, i T->array[key].tail=(BinItem_rcr*)rb; } -//TODO write deletion/removal methods +//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; + } + return retval; + } + + return -1; +} diff --git a/Robust/src/Runtime/oooJava/hashStructure.h b/Robust/src/Runtime/oooJava/hashStructure.h index ef81de1c..83ac6c6f 100644 --- a/Robust/src/Runtime/oooJava/hashStructure.h +++ b/Robust/src/Runtime/oooJava/hashStructure.h @@ -1,94 +1,121 @@ -#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 NUM_WAITING_Q_ITEMS 20 - -#define READEFFECT 0 -#define WRITEEFFECT 1 - -#define READBIN 0 -#define WRITEBIN 1 - -#define READY 1 -#define NOTREADY 0 - -#define TRUE 1 -#define FALSE 0 - -#define NUMBINS 64 -#define NUMREAD 64 -#define NUMITEMS 64 -#define NUMRENTRY 256 -#define H_MASK (NUMBINS<<4)-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 trackerElement { - BinItem_rcr * item; - struct trackerElement * next; -} TrackerElement; - -typedef struct tracker { - TrackerElement * head; - TrackerElement * tail; -} VariableTracker; - -//TODO more closely tie this in with Jim's stuff -struct genericObjectStruct { - int type; - int oid; - int allocsite; - int ___cachedCode___; - int ___cachedHash___; -}; - - -typedef struct BinElement_rcr { - BinItem_rcr * head; - BinItem_rcr * tail; -} BinElement_rcr; - - -typedef struct Hashtable_rcr { - BinElement_rcr array[NUMBINS]; - WaitingQueueBin * waitingQueue; -} HashStructure; - -//Todo this is a clone of REntry, remove data fields as necessary -typedef struct entry_rcr{ - //fields to handle next item. - struct Hashtable_rcr* hashtable; - BinItem_rcr* binitem; //stores binItem so we can get access to the next ptr in the queue - - //fields to help resume traverser - struct genericObjectStruct * resumePtr; -// int allocsite; //not needed since we can get it form ptr later - int traverserID; - SESEcommon * task; - struct genericObjectStruct * heaproot; -} TraverserData; - -typedef struct WriteBinItem_rcr { - BinItem_rcr item; - TraverserData val; -} WriteBinItem_rcr; - -typedef struct ReadBinItem_rcr { - BinItem_rcr item; - TraverserData array[NUMREAD]; - int index; -} ReadBinItem_rcr; - -#endif +#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; + + +//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 READY 1 +#define NOTREADY 0 + +#define TRUE 1 +#define FALSE 0 + +#define NUMBINS 64 +#define NUMREAD 64 +#define NUMRENTRY 256 +#define H_MASK (NUMBINS<<4)-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 trackerElement { + BinItem_rcr * item; + struct trackerElement * next; +} TrackerElement; + +typedef struct tracker { + TrackerElement * head; + TrackerElement * tail; +} VariableTracker; + +//TODO more closely tie this in with Jim's stuff +struct genericObjectStruct { + int type; + int oid; + int allocsite; + int ___cachedCode___; + int ___cachedHash___; +}; + + +typedef struct BinElement_rcr { + BinItem_rcr * head; + BinItem_rcr * tail; +} BinElement_rcr; + + +typedef struct Hashtable_rcr { + BinElement_rcr array[NUMBINS]; + WaitingQueueBin * waitingQueue; +} HashStructure; + +//Todo this is a clone of REntry, remove data fields as necessary +typedef struct entry_rcr{ + //fields to handle next item. + struct Hashtable_rcr* hashtable; + BinItem_rcr* binitem; //stores binItem so we can get access to the next ptr in the queue + + //fields to help resume traverser + struct genericObjectStruct * resumePtr; +// int allocsite; //not needed since we can get it form ptr later + int traverserID; + SESEcommon * task; + struct genericObjectStruct * heaproot; +} TraverserData; + +typedef struct WriteBinItem_rcr { + BinItem_rcr item; + TraverserData val; +} WriteBinItem_rcr; + +typedef struct ReadBinItem_rcr { + BinItem_rcr item; + TraverserData array[NUMREAD]; + //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 tail_Index; + int head_Index; +} ReadBinItem_rcr; + +typedef struct WQNote_rcr { + BinItem_rcr item; + int allocSiteID; +} WaitingQueueNote; + +void createMasterHashTableArray(int maxSize); //temporary +HashStructure* createHashtable(int sizeofWaitingQueue); +WriteBinItem_rcr* createWriteBinItem(); +ReadBinItem_rcr* createReadBinItem(); +int isReadBinItem(BinItem_rcr* b); +int isWriteBinItem(BinItem_rcr* b); +inline int 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 ADDTABLEITEM(HashStructure* table, void * ptr, int type, int traverserID, SESEcommon *task, void * heaproot); +int EMPTYBINCASE(HashStructure *T, BinElement_rcr* be, void *ptr, int type, int traverserId, SESEcommon * task, void *heaproot); +int WRITEBINCASE(HashStructure *T, void *ptr, int key, int traverserID, SESEcommon *task, void *heaproot); +int READBINCASE(HashStructure *T, void *ptr, int key, int traverserID, SESEcommon * task, void *heaproot); +int TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *bintail, int key, int traverserID, SESEcommon * task, void *heaproot); +void TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *bintail, int key, int traverserID, SESEcommon * task, void *heaproot); +int REMOVETABLEITEM(HashStructure* table, void * ptr, int traverserID, SESEcommon *task, void * heaproot); + +#endif -- 2.34.1