Block.h 10.4 KB
Newer Older
1
/* -----------------------------------------------------------------------------
2 3
 *
 * (c) The GHC Team, 1998-1999
4 5 6 7 8
 *
 * Block structure for the storage manager
 *
 * ---------------------------------------------------------------------------*/

9
#pragma once
10

11 12
#include "ghcconfig.h"

13 14 15 16
/* The actual block and megablock-size constants are defined in
 * includes/Constants.h, all constants here are derived from these.
 */

17
/* Block related constants (BLOCK_SHIFT is defined in Constants.h) */
18

19 20 21 22 23 24 25 26
#if SIZEOF_LONG == SIZEOF_VOID_P
#define UNIT 1UL
#elif SIZEOF_LONG_LONG == SIZEOF_VOID_P
#define UNIT 1ULL
#else
#error "Size of pointer is suspicious."
#endif

Ben Gamari's avatar
Ben Gamari committed
27
#if defined(CMINUSMINUS)
28
#define BLOCK_SIZE   (1<<BLOCK_SHIFT)
29
#else
30
#define BLOCK_SIZE   (UNIT<<BLOCK_SHIFT)
31 32 33
// Note [integer overflow]
#endif

34 35 36
#define BLOCK_SIZE_W (BLOCK_SIZE/sizeof(W_))
#define BLOCK_MASK   (BLOCK_SIZE-1)

37
#define BLOCK_ROUND_UP(p)   (((W_)(p)+BLOCK_SIZE-1) & ~BLOCK_MASK)
38 39
#define BLOCK_ROUND_DOWN(p) ((void *) ((W_)(p) & ~BLOCK_MASK))

40
/* Megablock related constants (MBLOCK_SHIFT is defined in Constants.h) */
41

Ben Gamari's avatar
Ben Gamari committed
42
#if defined(CMINUSMINUS)
43
#define MBLOCK_SIZE    (1<<MBLOCK_SHIFT)
44
#else
45
#define MBLOCK_SIZE    (UNIT<<MBLOCK_SHIFT)
46 47 48
// Note [integer overflow]
#endif

49 50 51 52 53 54
#define MBLOCK_SIZE_W  (MBLOCK_SIZE/sizeof(W_))
#define MBLOCK_MASK    (MBLOCK_SIZE-1)

#define MBLOCK_ROUND_UP(p)   ((void *)(((W_)(p)+MBLOCK_SIZE-1) & ~MBLOCK_MASK))
#define MBLOCK_ROUND_DOWN(p) ((void *)((W_)(p) & ~MBLOCK_MASK ))

sof's avatar
sof committed
55 56 57 58
/* The largest size an object can be before we give it a block of its
 * own and treat it as an immovable object during GC, expressed as a
 * fraction of BLOCK_SIZE.
 */
59
#define LARGE_OBJECT_THRESHOLD ((uint32_t)(BLOCK_SIZE * 8 / 10))
60

61 62 63 64 65 66 67 68 69 70 71 72
/*
 * Note [integer overflow]
 *
 * The UL suffix in BLOCK_SIZE and MBLOCK_SIZE promotes the expression
 * to an unsigned long, which means that expressions involving these
 * will be promoted to unsigned long, which makes integer overflow
 * less likely.  Historically, integer overflow in expressions like
 *    (n * BLOCK_SIZE)
 * where n is int or unsigned int, have caused obscure segfaults in
 * programs that use large amounts of memory (e.g. #7762, #5086).
 */

73 74 75 76 77 78 79 80 81
/* -----------------------------------------------------------------------------
 * Block descriptor.  This structure *must* be the right length, so we
 * can do pointer arithmetic on pointers to it.
 */

/* The block descriptor is 64 bytes on a 64-bit machine, and 32-bytes
 * on a 32-bit machine.
 */

Simon Marlow's avatar
Simon Marlow committed
82 83 84 85
// Note: fields marked with [READ ONLY] must not be modified by the
// client of the block allocator API.  All other fields can be
// freely modified.

