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