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 #ifndef CMINUSMINUS
  50 typedef struct bdescr_ {
  51     StgPtr start;              /* start addr of memory */
  52     StgPtr free;               /* first free byte of memory */
  53     struct bdescr_ *link;      /* used for chaining blocks together */
  54     union {
  55         struct bdescr_ *back;  /* used (occasionally) for doubly-linked lists*/
  56         StgWord *bitmap;
  57         StgPtr  scan;           /* scan pointer for copying GC */
  58     } u;
  59
  60     struct generation_ *gen;   /* generation */
  61     struct generation_ *dest;  /* destination gen */
  62
  63     StgWord32 blocks;           /* no. of blocks (if grp head, 0 otherwise) */
  64
  65     StgWord16 gen_no;
  66     StgWord16 flags;            /* block flags, see below */
  67 #if SIZEOF_VOID_P == 8
  68     StgWord32 _padding[2];
  69 #else
  70     StgWord32 _padding[0];
  71 #endif
  72 } bdescr;
  73 #endif
  74
  75 #if SIZEOF_VOID_P == 8
  76 #define BDESCR_SIZE  0x40
  77 #define BDESCR_MASK  0x3f
  78 #define BDESCR_SHIFT 6
  79 #else
  80 #define BDESCR_SIZE  0x20
  81 #define BDESCR_MASK  0x1f
  82 #define BDESCR_SHIFT 5
  83 #endif
  84
  85 /* Block contains objects evacuated during this GC */
  86 #define BF_EVACUATED 1
  87 /* Block is a large object */
  88 #define BF_LARGE     2
  89 /* Block is pinned */
  90 #define BF_PINNED    4
  91 /* Block is to be marked, not copied */
  92 #define BF_MARKED    8
  93 /* Block is free, and on the free list  (TODO: is this used?) */
  94 #define BF_FREE      16
  95 /* Block is executable */
  96 #define BF_EXEC      32
  97 /* Block contains only a small amount of live data */
  98 #define BF_FRAGMENTED 64
  99 /* we know about this block (for finding leaks) */
 100 #define BF_KNOWN     128
 101 /* Block was swept in the last generation */
 102 #define BF_SWEPT     256
 103
 104 /* Finding the block descriptor for a given block -------------------------- */
 105
 106 #ifdef CMINUSMINUS
 107
 108 #define Bdescr(p) \
 109     ((((p) &  MBLOCK_MASK & ~BLOCK_MASK) >> (BLOCK_SHIFT-BDESCR_SHIFT)) \
 110      | ((p) & ~MBLOCK_MASK))
 111
 112 #else
 113
 114 EXTERN_INLINE bdescr *Bdescr(StgPtr p);
 115 EXTERN_INLINE bdescr *Bdescr(StgPtr p)
 116 {
 117   return (bdescr *)
 118     ((((W_)p &  MBLOCK_MASK & ~BLOCK_MASK) >> (BLOCK_SHIFT-BDESCR_SHIFT))
 119      | ((W_)p & ~MBLOCK_MASK)
 120      );
 121 }
 122
 123 #endif
 124
 125 /* Useful Macros ------------------------------------------------------------ */
 126
 127 /* Offset of first real data block in a megablock */
 128
 129 #define FIRST_BLOCK_OFF \
 130    ((W_)BLOCK_ROUND_UP(BDESCR_SIZE * (MBLOCK_SIZE / BLOCK_SIZE)))
 131
 132 /* First data block in a given megablock */
 133
 134 #define FIRST_BLOCK(m) ((void *)(FIRST_BLOCK_OFF + (W_)(m)))
 135
 136 /* Last data block in a given megablock */
 137
 138 #define LAST_BLOCK(m)  ((void *)(MBLOCK_SIZE-BLOCK_SIZE + (W_)(m)))
 139
 140 /* First real block descriptor in a megablock */
 141
 142 #define FIRST_BDESCR(m) \
 143    ((bdescr *)((FIRST_BLOCK_OFF>>(BLOCK_SHIFT-BDESCR_SHIFT)) + (W_)(m)))
 144
 145 /* Last real block descriptor in a megablock */
 146
 147 #define LAST_BDESCR(m) \
 148   ((bdescr *)(((MBLOCK_SIZE-BLOCK_SIZE)>>(BLOCK_SHIFT-BDESCR_SHIFT)) + (W_)(m)))
 149
 150 /* Number of usable blocks in a megablock */
 151
 152 #ifndef CMINUSMINUS // already defined in DerivedConstants.h
 153 #define BLOCKS_PER_MBLOCK ((MBLOCK_SIZE - FIRST_BLOCK_OFF) / BLOCK_SIZE)
 154 #endif
 155
 156 /* How many blocks in this megablock group */
 157
 158 #define MBLOCK_GROUP_BLOCKS(n) \
 159    (BLOCKS_PER_MBLOCK + (n-1) * (MBLOCK_SIZE / BLOCK_SIZE))
 160
 161 /* Compute the required size of a megablock group */
 162
 163 #define BLOCKS_TO_MBLOCKS(n) \
 164    (1 + (W_)MBLOCK_ROUND_UP((n-BLOCKS_PER_MBLOCK) * BLOCK_SIZE) / MBLOCK_SIZE)
 165
 166
 167 #ifndef CMINUSMINUS
 168 /* to the end... */
 169
 170 /* Double-linked block lists: --------------------------------------------- */
 171
 172 INLINE_HEADER void
 173 dbl_link_onto(bdescr *bd, bdescr **list)
 174 {
 175   bd->link = *list;
 176   bd->u.back = NULL;
 177   if (*list) {
 178     (*list)->u.back = bd; /* double-link the list */
 179   }
 180   *list = bd;
 181 }
 182
 183 INLINE_HEADER void
 184 dbl_link_remove(bdescr *bd, bdescr **list)
 185 {
 186     if (bd->u.back) {
 187         bd->u.back->link = bd->link;
 188     } else {
 189         *list = bd->link;
 190     }
 191     if (bd->link) {
 192         bd->link->u.back = bd->u.back;
 193     }
 194 }
 195
 196 INLINE_HEADER void
 197 dbl_link_insert_after(bdescr *bd, bdescr *after)
 198 {
 199     bd->link = after->link;
 200     bd->u.back = after;
 201     if (after->link) {
 202         after->link->u.back = bd;
 203     }
 204     after->link = bd;
 205 }
 206
 207 INLINE_HEADER void
 208 dbl_link_replace(bdescr *new, bdescr *old, bdescr **list)
 209 {
 210     new->link = old->link;
 211     new->u.back = old->u.back;
 212     if (old->link) {
 213         old->link->u.back = new;
 214     }
 215     if (old->u.back) {
 216         old->u.back->link = new;
 217     } else {
 218         *list = new;
 219     }
 220 }
 221
 222 /* Initialisation ---------------------------------------------------------- */
 223
 224 extern void initBlockAllocator(void);
 225
 226 /* Allocation -------------------------------------------------------------- */
 227
 228 bdescr *allocGroup(nat n);
 229 bdescr *allocBlock(void);
 230
 231 // versions that take the storage manager lock for you:
 232 bdescr *allocGroup_lock(nat n);
 233 bdescr *allocBlock_lock(void);
 234
 235 /* De-Allocation ----------------------------------------------------------- */
 236
 237 void freeGroup(bdescr *p);
 238 void freeChain(bdescr *p);
 239
 240 // versions that take the storage manager lock for you:
 241 void freeGroup_lock(bdescr *p);
 242 void freeChain_lock(bdescr *p);
 243
 244 bdescr * splitBlockGroup (bdescr *bd, nat blocks);
 245
 246 /* Round a value to megablocks --------------------------------------------- */
 247
 248 // We want to allocate an object around a given size, round it up or
 249 // down to the nearest size that will fit in an mblock group.
 250 INLINE_HEADER StgWord
 251 round_to_mblocks(StgWord words)
 252 {
 253     if (words > BLOCKS_PER_MBLOCK * BLOCK_SIZE_W) {
 254         // first, ignore the gap at the beginning of the first mblock by
 255         // adding it to the total words.  Then we can pretend we're
 256         // dealing in a uniform unit of megablocks.
 257         words += FIRST_BLOCK_OFF/sizeof(W_);
 258
 259         if ((words % MBLOCK_SIZE_W) < (MBLOCK_SIZE_W / 2)) {
 260             words = (words / MBLOCK_SIZE_W) * MBLOCK_SIZE_W;
 261         } else {
 262             words = ((words / MBLOCK_SIZE_W) + 1) * MBLOCK_SIZE_W;
 263         }
 264
 265         words -= FIRST_BLOCK_OFF/sizeof(W_);
 266     }
 267     return words;
 268 }
 269
 270 INLINE_HEADER StgWord
 271 round_up_to_mblocks(StgWord words)
 272 {
 273     words += FIRST_BLOCK_OFF/sizeof(W_);
 274     words = ((words / MBLOCK_SIZE_W) + 1) * MBLOCK_SIZE_W;
 275     words -= FIRST_BLOCK_OFF/sizeof(W_);
 276     return words;
 277 }
 278
 279 #endif /* !CMINUSMINUS */
 280 #endif /* RTS_STORAGE_BLOCK_H */