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 int rcr_WRITEBINCASE(HashStructure *T, void *ptr, int traverserID, SESEcommon *task, void *heaproot) {
  52   //chain of bins exists => tail is valid
  53   //if there is something in front of us, then we are not ready
  54   BinItem_rcr * val;
  55   int key=rcr_generateKey(ptr);
  56   BinElement_rcr* be= &(T->array[key]); //do not grab head from here since it's locked (i.e. = 0x1)
  57
  58   //LOCK is still needed as different threads will remove items...
  59   do {
  60     val=(BinItem_rcr *)0x1;
  61     val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
  62   } while(val==(BinItem_rcr*)0x1);
  63
  64   if (val==NULL) {
  65     BinItem_rcr * b=(BinItem_rcr*)rcr_createWriteBinItem();
  66     TraverserData * td = &((WriteBinItem_rcr*)b)->val;
  67     b->total=1;
  68     b->status=READY;
  69
  70     //common to both types
  71     td->binitem = b;
  72     td->hashtable=T;
  73     td->resumePtr = ptr;
  74     td->task= task;
  75     td->traverserID = traverserID;
  76     td->heaproot = heaproot;
  77     be->tail=b;
  78
  79     //release lock
  80     be->head=b;
  81     return READY;
  82   }
  83
  84   int status=NOTREADY;
  85   BinItem_rcr *bintail=be->tail;
  86
  87   if (bintail->type == WRITEBIN) {
  88     TraverserData * td = &(((WriteBinItem_rcr *)bintail)->val);
  89     //last one is to check for SESE blocks in a while loop.
  90     if(unlikely(td->resumePtr == ptr) && td->traverserID == traverserID && td->task == task) {
  91       return bintail->status;
  92     }
  93   } else if (bintail->type == READBIN) {
  94     TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
  95     if(unlikely(td->resumePtr == ptr) && td->traverserID == traverserID) {
  96       //if it matches, then we remove it and the code below will upgrade it to a write.
  97       ((ReadBinItem_rcr *)bintail)->index--;
  98       bintail->total--;
  99     }
 100   }
 101
 102   WriteBinItem_rcr *b=rcr_createWriteBinItem();
 103   TraverserData * td = &b->val;
 104   b->item.total=1;
 105
 106   //fillout traverserData
 107   //Note: this list could be smaller in the future, for now I'm just including all the info I may need.
 108   td->binitem = (BinItem_rcr*)b;
 109   td->hashtable=T;
 110   td->resumePtr = ptr;
 111   td->task= task;
 112   td->traverserID = traverserID;
 113   td->heaproot = heaproot;
 114
 115   b->item.status=status;
 116   bintail->next=(BinItem_rcr*)b;
 117   be->tail=(BinItem_rcr*)b;
 118   //RELEASE LOCK
 119   be->head=val;
 120   return status;
 121 }
 122
 123 int rcr_READBINCASE(HashStructure *T, void *ptr, int traverserID, SESEcommon * task, void *heaproot) {
 124   BinItem_rcr * val;
 125   int key=rcr_generateKey(ptr);
 126   BinElement_rcr * be = &(T->array[key]);
 127
 128   //LOCK is still needed as different threads will remove items...
 129   do {
 130     val=(BinItem_rcr *)0x1;
 131     val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
 132   } while(val==(BinItem_rcr*)0x1);
 133
 134   if (val==NULL) {
 135     BinItem_rcr * b=(BinItem_rcr*)rcr_createReadBinItem();
 136     ReadBinItem_rcr* readbin=(ReadBinItem_rcr*)b;
 137     TraverserData * td = &(readbin->array[readbin->index++]);
 138     b->total=1;
 139     b->status = READY;
 140
 141     //common to both types
 142     td->binitem = b;
 143     td->hashtable=T;
 144     td->resumePtr = ptr;
 145     td->task= task;
 146     td->traverserID = traverserID;
 147     td->heaproot = heaproot;
 148     be->tail=b;
 149
 150     //release lock
 151     be->head=b;
 152
 153     return READY;
 154   }
 155
 156
 157   BinItem_rcr * bintail=be->tail;
 158
 159   //check if already added item or not.
 160   if (bintail->type == WRITEBIN) {
 161     TraverserData * td = &(((WriteBinItem_rcr *)bintail)->val);
 162     if(unlikely(td->resumePtr == ptr) && td->traverserID == traverserID) {
 163       //RELEASE LOCK
 164       be->head=val;
 165       return bintail->status;
 166     }
 167   } else if (bintail->type == READEFFECT) {
 168     TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
 169     if (unlikely(td->resumePtr == ptr) && td->traverserID == traverserID) {
 170       //RELEASE LOCK
 171       be->head=val;
 172       return bintail->status;
 173     }
 174   }
 175
 176   if (isReadBinItem(bintail)) {
 177     return rcr_TAILREADCASE(T, ptr, val, bintail, key, traverserID, task, heaproot);
 178   } else if (!isReadBinItem(bintail)) {
 179     rcr_TAILWRITECASE(T, ptr, val, bintail, key, traverserID, task, heaproot);
 180     return NOTREADY;
 181   }
 182 }
 183
 184
 185 int rcr_TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, int traverserID, SESEcommon * task, void *heaproot) {
 186   ReadBinItem_rcr * readbintail=(ReadBinItem_rcr*)T->array[key].tail;
 187   int status, retval;
 188   TraverserData *td;
 189   if (readbintail->item.status==READY) {
 190     status=READY;
 191     retval=READY;
 192   } else {
 193     status=NOTREADY;
 194     retval=NOTREADY;
 195   }
 196
 197   if (readbintail->index==NUMREAD) { // create new read group
 198     ReadBinItem_rcr* rb=rcr_createReadBinItem();
 199     td = &rb->array[rb->index++];
 200
 201     rb->item.total=1;
 202     rb->item.status=status;
 203     T->array[key].tail->next=(BinItem_rcr*)rb;
 204     T->array[key].tail=(BinItem_rcr*)rb;
 205   } else { // group into old tail
 206     td = &readbintail->array[readbintail->index++];
 207     atomic_inc(&readbintail->item.total);
 208     //printf("grouping with %d\n",readbintail->index);
 209   }
 210
 211   td->binitem = bintail;
 212   td->hashtable=T;
 213   td->resumePtr = ptr;
 214   td->task= task;
 215   td->traverserID = traverserID;
 216   td->heaproot = heaproot;
 217
 218   T->array[key].head=val;//released lock
 219   return retval;
 220 }
 221
 222 void rcr_TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, int traverserID, SESEcommon * task, void *heaproot) {
 223   ReadBinItem_rcr* rb=rcr_createReadBinItem();
 224   TraverserData * td = &(rb->array[rb->index++]);
 225   rb->item.total=1;
 226   rb->item.status=NOTREADY;
 227
 228   td->binitem = (BinItem_rcr *) rb;
 229   td->hashtable=T;
 230   td->resumePtr = ptr;
 231   td->task= task;
 232   td->traverserID = traverserID;
 233   td->heaproot = heaproot;
 234
 235   T->array[key].tail->next=(BinItem_rcr*)rb;
 236   T->array[key].tail=(BinItem_rcr*)rb;
 237   T->array[key].head=val;//released lock
 238 }
 239
 240 //TODO write deletion/removal methods
 241
 242 /*
 243 RETIREHASHTABLE(MemoryQueue *q, REntry *r) {
 244   Hashtable *T=r->hashtable;
 245   BinItem_rcr *b=r->binitem;
 246   RETIREBIN(T,r,b);
 247 }
 248
 249 RETIREBIN(Hashtable *T, REntry *r, BinItem_rcr *b) {
 250   int key=generateKey( OBJPTRPTR_2_OBJOID( r->pointer ) );
 251   if(isFineRead(r)) {
 252     atomic_dec(&b->total);
 253   }
 254   if (isFineWrite(r) || (isFineRead(r) && b->next!=NULL && b->total==0)) {
 255     // CHECK FIRST IF next is nonnull to guarantee that b.total cannot change
 256     BinItem_rcr * val;
 257     do {
 258       val=(BinItem_rcr*)0x1;
 259       val=(BinItem_rcr*)LOCKXCHG((unsigned INTPTR*)&(T->array[key]->head), (unsigned INTPTR)val);
 260     } while(val==(BinItem_rcr*)0x1);
 261     // at this point have locked bin
 262     BinItem_rcr *ptr=val;
 263     int haveread=FALSE;
 264     int i;
 265     while (ptr!=NULL) {
 266        if (isReadBinItem(ptr)) {
 267         ReadBinItem_rcr* rptr=(ReadBinItem_rcr*)ptr;
 268         if (rptr->item.status==NOTREADY) {
 269           for (i=0;i<rptr->index;i++) {
 270             resolveDependencies(rptr->array[i]);
 271             if (isParent(rptr->array[i])) {
 272               //parents go immediately
 273               atomic_dec(&rptr->item.total);
 274               atomic_dec(&T->item.total);
 275             }
 276           }
 277         }
 278         rptr->item.status=READY;
 279         if (rptr->item.next==NULL) {
 280           break;
 281         }
 282         if (rptr->item.total!=0) {
 283           haveread=TRUE;
 284         } else if ((BinItem_rcr*)rptr==val) {
 285           val=val->next;
 286         }
 287       } else if(isWriteBinItem(ptr)) {
 288         if (haveread)
 289           break;
 290         if(ptr->status==NOTREADY){
 291           resolveDependencies(((WriteBinItem_rcr*)ptr)->val);
 292           ptr->status=READY;
 293           if(isParent(((WriteBinItem_rcr*)ptr)->val)){
 294             atomic_dec(&T->item.total);
 295             val=val->next;
 296           }else
 297             break;
 298         }else{ // write bin is already resolved
 299           val=val->next;
 300         }
 301       }
 302       ptr=ptr->next;
 303     }
 304     T->array[key]->head=val; // release lock
 305   }
 306 }
 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
 382 */