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)
348 +(unsigned int)(length*elementsize);
354 // endaddr does not contain spaces for headers
355 INLINE bool moveobj(struct moveHelper * orig, struct moveHelper * to, unsigned int stopblock) {
361 unsigned int size = findValidObj(orig, to, &type);
362 unsigned int isize = 0;
365 // finished, no more data
368 ALIGNSIZE(size, &isize); // no matter is the obj marked or not
369 // should be able to across
370 unsigned int origptr = (unsigned int)(orig->ptr);
371 if(((struct ___Object___ *)origptr)->marked == MARKED) {
372 unsigned int totop = (unsigned int)to->top;
373 unsigned int tobound = (unsigned int)to->bound;
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 #ifdef GC_CACHE_ADAPT
388 CACHEADAPT_COMPLETE_PAGE_CONVERT(orig, to, tmp_ptr, true);
390 if(stopblock == to->numblocks) {
391 // already fulfilled the block
395 // set the mark field to 2, indicating that this obj has been moved
396 // and need to be flushed
397 ((struct ___Object___ *)origptr)->marked = COMPACTED;
398 unsigned int toptr = (unsigned int)to->ptr;
399 if(toptr != origptr) {
400 if((unsigned int)(origptr) < (unsigned int)(toptr+size)) {
401 memmove(toptr, origptr, size);
403 memcpy(toptr, origptr, size);
405 // fill the remaining space with -2
406 BAMBOO_MEMSET_WH((unsigned int)(toptr+size), -2, isize-size);
408 // store mapping info
409 gcmappingtbl[OBJMAPPINGINDEX((unsigned int)origptr)]=(unsigned int)toptr;
410 gccurr_heaptop -= isize;
414 #ifdef GC_CACHE_ADAPT
415 unsigned int tmp_ptr = to->ptr;
416 #endif // GC_CACHE_ADAPT
417 if(to->top == to->bound) {
418 CLOSEBLOCK(to->base, to->offset);
421 #ifdef GC_CACHE_ADAPT
422 CACHEADAPT_COMPLETE_PAGE_CONVERT(orig, to, tmp_ptr, true);
429 return ((((unsigned int)(orig->ptr) > (unsigned int)(orig->bound))||((unsigned int)(orig->ptr) == (unsigned int)(orig->blockbound)))&&!nextSBlock(orig));
432 // should be invoked with interrupt closed
433 bool gcfindSpareMem_I(unsigned int * startaddr,unsigned int * tomove,unsigned int * dstcore,unsigned int requiredmem,unsigned int requiredcore) {
434 for(int k = 0; k < NUMCORES4GC; k++) {
435 if((gccorestatus[k] == 0) && (gcfilledblocks[k] < gcstopblock[k])) {
436 // check if this stopped core has enough mem
437 assignSpareMem_I(k, requiredmem, tomove, startaddr);
442 // if can not find spare mem right now, hold the request
443 gcrequiredmems[requiredcore] = requiredmem;
448 bool gcfindSpareMem(unsigned int * startaddr,unsigned int * tomove,unsigned int * dstcore,unsigned int requiredmem,unsigned int requiredcore) {
449 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
450 for(int k = 0; k < NUMCORES4GC; k++) {
451 if((gccorestatus[k] == 0) && (gcfilledblocks[k] < gcstopblock[k])) {
452 // check if this stopped core has enough mem
453 assignSpareMem_I(k, requiredmem, tomove, startaddr);
455 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
459 // if can not find spare mem right now, hold the request
460 gcrequiredmems[requiredcore] = requiredmem;
462 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
466 INLINE bool compacthelper(struct moveHelper * orig,struct moveHelper * to,int * filledblocks,unsigned int * heaptopptr,bool * localcompact) {
467 // scan over all objs in this block, compact the marked objs
468 // loop stop when finishing either scanning all active objs or
469 // fulfilled the gcstopblock
471 while((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) {
472 if(moveobj(orig, to, gcblock2fill)) {
476 CACHEADAPT_SAMPLING_DATA_CONVERT(to->ptr);
477 // if no objs have been compact, do nothing,
478 // otherwise, fill the header of this block
479 if(to->offset > (unsigned int)BAMBOO_CACHE_LINE_SIZE) {
480 CLOSEBLOCK(to->base, to->offset);
484 to->top -= BAMBOO_CACHE_LINE_SIZE;
487 *heaptopptr = to->ptr;
488 *filledblocks = to->numblocks;
491 // send msgs to core coordinator indicating that the compact is finishing
492 // send compact finish message to core coordinator
493 if(STARTUPCORE == BAMBOO_NUM_OF_CORE) {
494 gcfilledblocks[BAMBOO_NUM_OF_CORE] = *filledblocks;
495 gcloads[BAMBOO_NUM_OF_CORE] = *heaptopptr;
496 if((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) {
499 if(gcfindSpareMem(&gcmovestartaddr,&gcblock2fill,&gcdstcore,gccurr_heaptop,BAMBOO_NUM_OF_CORE)) {
505 gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
510 if((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) {
513 send_msg_5(STARTUPCORE,GCFINISHCOMPACT,BAMBOO_NUM_OF_CORE,*filledblocks,*heaptopptr,gccurr_heaptop);
516 send_msg_5(STARTUPCORE,GCFINISHCOMPACT,BAMBOO_NUM_OF_CORE,*filledblocks,*heaptopptr, 0);
520 if(orig->ptr < gcmarkedptrbound) {
521 // still have unpacked obj
526 to->ptr = gcmovestartaddr;
527 to->numblocks = gcblock2fill - 1;
528 to->bound = BLOCKBOUND(to->numblocks);
529 BASEPTR(gcdstcore, to->numblocks, &(to->base));
530 to->offset = to->ptr - to->base;
531 to->top=(to->numblocks==0)?(to->offset):(to->bound-BAMBOO_SMEM_SIZE+to->offset);
533 to->offset = BAMBOO_CACHE_LINE_SIZE;
534 to->ptr += to->offset; // for header
535 to->top += to->offset;
536 *localcompact = (gcdstcore == BAMBOO_NUM_OF_CORE);
537 CACHEADAPT_SAMPLING_DATA_REVISE_INIT(orig, to);
544 BAMBOO_ASSERT(COMPACTPHASE == gc_status_info.gcphase);
546 // initialize pointers for comapcting
547 struct moveHelper * orig = (struct moveHelper *)RUNMALLOC(sizeof(struct moveHelper));
548 struct moveHelper * to = (struct moveHelper *)RUNMALLOC(sizeof(struct moveHelper));
549 if(!initOrig_Dst(orig, to)) {
550 // no available data to compact
551 // send compact finish msg to STARTUP core
552 send_msg_5(STARTUPCORE,GCFINISHCOMPACT,BAMBOO_NUM_OF_CORE,0,to->base,0);
556 CACHEADAPT_SAMPLING_DATA_REVISE_INIT(orig, to);
558 unsigned int filledblocks = 0;
559 unsigned int heaptopptr = 0;
560 bool localcompact = true;
561 compacthelper(orig, to, &filledblocks, &heaptopptr, &localcompact);
567 void compact_master(struct moveHelper * orig, struct moveHelper * to) {
568 // initialize pointers for comapcting
569 initOrig_Dst(orig, to);
570 CACHEADAPT_SAMPLING_DATA_REVISE_INIT(orig, to);
571 int filledblocks = 0;
572 unsigned int heaptopptr = 0;
573 bool finishcompact = false;
574 bool iscontinue = true;
575 bool localcompact = true;
576 while((COMPACTPHASE == gc_status_info.gcphase) || (SUBTLECOMPACTPHASE == gc_status_info.gcphase)) {
577 if((!finishcompact) && iscontinue) {
578 finishcompact = compacthelper(orig,to,&filledblocks,&heaptopptr,&localcompact);
581 if(gc_checkCoreStatus()) {
582 // all cores have finished compacting restore the gcstatus of all cores
583 gc_resetCoreStatus();
586 // check if there are spare mem for pending move requires
587 if(COMPACTPHASE == gc_status_info.gcphase) {
588 resolvePendingMoveRequest();
595 to->ptr = gcmovestartaddr;
596 to->numblocks = gcblock2fill - 1;
597 to->bound = BLOCKBOUND(to->numblocks);
598 BASEPTR(gcdstcore, to->numblocks, &(to->base));
599 to->offset = to->ptr - to->base;
600 to->top = (to->numblocks==0)?(to->offset):(to->bound-BAMBOO_SMEM_SIZE+to->offset);
602 to->offset = BAMBOO_CACHE_LINE_SIZE;
603 to->ptr += to->offset; // for header
604 to->top += to->offset;
605 localcompact = (gcdstcore == BAMBOO_NUM_OF_CORE);
608 } else if(!finishcompact) {
615 #endif // MULTICORE_GC