mprof.tex

早期freebsd实现

rather than size: cons cell (c), floating point number (f), structure
or vector (s), and other (o).} of the memory allocated by each
function as a fraction of the memory allocated by all functions.  In
this example, 99\% of the memory allocated by the program was
allocated in {\tt make\_widget} for medium-sized objects.  Blank
columns indicate values less than 1\%.  The other size breakdown given
in the direct allocation table is for the memory that was allocated
and never freed.  The {\tt \%~all~kept} field contains a size
breakdown of the memory not freed by a particular function as a
fraction of all the memory not freed.  In the example, 99\% of the
unfreed memory was of medium-sized objects allocated by {\tt
make\_widget}.

\subsection{The Allocation Call Graph}

Understanding the memory allocation behavior of a programs sometimes
requires more information than just knowing the functions that are
directly responsible for memory allocation.  Sometimes, as happens in
Figure~\ref{C example figure}, the same allocation function is called
by several different functions for different purposes.  The allocation
call graph shows all the functions that were indirect callers of
functions that allocated memory.

Because the dynamic caller/callee relations of a program are numerous,
the dynamic call graph is a complex table with many entries.  Often,
the information provided by the first three tables is enough to allow
programmers to understand the memory allocation of their program.
Nevertheless, for a full understanding of the allocation behavior of
programs the allocation call graph is useful.  Figure \ref{call graph
figure} contains the allocation call graph for the producer/consumer
example and corresponds to the call graph profile generated by {\tt
gprof}. 	

\begin{figure}[ht]
\begin{singlespace}
{\scriptsize
\include{extable2}
}
\end{singlespace}

\caption{Allocation Call Graph for Producer/Consumer Example}
\label{call graph figure}
\end{figure}

The allocation call graph is a large table with an entry for each
function that was on a call chain when memory was allocated.  Each
table entry is divided into three parts.  The line for the function
itself (called the {\em entry function\/}); lines above that line,
each of which represents a caller of the entry function (the
ancestors), and lines below that line, each of which represents a
function called by the entry function (the descendents).  The entry
function is easy to identify in each table entry because a large rule
appears in the {\tt frac} column on that row.  In the first entry of
Figure \ref{call graph figure}, {\tt main} is the entry function;
there are no ancestors and two descendents.

The entry function line of the allocation call graph contains
information about the function itself.  The {\tt index} field provides
a unique index to help users navigate through the call graph.  The
{\tt self~$+$~desc} field contains the percent of total memory
allocated that was allocated in this function and its descendents.
The call graph is sorted by decreasing values in this field.  The {\tt
self} field contains the number of bytes that were allocated directly
in the entry function.  The {\tt size-func} fields contain a size
breakdown of the memory allocated in the function itself.  Some
functions, like {\tt main} (index 0) allocated no memory directly, so
the {\tt size-func} fields are all blank.  The {\tt called} field
shows the number of times this function was called during a memory
allocation, with the number of recursive calls recorded in the
adjacent field.

Each caller of the entry function is listed on a separate line above
it.  A summary of all callers is given on the top line of the entry if
there is more than one ancestor.  The {\tt self} field of ancestors
lists the number of bytes that the entry function and its descendents
allocated on behalf of the ancestor.  The {\tt size-ances} field
breaks down those bytes into size categories, while the {\tt
frac-ances} field shows the size breakdown of the bytes requested by
this ancestor as a fraction of bytes allocated at the request of all
ancestors.  For example, in the entry for function {\tt make\_widget}
(index 1), the ancestor {\tt make\_red\_widget} can be seen to have
requested 1,023,876 bytes of data from {\tt make\_widget}, 99\% of which
was of medium-sized objects.  Furthermore, calls from {\tt
make\_red\_widget} accounted for 50\% of the total memory allocated by
{\tt make\_widget} and its descendents.  Other fields show how many
calls the ancestor made to the entry function and how many calls the
ancestor made in total.  In a similar fashion, information about the
function's descendents appears below the entry function.

