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