1 /* -----------------------------------------------------------------------------
2 *
3 * (c) The GHC Team, 1998-1999
4 *
5 * Block structure for the storage manager
6 *
7 * ---------------------------------------------------------------------------*/
8
9 #pragma once
10
11 #include "ghcconfig.h"
12
13 /* The actual block and megablock-size constants are defined in
14 * includes/Constants.h, all constants here are derived from these.
15 */
16
17 /* Block related constants (BLOCK_SHIFT is defined in Constants.h) */
18
19 #if SIZEOF_LONG == SIZEOF_VOID_P
20 #define UNIT 1UL
21 #elif SIZEOF_LONG_LONG == SIZEOF_VOID_P
22 #define UNIT 1ULL
23 #else
24 #error "Size of pointer is suspicious."
25 #endif
26
27 #if defined(CMINUSMINUS)
28 #define BLOCK_SIZE (1<<BLOCK_SHIFT)
29 #else
30 #define BLOCK_SIZE (UNIT<<BLOCK_SHIFT)
31 // Note [integer overflow]
32 #endif
33
34 #define BLOCK_SIZE_W (BLOCK_SIZE/sizeof(W_))
35 #define BLOCK_MASK (BLOCK_SIZE-1)
36
37 #define BLOCK_ROUND_UP(p) (((W_)(p)+BLOCK_SIZE-1) & ~BLOCK_MASK)
38 #define BLOCK_ROUND_DOWN(p) ((void *) ((W_)(p) & ~BLOCK_MASK))
39
40 /* Megablock related constants (MBLOCK_SHIFT is defined in Constants.h) */
41
42 #if defined(CMINUSMINUS)
43 #define MBLOCK_SIZE (1<<MBLOCK_SHIFT)
44 #else
45 #define MBLOCK_SIZE (UNIT<<MBLOCK_SHIFT)
46 // Note [integer overflow]
47 #endif
48
49 #define MBLOCK_SIZE_W (MBLOCK_SIZE/sizeof(W_))
50 #define MBLOCK_MASK (MBLOCK_SIZE-1)
51
52 #define MBLOCK_ROUND_UP(p) ((void *)(((W_)(p)+MBLOCK_SIZE-1) & ~MBLOCK_MASK))
53 #define MBLOCK_ROUND_DOWN(p) ((void *)((W_)(p) & ~MBLOCK_MASK ))
54
55 /* The largest size an object can be before we give it a block of its
56 * own and treat it as an immovable object during GC, expressed as a
57 * fraction of BLOCK_SIZE.
58 */
59 #define LARGE_OBJECT_THRESHOLD ((uint32_t)(BLOCK_SIZE * 8 / 10))
60
61 /*
62 * Note [integer overflow]
63 *
64 * The UL suffix in BLOCK_SIZE and MBLOCK_SIZE promotes the expression
65 * to an unsigned long, which means that expressions involving these
66 * will be promoted to unsigned long, which makes integer overflow
67 * less likely. Historically, integer overflow in expressions like
68 * (n * BLOCK_SIZE)
69 * where n is int or unsigned int, have caused obscure segfaults in
70 * programs that use large amounts of memory (e.g. #7762, #5086).
71 */
72
73 /* -----------------------------------------------------------------------------
74 * Block descriptor. This structure *must* be the right length, so we
75 * can do pointer arithmetic on pointers to it.
76 */
77
78 /* The block descriptor is 64 bytes on a 64-bit machine, and 32-bytes
79 * on a 32-bit machine.
80 */
81
82 // Note: fields marked with [READ ONLY] must not be modified by the
83 // client of the block allocator API. All other fields can be
84 // freely modified.
85
86 #if !defined(CMINUSMINUS)
87 typedef struct bdescr_ {
88
89 StgPtr start; // [READ ONLY] start addr of memory
90
91 union {
92 StgPtr free; // First free byte of memory.
93 // allocGroup() sets this to the value of start.
94 // NB. during use this value should lie
95 // between start and start + blocks *
96 // BLOCK_SIZE. Values outside this
97 // range are reserved for use by the
98 // block allocator. In particular, the
99 // value (StgPtr)(-1) is used to
100 // indicate that a block is unallocated.
101 //
102 // Unused by the non-moving allocator.
103 struct NonmovingSegmentInfo {
104 StgWord8 log_block_size;
105 StgWord16 next_free_snap;
106 } nonmoving_segment;
107 };
108
109 struct bdescr_ *link; // used for chaining blocks together
110
111 union {
112 struct bdescr_ *back; // used (occasionally) for doubly-linked lists
113 StgWord *bitmap; // bitmap for marking GC
114 StgPtr scan; // scan pointer for copying GC
115 } u;
116
117 struct generation_ *gen; // generation
118
119 StgWord16 gen_no; // gen->no, cached
120 StgWord16 dest_no; // number of destination generation
121 StgWord16 node; // which memory node does this block live on?
122
123 StgWord16 flags; // block flags, see below
124
125 StgWord32 blocks; // [READ ONLY] no. of blocks in a group
126 // (if group head, 0 otherwise)
127
128 #if SIZEOF_VOID_P == 8
129 StgWord32 _padding[3];
130 #else
131 StgWord32 _padding[0];
132 #endif
133 } bdescr;
134 #endif
135
136 #if SIZEOF_VOID_P == 8
137 #define BDESCR_SIZE 0x40
138 #define BDESCR_MASK 0x3f
139 #define BDESCR_SHIFT 6
140 #else
141 #define BDESCR_SIZE 0x20
142 #define BDESCR_MASK 0x1f
143 #define BDESCR_SHIFT 5
144 #endif
145
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 /* Block is to be marked, not copied. Also used for marked large objects in
153 * non-moving heap. */
154 #define BF_MARKED 8
155 /* Block is executable */
156 #define BF_EXEC 32
157 /* Block contains only a small amount of live data */
158 #define BF_FRAGMENTED 64
159 /* we know about this block (for finding leaks) */
160 #define BF_KNOWN 128
161 /* Block was swept in the last generation */
162 #define BF_SWEPT 256
163 /* Block is part of a Compact */
164 #define BF_COMPACT 512
165 /* A non-moving allocator segment (see NonMoving.c) */
166 #define BF_NONMOVING 1024
167 /* A large object which has been moved to off of oldest_gen->large_objects and
168 * onto nonmoving_large_objects. The mark phase ignores objects which aren't
169 * so-flagged */
170 #define BF_NONMOVING_SWEEPING 2048
171 /* Maximum flag value (do not define anything higher than this!) */
172 #define BF_FLAG_MAX (1 << 15)
173
174 /* Finding the block descriptor for a given block -------------------------- */
175
176 #if defined(CMINUSMINUS)
177
178 #define Bdescr(p) \
179 ((((p) & MBLOCK_MASK & ~BLOCK_MASK) >> (BLOCK_SHIFT-BDESCR_SHIFT)) \
180 | ((p) & ~MBLOCK_MASK))
181
182 #else
183
184 EXTERN_INLINE bdescr *Bdescr(StgPtr p);
Bdescr(StgPtr p)185 EXTERN_INLINE bdescr *Bdescr(StgPtr p)
186 {
187 return (bdescr *)
188 ((((W_)p & MBLOCK_MASK & ~BLOCK_MASK) >> (BLOCK_SHIFT-BDESCR_SHIFT))
189 | ((W_)p & ~MBLOCK_MASK)
190 );
191 }
192
193 #endif
194
195 /* Useful Macros ------------------------------------------------------------ */
196
197 /* Offset of first real data block in a megablock */
198
199 #define FIRST_BLOCK_OFF \
200 ((W_)BLOCK_ROUND_UP(BDESCR_SIZE * (MBLOCK_SIZE / BLOCK_SIZE)))
201
202 /* First data block in a given megablock */
203
204 #define FIRST_BLOCK(m) ((void *)(FIRST_BLOCK_OFF + (W_)(m)))
205
206 /* Last data block in a given megablock */
207
208 #define LAST_BLOCK(m) ((void *)(MBLOCK_SIZE-BLOCK_SIZE + (W_)(m)))
209
210 /* First real block descriptor in a megablock */
211
212 #define FIRST_BDESCR(m) \
213 ((bdescr *)((FIRST_BLOCK_OFF>>(BLOCK_SHIFT-BDESCR_SHIFT)) + (W_)(m)))
214
215 /* Last real block descriptor in a megablock */
216
217 #define LAST_BDESCR(m) \
218 ((bdescr *)(((MBLOCK_SIZE-BLOCK_SIZE)>>(BLOCK_SHIFT-BDESCR_SHIFT)) + (W_)(m)))
219
220 /* Number of usable blocks in a megablock */
221
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 /* How many blocks in this megablock group */
227
228 #define MBLOCK_GROUP_BLOCKS(n) \
229 (BLOCKS_PER_MBLOCK + (n-1) * (MBLOCK_SIZE / BLOCK_SIZE))
230
231 /* Compute the required size of a megablock group */
232
233 #define BLOCKS_TO_MBLOCKS(n) \
234 (1 + (W_)MBLOCK_ROUND_UP((n-BLOCKS_PER_MBLOCK) * BLOCK_SIZE) / MBLOCK_SIZE)
235
236
237 #if !defined(CMINUSMINUS)
238 /* to the end... */
239
240 /* Double-linked block lists: --------------------------------------------- */
241
242 INLINE_HEADER void
dbl_link_onto(bdescr * bd,bdescr ** list)243 dbl_link_onto(bdescr *bd, bdescr **list)
244 {
245 bd->link = *list;
246 bd->u.back = NULL;
247 if (*list) {
248 (*list)->u.back = bd; /* double-link the list */
249 }
250 *list = bd;
251 }
252
253 INLINE_HEADER void
dbl_link_remove(bdescr * bd,bdescr ** list)254 dbl_link_remove(bdescr *bd, bdescr **list)
255 {
256 if (bd->u.back) {
257 bd->u.back->link = bd->link;
258 } else {
259 *list = bd->link;
260 }
261 if (bd->link) {
262 bd->link->u.back = bd->u.back;
263 }
264 }
265
266 INLINE_HEADER void
dbl_link_insert_after(bdescr * bd,bdescr * after)267 dbl_link_insert_after(bdescr *bd, bdescr *after)
268 {
269 bd->link = after->link;
270 bd->u.back = after;
271 if (after->link) {
272 after->link->u.back = bd;
273 }
274 after->link = bd;
275 }
276
277 INLINE_HEADER void
dbl_link_replace(bdescr * new_,bdescr * old,bdescr ** list)278 dbl_link_replace(bdescr *new_, bdescr *old, bdescr **list)
279 {
280 new_->link = old->link;
281 new_->u.back = old->u.back;
282 if (old->link) {
283 old->link->u.back = new_;
284 }
285 if (old->u.back) {
286 old->u.back->link = new_;
287 } else {
288 *list = new_;
289 }
290 }
291
292 /* Initialisation ---------------------------------------------------------- */
293
294 extern void initBlockAllocator(void);
295
296 /* Allocation -------------------------------------------------------------- */
297
298 bdescr *allocGroup(W_ n);
299
300 EXTERN_INLINE bdescr* allocBlock(void);
allocBlock(void)301 EXTERN_INLINE bdescr* allocBlock(void)
302 {
303 return allocGroup(1);
304 }
305
306 bdescr *allocGroupOnNode(uint32_t node, W_ n);
307
308 // Allocate n blocks, aligned at n-block boundary. The returned bdescr will
309 // have this invariant
310 //
311 // bdescr->start % BLOCK_SIZE*n == 0
312 //
313 bdescr *allocAlignedGroupOnNode(uint32_t node, W_ n);
314
315 EXTERN_INLINE bdescr* allocBlockOnNode(uint32_t node);
allocBlockOnNode(uint32_t node)316 EXTERN_INLINE bdescr* allocBlockOnNode(uint32_t node)
317 {
318 return allocGroupOnNode(node,1);
319 }
320
321 // versions that take the storage manager lock for you:
322 bdescr *allocGroup_lock(W_ n);
323 bdescr *allocBlock_lock(void);
324
325 bdescr *allocGroupOnNode_lock(uint32_t node, W_ n);
326 bdescr *allocBlockOnNode_lock(uint32_t node);
327
328 /* De-Allocation ----------------------------------------------------------- */
329
330 void freeGroup(bdescr *p);
331 void freeChain(bdescr *p);
332
333 // versions that take the storage manager lock for you:
334 void freeGroup_lock(bdescr *p);
335 void freeChain_lock(bdescr *p);
336
337 bdescr * splitBlockGroup (bdescr *bd, uint32_t blocks);
338
339 /* Round a value to megablocks --------------------------------------------- */
340
341 // We want to allocate an object around a given size, round it up or
342 // down to the nearest size that will fit in an mblock group.
343 INLINE_HEADER StgWord
round_to_mblocks(StgWord words)344 round_to_mblocks(StgWord words)
345 {
346 if (words > BLOCKS_PER_MBLOCK * BLOCK_SIZE_W) {
347 // first, ignore the gap at the beginning of the first mblock by
348 // adding it to the total words. Then we can pretend we're
349 // dealing in a uniform unit of megablocks.
350 words += FIRST_BLOCK_OFF/sizeof(W_);
351
352 if ((words % MBLOCK_SIZE_W) < (MBLOCK_SIZE_W / 2)) {
353 words = (words / MBLOCK_SIZE_W) * MBLOCK_SIZE_W;
354 } else {
355 words = ((words / MBLOCK_SIZE_W) + 1) * MBLOCK_SIZE_W;
356 }
357
358 words -= FIRST_BLOCK_OFF/sizeof(W_);
359 }
360 return words;
361 }
362
363 #endif /* !CMINUSMINUS */
364