/* -----------------------------------------------------------------------------
- * $Id: BlockAlloc.c,v 1.9 2001/07/23 17:23:19 simonmar Exp $
*
- * (c) The GHC Team 1998-2000
+ * (c) The GHC Team 1998-2005
*
* The block allocator and free list manager.
*
*
* ---------------------------------------------------------------------------*/
+#include "PosixSource.h"
#include "Rts.h"
#include "RtsFlags.h"
#include "RtsUtils.h"
#include "BlockAlloc.h"
#include "MBlock.h"
+#include <string.h>
+
static void initMBlock(void *mblock);
static bdescr *allocMegaGroup(nat mblocks);
static void freeMegaGroup(bdescr *bd);
-static bdescr *free_list;
+static bdescr *free_list = NULL;
/* -----------------------------------------------------------------------------
Initialisation
void initBlockAllocator(void)
{
- free_list = NULL;
+ // The free list starts off NULL
}
/* -----------------------------------------------------------------------------
Allocation
-------------------------------------------------------------------------- */
-static inline void
-initGroup(nat n, bdescr *head)
+STATIC_INLINE void
+initGroupTail(nat n, bdescr *head, bdescr *tail)
{
- bdescr *bd;
- nat i;
+ bdescr *bd;
+ nat i;
+
+ for (i=0, bd = tail; i < n; i++, bd++) {
+ bd->flags = 0;
+ bd->free = 0;
+ bd->blocks = 0;
+ bd->link = head;
+ }
+}
+STATIC_INLINE void
+initGroup(nat n, bdescr *head)
+{
if (n != 0) {
head->blocks = n;
- head->free = head->start;
- for (i=1, bd = head+1; i < n; i++, bd++) {
- bd->free = 0;
- bd->link = head;
- }
+ head->free = head->start;
+ head->link = NULL;
+ head->flags = 0;
+ initGroupTail( n-1, head, head+1 );
}
}
last = &free_list;
for (bd = free_list; bd != NULL; bd = bd->link) {
if (bd->blocks == n) { /* exactly the right size! */
+ if (bd->link) {
+ bd->link->u.back = bd->u.back;
+ }
*last = bd->link;
/* no initialisation necessary - this is already a
* self-contained block group. */
-#ifdef DEBUG
- bd->free = bd->start; /* block isn't free now */
-#endif
+ bd->flags = 0;
+ bd->free = bd->start;
+ bd->link = NULL;
return bd;
}
if (bd->blocks > n) { /* block too big... */
last = bd;
}
- /* found all the megablocks we need on the free list
- */
+ /* found all the megablocks we need on the free list */
if (mbs_found == n) {
/* remove the megablocks from the free list */
if (grp_prev == NULL) { /* bd now points to the last mblock */
free_list = bd->link;
+ if (free_list) {
+ free_list->u.back = NULL;
+ }
} else {
grp_prev->link = bd->link;
+ if (bd->link) {
+ bd->link->u.back = grp_prev;
+ }
}
}
- /* the free list wasn't sufficient, allocate all new mblocks.
- */
+ /* the free list wasn't sufficient, allocate all new mblocks. */
else {
void *mblock = getMBlocks(n);
initMBlock(mblock); /* only need to init the 1st one */
De-Allocation
-------------------------------------------------------------------------- */
-/* coalesce the group p with p->link if possible.
+/* coalesce the group p with its predecessor and successor groups, if possible
*
- * Returns p->link if no coalescing was done, otherwise returns a
+ * Returns NULL if no coalescing was done, otherwise returns a
* pointer to the newly enlarged group p.
*/
-static inline bdescr *
+STATIC_INLINE bdescr *
coalesce(bdescr *p)
{
- bdescr *bd, *q;
- nat i;
-
- q = p->link;
- if (q != NULL && p->start + p->blocks * BLOCK_SIZE_W == q->start) {
- /* can coalesce */
- p->blocks += q->blocks;
- p->link = q->link;
- for (i = 0, bd = q; i < q->blocks; bd++, i++) {
- bd->free = 0;
- bd->link = p;
+ bdescr *first, *q, *result = NULL;
+
+ /* Get first megablock descriptor */
+ first = FIRST_BDESCR(MBLOCK_ROUND_DOWN(p->start));
+
+ /* Attempt to coalesce with predecessor if not the first block */
+ if (p != first) {
+ q = p - 1;
+ if (!q->blocks) { // not a block head?
+ q = q->link; // find the head.
+ }
+ /* Predecessor is free? */
+ if (q->flags & BF_FREE) {
+ q->blocks += p->blocks;
+ initGroupTail( p->blocks, q, p );
+ p = result = q;
+ }
}
- return p;
- }
- return q;
+
+ /* Attempt to coalesce with successor if not the last block */
+ q = p + p->blocks;
+ if (q != first + BLOCKS_PER_MBLOCK) {
+ /* Successor is free */
+ if (q->flags & BF_FREE) {
+ if (result) {
+ /* p is on free_list, q is on free_list, unlink
+ * q completely and patch up list
+ */
+ if (q->u.back) {
+ q->u.back->link = q->link;
+ }
+ if (q->link) {
+ q->link->u.back = q->u.back;
+ }
+ if (free_list == q) {
+ free_list = q->link;
+ }
+ } else {
+ /* p is not on free_list just assume q's links */
+ p->u.back = q->u.back;
+ if (p->u.back) {
+ p->u.back->link = p;
+ }
+ p->link = q->link;
+ if (p->link) {
+ p->link->u.back = p;
+ }
+ if (q == free_list) {
+ free_list = p;
+ free_list->u.back = NULL;
+ }
+ }
+
+ p->blocks += q->blocks;
+ initGroupTail( q->blocks, p, q );
+ result = p;
+ }
+ }
+
+ return result;
}
void
freeGroup(bdescr *p)
{
- bdescr *bd, *last;
-
/* are we dealing with a megablock group? */
if (p->blocks > BLOCKS_PER_MBLOCK) {
freeMegaGroup(p);
return;
}
-#ifdef DEBUG
- p->free = (void *)-1; /* indicates that this block is free */
+ p->flags = BF_FREE;
+ p->u.back = NULL;
+ p->link = NULL;
p->step = NULL;
p->gen_no = 0;
/* fill the block group with garbage if sanity checking is on */
IF_DEBUG(sanity,memset(p->start, 0xaa, p->blocks * BLOCK_SIZE));
-#endif
- /* find correct place in free list to place new group */
- last = NULL;
- for (bd = free_list; bd != NULL && bd->start < p->start;
- bd = bd->link) {
- last = bd;
+ if (!coalesce(p)) {
+ dbl_link_onto(p, &free_list);
}
- /* now, last = previous group (or NULL) */
- if (last == NULL) {
- p->link = free_list;
- free_list = p;
- } else {
- /* coalesce with previous group if possible */
- p->link = last->link;
- last->link = p;
- p = coalesce(last);
- }
-
- /* coalesce with next group if possible */
- coalesce(p);
IF_DEBUG(sanity, checkFreeListSanity());
}
freeMegaGroup(bdescr *p)
{
nat n;
+ void *q = p;
- n = p->blocks * BLOCK_SIZE / MBLOCK_SIZE + 1;
- for (; n > 0; (W_)p += MBLOCK_SIZE, n--) {
- initMBlock((void *)((W_)p & ~MBLOCK_MASK));
- initGroup(BLOCKS_PER_MBLOCK, p);
- freeGroup(p);
+ n = ((bdescr *)q)->blocks * BLOCK_SIZE / MBLOCK_SIZE + 1;
+ for (; n > 0; q += MBLOCK_SIZE, n--) {
+ initMBlock(MBLOCK_ROUND_DOWN(q));
+ initGroup(BLOCKS_PER_MBLOCK, (bdescr *)q);
+ freeGroup((bdescr *)q);
}
}
/* Initialise the start field of each block descriptor
*/
- for (; block <= LAST_BLOCK(mblock); bd += 1, (lnat)block += BLOCK_SIZE) {
+ for (; block <= LAST_BLOCK(mblock); bd += 1, block += BLOCK_SIZE) {
bd->start = block;
}
}
-------------------------------------------------------------------------- */
#ifdef DEBUG
+static void
+checkWellFormedGroup(bdescr *bd)
+{
+ nat i;
+
+ for (i = 1; i < bd->blocks; i++) {
+ ASSERT(bd[i].blocks == 0);
+ ASSERT(bd[i].free == 0);
+ ASSERT(bd[i].link == bd);
+ }
+}
+
void
checkFreeListSanity(void)
{
for (bd = free_list; bd != NULL; bd = bd->link) {
IF_DEBUG(block_alloc,
- fprintf(stderr,"group at 0x%x, length %d blocks\n",
- (nat)bd->start, bd->blocks));
+ debugBelch("group at 0x%x, length %d blocks\n",
+ (nat)bd->start, bd->blocks));
ASSERT(bd->blocks > 0);
+ ASSERT(bd->link ? bd->link->u.back == bd : 1);
+ ASSERT(bd->u.back ? bd->u.back->link == bd : 1);
+ checkWellFormedGroup(bd);
if (bd->link != NULL) {
/* make sure we're fully coalesced */
ASSERT(bd->start + bd->blocks * BLOCK_SIZE_W != bd->link->start);
- ASSERT(bd->start < bd->link->start);
}
}
}
projects / ghc-hetmet.git / blobdiff