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 //consider SPEC flag
  50 int rcr_WRITEBINCASE(HashStructure *T, void *ptr, SESEcommon *task, int index) {
  51   //chain of bins exists => tail is valid
  52   //if there is something in front of us, then we are not ready
  53   BinItem_rcr * val;
  54   int key=rcr_generateKey(ptr);
  55   BinElement_rcr* be= &(T->array[key]); //do not grab head from here since it's locked (i.e. = 0x1)
  56
  57   //LOCK is still needed as different threads will remove items...
  58   do {
  59     val=(BinItem_rcr *)0x1;
  60     val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
  61   } while(val==(BinItem_rcr*)0x1);
  62
  63   if (val==NULL) {
  64     BinItem_rcr * b=(BinItem_rcr*)rcr_createWriteBinItem();
  65     WriteBinItem_rcr * td = (WriteBinItem_rcr*)b;
  66     b->total=1;
  67     b->status=READY;
  68
  69     //common to both types
  70     td->task=task;
  71     td->bitindexrd=td->bitindexwr=1<<index;
  72     be->tail=b;
  73
  74     //release lock
  75     be->head=b;
  76     return READY;
  77   }
  78
  79   BinItem_rcr *bintail=be->tail;
  80   bitvt rdmask=0,wrmask=0;
  81   int status=NOTREADY;
  82
  83   if (ISWRITEBIN(bintail->type)) {
  84     WriteBinItem_rcr * td = (WriteBinItem_rcr *)bintail;
  85     //last one is to check for SESE blocks in a while loop.
  86     if(unlikely(td->task == task)) {
  87       be->head=val;
  88       bitvt bit=1<<index;
  89       if (!(bit & td->bitindexwr)) {
  90         td->bitindexwr|=bit;
  91         td->bitindexrd|=bit;
  92         return (bintail->status==READY)?SPECREADY:SPECNOTREADY;
  93       } else
  94         return SPECREADY;
  95     }
  96   } else {
  97     TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
  98     if(unlikely(td->task == task)) {
  99       //if it matches, then we remove it and the code below will upgrade it to a write.
 100       ((ReadBinItem_rcr *)bintail)->index--;
 101       atomic_dec(&bintail->total);
 102       rdmask=td->bitindex;
 103       if (bintail->status!=READY)
 104         wrmask=rdmask;
 105       status=SPECNOTREADY;
 106     }
 107   }
 108
 109   WriteBinItem_rcr *b=rcr_createWriteBinItem();
 110   b->item.total=1;
 111   b->task=task;
 112
 113   bitvt bit=1<<index;
 114   if (wrmask&bit) {
 115     //count already includes this
 116     status=SPECREADY;
 117   }
 118   b->bitindexwr=bit|wrmask;
 119   b->bitindexrd=bit|rdmask;
 120   b->item.status=status;
 121   bintail->next=(BinItem_rcr*)b;
 122   be->tail=(BinItem_rcr*)b;
 123
 124   if (bintail->status==READY&&bintail->total==0) {
 125     //we may have to set write as ready
 126     while(val->total==0) {
 127       if (val==((BinItem_rcr *)b)) {
 128         b->item.status=READY;
 129         be->head=val;
 130         if (status&SPEC)
 131           return SPECREADY;
 132         else
 133           return READY;
 134       }
 135       val=val->next;
 136     }
 137   }
 138
 139   //RELEASE LOCK
 140   be->head=val;
 141   return status;
 142 }
 143
 144 int rcr_READBINCASE(HashStructure *T, void *ptr, SESEcommon * task, int index) {
 145   BinItem_rcr * val;
 146   int key=rcr_generateKey(ptr);
 147   BinElement_rcr * be = &(T->array[key]);
 148
 149   //LOCK is still needed as different threads will remove items...
 150   do {
 151     val=(BinItem_rcr *)0x1;
 152     val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
 153   } while(val==(BinItem_rcr*)0x1);
 154
 155   if (val==NULL) {
 156     BinItem_rcr * b=(BinItem_rcr*)rcr_createReadBinItem();
 157     ReadBinItem_rcr* readbin=(ReadBinItem_rcr*)b;
 158     TraverserData * td = &(readbin->array[readbin->index++]);
 159     b->total=1;
 160     b->status=READY;
 161
 162     //common to both types
 163     td->task=task;
 164     td->bitindex=1<<index;
 165     be->tail=b;
 166
 167     //release lock
 168     be->head=b;
 169
 170     return READY;
 171   }
 172
 173
 174   BinItem_rcr * bintail=be->tail;
 175
 176   //check if already added item or not.
 177   if (ISWRITEBIN(bintail->type)) {
 178     WriteBinItem_rcr * td = (WriteBinItem_rcr *)bintail;
 179     if(unlikely(td->task==task)) {
 180       //RELEASE LOCK
 181       bitvt bit=1<<index;
 182       int status=bintail->status;
 183       if (!(td->bitindexrd & bit)) {
 184         td->bitindexrd|=bit;
 185         td->bitindexwr|=bit;
 186         status=status|SPEC;
 187       } else
 188         status=SPECREADY;
 189       be->head=val;
 190       return status;
 191     }
 192   } else {
 193     TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
 194     if (unlikely(td->task==task)) {
 195       //RELEASE LOCK
 196       bitvt bit=1<<index;
 197       int status=bintail->status;
 198       if (!(td->bitindex & bit)) {
 199         td->bitindex|=bit;
 200         status=status|SPEC;
 201       } else
 202         status=SPECREADY;
 203       be->head=val;
 204       return status;
 205     }
 206   }
 207
 208   if (ISREADBIN(bintail->type)) {
 209     return rcr_TAILREADCASE(T, ptr, val, bintail, key, task, index);
 210   } else {
 211     rcr_TAILWRITECASE(T, ptr, val, bintail, key, task, index);
 212     return NOTREADY;
 213   }
 214 }
 215
 216
 217 int rcr_TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index) {
 218   ReadBinItem_rcr * readbintail=(ReadBinItem_rcr*)T->array[key].tail;
 219   int status, retval;
 220   TraverserData *td;
 221   if (readbintail->item.status==READY) {
 222     status=READY;
 223     retval=READY;
 224   } else {
 225     status=NOTREADY;
 226     retval=NOTREADY;
 227   }
 228
 229   if (readbintail->index==RNUMREAD) { // create new read group
 230     ReadBinItem_rcr* rb=rcr_createReadBinItem();
 231     td = &rb->array[rb->index++];
 232
 233     rb->item.total=1;
 234     rb->item.status=status;
 235     T->array[key].tail->next=(BinItem_rcr*)rb;
 236     T->array[key].tail=(BinItem_rcr*)rb;
 237   } else { // group into old tail
 238     td = &readbintail->array[readbintail->index++];
 239     atomic_inc(&readbintail->item.total);
 240   }
 241
 242   td->task=task;
 243   td->bitindex=1<<index;
 244
 245   T->array[key].head=val;//released lock
 246   return retval;
 247 }
 248
 249 void rcr_TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index) {
 250   ReadBinItem_rcr* rb=rcr_createReadBinItem();
 251   TraverserData * td = &(rb->array[rb->index++]);
 252   rb->item.total=1;
 253   rb->item.status=NOTREADY;
 254
 255   td->task=task;
 256   td->bitindex=1<<index;
 257
 258   T->array[key].tail->next=(BinItem_rcr*)rb;
 259   T->array[key].tail=(BinItem_rcr*)rb;
 260   T->array[key].head=val;//released lock
 261 }
 262
 263 void rcr_RETIREHASHTABLE(HashStructure *T, SESEcommon *task, int key) {
 264   BinElement_rcr * be = &(T->array[key]);
 265   BinItem_rcr *b=be->head;
 266
 267   if(ISREADBIN(READBIN)) {
 268     atomic_dec(&b->total);
 269     if (b->next==NULL || b->total>0) {
 270       return;
 271     }
 272   }
 273   //We either have a write bin or we are at the end of a read bin
 274
 275   {
 276     // CHECK FIRST IF next is nonnull to guarantee that b.total cannot change
 277     BinItem_rcr * val=(BinItem_rcr *)0x1;
 278     do {
 279       val=(BinItem_rcr*)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
 280     } while(val==(BinItem_rcr*)0x1);
 281
 282     // at this point have locked bin
 283     BinItem_rcr *ptr=val;
 284     int haveread=FALSE;
 285     int i;
 286     while (ptr!=NULL) {
 287       if (ISREADBIN(ptr->type)) {
 288         if (ptr->status==NOTREADY) {
 289           ReadBinItem_rcr* rptr=(ReadBinItem_rcr*)ptr;
 290           for (i=0;i<rptr->index;i++) {
 291             TraverserData * td=&rptr->array[i];
 292             if (task==td->task) {
 293               RESOLVE(td->task, td->bitindex);
 294               if (((INTPTR)rptr->array[i].task)&PARENTBIN) {
 295                 //parents go immediately
 296                 atomic_dec(&rptr->item.total);
 297               }
 298               break;
 299             }
 300           }
 301           ptr->status=READY;
 302         }
 303         if (ptr->next==NULL) {
 304           break;
 305         }
 306         if (ptr->total!=0) {
 307           haveread=TRUE;
 308         } else if (ptr==val) {
 309           val=val->next;
 310         }
 311       } else {
 312         //write bin case
 313         if (haveread)
 314           break;
 315         if(ptr->status==NOTREADY) {
 316           WriteBinItem_rcr* wptr=(WriteBinItem_rcr*)ptr;
 317           RESOLVE(wptr->task, wptr->bitindexwr);
 318           ptr->status=READY;
 319           if(((INTPTR)wptr->task)&PARENTBIN) {
 320             val=val->next;
 321           } else
 322             break;
 323         } else { // write bin is already resolved
 324           val=val->next;
 325         }
 326       }
 327       ptr=ptr->next;
 328     }
 329     be->head=val; // release lock
 330   }
 331 }
 332
 333 void RESOLVE(SESEcommon *record, bitvt mask) {
 334   int index=-1;
 335   struct rcrRecord * array=(struct rcrRecord *)(((char *)record)+record->offsetToParamRecords);
 336   while(mask!=0) {
 337     int shift=__builtin_ctzll(mask)+1;
 338     index+=shift;
 339     if (atomic_sub_and_test(1,&array[index].count)) {
 340       int flag=LOCKXCHG32(&array[index].flag,0);
 341       if (flag) {
 342         if(atomic_sub_and_test(1, &(record->unresolvedDependencies)))
 343           workScheduleSubmit((void *)record);
 344       }
 345     }
 346     mask=mask>>shift;
 347   }
 348 }