schwartz@uw-taos.UUCP (Michael F. Schwartz) (07/10/87)
[I have a malloc package of my own which lets you call _malldmp() to dump
the malloc/free lists, _mallchk() to insure the list pointers are valid,
and set a flag to print all calls to malloc() or free(). Send mail for
info. ++bsa]
- Michael Schwartz
University of Washington Computer Science Department
Seattle, Washington, USA
schwartz@cs.washington.edu (ARPANET)
schwartz%cs.washington.edu@relay.cs.net (CSNET)
...{allegra,caip,ihnp4,nike}!uw-beaver!schwartz (UUCP)
#!/bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #!/bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create the files:
# README
# btree.c
# btree.h
# makefile
# maltrace.c
# test.c
# This archive created: Sun Apr 5 23:28:49 1987
export PATH; PATH=/bin:$PATH
echo shar: extracting "'README'" '(6452 characters)'
if test -f 'README'
then
echo shar: over-writing existing file "'README'"
fi
sed 's/^X//' << \SHAR_EOF > 'README'
X Malloc Leak Trace Package
X
X by Michael Schwartz
X University of Washington Computer Science Department
X Seattle, Washington, USA
X schwartz@cs.washington.edu (ARPANET)
X schwartz%cs.washington.edu@relay.cs.net (CSNET)
X ...{allegra,caip,ihnp4,nike}!uw-beaver!schwartz (UUCP)
X
X April 1987
X
X
X
X
X
X
X
X1. Description
X
XThis package is designed to help trace dynamic memory allocation leaks.
XIt works by providing the standard malloc/free/realloc interface, but at
Xthe same time keeping track of all malloc'd buffers, including their size,
Xorder of call, and address. That way, at any point during the execution of
Xyour program, you can see what malloc'd buffers haven't yet been freed.
XIt is particularly useful when your program performs many allocations
Xbefore reaching some steady state, and hence you want to ignore
Xthe initial allocations and concentrate on where steady-state
Xleaks occur.
X
XThe idea is that you have some code (usually a server) that looks as follows:
X initialization code;
X do {
X ...
X } while (1); /* main loop */
X
XThere might be some dynamic allocation during the initialization,
Xbut this isn't where the memory leak is, since it's a one-shot allocation
X(i.e., at worst the initialization wastes some memory, but doesn't
Xcontinually leak it). There might also be some dynamic allocation in
Xthe first few iterations of the main loop, until a "steady state" is
Xreached (e.g., until some cache gets filled). In both cases (initialization
Xand pre-steady state iterations), there may be many allocation calls, but
Xyou don't really want to look at them; rather, you want to look at what
Xmemory isn't being free'd once steady state has been reached. This
Xpackage helps you to see the state of memory allocation after steady
Xstate has been reached.
X
XBug reports and suggestions for improvements are welcome.
X
X
X
X
X
X
X
X2. Instructions
X
XTo use this package, take your favorite malloc/free/realloc code,
Xand change the routine names as follows:
X
X malloc -> mmalloc
X free -> ffree
X realloc -> rrealloc
X
XYou'll probably also need to add the following line to the beginning of
Xyour malloc.c:
X
X char *malloc();
X
X(because realloc still calls malloc, but malloc is no longer defined in
Xthat file). Then link the program to be leak-traced with maltrace.o,
Xbtree.o, and (your modified) malloc.o. I would have included my malloc.c,
Xbut it's the copyrighted BSD 4.3 code, and besides, there are plenty
Xof public domain malloc's available (e.g., in volume 6 of mod.sources).
X
XTo trace a leak, take the example program skeleton, and augment it as
Xfollows:
X extern int MalTraceEnbld;
X extern int MalBrkNum;
X initialization code;
X do {
X ...
X if ( steady state reached)
X MalTraceEnbld = 1;
X ...
X at end of first steady-state cycle:
X PMal(-10); /* print last 10 (say) malloc's
X that haven't yet been free'd */
X } while (1); /* main loop */
X
XThen compile the program with -g, and run it. At the end of the first
Xcycle, PMal will print a list of the last 10 malloc's that haven't yet been
Xfreed. (PMal(n) will print the first n entries if n > 0, the last -n
Xentries if n < 0, and all entries if n == 0). Note the sequence number of
Xone of these mallocs, and then go into dbx on the program, and put a
Xbreakpoint somewhere in the initialization code, and run the program. When
Xyou hit the breakpoint, use dbx to set MalBrkNum to the number of the
Xmalloc you just noticed, and set a break in MalBreak. Then, continue the
Xprogram. When the malloc call in question is reached, MalBreak will get
Xcalled, breaking, and giving you a chance to examine the state of the
Xprogram at the time of this (potentially leaking) malloc call. In case
Xthis call is still within the steady-state setup (it is sometimes difficult
Xto find where the setup ends), you can use dbx to call NextMal, to set
XMakBrkNum to be the next traced malloc call.
X
X
X
X
X
X
X
X2.1 Usage Details
X
XThis technique is not applicable to situations where the steady state
Xallocation behavior (i.e., order and size of malloc requests) exhibits
Xvariation, e.g., due to pseudo-randomization or interaction with other
Xprocesses via non-deterministically ordered message exchanges. In such
Xsituations you can sometimes inhibit the variation during debugging (e.g.,
Xby forcing interactions to occur in the same order each time).
XAlternatively, you can use dbx to set MalBreakSize to be the size of the
Xmalloc request at which to have MalBreak called, to reach a breakpoint
X(similar to the MalBrkNum scheme described above). This can be useful when
Xthe order of mallocs isn't fixed, but a particular size keeps showing up in
Xthe list of malloc's that haven't yet been free'd.
X
XThere is also a routine called UntracedFree that gets called when a free
Xcall is made on an address that was not malloc'd with tracing enabled
X(again, this routine is present to allow one to set dbx breakpoints for
Xthis event). This could either indicate a free call on an address that
Xisn't malloc'd (a bug) or a free call on an address that was malloc'd with
Xtracing disabled. You can determine if it was of the former nature by
Xgoing through the standard malloc code. For example, in the BSD code, you
Xcan set the switches -DDEBUG and -DRCHECK to check for this and other
Xtypes of bugs. Alternatively, you can enable tracing from the very
Xbeginning of your program, and then any time UntracedFree gets called, it
Xindicates a free call on an addresss that isn't malloc'd.
X
X
X
X
X
X
X
X3. Interactive Demo
X
XYou can try out this package interactively by making the program 'test'.
XNote that if you tell it to free some memory that was not malloc'd (with
XMalTraceEnbld = 1), it will give you a warning and then try to free the
Xaddress anyway (for the reasons explained earlier). This may or may not
Xcause malloc/free to get into a bad state; in BSD malloc this can cause a
Xcore dump, for instance.
X
X
X
X
X
X
X
X4. Acknoledgements, History
X
XThanks to Richard Hellier from the University of Kent at Canterbury
X(rlh@ukc.UUCP) for the btree package (which I modified slightly for the
Xcurrent package). I probably could have implemented my trace package more
Xefficiently than it works currently (e.g., by incorporating the linked-list
Xand btree nodes into the malloc header nodes), but I was more into hacking
Xsomething together quickly that would solve my problems than making
Xefficient code. Besides, this code doesn't need to be efficient, since
Xit's only plugged in during debugging.
SHAR_EOF
if test 6452 -ne "`wc -c 'README'`"
then
echo shar: error transmitting "'README'" '(should have been 6452 characters)'
fi
echo shar: extracting "'btree.c'" '(14571 characters)'
if test -f 'btree.c'
then
echo shar: over-writing existing file "'btree.c'"
fi
sed 's/^X//' << \SHAR_EOF > 'btree.c'
X/***
X
X* module name:
X btree.c
X* function:
X Provide a library of routines for creating and manipulating
X B-Trees. The "order" of the B-Tree is controlled by a manifest
X constant.
X
X This module runs stand-alone with a dummy main program
X if the symbol STAND_ALONE is defined.
X* interface routines:
X BTREE
X Insert(dtm, tree) Insert DATUM dtm into B-tree "tree",
X returning a reference to the updated
X tree.
X BTREE
X Delete(key, tree) Remove the entry associated with "key"
X from the B-Tree. Returns a reference
X to the updated tree.
X
X DATUM *
X Search(key, tree) Look for key "key" in B-tree "tree".
X Return a reference to the matching
X DATUM if found, else NULL.
X
X Apply(t, func) Applies function "func" to every cell
X in the B-Tree -- uses an inorder
X traversal.
X* libraries used:
X standard
X* compile time parameters:
X cc -O -c btree.c
X* history:
X Richard Hellier, University of Kent at Canterbury,
X working from "Algorithms+Data Structures = Programs"
X by N.Wirth -- also, "Data Structures and Program Design" by B.Kruse
X Pub. Prentice-Hall.
X
X Modified for use in dynamic memory allocation leak trace tool
X by Mike Schwartz, 3-20-87. We call mmalloc and ffree instead of
X malloc and free here, since malloc and free call this btree package
X in the dynamic memory allocation leak detection package.
X
X***/
X
X#include "btree.h"
X
XDATUM NullDatum = {
X (char *) NULL,
X};
X
Xstatic BTREE NewNode;
X
X
X /*
X** ERROR -- Print an error message
X**
X** Write the error text to the
X** standard error stream.
X**
X** Parameters:
X** fmt -- Printf-style format string
X** arg[1-3] -- Arguments as needed.
X**
X** Returns:
X** None.
X**
X*/
X
X/* ARGSUSED */
X
XError(fmt, arg1, arg2, arg3)
Xchar *fmt;{
X fprintf(stderr, fmt, arg1, arg2, arg3);
X}
X
X /*
X** KEYCMP -- Compare two key values
X**
X** Like "strcmp" but use key
X** values rather than strings.
X**
X** Parameters:
X** key1 -- First key,
X** key2 -- Second key.
X**
X** Returns:
X** -1 if key1 < key2;
X** 0 if key1 = key2;
X** 1 if key1 > key2;
X**
X*/
X
XKeyCmp(key1, key2)
XKEY key1,
X key2;{
X
X return key1 < key2 ? -1 : key1 == key2 ? 0 : 1;
X}
X
X /*
X** SHOWDATUM -- Display a datum
X**
X** Atomic routine used to display
X** the contents of a datum.
X**
X** Parameters:
X** datum -- Datum to print.
X**
X** Returns:
X** None.
X**
X*/
X
XShowDatum(dtm)
XDATUM dtm;{
X printf("\tkey x%x: callnum %d, size %d\n", dtm.key, dtm.inf.MalCallNum,
X dtm.inf.MalSize);
X}
X
X /*
X** MKNODE -- Make a new B-tree node
X**
X** Allocate storage for a new B-tree node
X** and copy in some pointers.
X**
X** Parameters:
X** k1 -- First key value,
X** p0 -- First ptr,
X** p1 -- Second ptr.
X**
X** Returns:
X** Reference to the new node.
X**
X*/
X
XBTREE
XMkNode(dtm, p0, p1)
XDATUM dtm;
XBTREE p0,
X p1;{
X char *mmalloc();
X BTREE t;
X
X t = (BTREE) mmalloc(sizeof(NODE));
X
X t -> t_ptr [0] = p0;
X t -> t_ptr [1] = p1;
X t -> t_dat [0] = dtm;
X t -> t_active = 1;
X
X return t;
X}
X /*
X** DISPOSE -- Dispose of a tree node
X**
X** Return the storage occupied by the
X** tree node to the pool.
X**
X** Parameters:
X** t -- Ptr to the tree node.
X**
X** Returns:
X** None.
X**
X*/
X
XDispose(t)
XBTREE t;{
X ffree((char *) t);
X}
X
X /*
X** INSINNODE -- Add a key to a node
X**
X** Add a key value into a
X** B-tree node. Splitting of
X** nodes is handled elsewhere.
X**
X** Parameters:
X** t -- Ptr to the node,
X** key -- Key value to enter,
X** ptr -- Link to subordinate node.
X**
X** Returns:
X** None.
X**
X*/
X
XInsInNode(t, d, ptr)
XBTREE t,
X ptr;
XDATUM d;{
X int i;
X
X for ( i = t -> t_active; i > 0 && KeyCmp(d . key, t -> t_dat [i-1] . key) < 0; i--) {
X t -> t_dat [i] = t -> t_dat [i - 1];
X t -> t_ptr [i + 1] = t -> t_ptr [i];
X }
X
X t -> t_active++;
X t -> t_dat [i] = d;
X t -> t_ptr [i+1] = ptr;
X}
X
X /*
X** INTERNALINSERT -- Key insert routine proper
X**
X** The business end of the key insertion
X** routine.
X**
X** Parameters:
X** key -- Key to insert,
X** t -- Tree to use.
X**
X** Returns:
X** Value of the key inserted.
X**
X*/
X
XDATUM
XInternalInsert(dtm, t)
XDATUM dtm;
XBTREE t;{
X int i,
X j;
X DATUM ins;
X BTREE tmp;
X
X if (t == NULL) {
X NewNode = NULL;
X return dtm;
X } else {
X for (i = 0; i < t -> t_active && KeyCmp(t -> t_dat [i] . key, dtm . key) < 0; ++i)
X ; /* NULL BODY */
X if (i < t -> t_active && KeyCmp(dtm . key, t -> t_dat [i] . key) == 0)
X fprintf(stderr, "Already had it!\n");
X else {
X ins = InternalInsert(dtm, t -> t_ptr [i]);
X
X if (KeyCmp(ins . key, NullDatum . key) != 0)
X if (t -> t_active < 2 * M)
X InsInNode(t, ins, NewNode);
X else {
X if (i <= M) {
X tmp = MkNode(t -> t_dat [2 * M - 1], (BTREE) NULL, t -> t_ptr [2 * M]);
X t -> t_active--;
X InsInNode(t, ins, NewNode);
X } else
X tmp = MkNode(ins, (BTREE) NULL, NewNode);
X /*
X * Move keys and pointers ...
X */
X
X for (j = M + 2; j <= 2 * M; ++j)
X InsInNode(tmp, t -> t_dat [j-1], t -> t_ptr [j]);
X
X t -> t_active = M;
X tmp -> t_ptr [0] = t -> t_ptr [M+1];
X NewNode = tmp;
X
X return t -> t_dat [M];
X }
X }
X return NullDatum;
X }
X}
X /*
X** INSERT -- Put a key into the B-tree
X**
X** Enter the given key into the
X** B-tree.
X**
X** Parameters:
X** key -- Key value to enter.
X**
X** Returns:
X** Reference to the new B-tree.
X**
X*/
X
XBTREE
XInsert(dtm, t)
XDATUM dtm;
XBTREE t;{
X DATUM ins;
X
X ins = InternalInsert(dtm, t);
X
X /*
X * Did the root grow ?
X */
X
X return KeyCmp(ins . key, NullDatum . key) != 0 ? MkNode(ins, t, NewNode) : t;
X}
X /*
X** DELETE -- Remove a key from a B-tree
X**
X** Remove the data associated with a
X** given key from a B-tree.
X**
X** Parameters:
X** key -- Key to use,
X** t -- B-tree to update.
X**
X** Returns:
X** Reference to the updated B-tree.
X**
X** Notes:
X** Real work is done by RealDelete() q.v.
X**
X*/
X
Xstatic int hadit = FALSE;
X
XBTREE
XDelete(key, t)
XKEY key;
XBTREE t;{
X BTREE savet;
X
X RealDelete(key, t);
X
X if (!hadit) {
X Error("No such key\n");
X return NULL;
X } else if (t -> t_active == 0) { /* Root is now empty */
X savet = t -> t_ptr [0];
X Dispose(t);
X return savet;
X } else
X return t;
X}
X
X /*
X** SEARCHNODE -- Find a key in a node
X**
X** Look for a key in a single B-tree
X** node.
X**
X** Parameters:
X** key -- Key to look for,
X** t -- Ptr to B-tree node.
X**
X** Returns:
X** Index of matching key.
X**
X*/
X
Xint
XSearchNode(key, t)
XKEY key;
XBTREE t;{
X int i;
X
X if (KeyCmp(key, t -> t_dat [0] . key) < 0) {
X hadit = FALSE;
X return 0;
X } else {
X for (i = t -> t_active; KeyCmp(key, t -> t_dat [i-1] . key) < 0 && i > 1; --i)
X ; /* NULL BODY */
X hadit = (KeyCmp(key, t -> t_dat [i-1] . key) == 0);
X
X return i;
X }
X}
X /*
X** REALDELETE -- Remove a key from a tree
X**
X** The business end of the Delete() function.
X**
X** Parameters:
X** key -- Key to use,
X** t -- Tree to update.
X**
X** Returns:
X** None.
X**
X*/
X
XRealDelete(key, t)
XKEY key;
XBTREE t;{
X int k;
X
X if (t == NULL)
X hadit = FALSE;
X else {
X k = SearchNode(key, t);
X
X if (hadit) {
X if (t -> t_ptr [k-1] == NULL) /* A leaf */
X Remove(t, k);
X else {
X Succ(t, k);
X RealDelete(t -> t_dat [k-1] . key, t -> t_ptr [k]);
X if (!hadit)
X Error("Hmm ???");
X }
X } else {
X RealDelete(key, t -> t_ptr [k]);
X
X if (t -> t_ptr [k] != NULL && t -> t_ptr [k] -> t_active < M)
X Restore(t, k);
X }
X }
X}
X
X /*
X** REMOVE -- Remove a single datum
X**
X** Remove a datum from a B-tree node
X** by shuffling down the pointers and
X** data above it.
X**
X** Parameters:
X** t -- Ptr to the B-tree node,
X** pos -- Index of the key to be removed.
X**
X** Returns:
X** None.
X**
X*/
X
XRemove(t, pos)
XBTREE t;
Xint pos;{
X int i;
X
X for (i = pos + 1; i <= t -> t_active; ++i) {
X t -> t_dat [i-2] = t -> t_dat [i-1];
X t -> t_ptr [i-1] = t -> t_ptr [i];
X }
X t -> t_active--;
X}
X
X /*
X** SUCC -- Replace a key by its successor
X**
X** Using the natural ordering, replace
X** a key with its successor.
X**
X** Parameters:
X** t -- Ptr to a B-tree node,
X** pos -- Index of the key to be succ'ed.
X**
X** Returns:
X** None.
X**
X** Notes:
X** This routine relies on the fact
X** that if the key to be deleted is
X** not in a leaf node, then its
X** immediate successor will be.
X*/
X
XSucc(t, pos)
XBTREE t;
Xint pos;{
X BTREE tsucc;
X
X /*
X * Using the branch *above* the key
X * chain down to leftmost node below
X * it.
X */
X
X for (tsucc = t -> t_ptr [pos]; tsucc -> t_ptr [0] != NULL; tsucc = tsucc -> t_ptr [0])
X ; /* NULL BODY */
X
X t -> t_dat [pos-1] = tsucc -> t_dat [0];
X}
X /*
X** RESTORE -- Restore balance to a B-tree
X**
X** After removing an item from a B-tree
X** we must restore the balance.
X**
X** Parameters:
X** t -- Ptr to the B-tree node,
X** pos -- Index of the out-of-balance point.
X**
X** Returns:
X** None.
X**
X*/
X
XRestore(t, pos)
XBTREE t;
Xint pos;{
X if (pos > 0) {
X if (t -> t_ptr [pos - 1] -> t_active > M)
X MoveRight(t, pos);
X else
X Combine(t, pos);
X } else {
X if (t -> t_ptr [1] -> t_active > M)
X MoveLeft(t, 1);
X else
X Combine(t, 1);
X }
X}
X
X /*
X** MOVERIGHT -- Shuffle keys up
X**
X** Make room for a key in a B-tree
X** node.
X**
X** Parameters:
X** t -- Ptr to the B-tree node,
X** pos -- Index of the first key
X** to be moved.
X**
X** Returns:
X** None.
X**
X*/
X
XMoveRight(t, pos)
XBTREE t;
Xint pos;{
X int i;
X BTREE tpos;
X
X tpos = t -> t_ptr [pos];
X
X for (i = tpos -> t_active; i >= 1; i--) {
X tpos -> t_dat [i] = tpos -> t_dat [i-1];
X tpos -> t_ptr [i+1] = tpos -> t_ptr [i];
X }
X
X tpos -> t_ptr [1] = tpos -> t_ptr [0];
X tpos -> t_active++;
X tpos -> t_dat [0] = t -> t_dat [pos-1];
X
X tpos = t -> t_ptr [pos-1];
X
X t -> t_dat [pos-1] = tpos -> t_dat [tpos -> t_active-1];
X t -> t_ptr [pos] -> t_ptr [0] = tpos -> t_ptr [tpos -> t_active];
X tpos -> t_active--;
X}
X /*
X** MOVELEFT -- Shuffle keys down
X**
X** Shuffle keys down after a removal
X** from a B-tree node.
X**
X** Parameters:
X** t -- Ptr to the B-tree node,
X** pos -- Index of the first key
X** to be moved.
X**
X** Returns:
X** None.
X**
X*/
X
XMoveLeft(t, pos)
XBTREE t;
Xint pos;{
X int i;
X BTREE tpos;
X
X tpos = t -> t_ptr [pos-1];
X
X tpos -> t_active++;
X tpos -> t_dat [tpos -> t_active-1] = t -> t_dat [pos-1];
X tpos -> t_ptr [tpos -> t_active] = t -> t_ptr [pos] -> t_ptr [0];
X
X
X tpos = t -> t_ptr [pos];
X
X t -> t_dat [pos-1] = tpos -> t_dat [0];
X tpos -> t_ptr [0] = tpos -> t_ptr [1];
X tpos -> t_active--;
X
X for (i = 1; i <= tpos -> t_active; ++i) {
X tpos -> t_dat [i-1] = tpos -> t_dat [i];
X tpos -> t_ptr [i] = tpos -> t_ptr [i+1];
X }
X}
X /*
X** COMBINE -- Combine two nodes.
X**
X** Coalesce two nodes of a
X** B-tree when they have too few nodes.
X**
X** Parameters:
X** t -- Ptr to B-tree node,
X** pos -- Index of the split point.
X**
X** Returns:
X** None.
X**
X*/
X
XCombine(t, k)
XBTREE t;
Xint k;{
X int i;
X BTREE p,
X q;
X
X p = t -> t_ptr [k-1];
X q = t -> t_ptr [k];
X
X p -> t_active++;
X p -> t_dat [p -> t_active-1] = t -> t_dat [k-1];
X p -> t_ptr [p -> t_active] = q -> t_ptr [0];
X
X for (i = 1; i <= q -> t_active; ++i) {
X p -> t_active++;
X p -> t_dat [p -> t_active-1] = q -> t_dat [i-1];
X p -> t_ptr [p -> t_active] = q -> t_ptr [i];
X }
X
X for (i = k; i <= t -> t_active - 1; ++i) {
X t -> t_dat [i-1] = t -> t_dat [i];
X t -> t_ptr [i] = t -> t_ptr [i+1];
X }
X t -> t_active--;
X
X Dispose(q);
X}
X
X /*
X** SEARCH -- Fetch a key from a tree
X**
X** Look for a key in a tree.
X**
X** Parameters:
X** key -- Key value to look for,
X** t -- Tree to look in.
X**
X** Returns:
X** None.
X**
X*/
X
XDATUM *
XSearch(key, t)
XKEY key;
XBTREE t;{
X int i;
X
X while (t != NULL) {
X for (i = 0; i < t -> t_active && KeyCmp(t -> t_dat [i] . key, key) < 0; ++i)
X ; /* NULL BODY */
X
X if (i < t -> t_active && KeyCmp(key, t -> t_dat [i] . key) == 0) {
X /* FOUND IT */
X return &t -> t_dat [i];
X }
X t = t -> t_ptr [i];
X }
X return NULL;
X}
X /*
X** SHOWTREE -- Display a tree
X**
X** Print the contents of
X** a tree, showing the level
X** of each node.
X**
X** Parameters:
X** t -- Tree to print,
X** level -- Depth in tree.
X**
X** Returns:
X** None.
X**
X*/
X
XShowTree(t, level)
XBTREE t;
Xint level;{
X int i;
X
X if (t != NULL) {
X for (i = 0; i < level; ++i)
X putchar(' ');
X for (i = 0; i < t -> t_active; ++i)
X ShowDatum(t -> t_dat [i]);
X putchar('\n');
X for (i = 0; i <= t -> t_active; ++i)
X ShowTree(t -> t_ptr [i], 1 + level);
X }
X}
X
X /*
X** APPLY -- Apply a function to a b-tree
X**
X** Traverse a B-tree, applying the function
X** to each key we find.
X**
X** Parameters:
X** t -- The tree to display,
X** func -- The function to apply.
X**
X** Returns:
X** None.
X**
X*/
X
XApply(t, func)
XBTREE t;
Xint (*func)();{
X int i;
X
X if (t != NULL) {
X for (i = 0; i < t -> t_active; ++i) {
X Apply(t -> t_ptr [i], func);
X (*func) (t -> t_dat [i]);
X }
X Apply(t -> t_ptr [t -> t_active], func);
X }
X}
X#ifdef STAND_ALONE
Xmain(){
X BTREE t,
X oldt;
X DATUM d,
X *dp;
X KEY k;
X char buf [BUFSIZ];
X
X t = NULL;
X
X printf("Command: "); fflush(stdout);
X while (fgets(buf, sizeof buf, stdin) != NULL) {
X buf [strlen(buf) - 1] = '\0';
X
X /*
X * Get the command
X */
X
X switch (buf [0]) {
X default: /* Error case */
X fprintf(stderr, "I, D, L, P or S please!\n");
X break;
X
X case '0':
X case '1':
X case '2':
X case '3':
X case '4':
X case '5':
X case '6':
X case '7':
X case '8':
X case '9':
X sscanf(buf, "%d", &d . key);
X t = Insert(d, t);
X break;
X
X case 'S': /* Set up default tree */
X t = NULL;
X d . key = 20;
X t = Insert(d, t);
X d . key = 10;
X t = Insert(d, t);
X d . key = 15;
X t = Insert(d, t);
X d . key = 30;
X t = Insert(d, t);
X d . key = 40;
X t = Insert(d, t);
X d . key = 7;
X t = Insert(d, t);
X d . key = 18;
X t = Insert(d, t);
X d . key = 22;
X t = Insert(d, t);
X d . key = 26;
X t = Insert(d, t);
X d . key = 5;
X t = Insert(d, t);
X d . key = 35;
X t = Insert(d, t);
X d . key = 13;
X t = Insert(d, t);
X d . key = 27;
X t = Insert(d, t);
X d . key = 32;
X t = Insert(d, t);
X d . key = 42;
X t = Insert(d, t);
X d . key = 46;
X t = Insert(d, t);
X d . key = 24;
X t = Insert(d, t);
X d . key = 45;
X t = Insert(d, t);
X d . key = 25;
X t = Insert(d, t);
X ShowTree(t, 0);
X break;
X
X case 'I': /* Insert a key */
X sscanf(buf+1, "%d", &d . key);
X t = Insert(d, t);
X break;
X
X case 'D': /* Delete a key */
X sscanf(buf+1, "%d", &d . key);
X oldt = t;
X t = Delete(d . key, t);
X if (t == NULL)
X t = oldt;
X break;
X
X case 'L': /* Lookup a key */
X sscanf(buf+1, "%d", &d . key);
X dp = Search(d . key, t);
X printf("%s\n",
X dp != NULL ? "Found it" : "No such key");
X break;
X
X case 'P': /* Show the tree */
X ShowTree(t, 0);
X break;
X }
X printf("Command: "); fflush(stdout);
X }
X Apply(t, ShowDatum);
X exit(0);
X}
X#endif STAND_ALONE
SHAR_EOF
if test 14571 -ne "`wc -c 'btree.c'`"
then
echo shar: error transmitting "'btree.c'" '(should have been 14571 characters)'
fi
echo shar: extracting "'btree.h'" '(801 characters)'
if test -f 'btree.h'
then
echo shar: over-writing existing file "'btree.h'"
fi
sed 's/^X//' << \SHAR_EOF > 'btree.h'
X#include <stdio.h>
X
X
X /*
X * Global structures and definitions
X */
X
X
X#define TRUE 1
X#define FALSE 0
X
X /*
X * Declare the type of the KEY
X */
X
Xtypedef char * KEY; /* Key = addr returned from malloc */
X
X
X /*
X * ... ditto for the INFO field
X */
X
Xtypedef struct {
X int MalCallNum; /* malloc call number */
X int MalSize; /* malloc'd size */
X char * MalAddr; /* malloc'd address */
X struct list *lp;
X} INFO;
X
Xtypedef struct Datum {
X KEY key;
X INFO inf;
X} DATUM;
X
X /*
X * This is the definition of
X * the nodes of the B-Tree
X */
X
X#define M 2
Xtypedef struct btnode {
X int t_active; /* # of active keys */
X DATUM t_dat [2 * M]; /* Keys + Data */
X struct btnode *t_ptr [2 * M + 1]; /* Subtree ptrs */
X} NODE, *BTREE;
X
XBTREE Insert();
X
XBTREE Delete();
X
XDATUM *Search();
X
Xint Apply();
SHAR_EOF
if test 801 -ne "`wc -c 'btree.h'`"
then
echo shar: error transmitting "'btree.h'" '(should have been 801 characters)'
fi
echo shar: extracting "'makefile'" '(177 characters)'
if test -f 'makefile'
then
echo shar: over-writing existing file "'makefile'"
fi
sed 's/^X//' << \SHAR_EOF > 'makefile'
XCFLAGS = -g
X
Xmaltrace.a: maltrace.o malloc.o btree.o
X ar rvu maltrace.a maltrace.o malloc.o btree.o
X ranlib maltrace.a
X
Xtest: test.o maltrace.a
X cc -g -o test test.o maltrace.a
SHAR_EOF
if test 177 -ne "`wc -c 'makefile'`"
then
echo shar: error transmitting "'makefile'" '(should have been 177 characters)'
fi
echo shar: extracting "'maltrace.c'" '(5349 characters)'
if test -f 'maltrace.c'
then
echo shar: over-writing existing file "'maltrace.c'"
fi
sed 's/^X//' << \SHAR_EOF > 'maltrace.c'
X/* Code for dynamic memory allocation leak trace tool. By Mike
X Schwartz, 3-20-87. */
X
X#include "btree.h"
X
XBTREE MalBtree = NULL;
Xint MalTraceEnbld = 0; /* Flag to enable/disable tracing of malloc/free
X calls. Need to turn it off sometime (e.g.,
X during printf calls, since printf (indirectly)
X calls malloc/free, and during
X uninteresting/debugged initialization code) */
X
Xint MallocCallCounter = 0;
Xint NumPendingMallocs = 0;
Xint MalBrkNum = -1; /* Malloc call number at which to call MalBreak routine */
Xint MalBrkSize = -1; /* Malloc size at which to call MalBreak routine */
Xstruct list {
X KEY MalAddr;
X struct list *prev;
X struct list *next;
X};
Xstruct list *ListHead = NULL, *ListTail = NULL;
X
Xchar *
Xmalloc(nbytes)
X unsigned nbytes;
X{
X char *mmalloc(), *MalAddr;
X struct list *lp;
X DATUM datum, *dp;
X
X MalAddr = mmalloc(nbytes);
X if (MalTraceEnbld == 1) { /* printf calls malloc/free */
X datum.key = MalAddr;
X datum.inf.MalCallNum = ++MallocCallCounter;
X datum.inf.MalSize = nbytes;
X datum.inf.MalAddr = MalAddr;
X MalBtree = Insert(datum, MalBtree);
X NumPendingMallocs++;
X dp = Search(MalAddr, MalBtree);
X /* Insert in ordered doubly linked list of mallocs */
X lp = (struct list *) mmalloc(sizeof(struct list));
X lp->MalAddr = MalAddr;
X (dp->inf).lp = lp;
X if (ListHead == NULL) {
X ListHead = lp;
X lp->prev = NULL;
X } else {
X ListTail->next = lp;
X lp->prev = ListTail;
X }
X lp->next = NULL;
X ListTail = lp;
X#ifdef DEBUG_MAL_TRACE
X MalTraceEnbld = 0; /* printf calls malloc/free */
X printf("\tmalloc(%d)=x%x\n", nbytes, MalAddr);
X fflush(stdout);
X MalTraceEnbld = 1;
X#endif DEBUG_MAL_TRACE
X if (MallocCallCounter == MalBrkNum || MalBrkSize == nbytes)
X MalBreak(); /* So we can hit dbx(1) breakpoint */
X }
X return(MalAddr);
X}
X
Xfree(cp)
X char *cp;
X{
X struct list *lp;
X DATUM datum, *dp;
X
X if (MalTraceEnbld == 1) {
X dp = Search(cp, MalBtree);
X if (dp == NULL) {
X MalTraceEnbld = 0; /* printf calls malloc/free */
X printf("\tfree(x%x): not malloc'd with MalTraceEnbld\n", cp);
X MalTraceEnbld = 1;
X UntracedFree();
X ffree(lp);
X return;
X }
X NumPendingMallocs--;
X
X lp = (dp->inf).lp;
X
X /* Delete from ordered doubly linked list of mallocs */
X if (ListHead == lp) {
X ListHead = ListHead->next;
X } else {
X (lp->prev)->next = lp->next;
X }
X if (ListTail == lp) {
X ListTail = lp->prev;
X } else {
X (lp->next)->prev = lp->prev;
X }
X ffree(lp);
X MalBtree = Delete(cp, MalBtree);
X
X#ifdef DEBUG_MAL_TRACE
X MalTraceEnbld = 0; /* printf calls malloc/free */
X printf("\tfree(x%x)\n", cp);
X fflush(stdout);
X MalTraceEnbld = 1;
X#endif DEBUG_MAL_TRACE
X }
X ffree(cp);
X}
X
X/* Don't need to modify btree/linked list structures here, since realloc
X will call malloc/free if it needs to, which will do the right thing. */
Xchar *
Xrealloc(cp, nbytes)
X char *cp;
X unsigned nbytes;
X{
X char *rrealloc(), *tmp;
X
X tmp=rrealloc(cp, nbytes);
X#ifdef DEBUG_MAL_TRACE
X if (MalTraceEnbld) {
X MalTraceEnbld = 0; /* printf calls malloc/free */
X printf("\trealloc(x%x, %d)=x%x\n", cp, nbytes, tmp);
X MalTraceEnbld = 1;
X }
X#endif DEBUG_MAL_TRACE
X return(tmp);
X}
X
X/* If n > 0, print (at most) the first n entries of list of pending info
X (i.e., mallocs which haven't yet been free'd). If n == 0, print all
X pending entries. If n < 0, print (at most) the last -n pending entries */
XPMal(n)
Xint n;
X{
X struct list *lp, *Start;
X DATUM datum, *dp;
X int i;
X int MalTraceInitialVal = MalTraceEnbld;
X char *OrdSuffix();
X
X MalTraceEnbld = 0; /* puts and printf call malloc/free */
X if (ListHead == NULL)
X puts("\tNo pending mallocs");
X else {
X Start = ListHead;
X if (n == 0)
X printf("\tPending mallocs (%d total):\n",
X NumPendingMallocs);
X else if (n == 1)
X printf("\tFirst pending malloc (of %d):\n",
X NumPendingMallocs);
X else if (n > 1)
X printf("\tFirst %d pending mallocs (of %d):\n",
X n, NumPendingMallocs);
X else {
X if (n == -1)
X printf("\tLast pending malloc (of %d):\n",
X NumPendingMallocs);
X else
X printf("\tLast %d pending mallocs (of %d):\n",
X -n, NumPendingMallocs);
X for (Start = ListTail, i = n + 1;
X Start != NULL && i < 0; Start = Start->prev, i++) {
X }
X if (Start == NULL)
X Start = ListHead;
X n = -n;
X }
X for (lp = Start, i = 0; lp != NULL; lp = lp->next, i++) {
X if (n != 0 && i >= n)
X break;
X dp = Search(lp->MalAddr, MalBtree);
X printf("\t%d%s malloc(%d): x%x\n",
X (dp->inf).MalCallNum,
X OrdSuffix((dp->inf).MalCallNum),
X (dp->inf).MalSize,
X (dp->inf).MalAddr);
X }
X }
X MalTraceEnbld = MalTraceInitialVal;
X return;
X}
X
X/* Return a character string suffix for the ordinal number n */
Xchar *
XOrdSuffix(n)
Xint n;
X{
X if ( (n % 100) > 10 && (n % 100) < 20)
X return("th");
X switch (n % 10) {
X case 0: case 4: case 5: case 6: case 7: case 8: case 9:
X return("th");
X case 1:
X return("st");
X case 2:
X return("nd");
X case 3:
X return("rd");
X }
X}
X
X
X
X/* Routines called to allow user to set dbx(1) breakpoints */
X
X/* Breakpoint in suspected leaking malloc call */
XMalBreak()
X{
X}
X
X/* Breakpoint in free call made on data not malloc'd with tracing enabled */
XUntracedFree()
X{
X}
X
X/* Set MalBrkNum to the next malloc call, for the next iteration of tracing */
XNextMal()
X{
X MalBrkNum = MallocCallCounter + 1;
X}
SHAR_EOF
if test 5349 -ne "`wc -c 'maltrace.c'`"
then
echo shar: error transmitting "'maltrace.c'" '(should have been 5349 characters)'
fi
echo shar: extracting "'test.c'" '(1898 characters)'
if test -f 'test.c'
then
echo shar: over-writing existing file "'test.c'"
fi
sed 's/^X//' << \SHAR_EOF > 'test.c'
X/* Test program for dynamic memory allocation leak trace tool. By Mike
X Schwartz, 3-20-87. */
X
X#include "btree.h"
X#include <stdio.h>
X
Xmain()
X{
X int size, n;
X extern int MalTraceEnbld;
X char buf[10];
X char *p, *malloc();
X extern BTREE MalBtree;
X
X MalTraceEnbld = 0; /* Only turn on malloc info printing/checking
X for direct calls (not for prints, etc.) */
X do {
X fputs("m/f/p/b: ", stdout);
X gets(buf);
X switch (buf[0]) {
X case 'm': /* interactive malloc */
X fputs("\t# bytes: ", stdout);
X scanf("%d", &size);
X gets(buf); /* throw away CR */
X MalTraceEnbld = 1;
X p = malloc(size);
X MalTraceEnbld = 0;
X printf("\tmalloc returned x%x\n", p);
X break;
X
X case 'f': /* interactive free */
X fputs("\taddr: ", stdout);
X scanf("%x", &p);
X gets(buf); /* throw away CR */
X MalTraceEnbld = 1;
X free(p);
X MalTraceEnbld = 0;
X break;
X
X case 'p': /* print pending (not yet freed)
X mallocs. If n > 0, print (at
X most) the first n entries. If n
X == 0, print all entries. If n <
X 0, print (at most) the last -n
X entries */
X fputs("\tnumber of mallocs to print: ", stdout);
X scanf("%d", &n);
X gets(buf); /* throw away CR */
X MalTraceEnbld = 1;
X PMal(n);
X fflush(stdout);
X MalTraceEnbld = 0;
X break;
X
X case 'b': /* print btree of pending mallocs */
X puts("btree of pending mallocs:");
X ShowTree(MalBtree, 0);
X break;
X
X default:
X puts("Invalid command; choose one of:");
X puts("\tm to malloc");
X puts("\tf to free");
X puts("\tp to print pending (not yet freed) mallocs");
X puts("\t(b to print the btree associated with pending mallocs)");
X break;
X }
X } while(1);
X}
SHAR_EOF
if test 1898 -ne "`wc -c 'test.c'`"
then
echo shar: error transmitting "'test.c'" '(should have been 1898 characters)'
fi
# End of shell archive
exit 0