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