2 #include "multicoregccompact.h"
3 #include "runtime_arch.h"
4 #include "multicoreruntime.h"
8 INLINE bool gc_checkCoreStatus_I() {
10 for(i = 0; i < NUMCORES4GC; ++i) {
11 if(gccorestatus[i] != 0) {
15 return (i == NUMCORES4GC);
18 INLINE void compact2Heaptophelper_I(unsigned int coren,
20 unsigned int* numblocks,
21 unsigned int* remain) {
23 unsigned int memneed = gcrequiredmems[coren] + BAMBOO_CACHE_LINE_SIZE;
24 if(STARTUPCORE == coren) {
27 gcdstcore = gctopcore;
28 gcblock2fill = *numblocks + 1;
30 send_msg_4(coren, GCMOVESTART, gctopcore, *p, (*numblocks) + 1, false);
32 if(memneed < *remain) {
34 gcrequiredmems[coren] = 0;
35 gcloads[gctopcore] += memneed;
36 *remain = *remain - memneed;
38 // next available block
40 gcfilledblocks[gctopcore] += 1;
41 unsigned int newbase = 0;
42 BASEPTR(gctopcore, gcfilledblocks[gctopcore], &newbase);
43 gcloads[gctopcore] = newbase;
44 gcrequiredmems[coren] -= *remain - BAMBOO_CACHE_LINE_SIZE;
45 gcstopblock[gctopcore]++;
46 gctopcore = NEXTTOPCORE(gctopblock);
48 *numblocks = gcstopblock[gctopcore];
49 *p = gcloads[gctopcore];
51 *remain=GC_BLOCK_REMAIN_SIZE(b, (*p));
56 INLINE void compact2Heaptop() {
57 // no cores with spare mem and some cores are blocked with pending move
58 // find the current heap top and make them move to the heap top
60 unsigned int numblocks = gcfilledblocks[gctopcore];
61 p = gcloads[gctopcore];
64 unsigned int remain=GC_BLOCK_REMAIN_SIZE(b, p);
65 // check if the top core finishes
66 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
67 if(gccorestatus[gctopcore] != 0) {
68 // let the top core finishes its own work first
69 compact2Heaptophelper_I(gctopcore, &p, &numblocks, &remain);
70 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
73 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
75 for(int i = 0; i < NUMCORES4GC; i++) {
76 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
77 if((gccorestatus[i] != 0) && (gcrequiredmems[i] > 0)) {
78 compact2Heaptophelper_I(i, &p, &numblocks, &remain);
79 if(gccorestatus[gctopcore] != 0) {
80 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
81 // the top core is not free now
85 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
89 INLINE void resolvePendingMoveRequest() {
92 bool nosparemem = true;
93 bool haspending = false;
94 bool hasrunning = false;
96 unsigned int dstcore = 0; // the core who need spare mem
97 unsigned int sourcecore = 0; // the core who has spare mem
98 for(i = j = 0; (i < NUMCORES4GC) && (j < NUMCORES4GC); ) {
100 // check if there are cores with spare mem
101 if(gccorestatus[i] == 0) {
102 // finished working, check if it still have spare mem
103 if(gcfilledblocks[i] < gcstopblock[i]) {
104 // still have spare mem
112 if(gccorestatus[j] != 0) {
113 // not finished, check if it has pending move requests
114 if((gcfilledblocks[j]==gcstopblock[j])&&(gcrequiredmems[j]>0)) {
123 if(!nosparemem && haspending) {
125 unsigned int tomove = 0;
126 unsigned int startaddr = 0;
127 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
128 gcrequiredmems[dstcore] = assignSpareMem_I(sourcecore,
129 gcrequiredmems[dstcore],
132 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
133 if(STARTUPCORE == dstcore) {
134 gcdstcore = sourcecore;
136 gcmovestartaddr = startaddr;
137 gcblock2fill = tomove;
139 send_msg_4(dstcore, GCMOVESTART, sourcecore,startaddr, tomove, false);
148 if(!hasrunning && !noblock) {
149 gcphase = SUBTLECOMPACTPHASE;
155 // If out of boundary of valid shared memory, return false, else return true
156 INLINE bool nextSBlock(struct moveHelper * orig) {
157 orig->blockbase = orig->blockbound;
159 bool sbchanged = false;
160 unsigned int origptr = orig->ptr;
161 unsigned int blockbase = orig->blockbase;
162 unsigned int blockbound = orig->blockbound;
163 unsigned int bound = orig->bound;
165 // check if across a big block
166 // TODO now do not zero out the whole memory, maybe the last two conditions
168 if((blockbase>=bound)||(origptr>=bound)
169 ||((origptr!=NULL)&&(*((int*)origptr))==0)||((*((int*)blockbase))==0)) {
171 // end of current heap block, jump to next one
173 BASEPTR(BAMBOO_NUM_OF_CORE, orig->numblocks, &(orig->base));
174 if(orig->base >= gcbaseva + BAMBOO_SHARED_MEM_SIZE) {
176 orig->ptr = orig->base; // set current ptr to out of boundary too
179 orig->blockbase = orig->base;
181 (unsigned int)(orig->blockbase-gcbaseva)/BAMBOO_SMEM_SIZE;
183 unsigned int blocknum = 0;
184 BLOCKINDEX(orig->base, &blocknum);
185 if(bamboo_smemtbl[blocknum] == 0) {
187 goto innernextSBlock;
189 // check the bamboo_smemtbl to decide the real bound
190 orig->bound = orig->base + bamboo_smemtbl[blocknum];
191 } else if(0 == (orig->blockbase%BAMBOO_SMEM_SIZE)) {
192 orig->sblockindex += 1;
196 // check if this sblock should be skipped or have special start point
197 int sbstart = gcsbstarttbl[orig->sblockindex];
200 orig->sblockindex += 1;
201 orig->blockbase += BAMBOO_SMEM_SIZE;
202 goto outernextSBlock;
203 } else if((sbstart != 0) && (sbchanged)) {
204 // the first time to access this SBlock
205 // not start from the very beginning
206 orig->blockbase = sbstart;
209 // setup information for this sblock
210 orig->blockbound = orig->blockbase+(unsigned int)*((int*)(orig->blockbase));
211 orig->offset = BAMBOO_CACHE_LINE_SIZE;
212 orig->ptr = orig->blockbase + orig->offset;
213 if(orig->ptr >= orig->bound) {
214 // met a lobj, move to next block
215 goto innernextSBlock;
221 // return false if there are no available data to compact
222 INLINE bool initOrig_Dst(struct moveHelper * orig,
223 struct moveHelper * to) {
226 to->top = to->offset = BAMBOO_CACHE_LINE_SIZE;
227 to->bound = BAMBOO_SMEM_SIZE_L;
228 BASEPTR(BAMBOO_NUM_OF_CORE, to->numblocks, &(to->base));
230 unsigned int tobase = to->base;
231 to->ptr = tobase + to->offset;
236 unsigned int blocknum = 0;
237 BLOCKINDEX(orig->base, &blocknum);
238 unsigned int origbase = orig->base;
239 // check the bamboo_smemtbl to decide the real bound
240 orig->bound = origbase + (unsigned int)bamboo_smemtbl[blocknum];
241 orig->blockbase = origbase;
242 orig->sblockindex = (unsigned int)(origbase - gcbaseva) / BAMBOO_SMEM_SIZE;
244 int sbstart = gcsbstarttbl[orig->sblockindex];
247 orig->blockbound=gcbaseva+BAMBOO_SMEM_SIZE*(orig->sblockindex+1);
248 return nextSBlock(orig);
249 } else if(sbstart != 0) {
250 orig->blockbase = sbstart;
252 orig->blockbound = orig->blockbase + *((int*)(orig->blockbase));
253 orig->offset = BAMBOO_CACHE_LINE_SIZE;
254 orig->ptr = orig->blockbase + orig->offset;
259 INLINE void nextBlock(struct moveHelper * to) {
260 to->top = to->bound + BAMBOO_CACHE_LINE_SIZE; // header!
261 to->bound += BAMBOO_SMEM_SIZE;
263 BASEPTR(BAMBOO_NUM_OF_CORE, to->numblocks, &(to->base));
264 to->offset = BAMBOO_CACHE_LINE_SIZE;
265 to->ptr = to->base + to->offset;
268 INLINE unsigned int findValidObj(struct moveHelper * orig,
269 struct moveHelper * to,
271 unsigned int size = 0;
273 CACHEADAPT_COMPLETE_PAGE_CONVERT(orig, to, to->ptr, false);
274 unsigned int origptr = (unsigned int)(orig->ptr);
275 unsigned int origbound = (unsigned int)orig->bound;
276 unsigned int origblockbound = (unsigned int)orig->blockbound;
277 if((origptr >= origbound) || (origptr == origblockbound)) {
278 if(!nextSBlock(orig)) {
279 // finished, no more data
284 // check the obj's type, size and mark flag
285 *type = ((int *)(origptr))[0];
288 // end of this block, go to next one
289 if(!nextSBlock(orig)) {
290 // finished, no more data
294 } else if(*type < NUMCLASSES) {
296 size = classsize[*type];
299 struct ArrayObject *ao=(struct ArrayObject *)(origptr);
300 unsigned int elementsize=classsize[*type];
301 unsigned int length=ao->___length___;
302 size=(unsigned int)sizeof(struct ArrayObject)
303 +(unsigned int)(length*elementsize);
309 // endaddr does not contain spaces for headers
310 INLINE bool moveobj(struct moveHelper * orig,
311 struct moveHelper * to,
312 unsigned int stopblock) {
318 unsigned int size = 0;
319 unsigned int isize = 0;
320 size = findValidObj(orig, to, &type);
322 // finished, no more data
325 ALIGNSIZE(size, &isize); // no matter is the obj marked or not
326 // should be able to across
327 unsigned int origptr = (unsigned int)(orig->ptr);
328 if(((struct ___Object___ *)origptr)->marked == MARKED) {
329 unsigned int totop = (unsigned int)to->top;
330 unsigned int tobound = (unsigned int)to->bound;
331 GCPROFILE_RECORD_LIVE_OBJ();
332 // marked obj, copy it to current heap top
333 // check to see if remaining space is enough
334 if((unsigned int)(totop + isize) > tobound) {
335 // fill 0 indicating the end of this block
336 BAMBOO_MEMSET_WH(to->ptr, '\0', tobound - totop);
337 // fill the header of this block and then go to next block
338 to->offset += tobound - totop;
339 CLOSEBLOCK(to->base, to->offset);
340 #ifdef GC_CACHE_ADAPT
341 unsigned int tmp_ptr = to->ptr;
344 #ifdef GC_CACHE_ADAPT
345 CACHEADAPT_COMPLETE_PAGE_CONVERT(orig, to, tmp_ptr, true);
347 if(stopblock == to->numblocks) {
348 // already fulfilled the block
352 // set the mark field to 2, indicating that this obj has been moved
353 // and need to be flushed
354 ((struct ___Object___ *)origptr)->marked = COMPACTED;
355 unsigned int toptr = (unsigned int)to->ptr;
356 if(toptr != origptr) {
357 if((unsigned int)(origptr) < (unsigned int)(toptr+size)) {
358 memmove(toptr, origptr, size);
360 memcpy(toptr, origptr, size);
362 // fill the remaining space with -2
363 BAMBOO_MEMSET_WH((unsigned int)(toptr+size), -2, isize-size);
365 // store mapping info
366 gcmappingtbl[OBJMAPPINGINDEX((unsigned int)origptr)]=(unsigned int)toptr;
367 gccurr_heaptop -= isize;
371 #ifdef GC_CACHE_ADAPT
372 unsigned int tmp_ptr = to->ptr;
373 #endif // GC_CACHE_ADAPT
374 if(to->top == to->bound) {
375 CLOSEBLOCK(to->base, to->offset);
378 #ifdef GC_CACHE_ADAPT
379 CACHEADAPT_COMPLETE_PAGE_CONVERT(orig, to, tmp_ptr, true);
386 if(((unsigned int)(orig->ptr) > (unsigned int)(orig->bound))
387 || ((unsigned int)(orig->ptr) == (unsigned int)(orig->blockbound))) {
388 if(!nextSBlock(orig)) {
389 // finished, no more data
396 // should be invoked with interrupt closed
397 INLINE int assignSpareMem_I(unsigned int sourcecore,
398 unsigned int * requiredmem,
399 unsigned int * tomove,
400 unsigned int * startaddr) {
402 BLOCKINDEX(gcloads[sourcecore], &b);
403 unsigned int boundptr = (b<NUMCORES4GC) ? ((b+1)*BAMBOO_SMEM_SIZE_L)
404 : (BAMBOO_LARGE_SMEM_BOUND+(b-NUMCORES4GC+1)*BAMBOO_SMEM_SIZE);
405 unsigned int remain = boundptr - gcloads[sourcecore];
406 unsigned int memneed = requiredmem + BAMBOO_CACHE_LINE_SIZE;
407 *startaddr = gcloads[sourcecore];
408 *tomove = gcfilledblocks[sourcecore] + 1;
409 if(memneed < remain) {
410 gcloads[sourcecore] += memneed;
413 // next available block
414 gcfilledblocks[sourcecore] += 1;
415 unsigned int newbase = 0;
416 BASEPTR(sourcecore, gcfilledblocks[sourcecore], &newbase);
417 gcloads[sourcecore] = newbase;
418 return requiredmem-remain;
422 // should be invoked with interrupt closed
423 INLINE bool gcfindSpareMem_I(unsigned int * startaddr,
424 unsigned int * tomove,
425 unsigned int * dstcore,
426 unsigned int requiredmem,
427 unsigned int requiredcore) {
428 for(int k = 0; k < NUMCORES4GC; k++) {
429 if((gccorestatus[k] == 0) && (gcfilledblocks[k] < gcstopblock[k])) {
430 // check if this stopped core has enough mem
431 assignSpareMem_I(k, requiredmem, tomove, startaddr);
436 // if can not find spare mem right now, hold the request
437 gcrequiredmems[requiredcore] = requiredmem;
442 INLINE bool compacthelper(struct moveHelper * orig,
443 struct moveHelper * to,
445 unsigned int * heaptopptr,
446 bool * localcompact) {
447 // scan over all objs in this block, compact the marked objs
448 // loop stop when finishing either scanning all active objs or
449 // fulfilled the gcstopblock
451 while((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) {
452 if(moveobj(orig, to, gcblock2fill)) {
456 CACHEADAPT_SAMPLING_DATA_CONVERT(to->ptr);
457 // if no objs have been compact, do nothing,
458 // otherwise, fill the header of this block
459 if(to->offset > (unsigned int)BAMBOO_CACHE_LINE_SIZE) {
460 CLOSEBLOCK(to->base, to->offset);
464 to->top -= BAMBOO_CACHE_LINE_SIZE;
467 *heaptopptr = to->ptr;
468 *filledblocks = to->numblocks;
471 // send msgs to core coordinator indicating that the compact is finishing
472 // send compact finish message to core coordinator
473 if(STARTUPCORE == BAMBOO_NUM_OF_CORE) {
474 gcfilledblocks[BAMBOO_NUM_OF_CORE] = *filledblocks;
475 gcloads[BAMBOO_NUM_OF_CORE] = *heaptopptr;
476 if((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) {
479 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
480 if(gcfindSpareMem_I(&gcmovestartaddr, &gcblock2fill, &gcdstcore,
481 gccurr_heaptop, BAMBOO_NUM_OF_CORE)) {
484 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
487 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
489 gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
494 if((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) {
497 send_msg_5(STARTUPCORE, GCFINISHCOMPACT, BAMBOO_NUM_OF_CORE,
498 *filledblocks, *heaptopptr, gccurr_heaptop, false);
501 send_msg_5(STARTUPCORE, GCFINISHCOMPACT, BAMBOO_NUM_OF_CORE,
502 *filledblocks, *heaptopptr, 0, false);
506 if(orig->ptr < gcmarkedptrbound) {
507 // still have unpacked obj
516 to->ptr = gcmovestartaddr;
517 to->numblocks = gcblock2fill - 1;
518 to->bound = ((to->numblocks==0)?BAMBOO_SMEM_SIZE_L:BAMBOO_SMEM_SIZE_L)
519 +BAMBOO_SMEM_SIZE*to->numblocks;
520 BASEPTR(gcdstcore, to->numblocks, &(to->base));
521 to->offset = to->ptr - to->base;
522 to->top = (to->numblocks==0)?(to->offset)
523 :(to->bound-BAMBOO_SMEM_SIZE+to->offset);
525 to->offset = BAMBOO_CACHE_LINE_SIZE;
526 to->ptr += to->offset; // for header
527 to->top += to->offset;
528 if(gcdstcore == BAMBOO_NUM_OF_CORE) {
529 *localcompact = true;
531 *localcompact = false;
533 CACHEADAPT_SAMPLING_DATA_REVISE_INIT();
539 INLINE void compact() {
540 if(COMPACTPHASE != gcphase) {
544 // initialize pointers for comapcting
545 struct moveHelper * orig =
546 (struct moveHelper *)RUNMALLOC(sizeof(struct moveHelper));
547 struct moveHelper * to =
548 (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,
553 0, to->base, 0, false);
558 CACHEADAPT_SAMPLING_DATA_REVISE_INIT();
560 unsigned int filledblocks = 0;
561 unsigned int heaptopptr = 0;
562 bool localcompact = true;
563 compacthelper(orig, to, &filledblocks, &heaptopptr, &localcompact);
568 INLINE void compact_master(struct moveHelper * orig,
569 struct moveHelper * to) {
570 bool finalcompact = false;
571 // initialize pointers for comapcting
572 initOrig_Dst(orig, to);
573 CACHEADAPT_SAMPLING_DATA_REVISE_INIT();
574 int filledblocks = 0;
575 unsigned int heaptopptr = 0;
576 bool finishcompact = false;
577 bool iscontinue = true;
578 bool localcompact = true;
579 while((COMPACTPHASE == gcphase) || (SUBTLECOMPACTPHASE == gcphase)) {
580 if((!finishcompact) && iscontinue) {
582 compacthelper(orig,to,&filledblocks,&heaptopptr,&localcompact);
585 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
586 if(gc_checkCoreStatus_I()) {
587 // all cores have finished compacting
588 // restore the gcstatus of all cores
589 for(int i = 0; i < NUMCORES4GC; ++i) {
592 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
595 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
596 // check if there are spare mem for pending move requires
597 if(COMPACTPHASE == gcphase) {
598 resolvePendingMoveRequest();
605 to->ptr = gcmovestartaddr;
606 to->numblocks = gcblock2fill - 1;
607 to->bound = (to->numblocks==0) ? BAMBOO_SMEM_SIZE_L :
608 BAMBOO_SMEM_SIZE_L+BAMBOO_SMEM_SIZE*to->numblocks;
609 BASEPTR(gcdstcore, to->numblocks, &(to->base));
610 to->offset = to->ptr - to->base;
611 to->top = (to->numblocks==0)?(to->offset):
612 (to->bound-BAMBOO_SMEM_SIZE+to->offset);
614 to->offset = BAMBOO_CACHE_LINE_SIZE;
615 to->ptr += to->offset; // for header
616 to->top += to->offset;
617 if(gcdstcore == BAMBOO_NUM_OF_CORE) {
620 localcompact = false;
624 } else if(!finishcompact) {
631 #endif // MULTICORE_GC