Robust/src/Runtime/oooJava/hashStructure.c

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