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
   9 #define NUMPTRS 100
  10
  11 #define INITIALHEAPSIZE 10*1024
  12 #define GCPOINT(x) ((int)((x)*0.9))
  13 /* This define takes in how full the heap is initially and returns a new heap size to use */
  14 #define HEAPSIZE(x,y) (((int)((x)/0.6))+y)
  15
  16 #ifdef TASK
  17 extern struct Queue * activetasks;
  18 extern struct parameterwrapper * objectqueues[NUMCLASSES];
  19 extern struct genhashtable * failedtasks;
  20 extern struct RuntimeHash *forward;
  21 extern struct RuntimeHash *reverse;
  22 extern struct RuntimeHash *fdtoobject;
  23 #endif
  24
  25 struct pointerblock {
  26   void * ptrs[NUMPTRS];
  27   struct pointerblock *next;
  28 };
  29
  30 struct pointerblock *head=NULL;
  31 int headindex=0;
  32 struct pointerblock *tail=NULL;
  33 int tailindex=0;
  34 struct pointerblock *spare=NULL;
  35
  36
  37 void enqueue(void *ptr) {
  38   if (headindex==NUMPTRS) {
  39     struct pointerblock * tmp;
  40     if (spare!=NULL) {
  41       tmp=spare;
  42       spare=NULL;
  43     } else
  44       tmp=malloc(sizeof(struct pointerblock));
  45     head->next=tmp;
  46     head=tmp;
  47     headindex=0;
  48   }
  49   head->ptrs[headindex++]=ptr;
  50 }
  51
  52 void * dequeue() {
  53   if (tailindex==NUMPTRS) {
  54     struct pointerblock *tmp=tail;
  55     tail=tail->next;
  56     tailindex=0;
  57     if (spare!=NULL)
  58       free(tmp);
  59     else
  60       spare=tmp;
  61   }
  62   return tail->ptrs[tailindex++];
  63 }
  64
  65 int moreItems() {
  66   if ((head==tail)&&(tailindex==headindex))
  67     return 0;
  68   return 1;
  69 }
  70
  71 void collect(struct garbagelist * stackptr) {
  72   if (head==NULL) {
  73     headindex=0;
  74     tailindex=0;
  75     head=tail=malloc(sizeof(struct pointerblock));
  76   }
  77   /* Check current stack */
  78   while(stackptr!=NULL) {
  79     int i;
  80     for(i=0;i<stackptr->size;i++) {
  81       void * orig=stackptr->array[i];
  82       void * copy;
  83       if (gc_createcopy(orig,&copy))
  84         enqueue(orig);
  85       stackptr->array[i]=copy;
  86     }
  87     stackptr=stackptr->next;
  88   }
  89
  90 #ifdef TASK
  91   {
  92     /* Update objectsets */
  93     int i;
  94     for(i=0;i<NUMCLASSES;i++) {
  95       struct parameterwrapper * p=objectqueues[i];
  96       while(p!=NULL) {
  97         struct RuntimeHash * set=p->objectset;
  98         struct RuntimeNode * ptr=set->listhead;
  99         while(ptr!=NULL) {
 100           void *orig=(void *)ptr->key;
 101           void *copy;
 102           if (gc_createcopy(orig, &copy))
 103             enqueue(orig);
 104           ptr->key=(int)copy;
 105
 106           ptr=ptr->lnext;
 107         }
 108         RuntimeHashrehash(set); /* Rehash the table */
 109         p=p->next;
 110       }
 111     }
 112   }
 113
 114   if (forward!=NULL) {
 115     struct RuntimeNode * ptr=forward->listhead;
 116     while(ptr!=NULL) {
 117       void * orig=(void *)ptr->key;
 118       void *copy;
 119       if (gc_createcopy(orig, &copy))
 120         enqueue(orig);
 121       ptr->key=(int)copy;
 122
 123       ptr=ptr->lnext;
 124     }
 125     RuntimeHashrehash(forward); /* Rehash the table */
 126   }
 127
 128   if (reverse!=NULL) {
 129     struct RuntimeNode * ptr=reverse->listhead;
 130     while(ptr!=NULL) {
 131       void *orig=(void *)ptr->data;
 132       void *copy;
 133       if (gc_createcopy(orig, &copy))
 134         enqueue(orig);
 135       ptr->data=(int)copy;
 136
 137       ptr=ptr->lnext;
 138     }
 139   }
 140
 141   {
 142     struct RuntimeNode * ptr=fdtoobject->listhead;
 143     while(ptr!=NULL) {
 144       void *orig=(void *)ptr->data;
 145       void *copy;
 146       if (gc_createcopy(orig, &copy))
 147         enqueue(orig);
 148       ptr->data=(int)copy;
 149
 150       ptr=ptr->lnext;
 151     }
 152   }
 153
 154
 155   {
 156     /* Update active tasks */
 157     struct QueueItem * ptr=activetasks->head;
 158     while (ptr!=NULL) {
 159       struct taskparamdescriptor *tpd=ptr->objectptr;
 160       int i;
 161       for(i=0;i<tpd->numParameters;i++) {
 162         void *orig=tpd->parameterArray[i];
 163         void *copy;
 164         if (gc_createcopy(orig, &copy))
 165           enqueue(orig);
 166         tpd->parameterArray[i]=copy;
 167       }
 168       ptr=ptr->next;
 169     }
 170   }
 171     /* Update failed tasks */
 172   {
 173     struct genpointerlist * ptr=failedtasks->list;
 174     while(ptr!=NULL) {
 175       void *orig=ptr->src;
 176       void *copy;
 177       if (gc_createcopy(orig, &copy))
 178         enqueue(orig);
 179       ptr->src=copy;
 180       ptr->object=copy;
 181       ptr=ptr->inext;
 182     }
 183     genrehash(failedtasks);
 184   }
 185 #endif
 186
 187   while(moreItems()) {
 188     void * ptr=dequeue();
 189     void *cpy=((void **)ptr)[1];
 190     int type=((int *)cpy)[0];
 191     int * pointer=pointerarray[type];
 192     if (pointer==0) {
 193       /* Array of primitives */
 194       /* Do nothing */
 195     } else if (((int)pointer)==1) {
 196       /* Array of pointers */
 197       struct ArrayObject *ao=(struct ArrayObject *) ptr;
 198       struct ArrayObject *ao_cpy=(struct ArrayObject *) cpy;
 199       int length=ao->___length___;
 200       int i;
 201       for(i=0;i<length;i++) {
 202         void *objptr=((void **)(((char *)& ao->___length___)+sizeof(int)))[i];
 203         void * copy;
 204         if (gc_createcopy(objptr, &copy))
 205           enqueue(objptr);
 206         ((void **)(((char *)& ao_cpy->___length___)+sizeof(int)))[i]=copy;
 207       }
 208     } else {
 209       int size=pointer[0];
 210       int i;
 211       for(i=1;i<=size;i++) {
 212         int offset=pointer[i];
 213         void * objptr=*((void **)(((int)ptr)+offset));
 214         void * copy;
 215         if (gc_createcopy(objptr, &copy))
 216           enqueue(objptr);
 217         *((void **) (((int)cpy)+offset))=copy;
 218       }
 219     }
 220   }
 221 }
 222
 223 void * curr_heapbase=0;
 224 void * curr_heapptr=0;
 225 void * curr_heapgcpoint=0;
 226 void * curr_heaptop=0;
 227
 228 void * to_heapbase=0;
 229 void * to_heapptr=0;
 230 void * to_heaptop=0;
 231 long lastgcsize=0;
 232
 233 void * tomalloc(int size) {
 234   void * ptr=to_heapptr;
 235   if ((size%4)!=0)
 236     size+=(4-(size%4));
 237   to_heapptr+=size;
 238   return ptr;
 239 }
 240
 241 void * mygcmalloc(struct garbagelist * stackptr, int size) {
 242   void *ptr=curr_heapptr;
 243   if ((size%4)!=0)
 244     size+=(4-(size%4));
 245   curr_heapptr+=size;
 246   if (curr_heapptr>curr_heapgcpoint) {
 247     if (curr_heapbase==0) {
 248       /* Need to allocate base heap */
 249       curr_heapbase=malloc(INITIALHEAPSIZE);
 250       bzero(curr_heapbase, INITIALHEAPSIZE);
 251       curr_heaptop=curr_heapbase+INITIALHEAPSIZE;
 252       curr_heapgcpoint=((char *) curr_heapbase)+GCPOINT(INITIALHEAPSIZE);
 253       curr_heapptr=curr_heapbase+size;
 254
 255       to_heapbase=malloc(INITIALHEAPSIZE);
 256       to_heaptop=to_heapbase+INITIALHEAPSIZE;
 257       to_heapptr=to_heapbase;
 258       return curr_heapbase;
 259     }
 260
 261     /* Grow the to heap if necessary */
 262     {
 263       int curr_heapsize=curr_heaptop-curr_heapbase;
 264       int to_heapsize=to_heaptop-to_heapbase;
 265       int last_heapsize=0;
 266       if (lastgcsize>0) {
 267         last_heapsize=HEAPSIZE(lastgcsize, size);
 268         if ((last_heapsize%4)!=0)
 269           last_heapsize+=(4-(last_heapsize%4));
 270       }
 271       if (curr_heapsize>last_heapsize)
 272         last_heapsize=curr_heapsize;
 273       if (last_heapsize>to_heapsize) {
 274         free(to_heapbase);
 275         to_heapbase=malloc(last_heapsize);
 276         to_heaptop=to_heapbase+last_heapsize;
 277         to_heapptr=to_heapbase;
 278       }
 279     }
 280
 281     /* Do our collection */
 282     collect(stackptr);
 283
 284     /* Update stat on previous gc size */
 285     lastgcsize=to_heapptr-to_heapbase;
 286
 287     /* Flip to/curr heaps */
 288     {
 289       void * tmp=to_heapbase;
 290       to_heapbase=curr_heapbase;
 291       curr_heapbase=tmp;
 292
 293       tmp=to_heaptop;
 294       to_heaptop=curr_heaptop;
 295       curr_heaptop=tmp;
 296
 297       tmp=to_heapptr;
 298       curr_heapptr=to_heapptr+size;
 299       curr_heapgcpoint=((char *) curr_heapbase)+GCPOINT(curr_heaptop-curr_heapbase);
 300       to_heapptr=to_heapbase;
 301
 302       //XXXXX Need check here in case we allocate a really big object
 303       bzero(tmp, curr_heaptop-tmp);
 304       return tmp;
 305     }
 306   } else
 307     return ptr;
 308 }
 309
 310
 311 int gc_createcopy(void * orig, void ** copy_ptr) {
 312   if (orig==0) {
 313     *copy_ptr=NULL;
 314     return 0;
 315   } else {
 316     int type=((int *)orig)[0];
 317     if (type==-1) {
 318       *copy_ptr=((void **)orig)[1];
 319       return 0;
 320     } if (type<NUMCLASSES) {
 321       /* We have a normal object */
 322       int size=classsize[type];
 323       void *newobj=tomalloc(size);
 324       memcpy(newobj, orig, size);
 325       ((int *)orig)[0]=-1;
 326       ((void **)orig)[1]=newobj;
 327       *copy_ptr=newobj;
 328       return 1;
 329     } else {
 330       /* We have an array */
 331       struct ArrayObject *ao=(struct ArrayObject *)orig;
 332       int elementsize=classsize[type];
 333       int length=ao->___length___;
 334       int size=sizeof(struct ArrayObject)+length*elementsize;
 335       void *newobj=tomalloc(size);
 336       memcpy(newobj, orig, size);
 337       ((int *)orig)[0]=-1;
 338       ((void **)orig)[1]=newobj;
 339       *copy_ptr=newobj;
 340       return 1;
 341     }
 342   }
 343 }