Ben Gamari's avatar
Ben Gamari committed
86
#if !defined(CMINUSMINUS)
87
typedef struct bdescr_ {
Simon Marlow's avatar
Simon Marlow committed
88 89 90

    StgPtr start;              // [READ ONLY] start addr of memory

91 92 93 94 95 96 97 98 99 100 101 102 103 104
    union {
        StgPtr free;               // First free byte of memory.
                                   // allocGroup() sets this to the value of start.
                                   // NB. during use this value should lie
                                   // between start and start + blocks *
                                   // BLOCK_SIZE.  Values outside this
                                   // range are reserved for use by the
                                   // block allocator.  In particular, the
                                   // value (StgPtr)(-1) is used to
                                   // indicate that a block is unallocated.
                                   //
                                   // Unused by the non-moving allocator.
        struct NonmovingSegmentInfo {
            StgWord8 log_block_size;
105
            StgWord16 next_free_snap;
106 107
        } nonmoving_segment;
    };
Simon Marlow's avatar
Simon Marlow committed
108 109 110

    struct bdescr_ *link;      // used for chaining blocks together

111
    union {
Simon Marlow's avatar
Simon Marlow committed
112 113 114
        struct bdescr_ *back;  // used (occasionally) for doubly-linked lists
        StgWord *bitmap;       // bitmap for marking GC
        StgPtr  scan;          // scan pointer for copying GC
115 116
    } u;

Simon Marlow's avatar
Simon Marlow committed
117 118 119 120
    struct generation_ *gen;   // generation

    StgWord16 gen_no;          // gen->no, cached
    StgWord16 dest_no;         // number of destination generation
Simon Marlow's avatar
Simon Marlow committed
121
    StgWord16 node;            // which memory node does this block live on?
Simon Marlow's avatar
Simon Marlow committed
122 123

    StgWord16 flags;           // block flags, see below
124

Simon Marlow's avatar
Simon Marlow committed
125 126
    StgWord32 blocks;          // [READ ONLY] no. of blocks in a group
                               // (if group head, 0 otherwise)
127

128
#if SIZEOF_VOID_P == 8
Simon Marlow's avatar
Simon Marlow committed
129
    StgWord32 _padding[3];
130
#else
131
    StgWord32 _padding[0];
132 133
#endif
} bdescr;
134
#endif
135 136 137 138 139 140 141 142 143 144 145

#if SIZEOF_VOID_P == 8
#define BDESCR_SIZE  0x40
#define BDESCR_MASK  0x3f
#define BDESCR_SHIFT 6
#else
#define BDESCR_SIZE  0x20
#define BDESCR_MASK  0x1f
#define BDESCR_SHIFT 5
#endif

146
/* Block contains objects evacuated during this GC */
147
#define BF_EVACUATED 1
148
/* Block is a large object */
149
#define BF_LARGE     2
150
/* Block is pinned */
151
#define BF_PINNED    4
152 153
/* Block is to be marked, not copied. Also used for marked large objects in
 * non-moving heap. */
154
#define BF_MARKED    8
155
/* Block is executable */
156
#define BF_EXEC      32
157 158
/* Block contains only a small amount of live data */
#define BF_FRAGMENTED 64
159 160
/* we know about this block (for finding leaks) */
#define BF_KNOWN     128
161 162
/* Block was swept in the last generation */
#define BF_SWEPT     256
gcampax's avatar
gcampax committed
163 164
/* Block is part of a Compact */
#define BF_COMPACT   512
165 166 167 168 169 170
/* A non-moving allocator segment (see NonMoving.c) */
#define BF_NONMOVING 1024
/* A large object which has been moved to off of oldest_gen->large_objects and
 * onto nonmoving_large_objects. The mark phase ignores objects which aren't
 * so-flagged */
#define BF_NONMOVING_SWEEPING 2048
gcampax's avatar
gcampax committed
171 172
/* Maximum flag value (do not define anything higher than this!) */
#define BF_FLAG_MAX  (1 << 15)
173

