mprof.tex

早期freebsd实现

% Master File: mprof.tex
% Document type: LaTeX
\documentstyle[11pt,captions,doublespace,twoside]{article}

\input{defs}
\setstretch{1}

\fullpagestyle

\begin{document}

\title{A Memory Allocation Profiler for C and Lisp Programs
\footnotetext{This research
was funded by DARPA contract number N00039-85-C-0269 as part of the
SPUR research project.}}


\author{Benjamin Zorn \\
	Department of Computer Science \\
	University of Colorado at Boulder \\
	\\
	Paul Hilfinger \\
	Computer Science Division, Dept. of EECS \\
	University of California at Berkeley \\
	}

\date{}

\maketitle

\begin{singlespace}
\begin{abstract}        
This paper describes {\tt mprof}, a tool used to study the dynamic
memory allocation behavior of programs.  {\tt Mprof} records the
amount of memory that a function allocates, breaks down allocation
information by type and size, and displays a program's dynamic call
graph so that functions indirectly responsible for memory allocation
are easy to identify.  {\tt Mprof} is a two-phase tool.  The monitor
phase is linked into executing programs and records information each
time memory is allocated.  The display phase reduces the data
generated by the monitor and presents the information to a user in
several tables.  {\tt Mprof} has been implemented for C and Kyoto
Common Lisp.  Measurements of these implementations are presented.
\end{abstract}
\end{singlespace}


\section{Introduction}
\setlength{\parskip}{6pt plus 2pt}

Dynamic memory allocation, hereafter referred to simply as memory
allocation, is an important part of many programs.  By dynamic
allocation, we mean the memory allocated from the heap.  Unnecessary
allocation can decrease program locality and increase execution time
for the allocation itself and for possible memory reclamation.  If
reclamation is not performed, or if some objects are accidently not
reclaimed (a ``memory leak''), programs can fail when they reach the
memory size limit.  Programmers often write their own versions of
memory allocation routines to measure and reduce allocation overhead.
It is estimated that Mesa programmers spent 40\% of their time solving
storage-management related problems before automatic storage
reclamation techniques were introduced in Cedar~\cite{rovner85:gc}.
Even with automatic storage management, in which reclamation occurs
transparently, memory allocation has a strong effect on the
performance of programs~\cite{moon84:gc}.  Although memory allocation
is important, few software tools exist to help programmers understand
the memory allocation behavior of their programs.

{\tt Mprof} is a tool that allows programmers to identify where and
why dynamic memory is allocated in a program.  It records which
functions are directly responsible for memory allocation and also
records the dynamic call chain at an allocation to show which
functions were indirectly responsible for the allocation.  The design
of {\tt mprof} was inspired by the tool {\tt gprof}, a dynamic
execution profiler~\cite{graham83:gprof}.  {\tt gprof} is a very
useful tool for understanding the execution behavior of programs; {\tt
mprof} extends the ideas of {\tt gprof} to give programmers
information about the dynamic memory allocation behavior of their
programs. {\tt Mprof} is a two-phase tool.  A monitor phase is linked
into an executing application and collects data as the application
executes.  A reduction and display phase takes the data collected by
the monitor and presents it to the user in concise tables.

A profiling program such as {\tt mprof} should satisfy several
criteria.  First, a program monitor should not significantly alter the
behavior of the program being monitored.  In particular, a monitor
should not impose so much overhead on the program being monitored that
large programs cannot be profiled.  Second, a monitor should be easy
to integrate into existing applications.  To use {\tt mprof},
programmers simply have to relink their applications with a special
version of the system library.  No source code modifications are
required.  Finally, a monitor should provide a programmer with
information that he can understand and use to reduce the memory
allocation overhead of his programs.  We will present an example that
illustrates such a use of {\tt mprof}.

In Section \ref{using mprof}, we present a simple program and
describe the use of {\tt mprof} with respect to the example. In
Section \ref{implementing mprof} we discuss techniques for the
effective implementation of {\tt mprof} .  Section \ref{measurements}
presents some measurements of {\tt mprof}.  Section \ref{related work}
describes other memory profiling tools and previous work on which {\tt
mprof} is based, while Section \ref{conclusions} contains our
conclusions.

\section{Using {\tt mprof}}
\label{using mprof}

\subsection{A Producer/Consumer Example}

To illustrate how {\tt mprof} helps a programmer understand the memory
allocation in his program, consider the C program in Figure~\ref{C
example figure}.  In this program, a simplified producer/consumer
simulation, objects are randomly allocated by two producers and freed
by the consumer.  The function {\tt random\_flip}, which is not shown,
randomly returns 1 or 0 with equal probability.  The function {\tt
consume\_widget}, which is responsible for freeing the memory
allocated, contains a bug and does not free red widgets.  If the
simulation ran for a long time, memory would eventually be exhausted,
and the program would fail.

\begin{figure}[htbp]
\begin{singlespace}
{\footnotesize
\include{expr}
}
\end{singlespace}
\caption{A Simple Producer/Consumer Simulation Program}
\label{C example figure}
\end{figure}

In the example, {\tt make\_widget} is the only function that allocates
memory directly.  To fully understand the allocation behavior of the
program, we must know which functions called {\tt make\_widget} and
hence were indirectly responsible for memory allocation.  {\tt Mprof}
provides this information.

