From 8d532c51318bad2436880ecac972c9dfa3996c9b Mon Sep 17 00:00:00 2001 From: Eric Andersen Date: Tue, 30 Dec 2003 10:40:49 +0000 Subject: Rework malloc. The new default implementation is based on dlmalloc from Doug Lea. It is about 2x faster than the old malloc-930716, and behave itself much better -- it will properly release memory back to the system, and it uses a combination of brk() for small allocations and mmap() for larger allocations. -Erik --- debian/config | 3 +- extra/Configs/Config.in | 28 +- libc/stdlib/Makefile | 9 +- libc/stdlib/calloc.c | 41 -- libc/stdlib/malloc-930716/Makefile | 46 -- libc/stdlib/malloc-930716/README | 40 -- libc/stdlib/malloc-930716/malloc.c | 445 ------------ libc/stdlib/malloc-930716/malloc.h | 89 --- libc/stdlib/malloc-930716/memalign.c | 67 -- libc/stdlib/malloc-930716/realloc.c | 142 ---- libc/stdlib/malloc-simple/alloc.c | 29 +- libc/stdlib/malloc-standard/Makefile | 51 ++ libc/stdlib/malloc-standard/calloc.c | 93 +++ libc/stdlib/malloc-standard/free.c | 382 +++++++++++ libc/stdlib/malloc-standard/mallinfo.c | 81 +++ libc/stdlib/malloc-standard/malloc.c | 1160 ++++++++++++++++++++++++++++++++ libc/stdlib/malloc-standard/malloc.h | 953 ++++++++++++++++++++++++++ libc/stdlib/malloc-standard/mallopt.c | 64 ++ libc/stdlib/malloc-standard/memalign.c | 126 ++++ libc/stdlib/malloc-standard/realloc.c | 237 +++++++ libc/stdlib/malloc/Makefile | 3 +- libc/stdlib/malloc/calloc.c | 41 ++ 22 files changed, 3239 insertions(+), 891 deletions(-) delete mode 100644 libc/stdlib/calloc.c delete mode 100644 libc/stdlib/malloc-930716/Makefile delete mode 100644 libc/stdlib/malloc-930716/README delete mode 100644 libc/stdlib/malloc-930716/malloc.c delete mode 100644 libc/stdlib/malloc-930716/malloc.h delete mode 100644 libc/stdlib/malloc-930716/memalign.c delete mode 100644 libc/stdlib/malloc-930716/realloc.c create mode 100644 libc/stdlib/malloc-standard/Makefile create mode 100644 libc/stdlib/malloc-standard/calloc.c create mode 100644 libc/stdlib/malloc-standard/free.c create mode 100644 libc/stdlib/malloc-standard/mallinfo.c create mode 100644 libc/stdlib/malloc-standard/malloc.c create mode 100644 libc/stdlib/malloc-standard/malloc.h create mode 100644 libc/stdlib/malloc-standard/mallopt.c create mode 100644 libc/stdlib/malloc-standard/memalign.c create mode 100644 libc/stdlib/malloc-standard/realloc.c create mode 100644 libc/stdlib/malloc/calloc.c diff --git a/debian/config b/debian/config index b1c32ab81..487198a72 100644 --- a/debian/config +++ b/debian/config @@ -45,7 +45,8 @@ UCLIBC_HAS_THREADS=y PTHREADS_DEBUG_SUPPORT=y UCLIBC_HAS_LFS=y # MALLOC is not set -MALLOC_930716=y +# MALLOC_SIMPLE is not set +MALLOC_STANDARD=y MALLOC_GLIBC_COMPAT=y UCLIBC_DYNAMIC_ATEXIT=y HAS_SHADOW=y diff --git a/extra/Configs/Config.in b/extra/Configs/Config.in index 151d60216..8f5eee439 100644 --- a/extra/Configs/Config.in +++ b/extra/Configs/Config.in @@ -287,24 +287,36 @@ config UCLIBC_HAS_LFS choice prompt "Malloc Implementation" - default MALLOC_930716 + default MALLOC if ! UCLIBC_HAS_MMU + default MALLOC_STANDARD if UCLIBC_HAS_MMU help "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. + This is the default for uClinux MMU-less systems. - "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-simple" was written from scratch for uClibc, and is the + simplest possible (and therefore smallest) malloc implementation. + It is rather dumb, and certainly isn't the fastest. But it is 100% + standards compliant, thread safe, and very small. - If unsure, answer "malloc". + "malloc-standard" is derived from the public domain dlmalloc + implementation by Doug Lea. It is quite fast, and is pretty smart + about reusing already allocated memory, and minimizing memory + wastage. This uses brk() for small allocations, while using mmap() + for larger allocations. This is the default malloc implementation + for uClibc. + + If unsure, answer "malloc-standard". config MALLOC bool "malloc" -config MALLOC_930716 - bool "malloc-930716" +config MALLOC_SIMPLE + bool "malloc-simple" + +config MALLOC_STANDARD + bool "malloc-standard" depends on UCLIBC_HAS_MMU endchoice diff --git a/libc/stdlib/Makefile b/libc/stdlib/Makefile index a22a8eb0a..878d2bd03 100644 --- a/libc/stdlib/Makefile +++ b/libc/stdlib/Makefile @@ -28,8 +28,11 @@ DIRS:= ifeq ($(MALLOC),y) DIRS+=malloc endif -ifeq ($(MALLOC_930716),y) - DIRS+=malloc-930716 +ifeq ($(MALLOC_SIMPLE),y) + DIRS+=malloc-simple +endif +ifeq ($(MALLOC_STANDARD),y) + DIRS+=malloc-standard endif @@ -83,7 +86,7 @@ CSRC = abort.c getenv.c mkdtemp.c mktemp.c realpath.c mkstemp.c mkstemp64.c \ ptsname.c grantpt.c unlockpt.c gcvt.c drand48-iter.c jrand48.c \ jrand48_r.c lrand48.c lrand48_r.c mrand48.c mrand48_r.c nrand48.c \ nrand48_r.c rand_r.c srand48.c srand48_r.c seed48.c seed48_r.c \ - calloc.c valloc.c + valloc.c ifeq ($(UCLIBC_HAS_FLOATS),y) CSRC += drand48.c drand48_r.c erand48.c erand48_r.c endif diff --git a/libc/stdlib/calloc.c b/libc/stdlib/calloc.c deleted file mode 100644 index 15281a97f..000000000 --- a/libc/stdlib/calloc.c +++ /dev/null @@ -1,41 +0,0 @@ -/* vi: set sw=4 ts=4: */ -/* calloc for uClibc - * - * Copyright (C) 2002 by 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 - */ - -#include -#include -#include - -void * calloc(size_t nmemb, size_t lsize) -{ - void *result; - size_t size=lsize * nmemb; - - /* guard vs integer overflow, but allow nmemb - * to fall through and call malloc(0) */ - if (nmemb && lsize != (size / nmemb)) { - __set_errno(ENOMEM); - return NULL; - } - if ((result=malloc(size)) != NULL) { - memset(result, 0, size); - } - return result; -} - diff --git a/libc/stdlib/malloc-930716/Makefile b/libc/stdlib/malloc-930716/Makefile deleted file mode 100644 index bd52b21e9..000000000 --- a/libc/stdlib/malloc-930716/Makefile +++ /dev/null @@ -1,46 +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 - -# calloc.c can be found at uClibc/libc/stdlib/calloc.c -# valloc.c can be found at uClibc/libc/stdlib/valloc.c -CSRC=malloc.c memalign.c realloc.c -COBJS=$(patsubst %.c,%.o, $(CSRC)) -OBJS=$(COBJS) - -all: $(OBJS) $(LIBC) - -$(LIBC): ar-target - -ar-target: $(OBJS) - $(AR) $(ARFLAGS) $(LIBC) $(OBJS) - -$(COBJS): %.o : %.c - $(CC) $(CFLAGS) -c $< -o $@ - $(STRIPTOOL) -x -R .note -R .comment $*.o - -clean: - $(RM) *.[oa] *~ core - diff --git a/libc/stdlib/malloc-930716/README b/libc/stdlib/malloc-930716/README deleted file mode 100644 index 39c048312..000000000 --- a/libc/stdlib/malloc-930716/README +++ /dev/null @@ -1,40 +0,0 @@ -This is a fast malloc implementation that I wrote several years ago. -I later used it as the basis of GNU malloc. My version differs from -the GNU version in that it does not support debugging hooks, and does -not record statistics. Therefore it is slightly faster. - -In order to safely link programs using this malloc with a C library -that provides a different malloc, you need to make sure that -malloc(), free(), and realloc() are defined in a single object file. -Otherwise when linking you might get a combination of this malloc() -with the library's free(). The Makefile builds such an object file, -alloc.o. - -If you are using this malloc as the allocator for a C library of your -own, and are not linking with another C library, then you don't need -alloc.o. If you are building a C library, you should also write a -replacement for the file "morecore.c" that doesn't pollute the name -space. - -The header file "malloc.h" in this directory is NOT intended to be a -public header file; it is for internal use by malloc and its -friends. Don't install malloc.h in a public include directory! - -When porting this allocator to a new machine or operating system, you -should inspect the definition of BLOCKSIZE in malloc.h to make sure -it is greater than or equal to your target machine's virtual memory -page size; otherwise valloc() won't work properly. (If you don't -care about valloc() then BLOCKSIZE doesn't matter.) - -You will also need to provide a machine-dependent _default_morecore() -function; see morecore.c for a sample version that works on Unix. -Your morecore function should return a pointer to a newly allocated -region of the given size, aligned on the most pessimistic alignment -boundary for the machine. Subsequent calls to morecore should return -contiguous memory, and calls to morecore with a negative argument -should return memory to the system. If no memory is available -morecore should return NULL. - -Bug reports to Mike Haertel, mike@cs.uoregon.edu. -This version is dated March 26, 1993; include this -date with your bug report. diff --git a/libc/stdlib/malloc-930716/malloc.c b/libc/stdlib/malloc-930716/malloc.c deleted file mode 100644 index 14047cb02..000000000 --- a/libc/stdlib/malloc-930716/malloc.c +++ /dev/null @@ -1,445 +0,0 @@ -/* malloc.c - C standard library routine. - Copyright (c) 1989, 1993 Michael J. Haertel - You may redistribute this library under the terms of the - GNU Library General Public License (version 2 or any later - version) as published by the Free Software Foundation. - THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY EXPRESS OR IMPLIED - WARRANTY. IN PARTICULAR, THE AUTHOR MAKES NO REPRESENTATION OR - WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS - SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. */ - -#define _GNU_SOURCE -#include -#include -#include -#include -#include -#include -#include -#include "malloc.h" - -#ifdef __UCLIBC_HAS_THREADS__ -#include -pthread_mutex_t __malloclock = PTHREAD_MUTEX_INITIALIZER; -# define LOCK __pthread_mutex_lock(&__malloclock) -# define UNLOCK __pthread_mutex_unlock(&__malloclock); -#else -# define LOCK -# define UNLOCK -#endif - - -/* Stuff that is shared across .o files */ - -/* Pointer to the base of the first block. */ -char *_heapbase; -/* Block information table. */ -union info *_heapinfo; -/* Search index in the info table. */ -size_t _heapindex; -/* Limit of valid info table indices. */ -size_t _heaplimit; -/* List of blocks allocated with memalign or valloc */ -struct alignlist *_aligned_blocks; - - - -/* Stuff that is local to this .o file only */ - -/* How to really get more memory. */ -static void * __morecore(long size); -/* Number of info entries. */ -static size_t heapsize; -/* Count of large blocks allocated for each fragment size. */ -static size_t _fragblocks[BLOCKLOG]; -/* Free lists for each fragment size. */ -static struct list _fraghead[BLOCKLOG]; -/* Are we experienced? */ -static int initialized; - - -/* Aligned allocation. - * Called within the lock in initialize() and morecore(), - * so no explicit locking needed... */ -static void * align(size_t size) -{ - void *result; - unsigned int adj; - - result = __morecore(size); - adj = (unsigned int) ((char *) result - (char *) NULL) % BLOCKSIZE; - if (adj != 0) { - __morecore(adj = BLOCKSIZE - adj); - result = (char *) result + adj; - } - return result; -} - -/* Set everything up and remember that we have. - * Called within the lock in malloc(), so no - * explicit locking needed... */ -static int initialize(void) -{ - heapsize = HEAP / BLOCKSIZE; - _heapinfo = align(heapsize * sizeof (union info)); - if (!_heapinfo) { - return 0; - } - memset(_heapinfo, 0, heapsize * sizeof (union info)); - _heapinfo[0].free.size = 0; - _heapinfo[0].free.next = _heapinfo[0].free.prev = 0; - _heapindex = 0; - _heapbase = (char *) _heapinfo; - initialized = 1; - return 1; -} - -/* Get neatly aligned memory, initializing or growing the - * heap info table as necessary. - * Called within a lock in malloc() and free(), - * so no explicit locking needed... */ -static void * morecore(size_t size) -{ - void *result; - union info *newinfo, *oldinfo; - size_t newsize; - - result = align(size); - if (!result) - return NULL; - - /* Check if we need to grow the info table. */ - if (BLOCK((char *) result + size) > heapsize) { - newsize = heapsize; - while (BLOCK((char *) result + size) > newsize) - newsize *= 2; - newinfo = align(newsize * sizeof (union info)); - if (!newinfo) { - __morecore(-size); - return NULL; - } - memset(newinfo, 0, newsize * sizeof (union info)); - memcpy(newinfo, _heapinfo, heapsize * sizeof (union info)); - oldinfo = _heapinfo; - newinfo[BLOCK(oldinfo)].busy.type = 0; - newinfo[BLOCK(oldinfo)].busy.info.size - = BLOCKIFY(heapsize * sizeof (union info)); - _heapinfo = newinfo; - __free_unlocked(oldinfo); - heapsize = newsize; - } - - _heaplimit = BLOCK((char *) result + size); - return result; -} - -/* Note that morecore has to take a signed argument so - that negative values can return memory to the system. */ -static void * __morecore(long size) -{ - void *result; - - result = sbrk(size); - if (result == (void *) -1) - return NULL; - return result; -} - -/* Allocate memory from the heap. */ -void * malloc (size_t size) -{ - void * ptr; - LOCK; - ptr = __malloc_unlocked(size); - UNLOCK; - return(ptr); -} - -void * __malloc_unlocked (size_t size) -{ - void *result; - size_t log, block, blocks, i, lastblocks, start; - struct list *next; - -#if defined(__MALLOC_GLIBC_COMPAT__) - if (unlikely(size == 0)) - size++; -#else - /* Some programs will call malloc (0). Lets be strict and return NULL */ - if (unlikely(size == 0)) - return 0; -#endif - /* Check if they are doing something dumb like malloc(-1) */ - if (unlikely(((unsigned long)size > (unsigned long)(sizeof (struct list)*-2)))) - goto oom; - - if (unlikely(size < sizeof (struct list))) - size = sizeof (struct list); - - if (!initialized && !initialize()) { - goto oom; - } - - /* Determine the allocation policy based on the request size. */ - if (size <= BLOCKSIZE / 2) { - /* Small allocation to receive a fragment of a block. Determine - the logarithm to base two of the fragment size. */ - --size; - for (log = 1; (size >>= 1) != 0; ++log) - ; - - /* Look in the fragment lists for a free fragment of the - desired size. */ - if ((next = _fraghead[log].next) != 0) { - /* There are free fragments of this size. Pop a fragment - out of the fragment list and return it. Update the block's - nfree and first counters. */ - result = next; - next->prev->next = next->next; - if (next->next) - next->next->prev = next->prev; - block = BLOCK(result); - if (--_heapinfo[block].busy.info.frag.nfree) - _heapinfo[block].busy.info.frag.first - = (unsigned int) ((char *) next->next - (char *) NULL) - % BLOCKSIZE >> log; - } else { - /* No free fragments of the desired size, so get a new block - and break it into fragments, returning the first. */ - result = __malloc_unlocked(BLOCKSIZE); - if (!result) { - goto oom; - } - ++_fragblocks[log]; - - /* Link all fragments but the first into the free list. */ - next = (struct list *) ((char *) result + (1 << log)); - next->next = 0; - next->prev = &_fraghead[log]; - _fraghead[log].next = next; - - for (i = 2; i < BLOCKSIZE >> log; ++i) { - next = (struct list *) ((char *) result + (i << log)); - next->next = _fraghead[log].next; - next->prev = &_fraghead[log]; - next->prev->next = next; - next->next->prev = next; - } - - /* Initialize the nfree and first counters for this block. */ - block = BLOCK(result); - _heapinfo[block].busy.type = log; - _heapinfo[block].busy.info.frag.nfree = i - 1; - _heapinfo[block].busy.info.frag.first = i - 1; - } - } else { - /* Large allocation to receive one or more blocks. Search - the free list in a circle starting at the last place visited. - If we loop completely around without finding a large enough - space we will have to get more memory from the system. */ - blocks = BLOCKIFY(size); - start = block = _heapindex; - while (_heapinfo[block].free.size < blocks) { - block = _heapinfo[block].free.next; - if (block == start) { - /* Need to get more from the system. Check to see if - the new core will be contiguous with the final free - block; if so we don't need to get as much. */ - block = _heapinfo[0].free.prev; - lastblocks = _heapinfo[block].free.size; - if (_heaplimit && block + lastblocks == _heaplimit - && __morecore(0) == ADDRESS(block + lastblocks) - && morecore((blocks - lastblocks) * BLOCKSIZE)) { - /* Note that morecore() can change the location of - the final block if it moves the info table and the - old one gets coalesced into the final block. */ - block = _heapinfo[0].free.prev; - _heapinfo[block].free.size += blocks - lastblocks; - continue; - } - result = morecore(blocks * BLOCKSIZE); - if (!result) { - goto oom; - } - block = BLOCK(result); - _heapinfo[block].busy.type = 0; - _heapinfo[block].busy.info.size = blocks; - return result; - } - } - - /* At this point we have found a suitable free list entry. - Figure out how to remove what we need from the list. */ - result = ADDRESS(block); - if (_heapinfo[block].free.size > blocks) { - /* The block we found has a bit left over, so relink the - tail end back into the free list. */ - _heapinfo[block + blocks].free.size - = _heapinfo[block].free.size - blocks; - _heapinfo[block + blocks].free.next - = _heapinfo[block].free.next; - _heapinfo[block + blocks].free.prev - = _heapinfo[block].free.prev; - _heapinfo[_heapinfo[block].free.prev].free.next - = _heapinfo[_heapinfo[block].free.next].free.prev - = _heapindex = block + blocks; - } else { - /* The block exactly matches our requirements, so - just remove it from the list. */ - _heapinfo[_heapinfo[block].free.next].free.prev - = _heapinfo[block].free.prev; - _heapinfo[_heapinfo[block].free.prev].free.next - = _heapindex = _heapinfo[block].free.next; - } - - _heapinfo[block].busy.type = 0; - _heapinfo[block].busy.info.size = blocks; - } - - return result; - -oom: - __set_errno(ENOMEM); - return NULL; -} - -/* Return memory to the heap. */ -void free(void *ptr) -{ - struct alignlist *l; - - if (ptr == NULL) - return; - - LOCK; - for (l = _aligned_blocks; l != NULL; l = l->next) { - if (l->aligned == ptr) { - /* Mark the block as free */ - l->aligned = NULL; - ptr = l->exact; - break; - } - } - - __free_unlocked(ptr); - UNLOCK; -} - -void __free_unlocked(void *ptr) -{ - int block, blocks, i, type; - struct list *prev, *next; - - if (ptr == NULL) - return; - - - block = BLOCK(ptr); - - switch (type = _heapinfo[block].busy.type) { - case 0: - /* Find the free cluster previous to this one in the free list. - Start searching at the last block referenced; this may benefit - programs with locality of allocation. */ - i = _heapindex; - if (i > block) - while (i > block) - i = _heapinfo[i].free.prev; - else { - do - i = _heapinfo[i].free.next; - while (i > 0 && i < block); - i = _heapinfo[i].free.prev; - } - - /* Determine how to link this block into the free list. */ - if (block == i + _heapinfo[i].free.size) { - /* Coalesce this block with its predecessor. */ - _heapinfo[i].free.size += _heapinfo[block].busy.info.size; - block = i; - } else { - /* Really link this block back into the free list. */ - _heapinfo[block].free.size = _heapinfo[block].busy.info.size; - _heapinfo[block].free.next = _heapinfo[i].free.next; - _heapinfo[block].free.prev = i; - _heapinfo[i].free.next = block; - _heapinfo[_heapinfo[block].free.next].free.prev = block; - } - - /* Now that the block is linked in, see if we can coalesce it - with its successor (by deleting its successor from the list - and adding in its size). */ - if (block + _heapinfo[block].free.size == _heapinfo[block].free.next) { - _heapinfo[block].free.size - += _heapinfo[_heapinfo[block].free.next].free.size; - _heapinfo[block].free.next - = _heapinfo[_heapinfo[block].free.next].free.next; - _heapinfo[_heapinfo[block].free.next].free.prev = block; - } - - /* Now see if we can return stuff to the system. */ - blocks = _heapinfo[block].free.size; - if (blocks >= FINAL_FREE_BLOCKS && block + blocks == _heaplimit - && __morecore(0) == ADDRESS(block + blocks)) { - _heaplimit -= blocks; - __morecore(-blocks * BLOCKSIZE); - _heapinfo[_heapinfo[block].free.prev].free.next - = _heapinfo[block].free.next; - _heapinfo[_heapinfo[block].free.next].free.prev - = _heapinfo[block].free.prev; - block = _heapinfo[block].free.prev; - } - - /* Set the next search to begin at this block. */ - _heapindex = block; - break; - - default: - /* Get the address of the first free fragment in this block. */ - prev = (struct list *) ((char *) ADDRESS(block) - + (_heapinfo[block].busy.info.frag.first - << type)); - - if (_heapinfo[block].busy.info.frag.nfree == (BLOCKSIZE >> type) - 1 - && _fragblocks[type] > 1) { - /* If all fragments of this block are free, remove them - from the fragment list and free the whole block. */ - --_fragblocks[type]; - for (next = prev, i = 1; i < BLOCKSIZE >> type; ++i) - next = next->next; - prev->prev->next = next; - if (next) - next->prev = prev->prev; - _heapinfo[block].busy.type = 0; - _heapinfo[block].busy.info.size = 1; - __free_unlocked(ADDRESS(block)); - } else if (_heapinfo[block].busy.info.frag.nfree) { - /* If some fragments of this block are free, link this fragment - into the fragment list after the first free fragment of - this block. */ - next = ptr; - next->next = prev->next; - next->prev = prev; - prev->next = next; - if (next->next) - next->next->prev = next; - ++_heapinfo[block].busy.info.frag.nfree; - } else { - /* No fragments of this block are free, so link this fragment - into the fragment list and announce that it is the first - free fragment of this block. */ - prev = (struct list *) ptr; - _heapinfo[block].busy.info.frag.nfree = 1; - _heapinfo[block].busy.info.frag.first - = (unsigned int) ((char *) ptr - (char *) NULL) % BLOCKSIZE - >> type; - prev->next = _fraghead[type].next; - prev->prev = &_fraghead[type]; - prev->prev->next = prev; - if (prev->next) - prev->next->prev = prev; - } - break; - } -} - diff --git a/libc/stdlib/malloc-930716/malloc.h b/libc/stdlib/malloc-930716/malloc.h deleted file mode 100644 index bd315f788..000000000 --- a/libc/stdlib/malloc-930716/malloc.h +++ /dev/null @@ -1,89 +0,0 @@ -/* malloc.h - declarations for the allocator. - Copyright (c) 1989, 1993 Michael J. Haertel - You may redistribute this library under the terms of the - GNU Library General Public License (version 2 or any later - version) as published by the Free Software Foundation. - THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY EXPRESS OR IMPLIED - WARRANTY. IN PARTICULAR, THE AUTHOR MAKES NO REPRESENTATION OR - WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS - SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. */ - -#include - - -#define MIN(x,y) ({ \ - const typeof(x) _x = (x); \ - const typeof(y) _y = (y); \ - (void) (&_x == &_y); \ - _x < _y ? _x : _y; }) - - - -/* The allocator divides the heap into blocks of fixed size; large - requests receive one or more whole blocks, and small requests - receive a fragment of a block. Fragment sizes are powers of two, - and all fragments of a block are the same size. When all the - fragments in a block have been freed, the block itself is freed. - */ -#define INT_BIT (CHAR_BIT * sizeof (size_t)) -#define BLOCKLOG (INT_BIT > 16 ? 12 : 9) -#define BLOCKSIZE (1 << BLOCKLOG) -#define BLOCKIFY(SIZE) (((SIZE) + BLOCKSIZE - 1) / BLOCKSIZE) - -/* Determine the amount of memory spanned by the initial heap table - (not an absolute limit). */ -#define HEAP (INT_BIT > 16 ? 4194304 : 65536) - -/* Number of contiguous free blocks allowed to build up at the end of - memory before they will be returned to the system. */ -#define FINAL_FREE_BLOCKS 8 - -/* Data structure giving per-block information. */ -union info { - struct { - size_t type; /* Zero for a large block, or positive - giving the logarithm to the base two - of the fragment size. */ - union { - struct { - size_t nfree; /* Free fragments in a fragmented block. */ - size_t first; /* First free fragment of the block. */ - } frag; - size_t size; /* Size (in blocks) of a large cluster. */ - } info; - } busy; - struct { - size_t size; /* Size (in blocks) of a free cluster. */ - size_t next; /* Index of next free cluster. */ - size_t prev; /* Index of previous free cluster. */ - } free; -}; - -/* Address to block number and vice versa. */ -#define BLOCK(A) (((char *) (A) - _heapbase) / BLOCKSIZE + 1) -#define ADDRESS(B) ((void *) (((B) - 1) * BLOCKSIZE + _heapbase)) - -/* Doubly linked lists of free fragments. */ -struct list { - struct list *next; - struct list *prev; -}; - -/* List of blocks allocated with memalign or valloc */ -struct alignlist -{ - struct alignlist *next; - __ptr_t aligned; /* The address that memaligned returned. */ - __ptr_t exact; /* The address that malloc returned. */ -}; -extern struct alignlist *_aligned_blocks; -extern char *_heapbase; -extern union info *_heapinfo; -extern size_t _heapindex; -extern size_t _heaplimit; - - -extern void *__malloc_unlocked (size_t size); -extern void __free_unlocked(void *ptr); - - diff --git a/libc/stdlib/malloc-930716/memalign.c b/libc/stdlib/malloc-930716/memalign.c deleted file mode 100644 index b89165452..000000000 --- a/libc/stdlib/malloc-930716/memalign.c +++ /dev/null @@ -1,67 +0,0 @@ -/* malloc.c - C standard library routine. - Copyright (c) 1989, 1993 Michael J. Haertel - You may redistribute this library under the terms of the - GNU Library General Public License (version 2 or any later - version) as published by the Free Software Foundation. - THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY EXPRESS OR IMPLIED - WARRANTY. IN PARTICULAR, THE AUTHOR MAKES NO REPRESENTATION OR - WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS - SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. */ - -#define _GNU_SOURCE -#include -#include -#include -#include -#include -#include -#include "malloc.h" - -#ifdef __UCLIBC_HAS_THREADS__ -#include -extern pthread_mutex_t __malloclock; -# define LOCK __pthread_mutex_lock(&__malloclock) -# define UNLOCK __pthread_mutex_unlock(&__malloclock); -#else -# define LOCK -# define UNLOCK -#endif - - -__ptr_t memalign (size_t alignment, size_t size) -{ - __ptr_t result; - unsigned long int adj; - - result = malloc (size + alignment - 1); - if (result == NULL) - return NULL; - adj = (unsigned long int) ((unsigned long int) ((char *) result - - (char *) NULL)) % alignment; - if (adj != 0) - { - struct alignlist *l; - LOCK; - for (l = _aligned_blocks; l != NULL; l = l->next) - if (l->aligned == NULL) - /* This slot is free. Use it. */ - break; - if (l == NULL) - { - l = (struct alignlist *) malloc (sizeof (struct alignlist)); - if (l == NULL) { - __free_unlocked (result); - UNLOCK; - return NULL; - } - l->next = _aligned_blocks; - _aligned_blocks = l; - } - l->exact = result; - result = l->aligned = (char *) result + alignment - adj; - UNLOCK; - } - - return result; -} - diff --git a/libc/stdlib/malloc-930716/realloc.c b/libc/stdlib/malloc-930716/realloc.c deleted file mode 100644 index 397534a5a..000000000 --- a/libc/stdlib/malloc-930716/realloc.c +++ /dev/null @@ -1,142 +0,0 @@ -/* malloc.c - C standard library routine. - Copyright (c) 1989, 1993 Michael J. Haertel - You may redistribute this library under the terms of the - GNU Library General Public License (version 2 or any later - version) as published by the Free Software Foundation. - THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY EXPRESS OR IMPLIED - WARRANTY. IN PARTICULAR, THE AUTHOR MAKES NO REPRESENTATION OR - WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS - SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. */ - -#define _GNU_SOURCE -#include -#include -#include -#include -#include -#include -#include -#include "malloc.h" - -#ifdef __UCLIBC_HAS_THREADS__ -#include -extern pthread_mutex_t __malloclock; -# define LOCK __pthread_mutex_lock(&__malloclock) -# define UNLOCK __pthread_mutex_unlock(&__malloclock); -#else -# define LOCK -# define UNLOCK -#endif - -/* Resize the given region to the new size, returning a pointer - to the (possibly moved) region. This is optimized for speed; - some benchmarks seem to indicate that greater compactness is - achieved by unconditionally allocating and copying to a - new region. */ -void * realloc (void *ptr, size_t size) -{ - void *result, *previous; - size_t block, blocks, type; - size_t oldlimit; - - if (!ptr) - return malloc(size); - if (!size) { - LOCK; - __free_unlocked(ptr); - result = __malloc_unlocked(0); - goto alldone; - } - - LOCK; - block = BLOCK(ptr); - - switch (type = _heapinfo[block].busy.type) { - case 0: - /* Maybe reallocate a large block to a small fragment. */ - if (size <= BLOCKSIZE / 2) { - if ((result = __malloc_unlocked(size)) != NULL) { - memcpy(result, ptr, size); - __free_unlocked(ptr); - } - goto alldone; - } - - /* The new size is a large allocation as well; see if - we can hold it in place. */ - blocks = BLOCKIFY(size); - if (blocks < _heapinfo[block].busy.info.size) { - /* The new size is smaller; return excess memory - to the free list. */ - _heapinfo[block + blocks].busy.type = 0; - _heapinfo[block + blocks].busy.info.size - = _heapinfo[block].busy.info.size - blocks; - _heapinfo[block].busy.info.size = blocks; - __free_unlocked(ADDRESS(block + blocks)); - result = ptr; - goto alldone; - } else if (blocks == _heapinfo[block].busy.info.size) { - /* No size change necessary. */ - result = ptr; - goto alldone; - } else { - /* Won't fit, so allocate a new region that will. Free - the old region first in case there is sufficient adjacent - free space to grow without moving. */ - blocks = _heapinfo[block].busy.info.size; - /* Prevent free from actually returning memory to the system. */ - oldlimit = _heaplimit; - _heaplimit = 0; - __free_unlocked(ptr); - _heaplimit = oldlimit; - result = __malloc_unlocked(size); - if (!result) { - /* Now we're really in trouble. We have to unfree - the thing we just freed. Unfortunately it might - have been coalesced with its neighbors. */ - if (_heapindex == block) - __malloc_unlocked(blocks * BLOCKSIZE); - else { - previous = __malloc_unlocked((block - _heapindex) * BLOCKSIZE); - __malloc_unlocked(blocks * BLOCKSIZE); - __free_unlocked(previous); - } - goto oom; - } - if (ptr != result) - memmove(result, ptr, blocks * BLOCKSIZE); - goto alldone; - } - break; - - default: - /* Old size is a fragment; type is logarithm to base two of - the fragment size. */ - if ((size > 1 << (type - 1)) && (size <= 1 << type)) { - /* New size is the same kind of fragment. */ - result = ptr; - goto alldone; - } - else { - /* New size is different; allocate a new space, and copy - the lesser of the new size and the old. */ - result = __malloc_unlocked(size); - if (!result) { - goto oom; - } - memcpy(result, ptr, MIN(size, (size_t)(1 << type))); - __free_unlocked(ptr); - goto alldone; - } - break; - } -alldone: - UNLOCK; - return result; - -oom: - UNLOCK; - __set_errno(ENOMEM); - return NULL; -} - diff --git a/libc/stdlib/malloc-simple/alloc.c b/libc/stdlib/malloc-simple/alloc.c index ee0135581..fcac02927 100644 --- a/libc/stdlib/malloc-simple/alloc.c +++ b/libc/stdlib/malloc-simple/alloc.c @@ -31,14 +31,14 @@ void *malloc(size_t size) #ifdef __UCLIBC_HAS_MMU__ result = mmap((void *) 0, size + sizeof(size_t), PROT_READ | PROT_WRITE, - MAP_PRIVATE | MAP_ANONYMOUS, 0, 0); + MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); if (result == MAP_FAILED) return 0; * (size_t *) result = size; return(result + sizeof(size_t)); #else result = mmap((void *) 0, size, PROT_READ | PROT_WRITE, - MAP_SHARED | MAP_ANONYMOUS, 0, 0); + MAP_SHARED | MAP_ANONYMOUS, -1, 0); if (result == MAP_FAILED) return 0; return(result); @@ -47,12 +47,27 @@ void *malloc(size_t size) #endif #ifdef L_calloc -void *calloc(size_t num, size_t size) +void * calloc(size_t nmemb, size_t lsize) { - void *ptr = malloc(num * size); - if (ptr) - memset(ptr, 0, num * size); - return ptr; + void *result; + size_t size=lsize * nmemb; + + /* guard vs integer overflow, but allow nmemb + * to fall through and call malloc(0) */ + if (nmemb && lsize != (size / nmemb)) { + __set_errno(ENOMEM); + return NULL; + } + result=malloc(size); +#if 0 + /* Standard unix mmap using /dev/zero clears memory so calloc + * doesn't need to actually zero anything.... + */ + if (result != NULL) { + memset(result, 0, size); + } +#endif + return result; } #endif diff --git a/libc/stdlib/malloc-standard/Makefile b/libc/stdlib/malloc-standard/Makefile new file mode 100644 index 000000000..2b87c5de2 --- /dev/null +++ b/libc/stdlib/malloc-standard/Makefile @@ -0,0 +1,51 @@ +# 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 + +# Turn on malloc debugging if requested +ifeq ($(UCLIBC_MALLOC_DEBUGGING),y) +CFLAGS += -D__MALLOC_DEBUGGING +endif + +# calloc.c can be found at uClibc/libc/stdlib/calloc.c +# valloc.c can be found at uClibc/libc/stdlib/valloc.c +CSRC=malloc.c calloc.c realloc.c free.c memalign.c mallopt.c mallinfo.c +COBJS=$(patsubst %.c,%.o, $(CSRC)) +OBJS=$(COBJS) + +all: $(OBJS) $(LIBC) + +$(LIBC): ar-target + +ar-target: $(OBJS) + $(AR) $(ARFLAGS) $(LIBC) $(OBJS) + +$(COBJS): %.o : %.c + $(CC) $(CFLAGS) -c $< -o $@ + $(STRIPTOOL) -x -R .note -R .comment $*.o + +clean: + $(RM) *.[oa] *~ core + diff --git a/libc/stdlib/malloc-standard/calloc.c b/libc/stdlib/malloc-standard/calloc.c new file mode 100644 index 000000000..cff0adab8 --- /dev/null +++ b/libc/stdlib/malloc-standard/calloc.c @@ -0,0 +1,93 @@ +/* + This is a version (aka dlmalloc) of malloc/free/realloc written by + Doug Lea and released to the public domain. Use, modify, and + redistribute this code without permission or acknowledgement in any + way you wish. Send questions, comments, complaints, performance + data, etc to dl@cs.oswego.edu + + VERSION 2.7.2 Sat Aug 17 09:07:30 2002 Doug Lea (dl at gee) + + Note: There may be an updated version of this malloc obtainable at + ftp://gee.cs.oswego.edu/pub/misc/malloc.c + Check before installing! + + Hacked up for uClibc by Erik Andersen +*/ + +#include "malloc.h" + + +/* ------------------------------ calloc ------------------------------ */ +void* calloc(size_t n_elements, size_t elem_size) +{ + mchunkptr p; + unsigned long clearsize; + unsigned long nclears; + size_t size, *d; + void* mem; + + + /* guard vs integer overflow, but allow nmemb + * to fall through and call malloc(0) */ + size=lsize * nmemb; + if (n_elements && elem_size != (size / n_elements)) { + __set_errno(ENOMEM); + return NULL; + } + + LOCK; + mem = malloc(size); + if (mem != 0) { + p = mem2chunk(mem); + + if (!chunk_is_mmapped(p)) + { + /* + Unroll clear of <= 36 bytes (72 if 8byte sizes) + We know that contents have an odd number of + size_t-sized words; minimally 3. + */ + + d = (size_t*)mem; + clearsize = chunksize(p) - (sizeof(size_t)); + nclears = clearsize / sizeof(size_t); + assert(nclears >= 3); + + if (nclears > 9) + memset(d, 0, clearsize); + + else { + *(d+0) = 0; + *(d+1) = 0; + *(d+2) = 0; + if (nclears > 4) { + *(d+3) = 0; + *(d+4) = 0; + if (nclears > 6) { + *(d+5) = 0; + *(d+6) = 0; + if (nclears > 8) { + *(d+7) = 0; + *(d+8) = 0; + } + } + } + } + } +#if 0 + else + { + /* Standard unix mmap using /dev/zero clears memory so calloc + * doesn't need to actually zero anything.... + */ + d = (size_t*)mem; + /* Note the additional (sizeof(size_t)) */ + clearsize = chunksize(p) - 2*(sizeof(size_t)); + memset(d, 0, clearsize); + } +#endif + } + UNLOCK; + return mem; +} + diff --git a/libc/stdlib/malloc-standard/free.c b/libc/stdlib/malloc-standard/free.c new file mode 100644 index 000000000..4277767fa --- /dev/null +++ b/libc/stdlib/malloc-standard/free.c @@ -0,0 +1,382 @@ +/* + This is a version (aka dlmalloc) of malloc/free/realloc written by + Doug Lea and released to the public domain. Use, modify, and + redistribute this code without permission or acknowledgement in any + way you wish. Send questions, comments, complaints, performance + data, etc to dl@cs.oswego.edu + + VERSION 2.7.2 Sat Aug 17 09:07:30 2002 Doug Lea (dl at gee) + + Note: There may be an updated version of this malloc obtainable at + ftp://gee.cs.oswego.edu/pub/misc/malloc.c + Check before installing! + + Hacked up for uClibc by Erik Andersen +*/ + +#include "malloc.h" + + +/* ------------------------- __malloc_trim ------------------------- + __malloc_trim is an inverse of sorts to __malloc_alloc. It gives memory + back to the system (via negative arguments to sbrk) if there is unused + memory at the `high' end of the malloc pool. It is called automatically by + free() when top space exceeds the trim threshold. It is also called by the + public malloc_trim routine. It returns 1 if it actually released any + memory, else 0. +*/ +static int __malloc_trim(size_t pad, mstate av) +{ + long top_size; /* Amount of top-most memory */ + long extra; /* Amount to release */ + long released; /* Amount actually released */ + char* current_brk; /* address returned by pre-check sbrk call */ + char* new_brk; /* address returned by post-check sbrk call */ + size_t pagesz; + + pagesz = av->pagesize; + top_size = chunksize(av->top); + + /* Release in pagesize units, keeping at least one page */ + extra = ((top_size - pad - MINSIZE + (pagesz-1)) / pagesz - 1) * pagesz; + + if (extra > 0) { + + /* + Only proceed if end of memory is where we last set it. + This avoids problems if there were foreign sbrk calls. + */ + current_brk = (char*)(MORECORE(0)); + if (current_brk == (char*)(av->top) + top_size) { + + /* + Attempt to release memory. We ignore MORECORE return value, + and instead call again to find out where new end of memory is. + This avoids problems if first call releases less than we asked, + of if failure somehow altered brk value. (We could still + encounter problems if it altered brk in some very bad way, + but the only thing we can do is adjust anyway, which will cause + some downstream failure.) + */ + + MORECORE(-extra); + new_brk = (char*)(MORECORE(0)); + + if (new_brk != (char*)MORECORE_FAILURE) { + released = (long)(current_brk - new_brk); + + if (released != 0) { + /* Success. Adjust top. */ + av->sbrked_mem -= released; + set_head(av->top, (top_size - released) | PREV_INUSE); + check_malloc_state(); + return 1; + } + } + } + } + return 0; +} + +/* + Initialize a malloc_state struct. + + This is called only from within __malloc_consolidate, which needs + be called in the same contexts anyway. It is never called directly + outside of __malloc_consolidate because some optimizing compilers try + to inline it at all call points, which turns out not to be an + optimization at all. (Inlining it in __malloc_consolidate is fine though.) +*/ +static void malloc_init_state(mstate av) +{ + int i; + mbinptr bin; + + /* Establish circular links for normal bins */ + for (i = 1; i < NBINS; ++i) { + bin = bin_at(av,i); + bin->fd = bin->bk = bin; + } + + av->top_pad = DEFAULT_TOP_PAD; + av->n_mmaps_max = DEFAULT_MMAP_MAX; + av->mmap_threshold = DEFAULT_MMAP_THRESHOLD; + av->trim_threshold = DEFAULT_TRIM_THRESHOLD; + +#if MORECORE_CONTIGUOUS + set_contiguous(av); +#else + set_noncontiguous(av); +#endif + + + set_max_fast(av, DEFAULT_MXFAST); + + av->top = initial_top(av); + av->pagesize = malloc_getpagesize; +} + + +/* ---------------------------------------------------------------------- + * + * PUBLIC STUFF + * + * ----------------------------------------------------------------------*/ + + +/* ------------------------- __malloc_consolidate ------------------------- + + __malloc_consolidate is a specialized version of free() that tears + down chunks held in fastbins. Free itself cannot be used for this + purpose since, among other things, it might place chunks back onto + fastbins. So, instead, we need to use a minor variant of the same + code. + + Also, because this routine needs to be called the first time through + malloc anyway, it turns out to be the perfect place to trigger + initialization code. +*/ +void __malloc_consolidate(mstate av) +{ + mfastbinptr* fb; /* current fastbin being consolidated */ + mfastbinptr* maxfb; /* last fastbin (for loop control) */ + mchunkptr p; /* current chunk being consolidated */ + mchunkptr nextp; /* next chunk to consolidate */ + mchunkptr unsorted_bin; /* bin header */ + mchunkptr first_unsorted; /* chunk to link to */ + + /* These have same use as in free() */ + mchunkptr nextchunk; + size_t size; + size_t nextsize; + size_t prevsize; + int nextinuse; + mchunkptr bck; + mchunkptr fwd; + + /* + If max_fast is 0, we know that av hasn't + yet been initialized, in which case do so below + */ + + if (av->max_fast != 0) { + clear_fastchunks(av); + + unsorted_bin = unsorted_chunks(av); + + /* + Remove each chunk from fast bin and consolidate it, placing it + then in unsorted bin. Among other reasons for doing this, + placing in unsorted bin avoids needing to calculate actual bins + until malloc is sure that chunks aren't immediately going to be + reused anyway. + */ + + maxfb = &(av->fastbins[fastbin_index(av->max_fast)]); + fb = &(av->fastbins[0]); + do { + if ( (p = *fb) != 0) { + *fb = 0; + + do { + check_inuse_chunk(p); + nextp = p->fd; + + /* Slightly streamlined version of consolidation code in free() */ + size = p->size & ~PREV_INUSE; + nextchunk = chunk_at_offset(p, size); + nextsize = chunksize(nextchunk); + + if (!prev_inuse(p)) { + prevsize = p->prev_size; + size += prevsize; + p = chunk_at_offset(p, -((long) prevsize)); + unlink(p, bck, fwd); + } + + if (nextchunk != av->top) { + nextinuse = inuse_bit_at_offset(nextchunk, nextsize); + set_head(nextchunk, nextsize); + + if (!nextinuse) { + size += nextsize; + unlink(nextchunk, bck, fwd); + } + + first_unsorted = unsorted_bin->fd; + unsorted_bin->fd = p; + first_unsorted->bk = p; + + set_head(p, size | PREV_INUSE); + p->bk = unsorted_bin; + p->fd = first_unsorted; + set_foot(p, size); + } + + else { + size += nextsize; + set_head(p, size | PREV_INUSE); + av->top = p; + } + + } while ( (p = nextp) != 0); + + } + } while (fb++ != maxfb); + } + else { + malloc_init_state(av); + check_malloc_state(); + } +} + + +/* ------------------------------ free ------------------------------ */ +void free(void* mem) +{ + mstate av; + + mchunkptr p; /* chunk corresponding to mem */ + size_t size; /* its size */ + mfastbinptr* fb; /* associated fastbin */ + mchunkptr nextchunk; /* next contiguous chunk */ + size_t nextsize; /* its size */ + int nextinuse; /* true if nextchunk is used */ + size_t prevsize; /* size of previous contiguous chunk */ + mchunkptr bck; /* misc temp for linking */ + mchunkptr fwd; /* misc temp for linking */ + + /* free(0) has no effect */ + if (mem == NULL) + return; + + LOCK; + av = get_malloc_state(); + p = mem2chunk(mem); + size = chunksize(p); + + check_inuse_chunk(p); + + /* + If eligible, place chunk on a fastbin so it can be found + and used quickly in malloc. + */ + + if ((unsigned long)(size) <= (unsigned long)(av->max_fast) + +#if TRIM_FASTBINS + /* If TRIM_FASTBINS set, don't place chunks + bordering top into fastbins */ + && (chunk_at_offset(p, size) != av->top) +#endif + ) { + + set_fastchunks(av); + fb = &(av->fastbins[fastbin_index(size)]); + p->fd = *fb; + *fb = p; + } + + /* + Consolidate other non-mmapped chunks as they arrive. + */ + + else if (!chunk_is_mmapped(p)) { + set_anychunks(av); + + nextchunk = chunk_at_offset(p, size); + nextsize = chunksize(nextchunk); + + /* consolidate backward */ + if (!prev_inuse(p)) { + prevsize = p->prev_size; + size += prevsize; + p = chunk_at_offset(p, -((long) prevsize)); + unlink(p, bck, fwd); + } + + if (nextchunk != av->top) { + /* get and clear inuse bit */ + nextinuse = inuse_bit_at_offset(nextchunk, nextsize); + set_head(nextchunk, nextsize); + + /* consolidate forward */ + if (!nextinuse) { + unlink(nextchunk, bck, fwd); + size += nextsize; + } + + /* + Place the chunk in unsorted chunk list. Chunks are + not placed into regular bins until after they have + been given one chance to be used in malloc. + */ + + bck = unsorted_chunks(av); + fwd = bck->fd; + p->bk = bck; + p->fd = fwd; + bck->fd = p; + fwd->bk = p; + + set_head(p, size | PREV_INUSE); + set_foot(p, size); + + check_free_chunk(p); + } + + /* + If the chunk borders the current high end of memory, + consolidate into top + */ + + else { + size += nextsize; + set_head(p, size | PREV_INUSE); + av->top = p; + check_chunk(p); + } + + /* + If freeing a large space, consolidate possibly-surrounding + chunks. Then, if the total unused topmost memory exceeds trim + threshold, ask malloc_trim to reduce top. + + Unless max_fast is 0, we don't know if there are fastbins + bordering top, so we cannot tell for sure whether threshold + has been reached unless fastbins are consolidated. But we + don't want to consolidate on each free. As a compromise, + consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD + is reached. + */ + + if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) { + if (have_fastchunks(av)) + __malloc_consolidate(av); + + if ((unsigned long)(chunksize(av->top)) >= + (unsigned long)(av->trim_threshold)) + __malloc_trim(av->top_pad, av); + } + + } + /* + If the chunk was allocated via mmap, release via munmap() + Note that if HAVE_MMAP is false but chunk_is_mmapped is + true, then user must have overwritten memory. There's nothing + we can do to catch this error unless DEBUG is set, in which case + check_inuse_chunk (above) will have triggered error. + */ + + else { + int ret; + size_t offset = p->prev_size; + av->n_mmaps--; + av->mmapped_mem -= (size + offset); + ret = munmap((char*)p - offset, size + offset); + /* munmap returns non-zero on failure */ + assert(ret == 0); + } + UNLOCK; +} + diff --git a/libc/stdlib/malloc-standard/mallinfo.c b/libc/stdlib/malloc-standard/mallinfo.c new file mode 100644 index 000000000..89d6b68e1 --- /dev/null +++ b/libc/stdlib/malloc-standard/mallinfo.c @@ -0,0 +1,81 @@ +/* + This is a version (aka dlmalloc) of malloc/free/realloc written by + Doug Lea and released to the public domain. Use, modify, and + redistribute this code without permission or acknowledgement in any + way you wish. Send questions, comments, complaints, performance + data, etc to dl@cs.oswego.edu + + VERSION 2.7.2 Sat Aug 17 09:07:30 2002 Doug Lea (dl at gee) + + Note: There may be an updated version of this malloc obtainable at + ftp://gee.cs.oswego.edu/pub/misc/malloc.c + Check before installing! + + Hacked up for uClibc by Erik Andersen +*/ + +#include "malloc.h" + + +/* ------------------------------ mallinfo ------------------------------ */ +struct mallinfo mallinfo(void) +{ + mstate av; + struct mallinfo mi; + int i; + mbinptr b; + mchunkptr p; + size_t avail; + size_t fastavail; + int nblocks; + int nfastblocks; + + LOCK; + av = get_malloc_state(); + /* Ensure initialization */ + if (av->top == 0) { + __malloc_consolidate(av); + } + + check_malloc_state(); + + /* Account for top */ + avail = chunksize(av->top); + nblocks = 1; /* top always exists */ + + /* traverse fastbins */ + nfastblocks = 0; + fastavail = 0; + + for (i = 0; i < NFASTBINS; ++i) { + for (p = av->fastbins[i]; p != 0; p = p->fd) { + ++nfastblocks; + fastavail += chunksize(p); + } + } + + avail += fastavail; + + /* traverse regular bins */ + for (i = 1; i < NBINS; ++i) { + b = bin_at(av, i); + for (p = last(b); p != b; p = p->bk) { + ++nblocks; + avail += chunksize(p); + } + } + + mi.smblks = nfastblocks; + mi.ordblks = nblocks; + mi.fordblks = avail; + mi.uordblks = av->sbrked_mem - avail; + mi.arena = av->sbrked_mem; + mi.hblks = av->n_mmaps; + mi.hblkhd = av->mmapped_mem; + mi.fsmblks = fastavail; + mi.keepcost = chunksize(av->top); + mi.usmblks = av->max_total_mem; + UNLOCK; + return mi; +} + diff --git a/libc/stdlib/malloc-standard/malloc.c b/libc/stdlib/malloc-standard/malloc.c new file mode 100644 index 000000000..8d132a43e --- /dev/null +++ b/libc/stdlib/malloc-standard/malloc.c @@ -0,0 +1,1160 @@ +/* + This is a version (aka dlmalloc) of malloc/free/realloc written by + Doug Lea and released to the public domain. Use, modify, and + redistribute this code without permission or acknowledgement in any + way you wish. Send questions, comments, complaints, performance + data, etc to dl@cs.oswego.edu + + VERSION 2.7.2 Sat Aug 17 09:07:30 2002 Doug Lea (dl at gee) + + Note: There may be an updated version of this malloc obtainable at + ftp://gee.cs.oswego.edu/pub/misc/malloc.c + Check before installing! + + Hacked up for uClibc by Erik Andersen +*/ + +#define _GNU_SOURCE +#include "malloc.h" + + +#ifdef __UCLIBC_HAS_THREADS__ +pthread_mutex_t __malloc_lock = PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP; +#endif + +/* + There is exactly one instance of this struct in this malloc. + If you are adapting this malloc in a way that does NOT use a static + malloc_state, you MUST explicitly zero-fill it before using. This + malloc relies on the property that malloc_state is initialized to + all zeroes (as is true of C statics). +*/ +struct malloc_state __malloc_state; /* never directly referenced */ + +/* forward declaration */ +static int __malloc_largebin_index(unsigned int sz); + +#ifdef __MALLOC_DEBUGGING + +/* + Debugging support + + Because freed chunks may be overwritten with bookkeeping fields, this + malloc will often die when freed memory is overwritten by user + programs. This can be very effective (albeit in an annoying way) + in helping track down dangling pointers. + + If you compile with -D__MALLOC_DEBUGGING, a number of assertion checks are + enabled that will catch more memory errors. You probably won't be + able to make much sense of the actual assertion errors, but they + should help you locate incorrectly overwritten memory. The + checking is fairly extensive, and will slow down execution + noticeably. Calling malloc_stats or mallinfo with __MALLOC_DEBUGGING set will + attempt to check every non-mmapped allocated and free chunk in the + course of computing the summmaries. (By nature, mmapped regions + cannot be checked very much automatically.) + + Setting __MALLOC_DEBUGGING may also be helpful if you are trying to modify + this code. The assertions in the check routines spell out in more + detail the assumptions and invariants underlying the algorithms. + + Setting __MALLOC_DEBUGGING does NOT provide an automated mechanism for checking + that all accesses to malloced memory stay within their + bounds. However, there are several add-ons and adaptations of this + or other mallocs available that do this. +*/ + +/* Properties of all chunks */ +void __do_check_chunk(mchunkptr p) +{ + mstate av = get_malloc_state(); +#ifdef __DOASSERTS__ + /* min and max possible addresses assuming contiguous allocation */ + char* max_address = (char*)(av->top) + chunksize(av->top); + char* min_address = max_address - av->sbrked_mem; + unsigned long sz = chunksize(p); +#endif + + if (!chunk_is_mmapped(p)) { + + /* Has legal address ... */ + if (p != av->top) { + if (contiguous(av)) { + assert(((char*)p) >= min_address); + assert(((char*)p + sz) <= ((char*)(av->top))); + } + } + else { + /* top size is always at least MINSIZE */ + assert((unsigned long)(sz) >= MINSIZE); + /* top predecessor always marked inuse */ + assert(prev_inuse(p)); + } + + } + else { + /* address is outside main heap */ + if (contiguous(av) && av->top != initial_top(av)) { + assert(((char*)p) < min_address || ((char*)p) > max_address); + } + /* chunk is page-aligned */ + assert(((p->prev_size + sz) & (av->pagesize-1)) == 0); + /* mem is aligned */ + assert(aligned_OK(chunk2mem(p))); + } +} + +/* Properties of free chunks */ +void __do_check_free_chunk(mchunkptr p) +{ + size_t sz = p->size & ~PREV_INUSE; +#ifdef __DOASSERTS__ + mstate av = get_malloc_state(); + mchunkptr next = chunk_at_offset(p, sz); +#endif + + __do_check_chunk(p); + + /* Chunk must claim to be free ... */ + assert(!inuse(p)); + assert (!chunk_is_mmapped(p)); + + /* Unless a special marker, must have OK fields */ + if ((unsigned long)(sz) >= MINSIZE) + { + assert((sz & MALLOC_ALIGN_MASK) == 0); + assert(aligned_OK(chunk2mem(p))); + /* ... matching footer field */ + assert(next->prev_size == sz); + /* ... and is fully consolidated */ + assert(prev_inuse(p)); + assert (next == av->top || inuse(next)); + + /* ... and has minimally sane links */ + assert(p->fd->bk == p); + assert(p->bk->fd == p); + } + else /* markers are always of size (sizeof(size_t)) */ + assert(sz == (sizeof(size_t))); +} + +/* Properties of inuse chunks */ +void __do_check_inuse_chunk(mchunkptr p) +{ + mstate av = get_malloc_state(); + mchunkptr next; + __do_check_chunk(p); + + if (chunk_is_mmapped(p)) + return; /* mmapped chunks have no next/prev */ + + /* Check whether it claims to be in use ... */ + assert(inuse(p)); + + next = next_chunk(p); + + /* ... and is surrounded by OK chunks. + Since more things can be checked with free chunks than inuse ones, + if an inuse chunk borders them and debug is on, it's worth doing them. + */ + if (!prev_inuse(p)) { + /* Note that we cannot even look at prev unless it is not inuse */ + mchunkptr prv = prev_chunk(p); + assert(next_chunk(prv) == p); + __do_check_free_chunk(prv); + } + + if (next == av->top) { + assert(prev_inuse(next)); + assert(chunksize(next) >= MINSIZE); + } + else if (!inuse(next)) + __do_check_free_chunk(next); +} + +/* Properties of chunks recycled from fastbins */ +void __do_check_remalloced_chunk(mchunkptr p, size_t s) +{ +#ifdef __DOASSERTS__ + size_t sz = p->size & ~PREV_INUSE; +#endif + + __do_check_inuse_chunk(p); + + /* Legal size ... */ + assert((sz & MALLOC_ALIGN_MASK) == 0); + assert((unsigned long)(sz) >= MINSIZE); + /* ... and alignment */ + assert(aligned_OK(chunk2mem(p))); + /* chunk is less than MINSIZE more than request */ + assert((long)(sz) - (long)(s) >= 0); + assert((long)(sz) - (long)(s + MINSIZE) < 0); +} + +/* Properties of nonrecycled chunks at the point they are malloced */ +void __do_check_malloced_chunk(mchunkptr p, size_t s) +{ + /* same as recycled case ... */ + __do_check_remalloced_chunk(p, s); + + /* + ... plus, must obey implementation invariant that prev_inuse is + always true of any allocated chunk; i.e., that each allocated + chunk borders either a previously allocated and still in-use + chunk, or the base of its memory arena. This is ensured + by making all allocations from the the `lowest' part of any found + chunk. This does not necessarily hold however for chunks + recycled via fastbins. + */ + + assert(prev_inuse(p)); +} + + +/* + Properties of malloc_state. + + This may be useful for debugging malloc, as well as detecting user + programmer errors that somehow write into malloc_state. + + If you are extending or experimenting with this malloc, you can + probably figure out how to hack this routine to print out or + display chunk addresses, sizes, bins, and other instrumentation. +*/ +void __do_check_malloc_state(void) +{ + mstate av = get_malloc_state(); + int i; + mchunkptr p; + mchunkptr q; + mbinptr b; + unsigned int binbit; + int empty; + unsigned int idx; + size_t size; + unsigned long total = 0; + int max_fast_bin; + + /* internal size_t must be no wider than pointer type */ + assert(sizeof(size_t) <= sizeof(char*)); + + /* alignment is a power of 2 */ + assert((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-1)) == 0); + + /* cannot run remaining checks until fully initialized */ + if (av->top == 0 || av->top == initial_top(av)) + return; + + /* pagesize is a power of 2 */ + assert((av->pagesize & (av->pagesize-1)) == 0); + + /* properties of fastbins */ + + /* max_fast is in allowed range */ + assert(get_max_fast(av) <= request2size(MAX_FAST_SIZE)); + + max_fast_bin = fastbin_index(av->max_fast); + + for (i = 0; i < NFASTBINS; ++i) { + p = av->fastbins[i]; + + /* all bins past max_fast are empty */ + if (i > max_fast_bin) + assert(p == 0); + + while (p != 0) { + /* each chunk claims to be inuse */ + __do_check_inuse_chunk(p); + total += chunksize(p); + /* chunk belongs in this bin */ + assert(fastbin_index(chunksize(p)) == i); + p = p->fd; + } + } + + if (total != 0) + assert(have_fastchunks(av)); + else if (!have_fastchunks(av)) + assert(total == 0); + + /* check normal bins */ + for (i = 1; i < NBINS; ++i) { + b = bin_at(av,i); + + /* binmap is accurate (except for bin 1 == unsorted_chunks) */ + if (i >= 2) { + binbit = get_binmap(av,i); + empty = last(b) == b; + if (!binbit) + assert(empty); + else if (!empty) + assert(binbit); + } + + for (p = last(b); p != b; p = p->bk) { + /* each chunk claims to be free */ + __do_check_free_chunk(p); + size = chunksize(p); + total += size; + if (i >= 2) { + /* chunk belongs in bin */ + idx = bin_index(size); + assert(idx == i); + /* lists are sorted */ + if ((unsigned long) size >= (unsigned long)(FIRST_SORTED_BIN_SIZE)) { + assert(p->bk == b || + (unsigned long)chunksize(p->bk) >= + (unsigned long)chunksize(p)); + } + } + /* chunk is followed by a legal chain of inuse chunks */ + for (q = next_chunk(p); + (q != av->top && inuse(q) && + (unsigned long)(chunksize(q)) >= MINSIZE); + q = next_chunk(q)) + __do_check_inuse_chunk(q); + } + } + + /* top chunk is OK */ + __do_check_chunk(av->top); + + /* sanity checks for statistics */ + + assert(total <= (unsigned long)(av->max_total_mem)); + assert(av->n_mmaps >= 0); + assert(av->n_mmaps <= av->max_n_mmaps); + + assert((unsigned long)(av->sbrked_mem) <= + (unsigned long)(av->max_sbrked_mem)); + + assert((unsigned long)(av->mmapped_mem) <= + (unsigned long)(av->max_mmapped_mem)); + + assert((unsigned long)(av->max_total_mem) >= + (unsigned long)(av->mmapped_mem) + (unsigned long)(av->sbrked_mem)); +} +#endif + + +/* ----------- Routines dealing with system allocation -------------- */ + +/* + sysmalloc handles malloc cases requiring more memory from the system. + On entry, it is assumed that av->top does not have enough + space to service request for nb bytes, thus requiring that av->top + be extended or replaced. +*/ +static void* __malloc_alloc(size_t nb, mstate av) +{ + mchunkptr old_top; /* incoming value of av->top */ + size_t old_size; /* its size */ + char* old_end; /* its end address */ + + lon