174 175
/* Finding the block descriptor for a given block -------------------------- */

Ben Gamari's avatar
Ben Gamari committed
176
#if defined(CMINUSMINUS)
177 178 179 180 181 182 183

#define Bdescr(p) \
    ((((p) &  MBLOCK_MASK & ~BLOCK_MASK) >> (BLOCK_SHIFT-BDESCR_SHIFT)) \
     | ((p) & ~MBLOCK_MASK))

#else

184 185
EXTERN_INLINE bdescr *Bdescr(StgPtr p);
EXTERN_INLINE bdescr *Bdescr(StgPtr p)
186 187
{
  return (bdescr *)
188
    ((((W_)p &  MBLOCK_MASK & ~BLOCK_MASK) >> (BLOCK_SHIFT-BDESCR_SHIFT))
189 190 191 192
     | ((W_)p & ~MBLOCK_MASK)
     );
}

193 194
#endif

195 196 197 198 199
/* Useful Macros ------------------------------------------------------------ */

/* Offset of first real data block in a megablock */

#define FIRST_BLOCK_OFF \
sof's avatar
sof committed
200
   ((W_)BLOCK_ROUND_UP(BDESCR_SIZE * (MBLOCK_SIZE / BLOCK_SIZE)))
201 202 203 204

/* First data block in a given megablock */

#define FIRST_BLOCK(m) ((void *)(FIRST_BLOCK_OFF + (W_)(m)))
205

206 207 208 209 210 211 212 213 214
/* Last data block in a given megablock */

#define LAST_BLOCK(m)  ((void *)(MBLOCK_SIZE-BLOCK_SIZE + (W_)(m)))

/* First real block descriptor in a megablock */

#define FIRST_BDESCR(m) \
   ((bdescr *)((FIRST_BLOCK_OFF>>(BLOCK_SHIFT-BDESCR_SHIFT)) + (W_)(m)))

Simon Marlow's avatar
Simon Marlow committed
215 216 217 218 219
/* Last real block descriptor in a megablock */

#define LAST_BDESCR(m) \
  ((bdescr *)(((MBLOCK_SIZE-BLOCK_SIZE)>>(BLOCK_SHIFT-BDESCR_SHIFT)) + (W_)(m)))

220 221
/* Number of usable blocks in a megablock */

Ben Gamari's avatar
Ben Gamari committed
222
#if !defined(CMINUSMINUS) // already defined in DerivedConstants.h
223
#define BLOCKS_PER_MBLOCK ((MBLOCK_SIZE - FIRST_BLOCK_OFF) / BLOCK_SIZE)
224
#endif
225 226 227 228 229 230 231 232 233 234 235

/* How many blocks in this megablock group */

#define MBLOCK_GROUP_BLOCKS(n) \
   (BLOCKS_PER_MBLOCK + (n-1) * (MBLOCK_SIZE / BLOCK_SIZE))

/* Compute the required size of a megablock group */

#define BLOCKS_TO_MBLOCKS(n) \
   (1 + (W_)MBLOCK_ROUND_UP((n-BLOCKS_PER_MBLOCK) * BLOCK_SIZE) / MBLOCK_SIZE)

236

Ben Gamari's avatar
Ben Gamari committed
237
#if !defined(CMINUSMINUS)
238
/* to the end... */
239

240 241 242 243 244 245 246 247 248 249 250 251 252
/* Double-linked block lists: --------------------------------------------- */

INLINE_HEADER void
dbl_link_onto(bdescr *bd, bdescr **list)
{
  bd->link = *list;
  bd->u.back = NULL;
  if (*list) {
    (*list)->u.back = bd; /* double-link the list */
  }
  *list = bd;
}

Simon Marlow's avatar
Simon Marlow committed
253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277
INLINE_HEADER void
dbl_link_remove(bdescr *bd, bdescr **list)
{
    if (bd->u.back) {
        bd->u.back->link = bd->link;
    } else {
        *list = bd->link;
    }
    if (bd->link) {
        bd->link->u.back = bd->u.back;
    }
}

