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
   7 //NOTE: this is only temporary (for testing) and will be removed in favor of thread local variables
   8 //It's basically an array of hashStructures so we can simulate what would happen in a many-threaded version
   9 HashStructure ** allHashStructures;
  10 #define ISWRITEBIN(x) (x&BINMASK)
  11 #define ISREADBIN(x) (!(x&BINMASK))
  12 //#define POPCOUNT(x) __builtin_popcountll(x)
  13 //__builtin_popcountll
  14 #define RESOLVE(x)
  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
  51 int rcr_WRITEBINCASE(HashStructure *T, void *ptr, SESEcommon *task, int index) {
  52   //chain of bins exists => tail is valid
  53   //if there is something in front of us, then we are not ready
  54   BinItem_rcr * val;
  55   int key=rcr_generateKey(ptr);
  56   BinElement_rcr* be= &(T->array[key]); //do not grab head from here since it's locked (i.e. = 0x1)
  57
  58   //LOCK is still needed as different threads will remove items...
  59   do {
  60     val=(BinItem_rcr *)0x1;
  61     val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
  62   } while(val==(BinItem_rcr*)0x1);
  63
  64   if (val==NULL) {
  65     BinItem_rcr * b=(BinItem_rcr*)rcr_createWriteBinItem();
  66     WriteBinItem_rcr * td = (WriteBinItem_rcr*)b;
  67     b->total=1;
  68     b->status=READY;
  69
  70     //common to both types
  71     td->task=task;
  72     td->bitindexrd=td->bitindexwr=1<<index;
  73     be->tail=b;
  74
  75     //release lock
  76     be->head=b;
  77     return READY;
  78   }
  79
  80   BinItem_rcr *bintail=be->tail;
  81   bitvt rdmask=0,wrmask=0;
  82   int status=NOTREADY;
  83
  84   if (ISWRITEBIN(bintail->type)) {
  85     WriteBinItem_rcr * td = (WriteBinItem_rcr *)bintail;
  86     //last one is to check for SESE blocks in a while loop.
  87     if(unlikely(td->task == task)) {
  88       be->head=val;
  89       bitvt bit=1<<index;
  90       if (!(bit & td->bitindexwr)) {
  91         td->bitindexwr|=bit;
  92         td->bitindexrd|=bit;
  93         return (bintail->status==READY)?SPECREADY:SPECNOTREADY;
  94       } else
  95         return SPECREADY;
  96     }
  97   } else {
  98     TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
  99     if(unlikely(td->task == task)) {
 100       //if it matches, then we remove it and the code below will upgrade it to a write.
 101       ((ReadBinItem_rcr *)bintail)->index--;
 102       atomic_dec(&bintail->total);
 103       rdmask=td->bitindex;
 104       if (bintail->status!=READY)
 105         wrmask=rdmask;
 106       status=SPECNOTREADY;
 107     }
 108   }
 109
 110   WriteBinItem_rcr *b=rcr_createWriteBinItem();
 111   b->item.total=1;
 112   b->task=task;
 113
 114   bitvt bit=1<<index;
 115   if (wrmask&bit) {
 116     //count already includes this
 117     status=READY;
 118   }
 119   b->bitindexwr=bit|wrmask;
 120   b->bitindexrd=bit|rdmask;
 121   b->item.status=status;
 122   bintail->next=(BinItem_rcr*)b;
 123   be->tail=(BinItem_rcr*)b;
 124
 125   if (bintail->status==READY&&bintail->total==0) {
 126     //we may have to set write as ready
 127     while(val->total==0) {
 128       if (val==((BinItem_rcr *)b)) {
 129         b->item.status=READY;
 130         be->head=val;
 131         return READY;
 132       }
 133       val=val->next;
 134     }
 135   }
 136
 137   //RELEASE LOCK
 138   be->head=val;
 139   return status;
 140 }
 141
 142 int rcr_READBINCASE(HashStructure *T, void *ptr, SESEcommon * task, int index) {
 143   BinItem_rcr * val;
 144   int key=rcr_generateKey(ptr);
 145   BinElement_rcr * be = &(T->array[key]);
 146
 147   //LOCK is still needed as different threads will remove items...
 148   do {
 149     val=(BinItem_rcr *)0x1;
 150     val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
 151   } while(val==(BinItem_rcr*)0x1);
 152
 153   if (val==NULL) {
 154     BinItem_rcr * b=(BinItem_rcr*)rcr_createReadBinItem();
 155     ReadBinItem_rcr* readbin=(ReadBinItem_rcr*)b;
 156     TraverserData * td = &(readbin->array[readbin->index++]);
 157     b->total=1;
 158     b->status=READY;
 159
 160     //common to both types
 161     td->task=task;
 162     td->bitindex=1<<index;
 163     be->tail=b;
 164
 165     //release lock
 166     be->head=b;
 167
 168     return READY;
 169   }
 170
 171
 172   BinItem_rcr * bintail=be->tail;
 173
 174   //check if already added item or not.
 175   if (ISWRITEBIN(bintail->type)) {
 176     WriteBinItem_rcr * td = (WriteBinItem_rcr *)bintail;
 177     if(unlikely(td->task==task)) {
 178       //RELEASE LOCK
 179       bitvt bit=1<<index;
 180       int status=bintail->status;
 181       if (!(td->bitindexrd & bit)) {
 182         td->bitindexrd|=bit;
 183         td->bitindexwr|=bit;
 184         if (status==NOTREADY)
 185           status=SPECNOTREADY;
 186       } else
 187         status=READY;
 188       be->head=val;
 189       return status;
 190     }
 191   } else {
 192     TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
 193     if (unlikely(td->task==task)) {
 194       //RELEASE LOCK
 195       bitvt bit=1<<index;
 196       int status=bintail->status;
 197       if (!(td->bitindex & bit)) {
 198         td->bitindex|=bit;
 199         if (status==NOTREADY)
 200           status=SPECNOTREADY;
 201       } else
 202         status=READY;
 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 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             RESOLVE(rptr->array[i]);
 292             if (((INTPTR)rptr->array[i].task)&PARENTBIN) {
 293               //parents go immediately
 294               atomic_dec(&rptr->item.total);
 295             }
 296           }
 297           ptr->status=READY;
 298         }
 299         if (ptr->next==NULL) {
 300           break;
 301         }
 302         if (ptr->total!=0) {
 303           haveread=TRUE;
 304         } else if (ptr==val) {
 305           val=val->next;
 306         }
 307       } else {
 308         //write bin case
 309         if (haveread)
 310           break;
 311         if(ptr->status==NOTREADY) {
 312           WriteBinItem_rcr* wptr=(WriteBinItem_rcr*)ptr;
 313           RESOLVE(wptr);
 314           ptr->status=READY;
 315           if(((INTPTR)wptr->task)&PARENTBIN) {
 316             val=val->next;
 317           } else
 318             break;
 319         } else { // write bin is already resolved
 320           val=val->next;
 321         }
 322       }
 323       ptr=ptr->next;
 324     }
 325     be->head=val; // release lock
 326   }
 327 }