Contact:
Garrett Arch Blythe (blythe@netscape.com)

Introduction

What makes one allocation footprint bloat and another allocation acceptable?  This is the question which prompted the creation of SpaceTrace.

In a project like mozilla, where millions of allocations are recorded by trace-malloc during a normal run of  the application, browsing such a large data set to find a culprit can be a fruitless task.  Some method must be utilized to narrow the data set to a human level.  Other trace-malloc genre tools exist to narrow the data.  A user of these tools can display the number of different types of objects allocated, list the allocations that were not freed, report where live allocations were created at a given point in time, et. al.   The one piece of information I was after was still missing however; allocation lifespan.

My answer to the prompting question:  "long lived allocations contribute to footprint bloat, short lived allocations are acceptable".  There need be no mention of size, number, or type of allocation, but just simply how long an allocation exists or lives.

SpaceTrace is a tool which reads a trace-malloc output log and allows the user to browse all allocations recorded by trace-malloc in an interactive manner by accepting http requests.  SpaceTrace intends to target allocations with longer lifespans contributing to footprint bloat.  This targeting is done by sorting all allocations using the concept of weight (described below).

Main Concepts

There are two concepts used throughout SpaceTrace which if explained beforehand will make the understanding come easier.

One concept is that of lifespan.  The lifespan of an allocation can be determined by subtracting the time of destruction from the time of creation.  Once the allocation's lifespan has been garnered more interesting decisions regarding the allocation can take place.  The composite lifespan from first creation to final destruction is known; that interval is assumed to be the total run time of the application.

Another concept is that of weight.  An allocation's weight is the product of the allocation's size and the allocation's lifespan (weight = size * lifespan).  While an allocation's weight is often a very large number, you should immediately gloss over the digits and look directly at the lifetime and size of the allocation.  The allocation's weight is meant to represent how much the allocation contributed to overall footprint bloat and  by default all lists are sorted by weight in SpaceTrace.

Configuring, Building, Running

Skip this section if you are only interested in using a dedicated server hosting SpaceTrace.  Information on were to find such a server is beyond the scope of this document.

The mozilla build system by default does not have trace-malloc enabled by default.  Perform the following platform specific instructions to get a trace-malloc build in order to use SpaceTrace.

WIN32

Follow normal win32 debug build instructions, with the following environment variable enabled:

set MOZ_TRACE_MALLOC=1

After your mozilla build completes, should you have http://www.boutell.com/gd installed, SpaceTrace is capable of producing some useful graphs.  This step is totally optional.  I had to jump through a few hoops to get the library compiled with the various other libraries it wants, with the correct LIBC (/MDd), and to use Mozilla's zlib_s.lib.  Other than those hangups, set the following environment variable to the directory where the build system can find gd.lib and the appropriate gd headers:

set HAVE_BOUTELL_GD=C:\gd-1.8.4

The tools to analyze trace-malloc output are not checked out or built by default.  From the parent directory of your existing mozilla source tree:

cvs checkout mozilla/tools/trace-malloc
cd mozilla\tools\trace-malloc
nmake /f makefile.win

From your dist bin directory (i.e. mozilla/dist/WIN32_D.OBJ/bin), you can use the following commands to execute mozilla to produce trace-malloc output, and once through running, to execute SpaceTrace to examine the data:

mozilla.exe --trace-malloc=C:\TEMP\TM.LOG
spacetrace.exe C:\TEMP\TM.LOG

Once SpaceTrace has loaded the data (could take a while depending on your machine), a message stating connections are being accepted on port 1969.  Simply point your everyday browser to http://localhost:1969/ to view the SpaceTrace reports interactively.

Linux

From the parent directory of your existing mozilla source tree:

cvs checkout mozilla/tools/trace-malloc

From the root of your mozilla source tree:

./configure --enable-cpp-rtti --enable-trace-malloc --disable-debug --enable-optimize="-O -g"

Should you have http://www.boutell.com/gd installed, SpaceTrace is capable of producing some useful graphs.  My redhat linux 7.1 workstation installation already had the required files (/usr/lib/libgd.a).  Set the following environment variable in whatever way you normally use:

export HAVE_BOUTELL_GD=1

From the root of your mozilla source tree:

make

Once the build completes, it is time to create the trace-mallloc output log.  From you mozilla/dist/bin directory, you will start mozilla with a special command line argument.  Be aware that the log file produced may range well into the hundreds of megabytes; be sure to use a partition with enough space.  Once mozilla starts, perform whatever tasks that will be of interest to you, and then normally close the application.  Perform the desired actions as quickly as possible as the trace-malloc output log tends to fill up even during an idle state.

./mozilla --trace-malloc=/tmp/tm.log

Next you should be ready to have SpaceTrace process the log.  Type the following commands from the mozilla/dist/bin directory.  The LD_LIBRARY_PATH is needed as SpaceTrace utilizes NSPR.

