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