diff options
Diffstat (limited to 'lib/libmalloc')
53 files changed, 6340 insertions, 0 deletions
diff --git a/lib/libmalloc/CHANGES b/lib/libmalloc/CHANGES new file mode 100644 index 000000000000..eaade6259236 --- /dev/null +++ b/lib/libmalloc/CHANGES @@ -0,0 +1,58 @@ +Jan 29, 1994 v1.13 + +Subtle realloc bug uncovered by Gianni Mariani's super malloc stress test. +(realloc could return a block less than _malloc_minchunk which could cause +free to die under certain conditions). testmalloc now checks this case. + +Dec 15, 1993 + +Fixed various problems with formats (printing ints for longs or vice versa) +pointed out by der Mouse. Integrated old fix to make grabhunk work if +blocks returned by the memfunc routine (sbrk, etc) are lower than the +previous blocks. Not well-tested yet. + +Jul 30, 1993 + +Bunch of fixes from mds@ilight.com (Mike Schechterman) to make it compile +and work on Alpha/OSF1, RS6000/AIX3.2, SGI/Irix4.0.5, HP720/HP-UX8.0.7, +DEC5000/Ultrix4.2. Thanks, Mike. + +Major user visible change is that 'make onefile' becomes 'make one' because +of overly-smart 'make's. Minor change is that testmalloc, teststomp and +simumalloc all want stdlib.h or proper stdio.h, else they have implicit +ints. I don't want to declare libc functions. + +Added ecalloc, _ecalloc. + +-- +Added mmap() support. + +Cleaned up externs.h a bit more, added sysconf() call for Posix + +Merged some of the smaller files into larger ones. + +Added mal_contents from ZMailer version of malloc, changed counters in +leak.c from long to unsigned long. + +On a pure allocation pattern, the old one started to take a bad +performance hit on the search that precedes an sbrk, because of the +wilderness preservation problem -- we search through every block in +the free list before the sbrk, even though none of them will satisfy +the request, since they're all probably little chunks left over from +the last sbrk chunk. So our performance reduces to the same as that of +the 4.1 malloc. Yech. If we were to preserve the wilderness, we +wouldn't have these little chunks. Good enough reason to reverse the +philosophy and cut blocks from the start, not the end. To minimize +pointer munging, means we have to make the block pointer p point to +the end of the block (i.e the end tag) NEXT becomes (p-1)->next, PREV +becomes (p-2)->prev, and the start tag becomes (p + 1 - +p->size)->size. The free logic is reversed -- preceding block merge +needs pointer shuffle, following block merge doesn't require pointer +shuffle. (has the additional advantage that realloc is more likely to +grow into a free area) Did this -- malloc, free stayed as complex/big, +but realloc and memalign simplified a fair bit. Now much faster on +pure allocation pattern, as well as any pattern where allocation +dominates, since fragmentation is less. Also much less wastage. + +Also trimmed down the search loop in malloc.c to make it much smaller +and simpler, also a mite faster. diff --git a/lib/libmalloc/COPYRIGHT b/lib/libmalloc/COPYRIGHT new file mode 100644 index 000000000000..5c3c417945d3 --- /dev/null +++ b/lib/libmalloc/COPYRIGHT @@ -0,0 +1,23 @@ +/* + * Copyright University of Toronto 1988, 1989, 1993. + * Written by Mark Moraes + * + * Permission is granted to anyone to use this software for any purpose on + * any computer system, and to alter it and redistribute it freely, subject + * to the following restrictions: + * + * 1. The author and the University of Toronto are not responsible + * for the consequences of use of this software, no matter how awful, + * even if they arise from flaws in it. + * + * 2. The origin of this software must not be misrepresented, either by + * explicit claim or by omission. Since few users ever read sources, + * credits must appear in the documentation. + * + * 3. Altered versions must be plainly marked as such, and must not be + * misrepresented as being the original software. Since few users + * ever read sources, credits must appear in the documentation. + * + * 4. This notice may not be removed or altered. + */ +/* This COPYRIGHT does not apply to the subdirectory splay and its contents */ diff --git a/lib/libmalloc/Makefile b/lib/libmalloc/Makefile new file mode 100644 index 000000000000..2ff0abf62b7f --- /dev/null +++ b/lib/libmalloc/Makefile @@ -0,0 +1,17 @@ +# $Id: Makefile,v 1.2 1994/05/27 10:42:42 csgr Exp $ + +CFLAGS+= -I${.CURDIR} -DHAVE_MMAP -DSTDHEADERS -fno-builtin +PFLAGS+= -DTRACE -DPROFILESIZES + +LIB= malloc + +SRCS+= _emalloc.c _malloc.c _memalign.c _strdup.c _strsave.c botch.c \ + dumpheap.c emalloc.c getmem.c leak.c malloc.c memalign.c setopts.c \ + sptree.c stats.c strdup.c strsave.c verify.c +NOMAN= noman + +beforeinstall: + install -c -o ${BINOWN} -g ${BINGRP} -m 444 ${.CURDIR}/malloc.h \ + ${DESTDIR}/usr/include + +.include <bsd.lib.mk> diff --git a/lib/libmalloc/Makefile.moraes b/lib/libmalloc/Makefile.moraes new file mode 100644 index 000000000000..c9d7fa3d45f6 --- /dev/null +++ b/lib/libmalloc/Makefile.moraes @@ -0,0 +1,187 @@ +# $Id: Makefile.moraes,v 1.1 1994/03/06 22:59:15 nate Exp $ +# +# This Makefile is set up to make a debugging malloc called libmalloc_d.a +# Also generates testmalloc and simumalloc, two regression tests. +# +# To make a production malloc, type 'make clean libmalloc' +# +# If you're impatient, and want it all in one file, type 'make one' +# and it'll merge the all the source into one file. Bit bigger, but +# avoids Unix linker misunderstandings if these are not in libc, and +# ensures the debugging routines are linked in whether called or not. +# On some machines, mv onefile.o libmalloc_d.a will work. On some, it +# upsets the linker and you will need to "ar ruv libmalloc_d.a onefile.o". +# +# 'make dist' runs 'bundle' to create a shell archive on stdout. +# +# 'make veryclean' cleans out lib*.a as well. +# +# 'make depend' runs 'mkdep' (from BSD src or named) to create dependencies. +# +# 'make install' puts all the OBJS in $(ARCHIVE), ranlibs it, and +# puts malloc.h in INCDIR. +# + +# neutralize SystemV genius +SHELL=/bin/sh + +# DEBUGDEFS are set for libmalloc_d.a. Say 'make libmalloc' for nondebug +# version. (DEBUGDEFS=$(FASTDEFS)) +# +DEBUGDEFS=-DDEBUG -DTRACE -DPROFILESIZES + +# FASTDEFS are used when the 'libmalloc' target is made. +# +# -DTRACE and -DPROFILESIZES shouldn't introduce very much overhead since the +# former is turned off (one 'if'), and the latter is one 'if' + increment. +# So you can keep them even in the fast production version. +# You may want to define -DBUGCOMPATIBILITY if you want malloc(0) to +# do the same thing as malloc(1). Some suntools programs expect this +# behaviour. So does Xlib, and the X server has done it at least once. +# (Note that SVID requires malloc(0) to return NULL, and the +# May 13, 1988 ANSI C draft says that you can either return a NULL pointer +# or a unique pointer (typically decisive standard...) +# +FASTDEFS=#-DBUGCOMPATIBILITY -DTRACE -DPROFILESIZES + + +# NORMALDEFS are used for both debugging and non-debugging versions +# -DSHORTNAMES makes sure all internal global symbols are unique within 6 +# characters. Avoid defining unless your linker is braindead. +# -DUSESTDIO is to make this use fputs() instead of write() for trace +# and debugging output. write() is preferable since it is unbuffered, +# and does not call malloc() or suchlike. Avoid defining if possible. +# -DSTDHEADERS if you have ANSI standard header files (stdlib.h, string.h) +# This can be defined on Solaris2.1, Irix3.3.x, BSD3.3, +# 386BSD, BSD386 and other sufficiently Posix systems. +# -DHAVE_MMAP should be defined for SunOS4.x and other systems +# that have a general purpose mmap call that allows memory-mapped files. +# +NORMALDEFS=-DHAVE_MMAP -DSTDHEADERS # -DSHORTNAMES -DUSESTDIO + +LIBMALLOC=libmalloc_d.a +ARCHIVE = $(HOME)/lib/$(LIBMALLOC) + +DEFINES= $(NORMALDEFS) $(DEBUGDEFS) + +LIBDIR=$(HOME)/lib +INCDIR=$(HOME)/include + +CC = gcc -Wall # -pedantic # add -pedantic if you fixed your includes. +# SGI needs cc -xansi -D__STDC__ on Irix4.0.5. + +EXTRAINCLUDES=-I$(HOME)/include +CDEBUGFLAGS=-g -O + +SPLAYOBJ = splay/sptree.o +SPLAYSRC = splay/sptree.c +SPLAYHDR = splay/sptree.h + +SRCS = _emalloc.c _malloc.c _memalign.c \ + _strdup.c _strsave.c botch.c \ + dumpheap.c emalloc.c getmem.c leak.c \ + malloc.c memalign.c setopts.c \ + stats.c strdup.c strsave.c verify.c + +OBJS = _emalloc.o _malloc.o _memalign.o \ + _strdup.o _strsave.o botch.o \ + dumpheap.o emalloc.o getmem.o leak.o \ + malloc.o memalign.o setopts.o \ + stats.o strdup.o strsave.o verify.o + +# HDRS, DOCS, TESTS and EXTRAS are used when making distributions. +# so please keep them uptodate. +# bundle is smart enough not to include object files, RCS, executables, +# etc, and does subdirectories right, but there's often other files +# in the development directory... + +# globals.c, version.c are included in malloc.c. +HDRS = align.h assert.h defs.h externs.h globals.c globals.h globrename.h \ + malloc.h trace.h version.c + +DOCS = README NOTE TODO CHANGES malloc.doc Makefile + +TESTS = testmalloc.c test.out testsbrk.c teststomp.c tests regress \ + simumalloc.c testrun.sh plot.sh munge.sh + +EXTRAS = splay + +INCLUDES=-I./splay $(EXTRAINCLUDES) + +LN = ln -s +OLDCC = cc +OLDCFLAGS = -O +AR = ar +ARFLAGS = ruv +RANLIB = ranlib + +LDFLAGS=#-Bstatic + +CFLAGS = $(CDEBUGFLAGS) $(INCLUDES) $(DEFINES) + +all: $(LIBMALLOC) testmalloc simumalloc teststomp + +libmalloc: + make -f Makefile $(MFLAGS) CC="$(CC)" DEBUGDEFS="$(FASTDEFS)" \ + LIBMALLOC=libmalloc.a CDEBUGFLAGS="$(CDEBUGFLAGS)" + +testmalloc: testmalloc.o $(LIBMALLOC) + $(CC) $(CFLAGS) -o testmalloc testmalloc.o $(LIBMALLOC) ${LDFLAGS} + +teststomp: teststomp.o $(LIBMALLOC) + $(CC) $(CFLAGS) -o teststomp teststomp.o $(LIBMALLOC) ${LDFLAGS} + +simumalloc: simumalloc.c $(LIBMALLOC) + $(CC) $(CFLAGS) -DMYMALLOC -o simumalloc \ + simumalloc.c $(LIBMALLOC) ${LDFLAGS} + +$(LIBMALLOC): $(OBJS) $(SPLAYOBJ) + rm -f $(LIBMALLOC) + $(AR) $(ARFLAGS) $(LIBMALLOC) $(OBJS) $(SPLAYOBJ) + -$(RANLIB) $(LIBMALLOC) + +$(SPLAYOBJ): .foo + cd splay; make $(MFLAGS) DEFINES="$(DEFINES)" \ + LIBMALLOC=../$(LIBMALLOC) CC="$(CC)" + +one: onefile.o + +onefile.c: $(SRCS) $(SPLAYSRC) + rm -f onefile.c + cat $(SRCS) $(SPLAYSRC) | sed '/RCSID/d' > onefile.c + +.foo: + +clean: + -rm -f *.o \#* *~ core a.out gmon.out mon.out testmalloc simumalloc \ + teststomp onefile.c *.sL prof.out + cd splay; make clean + +veryclean: clean + -rm -f libmalloc.a libmalloc_d.a make.log make.out + +install: + $(AR) $(ARFLAGS) $(ARCHIVE) $(OBJS) $(SPLAYOBJ) + -$(RANLIB) $(ARCHIVE) + install -c -m 644 malloc.h $(INCDIR) + +.id: $(SRCS) + mkid $(SRCS) $(SPLAYSRC) $(HDRS) $(SPLAYHDR) + touch .id + +dist: + @rm -f Makefile.bak + @mv Makefile Makefile.bak;\ + sed '/^# DO NOT PUT ANYTHING/,$$d' Makefile.bak > Makefile; \ + (bundle -v $(DOCS) $(SRCS) $(HDRS) $(TESTS) $(EXTRAS)); \ + mv Makefile.bak Makefile + +files: + find * -type f -print | \ + egrep -v '(,v|\.o|core|make.log|simumalloc|testmalloc|teststomp)$$' | \ + egrep -v '(libmalloc.*\.a|res\..*)$$' > FILES + +depend: onefile.c + mkdep $(INCLUDES) $(DEFINES) $(SRCS) onefile.c +# DO NOT DELETE THIS LINE -- mkdep uses it. +# DO NOT PUT ANYTHING AFTER THIS LINE, IT WILL GO AWAY. diff --git a/lib/libmalloc/NOTE b/lib/libmalloc/NOTE new file mode 100644 index 000000000000..dede8664d38e --- /dev/null +++ b/lib/libmalloc/NOTE @@ -0,0 +1,151 @@ +Miscellaneous notes on the malloc internals. + +First fit malloc with boundary tags for fast freeing - based on the +techniques described in 'The Art of Computer Programming' by Donald +Knuth. The essential features of the boundary tag are described in +Algorithm C, Section 2.5. The actual algorithms here incorporate the +improvements suggested in Exercises 12 and and 15 (I think), and +adaptations to the C/Un*x environment, plus some performance +improvements. By keeping the list circular, we don't have an AVAIL at +all - just use ROVER as the pointer into the list. It also tries to +"preserve the wilderness" -- i.e. try to keep the block nearest the +data break free as far as possible, but it does go overboard about it. +(i.e. it is a simple first fit -- many wilderness preservation schemes +tend to keep the wilderness block out of the free list, and search the +rest of the free list first. I find that degrades performance +somewhat, even if it keeps memory slightly less fragmented) + +This has a lot of debugging and tracing support built in - compiling +with -DDEBUG provides fairly comprehensive ASSERT protection to detect +heap corruption. (It aborts on the first sign of trouble). I hope that +every pointer reference is protected with an assertion, so the malloc +should never dump core or behave weirdly because of user program +misbehaviour -- it should blow an assertion instead. If the debugging +version ever gets a segmentation fault, bus error and dumps core +instead of blowing an assertion and then dumping core on an IO trap or +Illegal Instruction (depending on how your system does an abort()), I +want to know... + +For the non-debugging malloc: + +A minimum size for an allocated block is 4 units - two for the +leading and trailing size word, and two for the next and previous +pointers. Therefore the minimum size that we can allocate is 2 +units, since allocated and freed blocks both have the leading and +trailing size blocks. Only freed blocks have the next, prev +pointers. The size block is actually a signed - the sign bit +indicates whether it is a free or allocated block. i.e the tag. + +For the debugging malloc: + +The minimum size for an allocated block is still 4 units - two for the +leading and trailing size word, and two for the next and previous +pointers. But the minimum size that we can allocate is 1 units, since +allocated and freed blocks both have the leading and trailing size +blocks. Only freed blocks have the next, prev pointers. Only allocated +blocks have the realsize word, which indicates the size of the block +requested by the user in bytes. The next pointer and the realsize word +share the same header word. So the overhead for an allocated block is +3 words when debugging, as opposed to 2 words when not debugging. +(even though the minimum block size is still 4 words) + +The size block is actually a signed - the sign bit indicates whether +it is a free or allocated block. i.e the tag. Since the size is in +words, this loss of a bit is no big deal. The realsize block is a full +unsigned word, since it stores the size in bytes. + +For the leak tracing malloc + +The _*.c files all have the extra macros that record the blocks as +they are allocated, and deleted. The extra tracing macro also prints +the file name and line number before the usual tracing information +about size etc. This permits you to find out where block xxx was +freed, so that you can do an address to name mapping more easily. + +Note that to use this stuff, you HAVE to include malloc.h and define +MALLOC_TRACE when compiling. It still works correctly when you don't +include malloc.h, but you won't get all the information. + +Performance + +The fastest malloc I know of is the BSD4.3 malloc, which uses a number +of bins with different sized blocks, sized in powers of two. All it +has to do to find a free block is an iterated shift to compute the +bin, if the bin is empty then split a block from one of the higher +bins. Unfortunately, it can waste spectacular amounts of space for +many programs. + +The most space efficient malloc I know is Sun's Cartesian tree "better +fit" malloc (It has a hidden overhead of 8K of static data, though). +It is also unpleasantly slow. + +My malloc is close to the BSD4.3 malloc in performance - the +difference starts to become obvious only as the number of blocks in +the free list climbs towards the 100000 to million range at which +point the 4.3 malloc starts to pull ahead in user time, but quite +often, its VM behaviour deteriorates and makes its elapsed times very +large. My malloc is close to Sun's malloc in space efficiency. + +The key to the improved performance over typical first fit allocators +is the roving pointer, as well as the coalescing of freed blocks, +which keeps memory fragmentation and the size of the free list down. +The wilderness preservation heuristic also helps a lot. + +Guide to porting it: + +Should port without trouble to machines where any ugliness or +weirdness in pointers or segmentation is hidden from the programmer. I +haven't tried porting it to the 286 and below under DOS, nor do I +intend to at present. + +You may need to check align.h if your machine has non-standard +alignment requirements. (I interpret standard alignment to be +alignenment on one of char, int, char *, int *, char **, int **, +whichever requires the strictest alignment) If not, define ALIGN and +NALIGN. + +PLEASE LEAVE THE MAIN CODE FREE FROM #ifdefs. I'm interested in fixes +for porting it to new machines, only if they do not damage the code. +I'd prefer to find a least common denominator, or hide the difference +in a macro. + +People interested in reading and understanding this code should start +in defs.h (after this file, of course) -- it contains all the macros. +It'll help if you've read the following references. After that, study +globals.c, malloc.c, verify.c and dumpheap.c. Running testmalloc and +following the development of the heap is recommended. + +After you've ported it, you should be able to run testmalloc without +trouble, as well as the few runs of simumalloc listed in regress, +compiled with the debugging version of malloc. (-DDEBUG defined) + +If you uncover a bug, please enhance testmalloc.c with a case that +triggers the bug, if you can. That way, I can make sure future changes +to malloc don't re-introduce that bug. + +References: + +%A Donald E. Knuth +%T The Art of Computer Programming (Fundamental Algorithms) +%V 1 +%I Addison Wesley +%C Reading, Mass. +%D 1973 + +%A David G. Korn +%A Kiem-Phong Vo +%T In search of a better malloc +%J Proceedings of the USENIX 1985 Summer Conference +%C Portland, Oregon +%D June 1985 +%P 489-506 + +%A C.J. Stephenson +%T Fast fits: new methods for dynamic storage allocation +%J Proceedings of the Ninth ACM Symposium on Operating Systems Principles +%C Bretton Woods, New Hampshire +%D October 1983 +%P 30-32 +%O abstract only - paper to be published in TOCS +%O published as Operating Systems Review 17:5 +%O also appeared in Scientific American somewhere -- reference in Korn and Vo diff --git a/lib/libmalloc/README b/lib/libmalloc/README new file mode 100644 index 000000000000..6d508d37477e --- /dev/null +++ b/lib/libmalloc/README @@ -0,0 +1,68 @@ +This is a complete set of memory allocation functions (malloc and +friends). + The allocator is small, fast and space-efficient. + + It performs coalescing on frees. + + It has hooks for profiling, tracing and memory leak detection. + + It has very comprehensive and paranoid errorchecking as a compile + time option, enough to detect most forms of heap corruption. + + Optionally, it attempts to be compatible with the proposed ANSI C + Standard definition for the standard library functions malloc(), + calloc(), realloc() and free(). By default, it is more or less + compatible with existing Unix malloc() functions - some + differences do exist. (Notably free(), cfree() returning void, + realloc() not accepting a freed block) + +See the file malloc.doc for the full details. + +Porting to other machines shouldn't be hard if they have a civilized C +compiler, and an sbrk(). + +Eventually, the goal is to make this malloc() conformant with ANSI C - +it's getting there. It can be convinced to return void * and accept +size_t, so you can use it for ANSI C conformant programs by defining +ANSI_TYPES. Till then it's meant to be broadly conformant with Unix +malloc()s. + +To compile it, make sure ALIGN (in align.h) is correct for your machine, and +make it. testmalloc should run correctly and say Test done if it is +working, producing amazing amounts of heap trace. If it dumps core, it +isn't working... + +Depending on which end of the philosophical spectrum you lie, define +-DBUGCOMPATIBILITY. If defined, malloc(0) will do the same thing as +malloc(1). If not defined, the debugging malloc will abort() with an +error, while the non-debugging malloc will return NULL. (and set errno +to EINVAL). Note that the SVID requires malloc(0) to return NULL, and +the May 13, 1988 ANSI C draft says that you can either return a NULL +pointer or a unique pointer (typically decisive standard...) + +libmalloc.a is a fast, small version, with no +debugging/profiling/tracing, while libmalloc_d.a is the version with +all those three. (Profiling and tracing should not introduce serious +overhead, since profiling is simple and fast, (one 'if' and increment), +while tracing is turned off by default. So you may want to keep +profiling and tracing in the fast version as well) + make clean all +will make libmalloc_d.a and the test programs. + + make clean libmalloc +will make libmalloc.a. + +For linking convenience, you may want to compile the malloc as one +file instead. To do that, simply make onefile.o. It concatenates all +the src together and compiles it - the include files are protected +against multiple inclusion. This has the advantage of compiling in +things like mal_verify() and mal_trace() even if they aren't used, so +you can use them when debugging. + + Mark Moraes. + Computer Systems Research Institute, + Univerity of Toronto. + moraes@csri.toronto.{edu,cdn} + moraes@csri.utoronto.ca + moraes@utcsri.uucp + {your favourite backbone}!uunet!utai!utcsri!moraes diff --git a/lib/libmalloc/TODO b/lib/libmalloc/TODO new file mode 100644 index 000000000000..ae4430a74516 --- /dev/null +++ b/lib/libmalloc/TODO @@ -0,0 +1,62 @@ +alloca-like allocation with malloc -- mark()/release() paradigm. specify a +point where one starts a stack (stk_create), and stk_alloc from that. +stk_free releases the specified stack. This speeds up frees, doesn't speed +up mallocs too much? Time it in trace situations. + +Tests all in subdirectory. + +sbrk stuff for Mach. + +Scan all my email on malloc? + +Make the document a manual page. Terser, less cutesy. + +mal_size() returns size of a malloc'ed block in bytes. + +before starting a search in malloc(), if rover points to wilderness, and +wilderness->next is not null, rover = wilderness->next. need to keep +wilderness uptodate. should help rayan. + +check alignment in IS_VALID_PTR. + +Adaptive sbrk size. Keep increasing it by DEF_SBRKUNITS, then if sbrk fails, +half the sbrkunits till we're smaller than the request (in which case it's +all over). Should reduce the number of calls to sbrk without increasing +wastage too much. + +Generalize grabhunk() to work properly if new arenas are lower than the old +ones - i.e. don't rely on sbrk() semantics at all. I already did some of +this work in the port to the Firefly. [DONE -- Dec 15, 1993] + +Check that totalavail works right for realloc. Should we scrap totalavail +and save a pointer to the max block, so that can both tell if we need to +sbrk without a search, as well as realize if the max block has shrunk. +Problem: how do we know if the max block shrank below the size of some other +block? Heuristic? Average block size? Some adapting fraction of totalavail? +We sbrk if request is greater than (1+fraction)*totalavail/nfree is what +Korn and Vo suggest. Assuming fraction is always 1/K, we get +(K+1)*totalavail/K/nfree. We can double K everytime we fail a search. To +provide some negative feedback, we can change the 1 to M, and increment M +everytime we succeed in a search. Doesn't sound good. Need a better +heuristic. Grump. Avoid this stuff for now. + +Separate all system dependent stuff into a sysdep header where these things +can fight it out. + +create stdlib.h and move std. decls there. keep malloc.h as a value added +thing and declare new stuff there. decide on malloc(0). +(malloc 0 should return 0 sized block by default, I think) + +setopt Non-ansi should cause malloc(0), realloc(0, *) or realloc(*, 0) +to fail. + +some way to report when the last free happened when you try to use a freed +pointer. maintain a splay tree where you add ptrs when you free'em and +delete when you malloc them? + +finish my trace driven simulation stuff in ../maltrace. + +way to walk the heap. if it is a macro, then the other two could use it too. +should probably switch to arena before all these changes. + +interns.h from externs.h. Then we don't need aexterns.h. diff --git a/lib/libmalloc/_emalloc.c b/lib/libmalloc/_emalloc.c new file mode 100644 index 000000000000..347e8960f088 --- /dev/null +++ b/lib/libmalloc/_emalloc.c @@ -0,0 +1,55 @@ +/* Author: Mark Moraes <moraes@csri.toronto.edu> */ + +/*LINTLIBRARY*/ + +#include "defs.h" +#include "globals.h" +#include "trace.h" + +RCSID("$Id: _emalloc.c,v 1.1 1994/03/06 22:59:19 nate Exp $") + +univptr_t +__emalloc(nbytes, fname, linenum) +size_t nbytes; +const char *fname; +int linenum; +{ + univptr_t cp; + + PRTRACE(sprintf(_malloc_statsbuf, "%s:%d:", fname, linenum)); + cp = emalloc(nbytes); + RECORD_FILE_AND_LINE(cp, fname, linenum); + return(cp); +} + + +univptr_t +__erealloc(ptr, nbytes, fname, linenum) +univptr_t ptr; +size_t nbytes; +const char *fname; +int linenum; +{ + univptr_t cp; + + PRTRACE(sprintf(_malloc_statsbuf, "%s:%d:", fname, linenum)); + cp = erealloc(ptr, nbytes); + RECORD_FILE_AND_LINE(cp, fname, linenum); + return(cp); +} + +univptr_t +__ecalloc(nelem, sz, fname, linenum) +size_t nelem, sz; +const char *fname; +int linenum; +{ + univptr_t cp; + + PRTRACE(sprintf(_malloc_statsbuf, "%s:%d:", fname, linenum)); + cp = ecalloc(nelem, sz); + RECORD_FILE_AND_LINE(cp, fname, linenum); + return(cp); +} + + diff --git a/lib/libmalloc/_malloc.c b/lib/libmalloc/_malloc.c new file mode 100644 index 000000000000..34104e47f8c7 --- /dev/null +++ b/lib/libmalloc/_malloc.c @@ -0,0 +1,88 @@ +/* + * These are the wrappers around malloc for detailed tracing and leak + * detection. Allocation routines call RECORD_FILE_AND_LINE to record the + * filename/line number keyed on the block address in the splay tree, + * de-allocation functions call DELETE_RECORD to delete the specified block + * address and its associated file/line from the splay tree. + */ +/* Author: Mark Moraes <moraes@csri.toronto.edu> */ + +/*LINTLIBRARY*/ + +#include "defs.h" +#include "globals.h" +#include "trace.h" + +RCSID("$Id: _malloc.c,v 1.1 1994/03/06 22:59:20 nate Exp $") + +univptr_t +__malloc(nbytes, fname, linenum) +size_t nbytes; +const char *fname; +int linenum; +{ + univptr_t cp; + + PRTRACE(sprintf(_malloc_statsbuf, "%s:%d:", fname, linenum)); + cp = malloc(nbytes); + RECORD_FILE_AND_LINE(cp, fname, linenum); + return(cp); +} + +/* ARGSUSED if TRACE is not defined */ +void +__free(cp, fname, linenum) +univptr_t cp; +const char *fname; +int linenum; +{ + PRTRACE(sprintf(_malloc_statsbuf, "%s:%d:", fname, linenum)); + DELETE_RECORD(cp); + free(cp); +} + +univptr_t +__realloc(cp, nbytes, fname, linenum) +univptr_t cp; +size_t nbytes; +const char *fname; +int linenum; +{ + univptr_t old; + + PRTRACE(sprintf(_malloc_statsbuf, "%s:%d:", fname, linenum)); + old = cp; + cp = realloc(cp, nbytes); + if (old != cp) { + DELETE_RECORD(old); + RECORD_FILE_AND_LINE(cp, fname, linenum); + } + return(cp); +} + +univptr_t +__calloc(nelem, elsize, fname, linenum) +size_t nelem, elsize; +const char *fname; +int linenum; +{ + univptr_t cp; + + PRTRACE(sprintf(_malloc_statsbuf, "%s:%d:", fname, linenum)); + cp = calloc(nelem, elsize); + RECORD_FILE_AND_LINE(cp, fname, linenum); + return(cp); +} + +/* ARGSUSED if TRACE is not defined */ +void +__cfree(cp, fname, linenum) +univptr_t cp; +const char *fname; +int linenum; +{ + PRTRACE(sprintf(_malloc_statsbuf, "%s:%d:", fname, linenum)); + DELETE_RECORD(cp); + /* No point calling cfree() - it just calls free() */ + free(cp); +} diff --git a/lib/libmalloc/_memalign.c b/lib/libmalloc/_memalign.c new file mode 100644 index 000000000000..c39b3d269065 --- /dev/null +++ b/lib/libmalloc/_memalign.c @@ -0,0 +1,37 @@ +/* Author: Mark Moraes <moraes@csri.toronto.edu> */ + +/*LINTLIBRARY*/ + +#include "defs.h" +#include "globals.h" +#include "trace.h" + +RCSID("$Id: _memalign.c,v 1.1 1994/03/06 22:59:21 nate Exp $") + +univptr_t +__memalign(alignment, size, fname, linenum) +size_t alignment, size; +const char *fname; +int linenum; +{ + univptr_t cp; + + PRTRACE(sprintf(_malloc_statsbuf, "%s:%d:", fname, linenum)); + cp = memalign(alignment, size); + RECORD_FILE_AND_LINE(cp, fname, linenum); + return(cp); +} + +univptr_t +__valloc(size, fname, linenum) +size_t size; +const char *fname; +int linenum; +{ + univptr_t cp; + + PRTRACE(sprintf(_malloc_statsbuf, "%s:%d:", fname, linenum)); + cp = valloc(size); + RECORD_FILE_AND_LINE(cp, fname, linenum); + return(cp); +} diff --git a/lib/libmalloc/_strdup.c b/lib/libmalloc/_strdup.c new file mode 100644 index 000000000000..074bc1d68916 --- /dev/null +++ b/lib/libmalloc/_strdup.c @@ -0,0 +1,23 @@ +/* Author: Mark Moraes <moraes@csri.toronto.edu> */ + +/*LINTLIBRARY*/ + +#include "defs.h" +#include "globals.h" +#include "trace.h" + +RCSID("$Id: _strdup.c,v 1.1 1994/03/06 22:59:21 nate Exp $") + +char * +__strdup(s, fname, linenum) +char *s; +const char *fname; +int linenum; +{ + char *cp; + + PRTRACE(sprintf(_malloc_statsbuf, "%s:%d:", fname, linenum)); + cp = strdup(s); + RECORD_FILE_AND_LINE((univptr_t) cp, fname, linenum); + return(cp); +} diff --git a/lib/libmalloc/_strsave.c b/lib/libmalloc/_strsave.c new file mode 100644 index 000000000000..1db174d73d39 --- /dev/null +++ b/lib/libmalloc/_strsave.c @@ -0,0 +1,23 @@ +/* Author: Mark Moraes <moraes@csri.toronto.edu> */ + +/*LINTLIBRARY*/ + +#include "defs.h" +#include "globals.h" +#include "trace.h" + +RCSID("$Id: _strsave.c,v 1.1 1994/03/06 22:59:22 nate Exp $") + +char * +__strsave(s, fname, linenum) +char *s; +const char *fname; +int linenum; +{ + char *cp; + + PRTRACE(sprintf(_malloc_statsbuf, "%s:%d:", fname, linenum)); + cp = strsave(s); + RECORD_FILE_AND_LINE((univptr_t) cp, fname, linenum); + return(cp); +} diff --git a/lib/libmalloc/align.h b/lib/libmalloc/align.h new file mode 100644 index 000000000000..c1424895a9a3 --- /dev/null +++ b/lib/libmalloc/align.h @@ -0,0 +1,94 @@ +/* $Id: align.h,v 1.1 1994/03/06 22:59:26 nate Exp $ */ +#ifndef __ALIGN_H__ +#define __ALIGN_H__ +/* + * 'union word' must be aligned to the most pessimistic alignment needed + * on the architecture (See align.h) since all pointers returned by + * malloc and friends are really pointers to a Word. This is the job of + * the 'foo' field in the union, which actually decides the size. (On + * Sun3s, 1 int/long (4 bytes) is good enough, on Sun4s, 8 bytes are + * necessary, i.e. 2 ints/longs) + */ +/* + * 'union word' should also be the size necessary to ensure that an + * sbrk() immediately following an sbrk(sizeof(union word) * n) returns + * an address one higher than the first sbrk. i.e. contiguous space from + * successive sbrks. (Most sbrks will do this regardless of the size - + * Sun's doesnt) This is not vital - the malloc will work, but will not + * be able to coalesce between sbrk'ed segments. + */ + +#if defined(sparc) || defined(__sparc__) || defined(__sgi) +/* + * Sparcs require doubles to be aligned on double word, SGI R4000 based + * machines are 64 bit, this is the conservative way out + */ +/* this will waste space on R4000s or the 64bit UltraSparc */ +# define ALIGN long foo[2] +# define NALIGN 8 +#endif + +#if defined(__alpha) +/* 64 bit */ +# define ALIGN long foo +# define NALIGN 8 +#endif + +/* This default seems to work on most 32bit machines */ +#ifndef ALIGN +# define ALIGN long foo +# define NALIGN 4 +#endif + +/* Align with power of 2 */ +#define SIMPLEALIGN(X, N) (univptr_t)(((size_t)((char *)(X) + (N-1))) & ~(N-1)) + +#if NALIGN == 2 || NALIGN == 4 || NALIGN == 8 || NALIGN == 16 + /* if NALIGN is a power of 2, the next line will do ok */ +# define ALIGNPTR(X) SIMPLEALIGN(X, NALIGN) +#else + /* otherwise we need the generic version; hope the compiler isn't too smart */ + static size_t _N = NALIGN; +# define ALIGNPTR(X) (univptr_t)((((size_t)((univptr_t)(X)+(NALIGN-1)))/_N)*_N) +#endif + +/* + * If your sbrk does not return blocks that are aligned to the + * requirements of malloc(), as specified by ALIGN above, then you need + * to define SBRKEXTRA so that it gets the extra memory needed to find + * an alignment point. Not needed on Suns on which sbrk does return + * properly aligned blocks. But on U*x Vaxen, A/UX and UMIPS at least, + * you need to do this. It is safer to take the non Sun route (!! since + * the non-sun part also works on Suns, maybe we should just remove the + * Sun ifdef) + */ +#if ! (defined(sun) || defined(__sun__)) +# define SBRKEXTRA (sizeof(Word) - 1) +# define SBRKALIGN(x) ALIGNPTR(x) +#else +# define SBRKEXTRA 0 +# define SBRKALIGN(x) (x) +#endif + +#ifndef BITSPERBYTE + /* + * These values should work with any binary representation of integers + * where the high-order bit contains the sign. Should be in values.h, + * but just in case... + */ + /* a number used normally for size of a shift */ +# if gcos +# define BITSPERBYTE 9 +# else /* ! gcos */ +# define BITSPERBYTE 8 +# endif /* gcos */ +#endif /* BITSPERBYTE */ + +#ifndef BITS +# define BITS(type) (BITSPERBYTE * (int) sizeof(type)) +#endif /* BITS */ + +/* size_t with only the high-order bit turned on */ +#define HIBITSZ (((size_t) 1) << (BITS(size_t) - 1)) + +#endif /* __ALIGN_H__ */ /* Do not add anything after this line */ diff --git a/lib/libmalloc/assert.h b/lib/libmalloc/assert.h new file mode 100644 index 000000000000..08f11ff87994 --- /dev/null +++ b/lib/libmalloc/assert.h @@ -0,0 +1,10 @@ +/* $Id: assert.h,v 1.1 1994/05/19 14:34:09 nate Exp $ */ +#ifndef __ASSERT_H__ +#define __ASSERT_H__ +#ifdef DEBUG +#define ASSERT(p, s) ((void) (!(p) ? __m_botch(s, __FILE__, __LINE__) : 0)) +extern int __m_botch proto((const char *, const char *, int)); +#else +#define ASSERT(p, s) +#endif +#endif /* __ASSERT_H__ */ /* Do not add anything after this line */ diff --git a/lib/libmalloc/botch.c b/lib/libmalloc/botch.c new file mode 100644 index 000000000000..93b28b4938c8 --- /dev/null +++ b/lib/libmalloc/botch.c @@ -0,0 +1,45 @@ +#include "defs.h" +#include "globals.h" + +int +__nothing() +{ + return 0; +} + +/* + * Simple botch routine - writes directly to stderr. CAREFUL -- do not use + * printf because of the vile hack we use to redefine fputs with write for + * normal systems (i.e not super-pure ANSI)! + */ +int +__m_botch(s, filename, linenumber) +const char *s; +const char *filename; +int linenumber; +{ + static char linebuf[32]; /* Enough for a BIG linenumber! */ + static int notagain = 0; + + if (notagain == 0) { + /* Try to flush the trace file and unbuffer stderr */ + (void) fflush(_malloc_statsfile); + (void) setvbuf(stderr, (char *) 0, _IONBF, 0); + (void) sprintf(linebuf, "%d: ", linenumber); + (void) fputs("memory corruption error detected, file ", + stderr); + (void) fputs(filename, stderr); + (void) fputs(", line ", stderr); + (void) fputs(linebuf, stderr); + (void) fputs(s, stderr); + (void) fputs("\n", stderr); + /* + * In case stderr is buffered and was written to before we + * tried to unbuffer it + */ + (void) fflush(stderr); + notagain++; /* just in case abort() tries to cleanup */ + abort(); + } + return 0; /* SHOULDNTHAPPEN */ +} diff --git a/lib/libmalloc/bsd.lib.mk b/lib/libmalloc/bsd.lib.mk new file mode 100644 index 000000000000..4e4c51298e8d --- /dev/null +++ b/lib/libmalloc/bsd.lib.mk @@ -0,0 +1,269 @@ +# from: @(#)bsd.lib.mk 5.26 (Berkeley) 5/2/91 +# $Id: bsd.lib.mk,v 1.1 1994/03/06 22:59:28 nate Exp $ +# + +.if exists(${.CURDIR}/../Makefile.inc) +.include "${.CURDIR}/../Makefile.inc" +.endif + +.if exists(${.CURDIR}/shlib_version) +SHLIB_MAJOR != . ${.CURDIR}/shlib_version ; echo $$major +SHLIB_MINOR != . ${.CURDIR}/shlib_version ; echo $$minor +.endif + + +LIBDIR?= /usr/lib +LINTLIBDIR?= /usr/libdata/lint +LIBGRP?= bin +LIBOWN?= bin +LIBMODE?= 444 + +STRIP?= -s + +BINGRP?= bin +BINOWN?= bin +BINMODE?= 555 + +.MAIN: all + +# prefer .s to a .c, add .po, remove stuff not used in the BSD libraries +# .so used for PIC object files +.SUFFIXES: +.SUFFIXES: .out .o .po .so .s .S .c .cc .cxx .m .C .f .y .l + +.c.o: + ${CC} ${CFLAGS} -c ${.IMPSRC} -o ${.TARGET} + @${LD} -x -r ${.TARGET} + @mv a.out ${.TARGET} + +.c.po: + ${CC} -p ${CFLAGS} ${PFLAGS} -c ${.IMPSRC} -o ${.TARGET} + @${LD} -X -r ${.TARGET} + @mv a.out ${.TARGET} + +.c.so: + ${CC} ${PICFLAG} -DPIC ${CFLAGS} -c ${.IMPSRC} -o ${.TARGET} + +.cc.o .cxx.o .C.o: + ${CXX} ${CXXFLAGS} -c ${.IMPSRC} -o ${.TARGET} + @${LD} -x -r ${.TARGET} + @mv a.out ${.TARGET} + +.cc.po .C.po .cxx.o: + ${CXX} -p ${CXXFLAGS} -c ${.IMPSRC} -o ${.TARGET} + @${LD} -X -r ${.TARGET} + @mv a.out ${.TARGET} + +.cc.so .C.so: + ${CXX} ${PICFLAG} -DPIC ${CXXFLAGS} -c ${.IMPSRC} -o ${.TARGET} + +.f.o: + ${FC} ${FFLAGS} -o ${.TARGET} -c ${.IMPSRC} + @${LD} -x -r ${.TARGET} + @mv a.out ${.TARGET} + +.f.po: + ${FC} -p ${FFLAGS} -o ${.TARGET} -c ${.IMPSRC} + @${LD} -X -r ${.TARGET} + @mv a.out ${.TARGET} + +.f.so: + ${FC} ${PICFLAG} -DPIC ${FFLAGS} -o ${.TARGET} -c ${.IMPSRC} + +.s.o: + ${CPP} -E ${CFLAGS:M-[ID]*} ${AINC} ${.IMPSRC} | \ + ${AS} -o ${.TARGET} + @${LD} -x -r ${.TARGET} + @mv a.out ${.TARGET} + +.s.po: + ${CPP} -E -DPROF ${CFLAGS:M-[ID]*} ${AINC} ${.IMPSRC} | \ + ${AS} -o ${.TARGET} + @${LD} -X -r ${.TARGET} + @mv a.out ${.TARGET} + +.s.so: + ${CPP} -E -DPIC ${CFLAGS:M-[ID]*} ${AINC} ${.IMPSRC} | \ + ${AS} -k -o ${.TARGET} + +.S.o: + ${CPP} -E ${CFLAGS:M-[ID]*} ${AINC} ${.IMPSRC} | \ + ${AS} -o ${.TARGET} + +.S.po: + ${CPP} -E -DPROF ${CFLAGS:M-[ID]*} ${AINC} ${.IMPSRC} | \ + ${AS} -o ${.TARGET} + +.S.so: + ${CPP} -E -DPIC ${CFLAGS:M-[ID]*} ${AINC} ${.IMPSRC} | \ + ${AS} -k -o ${.TARGET} + +.m.po: + ${CC} ${CFLAGS} -p -c ${.IMPSRC} -o ${.TARGET} + @${LD} -X -r ${.TARGET} + @mv a.out ${.TARGET} + +.m.o: + ${CC} ${CFLAGS} -c ${.IMPSRC} -o ${.TARGET} + @${LD} -X -r ${.TARGET} + @mv a.out ${.TARGET} + +.if defined(PROFILE) +_LIBS=lib${LIB}.a lib${LIB}_p.a +.else +_LIBS=lib${LIB}.a +.endif + +.if !defined(NOPIC) +.if defined(SHLIB_MAJOR) && defined(SHLIB_MINOR) +_LIBS+=lib${LIB}.so.${SHLIB_MAJOR}.${SHLIB_MINOR} +.endif +.if defined(INSTALL_PIC_ARCHIVE) +_LIBS+=lib${LIB}_pic.a +.endif +.endif + +.if !defined(PICFLAG) +PICFLAG=-fpic +.endif + +all: ${_LIBS} # llib-l${LIB}.ln + +OBJS+= ${SRCS:N*.h:R:S/$/.o/g} + +lib${LIB}.a:: ${OBJS} + @echo building standard ${LIB} library + @rm -f lib${LIB}.a + @${AR} cTq lib${LIB}.a `lorder ${OBJS} | tsort` ${LDADD} + ${RANLIB} lib${LIB}.a + +POBJS+= ${OBJS:.o=.po} +lib${LIB}_p.a:: ${POBJS} + @echo building profiled ${LIB} library + @rm -f lib${LIB}_p.a + @${AR} cTq lib${LIB}_p.a `lorder ${POBJS} | tsort` ${LDADD} + ${RANLIB} lib${LIB}_p.a + +SOBJS+= ${OBJS:.o=.so} +lib${LIB}.so.${SHLIB_MAJOR}.${SHLIB_MINOR}: ${SOBJS} + @echo building shared ${LIB} library \(version ${SHLIB_MAJOR}.${SHLIB_MINOR}\) + @rm -f lib${LIB}.so.${SHLIB_MAJOR}.${SHLIB_MINOR} + @$(LD) -Bshareable \ + -o lib${LIB}.so.${SHLIB_MAJOR}.${SHLIB_MINOR} \ + ${SOBJS} ${LDADD} + +lib${LIB}_pic.a:: ${SOBJS} + @echo building special pic ${LIB} library + @rm -f lib${LIB}_pic.a + @${AR} cTq lib${LIB}_pic.a ${SOBJS} ${LDADD} + ${RANLIB} lib${LIB}_pic.a + +llib-l${LIB}.ln: ${SRCS} + ${LINT} -C${LIB} ${CFLAGS} ${.ALLSRC:M*.c} + +.if !target(clean) +clean: + rm -f a.out Errs errs mklog ${CLEANFILES} ${OBJS} + rm -f lib${LIB}.a llib-l${LIB}.ln + rm -f ${POBJS} profiled/*.o lib${LIB}_p.a + rm -f ${SOBJS} shared/*.o + rm -f lib${LIB}.so.*.* lib${LIB}_pic.a +.endif + +.if !target(cleandir) +cleandir: + rm -f a.out Errs errs mklog ${CLEANFILES} ${OBJS} + rm -f lib${LIB}.a llib-l${LIB}.ln + rm -f ${.CURDIR}/tags .depend + rm -f ${POBJS} profiled/*.o lib${LIB}_p.a + rm -f ${SOBJS} shared/*.o + rm -f lib${LIB}.so.*.* lib${LIB}_pic.a + cd ${.CURDIR}; rm -rf obj; +.endif + +.if defined(SRCS) +afterdepend: + @(TMP=/tmp/_depend$$$$; \ + sed -e 's/^\([^\.]*\).o[ ]*:/\1.o \1.po \1.so:/' < .depend > $$TMP; \ + mv $$TMP .depend) +.endif + +.if !target(install) +.if !target(beforeinstall) +beforeinstall: +.endif + +realinstall: beforeinstall + install ${COPY} -o ${LIBOWN} -g ${LIBGRP} -m ${LIBMODE} lib${LIB}.a \ + ${DESTDIR}${LIBDIR} + ${RANLIB} -t ${DESTDIR}${LIBDIR}/lib${LIB}.a +.if defined(PROFILE) + install ${COPY} -o ${LIBOWN} -g ${LIBGRP} -m ${LIBMODE} \ + lib${LIB}_p.a ${DESTDIR}${LIBDIR} + ${RANLIB} -t ${DESTDIR}${LIBDIR}/lib${LIB}_p.a +.endif +.if !defined(NOPIC) +.if defined(SHLIB_MAJOR) && defined(SHLIB_MINOR) + install ${COPY} -o ${LIBOWN} -g ${LIBGRP} -m ${LIBMODE} \ + lib${LIB}.so.${SHLIB_MAJOR}.${SHLIB_MINOR} ${DESTDIR}${LIBDIR} +.endif +.if defined(INSTALL_PIC_ARCHIVE) + install ${COPY} -o ${LIBOWN} -g ${LIBGRP} -m ${LIBMODE} \ + lib${LIB}_pic.a ${DESTDIR}${LIBDIR} + ${RANLIB} -t ${DESTDIR}${LIBDIR}/lib${LIB}_pic.a +.endif +.endif +.if defined(LINKS) && !empty(LINKS) + @set ${LINKS}; \ + while test $$# -ge 2; do \ + l=${DESTDIR}$$1; \ + shift; \ + t=${DESTDIR}$$1; \ + shift; \ + echo $$t -\> $$l; \ + rm -f $$t; \ + ln $$l $$t; \ + done; true +.endif + +install: afterinstall +.if !defined(NOMAN) +afterinstall: realinstall maninstall +.else +afterinstall: realinstall +.endif +.endif + +.if !target(lint) +lint: +.endif + +.if !target(tags) +tags: ${SRCS} + -cd ${.CURDIR}; ctags -f /dev/stdout ${.ALLSRC:M*.c} | \ + sed "s;\${.CURDIR}/;;" > tags +.endif + +.if !defined(NOMAN) +.include <bsd.man.mk> +.elif !target(maninstall) +maninstall: +.endif + +.if !target(obj) +.if defined(NOOBJ) +obj: +.else +obj: + @cd ${.CURDIR}; rm -rf obj; \ + here=`pwd`; dest=/usr/obj`echo $$here | sed 's,^/usr/src,,'`; \ + echo "$$here -> $$dest"; ln -s $$dest obj; \ + if test -d /usr/obj -a ! -d $$dest; then \ + mkdir -p $$dest; \ + else \ + true; \ + fi; +.endif +.endif + +.include <bsd.dep.mk> diff --git a/lib/libmalloc/defs.h b/lib/libmalloc/defs.h new file mode 100644 index 000000000000..0f794f1cee71 --- /dev/null +++ b/lib/libmalloc/defs.h @@ -0,0 +1,386 @@ +/* Author: Mark Moraes <moraes@csri.toronto.edu> */ +/* $Id: defs.h,v 1.1 1994/03/06 22:59:29 nate Exp $ */ +#ifndef __DEFS_H__ +#define __DEFS_H__ +/* + * This file includes all relevant include files, and defines various + * types and constants. It also defines lots of macros which operate on + * the malloc blocks and pointers, to try and keep the ugliness + * abstracted away from the source code. + */ + +#include <stdio.h> +#include <errno.h> +extern int errno; /* Some errno.h don't declare this */ + +/* + * ANSI defines malloc to return void *, and take size_t as an + * argument, while present Unix convention is char * and unsigned int + * respectively. This is not ifdef'ed with STDC because you may want to + * compile a Unix malloc with an ANSI C compiler or vice versa. Note + * that sys/types.h on BSD Unix systems defines size_t to be int or + * long. memsize_t is for routines that expect int in Unix and size_t + * in ANSI. + */ +#ifdef STDHEADERS +# define univptr_t void * +# define memsize_t size_t +#else /* ! STDHEADERS */ +# define univptr_t char * +# define size_t unsigned int +# define memsize_t int +#endif /* STDHEADERS */ + +#ifndef REGISTER +# ifdef __GNUC__ + /* gcc probably does better register allocation than I do */ +# define REGISTER +# else +# define REGISTER register +# endif +#endif + +/* + * Just in case you want an ANSI malloc without an ANSI compiler, or + * ANSI includes + */ +#if defined(STDHEADERS) && !defined(offsetof) && !defined(__FreeBSD__) +# define size_t unsigned long +#endif + +#if defined(__STDC__) +# define proto(x) x +#else +# define proto(x) () +# define const +# define volatile +#endif + +#include "externs.h" +#include "assert.h" + +#ifndef EXIT_FAILURE +# define EXIT_FAILURE 1 +#endif + +#ifdef __STDC__ +# include <limits.h> +# ifndef BITSPERBYTE +# define BITSPERBYTE CHAR_BIT +# endif +#else +# include <values.h> +#endif +#include "align.h" /* Needs BITSPERBYTE */ + +/* + * We assume that FREE is a 0 bit, and the for a free block, + * SIZE(p) == SIZEMASK(p) as an optimization to avoid an unnecessary + * masking operation with SIZEMASK. See FREESIZE below. Or'ing with + * ALLOCED should turn on the high bit, And'ing with SIZEMASK should + * turn it off. + */ + +#define FREE ((size_t) 0) +#define ALLOCED (HIBITSZ) +#define SIZEMASK (~HIBITSZ) + +union word { /* basic unit of storage */ + size_t size; /* size of this block + 1 bit status */ + union word *next; /* next free block */ + union word *prev; /* prev free block */ + univptr_t ptr; /* stops lint complaining, keeps alignment */ + char c; + int i; + char *cp; + char **cpp; + int *ip; + int **ipp; + ALIGN; /* alignment stuff - wild fun */ +}; + +typedef union word Word; + +/* + * WARNING - Many of these macros are UNSAFE because they have multiple + * evaluations of the arguments. Use with care, avoid side-effects. + */ +/* + * These macros define operations on a pointer to a block. The zero'th + * word of a block is the size field, where the top bit is 1 if the + * block is allocated. This word is also referred to as the starting tag. + * The last word of the block is identical to the zero'th word of the + * block and is the end tag. IF the block is free, the second last word + * is a pointer to the next block in the free list (a doubly linked list + * of all free blocks in the heap), and the third from last word is a + * pointer to the previous block in the free list. HEADERWORDS is the + * number of words before the pointer in the block that malloc returns, + * TRAILERWORDS is the number of words after the returned block. Note + * that the zero'th and the last word MUST be the boundary tags - this + * is hard-wired into the algorithm. Increasing HEADERWORDS or + * TRAILERWORDS suitably should be accompanied by additional macros to + * operate on those words. The routines most likely to be affected are + * malloc/realloc/free/memalign/mal_verify/mal_heapdump. + */ +/* + * There are two ways we can refer to a block -- by pointing at the + * start tag, or by pointing at the end tag. For reasons of efficiency + * and performance, free blocks are always referred to by the end tag, + * while allocated blocks are usually referred to by the start tag. + * Accordingly, the following macros indicate the type of their argument + * by using either 'p', 'sp', or 'ep' to indicate a pointer. 'p' means + * the pointer could point at either the start or end tag. 'sp' means it + * must point at a start tag for that macro to work correctly, 'ep' + * means it must point at the end tag. Usually, macros operating on free + * blocks (NEXT, PREV, VALID_PREV_PTR, VALID_NEXT_PTR) take 'ep', while + * macros operating on allocated blocks (REALSIZE, MAGIC_PTR, + * SET_REALSIZE) take 'sp'. The size field may be validated using either + * VALID_START_SIZE_FIELD for an 'sp' or VALID_END_SIZE_FIELD for an + * 'ep'. + */ +/* + * SIZE, SIZEFIELD and TAG are valid for allocated and free blocks, + * REALSIZE is valid for allocated blocks when debugging, and NEXT and + * PREV are valid for free blocks. We could speed things up by making + * the free list singly linked when not debugging - the double link are + * just so we can check for pointer validity. (PREV(NEXT(ep)) == ep and + * NEXT(PREV(ep)) == ep). FREESIZE is used only to get the size field + * from FREE blocks - in this implementation, free blocks have a tag + * bit of 0 so no masking is necessary to operate on the SIZEFIELD when + * a block is free. We take advantage of that as a minor optimization. + */ +#define SIZEFIELD(p) ((p)->size) +#define SIZE(p) ((size_t) (SIZEFIELD(p) & SIZEMASK)) +#define ALLOCMASK(n) ((n) | ALLOCED) +#define FREESIZE(p) SIZEFIELD(p) +/* + * FREEMASK should be (n) & SIZEMASK, but since (n) will always have + * the hi bit off after the conversion from bytes requested by the user + * to words. + */ +#define FREEMASK(n) (n) +#define TAG(p) (SIZEFIELD(p) & ~SIZEMASK) + +#ifdef DEBUG +# define REALSIZE(sp) (((sp)+1)->size) +#endif /* DEBUG */ + +#define NEXT(ep) (((ep)-1)->next) +#define PREV(ep) (((ep)-2)->prev) + +/* + * HEADERWORDS is the real block header in an allocated block - the + * free block header uses extra words in the block itself + */ +#ifdef DEBUG +# define HEADERWORDS 2 /* Start boundary tag + real size in bytes */ +#else /* ! DEBUG */ +# define HEADERWORDS 1 /* Start boundary tag */ +#endif /* DEBUG */ + +#define TRAILERWORDS 1 + +#define FREEHEADERWORDS 1 /* Start boundary tag */ + +#define FREETRAILERWORDS 3 /* next and prev, end boundary tag */ + +#define ALLOC_OVERHEAD (HEADERWORDS + TRAILERWORDS) +#define FREE_OVERHEAD (FREEHEADERWORDS + FREETRAILERWORDS) + +/* + * The allocator views memory as a list of non-contiguous arenas. (If + * successive sbrks() return contiguous blocks, they are colaesced into + * one arena - if a program never calls sbrk() other than malloc(), + * then there should only be one arena. This malloc will however + * happily coexist with other allocators calling sbrk() and uses only + * the blocks given to it by sbrk. It expects the same courtesy from + * other allocators. The arenas are chained into a linked list using + * the first word of each block as a pointer to the next arena. The + * second word of the arena, and the last word, contain fake boundary + * tags that are permanantly marked allocated, so that no attempt is + * made to coalesce past them. See the code in dumpheap for more info. + */ +#define ARENASTART 2 /* next ptr + fake start tag */ + +#ifdef DEBUG + /* + * 1 for prev link in free block - next link is absorbed by header + * REALSIZE word + */ +# define FIXEDOVERHEAD (1 + ALLOC_OVERHEAD) +#else /* ! DEBUG */ + /* 1 for prev link, 1 for next link, + header and trailer */ +# define FIXEDOVERHEAD (2 + ALLOC_OVERHEAD) +#endif /* DEBUG */ + +/* + * Check that pointer is safe to dereference i.e. actually points + * somewhere within the heap and is properly aligned. + */ +#define PTR_IN_HEAP(p) \ + ((p) > _malloc_loword && (p) < _malloc_hiword && \ + ALIGNPTR(p) == ((univptr_t) (p))) + +/* Check that the size field is valid */ +#define VALID_START_SIZE_FIELD(sp) \ + (PTR_IN_HEAP((sp) + SIZE(sp) - 1) && \ + SIZEFIELD(sp) == SIZEFIELD((sp) + SIZE(sp) - 1)) + +#define VALID_END_SIZE_FIELD(ep) \ + (PTR_IN_HEAP((ep) - SIZE(ep) + 1) && \ + SIZEFIELD(ep) == SIZEFIELD((ep) - SIZE(ep) + 1)) + + +#define ulong unsigned long + +#ifdef DEBUG + /* + * Byte that is stored at the end of each block if the requested size + * of the block is not a multiple of sizeof(Word). (If it is a multiple + * of sizeof(Word), then we don't need to put the magic because the + * endboundary tag will be corrupted and the tests that check the + * validity of the boundary tag should detect it + */ +# ifndef u_char +# define u_char unsigned char +# endif /* u_char */ + +# define MAGIC_BYTE ((u_char) '\252') + /* + * Check if size of the block is identical to requested size. Typical + * tests will be of the form DONT_NEED_MAGIC(p) || something for + * short-circuited protection, because blocks where DONT_NEED_MAGIC is + * true will be tested for boundary tag detection so we don't need the + * magic byte at the end. + */ +# define DONT_NEED_MAGIC(sp) \ + (REALSIZE(sp) == ((SIZE(sp) - ALLOC_OVERHEAD) * sizeof(Word))) + + /* Note that VALID_REALSIZE must not be used if DONT_NEED_MAGIC is true */ +# define VALID_REALSIZE(sp) \ + (REALSIZE(sp) < ((SIZE(sp) - ALLOC_OVERHEAD)*sizeof(Word))) + + /* Location of the magic byte */ +# define MAGIC_PTR(sp) ((u_char *)((sp) + HEADERWORDS) + REALSIZE(sp)) + + /* + * malloc code should only use the next two macros SET_REALSIZE and + * VALID_MAGIC, since they are the only ones which have non-DEBUG + * (null) alternatives + */ + + /* Macro sets the realsize of a block if necessary */ +# define SET_REALSIZE(sp, n) \ + (REALSIZE(sp) = (n), \ + DONT_NEED_MAGIC(sp) || (*MAGIC_PTR(sp) = MAGIC_BYTE)) + + /* Macro tests that the magic byte is valid if it exists */ +# define VALID_MAGIC(sp) \ + (DONT_NEED_MAGIC(sp) || \ + (VALID_REALSIZE(sp) && (*MAGIC_PTR(sp) == MAGIC_BYTE))) + +#else /* ! DEBUG */ +# define SET_REALSIZE(sp, n) +# define VALID_MAGIC(sp) (1) +#endif /* DEBUG */ + +/* + * Check that a free list ptr points to a block with something pointing + * back. This is the only reason we use a doubly linked free list. + */ +#define VALID_NEXT_PTR(ep) (PTR_IN_HEAP(NEXT(ep)) && PREV(NEXT(ep)) == (ep)) +#define VALID_PREV_PTR(ep) (PTR_IN_HEAP(PREV(ep)) && NEXT(PREV(ep)) == (ep)) + +/* + * quick bit-arithmetic to check a number (including 1) is a power of two. + */ +#define is_power_of_2(x) ((((x) - 1) & (x)) == 0) + +/* + * An array to try and keep track of the distribution of sizes of + * malloc'ed blocks + */ +#ifdef PROFILESIZES +# define MAXPROFILESIZE 2*1024 +# define COUNTSIZE(nw) (_malloc_scount[((nw) < MAXPROFILESIZE) ? (nw) : 0]++) +#else +# define COUNTSIZE(nw) +#endif + +#define DEF_SBRKUNITS 1024 + +#ifndef USESTDIO + /* + * Much better not to use stdio - stdio calls malloc() and can + * therefore cause problems when debugging heap corruption. However, + * there's no guaranteed way to turn off buffering on a FILE pointer in + * ANSI. This is a vile kludge! + */ +# define fputs(s, f) write(fileno(f), (s), strlen(s)) +# define setvbuf(f, s, n, l) __nothing() +# define fflush(f) __nothing() +#endif /* USESTDIO */ + +#ifdef TRACE + /* + * Prints a trace string. For convenience, x is an + * sprintf(_malloc_statsbuf, ...) or strcpy(_malloc_statsbuf, ...); + * something which puts the appropriate text to be printed in + * _malloc_statsbuf - ugly, but more convenient than making x a string. + */ +# define PRTRACE(x) \ + if (_malloc_tracing) { \ + (void) x; \ + (void) fputs(_malloc_statsbuf, _malloc_statsfile); \ + } else \ + _malloc_tracing += 0 +#else +# define PRTRACE(x) +#endif + +#ifdef DEBUG +# define CHECKHEAP() \ + if (_malloc_debugging >= 2) \ + (void) mal_verify(_malloc_debugging >= 3); \ + else \ + _malloc_debugging += 0 +#else +# define CHECKHEAP() +#endif + +#define FREEMAGIC '\125' + +/* + * Memory functions but in words. We just call memset/memcpy, and hope + * that someone has optimized them. If you are on pure 4.2BSD, either + * redefine these in terms of bcopy/your own memcpy, or + * get the functions from one of 4.3src/Henry Spencer's strings + * package/C News src + */ +#define MEMSET(p, c, n) \ + (void) memset((univptr_t) (p), (c), (memsize_t) ((n) * sizeof(Word))) +#define MEMCPY(p1, p2, n) \ + (void) memcpy((univptr_t) (p1), (univptr_t) (p2), \ + (memsize_t) ((n) * sizeof(Word))) + + +#ifdef DEBUG +# define DMEMSET(p, n) MEMSET((p), FREEMAGIC, (n)) +#else +# define DMEMSET(p, n) +#endif + +/* + * Thanks to Hugh Redelmeier for pointing out that an rcsid is "a + * variable accessed in a way not obvious to the compiler", so should + * be called volatile. Amazing - a use for const volatile... + */ +#ifndef RCSID /* define RCSID(x) to nothing if don't want the rcs headers */ +# ifndef lint +# define RCSID(x) static const volatile char *rcsid = x ; +# else +# define RCSID(x) +# endif +#endif + +#endif /* __DEFS_H__ */ /* Do not add anything after this line */ diff --git a/lib/libmalloc/dumpheap.c b/lib/libmalloc/dumpheap.c new file mode 100644 index 000000000000..e75ba8e8f279 --- /dev/null +++ b/lib/libmalloc/dumpheap.c @@ -0,0 +1,107 @@ +/* Author: Mark Moraes <moraes@csri.toronto.edu> */ + +/*LINTLIBRARY*/ + +#include "defs.h" +#include "globals.h" + +RCSID("$Id: dumpheap.c,v 1.1 1994/03/06 22:59:30 nate Exp $") + +/* + * Same as malloc_verify except that it prints the heap as it goes + * along. Some would argue that the printout routine should not have + * the ASSERTS, and should print a corrupt heap as well. + * Unfortunately, if any of those ASSERTs is false, this routine could + * wander off into the sunset because of corrupt tags. I have relaxed + * the tests for free list pointers because this routine doesn't need + * them so it just whines + */ +void +mal_heapdump(fd) +FILE *fd; +{ + REGISTER Word *ptr; + REGISTER Word *blk; + REGISTER Word *blkend; + char buf[512]; /* long enough for the sprintfs below */ + + if (_malloc_loword == NULL) { /* Nothing malloc'ed yet */ + (void) fputs("Null heap - nothing malloc'ed yet\n", fd); + return; + } + + (void) fputs("Heap printout:\n", fd); + (void) sprintf(buf, "Rover pointer is 0x%lx\n", (ulong) _malloc_rover); + (void) fputs(buf, fd); + if(!(_malloc_rover == NULL + || PTR_IN_HEAP(_malloc_rover) + || VALID_END_SIZE_FIELD(_malloc_rover) + || VALID_NEXT_PTR(_malloc_rover) + || VALID_PREV_PTR(_malloc_rover))) + (void) fputs("corrupt Rover pointer\n", fd); + for(ptr = _malloc_mem; ptr != NULL; ptr = ptr->next) { + /* print the arena */ + (void) sprintf(buf, "Arena from 0x%lx to 0x%lx, %lu (0x%lx) words\n", + (ulong) ptr, (ulong) (ptr + SIZE(ptr+1)), + (ulong) SIZE(ptr+1)+1, (ulong) SIZE(ptr+1)+1); + (void) fputs(buf, fd); + (void) sprintf(buf, "Next arena is 0x%lx\n", (ulong)ptr->next); + (void) fputs(buf, fd); + (void) fflush(fd); + ASSERT(SIZEFIELD(ptr+1) == SIZEFIELD(ptr + SIZE(ptr+1)), + "corrupt malloc arena"); + blkend = ptr + SIZE(ptr + 1); + for(blk = ptr + ARENASTART; blk < blkend; blk += SIZE(blk)) { + (void) sprintf(buf, " %s blk: 0x%lx to 0x%lx, %lu (0x%lx) words", + TAG(blk) == FREE ? "Free" : "Allocated", + (ulong) blk, (ulong) (blk+SIZE(blk)-1), + (ulong) SIZE(blk), (ulong) SIZE(blk)); + (void) fputs(buf, fd); + (void) fflush(fd); + ASSERT(PTR_IN_HEAP(blk), "corrupt pointer encountered"); + if (TAG(blk) == FREE) { + int i, n; + char *cp; + + (void) sprintf(buf, " next=0x%lx, prev=0x%lx\n", + (ulong) NEXT(blk + FREESIZE(blk) - 1), + (ulong) PREV(blk + FREESIZE(blk) - 1)); + (void) fputs(buf, fd); + /* Make sure free block is filled with FREEMAGIC */ + n = (SIZE(blk) - FREE_OVERHEAD) * + sizeof(Word); + cp = (char *) (blk + FREEHEADERWORDS); +#ifdef DEBUG + for (i = 0; i < n; i++, cp++) { + if (*cp != FREEMAGIC) { + (void) fputs( + " ** free block changed after being freed.\n", fd); + break; + } + } +#endif + } else { +#ifdef DEBUG + (void) sprintf(buf, " really %lu bytes\n", (ulong) REALSIZE(blk)); + (void) fputs(buf, fd); +#else + (void) fputs("\n", fd); +#endif + } + (void) fflush(fd); + ASSERT(VALID_START_SIZE_FIELD(blk), + "corrupt SIZE field encountered in mal_dumpheap()"); + if (TAG(blk) == FREE) { + if( ! VALID_NEXT_PTR(blk + FREESIZE(blk) - 1)) + (void) fputs(" ** bad next pointer\n", fd); + if( ! VALID_PREV_PTR(blk + FREESIZE(blk) - 1)) + (void) fputs(" ** bad prev pointer\n", fd); + } else { + if ( ! VALID_MAGIC(blk)) + (void) fputs(" ** end of block overwritten\n", fd); + } + } + } + (void) fputs("==============\n", fd); + (void) fflush(fd); +} diff --git a/lib/libmalloc/emalloc.c b/lib/libmalloc/emalloc.c new file mode 100644 index 000000000000..13a7b9ab0244 --- /dev/null +++ b/lib/libmalloc/emalloc.c @@ -0,0 +1,69 @@ +/* Author: Mark Moraes <moraes@csri.toronto.edu> */ + +/*LINTLIBRARY*/ + +#include "defs.h" +#include "globals.h" + +RCSID("$Id: emalloc.c,v 1.1 1994/03/06 22:59:31 nate Exp $") + +/* + * malloc which dies if it can't allocate enough storage. + */ +univptr_t +emalloc(nbytes) +size_t nbytes; +{ + univptr_t cp = malloc(nbytes); + + if (cp == 0) { + (void) fputs("No more memory for emalloc\n", stderr); +#ifdef DEBUG + (void) fflush(stderr); + (void) fflush(_malloc_statsfile); + abort(); +#else + exit(EXIT_FAILURE); +#endif + } + + return(cp); +} + +/* + * realloc which dies if it can't allocate enough storage. + */ +univptr_t +erealloc(ptr, nbytes) +univptr_t ptr; +size_t nbytes; +{ + univptr_t cp = realloc(ptr, nbytes); + + if (cp == 0) { + (void) fputs("No more memory for erealloc\n", stderr); +#ifdef DEBUG + (void) fflush(stderr); + (void) fflush(_malloc_statsfile); + abort(); +#else + exit(EXIT_FAILURE); +#endif + } + + return(cp); +} + +/* + * calloc which dies if it can't allocate enough storage. + */ +univptr_t +ecalloc(nelem, sz) +size_t nelem, sz; +{ + size_t nbytes = nelem * sz; + univptr_t cp = emalloc(nbytes); + + (void) memset((univptr_t) cp, 0, (memsize_t) nbytes); + return(cp); +} diff --git a/lib/libmalloc/externs.h b/lib/libmalloc/externs.h new file mode 100644 index 000000000000..77c0b19e014c --- /dev/null +++ b/lib/libmalloc/externs.h @@ -0,0 +1,113 @@ +#ifndef EXTERNS_H__ +#define EXTERNS_H__ + +/* Lots of ugliness as we cope with non-standardness */ + +#ifdef STDHEADERS + /* if we have properly prototyped standard headers, use them */ +# include <stdlib.h> +# include <stddef.h> +# include <stdio.h> +# include <string.h> +# include <unistd.h> + +#else /* ! STDHEADERS */ + +/* # include <sys/types.h> */ +#define caddr_t char * + +/* + * Malloc definitions from General Utilities <stdlib.h>. Note that we + * disagree with Berkeley Unix on the return type of free/cfree. + */ +extern univptr_t malloc proto((size_t)); +extern univptr_t calloc proto((size_t, size_t)); +extern univptr_t realloc proto((univptr_t, size_t)); +extern void free proto((univptr_t)); + +/* General Utilities <stdlib.h> */ + +extern void abort proto((void)); +extern void exit proto((int)); +extern char *getenv proto((const char *)); + +/* + * Input/Output <stdio.h> Note we disagree with Berkeley Unix on + * sprintf(). + */ + +#if 0 /* can't win with this one */ +extern int sprintf proto((char *, const char *, ...)); +#endif + +extern int fputs proto((const char *, FILE *)); +extern int fflush proto((FILE *)); +extern int setvbuf proto((FILE *, char *, int, memsize_t)); + +/* Character Handling: <string.h> */ + +extern univptr_t memset proto((univptr_t, int, memsize_t)); + +#ifndef __GNUC__ /* clash with builtin, garn */ +extern univptr_t memcpy proto((univptr_t, const univptr_t, memsize_t)); +#endif + +extern char *strcpy proto((char *, const char *)); +extern memsize_t strlen proto((const char *)); + +/* UNIX -- unistd.h */ +extern int write proto((int /*fd*/, const char * /*buf*/, int /*nbytes*/)); +extern int open proto((const char */*path*/, int /*flags*/, ...)); + +#endif /* STDHEADERS */ + +#ifdef _SC_PAGESIZE /* Solaris 2.x, SVR4? */ +# define getpagesize() sysconf(_SC_PAGESIZE) +#else /* ! _SC_PAGESIZE */ +# ifdef _SC_PAGE_SIZE /* HP, IBM */ +# define getpagesize() sysconf(_SC_PAGE_SIZE) +# else /* ! _SC_PAGE_SIZE */ +# ifndef getpagesize + extern int getpagesize proto((void)); +# endif /* getpagesize */ +# endif /* _SC_PAGE_SIZE */ +#endif /* _SC_PAGESIZE */ + +extern caddr_t sbrk proto((int)); + +/* Backwards compatibility with BSD/Sun -- these are going to vanish one day */ +extern univptr_t valloc proto((size_t)); +extern univptr_t memalign proto((size_t, size_t)); +extern void cfree proto((univptr_t)); + +/* Malloc definitions - my additions. Yuk, should use malloc.h properly!! */ +extern univptr_t emalloc proto((size_t)); +extern univptr_t ecalloc proto((size_t, size_t)); +extern univptr_t erealloc proto((univptr_t, size_t)); +extern char *strdup proto((const char *)); +extern char *strsave proto((const char *)); +extern void mal_debug proto((int)); +extern void mal_dumpleaktrace proto((FILE *)); +extern void mal_heapdump proto((FILE *)); +extern void mal_leaktrace proto((int)); +extern void mal_mmap proto((char *)); +extern void mal_sbrkset proto((int)); +extern void mal_slopset proto((int)); +extern void mal_statsdump proto((FILE *)); +extern void mal_setstatsfile proto((FILE *)); +extern void mal_trace proto((int)); +extern int mal_verify proto((int)); + +/* Internal definitions */ +extern int __nothing proto((void)); +extern univptr_t _mal_sbrk proto((size_t)); +extern univptr_t _mal_mmap proto((size_t)); + +#ifdef HAVE_MMAP +extern int madvise proto((caddr_t, size_t, int)); +#ifndef __FreeBSD__ +extern caddr_t mmap proto((caddr_t, size_t, int, int, int, off_t)); +#endif /* __FreeBSD__ */ +#endif /* HAVE_MMAP */ + +#endif /* EXTERNS_H__ */ /* Do not add anything after this line */ diff --git a/lib/libmalloc/getmem.c b/lib/libmalloc/getmem.c new file mode 100644 index 000000000000..4140c6da4cc3 --- /dev/null +++ b/lib/libmalloc/getmem.c @@ -0,0 +1,108 @@ +/* Author: Mark Moraes <moraes@csri.toronto.edu> */ + +/*LINTLIBRARY*/ + +#include "defs.h" +#include "globals.h" + +RCSID("$Id: getmem.c,v 1.1 1994/03/06 22:59:42 nate Exp $") + +/* gets memory from the system via the sbrk() system call. Most Un*xes */ +univptr_t +_mal_sbrk(nbytes) +size_t nbytes; +{ + return sbrk((int) nbytes); +} + +/* + * gets memory from the system via mmaping a file. This was written for SunOS + * versions greater than 4.0. The filename is specified by the environment + * variable CSRIMALLOC_MMAPFILE or by the call to mal_mmapset(). Using this + * instead of sbrk() has the advantage of bypassing the swap system, allowing + * processes to run with huge heaps even on systems configured with small swap + * space. + */ +static char *mmap_filename; + +#ifdef HAVE_MMAP +/* Sun gets size_t wrong, and these follow, thanks to my #defines! */ +#undef caddr_t +#undef size_t +#undef u_char +#include <sys/types.h> +#include <sys/mman.h> +#include <sys/stat.h> +#include <sys/file.h> + +univptr_t +_mal_mmap(nbytes) +size_t nbytes; +{ + static struct { + int i_fd; + caddr_t i_data; + caddr_t i_end; + size_t i_size; + size_t i_alloced; + } mmf; + struct stat stbuf; + + if (mmf.i_data != NULL) { + /* Already initialized & mmaped the file */ + univptr_t p = mmf.i_data + mmf.i_alloced; + + if ((char *) p + nbytes > mmf.i_end) { + errno = ENOMEM; + return (univptr_t) -1; + } + mmf.i_alloced += nbytes; + return p; + } + + /* + * This code is run the first time the function is called, it opens + * the file and mmaps the + */ + if (mmap_filename == NULL) { + mmap_filename = getenv("CSRIMALLOC_MMAPFILE"); + if (mmap_filename == NULL) { + errno = ENOMEM; + return (univptr_t) -1; + } + } + + mmf.i_fd = open(mmap_filename, O_RDWR, 0666); + if (mmf.i_fd < 0 || fstat(mmf.i_fd, &stbuf) < 0) + return (univptr_t) -1; + if (stbuf.st_size < nbytes) { + errno = ENOMEM; + return (univptr_t) -1; + } + mmf.i_size = stbuf.st_size; + mmf.i_data = mmap((caddr_t) 0, mmf.i_size, PROT_READ|PROT_WRITE, + MAP_SHARED, mmf.i_fd, (off_t) 0); + if (mmf.i_data == (caddr_t) -1) + return (univptr_t) -1; + mmf.i_end = mmf.i_data + mmf.i_size; + mmf.i_alloced = nbytes; + /* Advise vm system of random access pattern */ + (void) madvise(mmf.i_data, mmf.i_size, MADV_RANDOM); + return mmf.i_data; +} +#else /* !HAVE_MMAP */ +univptr_t +_mal_mmap(nbytes) +size_t nbytes; +{ + return (univptr_t) -1; +} +#endif /* HAVE_MMAP */ + +void +mal_mmap(fname) +char *fname; +{ + _malloc_memfunc = _mal_mmap; + mmap_filename = fname; +} diff --git a/lib/libmalloc/globals.c b/lib/libmalloc/globals.c new file mode 100644 index 000000000000..b1adf3d3f5a2 --- /dev/null +++ b/lib/libmalloc/globals.c @@ -0,0 +1,87 @@ +/* Author: Mark Moraes <moraes@csri.toronto.edu> */ + +/* + * All globals are names starting with _malloc, which should not clash + * with anything else. + */ +/* + * Remember to initialize the variable in globals.c if you want, and + * provide an alternative short name in globrename.h + */ +#include "globrename.h" +#include "version.c" + +/* + * _malloc_minchunk is the minimum number of units that a block can be + * cut down to. If the difference between the required block size, and + * the first available block is greater than _malloc_minchunk, the + * block is chopped into two pieces, else the whole block is returned. + * The larger this is, the less fragmentation there will be, but the + * greater the waste. The actual minimum size of a block is therefore + * _malloc_minchunk*sizeof(Word) This consists of one word each for the + * boundary tags, one for the next and one for the prev pointers in a + * free block. + */ +size_t _malloc_minchunk = FIXEDOVERHEAD; + +/* + * _malloc_rover is the pointer that points 'someplace' in the free + * list. We start our search for a block from _malloc_rover, thus + * starting the search at a different place everytime, rather than at + * the start of the list. This improves performance considerably, sez + * Knuth + */ +Word *_malloc_rover = NULL; +Word *_malloc_hiword = NULL; +Word *_malloc_loword = NULL; + +/* + * _malloc_sbrkunits is the multiple of sizeof(Word) to actually use in + * sbrk() calls - _malloc_sbrkunits should be large enough that sbrk + * isn't called too often, but small enough that any program that + * mallocs a few bytes doesn't end up being very large. I've set it to + * 1K resulting in a sbrk'ed size of 8K. This is (coincidentally!) the + * pagesize on Suns. I think that this seems a reasonable number for + * modern programs that malloc heavily. For small programs, you may + * want to set it to a lower number. + */ +size_t _malloc_sbrkunits = DEF_SBRKUNITS; + +/* + * optimization of keeping total amount available, so we know to sbrk + * without searching list. No point searching list unless we have a + * fair chance of success. Ideally, we'd keep the size of the largest + * block available and a pointer to it, so we could check definitely if + * we had enough space. But that is too much housekeeping - we'd have to + * update that on all mallocs and frees too. (Updating + * _malloc_totalavail is easier) + */ +size_t _malloc_totalavail = 0; + +Word *_malloc_mem = NULL; + +/* + * Do not call any output routine other than fputs() - use sprintf() if + * you want to format something before printing. We don't want stdio + * calling malloc() if we can help it + */ +int _malloc_tracing = 0; /* No tracing */ +FILE *_malloc_statsfile = stderr; +char _malloc_statsbuf[128]; + +int _malloc_leaktrace = 0; + +#ifdef PROFILESIZES +int _malloc_scount[MAXPROFILESIZE]; +#endif /* PROFILESIZES */ + +#ifdef DEBUG +/* + * 0 or 1 means checking all pointers before using them. Reasonably + * thorough. 2 means check the entire heap on every call to + * malloc/free/realloc/memalign. (the rest call these) + */ +int _malloc_debugging = 0; +#endif /* DEBUG */ + +univptr_t (* _malloc_memfunc) proto((size_t)) = _mal_sbrk; diff --git a/lib/libmalloc/globals.h b/lib/libmalloc/globals.h new file mode 100644 index 000000000000..4d3327edd81f --- /dev/null +++ b/lib/libmalloc/globals.h @@ -0,0 +1,43 @@ +/* $Id: globals.h,v 1.1 1994/03/06 22:59:44 nate Exp $ */ +#ifndef __GLOBALS_H__ +#define __GLOBALS_H__ +/* + * Remember to initialize the variable in globals.c if you want, and + * provide an alternative short name in globrename.h + */ +#include "globrename.h" + +extern size_t _malloc_minchunk; + +extern Word *_malloc_rover; +extern Word *_malloc_hiword; +extern Word *_malloc_loword; + +extern size_t _malloc_sbrkunits; + +extern size_t _malloc_totalavail; + +extern Word *_malloc_mem; + +extern int _malloc_tracing; /* No tracing */ +extern FILE *_malloc_statsfile; +extern char _malloc_statsbuf[]; + +extern int _malloc_leaktrace; + +#ifdef PROFILESIZES +extern int _malloc_scount[]; +#endif /* PROFILESIZES */ + +#ifdef DEBUG +/* + * 0 or 1 means checking all pointers before using them. Reasonably + * thorough. 2 means check the entire heap on every call to + * malloc/free/realloc/memalign. (the rest call these) + */ +extern int _malloc_debugging; +#endif /* DEBUG */ + +extern univptr_t (* _malloc_memfunc) proto((size_t)); + +#endif /* __GLOBALS_H__ */ /* Do not add anything after this line */ diff --git a/lib/libmalloc/globrename.h b/lib/libmalloc/globrename.h new file mode 100644 index 000000000000..9739f4f3ac6a --- /dev/null +++ b/lib/libmalloc/globrename.h @@ -0,0 +1,46 @@ +/* $Id: globrename.h,v 1.1 1994/03/06 22:59:45 nate Exp $ */ +#ifndef __GLOBALRENAME_H__ +#define __GLOBALRENAME_H__ +/* + * Renaming all external symbols that are internal to the malloc to be + * unique within 6 characters for machines whose linkers just can't keep + * up. We hope the cpp is smart enough - if not, get GNU cccp or the + * cpp that comes with X Windows Version 11 Release 3. + */ +#ifdef SHORTNAMES +#define _malloc_minchunk __MAL1_minchunk + +#define _malloc_rover __MAL2_rover +#define _malloc_hiword __MAL3_hiword +#define _malloc_loword __MAL4_loword + +#define _malloc_sbrkunits __MAL5_sbrkunits + +#define _malloc_totalavail __MAL6_totalavail + +#define _malloc_mem __MAL7_mem + +#define _malloc_tracing __MAL8_tracing +#define _malloc_statsfile __MAL9_statsfile +#define _malloc_statsbuf __MALA_statsbuf + +#define _malloc_leaktrace __MALB_leaktrace + +#ifdef PROFILESIZES +#define _malloc_scount __MALC_scount +#endif /* PROFILESIZES */ + +#ifdef DEBUG +/* + * 0 or 1 means checking all pointers before using them. Reasonably + * thorough. 2 means check the entire heap on every call to + * malloc/free/realloc/memalign. (the rest call these) + */ +#define _malloc_debugging __MALD_debugging +#endif /* DEBUG */ +#define _malloc_version __MALE_version + +#define _malloc_memfunc __MALF_memfunc + +#endif /* SHORTNAMES */ /* Do not add anything after this line */ +#endif /* __GLOBALRENAME_H__ */ /* Do not add anything after this line */ diff --git a/lib/libmalloc/leak.c b/lib/libmalloc/leak.c new file mode 100644 index 000000000000..b4014582b32e --- /dev/null +++ b/lib/libmalloc/leak.c @@ -0,0 +1,160 @@ +/* Author: Mark Moraes <moraes@csri.toronto.edu> */ + +/*LINTLIBRARY*/ + +#include "defs.h" +#include "globals.h" +#include "sptree.h" + +RCSID("$Id: leak.c,v 1.1 1994/03/06 22:59:46 nate Exp $") + +/* + * These routines provide an interface for tracing memory leaks. The + * user can turn on leak tracing at any time by calling + * mal_leaktrace(1), after which every block allocated by + * _malloc()/_calloc()/_realloc()/_valloc()/_memalign() has a string + * (containing the filename and linenumber of the routine invoking it) + * stored in a database. When _free()/_cfree() is called on that block, + * the record is deleted from the database. The user can call + * mal_dumpleaktrace() to show the list of blocks allocated, and + * where they were allocated. The location of leaks can usually be + * detected from this. + */ +/* + * The tree implementation used to store the blocks is a splay-tree, + * using an implementation in C by Dave Brower (daveb@rtech.uucp), + * translated from Douglas Jones' original Pascal. However, any data + * structure that permits insert(), delete() and traverse()/apply() of + * key, value pairs should be suitable. Only this file needs to be + * changed. + */ +static SPTREE *sp = NULL; + +/* + * num is a sequence number, incremented for ever block. min_num gets + * set to num after every dumpleaktrace - subsequent dumps do not print + * any blocks with sequence numbers less than min_num + */ +static unsigned long min_num = 0; +static unsigned long num = 0; + +/* + * These are used by mal_contents to count number of allocated blocks and the + * number of bytes allocated. Better way to do this is to walk the heap + * rather than scan the splay tree. + */ +static unsigned long nmallocs; +static unsigned long nbytes; + +static FILE *dumpfd = NULL; + +/* + * Turns recording of FILE and LINE number of each call to + * malloc/free/realloc/calloc/cfree/memalign/valloc on (if value != 0) + * or off, (if value == 0) + */ +void +mal_leaktrace(value) +int value; +{ + _malloc_leaktrace = (value != 0); + if (sp == NULL) + sp = __spinit(); +} + +/* + * The routine which actually does the printing. I know it is silly to + * print address in decimal, but sort doesn't read hex, so sorting the + * printed data by address is impossible otherwise. Urr. The format is + * FILE:LINE: sequence_number address_in_decimal (address_in_hex) + */ +void +__m_prnode(spblk) +SPBLK *spblk; +{ + if ((unsigned long) spblk->datb < min_num) + return; + (void) sprintf(_malloc_statsbuf, "%s%8lu %8lu(0x%08lx)\n", + (char *) spblk->data, (unsigned long) spblk->datb, + (unsigned long) spblk->key, (unsigned long) spblk->key); + (void) fputs(_malloc_statsbuf, dumpfd); +} + +/* + * Dumps all blocks which have been recorded. + */ +void +mal_dumpleaktrace(fd) +FILE *fd; +{ + dumpfd = fd; + __spscan(__m_prnode, (SPBLK *) NULL, sp); + (void) fflush(dumpfd); + min_num = num; +} + +/* + * Inserts a copy of a string keyed by the address addr into the tree + * that stores the leak trace information. The string is presumably of + * the form "file:linenumber:". It also stores a sequence number that + * gets incremented with each call to this routine. + */ +void +__m_install_record(addr, s) +univptr_t addr; +const char *s; +{ + num++; + (void) __spadd(addr, strsave(s), (char *) num, sp); +} + +/* Deletes the record keyed by addr if it exists */ +void +__m_delete_record(addr) +univptr_t addr; +{ + SPBLK *result; + + if ((result = __splookup(addr, sp)) != NULL) { + free(result->data); + result->data = 0; + __spdelete(result, sp); + } +} + +void +__m_count(spblk) +SPBLK *spblk; +{ + Word *p; + + nmallocs++; + p = (Word *) spblk->key; + p -= HEADERWORDS; + + /* A little paranoia... */ + ASSERT(PTR_IN_HEAP(p), "bad pointer seen in __m_count"); + ASSERT(TAG(p) != FREE, "freed block seen in __m_count"); + ASSERT(VALID_START_SIZE_FIELD(p), "corrupt block seen in __m_count"); + ASSERT(VALID_MAGIC(p), "block with end overwritten seen in __m_count"); + + nbytes += SIZE(p) * sizeof(Word); + return; +} + +void +mal_contents(fp) +FILE *fp; +{ + void __m_count proto((SPBLK *)); + + nmallocs = 0; + nbytes = 0; + __spscan(__m_count, (SPBLK *) NULL, sp); + (void) sprintf(_malloc_statsbuf, + "%% %lu bytes %lu mallocs %lu available %lu vm\n", + nbytes, nmallocs, (ulong) _malloc_totalavail, + (ulong) sbrk(0)); + (void) fputs(_malloc_statsbuf, fp); + (void) fflush(fp); +} diff --git a/lib/libmalloc/malloc.c b/lib/libmalloc/malloc.c new file mode 100644 index 000000000000..354520ac3da4 --- /dev/null +++ b/lib/libmalloc/malloc.c @@ -0,0 +1,622 @@ +/* Author: Mark Moraes <moraes@csri.toronto.edu> */ + +/*LINTLIBRARY*/ + +#include "defs.h" +#include "globals.c" + +RCSID("$Id: malloc.c,v 1.1 1994/03/06 22:59:47 nate Exp $") + +static int +grabhunk(nwords) +size_t nwords; +{ + univptr_t cp; + size_t morecore; + Word *ptr; + size_t sbrkwords; + size_t blksize; + static char *spare; + static int nspare; + + /* + * two words for fake boundary tags for the entire block, and one + * for the next ptr of the block. + */ +#define EXCESS 3 + sbrkwords = (size_t) (((nwords + EXCESS) / _malloc_sbrkunits + 1) * + _malloc_sbrkunits); + morecore = sbrkwords * sizeof(Word) + SBRKEXTRA; + if ((cp = (* _malloc_memfunc)(morecore)) == (univptr_t) -1) + return(0); + /* + * Should first GUARANTEE that what sbrk returns is aligned to + * Word boundaries - see align.h. Unfortunately, to guarantee + * that the pointer returned by sbrk is aligned on a word + * boundary, we must ask for sizeof(Word) -1 extra bytes, since + * we have no guarantee what other sbrk'ed blocks exist. (Sun + * sbrk always returns an aligned value, that is another story!) + * We use spare and nspare to keep track of the bytes wasted, so + * that we can try and reuse them later. If no other sbrk()s are + * called, then nspare rotates through the values 3, 2, 1, 0, + * and the first branch of the if() is always taken. + */ + if ((spare + nspare) == (char *) cp) { + ptr = (Word *) SBRKALIGN(spare); + morecore += nspare; + sbrkwords = morecore / sizeof(Word); + } else { + ptr = (Word *) SBRKALIGN(cp); + morecore -= (char *) ptr - (char *) cp; + } + spare = (char *) (ptr + sbrkwords); + nspare = (morecore - sbrkwords * sizeof(Word)); + _malloc_totalavail += sbrkwords; + PRTRACE(sprintf(_malloc_statsbuf, "sbrk %lu\n", + (ulong) sbrkwords*sizeof(Word))); + + /* + * Here we need to check if it adjoins the _malloc_hiword. If it + * does, then _malloc_hiword need not be a fake boundary tag any + * longer, (its a real one) and the higher end of the block we + * sbrk'ed is the fake tag. So we tag it appropriately, make + * the start of the block point to the old _malloc_hiword, and free it. + * If we aren't next to _malloc_hiword, then someone else sbrk'ed in + * between, so we can't coalesce over the boundary anyway, in + * which case we just change _malloc_hiword to be in the new sbrk'ed + * block without damaging the old one. And we free the block. + */ + if (ptr != _malloc_hiword + 1 || _malloc_rover == NULL) { + /* Non-contiguous sbrk'ed block, or first sbrk we've done. */ + /* + * First push this block on the stack of non-contiguous blocks + * we've sbrked. !! For real paranoia, we'd also check + * _malloc_mem... + */ + REGISTER Word *tmp = _malloc_mem; + + _malloc_mem = ptr; + ptr->next = tmp; + ptr++; + sbrkwords--; + + _malloc_hiword = ptr; + if (_malloc_loword == NULL || _malloc_loword > ptr) { + /* First time - set lower bound. */ + PRTRACE(sprintf(_malloc_statsbuf, "heapstart 0x%lx\n", + (ulong) ptr)); + _malloc_loword = ptr; + } + /* + * Fake boundary tags to indicate the ends of an arena. Since they + * are marked as allocated, no attempt will be made to coalesce + * before or after them. + */ + SIZEFIELD(ptr) = ALLOCED | sbrkwords; + _malloc_hiword += sbrkwords - 1; + PRTRACE(sprintf(_malloc_statsbuf, "heapend 0x%lx\n", + (ulong) _malloc_hiword)); + SIZEFIELD(_malloc_hiword) = ALLOCED | sbrkwords; + + ptr++; + /* + * The 2 we subtract are the special arena end tags, which is + * why we don't use HEADERWORDS and TRAILERWORDS + */ + sbrkwords -= 2; + SIZEFIELD(ptr) = FREEMASK(sbrkwords); + DMEMSET(ptr + FREEHEADERWORDS, sbrkwords - FREE_OVERHEAD); + ptr = _malloc_hiword - 1; + SIZEFIELD(ptr) = FREEMASK(sbrkwords); + /* links */ + if (_malloc_rover == NULL) { + /* Only block in free list - links point to itself */ + NEXT(ptr) = ptr; + PREV(ptr) = ptr; + } else { + /* + * Non-contiguous sbrk - insert into free list. No + * point calling free() because we know this cannot be + * coalesced + */ + NEXT(ptr) = _malloc_rover; + tmp = PREV(_malloc_rover); + PREV(ptr) = tmp; /* PREV(ptr) = PREV(_malloc_rover); */ + NEXT(tmp) = ptr; /* NEXT(PREV(_malloc_rover)) = ptr; */ + PREV(_malloc_rover) = ptr; + } + _malloc_rover = ptr; + return(1); + } + /* Set boundary tags and size */ + ptr--; + blksize = SIZE(ptr) + sbrkwords; + SIZEFIELD(ptr) = ALLOCMASK(sbrkwords); + _malloc_hiword += sbrkwords; + SIZEFIELD(_malloc_hiword-1) = SIZEFIELD(ptr); + /* Update fake end tags of the memory chunk */ + SIZEFIELD(_malloc_hiword) = ALLOCMASK(blksize); + SIZEFIELD(_malloc_hiword - blksize + 1) = ALLOCMASK(blksize); + SET_REALSIZE(ptr, (sbrkwords - ALLOC_OVERHEAD) * sizeof(Word)); + free((univptr_t) (ptr + HEADERWORDS)); + return(1); +} + +univptr_t +malloc(nbytes) +size_t nbytes; +{ + REGISTER Word *start, *search; + REGISTER Word *p; + REGISTER size_t required; + REGISTER size_t searchsize; + REGISTER size_t rest; + size_t roversize; + +#ifndef BUGCOMPATIBILITY + ASSERT(nbytes != 0, "What do you expect when you malloc(0)?!!"); + if (nbytes == 0) { /* If we're debugging, then we died on the ASSERT */ + errno = EINVAL; + return(NULL); + } +#endif /* BUGCOMPATIBILITY */ + + required = ALLOC_OVERHEAD + (nbytes + sizeof(Word) - 1) / + sizeof(Word); + if (required < (size_t) _malloc_minchunk) + required = _malloc_minchunk; + search = _malloc_rover; + if (!search || required > _malloc_totalavail) { + /* Not enough memory in free list - allocate enough memory. */ + if (grabhunk(required) == 0) { + errno = ENOMEM; + return( NULL); + } + search = _malloc_rover; + } + + ASSERT(PTR_IN_HEAP(_malloc_rover), "corrupt rover pointer in malloc()"); + ASSERT(VALID_END_SIZE_FIELD(_malloc_rover), "corrupt block in malloc()"); + ASSERT(VALID_NEXT_PTR(_malloc_rover), "corrupt block in malloc()"); + ASSERT(VALID_PREV_PTR(_malloc_rover), "corrupt block in malloc()"); + CHECKHEAP(); + + roversize = FREESIZE(search); + if (search == _malloc_hiword - 1) { /* avoid wilderness */ + search = NEXT(search); +#if 0 + { + char buf[1024]; + sprintf(buf, "wilderness = 0x%x, skipping to 0x%x\n", + _malloc_hiword - 1, search); + fputs(buf, stderr); + } +#endif + } + start = search; + do { + ASSERT(PTR_IN_HEAP(search), "corrupt pointer in malloc()"); + ASSERT(VALID_END_SIZE_FIELD(search), "corrupt pointer in malloc()"); + ASSERT(VALID_NEXT_PTR(search), "corrupt pointer in malloc()"); + ASSERT(VALID_PREV_PTR(search), "corrupt pointer in malloc()"); + searchsize = FREESIZE(search); + if (searchsize >= required) { + break; + } else { + search = NEXT(search); + } + } while (search != start); + + if (searchsize < required) { + if (grabhunk(required) == 0) { + errno = ENOMEM; + return( NULL); + } + /* + * We made sure in grabhunk() or free() that + * _malloc_rover is pointing to the newly sbrked (and + * freed) block. + */ + search = _malloc_rover; + roversize = searchsize = FREESIZE(search); + } + rest = searchsize - required; + if (rest >= _malloc_minchunk) { + SIZEFIELD(search) = FREEMASK(rest); + p = search - rest; + SIZEFIELD(p+1) = FREEMASK(rest); + SIZEFIELD(p) = ALLOCMASK(required); + p -= required - 1; + SIZEFIELD(p) = ALLOCMASK(required); + _malloc_totalavail -= required; + /* keep rover at the larger block */ + if (rest > roversize) + _malloc_rover = search; + } else { + /* alloc the entire block */ + REGISTER Word *nextp = NEXT(search); + + SIZEFIELD(search) |= ALLOCED; + p = search - searchsize + 1; + SIZEFIELD(p) = SIZEFIELD(search); + if (search == nextp) { + _malloc_rover = NULL; + } else { + REGISTER Word *prevp = PREV(search); + + NEXT(prevp) = nextp; + PREV(nextp) = prevp; + /* keep rover at the larger block, unless we just allocated rover*/ + if (search == _malloc_rover || FREESIZE(nextp) > roversize) + _malloc_rover = nextp; + } + _malloc_totalavail -= searchsize; + } + PRTRACE(sprintf(_malloc_statsbuf, "+ %lu %lu 0x%lx\n", (ulong) nbytes, + (ulong) (SIZE(p) - ALLOC_OVERHEAD) * sizeof(Word), + (ulong) (p + HEADERWORDS))); + COUNTSIZE(SIZE(p)); + SET_REALSIZE(p, nbytes); + return((univptr_t) (p + HEADERWORDS)); +} + + + +void +free(cp) +univptr_t cp; +{ + /* + * This is where the boundary tags come into their own. The + * boundary tag guarantees a constant time insert with full + * coalescing (the time varies slightly for the four case possible, + * but still, essentially a very fast free. + */ + /* + * P0 is the block being freed. P1 is the pointer to the block + * before the block being freed, and P2 is the block after it. + * We can either coalesce with P1, P2, both, or neither + */ + REGISTER Word *p0, *p1, *p2; + + if (cp == NULL) + return; + + p0 = (Word *) cp; + p0 -= HEADERWORDS; + + /* A little paranoia... */ + ASSERT(PTR_IN_HEAP(p0), "bad pointer passed to free()"); + ASSERT(TAG(p0) != FREE, "freed block passed to free()"); + ASSERT(VALID_START_SIZE_FIELD(p0), "corrupt block passed to free()"); + ASSERT(VALID_MAGIC(p0), "block with end overwritten passed to free()"); + /* With debugging, the assert would have already aborted */ + if (TAG(p0) == FREE) { + errno = EINVAL; + return; + } + + /* + * clear the entire block that used to be p0's, just in case someone + * tries to refer to it or anything in it again. We leave the end tags + * alone for now - we'll smash them individually depending on the way p0 + * merges with p1 and/or p2. + */ + DMEMSET(p0 + FREEHEADERWORDS, SIZE(p0) - FREE_OVERHEAD); + PRTRACE(sprintf(_malloc_statsbuf, "- %lu 0x%lx\n", + (ulong) (SIZE(p0) - ALLOC_OVERHEAD) * sizeof(Word), + (ulong) (p0 + HEADERWORDS))); + _malloc_totalavail += SIZE(p0); + + p1 = p0 - 1; + /* + * p0 now points to the end of the block -- we start treating it as + * a free block + */ + p0 += SIZE(p0) - 1; + p2 = p0 + 1; + + /* + * More paranoia.... We can't match the SIZEFIELDs of p1/p2 with + * p1/p2 + SIZE(p1/p2) -1 because they might be a fake tag to + * indicate the bounds of the arena. Further, we should only check + * p1 if p0-1 is not the _malloc_loword or an arena bound - else p1 is + * probably not a valid pointer. If tag p0-1 is allocated, then it + * could be an arena bound. + */ + + if (TAG(p2) == FREE) { + /* + * Aha - block which is physically after p0 is free. + * Merging with it merely means increasing its size to + * incorporate the block being freed - no pointer + * shuffling. + */ + p2 += FREESIZE(p2) - 1; + ASSERT(PTR_IN_HEAP(p2), "corrupt block in free()"); + ASSERT(TAG(p2)==FREE, "corrupt block in free()"); + ASSERT(VALID_END_SIZE_FIELD(p2), "corrupt block in free()"); + ASSERT(VALID_NEXT_PTR(p2), "corrupt block in free()"); + ASSERT(VALID_PREV_PTR(p2), "corrupt block in free()"); + + SIZEFIELD(p2) = FREEMASK(FREESIZE(p2) + SIZE(p0)); + SIZEFIELD(p2 - FREESIZE(p2) + 1) = SIZEFIELD(p2); + /* + * Smash p0's old end tag and p2's old start tag. + */ + DMEMSET(p0 - FREETRAILERWORDS + 1, FREETRAILERWORDS + FREEHEADERWORDS); + p0 = p2; /* p0 just vanished - became part of p2 */ + } + if (TAG(p1) == FREE) { + /* + * Block that physically precedes p0 in memory is free. Merging + * with it means rearranging the links to because the end of + * the block (the handle it is known by) is now the end of p0 + * rather than itself. So the blocks after and before it in the + * free list need to be told. + */ + REGISTER Word *nextp1, *prevp1; + + ASSERT(PTR_IN_HEAP(p1), "corrupt block in free()"); + ASSERT(VALID_END_SIZE_FIELD(p1), "corrupt block in free()"); + ASSERT(VALID_NEXT_PTR(p1), "corrupt block in free()"); + ASSERT(VALID_PREV_PTR(p1), "corrupt block in free()"); + + /* p0 grows to absorb p1 */ + SIZEFIELD(p0) = FREEMASK(SIZE(p0) + FREESIZE(p1)); + SIZEFIELD(p0 - FREESIZE(p0) + 1) = SIZEFIELD(p0); + nextp1 = NEXT(p1); + prevp1 = PREV(p1); + /* + * We smash the free list pointers in p1 (SIZE, NEXT, PREV) to + * make sure no one refers to them again. We cannot smash the + * start boundary tag because in both cases, it becomes the start + * tag for the new block. We also trash p0's start tag. + */ + DMEMSET(p1 - FREETRAILERWORDS + 1, FREETRAILERWORDS + FREEHEADERWORDS); + if (p0 != p2) { + /* + * Ok - p0 coalesced with the block physically + * before it (p1) (which is why we're here, but + * it didn't coalesce with the block after it + * (p2) which is why p0 != p2. So we need to + * insert p0 in the list in place of p1. + */ + + if (nextp1 != p1) { + /* Fix the PREV ptr of the next blk in the list */ + PREV(nextp1) = p0; + /* Fix the NEXT ptr of the previous blk in the list */ + NEXT(prevp1) = p0; + /* Copy the link info from p1 to p0 */ + NEXT(p0) = nextp1; + PREV(p0) = prevp1; + } else { + NEXT(p0) = p0; + PREV(p0) = p0; + } + /* p1 just vanished - became part of p0 */ + _malloc_rover = p0; + CHECKHEAP(); + return; + } else { + /* + * p0 merged with p2, and with p1, which + * essentially means that p2 grows to absorb p1 + * in the free list (bridged by p0). So we + * simply delete p1. Free list reduces by one blk. + */ + /* Fix the PREV ptr of the next blk in the list */ + PREV(nextp1) = prevp1; + /* Fix the NEXT ptr of the previous blk in the list */ + NEXT(prevp1) = nextp1; + } + } + if (p0 != p2) { + /* + * If we're here, it means block P0 didn't coalesce, so + * we need to insert it in the free list - we put it + * before ROVER, and make ROVER point to it. Or it + * means ROVER was NULL, i.e. free list is empty, which + * means we have to take care of the boundary linking + * Free list grows by one. + */ + if (_malloc_rover == NULL) { + /* + * Free list was empty - so we point _malloc_rover at + * the block we're freeing to get a proper + * circular linking. + */ + _malloc_rover = p0; + } else { + ASSERT(PTR_IN_HEAP(_malloc_rover), + "corrupt rover pointer in free()"); + ASSERT(VALID_END_SIZE_FIELD(_malloc_rover), + "corrupt block in free()"); + ASSERT(VALID_NEXT_PTR(_malloc_rover), "corrupt block in free()"); + ASSERT(VALID_PREV_PTR(_malloc_rover), "corrupt block in free()"); + } + NEXT(p0) = _malloc_rover; + PREV(p0) = PREV(_malloc_rover); + PREV(_malloc_rover) = p0; + NEXT(PREV(p0)) = p0; + SIZEFIELD(p0) &= SIZEMASK; /* sets the boundary tag to FREE */ + SIZEFIELD(p0 - FREESIZE(p0) + 1) = SIZEFIELD(p0); + } + _malloc_rover = p0; + + CHECKHEAP(); + return; +} + + + +/* + * WARNING: This realloc() IS *NOT* upwards compatible with the + * convention that the last freed block since the last malloc may be + * realloced. Allegedly, this was because the old free() didn't + * coalesce blocks, and reallocing a freed block would perform the + * compaction. Yuk! + */ +univptr_t +realloc(cp, nbytes) +univptr_t cp; +size_t nbytes; +{ + REGISTER Word *p0 = (Word *) cp; + REGISTER Word *p1; + univptr_t tmp; + REGISTER size_t required; + REGISTER size_t sizep0; + + if (p0 == NULL) + return(malloc(nbytes)); + + if (nbytes == 0) { + free(cp); + return(NULL); + } + + required = ALLOC_OVERHEAD + (nbytes + sizeof(Word) - 1) / + sizeof(Word); + if (required < (size_t) _malloc_minchunk) + required = _malloc_minchunk; + + p0 -= HEADERWORDS; + + /* A little paranoia... */ + ASSERT(PTR_IN_HEAP(p0), "bad pointer passed to realloc()"); + ASSERT(TAG(p0) != FREE, "freed block passed to realloc()"); + ASSERT(VALID_START_SIZE_FIELD(p0), "corrupt block passed to realloc()"); + ASSERT(VALID_MAGIC(p0), "block with end overwritten passed to realloc()"); + /* With debugging, the assert would have already aborted */ + if (TAG(p0) == FREE) { + errno = EINVAL; + return(NULL); + } + sizep0 = SIZE(p0); + if (sizep0 >= required) { + /* Shrinking the block */ + size_t after = sizep0 - required; + + SET_REALSIZE(p0, nbytes); + if (after < _malloc_minchunk) { + /* + * Not enough to free what's left so we return the block + * intact - print no-op for neatness in output. + */ + PRTRACE(strcpy(_malloc_statsbuf, "no-op\n")); + return(cp); + } + SIZEFIELD(p0) = ALLOCMASK(required); + SIZEFIELD(p0 + required - 1) = SIZEFIELD(p0); + p0 += required; + /* + * We free what's after the block - mark it alloced and + * throw it to free() to figure out whether to merge it + * with what follows... + */ + SIZEFIELD(p0) = ALLOCMASK(after); + SIZEFIELD(p0 + after - 1) = SIZEFIELD(p0); + SET_REALSIZE(p0, (after - ALLOC_OVERHEAD) * sizeof(Word)); + free((univptr_t) (p0 + HEADERWORDS)); + return(cp); + } + + /* + * If we get here, then we are growing the block to something + * bigger. If the following block is free and big enough to be + * realloced, then we grow using that block. This resembles the + * malloc code slightly. + */ + p1 = p0 + sizep0; + required -= sizep0; + if (TAG(p1) == FREE) { /* p1 not free, may be an arena bound or hiword */ + ASSERT(PTR_IN_HEAP(p1), "corrupt pointer in realloc()"); + ASSERT(VALID_START_SIZE_FIELD(p1), "corrupt block in realloc()"); + ASSERT(VALID_NEXT_PTR(p1 + FREESIZE(p1) - 1), + "corrupt block in realloc()"); + ASSERT(VALID_PREV_PTR(p1 + FREESIZE(p1) - 1), + "corrupt block in realloc()"); + } + if (TAG(p1) == FREE && FREESIZE(p1) >= required) { + size_t rest = FREESIZE(p1) - required; + REGISTER Word *p; + + if (rest >= _malloc_minchunk) { + sizep0 += required; + SIZEFIELD(p0) = ALLOCMASK(sizep0); + p = p0 + sizep0; + SIZEFIELD(p-1) = SIZEFIELD(p0);; + SIZEFIELD(p) = FREEMASK(rest); + SIZEFIELD(p + rest - 1) = FREEMASK(rest); + _malloc_totalavail -= required; + } else { + /* + * alloc the entire block and merge into p0. Free list + * shrinks by a block + */ + REGISTER Word *nextp1, *prevp1; + + sizep0 += FREESIZE(p1); + SIZEFIELD(p0) = ALLOCMASK(sizep0); + SIZEFIELD(p0 + sizep0 - 1) = SIZEFIELD(p0); + p1 += FREESIZE(p1) - 1; + p = nextp1 = NEXT(p1); + if (p1 == nextp1) { + _malloc_rover = NULL; + } else { + prevp1 = PREV(p1); + PREV(nextp1) = prevp1; + NEXT(prevp1) = nextp1; + _malloc_rover = nextp1; + } + _malloc_totalavail -= SIZE(p1); + } + SET_REALSIZE(p0, nbytes); + CHECKHEAP(); + + PRTRACE(sprintf(_malloc_statsbuf, "++ %lu %lu 0x%lx %lu 0x%lx\n", + (ulong) nbytes, + (ulong) (SIZE(p0)-ALLOC_OVERHEAD)*sizeof(Word), + (ulong) cp, (ulong) SIZE(p)*sizeof(Word), + (ulong) p)); + return(cp); + } + /* Have to do it the hard way */ + tmp = malloc(nbytes); + if (tmp != NULL) { + MEMCPY(tmp, cp, ((SIZE(p0) - ALLOC_OVERHEAD))); + free(cp); + } + return(tmp); +} + + + +/* + * !! Given what we know about alignment, we should be able to do better + * than memset and set words. Hopefully memset has been tuned. + */ +univptr_t +calloc(nelem, elsize) +size_t nelem, elsize; +{ + REGISTER size_t nbytes = nelem * elsize; + REGISTER univptr_t cp = malloc(nbytes); + + if (cp) + (void) memset((univptr_t) cp, 0, (memsize_t) nbytes); + return(cp); +} + + +/* + * Why would anyone want this.... ? + */ +void +cfree(cp) +univptr_t cp; +{ + free(cp); +} diff --git a/lib/libmalloc/malloc.doc b/lib/libmalloc/malloc.doc new file mode 100644 index 000000000000..f209baf5a7bf --- /dev/null +++ b/lib/libmalloc/malloc.doc @@ -0,0 +1,653 @@ +$Header: /home/cvs/386BSD/src/lib/libmalloc/malloc.doc,v 1.1 1994/03/06 22:59:48 nate Exp $ + Yet another malloc() + -------------------- + Mark Moraes + <moraes@csri.toronto.edu> + + Standard calls + +It provides the standard calls we expect from any self-respecting +malloc, viz. + + char * + malloc(nbytes) + + unsigned int nbytes; + +which returns pointer to a contiguous memory block, at least nbytes +bytes long, + + char * + calloc(nelements, element_size) + + unsigned int nelements, element_size; + +which returns a pointer to a contiguous memory block, at least +nelements * element_size bytes long, with all locations set to zero, + + char * + realloc(ptr, nbytes) + + char *ptr; + unsigned int nbytes; + +attempts to change the size of the previously malloc'ed block pointed +to by ptr to nbytes, and failing that, returns a pointer to a new block +nbytes long, after copying the contents of the old block to it. +Realloc returns NULL if it fails, and DOES NOTHING WITH THE OLD BLOCK. +(This is not defined; some reallocs may free the old block they were +passed) + + void + free(ptr) + + char *ptr; + +returns the previously malloc'ed block pointed to by ptr to the +storage pool. It will do its best to keep storage as unfragmented as +possible. + + void + cfree(ptr) + + char *ptr; + +The same as free(), used to free calloc()ed blocks. + +There are a couple of additional functions that Sun malloc provides, +and that some programs need (notably the X Windows server on Suns) + + char * + memalign(alignment, nbytes) + + unsigned int alignment; + unsigned int nbytes; + +This returns a pointer to a memory block at least nbytes long, +guaranteeing that the block starting address is an even multiple of +alignment. Alignment must be a power of 2. + + char * + valloc(nbytes) + + unsigned int nbytes; + +This is the same as memalign(getpagesize(), nbytes). + +A frequently used function is to save a copy of a NULL-terminated +character array (a C string) in storage malloc'ed exactly to fit it, +for example when reading or parsing some input line from a large +buffer. Newer systems provide the strdup() function to do just this. +(This may not appear a complex funtion - using it eliminates the +all-too-frequent error where you forget to add 1 to the length of the +string to allow for the NULL terminator) + + char * + strdup(s) + + char *s; + +strdup returns NULL if the malloc fails. + + Additional functions + +In addition to the usual functions, this malloc provides some +debugging and profiling functions, which we discuss in more detail +below. (NOTE: To use these special features, you have to include the +header file "malloc.h" provided with this malloc. This header file +also defines the C preprocessor symbol CSRIMALLOC. This allows anyone +using any of the special features of this malloc to enclose any calls +to the new features within #ifdef CSRIMALLOC, thus preserving code +portability) + +Since this malloc library is usually installed as libmalloc.a, to use +it instead of a regular system malloc, you need to specify something +like -lmalloc on your link/load command line before -lc, if any. +Make sure your program has at least one call to any one of +malloc/free/calloc/realloc or the Unix loader may not link in this +malloc, and will instead use the system one from libc, since it makes +only one pass. + +Most of the debugging features will be available in a version of the +malloc called malloc_d, which is what you should use for development +and testing by specifying -lmalloc_d. For production programs, link +with -lmalloc to get the fast version. + +Frequently, people forget to check the return value on a malloc() +assuming that modern systems never run out of memory. Inevitably, +Murphy ensures that some system will run out of memory, and a user +will be faced with the illuminating error message "Segmentation +violation - core dumped". Alas, when memory runs out, the core dump is +likely to be large. This malloc provides an emalloc() function which +exits if NULL is returned, with an out of memory message. Using this +in place of malloc is advised if running out of memory is a fatal +condition. (If not, either write your own emalloc() to recover +gracefully, or check the value returned by malloc) + + char * + emalloc(nbytes) + + unsigned nbytes; + +Similarly, a realloc which will die instead of returning NULL is +erealloc(). + + char * + erealloc(ptr, nbytes) + + unsigned nbytes; + +A similar function, like strdup() but not returning NULL is strsave(). + + char * + strsave(s) + + char *s; + + + Debugging support + +Alas, one of the more common, and unpleasant errors a C programmer can +make is to accidentally exceed the bounds of an array, and write over +the data that immediately follows (or less frequently, precedes) it in +memory. Such "corruption" errors usually show up at a completely +different place in the program from the place the actual overwriting +occurs (A corollary to Murphy's Law suggests the error will appear in +the last related module of the program), thus making it at least as +hard to track down as the proverbial needle in the haystack. While +there is little that we can do to help detect errors in static, +automatic or global data, we can at least try to ensure the validity +of the malloc()ed data. + +To get this support, the malloc() must be compiled with -DDEBUG - +since this reduces performance somewhat, it is usually done in a +separate object module from the one usually used in production code. +This debugging malloc() makes sure all internal heap pointers relevant +to an allocation (or free) are correct on every call to one of the +allocation routines, and aborts if it detects any trouble, with a +message starting with "assertion botched". This is +useful because it causes the program to die nearer the trouble spot +than would otherwise be the case, helping to pinpoint the error. +This narrows down the location of the error to something less than the +aforementioned haystack, but the problem is still somewhat large. + + int + mal_verify(fullcheck) + + int fullcheck; + +lends a helping hand in such distressing situations. It runs through +all allocated and free blocks, checking all heap pointers for +validity. Since the heap pointers (and block size values) are at the +beginning and end of allocated (and free) blocks, any overwriting off +the end of a memory block usually results in the corruption of the +heap size values, or the pointer values of the next block. If +'fullcheck' is non-zero, then additional checking of the contents of +free blocks is done, to ensure that they haven't been written into +after being freed. Calling mal_verify() with fullcheck as 1 is +recommended. (More on this later) + +On detecting an error, mal_verify() aborts the program, on the not +unreasonable grounds that such an error is A BAD THING and should be +fixed immediately. + +A careful programmer will probably want to put calls to mal_verify() +at frequent points in any code, as checkpoints to trap any stray +overwriting or memory corruption that may take place. Since +mal_verify() does nothing in a malloc compiled without -DDEBUG, it +has no overhead in production code other than the procedure call. +("But I can't be overwriting any data between X and Y in my code" are +famous last words) + +Instead of putting calls to mal_verify(), the programmer can set +the debugging level of the allocator. + + void + mal_debug(level) + + int level; + +Most debugging is done at level 1, which is the default. This only +checks the internal pointers that are encountered during a malloc() or +free(). Setting level to 2 with the mal_debug() call results in a +complete check of the heap (i.e. a call to mal_verify(0) ) every time +malloc(), realloc() or free() are called. (The other allocation +routines call these three) This can be very slow if your program does +a lot of debugging, but is worth turning on for a specific segment of +the program where you suspect trouble. (The author uses this mode when +writing and debugging a program initially, switches to normal +debugging for alpha and beta test) Level 3 asks for mal_verify(1) on +every malloc(), realloc() or free() which checks all free blocks' +insides for any signs of someone writing to them. + +We recommend the use of a binary search technique for pinpointing the +needle, er, the overwriting. This presupposes that malloc(), free(), +or a previously (wisely) inserted mal_verify() has caused the +program to die at some point with an "assertion botched" error. (If +the programmer has not been using this malloc so far, or a variant +compiled without -DDEBUG, then the only indication of a memory +corruption error is utterly strange things happening to the program, +possibly variable changing values when they're not supposed to, or +mysterious deaths of the program in malloc(), free() or some such +call) + +Insert a mal_verify() call (Referred to from now on as Checkpoint +1) at some point well before the error occurs, if necessary, at the +first executable statement in the program. Insert another +mal_verify call on the statement just before you suspect the error +manifesting itself. (Checkpoint 2) + +(Note that when we say insert a mal_verify() call at some point +"before" an error occurs, we are referring to a temporal location, +i.e some piece of code that is executed by the program in the time +before the error occurs. Physically, this may be in a different +procedure, or a different file altogether.) + +Run the program. + +If Checkpoint 1 causes the program to die, then the error is trapped +in between it and the start of the program. (case A) If Checkpoint 2 +causes the program to die, then the error is trapped between it and +Checkpoint 1, (case B) and if neither dies, the error is after +Checkpoint 2, (case C) or is not an overwriting error at all, or is an +error subtle enough to avoid the heap pointer checking. In the last +case, we wish you luck... + +Case A: (The bug is before checkpoint 1) + +Move Checkpoint 2 to where checkpoint 1 presently is, and move +checkpoint 1 further back. Run the program again. + +Case B: (The bug is between checkpoint 1 and checkpoint 2 - narrow the +search area down further) + +This is the case we attempt to maintain. Having attained it, we +promptly attempt to lose it again. (Why is this starting to sound like +Zen...) To do so, we move either Checkpoint 1 or Checkpoint 2 closer +to the other, and run the program again. + +Case C: (The bug is after checkpoint 2) + +Move Checkpoint 1 to where checkpoint 2 presently is, and move +checkpoint 2 further ahead. Run the program again. + +The objective is to bring the two checkpoints as close to each other +as is necessary to spot the bug. (Recognizing the bug is up to the +programmer - loops exceeding the bound by one are a common problem +causing this error - confusion with C's starting arrays at 0 unlike +other languages which start them at 1 is another problem). + +Those familiar with numerical methods will see the similarity between +this method and the binary search method for finding a root of an +equation. (It also bears a resemblance to the binary search method on +sorted data, but the resemblance is less striking) + +In a modular program, which has been well structured, placing such +checkpoints is easy to do; simply start at the top level, narrow it +down to some procedure call at that level, insert them at the entry and +exit points of that procedure, narrow it down to some procedure call +at this level, and recurse downward till the fault is detected. + +We noted earlier that some corruption bugs manifest themselves (Why is +this starting to read like a ghostbusters' script...) as data values +that change when they shouldn't. In this case, a simpler method to +trace the bug is often to put a trace on that data location by setting +a global pointer variable to point to it, and printing the value at +the two checkpoints. The same search strategy can be employed. This +has been found useful in at least one bug the author has encountered, +which sneakily refused to corrupt the heap pointers, jumping over them +straight into another block to do its dirty work. + +A vicious form of heap corruption is when someone frees a block of +memory, but forgets to NULL or reset all pointers pointing to that +block. At some point in the future, if that block is accessed, strange +things can happen. If that block is still free, and in the heap, there +is a chance of corrupting malloc's internal pointers and structures +used to maintain the free list, in which case mal_verify() will detect +the corruption and abort. Or the corruption may go into the middle of +the block and go undetected. Even worse, the block or part of the +block may have been allocated to the program for some other purpose, +and the corruption may now be smashing data in another part of the +program. This sort of corruption is insidious, and very hard to +reproduce, let alone trace down. To help trace this down, when a block +is freed, in debugging mode, the allocator scribbles a magic pattern +all over it, thus making sure any data in there is likely to be wrong. +Invoking mal_verify(1) will check every free block to make sure its +contents are that magic pattern and abort if it detects corruption. +Setting debug level to 3 with mal_debug() will force this sort of +verification on every call to malloc(), realloc() or free(). +Obviously, if the block gets allocated, and then corrupted, the malloc +verification cannot detect it, since it has no idea what goes on +inside allocated blocks. + + + Advanced debugging tools. + + void + mal_heapdump(fd) + + FILE *fd; + +If all else fails, the programmer may obtain a printout of the entire +heap by calling mal_heapdump() with a file descriptor to an already +open file (fopen(3)). This will print the start address of +all blocks, allocated or free, and their sizes. These can be matched +with pointer addresses in the program and used to trace heap +corruption. If you use this call, you probably know how to do this. +Large doses of intuition (and strong beverages) are recommended. +mal_heapdump() performs the same checking that mal_verify(1) does, but +does not abort unless the error makes it impossible to dump the heap +further. A knowledge of the malloc internals is necessary to fully +exploit this call's output. + + Profiling support + +This malloc() is faster than most other mallocs that I've seen - the +search strategy is a first-free, which is not excitingly fast in +theory, but, with small modifications turns out to be quite fast in +practice; See Knuth for more details. (Theoretically, the time is of +the same order as the size of the free list, so the free list is kept +as small as possible by coalescing a block with adjacent freed blocks +if possible, when it is freed) The free() is based on a boundary tags +scheme, as described in Knuth. It is linear-time, for those who care +about such things, and is a few statements of C code - 4 comparisons +and a little pointer arithmetic. It also accesses memory locations +next to the block only, so it has good virtual memory performance. (The +malloc turns out to have good VM performance most of the time, but +will occasionally scan through a few pages, and in worst case, through +a lot of pages. If however, those pages are all being used, then the +VM performance is likely to be influenced more by the program using +the malloc than the malloc itself) + +Nonetheless, a program which calls malloc and free *very* frequently +might be slow. In order to track down malloc usage, if compiled with +-DPROFILEDSIZES, this malloc keeps count of the number of block sizes +being used by the program. To print out these collected statistics, +call + + void + mal_statsdump(fd) + + FILE *fd; + +where fd is an already opened file descriptor, and it will print a +list of block sizes, and the number of times a block of that size was +allocated. This information provides some indication of the allocation +profile of the calling program. + +When mal_statsdump() is called, it zeroes all the counters, so that +you can check the allocation profile of specific segments of a program +by calling mal_statsdump() repeatedly. + +If more detailed tracing information is needed, the malloc must be +compiled with -DTRACE. This prints out the size of every allocation +or free. This can be turned on or off using + + void + mal_trace(flag) + + int flag; + +If flag is 0, tracing is turned off, (this is the default state), if +it is non-zero, then tracing commences. + +The trace records are of the form: +For a malloc, + + <nbytes> <realsize> <address> + + where <nbytes> is the number of +bytes requested, <realsize> is the number of bytes allocated (usually +nbytes rounded up to a multiple of the word size, plus any slop if +that is requested with mal_slopset), and <address> is the block +returned. + + If the malloc results in the system being asked for more memory, +via sbrk(), it prints + sbrk <bytesobtained> +where <bytesobtained> is the number of bytes the system was asked for. +After the first such call, it will then print + heapstart <address> +where <address> is the + +For a free, + - <realsize> <address> +where <address> is the address of the block being freed +and <realsize> is the malloc'ed size of the block. (the size requested +by the user, rounded up to the word size with slop, if any) + +For a realloc, it may print out + the same as as a free if we're shrinking and the part of the +block was freed + + no-op + if we're shrinking and the remaining part of the block +was too small to be freed, it prints + + ++ <nbytes> <realsize> <address> <realsize_free> <address_free> +where <nbytes> is the number of bytes requested, <realsize> is the actual +number of bytes in the block returned, and <address> is the address of +the block returned, <realsize_free> is the actual size of the free +block after the one we're returning, which we grew into, <address_free> +is the address of the free block after the one we're returning. The +free block information is internal to the malloc and is of little use +to the user. + + the same as for a malloc and a free if the block ends up being +copied to a new block. + + +The trace records may be prefixed by the filename and linenumber of +the call is the source if the file malloc.h was included and the C +preprocessor symbol MALLOC_TRACE defined when compiling the program, +and the malloc library was compield with the tracing option enabled. +(Ask your system adminstrator, or whoever installed the malloc) +(typically with the flag -DMALLOC_TRACE on the cc command line) This +is advised - it makes debugging and leak tracing much easier. + +The file to which this information is printed can be set with + + void + mal_setstatsfile(fd) + + FILE *fd; + +The default is stderr. + + +There are two variables in this malloc that can be set to tune +performance somewhat, and keep memory fragmentation down. One is +'slop', the other is the sbrk() size. + + void + mal_slopset(slop) + + int slop; + +The minimum size block allocated is slop. (The default for this is the +minimum possible to maintain the heap pointers required for a free +block, denoted by a slop of 0) If you notice however, that a lot of +blocks are being used in a specific small size, or small range of +small sizes, then you might want to increase slop so that slop is big +enough to cover all those sizes - while this may waste some memory, it +will speed up allocation for those sizes by guaranteeing that all +blocks in the free list are at least that size, so the first fit +becomes as fast as possible, and the memory fragmentation is reduced +because of the more uniform block size. + + void + mal_sbrkset(nbytes) + + int nbytes; + +If there isn't a block large enough to supply a malloc request, then +the allocator asks for the system to increase the data space of the +process using the sbrk call. By default, sbrk() is called with 1K * +sizeof(Word). (unless the malloc request is for a larger size) If your +program uses less memory than this, you may want to reduce the size. +On the other hand, in a program that allocates a lot of memory, to +reduce the number of system calls, you may want to increase this size, +using the mal_sbrkset() call. + + Performance + +The 4.3 malloc, (variants of which are distributed with perl, tcsh, +GNU and so on) is slightly faster than this malloc but it wastes more +space because it allocates blocks in powers of 2. It does not coalesce +free space, which can lead to it wasting lots of space. (There are some +pathological allocation sequences where it will ask for more space +from the system even though it has enough free space) + +The Sun malloc wastes somewhat less than this malloc, but is +twice as slow, and causes more paging because it stores free blocks +and their headers separately. It has debugging support similar to +mal_verify() and mal_debug(), but not quite as thorough. + +The 4.1 malloc is much slower than this malloc, and wastes about the +same space. + + Incompatibilities + +There is only one serious incompatibility that I know of with some +other malloc()s. In the old 4.1 malloc(), free was kept fast by not +having it merge adjacent free blocks. This resulted in seriously +fragmented arenas for programs that did a lot of allocation and +freeing. + +The realloc() kludge provided a hook to force the merging of such +blocks - the user called realloc() with a a block which had been freed. + +I think this practice is bad (Also, both ANSI and SVID do not support +it) - since this malloc does a fast free that also merges the freed +block to maintain the largest possible contiguous free blocks, there +is no need for storage compaction. If compiled with -DDEBUG, this +realloc() will die with an error if a freed block is passed to +realloc() which would enable fixing programs that adhere to the old +convention. If not compiled with -DDEBUG, it sets errno to EINVAL and +returns NULL. + + Memory leaks + +Some memory allocated by a program is meant for the entire lifetime of +the program. (For many simple programs, this constitutes all the +allocation done by the program, and this section does not apply to +such programs) Some memory however is allocated for some time, and is +later freed. + +Keeping track of memory to be freed is often a nuisance, and +sometimes, programs may change the only pointer to an allocated block +without freeing the block first. such unreferenced, but allocated +memory is called "garbage" or a "memory leak", and is wasted, since +the program has no way of finding it again. (Other languages, like +Lisp, perform garbage collection frequently, finding all blocks that +are unreferenced, and freeing them. In the Unix/C environment, this is +difficult to do, even though garbage collecting mallocs exist. Even +worse, it is often inefficient) + +Memory leaks are serious for programs that run for a long time - +window managers, daemons, and suchlike, since the total memory wasted +over time may be large. Meticulously freeing everything allocated +by a program is the best solution - alas, for object-oriented +programming styles, it becomes very hard to keep track of every object +ever created so that open can free it. + +One method or providing temporary storage is the alloca() function. +This is used to allocate space off the run-time stack so that it is +automatically reclaimed upon procedure exit. It can therefore be used +to provide temporary storage needed by a procedure and the procedures +called by the procedure. Whether or not to use the alloca() call is a +somewhat controversial matter. The manual page warns that + "alloca() is both machine- and compiler-dependent; its use is + discouraged." +On the other hand, a fairly portable implementation using malloc() and +free() does exist, and some compilers (eg) GNU cc provide a +__builtin_alloca function, which they translate into a couple of +machine instructions to extend the frame pointer in the appropriate +direction. With these compilers, alloca() can be very fast - much +faster than any other memory allocation technique short of statically +allocated buffers. + +Alloca() still does not address the problem of storage which is needed +temporarily, but which may be passed to a routine's parent. + +Another way for a programmer to trace what is going on is to define +the preprocessor symbol MALLOC_TRACE (for example, with -DMALLOC_TRACE +on the cc command line when compiling the program) and then include +the header file "malloc.h" in the program. When MALLOC_TRACE is +defined, this header redefines malloc() and friends to macros, which +invoke _malloc() etc; the latter are routines which take the filename +and linenumber at which they are called. Calling + + void + mal_leaktrace(value) + + int value; + +with value > 0 will start the leaktracing process, recording the +address of each block returned by malloc, calloc, etc, along with the +filename:linenumber at which it was called. If that block is freed, it +deletes the record for that block. (Calling mal_leaktrace() with +value == 0 turns off tracing) + +At any time, the programmer can call + + void + mal_dumpleaktrace(fd) + + FILE *fd; + +where fd is a file pointer onto a file openeed for writing with +fopen() or freopen(), into which a list of unfreed blocks is dumped. +This list is in the form + + filename:linenumber: sequence-no. address-in-decimal (address-in-hex) + +This permits the programmer to examine the places in the program where +blocks were allocated and not freed. These represent potential memory +leaks. (Several text-editors will understand this sort of output as +output from grep -n, and will be able to load and step through these +files, eg. Jove) + +Typically, memory leaks take place within the main loop of a program, +so the general structure of the program may look something like + + initialization allocation + while (something) { + things to do + } + +The initial allocation is at worst a one-time memory wastage and does +not concern us that much. Memory that is allocated inside the loop, +and is not freed does concern us since it is a continuous loss, so +after the initialization allocation, we insert a call to +mal_leaktrace() to start tracing. When the second iteration starts, +we call mal_dumpleaktrace() to dump the blocks that were presumably +allocated during the first iteration and have not yet been freed, and +do the same at the start of the third iteration for unfreed blocks +from the second iteration and so on. The code now looks something like + + initialization allocation + mal_leaktrace(1); + while(something) { + mal_dumpleaktrace(stderr); + things to do; + } + +The above is a simple example - more complex control-flow may require +turning leak tracing on and off repeatedly, so as not to get deluged +with information. + +If you use allocation functions within your code that layer on top of +malloc, this leak tracing as it is will not be too useful since it +will only report the location of your allocation functions. In that +case, you have to define subsidiary allocation functions like +_malloc() and #defines like those in the malloc.h file so that you can +record the real address of the call. See the _malloc.c file and the +malloc.h header for examples on how to do this. (You have to call the +real allocation and then use the RECORD_FILE_AND_LINE() macro from +trace.h to store the address of the allocated block. When you free the +block you have to call the DELETE_RECORD() macro to remove that +address. Do not include malloc.c in these files, and make sure you do +call the real malloc from your allocation function - otherwise the +allocation package will attempt to record the same address twice and +fail) You may also want to include defs.h and then use PRTRACE() to +print the line number and file name in the trace file. diff --git a/lib/libmalloc/malloc.h b/lib/libmalloc/malloc.h new file mode 100644 index 000000000000..f86ed22827ca --- /dev/null +++ b/lib/libmalloc/malloc.h @@ -0,0 +1,136 @@ +/* + * Copyright University of Toronto 1988, 1989, 1993. + * Written by Mark Moraes + * + * Permission is granted to anyone to use this software for any purpose on + * any computer system, and to alter it and redistribute it freely, subject + * to the following restrictions: + * + * 1. The author and the University of Toronto are not responsible + * for the consequences of use of this software, no matter how awful, + * even if they arise from flaws in it. + * + * 2. The origin of this software must not be misrepresented, either by + * explicit claim or by omission. Since few users ever read sources, + * credits must appear in the documentation. + * + * 3. Altered versions must be plainly marked as such, and must not be + * misrepresented as being the original software. Since few users + * ever read sources, credits must appear in the documentation. + * + * 4. This notice may not be removed or altered. + * + * $Id: malloc.h,v 1.1 1994/03/06 22:59:49 nate Exp $ + */ +#ifndef __XMALLOC_H__ +#define __XMALLOC_H__ + +#if defined(ANSI_TYPES) || defined(__STDC__) +#define univptr_t void * +#else /* ! ANSI_TYPES */ +#define univptr_t char * +#define size_t unsigned int +#endif /* ANSI_TYPES */ + +#if defined(ANSI_TYPES) && !defined(__STDC__) +#define size_t unsigned long +#endif + +#if defined(__STDC__) +#define __proto(x) x +#else +#define __proto(x) () +#endif + +/* + * defined so users of new features of this malloc can #ifdef + * invocations of those features. + */ +#define CSRIMALLOC + +#ifdef MALLOC_TRACE +/* Tracing malloc definitions - helps find leaks */ + +extern univptr_t __malloc __proto((size_t, const char *, int)); +extern univptr_t __calloc __proto((size_t, size_t, const char *, int)); +extern univptr_t __realloc __proto((univptr_t, size_t, const char *, int)); +extern univptr_t __valloc __proto((size_t, const char *, int)); +extern univptr_t __memalign __proto((size_t, size_t, const char *, int)); +extern univptr_t __emalloc __proto((size_t, const char *, int)); +extern univptr_t __ecalloc __proto((size_t, size_t, const char *, int)); +extern univptr_t __erealloc __proto((univptr_t, size_t, const char *, int)); +extern char *__strdup __proto((const char *, const char *, int)); +extern char *__strsave __proto((const char *, const char *, int)); +extern void __free __proto((univptr_t, const char *, int)); +extern void __cfree __proto((univptr_t, const char *, int)); + +#define malloc(x) __malloc((x), __FILE__, __LINE__) +#define calloc(x, n) __calloc((x), (n), __FILE__, __LINE__) +#define realloc(p, x) __realloc((p), (x), __FILE__, __LINE__) +#define memalign(x, n) __memalign((x), (n), __FILE__, __LINE__) +#define valloc(x) __valloc((x), __FILE__, __LINE__) +#define emalloc(x) __emalloc((x), __FILE__, __LINE__) +#define ecalloc(x, n) __ecalloc((x), (n), __FILE__, __LINE__) +#define erealloc(p, x) __erealloc((p), (x), __FILE__, __LINE__) +#define strdup(p) __strdup((p), __FILE__, __LINE__) +#define strsave(p) __strsave((p), __FILE__, __LINE__) +/* cfree and free are identical */ +#define cfree(p) __free((p), __FILE__, __LINE__) +#define free(p) __free((p), __FILE__, __LINE__) + +#else /* MALLOC_TRACE */ + +extern univptr_t malloc __proto((size_t)); +extern univptr_t calloc __proto((size_t, size_t)); +extern univptr_t realloc __proto((univptr_t, size_t)); +extern univptr_t valloc __proto((size_t)); +extern univptr_t memalign __proto((size_t, size_t)); +extern univptr_t emalloc __proto((size_t)); +extern univptr_t ecalloc __proto((size_t, size_t)); +extern univptr_t erealloc __proto((univptr_t, size_t)); +extern char *strdup __proto((const char *)); +extern char *strsave __proto((const char *)); +extern void free __proto((univptr_t)); +extern void cfree __proto((univptr_t)); + +#endif /* MALLOC_TRACE */ + +extern void mal_debug __proto((int)); +extern void mal_dumpleaktrace __proto((FILE *)); +extern void mal_heapdump __proto((FILE *)); +extern void mal_leaktrace __proto((int)); +extern void mal_sbrkset __proto((int)); +extern void mal_slopset __proto((int)); +extern void mal_statsdump __proto(()); +extern void mal_setstatsfile __proto((FILE *)); +extern void mal_trace __proto((int)); +extern int mal_verify __proto((int)); +extern void mal_mmap __proto((char *)); + + +/* + * You may or may not want this - In gcc version 1.30, on Sun3s running + * SunOS3.5, this works fine. + */ +#ifdef __GNUC__ +#define alloca(n) __builtin_alloca(n) +#endif /* __GNUC__ */ +#ifdef sparc +#define alloca(n) __builtin_alloca(n) +#endif /* sparc */ + +#ifdef ANSI_TYPES +#undef univptr_t +#else /* ! ANSI_TYPES */ +#undef univptr_t +#undef size_t +#endif /* ANSI_TYPES */ + +/* Just in case you want an ANSI malloc without an ANSI compiler */ +#if defined(ANSI_TYPES) && !defined(__STDC__) +#undef size_t +#endif + +#undef __proto + +#endif /* __XMALLOC_H__ */ /* Do not add anything after this line */ diff --git a/lib/libmalloc/memalign.c b/lib/libmalloc/memalign.c new file mode 100644 index 000000000000..270aa4e62676 --- /dev/null +++ b/lib/libmalloc/memalign.c @@ -0,0 +1,160 @@ +/* Author: Mark Moraes <moraes@csri.toronto.edu> */ + +/*LINTLIBRARY*/ + +#include "defs.h" +#include "globals.h" + +RCSID("$Id: memalign.c,v 1.1 1994/03/06 22:59:49 nate Exp $") + +/* + * !! memalign may leave small (< _malloc_minchunk) blocks as garbage. + * Not worth fixing now -- I've only seen two applications call valloc() + * or memalign(), and they do it only once in their life. + */ +/* + * This is needed to be compatible with Sun mallocs - Dunno how many + * programs need it - the X server sure does... Returns a block 'size' + * bytes long, such that the address is a multiple of 'alignment'. + * (alignment MUST be a power of 2). This routine is possibly more + * convoluted than free() - certainly uglier. Since it is rarely called + * - possibly once in a program, it should be ok. Since this is called + * from valloc() which is usually needed in conjunction with + * mmap()/munmap(), note the comment in the Sun manual page about + * freeing segments of size 128K and greater. Ugh. + */ +univptr_t +memalign(alignment, size) +size_t alignment, size; +{ + univptr_t cp; + univptr_t addr; + REGISTER Word *p0, *p1; + REGISTER size_t before, after; + size_t blksize; +#ifdef DEBUG + int tmp_debugging = _malloc_debugging; +#endif /* DEBUG */ + + if (alignment < sizeof(int) || !is_power_of_2(alignment) ||size == 0) { + errno = EINVAL; + return(NULL); + } + if (alignment < sizeof(Word)) + return(malloc(size)); /* We guarantee this alignment anyway */ + /* + * Life starts to get complicated - need to get a block large + * enough to hold a block 'size' long, starting on an 'alignment' + * boundary + */ + if ((cp = malloc((size_t) (size + alignment - 1))) == NULL) + return(NULL); + addr = SIMPLEALIGN(cp, alignment); + /* + * This is all we really need - can go back now, except that we + * might be wasting 'alignment - 1' bytes, which can be large since + * this junk is usually called to align with things like pagesize. + * So we try to push any free space before 'addr' and after 'addr + + * size' back on the free list by making the memaligned chunk + * ('addr' to 'addr + size') a block, and then doing stuff with the + * space left over - either making them free blocks or coelescing + * them whichever way is simplest. This usually involves making + * them look like allocated blocks and calling free() which has all + * the code to deal with this, and should do it reasonably fast. + */ + p0 = (Word *) cp; + p0 -= HEADERWORDS; + /* + * p0 now points to the word tag starting the block which we got + * from malloc. This remains invariant from now on - p1 is our + * temporary pointer + */ + p1 = (Word *) addr; + p1 -= HEADERWORDS; + blksize = (size + sizeof(Word) - 1) / sizeof(Word); + before = p1 - p0; + after = SIZE(p0) - ALLOC_OVERHEAD - blksize - before; + /* + * p1 now points to the word before addr - this is going to be the + * start of the memaligned block + */ + if (after < _malloc_minchunk) { + /* + * We merge the extra space after the memaligned block into it + * since that space isn't enough for a separate block. Note + * that if the block after the one malloc returned is free, we + * might be able to merge the space into that block even if it + * is too small - unfortunately, free() won't accept a block of + * this size, and I don't want to do that code here, so we'll + * just let it go to waste in the memaligned block. !! fix later, maybe + */ + blksize += after; + after = 0; + } + /* + * We mark the newly carved memaligned block p1 as alloced. addr is + * (p1 + 1) which is the address we'll return + */ + SIZEFIELD(p1) = ALLOCMASK(blksize + ALLOC_OVERHEAD); + SIZEFIELD(p1 + blksize + ALLOC_OVERHEAD - 1) = SIZEFIELD(p1); + SET_REALSIZE(p1, size); + if (after > 0) { + /* We can now free the block after the memaligned block. */ + p1 += blksize + ALLOC_OVERHEAD; /* SIZE(p1) */ + /* + * p1 now points to the space after the memaligned block. we + * fix the size, mark it alloced, and call free - the block + * after this may be free, which isn't simple to coalesce - let + * free() do it. + */ + SIZEFIELD(p1) = ALLOCMASK(after); + SIZEFIELD(p1 + after - 1) = SIZEFIELD(p1); + SET_REALSIZE(p1, (after - ALLOC_OVERHEAD) * sizeof(Word)); +#ifdef DEBUG + /* Full heap checking will break till we finish memalign */ + _malloc_debugging = 0; +#endif /* DEBUG */ + free((univptr_t) (p1 + HEADERWORDS)); + } + if (addr != cp) { + /* + * If what's 'before' is large enough to be freed, add p0 to + * free list after changing its size to just consist of the + * space before the memaligned block, also setting the + * alloced flag. Then call free() -- may merge with preceding + * block. (block after it is the memaligned block) + */ + /* + * Else the space before the block is too small to form a + * free block, and the preceding block isn't free, so we + * aren't touching it. Theoretically, we could put it in + * the preceding alloc'ed block, but there are painful + * complications if this is the start of the arena. We + * pass, but MUST mark it as allocated. This sort of garbage + * can split up the arena -- fix later with special case maybe?!! + */ + p1 = p0; + SIZEFIELD(p1) = ALLOCMASK(before); + SIZEFIELD(p1 + before - 1) = SIZEFIELD(p1); + SET_REALSIZE(p1, (before - ALLOC_OVERHEAD) * sizeof(Word)); + if (before >= _malloc_minchunk) { + free(cp); + } + } +#ifdef DEBUG + _malloc_debugging = tmp_debugging; +#endif /* DEBUG */ + return(addr); +} + +/* Just following the Sun manual page here */ +univptr_t +valloc(size) +size_t size; +{ + static size_t pagesz = 0; + + if (pagesz == 0) + pagesz = (size_t) getpagesize(); + return(memalign(pagesz, size)); +} diff --git a/lib/libmalloc/setopts.c b/lib/libmalloc/setopts.c new file mode 100644 index 000000000000..d3ddb70f7c63 --- /dev/null +++ b/lib/libmalloc/setopts.c @@ -0,0 +1,120 @@ +/* Set various malloc options */ +/* Author: Mark Moraes <moraes@csri.toronto.edu> */ + +/*LINTLIBRARY*/ + +#include "defs.h" +#include "globals.h" + +RCSID("$Id: setopts.c,v 1.1 1994/03/06 22:59:50 nate Exp $") + +/* + * Sets debugging level - level 0 and 1 both perform normal checking - + * making sure a pointer is valid before it is used for any heap data, + * and doing consistency checking on any block it touches while it + * works. Level 2 asks for a mal_verify() on every malloc(), free() or + * realloc(), thus checking the entire heap's pointers for consistency. + * Level 3 makes mal_verify() check that all free blocks contain a + * magic pattern that is put into a free block when it is freed. + */ +void +mal_debug(level) +int level; +{ +#ifdef DEBUG + if (level < 0 || level > 3) { + return; + } + _malloc_debugging = level; +#endif /* DEBUG */ +} + +/* + * Allows you to control the number of system calls made, which might + * be helpful in a program allocating a lot of memory - call this once + * to set a number big enough to contain all the allocations. Or for + * very little allocation, so that you don't get a huge space just + * because you alloc'e a couple of strings + */ +void +mal_sbrkset(n) +int n; +{ + if (n < _malloc_minchunk * sizeof(Word)) { + /* sbrk'ing anything less than a Word isn't a great idea.*/ + return; + } + + _malloc_sbrkunits = (n + sizeof(Word) - 1) / sizeof(Word); + return; +} + +/* + * Since the minimum size block allocated is sizeof(Word)*_malloc_minchunk, + * adjusting _malloc_minchunk is one way to control + * memory fragmentation, and if you do a lot of mallocs and frees of + * objects that have a similar size, then a good way to speed things up + * is to set _malloc_minchunk such that the minimum size block covers + * most of the objects you allocate + */ +void +mal_slopset(n) +int n; +{ + if (n < 0) { + return; + } + + _malloc_minchunk = (n + sizeof(Word) - 1) / sizeof(Word) + FIXEDOVERHEAD; + return; +} + +/* + * Sets the file used for verbose statistics to 'fd'. Does no + * verification whatsoever on the file descriptor + */ +void +mal_setstatsfile(fd) +FILE * fd; +{ + _malloc_statsfile = fd; + /* + * This file descriptor had better not have been written to before + * this + */ + (void) setvbuf(fd, (char *) 0, _IONBF, 0); +} + +/* + * Turns tracing on (if value != 0) or off, (if value == 0) + */ +void +mal_trace(value) +int value; +{ + if (value) { + /* Try to unbuffer the trace file */ + (void) setvbuf(_malloc_statsfile, (char *) 0, _IONBF, 0); + /* + * Write something to the stats file so stdio can initialize + * its buffers i.e. call malloc() at least once while tracing + * is off, if the unbuffering failed. + */ + (void) fputs("Malloc tracing starting\n", _malloc_statsfile); + _malloc_tracing = 1; + if (_malloc_loword != NULL) { + /* + * malloc happened before tracing turned on, so make + * sure we print the heap start for xmem analysis. + */ + PRTRACE(sprintf(_malloc_statsbuf, "heapstart 0x%lx\n", + (ulong) _malloc_loword)); + } + } else { + /* For symmetry */ + (void) fputs("Malloc tracing stopped\n", _malloc_statsfile); + _malloc_tracing = 0; + } + (void) fflush(_malloc_statsfile); +} + diff --git a/lib/libmalloc/sptree.c b/lib/libmalloc/sptree.c new file mode 100644 index 000000000000..e7d28f00ab26 --- /dev/null +++ b/lib/libmalloc/sptree.c @@ -0,0 +1,763 @@ +/* + * This file contains a few splay tree routines snarfed from David + * Brower's package, with globals renamed to keep them internal to the + * malloc, and not clash with similar routines that the application may + * use. The comments have been left with the original names - most of + * the renaming just involved prepending an __ before the name - + * spinstall got remapped to __spadd. Function prototypes added for + * external declarations. - Mark Moraes. + */ +/* + * spdaveb.c -- daveb's new splay tree functions. + * + * The functions in this file provide an interface that is nearly + * the same as the hash library I swiped from mkmf, allowing + * replacement of one by the other. Hey, it worked for me! + * + * splookup() -- given a key, find a node in a tree. + * spinstall() -- install an item in the tree, overwriting existing value. + * spfhead() -- fast (non-splay) find the first node in a tree. + * spscan() -- forward scan tree from the head. + * spfnext() -- non-splaying next. + * spstats() -- make char string of stats for a tree. + * + * Written by David Brower, daveb@rtech.uucp 1/88. + */ +/*LINTLIBRARY*/ + +#if defined(__STDC__) && defined(ANSI_TYPES) +#include <stddef.h> +#endif +#include <stdio.h> + +#include "defs.h" + +# define COMPARE(a,b) (((char *) (a)) - ((char *) (b))) + +# include "sptree.h" + +/* insert item into the tree */ +static SPBLK * spenq proto((SPBLK *, SPTREE *)); +/* return and remove lowest item in subtree */ +static SPBLK * spdeq proto((SPBLK **)); +/* reorganize tree */ +static void splay proto((SPBLK *, SPTREE *)); +/* fast non-splaying head */ +static SPBLK * spfhead proto((SPTREE *)); +/* fast non-splaying next */ +static SPBLK * spfnext proto((SPBLK *)); + +/* USER SUPPLIED! */ + +extern univptr_t emalloc proto((size_t)); + + +/*---------------- + * + * splookup() -- given key, find a node in a tree. + * + * Splays the found node to the root. + */ +SPBLK * +__splookup( key, q ) +REGISTER univptr_t key; +REGISTER SPTREE *q; + +{ + REGISTER SPBLK * n; + REGISTER int Sct; + REGISTER int c; + + /* find node in the tree */ + n = q->root; + c = ++(q->lkpcmps); + q->lookups++; + while( n && (Sct = COMPARE( key, n->key ) ) ) + { + c++; + n = ( Sct < 0 ) ? n->leftlink : n->rightlink; + } + q->lkpcmps = c; + + /* reorganize tree around this node */ + if( n != NULL ) + splay( n, q ); + + return( n ); +} + + + +/*---------------- + * + * spinstall() -- install an entry in a tree, overwriting any existing node. + * + * If the node already exists, replace its contents. + * If it does not exist, then allocate a new node and fill it in. + */ + +SPBLK * +__spadd( key, data, datb, q ) + +REGISTER univptr_t key; +REGISTER univptr_t data; +REGISTER univptr_t datb; +REGISTER SPTREE *q; + +{ + REGISTER SPBLK *n; + + if( NULL == ( n = __splookup( key, q ) ) ) + { + n = (SPBLK *) emalloc( sizeof( *n ) ); + n->key = (univptr_t) key; + n->leftlink = NULL; + n->rightlink = NULL; + n->uplink = NULL; + (void) spenq( n, q ); + } + + n->data = data; + n->datb = datb; + + return( n ); +} + + + + +/*---------------- + * + * spfhead() -- return the "lowest" element in the tree. + * + * returns a reference to the head event in the event-set q. + * avoids splaying but just searches for and returns a pointer to + * the bottom of the left branch. + */ +static SPBLK * +spfhead( q ) + +REGISTER SPTREE * q; + +{ + REGISTER SPBLK * x; + + if( NULL != ( x = q->root ) ) + while( x->leftlink != NULL ) + x = x->leftlink; + + return( x ); + +} /* spfhead */ + + + +/*---------------- + * + * spscan() -- apply a function to nodes in ascending order. + * + * if n is given, start at that node, otherwise start from + * the head. + */ +void +__spscan( f, n, q ) +REGISTER void (*f)(); +REGISTER SPBLK * n; +REGISTER SPTREE * q; +{ + REGISTER SPBLK * x; + + for( x = n != NULL ? n : spfhead( q ); x != NULL ; x = spfnext( x ) ) + (*f)( x ); +} + + +/*---------------- + * + * spfnext() -- fast return next higer item in the tree, or NULL. + * + * return the successor of n in q, represented as a splay tree. + * This is a fast (on average) version that does not splay. + */ +static SPBLK * +spfnext( n ) + +REGISTER SPBLK * n; + +{ + REGISTER SPBLK * next; + REGISTER SPBLK * x; + + /* a long version, avoids splaying for fast average, + * poor amortized bound + */ + + if( n == NULL ) + return( n ); + + x = n->rightlink; + if( x != NULL ) + { + while( x->leftlink != NULL ) + x = x->leftlink; + next = x; + } + else /* x == NULL */ + { + x = n->uplink; + next = NULL; + while( x != NULL ) + { + if( x->leftlink == n ) + { + next = x; + x = NULL; + } + else + { + n = x; + x = n->uplink; + } + } + } + + return( next ); + +} /* spfnext */ + + +char * +__spstats( q ) +SPTREE *q; +{ + static char buf[ 128 ]; + float llen; + float elen; + float sloops; + + if( q == NULL ) + return(""); + + llen = q->lookups ? (float)q->lkpcmps / q->lookups : 0; + elen = q->enqs ? (float)q->enqcmps/q->enqs : 0; + sloops = q->splays ? (float)q->splayloops/q->splays : 0; + + (void) sprintf(buf, "f(%d %4.2f) i(%d %4.2f) s(%d %4.2f)", + q->lookups, llen, q->enqs, elen, q->splays, sloops ); + + return buf; +} + +/* + spaux.c: This code implements the following operations on an event-set + or priority-queue implemented using splay trees: + + spdelete( n, q ) n is removed from q. + + In the above, n and np are pointers to single items (type + SPBLK *); q is an event-set (type SPTREE *), + The type definitions for these are taken + from file sptree.h. All of these operations rest on basic + splay tree operations from file sptree.c. + + The basic splay tree algorithms were originally presented in: + + Self Adjusting Binary Trees, + by D. D. Sleator and R. E. Tarjan, + Proc. ACM SIGACT Symposium on Theory + of Computing (Boston, Apr 1983) 235-245. + + The operations in this package supplement the operations from + file splay.h to provide support for operations typically needed + on the pending event set in discrete event simulation. See, for + example, + + Introduction to Simula 67, + by Gunther Lamprecht, Vieweg & Sohn, Braucschweig, Wiesbaden, 1981. + (Chapter 14 contains the relevant discussion.) + + Simula Begin, + by Graham M. Birtwistle, et al, Studentlitteratur, Lund, 1979. + (Chapter 9 contains the relevant discussion.) + + Many of the routines in this package use the splay procedure, + for bottom-up splaying of the queue. Consequently, item n in + delete and item np in all operations listed above must be in the + event-set prior to the call or the results will be + unpredictable (eg: chaos will ensue). + + Note that, in all cases, these operations can be replaced with + the corresponding operations formulated for a conventional + lexicographically ordered tree. The versions here all use the + splay operation to ensure the amortized bounds; this usually + leads to a very compact formulation of the operations + themselves, but it may slow the average performance. + + Alternative versions based on simple binary tree operations are + provided (commented out) for head, next, and prev, since these + are frequently used to traverse the entire data structure, and + the cost of traversal is independent of the shape of the + structure, so the extra time taken by splay in this context is + wasted. + + This code was written by: + Douglas W. Jones with assistance from Srinivas R. Sataluri + + Translated to C by David Brower, daveb@rtech.uucp + + Thu Oct 6 12:11:33 PDT 1988 (daveb) Fixed spdeq, which was broken + handling one-node trees. I botched the pascal translation of + a VAR parameter. Changed interface, so callers must also be + corrected to pass the node by address rather than value. + Mon Apr 3 15:18:32 PDT 1989 (daveb) + Apply fix supplied by Mark Moraes <moraes@csri.toronto.edu> to + spdelete(), which dropped core when taking out the last element + in a subtree -- that is, when the right subtree was empty and + the leftlink was also null, it tried to take out the leftlink's + uplink anyway. + */ +/*---------------- + * + * spdelete() -- Delete node from a tree. + * + * n is deleted from q; the resulting splay tree has been splayed + * around its new root, which is the successor of n + * + */ +void +__spdelete( n, q ) + +REGISTER SPBLK * n; +REGISTER SPTREE * q; + +{ + REGISTER SPBLK * x; + + splay( n, q ); + x = spdeq( &q->root->rightlink ); + if( x == NULL ) /* empty right subtree */ + { + q->root = q->root->leftlink; + if (q->root) q->root->uplink = NULL; + } + else /* non-empty right subtree */ + { + x->uplink = NULL; + x->leftlink = q->root->leftlink; + x->rightlink = q->root->rightlink; + if( x->leftlink != NULL ) + x->leftlink->uplink = x; + if( x->rightlink != NULL ) + x->rightlink->uplink = x; + q->root = x; + } + +} /* spdelete */ + + +/* + * + * sptree.c: The following code implements the basic operations on + * an event-set or priority-queue implemented using splay trees: + * + * SPTREE *spinit( compare ) Make a new tree + * SPBLK *spenq( n, q ) Insert n in q after all equal keys. + * SPBLK *spdeq( np ) Return first key under *np, removing it. + * void splay( n, q ) n (already in q) becomes the root. + * + * In the above, n points to an SPBLK type, while q points to an + * SPTREE. + * + * The implementation used here is based on the implementation + * which was used in the tests of splay trees reported in: + * + * An Empirical Comparison of Priority-Queue and Event-Set Implementations, + * by Douglas W. Jones, Comm. ACM 29, 4 (Apr. 1986) 300-311. + * + * The changes made include the addition of the enqprior + * operation and the addition of up-links to allow for the splay + * operation. The basic splay tree algorithms were originally + * presented in: + * + * Self Adjusting Binary Trees, + * by D. D. Sleator and R. E. Tarjan, + * Proc. ACM SIGACT Symposium on Theory + * of Computing (Boston, Apr 1983) 235-245. + * + * The enq and enqprior routines use variations on the + * top-down splay operation, while the splay routine is bottom-up. + * All are coded for speed. + * + * Written by: + * Douglas W. Jones + * + * Translated to C by: + * David Brower, daveb@rtech.uucp + * + * Thu Oct 6 12:11:33 PDT 1988 (daveb) Fixed spdeq, which was broken + * handling one-node trees. I botched the pascal translation of + * a VAR parameter. + */ +/*---------------- + * + * spinit() -- initialize an empty splay tree + * + */ +SPTREE * +__spinit() +{ + REGISTER SPTREE * q; + + q = (SPTREE *) emalloc( sizeof( *q ) ); + + q->lookups = 0; + q->lkpcmps = 0; + q->enqs = 0; + q->enqcmps = 0; + q->splays = 0; + q->splayloops = 0; + q->root = NULL; + return( q ); +} + +/*---------------- + * + * spenq() -- insert item in a tree. + * + * put n in q after all other nodes with the same key; when this is + * done, n will be the root of the splay tree representing q, all nodes + * in q with keys less than or equal to that of n will be in the + * left subtree, all with greater keys will be in the right subtree; + * the tree is split into these subtrees from the top down, with rotations + * performed along the way to shorten the left branch of the right subtree + * and the right branch of the left subtree + */ +static SPBLK * +spenq( n, q ) +REGISTER SPBLK * n; +REGISTER SPTREE * q; +{ + REGISTER SPBLK * left; /* the rightmost node in the left tree */ + REGISTER SPBLK * right; /* the leftmost node in the right tree */ + REGISTER SPBLK * next; /* the root of the unsplit part */ + REGISTER SPBLK * temp; + + REGISTER univptr_t key; + + q->enqs++; + n->uplink = NULL; + next = q->root; + q->root = n; + if( next == NULL ) /* trivial enq */ + { + n->leftlink = NULL; + n->rightlink = NULL; + } + else /* difficult enq */ + { + key = n->key; + left = n; + right = n; + + /* n's left and right children will hold the right and left + splayed trees resulting from splitting on n->key; + note that the children will be reversed! */ + + q->enqcmps++; + if ( COMPARE( next->key, key ) > 0 ) + goto two; + + one: /* assert next->key <= key */ + + do /* walk to the right in the left tree */ + { + temp = next->rightlink; + if( temp == NULL ) + { + left->rightlink = next; + next->uplink = left; + right->leftlink = NULL; + goto done; /* job done, entire tree split */ + } + + q->enqcmps++; + if( COMPARE( temp->key, key ) > 0 ) + { + left->rightlink = next; + next->uplink = left; + left = next; + next = temp; + goto two; /* change sides */ + } + + next->rightlink = temp->leftlink; + if( temp->leftlink != NULL ) + temp->leftlink->uplink = next; + left->rightlink = temp; + temp->uplink = left; + temp->leftlink = next; + next->uplink = temp; + left = temp; + next = temp->rightlink; + if( next == NULL ) + { + right->leftlink = NULL; + goto done; /* job done, entire tree split */ + } + + q->enqcmps++; + + } while( COMPARE( next->key, key ) <= 0 ); /* change sides */ + + two: /* assert next->key > key */ + + do /* walk to the left in the right tree */ + { + temp = next->leftlink; + if( temp == NULL ) + { + right->leftlink = next; + next->uplink = right; + left->rightlink = NULL; + goto done; /* job done, entire tree split */ + } + + q->enqcmps++; + if( COMPARE( temp->key, key ) <= 0 ) + { + right->leftlink = next; + next->uplink = right; + right = next; + next = temp; + goto one; /* change sides */ + } + next->leftlink = temp->rightlink; + if( temp->rightlink != NULL ) + temp->rightlink->uplink = next; + right->leftlink = temp; + temp->uplink = right; + temp->rightlink = next; + next->uplink = temp; + right = temp; + next = temp->leftlink; + if( next == NULL ) + { + left->rightlink = NULL; + goto done; /* job done, entire tree split */ + } + + q->enqcmps++; + + } while( COMPARE( next->key, key ) > 0 ); /* change sides */ + + goto one; + + done: /* split is done, branches of n need reversal */ + + temp = n->leftlink; + n->leftlink = n->rightlink; + n->rightlink = temp; + } + + return( n ); + +} /* spenq */ + + +/*---------------- + * + * spdeq() -- return and remove head node from a subtree. + * + * remove and return the head node from the node set; this deletes + * (and returns) the leftmost node from q, replacing it with its right + * subtree (if there is one); on the way to the leftmost node, rotations + * are performed to shorten the left branch of the tree + */ +static SPBLK * +spdeq( np ) + +SPBLK **np; /* pointer to a node pointer */ + +{ + REGISTER SPBLK * deq; /* one to return */ + REGISTER SPBLK * next; /* the next thing to deal with */ + REGISTER SPBLK * left; /* the left child of next */ + REGISTER SPBLK * farleft; /* the left child of left */ + REGISTER SPBLK * farfarleft; /* the left child of farleft */ + + if( np == NULL || *np == NULL ) + { + deq = NULL; + } + else + { + next = *np; + left = next->leftlink; + if( left == NULL ) + { + deq = next; + *np = next->rightlink; + + if( *np != NULL ) + (*np)->uplink = NULL; + + } + else for(;;) /* left is not null */ + { + /* next is not it, left is not NULL, might be it */ + farleft = left->leftlink; + if( farleft == NULL ) + { + deq = left; + next->leftlink = left->rightlink; + if( left->rightlink != NULL ) + left->rightlink->uplink = next; + break; + } + + /* next, left are not it, farleft is not NULL, might be it */ + farfarleft = farleft->leftlink; + if( farfarleft == NULL ) + { + deq = farleft; + left->leftlink = farleft->rightlink; + if( farleft->rightlink != NULL ) + farleft->rightlink->uplink = left; + break; + } + + /* next, left, farleft are not it, rotate */ + next->leftlink = farleft; + farleft->uplink = next; + left->leftlink = farleft->rightlink; + if( farleft->rightlink != NULL ) + farleft->rightlink->uplink = left; + farleft->rightlink = left; + left->uplink = farleft; + next = farleft; + left = farfarleft; + } + } + + return( deq ); + +} /* spdeq */ + + +/*---------------- + * + * splay() -- reorganize the tree. + * + * the tree is reorganized so that n is the root of the + * splay tree representing q; results are unpredictable if n is not + * in q to start with; q is split from n up to the old root, with all + * nodes to the left of n ending up in the left subtree, and all nodes + * to the right of n ending up in the right subtree; the left branch of + * the right subtree and the right branch of the left subtree are + * shortened in the process + * + * this code assumes that n is not NULL and is in q; it can sometimes + * detect n not in q and complain + */ + +static void +splay( n, q ) + +REGISTER SPBLK * n; +SPTREE * q; + +{ + REGISTER SPBLK * up; /* points to the node being dealt with */ + REGISTER SPBLK * prev; /* a descendent of up, already dealt with */ + REGISTER SPBLK * upup; /* the parent of up */ + REGISTER SPBLK * upupup; /* the grandparent of up */ + REGISTER SPBLK * left; /* the top of left subtree being built */ + REGISTER SPBLK * right; /* the top of right subtree being built */ + + left = n->leftlink; + right = n->rightlink; + prev = n; + up = prev->uplink; + + q->splays++; + + while( up != NULL ) + { + q->splayloops++; + + /* walk up the tree towards the root, splaying all to the left of + n into the left subtree, all to right into the right subtree */ + + upup = up->uplink; + if( up->leftlink == prev ) /* up is to the right of n */ + { + if( upup != NULL && upup->leftlink == up ) /* rotate */ + { + upupup = upup->uplink; + upup->leftlink = up->rightlink; + if( upup->leftlink != NULL ) + upup->leftlink->uplink = upup; + up->rightlink = upup; + upup->uplink = up; + if( upupup == NULL ) + q->root = up; + else if( upupup->leftlink == upup ) + upupup->leftlink = up; + else + upupup->rightlink = up; + up->uplink = upupup; + upup = upupup; + } + up->leftlink = right; + if( right != NULL ) + right->uplink = up; + right = up; + + } + else /* up is to the left of n */ + { + if( upup != NULL && upup->rightlink == up ) /* rotate */ + { + upupup = upup->uplink; + upup->rightlink = up->leftlink; + if( upup->rightlink != NULL ) + upup->rightlink->uplink = upup; + up->leftlink = upup; + upup->uplink = up; + if( upupup == NULL ) + q->root = up; + else if( upupup->rightlink == upup ) + upupup->rightlink = up; + else + upupup->leftlink = up; + up->uplink = upupup; + upup = upupup; + } + up->rightlink = left; + if( left != NULL ) + left->uplink = up; + left = up; + } + prev = up; + up = upup; + } + +# ifdef SPLAYDEBUG + if( q->root != prev ) + { +/* fprintf(stderr, " *** bug in splay: n not in q *** " ); */ + abort(); + } +# endif + + n->leftlink = left; + n->rightlink = right; + if( left != NULL ) + left->uplink = n; + if( right != NULL ) + right->uplink = n; + q->root = n; + n->uplink = NULL; + +} /* splay */ + diff --git a/lib/libmalloc/sptree.h b/lib/libmalloc/sptree.h new file mode 100644 index 000000000000..ea5a260d18df --- /dev/null +++ b/lib/libmalloc/sptree.h @@ -0,0 +1,65 @@ +/* +** sptree.h: The following type declarations provide the binary tree +** representation of event-sets or priority queues needed by splay trees +** +** assumes that data and datb will be provided by the application +** to hold all application specific information +** +** assumes that key will be provided by the application, comparable +** with the compare function applied to the addresses of two keys. +*/ + +# ifndef SPTREE_H +# define SPTREE_H + +typedef struct _spblk +{ + struct _spblk * leftlink; + struct _spblk * rightlink; + struct _spblk * uplink; + + univptr_t key; /* formerly time/timetyp */ + univptr_t data; /* formerly aux/auxtype */ + univptr_t datb; +} SPBLK; + +typedef struct +{ + SPBLK * root; /* root node */ + + /* Statistics, not strictly necessary, but handy for tuning */ + + int lookups; /* number of splookup()s */ + int lkpcmps; /* number of lookup comparisons */ + + int enqs; /* number of spenq()s */ + int enqcmps; /* compares in spenq */ + + int splays; + int splayloops; + +} SPTREE; + +#if defined(__STDC__) +#define __proto(x) x +#else +#define __proto(x) () +#endif + +/* sptree.c */ +/* init tree */ +extern SPTREE * __spinit __proto((void)); +/* find key in a tree */ +extern SPBLK * __splookup __proto((univptr_t, SPTREE *)); +/* enter an item, allocating or replacing */ +extern SPBLK * __spadd __proto((univptr_t, univptr_t, univptr_t, SPTREE *)); +/* scan forward through tree */ +extern void __spscan __proto((void (*) __proto((SPBLK *)), SPBLK *, SPTREE *)); +/* return tree statistics */ +extern char *__spstats __proto((SPTREE *)); +/* delete node from tree */ +extern void __spdelete __proto((SPBLK *, SPTREE *)); + +#undef __proto + +# endif /* SPTREE_H */ diff --git a/lib/libmalloc/stats.c b/lib/libmalloc/stats.c new file mode 100644 index 000000000000..05ebb48ad869 --- /dev/null +++ b/lib/libmalloc/stats.c @@ -0,0 +1,38 @@ +/* Author: Mark Moraes <moraes@csri.toronto.edu> */ + +/*LINTLIBRARY*/ + +#include "defs.h" +#include "globals.h" + +RCSID("$Id: stats.c,v 1.1 1994/03/06 22:59:53 nate Exp $") + +/* + * Dumps the distribution of allocated sizes we've gathered so far + */ +void +mal_statsdump(fd) +FILE *fd; +{ +#ifdef PROFILESIZES + int i; + char buf[128]; + + for (i = 1; i < MAXPROFILESIZE; i++) { + if(_malloc_scount[i] > 0) { + (void) sprintf(buf, "%lu: %lu\n",(ulong)i*sizeof(Word), + (ulong) _malloc_scount[i]); + (void) fputs(buf, fd); + _malloc_scount[i] = 0; + } + } + if (_malloc_scount[0] > 0) { + (void) sprintf(buf, ">= %lu: %lu\n", + (ulong) MAXPROFILESIZE * sizeof(Word), + (ulong) _malloc_scount[0]); + (void) fputs(buf, fd); + _malloc_scount[0] = 0; + } + (void) fflush(fd); +#endif /* PROFILESIZES */ +} diff --git a/lib/libmalloc/strdup.c b/lib/libmalloc/strdup.c new file mode 100644 index 000000000000..0e4a6bf24bb2 --- /dev/null +++ b/lib/libmalloc/strdup.c @@ -0,0 +1,26 @@ +/* Author: Mark Moraes <moraes@csri.toronto.edu> */ + +/*LINTLIBRARY*/ + +#include "defs.h" + +RCSID("$Id: strdup.c,v 1.1 1994/03/06 22:59:54 nate Exp $") + +/* + * makes a copy of a null terminated string in malloc'ed storage. + * returns null if it fails. + */ +char * +strdup(s) +const char *s; +{ + char *cp; + + if (s) { + cp = (char *) malloc((unsigned) (strlen(s)+1)); + if (cp) + (void) strcpy(cp, s); + } else + cp = (char *) NULL; + return(cp); +} diff --git a/lib/libmalloc/strsave.c b/lib/libmalloc/strsave.c new file mode 100644 index 000000000000..79fe856c4e45 --- /dev/null +++ b/lib/libmalloc/strsave.c @@ -0,0 +1,21 @@ +/* Author: Mark Moraes <moraes@csri.toronto.edu> */ + +/*LINTLIBRARY*/ + +#include "defs.h" + +RCSID("$Id: strsave.c,v 1.1 1994/03/06 22:59:55 nate Exp $") + +/* + * makes a copy of a null terminated string in malloc'ed storage. Dies + * if enough memory isn't available or there is a malloc error + */ +char * +strsave(s) +const char *s; +{ + if (s) + return(strcpy(emalloc((size_t) (strlen(s)+1)),s)); + else + return((char *) NULL); +} diff --git a/lib/libmalloc/tests/munge.sh b/lib/libmalloc/tests/munge.sh new file mode 100755 index 000000000000..d9a23309c11c --- /dev/null +++ b/lib/libmalloc/tests/munge.sh @@ -0,0 +1,40 @@ +#! /bin/sh +# takes output of testrun and massages into columnar form for easier +# evaluation and graphing +cat $* | tr ',' ' ' | + awk 'BEGIN { + printf " Maxtime Maxsize Maxlife Sbrked Alloced Wastage"; + printf " Real User Sys\n"; + } + $1 == "Maxtime" { + if (t != 0) { + printf "%8d%8d%8d%8d%8d %7.2f", t, s, l, sb, ma, w; + printf " %7.1f %7.1f %7.1f\n", mr, mu, ms; + } + t = $3; + s = $6; + l = $9; + mr = 100000; + mu = 100000; + ms = 100000; + next; + } + $1 == "Sbrked" { + sb = $2; + ma = $4; + w = $6; + next; + } + $2 == "real" { + if ($1 < mr) mr = $1; + if ($3 < mu) mu = $3; + if ($5 < ms) ms = $5; + next; + } + END { + if (t != 0) { + printf "%8d%8d%8d%8d%8d %7.2f", t, s, l, sb, ma, w; + printf " %7.1f %7.1f %7.1f\n", mr, mu, ms; + } + } + ' diff --git a/lib/libmalloc/tests/plot.sh b/lib/libmalloc/tests/plot.sh new file mode 100755 index 000000000000..74a8c8edd52e --- /dev/null +++ b/lib/libmalloc/tests/plot.sh @@ -0,0 +1,81 @@ +#! /bin/sh +# Things like +# '-s 10 file...' should plot Maxlife vs Wastage, Real, user + sys for all +# file for Maxsize == 10. +# '-l 10 file...' should plot Maxsize vs ... for Maxlife == 10. +usage="Usage: $0 [-s size | -l life] file..." +case $# in +[012]) + echo $usage >&2 + exit 1 + ;; +esac +tmp=./tmp.$$ +case $1 in +-s) + const='Maxsize' + indep='Maxlife' + units='iterations' + ;; +-l) + const='Maxlife' + indep='Maxsize' + units='words' + ;; +*) + echo $usage >&2 + exit 1 + ;; +esac +constval=$2 +shift +shift +mkdir $tmp +for i +do + base=`basename $i` + echo $base + ext=`expr "$base" : "res\.\(.*\)"` + awk '$1 == "Maxtime" { + for(i = 1; i <= NF; i++) { + field[$i] = i; + } + f1="'$tmp/W.$base'"; + f2="'$tmp/R.$base'"; + f3="'$tmp/US.$base'"; + print "\"" "'$ext'" > f1 + print "\"" "'$ext'" > f2 + print "\"" "'$ext'" > f3 + cfld=field["'$const'"]; + cval='$constval'; + xfld=field["'$indep'"]; + y1=field["Wastage"]; + y2=field["Real"]; + y3=field["User"]; + y4=field["Sys"]; + } + $cfld == cval { + print $xfld, $y1 * 100 >> f1; + print $xfld, $y2 >> f2; + print $xfld, $y3 + $y4 >> f3; + } + END { + print "" >> f1; + print "" >> f2; + print "" >> f3; + }' $i +done +cat $tmp/W.* > $tmp/W +rm -f $tmp/W.* +cat $tmp/R.* > $tmp/R +rm -f $tmp/R.* +cat $tmp/US.* > $tmp/US +rm -f $tmp/US.* +cd $tmp +xgraph -tk -bb -t "$const = $constval" -x "$indep ($units)" \ + -y 'User + System time (seconds)' US & +xgraph -tk -bb -t "$const = $constval" -x "$indep ($units)" \ + -y 'Elapsed time (seconds)' R & +xgraph -tk -bb -t "$const = $constval" -x "$indep ($units)" \ + -y 'Wastage (percent of data segment)' W & + diff --git a/lib/libmalloc/tests/regress b/lib/libmalloc/tests/regress new file mode 100755 index 000000000000..322aa608c196 --- /dev/null +++ b/lib/libmalloc/tests/regress @@ -0,0 +1,11 @@ +#! /bin/sh -x +# testmalloc tests some unusual cases -- will test all branches in free, +# which is important. +./testmalloc $@ +# simumalloc makes a good thorough exercise for malloc and free. +# need something for realloc, though. +./simumalloc -t 15000 -s 1024 -l 2000 $@ +./simumalloc -t 5000 -s 512 -l 20 $@ +./simumalloc -d -t 500 -s 512 -l 20 $@ +./simumalloc -d -t 500 -s 512 -l 500 $@ +./simumalloc -d -t 500 -s 512 -a $@ diff --git a/lib/libmalloc/tests/simumalloc.c b/lib/libmalloc/tests/simumalloc.c new file mode 100644 index 000000000000..f4607db3e453 --- /dev/null +++ b/lib/libmalloc/tests/simumalloc.c @@ -0,0 +1,239 @@ +/* + * To measure the speed of malloc - based on the algorithm described in + * "In Search of a Better Malloc" by David G. Korn and Kiem-Phong Vo, + * Usenix 1985. This is a vicious test of memory allocation, but does + * suffer from the problem that it asks for a uniform distribution of + * sizes - a more accurate distribution is a multi-normal distribution + * for all applications I've seen. + */ +/* Mark Moraes, CSRI, University of Toronto */ +#ifndef lint +static char rcsid[] = "$Id: simumalloc.c,v 1.1 1994/03/06 23:01:46 nate Exp $"; +#endif /*lint*/ + +#include <stdio.h> +#include <string.h> + +/* + * ANSI systems had better have this. Non-ANSI systems had better not + * complain about things that are implicitly declared int or void. + */ +#if defined(STDHEADERS) +# include <stdlib.h> +# include <unistd.h> +#endif + +#include "malloc.h" + +char *progname; +/* For getopt() */ +extern int getopt(); +extern int optind; +extern char *optarg; + + +int MaxTime, MaxLife, MaxSize, NumAllocs; + +typedef union u { + union u *ptr; + int size; +} word; + +#define MAXTIME 100000 +static word *bufs[MAXTIME]; + +unsigned long alloced = 0; +static unsigned long maxalloced = 0; + +#ifdef HAVE_RANDOM +extern long random(); +#define rnd(x) (random() % (long) (x)) +#define seedrnd(x) (srandom(x)) +#else /* ! HAVE_RANDOM */ +extern int rand(); +#define rnd(x) (rand() % (x)) +#define seedrnd(x) (srand(x)) +#endif /* HAVE_RANDOM */ + +#ifdef MYMALLOC +extern char * (* _malloc_memfunc)(); +#endif + +/* + * generally sprintf() to errstring and then call complain rather than + * use a varargs routine + */ +char errstring[128]; + +/* + * Should probably have a more fancy version that does perror as well + * in a library someplace - like error() + */ +void +complain(s) +char *s; +{ + (void) fprintf(stderr, "%s: %s\n", progname, s); + exit(-1); +} + +void +usage() +{ + (void) fprintf(stderr, "\ +Usage: %s [-t MaxTime] [-s MaxSize] [-l MaxLife] [-m Mmapfile] [-a] [-d]\n", progname); + exit(-1); +} + +int +main(argc, argv) +int argc; +char **argv; +{ + int c; + register int t; + char *before, *after; + extern char *sbrk(); + extern int atoi(); + extern void freeall(), reserve(); + unsigned long grew; + int alloconly = 0, use_mmap = 0, verbose = 0; + + progname = argv[0] ? argv[0] : "(no-argv[0])"; + NumAllocs = 1; + MaxTime = 15000; + MaxSize = 500; + MaxLife = 1000; + while((c = getopt(argc, argv, "n:t:s:l:dm:av")) != EOF) { + /* optarg has the current argument if the option was followed by ':'*/ + switch (c) { + case 't': + MaxTime = atoi(optarg); + if (MaxTime < 0 || MaxTime > MAXTIME) { + (void) fprintf(stderr, + "%s: MaxTime must be > 0 and < %d\n", progname, MAXTIME); + exit(-1); + } + break; + case 's': + MaxSize = atoi(optarg); + if (MaxSize < 1) + complain("MaxSize must be > 0"); + break; + case 'l': + MaxLife = atoi(optarg); + if (MaxLife < 0) + complain("MaxLife must be > 0"); + break; + case 'n': + NumAllocs = atoi(optarg); + if (NumAllocs <= 0) + complain("NumAllocs must be > 0"); + break; + case 'd': + /* Full heap debugging - S-L-O-W */ +#ifdef MYMALLOC + mal_debug(3); +#endif + break; + case 'm': + use_mmap = 1; +#ifdef MYMALLOC + mal_mmap(optarg); +#else + complain("-m option needs CSRI malloc"); +#endif + break; + case 'a': + /* Only allocate -- no free */ + alloconly = 1; + break; + case 'v': + verbose++; + break; + case '?': + usage(); + break; + } + } + /* Any filenames etc. after all the options */ + if (optind < argc) { + usage(); + } + + for(t = 0; t < MaxTime; t++) + bufs[t] = 0; + +#ifdef MYMALLOC + before = (* _malloc_memfunc)(0); +#else + before = sbrk(0); +#endif + for(t = 0; t < MaxTime; t++) { + register int n; + + for(n = rnd(NumAllocs) + 1; n > 0; n--) { + int s, l; + + s = rnd(MaxSize) + 2; + l = rnd(MaxLife) + 1; + reserve(s, t + l); + } + if (! alloconly) + freeall(t); + } +#ifdef MYMALLOC + after = (* _malloc_memfunc)(0); +#else + after = sbrk(0); +#endif + grew = after - before; + (void) sprintf(errstring, "Sbrked %ld, MaxAlloced %ld, Wastage %.2f\n", + grew, maxalloced * sizeof(word), + grew == 0 ? 0.0 : + (1.0 - ((double) maxalloced * sizeof(word)) / grew)); + (void) write(1, errstring, strlen(errstring)); +#ifdef MYMALLOC + if (verbose) + (void) mal_statsdump(stderr); +#endif + return 0; +} + +/* + * Mallocs a block s words long, and adds it to the list of blocks to + * be freed at time tfree + */ +void +reserve(s, tfree) +int s; +int tfree; +{ + word *wp; + + wp = (word *) malloc(s * sizeof(word)); + if (wp == NULL) + complain("Out of memory"); + wp[0].ptr = bufs[tfree]; + wp[1].size = s; + bufs[tfree] = wp; + alloced += s; + if (alloced > maxalloced) + maxalloced = alloced; +} + +/* free all blocks whose lifetime expires at time t */ +void +freeall(t) +int t; +{ + word *wp; + + wp = bufs[t]; + while(wp != NULL) { + word *tmp = wp[0].ptr; + alloced -= wp[1].size; + free((char *) wp); + wp = tmp; + } +} diff --git a/lib/libmalloc/tests/t1.c b/lib/libmalloc/tests/t1.c new file mode 100644 index 000000000000..7cdde93e4946 --- /dev/null +++ b/lib/libmalloc/tests/t1.c @@ -0,0 +1,40 @@ +#include <stdio.h> + +#define MAXALLOCS 1000 +#define SIZE 50 + +extern char *sbrk(); +extern char *malloc(); + +main() +{ + char *ptr[MAXALLOCS]; + char *obrk, *nbrk; + int i; + + obrk = sbrk(0); + printf("break is initially 0x%x\n", obrk); + + for(i = 0; i < MAXALLOCS; i++) { + ptr[i] = malloc(SIZE); + } + nbrk = sbrk(0); + printf("break is 0x%x (%d bytes sbrked) after %d allocations of %d\n", + nbrk, nbrk - obrk, MAXALLOCS, SIZE); + for(i = 0; i < MAXALLOCS; i++) { + free(ptr[i]); + } + nbrk = sbrk(0); + printf("break is 0x%x (%d bytes sbrked) after freeing all allocations\n", + nbrk, nbrk - obrk); + fflush(stdout); + + /* Should be enough memory for this without needing to sbrk */ + (void) malloc(SIZE * (MAXALLOCS / 2)); + nbrk = sbrk(0); + + printf("break is 0x%x (%d bytes sbrked) after allocating %d\n", + nbrk, nbrk - obrk, SIZE * (MAXALLOCS/2)); + + exit(0); +} diff --git a/lib/libmalloc/tests/t2.c b/lib/libmalloc/tests/t2.c new file mode 100644 index 000000000000..125c251e42b1 --- /dev/null +++ b/lib/libmalloc/tests/t2.c @@ -0,0 +1,37 @@ +#include <stdio.h> + +#define MAXALLOCS 100 +#define INC 50 + +extern char *sbrk(); +extern char *malloc(); + +main() +{ + char *ptr1, *ptr2; + char *obrk, *nbrk; + int i; + int small = 10; + int large = 128; + + obrk = sbrk(0); + printf("break is initially 0x%x\n", obrk); + + ptr1 = malloc(small); + ptr2 = malloc(small); + for(i = 0; i < MAXALLOCS; i++) { + (void) malloc(small); + free(ptr1); + ptr1 = malloc(large); + large += INC; + (void) malloc(small); + free(ptr2); + ptr2 = malloc(large); + large += INC; + mal_heapdump(stdout); + } + nbrk = sbrk(0); + printf("break is 0x%x (%d bytes sbrked)\n", + nbrk, nbrk - obrk); + exit(0); +} diff --git a/lib/libmalloc/tests/t3.c b/lib/libmalloc/tests/t3.c new file mode 100644 index 000000000000..fdbc181e54f7 --- /dev/null +++ b/lib/libmalloc/tests/t3.c @@ -0,0 +1,110 @@ +/* +Path: utstat!helios.physics.utoronto.ca!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!cs.utexas.edu!rice!sun-spots-request +From: munsell!jwf@uunet.uu.net (Jim Franklin) +Newsgroups: comp.sys.sun +Subject: bug in SUN malloc() +Keywords: Miscellaneous +Message-ID: <4193@brazos.Rice.edu> +Date: 4 Jan 90 13:05:06 GMT +Sender: root@rice.edu +Organization: Sun-Spots +Lines: 95 +Approved: Sun-Spots@rice.edu +X-Sun-Spots-Digest: Volume 9, Issue 4, message 10 of 12 + +There is a bug in SUN's malloc() that causes it to sometimes attempt an +sbrk() to grow the current process, even if there is a free block of the +exact size available. The bug exists in OS 3.5 and 4.0.3, probably +others. + +SUN's malloc() maintains the free list in a cartesian tree. The malloc() +bug occurs when the root block is exactly equal in size to the requested +allocation + alignment + overhead. + +malloc.c (416-427): +> /-* +> * ensure that at least one block is big enough to satisfy +> * the request. +> *-/ +> +> if (weight(_root) <= nbytes) { +> /-* +> * the largest block is not enough. +> *-/ +> if(!morecore(nbytes)) +> return 0; +> } + +The '<=' should be '<'. + +The following 'malloc_bug' program illustrates the bug. Do a 'pstat -s' +to see how much swap space you have, then run malloc_bug, requesting a +chunk of memory at least 1/2 that size. E.g., + +jwf@fechner #36 pstat -s +8856k used (2120k text), 648872k free, 2776k wasted, 0k missing +max process allocable = 229360k +avail: 77*8192k 2*4096k 2*2048k 3*1024k 2*512k 3*256k 4*128k 3*64k 2*32k 4*16k 104*1k + +jwf@fechner #37 malloc_bug 200000000 +malloc_bug: requesting 200000000 bytes +malloc_bug: got 200000000 bytes at 00022fd8 +malloc_bug: freeing 200000000 bytes +malloc_bug: requesting 200000000 bytes +malloc_bug: Not enough memory + + +Jim Franklin, EPPS Inc., uunet!atexnet ---\ +32 Wiggins Ave., harvard!adelie ---+-- munsell!jwf +Bedford, MA 01730 decvax!encore ---/ +(617) 276-7827 + + +*/ +#include <stdio.h> + +main (argc, argv) +int argc; +char **argv; +{ + char *p; + unsigned int size; + int i; + extern char *malloc (); + + if ( argc != 2 ) { + fprintf (stderr, "usage: malloc_bug <chunk_size>\n"); + exit (-1); + } + size = atoi (argv[1]); + /* malloc our large chunk */ + + fprintf (stderr, "malloc_bug: requesting %d bytes\n", size); + p = malloc (size); + if ( p == NULL ) { + perror ("malloc_bug"); + exit (-1); + } + fprintf (stderr, "malloc_bug: got %d bytes at %08x\n", size, p); + + /* malloc a bunch of small trash to + try to use up any free fragments + near the large chunk */ + for ( i = 0; i < 2000; i++ ) + (void) malloc (8); + /* repeatedly free and malloc the + large chunk -- if this fails then + malloc is broken ... */ + for (;;) { + fprintf (stderr, "malloc_bug: freeing %d bytes\n", size); + free (p); + fprintf (stderr, "malloc_bug: requesting %d bytes\n", size); + p = malloc (size); + if ( p == NULL ) { + perror ("malloc_bug"); + exit (-1); + } + fprintf (stderr, "malloc_bug: got %d bytes at %08x\n", size, p); + } + +} /* main */ diff --git a/lib/libmalloc/tests/t4.c b/lib/libmalloc/tests/t4.c new file mode 100644 index 000000000000..45161ad0cd49 --- /dev/null +++ b/lib/libmalloc/tests/t4.c @@ -0,0 +1,20 @@ +int +main() +{ + char *cp; + int i; + int n = getpagesize(); + extern char *malloc(); + + printf("pagesize = %d\n", n); + + for(i = 0; i < 5; i++) { + cp = malloc(n); + printf("malloc(%d) returned 0x%x\n", n, cp); + cp = malloc(2*n); + printf("malloc(%d) returned 0x%x\n", 2*n, cp); + cp = malloc(4*n); + printf("malloc(%d) returned 0x%x\n", 4*n, cp); + } + return 0; +} diff --git a/lib/libmalloc/tests/t5.c b/lib/libmalloc/tests/t5.c new file mode 100644 index 000000000000..f25df6045594 --- /dev/null +++ b/lib/libmalloc/tests/t5.c @@ -0,0 +1,31 @@ +/* + * posted to the net by someone who asked "Why is this causing malloc to + * dump core! Modified slightly to free the pointers, which causes my + * debugging malloc to find the bug. Turning on malloc_debug(2) also + * spots the problem. + */ +#include <stdio.h> + +int +main() +{ + char *p[3], wd[128]; + int len, i; + char *malloc(); + int strlen(); + + strcpy(wd,"test"); + + for (i=0; i<3; i++) { + len = strlen(wd); + if ((p[i] = malloc(len)) == NULL) { + printf("ERROR: malloc failed\n"); + exit(-1); + } + else + strcpy(p[i],wd); + } + for(i=0; i < 3; i++) + free(p[i]); + return 0; +} diff --git a/lib/libmalloc/tests/test.out b/lib/libmalloc/tests/test.out new file mode 100644 index 000000000000..49d51d139cf6 --- /dev/null +++ b/lib/libmalloc/tests/test.out @@ -0,0 +1,415 @@ +Malloc tracing starting +Test starting +testmalloc.c:48:sbrk 4096 +heapstart 0x23108 +heapend 0x24100 ++ 100 100 0x23114 +Heap printout: +Rover pointer is 0x240fc +Arena from 0x23104 to 0x24100, 1024 (0x400) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Free blk: 0x2317c to 0x240fc, 993 (0x3e1) words next=0x240fc, prev=0x240fc +============== +testmalloc.c:51:+ 150 152 0x23184 +Heap printout: +Rover pointer is 0x240fc +Arena from 0x23104 to 0x24100, 1024 (0x400) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Allocated blk: 0x2317c to 0x2321c, 41 (0x29) words really 150 bytes + Free blk: 0x23220 to 0x240fc, 952 (0x3b8) words next=0x240fc, prev=0x240fc +============== +testmalloc.c:54:+ 191 192 0x23228 +Heap printout: +Rover pointer is 0x240fc +Arena from 0x23104 to 0x24100, 1024 (0x400) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Allocated blk: 0x2317c to 0x2321c, 41 (0x29) words really 150 bytes + Allocated blk: 0x23220 to 0x232e8, 51 (0x33) words really 191 bytes + Free blk: 0x232ec to 0x240fc, 901 (0x385) words next=0x240fc, prev=0x240fc +============== +testmalloc.c:57:+ 2 4 0x232f4 +Heap printout: +Rover pointer is 0x240fc +Arena from 0x23104 to 0x24100, 1024 (0x400) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Allocated blk: 0x2317c to 0x2321c, 41 (0x29) words really 150 bytes + Allocated blk: 0x23220 to 0x232e8, 51 (0x33) words really 191 bytes + Allocated blk: 0x232ec to 0x232f8, 4 (0x4) words really 2 bytes + Free blk: 0x232fc to 0x240fc, 897 (0x381) words next=0x240fc, prev=0x240fc +============== +testmalloc.c:60:+ 21 24 0x23304 +Heap printout: +Rover pointer is 0x240fc +Arena from 0x23104 to 0x24100, 1024 (0x400) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Allocated blk: 0x2317c to 0x2321c, 41 (0x29) words really 150 bytes + Allocated blk: 0x23220 to 0x232e8, 51 (0x33) words really 191 bytes + Allocated blk: 0x232ec to 0x232f8, 4 (0x4) words really 2 bytes + Allocated blk: 0x232fc to 0x2331c, 9 (0x9) words really 21 bytes + Free blk: 0x23320 to 0x240fc, 888 (0x378) words next=0x240fc, prev=0x240fc +============== +testmalloc.c:63:+ 3540 3540 0x23328 +Heap printout: +Rover pointer is 0x0 +Arena from 0x23104 to 0x24100, 1024 (0x400) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Allocated blk: 0x2317c to 0x2321c, 41 (0x29) words really 150 bytes + Allocated blk: 0x23220 to 0x232e8, 51 (0x33) words really 191 bytes + Allocated blk: 0x232ec to 0x232f8, 4 (0x4) words really 2 bytes + Allocated blk: 0x232fc to 0x2331c, 9 (0x9) words really 21 bytes + Allocated blk: 0x23320 to 0x240fc, 888 (0x378) words really 3540 bytes +============== +testmalloc.c:67:- 3540 0x23328 +Heap printout: +Rover pointer is 0x240fc +Arena from 0x23104 to 0x24100, 1024 (0x400) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Allocated blk: 0x2317c to 0x2321c, 41 (0x29) words really 150 bytes + Allocated blk: 0x23220 to 0x232e8, 51 (0x33) words really 191 bytes + Allocated blk: 0x232ec to 0x232f8, 4 (0x4) words really 2 bytes + Allocated blk: 0x232fc to 0x2331c, 9 (0x9) words really 21 bytes + Free blk: 0x23320 to 0x240fc, 888 (0x378) words next=0x240fc, prev=0x240fc +============== +testmalloc.c:69:- 192 0x23228 +Heap printout: +Rover pointer is 0x232e8 +Arena from 0x23104 to 0x24100, 1024 (0x400) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Allocated blk: 0x2317c to 0x2321c, 41 (0x29) words really 150 bytes + Free blk: 0x23220 to 0x232e8, 51 (0x33) words next=0x240fc, prev=0x240fc + Allocated blk: 0x232ec to 0x232f8, 4 (0x4) words really 2 bytes + Allocated blk: 0x232fc to 0x2331c, 9 (0x9) words really 21 bytes + Free blk: 0x23320 to 0x240fc, 888 (0x378) words next=0x232e8, prev=0x232e8 +============== +testmalloc.c:71:- 4 0x232f4 +Heap printout: +Rover pointer is 0x232f8 +Arena from 0x23104 to 0x24100, 1024 (0x400) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Allocated blk: 0x2317c to 0x2321c, 41 (0x29) words really 150 bytes + Free blk: 0x23220 to 0x232f8, 55 (0x37) words next=0x240fc, prev=0x240fc + Allocated blk: 0x232fc to 0x2331c, 9 (0x9) words really 21 bytes + Free blk: 0x23320 to 0x240fc, 888 (0x378) words next=0x232f8, prev=0x232f8 +============== +testmalloc.c:73:- 152 0x23184 +Heap printout: +Rover pointer is 0x232f8 +Arena from 0x23104 to 0x24100, 1024 (0x400) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Free blk: 0x2317c to 0x232f8, 96 (0x60) words next=0x240fc, prev=0x240fc + Allocated blk: 0x232fc to 0x2331c, 9 (0x9) words really 21 bytes + Free blk: 0x23320 to 0x240fc, 888 (0x378) words next=0x232f8, prev=0x232f8 +============== +testmalloc.c:75:- 24 0x23304 +Heap printout: +Rover pointer is 0x240fc +Arena from 0x23104 to 0x24100, 1024 (0x400) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Free blk: 0x2317c to 0x240fc, 993 (0x3e1) words next=0x240fc, prev=0x240fc +============== +testmalloc.c:77:- 100 0x23114 +Heap printout: +Rover pointer is 0x240fc +Arena from 0x23104 to 0x24100, 1024 (0x400) words +Next arena is 0x0 + Free blk: 0x2310c to 0x240fc, 1021 (0x3fd) words next=0x240fc, prev=0x240fc +============== +testmalloc.c:79:+ 100 100 0x23114 +Heap printout: +Rover pointer is 0x240fc +Arena from 0x23104 to 0x24100, 1024 (0x400) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Free blk: 0x2317c to 0x240fc, 993 (0x3e1) words next=0x240fc, prev=0x240fc +============== +testmalloc.c:82:+ 155 156 0x23184 +Heap printout: +Rover pointer is 0x240fc +Arena from 0x23104 to 0x24100, 1024 (0x400) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Allocated blk: 0x2317c to 0x23220, 42 (0x2a) words really 155 bytes + Free blk: 0x23224 to 0x240fc, 951 (0x3b7) words next=0x240fc, prev=0x240fc +============== +testmalloc.c:85:sbrk 12288 +- 12276 0x24108 ++ 8192 8192 0x2322c +Heap printout: +Rover pointer is 0x270fc +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Allocated blk: 0x2317c to 0x23220, 42 (0x2a) words really 155 bytes + Allocated blk: 0x23224 to 0x2522c, 2051 (0x803) words really 8192 bytes + Free blk: 0x25230 to 0x270fc, 1972 (0x7b4) words next=0x270fc, prev=0x270fc +============== +testmalloc.c:88:+ 100 100 0x25238 +Heap printout: +Rover pointer is 0x270fc +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Allocated blk: 0x2317c to 0x23220, 42 (0x2a) words really 155 bytes + Allocated blk: 0x23224 to 0x2522c, 2051 (0x803) words really 8192 bytes + Allocated blk: 0x25230 to 0x2529c, 28 (0x1c) words really 100 bytes + Free blk: 0x252a0 to 0x270fc, 1944 (0x798) words next=0x270fc, prev=0x270fc +============== +testmalloc.c:91:+ 29 32 0x252a8 +Heap printout: +Rover pointer is 0x270fc +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Allocated blk: 0x2317c to 0x23220, 42 (0x2a) words really 155 bytes + Allocated blk: 0x23224 to 0x2522c, 2051 (0x803) words really 8192 bytes + Allocated blk: 0x25230 to 0x2529c, 28 (0x1c) words really 100 bytes + Allocated blk: 0x252a0 to 0x252c8, 11 (0xb) words really 29 bytes + Free blk: 0x252cc to 0x270fc, 1933 (0x78d) words next=0x270fc, prev=0x270fc +============== +testmalloc.c:94:- 8192 0x2322c +Heap printout: +Rover pointer is 0x2522c +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Allocated blk: 0x2317c to 0x23220, 42 (0x2a) words really 155 bytes + Free blk: 0x23224 to 0x2522c, 2051 (0x803) words next=0x270fc, prev=0x270fc + Allocated blk: 0x25230 to 0x2529c, 28 (0x1c) words really 100 bytes + Allocated blk: 0x252a0 to 0x252c8, 11 (0xb) words really 29 bytes + Free blk: 0x252cc to 0x270fc, 1933 (0x78d) words next=0x2522c, prev=0x2522c +============== +testmalloc.c:96:- 100 0x25238 +Heap printout: +Rover pointer is 0x2529c +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Allocated blk: 0x2317c to 0x23220, 42 (0x2a) words really 155 bytes + Free blk: 0x23224 to 0x2529c, 2079 (0x81f) words next=0x270fc, prev=0x270fc + Allocated blk: 0x252a0 to 0x252c8, 11 (0xb) words really 29 bytes + Free blk: 0x252cc to 0x270fc, 1933 (0x78d) words next=0x2529c, prev=0x2529c +============== +testmalloc.c:98:- 156 0x23184 +Heap printout: +Rover pointer is 0x2529c +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Free blk: 0x2317c to 0x2529c, 2121 (0x849) words next=0x270fc, prev=0x270fc + Allocated blk: 0x252a0 to 0x252c8, 11 (0xb) words really 29 bytes + Free blk: 0x252cc to 0x270fc, 1933 (0x78d) words next=0x2529c, prev=0x2529c +============== +testmalloc.c:100:- 32 0x252a8 +Heap printout: +Rover pointer is 0x270fc +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23178, 28 (0x1c) words really 100 bytes + Free blk: 0x2317c to 0x270fc, 4065 (0xfe1) words next=0x270fc, prev=0x270fc +============== +testmalloc.c:102:- 100 0x23114 +Heap printout: +Rover pointer is 0x270fc +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Free blk: 0x2310c to 0x270fc, 4093 (0xffd) words next=0x270fc, prev=0x270fc +============== +testmalloc.c:105:+ 1005 1008 0x23114 +Heap printout: +Rover pointer is 0x270fc +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23504, 255 (0xff) words really 1005 bytes + Free blk: 0x23508 to 0x270fc, 3838 (0xefe) words next=0x270fc, prev=0x270fc +============== +testmalloc.c:108:+ 8192 8192 0x23510 +Heap printout: +Rover pointer is 0x270fc +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23504, 255 (0xff) words really 1005 bytes + Allocated blk: 0x23508 to 0x25510, 2051 (0x803) words really 8192 bytes + Free blk: 0x25514 to 0x270fc, 1787 (0x6fb) words next=0x270fc, prev=0x270fc +============== +testmalloc.c:111:sbrk 16384 +heapend 0x2b164 ++ 16000 16000 0x27178 +Heap printout: +Rover pointer is 0x2b160 +Arena from 0x27168 to 0x2b164, 4096 (0x1000) words +Next arena is 0x23104 + Allocated blk: 0x27170 to 0x2aff8, 4003 (0xfa3) words really 16000 bytes + Free blk: 0x2affc to 0x2b160, 90 (0x5a) words next=0x270fc, prev=0x270fc +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23504, 255 (0xff) words really 1005 bytes + Allocated blk: 0x23508 to 0x25510, 2051 (0x803) words really 8192 bytes + Free blk: 0x25514 to 0x270fc, 1787 (0x6fb) words next=0x2b160, prev=0x2b160 +============== +testmalloc.c:114:+ 29 32 0x2b004 +Heap printout: +Rover pointer is 0x2b160 +Arena from 0x27168 to 0x2b164, 4096 (0x1000) words +Next arena is 0x23104 + Allocated blk: 0x27170 to 0x2aff8, 4003 (0xfa3) words really 16000 bytes + Allocated blk: 0x2affc to 0x2b024, 11 (0xb) words really 29 bytes + Free blk: 0x2b028 to 0x2b160, 79 (0x4f) words next=0x270fc, prev=0x270fc +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23504, 255 (0xff) words really 1005 bytes + Allocated blk: 0x23508 to 0x25510, 2051 (0x803) words really 8192 bytes + Free blk: 0x25514 to 0x270fc, 1787 (0x6fb) words next=0x2b160, prev=0x2b160 +============== +testmalloc.c:118:sbrk 77824 +- 77812 0x2b16c ++ 73727 73728 0x2b030 +- 4132 0x3c00c +- 4036 0x2b030 +Heap printout: +Rover pointer is 0x2bff4 +Arena from 0x27168 to 0x3e164, 23552 (0x5c00) words +Next arena is 0x23104 + Allocated blk: 0x27170 to 0x2aff8, 4003 (0xfa3) words really 16000 bytes + Allocated blk: 0x2affc to 0x2b024, 11 (0xb) words really 29 bytes + Free blk: 0x2b028 to 0x2bff4, 1012 (0x3f4) words next=0x3e160, prev=0x270fc + Allocated blk: 0x2bff8 to 0x3c000, 16387 (0x4003) words really 65536 bytes + Free blk: 0x3c004 to 0x3e160, 2136 (0x858) words next=0x270fc, prev=0x2bff4 +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23504, 255 (0xff) words really 1005 bytes + Allocated blk: 0x23508 to 0x25510, 2051 (0x803) words really 8192 bytes + Free blk: 0x25514 to 0x270fc, 1787 (0x6fb) words next=0x2bff4, prev=0x3e160 +============== +testmalloc.c:121:- 57524 0x2df4c +Heap printout: +Rover pointer is 0x3e160 +Arena from 0x27168 to 0x3e164, 23552 (0x5c00) words +Next arena is 0x23104 + Allocated blk: 0x27170 to 0x2aff8, 4003 (0xfa3) words really 16000 bytes + Allocated blk: 0x2affc to 0x2b024, 11 (0xb) words really 29 bytes + Free blk: 0x2b028 to 0x2bff4, 1012 (0x3f4) words next=0x3e160, prev=0x270fc + Allocated blk: 0x2bff8 to 0x2df40, 2003 (0x7d3) words really 8000 bytes + Free blk: 0x2df44 to 0x3e160, 16520 (0x4088) words next=0x270fc, prev=0x2bff4 +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23504, 255 (0xff) words really 1005 bytes + Allocated blk: 0x23508 to 0x25510, 2051 (0x803) words really 8192 bytes + Free blk: 0x25514 to 0x270fc, 1787 (0x6fb) words next=0x2bff4, prev=0x3e160 +============== +testmalloc.c:124:no-op +Heap printout: +Rover pointer is 0x3e160 +Arena from 0x27168 to 0x3e164, 23552 (0x5c00) words +Next arena is 0x23104 + Allocated blk: 0x27170 to 0x2aff8, 4003 (0xfa3) words really 16000 bytes + Allocated blk: 0x2affc to 0x2b024, 11 (0xb) words really 29 bytes + Free blk: 0x2b028 to 0x2bff4, 1012 (0x3f4) words next=0x3e160, prev=0x270fc + Allocated blk: 0x2bff8 to 0x2df40, 2003 (0x7d3) words really 7998 bytes + Free blk: 0x2df44 to 0x3e160, 16520 (0x4088) words next=0x270fc, prev=0x2bff4 +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Allocated blk: 0x2310c to 0x23504, 255 (0xff) words really 1005 bytes + Allocated blk: 0x23508 to 0x25510, 2051 (0x803) words really 8192 bytes + Free blk: 0x25514 to 0x270fc, 1787 (0x6fb) words next=0x2bff4, prev=0x3e160 +============== +testmalloc.c:127:- 1008 0x23114 +Heap printout: +Rover pointer is 0x23504 +Arena from 0x27168 to 0x3e164, 23552 (0x5c00) words +Next arena is 0x23104 + Allocated blk: 0x27170 to 0x2aff8, 4003 (0xfa3) words really 16000 bytes + Allocated blk: 0x2affc to 0x2b024, 11 (0xb) words really 29 bytes + Free blk: 0x2b028 to 0x2bff4, 1012 (0x3f4) words next=0x23504, prev=0x270fc + Allocated blk: 0x2bff8 to 0x2df40, 2003 (0x7d3) words really 7998 bytes + Free blk: 0x2df44 to 0x3e160, 16520 (0x4088) words next=0x270fc, prev=0x23504 +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Free blk: 0x2310c to 0x23504, 255 (0xff) words next=0x3e160, prev=0x2bff4 + Allocated blk: 0x23508 to 0x25510, 2051 (0x803) words really 8192 bytes + Free blk: 0x25514 to 0x270fc, 1787 (0x6fb) words next=0x2bff4, prev=0x3e160 +============== +testmalloc.c:129:- 8192 0x23510 +Heap printout: +Rover pointer is 0x270fc +Arena from 0x27168 to 0x3e164, 23552 (0x5c00) words +Next arena is 0x23104 + Allocated blk: 0x27170 to 0x2aff8, 4003 (0xfa3) words really 16000 bytes + Allocated blk: 0x2affc to 0x2b024, 11 (0xb) words really 29 bytes + Free blk: 0x2b028 to 0x2bff4, 1012 (0x3f4) words next=0x3e160, prev=0x270fc + Allocated blk: 0x2bff8 to 0x2df40, 2003 (0x7d3) words really 7998 bytes + Free blk: 0x2df44 to 0x3e160, 16520 (0x4088) words next=0x270fc, prev=0x2bff4 +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Free blk: 0x2310c to 0x270fc, 4093 (0xffd) words next=0x2bff4, prev=0x3e160 +============== +testmalloc.c:131:- 32 0x2b004 +Heap printout: +Rover pointer is 0x2bff4 +Arena from 0x27168 to 0x3e164, 23552 (0x5c00) words +Next arena is 0x23104 + Allocated blk: 0x27170 to 0x2aff8, 4003 (0xfa3) words really 16000 bytes + Free blk: 0x2affc to 0x2bff4, 1023 (0x3ff) words next=0x3e160, prev=0x270fc + Allocated blk: 0x2bff8 to 0x2df40, 2003 (0x7d3) words really 7998 bytes + Free blk: 0x2df44 to 0x3e160, 16520 (0x4088) words next=0x270fc, prev=0x2bff4 +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Free blk: 0x2310c to 0x270fc, 4093 (0xffd) words next=0x2bff4, prev=0x3e160 +============== +testmalloc.c:133:- 16000 0x27178 +Heap printout: +Rover pointer is 0x2bff4 +Arena from 0x27168 to 0x3e164, 23552 (0x5c00) words +Next arena is 0x23104 + Free blk: 0x27170 to 0x2bff4, 5026 (0x13a2) words next=0x3e160, prev=0x270fc + Allocated blk: 0x2bff8 to 0x2df40, 2003 (0x7d3) words really 7998 bytes + Free blk: 0x2df44 to 0x3e160, 16520 (0x4088) words next=0x270fc, prev=0x2bff4 +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Free blk: 0x2310c to 0x270fc, 4093 (0xffd) words next=0x2bff4, prev=0x3e160 +============== +testmalloc.c:135:++ 16000 16000 0x2c000 58080 0x2fe84 +Heap printout: +Rover pointer is 0x2bff4 +Arena from 0x27168 to 0x3e164, 23552 (0x5c00) words +Next arena is 0x23104 + Free blk: 0x27170 to 0x2bff4, 5026 (0x13a2) words next=0x3e160, prev=0x270fc + Allocated blk: 0x2bff8 to 0x2fe80, 4003 (0xfa3) words really 16000 bytes + Free blk: 0x2fe84 to 0x3e160, 14520 (0x38b8) words next=0x270fc, prev=0x2bff4 +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Free blk: 0x2310c to 0x270fc, 4093 (0xffd) words next=0x2bff4, prev=0x3e160 +============== +testmalloc.c:138:++ 32000 32000 0x2c000 42080 0x33d04 +Heap printout: +Rover pointer is 0x2bff4 +Arena from 0x27168 to 0x3e164, 23552 (0x5c00) words +Next arena is 0x23104 + Free blk: 0x27170 to 0x2bff4, 5026 (0x13a2) words next=0x3e160, prev=0x270fc + Allocated blk: 0x2bff8 to 0x33d00, 8003 (0x1f43) words really 32000 bytes + Free blk: 0x33d04 to 0x3e160, 10520 (0x2918) words next=0x270fc, prev=0x2bff4 +Arena from 0x23104 to 0x27100, 4096 (0x1000) words +Next arena is 0x0 + Free blk: 0x2310c to 0x270fc, 4093 (0xffd) words next=0x2bff4, prev=0x3e160 +============== +16: 1 +36: 1 +44: 2 +112: 3 +164: 1 +168: 1 +204: 1 +1020: 1 +3552: 1 +>= 8192: 4 +Test done diff --git a/lib/libmalloc/tests/testmalloc.c b/lib/libmalloc/tests/testmalloc.c new file mode 100644 index 000000000000..d037b5e1bf00 --- /dev/null +++ b/lib/libmalloc/tests/testmalloc.c @@ -0,0 +1,182 @@ +#if defined(STDHEADERS) +# include <stddef.h> +# include <string.h> +# include <stdlib.h> +# include <unistd.h> +#else +# define u_int unsigned int +extern char *memset(); +/* ignore some complaints about declarations. get ANSI headers */ +#endif + +#include <stdio.h> +#include "malloc.h" + +/* + * Things to test. 1. first malloc. 2. couple of ordinary mallocs 3. + * ordinary frees 4. want check a free with prev. merge, next merge, + * both, and no merge, and one with empty free list. 5. malloc that + * requires sbrk. 6. malloc that requires an sbrk, after test + * program does non-contiguous sbrk to check if non-contigous arenas + * work. 7. valloc (this should test memalign as well) We should work + * out tests to check boundary conditions, when blocks at the start + * of the arena are allocated/freed, last free block is allocated... + */ + + +char *progname; +/* For getopt() */ +extern int getopt(); +extern int optind; +extern char *optarg; + +int +main(argc, argv) +int argc; +char **argv; +{ + char *cp1; + char *cp2; + char *cp3; + char *cp4; + char *cp5; + char *cp6; + extern char *sbrk(); + FILE *dumpfp = stdout; + int errs = 0, c; + + progname = argv[0] ? argv[0] : "(no-argv[0])"; + mal_debug(3); + mal_setstatsfile(stdout); + mal_trace(1); + while((c = getopt(argc, argv, "m:")) != EOF) { + /* optarg has the current argument if the option was followed by ':'*/ + switch (c) { + case 'm': + mal_mmap(optarg); + break; + case '?': + errs++; + break; + } + } + if (optind < argc || errs > 0) { + fprintf(stderr, "Usage: %s [-m Mmapfile]\n", progname); + exit(1); + } + write(1, "Test starting\n", 14); + cp1 = (char *)malloc((u_int) 100); + (void) memset(cp1, 'A', 100); + mal_heapdump(dumpfp); + cp2 = (char *)calloc((u_int) 15, (u_int) 10); + (void) memset(cp2, 'B', 150); + mal_heapdump(dumpfp); + cp3 = (char *)malloc((u_int) 191); + (void) memset(cp3, 'C', 191); + mal_heapdump(dumpfp); + cp4 = (char *)malloc((u_int) 2); + (void) memset(cp4, 'D', 2); + mal_heapdump(dumpfp); + cp5 = (char *)malloc((u_int) 21); + (void) memset(cp5, 'E', 21); + mal_heapdump(dumpfp); + cp6 = (char *)malloc((u_int) 3540); + (void) memset(cp6, 'P', 3540); + mal_heapdump(dumpfp); + /* On a machine where sizeof(Word) == 4, rover should be NULL here */ + free(cp6); + mal_heapdump(dumpfp); + free(cp3); + mal_heapdump(dumpfp); + free(cp4); + mal_heapdump(dumpfp); + free(cp2); + mal_heapdump(dumpfp); + free(cp5); + mal_heapdump(dumpfp); + free(cp1); + mal_heapdump(dumpfp); + cp1 = (char *)malloc((u_int) 100); + (void) memset(cp1, 'Q', 100); + mal_heapdump(dumpfp); + cp2 = (char *)malloc((u_int) 155); + (void) memset(cp2, 'F', 155); + mal_heapdump(dumpfp); + cp3 = (char *)malloc((u_int) 8192); + (void) memset(cp3, 'G', 8192); + mal_heapdump(dumpfp); + cp4 = (char *)malloc((u_int) 100); + (void) memset(cp4, 'H', 100); + mal_heapdump(dumpfp); + cp5 = (char *)malloc((u_int) 29); + (void) memset(cp5, 'I', 29); + mal_heapdump(dumpfp); + free(cp3); + mal_heapdump(dumpfp); + free(cp4); + mal_heapdump(dumpfp); + free(cp2); + mal_heapdump(dumpfp); + free(cp5); + mal_heapdump(dumpfp); + free(cp1); + mal_heapdump(dumpfp); + cp1 = sbrk(100); + cp2 = (char *)malloc((u_int) 1005); + (void) memset(cp2, 'J', 1005); + mal_heapdump(dumpfp); + cp3 = (char *)calloc((u_int) 1024, (u_int) 8); + (void) memset(cp3, 'K', 8192); + mal_heapdump(dumpfp); + cp4 = (char *)malloc((u_int) 16000); + (void) memset(cp4, 'L', 16000); + mal_heapdump(dumpfp); + cp5 = (char *)malloc((u_int) 29); + (void) memset(cp5, 'M', 29); + mal_heapdump(dumpfp); + /* !! Should really test memalign with various cases */ + cp1 = (char *)valloc((u_int) 65536); + (void) memset(cp1, 'N', 65536); + mal_heapdump(dumpfp); + cp1 = (char *)realloc(cp1, (u_int) 8000); + (void) memset(cp1, 'O', 8000); + mal_heapdump(dumpfp); + cp1 = (char *)realloc(cp1, (u_int) 7998); + (void) memset(cp1, 'T', 7998); + mal_heapdump(dumpfp); + free(cp2); + mal_heapdump(dumpfp); + free(cp3); + mal_heapdump(dumpfp); + free(cp5); + mal_heapdump(dumpfp); + free(cp4); + mal_heapdump(dumpfp); + cp1 = (char *)realloc(cp1, (u_int) 16000); + (void) memset(cp1, 'R', 16000); + mal_heapdump(dumpfp); + cp1 = (char *)realloc(cp1, (u_int) 32000); + (void) memset(cp1, 'S', 32000); + mal_heapdump(dumpfp); + cp1 = (char *)realloc(cp1, (u_int) 1); + (void) memset(cp1, 'U', 1); + cp2 = (char *)malloc(60000); + (void) memset(cp2, 'V', 60000); + cp3 = (char *)malloc(18000); + (void) memset(cp3, 'W', 18000); + cp4 = (char *)malloc(18000); + (void) memset(cp4, 'W', 18000); + mal_heapdump(dumpfp); + free(cp1); + mal_heapdump(dumpfp); + mal_statsdump(dumpfp); + (void) write(1, "Test done\n", 10); + return 0; +} + +#ifdef atarist +getpagesize() +{ + return 8 * 1024; +} +#endif diff --git a/lib/libmalloc/tests/testmemalign.c b/lib/libmalloc/tests/testmemalign.c new file mode 100644 index 000000000000..2a5a729a9675 --- /dev/null +++ b/lib/libmalloc/tests/testmemalign.c @@ -0,0 +1,16 @@ +int +main() +{ + extern char *memalign(); + char *cp; + + if ((cp = memalign(2, 1024)) == 0) + perror("memalign 2"); + if ((cp = memalign(3, 1024)) == 0) + perror("memalign 3"); + if ((cp = memalign(4, 1024)) == 0) + perror("memalign 4"); + + return 0; +} + diff --git a/lib/libmalloc/tests/testrun.sh b/lib/libmalloc/tests/testrun.sh new file mode 100755 index 000000000000..9da9568d2cdf --- /dev/null +++ b/lib/libmalloc/tests/testrun.sh @@ -0,0 +1,28 @@ +#! /bin/sh +time=time +awk 'BEGIN { + maxtime = 15000; + maxsize = 610; isize = 50; + maxlife = 8010; ilife = 100; + hdrfmt = "echo \"Maxtime = %d, Maxsize = %d, Maxlife = %d\"\n"; + fmt = "$time $cmd -t %d -s %d -l %d\n"; + } + END { + for (i = 10; i < maxsize; i += isize) { + for (j = 10; j < maxlife; j += ilife) { + printf hdrfmt, maxtime, i, j; + printf fmt, maxtime, i, j; + printf fmt, maxtime, i, j; + printf fmt, maxtime, i, j; + } + } + }' /dev/null > /tmp/runs.$$ +for i +do + ext=`expr "$i" : "simumalloc.exe\(.*\)"` + date + echo $i + cmd="./$i" + . /tmp/runs.$$ > times$ext 2>&1 + date +done diff --git a/lib/libmalloc/tests/testsbrk.c b/lib/libmalloc/tests/testsbrk.c new file mode 100644 index 000000000000..ff6c68d1bb45 --- /dev/null +++ b/lib/libmalloc/tests/testsbrk.c @@ -0,0 +1,22 @@ +#include <stdio.h> + +int incr = 201; +char *cp; +int i; + +main() +{ + extern char *sbrk(); + int sz; + + sz = getpagesize(); + printf("pagesize is 0x%08x (%d)\n", sz, sz); + for(i = 0; i < 1000; i++) { + if ((cp = sbrk(incr)) == (char *) -1) { + fprintf(stderr, "Cannot sbrk further\n"); + exit(-1); + } + printf("segment starts at 0x%08x, ends at 0x%08x\n", (int) cp, + (int) (cp + incr - 1)); + } +} diff --git a/lib/libmalloc/tests/teststomp.c b/lib/libmalloc/tests/teststomp.c new file mode 100644 index 000000000000..c591921144a9 --- /dev/null +++ b/lib/libmalloc/tests/teststomp.c @@ -0,0 +1,34 @@ +#if defined(STDHEADERS) +# include <stddef.h> +# include <string.h> +# include <stdlib.h> +# include <unistd.h> +#else +# define u_int unsigned int +extern char *memset(); +/* ignore some complaints about declarations. get ANSI headers */ +#endif + +#include <stdio.h> +#include "malloc.h" + +int +main(argc, argv) +char **argv; +int argc; +{ + char *cp; + int nbytes; + + if (argc != 2) { + (void) fprintf(stderr, "Usage: %s nbytes\n", argv[0]); + exit(1); + } + + nbytes = atoi(argv[1]); + cp = (char *) malloc(nbytes); + cp[nbytes] = 'a'; + mal_verify(1); + /* We aren't going to get here, y'know... */ + return 0; +} diff --git a/lib/libmalloc/trace.h b/lib/libmalloc/trace.h new file mode 100644 index 000000000000..c3826dceca4b --- /dev/null +++ b/lib/libmalloc/trace.h @@ -0,0 +1,19 @@ +#ifndef __TRACE_H__ +#define __TRACE_H__ +extern void __m_install_record proto((univptr_t, const char *)); +extern void __m_delete_record proto((univptr_t)); + +#define RECORD_FILE_AND_LINE(addr, fname, linenum) \ + if (_malloc_leaktrace) { \ + (void) sprintf(_malloc_statsbuf, "%s:%d:", fname, linenum); \ + __m_install_record(addr, _malloc_statsbuf); \ + } else \ + _malloc_leaktrace += 0 + +#define DELETE_RECORD(addr) \ + if (_malloc_leaktrace) \ + __m_delete_record(addr); \ + else \ + _malloc_leaktrace += 0 + +#endif /* __TRACE_H__ */ /* Do not add anything after this line */ diff --git a/lib/libmalloc/verify.c b/lib/libmalloc/verify.c new file mode 100644 index 000000000000..9fbad097b986 --- /dev/null +++ b/lib/libmalloc/verify.c @@ -0,0 +1,81 @@ +/* Author: Mark Moraes <moraes@csri.toronto.edu> */ + +/*LINTLIBRARY*/ + +#include "defs.h" +#include "globals.h" + +RCSID("$Id: verify.c,v 1.1 1994/03/06 22:59:57 nate Exp $") + +/* + * Goes through the entire heap checking all pointers, tags for + * consistency. Should catch most casual heap corruption (overwriting + * the end of a malloc'ed chunk, etc..) Nonetheless, heap corrupters + * tend to be devious and ingenious in ways they corrupt heaps (Believe + * me, I know:-). We should probably do the same thing if DEBUG is not + * defined, but return 0 instead of aborting. If fullcheck is non-zero, + * it also checks that free blocks contain the magic pattern written + * into them when they were freed to make sure the program is not still + * trying to access those blocks. + */ +int +mal_verify(fullcheck) +int fullcheck; +{ +#ifdef DEBUG + REGISTER Word *ptr; + REGISTER Word *blk; + REGISTER Word *blkend; + + if (_malloc_loword == NULL) /* Nothing malloc'ed yet */ + return(0); + + if (_malloc_rover != NULL) { + ASSERT(PTR_IN_HEAP(_malloc_rover), + "corrupt ROVER pointer found by mal_verify()"); + ASSERT(VALID_END_SIZE_FIELD(_malloc_rover), + "corrupt ROVER SIZE field found by mal_verify()"); + ASSERT(VALID_NEXT_PTR(_malloc_rover), + "corrupt ROVER NEXT pointer found by mal_verify()"); + ASSERT(VALID_PREV_PTR(_malloc_rover), + "corrupt ROVER PREV pointer found by mal_verify()"); + } + for(ptr = _malloc_mem; ptr != NULL; ptr = ptr->next) { + /* + * Check arena bounds - not same as checking block tags, + * despite similar appearance of the test + */ + ASSERT(SIZEFIELD(ptr+1) == SIZEFIELD(ptr + SIZE(ptr+1)), + "corrupt malloc arena found by mal_verify"); + blkend = ptr + SIZE(ptr + 1); + for(blk = ptr + ARENASTART; blk < blkend; blk += SIZE(blk)) { + ASSERT(PTR_IN_HEAP(blk), "corrupt pointer found by mal_verify()"); + ASSERT(VALID_START_SIZE_FIELD(blk), + "corrupt SIZE field found by mal_verify()"); + if (TAG(blk) == FREE) { + ASSERT(VALID_NEXT_PTR(blk + FREESIZE(blk) - 1), + "corrupt NEXT pointer found by mal_verify()"); + ASSERT(VALID_PREV_PTR(blk + FREESIZE(blk) - 1), + "corrupt PREV pointer found by mal_verify()"); + if (fullcheck) { + /* Make sure all free blocks are filled with FREEMAGIC */ + int i, n; + char *cp; + + n = (SIZE(blk) - FREE_OVERHEAD) * + sizeof(Word); + cp = (char *) (blk + FREEHEADERWORDS); + for (i = 0; i < n; i++, cp++) { + ASSERT(*cp == FREEMAGIC, + "corrupt free block found by mal_verify()"); + } + } + } else { + ASSERT(VALID_MAGIC(blk), + "overwritten end of block found by mal_verify()"); + } + } + } +#endif /* DEBUG */ + return(0); +} diff --git a/lib/libmalloc/version.c b/lib/libmalloc/version.c new file mode 100644 index 000000000000..5752fb2c4220 --- /dev/null +++ b/lib/libmalloc/version.c @@ -0,0 +1 @@ +char *_malloc_version = "CSRI, University of Toronto Malloc Version 1.13beta"; |