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