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=SPECREADY;
 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         if (status&SPEC)
 132           return SPECREADY;
 133         else
 134           return READY;
 135       }
 136       val=val->next;
 137     }
 138   }
 139
 140   //RELEASE LOCK
 141   be->head=val;
 142   return status;
 143 }
 144
 145 int rcr_READBINCASE(HashStructure *T, void *ptr, SESEcommon * task, int index) {
 146   BinItem_rcr * val;
 147   int key=rcr_generateKey(ptr);
 148   BinElement_rcr * be = &(T->array[key]);
 149
 150   //LOCK is still needed as different threads will remove items...
 151   do {
 152     val=(BinItem_rcr *)0x1;
 153     val=(BinItem_rcr *)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
 154   } while(val==(BinItem_rcr*)0x1);
 155
 156   if (val==NULL) {
 157     BinItem_rcr * b=(BinItem_rcr*)rcr_createReadBinItem();
 158     ReadBinItem_rcr* readbin=(ReadBinItem_rcr*)b;
 159     TraverserData * td = &(readbin->array[readbin->index++]);
 160     b->total=1;
 161     b->status=READY;
 162
 163     //common to both types
 164     td->task=task;
 165     td->bitindex=1<<index;
 166     be->tail=b;
 167
 168     //release lock
 169     be->head=b;
 170
 171     return READY;
 172   }
 173
 174
 175   BinItem_rcr * bintail=be->tail;
 176
 177   //check if already added item or not.
 178   if (ISWRITEBIN(bintail->type)) {
 179     WriteBinItem_rcr * td = (WriteBinItem_rcr *)bintail;
 180     if(unlikely(td->task==task)) {
 181       //RELEASE LOCK
 182       bitvt bit=1<<index;
 183       int status=bintail->status;
 184       if (!(td->bitindexrd & bit)) {
 185         td->bitindexrd|=bit;
 186         td->bitindexwr|=bit;
 187         status=status|SPEC;
 188       } else
 189         status=SPECREADY;
 190       be->head=val;
 191       return status;
 192     }
 193   } else {
 194     TraverserData * td = &((ReadBinItem_rcr *)bintail)->array[((ReadBinItem_rcr *)bintail)->index - 1];
 195     if (unlikely(td->task==task)) {
 196       //RELEASE LOCK
 197       bitvt bit=1<<index;
 198       int status=bintail->status;
 199       if (!(td->bitindex & bit)) {
 200         td->bitindex|=bit;
 201         status=status|SPEC;
 202       } else
 203         status=SPECREADY;
 204       be->head=val;
 205       return status;
 206     }
 207   }
 208
 209   if (ISREADBIN(bintail->type)) {
 210     return rcr_TAILREADCASE(T, ptr, val, bintail, key, task, index);
 211   } else {
 212     rcr_TAILWRITECASE(T, ptr, val, bintail, key, task, index);
 213     return NOTREADY;
 214   }
 215 }
 216
 217
 218 int rcr_TAILREADCASE(HashStructure *T, void * ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index) {
 219   ReadBinItem_rcr * readbintail=(ReadBinItem_rcr*)T->array[key].tail;
 220   int status, retval;
 221   TraverserData *td;
 222   if (readbintail->item.status==READY) {
 223     status=READY;
 224     retval=READY;
 225   } else {
 226     status=NOTREADY;
 227     retval=NOTREADY;
 228   }
 229
 230   if (readbintail->index==RNUMREAD) { // create new read group
 231     ReadBinItem_rcr* rb=rcr_createReadBinItem();
 232     td = &rb->array[rb->index++];
 233
 234     rb->item.total=1;
 235     rb->item.status=status;
 236     T->array[key].tail->next=(BinItem_rcr*)rb;
 237     T->array[key].tail=(BinItem_rcr*)rb;
 238   } else { // group into old tail
 239     td = &readbintail->array[readbintail->index++];
 240     atomic_inc(&readbintail->item.total);
 241   }
 242
 243   td->task=task;
 244   td->bitindex=1<<index;
 245
 246   T->array[key].head=val;//released lock
 247   return retval;
 248 }
 249
 250 void rcr_TAILWRITECASE(HashStructure *T, void *ptr, BinItem_rcr *val, BinItem_rcr *bintail, int key, SESEcommon * task, int index) {
 251   ReadBinItem_rcr* rb=rcr_createReadBinItem();
 252   TraverserData * td = &(rb->array[rb->index++]);
 253   rb->item.total=1;
 254   rb->item.status=NOTREADY;
 255
 256   td->task=task;
 257   td->bitindex=1<<index;
 258
 259   T->array[key].tail->next=(BinItem_rcr*)rb;
 260   T->array[key].tail=(BinItem_rcr*)rb;
 261   T->array[key].head=val;//released lock
 262 }
 263
 264 rcr_RETIREHASHTABLE(HashStructure *T, SESEcommon *task, int key) {
 265   BinElement_rcr * be = &(T->array[key]);
 266   BinItem_rcr *b=be->head;
 267
 268   if(ISREADBIN(READBIN)) {
 269     atomic_dec(&b->total);
 270     if (b->next==NULL || b->total>0) {
 271       return;
 272     }
 273   }
 274   //We either have a write bin or we are at the end of a read bin
 275
 276   {
 277     // CHECK FIRST IF next is nonnull to guarantee that b.total cannot change
 278     BinItem_rcr * val=(BinItem_rcr *)0x1;
 279     do {
 280       val=(BinItem_rcr*)LOCKXCHG((unsigned INTPTR*)&(be->head), (unsigned INTPTR)val);
 281     } while(val==(BinItem_rcr*)0x1);
 282
 283     // at this point have locked bin
 284     BinItem_rcr *ptr=val;
 285     int haveread=FALSE;
 286     int i;
 287     while (ptr!=NULL) {
 288       if (ISREADBIN(ptr->type)) {
 289         if (ptr->status==NOTREADY) {
 290           ReadBinItem_rcr* rptr=(ReadBinItem_rcr*)ptr;
 291           for (i=0;i<rptr->index;i++) {
 292             RESOLVE(rptr->array[i]);
 293             if (((INTPTR)rptr->array[i].task)&PARENTBIN) {
 294               //parents go immediately
 295               atomic_dec(&rptr->item.total);
 296             }
 297           }
 298           ptr->status=READY;
 299         }
 300         if (ptr->next==NULL) {
 301           break;
 302         }
 303         if (ptr->total!=0) {
 304           haveread=TRUE;
 305         } else if (ptr==val) {
 306           val=val->next;
 307         }
 308       } else {
 309         //write bin case
 310         if (haveread)
 311           break;
 312         if(ptr->status==NOTREADY) {
 313           WriteBinItem_rcr* wptr=(WriteBinItem_rcr*)ptr;
 314           RESOLVE(wptr);
 315           ptr->status=READY;
 316           if(((INTPTR)wptr->task)&PARENTBIN) {
 317             val=val->next;
 318           } else
 319             break;
 320         } else { // write bin is already resolved
 321           val=val->next;
 322         }
 323       }
 324       ptr=ptr->next;
 325     }
 326     be->head=val; // release lock
 327   }
 328 }