2 #include "multicoregccompact.h"
3 #include "runtime_arch.h"
4 #include "multicoreruntime.h"
5 #include "multicoregarbage.h"
7 INLINE bool gc_checkCoreStatus() {
8 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
9 for(int i = 0; i < NUMCORES4GC; ++i) {
10 if(gccorestatus[i] != 0) {
11 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
15 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
19 INLINE void gc_resetCoreStatus() {
20 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
21 for(int i = 0; i < NUMCORES4GC; ++i) {
24 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
27 // should be invoked with interrupt closed
28 INLINE int assignSpareMem_I(unsigned int sourcecore,unsigned int * requiredmem,unsigned int * tomove,unsigned int * startaddr) {
30 BLOCKINDEX(gcloads[sourcecore], &b);
31 unsigned int boundptr = BOUNDPTR(b);
32 unsigned int remain = boundptr - gcloads[sourcecore];
33 unsigned int memneed = requiredmem + BAMBOO_CACHE_LINE_SIZE;
34 *startaddr = gcloads[sourcecore];
35 *tomove = gcfilledblocks[sourcecore] + 1;
36 if(memneed < remain) {
37 gcloads[sourcecore] += memneed;
40 // next available block
41 gcfilledblocks[sourcecore] += 1;
42 unsigned int newbase = 0;
43 BASEPTR(sourcecore, gcfilledblocks[sourcecore], &newbase);
44 gcloads[sourcecore] = newbase;
45 return requiredmem-remain;
49 INLINE int assignSpareMem(unsigned int sourcecore,unsigned int * requiredmem,unsigned int * tomove,unsigned int * startaddr) {
50 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
52 BLOCKINDEX(gcloads[sourcecore], &b);
53 unsigned int boundptr = BOUNDPTR(b);
54 unsigned int remain = boundptr - gcloads[sourcecore];
55 unsigned int memneed = requiredmem + BAMBOO_CACHE_LINE_SIZE;
56 *startaddr = gcloads[sourcecore];
57 *tomove = gcfilledblocks[sourcecore] + 1;
58 if(memneed < remain) {
59 gcloads[sourcecore] += memneed;
60 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
63 // next available block
64 gcfilledblocks[sourcecore] += 1;
65 unsigned int newbase = 0;
66 BASEPTR(sourcecore, gcfilledblocks[sourcecore], &newbase);
67 gcloads[sourcecore] = newbase;
68 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
69 return requiredmem-remain;
73 INLINE void compact2Heaptophelper_I(unsigned int coren,unsigned int* p,unsigned int* numblocks,unsigned int* remain) {
75 unsigned int memneed = gcrequiredmems[coren] + BAMBOO_CACHE_LINE_SIZE;
76 if(STARTUPCORE == coren) {
79 gcdstcore = gctopcore;
80 gcblock2fill = *numblocks + 1;
82 if(BAMBOO_CHECK_SEND_MODE()) {
83 cache_msg_4_I(coren,GCMOVESTART,gctopcore,*p,(*numblocks)+1);
85 send_msg_4_I(coren,GCMOVESTART,gctopcore,*p,(*numblocks)+1);
88 if(memneed < *remain) {
90 gcrequiredmems[coren] = 0;
91 gcloads[gctopcore] += memneed;
92 *remain = *remain - memneed;
94 // next available block
96 gcfilledblocks[gctopcore] += 1;
97 unsigned int newbase = 0;
98 BASEPTR(gctopcore, gcfilledblocks[gctopcore], &newbase);
99 gcloads[gctopcore] = newbase;
100 gcrequiredmems[coren] -= *remain - BAMBOO_CACHE_LINE_SIZE;
101 gcstopblock[gctopcore]++;
102 gctopcore = NEXTTOPCORE(gctopblock);
104 *numblocks = gcstopblock[gctopcore];
105 *p = gcloads[gctopcore];
107 *remain=GC_BLOCK_REMAIN_SIZE(b, (*p));
112 INLINE void compact2Heaptop() {
113 // no cores with spare mem and some cores are blocked with pending move
114 // find the current heap top and make them move to the heap top
116 unsigned int numblocks = gcfilledblocks[gctopcore];
117 p = gcloads[gctopcore];
120 unsigned int remain=GC_BLOCK_REMAIN_SIZE(b, p);
121 // check if the top core finishes
122 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
123 if(gccorestatus[gctopcore] != 0) {
124 // let the top core finishes its own work first
125 compact2Heaptophelper_I(gctopcore, &p, &numblocks, &remain);
126 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
129 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
131 for(int i = 0; i < NUMCORES4GC; i++) {
132 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
133 if((gccorestatus[i] != 0) && (gcrequiredmems[i] > 0)) {
134 compact2Heaptophelper_I(i, &p, &numblocks, &remain);
135 if(gccorestatus[gctopcore] != 0) {
136 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
137 // the top core is not free now
141 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
145 INLINE void resolvePendingMoveRequest() {
148 bool nosparemem = true;
149 bool haspending = false;
150 bool hasrunning = false;
151 bool noblock = false;
152 unsigned int dstcore = 0; // the core who need spare mem
153 unsigned int sourcecore = 0; // the core who has spare mem
154 for(i = j = 0; (i < NUMCORES4GC) && (j < NUMCORES4GC); ) {
156 // check if there are cores with spare mem
157 if(gccorestatus[i] == 0) {
158 // finished working, check if it still have spare mem
159 if(gcfilledblocks[i] < gcstopblock[i]) {
160 // still have spare mem
168 if(gccorestatus[j] != 0) {
169 // not finished, check if it has pending move requests
170 if((gcfilledblocks[j]==gcstopblock[j])&&(gcrequiredmems[j]>0)) {
179 if(!nosparemem && haspending) {
181 unsigned int tomove = 0;
182 unsigned int startaddr = 0;
183 gcrequiredmems[dstcore] = assignSpareMem(sourcecore,gcrequiredmems[dstcore],&tomove,&startaddr);
184 if(STARTUPCORE == dstcore) {
185 gcdstcore = sourcecore;
187 gcmovestartaddr = startaddr;
188 gcblock2fill = tomove;
190 send_msg_4(dstcore,GCMOVESTART,sourcecore,startaddr,tomove);
199 if(!hasrunning && !noblock) {
200 gc_status_info.gcphase = SUBTLECOMPACTPHASE;
205 // If out of boundary of valid shared memory, return false, else return true
206 INLINE bool nextSBlock(struct moveHelper * orig) {
207 orig->blockbase = orig->blockbound;
209 bool sbchanged = false;
210 unsigned int origptr = orig->ptr;
211 unsigned int blockbase = orig->blockbase;
212 unsigned int blockbound = orig->blockbound;
213 unsigned int bound = orig->bound;
215 // check if across a big block
216 // TODO now do not zero out the whole memory, maybe the last two conditions
218 if((blockbase>=bound)||(origptr>=bound)||((origptr!=NULL)&&(*((int*)origptr))==0)||((*((int*)blockbase))==0)) {
220 // end of current heap block, jump to next one
222 BASEPTR(BAMBOO_NUM_OF_CORE, orig->numblocks, &(orig->base));
223 if(orig->base >= gcbaseva + BAMBOO_SHARED_MEM_SIZE) {
225 orig->ptr = orig->base; // set current ptr to out of boundary too
228 orig->blockbase = orig->base;
229 orig->sblockindex=(unsigned int)(orig->blockbase-gcbaseva)/BAMBOO_SMEM_SIZE;
231 unsigned int blocknum = 0;
232 BLOCKINDEX(orig->base, &blocknum);
233 if(bamboo_smemtbl[blocknum] == 0) {
235 goto innernextSBlock;
237 // check the bamboo_smemtbl to decide the real bound
238 orig->bound = orig->base + bamboo_smemtbl[blocknum];
239 } else if(0 == (orig->blockbase%BAMBOO_SMEM_SIZE)) {
240 orig->sblockindex += 1;
244 // check if this sblock should be skipped or have special start point
245 int sbstart = gcsbstarttbl[orig->sblockindex];
248 orig->sblockindex += 1;
249 orig->blockbase += BAMBOO_SMEM_SIZE;
250 goto outernextSBlock;
251 } else if((sbstart != 0) && (sbchanged)) {
252 // the first time to access this SBlock
253 // not start from the very beginning
254 orig->blockbase = sbstart;
257 // setup information for this sblock
258 orig->blockbound = orig->blockbase+(unsigned int)*((int*)(orig->blockbase));
259 orig->offset = BAMBOO_CACHE_LINE_SIZE;
260 orig->ptr = orig->blockbase + orig->offset;
261 if(orig->ptr >= orig->bound) {
262 // met a lobj, move to next block
263 goto innernextSBlock;
269 // return false if there are no available data to compact
270 INLINE bool initOrig_Dst(struct moveHelper * orig,struct moveHelper * to) {
273 to->top = to->offset = BAMBOO_CACHE_LINE_SIZE;
274 to->bound = BAMBOO_SMEM_SIZE_L;
275 BASEPTR(BAMBOO_NUM_OF_CORE, to->numblocks, &(to->base));
277 unsigned int tobase = to->base;
278 to->ptr = tobase + to->offset;
283 unsigned int blocknum = 0;
284 BLOCKINDEX(orig->base, &blocknum);
285 unsigned int origbase = orig->base;
286 // check the bamboo_smemtbl to decide the real bound
287 orig->bound = origbase + (unsigned int)bamboo_smemtbl[blocknum];
288 orig->blockbase = origbase;
289 orig->sblockindex = (unsigned int)(origbase - gcbaseva) / BAMBOO_SMEM_SIZE;
291 int sbstart = gcsbstarttbl[orig->sblockindex];
294 orig->blockbound=gcbaseva+BAMBOO_SMEM_SIZE*(orig->sblockindex+1);
295 return nextSBlock(orig);
296 } else if(sbstart != 0) {
297 orig->blockbase = sbstart;
299 orig->blockbound = orig->blockbase + *((int*)(orig->blockbase));
300 orig->offset = BAMBOO_CACHE_LINE_SIZE;
301 orig->ptr = orig->blockbase + orig->offset;
306 INLINE void nextBlock(struct moveHelper * to) {
307 to->top = to->bound + BAMBOO_CACHE_LINE_SIZE; // header!
308 to->bound += BAMBOO_SMEM_SIZE;
310 BASEPTR(BAMBOO_NUM_OF_CORE, to->numblocks, &(to->base));
311 to->offset = BAMBOO_CACHE_LINE_SIZE;
312 to->ptr = to->base + to->offset;
315 INLINE unsigned int findValidObj(struct moveHelper * orig,struct moveHelper * to,int * type) {
316 unsigned int size = 0;
318 CACHEADAPT_COMPLETE_PAGE_CONVERT(orig, to, to->ptr, false);
319 unsigned int origptr = (unsigned int)(orig->ptr);
320 unsigned int origbound = (unsigned int)orig->bound;
321 unsigned int origblockbound = (unsigned int)orig->blockbound;
322 if((origptr >= origbound) || (origptr == origblockbound)) {
323 if(!nextSBlock(orig)) {
324 // finished, no more data
329 // check the obj's type, size and mark flag
330 *type = ((int *)(origptr))[0];
333 // end of this block, go to next one
334 if(!nextSBlock(orig)) {
335 // finished, no more data
339 } else if(*type < NUMCLASSES) {
341 size = classsize[*type];
344 struct ArrayObject *ao=(struct ArrayObject *)(origptr);
345 unsigned int elementsize=classsize[*type];
346 unsigned int length=ao->___length___;
347 size=(unsigned int)sizeof(struct ArrayObject)+(unsigned int)(length*elementsize);
353 // endaddr does not contain spaces for headers
354 INLINE bool moveobj(struct moveHelper * orig, struct moveHelper * to, unsigned int stopblock) {
360 unsigned int size = findValidObj(orig, to, &type);
361 unsigned int isize = 0;
364 // finished, no more data
367 ALIGNSIZE(size, &isize); // no matter is the obj marked or not
368 // should be able to across
369 unsigned int origptr = (unsigned int)(orig->ptr);
370 if(((struct ___Object___ *)origptr)->marked == MARKED) {
371 unsigned int totop = (unsigned int)to->top;
372 unsigned int tobound = (unsigned int)to->bound;
373 BAMBOO_ASSERT(totop<=tobound);
374 GCPROFILE_RECORD_LIVE_OBJ();
375 // marked obj, copy it to current heap top
376 // check to see if remaining space is enough
377 if((unsigned int)(totop + isize) > tobound) {
378 // fill 0 indicating the end of this block
379 BAMBOO_MEMSET_WH(to->ptr, '\0', tobound - totop);
380 // fill the header of this block and then go to next block
381 to->offset += tobound - totop;
382 CLOSEBLOCK(to->base, to->offset);
383 #ifdef GC_CACHE_ADAPT
384 unsigned int tmp_ptr = to->ptr;
387 if((to->top+isize)>(to->bound)) tprintf("%x, %x, %d, %d, %d, %d \n", to->ptr, orig->ptr, to->top, to->bound, isize, size);
388 BAMBOO_ASSERT((to->top+isize)<=(to->bound));
389 #ifdef GC_CACHE_ADAPT
390 CACHEADAPT_COMPLETE_PAGE_CONVERT(orig, to, tmp_ptr, true);
392 if(stopblock == to->numblocks) {
393 // already fulfilled the block
397 BAMBOO_ASSERT((to->top+isize)<=(to->bound));
398 // set the mark field to 2, indicating that this obj has been moved
399 // and need to be flushed
400 ((struct ___Object___ *)origptr)->marked = COMPACTED;
401 unsigned int toptr = (unsigned int)to->ptr;
402 if(toptr != origptr) {
403 if((unsigned int)(origptr) < (unsigned int)(toptr+size)) {
404 memmove(toptr, origptr, size);
406 memcpy(toptr, origptr, size);
408 // fill the remaining space with -2
409 BAMBOO_MEMSET_WH((unsigned int)(toptr+size), -2, isize-size);
411 // store mapping info
412 gcmappingtbl[OBJMAPPINGINDEX((unsigned int)origptr)]=(unsigned int)toptr;
413 gccurr_heaptop -= isize;
417 BAMBOO_ASSERT((to->top)<=(to->bound));
418 #ifdef GC_CACHE_ADAPT
419 unsigned int tmp_ptr = to->ptr;
420 #endif // GC_CACHE_ADAPT
421 if(to->top == to->bound) {
422 CLOSEBLOCK(to->base, to->offset);
425 #ifdef GC_CACHE_ADAPT
426 CACHEADAPT_COMPLETE_PAGE_CONVERT(orig, to, tmp_ptr, true);
433 return ((((unsigned int)(orig->ptr) > (unsigned int)(orig->bound))||((unsigned int)(orig->ptr) == (unsigned int)(orig->blockbound)))&&!nextSBlock(orig));
436 // should be invoked with interrupt closed
437 bool gcfindSpareMem_I(unsigned int * startaddr,unsigned int * tomove,unsigned int * dstcore,unsigned int requiredmem,unsigned int requiredcore) {
438 for(int k = 0; k < NUMCORES4GC; k++) {
439 if((gccorestatus[k] == 0) && (gcfilledblocks[k] < gcstopblock[k])) {
440 // check if this stopped core has enough mem
441 assignSpareMem_I(k, requiredmem, tomove, startaddr);
446 // if can not find spare mem right now, hold the request
447 gcrequiredmems[requiredcore] = requiredmem;
452 bool gcfindSpareMem(unsigned int * startaddr,unsigned int * tomove,unsigned int * dstcore,unsigned int requiredmem,unsigned int requiredcore) {
453 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
454 for(int k = 0; k < NUMCORES4GC; k++) {
455 if((gccorestatus[k] == 0) && (gcfilledblocks[k] < gcstopblock[k])) {
456 // check if this stopped core has enough mem
457 assignSpareMem_I(k, requiredmem, tomove, startaddr);
459 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
463 // if can not find spare mem right now, hold the request
464 gcrequiredmems[requiredcore] = requiredmem;
466 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
470 INLINE bool compacthelper(struct moveHelper * orig,struct moveHelper * to,int * filledblocks,unsigned int * heaptopptr,bool * localcompact, bool lbmove) {
471 bool loadbalancemove = lbmove;
472 // scan over all objs in this block, compact the marked objs
473 // loop stop when finishing either scanning all active objs or
474 // fulfilled the gcstopblock
476 while((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) {
477 if(moveobj(orig, to, gcblock2fill)) {
481 CACHEADAPT_SAMPLING_DATA_CONVERT(to->ptr);
482 // if no objs have been compact, do nothing,
483 // otherwise, fill the header of this block
484 if(to->offset > (unsigned int)BAMBOO_CACHE_LINE_SIZE) {
485 CLOSEBLOCK(to->base, to->offset);
489 to->top -= BAMBOO_CACHE_LINE_SIZE;
492 *heaptopptr = to->ptr;
493 *filledblocks = to->numblocks;
495 /*if(loadbalancemove) {
496 // write back to the Main Memory and release any DTLB entry for the
497 // last block as someone else might later write into it
498 // flush the shared heap
499 BAMBOO_CACHE_FLUSH_L2();
500 //loadbalancemove = false;
503 // send msgs to core coordinator indicating that the compact is finishing
504 // send compact finish message to core coordinator
505 if(STARTUPCORE == BAMBOO_NUM_OF_CORE) {
506 gcfilledblocks[BAMBOO_NUM_OF_CORE] = *filledblocks;
507 gcloads[BAMBOO_NUM_OF_CORE] = *heaptopptr;
508 //tprintf("--finish compact: %d, %d, %d, %x, %x \n", BAMBOO_NUM_OF_CORE, loadbalancemove, *filledblocks, *heaptopptr, gccurr_heaptop);
509 if((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) {
512 if(gcfindSpareMem(&gcmovestartaddr,&gcblock2fill,&gcdstcore,gccurr_heaptop,BAMBOO_NUM_OF_CORE)) {
518 gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
520 // write back to the Main Memory and release any DTLB entry for the
521 // last block as someone else might later write into it
522 // flush the shared heap
523 //BAMBOO_CACHE_FLUSH_L2();
527 if((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) {
530 //tprintf("finish compact: %d, %d, %d, %x, %x \n", BAMBOO_NUM_OF_CORE, loadbalancemove, *filledblocks, *heaptopptr, gccurr_heaptop);
531 send_msg_6(STARTUPCORE,GCFINISHCOMPACT,BAMBOO_NUM_OF_CORE,loadbalancemove,*filledblocks,*heaptopptr,gccurr_heaptop);
533 //tprintf("++ finish compact: %d, %d, %d, %x, %x \n", BAMBOO_NUM_OF_CORE, loadbalancemove, *filledblocks, *heaptopptr, 0);
535 send_msg_6(STARTUPCORE,GCFINISHCOMPACT,BAMBOO_NUM_OF_CORE,loadbalancemove,*filledblocks,*heaptopptr, 0);
536 // write back to the Main Memory and release any DTLB entry for the
537 // last block as someone else might later write into it.
538 // flush the shared heap
539 //BAMBOO_CACHE_FLUSH_L2();
543 if(orig->ptr < gcmarkedptrbound) {
544 // still have unpacked obj
547 loadbalancemove = true;
548 //tprintf("move start: %x, %d \n", gcmovestartaddr, gcdstcore);
551 to->ptr = gcmovestartaddr;
552 to->numblocks = gcblock2fill - 1;
553 to->bound = BLOCKBOUND(to->numblocks);
554 BASEPTR(gcdstcore, to->numblocks, &(to->base));
555 to->offset = to->ptr - to->base;
556 to->top=(to->numblocks==0)?(to->offset):(to->bound-BAMBOO_SMEM_SIZE+to->offset);
558 to->offset = BAMBOO_CACHE_LINE_SIZE;
559 to->ptr += to->offset; // for header
560 to->top += to->offset;
561 *localcompact = (gcdstcore == BAMBOO_NUM_OF_CORE);
562 CACHEADAPT_SAMPLING_DATA_REVISE_INIT(orig, to);
569 BAMBOO_ASSERT(COMPACTPHASE == gc_status_info.gcphase);
572 // initialize pointers for comapcting
573 struct moveHelper * orig = (struct moveHelper *)RUNMALLOC(sizeof(struct moveHelper));
574 struct moveHelper * to = (struct moveHelper *)RUNMALLOC(sizeof(struct moveHelper));
575 if(!initOrig_Dst(orig, to)) {
576 // no available data to compact
577 // send compact finish msg to STARTUP core
578 send_msg_6(STARTUPCORE,GCFINISHCOMPACT,BAMBOO_NUM_OF_CORE,false,0,to->base,0);
582 CACHEADAPT_SAMPLING_DATA_REVISE_INIT(orig, to);
584 unsigned int filledblocks = 0;
585 unsigned int heaptopptr = 0;
586 bool localcompact = true;
587 compacthelper(orig, to, &filledblocks, &heaptopptr, &localcompact, false);
593 void compact_master(struct moveHelper * orig, struct moveHelper * to) {
594 // initialize pointers for comapcting
595 initOrig_Dst(orig, to);
596 CACHEADAPT_SAMPLING_DATA_REVISE_INIT(orig, to);
597 int filledblocks = 0;
598 unsigned int heaptopptr = 0;
599 bool finishcompact = false;
600 bool iscontinue = true;
601 bool localcompact = true;
603 while((COMPACTPHASE == gc_status_info.gcphase) || (SUBTLECOMPACTPHASE == gc_status_info.gcphase)) {
604 if((!finishcompact) && iscontinue) {
605 finishcompact = compacthelper(orig,to,&filledblocks,&heaptopptr,&localcompact, lbmove);
608 if(gc_checkCoreStatus()) {
609 // all cores have finished compacting restore the gcstatus of all cores
610 gc_resetCoreStatus();
613 // check if there are spare mem for pending move requires
614 if(COMPACTPHASE == gc_status_info.gcphase) {
615 resolvePendingMoveRequest();
623 to->ptr = gcmovestartaddr;
624 to->numblocks = gcblock2fill - 1;
625 to->bound = BLOCKBOUND(to->numblocks);
626 BASEPTR(gcdstcore, to->numblocks, &(to->base));
627 to->offset = to->ptr - to->base;
628 to->top = (to->numblocks==0)?(to->offset):(to->bound-BAMBOO_SMEM_SIZE+to->offset);
630 to->offset = BAMBOO_CACHE_LINE_SIZE;
631 to->ptr += to->offset; // for header
632 to->top += to->offset;
633 localcompact = (gcdstcore == BAMBOO_NUM_OF_CORE);
637 } else if(!finishcompact) {
645 #endif // MULTICORE_GC