Robust/src/Runtime/oooJava/hashStructure.c

   1 #include "hashStructure.h"
   2 //#include "WaitingQueue.h"
   3 #include "mlp_lock.h"
   4 #include "rcr_runtime.h"
   5 #include "mem.h"
   6 #include "classdefs.h"
   7
   8 __thread HashStructure ** allHashStructures;
   9 #define ISWRITEBIN(x) (x&BINMASK)
  10 #define ISREADBIN(x) (!(x&BINMASK))
  11 //#define POPCOUNT(x) __builtin_popcountll(x)
  12 //__builtin_popcountll
  13 #define ONEVAL 1ULL
  14
  15
  16 inline reenqueuerecord(struct rcrRecord *rcrrec, int tmpkey, BinItem_rcr *olditem, BinItem_rcr *newitem) {
  17   if (likely(rcrrec!=NULL)) {
  18     struct rcrRecord * tmprec=rcrrec;;
  19     int i;
  20     do {
  21       for(i=tmprec->index-1;i>=0;i--) {
  22         if (tmprec->ptrarray[i]==olditem&&tmprec->array[i]==tmpkey) {
  23           tmprec->ptrarray[i]=newitem;
  24           return;
  25         }
  26       }
  27       tmprec=tmprec->next;
  28     } while(1);
  29   }
  30 }
  31
  32 inline enqueuerecord(struct rcrRecord *rcrrec, int tmpkey, BinItem_rcr *item) {
  33   if (likely(rcrrec!=NULL)) {
  34     struct rcrRecord * tmprec;
  35     if(likely(rcrrec->index<RCRSIZE)) {
  36       int index=rcrrec->index++;
  37       rcrrec->ptrarray[index]=(void *) item;
  38       rcrrec->array[index]=tmpkey;
  39     } else if(likely((tmprec=rcrrec->next)!=NULL)&&likely(tmprec->index<RCRSIZE)) {
  40       int index=tmprec->index++;
  41       tmprec->ptrarray[index]=(void *) item;
  42       tmprec->array[index]=tmpkey;
  43     } else {
  44       struct rcrRecord *trec=RUNMALLOC(sizeof(struct rcrRecord));
  45       trec->ptrarray[0]=(void *) item;
  46       trec->array[0]=tmpkey;
  47       trec->index=1;
  48       trec->next=tmprec;
  49       rcrrec->next=trec;
  50     }
  51   }
  52 }
  53
  54 HashStructure ** rcr_createMasterHashTableArray(int maxSize){
  55   return (HashStructure **) malloc(sizeof(HashStructure *) * maxSize);
  56 }
  57
  58 HashStructure* rcr_createHashtable(){
  59   int i=0;
  60   HashStructure* newTable=(HashStructure*)RUNMALLOC(sizeof(HashStructure));
  61   for(i=0;i<RNUMBINS;i++){
  62     newTable->array[i].head=NULL;
  63     newTable->array[i].tail=NULL;
  64   }
  65   //newTable->memPoolRead = poolcreate( sizeof(ReadBinItem_rcr), NULL );
  66   //newTable->memPoolWrite = poolcreate( sizeof(WriteBinItem_rcr), NULL );
  67   return newTable;
  68 }
  69
  70 #define WBMAX 256
  71 __thread WriteBinItem_rcr* bank=NULL;
  72 __thread offset=WBMAX;
  73
  74
  75 WriteBinItem_rcr* rcr_createWriteBinItem( HashStructure* htable ){
  76   //WriteBinItem_rcr* binitem=(WriteBinItem_rcr*)poolalloc( htable->memPoolWrite );
  77   if (offset==WBMAX) {
  78     bank=(WriteBinItem_rcr*)RUNMALLOC(sizeof(WriteBinItem_rcr)*WBMAX);
  79     offset=0;
  80   }
  81
  82   WriteBinItem_rcr* binitem=&bank[offset++];
  83   //(WriteBinItem_rcr*)RUNMALLOC(sizeof(WriteBinItem_rcr));
  84   binitem->item.type=WRITEBIN;
  85   binitem->item.next=NULL;
  86   return binitem;
  87 }
  88
  89
  90 ReadBinItem_rcr* rcr_createReadBinItem( HashStructure* htable ){
  91   //ReadBinItem_rcr* binitem=(ReadBinItem_rcr*)poolalloc( htable->memPoolRead );
  92   ReadBinItem_rcr* binitem=(ReadBinItem_rcr*)RUNMALLOC(sizeof(ReadBinItem_rcr));
  93   binitem->index=0;
  94   binitem->item.type=READBIN;
  95   binitem->item.next=NULL;
  96   return binitem;
  97 }
  98
  99 inline int rcr_generateKey(void * ptr){
 100   return (((struct ___Object___ *) ptr)->oid)&RH_MASK;
 101 }
 102
 103 inline int rcr_BWRITEBINCASE(HashStructure *T, int key, SESEcommon *task, struct rcrRecord *rcrrec, int index, int mode) {
 104   //chain of bins exists => tail is valid
 105   //if there is something in front of us, then we are not ready
 106   BinItem_rcr * val;
 107   BinElement_rcr* be= &(T->array[key]); //do not grab head from here since it's locked (i.e. = 0x1)
 108
 109   //LOCK is still needed as different threads will remove items...
 110   do {
 111     val=(BinItem_rcr *)0x1;
 112     val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
 113   } while(val==(BinItem_rcr*)0x1);
 114
 115   if (val==NULL) {
 116     if (((INTPTR)task)&PARENTBIN) {
 117       be->head=val;
 118       return READY;
 119     }
 120
 121     BinItem_rcr * b=(BinItem_rcr*)rcr_createWriteBinItem( T );
 122     WriteBinItem_rcr * td = (WriteBinItem_rcr*)b;
 123     b->total=1;
 124     b->status=READY;
 125
 126     //common to both types
 127     td->task=task;
 128     td->bitindexrd=td->bitindexwr=ONEVAL<<index;
 129     be->tail=b;
 130     BARRIER();//do tail before head
 131     //release lock
 132     be->head=b;
 133     enqueuerecord(rcrrec, key, b);
 134     return READY;
 135   }
 136   BARRIER();//read head before tail
 137   BinItem_rcr *bintail=be->tail;
 138   bitvt rdmask=0,wrmask=0;
 139   int status=NOTREADY;
 140
 141   WriteBinItem_rcr *b;
 142   if (ISWRITEBIN(bintail->type)) {
 143     WriteBinItem_rcr * td = (WriteBinItem_rcr *)bintail;
 144     //last one is to check for SESE blocks in a while loop.
 145     if(unlikely(td->task == task)) {
 146
 147       bitvt bit=ONEVAL<<index;
 148       if (!(bit & td->bitindexwr)) {
 149         td->bitindexwr|=bit;
 150         td->bitindexrd|=bit;
 151         be->head=val;
 152         if (mode) {
 153           while(bintail->status!=READY) {
 154             BARRIER();
 155           }
 156           return READY;
 157         } else {
 158           return bintail->status;
 159         }
 160       } else {
 161         be->head=val;
 162         return READY;
 163       }
 164     }
 165     b=rcr_createWriteBinItem( T );
 166   } else {
 167     TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
 168     b=rcr_createWriteBinItem( T );
 169     if(unlikely(td->task == task)) {
 170       //if it matches, then we remove it and the code below will upgrade it to a write.
 171       ((ReadBinItem_rcr *)bintail)->index--;
 172       atomic_dec(&bintail->total);
 173       rdmask=td->bitindex;
 174       if (bintail->status!=READY)
 175         wrmask=rdmask;
 176       status=SPECNOTREADY;
 177       {
 178         //yank the old one out of the retire list and put us in place
 179         int oldindex=__builtin_ctz(rdmask);
 180         struct rcrRecord * oldrec=&rcrrec[oldindex-index];
 181         reenqueuerecord(oldrec, key, bintail, (BinItem_rcr *) b);
 182       }
 183     }
 184   }
 185
 186   b->item.total=1;
 187   b->task=task;
 188
 189   bitvt bit=ONEVAL<<index;
 190   if (wrmask&bit) {
 191     //count already includes this
 192     status=SPECREADY;
 193   }
 194   b->bitindexwr=bit|wrmask;
 195   b->bitindexrd=bit|rdmask;
 196   b->item.status=status&READYMASK;
 197   bintail->next=(BinItem_rcr*)b;
 198   be->tail=(BinItem_rcr*)b;
 199   MBARRIER(); //need to make sure that the read below doesn't pass the write above
 200   if (bintail->status==READY&&bintail->total==0) {
 201     //we may have to set write as ready
 202     while(1) {
 203       if (val==((BinItem_rcr *)b)) {
 204         if (((INTPTR)task)&PARENTBIN) {
 205           //pull b from bin
 206           be->head=NULL;
 207           return READY;
 208         }
 209         b->item.status=READY;
 210         be->head=val;
 211         if (status&SPEC) {
 212           return READY;
 213         } else {
 214           enqueuerecord(rcrrec, key, (BinItem_rcr *) b);
 215           return READY;
 216         }
 217       } else if (val->total!=0) {
 218         break;
 219       }
 220       //TODO: WHEN WE DO POOLALLOC, WE LEAK NODES HERE AND ACCESS THEM W/O LOCKING BIN...
 221       val=val->next;
 222     }
 223   }
 224
 225   //RELEASE LOCK
 226   be->head=val;
 227   if (mode) {
 228     while(b->item.status==NOTREADY) {
 229       BARRIER();
 230     }
 231     if (!(status&SPEC))
 232       enqueuerecord(rcrrec, key, (BinItem_rcr *) b);
 233     return status&READY;
 234   } else {
 235     if (!(status&SPEC))
 236       enqueuerecord(rcrrec, key, (BinItem_rcr *) b);
 237     return status&READY;
 238   }
 239 }
 240
 241 inline int rcr_BREADBINCASE(HashStructure *T, int key, SESEcommon *task, struct rcrRecord *rcrrec, int index, int mode) {
 242   BinItem_rcr * val;
 243   BinElement_rcr * be = &(T->array[key]);
 244
 245   //LOCK is still needed as different threads will remove items...
 246   do {
 247     val=(BinItem_rcr *)0x1;
 248     val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
 249   } while(val==(BinItem_rcr*)0x1);
 250
 251   if (val==NULL) {
 252     if (((INTPTR)task)&PARENTBIN) {
 253       be->head=val;
 254       return READY;
 255     }
 256
 257     BinItem_rcr * b=(BinItem_rcr*)rcr_createReadBinItem( T );
 258     ReadBinItem_rcr* readbin=(ReadBinItem_rcr*)b;
 259     TraverserData * td = &(readbin->array[readbin->index++]);
 260     b->total=1;
 261     b->status=READY;
 262
 263     //common to both types
 264     td->task=task;
 265     td->bitindex=ONEVAL<<index;
 266     be->tail=b;
 267
 268     //release lock
 269     be->head=b;
 270     enqueuerecord(rcrrec, key, b);
 271     return READY;
 272   }
 273
 274
 275   BinItem_rcr * bintail=be->tail;
 276
 277   //check if already added item or not.
 278   if (ISWRITEBIN(bintail->type)) {
 279     WriteBinItem_rcr * td = (WriteBinItem_rcr *)bintail;
 280     if(unlikely(td->task==task)) {
 281       //RELEASE LOCK
 282       bitvt bit=ONEVAL<<index;
 283       int status=bintail->status;
 284       if (!(td->bitindexrd & bit)) {
 285         td->bitindexrd|=bit;
 286         td->bitindexwr|=bit;
 287       } else
 288         status=READY;
 289       be->head=val;
 290       if (mode) {
 291         while(bintail->status!=READY) {
 292           BARRIER();
 293         }
 294         return READY;
 295       } else {
 296         return status;
 297       }
 298     }
 299     rcr_TAILWRITECASE(T, val, bintail, key, task, rcrrec, index);
 300     if (mode) {
 301       struct BinItem_rcr * bt=be->tail;
 302       while(bt->status!=READY) {
 303         BARRIER();
 304       }
 305       return READY;
 306     } else {
 307       return NOTREADY;
 308     }
 309   } else {
 310     TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
 311     if (unlikely(td->task==task)) {
 312       //RELEASE LOCK
 313       bitvt bit=ONEVAL<<index;
 314       int status=bintail->status;
 315       if (!(td->bitindex & bit)) {
 316         td->bitindex|=bit;
 317       } else
 318         status=READY;
 319       be->head=val;
 320       if (mode) {
 321         while(bintail->status!=READY) {
 322           BARRIER();
 323         }
 324       }
 325       return status;
 326     }
 327
 328     if ((((INTPTR)task)&PARENTBIN)&&(bintail->status==READY)) {
 329       be->head=val;
 330       return READY;
 331     }
 332
 333     int stat=rcr_TAILREADCASE(T, val, bintail, key, task, rcrrec, index);
 334     if (mode) {
 335       struct BinItem_rcr * bt=be->tail;
 336       while(bt->status!=READY) {
 337         BARRIER();
 338       }
 339       return READY;
 340     } else {
 341       return stat;
 342     }
 343   }
 344 }
 345
 346
 347 int rcr_WRITEBINCASE(HashStructure *T, int key, SESEcommon *task, struct rcrRecord *rcrrec, int index) {
 348   return rcr_BWRITEBINCASE(T, key, task, rcrrec, index, 0);
 349 }
 350 int rcr_READBINCASE(HashStructure *T, int key, SESEcommon * task, struct rcrRecord *rcrrec, int index) {
 351   return rcr_BREADBINCASE(T, key, task, rcrrec, index, 0);
 352 }
 353
 354 int rcr_WTWRITEBINCASE(HashStructure *T, int key, SESEcommon *task, struct rcrRecord *rcrrec, int index) {
 355   return rcr_BWRITEBINCASE(T, key, task, rcrrec, index, 1);
 356 }
 357
 358 int rcr_WTREADBINCASE(HashStructure *T, int key, SESEcommon * task, struct rcrRecord *rcrrec, int index) {
 359   return rcr_BREADBINCASE(T, key, task, rcrrec, index, 1);
 360 }
 361
 362  int rcr_TAILREADCASE(HashStructure *T, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, struct rcrRecord * rcrrec, int index) {
 363   ReadBinItem_rcr * readbintail=(ReadBinItem_rcr*)T->array[key].tail;
 364   int status, retval;
 365   TraverserData *td;
 366   if (readbintail->item.status==READY) {
 367     status=READY;
 368     retval=READY;
 369   } else {
 370     status=NOTREADY;
 371     retval=NOTREADY;
 372   }
 373
 374   if (readbintail->index==RNUMREAD) { // create new read group
 375     ReadBinItem_rcr* rb=rcr_createReadBinItem( T );
 376     td = &rb->array[rb->index++];
 377     td->task=task;
 378     td->bitindex=ONEVAL<<index;
 379     rb->item.total=1;
 380     rb->item.status=status;
 381     T->array[key].tail->next=(BinItem_rcr*)rb;
 382     T->array[key].tail=(BinItem_rcr*)rb;
 383     enqueuerecord(rcrrec, key, (BinItem_rcr *) rb);
 384   } else { // group into old tail
 385     td = &readbintail->array[readbintail->index];
 386     td->task=task;
 387     td->bitindex=ONEVAL<<index;
 388     BARRIER();//ordering is to prevent retiring task from trashing us...
 389     readbintail->index++;
 390     atomic_inc(&readbintail->item.total);
 391     enqueuerecord(rcrrec, key, (BinItem_rcr *) readbintail);
 392   }
 393
 394
 395
 396   T->array[key].head=val;//released lock
 397   return retval;
 398 }
 399
 400 void rcr_TAILWRITECASE(HashStructure *T, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, struct rcrRecord *rcrrec, int index) {
 401   ReadBinItem_rcr* rb=rcr_createReadBinItem( T );
 402   TraverserData * td = &(rb->array[rb->index++]);
 403   rb->item.total=1;
 404   rb->item.status=NOTREADY;
 405
 406   td->task=task;
 407   td->bitindex=ONEVAL<<index;
 408   enqueuerecord(rcrrec, key, (BinItem_rcr *) rb);
 409
 410   T->array[key].tail->next=(BinItem_rcr*)rb;
 411   T->array[key].tail=(BinItem_rcr*)rb;
 412   T->array[key].head=val;//released lock
 413 }
 414
 415 void rcr_RETIREHASHTABLE(HashStructure *T, SESEcommon *task, int key, BinItem_rcr *b) {
 416   atomic_dec(&b->total);
 417
 418   //Need to clear ourself out of the read bin so that we aren't resolved after being freed
 419   if(ISREADBIN(b->type)) {
 420     //Have to clear our entry out of bin if we retired early
 421
 422     if (b->status==NOTREADY) {
 423       ReadBinItem_rcr* rptr=(ReadBinItem_rcr*)b;
 424       BinElement_rcr * be = &(T->array[key]);
 425       int i;
 426       // CHECK FIRST IF next is nonnull to guarantee that b.total cannot change
 427       BinItem_rcr * val=(BinItem_rcr *)0x1;
 428       do {
 429         val=(BinItem_rcr*)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
 430       } while(val==(BinItem_rcr*)0x1);
 431       for (i=0;i<rptr->index;i++) {
 432         TraverserData * td=&rptr->array[i];
 433         if (task==td->task) {
 434           //remove item from bin...
 435           td->task=NULL;
 436           break;
 437         }
 438       }
 439       be->head=val;
 440     }
 441     if (b->next==NULL || b->total>0) {
 442       //need to remove ourself to avoid writecombining problems
 443       ReadBinItem_rcr* rptr=(ReadBinItem_rcr*)b;
 444       TraverserData * td=&rptr->array[rptr->index-1];
 445       if (td->task==task)
 446         td->task=NULL;
 447       return;
 448     }
 449   }
 450
 451
 452   //We either have a write bin or we are at the end of a read bin
 453   BinElement_rcr * be = &(T->array[key]);
 454   {
 455     // CHECK FIRST IF next is nonnull to guarantee that b.total cannot change
 456     BinItem_rcr * val=(BinItem_rcr *)0x1;
 457     do {
 458       val=(BinItem_rcr*)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
 459     } while(val==(BinItem_rcr*)0x1);
 460
 461     // at this point have locked bin
 462     BinItem_rcr *ptr=val;
 463     BinItem_rcr *next;
 464     int haveread=FALSE;
 465     int i;
 466     while (ptr!=NULL) {
 467       next = ptr->next;
 468       if (ISREADBIN(ptr->type)) {
 469         if (ptr->status==NOTREADY) {
 470           ReadBinItem_rcr* rptr=(ReadBinItem_rcr*)ptr;
 471           for (i=0;i<rptr->index;i++) {
 472             TraverserData * td=&rptr->array[i];
 473             SESEcommon *record=td->task;
 474             if (((INTPTR)record)&PARENTBIN) {
 475               //parents go immediately
 476               atomic_dec(&rptr->item.total);
 477               record=(SESEcommon *)(((INTPTR)record)&~1ULL);
 478             }
 479             if (record!=NULL)
 480               RESOLVE(record, td->bitindex);
 481           }
 482           ptr->status=READY;
 483         }
 484         if (ptr->next==NULL) {
 485           break;
 486         }
 487         if (ptr->total!=0) {
 488           haveread=TRUE;
 489         } else if (ptr==val) {
 490           val=val->next;
 491
 492           // THE 3 POOLFREE's IN THIS FUNCTION ARE TOO EARLY:
 493           // OTHER FUNCTIONS IN THIS COMPILATION UNIT LOCK THE BIN ELEMENT
 494           // BUT MAY TOUCH THE STATUS FIELDS OF BIN ITEMS AFTER RELEASING
 495           // THE LOCK, WE HAVE TO MAKE SOME CAREFUL CHANGES TO ALLOW THE
 496           // POOLFREE's TO WORK!
 497
 498           //poolfreeinto( T->memPoolRead, ptr );
 499         }
 500       } else if (ptr->total==0) {
 501         //skip past retired item
 502         if (ptr==val) {
 503           val=val->next;
 504           //poolfreeinto( T->memPoolWrite, ptr );
 505         }
 506       } else {
 507         //write bin case
 508         if (haveread)
 509           break;
 510         if(ptr->status==NOTREADY) {
 511           WriteBinItem_rcr* wptr=(WriteBinItem_rcr*)ptr;
 512           RESOLVE((SESEcommon *)(((INTPTR)wptr->task)&~1ULL), wptr->bitindexwr);
 513           ptr->status=READY;
 514           if(((INTPTR)wptr->task)&PARENTBIN) {
 515             val=val->next;
 516             //poolfreeinto( T->memPoolWrite, ptr );
 517           } else
 518             break;
 519         } else
 520           break;
 521       }
 522       ptr = next;
 523     }
 524     be->head=val; // release lock
 525   }
 526 }
 527
 528 void RESOLVE(SESEcommon *record, bitvt mask) {
 529   int index=-1;
 530   struct rcrRecord * array=(struct rcrRecord *)(((char *)record)+record->offsetToParamRecords);
 531   while(mask!=0) {
 532     int shift=__builtin_ctzll(mask)+1;
 533     index+=shift;
 534     if (atomic_sub_and_test(1,&array[index].count)) {
 535       if(unlikely(record->classID<0)) {
 536         //parent stall...clear it
 537         psem_give_tag(record->parentsStallSem, ((SESEstall *)record)->tag);
 538         //mark the record unused
 539         BARRIER();
 540         record->rcrstatus=0;
 541 #ifndef OOO_DISABLE_TASKMEMPOOL
 542         RELEASE_REFERENCE_TO(record);
 543 #endif
 544       } else {
 545         int flag=LOCKXCHG32(&array[index].flag,0);
 546         if (flag) {
 547           if(atomic_sub_and_test(1, &(record->unresolvedDependencies)))
 548             workScheduleSubmit((void *)record);
 549         }
 550       }
 551     }
 552     mask=mask>>shift;
 553   }
 554 }