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