diff options
author | Eric Andersen <andersen@codepoet.org> | 2001-01-11 11:42:17 +0000 |
---|---|---|
committer | Eric Andersen <andersen@codepoet.org> | 2001-01-11 11:42:17 +0000 |
commit | ae97a89e1a1a9833080dccc81f6cd26784e1b964 (patch) | |
tree | 6ff1ddc7e3980591c7fd0bbd5d9b8ac82da12886 /libc/stdlib | |
parent | abdc3e4d06db2b9d93c509774fc7c4fde918ec8e (diff) |
A large update from Manuel Novoa III <mnovoa3@bellsouth.net>.
Diffstat (limited to 'libc/stdlib')
-rw-r--r-- | libc/stdlib/Makefile | 6 | ||||
-rw-r--r-- | libc/stdlib/atexit.c | 82 | ||||
-rw-r--r-- | libc/stdlib/malloc-930716/Makefile | 51 | ||||
-rw-r--r-- | libc/stdlib/malloc-930716/README | 40 | ||||
-rw-r--r-- | libc/stdlib/malloc-930716/calloc.c | 25 | ||||
-rw-r--r-- | libc/stdlib/malloc-930716/free.c | 156 | ||||
-rw-r--r-- | libc/stdlib/malloc-930716/malloc.c | 254 | ||||
-rw-r--r-- | libc/stdlib/malloc-930716/malloc.h | 107 | ||||
-rw-r--r-- | libc/stdlib/malloc-930716/memalign.c | 61 | ||||
-rw-r--r-- | libc/stdlib/malloc-930716/morecore.c | 28 | ||||
-rw-r--r-- | libc/stdlib/malloc-930716/realloc.c | 131 | ||||
-rw-r--r-- | libc/stdlib/malloc-930716/valloc.c | 62 | ||||
-rw-r--r-- | libc/stdlib/malloc-simple/Makefile | 4 | ||||
-rw-r--r-- | libc/stdlib/malloc/Makefile | 4 | ||||
-rw-r--r-- | libc/stdlib/qsort.c | 220 | ||||
-rw-r--r-- | libc/stdlib/system.c | 2 |
16 files changed, 1020 insertions, 213 deletions
diff --git a/libc/stdlib/Makefile b/libc/stdlib/Makefile index 5d7c9405a..52d00f876 100644 --- a/libc/stdlib/Makefile +++ b/libc/stdlib/Makefile @@ -33,7 +33,7 @@ MSRC1=strto_ll.c MOBJ1=strtoll.o strtoull.o strto_ll.o MSRC2=atexit.c -MOBJ2=on_exit.o atexit.o __do_exit.o exit.o +MOBJ2=atexit.o exit.o CSRC = abort.c getenv.c mktemp.c qsort.c realpath.c abs.c bsearch.c \ @@ -65,8 +65,8 @@ $(MOBJ2): $(MSRC2) $(CC) $(CFLAGS) -DL_$* $< -c -o $*.o $(STRIPTOOL) -x -R .note -R .comment $*.o -$(COBJS): - $(CC) $(CFLAGS) $< -c $*.c -o $*.o +$(COBJS): %.o : %.c + $(CC) $(CFLAGS) -c $< -o $@ $(STRIPTOOL) -x -R .note -R .comment $*.o $(OBJ): Makefile diff --git a/libc/stdlib/atexit.c b/libc/stdlib/atexit.c index 1c164ff86..20195fa96 100644 --- a/libc/stdlib/atexit.c +++ b/libc/stdlib/atexit.c @@ -4,11 +4,12 @@ */ /* - * This deals with both the atexit and on_exit function calls - * - * Note calls installed with atexit are called with the same args as on_exit - * fuctions; the void* is given the NULL value. - * + * Manuel Novoa III Dec 2000 + * + * Modifications: + * Made atexit handling conform to standards... i.e. no args. + * Removed on_exit since it did not match gnu libc definition. + * Combined atexit and __do_exit into one object file. */ #include <errno.h> @@ -16,93 +17,58 @@ /* ATEXIT.H */ #define MAXONEXIT 20 /* AIUI Posix requires 10 */ -typedef void (*vfuncp) (); +typedef void (*vfuncp) (void); extern vfuncp __cleanup; extern void __do_exit(); extern void _exit __P((int __status)) __attribute__ ((__noreturn__)); -extern struct exit_table { - vfuncp called; - void *argument; -} __on_exit_table[MAXONEXIT]; - -extern int __on_exit_count; +extern vfuncp __atexit_table[MAXONEXIT]; +extern int __atexit_count; /* End ATEXIT.H */ #ifdef L_atexit -vfuncp __cleanup; - -int atexit(ptr) -vfuncp ptr; +int atexit(vfuncp ptr) { - if (__on_exit_count < 0 || __on_exit_count >= MAXONEXIT) { + if ((__atexit_count < 0) || (__atexit_count >= MAXONEXIT)) { errno = ENOMEM; return -1; } - __cleanup = __do_exit; if (ptr) { - __on_exit_table[__on_exit_count].called = ptr; - __on_exit_table[__on_exit_count].argument = 0; - __on_exit_count++; + __cleanup = __do_exit; + __atexit_table[__atexit_count++] = ptr; } return 0; } -#endif +vfuncp __atexit_table[MAXONEXIT]; +int __atexit_count = 0; -#ifdef L_on_exit -int on_exit(ptr, arg) -vfuncp ptr; -void *arg; +void __do_exit(int rv) { - if (__on_exit_count < 0 || __on_exit_count >= MAXONEXIT) { - errno = ENOMEM; - return -1; - } - __cleanup = __do_exit; - if (ptr) { - __on_exit_table[__on_exit_count].called = ptr; - __on_exit_table[__on_exit_count].argument = arg; - __on_exit_count++; - } - return 0; -} + int count = __atexit_count - 1; -#endif - -#ifdef L___do_exit - -int __on_exit_count = 0; -struct exit_table __on_exit_table[MAXONEXIT]; - -void __do_exit(rv) -int rv; -{ - register int count = __on_exit_count - 1; - register vfuncp ptr; - - __on_exit_count = -1; /* ensure no more will be added */ + __atexit_count = -1; /* ensure no more will be added */ __cleanup = 0; /* Calling exit won't re-do this */ /* In reverse order */ for (; count >= 0; count--) { - ptr = __on_exit_table[count].called; - (*ptr) (rv, __on_exit_table[count].argument); + (*__atexit_table[count])(); } } - #endif #ifdef L_exit +void __stdio_close_all(void); /* note: see _start.S - could be faked */ -void exit(rv) -int rv; +vfuncp __cleanup = 0; + +void exit(int rv) { if (__cleanup) __cleanup(); + __stdio_close_all(); _exit(rv); } - #endif 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 <string.h> +#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 <limits.h> +#include <stddef.h> +#include <stdlib.h> +#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 <limits.h> +#include <stddef.h> +#include <stdlib.h> +#include <string.h> +#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 <sys/cdefs.h> + +/* 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 <stdlib.h> +#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 <limits.h> +#include <stddef.h> +#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 <limits.h> +#include <stddef.h> +#include <stdlib.h> +#include <string.h> +#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 <stdlib.h> +#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 <sys/param.h> +#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); +} diff --git a/libc/stdlib/malloc-simple/Makefile b/libc/stdlib/malloc-simple/Makefile index 294902b97..cc2c132b2 100644 --- a/libc/stdlib/malloc-simple/Makefile +++ b/libc/stdlib/malloc-simple/Makefile @@ -40,8 +40,8 @@ $(MOBJ): $(MSRC) $(CC) $(CFLAGS) -DL_$* $< -c -o $*.o $(STRIPTOOL) -x -R .note -R .comment $*.o -$(COBJS): - $(CC) $(CFLAGS) $< -c $*.c -o $*.o +$(COBJS): %.o : %.c + $(CC) $(CFLAGS) -c $< -o $@ $(STRIPTOOL) -x -R .note -R .comment $*.o clean: diff --git a/libc/stdlib/malloc/Makefile b/libc/stdlib/malloc/Makefile index d7ae2732d..0128bc545 100644 --- a/libc/stdlib/malloc/Makefile +++ b/libc/stdlib/malloc/Makefile @@ -42,8 +42,8 @@ $(MOBJ): $(MSRC) $(CC) $(CFLAGS) -DL_$* $< -c -o $*.o $(STRIPTOOL) -x -R .note -R .comment $*.o -$(COBJS): - $(CC) $(CFLAGS) $< -c $*.c -o $*.o +$(COBJS): %.o : %.c + $(CC) $(CFLAGS) -c $< -o $@ $(STRIPTOOL) -x -R .note -R .comment $*.o clean: diff --git a/libc/stdlib/qsort.c b/libc/stdlib/qsort.c index 7cb1d8ab4..7390c3bd3 100644 --- a/libc/stdlib/qsort.c +++ b/libc/stdlib/qsort.c @@ -1,148 +1,72 @@ -/* - * This file lifted in toto from 'Dlibs' on the atari ST (RdeBath) - * - * - * Dale Schumacher 399 Beacon Ave. - * (alias: Dalnefre') St. Paul, MN 55104 - * dal@syntel.UUCP United States of America - * "It's not reality that's important, but how you perceive things." - */ -#include <string.h> - -char *_qbuf = 0; /* pointer to storage for qsort() */ - -#define PIVOT ((i+j)>>1) -#define moveitem(dst,src,size) if(dst != src) memcpy(dst, src, size) - -static void _wqsort(base, lo, hi, cmp) -register int *base; -register int lo; -register int hi; -register int (*cmp) (); -{ - int k; - register int i, j, t; - register int *p = &k; - - while (hi > lo) { - i = lo; - j = hi; - t = PIVOT; - *p = base[t]; - base[t] = base[i]; - base[i] = *p; - while (i < j) { - while (((*cmp) ((base + j), p)) > 0) - --j; - base[i] = base[j]; - while ((i < j) && (((*cmp) ((base + i), p)) <= 0)) - ++i; - base[j] = base[i]; - } - base[i] = *p; - if ((i - lo) < (hi - i)) { - _wqsort(base, lo, (i - 1), cmp); - lo = i + 1; - } else { - _wqsort(base, (i + 1), hi, cmp); - hi = i - 1; - } - } -} - -static void _lqsort(base, lo, hi, cmp) -register long *base; -register int lo; -register int hi; -register int (*cmp) (); -{ - long k; - register int i, j, t; - register long *p = &k; - - while (hi > lo) { - i = lo; - j = hi; - t = PIVOT; - *p = base[t]; - base[t] = base[i]; - base[i] = *p; - while (i < j) { - while (((*cmp) ((base + j), p)) > 0) - --j; - base[i] = base[j]; - while ((i < j) && (((*cmp) ((base + i), p)) <= 0)) - ++i; - base[j] = base[i]; - } - base[i] = *p; - if ((i - lo) < (hi - i)) { - _lqsort(base, lo, (i - 1), cmp); - lo = i + 1; - } else { - _lqsort(base, (i + 1), hi, cmp); - hi = i - 1; - } - } -} - -static void _nqsort(base, lo, hi, size, cmp) -register char *base; -register int lo; -register int hi; -register int size; -register int (*cmp) (); -{ - register int i, j; - register char *p = _qbuf; - - while (hi > lo) { - i = lo; - j = hi; - p = (base + size * PIVOT); - moveitem(_qbuf, p, size); - moveitem(p, (base + size * i), size); - moveitem((base + size * i), _qbuf, size); - p = _qbuf; - while (i < j) { - while (((*cmp) ((base + size * j), p)) > 0) - --j; - moveitem((base + size * i), (base + size * j), size); - while ((i < j) && (((*cmp) ((base + size * i), p)) <= 0)) - ++i; - moveitem((base + size * j), (base + size * i), size); - } - moveitem((base + size * i), p, size); - if ((i - lo) < (hi - i)) { - _nqsort(base, lo, (i - 1), size, cmp); - lo = i + 1; - } else { - _nqsort(base, (i + 1), hi, size, cmp); - hi = i - 1; - } - } -} - -extern int qsort(base, num, size, cmp) -char *base; -int num; -int size; -int (*cmp) (); -{ - char _qtemp[128]; - - if (_qbuf == 0) { - if (size > sizeof(_qtemp)) /* records too large! */ - return 1; - _qbuf = _qtemp; - } - if (size == 2) - _wqsort(base, 0, num - 1, cmp); - else if (size == 4) - _lqsort(base, 0, num - 1, cmp); - else - _nqsort(base, 0, num - 1, size, cmp); - if (_qbuf == _qtemp) - _qbuf = 0; - return 0; -} +/* +++Date last modified: 05-Jul-1997 */
+
+/*
+** ssort() -- Fast, small, qsort()-compatible Shell sort
+**
+** by Ray Gardner, public domain 5/90
+*/
+
+/*
+ * Manuel Novoa III Dec 2000
+ *
+ * There were several problems with the qsort code contained in uClibc.
+ * It assumed sizeof(int) was 2 and sizeof(long) was 4. It then had three
+ * seperate quiicksort routines based on the width of the data passed: 2, 4,
+ * or anything else <= 128. If the width was > 128, it returned -1 (although
+ * qsort should not return a value) and did no sorting. On i386 with
+ * -Os -fomit-frame-pointer -ffunction-sections, the text segment of qsort.o
+ * was 1358 bytes, with an additional 4 bytes in bss.
+ *
+ * I decided to completely replace the existing code with a small
+ * implementation of a shell sort. It is a drop-in replacement for the
+ * standard qsort and, with the same gcc flags as above, the text segment
+ * size on i386 is only 183 bytes.
+ *
+ * Grabbed original file rg_ssort.c from snippets.org.
+ * Modified original code to avoid possible overflow in wgap calculation.
+ * Modified wgap calculation in loop and eliminated variables gap and wnel.
+ */
+
+
+#include <stdlib.h>
+
+void qsort (void *base,
+ size_t nel,
+ size_t width,
+ int (*comp)(const void *, const void *))
+{
+ size_t wgap, i, j, k;
+ char *a, *b, tmp;
+
+#if 0
+ /* Note: still conceivable that nel * width could overflow! */
+ assert(width > 0);
+#endif
+
+ if (nel > 1) {
+ for (wgap = 0; ++wgap < (nel-1)/3 ; wgap *= 3) {}
+ wgap *= width;
+ nel *= width; /* convert nel to 'wnel' */
+ do {
+ for (i = wgap; i < nel; i += width) {
+ for (j = i - wgap; ;j -= wgap) {
+ a = j + ((char *)base);
+ b = a + wgap;
+ if ( (*comp)(a, b) <= 0 ) {
+ break;
+ }
+ k = width;
+ do {
+ tmp = *a;
+ *a++ = *b;
+ *b++ = tmp;
+ } while ( --k );
+ if (j < wgap) {
+ break;
+ }
+ }
+ }
+ wgap = (wgap - width)/3;
+ } while (wgap);
+ }
+}
diff --git a/libc/stdlib/system.c b/libc/stdlib/system.c index 061dbc914..5b279976c 100644 --- a/libc/stdlib/system.c +++ b/libc/stdlib/system.c @@ -35,7 +35,9 @@ char *command; signal(SIGQUIT, SIG_IGN); signal(SIGINT, SIG_IGN); +#if 0 printf("Waiting for child %d\n", pid); +#endif if (wait4(pid, &wait_val, 0, 0) == -1) wait_val = -1; |