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
  11
  12 /*
  13 __thread struct Queue* seseCallStack;
  14 __thread pthread_once_t mlpOnceObj = PTHREAD_ONCE_INIT;
  15 void mlpInitOncePerThread() {
  16   seseCallStack = createQueue();
  17 }
  18 */
  19 __thread SESEcommon_p seseCaller;
  20
  21
  22 void* mlpAllocSESErecord( int size ) {
  23   void* newrec = RUNMALLOC( size );
  24   if( newrec == 0 ) {
  25     printf( "mlpAllocSESErecord did not obtain memory!\n" );
  26     exit( -1 );
  27   }
  28   return newrec;
  29 }
  30
  31
  32 void mlpFreeSESErecord( void* seseRecord ) {
  33   RUNFREE( seseRecord );
  34 }
  35
  36 MemoryQueue** mlpCreateMemoryQueueArray(int numMemoryQueue){
  37   int i;
  38   MemoryQueue** newMemoryQueue=(MemoryQueue**)RUNMALLOC( sizeof( MemoryQueue* ) * numMemoryQueue );
  39   for(i=0; i<numMemoryQueue; i++){
  40     newMemoryQueue[i]=createMemoryQueue();
  41   }
  42   return newMemoryQueue;
  43 }
  44
  45 REntry* mlpCreateREntryArray(){
  46   REntry* newREntryArray=(REntry*)RUNMALLOC(sizeof(REntry)*NUMRENTRY);
  47   return newREntryArray;
  48 }
  49
  50 REntry* mlpCreateFineREntry(int type, void* seseToIssue, void* dynID){
  51   REntry* newREntry=(REntry*)RUNMALLOC(sizeof(REntry));
  52   newREntry->type=type;
  53   newREntry->seseRec=seseToIssue;
  54   newREntry->dynID=dynID;
  55   return newREntry;
  56 }
  57
  58 REntry* mlpCreateREntry(int type, void* seseToIssue){
  59   REntry* newREntry=(REntry*)RUNMALLOC(sizeof(REntry));
  60   newREntry->type=type;
  61   newREntry->seseRec=seseToIssue;
  62   return newREntry;
  63 }
  64
  65 int isParent(REntry *r) {
  66   if (r->type==PARENTREAD || r->type==PARENTWRITE) {
  67     return TRUE;
  68   } else {
  69     return FALSE;
  70   }
  71 }
  72
  73 int isParentCoarse(REntry *r){
  74   if (r->type==PARENTCOARSE){
  75     return TRUE;
  76   }else{
  77     return FALSE;
  78   }
  79 }
  80
  81 int isFineRead(REntry *r) {
  82   if (r->type==READ || r->type==PARENTREAD) {
  83     return TRUE;
  84   } else {
  85     return FALSE;
  86   }
  87 }
  88
  89 int isFineWrite(REntry *r) {
  90   if (r->type==WRITE || r->type==PARENTWRITE) {
  91     return TRUE;
  92   } else {
  93     return FALSE;
  94   }
  95 }
  96
  97 int isCoarse(REntry *r){
  98   if(r->type==COARSE || r->type==PARENTCOARSE){
  99     return TRUE;
 100   } else {
 101     return FALSE;
 102   }
 103 }
 104
 105 int isSCC(REntry *r){
 106   if(r->type==SCCITEM){
 107     return TRUE;
 108   } else {
 109     return FALSE;
 110   }
 111 }
 112
 113 int isSingleItem(MemoryQueueItem *qItem){
 114   if(qItem->type==SINGLEITEM){
 115     return TRUE;
 116   } else {
 117     return FALSE;
 118   }
 119 }
 120
 121 int isHashtable(MemoryQueueItem *qItem){
 122   if(qItem->type==HASHTABLE){
 123     return TRUE;
 124   } else {
 125     return FALSE;
 126   }
 127 }
 128
 129 int isVector(MemoryQueueItem *qItem){
 130   if(qItem->type==VECTOR){
 131     return TRUE;
 132   } else {
 133     return FALSE;
 134   }
 135 }
 136
 137 int isReadBinItem(BinItem* b){
 138   if(b->type==READBIN){
 139     return TRUE;
 140   }else{
 141     return FALSE;
 142   }
 143 }
 144
 145 int isWriteBinItem(BinItem* b){
 146   if(b->type==WRITEBIN){
 147     return TRUE;
 148   }else{
 149     return FALSE;
 150   }
 151 }
 152
 153 int generateKey(unsigned int data){
 154   return (data&H_MASK)>> 4;
 155 }
 156
 157 Hashtable* createHashtable(){
 158   int i=0;
 159   Hashtable* newTable=(Hashtable*)RUNMALLOC(sizeof(Hashtable));
 160   newTable->item.type=HASHTABLE;
 161   for(i=0;i<NUMBINS;i++){
 162     newTable->array[i]=(BinElement*)RUNMALLOC(sizeof(BinElement));
 163     newTable->array[i]->head=NULL;
 164     newTable->array[i]->tail=NULL;
 165   }
 166   newTable->unresolvedQueue=NULL;
 167   return newTable;
 168 }
 169
 170 WriteBinItem* createWriteBinItem(){
 171   WriteBinItem* binitem=(WriteBinItem*)RUNMALLOC(sizeof(WriteBinItem));
 172   binitem->item.type=WRITEBIN;
 173   return binitem;
 174 }
 175
 176 ReadBinItem* createReadBinItem(){
 177   ReadBinItem* binitem=(ReadBinItem*)RUNMALLOC(sizeof(ReadBinItem));
 178   binitem->index=0;
 179   binitem->item.type=READBIN;
 180   return binitem;
 181 }
 182
 183 Vector* createVector(){
 184   Vector* vector=(Vector*)RUNMALLOC(sizeof(Vector));
 185   vector->index=0;
 186   vector->item.type=VECTOR;
 187   return vector;
 188 }
 189
 190 SCC* createSCC(){
 191   SCC* scc=(SCC*)RUNMALLOC(sizeof(SCC));
 192   scc->item.type=SINGLEITEM;
 193   return scc;
 194 }
 195
 196 MemoryQueue* createMemoryQueue(){
 197   MemoryQueue* queue = (MemoryQueue*)RUNMALLOC(sizeof(MemoryQueue));
 198   MemoryQueueItem* dummy=(MemoryQueueItem*)RUNMALLOC(sizeof(MemoryQueueItem));
 199   dummy->type=3; // dummy type
 200   dummy->total=0;
 201   dummy->status=READY;
 202   queue->head = dummy;
 203   queue->tail = dummy;
 204   return queue;
 205 }
 206
 207 int ADDRENTRY(MemoryQueue * q, REntry * r) {
 208   if (isFineRead(r) || isFineWrite(r)) {
 209     return ADDTABLE(q, r);
 210   } else if (isCoarse(r)) {
 211     return ADDVECTOR(q, r);
 212   } else if (isSCC(r)) {
 213     return ADDSCC(q, r);
 214   }
 215 }
 216
 217 int ADDTABLE(MemoryQueue *q, REntry *r) {
 218   if(!isHashtable(q->tail)) {
 219     //Fast Case
 220     MemoryQueueItem* tail=q->tail;
 221     if (isParent(r) && tail->total==0 && q->tail==q->head) {
 222       return READY;
 223     }
 224
 225     //Add table
 226     Hashtable* h=createHashtable();
 227     tail->next=(MemoryQueueItem*)h;
 228     //************NEED memory barrier here to ensure compiler does not cache Q.tail.status********
 229     if (BARRIER() && tail->status==READY && tail->total==0 && q->tail==q->head) {
 230       //previous Q item is finished
 231       h->item.status=READY;
 232     }
 233     q->tail=(MemoryQueueItem*)h;
 234     // handle the the queue item case
 235     if(q->head->type==3){
 236       q->head=(MemoryQueueItem*)h;
 237     }
 238   }
 239
 240   //at this point, have table
 241   Hashtable* table=(Hashtable*)q->tail;
 242   r->hashtable=table;
 243   if(r->pointer!=0 && (*(r->pointer)==0 || (*(r->pointer)!=0 && table->unresolvedQueue!=NULL))){
 244      struct Queue* val;
 245     // grab lock on the queue
 246     do {
 247       val=(struct Queue*)0x1;
 248       val=(struct Queue*)LOCKXCHG((unsigned INTPTR*)&(table->unresolvedQueue), (unsigned INTPTR)val);
 249     } while(val==(struct Queue*)0x1);
 250
 251     if(val==NULL){
 252       //first case
 253       if(*(r->pointer)!=0){
 254         // pointer is already resolved.
 255         table->unresolvedQueue=val; //released lock;
 256         return ADDTABLE(q,r);
 257       }
 258       table->unresolvedQueue=(struct Queue*)0x1;
 259       struct Queue* queue=createQueue();
 260       addNewItem(queue,r);
 261       atomic_inc(&table->item.total);
 262       table->unresolvedQueue=queue; // expose new queue
 263     }else{
 264       if(val==NULL){
 265         // someone else has already cleared all queue stuff
 266         table->unresolvedQueue=val; // released lock
 267         return ADDTABLE(q,r);
 268       }
 269       addNewItemBack(val,r);
 270       atomic_inc(&table->item.total);
 271       table->unresolvedQueue=val; // released lock
 272     }
 273     return NOTREADY;
 274   }
 275   if(r->pointer!=0){
 276     r->dynID=(void*)*(r->pointer); // interim fix.
 277   }
 278   BinItem * val;
 279   int key=generateKey((unsigned int)(unsigned INTPTR)r->dynID);
 280   do {
 281     val=(BinItem*)0x1;
 282     BinElement* bin=table->array[key];
 283     val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(bin->head), (unsigned INTPTR)val);//note...talk to me about optimizations here.
 284   } while(val==(BinItem*)0x1);
 285   //at this point have locked bin
 286   if (val==NULL) {
 287     return EMPTYBINCASE(table, table->array[key], r, TRUE);
 288   } else {
 289     if (isFineWrite(r)) {
 290       return WRITEBINCASE(table, r, val, key, TRUE);
 291     } else if (isFineRead(r)) {
 292       return READBINCASE(table, r, val, key, TRUE);
 293     }
 294   }
 295 }
 296
 297 int ADDTABLEITEM(Hashtable* table, REntry* r){
 298   BinItem * val;
 299   int key=generateKey((unsigned int)(unsigned INTPTR)r->dynID);
 300   do {
 301     val=(BinItem*)0x1;
 302     BinElement* bin=table->array[key];
 303     val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(bin->head), (unsigned INTPTR)val);//note...talk to me about optimizations here.
 304   } while(val==(BinItem*)0x1);
 305   //at this point have locked bin
 306   if (val==NULL) {
 307     return EMPTYBINCASE(table, table->array[key], r, FALSE);
 308   } else {
 309     if (isFineWrite(r)) {
 310       return WRITEBINCASE(table, r, val, key, FALSE);
 311     } else if (isFineRead(r)) {
 312       return READBINCASE(table, r, val, key, FALSE);
 313     }
 314   }
 315 }
 316
 317 int EMPTYBINCASE(Hashtable *T, BinElement* be, REntry *r, int inc) {
 318   int retval;
 319   BinItem* b;
 320   if (isFineWrite(r)) {
 321     b=(BinItem*)createWriteBinItem();
 322     ((WriteBinItem*)b)->val=r;//<-only different statement
 323   } else if (isFineRead(r)) {
 324     b=(BinItem*)createReadBinItem();
 325     ReadBinItem* readbin=(ReadBinItem*)b;
 326     readbin->array[readbin->index++]=r;
 327   }
 328   b->total=1;
 329
 330   if (T->item.status==READY) {
 331     //current entry is ready
 332     b->status=READY;
 333     retval=READY;
 334     if (isParent(r)) {
 335       be->head=NULL; // released lock
 336       return retval;
 337     }
 338   } else {
 339     b->status=NOTREADY;
 340     retval=NOTREADY;
 341   }
 342
 343   if(inc){
 344     atomic_inc(&T->item.total);
 345   }
 346   r->hashtable=T;
 347   r->binitem=b;
 348   be->tail=b;
 349   be->head=b;//released lock
 350   return retval;
 351 }
 352
 353 int WRITEBINCASE(Hashtable *T, REntry *r, BinItem *val, int key, int inc) {
 354   //chain of bins exists => tail is valid
 355   //if there is something in front of us, then we are not ready
 356
 357   int retval;
 358   BinElement* be=T->array[key];
 359
 360   BinItem *bintail=be->tail;
 361
 362   WriteBinItem *b=createWriteBinItem();
 363   b->val=r;
 364   b->item.total=1;
 365
 366   // note: If current table clears all dependencies, then write bin is ready
 367   if (T->item.total==0){
 368     retval=READY;
 369   }else{
 370     retval=NOTREADY;
 371   }
 372   b->item.status=retval;
 373   //  b->item.status=NOTREADY;
 374
 375   if(inc){
 376     atomic_inc(&T->item.total);
 377   }
 378
 379   r->hashtable=T;
 380   r->binitem=(BinItem*)b;
 381
 382   be->tail->next=(BinItem*)b;
 383   be->tail=(BinItem*)b;
 384   be->head=val;
 385   return retval;
 386 }
 387
 388 READBINCASE(Hashtable *T, REntry *r, BinItem *val, int key, int inc) {
 389   BinItem * bintail=T->array[key]->tail;
 390   if (isReadBinItem(bintail)) {
 391     return TAILREADCASE(T, r, val, bintail, key);
 392   } else if (!isReadBinItem(bintail)) {
 393     TAILWRITECASE(T, r, val, bintail, key);
 394     return NOTREADY;
 395   }
 396 }
 397
 398 int TAILREADCASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key, int inc) {
 399   ReadBinItem * readbintail=(ReadBinItem*)T->array[key]->tail;
 400   int status, retval;
 401   if (readbintail->item.status=READY) {
 402     status=READY;
 403     retval=READY;
 404     if (isParent(r)) {
 405       T->array[key]->head=val;//released lock
 406       return READY;
 407     }
 408   } else {
 409     status=NOTREADY;
 410     retval=NOTREADY;
 411   }
 412
 413   if (readbintail->index==NUMREAD) { // create new read group
 414     ReadBinItem* rb=createReadBinItem();
 415     rb->array[rb->index++]=r;
 416     rb->item.total=1;//safe only because item could not have started
 417     rb->item.status=status;
 418     T->array[key]->tail->next=(BinItem*)rb;
 419     T->array[key]->tail=(BinItem*)rb;
 420     r->binitem=(BinItem*)rb;
 421   } else { // group into old tail
 422     readbintail->array[readbintail->index++]=r;
 423     atomic_inc(&readbintail->item.total);
 424     r->binitem=(BinItem*)readbintail;
 425     //printf("grouping with %d\n",readbintail->index);
 426   }
 427   if(inc){
 428     atomic_inc(&T->item.total);
 429   }
 430   r->hashtable=T;
 431   T->array[key]->head=val;//released lock
 432   return retval;
 433 }
 434
 435 TAILWRITECASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key, int inc) {
 436   //  WriteBinItem* wb=createWriteBinItem();
 437   //wb->val=r;
 438   //wb->item.total=1;//safe because item could not have started
 439   //wb->item.status=NOTREADY;
 440   ReadBinItem* rb=createReadBinItem();
 441   rb->array[rb->index++]=r;
 442   rb->item.total=1;//safe because item could not have started
 443   rb->item.status=NOTREADY;
 444   if(inc){
 445     atomic_inc(&T->item.total);
 446   }
 447   r->hashtable=T;
 448   r->binitem=(BinItem*)rb;
 449   T->array[key]->tail->next=(BinItem*)rb;
 450   T->array[key]->tail=(BinItem*)rb;
 451   T->array[key]->head=val;//released lock
 452 }
 453
 454 ADDVECTOR(MemoryQueue *Q, REntry *r) {
 455   if(!isVector(Q->tail)) {
 456     //Fast Case
 457     if (isParentCoarse(r) && Q->tail->total==0 && Q->tail==Q->head) {
 458       return READY;
 459     }
 460
 461     //added vector
 462     Vector* V=createVector();
 463     Q->tail->next=(MemoryQueueItem*)V;
 464     //************NEED memory barrier here to ensure compiler does not cache Q.tail.status******
 465     if (BARRIER() && Q->tail->status==READY&&Q->tail->total==0) {
 466       //previous Q item is finished
 467       V->item.status=READY;
 468     }
 469     Q->tail=(MemoryQueueItem*)V;
 470     // handle the the queue item case
 471     if(Q->head->type==3){
 472       Q->head=(MemoryQueueItem*)V;
 473     }
 474   }
 475   //at this point, have vector
 476   Vector* V=(Vector*)Q->tail;
 477   if (V->index==NUMITEMS) {
 478     //vector is full
 479     //added vector
 480     V=createVector();
 481     V->item.status=NOTREADY;
 482     Q->tail->next=(MemoryQueueItem*)V;
 483     //***NEED memory barrier here to ensure compiler does not cache Q.tail.status******
 484     if (BARRIER() && Q->tail->status==READY) {
 485       V->item.status=READY;
 486     }
 487     Q->tail=(MemoryQueueItem*)V;
 488   }
 489
 490   atomic_inc(&V->item.total);
 491   //expose entry
 492   int index=V->index;
 493   V->array[index]=r;
 494   //*****NEED memory barrier here to ensure compiler does not reorder writes to V.array and V.index
 495   BARRIER();
 496   V->index++;
 497   //*****NEED memory barrier here to ensure compiler does not cache V.status*********
 498   r->vector=V;
 499   if (BARRIER() && V->item.status==READY) {
 500     void* flag=NULL;
 501     flag=(void*)LOCKXCHG((unsigned INTPTR*)&(V->array[index]), (unsigned INTPTR)flag);
 502     if (flag!=NULL) {
 503       if (isParent(r)) { //parent's retire immediately
 504         atomic_dec(&V->item.total);
 505       }
 506       return READY;
 507     } else {
 508       return NOTREADY;//<- means that some other dispatcher got this one...so need to do accounting correctly
 509     }
 510   } else {
 511     return NOTREADY;
 512   }
 513 }
 514
 515
 516 //SCC's don't come in parent variety
 517 ADDSCC(MemoryQueue *Q, REntry *r) {
 518   //added SCC
 519   SCC* S=createSCC();
 520   S->item.total=1;
 521   S->val=r;
 522   r->scc=S;
 523   Q->tail->next=(MemoryQueueItem*)S;
 524   //*** NEED BARRIER HERE
 525   if (BARRIER() && Q->tail->status==READY && Q->tail->total==0 && Q->tail==Q->head) {
 526     //previous Q item is finished
 527     S->item.status=READY;
 528     Q->tail=(MemoryQueueItem*)S;
 529     // handle the the queue item case
 530     if(Q->head->type==3){
 531       Q->head=(MemoryQueueItem*)S;
 532     }
 533     void* flag=NULL;
 534     flag=(void*)LOCKXCHG((unsigned INTPTR*)&(S->val), (unsigned INTPTR)flag);
 535     if (flag!=NULL) {
 536       return READY;
 537     } else {
 538       return NOTREADY;//<- means that some other dispatcher got this one...so need to do accounting correctly
 539     }
 540   } else {
 541     Q->tail=(MemoryQueueItem*)S;
 542     return NOTREADY;
 543   }
 544 }
 545
 546
 547 void RETIRERENTRY(MemoryQueue* Q, REntry * r) {
 548   if (isFineWrite(r)||isFineRead(r)) {
 549     RETIREHASHTABLE(Q, r);
 550   } else if (isCoarse(r)) {
 551     RETIREVECTOR(Q, r);
 552   } else if (isSCC(r)) {
 553     RETIRESCC(Q, r);
 554   }
 555 }
 556
 557 RETIRESCC(MemoryQueue *Q, REntry *r) {
 558   SCC* s=r->scc;
 559   s->item.total=0;//don't need atomicdec
 560   RESOLVECHAIN(Q);
 561 }
 562
 563
 564 RETIREHASHTABLE(MemoryQueue *q, REntry *r) {
 565   Hashtable *T=r->hashtable;
 566   BinItem *b=r->binitem;
 567   RETIREBIN(T,r,b);
 568   atomic_dec(&T->item.total);
 569   if (T->item.next!=NULL && T->item.total==0) {
 570     RESOLVECHAIN(q);
 571   }
 572 }
 573
 574 RETIREBIN(Hashtable *T, REntry *r, BinItem *b) {
 575   int key=generateKey((unsigned int)(unsigned INTPTR)r->dynID);
 576   if(isFineRead(r)) {
 577     atomic_dec(&b->total);
 578   }
 579   if (isFineWrite(r) || (isFineRead(r) && b->next!=NULL && b->total==0)) {
 580       // CHECK FIRST IF next is nonnull to guarantee that b.total cannot change
 581     BinItem * val;
 582     do {
 583       val=(BinItem*)0x1;
 584       val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(T->array[key]->head), (unsigned INTPTR)val);
 585     } while(val==(BinItem*)0x1);
 586     // at this point have locked bin
 587     BinItem *ptr=val;
 588     int haveread=FALSE;
 589      int i;
 590     while (ptr!=NULL) {
 591        if (isReadBinItem(ptr)) {
 592         ReadBinItem* rptr=(ReadBinItem*)ptr;
 593         if (rptr->item.status==NOTREADY) {
 594           for (i=0;i<rptr->index;i++) {
 595             resolveDependencies(rptr->array[i]);
 596             if (isParent(rptr->array[i])) {
 597               //parents go immediately
 598               atomic_dec(&rptr->item.total);
 599               atomic_dec(&T->item.total);
 600             }
 601           }
 602         }
 603         rptr->item.status=READY;
 604         if (rptr->item.next==NULL) {
 605           break;
 606         }
 607         if (rptr->item.total!=0) {
 608           haveread=TRUE;
 609         } else if ((BinItem*)rptr==val) {
 610           val=val->next;
 611         }
 612       } else if(isWriteBinItem(ptr)) {
 613         if (haveread)
 614           break;
 615         if(ptr->status==NOTREADY){
 616           resolveDependencies(((WriteBinItem*)ptr)->val);
 617           ptr->status=READY;
 618           if(isParent(((WriteBinItem*)ptr)->val)){
 619             atomic_dec(&T->item.total);
 620             val=val->next;
 621           }else
 622             break;
 623         }else{ // write bin is already resolved
 624           val=val->next;
 625         }
 626         /*
 627         if(ptr->status==NOTREADY) {
 628           resolveDependencies(((WriteBinItem*)ptr)->val);
 629         }
 630           ptr->status=READY;
 631           if (isParent(((WriteBinItem*)ptr)->val)) {
 632             atomic_dec(&T->item.total);
 633             //val=val->next;
 634             val=ptr->next;
 635           } else
 636             break;
 637         }
 638         */
 639       }
 640       ptr=ptr->next;
 641     }
 642     T->array[key]->head=val; // release lock
 643   }
 644 }
 645
 646
 647 RETIREVECTOR(MemoryQueue *Q, REntry *r) {
 648   Vector* V=r->vector;
 649   atomic_dec(&V->item.total);
 650   if (V->item.next!=NULL && V->item.total==0) { //NOTE: ORDERING CRUCIAL HERE
 651     RESOLVECHAIN(Q);
 652   }
 653 }
 654
 655 RESOLVECHAIN(MemoryQueue *Q) {
 656   while(TRUE) {
 657     MemoryQueueItem* head=Q->head;
 658     if (head->next==NULL||head->total!=0) {
 659       //item is not finished
 660       if (head->status!=READY) {
 661         //need to update status
 662         head->status=READY;
 663         if (isHashtable(head)) {
 664           RESOLVEHASHTABLE(Q, head);
 665         } else if (isVector(head)) {
 666           RESOLVEVECTOR(Q, head);
 667         } else if (isSingleItem(head)) {
 668           RESOLVESCC(head);
 669         }
 670         if (head->next==NULL)
 671           break;
 672         if (head->total!=0)
 673           break;
 674       } else
 675         break;
 676     }
 677     MemoryQueueItem* nextitem=head->next;
 678     CAS((unsigned INTPTR*)&(Q->head), (unsigned INTPTR)head, (unsigned INTPTR)nextitem);
 679     //oldvalue not needed...  if we fail we just repeat
 680   }
 681 }
 682
 683
 684 RESOLVEHASHTABLE(MemoryQueue *Q, Hashtable *T) {
 685   int binidx;
 686   for (binidx=0;binidx<NUMBINS;binidx++) {
 687     BinElement* bin=T->array[binidx];
 688     BinItem* val;
 689     do {
 690       val=(BinItem*)1;
 691       val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(bin->head), (unsigned INTPTR)val);
 692     } while (val==(BinItem*)1);
 693     //at this point have locked bin
 694     int haveread=FALSE;
 695     BinItem* ptr=val;
 696     if(ptr!=NULL&&ptr->status==NOTREADY) {
 697       do {
 698         if (isWriteBinItem(ptr)) {
 699           if (haveread)
 700             break;
 701           resolveDependencies(((WriteBinItem*)ptr)->val);
 702           ptr->status=READY;
 703           if (isParent(((WriteBinItem*)ptr)->val)) {
 704             atomic_dec(&T->item.total);
 705             val=val->next;
 706           } else
 707             break;
 708         } else if (isReadBinItem(ptr)) {
 709           int i;
 710           ReadBinItem* rptr=(ReadBinItem*)ptr;
 711           for(i=0;i<rptr->index;i++) {
 712             resolveDependencies(rptr->array[i]);
 713             if (isParent(rptr->array[i])) {
 714               atomic_dec(&rptr->item.total);
 715               atomic_dec(&T->item.total);
 716             }
 717           }
 718           if (rptr->item.next==NULL||rptr->item.total!=0) {
 719             haveread=TRUE;
 720           } else if((BinItem*)rptr==val) {
 721             val=val->next;
 722           }
 723           rptr->item.status=READY; {
 724           }
 725           ptr=ptr->next;
 726         }
 727       }while(ptr!=NULL);
 728     }
 729     bin->head=val; // released lock;
 730   }
 731 }
 732
 733 RESOLVEVECTOR(MemoryQueue *q, Vector *V) {
 734   int i;
 735   Vector* tmp=V;
 736   //handle ready cases
 737   while(TRUE) {
 738     //enqueue everything
 739     for (i=0;i<NUMITEMS;i++) {
 740       REntry* val=NULL;
 741       val=(REntry*)LOCKXCHG((unsigned INTPTR*)&(tmp->array[i]), (unsigned INTPTR)val);
 742       if (val!=NULL) {
 743         resolveDependencies(val);
 744         if (isParent(val)) {
 745           atomic_dec(&tmp->item.total);
 746         }
 747       }
 748     }
 749     if (tmp->item.next!=NULL&&isVector(tmp->item.next)) {
 750       tmp=(Vector*)tmp->item.next;
 751     } else {
 752       break;
 753     }
 754   }
 755 }
 756
 757 RESOLVESCC(SCC *S) {
 758   //precondition: SCC's state is READY
 759   void* flag=NULL;
 760   flag=(void*)LOCKXCHG((unsigned INTPTR*)&(S->val), (unsigned INTPTR)flag);
 761   if (flag!=NULL) {
 762     resolveDependencies(flag);
 763   }
 764 }
 765
 766
 767 resolveDependencies(REntry* rentry){
 768   SESEcommon* seseCommon=(SESEcommon*)rentry->seseRec;
 769   if(rentry->type==READ || rentry->type==WRITE || rentry->type==COARSE || rentry->type==SCCITEM){
 770     if( atomic_sub_and_test(1, &(seseCommon->unresolvedDependencies)) ){
 771       workScheduleSubmit(seseCommon);
 772     }
 773   }else if(rentry->type==PARENTREAD || rentry->type==PARENTWRITE ||rentry->type==PARENTCOARSE){
 774      psem_give(&(rentry->parentStallSem));
 775   }
 776 }
 777
 778 resolvePointer(REntry* rentry){
 779   rentry->dynID=(void*)*(rentry->pointer); // interim.
 780   Hashtable* table=rentry->hashtable;
 781   struct Queue* val;
 782   do {
 783     val=(struct Queue*)0x1;
 784     val=(struct Queue*)LOCKXCHG((unsigned INTPTR*)&(table->unresolvedQueue), (unsigned INTPTR)val);
 785   } while(val==(struct Queue*)0x1);
 786   if(val!=NULL && getHead(val)->objectptr==rentry){
 787     // handling pointer is the first item of the queue
 788     // start to resolve until it reaches unresolved pointer or end of queue
 789     do{
 790       struct QueueItem* head=getHead(val);
 791       if(head!=NULL){
 792         REntry* rentry=(REntry*)head->objectptr;
 793         if(*(rentry->pointer)==0){
 794           // encounters following unresolved pointer
 795           table->unresolvedQueue=val;//released lock
 796           break;
 797         }
 798         removeItem(val,head);
 799         if(ADDTABLEITEM(table, rentry)==READY){
 800           SESEcommon* seseCommon=(SESEcommon*)rentry->seseRec;
 801           atomic_sub_and_test(1, &(seseCommon->unresolvedDependencies));
 802         }
 803       }else{
 804         table->unresolvedQueue=NULL; // set hashtable as normal-mode.
 805         break;
 806       }
 807     }while(TRUE);
 808   }else{
 809     table->unresolvedQueue=val;//released lock;
 810   }
 811 }
 812