X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=ghc%2Frts%2FBlockAlloc.c;h=39c8907ed11cde13b84668d756195246a36f5ac0;hb=deda5eaa86852c08cbafc739ef4df7507cc89aa3;hp=9d13719918c13fe974f07695a9f0d811200945ce;hpb=7457757f193b28b5fe8fee01edbed012c2fda897;p=ghc-hetmet.git

diff --git a/ghc/rts/BlockAlloc.c b/ghc/rts/BlockAlloc.c
index 9d13719..39c8907 100644
--- a/ghc/rts/BlockAlloc.c
+++ b/ghc/rts/BlockAlloc.c
@@ -1,7 +1,6 @@
 /* -----------------------------------------------------------------------------
- * $Id: BlockAlloc.c,v 1.14 2002/07/17 09:21:49 simonmar Exp $
  *
- * (c) The GHC Team 1998-2000
+ * (c) The GHC Team 1998-2005
  * 
  * The block allocator and free list manager.
  *
@@ -29,7 +28,7 @@ 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
@@ -37,27 +36,36 @@ static bdescr *free_list;
 
 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;
 
-  if (n != 0) {
-    head->blocks = n;
-    head->free = head->start;
-    for (i=1, bd = head+1; i < n; i++, bd++) {
-      bd->free = 0;
+    for (i=0, bd = tail; i < n; i++, bd++) {
+      bd->flags  = 0;
+      bd->free   = 0;
       bd->blocks = 0;
-      bd->link = head;
+      bd->link   = head;
     }
+}
+
+STATIC_INLINE void
+initGroup(nat n, bdescr *head)
+{
+  if (n != 0) {
+    head->blocks = n;
+    head->free   = head->start;
+    head->link   = NULL;
+    head->flags  = 0;
+    initGroupTail( n-1, head, head+1 );
   }
 }
 
@@ -76,12 +84,15 @@ allocGroup(nat n)
   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... */
@@ -159,19 +170,23 @@ allocMegaGroup(nat n)
     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 */
@@ -188,73 +203,98 @@ allocMegaGroup(nat n)
    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, blocks;
-
-  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;
-    blocks = q->blocks;
-    for (i = 0, bd = q; i < blocks; bd++, i++) {
-	bd->free = 0;
-	bd->blocks = 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;
-  }
 
-  /* 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);
+  if (!coalesce(p)) {
+    dbl_link_onto(p, &free_list);
   }
 
-  /* coalesce with next group if possible */
-  coalesce(p);
   IF_DEBUG(sanity, checkFreeListSanity());
 }
 
@@ -262,12 +302,13 @@ static void
 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);
   }
 }
 
@@ -296,7 +337,7 @@ initMBlock(void *mblock)
 
   /* 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;
   }
 }
@@ -307,7 +348,7 @@ initMBlock(void *mblock)
 
 #ifdef DEBUG
 static void
-checkWellFormedGroup( bdescr *bd )
+checkWellFormedGroup(bdescr *bd)
 {
     nat i;
 
@@ -325,14 +366,15 @@ 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);
     }
   }
 }