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 "GenericHashtable.h"
   7 #include <string.h>
   8 #if defined(THREADS) || defined(DSTM)
   9 #include "thread.h"
  10 #endif
  11
  12 #ifdef DMALLOC
  13 #include "dmalloc.h"
  14 #endif
  15 #ifdef DSTM
  16 #include "dstm.h"
  17 #endif
  18
  19 #define NUMPTRS 100
  20
  21 #define INITIALHEAPSIZE 10*1024
  22 #define GCPOINT(x) ((int)((x)*0.9))
  23 /* This define takes in how full the heap is initially and returns a new heap size to use */
  24 #define HEAPSIZE(x,y) (((int)((x)/0.6))+y)
  25
  26 #ifdef TASK
  27 extern struct genhashtable * activetasks;
  28 extern struct parameterwrapper * objectqueues[NUMCLASSES];
  29 extern struct genhashtable * failedtasks;
  30 extern struct taskparamdescriptor *currtpd;
  31 extern struct RuntimeHash *forward;
  32 extern struct RuntimeHash *reverse;
  33 extern struct RuntimeHash *fdtoobject;
  34 #endif
  35
  36 #if defined(THREADS) || defined(DSTM)
  37 int needtocollect=0;
  38 struct listitem * list=NULL;
  39 int listcount=0;
  40 #endif
  41
  42 //Need to check if pointers are transaction pointers
  43 #ifdef DSTM
  44 #define ENQUEUE(orig, dst) \
  45 if ((!(((unsigned int)orig)&0x1))) {\
  46 if (orig>=curr_heapbase&&orig<curr_heaptop) {\
  47 void *copy;\
  48 if (gc_createcopy(orig,&copy))\
  49 enqueue(orig);\
  50 dst=copy;\
  51 }\
  52 }
  53 #else
  54 #define ENQUEUE(orig, dst) \
  55 void *copy; \
  56 if (gc_createcopy(orig,&copy))\
  57 enqueue(orig);\
  58 dst=copy
  59 #endif
  60
  61 struct pointerblock {
  62   void * ptrs[NUMPTRS];
  63   struct pointerblock *next;
  64 };
  65
  66 void * curr_heapbase=0;
  67 void * curr_heapptr=0;
  68 void * curr_heapgcpoint=0;
  69 void * curr_heaptop=0;
  70
  71 void * to_heapbase=0;
  72 void * to_heapptr=0;
  73 void * to_heaptop=0;
  74 long lastgcsize=0;
  75
  76 struct pointerblock *head=NULL;
  77 int headindex=0;
  78 struct pointerblock *tail=NULL;
  79 int tailindex=0;
  80 struct pointerblock *spare=NULL;
  81
  82 void enqueue(void *ptr) {
  83   if (headindex==NUMPTRS) {
  84     struct pointerblock * tmp;
  85     if (spare!=NULL) {
  86       tmp=spare;
  87       spare=NULL;
  88     } else
  89       tmp=malloc(sizeof(struct pointerblock));
  90     head->next=tmp;
  91     head=tmp;
  92     headindex=0;
  93   }
  94   head->ptrs[headindex++]=ptr;
  95 }
  96
  97 void * dequeue() {
  98   if (tailindex==NUMPTRS) {
  99     struct pointerblock *tmp=tail;
 100     tail=tail->next;
 101     tailindex=0;
 102     if (spare!=NULL)
 103       free(tmp);
 104     else
 105       spare=tmp;
 106   }
 107   return tail->ptrs[tailindex++];
 108 }
 109
 110 int moreItems() {
 111   if ((head==tail)&&(tailindex==headindex))
 112     return 0;
 113   return 1;
 114 }
 115
 116 #ifdef TASK
 117 struct pointerblock *taghead=NULL;
 118 int tagindex=0;
 119
 120 void enqueuetag(struct ___TagDescriptor___ *ptr) {
 121   if (tagindex==NUMPTRS) {
 122     struct pointerblock * tmp=malloc(sizeof(struct pointerblock));
 123     tmp->next=taghead;
 124     taghead=tmp;
 125     tagindex=0;
 126   }
 127   taghead->ptrs[tagindex++]=ptr;
 128 }
 129 #endif
 130
 131
 132 void collect(struct garbagelist * stackptr) {
 133 #if defined(THREADS)||defined(DSTM)
 134   needtocollect=1;
 135   pthread_mutex_lock(&gclistlock);
 136   while(1) {
 137     if ((listcount+1)==threadcount) {
 138       break; /* Have all other threads stopped */
 139     }
 140     pthread_cond_wait(&gccond, &gclistlock);
 141   }
 142 #endif
 143
 144   if (head==NULL) {
 145     headindex=0;
 146     tailindex=0;
 147     head=tail=malloc(sizeof(struct pointerblock));
 148   }
 149
 150 #ifdef TASK
 151   if (taghead==NULL) {
 152     tagindex=0;
 153     taghead=malloc(sizeof(struct pointerblock));
 154     taghead->next=NULL;
 155   }
 156 #endif
 157
 158   /* Check current stack */
 159 #if defined(THREADS)||defined(DSTM)
 160  {
 161    struct listitem *listptr=list;
 162    while(1) {
 163 #endif
 164
 165   while(stackptr!=NULL) {
 166     int i;
 167     for(i=0;i<stackptr->size;i++) {
 168       void * orig=stackptr->array[i];
 169       ENQUEUE(orig, stackptr->array[i]);
 170     }
 171     stackptr=stackptr->next;
 172   }
 173 #if defined(THREADS)||defined(DSTM)
 174   /* Go to next thread */
 175   if (listptr!=NULL) {
 176     void * orig=listptr->locklist;
 177     ENQUEUE(orig, listptr->locklist);
 178     stackptr=listptr->stackptr;
 179     listptr=listptr->next;
 180   } else
 181     break;
 182    }
 183  }
 184 #endif
 185
 186 #ifdef TASK
 187   {
 188     /* Update objectsets */
 189     int i;
 190     for(i=0;i<NUMCLASSES;i++) {
 191       struct parameterwrapper * p=objectqueues[i];
 192       while(p!=NULL) {
 193         struct ObjectHash * set=p->objectset;
 194         struct ObjectNode * ptr=set->listhead;
 195         while(ptr!=NULL) {
 196           void *orig=(void *)ptr->key;
 197           ENQUEUE(orig, *((void **)(&ptr->key)));
 198           ptr=ptr->lnext;
 199         }
 200         ObjectHashrehash(set); /* Rehash the table */
 201         p=p->next;
 202       }
 203     }
 204   }
 205
 206   if (forward!=NULL) {
 207     struct RuntimeNode * ptr=forward->listhead;
 208     while(ptr!=NULL) {
 209       void * orig=(void *)ptr->key;
 210       ENQUEUE(orig, *((void **)(&ptr->key)));
 211       ptr=ptr->lnext;
 212     }
 213     RuntimeHashrehash(forward); /* Rehash the table */
 214   }
 215
 216   if (reverse!=NULL) {
 217     struct RuntimeNode * ptr=reverse->listhead;
 218     while(ptr!=NULL) {
 219       void *orig=(void *)ptr->data;
 220       ENQUEUE(orig, *((void**)(&ptr->data)));
 221       ptr=ptr->lnext;
 222     }
 223   }
 224
 225   {
 226     struct RuntimeNode * ptr=fdtoobject->listhead;
 227     while(ptr!=NULL) {
 228       void *orig=(void *)ptr->data;
 229       ENQUEUE(orig, *((void**)(&ptr->data)));
 230       ptr=ptr->lnext;
 231     }
 232   }
 233
 234   {
 235     /* Update current task descriptor */
 236     int i;
 237     for(i=0;i<currtpd->numParameters;i++) {
 238       void *orig=currtpd->parameterArray[i];
 239       ENQUEUE(orig, currtpd->parameterArray[i]);
 240     }
 241
 242   }
 243
 244     /* Update active tasks */
 245   {
 246     struct genpointerlist * ptr=activetasks->list;
 247     while(ptr!=NULL) {
 248       struct taskparamdescriptor *tpd=ptr->src;
 249       int i;
 250       for(i=0;i<tpd->numParameters;i++) {
 251         void * orig=tpd->parameterArray[i];
 252         ENQUEUE(orig, tpd->parameterArray[i]);
 253       }
 254       ptr=ptr->inext;
 255     }
 256     genrehash(activetasks);
 257   }
 258
 259     /* Update failed tasks */
 260   {
 261     struct genpointerlist * ptr=failedtasks->list;
 262     while(ptr!=NULL) {
 263       struct taskparamdescriptor *tpd=ptr->src;
 264       int i;
 265       for(i=0;i<tpd->numParameters;i++) {
 266         void * orig=tpd->parameterArray[i];
 267         ENQUEUE(orig, tpd->parameterArray[i]);
 268       }
 269       ptr=ptr->inext;
 270     }
 271     genrehash(failedtasks);
 272   }
 273 #endif
 274
 275   while(moreItems()) {
 276     void * ptr=dequeue();
 277     void *cpy=((void **)ptr)[1];
 278     int type=((int *)cpy)[0];
 279     unsigned int * pointer;
 280 #ifdef TASK
 281     if(type==TAGTYPE) {
 282       /* Enqueue Tag */
 283       /* Nothing is inside */
 284       enqueuetag(ptr);
 285       continue;
 286     }
 287 #endif
 288     pointer=pointerarray[type];
 289     if (pointer==0) {
 290       /* Array of primitives */
 291       /* Do nothing */
 292 #ifdef DSTM
 293       struct ArrayObject *ao=(struct ArrayObject *) ptr;
 294       struct ArrayObject *ao_cpy=(struct ArrayObject *) cpy;
 295       ENQUEUE((void *)ao->___nextobject___, *((void **)&ao_cpy->___nextobject___));
 296       ENQUEUE((void *)ao->___localcopy___, *((void **)&ao_cpy->___localcopy___));
 297 #endif
 298     } else if (((int)pointer)==1) {
 299       /* Array of pointers */
 300       struct ArrayObject *ao=(struct ArrayObject *) ptr;
 301       struct ArrayObject *ao_cpy=(struct ArrayObject *) cpy;
 302 #ifdef DSTM
 303       ENQUEUE((void *)ao->___nextobject___, *((void **)&ao_cpy->___nextobject___));
 304       ENQUEUE((void *)ao->___localcopy___, *((void **)&ao_cpy->___localcopy___));
 305 #endif
 306       int length=ao->___length___;
 307       int i;
 308       for(i=0;i<length;i++) {
 309         void *objptr=((void **)(((char *)& ao->___length___)+sizeof(int)))[i];
 310         ENQUEUE(objptr, ((void **)(((char *)& ao_cpy->___length___)+sizeof(int)))[i]);
 311       }
 312     } else {
 313       int size=pointer[0];
 314       int i;
 315       for(i=1;i<=size;i++) {
 316         unsigned int offset=pointer[i];
 317         void * objptr=*((void **)(((int)ptr)+offset));
 318         ENQUEUE(objptr, *((void **) (((int)cpy)+offset)));
 319       }
 320     }
 321   }
 322 #ifdef TASK
 323   fixtags();
 324 #endif
 325
 326 #if defined(THREADS)||defined(DSTM)
 327   needtocollect=0;
 328   pthread_mutex_unlock(&gclistlock);
 329 #endif
 330 }
 331
 332 #ifdef TASK
 333
 334 /* Fix up the references from tags.  This can't be done earlier,
 335    because we don't want tags to keep objects alive */
 336 void fixtags() {
 337   while(taghead!=NULL) {
 338     int i;
 339     struct pointerblock *tmp=taghead->next;
 340     for(i=0;i<tagindex;i++) {
 341       struct ___TagDescriptor___ *tagd=taghead->ptrs[i];
 342       struct ___Object___ *obj=tagd->flagptr;
 343       struct ___TagDescriptor___ *copy=((struct ___TagDescriptor___**)tagd)[1];
 344       if (obj==NULL) {
 345         /* Zero object case */
 346       } else if (obj->type==-1) {
 347         /* Single object case */
 348         copy->flagptr=((struct ___Object___**)obj)[1];
 349       } else if (obj->type==OBJECTARRAYTYPE) {
 350         /* Array case */
 351         struct ArrayObject *ao=(struct ArrayObject *) obj;
 352         int livecount=0;
 353         int j;
 354         int k=0;
 355         struct ArrayObject *aonew;
 356
 357         /* Count live objects */
 358         for(j=0;j<ao->___cachedCode___;j++) {
 359           struct ___Object___ * tobj=ARRAYGET(ao, struct ___Object___ *, j);
 360           if (tobj->type==-1)
 361             livecount++;
 362         }
 363
 364         livecount=((livecount-1)/OBJECTARRAYINTERVAL+1)*OBJECTARRAYINTERVAL;
 365         aonew=(struct ArrayObject *) tomalloc(sizeof(struct ArrayObject)+sizeof(struct ___Object___*)*livecount);
 366         memcpy(aonew, ao, sizeof(struct ArrayObject));
 367         aonew->type=OBJECTARRAYTYPE;
 368         aonew->___length___=livecount;
 369         copy->flagptr=aonew;
 370         for(j=0;j<ao->___cachedCode___;j++) {
 371           struct ___Object___ * tobj=ARRAYGET(ao, struct ___Object___ *, j);
 372           if (tobj->type==-1) {
 373             struct ___Object___ * tobjcpy=((struct ___Object___**)tobj)[1];
 374             ARRAYSET(aonew, struct ___Object___*, k++,tobjcpy);
 375           }
 376         }
 377         aonew->___cachedCode___=k;
 378         for(;k<livecount;k++) {
 379           ARRAYSET(aonew, struct ___Object___*, k, NULL);
 380         }
 381       } else {
 382         /* No object live anymore */
 383         copy->flagptr=NULL;
 384       }
 385     }
 386     free(taghead);
 387     taghead=tmp;
 388     tagindex=NUMPTRS;
 389   }
 390 }
 391 #endif
 392
 393 void * tomalloc(int size) {
 394   void * ptr=to_heapptr;
 395   if ((size%4)!=0)
 396     size+=(4-(size%4));
 397   to_heapptr+=size;
 398   return ptr;
 399 }
 400
 401 #if defined(THREADS)||defined(DSTM)
 402 void checkcollect(void * ptr) {
 403   if (needtocollect) {
 404     struct listitem * tmp=stopforgc((struct garbagelist *)ptr);
 405     pthread_mutex_lock(&gclock); // Wait for GC
 406     restartaftergc(tmp);
 407     pthread_mutex_unlock(&gclock);
 408
 409   }
 410 }
 411
 412 #ifdef DSTM
 413 void checkcollect2(void * ptr, transrecord_t *trans) {
 414   if (needtocollect) {
 415     int ptrarray[]={1, (int)ptr, (int) trans->revertlist};
 416     struct listitem * tmp=stopforgc((struct garbagelist *)ptrarray);
 417     pthread_mutex_lock(&gclock); // Wait for GC
 418     restartaftergc(tmp);
 419     pthread_mutex_unlock(&gclock);
 420     trans->revertlist=(struct ___Object___*)ptrarray[2];
 421   }
 422 }
 423 #endif
 424
 425
 426 struct listitem * stopforgc(struct garbagelist * ptr) {
 427   struct listitem * litem=malloc(sizeof(struct listitem));
 428   litem->stackptr=ptr;
 429   litem->locklist=pthread_getspecific(threadlocks);
 430   litem->prev=NULL;
 431   pthread_mutex_lock(&gclistlock);
 432   litem->next=list;
 433   if(list!=NULL)
 434     list->prev=litem;
 435   list=litem;
 436   listcount++;
 437   pthread_cond_signal(&gccond);
 438   pthread_mutex_unlock(&gclistlock);
 439   return litem;
 440 }
 441
 442 void restartaftergc(struct listitem * litem) {
 443   pthread_mutex_lock(&gclistlock);
 444   pthread_setspecific(threadlocks, litem->locklist);
 445   if (litem->prev==NULL) {
 446     list=litem->next;
 447   } else {
 448     litem->prev->next=litem->next;
 449   }
 450   if (litem->next!=NULL) {
 451     litem->next->prev=litem->prev;
 452   }
 453   listcount--;
 454   pthread_mutex_unlock(&gclistlock);
 455   free(litem);
 456 }
 457 #endif
 458
 459 void * mygcmalloc(struct garbagelist * stackptr, int size) {
 460   void *ptr;
 461 #if defined(THREADS)||defined(DSTM)
 462   if (pthread_mutex_trylock(&gclock)!=0) {
 463     struct listitem *tmp=stopforgc(stackptr);
 464     pthread_mutex_lock(&gclock);
 465     restartaftergc(tmp);
 466   }
 467 #endif
 468   ptr=curr_heapptr;
 469   if ((size%4)!=0)
 470     size+=(4-(size%4));
 471   curr_heapptr+=size;
 472   if (curr_heapptr>curr_heapgcpoint) {
 473     if (curr_heapbase==0) {
 474       /* Need to allocate base heap */
 475       curr_heapbase=malloc(INITIALHEAPSIZE);
 476       bzero(curr_heapbase, INITIALHEAPSIZE);
 477       curr_heaptop=curr_heapbase+INITIALHEAPSIZE;
 478       curr_heapgcpoint=((char *) curr_heapbase)+GCPOINT(INITIALHEAPSIZE);
 479       curr_heapptr=curr_heapbase+size;
 480
 481       to_heapbase=malloc(INITIALHEAPSIZE);
 482       to_heaptop=to_heapbase+INITIALHEAPSIZE;
 483       to_heapptr=to_heapbase;
 484       ptr=curr_heapbase;
 485 #if defined(THREADS)||defined(DSTM)
 486       pthread_mutex_unlock(&gclock);
 487 #endif
 488       return ptr;
 489     }
 490
 491     /* Grow the to heap if necessary */
 492     {
 493       int curr_heapsize=curr_heaptop-curr_heapbase;
 494       int to_heapsize=to_heaptop-to_heapbase;
 495       int last_heapsize=0;
 496       if (lastgcsize>0) {
 497         last_heapsize=HEAPSIZE(lastgcsize, size);
 498         if ((last_heapsize%4)!=0)
 499           last_heapsize+=(4-(last_heapsize%4));
 500       }
 501       if (curr_heapsize>last_heapsize)
 502         last_heapsize=curr_heapsize;
 503       if (last_heapsize>to_heapsize) {
 504         free(to_heapbase);
 505         to_heapbase=malloc(last_heapsize);
 506         to_heaptop=to_heapbase+last_heapsize;
 507         to_heapptr=to_heapbase;
 508       }
 509     }
 510
 511     /* Do our collection */
 512     collect(stackptr);
 513
 514     /* Update stat on previous gc size */
 515     lastgcsize=(to_heapptr-to_heapbase)+size;
 516
 517     /* Flip to/curr heaps */
 518     {
 519       void * tmp=to_heapbase;
 520       to_heapbase=curr_heapbase;
 521       curr_heapbase=tmp;
 522
 523       tmp=to_heaptop;
 524       to_heaptop=curr_heaptop;
 525       curr_heaptop=tmp;
 526
 527       tmp=to_heapptr;
 528       curr_heapptr=to_heapptr+size;
 529       curr_heapgcpoint=((char *) curr_heapbase)+GCPOINT(curr_heaptop-curr_heapbase);
 530       to_heapptr=to_heapbase;
 531
 532       /* Not enough room :(, redo gc */
 533       if (curr_heapptr>curr_heapgcpoint) {
 534 #if defined(THREADS)||defined(DSTM)
 535         pthread_mutex_unlock(&gclock);
 536 #endif
 537         return mygcmalloc(stackptr, size);
 538       }
 539
 540       bzero(tmp, curr_heaptop-tmp);
 541 #if defined(THREADS)||defined(DSTM)
 542       pthread_mutex_unlock(&gclock);
 543 #endif
 544       return tmp;
 545     }
 546   } else {
 547 #if defined(THREADS)||defined(DSTM)
 548     pthread_mutex_unlock(&gclock);
 549 #endif
 550     return ptr;
 551   }
 552 }
 553
 554
 555 int gc_createcopy(void * orig, void ** copy_ptr) {
 556   if (orig==0) {
 557     *copy_ptr=NULL;
 558     return 0;
 559   } else {
 560     int type=((int *)orig)[0];
 561     if (type==-1) {
 562       *copy_ptr=((void **)orig)[1];
 563       return 0;
 564     } if (type<NUMCLASSES) {
 565       /* We have a normal object */
 566       int size=classsize[type];
 567       void *newobj=tomalloc(size);
 568       memcpy(newobj, orig, size);
 569       ((int *)orig)[0]=-1;
 570       ((void **)orig)[1]=newobj;
 571       *copy_ptr=newobj;
 572       return 1;
 573     } else {
 574       /* We have an array */
 575       struct ArrayObject *ao=(struct ArrayObject *)orig;
 576       int elementsize=classsize[type];
 577       int length=ao->___length___;
 578       int size=sizeof(struct ArrayObject)+length*elementsize;
 579       void *newobj=tomalloc(size);
 580       memcpy(newobj, orig, size);
 581       ((int *)orig)[0]=-1;
 582       ((void **)orig)[1]=newobj;
 583       *copy_ptr=newobj;
 584       return 1;
 585     }
 586   }
 587 }