aboutsummaryrefslogtreecommitdiffstats
path: root/lib/libmalloc
diff options
context:
space:
mode:
Diffstat (limited to 'lib/libmalloc')
-rw-r--r--lib/libmalloc/CHANGES58
-rw-r--r--lib/libmalloc/COPYRIGHT23
-rw-r--r--lib/libmalloc/Makefile17
-rw-r--r--lib/libmalloc/Makefile.moraes187
-rw-r--r--lib/libmalloc/NOTE151
-rw-r--r--lib/libmalloc/README68
-rw-r--r--lib/libmalloc/TODO62
-rw-r--r--lib/libmalloc/_emalloc.c55
-rw-r--r--lib/libmalloc/_malloc.c88
-rw-r--r--lib/libmalloc/_memalign.c37
-rw-r--r--lib/libmalloc/_strdup.c23
-rw-r--r--lib/libmalloc/_strsave.c23
-rw-r--r--lib/libmalloc/align.h94
-rw-r--r--lib/libmalloc/assert.h10
-rw-r--r--lib/libmalloc/botch.c45
-rw-r--r--lib/libmalloc/bsd.lib.mk269
-rw-r--r--lib/libmalloc/defs.h386
-rw-r--r--lib/libmalloc/dumpheap.c107
-rw-r--r--lib/libmalloc/emalloc.c69
-rw-r--r--lib/libmalloc/externs.h113
-rw-r--r--lib/libmalloc/getmem.c108
-rw-r--r--lib/libmalloc/globals.c87
-rw-r--r--lib/libmalloc/globals.h43
-rw-r--r--lib/libmalloc/globrename.h46
-rw-r--r--lib/libmalloc/leak.c160
-rw-r--r--lib/libmalloc/malloc.c622
-rw-r--r--lib/libmalloc/malloc.doc653
-rw-r--r--lib/libmalloc/malloc.h136
-rw-r--r--lib/libmalloc/memalign.c160
-rw-r--r--lib/libmalloc/setopts.c120
-rw-r--r--lib/libmalloc/sptree.c763
-rw-r--r--lib/libmalloc/sptree.h65
-rw-r--r--lib/libmalloc/stats.c38
-rw-r--r--lib/libmalloc/strdup.c26
-rw-r--r--lib/libmalloc/strsave.c21
-rwxr-xr-xlib/libmalloc/tests/munge.sh40
-rwxr-xr-xlib/libmalloc/tests/plot.sh81
-rwxr-xr-xlib/libmalloc/tests/regress11
-rw-r--r--lib/libmalloc/tests/simumalloc.c239
-rw-r--r--lib/libmalloc/tests/t1.c40
-rw-r--r--lib/libmalloc/tests/t2.c37
-rw-r--r--lib/libmalloc/tests/t3.c110
-rw-r--r--lib/libmalloc/tests/t4.c20
-rw-r--r--lib/libmalloc/tests/t5.c31
-rw-r--r--lib/libmalloc/tests/test.out415
-rw-r--r--lib/libmalloc/tests/testmalloc.c182
-rw-r--r--lib/libmalloc/tests/testmemalign.c16
-rwxr-xr-xlib/libmalloc/tests/testrun.sh28
-rw-r--r--lib/libmalloc/tests/testsbrk.c22
-rw-r--r--lib/libmalloc/tests/teststomp.c34
-rw-r--r--lib/libmalloc/trace.h19
-rw-r--r--lib/libmalloc/verify.c81
-rw-r--r--lib/libmalloc/version.c1
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";