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)
17 INLINE void compact2Heaptophelper_I(unsigned int coren,
19 unsigned int* numblocks,
20 unsigned int* remain) {
22 unsigned int memneed = gcrequiredmems[coren] + BAMBOO_CACHE_LINE_SIZE;
23 if(STARTUPCORE == coren) {
26 gcdstcore = gctopcore;
27 gcblock2fill = *numblocks + 1;
29 send_msg_4(coren, GCMOVESTART, gctopcore, *p, (*numblocks) + 1, false);
31 if(memneed < *remain) {
33 gcrequiredmems[coren] = 0;
34 gcloads[gctopcore] += memneed;
35 *remain = *remain - memneed;
37 // next available block
39 gcfilledblocks[gctopcore] += 1;
40 unsigned int newbase = 0;
41 BASEPTR(gctopcore, gcfilledblocks[gctopcore], &newbase);
42 gcloads[gctopcore] = newbase;
43 gcrequiredmems[coren] -= *remain - BAMBOO_CACHE_LINE_SIZE;
44 gcstopblock[gctopcore]++;
45 gctopcore = NEXTTOPCORE(gctopblock);
47 *numblocks = gcstopblock[gctopcore];
48 *p = gcloads[gctopcore];
50 *remain=GC_BLOCK_REMAIN_SIZE(b, (*p));
55 INLINE void compact2Heaptop() {
56 // no cores with spare mem and some cores are blocked with pending move
57 // find the current heap top and make them move to the heap top
59 unsigned int numblocks = gcfilledblocks[gctopcore];
60 p = gcloads[gctopcore];
63 unsigned int remain=GC_BLOCK_REMAIN_SIZE(b, p);
64 // check if the top core finishes
65 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
66 if(gccorestatus[gctopcore] != 0) {
67 // let the top core finishes its own work first
68 compact2Heaptophelper_I(gctopcore, &p, &numblocks, &remain);
69 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
72 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
74 for(int i = 0; i < NUMCORES4GC; i++) {
75 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
76 if((gccorestatus[i] != 0) && (gcrequiredmems[i] > 0)) {
77 compact2Heaptophelper_I(i, &p, &numblocks, &remain);
78 if(gccorestatus[gctopcore] != 0) {
79 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
80 // the top core is not free now
84 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
88 INLINE void resolvePendingMoveRequest() {
91 bool nosparemem = true;
92 bool haspending = false;
93 bool hasrunning = false;
95 unsigned int dstcore = 0; // the core who need spare mem
96 unsigned int sourcecore = 0; // the core who has spare mem
97 for(i = j = 0; (i < NUMCORES4GC) && (j < NUMCORES4GC); ) {
99 // check if there are cores with spare mem
100 if(gccorestatus[i] == 0) {
101 // finished working, check if it still have spare mem
102 if(gcfilledblocks[i] < gcstopblock[i]) {
103 // still have spare mem
111 if(gccorestatus[j] != 0) {
112 // not finished, check if it has pending move requests
113 if((gcfilledblocks[j]==gcstopblock[j])&&(gcrequiredmems[j]>0)) {
122 if(!nosparemem && haspending) {
124 unsigned int tomove = 0;
125 unsigned int startaddr = 0;
126 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
127 gcrequiredmems[dstcore] = assignSpareMem_I(sourcecore,
128 gcrequiredmems[dstcore],
131 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
132 if(STARTUPCORE == dstcore) {
133 gcdstcore = sourcecore;
135 gcmovestartaddr = startaddr;
136 gcblock2fill = tomove;
138 send_msg_4(dstcore, GCMOVESTART, sourcecore,startaddr, tomove, false);
147 if(!hasrunning && !noblock) {
148 gcphase = SUBTLECOMPACTPHASE;
154 // If out of boundary of valid shared memory, return false, else return true
155 INLINE bool nextSBlock(struct moveHelper * orig) {
156 orig->blockbase = orig->blockbound;
158 bool sbchanged = false;
159 unsigned int origptr = orig->ptr;
160 unsigned int blockbase = orig->blockbase;
161 unsigned int blockbound = orig->blockbound;
162 unsigned int bound = orig->bound;
164 // check if across a big block
165 // TODO now do not zero out the whole memory, maybe the last two conditions
167 if((blockbase>=bound)||(origptr>=bound)
168 ||((origptr!=NULL)&&(*((int*)origptr))==0)||((*((int*)blockbase))==0)) {
170 // end of current heap block, jump to next one
172 BASEPTR(BAMBOO_NUM_OF_CORE, orig->numblocks, &(orig->base));
173 if(orig->base >= gcbaseva + BAMBOO_SHARED_MEM_SIZE) {
175 orig->ptr = orig->base; // set current ptr to out of boundary too
178 orig->blockbase = orig->base;
180 (unsigned int)(orig->blockbase-gcbaseva)/BAMBOO_SMEM_SIZE;
182 unsigned int blocknum = 0;
183 BLOCKINDEX(orig->base, &blocknum);
184 if(bamboo_smemtbl[blocknum] == 0) {
186 goto innernextSBlock;
188 // check the bamboo_smemtbl to decide the real bound
189 orig->bound = orig->base + bamboo_smemtbl[blocknum];
190 } else if(0 == (orig->blockbase%BAMBOO_SMEM_SIZE)) {
191 orig->sblockindex += 1;
195 // check if this sblock should be skipped or have special start point
196 int sbstart = gcsbstarttbl[orig->sblockindex];
199 orig->sblockindex += 1;
200 orig->blockbase += BAMBOO_SMEM_SIZE;
201 goto outernextSBlock;
202 } else if((sbstart != 0) && (sbchanged)) {
203 // the first time to access this SBlock
204 // not start from the very beginning
205 orig->blockbase = sbstart;
208 // setup information for this sblock
209 orig->blockbound = orig->blockbase+(unsigned int)*((int*)(orig->blockbase));
210 orig->offset = BAMBOO_CACHE_LINE_SIZE;
211 orig->ptr = orig->blockbase + orig->offset;
212 if(orig->ptr >= orig->bound) {
213 // met a lobj, move to next block
214 goto innernextSBlock;
220 // return false if there are no available data to compact
221 INLINE bool initOrig_Dst(struct moveHelper * orig,
222 struct moveHelper * to) {
225 to->top = to->offset = BAMBOO_CACHE_LINE_SIZE;
226 to->bound = BAMBOO_SMEM_SIZE_L;
227 BASEPTR(BAMBOO_NUM_OF_CORE, to->numblocks, &(to->base));
229 unsigned int tobase = to->base;
230 to->ptr = tobase + to->offset;
235 unsigned int blocknum = 0;
236 BLOCKINDEX(orig->base, &blocknum);
237 unsigned int origbase = orig->base;
238 // check the bamboo_smemtbl to decide the real bound
239 orig->bound = origbase + (unsigned int)bamboo_smemtbl[blocknum];
240 orig->blockbase = origbase;
241 orig->sblockindex = (unsigned int)(origbase - gcbaseva) / BAMBOO_SMEM_SIZE;
243 int sbstart = gcsbstarttbl[orig->sblockindex];
246 orig->blockbound=gcbaseva+BAMBOO_SMEM_SIZE*(orig->sblockindex+1);
247 return nextSBlock(orig);
248 } else if(sbstart != 0) {
249 orig->blockbase = sbstart;
251 orig->blockbound = orig->blockbase + *((int*)(orig->blockbase));
252 orig->offset = BAMBOO_CACHE_LINE_SIZE;
253 orig->ptr = orig->blockbase + orig->offset;
258 INLINE void nextBlock(struct moveHelper * to) {
259 to->top = to->bound + BAMBOO_CACHE_LINE_SIZE; // header!
260 to->bound += BAMBOO_SMEM_SIZE;
262 BASEPTR(BAMBOO_NUM_OF_CORE, to->numblocks, &(to->base));
263 to->offset = BAMBOO_CACHE_LINE_SIZE;
264 to->ptr = to->base + to->offset;
267 INLINE unsigned int findValidObj(struct moveHelper * orig,
268 struct moveHelper * to,
270 unsigned int size = 0;
272 CACHEADAPT_COMPLETE_PAGE_CONVERT(orig, to, to->ptr, false);
273 unsigned int origptr = (unsigned int)(orig->ptr);
274 unsigned int origbound = (unsigned int)orig->bound;
275 unsigned int origblockbound = (unsigned int)orig->blockbound;
276 if((origptr >= origbound) || (origptr == origblockbound)) {
277 if(!nextSBlock(orig)) {
278 // finished, no more data
283 // check the obj's type, size and mark flag
284 *type = ((int *)(origptr))[0];
287 // end of this block, go to next one
288 if(!nextSBlock(orig)) {
289 // finished, no more data
293 } else if(*type < NUMCLASSES) {
295 size = classsize[*type];
298 struct ArrayObject *ao=(struct ArrayObject *)(origptr);
299 unsigned int elementsize=classsize[*type];
300 unsigned int length=ao->___length___;
301 size=(unsigned int)sizeof(struct ArrayObject)
302 +(unsigned int)(length*elementsize);
308 // endaddr does not contain spaces for headers
309 INLINE bool moveobj(struct moveHelper * orig,
310 struct moveHelper * to,
311 unsigned int stopblock) {
317 unsigned int size = 0;
318 unsigned int isize = 0;
319 size = findValidObj(orig, to, &type);
321 // finished, no more data
324 ALIGNSIZE(size, &isize); // no matter is the obj marked or not
325 // should be able to across
326 unsigned int origptr = (unsigned int)(orig->ptr);
327 if(((struct ___Object___ *)origptr)->marked == MARKED) {
328 unsigned int totop = (unsigned int)to->top;
329 unsigned int tobound = (unsigned int)to->bound;
330 GCPROFILE_RECORD_LIVE_OBJ();
331 // marked obj, copy it to current heap top
332 // check to see if remaining space is enough
333 if((unsigned int)(totop + isize) > tobound) {
334 // fill 0 indicating the end of this block
335 BAMBOO_MEMSET_WH(to->ptr, '\0', tobound - totop);
336 // fill the header of this block and then go to next block
337 to->offset += tobound - totop;
338 CLOSEBLOCK(to->base, to->offset);
339 #ifdef GC_CACHE_ADAPT
340 unsigned int tmp_ptr = to->ptr;
343 #ifdef GC_CACHE_ADAPT
344 CACHEADAPT_COMPLETE_PAGE_CONVERT(orig, to, tmp_ptr, true);
346 if(stopblock == to->numblocks) {
347 // already fulfilled the block
351 // set the mark field to 2, indicating that this obj has been moved
352 // and need to be flushed
353 ((struct ___Object___ *)origptr)->marked = COMPACTED;
354 unsigned int toptr = (unsigned int)to->ptr;
355 if(toptr != origptr) {
356 if((unsigned int)(origptr) < (unsigned int)(toptr+size)) {
357 memmove(toptr, origptr, size);
359 memcpy(toptr, origptr, size);
361 // fill the remaining space with -2
362 BAMBOO_MEMSET_WH((unsigned int)(toptr+size), -2, isize-size);
364 // store mapping info
365 gcmappingtbl[OBJMAPPINGINDEX((unsigned int)origptr)]=(unsigned int)toptr;
366 gccurr_heaptop -= isize;
370 #ifdef GC_CACHE_ADAPT
371 unsigned int tmp_ptr = to->ptr;
372 #endif // GC_CACHE_ADAPT
373 if(to->top == to->bound) {
374 CLOSEBLOCK(to->base, to->offset);
377 #ifdef GC_CACHE_ADAPT
378 CACHEADAPT_COMPLETE_PAGE_CONVERT(orig, to, tmp_ptr, true);
385 return ((((unsigned int)(orig->ptr) > (unsigned int)(orig->bound))
386 || ((unsigned int)(orig->ptr) == (unsigned int)(orig->blockbound)))
387 &&!nextSBlock(orig));
390 // should be invoked with interrupt closed
391 INLINE int assignSpareMem_I(unsigned int sourcecore,
392 unsigned int * requiredmem,
393 unsigned int * tomove,
394 unsigned int * startaddr) {
396 BLOCKINDEX(gcloads[sourcecore], &b);
397 unsigned int boundptr = (b<NUMCORES4GC) ? ((b+1)*BAMBOO_SMEM_SIZE_L)
398 : (BAMBOO_LARGE_SMEM_BOUND+(b-NUMCORES4GC+1)*BAMBOO_SMEM_SIZE);
399 unsigned int remain = boundptr - gcloads[sourcecore];
400 unsigned int memneed = requiredmem + BAMBOO_CACHE_LINE_SIZE;
401 *startaddr = gcloads[sourcecore];
402 *tomove = gcfilledblocks[sourcecore] + 1;
403 if(memneed < remain) {
404 gcloads[sourcecore] += memneed;
407 // next available block
408 gcfilledblocks[sourcecore] += 1;
409 unsigned int newbase = 0;
410 BASEPTR(sourcecore, gcfilledblocks[sourcecore], &newbase);
411 gcloads[sourcecore] = newbase;
412 return requiredmem-remain;
416 // should be invoked with interrupt closed
417 INLINE bool gcfindSpareMem_I(unsigned int * startaddr,
418 unsigned int * tomove,
419 unsigned int * dstcore,
420 unsigned int requiredmem,
421 unsigned int requiredcore) {
422 for(int k = 0; k < NUMCORES4GC; k++) {
423 if((gccorestatus[k] == 0) && (gcfilledblocks[k] < gcstopblock[k])) {
424 // check if this stopped core has enough mem
425 assignSpareMem_I(k, requiredmem, tomove, startaddr);
430 // if can not find spare mem right now, hold the request
431 gcrequiredmems[requiredcore] = requiredmem;
436 INLINE bool compacthelper(struct moveHelper * orig,
437 struct moveHelper * to,
439 unsigned int * heaptopptr,
440 bool * localcompact) {
441 // scan over all objs in this block, compact the marked objs
442 // loop stop when finishing either scanning all active objs or
443 // fulfilled the gcstopblock
445 while((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) {
446 if(moveobj(orig, to, gcblock2fill)) {
450 CACHEADAPT_SAMPLING_DATA_CONVERT(to->ptr);
451 // if no objs have been compact, do nothing,
452 // otherwise, fill the header of this block
453 if(to->offset > (unsigned int)BAMBOO_CACHE_LINE_SIZE) {
454 CLOSEBLOCK(to->base, to->offset);
458 to->top -= BAMBOO_CACHE_LINE_SIZE;
461 *heaptopptr = to->ptr;
462 *filledblocks = to->numblocks;
465 // send msgs to core coordinator indicating that the compact is finishing
466 // send compact finish message to core coordinator
467 if(STARTUPCORE == BAMBOO_NUM_OF_CORE) {
468 gcfilledblocks[BAMBOO_NUM_OF_CORE] = *filledblocks;
469 gcloads[BAMBOO_NUM_OF_CORE] = *heaptopptr;
470 if((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) {
473 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
474 if(gcfindSpareMem_I(&gcmovestartaddr, &gcblock2fill, &gcdstcore,
475 gccurr_heaptop, BAMBOO_NUM_OF_CORE)) {
478 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
481 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
483 gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
488 if((unsigned int)(orig->ptr) < (unsigned int)gcmarkedptrbound) {
491 send_msg_5(STARTUPCORE, GCFINISHCOMPACT, BAMBOO_NUM_OF_CORE,
492 *filledblocks, *heaptopptr, gccurr_heaptop, false);
495 send_msg_5(STARTUPCORE, GCFINISHCOMPACT, BAMBOO_NUM_OF_CORE,
496 *filledblocks, *heaptopptr, 0, false);
500 if(orig->ptr < gcmarkedptrbound) {
501 // still have unpacked obj
507 to->ptr = gcmovestartaddr;
508 to->numblocks = gcblock2fill - 1;
509 to->bound = ((to->numblocks==0)?BAMBOO_SMEM_SIZE_L:BAMBOO_SMEM_SIZE_L)
510 +BAMBOO_SMEM_SIZE*to->numblocks;
511 BASEPTR(gcdstcore, to->numblocks, &(to->base));
512 to->offset = to->ptr - to->base;
513 to->top = (to->numblocks==0)?(to->offset)
514 :(to->bound-BAMBOO_SMEM_SIZE+to->offset);
516 to->offset = BAMBOO_CACHE_LINE_SIZE;
517 to->ptr += to->offset; // for header
518 to->top += to->offset;
519 if(gcdstcore == BAMBOO_NUM_OF_CORE) {
520 *localcompact = true;
522 *localcompact = false;
524 CACHEADAPT_SAMPLING_DATA_REVISE_INIT();
531 if(COMPACTPHASE != gcphase) {
535 // initialize pointers for comapcting
536 struct moveHelper * orig = (struct moveHelper *)RUNMALLOC(sizeof(struct moveHelper));
537 struct moveHelper * to = (struct moveHelper *)RUNMALLOC(sizeof(struct moveHelper));
538 if(!initOrig_Dst(orig, to)) {
539 // no available data to compact
540 // send compact finish msg to STARTUP core
541 send_msg_5(STARTUPCORE, GCFINISHCOMPACT, BAMBOO_NUM_OF_CORE,
542 0, to->base, 0, false);
547 CACHEADAPT_SAMPLING_DATA_REVISE_INIT();
549 unsigned int filledblocks = 0;
550 unsigned int heaptopptr = 0;
551 bool localcompact = true;
552 compacthelper(orig, to, &filledblocks, &heaptopptr, &localcompact);
557 void compact_master(struct moveHelper * orig, struct moveHelper * to) {
558 bool finalcompact = false;
559 // initialize pointers for comapcting
560 initOrig_Dst(orig, to);
561 CACHEADAPT_SAMPLING_DATA_REVISE_INIT();
562 int filledblocks = 0;
563 unsigned int heaptopptr = 0;
564 bool finishcompact = false;
565 bool iscontinue = true;
566 bool localcompact = true;
567 while((COMPACTPHASE == gcphase) || (SUBTLECOMPACTPHASE == gcphase)) {
568 if((!finishcompact) && iscontinue) {
569 finishcompact = compacthelper(orig,to,&filledblocks,&heaptopptr,&localcompact);
572 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
573 if(gc_checkCoreStatus_I()) {
574 // all cores have finished compacting
575 // restore the gcstatus of all cores
576 for(int i = 0; i < NUMCORES4GC; ++i) {
579 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
582 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
583 // check if there are spare mem for pending move requires
584 if(COMPACTPHASE == gcphase) {
585 resolvePendingMoveRequest();
592 to->ptr = gcmovestartaddr;
593 to->numblocks = gcblock2fill - 1;
594 to->bound = (to->numblocks==0) ? BAMBOO_SMEM_SIZE_L : BAMBOO_SMEM_SIZE_L+BAMBOO_SMEM_SIZE*to->numblocks;
595 BASEPTR(gcdstcore, to->numblocks, &(to->base));
596 to->offset = to->ptr - to->base;
597 to->top = (to->numblocks==0)?(to->offset):(to->bound-BAMBOO_SMEM_SIZE+to->offset);
599 to->offset = BAMBOO_CACHE_LINE_SIZE;
600 to->ptr += to->offset; // for header
601 to->top += to->offset;
602 localcompact = (gcdstcore == BAMBOO_NUM_OF_CORE);
605 } else if(!finishcompact) {
612 #endif // MULTICORE_GC