Robust/src/Runtime/garbage.c

   1 #include "garbage.h"
   2 #include "runtime.h"
   3 #include "structdefs.h"
   4 #include "Queue.h"
   5 #include "SimpleHash.h"
   6 #include "chash.h"
   7 #include "GenericHashtable.h"
   8 #include <string.h>
   9 #if defined(THREADS) || defined(DSTM) || defined(STM)
  10 #include "thread.h"
  11 #endif
  12 #ifdef MLP
  13 #ifdef SQUEUE
  14 #include "squeue.h"
  15 #else
  16 #include "deque.h"
  17 #endif
  18 #include "workschedule.h"
  19 extern volatile int    numWorkSchedWorkers;
  20 extern deque* deques;
  21 #endif
  22
  23 #ifdef DMALLOC
  24 #include "dmalloc.h"
  25 #endif
  26 #ifdef DSTM
  27 #ifdef RECOVERY
  28 #include <DSTM/interface_recovery/dstm.h>
  29 #else
  30 #include <DSTM/interface/dstm.h>
  31 #endif
  32 #endif
  33 #ifdef STM
  34 #include "tm.h"
  35 #endif
  36 #ifdef DELAYCOMP
  37 #include "delaycomp.h"
  38 #endif
  39
  40
  41 #define NUMPTRS 100
  42
  43 #ifndef INITIALHEAPSIZE_MB
  44 #define INITIALHEAPSIZE_MB (256)
  45 #endif
  46
  47 #define INITIALHEAPSIZE INITIALHEAPSIZE_MB*1024*1024L
  48 #define GCPOINT(x) ((INTPTR)((x)*0.99))
  49 /* This define takes in how full the heap is initially and returns a new heap size to use */
  50 #define HEAPSIZE(x,y) ((INTPTR)(x+y))*2
  51
  52 #ifdef TASK
  53 extern struct genhashtable * activetasks;
  54 #ifndef MULTICORE
  55 extern struct parameterwrapper * objectqueues[NUMCLASSES];
  56 #endif
  57 extern struct genhashtable * failedtasks;
  58 extern struct taskparamdescriptor *currtpd;
  59 extern struct ctable *forward;
  60 extern struct ctable *reverse;
  61 extern struct RuntimeHash *fdtoobject;
  62 #endif
  63
  64 #ifdef GARBAGESTATS
  65 #define MAXSTATS 500
  66 long garbagearray[MAXSTATS];
  67 #endif
  68
  69 #if defined(THREADS) || defined(DSTM) || defined(STM)||defined(MLP)
  70 int needtocollect=0;
  71 struct listitem * list=NULL;
  72 int listcount=0;
  73 #ifndef MAC
  74 __thread struct listitem litem;
  75 #endif
  76 #endif
  77
  78 #ifdef MLP
  79 __thread SESEcommon* seseCommon;
  80 #endif
  81
  82 //Need to check if pointers are transaction pointers
  83 //this also catches the special flag value of 1 for local copies
  84 #ifdef DSTM
  85 #define ENQUEUE(orig, dst) \
  86   if ((!(((unsigned int)orig)&0x1))) { \
  87     if (orig>=curr_heapbase&&orig<curr_heaptop) { \
  88       void *copy; \
  89       if (gc_createcopy(orig,&copy)) \
  90         enqueue(copy);\
  91       dst=copy; \
  92     } \
  93   }
  94 #elif defined(STM)
  95 #define ENQUEUE(orig, dst) \
  96   if (orig>=curr_heapbase&&orig<curr_heaptop) { \
  97     void *copy; \
  98     if (gc_createcopy(orig,&copy)) \
  99       enqueue(copy);\
 100     dst=copy; \
 101   }
 102 #define SENQUEUE(orig, dst) \
 103   { \
 104     void *copy; \
 105     if (gc_createcopy(orig,&copy)) \
 106       enqueue(copy);\
 107     dst=copy; \
 108   }
 109 #elif defined(FASTCHECK)
 110 #define ENQUEUE(orig, dst) \
 111   if (((unsigned int)orig)!=1) { \
 112     void *copy; \
 113     if (gc_createcopy(orig,&copy)) \
 114       enqueue(copy);\
 115     dst=copy; }
 116 #else
 117 #define ENQUEUE(orig, dst) \
 118   if (orig>=curr_heapbase&&orig<curr_heaptop) { \
 119      void *copy; \
 120      if (gc_createcopy(orig,&copy)) \
 121          enqueue(copy); \
 122      dst=copy; \
 123   }
 124 #endif
 125
 126
 127 struct pointerblock {
 128   void * ptrs[NUMPTRS];
 129   struct pointerblock *next;
 130 };
 131
 132 void * curr_heapbase=0;
 133 void * curr_heapptr=0;
 134 void * curr_heapgcpoint=0;
 135 void * curr_heaptop=0;
 136
 137 void * to_heapbase=0;
 138 void * to_heapptr=0;
 139 void * to_heaptop=0;
 140 long lastgcsize=0;
 141
 142
 143 struct pointerblock *head=NULL;
 144 int headindex=0;
 145 struct pointerblock *tail=NULL;
 146 int tailindex=0;
 147 struct pointerblock *spare=NULL;
 148
 149 void enqueue(void *ptr) {
 150   if (headindex==NUMPTRS) {
 151     struct pointerblock * tmp;
 152     if (spare!=NULL) {
 153       tmp=spare;
 154       spare=NULL;
 155     } else      tmp=malloc(sizeof(struct pointerblock));
 156     head->next=tmp;
 157     head=tmp;
 158     headindex=0;
 159   }
 160   head->ptrs[headindex++]=ptr;
 161 }
 162
 163 void * dequeue() {
 164   if (tailindex==NUMPTRS) {
 165     struct pointerblock *tmp=tail;
 166     tail=tail->next;
 167     tailindex=0;
 168     if (spare!=NULL)
 169       free(tmp);
 170     else
 171       spare=tmp;
 172   }
 173   return tail->ptrs[tailindex++];
 174 }
 175
 176 #ifdef STM
 177 void fixobjlist(struct objlist * ptr) {
 178   while(ptr!=NULL) {
 179     int i;
 180     for(i=0;i<ptr->offset;i++) {
 181       SENQUEUE(ptr->objs[i], ptr->objs[i]);
 182     }
 183     ptr=ptr->next;
 184   }
 185 }
 186
 187 void fixtable(chashlistnode_t ** tc_table, chashlistnode_t **tc_list, cliststruct_t **cstr, unsigned int tc_size) {
 188   unsigned int mask=(tc_size<<4)-1;
 189   chashlistnode_t *node=calloc(tc_size, sizeof(chashlistnode_t));
 190   chashlistnode_t *ptr=*tc_table;
 191   chashlistnode_t *curr;
 192   unsigned int i;
 193   unsigned int index;
 194   int isfirst;
 195   chashlistnode_t *newlist=NULL;
 196   for(i=0;i<tc_size;i++) {
 197     curr=&ptr[i];
 198     isfirst=1;
 199     do {                      //Inner loop to go through linked lists
 200       void * key;
 201       chashlistnode_t *tmp,*next;
 202
 203       if ((key=(void *)curr->key) == 0) {             //Exit inner loop if there the first element is 0
 204         break;                  //key = val =0 for element if not present within the hash table
 205       }
 206       SENQUEUE(key, key);
 207       if (curr->val>=curr_heapbase&&curr->val<curr_heaptop) {
 208         SENQUEUE(curr->val, curr->val);
 209       } else {
 210         //rewrite transaction cache entry
 211         void *vptr=curr->val;
 212         int type=((int *)vptr)[0];
 213         unsigned INTPTR *pointer=pointerarray[type];
 214         if (pointer==0) {
 215           //array of primitives - do nothing
 216           struct ArrayObject *ao=(struct ArrayObject *) vptr;
 217           SENQUEUE((void *)ao->___objlocation___, *((void **)&ao->___objlocation___));
 218         } else if (((INTPTR)pointer)==1) {
 219           //array of pointers
 220           struct ArrayObject *ao=(struct ArrayObject *) vptr;
 221           int length=ao->___length___;
 222           int i;
 223           SENQUEUE((void *)ao->___objlocation___, *((void **)&ao->___objlocation___));
 224 #ifdef STMARRAY
 225           int lowindex=ao->lowindex;
 226           int highindex=ao->highindex;
 227           int j;
 228           for(j=lowindex; j<=highindex; j++) {
 229             unsigned int lockval;
 230             GETLOCKVAL(lockval, ao, j);
 231             if (lockval!=STMNONE) {
 232               int lowi=(j<<INDEXSHIFT)/sizeof(void *);
 233               int highi=lowi+(INDEXLENGTH/sizeof(void *));
 234               for(i=lowi; i<highi;i++) {
 235 #else
 236               for(i=0; i<length; i++) {
 237 #endif
 238                 void *objptr=((void **)(((char *)&ao->___length___)+sizeof(int)))[i];
 239                 SENQUEUE(objptr, ((void **)(((char *)&ao->___length___)+sizeof(int)))[i]);
 240               }
 241 #ifdef STMARRAY
 242             }
 243           }
 244 #endif
 245           {
 246             pointer=pointerarray[OBJECTTYPE];
 247             //handle object class
 248             INTPTR size=pointer[0];
 249             int i;
 250             for(i=1; i<=size; i++) {
 251               unsigned int offset=pointer[i];
 252               void * objptr=*((void **)(((char *)vptr)+offset));
 253               SENQUEUE(objptr, *((void **)(((char *)vptr)+offset)));
 254             }
 255           }
 256         } else {
 257           INTPTR size=pointer[0];
 258           int i;
 259           for(i=1; i<=size; i++) {
 260             unsigned int offset=pointer[i];
 261             void * objptr=*((void **)(((char *)vptr)+offset));
 262             SENQUEUE(objptr, *((void **)(((char *)vptr)+offset)));
 263           }
 264         }
 265       }
 266
 267       next = curr->next;
 268       index = (((unsigned INTPTR)key) & mask) >>4;
 269
 270       curr->key=key;
 271       tmp=&node[index];
 272       // Insert into the new table
 273       if(tmp->key == 0) {
 274         tmp->key = curr->key;
 275         tmp->val = curr->val;
 276         tmp->lnext=newlist;
 277         newlist=tmp;
 278       } else if (isfirst) {
 279         chashlistnode_t *newnode;
 280         if ((*cstr)->num<NUMCLIST) {
 281           newnode=&(*cstr)->array[(*cstr)->num];
 282           (*cstr)->num++;
 283         } else {
 284           //get new list
 285           cliststruct_t *tcl=calloc(1,sizeof(cliststruct_t));
 286           tcl->next=*cstr;
 287           *cstr=tcl;
 288           newnode=&tcl->array[0];
 289           tcl->num=1;
 290         }
 291         newnode->key = curr->key;
 292         newnode->val = curr->val;
 293         newnode->next = tmp->next;
 294         newnode->lnext=newlist;
 295         newlist=newnode;
 296         tmp->next=newnode;
 297       } else {
 298         curr->lnext=newlist;
 299         newlist=curr;
 300         curr->next=tmp->next;
 301         tmp->next=curr;
 302       }
 303       isfirst = 0;
 304       curr = next;
 305     } while(curr!=NULL);
 306   }
 307   free(ptr);
 308   (*tc_table)=node;
 309   (*tc_list)=newlist;
 310 }
 311 #endif
 312
 313 int moreItems() {
 314   if ((head==tail)&&(tailindex==headindex))
 315     return 0;
 316   return 1;
 317 }
 318
 319 #ifdef TASK
 320 struct pointerblock *taghead=NULL;
 321 int tagindex=0;
 322
 323 void enqueuetag(struct ___TagDescriptor___ *ptr) {
 324   if (tagindex==NUMPTRS) {
 325     struct pointerblock * tmp=malloc(sizeof(struct pointerblock));
 326     tmp->next=taghead;
 327     taghead=tmp;
 328     tagindex=0;
 329   }
 330   taghead->ptrs[tagindex++]=ptr;
 331 }
 332 #endif
 333
 334 #if defined(STM)||defined(THREADS)||defined(MLP)
 335 __thread char * memorybase=NULL;
 336 __thread char * memorytop=NULL;
 337 #endif
 338
 339
 340 void collect(struct garbagelist * stackptr) {
 341 #if defined(THREADS)||defined(DSTM)||defined(STM)||defined(MLP)
 342   needtocollect=1;
 343   pthread_mutex_lock(&gclistlock);
 344   while(1) {
 345     if ((listcount+1)==threadcount) {
 346       break; /* Have all other threads stopped */
 347     }
 348     pthread_cond_wait(&gccond, &gclistlock);
 349   }
 350 #endif
 351 #ifdef DELAYCOMP
 352   ptrstack.prev=stackptr;
 353   stackptr=(struct garbagelist *) &ptrstack;
 354 #if defined(STMARRAY)&&!defined(DUALVIEW)
 355   arraystack.prev=stackptr;
 356   stackptr=(struct garbagelist *) &arraystack;
 357 #endif
 358 #endif
 359
 360 #ifdef GARBAGESTATS
 361   {
 362     int i;
 363     for(i=0;i<MAXSTATS;i++)
 364       garbagearray[i]=0;
 365   }
 366 #endif
 367
 368   if (head==NULL) {
 369     headindex=0;
 370     tailindex=0;
 371     head=tail=malloc(sizeof(struct pointerblock));
 372   }
 373
 374 #ifdef TASK
 375   if (taghead==NULL) {
 376     tagindex=0;
 377     taghead=malloc(sizeof(struct pointerblock));
 378     taghead->next=NULL;
 379   }
 380 #endif
 381
 382 #ifdef STM
 383   if (c_table!=NULL) {
 384     fixtable(&c_table, &c_list, &c_structs, c_size);
 385     fixobjlist(newobjs);
 386 #ifdef STMSTATS
 387     fixobjlist(lockedobjs);
 388 #endif
 389   }
 390 #endif
 391 #if defined(STM)||defined(THREADS)||defined(MLP)
 392   memorybase=NULL;
 393 #endif
 394
 395   /* Check current stack */
 396 #if defined(THREADS)||defined(DSTM)||defined(STM)||defined(MLP)
 397   {
 398     struct listitem *listptr=list;
 399     while(1) {
 400 #endif
 401
 402   while(stackptr!=NULL) {
 403     int i;
 404     for(i=0; i<stackptr->size; i++) {
 405       void * orig=stackptr->array[i];
 406       ENQUEUE(orig, stackptr->array[i]);
 407     }
 408     stackptr=stackptr->next;
 409   }
 410 #if defined(THREADS)||defined(DSTM)||defined(STM)||defined(MLP)
 411   /* Go to next thread */
 412 #ifndef MAC
 413   //skip over us
 414   if (listptr==&litem) {
 415 #ifdef MLP
 416     // update forward list & memory queue for the current SESE
 417     updateForwardList(&((SESEcommon*)listptr->seseCommon)->forwardList,FALSE);
 418     updateMemoryQueue((SESEcommon*)(listptr->seseCommon));
 419 #endif
 420     listptr=listptr->next;
 421   }
 422 #else
 423  {
 424   struct listitem *litem=pthread_getspecific(litemkey);
 425   if (listptr==litem) {
 426     listptr=listptr->next;
 427   }
 428  }
 429 #endif
 430
 431   if (listptr!=NULL) {
 432 #ifdef THREADS
 433     void * orig=listptr->locklist;
 434     ENQUEUE(orig, listptr->locklist);
 435 #endif
 436 #ifdef STM
 437     if ((*listptr->tc_table)!=NULL) {
 438       fixtable(listptr->tc_table, listptr->tc_list, listptr->tc_structs, listptr->tc_size);
 439       fixobjlist(listptr->objlist);
 440 #ifdef STMSTATS
 441       fixobjlist(listptr->lockedlist);
 442 #endif
 443     }
 444 #endif
 445 #if defined(STM)||defined(THREADS)||defined(MLP)
 446     *(listptr->base)=NULL;
 447 #endif
 448 #ifdef MLP
 449     // update forward list & memory queue for all running SESEs.
 450     if (listptr->seseCommon!=NULL) {
 451       updateForwardList(&((SESEcommon*)listptr->seseCommon)->forwardList,FALSE);
 452       updateMemoryQueue((SESEcommon*)(listptr->seseCommon));
 453     }
 454 #endif
 455     stackptr=listptr->stackptr;
 456     listptr=listptr->next;
 457   } else
 458     break;
 459 }
 460 }
 461 #endif
 462
 463 #ifdef FASTCHECK
 464   ENQUEUE(___fcrevert___, ___fcrevert___);
 465 #endif
 466
 467 #if defined(THREADS)||defined(DSTM)||defined(STM)||defined(MLP)
 468   {
 469     int i;
 470     stackptr=(struct garbagelist *)global_defs_p;
 471     for(i=0; i<stackptr->size; i++) {
 472       void * orig=stackptr->array[i];
 473       ENQUEUE(orig, stackptr->array[i]);
 474     }
 475   }
 476 #endif
 477
 478 #ifdef TASK
 479   {
 480     /* Update objectsets */
 481     int i;
 482     for(i=0; i<NUMCLASSES; i++) {
 483 #if !defined(MULTICORE)
 484       struct parameterwrapper * p=objectqueues[i];
 485       while(p!=NULL) {
 486         struct ObjectHash * set=p->objectset;
 487         struct ObjectNode * ptr=set->listhead;
 488         while(ptr!=NULL) {
 489           void *orig=(void *)ptr->key;
 490           ENQUEUE(orig, *((void **)(&ptr->key)));
 491           ptr=ptr->lnext;
 492         }
 493         ObjectHashrehash(set); /* Rehash the table */
 494         p=p->next;
 495       }
 496 #endif
 497     }
 498   }
 499
 500 #ifndef FASTCHECK
 501   if (forward!=NULL) {
 502     struct cnode * ptr=forward->listhead;
 503     while(ptr!=NULL) {
 504       void * orig=(void *)ptr->key;
 505       ENQUEUE(orig, *((void **)(&ptr->key)));
 506       ptr=ptr->lnext;
 507     }
 508     crehash(forward); /* Rehash the table */
 509   }
 510
 511   if (reverse!=NULL) {
 512     struct cnode * ptr=reverse->listhead;
 513     while(ptr!=NULL) {
 514       void *orig=(void *)ptr->val;
 515       ENQUEUE(orig, *((void**)(&ptr->val)));
 516       ptr=ptr->lnext;
 517     }
 518   }
 519 #endif
 520
 521   {
 522     struct RuntimeNode * ptr=fdtoobject->listhead;
 523     while(ptr!=NULL) {
 524       void *orig=(void *)ptr->data;
 525       ENQUEUE(orig, *((void**)(&ptr->data)));
 526       ptr=ptr->lnext;
 527     }
 528   }
 529
 530   {
 531     /* Update current task descriptor */
 532     int i;
 533     for(i=0; i<currtpd->numParameters; i++) {
 534       void *orig=currtpd->parameterArray[i];
 535       ENQUEUE(orig, currtpd->parameterArray[i]);
 536     }
 537
 538   }
 539
 540   /* Update active tasks */
 541   {
 542     struct genpointerlist * ptr=activetasks->list;
 543     while(ptr!=NULL) {
 544       struct taskparamdescriptor *tpd=ptr->src;
 545       int i;
 546       for(i=0; i<tpd->numParameters; i++) {
 547         void * orig=tpd->parameterArray[i];
 548         ENQUEUE(orig, tpd->parameterArray[i]);
 549       }
 550       ptr=ptr->inext;
 551     }
 552     genrehash(activetasks);
 553   }
 554
 555   /* Update failed tasks */
 556   {
 557     struct genpointerlist * ptr=failedtasks->list;
 558     while(ptr!=NULL) {
 559       struct taskparamdescriptor *tpd=ptr->src;
 560       int i;
 561       for(i=0; i<tpd->numParameters; i++) {
 562         void * orig=tpd->parameterArray[i];
 563         ENQUEUE(orig, tpd->parameterArray[i]);
 564       }
 565       ptr=ptr->inext;
 566     }
 567     genrehash(failedtasks);
 568   }
 569 #endif
 570
 571 #ifdef MLP
 572 #ifdef SQUEUE
 573   {
 574     int        i;
 575     deque*     dq;
 576     dequeItem *di;
 577     int        j;
 578
 579     // goes over ready-to-run SESEs
 580     for( i = 0; i < numWorkSchedWorkers; ++i ) {
 581       dq = &(deques[i]);
 582
 583       di=dq->head;
 584
 585       do {
 586         // check all the relevant indices of this
 587         // node in the deque, noting if we are in
 588         // the top/bottom node which can be partially
 589         // full
 590
 591           // WHAT?
 592           //SESEcommon* common = (SESEcommon*) n->itsDataArr[j];
 593           //if(common==seseCommon){
 594           // skip the current running SESE
 595           //  continue;
 596           //}
 597         di=(dequeItem *) EXTRACTPTR((INTPTR)di);
 598         SESEcommon* seseRec = (SESEcommon*) di->work;
 599         if (seseRec!=NULL) {
 600           struct garbagelist* gl     = (struct garbagelist*) &(seseRec[1]);
 601           struct garbagelist* glroot = gl;
 602
 603           updateAscendantSESE( seseRec );
 604
 605           while( gl != NULL ) {
 606             int k;
 607             for( k = 0; k < gl->size; k++ ) {
 608               void* orig = gl->array[k];
 609               ENQUEUE( orig, gl->array[k] );
 610             }
 611             gl = gl->next;
 612           }
 613         }
 614         // we only have to move across the nodes
 615         // of the deque if the top and bottom are
 616         // not the same already
 617           di=di->next;
 618       } while( di !=NULL) ;
 619     }
 620   }
 621 #else
 622   {
 623     int        i;
 624     deque*     dq;
 625     dequeNode* botNode;
 626     int        botIndx;
 627     dequeNode* topNode;
 628     int        topIndx;
 629     dequeNode* n;
 630     int        j;
 631     int        jLo;
 632     int        jHi;
 633
 634     // goes over ready-to-run SESEs
 635     for( i = 0; i < numWorkSchedWorkers; ++i ) {
 636       dq = &(deques[i]);
 637
 638       botNode = dqDecodePtr( dq->bottom );
 639       botIndx = dqDecodeIdx( dq->bottom );
 640
 641       topNode = dqDecodePtr( dq->top );
 642       topIndx = dqDecodeIdx( dq->top );
 643
 644
 645       n = botNode;
 646       do {
 647         // check all the relevant indices of this
 648         // node in the deque, noting if we are in
 649         // the top/bottom node which can be partially
 650         // full
 651         if( n == botNode ) { jLo = botIndx; } else { jLo = 0; }
 652         if( n == topNode ) { jHi = topIndx; } else { jHi = DQNODE_ARRAYSIZE; }
 653
 654         for( j = jLo; j < jHi; ++j ) {
 655
 656           // WHAT?
 657           //SESEcommon* common = (SESEcommon*) n->itsDataArr[j];
 658           //if(common==seseCommon){
 659           //  continue;
 660           //}
 661
 662           SESEcommon* seseRec = (SESEcommon*) n->itsDataArr[j];
 663
 664           struct garbagelist* gl     = (struct garbagelist*) &(seseRec[1]);
 665           struct garbagelist* glroot = gl;
 666
 667           updateAscendantSESE( seseRec );
 668
 669           while( gl != NULL ) {
 670             int k;
 671             for( k = 0; k < gl->size; k++ ) {
 672               void* orig = gl->array[k];
 673               ENQUEUE( orig, gl->array[k] );
 674             }
 675             gl = gl->next;
 676           }
 677         }
 678
 679         // we only have to move across the nodes
 680         // of the deque if the top and bottom are
 681         // not the same already
 682         if( botNode != topNode ) {
 683           n = n->next;
 684         }
 685       } while( n != topNode );
 686     }
 687   }
 688 #endif
 689 #endif
 690
 691
 692   while(moreItems()) {
 693     void * ptr=dequeue();
 694     void *cpy=ptr;
 695     int type=((int *)cpy)[0];
 696     unsigned INTPTR * pointer;
 697 #ifdef TASK
 698     if(type==TAGTYPE) {
 699       /* Enqueue Tag */
 700       /* Nothing is inside */
 701       enqueuetag(ptr);
 702       continue;
 703     }
 704 #endif
 705     pointer=pointerarray[type];
 706     if (pointer==0) {
 707       /* Array of primitives */
 708       /* Do nothing */
 709 #if defined(DSTM)||defined(FASTCHECK)
 710       struct ArrayObject *ao=(struct ArrayObject *) ptr;
 711       struct ArrayObject *ao_cpy=(struct ArrayObject *) cpy;
 712       ENQUEUE((void *)ao->___nextobject___, *((void **)&ao_cpy->___nextobject___));
 713       ENQUEUE((void *)ao->___localcopy___, *((void **)&ao_cpy->___localcopy___));
 714 #endif
 715 #if defined(STM)
 716       struct ArrayObject *ao=(struct ArrayObject *) ptr;
 717       struct ArrayObject *ao_cpy=(struct ArrayObject *) cpy;
 718       SENQUEUE((void *)ao->___objlocation___, *((void **)&ao_cpy->___objlocation___));
 719 #endif
 720     } else if (((INTPTR)pointer)==1) {
 721       /* Array of pointers */
 722       struct ArrayObject *ao=(struct ArrayObject *) ptr;
 723       struct ArrayObject *ao_cpy=(struct ArrayObject *) cpy;
 724 #if (defined(DSTM)||defined(FASTCHECK))
 725       ENQUEUE((void *)ao->___nextobject___, *((void **)&ao_cpy->___nextobject___));
 726       ENQUEUE((void *)ao->___localcopy___, *((void **)&ao_cpy->___localcopy___));
 727 #endif
 728 #if defined(STM)
 729       SENQUEUE((void *)ao->___objlocation___, *((void **)&ao_cpy->___objlocation___));
 730 #endif
 731       int length=ao->___length___;
 732       int i;
 733       for(i=0; i<length; i++) {
 734         void *objptr=((void **)(((char *)&ao->___length___)+sizeof(int)))[i];
 735         ENQUEUE(objptr, ((void **)(((char *)&ao_cpy->___length___)+sizeof(int)))[i]);
 736       }
 737     } else {
 738       INTPTR size=pointer[0];
 739       int i;
 740       for(i=1; i<=size; i++) {
 741         unsigned int offset=pointer[i];
 742         void * objptr=*((void **)(((char *)ptr)+offset));
 743         ENQUEUE(objptr, *((void **)(((char *)cpy)+offset)));
 744       }
 745     }
 746   }
 747 #ifdef TASK
 748   fixtags();
 749 #endif
 750
 751 #if defined(THREADS)||defined(DSTM)||defined(STM)||defined(MLP)
 752   needtocollect=0;
 753   pthread_mutex_unlock(&gclistlock);
 754 #endif
 755 }
 756
 757 #ifdef TASK
 758 /* Fix up the references from tags.  This can't be done earlier,
 759    because we don't want tags to keep objects alive */
 760 void fixtags() {
 761   while(taghead!=NULL) {
 762     int i;
 763     struct pointerblock *tmp=taghead->next;
 764     for(i=0; i<tagindex; i++) {
 765       struct ___TagDescriptor___ *tagd=taghead->ptrs[i];
 766       struct ___Object___ *obj=tagd->flagptr;
 767       struct ___TagDescriptor___ *copy=((struct ___TagDescriptor___**)tagd)[1];
 768       if (obj==NULL) {
 769         /* Zero object case */
 770       } else if (obj->type==-1) {
 771         /* Single object case */
 772         copy->flagptr=((struct ___Object___**)obj)[1];
 773       } else if (obj->type==OBJECTARRAYTYPE) {
 774         /* Array case */
 775         struct ArrayObject *ao=(struct ArrayObject *) obj;
 776         int livecount=0;
 777         int j;
 778         int k=0;
 779         struct ArrayObject *aonew;
 780
 781         /* Count live objects */
 782         for(j=0; j<ao->___cachedCode___; j++) {
 783           struct ___Object___ * tobj=ARRAYGET(ao, struct ___Object___ *, j);
 784           if (tobj->type==-1)
 785             livecount++;
 786         }
 787
 788         livecount=((livecount-1)/OBJECTARRAYINTERVAL+1)*OBJECTARRAYINTERVAL;
 789         aonew=(struct ArrayObject *) tomalloc(sizeof(struct ArrayObject)+sizeof(struct ___Object___*)*livecount);
 790         memcpy(aonew, ao, sizeof(struct ArrayObject));
 791         aonew->type=OBJECTARRAYTYPE;
 792         aonew->___length___=livecount;
 793         copy->flagptr=aonew;
 794         for(j=0; j<ao->___cachedCode___; j++) {
 795           struct ___Object___ * tobj=ARRAYGET(ao, struct ___Object___ *, j);
 796           if (tobj->type==-1) {
 797             struct ___Object___ * tobjcpy=((struct ___Object___**)tobj)[1];
 798             ARRAYSET(aonew, struct ___Object___*, k++,tobjcpy);
 799           }
 800         }
 801         aonew->___cachedCode___=k;
 802         for(; k<livecount; k++) {
 803           ARRAYSET(aonew, struct ___Object___*, k, NULL);
 804         }
 805       } else {
 806         /* No object live anymore */
 807         copy->flagptr=NULL;
 808       }
 809     }
 810     free(taghead);
 811     taghead=tmp;
 812     tagindex=NUMPTRS;
 813   }
 814 }
 815 #endif
 816
 817 void * tomalloc(int size) {
 818   void * ptr=to_heapptr;
 819   if ((size&7)!=0)
 820     size+=(8-(size%8));
 821   to_heapptr+=size;
 822   return ptr;
 823 }
 824
 825 #if defined(THREADS)||defined(DSTM)||defined(STM)||defined(MLP)
 826 void checkcollect(void * ptr) {
 827   stopforgc((struct garbagelist *)ptr);
 828   restartaftergc();
 829 }
 830
 831 #ifdef DSTM
 832 void checkcollect2(void * ptr) {
 833   int ptrarray[]={1, (int)ptr, (int) revertlist};
 834   stopforgc((struct garbagelist *)ptrarray);
 835   restartaftergc();
 836   revertlist=(struct ___Object___*)ptrarray[2];
 837 }
 838 #endif
 839
 840 void stopforgc(struct garbagelist * ptr) {
 841 #ifdef DELAYCOMP
 842   //just append us to the list
 843   ptrstack.prev=ptr;
 844   ptr=(struct garbagelist *) &ptrstack;
 845 #if defined(STMARRAY)&&!defined(DUALVIEW)
 846   arraystack.prev=ptr;
 847   ptr=(struct garbagelist *) &arraystack;
 848 #endif
 849 #endif
 850 #ifndef MAC
 851   litem.stackptr=ptr;
 852 #ifdef THREADS
 853   litem.locklist=pthread_getspecific(threadlocks);
 854 #endif
 855 #if defined(STM)||defined(THREADS)||defined(MLP)
 856   litem.base=&memorybase;
 857 #endif
 858 #ifdef STM
 859   litem.tc_size=c_size;
 860   litem.tc_table=&c_table;
 861   litem.tc_list=&c_list;
 862   litem.tc_structs=&c_structs;
 863   litem.objlist=newobjs;
 864 #ifdef STMSTATS
 865   litem.lockedlist=lockedobjs;
 866 #endif
 867 #endif
 868 #else
 869   //handle MAC
 870   struct listitem *litem=pthread_getspecific(litemkey);
 871   litem->stackptr=ptr;
 872 #ifdef THREADS
 873   litem->locklist=pthread_getspecific(threadlocks);
 874 #endif
 875 #endif
 876   pthread_mutex_lock(&gclistlock);
 877   listcount++;
 878   if ((listcount+1)==threadcount) {
 879     //only do wakeup if we are ready to GC
 880     pthread_cond_signal(&gccond);
 881   }
 882   pthread_mutex_unlock(&gclistlock);
 883 }
 884
 885 void restartaftergc() {
 886   if (needtocollect) {
 887     pthread_mutex_lock(&gclock); // Wait for GC
 888     pthread_mutex_unlock(&gclock);
 889   }
 890   pthread_mutex_lock(&gclistlock);
 891   listcount--;
 892   pthread_mutex_unlock(&gclistlock);
 893 #ifdef THREADS
 894 #ifdef MAC
 895   struct listitem *litem=pthread_getspecific(litemkey);
 896   pthread_setspecific(threadlocks,litem->locklist);
 897 #else
 898   pthread_setspecific(threadlocks,litem.locklist);
 899 #endif
 900 #endif
 901 }
 902 #endif
 903
 904 #if defined(STM)||defined(THREADS)||defined(MLP)
 905 #define MEMORYBLOCK 65536
 906 void * helper(struct garbagelist *, int);
 907 void * mygcmalloc(struct garbagelist * stackptr, int size) {
 908   if ((size&7)!=0)
 909     size=(size&~7)+8;
 910   if (memorybase==NULL||size>(memorytop-memorybase)) {
 911     int toallocate=(size>MEMORYBLOCK)?size:MEMORYBLOCK;
 912     memorybase=helper(stackptr, toallocate);
 913     bzero(memorybase, toallocate);
 914     memorytop=memorybase+toallocate;
 915   }
 916   char *retvalue=memorybase;
 917   memorybase+=size;
 918   return retvalue;
 919 }
 920
 921 void * helper(struct garbagelist * stackptr, int size) {
 922 #else
 923 void * mygcmalloc(struct garbagelist * stackptr, int size) {
 924 #endif
 925   void *ptr;
 926 #if defined(THREADS)||defined(DSTM)||defined(STM)||defined(MLP)
 927   while (pthread_mutex_trylock(&gclock)!=0) {
 928     stopforgc(stackptr);
 929     restartaftergc();
 930   }
 931 #endif
 932   ptr=curr_heapptr;
 933   if ((size&7)!=0)
 934     size=(size&~7)+8;
 935   curr_heapptr+=size;
 936   if (curr_heapptr>curr_heapgcpoint||curr_heapptr<curr_heapbase) {
 937     if (curr_heapbase==0) {
 938       /* Need to allocate base heap */
 939       curr_heapbase=malloc(INITIALHEAPSIZE);
 940       if (curr_heapbase==NULL) {
 941         printf("malloc failed.  Garbage colletcor couldn't get enough memory.  Try changing heap size.\n");
 942         exit(-1);
 943       }
 944 #if defined(STM)||defined(THREADS)||defined(MLP)
 945 #else
 946       bzero(curr_heapbase, INITIALHEAPSIZE);
 947 #endif
 948       curr_heaptop=curr_heapbase+INITIALHEAPSIZE;
 949       curr_heapgcpoint=((char *) curr_heapbase)+GCPOINT(INITIALHEAPSIZE);
 950       curr_heapptr=curr_heapbase+size;
 951
 952       to_heapbase=malloc(INITIALHEAPSIZE);
 953       if (to_heapbase==NULL) {
 954         printf("malloc failed.  Garbage collector couldn't get enough memory.  Try changing heap size.\n");
 955         exit(-1);
 956       }
 957
 958       to_heaptop=to_heapbase+INITIALHEAPSIZE;
 959       to_heapptr=to_heapbase;
 960       ptr=curr_heapbase;
 961 #if defined(THREADS)||defined(DSTM)||defined(STM)||defined(MLP)
 962       pthread_mutex_unlock(&gclock);
 963 #endif
 964       return ptr;
 965     }
 966
 967     /* Grow the to heap if necessary */
 968     {
 969       INTPTR curr_heapsize=curr_heaptop-curr_heapbase;
 970       INTPTR to_heapsize=to_heaptop-to_heapbase;
 971       INTPTR last_heapsize=0;
 972       if (lastgcsize>0) {
 973         last_heapsize=HEAPSIZE(lastgcsize, size);
 974         if ((last_heapsize&7)!=0)
 975           last_heapsize+=(8-(last_heapsize%8));
 976       }
 977       if (curr_heapsize>last_heapsize)
 978         last_heapsize=curr_heapsize;
 979       if (last_heapsize>to_heapsize) {
 980         free(to_heapbase);
 981         to_heapbase=malloc(last_heapsize);
 982         if (to_heapbase==NULL) {
 983           printf("Error Allocating enough memory\n");
 984           exit(-1);
 985         }
 986         to_heaptop=to_heapbase+last_heapsize;
 987         to_heapptr=to_heapbase;
 988       }
 989     }
 990
 991     /* Do our collection */
 992     collect(stackptr);
 993
 994     /* Update stat on previous gc size */
 995     lastgcsize=(to_heapptr-to_heapbase)+size;
 996
 997 #ifdef GARBAGESTATS
 998     printf("Garbage collected: Old bytes: %u\n", curr_heapptr-curr_heapbase);
 999     printf("New space: %u\n", to_heapptr-to_heapbase);
1000     printf("Total space: %u\n", to_heaptop-to_heapbase);
1001     {
1002       int i;
1003       for(i=0;i<MAXSTATS;i++) {
1004         if (garbagearray[i]!=0)
1005           printf("Type=%d Size=%u\n", i, garbagearray[i]);
1006       }
1007     }
1008 #endif
1009     /* Flip to/curr heaps */
1010     {
1011       void * tmp=to_heapbase;
1012       to_heapbase=curr_heapbase;
1013       curr_heapbase=tmp;
1014
1015       tmp=to_heaptop;
1016       to_heaptop=curr_heaptop;
1017       curr_heaptop=tmp;
1018
1019       tmp=to_heapptr;
1020       curr_heapptr=to_heapptr+size;
1021       curr_heapgcpoint=((char *) curr_heapbase)+GCPOINT(curr_heaptop-curr_heapbase);
1022       to_heapptr=to_heapbase;
1023
1024       /* Not enough room :(, redo gc */
1025       if (curr_heapptr>curr_heapgcpoint) {
1026 #if defined(THREADS)||defined(DSTM)||defined(STM)||defined(MLP)
1027         pthread_mutex_unlock(&gclock);
1028 #endif
1029         return mygcmalloc(stackptr, size);
1030       }
1031
1032       bzero(tmp, curr_heaptop-tmp);
1033 #if defined(THREADS)||defined(DSTM)||defined(STM)||defined(MLP)
1034       pthread_mutex_unlock(&gclock);
1035 #endif
1036       return tmp;
1037     }
1038   } else {
1039 #if defined(THREADS)||defined(DSTM)||defined(STM)||defined(MLP)
1040     pthread_mutex_unlock(&gclock);
1041 #endif
1042     return ptr;
1043   }
1044 }
1045
1046 int gc_createcopy(void * orig, void ** copy_ptr) {
1047   if (orig==0) {
1048     *copy_ptr=NULL;
1049     return 0;
1050   } else {
1051     int type=((int *)orig)[0];
1052     if (type==-1) {
1053       *copy_ptr=((void **)orig)[1];
1054       return 0;
1055     }
1056     if (type<NUMCLASSES) {
1057       /* We have a normal object */
1058 #ifdef STM
1059       int size=classsize[type]+sizeof(objheader_t);
1060       void *newobj=tomalloc(size);
1061       memcpy(newobj,((char *) orig)-sizeof(objheader_t), size);
1062       newobj=((char *)newobj)+sizeof(objheader_t);
1063 #else
1064       int size=classsize[type];
1065       void *newobj=tomalloc(size);
1066       memcpy(newobj, orig, size);
1067 #endif
1068 #ifdef GARBAGESTATS
1069       garbagearray[type]+=size;
1070 #endif
1071       ((int *)orig)[0]=-1;
1072       ((void **)orig)[1]=newobj;
1073       *copy_ptr=newobj;
1074       return 1;
1075     } else {
1076       /* We have an array */
1077       struct ArrayObject *ao=(struct ArrayObject *)orig;
1078       int elementsize=classsize[type];
1079       int length=ao->___length___;
1080 #ifdef STM
1081 #ifdef STMARRAY
1082       int basesize=length*elementsize;
1083       basesize=(basesize+LOWMASK)&HIGHMASK;
1084       int versionspace=sizeof(int)*2*(basesize>>INDEXSHIFT);
1085       int size=sizeof(struct ArrayObject)+basesize+sizeof(objheader_t)+versionspace;
1086       void *newobj=tomalloc(size);
1087       memcpy(newobj, ((char*)orig)-sizeof(objheader_t)-versionspace, size);
1088       newobj=((char *)newobj)+sizeof(objheader_t)+versionspace;
1089 #else
1090       int size=sizeof(struct ArrayObject)+length*elementsize+sizeof(objheader_t);
1091       void *newobj=tomalloc(size);
1092       memcpy(newobj, ((char*)orig)-sizeof(objheader_t), size);
1093       newobj=((char *)newobj)+sizeof(objheader_t);
1094 #endif
1095 #else
1096       int size=sizeof(struct ArrayObject)+length*elementsize;
1097       void *newobj=tomalloc(size);
1098       memcpy(newobj, orig, size);
1099 #endif
1100 #ifdef GARBAGESTATS
1101       garbagearray[type]+=size;
1102 #endif
1103       ((int *)orig)[0]=-1;
1104       ((void **)orig)[1]=newobj;
1105       *copy_ptr=newobj;
1106       return 1;
1107     }
1108   }
1109 }
1110
1111 #ifdef MLP
1112 updateForwardList(struct Queue *forwardList, int prevUpdate){
1113
1114   struct QueueItem * fqItem=getHead(forwardList);
1115   while(fqItem!=NULL){
1116     SESEcommon* seseRec = (SESEcommon*)(fqItem->objectptr);
1117     struct garbagelist * gl=(struct garbagelist *)&(seseRec[1]);
1118     if(prevUpdate==TRUE){
1119       updateAscendantSESE(seseRec);
1120     }
1121     // do something here
1122     while(gl!=NULL) {
1123       int i;
1124       for(i=0; i<gl->size; i++) {
1125         void * orig=gl->array[i];
1126         ENQUEUE(orig, gl->array[i]);
1127       }
1128       gl=gl->next;
1129     }
1130     // iterate forwarding list of seseRec
1131     struct Queue* fList=&seseRec->forwardList;
1132     updateForwardList(fList,prevUpdate);
1133     fqItem=getNextQueueItem(fqItem);
1134   }
1135
1136 }
1137
1138 updateMemoryQueue(SESEcommon* seseParent){
1139   // update memory queue
1140   int i,binidx;
1141   for(i=0; i<seseParent->numMemoryQueue; i++){
1142     MemoryQueue *memoryQueue=seseParent->memoryQueueArray[i];
1143     MemoryQueueItem *memoryItem=memoryQueue->head;
1144     while(memoryItem!=NULL){
1145       if(memoryItem->type==HASHTABLE){
1146         Hashtable *ht=(Hashtable*)memoryItem;
1147         for(binidx=0; binidx<NUMBINS; binidx++){
1148           BinElement *bin=ht->array[binidx];
1149           BinItem *binItem=bin->head;
1150           while(binItem!=NULL){
1151             if(binItem->type==READBIN){
1152               ReadBinItem* readBinItem=(ReadBinItem*)binItem;
1153               int ridx;
1154               for(ridx=0; ridx<readBinItem->index; ridx++){
1155                 REntry *rentry=readBinItem->array[ridx];
1156                 SESEcommon* seseRec = (SESEcommon*)(rentry->seseRec);
1157                 struct garbagelist * gl= (struct garbagelist *)&(seseRec[1]);
1158                 updateAscendantSESE(seseRec);
1159                 while(gl!=NULL) {
1160                   int i;
1161                   for(i=0; i<gl->size; i++) {
1162                     void * orig=gl->array[i];
1163                     ENQUEUE(orig, gl->array[i]);
1164                   }
1165                   gl=gl->next;
1166                 }
1167               }
1168             }else{ //writebin
1169               REntry *rentry=((WriteBinItem*)binItem)->val;
1170               SESEcommon* seseRec = (SESEcommon*)(rentry->seseRec);
1171               struct garbagelist * gl= (struct garbagelist *)&(seseRec[1]);
1172               updateAscendantSESE(seseRec);
1173               while(gl!=NULL) {
1174                 int i;
1175                 for(i=0; i<gl->size; i++) {
1176                   void * orig=gl->array[i];
1177                   ENQUEUE(orig, gl->array[i]);
1178                 }
1179                 gl=gl->next;
1180               }
1181             }
1182             binItem=binItem->next;
1183           }
1184         }
1185       }else if(memoryItem->type==VECTOR){
1186         Vector *vt=(Vector*)memoryItem;
1187         int idx;
1188         for(idx=0; idx<vt->index; idx++){
1189           REntry *rentry=vt->array[idx];
1190           if(rentry!=NULL){
1191             SESEcommon* seseRec = (SESEcommon*)(rentry->seseRec);
1192             struct garbagelist * gl= (struct garbagelist *)&(seseRec[1]);
1193             updateAscendantSESE(seseRec);
1194             while(gl!=NULL) {
1195               int i;
1196               for(i=0; i<gl->size; i++) {
1197                 void * orig=gl->array[i];
1198                 ENQUEUE(orig, gl->array[i]);
1199               }
1200               gl=gl->next;
1201             }
1202           }
1203         }
1204       }else if(memoryItem->type==SINGLEITEM){
1205         SCC *scc=(SCC*)memoryItem;
1206         REntry *rentry=scc->val;
1207         if(rentry!=NULL){
1208           SESEcommon* seseRec = (SESEcommon*)(rentry->seseRec);
1209           struct garbagelist * gl= (struct garbagelist *)&(seseRec[1]);
1210           updateAscendantSESE(seseRec);
1211           while(gl!=NULL) {
1212             int i;
1213             for(i=0; i<gl->size; i++) {
1214               void * orig=gl->array[i];
1215               ENQUEUE(orig, gl->array[i]);
1216             }
1217             gl=gl->next;
1218           }
1219         }
1220       }
1221       memoryItem=memoryItem->next;
1222     }
1223   }
1224  }
1225
1226  updateAscendantSESE(SESEcommon* seseRec){
1227   int prevIdx;
1228   for(prevIdx=0; prevIdx<(seseRec->numDependentSESErecords); prevIdx++){
1229     SESEcommon* prevSESE = (SESEcommon*)
1230       (
1231        ((INTPTR)seseRec) +
1232        seseRec->offsetToDepSESErecords +
1233        (sizeof(INTPTR)*prevIdx)
1234       );
1235
1236     if(prevSESE!=NULL){
1237       struct garbagelist * prevgl=(struct garbagelist *)&(((SESEcommon*)(prevSESE))[1]);
1238       while(prevgl!=NULL) {
1239         int i;
1240         for(i=0; i<prevgl->size; i++) {
1241           void * orig=prevgl->array[i];
1242           ENQUEUE(orig, prevgl->array[i]);
1243         }
1244         prevgl=prevgl->next;
1245       }
1246     }
1247   }
1248
1249  }
1250 #endif
1251
1252 int within(void *ptr){ //debug function
1253   if(ptr>curr_heapptr || ptr<curr_heapbase){
1254     __asm__ __volatile__ ("int $3");  // breakpoint
1255   }
1256 }