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 88 89 90 91 92 93


struct NonmovingSegmentInfo {
  StgWord8 log_block_size;
  StgWord16 next_free_snap;
};

94
typedef struct bdescr_ {
Simon Marlow's avatar
Simon Marlow committed
95 96 97

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

98

99 100 101 102 103 104 105 106 107 108 109 110
    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.
111
        struct NonmovingSegmentInfo nonmoving_segment;
112
    };
Simon Marlow's avatar
Simon Marlow committed
113 114 115

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

116
    union {
Simon Marlow's avatar
Simon Marlow committed
117 118 119
        struct bdescr_ *back;  // used (occasionally) for doubly-linked lists
        StgWord *bitmap;       // bitmap for marking GC
        StgPtr  scan;          // scan pointer for copying GC
120 121
    } u;

Simon Marlow's avatar
Simon Marlow committed
122 123 124 125
    struct generation_ *gen;   // generation

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

    StgWord16 flags;           // block flags, see below
129

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

133
#if SIZEOF_VOID_P == 8
Simon Marlow's avatar
Simon Marlow committed
134
    StgWord32 _padding[3];
135
#else
136
    StgWord32 _padding[0];
137 138
#endif
} bdescr;
139
#endif
140 141 142 143 144 145 146 147 148 149 150

#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

151
/* Block contains objects evacuated during this GC */
152
#define BF_EVACUATED 1
153
/* Block is a large object */
154
#define BF_LARGE     2
155
/* Block is pinned */
156
#define BF_PINNED    4
157 158
/* Block is to be marked, not copied. Also used for marked large objects in
 * non-moving heap. */
159
#define BF_MARKED    8
160
/* Block is executable */
161
#define BF_EXEC      32
162 163
/* Block contains only a small amount of live data */
#define BF_FRAGMENTED 64
164 165
/* we know about this block (for finding leaks) */
#define BF_KNOWN     128
166 167
/* Block was swept in the last generation */
#define BF_SWEPT     256
gcampax's avatar
gcampax committed
168 169
/* Block is part of a Compact */
#define BF_COMPACT   512
170 171 172 173 174 175
/* 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
176 177
/* Maximum flag value (do not define anything higher than this!) */
#define BF_FLAG_MAX  (1 << 15)
178

179 180
/* Finding the block descriptor for a given block -------------------------- */

Ben Gamari's avatar
Ben Gamari committed
181
#if defined(CMINUSMINUS)
182 183 184 185 186 187 188

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

#else

189 190
EXTERN_INLINE bdescr *Bdescr(StgPtr p);
EXTERN_INLINE bdescr *Bdescr(StgPtr p)
191 192
{
  return (bdescr *)
193
    ((((W_)p &  MBLOCK_MASK & ~BLOCK_MASK) >> (BLOCK_SHIFT-BDESCR_SHIFT))
194 195 196 197
     | ((W_)p & ~MBLOCK_MASK)
     );
}

198 199
#endif

200 201 202 203 204
/* Useful Macros ------------------------------------------------------------ */

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

#define FIRST_BLOCK_OFF \
sof's avatar
sof committed
205
   ((W_)BLOCK_ROUND_UP(BDESCR_SIZE * (MBLOCK_SIZE / BLOCK_SIZE)))
206 207 208 209

/* First data block in a given megablock */

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

211 212 213 214 215 216 217 218 219
/* 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
220 221 222 223 224
/* Last real block descriptor in a megablock */

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

225 226
/* Number of usable blocks in a megablock */

Ben Gamari's avatar
Ben Gamari committed
227
#if !defined(CMINUSMINUS) // already defined in DerivedConstants.h
228
#define BLOCKS_PER_MBLOCK ((MBLOCK_SIZE - FIRST_BLOCK_OFF) / BLOCK_SIZE)
229
#endif
230 231 232 233 234 235 236 237 238 239 240

/* 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)

241

Ben Gamari's avatar
Ben Gamari committed
242
#if !defined(CMINUSMINUS)
243
/* to the end... */
244

245 246 247 248 249 250 251 252 253 254 255 256 257
/* 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
258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282
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
283
dbl_link_replace(bdescr *new_, bdescr *old, bdescr **list)
Simon Marlow's avatar
Simon Marlow committed
284
{
285 286
    new_->link = old->link;
    new_->u.back = old->u.back;
Simon Marlow's avatar
Simon Marlow committed
287
    if (old->link) {
288
        old->link->u.back = new_;
Simon Marlow's avatar
Simon Marlow committed
289 290
    }
    if (old->u.back) {
291
        old->u.back->link = new_;
Simon Marlow's avatar
Simon Marlow committed
292
    } else {
293
        *list = new_;
Simon Marlow's avatar
Simon Marlow committed
294 295 296
    }
}

297 298 299 300 301 302
/* Initialisation ---------------------------------------------------------- */

extern void initBlockAllocator(void);

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

Simon Marlow's avatar
Simon Marlow committed
303
bdescr *allocGroup(W_ n);
Simon Marlow's avatar
Simon Marlow committed
304 305 306 307 308 309 310 311 312

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

bdescr *allocGroupOnNode(uint32_t node, W_ n);

313 314 315 316 317 318 319
// 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
320 321 322 323 324
EXTERN_INLINE bdescr* allocBlockOnNode(uint32_t node);
EXTERN_INLINE bdescr* allocBlockOnNode(uint32_t node)
{
    return allocGroupOnNode(node,1);
}
325 326

// versions that take the storage manager lock for you:
Simon Marlow's avatar
Simon Marlow committed
327
bdescr *allocGroup_lock(W_ n);
328
bdescr *allocBlock_lock(void);
329

Simon Marlow's avatar
Simon Marlow committed
330 331 332
bdescr *allocGroupOnNode_lock(uint32_t node, W_ n);
bdescr *allocBlockOnNode_lock(uint32_t node);

333 334
/* De-Allocation ----------------------------------------------------------- */

335 336 337 338 339 340
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);
341

342
bdescr * splitBlockGroup (bdescr *bd, uint32_t blocks);
343

344
/* Round a value to megablocks --------------------------------------------- */
345

346 347
// 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.
348 349
INLINE_HEADER StgWord
round_to_mblocks(StgWord words)
350
{
351 352 353 354 355 356 357 358 359 360 361 362 363
    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_);
364
    }
365
    return words;
366 367 368
}

#endif /* !CMINUSMINUS */