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

Simon Marlow's avatar
Simon Marlow committed
9 10
#ifndef RTS_STORAGE_BLOCK_H
#define RTS_STORAGE_BLOCK_H
11 12 13 14 15

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

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

18
#ifdef CMINUSMINUS
19
#define BLOCK_SIZE   (1<<BLOCK_SHIFT)
20 21 22 23 24
#else
#define BLOCK_SIZE   (1UL<<BLOCK_SHIFT)
// Note [integer overflow]
#endif

25 26 27
#define BLOCK_SIZE_W (BLOCK_SIZE/sizeof(W_))
#define BLOCK_MASK   (BLOCK_SIZE-1)

28
#define BLOCK_ROUND_UP(p)   (((W_)(p)+BLOCK_SIZE-1) & ~BLOCK_MASK)
29 30
#define BLOCK_ROUND_DOWN(p) ((void *) ((W_)(p) & ~BLOCK_MASK))

31
/* Megablock related constants (MBLOCK_SHIFT is defined in Constants.h) */
32

33
#ifdef CMINUSMINUS
34
#define MBLOCK_SIZE    (1<<MBLOCK_SHIFT)
35 36 37 38 39
#else
#define MBLOCK_SIZE    (1UL<<MBLOCK_SHIFT)
// Note [integer overflow]
#endif

40 41 42 43 44 45
#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
46 47 48 49 50
/* 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.
 */
#define LARGE_OBJECT_THRESHOLD ((nat)(BLOCK_SIZE * 8 / 10))
51

52 53 54 55 56 57 58 59 60 61 62 63
/*
 * 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).
 */

64 65 66 67 68 69 70 71 72
/* -----------------------------------------------------------------------------
 * 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
73 74 75 76
// 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.

77 78
#ifndef CMINUSMINUS
typedef struct bdescr_ {
Simon Marlow's avatar
Simon Marlow committed
79 80 81 82 83 84 85 86 87 88 89 90 91 92

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

    StgPtr free;               // first free byte of memory.
                               // 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.

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

93
    union {
Simon Marlow's avatar
Simon Marlow committed
94 95 96
        struct bdescr_ *back;  // used (occasionally) for doubly-linked lists
        StgWord *bitmap;       // bitmap for marking GC
        StgPtr  scan;          // scan pointer for copying GC
97 98
    } u;

Simon Marlow's avatar
Simon Marlow committed
99 100 101 102 103 104 105
    struct generation_ *gen;   // generation

    StgWord16 gen_no;          // gen->no, cached
    StgWord16 dest_no;         // number of destination generation
    StgWord16 _pad1;

    StgWord16 flags;           // block flags, see below
106

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

110
#if SIZEOF_VOID_P == 8
Simon Marlow's avatar
Simon Marlow committed
111
    StgWord32 _padding[3];
112
#else
113
    StgWord32 _padding[0];
114 115
#endif
} bdescr;
116
#endif
117 118 119 120 121 122 123 124 125 126 127

#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

128
/* Block contains objects evacuated during this GC */
129
#define BF_EVACUATED 1
130
/* Block is a large object */
131
#define BF_LARGE     2
132
/* Block is pinned */
133
#define BF_PINNED    4
134 135
/* Block is to be marked, not copied */
#define BF_MARKED    8
136
/* Block is free, and on the free list  (TODO: is this used?) */
137
#define BF_FREE      16
138 139
/* Block is executable */
#define BF_EXEC	     32
140 141
/* Block contains only a small amount of live data */
#define BF_FRAGMENTED 64
142 143
/* we know about this block (for finding leaks) */
#define BF_KNOWN     128
144 145
/* Block was swept in the last generation */
#define BF_SWEPT     256
146

147 148
/* Finding the block descriptor for a given block -------------------------- */

149 150 151 152 153 154 155 156
#ifdef CMINUSMINUS

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

#else

157 158
EXTERN_INLINE bdescr *Bdescr(StgPtr p);
EXTERN_INLINE bdescr *Bdescr(StgPtr p)
159 160 161 162 163 164 165
{
  return (bdescr *)
    ((((W_)p &  MBLOCK_MASK & ~BLOCK_MASK) >> (BLOCK_SHIFT-BDESCR_SHIFT)) 
     | ((W_)p & ~MBLOCK_MASK)
     );
}

166 167
#endif

168 169 170 171 172
/* Useful Macros ------------------------------------------------------------ */

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

#define FIRST_BLOCK_OFF \
sof's avatar
sof committed
173
   ((W_)BLOCK_ROUND_UP(BDESCR_SIZE * (MBLOCK_SIZE / BLOCK_SIZE)))
174 175 176 177 178 179 180 181 182 183 184 185 186 187

/* First data block in a given megablock */

#define FIRST_BLOCK(m) ((void *)(FIRST_BLOCK_OFF + (W_)(m)))
   
/* 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
188 189 190 191 192
/* Last real block descriptor in a megablock */

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

193 194
/* Number of usable blocks in a megablock */

195
#ifndef CMINUSMINUS // already defined in DerivedConstants.h
196
#define BLOCKS_PER_MBLOCK ((MBLOCK_SIZE - FIRST_BLOCK_OFF) / BLOCK_SIZE)
197
#endif
198 199 200 201 202 203 204 205 206 207 208

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

209

210
#ifndef CMINUSMINUS 
211
/* to the end... */
212

213 214 215 216 217 218 219 220 221 222 223 224 225
/* 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
226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250
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
251
dbl_link_replace(bdescr *new_, bdescr *old, bdescr **list)
Simon Marlow's avatar
Simon Marlow committed
252
{
253 254
    new_->link = old->link;
    new_->u.back = old->u.back;
Simon Marlow's avatar
Simon Marlow committed
255
    if (old->link) {
256
        old->link->u.back = new_;
Simon Marlow's avatar
Simon Marlow committed
257 258
    }
    if (old->u.back) {
259
        old->u.back->link = new_;
Simon Marlow's avatar
Simon Marlow committed
260
    } else {
261
        *list = new_;
Simon Marlow's avatar
Simon Marlow committed
262 263 264
    }
}

265 266 267 268 269 270
/* Initialisation ---------------------------------------------------------- */

extern void initBlockAllocator(void);

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

Simon Marlow's avatar
Simon Marlow committed
271
bdescr *allocGroup(W_ n);
272 273 274
bdescr *allocBlock(void);

// versions that take the storage manager lock for you:
Simon Marlow's avatar
Simon Marlow committed
275
bdescr *allocGroup_lock(W_ n);
276
bdescr *allocBlock_lock(void);
277 278 279

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

280 281 282 283 284 285
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);
286

287
bdescr * splitBlockGroup (bdescr *bd, nat blocks);
288

289
/* Round a value to megablocks --------------------------------------------- */
290

291 292
// 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.
293 294
INLINE_HEADER StgWord
round_to_mblocks(StgWord words)
295
{
296 297 298 299 300 301 302 303 304 305 306 307 308
    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_);
309
    }
310
    return words;
311 312
}

313 314 315 316 317 318 319 320 321
INLINE_HEADER StgWord
round_up_to_mblocks(StgWord words)
{
    words += FIRST_BLOCK_OFF/sizeof(W_);
    words = ((words / MBLOCK_SIZE_W) + 1) * MBLOCK_SIZE_W;
    words -= FIRST_BLOCK_OFF/sizeof(W_);
    return words;
}

322
#endif /* !CMINUSMINUS */
Simon Marlow's avatar
Simon Marlow committed
323
#endif /* RTS_STORAGE_BLOCK_H */