export LD_LIBRARY_PATH=.
./spacetrace /tmp/tm.log

Once the tool has finished loading the data, a message stating that SpaceTrace is accepting connections on port 1969 will be displayed.  Simply point your everyday browser to http://localhost:1969/ to view the SpaceTrace reports interactively.

Available Reports

Upon loading the SpaceTrace Index, you are presented with some very plain machine generated HTML.  All the pages you visit while interactively using SpaceTrace are generated on the fly and some may require many millions of iterations to produce the results you see; be patient if the host machine is slow.

A description of the reports you encounter and their intended meaning are listed below.  Note that the image graphs will not be present unless image support was turned on during the build process.

Root Callsites

A hunt-and-peck method of browsing through the allocation callsites.  Interesting for manual discovery purposes alone.

Should a user know a callstack they are interested in, they can browse to it and discover the allocation characteristics using this bottom-up method.

Top Callsites Report

A sorted list of the top allocation callsites.

Allocation callsites represent one or more allocations that occurred at the callsite.  These are the callsites which rank highest in SpaceTrace's ability to identify the source code behavior which contributes most to footprint bloat.

By clicking on a callsite you can see the entire backtrace as well as the top allocations which took place at the callsite.

Considered by me to be the most important report generated by SpaceTrace.

Top Allocations Report

A sorted list of the top individual allocations.

These are the allocations which rank highest in SpaceTrace's ability to identify footprint bloat.

By clicking on an allocation you can see the callsite backtrace which created the allocation as well as the life events which occurred to the allocation (malloc, free, et. al.).

Memory Leak Report

A sorted list of the allocations for which trace-malloc did not record a destruction or free event.

Produced by SpaceTrace simply because it can.

Footprint Graph

Reports how much memory was alive over the run of the application.

Very useful for visually explaining how much memory was used at different times during the run.

Allocation Lifespans Graph

Reports how much memory lived a particular lifespan.

This graph is a bit hard to understand at first glance.  The important thing to note is that the X axis is the lifespan of an allocation, not the total run interval of the application.

You may notice that the short lived allocations do not show up; by default SpaceTrace ignores allocations that do not at least have a lifespan of 10 seconds (configurable in the options should these be of interest to you).

This graph is most useful for obtaining information for tuning the options to target allocations which lived a particular amount of time.

Allocation Times Graph

Report how much memory was allocated at particular intervals during the run of of the application.

Very useful for obtaining information for tuning the options to target a time slice in which large amounts of memory were allocated.

Allocation Weights Graph

Nearly identical to the Allocation Times Graph, except that the Y axis is weight as opposed to size.

This graph is most useful for finding out at what time slice the heaviest footprint bloat allocations took place.

While a hard to digest graph, this is considered by me to be the most important graph generated by SpaceTrace.  The graph can be more useful after having narrowed the data set via the options.

Global Options

Multiple User Caution:  See Implementation Issues.

Listed below are the options available from the SpaceTrace command line.  All options are configurable interactively at runtime as well via the options form provided.  Note that the graph options are not available if SpaceTrace was not build with graph support.

-h

Provide command line help.

-c<text>

Restrict callsite backtraces to those only containing <text>.

All allocations that do not have callsite backtraces matching <text> will be excluded from the generated reports.

Very useful for targeting a genre of code or specific object creation functions.

-o<num>

Control the sort order of the lists printed in the reports.

-o0 is to sort by allocation weight.
-o1 is to sort by allocation size.
-o2 is to sort by allocation lifespan.

-a<num>

Set the allocation alignment boundary to <num>

By default, the allocation boundary is 16.

Allocations sizes are rounded up to the nearest boundary, simulating actual heap usage on the platform's heap implementation; Windows is known to have such a heap implementation.

Set this value to 1 in order to only see the actual sizes passed to the allocation routines, effectively turning off this feature.

-smin<num>

-smax<num>

Restrict the size of allocations being shown in generated reports to the minimum or maximum provided.

Very useful for excluding large or small allocations you consider noise.

-tmin<num>

-tmax<num>

Restrict the lifetime of allocations being shown in the generated reports to the minimum or maximum second provided.

By default allocations with a lifespan less than 10 seconds are ignored.  You can override that default using these options.

Useful for excluding short lived allocations or allocations which live the entire length of the applications (leaks).

-wmin<num>

-wmax<num>

Restrict the weight of allocations being shown in the generated reports to the minimum or maximum provided.

Useful for narrowing the data set by weight.

-imin<num>

-imax<num>

Do not consider allocations existing solely before or after the minimum or maximum second provided.

Useful for having SpaceTrace report on the live memory solely within the time slice.

-amin<num>

-amax<num>

Do not consider allocations that were not created before the minimum or after the maximum second.

