Miles Bader implemented a new mmap based malloc which is much

smarter than the old "malloc-simple", and actually works, unlike
the old "malloc".  So kill the old "malloc-simple" and the old
"malloc" and replace them with Miles' new malloc implementation.
Update Config files to match.  Thanks Miles!

16 files changed, 740 insertions, 1392 deletions

diff --git a/libc/stdlib/malloc-simple/.indent.pro b/libc/stdlib/malloc-simple/.indent.pro
deleted file mode 100644
index 492ecf1c7..000000000
--- a/libc/stdlib/malloc-simple/.indent.pro
+++ /dev/null
@@ -1,33 +0,0 @@
---blank-lines-after-declarations
---blank-lines-after-procedures
---break-before-boolean-operator
---no-blank-lines-after-commas
---braces-on-if-line
---braces-on-struct-decl-line
---comment-indentation25
---declaration-comment-column25
---no-comment-delimiters-on-blank-lines
---cuddle-else
---continuation-indentation4
---case-indentation0
---else-endif-column33
---space-after-cast
---line-comments-indentation0
---declaration-indentation1
---dont-format-first-column-comments
---dont-format-comments
---honour-newlines
---indent-level4
-/* changed from 0 to 4 */
---parameter-indentation4
---line-length78 /* changed from 75 */
---continue-at-parentheses
---no-space-after-function-call-names
---dont-break-procedure-type
---dont-star-comments
---leave-optional-blank-lines
---dont-space-special-semicolon
---tab-size4
-/* additions by Mark */
---case-brace-indentation0
---leave-preprocessor-space
diff --git a/libc/stdlib/malloc-simple/Makefile b/libc/stdlib/malloc-simple/Makefile
deleted file mode 100644
index f8fe3520d..000000000
--- a/libc/stdlib/malloc-simple/Makefile
+++ /dev/null
@@ -1,49 +0,0 @@
-# Makefile for uClibc
-#
-# Copyright (C) 2000 by Lineo, inc.
-# Copyright (C) 2000,2001 Erik Andersen <andersen@uclibc.org>
-#
-# This program is free software; you can redistribute it and/or modify it under
-# the terms of the GNU Library General Public License as published by the Free
-# Software Foundation; either version 2 of the License, or (at your option) any
-# later version.
-#
-# This program is distributed in the hope that it will be useful, but WITHOUT
-# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
-# FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more
-# details.
-#
-# You should have received a copy of the GNU Library General Public License
-# along with this program; if not, write to the Free Software Foundation, Inc.,
-# 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
-#
-# Derived in part from the Linux-8086 C library, the GNU C Library, and several
-# other sundry sources.  Files within this library are copyright by their
-# respective copyright holders.
-
-TOPDIR=../../../
-include $(TOPDIR)Rules.mak
-
-MSRC=alloc.c
-MOBJ=malloc.o realloc.o free.o calloc.o #malloc_dbg.o free_dbg.o calloc_dbg.o
-OBJS=$(MOBJ)
-
-
-all: $(OBJS) $(LIBC)
-
-$(LIBC): ar-target
-
-ar-target: $(OBJS)
-	$(AR) $(ARFLAGS) $(LIBC) $(OBJS)
-
-$(MOBJ): $(MSRC)
-	$(CC) $(CFLAGS) -DL_$* $< -c -o $*.o
-	$(STRIPTOOL) -x -R .note -R .comment $*.o
-
-$(COBJS): %.o : %.c
-	$(CC) $(CFLAGS) -c $< -o $@
-	$(STRIPTOOL) -x -R .note -R .comment $*.o
-
-clean:
-	rm -f *.[oa] *~ core
-
diff --git a/libc/stdlib/malloc-simple/alloc.c b/libc/stdlib/malloc-simple/alloc.c
deleted file mode 100644
index 1824507eb..000000000
--- a/libc/stdlib/malloc-simple/alloc.c
+++ /dev/null
@@ -1,141 +0,0 @@
-
-/*
- *	For MMU hosts we need to track the size of the allocations otherwise
- *	munmap will fail to free the memory (EINVAL).
- */
-
-#include <features.h>
-#include <unistd.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-#include <unistd.h>
-#include <sys/mman.h>
-
-
-#ifdef L_calloc_dbg
-
-void *calloc_dbg(size_t num, size_t size, char *function, char *file,
-				 int line)
-{
-	void *ptr;
-
-	fprintf(stderr, "calloc of %d bytes at %s @%s:%d = ", (int) (num * size),
-			function, file, line);
-	ptr = calloc(num, size);
-	fprintf(stderr, "%p\n", ptr);
-	return ptr;
-}
-
-#endif
-
-#ifdef L_malloc_dbg
-
-void *malloc_dbg(size_t size, char *function, char *file, int line)
-{
-	void *result;
-
-	fprintf(stderr, "malloc of %d bytes at %s @%s:%d = ", (int) size, function,
-			file, line);
-	result = malloc(size);
-	fprintf(stderr, "%p\n", result);
-	return result;
-}
-
-#endif
-
-#ifdef L_free_dbg
-
-void free_dbg(void *ptr, char *function, char *file, int line)
-{
-	fprintf(stderr, "free of %p at %s @%s:%d\n", ptr, function, file,
-			line);
-	free(ptr);
-}
-
-#endif
-
-
-#ifdef L_calloc
-
-void *calloc(size_t num, size_t size)
-{
-	void *ptr = malloc(num * size);
-
-	if (ptr)
-		memset(ptr, 0, num * size);
-	return ptr;
-}
-
-#endif
-
-#ifdef L_malloc
-
-void *malloc(size_t size)
-{
-	void *result;
-
-    /* Some programs will call malloc (0).  Lets be strict and return NULL */
-    if (size == 0)
-		return NULL;
-
-#ifdef __UCLIBC_HAS_MMU__
-	result = mmap((void *) 0, size + sizeof(size_t), PROT_READ | PROT_WRITE,
-						MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
-#else
-	result = mmap((void *) 0, size, PROT_READ | PROT_WRITE,
-						MAP_SHARED | MAP_ANONYMOUS, 0, 0);
-#endif
-
-	if (result == MAP_FAILED)
-		return 0;
-	
-#ifdef __UCLIBC_HAS_MMU__
-	* (size_t *) result = size;
-	return(result + sizeof(size_t));
-#else
-	return(result);
-#endif
-}
-
-#endif
-
-#ifdef L_free
-
-void free(void *ptr)
-{
-#ifdef __UCLIBC_HAS_MMU__
-	if (ptr) {
-		ptr -= sizeof(size_t);
-		munmap(ptr, * (size_t *) ptr + sizeof(size_t));
-	}
-#else
-	munmap(ptr, 0);
-#endif
-}
-
-#endif
-
-#ifdef L_realloc
-
-void *realloc(void *ptr, size_t size)
-{
-	void *newptr = NULL;
-
-	if (size > 0) {
-		newptr = malloc(size);
-		if (newptr && ptr) {
-#ifdef __UCLIBC_HAS_MMU__
-			memcpy(newptr, ptr, * ((size_t *) (ptr - sizeof(size_t))));
-#else
-			memcpy(newptr, ptr, size);
-#endif
-			free(ptr);
-		}
-	}
-	else
-		free(ptr);
-	return newptr;
-}
-
-#endif
diff --git a/libc/stdlib/malloc/Makefile b/libc/stdlib/malloc/Makefile
index 64aad319a..710f70297 100644
--- a/libc/stdlib/malloc/Makefile
+++ b/libc/stdlib/malloc/Makefile
@@ -1,7 +1,7 @@
 # Makefile for uClibc
 #
-# Copyright (C) 2000 by Lineo, inc.
-# Copyright (C) 2000,2001 Erik Andersen <andersen@uclibc.org>
+# Copyright (C) 2002  NEC Corporation
+# Copyright (C) 2002  Miles Bader <miles@gnu.org>
 #
 # This program is free software; you can redistribute it and/or modify it under
 # the terms of the GNU Library General Public License as published by the Free
@@ -24,14 +24,10 @@
 TOPDIR=../../../
 include $(TOPDIR)Rules.mak
 
-#MSRC=alloc.c
-#MOBJ=malloc_dbg.o free_dbg.o calloc_dbg.o realloc_dbg.o
-
-MSRC1=malloc.c
-MOBJ1=_avl_support.o _free_support.o _malloc_init.o _realloc_no_move.o calloc.o \
-	 free.o malloc.o realloc.o
-
-OBJS=$(MOBJ) $(MOBJ1)
+CSRC = malloc.o free.o realloc.o calloc.o heap_alloc.o \
+	heap_alloc_at.o heap_free.o heap_append_free.o
+COBJS=$(patsubst %.c,%.o, $(CSRC))
+OBJS=$(COBJS)
 
 all: $(OBJS) $(LIBC)
 
@@ -40,12 +36,8 @@ $(LIBC): ar-target
 ar-target: $(OBJS)
 	$(AR) $(ARFLAGS) $(LIBC) $(OBJS)
 
-$(MOBJ): $(MSRC)
-	$(CC) $(CFLAGS) -DL_$* $< -c -o $*.o
-	$(STRIPTOOL) -x -R .note -R .comment $*.o
-
-$(MOBJ1): $(MSRC1)
-	$(CC) $(CFLAGS) -DL_$* $< -c -o $*.o
+$(COBJS): %.o : %.c
+	$(CC) $(CFLAGS) -c $< -o $@
 	$(STRIPTOOL) -x -R .note -R .comment $*.o
 
 clean:
diff --git a/libc/stdlib/malloc/alloc.c b/libc/stdlib/malloc/alloc.c
deleted file mode 100644
index 99537a35d..000000000
--- a/libc/stdlib/malloc/alloc.c
+++ /dev/null
@@ -1,60 +0,0 @@
-#include <unistd.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-#include <unistd.h>
-#include <sys/mman.h>
-
-
-#ifdef L_calloc_dbg
-
-void *calloc_dbg(size_t num, size_t size, char *function, char *file,
-				 int line)
-{
-	void *ptr;
-
-	fprintf(stderr, "calloc of %ld bytes at %s @%s:%d = ",
-			(long) (num * size), function, file, line);
-	ptr = calloc(num, size);
-	fprintf(stderr, "%p\n", ptr);
-	return ptr;
-}
-
-#endif
-
-#ifdef L_malloc_dbg
-
-void *malloc_dbg(size_t len, char *function, char *file, int line)
-{
-	void *result;
-
-	fprintf(stderr, "malloc of %ld bytes at %s @%s:%d = ", (long) len,
-			function, file, line);
-	result = malloc(len);
-	fprintf(stderr, "%p\n", result);
-	return result;
-}
-
-#endif
-
-#ifdef L_free_dbg
-
-void free_dbg(void *ptr, char *function, char *file, int line)
-{
-	fprintf(stderr, "free of %p at %s @%s:%d\n", ptr, function, file,
-			line);
-	free(ptr);
-}
-
-#endif
-
-#ifdef L_realloc_dbg
-void *realloc_dbg(void *ptr, size_t size, char *function, char *file, int line)
-{
-	fprintf(stderr, "realloc of %p to %ld bytes at %s @%s;%d = ", ptr,
-			(long)size, function, file, line);
-	ptr = realloc(ptr, size);
-	fprintf(stderr, "%p\n", ptr);
-	return ptr;
-}
-#endif
diff --git a/libc/stdlib/malloc/avlmacro.h b/libc/stdlib/malloc/avlmacro.h
deleted file mode 100644
index cce2c38f3..000000000
--- a/libc/stdlib/malloc/avlmacro.h
+++ /dev/null
@@ -1,226 +0,0 @@
-/* MACRO-CODED FAST FIXED AVL TREES IMPLEMENTATION IN C              */
-/* COPYRIGHT (C) 1998 VALERY SHCHEDRIN                               */
-/* IT IS DISTRIBUTED UNDER GLPL (GNU GENERAL LIBRARY PUBLIC LICENSE) */
-
-/*
- * Manuel Novoa III       Jan 2001
- *
- * Modified to decrease object size.
- *   Tree balancing is now done in a fuction rather than inline.
- *   Removed common code in balance by use of a goto.
- *   Added macro Avl_Tree_no_replace since ptrs_replace was not used.
- *   Prepended may symbols with "__" for possible conversion to extern.
- */
-
-#define __Avl_balance_proto(objname, pr, root) \
-  static int __Avl_##objname##pr##balance(objname **root) \
-  { \
-    objname *p; \
-    int ht_changed; \
-    p = *root; \
-    if (p->bal_##pr < -1) \
-    { \
-      if (p->l_##pr->bal_##pr == 1) \
-      { \
-	objname *pp; \
-	pp=p->l_##pr; *root=p->l_##pr->r_##pr; p->l_##pr = (*root)->r_##pr; \
-	(*root)->r_##pr = p; pp->r_##pr = (*root)->l_##pr; \
-	p = *root; p->l_##pr = pp; \
-    goto pr_common_ht_changed; \
-      } \
-      else \
-      { \
-	ht_changed = (p->l_##pr ->bal_##pr)?1:0; \
-	*root = p->l_##pr ; \
-	p->l_##pr = (*root)->r_##pr ; (*root)->r_##pr = p; \
-	p->bal_##pr = - (++((*root)->bal_##pr )); \
-      } \
-    } \
-    else if (p->bal_##pr > 1) \
-    { \
-      if (p->r_##pr->bal_##pr == -1) \
-      { \
-	objname *pp; \
-	pp=p->r_##pr ; *root=p->r_##pr ->l_##pr ; p->r_##pr =(*root)->l_##pr ; \
-	(*root)->l_##pr = p; pp->l_##pr = (*root)->r_##pr ; \
-	p = *root; p->r_##pr = pp; \
-    pr_common_ht_changed: \
-	if (p->bal_##pr > 0) p->l_##pr ->bal_##pr = -p->bal_##pr ; \
-	else p->l_##pr ->bal_##pr = 0; \
-	if (p->bal_##pr < 0) p->r_##pr ->bal_##pr = -p->bal_##pr ; \
-	else p->r_##pr ->bal_##pr = 0; \
-	p->bal_##pr = 0; \
-	ht_changed = 1; \
-      } \
-      else \
-      { \
-	ht_changed = (p->r_##pr ->bal_##pr)?1:0; \
-	*root = p->r_##pr ; \
-	p->r_##pr = (*root)->l_##pr ; (*root)->l_##pr = p; \
-	p->bal_##pr = - (--((*root)->bal_##pr )); \
-      } \
-    } else ht_changed = 0; \
-   return ht_changed; \
-  }
-
-#define balance(objname, pr, root) \
-  __Avl_##objname##pr##balance(root)
-
-#define __Avl_r_insert_proto(objname, pr, COMPARE) \
-  static int __Avl_##objname##pr##_r_insert(objname **root) \
-  { \
-    int i; /* height increase */ \
-    if (!*root) \
-    { \
-      *root = __Avl_##objname##pr##_new_node; \
-      __Avl_##objname##pr##_new_node = NULL; \
-      return 1; \
-    } \
-    COMPARE(i, __Avl_##objname##pr##_new_node, *root); \
-    \
-    if (i < 0) \
-    { /* insert into the left subtree */ \
-      i = -__Avl_##objname##pr##_r_insert(&((*root)->l_##pr)); \
-      if (__Avl_##objname##pr##_new_node != NULL) return 0; /* already there */ \
-    } \
-    else if (i > 0) \
-    { /* insert into the right subtree */ \
-      i = __Avl_##objname##pr##_r_insert(&((*root)->r_##pr)); \
-      if (__Avl_##objname##pr##_new_node != NULL) return 0; /* already there */ \
-    } \
-    else \
-    { /* found */ \
-      __Avl_##objname##pr##_new_node = *root; \
-      return 0; \
-    } \
-    if (!i) return 0; \
-    (*root)->bal_##pr += i; /* update balance factor */ \
-    if ((*root)->bal_##pr) \
-    { \
-      return 1 - balance(objname,pr,root); \
-    } \
-    else return 0; \
-  }
-
-#define __Avl_r_delete_proto(objname,pr,COMPARE) \
-  static int __Avl_##objname##pr##_r_delete(objname **root) \
-  { \
-    int i; /* height decrease */ \
-    \
-    if (!*root) return 0; /* not found */ \
-    \
-    COMPARE(i, __Avl_##objname##pr##_new_node, *root); \
-    \
-    if (i < 0) \
-      i = -__Avl_##objname##pr##_r_delete(&((*root)->l_##pr)); \
-    else if (i > 0) \
-      i =  __Avl_##objname##pr##_r_delete(&((*root)->r_##pr)); \
-    else \
-    { \
-      if (!(*root)->l_##pr) \
-      { \
-	*root = (*root)->r_##pr; \
-	return 1; \
-      } \
-      else if (!(*root)->r_##pr) \
-      { \
-	*root = (*root)->l_##pr; \
-	return 1; \
-      } \
-      else \
-      { \
-	i = __Avl_##objname##pr##_r_delfix(&((*root)->r_##pr)); \
-	__Avl_##objname##pr##_new_node->l_##pr = (*root)->l_##pr; \
-	__Avl_##objname##pr##_new_node->r_##pr = (*root)->r_##pr; \
-	__Avl_##objname##pr##_new_node->bal_##pr = (*root)->bal_##pr; \
-	*root = __Avl_##objname##pr##_new_node; \
-      } \
-    } \
-    if (!i) return 0; \
-    (*root)->bal_##pr -= i; \
-    if ((*root)->bal_##pr) \
-    { \
-      return balance(objname,pr,root); \
-    } \
-    return 1; \
-  }
-
-#define __Avl_r_delfix_proto(objname,pr) \
-  static int __Avl_##objname##pr##_r_delfix(objname **root) \
-  { \
-    int i; /* height decrease */ \
-    \
-    if (!(*root)->l_##pr) \
-    { \
-      __Avl_##objname##pr##_new_node = *root; \
-      *root = (*root)->r_##pr; \
-      return 1; \
-    } \
-    i = -__Avl_##objname##pr##_r_delfix(&((*root)->l_##pr)); \
-    if (!i) return 0; \
-    (*root)->bal_##pr -= i; \
-    if ((*root)->bal_##pr) \
-    { \
-      return balance(objname,pr,root); \
-    } \
-    return 1; \
-  }
-
-#define __Avl_ins_proto(alias,objname,pr) \
-  objname *__##alias##_ins(objname *data) \
-  { \
-    __Avl_##objname##pr##_new_node = data; \
-    (data)->l_##pr = NULL; \
-    (data)->r_##pr = NULL; \
-    (data)->bal_##pr = 0; \
-    __Avl_##objname##pr##_r_insert(&__Avl_##objname##pr##_tree); \
-    if (__Avl_##objname##pr##_new_node) \
-      return __Avl_##objname##pr##_new_node; \
-    return NULL; \
-  }
-
-#define __Avl_del_proto(alias,objname,pr) \
-  void __##alias##_del(objname *data) \
-  { \
-    __Avl_##objname##pr##_new_node = data; \
-    __Avl_##objname##pr##_r_delete(&__Avl_##objname##pr##_tree); \
-  }
-
-#define __Avl_replace_proto(alias,objname,pr,COMPARE) \
-  void __##alias##_replace(objname *data) \
-  { \
-    objname **p = &__Avl_##objname##pr##_tree; \
-    int cmp; \
-    while (*p) \
-    { \
-      COMPARE(cmp, data, *p); \
-      if (cmp < 0) \
-	p = &((*p)->l_##pr); \
-      else if (cmp > 0) \
-	p = &((*p)->r_##pr); \
-      else \
-      { \
-	(data)->l_##pr = (*p)->l_##pr; \
-	(data)->r_##pr = (*p)->r_##pr; \
-	(data)->bal_##pr = (*p)->bal_##pr; \
-	*p = data; \
-	return; \
-      } \
-    } \
-  }
-
-#define Avl_Root(objname,pr) __Avl_##objname##pr##_tree
-
-#define Avl_Tree_no_replace(alias,objname,pr,COMPARE) \
-objname *__Avl_##objname##pr##_tree = NULL; \
-static objname *__Avl_##objname##pr##_new_node; \
-__Avl_balance_proto(objname, pr, root) \
-__Avl_r_insert_proto(objname,pr,COMPARE) \
-__Avl_r_delfix_proto(objname,pr) \
-__Avl_r_delete_proto(objname,pr,COMPARE) \
-__Avl_ins_proto(alias,objname,pr) \
-__Avl_del_proto(alias,objname,pr)
-
-#define Avl_Tree(alias,objname,pr,COMPARE) \
-Avl_Tree_no_replace(alias,objname,pr,COMPARE) \
-__Avl_replace_proto(alias,objname,pr,COMPARE)
diff --git a/libc/stdlib/malloc/calloc.c b/libc/stdlib/malloc/calloc.c
new file mode 100644
index 000000000..6231edb46
--- /dev/null
+++ b/libc/stdlib/malloc/calloc.c
@@ -0,0 +1,32 @@
+/*
+ * libc/stdlib/malloc-zarg/calloc.c -- calloc function
+ *
+ *  Copyright (C) 2002  NEC Corporation
+ *  Copyright (C) 2002  Miles Bader <miles@gnu.org>
+ *
+ * This file is subject to the terms and conditions of the GNU Lesser
+ * General Public License.  See the file COPYING.LIB in the main
+ * directory of this archive for more details.
+ * 
+ * Written by Miles Bader <miles@gnu.org>
+ */
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "malloc.h"
+
+
+void *
+calloc (size_t size, size_t num)
+{
+  void *mem;
+
+  size *= num;
+
+  mem = malloc (size);
+  if (mem)
+    memset (mem, 0, size);
+
+  return mem;
+}
diff --git a/libc/stdlib/malloc/free.c b/libc/stdlib/malloc/free.c
new file mode 100644
index 000000000..5d5b8f033
--- /dev/null
+++ b/libc/stdlib/malloc/free.c
@@ -0,0 +1,35 @@
+/*
+ * libc/stdlib/malloc-zarg/free.c -- free function
+ *
+ *  Copyright (C) 2002  NEC Corporation
+ *  Copyright (C) 2002  Miles Bader <miles@gnu.org>
+ *
+ * This file is subject to the terms and conditions of the GNU Lesser
+ * General Public License.  See the file COPYING.LIB in the main
+ * directory of this archive for more details.
+ * 
+ * Written by Miles Bader <miles@gnu.org>
+ */
+
+#include <stdlib.h>
+#include <sys/mman.h>
+
+#include "malloc.h"
+#include "heap.h"
+
+
+void free (void *mem)
+{
+  size_t size;
+
+  mem = (size_t *)mem - 1;
+  size = *(size_t *)mem;
+
+  MALLOC_DEBUG ("free: 0x%lx (base = 0x%lx, total_size = %d)\n",
+		(long)mem + sizeof (size_t), (long)mem, size);
+
+  if (size >= MALLOC_MMAP_THRESHOLD)
+    munmap (mem, size);
+  else
+    __heap_free (&__malloc_heap, mem, size);
+}
diff --git a/libc/stdlib/malloc/heap.h b/libc/stdlib/malloc/heap.h
new file mode 100644
index 000000000..74b56603b
--- /dev/null
+++ b/libc/stdlib/malloc/heap.h
@@ -0,0 +1,146 @@
+/*
+ * libc/stdlib/malloc-zarg/heap.h -- heap allocator used for malloc
+ *
+ *  Copyright (C) 2002  NEC Corporation
+ *  Copyright (C) 2002  Miles Bader <miles@gnu.org>
+ *
+ * This file is subject to the terms and conditions of the GNU Lesser
+ * General Public License.  See the file COPYING.LIB in the main
+ * directory of this archive for more details.
+ * 
+ * Written by Miles Bader <miles@gnu.org>
+ */
+
+#include <features.h>
+
+
+#ifdef __UCLIBC_HAS_THREADS__
+#include <pthread.h>
+typedef pthread_mutex_t mutex_t;
+# define MUTEX_INITIALIZER  PTHREAD_MUTEX_INITIALIZER
+# define mutex_lock(x)	    pthread_mutex_lock(&(x))
+# define mutex_unlock(x)    pthread_mutex_unlock(&(x));
+#else
+/* Mutex operations are currently a nop.  */
+typedef int mutex_t;
+# define MUTEX_INITIALIZER 0
+# define mutex_lock(x)
+# define mutex_unlock(x)
+#endif
+
+
+
+/* The unit in which allocation is done, due to alignment constraints, etc.
+   All allocation requests are rounded up to a multiple of this size.
+   Must be a power of 2.  */
+#define HEAP_GRANULARITY	(sizeof (double))
+
+
+struct heap
+{
+  struct heap_free_area *free_areas;
+  mutex_t lock;
+};
+
+#define HEAP_INIT 	{ 0, MUTEX_INITIALIZER }
+
+
+/* A free-list area `header'.  These are actually stored at the _ends_ of
+   free areas (to make allocating from the beginning of the area simpler),
+   so one might call it a `footer'.  */
+struct heap_free_area
+{
+	size_t size;
+	struct heap_free_area *next, *prev;
+};
+
+/* Return the address of the end of the frea area FA.  */
+#define HEAP_FREE_AREA_END(fa) ((void *)(fa + 1))
+/* Return the address of the beginning of the frea area FA.  FA is
+   evaulated multiple times.  */
+#define HEAP_FREE_AREA_START(fa) ((void *)((char *)(fa + 1) - (fa)->size))
+
+
+/* Rounds SZ up to be a multiple of HEAP_GRANULARITY.  */
+#define HEAP_ADJUST_SIZE(sz)  \
+   (((sz) + HEAP_GRANULARITY - 1) & ~(HEAP_GRANULARITY - 1))
+
+/* The minimum size of a free area.  It must include at least enough room
+   to hold a struct heap_free_area, plus enough extra to be usefully
+   allocated.  */
+#define HEAP_MIN_FREE_AREA_SIZE  \
+  (sizeof (struct heap_free_area) + HEAP_ADJUST_SIZE (1))
+
+
+#if 0
+#include <stdio.h>
+static void HEAP_DEBUG (struct heap *heap, const char *str)
+{
+  static int recursed = 0;
+  if (! recursed)
+    {
+      struct heap_free_area *fa;
+      recursed = 1;
+      fprintf (stderr, "  %s: heap @0x%lx:\n", str, (long)heap);
+      for (fa = heap->free_areas; fa; fa = fa->next)
+	fprintf (stderr,
+		 "    0x%lx:  0x%lx - 0x%lx  (%d)\tN=0x%lx, P=0x%lx\n",
+		 (long)fa,
+		 (long)HEAP_FREE_AREA_START (fa),
+		 (long)HEAP_FREE_AREA_END (fa),
+		 fa->size,
+		 (long)fa->prev,
+		 (long)fa->next);
+      recursed = 0;
+    }
+}
+#else
+#define HEAP_DEBUG(heap, str) (void)0
+#endif
+
+
+/* Allocate SIZE bytes from the front of the free-area FA in HEAP, and
+   return the amount actually allocated (which may be more than SIZE).  */
+extern inline size_t
+__heap_free_area_alloc (struct heap *heap,
+			struct heap_free_area *fa, size_t size)
+{
+  size_t fa_size = fa->size;
+
+  if (fa_size < size + HEAP_MIN_FREE_AREA_SIZE)
+    /* There's not enough room left over in FA after allocating the block, so
+       just use the whole thing, removing it from the list of free areas.  */
+    {
+      if (fa->next)
+	fa->next->prev = fa->prev;
+      if (fa->prev)
+	fa->prev->next = fa->next;
+      else
+	heap->free_areas = fa->next;
+      /* Remember that we've alloced the whole area.  */
+      size = fa_size;
+    }
+  else
+    /* Reduce size of FA to account for this allocation.  */
+    fa->size = fa_size - size;
+
+  return size;
+}
+
+
+/* Allocate and return a block at least *SIZE bytes long from HEAP.
+   *SIZE is adjusted to reflect the actual amount allocated (which may be
+   greater than requested).  */
+extern void *__heap_alloc (struct heap *heap, size_t *size);
+
+/* Allocate SIZE bytes at address MEM in HEAP.  Return the actual size
+   allocated, or 0 if we failed.  */
+extern size_t __heap_alloc_at (struct heap *heap, void *mem, size_t size);
+
+/* Return the memory area MEM of size SIZE to HEAP.  */
+extern void __heap_free (struct heap *heap, void *mem, size_t size);
+
+/* If the memory area MEM, of size SIZE, immediately follows an existing
+   free-area in HEAP, use it to extend that free-area, and return true;
+   otherwise return false.  */
+extern int __heap_append_free (struct heap *heap, void *mem, size_t size);
diff --git a/libc/stdlib/malloc/heap_alloc.c b/libc/stdlib/malloc/heap_alloc.c
new file mode 100644
index 000000000..22591d613
--- /dev/null
+++ b/libc/stdlib/malloc/heap_alloc.c
@@ -0,0 +1,55 @@
+/*
+ * libc/stdlib/malloc-zarg/heap_alloc.c -- allocate from a heap
+ *
+ *  Copyright (C) 2002  NEC Corporation
+ *  Copyright (C) 2002  Miles Bader <miles@gnu.org>
+ *
+ * This file is subject to the terms and conditions of the GNU Lesser
+ * General Public License.  See the file COPYING.LIB in the main
+ * directory of this archive for more details.
+ * 
+ * Written by Miles Bader <miles@gnu.org>
+ */
+
+#include <stdlib.h>
+
+#include "heap.h"
+
+
+/* Allocate and return a block at least *SIZE bytes long from HEAP.
+   *SIZE is adjusted to reflect the actual amount allocated (which may be
+   greater than requested).  */
+void *
+__heap_alloc (struct heap *heap, size_t *size)
+{
+  struct heap_free_area *fa;
+  size_t _size = *size;
+  void *mem = 0;
+
+  _size = HEAP_ADJUST_SIZE (_size);
+  
+  if (_size < sizeof (struct heap_free_area))
+    /* Because we sometimes must use a freed block to hold a free-area node,
+       we must make sure that every allocated block can hold one.  */
+    _size = HEAP_ADJUST_SIZE (sizeof (struct heap_free_area));
+
+  mutex_lock (heap->lock);
+
+  HEAP_DEBUG (heap, "before __heap_alloc");
+
+  /* Look for a free area that can contain _SIZE bytes.  */
+  for (fa = heap->free_areas; fa; fa = fa->next)
+    if (fa->size >= _size)
+      {
+	/* Found one!  */
+	mem = HEAP_FREE_AREA_START (fa);
+	*size = __heap_free_area_alloc (heap, fa, _size);
+	break;
+      }
+
+  HEAP_DEBUG (heap, "after __heap_alloc");
+
+  mutex_unlock (heap->lock);
+
+  return mem;
+}
diff --git a/libc/stdlib/malloc/heap_alloc_at.c b/libc/stdlib/malloc/heap_alloc_at.c
new file mode 100644
index 000000000..8ee925488
--- /dev/null
+++ b/libc/stdlib/malloc/heap_alloc_at.c
@@ -0,0 +1,51 @@
+/*
+ * libc/stdlib/malloc-zarg/heap_alloc_at.c -- allocate at a specific address
+ *
+ *  Copyright (C) 2002  NEC Corporation
+ *  Copyright (C) 2002  Miles Bader <miles@gnu.org>
+ *
+ * This file is subject to the terms and conditions of the GNU Lesser
+ * General Public License.  See the file COPYING.LIB in the main
+ * directory of this archive for more details.
+ * 
+ * Written by Miles Bader <miles@gnu.org>
+ */
+
+#include <stdlib.h>
+
+#include "heap.h"
+
+
+/* Allocate SIZE bytes at address MEM in HEAP.  Return the actual size
+   allocated, or 0 if we failed.  */
+size_t
+__heap_alloc_at (struct heap *heap, void *mem, size_t size)
+{
+  struct heap_free_area *fa;
+  size_t alloced = 0;
+
+  size = HEAP_ADJUST_SIZE (size);
+
+  mutex_lock (heap->lock);
+
+  HEAP_DEBUG (heap, "before __heap_alloc_at");
+
+  /* Look for a free area that can contain SIZE bytes.  */
+  for (fa = heap->free_areas; fa; fa = fa->next)
+    {
+      void *fa_mem = HEAP_FREE_AREA_START (fa);
+      if (fa_mem <= mem) 
+	{
+	  if (fa_mem == mem && fa->size >= size)
+	    /* FA has the right addr, and is big enough! */
+	    alloced = __heap_free_area_alloc (heap, fa, size);
+	  break;
+	}
+    }
+
+  HEAP_DEBUG (heap, "after __heap_alloc_at");
+
+  mutex_unlock (heap->lock);
+
+  return alloced;
+}
diff --git a/libc/stdlib/malloc/heap_append_free.c b/libc/stdlib/malloc/heap_append_free.c
new file mode 100644
index 000000000..42f0cf5bb
--- /dev/null
+++ b/libc/stdlib/malloc/heap_append_free.c
@@ -0,0 +1,71 @@
+/*
+ * libc/stdlib/malloc-zarg/heap_append_free.c -- append to heap free area
+ *
+ *  Copyright (C) 2002  NEC Corporation
+ *  Copyright (C) 2002  Miles Bader <miles@gnu.org>
+ *
+ * This file is subject to the terms and conditions of the GNU Lesser
+ * General Public License.  See the file COPYING.LIB in the main
+ * directory of this archive for more details.
+ * 
+ * Written by Miles Bader <miles@gnu.org>
+ */
+
+#include <stdlib.h>
+
+#include "heap.h"
+
+
+/* If the block MEM, of size SIZE, immediately follows an existing free-area
+   in HEAP, use it to extend that free-area, and return true; otherwise return
+   false.  */
+int
+__heap_append_free (struct heap *heap, void *mem, size_t size)
+{
+  int success = 0;
+  struct heap_free_area *fa;
+
+  mutex_lock (heap->lock);
+
+  HEAP_DEBUG (heap, "before __heap_append_free");
+
+  /* Find an adjacent free-list entry.  */
+  for (fa = heap->free_areas; fa; fa = fa->next)
+    if (HEAP_FREE_AREA_END (fa) == mem)
+      /* MEM follows FA, extend FA to include it.  Since the descriptor for FA
+	 is located at the end, we must actually write a new descriptor.  Note
+	 that we _don't_ handle the case where the extended FA can be merged
+	 with a following free area; this is because this function is
+	 generally only used in cases were we believe that usually won't
+	 happen (it doesn't cause any incorrectness, and the two blocks can be
+	 merged by __heap_free later).  */
+      {
+	struct heap_free_area *next_fa = fa->next;
+	struct heap_free_area *prev_fa = fa->prev;
+	size_t fa_size = fa->size;
+	struct heap_free_area *new_fa =
+	  (struct heap_free_area *)((char *)fa + size);
+
+	/* Update surrounding free-areas to point to FA's new address.  */
+	if (prev_fa)
+	  prev_fa->next = new_fa;
+	else
+	  heap->free_areas = new_fa;
+	if (next_fa)
+	  next_fa->prev = new_fa;
+
+	/* Fill in the moved descriptor.  */
+	new_fa->prev = prev_fa;
+	new_fa->next = next_fa;
+	new_fa->size = fa_size + size;
+
+	success = 1;
+	break;
+      }
+
+  HEAP_DEBUG (heap, "after __heap_append_free");
+
+  mutex_unlock (heap->lock);
+
+  return success;
+}
diff --git a/libc/stdlib/malloc/heap_free.c b/libc/stdlib/malloc/heap_free.c
new file mode 100644
index 000000000..20ef65572
--- /dev/null
+++ b/libc/stdlib/malloc/heap_free.c
@@ -0,0 +1,127 @@
+/*
+ * libc/stdlib/malloc-zarg/heap_free.c -- return memory to a heap
+ *
+ *  Copyright (C) 2002  NEC Corporation
+ *  Copyright (C) 2002  Miles Bader <miles@gnu.org>
+ *
+ * This file is subject to the terms and conditions of the GNU Lesser
+ * General Public License.  See the file COPYING.LIB in the main
+ * directory of this archive for more details.
+ * 
+ * Written by Miles Bader <miles@gnu.org>
+ */
+
+#include <stdlib.h>
+
+#include "heap.h"