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       pthread_mutex_unlock(&threadtable);
  88       pthread_mutex_unlock(&gclistlock);
  89       break; /* Have all other threads stopped */
  90     }
  91     pthread_mutex_unlock(&threadtable);
  92     pthread_cond_wait(&gccond, &gclistlock);
  93     pthread_mutex_unlock(&gclistlock);
  94   }
  95 #endif
  96
  97   if (head==NULL) {
  98     headindex=0;
  99     tailindex=0;
 100     head=tail=malloc(sizeof(struct pointerblock));
 101   }
 102   /* Check current stack */
 103 #ifdef THREADS
 104  {
 105    struct listitem *listptr=list;
 106    while(stackptr!=NULL) {
 107 #endif
 108
 109   while(stackptr!=NULL) {
 110     int i;
 111     for(i=0;i<stackptr->size;i++) {
 112       void * orig=stackptr->array[i];
 113       void * copy;
 114       if (gc_createcopy(orig,&copy))
 115         enqueue(orig);
 116       stackptr->array[i]=copy;
 117     }
 118     stackptr=stackptr->next;
 119   }
 120 #ifdef THREADS
 121   /* Go to next thread */
 122   if (listptr!=NULL) {
 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 #endif
 264 }
 265
 266 void * curr_heapbase=0;
 267 void * curr_heapptr=0;
 268 void * curr_heapgcpoint=0;
 269 void * curr_heaptop=0;
 270
 271 void * to_heapbase=0;
 272 void * to_heapptr=0;
 273 void * to_heaptop=0;
 274 long lastgcsize=0;
 275
 276 void * tomalloc(int size) {
 277   void * ptr=to_heapptr;
 278   if ((size%4)!=0)
 279     size+=(4-(size%4));
 280   to_heapptr+=size;
 281   return ptr;
 282 }
 283
 284 #ifdef THREADS
 285
 286 void checkcollect(void * ptr) {
 287   if (needtocollect) {
 288     struct listitem * tmp=stopforgc((struct garbagelist *)ptr);
 289     pthread_mutex_lock(&gclock);
 290     restartaftergc(tmp);
 291     pthread_mutex_unlock(&gclock);
 292   }
 293 }
 294
 295 struct listitem * stopforgc(struct garbagelist * ptr) {
 296   struct listitem * litem=malloc(sizeof(struct listitem));
 297   litem->stackptr=ptr;
 298   litem->prev=NULL;
 299   pthread_mutex_lock(&gclistlock);
 300   litem->next=list;
 301   if(list!=NULL)
 302     list->prev=litem;
 303   list=litem;
 304   listcount++;
 305   pthread_cond_signal(&gccond);
 306   pthread_mutex_unlock(&gclistlock);
 307   return litem;
 308 }
 309
 310 void restartaftergc(struct listitem * litem) {
 311   pthread_mutex_lock(&gclistlock);
 312   if (litem->prev==NULL) {
 313     list=litem->next;
 314   } else {
 315     litem->prev->next=litem->next;
 316   }
 317   if (litem->next!=NULL) {
 318     litem->next->prev=litem->prev;
 319   }
 320   listcount--;
 321   pthread_mutex_unlock(&gclistlock);
 322   free(litem);
 323 }
 324 #endif
 325
 326 void * mygcmalloc(struct garbagelist * stackptr, int size) {
 327   void *ptr;
 328 #ifdef THREADS
 329   if (pthread_mutex_trylock(&gclock)!=0) {
 330     struct listitem *tmp=stopforgc(stackptr);
 331     pthread_mutex_lock(&gclock);
 332     restartaftergc(tmp);
 333   }
 334 #endif
 335   ptr=curr_heapptr;
 336   if ((size%4)!=0)
 337     size+=(4-(size%4));
 338   curr_heapptr+=size;
 339   if (curr_heapptr>curr_heapgcpoint) {
 340     if (curr_heapbase==0) {
 341       /* Need to allocate base heap */
 342       curr_heapbase=malloc(INITIALHEAPSIZE);
 343       bzero(curr_heapbase, INITIALHEAPSIZE);
 344       curr_heaptop=curr_heapbase+INITIALHEAPSIZE;
 345       curr_heapgcpoint=((char *) curr_heapbase)+GCPOINT(INITIALHEAPSIZE);
 346       curr_heapptr=curr_heapbase+size;
 347
 348       to_heapbase=malloc(INITIALHEAPSIZE);
 349       to_heaptop=to_heapbase+INITIALHEAPSIZE;
 350       to_heapptr=to_heapbase;
 351       ptr=curr_heapbase;
 352 #ifdef THREADS
 353       pthread_mutex_unlock(&gclock);
 354 #endif
 355       return ptr;
 356     }
 357
 358     /* Grow the to heap if necessary */
 359     {
 360       int curr_heapsize=curr_heaptop-curr_heapbase;
 361       int to_heapsize=to_heaptop-to_heapbase;
 362       int last_heapsize=0;
 363       if (lastgcsize>0) {
 364         last_heapsize=HEAPSIZE(lastgcsize, size);
 365         if ((last_heapsize%4)!=0)
 366           last_heapsize+=(4-(last_heapsize%4));
 367       }
 368       if (curr_heapsize>last_heapsize)
 369         last_heapsize=curr_heapsize;
 370       if (last_heapsize>to_heapsize) {
 371         free(to_heapbase);
 372         to_heapbase=malloc(last_heapsize);
 373         to_heaptop=to_heapbase+last_heapsize;
 374         to_heapptr=to_heapbase;
 375       }
 376     }
 377
 378     /* Do our collection */
 379     collect(stackptr);
 380
 381     /* Update stat on previous gc size */
 382     lastgcsize=(to_heapptr-to_heapbase)+size;
 383
 384     /* Flip to/curr heaps */
 385     {
 386       void * tmp=to_heapbase;
 387       to_heapbase=curr_heapbase;
 388       curr_heapbase=tmp;
 389
 390       tmp=to_heaptop;
 391       to_heaptop=curr_heaptop;
 392       curr_heaptop=tmp;
 393
 394       tmp=to_heapptr;
 395       curr_heapptr=to_heapptr+size;
 396       curr_heapgcpoint=((char *) curr_heapbase)+GCPOINT(curr_heaptop-curr_heapbase);
 397       to_heapptr=to_heapbase;
 398
 399       /* Not enough room :(, redo gc */
 400       if (curr_heapptr>curr_heapgcpoint) {
 401 #ifdef THREADS
 402         pthread_mutex_unlock(&gclock);
 403 #endif
 404         return mygcmalloc(stackptr, size);
 405       }
 406
 407       bzero(tmp, curr_heaptop-tmp);
 408 #ifdef THREADS
 409       pthread_mutex_unlock(&gclock);
 410 #endif
 411       return tmp;
 412     }
 413   } else {
 414 #ifdef THREADS
 415     pthread_mutex_unlock(&gclock);
 416 #endif
 417     return ptr;
 418   }
 419 }
 420
 421
 422 int gc_createcopy(void * orig, void ** copy_ptr) {
 423   if (orig==0) {
 424     *copy_ptr=NULL;
 425     return 0;
 426   } else {
 427     int type=((int *)orig)[0];
 428     if (type==-1) {
 429       *copy_ptr=((void **)orig)[1];
 430       return 0;
 431     } if (type<NUMCLASSES) {
 432       /* We have a normal object */
 433       int size=classsize[type];
 434       void *newobj=tomalloc(size);
 435       memcpy(newobj, orig, size);
 436       ((int *)orig)[0]=-1;
 437       ((void **)orig)[1]=newobj;
 438       *copy_ptr=newobj;
 439       return 1;
 440     } else {
 441       /* We have an array */
 442       struct ArrayObject *ao=(struct ArrayObject *)orig;
 443       int elementsize=classsize[type];
 444       int length=ao->___length___;
 445       int size=sizeof(struct ArrayObject)+length*elementsize;
 446       void *newobj=tomalloc(size);
 447       memcpy(newobj, orig, size);
 448       ((int *)orig)[0]=-1;
 449       ((void **)orig)[1]=newobj;
 450       *copy_ptr=newobj;
 451       return 1;
 452     }
 453   }
 454 }