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