Had the memory leak table not already told us what objects were not
being freed, we could use the allocation call graph for the same
purpose.  The direct allocation table told us that {\tt make\_widget}
allocated 1,023,876 bytes of unfreed memory, all for medium-sized
objects.  From the allocation call graph, we can see that the function
{\tt make\_red\_widget} was the function calling {\tt make\_widget}
that requested 1,023,876 bytes of medium-sized objects.  

Cycles in the call graph are not illustrated in Figure~\ref{call graph
figure}.  As described in the next section, cycles obscure allocation
information among functions that are members of a cycle.  When the
parent/child relationships that appear in the graph are between
members of the same cycle, most of the fields in the graph must be
omitted.


\section{Implementation}
\label{implementing mprof}

We have implemented {\tt mprof} for use with C and Common Lisp
programs.  Since the implementations are quite similar, the C
implementation will be described in detail, and the minor differences
in the Lisp implementation will be noted at the end of the section.

\subsection{The Monitor} 

The first phase of {\tt mprof} is a monitor that is linked into the
executing application.  The monitor includes modified versions of {\tt
malloc} and {\tt free} that record information each time they are
invoked.  Along with {\tt malloc} and {\tt free}, {\tt mprof} provides
its own {\tt exit} function, so that when the application program
exits, the data collected by the monitor is written to a file.  The
monitor maintains several data structures needed to construct the
tables.

To construct the leak table, the monitor associates a list of the last
five callers in the call chain, the {\em partial call chain\/}, with
the object allocated.  {\tt mprof} augments every object allocated
with two items: an integer which is the object size as requested by
the user (since the allocator may allocate an object of a different
size for convenience), and a pointer to a structure that contains the
object's partial call chain and a count of allocations and frees of
objects with that call chain.  A hash table is used to map a partial
call chain to the structure containing the counters.  When an object
is allocated, its partial call chain is used as a hash key to retrieve
the structure containing the counters.  A pointer to the structure is
placed in the allocated object and the allocation counter is
incremented.  When the object is later freed, the pointer is followed
and the counter of frees is incremented.  Any partial call chain in
which the number of allocations does not match the number of frees
indicates a memory leak and is printed in the leak table.

To construct the allocation bin table, the monitor has a 1026-element
array of integers to count allocations and another 1026-element array
to count frees.  When objects of a particular size from 0--1024 bytes
are allocated or freed, the appropriated bin is incremented.  Objects
larger than 1024 bytes are grouped into the same bin.

The construction of the direct allocation table falls out directly
from maintaining the allocation call graph information, which is
described in the next section.

\subsection{Constructing the Allocation Call Graph}

To construct the allocation call graph, the monitor must associate the
number of bytes allocated with every function on the current dynamic
call chain, each time {\tt malloc} is called.  Consider the sample
call chain in Figure~\ref{cchain:fig}, which we abbreviate:
{\tt main}-$>${\tt foo}-$>${\tt bar}(24).

\begin{figure}[htbp]
\begin{verbatim}
     CALL STACK:                     MPROF RECORDS:
     main calls foo                       24 bytes over main -> foo
           foo calls bar                  24 bytes over foo -> bar
              bar calls malloc(24)        24 bytes allocated in bar
\end{verbatim}
\caption{Example of a Dynamic Call Chain}
\label{cchain:fig}
\end{figure}

In {\tt mprof}, the monitor traverses the entire call chain by
following return addresses.  This differs from {\tt gprof}, where only
the immediate caller of the current function is recorded.  {\tt gprof}
makes the assumption that each call takes an equal amount of time and
uses this assumption to reconstruct the complete dynamic call graph
from information only about the immediate callers.  In {\tt mprof}, we
actually traverse the entire dynamic call chain and need to make no
assumptions. 

In choosing to traverse the entire call chain, we have elected to
perform an operation that is potentially expensive both in time and
space.  One implementation would simply record every function in every
chain and write the information to a file (i.e., in the example we
would output [{\tt main}-$>${\tt foo}-$>${\tt bar}, 24]).  Considering that
many programs execute millions of calls to {\tt malloc} and that the
depth of a call chain can be hundreds of functions, the amount of
information could be prohibitive.