Very useful for targeting allocations which occurred during a particular time slice.

-gmin<num>

-gmax<num>

Zoom in or out to particular X axis ranges on all reported graphs by second.

Great for getting more detail in a time slice, but a bit confusing when used with the Allocation Lifetimes graph.

-p<port>

Use <port> to listen for http requests.

-l<max>

Do not list more than <max> items in each list in the reports to avoid information overload.

-b<filepath>

Specifying this options causes SpaceTrace to execute in batch mode and not as an interactive httpd server.  Multiple -b options may be used on the command line.

In batch mode, SpaceTrace will load the trace-malloc data file, write the requested <filepath>(s) to disk, and then exit.  As an example, -bfootprint.png would save the footprint graph to disk and then exit SpaceTrace normally.

If you need to save everything and get tired of specifying batch mode options, you might want to consider using an automated fetch tool like wget on an interactive SpaceTrace server.

-d<dir>

Specify the directory that batch mode files will get saved.  Leave off the trailing slash.

Getting the Most Out of SpaceTrace

Feedback on SpaceTrace has been very positive. However I observed users of the tool encountering information overload, and they often end up asking themselves "what am I looking at?".  In defense, SpaceTrace and trace-malloc help answer the question of "where is the bloat?", every allocation and every detail is right there in front of the user, but the brutal reality is that millions of allocations and all the details presented to the user will eventually cause blurred vision.

In order to maximize your experience, you have to use the options to narrow the data set to something more relevant to you.  There are some dangers in doing this if in a multiple user scenario (see Implementation Issues).  Only through use and familiarity can you begin to mine relevant information.

The number one option to consider is -c<text>.  If you happen to know the creation routine or a central pathway to the code you are responsible for, by all means set the option to restrict only reporting that data to yourself.  Things will make a lot more sense and be a lot more relevant to you if you do.

Implementation Issues

The current incarnation of SpaceTrace is a C source file; this is acceptable so long as the abilities of the program keep up with the demands of the people using it.

One area of concern will be the plain HTML and large tables used to present the data.  Please, if you have the means, feel free to improve the presentation to your liking.  I am no expert in such details and was only interested in getting the data into the hands of the people that need it.

Futher, the lack of graphs on the platforms without GD will eventually be a hinderance, and some simple tables with colored cell backgrounds could represent the same data but in a rougher format.  If you have the means, again, please feel free to help out.

Perhaps the biggest issue, one other area of concern is the options effect the entire SpaceTrace process in a global sweeping manner.  As a disclaimer, the tool was originally written with only a single user in mind;  in my perfect little world each developer would run the tool at their leisure inspecting their own trace-malloc output files.  I soon discovered that with a large trace-malloc output file SpaceTrace will grow in memory usage significantly.  Alas, the number of machines capable of running SpaceTrace with adequate performance waned and ideas of hosting the data on dedicated machines obviously sprung to mind.  In a multiple user scenario, this dubious shared options feature will likely lead to some red herrings while the data set changes beneath the users' feet with no warning.  On the flip side, a user can then point random people to the server without any trouble and have them see what was intended.  I would be lying if I said correcting the behavior would be easy.  Giving each client their own view of the data set will be hard to implement in the C code because of some of the data stamping and caching code I wrote.  The issue can be corrected in time, but then I truly wonder about the performance aspects of such a tool where cache misses are common and each page view could cause many millions of iterations....  I need to mention the code is single threaded, though I think a multiple thread transition would be attainable by almost anyone.

For now, a usage pattern must emerge to minimize the effects of the implementation.  I suggest that the options URL with appropriate GET form data be copied and pasted into bug reports, emails, or other messages before the actual URL of interest.  In this manner, you can ensure that the recipient can load the desired options when they want to view the data.

Onward to an answer, I believe real power of SpaceTrace will be in allowing users of the tool to have their own custom queries performed on the data set.  The final solution seems obvious, but as there is a lack of time to go back and do things right I will document my simple thoughts here in the hopes one day someone will pick up the torch.

The trace-malloc output file combined with the SpaceTrace reader of that file should insert their datum into a database such as MySQL.  Some time will have to be spent architecting the various database tables involved, but the concepts should mostly follow what is there today in the C data structures.  A web front end written in a scripting language such as PHP could then be written for casual users of the data not unlike what is provided today in the C version. More formal users could write their own database queries using dedicated tools or by hand.  An entire barrage of automated reports could be written, a veritable dream when you need to track footprint and publish the results to a community like mozilla.

Non-Mozilla Usage

The only code in SpaceTrace that is possibly specific to mozilla, restricting SpaceTrace usage on other projects, is the format of trace-malloc output to be parsed.  Should you intend to use SpaceTrace on a project other than mozilla, you need to either output data in a compatible trace-malloc format (easier) or put a new parser into SpaceTrace (harder).