2 #include "multicoregccompact.h"
3 #include "runtime_arch.h"
4 #include "multicoreruntime.h"
6 INLINE bool gc_checkCoreStatus() {
7 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
8 for(int i = 0; i < NUMCORES4GC; ++i) {
9 if(gccorestatus[i] != 0) {
10 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
14 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
18 INLINE void gc_resetCoreStatus() {
19 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
20 for(int i = 0; i < NUMCORES4GC; ++i) {
23 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
26 // should be invoked with interrupt closed
27 int assignSpareMem_I(unsigned int sourcecore,
28 unsigned int * requiredmem,
29 unsigned int * tomove,
30 unsigned int * startaddr) {
32 BLOCKINDEX(gcloads[sourcecore], &b);
33 unsigned int boundptr = (b<NUMCORES4GC) ? ((b+1)*BAMBOO_SMEM_SIZE_L)
34 : (BAMBOO_LARGE_SMEM_BOUND+(b-NUMCORES4GC+1)*BAMBOO_SMEM_SIZE);
35 unsigned int remain = boundptr - gcloads[sourcecore];
36 unsigned int memneed = requiredmem + BAMBOO_CACHE_LINE_SIZE;
37 *startaddr = gcloads[sourcecore];
38 *tomove = gcfilledblocks[sourcecore] + 1;
39 if(memneed < remain) {
40 gcloads[sourcecore] += memneed;
43 // next available block
44 gcfilledblocks[sourcecore] += 1;
45 unsigned int newbase = 0;
46 BASEPTR(sourcecore, gcfilledblocks[sourcecore], &newbase);
47 gcloads[sourcecore] = newbase;
48 return requiredmem-remain;
52 int assignSpareMem(unsigned int sourcecore,
53 unsigned int * requiredmem,
54 unsigned int * tomove,
55 unsigned int * startaddr) {
56 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
58 BLOCKINDEX(gcloads[sourcecore], &b);
59 unsigned int boundptr = (b<NUMCORES4GC) ? ((b+1)*BAMBOO_SMEM_SIZE_L)
60 : (BAMBOO_LARGE_SMEM_BOUND+(b-NUMCORES4GC+1)*BAMBOO_SMEM_SIZE);
61 unsigned int remain = boundptr - gcloads[sourcecore];
62 unsigned int memneed = requiredmem + BAMBOO_CACHE_LINE_SIZE;
63 *startaddr = gcloads[sourcecore];
64 *tomove = gcfilledblocks[sourcecore] + 1;
65 if(memneed < remain) {
66 gcloads[sourcecore] += memneed;
67 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
70 // next available block
71 gcfilledblocks[sourcecore] += 1;
72 unsigned int newbase = 0;
73 BASEPTR(sourcecore, gcfilledblocks[sourcecore], &newbase);
74 gcloads[sourcecore] = newbase;
75 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
76 return requiredmem-remain;
80 INLINE void compact2Heaptophelper_I(unsigned int coren,
82 unsigned int* numblocks,
83 unsigned int* remain) {
85 unsigned int memneed = gcrequiredmems[coren] + BAMBOO_CACHE_LINE_SIZE;
86 if(STARTUPCORE == coren) {
89 gcdstcore = gctopcore;
90 gcblock2fill = *numblocks + 1;
92 if(BAMBOO_CHECK_SEND_MODE()) {
93 cache_msg_4_I(coren,GCMOVESTART,gctopcore,*p,(*numblocks)+1);
95 send_msg_4_I(coren,GCMOVESTART,gctopcore,*p,(*numblocks)+1);
98 if(memneed < *remain) {
100 gcrequiredmems[coren] = 0;
101 gcloads[gctopcore] += memneed;
102 *remain = *remain - memneed;
104 // next available block
106 gcfilledblocks[gctopcore] += 1;
107 unsigned int newbase = 0;
108 BASEPTR(gctopcore, gcfilledblocks[gctopcore], &newbase);
109 gcloads[gctopcore] = newbase;
110 gcrequiredmems[coren] -= *remain - BAMBOO_CACHE_LINE_SIZE;
111 gcstopblock[gctopcore]++;
112 gctopcore = NEXTTOPCORE(gctopblock);
114 *numblocks = gcstopblock[gctopcore];
115 *p = gcloads[gctopcore];
117 *remain=GC_BLOCK_REMAIN_SIZE(b, (*p));
122 INLINE void compact2Heaptop() {
123 // no cores with spare mem and some cores are blocked with pending move
124 // find the current heap top and make them move to the heap top
126 unsigned int numblocks = gcfilledblocks[gctopcore];
127 p = gcloads[gctopcore];
130 unsigned int remain=GC_BLOCK_REMAIN_SIZE(b, p);
131 // check if the top core finishes
132 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
133 if(gccorestatus[gctopcore] != 0) {
134 // let the top core finishes its own work first
135 compact2Heaptophelper_I(gctopcore, &p, &numblocks, &remain);
136 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
139 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
141 for(int i = 0; i < NUMCORES4GC; i++) {
142 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
143 if((gccorestatus[i] != 0) && (gcrequiredmems[i] > 0)) {
144 compact2Heaptophelper_I(i, &p, &numblocks, &remain);
145 if(gccorestatus[gctopcore] != 0) {
146 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
147 // the top core is not free now
151 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
155 INLINE void resolvePendingMoveRequest() {
158 bool nosparemem = true;
159 bool haspending = false;
160 bool hasrunning = false;
161 bool noblock = false;
162 unsigned int dstcore = 0; // the core who need spare mem
163 unsigned int sourcecore = 0; // the core who has spare mem
164 for(i = j = 0; (i < NUMCORES4GC) && (j < NUMCORES4GC); ) {
166 // check if there are cores with spare mem
167 if(gccorestatus[i] == 0) {
168 // finished working, check if it still have spare mem
169 if(gcfilledblocks[i] < gcstopblock[i]) {
170 // still have spare mem
178 if(gccorestatus[j] != 0) {
179 // not finished, check if it has pending move requests
180 if((gcfilledblocks[j]==gcstopblock[j])&&(gcrequiredmems[j]>0)) {
189 if(!nosparemem && haspending) {
191 unsigned int tomove = 0;
192 unsigned int startaddr = 0;
193 gcrequiredmems[dstcore] = assignSpareMem(sourcecore,
194 gcrequiredmems[dstcore],
197 if(STARTUPCORE == dstcore) {
198 gcdstcore = sourcecore;
200 gcmovestartaddr = startaddr;
201 gcblock2fill = tomove;
203 send_msg_4(dstcore,GCMOVESTART,sourcecore,startaddr,tomove);
212 if(!hasrunning && !noblock) {
213 gcphase = SUBTLECOMPACTPHASE;
218 // If out of boundary of valid shared memory, return false, else return true
219 INLINE bool nextSBlock(struct moveHelper * orig) {
220 orig->blockbase = orig->blockbound;
222 bool sbchanged = false;
223 unsigned int origptr = orig->ptr;
224 unsigned int blockbase = orig->blockbase;
225 unsigned int blockbound = orig->blockbound;
226 unsigned int bound = orig->bound;
228 // check if across a big block
229 // TODO now do not zero out the whole memory, maybe the last two conditions
231 if((blockbase>=bound)||(origptr>=bound)
232 ||((origptr!=NULL)&&(*((int*)origptr))==0)||((*((int*)blockbase))==0)) {
234 // end of current heap block, jump to next one
236 BASEPTR(BAMBOO_NUM_OF_CORE, orig->numblocks, &(orig->base));
237 if(orig->base >= gcbaseva + BAMBOO_SHARED_MEM_SIZE) {
239 orig->ptr = orig->base; // set current ptr to out of boundary too
242 orig->blockbase = orig->base;
244 (unsigned int)(orig->blockbase-gcbaseva)/BAMBOO_SMEM_SIZE;
246 unsigned int blocknum = 0;
247 BLOCKINDEX(orig->base, &blocknum);
248 if(bamboo_smemtbl[blocknum] == 0) {
250 goto innernextSBlock;
252 // check the bamboo_smemtbl to decide the real bound
253 orig->bound = orig->base + bamboo_smemtbl[blocknum];
254 } else if(0 == (orig->blockbase%BAMBOO_SMEM_SIZE)) {
255 orig->sblockindex += 1;
259 // check if this sblock should be skipped or have special start point
260 int sbstart = gcsbstarttbl[orig->sblockindex];
263 orig->sblockindex += 1;
264 orig->blockbase += BAMBOO_SMEM_SIZE;
265 goto outernextSBlock;
266 } else if((sbstart != 0) && (sbchanged)) {
267 // the first time to access this SBlock
268 // not start from the very beginning
269 orig->blockbase = sbstart;
272 // setup information for this sblock
273 orig->blockbound = orig->blockbase+(unsigned int)*((int*)(orig->blockbase));
274 orig->offset = BAMBOO_CACHE_LINE_SIZE;
275 orig->ptr = orig->blockbase + orig->offset;
276 if(orig->ptr >= orig->bound) {
277 // met a lobj, move to next block
278 goto innernextSBlock;
284 // return false if there are no available data to compact
285 INLINE bool initOrig_Dst(struct moveHelper * orig,
286 struct moveHelper * to) {
289 to->top = to->offset = BAMBOO_CACHE_LINE_SIZE;
290 to->bound = BAMBOO_SMEM_SIZE_L;
291 BASEPTR(BAMBOO_NUM_OF_CORE, to->numblocks, &(to->base));
293 unsigned int tobase = to->base;
294 to->ptr = tobase + to->offset;
299 unsigned int blocknum = 0;
300 BLOCKINDEX(orig->base, &blocknum);
301 unsigned int origbase = orig->base;
302 // check the bamboo_smemtbl to decide the real bound
303 orig->bound = origbase + (unsigned int)bamboo_smemtbl[blocknum];
304 orig->blockbase = origbase;
305 orig->sblockindex = (unsigned int)(origbase - gcbaseva) / BAMBOO_SMEM_SIZE;
307 int sbstart = gcsbstarttbl[orig->sblockindex];
310 orig->blockbound=gcbaseva+BAMBOO_SMEM_SIZE*(orig->sblockindex+1);
311 return nextSBlock(orig);
312 } else if(sbstart != 0) {
313 orig->blockbase = sbstart;
315 orig->blockbound = orig->blockbase + *((int*)(orig->blockbase));
316 orig->offset = BAMBOO_CACHE_LINE_SIZE;
317 orig->ptr = orig->blockbase + orig->offset;
322 INLINE void nextBlock(struct moveHelper * to) {
323 to->top = to->bound + BAMBOO_CACHE_LINE_SIZE; // header!
324 to->bound += BAMBOO_SMEM_SIZE;
326 BASEPTR(BAMBOO_NUM_OF_CORE, to->numblocks, &(to->base));
327 to->offset = BAMBOO_CACHE_LINE_SIZE;
328 to->ptr = to->base + to->offset;
331 INLINE unsigned int findValidObj(struct moveHelper * orig,
332 struct moveHelper * to,
334 unsigned int size = 0;
336 CACHEADAPT_COMPLETE_PAGE_CONVERT(orig, to, to->ptr, false);
337 unsigned int origptr = (unsigned int)(orig->ptr);
338 unsigned int origbound = (unsigned int)orig->bound;
339 unsigned int origblockbound = (unsigned int)orig->blockbound;
340 if((origptr >= origbound) || (origptr == origblockbound)) {
341 if(!nextSBlock(orig)) {
342 // finished, no more data
347 // check the obj's type, size and mark flag
348 *type = ((int *)(origptr))[0];
351 // end of this block, go to next one
352 if(!nextSBlock(orig)) {
353 // finished, no more data
357 } else if(*type < NUMCLASSES) {
359 size = classsize[*type];
362 struct ArrayObject *ao=(struct ArrayObject *)(origptr);
363 unsigned int elementsize=classsize[*type];
364 unsigned int length=ao->___length___;
365 size=(unsigned int)sizeof(struct ArrayObject)
366 +(unsigned int)(length*elementsize);
372 // endaddr does not contain spaces for headers
373 INLINE bool moveobj(struct moveHelper * orig, struct moveHelper * to, unsigned int stopblock) {
379 unsigned int size = findValidObj(orig, to, &type);
380 unsigned int isize = 0;
383 // finished, no more data
386 ALIGNSIZE(size, &isize); // no matter is the obj marked or not
387 // should be able to across
388 unsigned int origptr = (unsigned int)(orig->ptr);
389 if(((struct ___Object___ *)origptr)->marked == MARKED) {
390 unsigned int totop = (unsigned int)to->top;
391 unsigned int tobound = (unsigned int)to->bound;
392 GCPROFILE_RECORD_LIVE_OBJ();
393 // marked obj, copy it to current heap top
394 // check to see if remaining space is enough
395 if((unsigned int)(totop + isize) > tobound) {
396 // fill 0 indicating the end of this block
397 BAMBOO_MEMSET_WH(to->ptr, '\0', tobound - totop);
398 // fill the header of this block and then go to next block
399 to->offset += tobound - totop;
400 CLOSEBLOCK(to->base, to->offset);
401 #ifdef GC_CACHE_ADAPT
402 unsigned int tmp_ptr = to->ptr;
405 #ifdef GC_CACHE_ADAPT
406 CACHEADAPT_COMPLETE_PAGE_CONVERT(orig, to, tmp_ptr, true);
408 if(stopblock == to->numblocks) {
409 // already fulfilled the block
413 // set the mark field to 2, indicating that this obj has been moved
414 // and need to be flushed
415 ((struct ___Object___ *)origptr)->marked = COMPACTED;
416 unsigned int toptr = (unsigned int)to->ptr;
417 if(toptr != origptr) {
418 if((unsigned int)(origptr) < (unsigned int)(toptr+size)) {
419 memmove(toptr, origptr, size);
421 memcpy(toptr, origptr, size);
423 // fill the remaining space with -2
424 BAMBOO_MEMSET_WH((unsigned int)(toptr+size), -2, isize-size);
426 // store mapping info
427 gcmappingtbl[OBJMAPPINGINDEX((unsigned int)origptr)]=(unsigned int)toptr;
428 gccurr_heaptop -= isize;
432 #ifdef GC_CACHE_ADAPT
433 unsigned int tmp_ptr = to->ptr;
434 #endif // GC_CACHE_ADAPT
435 if(to->top == to->bound) {
436 CLOSEBLOCK(to->base, to->offset);
439 #ifdef GC_CACHE_ADAPT
440 CACHEADAPT_COMPLETE_PAGE_CONVERT(orig, to, tmp_ptr, true);
447 return ((((unsigned int)(orig->ptr) > (unsigned int)(orig->bound))
448 || ((unsigned int)(orig->ptr) == (unsigned int)(orig->blockbound)))
449 &&!nextSBlock(orig));
452 // should be invoked with interrupt closed
453 bool gcfindSpareMem_I(unsigned int * startaddr,
454 unsigned int * tomove,
455 unsigned int * dstcore,
456 unsigned int requiredmem,
457 unsigned int requiredcore) {
458 for(int k = 0; k < NUMCORES4GC; k++) {
459 if((gccorestatus[k] == 0) && (gcfilledblocks[k] < gcstopblock[k])) {
460 // check if this stopped core has enough mem
461 assignSpareMem_I(k, requiredmem, tomove, startaddr);
466 // if can not find spare mem right now, hold the request
467 gcrequiredmems[requiredcore] = requiredmem;
472 bool gcfindSpareMem(unsigned int * startaddr,
473 unsigned int * tomove,
474 unsigned int * dstcore,
475 unsigned int requiredmem,
476 unsigned int requiredcore) {
477 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
478 for(int k = 0; k < NUMCORES4GC; k++) {
479 if((gccorestatus[k] == 0) && (gcfilledblocks[k] < gcstopblock[k])) {
480 // check if this stopped core has enough mem
481 assignSpareMem_I(k, requiredmem, tomove, startaddr);
483 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
487 // if can not find spare mem right now, hold the request
488 gcrequiredmems[requiredcore] = requiredmem;
490 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
494 INLINE bool compacthelper(struct moveHelper * orig,
495 struct moveHelper * to,
497 unsigned int * heaptopptr,
498 bool * localcompact) {
499 // scan over all objs in this block, compact the marked objs
500 // loop stop when finishing either scanning all active objs or
501 // fulfilled the gcstopblock
503 while((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) {
504 if(moveobj(orig, to, gcblock2fill)) {
508 CACHEADAPT_SAMPLING_DATA_CONVERT(to->ptr);
509 // if no objs have been compact, do nothing,
510 // otherwise, fill the header of this block
511 if(to->offset > (unsigned int)BAMBOO_CACHE_LINE_SIZE) {
512 CLOSEBLOCK(to->base, to->offset);
516 to->top -= BAMBOO_CACHE_LINE_SIZE;
519 *heaptopptr = to->ptr;
520 *filledblocks = to->numblocks;
523 // send msgs to core coordinator indicating that the compact is finishing
524 // send compact finish message to core coordinator
525 if(STARTUPCORE == BAMBOO_NUM_OF_CORE) {
526 gcfilledblocks[BAMBOO_NUM_OF_CORE] = *filledblocks;
527 gcloads[BAMBOO_NUM_OF_CORE] = *heaptopptr;
528 if((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) {
531 if(gcfindSpareMem(&gcmovestartaddr, &gcblock2fill, &gcdstcore,
532 gccurr_heaptop, BAMBOO_NUM_OF_CORE)) {
538 gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
543 if((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) {
546 send_msg_5(STARTUPCORE,GCFINISHCOMPACT,BAMBOO_NUM_OF_CORE,*filledblocks,*heaptopptr,gccurr_heaptop);
549 send_msg_5(STARTUPCORE,GCFINISHCOMPACT,BAMBOO_NUM_OF_CORE,*filledblocks,*heaptopptr, 0);
553 if(orig->ptr < gcmarkedptrbound) {
554 // still have unpacked obj
559 to->ptr = gcmovestartaddr;
560 to->numblocks = gcblock2fill - 1;
561 to->bound = ((to->numblocks==0)?BAMBOO_SMEM_SIZE_L:BAMBOO_SMEM_SIZE_L)+BAMBOO_SMEM_SIZE*to->numblocks;
562 BASEPTR(gcdstcore, to->numblocks, &(to->base));
563 to->offset = to->ptr - to->base;
564 to->top = (to->numblocks==0)?(to->offset):(to->bound-BAMBOO_SMEM_SIZE+to->offset);
566 to->offset = BAMBOO_CACHE_LINE_SIZE;
567 to->ptr += to->offset; // for header
568 to->top += to->offset;
569 *localcompact = (gcdstcore == BAMBOO_NUM_OF_CORE);
570 CACHEADAPT_SAMPLING_DATA_REVISE_INIT();
577 BAMBOO_ASSERT(COMPACTPHASE == gcphase);
579 // initialize pointers for comapcting
580 struct moveHelper * orig = (struct moveHelper *)RUNMALLOC(sizeof(struct moveHelper));
581 struct moveHelper * to = (struct moveHelper *)RUNMALLOC(sizeof(struct moveHelper));
582 if(!initOrig_Dst(orig, to)) {
583 // no available data to compact
584 // send compact finish msg to STARTUP core
585 send_msg_5(STARTUPCORE,GCFINISHCOMPACT,BAMBOO_NUM_OF_CORE,0,to->base,0);
589 CACHEADAPT_SAMPLING_DATA_REVISE_INIT();
591 unsigned int filledblocks = 0;
592 unsigned int heaptopptr = 0;
593 bool localcompact = true;
594 compacthelper(orig, to, &filledblocks, &heaptopptr, &localcompact);
600 void compact_master(struct moveHelper * orig, struct moveHelper * to) {
601 // initialize pointers for comapcting
602 initOrig_Dst(orig, to);
603 CACHEADAPT_SAMPLING_DATA_REVISE_INIT();
604 int filledblocks = 0;
605 unsigned int heaptopptr = 0;
606 bool finishcompact = false;
607 bool iscontinue = true;
608 bool localcompact = true;
609 while((COMPACTPHASE == gcphase) || (SUBTLECOMPACTPHASE == gcphase)) {
610 if((!finishcompact) && iscontinue) {
611 finishcompact = compacthelper(orig,to,&filledblocks,&heaptopptr,&localcompact);
614 if(gc_checkCoreStatus()) {
615 // all cores have finished compacting restore the gcstatus of all cores
616 gc_resetCoreStatus();
619 // check if there are spare mem for pending move requires
620 if(COMPACTPHASE == gcphase) {
621 resolvePendingMoveRequest();
628 to->ptr = gcmovestartaddr;
629 to->numblocks = gcblock2fill - 1;
630 to->bound = (to->numblocks==0) ? BAMBOO_SMEM_SIZE_L : BAMBOO_SMEM_SIZE_L+BAMBOO_SMEM_SIZE*to->numblocks;
631 BASEPTR(gcdstcore, to->numblocks, &(to->base));
632 to->offset = to->ptr - to->base;
633 to->top = (to->numblocks==0)?(to->offset):(to->bound-BAMBOO_SMEM_SIZE+to->offset);
635 to->offset = BAMBOO_CACHE_LINE_SIZE;
636 to->ptr += to->offset; // for header
637 to->top += to->offset;
638 localcompact = (gcdstcore == BAMBOO_NUM_OF_CORE);
641 } else if(!finishcompact) {
648 #endif // MULTICORE_GC