Robust/src/Runtime/oooJava/hashStructure.c

   1 #include "hashStructure.h"
   2 //#include "WaitingQueue.h"
   3 #include "mlp_lock.h"
   4 #include "mem.h"
   5 #include "classdefs.h"
   6 #include "rcr_runtime.h"
   7
   8 //NOTE: this is only temporary (for testing) and will be removed in favor of thread local variables
   9 //It's basically an array of hashStructures so we can simulate what would happen in a many-threaded version
  10 HashStructure ** allHashStructures;
  11 #define ISWRITEBIN(x) (x&BINMASK)
  12 #define ISREADBIN(x) (!(x&BINMASK))
  13 //#define POPCOUNT(x) __builtin_popcountll(x)
  14 //__builtin_popcountll
  15
  16
  17 //NOTE: only temporary
  18 void rcr_createMasterHashTableArray(int maxSize){
  19 }
  20
  21 HashStructure* rcr_createHashtable(int sizeofWaitingQueue){
  22   int i=0;
  23   HashStructure* newTable=(HashStructure*)RUNMALLOC(sizeof(HashStructure));
  24   for(i=0;i<RNUMBINS;i++){
  25     newTable->array[i].head=NULL;
  26     newTable->array[i].tail=NULL;
  27   }
  28
  29   return newTable;
  30 }
  31
  32 WriteBinItem_rcr* rcr_createWriteBinItem(){
  33   WriteBinItem_rcr* binitem=(WriteBinItem_rcr*)RUNMALLOC(sizeof(WriteBinItem_rcr));
  34   binitem->item.type=WRITEBIN;
  35   return binitem;
  36 }
  37
  38 ReadBinItem_rcr* rcr_createReadBinItem(){
  39   ReadBinItem_rcr* binitem=(ReadBinItem_rcr*)RUNMALLOC(sizeof(ReadBinItem_rcr));
  40   binitem->index=0;
  41   binitem->item.type=READBIN;
  42   return binitem;
  43 }
  44
  45 inline int rcr_generateKey(void * ptr){
  46   return (((struct ___Object___ *) ptr)->oid)&RH_MASK;
  47 }
  48
  49 inline int rcr_BWRITEBINCASE(HashStructure *T, void *ptr, SESEcommon *task, int index, int mode) {
  50   //chain of bins exists => tail is valid
  51   //if there is something in front of us, then we are not ready
  52   BinItem_rcr * val;
  53   int key=rcr_generateKey(ptr);
  54   BinElement_rcr* be= &(T->array[key]); //do not grab head from here since it's locked (i.e. = 0x1)
  55
  56   //LOCK is still needed as different threads will remove items...
  57   do {
  58     val=(BinItem_rcr *)0x1;
  59     val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
  60   } while(val==(BinItem_rcr*)0x1);
  61
  62   if (val==NULL) {
  63     BinItem_rcr * b=(BinItem_rcr*)rcr_createWriteBinItem();
  64     WriteBinItem_rcr * td = (WriteBinItem_rcr*)b;
  65     b->total=1;
  66     b->status=READY;
  67
  68     //common to both types
  69     td->task=task;
  70     td->bitindexrd=td->bitindexwr=1<<index;
  71     be->tail=b;
  72
  73     //release lock
  74     be->head=b;
  75     return READY;
  76   }
  77
  78   BinItem_rcr *bintail=be->tail;
  79   bitvt rdmask=0,wrmask=0;
  80   int status=NOTREADY;
  81
  82   if (ISWRITEBIN(bintail->type)) {
  83     WriteBinItem_rcr * td = (WriteBinItem_rcr *)bintail;
  84     //last one is to check for SESE blocks in a while loop.
  85     if(unlikely(td->task == task)) {
  86
  87       bitvt bit=1<<index;
  88       if (!(bit & td->bitindexwr)) {
  89         td->bitindexwr|=bit;
  90         td->bitindexrd|=bit;
  91         be->head=val;
  92         if (mode) {
  93           while(bintail->status!=READY) {
  94             BARRIER();
  95           }
  96           return SPECREADY;
  97         } else {
  98           return (bintail->status==READY)?SPECREADY:SPECNOTREADY;
  99         }
 100       } else {
 101         be->head=val;
 102         return SPECREADY;
 103       }
 104     }
 105   } else {
 106     TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
 107     if(unlikely(td->task == task)) {
 108       //if it matches, then we remove it and the code below will upgrade it to a write.
 109       ((ReadBinItem_rcr *)bintail)->index--;
 110       atomic_dec(&bintail->total);
 111       rdmask=td->bitindex;
 112       if (bintail->status!=READY)
 113         wrmask=rdmask;
 114       status=SPECNOTREADY;
 115     }
 116   }
 117
 118   WriteBinItem_rcr *b=rcr_createWriteBinItem();
 119   b->item.total=1;
 120   b->task=task;
 121
 122   bitvt bit=1<<index;
 123   if (wrmask&bit) {
 124     //count already includes this
 125     status=SPECREADY;
 126   }
 127   b->bitindexwr=bit|wrmask;
 128   b->bitindexrd=bit|rdmask;
 129   b->item.status=status;
 130   bintail->next=(BinItem_rcr*)b;
 131   be->tail=(BinItem_rcr*)b;
 132
 133   if (bintail->status==READY&&bintail->total==0) {
 134     //we may have to set write as ready
 135     while(val->total==0) {
 136       if (val==((BinItem_rcr *)b)) {
 137         b->item.status=READY;
 138         be->head=val;
 139         if (status&SPEC)
 140           return SPECREADY;
 141         else
 142           return READY;
 143       }
 144       val=val->next;
 145     }
 146   }
 147
 148   //RELEASE LOCK
 149   be->head=val;
 150   if (mode) {
 151     while(b->item.status==NOTREADY) {
 152       BARRIER();
 153     }
 154     return status&SPEC;
 155   } else {
 156     return status;
 157   }
 158 }
 159
 160 inline int rcr_BREADBINCASE(HashStructure *T, void *ptr, SESEcommon *task, int index, int mode) {
 161   BinItem_rcr * val;
 162   int key=rcr_generateKey(ptr);
 163   BinElement_rcr * be = &(T->array[key]);
 164
 165   //LOCK is still needed as different threads will remove items...
 166   do {
 167     val=(BinItem_rcr *)0x1;
 168     val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
 169   } while(val==(BinItem_rcr*)0x1);
 170
 171   if (val==NULL) {
 172     BinItem_rcr * b=(BinItem_rcr*)rcr_createReadBinItem();
 173     ReadBinItem_rcr* readbin=(ReadBinItem_rcr*)b;
 174     TraverserData * td = &(readbin->array[readbin->index++]);
 175     b->total=1;
 176     b->status=READY;
 177
 178     //common to both types
 179     td->task=task;
 180     td->bitindex=1<<index;
 181     be->tail=b;
 182
 183     //release lock
 184     be->head=b;
 185
 186     return READY;
 187   }
 188
 189
 190   BinItem_rcr * bintail=be->tail;
 191
 192   //check if already added item or not.
 193   if (ISWRITEBIN(bintail->type)) {
 194     WriteBinItem_rcr * td = (WriteBinItem_rcr *)bintail;
 195     if(unlikely(td->task==task)) {
 196       //RELEASE LOCK
 197       bitvt bit=1<<index;
 198       int status=bintail->status;
 199       if (!(td->bitindexrd & bit)) {
 200         td->bitindexrd|=bit;
 201         td->bitindexwr|=bit;
 202         status=status|SPEC;
 203       } else
 204         status=SPECREADY;
 205       be->head=val;
 206       if (mode) {
 207         while(bintail->status!=READY) {
 208           BARRIER();
 209         }
 210         return SPECREADY;
 211       } else {
 212         return status;
 213       }
 214     }
 215   } else {
 216     TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
 217     if (unlikely(td->task==task)) {
 218       //RELEASE LOCK
 219       bitvt bit=1<<index;
 220       int status=bintail->status;
 221       if (!(td->bitindex & bit)) {
 222         td->bitindex|=bit;
 223         status=status|SPEC;
 224       } else
 225         status=SPECREADY;
 226       be->head=val;
 227       if (mode) {
 228         while(bintail->status!=READY) {
 229           BARRIER();
 230         }
 231         return status&SPEC;
 232       } else {
 233         return status;
 234       }
 235     }
 236   }
 237
 238   if (ISREADBIN(bintail->type)) {
 239     int stat=rcr_TAILREADCASE(T, ptr, val, bintail, key, task, index);
 240     if (mode) {
 241       struct BinItem_rcr * bt=be->tail;
 242       while(bt->status!=READY) {
 243         BARRIER();
 244       }
 245       return READY;
 246     } else {
 247       return stat;
 248     }
 249   } else {
 250     rcr_TAILWRITECASE(T, ptr, val, bintail, key, task, index);
 251     if (mode) {
 252       struct BinItem_rcr * bt=be->tail;
 253       while(bt->status!=READY) {
 254         BARRIER();
 255       }
 256       return READY;
 257     } else {
 258       return NOTREADY;
 259     }
 260   }
 261 }
 262
 263
 264 int rcr_WRITEBINCASE(HashStructure *T, void *ptr, SESEcommon *task, int index) {
 265   return rcr_BWRITEBINCASE(T, ptr, task, index, 0);
 266 }
 267 int rcr_READBINCASE(HashStructure *T, void *ptr, SESEcommon * task, int index) {
 268   return rcr_BREADBINCASE(T, ptr, task, index, 0);
 269 }
 270
 271 int rcr_WTWRITEBINCASE(HashStructure *T, void *ptr, SESEcommon *task, int index) {
 272   return rcr_BWRITEBINCASE(T, ptr, task, index, 1);
 273 }
 274
 275 int rcr_WTREADBINCASE(HashStructure *T, void *ptr, SESEcommon * task, int index) {
 276   return rcr_BREADBINCASE(T, ptr, task, index, 1);
 277 }
 278
 279 int rcr_TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index) {
 280   ReadBinItem_rcr * readbintail=(ReadBinItem_rcr*)T->array[key].tail;
 281   int status, retval;
 282   TraverserData *td;
 283   if (readbintail->item.status==READY) {
 284     status=READY;
 285     retval=READY;
 286   } else {
 287     status=NOTREADY;
 288     retval=NOTREADY;
 289   }
 290
 291   if (readbintail->index==RNUMREAD) { // create new read group
 292     ReadBinItem_rcr* rb=rcr_createReadBinItem();
 293     td = &rb->array[rb->index++];
 294
 295     rb->item.total=1;
 296     rb->item.status=status;
 297     T->array[key].tail->next=(BinItem_rcr*)rb;
 298     T->array[key].tail=(BinItem_rcr*)rb;
 299   } else { // group into old tail
 300     td = &readbintail->array[readbintail->index++];
 301     atomic_inc(&readbintail->item.total);
 302   }
 303
 304   td->task=task;
 305   td->bitindex=1<<index;
 306
 307   T->array[key].head=val;//released lock
 308   return retval;
 309 }
 310
 311 void rcr_TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index) {
 312   ReadBinItem_rcr* rb=rcr_createReadBinItem();
 313   TraverserData * td = &(rb->array[rb->index++]);
 314   rb->item.total=1;
 315   rb->item.status=NOTREADY;
 316
 317   td->task=task;
 318   td->bitindex=1<<index;
 319
 320   T->array[key].tail->next=(BinItem_rcr*)rb;
 321   T->array[key].tail=(BinItem_rcr*)rb;
 322   T->array[key].head=val;//released lock
 323 }
 324
 325 void rcr_RETIREHASHTABLE(HashStructure *T, SESEcommon *task, int key) {
 326   BinElement_rcr * be = &(T->array[key]);
 327   BinItem_rcr *b=be->head;
 328
 329   if(ISREADBIN(READBIN)) {
 330     atomic_dec(&b->total);
 331     if (b->next==NULL || b->total>0) {
 332       return;
 333     }
 334   }
 335   //We either have a write bin or we are at the end of a read bin
 336
 337   {
 338     // CHECK FIRST IF next is nonnull to guarantee that b.total cannot change
 339     BinItem_rcr * val=(BinItem_rcr *)0x1;
 340     do {
 341       val=(BinItem_rcr*)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
 342     } while(val==(BinItem_rcr*)0x1);
 343
 344     // at this point have locked bin
 345     BinItem_rcr *ptr=val;
 346     int haveread=FALSE;
 347     int i;
 348     while (ptr!=NULL) {
 349       if (ISREADBIN(ptr->type)) {
 350         if (ptr->status==NOTREADY) {
 351           ReadBinItem_rcr* rptr=(ReadBinItem_rcr*)ptr;
 352           for (i=0;i<rptr->index;i++) {
 353             TraverserData * td=&rptr->array[i];
 354             if (task==td->task) {
 355               RESOLVE(td->task, td->bitindex);
 356               if (((INTPTR)rptr->array[i].task)&PARENTBIN) {
 357                 //parents go immediately
 358                 atomic_dec(&rptr->item.total);
 359               }
 360               break;
 361             }
 362           }
 363           ptr->status=READY;
 364         }
 365         if (ptr->next==NULL) {
 366           break;
 367         }
 368         if (ptr->total!=0) {
 369           haveread=TRUE;
 370         } else if (ptr==val) {
 371           val=val->next;
 372         }
 373       } else {
 374         //write bin case
 375         if (haveread)
 376           break;
 377         if(ptr->status==NOTREADY) {
 378           WriteBinItem_rcr* wptr=(WriteBinItem_rcr*)ptr;
 379           RESOLVE(wptr->task, wptr->bitindexwr);
 380           ptr->status=READY;
 381           if(((INTPTR)wptr->task)&PARENTBIN) {
 382             val=val->next;
 383           } else
 384             break;
 385         } else { // write bin is already resolved
 386           val=val->next;
 387         }
 388       }
 389       ptr=ptr->next;
 390     }
 391     be->head=val; // release lock
 392   }
 393 }
 394
 395 void RESOLVE(SESEcommon *record, bitvt mask) {
 396   int index=-1;
 397   struct rcrRecord * array=(struct rcrRecord *)(((char *)record)+record->offsetToParamRecords);
 398   while(mask!=0) {
 399     int shift=__builtin_ctzll(mask)+1;
 400     index+=shift;
 401     if (atomic_sub_and_test(1,&array[index].count)) {
 402       if(unlikely(record->classID<0)) {
 403         //parent stall...clear it
 404         psem_give_tag(record->parentsStallSem, ((SESEstall *)record)->tag);
 405         //mark the record unused
 406         BARRIER();
 407         record->rcrstatus=0;
 408       } else {
 409         int flag=LOCKXCHG32(&array[index].flag,0);
 410         if (flag) {
 411           if(atomic_sub_and_test(1, &(record->unresolvedDependencies)))
 412             workScheduleSubmit((void *)record);
 413         }
 414       }
 415     }
 416     mask=mask>>shift;
 417   }
 418 }