diff options
Diffstat (limited to 'lib/malloclib')
| -rw-r--r-- | lib/malloclib/Makefile | 53 | ||||
| -rw-r--r-- | lib/malloclib/alloca.c | 189 | ||||
| -rw-r--r-- | lib/malloclib/calloc.c | 39 | ||||
| -rw-r--r-- | lib/malloclib/cfree.c | 43 | ||||
| -rw-r--r-- | lib/malloclib/free.c | 212 | ||||
| -rw-r--r-- | lib/malloclib/getpagesize.h | 56 | ||||
| -rw-r--r-- | lib/malloclib/i386-alloca.s | 16 | ||||
| -rw-r--r-- | lib/malloclib/malloc.c | 324 | ||||
| -rw-r--r-- | lib/malloclib/malloc.h | 268 | ||||
| -rw-r--r-- | lib/malloclib/mcheck.c | 133 | ||||
| -rw-r--r-- | lib/malloclib/memalign.c | 61 | ||||
| -rw-r--r-- | lib/malloclib/morecore.c | 44 | ||||
| -rw-r--r-- | lib/malloclib/mstats.c | 39 | ||||
| -rw-r--r-- | lib/malloclib/mtrace.awk | 36 | ||||
| -rw-r--r-- | lib/malloclib/mtrace.c | 150 | ||||
| -rw-r--r-- | lib/malloclib/realloc.c | 146 | ||||
| -rw-r--r-- | lib/malloclib/valloc.c | 48 | ||||
| -rw-r--r-- | lib/malloclib/x386-alloca.s | 63 | ||||
| -rw-r--r-- | lib/malloclib/xmalloc.c | 69 |
19 files changed, 1989 insertions, 0 deletions
diff --git a/lib/malloclib/Makefile b/lib/malloclib/Makefile new file mode 100644 index 0000000..7a449c3 --- /dev/null +++ b/lib/malloclib/Makefile @@ -0,0 +1,53 @@ +# Copyright (C) 1991 Free Software Foundation, Inc. +# This file is part of the GNU C Library. + +# The GNU C 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. + +# The GNU C 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 the GNU C Library; see the file COPYING.LIB. If +# not, write to the Free Software Foundation, Inc., 675 Mass Ave, +# Cambridge, MA 02139, USA. + +# Makefile for standalone distribution of malloc. + +srcdir = . +VPATH = .:$(srcdir) + +all: libmalloc.a + +sources = calloc.c cfree.c free.c malloc.c mcheck.c morecore.c \ + memalign.c mstats.c mtrace.c realloc.c valloc.c +objects = calloc.o cfree.o free.o malloc.o mcheck.o morecore.o \ + memalign.o mstats.o mtrace.o realloc.o valloc.o +headers = malloc.h getpagesize.h + +libmalloc.a: $(objects) + ar crv $@ $(objects) + ranlib $@ + +.c.o: + $(CC) $(CFLAGS) $(CPPFLAGS) -I. -c $< $(OUTPUT_OPTION) + +.PHONY: clean realclean malloc-clean malloc-realclean +clean malloc-clean: + -rm -f libmalloc.a $(objects) core +realclean malloc-realclean: clean + -rm -f TAGS tags *~ + +calloc.o: malloc.h +free.o: malloc.h +malloc.o: malloc.h +mcheck.o: malloc.h +memalign.o: malloc.h +mstats.o: malloc.h +mtrace.o: malloc.h +realloc.o: malloc.h +valloc.o: malloc.h getpagesize.h diff --git a/lib/malloclib/alloca.c b/lib/malloclib/alloca.c new file mode 100644 index 0000000..918d023 --- /dev/null +++ b/lib/malloclib/alloca.c @@ -0,0 +1,189 @@ +/* alloca -- (mostly) portable public-domain implementation -- D A Gwyn + + last edit: 86/05/30 rms + include config.h, since on VMS it renames some symbols. + Use xmalloc instead of malloc. + + This implementation of the PWB library alloca() function, + which is used to allocate space off the run-time stack so + that it is automatically reclaimed upon procedure exit, + was inspired by discussions with J. Q. Johnson of Cornell. + + It should work under any C implementation that uses an + actual procedure stack (as opposed to a linked list of + frames). There are some preprocessor constants that can + be defined when compiling for your specific system, for + improved efficiency; however, the defaults should be okay. + + The general concept of this implementation is to keep + track of all alloca()-allocated blocks, and reclaim any + that are found to be deeper in the stack than the current + invocation. This heuristic does not reclaim storage as + soon as it becomes invalid, but it will do so eventually. + + As a special case, alloca(0) reclaims storage without + allocating any. It is a good idea to use alloca(0) in + your main control loop, etc. to force garbage collection. +*/ +#ifndef lint +static char SCCSid[] = "@(#)alloca.c 1.1"; /* for the "what" utility */ +#endif + +#ifdef emacs +#include "config.h" +#ifdef static +/* actually, only want this if static is defined as "" + -- this is for usg, in which emacs must undefine static + in order to make unexec workable + */ +#ifndef STACK_DIRECTION +you +lose +-- must know STACK_DIRECTION at compile-time +#endif /* STACK_DIRECTION undefined */ +#endif /* static */ +#endif /* emacs */ + +#ifdef X3J11 +typedef void *pointer; /* generic pointer type */ +#else +typedef char *pointer; /* generic pointer type */ +#endif /* X3J11 */ + +#define NULL 0 /* null pointer constant */ + +extern void free(); +extern pointer xmalloc(); + +/* + Define STACK_DIRECTION if you know the direction of stack + growth for your system; otherwise it will be automatically + deduced at run-time. + + STACK_DIRECTION > 0 => grows toward higher addresses + STACK_DIRECTION < 0 => grows toward lower addresses + STACK_DIRECTION = 0 => direction of growth unknown +*/ + +#ifndef STACK_DIRECTION +#define STACK_DIRECTION 0 /* direction unknown */ +#endif + +#if STACK_DIRECTION != 0 + +#define STACK_DIR STACK_DIRECTION /* known at compile-time */ + +#else /* STACK_DIRECTION == 0; need run-time code */ + +static int stack_dir; /* 1 or -1 once known */ +#define STACK_DIR stack_dir + +static void +find_stack_direction (/* void */) +{ + static char *addr = NULL; /* address of first + `dummy', once known */ + auto char dummy; /* to get stack address */ + + if (addr == NULL) + { /* initial entry */ + addr = &dummy; + + find_stack_direction (); /* recurse once */ + } + else /* second entry */ + if (&dummy > addr) + stack_dir = 1; /* stack grew upward */ + else + stack_dir = -1; /* stack grew downward */ +} + +#endif /* STACK_DIRECTION == 0 */ + +/* + An "alloca header" is used to: + (a) chain together all alloca()ed blocks; + (b) keep track of stack depth. + + It is very important that sizeof(header) agree with malloc() + alignment chunk size. The following default should work okay. +*/ + +#ifndef ALIGN_SIZE +#define ALIGN_SIZE sizeof(double) +#endif + +typedef union hdr +{ + char align[ALIGN_SIZE]; /* to force sizeof(header) */ + struct + { + union hdr *next; /* for chaining headers */ + char *deep; /* for stack depth measure */ + } h; +} header; + +/* + alloca( size ) returns a pointer to at least `size' bytes of + storage which will be automatically reclaimed upon exit from + the procedure that called alloca(). Originally, this space + was supposed to be taken from the current stack frame of the + caller, but that method cannot be made to work for some + implementations of C, for example under Gould's UTX/32. +*/ + +static header *last_alloca_header = NULL; /* -> last alloca header */ + +pointer +alloca (size) /* returns pointer to storage */ + unsigned size; /* # bytes to allocate */ +{ + auto char probe; /* probes stack depth: */ + register char *depth = &probe; + +#if STACK_DIRECTION == 0 + if (STACK_DIR == 0) /* unknown growth direction */ + find_stack_direction (); +#endif + + /* Reclaim garbage, defined as all alloca()ed storage that + was allocated from deeper in the stack than currently. */ + { + register header *hp; /* traverses linked list */ + + for (hp = last_alloca_header; hp != NULL;) + if (STACK_DIR > 0 && hp->h.deep > depth + || STACK_DIR < 0 && hp->h.deep < depth) + { + register header *np = hp->h.next; + + free ((pointer) hp); /* collect garbage */ + + hp = np; /* -> next header */ + } + else + break; /* rest are not deeper */ + + last_alloca_header = hp; /* -> last valid storage */ + } + + if (size == 0) + return NULL; /* no allocation required */ + + /* Allocate combined header + user data storage. */ + + { + register pointer new = xmalloc (sizeof (header) + size); + /* address of header */ + + ((header *)new)->h.next = last_alloca_header; + ((header *)new)->h.deep = depth; + + last_alloca_header = (header *)new; + + /* User storage begins just after header. */ + + return (pointer)((char *)new + sizeof(header)); + } +} + diff --git a/lib/malloclib/calloc.c b/lib/malloclib/calloc.c new file mode 100644 index 0000000..f870e94 --- /dev/null +++ b/lib/malloclib/calloc.c @@ -0,0 +1,39 @@ +/* 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. */ + +#ifndef _MALLOC_INTERNAL +#define _MALLOC_INTERNAL +#include <malloc.h> +#endif + +/* Allocate an array of NMEMB elements each SIZE bytes long. + The entire array is initialized to zeros. */ +__ptr_t +calloc (nmemb, size) + register size_t nmemb; + register size_t size; +{ + register __ptr_t result = malloc (nmemb * size); + + if (result != NULL) + (void) memset (result, 0, nmemb * size); + + return result; +} diff --git a/lib/malloclib/cfree.c b/lib/malloclib/cfree.c new file mode 100644 index 0000000..adc1ff6 --- /dev/null +++ b/lib/malloclib/cfree.c @@ -0,0 +1,43 @@ +/* Copyright (C) 1991, 1993 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C 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. + +The GNU C 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 the GNU C Library; see the file COPYING.LIB. If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. */ + +#ifndef _MALLOC_INTERNAL +#define _MALLOC_INTERNAL +#include <malloc.h> +#endif + +#undef cfree + +#ifdef _LIBC + +#include <ansidecl.h> +#include <gnu-stabs.h> + +function_alias(cfree, free, void, (ptr), + DEFUN(cfree, (ptr), PTR ptr)) + +#else + +void +cfree (ptr) + __ptr_t ptr; +{ + free (ptr); +} + +#endif diff --git a/lib/malloclib/free.c b/lib/malloclib/free.c new file mode 100644 index 0000000..db97fcb --- /dev/null +++ b/lib/malloclib/free.c @@ -0,0 +1,212 @@ +/* Free a block of memory allocated by `malloc'. + Copyright 1990, 1991, 1992 Free Software Foundation + Written May 1989 by Mike Haertel. + +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. */ + +#ifndef _MALLOC_INTERNAL +#define _MALLOC_INTERNAL +#include <malloc.h> +#endif + +/* Debugging hook for free. */ +void (*__free_hook) __P ((__ptr_t __ptr)); + +/* List of blocks allocated by memalign. */ +struct alignlist *_aligned_blocks = NULL; + +/* Return memory to the heap. + Like `free' but don't call a __free_hook if there is one. */ +void +_free_internal (ptr) + __ptr_t ptr; +{ + int type; + size_t block, blocks; + register size_t i; + struct list *prev, *next; + + block = BLOCK (ptr); + + type = _heapinfo[block].busy.type; + switch (type) + { + case 0: + /* Get as many statistics as early as we can. */ + --_chunks_used; + _bytes_used -= _heapinfo[block].busy.info.size * BLOCKSIZE; + _bytes_free += _heapinfo[block].busy.info.size * BLOCKSIZE; + + /* 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; + ++_chunks_free; + } + + /* 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; + --_chunks_free; + } + + /* 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)) + { + register size_t bytes = blocks * BLOCKSIZE; + _heaplimit -= blocks; + (*__morecore) (-bytes); + _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; + --_chunks_free; + _bytes_free -= bytes; + } + + /* Set the next search to begin at this block. */ + _heapindex = block; + break; + + default: + /* Do some of the statistics. */ + --_chunks_used; + _bytes_used -= 1 << type; + ++_chunks_free; + _bytes_free += 1 << type; + + /* 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]; + next = prev; + for (i = 1; i < (size_t) (BLOCKSIZE >> type); ++i) + next = next->next; + prev->prev->next = next; + if (next != NULL) + next->prev = prev->prev; + _heapinfo[block].busy.type = 0; + _heapinfo[block].busy.info.size = 1; + + /* Keep the statistics accurate. */ + ++_chunks_used; + _bytes_used += BLOCKSIZE; + _chunks_free -= BLOCKSIZE >> type; + _bytes_free -= BLOCKSIZE; + + free (ADDRESS (block)); + } + else if (_heapinfo[block].busy.info.frag.nfree != 0) + { + /* If some fragments of this block are free, link this + fragment into the fragment list after the first free + fragment of this block. */ + next = (struct list *) ptr; + next->next = prev->next; + next->prev = prev; + prev->next = next; + if (next->next != NULL) + 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 long int) + ((unsigned long int) ((char *) ptr - (char *) NULL) + % BLOCKSIZE >> type); + prev->next = _fraghead[type].next; + prev->prev = &_fraghead[type]; + prev->prev->next = prev; + if (prev->next != NULL) + prev->next->prev = prev; + } + break; + } +} + +/* Return memory to the heap. */ +void +free (ptr) + __ptr_t 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; + } + + if (__free_hook != NULL) + (*__free_hook) (ptr); + else + _free_internal (ptr); +} diff --git a/lib/malloclib/getpagesize.h b/lib/malloclib/getpagesize.h new file mode 100644 index 0000000..b3aa4ba --- /dev/null +++ b/lib/malloclib/getpagesize.h @@ -0,0 +1,56 @@ +/* Emulation of getpagesize() for systems that need it. + Copyright (C) 1991 Free Software Foundation, Inc. + +This program is free software; you can redistribute it and/or modify +it under the terms of the GNU 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 General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program; if not, write to the Free Software +Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ + +#if !defined (USG) +extern size_t getpagesize __P ((void)); +# if !defined (HAVE_GETPAGESIZE) +# define HAVE_GETPAGESIZE +# endif /* !HAVE_GETPAGESIZE */ +#endif /* !USG */ + +#if !defined (HAVE_GETPAGESIZE) && defined (HAVE_UNISTD_H) +# include <unistd.h> +# if defined (_SC_PAGESIZE) +# define getpagesize() sysconf(_SC_PAGESIZE) +# endif /* _SC_PAGESIZE */ +#endif + +#if !defined (HAVE_GETPAGESIZE) +# include <sys/param.h> +# if defined (PAGESIZE) +# define getpagesize() PAGESIZE +# else /* !PAGESIZE */ +# if defined (EXEC_PAGESIZE) +# define getpagesize() EXEC_PAGESIZE +# else /* !EXEC_PAGESIZE */ +# if defined (NBPG) +# if !defined (CLSIZE) +# define CLSIZE 1 +# endif /* !CLSIZE */ +# define getpagesize() (NBPG * CLSIZE) +# else /* !NBPG */ +# if defined (NBPC) +# define getpagesize() NBPC +# endif /* NBPC */ +# endif /* !NBPG */ +# endif /* !EXEC_PAGESIZE */ +# endif /* !PAGESIZE */ +#endif /* !getpagesize */ + +#if !defined (HAVE_GETPAGESIZE) && !defined (getpagesize) +# define getpagesize() 4096 /* Just punt and use reasonable value */ +#endif /* !HAVE_GETPAGESIZE && !getpagesize */ diff --git a/lib/malloclib/i386-alloca.s b/lib/malloclib/i386-alloca.s new file mode 100644 index 0000000..01b2cfe --- /dev/null +++ b/lib/malloclib/i386-alloca.s @@ -0,0 +1,16 @@ + .file "alloca.s" + .text + .align 4 + .def alloca; .val alloca; .scl 2; .type 044; .endef + .globl alloca +alloca: + popl %edx + popl %eax + addl $3,%eax + andl $0xfffffffc,%eax + subl %eax,%esp + movl %esp,%eax + pushl %eax + pushl %edx + ret + .def alloca; .val .; .scl -1; .endef diff --git a/lib/malloclib/malloc.c b/lib/malloclib/malloc.c new file mode 100644 index 0000000..1d9bc03 --- /dev/null +++ b/lib/malloclib/malloc.c @@ -0,0 +1,324 @@ +/* Memory allocator `malloc'. + Copyright 1990, 1991, 1992, 1993 Free Software Foundation + Written May 1989 by Mike Haertel. + +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. */ + +#ifndef _MALLOC_INTERNAL +#define _MALLOC_INTERNAL +#include <malloc.h> +#endif + +/* How to really get more memory. */ +__ptr_t (*__morecore) __P ((ptrdiff_t __size)) = __default_morecore; + +/* Debugging hook for `malloc'. */ +__ptr_t (*__malloc_hook) __P ((size_t __size)); + +/* Pointer to the base of the first block. */ +char *_heapbase; + +/* Block information table. Allocated with align/__free (not malloc/free). */ +malloc_info *_heapinfo; + +/* Number of info entries. */ +static size_t heapsize; + +/* Search index in the info table. */ +size_t _heapindex; + +/* Limit of valid info table indices. */ +size_t _heaplimit; + +/* Count of large blocks allocated for each fragment size. */ +int _fragblocks[BLOCKLOG]; + +/* Free lists for each fragment size. */ +struct list _fraghead[BLOCKLOG]; + +/* Instrumentation. */ +size_t _chunks_used; +size_t _bytes_used; +size_t _chunks_free; +size_t _bytes_free; + +/* Are you experienced? */ +int __malloc_initialized; + +void (*__after_morecore_hook) __P ((void)); + +/* Aligned allocation. */ +static __ptr_t align __P ((size_t)); +static __ptr_t +align (size) + size_t size; +{ + __ptr_t result; + unsigned long int adj; + + result = (*__morecore) (size); + adj = (unsigned long int) ((unsigned long int) ((char *) result - + (char *) NULL)) % BLOCKSIZE; + if (adj != 0) + { + adj = BLOCKSIZE - adj; + (void) (*__morecore) (adj); + result = (char *) result + adj; + } + + if (__after_morecore_hook) + (*__after_morecore_hook) (); + + return result; +} + +/* Set everything up and remember that we have. */ +static int initialize __P ((void)); +static int +initialize () +{ + heapsize = HEAP / BLOCKSIZE; + _heapinfo = (malloc_info *) align (heapsize * sizeof (malloc_info)); + + _bytes_used = heapsize * sizeof (malloc_info); + _chunks_used++; + + if (_heapinfo == NULL) + return 0; + memset (_heapinfo, 0, heapsize * sizeof (malloc_info)); + _heapinfo[0].free.size = 0; + _heapinfo[0].free.next = _heapinfo[0].free.prev = 0; + _heapindex = 0; + _heapbase = (char *) _heapinfo; + __malloc_initialized = 1; + return 1; +} + +/* Get neatly aligned memory, initializing or + growing the heap info table as necessary. */ +static __ptr_t morecore __P ((size_t)); +static __ptr_t +morecore (size) + size_t size; +{ + __ptr_t result; + malloc_info *newinfo, *oldinfo; + size_t newsize; + + result = align (size); + if (result == NULL) + return NULL; + + /* Check if we need to grow the info table. */ + if ((size_t) BLOCK ((char *) result + size) > heapsize) + { + newsize = heapsize; + while ((size_t) BLOCK ((char *) result + size) > newsize) + newsize *= 2; + newinfo = (malloc_info *) align (newsize * sizeof (malloc_info)); + if (newinfo == NULL) + { + (*__morecore) (-size); + return NULL; + } + + _bytes_used += newsize * sizeof (malloc_info); + _chunks_used++; + + memset (newinfo, 0, newsize * sizeof (malloc_info)); + memcpy (newinfo, _heapinfo, heapsize * sizeof (malloc_info)); + oldinfo = _heapinfo; + newinfo[BLOCK (oldinfo)].busy.type = 0; + newinfo[BLOCK (oldinfo)].busy.info.size + = BLOCKIFY (heapsize * sizeof (malloc_info)); + _heapinfo = newinfo; + + heapsize = newsize; + } + + _heaplimit = BLOCK ((char *) result + size); + return result; +} + +/* Allocate memory from the heap. */ +__ptr_t +malloc (size) + size_t size; +{ + __ptr_t result; + size_t block, blocks, lastblocks, start; + register size_t i; + struct list *next; + + if (size == 0) + return NULL; + + if (__malloc_hook != NULL) + return (*__malloc_hook) (size); + + if (!__malloc_initialized) + if (!initialize ()) + return NULL; + + 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. */ + register size_t log = 1; + --size; + while ((size /= 2) != 0) + ++log; + + /* Look in the fragment lists for a + free fragment of the desired size. */ + next = _fraghead[log].next; + if (next != NULL) + { + /* 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 = (__ptr_t) next; + next->prev->next = next->next; + if (next->next != NULL) + next->next->prev = next->prev; + block = BLOCK (result); + if (--_heapinfo[block].busy.info.frag.nfree != 0) + _heapinfo[block].busy.info.frag.first = (unsigned long int) + ((unsigned long int) ((char *) next->next - (char *) NULL) + % BLOCKSIZE) >> log; + + /* Update the statistics. */ + ++_chunks_used; + _bytes_used += 1 << log; + --_chunks_free; + _bytes_free -= 1 << 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 == NULL) + return NULL; + ++_fragblocks[log]; + + /* Link all fragments but the first into the free list. */ + for (i = 1; i < (size_t) (BLOCKSIZE >> log); ++i) + { + next = (struct list *) ((char *) result + (i << log)); + next->next = _fraghead[log].next; + next->prev = &_fraghead[log]; + next->prev->next = next; + if (next->next != NULL) + 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; + + _chunks_free += (BLOCKSIZE >> log) - 1; + _bytes_free += BLOCKSIZE - (1 << log); + _bytes_used -= BLOCKSIZE - (1 << log); + } + } + 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 != 0 && block + lastblocks == _heaplimit && + (*__morecore) (0) == ADDRESS (block + lastblocks) && + (morecore ((blocks - lastblocks) * BLOCKSIZE)) != NULL) + { + /* 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 == NULL) + return NULL; + block = BLOCK (result); + _heapinfo[block].busy.type = 0; + _heapinfo[block].busy.info.size = blocks; + ++_chunks_used; + _bytes_used += blocks * BLOCKSIZE; + 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; + --_chunks_free; + } + + _heapinfo[block].busy.type = 0; + _heapinfo[block].busy.info.size = blocks; + ++_chunks_used; + _bytes_used += blocks * BLOCKSIZE; + _bytes_free -= blocks * BLOCKSIZE; + } + + return result; +} diff --git a/lib/malloclib/malloc.h b/lib/malloclib/malloc.h new file mode 100644 index 0000000..705a8c0 --- /dev/null +++ b/lib/malloclib/malloc.h @@ -0,0 +1,268 @@ +/* Declarations for `malloc' and friends. + Copyright 1990, 1991, 1992, 1993 Free Software Foundation, Inc. + Written May 1989 by Mike Haertel. + +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. */ + +#ifndef _MALLOC_H + +#define _MALLOC_H 1 + +#ifdef _MALLOC_INTERNAL +/* Harmless, gets __GNU_LIBRARY__ defined. + We must do this before #defining size_t and ptrdiff_t + because <stdio.h> tries to typedef them on some systems. */ +#include <stdio.h> +#endif + +#ifdef __cplusplus +extern "C" +{ +#endif + +#if defined (__cplusplus) || (defined (__STDC__) && __STDC__) +#undef __P +#define __P(args) args +#undef __ptr_t +#define __ptr_t void * +#else /* Not C++ or ANSI C. */ +#undef __P +#define __P(args) () +#undef const +#define const +#undef __ptr_t +#define __ptr_t char * +#endif /* C++ or ANSI C. */ + +#ifndef NULL +#define NULL 0 +#endif + +#ifdef __STDC__ +#include <stddef.h> +#else +#undef size_t +#define size_t unsigned int +#undef ptrdiff_t +#define ptrdiff_t int +#endif + + +/* Allocate SIZE bytes of memory. */ +extern __ptr_t malloc __P ((size_t __size)); +/* Re-allocate the previously allocated block + in __ptr_t, making the new block SIZE bytes long. */ +extern __ptr_t realloc __P ((__ptr_t __ptr, size_t __size)); +/* Allocate NMEMB elements of SIZE bytes each, all initialized to 0. */ +extern __ptr_t calloc __P ((size_t __nmemb, size_t __size)); +/* Free a block allocated by `malloc', `realloc' or `calloc'. */ +extern void free __P ((__ptr_t __ptr)); + +/* Allocate SIZE bytes allocated to ALIGNMENT bytes. */ +extern __ptr_t memalign __P ((size_t __alignment, size_t __size)); + +/* Allocate SIZE bytes on a page boundary. */ +extern __ptr_t valloc __P ((size_t __size)); + + +#ifdef _MALLOC_INTERNAL + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#if defined(__GNU_LIBRARY__) || defined(STDC_HEADERS) || defined(USG) +#include <string.h> +#else +#ifndef memset +#define memset(s, zero, n) bzero ((s), (n)) +#endif +#ifndef memcpy +#define memcpy(d, s, n) bcopy ((s), (d), (n)) +#endif +#ifndef memmove +#define memmove(d, s, n) bcopy ((s), (d), (n)) +#endif +#endif + + +#if defined(__GNU_LIBRARY__) || defined(__STDC__) +#include <limits.h> +#else +#define CHAR_BIT 8 +#endif + +/* 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(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. */ +typedef union + { + /* Heap information for a busy block. */ + struct + { + /* Zero for a large block, or positive giving the + logarithm to the base two of the fragment size. */ + int type; + union + { + struct + { + size_t nfree; /* Free fragments in a fragmented block. */ + size_t first; /* First free fragment of the block. */ + } frag; + /* Size (in blocks) of a large cluster. */ + size_t size; + } info; + } busy; + /* Heap information for a free block + (that may be the first of a free cluster). */ + 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; + } malloc_info; + +/* Pointer to first block of the heap. */ +extern char *_heapbase; + +/* Table indexed by block number giving per-block information. */ +extern malloc_info *_heapinfo; + +/* Address to block number and vice versa. */ +#define BLOCK(A) (((char *) (A) - _heapbase) / BLOCKSIZE + 1) +#define ADDRESS(B) ((__ptr_t) (((B) - 1) * BLOCKSIZE + _heapbase)) + +/* Current search index for the heap table. */ +extern size_t _heapindex; + +/* Limit of valid info table indices. */ +extern size_t _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; + +/* Instrumentation. */ +extern size_t _chunks_used; +extern size_t _bytes_used; +extern size_t _chunks_free; +extern size_t _bytes_free; + +/* Internal version of `free' used in `morecore' (malloc.c). */ +extern void _free_internal __P ((__ptr_t __ptr)); + +#endif /* _MALLOC_INTERNAL. */ + +/* Underlying allocation function; successive calls should + return contiguous pieces of memory. */ +extern __ptr_t (*__morecore) __P ((ptrdiff_t __size)); + +/* Default value of `__morecore'. */ +extern __ptr_t __default_morecore __P ((ptrdiff_t __size)); + +/* If not NULL, this function is called after each time + `__morecore' is called to increase the data size. */ +extern void (*__after_morecore_hook) __P ((void)); + +/* Nonzero if `malloc' has been called and done its initialization. */ +extern int __malloc_initialized; + +/* Hooks for debugging versions. */ +extern void (*__free_hook) __P ((__ptr_t __ptr)); +extern __ptr_t (*__malloc_hook) __P ((size_t __size)); +extern __ptr_t (*__realloc_hook) __P ((__ptr_t __ptr, size_t __size)); + +/* Activate a standard collection of debugging hooks. */ +extern int mcheck __P ((void (*__bfunc) __P ((char *)), + void (*__afunc) __P ((void)))); + +/* Activate a standard collection of tracing hooks. */ +extern void mtrace __P ((void)); + +/* Statistics available to the user. */ +struct mstats + { + size_t bytes_total; /* Total size of the heap. */ + size_t chunks_used; /* Chunks allocated by the user. */ + size_t bytes_used; /* Byte total of user-allocated chunks. */ + size_t chunks_free; /* Chunks in the free list. */ + size_t bytes_free; /* Byte total of chunks in the free list. */ + }; + +/* Pick up the current statistics. */ +extern struct mstats mstats __P ((void)); + +/* Call WARNFUN with a warning message when memory usage is high. */ +extern void memory_warnings __P ((__ptr_t __start, + void (*__warnfun) __P ((__const char *)))); + + +/* Relocating allocator. */ + +/* Allocate SIZE bytes, and store the address in *HANDLEPTR. */ +extern __ptr_t r_alloc __P ((__ptr_t *__handleptr, size_t __size)); + +/* Free the storage allocated in HANDLEPTR. */ +extern void r_alloc_free __P ((__ptr_t *__handleptr)); + +/* Adjust the block at HANDLEPTR to be SIZE bytes long. */ +extern __ptr_t r_re_alloc __P ((__ptr_t *__handleptr, size_t __size)); + + +#ifdef __cplusplus +} +#endif + +#endif /* malloc.h */ diff --git a/lib/malloclib/mcheck.c b/lib/malloclib/mcheck.c new file mode 100644 index 0000000..f7d9d4f --- /dev/null +++ b/lib/malloclib/mcheck.c @@ -0,0 +1,133 @@ +/* Standard debugging hooks for `malloc'. + Copyright 1990, 1991, 1992, 1993 Free Software Foundation + Written May 1989 by Mike Haertel. + +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. */ + +#ifndef _MALLOC_INTERNAL +#define _MALLOC_INTERNAL +#include <malloc.h> +#endif + +/* Old hook values. */ +static void (*old_free_hook) __P ((__ptr_t ptr)); +static __ptr_t (*old_malloc_hook) __P ((size_t size)); +static __ptr_t (*old_realloc_hook) __P ((__ptr_t ptr, size_t size)); + +/* Function to call when something awful happens. */ +static void (*abortfunc) __P ((void)); + +/* Arbitrary magical numbers. */ +#define MAGICWORD 0xfedabeeb +#define MAGICBYTE ((char) 0xd7) + +struct hdr + { + size_t size; /* Exact size requested by user. */ + unsigned long int magic; /* Magic number to check header integrity. */ + }; + +static void checkhdr __P ((const struct hdr *)); +static void +checkhdr (hdr) + const struct hdr *hdr; +{ + if (hdr->magic != MAGICWORD || ((char *) &hdr[1])[hdr->size] != MAGICBYTE) + (*abortfunc) (); +} + +static void freehook __P ((__ptr_t)); +static void +freehook (ptr) + __ptr_t ptr; +{ + struct hdr *hdr = ((struct hdr *) ptr) - 1; + checkhdr (hdr); + hdr->magic = 0; + __free_hook = old_free_hook; + free (hdr); + __free_hook = freehook; +} + +static __ptr_t mallochook __P ((size_t)); +static __ptr_t +mallochook (size) + size_t size; +{ + struct hdr *hdr; + + __malloc_hook = old_malloc_hook; + hdr = (struct hdr *) malloc (sizeof (struct hdr) + size + 1); + __malloc_hook = mallochook; + if (hdr == NULL) + return NULL; + + hdr->size = size; + hdr->magic = MAGICWORD; + ((char *) &hdr[1])[size] = MAGICBYTE; + return (__ptr_t) (hdr + 1); +} + +static __ptr_t reallochook __P ((__ptr_t, size_t)); +static __ptr_t +reallochook (ptr, size) + __ptr_t ptr; + size_t size; +{ + struct hdr *hdr = ((struct hdr *) ptr) - 1; + + checkhdr (hdr); + __free_hook = old_free_hook; + __malloc_hook = old_malloc_hook; + __realloc_hook = old_realloc_hook; + hdr = (struct hdr *) realloc ((__ptr_t) hdr, sizeof (struct hdr) + size + 1); + __free_hook = freehook; + __malloc_hook = mallochook; + __realloc_hook = reallochook; + if (hdr == NULL) + return NULL; + + hdr->size = size; + ((char *) &hdr[1])[size] = MAGICBYTE; + return (__ptr_t) (hdr + 1); +} + +int +mcheck (func) + void (*func) __P ((void)); +{ + extern void abort __P ((void)); + static int mcheck_used = 0; + + abortfunc = (func != NULL) ? func : abort; + + /* These hooks may not be safely inserted if malloc is already in use. */ + if (!__malloc_initialized && !mcheck_used) + { + old_free_hook = __free_hook; + __free_hook = freehook; + old_malloc_hook = __malloc_hook; + __malloc_hook = mallochook; + old_realloc_hook = __realloc_hook; + __realloc_hook = reallochook; + mcheck_used = 1; + } + + return mcheck_used ? 0 : -1; +} diff --git a/lib/malloclib/memalign.c b/lib/malloclib/memalign.c new file mode 100644 index 0000000..f5ad17c --- /dev/null +++ b/lib/malloclib/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. */ + +#ifndef _MALLOC_INTERNAL +#define _MALLOC_INTERNAL +#include <malloc.h> +#endif + +__ptr_t +memalign (alignment, size) + size_t alignment; + size_t size; +{ + __ptr_t result; + unsigned long int adj; + + size = ((size + alignment - 1) / alignment) * alignment; + + result = malloc (size); + 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) + { + free (result); + return NULL; + } + } + l->exact = result; + result = l->aligned = (char *) result + alignment - adj; + l->next = _aligned_blocks; + _aligned_blocks = l; + } + + return result; +} diff --git a/lib/malloclib/morecore.c b/lib/malloclib/morecore.c new file mode 100644 index 0000000..c9a9ca5 --- /dev/null +++ b/lib/malloclib/morecore.c @@ -0,0 +1,44 @@ +/* Copyright (C) 1991, 1992 Free Software Foundation, Inc. +This file is part of the GNU C Library. + +The GNU C Library is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +The GNU C 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 General Public License for more details. + +You should have received a copy of the GNU General Public License +along with the GNU C Library; see the file COPYING. If not, write to +the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + +#ifndef _MALLOC_INTERNAL +#define _MALLOC_INTERNAL +#include <malloc.h> +#endif + +#ifndef __GNU_LIBRARY__ +#define __sbrk sbrk +#endif + +extern __ptr_t __sbrk __P ((int increment)); + +#ifndef NULL +#define NULL 0 +#endif + +/* Allocate INCREMENT more bytes of data space, + and return the start of data space, or NULL on errors. + If INCREMENT is negative, shrink data space. */ +__ptr_t +__default_morecore (increment) + ptrdiff_t increment; +{ + __ptr_t result = __sbrk ((int) increment); + if (result == (__ptr_t) -1) + return NULL; + return result; +} diff --git a/lib/malloclib/mstats.c b/lib/malloclib/mstats.c new file mode 100644 index 0000000..511cdad --- /dev/null +++ b/lib/malloclib/mstats.c @@ -0,0 +1,39 @@ +/* Access the statistics maintained by `malloc'. + Copyright 1990, 1991, 1992 Free Software Foundation + Written May 1989 by Mike Haertel. + +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. */ + +#ifndef _MALLOC_INTERNAL +#define _MALLOC_INTERNAL +#include <malloc.h> +#endif + +struct mstats +mstats () +{ + struct mstats result; + + result.bytes_total = (char *) (*__morecore) (0) - _heapbase; + result.chunks_used = _chunks_used; + result.bytes_used = _bytes_used; + result.chunks_free = _chunks_free; + result.bytes_free = _bytes_free; + return result; +} diff --git a/lib/malloclib/mtrace.awk b/lib/malloclib/mtrace.awk new file mode 100644 index 0000000..d7689ce --- /dev/null +++ b/lib/malloclib/mtrace.awk @@ -0,0 +1,36 @@ +# +# Awk program to analyze mtrace.c output. +# +$1 == "+" { if (allocated[$2] != "") + print "+", $2, "Alloc", NR, "duplicate:", allocated[$2]; + else + allocated[$2] = $3; + } +$1 == "-" { if (allocated[$2] != "") { + allocated[$2] = ""; + if (allocated[$2] != "") + print "DELETE FAILED", $2, allocated[$2]; + } else + print "-", $2, "Free", NR, "was never alloc'd"; + } +$1 == "<" { if (allocated[$2] != "") + allocated[$2] = ""; + else + print "-", $2, "Realloc", NR, "was never alloc'd"; + } +$1 == ">" { if (allocated[$2] != "") + print "+", $2, "Realloc", NR, "duplicate:", allocated[$2]; + else + allocated[$2] = $3; + } + +# Ignore "= Start" +$1 == "=" { } +# Ignore failed realloc attempts for now +$1 == "!" { } + + +END { for (x in allocated) + if (allocated[x] != "") + print "+", x, allocated[x]; + } diff --git a/lib/malloclib/mtrace.c b/lib/malloclib/mtrace.c new file mode 100644 index 0000000..ea1d3a4 --- /dev/null +++ b/lib/malloclib/mtrace.c @@ -0,0 +1,150 @@ +/* More debugging hooks for `malloc'. + Copyright (C) 1991, 1992, 1993 Free Software Foundation, Inc. + Written April 2, 1991 by John Gilmore of Cygnus Support. + Based on mcheck.c by Mike Haertel. + +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. */ + +#ifndef _MALLOC_INTERNAL +#define _MALLOC_INTERNAL +#include <malloc.h> +#endif + +/* Don't #include <stdio.h> because <malloc.h> did it for us. */ + +#ifndef __GNU_LIBRARY__ +extern char *getenv (); +#else +#include <stdlib.h> +#endif + +static FILE *mallstream; +static char mallenv[]= "MALLOC_TRACE"; +static char mallbuf[BUFSIZ]; /* Buffer for the output. */ + +/* Address to breakpoint on accesses to... */ +__ptr_t mallwatch; + +/* Old hook values. */ +static void (*tr_old_free_hook) __P ((__ptr_t ptr)); +static __ptr_t (*tr_old_malloc_hook) __P ((size_t size)); +static __ptr_t (*tr_old_realloc_hook) __P ((__ptr_t ptr, size_t size)); + +/* This function is called when the block being alloc'd, realloc'd, or + freed has an address matching the variable "mallwatch". In a debugger, + set "mallwatch" to the address of interest, then put a breakpoint on + tr_break. */ + +void tr_break __P ((void)); +void +tr_break () +{ +} + +static void tr_freehook __P ((__ptr_t)); +static void +tr_freehook (ptr) + __ptr_t ptr; +{ + fprintf (mallstream, "- %p\n", ptr); /* Be sure to print it first. */ + if (ptr == mallwatch) + tr_break (); + __free_hook = tr_old_free_hook; + free (ptr); + __free_hook = tr_freehook; +} + +static __ptr_t tr_mallochook __P ((size_t)); +static __ptr_t +tr_mallochook (size) + size_t size; +{ + __ptr_t hdr; + + __malloc_hook = tr_old_malloc_hook; + hdr = (__ptr_t) malloc (size); + __malloc_hook = tr_mallochook; + + /* We could be printing a NULL here; that's OK. */ + fprintf (mallstream, "+ %p %x\n", hdr, size); + + if (hdr == mallwatch) + tr_break (); + + return hdr; +} + +static __ptr_t tr_reallochook __P ((__ptr_t, size_t)); +static __ptr_t +tr_reallochook (ptr, size) + __ptr_t ptr; + size_t size; +{ + __ptr_t hdr; + + if (ptr == mallwatch) + tr_break (); + + __free_hook = tr_old_free_hook; + __malloc_hook = tr_old_malloc_hook; + __realloc_hook = tr_old_realloc_hook; + hdr = (__ptr_t) realloc (ptr, size); + __free_hook = tr_freehook; + __malloc_hook = tr_mallochook; + __realloc_hook = tr_reallochook; + if (hdr == NULL) + /* Failed realloc. */ + fprintf (mallstream, "! %p %x\n", ptr, size); + else + fprintf (mallstream, "< %p\n> %p %x\n", ptr, hdr, size); + + if (hdr == mallwatch) + tr_break (); + + return hdr; +} + +/* We enable tracing if either the environment variable MALLOC_TRACE + is set, or if the variable mallwatch has been patched to an address + that the debugging user wants us to stop on. When patching mallwatch, + don't forget to set a breakpoint on tr_break! */ + +void +mtrace () +{ + char *mallfile; + + mallfile = getenv (mallenv); + if (mallfile != NULL || mallwatch != NULL) + { + mallstream = fopen (mallfile != NULL ? mallfile : "/dev/null", "w"); + if (mallstream != NULL) + { + /* Be sure it doesn't malloc its buffer! */ + setbuf (mallstream, mallbuf); + fprintf (mallstream, "= Start\n"); + tr_old_free_hook = __free_hook; + __free_hook = tr_freehook; + tr_old_malloc_hook = __malloc_hook; + __malloc_hook = tr_mallochook; + tr_old_realloc_hook = __realloc_hook; + __realloc_hook = tr_reallochook; + } + } +} diff --git a/lib/malloclib/realloc.c b/lib/malloclib/realloc.c new file mode 100644 index 0000000..2d31766 --- /dev/null +++ b/lib/malloclib/realloc.c @@ -0,0 +1,146 @@ +/* Change the size of a block allocated by `malloc'. + Copyright 1990, 1991, 1992, 1993 Free Software Foundation, Inc. + Written May 1989 by Mike Haertel. + +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. */ + +#ifndef _MALLOC_INTERNAL +#define _MALLOC_INTERNAL +#include <malloc.h> +#endif + +#define min(A, B) ((A) < (B) ? (A) : (B)) + +/* Debugging hook for realloc. */ +__ptr_t (*__realloc_hook) __P ((__ptr_t __ptr, size_t __size)); + +/* 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. This module has incestuous knowledge of the + internals of both free and malloc. */ +__ptr_t +realloc (ptr, size) + __ptr_t ptr; + size_t size; +{ + __ptr_t result; + int type; + size_t block, blocks, oldlimit; + + if (size == 0) + { + free (ptr); + return malloc (0); + } + else if (ptr == NULL) + return malloc (size); + + if (__realloc_hook != NULL) + return (*__realloc_hook) (ptr, size); + + block = BLOCK (ptr); + + type = _heapinfo[block].busy.type; + switch (type) + { + case 0: + /* Maybe reallocate a large block to a small fragment. */ + if (size <= BLOCKSIZE / 2) + { + result = malloc (size); + if (result != NULL) + { + memcpy (result, ptr, size); + free (ptr); + 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; + free (ADDRESS (block + blocks)); + result = ptr; + } + else if (blocks == _heapinfo[block].busy.info.size) + /* No size change necessary. */ + result = 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; + free (ptr); + _heaplimit = oldlimit; + result = malloc (size); + if (result == NULL) + { + /* 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) + (void) malloc (blocks * BLOCKSIZE); + else + { + __ptr_t previous = malloc ((block - _heapindex) * BLOCKSIZE); + (void) malloc (blocks * BLOCKSIZE); + free (previous); + } + return NULL; + } + if (ptr != result) + memmove (result, ptr, blocks * BLOCKSIZE); + } + break; + + default: + /* Old size is a fragment; type is logarithm + to base two of the fragment size. */ + if (size > (size_t) (1 << (type - 1)) && size <= (size_t) (1 << type)) + /* The new size is the same kind of fragment. */ + result = ptr; + else + { + /* The new size is different; allocate a new space, + and copy the lesser of the new size and the old. */ + result = malloc (size); + if (result == NULL) + return NULL; + memcpy (result, ptr, min (size, (size_t) 1 << type)); + free (ptr); + } + break; + } + + return result; +} diff --git a/lib/malloclib/valloc.c b/lib/malloclib/valloc.c new file mode 100644 index 0000000..eb5d372 --- /dev/null +++ b/lib/malloclib/valloc.c @@ -0,0 +1,48 @@ +/* Allocate memory on a page boundary. + Copyright (C) 1991, 1992, 1993 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. */ + +#ifndef _MALLOC_INTERNAL +#define _MALLOC_INTERNAL +#include <malloc.h> +#endif + +#if defined (emacs) || defined (HAVE_CONFIG_H) +#include "config.h" +#endif + +#ifdef __GNU_LIBRARY__ +extern size_t __getpagesize __P ((void)); +#else +#include "getpagesize.h" +#define __getpagesize() getpagesize() +#endif + +static size_t pagesize; + +__ptr_t +valloc (size) + size_t size; +{ + if (pagesize == 0) + pagesize = __getpagesize (); + + return memalign (pagesize, size); +} diff --git a/lib/malloclib/x386-alloca.s b/lib/malloclib/x386-alloca.s new file mode 100644 index 0000000..112d33c --- /dev/null +++ b/lib/malloclib/x386-alloca.s @@ -0,0 +1,63 @@ +;; alloca386.s 1.2 +;; GNU-compatible stack allocation function for Xenix/386. +;; Written by Chip Salzenberg at ComDev. +;; Last modified 90/01/11 +;;> Is your alloca clearly better than the one in i386-alloca.s? I haven't +;;> looked at either. +;; +;;They're different because Xenix/386 has a different assembler. SCO +;;Xenix has the Microsoft C compiler and the Microsoft macro assembler, +;;called "masm". MASM's assembler syntax is quite different from AT&T's +;;in all sorts of ways. Xenix people can't use the AT&T version. +;;-- +;;Chip Salzenberg at ComDev/TCT <chip@tct.uucp>, <uunet!ateng!tct!chip> + + TITLE $alloca386 + + .386 +DGROUP GROUP CONST, _BSS, _DATA +_DATA SEGMENT DWORD USE32 PUBLIC 'DATA' +_DATA ENDS +_BSS SEGMENT DWORD USE32 PUBLIC 'BSS' +_BSS ENDS +CONST SEGMENT DWORD USE32 PUBLIC 'CONST' +CONST ENDS +_TEXT SEGMENT DWORD USE32 PUBLIC 'CODE' + ASSUME CS: _TEXT, DS: DGROUP, SS: DGROUP, ES: DGROUP + + PUBLIC _alloca +_alloca PROC NEAR + +; Get argument. + pop edx ; edx -> return address + pop eax ; eax = amount to allocate + +; Validate allocation amount. + add eax,3 + and eax,not 3 + cmp eax,0 + jg aa_size_ok + mov eax,4 +aa_size_ok: + +; Allocate stack space. + mov ecx,esp ; ecx -> old stack pointer + sub esp,eax ; perform allocation + mov eax,esp ; eax -> new stack pointer + +; Copy the three saved register variables from old stack top to new stack top. +; They may not be there. So we waste twelve bytes. Big fat hairy deal. + push DWORD PTR 8[ecx] + push DWORD PTR 4[ecx] + push DWORD PTR 0[ecx] + +; Push something so the caller can pop it off. + push eax + +; Return to caller. + jmp edx + +_alloca ENDP + +_TEXT ENDS + END diff --git a/lib/malloclib/xmalloc.c b/lib/malloclib/xmalloc.c new file mode 100644 index 0000000..a25cb11 --- /dev/null +++ b/lib/malloclib/xmalloc.c @@ -0,0 +1,69 @@ +/* xmalloc.c -- safe versions of malloc and realloc */ + +/* Copyright (C) 1991 Free Software Foundation, Inc. + + This file is part of GNU Readline, a library for reading lines + of text with interactive input and history editing. + + Readline is free software; you can redistribute it and/or modify it + under the terms of the GNU General Public License as published by the + Free Software Foundation; either version 1, or (at your option) any + later version. + + Readline 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 + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with Readline; see the file COPYING. If not, write to the Free + Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + +#include <stdio.h> + +static void memory_error_and_abort (); + +/* **************************************************************** */ +/* */ +/* Memory Allocation and Deallocation. */ +/* */ +/* **************************************************************** */ + +/* Return a pointer to free()able block of memory large enough + to hold BYTES number of bytes. If the memory cannot be allocated, + print an error message and abort. */ +char * +xmalloc (bytes) + int bytes; +{ + char *temp = (char *)malloc (bytes); + + if (!temp) + memory_error_and_abort ("xmalloc"); + return (temp); +} + +char * +xrealloc (pointer, bytes) + char *pointer; + int bytes; +{ + char *temp; + + if (!pointer) + temp = (char *)malloc (bytes); + else + temp = (char *)realloc (pointer, bytes); + + if (!temp) + memory_error_and_abort ("xrealloc"); + return (temp); +} + +static void +memory_error_and_abort (fname) + char *fname; +{ + fprintf (stderr, "%s: Out of virtual memory!\n", fname); + abort (); +} |