Programming Languages Research Group: Git - IRC.git/blob

   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 genhashtable * activetasks;
  25 extern struct parameterwrapper * objectqueues[NUMCLASSES];
  26 extern struct genhashtable * failedtasks;
  27 extern struct taskparamdescriptor *currtpd;
  28 extern struct RuntimeHash *forward;
  29 extern struct RuntimeHash *reverse;
  30 extern struct RuntimeHash *fdtoobject;
  31 #endif
  32
  33 #ifdef THREADS
  34 int needtocollect=0;
  35 struct listitem * list=NULL;
  36 int listcount=0;
  37 #endif
  38
  39 struct pointerblock {
  40   void * ptrs[NUMPTRS];
  41   struct pointerblock *next;
  42 };
  43
  44 struct pointerblock *head=NULL;
  45 int headindex=0;
  46 struct pointerblock *tail=NULL;
  47 int tailindex=0;
  48 struct pointerblock *spare=NULL;
  49
  50 void enqueue(void *ptr) {
  51   if (headindex==NUMPTRS) {
  52     struct pointerblock * tmp;
  53     if (spare!=NULL) {
  54       tmp=spare;
  55       spare=NULL;
  56     } else
  57       tmp=malloc(sizeof(struct pointerblock));
  58     head->next=tmp;
  59     head=tmp;
  60     headindex=0;
  61   }
  62   head->ptrs[headindex++]=ptr;
  63 }
  64
  65 void * dequeue() {
  66   if (tailindex==NUMPTRS) {
  67     struct pointerblock *tmp=tail;
  68     tail=tail->next;
  69     tailindex=0;
  70     if (spare!=NULL)
  71       free(tmp);
  72     else
  73       spare=tmp;
  74   }
  75   return tail->ptrs[tailindex++];
  76 }
  77
  78 int moreItems() {
  79   if ((head==tail)&&(tailindex==headindex))
  80     return 0;
  81   return 1;
  82 }
  83
  84 #ifdef TASK
  85 struct pointerblock *taghead=NULL;
  86 int tagindex=0;
  87
  88 void enqueuetag(struct ___TagDescriptor___ *ptr) {
  89   if (tagindex==NUMPTRS) {
  90     struct pointerblock * tmp=malloc(sizeof(struct pointerblock));
  91     tmp->next=taghead;
  92     taghead=tmp;
  93     tagindex=0;
  94   }
  95   taghead->ptrs[tagindex++]=ptr;
  96 }
  97 #endif
  98
  99
 100 void collect(struct garbagelist * stackptr) {
 101 #ifdef THREADS
 102   needtocollect=1;
 103   pthread_mutex_lock(&gclistlock);
 104   while(1) {
 105     if ((listcount+1)==threadcount) {
 106       break; /* Have all other threads stopped */
 107     }
 108     pthread_cond_wait(&gccond, &gclistlock);
 109   }
 110 #endif
 111
 112   if (head==NULL) {
 113     headindex=0;
 114     tailindex=0;
 115     head=tail=malloc(sizeof(struct pointerblock));
 116   }
 117
 118 #ifdef TASK
 119   if (taghead==NULL) {
 120     tagindex=0;
 121     taghead=malloc(sizeof(struct pointerblock));
 122     taghead->next=NULL;
 123   }
 124 #endif
 125
 126   /* Check current stack */
 127 #ifdef THREADS
 128  {
 129    struct listitem *listptr=list;
 130    while(1) {
 131 #endif
 132
 133   while(stackptr!=NULL) {
 134     int i;
 135     for(i=0;i<stackptr->size;i++) {
 136       void * orig=stackptr->array[i];
 137       void * copy;
 138       if (gc_createcopy(orig,&copy))
 139         enqueue(orig);
 140       stackptr->array[i]=copy;
 141     }
 142     stackptr=stackptr->next;
 143   }
 144 #ifdef THREADS
 145   /* Go to next thread */
 146   if (listptr!=NULL) {
 147     void * orig=listptr->locklist;
 148     void * copy;
 149     if (gc_createcopy(orig,&copy))
 150       enqueue(orig);
 151     listptr->locklist=copy;
 152     stackptr=listptr->stackptr;
 153     listptr=listptr->next;
 154   } else
 155     break;
 156    }
 157  }
 158 #endif
 159
 160 #ifdef TASK
 161   {
 162     /* Update objectsets */
 163     int i;
 164     for(i=0;i<NUMCLASSES;i++) {
 165       struct parameterwrapper * p=objectqueues[i];
 166       while(p!=NULL) {
 167         struct RuntimeHash * set=p->objectset;
 168         struct RuntimeNode * ptr=set->listhead;
 169         while(ptr!=NULL) {
 170           void *orig=(void *)ptr->key;
 171           void *copy;
 172           if (gc_createcopy(orig, &copy))
 173             enqueue(orig);
 174           ptr->key=(int)copy;
 175
 176           ptr=ptr->lnext;
 177         }
 178         RuntimeHashrehash(set); /* Rehash the table */
 179         p=p->next;
 180       }
 181     }
 182   }
 183
 184   if (forward!=NULL) {
 185     struct RuntimeNode * ptr=forward->listhead;
 186     while(ptr!=NULL) {
 187       void * orig=(void *)ptr->key;
 188       void *copy;
 189       if (gc_createcopy(orig, &copy))
 190         enqueue(orig);
 191       ptr->key=(int)copy;
 192
 193       ptr=ptr->lnext;
 194     }
 195     RuntimeHashrehash(forward); /* Rehash the table */
 196   }
 197
 198   if (reverse!=NULL) {
 199     struct RuntimeNode * ptr=reverse->listhead;
 200     while(ptr!=NULL) {
 201       void *orig=(void *)ptr->data;
 202       void *copy;
 203       if (gc_createcopy(orig, &copy))
 204         enqueue(orig);
 205       ptr->data=(int)copy;
 206
 207       ptr=ptr->lnext;
 208     }
 209   }
 210
 211   {
 212     struct RuntimeNode * ptr=fdtoobject->listhead;
 213     while(ptr!=NULL) {
 214       void *orig=(void *)ptr->data;
 215       void *copy;
 216       if (gc_createcopy(orig, &copy))
 217         enqueue(orig);
 218       ptr->data=(int)copy;
 219
 220       ptr=ptr->lnext;
 221     }
 222   }
 223
 224   {
 225     /* Update current task descriptor */
 226     int i;
 227     for(i=0;i<currtpd->numParameters;i++) {
 228       void *orig=currtpd->parameterArray[i];
 229       void *copy;
 230       if (gc_createcopy(orig, &copy))
 231         enqueue(orig);
 232       currtpd->parameterArray[i]=copy;
 233     }
 234
 235   }
 236
 237     /* Update active tasks */
 238   {
 239     struct genpointerlist * ptr=activetasks->list;
 240     while(ptr!=NULL) {
 241       struct taskparamdescriptor *tpd=ptr->src;
 242       int i;
 243       for(i=0;i<tpd->numParameters;i++) {
 244         void * orig=tpd->parameterArray[i];
 245         void * copy;
 246         if (gc_createcopy(orig, &copy))
 247           enqueue(orig);
 248         tpd->parameterArray[i]=copy;
 249       }
 250       ptr=ptr->inext;
 251     }
 252     genrehash(activetasks);
 253   }
 254
 255     /* Update failed tasks */
 256   {
 257     struct genpointerlist * ptr=failedtasks->list;
 258     while(ptr!=NULL) {
 259       struct taskparamdescriptor *tpd=ptr->src;
 260       int i;
 261       for(i=0;i<tpd->numParameters;i++) {
 262         void * orig=tpd->parameterArray[i];
 263         void * copy;
 264         if (gc_createcopy(orig, &copy))
 265           enqueue(orig);
 266         tpd->parameterArray[i]=copy;
 267       }
 268       ptr=ptr->inext;
 269     }
 270     genrehash(failedtasks);
 271   }
 272 #endif
 273
 274   while(moreItems()) {
 275     void * ptr=dequeue();
 276     void *cpy=((void **)ptr)[1];
 277     int type=((int *)cpy)[0];
 278     int * pointer;
 279 #ifdef TASK
 280     if(type==TAGTYPE) {
 281       /* Enqueue Tag */
 282       /* Nothing is inside */
 283       enqueuetag(ptr);
 284       continue;
 285     }
 286 #endif
 287     pointer=pointerarray[type];
 288     if (pointer==0) {
 289       /* Array of primitives */
 290       /* Do nothing */
 291     } else if (((int)pointer)==1) {
 292       /* Array of pointers */
 293       struct ArrayObject *ao=(struct ArrayObject *) ptr;
 294       struct ArrayObject *ao_cpy=(struct ArrayObject *) cpy;
 295       int length=ao->___length___;
 296       int i;
 297       for(i=0;i<length;i++) {
 298         void *objptr=((void **)(((char *)& ao->___length___)+sizeof(int)))[i];
 299         void * copy;
 300         if (gc_createcopy(objptr, &copy))
 301           enqueue(objptr);
 302         ((void **)(((char *)& ao_cpy->___length___)+sizeof(int)))[i]=copy;
 303       }
 304     } else {
 305       int size=pointer[0];
 306       int i;
 307       for(i=1;i<=size;i++) {
 308         int offset=pointer[i];
 309         void * objptr=*((void **)(((int)ptr)+offset));
 310         void * copy;
 311         if (gc_createcopy(objptr, &copy))
 312           enqueue(objptr);
 313         *((void **) (((int)cpy)+offset))=copy;
 314       }
 315     }
 316   }
 317 #ifdef TASK
 318   fixtags();
 319 #endif
 320
 321 #ifdef THREADS
 322   needtocollect=0;
 323   pthread_mutex_unlock(&gclistlock);
 324 #endif
 325 }
 326
 327 #ifdef TASK
 328 void fixtags() {
 329   while(taghead!=NULL) {
 330     int i;
 331     struct pointerblock *tmp=taghead->next;
 332     for(i=0;i<tagindex;i++) {
 333       struct ___TagDescriptor___ *tagd=taghead->ptrs[i];
 334       struct ___Object___ *obj=tagd->flagptr;
 335       struct ___TagDescriptor___ *copy=((struct ___TagDescriptor___**)tagd)[1];
 336       if (obj->type==-1) {
 337         /* Single object case */
 338         copy->flagptr=((struct ___Object___**)obj)[1];
 339       } else if (obj->type==OBJECTARRAYTYPE) {
 340         /* Array case */
 341         struct ArrayObject *ao=(struct ArrayObject *) obj;
 342         int livecount=0;
 343         int j;
 344         int k=0;
 345         struct ArrayObject *aonew;
 346
 347         /* Count live objects */
 348         for(j=0;j<ao->___cachedCode___;j++) {
 349           struct ___Object___ * tobj=ARRAYGET(ao, struct ___Object___ *, j);
 350           if (tobj->type==-1)
 351             livecount++;
 352         }
 353
 354         livecount=((livecount-1)/OBJECTARRAYINTERVAL+1)*OBJECTARRAYINTERVAL;
 355         aonew=(struct ArrayObject *) tomalloc(sizeof(struct ArrayObject)+sizeof(struct ___Object___*)*livecount);
 356         aonew->type=OBJECTARRAYTYPE;
 357         aonew->___length___=livecount;
 358         copy->flagptr=aonew;
 359         for(j=0;j<ao->___cachedCode___;j++) {
 360           struct ___Object___ * tobj=ARRAYGET(ao, struct ___Object___ *, j);
 361           if (tobj->type==-1) {
 362             struct ___Object___ * tobjcpy=((struct ___Object___**)tobj)[1];
 363             ARRAYSET(aonew, struct ___Object___*, k++,tobjcpy);
 364           }
 365         }
 366         aonew->___cachedCode___=k;
 367
 368       } else {
 369         /* No object live anymore */
 370         copy->flagptr=NULL;
 371       }
 372     }
 373     free(taghead);
 374     taghead=tmp;
 375     tagindex=NUMPTRS;
 376   }
 377 }
 378 #endif
 379
 380 void * curr_heapbase=0;
 381 void * curr_heapptr=0;
 382 void * curr_heapgcpoint=0;
 383 void * curr_heaptop=0;
 384
 385 void * to_heapbase=0;
 386 void * to_heapptr=0;
 387 void * to_heaptop=0;
 388 long lastgcsize=0;
 389
 390 void * tomalloc(int size) {
 391   void * ptr=to_heapptr;
 392   if ((size%4)!=0)
 393     size+=(4-(size%4));
 394   to_heapptr+=size;
 395   return ptr;
 396 }
 397
 398 #ifdef THREADS
 399
 400 void checkcollect(void * ptr) {
 401   if (needtocollect) {
 402     struct listitem * tmp=stopforgc((struct garbagelist *)ptr);
 403     pthread_mutex_lock(&gclock); // Wait for GC
 404     restartaftergc(tmp);
 405     pthread_mutex_unlock(&gclock);
 406
 407   }
 408 }
 409
 410 struct listitem * stopforgc(struct garbagelist * ptr) {
 411   struct listitem * litem=malloc(sizeof(struct listitem));
 412   litem->stackptr=ptr;
 413   litem->locklist=pthread_getspecific(threadlocks);
 414   litem->prev=NULL;
 415   pthread_mutex_lock(&gclistlock);
 416   litem->next=list;
 417   if(list!=NULL)
 418     list->prev=litem;
 419   list=litem;
 420   listcount++;
 421   pthread_cond_signal(&gccond);
 422   pthread_mutex_unlock(&gclistlock);
 423   return litem;
 424 }
 425
 426 void restartaftergc(struct listitem * litem) {
 427   pthread_mutex_lock(&gclistlock);
 428   pthread_setspecific(threadlocks, litem->locklist);
 429   if (litem->prev==NULL) {
 430     list=litem->next;
 431   } else {
 432     litem->prev->next=litem->next;
 433   }
 434   if (litem->next!=NULL) {
 435     litem->next->prev=litem->prev;
 436   }
 437   listcount--;
 438   pthread_mutex_unlock(&gclistlock);
 439   free(litem);
 440 }
 441 #endif
 442
 443 void * mygcmalloc(struct garbagelist * stackptr, int size) {
 444   void *ptr;
 445 #ifdef THREADS
 446   if (pthread_mutex_trylock(&gclock)!=0) {
 447     struct listitem *tmp=stopforgc(stackptr);
 448     pthread_mutex_lock(&gclock);
 449     restartaftergc(tmp);
 450   }
 451 #endif
 452   ptr=curr_heapptr;
 453   if ((size%4)!=0)
 454     size+=(4-(size%4));
 455   curr_heapptr+=size;
 456   if (curr_heapptr>curr_heapgcpoint) {
 457     if (curr_heapbase==0) {
 458       /* Need to allocate base heap */
 459       curr_heapbase=malloc(INITIALHEAPSIZE);
 460       bzero(curr_heapbase, INITIALHEAPSIZE);
 461       curr_heaptop=curr_heapbase+INITIALHEAPSIZE;
 462       curr_heapgcpoint=((char *) curr_heapbase)+GCPOINT(INITIALHEAPSIZE);
 463       curr_heapptr=curr_heapbase+size;
 464
 465       to_heapbase=malloc(INITIALHEAPSIZE);
 466       to_heaptop=to_heapbase+INITIALHEAPSIZE;
 467       to_heapptr=to_heapbase;
 468       ptr=curr_heapbase;
 469 #ifdef THREADS
 470       pthread_mutex_unlock(&gclock);
 471 #endif
 472       return ptr;
 473     }
 474
 475     /* Grow the to heap if necessary */
 476     {
 477       int curr_heapsize=curr_heaptop-curr_heapbase;
 478       int to_heapsize=to_heaptop-to_heapbase;
 479       int last_heapsize=0;
 480       if (lastgcsize>0) {
 481         last_heapsize=HEAPSIZE(lastgcsize, size);
 482         if ((last_heapsize%4)!=0)
 483           last_heapsize+=(4-(last_heapsize%4));
 484       }
 485       if (curr_heapsize>last_heapsize)
 486         last_heapsize=curr_heapsize;
 487       if (last_heapsize>to_heapsize) {
 488         free(to_heapbase);
 489         to_heapbase=malloc(last_heapsize);
 490         to_heaptop=to_heapbase+last_heapsize;
 491         to_heapptr=to_heapbase;
 492       }
 493     }
 494
 495     /* Do our collection */
 496     collect(stackptr);
 497
 498     /* Update stat on previous gc size */
 499     lastgcsize=(to_heapptr-to_heapbase)+size;
 500
 501     /* Flip to/curr heaps */
 502     {
 503       void * tmp=to_heapbase;
 504       to_heapbase=curr_heapbase;
 505       curr_heapbase=tmp;
 506
 507       tmp=to_heaptop;
 508       to_heaptop=curr_heaptop;
 509       curr_heaptop=tmp;
 510
 511       tmp=to_heapptr;
 512       curr_heapptr=to_heapptr+size;
 513       curr_heapgcpoint=((char *) curr_heapbase)+GCPOINT(curr_heaptop-curr_heapbase);
 514       to_heapptr=to_heapbase;
 515
 516       /* Not enough room :(, redo gc */
 517       if (curr_heapptr>curr_heapgcpoint) {
 518 #ifdef THREADS
 519         pthread_mutex_unlock(&gclock);
 520 #endif
 521         return mygcmalloc(stackptr, size);
 522       }
 523
 524       bzero(tmp, curr_heaptop-tmp);
 525 #ifdef THREADS
 526       pthread_mutex_unlock(&gclock);
 527 #endif
 528       return tmp;
 529     }
 530   } else {
 531 #ifdef THREADS
 532     pthread_mutex_unlock(&gclock);
 533 #endif
 534     return ptr;
 535   }
 536 }
 537
 538
 539 int gc_createcopy(void * orig, void ** copy_ptr) {
 540   if (orig==0) {
 541     *copy_ptr=NULL;
 542     return 0;
 543   } else {
 544     int type=((int *)orig)[0];
 545     if (type==-1) {
 546       *copy_ptr=((void **)orig)[1];
 547       return 0;
 548     } if (type<NUMCLASSES) {
 549       /* We have a normal object */
 550       int size=classsize[type];
 551       void *newobj=tomalloc(size);
 552       memcpy(newobj, orig, size);
 553       ((int *)orig)[0]=-1;
 554       ((void **)orig)[1]=newobj;
 555       *copy_ptr=newobj;
 556       return 1;
 557     } else {
 558       /* We have an array */
 559       struct ArrayObject *ao=(struct ArrayObject *)orig;
 560       int elementsize=classsize[type];
 561       int length=ao->___length___;
 562       int size=sizeof(struct ArrayObject)+length*elementsize;
 563       void *newobj=tomalloc(size);
 564       memcpy(newobj, orig, size);
 565       ((int *)orig)[0]=-1;
 566       ((void **)orig)[1]=newobj;
 567       *copy_ptr=newobj;
 568       return 1;
 569     }
 570   }
 571 }