From 35d29fcb08fadaf006561a058746b0fce76a6a74 Mon Sep 17 00:00:00 2001 From: Eric Andersen Date: Thu, 18 Jul 2002 15:00:07 +0000 Subject: 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! --- extra/Configs/Config.alpha | 18 +- extra/Configs/Config.arm | 16 +- extra/Configs/Config.cross.arm.uclinux | 18 +- extra/Configs/Config.h8300 | 18 +- extra/Configs/Config.i386 | 16 +- extra/Configs/Config.i960 | 16 +- extra/Configs/Config.m68k | 18 +- extra/Configs/Config.m68k.coff | 18 +- extra/Configs/Config.mips | 16 +- extra/Configs/Config.mipsel | 16 +- extra/Configs/Config.powerpc | 16 +- extra/Configs/Config.sh | 18 +- extra/Configs/Config.sparc | 16 +- extra/Configs/Config.v850e | 16 +- libc/stdlib/malloc-simple/.indent.pro | 33 -- libc/stdlib/malloc-simple/Makefile | 49 -- libc/stdlib/malloc-simple/alloc.c | 141 ----- libc/stdlib/malloc/Makefile | 24 +- libc/stdlib/malloc/alloc.c | 60 -- libc/stdlib/malloc/avlmacro.h | 226 -------- libc/stdlib/malloc/calloc.c | 32 ++ libc/stdlib/malloc/free.c | 35 ++ libc/stdlib/malloc/heap.h | 146 +++++ libc/stdlib/malloc/heap_alloc.c | 55 ++ libc/stdlib/malloc/heap_alloc_at.c | 51 ++ libc/stdlib/malloc/heap_append_free.c | 71 +++ libc/stdlib/malloc/heap_free.c | 127 +++++ libc/stdlib/malloc/malloc.c | 961 ++++----------------------------- libc/stdlib/malloc/malloc.h | 45 ++ libc/stdlib/malloc/realloc.c | 76 +++ 30 files changed, 844 insertions(+), 1524 deletions(-) delete mode 100644 libc/stdlib/malloc-simple/.indent.pro delete mode 100644 libc/stdlib/malloc-simple/Makefile delete mode 100644 libc/stdlib/malloc-simple/alloc.c delete mode 100644 libc/stdlib/malloc/alloc.c delete mode 100644 libc/stdlib/malloc/avlmacro.h create mode 100644 libc/stdlib/malloc/calloc.c create mode 100644 libc/stdlib/malloc/free.c create mode 100644 libc/stdlib/malloc/heap.h create mode 100644 libc/stdlib/malloc/heap_alloc.c create mode 100644 libc/stdlib/malloc/heap_alloc_at.c create mode 100644 libc/stdlib/malloc/heap_append_free.c create mode 100644 libc/stdlib/malloc/heap_free.c create mode 100644 libc/stdlib/malloc/malloc.h create mode 100644 libc/stdlib/malloc/realloc.c diff --git a/extra/Configs/Config.alpha b/extra/Configs/Config.alpha index f8cc9ddbc..d5160c1fa 100644 --- a/extra/Configs/Config.alpha +++ b/extra/Configs/Config.alpha @@ -86,19 +86,17 @@ HAS_LOCALE = false HAS_WCHAR = false # This specifies which malloc implementation is used. -# "malloc-simple" is very, very small, but is also very, very dumb -# and does not try to make good use of memory or clean up after itself. # -# "malloc" on the other hand is a bit bigger, but is pretty smart thereby -# minimizing memory wastage and reusing already allocated memory. This -# can be lots faster and safer IMHO. +# "malloc" use mmap for all allocations and so works very well on MMU-less +# systems that do not support the brk() system call. It is pretty smart +# about reusing already allocated memory, and minimizing memory wastage. # -# "malloc-930716" is from libc-5.3.12 and was/is the standard gnu malloc. -# It is actually smaller than "malloc", but because it is based on brk/sbrk -# it will only work on systems with an MMU. -MALLOC = malloc-simple +# "malloc-930716" is derived from libc-5.3.12 and uses the brk() system call +# for all memory allocations. This makes it very fast. It is also pretty +# smart about reusing already allocated memory, and minimizing memory wastage. +# Because this uses brk() it will not work on uClinux MMU-less systems. #MALLOC = malloc -#MALLOC = malloc-930716 +MALLOC = malloc-930716 # If you want to collect common syscall code into one function, set to this to # `true'. Set it to false otherwise. diff --git a/extra/Configs/Config.arm b/extra/Configs/Config.arm index 4d552624f..7c91b5fc6 100644 --- a/extra/Configs/Config.arm +++ b/extra/Configs/Config.arm @@ -90,17 +90,15 @@ HAS_LOCALE = false HAS_WCHAR = false # This specifies which malloc implementation is used. -# "malloc-simple" is very, very small, but is also very, very dumb -# and does not try to make good use of memory or clean up after itself. # -# "malloc" on the other hand is a bit bigger, but is pretty smart thereby -# minimizing memory wastage and reusing already allocated memory. This -# can be lots faster and safer IMHO. +# "malloc" use mmap for all allocations and so works very well on MMU-less +# systems that do not support the brk() system call. It is pretty smart +# about reusing already allocated memory, and minimizing memory wastage. # -# "malloc-930716" is from libc-5.3.12 and was/is the standard gnu malloc. -# It is actually smaller than "malloc", but because it is based on brk/sbrk -# it will only work on systems with an MMU. -#MALLOC = malloc-simple +# "malloc-930716" is derived from libc-5.3.12 and uses the brk() system call +# for all memory allocations. This makes it very fast. It is also pretty +# smart about reusing already allocated memory, and minimizing memory wastage. +# Because this uses brk() it will not work on uClinux MMU-less systems. #MALLOC = malloc MALLOC = malloc-930716 diff --git a/extra/Configs/Config.cross.arm.uclinux b/extra/Configs/Config.cross.arm.uclinux index a86931f0b..30a915f26 100644 --- a/extra/Configs/Config.cross.arm.uclinux +++ b/extra/Configs/Config.cross.arm.uclinux @@ -86,18 +86,16 @@ HAS_LOCALE = false HAS_WCHAR = false # This specifies which malloc implementation is used. -# "malloc-simple" is very, very small, but is also very, very dumb -# and does not try to make good use of memory or clean up after itself. # -# "malloc" on the other hand is a bit bigger, but is pretty smart thereby -# minimizing memory wastage and reusing already allocated memory. This -# can be lots faster and safer IMHO. +# "malloc" use mmap for all allocations and so works very well on MMU-less +# systems that do not support the brk() system call. It is pretty smart +# about reusing already allocated memory, and minimizing memory wastage. # -# "malloc-930716" is from libc-5.3.12 and was/is the standard gnu malloc. -# It is actually smaller than "malloc", but because it is based on brk/sbrk -# it will only work on systems with an MMU. -MALLOC = malloc-simple -#MALLOC = malloc +# "malloc-930716" is derived from libc-5.3.12 and uses the brk() system call +# for all memory allocations. This makes it very fast. It is also pretty +# smart about reusing already allocated memory, and minimizing memory wastage. +# Because this uses brk() it will not work on uClinux MMU-less systems. +MALLOC = malloc #MALLOC = malloc-930716 # Having brk allows one to use malloc-930716, which is an order diff --git a/extra/Configs/Config.h8300 b/extra/Configs/Config.h8300 index 8f29b8bd8..716c19d57 100644 --- a/extra/Configs/Config.h8300 +++ b/extra/Configs/Config.h8300 @@ -89,18 +89,16 @@ HAS_LOCALE = false HAS_WCHAR = false # This specifies which malloc implementation is used. -# "malloc-simple" is very, very small, but is also very, very dumb -# and does not try to make good use of memory or clean up after itself. # -# "malloc" on the other hand is a bit bigger, but is pretty smart thereby -# minimizing memory wastage and reusing already allocated memory. This -# can be lots faster and safer IMHO. +# "malloc" use mmap for all allocations and so works very well on MMU-less +# systems that do not support the brk() system call. It is pretty smart +# about reusing already allocated memory, and minimizing memory wastage. # -# "malloc-930716" is from libc-5.3.12 and was/is the standard gnu malloc. -# It is actually smaller than "malloc", but because it is based on brk/sbrk -# it will only work on systems with an MMU. -MALLOC = malloc-simple -#MALLOC = malloc +# "malloc-930716" is derived from libc-5.3.12 and uses the brk() system call +# for all memory allocations. This makes it very fast. It is also pretty +# smart about reusing already allocated memory, and minimizing memory wastage. +# Because this uses brk() it will not work on uClinux MMU-less systems. +MALLOC = malloc #MALLOC = malloc-930716 # If you want to collect common syscall code into one function, set to this to diff --git a/extra/Configs/Config.i386 b/extra/Configs/Config.i386 index 706a34223..0125417e7 100644 --- a/extra/Configs/Config.i386 +++ b/extra/Configs/Config.i386 @@ -86,17 +86,15 @@ HAS_LOCALE = false HAS_WCHAR = false # This specifies which malloc implementation is used. -# "malloc-simple" is very, very small, but is also very, very dumb -# and does not try to make good use of memory or clean up after itself. # -# "malloc" on the other hand is a bit bigger, but is pretty smart thereby -# minimizing memory wastage and reusing already allocated memory. This -# can be lots faster and safer IMHO. +# "malloc" use mmap for all allocations and so works very well on MMU-less +# systems that do not support the brk() system call. It is pretty smart +# about reusing already allocated memory, and minimizing memory wastage. # -# "malloc-930716" is from libc-5.3.12 and was/is the standard gnu malloc. -# It is actually smaller than "malloc", but because it is based on brk/sbrk -# it will only work on systems with an MMU. -#MALLOC = malloc-simple +# "malloc-930716" is derived from libc-5.3.12 and uses the brk() system call +# for all memory allocations. This makes it very fast. It is also pretty +# smart about reusing already allocated memory, and minimizing memory wastage. +# Because this uses brk() it will not work on uClinux MMU-less systems. #MALLOC = malloc MALLOC = malloc-930716 diff --git a/extra/Configs/Config.i960 b/extra/Configs/Config.i960 index 65d563b7f..0c073e9e8 100644 --- a/extra/Configs/Config.i960 +++ b/extra/Configs/Config.i960 @@ -86,17 +86,15 @@ HAS_LOCALE = false HAS_WCHAR = false # This specifies which malloc implementation is used. -# "malloc-simple" is very, very small, but is also very, very dumb -# and does not try to make good use of memory or clean up after itself. # -# "malloc" on the other hand is a bit bigger, but is pretty smart thereby -# minimizing memory wastage and reusing already allocated memory. This -# can be lots faster and safer IMHO. +# "malloc" use mmap for all allocations and so works very well on MMU-less +# systems that do not support the brk() system call. It is pretty smart +# about reusing already allocated memory, and minimizing memory wastage. # -# "malloc-930716" is from libc-5.3.12 and was/is the standard gnu malloc. -# It is actually smaller than "malloc", but because it is based on brk/sbrk -# it will only work on systems with an MMU. -#MALLOC = malloc-simple +# "malloc-930716" is derived from libc-5.3.12 and uses the brk() system call +# for all memory allocations. This makes it very fast. It is also pretty +# smart about reusing already allocated memory, and minimizing memory wastage. +# Because this uses brk() it will not work on uClinux MMU-less systems. MALLOC = malloc #MALLOC = malloc-930716 diff --git a/extra/Configs/Config.m68k b/extra/Configs/Config.m68k index 90e1d4783..6a68fe786 100644 --- a/extra/Configs/Config.m68k +++ b/extra/Configs/Config.m68k @@ -86,18 +86,16 @@ HAS_LOCALE = false HAS_WCHAR = false # This specifies which malloc implementation is used. -# "malloc-simple" is very, very small, but is also very, very dumb -# and does not try to make good use of memory or clean up after itself. # -# "malloc" on the other hand is a bit bigger, but is pretty smart thereby -# minimizing memory wastage and reusing already allocated memory. This -# can be lots faster and safer IMHO. +# "malloc" use mmap for all allocations and so works very well on MMU-less +# systems that do not support the brk() system call. It is pretty smart +# about reusing already allocated memory, and minimizing memory wastage. # -# "malloc-930716" is from libc-5.3.12 and was/is the standard gnu malloc. -# It is actually smaller than "malloc", but because it is based on brk/sbrk -# it will only work on systems with an MMU. -MALLOC = malloc-simple -#MALLOC = malloc +# "malloc-930716" is derived from libc-5.3.12 and uses the brk() system call +# for all memory allocations. This makes it very fast. It is also pretty +# smart about reusing already allocated memory, and minimizing memory wastage. +# Because this uses brk() it will not work on uClinux MMU-less systems. +MALLOC = malloc #MALLOC = malloc-930716 # Having brk allows one to use malloc-930716, which is an order diff --git a/extra/Configs/Config.m68k.coff b/extra/Configs/Config.m68k.coff index 0ca204a7c..73cc40d23 100644 --- a/extra/Configs/Config.m68k.coff +++ b/extra/Configs/Config.m68k.coff @@ -86,18 +86,16 @@ HAS_LOCALE = false HAS_WCHAR = false # This specifies which malloc implementation is used. -# "malloc-simple" is very, very small, but is also very, very dumb -# and does not try to make good use of memory or clean up after itself. # -# "malloc" on the other hand is a bit bigger, but is pretty smart thereby -# minimizing memory wastage and reusing already allocated memory. This -# can be lots faster and safer IMHO. +# "malloc" use mmap for all allocations and so works very well on MMU-less +# systems that do not support the brk() system call. It is pretty smart +# about reusing already allocated memory, and minimizing memory wastage. # -# "malloc-930716" is from libc-5.3.12 and was/is the standard gnu malloc. -# It is actually smaller than "malloc", but because it is based on brk/sbrk -# it will only work on systems with an MMU. -MALLOC = malloc-simple -#MALLOC = malloc +# "malloc-930716" is derived from libc-5.3.12 and uses the brk() system call +# for all memory allocations. This makes it very fast. It is also pretty +# smart about reusing already allocated memory, and minimizing memory wastage. +# Because this uses brk() it will not work on uClinux MMU-less systems. +MALLOC = malloc #MALLOC = malloc-930716 # Having brk allows one to use malloc-930716, which is an order diff --git a/extra/Configs/Config.mips b/extra/Configs/Config.mips index eac4dd6ad..75ad13b43 100644 --- a/extra/Configs/Config.mips +++ b/extra/Configs/Config.mips @@ -89,17 +89,15 @@ HAS_LOCALE = false HAS_WCHAR = false # This specifies which malloc implementation is used. -# "malloc-simple" is very, very small, but is also very, very dumb -# and does not try to make good use of memory or clean up after itself. # -# "malloc" on the other hand is a bit bigger, but is pretty smart thereby -# minimizing memory wastage and reusing already allocated memory. This -# can be lots faster and safer IMHO. +# "malloc" use mmap for all allocations and so works very well on MMU-less +# systems that do not support the brk() system call. It is pretty smart +# about reusing already allocated memory, and minimizing memory wastage. # -# "malloc-930716" is from libc-5.3.12 and was/is the standard gnu malloc. -# It is actually smaller than "malloc", but because it is based on brk/sbrk -# it will only work on systems with an MMU. -#MALLOC = malloc-simple +# "malloc-930716" is derived from libc-5.3.12 and uses the brk() system call +# for all memory allocations. This makes it very fast. It is also pretty +# smart about reusing already allocated memory, and minimizing memory wastage. +# Because this uses brk() it will not work on uClinux MMU-less systems. #MALLOC = malloc MALLOC = malloc-930716 diff --git a/extra/Configs/Config.mipsel b/extra/Configs/Config.mipsel index acb00142b..c302199f7 100644 --- a/extra/Configs/Config.mipsel +++ b/extra/Configs/Config.mipsel @@ -89,17 +89,15 @@ HAS_LOCALE = false HAS_WCHAR = false # This specifies which malloc implementation is used. -# "malloc-simple" is very, very small, but is also very, very dumb -# and does not try to make good use of memory or clean up after itself. # -# "malloc" on the other hand is a bit bigger, but is pretty smart thereby -# minimizing memory wastage and reusing already allocated memory. This -# can be lots faster and safer IMHO. +# "malloc" use mmap for all allocations and so works very well on MMU-less +# systems that do not support the brk() system call. It is pretty smart +# about reusing already allocated memory, and minimizing memory wastage. # -# "malloc-930716" is from libc-5.3.12 and was/is the standard gnu malloc. -# It is actually smaller than "malloc", but because it is based on brk/sbrk -# it will only work on systems with an MMU. -#MALLOC = malloc-simple +# "malloc-930716" is derived from libc-5.3.12 and uses the brk() system call +# for all memory allocations. This makes it very fast. It is also pretty +# smart about reusing already allocated memory, and minimizing memory wastage. +# Because this uses brk() it will not work on uClinux MMU-less systems. #MALLOC = malloc MALLOC = malloc-930716 diff --git a/extra/Configs/Config.powerpc b/extra/Configs/Config.powerpc index 4cd446979..1d1cacf68 100644 --- a/extra/Configs/Config.powerpc +++ b/extra/Configs/Config.powerpc @@ -86,17 +86,15 @@ HAS_LOCALE = false HAS_WCHAR = false # This specifies which malloc implementation is used. -# "malloc-simple" is very, very small, but is also very, very dumb -# and does not try to make good use of memory or clean up after itself. # -# "malloc" on the other hand is a bit bigger, but is pretty smart thereby -# minimizing memory wastage and reusing already allocated memory. This -# can be lots faster and safer IMHO. +# "malloc" use mmap for all allocations and so works very well on MMU-less +# systems that do not support the brk() system call. It is pretty smart +# about reusing already allocated memory, and minimizing memory wastage. # -# "malloc-930716" is from libc-5.3.12 and was/is the standard gnu malloc. -# It is actually smaller than "malloc", but because it is based on brk/sbrk -# it will only work on systems with an MMU. -#MALLOC = malloc-simple +# "malloc-930716" is derived from libc-5.3.12 and uses the brk() system call +# for all memory allocations. This makes it very fast. It is also pretty +# smart about reusing already allocated memory, and minimizing memory wastage. +# Because this uses brk() it will not work on uClinux MMU-less systems. #MALLOC = malloc MALLOC = malloc-930716 diff --git a/extra/Configs/Config.sh b/extra/Configs/Config.sh index 399d6bcc5..0b6fccc25 100644 --- a/extra/Configs/Config.sh +++ b/extra/Configs/Config.sh @@ -110,18 +110,16 @@ HAS_LOCALE = false HAS_WCHAR = false # This specifies which malloc implementation is used. -# "malloc-simple" is very, very small, but is also very, very dumb -# and does not try to make good use of memory or clean up after itself. # -# "malloc" on the other hand is a bit bigger, but is pretty smart thereby -# minimizing memory wastage and reusing already allocated memory. This -# can be lots faster and safer IMHO. +# "malloc" use mmap for all allocations and so works very well on MMU-less +# systems that do not support the brk() system call. It is pretty smart +# about reusing already allocated memory, and minimizing memory wastage. # -# "malloc-930716" is from libc-5.3.12 and was/is the standard gnu malloc. -# It is actually smaller than "malloc", but because it is based on brk/sbrk -# it will only work on systems with an MMU. -MALLOC = malloc-simple -#MALLOC = malloc +# "malloc-930716" is derived from libc-5.3.12 and uses the brk() system call +# for all memory allocations. This makes it very fast. It is also pretty +# smart about reusing already allocated memory, and minimizing memory wastage. +# Because this uses brk() it will not work on uClinux MMU-less systems. +MALLOC = malloc #MALLOC = malloc-930716 # If you want to collect common syscall code into one function, set to this to diff --git a/extra/Configs/Config.sparc b/extra/Configs/Config.sparc index 761262365..f96e83020 100644 --- a/extra/Configs/Config.sparc +++ b/extra/Configs/Config.sparc @@ -86,17 +86,15 @@ HAS_LOCALE = false HAS_WCHAR = false # This specifies which malloc implementation is used. -# "malloc-simple" is very, very small, but is also very, very dumb -# and does not try to make good use of memory or clean up after itself. # -# "malloc" on the other hand is a bit bigger, but is pretty smart thereby -# minimizing memory wastage and reusing already allocated memory. This -# can be lots faster and safer IMHO. +# "malloc" use mmap for all allocations and so works very well on MMU-less +# systems that do not support the brk() system call. It is pretty smart +# about reusing already allocated memory, and minimizing memory wastage. # -# "malloc-930716" is from libc-5.3.12 and was/is the standard gnu malloc. -# It is actually smaller than "malloc", but because it is based on brk/sbrk -# it will only work on systems with an MMU. -#MALLOC = malloc-simple +# "malloc-930716" is derived from libc-5.3.12 and uses the brk() system call +# for all memory allocations. This makes it very fast. It is also pretty +# smart about reusing already allocated memory, and minimizing memory wastage. +# Because this uses brk() it will not work on uClinux MMU-less systems. #MALLOC = malloc MALLOC = malloc-930716 diff --git a/extra/Configs/Config.v850e b/extra/Configs/Config.v850e index f1e618a0c..bd0a62c9b 100644 --- a/extra/Configs/Config.v850e +++ b/extra/Configs/Config.v850e @@ -88,17 +88,15 @@ HAS_LOCALE = false HAS_WCHAR = false # This specifies which malloc implementation is used. -# "malloc-simple" is very, very small, but is also very, very dumb -# and does not try to make good use of memory or clean up after itself. # -# "malloc" on the other hand is a bit bigger, but is pretty smart thereby -# minimizing memory wastage and reusing already allocated memory. This -# can be lots faster and safer IMHO. +# "malloc" use mmap for all allocations and so works very well on MMU-less +# systems that do not support the brk() system call. It is pretty smart +# about reusing already allocated memory, and minimizing memory wastage. # -# "malloc-930716" is from libc-5.3.12 and was/is the standard gnu malloc. -# It is actually smaller than "malloc", but because it is based on brk/sbrk -# it will only work on systems with an MMU. -#MALLOC = malloc-simple +# "malloc-930716" is derived from libc-5.3.12 and uses the brk() system call +# for all memory allocations. This makes it very fast. It is also pretty +# smart about reusing already allocated memory, and minimizing memory wastage. +# Because this uses brk() it will not work on uClinux MMU-less systems. MALLOC = malloc #MALLOC = malloc-930716 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 -# -# 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 -#include -#include -#include -#include -#include -#include - - -#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 +# Copyright (C) 2002 NEC Corporation +# Copyright (C) 2002 Miles Bader # # 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 -#include -#include -#include -#include -#include - - -#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 + * + * 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 + */ + +#include +#include + +#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 + * + * 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 + */ + +#include +#include + +#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 + * + * 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 + */ + +#include + + +#ifdef __UCLIBC_HAS_THREADS__ +#include +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 +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 + * + * 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 + */ + +#include + +#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 + * + * 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 + */ + +#include + +#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 + * + * 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 + */ + +#include + +#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 + * + * 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 + */ + +#include + +#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 * - * 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 */ -#include -#ifndef _XOPEN_SOURCE -#define _XOPEN_SOURCE -#endif -#include -#include -#include -#include -#include -#include +#include #include -#include -#include "malloc.h" -#include - -#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) */ -#define DIV8(v) ((v)/8) - -#if M_MULTITHREADED -#error This version does not support threads -#else -typedef int mutex_t; - -#define mutex_lock(x) -#define mutex_unlock(x) -#define mutex_init(x) -#define MUTEX_INITIALIZER 0 -//static mutex_t malloc_lock = MUTEX_INITIALIZER; -#endif - -extern int __malloc_initialized; - -#ifdef L__malloc_init -int __malloc_initialized = -1; - - /* -1 == uninitialized, 0 == initializing, 1 == initialized */ -#endif - -#ifndef MAP_FAILED -#define MAP_FAILED ((void*)-1) -#endif - -#if defined(MAP_ANONYMOUS) && !defined(MAP_ANON) -#define MAP_ANON MAP_ANONYMOUS -#endif - -#ifndef NULL -#define NULL ((void*)0) -#endif - -/* guess pagesize */ -#define M_PAGESIZE getpagesize() - -/* HUNK MANAGER */ - -typedef struct Hunk_s Hunk_t; - -struct Hunk_s { /* Hunked block - 8 byte overhead */ - int id; /* unique id */ - unsigned int total:12, used:12, size:8; - Hunk_t *next; /* next free in __free_h */ -}; - -#define usagemap(h) (((unsigned char *)(h))+sizeof(Hunk_t)) -#define hunk_ptr(h) (((char*)(h))+sizeof(Hunk_t)+ALIGN(DIV8(h->total+7))) -#define hunk(h) ((Hunk_t*)(h)) - -extern Hunk_t *__free_h[HUNK_MAXSIZE + 1]; -extern int __total_h[HUNK_MAXSIZE + 1]; - -#ifdef L__malloc_init -Hunk_t *__free_h[HUNK_MAXSIZE + 1]; /* free hash */ -int __total_h[HUNK_MAXSIZE + 1]; /* Hunk_t's `total` member */ -#endif - -extern void *__hunk_alloc(int size); - -#ifdef L_malloc -/* __hunk_alloc allocates <= HUNK_MAXSIZE blocks */ -void *__hunk_alloc(int size) -{ - Hunk_t *p; - unsigned long *cpl; - int i, c; - - // if (size >= HUNK_THRESHOLD) - size = ALIGN(size); - - /* Look for already allocated hunkblocks */ - if ((p = __free_h[size]) == NULL) { - if ( - (p = - (Hunk_t *) mmap(HUNK_MSTART, HUNK_MSIZE, - PROT_READ | PROT_WRITE, -#ifdef __UCLIBC_HAS_MMU__ - MAP_PRIVATE | MAP_ANONYMOUS -#else - MAP_SHARED | MAP_ANONYMOUS -#endif - , 0, 0)) == (Hunk_t *) MAP_FAILED) - // { - // printf("hunk_alloc failed: %d, %d\n", size, errno); - return NULL; - // } - memset(p, 0, HUNK_MSIZE); - p->id = HUNK_ID; - p->total = __total_h[size]; - /* p->used = 0; */ - p->size = size; - /* p->next = (Hunk_t*)NULL; */ - /* memset(usagemap(p), 0, bound); */ - __free_h[size] = p; - } - - /* Locate free point in usagemap */ - - /* First find a word where not all the bits are set */ - for (cpl = (unsigned long *) usagemap(p); *cpl == 0xFFFFFFFF; cpl++); - - /* Remember the byte position of that word */ - i = ((unsigned char *) cpl) - usagemap(p); - - /* Now find find a free bit in the word using binary search */ - if (*(unsigned short *) cpl != 0xFFFF) { - - if (*(unsigned char *) cpl == 0xFF) { - c = *(((unsigned char *) cpl) + 1); - i++; - } - else - { - c = *(unsigned char *) cpl; - } - } else { - i += 2; - c = *(((unsigned char *) cpl) + 2); - if (c == 0xFF) { - c = *(((unsigned char *) cpl) + 3); - i++; - } - } - - /* - * Multiply i by 8 for the bit position - * Further down, we divide by 8 again to find the byte position - */ - EMUL8(i); - - /* If bottom nibble is set, shift down the top nibble */ - if ((c & 0xF) == 0xF) { - c >>= 4; - i += 4; - } - - /* If bottom 2 bits are set, shift down the top two */ - if ((c & 0x3) == 0x3) { - c >>= 2; - i += 2; - } - - /* Check which one of the two bits is set */ - if (c & 1) - i++; - - usagemap(p)[DIV8(i)] |= (1 << (i & 7)); /* set bit */ - /* Increment counter and update hashes */ - if (++p->used == p->total) { - __free_h[p->size] = p->next; - p->next = NULL; - } - - // fprintf(stderr, "hunk_alloc: i=%d, p->size=%d, p=%p\n", i, p->size, p); - return hunk_ptr(p) + i * p->size; -} -#endif /* L_malloc */ - -extern void __hunk_free(char *ptr); - -#ifdef L__free_support -/* __hunk_free frees blocks allocated by __hunk_alloc */ -void __hunk_free(char *ptr) -{ - unsigned char *up; - int i, v; - Hunk_t *h; - - if (!ptr) - return; - - h = (Hunk_t *) PAGE_DOWNALIGNP(ptr); - - /* Validate `ptr` */ - if (h->id != HUNK_ID) - return; - v = ptr - hunk_ptr(h); - i = v / h->size; - if (v % h->size != 0 || i < 0 || i >= h->total) - return; - - /* Update `usagemap` */ - up = &(usagemap(h)[DIV8(i)]); - i = 1 << (i & 7); - if (!(*up & i)) - return; - *up ^= i; - - /* Update hunk counters */ - if (h->used == h->total) { - if (--h->used) { /* insert into __free_h */ - h->next = __free_h[h->size]; - __free_h[h->size] = h; - } /* else - it will be unmapped */ - } else { - if (!--h->used) { /* delete from __free_h - will be __bl_freed */ - Hunk_t *p, *pp; - - for (p = __free_h[h->size], pp = NULL; p != h; - pp = p, p = p->next); - if (!pp) - __free_h[h->size] = p->next; - else - pp->next = p->next; - } - } - - /* Unmap empty Hunk_t */ - if (!h->used) - munmap((void *) h, HUNK_MSIZE); -} -#endif /* L__free_support */ - -/* BLOCK MANAGER */ - -typedef struct Block_s Block_t; - -struct Block_s { /* 32-bytes long control structure (if 4-byte aligned) */ - char *ptr; /* pointer to related data */ - Block_t *next; /* next in free_mem list */ - Block_t *l_free_mem, *r_free_mem; /* left & right subtrees of */ - Block_t *l_ptrs, *r_ptrs; /* left & right subtrees of */ - size_t size; /* size - divided by align */ - - /* packed 4-byte attributes */ -/* { */ - signed char bal_free_mem:8; /* balance of subtree */ - signed char bal_ptrs:8; /* balance of subtree */ - unsigned int used:1; /* used/free state of the block */ - unsigned int broken:1; /* 1 if previous block can't be merged with it */ -/* } */ -}; - -extern Block_t *__bl_last; /* last mmapped block */ - -#ifdef L__malloc_init -Block_t *__bl_last; /* last mmapped block */ -#endif - -#define bl_get() __hunk_alloc(sizeof(Block_t)) -#define bl_rel(p) __hunk_free((char*)p) - -extern Block_t *__Avl_Block_tfree_mem_tree; -extern Block_t *__free_mem_ins(Block_t * data); -extern void __free_mem_del(Block_t * data); -extern void __free_mem_replace(Block_t * data); -extern Block_t *__Avl_Block_tptrs_tree; -extern Block_t *__ptrs_ins(Block_t * data); -extern void __ptrs_del(Block_t * data); - -extern void __bl_uncommit(Block_t * b); -extern void __bl_free(Block_t * b); - -/* like C++ templates ;-) */ -#include "avlmacro.h" - -#define FREE_MEM_COMPARE(i,a,b) \ -{ \ - if ( (a)->size < (b)->size ) { \ - i = -1; \ - } else if ( (a)->size > (b)->size ) { \ - i = 1; \ - } else { \ - i = 0; \ - } \ -} - -#define PTRS_COMPARE(i,a,b) \ -{ \ - if ( (a)->ptr < (b)->ptr ) { \ - i = -1; \ - } else if ( (a)->ptr > (b)->ptr ) { \ - i = 1; \ - } else { \ - i = 0; \ - } \ -} - -#ifdef L__avl_support -Avl_Tree(free_mem, Block_t, free_mem, FREE_MEM_COMPARE) - Avl_Tree_no_replace(ptrs, Block_t, ptrs, PTRS_COMPARE) -#endif -#define free_mem_root Avl_Root(Block_t, free_mem) -#define ptrs_root Avl_Root(Block_t, ptrs) -/* pp is freed block */ -#define FREE_MEM_DEL_BLOCK(pp,p) {p = __free_mem_del_block(pp,p);} -extern Block_t *__free_mem_del_block(Block