From ae97a89e1a1a9833080dccc81f6cd26784e1b964 Mon Sep 17 00:00:00 2001 From: Eric Andersen Date: Thu, 11 Jan 2001 11:42:17 +0000 Subject: A large update from Manuel Novoa III . --- libc/stdlib/malloc-930716/Makefile | 51 +++++++ libc/stdlib/malloc-930716/README | 40 ++++++ libc/stdlib/malloc-930716/calloc.c | 25 ++++ libc/stdlib/malloc-930716/free.c | 156 +++++++++++++++++++++ libc/stdlib/malloc-930716/malloc.c | 254 +++++++++++++++++++++++++++++++++++ libc/stdlib/malloc-930716/malloc.h | 107 +++++++++++++++ libc/stdlib/malloc-930716/memalign.c | 61 +++++++++ libc/stdlib/malloc-930716/morecore.c | 28 ++++ libc/stdlib/malloc-930716/realloc.c | 131 ++++++++++++++++++ libc/stdlib/malloc-930716/valloc.c | 62 +++++++++ 10 files changed, 915 insertions(+) create mode 100644 libc/stdlib/malloc-930716/Makefile create mode 100644 libc/stdlib/malloc-930716/README create mode 100644 libc/stdlib/malloc-930716/calloc.c create mode 100644 libc/stdlib/malloc-930716/free.c create mode 100644 libc/stdlib/malloc-930716/malloc.c create mode 100644 libc/stdlib/malloc-930716/malloc.h create mode 100644 libc/stdlib/malloc-930716/memalign.c create mode 100644 libc/stdlib/malloc-930716/morecore.c create mode 100644 libc/stdlib/malloc-930716/realloc.c create mode 100644 libc/stdlib/malloc-930716/valloc.c (limited to 'libc/stdlib/malloc-930716') diff --git a/libc/stdlib/malloc-930716/Makefile b/libc/stdlib/malloc-930716/Makefile new file mode 100644 index 000000000..a4ae21798 --- /dev/null +++ b/libc/stdlib/malloc-930716/Makefile @@ -0,0 +1,51 @@ +# Makefile for uClibc +# +# Copyright (C) 2000 by Lineo, inc. +# +# 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 +LIBC=$(TOPDIR)libc.a + +CSRC=calloc.c free.c malloc.c memalign.c morecore.c realloc.c valloc.c +COBJS=$(patsubst %.c,%.o, $(CSRC)) + +MSRC=../malloc/alloc.c +MOBJ=malloc_dbg.o free_dbg.o calloc_dbg.o +OBJS=$(COBJS) $(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-930716/README b/libc/stdlib/malloc-930716/README new file mode 100644 index 000000000..39c048312 --- /dev/null +++ b/libc/stdlib/malloc-930716/README @@ -0,0 +1,40 @@ +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/calloc.c b/libc/stdlib/malloc-930716/calloc.c new file mode 100644 index 000000000..152fe09c6 --- /dev/null +++ b/libc/stdlib/malloc-930716/calloc.c @@ -0,0 +1,25 @@ +/* calloc.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. */ + +#include +#include "malloc.h" + +/* Allocate space for the given number of elements of the given + size, initializing the whole region to binary zeroes. */ +void * +calloc(size_t nelem, size_t size) +{ + void *result; + + result = malloc(size * nelem); + if (result) + memset(result, 0, nelem * size); + return result; +} diff --git a/libc/stdlib/malloc-930716/free.c b/libc/stdlib/malloc-930716/free.c new file mode 100644 index 000000000..fbc98b714 --- /dev/null +++ b/libc/stdlib/malloc-930716/free.c @@ -0,0 +1,156 @@ +/* free.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. */ + +#include +#include +#include +#include "malloc.h" + +/* Return memory to the heap. */ +void +_free_internal (void *ptr) +{ + int block, blocks, i, type; + struct list *prev, *next; + + if (!ptr) + 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(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; + } +} + +struct alignlist *_aligned_blocks = NULL; + +void +free (void *ptr) +{ + register struct alignlist *l; + + if (ptr == NULL) + return; + + for (l = _aligned_blocks; l != NULL; l = l->next) + { + if (l->aligned == ptr) + { + l->aligned = NULL; /* Mark the slot in the list as free. */ + ptr = l->exact; + break; + } + } + + _free_internal (ptr); +} diff --git a/libc/stdlib/malloc-930716/malloc.c b/libc/stdlib/malloc-930716/malloc.c new file mode 100644 index 000000000..e8f7c7004 --- /dev/null +++ b/libc/stdlib/malloc-930716/malloc.c @@ -0,0 +1,254 @@ +/* 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. */ + +#include +#include +#include +#include +#include "malloc.h" + +/* How to really get more memory. */ +void *(*__morecore)(long) = __default_morecore_init; + +/* Pointer to the base of the first block. */ +char *_heapbase; + +/* Block information table. */ +union info *_heapinfo; + +/* Number of info entries. */ +static int heapsize; + +/* Search index in the info table. */ +int _heapindex; + +/* Limit of valid info table indices. */ +int _heaplimit; + +/* Count of large blocks allocated for each fragment size. */ +int _fragblocks[BLOCKLOG]; + +/* Free lists for each fragment size. */ +struct list _fraghead[BLOCKLOG]; + +/* Are we experienced? */ +static int initialized; + +/* Aligned allocation. */ +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. */ +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. */ +static void * +morecore(size_t size) +{ + void *result; + union info *newinfo, *oldinfo; + int 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; +#if 0 + free(oldinfo); +#else + _free_internal (oldinfo); +#endif + heapsize = newsize; + } + + _heaplimit = BLOCK((char *) result + size); + return result; +} + +/* Allocate memory from the heap. */ +void * +malloc (size_t size) +{ + void *result; + int log, block, blocks, i, lastblocks, start; + struct list *next; + + if (!initialized && !initialize()) + return NULL; + + /* Some programs will call malloc (0). We let them pass. */ +#if 0 + if (size == 0) + return NULL; +#endif + + if (size < sizeof (struct list)) + size = sizeof (struct list); + + /* 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(BLOCKSIZE); + if (!result) + return NULL; + ++_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) + return NULL; + 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; +} diff --git a/libc/stdlib/malloc-930716/malloc.h b/libc/stdlib/malloc-930716/malloc.h new file mode 100644 index 000000000..34458c062 --- /dev/null +++ b/libc/stdlib/malloc-930716/malloc.h @@ -0,0 +1,107 @@ +/* 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 + +/* Underlying allocation function; successive calls should return + contiguous pieces of memory. */ +extern void *(*__morecore)(long); + +/* Default value of previous. */ +extern void *__default_morecore_init(long); +extern void *__default_morecore(long); + +/* 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. + WARNING: BLOCKSIZE must be set greater than or equal to the + machine's page size for valloc() to work correctly. The default + definition here is 4096 bytes. */ +#define INT_BIT (CHAR_BIT * sizeof (int)) +#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 { + int type; /* Zero for a large block, or positive + giving the logarithm to the base two + of the fragment size. */ + union { + struct { + int nfree; /* Free fragments in a fragmented block. */ + int first; /* First free fragment of the block. */ + } frag; + int size; /* Size (in blocks) of a large cluster. */ + } info; + } busy; + struct { + int size; /* Size (in blocks) of a free cluster. */ + int next; /* Index of next free cluster. */ + int prev; /* Index of previous free cluster. */ + } free; +}; + +/* Pointer to first block of the heap. */ +extern char *_heapbase; + +/* Table indexed by block number giving per-block information. */ +extern union info *_heapinfo; + +/* Address to block number and vice versa. */ +#define BLOCK(A) (((char *) (A) - _heapbase) / BLOCKSIZE + 1) +#define ADDRESS(B) ((void *) (((B) - 1) * BLOCKSIZE + _heapbase)) + +/* Current search index for the heap table. */ +extern int _heapindex; + +/* Limit of valid info table indices. */ +extern int _heaplimit; + +/* Doubly linked lists of free fragments. */ +struct list { + struct list *next; + struct list *prev; +}; + +/* Count of blocks for each fragment size. */ +extern int _fragblocks[]; + +/* Free list headers for each fragment size. */ +extern struct list _fraghead[]; + +/* 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 void _free_internal __P ((__ptr_t __ptr)); + +extern void free (void *); +extern void * malloc (size_t); +extern void * calloc (size_t, size_t); +extern void * valloc (size_t); +extern void * memalign (size_t, size_t); +extern void * realloc (void *, size_t); diff --git a/libc/stdlib/malloc-930716/memalign.c b/libc/stdlib/malloc-930716/memalign.c new file mode 100644 index 000000000..1098f5890 --- /dev/null +++ b/libc/stdlib/malloc-930716/memalign.c @@ -0,0 +1,61 @@ +/* Copyright (C) 1991, 1992 Free Software Foundation, Inc. + +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; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#include +#include "malloc.h" + +__ptr_t +memalign (alignment, size) + 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; + 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) + { +#if 1 + free (result); +#else + _free_internal (result); +#endif + return NULL; + } + l->next = _aligned_blocks; + _aligned_blocks = l; + } + l->exact = result; + result = l->aligned = (char *) result + alignment - adj; + } + + return result; +} diff --git a/libc/stdlib/malloc-930716/morecore.c b/libc/stdlib/malloc-930716/morecore.c new file mode 100644 index 000000000..e2ad4464b --- /dev/null +++ b/libc/stdlib/malloc-930716/morecore.c @@ -0,0 +1,28 @@ +/* morecore.c - C library support routine for UNIX. + 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 +#include +#include "malloc.h" + +extern void *sbrk(int); + +/* Note that morecore has to take a signed argument so + that negative values can return memory to the system. */ +void * +__default_morecore_init(long size) +{ + void *result; + + result = sbrk(size); + if (result == (void *) -1) + return NULL; + return result; +} diff --git a/libc/stdlib/malloc-930716/realloc.c b/libc/stdlib/malloc-930716/realloc.c new file mode 100644 index 000000000..1453e813c --- /dev/null +++ b/libc/stdlib/malloc-930716/realloc.c @@ -0,0 +1,131 @@ +/* realloc.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. */ + +#include +#include +#include +#include +#include "malloc.h" + +#define MIN(A, B) ((A) < (B) ? (A) : (B)) + +/* 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; + int block, blocks, type; + int oldlimit; + + if (!ptr) + return malloc(size); + if (!size) { + free(ptr); + return malloc(0); + } + + 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(size)) != NULL) { + memcpy(result, ptr, size); +#if 1 + free(ptr); +#else + _free_internal(ptr); +#endif + + } + return result; + } + + /* 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; +#if 1 + free(ADDRESS(block + blocks)); +#else + _free_internal(ADDRESS(block + blocks)); +#endif + return ptr; + } else if (blocks == _heapinfo[block].busy.info.size) + /* No size change necessary. */ + return ptr; + 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; +#if 1 + free(ptr); +#else + _free_internal(ptr); +#endif + _heaplimit = oldlimit; + result = malloc(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(blocks * BLOCKSIZE); + else { + previous = malloc((block - _heapindex) * BLOCKSIZE); + malloc(blocks * BLOCKSIZE); +#if 1 + free(previous); +#else + _free_internal(previous); +#endif + } + return NULL; + } + if (ptr != result) + memmove(result, ptr, blocks * BLOCKSIZE); + return result; + } + 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. */ + return ptr; + else { + /* New size is different; allocate a new space, and copy + the lesser of the new size and the old. */ + result = malloc(size); + if (!result) + return NULL; + memcpy(result, ptr, MIN(size, 1 << type)); + free(ptr); + return result; + } + break; + } +} diff --git a/libc/stdlib/malloc-930716/valloc.c b/libc/stdlib/malloc-930716/valloc.c new file mode 100644 index 000000000..dad12a1d2 --- /dev/null +++ b/libc/stdlib/malloc-930716/valloc.c @@ -0,0 +1,62 @@ +/* Allocate memory on a page boundary. + Copyright (C) 1991, 1992 Free Software Foundation, Inc. + +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; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. + + The author may be reached (Email) at the address mike@ai.mit.edu, + or (US mail) as Mike Haertel c/o Free Software Foundation. */ + +#include +#include "malloc.h" + +#ifdef emacs +#include "config.h" +#endif + +#ifdef __GNU_LIBRARY__ +extern size_t __getpagesize __P ((void)); +#else +#ifndef USG +extern size_t getpagesize __P ((void)); +#define __getpagesize() getpagesize() +#else +#include +#ifdef EXEC_PAGESIZE +#define __getpagesize() EXEC_PAGESIZE +#else /* No EXEC_PAGESIZE. */ +#ifdef NBPG +#ifndef CLSIZE +#define CLSIZE 1 +#endif /* No CLSIZE. */ +#define __getpagesize() (NBPG * CLSIZE) +#else /* No NBPG. */ +#define __getpagesize() NBPC +#endif /* NBPG. */ +#endif /* EXEC_PAGESIZE. */ +#endif /* USG. */ +#endif + +static size_t pagesize; + +__ptr_t +valloc (size) + size_t size; +{ + if (pagesize == 0) + pagesize = __getpagesize (); + + return memalign (pagesize, size); +} -- cgit v1.2.3