1 /* -----------------------------------------------------------------------------
2 * $Id: BlockAlloc.c,v 1.2 1998/12/02 13:28:12 simonm Exp $
4 * The block allocator and free list manager.
6 * This is the architecture independent part of the block allocator.
7 * It requires only the following support from the operating system:
11 * returns the address of an MBLOCK_SIZE region of memory, aligned on
12 * an MBLOCK_SIZE boundary. There is no requirement for successive
13 * calls to getMBlock to return strictly increasing addresses.
15 * ---------------------------------------------------------------------------*/
20 #include "BlockAlloc.h"
23 static void initMBlock(void *mblock);
24 static bdescr *allocMegaGroup(nat mblocks);
25 static void freeMegaGroup(bdescr *bd);
27 static bdescr *free_list;
29 /* -----------------------------------------------------------------------------
31 -------------------------------------------------------------------------- */
33 void initBlockAllocator(void)
38 /* -----------------------------------------------------------------------------
40 -------------------------------------------------------------------------- */
43 initGroup(nat n, bdescr *head)
50 head->free = head->start;
51 for (i=1, bd = head+1; i < n; i++, bd++) {
64 if (n > BLOCKS_PER_MBLOCK) {
65 return allocMegaGroup(BLOCKS_TO_MBLOCKS(n));
69 for (bd = free_list; bd != NULL; bd = bd->link) {
70 if (bd->blocks == n) { /* exactly the right size! */
72 /* no initialisation necessary - this is already a
73 * self-contained block group. */
76 if (bd->blocks > n) { /* block too big... */
77 bd->blocks -= n; /* take a chunk off the *end* */
79 initGroup(n, bd); /* initialise it */
85 mblock = getMBlock(); /* get a new megablock */
86 initMBlock(mblock); /* initialise the start fields */
87 bd = FIRST_BDESCR(mblock);
88 initGroup(n,bd); /* we know the group will fit */
89 initGroup(BLOCKS_PER_MBLOCK-n, bd+n);
90 freeGroup(bd+n); /* add the rest on to the free list */
100 /* -----------------------------------------------------------------------------
101 Any request larger than BLOCKS_PER_MBLOCK needs a megablock group.
102 First, search the free list for enough contiguous megablocks to
103 fulfill the request - if we don't have enough, we need to
104 allocate some new ones.
106 A megablock group looks just like a normal block group, except that
107 the blocks field in the head will be larger than BLOCKS_PER_MBLOCK.
109 Note that any objects placed in this group must start in the first
110 megablock, since the other blocks don't have block descriptors.
111 -------------------------------------------------------------------------- */
114 allocMegaGroup(nat n)
117 bdescr *bd, *last, *grp_start, *grp_prev;
123 for (bd = free_list; bd != NULL; bd = bd->link) {
125 if (bd->blocks == BLOCKS_PER_MBLOCK) { /* whole megablock found */
127 if (grp_start == NULL) { /* is it the first one we've found? */
135 if (mbs_found == n) { /* found enough contig megablocks? */
140 else { /* only a partial megablock, start again */
147 /* found all the megablocks we need on the free list
149 if (mbs_found == n) {
150 /* remove the megablocks from the free list */
151 if (grp_prev == NULL) { /* bd now points to the last mblock */
152 free_list = bd->link;
154 grp_prev->link = bd->link;
158 /* the free list wasn't sufficient, allocate all new mblocks.
161 void *mblock = getMBlocks(n);
162 initMBlock(mblock); /* only need to init the 1st one */
163 grp_start = FIRST_BDESCR(mblock);
166 /* set up the megablock group */
167 initGroup(BLOCKS_PER_MBLOCK, grp_start);
168 grp_start->blocks = MBLOCK_GROUP_BLOCKS(n);
172 /* -----------------------------------------------------------------------------
174 -------------------------------------------------------------------------- */
176 /* coalesce the group p with p->link if possible.
178 * Returns p->link if no coalescing was done, otherwise returns a
179 * pointer to the newly enlarged group p.
182 static inline bdescr *
189 if (q != NULL && p->start + p->blocks * BLOCK_SIZE_W == q->start) {
191 p->blocks += q->blocks;
193 for (i = 0, bd = q; i < q->blocks; bd++, i++) {
207 /* are we dealing with a megablock group? */
208 if (p->blocks > BLOCKS_PER_MBLOCK) {
213 /* find correct place in free list to place new group */
215 for (bd = free_list; bd != NULL && bd->start < p->start;
220 /* now, last = previous group (or NULL) */
225 /* coalesce with previous group if possible */
226 p->link = last->link;
231 /* coalesce with next group if possible */
233 IF_DEBUG(sanity, checkFreeListSanity());
237 freeMegaGroup(bdescr *p)
241 n = p->blocks * BLOCK_SIZE / MBLOCK_SIZE + 1;
242 for (; n > 0; (W_)p += MBLOCK_SIZE, n--) {
243 initMBlock((void *)((W_)p & ~MBLOCK_MASK));
244 initGroup(BLOCKS_PER_MBLOCK, p);
250 freeChain(bdescr *bd)
256 bd->free = (void *)-1; /* indicates that this block is free */
264 initMBlock(void *mblock)
269 /* the first few Bdescr's in a block are unused, so we don't want to
270 * put them all on the free list.
272 block = FIRST_BLOCK(mblock);
273 bd = FIRST_BDESCR(mblock);
275 /* Initialise the start field of each block descriptor
277 for (; block <= LAST_BLOCK(mblock); bd += 1, (lnat)block += BLOCK_SIZE) {
282 /* -----------------------------------------------------------------------------
284 -------------------------------------------------------------------------- */
288 checkFreeListSanity(void)
292 for (bd = free_list; bd != NULL; bd = bd->link) {
293 IF_DEBUG(block_alloc,
294 fprintf(stderr,"group at 0x%x, length %d blocks\n",
295 (nat)bd->start, bd->blocks));
296 ASSERT(bd->blocks > 0);
297 if (bd->link != NULL) {
298 /* make sure we're fully coalesced */
299 ASSERT(bd->start + bd->blocks * BLOCK_SIZE_W != bd->link->start);
300 ASSERT(bd->start < bd->link->start);