rsalz@uunet.uu.net (Rich Salz) (03/28/89)
Submitted-by: Mark Brader <msb@sq.sq.com>
Posting-number: Volume 18, Issue 66
Archive-name: malloctrace
This package has been put together from a number of different pieces and
I don't have time to edit all the README files together nicely. Most of
them are just cover notes that came with the different parts. I believe
all code except my own to have previously been posted to the net and
to be in the public domain. My code is also in the public domain.
What this is is a malloc package with tracing, so you can find where in
your program there is a call to malloc() without a matching free().
The malloc part is portable, the tracing will need work to run on
anything other than Sun's.
: To unbundle, sh this file
echo x - OVERALL_README 1>&2
cat >OVERALL_README <<'@@@End of OVERALL_README'
This package has been put together from a number of different pieces and
I don't have time to edit all the README files together nicely. Most of
them are just cover notes that came with the different parts. I believe
all code except my own to have previously been posted to the net and
to be in the public domain. My code is also in the public domain.
What this is is a malloc package with tracing, so you can find where in
your program there is a call to malloc() without a matching free().
This package is written in several separate source files so that a program
won't have to load all of it if it doesn't need it. However, there may be
cases where a function in the C runtime library calls a malloc() family
function that your program doesn't call, and it will then go to the system
version of the malloc() package for that function. This causes chaos.
You can force a particular function to be loaded from the malloctrace.a
library by putting, e.g., "-u _calloc" on the compile line just before
the library name. Or you could avoid the problem permanently by editing
the files malloc.h, malloc.c, free.c, calloc.c, init_trace.c, write_trace.c,
and forget.c into one big file.
The original malloc package was written by Bill Sebok. I then added the
tracing, while Arthur David Olson, independently, added some bug fixes
and enhancements. I then took Olson's version and added my tracing to it.
For more details on the tracing see mallck.1 and TRACE_README in this
directory. README is Sebok's original README. NEW_VERSION_README is
Olson's cover note. README.mtest2 and README.mtest3 are cover notes
for two malloc-tester programs (originally called mtest and looptest).
(mtest1, included here without its own README file, is part of Sebok's
package and was originally called tstmalloc).
UNPORTABILITY CAVEATS -
The tracing depends on being able to dump one's call stack. This is
done by code in the file write_trace.c. It works on our Sun running SunOS
3.0 or 3.2, but is likely to need rewriting on your machine!
There are two other things that work on our Sun but aren't portable:
the types "char *", "long", and "unsigned" seem to be inter-assigned
carelessly (I don't have time to delint this, either); and the BSDish
library function bcopy() is used.
Use at your own risk.
Mark Brader, SoftQuad Inc., Toronto, August 25, 1988
{ uunet!attcan | linus | decvax | watmath | pyramid } !utzoo!sq!msb
msb@sq.com decwrl!utcsri!sq!msb
@@@End of OVERALL_README
echo x - README 1>&2
cat >README <<'@@@End of README'
This is the malloc()/free()/realloc()/forget() package used at astrovax.
[Except for the MALLOCTRACE feature -- see ./TRACE_README]
It does not have the property of the 4.2 BSD malloc of allocating huge amounts
of excess memory. Image processing is done here and large malloc requests
are not rare. It is quite undesirable when one asks for 4.1 megabytes of memory
to have it try to return 8 megabytes and to fail because the process goes over
quota or there is not enough swap space.
Also this malloc does not have the property of the 4.1 BSD malloc that a search
for free memory traverses a linked list that covers all previous allocations,
causing thrashing by touching them and thus paging them back into memory.
Hopefully this malloc covers the best of both worlds. There is a fair attempt
at storage compaction, merging freed areas with adjacent free areas and
optionally returning freed areas adjacent to the break back to the system,
thereby shrinking the size of the process.
It is also allowable and compatible with this package to obtain memory by the
use of the sbrk() system call. This memory can be reclaimed and returned to
the malloc arena by the use of the provided forget() function. This function
is intended to provide the functionality of the Forth FORGET primitive in
an environment that also includes malloc and free.
The main disadvantage of this package is a larger storage overhead of 24 bytes
per memory area, due to the fact that each area is linked into two
bi-directional chains.
Non-vax users should edit the commented system-dependent parts of Makefile and
malloc.h for the requirements of one's own computer.
Bill Sebok Princeton University, Astrophysics
{allegra,akgua,cbosgd,decvax,ihnp4,noao,philabs,princeton,vax135}!astrovax!wls
@@@End of README
echo x - TRACE_README 1>&2
cat >TRACE_README <<'@@@End of TRACE_README'
The files malloc.c, free.c, realloc.c, and malloc.h have been edited,
and the new files write_trace.c and init_trace.c have been created,
to implement the tracing of calls to malloc, free, and realloc.
[WARNING: The implementation is system-dependent. It works on our SunOS 3.2.]
The method is based on that described in the paper:
"A Technique for Finding Storage Allocation Errors in
C-language Programs", David R. Barach, David H. Taenzer,
and Robert E. Wells; SIGPLAN Notices, V17#5 (May 1982).
All these changes and the associated new files are public domain,
and are not guaranteed.
Basically, the functions free and malloc are modified by inserting
calls to the new functions init_trace and write_trace. Init_trace
is called the first time malloc is called; it opens the output file
named by the environment variable $MALLOCTRACE, or "malloc.out" by
default. Each call to write_trace then writes to that trace file
a one-line description of the current event, e.g. "malloc of 256 at 5a10a".
It follows this by a traceback of the calling stack with one line for
each stack frame, e.g. "caller 0000210f", and an empty line.
The possible events are "malloc" and "realloc-to" to allocate memory,
"free" and "realloc" to free memory. A call to realloc generates
both a "realloc" and a "realloc-to".
The variable _malstate provides interlocking so that when realloc
calls malloc or free, which it sometimes does, an additional tracing
line will not be generated, and so that no tracing will be generated
before initialization is complete or if the trace file cannot be opened.
The associated shell script "prleak", containing three awk programs,
reads the $MALLOCTRACE or "malloc.out" (or other specified) file, and
does an "nm" on the program supposed to have generated it ("a.out"
by default). It scans these outputs and produces a report of the
high water level of allocated data (excluding that from stdio, as far
as possible), the total amount of data remaining allocated at termin-
ation, and the tracebacks of all calls that left data allocated at
termination or that resulted in any error (including nonfatal ones
such as frees of unallocated data). The tracebacks give entries in
forms such as "called from 5a9b [ _getframe + 42]", where 5a9b is in
hexadecimal and 42 in decimal.
Mark Brader
SoftQuad Inc.
January 1987
@@@End of TRACE_README
echo x - NEW_VERSION_README 1>&2
cat >NEW_VERSION_README <<'@@@End of NEW_VERSION_README'
>From utai!uunet!ncifcrf.gov!elsie!ado Mon Aug 1 02:37:08 1988
Received: by sq.sq.com id 21060; Mon, 1 Aug 88 02:36:59 EDT
From: ncifcrf.gov!elsie!ado
Received: from fcs280s.ncifcrf.gov by a.cs.uiuc.edu with SMTP (UIUC-5.52/9.7)
id AA09603; Sun, 31 Jul 88 13:13:31 CDT
Received: by fcs280s.ncifcrf.gov (4.0/NCIFCRF-1.0)
id AA05293; Sun, 31 Jul 88 14:15:06 EDT
Received: by elsie.UUCP (5.51/4.7)
id AA15980; Sun, 31 Jul 88 14:11:42 EDT
Date: Sun, 31 Jul 88 12:51:42 EDT
From: ncifcrf.gov!elsie!ado (Arthur David Olson)
Message-Id: <8807311811.AA15980@elsie.UUCP>
To: msb@sq.com
Subject: Re: Bug in Bill Sebok's malloc() package
Status: RO
I get the right output from your sample code with the version of malloc we're
using here at elsie; our version (Bill's with bug fixes) is attached.
--ado
@@@End of NEW_VERSION_README
echo x - README.mtest2 1>&2
cat >README.mtest2 <<'@@@End of README.mtest2'
Article 1077 of net.sources:
Path: sq!utfyzx!utgpu!water!watnot!watmath!clyde!rutgers!husc6!necntc!encore!vaxine!nw
From: nw@vaxine.UUCP (Neil Webber)
Newsgroups: net.sources
Subject: malloc/free test program
Message-ID: <417@vaxine.UUCP>
Date: 16 Feb 87 20:49:49 GMT
Organization: Automatix, Inc., Billerica, MA
Lines: 460
A while back I asked the net if anyone had a malloc/free test program that
would allocate and free randomly sized pieces of memory with random lifetimes
(and fill them with patterns that would be checked for corruption). I got
a number of useful suggestions (best one: use the "diff" program as a
malloc test ... it's brutal). Eventually, I wound up writing my own
test program, which actually helped me find a bug.
On the assumption that it might be useful to someone else, here it is.
Please note:
- No documentation (read the code to find out what it does).
- Could be extended in zillions of ways to make it more useful.
- No makefile, just compile "cc mtest.c"
A "shar" archive follows.
Neil Webber Automatix Inc. (or current resident) Billerica MA
{decvax,ihnp4,allegra}!encore!vaxine!nw
@@@End of README.mtest2
echo x - README.mtest3 1>&2
cat >README.mtest3 <<'@@@End of README.mtest3'
Article 1086 of net.sources:
Path: sq!utfyzx!utgpu!water!watnot!watmath!clyde!rutgers!lll-lcc!ptsfa!amdahl!rtech!daveb
From: daveb@rtech.UUCP (Dave Brower)
Newsgroups: net.sources
Subject: Another allocator tester
Message-ID: <665@rtech.UUCP>
Date: 17 Feb 87 19:00:13 GMT
References: <417@vaxine.UUCP>
Organization: Relational Technology, Alameda CA
Lines: 204
> A while back I asked the net if anyone had a malloc/free test program that
> would allocate and free randomly sized pieces of memory with random
> lifetimes... [ and one follows ]
Here is a program I've been using recently. It is a lot more intensive
than Neil Webber's, and shows you what the process size is doing. I am
usually comfortable when I can run an allocator through 10 million or so
loops with out a problem.
A useful addition would be computation of kilo-core-seconds.
As usual, no documentation and best wishes.
-dB
---------------- cut here ----------------
@@@End of README.mtest3
echo x - mallck.1 1>&2
cat >mallck.1 <<'@@@End of mallck.1'
.TH MALLCK 1 "25 August 1988"
.ds li /usr/lib/malloctrace.a
.SH NAME
mallck \- check memory allocation and deallocation calls
.SH SYNOPSIS
.B mallck
[ program ] [ tracefile ]
.SH DESCRIPTION
.IX mallck "" "\fLmallck\fP \(em check memory allocation and deallocation calls
.I Mallck
is used in conjunction with the library
.IR \*(li .
.PP
If a program is linked with that library (as the last library searched),
then when it is run, it will create a trace file of all the calls to
.IR malloc ,
.IR realloc ", and
.IR free .
The name of the trace file is taken from the environment variable
\s-2MALLOCTRACE\s+2, or if that is undefined, defaults to
.IR malloc.out .
Output to the file is flushed after each entry unless the environment variable
\s-2MALLOCTRACEBUF\s+2 is nonnull.
.PP
.I Mallck
is used to scan this file and look for calls that do not pair up\(emeither
.IR malloc s
without
.IR free s,
or vice versa, or calls where the amount freed (taken from the
internal information that
.I free
uses) does not correspond to the amount allocated.
.I Mallck
also reports the high-water mark of
memory that it knows (see Bugs section) to have been allocated.
.PP
.I Mallck
also examines the symbol table of the program, to format the tracebacks
usefully.
Its first argument
.I program
should be either the executable program, not stripped, or the output
from running
.I nm
on the executable program.
(Only the `T' entries are examined and their sequence does not matter, so
.IR "nm -gp" "'s
output would suffice.)
If no arguments are given,
.I a.out
is used for
.IR program .
.PP
The second argument
.I malloctrace
is the trace file described above.
If omitted, the same defaults apply as above.
.SH AUTHOR
Mark Brader, SoftQuad Inc., 1987-88.
.PP
Based on the paper
.I "A Technique for Finding Storage Allocation Errors in C-language Programs
by David R. Barach, David H. Taenzer, and Robert E. Wells, in
.IR "SIGPLAN Notices" ,
.BR 17 ,
5 (May 1982).
.PP
The
.I malloc
family functions to which the tracing was added to create
.I \*(li
were the public-domain ones by Bill Sebok, then of Princeton University,
with modifications by Arthur David Olson of the National Institutes of Health.
.SH DIAGNOSTICS
Self-explanatory, as they say.
Since memory being allocated but never freed may be a harmless
situation, it is reported in lower case, while other messages
are more emphatic.
.SH SEE ALSO
nm(1), malloc(3)
.SH FILES
a.out
.br
malloc.out
.br
\*(li
.SH BUGS
There is no way to verify that the trace
file did in fact come from the program
.IR program ;
nonsensical tracebacks are the only hint.
Even if the program is the correct one, functions declared static are
not seen by
.I nm
and thus tracebacks from calls in such functions will be misleading.
.PP
Due to interactions between
.I stdio
and the traced
.I malloc
family, programs may be unstable as to whether they report the
calls to the
.I malloc
family that
.I stdio
functions may make.
Thus
.I stdio
buffers may be counted in the high-water mark or not, depending only
on what input the program received.
The first
.I stdio
buffer is never reported.
.PP
Calls to
.I realloc
are treated internally as successive calls to two functions,
.I realloc
and
.I realloc-to
(equivalent to
.I free
and
.IR malloc ),
and are so referred to in the output report.
.PP
The sizes reported in ``never freed'' messages
exclude the overhead added by the
.I malloc
family functions, even though the allocation statistics do report it.
(This is because the overhead may differ slightly on otherwise identical calls,
and if this is ignored, their reports can be combined.)
.PP
The code in
.I \*(li
that produces the calling stack traceback was written
without the aid of documentation on the Sun's stack format.
Since it depends on the stack format, it is not portable.
.PP
The format of the trace file is somewhat verbose and it can rapidly
consume large amounts of disk space.
A pipe cannot be used because
.I mallck
reads the trace file twice.
.SH NOTES
.I Mallck
is a shell script consisting principally of 3 invocations of
.IR awk ,
3 of
.IR sort ,
and one each of
.IR sed ,
.IR grep ", and
.IR nm .
@@@End of mallck.1
echo x - malloc.3 1>&2
cat >malloc.3 <<'@@@End of malloc.3'
.TH MALLOC 3 "30 June 1986"
.SH NAME
malloc, free, realloc \- memory allocator
.SH SYNOPSIS
.nf
.B char *malloc(size)
.B Size size;
.PP
.B void free(ptr)
.B char *ptr;
.PP
.B char *realloc(ptr, size)
.B char *ptr;
.B Size size;
.PP
.B extern char endfree
.PP
.B extern void (*mlabort)()
.fi
.PP
Where
.I Size
is an integer large enough to hold a char pointer.
.SH DESCRIPTION
.I Malloc
and
.I free
provide a simple general-purpose memory allocation package.
.I Malloc
returns a pointer to a block of at least
.I size
bytes beginning on the boundary of the most stringent alignment required
by the architecture.
.PP
The argument to
.I free
is a pointer to a block previously allocated by
.IR malloc ;
this space is made available for further allocation,
but its contents are left undisturbed.
.PP
Needless to say, grave disorder will result if the space assigned by
.I malloc
is overrun or if some random number is handed to
.IR free .
.PP
.I Malloc
maintains multiple lists of free blocks according to size,
allocating space from the appropriate list.
It calls
.I brk
(see
.IR brk (2))
to get more memory from the system when there is no
suitable space already free.
.PP
.I Free
makes an attempt to merge newly freed memory with adjacent free areas.
If the result of this merging is an area that touches the system break
(the current location of the highest valid address of the data segment of the
process) and if
.I
endfree
has a non-zero value, then break is moved back, contracting the process
size and releasing the memory back to the system.
.PP
By default
.I endfree
has a value of 0, which disables the release of memory back to the system.
.PP
It is valid to also allocate memory by the use of
.I sbrk(3)
or by moving up the break with
.I brk(3).
This memory may be reclaimed and returned to
the \fImalloc\fP/\fIfree\fP arena by the use of
.I forget
(see \fIforget\fP(3)).
.PP
.I Realloc
changes the size of the block pointed to by
.I ptr
to
.I size
bytes and returns a pointer to the (possibly moved) block.
The contents will be unchanged up to the lesser of the new and old sizes.
.PP
In order to be compatible with older versions,
if
.I endfree
is 0, then
.I realloc
also works if
.I ptr
points to a block freed since the last call of
.I malloc
or
.I realloc.
Sequences of
.I free, malloc
and
.I realloc
were previously used to attempt storage compaction.
This procedure is no longer recommended.
In this implementation
.I Realloc,
.I malloc
and
.I free
do a fair amount of their own storage compaction anyway.
.SH DIAGNOSTICS
.I Malloc, realloc
return a null pointer (0) if there is no available memory or if the arena
has been detectably corrupted by storing outside the bounds of a block.
.I Realloc
makes an attempt to detect and return a null pointer when the break has been
moved so that the requested address is no longer valid.
.I Malloc
may be recompiled to check the arena very stringently on every transaction;
those sites with a source code license may do this by recompiling the source
with -Ddebug .
.PP
On detection of corruption of the malloc arena the normal response is an
abort with a core dump. This response can be changed by placing a pointer to
a function with the desired response into the extern pointer
.I mlabort.
.SH ALGORITHM
.I Malloc
returns a block of size equal to the size requested plus an overhead (24
bytes for a 32 bit machine).
Freed memory is linked into a chain selected by the size of the freed area
(currently, memory size of items in a chain is between two adjacent powers of
2).
The search for memory starts with the chain whose length index is at least
equal to the size of the request and proceeds if unsuccessful to larger
memory size chains. If there is any surplus memory left after the filling
of a request it is returned to the appropriate free list chain.
.SH BUGS
When
.I realloc
returns 0, the block pointed to by
.I ptr
may have been destroyed.
@@@End of malloc.3
echo x - forget.3 1>&2
cat >forget.3 <<'@@@End of forget.3'
.TH FORGET 3 "30 June 1986"
.SH NAME
forget \- reclaim sbrk'ed memory into malloc arena
.SH SYNOPSIS
.nf
.B void forget(ptr)
.B char *ptr;
.PP
.B extern char endfree
.SH DESCRIPTION
.I Forget
provides a way of reclaiming memory obtained by
.I sbrk(3)
and returning it to the malloc arena. All such memory above
.I ptr
(the "forget point") is marked free and merged if possible with adjacent
free areas. If
.I endfree
is non-zero any such memory adjacent to the "break" (the highest valid
data address for the process) is released to the system by moving back
the break.
.PP
This function was written to provide the functionality of the Forth
FORGET primitive in an environment where
a dictionary is grown by
.I sbrk
and
.I malloc
and
.I free
are also present.
.SH BUGS
When the specified forget point is below the initial end of the program,
disaster can result.
@@@End of forget.3
echo x - mallck 1>&2
cat >mallck <<'@@@End of mallck'
#
# mallck
# Mark Brader, SoftQuad Inc., 1987
#
# NOT copyright by SoftQuad. - msb, 1988
#
# sccsid @(#)mallck 1.4 88/08/24
#
#
# Checks a malloc trace file as produced by modified forms of malloc,
# free, and realloc -- locally in /usr/lib/malloctrace.a -- for any
# incorrectly paired allocations and frees, and any other problems.
# Also computes a few statistics from the data.
#
# Usage:
# mallck [a.out] [${MALLOCTRACE-malloc.out}]
# or
# mallck nm.out [${MALLOCTRACE-malloc.out}]
#
# Both arguments optional, defaults as indicated. nm.out is the result of
# running nm on the program; only the T lines are significant.
#
# The contents of the malloc trace file look like this:
#
# malloc of 71 gets 104 at 143692
# caller 000020e8
# caller 0000204c
#
# free of 44 at 143500
# caller 000020f8
# caller 0000204c
#
# First, three awk programs. Unfortunately, while it's most convenient
# to put them in sh variables, it runs sh near its limits, so we use sed
# to pack the programs a bit first...
# Look up locations in symbol table. This program reads the "caller"
# entries in the malloc trace file, and the output of nm, and produces
# output of this form:
#
# 0000204c 204c start 44
# 000020b8 20b8 _main 24
# 000020c8 20c8 _main 40
# 000020d8 20d8 _main 56
SYMTAB=`sed -e "s/ //" -e "s/ *#.*//" <<'Eot'
BEGIN {
digit["a"] = 10 # Hex into decimal without scanf
digit["b"] = 11
digit["c"] = 12
digit["d"] = 13
digit["e"] = 14
digit["f"] = 15
for (i = 0; i <= 9; ++i) digit[i] = i
func = "0"
funaddr = 0
}
/./ {
addr = 0
for (i = 1; i <= 8; ++i) addr = 16*addr + digit[substr($1,i,1)]
if (addr + 1 == addr) {
printf " --- **** WARNING: conversion of hex %s to decimal" \
" %d may be inaccurate!\n", $1, addr
# Single precision floating point!
}
if ($2 == "T") {
func = $3
funaddr = addr
} else \
printf "%8.8x %8x %s %d\n", addr, addr, func, addr - funaddr
}
Eot
`
# Examine calls to malloc et al, and locate any problems.
# This program reads the malloc trace file again, and produces output of
# the following form, which is then sorted and filtered through uniq -c.
# The part before the "---" is a complete call stack traceback.
# There are also summary lines.
#
# 00002110 0000204c --- malloc - size 21 - never freed
# 00002124 0000204c --- realloc-to - size 21 - never freed
#
# The sizes shown are the requested sizes, not the actual ones including
# overhead. This is so that duplicate entries can be reduced accurately
# by uniq -c. However, when errors are reported, actual sizes are shown too.
#
FIND=`sed -e "s/ //" -e "s/ *#.*//" <<'Eot'
BEGIN {
# So null input is harmless ...
alact[""] = totalloc = maxalloc = maxloc = 0
# for waking up recipients of important errors
bang = " *****************"
}
/of/ {
act = $1
reqsize = $3
caller = ""
if ($4 == "gets") {
gotsize = $5
loc = $7
} else {
gotsize = reqsize
loc = $5
}
}
/caller/ {
caller = caller " " $2 # concatenate traceback together
}
/^$/ {
if (act == "malloc" || act == "realloc-to") {
if (loc == 0) {
printf "%s --- %s - size %s - ALLOCATION FAILED%s\n", \
caller, act, reqsize, bang
} else {
# just take note for later reference
alcall[loc] = caller
alreq [loc] = reqsize
algot [loc] = gotsize
alact [loc] = act
totreq += reqsize
totgot += gotsize
if (maxreq < totreq) maxreq = totreq
if (maxgot < totgot) maxgot = totgot
if (maxloc < gotsize + loc) maxloc = gotsize + loc
}
} else {
# Must be free or realloc - check the data
if (alact[loc]) {
if (algot[loc] != gotsize) {
printf "%s --- %s - size %s - actual %s -" \
" WRONG SIZE LATER FREED%s\n", \
alcall[loc], alact[loc], alreq[loc], \
algot[loc], bang
printf "%s --- %s - size %s -" \
" ACTUAL ALLOCATED SIZE WAS %s%s\n", \
caller, act, gotsize, algot[loc], bang
}
alact[loc] = ""
totgot -= gotsize
totreq -= alreq[loc]
} else {
printf "%s --- %s - size %s - UNALLOCATED%s\n", \
caller, act, gotsize, bang
}
}
}
END {
# check for never-freed space
for (loc in alact)
if (alact[loc])
printf "%s --- %s - size %s -" \
" never freed\n", \
alcall[loc], alact[loc], alreq[loc]
# The following statistics will print at the top of the
# final output, by a little trickery -- their beginnings
# are chosen to sort before the other records (and to
# leave them in the desired order after sorting)
print " --- ****** ALLOCATION STATISTICS (excluding most stdio)"
printf " --- ****** Greatest allocated address: %d (hex %x)\n", \
maxloc - 1, maxloc - 1
print " --- ****** High-water allocation level: " \
maxreq " bytes (+ " maxgot-maxreq " overhead)"
print " --- ****** Total of memory never freed: " \
totreq " bytes (+ " totgot-totreq " overhead)"
}
Eot
`
# Format the output of the 2nd awk program using the output
# of the 1st to display symbolic locations
REPORT=`sed -e "s/ //" -e "s/ *#.*//" <<'Eot'
! / --- / {
func[$1] = $3
offs[$1] = $4
nozeros[$1] = $2
if (maxlen < length($3)) maxlen = length($3)
if (maxdig < length($4)) maxdig = length($4)
}
/ --- / {
for (punct = 1; $punct != "---"; ++punct) {;} # Where in line is "---"?
if (punct > 2) printf "\n\n"
if ($1 > 1) printf "occurring %d times - ", $1 # Bless uniq -c!
for (i = punct + 1; i <= NF; ++i) printf "%s ", $i
printf "\n"
if (punct > 2) {
for (i = 2; i < punct; ++i) {
if (i == 2) printf "\n\tcalled"; else printf "\t"
printf "\tfrom %8s [%" maxlen "s + %" maxdig "d]\n", \
nozeros[$i], func[$i], offs[$i]
}
}
}
Eot
`
# Default arguments:
BIN=${1-a.out}
TRACE=${2-${MALLOCTRACE-malloc.out}}
# And do it...
(
(
(sed -n '/caller /s///p' $TRACE || exit) \
| sort -u
(nm -gp $BIN 2>/dev/null || cat $BIN) \
| grep ' T '
) \
| sort | awk "$SYMTAB"
awk "$FIND" $TRACE | sort | uniq -c
) \
| awk "$REPORT"
@@@End of mallck
echo chmod +x mallck
chmod +x mallck
echo x - calloc.c 1>&2
cat >calloc.c <<'@@@End of calloc.c'
#include "malloc.h"
#define NULL 0
/* NOT copyright by SoftQuad. - msb, 1988 */
#ifndef lint
static char *SQ_SccsId = "@(#)calloc.c 1.2 88/08/24";
#endif
/*
** And added by ado. . .
*/
char *
calloc(n, s)
unsigned n;
unsigned s;
{
unsigned cnt;
char * cp;
cnt = n * s;
cp = malloc(cnt);
if (cp != NULL)
bzero(cp, (int) cnt);
return cp;
}
void
cfree(mem)
char * mem;
{
free(mem);
}
@@@End of calloc.c
echo x - forget.c 1>&2
cat >forget.c <<'@@@End of forget.c'
#include "malloc.h"
#define NULL 0
/* NOT copyright by SoftQuad. - msb, 1988 */
#ifndef lint
static char *SQ_SccsId = "@(#)forget.c 1.4 88/08/24";
#endif
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* forget William L. Sebok
* A "smarter" malloc v1.0 Sept. 24, 1984 rev. June 30,1986
* Then modified by Arthur David Olsen
*
* forget returns to the malloc arena all memory allocated by sbrk()
* above "bpnt".
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
void
forget(bpnt)
char *bpnt;
{
register struct overhead *p, *q, *r, *b;
register Size l;
struct overhead *crbrk;
char pinvalid, oendfree;
/*
* b = forget point
* p = beginning of entry
* q = end of entry, beginning of gap
* r = end of gap, beginning of next entry (or the break)
* pinvalid = true when groveling at forget point
*/
pinvalid = 0;
oendfree = endfree; endfree = 0;
b = (struct overhead *)bpnt;
p = FROMADJ(adjhead.q_back);
r = crbrk = (struct overhead *)CURBRK;
for (;pinvalid == 0 && b < r; p = FROMADJ(TOADJ(r = p)->q_back)) {
if ( p == FROMADJ(&adjhead)
|| (q = (struct overhead *)((char *)p + p->ov_length)) < b
) {
pinvalid = 1;
q = b;
}
if (q == r)
continue;
ASSERT(q < r,
"\nforget: addresses in adjacency chain are out of order!\n");
/* end of gap is at break */
if (oendfree && r == crbrk) {
(void)BRK((char *)q); /* free it yourself */
crbrk = r = q;
continue;
}
if (pinvalid)
q = (struct overhead *) /* align q pointer */
(((long)q + (NALIGN-1)) & (~(NALIGN-1)));
l = (char *)r - (char *)q;
/*
* note: unless something is screwy: (l%NALIGN) == 0
* as r should be aligned by this point
*/
if (l >= (int) sizeof(struct overhead)) {
/* construct busy entry and free it */
q->ov_magic = MAGIC_BUSY;
q->ov_length = l;
insque(TOADJ(q),TOADJ(p));
free((char *)q + sizeof(struct overhead));
} else if (pinvalid == 0) {
/* append it to previous entry */
p->ov_length += l;
if (p->ov_magic == MAGIC_FREE) {
remque(TOBUK(p));
{
register struct qelem * bp;
bp = &buckets[mlindx(p->ov_length)];
if (bp > hifreebp)
hifreebp = bp;
insque(TOBUK(p),bp);
}
}
}
}
endfree = oendfree;
if (endfree)
mlfree_end();
return;
}
@@@End of forget.c
echo x - free.c 1>&2
cat >free.c <<'@@@End of free.c'
#include "malloc.h"
#define NULL 0
/* NOT copyright by SoftQuad. - msb, 1988 */
#ifndef lint
static char *SQ_SccsId = "@(#)free.c 1.6 88/08/24";
#endif
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* free William L. Sebok
* A "smarter" malloc v1.0 Sept. 24, 1984 rev. June 30,1986
* Then modified by Arthur David Olsen
* MALLOCTRACE added by Mark Brader
*
* free takes a previously malloc-allocated area at mem and frees it.
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
free(mem)
register char *mem;
{
register struct overhead *p, *q;
void mlfree_end();
#ifdef MALLOCTRACE /* See ./TRACE_README */
extern enum _malstate _malstate;
if (_malstate == S_INITIAL) _mal_init_trace();
#endif
if (mem == NULL)
return;
p = (struct overhead *)(mem - sizeof(struct overhead));
#ifdef MALLOCTRACE
if (_malstate == S_TRACING)
_mal_write_trace ("free", p->ov_length, p->ov_length, mem);
#endif
/* not advised but allowed */
if (p->ov_magic == MAGIC_FREE)
return;
if (p->ov_magic != MAGIC_BUSY) {
mllcerr("attempt to free memory not allocated with malloc!\n");
#ifdef MALLOCTRACE
return; /* mllcerr() normally doesn't return */
#endif
}
/* try to merge with previous free area */
q = FROMADJ((TOADJ(p))->q_back);
if (q != FROMADJ(&adjhead)) {
ASSERT(q < p,
"\nfree: While trying to merge a free area with a lower adjacent free area,\n\
addresses were found out of order!\n");
/* If lower segment can be merged */
if ( q->ov_magic == MAGIC_FREE
&& (char *)q + q->ov_length == (char *)p
) {
/* remove lower address area from bucket chain */
remque(TOBUK(q));
/* remove upper address area from adjacency chain */
remque(TOADJ(p));
q->ov_length += p->ov_length;
p->ov_magic = NULL; /* decommission */
p = q;
}
}
/* try to merge with next higher free area */
q = FROMADJ((TOADJ(p))->q_forw);
if (q != FROMADJ(&adjhead)) {
/* upper segment can be merged */
ASSERT(q > p,
"\nfree: While trying to merge a free area with a higher adjacent free area,\n\
addresses were found out of order!\n");
if ( q->ov_magic == MAGIC_FREE
&& (char *)p + p->ov_length == (char *)q
) {
/* remove upper from bucket chain */
remque(TOBUK(q));
/* remove upper from adjacency chain */
remque(TOADJ(q));
p->ov_length += q->ov_length;
q->ov_magic = NULL; /* decommission */
}
}
p->ov_magic = MAGIC_FREE;
/* place in bucket chain */
{
register struct qelem * bp;
bp = &buckets[mlindx(p->ov_length)];
if (bp > hifreebp)
hifreebp = bp;
insque(TOBUK(p),bp);
}
if (endfree)
mlfree_end();
return;
}
void
mlfree_end()
{
register struct overhead *p;
p = FROMADJ(adjhead.q_back);
if ( /* area is free and at end of memory */
p->ov_magic == MAGIC_FREE
&& (char*)p + p->ov_length == (char *)CURBRK
) {
p->ov_magic = NULL; /* decommission (just in case) */
/* remove from end of adjacency chain */
remque(TOADJ(p));
/* remove from bucket chain */
remque(TOBUK(p));
/* release memory to system */
(void)BRK((char *)p);
}
return;
}
@@@End of free.c
echo x - init_trace.c 1>&2
cat >init_trace.c <<'@@@End of init_trace.c'
#ifdef MALLOCTRACE
#include <stdio.h>
#include "malloc.h"
/* NOT copyright by SoftQuad. - msb, 1988 */
#ifndef lint
static char *SQ_SccsId = "@(#)init_trace.c 1.3 88/08/24";
#endif
/*
* Open the trace output file. The _malstate serves to prevent
* any infinite recursion if stdio itself calls malloc.
*/
void
_mal_init_trace()
{
char *filename, *bufflag;
char *getenv();
extern enum _malstate _malstate;
extern int _malbuff;
extern FILE *_malfp;
if (_malstate != S_INITIAL) /* Can't happen, but what the heck */
return;
_malstate = S_IN_STDIO;
filename = getenv (TRACEENVVAR);
if (filename == NULL)
filename = TRACEFILE;
_malfp = fopen (filename, "w");
if (_malfp == NULL) {
perror (filename);
fprintf(stderr, "(will run without malloc tracing)\n");
} else {
/*
* Nonportable kludge that should trigger a malloc
* in stdio while doing no harm, and also reduce the
* likelihood of a future malloc in stdio.
*/
putc (0, _malfp);
fflush (_malfp);
fseek (_malfp, 0L, 0);
/* Were we requested not to flush after each entry? */
bufflag = getenv (TRACEBUFVAR);
_malbuff = (bufflag != NULL && *bufflag != '\0');
/* Initialization successful */
_malstate = S_TRACING;
}
}
#endif
@@@End of init_trace.c
echo x - malloc.c 1>&2
cat >malloc.c <<'@@@End of malloc.c'
#include "malloc.h"
#define NULL 0
/* NOT copyright by SoftQuad. - msb, 1988 */
#ifndef lint
static char *SQ_SccsId = "@(#)malloc.c 1.8 88/08/24";
#endif
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* A "smarter" malloc v1.0 William L. Sebok
* Sept. 24, 1984 rev. June 30,1986
* Then modified by Arthur David Olsen
* MALLOCTRACE added by Mark Brader
*
* malloc allocates and returns a pointer to a piece of memory nbytes
* in size.
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#ifdef MALLOCTRACE /* See ./TRACE_README */
#include <stdio.h>
FILE *_malfp;
int _malbuff;
enum _malstate _malstate = S_INITIAL;
#endif
/* sizes of buckets currently proportional to log 2() */
static Size mlsizes[] = {0, 64, 128, 256, 512, 1024, 2048,
4096, 8192, 16384, 32768, 65536, 131072,
262144, 524288, 1048576, 2097152, 4194304};
/* head of adjacency chain */
struct qelem adjhead = { &adjhead, &adjhead };
/* head of bucket chains */
struct qelem buckets[NBUCKETS] = {
&buckets[0], &buckets[0], &buckets[1], &buckets[1],
&buckets[2], &buckets[2], &buckets[3], &buckets[3],
&buckets[4], &buckets[4], &buckets[5], &buckets[5],
&buckets[6], &buckets[6], &buckets[7], &buckets[7],
&buckets[8], &buckets[8], &buckets[9], &buckets[9],
&buckets[10], &buckets[10], &buckets[11], &buckets[11],
&buckets[12], &buckets[12], &buckets[13], &buckets[13],
&buckets[14], &buckets[14], &buckets[15], &buckets[15],
&buckets[16], &buckets[16], &buckets[17], &buckets[17]
};
struct qelem * hifreebp = &buckets[0];
char endfree = 0;
void (*mlabort)() = {0};
void mlfree_end();
char *
malloc(nbytes)
unsigned nbytes; /* for 4.3 compat. */
{
register struct overhead *p, *q;
register struct qelem *bucket;
register Size surplus;
Size mlindx();
#ifdef MALLOCTRACE
unsigned old_nbytes;
old_nbytes = nbytes;
if (_malstate == S_INITIAL) _mal_init_trace();
#endif
nbytes = ((nbytes + (NALIGN-1)) & ~(NALIGN-1))
+ sizeof(struct overhead);
for (
bucket = &buckets[mlindx((Size) nbytes)];
bucket <= hifreebp;
bucket++
) {
register struct qelem *b;
for(b = bucket->q_forw; b != bucket; b = b->q_forw) {
p = FROMBUK(b);
ASSERT(p->ov_magic == MAGIC_FREE,
"\nmalloc: Entry not marked FREE found on Free List!\n");
if (p->ov_length >= nbytes) {
remque(b);
surplus = p->ov_length - nbytes;
goto foundit;
}
}
}
/* obtain additional memory from system */
{
register Size i;
p = (struct overhead *)CURBRK;
i = ((Size)p)&(NALIGN-1);
if (i != 0)
p = (struct overhead *)((char *)p + NALIGN - i);
if (BRK((char *)p + nbytes)) {
#ifdef MALLOCTRACE
if (_malstate == S_TRACING)
_mal_write_trace ("malloc", (Size) old_nbytes,
(Size) 0, (char*) 0);
#endif
return(NULL);
}
p->ov_length = nbytes;
surplus = 0;
/* add to end of adjacency chain */
ASSERT((FROMADJ(adjhead.q_back)) < p,
"\nmalloc: Entry in adjacency chain found with address lower than Chain head!\n"
);
insque(TOADJ(p),adjhead.q_back);
}
foundit:
/* mark surplus memory free */
if (surplus > (int) sizeof(struct overhead)) {
/* if big enough, split it up */
q = (struct overhead *)((char *)p + nbytes);
q->ov_length = surplus;
p->ov_length = nbytes;
q->ov_magic = MAGIC_FREE;
/* add surplus into adjacency chain */
insque(TOADJ(q),TOADJ(p));
/* add surplus into bucket chain */
{
register struct qelem * bp;
bp = &buckets[mlindx(surplus)];
if (bp > hifreebp)
hifreebp = bp;
insque(TOBUK(q),bp);
}
}
#ifdef MALLOCTRACE
else
nbytes += surplus;
if (_malstate == S_TRACING)
_mal_write_trace ("malloc", (Size) old_nbytes, (Size) nbytes,
(char *) p + sizeof (struct overhead));
#endif
p->ov_magic = MAGIC_BUSY;
return((char*)p + sizeof(struct overhead));
}
/*
* select the proper size bucket
*/
Size
mlindx(n)
register Size n;
{
register Size *p;
p = mlsizes;
p[NBUCKETS - 1] = n;
/* Linear search. */
while (n > *p++)
;
return (p - 1) - mlsizes;
}
void
mllcerr(p)
char *p;
{
register char *q;
q = p;
while (*q++); /* find end of string */
(void)write(2,p,q-p-1);
#ifndef MALLOCTRACE
if (mlabort)
(*mlabort)();
#ifdef debug
else
abort();
#endif debug
#endif MALLOCTRACE
}
#ifndef vax
/*
* The vax has wondrous instructions for inserting and removing items into
* doubly linked queues. On the vax the assembler output of the C compiler is
* massaged by an sed script to turn these function calls into invocations of
* the insque and remque machine instructions.
*/
void
insque(item,queu)
register struct qelem *item, *queu;
/* insert "item" after "queu" */
{
register struct qelem *pueu;
pueu = queu->q_forw;
item->q_forw = pueu;
item->q_back = queu;
queu->q_forw = item;
pueu->q_back = item;
}
void
remque(item)
register struct qelem *item;
/* remove "item" */
{
register struct qelem *queu, *pueu;
pueu = item->q_forw;
queu = item->q_back;
queu->q_forw = pueu;
pueu->q_back = queu;
}
#endif
@@@End of malloc.c
echo x - malloc.h 1>&2
cat >malloc.h <<'@@@End of malloc.h'
/* NOT copyright by SoftQuad. - msb, 1988 */
/* SQ SccsId "@(#)malloc.h 1.6 88/08/24" */
/*LINTLIBRARY*/
#ifndef lint
#ifndef NOID
#endif /* !NOID */
#endif /* !lint */
#ifdef vax
struct qelem * _p;
struct qelem * _q;
#define remque(p) { _p = (p); asm("remque *__p,r0"); }
#define insque(p, q) { _p = (p); _q = (q) ; asm("insque *__p,*__q"); }
#endif /* vax */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* A "smarter" malloc William L. Sebok
* Then modified by Arthur David Olsen
* MALLOCTRACE added by Mark Brader
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* Algorithm:
* Assign to each area an index "n". This is currently proportional to
* the log 2 of size of the area rounded down to the nearest integer.
* Then all free areas of storage whose length have the same index n are
* organized into a chain with other free areas of index n (the "bucket"
* chain). A request for allocation of storage first searches the list of
* free memory. The search starts at the bucket chain of index equal to
* that of the storage request, continuing to higher index bucket chains
* if the first attempt fails.
* If the search fails then new memory is allocated. Only the amount of
* new memory needed is allocated. Any old free memory left after an
* allocation is returned to the free list.
*
* All memory areas (free or busy) handled by malloc are also chained
* sequentially by increasing address (the adjacency chain). When memory
* is freed it is merged with adjacent free areas, if any. If a free area
* of memory ends at the end of memory (i.e. at the break), and if the
* variable "endfree" is non-zero, then the break is contracted, freeing
* the memory back to the system.
*
* Notes:
* ov_length field includes sizeof(struct overhead)
* adjacency chain includes all memory, allocated plus free.
*/
/* the following items may need to be configured for a particular machine */
/* alignment requirement for machine (in bytes) */
#define NALIGN 4
/* size of an integer large enough to hold a character pointer */
typedef long Size;
/*
* CURBRK returns the value of the current system break, i.e., the system's
* idea of the highest legal address in the data area. It is defined as
* a macro for the benefit of systems that have provided an easier way to
* obtain this number (such as in an external variable)
*/
#ifndef CURBRK
#define CURBRK sbrk(0)
extern char *sbrk();
#else /* CURBRK */
# if CURBRK == curbrk
extern Size curbrk;
# endif
#endif /* CURBRK */
/*
* note that it is assumed that CURBRK remembers the last requested break to
* the nearest byte (or at least the nearest word) rather than the nearest page
* boundary. If this is not true then the following BRK macro should be
* replaced with one that remembers the break to within word-size accuracy.
*/
#ifndef BRK
#define BRK(x) brk(x)
extern char *brk();
#endif /* !BRK */
/* END of machine dependent portion */
#ifdef MALLOCTRACE
/* Tracing of all calls to malloc, free, realloc... see ./TRACE_README */
enum _malstate {S_INITIAL, S_IN_STDIO, S_IN_REALLOC, S_TRACING};
#define TRACEFILE "malloc.out" /* default output filename */
#undef MALLOCTRACE /* so the next line means what it says! */
#define TRACEENVVAR "MALLOCTRACE" /* where to read nondefault name */
#define MALLOCTRACE /* cancel #undef! */
#define TRACEBUFVAR "MALLOCTRACEBUF" /* No-flush request */
#endif
#define MAGIC_FREE 0x548a934c
#define MAGIC_BUSY 0xc139569a
#define NBUCKETS 18
struct qelem {
struct qelem *q_forw;
struct qelem *q_back;
};
struct overhead {
struct qelem ov_adj; /* adjacency chain pointers */
struct qelem ov_buk; /* bucket chain pointers */
long ov_magic;
Size ov_length;
};
/*
* The following macros depend on the order of the elements in struct overhead
*/
#define TOADJ(p) ((struct qelem *)(p))
#define FROMADJ(p) ((struct overhead *)(p))
#define FROMBUK(p) ((struct overhead *)( (char *)p - sizeof(struct qelem)))
#define TOBUK(p) ((struct qelem *)( (char *)p + sizeof(struct qelem)))
/*
* return to the system memory freed adjacent to the break
* default is Off
*/
extern char endfree;
/* head of adjacency chain */
extern struct qelem adjhead;
/* head of bucket chains */
extern struct qelem buckets[NBUCKETS];
extern struct qelem * hifreebp;
extern void (*mlabort)();
#ifndef vax
extern void insque(), remque();
#endif
extern void mllcerr();
extern char *malloc(), *realloc();
#ifdef debug
# define ASSERT(p,q) if (!(p)) mllcerr(q)
#else
# define ASSERT(p,q) ((p),(q))
#endif
@@@End of malloc.h
echo x - mtest1.c 1>&2
cat >mtest1.c <<'@@@End of mtest1.c'
/* NOT copyright by SoftQuad. - msb, 1988 */
#ifndef lint
static char *SQ_SccsId = "@(#)mtest1.c 1.2 88/08/24";
#endif
/*
* tstmalloc this routine tests and exercizes the malloc/free package
*/
#include <stdio.h>
#include <setjmp.h>
#include "malloc.h"
jmp_buf env;
main(argc,argv)
int argc; char *argv[];
{
char lin[100], arg1[20], arg2[20], arg3[20];
char *res, *malloc(), *realloc();
register struct overhead *p, *q;
register struct qelem *qp;
int arg, nargs, argn;
int l;
void malerror();
mlabort = &malerror;
setjmp(env);
for (;;) {
printf("* ");
if (fgets(lin,sizeof lin, stdin)== NULL)
exit(0);
nargs = sscanf(lin,"%s%s%s",arg1,arg2,arg3);
switch (arg1[0]) {
case 'b':
if (nargs == 2) {
arg = atoi(arg2);
if (arg<0 || arg>=NBUCKETS)
goto bad;
qp = &buckets[arg];
printf("Bucket %2d\t\t\t buk=%08lx %08lx\n",
arg, qp->q_forw,qp->q_back);
qp = qp->q_forw;
for (; qp != &buckets[arg]; qp = qp->q_forw) {
p = FROMBUK(qp);
if (dump(p))
break;
}
} else {
printf("Buckets:");
for (qp=buckets; qp<&buckets[NBUCKETS];qp++){
if (qp->q_forw != qp)
printf(" %d", qp-buckets);
}
printf("\n");
}
break;
case 'e':
endfree = 1;
break;
case 'E':
endfree = 0;
break;
case 'f':
if (nargs != 2) goto bad;
sscanf(arg2,"%lx",&arg);
printf("free(%x)\n",arg);
free(arg);
break;
case 'F':
if (nargs != 2) goto bad;
sscanf(arg2,"%lx",&arg);
printf("forget(%x)\n",arg);
forget(arg);
break;
case 'h':
printf("\
b print bucket chains that aren't empty\n\
b [n] trace through bucket chains\n\
e turn on freeing of end of memory\n\
E turn off freeing of end of memory\n\
f addr free addr\n\
F addr forget below addr\n\
h print this help file\n\
m bytes malloc bytes\n\
q quit\n\
r addr bytes realloc\n\
s print break addr\n\
S sbrk count\n\
t trace through adjacency chain\n\
");
break;
case 'm':
if (nargs != 2) goto bad;
arg = atoi(arg2);
res = malloc(arg);
printf("malloc(%d) = %lx\n",arg, res);
break;
case 'r':
if (nargs != 3) goto bad;
sscanf(arg2,"%lx",&arg);
argn = atoi(arg3);
res = realloc(arg,argn);
printf("realloc(%lx,%d) = %lx\n",arg,argn,res);
break;
case 'q':
exit(0);
break;
case 's':
printf("brk = %08x\n",sbrk(0));
break;
case 'S':
if (nargs != 2) goto bad;
sscanf(arg2,"%ld",&arg);
printf("sbrk(%d)\n",arg);
sbrk(arg);
break;
case 't':
printf("\t\t\t\t\t\thead adj=%08lx %08lx\n",
adjhead.q_forw,adjhead.q_back);
for (qp = adjhead.q_forw; qp!=&adjhead; qp=qp->q_forw) {
p = FROMADJ(qp);
if (dump(p))
break;
q = FROMADJ(qp->q_forw);
if (q==FROMADJ(&adjhead))
q = (struct overhead *)sbrk(0);
l = (char *)q - (char *)p - p->ov_length;
if (l>0)
printf("%08x free space len=%8d\n",
(char *)p + p->ov_length, l);
}
break;
default:
bad: printf("Bad command\n");
}
}
}
dump(p)
register struct overhead *p;
{
register char *s;
int stat = 0;
if (p->ov_magic == MAGIC_FREE)
s = "MAGIC_FREE ";
else if (p->ov_magic == MAGIC_BUSY)
s = "MAGIC_BUSY ";
else {
s = "BAD MAGIC ";
stat = 1;
}
printf( "%08x %s len=%8d buk=%08x %08x adj=%08x %08x\n",
(&p[1]),s,p->ov_length,p->ov_buk.q_forw,p->ov_buk.q_back,
p->ov_adj.q_forw,p->ov_adj.q_back
);
return(stat);
}
void
malerror()
{
write(2,"malloc error\n",13);
longjmp(env,1);
}
@@@End of mtest1.c
echo x - mtest2.c 1>&2
cat >mtest2.c <<'@@@End of mtest2.c'
/* NOT copyright by SoftQuad Inc. -- msb, 1988 */
#ifndef lint
static char *SQ_SccsId = "@(#)mtest2.c 1.2 88/08/25";
#endif
#include <stdio.h>
extern int atoi ();
extern long random ();
extern char *sbrk ();
extern char *malloc ();
extern char *realloc ();
extern int free ();
struct memevent {
int m_time; /* time to go */
char *m_memory; /* malloc'ed mem */
unsigned m_size; /* size of mem */
int m_id; /* id, for trace/debug */
int m_realloc; /* counter, for debugging */
char m_pattern; /* pattern in memory */
struct memevent *m_next; /* linked list pointer */
};
#ifndef MAX_EVENTS
#define MAX_EVENTS 10000
#endif
struct memevent eventpool[ MAX_EVENTS ];
struct memevent *events;
struct memevent *free_events;
char stdout_buf[ BUFSIZ ];
char stderr_buf[ BUFSIZ ];
int time_to_go;
int new_probability;
int realloc_probability = 25; /* XXX: should set from argv */
int stat_frequency;
main (argc, argv)
int argc;
char *argv[];
{
init (argc, argv);
run_test ();
}
/*
* run_test ()
*
* Run the actual memory test.
*/
run_test ()
{
while (time_to_go > 0) {
arrival ();
service ();
-- time_to_go;
if ((time_to_go % stat_frequency) == 0)
do_stats ();
}
}
/*
* arrival ()
*
* With probability new_probability/100, allocate a new piece
* of memory with some randomly determined size and lifetime,
* and add it to the memory event list.
*/
arrival ()
{
if (free_events && odds (new_probability, 100)) {
register struct memevent *m;
register char *p;
m = free_events;
free_events = m->m_next;
m->m_next = NULL;
/* XXX: let these be set from argv */
m->m_size = (unsigned) random_range (1, 100);
if (time_to_go < 100)
m->m_time = random_range (1, time_to_go);
else
m->m_time = random_range (1, 100);
m->m_pattern = (char) random_range (0, 127);
m->m_realloc = 0;
m->m_memory = malloc (m->m_size);
if (! m->m_memory)
out_of_memory ();
for (p = m->m_memory; p < & m->m_memory[ m->m_size ]; p++)
*p = m->m_pattern;
add_to_events (m);
}
} /* arrival */
/*
* do_stats ()
*/
do_stats ()
{
register struct memevent *m;
int i;
long total;
printf ("---------------------\nTIME Remaining: %d\n", time_to_go);
/* print other interesting but implementation-dependent stuff here
(like count of blocks in heap, size of heap, etc) */
total = 0;
for (i = 1, m = events; m != NULL; m = m->m_next, i++) {
printf ("EVENT %5d (id %5d): ", i, m->m_id);
printf ("SIZE %4d, ", m->m_size);
printf ("PATTERN 0x%02x, ", m->m_pattern & 0xFF);
printf ("TIME %4d ", m->m_time);
if (m->m_realloc > 0)
printf ("REALLOC %d", m->m_realloc);
printf ("\n");
total += m->m_size;
}
printf ("TOTAL events %d, allocated memory %d\n", i-1, total);
(void) fflush (stdout);
} /* do_stats */
/*
* service ()
*
* Decrement the time remaining on the head event. If
* it's time is up (zero), service it.
*
* Servicing an event generally means free'ing it (after checking
* for corruption). It is also possible (realloc_probability) to
* realloc the event instead.
*/
service ()
{
register struct memevent *m;
if ((m = events) != NULL)
-- m->m_time;
while (m != NULL && m->m_time == 0) {
register char *p;
for (p = m->m_memory; p < & m->m_memory[ m->m_size ]; p++) {
if (*p != m->m_pattern)
corrupted ();
}
events = m->m_next; /* delete this event */
if (time_to_go > 1 && odds (realloc_probability, 100))
realloc_event (m);
else
free_event (m);
m = events;
}
} /* service */
/*
* free_event (m)
*
* Called to free up the given event, including its memory.
*/
free_event (m)
register struct memevent *m;
{
free (m->m_memory);
m->m_next = free_events;
free_events = m;
}
/*
* realloc_event (m)
*
* Called from service(), to reallocate an event's memory,
* rather than freeing it.
*/
realloc_event (m)
register struct memevent *m;
{
register char *p;
unsigned new_size;
unsigned min_size;
/* XXX: let these be set from argv */
new_size = (unsigned) random_range (1, 100);
++ m->m_realloc; /* for stats */
m->m_memory = realloc (m->m_memory, new_size);
if (! m->m_memory)
out_of_memory ();
m->m_next = NULL;
if (time_to_go < 100)
m->m_time = random_range (1, time_to_go - 1);
else
m->m_time = random_range (1, 100); /* XXX: should set from argv */
min_size = new_size > m->m_size ? m->m_size : new_size;
for (p = m->m_memory; p < & m->m_memory[ min_size ]; p++) {
if (*p != m->m_pattern)
corrupted ();
}
m->m_size = new_size;
for (p = m->m_memory; p < & m->m_memory[ m->m_size ]; p++)
*p = m->m_pattern;
add_to_events (m);
} /* realloc_event */
/*
* add_to_events (m)
*
* Add the given event structure onto the time-ordered event list.
*/
add_to_events (m)
register struct memevent *m;
{
register struct memevent *l;
register struct memevent *ol;
for (ol = NULL, l = events; l != NULL; ol = l, l = l->m_next) {
if (l->m_time > m->m_time) {
if (ol == NULL) {
m->m_next = events;
events = m;
}
else {
m->m_next = l;
ol->m_next = m;
}
l->m_time -= m->m_time;
return;
}
m->m_time -= l->m_time;
}
if (events == NULL)
events = m;
else
ol->m_next = m;
} /* add_to_events */
/*
* init_events ()
*
* Set up the memevent pools.
*/
init_events ()
{
register struct memevent *m;
int i;
for (i = 0, m = eventpool; m < & eventpool[ MAX_EVENTS ]; m++, i++) {
m->m_id = i;
m->m_next = m + 1;
}
eventpool[ MAX_EVENTS-1 ].m_next = NULL;
free_events = eventpool;
}
/*
* init (argc, argv)
*
* Initialize the memory tests.
*/
init (argc, argv)
int argc;
char *argv[];
{
if (argc != 4) {
fprintf (stderr, "usage: %s new_prob time_to_go stat_freq\n", argv[ 0 ]);
exit (1);
}
new_probability = atoi (argv[ 1 ]);
time_to_go = atoi (argv[ 2 ]);
stat_frequency = atoi (argv[ 3 ]);
srandom (1);
init_events ();
/*
* Use statically allocated buffers, otherwise
* stdio() will call malloc to allocate buffers, and
* this gets confusing when debugging stuff.
*/
setbuf (stdout, (char *) NULL);
setbuf (stderr, (char *) NULL);
}
/*
* XXX: Should really send SIGQUIT ...
*/
cause_core_dump ()
{
* (long *) 1 = 5;
}
corrupted ()
{
printf ("Corrupted\n");
cause_core_dump ();
}
out_of_memory ()
{
printf ("Out of memory!\n");
cause_core_dump ();
}
/*
* odds (m, n)
*
* Return TRUE (non-zero) with probability m out of n.
*/
odds (m, n)
int m;
int n;
{
return ((random () % n) < m);
}
/*
* random_range (lo, hi)
*
* Pick a random integer from lo to hi (inclusive).
*/
random_range (lo, hi)
int lo;
int hi;
{
return ((random () % (hi - lo + 1)) + lo);
}
#if DBG
/*
* de_cmpf (m1,m2)
*
* compare function for qsort() in dump_events.
* Sort by memory address of the memory allocated to
* the event.
*/
int
de_cmpf (m1, m2)
struct memevent **m1;
struct memevent **m2;
{
unsigned long maddr1 = (unsigned long) (*m1)->m_memory;
unsigned long maddr2 = (unsigned long) (*m2)->m_memory;
/* sloppy */
return (maddr1 - maddr2);
}
#endif DBG
/*
* dump_events ()
*
* Useful for debugging.
*/
#if DBG
dump_events ()
{
static struct memevent *sorted[ MAX_EVENTS ];
register struct memevent *m;
register int i;
fprintf (stderr, "DUMP EVENTS (time remaining = %d)\n", time_to_go);
for (m = events, i = 0; m != NULL; m = m->m_next, i++)
sorted[ i ] = m;
if (i == 0) {
fprintf (stderr, "No events.\n");
return;
}
qsort ((char *) sorted, i, sizeof (struct memevent *), de_cmpf);
sorted[ i ] = 0;
for (i = 0, m = sorted[ 0 ]; m != NULL; m = sorted[ ++i ]) {
fprintf (stderr, "E# %3d: ", m->m_id);
fprintf (stderr, "SIZ%4d, ", m->m_size);
fprintf (stderr, "RANGE: 0x%08x -- 0x%08x ",
m->m_memory, m->m_memory + m->m_size - 1);
(void) fflush (stderr);
/* Peek at the surrounding longs,
for debugging a particular malloc
implementation. Your choices may
vary. */
fprintf (stderr, "BOUNDARY TAGS: %4d ", * (long *) (m->m_memory - 4));
(void) fflush (stderr);
fprintf (stderr, "%4d\n", * (long *) ((m->m_memory - 8) - (* (long *) (m->m_memory - 4))));
(void) fflush (stderr);
}
fprintf (stderr, "END DUMP_EVENTS\n");
(void) fflush (stderr);
} /* dump_events */
#endif DBG
@@@End of mtest2.c
echo x - mtest3.c 1>&2
cat >mtest3.c <<'@@@End of mtest3.c'
/* NOT copyright by SoftQuad Inc. -- msb, 1988 */
#ifndef lint
static char *SQ_SccsId = "@(#)mtest3.c 1.2 88/08/25";
#endif
#include <stdio.h>
/*
** looptest.c -- intensive allocator tester
**
** Usage: looptest
**
** History:
** 4-Feb-1987 rtech!daveb
*/
# ifdef SYS5
# define random rand
# else
# include <sys/vadvise.h>
# endif
# include <stdio.h>
# include <signal.h>
# include <setjmp.h>
# define MAXITER 1000000 /* main loop iterations */
# define MAXOBJS 1000 /* objects in pool */
# define BIGOBJ 90000 /* max size of a big object */
# define TINYOBJ 80 /* max size of a small object */
# define BIGMOD 100 /* 1 in BIGMOD is a BIGOBJ */
# define STATMOD 10000 /* interation interval for status */
main( argc, argv )
int argc;
char **argv;
{
register int **objs; /* array of objects */
register int *sizes; /* array of object sizes */
register int n; /* iteration counter */
register int i; /* object index */
register int size; /* object size */
register int r; /* random number */
int objmax; /* max size this iteration */
int cnt; /* number of allocated objects */
int nm = 0; /* number of mallocs */
int nre = 0; /* number of reallocs */
int nal; /* number of allocated objects */
int nfre; /* number of free list objects */
long alm; /* memory in allocated objects */
long frem; /* memory in free list */
long startsize; /* size at loop start */
long endsize; /* size at loop exit */
long maxiter = 0; /* real max # iterations */
extern char end; /* memory before heap */
char *calloc();
char *malloc();
char *sbrk();
long atol();
# ifndef SYS5
/* your milage may vary... */
vadvise( VA_ANOM );
# endif
if (argc > 1)
maxiter = atol (argv[1]);
if (maxiter <= 0)
maxiter = MAXITER;
printf("MAXITER %d MAXOBJS %d ", maxiter, MAXOBJS );
printf("BIGOBJ %d, TINYOBJ %d, nbig/ntiny 1/%d\n",
BIGOBJ, TINYOBJ, BIGMOD );
fflush( stdout );
if( NULL == (objs = (int **)calloc( MAXOBJS, sizeof( *objs ) ) ) )
{
fprintf(stderr, "Can't allocate memory for objs array\n");
exit(1);
}
if( NULL == ( sizes = (int *)calloc( MAXOBJS, sizeof( *sizes ) ) ) )
{
fprintf(stderr, "Can't allocate memory for sizes array\n");
exit(1);
}
/* as per recent discussion on net.lang.c, calloc does not
** necessarily fill in NULL pointers...
*/
for( i = 0; i < MAXOBJS; i++ )
objs[ i ] = NULL;
startsize = sbrk(0) - &end;
printf( "Memory use at start: %d bytes\n", startsize );
fflush(stdout);
printf("Starting the test...\n");
fflush(stdout);
for( n = 0; n < maxiter ; n++ )
{
if( !(n % STATMOD) )
{
printf("%d iterations\n", n);
fflush(stdout);
}
/* determine object of interst and it's size */
r = random();
objmax = ( r % BIGMOD ) ? TINYOBJ : BIGOBJ;
size = r % objmax;
i = r % (MAXOBJS - 1);
/* either replace the object of get a new one */
if( objs[ i ] == NULL )
{
objs[ i ] = (int *)malloc( size );
nm++;
}
else
{
/* don't keep bigger objects around */
if( size > sizes[ i ] )
{
objs[ i ] = (int *)realloc( objs[ i ], size );
nre++;
}
else
{
free( objs[ i ] );
objs[ i ] = (int *)malloc( size );
nm++;
}
}
sizes[ i ] = size;
if( objs[ i ] == NULL )
{
printf("\nCouldn't allocate %d byte object!\n",
size );
break;
}
} /* for() */
printf( "\n" );
cnt = 0;
for( i = 0; i < MAXOBJS; i++ )
if( objs[ i ] )
cnt++;
printf( "Did %d iterations, %d objects, %d mallocs, %d reallocs\n",
n, cnt, nm, nre );
printf( "Memory use at end: %d bytes\n", sbrk(0) - &end );
fflush( stdout );
/* free all the objects */
for( i = 0; i < MAXOBJS; i++ )
if( objs[ i ] != NULL )
free( objs[ i ] );
endsize = sbrk(0) - &end;
printf( "Memory use after free: %d bytes\n", endsize );
fflush( stdout );
if( startsize != endsize )
printf("startsize %d != endsize %d\n", startsize, endsize );
free( objs );
free( sizes );
exit( 0 );
}
@@@End of mtest3.c
echo x - realloc.c 1>&2
cat >realloc.c <<'@@@End of realloc.c'
#include "malloc.h"
#define NULL 0
/* NOT copyright by SoftQuad. - msb, 1988 */
#ifndef lint
static char *SQ_SccsId = "@(#)realloc.c 1.7 88/08/24";
#endif
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* realloc William L. Sebok
* A "smarter" malloc v1.0 Sept. 24, 1984 rev. Oct 17,1986
* Then modified by Arthur David Olsen
* MALLOCTRACE added by Mark Brader
*
* realloc takes previously malloc-allocated area at mem, and tries
* to change its size to nbytes bytes, moving it and copying its
* contents if necessary.
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#ifdef MALLOCTRACE /* See ./TRACE_README */
unsigned old_nbytes;
#endif
char *
realloc(mem,nbytes)
register char *mem; unsigned nbytes; /* for 4.3 compat. */
#ifdef MALLOCTRACE
/*
* The (real) realloc function may call malloc or not; we want
* to generate a trace message from here if it doesn't. And
* likewise for free. Since the function is somewhat complicated,
* this goal is most easily achieved by wrapping a dummy realloc
* function -- this one -- around the real realloc. The real
* realloc is imaginatively renamed real_realloc.
*/
{
char *real_realloc(), *newmem;
Size new_nbytes;
extern enum _malstate _malstate;
#define BYTES(mem) (((struct overhead *)(mem - sizeof(struct overhead))) \
->ov_length) /* How realloc finds the allocated length */
old_nbytes = 0; /* Normally changed in real_realloc */
if (_malstate == S_INITIAL) _mal_init_trace();
if (_malstate == S_TRACING)
_malstate = S_IN_REALLOC;
newmem = real_realloc (mem, nbytes);
if (_malstate == S_IN_REALLOC) {
_malstate = S_TRACING;
if (newmem) new_nbytes = BYTES (newmem);
_mal_write_trace ("realloc", (Size) old_nbytes,
(Size) old_nbytes, mem);
_mal_write_trace ("realloc-to", (Size) nbytes,
(Size) new_nbytes, newmem);
}
return newmem;
}
/*
* And now, the real realloc. If MALLOCTRACE is not defined,
* this function will of course compile as realloc.
*/
static char *
real_realloc(mem,nbytes)
register char *mem; unsigned nbytes;
#endif
{
register char *newmem = NULL;
register struct overhead *p;
Size surplus, length;
Size oldlength;
if (mem == NULL)
return(malloc(nbytes));
/* if beyond current arena it has to be bad */
if (mem > (char*)FROMADJ(adjhead.q_back) + sizeof(struct overhead))
return(NULL);
p = (struct overhead *)(mem - sizeof(struct overhead));
if (p->ov_magic != MAGIC_BUSY && p->ov_magic != MAGIC_FREE)
return(NULL); /* already gone */
oldlength = p->ov_length;
#ifdef MALLOCTRACE
old_nbytes = oldlength;
#endif
nbytes = ((nbytes + (NALIGN-1)) & (~(NALIGN-1)))
+ sizeof(struct overhead);
if (p->ov_magic == MAGIC_BUSY) {
/* free may claim adjacent free memory, compacting storage */
char oendfree = endfree;
endfree = 0;
free(mem); /* free it but don't let it contract break */
endfree = oendfree;
if (p->ov_magic != MAGIC_FREE) { /* check if moved */
p = FROMADJ(p->ov_adj.q_back);
newmem = (char *)p + sizeof(struct overhead);
}
}
/* at this point p->ov_magic should be MAGIC_FREE */
ASSERT(p->ov_magic == MAGIC_FREE, "\nrealloc: bad magic number.\n");
/*
** We wait to set length until after any possible compaction.
*/
length = p->ov_length;
surplus = length - nbytes;
if (surplus >= 0) {
/* present location large enough */
remque(TOBUK(p));
p->ov_magic = MAGIC_BUSY;
} else if ( ((char *)p + p->ov_length) == CURBRK) {
/* if at break, grow in place */
(void) BRK((char *)p + nbytes);
p->ov_length = nbytes;
remque(TOBUK(p));
p->ov_magic = MAGIC_BUSY;
} else {
newmem = malloc(nbytes - sizeof(struct overhead));
if (newmem == NULL)
return(NULL);
surplus = 0;
}
/* if returned address is different, move data */
if (newmem != NULL) {
/* note: it is assumed that bcopy does the right thing on
* overlapping extents (true on the vax)
*/
(void)bcopy(mem, newmem,
((oldlength < nbytes) ? oldlength : nbytes) -
sizeof(struct overhead));
mem = newmem;
}
/* if more memory than we need then return excess to buckets */
if (surplus > (int) sizeof(struct overhead)) {
register struct overhead *q;
q = (struct overhead *)( (char *)p + nbytes);
q->ov_length = surplus;
q->ov_magic = MAGIC_FREE;
insque(TOADJ(q),TOADJ(p));
{
register struct qelem * bp;
bp = &buckets[mlindx(surplus)];
if (bp > hifreebp)
hifreebp = bp;
insque(TOBUK(q),bp);
}
p->ov_length -= surplus;
}
if (endfree)
mlfree_end();
return(mem);
}
@@@End of realloc.c
echo x - write_trace.c 1>&2
cat >write_trace.c <<'@@@End of write_trace.c'
#ifdef MALLOCTRACE
/* NOT copyright by SoftQuad. - msb, 1988 */
#ifndef lint
static char *SQ_SccsId = "@(#)write_trace.c 1.4 88/08/24";
#endif
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* _mal_write_trace See ./ORIGINS for credits
*
* _mal_write_trace writes a line to the malloc trace file.
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#include <stdio.h>
#include "malloc.h"
/* Machine-dependent stuff: the Sun's stack format. */
struct stackframe {
struct stackframe *link;
char *ret_addr;
};
typedef struct stackframe *FRAMEPTR;
#define MYFRAME(myfirstarg) ((FRAMEPTR) (((Size *) &(myfirstarg)) - 2))
#define NEXTFRAME(myframe) ((myframe)->link)
#define RET_ADDR(myframe) ((myframe)->ret_addr)
/* Test whether a stdio file is still writable */
#define STDIO_WRITABLE(fp) (((fp)->_flag & _IOWRT) != NULL)
void
_mal_write_trace (event_label, req_nbytes, act_nbytes, mem)
char *event_label;
Size req_nbytes, act_nbytes;
char *mem;
{
extern enum _malstate _malstate;
extern FILE *_malfp;
extern int _malbuff;
FRAMEPTR frame;
if (_malstate != S_TRACING || !STDIO_WRITABLE(_malfp))
return;
/* Reset the state in case stdio does any mallocing */
_malstate = S_IN_STDIO;
if (req_nbytes == act_nbytes)
fprintf (_malfp, "%s of %ld at %ld\n",
event_label, (long) req_nbytes, (long) mem);
else
fprintf (_malfp, "%s of %ld gets %ld at %ld\n",
event_label, (long) req_nbytes, (long) act_nbytes,
(long) mem);
for (frame = NEXTFRAME (MYFRAME (event_label));
frame;
frame = NEXTFRAME (frame))
fprintf (_malfp, "caller %8.8lx\n", (long) RET_ADDR (frame));
fprintf (_malfp, "\n");
/* Flush if desired */
if (!_malbuff) fflush (_malfp);
/* And back to normal */
_malstate = S_TRACING;
}
#endif
@@@End of write_trace.c
echo x - Makefile 1>&2
cat >Makefile <<'@@@End of Makefile'
#
# SQ sccsid @(#)Makefile 1.4 88/08/25
# NOT copyright by SoftQuad. - msb, 1988
#
# This is configured to make the traced version of malloc; see mallck(1)
# and ./TRACE_README. To make the regular version, delete -DMALLOCTRACE.
# Mark Brader
#
CARGS= -O -DMALLOCTRACE
MALLOC_C = malloc.c free.c realloc.c forget.c write_trace.c init_trace.c
MALLOC_O = malloc.o free.o realloc.o forget.o write_trace.o init_trace.o
all: malloctrace.a
mtests: mtest1 mtest2 mtest3
install: malloctrace.a
mv malloctrace.a /usr/lib/malloctrace.a
.c.o: $*.c
${CC} -c ${CARGS} $*.c
$(MALLOC_O): malloc.h
malloctrace.a: $(MALLOC_O)
ar rv malloctrace.a $(MALLOC_O)
ranlib malloctrace.a
mtest1: mtest1.c
mtest2: mtest2.c
mtest3: mtest3.c
mtest1 mtest2 mtest3: malloctrace.a
${CC} -O $@.c malloctrace.a -o $@
clean:
rm -f *.o tstmalloc core
@@@End of Makefile
exit 0
--
Please send comp.sources.unix-related mail to rsalz@uunet.uu.net.