Robust/src/Runtime/bamboo/multicoregarbage.h

   1 #ifndef BAMBOO_MULTICORE_GARBAGE_H
   2 #define BAMBOO_MULTICORE_GARBAGE_H
   3 #ifdef MULTICORE_GC
   4 #include "multicore.h"
   5 #include "multicoregc.h"
   6 #include "multicorehelper.h"  // for mappings between core # and block #
   7 #include "structdefs.h"
   8 #include "multicoregcprofile.h"
   9 #include "gctypes.h"
  10
  11 #ifdef GC_DEBUG
  12 #define GC_PRINTF tprintf
  13 #else
  14 #define GC_PRINTF if(0) tprintf
  15 #endif
  16
  17 #ifdef GC_DEBUG
  18 #define TR() tprintf("%u\n",__LINE__)
  19 #else
  20 #define TR()
  21 #endif
  22
  23 // data structures for GC
  24 #define BAMBOO_SMEM_SIZE_L (BAMBOO_SMEM_SIZE * 2)
  25 #define BAMBOO_LARGE_SMEM_BOUND (BAMBOO_SMEM_SIZE_L*NUMCORES4GC)
  26 // let each gc core to have one big block, this is very important
  27 // for the computation of NUMBLOCKS(s, n), DO NOT change this!
  28
  29 typedef enum {
  30   INITPHASE = 0x0,         // 0x0
  31   MARKPHASE,               // 0x1
  32   COMPACTPHASE,            // 0x2
  33   SUBTLECOMPACTPHASE,      // 0x3
  34   MAPPHASE,                // 0x4
  35   UPDATEPHASE,             // 0x5
  36   CACHEPOLICYPHASE,        // 0x6
  37   PREFINISHPHASE,          // 0x7
  38   FINISHPHASE              // 0x8
  39 } GCPHASETYPE;
  40
  41 typedef struct gc_status {
  42   volatile bool gcprocessing;
  43   volatile GCPHASETYPE gcphase; // indicating GC phase
  44   volatile bool gcbusystatus;
  45 } gc_status_t;
  46
  47 extern volatile bool gcflag;
  48 extern gc_status_t gc_status_info;
  49 volatile bool gcprecheck; // indicates if there are updated pregc information
  50
  51 unsigned INTPTR gccurr_heaptop;
  52 struct MGCHash * gcforwardobjtbl; // cache forwarded objs in mark phase
  53 // for mark phase termination
  54 volatile unsigned int gccorestatus[NUMCORESACTIVE];//records status of each core
  55                                                    // 1: running gc
  56                                                    // 0: stall
  57
  58 volatile unsigned int returnedmem[NUMCORESACTIVE];//records status of each core
  59                                                    // 1: running gc
  60                                                    // 0: stall
  61 volatile unsigned int gcnumsendobjs[2][NUMCORESACTIVE];//# of objects sent out
  62 volatile unsigned int gcnumreceiveobjs[2][NUMCORESACTIVE];//# of objects received
  63 volatile unsigned int gcnumsrobjs_index;//indicates which entry to record the
  64                  // info received before phase 1 of the mark finish
  65                  // checking process
  66                  // the info received in phase 2 must be
  67                  // recorded in the other entry
  68
  69 unsigned int gcself_numsendobjs;
  70 unsigned int gcself_numreceiveobjs;
  71
  72 // for load balancing
  73 unsigned INTPTR gcloads[NUMCORES4GC];
  74 block_t numblockspercore;
  75
  76 //Top of each core's heap
  77 void * topptrs[NUMCORES4GC];
  78
  79 // compact instruction
  80 //keep track of what block we can fill to
  81 unsigned int gcblock2fill;
  82
  83 // move instruction;
  84 //this points to memory handed to core from master
  85 volatile unsigned int gcmovestartaddr;
  86 //this flag tells core that it is okay to start compacting
  87 volatile bool gctomove;
  88
  89 //keeps track of memory request master was not able to serve
  90 volatile unsigned int maxusefulmems[NUMCORES4GC]; //record pending mem requests
  91 volatile unsigned int gcrequiredmems[NUMCORES4GC]; //record pending mem requests
  92 volatile unsigned int gcmovepending;
  93
  94 //keep track of current base block pointer for orig block
  95 volatile void * update_origblockptr;
  96 volatile void * origblockarray[NUMCORES4GC];
  97 volatile int origarraycount;
  98 volatile bool blockgranted;
  99
 100
 101 // shared memory pointer for pointer mapping tbls
 102 // In GC version, this block of memory is located at the bottom of the
 103 // shared memory, right on the top of the smem tbl.
 104 // The bottom of the shared memory = sbstart tbl + smemtbl + bamboo_rmsp
 105 // These three types of table are always reside at the bottom of the shared
 106 // memory and will never be moved or garbage collected
 107 //gcmappingtable gives new pointer location
 108 void ** gcmappingtbl;
 109 //number of bytes in mapping table
 110 unsigned int bamboo_rmsp_size;
 111
 112 //mark table....keep track of mark bits
 113 volatile unsigned int * gcmarktbl;
 114
 115 void * gcbaseva; // base va for shared memory without reserved sblocks
 116
 117 bool gc_checkCoreStatus();
 118
 119 void gc_resetCoreStatus();
 120
 121
 122
 123 /* Structure to keep track of free space in block */
 124 enum blockstatus {
 125   /* BS_USED indicates that we don't have information for this block yet */
 126   BS_USED,
 127   /* BS_LARGEOBJECT indicates that the beginning of this block has a large object*/
 128   BS_LARGEOBJECT,
 129   /* BS_FREE indicates that the block is at least partially free */
 130   BS_FREE
 131 };
 132
 133 struct blockrecord {
 134   enum blockstatus status;
 135   unsigned INTPTR usedspace;
 136   unsigned INTPTR freespace;
 137   unsigned int corenum;
 138 };
 139
 140 #define NOFREEBLOCK 0xffffffff
 141 struct allocrecord {
 142   unsigned int lowestfreeblock;
 143   struct blockrecord * blocktable;
 144 };
 145
 146 struct allocrecord allocationinfo;
 147
 148 #ifdef GC_CACHE_ADAPT
 149 void * gctopva; // top va for shared memory without reserved sblocks
 150 volatile bool gccachestage;
 151 // table recording the sampling data collected for cache adaption
 152 int * gccachesamplingtbl;
 153 int * gccachesamplingtbl_local;// for zeroing memory only
 154 unsigned int size_cachesamplingtbl_local; // for zeroing memory only
 155 int * gccachesamplingtbl_r;
 156 int * gccachesamplingtbl_local_r; // for zeroing memory only
 157 unsigned int size_cachesamplingtbl_local_r; // for zeroing memory only
 158 int * gccachepolicytbl;
 159 unsigned int size_cachepolicytbl;
 160 #endif
 161
 162 /* Total number of blocks in heap */
 163
 164 #define GCNUMBLOCK (NUMCORES4GC+(BAMBOO_SHARED_MEM_SIZE-BAMBOO_LARGE_SMEM_BOUND)/BAMBOO_SMEM_SIZE)
 165 #define GCNUMLOCALBLOCK (GCNUMBLOCK/NUMCORES4GC)
 166
 167 /* Leave the neighboring cores with at least two blocks */
 168 #define MAXNEIGHBORALLOC (GCNUMLOCALBLOCK-2)
 169
 170 /* This macro defines the smallest memoy chunk the master will hand out to another core during compacting */
 171
 172 #define MINMEMORYCHUNKSIZE 32768
 173
 174 #define ISVALIDPTR(x) ((((unsigned INTPTR)x)>=((unsigned INTPTR)gcbaseva))&&(((unsigned INTPTR)x)<((unsigned INTPTR)(gcbaseva+BAMBOO_SHARED_MEM_SIZE))))
 175
 176 /* This macro waits for the given gc phase */
 177 #define WAITFORGCPHASE(phase) while(gc_status_info.gcphase != phase) ;
 178
 179 /* Local block number that can never be reached...*/
 180 #define MAXBLOCK 0x4fffffff
 181
 182 //Takes in pointer to heap object and converts to offset in alignment units
 183 #define OBJMAPPINGINDEX(p) ALIGNOBJSIZE((unsigned INTPTR)(p-gcbaseva))
 184
 185 //Converts size of object into alignment units (need to round up)
 186 #define ALIGNUNITS(s) (((s-1)>>ALIGNMENTSHIFT)+1)
 187
 188 //Rounds object size up to next alignment unit size
 189 #define ALIGNSIZE(s) ((((unsigned int)(s-1))&~(ALIGNMENTBYTES-1))+ALIGNMENTBYTES)
 190
 191 #define GLOBALBLOCK2LOCAL(s) (s/NUMCORES4GC)
 192
 193 // mapping of pointer to block # (start from 0), here the block # is
 194 // the global index
 195 #define BLOCKINDEX(b, p)                        \
 196   {                                                             \
 197     unsigned INTPTR t = (unsigned INTPTR)(p - gcbaseva);        \
 198     if(t < BAMBOO_LARGE_SMEM_BOUND) {                           \
 199       b = t / BAMBOO_SMEM_SIZE_L;                               \
 200     } else {                                                          \
 201       b = NUMCORES4GC+((t-BAMBOO_LARGE_SMEM_BOUND)/BAMBOO_SMEM_SIZE); \
 202     }                                                                 \
 203   }
 204
 205 #define RESIDECORE(c, p) {     \
 206     if(1 == (NUMCORES4GC)) { \
 207       c = 0; \
 208     } else { \
 209       unsigned INTPTR b; \
 210       BLOCKINDEX(b, p);               \
 211       c = gc_block2core[(b%(NUMCORES4GC*2))]; \
 212     } \
 213   }
 214
 215 #define BLOCK2CORE(c, b) {                      \
 216     if(1 == (NUMCORES4GC)) {                    \
 217       c = 0;                                    \
 218     } else {                                    \
 219       c = gc_block2core[(b%(NUMCORES4GC*2))];   \
 220     }                                           \
 221   }
 222
 223 INLINE static unsigned int hostcore(void * ptr) {
 224   // check the host core of ptr
 225   unsigned int host;
 226   RESIDECORE(host, ptr);
 227   return host;
 228 }
 229
 230 /*This macro takes in a number of bytes (the current offset into the
 231   heap) and returns the number of local blocks needed for that many
 232   bytes */
 233
 234 #define NUMBLOCKS(s, n) \
 235   if(s < (BAMBOO_SMEM_SIZE_L)) { \
 236     (n) = 0; \
 237   } else { \
 238     (n) = 1 + ((s) - (BAMBOO_SMEM_SIZE_L)) / (BAMBOO_SMEM_SIZE); \
 239   }
 240
 241 //this macro takes in a global block identifier and returns the base
 242 //offset into the heap
 243 #define OFFSET2BASEVA(i) \
 244   (((i)<NUMCORES4GC)?(BAMBOO_SMEM_SIZE_L*(i)):(BAMBOO_SMEM_SIZE*((i)-NUMCORES4GC)+BAMBOO_LARGE_SMEM_BOUND))
 245
 246
 247 //This macro takes in a local block number and returns the size of the block
 248 #define BLOCKSIZE(c) \
 249   ((c)?BAMBOO_SMEM_SIZE:BAMBOO_SMEM_SIZE_L)
 250
 251 //This macro takes in a local block number and returns the size of the block
 252 #define GLOBALBLOCKSIZE(c) \
 253   ((c<NUMCORES4GC)?BAMBOO_SMEM_SIZE_L:BAMBOO_SMEM_SIZE)
 254
 255 //Takes as input the core number c and the local block index n and
 256 //returns the global block index
 257
 258 #define BLOCKINDEX2(c, n) \
 259   (gc_core2block[2*(c)+((n)&1)]+(NUMCORES4GC*2)*((n)>>1))
 260
 261 //This macro takes in a global block number and returns the base
 262 //pointer of the next block
 263 #define BOUNDPTR(b) \
 264   (((b)<NUMCORES4GC)?(((b)+1)*BAMBOO_SMEM_SIZE_L):(BAMBOO_LARGE_SMEM_BOUND+((b)-NUMCORES4GC+1)*BAMBOO_SMEM_SIZE))
 265
 266 //This macro takes in the core number c and the local block number and
 267 //sets p to the base pointer
 268
 269 #define BASEPTR(p, c, n) {                                 \
 270     unsigned int b = BLOCKINDEX2((c), (n));                \
 271     if(b < (NUMCORES4GC)) {                                \
 272       p = gcbaseva + b * (BAMBOO_SMEM_SIZE_L);             \
 273     } else {                                               \
 274       p = gcbaseva+(BAMBOO_LARGE_SMEM_BOUND)+              \
 275         (b-(NUMCORES4GC))*(BAMBOO_SMEM_SIZE);              \
 276     }                                                      \
 277   }
 278
 279 // the next core in the top of the heap
 280 #define NEXTTOPCORE(b) (gc_block2core[((b)+1)%(NUMCORES4GC*2)])
 281
 282 // check if all cores are stall now
 283 #define GC_CHECK_ALL_CORE_STATUS() gccorestatus[BAMBOO_NUM_OF_CORE] = 0; \
 284   while(!gc_checkCoreStatus()) ;
 285
 286 // send a 1-word msg to all clients
 287 #define GC_SEND_MSG_1_TO_CLIENT(m) \
 288   { \
 289     for(int i = 0; i < NUMCORESACTIVE; ++i) { \
 290       gccorestatus[i] = 1; \
 291       if(BAMBOO_NUM_OF_CORE != i) { \
 292         send_msg_1(i, (m)); \
 293       } \
 294     } \
 295   }
 296
 297 #define ISLOCAL(p) (hostcore(p)==BAMBOO_NUM_OF_CORE)
 298
 299 void initmulticoregcdata();
 300 void dismulticoregcdata();
 301 bool gc(struct garbagelist * stackptr); // core coordinator routine
 302 void gc_collect(struct garbagelist* stackptr); //core collector routine
 303 void gc_nocollect(struct garbagelist* stackptr); //non-gc core collector routine
 304 void master_mark(struct garbagelist *stackptr);
 305 void master_getlargeobjs();
 306 void master_compact();
 307 void master_updaterefs();
 308 void master_finish();
 309 void gc_master(struct garbagelist * stackptr);
 310
 311
 312 void transferMarkResults_I();
 313 void * gcfindSpareMem_I(unsigned INTPTR requiredmem, unsigned INTPTR maxbytesneeded, unsigned int requiredcore);
 314
 315 #define INITMULTICOREGCDATA() initmulticoregcdata()
 316 #define DISMULTICOREGCDATA() dismulticoregcdata()
 317 #else // MULTICORE_GC
 318 #define INITMULTICOREGCDATA()
 319 #define DISMULTICOREGCDATA()
 320 #endif // MULTICORE_GC
 321 #endif // BAMBOO_MULTICORE_GARBAGE_H