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 #ifdef THREADS
   9 #include "thread.h"
  10 #endif
  11 #ifdef DMALLOC
  12 #include "dmalloc.h"
  13 #endif
  14
  15
  16 #define NUMPTRS 100
  17
  18 #define INITIALHEAPSIZE 10*1024
  19 #define GCPOINT(x) ((int)((x)*0.9))
  20 /* This define takes in how full the heap is initially and returns a new heap size to use */
  21 #define HEAPSIZE(x,y) (((int)((x)/0.6))+y)
  22
  23 #ifdef TASK
  24 extern struct genhashtable * activetasks;
  25 extern struct parameterwrapper * objectqueues[NUMCLASSES];
  26 extern struct genhashtable * failedtasks;
  27 extern struct taskparamdescriptor *currtpd;
  28 extern struct RuntimeHash *forward;
  29 extern struct RuntimeHash *reverse;
  30 extern struct RuntimeHash *fdtoobject;
  31 #endif
  32
  33 #ifdef THREADS
  34 int needtocollect=0;
  35 struct listitem * list=NULL;
  36 int listcount=0;
  37 #endif
  38
  39 struct pointerblock {
  40   void * ptrs[NUMPTRS];
  41   struct pointerblock *next;
  42 };
  43
  44 struct pointerblock *head=NULL;
  45 int headindex=0;
  46 struct pointerblock *tail=NULL;
  47 int tailindex=0;
  48 struct pointerblock *spare=NULL;
  49
  50 void enqueue(void *ptr) {
  51   if (headindex==NUMPTRS) {
  52     struct pointerblock * tmp;
  53     if (spare!=NULL) {
  54       tmp=spare;
  55       spare=NULL;
  56     } else
  57       tmp=malloc(sizeof(struct pointerblock));
  58     head->next=tmp;
  59     head=tmp;
  60     headindex=0;
  61   }
  62   head->ptrs[headindex++]=ptr;
  63 }
  64
  65 void * dequeue() {
  66   if (tailindex==NUMPTRS) {
  67     struct pointerblock *tmp=tail;
  68     tail=tail->next;
  69     tailindex=0;
  70     if (spare!=NULL)
  71       free(tmp);
  72     else
  73       spare=tmp;
  74   }
  75   return tail->ptrs[tailindex++];
  76 }
  77
  78 int moreItems() {
  79   if ((head==tail)&&(tailindex==headindex))
  80     return 0;
  81   return 1;
  82 }
  83
  84 void collect(struct garbagelist * stackptr) {
  85 #ifdef THREADS
  86   needtocollect=1;
  87   pthread_mutex_lock(&gclistlock);
  88   while(1) {
  89     if ((listcount+1)==threadcount) {
  90       break; /* Have all other threads stopped */
  91     }
  92     pthread_cond_wait(&gccond, &gclistlock);
  93   }
  94 #endif
  95
  96   if (head==NULL) {
  97     headindex=0;
  98     tailindex=0;
  99     head=tail=malloc(sizeof(struct pointerblock));
 100   }
 101   /* Check current stack */
 102 #ifdef THREADS
 103  {
 104    struct listitem *listptr=list;
 105    while(stackptr!=NULL) {
 106 #endif
 107
 108   while(stackptr!=NULL) {
 109     int i;
 110     for(i=0;i<stackptr->size;i++) {
 111       void * orig=stackptr->array[i];
 112       void * copy;
 113       if (gc_createcopy(orig,&copy))
 114         enqueue(orig);
 115       stackptr->array[i]=copy;
 116     }
 117     stackptr=stackptr->next;
 118   }
 119 #ifdef THREADS
 120   /* Go to next thread */
 121   if (listptr!=NULL) {
 122     void * orig=listptr->locklist;
 123     void * copy;
 124     if (gc_createcopy(orig,&copy))
 125       enqueue(orig);
 126     listptr->locklist=copy;
 127     stackptr=listptr->stackptr;
 128     listptr=listptr->next;
 129   }
 130    }
 131  }
 132 #endif
 133
 134 #ifdef TASK
 135   {
 136     /* Update objectsets */
 137     int i;
 138     for(i=0;i<NUMCLASSES;i++) {
 139       struct parameterwrapper * p=objectqueues[i];
 140       while(p!=NULL) {
 141         struct RuntimeHash * set=p->objectset;
 142         struct RuntimeNode * ptr=set->listhead;
 143         while(ptr!=NULL) {
 144           void *orig=(void *)ptr->key;
 145           void *copy;
 146           if (gc_createcopy(orig, &copy))
 147             enqueue(orig);
 148           ptr->key=(int)copy;
 149
 150           ptr=ptr->lnext;
 151         }
 152         RuntimeHashrehash(set); /* Rehash the table */
 153         p=p->next;
 154       }
 155     }
 156   }
 157
 158   if (forward!=NULL) {
 159     struct RuntimeNode * ptr=forward->listhead;
 160     while(ptr!=NULL) {
 161       void * orig=(void *)ptr->key;
 162       void *copy;
 163       if (gc_createcopy(orig, &copy))
 164         enqueue(orig);
 165       ptr->key=(int)copy;
 166
 167       ptr=ptr->lnext;
 168     }
 169     RuntimeHashrehash(forward); /* Rehash the table */
 170   }
 171
 172   if (reverse!=NULL) {
 173     struct RuntimeNode * ptr=reverse->listhead;
 174     while(ptr!=NULL) {
 175       void *orig=(void *)ptr->data;
 176       void *copy;
 177       if (gc_createcopy(orig, &copy))
 178         enqueue(orig);
 179       ptr->data=(int)copy;
 180
 181       ptr=ptr->lnext;
 182     }
 183   }
 184
 185   {
 186     struct RuntimeNode * ptr=fdtoobject->listhead;
 187     while(ptr!=NULL) {
 188       void *orig=(void *)ptr->data;
 189       void *copy;
 190       if (gc_createcopy(orig, &copy))
 191         enqueue(orig);
 192       ptr->data=(int)copy;
 193
 194       ptr=ptr->lnext;
 195     }
 196   }
 197
 198   {
 199     /* Update current task descriptor */
 200     int i;
 201     for(i=0;i<currtpd->numParameters;i++) {
 202       void *orig=currtpd->parameterArray[i];
 203       void *copy;
 204       if (gc_createcopy(orig, &copy))
 205         enqueue(orig);
 206       currtpd->parameterArray[i]=copy;
 207     }
 208
 209   }
 210
 211     /* Update active tasks */
 212   {
 213     struct genpointerlist * ptr=activetasks->list;
 214     while(ptr!=NULL) {
 215       struct taskparamdescriptor *tpd=ptr->src;
 216       int i;
 217       for(i=0;i<tpd->numParameters;i++) {
 218         void * orig=tpd->parameterArray[i];
 219         void * copy;
 220         if (gc_createcopy(orig, &copy))
 221           enqueue(orig);
 222         tpd->parameterArray[i]=copy;
 223       }
 224       ptr=ptr->inext;
 225     }
 226     genrehash(activetasks);
 227   }
 228
 229     /* Update failed tasks */
 230   {
 231     struct genpointerlist * ptr=failedtasks->list;
 232     while(ptr!=NULL) {
 233       struct taskparamdescriptor *tpd=ptr->src;
 234       int i;
 235       for(i=0;i<tpd->numParameters;i++) {
 236         void * orig=tpd->parameterArray[i];
 237         void * copy;
 238         if (gc_createcopy(orig, &copy))
 239           enqueue(orig);
 240         tpd->parameterArray[i]=copy;
 241       }
 242       ptr=ptr->inext;
 243     }
 244     genrehash(failedtasks);
 245   }
 246 #endif
 247
 248   while(moreItems()) {
 249     void * ptr=dequeue();
 250     void *cpy=((void **)ptr)[1];
 251     int type=((int *)cpy)[0];
 252     int * pointer=pointerarray[type];
 253     if (pointer==0) {
 254       /* Array of primitives */
 255       /* Do nothing */
 256     } else if (((int)pointer)==1) {
 257       /* Array of pointers */
 258       struct ArrayObject *ao=(struct ArrayObject *) ptr;
 259       struct ArrayObject *ao_cpy=(struct ArrayObject *) cpy;
 260       int length=ao->___length___;
 261       int i;
 262       for(i=0;i<length;i++) {
 263         void *objptr=((void **)(((char *)& ao->___length___)+sizeof(int)))[i];
 264         void * copy;
 265         if (gc_createcopy(objptr, &copy))
 266           enqueue(objptr);
 267         ((void **)(((char *)& ao_cpy->___length___)+sizeof(int)))[i]=copy;
 268       }
 269     } else {
 270       int size=pointer[0];
 271       int i;
 272       for(i=1;i<=size;i++) {
 273         int offset=pointer[i];
 274         void * objptr=*((void **)(((int)ptr)+offset));
 275         void * copy;
 276         if (gc_createcopy(objptr, &copy))
 277           enqueue(objptr);
 278         *((void **) (((int)cpy)+offset))=copy;
 279       }
 280     }
 281   }
 282 #ifdef THREADS
 283   needtocollect=0;
 284   pthread_mutex_unlock(&gclistlock);
 285 #endif
 286 }
 287
 288 void * curr_heapbase=0;
 289 void * curr_heapptr=0;
 290 void * curr_heapgcpoint=0;
 291 void * curr_heaptop=0;
 292
 293 void * to_heapbase=0;
 294 void * to_heapptr=0;
 295 void * to_heaptop=0;
 296 long lastgcsize=0;
 297
 298 void * tomalloc(int size) {
 299   void * ptr=to_heapptr;
 300   if ((size%4)!=0)
 301     size+=(4-(size%4));
 302   to_heapptr+=size;
 303   return ptr;
 304 }
 305
 306 #ifdef THREADS
 307
 308 void checkcollect(void * ptr) {
 309   if (needtocollect) {
 310     struct listitem * tmp=stopforgc((struct garbagelist *)ptr);
 311     pthread_mutex_lock(&gclock); // Wait for GC
 312     restartaftergc(tmp);
 313     pthread_mutex_unlock(&gclock);
 314
 315   }
 316 }
 317
 318 struct listitem * stopforgc(struct garbagelist * ptr) {
 319   struct listitem * litem=malloc(sizeof(struct listitem));
 320   litem->stackptr=ptr;
 321   litem->locklist=pthread_getspecific(threadlocks);
 322   litem->prev=NULL;
 323   pthread_mutex_lock(&gclistlock);
 324   litem->next=list;
 325   if(list!=NULL)
 326     list->prev=litem;
 327   list=litem;
 328   listcount++;
 329   pthread_cond_signal(&gccond);
 330   pthread_mutex_unlock(&gclistlock);
 331   return litem;
 332 }
 333
 334 void restartaftergc(struct listitem * litem) {
 335   pthread_mutex_lock(&gclistlock);
 336   pthread_setspecific(threadlocks, litem->locklist);
 337   if (litem->prev==NULL) {
 338     list=litem->next;
 339   } else {
 340     litem->prev->next=litem->next;
 341   }
 342   if (litem->next!=NULL) {
 343     litem->next->prev=litem->prev;
 344   }
 345   listcount--;
 346   pthread_mutex_unlock(&gclistlock);
 347   free(litem);
 348 }
 349 #endif
 350
 351 void * mygcmalloc(struct garbagelist * stackptr, int size) {
 352   void *ptr;
 353 #ifdef THREADS
 354   if (pthread_mutex_trylock(&gclock)!=0) {
 355     struct listitem *tmp=stopforgc(stackptr);
 356     pthread_mutex_lock(&gclock);
 357     restartaftergc(tmp);
 358   }
 359 #endif
 360   ptr=curr_heapptr;
 361   if ((size%4)!=0)
 362     size+=(4-(size%4));
 363   curr_heapptr+=size;
 364   if (curr_heapptr>curr_heapgcpoint) {
 365     if (curr_heapbase==0) {
 366       /* Need to allocate base heap */
 367       curr_heapbase=malloc(INITIALHEAPSIZE);
 368       bzero(curr_heapbase, INITIALHEAPSIZE);
 369       curr_heaptop=curr_heapbase+INITIALHEAPSIZE;
 370       curr_heapgcpoint=((char *) curr_heapbase)+GCPOINT(INITIALHEAPSIZE);
 371       curr_heapptr=curr_heapbase+size;
 372
 373       to_heapbase=malloc(INITIALHEAPSIZE);
 374       to_heaptop=to_heapbase+INITIALHEAPSIZE;
 375       to_heapptr=to_heapbase;
 376       ptr=curr_heapbase;
 377 #ifdef THREADS
 378       pthread_mutex_unlock(&gclock);
 379 #endif
 380       return ptr;
 381     }
 382
 383     /* Grow the to heap if necessary */
 384     {
 385       int curr_heapsize=curr_heaptop-curr_heapbase;
 386       int to_heapsize=to_heaptop-to_heapbase;
 387       int last_heapsize=0;
 388       if (lastgcsize>0) {
 389         last_heapsize=HEAPSIZE(lastgcsize, size);
 390         if ((last_heapsize%4)!=0)
 391           last_heapsize+=(4-(last_heapsize%4));
 392       }
 393       if (curr_heapsize>last_heapsize)
 394         last_heapsize=curr_heapsize;
 395       if (last_heapsize>to_heapsize) {
 396         free(to_heapbase);
 397         to_heapbase=malloc(last_heapsize);
 398         to_heaptop=to_heapbase+last_heapsize;
 399         to_heapptr=to_heapbase;
 400       }
 401     }
 402
 403     /* Do our collection */
 404     collect(stackptr);
 405
 406     /* Update stat on previous gc size */
 407     lastgcsize=(to_heapptr-to_heapbase)+size;
 408
 409     /* Flip to/curr heaps */
 410     {
 411       void * tmp=to_heapbase;
 412       to_heapbase=curr_heapbase;
 413       curr_heapbase=tmp;
 414
 415       tmp=to_heaptop;
 416       to_heaptop=curr_heaptop;
 417       curr_heaptop=tmp;
 418
 419       tmp=to_heapptr;
 420       curr_heapptr=to_heapptr+size;
 421       curr_heapgcpoint=((char *) curr_heapbase)+GCPOINT(curr_heaptop-curr_heapbase);
 422       to_heapptr=to_heapbase;
 423
 424       /* Not enough room :(, redo gc */
 425       if (curr_heapptr>curr_heapgcpoint) {
 426 #ifdef THREADS
 427         pthread_mutex_unlock(&gclock);
 428 #endif
 429         return mygcmalloc(stackptr, size);
 430       }
 431
 432       bzero(tmp, curr_heaptop-tmp);
 433 #ifdef THREADS
 434       pthread_mutex_unlock(&gclock);
 435 #endif
 436       return tmp;
 437     }
 438   } else {
 439 #ifdef THREADS
 440     pthread_mutex_unlock(&gclock);
 441 #endif
 442     return ptr;
 443   }
 444 }
 445
 446
 447 int gc_createcopy(void * orig, void ** copy_ptr) {
 448   if (orig==0) {
 449     *copy_ptr=NULL;
 450     return 0;
 451   } else {
 452     int type=((int *)orig)[0];
 453     if (type==-1) {
 454       *copy_ptr=((void **)orig)[1];
 455       return 0;
 456     } if (type<NUMCLASSES) {
 457       /* We have a normal object */
 458       int size=classsize[type];
 459       void *newobj=tomalloc(size);
 460       memcpy(newobj, orig, size);
 461       ((int *)orig)[0]=-1;
 462       ((void **)orig)[1]=newobj;
 463       *copy_ptr=newobj;
 464       return 1;
 465     } else {
 466       /* We have an array */
 467       struct ArrayObject *ao=(struct ArrayObject *)orig;
 468       int elementsize=classsize[type];
 469       int length=ao->___length___;
 470       int size=sizeof(struct ArrayObject)+length*elementsize;
 471       void *newobj=tomalloc(size);
 472       memcpy(newobj, orig, size);
 473       ((int *)orig)[0]=-1;
 474       ((void **)orig)[1]=newobj;
 475       *copy_ptr=newobj;
 476       return 1;
 477     }
 478   }
 479 }