Robust/src/Runtime/oooJava/hashStructure.c

   1 #include "hashStructure.h"
   2 #include "WaitingQueue.h"
   3 #include "mlp_lock.h"
   4 #include "tm.h"
   5
   6 //NOTE: this is only temporary (for testing) and will be removed in favor of thread local variables
   7 //It's basically an array of hashStructures so we can simulate what would happen in a many-threaded version
   8 HashStructure ** allHashStructures;
   9
  10 //NOTE: only temporary
  11 void createMasterHashTableArray(int maxSize){
  12   int i;
  13   allHashTables = (HashTable**) malloc(sizeof(Hashtable) * maxSize);
  14
  15   for(i = 0; i < maxSize; i++) {
  16     allHashTables[i] = createHashtable();
  17   }
  18 }
  19
  20 HashStructure* createHashtable(int sizeofWaitingQueue){
  21   int i=0;
  22   HashStructure* newTable=(HashStructure*)RUNMALLOC(sizeof(HashStructure));
  23   for(i=0;i<NUMBINS;i++){
  24     newTable->array[i].head=NULL;
  25     newTable->array[i].tail=NULL;
  26   }
  27
  28   newTable->waitingQueue=mallocWaitingQueue(sizeofWaitingQueue);
  29   return newTable;
  30 }
  31
  32 WriteBinItem_rcr* createWriteBinItem(){
  33   WriteBinItem_rcr* binitem=(WriteBinItem_rcr*)RUNMALLOC(sizeof(WriteBinItem_rcr));
  34   binitem->item.type=WRITEBIN;
  35   return binitem;
  36 }
  37
  38 ReadBinItem_rcr* createReadBinItem(){
  39   ReadBinItem_rcr* binitem=(ReadBinItem_rcr*)RUNMALLOC(sizeof(ReadBinItem_rcr));
  40   binitem->tail_Index=0;
  41   binitem->head_Index=0;
  42   binitem->item.type=READBIN;
  43   return binitem;
  44 }
  45
  46 int isReadBinItem(BinItem_rcr* b){
  47   return b->type==READBIN;
  48 }
  49
  50 int isWriteBinItem(BinItem_rcr* b){
  51   return b->type==WRITEBIN;
  52 }
  53
  54 inline int generateKey(void * ptr){
  55   return (((struct genericObjectStruct *) ptr)->oid)&H_MASK;
  56 }
  57
  58 //TODO handle logic for waiting Queues separately
  59 //TODO pass in task to traverser
  60 int ADDTABLEITEM(HashStructure* table, void * ptr, int type, int traverserID, SESEcommon *task, void * heaproot){
  61   BinItem_rcr * val;
  62   int key=generateKey(ptr);
  63
  64   //LOCK is still needed as different threads will remove items...
  65   do {
  66     val=(BinItem_rcr *)0x1;
  67     val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(table->array[key]->bin->head), (unsigned INTPTR)val);
  68   } while(val==(BinItem_rcr*)0x1);
  69
  70   if (val==NULL) {
  71     return EMPTYBINCASE(table, table->array[key], ptr, type, traverserID, task, heaproot);
  72   } else {
  73     //else create item
  74     if (type == WRITEEFFECT) {
  75       return WRITEBINCASE(table, ptr, val, key, traverserID, task, heaproot);
  76     } else if (type == READEFFECT) {
  77       return READBINCASE(table, ptr, val, key, traverserID, task, heaproot);
  78     }
  79   }
  80 }
  81
  82 int EMPTYBINCASE(HashStructure *T, BinElement_rcr* be, void *ptr, int type, int traverserId, SESEcommon * task, void *heaproot){
  83   BinItem_rcr* b;
  84   TraverserData * td;
  85   //TODO: NEED PARENT CHECK HERE!!!!!!!!!
  86
  87
  88   if (type == WRITEEFFECT) {
  89     b=(BinItem_rcr*)createWriteBinItem();
  90     td = &((WriteBinItem_rcr*)b)->val;
  91   } else if (type == READEFFECT) {
  92     b=(BinItem_rcr*)createReadBinItem();
  93     ReadBinItem_rcr* readbin=(ReadBinItem_rcr*)b;
  94     td = &(readbin->array[readbin->tail_Index++]);
  95   }
  96   b->total=1;
  97   b->type= type;
  98   b->status = READY;
  99
 100   //common to both types
 101   td->binitem = b;
 102   td->hashtable=T;
 103   td->resumePtr = ptr;
 104   td->task= task;
 105   td->traverserID = traverserId;
 106   td->heaproot = heaproot;
 107   be->tail=b;
 108
 109   //release lock
 110   be->head=b;
 111
 112   return READY;
 113 }
 114
 115
 116 int WRITEBINCASE(HashStructure *T, void *ptr, BinItem * val, int key, int traverserID, SESEcommon *task, void *heaproot) {
 117   //chain of bins exists => tail is valid
 118   //if there is something in front of us, then we are not ready
 119   int status=NOTREADY;
 120   BinElement_rcr* be= &(T->array[key]); //do not grab head from here since it's locked (i.e. = 0x1)
 121   BinItem *bintail=be->tail;
 122
 123   if (bintail->type == WRITEBIN) {
 124     TraverserData * td = &(((WriteBinItem_rcr *)bintail)->val);
 125     //last one is to check for SESE blocks in a while loop.
 126     if(unlikely(td->resumePtr == ptr) && td->traverserID == traverserID && td->task == task) {
 127       return bintail->status;
 128     }
 129   } else if (bintail->type == READBIN) {
 130     TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
 131     if(unlikely(td->resumePtr == ptr) && td->traverserID == traverserID) {
 132       //if it matches, then we remove it and the code below will upgrade it to a write.
 133       ((ReadBinItem_rcr *)bintail)->index--;
 134       bintail->total--;
 135     }
 136   }
 137
 138   WriteBinItem_rcr *b=createWriteBinItem();
 139   TraverserData * td = &b->val;
 140   b->item.total=1;
 141
 142   //fillout traverserData
 143   //Note: this list could be smaller in the future, for now I'm just including all the info I may need.
 144   td->binitem = b;
 145   td->hashtable=T;
 146   td->resumePtr = ptr;
 147   td->task= task;
 148   td->traverserID = traverserID;
 149   td->heaproot = heaproot;
 150
 151   b->item.status=status;
 152   bintail->next=(BinItem_rcr*)b;
 153   be->tail=(BinItem_rcr*)b;
 154   //RELEASE LOCK
 155   be->head=val;
 156   return status;
 157 }
 158
 159 int READBINCASE(HashStructure *T, void *ptr, BinItem *val, int key, int traverserID, SESEcommon * task, void *heaproot) {
 160   BinElement_rcr * be = &(T->array[key]);
 161   BinItem_rcr * bintail=be->tail;
 162   //check if already added item or not.
 163   if (bintail->type == WRITEBIN) {
 164     TraverserData * td = &(((WriteBinItem_rcr *)bintail)->val);
 165     if(unlikely(td->resumePtr == ptr) && td->traverserID == traverserID) {
 166       //RELEASE LOCK
 167       be->head=val;
 168       return bintail->status;
 169     }
 170   } else if (bintail->type == READEFFECT) {
 171     TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
 172     if (unlikely(td->resumePtr == ptr) && td->traverserID == traverserID) {
 173       //RELEASE LOCK
 174       be->head=val;
 175       return bintail->status;
 176     }
 177   }
 178
 179   if (isReadBinItem(bintail)) {
 180     return TAILREADCASE(T, ptr, val, bintail, key, traverserID, task, heaproot);
 181   } else if (!isReadBinItem(bintail)) {
 182     TAILWRITECASE(T, ptr, val, bintail, key, traverserID, task, heaproot);
 183     return NOTREADY;
 184   }
 185 }
 186
 187
 188 int TAILREADCASE(HashStructure *T, void * ptr, BinItem *val, BinItem_rcr *bintail, int key, int traverserID, SESEcommon * task, void *heaproot) {
 189   ReadBinItem_rcr * readbintail=(ReadBinItem_rcr*)T->array[key].tail;
 190   int status, retval;
 191   TraverserData *td;
 192   if (readbintail->item.status==READY) {
 193     status=READY;
 194     retval=READY;
 195   } else {
 196     status=NOTREADY;
 197     retval=NOTREADY;
 198   }
 199
 200   if (readbintail->tail_Index==NUMREAD) { // create new read group
 201     ReadBinItem_rcr* rb=createReadBinItem();
 202     td = &rb->array[rb->tail_Index++];
 203
 204     rb->item.total=1;
 205     rb->item.status=status;
 206     T->array[key].tail->next=(BinItem_rcr*)rb;
 207     T->array[key].tail=(BinItem_rcr*)rb;
 208   } else { // group into old tail
 209     td = &readbintail->array[readbintail->tail_Index++];
 210     atomic_inc(&readbintail->item.total);
 211     //printf("grouping with %d\n",readbintail->index);
 212   }
 213
 214   td->binitem = bintail;
 215   td->hashtable=T;
 216   td->resumePtr = ptr;
 217   td->task= task;
 218   td->traverserID = traverserID;
 219   td->heaproot = heaproot;
 220
 221   T->array[key]->head=val;//released lock
 222   return retval;
 223 }
 224
 225 void TAILWRITECASE(HashStructure *T, void *ptr, BinItem *val, BinItem_rcr *bintail, int key, int traverserID, SESEcommon * task, void *heaproot) {
 226   ReadBinItem_rcr* rb=createReadBinItem();
 227   TraverserData * td = &(rb->array[rb->tail_Index++]);
 228   rb->item.total=1;
 229   rb->item.status=NOTREADY;
 230
 231   td->binitem = rb;
 232   td->hashtable=T;
 233   td->resumePtr = ptr;
 234   td->task= task;
 235   td->traverserID = traverserID;
 236   td->heaproot = heaproot;
 237
 238   T->array[key].tail->next=(BinItem_rcr*)rb;
 239   T->array[key].tail=(BinItem_rcr*)rb;
 240   T->array[key]->head=val;//released lock
 241 }
 242
 243 //TODO write deletion/removal methods
 244
 245 RETIREHASHTABLE(MemoryQueue *q, REntry *r) {
 246   Hashtable *T=r->hashtable;
 247   BinItem *b=r->binitem;
 248   RETIREBIN(T,r,b);
 249 }
 250
 251 RETIREBIN(Hashtable *T, REntry *r, BinItem *b) {
 252   int key=generateKey( OBJPTRPTR_2_OBJOID( r->pointer ) );
 253   if(isFineRead(r)) {
 254     atomic_dec(&b->total);
 255   }
 256   if (isFineWrite(r) || (isFineRead(r) && b->next!=NULL && b->total==0)) {
 257     // CHECK FIRST IF next is nonnull to guarantee that b.total cannot change
 258     BinItem * val;
 259     do {
 260       val=(BinItem*)0x1;
 261       val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(T->array[key]->head), (unsigned INTPTR)val);
 262     } while(val==(BinItem*)0x1);
 263     // at this point have locked bin
 264     BinItem *ptr=val;
 265     int haveread=FALSE;
 266     int i;
 267     while (ptr!=NULL) {
 268        if (isReadBinItem(ptr)) {
 269         ReadBinItem* rptr=(ReadBinItem*)ptr;
 270         if (rptr->item.status==NOTREADY) {
 271           for (i=0;i<rptr->index;i++) {
 272             resolveDependencies(rptr->array[i]);
 273             if (isParent(rptr->array[i])) {
 274               //parents go immediately
 275               atomic_dec(&rptr->item.total);
 276               atomic_dec(&T->item.total);
 277             }
 278           }
 279         }
 280         rptr->item.status=READY;
 281         if (rptr->item.next==NULL) {
 282           break;
 283         }
 284         if (rptr->item.total!=0) {
 285           haveread=TRUE;
 286         } else if ((BinItem*)rptr==val) {
 287           val=val->next;
 288         }
 289       } else if(isWriteBinItem(ptr)) {
 290         if (haveread)
 291           break;
 292         if(ptr->status==NOTREADY){
 293           resolveDependencies(((WriteBinItem*)ptr)->val);
 294           ptr->status=READY;
 295           if(isParent(((WriteBinItem*)ptr)->val)){
 296             atomic_dec(&T->item.total);
 297             val=val->next;
 298           }else
 299             break;
 300         }else{ // write bin is already resolved
 301           val=val->next;
 302         }
 303       }
 304       ptr=ptr->next;
 305     }
 306     T->array[key]->head=val; // release lock
 307   }
 308 }
 309
 310 //Int will return success/fail. -1 indicates error (i.e. there's nothing there).
 311 //0 = nothing removed, >0 something was removed
 312 int REMOVETABLEITEM(HashStructure* table, void * ptr, int traverserID, SESEcommon *task, void * heaproot) {
 313   int key = generateKey(ptr);
 314   BinElement_rcr * bucket = table->array[key];
 315
 316   if(bucket->head == NULL) {
 317     return -1;
 318     //This can occur if we try to remove something that's in the waitingQueue directly from the hashtable.
 319   }
 320
 321   if(bucket->head->type == WRITEBIN) {
 322     TraverserData * td = &(((WriteBinItem_rcr *) head)->val);
 323     if(td->resumePtr == ptr && td->traverserID == traverserID && td->heaproot == heaproot) {
 324       BinItem_rcr * temp = bucket->head;
 325       bucket->head = bucket->head->next;
 326       free(temp); //TODO perhaps implement a linked list of free BinElements as was done in WaitingQueue
 327
 328       //Handle items behind write item
 329       if(bucket->head == NULL) {
 330         bucket->tail == NULL;
 331         return 1;
 332       }
 333
 334       int type = bucket->head->type;
 335       switch(bucket->head->type) {
 336         case WRITEBIN:
 337           bucket->head->status = READY;
 338           //TODO Decrement dependency count
 339           return 1;
 340         case WAITINGQUEUENOTE:
 341           int retval = removeFromWaitingQueue(table->waitingQueue, ((WaitingQueueNote *) bucket->head)->allocSiteID, traverserID);
 342           if(retval >0) {
 343             //we set both to NULL because the note should ALWAYS be the last item in the hashStructure.
 344              bucket->head = NULL;
 345              bucket->tail = NULL;
 346           }
 347           return retval;
 348         default:
 349           BinItem_rcr * temp = bucket->head;
 350           while(temp != NULL && temp->type == READBIN) {
 351             temp->status = READY;
 352             temp = temp->next;
 353             //TODO decrement dependency count
 354           }
 355           return 1;
 356       }
 357     } else {
 358       return 0;
 359     }
 360   }
 361
 362   if(bucket->head->type == READBIN) {
 363     //TODO There's an issue here; bins are groups of items that may be enqueued by different ids.
 364     //I may have to search through them to find which one to remove but then there'd be a blank spot in an
 365     //otherwise clean array. It wouldn't make sense to just check the first one since reads are reorderable.
 366     //Nor does it make sense to lop off the reads since that may signal the next write to be ready even before it
 367     //really is ready.
 368   }
 369
 370   if(bucket->head->type == WAITINGQUEUENOTE) {
 371     int retval = removeFromWaitingQueue(table->waitingQueue, ((WaitingQueueNote *) bucket->head)->allocSiteID, traverserID);
 372     if(retval >0) {
 373        bucket->head = NULL;
 374        bucket->tail = NULL;
 375     }
 376     return retval;
 377   }
 378
 379   return -1;
 380 }
 381