To use {\tt mprof}, programmers link in special versions of the system
functions {\tt malloc} and {\tt free}, which are called each time
memory is allocated and freed, respectively.  The application is then
run normally.  The {\tt mprof} monitor function, linked in with {\tt
malloc}, gathers statistics as the program runs and writes this
information to a file when the application exits.  The programmer then
runs a display program over the data file, and four tables are
printed: a list of memory leaks, an allocation bin table, a direct
allocation table, and a dynamic call graph.  Each table presents the
allocation behavior of the program from a different perspective.  The
rest of this section describes each of the tables for the C program in
Figure~\ref{C example figure}.

% Fields in the tables are described in detail in the appendix.

\subsection{The Memory Leak Table}

C programmers must explicitly free memory objects when they are done
using them.  Memory leaks arise when programmers accidently forget to
release memory.  Because Lisp reclaims memory automatically, the
memory leak table is not necessary in the Lisp version of {\tt mprof}.

The memory leak table tells a programmer which functions allocated the
memory associated with memory leaks.  The table contains a list of
partial call paths that resulted in memory that was allocated and not
subsequently freed.  The paths are partial because complete path
information is not recorded; only the last five callers on the call
stack are listed in the memory leak table.  In our simple example,
there is only one such path, and it tells us immediately what objects
are not freed.  Figure~\ref{memory leak figure} contains the memory
leak table for our example.

\begin{figure}[htbp]
\begin{singlespace}
{
\include{extable0a}
}
\end{singlespace}
\caption{Memory Leak Table for Producer/Consumer Example}
\label{memory leak figure}
\end{figure}

In larger examples, more than one path through a particular function
is possible.  We provide an option that distinguishes individual call
sites within the same function in the memory leak table if such a
distinction is needed.

\subsection{The Allocation Bin Table}

A major part of understanding the memory allocation behavior of a
program is knowing what objects were allocated.  In C, memory
allocation is done by object size; the type of object being allocated
is not known at allocation time.  The allocation bin table provides
information about what sizes of objects were allocated and what
program types correspond to the sizes listed.  This knowledge helps a
programmer recognize which data structures consume the most memory and
allows him to concentrate any space optimizations on them.

The allocation bin table breaks down object allocation by the size, in
bytes, of allocated objects.  Figure~\ref{allocation bin figure} shows
the allocation bin table for the program in Figure~\ref{C example
figure}.

\begin{figure}[htbp]
\begin{singlespace}
{
\include{extable0}
}
\end{singlespace}
\caption{Allocation Bin Table for Producer/Consumer Example}
\label{allocation bin figure}
\end{figure}

The allocation bin table contains information about objects of each
byte size from 0 to 1024 bytes and groups objects larger than 1024
bytes into a single bin.  For each byte size in which memory was
allocated, the allocation bin table shows the number of allocations of
that size ({\tt allocs}), the total number of bytes allocated to
objects of that size ({\tt bytes}), the number of frees of objects of
that size ({\tt frees}), the number of bytes not freed that were
allocated to objects of that size ({\tt kept}\footnote{The label {\tt
kept} is used throughout the paper to refer to objects that were never
freed.}), and user types whose size is the same as the bin size ({\tt
types}).  From the example, we can see that 10,000 widgets were
allocated by the program, but only 4,981 of these were eventually
freed, resulting in 1,023,876 bytes of memory lost to the memory leak.
The percentages show what fraction of all bins a particular bin
contributed.  This information is provided to allow a user to rapidly
determine which bins are of interest (i.e., contribute a substantial
percentage).  99\% is the largest percentage possible because we chose
to use a 2 character field width.

\subsection{The Direct Allocation Table}

Another facet of understanding memory allocation is knowing which
functions allocated memory and how much they allocated.  In C, memory
allocation is performed explicitly by calling {\tt malloc}, and so
programmers are often aware of the functions that allocate memory.
Even in C, however, knowing how much memory was allocated can point
out functions that do unnecessary allocation and guide the programmer
when he attempts to optimize the space consumption of his program.  In
Lisp, memory allocation happens implicitly in many primitive routines
such as {\tt mapcar}, {\tt *}, and {\tt intern}. The direct allocation
table can reveal unsuspected sources of allocation to Lisp
programmers.

Figure~\ref{direct allocation figure} contains the direct allocation
table for our example.  The direct allocation table corresponds to the
flat profile generated by {\tt gprof}.

\begin{figure}[htbp]
\begin{singlespace}
{\scriptsize
\include{extable1}
}
\end{singlespace}

\caption{Direct Allocation Table for Producer/Consumer Example}
\label{direct allocation figure}
\end{figure}

The first line of the direct allocation table contains the totals for
all functions allocating memory.  In this example, only one function,
{\tt make\_widget}, allocates memory.  The direct allocation table
prints percent of total allocation that took place in each function
({\tt \%~mem}), the number of bytes allocated by each function ({\tt
bytes}), the number of bytes allocated by the function and never freed
({\tt bytes kept}), and the number of calls made to the function that
resulted in allocation ({\tt calls}).  The {\tt \%~mem(size)} fields
contain a size breakdown\footnote{ Both the direct allocation table
and the dynamic call graph break down object allocation into four
categories of object size: small (s), from 0--32 bytes; medium (m),
from 33--256 bytes; large (l), from 257--2048 bytes; and extra large
(x), larger than 2048 bytes.  For Lisp, categorization is by type