2 #include "multicoregccompact.h"
3 #include "runtime_arch.h"
4 #include "multicoreruntime.h"
8 INLINE bool gc_checkCoreStatus_I() {
9 for(int i = 0; i < NUMCORES4GC; ++i) {
10 if(gccorestatus[i] != 0)
16 INLINE void compact2Heaptophelper_I(unsigned int coren,
18 unsigned int* numblocks,
19 unsigned int* remain) {
21 unsigned int memneed = gcrequiredmems[coren] + BAMBOO_CACHE_LINE_SIZE;
22 if(STARTUPCORE == coren) {
25 gcdstcore = gctopcore;
26 gcblock2fill = *numblocks + 1;
28 send_msg_4(coren, GCMOVESTART, gctopcore, *p, (*numblocks) + 1, false);
30 if(memneed < *remain) {
32 gcrequiredmems[coren] = 0;
33 gcloads[gctopcore] += memneed;
34 *remain = *remain - memneed;
36 // next available block
38 gcfilledblocks[gctopcore] += 1;
39 unsigned int newbase = 0;
40 BASEPTR(gctopcore, gcfilledblocks[gctopcore], &newbase);
41 gcloads[gctopcore] = newbase;
42 gcrequiredmems[coren] -= *remain - BAMBOO_CACHE_LINE_SIZE;
43 gcstopblock[gctopcore]++;
44 gctopcore = NEXTTOPCORE(gctopblock);
46 *numblocks = gcstopblock[gctopcore];
47 *p = gcloads[gctopcore];
49 *remain=GC_BLOCK_REMAIN_SIZE(b, (*p));
54 INLINE void compact2Heaptop() {
55 // no cores with spare mem and some cores are blocked with pending move
56 // find the current heap top and make them move to the heap top
58 unsigned int numblocks = gcfilledblocks[gctopcore];
59 p = gcloads[gctopcore];
62 unsigned int remain=GC_BLOCK_REMAIN_SIZE(b, p);
63 // check if the top core finishes
64 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
65 if(gccorestatus[gctopcore] != 0) {
66 // let the top core finishes its own work first
67 compact2Heaptophelper_I(gctopcore, &p, &numblocks, &remain);
68 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
71 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
73 for(int i = 0; i < NUMCORES4GC; i++) {
74 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
75 if((gccorestatus[i] != 0) && (gcrequiredmems[i] > 0)) {
76 compact2Heaptophelper_I(i, &p, &numblocks, &remain);
77 if(gccorestatus[gctopcore] != 0) {
78 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
79 // the top core is not free now
83 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
87 INLINE void resolvePendingMoveRequest() {
90 bool nosparemem = true;
91 bool haspending = false;
92 bool hasrunning = false;
94 unsigned int dstcore = 0; // the core who need spare mem
95 unsigned int sourcecore = 0; // the core who has spare mem
96 for(i = j = 0; (i < NUMCORES4GC) && (j < NUMCORES4GC); ) {
98 // check if there are cores with spare mem
99 if(gccorestatus[i] == 0) {
100 // finished working, check if it still have spare mem
101 if(gcfilledblocks[i] < gcstopblock[i]) {
102 // still have spare mem
110 if(gccorestatus[j] != 0) {
111 // not finished, check if it has pending move requests
112 if((gcfilledblocks[j]==gcstopblock[j])&&(gcrequiredmems[j]>0)) {
121 if(!nosparemem && haspending) {
123 unsigned int tomove = 0;
124 unsigned int startaddr = 0;
125 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
126 gcrequiredmems[dstcore] = assignSpareMem_I(sourcecore,
127 gcrequiredmems[dstcore],
130 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
131 if(STARTUPCORE == dstcore) {
132 gcdstcore = sourcecore;
134 gcmovestartaddr = startaddr;
135 gcblock2fill = tomove;
137 send_msg_4(dstcore, GCMOVESTART, sourcecore,startaddr, tomove, false);
146 if(!hasrunning && !noblock) {
147 gcphase = SUBTLECOMPACTPHASE;
152 // If out of boundary of valid shared memory, return false, else return true
153 INLINE bool nextSBlock(struct moveHelper * orig) {
154 orig->blockbase = orig->blockbound;
156 bool sbchanged = false;
157 unsigned int origptr = orig->ptr;
158 unsigned int blockbase = orig->blockbase;
159 unsigned int blockbound = orig->blockbound;
160 unsigned int bound = orig->bound;
162 // check if across a big block
163 // TODO now do not zero out the whole memory, maybe the last two conditions
165 if((blockbase>=bound)||(origptr>=bound)
166 ||((origptr!=NULL)&&(*((int*)origptr))==0)||((*((int*)blockbase))==0)) {
168 // end of current heap block, jump to next one
170 BASEPTR(BAMBOO_NUM_OF_CORE, orig->numblocks, &(orig->base));
171 if(orig->base >= gcbaseva + BAMBOO_SHARED_MEM_SIZE) {
173 orig->ptr = orig->base; // set current ptr to out of boundary too
176 orig->blockbase = orig->base;
178 (unsigned int)(orig->blockbase-gcbaseva)/BAMBOO_SMEM_SIZE;
180 unsigned int blocknum = 0;
181 BLOCKINDEX(orig->base, &blocknum);
182 if(bamboo_smemtbl[blocknum] == 0) {
184 goto innernextSBlock;
186 // check the bamboo_smemtbl to decide the real bound
187 orig->bound = orig->base + bamboo_smemtbl[blocknum];
188 } else if(0 == (orig->blockbase%BAMBOO_SMEM_SIZE)) {
189 orig->sblockindex += 1;
193 // check if this sblock should be skipped or have special start point
194 int sbstart = gcsbstarttbl[orig->sblockindex];
197 orig->sblockindex += 1;
198 orig->blockbase += BAMBOO_SMEM_SIZE;
199 goto outernextSBlock;
200 } else if((sbstart != 0) && (sbchanged)) {
201 // the first time to access this SBlock
202 // not start from the very beginning
203 orig->blockbase = sbstart;
206 // setup information for this sblock
207 orig->blockbound = orig->blockbase+(unsigned int)*((int*)(orig->blockbase));
208 orig->offset = BAMBOO_CACHE_LINE_SIZE;
209 orig->ptr = orig->blockbase + orig->offset;
210 if(orig->ptr >= orig->bound) {
211 // met a lobj, move to next block
212 goto innernextSBlock;
218 // return false if there are no available data to compact
219 INLINE bool initOrig_Dst(struct moveHelper * orig,
220 struct moveHelper * to) {
223 to->top = to->offset = BAMBOO_CACHE_LINE_SIZE;
224 to->bound = BAMBOO_SMEM_SIZE_L;
225 BASEPTR(BAMBOO_NUM_OF_CORE, to->numblocks, &(to->base));
227 unsigned int tobase = to->base;
228 to->ptr = tobase + to->offset;
233 unsigned int blocknum = 0;
234 BLOCKINDEX(orig->base, &blocknum);
235 unsigned int origbase = orig->base;
236 // check the bamboo_smemtbl to decide the real bound
237 orig->bound = origbase + (unsigned int)bamboo_smemtbl[blocknum];
238 orig->blockbase = origbase;
239 orig->sblockindex = (unsigned int)(origbase - gcbaseva) / BAMBOO_SMEM_SIZE;
241 int sbstart = gcsbstarttbl[orig->sblockindex];
244 orig->blockbound=gcbaseva+BAMBOO_SMEM_SIZE*(orig->sblockindex+1);
245 return nextSBlock(orig);
246 } else if(sbstart != 0) {
247 orig->blockbase = sbstart;
249 orig->blockbound = orig->blockbase + *((int*)(orig->blockbase));
250 orig->offset = BAMBOO_CACHE_LINE_SIZE;
251 orig->ptr = orig->blockbase + orig->offset;
256 INLINE void nextBlock(struct moveHelper * to) {
257 to->top = to->bound + BAMBOO_CACHE_LINE_SIZE; // header!
258 to->bound += BAMBOO_SMEM_SIZE;
260 BASEPTR(BAMBOO_NUM_OF_CORE, to->numblocks, &(to->base));
261 to->offset = BAMBOO_CACHE_LINE_SIZE;
262 to->ptr = to->base + to->offset;
265 INLINE unsigned int findValidObj(struct moveHelper * orig,
266 struct moveHelper * to,
268 unsigned int size = 0;
270 CACHEADAPT_COMPLETE_PAGE_CONVERT(orig, to, to->ptr, false);
271 unsigned int origptr = (unsigned int)(orig->ptr);
272 unsigned int origbound = (unsigned int)orig->bound;
273 unsigned int origblockbound = (unsigned int)orig->blockbound;
274 if((origptr >= origbound) || (origptr == origblockbound)) {
275 if(!nextSBlock(orig)) {
276 // finished, no more data
281 // check the obj's type, size and mark flag
282 *type = ((int *)(origptr))[0];
285 // end of this block, go to next one
286 if(!nextSBlock(orig)) {
287 // finished, no more data
291 } else if(*type < NUMCLASSES) {
293 size = classsize[*type];
296 struct ArrayObject *ao=(struct ArrayObject *)(origptr);
297 unsigned int elementsize=classsize[*type];
298 unsigned int length=ao->___length___;
299 size=(unsigned int)sizeof(struct ArrayObject)
300 +(unsigned int)(length*elementsize);
306 // endaddr does not contain spaces for headers
307 INLINE bool moveobj(struct moveHelper * orig, struct moveHelper * to, unsigned int stopblock) {
313 unsigned int size = findValidObj(orig, to, &type);
314 unsigned int isize = 0;
317 // finished, no more data
320 ALIGNSIZE(size, &isize); // no matter is the obj marked or not
321 // should be able to across
322 unsigned int origptr = (unsigned int)(orig->ptr);
323 if(((struct ___Object___ *)origptr)->marked == MARKED) {
324 unsigned int totop = (unsigned int)to->top;
325 unsigned int tobound = (unsigned int)to->bound;
326 GCPROFILE_RECORD_LIVE_OBJ();
327 // marked obj, copy it to current heap top
328 // check to see if remaining space is enough
329 if((unsigned int)(totop + isize) > tobound) {
330 // fill 0 indicating the end of this block
331 BAMBOO_MEMSET_WH(to->ptr, '\0', tobound - totop);
332 // fill the header of this block and then go to next block
333 to->offset += tobound - totop;
334 CLOSEBLOCK(to->base, to->offset);
335 #ifdef GC_CACHE_ADAPT
336 unsigned int tmp_ptr = to->ptr;
339 #ifdef GC_CACHE_ADAPT
340 CACHEADAPT_COMPLETE_PAGE_CONVERT(orig, to, tmp_ptr, true);
342 if(stopblock == to->numblocks) {
343 // already fulfilled the block
347 // set the mark field to 2, indicating that this obj has been moved
348 // and need to be flushed
349 ((struct ___Object___ *)origptr)->marked = COMPACTED;
350 unsigned int toptr = (unsigned int)to->ptr;
351 if(toptr != origptr) {
352 if((unsigned int)(origptr) < (unsigned int)(toptr+size)) {
353 memmove(toptr, origptr, size);
355 memcpy(toptr, origptr, size);
357 // fill the remaining space with -2
358 BAMBOO_MEMSET_WH((unsigned int)(toptr+size), -2, isize-size);
360 // store mapping info
361 gcmappingtbl[OBJMAPPINGINDEX((unsigned int)origptr)]=(unsigned int)toptr;
362 gccurr_heaptop -= isize;
366 #ifdef GC_CACHE_ADAPT
367 unsigned int tmp_ptr = to->ptr;
368 #endif // GC_CACHE_ADAPT
369 if(to->top == to->bound) {
370 CLOSEBLOCK(to->base, to->offset);
373 #ifdef GC_CACHE_ADAPT
374 CACHEADAPT_COMPLETE_PAGE_CONVERT(orig, to, tmp_ptr, true);
381 return ((((unsigned int)(orig->ptr) > (unsigned int)(orig->bound))
382 || ((unsigned int)(orig->ptr) == (unsigned int)(orig->blockbound)))
383 &&!nextSBlock(orig));
386 // should be invoked with interrupt closed
387 INLINE int assignSpareMem_I(unsigned int sourcecore,
388 unsigned int * requiredmem,
389 unsigned int * tomove,
390 unsigned int * startaddr) {
392 BLOCKINDEX(gcloads[sourcecore], &b);
393 unsigned int boundptr = (b<NUMCORES4GC) ? ((b+1)*BAMBOO_SMEM_SIZE_L)
394 : (BAMBOO_LARGE_SMEM_BOUND+(b-NUMCORES4GC+1)*BAMBOO_SMEM_SIZE);
395 unsigned int remain = boundptr - gcloads[sourcecore];
396 unsigned int memneed = requiredmem + BAMBOO_CACHE_LINE_SIZE;
397 *startaddr = gcloads[sourcecore];
398 *tomove = gcfilledblocks[sourcecore] + 1;
399 if(memneed < remain) {
400 gcloads[sourcecore] += memneed;
403 // next available block
404 gcfilledblocks[sourcecore] += 1;
405 unsigned int newbase = 0;
406 BASEPTR(sourcecore, gcfilledblocks[sourcecore], &newbase);
407 gcloads[sourcecore] = newbase;
408 return requiredmem-remain;
412 // should be invoked with interrupt closed
413 INLINE bool gcfindSpareMem_I(unsigned int * startaddr,
414 unsigned int * tomove,
415 unsigned int * dstcore,
416 unsigned int requiredmem,
417 unsigned int requiredcore) {
418 for(int k = 0; k < NUMCORES4GC; k++) {
419 if((gccorestatus[k] == 0) && (gcfilledblocks[k] < gcstopblock[k])) {
420 // check if this stopped core has enough mem
421 assignSpareMem_I(k, requiredmem, tomove, startaddr);
426 // if can not find spare mem right now, hold the request
427 gcrequiredmems[requiredcore] = requiredmem;
432 INLINE bool compacthelper(struct moveHelper * orig,
433 struct moveHelper * to,
435 unsigned int * heaptopptr,
436 bool * localcompact) {
437 // scan over all objs in this block, compact the marked objs
438 // loop stop when finishing either scanning all active objs or
439 // fulfilled the gcstopblock
441 while((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) {
442 if(moveobj(orig, to, gcblock2fill)) {
446 CACHEADAPT_SAMPLING_DATA_CONVERT(to->ptr);
447 // if no objs have been compact, do nothing,
448 // otherwise, fill the header of this block
449 if(to->offset > (unsigned int)BAMBOO_CACHE_LINE_SIZE) {
450 CLOSEBLOCK(to->base, to->offset);
454 to->top -= BAMBOO_CACHE_LINE_SIZE;
457 *heaptopptr = to->ptr;
458 *filledblocks = to->numblocks;
461 // send msgs to core coordinator indicating that the compact is finishing
462 // send compact finish message to core coordinator
463 if(STARTUPCORE == BAMBOO_NUM_OF_CORE) {
464 gcfilledblocks[BAMBOO_NUM_OF_CORE] = *filledblocks;
465 gcloads[BAMBOO_NUM_OF_CORE] = *heaptopptr;
466 if((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) {
469 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
470 if(gcfindSpareMem_I(&gcmovestartaddr, &gcblock2fill, &gcdstcore,
471 gccurr_heaptop, BAMBOO_NUM_OF_CORE)) {
474 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
477 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
479 gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
484 if((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) {
487 send_msg_5(STARTUPCORE, GCFINISHCOMPACT, BAMBOO_NUM_OF_CORE,
488 *filledblocks, *heaptopptr, gccurr_heaptop, false);
491 send_msg_5(STARTUPCORE, GCFINISHCOMPACT, BAMBOO_NUM_OF_CORE,
492 *filledblocks, *heaptopptr, 0, false);
496 if(orig->ptr < gcmarkedptrbound) {
497 // still have unpacked obj
503 to->ptr = gcmovestartaddr;
504 to->numblocks = gcblock2fill - 1;
505 to->bound = ((to->numblocks==0)?BAMBOO_SMEM_SIZE_L:BAMBOO_SMEM_SIZE_L)+BAMBOO_SMEM_SIZE*to->numblocks;
506 BASEPTR(gcdstcore, to->numblocks, &(to->base));
507 to->offset = to->ptr - to->base;
508 to->top = (to->numblocks==0)?(to->offset):(to->bound-BAMBOO_SMEM_SIZE+to->offset);
510 to->offset = BAMBOO_CACHE_LINE_SIZE;
511 to->ptr += to->offset; // for header
512 to->top += to->offset;
513 *localcompact = (gcdstcore == BAMBOO_NUM_OF_CORE);
514 CACHEADAPT_SAMPLING_DATA_REVISE_INIT();
521 BAMBOO_ASSERT(COMPACTPHASE == gcphase, 0xb025);
523 // initialize pointers for comapcting
524 struct moveHelper * orig = (struct moveHelper *)RUNMALLOC(sizeof(struct moveHelper));
525 struct moveHelper * to = (struct moveHelper *)RUNMALLOC(sizeof(struct moveHelper));
526 if(!initOrig_Dst(orig, to)) {
527 // no available data to compact
528 // send compact finish msg to STARTUP core
529 send_msg_5(STARTUPCORE, GCFINISHCOMPACT, BAMBOO_NUM_OF_CORE,
530 0, to->base, 0, false);
534 CACHEADAPT_SAMPLING_DATA_REVISE_INIT();
536 unsigned int filledblocks = 0;
537 unsigned int heaptopptr = 0;
538 bool localcompact = true;
539 compacthelper(orig, to, &filledblocks, &heaptopptr, &localcompact);
545 void compact_master(struct moveHelper * orig, struct moveHelper * to) {
546 // initialize pointers for comapcting
547 initOrig_Dst(orig, to);
548 CACHEADAPT_SAMPLING_DATA_REVISE_INIT();
549 int filledblocks = 0;
550 unsigned int heaptopptr = 0;
551 bool finishcompact = false;
552 bool iscontinue = true;
553 bool localcompact = true;
554 while((COMPACTPHASE == gcphase) || (SUBTLECOMPACTPHASE == gcphase)) {
555 if((!finishcompact) && iscontinue) {
556 finishcompact = compacthelper(orig,to,&filledblocks,&heaptopptr,&localcompact);
559 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
560 if(gc_checkCoreStatus_I()) {
561 // all cores have finished compacting
562 // restore the gcstatus of all cores
563 for(int i = 0; i < NUMCORES4GC; ++i) {
566 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
569 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
570 // check if there are spare mem for pending move requires
571 if(COMPACTPHASE == gcphase) {
572 resolvePendingMoveRequest();
579 to->ptr = gcmovestartaddr;
580 to->numblocks = gcblock2fill - 1;
581 to->bound = (to->numblocks==0) ? BAMBOO_SMEM_SIZE_L : BAMBOO_SMEM_SIZE_L+BAMBOO_SMEM_SIZE*to->numblocks;
582 BASEPTR(gcdstcore, to->numblocks, &(to->base));
583 to->offset = to->ptr - to->base;
584 to->top = (to->numblocks==0)?(to->offset):(to->bound-BAMBOO_SMEM_SIZE+to->offset);
586 to->offset = BAMBOO_CACHE_LINE_SIZE;
587 to->ptr += to->offset; // for header
588 to->top += to->offset;
589 localcompact = (gcdstcore == BAMBOO_NUM_OF_CORE);
592 } else if(!finishcompact) {
599 #endif // MULTICORE_GC