Rework the block allocator

The main goal here is to reduce fragmentation, which turns out to be
the case of #743.  While I was here I found some opportunities to
improve performance too.  The code is rather more complex, but it also
contains a long comment describing the strategy, so please take a look
at that for the details.

1 files changed, 44 insertions, 0 deletions

diff --git a/includes/Block.h b/includes/Block.h
index 408088087a..dd3e201234 100644
--- a/includes/Block.h
+++ b/includes/Block.h
@@ -130,6 +130,11 @@ INLINE_HEADER bdescr *Bdescr(StgPtr p)
 #define FIRST_BDESCR(m) \
    ((bdescr *)((FIRST_BLOCK_OFF>>(BLOCK_SHIFT-BDESCR_SHIFT)) + (W_)(m)))
 
+/* Last real block descriptor in a megablock */
+
+#define LAST_BDESCR(m) \
+  ((bdescr *)(((MBLOCK_SIZE-BLOCK_SIZE)>>(BLOCK_SHIFT-BDESCR_SHIFT)) + (W_)(m)))
+
 /* Number of usable blocks in a megablock */
 
 #define BLOCKS_PER_MBLOCK ((MBLOCK_SIZE - FIRST_BLOCK_OFF) / BLOCK_SIZE)
@@ -161,6 +166,45 @@ dbl_link_onto(bdescr *bd, bdescr **list)
   *list = bd;
 }
 
+INLINE_HEADER void
+dbl_link_remove(bdescr *bd, bdescr **list)
+{
+    if (bd->u.back) {
+        bd->u.back->link = bd->link;
+    } else {
+        *list = bd->link;
+    }
+    if (bd->link) {
+        bd->link->u.back = bd->u.back;
+    }
+}
+
+INLINE_HEADER void
+dbl_link_insert_after(bdescr *bd, bdescr *after)
+{
+    bd->link = after->link;
+    bd->u.back = after;
+    if (after->link) {
+        after->link->u.back = bd;
+    }
+    after->link = bd;
+}
+
+INLINE_HEADER void
+dbl_link_replace(bdescr *new, bdescr *old, bdescr **list)
+{
+    new->link = old->link;
+    new->u.back = old->u.back;
+    if (old->link) {
+        old->link->u.back = new;
+    }
+    if (old->u.back) {
+        old->u.back->link = new;
+    } else {
+        *list = new;
+    }
+}
+
 /* Initialisation ---------------------------------------------------------- */
 
 extern void initBlockAllocator(void);