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