Nasty Evil Memory Fragmentation fix

[Gavriel State]

We just spent about 3 days tracking down a very subtle memory 
fragmentation problem in an app we're working on.  The problem:

App allocates lots of little blocks, then a few large blocks, 
then lots of little blocks.  Throughout this process, many 
blocks would be freed from all over the heap.  Repeat ad infinitum.

We ended up creating a new subheap every time one of these larger 
blocks came along.  The new space from the subheap then went to 
the top of the freelist, so all the small allocations then filled 
it up until the next large block allocation.  IE: We never got a 
chance to reuse freed blocks in older subheaps - at least not 
very well.  

This fix addresses the problem by pushing 'large' freed blocks to 
the end of the free list, leaving 'small' blocks at the front, to 
be found sooner.  The size of 'large' vs 'small' is tunable.

Despite the workaround, we're still not too pleased with the current
heap allocator.  It's quite slow, and still not as efficient as 
it could be.  It would probably be worth the effort to integrate
a new allocator - anyone know if there's a high-quality Wine-license-
compatible allocator out there?

 -Gav

-- 
Gavriel State, CEO
TransGaming Technologies Inc.
http://www.transgaming.com
gav at transgaming.com
-------------- next part --------------
--- heap.c	Wed Sep 26 19:11:21 2001
+++ /home/gavriels/transgaming/wine/memory/heap.c	Tue Oct  9 23:53:15 2001
@@ -59,6 +59,8 @@
 #define QUIET                  1           /* Suppress messages  */
 #define NOISY                  0           /* Report all errors  */
 
+#define FREE_BLOCK_INSERTION_THRESHOLD	4096
+
 #define HEAP_NB_FREE_LISTS   4   /* Number of free lists */
 
 /* Max size of the blocks on the free lists */
@@ -229,11 +231,11 @@
 
 
 /***********************************************************************
- *           HEAP_InsertFreeBlock
+ *           HEAP_InsertFreeBlockAtFront
  *
- * Insert a free block into the free list.
+ * Insert a free block into the front of the free list.
  */
-static void HEAP_InsertFreeBlock( HEAP *heap, ARENA_FREE *pArena )
+static void HEAP_InsertFreeBlockAtFront( HEAP *heap, ARENA_FREE *pArena )
 {
     FREE_LIST_ENTRY *pEntry = heap->freeList;
     while (pEntry->size < pArena->size) pEntry++;
@@ -244,6 +246,31 @@
     pEntry->arena.next = pArena;
 }
 
+/***********************************************************************
+ *           HEAP_InsertFreeBlockAtEnd
+ *
+ * Insert a free block into the end of the free list.
+ */
+static void HEAP_InsertFreeBlockAtEnd( HEAP *heap, ARENA_FREE *pArena )
+{
+    FREE_LIST_ENTRY *pEntry = heap->freeList;
+ 
+    /* Determine which free list contains blocks of the appropriate size. */
+    while (pEntry->size < pArena->size) pEntry++;
+ 
+    /* But we want to put this block on the end of said appropriate free list.
+     * So instead, find the list for the next size up, knowing that they are
+     * all connected. */
+    if (++pEntry == heap->freeList+HEAP_NB_FREE_LISTS)
+        pEntry = heap->freeList;
+ 
+    pArena->size      |= ARENA_FLAG_FREE;
+    pArena->next       = &pEntry->arena;
+    pArena->prev       = pEntry->arena.prev;
+ 
+    pArena->next->prev = pArena;
+    pArena->prev->next = pArena;
+}                                         
 
 /***********************************************************************
  *           HEAP_FindSubHeap
@@ -372,7 +399,11 @@
     /* Last, insert the new block into the free list */
 
     pFree->size = size - sizeof(*pFree);
-    HEAP_InsertFreeBlock( subheap->heap, pFree );
+
+    if ((pFree->size & ARENA_SIZE_MASK) > FREE_BLOCK_INSERTION_THRESHOLD)
+        HEAP_InsertFreeBlockAtEnd( subheap->heap, pFree );
+    else
+        HEAP_InsertFreeBlockAtFront( subheap->heap, pFree );
 }