Robust/src/Runtime/multicoregarbage.c

   1 #ifdef MULTICORE_GC
   2 #include "runtime.h"
   3 #include "multicoregarbage.h"
   4 #include "multicoreruntime.h"
   5 #include "runtime_arch.h"
   6 #include "SimpleHash.h"
   7 #include "GenericHashtable.h"
   8 #include "ObjectHash.h"
   9
  10 extern int corenum;
  11 extern struct parameterwrapper ** objectqueues[][NUMCLASSES];
  12 extern int numqueues[][NUMCLASSES];
  13
  14 extern struct genhashtable * activetasks;
  15 extern struct parameterwrapper ** objectqueues[][NUMCLASSES];
  16 extern struct taskparamdescriptor *currtpd;
  17
  18 struct pointerblock {
  19   void * ptrs[NUMPTRS];
  20   struct pointerblock *next;
  21 };
  22
  23 struct pointerblock *gchead=NULL;
  24 int gcheadindex=0;
  25 struct pointerblock *gctail=NULL;
  26 int gctailindex=0;
  27 struct pointerblock *gctail2=NULL;
  28 int gctailindex2=0;
  29 struct pointerblock *gcspare=NULL;
  30
  31 #define NUMLOBJPTRS 20
  32
  33 struct lobjpointerblock {
  34   void * lobjs[NUMLOBJPTRS];
  35         //void * dsts[NUMLOBJPTRS];
  36         int lengths[NUMLOBJPTRS];
  37         //void * origs[NUMLOBJPTRS];
  38         int hosts[NUMLOBJPTRS];
  39   struct lobjpointerblock *next;
  40 };
  41
  42 struct lobjpointerblock *gclobjhead=NULL;
  43 int gclobjheadindex=0;
  44 struct lobjpointerblock *gclobjtail=NULL;
  45 int gclobjtailindex=0;
  46 struct lobjpointerblock *gclobjtail2=NULL;
  47 int gclobjtailindex2=0;
  48 struct lobjpointerblock *gclobjspare=NULL;
  49
  50 #ifdef GC_DEBUG
  51 inline void dumpSMem() {
  52         int block = 0;
  53         int sblock = 0;
  54         int j = 0;
  55         int i = 0;
  56         bool reverse = false;
  57         int coren = 0;
  58         tprintf("Dump shared mem: \n");
  59         tprintf("++++ reserved sblocks ++++ \n");
  60         for(i=BAMBOO_BASE_VA; i<gcbaseva; i+= 4*16) {
  61                 tprintf("0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x \n",
  62             *((int *)(i)), *((int *)(i + 4)), *((int *)(i + 4*2)), *((int *)(i + 4*3)),
  63                                                 *((int *)(i + 4*4)), *((int *)(i + 4*5)), *((int *)(i + 4*6)), *((int *)(i + 4*7)),
  64                                                 *((int *)(i + 4*8)), *((int *)(i + 4*9)), *((int *)(i + 4*10)), *((int *)(i + 4*11)),
  65                                                 *((int *)(i + 4*12)), *((int *)(i + 4*13)), *((int *)(i + 4*14)), *((int *)(i + 4*15)));
  66         }
  67         for(i=gcbaseva;i<BAMBOO_BASE_VA+BAMBOO_SHARED_MEM_SIZE;i+=4*16){
  68                 if(j%((BAMBOO_SMEM_SIZE)/(4*16)) == 0) {
  69                         if(j < ((BAMBOO_LARGE_SMEM_BOUND)/(4*16))) {
  70                                 if((j > 0) && (j%((BAMBOO_SMEM_SIZE_L)/(4*16)) == 0)) {
  71                                         block++;
  72                                         if(block%NUMCORES == 0) {
  73                                                 reverse = !reverse;
  74                                         } else {
  75                                                 if(reverse) {
  76                                                         coren--;
  77                                                 } else {
  78                                                         coren++;
  79                                                 }
  80                                         }
  81                                 }
  82                         } else {
  83                                 block++;
  84                                 if(block%NUMCORES == 0) {
  85                                         reverse = !reverse;
  86                                 } else {
  87                                         if(reverse) {
  88                                                 coren--;
  89                                         } else {
  90                                                 coren++;
  91                                         }
  92                                 }
  93                         }
  94                         tprintf("==== %d, %d : core %d, saddr %x====\n", block,
  95                                             sblock++, coren, sblock*(BAMBOO_SMEM_SIZE)+BAMBOO_BASE_VA);
  96                 }
  97                 j++;
  98     tprintf("0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x 0x%08x \n",
  99             *((int *)(i)), *((int *)(i + 4)), *((int *)(i + 4*2)), *((int *)(i + 4*3)),
 100                                                 *((int *)(i + 4*4)), *((int *)(i + 4*5)), *((int *)(i + 4*6)), *((int *)(i + 4*7)),
 101                                                 *((int *)(i + 4*8)), *((int *)(i + 4*9)), *((int *)(i + 4*10)), *((int *)(i + 4*11)),
 102                                                 *((int *)(i + 4*12)), *((int *)(i + 4*13)), *((int *)(i + 4*14)), *((int *)(i + 4*15)));
 103         }
 104         tprintf("\n");
 105 }
 106 #endif
 107
 108 // should be invoked with interruption closed
 109 inline void gc_enqueue_I(void *ptr) {
 110 #ifdef DEBUG
 111         BAMBOO_DEBUGPRINT(0xe601);
 112         BAMBOO_DEBUGPRINT_REG(ptr);
 113 #endif
 114   if (gcheadindex==NUMPTRS) {
 115     struct pointerblock * tmp;
 116     if (gcspare!=NULL) {
 117       tmp=gcspare;
 118       gcspare=NULL;
 119     } else {
 120       tmp=RUNMALLOC_I(sizeof(struct pointerblock));
 121                 } // if (gcspare!=NULL)
 122     gchead->next=tmp;
 123     gchead=tmp;
 124     gcheadindex=0;
 125   } // if (gcheadindex==NUMPTRS)
 126   gchead->ptrs[gcheadindex++]=ptr;
 127 #ifdef DEBUG
 128         BAMBOO_DEBUGPRINT(0xe602);
 129 #endif
 130 } // void gc_enqueue_I(void *ptr)
 131
 132 // dequeue and destroy the queue
 133 inline void * gc_dequeue() {
 134   if (gctailindex==NUMPTRS) {
 135     struct pointerblock *tmp=gctail;
 136     gctail=gctail->next;
 137     gctailindex=0;
 138     if (gcspare!=NULL) {
 139       RUNFREE(tmp);
 140                 } else {
 141       gcspare=tmp;
 142                 } // if (gcspare!=NULL)
 143   } // if (gctailindex==NUMPTRS)
 144   return gctail->ptrs[gctailindex++];
 145 } // void * gc_dequeue()
 146
 147 // dequeue and do not destroy the queue
 148 inline void * gc_dequeue2() {
 149         if (gctailindex2==NUMPTRS) {
 150     struct pointerblock *tmp=gctail2;
 151     gctail2=gctail2->next;
 152     gctailindex2=0;
 153   } // if (gctailindex2==NUMPTRS)
 154   return gctail2->ptrs[gctailindex2++];
 155 } // void * gc_dequeue2()
 156
 157 inline int gc_moreItems() {
 158   if ((gchead==gctail)&&(gctailindex==gcheadindex))
 159     return 0;
 160   return 1;
 161 } // int gc_moreItems()
 162
 163 inline int gc_moreItems2() {
 164   if ((gchead==gctail2)&&(gctailindex2==gcheadindex))
 165     return 0;
 166   return 1;
 167 } // int gc_moreItems2()
 168
 169 // should be invoked with interruption closed
 170 // enqueue a large obj: start addr & length
 171 inline void gc_lobjenqueue_I(void *ptr,
 172                                          int length,
 173                                                                                          int host) {
 174 #ifdef DEBUG
 175         BAMBOO_DEBUGPRINT(0xe901);
 176 #endif
 177   if (gclobjheadindex==NUMLOBJPTRS) {
 178     struct lobjpointerblock * tmp;
 179     if (gclobjspare!=NULL) {
 180       tmp=gclobjspare;
 181       gclobjspare=NULL;
 182     } else {
 183       tmp=RUNMALLOC_I(sizeof(struct lobjpointerblock));
 184                 } // if (gclobjspare!=NULL)
 185     gclobjhead->next=tmp;
 186     gclobjhead=tmp;
 187     gclobjheadindex=0;
 188   } // if (gclobjheadindex==NUMLOBJPTRS)
 189   gclobjhead->lobjs[gclobjheadindex]=ptr;
 190         gclobjhead->lengths[gclobjheadindex]=length;
 191         gclobjhead->hosts[gclobjheadindex++]=host;
 192 #ifdef DEBUG
 193         BAMBOO_DEBUGPRINT_REG(gclobjhead->lobjs[gclobjheadindex-1]);
 194         BAMBOO_DEBUGPRINT_REG(gclobjhead->lengths[gclobjheadindex-1]);
 195         BAMBOO_DEBUGPRINT_REG(gclobjhead->hosts[gclobjheadindex-1]);
 196 #endif
 197 } // void gc_lobjenqueue_I(void *ptr...)
 198
 199 // dequeue and destroy the queue
 200 inline void * gc_lobjdequeue(int * length,
 201                                          int * host) {
 202   if (gclobjtailindex==NUMLOBJPTRS) {
 203     struct lobjpointerblock *tmp=gclobjtail;
 204     gclobjtail=gclobjtail->next;
 205     gclobjtailindex=0;
 206     if (gclobjspare!=NULL) {
 207       RUNFREE(tmp);
 208                 } else {
 209       gclobjspare=tmp;
 210                 } // if (gclobjspare!=NULL)
 211   } // if (gclobjtailindex==NUMLOBJPTRS)
 212         if(length != NULL) {
 213                 *length = gclobjtail->lengths[gclobjtailindex];
 214         }
 215         if(host != NULL) {
 216                 *host = (int)(gclobjtail->hosts[gclobjtailindex]);
 217         }
 218   return gclobjtail->lobjs[gclobjtailindex++];
 219 } // void * gc_lobjdequeue()
 220
 221 inline int gc_lobjmoreItems() {
 222   if ((gclobjhead==gclobjtail)&&(gclobjtailindex==gclobjheadindex))
 223     return 0;
 224   return 1;
 225 } // int gc_lobjmoreItems()
 226
 227 // dequeue and don't destroy the queue
 228 inline void gc_lobjdequeue2() {
 229   if (gclobjtailindex2==NUMLOBJPTRS) {
 230     gclobjtail2=gclobjtail2->next;
 231     gclobjtailindex2=1;
 232   } else {
 233                 gclobjtailindex2++;
 234         }// if (gclobjtailindex2==NUMLOBJPTRS)
 235 } // void * gc_lobjdequeue2()
 236
 237 inline int gc_lobjmoreItems2() {
 238   if ((gclobjhead==gclobjtail2)&&(gclobjtailindex2==gclobjheadindex))
 239     return 0;
 240   return 1;
 241 } // int gc_lobjmoreItems2()
 242
 243 INTPTR gccurr_heapbound = 0;
 244
 245 inline void gettype_size(void * ptr,
 246                                      int * ttype,
 247                                                                          int * tsize) {
 248         int type = ((int *)ptr)[0];
 249         int size = 0;
 250         if(type < NUMCLASSES) {
 251                 // a normal object
 252                 size = classsize[type];
 253         } else {
 254                 // an array
 255                 struct ArrayObject *ao=(struct ArrayObject *)ptr;
 256                 int elementsize=classsize[type];
 257                 int length=ao->___length___;
 258                 size=sizeof(struct ArrayObject)+length*elementsize;
 259         } // if(type < NUMCLASSES)
 260         *ttype = type;
 261         *tsize = size;
 262 }
 263
 264 inline bool isLarge(void * ptr,
 265                                 int * ttype,
 266                                                                                 int * tsize) {
 267 #ifdef DEBUG
 268                 BAMBOO_DEBUGPRINT(0xe701);
 269                 BAMBOO_DEBUGPRINT_REG(ptr);
 270 #endif
 271         // check if a pointer is referring to a large object
 272         gettype_size(ptr, ttype, tsize);
 273 #ifdef DEBUG
 274         BAMBOO_DEBUGPRINT(*tsize);
 275 #endif
 276         int bound = (BAMBOO_SMEM_SIZE);
 277         if(((int)ptr-gcbaseva) < (BAMBOO_LARGE_SMEM_BOUND)) {
 278                 bound = (BAMBOO_SMEM_SIZE_L);
 279         }
 280         if((((int)ptr-gcbaseva)%(bound))==0) {
 281                 // ptr is a start of a block
 282 #ifdef DEBUG
 283                 BAMBOO_DEBUGPRINT(0xe702);
 284                 BAMBOO_DEBUGPRINT(1);
 285 #endif
 286                 return true;
 287         }
 288         if((bound-(((int)ptr-gcbaseva)%bound)) < (*tsize)) {
 289                 // it acrosses the boundary of current block
 290 #ifdef DEBUG
 291                 BAMBOO_DEBUGPRINT(0xe703);
 292                 BAMBOO_DEBUGPRINT(1);
 293 #endif
 294                 return true;
 295         }
 296 #ifdef DEBUG
 297                 BAMBOO_DEBUGPRINT(0);
 298 #endif
 299         return false;
 300 } // bool isLarge(void * ptr, int * ttype, int * tsize)
 301
 302 inline int hostcore(void * ptr) {
 303         // check the host core of ptr
 304         int host = 0;
 305         int x = 0;
 306         int y = 0;
 307         RESIDECORE(ptr, &x, &y);
 308         host = (x==0)?(x*bamboo_height+y):(x*bamboo_height+y-2);
 309         return host;
 310 } // int hostcore(void * ptr)
 311
 312 inline bool isLocal(void * ptr) {
 313         // check if a pointer is in shared heap on this core
 314         return hostcore(ptr) == BAMBOO_NUM_OF_CORE;
 315 } // bool isLocal(void * ptr)
 316
 317 inline bool gc_checkCoreStatus() {
 318         bool allStall = true;
 319         for(int i = 0; i < NUMCORES; ++i) {
 320                 if(gccorestatus[i] != 0) {
 321                         allStall = false;
 322                         break;
 323                 } // if(gccorestatus[i] != 0)
 324         } // for(i = 0; i < NUMCORES; ++i)
 325         return allStall;
 326 }
 327
 328 inline void checkMarkStatue() {
 329 #ifdef DEBUG
 330         BAMBOO_DEBUGPRINT(0xee01);
 331 #endif
 332         int i;
 333         if((!waitconfirm) ||
 334                         (waitconfirm && (numconfirm == 0))) {
 335 #ifdef DEBUG
 336                 BAMBOO_DEBUGPRINT(0xee02);
 337 #endif
 338                 BAMBOO_START_CRITICAL_SECTION_STATUS();
 339                 gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
 340                 gcnumsendobjs[BAMBOO_NUM_OF_CORE] = gcself_numsendobjs;
 341                 gcnumreceiveobjs[BAMBOO_NUM_OF_CORE] = gcself_numreceiveobjs;
 342                 // check the status of all cores
 343                 bool allStall = gc_checkCoreStatus();
 344 #ifdef DEBUG
 345                 BAMBOO_DEBUGPRINT(0xee03);
 346 #endif
 347                 if(allStall) {
 348 #ifdef DEBUG
 349                         BAMBOO_DEBUGPRINT(0xee04);
 350 #endif
 351                         // check if the sum of send objs and receive obj are the same
 352                         // yes->check if the info is the latest; no->go on executing
 353                         int sumsendobj = 0;
 354                         for(i = 0; i < NUMCORES; ++i) {
 355                                 sumsendobj += gcnumsendobjs[i];
 356                         } // for(i = 0; i < NUMCORES; ++i)
 357 #ifdef DEBUG
 358                         BAMBOO_DEBUGPRINT(0xee05);
 359                         BAMBOO_DEBUGPRINT_REG(sumsendobj);
 360 #endif
 361                         for(i = 0; i < NUMCORES; ++i) {
 362                                 sumsendobj -= gcnumreceiveobjs[i];
 363                         } // for(i = 0; i < NUMCORES; ++i)
 364 #ifdef DEBUG
 365                         BAMBOO_DEBUGPRINT(0xee06);
 366                         BAMBOO_DEBUGPRINT_REG(sumsendobj);
 367 #endif
 368                         if(0 == sumsendobj) {
 369 #ifdef DEBUG
 370                                 BAMBOO_DEBUGPRINT(0xee07);
 371 #endif
 372                                 if(!waitconfirm) {
 373 #ifdef DEBUG
 374                                         BAMBOO_DEBUGPRINT(0xee08);
 375 #endif
 376                                         // the first time found all cores stall
 377                                         // send out status confirm msg to all other cores
 378                                         // reset the corestatus array too
 379                                         gccorestatus[BAMBOO_NUM_OF_CORE] = 1;
 380                                         waitconfirm = true;
 381                                         numconfirm = NUMCORES - 1;
 382                                         for(i = 1; i < NUMCORES; ++i) {
 383                                                 gccorestatus[i] = 1;
 384                                                 // send mark phase finish confirm request msg to core i
 385                                                 send_msg_1(i, GCMARKCONFIRM);
 386                                         } // for(i = 1; i < NUMCORES; ++i)
 387                                 } else {
 388 #ifdef DEBUG
 389                                         BAMBOO_DEBUGPRINT(0xee09);
 390 #endif
 391                                         // all the core status info are the latest
 392                                         // stop mark phase
 393                                         gcphase = COMPACTPHASE;
 394                                         // restore the gcstatus for all cores
 395                                         for(i = 0; i < NUMCORES; ++i) {
 396                                                 gccorestatus[i] = 1;
 397                                         } // for(i = 0; i < NUMCORES; ++i)
 398                                 } // if(!gcwautconfirm) else()
 399                         } // if(0 == sumsendobj)
 400                 } // if(allStall)
 401                 BAMBOO_CLOSE_CRITICAL_SECTION_STATUS();
 402         } // if((!waitconfirm)...
 403 #ifdef DEBUG
 404         BAMBOO_DEBUGPRINT(0xee0a);
 405 #endif
 406 } // void checkMarkStatue()
 407
 408 inline bool preGC() {
 409         // preparation for gc
 410         // make sure to clear all incoming msgs espacially transfer obj msgs
 411 #ifdef GC_DEBUG
 412         BAMBOO_DEBUGPRINT(0xec01);
 413 #endif
 414         int i;
 415         if((!waitconfirm) ||
 416                                                   (waitconfirm && (numconfirm == 0))) {
 417                 // send out status confirm msgs to all cores to check if there are
 418                 // transfer obj msgs on-the-fly
 419                 waitconfirm = true;
 420                 numconfirm = NUMCORES - 1;
 421                 for(i = 1; i < NUMCORES; ++i) {
 422                         corestatus[i] = 1;
 423                         // send status confirm msg to core i
 424                         send_msg_1(i, STATUSCONFIRM);
 425                 } // for(i = 1; i < NUMCORES; ++i)
 426
 427 #ifdef GC_DEBUG
 428                 BAMBOO_DEBUGPRINT(0xec02);
 429 #endif
 430                 while(numconfirm != 0) {} // wait for confirmations
 431                 waitconfirm = false;
 432                 numconfirm = 0;
 433 #ifdef DEBUG
 434                 BAMBOO_DEBUGPRINT(0xec03);
 435 #endif
 436                 numsendobjs[BAMBOO_NUM_OF_CORE] = self_numsendobjs;
 437                 numreceiveobjs[BAMBOO_NUM_OF_CORE] = self_numreceiveobjs;
 438                 int sumsendobj = 0;
 439 #ifdef DEBUG
 440                 BAMBOO_DEBUGPRINT(0xec04);
 441 #endif
 442                 for(i = 0; i < NUMCORES; ++i) {
 443                         sumsendobj += numsendobjs[i];
 444 #ifdef DEBUG
 445                         BAMBOO_DEBUGPRINT(0xf000 + numsendobjs[i]);
 446 #endif
 447                 } // for(i = 1; i < NUMCORES; ++i)
 448 #ifdef DEBUG
 449         BAMBOO_DEBUGPRINT(0xec05);
 450         BAMBOO_DEBUGPRINT_REG(sumsendobj);
 451 #endif
 452                 for(i = 0; i < NUMCORES; ++i) {
 453                         sumsendobj -= numreceiveobjs[i];
 454 #ifdef DEBUG
 455                         BAMBOO_DEBUGPRINT(0xf000 + numreceiveobjs[i]);
 456 #endif
 457                 } // for(i = 1; i < NUMCORES; ++i)
 458 #ifdef DEBUG
 459                 BAMBOO_DEBUGPRINT(0xec06);
 460                 BAMBOO_DEBUGPRINT_REG(sumsendobj);
 461 #endif
 462                 if(0 == sumsendobj) {
 463                         return true;
 464                 } else {
 465                         // still have some transfer obj msgs on-the-fly, can not start gc
 466                         return false;
 467                 } // if(0 == sumsendobj)
 468         } else {
 469 #ifdef DEBUG
 470                 BAMBOO_DEBUGPRINT(0xec07);
 471 #endif
 472                 // previously asked for status confirmation and do not have all the
 473                 // confirmations yet, can not start gc
 474                 return false;
 475         } // if((!waitconfirm) ||
 476 } // bool preGC()
 477
 478 inline void initGC() {
 479         int i;
 480         if(STARTUPCORE == BAMBOO_NUM_OF_CORE) {
 481                 for(i = 0; i < NUMCORES; ++i) {
 482                         gccorestatus[i] = 1;
 483                         gcnumsendobjs[i] = 0;
 484                         gcnumreceiveobjs[i] = 0;
 485                         gcloads[i] = 0;
 486                         gcrequiredmems[i] = 0;
 487                         gcfilledblocks[i] = 0;
 488                         gcstopblock[i] = 0;
 489                 } // for(i = 0; i < NUMCORES; ++i)
 490                 gcheaptop = 0;
 491                 gctopcore = 0;
 492                 gcheapdirection = 1;
 493         }
 494         gcself_numsendobjs = 0;
 495         gcself_numreceiveobjs = 0;
 496         gcmarkedptrbound = 0;
 497         gcobj2map = 0;
 498         gcmappedobj = 0;
 499         gcismapped = false;
 500         gcnumlobjs = 0;
 501         gcmovestartaddr = 0;
 502         gctomove = false;
 503         gcblock2fill = 0;
 504         gcmovepending = 0;
 505         gccurr_heaptop = 0;
 506         gcdstcore = 0;
 507
 508         // initialize queue
 509         if (gchead==NULL) {
 510                 gcheadindex=gctailindex=gctailindex2 = 0;
 511                 gchead=gctail=gctail2=RUNMALLOC(sizeof(struct pointerblock));
 512         } else {
 513                 gctailindex = gctailindex2 = gcheadindex;
 514                 gctail = gctail2 = gchead;
 515         }
 516
 517         // initialize the large obj queues
 518         if (gclobjhead==NULL) {
 519                 gclobjheadindex=0;
 520                 gclobjtailindex=0;
 521                 gclobjtailindex2 = 0;
 522                 gclobjhead=gclobjtail=gclobjtail2=
 523                         RUNMALLOC(sizeof(struct lobjpointerblock));
 524         } else {
 525                 gclobjtailindex = gclobjtailindex2 = gclobjheadindex;
 526                 gclobjtail = gclobjtail2 = gclobjhead;
 527         }
 528
 529         freeRuntimeHash(gcpointertbl);
 530         gcpointertbl = allocateRuntimeHash(20);
 531 } // void initGC()
 532
 533 // compute load balance for all cores
 534 inline int loadbalance() {
 535         // compute load balance
 536         int i;
 537
 538         // get the total loads
 539         int tloads = gcloads[STARTUPCORE];
 540         for(i = 1; i < NUMCORES; i++) {
 541                 tloads += gcloads[i];
 542         }
 543         int heaptop = gcbaseva + tloads;
 544 #ifdef DEBUG
 545         BAMBOO_DEBUGPRINT(0xdddd);
 546         BAMBOO_DEBUGPRINT_REG(tloads);
 547         BAMBOO_DEBUGPRINT_REG(heaptop);
 548 #endif
 549         int b = 0;
 550         BLOCKINDEX(heaptop, &b);
 551         int numbpc = b / NUMCORES; // num of blocks per core
 552 #ifdef DEBUG
 553         BAMBOO_DEBUGPRINT_REG(b);
 554         BAMBOO_DEBUGPRINT_REG(numbpc);
 555 #endif
 556         gcheapdirection = (numbpc%2 == 0);
 557         int x = 0;
 558         int y = 0;
 559         RESIDECORE(heaptop, &x, &y);
 560         gctopcore = (x == 0 ? y : x * bamboo_height + y - 2);
 561 #ifdef DEBUG
 562         BAMBOO_DEBUGPRINT_REG(gctopcore);
 563 #endif
 564         return numbpc;
 565 } // void loadbalance()
 566
 567 inline bool cacheLObjs() {
 568         // check the total mem size need for large objs
 569         int sumsize = 0;
 570         int size = 0;
 571 #ifdef DEBUG
 572         BAMBOO_DEBUGPRINT(0xe801);
 573 #endif
 574         gclobjtail2 = gclobjtail;
 575         gclobjtailindex2 = gclobjtailindex;
 576         while(gc_lobjmoreItems2()){
 577                 gc_lobjdequeue2();
 578                 size = gclobjtail2->lengths[gclobjtailindex2 - 1];
 579                 sumsize += size;
 580 #ifdef DEBUG
 581                 BAMBOO_DEBUGPRINT_REG(size);
 582                 BAMBOO_DEBUGPRINT_REG(sumsize);
 583 #endif
 584         } // while(gc_lobjmoreItems2())
 585
 586         // check if there are enough space to cache these large objs
 587         INTPTR dst = (BAMBOO_BASE_VA) + (BAMBOO_SHARED_MEM_SIZE) - sumsize;
 588         if(gcheaptop > dst) {
 589                 // do not have enough room to cache large objs
 590                 return false;
 591         }
 592 #ifdef DEBUG
 593         BAMBOO_DEBUGPRINT(0xe802);
 594         BAMBOO_DEBUGPRINT_REG(dst);
 595 #endif
 596
 597         gcheaptop = dst; // Note: record the start of cached lobjs with gcheaptop
 598         // cache the largeObjs to the top of the shared heap
 599         gclobjtail2 = gclobjtail;
 600         gclobjtailindex2 = gclobjtailindex;
 601         while(gc_lobjmoreItems2()) {
 602                 gc_lobjdequeue2();
 603                 size = gclobjtail2->lengths[gclobjtailindex2 - 1];
 604                 // set the mark field to 2, indicating that this obj has been moved and need to be flushed
 605                 ((int *)(gclobjtail2->lobjs[gclobjtailindex2-1]))[6] = 2;
 606                 memcpy(dst, gclobjtail2->lobjs[gclobjtailindex2 - 1], size);
 607                 dst += size;
 608 #ifdef DEBUG
 609                 BAMBOO_DEBUGPRINT_REG(gclobjtail2->lobjs[gclobjtailindex2-1]);
 610                 BAMBOO_DEBUGPRINT(dst-size);
 611                 BAMBOO_DEBUGPRINT_REG(size);
 612 #endif
 613         }
 614         return true;
 615 } // void cacheLObjs()
 616
 617 inline void moveLObjs() {
 618 #ifdef DEBUG
 619         BAMBOO_DEBUGPRINT(0xea01);
 620 #endif
 621         // find current heap top
 622         // flush all gcloads to indicate the real heap top on one core
 623         // previous it represents the next available ptr on a core
 624         if((gcloads[0] > (gcbaseva+(BAMBOO_SMEM_SIZE_L)))
 625                         && ((gcloads[0]%(BAMBOO_SMEM_SIZE)) == 0)) {
 626                 // edge of a block, check if this is exactly the heaptop
 627                 BASEPTR(0, gcfilledblocks[0]-1, &(gcloads[0]));
 628                 gcloads[0]+=(gcfilledblocks[0]>1?(BAMBOO_SMEM_SIZE):(BAMBOO_SMEM_SIZE_L));
 629         }
 630         int tmpheaptop = gcloads[0];
 631 #ifdef DEBUG
 632         BAMBOO_DEBUGPRINT_REG(tmpheaptop);
 633 #endif
 634         for(int i = 1; i < NUMCORES; i++) {
 635                 if((gcloads[i] > (gcbaseva+(BAMBOO_SMEM_SIZE_L)))
 636                                 && ((gcloads[i] % (BAMBOO_SMEM_SIZE)) == 0)) {
 637                         // edge of a block, check if this is exactly the heaptop
 638                         BASEPTR(0, gcfilledblocks[i]-1, &gcloads[i]);
 639                         gcloads[i]
 640                                 +=(gcfilledblocks[i]>1?(BAMBOO_SMEM_SIZE):(BAMBOO_SMEM_SIZE_L));
 641                 }
 642                 if(tmpheaptop < gcloads[i]) {
 643                         tmpheaptop = gcloads[i];
 644                 }
 645 #ifdef DEBUG
 646                 BAMBOO_DEBUGPRINT_REG(gcloads[i]);
 647                 BAMBOO_DEBUGPRINT_REG(tmpheaptop);
 648 #endif
 649         }
 650         // move large objs from gcheaptop to tmpheaptop
 651         // write the header first
 652         int tomove = (BAMBOO_BASE_VA) + (BAMBOO_SHARED_MEM_SIZE) - gcheaptop;
 653 #ifdef DEBUG
 654         BAMBOO_DEBUGPRINT(0xea02);
 655         BAMBOO_DEBUGPRINT_REG(tomove);
 656 #endif
 657         // flush the sbstartbl
 658         memset(&(gcsbstarttbl[gcreservedsb]), '\0',
 659                            BAMBOO_SHARED_MEM_SIZE/BAMBOO_SMEM_SIZE*sizeof(INTPTR));
 660         if(tomove == 0) {
 661                 gcheaptop = tmpheaptop;
 662                 return;
 663         }
 664         // check how many blocks it acrosses
 665         int remain = tmpheaptop-gcbaseva;
 666         int b = remain/(BAMBOO_SMEM_SIZE) + gcreservedsb;
 667         // check the remaining space in this block
 668         int bound = (BAMBOO_SMEM_SIZE);
 669         if(remain < (BAMBOO_LARGE_SMEM_BOUND)) {
 670                 bound = (BAMBOO_SMEM_SIZE_L);
 671         }
 672         remain = bound - remain%bound;
 673
 674 #ifdef DEBUG
 675         BAMBOO_DEBUGPRINT(0xea03);
 676 #endif
 677         int size = 0;
 678         int isize = 0;
 679         int host = 0;
 680         int ptr = 0;
 681         int base = tmpheaptop;
 682         int cpysize = 0;
 683         remain -= BAMBOO_CACHE_LINE_SIZE;
 684         tmpheaptop += BAMBOO_CACHE_LINE_SIZE;
 685         while(gc_lobjmoreItems()) {
 686                 ptr = (int)(gc_lobjdequeue(&size, &host));
 687                 ALIGNSIZE(size, &isize);
 688                 if(remain < isize) {
 689                         // this object acrosses blocks
 690                         if(cpysize > 0) {
 691                                 // close current block, fill its header
 692                                 memset(base, '\0', BAMBOO_CACHE_LINE_SIZE);
 693                                 *((int*)base) = cpysize + BAMBOO_CACHE_LINE_SIZE;
 694                                 cpysize = 0;
 695                                 base = tmpheaptop;
 696                                 if(remain == 0) {
 697                                         remain = ((tmpheaptop-gcbaseva)<(BAMBOO_LARGE_SMEM_BOUND)) ?
 698                                                        BAMBOO_SMEM_SIZE_L : BAMBOO_SMEM_SIZE;
 699                                 }
 700                                 remain -= BAMBOO_CACHE_LINE_SIZE;
 701                                 tmpheaptop += BAMBOO_CACHE_LINE_SIZE;
 702                         } // if(cpysize > 0)
 703
 704                         // move the large obj
 705                         memcpy(tmpheaptop, gcheaptop, size);
 706                         // fill the remaining space with -2 padding
 707                         memset(tmpheaptop+size, -2, isize-size);
 708 #ifdef DEBUG
 709                         BAMBOO_DEBUGPRINT(0xea04);
 710                         BAMBOO_DEBUGPRINT_REG(gcheaptop);
 711                         BAMBOO_DEBUGPRINT_REG(tmpheaptop);
 712                         BAMBOO_DEBUGPRINT_REG(size);
 713                         BAMBOO_DEBUGPRINT_REG(isize);
 714 #endif
 715                         gcheaptop += size;
 716                         if(host == BAMBOO_NUM_OF_CORE) {
 717                                 BAMBOO_START_CRITICAL_SECTION();
 718                                 RuntimeHashadd_I(gcpointertbl, ptr, tmpheaptop);
 719                                 BAMBOO_CLOSE_CRITICAL_SECTION();
 720 #ifdef DEBUG
 721                                 BAMBOO_DEBUGPRINT(0xcdcd);
 722                                 BAMBOO_DEBUGPRINT_REG(ptr);
 723                                 BAMBOO_DEBUGPRINT_REG(tmpheaptop);
 724 #endif
 725                         } else {
 726                                 // send the original host core with the mapping info
 727                                 send_msg_3(host, GCLOBJMAPPING, ptr, tmpheaptop);
 728 #ifdef DEBUG
 729                                 BAMBOO_DEBUGPRINT(0xcdcd);
 730                                 BAMBOO_DEBUGPRINT_REG(ptr);
 731                                 BAMBOO_DEBUGPRINT_REG(tmpheaptop);
 732 #endif
 733                         } // if(host == BAMBOO_NUM_OF_CORE) else ...
 734                         tmpheaptop += isize;
 735
 736                         // set the gcsbstarttbl
 737                         int tmpsbs = 1+(isize-remain-1)/BAMBOO_SMEM_SIZE;
 738                         for(int k = 1; k < tmpsbs; k++) {
 739                                 gcsbstarttbl[b+k] = (INTPTR)(-1);
 740                         }
 741                         b += tmpsbs;
 742                         if(((isize-remain)%(BAMBOO_SMEM_SIZE)) == 0) {
 743                                 gcsbstarttbl[b] = (INTPTR)(-1);
 744                                 remain = ((tmpheaptop-gcbaseva)<(BAMBOO_LARGE_SMEM_BOUND)) ?
 745                                                      BAMBOO_SMEM_SIZE_L : BAMBOO_SMEM_SIZE;
 746                         } else {
 747                                 gcsbstarttbl[b] = (INTPTR)(tmpheaptop);
 748                                 remain = tmpheaptop-gcbaseva;
 749                                 int bound = remain<(BAMBOO_LARGE_SMEM_BOUND)?(BAMBOO_SMEM_SIZE_L):(BAMBOO_SMEM_SIZE);
 750                                 remain = bound - remain%bound;
 751                         } // if(((isize-remain)%(BAMBOO_SMEM_SIZE)) == 0) else ...
 752
 753                         // close current block and fill the header
 754                         memset(base, '\0', BAMBOO_CACHE_LINE_SIZE);
 755                         *((int*)base) = isize + BAMBOO_CACHE_LINE_SIZE;
 756                         cpysize = 0;
 757                         base = tmpheaptop;
 758                         remain -= BAMBOO_CACHE_LINE_SIZE;
 759                         tmpheaptop += BAMBOO_CACHE_LINE_SIZE;
 760                 } else {
 761                         remain -= isize;
 762                         // move the large obj
 763                         memcpy(tmpheaptop, gcheaptop, size);
 764                         // fill the remaining space with -2 padding
 765                         memset(tmpheaptop+size, -2, isize-size);
 766 #ifdef DEBUG
 767                         BAMBOO_DEBUGPRINT(0xea05);
 768                         BAMBOO_DEBUGPRINT_REG(gcheaptop);
 769                         BAMBOO_DEBUGPRINT_REG(tmpheaptop);
 770                         BAMBOO_DEBUGPRINT_REG(size);
 771                         BAMBOO_DEBUGPRINT_REG(isize);
 772 #endif
 773                         gcheaptop += size;
 774                         cpysize += isize;
 775                         if(host == BAMBOO_NUM_OF_CORE) {
 776                                 BAMBOO_START_CRITICAL_SECTION();
 777                                 RuntimeHashadd_I(gcpointertbl, ptr, tmpheaptop);
 778                                 BAMBOO_CLOSE_CRITICAL_SECTION();
 779 #ifdef DEBUG
 780                                 BAMBOO_DEBUGPRINT(0xcdcd);
 781                                 BAMBOO_DEBUGPRINT_REG(ptr);
 782                                 BAMBOO_DEBUGPRINT_REG(tmpheaptop);
 783 #endif
 784                         } else {
 785                                 // send the original host core with the mapping info
 786                                 send_msg_3(host, GCLOBJMAPPING, ptr, tmpheaptop);
 787 #ifdef DEBUG
 788                                 BAMBOO_DEBUGPRINT(0xcdcd);
 789                                 BAMBOO_DEBUGPRINT_REG(ptr);
 790                                 BAMBOO_DEBUGPRINT_REG(tmpheaptop);
 791 #endif
 792                         } // if(host == BAMBOO_NUM_OF_CORE) else ...
 793                         tmpheaptop += isize;
 794                 } // if(remain < isize) else ...
 795         } // while(gc_lobjmoreItems())
 796         if(cpysize > 0) {
 797                 // close current block, fill the header
 798                 memset(base, '\0', BAMBOO_CACHE_LINE_SIZE);
 799                 *((int*)base) = cpysize + BAMBOO_CACHE_LINE_SIZE;
 800         } else {
 801                 tmpheaptop -= BAMBOO_CACHE_LINE_SIZE;
 802         }
 803         gcheaptop = tmpheaptop;
 804 #ifdef DEBUG
 805         BAMBOO_DEBUGPRINT(0xea06);
 806         BAMBOO_DEBUGPRINT_REG(gcheaptop);
 807 #endif
 808 } // void moveLObjs()
 809
 810 inline void updateFreeMemList() {
 811         struct freeMemItem * tochange = bamboo_free_mem_list->head;
 812         if(tochange == NULL) {
 813                 bamboo_free_mem_list->head = tochange =
 814                         (struct freeMemItem *)RUNMALLOC(sizeof(struct freeMemItem));
 815         }
 816         // handle the top of the heap
 817         tochange->ptr = gcheaptop;
 818         tochange->size = BAMBOO_SHARED_MEM_SIZE + BAMBOO_BASE_VA - gcheaptop;
 819         // zero out all these spare memory
 820         memset(tochange->ptr, '\0', tochange->size);
 821         if(bamboo_free_mem_list->tail != tochange) {
 822                 bamboo_free_mem_list->tail = tochange;
 823                 if(bamboo_free_mem_list->tail != NULL) {
 824                         RUNFREE(bamboo_free_mem_list->tail);
 825                 }
 826         }
 827 } // void updateFreeMemList()
 828
 829 // enqueue root objs
 830 inline void tomark(struct garbagelist * stackptr) {
 831         if(MARKPHASE != gcphase) {
 832                 BAMBOO_EXIT(0xb101);
 833         }
 834         gcbusystatus = true;
 835         gcnumlobjs = 0;
 836
 837         int i,j;
 838         // enqueue current stack
 839         while(stackptr!=NULL) {
 840 #ifdef DEBUG
 841                 BAMBOO_DEBUGPRINT(0xe501);
 842                 BAMBOO_DEBUGPRINT_REG(stackptr->size);
 843                 BAMBOO_DEBUGPRINT_REG(stackptr->next);
 844                 BAMBOO_DEBUGPRINT_REG(stackptr->array[0]);
 845 #endif
 846                 for(i=0; i<stackptr->size; i++) {
 847                         if(stackptr->array[i] != NULL) {
 848                                 BAMBOO_START_CRITICAL_SECTION();
 849                                 gc_enqueue_I(stackptr->array[i]);
 850                                 BAMBOO_CLOSE_CRITICAL_SECTION();
 851                         }
 852                 }
 853                 stackptr=stackptr->next;
 854         }
 855
 856 #ifdef DEBUG
 857         BAMBOO_DEBUGPRINT(0xe503);
 858 #endif
 859         // enqueue objectsets
 860         for(i=0; i<NUMCLASSES; i++) {
 861                 struct parameterwrapper ** queues =
 862                         objectqueues[BAMBOO_NUM_OF_CORE][i];
 863                 int length = numqueues[BAMBOO_NUM_OF_CORE][i];
 864                 for(j = 0; j < length; ++j) {
 865                         struct parameterwrapper * parameter = queues[j];
 866                         struct ObjectHash * set=parameter->objectset;
 867                         struct ObjectNode * ptr=set->listhead;
 868                         while(ptr!=NULL) {
 869                                 BAMBOO_START_CRITICAL_SECTION();
 870                                 gc_enqueue_I((void *)ptr->key);
 871                                 BAMBOO_CLOSE_CRITICAL_SECTION();
 872                                 ptr=ptr->lnext;
 873                         }
 874                 }
 875         }
 876
 877         // euqueue current task descriptor
 878         if(currtpd != NULL) {
 879 #ifdef DEBUG
 880                 BAMBOO_DEBUGPRINT(0xe504);
 881 #endif
 882                 for(i=0; i<currtpd->numParameters; i++) {
 883                         BAMBOO_START_CRITICAL_SECTION();
 884                         gc_enqueue_I(currtpd->parameterArray[i]);
 885                         BAMBOO_CLOSE_CRITICAL_SECTION();
 886                 }
 887         }
 888
 889 #ifdef DEBUG
 890         BAMBOO_DEBUGPRINT(0xe505);
 891 #endif
 892         // euqueue active tasks
 893         struct genpointerlist * ptr=activetasks->list;
 894         while(ptr!=NULL) {
 895                 struct taskparamdescriptor *tpd=ptr->src;
 896                 int i;
 897                 for(i=0; i<tpd->numParameters; i++) {
 898                         BAMBOO_START_CRITICAL_SECTION();
 899                         gc_enqueue_I(tpd->parameterArray[i]);
 900                         BAMBOO_CLOSE_CRITICAL_SECTION();
 901                 }
 902                 ptr=ptr->inext;
 903         }
 904
 905 #ifdef DEBUG
 906         BAMBOO_DEBUGPRINT(0xe506);
 907 #endif
 908         // enqueue cached transferred obj
 909         struct QueueItem * tmpobjptr =  getHead(&objqueue);
 910         while(tmpobjptr != NULL) {
 911                 struct transObjInfo * objInfo =
 912                         (struct transObjInfo *)(tmpobjptr->objectptr);
 913                 BAMBOO_START_CRITICAL_SECTION();
 914                 gc_enqueue_I(objInfo->objptr);
 915                 BAMBOO_CLOSE_CRITICAL_SECTION();
 916                 tmpobjptr = getNextQueueItem(tmpobjptr);
 917         }
 918
 919 #ifdef DEBUG
 920         BAMBOO_DEBUGPRINT(0xe507);
 921 #endif
 922         // enqueue cached objs to be transferred
 923         struct QueueItem * item = getHead(totransobjqueue);
 924         while(item != NULL) {
 925                 struct transObjInfo * totransobj =
 926                         (struct transObjInfo *)(item->objectptr);
 927                 BAMBOO_START_CRITICAL_SECTION();
 928                 gc_enqueue_I(totransobj->objptr);
 929                 BAMBOO_CLOSE_CRITICAL_SECTION();
 930                 item = getNextQueueItem(item);
 931         } // while(item != NULL)
 932 } // void tomark(struct garbagelist * stackptr)
 933
 934 inline void markObj(void * objptr) {
 935         if(objptr == NULL) {
 936                 return;
 937         }
 938         if(ISSHAREDOBJ(objptr)) {
 939                 int host = hostcore(objptr);
 940                 if(BAMBOO_NUM_OF_CORE == host) {
 941                         // on this core
 942                         BAMBOO_START_CRITICAL_SECTION();
 943                         gc_enqueue_I(objptr);
 944                         BAMBOO_CLOSE_CRITICAL_SECTION();
 945                 } else {
 946 #ifdef GC_DEBUG
 947                         BAMBOO_DEBUGPRINT(0xbbbb);
 948                         BAMBOO_DEBUGPRINT_REG(host);
 949                         BAMBOO_DEBUGPRINT_REG(objptr);
 950 #endif
 951                         // send a msg to host informing that objptr is active
 952                         send_msg_2(host, GCMARKEDOBJ, objptr);
 953                         gcself_numsendobjs++;
 954                 }
 955         } else {
 956                 BAMBOO_START_CRITICAL_SECTION();
 957                 gc_enqueue_I(objptr);
 958                 BAMBOO_CLOSE_CRITICAL_SECTION();
 959         } // if(ISSHAREDOBJ(objptr))
 960 } // void markObj(void * objptr)
 961
 962 inline void mark(bool isfirst,
 963                              struct garbagelist * stackptr) {
 964 #ifdef DEBUG
 965         BAMBOO_DEBUGPRINT(0xed01);
 966 #endif
 967         if(isfirst) {
 968 #ifdef DEBUG
 969                 BAMBOO_DEBUGPRINT(0xed02);
 970 #endif
 971                 // enqueue root objs
 972                 tomark(stackptr);
 973                 gccurr_heaptop = 0; // record the size of all active objs in this core
 974                                   // aligned but does not consider block boundaries
 975                 gcmarkedptrbound = 0;
 976         }
 977 #ifdef DEBUG
 978         BAMBOO_DEBUGPRINT(0xed03);
 979 #endif
 980         int isize = 0;
 981         bool checkfield = true;
 982         bool sendStall = false;
 983         // mark phase
 984         while(MARKPHASE == gcphase) {
 985 #ifdef DEBUG
 986                 BAMBOO_DEBUGPRINT(0xed04);
 987 #endif
 988                 while(gc_moreItems2()) {
 989 #ifdef DEBUG
 990                         BAMBOO_DEBUGPRINT(0xed05);
 991 #endif
 992                         sendStall = false;
 993                         gcbusystatus = true;
 994                         checkfield = true;
 995                         void * ptr = gc_dequeue2();
 996 #ifdef DEBUG
 997                         BAMBOO_DEBUGPRINT_REG(ptr);
 998 #endif
 999                         int size = 0;
1000                         int isize = 0;
1001                         int type = 0;
1002                         // check if it is a shared obj
1003                         if(ISSHAREDOBJ(ptr)) {
1004                                 // a shared obj, check if it is a local obj on this core
1005                                 if(isLarge(ptr, &type, &size)) {
1006                                         // ptr is a large object
1007                                         if(((int *)ptr)[6] == 0) {
1008                                                 // not marked and not enqueued
1009                                                 BAMBOO_START_CRITICAL_SECTION();
1010                                                 gc_lobjenqueue_I(ptr, size, BAMBOO_NUM_OF_CORE);
1011                                                 gcnumlobjs++;
1012                                                 BAMBOO_CLOSE_CRITICAL_SECTION();
1013                                                 // mark this obj
1014                                                 ((int *)ptr)[6] = 1;
1015                                         }
1016                                 } else {
1017                                         bool islocal = isLocal(ptr);
1018                                         if (islocal && (((int *)ptr)[6] == 0)) {
1019                                                 // ptr is an unmarked active object on this core
1020                                                 ALIGNSIZE(size, &isize);
1021                                                 gccurr_heaptop += isize;
1022 #ifdef GC_DEBUG
1023                                                 BAMBOO_DEBUGPRINT(0xaaaa);
1024                                                 BAMBOO_DEBUGPRINT_REG(ptr);
1025                                                 BAMBOO_DEBUGPRINT_REG(isize);
1026 #endif
1027                                                 // mark this obj
1028                                                 ((int *)ptr)[6] = 1;
1029                                                 if(ptr + size > gcmarkedptrbound) {
1030                                                         gcmarkedptrbound = ptr + size;
1031                                                 } // if(ptr + size > gcmarkedptrbound)
1032                                         } else if ((!islocal) && (((int *)ptr)[6] == 0)) {
1033                                                 int host = hostcore(ptr);
1034 #ifdef GC_DEBUG
1035                                                 BAMBOO_DEBUGPRINT(0xbbbb);
1036                                                 BAMBOO_DEBUGPRINT_REG(host);
1037                                                 BAMBOO_DEBUGPRINT_REG(ptr);
1038 #endif
1039                                                 // send a msg to host informing that ptr is active
1040                                                 send_msg_2(host, GCMARKEDOBJ, ptr);
1041                                                 gcself_numsendobjs++;
1042                                                 checkfield = false;
1043                                         }// if(isLocal(ptr)) else ...
1044                                 } // if(isLarge(ptr, &type, &size)) else ...
1045                         } // if(ISSHAREDOBJ(ptr))
1046 #ifdef DEBUG
1047                         BAMBOO_DEBUGPRINT(0xed06);
1048 #endif
1049
1050                         if(checkfield) {
1051                                 // scan all pointers in ptr
1052                                 unsigned INTPTR * pointer;
1053                                 pointer=pointerarray[type];
1054                                 if (pointer==0) {
1055                                         /* Array of primitives */
1056                                         /* Do nothing */
1057                                 } else if (((INTPTR)pointer)==1) {
1058                                         /* Array of pointers */
1059                                         struct ArrayObject *ao=(struct ArrayObject *) ptr;
1060                                         int length=ao->___length___;
1061                                         int j;
1062                                         for(j=0; j<length; j++) {
1063                                                 void *objptr =
1064                                                         ((void **)(((char *)&ao->___length___)+sizeof(int)))[j];
1065                                                 markObj(objptr);
1066                                         }
1067                                 } else {
1068                                         INTPTR size=pointer[0];
1069                                         int i;
1070                                         for(i=1; i<=size; i++) {
1071                                                 unsigned int offset=pointer[i];
1072                                                 void * objptr=*((void **)(((char *)ptr)+offset));
1073                                                 markObj(objptr);
1074                                         }
1075                                 } // if (pointer==0) else if ... else ...
1076                         } // if(checkfield)
1077                 } // while(!isEmpty(gctomark))
1078 #ifdef DEBUG
1079                 BAMBOO_DEBUGPRINT(0xed07);
1080 #endif
1081                 gcbusystatus = false;
1082                 // send mark finish msg to core coordinator
1083                 if(STARTUPCORE == BAMBOO_NUM_OF_CORE) {
1084 #ifdef DEBUG
1085                         BAMBOO_DEBUGPRINT(0xed08);
1086 #endif
1087                         gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
1088                         gcnumsendobjs[BAMBOO_NUM_OF_CORE] = gcself_numsendobjs;
1089                         gcnumreceiveobjs[BAMBOO_NUM_OF_CORE] = gcself_numreceiveobjs;
1090                         gcloads[BAMBOO_NUM_OF_CORE] = gccurr_heaptop;
1091                 } else {
1092                         if(!sendStall) {
1093 #ifdef DEBUG
1094                                 BAMBOO_DEBUGPRINT(0xed09);
1095 #endif
1096                                 send_msg_4(STARTUPCORE, GCFINISHMARK, BAMBOO_NUM_OF_CORE,
1097                                                                          gcself_numsendobjs, gcself_numreceiveobjs);
1098                                 sendStall = true;
1099                         }
1100                 }
1101 #ifdef DEBUG
1102                 BAMBOO_DEBUGPRINT(0xed0a);
1103 #endif
1104
1105                 if(BAMBOO_NUM_OF_CORE == 0) {
1106 #ifdef DEBUG
1107                         BAMBOO_DEBUGPRINT(0xed0b);
1108 #endif
1109                         return;
1110                 }
1111         } // while(MARKPHASE == gcphase)
1112 } // mark()
1113
1114 inline void compact2Heaptop() {
1115         // no cores with spare mem and some cores are blocked with pending move
1116         // find the current heap top and make them move to the heap top
1117         int p;
1118         int numblocks = gcfilledblocks[gctopcore];
1119         BASEPTR(gctopcore, numblocks, &p);
1120         int b;
1121         BLOCKINDEX(p, &b);
1122         int remain = b<NUMCORES ? BAMBOO_SMEM_SIZE_L : BAMBOO_SMEM_SIZE;
1123         /*if((gctopcore == STARTUPCORE) && (b == 0)) {
1124                 remain -= gcreservedsb*BAMBOO_SMEM_SIZE;
1125                 p += gcreservedsb*BAMBOO_SMEM_SIZE;
1126         }*/
1127         for(int i = 0; i < NUMCORES; i++) {
1128                 if((gccorestatus[i] != 0) && (gcrequiredmems[i] > 0)) {
1129                         int memneed = gcrequiredmems[i] + BAMBOO_CACHE_LINE_SIZE;
1130                         if(STARTUPCORE == i) {
1131                                 gctomove = true;
1132                                 gcmovestartaddr = p;
1133                                 gcdstcore = gctopcore;
1134                                 gcblock2fill = numblocks + 1;
1135                         } else {
1136                                 send_msg_4(i, GCMOVESTART, gctopcore, p, numblocks + 1);
1137                         }
1138                         if(memneed < remain) {
1139                                 p += memneed;
1140                                 gcrequiredmems[i] = 0;
1141                                 gcmovepending--;
1142                                 gcloads[gctopcore] += memneed;
1143                         } else {
1144                                 // next available block
1145                                 p += remain;
1146                                 gcfilledblocks[gctopcore] += 1;
1147                                 int newbase = 0;
1148                                 BASEPTR(gctopcore, gcfilledblocks[gctopcore], &newbase);
1149                                 gcloads[gctopcore] = newbase;
1150                                 gcrequiredmems[i] -= remain - BAMBOO_CACHE_LINE_SIZE;
1151                                 gcstopblock[gctopcore]++;
1152                                 if(gcheapdirection) {
1153                                         gctopcore++;
1154                                         if(gctopcore== NUMCORES) {
1155                                                 gctopcore--;
1156                                                 gcheapdirection = false;
1157                                         }
1158                                 } else {
1159                                         gctopcore--;
1160                                         if(gctopcore < 0) {
1161                                                 gctopcore++;
1162                                                 gcheapdirection = true;
1163                                         }
1164                                 }
1165                                 numblocks = gcstopblock[gctopcore];
1166                                 BASEPTR(gctopcore, numblocks, &p);
1167                                 BLOCKINDEX(p, &p);
1168                                 remain = b<NUMCORES ? BAMBOO_SMEM_SIZE_L : BAMBOO_SMEM_SIZE;
1169                         } // if(memneed < remain)
1170                 } // if((gccorestatus[i] != 0) && (gcrequiredmems[i] > 0))
1171         } // for(i = 0; i < NUMCORES; i++)
1172 } // void compact2Heaptop()
1173
1174 inline void resolvePendingMoveRequest() {
1175 #ifdef DEBUG
1176         BAMBOO_DEBUGPRINT(0xeb01);
1177 #endif
1178         int i;
1179         int j;
1180         bool nosparemem = true;
1181         bool haspending = false;
1182         bool hasrunning = false;
1183         bool noblock = false;
1184         int dstcore = 0;
1185         int sourcecore = 0;
1186         for(i = j = 0; (i < NUMCORES) && (j < NUMCORES);) {
1187                 if(nosparemem) {
1188                         // check if there are cores with spare mem
1189                         if(gccorestatus[i] == 0) {
1190                                 // finished working, check if it still have spare mem
1191                                 if(gcfilledblocks[i] < gcstopblock[i]) {
1192                                         // still have spare mem
1193                                         nosparemem = false;
1194                                         dstcore = i;
1195                                 } // if(gcfilledblocks[i] < gcstopblock[i]) else ...
1196                         }
1197                         i++;
1198                 } // if(nosparemem)
1199                 if(!haspending) {
1200                         if(gccorestatus[j] != 0) {
1201                                 // not finished, check if it has pending move requests
1202                                 if((gcfilledblocks[j]==gcstopblock[j])&&(gcrequiredmems[j]>0)) {
1203                                         sourcecore = j;
1204                                         haspending = true;
1205                                 } else {
1206                                         hasrunning = true;
1207                                 } // if((gcfilledblocks[i] == gcstopblock[i])...) else ...
1208                         } // if(gccorestatus[i] == 0) else ...
1209                         j++;
1210                 } // if(!haspending)
1211                 if(!nosparemem && haspending) {
1212                         // find match
1213                         int tomove = 0;
1214                         int startaddr = 0;
1215                         BAMBOO_START_CRITICAL_SECTION();
1216                         gcrequiredmems[dstcore] = assignSpareMem_I(sourcecore,
1217                                                                                gcrequiredmems[dstcore],
1218                                                                                                                                                                                            &tomove,
1219                                                                                                                                                                                            &startaddr);
1220                         BAMBOO_CLOSE_CRITICAL_SECTION();
1221                         if(STARTUPCORE == dstcore) {
1222                                 gcdstcore = sourcecore;
1223                                 gctomove = true;
1224                                 gcmovestartaddr = startaddr;
1225                                 gcblock2fill = tomove;
1226                         } else {
1227                                 send_msg_4(dstcore, GCMOVESTART, sourcecore, startaddr, tomove);
1228                         }
1229                         if(gcrequiredmems[dstcore] == 0) {
1230                                 gcmovepending--;
1231                         }
1232                         nosparemem = true;
1233                         haspending = false;
1234                         noblock = true;
1235                 }
1236         } // for(i = 0; i < NUMCORES; i++)
1237 #ifdef DEBUG
1238         BAMBOO_DEBUGPRINT(0xcccc);
1239         BAMBOO_DEBUGPRINT_REG(hasrunning);
1240         BAMBOO_DEBUGPRINT_REG(haspending);
1241         BAMBOO_DEBUGPRINT_REG(noblock);
1242 #endif
1243
1244         if(!hasrunning && !noblock) {
1245                 gcphase = SUBTLECOMPACTPHASE;
1246                 compact2Heaptop();
1247         }
1248
1249 } // void resovePendingMoveRequest()
1250
1251 struct moveHelper {
1252         int numblocks; // block num for heap
1253         INTPTR base; // base virtual address of current heap block
1254         INTPTR ptr; // virtual address of current heap top
1255         int offset; // offset in current heap block
1256         int blockbase; // virtual address of current small block to check
1257         int blockbound; // bound virtual address of current small blcok
1258         int sblockindex; // index of the small blocks
1259         int top; // real size of current heap block to check
1260         int bound; // bound size of current heap block to check
1261 }; // struct moveHelper
1262
1263 inline void nextSBlock(struct moveHelper * orig) {
1264         orig->blockbase = orig->blockbound;
1265 innernextSBlock:
1266         if(orig->blockbase >= orig->bound) {
1267                 // end of current heap block, jump to next one
1268                 orig->numblocks++;
1269                 BASEPTR(BAMBOO_NUM_OF_CORE, orig->numblocks, &(orig->base));
1270                 orig->bound = orig->base + BAMBOO_SMEM_SIZE;
1271                 orig->blockbase = orig->base;
1272         }
1273         orig->sblockindex = (orig->blockbase-BAMBOO_BASE_VA)/BAMBOO_SMEM_SIZE;
1274         if(gcsbstarttbl[orig->sblockindex] == -1) {
1275                 // goto next sblock
1276                 orig->sblockindex += 1;
1277                 orig->blockbase += BAMBOO_SMEM_SIZE;
1278                 goto innernextSBlock;
1279         } else if(gcsbstarttbl[orig->sblockindex] != 0) {
1280                 // not start from the very beginning
1281                 orig->blockbase = gcsbstarttbl[orig->sblockindex];
1282         }
1283         orig->blockbound = orig->blockbase + *((int*)(orig->blockbase));
1284         orig->offset = BAMBOO_CACHE_LINE_SIZE;
1285         orig->ptr = orig->blockbase + orig->offset;
1286 } // void nextSBlock(struct moveHelper * orig)
1287
1288 inline void initOrig_Dst(struct moveHelper * orig,
1289                                      struct moveHelper * to) {
1290         // init the dst ptr
1291         to->numblocks = 0;
1292         to->top = to->offset = BAMBOO_CACHE_LINE_SIZE;
1293         to->bound = BAMBOO_SMEM_SIZE_L;
1294         BASEPTR(BAMBOO_NUM_OF_CORE, to->numblocks, &(to->base));
1295         /*if(STARTUPCORE == BAMBOO_NUM_OF_CORE) {
1296                 to->base += gcreservedsb * BAMBOO_SMEM_SIZE;
1297                 to->top += gcreservedsb * BAMBOO_SMEM_SIZE;
1298         }*/
1299         to->ptr = to->base + to->offset;
1300
1301         // init the orig ptr
1302         orig->numblocks = 0;
1303         orig->base = to->base;
1304         orig->bound = to->base + BAMBOO_SMEM_SIZE_L;
1305         orig->blockbase = orig->base;
1306         /*if(STARTUPCORE == BAMBOO_NUM_OF_CORE) {
1307                 orig->sblockindex = gcreservedsb;
1308         } else {*/
1309                 orig->sblockindex = (orig->base - BAMBOO_BASE_VA) / BAMBOO_SMEM_SIZE;
1310         //}
1311         if(gcsbstarttbl[orig->sblockindex] == -1) {
1312                 // goto next sblock
1313                 orig->blockbound =
1314                         BAMBOO_BASE_VA+BAMBOO_SMEM_SIZE*(orig->sblockindex+1);
1315                 nextSBlock(orig);
1316                 return;
1317         } else if(gcsbstarttbl[orig->sblockindex] != 0) {
1318                 orig->blockbase = gcsbstarttbl[orig->sblockindex];
1319         }
1320         orig->blockbound = orig->blockbase + *((int*)(orig->blockbase));
1321         orig->offset = BAMBOO_CACHE_LINE_SIZE;
1322         orig->ptr = orig->blockbase + orig->offset;
1323 } // void initOrig_Dst(struct moveHelper * orig, struct moveHelper * to)
1324
1325 inline void nextBlock(struct moveHelper * to) {
1326         to->top = to->bound + BAMBOO_CACHE_LINE_SIZE; // header!
1327         to->bound += BAMBOO_SMEM_SIZE;
1328         to->numblocks++;
1329         BASEPTR(BAMBOO_NUM_OF_CORE, to->numblocks, &(to->base));
1330         to->offset = BAMBOO_CACHE_LINE_SIZE;
1331         to->ptr = to->base + to->offset;
1332 } // void nextBlock(struct moveHelper * to)
1333
1334 // endaddr does not contain spaces for headers
1335 inline bool moveobj(struct moveHelper * orig,
1336                                 struct moveHelper * to,
1337                                                         int stopblock) {
1338         if(stopblock == 0) {
1339                 return true;
1340         }
1341
1342 #ifdef DEBUG
1343         BAMBOO_DEBUGPRINT(0xe201);
1344         BAMBOO_DEBUGPRINT_REG(orig->ptr);
1345         BAMBOO_DEBUGPRINT_REG(to->ptr);
1346 #endif
1347
1348         int type = 0;
1349         int size = 0;
1350         int mark = 0;
1351         int isize = 0;
1352 innermoveobj:
1353         while((char)(*((int*)(orig->ptr))) == (char)(-2)) {
1354                 orig->ptr = (int*)(orig->ptr) + 1;
1355         }
1356         if((orig->ptr > orig->bound) || (orig->ptr == orig->blockbound)) {
1357                 nextSBlock(orig);
1358                 goto innermoveobj;
1359         }
1360 #ifdef DEBUG
1361         BAMBOO_DEBUGPRINT(0xe202);
1362 #endif
1363         // check the obj's type, size and mark flag
1364         type = ((int *)(orig->ptr))[0];
1365         size = 0;
1366         if(type == -1) {
1367                 // end of this block, go to next one
1368                 nextSBlock(orig);
1369                 goto innermoveobj;
1370         } else if(type < NUMCLASSES) {
1371                 // a normal object
1372                 size = classsize[type];
1373         } else {
1374                 // an array
1375                 struct ArrayObject *ao=(struct ArrayObject *)(orig->ptr);
1376                 int elementsize=classsize[type];
1377                 int length=ao->___length___;
1378                 size=sizeof(struct ArrayObject)+length*elementsize;
1379         }
1380         mark = ((int *)(orig->ptr))[6];
1381 #ifdef DEBUG
1382         BAMBOO_DEBUGPRINT(0xe203);
1383 #endif
1384         if(mark == 1) {
1385 #ifdef DEBUG
1386                 BAMBOO_DEBUGPRINT(0xe204);
1387 #endif
1388                 // marked obj, copy it to current heap top
1389                 // check to see if remaining space is enough
1390                 ALIGNSIZE(size, &isize);
1391                 if(to->top + isize > to->bound) {
1392                         // fill -1 indicating the end of this block
1393                         if(to->top != to->bound) {
1394                                 *((int*)to->ptr) = -1;
1395                         }
1396                         //memset(to->ptr+1,  -2, to->bound - to->top - 1);
1397                         // fill the header of this block and then go to next block
1398         to->offset += to->bound - to->top;
1399                         memset(to->base, '\0', BAMBOO_CACHE_LINE_SIZE);
1400                         (*((int*)(to->base))) = to->offset;
1401                         nextBlock(to);
1402                         if(stopblock == to->numblocks) {
1403                                 // already fulfilled the block
1404                                 to->offset = 0;
1405                                 to->ptr = to->base;
1406                                 return true;
1407                         } // if(stopblock == to->numblocks)
1408                 } // if(to->top + isize > to->bound)
1409                 // set the mark field to 2, indicating that this obj has been moved and need to be flushed
1410                 ((int *)(orig->ptr))[6] = 2;
1411                 if(to->ptr != orig->ptr) {
1412                         memcpy(to->ptr, orig->ptr, size);
1413                         // fill the remaining space with -2
1414                         memset(to->ptr+size, -2, isize-size);
1415                 }
1416                 // store mapping info
1417                 BAMBOO_START_CRITICAL_SECTION();
1418                 RuntimeHashadd_I(gcpointertbl, orig->ptr, to->ptr);
1419                 BAMBOO_CLOSE_CRITICAL_SECTION();
1420 #ifdef DEBUG
1421                 BAMBOO_DEBUGPRINT(0xcdcd);
1422                 BAMBOO_DEBUGPRINT_REG(orig->ptr);
1423                 BAMBOO_DEBUGPRINT_REG(to->ptr);
1424 #endif
1425                 gccurr_heaptop -= isize;
1426                 to->ptr += isize;
1427                 to->offset += isize;
1428                 to->top += isize;
1429         } // if(mark == 1)
1430 #ifdef DEBUG
1431         BAMBOO_DEBUGPRINT(0xe205);
1432 #endif
1433         // move to next obj
1434         orig->ptr += isize;
1435 #ifdef DEBUG
1436         BAMBOO_DEBUGPRINT_REG(isize);
1437         BAMBOO_DEBUGPRINT_REG(orig->ptr);
1438 #endif
1439         if((orig->ptr > orig->bound) || (orig->ptr == orig->blockbound)) {
1440 #ifdef DEBUG
1441         BAMBOO_DEBUGPRINT(0xe206);
1442 #endif
1443                 nextSBlock(orig);
1444         }
1445 #ifdef DEBUG
1446         BAMBOO_DEBUGPRINT_REG(orig->ptr);
1447 #endif
1448         return false;
1449 } //bool moveobj(struct moveHelper* orig,struct moveHelper* to,int* endaddr)
1450
1451 // should be invoked with interrupt closed
1452 inline int assignSpareMem_I(int sourcecore,
1453                                         int * requiredmem,
1454                                                                                                           int * tomove,
1455                                                                                                           int * startaddr) {
1456         int b = 0;
1457         BLOCKINDEX(gcloads[sourcecore], &b);
1458         int boundptr = b<NUMCORES?(b+1)*BAMBOO_SMEM_SIZE_L
1459                 :BAMBOO_LARGE_SMEM_BOUND+(b-NUMCORES+1)*BAMBOO_SMEM_SIZE;
1460         int remain = boundptr - gcloads[sourcecore];
1461         int memneed = requiredmem + BAMBOO_CACHE_LINE_SIZE;
1462         *startaddr = gcloads[sourcecore];
1463         *tomove = gcfilledblocks[sourcecore] + 1;
1464         if(memneed < remain) {
1465                 gcloads[sourcecore] += memneed;
1466                 return 0;
1467         } else {
1468                 // next available block
1469                 gcfilledblocks[sourcecore] += 1;
1470                 int newbase = 0;
1471                 BASEPTR(sourcecore, gcfilledblocks[sourcecore], &newbase);
1472                 gcloads[sourcecore] = newbase;
1473                 return requiredmem-remain;
1474         }
1475 } // int assignSpareMem_I(int ,int * , int * , int * )
1476
1477 // should be invoked with interrupt closed
1478 inline bool gcfindSpareMem_I(int * startaddr,
1479                                          int * tomove,
1480                                                                                                    int * dstcore,
1481                                                                                                    int requiredmem,
1482                                                                                                    int requiredcore) {
1483         for(int k = 0; k < NUMCORES; k++) {
1484                 if((gccorestatus[k] == 0) && (gcfilledblocks[k] < gcstopblock[k])) {
1485                         // check if this stopped core has enough mem
1486                         assignSpareMem_I(k, requiredmem, tomove, startaddr);
1487                         *dstcore = k;
1488                         return true;
1489                 }
1490         }
1491         // if can not find spare mem right now, hold the request
1492         gcrequiredmems[requiredcore] = requiredmem;
1493         gcmovepending++;
1494         return false;
1495 } //bool gcfindSpareMem_I(int* startaddr,int* tomove,int mem,int core)
1496
1497 inline bool compacthelper(struct moveHelper * orig,
1498                                       struct moveHelper * to,
1499                                                                                                         int * filledblocks,
1500                                                                                                         int * heaptopptr,
1501                                                                                                         bool * localcompact) {
1502         // scan over all objs in this block, compact the marked objs
1503         // loop stop when finishing either scanning all active objs or
1504         // fulfilled the gcstopblock
1505 #ifdef DEBUG
1506         BAMBOO_DEBUGPRINT(0xe101);
1507         BAMBOO_DEBUGPRINT_REG(gcblock2fill);
1508 #endif
1509 innercompact:
1510         do {
1511                 bool stop = moveobj(orig, to, gcblock2fill);
1512                 if(stop) {
1513                         break;
1514                 }
1515         } while(orig->ptr < gcmarkedptrbound);
1516         // if no objs have been compact, do nothing,
1517         // otherwise, fill the header of this block
1518         if(to->offset > BAMBOO_CACHE_LINE_SIZE) {
1519                 memset(to->base, '\0', BAMBOO_CACHE_LINE_SIZE);
1520                 (*((int*)(to->base))) = to->offset;
1521         } else {
1522                 to->offset = 0;
1523                 to->ptr = to->base;
1524                 to->top -= BAMBOO_CACHE_LINE_SIZE;
1525         } // if(to->offset > BAMBOO_CACHE_LINE_SIZE) else ...
1526         if(*localcompact) {
1527                 *heaptopptr = to->ptr;
1528                 *filledblocks = to->numblocks;
1529         }
1530 #ifdef DEBUG
1531         BAMBOO_DEBUGPRINT(0xe102);
1532         BAMBOO_DEBUGPRINT_REG(orig->ptr);
1533         BAMBOO_DEBUGPRINT_REG(gcmarkedptrbound);
1534         BAMBOO_DEBUGPRINT_REG(*heaptopptr);
1535         BAMBOO_DEBUGPRINT_REG(*filledblocks);
1536 #endif
1537
1538         // send msgs to core coordinator indicating that the compact is finishing
1539         // send compact finish message to core coordinator
1540         if(STARTUPCORE == BAMBOO_NUM_OF_CORE) {
1541                 gcfilledblocks[BAMBOO_NUM_OF_CORE] = *filledblocks;
1542                 gcloads[BAMBOO_NUM_OF_CORE] = *heaptopptr;
1543                 if(orig->ptr < gcmarkedptrbound) {
1544                         // ask for more mem
1545                         gctomove = false;
1546                         BAMBOO_START_CRITICAL_SECTION();
1547                         if(gcfindSpareMem_I(&gcmovestartaddr, &gcblock2fill, &gcdstcore,
1548                                                               gccurr_heaptop, BAMBOO_NUM_OF_CORE)) {
1549                                 gctomove = true;
1550                         } else {
1551                                 BAMBOO_CLOSE_CRITICAL_SECTION();
1552                                 return false;
1553                         }
1554                         BAMBOO_CLOSE_CRITICAL_SECTION();
1555                 } else {
1556                         gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
1557                         return true;
1558                 }
1559         } else {
1560                 if(orig->ptr < gcmarkedptrbound) {
1561                         // ask for more mem
1562                         gctomove = false;
1563                         send_msg_5(STARTUPCORE, GCFINISHCOMPACT, BAMBOO_NUM_OF_CORE,
1564                                                *filledblocks, *heaptopptr, gccurr_heaptop);
1565                 } else {
1566                         // finish compacting
1567                         send_msg_5(STARTUPCORE, GCFINISHCOMPACT, BAMBOO_NUM_OF_CORE,
1568                                                *filledblocks, *heaptopptr, 0);
1569                 }
1570         } // if(STARTUPCORE == BAMBOO_NUM_OF_CORE)
1571
1572         if(orig->ptr < gcmarkedptrbound) {
1573                 // still have unpacked obj
1574                 while(!gctomove) {};
1575                 gctomove = false;
1576
1577                 to->ptr = gcmovestartaddr;
1578                 to->numblocks = gcblock2fill - 1;
1579                 to->bound = (to->numblocks==0)?
1580                         BAMBOO_SMEM_SIZE_L:
1581                         BAMBOO_SMEM_SIZE_L+BAMBOO_SMEM_SIZE*to->numblocks;
1582                 BASEPTR(BAMBOO_NUM_OF_CORE, to->numblocks, &(to->base));
1583                 to->offset = to->ptr - to->base;
1584                 to->top = (to->numblocks==0)?
1585                         (to->offset):(to->bound-BAMBOO_SMEM_SIZE+to->offset);
1586                 to->base = to->ptr;
1587                 to->offset = BAMBOO_CACHE_LINE_SIZE;
1588                 to->ptr += to->offset; // for header
1589                 to->top += to->offset;
1590                 if(gcdstcore == BAMBOO_NUM_OF_CORE) {
1591                         *localcompact = true;
1592                 } else {
1593                         *localcompact = false;
1594                 }
1595                 goto innercompact;
1596         }
1597         return true;
1598 } // void compacthelper()
1599
1600 inline void compact() {
1601         if(COMPACTPHASE != gcphase) {
1602                 BAMBOO_EXIT(0xb102);
1603         }
1604
1605         // initialize pointers for comapcting
1606         struct moveHelper * orig =
1607                 (struct moveHelper *)RUNMALLOC(sizeof(struct moveHelper));
1608         struct moveHelper * to =
1609                 (struct moveHelper *)RUNMALLOC(sizeof(struct moveHelper));
1610
1611         initOrig_Dst(orig, to);
1612
1613         int filledblocks = 0;
1614         INTPTR heaptopptr = 0;
1615         bool localcompact = true;
1616         compacthelper(orig, to, &filledblocks, &heaptopptr, &localcompact);
1617
1618         RUNFREE(orig);
1619         RUNFREE(to);
1620 } // compact()
1621
1622 inline void * flushObj(void * objptr) {
1623 #ifdef DEBUG
1624         BAMBOO_DEBUGPRINT(0xe401);
1625 #endif
1626         void * dstptr = NULL;
1627         if(ISSHAREDOBJ(objptr)) {
1628 #ifdef DEBUG
1629                 BAMBOO_DEBUGPRINT(0xe402);
1630                 BAMBOO_DEBUGPRINT_REG(objptr);
1631 #endif
1632                 // a shared obj ptr, change to new address
1633                 BAMBOO_START_CRITICAL_SECTION();
1634                 RuntimeHashget(gcpointertbl, objptr, &dstptr);
1635                 BAMBOO_CLOSE_CRITICAL_SECTION();
1636 #ifdef DEBUG
1637                 BAMBOO_DEBUGPRINT_REG(dstptr);
1638 #endif
1639                 if(NULL == dstptr) {
1640 #ifdef DEBUG
1641                         BAMBOO_DEBUGPRINT(0xe403);
1642 #endif
1643                         // send msg to host core for the mapping info
1644                         gcobj2map = (int)objptr;
1645                         gcismapped = false;
1646                         gcmappedobj = NULL;
1647                         send_msg_3(hostcore(objptr), GCMAPREQUEST, (int)objptr,
1648                                                                  BAMBOO_NUM_OF_CORE);
1649                         while(!gcismapped) {}
1650                         BAMBOO_START_CRITICAL_SECTION();
1651                         RuntimeHashget(gcpointertbl, objptr, &dstptr);
1652                         BAMBOO_CLOSE_CRITICAL_SECTION();
1653 #ifdef DEBUG
1654                         BAMBOO_DEBUGPRINT_REG(dstptr);
1655 #endif
1656                 }
1657         } // if(ISSHAREDOBJ(objptr))
1658 #ifdef DEBUG
1659         BAMBOO_DEBUGPRINT(0xe404);
1660 #endif
1661         return dstptr;
1662 } // void flushObj(void * objptr, void ** tochange)
1663
1664 inline void flushRuntimeObj(struct garbagelist * stackptr) {
1665         int i,j;
1666         // flush current stack
1667         while(stackptr!=NULL) {
1668                 for(i=0; i<stackptr->size; i++) {
1669                         if(stackptr->array[i] != NULL) {
1670                                 stackptr->array[i] = flushObj(stackptr->array[i]);
1671                         }
1672                 }
1673                 stackptr=stackptr->next;
1674         }
1675
1676         // flush objectsets
1677         for(i=0; i<NUMCLASSES; i++) {
1678                 struct parameterwrapper ** queues =
1679                         objectqueues[BAMBOO_NUM_OF_CORE][i];
1680                 int length = numqueues[BAMBOO_NUM_OF_CORE][i];
1681                 for(j = 0; j < length; ++j) {
1682                         struct parameterwrapper * parameter = queues[j];
1683                         struct ObjectHash * set=parameter->objectset;
1684                         struct ObjectNode * ptr=set->listhead;
1685                         while(ptr!=NULL) {
1686                                 ptr->key = flushObj((void *)ptr->key);
1687                                 ptr=ptr->lnext;
1688                         }
1689                 }
1690         }
1691
1692         // flush current task descriptor
1693         if(currtpd != NULL) {
1694                 for(i=0; i<currtpd->numParameters; i++) {
1695                         currtpd->parameterArray[i] = flushObj(currtpd->parameterArray[i]);
1696                 }
1697         }
1698
1699         // flush active tasks
1700         struct genpointerlist * ptr=activetasks->list;
1701         while(ptr!=NULL) {
1702                 struct taskparamdescriptor *tpd=ptr->src;
1703                 int i;
1704                 for(i=0; i<tpd->numParameters; i++) {
1705                         tpd->parameterArray[i] = flushObj(tpd->parameterArray[i]);
1706                 }
1707                 ptr=ptr->inext;
1708         }
1709
1710         // flush cached transferred obj
1711         struct QueueItem * tmpobjptr =  getHead(&objqueue);
1712         while(tmpobjptr != NULL) {
1713                 struct transObjInfo * objInfo =
1714                         (struct transObjInfo *)(tmpobjptr->objectptr);
1715                 objInfo->objptr = flushObj(objInfo->objptr);
1716                 tmpobjptr = getNextQueueItem(tmpobjptr);
1717         }
1718
1719         // flush cached objs to be transferred
1720         struct QueueItem * item = getHead(totransobjqueue);
1721         while(item != NULL) {
1722                 struct transObjInfo * totransobj =
1723                         (struct transObjInfo *)(item->objectptr);
1724                 totransobj->objptr = flushObj(totransobj->objptr);
1725                 item = getNextQueueItem(item);
1726         } // while(item != NULL)
1727 } // void flushRuntimeObj(struct garbagelist * stackptr)
1728
1729 inline void flush(struct garbagelist * stackptr) {
1730         flushRuntimeObj(stackptr);
1731         while(gc_moreItems()) {
1732 #ifdef DEBUG
1733                 BAMBOO_DEBUGPRINT(0xe301);
1734 #endif
1735                 void * ptr = gc_dequeue();
1736 #ifdef DEBUG
1737                 BAMBOO_DEBUGPRINT_REG(ptr);
1738 #endif
1739                 void * tptr = flushObj(ptr);
1740 #ifdef DEBUG
1741                 BAMBOO_DEBUGPRINT(0xe302);
1742                 BAMBOO_DEBUGPRINT_REG(ptr);
1743                 BAMBOO_DEBUGPRINT_REG(tptr);
1744 #endif
1745                 if(tptr != NULL) {
1746                         ptr = tptr;
1747                 }
1748                 if(((int *)(ptr))[6] == 2) {
1749                         int type = ((int *)(ptr))[0];
1750                         // scan all pointers in ptr
1751                         unsigned INTPTR * pointer;
1752                         pointer=pointerarray[type];
1753 #ifdef DEBUG
1754                         BAMBOO_DEBUGPRINT(0xe303);
1755                         BAMBOO_DEBUGPRINT_REG(pointer);
1756 #endif
1757                         if (pointer==0) {
1758                                 /* Array of primitives */
1759                                 /* Do nothing */
1760                         } else if (((INTPTR)pointer)==1) {
1761 #ifdef DEBUG
1762                                 BAMBOO_DEBUGPRINT(0xe304);
1763 #endif
1764                                 /* Array of pointers */
1765                                 struct ArrayObject *ao=(struct ArrayObject *) ptr;
1766                                 int length=ao->___length___;
1767                                 int j;
1768                                 for(j=0; j<length; j++) {
1769 #ifdef DEBUG
1770                                         BAMBOO_DEBUGPRINT(0xe305);
1771 #endif
1772                                         void *objptr=
1773                                                 ((void **)(((char *)&ao->___length___)+sizeof(int)))[j];
1774 #ifdef DEBUG
1775                                         BAMBOO_DEBUGPRINT_REG(objptr);
1776 #endif
1777                                         ((void **)(((char *)&ao->___length___)+sizeof(int)))[j] =
1778                                                 flushObj(objptr);
1779                                 }
1780                         } else {
1781 #ifdef DEBUG
1782                                 BAMBOO_DEBUGPRINT(0xe306);
1783 #endif
1784                                 INTPTR size=pointer[0];
1785                                 int i;
1786                                 for(i=1; i<=size; i++) {
1787 #ifdef DEBUG
1788                                         BAMBOO_DEBUGPRINT(0xe307);
1789 #endif
1790                                         unsigned int offset=pointer[i];
1791                                         void * objptr=*((void **)(((char *)ptr)+offset));
1792 #ifdef DEBUG
1793                                         BAMBOO_DEBUGPRINT_REG(objptr);
1794 #endif
1795                                         *((void **)(((char *)ptr)+offset)) = flushObj(objptr);
1796                                 } // for(i=1; i<=size; i++)
1797                         } // if (pointer==0) else if (((INTPTR)pointer)==1) else ()
1798                         // restore the mark field, indicating that this obj has been flushed
1799                         ((int *)(ptr))[6] = 0;
1800                 } // if(((int *)(ptr))[6] == 2)
1801         } // while(moi != NULL)
1802 #ifdef DEBUG
1803         BAMBOO_DEBUGPRINT(0xe308);
1804 #endif
1805         // send flush finish message to core coordinator
1806         if(STARTUPCORE == BAMBOO_NUM_OF_CORE) {
1807                 gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
1808         } else {
1809                 send_msg_2(STARTUPCORE, GCFINISHFLUSH, BAMBOO_NUM_OF_CORE);
1810         }
1811 #ifdef DEBUG
1812         BAMBOO_DEBUGPRINT(0xe309);
1813 #endif
1814 } // flush()
1815
1816 inline void gc_collect(struct garbagelist * stackptr) {
1817         // core collector routine
1818 #ifdef GC_DEBUG
1819         tprintf("Do initGC\n");
1820 #endif
1821         initGC();
1822         //send init finish msg to core coordinator
1823         send_msg_2(STARTUPCORE, GCFINISHINIT, BAMBOO_NUM_OF_CORE);
1824 #ifdef GC_DEBUG
1825         tprintf("Start mark phase\n");
1826 #endif
1827         mark(true, stackptr);
1828 #ifdef GC_DEBUG
1829         tprintf("Finish mark phase, start compact phase\n");
1830 #endif
1831         compact();
1832 #ifdef GC_DEBUG
1833         tprintf("Finish compact phase\n");
1834 #endif
1835         while(FLUSHPHASE != gcphase) {}
1836 #ifdef GC_DEBUG
1837         tprintf("Start flush phase\n");
1838 #endif
1839         flush(stackptr);
1840 #ifdef GC_DEBUG
1841         tprintf("Finish flush phase\n");
1842 #endif
1843
1844         while(FINISHPHASE != gcphase) {}
1845 #ifdef GC_DEBUG
1846         tprintf("Finish gc!\n");
1847 #endif
1848 } // void gc_collect(struct garbagelist * stackptr)
1849
1850 inline void gc(struct garbagelist * stackptr) {
1851         // check if do gc
1852         if(!gcflag) {
1853                 return;
1854         }
1855
1856         // core coordinator routine
1857         if(0 == BAMBOO_NUM_OF_CORE) {
1858 #ifdef GC_DEBUG
1859         tprintf("Check if can do gc or not\n");
1860 #endif
1861                 if(!preGC()) {
1862                         // not ready to do gc
1863                         gcflag = true;
1864                         return;
1865                 }
1866
1867 #ifdef GC_DEBUG
1868                 tprintf("start gc! \n");
1869                 dumpSMem();
1870 #endif
1871
1872                 gcprocessing = true;
1873                 int i = 0;
1874                 waitconfirm = false;
1875                 waitconfirm = 0;
1876                 gcphase = MARKPHASE;
1877                 for(i = 1; i < NUMCORES; i++) {
1878                         // send GC init messages to all cores
1879                         send_msg_1(i, GCSTARTINIT);
1880                 }
1881                 bool isfirst = true;
1882                 bool allStall = false;
1883
1884                 initGC();
1885
1886                 gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
1887                 while(!gc_checkCoreStatus()) {}
1888                 // all cores have finished compacting
1889                 // restore the gcstatus of all cores
1890                 gccorestatus[BAMBOO_NUM_OF_CORE] = 1;
1891                 for(i = 1; i < NUMCORES; ++i) {
1892                         gccorestatus[i] = 1;
1893                         // send GC start messages to all cores
1894                         send_msg_1(i, GCSTART);
1895                 }
1896
1897                 // mark phase
1898                 while(MARKPHASE == gcphase) {
1899                         mark(isfirst, stackptr);
1900                         if(isfirst) {
1901                                 isfirst = false;
1902                         }
1903
1904                         // check gcstatus
1905                         checkMarkStatue();
1906                 }  // while(MARKPHASE == gcphase)
1907                 // send msgs to all cores requiring large objs info
1908                 numconfirm = NUMCORES - 1;
1909                 for(i = 1; i < NUMCORES; ++i) {
1910                         send_msg_1(i, GCLOBJREQUEST);
1911                 }
1912                 gcloads[BAMBOO_NUM_OF_CORE] = gccurr_heaptop;
1913                 while(numconfirm != 0) {} // wait for responses
1914 #ifdef GC_DEBUG
1915                 tprintf("prepare to cache large objs \n");
1916                 dumpSMem();
1917 #endif
1918                 // cache all large objs
1919                 if(!cacheLObjs()) {
1920                         // no enough space to cache large objs
1921                         BAMBOO_EXIT(0xb103);
1922                 }
1923                 // predict number of blocks to fill for each core
1924                 int numpbc = loadbalance();
1925                 for(i = 0; i < NUMCORES; ++i) {
1926                         //send start compact messages to all cores
1927                         if((gcheapdirection) && (i < gctopcore)
1928                                         || ((!gcheapdirection) && (i > gctopcore))) {
1929                                 gcstopblock[i] =numpbc + 1;
1930                                 if(i != STARTUPCORE) {
1931                                         send_msg_2(i, GCSTARTCOMPACT, numpbc+1);
1932                                 } else {
1933                                         gcblock2fill = numpbc+1;
1934                                 } // if(i != STARTUPCORE)
1935                         } else {
1936                                 gcstopblock[i] = numpbc;
1937                                 if(i != STARTUPCORE) {
1938                                         send_msg_2(i, GCSTARTCOMPACT, numpbc);
1939                                 } else {
1940                                         gcblock2fill = numpbc;
1941                                 } // if(i != STARTUPCORE)
1942                         }
1943                         // init some data strutures for compact phase
1944                         gcloads[i] = 0;
1945                         gcfilledblocks[i] = 0;
1946                         gcrequiredmems[i] = 0;
1947                 }
1948 #ifdef GC_DEBUG
1949                 tprintf("mark phase finished \n");
1950                 dumpSMem();
1951 #endif
1952
1953                 // compact phase
1954                 bool finalcompact = false;
1955                 // initialize pointers for comapcting
1956                 struct moveHelper * orig =
1957                         (struct moveHelper *)RUNMALLOC(sizeof(struct moveHelper));
1958                 struct moveHelper * to =
1959                         (struct moveHelper *)RUNMALLOC(sizeof(struct moveHelper));
1960                 initOrig_Dst(orig, to);
1961                 int filledblocks = 0;
1962                 INTPTR heaptopptr = 0;
1963                 bool finishcompact = false;
1964                 bool iscontinue = true;
1965                 bool localcompact = true;
1966                 while((COMPACTPHASE == gcphase) || (SUBTLECOMPACTPHASE == gcphase)) {
1967                         if((!finishcompact) && iscontinue) {
1968 #ifdef DEBUG
1969                                 BAMBOO_DEBUGPRINT(0xe001);
1970                                 BAMBOO_DEBUGPRINT_REG(gcblock2fill);
1971 #endif
1972                                 finishcompact = compacthelper(orig, to, &filledblocks,
1973                                                                           &heaptopptr, &localcompact);
1974 #ifdef DEBUG
1975                                 BAMBOO_DEBUGPRINT_REG(finishcompact);
1976                                 BAMBOO_DEBUGPRINT_REG(gctomove);
1977                                 BAMBOO_DEBUGPRINT_REG(gcrequiredmems[0]);
1978                                 BAMBOO_DEBUGPRINT_REG(gcfilledblocks[0]);
1979                                 BAMBOO_DEBUGPRINT_REG(gcstopblock[0]);
1980                                 dumpSMem();
1981 #endif
1982                         }
1983
1984                         if(gc_checkCoreStatus()) {
1985                                 // all cores have finished compacting
1986                                 // restore the gcstatus of all cores
1987                                 for(i = 0; i < NUMCORES; ++i) {
1988                                         gccorestatus[i] = 1;
1989                                 }
1990                                 break;
1991                         } else {
1992                                 // check if there are spare mem for pending move requires
1993                                 if(COMPACTPHASE == gcphase) {
1994                                         resolvePendingMoveRequest();
1995                                 } else {
1996 #ifdef GC_DEBUG
1997                                         BAMBOO_DEBUGPRINT(0xe002);
1998 #endif
1999                                         compact2Heaptop();
2000                                 }
2001                         } // if(gc_checkCoreStatus()) else ...
2002
2003                         if(gctomove) {
2004 #ifdef GC_DEBUG
2005                                 BAMBOO_DEBUGPRINT(0xe003);
2006                                 BAMBOO_DEBUGPRINT_REG(gcmovestartaddr);
2007                                 BAMBOO_DEBUGPRINT_REG(gcblock2fill);
2008                                 BAMBOO_DEBUGPRINT_REG(gctomove);
2009 #endif
2010                                 to->ptr = gcmovestartaddr;
2011                                 to->numblocks = gcblock2fill - 1;
2012                                 to->bound = (to->numblocks==0)?
2013                                         BAMBOO_SMEM_SIZE_L:
2014                                         BAMBOO_SMEM_SIZE_L+BAMBOO_SMEM_SIZE*to->numblocks;
2015                                 BASEPTR(BAMBOO_NUM_OF_CORE, to->numblocks, &(to->base));
2016                                 to->offset = to->ptr - to->base;
2017                                 to->top = (to->numblocks==0)?
2018                                         (to->offset):(to->bound-BAMBOO_SMEM_SIZE+to->offset);
2019                                 to->base = to->ptr;
2020                                 to->offset = BAMBOO_CACHE_LINE_SIZE;
2021                                 to->ptr += to->offset; // for header
2022                                 to->top += to->offset;
2023                                 if(gcdstcore == BAMBOO_NUM_OF_CORE) {
2024                                         localcompact = true;
2025                                 } else {
2026                                         localcompact = false;
2027                                 }
2028                                 gctomove = false;
2029                                 iscontinue = true;
2030                         } else if(!finishcompact) {
2031                                 // still pending
2032                                 iscontinue = false;
2033                         } // if(gctomove)
2034
2035                 } // while(COMPACTPHASE == gcphase)
2036 #ifdef GC_DEBUG
2037                 tprintf("prepare to move large objs \n");
2038                 dumpSMem();
2039 #endif
2040                 // move largeObjs
2041                 moveLObjs();
2042 #ifdef GC_DEBUG
2043                 tprintf("compact phase finished \n");
2044                 dumpSMem();
2045 #endif
2046
2047                 gcphase = FLUSHPHASE;
2048                 for(i = 1; i < NUMCORES; ++i) {
2049                         // send start flush messages to all cores
2050                         send_msg_1(i, GCSTARTFLUSH);
2051                 }
2052
2053                 // flush phase
2054                 flush(stackptr);
2055                 gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
2056                 while(FLUSHPHASE == gcphase) {
2057                         // check the status of all cores
2058                         allStall = true;
2059                         for(i = 0; i < NUMCORES; ++i) {
2060                                 if(gccorestatus[i] != 0) {
2061                                         allStall = false;
2062                                         break;
2063                                 }
2064                         }
2065                         if(allStall) {
2066                                 break;
2067                         }
2068                 } // while(FLUSHPHASE == gcphase)
2069                 gcphase = FINISHPHASE;
2070                 for(i = 1; i < NUMCORES; ++i) {
2071                         // send gc finish messages to all cores
2072                         send_msg_1(i, GCFINISH);
2073                 }
2074 #ifdef GC_DEBUG
2075                 tprintf("flush phase finished \n");
2076                 dumpSMem();
2077 #endif
2078
2079                 // need to create free memory list
2080                 updateFreeMemList();
2081 #ifdef GC_DEBUG
2082                 tprintf("gc finished \n");
2083                 dumpSMem();
2084 #endif
2085         } else {
2086                 gcprocessing = true;
2087                 gc_collect(stackptr);
2088         }
2089
2090         // invalidate all shared mem pointers
2091         bamboo_cur_msp = NULL;
2092         bamboo_smem_size = 0;
2093
2094         gcflag = false;
2095         gcprocessing = false;
2096
2097 } // void gc(struct garbagelist * stackptr)
2098
2099 #endif