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 // TODO for profiling the flush phase
  11 #ifdef GC_PROFILE
  12 int num_mapinforequest;
  13 int num_markrequest;
  14 unsigned long long marktime;
  15 #endif
  16
  17 extern int corenum;
  18 extern struct parameterwrapper ** objectqueues[][NUMCLASSES];
  19 extern int numqueues[][NUMCLASSES];
  20
  21 extern struct genhashtable * activetasks;
  22 extern struct parameterwrapper ** objectqueues[][NUMCLASSES];
  23 extern struct taskparamdescriptor *currtpd;
  24
  25 extern struct LockValue runtime_locks[MAXTASKPARAMS];
  26 extern int runtime_locklen;
  27
  28 struct pointerblock {
  29   void * ptrs[NUMPTRS];
  30   struct pointerblock *next;
  31 };
  32
  33 struct pointerblock *gchead=NULL;
  34 int gcheadindex=0;
  35 struct pointerblock *gctail=NULL;
  36 int gctailindex=0;
  37 struct pointerblock *gctail2=NULL;
  38 int gctailindex2=0;
  39 struct pointerblock *gcspare=NULL;
  40
  41 #define NUMLOBJPTRS 20
  42
  43 struct lobjpointerblock {
  44   void * lobjs[NUMLOBJPTRS];
  45   //void * dsts[NUMLOBJPTRS];
  46   int lengths[NUMLOBJPTRS];
  47   //void * origs[NUMLOBJPTRS];
  48   int hosts[NUMLOBJPTRS];
  49   struct lobjpointerblock *next;
  50   struct lobjpointerblock *prev;
  51 };
  52
  53 struct lobjpointerblock *gclobjhead=NULL;
  54 int gclobjheadindex=0;
  55 struct lobjpointerblock *gclobjtail=NULL;
  56 int gclobjtailindex=0;
  57 struct lobjpointerblock *gclobjtail2=NULL;
  58 int gclobjtailindex2=0;
  59 struct lobjpointerblock *gclobjspare=NULL;
  60
  61 #ifdef GC_DEBUG
  62 // dump whole mem in blocks
  63 inline void dumpSMem() {
  64   int block = 0;
  65   int sblock = 0;
  66   int j = 0;
  67   int i = 0;
  68   int coren = 0;
  69   int x = 0;
  70   int y = 0;
  71   printf("(%x,%x) Dump shared mem: \n", udn_tile_coord_x(),
  72              udn_tile_coord_y());
  73   // reserved blocks for sblocktbl
  74   printf("(%x,%x) ++++ reserved sblocks ++++ \n", udn_tile_coord_x(),
  75              udn_tile_coord_y());
  76   for(i=BAMBOO_BASE_VA; i<gcbaseva; i+= 4*16) {
  77     printf("(%x,%x) 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",
  78                    udn_tile_coord_x(), udn_tile_coord_y(),
  79            *((int *)(i)), *((int *)(i + 4)),
  80            *((int *)(i + 4*2)), *((int *)(i + 4*3)),
  81            *((int *)(i + 4*4)), *((int *)(i + 4*5)),
  82            *((int *)(i + 4*6)), *((int *)(i + 4*7)),
  83            *((int *)(i + 4*8)), *((int *)(i + 4*9)),
  84            *((int *)(i + 4*10)), *((int *)(i + 4*11)),
  85            *((int *)(i + 4*12)), *((int *)(i + 4*13)),
  86            *((int *)(i + 4*14)), *((int *)(i + 4*15)));
  87   }
  88   sblock = gcreservedsb;
  89   bool advanceblock = false;
  90   // remaining memory
  91   for(i=gcbaseva; i<BAMBOO_BASE_VA+BAMBOO_SHARED_MEM_SIZE; i+=4*16) {
  92     advanceblock = false;
  93     // computing sblock # and block #, core coordinate (x,y) also
  94     if(j%((BAMBOO_SMEM_SIZE)/(4*16)) == 0) {
  95       // finished a sblock
  96       if(j < ((BAMBOO_LARGE_SMEM_BOUND)/(4*16))) {
  97         if((j > 0) && (j%((BAMBOO_SMEM_SIZE_L)/(4*16)) == 0)) {
  98           // finished a block
  99           block++;
 100           advanceblock = true;
 101         }
 102       } else {
 103         // finished a block
 104         block++;
 105         advanceblock = true;
 106       }
 107       // compute core #
 108       if(advanceblock) {
 109         coren = gc_block2core[block%(NUMCORES4GC*2)];
 110       }
 111       // compute core coordinate
 112       BAMBOO_COORDS(coren, &x, &y);
 113       printf("(%x,%x) ==== %d, %d : core (%d,%d), saddr %x====\n",
 114                      udn_tile_coord_x(), udn_tile_coord_y(),
 115              block, sblock++, x, y,
 116              (sblock-1)*(BAMBOO_SMEM_SIZE)+BAMBOO_BASE_VA);
 117     }
 118     j++;
 119     printf("(%x,%x) 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",
 120                    udn_tile_coord_x(), udn_tile_coord_y(),
 121            *((int *)(i)), *((int *)(i + 4)),
 122            *((int *)(i + 4*2)), *((int *)(i + 4*3)),
 123            *((int *)(i + 4*4)), *((int *)(i + 4*5)),
 124            *((int *)(i + 4*6)), *((int *)(i + 4*7)),
 125            *((int *)(i + 4*8)), *((int *)(i + 4*9)),
 126            *((int *)(i + 4*10)), *((int *)(i + 4*11)),
 127            *((int *)(i + 4*12)), *((int *)(i + 4*13)),
 128            *((int *)(i + 4*14)), *((int *)(i + 4*15)));
 129   }
 130   printf("(%x,%x) \n", udn_tile_coord_x(), udn_tile_coord_y());
 131 }
 132 #endif
 133
 134 // should be invoked with interruption closed
 135 inline void gc_enqueue_I(void *ptr) {
 136 #ifdef DEBUG
 137   BAMBOO_DEBUGPRINT(0xe601);
 138   BAMBOO_DEBUGPRINT_REG(ptr);
 139 #endif
 140   if (gcheadindex==NUMPTRS) {
 141     struct pointerblock * tmp;
 142     if (gcspare!=NULL) {
 143       tmp=gcspare;
 144       gcspare=NULL;
 145     } else {
 146       tmp=RUNMALLOC_I(sizeof(struct pointerblock));
 147     }             // if (gcspare!=NULL)
 148     gchead->next=tmp;
 149     gchead=tmp;
 150     gcheadindex=0;
 151   } // if (gcheadindex==NUMPTRS)
 152   gchead->ptrs[gcheadindex++]=ptr;
 153 #ifdef DEBUG
 154   BAMBOO_DEBUGPRINT(0xe602);
 155 #endif
 156 } // void gc_enqueue_I(void *ptr)
 157
 158 // dequeue and destroy the queue
 159 inline void * gc_dequeue_I() {
 160   if (gctailindex==NUMPTRS) {
 161     struct pointerblock *tmp=gctail;
 162     gctail=gctail->next;
 163     gctailindex=0;
 164     if (gcspare!=NULL) {
 165       RUNFREE(tmp);
 166     } else {
 167       gcspare=tmp;
 168     }             // if (gcspare!=NULL)
 169   } // if (gctailindex==NUMPTRS)
 170   return gctail->ptrs[gctailindex++];
 171 } // void * gc_dequeue()
 172
 173 // dequeue and do not destroy the queue
 174 inline void * gc_dequeue2_I() {
 175   if (gctailindex2==NUMPTRS) {
 176     struct pointerblock *tmp=gctail2;
 177     gctail2=gctail2->next;
 178     gctailindex2=0;
 179   } // if (gctailindex2==NUMPTRS)
 180   return gctail2->ptrs[gctailindex2++];
 181 } // void * gc_dequeue2()
 182
 183 inline int gc_moreItems_I() {
 184   if ((gchead==gctail)&&(gctailindex==gcheadindex))
 185     return 0;
 186   return 1;
 187 } // int gc_moreItems()
 188
 189 inline int gc_moreItems2_I() {
 190   if ((gchead==gctail2)&&(gctailindex2==gcheadindex))
 191     return 0;
 192   return 1;
 193 } // int gc_moreItems2()
 194
 195 // should be invoked with interruption closed
 196 // enqueue a large obj: start addr & length
 197 inline void gc_lobjenqueue_I(void *ptr,
 198                              int length,
 199                              int host) {
 200 #ifdef DEBUG
 201   BAMBOO_DEBUGPRINT(0xe901);
 202 #endif
 203   if (gclobjheadindex==NUMLOBJPTRS) {
 204     struct lobjpointerblock * tmp;
 205     if (gclobjspare!=NULL) {
 206       tmp=gclobjspare;
 207       gclobjspare=NULL;
 208     } else {
 209       tmp=RUNMALLOC_I(sizeof(struct lobjpointerblock));
 210     }             // if (gclobjspare!=NULL)
 211     gclobjhead->next=tmp;
 212     tmp->prev = gclobjhead;
 213     gclobjhead=tmp;
 214     gclobjheadindex=0;
 215   } // if (gclobjheadindex==NUMLOBJPTRS)
 216   gclobjhead->lobjs[gclobjheadindex]=ptr;
 217   gclobjhead->lengths[gclobjheadindex]=length;
 218   gclobjhead->hosts[gclobjheadindex++]=host;
 219 #ifdef DEBUG
 220   BAMBOO_DEBUGPRINT_REG(gclobjhead->lobjs[gclobjheadindex-1]);
 221   BAMBOO_DEBUGPRINT_REG(gclobjhead->lengths[gclobjheadindex-1]);
 222   BAMBOO_DEBUGPRINT_REG(gclobjhead->hosts[gclobjheadindex-1]);
 223 #endif
 224 } // void gc_lobjenqueue_I(void *ptr...)
 225
 226 // dequeue and destroy the queue
 227 inline void * gc_lobjdequeue_I(int * length,
 228                                int * host) {
 229   if (gclobjtailindex==NUMLOBJPTRS) {
 230     struct lobjpointerblock *tmp=gclobjtail;
 231     gclobjtail=gclobjtail->next;
 232     gclobjtailindex=0;
 233     gclobjtail->prev = NULL;
 234     if (gclobjspare!=NULL) {
 235       RUNFREE(tmp);
 236     } else {
 237       gclobjspare=tmp;
 238       tmp->next = NULL;
 239       tmp->prev = NULL;
 240     }             // if (gclobjspare!=NULL)
 241   } // if (gclobjtailindex==NUMLOBJPTRS)
 242   if(length != NULL) {
 243     *length = gclobjtail->lengths[gclobjtailindex];
 244   }
 245   if(host != NULL) {
 246     *host = (int)(gclobjtail->hosts[gclobjtailindex]);
 247   }
 248   return gclobjtail->lobjs[gclobjtailindex++];
 249 } // void * gc_lobjdequeue()
 250
 251 inline int gc_lobjmoreItems_I() {
 252   if ((gclobjhead==gclobjtail)&&(gclobjtailindex==gclobjheadindex))
 253     return 0;
 254   return 1;
 255 } // int gc_lobjmoreItems()
 256
 257 // dequeue and don't destroy the queue
 258 inline void gc_lobjdequeue2_I() {
 259   if (gclobjtailindex2==NUMLOBJPTRS) {
 260     gclobjtail2=gclobjtail2->next;
 261     gclobjtailindex2=1;
 262   } else {
 263     gclobjtailindex2++;
 264   }      // if (gclobjtailindex2==NUMLOBJPTRS)
 265 } // void * gc_lobjdequeue2()
 266
 267 inline int gc_lobjmoreItems2_I() {
 268   if ((gclobjhead==gclobjtail2)&&(gclobjtailindex2==gclobjheadindex))
 269     return 0;
 270   return 1;
 271 } // int gc_lobjmoreItems2()
 272
 273 // 'reversly' dequeue and don't destroy the queue
 274 inline void gc_lobjdequeue3_I() {
 275   if (gclobjtailindex2==0) {
 276     gclobjtail2=gclobjtail2->prev;
 277     gclobjtailindex2=NUMLOBJPTRS-1;
 278   } else {
 279     gclobjtailindex2--;
 280   }      // if (gclobjtailindex2==NUMLOBJPTRS)
 281 } // void * gc_lobjdequeue3()
 282
 283 inline int gc_lobjmoreItems3_I() {
 284   if ((gclobjtail==gclobjtail2)&&(gclobjtailindex2==gclobjtailindex))
 285     return 0;
 286   return 1;
 287 } // int gc_lobjmoreItems3()
 288
 289 inline void gc_lobjqueueinit4_I() {
 290   gclobjtail2 = gclobjtail;
 291   gclobjtailindex2 = gclobjtailindex;
 292 } // void gc_lobjqueueinit2()
 293
 294 inline void * gc_lobjdequeue4_I(int * length,
 295                                 int * host) {
 296   if (gclobjtailindex2==NUMLOBJPTRS) {
 297     gclobjtail2=gclobjtail2->next;
 298     gclobjtailindex2=0;
 299   } // if (gclobjtailindex==NUMLOBJPTRS)
 300   if(length != NULL) {
 301     *length = gclobjtail2->lengths[gclobjtailindex2];
 302   }
 303   if(host != NULL) {
 304     *host = (int)(gclobjtail2->hosts[gclobjtailindex2]);
 305   }
 306   return gclobjtail2->lobjs[gclobjtailindex2++];
 307 } // void * gc_lobjdequeue()
 308
 309 inline int gc_lobjmoreItems4_I() {
 310   if ((gclobjhead==gclobjtail2)&&(gclobjtailindex2==gclobjheadindex))
 311     return 0;
 312   return 1;
 313 } // int gc_lobjmoreItems(
 314
 315 INTPTR gccurr_heapbound = 0;
 316
 317 inline void gettype_size(void * ptr,
 318                          int * ttype,
 319                          int * tsize) {
 320   int type = ((int *)ptr)[0];
 321   int size = 0;
 322   if(type < NUMCLASSES) {
 323     // a normal object
 324     size = classsize[type];
 325   } else {
 326     // an array
 327     struct ArrayObject *ao=(struct ArrayObject *)ptr;
 328     int elementsize=classsize[type];
 329     int length=ao->___length___;
 330     size=sizeof(struct ArrayObject)+length*elementsize;
 331   }       // if(type < NUMCLASSES)
 332   *ttype = type;
 333   *tsize = size;
 334 }
 335
 336 inline bool isLarge(void * ptr,
 337                     int * ttype,
 338                     int * tsize) {
 339 #ifdef DEBUG
 340   BAMBOO_DEBUGPRINT(0xe701);
 341   BAMBOO_DEBUGPRINT_REG(ptr);
 342 #endif
 343   // check if a pointer is referring to a large object
 344   gettype_size(ptr, ttype, tsize);
 345 #ifdef DEBUG
 346   BAMBOO_DEBUGPRINT(*tsize);
 347 #endif
 348   int bound = (BAMBOO_SMEM_SIZE);
 349   if(((int)ptr-gcbaseva) < (BAMBOO_LARGE_SMEM_BOUND)) {
 350     bound = (BAMBOO_SMEM_SIZE_L);
 351   }
 352   if((((int)ptr-gcbaseva)%(bound))==0) {
 353     // ptr is a start of a block
 354 #ifdef DEBUG
 355     BAMBOO_DEBUGPRINT(0xe702);
 356     BAMBOO_DEBUGPRINT(1);
 357 #endif
 358     return true;
 359   }
 360   if((bound-(((int)ptr-gcbaseva)%bound)) < (*tsize)) {
 361     // it acrosses the boundary of current block
 362 #ifdef DEBUG
 363     BAMBOO_DEBUGPRINT(0xe703);
 364     BAMBOO_DEBUGPRINT(1);
 365 #endif
 366     return true;
 367   }
 368 #ifdef DEBUG
 369   BAMBOO_DEBUGPRINT(0);
 370 #endif
 371   return false;
 372 } // bool isLarge(void * ptr, int * ttype, int * tsize)
 373
 374 inline int hostcore(void * ptr) {
 375   // check the host core of ptr
 376   int host = 0;
 377   RESIDECORE(ptr, &host);
 378 #ifdef DEBUG
 379   BAMBOO_DEBUGPRINT(0xedd0);
 380   BAMBOO_DEBUGPRINT_REG(ptr);
 381   BAMBOO_DEBUGPRINT_REG(host);
 382 #endif
 383   return host;
 384 } // int hostcore(void * ptr)
 385
 386 inline bool isLocal(void * ptr) {
 387   // check if a pointer is in shared heap on this core
 388   return hostcore(ptr) == BAMBOO_NUM_OF_CORE;
 389 } // bool isLocal(void * ptr)
 390
 391 inline bool gc_checkCoreStatus_I() {
 392   bool allStall = true;
 393   for(int i = 0; i < NUMCORES4GC; ++i) {
 394     if(gccorestatus[i] != 0) {
 395       allStall = false;
 396       break;
 397     }             // if(gccorestatus[i] != 0)
 398   }       // for(i = 0; i < NUMCORES4GC; ++i)
 399   return allStall;
 400 }
 401
 402 inline bool gc_checkAllCoreStatus_I() {
 403   bool allStall = true;
 404   for(int i = 0; i < NUMCORESACTIVE; ++i) {
 405     if(gccorestatus[i] != 0) {
 406       allStall = false;
 407       break;
 408     }             // if(gccorestatus[i] != 0)
 409   }       // for(i = 0; i < NUMCORESACTIVE; ++i)
 410   return allStall;
 411 }
 412
 413 inline void checkMarkStatue() {
 414 #ifdef DEBUG
 415   BAMBOO_DEBUGPRINT(0xee01);
 416 #endif
 417   int i;
 418   if((!waitconfirm) ||
 419      (waitconfirm && (numconfirm == 0))) {
 420 #ifdef DEBUG
 421     BAMBOO_DEBUGPRINT(0xee02);
 422 #endif
 423     BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
 424     gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
 425     gcnumsendobjs[BAMBOO_NUM_OF_CORE] = gcself_numsendobjs;
 426     gcnumreceiveobjs[BAMBOO_NUM_OF_CORE] = gcself_numreceiveobjs;
 427     // check the status of all cores
 428     bool allStall = gc_checkAllCoreStatus_I();
 429 #ifdef DEBUG
 430     BAMBOO_DEBUGPRINT(0xee03);
 431 #endif
 432     if(allStall) {
 433 #ifdef DEBUG
 434       BAMBOO_DEBUGPRINT(0xee04);
 435 #endif
 436       // ask for confirm
 437       if(!waitconfirm) {
 438 #ifdef DEBUG
 439         BAMBOO_DEBUGPRINT(0xee05);
 440 #endif
 441         // the first time found all cores stall
 442         // send out status confirm msg to all other cores
 443         // reset the corestatus array too
 444         gccorestatus[BAMBOO_NUM_OF_CORE] = 1;
 445         waitconfirm = true;
 446         numconfirm = NUMCORESACTIVE - 1;
 447         BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
 448         for(i = 1; i < NUMCORESACTIVE; ++i) {
 449           gccorestatus[i] = 1;
 450           // send mark phase finish confirm request msg to core i
 451           send_msg_1(i, GCMARKCONFIRM);
 452         }                         // for(i = 1; i < NUMCORESACTIVE; ++i)
 453       } else {
 454         // check if the sum of send objs and receive obj are the same
 455         // yes->check if the info is the latest; no->go on executing
 456         int sumsendobj = 0;
 457         for(i = 0; i < NUMCORESACTIVE; ++i) {
 458           sumsendobj += gcnumsendobjs[i];
 459         }                         // for(i = 0; i < NUMCORESACTIVE; ++i)
 460 #ifdef DEBUG
 461         BAMBOO_DEBUGPRINT(0xee06);
 462         BAMBOO_DEBUGPRINT_REG(sumsendobj);
 463 #endif
 464         for(i = 0; i < NUMCORESACTIVE; ++i) {
 465           sumsendobj -= gcnumreceiveobjs[i];
 466         }                         // for(i = 0; i < NUMCORESACTIVE; ++i)
 467 #ifdef DEBUG
 468         BAMBOO_DEBUGPRINT(0xee07);
 469         BAMBOO_DEBUGPRINT_REG(sumsendobj);
 470 #endif
 471         if(0 == sumsendobj) {
 472 #ifdef DEBUG
 473           BAMBOO_DEBUGPRINT(0xee08);
 474 #endif
 475           // all the core status info are the latest
 476           // stop mark phase
 477           gcphase = COMPACTPHASE;
 478           // restore the gcstatus for all cores
 479           for(i = 0; i < NUMCORESACTIVE; ++i) {
 480             gccorestatus[i] = 1;
 481           }                               // for(i = 0; i < NUMCORESACTIVE; ++i)
 482         } else {
 483           // wait for a while and ask for confirm again
 484           int h = 100;
 485           while(h--) {
 486           }
 487           waitconfirm = false;
 488         }                        // if(0 == sumsendobj) else ...
 489         BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
 490       }                   // if(!gcwaitconfirm) else()
 491     } else {
 492       BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
 493     }              // if(allStall)
 494   }       // if((!waitconfirm)...
 495 #ifdef DEBUG
 496   BAMBOO_DEBUGPRINT(0xee0a);
 497 #endif
 498 } // void checkMarkStatue()
 499
 500 inline bool preGC() {
 501   // preparation for gc
 502   // make sure to clear all incoming msgs espacially transfer obj msgs
 503 #ifdef DEBUG
 504   BAMBOO_DEBUGPRINT(0xec01);
 505 #endif
 506   int i;
 507   if((!waitconfirm) ||
 508      (waitconfirm && (numconfirm == 0))) {
 509     // send out status confirm msgs to all cores to check if there are
 510     // transfer obj msgs on-the-fly
 511     waitconfirm = true;
 512     numconfirm = NUMCORESACTIVE - 1;
 513     for(i = 1; i < NUMCORESACTIVE; ++i) {
 514       corestatus[i] = 1;
 515       // send status confirm msg to core i
 516       send_msg_1(i, STATUSCONFIRM);
 517     }             // for(i = 1; i < NUMCORESACTIVE; ++i)
 518
 519 #ifdef DEBUG
 520     BAMBOO_DEBUGPRINT(0xec02);
 521 #endif
 522     while(true) {
 523       if(numconfirm == 0) {
 524         break;
 525       }
 526     }             // wait for confirmations
 527     waitconfirm = false;
 528     numconfirm = 0;
 529 #ifdef DEBUG
 530     BAMBOO_DEBUGPRINT(0xec03);
 531 #endif
 532     numsendobjs[BAMBOO_NUM_OF_CORE] = self_numsendobjs;
 533     numreceiveobjs[BAMBOO_NUM_OF_CORE] = self_numreceiveobjs;
 534     int sumsendobj = 0;
 535 #ifdef DEBUG
 536     BAMBOO_DEBUGPRINT(0xec04);
 537 #endif
 538     for(i = 0; i < NUMCORESACTIVE; ++i) {
 539       sumsendobj += numsendobjs[i];
 540 #ifdef DEBUG
 541       BAMBOO_DEBUGPRINT(0xf000 + numsendobjs[i]);
 542 #endif
 543     }             // for(i = 1; i < NUMCORESACTIVE; ++i)
 544 #ifdef DEBUG
 545     BAMBOO_DEBUGPRINT(0xec05);
 546     BAMBOO_DEBUGPRINT_REG(sumsendobj);
 547 #endif
 548     for(i = 0; i < NUMCORESACTIVE; ++i) {
 549       sumsendobj -= numreceiveobjs[i];
 550 #ifdef DEBUG
 551       BAMBOO_DEBUGPRINT(0xf000 + numreceiveobjs[i]);
 552 #endif
 553     }             // for(i = 1; i < NUMCORESACTIVE; ++i)
 554 #ifdef DEBUG
 555     BAMBOO_DEBUGPRINT(0xec06);
 556     BAMBOO_DEBUGPRINT_REG(sumsendobj);
 557 #endif
 558     if(0 == sumsendobj) {
 559       return true;
 560     } else {
 561       // still have some transfer obj msgs on-the-fly, can not start gc
 562       return false;
 563     }             // if(0 == sumsendobj)
 564   } else {
 565 #ifdef DEBUG
 566     BAMBOO_DEBUGPRINT(0xec07);
 567 #endif
 568     // previously asked for status confirmation and do not have all the
 569     // confirmations yet, can not start gc
 570     return false;
 571   }       // if((!waitconfirm) ||
 572 } // bool preGC()
 573
 574 inline void initGC() {
 575   int i;
 576   if(STARTUPCORE == BAMBOO_NUM_OF_CORE) {
 577     for(i = 0; i < NUMCORES4GC; ++i) {
 578       gccorestatus[i] = 1;
 579       gcnumsendobjs[i] = 0;
 580       gcnumreceiveobjs[i] = 0;
 581       gcloads[i] = 0;
 582       gcrequiredmems[i] = 0;
 583       gcfilledblocks[i] = 0;
 584       gcstopblock[i] = 0;
 585     }             // for(i = 0; i < NUMCORES4GC; ++i)
 586     for(i = NUMCORES4GC; i < NUMCORESACTIVE; ++i) {
 587       gccorestatus[i] = 1;
 588       gcnumsendobjs[i] = 0;
 589       gcnumreceiveobjs[i] = 0;
 590     }
 591     gcheaptop = 0;
 592     gctopcore = 0;
 593     gctopblock = 0;
 594   }       // if(STARTUPCORE == BAMBOO_NUM_OF_CORE)
 595   gcself_numsendobjs = 0;
 596   gcself_numreceiveobjs = 0;
 597   gcmarkedptrbound = 0;
 598   gcobj2map = 0;
 599   gcmappedobj = 0;
 600   gcismapped = false;
 601   gcnumlobjs = 0;
 602   gcmovestartaddr = 0;
 603   gctomove = false;
 604   gcblock2fill = 0;
 605   gcmovepending = 0;
 606   gccurr_heaptop = 0;
 607   gcdstcore = 0;
 608
 609   // initialize queue
 610   if (gchead==NULL) {
 611     gcheadindex=gctailindex=gctailindex2 = 0;
 612     gchead=gctail=gctail2=RUNMALLOC(sizeof(struct pointerblock));
 613   } else {
 614     gctailindex = gctailindex2 = gcheadindex;
 615     gctail = gctail2 = gchead;
 616   }
 617
 618   // initialize the large obj queues
 619   if (gclobjhead==NULL) {
 620     gclobjheadindex=0;
 621     gclobjtailindex=0;
 622     gclobjtailindex2 = 0;
 623     gclobjhead=gclobjtail=gclobjtail2=
 624                              RUNMALLOC(sizeof(struct lobjpointerblock));
 625   } else {
 626     gclobjtailindex = gclobjtailindex2 = gclobjheadindex = 0;
 627     gclobjtail = gclobjtail2 = gclobjhead;
 628   }
 629   gclobjhead->next = gclobjhead->prev = NULL;
 630
 631   freeRuntimeHash(gcpointertbl);
 632   gcpointertbl = allocateRuntimeHash(20);
 633   //gcpointertbl = allocateMGCHash(20);
 634   //mgchashreset();
 635
 636   freeMGCHash(gcforwardobjtbl);
 637   gcforwardobjtbl = allocateMGCHash(20, 3);
 638
 639 #ifdef GC_PROFILE
 640   // TODO
 641   num_mapinforequest = 0;
 642   num_mapinforequest_i = 0;
 643   flushstalltime = 0;
 644   flushstalltime_i = 0;
 645   num_markrequest = 0;
 646   marktime = 0;
 647 #endif
 648 } // void initGC()
 649
 650 // compute load balance for all cores
 651 inline int loadbalance(int * heaptop) {
 652   // compute load balance
 653   int i;
 654
 655   // get the total loads
 656   int tloads = gcloads[STARTUPCORE];
 657   for(i = 1; i < NUMCORES4GC; i++) {
 658     tloads += gcloads[i];
 659   }
 660   *heaptop = gcbaseva + tloads;
 661 #ifdef DEBUG
 662   BAMBOO_DEBUGPRINT(0xdddd);
 663   BAMBOO_DEBUGPRINT_REG(tloads);
 664   BAMBOO_DEBUGPRINT_REG(*heaptop);
 665 #endif
 666   int b = 0;
 667   BLOCKINDEX(*heaptop, &b);
 668   int numbpc = b / NUMCORES4GC;       // num of blocks per core
 669 #ifdef DEBUG
 670   BAMBOO_DEBUGPRINT_REG(b);
 671   BAMBOO_DEBUGPRINT_REG(numbpc);
 672 #endif
 673   gctopblock = b;
 674   RESIDECORE(heaptop, &gctopcore);
 675 #ifdef DEBUG
 676   BAMBOO_DEBUGPRINT_REG(gctopcore);
 677 #endif
 678   return numbpc;
 679 } // void loadbalance(int * heaptop)
 680
 681 inline bool cacheLObjs() {
 682   // check the total mem size need for large objs
 683   int sumsize = 0;
 684   int size = 0;
 685 #ifdef DEBUG
 686   BAMBOO_DEBUGPRINT(0xe801);
 687 #endif
 688   gclobjtail2 = gclobjtail;
 689   gclobjtailindex2 = gclobjtailindex;
 690   int tmp_lobj = 0;
 691   int tmp_len = 0;
 692   int tmp_host = 0;
 693   // compute total mem size required and sort the lobjs in ascending order
 694   while(gc_lobjmoreItems2_I()) {
 695     gc_lobjdequeue2_I();
 696     tmp_lobj = gclobjtail2->lobjs[gclobjtailindex2-1];
 697     tmp_host = gclobjtail2->hosts[gclobjtailindex2-1];
 698     tmp_len = gclobjtail2->lengths[gclobjtailindex2 - 1];
 699     sumsize += tmp_len;
 700 #ifdef DEBUG
 701     BAMBOO_DEBUGPRINT_REG(gclobjtail2->lobjs[gclobjtailindex2-1]);
 702     BAMBOO_DEBUGPRINT_REG(tmp_len);
 703     BAMBOO_DEBUGPRINT_REG(sumsize);
 704 #endif
 705     int i = gclobjtailindex2-1;
 706     struct lobjpointerblock * tmp_block = gclobjtail2;
 707     // find the place to insert
 708     while(true) {
 709       if(i == 0) {
 710         if(tmp_block->prev == NULL) {
 711           break;
 712         }
 713         if(tmp_block->prev->lobjs[NUMLOBJPTRS-1] > tmp_lobj) {
 714           tmp_block->lobjs[i] = tmp_block->prev->lobjs[NUMLOBJPTRS-1];
 715           tmp_block->lengths[i] = tmp_block->prev->lengths[NUMLOBJPTRS-1];
 716           tmp_block->hosts[i] = tmp_block->prev->hosts[NUMLOBJPTRS-1];
 717           tmp_block = tmp_block->prev;
 718           i = NUMLOBJPTRS-1;
 719         } else {
 720           break;
 721         }                         // if(tmp_block->prev->lobjs[NUMLOBJPTRS-1] < tmp_lobj)
 722       } else {
 723         if(tmp_block->lobjs[i-1] > tmp_lobj) {
 724           tmp_block->lobjs[i] = tmp_block->lobjs[i-1];
 725           tmp_block->lengths[i] = tmp_block->lengths[i-1];
 726           tmp_block->hosts[i] = tmp_block->hosts[i-1];
 727           i--;
 728         } else {
 729           break;
 730         }                         // if(tmp_block->lobjs[i-1] < tmp_lobj)
 731       }                   // if(i ==0 ) else {}
 732     }             // while(true)
 733                   // insert it
 734     if(i != gclobjtailindex2 - 1) {
 735       tmp_block->lobjs[i] = tmp_lobj;
 736       tmp_block->lengths[i] = tmp_len;
 737       tmp_block->hosts[i] = tmp_host;
 738     }
 739   }       // while(gc_lobjmoreItems2())
 740
 741   // check if there are enough space to cache these large objs
 742   INTPTR dst = (BAMBOO_BASE_VA) + (BAMBOO_SHARED_MEM_SIZE) -sumsize;
 743   if(gcheaptop > dst) {
 744     // do not have enough room to cache large objs
 745 #ifdef DEBUG
 746     BAMBOO_DEBUGPRINT(0xe802);
 747     BAMBOO_DEBUGPRINT_REG(dst);
 748     BAMBOO_DEBUGPRINT_REG(gcheaptop);
 749 #endif
 750     return false;
 751   }
 752 #ifdef DEBUG
 753   BAMBOO_DEBUGPRINT(0xe803);
 754   BAMBOO_DEBUGPRINT_REG(dst);
 755   BAMBOO_DEBUGPRINT_REG(gcheaptop);
 756 #endif
 757
 758   gcheaptop = dst;       // Note: record the start of cached lobjs with gcheaptop
 759   // cache the largeObjs to the top of the shared heap
 760   //gclobjtail2 = gclobjtail;
 761   //gclobjtailindex2 = gclobjtailindex;
 762   dst = (BAMBOO_BASE_VA) + (BAMBOO_SHARED_MEM_SIZE);
 763   while(gc_lobjmoreItems3_I()) {
 764     gc_lobjdequeue3_I();
 765     size = gclobjtail2->lengths[gclobjtailindex2];
 766     // set the mark field to , indicating that this obj has been moved
 767     // and need to be flushed
 768     ((int *)(gclobjtail2->lobjs[gclobjtailindex2]))[6] = COMPACTED;
 769     dst -= size;
 770     if((int)dst < (int)(gclobjtail2->lobjs[gclobjtailindex2])+size) {
 771       memmove(dst, gclobjtail2->lobjs[gclobjtailindex2], size);
 772     } else {
 773       //BAMBOO_WRITE_HINT_CACHE(dst, size);
 774       memcpy(dst, gclobjtail2->lobjs[gclobjtailindex2], size);
 775     }
 776 #ifdef DEBUG
 777     BAMBOO_DEBUGPRINT(0x804);
 778     BAMBOO_DEBUGPRINT_REG(gclobjtail2->lobjs[gclobjtailindex2]);
 779     BAMBOO_DEBUGPRINT(dst);
 780     BAMBOO_DEBUGPRINT_REG(size);
 781     BAMBOO_DEBUGPRINT_REG(*((int*)gclobjtail2->lobjs[gclobjtailindex2]));
 782     BAMBOO_DEBUGPRINT_REG(*((int*)(dst)));
 783 #endif
 784   }
 785   return true;
 786 } // void cacheLObjs()
 787
 788 // NOTE: the free mem chunks should be maintained in an ordered linklist
 789 // the listtop param always specify current list tail
 790
 791 // update the bmmboo_smemtbl to record current shared mem usage
 792 void updateSmemTbl(int coren,
 793                    int localtop) {
 794   int ltopcore = 0;
 795   int bound = BAMBOO_SMEM_SIZE_L;
 796   BLOCKINDEX(localtop, &ltopcore);
 797   if(localtop >= (gcbaseva+(BAMBOO_LARGE_SMEM_BOUND))) {
 798     bound = BAMBOO_SMEM_SIZE;
 799   }
 800   int load = (localtop-gcbaseva)%bound;
 801   int i = 0;
 802   int j = 0;
 803   int toset = 0;
 804   do {
 805     toset = gc_core2block[2*coren+i]+(NUMCORES4GC*2)*j;
 806     if(toset < ltopcore) {
 807       bamboo_smemtbl[toset]=
 808         (toset<NUMCORES4GC) ? BAMBOO_SMEM_SIZE_L : BAMBOO_SMEM_SIZE;
 809     } else if(toset == ltopcore) {
 810       bamboo_smemtbl[toset] = load;
 811       break;
 812     } else {
 813       break;
 814     }
 815     i++;
 816     if(i == 2) {
 817       i = 0;
 818       j++;
 819     }
 820   } while(true);
 821 } // void updateSmemTbl(int, int)
 822
 823 inline void moveLObjs() {
 824 #ifdef DEBUG
 825   BAMBOO_DEBUGPRINT(0xea01);
 826 #endif
 827   // zero out the smemtbl
 828   BAMBOO_MEMSET_WH(bamboo_smemtbl, 0, sizeof(int)*gcnumblock);
 829   // find current heap top
 830   // flush all gcloads to indicate the real heap top on one core
 831   // previous it represents the next available ptr on a core
 832   if((gcloads[0] > (gcbaseva+(BAMBOO_SMEM_SIZE_L)))
 833      && ((gcloads[0]%(BAMBOO_SMEM_SIZE)) == 0)) {
 834     // edge of a block, check if this is exactly the heaptop
 835     BASEPTR(0, gcfilledblocks[0]-1, &(gcloads[0]));
 836     gcloads[0]+=(gcfilledblocks[0]>1 ?
 837                  (BAMBOO_SMEM_SIZE) : (BAMBOO_SMEM_SIZE_L));
 838   }
 839   updateSmemTbl(0, gcloads[0]);
 840 #ifdef DEBUG
 841   BAMBOO_DEBUGPRINT(0xea02);
 842   BAMBOO_DEBUGPRINT_REG(gcloads[0]);
 843   BAMBOO_DEBUGPRINT_REG(bamboo_smemtbl[0]);
 844 #endif
 845   for(int i = 1; i < NUMCORES4GC; i++) {
 846     int tmptop = 0;
 847 #ifdef DEBUG
 848     BAMBOO_DEBUGPRINT(0xf000+i);
 849     BAMBOO_DEBUGPRINT_REG(gcloads[i]);
 850     BAMBOO_DEBUGPRINT_REG(gcfilledblocks[i]);
 851 #endif
 852     if((gcfilledblocks[i] > 0)
 853        && ((gcloads[i] % (BAMBOO_SMEM_SIZE)) == 0)) {
 854       // edge of a block, check if this is exactly the heaptop
 855       BASEPTR(i, gcfilledblocks[i]-1, &gcloads[i]);
 856       gcloads[i]
 857         +=(gcfilledblocks[i]>1 ? (BAMBOO_SMEM_SIZE) : (BAMBOO_SMEM_SIZE_L));
 858       tmptop = gcloads[i];
 859     }
 860     updateSmemTbl(i, gcloads[i]);
 861 #ifdef DEBUG
 862     BAMBOO_DEBUGPRINT_REG(gcloads[i]);
 863 #endif
 864   }       // for(int i = 1; i < NUMCORES4GC; i++) {
 865
 866   // find current heap top
 867   // TODO
 868   // a bug here: when using local allocation, directly move large objects
 869   // to the highest free chunk might not be memory efficient
 870   int tmpheaptop = 0;
 871   int size = 0;
 872   int bound = 0;
 873   int i = 0;
 874   for(i = gcnumblock-1; i >= 0; i--) {
 875     if(bamboo_smemtbl[i] > 0) {
 876       break;
 877     }
 878   }
 879   if(i == -1) {
 880     tmpheaptop = gcbaseva;
 881   } else {
 882     tmpheaptop = gcbaseva+bamboo_smemtbl[i]+((i<NUMCORES4GC) ?
 883                                              (BAMBOO_SMEM_SIZE_L*i) :
 884                                              (BAMBOO_SMEM_SIZE*(i-NUMCORES4GC)+BAMBOO_LARGE_SMEM_BOUND));
 885   }
 886
 887   // move large objs from gcheaptop to tmpheaptop
 888   // write the header first
 889   int tomove = (BAMBOO_BASE_VA) + (BAMBOO_SHARED_MEM_SIZE) -gcheaptop;
 890 #ifdef DEBUG
 891   BAMBOO_DEBUGPRINT(0xea03);
 892   BAMBOO_DEBUGPRINT_REG(tomove);
 893   BAMBOO_DEBUGPRINT_REG(tmpheaptop);
 894   BAMBOO_DEBUGPRINT_REG(gcheaptop);
 895 #endif
 896   // flush the sbstartbl
 897   BAMBOO_MEMSET_WH(&(gcsbstarttbl[gcreservedsb]), '\0',
 898                    (BAMBOO_SHARED_MEM_SIZE/BAMBOO_SMEM_SIZE-gcreservedsb)*sizeof(INTPTR));
 899   if(tomove == 0) {
 900     gcheaptop = tmpheaptop;
 901   } else {
 902     // check how many blocks it acrosses
 903     int remain = tmpheaptop-gcbaseva;
 904     int sb = remain/(BAMBOO_SMEM_SIZE) + gcreservedsb;             //number of the sblock
 905     int b = 0;             // number of the block
 906     BLOCKINDEX(tmpheaptop, &b);
 907     // check the remaining space in this block
 908     bound = (BAMBOO_SMEM_SIZE);
 909     if(remain < (BAMBOO_LARGE_SMEM_BOUND)) {
 910       bound = (BAMBOO_SMEM_SIZE_L);
 911     }
 912     remain = bound - remain%bound;
 913
 914 #ifdef DEBUG
 915     BAMBOO_DEBUGPRINT(0xea04);
 916 #endif
 917     size = 0;
 918     int isize = 0;
 919     int host = 0;
 920     int ptr = 0;
 921     int base = tmpheaptop;
 922     int cpysize = 0;
 923     remain -= BAMBOO_CACHE_LINE_SIZE;
 924     tmpheaptop += BAMBOO_CACHE_LINE_SIZE;
 925     gc_lobjqueueinit4_I();
 926     while(gc_lobjmoreItems4_I()) {
 927       ptr = (int)(gc_lobjdequeue4_I(&size, &host));
 928       ALIGNSIZE(size, &isize);
 929       if(remain < isize) {
 930         // this object acrosses blocks
 931         if(cpysize > 0) {
 932           // close current block, fill its header
 933           BAMBOO_MEMSET_WH(base, '\0', BAMBOO_CACHE_LINE_SIZE);
 934           *((int*)base) = cpysize + BAMBOO_CACHE_LINE_SIZE;
 935           bamboo_smemtbl[b]+=BAMBOO_CACHE_LINE_SIZE;                               // add the size of the header
 936           cpysize = 0;
 937           base = tmpheaptop;
 938           if(remain == 0) {
 939             remain = ((tmpheaptop-gcbaseva)<(BAMBOO_LARGE_SMEM_BOUND)) ?
 940                      BAMBOO_SMEM_SIZE_L : BAMBOO_SMEM_SIZE;
 941           }
 942           remain -= BAMBOO_CACHE_LINE_SIZE;
 943           tmpheaptop += BAMBOO_CACHE_LINE_SIZE;
 944           BLOCKINDEX(tmpheaptop, &b);
 945           sb = (tmpheaptop-gcbaseva)/(BAMBOO_SMEM_SIZE) + gcreservedsb;
 946         }                         // if(cpysize > 0)
 947
 948         // move the large obj
 949         if((int)gcheaptop < (int)(tmpheaptop)+size) {
 950           memmove(tmpheaptop, gcheaptop, size);
 951         } else {
 952           //BAMBOO_WRITE_HINT_CACHE(tmpheaptop, size);
 953           memcpy(tmpheaptop, gcheaptop, size);
 954         }
 955         // fill the remaining space with -2 padding
 956         BAMBOO_MEMSET_WH(tmpheaptop+size, -2, isize-size);
 957         // zero out original mem caching the lobj
 958         BAMBOO_MEMSET_WH(gcheaptop, '\0', size);
 959 #ifdef DEBUG
 960         BAMBOO_DEBUGPRINT(0xea05);
 961         BAMBOO_DEBUGPRINT_REG(gcheaptop);
 962         BAMBOO_DEBUGPRINT_REG(tmpheaptop);
 963         BAMBOO_DEBUGPRINT_REG(size);
 964         BAMBOO_DEBUGPRINT_REG(isize);
 965         BAMBOO_DEBUGPRINT_REG(base);
 966 #endif
 967         gcheaptop += size;
 968         // cache the mapping info anyway
 969         //if(ptr != tmpheaptop) {
 970         BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
 971         //mgchashInsert_I(ptr, tmpheaptop);
 972         RuntimeHashadd_I(gcpointertbl, ptr, tmpheaptop);
 973         //MGCHashadd_I(gcpointertbl, ptr, tmpheaptop);
 974         BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
 975         //}
 976 #ifdef DEBUG
 977         BAMBOO_DEBUGPRINT(0xcdca);
 978         BAMBOO_DEBUGPRINT_REG(ptr);
 979         BAMBOO_DEBUGPRINT_REG(tmpheaptop);
 980 #endif
 981         if(host != BAMBOO_NUM_OF_CORE) {
 982           // send the original host core with the mapping info
 983           send_msg_3(host, GCLOBJMAPPING, ptr, tmpheaptop);
 984 #ifdef DEBUG
 985           BAMBOO_DEBUGPRINT(0xcdcb);
 986           BAMBOO_DEBUGPRINT_REG(ptr);
 987           BAMBOO_DEBUGPRINT_REG(tmpheaptop);
 988 #endif
 989         }                         // if(host != BAMBOO_NUM_OF_CORE)
 990         tmpheaptop += isize;
 991
 992         // set the gcsbstarttbl and bamboo_smemtbl
 993         int tmpsbs = 1+(isize-remain-1)/BAMBOO_SMEM_SIZE;
 994         for(int k = 1; k < tmpsbs; k++) {
 995           gcsbstarttbl[sb+k] = (INTPTR)(-1);
 996         }
 997         sb += tmpsbs;
 998         bound = (b<NUMCORES4GC) ? BAMBOO_SMEM_SIZE_L : BAMBOO_SMEM_SIZE;
 999         BLOCKINDEX(tmpheaptop-1, &tmpsbs);
1000         for(; b < tmpsbs; b++) {
1001           bamboo_smemtbl[b] = bound;
1002           if(b==NUMCORES4GC-1) {
1003             bound = BAMBOO_SMEM_SIZE;
1004           }
1005         }
1006         if(((isize-remain)%(BAMBOO_SMEM_SIZE)) == 0) {
1007           gcsbstarttbl[sb] = (INTPTR)(-1);
1008           remain = ((tmpheaptop-gcbaseva)<(BAMBOO_LARGE_SMEM_BOUND)) ?
1009                    BAMBOO_SMEM_SIZE_L : BAMBOO_SMEM_SIZE;
1010           bamboo_smemtbl[b] = bound;
1011         } else {
1012           gcsbstarttbl[sb] = (INTPTR)(tmpheaptop);
1013           remain = tmpheaptop-gcbaseva;
1014           bamboo_smemtbl[b] = remain%bound;
1015           remain = bound - bamboo_smemtbl[b];
1016         }                         // if(((isize-remain)%(BAMBOO_SMEM_SIZE)) == 0) else ...
1017
1018         // close current block and fill the header
1019         BAMBOO_MEMSET_WH(base, '\0', BAMBOO_CACHE_LINE_SIZE);
1020         *((int*)base) = isize + BAMBOO_CACHE_LINE_SIZE;
1021         cpysize = 0;
1022         base = tmpheaptop;
1023         if(remain == BAMBOO_CACHE_LINE_SIZE) {
1024           // fill with 0 in case
1025           BAMBOO_MEMSET_WH(tmpheaptop, '\0', remain);
1026         }
1027         remain -= BAMBOO_CACHE_LINE_SIZE;
1028         tmpheaptop += BAMBOO_CACHE_LINE_SIZE;
1029       } else {
1030         remain -= isize;
1031         // move the large obj
1032         if((int)gcheaptop < (int)(tmpheaptop)+size) {
1033           memmove(tmpheaptop, gcheaptop, size);
1034         } else {
1035           //BAMBOO_WRITE_HINT_CACHE(tmpheaptop, size);
1036           memcpy(tmpheaptop, gcheaptop, size);
1037         }
1038         // fill the remaining space with -2 padding
1039         BAMBOO_MEMSET_WH(tmpheaptop+size, -2, isize-size);
1040         // zero out original mem caching the lobj
1041         BAMBOO_MEMSET_WH(gcheaptop, '\0', size);
1042 #ifdef DEBUG
1043         BAMBOO_DEBUGPRINT(0xea06);
1044         BAMBOO_DEBUGPRINT_REG(gcheaptop);
1045         BAMBOO_DEBUGPRINT_REG(tmpheaptop);
1046         BAMBOO_DEBUGPRINT_REG(size);
1047         BAMBOO_DEBUGPRINT_REG(isize);
1048 #endif
1049
1050         gcheaptop += size;
1051         cpysize += isize;
1052         // cache the mapping info anyway
1053         //if(ptr != tmpheaptop) {
1054         BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
1055         //mgchashInsert_I(ptr, tmpheaptop);
1056         RuntimeHashadd_I(gcpointertbl, ptr, tmpheaptop);
1057         //MGCHashadd_I(gcpointertbl, ptr, tmpheaptop);
1058         BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
1059         //}
1060 #ifdef DEBUG
1061         BAMBOO_DEBUGPRINT(0xcdcc);
1062         BAMBOO_DEBUGPRINT_REG(ptr);
1063         BAMBOO_DEBUGPRINT_REG(tmpheaptop);
1064         BAMBOO_DEBUGPRINT_REG(*((int*)tmpheaptop));
1065 #endif
1066         if(host != BAMBOO_NUM_OF_CORE) {
1067           // send the original host core with the mapping info
1068           send_msg_3(host, GCLOBJMAPPING, ptr, tmpheaptop);
1069 #ifdef DEBUG
1070           BAMBOO_DEBUGPRINT(0xcdcd);
1071           BAMBOO_DEBUGPRINT_REG(ptr);
1072           BAMBOO_DEBUGPRINT_REG(tmpheaptop);
1073 #endif
1074         }                         // if(host != BAMBOO_NUM_OF_CORE)
1075         tmpheaptop += isize;
1076
1077         // update bamboo_smemtbl
1078         bamboo_smemtbl[b] += isize;
1079       }                   // if(remain < isize) else ...
1080     }             // while(gc_lobjmoreItems())
1081     if(cpysize > 0) {
1082       // close current block, fill the header
1083       BAMBOO_MEMSET_WH(base, '\0', BAMBOO_CACHE_LINE_SIZE);
1084       *((int*)base) = cpysize + BAMBOO_CACHE_LINE_SIZE;
1085       bamboo_smemtbl[b] += BAMBOO_CACHE_LINE_SIZE;                   // add the size of the header
1086     } else {
1087       tmpheaptop -= BAMBOO_CACHE_LINE_SIZE;
1088     }
1089     gcheaptop = tmpheaptop;
1090
1091   }       // if(tomove == 0)
1092
1093 #ifdef DEBUG
1094   BAMBOO_DEBUGPRINT(0xea07);
1095   BAMBOO_DEBUGPRINT_REG(gcheaptop);
1096 #endif
1097
1098   bamboo_free_block = 0;
1099   int tbound = 0;
1100   do {
1101     tbound = (bamboo_free_block<NUMCORES4GC) ?
1102              BAMBOO_SMEM_SIZE_L : BAMBOO_SMEM_SIZE;
1103     if(bamboo_smemtbl[bamboo_free_block] == tbound) {
1104       bamboo_free_block++;
1105     } else {
1106       // the first non-full partition
1107       break;
1108     }
1109   } while(true);
1110 #ifdef DEBUG
1111   BAMBOO_DEBUGPRINT(0xea08);
1112   BAMBOO_DEBUGPRINT_REG(gcheaptop);
1113 #endif
1114 } // void moveLObjs()
1115
1116 inline void markObj(void * objptr) {
1117   if(objptr == NULL) {
1118     return;
1119   }
1120   if(ISSHAREDOBJ(objptr)) {
1121     int host = hostcore(objptr);
1122     if(BAMBOO_NUM_OF_CORE == host) {
1123       // on this core
1124       BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
1125       if(((int *)objptr)[6] == INIT) {
1126         // this is the first time that this object is discovered,
1127         // set the flag as DISCOVERED
1128         ((int *)objptr)[6] = DISCOVERED;
1129         gc_enqueue_I(objptr);
1130       }
1131       BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
1132     } else {
1133 #ifdef DEBUG
1134       BAMBOO_DEBUGPRINT(0xbbbb);
1135       BAMBOO_DEBUGPRINT_REG(host);
1136       BAMBOO_DEBUGPRINT_REG(objptr);
1137 #endif
1138       // check if this obj has been forwarded
1139       if(!MGCHashcontains(gcforwardobjtbl, (int)objptr)) {
1140 #ifdef GC_PROFILE
1141         unsigned long long ttime = BAMBOO_GET_EXE_TIME();
1142 #endif
1143         // send a msg to host informing that objptr is active
1144         send_msg_2(host, GCMARKEDOBJ, objptr);
1145 #ifdef GC_PROFILE
1146         marktime += BAMBOO_GET_EXE_TIME() - ttime;
1147         num_markrequest++;
1148 #endif
1149         gcself_numsendobjs++;
1150         MGCHashadd(gcforwardobjtbl, (int)objptr);
1151       }
1152     }
1153   } else {
1154     BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
1155     gc_enqueue_I(objptr);
1156     BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
1157   }       // if(ISSHAREDOBJ(objptr))
1158 } // void markObj(void * objptr)
1159
1160 // enqueue root objs
1161 inline void tomark(struct garbagelist * stackptr) {
1162   if(MARKPHASE != gcphase) {
1163 #ifdef DEBUG
1164     BAMBOO_DEBUGPRINT_REG(gcphase);
1165 #endif
1166     BAMBOO_EXIT(0xb101);
1167   }
1168   gcbusystatus = true;
1169   gcnumlobjs = 0;
1170
1171   int i,j;
1172   // enqueue current stack
1173   while(stackptr!=NULL) {
1174 #ifdef DEBUG
1175     BAMBOO_DEBUGPRINT(0xe501);
1176     BAMBOO_DEBUGPRINT_REG(stackptr->size);
1177     BAMBOO_DEBUGPRINT_REG(stackptr->next);
1178     BAMBOO_DEBUGPRINT_REG(stackptr->array[0]);
1179 #endif
1180     for(i=0; i<stackptr->size; i++) {
1181       if(stackptr->array[i] != NULL) {
1182         markObj(stackptr->array[i]);
1183       }
1184     }
1185     stackptr=stackptr->next;
1186   }
1187
1188 #ifdef DEBUG
1189   BAMBOO_DEBUGPRINT(0xe503);
1190 #endif
1191   // enqueue objectsets
1192   if(BAMBOO_NUM_OF_CORE < NUMCORESACTIVE) {
1193     for(i=0; i<NUMCLASSES; i++) {
1194       struct parameterwrapper ** queues =
1195         objectqueues[BAMBOO_NUM_OF_CORE][i];
1196       int length = numqueues[BAMBOO_NUM_OF_CORE][i];
1197       for(j = 0; j < length; ++j) {
1198         struct parameterwrapper * parameter = queues[j];
1199         struct ObjectHash * set=parameter->objectset;
1200         struct ObjectNode * ptr=set->listhead;
1201         while(ptr!=NULL) {
1202           markObj((void *)ptr->key);
1203           ptr=ptr->lnext;
1204         }
1205       }
1206     }
1207   }
1208
1209   // euqueue current task descriptor
1210   if(currtpd != NULL) {
1211 #ifdef DEBUG
1212     BAMBOO_DEBUGPRINT(0xe504);
1213 #endif
1214     for(i=0; i<currtpd->numParameters; i++) {
1215       markObj(currtpd->parameterArray[i]);
1216     }
1217   }
1218
1219 #ifdef DEBUG
1220   BAMBOO_DEBUGPRINT(0xe505);
1221 #endif
1222   // euqueue active tasks
1223   if(activetasks != NULL) {
1224     struct genpointerlist * ptr=activetasks->list;
1225     while(ptr!=NULL) {
1226       struct taskparamdescriptor *tpd=ptr->src;
1227       int i;
1228       for(i=0; i<tpd->numParameters; i++) {
1229         markObj(tpd->parameterArray[i]);
1230       }
1231       ptr=ptr->inext;
1232     }
1233   }
1234
1235 #ifdef DEBUG
1236   BAMBOO_DEBUGPRINT(0xe506);
1237 #endif
1238   // enqueue cached transferred obj
1239   struct QueueItem * tmpobjptr =  getHead(&objqueue);
1240   while(tmpobjptr != NULL) {
1241     struct transObjInfo * objInfo =
1242       (struct transObjInfo *)(tmpobjptr->objectptr);
1243     markObj(objInfo->objptr);
1244     tmpobjptr = getNextQueueItem(tmpobjptr);
1245   }
1246
1247 #ifdef DEBUG
1248   BAMBOO_DEBUGPRINT(0xe507);
1249 #endif
1250   // enqueue cached objs to be transferred
1251   struct QueueItem * item = getHead(totransobjqueue);
1252   while(item != NULL) {
1253     struct transObjInfo * totransobj =
1254       (struct transObjInfo *)(item->objectptr);
1255     markObj(totransobj->objptr);
1256     item = getNextQueueItem(item);
1257   }       // while(item != NULL)
1258
1259 #ifdef DEBUG
1260   BAMBOO_DEBUGPRINT(0xe508);
1261 #endif
1262   // enqueue lock related info
1263   for(i = 0; i < runtime_locklen; ++i) {
1264     markObj((void *)(runtime_locks[i].redirectlock));
1265     if(runtime_locks[i].value != NULL) {
1266       markObj((void *)(runtime_locks[i].value));
1267     }
1268   }
1269
1270 } // void tomark(struct garbagelist * stackptr)
1271
1272 inline void mark(bool isfirst,
1273                  struct garbagelist * stackptr) {
1274 #ifdef DEBUG
1275   if(BAMBOO_NUM_OF_CORE == 0) BAMBOO_DEBUGPRINT(0xed01);
1276 #endif
1277   if(isfirst) {
1278 #ifdef DEBUG
1279     if(BAMBOO_NUM_OF_CORE == 0) BAMBOO_DEBUGPRINT(0xed02);
1280 #endif
1281     // enqueue root objs
1282     tomark(stackptr);
1283     gccurr_heaptop = 0;             // record the size of all active objs in this core
1284                                     // aligned but does not consider block boundaries
1285     gcmarkedptrbound = 0;
1286   }
1287 #ifdef DEBUG
1288   if(BAMBOO_NUM_OF_CORE == 0) BAMBOO_DEBUGPRINT(0xed03);
1289 #endif
1290   int isize = 0;
1291   bool checkfield = true;
1292   bool sendStall = false;
1293   // mark phase
1294   while(MARKPHASE == gcphase) {
1295 #ifdef DEBUG
1296     if(BAMBOO_NUM_OF_CORE == 0) BAMBOO_DEBUGPRINT(0xed04);
1297 #endif
1298     while(true) {
1299       BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
1300       bool hasItems = gc_moreItems2_I();
1301       BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
1302 #ifdef DEBUG
1303       BAMBOO_DEBUGPRINT(0xed05);
1304 #endif
1305       if(!hasItems) {
1306         break;
1307       }
1308       sendStall = false;
1309       gcbusystatus = true;
1310       checkfield = true;
1311       void * ptr = gc_dequeue2_I();
1312
1313 #ifdef DEBUG
1314       BAMBOO_DEBUGPRINT_REG(ptr);
1315 #endif
1316       int size = 0;
1317       int isize = 0;
1318       int type = 0;
1319       // check if it is a shared obj
1320       if(ISSHAREDOBJ(ptr)) {
1321         // a shared obj, check if it is a local obj on this core
1322         int host = hostcore(ptr);
1323         bool islocal = (host == BAMBOO_NUM_OF_CORE);
1324         if(islocal) {
1325           bool isnotmarked = (((int *)ptr)[6] == DISCOVERED);
1326           if(isLarge(ptr, &type, &size) && isnotmarked) {
1327             // ptr is a large object and not marked or enqueued
1328 #ifdef DEBUG
1329             BAMBOO_DEBUGPRINT(0xecec);
1330             BAMBOO_DEBUGPRINT_REG(ptr);
1331             BAMBOO_DEBUGPRINT_REG(*((int*)ptr));
1332 #endif
1333             BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
1334             gc_lobjenqueue_I(ptr, size, BAMBOO_NUM_OF_CORE);
1335             gcnumlobjs++;
1336             BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
1337             // mark this obj
1338             ((int *)ptr)[6] = MARKED;
1339           } else if(isnotmarked) {
1340             // ptr is an unmarked active object on this core
1341             ALIGNSIZE(size, &isize);
1342             gccurr_heaptop += isize;
1343 #ifdef DEBUG
1344             BAMBOO_DEBUGPRINT(0xaaaa);
1345             BAMBOO_DEBUGPRINT_REG(ptr);
1346             BAMBOO_DEBUGPRINT_REG(isize);
1347             BAMBOO_DEBUGPRINT(((int *)(ptr))[0]);
1348 #endif
1349             // mark this obj
1350             ((int *)ptr)[6] = MARKED;
1351
1352             if(ptr + size > gcmarkedptrbound) {
1353               gcmarkedptrbound = ptr + size;
1354             }                                     // if(ptr + size > gcmarkedptrbound)
1355           } else {
1356             // ptr is not an active obj or has been marked
1357             checkfield = false;
1358           }                              // if(isLarge(ptr, &type, &size)) else ...
1359         }                         /* can never reach here
1360                                                  else {
1361                                    #ifdef DEBUG
1362                                         if(BAMBOO_NUM_OF_CORE == 0) {
1363                                         BAMBOO_DEBUGPRINT(0xbbbb);
1364                                         BAMBOO_DEBUGPRINT_REG(host);
1365                                         BAMBOO_DEBUGPRINT_REG(ptr);
1366                                         }
1367                                    #endif
1368                                         // check if this obj has been forwarded
1369                                         if(!MGCHashcontains(gcforwardobjtbl, (int)ptr)) {
1370                                                 // send a msg to host informing that ptr is active
1371                                                 send_msg_2(host, GCMARKEDOBJ, ptr);
1372                                                 gcself_numsendobjs++;
1373                                                 MGCHashadd(gcforwardobjtbl, (int)ptr);
1374                                         }
1375                                         checkfield = false;
1376                                      }// if(isLocal(ptr)) else ...*/
1377       }                   // if(ISSHAREDOBJ(ptr))
1378 #ifdef DEBUG
1379       BAMBOO_DEBUGPRINT(0xed06);
1380 #endif
1381
1382       if(checkfield) {
1383         // scan all pointers in ptr
1384         unsigned INTPTR * pointer;
1385         pointer=pointerarray[type];
1386         if (pointer==0) {
1387           /* Array of primitives */
1388           /* Do nothing */
1389         } else if (((INTPTR)pointer)==1) {
1390           /* Array of pointers */
1391           struct ArrayObject *ao=(struct ArrayObject *) ptr;
1392           int length=ao->___length___;
1393           int j;
1394           for(j=0; j<length; j++) {
1395             void *objptr =
1396               ((void **)(((char *)&ao->___length___)+sizeof(int)))[j];
1397             markObj(objptr);
1398           }
1399         } else {
1400           INTPTR size=pointer[0];
1401           int i;
1402           for(i=1; i<=size; i++) {
1403             unsigned int offset=pointer[i];
1404             void * objptr=*((void **)(((char *)ptr)+offset));
1405             markObj(objptr);
1406           }
1407         }                         // if (pointer==0) else if ... else ...
1408       }                   // if(checkfield)
1409     }             // while(gc_moreItems2())
1410 #ifdef DEBUG
1411     BAMBOO_DEBUGPRINT(0xed07);
1412 #endif
1413     gcbusystatus = false;
1414     // send mark finish msg to core coordinator
1415     if(STARTUPCORE == BAMBOO_NUM_OF_CORE) {
1416 #ifdef DEBUG
1417       BAMBOO_DEBUGPRINT(0xed08);
1418 #endif
1419       gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
1420       gcnumsendobjs[BAMBOO_NUM_OF_CORE] = gcself_numsendobjs;
1421       gcnumreceiveobjs[BAMBOO_NUM_OF_CORE] = gcself_numreceiveobjs;
1422       gcloads[BAMBOO_NUM_OF_CORE] = gccurr_heaptop;
1423     } else {
1424       if(!sendStall) {
1425 #ifdef DEBUG
1426         BAMBOO_DEBUGPRINT(0xed09);
1427 #endif
1428         send_msg_4(STARTUPCORE, GCFINISHMARK, BAMBOO_NUM_OF_CORE,
1429                    gcself_numsendobjs, gcself_numreceiveobjs);
1430         sendStall = true;
1431       }
1432     }             // if(STARTUPCORE == BAMBOO_NUM_OF_CORE) ...
1433 #ifdef DEBUG
1434     BAMBOO_DEBUGPRINT(0xed0a);
1435 #endif
1436
1437     if(BAMBOO_NUM_OF_CORE == STARTUPCORE) {
1438 #ifdef DEBUG
1439       BAMBOO_DEBUGPRINT(0xed0b);
1440 #endif
1441       return;
1442     }
1443   }       // while(MARKPHASE == gcphase)
1444 } // mark()
1445
1446 inline void compact2Heaptophelper_I(int coren,
1447                                     int* p,
1448                                     int* numblocks,
1449                                     int* remain) {
1450   int b;
1451   int memneed = gcrequiredmems[coren] + BAMBOO_CACHE_LINE_SIZE;
1452   if(STARTUPCORE == coren) {
1453     gctomove = true;
1454     gcmovestartaddr = *p;
1455     gcdstcore = gctopcore;
1456     gcblock2fill = *numblocks + 1;
1457   } else {
1458     send_msg_4(coren, GCMOVESTART, gctopcore, *p, (*numblocks) + 1);
1459   }
1460 #ifdef DEBUG
1461   BAMBOO_DEBUGPRINT_REG(coren);
1462   BAMBOO_DEBUGPRINT_REG(gctopcore);
1463   BAMBOO_DEBUGPRINT_REG(*p);
1464   BAMBOO_DEBUGPRINT_REG(*numblocks+1);
1465 #endif
1466   if(memneed < *remain) {
1467 #ifdef DEBUG
1468     BAMBOO_DEBUGPRINT(0xd104);
1469 #endif
1470     *p = *p + memneed;
1471     gcrequiredmems[coren] = 0;
1472     gcloads[gctopcore] += memneed;
1473     *remain = *remain - memneed;
1474   } else {
1475 #ifdef DEBUG
1476     BAMBOO_DEBUGPRINT(0xd105);
1477 #endif
1478     // next available block
1479     *p = *p + *remain;
1480     gcfilledblocks[gctopcore] += 1;
1481     int newbase = 0;
1482     BASEPTR(gctopcore, gcfilledblocks[gctopcore], &newbase);
1483     gcloads[gctopcore] = newbase;
1484     gcrequiredmems[coren] -= *remain - BAMBOO_CACHE_LINE_SIZE;
1485     gcstopblock[gctopcore]++;
1486     gctopcore = NEXTTOPCORE(gctopblock);
1487     gctopblock++;
1488     *numblocks = gcstopblock[gctopcore];
1489     *p = gcloads[gctopcore];
1490     BLOCKINDEX(*p, &b);
1491     *remain=(b<NUMCORES4GC) ?
1492              ((BAMBOO_SMEM_SIZE_L)-((*p)%(BAMBOO_SMEM_SIZE_L)))
1493              : ((BAMBOO_SMEM_SIZE)-((*p)%(BAMBOO_SMEM_SIZE)));
1494 #ifdef DEBUG
1495     BAMBOO_DEBUGPRINT(0xd106);
1496     BAMBOO_DEBUGPRINT_REG(gctopcore);
1497     BAMBOO_DEBUGPRINT_REG(*p);
1498     BAMBOO_DEBUGPRINT_REG(b);
1499     BAMBOO_DEBUGPRINT_REG(*remain);
1500 #endif
1501   }       // if(memneed < remain)
1502   gcmovepending--;
1503 } // void compact2Heaptophelper_I(int, int*, int*, int*)
1504
1505 inline void compact2Heaptop() {
1506   // no cores with spare mem and some cores are blocked with pending move
1507   // find the current heap top and make them move to the heap top
1508   int p;
1509   int numblocks = gcfilledblocks[gctopcore];
1510   //BASEPTR(gctopcore, numblocks, &p);
1511   p = gcloads[gctopcore];
1512   int b;
1513   BLOCKINDEX(p, &b);
1514   int remain = (b<NUMCORES4GC) ?
1515                ((BAMBOO_SMEM_SIZE_L)-(p%(BAMBOO_SMEM_SIZE_L)))
1516                : ((BAMBOO_SMEM_SIZE)-(p%(BAMBOO_SMEM_SIZE)));
1517   // check if the top core finishes
1518   BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
1519   if(gccorestatus[gctopcore] != 0) {
1520 #ifdef DEBUG
1521     BAMBOO_DEBUGPRINT(0xd101);
1522     BAMBOO_DEBUGPRINT_REG(gctopcore);
1523 #endif
1524     // let the top core finishes its own work first
1525     compact2Heaptophelper_I(gctopcore, &p, &numblocks, &remain);
1526     BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
1527     return;
1528   }
1529   BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
1530
1531 #ifdef DEBUG
1532   BAMBOO_DEBUGPRINT(0xd102);
1533   BAMBOO_DEBUGPRINT_REG(gctopcore);
1534   BAMBOO_DEBUGPRINT_REG(p);
1535   BAMBOO_DEBUGPRINT_REG(b);
1536   BAMBOO_DEBUGPRINT_REG(remain);
1537 #endif
1538   for(int i = 0; i < NUMCORES4GC; i++) {
1539     BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
1540     if((gccorestatus[i] != 0) && (gcrequiredmems[i] > 0)) {
1541 #ifdef DEBUG
1542       BAMBOO_DEBUGPRINT(0xd103);
1543 #endif
1544       compact2Heaptophelper_I(i, &p, &numblocks, &remain);
1545       if(gccorestatus[gctopcore] != 0) {
1546 #ifdef DEBUG
1547         BAMBOO_DEBUGPRINT(0xd101);
1548         BAMBOO_DEBUGPRINT_REG(gctopcore);
1549 #endif
1550         BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
1551         // the top core is not free now
1552         return;
1553       }
1554     }             // if((gccorestatus[i] != 0) && (gcrequiredmems[i] > 0))
1555     BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
1556   }       // for(i = 0; i < NUMCORES4GC; i++)
1557 #ifdef DEBUG
1558   BAMBOO_DEBUGPRINT(0xd106);
1559 #endif
1560 } // void compact2Heaptop()
1561
1562 inline void resolvePendingMoveRequest() {
1563 #ifdef DEBUG
1564   BAMBOO_DEBUGPRINT(0xeb01);
1565 #endif
1566 #ifdef DEBUG
1567   BAMBOO_DEBUGPRINT(0xeeee);
1568   for(int k = 0; k < NUMCORES4GC; k++) {
1569     BAMBOO_DEBUGPRINT(0xf000+k);
1570     BAMBOO_DEBUGPRINT_REG(gccorestatus[k]);
1571     BAMBOO_DEBUGPRINT_REG(gcloads[k]);
1572     BAMBOO_DEBUGPRINT_REG(gcfilledblocks[k]);
1573     BAMBOO_DEBUGPRINT_REG(gcstopblock[k]);
1574   }
1575   BAMBOO_DEBUGPRINT(0xffff);
1576 #endif
1577   int i;
1578   int j;
1579   bool nosparemem = true;
1580   bool haspending = false;
1581   bool hasrunning = false;
1582   bool noblock = false;
1583   int dstcore = 0;       // the core who need spare mem
1584   int sourcecore = 0;       // the core who has spare mem
1585   for(i = j = 0; (i < NUMCORES4GC) && (j < NUMCORES4GC); ) {
1586     if(nosparemem) {
1587       // check if there are cores with spare mem
1588       if(gccorestatus[i] == 0) {
1589         // finished working, check if it still have spare mem
1590         if(gcfilledblocks[i] < gcstopblock[i]) {
1591           // still have spare mem
1592           nosparemem = false;
1593           sourcecore = i;
1594         }                         // if(gcfilledblocks[i] < gcstopblock[i]) else ...
1595       }
1596       i++;
1597     }             // if(nosparemem)
1598     if(!haspending) {
1599       if(gccorestatus[j] != 0) {
1600         // not finished, check if it has pending move requests
1601         if((gcfilledblocks[j]==gcstopblock[j])&&(gcrequiredmems[j]>0)) {
1602           dstcore = j;
1603           haspending = true;
1604         } else {
1605           hasrunning = true;
1606         }                         // if((gcfilledblocks[i] == gcstopblock[i])...) else ...
1607       }                   // if(gccorestatus[i] == 0) else ...
1608       j++;
1609     }             // if(!haspending)
1610     if(!nosparemem && haspending) {
1611       // find match
1612       int tomove = 0;
1613       int startaddr = 0;
1614       BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
1615       gcrequiredmems[dstcore] = assignSpareMem_I(sourcecore,
1616                                                  gcrequiredmems[dstcore],
1617                                                  &tomove,
1618                                                  &startaddr);
1619       BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
1620 #ifdef DEBUG
1621       BAMBOO_DEBUGPRINT(0xeb02);
1622       BAMBOO_DEBUGPRINT_REG(sourcecore);
1623       BAMBOO_DEBUGPRINT_REG(dstcore);
1624       BAMBOO_DEBUGPRINT_REG(startaddr);
1625       BAMBOO_DEBUGPRINT_REG(tomove);
1626 #endif
1627       if(STARTUPCORE == dstcore) {
1628 #ifdef DEBUG
1629         BAMBOO_DEBUGPRINT(0xeb03);
1630 #endif
1631         gcdstcore = sourcecore;
1632         gctomove = true;
1633         gcmovestartaddr = startaddr;
1634         gcblock2fill = tomove;
1635       } else {
1636 #ifdef DEBUG
1637         BAMBOO_DEBUGPRINT(0xeb04);
1638 #endif
1639         send_msg_4(dstcore, GCMOVESTART, sourcecore,
1640                    startaddr, tomove);
1641       }
1642       gcmovepending--;
1643       nosparemem = true;
1644       haspending = false;
1645       noblock = true;
1646     }
1647   }       // for(i = 0; i < NUMCORES4GC; i++)
1648 #ifdef DEBUG
1649   BAMBOO_DEBUGPRINT(0xcccc);
1650   BAMBOO_DEBUGPRINT_REG(hasrunning);
1651   BAMBOO_DEBUGPRINT_REG(haspending);
1652   BAMBOO_DEBUGPRINT_REG(noblock);
1653 #endif
1654
1655   if(!hasrunning && !noblock) {
1656     gcphase = SUBTLECOMPACTPHASE;
1657     compact2Heaptop();
1658   }
1659
1660 } // void resovePendingMoveRequest()
1661
1662 struct moveHelper {
1663   int numblocks;       // block num for heap
1664   INTPTR base;       // base virtual address of current heap block
1665   INTPTR ptr;       // virtual address of current heap top
1666   int offset;       // offset in current heap block
1667   int blockbase;       // virtual address of current small block to check
1668   int blockbound;       // bound virtual address of current small blcok
1669   int sblockindex;       // index of the small blocks
1670   int top;       // real size of current heap block to check
1671   int bound;       // bound size of current heap block to check
1672 }; // struct moveHelper
1673
1674 // if out of boundary of valid shared memory, return false, else return true
1675 inline bool nextSBlock(struct moveHelper * orig) {
1676   orig->blockbase = orig->blockbound;
1677   bool sbchanged = false;
1678 #ifdef DEBUG
1679   BAMBOO_DEBUGPRINT(0xecc0);
1680   BAMBOO_DEBUGPRINT_REG(orig->blockbase);
1681   BAMBOO_DEBUGPRINT_REG(orig->blockbound);
1682   BAMBOO_DEBUGPRINT_REG(orig->bound);
1683   BAMBOO_DEBUGPRINT_REG(orig->ptr);
1684 #endif
1685 outernextSBlock:
1686   // check if across a big block
1687   if((orig->blockbase >= orig->bound) || (orig->ptr >= orig->bound)
1688      || ((orig->ptr != NULL) && (*((int*)orig->ptr))==0)
1689      || ((*((int*)orig->blockbase))==0)) {
1690 innernextSBlock:
1691     // end of current heap block, jump to next one
1692     orig->numblocks++;
1693 #ifdef DEBUG
1694     BAMBOO_DEBUGPRINT(0xecc1);
1695     BAMBOO_DEBUGPRINT_REG(orig->numblocks);
1696 #endif
1697     BASEPTR(BAMBOO_NUM_OF_CORE, orig->numblocks, &(orig->base));
1698 #ifdef DEBUG
1699     BAMBOO_DEBUGPRINT(orig->base);
1700 #endif
1701     if(orig->base >= BAMBOO_BASE_VA + BAMBOO_SHARED_MEM_SIZE) {
1702       // out of boundary
1703       orig->ptr = orig->base;                   // set current ptr to out of boundary too
1704       return false;
1705     }
1706     orig->bound = orig->base + BAMBOO_SMEM_SIZE;
1707     orig->blockbase = orig->base;
1708     orig->sblockindex = (orig->blockbase-BAMBOO_BASE_VA)/BAMBOO_SMEM_SIZE;
1709     sbchanged = true;
1710     int blocknum = 0;
1711     BLOCKINDEX(orig->base, &blocknum);
1712     if(bamboo_smemtbl[blocknum] == 0) {
1713       // goto next block
1714       goto innernextSBlock;
1715     }
1716   } else if(0 == (orig->blockbase%BAMBOO_SMEM_SIZE)) {
1717     orig->sblockindex += 1;
1718     sbchanged = true;
1719   }       // if((orig->blockbase >= orig->bound) || (orig->ptr >= orig->bound)...
1720
1721   // check if this sblock should be skipped or have special start point
1722   if(gcsbstarttbl[orig->sblockindex] == -1) {
1723     // goto next sblock
1724 #ifdef DEBUG
1725     BAMBOO_DEBUGPRINT(0xecc2);
1726 #endif
1727     orig->sblockindex += 1;
1728     orig->blockbase += BAMBOO_SMEM_SIZE;
1729     goto outernextSBlock;
1730   } else if((gcsbstarttbl[orig->sblockindex] != 0)
1731             && (sbchanged)) {
1732     // the first time to access this SBlock
1733 #ifdef DEBUG
1734     BAMBOO_DEBUGPRINT(0xecc3);
1735 #endif
1736     // not start from the very beginning
1737     orig->blockbase = gcsbstarttbl[orig->sblockindex];
1738   }       // if(gcsbstarttbl[orig->sblockindex] == -1) else ...
1739
1740   // setup information for this sblock
1741   orig->blockbound = orig->blockbase + *((int*)(orig->blockbase));
1742   orig->offset = BAMBOO_CACHE_LINE_SIZE;
1743   orig->ptr = orig->blockbase + orig->offset;
1744 #ifdef DEBUG
1745   BAMBOO_DEBUGPRINT(0xecc4);
1746   BAMBOO_DEBUGPRINT_REG(orig->base);
1747   BAMBOO_DEBUGPRINT_REG(orig->bound);
1748   BAMBOO_DEBUGPRINT_REG(orig->ptr);
1749   BAMBOO_DEBUGPRINT_REG(orig->blockbound);
1750   BAMBOO_DEBUGPRINT_REG(orig->blockbase);
1751   BAMBOO_DEBUGPRINT_REG(orig->offset);
1752 #endif
1753   if(orig->ptr >= orig->bound) {
1754     // met a lobj, move to next block
1755     goto innernextSBlock;
1756   }
1757
1758   return true;
1759 } // bool nextSBlock(struct moveHelper * orig)
1760
1761 // return false if there are no available data to compact
1762 inline bool initOrig_Dst(struct moveHelper * orig,
1763                          struct moveHelper * to) {
1764   // init the dst ptr
1765   to->numblocks = 0;
1766   to->top = to->offset = BAMBOO_CACHE_LINE_SIZE;
1767   to->bound = BAMBOO_SMEM_SIZE_L;
1768   BASEPTR(BAMBOO_NUM_OF_CORE, to->numblocks, &(to->base));
1769
1770 #ifdef DEBUG
1771   BAMBOO_DEBUGPRINT(0xef01);
1772   BAMBOO_DEBUGPRINT_REG(to->base);
1773 #endif
1774   to->ptr = to->base + to->offset;
1775
1776   // init the orig ptr
1777   orig->numblocks = 0;
1778   orig->base = to->base;
1779   orig->bound = to->base + BAMBOO_SMEM_SIZE_L;
1780   orig->blockbase = orig->base;
1781   orig->sblockindex = (orig->base - BAMBOO_BASE_VA) / BAMBOO_SMEM_SIZE;
1782 #ifdef DEBUG
1783   BAMBOO_DEBUGPRINT(0xef02);
1784   BAMBOO_DEBUGPRINT_REG(orig->base);
1785   BAMBOO_DEBUGPRINT_REG(orig->sblockindex);
1786   BAMBOO_DEBUGPRINT_REG(gcsbstarttbl);
1787   BAMBOO_DEBUGPRINT_REG(gcsbstarttbl[orig->sblockindex]);
1788 #endif
1789
1790   if(gcsbstarttbl[orig->sblockindex] == -1) {
1791 #ifdef DEBUG
1792     BAMBOO_DEBUGPRINT(0xef03);
1793 #endif
1794     // goto next sblock
1795     orig->blockbound =
1796       BAMBOO_BASE_VA+BAMBOO_SMEM_SIZE*(orig->sblockindex+1);
1797     return nextSBlock(orig);
1798   } else if(gcsbstarttbl[orig->sblockindex] != 0) {
1799 #ifdef DEBUG
1800     BAMBOO_DEBUGPRINT(0xef04);
1801 #endif
1802     orig->blockbase = gcsbstarttbl[orig->sblockindex];
1803   }
1804 #ifdef DEBUG
1805   BAMBOO_DEBUGPRINT(0xef05);
1806 #endif
1807   orig->blockbound = orig->blockbase + *((int*)(orig->blockbase));
1808   orig->offset = BAMBOO_CACHE_LINE_SIZE;
1809   orig->ptr = orig->blockbase + orig->offset;
1810 #ifdef DEBUG
1811   BAMBOO_DEBUGPRINT(0xef06);
1812   BAMBOO_DEBUGPRINT_REG(orig->base);
1813 #endif
1814   return true;
1815 } // bool initOrig_Dst(struct moveHelper * orig, struct moveHelper * to)
1816
1817 inline void nextBlock(struct moveHelper * to) {
1818   to->top = to->bound + BAMBOO_CACHE_LINE_SIZE;       // header!
1819   to->bound += BAMBOO_SMEM_SIZE;
1820   to->numblocks++;
1821   BASEPTR(BAMBOO_NUM_OF_CORE, to->numblocks, &(to->base));
1822   to->offset = BAMBOO_CACHE_LINE_SIZE;
1823   to->ptr = to->base + to->offset;
1824 } // void nextBlock(struct moveHelper * to)
1825
1826 // endaddr does not contain spaces for headers
1827 inline bool moveobj(struct moveHelper * orig,
1828                     struct moveHelper * to,
1829                     int stopblock) {
1830   if(stopblock == 0) {
1831     return true;
1832   }
1833
1834 #ifdef DEBUG
1835   BAMBOO_DEBUGPRINT(0xe201);
1836   BAMBOO_DEBUGPRINT_REG(orig->ptr);
1837   BAMBOO_DEBUGPRINT_REG(to->ptr);
1838 #endif
1839
1840   int type = 0;
1841   int size = 0;
1842   int mark = 0;
1843   int isize = 0;
1844 innermoveobj:
1845   while((char)(*((int*)(orig->ptr))) == (char)(-2)) {
1846     orig->ptr = (int*)(orig->ptr) + 1;
1847   }
1848   if((orig->ptr > orig->bound) || (orig->ptr == orig->blockbound)) {
1849     if(!nextSBlock(orig)) {
1850       // finished, no more data
1851       return true;
1852     }
1853     goto innermoveobj;
1854   }
1855 #ifdef DEBUG
1856   BAMBOO_DEBUGPRINT(0xe202);
1857   BAMBOO_DEBUGPRINT_REG(orig->ptr);
1858   BAMBOO_DEBUGPRINT(((int *)(orig->ptr))[0]);
1859 #endif
1860   // check the obj's type, size and mark flag
1861   type = ((int *)(orig->ptr))[0];
1862   size = 0;
1863   if(type == 0) {
1864     // end of this block, go to next one
1865     if(!nextSBlock(orig)) {
1866       // finished, no more data
1867       return true;
1868     }
1869     goto innermoveobj;
1870   } else if(type < NUMCLASSES) {
1871     // a normal object
1872     size = classsize[type];
1873   } else {
1874     // an array
1875     struct ArrayObject *ao=(struct ArrayObject *)(orig->ptr);
1876     int elementsize=classsize[type];
1877     int length=ao->___length___;
1878     size=sizeof(struct ArrayObject)+length*elementsize;
1879   }
1880   mark = ((int *)(orig->ptr))[6];
1881 #ifdef DEBUG
1882   BAMBOO_DEBUGPRINT(0xe203);
1883   BAMBOO_DEBUGPRINT_REG(orig->ptr);
1884   BAMBOO_DEBUGPRINT_REG(size);
1885 #endif
1886   ALIGNSIZE(size, &isize);       // no matter is the obj marked or not
1887                                  // should be able to across it
1888   if(mark == MARKED) {
1889 #ifdef DEBUG
1890     BAMBOO_DEBUGPRINT(0xe204);
1891 #endif
1892     // marked obj, copy it to current heap top
1893     // check to see if remaining space is enough
1894     if(to->top + isize > to->bound) {
1895       // fill 0 indicating the end of this block
1896       BAMBOO_MEMSET_WH(to->ptr,  '\0', to->bound - to->top);
1897       // fill the header of this block and then go to next block
1898       to->offset += to->bound - to->top;
1899       BAMBOO_MEMSET_WH(to->base, '\0', BAMBOO_CACHE_LINE_SIZE);
1900       (*((int*)(to->base))) = to->offset;
1901       nextBlock(to);
1902       if(stopblock == to->numblocks) {
1903         // already fulfilled the block
1904         return true;
1905       }                   // if(stopblock == to->numblocks)
1906     }             // if(to->top + isize > to->bound)
1907                   // set the mark field to 2, indicating that this obj has been moved
1908                   // and need to be flushed
1909     ((int *)(orig->ptr))[6] = COMPACTED;
1910     if(to->ptr != orig->ptr) {
1911       if((int)(orig->ptr) < (int)(to->ptr)+size) {
1912         memmove(to->ptr, orig->ptr, size);
1913       } else {
1914         //BAMBOO_WRITE_HINT_CACHE(to->ptr, size);
1915         memcpy(to->ptr, orig->ptr, size);
1916       }
1917       // fill the remaining space with -2
1918       BAMBOO_MEMSET_WH(to->ptr+size, -2, isize-size);
1919     }
1920     // store mapping info
1921     BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
1922     //mgchashInsert_I(orig->ptr, to->ptr);
1923     RuntimeHashadd_I(gcpointertbl, orig->ptr, to->ptr);
1924     //MGCHashadd_I(gcpointertbl, orig->ptr, to->ptr);
1925     BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
1926     //}
1927 #ifdef DEBUG
1928     BAMBOO_DEBUGPRINT(0xcdce);
1929     BAMBOO_DEBUGPRINT_REG(orig->ptr);
1930     BAMBOO_DEBUGPRINT_REG(to->ptr);
1931 #endif
1932     gccurr_heaptop -= isize;
1933     to->ptr += isize;
1934     to->offset += isize;
1935     to->top += isize;
1936     if(to->top == to->bound) {
1937       // fill the header of this block and then go to next block
1938       BAMBOO_MEMSET_WH(to->base, '\0', BAMBOO_CACHE_LINE_SIZE);
1939       (*((int*)(to->base))) = to->offset;
1940       nextBlock(to);
1941     }
1942   }       // if(mark == 1)
1943 #ifdef DEBUG
1944   BAMBOO_DEBUGPRINT(0xe205);
1945 #endif
1946   // move to next obj
1947   orig->ptr += size;
1948
1949 #ifdef DEBUG
1950   BAMBOO_DEBUGPRINT_REG(isize);
1951   BAMBOO_DEBUGPRINT_REG(size);
1952   BAMBOO_DEBUGPRINT_REG(orig->ptr);
1953   BAMBOO_DEBUGPRINT_REG(orig->bound);
1954 #endif
1955   if((orig->ptr > orig->bound) || (orig->ptr == orig->blockbound)) {
1956 #ifdef DEBUG
1957     BAMBOO_DEBUGPRINT(0xe206);
1958 #endif
1959     if(!nextSBlock(orig)) {
1960       // finished, no more data
1961       return true;
1962     }
1963   }
1964 #ifdef DEBUG
1965   BAMBOO_DEBUGPRINT(0xe207);
1966   BAMBOO_DEBUGPRINT_REG(orig->ptr);
1967 #endif
1968   return false;
1969 } //bool moveobj(struct moveHelper* orig,struct moveHelper* to,int* endaddr)
1970
1971 // should be invoked with interrupt closed
1972 inline int assignSpareMem_I(int sourcecore,
1973                             int * requiredmem,
1974                             int * tomove,
1975                             int * startaddr) {
1976   int b = 0;
1977   BLOCKINDEX(gcloads[sourcecore], &b);
1978   int boundptr = (b<NUMCORES4GC) ? ((b+1)*BAMBOO_SMEM_SIZE_L)
1979                  : (BAMBOO_LARGE_SMEM_BOUND+(b-NUMCORES4GC+1)*BAMBOO_SMEM_SIZE);
1980   int remain = boundptr - gcloads[sourcecore];
1981   int memneed = requiredmem + BAMBOO_CACHE_LINE_SIZE;
1982   *startaddr = gcloads[sourcecore];
1983   *tomove = gcfilledblocks[sourcecore] + 1;
1984   if(memneed < remain) {
1985     gcloads[sourcecore] += memneed;
1986     return 0;
1987   } else {
1988     // next available block
1989     gcfilledblocks[sourcecore] += 1;
1990     int newbase = 0;
1991     BASEPTR(sourcecore, gcfilledblocks[sourcecore], &newbase);
1992     gcloads[sourcecore] = newbase;
1993     return requiredmem-remain;
1994   }
1995 } // int assignSpareMem_I(int ,int * , int * , int * )
1996
1997 // should be invoked with interrupt closed
1998 inline bool gcfindSpareMem_I(int * startaddr,
1999                              int * tomove,
2000                              int * dstcore,
2001                              int requiredmem,
2002                              int requiredcore) {
2003   for(int k = 0; k < NUMCORES4GC; k++) {
2004     if((gccorestatus[k] == 0) && (gcfilledblocks[k] < gcstopblock[k])) {
2005       // check if this stopped core has enough mem
2006       assignSpareMem_I(k, requiredmem, tomove, startaddr);
2007       *dstcore = k;
2008       return true;
2009     }
2010   }
2011   // if can not find spare mem right now, hold the request
2012   gcrequiredmems[requiredcore] = requiredmem;
2013   gcmovepending++;
2014   return false;
2015 } //bool gcfindSpareMem_I(int* startaddr,int* tomove,int mem,int core)
2016
2017 inline bool compacthelper(struct moveHelper * orig,
2018                           struct moveHelper * to,
2019                           int * filledblocks,
2020                           int * heaptopptr,
2021                           bool * localcompact) {
2022   // scan over all objs in this block, compact the marked objs
2023   // loop stop when finishing either scanning all active objs or
2024   // fulfilled the gcstopblock
2025 #ifdef DEBUG
2026   BAMBOO_DEBUGPRINT(0xe101);
2027   BAMBOO_DEBUGPRINT_REG(gcblock2fill);
2028   BAMBOO_DEBUGPRINT_REG(gcmarkedptrbound);
2029 #endif
2030 innercompact:
2031   while(orig->ptr < gcmarkedptrbound) {
2032     bool stop = moveobj(orig, to, gcblock2fill);
2033     if(stop) {
2034       break;
2035     }
2036   }
2037   // if no objs have been compact, do nothing,
2038   // otherwise, fill the header of this block
2039   if(to->offset > BAMBOO_CACHE_LINE_SIZE) {
2040     BAMBOO_MEMSET_WH(to->base, '\0', BAMBOO_CACHE_LINE_SIZE);
2041     (*((int*)(to->base))) = to->offset;
2042   } else {
2043     to->offset = 0;
2044     to->ptr = to->base;
2045     to->top -= BAMBOO_CACHE_LINE_SIZE;
2046   }       // if(to->offset > BAMBOO_CACHE_LINE_SIZE) else ...
2047   if(*localcompact) {
2048     *heaptopptr = to->ptr;
2049     *filledblocks = to->numblocks;
2050   }
2051 #ifdef DEBUG
2052   BAMBOO_DEBUGPRINT(0xe102);
2053   BAMBOO_DEBUGPRINT_REG(orig->ptr);
2054   BAMBOO_DEBUGPRINT_REG(gcmarkedptrbound);
2055   BAMBOO_DEBUGPRINT_REG(*heaptopptr);
2056   BAMBOO_DEBUGPRINT_REG(*filledblocks);
2057   BAMBOO_DEBUGPRINT_REG(gccurr_heaptop);
2058 #endif
2059
2060   // send msgs to core coordinator indicating that the compact is finishing
2061   // send compact finish message to core coordinator
2062   if(STARTUPCORE == BAMBOO_NUM_OF_CORE) {
2063     gcfilledblocks[BAMBOO_NUM_OF_CORE] = *filledblocks;
2064     gcloads[BAMBOO_NUM_OF_CORE] = *heaptopptr;
2065     if(orig->ptr < gcmarkedptrbound) {
2066 #ifdef DEBUG
2067       BAMBOO_DEBUGPRINT(0xe103);
2068 #endif
2069       // ask for more mem
2070       gctomove = false;
2071       BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
2072       if(gcfindSpareMem_I(&gcmovestartaddr, &gcblock2fill, &gcdstcore,
2073                           gccurr_heaptop, BAMBOO_NUM_OF_CORE)) {
2074 #ifdef DEBUG
2075         BAMBOO_DEBUGPRINT(0xe104);
2076 #endif
2077         gctomove = true;
2078       } else {
2079         BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
2080 #ifdef DEBUG
2081         BAMBOO_DEBUGPRINT(0xe105);
2082 #endif
2083         return false;
2084       }
2085       BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
2086     } else {
2087 #ifdef DEBUG
2088       BAMBOO_DEBUGPRINT(0xe106);
2089 #endif
2090       gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
2091       gctomove = false;
2092       return true;
2093     }
2094   } else {
2095     if(orig->ptr < gcmarkedptrbound) {
2096 #ifdef DEBUG
2097       BAMBOO_DEBUGPRINT(0xe107);
2098 #endif
2099       // ask for more mem
2100       gctomove = false;
2101       send_msg_5(STARTUPCORE, GCFINISHCOMPACT, BAMBOO_NUM_OF_CORE,
2102                  *filledblocks, *heaptopptr, gccurr_heaptop);
2103     } else {
2104 #ifdef DEBUG
2105       BAMBOO_DEBUGPRINT(0xe108);
2106       BAMBOO_DEBUGPRINT_REG(*heaptopptr);
2107 #endif
2108       // finish compacting
2109       send_msg_5(STARTUPCORE, GCFINISHCOMPACT, BAMBOO_NUM_OF_CORE,
2110                  *filledblocks, *heaptopptr, 0);
2111     }
2112   }       // if(STARTUPCORE == BAMBOO_NUM_OF_CORE)
2113
2114   if(orig->ptr < gcmarkedptrbound) {
2115 #ifdef DEBUG
2116     BAMBOO_DEBUGPRINT(0xe109);
2117 #endif
2118     // still have unpacked obj
2119     while(true) {
2120       if(gctomove) {
2121         break;
2122       }
2123     }
2124     ;
2125     gctomove = false;
2126 #ifdef DEBUG
2127     BAMBOO_DEBUGPRINT(0xe10a);
2128 #endif
2129
2130     to->ptr = gcmovestartaddr;
2131     to->numblocks = gcblock2fill - 1;
2132     to->bound = (to->numblocks==0) ?
2133                 BAMBOO_SMEM_SIZE_L :
2134                 BAMBOO_SMEM_SIZE_L+BAMBOO_SMEM_SIZE*to->numblocks;
2135     BASEPTR(gcdstcore, to->numblocks, &(to->base));
2136     to->offset = to->ptr - to->base;
2137     to->top = (to->numblocks==0) ?
2138               (to->offset) : (to->bound-BAMBOO_SMEM_SIZE+to->offset);
2139     to->base = to->ptr;
2140     to->offset = BAMBOO_CACHE_LINE_SIZE;
2141     to->ptr += to->offset;             // for header
2142     to->top += to->offset;
2143     if(gcdstcore == BAMBOO_NUM_OF_CORE) {
2144       *localcompact = true;
2145     } else {
2146       *localcompact = false;
2147     }
2148     goto innercompact;
2149   }
2150 #ifdef DEBUG
2151   BAMBOO_DEBUGPRINT(0xe10b);
2152 #endif
2153   return true;
2154 } // void compacthelper()
2155
2156 inline void compact() {
2157   if(COMPACTPHASE != gcphase) {
2158     BAMBOO_EXIT(0xb102);
2159   }
2160
2161   // initialize pointers for comapcting
2162   struct moveHelper * orig =
2163     (struct moveHelper *)RUNMALLOC(sizeof(struct moveHelper));
2164   struct moveHelper * to =
2165     (struct moveHelper *)RUNMALLOC(sizeof(struct moveHelper));
2166
2167   if(!initOrig_Dst(orig, to)) {
2168     // no available data to compact
2169     // send compact finish msg to STARTUP core
2170 #ifdef DEBUG
2171     BAMBOO_DEBUGPRINT(0xe001);
2172     BAMBOO_DEBUGPRINT_REG(to->base);
2173 #endif
2174     send_msg_5(STARTUPCORE, GCFINISHCOMPACT, BAMBOO_NUM_OF_CORE,
2175                0, to->base, 0);
2176     RUNFREE(orig);
2177     RUNFREE(to);
2178     return;
2179   }
2180
2181   int filledblocks = 0;
2182   INTPTR heaptopptr = 0;
2183   bool localcompact = true;
2184   compacthelper(orig, to, &filledblocks, &heaptopptr, &localcompact);
2185
2186   RUNFREE(orig);
2187   RUNFREE(to);
2188 } // compact()
2189
2190 // if return NULL, means
2191 //   1. objptr is NULL
2192 //   2. objptr is not a shared obj
2193 // in these cases, remain the original value is OK
2194 inline void * flushObj(void * objptr) {
2195 #ifdef DEBUG
2196   BAMBOO_DEBUGPRINT(0xe401);
2197 #endif
2198   if(objptr == NULL) {
2199     return NULL;
2200   }
2201   void * dstptr = NULL;
2202   if(ISSHAREDOBJ(objptr)) {
2203 #ifdef DEBUG
2204     BAMBOO_DEBUGPRINT(0xe402);
2205     BAMBOO_DEBUGPRINT_REG(objptr);
2206 #endif
2207     // a shared obj ptr, change to new address
2208     BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
2209 #ifdef GC_PROFILE
2210     unsigned long long ttime = BAMBOO_GET_EXE_TIME();
2211 #endif
2212     //dstptr = mgchashSearch(objptr);
2213     RuntimeHashget(gcpointertbl, objptr, &dstptr);
2214 #ifdef GC_PROFILE
2215     flushstalltime += BAMBOO_GET_EXE_TIME()-ttime;
2216 #endif
2217     //MGCHashget(gcpointertbl, objptr, &dstptr);
2218     BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
2219 #ifdef DEBUG
2220     BAMBOO_DEBUGPRINT_REG(dstptr);
2221 #endif
2222     if(NULL == dstptr) {
2223       // no mapping info
2224 #ifdef DEBUG
2225       BAMBOO_DEBUGPRINT(0xe403);
2226       BAMBOO_DEBUGPRINT_REG(objptr);
2227       BAMBOO_DEBUGPRINT_REG(hostcore(objptr));
2228 #endif
2229       if(hostcore(objptr) == BAMBOO_NUM_OF_CORE) {
2230         // error! the obj is right on this core, but cannot find it
2231         BAMBOO_DEBUGPRINT_REG(objptr);
2232         BAMBOO_EXIT(0xb103);
2233         // assume that the obj has not been moved, use the original address
2234         //dstptr = objptr;
2235       } else {
2236         // send msg to host core for the mapping info
2237         gcobj2map = (int)objptr;
2238         gcismapped = false;
2239         gcmappedobj = NULL;
2240 #ifdef GC_PROFILE
2241         // TODO
2242         num_mapinforequest++;
2243         //unsigned long long ttime = BAMBOO_GET_EXE_TIME();
2244 #endif
2245 #ifdef GC_PROFILE
2246         unsigned long long ttimet = BAMBOO_GET_EXE_TIME();
2247 #endif
2248         // the first time require the mapping, send msg to the hostcore
2249         // for the mapping info
2250         send_msg_3(hostcore(objptr), GCMAPREQUEST, (int)objptr,
2251                    BAMBOO_NUM_OF_CORE);
2252         while(true) {
2253           if(gcismapped) {
2254             break;
2255           }
2256         }
2257 #ifdef GC_PROFILE
2258         flushstalltime_i += BAMBOO_GET_EXE_TIME()-ttimet;
2259 #endif
2260 #ifdef GC_PROFILE
2261         // TODO
2262         //flushstalltime += BAMBOO_GET_EXE_TIME() - ttime;
2263 #endif
2264         BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
2265         //dstptr = mgchashSearch(objptr);
2266         RuntimeHashget(gcpointertbl, objptr, &dstptr);
2267         //MGCHashget(gcpointertbl, objptr, &dstptr);
2268         BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
2269       }                   // if(hostcore(objptr) == BAMBOO_NUM_OF_CORE) else ...
2270 #ifdef DEBUG
2271       BAMBOO_DEBUGPRINT_REG(dstptr);
2272 #endif
2273     }             // if(NULL == dstptr)
2274   }      // if(ISSHAREDOBJ(objptr))
2275          // if not a shared obj, return NULL to indicate no need to flush
2276 #ifdef DEBUG
2277   BAMBOO_DEBUGPRINT(0xe404);
2278 #endif
2279   return dstptr;
2280 } // void flushObj(void * objptr)
2281
2282 inline void flushRuntimeObj(struct garbagelist * stackptr) {
2283   int i,j;
2284   // flush current stack
2285   while(stackptr!=NULL) {
2286     for(i=0; i<stackptr->size; i++) {
2287       if(stackptr->array[i] != NULL) {
2288         void * dst = flushObj(stackptr->array[i]);
2289         if(dst != NULL) {
2290           stackptr->array[i] = dst;
2291         }
2292       }
2293     }
2294     stackptr=stackptr->next;
2295   }
2296
2297   // flush objectsets
2298   if(BAMBOO_NUM_OF_CORE < NUMCORESACTIVE) {
2299     for(i=0; i<NUMCLASSES; i++) {
2300       struct parameterwrapper ** queues =
2301         objectqueues[BAMBOO_NUM_OF_CORE][i];
2302       int length = numqueues[BAMBOO_NUM_OF_CORE][i];
2303       for(j = 0; j < length; ++j) {
2304         struct parameterwrapper * parameter = queues[j];
2305         struct ObjectHash * set=parameter->objectset;
2306         struct ObjectNode * ptr=set->listhead;
2307         while(ptr!=NULL) {
2308           void * dst = flushObj((void *)ptr->key);
2309           if(dst != NULL) {
2310             ptr->key = dst;
2311           }
2312           ptr=ptr->lnext;
2313         }
2314         ObjectHashrehash(set);
2315       }
2316     }
2317   }
2318
2319   // flush current task descriptor
2320   if(currtpd != NULL) {
2321     for(i=0; i<currtpd->numParameters; i++) {
2322       void * dst = flushObj(currtpd->parameterArray[i]);
2323       if(dst != NULL) {
2324         currtpd->parameterArray[i] = dst;
2325       }
2326     }
2327   }
2328
2329   // flush active tasks
2330   if(activetasks != NULL) {
2331     struct genpointerlist * ptr=activetasks->list;
2332     while(ptr!=NULL) {
2333       struct taskparamdescriptor *tpd=ptr->src;
2334       int i;
2335       for(i=0; i<tpd->numParameters; i++) {
2336         void * dst = flushObj(tpd->parameterArray[i]);
2337         if(dst != NULL) {
2338           tpd->parameterArray[i] = dst;
2339         }
2340       }
2341       ptr=ptr->inext;
2342     }
2343     genrehash(activetasks);
2344   }
2345
2346   // flush cached transferred obj
2347   struct QueueItem * tmpobjptr =  getHead(&objqueue);
2348   while(tmpobjptr != NULL) {
2349     struct transObjInfo * objInfo =
2350       (struct transObjInfo *)(tmpobjptr->objectptr);
2351     void * dst = flushObj(objInfo->objptr);
2352     if(dst != NULL) {
2353       objInfo->objptr = dst;
2354     }
2355     tmpobjptr = getNextQueueItem(tmpobjptr);
2356   }
2357
2358   // flush cached objs to be transferred
2359   struct QueueItem * item = getHead(totransobjqueue);
2360   while(item != NULL) {
2361     struct transObjInfo * totransobj =
2362       (struct transObjInfo *)(item->objectptr);
2363     void * dst = flushObj(totransobj->objptr);
2364     if(dst != NULL) {
2365       totransobj->objptr = dst;
2366     }
2367     item = getNextQueueItem(item);
2368   }       // while(item != NULL)
2369
2370   // enqueue lock related info
2371   for(i = 0; i < runtime_locklen; ++i) {
2372     void * dst = flushObj(runtime_locks[i].redirectlock);
2373     if(dst != NULL) {
2374       runtime_locks[i].redirectlock = (int)dst;
2375     }
2376     if(runtime_locks[i].value != NULL) {
2377       void * dst=flushObj(runtime_locks[i].value);
2378       if(dst != NULL) {
2379         runtime_locks[i].value = (int)dst;
2380       }
2381     }
2382   }
2383
2384 } // void flushRuntimeObj(struct garbagelist * stackptr)
2385
2386 inline void flush(struct garbagelist * stackptr) {
2387 #ifdef GC_PROFILE
2388   if(BAMBOO_NUM_OF_CORE == 0) {
2389     BAMBOO_DEBUGPRINT(0xcccc);
2390     BAMBOO_DEBUGPRINT_REG(BAMBOO_GET_EXE_TIME());
2391   }
2392 #endif
2393   flushRuntimeObj(stackptr);
2394 #ifdef GC_PROFILE
2395   if(BAMBOO_NUM_OF_CORE == 0) BAMBOO_DEBUGPRINT_REG(BAMBOO_GET_EXE_TIME());
2396 #endif
2397
2398   while(true) {
2399     BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
2400     bool hasItems = gc_moreItems_I();
2401     BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
2402     if(!hasItems) {
2403       break;
2404     }
2405
2406 #ifdef DEBUG
2407     BAMBOO_DEBUGPRINT(0xe301);
2408 #endif
2409     BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
2410     void * ptr = gc_dequeue_I();
2411     BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
2412     if(ISSHAREDOBJ(ptr)) {
2413       // should be a local shared obj and should have mapping info
2414       ptr = flushObj(ptr);
2415 #ifdef DEBUG
2416       BAMBOO_DEBUGPRINT(0xe302);
2417       BAMBOO_DEBUGPRINT_REG(ptr);
2418       BAMBOO_DEBUGPRINT_REG(tptr);
2419       BAMBOO_DEBUGPRINT_REG(((int *)(tptr))[0]);
2420 #endif
2421       if(ptr == NULL) {
2422         BAMBOO_EXIT(0xb105);
2423       }
2424     }             // if(ISSHAREDOBJ(ptr))
2425     if((!ISSHAREDOBJ(ptr)) || (((int *)(ptr))[6] == COMPACTED)) {
2426       int type = ((int *)(ptr))[0];
2427       // scan all pointers in ptr
2428       unsigned INTPTR * pointer;
2429       pointer=pointerarray[type];
2430 #ifdef DEBUG
2431       BAMBOO_DEBUGPRINT(0xe303);
2432       BAMBOO_DEBUGPRINT_REG(pointer);
2433 #endif
2434       if (pointer==0) {
2435         /* Array of primitives */
2436         /* Do nothing */
2437       } else if (((INTPTR)pointer)==1) {
2438 #ifdef DEBUG
2439         BAMBOO_DEBUGPRINT(0xe304);
2440 #endif
2441         /* Array of pointers */
2442         struct ArrayObject *ao=(struct ArrayObject *) ptr;
2443         int length=ao->___length___;
2444         int j;
2445         for(j=0; j<length; j++) {
2446 #ifdef DEBUG
2447           BAMBOO_DEBUGPRINT(0xe305);
2448 #endif
2449           void *objptr=
2450             ((void **)(((char *)&ao->___length___)+sizeof(int)))[j];
2451 #ifdef DEBUG
2452           BAMBOO_DEBUGPRINT_REG(objptr);
2453 #endif
2454           if(objptr != NULL) {
2455             void * dst = flushObj(objptr);
2456             if(dst != NULL) {
2457               ((void **)(((char *)&ao->___length___)+sizeof(int)))[j] = dst;
2458             }
2459           }
2460         }
2461       } else {
2462 #ifdef DEBUG
2463         BAMBOO_DEBUGPRINT(0xe306);
2464 #endif
2465         INTPTR size=pointer[0];
2466         int i;
2467         for(i=1; i<=size; i++) {
2468 #ifdef DEBUG
2469           BAMBOO_DEBUGPRINT(0xe307);
2470 #endif
2471           unsigned int offset=pointer[i];
2472           void * objptr=*((void **)(((char *)ptr)+offset));
2473 #ifdef DEBUG
2474           BAMBOO_DEBUGPRINT_REG(objptr);
2475 #endif
2476           if(objptr != NULL) {
2477             void * dst = flushObj(objptr);
2478             if(dst != NULL) {
2479               *((void **)(((char *)ptr)+offset)) = dst;
2480             }
2481           }
2482         }                         // for(i=1; i<=size; i++)
2483       }                   // if (pointer==0) else if (((INTPTR)pointer)==1) else ()
2484                           // restore the mark field, indicating that this obj has been flushed
2485       if(ISSHAREDOBJ(ptr)) {
2486         ((int *)(ptr))[6] = INIT;
2487       }
2488     }             // if((!ISSHAREDOBJ(ptr)) || (((int *)(ptr))[6] == COMPACTED))
2489   }       // while(gc_moreItems())
2490 #ifdef DEBUG
2491   BAMBOO_DEBUGPRINT(0xe308);
2492 #endif
2493 #ifdef GC_PROFILE
2494   if(BAMBOO_NUM_OF_CORE == 0) BAMBOO_DEBUGPRINT_REG(BAMBOO_GET_EXE_TIME());
2495 #endif
2496
2497   // TODO bug here: the startup core contains all lobjs' info, thus all the
2498   // lobjs are flushed in sequence.
2499   // flush lobjs
2500   while(gc_lobjmoreItems_I()) {
2501 #ifdef DEBUG
2502     BAMBOO_DEBUGPRINT(0xe309);
2503 #endif
2504     void * ptr = gc_lobjdequeue_I(NULL, NULL);
2505     ptr = flushObj(ptr);
2506 #ifdef DEBUG
2507     BAMBOO_DEBUGPRINT(0xe30a);
2508     BAMBOO_DEBUGPRINT_REG(ptr);
2509     BAMBOO_DEBUGPRINT_REG(tptr);
2510     BAMBOO_DEBUGPRINT_REG(((int *)(tptr))[0]);
2511 #endif
2512     if(ptr == NULL) {
2513       BAMBOO_EXIT(0x106);
2514     }
2515     if(((int *)(ptr))[6] == COMPACTED) {
2516       int type = ((int *)(ptr))[0];
2517       // scan all pointers in ptr
2518       unsigned INTPTR * pointer;
2519       pointer=pointerarray[type];
2520 #ifdef DEBUG
2521       BAMBOO_DEBUGPRINT(0xe30b);
2522       BAMBOO_DEBUGPRINT_REG(pointer);
2523 #endif
2524       if (pointer==0) {
2525         /* Array of primitives */
2526         /* Do nothing */
2527       } else if (((INTPTR)pointer)==1) {
2528 #ifdef DEBUG
2529         BAMBOO_DEBUGPRINT(0xe30c);
2530 #endif
2531         /* Array of pointers */
2532         struct ArrayObject *ao=(struct ArrayObject *) ptr;
2533         int length=ao->___length___;
2534         int j;
2535         for(j=0; j<length; j++) {
2536 #ifdef DEBUG
2537           BAMBOO_DEBUGPRINT(0xe30d);
2538 #endif
2539           void *objptr=
2540             ((void **)(((char *)&ao->___length___)+sizeof(int)))[j];
2541 #ifdef DEBUG
2542           BAMBOO_DEBUGPRINT_REG(objptr);
2543 #endif
2544           if(objptr != NULL) {
2545             void * dst = flushObj(objptr);
2546             if(dst != NULL) {
2547               ((void **)(((char *)&ao->___length___)+sizeof(int)))[j] = dst;
2548             }
2549           }
2550         }
2551       } else {
2552 #ifdef DEBUG
2553         BAMBOO_DEBUGPRINT(0xe30e);
2554 #endif
2555         INTPTR size=pointer[0];
2556         int i;
2557         for(i=1; i<=size; i++) {
2558 #ifdef DEBUG
2559           BAMBOO_DEBUGPRINT(0xe30f);
2560 #endif
2561           unsigned int offset=pointer[i];
2562           void * objptr=*((void **)(((char *)ptr)+offset));
2563
2564 #ifdef DEBUG
2565           BAMBOO_DEBUGPRINT_REG(objptr);
2566 #endif
2567           if(objptr != NULL) {
2568             void * dst = flushObj(objptr);
2569             if(dst != NULL) {
2570               *((void **)(((char *)ptr)+offset)) = dst;
2571             }
2572           }
2573         }                         // for(i=1; i<=size; i++)
2574       }                   // if (pointer==0) else if (((INTPTR)pointer)==1) else ()
2575                           // restore the mark field, indicating that this obj has been flushed
2576       ((int *)(ptr))[6] = INIT;
2577     }             // if(((int *)(ptr))[6] == COMPACTED)
2578   }       // while(gc_lobjmoreItems())
2579 #ifdef DEBUG
2580   BAMBOO_DEBUGPRINT(0xe310);
2581 #endif
2582 #ifdef GC_PROFILE
2583   if(BAMBOO_NUM_OF_CORE == 0) BAMBOO_DEBUGPRINT_REG(BAMBOO_GET_EXE_TIME());
2584 #endif
2585
2586   // send flush finish message to core coordinator
2587   if(STARTUPCORE == BAMBOO_NUM_OF_CORE) {
2588     gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
2589   } else {
2590     send_msg_2(STARTUPCORE, GCFINISHFLUSH, BAMBOO_NUM_OF_CORE);
2591   }
2592 #ifdef GC_PROFILE
2593   if(BAMBOO_NUM_OF_CORE == 0) {
2594     BAMBOO_DEBUGPRINT(0xffff);
2595     //BAMBOO_DEBUGPRINT_REG(num_mapinforequest);
2596     BAMBOO_DEBUGPRINT_REG(flushstalltime);
2597     //BAMBOO_DEBUGPRINT_REG(num_mapinforequest_i);
2598     BAMBOO_DEBUGPRINT_REG(flushstalltime_i);
2599   }
2600   //BAMBOO_DEBUGPRINT_REG(flushstalltime);
2601 #endif
2602 #ifdef DEBUG
2603   BAMBOO_DEBUGPRINT(0xe311);
2604 #endif
2605 } // flush()
2606
2607 inline void gc_collect(struct garbagelist * stackptr) {
2608   // core collector routine
2609   while(true) {
2610     if(INITPHASE == gcphase) {
2611       break;
2612     }
2613   }
2614 #ifdef RAWPATH // TODO GC_DEBUG
2615   printf("(%X,%X) Do initGC\n", udn_tile_coord_x(), udn_tile_coord_y());
2616 #endif
2617   initGC();
2618   //send init finish msg to core coordinator
2619   send_msg_2(STARTUPCORE, GCFINISHINIT, BAMBOO_NUM_OF_CORE);
2620   while(true) {
2621     if(MARKPHASE == gcphase) {
2622       break;
2623     }
2624   }
2625 #ifdef RAWPATH // TODO GC_DEBUG
2626   printf("(%x,%x) Start mark phase\n", udn_tile_coord_x(),
2627              udn_tile_coord_y());
2628 #endif
2629   mark(true, stackptr);
2630 #ifdef RAWPATH // TODO GC_DEBUG
2631   printf("(%x,%x) Finish mark phase, start compact phase\n",
2632              udn_tile_coord_x(), udn_tile_coord_y());
2633 #endif
2634   compact();
2635 #ifdef RAWPATH // TODO GC_DEBUG
2636   printf("(%x,%x) Finish compact phase\n", udn_tile_coord_x(),
2637              udn_tile_coord_y());
2638 #endif
2639   while(true) {
2640     if(FLUSHPHASE == gcphase) {
2641       break;
2642     }
2643   }
2644 #ifdef RAWPATH // TODO GC_DEBUG
2645   printf("(%x,%x) Start flush phase\n", udn_tile_coord_x(),
2646              udn_tile_coord_y());
2647 #endif
2648   flush(stackptr);
2649 #ifdef RAWPATH // TODO GC_DEBUG
2650   printf("(%x,%x) Finish flush phase\n", udn_tile_coord_x(),
2651              udn_tile_coord_y());
2652 #endif
2653
2654   while(true) {
2655     if(FINISHPHASE == gcphase) {
2656       break;
2657     }
2658   }
2659 #ifdef RAWPATH // TODO GC_DEBUG
2660   printf("(%x,%x) Finish gc!\n", udn_tile_coord_x(), udn_tile_coord_y());
2661 #endif
2662 } // void gc_collect(struct garbagelist * stackptr)
2663
2664 inline void gc_nocollect(struct garbagelist * stackptr) {
2665   while(true) {
2666     if(INITPHASE == gcphase) {
2667       break;
2668     }
2669   }
2670 #ifdef RAWPATH // TODO GC_DEBUG
2671   printf("(%x,%x) Do initGC\n", udn_tile_coord_x(), udn_tile_coord_y());
2672 #endif
2673   initGC();
2674   //send init finish msg to core coordinator
2675   send_msg_2(STARTUPCORE, GCFINISHINIT, BAMBOO_NUM_OF_CORE);
2676   while(true) {
2677     if(MARKPHASE == gcphase) {
2678       break;
2679     }
2680   }
2681 #ifdef RAWPATH // TODO GC_DEBUG
2682   printf("(%x,%x) Start mark phase\n", udn_tile_coord_x(),
2683              udn_tile_coord_y());
2684 #endif
2685   mark(true, stackptr);
2686 #ifdef RAWPATH // TODO GC_DEBUG
2687   printf("(%x,%x) Finish mark phase, wait for flush\n",
2688              udn_tile_coord_x(), udn_tile_coord_y());
2689 #endif
2690   // non-gc core collector routine
2691   while(true) {
2692     if(FLUSHPHASE == gcphase) {
2693       break;
2694     }
2695   }
2696 #ifdef RAWPATH // TODO GC_DEBUG
2697   printf("(%x,%x) Start flush phase\n", udn_tile_coord_x(),
2698              udn_tile_coord_y());
2699 #endif
2700   flush(stackptr);
2701 #ifdef RAWPATH // TODO GC_DEBUG
2702   printf("(%x,%x) Finish flush phase\n", udn_tile_coord_x(),
2703              udn_tile_coord_y());
2704 #endif
2705
2706   while(true) {
2707     if(FINISHPHASE == gcphase) {
2708       break;
2709     }
2710   }
2711 #ifdef RAWPATH // TODO GC_DEBUG
2712   printf("(%x,%x) Finish gc!\n", udn_tile_coord_x(), udn_tile_coord_y());
2713 #endif
2714 } // void gc_collect(struct garbagelist * stackptr)
2715
2716 inline void gc(struct garbagelist * stackptr) {
2717   // check if do gc
2718   if(!gcflag) {
2719     gcprocessing = false;
2720     return;
2721   }
2722
2723   // core coordinator routine
2724   if(0 == BAMBOO_NUM_OF_CORE) {
2725 #ifdef GC_DEBUG
2726     printf("(%x,%X) Check if can do gc or not\n", udn_tile_coord_x(),
2727                    udn_tile_coord_y());
2728 #endif
2729     if(!preGC()) {
2730       // not ready to do gc
2731       gcflag = true;
2732       return;
2733     }
2734
2735 #ifdef GC_PROFILE
2736     gc_profileStart();
2737 #endif
2738
2739 #ifdef RAWPATH // TODO GC_DEBUG
2740     printf("(%x,%x) start gc! \n", udn_tile_coord_x(), udn_tile_coord_y());
2741     //dumpSMem();
2742 #endif
2743     gcprocessing = true;
2744     gcphase = INITPHASE;
2745     int i = 0;
2746     waitconfirm = false;
2747     numconfirm = 0;
2748     initGC();
2749
2750     // Note: all cores need to init gc including non-gc cores
2751     for(i = 1; i < NUMCORESACTIVE /*NUMCORES4GC*/; i++) {
2752       // send GC init messages to all cores
2753       send_msg_1(i, GCSTARTINIT);
2754     }
2755     bool isfirst = true;
2756     bool allStall = false;
2757
2758 #ifdef RAWPATH // TODO GC_DEBUG
2759     printf("(%x,%x) Check core status \n", udn_tile_coord_x(),
2760                    udn_tile_coord_y());
2761 #endif
2762
2763     gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
2764     while(true) {
2765       BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
2766       if(gc_checkAllCoreStatus_I()) {
2767         BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
2768         break;
2769       }
2770       BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
2771     }
2772 #ifdef GC_PROFILE
2773     gc_profileItem();
2774 #endif
2775 #ifdef RAWPATH // TODO GC_DEBUG
2776     printf("(%x,%x) Start mark phase \n", udn_tile_coord_x(),
2777                    udn_tile_coord_y());
2778 #endif
2779     // all cores have finished compacting
2780     // restore the gcstatus of all cores
2781     // Note: all cores have to do mark including non-gc cores
2782     gccorestatus[BAMBOO_NUM_OF_CORE] = 1;
2783     for(i = 1; i < NUMCORESACTIVE /*NUMCORES4GC*/; ++i) {
2784       gccorestatus[i] = 1;
2785       // send GC start messages to all cores
2786       send_msg_1(i, GCSTART);
2787     }
2788
2789     gcphase = MARKPHASE;
2790     // mark phase
2791     while(MARKPHASE == gcphase) {
2792       mark(isfirst, stackptr);
2793       if(isfirst) {
2794         isfirst = false;
2795       }
2796
2797       // check gcstatus
2798       checkMarkStatue();
2799     }              // while(MARKPHASE == gcphase)
2800                    // send msgs to all cores requiring large objs info
2801                    // Note: only need to ask gc cores, non-gc cores do not host any objs
2802     numconfirm = NUMCORES4GC - 1;
2803     for(i = 1; i < NUMCORES4GC; ++i) {
2804       send_msg_1(i, GCLOBJREQUEST);
2805     }
2806     gcloads[BAMBOO_NUM_OF_CORE] = gccurr_heaptop;
2807     while(true) {
2808       if(numconfirm==0) {
2809         break;
2810       }
2811     }             // wait for responses
2812                   // check the heaptop
2813     if(gcheaptop < gcmarkedptrbound) {
2814       gcheaptop = gcmarkedptrbound;
2815     }
2816 #ifdef GC_PROFILE
2817     gc_profileItem();
2818     // TODO
2819     if(BAMBOO_NUM_OF_CORE == 0) {
2820       BAMBOO_DEBUGPRINT(0xeeee);
2821       BAMBOO_DEBUGPRINT_REG(num_markrequest);
2822       BAMBOO_DEBUGPRINT_REG(marktime);
2823     }
2824 #endif
2825 #ifdef RAWPATH // TODO GC_DEBUG
2826     printf("(%x,%x) prepare to cache large objs \n", udn_tile_coord_x(),
2827                    udn_tile_coord_y());
2828     //dumpSMem();
2829 #endif
2830     // cache all large objs
2831     if(!cacheLObjs()) {
2832       // no enough space to cache large objs
2833       BAMBOO_EXIT(0xb107);
2834     }
2835     // predict number of blocks to fill for each core
2836     int tmpheaptop = 0;
2837     int numpbc = loadbalance(&tmpheaptop);
2838     // TODO
2839     numpbc = (BAMBOO_SHARED_MEM_SIZE)/(BAMBOO_SMEM_SIZE);
2840 #ifdef RAWPATH // TODO GC_DEBUG
2841     printf("(%x,%x) mark phase finished \n", udn_tile_coord_x(),
2842                    udn_tile_coord_y());
2843     //dumpSMem();
2844 #endif
2845     //int tmptopptr = 0;
2846     //BASEPTR(gctopcore, 0, &tmptopptr);
2847     // TODO
2848     //tmptopptr = (BAMBOO_BASE_VA) + (BAMBOO_SHARED_MEM_SIZE);
2849     tmpheaptop = (BAMBOO_BASE_VA) + (BAMBOO_SHARED_MEM_SIZE);
2850 #ifdef DEBUG
2851     BAMBOO_DEBUGPRINT(0xabab);
2852     BAMBOO_DEBUGPRINT_REG(tmptopptr);
2853 #endif
2854     for(i = 0; i < NUMCORES4GC; ++i) {
2855       int tmpcoreptr = 0;
2856       BASEPTR(i, numpbc, &tmpcoreptr);
2857       //send start compact messages to all cores
2858       //TODO bug here, do not know if the direction is positive or negtive?
2859       if (tmpcoreptr < tmpheaptop /*tmptopptr*/) {
2860         gcstopblock[i] = numpbc + 1;
2861         if(i != STARTUPCORE) {
2862           send_msg_2(i, GCSTARTCOMPACT, numpbc+1);
2863         } else {
2864           gcblock2fill = numpbc+1;
2865         }                         // if(i != STARTUPCORE)
2866       } else {
2867         gcstopblock[i] = numpbc;
2868         if(i != STARTUPCORE) {
2869           send_msg_2(i, GCSTARTCOMPACT, numpbc);
2870         } else {
2871           gcblock2fill = numpbc;
2872         }                         // if(i != STARTUPCORE)
2873       }
2874 #ifdef DEBUG
2875       BAMBOO_DEBUGPRINT(0xf000+i);
2876       BAMBOO_DEBUGPRINT_REG(tmpcoreptr);
2877       BAMBOO_DEBUGPRINT_REG(gcstopblock[i]);
2878 #endif
2879       // init some data strutures for compact phase
2880       gcloads[i] = 0;
2881       gcfilledblocks[i] = 0;
2882       gcrequiredmems[i] = 0;
2883     }
2884
2885 #ifdef GC_PROFILE
2886     gc_profileItem();
2887 #endif
2888
2889     // compact phase
2890     bool finalcompact = false;
2891     // initialize pointers for comapcting
2892     struct moveHelper * orig =
2893       (struct moveHelper *)RUNMALLOC(sizeof(struct moveHelper));
2894     struct moveHelper * to =
2895       (struct moveHelper *)RUNMALLOC(sizeof(struct moveHelper));
2896     initOrig_Dst(orig, to);
2897     int filledblocks = 0;
2898     INTPTR heaptopptr = 0;
2899     bool finishcompact = false;
2900     bool iscontinue = true;
2901     bool localcompact = true;
2902     while((COMPACTPHASE == gcphase) || (SUBTLECOMPACTPHASE == gcphase)) {
2903       if((!finishcompact) && iscontinue) {
2904 #ifdef DEBUG
2905         BAMBOO_DEBUGPRINT(0xe001);
2906         BAMBOO_DEBUGPRINT_REG(numpbc);
2907         BAMBOO_DEBUGPRINT_REG(gcblock2fill);
2908 #endif
2909         finishcompact = compacthelper(orig, to, &filledblocks,
2910                                       &heaptopptr, &localcompact);
2911 #ifdef DEBUG
2912         BAMBOO_DEBUGPRINT(0xe002);
2913         BAMBOO_DEBUGPRINT_REG(finishcompact);
2914         BAMBOO_DEBUGPRINT_REG(gctomove);
2915         BAMBOO_DEBUGPRINT_REG(gcrequiredmems[0]);
2916         BAMBOO_DEBUGPRINT_REG(gcfilledblocks[0]);
2917         BAMBOO_DEBUGPRINT_REG(gcstopblock[0]);
2918 #endif
2919       }
2920
2921       BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
2922       if(gc_checkCoreStatus_I()) {
2923         // all cores have finished compacting
2924         // restore the gcstatus of all cores
2925         for(i = 0; i < NUMCORES4GC; ++i) {
2926           gccorestatus[i] = 1;
2927         }
2928         BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
2929         break;
2930       } else {
2931         BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
2932         // check if there are spare mem for pending move requires
2933         if(COMPACTPHASE == gcphase) {
2934 #ifdef DEBUG
2935           BAMBOO_DEBUGPRINT(0xe003);
2936 #endif
2937           resolvePendingMoveRequest();
2938 #ifdef DEBUG
2939           BAMBOO_DEBUGPRINT_REG(gctomove);
2940 #endif
2941         } else {
2942 #ifdef DEBUG
2943           BAMBOO_DEBUGPRINT(0xe004);
2944 #endif
2945           compact2Heaptop();
2946         }
2947       }                   // if(gc_checkCoreStatus_I()) else ...
2948
2949       if(gctomove) {
2950 #ifdef DEBUG
2951         BAMBOO_DEBUGPRINT(0xe005);
2952         BAMBOO_DEBUGPRINT_REG(gcmovestartaddr);
2953         BAMBOO_DEBUGPRINT_REG(gcblock2fill);
2954         BAMBOO_DEBUGPRINT_REG(gctomove);
2955 #endif
2956         to->ptr = gcmovestartaddr;
2957         to->numblocks = gcblock2fill - 1;
2958         to->bound = (to->numblocks==0) ?
2959                     BAMBOO_SMEM_SIZE_L :
2960                     BAMBOO_SMEM_SIZE_L+BAMBOO_SMEM_SIZE*to->numblocks;
2961         BASEPTR(gcdstcore, to->numblocks, &(to->base));
2962         to->offset = to->ptr - to->base;
2963         to->top = (to->numblocks==0) ?
2964                   (to->offset) : (to->bound-BAMBOO_SMEM_SIZE+to->offset);
2965         to->base = to->ptr;
2966         to->offset = BAMBOO_CACHE_LINE_SIZE;
2967         to->ptr += to->offset;                         // for header
2968         to->top += to->offset;
2969         if(gcdstcore == BAMBOO_NUM_OF_CORE) {
2970           localcompact = true;
2971         } else {
2972           localcompact = false;
2973         }
2974         gctomove = false;
2975         iscontinue = true;
2976       } else if(!finishcompact) {
2977         // still pending
2978         iscontinue = false;
2979       }                   // if(gctomove)
2980
2981     }             // while(COMPACTPHASE == gcphase)
2982 #ifdef GC_PROFILE
2983     gc_profileItem();
2984 #endif
2985 #ifdef RAWPATH // TODO GC_DEBUG
2986     printf("(%x,%x) prepare to move large objs \n", udn_tile_coord_x(),
2987                udn_tile_coord_y());
2988     //dumpSMem();
2989 #endif
2990     // move largeObjs
2991     moveLObjs();
2992 #ifdef RAWPATH // TODO GC_DEBUG
2993     printf("(%x,%x) compact phase finished \n", udn_tile_coord_x(),
2994                    udn_tile_coord_y());
2995     //dumpSMem();
2996 #endif
2997     RUNFREE(orig);
2998     RUNFREE(to);
2999     orig = to = NULL;
3000
3001     gcphase = FLUSHPHASE;
3002     gccorestatus[BAMBOO_NUM_OF_CORE] = 1;
3003     // Note: all cores should flush their runtime data including non-gc
3004     //       cores
3005     for(i = 1; i < NUMCORESACTIVE /*NUMCORES4GC*/; ++i) {
3006       // send start flush messages to all cores
3007       gccorestatus[i] = 1;
3008       send_msg_1(i, GCSTARTFLUSH);
3009     }
3010 #ifdef GC_PROFILE
3011     gc_profileItem();
3012 #endif
3013 #ifdef RAWPATH // TODO GC_DEBUG
3014     printf("(%x,%x) Start flush phase \n", udn_tile_coord_x(),
3015                    udn_tile_coord_y());
3016 #endif
3017     // flush phase
3018     flush(stackptr);
3019     gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
3020     while(FLUSHPHASE == gcphase) {
3021       // check the status of all cores
3022       BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
3023       if(gc_checkAllCoreStatus_I()) {
3024         BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
3025         break;
3026       }
3027       BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
3028     }             // while(FLUSHPHASE == gcphase)
3029     gcphase = FINISHPHASE;
3030
3031     // invalidate all shared mem pointers
3032     // put it here as it takes time to inform all the other cores to
3033     // finish gc and it might cause problem when some core resumes
3034     // mutator earlier than the other cores
3035     bamboo_cur_msp = NULL;
3036     bamboo_smem_size = 0;
3037     gcflag = false;
3038     gcprocessing = false;
3039
3040 #ifdef GC_PROFILE
3041     gc_profileEnd();
3042 #endif
3043     gccorestatus[BAMBOO_NUM_OF_CORE] = 1;
3044     for(i = 1; i < NUMCORESACTIVE /*NUMCORES4GC*/; ++i) {
3045       // send gc finish messages to all cores
3046       send_msg_1(i, GCFINISH);
3047       gccorestatus[i] = 1;
3048     }
3049 #ifdef RAWPATH // TODO GC_DEBUG
3050     printf("(%x,%x) gc finished \n", udn_tile_coord_x(),
3051                    udn_tile_coord_y());
3052     //dumpSMem();
3053 #endif
3054   } else if(BAMBOO_NUM_OF_CORE < NUMCORES4GC) {
3055     gcprocessing = true;
3056     gc_collect(stackptr);
3057
3058     // invalidate all shared mem pointers
3059     bamboo_cur_msp = NULL;
3060     bamboo_smem_size = 0;
3061
3062     gcflag = false;
3063     gcprocessing = false;
3064   } else {
3065     // not a gc core, should wait for gcfinish msg
3066     gcprocessing = true;
3067     gc_nocollect(stackptr);
3068
3069     // invalidate all shared mem pointers
3070     bamboo_cur_msp = NULL;
3071     bamboo_smem_size = 0;
3072
3073     gcflag = false;
3074     gcprocessing = false;
3075   }
3076 } // void gc(struct garbagelist * stackptr)
3077
3078 #ifdef GC_PROFILE
3079 inline void gc_profileStart(void) {
3080   if(!gc_infoOverflow) {
3081     GCInfo* gcInfo = RUNMALLOC(sizeof(struct gc_info));
3082     gc_infoArray[gc_infoIndex] = gcInfo;
3083     gcInfo->index = 1;
3084     gcInfo->time[0] = BAMBOO_GET_EXE_TIME();
3085   }
3086 }
3087
3088 inline void gc_profileItem(void) {
3089   if(!gc_infoOverflow) {
3090     GCInfo* gcInfo = gc_infoArray[gc_infoIndex];
3091     gcInfo->time[gcInfo->index++] = BAMBOO_GET_EXE_TIME();
3092   }
3093 }
3094
3095 inline void gc_profileEnd(void) {
3096   if(!gc_infoOverflow) {
3097     GCInfo* gcInfo = gc_infoArray[gc_infoIndex];
3098     gcInfo->time[gcInfo->index++] = BAMBOO_GET_EXE_TIME();
3099     gc_infoIndex++;
3100     if(gc_infoIndex == GCINFOLENGTH) {
3101       gc_infoOverflow = true;
3102       //taskInfoIndex = 0;
3103     }
3104   }
3105 }
3106
3107 // output the profiling data
3108 void gc_outputProfileData() {
3109 #ifdef USEIO
3110   int i,j;
3111   unsigned long long totalgc = 0;
3112
3113   //printf("Start Time, End Time, Duration\n");
3114   // output task related info
3115   for(i = 0; i < gc_infoIndex; i++) {
3116     GCInfo * gcInfo = gc_infoArray[i];
3117     unsigned long long tmp = 0;
3118     for(j = 0; j < gcInfo->index; j++) {
3119       printf("%lld(%lld), ", gcInfo->time[j], (gcInfo->time[j]-tmp));
3120       tmp = gcInfo->time[j];
3121     }
3122     tmp = (tmp-gcInfo->time[0]);
3123     printf(" ++ %lld \n", tmp);
3124     totalgc += tmp;
3125   }
3126
3127   if(gc_infoOverflow) {
3128     printf("Caution: gc info overflow!\n");
3129   }
3130
3131   printf("\n\n total gc time: %lld \n", totalgc);
3132 #else
3133   int i = 0;
3134   int j = 0;
3135   unsigned long long totalgc = 0;
3136
3137   BAMBOO_DEBUGPRINT(0xdddd);
3138   // output task related info
3139   for(i= 0; i < gc_infoIndex; i++) {
3140     GCInfo * gcInfo = gc_infoArray[i];
3141     unsigned long long tmp = 0;
3142     BAMBOO_DEBUGPRINT(0xddda);
3143     for(j = 0; j < gcInfo->index; j++) {
3144       BAMBOO_DEBUGPRINT(gcInfo->time[j]);
3145       BAMBOO_DEBUGPRINT(gcInfo->time[j]-tmp);
3146       BAMBOO_DEBUGPRINT(0xdddb);
3147       tmp = gcInfo->time[j];
3148     }
3149     tmp = (tmp-gcInfo->time[0]);
3150     BAMBOO_DEBUGPRINT_REG(tmp);
3151     BAMBOO_DEBUGPRINT(0xdddc);
3152     totalgc += tmp;
3153   }
3154   BAMBOO_DEBUGPRINT(0xdddd);
3155   BAMBOO_DEBUGPRINT_REG(totalgc);
3156
3157   if(gc_infoOverflow) {
3158     BAMBOO_DEBUGPRINT(0xefee);
3159   }
3160
3161   BAMBOO_DEBUGPRINT(0xeeee);
3162 #endif
3163 }
3164 #endif  // #ifdef GC_PROFILE
3165
3166 #endif