From 2b528fbd3a7c882098a43240a6f88ea2bdb7be56 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Tue, 14 Jun 2011 09:17:55 +0000 Subject: [PATCH] changes to support marked bit table...might work?? --- Robust/src/Runtime/bamboo/multicoregarbage.c | 2 - Robust/src/Runtime/bamboo/multicoregarbage.h | 33 ++- .../src/Runtime/bamboo/multicoregccompact.c | 205 +++++++----------- Robust/src/Runtime/bamboo/multicoregcflush.c | 13 +- Robust/src/Runtime/bamboo/multicoregcmark.c | 49 ++--- Robust/src/Runtime/bamboo/multicoremsg.c | 7 +- 6 files changed, 141 insertions(+), 168 deletions(-) diff --git a/Robust/src/Runtime/bamboo/multicoregarbage.c b/Robust/src/Runtime/bamboo/multicoregarbage.c index 01572d64..6fc315b4 100644 --- a/Robust/src/Runtime/bamboo/multicoregarbage.c +++ b/Robust/src/Runtime/bamboo/multicoregarbage.c @@ -385,8 +385,6 @@ INLINE bool cacheLObjs() { size = gclobjtail2->lengths[gclobjtailindex2]; // set the mark field to , indicating that this obj has been moved // and need to be flushed - ((struct ___Object___ *)(gclobjtail2->lobjs[gclobjtailindex2]))->marked=COMPACTED; - BAMBOO_CACHE_FLUSH_LINE(gclobjtail2->lobjs[gclobjtailindex2]); dst -= size; if((unsigned int)dst<(unsigned int)(gclobjtail2->lobjs[gclobjtailindex2]+size)) { memmove(dst, gclobjtail2->lobjs[gclobjtailindex2], size); diff --git a/Robust/src/Runtime/bamboo/multicoregarbage.h b/Robust/src/Runtime/bamboo/multicoregarbage.h index 5dd5ceeb..c7177ec8 100644 --- a/Robust/src/Runtime/bamboo/multicoregarbage.h +++ b/Robust/src/Runtime/bamboo/multicoregarbage.h @@ -19,14 +19,6 @@ // let each gc core to have one big block, this is very important // for the computation of NUMBLOCKS(s, n), DO NOT change this! -typedef enum { - INIT = 0, // 0 - DISCOVERED = 2, // 2 - MARKED = 4, // 4 - COMPACTED = 8, // 8 - END = 9 // 9 -} GCOBJFLAG; - typedef enum { INITPHASE = 0x0, // 0x0 MARKPHASE, // 0x1 @@ -97,6 +89,9 @@ volatile unsigned int gcmovepending; unsigned int * gcmappingtbl; unsigned int bamboo_rmsp_size; +unsigned int * gcmarktbl; + + // table recording the starting address of each small block // (size is BAMBOO_SMEM_SIZE) // Note: 1. this table always resides on the very bottom of the shared memory @@ -108,6 +103,7 @@ unsigned int gcsbstarttbl_len; #endif unsigned int gcnumblock; // number of total blocks in the shared mem void * gcbaseva; // base va for shared memory without reserved sblocks + #ifdef GC_CACHE_ADAPT void * gctopva; // top va for shared memory without reserved sblocks volatile bool gccachestage; @@ -134,6 +130,27 @@ unsigned int size_cachepolicytbl; #define ALIGNMENTSHIFT 5 #define ALIGNOBJSIZE(x) (x>>ALIGNMENTSHIFT) +//There are two bits per object +//00 means not marked +//11 means first block of object +//10 means marked block + +#define UNMARKED 0 +#define MARKEDFIRST 3 +#define MARKEDLATER 2 + +//sets y to the marked status of x +#define GETMARKED(y,x) { unsigned int offset=ALIGNOBJSIZE(x-gcbaseva); \ + y=(gcmarktbl[offset>>4]>>((offset&15)<<1))&3; } + +//sets the marked status of x to y (assumes zero'd) +#define SETMARKED(y,x) { unsigned int offset=ALIGNOBJSIZE(x-gcbaseva); \ + gcmarktbl[offset>>4]|=y<<((offset&15)<<1); } + +//sets the marked status of x to y (assumes zero'd) +#define RESETMARKED(x) { unsigned int offset=ALIGNOBJSIZE(x-gcbaseva); \ + gcmarktbl[offset>>4]&=~(3<<((offset&15)<<1)); } + #define ALIGNSIZE(s, as) (*((unsigned int*)as))=((((unsigned int)(s-1))&(~(BAMBOO_CACHE_LINE_MASK)))+(BAMBOO_CACHE_LINE_SIZE)) diff --git a/Robust/src/Runtime/bamboo/multicoregccompact.c b/Robust/src/Runtime/bamboo/multicoregccompact.c index 53819a8b..20d06004 100644 --- a/Robust/src/Runtime/bamboo/multicoregccompact.c +++ b/Robust/src/Runtime/bamboo/multicoregccompact.c @@ -48,26 +48,9 @@ INLINE int assignSpareMem_I(unsigned int sourcecore,unsigned int * requiredmem,u INLINE int assignSpareMem(unsigned int sourcecore,unsigned int * requiredmem,unsigned int * tomove,unsigned int * startaddr) { BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT(); - unsigned int b = 0; - BLOCKINDEX(gcloads[sourcecore], &b); - unsigned int boundptr = BOUNDPTR(b); - unsigned int remain = boundptr - gcloads[sourcecore]; - unsigned int memneed = requiredmem + BAMBOO_CACHE_LINE_SIZE; - *startaddr = gcloads[sourcecore]; - *tomove = gcfilledblocks[sourcecore] + 1; - if(memneed < remain) { - gcloads[sourcecore] += memneed; - BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME(); - return 0; - } else { - // next available block - gcfilledblocks[sourcecore] += 1; - unsigned int newbase = 0; - BASEPTR(sourcecore, gcfilledblocks[sourcecore], &newbase); - gcloads[sourcecore] = newbase; - BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME(); - return requiredmem-remain; - } + int retval=assignSpareMem_I(sourcecore, requiredmem, tomove, startaddr); + BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME(); + return retval; } INLINE void compact2Heaptophelper_I(unsigned int coren,unsigned int* p,unsigned int* numblocks,unsigned int* remain) { @@ -367,7 +350,10 @@ INLINE bool moveobj(struct moveHelper * orig, struct moveHelper * to, unsigned i ALIGNSIZE(size, &isize); // no matter is the obj marked or not // should be able to across unsigned int origptr = (unsigned int)(orig->ptr); - if(((struct ___Object___ *)origptr)->marked == MARKED) { + int markedstatus; + GETMARKED(markedstatus, origptr); + + if(markedstatus==MARKEDFIRST) { unsigned int totop = (unsigned int)to->top; unsigned int tobound = (unsigned int)to->bound; BAMBOO_ASSERT(totop<=tobound); @@ -397,7 +383,6 @@ INLINE bool moveobj(struct moveHelper * orig, struct moveHelper * to, unsigned i BAMBOO_ASSERT((to->top+isize)<=(to->bound)); // set the mark field to 2, indicating that this obj has been moved // and need to be flushed - ((struct ___Object___ *)origptr)->marked = COMPACTED; unsigned int toptr = (unsigned int)to->ptr; if(toptr != origptr) { if((unsigned int)(origptr) < (unsigned int)(toptr+size)) { @@ -451,118 +436,96 @@ bool gcfindSpareMem_I(unsigned int * startaddr,unsigned int * tomove,unsigned in bool gcfindSpareMem(unsigned int * startaddr,unsigned int * tomove,unsigned int * dstcore,unsigned int requiredmem,unsigned int requiredcore) { BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT(); - for(int k = 0; k < NUMCORES4GC; k++) { - if((gccorestatus[k] == 0) && (gcfilledblocks[k] < gcstopblock[k])) { - // check if this stopped core has enough mem - assignSpareMem_I(k, requiredmem, tomove, startaddr); - *dstcore = k; - BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME(); - return true; - } - } - // if can not find spare mem right now, hold the request - gcrequiredmems[requiredcore] = requiredmem; - gcmovepending++; + bool retval=gcfindSpareMem_I(startaddr, tomove, dstcore, requiredmem, requiredcore); BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME(); - return false; + return retval; } -INLINE bool compacthelper(struct moveHelper * orig,struct moveHelper * to,int * filledblocks,unsigned int * heaptopptr,bool * localcompact, bool lbmove) { +bool compacthelper(struct moveHelper * orig,struct moveHelper * to,int * filledblocks,unsigned int * heaptopptr,bool * localcompact, bool lbmove) { bool loadbalancemove = lbmove; // scan over all objs in this block, compact the marked objs // loop stop when finishing either scanning all active objs or // fulfilled the gcstopblock -innercompact: - while((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) { - if(moveobj(orig, to, gcblock2fill)) { - break; - } - } - CACHEADAPT_SAMPLING_DATA_CONVERT(to->ptr); - // if no objs have been compact, do nothing, - // otherwise, fill the header of this block - if(to->offset > (unsigned int)BAMBOO_CACHE_LINE_SIZE) { - CLOSEBLOCK(to->base, to->offset); - } else { - to->offset = 0; - to->ptr = to->base; - to->top -= BAMBOO_CACHE_LINE_SIZE; - } - if(*localcompact) { - *heaptopptr = to->ptr; - *filledblocks = to->numblocks; - } - /*if(loadbalancemove) { - // write back to the Main Memory and release any DTLB entry for the - // last block as someone else might later write into it - // flush the shared heap - BAMBOO_CACHE_FLUSH_L2(); - //loadbalancemove = false; - }*/ - - // send msgs to core coordinator indicating that the compact is finishing - // send compact finish message to core coordinator - if(STARTUPCORE == BAMBOO_NUM_OF_CORE) { - gcfilledblocks[BAMBOO_NUM_OF_CORE] = *filledblocks; - gcloads[BAMBOO_NUM_OF_CORE] = *heaptopptr; - //tprintf("--finish compact: %d, %d, %d, %x, %x \n", BAMBOO_NUM_OF_CORE, loadbalancemove, *filledblocks, *heaptopptr, gccurr_heaptop); - if((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) { - // ask for more mem - gctomove = false; - if(gcfindSpareMem(&gcmovestartaddr,&gcblock2fill,&gcdstcore,gccurr_heaptop,BAMBOO_NUM_OF_CORE)) { - gctomove = true; - } else { - return false; + while(true) { + while((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) { + if(moveobj(orig, to, gcblock2fill)) { + break; } + } + CACHEADAPT_SAMPLING_DATA_CONVERT(to->ptr); + // if no objs have been compact, do nothing, + // otherwise, fill the header of this block + if(to->offset > (unsigned int)BAMBOO_CACHE_LINE_SIZE) { + CLOSEBLOCK(to->base, to->offset); } else { - gccorestatus[BAMBOO_NUM_OF_CORE] = 0; - gctomove = false; - // write back to the Main Memory and release any DTLB entry for the - // last block as someone else might later write into it - // flush the shared heap - //BAMBOO_CACHE_FLUSH_L2(); - return true; + to->offset = 0; + to->ptr = to->base; + to->top -= BAMBOO_CACHE_LINE_SIZE; + } + if(*localcompact) { + *heaptopptr = to->ptr; + *filledblocks = to->numblocks; } - } else { - if((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) { - // ask for more mem - gctomove = false; - //tprintf("finish compact: %d, %d, %d, %x, %x \n", BAMBOO_NUM_OF_CORE, loadbalancemove, *filledblocks, *heaptopptr, gccurr_heaptop); - send_msg_6(STARTUPCORE,GCFINISHCOMPACT,BAMBOO_NUM_OF_CORE,loadbalancemove,*filledblocks,*heaptopptr,gccurr_heaptop); + + // send msgs to core coordinator indicating that the compact is finishing + // send compact finish message to core coordinator + if(STARTUPCORE == BAMBOO_NUM_OF_CORE) { + gcfilledblocks[BAMBOO_NUM_OF_CORE] = *filledblocks; + gcloads[BAMBOO_NUM_OF_CORE] = *heaptopptr; + //tprintf("--finish compact: %d, %d, %d, %x, %x \n", BAMBOO_NUM_OF_CORE, loadbalancemove, *filledblocks, *heaptopptr, gccurr_heaptop); + if((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) { + // ask for more mem + gctomove = false; + if(gcfindSpareMem(&gcmovestartaddr,&gcblock2fill,&gcdstcore,gccurr_heaptop,BAMBOO_NUM_OF_CORE)) { + gctomove = true; + } else { + return false; + } + } else { + gccorestatus[BAMBOO_NUM_OF_CORE] = 0; + gctomove = false; + // write back to the Main Memory and release any DTLB entry for the + // last block as someone else might later write into it + // flush the shared heap + //BAMBOO_CACHE_FLUSH_L2(); + return true; + } } else { - //tprintf("++ finish compact: %d, %d, %d, %x, %x \n", BAMBOO_NUM_OF_CORE, loadbalancemove, *filledblocks, *heaptopptr, 0); - // finish compacting - send_msg_6(STARTUPCORE,GCFINISHCOMPACT,BAMBOO_NUM_OF_CORE,loadbalancemove,*filledblocks,*heaptopptr, 0); - // write back to the Main Memory and release any DTLB entry for the - // last block as someone else might later write into it. - // flush the shared heap - //BAMBOO_CACHE_FLUSH_L2(); + if((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) { + // ask for more mem + gctomove = false; + send_msg_6(STARTUPCORE,GCFINISHCOMPACT,BAMBOO_NUM_OF_CORE,loadbalancemove,*filledblocks,*heaptopptr,gccurr_heaptop); + } else { + // finish compacting + send_msg_6(STARTUPCORE,GCFINISHCOMPACT,BAMBOO_NUM_OF_CORE,loadbalancemove,*filledblocks,*heaptopptr, 0); + // write back to the Main Memory and release any DTLB entry for the + // last block as someone else might later write into it. + // flush the shared heap + } } - } - - if(orig->ptr < gcmarkedptrbound) { - // still have unpacked obj - while(!gctomove) ; - BAMBOO_CACHE_MF(); - loadbalancemove = true; - //tprintf("move start: %x, %d \n", gcmovestartaddr, gcdstcore); - gctomove = false; - to->ptr = gcmovestartaddr; - to->numblocks = gcblock2fill - 1; - to->bound = BLOCKBOUND(to->numblocks); - BASEPTR(gcdstcore, to->numblocks, &(to->base)); - to->offset = to->ptr - to->base; - to->top=(to->numblocks==0)?(to->offset):(to->bound-BAMBOO_SMEM_SIZE+to->offset); - to->base = to->ptr; - to->offset = BAMBOO_CACHE_LINE_SIZE; - to->ptr += to->offset; // for header - to->top += to->offset; - *localcompact = (gcdstcore == BAMBOO_NUM_OF_CORE); - CACHEADAPT_SAMPLING_DATA_REVISE_INIT(orig, to); - goto innercompact; - } - return true; + if(orig->ptr < gcmarkedptrbound) { + // still have unpacked obj + while(!gctomove) ; + BAMBOO_CACHE_MF(); + loadbalancemove = true; + + gctomove = false; + to->ptr = gcmovestartaddr; + to->numblocks = gcblock2fill - 1; + to->bound = BLOCKBOUND(to->numblocks); + BASEPTR(gcdstcore, to->numblocks, &(to->base)); + to->offset = to->ptr - to->base; + to->top=(to->numblocks==0)?(to->offset):(to->bound-BAMBOO_SMEM_SIZE+to->offset); + to->base = to->ptr; + to->offset = BAMBOO_CACHE_LINE_SIZE; + to->ptr += to->offset; // for header + to->top += to->offset; + *localcompact = (gcdstcore == BAMBOO_NUM_OF_CORE); + CACHEADAPT_SAMPLING_DATA_REVISE_INIT(orig, to); + } else + return true; +} } void compact() { diff --git a/Robust/src/Runtime/bamboo/multicoregcflush.c b/Robust/src/Runtime/bamboo/multicoregcflush.c index 411f5148..a43f5cda 100644 --- a/Robust/src/Runtime/bamboo/multicoregcflush.c +++ b/Robust/src/Runtime/bamboo/multicoregcflush.c @@ -175,7 +175,6 @@ INLINE void flushPtrsInObj(void * ptr) { } void flush(struct garbagelist * stackptr) { - //unsigned long long tmpt = BAMBOO_GET_EXE_TIME(); // TODO BAMBOO_CACHE_MF(); flushRuntimeObj(stackptr); @@ -184,11 +183,13 @@ void flush(struct garbagelist * stackptr) { // should be a local shared obj and should have mapping info FLUSHOBJNONNULL(ptr, 0); BAMBOO_ASSERT(ptr != NULL); + int markedstatus; + GETMARKED(markedstatus, ptr); - if(((struct ___Object___ *)ptr)->marked == COMPACTED) { + if(markedstatus==MARKEDFIRST) { flushPtrsInObj((void *)ptr); // restore the mark field, indicating that this obj has been flushed - ((struct ___Object___ *)ptr)->marked = INIT; + RESETMARKED(ptr); } } @@ -200,10 +201,12 @@ void flush(struct garbagelist * stackptr) { FLUSHOBJ(ptr, 0); BAMBOO_ASSERT(ptr!=NULL); - if(((struct ___Object___ *)ptr)->marked == COMPACTED) { + GETMARKED(markedstatus, ptr); + + if(markedstatus==MARKEDFIRST) { flushPtrsInObj((void *)ptr); // restore the mark field, indicating that this obj has been flushed - ((struct ___Object___ *)ptr)->marked = INIT; + RESETMARKED(ptr); } } diff --git a/Robust/src/Runtime/bamboo/multicoregcmark.c b/Robust/src/Runtime/bamboo/multicoregcmark.c index 5b940a4f..ea39e0bb 100644 --- a/Robust/src/Runtime/bamboo/multicoregcmark.c +++ b/Robust/src/Runtime/bamboo/multicoregcmark.c @@ -42,15 +42,13 @@ INLINE void gettype_size(void * ptr, int * ttype, unsigned int * tsize) { } } -/* THIS FUNCTION IS BAD!!!!!!!!!!!!!! */ INLINE bool isLarge(void * ptr, int * ttype, unsigned int * tsize) { // check if a pointer refers to a large object gettype_size(ptr, ttype, tsize); unsigned int blocksize = (((unsigned int)ptr-gcbaseva) < (BAMBOO_LARGE_SMEM_BOUND))? BAMBOO_SMEM_SIZE_L:BAMBOO_SMEM_SIZE; // ptr is a start of a block OR it crosses the boundary of current block - return (((((unsigned int)ptr-gcbaseva)%blocksize)==0)|| - ((blocksize-(((unsigned int)ptr-gcbaseva)%blocksize)) < (*tsize))); + return *tsize > blocksize; } INLINE unsigned int hostcore(void * ptr) { @@ -68,7 +66,6 @@ INLINE unsigned int hostcore(void * ptr) { //push the null check into the mark macro //#define MARKOBJ(objptr, ii) {void * marktmpptr=objptr; if (marktmpptr!=NULL) markObj(marktmpptr, __LINE__, ii);} - //#define MARKOBJNONNULL(objptr, ii) {markObj(objptr, __LINE__, ii);} #define MARKOBJ(objptr, ii) {void * marktmpptr=objptr; if (marktmpptr!=NULL) markObj(marktmpptr);} @@ -79,12 +76,13 @@ INLINE unsigned int hostcore(void * ptr) { INLINE void markObj(void * objptr) { unsigned int host = hostcore(objptr); if(BAMBOO_NUM_OF_CORE == host) { + int markedbit; + GETMARKED(markedbit, objptr); // on this core - if(((struct ___Object___ *)objptr)->marked == INIT) { + if(markedbit == UNMARKED) { // this is the first time that this object is discovered, // set the flag as DISCOVERED - ((struct ___Object___ *)objptr)->marked = DISCOVERED; - BAMBOO_CACHE_FLUSH_LINE(objptr); + SETMARKED(MARKEDFIRST, objptr); gc_enqueue(objptr); } } else { @@ -111,18 +109,18 @@ INLINE void markgarbagelist(struct garbagelist * listptr) { // enqueue root objs INLINE void tomark(struct garbagelist * stackptr) { BAMBOO_ASSERT(MARKPHASE == gc_status_info.gcphase); - + gc_status_info.gcbusystatus = true; gcnumlobjs = 0; - + // enqueue current stack markgarbagelist(stackptr); - + // enqueue static pointers global_defs_p if(STARTUPCORE == BAMBOO_NUM_OF_CORE) { markgarbagelist((struct garbagelist *)global_defs_p); } - + #ifdef TASK // enqueue objectsets if(BAMBOO_NUM_OF_CORE < NUMCORESACTIVE) { @@ -139,8 +137,8 @@ INLINE void tomark(struct garbagelist * stackptr) { } } } - - // euqueue current task descriptor + + // enqueue current task descriptor if(currtpd != NULL) { for(int i=0; inumParameters; i++) { // currtpd->parameterArray[i] can not be NULL @@ -148,7 +146,7 @@ INLINE void tomark(struct garbagelist * stackptr) { } } - // euqueue active tasks + // enqueue active tasks if(activetasks != NULL) { struct genpointerlist * ptr=activetasks->list; for(;ptr!=NULL;ptr=ptr->inext) { @@ -272,35 +270,26 @@ INLINE void mark(bool isfirst, struct garbagelist * stackptr) { unsigned int ptr = gc_dequeue2(); unsigned int size = 0; - unsigned int isize = 0; unsigned int type = 0; - // check if it is a local obj on this core - if(((struct ___Object___ *)ptr)->marked!=DISCOVERED) { - // ptr has been marked - continue; - } else if(isLarge(ptr, &type, &size)) { + + if(isLarge(ptr, &type, &size)) { // ptr is a large object and not marked or enqueued gc_lobjenqueue(ptr, size, BAMBOO_NUM_OF_CORE); gcnumlobjs++; - // mark this obj - //((struct ___Object___ *)ptr)->marked = COMPACTED; } else { // ptr is an unmarked active object on this core + unsigned int isize = 0; ALIGNSIZE(size, &isize); gccurr_heaptop += isize; - + if((unsigned int)(ptr + size) > (unsigned int)gcmarkedptrbound) { gcmarkedptrbound = (unsigned int)(ptr + size); } - // mark this obj - //((struct ___Object___ *)ptr)->marked = MARKED; } - // mark this obj - ((struct ___Object___ *)ptr)->marked = MARKED; - BAMBOO_CACHE_FLUSH_LINE(ptr); + // scan the pointers in object - scanPtrsInObj(ptr, type); - } + scanPtrsInObj(ptr, type); + } gc_status_info.gcbusystatus = false; // send mark finish msg to core coordinator if(STARTUPCORE == BAMBOO_NUM_OF_CORE) { diff --git a/Robust/src/Runtime/bamboo/multicoremsg.c b/Robust/src/Runtime/bamboo/multicoremsg.c index 7be4c17b..2b80c6bf 100644 --- a/Robust/src/Runtime/bamboo/multicoremsg.c +++ b/Robust/src/Runtime/bamboo/multicoremsg.c @@ -597,10 +597,13 @@ INLINE void processmsg_gcmarkedobj_I() { BAMBOO_ASSERT(ISSHAREDOBJ(data1)); // received a markedObj msg - if(((struct ___Object___ *)data1)->marked == INIT) { + int markedbit; + GETMARKED(markedbit, data1); + + if(markedbit==UNMARKED) { // this is the first time that this object is discovered, // set the flag as DISCOVERED - ((struct ___Object___ *)data1)->marked = DISCOVERED; + SETMARKED(MARKEDFIRST, data1); gc_enqueue_I(data1); } gcself_numreceiveobjs++; -- 2.34.1