Source Code 1992 March

home *** CD-ROM | disk | FTP | other *** search

/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / compsrcs / unix / volume18 / malloctr.ace < prev next >

Wrap

Internet Message Format | 1989-03-27 | 67.7 KB

Path: wugate!wucs1!uunet!bbn.com!rsalz From: rsalz@uunet.uu.net (Rich Salz) Newsgroups: comp.sources.unix Subject: v18i066: Malloc package with tracing Message-ID: <1624@papaya.bbn.com> Date: 27 Mar 89 17:43:33 GMT Lines: 2636 Approved: rsalz@uunet.UU.NET 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.