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