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