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
 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         b->item.status=READY;
 169         be->head=val;
 170         if (status&SPEC) {
 171           return READY;
 172         } else {
 173           enqueuerecord(rcrrec, key, (BinItem_rcr *) b);
 174           return READY;
 175         }
 176       } else if (val->total!=0) {
 177         break;
 178       }
 179       //TODO: WHEN WE DO POOLALLOC, WE LEAK NODES HERE AND ACCESS THEM W/O LOCKING BIN...
 180       val=val->next;
 181     }
 182   }
 183
 184   //RELEASE LOCK
 185   be->head=val;
 186   if (mode) {
 187     while(b->item.status==NOTREADY) {
 188       BARRIER();
 189     }
 190     return status&READY;
 191   } else {
 192     if (!(status&SPEC))
 193       enqueuerecord(rcrrec, key, (BinItem_rcr *) b);
 194     return status&READY;
 195   }
 196 }
 197
 198 inline int rcr_BREADBINCASE(HashStructure *T, int key, SESEcommon *task, struct rcrRecord *rcrrec, int index, int mode) {
 199   BinItem_rcr * val;
 200   BinElement_rcr * be = &(T->array[key]);
 201
 202   //LOCK is still needed as different threads will remove items...
 203   do {
 204     val=(BinItem_rcr *)0x1;
 205     val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
 206   } while(val==(BinItem_rcr*)0x1);
 207
 208   if (val==NULL) {
 209     if (((INTPTR)task)&PARENTBIN) {
 210       be->head=val;
 211       return READY;
 212     }
 213
 214     BinItem_rcr * b=(BinItem_rcr*)rcr_createReadBinItem( T );
 215     ReadBinItem_rcr* readbin=(ReadBinItem_rcr*)b;
 216     TraverserData * td = &(readbin->array[readbin->index++]);
 217     b->total=1;
 218     b->status=READY;
 219
 220     //common to both types
 221     td->task=task;
 222     td->bitindex=ONEVAL<<index;
 223     be->tail=b;
 224
 225     //release lock
 226     be->head=b;
 227     enqueuerecord(rcrrec, key, b);
 228     return READY;
 229   }
 230
 231
 232   BinItem_rcr * bintail=be->tail;
 233
 234   //check if already added item or not.
 235   if (ISWRITEBIN(bintail->type)) {
 236     WriteBinItem_rcr * td = (WriteBinItem_rcr *)bintail;
 237     if(unlikely(td->task==task)) {
 238       //RELEASE LOCK
 239       bitvt bit=ONEVAL<<index;
 240       int status=bintail->status;
 241       if (!(td->bitindexrd & bit)) {
 242         td->bitindexrd|=bit;
 243         td->bitindexwr|=bit;
 244       } else
 245         status=READY;
 246       be->head=val;
 247       if (mode) {
 248         while(bintail->status!=READY) {
 249           BARRIER();
 250         }
 251         return READY;
 252       } else {
 253         return status;
 254       }
 255     }
 256     rcr_TAILWRITECASE(T, val, bintail, key, task, rcrrec, index);
 257     if (mode) {
 258       struct BinItem_rcr * bt=be->tail;
 259       while(bt->status!=READY) {
 260         BARRIER();
 261       }
 262       return READY;
 263     } else {
 264       return NOTREADY;
 265     }
 266   } else {
 267     TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
 268     if (unlikely(td->task==task)) {
 269       //RELEASE LOCK
 270       bitvt bit=ONEVAL<<index;
 271       int status=bintail->status;
 272       if (!(td->bitindex & bit)) {
 273         td->bitindex|=bit;
 274       } else
 275         status=READY;
 276       be->head=val;
 277       if (mode) {
 278         while(bintail->status!=READY) {
 279           BARRIER();
 280         }
 281       }
 282       return status;
 283     }
 284
 285     if ((((INTPTR)task)&PARENTBIN)&&(bintail->status==READY)) {
 286       be->head=val;
 287       return READY;
 288     }
 289
 290     int stat=rcr_TAILREADCASE(T, val, bintail, key, task, rcrrec, index);
 291     if (mode) {
 292       struct BinItem_rcr * bt=be->tail;
 293       while(bt->status!=READY) {
 294         BARRIER();
 295       }
 296       return READY;
 297     } else {
 298       return stat;
 299     }
 300   }
 301 }
 302
 303
 304 int rcr_WRITEBINCASE(HashStructure *T, int key, SESEcommon *task, struct rcrRecord *rcrrec, int index) {
 305   return rcr_BWRITEBINCASE(T, key, task, rcrrec, index, 0);
 306 }
 307 int rcr_READBINCASE(HashStructure *T, int key, SESEcommon * task, struct rcrRecord *rcrrec, int index) {
 308   return rcr_BREADBINCASE(T, key, task, rcrrec, index, 0);
 309 }
 310
 311 int rcr_WTWRITEBINCASE(HashStructure *T, int key, SESEcommon *task, struct rcrRecord *rcrrec, int index) {
 312   return rcr_BWRITEBINCASE(T, key, task, rcrrec, index, 1);
 313 }
 314
 315 int rcr_WTREADBINCASE(HashStructure *T, int key, SESEcommon * task, struct rcrRecord *rcrrec, int index) {
 316   return rcr_BREADBINCASE(T, key, task, rcrrec, index, 1);
 317 }
 318
 319  int rcr_TAILREADCASE(HashStructure *T, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, struct rcrRecord * rcrrec, int index) {
 320   ReadBinItem_rcr * readbintail=(ReadBinItem_rcr*)T->array[key].tail;
 321   int status, retval;
 322   TraverserData *td;
 323   if (readbintail->item.status==READY) {
 324     status=READY;
 325     retval=READY;
 326   } else {
 327     status=NOTREADY;
 328     retval=NOTREADY;
 329   }
 330
 331   if (readbintail->index==RNUMREAD) { // create new read group
 332     ReadBinItem_rcr* rb=rcr_createReadBinItem( T );
 333     td = &rb->array[rb->index++];
 334
 335     rb->item.total=1;
 336     rb->item.status=status;
 337     T->array[key].tail->next=(BinItem_rcr*)rb;
 338     T->array[key].tail=(BinItem_rcr*)rb;
 339     enqueuerecord(rcrrec, key, (BinItem_rcr *) rb);
 340   } else { // group into old tail
 341     td = &readbintail->array[readbintail->index++];
 342     atomic_inc(&readbintail->item.total);
 343     enqueuerecord(rcrrec, key, (BinItem_rcr *) readbintail);
 344   }
 345
 346   td->task=task;
 347   td->bitindex=ONEVAL<<index;
 348
 349   T->array[key].head=val;//released lock
 350   return retval;
 351 }
 352
 353 void rcr_TAILWRITECASE(HashStructure *T, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, struct rcrRecord *rcrrec, int index) {
 354   ReadBinItem_rcr* rb=rcr_createReadBinItem( T );
 355   TraverserData * td = &(rb->array[rb->index++]);
 356   rb->item.total=1;
 357   rb->item.status=NOTREADY;
 358
 359   td->task=task;
 360   td->bitindex=ONEVAL<<index;
 361   enqueuerecord(rcrrec, key, (BinItem_rcr *) rb);
 362
 363   T->array[key].tail->next=(BinItem_rcr*)rb;
 364   T->array[key].tail=(BinItem_rcr*)rb;
 365   T->array[key].head=val;//released lock
 366 }
 367
 368 void rcr_RETIREHASHTABLE(HashStructure *T, SESEcommon *task, int key, BinItem_rcr *b) {
 369   atomic_dec(&b->total);
 370   //Need to clear ourself out of the read bin so that we aren't resolved after being freed
 371   if(ISREADBIN(b->type)) {
 372     //Have to clear our entry out of bin if we retired early
 373
 374     if (b->status==NOTREADY) {
 375       ReadBinItem_rcr* rptr=(ReadBinItem_rcr*)b;
 376       BinElement_rcr * be = &(T->array[key]);
 377       int i;
 378       // CHECK FIRST IF next is nonnull to guarantee that b.total cannot change
 379       BinItem_rcr * val=(BinItem_rcr *)0x1;
 380       do {
 381         val=(BinItem_rcr*)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
 382       } while(val==(BinItem_rcr*)0x1);
 383
 384       for (i=0;i<rptr->index;i++) {
 385         TraverserData * td=&rptr->array[i];
 386         if (task==td->task) {
 387           //remove item from bin...
 388           td->task=NULL;
 389           break;
 390         }
 391       }
 392       be->head=val;
 393     }
 394
 395     if (b->next==NULL || b->total>0) {
 396       return;
 397     }
 398   }
 399
 400
 401   //We either have a write bin or we are at the end of a read bin
 402   BinElement_rcr * be = &(T->array[key]);
 403   {
 404     // CHECK FIRST IF next is nonnull to guarantee that b.total cannot change
 405     BinItem_rcr * val=(BinItem_rcr *)0x1;
 406     do {
 407       val=(BinItem_rcr*)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
 408     } while(val==(BinItem_rcr*)0x1);
 409
 410     // at this point have locked bin
 411     BinItem_rcr *ptr=val;
 412     BinItem_rcr *next;
 413     int haveread=FALSE;
 414     int i;
 415     while (ptr!=NULL) {
 416       next = ptr->next;
 417       if (ISREADBIN(ptr->type)) {
 418         if (ptr->status==NOTREADY) {
 419           ReadBinItem_rcr* rptr=(ReadBinItem_rcr*)ptr;
 420           for (i=0;i<rptr->index;i++) {
 421             TraverserData * td=&rptr->array[i];
 422             SESEcommon *record=td->task;
 423             if (((INTPTR)rptr->array[i].task)&PARENTBIN) {
 424               //parents go immediately
 425               atomic_dec(&rptr->item.total);
 426               record=(SESEcommon *)(((INTPTR)record)&~1ULL);
 427             }
 428             if (record!=NULL)
 429               RESOLVE(record, td->bitindex);
 430           }
 431           ptr->status=READY;
 432         }
 433         if (ptr->next==NULL) {
 434           break;
 435         }
 436         if (ptr->total!=0) {
 437           haveread=TRUE;
 438         } else if (ptr==val) {
 439           val=val->next;
 440
 441           // THE 3 POOLFREE's IN THIS FUNCTION ARE TOO EARLY:
 442           // OTHER FUNCTIONS IN THIS COMPILATION UNIT LOCK THE BIN ELEMENT
 443           // BUT MAY TOUCH THE STATUS FIELDS OF BIN ITEMS AFTER RELEASING
 444           // THE LOCK, WE HAVE TO MAKE SOME CAREFUL CHANGES TO ALLOW THE
 445           // POOLFREE's TO WORK!
 446
 447           //poolfreeinto( T->memPoolRead, ptr );
 448         }
 449       } else if (ptr->total==0) {
 450         //skip past retired item
 451         if (ptr==val) {
 452           val=val->next;
 453           //poolfreeinto( T->memPoolWrite, ptr );
 454         }
 455       } else {
 456         //write bin case
 457         if (haveread)
 458           break;
 459         if(ptr->status==NOTREADY) {
 460           WriteBinItem_rcr* wptr=(WriteBinItem_rcr*)ptr;
 461           RESOLVE((SESEcommon *)(((INTPTR)wptr->task)&~1ULL), wptr->bitindexwr);
 462           ptr->status=READY;
 463           if(((INTPTR)wptr->task)&PARENTBIN) {
 464             val=val->next;
 465             //poolfreeinto( T->memPoolWrite, ptr );
 466           } else
 467             break;
 468         } else
 469           break;
 470       }
 471       ptr = next;
 472     }
 473     be->head=val; // release lock
 474   }
 475 }
 476
 477 void RESOLVE(SESEcommon *record, bitvt mask) {
 478   int index=-1;
 479   struct rcrRecord * array=(struct rcrRecord *)(((char *)record)+record->offsetToParamRecords);
 480   while(mask!=0) {
 481     int shift=__builtin_ctzll(mask)+1;
 482     index+=shift;
 483     if (atomic_sub_and_test(1,&array[index].count)) {
 484       if(unlikely(record->classID<0)) {
 485         //parent stall...clear it
 486         psem_give_tag(record->parentsStallSem, ((SESEstall *)record)->tag);
 487         //mark the record unused
 488         BARRIER();
 489         record->rcrstatus=0;
 490 #ifndef OOO_DISABLE_TASKMEMPOOL
 491         RELEASE_REFERENCE_TO(record);
 492 #endif
 493       } else {
 494         int flag=LOCKXCHG32(&array[index].flag,0);
 495         if (flag) {
 496           if(atomic_sub_and_test(1, &(record->unresolvedDependencies)))
 497             workScheduleSubmit((void *)record);
 498         }
 499       }
 500     }
 501     mask=mask>>shift;
 502   }
 503 }