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