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 *currtpd;
  11
  12 INTPTR curr_heaptop = 0;
  13
  14 bool isLarge(void * ptr, int * ttype, int * tsize) {
  15         // check if a pointer is referring to a large object
  16         int type = ((int *)ptr)[0];
  17         int size = 0;
  18         if(type < NUMCLASSES) {
  19                 // a normal object
  20                 size = classsize[type];
  21         } else {
  22                 // an array
  23                 struct ArrayObject *ao=(struct ArrayObject *)ptr;
  24                 int elementsize=classsize[type];
  25                 int length=ao->___length___;
  26                 size=sizeof(struct ArrayObject)+length*elementsize;
  27         }
  28         *ttype = type;
  29         *tsize = size;
  30         return(!isLocal(ptr + size));
  31 }
  32
  33 int hostcore(void * ptr) {
  34         // check the host core of ptr
  35         int host = 0;
  36         int x = 0;
  37         int y = 0;
  38         RESIDECORE(ptr, &x, &y);
  39         host = (x == 0)?(x * bamboo_height + y) : (x * bamboo_height + y - 2);
  40         return host;
  41 }
  42
  43 bool isLocal(void * ptr) {
  44         // check if a pointer is in shared heap on this core
  45         return hostcore(ptr) == BAMBOO_NUM_OF_CORE;
  46 }
  47
  48 void transferMarkResults() {
  49         // TODO, need distiguish between send and cache
  50         // invoked inside interruptiong handler
  51 }
  52
  53 void checkMarkStatue() {
  54         if((!gcwaitconfirm) ||
  55                         (gcwaitconfirm && (gcnumconfirm == 0))) {
  56                 BAMBOO_START_CRITICAL_SECTION_STATUS();
  57                 gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
  58                 gcnumsendobjs[BAMBOO_NUM_OF_CORE] = gcself_numsendobjs;
  59                 gcnumreceiveobjs[BAMBOO_NUM_OF_CORE] = gcself_numreceiveobjs;
  60                 // check the status of all cores
  61                 bool allStall = true;
  62                 for(i = 0; i < NUMCORES; ++i) {
  63                         if(gccorestatus[i] != 0) {
  64                                 allStall = false;
  65                                 break;
  66                         }
  67                 }
  68                 if(allStall) {
  69                         // check if the sum of send objs and receive obj are the same
  70                         // yes->check if the info is the latest; no->go on executing
  71                         int sumsendobj = 0;
  72                         for(i = 0; i < NUMCORES; ++i) {
  73                                 sumsendobj += gcnumsendobjs[i];
  74                         }
  75                         for(i = 0; i < NUMCORES; ++i) {
  76                                 sumsendobj -= gcnumreceiveobjs[i];
  77                         }
  78                         if(0 == sumsendobj) {
  79                                 if(!gcwaitconfirm) {
  80                                         // the first time found all cores stall
  81                                         // send out status confirm msg to all other cores
  82                                         // reset the corestatus array too
  83                                         gccorestatus[BAMBOO_NUM_OF_CORE] = 1;
  84                                         gcwaitconfirm = true;
  85                                         gcnumconfirm = NUMCORES - 1;
  86                                         for(i = 1; i < NUMCORES; ++i) {
  87                                                 gccorestatus[i] = 1;
  88                                                 // send mark phase finish confirm request msg to core i
  89                                                 send_msg_1(i, GCMARKCONFIRM);
  90                                         }
  91                                 } else {
  92                                         // all the core status info are the latest
  93                                         // stop mark phase
  94                                         gcphase = COMPACTPHASE;
  95                                         // restore the gcstatus for all cores
  96                                         for(i = 0; i < NUMCORES; ++i) {
  97                                                 gccorestatus[i] = 1;
  98                                         }
  99                                 } // if(!gcwautconfirm) else()
 100                         } // if(0 == sumsendobj)
 101                 } // if(allStall)
 102                 BAMBOO_CLOSE_CRITICAL_SECTION_STATUS();
 103         } // if((!gcwaitconfirm)...
 104 }
 105
 106 void gc() {
 107         // check if do gc
 108         if(!gcflag) {
 109                 return;
 110         } else {
 111                 // do gc
 112                 gcflag = false;
 113         }
 114
 115         // TODO, preparation
 116
 117         // core coordinator routine
 118         if(0 == BAMBOO_NUM_OF_CORE) {
 119                 int i = 0;
 120                 gcwaitconfirm = false;
 121                 gcwaitconfirm = 0;
 122                 gcphase = MARKPHASE;
 123                 for(i = 1; i < NUMCORES - 1; i++) {
 124                         // send GC start messages to all cores
 125                         send_msg_1(i, GCSTART);
 126                 }
 127                 bool isfirst = true;
 128                 bool allStall = false;
 129
 130                 // mark phase
 131                 while(MARKPHASE == gcphase) {
 132                         mark(isfirst);
 133                         if(isfirst) {
 134                                 isfirst = false;
 135                         }
 136
 137                         // check gcstatus
 138                         checkMarkStatue();
 139                 }  // while(MARKPHASE == gcphase)
 140                 // send msgs to all cores requiring large objs info
 141                 gcnumconfirm = NUMCORES - 1;
 142                 for(i = 1; i < NUMCORES; ++i) {
 143                         send_msg_1(i, GCLOBJREQUEST);
 144                 }
 145                 while(gcnumconfirm != 0) {} // wait for responses
 146                 // TODO compute load balance
 147
 148                 // TODO cache all large objects
 149                 for(i = 1; i < NUMCORES; ++i) {
 150                         //TODO send start compact messages to all cores
 151
 152                 }
 153
 154                 // compact phase
 155                 compact();
 156                 gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
 157                 while(COMPACTPHASE == gcphase) {
 158                         // check the status of all cores
 159                         allStall = true;
 160                         for(i = 0; i < NUMCORES; ++i) {
 161                                 if(gccorestatus[i] != 0) {
 162                                         allStall = false;
 163                                         break;
 164                                 }
 165                         }
 166                         if(allStall) {
 167                                 // restore the gcstatus of all cores
 168                                 for(i = 0; i < NUMCORES; ++i) {
 169                                         gccorestatus[i] = 1;
 170                                 }
 171                                 break;
 172                         }
 173                 } // while(COMPACTPHASE == gcphase)
 174                 // TODO merge all mapping information
 175
 176                 gcphase = FLUSHPHASE;
 177                 for(i = 1; i < NUMCORES; ++i) {
 178                         // send start flush messages to all cores
 179                         send_msg_1(i, GCSTARTFLUSH);
 180                 }
 181
 182                 // flush phase
 183                 flush();
 184                 gccorestatus[BAMBOO_NUM_OF_CORE] = 0;
 185                 while(FLUSHPHASE == gcphase) {
 186                         // check the status of all cores
 187                         allStall = true;
 188                         for(i = 0; i < NUMCORES; ++i) {
 189                                 if(gccorestatus[i] != 0) {
 190                                         allStall = false;
 191                                         break;
 192                                 }
 193                         }
 194                         if(allStall) {
 195                                 break;
 196                         }
 197                 } // while(FLUSHPHASE == gcphase)
 198                 gcphase = FINISHPHASE;
 199                 for(i = 1; i < NUMCORES; ++i) {
 200                         // send gc finish messages to all cores
 201                         send_msg_1(i, GCFINISH);
 202                 }
 203                 return;
 204         } else {
 205                 gc_collect();
 206         }
 207 }
 208
 209 void mark(bool isfirst) {
 210         if(isfirst) {
 211                 if(MARKPHASE != gcphase) {
 212                         BAMBOO_EXIT(0xb002);
 213                 }
 214                 gcbusystatus = 1;
 215                 // initialize gctomark queue
 216                 while(!isEmpty(gctomark)) {
 217                         getItem(gctomark);
 218                 }
 219                 // enqueue current stack  TODO
 220
 221                 // enqueue objectsets
 222                 int i;
 223                 for(i=0; i<NUMCLASSES; i++) {
 224                         struct parameterwrapper ** queues=objectqueues[BAMBOO_NUM_OF_CORE][i];
 225                         int length = numqueues[BAMBOO_NUM_OF_CORE][i];
 226                         for(j = 0; j < length; ++j) {
 227                                 struct parameterwrapper * parameter = queues[j];
 228                                 struct ObjectHash * set=parameter->objectset;
 229                                 struct ObjectNode * ptr=set->listhead;
 230                                 while(ptr!=NULL) {
 231                                         void *orig=(void *)ptr->key;
 232                                         addNewItem(gctomark, orig);
 233                                         ptr=ptr->lnext;
 234                                 }
 235                         }
 236                 }
 237                 // euqueue current task descriptor
 238                 for(i=0; i<currtpd->numParameters; i++) {
 239                         void *orig=currtpd->parameterArray[i];
 240                         addNewItem(gctomark, orig);
 241                 }
 242                 // euqueue active tasks
 243                 struct genpointerlist * ptr=activetasks->list;
 244                 while(ptr!=NULL) {
 245                         struct taskparamdescriptor *tpd=ptr->src;
 246                         int i;
 247                         for(i=0; i<tpd->numParameters; i++) {
 248                                 void * orig=tpd->parameterArray[i];
 249                                 addNewItem(gctomark, orig);
 250                         }
 251                         ptr=ptr->inext;
 252                 }
 253         }
 254
 255         // mark phase
 256         while(MARKPHASE == gcphase) {
 257                 while(!isEmpty(gctomark)) {
 258                         voit * ptr = getItem(gctomark);
 259                         int size = 0;
 260                         int type = 0;
 261                         if(isLarge(ptr, &type, &size)) {
 262                                 // ptr is a large object
 263                                 // TODO
 264 /*                              struct largeObjItem * loi =
 265                                         (struct largeObjItem *)RUNMALLOC(sizeof(struct largeObjItem));
 266                                 loi->orig = (INTPTR)ptr;
 267                                 loi->dst = (INTPTR)0;
 268                                 loi->length = size;
 269                                 if(lObjList.head == NULL) {
 270                                         lObjList.head = lObjList.tail = loi;
 271                                 } else {
 272                                         lObjList.tail->next = loi;
 273                                         lObjList.tail = loi;
 274                                 }*/
 275                         } else if (isLocal(ptr)) {
 276                                 // ptr is an active object on this core
 277                                 if(type == -1) {
 278                                         // nothing to do
 279                                 }
 280                                 curr_heaptop += size;
 281
 282                         }
 283                         // scan all pointers in ptr
 284                         unsigned INTPTR * pointer;
 285                         pointer=pointerarray[type];
 286                         if (pointer==0) {
 287                                 /* Array of primitives */
 288                                 /* Do nothing */
 289                         } else if (((INTPTR)pointer)==1) {
 290                                 /* Array of pointers */
 291                                 struct ArrayObject *ao=(struct ArrayObject *) ptr;
 292                                 int length=ao->___length___;
 293                                 int j;
 294                                 for(j=0; j<length; j++) {
 295                                         void *objptr=((void **)(((char *)&ao->___length___)+sizeof(int)))[j];
 296                                         int host = hostcore(objptr);
 297                                         if(BAMBOO_NUM_OF_CORE == host) {
 298                                                 // on this core
 299                                                 addNewItem(gctomark, objptr);
 300                                         } else {
 301                                                 // send a msg to host informing that objptr is active
 302                                                 send_msg_2(host, GCMARKEDOBJ, objptr);
 303                                                 gcself_numsendobjs++;
 304                                         }
 305                                 }
 306                         } else {
 307                                 INTPTR size=pointer[0];
 308                                 int i;
 309                                 for(i=1; i<=size; i++) {
 310                                         unsigned int offset=pointer[i];
 311                                         void * objptr=*((void **)(((char *)ptr)+offset));
 312                                         int host = hostcore(objptr);
 313                                         if(BAMBOO_NUM_OF_CORE == host) {
 314                                                 // on this core
 315                                                 addNewItem(gctomark, objptr);
 316                                         } else {
 317                                                 // send a msg to host informing that objptr is active
 318                                                 send_msg_2(host, GCMARKEDOBJ, objptr);
 319                                                 gcself_numsendobjs++;
 320                                         }
 321                                 }
 322                         }
 323                 } // while(!isEmpty(gctomark))
 324                 gcbusystatus = false;
 325                 // send mark finish msg to core coordinator
 326                 send_msg_4(STARTUPCORE, GCFINISHMARK, BAMBOO_NUM_OF_CORE, gcself_numsendobjs, gcself_numreceiveobjs);
 327
 328                 if(BAMBOO_NUM_OF_CORE == 0) {
 329                         return;
 330                 }
 331         } // while(MARKPHASE == gcphase)
 332 } // mark()
 333
 334 void compact() {
 335         if(COMPACTPHASE != gcphase) {
 336                 BAMBOO_EXIT(0xb003);
 337         }
 338         curr_heaptop = 0;
 339         struct markedObjItem * moi = mObjList.head;
 340         bool iscopy = true;
 341         while(moi != NULL) {
 342                 if((cinstruction == NULL) || (cinstruction->tomoveobjs == NULL)
 343                                 || (curr_heaptop < cinstruction->tomoveobjs->starts[0])) {
 344                         // objs to compact
 345                         int type = ((int *)(moi->orig))[0];
 346                         int size = 0;
 347                         if(type == -1) {
 348                                 // do nothing
 349                         }
 350                         if(type < NUMCLASSES) {
 351                                 // a normal object
 352                                 size = classsize[type];
 353                                 moi->dst = curr_heaptop;
 354                                 curr_heaptop += size;
 355                                 if(iscopy) {
 356                                         memcpy(moi->dst, moi->orig, size);
 357                                         genputtable(pointertbl, moi->orig, moi->dst);
 358                                 }
 359                         } else {
 360                                 // an array
 361                                 struct ArrayObject *ao=(struct ArrayObject *)ptr;
 362                                 int elementsize=classsize[type];
 363                                 int length=ao->___length___;
 364                                 size=sizeof(struct ArrayObject)+length*elementsize;
 365                                 moi->dst = curr_heaptop;
 366                                 curr_heaptop += size;
 367                                 if(iscopy) {
 368                                         memcpy(moi->dst, moi->orig, size);
 369                                         genputtable(pointertbl, moi->orig, moi->dst);
 370                                 }
 371                         }
 372                 } else {
 373                         iscopy = false;;
 374                 }
 375                 moi = moi->next;
 376         } // while(moi != NULL)
 377         if(moi == NULL) {
 378                 if(cinstruction->incomingobjs != NULL) {
 379                         for(int j = 0; j < cinstruction->incomingobjs->length; j++) {
 380                                 // send messages to corresponding cores to start moving
 381                                 send_msg_2(cinstruction->incomingobjs->dsts[j], GCMOVESTART,
 382                                                        BAMBOO_NUM_OF_CORE);
 383                         }
 384                 }
 385         } else {
 386                 int num_dsts = cinstruction->tomoveobjs->length;
 387                 while(num_dsts > 0) {
 388                         while(!gctomove) {}
 389                         // start moving objects to other cores
 390                         gctomove = 0;
 391                         while(!isEmpty(gcdsts)) {
 392                                 int dst = (int)(getItem(gcdsts));
 393                                 num_dsts--;
 394                                 int j = 0;
 395                                 for(j = 0; j < cinstruction->tomoveobjs->length; j++) {
 396                                         if(dst == cinstruction->tomoveobjs->dsts[j]) {
 397                                                 break;
 398                                         }
 399                                 }
 400                                 INTPTR top = cinstruction->tomoveobjs->dststarts[j];
 401                                 INTPTR start = cinstruction->tomoveobjs->starts[j];
 402                                 INTPTR end = cinstruction->tomoveobjs->ends[j];
 403                                 struct markedObjItem * tomove = getStartItem(moi, start);
 404                                 do {
 405                                         int type = ((int *)(tomove->orig))[0];
 406                                         int size = 0;
 407                                         if(type == -1) {
 408                                                 // do nothing
 409                                         }
 410                                         if(type < NUMCLASSES) {
 411                                                 // a normal object
 412                                                 size = classsize[type];
 413                                                 moi->dst = top;
 414                                                 top += size;
 415                                                 memcpy(moi->dst, moi->orig, size);
 416                                                 genputtable(pointertbl, moi->orig, moi->dst);
 417                                         } else {
 418                                                 // an array
 419                                                 struct ArrayObject *ao=(struct ArrayObject *)ptr;
 420                                                 int elementsize=classsize[type];
 421                                                 int length=ao->___length___;
 422                                                 size=sizeof(struct ArrayObject)+length*elementsize;
 423                                                 moi->dst = top;
 424                                                 top += size;
 425                                                 memcpy(moi->dst, moi->orig, size);
 426                                                 genputtable(pointertbl, moi->orig, moi->dst);
 427                                         }
 428                                         tomove = tomove->next;
 429                                 } while(tomove->orig < end);
 430                         } // while(!isEmpty(gcdsts))
 431                 } // while(num_dsts > 0)
 432         } // if(moi == NULL) else()
 433         if((cinstruction != NULL) && (cinstruction->largeobjs != NULL)) {
 434                 // move all large objects
 435                 do {
 436                         // dequeue the first large obj
 437                         struct largeObjItem * loi = cinstruction->largeobjs;
 438                         cinstruction->largeobjs = loi->next;
 439                         // move this large obj
 440                         memcpy(loi->dst, loi->orig, loi->length);
 441                         genputtable(pointertbl, loi->orig, loi->dst);
 442                         RUNFREE(loi);
 443                 }while(cinstruction->largeobjs != NULL);
 444         }
 445         // send compact finish message to core coordinator
 446         send_msg_2(STARTUPCORE, GCFINISHCOMPACT, BAMBOO_NUM_OF_CORE);
 447
 448 } // compact()
 449
 450 void flush() {
 451         struct markedObjItem * moi = mObjList.head;
 452         while(moi != NULL) {
 453                 void * ptr = moi->dst;
 454                 int type = ((int *)(ptr))[0];
 455                 // scan all pointers in ptr
 456                 unsigned INTPTR * pointer;
 457                 pointer=pointerarray[type];
 458                 if (pointer==0) {
 459                         /* Array of primitives */
 460                         /* Do nothing */
 461                 } else if (((INTPTR)pointer)==1) {
 462                         /* Array of pointers */
 463                         struct ArrayObject *ao=(struct ArrayObject *) ptr;
 464                         int length=ao->___length___;
 465                         int j;
 466                         for(j=0; j<length; j++) {
 467                                 void *objptr=((void **)(((char *)&ao->___length___)+sizeof(int)))[j];
 468                                 // change to new address
 469                                 void *dstptr = gengettable(pointertbl, objptr);
 470                                 if(NULL == dstptr) {
 471                                         // send msg to host core for the mapping info
 472                                         obj2map = (int)objptr;
 473                                         ismapped = false;
 474                                         mappedobj = NULL;
 475                                         send_msg_3(hostcore(objptr), GCMAPREQUEST, (int)objptr,
 476                                                                BAMBOO_NUM_OF_CORE);
 477                                         while(!ismapped) {}
 478                                         dstptr = mappedobj;
 479                                 }
 480                                 ((void **)(((char *)&ao->___length___)+sizeof(int)))[j] = dstptr;
 481                         }
 482                 } else {
 483                         INTPTR size=pointer[0];
 484                         int i;
 485                         for(i=1; i<=size; i++) {
 486                                 unsigned int offset=pointer[i];
 487                                 void * objptr=*((void **)(((char *)ptr)+offset));
 488                                 // change to new address
 489                                 void *dstptr = gengettable(pointertbl, objptr);
 490                                 if(NULL == dstptr) {
 491                                         // send msg to host core for the mapping info
 492                                         obj2map = (int)objptr;
 493                                         ismapped = false;
 494                                         mappedobj = NULL;
 495                                         send_msg_3(hostcore(objptr), GCMAPREQUEST, (int)objptr,
 496                                                                BAMBOO_NUM_OF_CORE);
 497                                         while(!ismapped) {}
 498                                         dstptr = mappedobj;
 499                                 }
 500                                 *((void **)(((char *)ptr)+offset)) = dstptr;
 501                         }
 502                 }
 503                 moi = moi->next;
 504         } // while(moi != NULL)
 505         // send flush finish message to core coordinator
 506         send_msg_2(STARTUPCORE, GCFINISHFLUSH, BAMBOO_NUM_OF_CORE);
 507
 508 } // flush()
 509
 510 void gc_collect() {
 511         // core collector routine
 512         // change to UDN1
 513         bme_install_interrupt_handler(INT_UDN_AVAIL, gc_msghandler);
 514 #ifdef DEBUG
 515         tprintf("Process %x(%d): change udn interrupt handler\n", BAMBOO_NUM_OF_CORE,
 516                         BAMBOO_NUM_OF_CORE);
 517 #endif
 518         __insn_mtspr(SPR_UDN_TAG_1, UDN1_DEMUX_TAG);
 519         // enable udn interrupts
 520         //__insn_mtspr(SPR_INTERRUPT_MASK_RESET_2_1, INT_MASK_HI(INT_UDN_AVAIL));
 521         __insn_mtspr(SPR_UDN_AVAIL_EN, (1<<1));
 522         BAMBOO_CLOSE_CRITICAL_SECTION_MSG();
 523
 524         lObjList.head = NULL;
 525         lObjList.tail = NULL;
 526         mObjList.head = NULL;
 527         mObjList.tail = NULL;
 528         mark(true);
 529         compact();
 530         while(FLUSHPHASE != gcphase) {}
 531         flush();
 532
 533         while(true) {
 534                 if(FINISHPHASE == gcphase) {
 535                         // change to UDN0
 536                         bme_install_interrupt_handler(INT_UDN_AVAIL, udn_inter_handle);
 537 #ifdef DEBUG
 538                         tprintf("Process %x(%d): change back udn interrupt handler\n", BAMBOO_NUM_OF_CORE,
 539                                         BAMBOO_NUM_OF_CORE);
 540 #endif
 541                         __insn_mtspr(SPR_UDN_TAG_0, UDN0_DEMUX_TAG);
 542                         // enable udn interrupts
 543                         //__insn_mtspr(SPR_INTERRUPT_MASK_RESET_2_1, INT_MASK_HI(INT_UDN_AVAIL));
 544                         __insn_mtspr(SPR_UDN_AVAIL_EN, (1<<0));
 545                         BAMBOO_START_CRITICAL_SECTION_MSG();
 546
 547                         return;
 548                 }
 549         }
 550 }
 551
 552 #endif