1 files changed, 24 insertions, 29 deletions

diff --git a/libc/stdlib/malloc/heap_free.c b/libc/stdlib/malloc/heap_free.c
index 272327260..ad8de5182 100644
--- a/libc/stdlib/malloc/heap_free.c
+++ b/libc/stdlib/malloc/heap_free.c
@@ -16,30 +16,34 @@
 #include "heap.h"
 
 
-/* Return the memory area MEM of size SIZE to HEAP.  */
+/* Return the block of memory at MEM, of size SIZE, to HEAP.  */
 struct heap_free_area *
 __heap_free (struct heap *heap, void *mem, size_t size)
 {
-  struct heap_free_area *prev_fa, *fa;
+  struct heap_free_area *fa, *prev_fa;
   void *end = (char *)mem + size;
 
   HEAP_DEBUG (heap, "before __heap_free");
 
-  /* Find an adjacent free-list entry.  */
+  /* Find the right position in the free-list entry to place the new block.
+     This is the most speed critical loop in this malloc implementation:
+     since we use a simple linked-list for the free-list, and we keep it in
+     address-sorted order, it can become very expensive to insert something
+     in the free-list when it becomes fragmented and long.  [A better
+     implemention would use a balanced tree or something for the free-list,
+     though that bloats the code-size and complexity quite a bit.]  */
   for (prev_fa = 0, fa = heap->free_areas; fa; prev_fa = fa, fa = fa->next)
+    if (unlikely (HEAP_FREE_AREA_END (fa) >= mem))
+      break;
+
+  if (fa && HEAP_FREE_AREA_START (fa) <= end)
+    /* The free-list FA is adjacent to the new block, merge them.  */
     {
-      size_t fa_size = fa->size;
-      void *fa_mem = HEAP_FREE_AREA_START (fa);
+      size_t fa_size = fa->size + size;
 
-      if (fa_mem > end)
-	/* We've reached the right spot in the free-list without finding an
-	   adjacent free-area, so continue below to add a new free area. */
-	break;
-      else if (fa_mem == end)
-	/* FA is just after MEM, grow down to encompass it. */
+      if (HEAP_FREE_AREA_START (fa) == end)
+	/* FA is just after the new block, grow down to encompass it. */
 	{
-	  fa_size += size;
-
 	  /* See if FA can now be merged with its predecessor. */
 	  if (prev_fa && mem == HEAP_FREE_AREA_END (prev_fa))
 	    /* Yup; merge PREV_FA's info into FA.  */
@@ -47,18 +51,12 @@ __heap_free (struct heap *heap, void *mem, size_t size)
 	      fa_size += prev_fa->size;
 	      __heap_link_free_area_after (heap, fa, prev_fa->prev);
 	    }
-
-	  fa->size = fa_size;
-
-	  goto done;
 	}
-      else if (HEAP_FREE_AREA_END (fa) == mem)
-	/* FA is just before MEM, expand to encompass it. */
+      else
+	/* FA is just before the new block, expand to encompass it. */
 	{
 	  struct heap_free_area *next_fa = fa->next;
 
-	  fa_size += size;
-
 	  /* See if FA can now be merged with its successor. */
 	  if (next_fa && end == HEAP_FREE_AREA_START (next_fa))
 	    /* Yup; merge FA's info into NEXT_FA.  */
@@ -77,17 +75,14 @@ __heap_free (struct heap *heap, void *mem, size_t size)
 	      /* Update links with the neighbors in the list.  */ 
 	      __heap_link_free_area (heap, fa, prev_fa, next_fa);
 	    }
-
-	  fa->size = fa_size;
-
-	  goto done;
 	}
-    }
 
-  /* Make MEM into a new free-list entry.  */
-  fa = __heap_add_free_area (heap, mem, size, prev_fa, fa);
+      fa->size = fa_size;
+    }
+  else
+    /* Make the new block into a separate free-list entry.  */
+    fa = __heap_add_free_area (heap, mem, size, prev_fa, fa);
 
- done:
   HEAP_DEBUG (heap, "after __heap_free");
 
   return fa;