X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FRuntime%2Fgarbage.c;h=e43dd3cb3e067e0f3cf025cc56530f096b4c3f8c;hb=81520bb20d5e1ceb2bb7037da6a4cb6a9c9eb033;hp=e86f2c1b6d1a7f259b7f12fbf19bb5809c814949;hpb=09c3fed9d2f57fe2a4a1e66e72de9d4791e761c7;p=IRC.git diff --git a/Robust/src/Runtime/garbage.c b/Robust/src/Runtime/garbage.c index e86f2c1b..e43dd3cb 100644 --- a/Robust/src/Runtime/garbage.c +++ b/Robust/src/Runtime/garbage.c @@ -3,37 +3,100 @@ #include "structdefs.h" #include "Queue.h" #include "SimpleHash.h" +#include "chash.h" #include "GenericHashtable.h" #include -#ifdef THREADS +#if defined(THREADS) || defined(DSTM) || defined(STM) #include "thread.h" #endif + #ifdef DMALLOC #include "dmalloc.h" #endif +#ifdef DSTM +#include "dstm.h" +#endif +#ifdef STM +#include "tm.h" +#endif +#ifdef DELAYCOMP +#include "delaycomp.h" +#endif #define NUMPTRS 100 -#define INITIALHEAPSIZE 10*1024 -#define GCPOINT(x) ((int)((x)*0.9)) +#define INITIALHEAPSIZE 256*1024*1024L +#define GCPOINT(x) ((INTPTR)((x)*0.99)) /* This define takes in how full the heap is initially and returns a new heap size to use */ -#define HEAPSIZE(x,y) (((int)((x)/0.6))+y) +#define HEAPSIZE(x,y) ((INTPTR)(x+y))*2 #ifdef TASK extern struct genhashtable * activetasks; +#ifndef MULTICORE extern struct parameterwrapper * objectqueues[NUMCLASSES]; +#endif extern struct genhashtable * failedtasks; extern struct taskparamdescriptor *currtpd; -extern struct RuntimeHash *forward; -extern struct RuntimeHash *reverse; +extern struct ctable *forward; +extern struct ctable *reverse; extern struct RuntimeHash *fdtoobject; #endif -#ifdef THREADS +#ifdef GARBAGESTATS +#define MAXSTATS 500 +long garbagearray[MAXSTATS]; +#endif + +#if defined(THREADS) || defined(DSTM) || defined(STM) int needtocollect=0; struct listitem * list=NULL; int listcount=0; +#ifndef MAC +__thread struct listitem litem; +#endif +#endif + +//Need to check if pointers are transaction pointers +//this also catches the special flag value of 1 for local copies +#ifdef DSTM +#define ENQUEUE(orig, dst) \ + if ((!(((unsigned int)orig)&0x1))) { \ + if (orig>=curr_heapbase&&orig=curr_heapbase&&orignext=tmp; head=tmp; @@ -75,6 +148,115 @@ void * dequeue() { return tail->ptrs[tailindex++]; } +#ifdef STM +void fixobjlist(struct objlist * ptr) { + while(ptr!=NULL) { + int i; + for(i=0;ioffset;i++) { + SENQUEUE(ptr->objs[i], ptr->objs[i]); + } + ptr=ptr->next; + } +} + +void fixtable(chashlistnode_t ** tc_table, chashlistnode_t **tc_list, cliststruct_t **cstr, unsigned int tc_size) { + unsigned int mask=(tc_size<<4)-1; + chashlistnode_t *node=calloc(tc_size, sizeof(chashlistnode_t)); + chashlistnode_t *ptr=*tc_table; + chashlistnode_t *curr; + unsigned int i; + unsigned int index; + int isfirst; + chashlistnode_t *newlist=NULL; + for(i=0;ikey) == 0) { //Exit inner loop if there the first element is 0 + break; //key = val =0 for element if not present within the hash table + } + SENQUEUE(key, key); + if (curr->val>=curr_heapbase&&curr->valval, curr->val); + } else { + //rewrite transaction cache entry + void *vptr=curr->val; + int type=((int *)vptr)[0]; + unsigned INTPTR *pointer=pointerarray[type]; + if (pointer==0) { + //array of primitives - do nothing + struct ArrayObject *ao=(struct ArrayObject *) vptr; + SENQUEUE((void *)ao->___objlocation___, *((void **)&ao->___objlocation___)); + } else if (((INTPTR)pointer)==1) { + //array of pointers + struct ArrayObject *ao=(struct ArrayObject *) vptr; + int length=ao->___length___; + int i; + SENQUEUE((void *)ao->___objlocation___, *((void **)&ao->___objlocation___)); + for(i=0; i___length___)+sizeof(int)))[i]; + SENQUEUE(objptr, ((void **)(((char *)&ao->___length___)+sizeof(int)))[i]); + } + } else { + INTPTR size=pointer[0]; + int i; + for(i=1; i<=size; i++) { + unsigned int offset=pointer[i]; + void * objptr=*((void **)(((char *)vptr)+offset)); + SENQUEUE(objptr, *((void **)(((char *)vptr)+offset))); + } + } + } + + next = curr->next; + index = (((unsigned INTPTR)key) & mask) >>4; + + curr->key=key; + tmp=&node[index]; + // Insert into the new table + if(tmp->key == 0) { + tmp->key = curr->key; + tmp->val = curr->val; + tmp->lnext=newlist; + newlist=tmp; + } else if (isfirst) { + chashlistnode_t *newnode; + if ((*cstr)->numarray[(*cstr)->num]; + (*cstr)->num++; + } else { + //get new list + cliststruct_t *tcl=calloc(1,sizeof(cliststruct_t)); + tcl->next=*cstr; + *cstr=tcl; + newnode=&tcl->array[0]; + tcl->num=1; + } + newnode->key = curr->key; + newnode->val = curr->val; + newnode->next = tmp->next; + newnode->lnext=newlist; + newlist=newnode; + tmp->next=newnode; + } else { + curr->lnext=newlist; + newlist=curr; + curr->next=tmp->next; + tmp->next=curr; + } + isfirst = 0; + curr = next; + } while(curr!=NULL); + } + free(ptr); + (*tc_table)=node; + (*tc_list)=newlist; +} +#endif + int moreItems() { if ((head==tail)&&(tailindex==headindex)) return 0; @@ -96,9 +278,14 @@ void enqueuetag(struct ___TagDescriptor___ *ptr) { } #endif +#if defined(STM)||defined(THREADS) +__thread char * memorybase=NULL; +__thread char * memorytop=NULL; +#endif + void collect(struct garbagelist * stackptr) { -#ifdef THREADS +#if defined(THREADS)||defined(DSTM)||defined(STM) needtocollect=1; pthread_mutex_lock(&gclistlock); while(1) { @@ -108,6 +295,18 @@ void collect(struct garbagelist * stackptr) { pthread_cond_wait(&gccond, &gclistlock); } #endif +#ifdef DELAYCOMP + ptrstack.prev=stackptr; + stackptr=(struct garbagelist *) &ptrstack; +#endif + +#ifdef GARBAGESTATS + { + int i; + for(i=0;isize;i++) { + for(i=0; isize; i++) { void * orig=stackptr->array[i]; - void * copy; - if (gc_createcopy(orig,©)) - enqueue(orig); - stackptr->array[i]=copy; + ENQUEUE(orig, stackptr->array[i]); } stackptr=stackptr->next; } -#ifdef THREADS +#if defined(THREADS)||defined(DSTM)||defined(STM) /* Go to next thread */ +#ifndef MAC + //skip over us + if (listptr==&litem) { + listptr=listptr->next; + } +#else + { + struct listitem *litem=pthread_getspecific(litemkey); + if (listptr==litem) { + listptr=listptr->next; + } + } +#endif + if (listptr!=NULL) { +#ifdef THREADS void * orig=listptr->locklist; - void * copy; - if (gc_createcopy(orig,©)) - enqueue(orig); - listptr->locklist=copy; + ENQUEUE(orig, listptr->locklist); +#endif +#ifdef STM + if ((*listptr->tc_table)!=NULL) { + fixtable(listptr->tc_table, listptr->tc_list, listptr->tc_structs, listptr->tc_size); + fixobjlist(listptr->objlist); +#ifdef STMSTATS + fixobjlist(listptr->lockedlist); +#endif + } + *(listptr->base)=NULL; +#endif stackptr=listptr->stackptr; listptr=listptr->next; } else break; - } - } +} +} #endif - + +#ifdef FASTCHECK + ENQUEUE(___fcrevert___, ___fcrevert___); +#endif + #ifdef TASK { /* Update objectsets */ int i; - for(i=0;iobjectset; - struct RuntimeNode * ptr=set->listhead; + struct ObjectHash * set=p->objectset; + struct ObjectNode * ptr=set->listhead; while(ptr!=NULL) { void *orig=(void *)ptr->key; - void *copy; - if (gc_createcopy(orig, ©)) - enqueue(orig); - ptr->key=(int)copy; - + ENQUEUE(orig, *((void **)(&ptr->key))); ptr=ptr->lnext; } - RuntimeHashrehash(set); /* Rehash the table */ + ObjectHashrehash(set); /* Rehash the table */ p=p->next; } +#endif } } - + +#ifndef FASTCHECK if (forward!=NULL) { - struct RuntimeNode * ptr=forward->listhead; + struct cnode * ptr=forward->listhead; while(ptr!=NULL) { void * orig=(void *)ptr->key; - void *copy; - if (gc_createcopy(orig, ©)) - enqueue(orig); - ptr->key=(int)copy; - + ENQUEUE(orig, *((void **)(&ptr->key))); ptr=ptr->lnext; } - RuntimeHashrehash(forward); /* Rehash the table */ + crehash(forward); /* Rehash the table */ } if (reverse!=NULL) { - struct RuntimeNode * ptr=reverse->listhead; + struct cnode * ptr=reverse->listhead; while(ptr!=NULL) { - void *orig=(void *)ptr->data; - void *copy; - if (gc_createcopy(orig, ©)) - enqueue(orig); - ptr->data=(int)copy; - + void *orig=(void *)ptr->val; + ENQUEUE(orig, *((void**)(&ptr->val))); ptr=ptr->lnext; } } +#endif { struct RuntimeNode * ptr=fdtoobject->listhead; while(ptr!=NULL) { void *orig=(void *)ptr->data; - void *copy; - if (gc_createcopy(orig, ©)) - enqueue(orig); - ptr->data=(int)copy; - + ENQUEUE(orig, *((void**)(&ptr->data))); ptr=ptr->lnext; } } @@ -224,46 +446,37 @@ void collect(struct garbagelist * stackptr) { { /* Update current task descriptor */ int i; - for(i=0;inumParameters;i++) { + for(i=0; inumParameters; i++) { void *orig=currtpd->parameterArray[i]; - void *copy; - if (gc_createcopy(orig, ©)) - enqueue(orig); - currtpd->parameterArray[i]=copy; + ENQUEUE(orig, currtpd->parameterArray[i]); } } - /* Update active tasks */ + /* Update active tasks */ { struct genpointerlist * ptr=activetasks->list; while(ptr!=NULL) { struct taskparamdescriptor *tpd=ptr->src; int i; - for(i=0;inumParameters;i++) { + for(i=0; inumParameters; i++) { void * orig=tpd->parameterArray[i]; - void * copy; - if (gc_createcopy(orig, ©)) - enqueue(orig); - tpd->parameterArray[i]=copy; + ENQUEUE(orig, tpd->parameterArray[i]); } ptr=ptr->inext; } genrehash(activetasks); } - /* Update failed tasks */ + /* Update failed tasks */ { struct genpointerlist * ptr=failedtasks->list; while(ptr!=NULL) { struct taskparamdescriptor *tpd=ptr->src; int i; - for(i=0;inumParameters;i++) { + for(i=0; inumParameters; i++) { void * orig=tpd->parameterArray[i]; - void * copy; - if (gc_createcopy(orig, ©)) - enqueue(orig); - tpd->parameterArray[i]=copy; + ENQUEUE(orig, tpd->parameterArray[i]); } ptr=ptr->inext; } @@ -273,9 +486,9 @@ void collect(struct garbagelist * stackptr) { while(moreItems()) { void * ptr=dequeue(); - void *cpy=((void **)ptr)[1]; + void *cpy=ptr; int type=((int *)cpy)[0]; - unsigned int * pointer; + unsigned INTPTR * pointer; #ifdef TASK if(type==TAGTYPE) { /* Enqueue Tag */ @@ -288,29 +501,41 @@ void collect(struct garbagelist * stackptr) { if (pointer==0) { /* Array of primitives */ /* Do nothing */ - } else if (((int)pointer)==1) { +#if defined(DSTM)||defined(FASTCHECK) + struct ArrayObject *ao=(struct ArrayObject *) ptr; + struct ArrayObject *ao_cpy=(struct ArrayObject *) cpy; + ENQUEUE((void *)ao->___nextobject___, *((void **)&ao_cpy->___nextobject___)); + ENQUEUE((void *)ao->___localcopy___, *((void **)&ao_cpy->___localcopy___)); +#endif +#if defined(STM) + struct ArrayObject *ao=(struct ArrayObject *) ptr; + struct ArrayObject *ao_cpy=(struct ArrayObject *) cpy; + SENQUEUE((void *)ao->___objlocation___, *((void **)&ao_cpy->___objlocation___)); +#endif + } else if (((INTPTR)pointer)==1) { /* Array of pointers */ struct ArrayObject *ao=(struct ArrayObject *) ptr; struct ArrayObject *ao_cpy=(struct ArrayObject *) cpy; +#if (defined(DSTM)||defined(FASTCHECK)) + ENQUEUE((void *)ao->___nextobject___, *((void **)&ao_cpy->___nextobject___)); + ENQUEUE((void *)ao->___localcopy___, *((void **)&ao_cpy->___localcopy___)); +#endif +#if defined(STM) + SENQUEUE((void *)ao->___objlocation___, *((void **)&ao_cpy->___objlocation___)); +#endif int length=ao->___length___; int i; - for(i=0;i___length___)+sizeof(int)))[i]; - void * copy; - if (gc_createcopy(objptr, ©)) - enqueue(objptr); - ((void **)(((char *)& ao_cpy->___length___)+sizeof(int)))[i]=copy; + for(i=0; i___length___)+sizeof(int)))[i]; + ENQUEUE(objptr, ((void **)(((char *)&ao_cpy->___length___)+sizeof(int)))[i]); } } else { - int size=pointer[0]; + INTPTR size=pointer[0]; int i; - for(i=1;i<=size;i++) { + for(i=1; i<=size; i++) { unsigned int offset=pointer[i]; - void * objptr=*((void **)(((int)ptr)+offset)); - void * copy; - if (gc_createcopy(objptr, ©)) - enqueue(objptr); - *((void **) (((int)cpy)+offset))=copy; + void * objptr=*((void **)(((char *)ptr)+offset)); + ENQUEUE(objptr, *((void **)(((char *)cpy)+offset))); } } } @@ -318,22 +543,26 @@ void collect(struct garbagelist * stackptr) { fixtags(); #endif -#ifdef THREADS +#if defined(THREADS)||defined(DSTM)||defined(STM) needtocollect=0; pthread_mutex_unlock(&gclistlock); #endif } #ifdef TASK +/* Fix up the references from tags. This can't be done earlier, + because we don't want tags to keep objects alive */ void fixtags() { while(taghead!=NULL) { int i; struct pointerblock *tmp=taghead->next; - for(i=0;iptrs[i]; struct ___Object___ *obj=tagd->flagptr; struct ___TagDescriptor___ *copy=((struct ___TagDescriptor___**)tagd)[1]; - if (obj->type==-1) { + if (obj==NULL) { + /* Zero object case */ + } else if (obj->type==-1) { /* Single object case */ copy->flagptr=((struct ___Object___**)obj)[1]; } else if (obj->type==OBJECTARRAYTYPE) { @@ -343,20 +572,21 @@ void fixtags() { int j; int k=0; struct ArrayObject *aonew; - + /* Count live objects */ - for(j=0;j___cachedCode___;j++) { + for(j=0; j___cachedCode___; j++) { struct ___Object___ * tobj=ARRAYGET(ao, struct ___Object___ *, j); if (tobj->type==-1) livecount++; } - + livecount=((livecount-1)/OBJECTARRAYINTERVAL+1)*OBJECTARRAYINTERVAL; aonew=(struct ArrayObject *) tomalloc(sizeof(struct ArrayObject)+sizeof(struct ___Object___*)*livecount); + memcpy(aonew, ao, sizeof(struct ArrayObject)); aonew->type=OBJECTARRAYTYPE; aonew->___length___=livecount; copy->flagptr=aonew; - for(j=0;j___cachedCode___;j++) { + for(j=0; j___cachedCode___; j++) { struct ___Object___ * tobj=ARRAYGET(ao, struct ___Object___ *, j); if (tobj->type==-1) { struct ___Object___ * tobjcpy=((struct ___Object___**)tobj)[1]; @@ -364,7 +594,9 @@ void fixtags() { } } aonew->___cachedCode___=k; - + for(; kflagptr=NULL; @@ -377,96 +609,132 @@ void fixtags() { } #endif -void * curr_heapbase=0; -void * curr_heapptr=0; -void * curr_heapgcpoint=0; -void * curr_heaptop=0; - -void * to_heapbase=0; -void * to_heapptr=0; -void * to_heaptop=0; -long lastgcsize=0; - void * tomalloc(int size) { void * ptr=to_heapptr; - if ((size%4)!=0) - size+=(4-(size%4)); + if ((size&7)!=0) + size+=(8-(size%8)); to_heapptr+=size; return ptr; } -#ifdef THREADS - +#if defined(THREADS)||defined(DSTM)||defined(STM) void checkcollect(void * ptr) { - if (needtocollect) { - struct listitem * tmp=stopforgc((struct garbagelist *)ptr); - pthread_mutex_lock(&gclock); // Wait for GC - restartaftergc(tmp); - pthread_mutex_unlock(&gclock); + stopforgc((struct garbagelist *)ptr); + restartaftergc(); +} - } +#ifdef DSTM +void checkcollect2(void * ptr) { + int ptrarray[]={1, (int)ptr, (int) revertlist}; + stopforgc((struct garbagelist *)ptrarray); + restartaftergc(); + revertlist=(struct ___Object___*)ptrarray[2]; } +#endif -struct listitem * stopforgc(struct garbagelist * ptr) { - struct listitem * litem=malloc(sizeof(struct listitem)); +void stopforgc(struct garbagelist * ptr) { +#ifdef DELAYCOMP + //just append us to the list + ptrstack.prev=ptr; + ptr=(struct garbagelist *) &ptrstack; +#endif +#ifndef MAC + litem.stackptr=ptr; +#ifdef THREADS + litem.locklist=pthread_getspecific(threadlocks); +#endif +#ifdef STM + litem.tc_size=c_size; + litem.tc_table=&c_table; + litem.tc_list=&c_list; + litem.tc_structs=&c_structs; + litem.objlist=newobjs; +#ifdef STMSTATS + litem.lockedlist=lockedobjs; +#endif + litem.base=&memorybase; +#endif +#else + //handle MAC + struct listitem *litem=pthread_getspecific(litemkey); litem->stackptr=ptr; +#ifdef THREADS litem->locklist=pthread_getspecific(threadlocks); - litem->prev=NULL; +#endif +#endif pthread_mutex_lock(&gclistlock); - litem->next=list; - if(list!=NULL) - list->prev=litem; - list=litem; listcount++; - pthread_cond_signal(&gccond); + if ((listcount+1)==threadcount) { + //only do wakeup if we are ready to GC + pthread_cond_signal(&gccond); + } pthread_mutex_unlock(&gclistlock); - return litem; } -void restartaftergc(struct listitem * litem) { - pthread_mutex_lock(&gclistlock); - pthread_setspecific(threadlocks, litem->locklist); - if (litem->prev==NULL) { - list=litem->next; - } else { - litem->prev->next=litem->next; - } - if (litem->next!=NULL) { - litem->next->prev=litem->prev; +void restartaftergc() { + if (needtocollect) { + pthread_mutex_lock(&gclock); // Wait for GC + pthread_mutex_unlock(&gclock); } + pthread_mutex_lock(&gclistlock); listcount--; pthread_mutex_unlock(&gclistlock); - free(litem); } #endif +#if defined(STM)||defined(THREADS) +#define MEMORYBLOCK 65536 +void * helper(struct garbagelist *, int); void * mygcmalloc(struct garbagelist * stackptr, int size) { + if ((size&7)!=0) + size=(size&~7)+8; + if (memorybase==NULL||size>(memorytop-memorybase)) { + int toallocate=(size>MEMORYBLOCK)?size:MEMORYBLOCK; + memorybase=helper(stackptr, toallocate); + memorytop=memorybase+toallocate; + } + char *retvalue=memorybase; + memorybase+=size; + return retvalue; +} + +void * helper(struct garbagelist * stackptr, int size) { +#else +void * mygcmalloc(struct garbagelist * stackptr, int size) { +#endif void *ptr; -#ifdef THREADS - if (pthread_mutex_trylock(&gclock)!=0) { - struct listitem *tmp=stopforgc(stackptr); - pthread_mutex_lock(&gclock); - restartaftergc(tmp); +#if defined(THREADS)||defined(DSTM)||defined(STM) + while (pthread_mutex_trylock(&gclock)!=0) { + stopforgc(stackptr); + restartaftergc(); } #endif ptr=curr_heapptr; - if ((size%4)!=0) - size+=(4-(size%4)); + if ((size&7)!=0) + size=(size&~7)+8; curr_heapptr+=size; - if (curr_heapptr>curr_heapgcpoint) { + if (curr_heapptr>curr_heapgcpoint||curr_heapptr0) { last_heapsize=HEAPSIZE(lastgcsize, size); - if ((last_heapsize%4)!=0) - last_heapsize+=(4-(last_heapsize%4)); + if ((last_heapsize&7)!=0) + last_heapsize+=(8-(last_heapsize%8)); } if (curr_heapsize>last_heapsize) last_heapsize=curr_heapsize; if (last_heapsize>to_heapsize) { free(to_heapbase); to_heapbase=malloc(last_heapsize); + if (to_heapbase==NULL) { + printf("Error Allocating enough memory\n"); + exit(-1); + } to_heaptop=to_heapbase+last_heapsize; to_heapptr=to_heapbase; } } - + /* Do our collection */ collect(stackptr); /* Update stat on previous gc size */ lastgcsize=(to_heapptr-to_heapbase)+size; +#ifdef GARBAGESTATS + printf("Garbage collected: Old bytes: %u\n", curr_heapptr-curr_heapbase); + printf("New space: %u\n", to_heapptr-to_heapbase); + printf("Total space: %u\n", to_heaptop-to_heapbase); + { + int i; + for(i=0;icurr_heapgcpoint) { -#ifdef THREADS +#if defined(THREADS)||defined(DSTM)||defined(STM) pthread_mutex_unlock(&gclock); #endif return mygcmalloc(stackptr, size); } - + bzero(tmp, curr_heaptop-tmp); -#ifdef THREADS +#if defined(THREADS)||defined(DSTM)||defined(STM) pthread_mutex_unlock(&gclock); #endif return tmp; } } else { -#ifdef THREADS +#if defined(THREADS)||defined(DSTM)||defined(STM) pthread_mutex_unlock(&gclock); #endif return ptr; @@ -545,11 +829,22 @@ int gc_createcopy(void * orig, void ** copy_ptr) { if (type==-1) { *copy_ptr=((void **)orig)[1]; return 0; - } if (type___length___; +#ifdef STM + int size=sizeof(struct ArrayObject)+length*elementsize+sizeof(objheader_t); + void *newobj=tomalloc(size); + memcpy(newobj, ((char*)orig)-sizeof(objheader_t), size); + newobj=((char *)newobj)+sizeof(objheader_t); +#else int size=sizeof(struct ArrayObject)+length*elementsize; void *newobj=tomalloc(size); memcpy(newobj, orig, size); +#endif +#ifdef GARBAGESTATS + garbagearray[type]+=size; +#endif ((int *)orig)[0]=-1; ((void **)orig)[1]=newobj; *copy_ptr=newobj;