includes/rts/storage/Block.h

   1 /* -----------------------------------------------------------------------------
   2  *
   3  * (c) The GHC Team, 1998-1999
   4  *
   5  * Block structure for the storage manager
   6  *
   7  * ---------------------------------------------------------------------------*/
   8
   9 #ifndef RTS_STORAGE_BLOCK_H
  10 #define RTS_STORAGE_BLOCK_H
  11
  12 /* The actual block and megablock-size constants are defined in
  13  * includes/Constants.h, all constants here are derived from these.
  14  */
  15
  16 /* Block related constants (BLOCK_SHIFT is defined in Constants.h) */
  17
  18 #define BLOCK_SIZE   (1<<BLOCK_SHIFT)
  19 #define BLOCK_SIZE_W (BLOCK_SIZE/sizeof(W_))
  20 #define BLOCK_MASK   (BLOCK_SIZE-1)
  21
  22 #define BLOCK_ROUND_UP(p)   ((void *) (((W_)(p)+BLOCK_SIZE-1) & ~BLOCK_MASK))
  23 #define BLOCK_ROUND_DOWN(p) ((void *) ((W_)(p) & ~BLOCK_MASK))
  24
  25 /* Megablock related constants (MBLOCK_SHIFT is defined in Constants.h) */
  26
  27 #define MBLOCK_SIZE    (1<<MBLOCK_SHIFT)
  28 #define MBLOCK_SIZE_W  (MBLOCK_SIZE/sizeof(W_))
  29 #define MBLOCK_MASK    (MBLOCK_SIZE-1)
  30
  31 #define MBLOCK_ROUND_UP(p)   ((void *)(((W_)(p)+MBLOCK_SIZE-1) & ~MBLOCK_MASK))
  32 #define MBLOCK_ROUND_DOWN(p) ((void *)((W_)(p) & ~MBLOCK_MASK ))
  33
  34 /* The largest size an object can be before we give it a block of its
  35  * own and treat it as an immovable object during GC, expressed as a
  36  * fraction of BLOCK_SIZE.
  37  */
  38 #define LARGE_OBJECT_THRESHOLD ((nat)(BLOCK_SIZE * 8 / 10))
  39
  40 /* -----------------------------------------------------------------------------
  41  * Block descriptor.  This structure *must* be the right length, so we
  42  * can do pointer arithmetic on pointers to it.
  43  */
  44
  45 /* The block descriptor is 64 bytes on a 64-bit machine, and 32-bytes
  46  * on a 32-bit machine.
  47  */
  48
  49 // Note: fields marked with [READ ONLY] must not be modified by the
  50 // client of the block allocator API.  All other fields can be
  51 // freely modified.
  52
  53 #ifndef CMINUSMINUS
  54 typedef struct bdescr_ {
  55
  56     StgPtr start;              // [READ ONLY] start addr of memory
  57
  58     StgPtr free;               // first free byte of memory.
  59                                // NB. during use this value should lie
  60                                // between start and start + blocks *
  61                                // BLOCK_SIZE.  Values outside this
  62                                // range are reserved for use by the
  63                                // block allocator.  In particular, the
  64                                // value (StgPtr)(-1) is used to
  65                                // indicate that a block is unallocated.
  66
  67     struct bdescr_ *link;      // used for chaining blocks together
  68
  69     union {
  70         struct bdescr_ *back;  // used (occasionally) for doubly-linked lists
  71         StgWord *bitmap;       // bitmap for marking GC
  72         StgPtr  scan;          // scan pointer for copying GC
  73     } u;
  74
  75     struct generation_ *gen;   // generation
  76
  77     StgWord16 gen_no;          // gen->no, cached
  78     StgWord16 dest_no;         // number of destination generation
  79     StgWord16 _pad1;
  80
  81     StgWord16 flags;           // block flags, see below
  82
  83     StgWord32 blocks;          // [READ ONLY] no. of blocks in a group
  84                                // (if group head, 0 otherwise)
  85
  86 #if SIZEOF_VOID_P == 8
  87     StgWord32 _padding[3];
  88 #else
  89     StgWord32 _padding[0];
  90 #endif
  91 } bdescr;
  92 #endif
  93
  94 #if SIZEOF_VOID_P == 8
  95 #define BDESCR_SIZE  0x40
  96 #define BDESCR_MASK  0x3f
  97 #define BDESCR_SHIFT 6
  98 #else
  99 #define BDESCR_SIZE  0x20
 100 #define BDESCR_MASK  0x1f
 101 #define BDESCR_SHIFT 5
 102 #endif
 103
 104 /* Block contains objects evacuated during this GC */
 105 #define BF_EVACUATED 1
 106 /* Block is a large object */
 107 #define BF_LARGE     2
 108 /* Block is pinned */
 109 #define BF_PINNED    4
 110 /* Block is to be marked, not copied */
 111 #define BF_MARKED    8
 112 /* Block is free, and on the free list  (TODO: is this used?) */
 113 #define BF_FREE      16
 114 /* Block is executable */
 115 #define BF_EXEC      32
 116 /* Block contains only a small amount of live data */
 117 #define BF_FRAGMENTED 64
 118 /* we know about this block (for finding leaks) */
 119 #define BF_KNOWN     128
 120 /* Block was swept in the last generation */
 121 #define BF_SWEPT     256
 122
 123 /* Finding the block descriptor for a given block -------------------------- */
 124
 125 #ifdef CMINUSMINUS
 126
 127 #define Bdescr(p) \
 128     ((((p) &  MBLOCK_MASK & ~BLOCK_MASK) >> (BLOCK_SHIFT-BDESCR_SHIFT)) \
 129      | ((p) & ~MBLOCK_MASK))
 130
 131 #else
 132
 133 EXTERN_INLINE bdescr *Bdescr(StgPtr p);
 134 EXTERN_INLINE bdescr *Bdescr(StgPtr p)
 135 {
 136   return (bdescr *)
 137     ((((W_)p &  MBLOCK_MASK & ~BLOCK_MASK) >> (BLOCK_SHIFT-BDESCR_SHIFT))
 138      | ((W_)p & ~MBLOCK_MASK)
 139      );
 140 }
 141
 142 #endif
 143
 144 /* Useful Macros ------------------------------------------------------------ */
 145
 146 /* Offset of first real data block in a megablock */
 147
 148 #define FIRST_BLOCK_OFF \
 149    ((W_)BLOCK_ROUND_UP(BDESCR_SIZE * (MBLOCK_SIZE / BLOCK_SIZE)))
 150
 151 /* First data block in a given megablock */
 152
 153 #define FIRST_BLOCK(m) ((void *)(FIRST_BLOCK_OFF + (W_)(m)))
 154
 155 /* Last data block in a given megablock */
 156
 157 #define LAST_BLOCK(m)  ((void *)(MBLOCK_SIZE-BLOCK_SIZE + (W_)(m)))
 158
 159 /* First real block descriptor in a megablock */
 160
 161 #define FIRST_BDESCR(m) \
 162    ((bdescr *)((FIRST_BLOCK_OFF>>(BLOCK_SHIFT-BDESCR_SHIFT)) + (W_)(m)))
 163
 164 /* Last real block descriptor in a megablock */
 165
 166 #define LAST_BDESCR(m) \
 167   ((bdescr *)(((MBLOCK_SIZE-BLOCK_SIZE)>>(BLOCK_SHIFT-BDESCR_SHIFT)) + (W_)(m)))
 168
 169 /* Number of usable blocks in a megablock */
 170
 171 #ifndef CMINUSMINUS // already defined in DerivedConstants.h
 172 #define BLOCKS_PER_MBLOCK ((MBLOCK_SIZE - FIRST_BLOCK_OFF) / BLOCK_SIZE)
 173 #endif
 174
 175 /* How many blocks in this megablock group */
 176
 177 #define MBLOCK_GROUP_BLOCKS(n) \
 178    (BLOCKS_PER_MBLOCK + (n-1) * (MBLOCK_SIZE / BLOCK_SIZE))
 179
 180 /* Compute the required size of a megablock group */
 181
 182 #define BLOCKS_TO_MBLOCKS(n) \
 183    (1 + (W_)MBLOCK_ROUND_UP((n-BLOCKS_PER_MBLOCK) * BLOCK_SIZE) / MBLOCK_SIZE)
 184
 185
 186 #ifndef CMINUSMINUS
 187 /* to the end... */
 188
 189 /* Double-linked block lists: --------------------------------------------- */
 190
 191 INLINE_HEADER void
 192 dbl_link_onto(bdescr *bd, bdescr **list)
 193 {
 194   bd->link = *list;
 195   bd->u.back = NULL;
 196   if (*list) {
 197     (*list)->u.back = bd; /* double-link the list */
 198   }
 199   *list = bd;
 200 }
 201
 202 INLINE_HEADER void
 203 dbl_link_remove(bdescr *bd, bdescr **list)
 204 {
 205     if (bd->u.back) {
 206         bd->u.back->link = bd->link;
 207     } else {
 208         *list = bd->link;
 209     }
 210     if (bd->link) {
 211         bd->link->u.back = bd->u.back;
 212     }
 213 }
 214
 215 INLINE_HEADER void
 216 dbl_link_insert_after(bdescr *bd, bdescr *after)
 217 {
 218     bd->link = after->link;
 219     bd->u.back = after;
 220     if (after->link) {
 221         after->link->u.back = bd;
 222     }
 223     after->link = bd;
 224 }
 225
 226 INLINE_HEADER void
 227 dbl_link_replace(bdescr *new, bdescr *old, bdescr **list)
 228 {
 229     new->link = old->link;
 230     new->u.back = old->u.back;
 231     if (old->link) {
 232         old->link->u.back = new;
 233     }
 234     if (old->u.back) {
 235         old->u.back->link = new;
 236     } else {
 237         *list = new;
 238     }
 239 }
 240
 241 /* Initialisation ---------------------------------------------------------- */
 242
 243 extern void initBlockAllocator(void);
 244
 245 /* Allocation -------------------------------------------------------------- */
 246
 247 bdescr *allocGroup(nat n);
 248 bdescr *allocBlock(void);
 249
 250 // versions that take the storage manager lock for you:
 251 bdescr *allocGroup_lock(nat n);
 252 bdescr *allocBlock_lock(void);
 253
 254 /* De-Allocation ----------------------------------------------------------- */
 255
 256 void freeGroup(bdescr *p);
 257 void freeChain(bdescr *p);
 258
 259 // versions that take the storage manager lock for you:
 260 void freeGroup_lock(bdescr *p);
 261 void freeChain_lock(bdescr *p);
 262
 263 bdescr * splitBlockGroup (bdescr *bd, nat blocks);
 264
 265 /* Round a value to megablocks --------------------------------------------- */
 266
 267 // We want to allocate an object around a given size, round it up or
 268 // down to the nearest size that will fit in an mblock group.
 269 INLINE_HEADER StgWord
 270 round_to_mblocks(StgWord words)
 271 {
 272     if (words > BLOCKS_PER_MBLOCK * BLOCK_SIZE_W) {
 273         // first, ignore the gap at the beginning of the first mblock by
 274         // adding it to the total words.  Then we can pretend we're
 275         // dealing in a uniform unit of megablocks.
 276         words += FIRST_BLOCK_OFF/sizeof(W_);
 277
 278         if ((words % MBLOCK_SIZE_W) < (MBLOCK_SIZE_W / 2)) {
 279             words = (words / MBLOCK_SIZE_W) * MBLOCK_SIZE_W;
 280         } else {
 281             words = ((words / MBLOCK_SIZE_W) + 1) * MBLOCK_SIZE_W;
 282         }
 283
 284         words -= FIRST_BLOCK_OFF/sizeof(W_);
 285     }
 286     return words;
 287 }
 288
 289 INLINE_HEADER StgWord
 290 round_up_to_mblocks(StgWord words)
 291 {
 292     words += FIRST_BLOCK_OFF/sizeof(W_);
 293     words = ((words / MBLOCK_SIZE_W) + 1) * MBLOCK_SIZE_W;
 294     words -= FIRST_BLOCK_OFF/sizeof(W_);
 295     return words;
 296 }
 297
 298 #endif /* !CMINUSMINUS */
 299 #endif /* RTS_STORAGE_BLOCK_H */