INLINE_HEADER void
dbl_link_insert_after(bdescr *bd, bdescr *after)
{
    bd->link = after->link;
    bd->u.back = after;
    if (after->link) {
        after->link->u.back = bd;
    }
    after->link = bd;
}

INLINE_HEADER void
278
dbl_link_replace(bdescr *new_, bdescr *old, bdescr **list)
Simon Marlow's avatar
Simon Marlow committed
279
{
280 281
    new_->link = old->link;
    new_->u.back = old->u.back;
Simon Marlow's avatar
Simon Marlow committed
282
    if (old->link) {
283
        old->link->u.back = new_;
Simon Marlow's avatar
Simon Marlow committed
284 285
    }
    if (old->u.back) {
286
        old->u.back->link = new_;
Simon Marlow's avatar
Simon Marlow committed
287
    } else {
288
        *list = new_;
Simon Marlow's avatar
Simon Marlow committed
289 290 291
    }
}

292 293 294 295 296 297
/* Initialisation ---------------------------------------------------------- */

extern void initBlockAllocator(void);

/* Allocation -------------------------------------------------------------- */

298
bdescr *allocGroup(W_ n);
Simon Marlow's avatar
Simon Marlow committed
299 300 301 302 303 304 305 306 307

EXTERN_INLINE bdescr* allocBlock(void);
EXTERN_INLINE bdescr* allocBlock(void)
{
    return allocGroup(1);
}

bdescr *allocGroupOnNode(uint32_t node, W_ n);

308 309 310 311 312 313 314
// Allocate n blocks, aligned at n-block boundary. The returned bdescr will
// have this invariant
//
//     bdescr->start % BLOCK_SIZE*n == 0
//
bdescr *allocAlignedGroupOnNode(uint32_t node, W_ n);

Simon Marlow's avatar
Simon Marlow committed
315 316 317 318 319
EXTERN_INLINE bdescr* allocBlockOnNode(uint32_t node);
EXTERN_INLINE bdescr* allocBlockOnNode(uint32_t node)
{
    return allocGroupOnNode(node,1);
}
320 321

// versions that take the storage manager lock for you:
322
bdescr *allocGroup_lock(W_ n);
323
bdescr *allocBlock_lock(void);
324

Simon Marlow's avatar
Simon Marlow committed
325 326 327
bdescr *allocGroupOnNode_lock(uint32_t node, W_ n);
bdescr *allocBlockOnNode_lock(uint32_t node);

328 329
/* De-Allocation ----------------------------------------------------------- */

330 331 332 333 334 335
void freeGroup(bdescr *p);
void freeChain(bdescr *p);

// versions that take the storage manager lock for you:
void freeGroup_lock(bdescr *p);
void freeChain_lock(bdescr *p);
336

337
bdescr * splitBlockGroup (bdescr *bd, uint32_t blocks);
338

339
/* Round a value to megablocks --------------------------------------------- */
340

341 342
// We want to allocate an object around a given size, round it up or
// down to the nearest size that will fit in an mblock group.
343 344
INLINE_HEADER StgWord
round_to_mblocks(StgWord words)
345
{
346 347 348 349 350 351 352 353 354 355 356 357 358
    if (words > BLOCKS_PER_MBLOCK * BLOCK_SIZE_W) {
        // first, ignore the gap at the beginning of the first mblock by
        // adding it to the total words.  Then we can pretend we're
        // dealing in a uniform unit of megablocks.
        words += FIRST_BLOCK_OFF/sizeof(W_);

        if ((words % MBLOCK_SIZE_W) < (MBLOCK_SIZE_W / 2)) {
            words = (words / MBLOCK_SIZE_W) * MBLOCK_SIZE_W;
        } else {
            words = ((words / MBLOCK_SIZE_W) + 1) * MBLOCK_SIZE_W;
        }

        words -= FIRST_BLOCK_OFF/sizeof(W_);
359
    }
360
    return words;
361 362 363
}

#endif /* !CMINUSMINUS */