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       struct taskparamdescriptor *tpd=ptr->src;
 216       void *orig;
 217       void *copy;
 218       int i;
 219       for(i=0;i<tpd->numParameters;i++) {
 220         orig=tpd->parameterArray[i];
 221         if (gc_createcopy(orig, &copy))
 222           enqueue(orig);
 223         tpd->parameterArray[i]=copy;
 224       }
 225       ptr=ptr->inext;
 226     }
 227     genrehash(failedtasks);
 228   }
 229 #endif
 230
 231   while(moreItems()) {
 232     void * ptr=dequeue();
 233     void *cpy=((void **)ptr)[1];
 234     int type=((int *)cpy)[0];
 235     int * pointer=pointerarray[type];
 236     if (pointer==0) {
 237       /* Array of primitives */
 238       /* Do nothing */
 239     } else if (((int)pointer)==1) {
 240       /* Array of pointers */
 241       struct ArrayObject *ao=(struct ArrayObject *) ptr;
 242       struct ArrayObject *ao_cpy=(struct ArrayObject *) cpy;
 243       int length=ao->___length___;
 244       int i;
 245       for(i=0;i<length;i++) {
 246         void *objptr=((void **)(((char *)& ao->___length___)+sizeof(int)))[i];
 247         void * copy;
 248         if (gc_createcopy(objptr, &copy))
 249           enqueue(objptr);
 250         ((void **)(((char *)& ao_cpy->___length___)+sizeof(int)))[i]=copy;
 251       }
 252     } else {
 253       int size=pointer[0];
 254       int i;
 255       for(i=1;i<=size;i++) {
 256         int offset=pointer[i];
 257         void * objptr=*((void **)(((int)ptr)+offset));
 258         void * copy;
 259         if (gc_createcopy(objptr, &copy))
 260           enqueue(objptr);
 261         *((void **) (((int)cpy)+offset))=copy;
 262       }
 263     }
 264   }
 265 #ifdef THREADS
 266   needtocollect=0;
 267   pthread_mutex_unlock(&gclistlock);
 268 #endif
 269 }
 270
 271 void * curr_heapbase=0;
 272 void * curr_heapptr=0;
 273 void * curr_heapgcpoint=0;
 274 void * curr_heaptop=0;
 275
 276 void * to_heapbase=0;
 277 void * to_heapptr=0;
 278 void * to_heaptop=0;
 279 long lastgcsize=0;
 280
 281 void * tomalloc(int size) {
 282   void * ptr=to_heapptr;
 283   if ((size%4)!=0)
 284     size+=(4-(size%4));
 285   to_heapptr+=size;
 286   return ptr;
 287 }
 288
 289 #ifdef THREADS
 290
 291 void checkcollect(void * ptr) {
 292   if (needtocollect) {
 293     struct listitem * tmp=stopforgc((struct garbagelist *)ptr);
 294     pthread_mutex_lock(&gclock); // Wait for GC
 295     restartaftergc(tmp);
 296     pthread_mutex_unlock(&gclock);
 297
 298   }
 299 }
 300
 301 struct listitem * stopforgc(struct garbagelist * ptr) {
 302   struct listitem * litem=malloc(sizeof(struct listitem));
 303   litem->stackptr=ptr;
 304   litem->locklist=pthread_getspecific(threadlocks);
 305   litem->prev=NULL;
 306   pthread_mutex_lock(&gclistlock);
 307   litem->next=list;
 308   if(list!=NULL)
 309     list->prev=litem;
 310   list=litem;
 311   listcount++;
 312   pthread_cond_signal(&gccond);
 313   pthread_mutex_unlock(&gclistlock);
 314   return litem;
 315 }
 316
 317 void restartaftergc(struct listitem * litem) {
 318   pthread_mutex_lock(&gclistlock);
 319   pthread_setspecific(threadlocks, litem->locklist);
 320   if (litem->prev==NULL) {
 321     list=litem->next;
 322   } else {
 323     litem->prev->next=litem->next;
 324   }
 325   if (litem->next!=NULL) {
 326     litem->next->prev=litem->prev;
 327   }
 328   listcount--;
 329   pthread_mutex_unlock(&gclistlock);
 330   free(litem);
 331 }
 332 #endif
 333
 334 void * mygcmalloc(struct garbagelist * stackptr, int size) {
 335   void *ptr;
 336 #ifdef THREADS
 337   if (pthread_mutex_trylock(&gclock)!=0) {
 338     struct listitem *tmp=stopforgc(stackptr);
 339     pthread_mutex_lock(&gclock);
 340     restartaftergc(tmp);
 341   }
 342 #endif
 343   ptr=curr_heapptr;
 344   if ((size%4)!=0)
 345     size+=(4-(size%4));
 346   curr_heapptr+=size;
 347   if (curr_heapptr>curr_heapgcpoint) {
 348     if (curr_heapbase==0) {
 349       /* Need to allocate base heap */
 350       curr_heapbase=malloc(INITIALHEAPSIZE);
 351       bzero(curr_heapbase, INITIALHEAPSIZE);
 352       curr_heaptop=curr_heapbase+INITIALHEAPSIZE;
 353       curr_heapgcpoint=((char *) curr_heapbase)+GCPOINT(INITIALHEAPSIZE);
 354       curr_heapptr=curr_heapbase+size;
 355
 356       to_heapbase=malloc(INITIALHEAPSIZE);
 357       to_heaptop=to_heapbase+INITIALHEAPSIZE;
 358       to_heapptr=to_heapbase;
 359       ptr=curr_heapbase;
 360 #ifdef THREADS
 361       pthread_mutex_unlock(&gclock);
 362 #endif
 363       return ptr;
 364     }
 365
 366     /* Grow the to heap if necessary */
 367     {
 368       int curr_heapsize=curr_heaptop-curr_heapbase;
 369       int to_heapsize=to_heaptop-to_heapbase;
 370       int last_heapsize=0;
 371       if (lastgcsize>0) {
 372         last_heapsize=HEAPSIZE(lastgcsize, size);
 373         if ((last_heapsize%4)!=0)
 374           last_heapsize+=(4-(last_heapsize%4));
 375       }
 376       if (curr_heapsize>last_heapsize)
 377         last_heapsize=curr_heapsize;
 378       if (last_heapsize>to_heapsize) {
 379         free(to_heapbase);
 380         to_heapbase=malloc(last_heapsize);
 381         to_heaptop=to_heapbase+last_heapsize;
 382         to_heapptr=to_heapbase;
 383       }
 384     }
 385
 386     /* Do our collection */
 387     collect(stackptr);
 388
 389     /* Update stat on previous gc size */
 390     lastgcsize=(to_heapptr-to_heapbase)+size;
 391
 392     /* Flip to/curr heaps */
 393     {
 394       void * tmp=to_heapbase;
 395       to_heapbase=curr_heapbase;
 396       curr_heapbase=tmp;
 397
 398       tmp=to_heaptop;
 399       to_heaptop=curr_heaptop;
 400       curr_heaptop=tmp;
 401
 402       tmp=to_heapptr;
 403       curr_heapptr=to_heapptr+size;
 404       curr_heapgcpoint=((char *) curr_heapbase)+GCPOINT(curr_heaptop-curr_heapbase);
 405       to_heapptr=to_heapbase;
 406
 407       /* Not enough room :(, redo gc */
 408       if (curr_heapptr>curr_heapgcpoint) {
 409 #ifdef THREADS
 410         pthread_mutex_unlock(&gclock);
 411 #endif
 412         return mygcmalloc(stackptr, size);
 413       }
 414
 415       bzero(tmp, curr_heaptop-tmp);
 416 #ifdef THREADS
 417       pthread_mutex_unlock(&gclock);
 418 #endif
 419       return tmp;
 420     }
 421   } else {
 422 #ifdef THREADS
 423     pthread_mutex_unlock(&gclock);
 424 #endif
 425     return ptr;
 426   }
 427 }
 428
 429
 430 int gc_createcopy(void * orig, void ** copy_ptr) {
 431   if (orig==0) {
 432     *copy_ptr=NULL;
 433     return 0;
 434   } else {
 435     int type=((int *)orig)[0];
 436     if (type==-1) {
 437       *copy_ptr=((void **)orig)[1];
 438       return 0;
 439     } if (type<NUMCLASSES) {
 440       /* We have a normal object */
 441       int size=classsize[type];
 442       void *newobj=tomalloc(size);
 443       memcpy(newobj, orig, size);
 444       ((int *)orig)[0]=-1;
 445       ((void **)orig)[1]=newobj;
 446       *copy_ptr=newobj;
 447       return 1;
 448     } else {
 449       /* We have an array */
 450       struct ArrayObject *ao=(struct ArrayObject *)orig;
 451       int elementsize=classsize[type];
 452       int length=ao->___length___;
 453       int size=sizeof(struct ArrayObject)+length*elementsize;
 454       void *newobj=tomalloc(size);
 455       memcpy(newobj, orig, size);
 456       ((int *)orig)[0]=-1;
 457       ((void **)orig)[1]=newobj;
 458       *copy_ptr=newobj;
 459       return 1;
 460     }
 461   }
 462 }