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