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