Robust/src/Runtime/bamboo/multicoregccompact.c

   1 #ifdef MULTICORE_GC
   2 #include "multicoregccompact.h"
   3 #include "runtime_arch.h"
   4 #include "multicoreruntime.h"
   5 #include "multicoregarbage.h"
   6 #include "markbit.h"
   7 #include "multicoremem_helper.h"
   8
   9 int gc_countRunningCores() {
  10   int count=0;
  11   for(int i = 0; i < NUMCORES4GC; i++) {
  12     if(returnedmem[i]) {
  13       count++;
  14     }
  15   }
  16   return count;
  17 }
  18
  19 void initOrig_Dst(struct moveHelper * orig,struct moveHelper * to) {
  20   // init the dst ptr
  21   to->localblocknum = 0;
  22   BASEPTR(to->base, BAMBOO_NUM_OF_CORE, to->localblocknum);
  23   to->ptr = to->base;
  24   to->bound=to->base+BLOCKSIZE(to->localblocknum);
  25
  26   // init the orig ptr
  27   orig->localblocknum = 0;
  28   orig->ptr=orig->base = to->base;
  29   orig->bound = orig->base + BLOCKSIZE(orig->localblocknum);
  30 }
  31
  32 void getSpaceLocally(struct moveHelper *to) {
  33   //we have space on our core...just keep going
  34   to->localblocknum++;
  35   BASEPTR(to->base,BAMBOO_NUM_OF_CORE, to->localblocknum);
  36   to->ptr=to->base;
  37   to->bound = to->base + BLOCKSIZE(to->localblocknum);
  38 }
  39
  40 //This function is called on the master core only...and typically by
  41 //the message interrupt handler
  42
  43 void handleReturnMem_I(unsigned int cnum, void *heaptop) {
  44   unsigned int blockindex;
  45   BLOCKINDEX(blockindex, heaptop);
  46   unsigned INTPTR localblocknum=GLOBALBLOCK2LOCAL(blockindex);
  47
  48   //this core is done as far as memory usage is concerned
  49   returnedmem[cnum]=0;
  50
  51   struct blockrecord * blockrecord=&allocationinfo.blocktable[blockindex];
  52
  53   blockrecord->status=BS_FREE;
  54   blockrecord->usedspace=(unsigned INTPTR)(heaptop-OFFSET2BASEVA(blockindex)-gcbaseva);
  55   blockrecord->freespace=BLOCKSIZE(localblocknum)-blockrecord->usedspace;
  56   /* Update the lowest free block */
  57   if (blockindex < allocationinfo.lowestfreeblock) {
  58     allocationinfo.lowestfreeblock=blockindex;
  59   }
  60
  61   /* This is our own block...means we should mark other blocks above us as free*/
  62   if (cnum==blockrecord->corenum) {
  63     unsigned INTPTR nextlocalblocknum=localblocknum+1;
  64     for(;nextlocalblocknum<numblockspercore;nextlocalblocknum++) {
  65       unsigned INTPTR blocknum=BLOCKINDEX2(cnum, nextlocalblocknum);
  66       struct blockrecord * nextblockrecord=&allocationinfo.blocktable[blockindex];
  67       nextblockrecord->status=BS_FREE;
  68       nextblockrecord->usedspace=0;
  69       //this is true because this cannot be the lowest block
  70       nextblockrecord->freespace=BLOCKSIZE(1);
  71     }
  72   }
  73 }
  74
  75 void handleReturnMem(unsigned int cnum, void *heaptop) {
  76   BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
  77   handleReturnMem_I(cnum, heaptop);
  78   BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
  79 }
  80
  81 void getSpaceRemotely(struct moveHelper *to, unsigned int minimumbytes) {
  82   //need to get another block from elsewhere
  83   //set flag to wait for memory
  84   if (BAMBOO_NUM_OF_CORE==STARTUPCORE) {
  85     gctomove=false;
  86     BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
  87     void *startaddr=handlegcfinishcompact_I(BAMBOO_NUM_OF_CORE, minimumbytes, gccurr_heaptop);
  88     BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
  89     if (startaddr) {
  90       gcmovestartaddr=startaddr;
  91     } else {
  92       while(!gctomove) ;
  93     }
  94   } else {
  95     gctomove=false;
  96     //send request for memory
  97     send_msg_4(STARTUPCORE,GCFINISHCOMPACT,BAMBOO_NUM_OF_CORE, minimumbytes, gccurr_heaptop);
  98     //wait for flag to be set that we received message
  99     int cc=0;
 100     while(!gctomove)
 101       ;
 102   }
 103
 104   //store pointer
 105   to->ptr = gcmovestartaddr;
 106
 107   //set localblock number to high number to indicate this block isn't local
 108   to->localblocknum = MAXBLOCK;
 109   unsigned int globalblocknum;
 110   BLOCKINDEX(globalblocknum, to->ptr);
 111   to->base = gcbaseva + OFFSET2BASEVA(globalblocknum);
 112   to->bound = gcbaseva + BOUNDPTR(globalblocknum);
 113 }
 114
 115 void getSpace(struct moveHelper *to, unsigned int minimumbytes) {
 116   //need more space to compact into
 117   if (to->localblocknum < gcblock2fill) {
 118     getSpaceLocally(to);
 119   } else {
 120     getSpaceRemotely(to, minimumbytes);
 121   }
 122 }
 123
 124 void compacthelper(struct moveHelper * orig,struct moveHelper * to) {
 125   bool senttopmessage=false;
 126   while(true) {
 127     if ((gccurr_heaptop < ((unsigned INTPTR)(to->bound-to->ptr)))&&!senttopmessage) {
 128       //This block is the last for this core...let the startup know
 129       if (BAMBOO_NUM_OF_CORE==STARTUPCORE) {
 130         handleReturnMem(BAMBOO_NUM_OF_CORE, to->ptr+gccurr_heaptop);
 131       } else {
 132         send_msg_3(STARTUPCORE, GCRETURNMEM, BAMBOO_NUM_OF_CORE, to->ptr+gccurr_heaptop);
 133       }
 134       //Only send the message once
 135       senttopmessage=true;
 136     }
 137     unsigned int minimumbytes=compactblocks(orig, to);
 138     if (orig->ptr==orig->bound) {
 139       //need more data to compact
 140       //increment the core
 141       orig->localblocknum++;
 142       BASEPTR(orig->base,BAMBOO_NUM_OF_CORE, orig->localblocknum);
 143       orig->ptr=orig->base;
 144       orig->bound = orig->base + BLOCKSIZE(orig->localblocknum);
 145       if (orig->base >= gcbaseva+BAMBOO_SHARED_MEM_SIZE)
 146         break;
 147     }
 148     if (minimumbytes!=0) {
 149       getSpace(to, minimumbytes);
 150     }
 151   }
 152
 153   if (BAMBOO_NUM_OF_CORE==STARTUPCORE) {
 154     BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
 155     handlegcfinishcompact_I(BAMBOO_NUM_OF_CORE, 0, 0);
 156     BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
 157   } else {
 158     send_msg_4(STARTUPCORE,GCFINISHCOMPACT,BAMBOO_NUM_OF_CORE, 0, 0);
 159   }
 160 }
 161
 162 void * checkNeighbors_I(int corenum, unsigned INTPTR requiredmem, unsigned INTPTR desiredmem) {
 163   int minblockindex=allocationinfo.lowestfreeblock/NUMCORES4GC;
 164   unsigned INTPTR threshold=(desiredmem<MINMEMORYCHUNKSIZE)? desiredmem: MINMEMORYCHUNKSIZE;
 165   unsigned INTPTR memcheck=requiredmem>threshold?requiredmem:threshold;
 166
 167   for(int i=0;i<NUM_CORES2TEST;i++) {
 168     int neighborcore=core2test[corenum][i];
 169     if (neighborcore!=-1) {
 170       for(block_t lblock=minblockindex;lblock<numblockspercore;lblock++) {
 171         block_t globalblockindex=BLOCKINDEX2(neighborcore, lblock);
 172         struct blockrecord * block=&allocationinfo.blocktable[globalblockindex];
 173         if (block->status==BS_FREE) {
 174           unsigned INTPTR freespace=block->freespace&~BAMBOO_CACHE_LINE_MASK;
 175           if (memcheck<=freespace) {
 176             //we have a block
 177             //mark block as used
 178             block->status=BS_USED;
 179             void *blockptr=OFFSET2BASEVA(globalblockindex)+gcbaseva;
 180             unsigned INTPTR usedspace=((block->usedspace-1)&~BAMBOO_CACHE_LINE_MASK)+BAMBOO_CACHE_LINE_SIZE;
 181             return blockptr+usedspace;
 182           }
 183         }
 184       }
 185     }
 186   }
 187   return NULL;
 188 }
 189
 190 void * globalSearch_I(unsigned int topblock, unsigned INTPTR requiredmem, unsigned INTPTR desiredmem) {
 191   unsigned int firstfree=NOFREEBLOCK;
 192   unsigned INTPTR threshold=(desiredmem<MINMEMORYCHUNKSIZE)? desiredmem: MINMEMORYCHUNKSIZE;
 193   unsigned INTPTR memcheck=requiredmem>threshold?requiredmem:threshold;
 194
 195   for(block_t i=allocationinfo.lowestfreeblock;i<topblock;i++) {
 196     struct blockrecord * block=&allocationinfo.blocktable[i];
 197     if (block->status==BS_FREE) {
 198       if(firstfree==NOFREEBLOCK)
 199         firstfree=i;
 200       unsigned INTPTR freespace=block->freespace&~BAMBOO_CACHE_LINE_MASK;
 201       if (memcheck<=freespace) {
 202         //we have a block
 203         //mark block as used
 204         block->status=BS_USED;
 205         void *blockptr=OFFSET2BASEVA(i)+gcbaseva;
 206         unsigned INTPTR usedspace=((block->usedspace-1)&~BAMBOO_CACHE_LINE_MASK)+BAMBOO_CACHE_LINE_SIZE;
 207         allocationinfo.lowestfreeblock=firstfree;
 208         return blockptr+usedspace;
 209       }
 210     }
 211   }
 212   allocationinfo.lowestfreeblock=firstfree;
 213   return NULL;
 214 }
 215
 216 void handleOneMemoryRequest(int core, unsigned int lowestblock) {
 217   unsigned INTPTR requiredmem=gcrequiredmems[core];
 218   unsigned INTPTR desiredmem=maxusefulmems[core];
 219   block_t firstfree=NOFREEBLOCK;
 220   unsigned INTPTR threshold=(desiredmem<MINMEMORYCHUNKSIZE)? desiredmem: MINMEMORYCHUNKSIZE;
 221   unsigned INTPTR memcheck=requiredmem>threshold?requiredmem:threshold;
 222
 223   for(block_t searchblock=lowestblock;searchblock<GCNUMBLOCK;searchblock++) {
 224     struct blockrecord * block=&allocationinfo.blocktable[searchblock];
 225     if (block->status==BS_FREE) {
 226       if(firstfree==NOFREEBLOCK)
 227         firstfree=searchblock;
 228       unsigned INTPTR freespace=block->freespace&~BAMBOO_CACHE_LINE_MASK;
 229       if (freespace>=memcheck) {
 230         //TODO: should check memory block at same level on our own core...if that works, use it to preserve locality
 231
 232         //we have a block
 233         //mark block as used
 234         block->status=BS_USED;
 235         void *blockptr=OFFSET2BASEVA(searchblock)+gcbaseva;
 236         unsigned INTPTR usedspace=((block->usedspace-1)&~BAMBOO_CACHE_LINE_MASK)+BAMBOO_CACHE_LINE_SIZE;
 237         allocationinfo.lowestfreeblock=firstfree;
 238         //taken care of one block
 239         gcmovepending--;
 240         void *startaddr=blockptr+usedspace;
 241         if(BAMBOO_CHECK_SEND_MODE()) {
 242           cache_msg_2_I(core,GCMOVESTART,startaddr);
 243         } else {
 244           send_msg_2_I(core,GCMOVESTART,startaddr);
 245         }
 246         return;
 247       }
 248     }
 249   }
 250   //this is bad...ran out of memory
 251   BAMBOO_EXIT();
 252 }
 253
 254 void handleMemoryRequests_I() {
 255   unsigned int lowestblock=allocationinfo.lowestfreeblock;
 256   if (lowestblock==NOFREEBLOCK) {
 257     lowestblock=numblockspercore*NUMCORES4GC;
 258   }
 259
 260   for(int i=0;i < NUMCORES4GC; i++) {
 261     if (gcrequiredmems[i]) {
 262       handleOneMemoryRequest(i, lowestblock);
 263       lowestblock=allocationinfo.lowestfreeblock;
 264     }
 265   }
 266 }
 267
 268 /* should be invoked with interrupt turned off */
 269
 270 void * gcfindSpareMem_I(unsigned INTPTR requiredmem, unsigned INTPTR desiredmem,unsigned int requiredcore) {
 271   if (allocationinfo.lowestfreeblock!=NOFREEBLOCK) {
 272     //There are spare blocks
 273     unsigned int topblock=numblockspercore*NUMCORES4GC;
 274     void *memblock;
 275
 276     if (memblock=checkNeighbors_I(requiredcore, requiredmem, desiredmem)) {
 277       return memblock;
 278     } else if (memblock=globalSearch_I(topblock, requiredmem, desiredmem)) {
 279       return memblock;
 280     }
 281   }
 282
 283   // If we cannot find spare mem right now, hold the request
 284   gcrequiredmems[requiredcore] = requiredmem;
 285   maxusefulmems[requiredcore]=desiredmem;
 286   gcmovepending++;
 287
 288   int count=gc_countRunningCores();
 289   if (gcmovepending==count) {
 290     // All cores have stopped...hand out memory as necessary to handle all requests
 291     handleMemoryRequests_I();
 292   }
 293
 294   return NULL;
 295 }
 296
 297 /* This function is performance critical...  spend more time optimizing it */
 298
 299 unsigned int compactblocks(struct moveHelper * orig, struct moveHelper * to) {
 300   void *toptrinit=to->ptr;
 301   void *toptr=toptrinit;
 302   void *tobound=to->bound;
 303   void *origptr=orig->ptr;
 304   void *origbound=orig->bound;
 305   unsigned INTPTR origendoffset=ALIGNTOTABLEINDEX((unsigned INTPTR)(origbound-gcbaseva));
 306   unsigned int objlength;
 307   while(origptr<origbound) {
 308     //Try to skip over stuff fast first
 309     unsigned INTPTR offset=(unsigned INTPTR) (origptr-gcbaseva);
 310     unsigned INTPTR arrayoffset=ALIGNTOTABLEINDEX(offset);
 311     if (!gcmarktbl[arrayoffset]) {
 312       do {
 313         arrayoffset++;
 314         if (arrayoffset>=origendoffset) {
 315           //finished with block...
 316           origptr=origbound;
 317           to->ptr=toptr;
 318           orig->ptr=origptr;
 319           gccurr_heaptop-=(unsigned INTPTR)(toptr-toptrinit);
 320           return 0;
 321         }
 322       } while(!gcmarktbl[arrayoffset]);
 323       origptr=CONVERTTABLEINDEXTOPTR(arrayoffset);
 324     }
 325
 326     //Scan more carefully next
 327     objlength=getMarkedLength(origptr);
 328
 329
 330     if (objlength!=NOTMARKED) {
 331       unsigned int length=ALIGNSIZETOBYTES(objlength);
 332       void *endtoptr=toptr+length;
 333       if (endtoptr>tobound) {
 334         gccurr_heaptop-=(unsigned INTPTR)(toptr-toptrinit);
 335         to->ptr=tobound;
 336         orig->ptr=origptr;
 337         return length;
 338       }
 339       //good to move objects and update pointers
 340       gcmappingtbl[OBJMAPPINGINDEX(origptr)]=toptr;
 341       origptr+=length;
 342       toptr=endtoptr;
 343     } else
 344       origptr+=ALIGNMENTSIZE;
 345   }
 346   to->ptr=toptr;
 347   orig->ptr=origptr;
 348   return 0;
 349 }
 350
 351 void compact() {
 352   BAMBOO_ASSERT(COMPACTPHASE == gc_status_info.gcphase);
 353
 354   // initialize structs for compacting
 355   struct moveHelper orig={0,NULL,NULL,0,NULL,0,0,0,0};
 356   struct moveHelper to={0,NULL,NULL,0,NULL,0,0,0,0};
 357   initOrig_Dst(&orig, &to);
 358
 359   CACHEADAPT_SAMPLING_DATA_REVISE_INIT(&orig, &to);
 360
 361   compacthelper(&orig, &to);
 362 }
 363
 364 void master_compact() {
 365   // predict number of blocks to fill for each core
 366   numblockspercore = loadbalance()+1;
 367
 368   GC_PRINTF("mark phase finished \n");
 369
 370   gc_resetCoreStatus();
 371   //initialize local data structures first....we don't want remote requests messing data up
 372   unsigned int initblocks=numblockspercore*NUMCORES4GC;
 373   allocationinfo.lowestfreeblock=NOFREEBLOCK;
 374
 375   //assigned blocks
 376   for(int i=0;i<initblocks;i++) {
 377     allocationinfo.blocktable[i].status=BS_USED;
 378   }
 379
 380   //free blocks
 381   for(int i=initblocks;i<GCNUMBLOCK;i++) {
 382     allocationinfo.blocktable[i].status=BS_FREE;
 383     allocationinfo.blocktable[i].usedspace=0;
 384     //this is true because all cores have at least one block already...
 385     allocationinfo.blocktable[i].freespace=BLOCKSIZE(1);
 386   }
 387
 388   //start all of the cores
 389   for(int i = 0; i < NUMCORES4GC; i++) {
 390     // init some data strutures for compact phase
 391     gcrequiredmems[i] = 0;
 392     gccorestatus[i] = 1;
 393     returnedmem[i] = 1;
 394     //send start compact messages to all cores
 395     if(i != STARTUPCORE) {
 396       send_msg_2(i, GCSTARTCOMPACT, numblockspercore);
 397     } else {
 398       gcblock2fill = numblockspercore;
 399     }
 400   }
 401   GCPROFILE_ITEM();
 402   // compact phase
 403   compact();
 404   /* wait for all cores to finish compacting */
 405   tprintf("MASTER WAITING\n");
 406
 407
 408   while(!gc_checkCoreStatus())
 409     ;
 410
 411   tprintf("POST_WAIT\n");
 412   GCPROFILE_ITEM();
 413
 414   //just in case we didn't get blocks back...
 415   if (allocationinfo.lowestfreeblock==NOFREEBLOCK)
 416     allocationinfo.lowestfreeblock=numblockspercore*NUMCORES4GC;
 417
 418   GC_PRINTF("compact phase finished \n");
 419 }
 420
 421 #endif // MULTICORE_GC