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     //optimization only on next line....DO NOT TRUST THIS TO RETIRE PARENTS!!!!
 246     if (isParent(r) && tail->total==0 && q->tail==q->head) {
 247       return READY;
 248     }
 249
 250     //Add table
 251     Hashtable* h=createHashtable();
 252     tail->next=(MemoryQueueItem*)h;
 253     //************NEED memory barrier here to ensure compiler does not cache Q.tail.status********
 254     MBARRIER();
 255     if (tail->status==READY && tail->total==0 && q->tail==q->head) {
 256       //previous Q item is finished
 257       h->item.status=READY;
 258     }
 259     q->tail=(MemoryQueueItem*)h;
 260     // handle the the queue item case
 261     if(q->head->type==3) {
 262       q->head=(MemoryQueueItem*)h;
 263     }
 264   }
 265
 266   //at this point, have table
 267   Hashtable* table=(Hashtable*)q->tail;
 268   r->qitem=(MemoryQueueItem *) table; // set rentry's hashtable
 269   if( *(r->pointer)==0 ||
 270       ( *(r->pointer)!=0 &&
 271         BARRIER() &&
 272         table->unresolvedQueue!=NULL
 273       )
 274       ) {
 275     struct Queue* val;
 276     // grab lock on the queue
 277     do {
 278       val=(struct Queue*)0x1;
 279       val=(struct Queue*)LOCKXCHG((unsigned INTPTR*)&(table->unresolvedQueue), (unsigned INTPTR)val);
 280     } while(val==(struct Queue*)0x1);
 281     if(val==NULL) {
 282       //queue is null, first case
 283       if(*(r->pointer)!=0) {
 284         // check whether pointer is already resolved, or not.
 285         table->unresolvedQueue=NULL; //released lock;
 286         return ADDTABLEITEM(table,r,TRUE);
 287       }
 288       struct Queue* queue=createQueue();
 289       addNewItemBack(queue,r);
 290       atomic_inc(&table->item.total);
 291       table->unresolvedQueue=queue; // expose new queue
 292     } else {
 293       // add unresolved rentry at the end of the queue.
 294       addNewItemBack(val,r);
 295       atomic_inc(&table->item.total);
 296       table->unresolvedQueue=val; // released lock
 297     }
 298     return NOTREADY;
 299   }
 300   BinItem * val;
 301
 302   // leave this--its a helpful test when things are going bonkers
 303   //if( OBJPTRPTR_2_OBJOID( r->pointer ) == 0 ) {
 304   //  // we started numbering object ID's at 1, if we try to
 305   //  // hash a zero oid, something BAD is about to happen!
 306   //  printf( "Tried to insert invalid object type=%d into mem Q hashtable!\n",
 307   //          OBJPTRPTR_2_OBJTYPE( r->pointer ) );
 308   //  exit( -1 );
 309   //}
 310   int key=generateKey(OBJPTRPTR_2_OBJOID(r->pointer) );
 311   do {
 312     val=(BinItem*)0x1;
 313     BinElement* bin=table->array[key];
 314     val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(bin->head), (unsigned INTPTR)val); //note...talk to me about optimizations here.
 315   } while(val==(BinItem*)0x1);
 316   //at this point have locked bin
 317   if (val==NULL) {
 318     return EMPTYBINCASE(table, table->array[key], r, TRUE);
 319   } else {
 320     if (isFineWrite(r)) {
 321       return WRITEBINCASE(table, r, val, key, TRUE);
 322     } else if (isFineRead(r)) {
 323       return READBINCASE(table, r, val, key, TRUE);
 324     }
 325   }
 326 }
 327
 328 int ADDTABLEITEM(Hashtable* table, REntry* r, int inc) {
 329
 330   BinItem * val;
 331   int key=generateKey(OBJPTRPTR_2_OBJOID(r->pointer) );
 332   do {
 333     val=(BinItem*)0x1;
 334     BinElement* bin=table->array[key];
 335     val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(bin->head), (unsigned INTPTR)val);
 336   } while(val==(BinItem*)0x1);
 337   //at this point have locked bin
 338   if (val==NULL) {
 339     return EMPTYBINCASE(table, table->array[key], r, inc);
 340   } else {
 341     if (isFineWrite(r)) {
 342       return WRITEBINCASE(table, r, val, key, inc);
 343     } else if (isFineRead(r)) {
 344       return READBINCASE(table, r, val, key, inc);
 345     }
 346   }
 347 }
 348
 349 int EMPTYBINCASE(Hashtable *T, BinElement* be, REntry *r, int inc) {
 350   int retval;
 351   BinItem* b;
 352   if (isFineWrite(r)) {
 353     b=(BinItem*)createWriteBinItem();
 354     ((WriteBinItem*)b)->val=r; //<-only different statement
 355   } else if (isFineRead(r)) {
 356     b=(BinItem*)createReadBinItem();
 357     ReadBinItem* readbin=(ReadBinItem*)b;
 358     readbin->array[readbin->index++]=r;
 359   }
 360   b->total=1;
 361
 362   if (T->item.status==READY) {
 363     //current entry is ready
 364     b->status=READY;
 365     retval=READY;
 366     if (isParent(r)) {
 367       be->head=NULL; // released lock
 368       return retval;
 369     }
 370   } else {
 371     b->status=NOTREADY;
 372     retval=NOTREADY;
 373   }
 374
 375   if(inc) {
 376     atomic_inc(&T->item.total);
 377   }
 378   r->qitem=(MemoryQueueItem *)T;
 379   r->binitem=b;
 380   be->tail=b;
 381   be->head=b; //released lock
 382   return retval;
 383 }
 384
 385 int WRITEBINCASE(Hashtable *T, REntry *r, BinItem *val, int key, int inc) {
 386   //chain of bins exists => tail is valid
 387   //if there is something in front of us, then we are not ready
 388
 389   int retval=NOTREADY;
 390   BinElement* be=T->array[key];
 391
 392   BinItem *bintail=be->tail;
 393
 394   WriteBinItem *b=createWriteBinItem();
 395   b->val=r;
 396   b->item.total=1;
 397
 398   // note: If current table clears all dependencies, then write bin is ready
 399
 400
 401   if(inc) {
 402     atomic_inc(&T->item.total);
 403   }
 404
 405   r->qitem=(MemoryQueueItem *)T;
 406   r->binitem=(BinItem*)b;
 407
 408   be->tail->next=(BinItem*)b;
 409   //need to check if we can go...
 410   MBARRIER();
 411   if (T->item.status==READY) {
 412     for(; val!=NULL; val=val->next) {
 413       if (val==((BinItem *)b)) {
 414         //ready to retire
 415         retval=READY;
 416         if (isParent(r)) {
 417           b->item.status=retval; //unsure if really needed at this point..
 418           be->head=NULL; // released lock
 419           return retval;
 420         }
 421         break;
 422       } else if (val->total!=0) {
 423         break;
 424       }
 425     }
 426   }
 427
 428   b->item.status=retval;
 429   be->tail=(BinItem*)b;
 430   be->head=val;
 431   return retval;
 432 }
 433
 434 int READBINCASE(Hashtable *T, REntry *r, BinItem *val, int key, int inc) {
 435   BinItem * bintail=T->array[key]->tail;
 436   if (isReadBinItem(bintail)) {
 437     return TAILREADCASE(T, r, val, bintail, key, inc);
 438   } else if (!isReadBinItem(bintail)) {
 439     TAILWRITECASE(T, r, val, bintail, key, inc);
 440     return NOTREADY;
 441   }
 442 }
 443
 444 int TAILREADCASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key, int inc) {
 445   ReadBinItem * readbintail=(ReadBinItem*)T->array[key]->tail;
 446   int status, retval;
 447   if (readbintail->item.status==READY) {
 448     status=READY;
 449     retval=READY;
 450     if (isParent(r)) {
 451       T->array[key]->head=val; //released lock
 452       return READY;
 453     }
 454   } else {
 455     status=NOTREADY;
 456     retval=NOTREADY;
 457   }
 458
 459   if (readbintail->index==NUMREAD) { // create new read group
 460     ReadBinItem* rb=createReadBinItem();
 461     rb->array[rb->index++]=r;
 462     rb->item.total=1; //safe only because item could not have started
 463     rb->item.status=status;
 464     T->array[key]->tail->next=(BinItem*)rb;
 465     T->array[key]->tail=(BinItem*)rb;
 466     r->binitem=(BinItem*)rb;
 467   } else { // group into old tail
 468     readbintail->array[readbintail->index++]=r;
 469     atomic_inc(&readbintail->item.total);
 470     r->binitem=(BinItem*)readbintail;
 471   }
 472   if(inc) {
 473     atomic_inc(&T->item.total);
 474   }
 475   r->qitem=(MemoryQueueItem *)T;
 476   T->array[key]->head=val; //released lock
 477   return retval;
 478 }
 479
 480 void TAILWRITECASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key, int inc) {
 481   //  WriteBinItem* wb=createWriteBinItem();
 482   //wb->val=r;
 483   //wb->item.total=1;//safe because item could not have started
 484   //wb->item.status=NOTREADY;
 485   ReadBinItem* rb=createReadBinItem();
 486   rb->array[rb->index++]=r;
 487   rb->item.total=1; //safe because item could not have started
 488   rb->item.status=NOTREADY;
 489   if(inc) {
 490     atomic_inc(&T->item.total);
 491   }
 492   r->qitem=(MemoryQueueItem *)T;
 493   r->binitem=(BinItem*)rb;
 494   T->array[key]->tail->next=(BinItem*)rb;
 495   T->array[key]->tail=(BinItem*)rb;
 496   T->array[key]->head=val; //released lock
 497 }
 498
 499 int ADDVECTOR(MemoryQueue *Q, REntry *r) {
 500   if(!isVector(Q->tail)) {
 501     //Fast Case
 502     if (isParentCoarse(r) && Q->tail->total==0 && Q->tail==Q->head) {
 503       return READY;
 504     }
 505
 506     //added vector
 507     Vector* V=createVector();
 508     V->item.status=NOTREADY;
 509     BARRIER();
 510     Q->tail->next=(MemoryQueueItem*)V;
 511     //************NEED memory barrier here to ensure compiler does not cache Q.tail.status******
 512     MBARRIER();
 513     if (Q->tail->status==READY&&Q->tail->total==0&&Q->head==Q->tail) {
 514       //previous Q item is finished
 515       V->item.status=READY;
 516       //Get rid of item in front of us...
 517       CAS((unsigned INTPTR*)&(Q->head), (unsigned INTPTR)Q->tail, (unsigned INTPTR)V);
 518     }
 519     Q->tail=(MemoryQueueItem*)V;
 520     // handle the the queue item case
 521     if(Q->head->type==3) {
 522       Q->head=(MemoryQueueItem*)V;
 523     }
 524   }
 525   //at this point, have vector
 526   Vector* V=(Vector*)Q->tail;
 527   if (V->index==NUMITEMS) {
 528     //vector is full
 529     //added vector
 530     V=createVector();
 531     V->item.status=NOTREADY;
 532     Q->tail->next=(MemoryQueueItem*)V;
 533     //***NEED memory barrier here to ensure compiler does not cache Q.tail.status******
 534     MBARRIER();
 535     if (Q->tail->status==READY) {
 536       V->item.status=READY;
 537     }
 538     if (Q->tail->total==0&&Q->head==Q->tail) {
 539       //may need to remove things
 540       CAS((unsigned INTPTR*)&(Q->head), (unsigned INTPTR)Q->tail, (unsigned INTPTR)V);
 541     }
 542     Q->tail=(MemoryQueueItem*)V;
 543   }
 544
 545   atomic_inc(&V->item.total);
 546   //expose entry
 547   int index=V->index;
 548   V->array[index]=r;
 549 #ifdef RCR
 550   r->index=index;
 551 #endif
 552   //*****NEED memory barrier here to ensure compiler does not reorder writes to V.array and V.index
 553   BARRIER();
 554   V->index++;
 555   //*****NEED memory barrier here to ensure compiler does not cache V.status*********
 556   r->qitem=(MemoryQueueItem *)V;
 557   MBARRIER();
 558   if (V->item.status==READY) {
 559     void* flag=NULL;
 560     flag=(void*)LOCKXCHG((unsigned INTPTR*)&(V->array[index]), (unsigned INTPTR)flag);
 561     if (flag!=NULL) {
 562       if (isParentCoarse(r)) { //parent's retire immediately
 563         atomic_dec(&V->item.total);
 564         V->index--;
 565       } else {
 566 #if defined(RCR)&&!defined(OOO_DISABLE_TASKMEMPOOL)
 567         if (atomic_sub_and_test(1, &r->count))
 568           poolfreeinto(Q->rentrypool, r);
 569 #endif
 570       }
 571       return READY;
 572     } else {
 573       return NOTREADY; //<- means that some other dispatcher got this one...so need to do accounting correctly
 574     }
 575   } else {
 576     return NOTREADY;
 577   }
 578 }
 579
 580
 581 //SCC's don't come in parent variety
 582 int ADDSCC(MemoryQueue *Q, REntry *r) {
 583   //added SCC
 584   SCC* S=createSCC();
 585   S->item.total=1;
 586   S->val=r;
 587   S->item.status=NOTREADY;
 588   r->qitem=(MemoryQueueItem *)S;
 589   //*** NEED BARRIER HERE -- data structure needs to be complete before exposing
 590   BARRIER();
 591   Q->tail->next=(MemoryQueueItem*)S;
 592   //*** NEED BARRIER HERE
 593   MBARRIER();
 594   if (Q->tail->status==READY && Q->tail->total==0 && Q->tail==Q->head) {
 595     //previous Q item is finished
 596     S->item.status=READY;
 597     Q->tail=(MemoryQueueItem*)S;
 598     // handle the the queue item case
 599     if(Q->head->type==3) {
 600       Q->head=(MemoryQueueItem*)S;
 601     }
 602     void* flag=NULL;
 603     flag=(void*)LOCKXCHG((unsigned INTPTR*)&(S->val), (unsigned INTPTR)flag);
 604     if (flag!=NULL) {
 605 #if defined(RCR)&&!defined(OOO_DISABLE_TASKMEMPOOL)
 606       if (atomic_sub_and_test(1, &r->count))
 607         poolfreeinto(Q->rentrypool, r);
 608 #endif
 609       return READY;
 610     } else {
 611       return NOTREADY; //<- means that some other dispatcher got this one...so need to do accounting correctly
 612     }
 613   } else {
 614     Q->tail=(MemoryQueueItem*)S;
 615     return NOTREADY;
 616   }
 617 }
 618
 619
 620 void RETIRERENTRY(MemoryQueue* Q, REntry * r) {
 621   if (isFineWrite(r)||isFineRead(r)) {
 622     RETIREHASHTABLE(Q, r);
 623   } else if (isCoarse(r)) {
 624     RETIREVECTOR(Q, r);
 625   } else if (isSCC(r)) {
 626     RETIRESCC(Q, r);
 627   }
 628 #ifndef OOO_DISABLE_TASKMEMPOOL
 629 #ifdef RCR
 630   if (atomic_sub_and_test(1, &r->count))
 631 #endif
 632   poolfreeinto(Q->rentrypool, r);
 633 #endif
 634 }
 635
 636 void RETIRESCC(MemoryQueue *Q, REntry *r) {
 637   SCC* s=(SCC *)r->qitem;
 638   s->item.total=0; //don't need atomicdec
 639 #ifdef RCR
 640   void *flag=NULL;
 641   flag=(void*)LOCKXCHG((unsigned INTPTR*)&(s->val), (unsigned INTPTR)flag);
 642   if (flag!=NULL) {
 643 #ifndef OOO_DISABLE_TASKMEMPOOL
 644     RELEASE_REFERENCE_TO(((REntry*)flag)->seseRec);
 645 #endif
 646     //only release reference if we haven't cleared it before
 647 #if !defined(OOO_DISABLE_TASKMEMPOOL)&&defined(RCR)
 648     if (atomic_sub_and_test(1, &r->count))
 649       poolfreeinto(Q->rentrypool, r);
 650 #endif
 651   }
 652 #endif
 653   RESOLVECHAIN(Q);
 654 }
 655
 656
 657 void RETIREHASHTABLE(MemoryQueue *q, REntry *r) {
 658   Hashtable *T=(Hashtable *)r->qitem;
 659   BinItem *b=r->binitem;
 660   RETIREBIN(T,r,b);
 661   atomic_dec(&T->item.total);
 662   BARRIER();
 663   if (T->item.next!=NULL && T->item.total==0) {
 664     RESOLVECHAIN(q);
 665   }
 666 }
 667
 668 void RETIREBIN(Hashtable *T, REntry *r, BinItem *b) {
 669   int key=generateKey(OBJPTRPTR_2_OBJOID(r->pointer) );
 670   if(isFineRead(r)) {
 671     atomic_dec(&b->total);
 672   }
 673   if (isFineWrite(r) || (isFineRead(r) && b->next!=NULL && b->total==0)) {
 674     // CHECK FIRST IF next is nonnull to guarantee that b.total cannot change
 675     BinItem * val;
 676     do {
 677       val=(BinItem*)0x1;
 678       val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(T->array[key]->head), (unsigned INTPTR)val);
 679     } while(val==(BinItem*)0x1);
 680     // at this point have locked bin
 681     BinItem *ptr=val;
 682     int haveread=FALSE;
 683     int i;
 684     while (ptr!=NULL) {
 685       if (isReadBinItem(ptr)) {
 686         ReadBinItem* rptr=(ReadBinItem*)ptr;
 687         if (rptr->item.status==NOTREADY) {
 688           for (i=0; i<rptr->index; i++) {
 689             resolveDependencies(rptr->array[i]);
 690             if (isParent(rptr->array[i])) {
 691               //parents go immediately
 692               atomic_dec(&rptr->item.total);
 693               atomic_dec(&T->item.total);
 694             }
 695           }
 696         }
 697         rptr->item.status=READY;
 698         if (rptr->item.next==NULL) {
 699           break;
 700         }
 701         if (rptr->item.total!=0) {
 702           haveread=TRUE;
 703         } else if ((BinItem*)rptr==val) {
 704           val=val->next;
 705         }
 706       } else if(isWriteBinItem(ptr)) {
 707         if (haveread)
 708           break;
 709         if(ptr->status==NOTREADY) {
 710           resolveDependencies(((WriteBinItem*)ptr)->val);
 711           ptr->status=READY;
 712           if(isParent(((WriteBinItem*)ptr)->val)) {
 713             atomic_dec(&T->item.total);
 714             val=val->next;
 715           } else
 716             break;
 717         } else { // write bin is already resolved
 718           val=val->next;
 719         }
 720         /*
 721            if(ptr->status==NOTREADY) {
 722            resolveDependencies(((WriteBinItem*)ptr)->val);
 723            }
 724            ptr->status=READY;
 725            if (isParent(((WriteBinItem*)ptr)->val)) {
 726             atomic_dec(&T->item.total);
 727             //val=val->next;
 728             val=ptr->next;
 729            } else
 730             break;
 731            }
 732          */
 733       }
 734       ptr=ptr->next;
 735     }
 736     T->array[key]->head=val; // release lock
 737   }
 738 }
 739
 740
 741 void RETIREVECTOR(MemoryQueue *Q, REntry *r) {
 742   Vector* V=(Vector *)r->qitem;
 743   atomic_dec(&V->item.total);
 744 #ifdef RCR
 745   REntry* val=NULL;
 746   val=(REntry*)LOCKXCHG((unsigned INTPTR*)&(V->array[r->index]), (unsigned INTPTR)val);
 747   if (val!=NULL) {
 748     //release reference if we haven't cleared this one
 749 #if !defined(OOO_DISABLE_TASKMEMPOOL)&&defined(RCR)
 750     if (atomic_sub_and_test(1, &r->count))
 751       poolfreeinto(Q->rentrypool, r);
 752 #endif
 753     RELEASE_REFERENCE_TO( ((REntry*)val)->seseRec);
 754   }
 755 #endif
 756   if (V->item.next!=NULL && V->item.total==0) { //NOTE: ORDERING CRUCIAL HERE
 757     RESOLVECHAIN(Q);
 758   }
 759 }
 760
 761 void RESOLVECHAIN(MemoryQueue *Q) {
 762   while(TRUE) {
 763     MemoryQueueItem* head=Q->head;
 764     if (head->next==NULL||head->total!=0) {
 765       //item is not finished
 766       if (head->status!=READY) {
 767         //need to update status
 768         head->status=READY;
 769         if (isHashtable(head)) {
 770           RESOLVEHASHTABLE(Q, (Hashtable *) head);
 771         } else if (isVector(head)) {
 772           RESOLVEVECTOR(Q, (Vector *) head);
 773         } else if (isSingleItem(head)) {
 774           RESOLVESCC(Q, (SCC *)head);
 775         }
 776         if (head->next==NULL)
 777           break;
 778         if (head->total!=0)
 779           break;
 780       } else
 781         break;
 782     }
 783     MemoryQueueItem* nextitem=head->next;
 784     CAS((unsigned INTPTR*)&(Q->head), (unsigned INTPTR)head, (unsigned INTPTR)nextitem);
 785     //oldvalue not needed...  if we fail we just repeat
 786   }
 787 }
 788
 789
 790 void RESOLVEHASHTABLE(MemoryQueue *Q, Hashtable *T) {
 791   int binidx;
 792   for (binidx=0; binidx<NUMBINS; binidx++) {
 793     BinElement* bin=T->array[binidx];
 794     BinItem* val;
 795     do {
 796       val=(BinItem*)1;
 797       val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(bin->head), (unsigned INTPTR)val);
 798     } while (val==(BinItem*)1);
 799     //at this point have locked bin
 800     int haveread=FALSE;
 801     BinItem* ptr=val;
 802     if(ptr!=NULL&&ptr->status==NOTREADY) {
 803       do {
 804         if (isWriteBinItem(ptr)) {
 805           if (haveread)
 806             break;
 807           resolveDependencies(((WriteBinItem*)ptr)->val);
 808           ptr->status=READY;
 809           if (isParent(((WriteBinItem*)ptr)->val)) {
 810             atomic_dec(&T->item.total);
 811             val=val->next;
 812           } else
 813             break;
 814         } else if (isReadBinItem(ptr)) {
 815           int i;
 816           ReadBinItem* rptr=(ReadBinItem*)ptr;
 817           for(i=0; i<rptr->index; i++) {
 818             resolveDependencies(rptr->array[i]);
 819             if (isParent(rptr->array[i])) {
 820               atomic_dec(&rptr->item.total);
 821               atomic_dec(&T->item.total);
 822             }
 823           }
 824           if (rptr->item.next==NULL||rptr->item.total!=0) {
 825             haveread=TRUE;
 826           } else if((BinItem*)rptr==val) {
 827             val=val->next;
 828           }
 829           rptr->item.status=READY;
 830         }
 831         ptr=ptr->next;
 832       } while(ptr!=NULL);
 833     }
 834     bin->head=val; // released lock;
 835   }
 836 }
 837
 838 void RESOLVEVECTOR(MemoryQueue *q, Vector *V) {
 839   int i;
 840   Vector* tmp=V;
 841   //handle ready cases
 842   while(TRUE) {
 843     //enqueue everything
 844     for (i=0; i<NUMITEMS; i++) {
 845       REntry* val=NULL;
 846       val=(REntry*)LOCKXCHG((unsigned INTPTR*)&(tmp->array[i]), (unsigned INTPTR)val);
 847       if (val!=NULL) {
 848         SESEcommon *seseCommon=val->seseRec;
 849         resolveDependencies(val);
 850         if (isParent(val)) {
 851           atomic_dec(&tmp->item.total);
 852 #ifdef RCR
 853           poolfreeinto(q->rentrypool,val);
 854 #endif
 855         }
 856 #if defined(RCR)&&!defined(OOO_DISABLE_TASKMEMPOOL)
 857         else if (atomic_sub_and_test(1, &((REntry *)val)->count))
 858           poolfreeinto(q->rentrypool,val);
 859         RELEASE_REFERENCE_TO(seseCommon);
 860 #endif
 861       }
 862     }
 863     if (tmp->item.next!=NULL&&isVector(tmp->item.next)) {
 864       tmp=(Vector*)tmp->item.next;
 865     } else {
 866       break;
 867     }
 868   }
 869 }
 870
 871 void RESOLVESCC(MemoryQueue *q, SCC *S) {
 872   //precondition: SCC's state is READY
 873   void* flag=NULL;
 874   flag=(void*)LOCKXCHG((unsigned INTPTR*)&(S->val), (unsigned INTPTR)flag);
 875   if (flag!=NULL) {
 876     SESEcommon *seseCommon=((REntry *)flag)->seseRec;
 877     resolveDependencies(flag);
 878 #if defined(RCR)&&!defined(OOO_DISABLE_TASKMEMPOOL)
 879     if (atomic_sub_and_test(1, &((REntry *)flag)->count))
 880       poolfreeinto(q->rentrypool, flag);
 881     RELEASE_REFERENCE_TO(seseCommon);
 882 #endif
 883   }
 884 }
 885
 886
 887 void resolveDependencies(REntry* rentry) {
 888   SESEcommon* seseCommon=(SESEcommon*)rentry->seseRec;
 889   int type=rentry->type;
 890 #ifdef RCR
 891   if (type==COARSE||type==SCCITEM) {
 892     struct rcrRecord * array=(struct rcrRecord *)(((char *)seseCommon)+seseCommon->offsetToParamRecords);
 893     INTPTR mask=rentry->mask;
 894     int index=-1;
 895     while(mask!=0) {
 896       int shift=__builtin_ctzll(mask)+1;
 897       mask=mask>>shift;
 898       index+=shift;
 899       if(atomic_sub_and_test(1, &array[index].flag)) {
 900         if(atomic_sub_and_test(1, &(seseCommon->unresolvedDependencies)))
 901           workScheduleSubmit((void *)seseCommon);
 902       }
 903     }
 904   } else if (type==PARENTCOARSE) {
 905     if (atomic_sub_and_test(1, &(seseCommon->unresolvedDependencies))) {
 906       psem_give_tag(seseCommon->parentsStallSem, ((SESEstall *) seseCommon)->tag);
 907       //release our reference to stallrecord
 908     }
 909   } else {
 910     printf("ERROR: REntry type %d should never be generated in RCR..\n", rentry->type);
 911   }
 912 #else
 913   if(type==READ || type==WRITE || type==COARSE || type==SCCITEM) {
 914     if( atomic_sub_and_test(1, &(seseCommon->unresolvedDependencies)) ) {
 915       workScheduleSubmit(seseCommon);
 916     }
 917   } else if(type==PARENTREAD || type==PARENTWRITE || type==PARENTCOARSE) {
 918     psem_give_tag(rentry->parentStallSem, rentry->tag);
 919   }
 920 #endif
 921 }
 922
 923 void INITIALIZEBUF(MemoryQueue * q) {
 924   int i=0;
 925   for(i=0; i<NUMBINS; i++) {
 926     q->binbuf[i]=NULL;
 927   }
 928   q->bufcount=0;
 929 }
 930
 931 void ADDRENTRYTOBUF(MemoryQueue * q, REntry * r) {
 932   q->buf[q->bufcount]=r;
 933   q->bufcount++;
 934 }
 935
 936 int RESOLVEBUFFORHASHTABLE(MemoryQueue * q, Hashtable* table, SESEcommon *seseCommon) {
 937   int i;
 938   // first phase: only consider write rentry
 939   for(i=0; i<q->bufcount; i++) {
 940     REntry *r=q->buf[i];
 941     if(r->type==WRITE) {
 942       int key=generateKey(OBJPTRPTR_2_OBJOID(r->pointer) );
 943       if(q->binbuf[key]==NULL) {
 944         // for multiple writes, add only the first write that hashes to the same bin
 945         q->binbuf[key]=r;
 946       } else {
 947         q->buf[i]=NULL;
 948       }
 949     }
 950   }
 951   // second phase: enqueue read items if it is eligible
 952   for(i=0; i<q->bufcount; i++) {
 953     REntry *r=q->buf[i];
 954     if(r!=NULL && r->type==READ) {
 955       int key=generateKey(OBJPTRPTR_2_OBJOID(r->pointer) );
 956       if(q->binbuf[key]==NULL) {
 957         // read item that hashes to the bin which doen't contain any write
 958         seseCommon->rentryArray[seseCommon->rentryIdx++]=r;
 959         if(ADDTABLEITEM(table, r, FALSE)==READY) {
 960           resolveDependencies(r);
 961         }
 962       }
 963       q->buf[i]=NULL;
 964     }
 965   }
 966
 967   // then, add only one of write items that hashes to the same bin
 968   for(i=0; i<q->bufcount; i++) {
 969     REntry *r=q->buf[i];
 970     if(r!=NULL) {
 971       seseCommon->rentryArray[seseCommon->rentryIdx++]=r;
 972       if(ADDTABLEITEM(table, r, FALSE)==READY) {
 973         resolveDependencies(r);
 974       }
 975     }
 976   }
 977 }
 978
 979 #ifndef RCR
 980 int RESOLVEBUF(MemoryQueue * q, SESEcommon *seseCommon) {
 981   int localCount=0;
 982   int i;
 983   // check if every waiting entry is resolved
 984   // if not, defer every items for hashtable until it is resolved.
 985   int unresolved=FALSE;
 986   for(i=0; i<q->bufcount; i++) {
 987     REntry *r=q->buf[i];
 988     if(*(r->pointer)==0) {
 989       unresolved=TRUE;
 990     }
 991   }
 992   if(unresolved==TRUE) {
 993     for(i=0; i<q->bufcount; i++) {
 994       REntry *r=q->buf[i];
 995       r->queue=q;
 996       r->isBufMode=TRUE;
 997       if(ADDRENTRY(q,r)==NOTREADY) {
 998         localCount++;
 999       }
1000     }
1001     return localCount;
1002   }
1003
1004   // first phase: only consider write rentry
1005   for(i=0; i<q->bufcount; i++) {
1006     REntry *r=q->buf[i];
1007     if(r->type==WRITE) {
1008       int key=generateKey(OBJPTRPTR_2_OBJOID(r->pointer) );
1009       if(q->binbuf[key]==NULL) {
1010         // for multiple writes, add only the first write that hashes to the same bin
1011         q->binbuf[key]=r;
1012       } else {
1013         q->buf[i]=NULL;
1014       }
1015     }
1016   }
1017   // second phase: enqueue read items if it is eligible
1018   for(i=0; i<q->bufcount; i++) {
1019     REntry *r=q->buf[i];
1020     if(r!=NULL && r->type==READ) {
1021       int key=generateKey(OBJPTRPTR_2_OBJOID(r->pointer) );
1022       if(q->binbuf[key]==NULL) {
1023         // read item that hashes to the bin which doen't contain any write
1024         seseCommon->rentryArray[seseCommon->rentryIdx++]=r;
1025         if(ADDRENTRY(q,r)==NOTREADY) {
1026           localCount++;
1027         }
1028       }
1029       q->buf[i]=NULL;
1030     }
1031   }
1032
1033   // then, add only one of write items that hashes to the same bin
1034   for(i=0; i<q->bufcount; i++) {
1035     REntry *r=q->buf[i];
1036     if(r!=NULL) {
1037       seseCommon->rentryArray[seseCommon->rentryIdx++]=r;
1038       if(ADDRENTRY(q,r)==NOTREADY) {
1039         localCount++;
1040       }
1041     }
1042   }
1043   return localCount;
1044 }
1045
1046
1047 void resolvePointer(REntry* rentry) {
1048   Hashtable* table=(Hashtable *)rentry->qitem;
1049   MemoryQueue* queue;
1050   // we don't need to consider unresolved cases for coarse rentries.
1051   // or if resolved already before related rentry is enqueued to the waiting queue
1052   if(rentry->type==COARSE ||
1053      rentry->type==PARENTCOARSE ||
1054      rentry->type==SCCITEM ||
1055      table==NULL ||
1056      table->unresolvedQueue==NULL) {
1057     return;
1058   }
1059   struct Queue* val;
1060   do {
1061     val=(struct Queue*)0x1;
1062     val=(struct Queue*)LOCKXCHG((unsigned INTPTR*)&(table->unresolvedQueue), (unsigned INTPTR)val);
1063   } while(val==(struct Queue*)0x1);
1064   if(val!=NULL &&
1065      getHead(val)!=NULL &&
1066      getHead(val)->objectptr==rentry) {
1067     // handling pointer is the first item of the queue
1068     // start to resolve until it reaches unresolved pointer or end of queue
1069     INTPTR currentSESE=0;
1070     do {
1071       struct QueueItem* head=getHead(val);
1072       if(head!=NULL) {
1073         REntry* rentry=(REntry*)head->objectptr;
1074         if(*(rentry->pointer)==0) {
1075           // encounters following unresolved pointer
1076           table->unresolvedQueue=val; //released lock
1077           break;
1078         }
1079         removeItem(val,head);
1080
1081         //now, address is resolved
1082
1083         //check if rentry is buffer mode
1084         if(rentry->isBufMode==TRUE) {
1085           if(currentSESE==0) {
1086             queue=rentry->queue;
1087             INITIALIZEBUF(queue);
1088             currentSESE=(INTPTR)rentry;
1089             ADDRENTRYTOBUF(queue,rentry);
1090           } else if(currentSESE==(INTPTR)rentry) {
1091             ADDRENTRYTOBUF(queue,rentry);
1092           } else if(currentSESE!=(INTPTR)rentry) {
1093             RESOLVEBUFFORHASHTABLE(queue,table,(SESEcommon*)rentry->seseRec);
1094             currentSESE=(INTPTR)rentry;
1095             INITIALIZEBUF(queue);
1096             ADDRENTRYTOBUF(rentry->queue,rentry);
1097           }
1098         } else {
1099           if(currentSESE!=0) {
1100             //previous SESE has buf mode, need to invoke resolve buffer
1101             RESOLVEBUFFORHASHTABLE(queue,table,(SESEcommon*)rentry->seseRec);
1102             currentSESE=0;
1103           }
1104           //normal mode
1105           if(ADDTABLEITEM(table, rentry, FALSE)==READY) {
1106             resolveDependencies(rentry);
1107           }
1108         }
1109       } else {
1110         table->unresolvedQueue=NULL; // set hashtable as normal-mode.
1111         break;
1112       }
1113     } while(TRUE);
1114   } else {
1115     // resolved rentry is not head of queue
1116     table->unresolvedQueue=val; //released lock;
1117   }
1118 }
1119 #endif