1 /* -----------------------------------------------------------------------------
2 * $Id: BlockAlloc.c,v 1.13 2001/11/08 14:42:11 simonmar Exp $
4 * (c) The GHC Team 1998-2000
6 * The block allocator and free list manager.
8 * This is the architecture independent part of the block allocator.
9 * It requires only the following support from the operating system:
13 * returns the address of an MBLOCK_SIZE region of memory, aligned on
14 * an MBLOCK_SIZE boundary. There is no requirement for successive
15 * calls to getMBlock to return strictly increasing addresses.
17 * ---------------------------------------------------------------------------*/
19 #include "PosixSource.h"
23 #include "BlockAlloc.h"
26 static void initMBlock(void *mblock);
27 static bdescr *allocMegaGroup(nat mblocks);
28 static void freeMegaGroup(bdescr *bd);
30 static bdescr *free_list;
32 /* -----------------------------------------------------------------------------
34 -------------------------------------------------------------------------- */
36 void initBlockAllocator(void)
41 /* -----------------------------------------------------------------------------
43 -------------------------------------------------------------------------- */
46 initGroup(nat n, bdescr *head)
53 head->free = head->start;
54 for (i=1, bd = head+1; i < n; i++, bd++) {
70 if (n > BLOCKS_PER_MBLOCK) {
71 return allocMegaGroup(BLOCKS_TO_MBLOCKS(n));
75 for (bd = free_list; bd != NULL; bd = bd->link) {
76 if (bd->blocks == n) { /* exactly the right size! */
78 /* no initialisation necessary - this is already a
79 * self-contained block group. */
81 bd->free = bd->start; /* block isn't free now */
85 if (bd->blocks > n) { /* block too big... */
86 bd->blocks -= n; /* take a chunk off the *end* */
88 initGroup(n, bd); /* initialise it */
94 mblock = getMBlock(); /* get a new megablock */
95 initMBlock(mblock); /* initialise the start fields */
96 bd = FIRST_BDESCR(mblock);
97 initGroup(n,bd); /* we know the group will fit */
98 if (n < BLOCKS_PER_MBLOCK) {
99 initGroup(BLOCKS_PER_MBLOCK-n, bd+n);
100 freeGroup(bd+n); /* add the rest on to the free list */
108 return allocGroup(1);
111 /* -----------------------------------------------------------------------------
112 Any request larger than BLOCKS_PER_MBLOCK needs a megablock group.
113 First, search the free list for enough contiguous megablocks to
114 fulfill the request - if we don't have enough, we need to
115 allocate some new ones.
117 A megablock group looks just like a normal block group, except that
118 the blocks field in the head will be larger than BLOCKS_PER_MBLOCK.
120 Note that any objects placed in this group must start in the first
121 megablock, since the other blocks don't have block descriptors.
122 -------------------------------------------------------------------------- */
125 allocMegaGroup(nat n)
128 bdescr *bd, *last, *grp_start, *grp_prev;
134 for (bd = free_list; bd != NULL; bd = bd->link) {
136 if (bd->blocks == BLOCKS_PER_MBLOCK) { /* whole megablock found */
138 /* is it the first one we've found or a non-contiguous megablock? */
139 if (grp_start == NULL ||
140 bd->start != last->start + MBLOCK_SIZE/sizeof(W_)) {
148 if (mbs_found == n) { /* found enough contig megablocks? */
153 else { /* only a partial megablock, start again */
160 /* found all the megablocks we need on the free list
162 if (mbs_found == n) {
163 /* remove the megablocks from the free list */
164 if (grp_prev == NULL) { /* bd now points to the last mblock */
165 free_list = bd->link;
167 grp_prev->link = bd->link;
171 /* the free list wasn't sufficient, allocate all new mblocks.
174 void *mblock = getMBlocks(n);
175 initMBlock(mblock); /* only need to init the 1st one */
176 grp_start = FIRST_BDESCR(mblock);
179 /* set up the megablock group */
180 initGroup(BLOCKS_PER_MBLOCK, grp_start);
181 grp_start->blocks = MBLOCK_GROUP_BLOCKS(n);
185 /* -----------------------------------------------------------------------------
187 -------------------------------------------------------------------------- */
189 /* coalesce the group p with p->link if possible.
191 * Returns p->link if no coalescing was done, otherwise returns a
192 * pointer to the newly enlarged group p.
195 static inline bdescr *
202 if (q != NULL && p->start + p->blocks * BLOCK_SIZE_W == q->start) {
204 p->blocks += q->blocks;
207 for (i = 0, bd = q; i < blocks; bd++, i++) {
222 /* are we dealing with a megablock group? */
223 if (p->blocks > BLOCKS_PER_MBLOCK) {
229 p->free = (void *)-1; /* indicates that this block is free */
232 /* fill the block group with garbage if sanity checking is on */
233 IF_DEBUG(sanity,memset(p->start, 0xaa, p->blocks * BLOCK_SIZE));
236 /* find correct place in free list to place new group */
238 for (bd = free_list; bd != NULL && bd->start < p->start;
243 /* now, last = previous group (or NULL) */
248 /* coalesce with previous group if possible */
249 p->link = last->link;
254 /* coalesce with next group if possible */
256 IF_DEBUG(sanity, checkFreeListSanity());
260 freeMegaGroup(bdescr *p)
264 n = p->blocks * BLOCK_SIZE / MBLOCK_SIZE + 1;
265 for (; n > 0; (W_)p += MBLOCK_SIZE, n--) {
266 initMBlock((void *)((W_)p & ~MBLOCK_MASK));
267 initGroup(BLOCKS_PER_MBLOCK, p);
273 freeChain(bdescr *bd)
284 initMBlock(void *mblock)
289 /* the first few Bdescr's in a block are unused, so we don't want to
290 * put them all on the free list.
292 block = FIRST_BLOCK(mblock);
293 bd = FIRST_BDESCR(mblock);
295 /* Initialise the start field of each block descriptor
297 for (; block <= LAST_BLOCK(mblock); bd += 1, (lnat)block += BLOCK_SIZE) {
302 /* -----------------------------------------------------------------------------
304 -------------------------------------------------------------------------- */
308 checkWellFormedGroup( bdescr *bd )
312 for (i = 1; i < bd->blocks; i++) {
313 ASSERT(bd[i].blocks == 0);
314 ASSERT(bd[i].free == 0);
315 ASSERT(bd[i].link == bd);
320 checkFreeListSanity(void)
324 for (bd = free_list; bd != NULL; bd = bd->link) {
325 IF_DEBUG(block_alloc,
326 fprintf(stderr,"group at 0x%x, length %d blocks\n",
327 (nat)bd->start, bd->blocks));
328 ASSERT(bd->blocks > 0);
329 checkWellFormedGroup(bd);
330 if (bd->link != NULL) {
331 /* make sure we're fully coalesced */
332 ASSERT(bd->start + bd->blocks * BLOCK_SIZE_W != bd->link->start);
333 ASSERT(bd->start < bd->link->start);
342 lnat total_blocks = 0;
344 for (bd = free_list; bd != NULL; bd = bd->link) {
345 total_blocks += bd->blocks;