Robust/src/Runtime/oooJava/hashStructure.c

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