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
  14 /*
  15 __thread struct Queue* seseCallStack;
  16 __thread pthread_once_t mlpOnceObj = PTHREAD_ONCE_INIT;
  17 void mlpInitOncePerThread() {
  18   seseCallStack = createQueue();
  19 }
  20 */
  21 __thread SESEcommon_p seseCaller;
  22
  23
  24 void* mlpAllocSESErecord( int size ) {
  25   void* newrec = RUNMALLOC( size );
  26   if( newrec == 0 ) {
  27     printf( "mlpAllocSESErecord did not obtain memory!\n" );
  28     exit( -1 );
  29   }
  30   return newrec;
  31 }
  32
  33
  34 void mlpFreeSESErecord( void* seseRecord ) {
  35   RUNFREE( seseRecord );
  36 }
  37
  38 MemoryQueue** mlpCreateMemoryQueueArray(int numMemoryQueue){
  39   int i;
  40   MemoryQueue** newMemoryQueue=(MemoryQueue**)RUNMALLOC( sizeof( MemoryQueue* ) * numMemoryQueue );
  41   for(i=0; i<numMemoryQueue; i++){
  42     newMemoryQueue[i]=createMemoryQueue();
  43   }
  44   return newMemoryQueue;
  45 }
  46
  47 REntry* mlpCreateREntryArray(){
  48   REntry* newREntryArray=(REntry*)RUNMALLOC(sizeof(REntry)*NUMRENTRY);
  49   return newREntryArray;
  50 }
  51
  52 REntry* mlpCreateFineREntry(int type, void* seseToIssue, void* dynID){
  53   REntry* newREntry=(REntry*)RUNMALLOC(sizeof(REntry));
  54   newREntry->type=type;
  55   newREntry->seseRec=seseToIssue;
  56   newREntry->pointer=dynID;
  57   if((*newREntry->pointer)!=0){// make sure it is not unresolved address.
  58     struct ___Object___ * obj=(struct ___Object___*)((unsigned INTPTR)*newREntry->pointer);
  59     newREntry->oid=obj->oid;
  60   }
  61   return newREntry;
  62 }
  63
  64 REntry* mlpCreateREntry(int type, void* seseToIssue){
  65   REntry* newREntry=(REntry*)RUNMALLOC(sizeof(REntry));
  66   newREntry->type=type;
  67   newREntry->seseRec=seseToIssue;
  68   return newREntry;
  69 }
  70
  71 int isParent(REntry *r) {
  72   if (r->type==PARENTREAD || r->type==PARENTWRITE || r->type==PARENTCOARSE) {
  73     return TRUE;
  74   } else {
  75     return FALSE;
  76   }
  77 }
  78
  79 int isParentCoarse(REntry *r){
  80   if (r->type==PARENTCOARSE){
  81     return TRUE;
  82   }else{
  83     return FALSE;
  84   }
  85 }
  86
  87 int isFineRead(REntry *r) {
  88   if (r->type==READ || r->type==PARENTREAD) {
  89     return TRUE;
  90   } else {
  91     return FALSE;
  92   }
  93 }
  94
  95 int isFineWrite(REntry *r) {
  96   if (r->type==WRITE || r->type==PARENTWRITE) {
  97     return TRUE;
  98   } else {
  99     return FALSE;
 100   }
 101 }
 102
 103 int isCoarse(REntry *r){
 104   if(r->type==COARSE || r->type==PARENTCOARSE){
 105     return TRUE;
 106   } else {
 107     return FALSE;
 108   }
 109 }
 110
 111 int isSCC(REntry *r){
 112   if(r->type==SCCITEM){
 113     return TRUE;
 114   } else {
 115     return FALSE;
 116   }
 117 }
 118
 119 int isSingleItem(MemoryQueueItem *qItem){
 120   if(qItem->type==SINGLEITEM){
 121     return TRUE;
 122   } else {
 123     return FALSE;
 124   }
 125 }
 126
 127 int isHashtable(MemoryQueueItem *qItem){
 128   if(qItem->type==HASHTABLE){
 129     return TRUE;
 130   } else {
 131     return FALSE;
 132   }
 133 }
 134
 135 int isVector(MemoryQueueItem *qItem){
 136   if(qItem->type==VECTOR){
 137     return TRUE;
 138   } else {
 139     return FALSE;
 140   }
 141 }
 142
 143 int isReadBinItem(BinItem* b){
 144   if(b->type==READBIN){
 145     return TRUE;
 146   }else{
 147     return FALSE;
 148   }
 149 }
 150
 151 int isWriteBinItem(BinItem* b){
 152   if(b->type==WRITEBIN){
 153     return TRUE;
 154   }else{
 155     return FALSE;
 156   }
 157 }
 158
 159 int generateKey(unsigned int data){
 160   return (data&H_MASK)>> 4;
 161 }
 162
 163 Hashtable* createHashtable(){
 164   int i=0;
 165   Hashtable* newTable=(Hashtable*)RUNMALLOC(sizeof(Hashtable));
 166   newTable->item.type=HASHTABLE;
 167   for(i=0;i<NUMBINS;i++){
 168     newTable->array[i]=(BinElement*)RUNMALLOC(sizeof(BinElement));
 169     newTable->array[i]->head=NULL;
 170     newTable->array[i]->tail=NULL;
 171   }
 172   newTable->unresolvedQueue=NULL;
 173   return newTable;
 174 }
 175
 176 WriteBinItem* createWriteBinItem(){
 177   WriteBinItem* binitem=(WriteBinItem*)RUNMALLOC(sizeof(WriteBinItem));
 178   binitem->item.type=WRITEBIN;
 179   return binitem;
 180 }
 181
 182 ReadBinItem* createReadBinItem(){
 183   ReadBinItem* binitem=(ReadBinItem*)RUNMALLOC(sizeof(ReadBinItem));
 184   binitem->index=0;
 185   binitem->item.type=READBIN;
 186   return binitem;
 187 }
 188
 189 Vector* createVector(){
 190   Vector* vector=(Vector*)RUNMALLOC(sizeof(Vector));
 191   vector->index=0;
 192   vector->item.type=VECTOR;
 193   return vector;
 194 }
 195
 196 SCC* createSCC(){
 197   SCC* scc=(SCC*)RUNMALLOC(sizeof(SCC));
 198   scc->item.type=SINGLEITEM;
 199   return scc;
 200 }
 201
 202 MemoryQueue* createMemoryQueue(){
 203   MemoryQueue* queue = (MemoryQueue*)RUNMALLOC(sizeof(MemoryQueue));
 204   MemoryQueueItem* dummy=(MemoryQueueItem*)RUNMALLOC(sizeof(MemoryQueueItem));
 205   dummy->type=3; // dummy type
 206   dummy->total=0;
 207   dummy->status=READY;
 208   queue->head = dummy;
 209   queue->tail = dummy;
 210   return queue;
 211 }
 212
 213 int ADDRENTRY(MemoryQueue * q, REntry * r) {
 214   if (isFineRead(r) || isFineWrite(r)) {
 215     return ADDTABLE(q, r);
 216   } else if (isCoarse(r)) {
 217     return ADDVECTOR(q, r);
 218   } else if (isSCC(r)) {
 219     return ADDSCC(q, r);
 220   }
 221 }
 222
 223 int ADDTABLE(MemoryQueue *q, REntry *r) {
 224   if(!isHashtable(q->tail)) {
 225     //Fast Case
 226     MemoryQueueItem* tail=q->tail;
 227     if (isParent(r) && tail->total==0 && q->tail==q->head) {
 228       return READY;
 229     }
 230
 231     //Add table
 232     Hashtable* h=createHashtable();
 233     tail->next=(MemoryQueueItem*)h;
 234     //************NEED memory barrier here to ensure compiler does not cache Q.tail.status********
 235     if (BARRIER() && tail->status==READY && tail->total==0 && q->tail==q->head) {
 236       //previous Q item is finished
 237       h->item.status=READY;
 238     }
 239     q->tail=(MemoryQueueItem*)h;
 240     // handle the the queue item case
 241     if(q->head->type==3){
 242       q->head=(MemoryQueueItem*)h;
 243     }
 244   }
 245
 246   //at this point, have table
 247   Hashtable* table=(Hashtable*)q->tail;
 248   r->hashtable=table; // set rentry's hashtable
 249   if((*(r->pointer)==0 || (*(r->pointer)!=0 && BARRIER() && table->unresolvedQueue!=NULL))){
 250     struct Queue* val;
 251     // grab lock on the queue
 252     do {
 253       val=(struct Queue*)0x1;
 254       val=(struct Queue*)LOCKXCHG((unsigned INTPTR*)&(table->unresolvedQueue), (unsigned INTPTR)val);
 255     } while(val==(struct Queue*)0x1);
 256     if(val==NULL){
 257       //queue is null, first case
 258       if(*(r->pointer)!=0){
 259         // check whether pointer is already resolved, or not.
 260         table->unresolvedQueue=NULL; //released lock;
 261         return ADDTABLEITEM(table,r,TRUE);
 262       }
 263       struct Queue* queue=createQueue();
 264       addNewItemBack(queue,r);
 265       atomic_inc(&table->item.total);
 266       table->unresolvedQueue=queue; // expose new queue
 267     }else{
 268       // add unresolved rentry at the end of the queue.
 269       addNewItemBack(val,r);
 270       atomic_inc(&table->item.total);
 271       table->unresolvedQueue=val; // released lock
 272     }
 273     return NOTREADY;
 274   }
 275   BinItem * val;
 276   //int key=generateKey((unsigned int)(unsigned INTPTR)*(r->pointer));
 277   int key=generateKey(r->oid);
 278   do {
 279     val=(BinItem*)0x1;
 280     BinElement* bin=table->array[key];
 281     val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(bin->head), (unsigned INTPTR)val);//note...talk to me about optimizations here.
 282   } while(val==(BinItem*)0x1);
 283   //at this point have locked bin
 284   if (val==NULL) {
 285     return EMPTYBINCASE(table, table->array[key], r, TRUE);
 286   } else {
 287     if (isFineWrite(r)) {
 288       return WRITEBINCASE(table, r, val, key, TRUE);
 289     } else if (isFineRead(r)) {
 290       return READBINCASE(table, r, val, key, TRUE);
 291     }
 292   }
 293 }
 294
 295 int ADDTABLEITEM(Hashtable* table, REntry* r, int inc){
 296
 297   BinItem * val;
 298   //  int key=generateKey((unsigned int)(unsigned INTPTR)*(r->pointer));
 299   int key=generateKey(r->oid);
 300   do {
 301     val=(BinItem*)0x1;
 302     BinElement* bin=table->array[key];
 303     val=(BinItem*)LOCKXCHG((unsigned INTPTR*)&(bin->head), (unsigned INTPTR)val);
 304   } while(val==(BinItem*)0x1);
 305   //at this point have locked bin
 306   if (val==NULL) {
 307     return EMPTYBINCASE(table, table->array[key], r, inc);
 308   } else {
 309     if (isFineWrite(r)) {
 310       return WRITEBINCASE(table, r, val, key, inc);
 311     } else if (isFineRead(r)) {
 312       return READBINCASE(table, r, val, key, inc);
 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=NOTREADY;
 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
 368
 369   if(inc){
 370     atomic_inc(&T->item.total);
 371   }
 372
 373   r->hashtable=T;
 374   r->binitem=(BinItem*)b;
 375
 376   be->tail->next=(BinItem*)b;
 377   //need to check if we can go...
 378   BARRIER();
 379   if (T->item.status==READY) {
 380     for(;val!=NULL;val=val->next) {
 381       if (val==((BinItem *)b)) {
 382         //ready to retire
 383         retval=READY;
 384         if (isParent(r)) {
 385           b->item.status=retval;//unsure if really needed at this point..
 386           be->head=NULL; // released lock
 387           return retval;
 388         }
 389         break;
 390       } else if (val->total!=0) {
 391         break;
 392       }
 393     }
 394   }
 395
 396   b->item.status=retval;
 397   be->tail=(BinItem*)b;
 398   be->head=val;
 399   return retval;
 400 }
 401
 402 READBINCASE(Hashtable *T, REntry *r, BinItem *val, int key, int inc) {
 403   BinItem * bintail=T->array[key]->tail;
 404   if (isReadBinItem(bintail)) {
 405     return TAILREADCASE(T, r, val, bintail, key, inc);
 406   } else if (!isReadBinItem(bintail)) {
 407     TAILWRITECASE(T, r, val, bintail, key, inc);
 408     return NOTREADY;
 409   }
 410 }
 411
 412 int TAILREADCASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key, int inc) {
 413   ReadBinItem * readbintail=(ReadBinItem*)T->array[key]->tail;
 414   int status, retval;
 415   if (readbintail->item.status==READY) {
 416     status=READY;
 417     retval=READY;
 418     if (isParent(r)) {
 419       T->array[key]->head=val;//released lock
 420       return READY;
 421     }
 422   } else {
 423     status=NOTREADY;
 424     retval=NOTREADY;
 425   }
 426
 427   if (readbintail->index==NUMREAD) { // create new read group
 428     ReadBinItem* rb=createReadBinItem();
 429     rb->array[rb->index++]=r;
 430     rb->item.total=1;//safe only because item could not have started
 431     rb->item.status=status;
 432     T->array[key]->tail->next=(BinItem*)rb;
 433     T->array[key]->tail=(BinItem*)rb;
 434     r->binitem=(BinItem*)rb;
 435   } else { // group into old tail
 436     readbintail->array[readbintail->index++]=r;
 437     atomic_inc(&readbintail->item.total);
 438     r->binitem=(BinItem*)readbintail;
 439     //printf("grouping with %d\n",readbintail->index);
 440   }
 441   if(inc){
 442     atomic_inc(&T->item.total);
 443   }
 444   r->hashtable=T;
 445   T->array[key]->head=val;//released lock
 446   return retval;
 447 }
 448
 449 TAILWRITECASE(Hashtable *T, REntry *r, BinItem *val, BinItem *bintail, int key, int inc) {
 450   //  WriteBinItem* wb=createWriteBinItem();
 451   //wb->val=r;
 452   //wb->item.total=1;//safe because item could not have started
 453   //wb->item.status=NOTREADY;
 454   ReadBinItem* rb=createReadBinItem();
 455   rb->array[rb->index++]=r;
 456   rb->item.total=1;//safe because item could not have started
 457   rb->item.status=NOTREADY;
 458   if(inc){
 459     atomic_inc(&T->item.total);
 460   }
 461   r->hashtable=T;
 462   r->binitem=(BinItem*)rb;
 463   T->array[key]->tail->next=(BinItem*)rb;
 464   T->array[key]->tail=(BinItem*)rb;
 465   T->array[key]->head=val;//released lock
 466 }
 467
 468 ADDVECTOR(MemoryQueue *Q, REntry *r) {
 469   if(!isVector(Q->tail)) {
 470     //Fast Case
 471     if (isParentCoarse(r) && Q->tail->total==0 && Q->tail==Q->head) {
 472       return READY;
 473     }
 474
 475     //added vector
 476     Vector* V=createVector();
 477     Q->tail->next=(MemoryQueueItem*)V;
 478     //************NEED memory barrier here to ensure compiler does not cache Q.tail.status******
 479     if (BARRIER() && Q->tail->status==READY&&Q->tail->total==0) {
 480       //previous Q item is finished
 481       V->item.status=READY;
 482     }
 483     Q->tail=(MemoryQueueItem*)V;
 484     // handle the the queue item case
 485     if(Q->head->type==3){
 486       Q->head=(MemoryQueueItem*)V;
 487     }
 488   }
 489   //at this point, have vector
 490   Vector* V=(Vector*)Q->tail;
 491   if (V->index==NUMITEMS) {
 492     //vector is full
 493     //added vector
 494     V=createVector();
 495     V->item.status=NOTREADY;
 496     Q->tail->next=(MemoryQueueItem*)V;
 497     //***NEED memory barrier here to ensure compiler does not cache Q.tail.status******
 498     if (BARRIER() && Q->tail->status==READY) {
 499       V->item.status=READY;
 500     }
 501     Q->tail=(MemoryQueueItem*)V;
 502   }
 503
 504   atomic_inc(&V->item.total);
 505   //expose entry
 506   int index=V->index;
 507   V->array[index]=r;
 508   //*****NEED memory barrier here to ensure compiler does not reorder writes to V.array and V.index
 509   BARRIER();
 510   V->index++;
 511   //*****NEED memory barrier here to ensure compiler does not cache V.status*********
 512   r->vector=V;
 513   if (BARRIER() && V->item.status==READY) {
 514     void* flag=NULL;
 515     flag=(void*)LOCKXCHG((unsigned INTPTR*)&(V->array[index]), (unsigned INTPTR)flag);
 516     if (flag!=NULL) {
 517       if (isParentCoarse(r)) { //parent's retire immediately
 518         atomic_dec(&V->item.total);
 519         V->index--;
 520       }
 521       return READY;
 522     } else {
 523       return NOTREADY;//<- means that some other dispatcher got this one...so need to do accounting correctly
 524     }
 525   } else {
 526     return NOTREADY;
 527   }
 528 }
 529
 530
 531 //SCC's don't come in parent variety
 532 ADDSCC(MemoryQueue *Q, REntry *r) {
 533   //added SCC
 534   SCC* S=createSCC();
 535   S->item.total=1;
 536   S->val=r;
 537   r->scc=S;
 538   Q->tail->next=(MemoryQueueItem*)S;
 539   //*** NEED BARRIER HERE
 540   if (BARRIER() && Q->tail->status==READY && Q->tail->total==0 && Q->tail==Q->head) {
 541     //previous Q item is finished
 542     S->item.status=READY;
 543     Q->tail=(MemoryQueueItem*)S;
 544     // handle the the queue item case
 545     if(Q->head->type==3){
 546       Q->head=(MemoryQueueItem*)S;
 547     }
 548     void* flag=NULL;
 549     flag=(void*)LOCKXCHG((unsigned INTPTR*)&(S->val), (unsigned INTPTR)flag);
 550     if (flag!=NULL) {
 551       return READY;
 552     } else {
 553       return NOTREADY;//<- means that some other dispatcher got this one...so need to do accounting correctly
 554     }
 555   } else {
 556     Q->tail=(MemoryQueueItem*)S;
 557     return NOTREADY;
 558   }
 559 }
 560
 561
 562 void RETIRERENTRY(MemoryQueue* Q, REntry * r) {
 563   if (isFineWrite(r)||isFineRead(r)) {
 564     RETIREHASHTABLE(Q, r);
 565   } else if (isCoarse(r)) {
 566     RETIREVECTOR(Q, r);
 567   } else if (isSCC(r)) {
 568     RETIRESCC(Q, r);
 569   }
 570 }
 571
 572 RETIRESCC(MemoryQueue *Q, REntry *r) {
 573   SCC* s=r->scc;
 574   s->item.total=0;//don't need atomicdec
 575   RESOLVECHAIN(Q);
 576 }
 577
 578
 579 RETIREHASHTABLE(MemoryQueue *q, REntry *r) {
 580   Hashtable *T=r->hashtable;
 581   BinItem *b=r->binitem;
 582   RETIREBIN(T,r,b);
 583   atomic_dec(&T->item.total);
 584   if (T->item.next!=NULL && T->item.total==0) {
 585     RESOLVECHAIN(q);
 586   }
 587 }
 588
 589 RETIREBIN(Hashtable *T, REntry *r, BinItem *b) {
 590   //  int key=generateKey((unsigned int)(unsigned INTPTR)*(r->pointer));
 591   int key=generateKey(r->oid);
 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(r->oid);
 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(r->oid);
 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(r->oid);
 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(r->oid);
 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         //now, address is resolved. update OID field.
 944         struct ___Object___ * obj=(struct ___Object___*)((unsigned INTPTR)*rentry->pointer);
 945         rentry->oid=obj->oid;
 946
 947         //check if rentry is buffer mode
 948         if(rentry->isBufMode==TRUE){
 949           if(currentSESE==0){
 950             queue=rentry->queue;
 951             INITIALIZEBUF(queue);
 952             currentSESE=(INTPTR)rentry;
 953             ADDRENTRYTOBUF(queue,rentry);
 954           } else if(currentSESE==(INTPTR)rentry){
 955             ADDRENTRYTOBUF(queue,rentry);
 956           } else if(currentSESE!=(INTPTR)rentry){
 957             RESOLVEBUFFORHASHTABLE(queue,table,(SESEcommon*)rentry->seseRec);
 958             currentSESE=(INTPTR)rentry;
 959             INITIALIZEBUF(queue);
 960             ADDRENTRYTOBUF(rentry->queue,rentry);
 961           }
 962         }else{
 963           if(currentSESE!=0){
 964             //previous SESE has buf mode, need to invoke resolve buffer
 965             RESOLVEBUFFORHASHTABLE(queue,table,(SESEcommon*)rentry->seseRec);
 966             currentSESE=0;
 967           }
 968           //normal mode
 969           if(ADDTABLEITEM(table, rentry, FALSE)==READY){
 970             resolveDependencies(rentry);
 971           }
 972         }
 973       }else{
 974         table->unresolvedQueue=NULL; // set hashtable as normal-mode.
 975         break;
 976       }
 977     }while(TRUE);
 978   }else{
 979     // resolved rentry is not head of queue
 980     table->unresolvedQueue=val;//released lock;
 981   }
 982 }
 983
 984 void rehashMemoryQueue(SESEcommon_p seseParent){
 985 #if 0
 986   // update memory queue
 987   int i,binidx;
 988   for(i=0; i<seseParent->numMemoryQueue; i++){
 989     MemoryQueue *memoryQueue=seseParent->memoryQueueArray[i];
 990     MemoryQueueItem *memoryItem=memoryQueue->head;
 991     MemoryQueueItem *prevItem=NULL;
 992     while(memoryItem!=NULL){
 993       if(memoryItem->type==HASHTABLE){
 994         //do re-hash!
 995         Hashtable* ht=(Hashtable*)memoryItem;
 996         Hashtable* newht=createHashtable();
 997         int binidx;
 998         for(binidx=0; binidx<NUMBINS; binidx++){
 999           BinElement *bin=ht->array[binidx];
1000           BinItem *binItem=bin->head;
1001           //traverse over the list of each bin
1002           while(binItem!=NULL){
1003             if(binItem->type==READBIN){
1004               ReadBinItem* readBinItem=(ReadBinItem*)binItem;
1005               int ridx;
1006               for(ridx=0; ridx<readBinItem->index; ridx++){
1007                 REntry *rentry=readBinItem->array[ridx];
1008                 int newkey=generateKey((unsigned int)(unsigned INTPTR)*(rentry->pointer));
1009                 int status=rentry->binitem->status;
1010                 ADDTABLEITEM(newht,rentry,TRUE);
1011                 rentry->binitem->status=status; // update bin status as before rehash
1012               }
1013             }else{//write bin
1014               REntry *rentry=((WriteBinItem*)binItem)->val;
1015               int newkey=generateKey((unsigned int)(unsigned INTPTR)*(rentry->pointer));
1016               int status=rentry->binitem->status;
1017               ADDTABLEITEM(newht,rentry,TRUE);
1018               int newstatus=rentry->binitem->status;
1019               //printf("[%d]old status=%d new status=%d\n",i,status,newstatus);
1020               rentry->binitem->status=status; // update bin status as before rehash
1021             }
1022             binItem=binItem->next;
1023           }
1024         }
1025         newht->item.status=ht->item.status; // update hashtable status
1026         if(prevItem!=NULL){
1027           prevItem->next=(MemoryQueueItem*)newht;
1028         }else{
1029           if(memoryQueue->head==memoryQueue->tail){
1030             memoryQueue->tail=(MemoryQueueItem*)newht;
1031           }
1032           memoryQueue->head=(MemoryQueueItem*)newht;
1033         }
1034         newht->item.next=ht->item.next;
1035       }
1036       prevItem=memoryItem;
1037       memoryItem=memoryItem->next;
1038     }
1039   }
1040 #endif
1041 }