summaryrefslogtreecommitdiff
path: root/libc/stdlib/malloc
diff options
context:
space:
mode:
authorEric Andersen <andersen@codepoet.org>2002-07-18 15:00:07 +0000
committerEric Andersen <andersen@codepoet.org>2002-07-18 15:00:07 +0000
commit35d29fcb08fadaf006561a058746b0fce76a6a74 (patch)
treeb42a59394f8ee7dc7c11f71ae2d45b1e1beb834b /libc/stdlib/malloc
parent3b1e82407a02aed6319c6686c5b06c2051a20cca (diff)
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!
Diffstat (limited to 'libc/stdlib/malloc')
-rw-r--r--libc/stdlib/malloc/Makefile24
-rw-r--r--libc/stdlib/malloc/alloc.c60
-rw-r--r--libc/stdlib/malloc/avlmacro.h226
-rw-r--r--libc/stdlib/malloc/calloc.c32
-rw-r--r--libc/stdlib/malloc/free.c35
-rw-r--r--libc/stdlib/malloc/heap.h146
-rw-r--r--libc/stdlib/malloc/heap_alloc.c55
-rw-r--r--libc/stdlib/malloc/heap_alloc_at.c51
-rw-r--r--libc/stdlib/malloc/heap_append_free.c71
-rw-r--r--libc/stdlib/malloc/heap_free.c127
-rw-r--r--libc/stdlib/malloc/malloc.c961
-rw-r--r--libc/stdlib/malloc/malloc.h45
-rw-r--r--libc/stdlib/malloc/realloc.c76
13 files changed, 740 insertions, 1169 deletions
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"
+
+
+/* Return the memory area MEM of size SIZE to HEAP. */
+void
+__heap_free (struct heap *heap, void *mem, size_t size)
+{
+ struct heap_free_area *prev_fa, *fa, *new_fa;
+ void *end = (char *)mem + size;
+
+ mutex_lock (heap->lock);
+
+ HEAP_DEBUG (heap, "before __heap_free");
+
+ /* Find an adjacent free-list entry. */
+ for (prev_fa = 0, fa = heap->free_areas; fa; prev_fa = fa, fa = fa->next)
+ {
+ size_t fa_size = fa->size;
+ void *fa_end = HEAP_FREE_AREA_END (fa);
+ void *fa_mem = HEAP_FREE_AREA_START (fa);
+
+ if (fa_mem == end)
+ /* FA is just after MEM, grow down to encompass it. */
+ {
+ fa_size += size;
+
+ /* See if FA can now be merged with its predecessor. */
+ if (prev_fa && fa_mem - size == HEAP_FREE_AREA_END (prev_fa))
+ /* Yup; merge PREV_FA's info into FA. */
+ {
+ struct heap_free_area *pp = prev_fa->prev;
+ fa_size += prev_fa->size;
+ if (pp)
+ pp->next = fa;
+ else
+ heap->free_areas = fa;
+ fa->prev = pp;
+ }
+
+ fa->size = fa_size;
+
+ goto done;
+ }
+ else if (fa_end == mem)
+ /* FA is just before MEM, 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 && fa_end + size == HEAP_FREE_AREA_START (next_fa))
+ {
+ /* Yup; merge FA's info into NEXT_FA. */
+ fa_size += next_fa->size;
+ if (prev_fa)
+ prev_fa->next = next_fa;
+ else
+ heap->free_areas = next_fa;
+ next_fa->prev = prev_fa;
+ fa = next_fa;
+ }
+ else
+ /* FA can't be merged; move the descriptor for it to the tail-end
+ of the memory block. */
+ {
+ 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;
+ fa = new_fa;
+ }
+
+ fa->size = fa_size;
+
+ goto done;
+ }
+ else if (fa_mem > mem)
+ /* We've reached the right spot in the free-list without finding an
+ adjacent free-area, so add a new free area to hold MEM. */
+ break;
+ }
+
+ /* Make a new free-list entry. */
+
+ /* NEW_FA initially holds only MEM. */
+ new_fa = (struct heap_free_area *)
+ ((char *)mem + size - sizeof (struct heap_free_area));
+ new_fa->size = size;
+ new_fa->next = fa;
+ new_fa->prev = prev_fa;
+
+ /* Insert NEW_FA in the free-list between PREV_FA and FA. */
+ if (prev_fa)
+ prev_fa->next = new_fa;
+ else
+ heap->free_areas = new_fa;
+ if (fa)
+ fa->prev = new_fa;
+
+ done:
+ HEAP_DEBUG (heap, "after __heap_free");
+
+ mutex_unlock (heap->lock);
+}
diff --git a/libc/stdlib/malloc/malloc.c b/libc/stdlib/malloc/malloc.c
index 9a3bbb332..317b10840 100644
--- a/libc/stdlib/malloc/malloc.c
+++ b/libc/stdlib/malloc/malloc.c
@@ -1,880 +1,107 @@
/*
- malloc - heap manager based on heavy use of virtual memory management.
- Copyright (C) 1998 Valery Shchedrin
-
- This library 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 library 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 library; if not, write to the Free
- Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
- MA 02111-1307, USA
-
- Public Functions:
-
- void *malloc(size_t size);
-
- Allocates `size` bytes
- returns NULL if no free memory available
-
- void *calloc(size_t unit, size_t quantity);
-
- Allocates `quantity*unit` zeroed bytes via internal malloc call
-
- void *realloc(void *ptr, size_t size);
-
- Reallocates already allocated block `ptr`, if `ptr` is not valid block
- then it works as malloc. NULL is returned if no free memory available
-
- void *_realloc_no_move(void *ptr, size_t size);
-
- Reallocates already allocated block `ptr`, if `ptr` is not valid block
- or if reallocation can't be done with shrinking/expanding already
- allocated block NULL is returned
-
- void free(void *ptr);
-
- Frees already allocated block, if `ptr` is incorrect one nothing will
- happen.
-*/
-
-/*
- * Manuel Novoa III Jan 2001
+ * libc/stdlib/malloc-zarg/malloc.c -- malloc function
+ *
+ * Copyright (C) 2002 NEC Corporation
+ * Copyright (C) 2002 Miles Bader <miles@gnu.org>
*
- * Modified to decrease object sizes.
- * Broke into independent object files.
- * Converted INIT_BLOCK() and FREE_MEM_DEL_BLOCK() from macros to functions.
+ * 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>
-#ifndef _XOPEN_SOURCE
-#define _XOPEN_SOURCE
-#endif
-#include <sys/types.h>
-#include <unistd.h>
-#include <limits.h>
-#include <sys/time.h>
-#include <asm/page.h>
-#include <unistd.h>
+#include <stdlib.h>
#include <sys/mman.h>
-#include <string.h>
-#include "malloc.h"
-#include <stdio.h>
-
-#define M_DOTRIMMING 1
-#define M_MULTITHREADED 0
-
-#define VALLOC_MSTART ((void*)0x1c000000)
-#define LARGE_MSTART ((void*)0x19000000)
-#define HUNK_MSTART ((void*)0x18000000)
-#define HUNK_MSIZE M_PAGESIZE
-#define HUNK_ID 0x99171713
-
-/* alignment of allocations > HUNK_THRESHOLD */
-#define MALLOC_ALIGN 4
-
-/* allocations < HUNK_THRESHOLD will not be aligned */
-#define HUNK_THRESHOLD 4
-
-/*up to HUNK_MAXSIZE blocks will be joined together to decrease memory waste*/
-#define HUNK_MAXSIZE 128
-
-/* returns value not less than size, aligned to MALLOC_ALIGN */
-#define ALIGN(size) (((size)+(MALLOC_ALIGN)-1)&(~((MALLOC_ALIGN)-1)))
-
-/* aligns s or p to page boundaries */
-#define PAGE_ALIGN(s) (((s)+M_PAGESIZE-1)&(~(M_PAGESIZE-1)))
-#define PAGE_ALIGNP(p) ((char*)PAGE_ALIGN((unsigned)(p)))
-#define PAGE_DOWNALIGNP(p) ((char*)(((unsigned)(p))&(~(M_PAGESIZE-1))))
-
-/* returns v * 2 for your machine (speed-up) */
-#define MUL2(v) ((v)*2)
-
-/* does v *= 8 for your machine (speed-up) */
-#define EMUL8(v) v*=8
-
-/* does v/8 for your machind (speed-up) */