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