Robust/src/Runtime/multicoregarbage.c

   1 #ifdef MULTICORE_GC
   2 #include "multicoregarbage.h"
   3 #include "multicoreruntime.h"
   4 #include "runtime_arch.h"
   5 #include "SimpleHash.h"
   6 #include "GenericHashtable.h"
   7
   8 extern struct genhashtable * activetasks;
   9 extern struct parameterwrapper ** objectqueues[][NUMCLASSES];
  10 extern struct taskparamdescriptor *currtpdo;
  11
  12 struct largeObjList {
  13         struct largeObjItem * head;
  14         struct largeObjItem * tail;
  15 };
  16
  17 struct largeObjList lObjList;
  18
  19 #define NUMPTRS 100
  20
  21 void gc_enqueue(void *ptr) {
  22   if (gcheadindex==NUMPTRS) {
  23     struct pointerblock * tmp;
  24     if (gcspare!=NULL) {
  25       tmp=gcspare;
  26       gcspare=NULL;
  27     } else
  28       tmp=malloc(sizeof(struct pointerblock));
  29     gchead->next=tmp;
  30     gchead=tmp;
  31     gcheadindex=0;
  32   }
  33   gchead->ptrs[gcheadindex++]=ptr;
  34 }
  35
  36 // dequeue and destroy the queue
  37 void * gc_dequeue() {
  38   if (gctailindex==NUMPTRS) {
  39     struct pointerblock *tmp=tail;
  40     gctail=gctail->next;
  41     gctailindex=0;
  42     if (gcspare!=NULL)
  43       free(tmp);
  44     else
  45       gcspare=tmp;
  46   }
  47   return gctail->ptrs[gctailindex++];
  48 }
  49
  50 // dequeue and do not destroy the queue
  51 void * gc_dequeue2() {
  52         if (gctailindex2==NUMPTRS) {
  53     struct pointerblock *tmp=tail;
  54     gctail2=gctail2->next;
  55     gctailindex2=0;
  56   }
  57   return gctail2->ptrs[gctailindex2++];
  58 }
  59
  60 int gc_moreItems() {
  61   if ((gchead==gctail)&&(gctailindex==gcheadindex))
  62     return 0;
  63   return 1;
  64 }
  65
  66 int gc_moreItems2() {
  67   if ((gchead==gctail2)&&(gctailindex2==gcheadindex))
  68     return 0;
  69   return 1;
  70 }
  71
  72 INTPTR curr_heaptop = 0;
  73
  74 bool isLarge(void * ptr, int * ttype, int * tsize) {
  75         // check if a pointer is referring to a large object
  76         int type = ((int *)ptr)[0];
  77         int size = 0;
  78         if(type < NUMCLASSES) {
  79                 // a normal object
  80                 size = classsize[type];
  81         } else {
  82                 // an array
  83                 struct ArrayObject *ao=(struct ArrayObject *)ptr;
  84                 int elementsize=classsize[type];
  85                 int length=ao->___length___;
  86                 size=sizeof(struct ArrayObject)+length*elementsize;
  87         }
  88         *ttype = type;
  89         *tsize = size;
  90         return(!isLocal(ptr + size));
  91 }
  92
  93 int hostcore(void * ptr) {
  94         // check the host core of ptr
  95         int host = 0;
  96         int x = 0;
  97         int y = 0;
  98         RESIDECORE(ptr, &x, &y);
  99         host = (x == 0)?(x * bamboo_height + y) : (x * bamboo_height + y - 2);
 100         return host;
 101 }
 102
 103 bool isLocal(void * ptr) {
 104         // check if a pointer is in shared heap on this core
 105         return hostcore(ptr) == BAMBOO_NUM_OF_CORE;
 106 }
 107
 108 void transferMarkResults() {
 109         // TODO, need distiguish between send and cache
 110         // invoked inside interruptiong handler
 111 }
 112
 113 void checkMarkStatue() {
 114         if((!gcwaitconfirm) ||
 115                         (waitconfirm && (numconfirm == 0))) {
 116                 BAMBOO_START_CRITICAL_SECTION_STATUS();
 117                 gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
 118                 gcnumsendobjs[BAMBOO_NUM_OF_CORE] = gcself_numsendobjs;
 119                 gcnumreceiveobjs[BAMBOO_NUM_OF_CORE] = gcself_numreceiveobjs;
 120                 // check the status of all cores
 121                 bool allStall = true;
 122                 for(i = 0; i < NUMCORES; ++i) {
 123                         if(gccorestatus[i] != 0) {
 124                                 allStall = false;
 125                                 break;
 126                         }
 127                 }
 128                 if(allStall) {
 129                         // check if the sum of send objs and receive obj are the same
 130                         // yes->check if the info is the latest; no->go on executing
 131                         int sumsendobj = 0;
 132                         for(i = 0; i < NUMCORES; ++i) {
 133                                 sumsendobj += gcnumsendobjs[i];
 134                         }
 135                         for(i = 0; i < NUMCORES; ++i) {
 136                                 sumsendobj -= gcnumreceiveobjs[i];
 137                         }
 138                         if(0 == sumsendobj) {
 139                                 if(!waitconfirm) {
 140                                         // the first time found all cores stall
 141                                         // send out status confirm msg to all other cores
 142                                         // reset the corestatus array too
 143                                         gccorestatus[BAMBOO_NUM_OF_CORE] = 1;
 144                                         waitconfirm = true;
 145                                         numconfirm = NUMCORES - 1;
 146                                         for(i = 1; i < NUMCORES; ++i) {
 147                                                 gccorestatus[i] = 1;
 148                                                 // send mark phase finish confirm request msg to core i
 149                                                 send_msg_1(i, GCMARKCONFIRM);
 150                                         }
 151                                 } else {
 152                                         // all the core status info are the latest
 153                                         // stop mark phase
 154                                         gcphase = COMPACTPHASE;
 155                                         // restore the gcstatus for all cores
 156                                         for(i = 0; i < NUMCORES; ++i) {
 157                                                 gccorestatus[i] = 1;
 158                                         }
 159                                 } // if(!gcwautconfirm) else()
 160                         } // if(0 == sumsendobj)
 161                 } // if(allStall)
 162                 BAMBOO_CLOSE_CRITICAL_SECTION_STATUS();
 163         } // if((!gcwaitconfirm)...
 164 }
 165
 166 bool preGC() {
 167         // preparation for gc
 168         // make sure to clear all incoming msgs espacially transfer obj msgs
 169         int i;
 170         if((!waitconfirm) ||
 171                                                   (waitconfirm && (numconfirm == 0))) {
 172                 // send out status confirm msgs to all cores to check if there are
 173                 // transfer obj msgs on-the-fly
 174                 waitconfirm = true;
 175                 numconfirm = NUMCORES - 1;
 176                 for(i = 1; i < NUMCORES; ++i) {
 177                         corestatus[i] = 1;
 178                         // send status confirm msg to core i
 179                         send_msg_1(i, STATUSCONFIRM);
 180                 }
 181
 182                 while(numconfirm != 0) {} // wait for confirmations
 183                 numsendobjs[BAMBOO_NUM_OF_CORE] = self_numsendobjs;
 184                 numreceiveobjs[BAMBOO_NUM_OF_CORE] = self_numreceiveobjs;
 185                 int sumsendobj = 0;
 186                 for(i = 0; i < NUMCORES; ++i) {
 187                         sumsendobj += numsendobjs[i];
 188                 }
 189                 for(i = 0; i < NUMCORES; ++i) {
 190                         sumsendobj -= numreceiveobjs[i];
 191                 }
 192                 if(0 == sumsendobj) {
 193                         return true;
 194                 } else {
 195                         // still have some transfer obj msgs on-the-fly, can not start gc
 196                         return false;
 197                 }
 198         } else {
 199                 // previously asked for status confirmation and do not have all the
 200                 // confirmations yet, can not start gc
 201                 return false;
 202         }
 203 }
 204
 205 // compute load balance for all cores
 206 void loadbalance() {
 207         // compute load balance
 208         // initialize the deltas
 209         int i;
 210         int delta = 1 << 32 -1;
 211         int deltanew = 1 << 32 - 1;
 212         int lcore = 0;
 213         int rcore = 0;
 214         bool stop = true;
 215         for(i = 0; i < NUMCORES; i++) {
 216                 gcdeltal[i] = gcdeltar[i] = 0;
 217                 gcreloads[i] = gcloads[i];
 218         }
 219         do {
 220                 stop = true;
 221                 delta = deltanew;
 222                 // compute load balance
 223                 for(i = 0; i < NUMCORES; i++) {
 224                         if(gcreloads[i] > BAMBOO_SMEM_SIZE_L) {
 225                                 // too much load, try to redirect some of it to its neighbours
 226                                 LEFTNEIGHBOUR(i, &lcore);
 227                                 RIGHTNEIGHBOUR(i, &rcore);
 228                                 if(lcore != -1) {
 229                                         int tmp = (gcreloads[lcore] - gcreloads[i]) / 2;
 230                                         gcdeltal[i] = tmp;
 231                                         gcdeltar[lcore] = 0-tmp;
 232                                         deltanew += abs(gcreloads[lcore] - gcreloads[i]);
 233                                 }
 234                                 if(rcore != -1) {
 235                                         int tmp = (gcreloads[rcore] - gcreloads[i]) / 2;
 236                                         gcdeltar[i] = tmp;
 237                                         gcdeltal[rcore] = 0-tmp;
 238                                         deltanew += abs(gcreloads[rcore] - gcreloads[i]);
 239                                 }
 240                         }
 241                 }
 242                 deltanew /= 2;
 243                 if((deltanew == 0) || (delta == deltanew)) {
 244                         break;
 245                 }
 246                 // flush for new loads
 247                 for(i = 0; i < NUMCORES; i++) {
 248                         if((gcdeltal[i] != 0) || (gcdeltar[i] != 0)) {
 249                                 stop = false;
 250                                 gcreloads[i] += gcdeltal[i] + gcdeltar[i];
 251                                 gcdeltal[i] = gcdeltar[i] = 0;
 252                         }
 253                 }
 254         } while(!stop);
 255         for(i = 0; i < NUMCORES; i++) {
 256                 gcdeltal[i] = gcdeltar[i] = 0;
 257         }
 258         // decide how to do load balance
 259         for(i = 0; i < NUMCORES; i++) {
 260                 int tomove = (gcloads[i] - gcreloads[i]);
 261                 if(tomove > 0) {
 262                         LEFTNEIGHBOUR(i, &lcore);
 263                         RIGHTNEIGHBOUR(i, &rcore);
 264                         int lmove = 0;
 265                         int rmove = 0;
 266                         if(lcore != -1) {
 267                                 lmove = (gcreloads[lcore] - gcloads[lcore] - gcdeltal[lcore]);
 268                                 if(lmove < 0) {
 269                                         lmove = 0;
 270                                 }
 271                         }
 272                         if(rcore != -1) {
 273                                 rmove = (gcreloads[rcore] - gcloads[rcore] - gcdeltar[rcore]);
 274                                 if(rmove < 0) {
 275                                         rmove = 0;
 276                                 }
 277                         }
 278                         // the one with bigger gap has higher priority
 279                         if(lmove > rmove) {
 280                                 int ltomove = (lmove > tomove)? tomove:lmove;
 281                                 gcdeltar[lcore] = ltomove;
 282                                 gcdeltal[i] = 0-ltomove;
 283                                 gcdeltal[rcore] = tomove - ltomove;
 284                                 gcdeltar[i] = ltomove - tomove;
 285                         } else {
 286                                 int rtomove = (rmove > tomove)? tomove:rmove;
 287                                 gcdeltal[rcore] = rtomove;
 288                                 gcdeltar[i] = 0-rtomove;
 289                                 gcdeltar[lcore] = tomove - rtomove;
 290                                 gcdeltal[i] = rtomove - tomove;
 291                         }
 292                 }
 293         }
 294 }
 295
 296 void gc(struct garbagelist * stackptr) {
 297         // check if do gc
 298         if(!gcflag) {
 299                 return;
 300         }
 301
 302         // core coordinator routine
 303         if(0 == BAMBOO_NUM_OF_CORE) {
 304                 if(!preGC()) {
 305                         // not ready to do gc
 306                         gcflag = true;
 307                         return;
 308                 }
 309
 310                 int i = 0;
 311                 gcwaitconfirm = false;
 312                 gcwaitconfirm = 0;
 313                 gcphase = MARKPHASE;
 314                 for(i = 1; i < NUMCORES - 1; i++) {
 315                         // send GC start messages to all cores
 316                         send_msg_1(i, GCSTART);
 317                 }
 318                 bool isfirst = true;
 319                 bool allStall = false;
 320
 321                 // mark phase
 322                 while(MARKPHASE == gcphase) {
 323                         mark(isfirst, stackptr);
 324                         if(isfirst) {
 325                                 isfirst = false;
 326                         }
 327
 328                         // check gcstatus
 329                         checkMarkStatue();
 330                 }  // while(MARKPHASE == gcphase)
 331                 // send msgs to all cores requiring large objs info
 332                 numconfirm = NUMCORES - 1;
 333                 for(i = 1; i < NUMCORES; ++i) {
 334                         send_msg_1(i, GCLOBJREQUEST);
 335                 }
 336                 while(numconfirm != 0) {} // wait for responses
 337                 loadbalance();
 338                 // TODO need to decide where to put large objects
 339
 340                 // TODO cache all large objects
 341
 342                 for(i = 1; i < NUMCORES; ++i) {
 343                         //TODO send start compact messages to all cores
 344
 345                 }
 346
 347                 // compact phase
 348                 compact();
 349                 gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
 350                 while(COMPACTPHASE == gcphase) {
 351                         // check the status of all cores
 352                         allStall = true;
 353                         for(i = 0; i < NUMCORES; ++i) {
 354                                 if(gccorestatus[i] != 0) {
 355                                         allStall = false;
 356                                         break;
 357                                 }
 358                         }
 359                         if(allStall) {
 360                                 // restore the gcstatus of all cores
 361                                 for(i = 0; i < NUMCORES; ++i) {
 362                                         gccorestatus[i] = 1;
 363                                 }
 364                                 break;
 365                         }
 366                 } // while(COMPACTPHASE == gcphase)
 367                 // TODO merge all mapping information
 368
 369                 gcphase = FLUSHPHASE;
 370                 for(i = 1; i < NUMCORES; ++i) {
 371                         // send start flush messages to all cores
 372                         send_msg_1(i, GCSTARTFLUSH);
 373                 }
 374
 375                 // flush phase
 376                 flush();
 377                 gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
 378                 while(FLUSHPHASE == gcphase) {
 379                         // check the status of all cores
 380                         allStall = true;
 381                         for(i = 0; i < NUMCORES; ++i) {
 382                                 if(gccorestatus[i] != 0) {
 383                                         allStall = false;
 384                                         break;
 385                                 }
 386                         }
 387                         if(allStall) {
 388                                 break;
 389                         }
 390                 } // while(FLUSHPHASE == gcphase)
 391                 gcphase = FINISHPHASE;
 392                 for(i = 1; i < NUMCORES; ++i) {
 393                         // send gc finish messages to all cores
 394                         send_msg_1(i, GCFINISH);
 395                 }
 396                 return;
 397         } else {
 398                 gc_collect(stackptr);
 399         }
 400         gcflag = false;
 401 }
 402
 403 // enqueue root objs
 404 void tomark(struct garbagelist * stackptr) {
 405         if(MARKPHASE != gcphase) {
 406                 BAMBOO_EXIT(0xb002);
 407         }
 408         gcbusystatus = 1;
 409         // initialize queue
 410         if (gchead==NULL) {
 411                 gcheadindex=0;
 412                 gctailindex=0;
 413                 gctailindex2 = 0;
 414                 gchead=gctail=gctail2=malloc(sizeof(struct pointerblock));
 415         }
 416         int i;
 417         // enqueue current stack
 418         while(stackptr!=NULL) {
 419                 for(i=0; i<stackptr->size; i++) {
 420                         gc_enqueue(stackptr->array[i]);
 421                 }
 422                 stackptr=stackptr->next;
 423         }
 424         // enqueue objectsets
 425         for(i=0; i<NUMCLASSES; i++) {
 426                 struct parameterwrapper ** queues=objectqueues[BAMBOO_NUM_OF_CORE][i];
 427                 int length = numqueues[BAMBOO_NUM_OF_CORE][i];
 428                 for(j = 0; j < length; ++j) {
 429                         struct parameterwrapper * parameter = queues[j];
 430                         struct ObjectHash * set=parameter->objectset;
 431                         struct ObjectNode * ptr=set->listhead;
 432                         while(ptr!=NULL) {
 433                                 gc_enqueue((void *)ptr->key);
 434                                 ptr=ptr->lnext;
 435                         }
 436                 }
 437         }
 438         // euqueue current task descriptor
 439         for(i=0; i<currtpd->numParameters; i++) {
 440                 gc_enqueue(currtpd->parameterArray[i]);
 441         }
 442         // euqueue active tasks
 443         struct genpointerlist * ptr=activetasks->list;
 444         while(ptr!=NULL) {
 445                 struct taskparamdescriptor *tpd=ptr->src;
 446                 int i;
 447                 for(i=0; i<tpd->numParameters; i++) {
 448                         gc_enqueue(tpd->parameterArray[i]);
 449                 }
 450                 ptr=ptr->inext;
 451         }
 452         // enqueue cached transferred obj
 453         struct QueueItem * tmpobjptr =  getHead(&objqueue);
 454         while(tmpobjptr != NULL) {
 455                 struct transObjInfo * objInfo = (struct transObjInfo *)(tmpobjptr->objectptr);
 456                 gc_enqueue(objInfo->objptr);
 457                 getNextQueueItem(tmpobjptr);
 458         }
 459 }
 460
 461 void mark(bool isfirst, struct garbagelist * stackptr) {
 462         if(isfirst) {
 463                 // enqueue root objs
 464                 tomark(stackptr);
 465         }
 466
 467         // mark phase
 468         while(MARKPHASE == gcphase) {
 469                 while(gc_moreItems2()) {
 470                         voit * ptr = gc_dequeue2();
 471                         int size = 0;
 472                         int type = 0;
 473                         if(isLarge(ptr, &type, &size)) {
 474                                 // ptr is a large object
 475                                 struct largeObjItem * loi =
 476                                         (struct largeObjItem *)RUNMALLOC(sizeof(struct largeObjItem));
 477                                 loi->orig = (INTPTR)ptr;
 478                                 loi->dst = (INTPTR)0;
 479                                 loi->length = size;
 480                                 if(lObjList.head == NULL) {
 481                                         lObjList.head = lObjList.tail = loi;
 482                                 } else {
 483                                         lObjList.tail->next = loi;
 484                                         lObjList.tail = loi;
 485                                 }
 486                         } else if (isLocal(ptr)) {
 487                                 // ptr is an active object on this core
 488                                 if(type == -1) {
 489                                         // nothing to do
 490                                 }
 491                                 curr_heaptop += size;
 492                                 // mark this obj
 493                                 ((int *)ptr)[6] = 1;
 494                         }
 495                         // scan all pointers in ptr
 496                         unsigned INTPTR * pointer;
 497                         pointer=pointerarray[type];
 498                         if (pointer==0) {
 499                                 /* Array of primitives */
 500                                 /* Do nothing */
 501                         } else if (((INTPTR)pointer)==1) {
 502                                 /* Array of pointers */
 503                                 struct ArrayObject *ao=(struct ArrayObject *) ptr;
 504                                 int length=ao->___length___;
 505                                 int j;
 506                                 for(j=0; j<length; j++) {
 507                                         void *objptr=((void **)(((char *)&ao->___length___)+sizeof(int)))[j];
 508                                         int host = hostcore(objptr);
 509                                         if(BAMBOO_NUM_OF_CORE == host) {
 510                                                 // on this core
 511                                                 gc_enqueue(objptr);
 512                                         } else {
 513                                                 // send a msg to host informing that objptr is active
 514                                                 send_msg_2(host, GCMARKEDOBJ, objptr);
 515                                                 gcself_numsendobjs++;
 516                                         }
 517                                 }
 518                         } else {
 519                                 INTPTR size=pointer[0];
 520                                 int i;
 521                                 for(i=1; i<=size; i++) {
 522                                         unsigned int offset=pointer[i];
 523                                         void * objptr=*((void **)(((char *)ptr)+offset));
 524                                         int host = hostcore(objptr);
 525                                         if(BAMBOO_NUM_OF_CORE == host) {
 526                                                 // on this core
 527                                                 gc_enqueue(objptr);
 528                                         } else {
 529                                                 // send a msg to host informing that objptr is active
 530                                                 send_msg_2(host, GCMARKEDOBJ, objptr);
 531                                                 gcself_numsendobjs++;
 532                                         }
 533                                 }
 534                         }
 535                 } // while(!isEmpty(gctomark))
 536                 gcbusystatus = false;
 537                 // send mark finish msg to core coordinator
 538                 send_msg_4(STARTUPCORE, GCFINISHMARK, BAMBOO_NUM_OF_CORE,
 539                                        gcself_numsendobjs, gcself_numreceiveobjs);
 540
 541                 if(BAMBOO_NUM_OF_CORE == 0) {
 542                         return;
 543                 }
 544         } // while(MARKPHASE == gcphase)
 545 } // mark()
 546
 547 void compact() {
 548         if(COMPACTPHASE != gcphase) {
 549                 BAMBOO_EXIT(0xb003);
 550         }
 551         curr_heaptop = 0;
 552         struct markedObjItem * moi = mObjList.head;
 553         bool iscopy = true;
 554         while(moi != NULL) {
 555                 if((cinstruction == NULL) || (cinstruction->tomoveobjs == NULL)
 556                                 || (curr_heaptop < cinstruction->tomoveobjs->starts[0])) {
 557                         // objs to compact
 558                         int type = ((int *)(moi->orig))[0];
 559                         int size = 0;
 560                         if(type == -1) {
 561                                 // do nothing
 562                         }
 563                         if(type < NUMCLASSES) {
 564                                 // a normal object
 565                                 size = classsize[type];
 566                                 moi->dst = curr_heaptop;
 567                                 curr_heaptop += size;
 568                                 if(iscopy) {
 569                                         memcpy(moi->dst, moi->orig, size);
 570                                         genputtable(pointertbl, moi->orig, moi->dst);
 571                                 }
 572                         } else {
 573                                 // an array
 574                                 struct ArrayObject *ao=(struct ArrayObject *)ptr;
 575                                 int elementsize=classsize[type];
 576                                 int length=ao->___length___;
 577                                 size=sizeof(struct ArrayObject)+length*elementsize;
 578                                 moi->dst = curr_heaptop;
 579                                 curr_heaptop += size;
 580                                 if(iscopy) {
 581                                         memcpy(moi->dst, moi->orig, size);
 582                                         genputtable(pointertbl, moi->orig, moi->dst);
 583                                 }
 584                         }
 585                 } else {
 586                         iscopy = false;;
 587                 }
 588                 moi = moi->next;
 589         } // while(moi != NULL)
 590         if(moi == NULL) {
 591                 if(cinstruction->incomingobjs != NULL) {
 592                         for(int j = 0; j < cinstruction->incomingobjs->length; j++) {
 593                                 // send messages to corresponding cores to start moving
 594                                 send_msg_2(cinstruction->incomingobjs->dsts[j], GCMOVESTART,
 595                                                        BAMBOO_NUM_OF_CORE);
 596                         }
 597                 }
 598         } else {
 599                 int num_dsts = cinstruction->tomoveobjs->length;
 600                 while(num_dsts > 0) {
 601                         while(!gctomove) {}
 602                         // start moving objects to other cores
 603                         gctomove = 0;
 604                         while(!isEmpty(gcdsts)) {
 605                                 int dst = (int)(getItem(gcdsts));
 606                                 num_dsts--;
 607                                 int j = 0;
 608                                 for(j = 0; j < cinstruction->tomoveobjs->length; j++) {
 609                                         if(dst == cinstruction->tomoveobjs->dsts[j]) {
 610                                                 break;
 611                                         }
 612                                 }
 613                                 INTPTR top = cinstruction->tomoveobjs->dststarts[j];
 614                                 INTPTR start = cinstruction->tomoveobjs->starts[j];
 615                                 INTPTR end = cinstruction->tomoveobjs->ends[j];
 616                                 struct markedObjItem * tomove = getStartItem(moi, start);
 617                                 do {
 618                                         int type = ((int *)(tomove->orig))[0];
 619                                         int size = 0;
 620                                         if(type == -1) {
 621                                                 // do nothing
 622                                         }
 623                                         if(type < NUMCLASSES) {
 624                                                 // a normal object
 625                                                 size = classsize[type];
 626                                                 moi->dst = top;
 627                                                 top += size;
 628                                                 memcpy(moi->dst, moi->orig, size);
 629                                                 genputtable(pointertbl, moi->orig, moi->dst);
 630                                         } else {
 631                                                 // an array
 632                                                 struct ArrayObject *ao=(struct ArrayObject *)ptr;
 633                                                 int elementsize=classsize[type];
 634                                                 int length=ao->___length___;
 635                                                 size=sizeof(struct ArrayObject)+length*elementsize;
 636                                                 moi->dst = top;
 637                                                 top += size;
 638                                                 memcpy(moi->dst, moi->orig, size);
 639                                                 genputtable(pointertbl, moi->orig, moi->dst);
 640                                         }
 641                                         tomove = tomove->next;
 642                                 } while(tomove->orig < end);
 643                         } // while(!isEmpty(gcdsts))
 644                 } // while(num_dsts > 0)
 645         } // if(moi == NULL) else()
 646         if((cinstruction != NULL) && (cinstruction->largeobjs != NULL)) {
 647                 // move all large objects
 648                 do {
 649                         // dequeue the first large obj
 650                         struct largeObjItem * loi = cinstruction->largeobjs;
 651                         cinstruction->largeobjs = loi->next;
 652                         // move this large obj
 653                         memcpy(loi->dst, loi->orig, loi->length);
 654                         genputtable(pointertbl, loi->orig, loi->dst);
 655                         RUNFREE(loi);
 656                 }while(cinstruction->largeobjs != NULL);
 657         }
 658         // send compact finish message to core coordinator
 659         send_msg_2(STARTUPCORE, GCFINISHCOMPACT, BAMBOO_NUM_OF_CORE);
 660
 661 } // compact()
 662
 663 void flush() {
 664         struct markedObjItem * moi = mObjList.head;
 665         while(moi != NULL) {
 666                 void * ptr = moi->dst;
 667                 int type = ((int *)(ptr))[0];
 668                 // scan all pointers in ptr
 669                 unsigned INTPTR * pointer;
 670                 pointer=pointerarray[type];
 671                 if (pointer==0) {
 672                         /* Array of primitives */
 673                         /* Do nothing */
 674                 } else if (((INTPTR)pointer)==1) {
 675                         /* Array of pointers */
 676                         struct ArrayObject *ao=(struct ArrayObject *) ptr;
 677                         int length=ao->___length___;
 678                         int j;
 679                         for(j=0; j<length; j++) {
 680                                 void *objptr=((void **)(((char *)&ao->___length___)+sizeof(int)))[j];
 681                                 // change to new address
 682                                 void *dstptr = gengettable(pointertbl, objptr);
 683                                 if(NULL == dstptr) {
 684                                         // send msg to host core for the mapping info
 685                                         obj2map = (int)objptr;
 686                                         ismapped = false;
 687                                         mappedobj = NULL;
 688                                         send_msg_3(hostcore(objptr), GCMAPREQUEST, (int)objptr,
 689                                                                BAMBOO_NUM_OF_CORE);
 690                                         while(!ismapped) {}
 691                                         dstptr = mappedobj;
 692                                 }
 693                                 ((void **)(((char *)&ao->___length___)+sizeof(int)))[j] = dstptr;
 694                         }
 695                 } else {
 696                         INTPTR size=pointer[0];
 697                         int i;
 698                         for(i=1; i<=size; i++) {
 699                                 unsigned int offset=pointer[i];
 700                                 void * objptr=*((void **)(((char *)ptr)+offset));
 701                                 // change to new address
 702                                 void *dstptr = gengettable(pointertbl, objptr);
 703                                 if(NULL == dstptr) {
 704                                         // send msg to host core for the mapping info
 705                                         obj2map = (int)objptr;
 706                                         ismapped = false;
 707                                         mappedobj = NULL;
 708                                         send_msg_3(hostcore(objptr), GCMAPREQUEST, (int)objptr,
 709                                                                BAMBOO_NUM_OF_CORE);
 710                                         while(!ismapped) {}
 711                                         dstptr = mappedobj;
 712                                 }
 713                                 *((void **)(((char *)ptr)+offset)) = dstptr;
 714                         }
 715                 }
 716                 moi = moi->next;
 717         } // while(moi != NULL)
 718         // send flush finish message to core coordinator
 719         send_msg_2(STARTUPCORE, GCFINISHFLUSH, BAMBOO_NUM_OF_CORE);
 720
 721 } // flush()
 722
 723 void gc_collect(struct garbagelist * stackptr) {
 724         // core collector routine
 725         mark(true, stackptr);
 726         compact();
 727         while(FLUSHPHASE != gcphase) {}
 728         flush();
 729
 730         while(true) {
 731                 if(FINISHPHASE == gcphase) {
 732                         return;
 733                 }
 734         }
 735 }
 736
 737 #endif