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 --- 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 ----------- 6 files changed, 829 deletions(-) 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 (limited to 'libc/stdlib/malloc-930716') 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; -} - -- cgit v1.2.3