Robust/src/Runtime/mlp_runtime.c

   1 #include "runtime.h"
   2
   3 #include <stdlib.h>
   4 #include <stdio.h>
   5 #include <assert.h>
   6
   7 #include "mem.h"
   8 #include "mlp_runtime.h"
   9 #include "workschedule.h"
  10 #include "methodheaders.h"
  11
  12
  13 __thread SESEcommon* runningSESE;
  14 __thread int childSESE=0;
  15
  16 __thread psemaphore runningSESEstallSem;
  17
  18
  19 // this is for using a memPool to allocate task records,
  20 // pass this into the poolcreate so it will run your
  21 // custom init code ONLY for fresh records, reused records
  22 // can be returned as is
  23 void freshTaskRecordInitializer( void* seseRecord ) {
  24   SESEcommon* c = (SESEcommon*) seseRecord;
  25   pthread_cond_init( &(c->runningChildrenCond), NULL );
  26   pthread_mutex_init( &(c->lock), NULL );
  27   c->refCount = 0;
  28   //c->fresh = 1;
  29 }
  30
  31
  32
  33
  34 void* mlpAllocSESErecord( int size ) {
  35   void* newrec = RUNMALLOC( size );
  36   if( newrec == 0 ) {
  37     printf( "mlpAllocSESErecord did not obtain memory!\n" );
  38     exit( -1 );
  39   }
  40   return newrec;
  41 }
  42
  43 void mlpFreeSESErecord( SESEcommon* seseRecord ) {
  44   RUNFREE( seseRecord );
  45 }
  46
  47 MemoryQueue** mlpCreateMemoryQueueArray(int numMemoryQueue){
  48   int i;
  49   MemoryQueue** newMemoryQueue=(MemoryQueue**)RUNMALLOC( sizeof( MemoryQueue* ) * numMemoryQueue );
  50   for(i=0; i<numMemoryQueue; i++){
  51     newMemoryQueue[i]=createMemoryQueue();
  52   }
  53   return newMemoryQueue;
  54 }
  55
  56 REntry* mlpCreateFineREntry(MemoryQueue* q, int type, SESEcommon* seseToIssue, void* dynID){
  57 #ifdef OOO_DISABLE_TASKMEMPOOL
  58   REntry* newREntry=(REntry*)RUNMALLOC(sizeof(REntry));
  59 #else
  60   REntry* newREntry=poolalloc(q->rentrypool);
  61 #endif
  62   newREntry->type=type;
  63   newREntry->seseRec=seseToIssue;
  64   newREntry->pointer=dynID;
  65   return newREntry;
  66 }
  67
  68 #ifdef RCR
  69 REntry* mlpCreateREntry(MemoryQueue* q, int type, SESEcommon* seseToIssue, INTPTR mask) {
  70 #else
  71 REntry* mlpCreateREntry(MemoryQueue* q, int type, SESEcommon* seseToIssue) {
  72 #endif
  73 #ifdef OOO_DISABLE_TASKMEMPOOL
  74   REntry* newREntry=(REntry*)RUNMALLOC(sizeof(REntry));
  75 #else
  76   REntry* newREntry=poolalloc(q->rentrypool);
  77 #endif
  78   newREntry->type=type;
  79   newREntry->seseRec=seseToIssue;
  80 #ifdef RCR
  81   newREntry->mask=mask;
  82 #endif
  83   return newREntry;
  84 }
  85
  86 int isParent(REntry *r) {
  87   if (r->type==PARENTREAD || r->type==PARENTWRITE || r->type==PARENTCOARSE) {
  88     return TRUE;
  89   } else {
  90     return FALSE;
  91   }
  92 }
  93
  94 int isParentCoarse(REntry *r){
  95   if (r->type==PARENTCOARSE){
  96     return TRUE;
  97   }else{
  98     return FALSE;
  99   }
 100 }
 101
 102 int isFineRead(REntry *r) {
 103   if (r->type==READ || r->type==PARENTREAD) {
 104     return TRUE;
 105   } else {
 106     return FALSE;
 107   }
 108 }
 109
 110 int isFineWrite(REntry *r) {
 111   if (r->type==WRITE || r->type==PARENTWRITE) {
 112     return TRUE;
 113   } else {
 114     return FALSE;
 115   }
 116 }
 117
 118 int isCoarse(REntry *r){
 119   if(r->type==COARSE || r->type==PARENTCOARSE){
 120     return TRUE;
 121   } else {
 122     return FALSE;
 123   }
 124 }
 125
 126 int isSCC(REntry *r){
 127   if(r->type==SCCITEM){
 128     return TRUE;
 129   } else {
 130     return FALSE;
 131   }
 132 }
 133
 134 int isSingleItem(MemoryQueueItem *qItem){
 135   if(qItem->type==SINGLEITEM){
 136     return TRUE;
 137   } else {
 138     return FALSE;
 139   }
 140 }
 141
 142 int isHashtable(MemoryQueueItem *qItem){
 143   if(qItem->type==HASHTABLE){
 144     return TRUE;
 145   } else {
 146     return FALSE;
 147   }
 148 }
 149
 150 int isVector(MemoryQueueItem *qItem){
 151   if(qItem->type==VECTOR){
 152     return TRUE;
 153   } else {
 154     return FALSE;
 155   }
 156 }
 157
 158 int isReadBinItem(BinItem* b){
 159   if(b->type==READBIN){
 160     return TRUE;
 161   }else{
 162     return FALSE;
 163   }
 164 }
 165
 166 int isWriteBinItem(BinItem* b){
 167   if(b->type==WRITEBIN){
 168     return TRUE;
 169   }else{
 170     return FALSE;
 171   }
 172 }
 173
 174 int generateKey(unsigned int data){
 175   return (data&H_MASK);
 176 }
 177
 178 Hashtable* createHashtable(){
 179   int i=0;
 180   Hashtable* newTable=(Hashtable*)RUNMALLOC(sizeof(Hashtable));
 181   newTable->item.type=HASHTABLE;
 182   for(i=0;i<NUMBINS;i++){
 183     newTable->array[i]=(BinElement*)RUNMALLOC(sizeof(BinElement));
 184     newTable->array[i]->head=NULL;
 185     newTable->array[i]->tail=NULL;
 186   }
 187   newTable->unresolvedQueue=NULL;
 188   return newTable;
 189 }
 190
 191 WriteBinItem* createWriteBinItem(){
 192   WriteBinItem* binitem=(WriteBinItem*)RUNMALLOC(sizeof(WriteBinItem));
 193   binitem->item.type=WRITEBIN;
 194   return binitem;
 195 }
 196
 197 ReadBinItem* createReadBinItem(){
 198   ReadBinItem* binitem=(ReadBinItem*)RUNMALLOC(sizeof(ReadBinItem));
 199   binitem->index=0;
 200   binitem->item.type=READBIN;
 201   return binitem;
 202 }
 203
 204 Vector* createVector(){
 205   Vector* vector=(Vector*)RUNMALLOC(sizeof(Vector));
 206   vector->index=0;
 207   vector->item.type=VECTOR;
 208   return vector;
 209 }
 210
 211 SCC* createSCC(){
 212   SCC* scc=(SCC*)RUNMALLOC(sizeof(SCC));
 213   scc->item.type=SINGLEITEM;
 214   return scc;
 215 }
 216
 217 MemoryQueue* createMemoryQueue(){
 218   MemoryQueue* queue = (MemoryQueue*)RUNMALLOC(sizeof(MemoryQueue));
 219   MemoryQueueItem* dummy=(MemoryQueueItem*)RUNMALLOC(sizeof(MemoryQueueItem));
 220   dummy->type=3; // dummy type
 221   dummy->total=0;
 222   dummy->status=READY;
 223   queue->head = dummy;
 224   queue->tail = dummy;
 225 #ifndef OOO_DISABLE_TASKMEMPOOL
 226   queue->rentrypool = poolcreate( sizeof(REntry), NULL );
 227 #endif
 228   return queue;
 229 }
 230
 231 int ADDRENTRY(MemoryQueue * q, REntry * r) {
 232   if (isFineRead(r) || isFineWrite(r)) {
 233     return ADDTABLE(q, r);
 234   } else if (isCoarse(r)) {
 235     return ADDVECTOR(q, r);
 236   } else if (isSCC(r)) {
 237     return ADDSCC(q, r);
 238   }
 239 }
 240
 241 int ADDTABLE(MemoryQueue *q, REntry *r) {
 242   if(!isHashtable(q->tail)) {
 243     //Fast Case
 244     MemoryQueueItem* tail=q->tail;
 245     if (isParent(r) && tail->total==0 && q->tail==q->head) {
 246       return READY;
 247     }
 248
 249     //Add table
 250     Hashtable* h=createHashtable();
 251     tail->next=(MemoryQueueItem*)h;
 252     //************NEED memory barrier here to ensure compiler does not cache Q.tail.status********
 253     if (BARRIER() && tail->status==READY && tail->total==0 && q->tail==q->head) {
 254       //previous Q item is finished
 255       h->item.status=READY;
 256     }
 257     q->tail=(MemoryQueueItem*)h;
 258     // handle the the queue item case
 259     if(q->head->type==3){
 260       q->head=(MemoryQueueItem*)h;
 261     }
 262   }
 263
 264   //at this point, have table
 265   Hashtable* table=(Hashtable*)q->tail;
 266   r->qitem=(MemoryQueueItem *) table; // set rentry's hashtable
 267   if( *(r->pointer)==0 ||
 268       ( *(r->pointer)!=0 &&
 269         BARRIER() &&
 270         table->unresolvedQueue!=NULL
 271         )
 272    ){
 273     struct Queue* val;
 274     // grab lock on the queue
 275     do {
 276       val=(struct Queue*)0x1;
 277       val=(struct Queue*)LOCKXCHG((unsigned INTPTR*)&(table->unresolvedQueue), (unsigned INTPTR)val);
 278     } while(val==(struct Queue*)0x1);
 279     if(val==NULL){
 280       //queue is null, first case
 281       if(*(r->pointer)!=0){
 282         // check whether pointer is already resolved, or not.
 283         table->unresolvedQueue=NULL; //released lock;
 284         return ADDTABLEITEM(table,r,TRUE);
 285       }
 286       struct Queue* queue=createQueue();
 287       addNewItemBack(queue,r);
 288       atomic_inc(&table->item.total);
 289       table->unresolvedQueue=queue; // expose new queue
 290     }else{
 291       // add unresolved rentry at the end of the queue.
 292       addNewItemBack(val,r);
 293       atomic_inc(&table->item.total);
 294       table->unresolvedQueue=val; // released lock
 295     }
 296     return NOTREADY;
 297   }
 298   BinItem * val;
 299
 300   // leave this--its a helpful test when things are going bonkers
 301   //if( OBJPTRPTR_2_OBJOID( r->pointer ) == 0 ) {
 302   //  // we started numbering object ID's at 1, if we try to
 303   //  // hash a zero oid, something BAD is about to happen!
 304   //  printf( "Tried to insert invalid object type=%d into mem Q hashtable!\n",
 305   //          OBJPTRPTR_2_OBJTYPE( r->pointer ) );
 306   //  exit( -1 );
 307   //}
 308   int key=generateKey( OBJPTRPTR_2_OBJOID( r->pointer ) );
 309   do {
 310     val=(BinItem*)0x1;
 311     BinElement* bin=table->array[key];
 312     val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(bin->head), (unsigned INTPTR)val);//note...talk to me about optimizations here.
 313   } while(val==(BinItem*)0x1);
 314   //at this point have locked bin
 315   if (val==NULL) {
 316     return EMPTYBINCASE(table, table->array[key], r, TRUE);
 317   } else {
 318     if (isFineWrite(r)) {
 319       return WRITEBINCASE(table, r, val, key, TRUE);
 320     } else if (isFineRead(r)) {
 321       return READBINCASE(table, r, val, key, TRUE);
 322     }
 323   }
 324 }
 325
 326 int ADDTABLEITEM(Hashtable* table, REntry* r, int inc){
 327
 328   BinItem * val;
 329   int key=generateKey( OBJPTRPTR_2_OBJOID( r->pointer ) );
 330   do {
 331     val=(BinItem*)0x1;
 332     BinElement* bin=table->array[key];
 333     val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(bin->head), (unsigned INTPTR)val);
 334   } while(val==(BinItem*)0x1);
 335   //at this point have locked bin
 336   if (val==NULL) {
 337     return EMPTYBINCASE(table, table->array[key], r, inc);
 338   } else {
 339     if (isFineWrite(r)) {
 340       return WRITEBINCASE(table, r, val, key, inc);
 341     } else if (isFineRead(r)) {
 342       return READBINCASE(table, r, val, key, inc);
 343     }
 344   }
 345 }
 346
 347 int EMPTYBINCASE(Hashtable *T, BinElement* be, REntry *r, int inc) {
 348   int retval;
 349   BinItem* b;
 350   if (isFineWrite(r)) {
 351     b=(BinItem*)createWriteBinItem();
 352     ((WriteBinItem*)b)->val=r;//<-only different statement
 353   } else if (isFineRead(r)) {
 354     b=(BinItem*)createReadBinItem();
 355     ReadBinItem* readbin=(ReadBinItem*)b;
 356     readbin->array[readbin->index++]=r;
 357   }
 358   b->total=1;
 359
 360   if (T->item.status==READY) {
 361     //current entry is ready
 362     b->status=READY;
 363     retval=READY;
 364     if (isParent(r)) {
 365       be->head=NULL; // released lock
 366       return retval;
 367     }
 368   } else {
 369     b->status=NOTREADY;
 370     retval=NOTREADY;
 371   }
 372
 373   if(inc){
 374     atomic_inc(&T->item.total);
 375   }
 376   r->qitem=(MemoryQueueItem *)T;
 377   r->binitem=b;
 378   be->tail=b;
 379   be->head=b;//released lock
 380   return retval;
 381 }
 382
 383 int WRITEBINCASE(Hashtable *T, REntry *r, BinItem *val, int key, int inc) {
 384   //chain of bins exists => tail is valid
 385   //if there is something in front of us, then we are not ready
 386
 387   int retval=NOTREADY;
 388   BinElement* be=T->array[key];
 389
 390   BinItem *bintail=be->tail;
 391
 392   WriteBinItem *b=createWriteBinItem();
 393   b->val=r;
 394   b->item.total=1;
 395
 396   // note: If current table clears all dependencies, then write bin is ready
 397
 398
 399   if(inc){
 400     atomic_inc(&T->item.total);
 401   }
 402
 403   r->qitem=(MemoryQueueItem *)T;
 404   r->binitem=(BinItem*)b;
 405
 406   be->tail->next=(BinItem*)b;
 407   //need to check if we can go...
 408   BARRIER();
 409   if (T->item.status==READY) {
 410     for(;val!=NULL;val=val->next) {
 411       if (val==((BinItem *)b)) {
 412         //ready to retire
 413         retval=READY;
 414         if (isParent(r)) {
 415           b->item.status=retval;//unsure if really needed at this point..
 416           be->head=NULL; // released lock
 417           return retval;
 418         }
 419         break;
 420       } else if (val->total!=0) {
 421         break;
 422       }
 423     }
 424   }
 425
 426   b->item.status=retval;
 427   be->tail=(BinItem*)b;
 428   be->head=val;
 429   return retval;
 430 }
 431
 432 int READBINCASE(Hashtable *T, REntry *r, BinItem *val, int key, int inc) {
 433   BinItem * bintail=T->array[key]->tail;
 434   if (isReadBinItem(bintail)) {
 435     return TAILREADCASE(T, r, val, bintail, key, inc);
 436   } else if (!isReadBinItem(bintail)) {
 437     TAILWRITECASE(T, r, val, bintail, key, inc);
 438     return NOTREADY;
 439   }
 440 }
 441
 442 int TAILREADCASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key, int inc) {
 443   ReadBinItem * readbintail=(ReadBinItem*)T->array[key]->tail;
 444   int status, retval;
 445   if (readbintail->item.status==READY) {
 446     status=READY;
 447     retval=READY;
 448     if (isParent(r)) {
 449       T->array[key]->head=val;//released lock
 450       return READY;
 451     }
 452   } else {
 453     status=NOTREADY;
 454     retval=NOTREADY;
 455   }
 456
 457   if (readbintail->index==NUMREAD) { // create new read group
 458     ReadBinItem* rb=createReadBinItem();
 459     rb->array[rb->index++]=r;
 460     rb->item.total=1;//safe only because item could not have started
 461     rb->item.status=status;
 462     T->array[key]->tail->next=(BinItem*)rb;
 463     T->array[key]->tail=(BinItem*)rb;
 464     r->binitem=(BinItem*)rb;
 465   } else { // group into old tail
 466     readbintail->array[readbintail->index++]=r;
 467     atomic_inc(&readbintail->item.total);
 468     r->binitem=(BinItem*)readbintail;
 469   }
 470   if(inc){
 471     atomic_inc(&T->item.total);
 472   }
 473   r->qitem=(MemoryQueueItem *)T;
 474   T->array[key]->head=val;//released lock
 475   return retval;
 476 }
 477
 478 void TAILWRITECASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key, int inc) {
 479   //  WriteBinItem* wb=createWriteBinItem();
 480   //wb->val=r;
 481   //wb->item.total=1;//safe because item could not have started
 482   //wb->item.status=NOTREADY;
 483   ReadBinItem* rb=createReadBinItem();
 484   rb->array[rb->index++]=r;
 485   rb->item.total=1;//safe because item could not have started
 486   rb->item.status=NOTREADY;
 487   if(inc){
 488     atomic_inc(&T->item.total);
 489   }
 490   r->qitem=(MemoryQueueItem *)T;
 491   r->binitem=(BinItem*)rb;
 492   T->array[key]->tail->next=(BinItem*)rb;
 493   T->array[key]->tail=(BinItem*)rb;
 494   T->array[key]->head=val;//released lock
 495 }
 496
 497 int ADDVECTOR(MemoryQueue *Q, REntry *r) {
 498   if(!isVector(Q->tail)) {
 499     //Fast Case
 500     if (isParentCoarse(r) && Q->tail->total==0 && Q->tail==Q->head) {
 501       return READY;
 502     }
 503
 504     //added vector
 505     Vector* V=createVector();
 506     Q->tail->next=(MemoryQueueItem*)V;
 507     //************NEED memory barrier here to ensure compiler does not cache Q.tail.status******
 508     if (BARRIER() && Q->tail->status==READY&&Q->tail->total==0) {
 509       //previous Q item is finished
 510       V->item.status=READY;
 511     }
 512     Q->tail=(MemoryQueueItem*)V;
 513     // handle the the queue item case
 514     if(Q->head->type==3){
 515       Q->head=(MemoryQueueItem*)V;
 516     }
 517   }
 518   //at this point, have vector
 519   Vector* V=(Vector*)Q->tail;
 520   if (V->index==NUMITEMS) {
 521     //vector is full
 522     //added vector
 523     V=createVector();
 524     V->item.status=NOTREADY;
 525     Q->tail->next=(MemoryQueueItem*)V;
 526     //***NEED memory barrier here to ensure compiler does not cache Q.tail.status******
 527     if (BARRIER() && Q->tail->status==READY) {
 528       V->item.status=READY;
 529     }
 530     Q->tail=(MemoryQueueItem*)V;
 531   }
 532
 533   atomic_inc(&V->item.total);
 534   //expose entry
 535   int index=V->index;
 536   V->array[index]=r;
 537   r->index=index;
 538   //*****NEED memory barrier here to ensure compiler does not reorder writes to V.array and V.index
 539   BARRIER();
 540   V->index++;
 541   //*****NEED memory barrier here to ensure compiler does not cache V.status*********
 542   r->qitem=(MemoryQueueItem *)V;
 543   if (BARRIER() && V->item.status==READY) {
 544     void* flag=NULL;
 545     flag=(void*)LOCKXCHG((unsigned INTPTR*)&(V->array[index]), (unsigned INTPTR)flag);
 546     if (flag!=NULL) {
 547       if (isParentCoarse(r)) { //parent's retire immediately
 548         atomic_dec(&V->item.total);
 549         V->index--;
 550       }
 551       return READY;
 552     } else {
 553       return NOTREADY;//<- means that some other dispatcher got this one...so need to do accounting correctly
 554     }
 555   } else {
 556     return NOTREADY;
 557   }
 558 }
 559
 560
 561 //SCC's don't come in parent variety
 562 int ADDSCC(MemoryQueue *Q, REntry *r) {
 563   //added SCC
 564   SCC* S=createSCC();
 565   S->item.total=1;
 566   S->val=r;
 567   r->qitem=(MemoryQueueItem *)S;
 568   Q->tail->next=(MemoryQueueItem*)S;
 569   //*** NEED BARRIER HERE
 570   if (BARRIER() && Q->tail->status==READY && Q->tail->total==0 && Q->tail==Q->head) {
 571     //previous Q item is finished
 572     S->item.status=READY;
 573     Q->tail=(MemoryQueueItem*)S;
 574     // handle the the queue item case
 575     if(Q->head->type==3){
 576       Q->head=(MemoryQueueItem*)S;
 577     }
 578     void* flag=NULL;
 579     flag=(void*)LOCKXCHG((unsigned INTPTR*)&(S->val), (unsigned INTPTR)flag);
 580     if (flag!=NULL) {
 581       return READY;
 582     } else {
 583       return NOTREADY;//<- means that some other dispatcher got this one...so need to do accounting correctly
 584     }
 585   } else {
 586     Q->tail=(MemoryQueueItem*)S;
 587     return NOTREADY;
 588   }
 589 }
 590
 591
 592 void RETIRERENTRY(MemoryQueue* Q, REntry * r) {
 593   if (isFineWrite(r)||isFineRead(r)) {
 594     RETIREHASHTABLE(Q, r);
 595   } else if (isCoarse(r)) {
 596     RETIREVECTOR(Q, r);
 597   } else if (isSCC(r)) {
 598     RETIRESCC(Q, r);
 599   }
 600 #ifndef OOO_DISABLE_TASKMEMPOOL
 601 #ifdef RCR
 602   if (atomic_sub_and_test(1, &r->count))
 603 #endif
 604     poolfreeinto(Q->rentrypool, r);
 605 #endif
 606 }
 607
 608 void RETIRESCC(MemoryQueue *Q, REntry *r) {
 609   SCC* s=(SCC *)r->qitem;
 610   s->item.total=0;//don't need atomicdec
 611 #ifdef RCR
 612   void *flag=NULL;
 613   flag=(void*)LOCKXCHG((unsigned INTPTR*)&(s->val), (unsigned INTPTR)flag);
 614   if (flag!=NULL) {
 615 #ifdef OOO_DISABLE_TASKMEMPOOL
 616     RELEASE_REFERENCE_TO(((REntry*)flag)->seseRec);
 617 #endif
 618   }
 619 #endif
 620   RESOLVECHAIN(Q);
 621 }
 622
 623
 624 void RETIREHASHTABLE(MemoryQueue *q, REntry *r) {
 625   Hashtable *T=(Hashtable *)r->qitem;
 626   BinItem *b=r->binitem;
 627   RETIREBIN(T,r,b);
 628   atomic_dec(&T->item.total);
 629   if (T->item.next!=NULL && T->item.total==0) {
 630     RESOLVECHAIN(q);
 631   }
 632 }
 633
 634 void RETIREBIN(Hashtable *T, REntry *r, BinItem *b) {
 635   int key=generateKey( OBJPTRPTR_2_OBJOID( r->pointer ) );
 636   if(isFineRead(r)) {
 637     atomic_dec(&b->total);
 638   }
 639   if (isFineWrite(r) || (isFineRead(r) && b->next!=NULL && b->total==0)) {
 640       // CHECK FIRST IF next is nonnull to guarantee that b.total cannot change
 641     BinItem * val;
 642     do {
 643       val=(BinItem*)0x1;
 644       val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(T->array[key]->head), (unsigned INTPTR)val);
 645     } while(val==(BinItem*)0x1);
 646     // at this point have locked bin
 647     BinItem *ptr=val;
 648     int haveread=FALSE;
 649     int i;
 650     while (ptr!=NULL) {
 651        if (isReadBinItem(ptr)) {
 652         ReadBinItem* rptr=(ReadBinItem*)ptr;
 653         if (rptr->item.status==NOTREADY) {
 654           for (i=0;i<rptr->index;i++) {
 655             resolveDependencies(rptr->array[i]);
 656             if (isParent(rptr->array[i])) {
 657               //parents go immediately
 658               atomic_dec(&rptr->item.total);
 659               atomic_dec(&T->item.total);
 660             }
 661           }
 662         }
 663         rptr->item.status=READY;
 664         if (rptr->item.next==NULL) {
 665           break;
 666         }
 667         if (rptr->item.total!=0) {
 668           haveread=TRUE;
 669         } else if ((BinItem*)rptr==val) {
 670           val=val->next;
 671         }
 672       } else if(isWriteBinItem(ptr)) {
 673         if (haveread)
 674           break;
 675         if(ptr->status==NOTREADY){
 676           resolveDependencies(((WriteBinItem*)ptr)->val);
 677           ptr->status=READY;
 678           if(isParent(((WriteBinItem*)ptr)->val)){
 679             atomic_dec(&T->item.total);
 680             val=val->next;
 681           }else
 682             break;
 683         }else{ // write bin is already resolved
 684           val=val->next;
 685         }
 686         /*
 687         if(ptr->status==NOTREADY) {
 688           resolveDependencies(((WriteBinItem*)ptr)->val);
 689         }
 690           ptr->status=READY;
 691           if (isParent(((WriteBinItem*)ptr)->val)) {
 692             atomic_dec(&T->item.total);
 693             //val=val->next;
 694             val=ptr->next;
 695           } else
 696             break;
 697         }
 698         */
 699       }
 700       ptr=ptr->next;
 701     }
 702     T->array[key]->head=val; // release lock
 703   }
 704 }
 705
 706
 707 void RETIREVECTOR(MemoryQueue *Q, REntry *r) {
 708   Vector* V=(Vector *)r->qitem;
 709   atomic_dec(&V->item.total);
 710 #ifdef RCR
 711   REntry* val=NULL;
 712   val=(REntry*)LOCKXCHG((unsigned INTPTR*)&(V->array[r->index]), (unsigned INTPTR)val);
 713   if (val!=NULL) {
 714     RELEASE_REFERENCE_TO( ((REntry*)val)->seseRec);
 715   }
 716 #endif
 717   if (V->item.next!=NULL && V->item.total==0) { //NOTE: ORDERING CRUCIAL HERE
 718     RESOLVECHAIN(Q);
 719   }
 720 }
 721
 722 void RESOLVECHAIN(MemoryQueue *Q) {
 723   while(TRUE) {
 724     MemoryQueueItem* head=Q->head;
 725     if (head->next==NULL||head->total!=0) {
 726       //item is not finished
 727       if (head->status!=READY) {
 728         //need to update status
 729         head->status=READY;
 730         if (isHashtable(head)) {
 731           RESOLVEHASHTABLE(Q, (Hashtable *) head);
 732         } else if (isVector(head)) {
 733           RESOLVEVECTOR(Q, (Vector *) head);
 734         } else if (isSingleItem(head)) {
 735           RESOLVESCC((SCC *)head);
 736         }
 737         if (head->next==NULL)
 738           break;
 739         if (head->total!=0)
 740           break;
 741       } else
 742         break;
 743     }
 744     MemoryQueueItem* nextitem=head->next;
 745     CAS((unsigned INTPTR*)&(Q->head), (unsigned INTPTR)head, (unsigned INTPTR)nextitem);
 746     //oldvalue not needed...  if we fail we just repeat
 747   }
 748 }
 749
 750
 751 void RESOLVEHASHTABLE(MemoryQueue *Q, Hashtable *T) {
 752   int binidx;
 753   for (binidx=0;binidx<NUMBINS;binidx++) {
 754     BinElement* bin=T->array[binidx];
 755     BinItem* val;
 756     do {
 757       val=(BinItem*)1;
 758       val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(bin->head), (unsigned INTPTR)val);
 759     } while (val==(BinItem*)1);
 760     //at this point have locked bin
 761     int haveread=FALSE;
 762     BinItem* ptr=val;
 763     if(ptr!=NULL&&ptr->status==NOTREADY) {
 764       do {
 765         if (isWriteBinItem(ptr)) {
 766           if (haveread)
 767             break;
 768           resolveDependencies(((WriteBinItem*)ptr)->val);
 769           ptr->status=READY;
 770           if (isParent(((WriteBinItem*)ptr)->val)) {
 771             atomic_dec(&T->item.total);
 772             val=val->next;
 773           } else
 774             break;
 775         } else if (isReadBinItem(ptr)) {
 776           int i;
 777           ReadBinItem* rptr=(ReadBinItem*)ptr;
 778           for(i=0;i<rptr->index;i++) {
 779             resolveDependencies(rptr->array[i]);
 780             if (isParent(rptr->array[i])) {
 781               atomic_dec(&rptr->item.total);
 782               atomic_dec(&T->item.total);
 783             }
 784           }
 785           if (rptr->item.next==NULL||rptr->item.total!=0) {
 786             haveread=TRUE;
 787           } else if((BinItem*)rptr==val) {
 788             val=val->next;
 789           }
 790           rptr->item.status=READY;
 791         }
 792         ptr=ptr->next;
 793       }while(ptr!=NULL);
 794     }
 795     bin->head=val; // released lock;
 796   }
 797 }
 798
 799 void RESOLVEVECTOR(MemoryQueue *q, Vector *V) {
 800   int i;
 801   Vector* tmp=V;
 802   //handle ready cases
 803   while(TRUE) {
 804     //enqueue everything
 805     for (i=0;i<NUMITEMS;i++) {
 806       REntry* val=NULL;
 807       val=(REntry*)LOCKXCHG((unsigned INTPTR*)&(tmp->array[i]), (unsigned INTPTR)val);
 808       if (val!=NULL) {
 809         SESEcommon *seseCommon=val->seseRec;
 810         resolveDependencies(val);
 811         if (isParent(val)) {
 812           atomic_dec(&tmp->item.total);
 813 #ifdef RCR
 814           poolfreeinto(q->rentrypool,val);
 815 #endif
 816         }
 817 #if defined(RCR)&&defined(OOO_DISABLE_TASKMEMPOOL)
 818         else if (atomic_sub_and_test(1, &((REntry *)val)->count))
 819           poolfreeinto(q->rentrypool,val);
 820         RELEASE_REFERENCE_TO(seseCommon);
 821 #endif
 822       }
 823     }
 824     if (tmp->item.next!=NULL&&isVector(tmp->item.next)) {
 825       tmp=(Vector*)tmp->item.next;
 826     } else {
 827       break;
 828     }
 829   }
 830 }
 831
 832 void RESOLVESCC(SCC *S) {
 833   //precondition: SCC's state is READY
 834   void* flag=NULL;
 835   flag=(void*)LOCKXCHG((unsigned INTPTR*)&(S->val), (unsigned INTPTR)flag);
 836   if (flag!=NULL) {
 837     SESEcommon *seseCommon=((REntry *)flag)->seseRec;
 838     resolveDependencies(flag);
 839 #if defined(RCR)&&defined(OOO_DISABLE_TASKMEMPOOL)
 840     if (atomic_sub_and_test(1, &((REntry *)flag)->count))
 841       poolfreeinto(q->rentrypool, flag);
 842     RELEASE_REFERENCE_TO(seseCommon);
 843 #endif
 844   }
 845 }
 846
 847
 848 void resolveDependencies(REntry* rentry){
 849   SESEcommon* seseCommon=(SESEcommon*)rentry->seseRec;
 850   int type=rentry->type;
 851 #ifdef RCR
 852   if (type==COARSE||type==SCCITEM) {
 853     struct rcrRecord * array=(struct rcrRecord *)(((char *)seseCommon)+seseCommon->offsetToParamRecords);
 854     INTPTR mask=rentry->mask;
 855     int index=-1;
 856     while(mask!=0) {
 857       int shift=__builtin_ctzll(mask)+1;
 858       mask=mask>>shift;
 859       index+=shift;
 860       if(atomic_sub_and_test(1, &array[index].flag)) {
 861         if(atomic_sub_and_test(1, &(seseCommon->unresolvedDependencies)))
 862           workScheduleSubmit((void *)seseCommon);
 863       }
 864     }
 865   } else if (type==PARENTCOARSE) {
 866     if (atomic_sub_and_test(1, &(seseCommon->unresolvedDependencies))) {
 867       psem_give_tag(seseCommon->parentsStallSem, ((SESEstall *) seseCommon)->tag);
 868       //release our reference to stallrecord
 869     }
 870   } else {
 871     printf("ERROR: REntry type %d should never be generated in RCR..\n", rentry->type);
 872   }
 873 #else
 874   if(type==READ || type==WRITE || type==COARSE || type==SCCITEM){
 875     if( atomic_sub_and_test(1, &(seseCommon->unresolvedDependencies)) ){
 876       workScheduleSubmit(seseCommon);
 877     }
 878   }else if(type==PARENTREAD || type==PARENTWRITE || type==PARENTCOARSE){
 879     psem_give_tag(rentry->parentStallSem, rentry->tag);
 880   }
 881 #endif
 882 }
 883
 884 void INITIALIZEBUF(MemoryQueue * q){
 885   int i=0;
 886   for(i=0; i<NUMBINS; i++){
 887     q->binbuf[i]=NULL;
 888   }
 889   q->bufcount=0;
 890 }
 891
 892 void ADDRENTRYTOBUF(MemoryQueue * q, REntry * r){
 893   q->buf[q->bufcount]=r;
 894   q->bufcount++;
 895 }
 896
 897 int RESOLVEBUFFORHASHTABLE(MemoryQueue * q, Hashtable* table, SESEcommon *seseCommon){
 898   int i;
 899  // first phase: only consider write rentry
 900   for(i=0; i<q->bufcount;i++){
 901     REntry *r=q->buf[i];
 902     if(r->type==WRITE){
 903       int key=generateKey( OBJPTRPTR_2_OBJOID( r->pointer ) );
 904       if(q->binbuf[key]==NULL){
 905         // for multiple writes, add only the first write that hashes to the same bin
 906         q->binbuf[key]=r;
 907       }else{
 908         q->buf[i]=NULL;
 909       }
 910     }
 911   }
 912   // second phase: enqueue read items if it is eligible
 913   for(i=0; i<q->bufcount;i++){
 914     REntry *r=q->buf[i];
 915     if(r!=NULL && r->type==READ){
 916       int key=generateKey( OBJPTRPTR_2_OBJOID( r->pointer ) );
 917       if(q->binbuf[key]==NULL){
 918         // read item that hashes to the bin which doen't contain any write
 919         seseCommon->rentryArray[seseCommon->rentryIdx++]=r;
 920         if(ADDTABLEITEM(table, r, FALSE)==READY){
 921           resolveDependencies(r);
 922         }
 923       }
 924       q->buf[i]=NULL;
 925     }
 926   }
 927
 928   // then, add only one of write items that hashes to the same bin
 929   for(i=0; i<q->bufcount;i++){
 930     REntry *r=q->buf[i];
 931     if(r!=NULL){
 932       seseCommon->rentryArray[seseCommon->rentryIdx++]=r;
 933       if(ADDTABLEITEM(table, r, FALSE)==READY){
 934         resolveDependencies(r);
 935       }
 936     }
 937   }
 938 }
 939
 940 #ifndef RCR
 941 int RESOLVEBUF(MemoryQueue * q, SESEcommon *seseCommon){
 942   int localCount=0;
 943   int i;
 944   // check if every waiting entry is resolved
 945   // if not, defer every items for hashtable until it is resolved.
 946   int unresolved=FALSE;
 947   for(i=0; i<q->bufcount;i++){
 948      REntry *r=q->buf[i];
 949      if(*(r->pointer)==0){
 950        unresolved=TRUE;
 951      }
 952   }
 953   if(unresolved==TRUE){
 954     for(i=0; i<q->bufcount;i++){
 955       REntry *r=q->buf[i];
 956       r->queue=q;
 957       r->isBufMode=TRUE;
 958       if(ADDRENTRY(q,r)==NOTREADY){
 959         localCount++;
 960       }
 961     }
 962     return localCount;
 963   }
 964
 965   // first phase: only consider write rentry
 966   for(i=0; i<q->bufcount;i++){
 967     REntry *r=q->buf[i];
 968     if(r->type==WRITE){
 969       int key=generateKey( OBJPTRPTR_2_OBJOID( r->pointer ) );
 970       if(q->binbuf[key]==NULL){
 971         // for multiple writes, add only the first write that hashes to the same bin
 972         q->binbuf[key]=r;
 973       }else{
 974         q->buf[i]=NULL;
 975       }
 976     }
 977   }
 978   // second phase: enqueue read items if it is eligible
 979   for(i=0; i<q->bufcount;i++){
 980     REntry *r=q->buf[i];
 981     if(r!=NULL && r->type==READ){
 982       int key=generateKey( OBJPTRPTR_2_OBJOID( r->pointer ) );
 983       if(q->binbuf[key]==NULL){
 984         // read item that hashes to the bin which doen't contain any write
 985         seseCommon->rentryArray[seseCommon->rentryIdx++]=r;
 986         if(ADDRENTRY(q,r)==NOTREADY){
 987           localCount++;
 988         }
 989       }
 990       q->buf[i]=NULL;
 991     }
 992   }
 993
 994   // then, add only one of write items that hashes to the same bin
 995   for(i=0; i<q->bufcount;i++){
 996     REntry *r=q->buf[i];
 997     if(r!=NULL){
 998       seseCommon->rentryArray[seseCommon->rentryIdx++]=r;
 999       if(ADDRENTRY(q,r)==NOTREADY){
1000         localCount++;
1001       }
1002     }
1003   }
1004   return localCount;
1005 }
1006
1007
1008 void resolvePointer(REntry* rentry){
1009   Hashtable* table=(Hashtable *)rentry->qitem;
1010   MemoryQueue* queue;
1011   // we don't need to consider unresolved cases for coarse rentries.
1012   // or if resolved already before related rentry is enqueued to the waiting queue
1013   if(rentry->type==COARSE ||
1014      rentry->type==PARENTCOARSE ||
1015      rentry->type==SCCITEM ||
1016      table==NULL ||
1017      table->unresolvedQueue==NULL){
1018     return;
1019   }
1020   struct Queue* val;
1021   do {
1022     val=(struct Queue*)0x1;
1023     val=(struct Queue*)LOCKXCHG((unsigned INTPTR*)&(table->unresolvedQueue), (unsigned INTPTR)val);
1024   } while(val==(struct Queue*)0x1);
1025   if(val!=NULL &&
1026      getHead(val)!=NULL &&
1027      getHead(val)->objectptr==rentry){
1028     // handling pointer is the first item of the queue
1029     // start to resolve until it reaches unresolved pointer or end of queue
1030     INTPTR currentSESE=0;
1031     do{
1032       struct QueueItem* head=getHead(val);
1033       if(head!=NULL){
1034         REntry* rentry=(REntry*)head->objectptr;
1035         if(*(rentry->pointer)==0){
1036           // encounters following unresolved pointer
1037           table->unresolvedQueue=val;//released lock
1038           break;
1039         }
1040         removeItem(val,head);
1041
1042         //now, address is resolved
1043
1044         //check if rentry is buffer mode
1045         if(rentry->isBufMode==TRUE){
1046           if(currentSESE==0){
1047             queue=rentry->queue;
1048             INITIALIZEBUF(queue);
1049             currentSESE=(INTPTR)rentry;
1050             ADDRENTRYTOBUF(queue,rentry);
1051           } else if(currentSESE==(INTPTR)rentry){
1052             ADDRENTRYTOBUF(queue,rentry);
1053           } else if(currentSESE!=(INTPTR)rentry){
1054             RESOLVEBUFFORHASHTABLE(queue,table,(SESEcommon*)rentry->seseRec);
1055             currentSESE=(INTPTR)rentry;
1056             INITIALIZEBUF(queue);
1057             ADDRENTRYTOBUF(rentry->queue,rentry);
1058           }
1059         }else{
1060           if(currentSESE!=0){
1061             //previous SESE has buf mode, need to invoke resolve buffer
1062             RESOLVEBUFFORHASHTABLE(queue,table,(SESEcommon*)rentry->seseRec);
1063             currentSESE=0;
1064           }
1065           //normal mode
1066           if(ADDTABLEITEM(table, rentry, FALSE)==READY){
1067             resolveDependencies(rentry);
1068           }
1069         }
1070       }else{
1071         table->unresolvedQueue=NULL; // set hashtable as normal-mode.
1072         break;
1073       }
1074     }while(TRUE);
1075   }else{
1076     // resolved rentry is not head of queue
1077     table->unresolvedQueue=val;//released lock;
1078   }
1079 }
1080 #endif