An alternative to recording the entire chain of callers is to break
the call chain into a set of caller/callee pairs, and associate the
bytes allocated with each pair in the chain.  For the call in the
example, we could maintain the pairs [{\tt main}, {\tt foo}] and [{\tt foo},
{\tt bar}], and associate 24 bytes with each pair.  Conceptually, the
data structure our monitor maintains is an association between
caller/callee pairs and the cumulative bytes allocated over the pair,
which we denote ([{\tt main}, {\tt foo}], 24).  To continue with the
example, if the next allocation was: {\tt main}-$>${\tt foo}-$>${\tt
otherbar}(10), where this is the first call to {\tt otherbar}, we
would update the byte count associated with the [{\tt main}, {\tt foo}] pair
to 34 from 24.  Furthermore, we would create a new association between
[{\tt foo}, {\tt otherbar}] and the byte count, 10.  A disadvantage
with this implementation is that the exact call chains are no longer
available.  However, from the pairs we can construct the correct
dynamic call graph of the program, which is the information that we
need for the allocation call graph.

For the overhead imposed by the monitor to be reasonable, we have to
make the association between caller/callee pairs and cumulative byte
counts fast.  We use a hash table in which the hash function is a
simple byte-swap XOR of the callee address.  Each callee has a list of
its callers and the number of allocated bytes associated with each
pair.  In an effort to decrease the number of hash lookups, we noted
that from allocation to allocation, most of the call chain remains the
same.  Our measurements show that on the average, 60--75\% of the call
chain remains the same between allocations.  This observation allows
us to cache the pairs associated with the current caller chain and to
use most of these pairs the next time a caller chain is recorded.
Thus, on any particular allocation, only a few addresses need to be
hashed.  Here are the events that take place when a call to {\tt
malloc} is monitored:

\begin{enumerate}
  \item The chain of return addresses is stored in a vector.
  \item The new chain is compared with the previous chain, and the point
at which they differ is noted.
  \item For the addresses in the chain that have not changed, the
caller/callee byte count for each pair is already available and is
incremented. 
  \item For new addresses in the chain, each caller/callee byte count is
looked up and updated.
  \item For the tail of the chain (i.e., the function that called {\tt
malloc} directly), the direct allocation information is recorded.
\end{enumerate}

Maintaining allocation call graph information requires a byte count
for every distinct caller/callee pair in every call chain that
allocates memory.  Our experience is that there are a limited number
of such pairs, even in very large C programs, so that the memory
requirements of the {\tt mprof} monitor are not large (see
section~\ref{mmeas:sec}).

\subsection{Reduction and Display}

The second phase of {\tt mprof} reads the output of the monitor,
reduces the data to create a dynamic call graph, and displays the data
in four tables.  The first part of the data reduction is to map the
caller/callee address pairs to actual function names.  A program {\tt
mpfilt} reads the executable file that created the monitor trace
(compiled so that symbol table information is retained), and outputs a
new set of function caller/callee relations.  These relations are then
used to construct the subset of the program's dynamic call graph that
involved memory allocation.

The call graph initially can contain cycles due to recursion in the
program's execution.  Cycles in the call graph introduce spurious
allocation relations, as is illustrated in Figure~\ref{recursive call
figure}.  In this example, {\tt main} is credited as being indirectly
responsible for 10 bytes, but because we only keep track of
caller/callee pairs, {\tt F} appears to have requested 20 bytes from
{\tt G}, even though only 10 bytes were allocated.

\begin{figure}[htbp]
\begin{verbatim}
        CALL STACK:                     MPROF RECORDS:
        main calls F                    (10 bytes over main -> F)
             F calls G                  (10 bytes over F -> G)
               G calls F                (10 bytes over G -> F)
                 F calls G              (10 MORE bytes over F -> G)
                   G calls malloc(10)   (10 bytes allocated in G)
\end{verbatim}
\caption{Problems Caused by Recursive Calls}