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