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(gccorestatus[i] != 0) {
  13       count++;
  14     }
  15   }
  16   return count;
  17 }
  18
  19 bool gc_checkCoreStatus() {
  20   for(int i = 0; i < NUMCORES4GC; ++i) {
  21     if(gccorestatus[i] != 0) {
  22       return false;
  23     }
  24   }
  25   return true;
  26 }
  27
  28 void gc_resetCoreStatus() {
  29   for(int i = 0; i < NUMCORES4GC; ++i) {
  30     gccorestatus[i] = 1;
  31   }
  32 }
  33
  34 void initOrig_Dst(struct moveHelper * orig,struct moveHelper * to) {
  35   // init the dst ptr
  36   to->localblocknum = 0;
  37   BASEPTR(to->base, BAMBOO_NUM_OF_CORE, to->localblocknum);
  38   to->ptr = to->base;
  39   to->bound=to->base+BLOCKSIZE(to->localblocknum);
  40
  41   // init the orig ptr
  42   orig->localblocknum = 0;
  43   orig->ptr=orig->base = to->base;
  44   orig->bound = orig->base + BLOCKSIZE(orig->localblocknum);
  45 }
  46
  47 void getSpaceLocally(struct moveHelper *to) {
  48   //we have space on our core...just keep going
  49   to->localblocknum++;
  50   BASEPTR(to->base,BAMBOO_NUM_OF_CORE, to->localblocknum);
  51   to->ptr=to->base;
  52   to->bound = to->base + BLOCKSIZE(to->localblocknum);
  53 }
  54
  55 void getSpaceRemotely(struct moveHelper *to, unsigned int minimumbytes) {
  56   //need to get another block from elsewhere
  57   //set flag to wait for memory
  58   gctomove=false;
  59   //send request for memory
  60   send_msg_3(STARTUPCORE,GCFINISHCOMPACT,BAMBOO_NUM_OF_CORE, minimumbytes);
  61   //wait for flag to be set that we received message
  62   while(!gctomove) ;
  63
  64   //store pointer
  65   to->ptr = gcmovestartaddr;
  66
  67   //set localblock number to high number to indicate this block isn't local
  68   to->localblocknum = MAXBLOCK;
  69   unsigned int globalblocknum;
  70   BLOCKINDEX(globalblocknum, to->ptr);
  71   to->base = gcbaseva + OFFSET2BASEVA(globalblocknum);
  72   to->bound = gcbaseva + BOUNDPTR(globalblocknum);
  73 }
  74
  75 void getSpace(struct moveHelper *to, unsigned int minimumbytes) {
  76   //need more space to compact into
  77   if (to->localblocknum < gcblock2fill) {
  78     getSpaceLocally(to);
  79   } else {
  80     getSpaceRemotely(to, minimumbytes);
  81   }
  82 }
  83
  84 void compacthelper(struct moveHelper * orig,struct moveHelper * to) {
  85   bool senttopmessage=false;
  86   while(true) {
  87     if ((gccurr_heaptop < ((unsigned INTPTR)(to->bound-to->ptr)))&&!senttopmessage) {
  88       //This block is the last for this core...let the startup know
  89       send_msg_3(STARTUPCORE, GCRETURNMEM, BAMBOO_NUM_OF_CORE, to->ptr+gccurr_heaptop);
  90       //Only send the message once
  91       senttopmessage=true;
  92     }
  93
  94     unsigned int minimumbytes=compactblocks(orig, to);
  95     if (orig->ptr==orig->bound) {
  96       //need more data to compact
  97       //increment the core
  98       orig->localblocknum++;
  99       BASEPTR(orig->base,BAMBOO_NUM_OF_CORE, orig->localblocknum);
 100       orig->ptr=orig->base;
 101       orig->bound = orig->base + BLOCKSIZE(orig->localblocknum);
 102       if (orig->base >= gcbaseva+BAMBOO_SHARED_MEM_SIZE)
 103         break;
 104     }
 105     if (minimumbytes!=0) {
 106       getSpace(to, minimumbytes);
 107     }
 108   }
 109
 110   send_msg_3(STARTUPCORE,GCFINISHCOMPACT,BAMBOO_NUM_OF_CORE, 0);
 111 }
 112
 113 void * checkNeighbors(int corenum, unsigned INTPTR requiredmem) {
 114   int minblockindex=allocationinfo.lowestfreeblock/NUMCORES4GC;
 115   for(int i=0;i<NUM_CORES2TEST;i++) {
 116     int neighborcore=core2test[corenum][i];
 117     if (neighborcore!=-1) {
 118       for(block_t lblock=minblockindex;lblock<numblockspercore;lblock++) {
 119         block_t globalblockindex=BLOCKINDEX2(neighborcore, lblock);
 120         struct blockrecord * block=&allocationinfo.blocktable[globalblockindex];
 121         if (block->status==BS_FREE) {
 122           unsigned INTPTR freespace=block->freespace&~BAMBOO_CACHE_LINE_MASK;
 123           if (requiredmem<freespace) {
 124             //we have a block
 125             //mark block as used
 126             block->status=BS_USED;
 127             void *blockptr=OFFSET2BASEVA(globalblockindex)+gcbaseva;
 128             unsigned INTPTR usedspace=((block->usedspace-1)&~BAMBOO_CACHE_LINE_MASK)+BAMBOO_CACHE_LINE_SIZE;
 129             return blockptr+usedspace;
 130           }
 131         }
 132       }
 133     }
 134   }
 135   return NULL;
 136 }
 137
 138 void * globalSearch(unsigned int topblock, unsigned INTPTR requiredmem) {
 139   unsigned int firstfree=NOFREEBLOCK;
 140   for(block_t i=allocationinfo.lowestfreeblock;i<topblock;i++) {
 141     struct blockrecord * block=&allocationinfo.blocktable[i];
 142     if (block->status==BS_FREE) {
 143       if(firstfree==NOFREEBLOCK)
 144         firstfree=i;
 145       unsigned INTPTR freespace=block->freespace&~BAMBOO_CACHE_LINE_MASK;
 146       if (requiredmem<freespace) {
 147         //we have a block
 148         //mark block as used
 149         block->status=BS_USED;
 150         void *blockptr=OFFSET2BASEVA(i)+gcbaseva;
 151         unsigned INTPTR usedspace=((block->usedspace-1)&~BAMBOO_CACHE_LINE_MASK)+BAMBOO_CACHE_LINE_SIZE;
 152         allocationinfo.lowestfreeblock=firstfree;
 153         return blockptr+usedspace;
 154       }
 155     }
 156   }
 157   allocationinfo.lowestfreeblock=firstfree;
 158   return NULL;
 159 }
 160
 161 /* should be invoked with interrupt turned off */
 162
 163 void * gcfindSpareMem_I(unsigned INTPTR requiredmem,unsigned int requiredcore) {
 164   if (allocationinfo.lowestfreeblock!=NOFREEBLOCK) {
 165     //There are spare blocks
 166     unsigned int topblock=numblockspercore*NUMCORES4GC;
 167     void *memblock;
 168
 169     if (memblock=checkNeighbors(requiredcore, requiredmem)) {
 170       return memblock;
 171     } else if (memblock=globalSearch(topblock, requiredmem)) {
 172       return memblock;
 173     }
 174   }
 175
 176   // If we cannot find spare mem right now, hold the request
 177   gcrequiredmems[requiredcore] = requiredmem;
 178   gcmovepending++;
 179
 180   int count=gc_countRunningCores();
 181   if (gcmovepending==count) {
 182     // All cores have stopped...hand out memory as necessary to handle all requests
 183
 184   }
 185
 186   return NULL;
 187 }
 188
 189 bool gcfindSpareMem(unsigned int requiredmem,unsigned int requiredcore) {
 190   BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
 191   bool retval=gcfindSpareMem_I(requiredmem, requiredcore);
 192   BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
 193   return retval;
 194 }
 195
 196 /* This function is performance critical...  spend more time optimizing it */
 197
 198 unsigned int compactblocks(struct moveHelper * orig, struct moveHelper * to) {
 199   void *toptrinit=to->ptr;
 200   void *toptr=toptr;
 201   void *tobound=to->bound;
 202   void *origptr=orig->ptr;
 203   void *origbound=orig->bound;
 204   unsigned INTPTR origendoffset=ALIGNTOTABLEINDEX((unsigned INTPTR)(origbound-gcbaseva));
 205   unsigned int objlength;
 206
 207   while(origptr<origbound) {
 208     //Try to skip over stuff fast first
 209     unsigned INTPTR offset=(unsigned INTPTR) (origptr-gcbaseva);
 210     unsigned INTPTR arrayoffset=ALIGNTOTABLEINDEX(offset);
 211     if (!gcmarktbl[arrayoffset]) {
 212       do {
 213         arrayoffset++;
 214         if (arrayoffset<origendoffset) {
 215           //finished with block...
 216           origptr=origbound;
 217           to->ptr=toptr;
 218           orig->ptr=origptr;
 219           gccurr_heaptop-=(unsigned INTPTR)(toptr-toptrinit);
 220           return 0;
 221         }
 222       } while(!gcmarktbl[arrayoffset]);
 223       origptr=CONVERTTABLEINDEXTOPTR(arrayoffset);
 224     }
 225
 226     //Scan more carefully next
 227     objlength=getMarkedLength(origptr);
 228
 229     if (objlength!=NOTMARKED) {
 230       unsigned int length=ALIGNSIZETOBYTES(objlength);
 231       void *endtoptr=toptr+length;
 232       if (endtoptr>tobound) {
 233         gccurr_heaptop-=(unsigned INTPTR)(toptr-toptrinit);
 234         to->ptr=tobound;
 235         orig->ptr=origptr;
 236         return length;
 237       }
 238       //good to move objects and update pointers
 239       gcmappingtbl[OBJMAPPINGINDEX(origptr)]=toptr;
 240       origptr+=length;
 241       toptr=endtoptr;
 242     } else
 243       origptr+=ALIGNMENTSIZE;
 244   }
 245 }
 246
 247 void compact() {
 248   BAMBOO_ASSERT(COMPACTPHASE == gc_status_info.gcphase);
 249   BAMBOO_CACHE_MF();
 250
 251   // initialize structs for compacting
 252   struct moveHelper orig={0,NULL,NULL,0,NULL,0,0,0,0};
 253   struct moveHelper to={0,NULL,NULL,0,NULL,0,0,0,0};
 254   initOrig_Dst(&orig, &to);
 255
 256   CACHEADAPT_SAMPLING_DATA_REVISE_INIT(&orig, &to);
 257
 258   compacthelper(&orig, &to);
 259 }
 260
 261 void master_compact() {
 262   // predict number of blocks to fill for each core
 263   numblockspercore = loadbalance()+1;
 264
 265   GC_PRINTF("mark phase finished \n");
 266
 267   gc_resetCoreStatus();
 268   //initialize local data structures first....we don't want remote requests messing data up
 269   unsigned int initblocks=numblockspercore*NUMCORES4GC;
 270   allocationinfo.lowestfreeblock=NOFREEBLOCK;
 271
 272   //assigned blocks
 273   for(int i=0;i<initblocks;i++) {
 274     allocationinfo.blocktable[i].status=BS_USED;
 275   }
 276
 277   //free blocks
 278   for(int i=initblocks;i<GCNUMBLOCK;i++) {
 279     allocationinfo.blocktable[i].status=BS_FREE;
 280     allocationinfo.blocktable[i].usedspace=0;
 281     //this is true because all cores have at least one block already...
 282     allocationinfo.blocktable[i].freespace=BLOCKSIZE(1);
 283   }
 284
 285   //start all of the cores
 286   for(int i = 0; i < NUMCORES4GC; i++) {
 287     // init some data strutures for compact phase
 288     gcrequiredmems[i] = 0;
 289     gccorestatus[i] = 1;
 290     //send start compact messages to all cores
 291     if(i != STARTUPCORE) {
 292       send_msg_2(i, GCSTARTCOMPACT, numblockspercore);
 293     } else {
 294       gcblock2fill = numblockspercore;
 295     }
 296   }
 297   BAMBOO_CACHE_MF();
 298   GCPROFILE_ITEM();
 299   // compact phase
 300   compact();
 301   /* wait for all cores to finish compacting */
 302
 303   while(gc_checkCoreStatus())
 304     ;
 305
 306   GCPROFILE_ITEM();
 307
 308   GC_PRINTF("compact phase finished \n");
 309 }
 310
 311 #endif // MULTICORE_GC