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