Adding Massif, the heap profiler.
git-svn-id: svn://svn.valgrind.org/valgrind/trunk@2245 a5019735-40e9-0310-863c-91ae7b9d1cf9
diff --git a/Makefile.am b/Makefile.am
index 0fb69e9..6e3798d 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -9,6 +9,7 @@
cachegrind \
corecheck \
helgrind \
+ massif \
lackey \
none
diff --git a/configure.in b/configure.in
index e23608f..00c9d53 100644
--- a/configure.in
+++ b/configure.in
@@ -373,12 +373,16 @@
cachegrind/tests/Makefile
cachegrind/docs/Makefile
cachegrind/cg_annotate
- corecheck/Makefile
- corecheck/tests/Makefile
- corecheck/docs/Makefile
helgrind/Makefile
helgrind/tests/Makefile
helgrind/docs/Makefile
+ massif/Makefile
+ massif/hp2ps/Makefile
+ massif/tests/Makefile
+ massif/docs/Makefile
+ corecheck/Makefile
+ corecheck/tests/Makefile
+ corecheck/docs/Makefile
lackey/Makefile
lackey/tests/Makefile
lackey/docs/Makefile
diff --git a/coregrind/vg_include.h b/coregrind/vg_include.h
index f699699..5e4d810 100644
--- a/coregrind/vg_include.h
+++ b/coregrind/vg_include.h
@@ -1365,9 +1365,6 @@
/* client executable file descriptor */
extern Int VG_(clexecfd);
-/* Path to all our library/aux files */
-extern const Char *VG_(libdir);
-
/* Determine if %esp adjustment must be noted */
extern Bool VG_(need_to_handle_esp_assignment) ( void );
diff --git a/docs/manual.html b/docs/manual.html
index 626fcd7..3530a99 100644
--- a/docs/manual.html
+++ b/docs/manual.html
@@ -98,12 +98,15 @@
<h4>6 <a href="hg_main.html#hg-top">
Helgrind: a data-race detector</a></h4>
+<h4>7 <a href="ms_main.html#ms-top">
+ Massif: a heap profiler</a></h4>
+
<p>
The following is not part of the user manual. It describes how you can
write tools for Valgrind, in order to make new program supervision
tools.
-<h4>7 <a href="coregrind_tools.html">
+<h4>8 <a href="coregrind_tools.html">
Valgrind Tools</a></h4>
<p>
@@ -111,10 +114,10 @@
details of how Valgrind works. Reading them may rot your brain. You
have been warned.
-<h4>8 <a href="mc_techdocs.html#mc-techdocs">
+<h4>9 <a href="mc_techdocs.html#mc-techdocs">
The design and implementation of Valgrind</a></h4>
-<h4>9 <a href="cg_techdocs.html#cg-techdocs">
+<h4>10 <a href="cg_techdocs.html#cg-techdocs">
How Cachegrind works</a></h4>
<hr width="100%">
diff --git a/include/vg_skin.h.base b/include/vg_skin.h.base
index c294a45..f456276 100644
--- a/include/vg_skin.h.base
+++ b/include/vg_skin.h.base
@@ -114,6 +114,10 @@
#include "vg_kerneliface.h"
+/* Path to all our library/aux files */
+extern const Char *VG_(libdir);
+
+
/*====================================================================*/
/*=== Core/skin interface version ===*/
/*====================================================================*/
diff --git a/massif/Makefile.am b/massif/Makefile.am
new file mode 100644
index 0000000..27ceaae
--- /dev/null
+++ b/massif/Makefile.am
@@ -0,0 +1,24 @@
+
+SUBDIRS = . tests docs hp2ps
+
+AM_CPPFLAGS = -I$(top_srcdir)/include -DVG_LIBDIR="\"$(libdir)"\"
+AM_CFLAGS = $(WERROR) -Winline -Wall -Wshadow -O -fomit-frame-pointer \
+ @PREFERRED_STACK_BOUNDARY@ -g
+
+valdir = $(libdir)/valgrind
+inplacedir = $(top_srcdir)/.in_place
+
+val_PROGRAMS = vgskin_massif.so vgpreload_massif.so
+
+vgskin_massif_so_SOURCES = ms_main.c
+vgskin_massif_so_LDFLAGS = -shared
+
+vgpreload_massif_so_SOURCES =
+vgpreload_massif_so_LDADD = $(top_srcdir)/coregrind/vg_replace_malloc.o
+vgpreload_massif_so_DEPENDENCIES = $(top_srcdir)/coregrind/vg_replace_malloc.o
+vgpreload_massif_so_LDFLAGS = -shared -Wl,-z,interpose,-z,initfirst
+
+all-local:
+ mkdir -p $(inplacedir)
+ -rm -f $(addprefix $(inplacedir)/,$(val_PROGRAMS))
+ ln -f -s $(addprefix $(top_srcdir)/$(subdir)/,$(val_PROGRAMS)) $(inplacedir)
diff --git a/massif/docs/Makefile.am b/massif/docs/Makefile.am
new file mode 100644
index 0000000..11bf87e
--- /dev/null
+++ b/massif/docs/Makefile.am
@@ -0,0 +1,5 @@
+docdir = $(datadir)/doc/valgrind
+
+doc_DATA = ms_main.html date.gif
+
+EXTRA_DIST = $(doc_DATA)
diff --git a/massif/docs/date.gif b/massif/docs/date.gif
new file mode 100644
index 0000000..eff527a
--- /dev/null
+++ b/massif/docs/date.gif
Binary files differ
diff --git a/massif/docs/ms_main.html b/massif/docs/ms_main.html
new file mode 100644
index 0000000..87d1abc
--- /dev/null
+++ b/massif/docs/ms_main.html
@@ -0,0 +1,331 @@
+<html>
+ <head>
+ <title>Massif: a heap profiler</title>
+ </head>
+
+<body>
+<a name="ms-top"></a>
+<h2>7 <b>Massif</b>: a heap profiler</h2>
+
+To use this tool, you must specify <code>--tool=massif</code>
+on the Valgrind command line.
+
+<a name="spaceprof"></a>
+<h3>7.1 Heap profiling</h3>
+Massif is a heap profiler, i.e. it measures how much heap memory programs use.
+In particular, it can give you information about:
+<ul>
+ <li>Heap blocks;
+ <li>Heap administration blocks;
+ <li>Stack sizes.
+</ul>
+
+Heap profiling is useful to help you reduce the amount of memory your program
+uses. On modern machines with virtual memory, this provides the following
+benefits:
+<ul>
+<li>It can speed up your program -- a smaller program will interact better
+ with your machine's caches, avoid paging, and so on.
+
+<li>If your program uses lots of memory, it will reduce the chance that it
+ exhausts your machine's swap space.
+</ul>
+
+Also, there are certain space leaks that aren't detected by traditional
+leak-checkers, such as Memcheck's. That's because the memory isn't ever
+actually lost -- a pointer remains to it -- but it's not in use. Programs
+that have leaks like this can unnecessarily increase the amount of memory
+they are using over time.
+<p>
+
+
+<a name="whyuse_heapprof"></a>
+<h3>7.2 Why Use a Heap Profiler?</h3>
+
+Everybody knows how useful time profilers are for speeding up programs. They
+are particularly useful because people are notoriously bad at predicting where
+are the bottlenecks in their programs.
+<p>
+But the story is different for heap profilers. Some programming languages,
+particularly lazy functional languages like <a
+href="http://www.haskell.org">Haskell</a>, have quite sophisticated heap
+profilers. But there are few tools as powerful for profiling C and C++
+programs.
+<p>
+Why is this? Maybe it's because C and C++ programmers must think that
+they know where the memory is being allocated. After all, you can see all the
+calls to <code>malloc()</code> and <code>new</code> and <code>new[]</code>,
+right? But, in a big program, do you really know which heap allocations are
+being executed, how many times, and how large each allocation is? Can you give
+even a vague estimate of the memory footprint for your program? Do you know
+this for all the libraries your program uses? What about administration bytes
+required by the heap allocator to track heap blocks -- have you thought about
+them? What about the stack? If you are unsure about any of these things,
+maybe you should think about heap profiling.
+<p>
+Massif can tell you these things.
+<p>
+Or maybe it's because it's relatively easy to add basic heap profiling
+functionality into a program, to tell you how many bytes you have allocated for
+certain objects, or similar. But this information might only be simple like
+total counts for the whole program's execution. What about space usage at
+different points in the program's execution, for example? And reimplementing
+heap profiling code for each project is a pain.
+<p>
+Massif can save you this effort.
+<p>
+
+
+<a name="overview"></a>
+<h3>7.3 Overview</h3>
+First off, as for normal Valgrind use, you probably want to compile with
+debugging info (the <code>-g</code> flag). But, as opposed to Memcheck,
+you probably <b>do</b> want to turn optimisation on, since you should profile
+your program as it will be normally run.
+<p>
+Then, run your program with <code>valgrind --tool=massif</code> in front of the
+normal command line invocation. When the program finishes, Massif will print
+summary space statistics. It also creates a graph representing the program's
+heap usage in a file called <code>massif.<i>pid</i>.ps</code>, which can
+be read by any PostScript viewer, such as Ghostview.
+<p>
+It also puts detailed information about heap consumption in a file file
+<code>massif.<i>pid</i>.txt</code> (text format) or
+<code>massif.<i>pid</i>.html</code> (HTML format), where
+<code><i>pid</i></code> is the program's process id.
+<p>
+
+
+<a name="basicresults"></a>
+<h3>7.4 Basic Results of Profiling</h3>
+
+To gather heap profiling information about the program <code>prog</code>,
+type:
+<p>
+<blockquote>
+<code>valgrind --tool=massif prog</code>
+</blockquote>
+<p>
+The program will execute (slowly). Upon completion, summary statistics
+that look like this will be printed:
+
+<pre>
+==27519== Total spacetime: 2,258,106 ms.B
+==27519== heap: 24.0%
+==27519== heap admin: 2.2%
+==27519== stack(s): 73.7%
+</pre>
+
+All measurements are done in <i>spacetime</i>, i.e. space (in bytes) multiplied
+by time (in milliseconds). Note that because Massif slows a program down a
+lot, the actual spacetime figure is fairly meaningless; it's the relative
+values that are interesting.
+<p>
+Which entries you see in the breakdown depends on the command line options
+given. The above example measures all the possible parts of memory:
+<ul>
+<li>Heap: number of words allocated on the heap, via <code>malloc()</code>,
+ <code>new</code> and <code>new[]</code>.
+ <p>
+<li>Heap admin: each heap block allocated requires some administration data,
+ which lets the allocator track certain things about the block. It is easy
+ to forget about this, and if your program allocates lots of small blocks,
+ it can add up. This value is an estimate of the space required for this
+ administration data.
+ <p>
+<li>Stack(s): the spacetime used by the programs' stack(s). (Threaded programs
+ can have multiple stacks.) This includes signal handler stacks.
+ <p>
+</ul>
+<p>
+
+
+<a name="graphs"></a>
+<h3>7.5 Spacetime Graphs</h3>
+As well as printing summary information, Massif also creates a file
+representing a spacetime graph, <code>massif.<i>pid</i>.hp</code>.
+It will produce a file called <code>massif.<i>pid</i>.ps</code>, which can be
+viewed in a PostScript viewer.
+<p>
+Massif uses a program called <code>hp2ps</code> to convert the raw data into
+the PostScript graph. It's distributed with Massif, but came originally
+from the <a href="http://haskell.cs.yale.edu/ghc/">Glasgow Haskell
+Compiler</a>. You shouldn't need to worry about this at all. However, if
+the graph creation fails for any reason, Massif tell you, and will leave
+behind a file named <code>massif.<i>pid</i>.hp</code>, containing the raw
+heap profiling data.
+<p>
+Here's an example graph:<br>
+ <img src="date.gif" alt="spacetime graph">
+<p>
+The graph is broken into several bands. Most bands represent a single line of
+your program that does some heap allocation; each such band represents all
+the allocations and deallocations done from that line. Up to twenty bands are
+shown; less significant allocation sites are merged into "other" and/or "OTHER"
+bands. The accompanying text/HTML file produced by Massif has more detail
+about these heap allocation bands. Then there are single bands for the
+stack(s) and heap admin bytes.
+<p>
+Note: it's the height of a band that's important. Don't let the ups and downs
+caused by other bands confuse you. For example, the
+<code>read_alias_file</code> band in the example has the same height all the
+time it's in existence.
+<p>
+The triangles on the x-axis show each point at which a memory census was taken.
+These aren't necessarily evenly spread; Massif only takes a census when
+memory is allocated or deallocated. The time on the x-axis is wallclock
+time, which is not ideal because you can get different graphs for different
+executions of the same program, due to random OS delays. But it's not too
+bad, and it becomes less of a problem the longer a program runs.
+<p>
+Massif takes censuses at an appropriate timescale; censuses take place less
+frequently as the program runs for longer. There is no point having more
+than 100-200 censuses on a single graph.
+<p>
+The graphs give a good overview of where your program's space use comes from,
+and how that varies over time. The accompanying text/HTML file gives a lot
+more information about heap use.
+
+<a name="detailsofheap"></a>
+<h3>7.6 Details of Heap Allocations</h3>
+
+The text/HTML file contains information to help interpret the heap bands of the
+graph. It also contains a lot of extra information about heap allocations that you don't see in the graph.
+<p>
+Here's part of the information that accompanies the above graph.
+
+<hr>
+== 0 ===========================<br>
+Heap allocation functions accounted for 50.8% of measured spacetime<br>
+<p>
+Called from:
+<ul>
+<li><a name="a401767D1"></a><a href="#b401767D1">22.1%</a>: 0x401767D0: _nl_intern_locale_data (in /lib/i686/libc-2.3.2.so)
+<li><a name="a4017C394"></a><a href="#b4017C394"> 8.6%</a>: 0x4017C393: read_alias_file (in /lib/i686/libc-2.3.2.so)
+
+<li><i>(several entries omitted)</i>
+
+<li>and 6 other insignificant places</li>
+</ul>
+<hr>
+The first part shows the total spacetime due to heap allocations, and the
+places in the program where most memory was allocated (nb: if this program had
+been compiled with <code>-g</code>, actual line numbers would be given). These
+places are sorted, from most significant to least, and correspond to the bands
+seen in the graph. Insignificant sites (accounting for less than 0.5% of total
+spacetime) are omitted.
+<p>
+That alone can be useful, but often isn't enough. What if one of these
+functions was called from several different places in the program? Which one
+of these is responsible for most of the memory used? For
+<code>_nl_intern_locale_data()</code>, this question is answered by clicking on
+the <a href="#b401767D1">22.1%</a> link, which takes us to the following part
+of the file.
+
+<hr>
+<p>== 1 ===========================<br>
+<a name="b401767D1"></a>Context accounted for <a href="#a401767D1">22.1%</a> of measured spacetime<br>
+ 0x401767D0: _nl_intern_locale_data (in /lib/i686/libc-2.3.2.so)<br>
+<p>
+Called from:
+<ul>
+<li><a name="a40176F96"></a><a href="#b40176F96">22.1%</a>: 0x40176F95: _nl_load_locale_from_archive (in /lib/i686/libc-2.3.2.so)
+</ul>
+<hr>
+
+At this level, we can see all the places from which
+<code>_nl_load_locale_from_archive()</code> was called such that it allocated
+memory at 0x401767D0. (We can click on the top <a href="#a40176F96">22.1%</a>
+link to go back to the parent entry.) At this level, we have moved beyond the
+information presented in the graph. In this case, it is only called from one
+place. We can again follow the link for more detail, moving to the following
+part of the file.
+
+<hr>
+<p>== 2 ===========================<br>
+<a name="b40176F96"></a>Context accounted for <a href="#a40176F96">22.1%</a> of measured spacetime<br>
+ 0x401767D0: _nl_intern_locale_data (in /lib/i686/libc-2.3.2.so)<br>
+ 0x40176F95: _nl_load_locale_from_archive (in /lib/i686/libc-2.3.2.so)<br>
+<p>
+Called from:
+<ul>
+<li><a name="a40176185"></a>22.1%: 0x40176184: _nl_find_locale (in /lib/i686/libc-2.3.2.so)
+</ul>
+<hr>
+
+In this way we can dig deeper into the call stack, to work out exactly what
+sequence of calls led to some memory being allocated. At this point, with a
+call depth of 3, the information runs out (thus the address of the child entry,
+0x40176184, isn't a link). We could rerun the program with a greater
+<code>--depth</code> value if we wanted more information.
+<p>
+Sometimes you will get a code location like this:
+<ul>
+<li>30.8% : 0xFFFFFFFF: ???
+</ul>
+The code address isn't really 0xFFFFFFFF -- that's impossible. This is what
+Massif does when it can't work out what the real code address is.
+<p>
+Massif produces this information in a plain text file by default, or HTML with
+the <code>--format=html</code> option. The plain text version obviously
+doesn't have the links, but a similar effect can be achieved by searching on
+the code addresses. (In Vim, the '*' and '#' searches are ideal for this.)
+
+
+<a name="massifoptions"></a>
+<h3>7.7 Massif options</h3>
+
+Massif-specific options are:
+
+<ul>
+<li><code>--heap=no</code><br>
+ <code>--heap=yes</code> [default]<br>
+ When enabled, profile heap usage in detail. Without it, the
+ <code>massif.<i>pid</i>.txt</code> or
+ <code>massif.<i>pid</i>.html</code> will be very short.
+ <p>
+<li><code>--heap-admin=<i>n</i></code> [default: 8]<br>
+ The number of admin bytes per block to use. This can only be an
+ estimate of the average, since it may vary. The allocator used by
+ <code>glibc</code> requires somewhere between 4--15 bytes per block,
+ depending on various factors. It also requires admin space for freed
+ blocks, although Massif does not count this.
+ <p>
+<li><code>--stacks=no</code><br>
+ <code>--stacks=yes</code> [default]<br>
+ When enabled, include stack(s) in the profile. Threaded programs can
+ have multiple stacks.
+ <p>
+<li><code>--depth=<i>n</i></code> [default: 3]<br>
+ Depth of call chains to present in the detailed heap information.
+ Increasing it will give more information, but Massif will run the program
+ more slowly, using more memory, and produce a bigger
+ <code>.txt</code>/<code>.hp</code> file.
+ <p>
+<li><code>--alloc-fn=<i>name</i></code><br>
+ Specify a function that allocates memory. This is useful for functions
+ that are wrappers to <code>malloc()</code>, which can fill up the context
+ information uselessly (and give very uninformative bands on the graph).
+ Functions specified will be ignored in contexts, i.e. treated as though
+ they were <code>malloc()</code>. This option can be specified multiple
+ times on the command line, to name multiple functions.
+ <p>
+<li><code>--format=text</code> [default]<br>
+ <code>--format=html</code><br>
+ Produce the detailed heap information in text or HTML format. The file
+ suffix used will be either <code>.txt</code> or <code>.html</code>.
+ <p>
+</ul>
+
+<a name="accuracy"></a>
+<h3>7.8 Accuracy</h3>
+The information should be pretty accurate. Some approximations made might
+cause some allocation contexts to be attributed with less memory than they
+actually allocated, but the amounts should be miniscule.
+<p>
+The heap admin spacetime figure is an approximation, as described above. If
+anyone knows how to improve its accuracy, please let us know.
+
+</body>
+</html>
+
diff --git a/massif/hp2ps/AreaBelow.c b/massif/hp2ps/AreaBelow.c
new file mode 100644
index 0000000..7413807
--- /dev/null
+++ b/massif/hp2ps/AreaBelow.c
@@ -0,0 +1,63 @@
+#include <stdio.h>
+#include "Main.h"
+#include "Defines.h"
+#include "Error.h"
+#include "HpFile.h"
+#include "Utilities.h"
+
+/* own stuff */
+#include "AreaBelow.h"
+
+extern void free();
+
+/*
+ * Return the area enclosed by all of the curves. The algorithm
+ * used is the same as the trapizoidal rule for integration.
+ */
+
+floatish
+AreaBelow()
+{
+ intish i;
+ intish j;
+ intish bucket;
+ floatish value;
+ struct chunk *ch;
+ floatish area;
+ floatish trap;
+ floatish base;
+ floatish *maxima;
+
+ maxima = (floatish *) xmalloc(nsamples * sizeof(floatish));
+ for (i = 0; i < nsamples; i++) {
+ maxima[i] = 0.0;
+ }
+
+ for (i = 0; i < nidents; i++) {
+ for (ch = identtable[i]->chk; ch; ch = ch->next) {
+ for (j = 0; j < ch->nd; j++) {
+ bucket = ch->d[j].bucket;
+ value = ch->d[j].value;
+ if (bucket >= nsamples)
+ Disaster("bucket out of range");
+ maxima[ bucket ] += value;
+ }
+ }
+ }
+
+ area = 0.0;
+
+ for (i = 1; i < nsamples; i++) {
+ base = samplemap[i] - samplemap[i-1];
+ if (maxima[i] > maxima[i-1]) {
+ trap = base * maxima[i-1] + ((base * (maxima[i] - maxima[i-1]))/ 2.0);
+ } else {
+ trap = base * maxima[i] + ((base * (maxima[i-1] - maxima[i]))/ 2.0);
+ }
+
+ area += trap;
+ }
+
+ free(maxima);
+ return area;
+}
diff --git a/massif/hp2ps/AreaBelow.h b/massif/hp2ps/AreaBelow.h
new file mode 100644
index 0000000..d7f713f
--- /dev/null
+++ b/massif/hp2ps/AreaBelow.h
@@ -0,0 +1,6 @@
+#ifndef AREA_BELOW_H
+#define AREA_BELOW_H
+
+floatish AreaBelow PROTO((void));
+
+#endif /* AREA_BELOW_H */
diff --git a/massif/hp2ps/AuxFile.c b/massif/hp2ps/AuxFile.c
new file mode 100644
index 0000000..bbdc4aa
--- /dev/null
+++ b/massif/hp2ps/AuxFile.c
@@ -0,0 +1,168 @@
+#include <ctype.h>
+#include <stdio.h>
+#include <string.h>
+#include "Main.h"
+#include "Defines.h"
+#include "Shade.h"
+#include "Error.h"
+#include "HpFile.h"
+#include "Reorder.h"
+
+/* own stuff */
+#include "AuxFile.h"
+
+static void GetAuxLine PROTO((FILE *)); /* forward */
+static void GetAuxTok PROTO((FILE *)); /* forward */
+
+void
+GetAuxFile(auxfp)
+ FILE* auxfp;
+{
+ g_ch = ' ';
+ endfile = 0;
+ linenum = 1;
+
+ GetAuxTok(auxfp);
+
+ while (endfile == 0) {
+ GetAuxLine(auxfp);
+ }
+
+ fclose(auxfp);
+}
+
+
+
+/*
+ * Read the next line from the aux file, check the syntax, and
+ * perform the appropriate action.
+ */
+
+static void
+GetAuxLine(auxfp)
+ FILE* auxfp;
+{
+ switch (thetok) {
+ case X_RANGE_TOK:
+ GetAuxTok(auxfp);
+ if (thetok != FLOAT_TOK) {
+ Error("%s, line %d, floating point number must follow X_RANGE",
+ auxfile, linenum);
+ }
+ auxxrange = thefloatish;
+ GetAuxTok(auxfp);
+ break;
+ case Y_RANGE_TOK:
+ GetAuxTok(auxfp);
+ if (thetok != FLOAT_TOK) {
+ Error("%s, line %d, floating point number must follow Y_RANGE",
+ auxfile, linenum);
+ }
+ auxyrange = thefloatish;
+ GetAuxTok(auxfp);
+ break;
+ case ORDER_TOK:
+ GetAuxTok(auxfp);
+ if (thetok != IDENTIFIER_TOK) {
+ Error("%s, line %d: identifier must follow ORDER",
+ auxfile, linenum);
+ }
+ GetAuxTok(auxfp);
+ if (thetok != INTEGER_TOK) {
+ Error("%s, line %d: identifier and integer must follow ORDER",
+ auxfile, linenum);
+ }
+ OrderFor(theident, theinteger);
+ GetAuxTok(auxfp);
+ break;
+ case SHADE_TOK:
+ GetAuxTok(auxfp);
+ if (thetok != IDENTIFIER_TOK) {
+ Error("%s, line %d: identifier must follow SHADE",
+ auxfile, linenum);
+ }
+ GetAuxTok(auxfp);
+ if (thetok != FLOAT_TOK) {
+ Error("%s, line %d: identifier and floating point number must follow SHADE",
+ auxfile, linenum);
+ }
+ ShadeFor(theident, thefloatish);
+ GetAuxTok(auxfp);
+ break;
+ case EOF_TOK:
+ endfile = 1;
+ break;
+ default:
+ Error("%s, line %d: %s unexpected", auxfile, linenum,
+ TokenToString(thetok));
+ break;
+ }
+}
+
+
+
+/*
+ * Read the next token from the input and assign its value
+ * to the global variable "thetok". In the case of numbers,
+ * the corresponding value is also assigned to "thefloatish";
+ * in the case of identifiers it is assigned to "theident".
+ */
+
+static void GetAuxTok(auxfp)
+FILE* auxfp;
+{
+
+ while (isspace(g_ch)) { /* skip whitespace */
+ if (g_ch == '\n') linenum++;
+ g_ch = getc(auxfp);
+ }
+
+ if (g_ch == EOF) {
+ thetok = EOF_TOK;
+ return;
+ }
+
+ if (isdigit(g_ch)) {
+ thetok = GetNumber(auxfp);
+ return;
+ } else if (IsIdChar(g_ch)) { /* g_ch can't be a digit here */
+ GetIdent(auxfp);
+ if (!isupper(theident[0])) {
+ thetok = IDENTIFIER_TOK;
+ } else if (strcmp(theident, "X_RANGE") == 0) {
+ thetok = X_RANGE_TOK;
+ } else if (strcmp(theident, "Y_RANGE") == 0) {
+ thetok = Y_RANGE_TOK;
+ } else if (strcmp(theident, "ORDER") == 0) {
+ thetok = ORDER_TOK;
+ } else if (strcmp(theident, "SHADE") == 0) {
+ thetok = SHADE_TOK;
+ } else {
+ thetok = IDENTIFIER_TOK;
+ }
+ return;
+ } else {
+ Error("%s, line %d: strange character (%c)", auxfile, linenum, g_ch);
+ }
+}
+
+void
+PutAuxFile(auxfp)
+ FILE* auxfp;
+{
+ int i;
+
+ fprintf(auxfp, "X_RANGE %.2f\n", xrange);
+ fprintf(auxfp, "Y_RANGE %.2f\n", yrange);
+
+ for (i = 0; i < nidents; i++) {
+ fprintf(auxfp, "ORDER %s %d\n", identtable[i]->name, i+1);
+ }
+
+ for (i = 0; i < nidents; i++) {
+ fprintf(auxfp, "SHADE %s %.2f\n", identtable[i]->name,
+ ShadeOf(identtable[i]->name));
+ }
+
+ fclose(auxfp);
+}
diff --git a/massif/hp2ps/AuxFile.h b/massif/hp2ps/AuxFile.h
new file mode 100644
index 0000000..6e962c4
--- /dev/null
+++ b/massif/hp2ps/AuxFile.h
@@ -0,0 +1,7 @@
+#ifndef AUX_FILE_H
+#define AUX_FILE_H
+
+void PutAuxFile PROTO((FILE *));
+void GetAuxFile PROTO((FILE *));
+
+#endif /* AUX_FILE_H */
diff --git a/massif/hp2ps/Axes.c b/massif/hp2ps/Axes.c
new file mode 100644
index 0000000..0733edd
--- /dev/null
+++ b/massif/hp2ps/Axes.c
@@ -0,0 +1,241 @@
+#include <stdio.h>
+#include <string.h>
+#include "Main.h"
+#include "Curves.h"
+#include "Defines.h"
+#include "Dimensions.h"
+#include "HpFile.h"
+#include "Utilities.h"
+
+/* own stuff */
+#include "Axes.h"
+
+typedef enum {MEGABYTE, KILOBYTE, BYTE} mkb;
+
+static void XAxis PROTO((void)); /* forward */
+static void YAxis PROTO((void)); /* forward */
+
+static void XAxisMark PROTO((floatish, floatish)); /* forward */
+static void YAxisMark PROTO((floatish, floatish, mkb)); /* forward */
+
+static floatish Round PROTO((floatish)); /* forward */
+
+void
+Axes()
+{
+ XAxis();
+ YAxis();
+}
+
+static void
+XAxisMark(x, num)
+ floatish x; floatish num;
+{
+ /* calibration mark */
+ fprintf(psfp, "%f %f moveto\n", xpage(x), ypage(0.0));
+ fprintf(psfp, "0 -4 rlineto\n");
+ fprintf(psfp, "stroke\n");
+
+ /* number */
+ fprintf(psfp, "HE%d setfont\n", NORMAL_FONT);
+ fprintf(psfp, "(%.1f)\n", num);
+ fprintf(psfp, "dup stringwidth pop\n");
+ fprintf(psfp, "2 div\n");
+ fprintf(psfp, "%f exch sub\n", xpage(x));
+ fprintf(psfp, "%f moveto\n", borderspace);
+ fprintf(psfp, "show\n");
+}
+
+
+#define N_X_MARKS 7
+#define XFUDGE 15
+
+extern floatish xrange;
+extern char *sampleunitstring;
+
+static void
+XAxis()
+{
+ floatish increment, i;
+ floatish t, x;
+ floatish legendlen;
+
+ /* draw the x axis line */
+ fprintf(psfp, "%f %f moveto\n", xpage(0.0), ypage(0.0));
+ fprintf(psfp, "%f 0 rlineto\n", graphwidth);
+ fprintf(psfp, "%f setlinewidth\n", borderthick);
+ fprintf(psfp, "stroke\n");
+
+ /* draw x axis legend */
+ fprintf(psfp, "HE%d setfont\n", NORMAL_FONT);
+ fprintf(psfp, "(%s)\n", sampleunitstring);
+ fprintf(psfp, "dup stringwidth pop\n");
+ fprintf(psfp, "%f\n", xpage(0.0) + graphwidth);
+ fprintf(psfp, "exch sub\n");
+ fprintf(psfp, "%f moveto\n", borderspace);
+ fprintf(psfp, "show\n");
+
+
+ /* draw x axis scaling */
+
+ increment = Round(xrange / (floatish) N_X_MARKS);
+
+ t = graphwidth / xrange;
+ legendlen = StringSize(sampleunitstring) + (floatish) XFUDGE;
+
+ for (i = samplemap[0]; i < samplemap[nsamples - 1]; i += increment) {
+ x = (i - samplemap[0]) * t;
+
+ if (x < (graphwidth - legendlen)) {
+ XAxisMark(x,i);
+ }
+ }
+}
+
+static void
+YAxisMark(y, num, unit)
+ floatish y; floatish num; mkb unit;
+{
+ /* calibration mark */
+ fprintf(psfp, "%f %f moveto\n", xpage(0.0), ypage(y));
+ fprintf(psfp, "-4 0 rlineto\n");
+ fprintf(psfp, "stroke\n");
+
+ /* number */
+ fprintf(psfp, "HE%d setfont\n", NORMAL_FONT);
+
+ switch (unit) {
+ case MEGABYTE :
+ fprintf(psfp, "(");
+ CommaPrint(psfp, (intish) (num / 1e6 + 0.5));
+ fprintf(psfp, "M)\n");
+ break;
+ case KILOBYTE :
+ fprintf(psfp, "(");
+ CommaPrint(psfp, (intish) (num / 1e3 + 0.5));
+ fprintf(psfp, "k)\n");
+ break;
+ case BYTE:
+ fprintf(psfp, "(");
+ CommaPrint(psfp, (intish) (num + 0.5));
+ fprintf(psfp, ")\n");
+ break;
+ }
+
+ fprintf(psfp, "dup stringwidth\n");
+ fprintf(psfp, "2 div\n");
+ fprintf(psfp, "%f exch sub\n", ypage(y));
+
+ fprintf(psfp, "exch\n");
+ fprintf(psfp, "%f exch sub\n", graphx0 - borderspace);
+
+ fprintf(psfp, "exch\n");
+ fprintf(psfp, "moveto\n");
+ fprintf(psfp, "show\n");
+}
+
+#define N_Y_MARKS 7
+#define YFUDGE 15
+
+extern floatish yrange;
+extern char *valueunitstring;
+
+static void
+YAxis()
+{
+ floatish increment, i;
+ floatish t, y;
+ floatish legendlen;
+ mkb unit;
+
+ /* draw the y axis line */
+ fprintf(psfp, "%f %f moveto\n", xpage(0.0), ypage(0.0));
+ fprintf(psfp, "0 %f rlineto\n", graphheight);
+ fprintf(psfp, "%f setlinewidth\n", borderthick);
+ fprintf(psfp, "stroke\n");
+
+ /* draw y axis legend */
+ fprintf(psfp, "gsave\n");
+ fprintf(psfp, "HE%d setfont\n", NORMAL_FONT);
+ fprintf(psfp, "(%s)\n", valueunitstring);
+ fprintf(psfp, "dup stringwidth pop\n");
+ fprintf(psfp, "%f\n", ypage(0.0) + graphheight);
+ fprintf(psfp, "exch sub\n");
+ fprintf(psfp, "%f exch\n", xpage(0.0) - borderspace);
+ fprintf(psfp, "translate\n");
+ fprintf(psfp, "90 rotate\n");
+ fprintf(psfp, "0 0 moveto\n");
+ fprintf(psfp, "show\n");
+ fprintf(psfp, "grestore\n");
+
+ /* draw y axis scaling */
+ increment = max( yrange / (floatish) N_Y_MARKS, 1.0);
+ increment = Round(increment);
+
+ if (increment >= 1e6) {
+ unit = MEGABYTE;
+ } else if (increment >= 1e3) {
+ unit = KILOBYTE;
+ } else {
+ unit = BYTE;
+ }
+
+ t = graphheight / yrange;
+ legendlen = StringSize(valueunitstring) + (floatish) YFUDGE;
+
+ for (i = 0.0; i <= yrange; i += increment) {
+ y = i * t;
+
+ if (y < (graphheight - legendlen)) {
+ YAxisMark(y, i, unit);
+ }
+ }
+}
+
+
+/*
+ * Find a "nice round" value to use on the axis.
+ */
+
+static floatish OneTwoFive PROTO((floatish)); /* forward */
+
+static floatish
+Round(y)
+ floatish y;
+{
+ int i;
+
+ if (y > 10.0) {
+ for (i = 0; y > 10.0; y /= 10.0, i++) ;
+ y = OneTwoFive(y);
+ for ( ; i > 0; y = y * 10.0, i--) ;
+
+ } else if (y < 1.0) {
+ for (i = 0; y < 1.0; y *= 10.0, i++) ;
+ y = OneTwoFive(y);
+ for ( ; i > 0; y = y / 10.0, i--) ;
+
+ } else {
+ y = OneTwoFive(y);
+ }
+
+ return (y);
+}
+
+
+/*
+ * OneTwoFive() -- Runciman's 1,2,5 scaling rule. Argument 1.0 <= y <= 10.0.
+ */
+
+static floatish
+OneTwoFive(y)
+ floatish y;
+{
+ if (y > 4.0) {
+ return (5.0);
+ } else if (y > 1.0) {
+ return (2.0);
+ } else {
+ return (1.0);
+ }
+}
diff --git a/massif/hp2ps/Axes.h b/massif/hp2ps/Axes.h
new file mode 100644
index 0000000..e4be505
--- /dev/null
+++ b/massif/hp2ps/Axes.h
@@ -0,0 +1,6 @@
+#ifndef AXES_H
+#define AXES_H
+
+void Axes PROTO((void));
+
+#endif /* AXES_H */
diff --git a/massif/hp2ps/CHANGES b/massif/hp2ps/CHANGES
new file mode 100644
index 0000000..60933d6
--- /dev/null
+++ b/massif/hp2ps/CHANGES
@@ -0,0 +1,39 @@
+1.
+
+When generating PostScript to show strings, '(' and ')' may need to be escaped.
+These characters are now escaped when the JOB string is shown.
+
+2.
+
+Manually deleting samples from a .hp file now does what you would expect.
+
+3.
+
+The -t flag for setting the threshold percentage has been scrapped. No one
+ever used it.
+
+4.
+
+Long JOB strings cause hp2ps to use a big title box. Big and small boxes
+can be forced with -b and -s flag.
+
+5.
+
+MARKS now print as small triangles which remain below the x axis.
+
+6.
+
+There is an updated manual page.
+
+7.
+
+-m flag for setting maximum no of bands (default 20, cant be more than 20).
+-t flag for setting threshold (between 0% and 5%, default 1%).
+
+8.
+
+Axes scaling rounding errors removed.
+
+9.
+
+Fixed bug whereby x-axis was assumed to start at zero when placing MARKs.
diff --git a/massif/hp2ps/Curves.c b/massif/hp2ps/Curves.c
new file mode 100644
index 0000000..68dc417
--- /dev/null
+++ b/massif/hp2ps/Curves.c
@@ -0,0 +1,164 @@
+#include <stdio.h>
+#include <math.h>
+#include "Main.h"
+#include "Defines.h"
+#include "Dimensions.h"
+#include "HpFile.h"
+#include "Shade.h"
+#include "Utilities.h"
+
+/* own stuff */
+#include "Curves.h"
+
+static floatish *g_x; /* x and y values */
+static floatish *g_y;
+
+static floatish *g_py; /* previous y values */
+
+static void Curve PROTO((struct entry *)); /* forward */
+static void ShadeCurve(); /* forward */
+
+void
+Curves()
+{
+ intish i;
+
+ for (i = 0; i < nidents; i++) {
+ Curve(identtable[i]);
+ }
+}
+
+/*
+ * Draw a curve, and fill the area that is below it and above
+ * the previous curve.
+ */
+
+static void
+Curve(e)
+ struct entry* e;
+{
+ struct chunk* ch;
+ int j;
+
+ for (ch = e->chk; ch; ch = ch->next) {
+ for (j = 0; j < ch->nd; j++) {
+ g_y[ ch->d[j].bucket ] += ch->d[j].value;
+ }
+ }
+
+ ShadeCurve(g_x, g_y, g_py, ShadeOf(e->name));
+}
+
+
+static void PlotCurveLeftToRight PROTO((floatish *, floatish *)); /* forward */
+static void PlotCurveRightToLeft PROTO((floatish *, floatish *)); /* forward */
+
+static void SaveCurve PROTO((floatish *, floatish *)); /* forward */
+
+/*
+ * Map virtual x coord to physical x coord
+ */
+
+floatish
+xpage(x)
+ floatish x;
+{
+ return (x + graphx0);
+}
+
+
+
+/*
+ * Map virtual y coord to physical y coord
+ */
+
+floatish
+ypage(y)
+ floatish y;
+{
+ return (y + graphy0);
+}
+
+
+/*
+ * Fill the region bounded by two splines, using the given
+ * shade.
+ */
+
+static void
+ShadeCurve(x, y, py, shade)
+ floatish *x; floatish *y; floatish *py; floatish shade;
+{
+ fprintf(psfp, "%f %f moveto\n", xpage(x[0]), ypage(py[0]));
+ PlotCurveLeftToRight(x, py);
+
+ fprintf(psfp, "%f %f lineto\n", xpage(x[nsamples - 1]),
+ ypage(y[nsamples - 1]));
+ PlotCurveRightToLeft(x, y);
+
+ fprintf(psfp, "closepath\n");
+
+ fprintf(psfp, "gsave\n");
+
+ SetPSColour(shade);
+ fprintf(psfp, "fill\n");
+
+ fprintf(psfp, "grestore\n");
+ fprintf(psfp, "stroke\n");
+
+ SaveCurve(y, py);
+}
+
+static void
+PlotCurveLeftToRight(x,y)
+ floatish *x; floatish *y;
+{
+ intish i;
+
+ for (i = 0; i < nsamples; i++) {
+ fprintf(psfp, "%f %f lineto\n", xpage(x[i]), ypage(y[i]));
+ }
+}
+
+static void
+PlotCurveRightToLeft(x,y)
+ floatish *x; floatish *y;
+{
+ intish i;
+
+ for (i = nsamples - 1; i >= 0; i-- ) {
+ fprintf(psfp, "%f %f lineto\n", xpage(x[i]), ypage(y[i]));
+ }
+}
+
+/*
+ * Save the curve coordinates stored in y[] in py[].
+ */
+
+static void
+SaveCurve(y, py)
+ floatish *y; floatish* py;
+{
+ intish i;
+
+ for (i = 0; i < nsamples; i++) {
+ py[i] = y[i];
+ }
+}
+
+extern floatish xrange;
+
+void
+CurvesInit()
+{
+ intish i;
+
+ g_x = (floatish*) xmalloc(nsamples * sizeof(floatish));
+ g_y = (floatish*) xmalloc(nsamples * sizeof(floatish));
+ g_py = (floatish*) xmalloc(nsamples * sizeof(floatish));
+
+ for (i = 0; i < nsamples; i++) {
+ g_x[i] = ((samplemap[i] - samplemap[0])/ xrange) * graphwidth;
+ g_y[i] = g_py[i] = 0.0;
+ }
+}
diff --git a/massif/hp2ps/Curves.h b/massif/hp2ps/Curves.h
new file mode 100644
index 0000000..0aa397f
--- /dev/null
+++ b/massif/hp2ps/Curves.h
@@ -0,0 +1,10 @@
+#ifndef CURVES_H
+#define CURVES_H
+
+void Curves PROTO((void));
+void CurvesInit PROTO((void));
+
+floatish xpage PROTO((floatish));
+floatish ypage PROTO((floatish));
+
+#endif /* CURVES_H */
diff --git a/massif/hp2ps/Defines.h b/massif/hp2ps/Defines.h
new file mode 100644
index 0000000..8d38546
--- /dev/null
+++ b/massif/hp2ps/Defines.h
@@ -0,0 +1,61 @@
+#ifndef DEFINES_H
+#define DEFINES_H
+
+/*
+ * Things that can be altered.
+ */
+
+#define THRESHOLD_PERCENT _thresh_ /* all values below 1% insignificant */
+#define DEFAULT_THRESHOLD 1.0
+extern floatish _thresh_;
+
+#define TWENTY _twenty_ /* show top 20 bands, grouping excess */
+#define DEFAULT_TWENTY 20 /* this is default and absolute maximum */
+extern int _twenty_;
+
+#define LARGE_FONT 12 /* Helvetica 12pt */
+#define NORMAL_FONT 10 /* Helvetica 10pt */
+
+#define BORDER_HEIGHT 432.0 /* page border box 432pt (6 inches high) */
+#define BORDER_WIDTH 648.0 /* page border box 648pt (9 inches wide) */
+#define BORDER_SPACE 5.0 /* page border space */
+#define BORDER_THICK 0.5 /* page border line thickness 0.5pt */
+
+
+#define TITLE_HEIGHT 20.0 /* title box is 20pt high */
+#define TITLE_TEXT_FONT LARGE_FONT /* title in large font */
+#define TITLE_TEXT_SPACE 6.0 /* space between title text and box */
+
+
+#define AXIS_THICK 0.5 /* axis thickness 0.5pt */
+#define AXIS_TEXT_SPACE 6 /* space between axis legends and axis */
+#define AXIS_TEXT_FONT NORMAL_FONT /* axis legends in normal font */
+#define AXIS_Y_TEXT_SPACE 35 /* space for y axis text */
+
+#define KEY_BOX_WIDTH 14 /* key boxes are 14pt high */
+
+#define SMALL_JOB_STRING_WIDTH 35 /* small title for 35 characters or less */
+#define BIG_JOB_STRING_WIDTH 80 /* big title for everything else */
+
+#define GRAPH_X0 (AXIS_Y_TEXT_SPACE + (2 * BORDER_SPACE))
+#define GRAPH_Y0 (AXIS_TEXT_FONT + (2 * BORDER_SPACE))
+
+
+/*
+ * Things that should be left well alone.
+ */
+
+
+
+#define START_X 72 /* start 72pt (1 inch) from left (portrait) */
+#define START_Y 108 /* start 108pt (1.5 inch) from bottom (portrait) */
+
+#define NUMBER_LENGTH 32
+
+#define N_CHUNK 24
+
+#define VERSION "0.25" /* as of 95/03/21 */
+
+#define max(x,y) ((x) > (y) ? (x) : (y)) /* not everyone has this */
+
+#endif /* DEFINES_H */
diff --git a/massif/hp2ps/Deviation.c b/massif/hp2ps/Deviation.c
new file mode 100644
index 0000000..49e8d21
--- /dev/null
+++ b/massif/hp2ps/Deviation.c
@@ -0,0 +1,140 @@
+#include <stdio.h>
+#include <string.h>
+#include <math.h>
+#include "Main.h"
+#include "Defines.h"
+#include "Error.h"
+#include "HpFile.h"
+#include "Utilities.h"
+
+extern void free();
+
+/* own stuff */
+#include "Deviation.h"
+
+/*
+ * Reorder the identifiers in the identifier table so that the
+ * ones whose data points exhibit the mininal standard deviation
+ * come first.
+ */
+
+void
+Deviation()
+{
+ intish i;
+ intish j;
+ floatish dev;
+ struct chunk* ch;
+ int min;
+ floatish t;
+ struct entry* e;
+ floatish *averages;
+ floatish *deviations;
+
+ averages = (floatish*) xmalloc(nidents * sizeof(floatish));
+ deviations = (floatish*) xmalloc(nidents * sizeof(floatish));
+
+ /* find averages */
+
+ for (i = 0; i < nidents; i++) {
+ averages[i] = 0.0;
+ }
+
+ for (i = 0; i < nidents; i++) {
+ for (ch = identtable[i]->chk; ch; ch = ch->next) {
+ for (j = 0; j < ch->nd; j++) {
+ averages[i] += ch->d[j].value;
+ }
+ }
+ }
+
+ for (i = 0; i < nidents; i++) {
+ averages[i] /= (floatish) nsamples;
+ }
+
+ /* calculate standard deviation */
+
+ for (i = 0; i < nidents; i++) {
+ deviations[i] = 0.0;
+ }
+
+ for (i = 0; i < nidents; i++) {
+ for (ch = identtable[i]->chk; ch; ch = ch->next) {
+ for (j = 0; j < ch->nd; j++) {
+ dev = ch->d[j].value - averages[i];
+ deviations[i] += dev * dev;
+ }
+ }
+ }
+
+ for (i = 0; i < nidents; i++) {
+ deviations[i] = (floatish) sqrt ((doublish) (deviations[i] /
+ (floatish) (nsamples - 1)));
+ }
+
+
+ /* sort on basis of standard deviation */
+
+ for (i = 0; i < nidents-1; i++) {
+ min = i;
+ for (j = i+1; j < nidents; j++) {
+ if (deviations[ j ] < deviations[min]) {
+ min = j;
+ }
+ }
+
+ t = deviations[min];
+ deviations[min] = deviations[i];
+ deviations[i] = t;
+
+ e = identtable[min];
+ identtable[min] = identtable[i];
+ identtable[i] = e;
+ }
+
+ free(averages);
+ free(deviations);
+}
+
+void
+Identorder(iflag)
+ int iflag; /* a funny three-way flag ? WDP 95/03 */
+{
+ int i;
+ int j;
+ int min;
+ struct entry* e;
+
+ /* sort on basis of ident string */
+ if (iflag > 0) {
+ /* greatest at top i.e. smallest at start */
+
+ for (i = 0; i < nidents-1; i++) {
+ min = i;
+ for (j = i+1; j < nidents; j++) {
+ if (strcmp(identtable[j]->name, identtable[min]->name) < 0) {
+ min = j;
+ }
+ }
+
+ e = identtable[min];
+ identtable[min] = identtable[i];
+ identtable[i] = e;
+ }
+ } else {
+ /* smallest at top i.e. greatest at start */
+
+ for (i = 0; i < nidents-1; i++) {
+ min = i;
+ for (j = i+1; j < nidents; j++) {
+ if (strcmp(identtable[j]->name, identtable[min]->name) > 0) {
+ min = j;
+ }
+ }
+
+ e = identtable[min];
+ identtable[min] = identtable[i];
+ identtable[i] = e;
+ }
+ }
+}
diff --git a/massif/hp2ps/Deviation.h b/massif/hp2ps/Deviation.h
new file mode 100644
index 0000000..14e4df1
--- /dev/null
+++ b/massif/hp2ps/Deviation.h
@@ -0,0 +1,7 @@
+#ifndef DEVIATION_H
+#define DEVIATION_H
+
+void Deviation PROTO((void));
+void Identorder PROTO((int));
+
+#endif /* DEVIATION_H */
diff --git a/massif/hp2ps/Dimensions.c b/massif/hp2ps/Dimensions.c
new file mode 100644
index 0000000..b0d1bd5
--- /dev/null
+++ b/massif/hp2ps/Dimensions.c
@@ -0,0 +1,203 @@
+#include <ctype.h>
+#include <string.h>
+#include <stdio.h>
+#include "Main.h"
+#include "Defines.h"
+#include "HpFile.h"
+#include "Scale.h"
+
+/* own stuff */
+#include "Dimensions.h"
+
+/*
+ * Get page and other dimensions before printing.
+ */
+
+floatish borderheight = BORDER_HEIGHT;
+floatish borderwidth = BORDER_WIDTH;
+floatish borderspace = BORDER_SPACE;
+floatish borderthick = BORDER_THICK;
+
+floatish titlewidth = (BORDER_WIDTH - (2 * BORDER_SPACE));
+floatish titletextspace = TITLE_TEXT_SPACE;
+floatish titleheight;
+
+floatish graphx0 = GRAPH_X0;
+floatish graphy0 = GRAPH_Y0;
+
+floatish graphheight;
+floatish graphwidth;
+
+static floatish KeyWidth PROTO((void)); /* forward */
+
+void
+Dimensions()
+{
+ xrange = samplemap[nsamples - 1] - samplemap[0];
+ xrange = max(xrange, auxxrange);
+ if (xrange == 0.0) xrange = 1.0; /* avoid division by 0.0 */
+
+ yrange = MaxCombinedHeight();
+ yrange = max(yrange, auxyrange);
+ if (yrange == 0.0) yrange = 1.0; /* avoid division by 0.0 */
+
+ if (!bflag && !sflag) {
+ bflag = strlen(jobstring) > SMALL_JOB_STRING_WIDTH;
+ }
+
+ if (bflag) {
+ titleheight = 2 * TITLE_HEIGHT;
+ } else {
+ titleheight = TITLE_HEIGHT;
+ }
+
+ graphwidth = titlewidth - graphx0 - (TWENTY ? KeyWidth() : 0);
+ graphheight = borderheight - titleheight - (2 * borderspace) - graphy0;
+}
+
+/*
+ * Calculate the width of the key.
+ */
+
+static floatish
+KeyWidth()
+{
+ intish i;
+ floatish c;
+
+ c = 0.0;
+
+ for (i = 0; i < nidents; i++) {
+ c = max(c, StringSize(identtable[i]->name));
+ }
+
+ c += 3.0 * borderspace;
+
+ c += (floatish) KEY_BOX_WIDTH;
+
+ return c;
+}
+
+
+/*
+ * A desperately grim solution.
+ */
+
+
+floatish fonttab[] = {
+ /* 20 (' ') = */ 3.0,
+ /* 21 ('!') = */ 1.0,
+ /* 22 ('"') = */ 1.0,
+ /* 23 ('#') = */ 3.0,
+ /* 24 ('$') = */ 3.0,
+ /* 25 ('%') = */ 3.0,
+ /* 26 ('&') = */ 3.0,
+ /* 27 (''') = */ 1.0,
+ /* 28 ('(') = */ 3.0,
+ /* 29 (')') = */ 3.0,
+ /* 2a ('*') = */ 2.0,
+ /* 2b ('+') = */ 3.0,
+ /* 2c (',') = */ 1.0,
+ /* 2d ('-') = */ 3.0,
+ /* 2e ('.') = */ 1.0,
+ /* 2f ('/') = */ 3.0,
+ /* 30 ('0') = */ 4.0,
+ /* 31 ('1') = */ 4.0,
+ /* 32 ('2') = */ 4.0,
+ /* 33 ('3') = */ 4.0,
+ /* 34 ('4') = */ 4.0,
+ /* 35 ('5') = */ 4.0,
+ /* 36 ('6') = */ 4.0,
+ /* 37 ('7') = */ 4.0,
+ /* 38 ('8') = */ 4.0,
+ /* 39 ('9') = */ 4.0,
+ /* 3a (':') = */ 1.0,
+ /* 3b (';') = */ 1.0,
+ /* 3c ('<') = */ 3.0,
+ /* 3d ('=') = */ 3.0,
+ /* 3e ('>') = */ 3.0,
+ /* 3f ('?') = */ 2.0,
+ /* 40 ('@') = */ 3.0,
+ /* 41 ('A') = */ 5.0,
+ /* 42 ('B') = */ 5.0,
+ /* 43 ('C') = */ 5.0,
+ /* 44 ('D') = */ 5.0,
+ /* 45 ('E') = */ 5.0,
+ /* 46 ('F') = */ 5.0,
+ /* 47 ('G') = */ 5.0,
+ /* 48 ('H') = */ 5.0,
+ /* 49 ('I') = */ 1.0,
+ /* 4a ('J') = */ 5.0,
+ /* 4b ('K') = */ 5.0,
+ /* 4c ('L') = */ 5.0,
+ /* 4d ('M') = */ 5.0,
+ /* 4e ('N') = */ 5.0,
+ /* 4f ('O') = */ 5.0,
+ /* 50 ('P') = */ 5.0,
+ /* 51 ('Q') = */ 5.0,
+ /* 52 ('R') = */ 5.0,
+ /* 53 ('S') = */ 5.0,
+ /* 54 ('T') = */ 5.0,
+ /* 55 ('U') = */ 5.0,
+ /* 56 ('V') = */ 5.0,
+ /* 57 ('W') = */ 5.0,
+ /* 58 ('X') = */ 5.0,
+ /* 59 ('Y') = */ 5.0,
+ /* 5a ('Z') = */ 5.0,
+ /* 5b ('[') = */ 2.0,
+ /* 5c ('\') = */ 3.0,
+ /* 5d (']') = */ 2.0,
+ /* 5e ('^') = */ 1.0,
+ /* 5f ('_') = */ 3.0,
+ /* 60 ('`') = */ 1.0,
+ /* 61 ('a') = */ 3.0,
+ /* 62 ('b') = */ 3.0,
+ /* 63 ('c') = */ 3.0,
+ /* 64 ('d') = */ 3.0,
+ /* 65 ('e') = */ 3.0,
+ /* 66 ('f') = */ 3.0,
+ /* 67 ('g') = */ 3.0,
+ /* 68 ('h') = */ 3.0,
+ /* 69 ('i') = */ 1.0,
+ /* 6a ('j') = */ 2.0,
+ /* 6b ('k') = */ 3.0,
+ /* 6c ('l') = */ 1.0,
+ /* 6d ('m') = */ 5.0,
+ /* 6e ('n') = */ 3.0,
+ /* 6f ('o') = */ 3.0,
+ /* 70 ('p') = */ 3.0,
+ /* 71 ('q') = */ 3.0,
+ /* 72 ('r') = */ 2.0,
+ /* 73 ('s') = */ 3.0,
+ /* 74 ('t') = */ 2.0,
+ /* 75 ('u') = */ 3.0,
+ /* 76 ('v') = */ 3.0,
+ /* 77 ('w') = */ 3.0,
+ /* 78 ('x') = */ 3.0,
+ /* 79 ('y') = */ 3.0,
+ /* 7a ('z') = */ 3.0,
+ /* 7b ('{') = */ 2.0,
+ /* 7c ('|') = */ 1.0,
+ /* 7d ('}') = */ 2.0,
+ /* 7e ('~') = */ 2.0
+};
+
+
+/*
+ * What size is a string (in points)?
+ */
+
+#define FUDGE (2.834646 * 0.6)
+
+floatish
+StringSize(s)
+ char* s;
+{
+ floatish r;
+
+ for (r = 0.0; *s; s++) {
+ r += fonttab[(*s) - 0x20];
+ }
+
+ return r * FUDGE;
+}
diff --git a/massif/hp2ps/Dimensions.h b/massif/hp2ps/Dimensions.h
new file mode 100644
index 0000000..7bcc05b
--- /dev/null
+++ b/massif/hp2ps/Dimensions.h
@@ -0,0 +1,22 @@
+#ifndef DIMENSIONS_H
+#define DIMENSIONS_H
+
+extern floatish borderheight;
+extern floatish borderwidth;
+extern floatish borderspace;
+extern floatish borderthick;
+
+extern floatish titleheight;
+extern floatish titlewidth;
+extern floatish titletextspace;
+
+extern floatish graphx0;
+extern floatish graphy0;
+
+extern floatish graphheight;
+extern floatish graphwidth;
+
+void Dimensions PROTO((void));
+floatish StringSize PROTO((char *));
+
+#endif /* DIMENSIONS_H */
diff --git a/massif/hp2ps/Error.c b/massif/hp2ps/Error.c
new file mode 100644
index 0000000..7844204
--- /dev/null
+++ b/massif/hp2ps/Error.c
@@ -0,0 +1,55 @@
+#include <stdio.h>
+#include "Main.h"
+#include "Defines.h"
+
+/* own stuff */
+#include "Error.h"
+
+void exit PROTO((int));
+
+/*VARARGS0*/
+void
+Error(a1,a2,a3,a4)
+ char* a1; char* a2; char* a3; char* a4;
+{
+ fflush(stdout);
+ fprintf(stderr, "%s: ", programname);
+ fprintf(stderr, a1, a2, a3, a4);
+ fprintf(stderr, "\n");
+ exit(1);
+}
+
+/*VARARGS0*/
+void
+Disaster(a1,a2,a3,a4)
+ char* a1; char* a2; char* a3; char* a4;
+{
+ fflush(stdout);
+ fprintf(stderr, "%s: ", programname);
+ fprintf(stderr, " Disaster! (");
+ fprintf(stderr, a1, a2, a3, a4);
+ fprintf(stderr, ")\n");
+ exit(1);
+}
+
+void
+Usage(str)
+ char *str;
+{
+ if (str) printf("error: %s\n", str);
+ printf("usage: %s -b -d -ef -g -i -p -mn -p -s -tf -y [file[.hp]]\n", programname);
+ printf("where -b use large title box\n");
+ printf(" -d sort by standard deviation\n");
+ printf(" -ef[in|mm|pt] produce Encapsulated PostScript f units wide (f > 2 inches)\n");
+ printf(" -g produce output suitable for GHOSTSCRIPT previever\n");
+ printf(" -i[+|-] sort by identifier string (-i+ gives greatest on top) \n");
+ printf(" -mn print maximum of n bands (default & max 20)\n");
+ printf(" -m0 removes the band limit altogether\n");
+ printf(" -p use previous scaling, shading and ordering\n");
+ printf(" -s use small title box\n");
+ printf(" -tf ignore trace bands which sum below f%% (default 1%%, max 5%%)\n");
+ printf(" -y traditional\n");
+ printf(" -c colour ouput\n");
+ exit(0);
+}
+
diff --git a/massif/hp2ps/Error.h b/massif/hp2ps/Error.h
new file mode 100644
index 0000000..0febc84
--- /dev/null
+++ b/massif/hp2ps/Error.h
@@ -0,0 +1,8 @@
+#ifndef ERROR_H
+#define ERROR_H
+
+extern void Error (); /*PROTO((char *, ...)); */
+extern void Disaster (); /* PROTO((char *, ...)); */
+extern void Usage (); /* PROTO((char *)); */
+
+#endif /* ERROR_H */
diff --git a/massif/hp2ps/HpFile.c b/massif/hp2ps/HpFile.c
new file mode 100644
index 0000000..071016f
--- /dev/null
+++ b/massif/hp2ps/HpFile.c
@@ -0,0 +1,587 @@
+#include <ctype.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "Main.h"
+#include "Defines.h"
+#include "Error.h"
+#include "HpFile.h"
+#include "Utilities.h"
+
+#ifndef atof
+double atof PROTO((const char *));
+#endif
+
+/* own stuff already included */
+
+#define N_MARKS 50 /* start size of the mark table */
+#define N_SAMPLES 500 /* start size of the sample table */
+
+char *theident;
+char *thestring;
+int theinteger;
+floatish thefloatish;
+int g_ch; /* last character read */
+token thetok; /* last token */
+int linenum; /* current line number */
+int endfile; /* true at end of file */
+
+static boolish gotjob = 0; /* "JOB" read */
+static boolish gotdate = 0; /* "DATE" read */
+static boolish gotvalueunit = 0; /* "VALUE_UNIT" read */
+static boolish gotsampleunit = 0; /* "SAMPLE_UNIT" read */
+static boolish insample = 0; /* true when in sample */
+
+static floatish lastsample; /* the last sample time */
+
+static void GetHpLine PROTO((FILE *)); /* forward */
+static void GetHpTok PROTO((FILE *)); /* forward */
+
+static struct entry *GetEntry PROTO((char *)); /* forward */
+
+static void MakeIdentTable PROTO((void)); /* forward */
+
+char *jobstring;
+char *datestring;
+
+char *sampleunitstring;
+char *valueunitstring;
+
+floatish *samplemap; /* sample intervals */
+floatish *markmap; /* sample marks */
+
+/*
+ * An extremely simple parser. The input is organised into lines of
+ * the form
+ *
+ * JOB s -- job identifier string
+ * DATE s -- date string
+ * SAMPLE_UNIT s -- sample unit eg "seconds"
+ * VALUE_UNIT s -- value unit eg "bytes"
+ * MARK i -- sample mark
+ * BEGIN_SAMPLE i -- start of ith sample
+ * identifier i -- there are i identifiers in this sample
+ * END_SAMPLE i -- end of ith sample
+ *
+ */
+
+void
+GetHpFile(infp)
+ FILE *infp;
+{
+ nsamples = 0;
+ nmarks = 0;
+ nidents = 0;
+
+ g_ch = ' ';
+ endfile = 0;
+ linenum = 1;
+ lastsample = 0.0;
+
+ GetHpTok(infp);
+
+ while (endfile == 0) {
+ GetHpLine(infp);
+ }
+
+ if (!gotjob) {
+ Error("%s: JOB missing", hpfile);
+ }
+
+ if (!gotdate) {
+ Error("%s: DATE missing", hpfile);
+ }
+
+ if (!gotvalueunit) {
+ Error("%s: VALUE_UNIT missing", hpfile);
+ }
+
+ if (!gotsampleunit) {
+ Error("%s: SAMPLE_UNIT missing", hpfile);
+ }
+
+ if (nsamples == 0) {
+ Error("%s: contains no samples", hpfile);
+ }
+
+
+ MakeIdentTable();
+
+ fclose(hpfp);
+}
+
+
+/*
+ * Read the next line from the input, check the syntax, and perform
+ * the appropriate action.
+ */
+
+static void
+GetHpLine(infp)
+ FILE* infp;
+{
+ static intish nmarkmax = 0, nsamplemax = 0;
+
+ switch (thetok) {
+ case JOB_TOK:
+ GetHpTok(infp);
+ if (thetok != STRING_TOK) {
+ Error("%s, line %d: string must follow JOB", hpfile, linenum);
+ }
+ jobstring = thestring;
+ gotjob = 1;
+ GetHpTok(infp);
+ break;
+
+ case DATE_TOK:
+ GetHpTok(infp);
+ if (thetok != STRING_TOK) {
+ Error("%s, line %d: string must follow DATE", hpfile, linenum);
+ }
+ datestring = thestring;
+ gotdate = 1;
+ GetHpTok(infp);
+ break;
+
+ case SAMPLE_UNIT_TOK:
+ GetHpTok(infp);
+ if (thetok != STRING_TOK) {
+ Error("%s, line %d: string must follow SAMPLE_UNIT", hpfile,
+ linenum);
+ }
+ sampleunitstring = thestring;
+ gotsampleunit = 1;
+ GetHpTok(infp);
+ break;
+
+ case VALUE_UNIT_TOK:
+ GetHpTok(infp);
+ if (thetok != STRING_TOK) {
+ Error("%s, line %d: string must follow VALUE_UNIT", hpfile,
+ linenum);
+ }
+ valueunitstring = thestring;
+ gotvalueunit = 1;
+ GetHpTok(infp);
+ break;
+
+ case MARK_TOK:
+ GetHpTok(infp);
+ if (thetok != FLOAT_TOK) {
+ Error("%s, line %d, floating point number must follow MARK",
+ hpfile, linenum);
+ }
+ if (insample) {
+ Error("%s, line %d, MARK occurs within sample", hpfile, linenum);
+ }
+ if (nmarks >= nmarkmax) {
+ if (!markmap) {
+ nmarkmax = N_MARKS;
+ markmap = (floatish*) xmalloc(nmarkmax * sizeof(floatish));
+ } else {
+ nmarkmax *= 2;
+ markmap = (floatish*) xrealloc(markmap, nmarkmax * sizeof(floatish));
+ }
+ }
+ markmap[ nmarks++ ] = thefloatish;
+ GetHpTok(infp);
+ break;
+
+ case BEGIN_SAMPLE_TOK:
+ insample = 1;
+ GetHpTok(infp);
+ if (thetok != FLOAT_TOK) {
+ Error("%s, line %d, floating point number must follow BEGIN_SAMPLE", hpfile, linenum);
+ }
+ if (thefloatish < lastsample) {
+ Error("%s, line %d, samples out of sequence", hpfile, linenum);
+ } else {
+ lastsample = thefloatish;
+ }
+ if (nsamples >= nsamplemax) {
+ if (!samplemap) {
+ nsamplemax = N_SAMPLES;
+ samplemap = (floatish*) xmalloc(nsamplemax * sizeof(floatish));
+ } else {
+ nsamplemax *= 2;
+ samplemap = (floatish*) xrealloc(samplemap,
+ nsamplemax * sizeof(floatish));
+ }
+ }
+ samplemap[ nsamples ] = thefloatish;
+ GetHpTok(infp);
+ break;
+
+ case END_SAMPLE_TOK:
+ insample = 0;
+ GetHpTok(infp);
+ if (thetok != FLOAT_TOK) {
+ Error("%s, line %d: floating point number must follow END_SAMPLE",
+ hpfile, linenum);
+ }
+ nsamples++;
+ GetHpTok(infp);
+ break;
+
+ case IDENTIFIER_TOK:
+ GetHpTok(infp);
+ if (thetok != INTEGER_TOK) {
+ Error("%s, line %d: integer must follow identifier", hpfile,
+ linenum);
+ }
+ StoreSample(GetEntry(theident), nsamples, (floatish) theinteger);
+ GetHpTok(infp);
+ break;
+
+ case EOF_TOK:
+ endfile = 1;
+ break;
+
+ default:
+ Error("%s, line %d: %s unexpected", hpfile, linenum,
+ TokenToString(thetok));
+ break;
+ }
+}
+
+
+char *
+TokenToString(t)
+ token t;
+{
+ switch (t) {
+ case EOF_TOK: return "EOF";
+ case INTEGER_TOK: return "integer";
+ case FLOAT_TOK: return "floating point number";
+ case IDENTIFIER_TOK: return "identifier";
+ case STRING_TOK: return "string";
+ case BEGIN_SAMPLE_TOK: return "BEGIN_SAMPLE";
+ case END_SAMPLE_TOK: return "END_SAMPLE";
+ case JOB_TOK: return "JOB";
+ case DATE_TOK: return "DATE";
+ case SAMPLE_UNIT_TOK: return "SAMPLE_UNIT";
+ case VALUE_UNIT_TOK: return "VALUE_UNIT";
+ case MARK_TOK: return "MARK";
+
+ case X_RANGE_TOK: return "X_RANGE";
+ case Y_RANGE_TOK: return "Y_RANGE";
+ case ORDER_TOK: return "ORDER";
+ case SHADE_TOK: return "SHADE";
+ default: return "(strange token)";
+ }
+}
+
+/*
+ * Read the next token from the input and assign its value
+ * to the global variable "thetok". In the case of numbers,
+ * the corresponding value is also assigned to "theinteger"
+ * or "thefloatish" as appropriate; in the case of identifiers
+ * it is assigned to "theident".
+ */
+
+static void
+GetHpTok(infp)
+ FILE* infp;
+{
+
+ while (isspace(g_ch)) { /* skip whitespace */
+ if (g_ch == '\n') linenum++;
+ g_ch = getc(infp);
+ }
+
+ if (g_ch == EOF) {
+ thetok = EOF_TOK;
+ return;
+ }
+
+ if (isdigit(g_ch)) {
+ thetok = GetNumber(infp);
+ return;
+ } else if (g_ch == '\"') {
+ GetString(infp);
+ thetok = STRING_TOK;
+ return;
+ } else if (IsIdChar(g_ch)) {
+ ASSERT(! (isdigit(g_ch))); /* g_ch can't be a digit here */
+ GetIdent(infp);
+ if (!isupper(theident[0])) {
+ thetok = IDENTIFIER_TOK;
+ } else if (strcmp(theident, "BEGIN_SAMPLE") == 0) {
+ thetok = BEGIN_SAMPLE_TOK;
+ } else if (strcmp(theident, "END_SAMPLE") == 0) {
+ thetok = END_SAMPLE_TOK;
+ } else if (strcmp(theident, "JOB") == 0) {
+ thetok = JOB_TOK;
+ } else if (strcmp(theident, "DATE") == 0) {
+ thetok = DATE_TOK;
+ } else if (strcmp(theident, "SAMPLE_UNIT") == 0) {
+ thetok = SAMPLE_UNIT_TOK;
+ } else if (strcmp(theident, "VALUE_UNIT") == 0) {
+ thetok = VALUE_UNIT_TOK;
+ } else if (strcmp(theident, "MARK") == 0) {
+ thetok = MARK_TOK;
+ } else {
+ thetok = IDENTIFIER_TOK;
+ }
+ return;
+ } else {
+ Error("%s, line %d: strange character (%c)", hpfile, linenum, g_ch);
+ }
+}
+
+
+/*
+ * Read a sequence of digits and convert the result to an integer
+ * or floating point value (assigned to the "theinteger" or
+ * "thefloatish").
+ */
+
+static char numberstring[ NUMBER_LENGTH - 1 ];
+
+token
+GetNumber(infp)
+ FILE* infp;
+{
+ int i;
+ int containsdot;
+
+ ASSERT(isdigit(ch)); /* we must have a digit to start with */
+
+ containsdot = 0;
+
+ for (i = 0; i < NUMBER_LENGTH && (isdigit(g_ch) || g_ch == '.'); i++) {
+ numberstring[ i ] = g_ch;
+ containsdot |= (g_ch == '.');
+ g_ch = getc(infp);
+ }
+
+ ASSERT(i < NUMBER_LENGTH); /* did not overflow */
+
+ numberstring[ i ] = '\0';
+
+ if (containsdot) {
+ thefloatish = (floatish) atof(numberstring);
+ return FLOAT_TOK;
+ } else {
+ theinteger = atoi(numberstring);
+ return INTEGER_TOK;
+ }
+}
+
+/*
+ * Read a sequence of identifier characters and assign the result
+ * to the string "theident".
+ */
+
+void
+GetIdent(infp)
+ FILE *infp;
+{
+ unsigned int i;
+ char idbuffer[5000];
+
+ for (i = 0; i < (sizeof idbuffer)-1 && IsIdChar(g_ch); i++) {
+ idbuffer[ i ] = g_ch;
+ g_ch = getc(infp);
+ }
+
+ idbuffer[ i ] = '\0';
+
+ if (theident)
+ free(theident);
+
+ theident = copystring(idbuffer);
+}
+
+
+/*
+ * Read a sequence of characters that make up a string and
+ * assign the result to "thestring".
+ */
+
+void
+GetString(infp)
+ FILE *infp;
+{
+ unsigned int i;
+ char stringbuffer[5000];
+
+ ASSERT(ch == '\"');
+
+ g_ch = getc(infp); /* skip the '\"' that begins the string */
+
+ for (i = 0; i < (sizeof stringbuffer)-1 && g_ch != '\"'; i++) {
+ stringbuffer[ i ] = g_ch;
+ g_ch = getc(infp);
+ }
+
+ stringbuffer[i] = '\0';
+ thestring = copystring(stringbuffer);
+
+ ASSERT(g_ch == '\"');
+
+ g_ch = getc(infp); /* skip the '\"' that terminates the string */
+}
+
+boolish
+IsIdChar(ch)
+ int ch;
+{
+ return (!isspace(ch));
+}
+
+
+/*
+ * The information associated with each identifier is stored
+ * in a linked list of chunks. The table below allows the list
+ * of chunks to be retrieved given an identifier name.
+ */
+
+#define N_HASH 513
+
+static struct entry* hashtable[ N_HASH ];
+
+static intish
+Hash(s)
+ char *s;
+{
+ int r;
+
+ for (r = 0; *s; s++) {
+ r = r + r + r + *s;
+ }
+
+ if (r < 0) r = -r;
+
+ return r % N_HASH;
+}
+
+/*
+ * Get space for a new chunk. Initialise it, and return a pointer
+ * to the new chunk.
+ */
+
+static struct chunk*
+MakeChunk()
+{
+ struct chunk* ch;
+ struct datapoint* d;
+
+ ch = (struct chunk*) xmalloc( sizeof(struct chunk) );
+
+ d = (struct datapoint*) xmalloc (sizeof(struct datapoint) * N_CHUNK);
+
+ ch->nd = 0;
+ ch->d = d;
+ ch->next = 0;
+ return ch;
+}
+
+
+/*
+ * Get space for a new entry. Initialise it, and return a pointer
+ * to the new entry.
+ */
+
+struct entry *
+MakeEntry(name)
+ char *name;
+{
+ struct entry* e;
+
+ e = (struct entry *) xmalloc(sizeof(struct entry));
+ e->chk = MakeChunk();
+ e->name = copystring(name);
+ return e;
+}
+
+/*
+ * Get the entry associated with "name", creating a new entry if
+ * necessary.
+ */
+
+static struct entry *
+GetEntry(name)
+ char* name;
+{
+ intish h;
+ struct entry* e;
+
+ h = Hash(name);
+
+ for (e = hashtable[ h ]; e; e = e->next) {
+ if (strcmp(e->name, name) == 0) {
+ break;
+ }
+ }
+
+ if (e) {
+ return (e);
+ } else {
+ nidents++;
+ e = MakeEntry(name);
+ e->next = hashtable[ h ];
+ hashtable[ h ] = e;
+ return (e);
+ }
+}
+
+
+/*
+ * Store information from a sample.
+ */
+
+void
+StoreSample(en, bucket, value)
+ struct entry* en; intish bucket; floatish value;
+{
+ struct chunk* chk;
+
+ for (chk = en->chk; chk->next != 0; chk = chk->next)
+ ;
+
+ if (chk->nd < N_CHUNK) {
+ chk->d[ chk->nd ].bucket = bucket;
+ chk->d[ chk->nd ].value = value;
+ chk->nd += 1;
+ } else {
+ struct chunk* t;
+ t = chk->next = MakeChunk();
+ t->d[ 0 ].bucket = bucket;
+ t->d[ 0 ].value = value;
+ t->nd += 1;
+ }
+}
+
+
+struct entry** identtable;
+
+/*
+ * The hash table is useful while reading the input, but it
+ * becomes a liability thereafter. The code below converts
+ * it to a more easily processed table.
+ */
+
+static void
+MakeIdentTable()
+{
+ intish i;
+ intish j;
+ struct entry* e;
+
+ nidents = 0;
+ for (i = 0; i < N_HASH; i++) {
+ for (e = hashtable[ i ]; e; e = e->next) {
+ nidents++;
+ }
+ }
+
+ identtable = (struct entry**) xmalloc(nidents * sizeof(struct entry*));
+ j = 0;
+
+ for (i = 0; i < N_HASH; i++) {
+ for (e = hashtable[ i ]; e; e = e->next, j++) {
+ identtable[ j ] = e;
+ }
+ }
+}
diff --git a/massif/hp2ps/HpFile.h b/massif/hp2ps/HpFile.h
new file mode 100644
index 0000000..571a584
--- /dev/null
+++ b/massif/hp2ps/HpFile.h
@@ -0,0 +1,77 @@
+#ifndef HP_FILE_H
+#define HP_FILE_H
+
+typedef enum {
+ /* These tokens are found in ".hp" files */
+
+ EOF_TOK,
+ INTEGER_TOK,
+ FLOAT_TOK,
+ IDENTIFIER_TOK,
+ STRING_TOK,
+ BEGIN_SAMPLE_TOK,
+ END_SAMPLE_TOK,
+ JOB_TOK,
+ DATE_TOK,
+ SAMPLE_UNIT_TOK,
+ VALUE_UNIT_TOK,
+ MARK_TOK,
+
+ /* These extra ones are found only in ".aux" files */
+
+ X_RANGE_TOK,
+ Y_RANGE_TOK,
+ ORDER_TOK,
+ SHADE_TOK
+} token;
+
+struct datapoint {
+ int bucket;
+ floatish value;
+};
+
+struct chunk {
+ struct chunk *next;
+ short nd; /* 0 .. N_CHUNK - 1 */
+ struct datapoint *d;
+};
+
+
+struct entry {
+ struct entry *next;
+ struct chunk *chk;
+ char *name;
+};
+
+extern char *theident;
+extern char *thestring;
+extern int theinteger;
+extern floatish thefloatish;
+extern int g_ch;
+extern token thetok;
+extern int linenum;
+extern int endfile;
+
+char *TokenToString PROTO((token));
+
+extern struct entry** identtable;
+
+extern floatish *samplemap;
+extern floatish *markmap;
+
+void GetHpFile PROTO((FILE *));
+void StoreSample PROTO((struct entry *, intish, floatish));
+struct entry *MakeEntry PROTO((char *));
+
+token GetNumber PROTO((FILE *));
+void GetIdent PROTO((FILE *));
+void GetString PROTO((FILE *));
+boolish IsIdChar PROTO((int)); /* int is a "char" from getc */
+
+extern char *jobstring;
+extern char *datestring;
+
+extern char *sampleunitstring;
+extern char *valueunitstring;
+
+#endif /* HP_FILE_H */
diff --git a/massif/hp2ps/INSTALL b/massif/hp2ps/INSTALL
new file mode 100644
index 0000000..92fe7b7
--- /dev/null
+++ b/massif/hp2ps/INSTALL
@@ -0,0 +1,17 @@
+NOTE: these are instructions for installing hp2ps separately. If you only want
+to use it with the Valgrind tool, Massif, it should be installed automatically.
+
+The original Makefile, for which the below instructions apply, is kept as
+Makefile.old.
+
+-----------------------------------------------------------------------------
+For binary distribution:
+
+ - just copy "hp2ps" into an appropriate directory.
+
+For source distribution:
+
+ - edit "Makefile" and set the $DSTBIN to the directory you wish to install
+ hp2ps in
+
+ - do "make install"
diff --git a/massif/hp2ps/Key.c b/massif/hp2ps/Key.c
new file mode 100644
index 0000000..a8a761d
--- /dev/null
+++ b/massif/hp2ps/Key.c
@@ -0,0 +1,63 @@
+#include <stdio.h>
+#include <math.h>
+#include "Main.h"
+#include "Defines.h"
+#include "Dimensions.h"
+#include "HpFile.h"
+#include "Shade.h"
+
+/* own stuff */
+#include "Key.h"
+
+static void KeyEntry PROTO((floatish, char *, floatish));
+
+void Key()
+{
+ intish i;
+ floatish c;
+ floatish dc;
+
+ for (i = 0; i < nidents; i++) /* count identifiers */
+ ;
+
+ c = graphy0;
+ dc = graphheight / (floatish) (i + 1);
+
+ for (i = 0; i < nidents; i++) {
+ c += dc;
+ KeyEntry(c, identtable[i]->name, ShadeOf(identtable[i]->name));
+ }
+}
+
+
+
+static void
+KeyEntry(centreline, name, colour)
+ floatish centreline; char* name; floatish colour;
+{
+ floatish namebase;
+ floatish keyboxbase;
+ floatish kstart;
+
+ namebase = centreline - (floatish) (NORMAL_FONT / 2);
+ keyboxbase = centreline - ((floatish) KEY_BOX_WIDTH / 2.0);
+
+ kstart = graphx0 + graphwidth;
+
+ fprintf(psfp, "%f %f moveto\n", kstart + borderspace, keyboxbase);
+ fprintf(psfp, "0 %d rlineto\n", KEY_BOX_WIDTH);
+ fprintf(psfp, "%d 0 rlineto\n", KEY_BOX_WIDTH);
+ fprintf(psfp, "0 %d rlineto\n", -KEY_BOX_WIDTH);
+ fprintf(psfp, "closepath\n");
+
+ fprintf(psfp, "gsave\n");
+ SetPSColour(colour);
+ fprintf(psfp, "fill\n");
+ fprintf(psfp, "grestore\n");
+ fprintf(psfp, "stroke\n");
+
+ fprintf(psfp, "HE%d setfont\n", NORMAL_FONT);
+ fprintf(psfp, "%f %f moveto\n", kstart + (floatish) KEY_BOX_WIDTH + 2 * borderspace, namebase);
+
+ fprintf(psfp, "(%s) show\n", name);
+}
diff --git a/massif/hp2ps/Key.h b/massif/hp2ps/Key.h
new file mode 100644
index 0000000..d2a7b8e
--- /dev/null
+++ b/massif/hp2ps/Key.h
@@ -0,0 +1,6 @@
+#ifndef KEY_H
+#define KEY_H
+
+void Key PROTO((void));
+
+#endif /* KEY_H */
diff --git a/massif/hp2ps/LICENSE b/massif/hp2ps/LICENSE
new file mode 100644
index 0000000..b5059b7
--- /dev/null
+++ b/massif/hp2ps/LICENSE
@@ -0,0 +1,31 @@
+The Glasgow Haskell Compiler License
+
+Copyright 2002, The University Court of the University of Glasgow.
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+- Redistributions of source code must retain the above copyright notice,
+this list of conditions and the following disclaimer.
+
+- Redistributions in binary form must reproduce the above copyright notice,
+this list of conditions and the following disclaimer in the documentation
+and/or other materials provided with the distribution.
+
+- Neither name of the University nor the names of its contributors may be
+used to endorse or promote products derived from this software without
+specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE UNIVERSITY COURT OF THE UNIVERSITY OF
+GLASGOW AND THE CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
+FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+UNIVERSITY COURT OF THE UNIVERSITY OF GLASGOW OR THE CONTRIBUTORS BE LIABLE
+FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
+DAMAGE.
diff --git a/massif/hp2ps/Main.c b/massif/hp2ps/Main.c
new file mode 100644
index 0000000..e1cfe63
--- /dev/null
+++ b/massif/hp2ps/Main.c
@@ -0,0 +1,253 @@
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include "Main.h"
+#include "Defines.h"
+#include "AuxFile.h"
+#include "AreaBelow.h"
+#include "Dimensions.h"
+#include "HpFile.h"
+#include "PsFile.h"
+#include "Reorder.h"
+#include "Scale.h"
+#include "TopTwenty.h"
+#include "TraceElement.h"
+#include "Deviation.h"
+#include "Error.h"
+#include "Utilities.h"
+
+boolish pflag = 0; /* read auxiliary file */
+boolish eflag = 0; /* scaled EPSF */
+boolish dflag = 0; /* sort by standard deviation */
+int iflag = 0; /* sort by identifier (3-way flag) */
+boolish gflag = 0; /* output suitable for previewer */
+boolish yflag = 0; /* ignore marks */
+boolish bflag = 0; /* use a big title box */
+boolish sflag = 0; /* use a small title box */
+int mflag = 0; /* max no. of bands displayed (default 20) */
+boolish tflag = 0; /* ignored threshold specified */
+boolish cflag = 0; /* colour output */
+
+boolish filter; /* true when running as a filter */
+
+static floatish WidthInPoints PROTO((char *)); /* forward */
+static FILE *Fp PROTO((char *, char **, char *, char *)); /* forward */
+
+char *hpfile;
+char *psfile;
+char *auxfile;
+
+char *programname;
+
+static char *pathName;
+static char *baseName; /* "basename" is a std C library name (sigh) */
+
+FILE* hpfp;
+FILE* psfp;
+FILE* auxfp;
+
+floatish xrange = 0.0;
+floatish yrange = 0.0;
+
+floatish auxxrange = 0.0;
+floatish auxyrange = 0.0;
+
+floatish epsfwidth;
+floatish areabelow;
+
+intish nsamples;
+intish nmarks;
+intish nidents;
+
+floatish THRESHOLD_PERCENT = DEFAULT_THRESHOLD;
+int TWENTY = DEFAULT_TWENTY;
+
+int main(argc, argv)
+int argc;
+char* argv[];
+{
+
+ programname = copystring(Basename(argv[0]));
+
+ argc--, argv++;
+ while (argc && argv[0][0] == '-') {
+ while (*++*argv)
+ switch(**argv) {
+ case 'p':
+ pflag++;
+ break;
+ case 'e':
+ eflag++;
+ epsfwidth = WidthInPoints(*argv + 1);
+ goto nextarg;
+ case 'd':
+ dflag++;
+ goto nextarg;
+ case 'i':
+ switch( *(*argv + 1) ) {
+ case '-':
+ iflag = -1;
+ case '+':
+ default:
+ iflag = 1;
+ }
+ goto nextarg;
+ case 'g':
+ gflag++;
+ goto nextarg;
+ case 'y':
+ yflag++;
+ goto nextarg;
+ case 'b':
+ bflag++;
+ goto nextarg;
+ case 's':
+ sflag++;
+ goto nextarg;
+ case 'm':
+ mflag++;
+ TWENTY = atoi(*argv + 1);
+ if (TWENTY > DEFAULT_TWENTY)
+ Usage(*argv-1);
+ goto nextarg;
+ case 't':
+ tflag++;
+ THRESHOLD_PERCENT = (floatish) atof(*argv + 1);
+ if (THRESHOLD_PERCENT < 0 || THRESHOLD_PERCENT > 5)
+ Usage(*argv-1);
+ goto nextarg;
+ case 'c':
+ cflag++;
+ goto nextarg;
+ case '?':
+ default:
+ Usage(*argv-1);
+ }
+nextarg: ;
+ argc--, argv++;
+ }
+
+ hpfile = "stdin";
+ psfile = "stdout";
+
+ hpfp = stdin;
+ psfp = stdout;
+
+ filter = argc < 1;
+
+
+
+ if (!filter) {
+ pathName = copystring(argv[0]);
+ DropSuffix(pathName, ".hp");
+ baseName = copystring(Basename(pathName));
+
+ hpfp = Fp(pathName, &hpfile, ".hp", "r");
+ psfp = Fp(baseName, &psfile, ".ps", "w");
+
+ if (pflag) auxfp = Fp(baseName, &auxfile, ".aux", "r");
+ }
+
+ GetHpFile(hpfp);
+
+ if (!filter && pflag) GetAuxFile(auxfp);
+
+
+ TraceElement(); /* Orders on total, Removes trace elements (tflag) */
+
+ if (dflag) Deviation(); /* ReOrders on deviation */
+
+ if (iflag) Identorder(iflag); /* ReOrders on identifier */
+
+ if (pflag) Reorder(); /* ReOrders on aux file */
+
+ if (TWENTY) TopTwenty(); /* Selects top twenty (mflag) */
+
+ Dimensions();
+
+ areabelow = AreaBelow();
+
+ Scale();
+
+ PutPsFile();
+
+ if (!filter) {
+ auxfp = Fp(baseName, &auxfile, ".aux", "w");
+ PutAuxFile(auxfp);
+ }
+
+ return(0);
+}
+
+
+
+typedef enum {POINTS, INCHES, MILLIMETRES} pim;
+
+static pim Units PROTO((char *)); /* forward */
+
+static floatish
+WidthInPoints(wstr)
+ char *wstr;
+{
+ floatish result;
+
+ result = (floatish) atof(wstr);
+
+ switch (Units(wstr)) {
+ case INCHES:
+ result *= 72.0;
+ break;
+ case MILLIMETRES:
+ result *= 2.834646;
+ break;
+ case POINTS:
+ default: ;
+ }
+
+ if (result <= 144) /* Minimum of 2in wide ! */
+ Usage(wstr);
+
+ return result;
+}
+
+
+static pim
+Units(wstr)
+ char* wstr;
+{
+int i;
+
+ i = strlen(wstr) - 2;
+
+ if (wstr[i] == 'p' && wstr[i+1] == 't') {
+ return POINTS;
+ } else if (wstr[i] == 'i' && wstr[i+1] == 'n') {
+ return INCHES;
+ } else if (wstr[i] == 'm' && wstr[i+1] == 'm') {
+ return MILLIMETRES;
+ } else {
+ return POINTS;
+ }
+}
+
+static FILE *
+Fp(rootname, filename, suffix, mode)
+ char* rootname; char** filename; char* suffix; char* mode;
+{
+ *filename = copystring2(rootname, suffix);
+
+ return(OpenFile(*filename, mode));
+}
+
+#ifdef DEBUG
+void
+_stgAssert (filename, linenum)
+ char *filename;
+ unsigned int linenum;
+{
+ fflush(stdout);
+ fprintf(stderr, "ASSERTION FAILED: file %s, line %u\n", filename, linenum);
+ fflush(stderr);
+ abort();
+}
+#endif
diff --git a/massif/hp2ps/Main.h b/massif/hp2ps/Main.h
new file mode 100644
index 0000000..3aedb91
--- /dev/null
+++ b/massif/hp2ps/Main.h
@@ -0,0 +1,78 @@
+#ifndef MAIN_H
+#define MAIN_H
+
+//#include "config.h"
+
+#ifdef __STDC__
+#define PROTO(x) x
+#else
+#define PROTO(x) ()
+#endif
+
+/* our own ASSERT macro (for C) */
+#ifndef DEBUG
+#define ASSERT(predicate) /*nothing*/
+
+#else
+void _ghcAssert PROTO((char *, unsigned int));
+
+#define ASSERT(predicate) \
+ if (predicate) \
+ /*null*/; \
+ else \
+ _ghcAssert(__FILE__, __LINE__)
+#endif
+
+/* partain: some ubiquitous types: floatish & intish.
+ Dubious to use float/int, but that is what it used to be...
+ (WDP 95/03)
+*/
+typedef double floatish;
+typedef double doublish; /* higher precision, if anything; little used */
+typedef int boolish;
+
+/* Use "long long" if we have it: the numbers in profiles can easily
+ * overflow 32 bits after a few seconds execution.
+ */
+#define HAVE_LONG_LONG 1 // --added by njn, because config.h removed
+
+#ifdef HAVE_LONG_LONG
+typedef long long int intish;
+#else
+typedef long int intish;
+#endif
+
+extern intish nsamples;
+extern intish nmarks;
+extern intish nidents;
+
+extern floatish maxcombinedheight;
+extern floatish areabelow;
+extern floatish epsfwidth;
+
+extern floatish xrange;
+extern floatish yrange;
+
+extern floatish auxxrange;
+extern floatish auxyrange;
+
+extern boolish eflag;
+extern boolish gflag;
+extern boolish yflag;
+extern boolish bflag;
+extern boolish sflag;
+extern int mflag;
+extern boolish tflag;
+extern boolish cflag;
+
+extern char *programname;
+
+extern char *hpfile;
+extern char *psfile;
+extern char *auxfile;
+
+extern FILE *hpfp;
+extern FILE *psfp;
+extern FILE *g_auxfp;
+
+#endif /* MAIN_H */
diff --git a/massif/hp2ps/Marks.c b/massif/hp2ps/Marks.c
new file mode 100644
index 0000000..27702c7
--- /dev/null
+++ b/massif/hp2ps/Marks.c
@@ -0,0 +1,43 @@
+#include <stdio.h>
+#include "Main.h"
+#include "Curves.h"
+#include "Dimensions.h"
+#include "HpFile.h"
+
+/* own stuff */
+#include "Marks.h"
+
+static void Caret PROTO((floatish, floatish, floatish));
+
+void
+Marks()
+{
+ intish i;
+ floatish m;
+
+ for (i = 0; i < nmarks; i++) {
+ m = ((markmap[i] - samplemap[0]) / xrange) * graphwidth;
+ Caret(xpage(m), ypage(0.0), 4.0);
+ }
+}
+
+
+/*
+ * Draw a small white caret at (x,y) with width 2 * d
+ */
+
+static void
+Caret(x,y,d)
+ floatish x; floatish y; floatish d;
+{
+ fprintf(psfp, "%f %f moveto\n", x - d, y);
+ fprintf(psfp, "%f %f rlineto\n", d, -d);
+ fprintf(psfp, "%f %f rlineto\n", d, d);
+ fprintf(psfp, "closepath\n");
+
+ fprintf(psfp, "gsave\n");
+ fprintf(psfp, "1.0 setgray\n");
+ fprintf(psfp, "fill\n");
+ fprintf(psfp, "grestore\n");
+ fprintf(psfp, "stroke\n");
+}
diff --git a/massif/hp2ps/Marks.h b/massif/hp2ps/Marks.h
new file mode 100644
index 0000000..41956f6
--- /dev/null
+++ b/massif/hp2ps/Marks.h
@@ -0,0 +1,6 @@
+#ifndef MARKS_H
+#define MARKS_H
+
+void Marks PROTO((void));
+
+#endif /* MARKS_H */
diff --git a/massif/hp2ps/PsFile.c b/massif/hp2ps/PsFile.c
new file mode 100644
index 0000000..40b08da
--- /dev/null
+++ b/massif/hp2ps/PsFile.c
@@ -0,0 +1,280 @@
+#include <stdio.h>
+#include <string.h>
+#include "Main.h"
+#include "Defines.h"
+#include "Dimensions.h"
+#include "Curves.h"
+#include "HpFile.h"
+#include "Axes.h"
+#include "Key.h"
+#include "Marks.h"
+#include "Utilities.h"
+
+/* own stuff */
+#include "PsFile.h"
+
+static void Prologue PROTO((void)); /* forward */
+static void Variables PROTO((void)); /* forward */
+static void BorderOutlineBox PROTO((void)); /* forward */
+static void BigTitleOutlineBox PROTO((void)); /* forward */
+static void TitleOutlineBox PROTO((void)); /* forward */
+static void BigTitleText PROTO((void)); /* forward */
+static void TitleText PROTO((void)); /* forward */
+
+void
+PutPsFile()
+{
+ Prologue();
+ Variables();
+ BorderOutlineBox();
+
+ if (bflag) {
+ BigTitleOutlineBox();
+ BigTitleText();
+ } else {
+ TitleOutlineBox();
+ TitleText();
+ }
+
+ CurvesInit();
+
+ Axes();
+
+ if (TWENTY) Key();
+
+ Curves();
+
+ if (!yflag) Marks();
+
+ fprintf(psfp, "showpage\n");
+}
+
+
+static void StandardSpecialComments PROTO((void)); /* forward */
+static void EPSFSpecialComments PROTO((floatish)); /* forward */
+static void Landscape PROTO((void)); /* forward */
+static void Portrait PROTO((void)); /* forward */
+static void Scaling PROTO((floatish)); /* forward */
+
+static void
+Prologue()
+{
+ if (eflag) {
+ floatish epsfscale = epsfwidth / (floatish) borderwidth;
+ EPSFSpecialComments(epsfscale);
+ Scaling(epsfscale);
+ } else {
+ StandardSpecialComments();
+ if (gflag) Portrait(); else Landscape();
+ }
+}
+
+extern char *jobstring;
+extern char *datestring;
+
+static void
+StandardSpecialComments()
+{
+ fprintf(psfp, "%%!PS-Adobe-2.0\n");
+ fprintf(psfp, "%%%%Title: %s\n", jobstring);
+ fprintf(psfp, "%%%%Creator: %s (version %s)\n", programname, VERSION);
+ fprintf(psfp, "%%%%CreationDate: %s\n", datestring);
+ fprintf(psfp, "%%%%EndComments\n");
+}
+
+static void
+EPSFSpecialComments(epsfscale)
+ floatish epsfscale;
+{
+ fprintf(psfp, "%%!PS-Adobe-2.0\n");
+ fprintf(psfp, "%%%%Title: %s\n", jobstring);
+ fprintf(psfp, "%%%%Creator: %s (version %s)\n", programname, VERSION);
+ fprintf(psfp, "%%%%CreationDate: %s\n", datestring);
+ fprintf(psfp, "%%%%BoundingBox: 0 0 %d %d\n",
+ (int) (borderwidth * epsfscale + 0.5),
+ (int) (borderheight * epsfscale + 0.5) );
+ fprintf(psfp, "%%%%EndComments\n");
+}
+
+
+
+static void
+Landscape()
+{
+ fprintf(psfp, "-90 rotate\n");
+ fprintf(psfp, "%f %f translate\n", -(borderwidth + (floatish) START_Y),
+ (floatish) START_X);
+}
+
+static void
+Portrait()
+{
+ fprintf(psfp, "%f %f translate\n", (floatish) START_X, (floatish) START_Y);
+}
+
+static void
+Scaling(epsfscale)
+ floatish epsfscale;
+{
+ fprintf(psfp, "%f %f scale\n", epsfscale, epsfscale);
+}
+
+
+static void
+Variables()
+{
+ fprintf(psfp, "/HE%d /Helvetica findfont %d scalefont def\n",
+ NORMAL_FONT, NORMAL_FONT);
+
+ fprintf(psfp, "/HE%d /Helvetica findfont %d scalefont def\n",
+ LARGE_FONT, LARGE_FONT);
+}
+
+
+static void
+BorderOutlineBox()
+{
+ fprintf(psfp, "newpath\n");
+ fprintf(psfp, "0 0 moveto\n");
+ fprintf(psfp, "0 %f rlineto\n", borderheight);
+ fprintf(psfp, "%f 0 rlineto\n", borderwidth);
+ fprintf(psfp, "0 %f rlineto\n", -borderheight);
+ fprintf(psfp, "closepath\n");
+ fprintf(psfp, "%f setlinewidth\n", borderthick);
+ fprintf(psfp, "stroke\n");
+}
+
+static void
+BigTitleOutlineBox()
+{
+ fprintf(psfp, "newpath\n");
+ fprintf(psfp, "%f %f moveto\n", borderspace,
+ borderheight - titleheight - borderspace);
+ fprintf(psfp, "0 %f rlineto\n", titleheight);
+ fprintf(psfp, "%f 0 rlineto\n", titlewidth);
+ fprintf(psfp, "0 %f rlineto\n", -titleheight);
+ fprintf(psfp, "closepath\n");
+ fprintf(psfp, "%f setlinewidth\n", borderthick);
+ fprintf(psfp, "stroke\n");
+
+ fprintf(psfp, "%f %f moveto\n", borderspace,
+ borderheight - titleheight / 2 - borderspace);
+ fprintf(psfp, "%f 0 rlineto\n", titlewidth);
+ fprintf(psfp, "stroke\n");
+}
+
+
+static void
+TitleOutlineBox()
+{
+ fprintf(psfp, "newpath\n");
+ fprintf(psfp, "%f %f moveto\n", borderspace,
+ borderheight - titleheight - borderspace);
+ fprintf(psfp, "0 %f rlineto\n", titleheight);
+ fprintf(psfp, "%f 0 rlineto\n", titlewidth);
+ fprintf(psfp, "0 %f rlineto\n", -titleheight);
+ fprintf(psfp, "closepath\n");
+ fprintf(psfp, "%f setlinewidth\n", borderthick);
+ fprintf(psfp, "stroke\n");
+}
+
+static void EscapePrint PROTO((char *, int)); /* forward */
+
+static void
+BigTitleText()
+{
+ floatish x, y;
+
+ x = borderspace + titletextspace;
+ y = borderheight - titleheight / 2 - borderspace + titletextspace;
+
+ /* job identifier goes on top at the far left */
+
+ fprintf(psfp, "HE%d setfont\n", TITLE_TEXT_FONT);
+ fprintf(psfp, "%f %f moveto\n", x, y);
+ fputc('(', psfp);
+ EscapePrint(jobstring, BIG_JOB_STRING_WIDTH);
+ fprintf(psfp, ") show\n");
+
+ y = borderheight - titleheight - borderspace + titletextspace;
+
+ /* area below curve gows at the botton, far left */
+
+ fprintf(psfp, "HE%d setfont\n", TITLE_TEXT_FONT);
+ fprintf(psfp, "%f %f moveto\n", x, y);
+ fputc('(', psfp);
+ CommaPrint(psfp, (intish)areabelow);
+ fprintf(psfp, " %s x %s)\n", valueunitstring, sampleunitstring);
+ fprintf(psfp, "show\n");
+
+ /* date goes at far right */
+
+ fprintf(psfp, "HE%d setfont\n", TITLE_TEXT_FONT);
+ fprintf(psfp, "(%s)\n", datestring);
+ fprintf(psfp, "dup stringwidth pop\n");
+ fprintf(psfp, "%f\n", (titlewidth + borderspace) - titletextspace);
+ fprintf(psfp, "exch sub\n");
+ fprintf(psfp, "%f moveto\n", y);
+ fprintf(psfp, "show\n");
+}
+
+
+static void
+TitleText()
+{
+ floatish x, y;
+
+ x = borderspace + titletextspace;
+ y = borderheight - titleheight - borderspace + titletextspace;
+
+ /* job identifier goes at far left */
+
+ fprintf(psfp, "HE%d setfont\n", TITLE_TEXT_FONT);
+ fprintf(psfp, "%f %f moveto\n", x, y);
+ fputc('(', psfp);
+ EscapePrint(jobstring, SMALL_JOB_STRING_WIDTH);
+ fprintf(psfp, ") show\n");
+
+ /* area below curve is centered */
+
+ fprintf(psfp, "HE%d setfont\n", TITLE_TEXT_FONT);
+ fputc('(', psfp);
+ CommaPrint(psfp, (intish) areabelow);
+ fprintf(psfp, " %s x %s)\n", valueunitstring, sampleunitstring);
+
+ fprintf(psfp, "dup stringwidth pop\n");
+ fprintf(psfp, "2 div\n");
+ fprintf(psfp, "%f\n", titlewidth / 2);
+ fprintf(psfp, "exch sub\n");
+ fprintf(psfp, "%f moveto\n", y);
+ fprintf(psfp, "show\n");
+
+ /* date goes at far right */
+
+ fprintf(psfp, "HE%d setfont\n", TITLE_TEXT_FONT);
+ fprintf(psfp, "(%s)\n", datestring);
+ fprintf(psfp, "dup stringwidth pop\n");
+ fprintf(psfp, "%f\n", (titlewidth + borderspace) - titletextspace);
+ fprintf(psfp, "exch sub\n");
+ fprintf(psfp, "%f moveto\n", y);
+ fprintf(psfp, "show\n");
+}
+
+/*
+ * Print a string s in width w, escaping characters where necessary.
+ */
+
+static void
+EscapePrint(s,w)
+ char* s; int w;
+{
+ for ( ; *s && w > 0; s++, w--) {
+ if (*s == '(') { /* escape required */
+ fputc('\\', psfp);
+ } else if (*s == ')') {
+ fputc('\\', psfp);
+ }
+
+ fputc(*s, psfp);
+ }
+}
diff --git a/massif/hp2ps/PsFile.h b/massif/hp2ps/PsFile.h
new file mode 100644
index 0000000..acec070
--- /dev/null
+++ b/massif/hp2ps/PsFile.h
@@ -0,0 +1,6 @@
+#ifndef PS_FILE_H
+#define PS_FILE_H
+
+void PutPsFile PROTO((void));
+
+#endif /* PS_FILE_H */
diff --git a/massif/hp2ps/README b/massif/hp2ps/README
new file mode 100644
index 0000000..f0f09ce
--- /dev/null
+++ b/massif/hp2ps/README
@@ -0,0 +1 @@
+This "hp2ps" program was written by Dave Wakeling at York.
diff --git a/massif/hp2ps/Reorder.c b/massif/hp2ps/Reorder.c
new file mode 100644
index 0000000..94bda2c
--- /dev/null
+++ b/massif/hp2ps/Reorder.c
@@ -0,0 +1,89 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "Main.h"
+#include "Defines.h"
+#include "Error.h"
+#include "HpFile.h"
+#include "Utilities.h"
+
+/* own stuff */
+#include "Reorder.h"
+
+static struct order {
+ char* ident;
+ int order;
+} *ordermap = 0;
+
+static int ordermapmax = 0;
+static int ordermapindex = 0;
+
+
+void
+OrderFor(ident, order)
+ char* ident;
+ int order;
+{
+ if (! ordermap) {
+ ordermapmax = (nidents > TWENTY ? nidents : TWENTY) * 2;
+ /* Assume nidents read is indication of the No of
+ idents in the .aux file (*2 for good luck !) */
+ ordermap = xmalloc(ordermapmax * sizeof(struct order));
+ }
+
+ if (ordermapindex < ordermapmax) {
+ ordermap[ ordermapindex ].ident = copystring(ident);
+ ordermap[ ordermapindex ].order = order;
+ ordermapindex++;
+ } else {
+ Disaster("order map overflow");
+ }
+}
+
+/*
+ * Get the order of to be used for "ident" if there is one.
+ * Otherwise, return 0 which is the minimum ordering value.
+ */
+
+int
+OrderOf(ident)
+ char* ident;
+{
+ int i;
+
+ for (i = 0; i < ordermapindex; i++) {
+ if (strcmp(ordermap[i].ident, ident) == 0) { /* got it */
+ return(ordermap[i].order);
+ }
+ }
+
+ return 0;
+}
+
+/*
+ * Reorder on the basis of information from ".aux" file.
+ */
+
+void
+Reorder()
+{
+ intish i;
+ intish j;
+ int min;
+ struct entry* e;
+ int o1, o2;
+
+ for (i = 0; i < nidents-1; i++) {
+ min = i;
+ for (j = i+1; j < nidents; j++) {
+ o1 = OrderOf(identtable[ j ]->name);
+ o2 = OrderOf(identtable[ min ]->name);
+
+ if (o1 < o2 ) min = j;
+ }
+
+ e = identtable[ min ];
+ identtable[ min ] = identtable[ i ];
+ identtable[ i ] = e;
+ }
+}
diff --git a/massif/hp2ps/Reorder.h b/massif/hp2ps/Reorder.h
new file mode 100644
index 0000000..089ef75
--- /dev/null
+++ b/massif/hp2ps/Reorder.h
@@ -0,0 +1,8 @@
+#ifndef REORDER_H
+#define REORDER_H
+
+void Reorder PROTO((void));
+int OrderOf PROTO((char *));
+void OrderFor PROTO((char *, int));
+
+#endif /* REORDER_H */
diff --git a/massif/hp2ps/Scale.c b/massif/hp2ps/Scale.c
new file mode 100644
index 0000000..576e173
--- /dev/null
+++ b/massif/hp2ps/Scale.c
@@ -0,0 +1,87 @@
+#include <stdio.h>
+#include "Main.h"
+#include "Defines.h"
+#include "Dimensions.h"
+#include "Error.h"
+#include "HpFile.h"
+#include "Utilities.h"
+
+/* own stuff */
+#include "Scale.h"
+
+/*
+ * Return the maximum combined height that all the sample
+ * curves will reach. This (absolute) figure can then be
+ * used to scale the samples automatically so that they
+ * fit on the page.
+ */
+
+extern void free();
+
+floatish
+MaxCombinedHeight()
+{
+ intish i;
+ intish j;
+ floatish mx;
+ int bucket;
+ floatish value;
+ struct chunk* ch;
+ floatish *maxima;
+
+ maxima = (floatish*) xmalloc(nsamples * sizeof(floatish));
+ for (i = 0; i < nsamples; i++) {
+ maxima[ i ] = 0.0;
+ }
+
+ for (i = 0; i < nidents; i++) {
+ for (ch = identtable[i]->chk; ch; ch = ch->next) {
+ for (j = 0; j < ch->nd; j++) {
+ bucket = ch->d[j].bucket;
+ value = ch->d[j].value;
+ if (bucket >= nsamples)
+ Disaster("bucket out of range");
+ maxima[ bucket ] += value;
+ }
+ }
+ }
+
+ for (mx = maxima[ 0 ], i = 0; i < nsamples; i++) {
+ if (maxima[ i ] > mx) mx = maxima[ i ];
+ }
+
+ free(maxima);
+ return mx;
+}
+
+
+
+/*
+ * Scale the values from the samples so that they will fit on
+ * the page.
+ */
+
+extern floatish xrange;
+extern floatish yrange;
+
+void
+Scale()
+{
+ intish i;
+ intish j;
+ floatish sf;
+ struct chunk* ch;
+
+ if (yrange == 0.0) /* no samples */
+ return;
+
+ sf = graphheight / yrange;
+
+ for (i = 0; i < nidents; i++) {
+ for (ch = identtable[i]->chk; ch; ch = ch->next) {
+ for (j = 0; j < ch->nd; j++) {
+ ch->d[j].value = ch->d[j].value * sf;
+ }
+ }
+ }
+}
diff --git a/massif/hp2ps/Scale.h b/massif/hp2ps/Scale.h
new file mode 100644
index 0000000..0c19d6c
--- /dev/null
+++ b/massif/hp2ps/Scale.h
@@ -0,0 +1,7 @@
+#ifndef SCALE_H
+#define SCALE_H
+
+floatish MaxCombinedHeight PROTO((void));
+void Scale PROTO((void));
+
+#endif /* SCALE_H */
diff --git a/massif/hp2ps/Shade.c b/massif/hp2ps/Shade.c
new file mode 100644
index 0000000..2920fb6
--- /dev/null
+++ b/massif/hp2ps/Shade.c
@@ -0,0 +1,130 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "Main.h"
+#include "Defines.h"
+#include "Error.h"
+#include "Utilities.h"
+
+/* own stuff */
+#include "Shade.h"
+
+static struct shade {
+ char* ident;
+ floatish shade;
+} *shademap;
+
+static int shademapmax = 0;
+static int shademapindex = 0;
+
+/*
+ * Set the shade to be used for "ident" to "shade".
+ */
+
+void
+ShadeFor(ident, shade)
+ char* ident;
+ floatish shade;
+{
+ if (! shademap) {
+ shademapmax = (nidents > TWENTY ? nidents : TWENTY) * 2;
+ /* Assume nidents read is indication of the No of
+ idents in the .aux file (*2 for good luck) */
+ /* NB *2 is needed as .aux and .hp elements may differ */
+ shademap = xmalloc(shademapmax * sizeof(struct shade));
+ }
+
+ if (shademapindex < shademapmax) {
+ shademap[ shademapindex ].ident = copystring(ident);
+ shademap[ shademapindex ].shade = shade;
+ shademapindex++;
+ } else {
+ Disaster("shade map overflow");
+ }
+}
+
+/*
+ * Get the shade to be used for "ident" if there is one.
+ * Otherwise, think of a new one.
+ */
+
+static floatish ThinkOfAShade PROTO((void)); /* forward */
+
+floatish
+ShadeOf(ident)
+ char* ident;
+{
+ int i;
+ floatish shade;
+
+ for (i = 0; i < shademapindex; i++) {
+ if (strcmp(shademap[i].ident, ident) == 0) { /* got it */
+ return(shademap[i].shade);
+ }
+ }
+
+ shade = ThinkOfAShade();
+
+ ShadeFor(ident, shade);
+
+ return shade;
+}
+
+
+
+#define N_MONO_SHADES 10
+
+static floatish m_shades[ N_MONO_SHADES ] = {
+ 0.00000, 0.20000, 0.60000, 0.30000, 0.90000,
+ 0.40000, 1.00000, 0.70000, 0.50000, 0.80000
+};
+
+#define N_COLOUR_SHADES 27
+
+/* HACK: 0.100505 means 100% red, 50% green, 50% blue */
+
+static floatish c_shades[ N_COLOUR_SHADES ] = {
+ 0.000000, 0.000010, 0.001000, 0.001010, 0.100000,
+ 0.100010, 0.101000, 0.101010, 0.000005, 0.000500,
+ 0.000510, 0.001005, 0.050000, 0.050010, 0.051000,
+ 0.051010, 0.100005, 0.100500, 0.100510, 0.101005,
+ 0.000505, 0.050005, 0.050500, 0.050510, 0.051005,
+ 0.100505, 0.050505
+};
+
+static floatish
+ThinkOfAShade()
+{
+ static int thisshade = -1;
+
+ thisshade++;
+ return cflag ?
+ c_shades[ thisshade % N_COLOUR_SHADES ] :
+ m_shades[ thisshade % N_MONO_SHADES ] ;
+}
+
+static floatish
+extract_colour(shade,factor)
+ floatish shade;
+ intish factor;
+{
+ intish i,j;
+
+ i = (int)(shade * factor);
+ j = i / 100;
+ return (i - j * 100) / 10.0;
+}
+
+void
+SetPSColour(shade)
+ floatish shade;
+{
+ if (cflag) {
+ fprintf(psfp, "%f %f %f setrgbcolor\n",
+ extract_colour(shade, (intish)100),
+ extract_colour(shade, (intish)10000),
+ extract_colour(shade, (intish)1000000));
+ } else {
+ fprintf(psfp, "%f setgray\n", shade);
+ }
+}
diff --git a/massif/hp2ps/Shade.h b/massif/hp2ps/Shade.h
new file mode 100644
index 0000000..0e49c90
--- /dev/null
+++ b/massif/hp2ps/Shade.h
@@ -0,0 +1,8 @@
+#ifndef SHADE_H
+#define SHADE_H
+
+floatish ShadeOf PROTO((char *));
+void ShadeFor PROTO((char *, floatish));
+void SetPSColour PROTO((floatish));
+
+#endif /* SHADE_H */
diff --git a/massif/hp2ps/TopTwenty.c b/massif/hp2ps/TopTwenty.c
new file mode 100644
index 0000000..9060aaf
--- /dev/null
+++ b/massif/hp2ps/TopTwenty.c
@@ -0,0 +1,73 @@
+#include <stdio.h>
+#include "Main.h"
+#include "Defines.h"
+#include "Error.h"
+#include "HpFile.h"
+#include "Utilities.h"
+
+/* own stuff */
+#include "TopTwenty.h"
+
+/*
+ * We only have room in the key for a maximum of 20 identifiers.
+ * We therefore choose to keep the top 20 bands --- these will
+ * be the most important ones, since this pass is performed after
+ * the threshold and standard deviation passes. If there are more
+ * than 20 bands, the excess are gathered together as an "OTHER" ]
+ * band which appears as band 20.
+ */
+
+extern void free();
+
+void
+TopTwenty()
+{
+ intish i;
+ intish j;
+ intish compact;
+ intish bucket;
+ floatish value;
+ struct entry* en;
+ struct chunk* ch;
+ floatish *other;
+
+ i = nidents;
+ if (i <= TWENTY) return; /* nothing to do! */
+
+ other = (floatish*) xmalloc(nsamples * sizeof(floatish));
+ /* build a list of samples for "OTHER" */
+
+ compact = (i - TWENTY) + 1;
+
+ for (i = 0; i < nsamples; i++) {
+ other[ i ] = 0.0;
+ }
+
+ for (i = 0; i < compact && i < nidents; i++) {
+ for (ch = identtable[i]->chk; ch; ch = ch->next) {
+ for (j = 0; j < ch->nd; j++) {
+ bucket = ch->d[j].bucket;
+ value = ch->d[j].value;
+ if (bucket >= nsamples)
+ Disaster("bucket out of range");
+ other[ bucket ] += value;
+ }
+ }
+ }
+
+ en = MakeEntry("OTHER");
+ en->next = 0;
+
+ for (i = 0; i < nsamples; i++) {
+ StoreSample(en, i, other[i]);
+ }
+
+ /* slide samples down */
+ for (i = compact; i < nidents; i++) {
+ identtable[i-compact+1] = identtable[i];
+ }
+
+ nidents = TWENTY;
+ identtable[0] = en;
+ free(other);
+}
diff --git a/massif/hp2ps/TopTwenty.h b/massif/hp2ps/TopTwenty.h
new file mode 100644
index 0000000..53a7aed
--- /dev/null
+++ b/massif/hp2ps/TopTwenty.h
@@ -0,0 +1,6 @@
+#ifndef TOP_TWENTY_H
+#define TOP_TWENTY_H
+
+void TopTwenty PROTO((void));
+
+#endif /* TOP_TWENTY_H */
diff --git a/massif/hp2ps/TraceElement.c b/massif/hp2ps/TraceElement.c
new file mode 100644
index 0000000..984faf5
--- /dev/null
+++ b/massif/hp2ps/TraceElement.c
@@ -0,0 +1,97 @@
+#include <stdio.h>
+#include "Main.h"
+#include "Defines.h"
+#include "HpFile.h"
+#include "Error.h"
+#include "Utilities.h"
+
+/* own stuff */
+#include "TraceElement.h"
+
+/*
+ * Compute the total volume for each identifier, and the grand
+ * total of these totals. The identifiers whose totals when
+ * added together amount to less that a threshold percentage
+ * (default 1%) of the grand total are considered to be ``trace
+ * elements'' and they are thrown away.
+ */
+
+extern void free();
+
+extern floatish thresholdpercent;
+
+void TraceElement()
+{
+ intish i;
+ intish j;
+ struct chunk* ch;
+ floatish grandtotal;
+ intish min;
+ floatish t;
+ floatish p;
+ struct entry* e;
+ intish *totals;
+
+ totals = (intish *) xmalloc(nidents * sizeof(intish));
+
+ /* find totals */
+
+ for (i = 0; i < nidents; i++) {
+ totals[ i ] = 0;
+ }
+
+ for (i = 0; i < nidents; i++) {
+ for (ch = identtable[i]->chk; ch; ch = ch->next) {
+ for (j = 0; j < ch->nd; j++) {
+ totals[ i ] += ch->d[j].value;
+ }
+ }
+ }
+
+ /* sort on the basis of total */
+
+ for (i = 0; i < nidents-1; i++) {
+ min = i;
+ for (j = i+1; j < nidents; j++) {
+ if (totals[ j ] < totals[ min ]) {
+ min = j;
+ }
+ }
+
+ t = totals[ min ];
+ totals[ min ] = totals[ i ];
+ totals[ i ] = t;
+
+ e = identtable[ min ];
+ identtable[ min ] = identtable[ i ];
+ identtable[ i ] = e;
+ }
+
+
+ /* find the grand total (NB: can get *BIG*!) */
+
+ grandtotal = 0.0;
+
+ for (i = 0; i < nidents; i++) {
+ grandtotal += (floatish) totals[ i ];
+ }
+
+ t = 0.0; /* cumulative percentage */
+
+ for (i = 0; i < nidents; i++) {
+ p = (100.0 * (floatish) totals[i]) / grandtotal;
+ t = t + p;
+ if (t >= THRESHOLD_PERCENT) {
+ break;
+ }
+ }
+
+ /* identifiers from 0 to i-1 should be removed */
+ for (j = 0; i < nidents; i++, j++) {
+ identtable[j] = identtable[i];
+ }
+
+ nidents = j;
+
+ free(totals);
+}
diff --git a/massif/hp2ps/TraceElement.h b/massif/hp2ps/TraceElement.h
new file mode 100644
index 0000000..d843392
--- /dev/null
+++ b/massif/hp2ps/TraceElement.h
@@ -0,0 +1,6 @@
+#ifndef TRACE_ELEMENT_H
+#define TRACE_ELEMENT_H
+
+void TraceElement PROTO((void));
+
+#endif /* TRACE_ELEMENT_H */
diff --git a/massif/hp2ps/Utilities.c b/massif/hp2ps/Utilities.c
new file mode 100644
index 0000000..57d20b1
--- /dev/null
+++ b/massif/hp2ps/Utilities.c
@@ -0,0 +1,132 @@
+#include <stdio.h>
+#include <string.h>
+#include "Main.h"
+#include "Error.h"
+
+extern void* malloc();
+
+char*
+Basename(name)
+ char* name;
+{
+ char* t;
+
+ t = name;
+
+ while (*name) {
+ if (*name == '/') {
+ t = name+1;
+ }
+ name++;
+ }
+
+ return t;
+}
+
+void
+DropSuffix(name, suffix)
+ char* name; char* suffix;
+{
+ char* t;
+
+ t = (char*) 0;
+
+ while (*name) {
+ if (*name == '.') {
+ t = name;
+ }
+ name++;
+ }
+
+ if (t != (char*) 0 && strcmp(t, suffix) == 0) {
+ *t = '\0';
+ }
+}
+
+FILE*
+OpenFile(s, mode)
+ char* s; char* mode;
+{
+ FILE* r;
+
+ if ((r = fopen(s, mode)) == NULL) {
+ /*NOTREACHED*/
+ Error("cannot open %s", s);
+ }
+
+ return r;
+}
+
+
+#define ONETHOUSAND 1000
+
+/*
+ * Print a positive integer with commas
+ */
+
+void
+CommaPrint(fp,n)
+ FILE* fp;
+ intish n;
+{
+ if (n < ONETHOUSAND) {
+ fprintf(fp, "%d", (int)n);
+ } else {
+ CommaPrint(fp, n / ONETHOUSAND);
+ fprintf(fp, ",%03d", (int)n % ONETHOUSAND);
+ }
+}
+
+void *
+xmalloc(n)
+ int n;
+{
+ void *r;
+
+ r = (void*) malloc(n);
+ if (!r) {
+ /*NOTREACHED*/
+ Disaster("%s, sorry, out of memory", hpfile);
+ }
+ return r;
+}
+
+void *
+xrealloc(p, n)
+ void *p;
+ int n;
+{
+ void *r;
+ extern void *realloc();
+
+ r = realloc(p, n);
+ if (!r) {
+ /*NOTREACHED*/
+ Disaster("%s, sorry, out of memory", hpfile);
+ }
+ return r;
+}
+
+char *
+copystring(s)
+ char *s;
+{
+ char *r;
+
+ r = (char*) xmalloc(strlen(s)+1);
+ strcpy(r, s);
+ return r;
+}
+
+char *
+copystring2(s, t)
+ char *s, *t;
+{
+ char *r;
+
+ r = (char*) xmalloc(strlen(s)+strlen(t)+1);
+ strcpy(r, s);
+ strcat(r, t);
+ return r;
+}
+
diff --git a/massif/hp2ps/Utilities.h b/massif/hp2ps/Utilities.h
new file mode 100644
index 0000000..bffc87d
--- /dev/null
+++ b/massif/hp2ps/Utilities.h
@@ -0,0 +1,13 @@
+#ifndef UTILITIES_H
+#define UTILITIES_H
+
+char* Basename PROTO((char *));
+void DropSuffix PROTO((char *, char *));
+FILE* OpenFile PROTO((char *, char *));
+void CommaPrint PROTO((FILE *, intish));
+char *copystring PROTO((char *));
+char *copystring2 PROTO((char *, char *));
+void *xmalloc PROTO((int));
+void *xrealloc PROTO((void *, int));
+
+#endif /* UTILITIES_H */
diff --git a/massif/hp2ps/hp2ps.1 b/massif/hp2ps/hp2ps.1
new file mode 100644
index 0000000..fd0bca0
--- /dev/null
+++ b/massif/hp2ps/hp2ps.1
@@ -0,0 +1,145 @@
+.\" man page for hp2ps
+.ds PS P\s-2OST\s+2S\s-2CRIPT\s+2
+.\" typeset examples in fixed size font as indented paragraph
+.de Ex
+.sp
+.RS
+.nf
+.ft C
+..
+.de Xe
+.RE
+.sp
+.fi
+..
+.TH HP2PS 1 "18 April 1992"
+.SH NAME
+hp2ps \- convert a heap profile to a \*(PS graph
+.SH SYNOPSIS
+.B hp2ps
+[flags] [file][.hp]
+.SH DESCRIPTION
+The program
+.B hp2ps
+converts a heap profile stored in
+.IR file
+into a \*(PS graph, sending the result to
+.IR file.ps.
+By convention, files to be processed by
+.B hp2ps
+have a
+.I .hp
+extension. However, for compatibility with older versions of
+.B hp2ps,
+this extension can be omitted. If
+.IR file
+is omitted entirely, then the program behaves as a filter.
+.SH OPTIONS
+The flags are:
+.IP "\fB\-d\fP"
+In order to make graphs more readable,
+.B hp2ps
+sorts the shaded bands for each identifier. The default sort ordering is for
+the bands with the largest area to be stacked on top of the smaller ones.
+The
+.B \-d
+option causes rougher bands (those reprsenting series of values with the
+largest standard deviations) to be stacked on top of smoother ones.
+.IP "\fB\-b\fP"
+Normally,
+.B hp2ps
+puts the title of the graph in a small box at the top of the page. However,
+if the JOB string is too long to fit in a small box (more than 35 characters),
+then
+.B hp2ps
+will choose to use a big box instead. The
+.B \-b
+option forces
+.B hp2ps
+to use a big box.
+.IP "\fB\-e\fP \fIfloat\fP[in|mm|pt]"
+Generate encapsulated \*(PS suitable for inclusion in LaTeX documents.
+Usually, the \*(PS graph is drawn in landscape mode in an area
+9 inches wide by 6 inches high, and
+.B hp2ps
+arranges for this area to be approximately centered on a sheet of a4
+paper. This format is convenient of studying the graph in detail, but
+it is unsuitable for inclusion in LaTeX documents. The
+.B \-e
+option causes the graph to be drawn in portrait mode, with
+.I float
+specifying the width in inches, millimetres or points (the default).
+The resulting \*(PS file conforms to the
+.I "Encapsulated Post Script"
+(EPS) convention, and it can be included in a LaTeX document using Rokicki's
+dvi-to-\*(PS converter
+.B dvips.
+.B hp2ps
+requires the width to exceed 2 inches.
+.IP "\fB\-g\fP"
+Create output suitable for the
+.B gs
+\*(PS previewer (or similar). In this case the graph is printed in portrait
+mode without scaling. The output is unsuitable for a laser printer.
+.IP "\fB\-p\fP"
+Use previous parameters. By default, the \*(PS graph is automatically
+scaled both horizontally and vertically so that it fills the page.
+However, when preparing a seires of graphs for use in a presentation,
+it is often useful to draw a new graph using the same scale, shading and
+ordering as a previous one. The
+.B \-p
+flag causes the graph to be drawn using the parameters determined by
+a previous run of
+.B hp2ps
+on
+.IR file.
+.IP "\fB\-s\fP"
+Use a small box for the title.
+.IP "\fB\-y\fP"
+Draw the graph in the traditional York style, ignoring marks.
+.IP "\fB\-?\fP"
+Print out usage information.
+.SH "INPUT FORMAT"
+The format of a heap profile is best described by example:
+.Ex
+JOB "a.out -p"
+DATE "Fri Apr 17 11:43:45 1992"
+SAMPLE_UNIT "seconds"
+VALUE_UNIT "bytes"
+BEGIN_SAMPLE 0.00
+ SYSTEM 24
+END_SAMPLE 0.00
+BEGIN_SAMPLE 1.00
+ elim 180
+ insert 24
+ intersect 12
+ disin 60
+ main 12
+ reduce 20
+ SYSTEM 12
+END_SAMPLE 1.00
+MARK 1.50
+MARK 1.75
+MARK 1.80
+BEGIN_SAMPLE 2.00
+ elim 192
+ insert 24
+ intersect 12
+ disin 84
+ main 12
+ SYSTEM 24
+END_SAMPLE 2.00
+BEGIN_SAMPLE 2.82
+END_SAMPLE 2.82
+
+.Xe
+.SH "SEE ALSO"
+dvips(1), latex(1), hbchp (1), lmlchp(1)
+.br
+C. Runciman and D. Wakeling,
+.I
+Heap Profiling for Lazy Functional Languages, YCS-172, University of York, 1992
+.SH NOTES
+\*(PS is a registered trademark of Adobe Systems Incorporated.
+.SH AUTHOR
+David Wakeling of the University of York.
diff --git a/massif/ms_main.c b/massif/ms_main.c
new file mode 100644
index 0000000..54c4cce
--- /dev/null
+++ b/massif/ms_main.c
@@ -0,0 +1,1815 @@
+
+/*--------------------------------------------------------------------*/
+/*--- Massif: a heap profiling skin. ms_main.c ---*/
+/*--------------------------------------------------------------------*/
+
+/*
+ This file is part of Massif, a Valgrind skin for profiling memory
+ usage of programs.
+
+ Copyright (C) 2003 Nicholas Nethercote
+ njn25@cam.ac.uk
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License as
+ published by the Free Software Foundation; either version 2 of the
+ License, or (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+ 02111-1307, USA.
+
+ The GNU General Public License is contained in the file COPYING.
+*/
+
+// Memory profiler. Produces a graph, gives lots of information about
+// allocation contexts, in terms of space.time values (ie. area under the
+// graph). Allocation context information is hierarchical, and can thus
+// be inspected step-wise to an appropriate depth. See comments on data
+// structures below for more info on how things work.
+
+#include "vg_skin.h"
+//#include "vg_profile.c"
+
+#include "valgrind.h" // For {MALLOC,FREE}LIKE_BLOCK
+
+/*------------------------------------------------------------*/
+/*--- Overview of operation ---*/
+/*------------------------------------------------------------*/
+
+// Heap blocks are tracked, and the amount of space allocated by various
+// contexts (ie. lines of code, more or less) is also tracked.
+// Periodically, a census is taken, and the amount of space used, at that
+// point, by the most significant (highly allocating) contexts is recorded.
+// Census start off frequently, but are scaled back as the program goes on,
+// so that there are always a good number of them. At the end, overall
+// spacetimes for different contexts (of differing levels of precision) is
+// calculated, the graph is printed, and the text giving spacetimes for the
+// increasingly precise contexts is given.
+//
+// Measures the following:
+// - heap blocks
+// - heap admin bytes
+// - stack(s)
+// - code (code segments loaded at startup, and loaded with mmap)
+// - data (data segments loaded at startup, and loaded/created with mmap,
+// and brk()d segments)
+
+/*------------------------------------------------------------*/
+/*--- Main types ---*/
+/*------------------------------------------------------------*/
+
+// An XPt represents an "execution point", ie. a code address. Each XPt is
+// part of a tree of XPts (an "execution tree", or "XTree"). Each
+// top-to-bottom path through an XTree gives an execution context ("XCon"),
+// and is equivalent to a traditional Valgrind ExeContext.
+//
+// The XPt at the top of an XTree (but below "alloc_xpt") is called a
+// "top-XPt". The XPts are the bottom of an XTree (leaf nodes) are
+// "bottom-XPTs". The number of XCons in an XTree is equal to the number of
+// bottom-XPTs in that XTree.
+//
+// All XCons have the same top-XPt, "alloc_xpt", which represents all
+// allocation functions like malloc(). It's a bit of a fake XPt, though,
+// and is only used because it makes some of the code simpler.
+//
+// XTrees are bi-directional.
+//
+// > parent < Example: if child1() calls parent() and child2()
+// / | \ also calls parent(), and parent() calls malloc(),
+// | / \ | the XTree will look like this.
+// | v v |
+// child1 child2
+
+typedef struct _XPt XPt;
+
+struct _XPt {
+ Addr eip; // code address
+
+ // Bottom-XPts: space for the precise context.
+ // Other XPts: space of all the descendent bottom-XPts.
+ // Nb: this value goes up and down as the program executes.
+ UInt curr_space;
+
+ // An approximate space.time calculation used along the way for selecting
+ // which contexts to include at each census point.
+ // !!! top-XPTs only !!!
+ ULong spacetime;
+
+ // spacetime2 is an exact space.time calculation done at the end, and
+ // used in the results.
+ // Note that it is *doubled*, to avoid rounding errors.
+ // !!! not used for 'alloc_xpt' !!!
+ ULong spacetime2;
+
+ // n_children and max_children are integers; a very big program might
+ // have more than 65536 allocation points (Konqueror startup has 1800).
+ XPt* parent; // pointer to parent XPt
+ UInt n_children; // number of children
+ UInt max_children; // capacity of children array
+ XPt** children; // pointers to children XPts
+};
+
+// Each census snapshots the most significant XTrees, each XTree having a
+// top-XPt as its root. The 'curr_space' element for each XPt is recorded
+// in the snapshot. The snapshot contains all the XTree's XPts, not in a
+// tree structure, but flattened into an array. This flat snapshot is used
+// at the end for computing spacetime2 for each XPt.
+//
+// Graph resolution, x-axis: no point having more than about 200 census
+// x-points; you can't see them on the graph. Therefore:
+//
+// - do a census every 1 ms for first 200 --> 200, all (200 ms)
+// - halve (drop half of them) --> 100, every 2nd (200 ms)
+// - do a census every 2 ms for next 200 --> 200, every 2nd (400 ms)
+// - halve --> 100, every 4th (400 ms)
+// - do a census every 4 ms for next 400 --> 200, every 4th (800 ms)
+// - etc.
+//
+// This isn't exactly right, because we actually drop (N/2)-1 when halving,
+// but it shows the basic idea.
+
+#define MAX_N_CENSI 200 // Keep it even, for simplicity
+
+// Graph resolution, y-axis: hp2ps only draws the 19 biggest (in space-time)
+// bands, rest get lumped into OTHERS. I only print the top N
+// (cumulative-so-far space-time) at each point. N should be a bit bigger
+// than 19 in case the cumulative space-time doesn't fit with the eventual
+// space-time computed by hp2ps (but it should be close if the samples are
+// evenly spread, since hp2ps does an approximate per-band space-time
+// calculation that just sums the totals; ie. it assumes all samples are
+// the same distance apart).
+
+#define MAX_SNAPSHOTS 32
+
+typedef
+ struct {
+ XPt* xpt;
+ UInt space;
+ }
+ XPtSnapshot;
+
+// An XTree snapshot is stored as an array of of XPt snapshots.
+typedef XPtSnapshot* XTreeSnapshot;
+
+typedef
+ struct {
+ Int ms_time; // Int: must allow -1
+ XTreeSnapshot xtree_snapshots[MAX_SNAPSHOTS+1]; // +1 for zero-termination
+ UInt others_space;
+ UInt heap_admin_space;
+ UInt stacks_space;
+ }
+ Census;
+
+// Metadata for heap blocks. Each one contains a pointer to a bottom-XPt,
+// which is a foothold into the XCon at which it was allocated. From
+// HP_Chunks, XPt 'space' fields are incremented (at allocation) and
+// decremented (at deallocation).
+//
+// Nb: first two fields must match core's VgHashNode.
+typedef
+ struct _HP_Chunk {
+ struct _HP_Chunk* next;
+ Addr data; // Ptr to actual block
+ UInt size; // Size requested
+ XPt* where; // Where allocated; bottom-XPt
+ }
+ HP_Chunk;
+
+/*------------------------------------------------------------*/
+/*--- Profiling events ---*/
+/*------------------------------------------------------------*/
+
+typedef
+ enum {
+ VgpGetXPt = VgpFini+1,
+ VgpGetXPtSearch,
+ VgpCensus,
+ VgpCensusHeap,
+ VgpCensusSnapshot,
+ VgpCensusTreeSize,
+ VgpUpdateXCon,
+ VgpCalcSpacetime2,
+ VgpPrintHp,
+ VgpPrintXPts,
+ }
+ VgpSkinCC;
+
+/*------------------------------------------------------------*/
+/*--- Statistics ---*/
+/*------------------------------------------------------------*/
+
+// Konqueror startup, to give an idea of the numbers involved with a biggish
+// program, with default depth:
+//
+// depth=3 depth=40
+// - 310,000 allocations
+// - 300,000 frees
+// - 15,000 XPts 800,000 XPts
+// - 1,800 top-XPts
+
+static UInt n_xpts = 0;
+static UInt n_bot_xpts = 0;
+static UInt n_allocs = 0;
+static UInt n_zero_allocs = 0;
+static UInt n_frees = 0;
+static UInt n_children_reallocs = 0;
+static UInt n_snapshot_frees = 0;
+
+static UInt n_halvings = 0;
+static UInt n_real_censi = 0;
+static UInt n_fake_censi = 0;
+static UInt n_attempted_censi = 0;
+
+/*------------------------------------------------------------*/
+/*--- Globals ---*/
+/*------------------------------------------------------------*/
+
+#define FILENAME_LEN 256
+
+#define SPRINTF(zz_buf, fmt, args...) \
+ do { Int len = VG_(sprintf)(zz_buf, fmt, ## args); \
+ VG_(write)(fd, (void*)zz_buf, len); \
+ } while (0)
+
+#define BUF_LEN 1024 // general purpose
+static Char buf [BUF_LEN];
+static Char buf2[BUF_LEN];
+static Char buf3[BUF_LEN];
+
+static UInt sigstacks_space = 0; // Current signal stacks space sum
+
+static VgHashTable malloc_list = NULL; // HP_Chunks
+
+static UInt n_heap_blocks = 0;
+
+
+#define MAX_ALLOC_FNS 32 // includes the builtin ones
+
+// First six filled in, rest should be zeroed. argc/argv-style vector.
+static UInt n_alloc_fns = 8;
+static Char* alloc_fns[MAX_ALLOC_FNS] = {
+ "malloc",
+ "operator new(unsigned)",
+ "operator new[](unsigned)",
+ "__builtin_new",
+ "__builtin_vec_new",
+ "calloc",
+ "realloc",
+ "my_malloc", // from vg_libpthread.c
+};
+
+
+/*------------------------------------------------------------*/
+/*--- Command line args ---*/
+/*------------------------------------------------------------*/
+
+#define MAX_DEPTH 50
+
+typedef
+ enum {
+ XText, XHTML,
+ }
+ XFormat;
+
+static Bool clo_heap = True;
+static UInt clo_heap_admin = 8;
+static Bool clo_stacks = True;
+static Bool clo_depth = 3;
+static XFormat clo_format = XText;
+
+Bool SK_(process_cmd_line_option)(Char* arg)
+{
+ if (VG_CLO_STREQ(arg, "--heap=yes"))
+ clo_heap = True;
+ else if (VG_CLO_STREQ(arg, "--heap=no"))
+ clo_heap = False;
+
+ else if (VG_CLO_STREQN(13, arg, "--heap-admin=")) {
+ clo_heap_admin = (Int)VG_(atoll)(&arg[13]);
+ if (clo_heap_admin > 100) {
+ VG_(message)(Vg_UserMsg,
+ "Admin size for heap blocks too large");
+ VG_(bad_option)(arg);
+ }
+ }
+
+ else if (VG_CLO_STREQ(arg, "--stacks=yes"))
+ clo_stacks = True;
+ else if (VG_CLO_STREQ(arg, "--stacks=no"))
+ clo_stacks = False;
+
+ else if (VG_CLO_STREQN(8, arg, "--depth=")) {
+ clo_depth = (Int)VG_(atoll)(&arg[8]);
+ if (clo_depth < 1) clo_depth = 1;
+ if (clo_depth >= MAX_DEPTH) clo_depth = MAX_DEPTH;
+ }
+
+ else if (VG_CLO_STREQN(11, arg, "--alloc-fn=")) {
+ alloc_fns[n_alloc_fns] = & arg[11];
+ n_alloc_fns++;
+ if (n_alloc_fns >= MAX_ALLOC_FNS) {
+ VG_(printf)("Too many alloc functions specified, sorry");
+ VG_(bad_option)(arg);
+ }
+ }
+
+ else if (VG_CLO_STREQ(arg, "--format=text"))
+ clo_format = XText;
+ else if (VG_CLO_STREQ(arg, "--format=html"))
+ clo_format = XHTML;
+
+ else
+ return VG_(replacement_malloc_process_cmd_line_option)(arg);
+
+ return True;
+}
+
+void SK_(print_usage)(void)
+{
+ VG_(printf)(
+" --heap=no|yes profile heap blocks [yes]\n"
+" --heap-admin=<number> average admin bytes per heap block [8]\n"
+" --stacks=no|yes profile stack(s) [yes]\n"
+" --depth=<number> depth of contexts [3]\n"
+" --alloc-fn=<name> specify <fn> as an alloc function [empty]\n"
+" --format=text|html format of textual output [text]\n"
+ );
+ VG_(replacement_malloc_print_usage)();
+}
+
+void SK_(print_debug_usage)(void)
+{
+ VG_(replacement_malloc_print_debug_usage)();
+}
+
+/*------------------------------------------------------------*/
+/*--- Execution contexts ---*/
+/*------------------------------------------------------------*/
+
+// Fake XPt representing all allocation functions like malloc(). Acts as
+// parent node to all top-XPts.
+static XPt* alloc_xpt;
+
+// Cheap allocation for blocks that never need to be freed. Saves about 10%
+// for Konqueror startup with --depth=40.
+static void* perm_malloc(UInt n_bytes)
+{
+ static Addr hp = 0; // current heap pointer
+ static Addr hp_lim = 0; // maximum usable byte in current block
+
+ #define SUPERBLOCK_SIZE (1 << 20) // 1 MB
+
+ if (hp + n_bytes > hp_lim) {
+ hp = (Addr)VG_(get_memory_from_mmap)(SUPERBLOCK_SIZE, "perm_malloc");
+ hp_lim = hp + SUPERBLOCK_SIZE - 1;
+ }
+
+ hp += n_bytes;
+
+ return (void*)(hp - n_bytes);
+}
+
+
+
+static XPt* new_XPt(Addr eip, XPt* parent, Bool is_bottom)
+{
+ XPt* xpt = perm_malloc(sizeof(XPt));
+ xpt->eip = eip;
+
+ xpt->curr_space = 0;
+ xpt->spacetime = 0;
+ xpt->spacetime2 = 0;
+
+ xpt->parent = parent;
+ sk_assert(parent == NULL || 0xffffffff != parent->eip);
+
+ xpt->n_children = 0;
+
+ // If a bottom-XPt, don't allocate space for children. This can be 50%
+ // or more, although it tends to drop as --depth increases (eg. 10% for
+ // konqueror with --depth=20).
+ if ( is_bottom ) {
+ xpt->max_children = 0;
+ xpt->children = NULL;
+ n_bot_xpts++;
+ } else {
+ xpt->max_children = 4;
+ xpt->children = VG_(malloc)( xpt->max_children * sizeof(XPt*) );
+ }
+
+ // Update statistics
+ n_xpts++;
+
+ return xpt;
+}
+
+static Bool is_alloc_fn(Addr eip)
+{
+ Int i;
+
+ if ( VG_(get_fnname)(eip, buf, BUF_LEN) ) {
+ for (i = 0; i < n_alloc_fns; i++) {
+ if (VG_STREQ(buf, alloc_fns[i]))
+ return True;
+ }
+ }
+ return False;
+}
+
+// Returns an XCon, from the bottom-XPt. Nb: the XPt returned must be a
+// bottom-XPt now and must always remain a bottom-XPt. We go to some effort
+// to ensure this in certain cases. See comments below.
+static XPt* get_XCon( ThreadId tid, Bool custom_malloc )
+{
+ // Static to minimise stack size. +1 for added 0xffffffff %eip.
+ static Addr eips[MAX_DEPTH + MAX_ALLOC_FNS + 1];
+
+ XPt* xpt = alloc_xpt;
+ UInt n_eips, L, A, B, nC;
+ UInt overestimate;
+ Bool reached_bottom;
+
+ VGP_PUSHCC(VgpGetXPt);
+
+ // Want at least clo_depth non-alloc-fn entries in the snapshot.
+ // However, because we have 1 or more (an unknown number, at this point)
+ // alloc-fns ignored, we overestimate the size needed for the stack
+ // snapshot. Then, if necessary, we repeatedly increase the size until
+ // it is enough.
+ overestimate = 2;
+ while (True) {
+ n_eips = VG_(stack_snapshot)( tid, eips, clo_depth + overestimate );
+
+ // Now we add a dummy "unknown" %eip at the end. This is only used if we
+ // run out of %eips before hitting clo_depth. It's done to ensure the
+ // XPt we return is (now and forever) a bottom-XPt. If the returned XPt
+ // wasn't a bottom-XPt (now or later) it would cause problems later (eg.
+ // the parent's spacetime wouldn't be equal to the total of the
+ // childrens' spacetimes).
+ eips[ n_eips++ ] = 0xffffffff;
+
+ // Skip over alloc functions in eips[].
+ for (L = 0; is_alloc_fn(eips[L]) && L < n_eips; L++) { }
+
+ // Must be at least one alloc function, unless client used
+ // MALLOCLIKE_BLOCK
+ if (!custom_malloc) sk_assert(L > 0);
+
+ // Should be at least one non-alloc function. If not, try again.
+ if (L == n_eips) {
+ overestimate += 2;
+ if (overestimate > MAX_ALLOC_FNS)
+ VG_(skin_panic)("No stk snapshot big enough to find non-alloc fns");
+ } else {
+ break;
+ }
+ }
+ A = L;
+ B = n_eips - 1;
+ reached_bottom = False;
+
+ // By this point, the eips we care about are in eips[A]..eips[B]
+
+ // Now do the search/insertion of the XCon. 'L' is the loop counter,
+ // being the index into eips[].
+ while (True) {
+ // Look for %eip in xpt's children.
+ // XXX: linear search, ugh -- about 10% of time for konqueror startup
+ // XXX: tried cacheing last result, only hit about 4% for konqueror
+ // Nb: this search hits about 98% of the time for konqueror
+ VGP_PUSHCC(VgpGetXPtSearch);
+
+ // If we've searched/added deep enough, or run out of EIPs, this is
+ // the bottom XPt.
+ if (L - A + 1 == clo_depth || L == B)
+ reached_bottom = True;
+
+ nC = 0;
+ while (True) {
+ if (nC == xpt->n_children) {
+ // not found, insert new XPt
+ sk_assert(xpt->max_children != 0);
+ sk_assert(xpt->n_children <= xpt->max_children);
+ // Expand 'children' if necessary
+ if (xpt->n_children == xpt->max_children) {
+ xpt->max_children *= 2;
+ xpt->children = VG_(realloc)( xpt->children,
+ xpt->max_children * sizeof(XPt*) );
+ n_children_reallocs++;
+ }
+ // Make new XPt for %eip, insert in list
+ xpt->children[ xpt->n_children++ ] =
+ new_XPt(eips[L], xpt, reached_bottom);
+ break;
+ }
+ if (eips[L] == xpt->children[nC]->eip) break; // found the %eip
+ nC++; // keep looking
+ }
+ VGP_POPCC(VgpGetXPtSearch);
+
+ // Return found/built bottom-XPt.
+ if (reached_bottom) {
+ sk_assert(0 == xpt->children[nC]->n_children); // Must be bottom-XPt
+ VGP_POPCC(VgpGetXPt);
+ return xpt->children[nC];
+ }
+
+ // Descend to next level in XTree, the newly found/built non-bottom-XPt
+ xpt = xpt->children[nC];
+ L++;
+ }
+}
+
+// Update 'curr_space' of every XPt in the XCon, by percolating upwards.
+static void update_XCon(XPt* xpt, Int space_delta)
+{
+ VGP_PUSHCC(VgpUpdateXCon);
+
+ sk_assert(True == clo_heap);
+ sk_assert(0 != space_delta);
+ sk_assert(NULL != xpt);
+ sk_assert(0 == xpt->n_children); // must be bottom-XPt
+
+ while (xpt != alloc_xpt) {
+ if (space_delta < 0) sk_assert(xpt->curr_space >= -space_delta);
+ xpt->curr_space += space_delta;
+ xpt = xpt->parent;
+ }
+ if (space_delta < 0) sk_assert(alloc_xpt->curr_space >= -space_delta);
+ alloc_xpt->curr_space += space_delta;
+
+ VGP_POPCC(VgpUpdateXCon);
+}
+
+// Actually want a reverse sort, biggest to smallest
+static Int XPt_cmp_spacetime(void* n1, void* n2)
+{
+ XPt* xpt1 = *(XPt**)n1;
+ XPt* xpt2 = *(XPt**)n2;
+ return (xpt1->spacetime < xpt2->spacetime ? 1 : -1);
+}
+
+static Int XPt_cmp_spacetime2(void* n1, void* n2)
+{
+ XPt* xpt1 = *(XPt**)n1;
+ XPt* xpt2 = *(XPt**)n2;
+ return (xpt1->spacetime2 < xpt2->spacetime2 ? 1 : -1);
+}
+
+
+/*------------------------------------------------------------*/
+/*--- A generic Queue ---*/
+/*------------------------------------------------------------*/
+
+typedef
+ struct {
+ UInt head; // Index of first entry
+ UInt tail; // Index of final+1 entry, ie. next free slot
+ UInt max_elems;
+ void** elems;
+ }
+ Queue;
+
+static Queue* construct_queue(UInt size)
+{
+ UInt i;
+ Queue* q = VG_(malloc)(sizeof(Queue));
+ q->head = 0;
+ q->tail = 0;
+ q->max_elems = size;
+ q->elems = VG_(malloc)(size * sizeof(void*));
+ for (i = 0; i < size; i++)
+ q->elems[i] = NULL;
+
+ return q;
+}
+
+static void destruct_queue(Queue* q)
+{
+ VG_(free)(q->elems);
+ VG_(free)(q);
+}
+
+static void shuffle(Queue* dest_q, void** old_elems)
+{
+ UInt i, j;
+ for (i = 0, j = dest_q->head; j < dest_q->tail; i++, j++)
+ dest_q->elems[i] = old_elems[j];
+ dest_q->head = 0;
+ dest_q->tail = i;
+ for ( ; i < dest_q->max_elems; i++)
+ dest_q->elems[i] = NULL; // paranoia
+}
+
+// Shuffles elements down. If not enough slots free, increase size. (We
+// don't wait until we've completely run out of space, because there could
+// be lots of shuffling just before that point which would be slow.)
+static void adjust(Queue* q)
+{
+ void** old_elems;
+
+ sk_assert(q->tail == q->max_elems);
+ if (q->head < 10) {
+ old_elems = q->elems;
+ q->max_elems *= 2;
+ q->elems = VG_(malloc)(q->max_elems * sizeof(void*));
+ shuffle(q, old_elems);
+ VG_(free)(old_elems);
+ } else {
+ shuffle(q, q->elems);
+ }
+}
+
+static void enqueue(Queue* q, void* elem)
+{
+ if (q->tail == q->max_elems)
+ adjust(q);
+ q->elems[q->tail++] = elem;
+}
+
+static Bool is_empty_queue(Queue* q)
+{
+ return (q->head == q->tail);
+}
+
+static void* dequeue(Queue* q)
+{
+ if (is_empty_queue(q))
+ return NULL; // Queue empty
+ else
+ return q->elems[q->head++];
+}
+
+/*------------------------------------------------------------*/
+/*--- malloc() et al replacement wrappers ---*/
+/*------------------------------------------------------------*/
+
+static __inline__
+void add_HP_Chunk(HP_Chunk* hc)
+{
+ n_heap_blocks++;
+ VG_(HT_add_node) ( malloc_list, (VgHashNode*)hc );
+}
+
+static __inline__
+HP_Chunk* get_HP_Chunk(void* p, HP_Chunk*** prev_chunks_next_ptr)
+{
+ return (HP_Chunk*)VG_(HT_get_node) ( malloc_list, (UInt)p,
+ (VgHashNode***)prev_chunks_next_ptr );
+}
+
+static __inline__
+void remove_HP_Chunk(HP_Chunk* hc, HP_Chunk** prev_chunks_next_ptr)
+{
+ sk_assert(n_heap_blocks > 0);
+ n_heap_blocks--;
+ *prev_chunks_next_ptr = hc->next;
+}
+
+// Forward declaration
+static void hp_census(void);
+
+static __inline__
+void new_block_meta ( void* p, Int size, Bool custom_malloc )
+{
+ HP_Chunk* hc;
+
+ VGP_PUSHCC(VgpCliMalloc);
+
+ if (0 == size) n_zero_allocs++;
+
+ // Make new HP_Chunk node, add to malloclist
+ hc = VG_(malloc)(sizeof(HP_Chunk));
+ hc->size = size;
+ hc->data = (Addr)p;
+
+ if (clo_heap) {
+ hc->where = get_XCon( VG_(get_current_or_recent_tid)(), custom_malloc );
+ if (size != 0)
+ update_XCon(hc->where, size);
+ } else {
+ hc->where = NULL; // paranoia
+ }
+
+ add_HP_Chunk( hc );
+
+ hp_census(); // do a census!
+
+ VGP_POPCC(VgpCliMalloc);
+}
+
+static __inline__
+void* new_block ( Int size, UInt align, Bool is_zeroed )
+{
+ void* p;
+
+ if (size < 0) return NULL;
+
+ VGP_PUSHCC(VgpCliMalloc);
+
+ // Update statistics
+ n_allocs++;
+
+ p = VG_(cli_malloc)( align, size );
+ if (is_zeroed) VG_(memset)(p, 0, size);
+ new_block_meta(p, size, /*custom_malloc*/False);
+
+ VGP_POPCC(VgpCliMalloc);
+ return p;
+}
+
+static __inline__
+void die_block ( void* p, Bool custom_free )
+{
+ HP_Chunk* hc;
+ HP_Chunk** remove_handle;
+
+ VGP_PUSHCC(VgpCliMalloc);
+
+ // Update statistics
+ n_frees++;
+
+ hc = get_HP_Chunk ( p, &remove_handle );
+ if (hc == NULL)
+ return; // must have been a bogus free(), or p==NULL
+
+ sk_assert(hc->data == (Addr)p);
+
+ if (clo_heap && hc->size != 0)
+ update_XCon(hc->where, -hc->size);
+
+ // Actually free the heap block
+ if (!custom_free)
+ VG_(cli_free)( p );
+
+ // Remove HP_Chunk from malloclist, destroy
+ remove_HP_Chunk(hc, remove_handle);
+
+ hp_census(); // do a census!
+
+ VG_(free)( hc );
+ VGP_POPCC(VgpCliMalloc);
+}
+
+
+void* SK_(malloc) ( Int n )
+{
+ return new_block( n, VG_(clo_alignment), /*is_zeroed*/False );
+}
+
+void* SK_(__builtin_new) ( Int n )
+{
+ return new_block( n, VG_(clo_alignment), /*is_zeroed*/False );
+}
+
+void* SK_(__builtin_vec_new) ( Int n )
+{
+ return new_block( n, VG_(clo_alignment), /*is_zeroed*/False );
+}
+
+void* SK_(calloc) ( Int m, Int size )
+{
+ return new_block( m*size, VG_(clo_alignment), /*is_zeroed*/True );
+}
+
+void SK_(free) ( void* p )
+{
+ die_block( p, /*custom_free*/False );
+}
+
+void SK_(__builtin_delete) ( void* p )
+{
+ die_block( p, /*custom_free*/False);
+}
+
+void SK_(__builtin_vec_delete) ( void* p )
+{
+ die_block( p, /*custom_free*/False );
+}
+
+void* SK_(realloc) ( void* p_old, Int new_size )
+{
+ HP_Chunk* hc;
+ HP_Chunk** remove_handle;
+ Int i;
+ void* p_new;
+ UInt old_size;
+ XPt *old_where, *new_where;
+
+ VGP_PUSHCC(VgpCliMalloc);
+
+ // First try and find the block.
+ hc = get_HP_Chunk ( p_old, &remove_handle );
+ if (hc == NULL) {
+ VGP_POPCC(VgpCliMalloc);
+ return NULL; // must have been a bogus free()
+ }
+
+ sk_assert(hc->data == (Addr)p_old);
+ old_size = hc->size;
+
+ if (new_size <= old_size) {
+ // new size is smaller or same; block not moved
+ p_new = p_old;
+
+ } else {
+ // new size is bigger; make new block, copy shared contents, free old
+ p_new = VG_(cli_malloc)(VG_(clo_alignment), new_size);
+
+ for (i = 0; i < old_size; i++)
+ ((UChar*)p_new)[i] = ((UChar*)p_old)[i];
+
+ VG_(cli_free)(p_old);
+ }
+
+ old_where = hc->where;
+ new_where = get_XCon( VG_(get_current_or_recent_tid)(),
+ /*custom_malloc*/False);
+
+ // Update HP_Chunk
+ hc->data = (Addr)p_new;
+ hc->size = new_size;
+ hc->where = new_where;
+
+ // Update XPt curr_space fields
+ if (clo_heap) {
+ if (0 != old_size) update_XCon(old_where, -old_size);
+ if (0 != new_size) update_XCon(new_where, new_size);
+ }
+
+ // If block has moved, have to remove and reinsert in the malloclist
+ // (since the updated 'data' field is the hash lookup key).
+ if (p_new != p_old) {
+ remove_HP_Chunk(hc, remove_handle);
+ add_HP_Chunk(hc);
+ }
+
+ VGP_POPCC(VgpCliMalloc);
+ return p_new;
+}
+
+
+/*------------------------------------------------------------*/
+/*--- Taking a census ---*/
+/*------------------------------------------------------------*/
+
+static Census censi[MAX_N_CENSI];
+static UInt curr_census = 0;
+
+// Must return False so that all stacks are traversed
+static UInt count_stack_size_counter;
+static Bool count_stack_size( Addr stack_min, Addr stack_max )
+{
+ count_stack_size_counter += (stack_max - stack_min);
+ return False;
+}
+
+static UInt get_xtree_size(XPt* xpt, UInt ix)
+{
+ UInt i;
+
+// VG_(printf)("%4d ", xpt->curr_space);
+
+ // If this one has size zero, all the children will be size zero too, so
+ // nothing interesting to record.
+// if (0 != xpt->curr_space || 0 == ix) {
+ if (xpt->curr_space / (double)alloc_xpt->curr_space > 0.002 || 0 == ix) {
+ ix++;
+
+ // Count all (non-zero) descendent XPts
+ for (i = 0; i < xpt->n_children; i++)
+ ix = get_xtree_size(xpt->children[i], ix);
+ }
+ return ix;
+}
+
+static
+UInt do_space_snapshot(XPt xpt[], XTreeSnapshot xtree_snapshot, UInt ix)
+{
+ UInt i;
+
+ // Snapshot this XPt, if non-zero space, or the first one
+// if (0 != xpt->curr_space || 0 == ix) {
+ if (xpt->curr_space / (double)alloc_xpt->curr_space > 0.002 || 0 == ix) {
+ xtree_snapshot[ix].xpt = xpt;
+ xtree_snapshot[ix].space = xpt->curr_space;
+ ix++;
+
+ // Snapshot all (non-zero) descendent XPts
+ for (i = 0; i < xpt->n_children; i++)
+ ix = do_space_snapshot(xpt->children[i], xtree_snapshot, ix);
+ }
+ return ix;
+}
+
+static UInt ms_interval;
+static UInt do_every_nth_census = 30;
+
+// Weed out half the censi; we choose those that represent the smallest
+// time-spans, because that loses the least information.
+//
+// Algorithm for N censi: We find the census representing the smallest
+// timeframe, and remove it. We repeat this until (N/2)-1 censi are gone.
+// (It's (N/2)-1 because we never remove the first and last censi.)
+// We have to do this one census at a time, rather than finding the (N/2)-1
+// smallest censi in one hit, because when a census is removed, it's
+// neighbours immediately cover greater timespans. So it's N^2, but N only
+// equals 200, and this is only done every 100 censi, which is not too often.
+static void halve_censi(void)
+{
+ Int i, jp, j, jn, k;
+ Census* min_census;
+
+ n_halvings++;
+ if (VG_(clo_verbosity) > 1)
+ VG_(message)(Vg_UserMsg, "Halving censi...");
+
+ // Sets j to the index of the first not-yet-removed census at or after i
+ #define FIND_CENSUS(i, j) \
+ for (j = i; -1 == censi[j].ms_time; j++) { }
+
+ for (i = 2; i < MAX_N_CENSI; i += 2) {
+ // Find the censi representing the smallest timespan. The timespan
+ // for census n = d(N-1,N)+d(N,N+1), where d(A,B) is the time between
+ // censi A and B. We don't consider the first and last censi for
+ // removal.
+ Int min_span = 0x7fffffff;
+ Int min_j = 0;
+
+ // Initial triple: (prev, curr, next) == (jp, j, jn)
+ jp = 0;
+ FIND_CENSUS(1, j);
+ FIND_CENSUS(j+1, jn);
+ while (jn < MAX_N_CENSI) {
+ Int timespan = censi[jn].ms_time - censi[jp].ms_time;
+ sk_assert(timespan >= 0);
+ if (timespan < min_span) {
+ min_span = timespan;
+ min_j = j;
+ }
+ // Move on to next triple
+ jp = j;
+ j = jn;
+ FIND_CENSUS(jn+1, jn);
+ }
+ // We've found the least important census, now remove it
+ min_census = & censi[ min_j ];
+ for (k = 0; NULL != min_census->xtree_snapshots[k]; k++) {
+ n_snapshot_frees++;
+ VG_(free)(min_census->xtree_snapshots[k]);
+ min_census->xtree_snapshots[k] = NULL;
+ }
+ min_census->ms_time = -1;
+ }
+
+ // Slide down the remaining censi over the removed ones. The '<=' is
+ // because we are removing on (N/2)-1, rather than N/2.
+ for (i = 0, j = 0; i <= MAX_N_CENSI / 2; i++, j++) {
+ FIND_CENSUS(j, j);
+ if (i != j) {
+ censi[i] = censi[j];
+ }
+ }
+ curr_census = i;
+
+ // Double intervals
+ ms_interval *= 2;
+ do_every_nth_census *= 2;
+
+ if (VG_(clo_verbosity) > 1)
+ VG_(message)(Vg_UserMsg, "...done");
+}
+
+// Take a census. Census time seems to be insignificant (usually <= 0 ms,
+// almost always <= 1ms) so don't have to worry about subtracting it from
+// running time in any way.
+//
+// XXX: NOT TRUE! with bigger depths, konqueror censuses can easily take
+// 50ms!
+static void hp_census(void)
+{
+ static UInt ms_prev_census = 0;
+ static UInt ms_next_census = 0; // zero allows startup census
+
+ Int ms_time, ms_time_since_prev;
+ Int i, K;
+ Census* census;
+
+ VGP_PUSHCC(VgpCensus);
+
+ // Only do a census if it's time
+ ms_time = VG_(read_millisecond_timer)();
+ ms_time_since_prev = ms_time - ms_prev_census;
+ if (ms_time < ms_next_census) {
+ n_fake_censi++;
+ VGP_POPCC(VgpCensus);
+ return;
+ }
+ n_real_censi++;
+
+ census = & censi[curr_census];
+
+ census->ms_time = ms_time;
+
+ // Heap: snapshot the K most significant XTrees -------------------
+ if (clo_heap) {
+ K = ( alloc_xpt->n_children < MAX_SNAPSHOTS
+ ? alloc_xpt->n_children
+ : MAX_SNAPSHOTS); // max out
+
+ // Update .spacetime field (approximatively) for all top-XPts.
+ // We *do not* do it for any non-top-XPTs.
+ for (i = 0; i < alloc_xpt->n_children; i++) {
+ XPt* top_XPt = alloc_xpt->children[i];
+ top_XPt->spacetime += top_XPt->curr_space * ms_time_since_prev;
+ }
+ // Sort top-XPts by spacetime2 field.
+ VG_(ssort)(alloc_xpt->children, alloc_xpt->n_children, sizeof(XPt*),
+ XPt_cmp_spacetime);
+
+ VGP_PUSHCC(VgpCensusHeap);
+
+ // For each significant top-level XPt, record space info about its
+ // entire XTree, in a single census entry.
+ // Nb: the xtree_size count/snapshot buffer allocation, and the actual
+ // snapshot, take similar amounts of time (measured with the
+ // millesecond counter).
+ for (i = 0; i < K; i++) {
+ UInt xtree_size, xtree_size2;
+// VG_(printf)("%7u ", alloc_xpt->children[i]->spacetime);
+ // Count how many XPts are in the XTree; make array of that size
+ // (+1 for zero termination, which calloc() does for us).
+ VGP_PUSHCC(VgpCensusTreeSize);
+ xtree_size = get_xtree_size( alloc_xpt->children[i], 0 );
+ VGP_POPCC(VgpCensusTreeSize);
+ census->xtree_snapshots[i] =
+ VG_(calloc)(xtree_size+1, sizeof(XPtSnapshot));
+ if (VG_(clo_verbosity) > 1)
+ VG_(printf)("calloc: %d (%d B)\n", xtree_size+1,
+ (xtree_size+1) * sizeof(XPtSnapshot));
+
+ // Take space-snapshot: copy 'curr_space' for every XPt in the
+ // XTree into the snapshot array, along with pointers to the XPts.
+ // (Except for ones with curr_space==0, which wouldn't contribute
+ // to the final spacetime2 calculation anyway; excluding them
+ // saves a lot of memory and up to 40% time with big --depth valus.
+ VGP_PUSHCC(VgpCensusSnapshot);
+ xtree_size2 = do_space_snapshot(alloc_xpt->children[i],
+ census->xtree_snapshots[i], 0);
+ sk_assert(xtree_size == xtree_size2);
+ VGP_POPCC(VgpCensusSnapshot);
+ }
+// VG_(printf)("\n\n");
+ // Zero-terminate 'xtree_snapshot' array
+ census->xtree_snapshots[i] = NULL;
+
+ VGP_POPCC(VgpCensusHeap);
+
+ //VG_(printf)("printed %d censi\n", K);
+
+ // Lump the rest into a single "others" entry.
+ census->others_space = 0;
+ for (i = K; i < alloc_xpt->n_children; i++) {
+ census->others_space += alloc_xpt->children[i]->curr_space;
+ }
+ }
+
+ // Heap admin -------------------------------------------------------
+ if (clo_heap_admin > 0)
+ census->heap_admin_space = clo_heap_admin * n_heap_blocks;
+
+ // Stack(s) ---------------------------------------------------------
+ if (clo_stacks) {
+ count_stack_size_counter = sigstacks_space;
+ // slightly abusing this function
+ VG_(first_matching_thread_stack)( count_stack_size );
+ census->stacks_space = count_stack_size_counter;
+ i++;
+ }
+
+ // Finish, update interval if necessary -----------------------------
+ curr_census++;
+ census = NULL; // don't use again now that curr_census changed
+
+ // Halve the entries, if our census table is full
+ if (MAX_N_CENSI == curr_census) {
+ halve_censi();
+ }
+
+ // Take time for next census from now, rather than when this census
+ // should have happened. Because, if there's a big gap due to a kernel
+ // operation, there's no point doing catch-up censi every BB for a while
+ // -- that would just give N censi at almost the same time.
+ if (VG_(clo_verbosity) > 1) {
+ VG_(message)(Vg_UserMsg, "census: %d ms (took %d ms)", ms_time,
+ VG_(read_millisecond_timer)() - ms_time );
+ }
+ ms_prev_census = ms_time;
+ ms_next_census = ms_time + ms_interval;
+ //ms_next_census += ms_interval;
+
+ //VG_(printf)("Next: %d ms\n", ms_next_census);
+
+ VGP_POPCC(VgpCensus);
+}
+
+/*------------------------------------------------------------*/
+/*--- Tracked events ---*/
+/*------------------------------------------------------------*/
+
+static void new_mem_stack_signal(Addr a, UInt len)
+{
+ sigstacks_space += len;
+}
+
+static void die_mem_stack_signal(Addr a, UInt len)
+{
+ sk_assert(sigstacks_space >= len);
+ sigstacks_space -= len;
+}
+
+/*------------------------------------------------------------*/
+/*--- Client Requests ---*/
+/*------------------------------------------------------------*/
+
+Bool SK_(handle_client_request) ( ThreadId tid, UInt* argv, UInt* ret )
+{
+ switch (argv[0]) {
+ case VG_USERREQ__MALLOCLIKE_BLOCK: {
+ void* p = (void*)argv[1];
+ UInt sizeB = argv[2];
+ *ret = 0;
+ new_block_meta( p, sizeB, /*custom_malloc*/True );
+ return True;
+ }
+ case VG_USERREQ__FREELIKE_BLOCK: {
+ void* p = (void*)argv[1];
+ *ret = 0;
+ die_block( p, /*custom_free*/True );
+ return True;
+ }
+ default:
+ *ret = 0;
+ return False;
+ }
+}
+
+/*------------------------------------------------------------*/
+/*--- Initialisation ---*/
+/*------------------------------------------------------------*/
+
+// Current directory at startup.
+static Char* base_dir;
+
+UInt VG_(vg_malloc_redzone_szB) = 0;
+
+void SK_(pre_clo_init)()
+{
+ VG_(details_name) ("Massif");
+ VG_(details_version) ("0.0.3");
+ VG_(details_description) ("a space profiler");
+ VG_(details_copyright_author)("Copyright (C) 2003, Nicholas Nethercote");
+ VG_(details_bug_reports_to) ("njn25@cam.ac.uk");
+
+ // Needs
+ VG_(needs_libc_freeres)();
+ VG_(needs_command_line_options)();
+ VG_(needs_client_requests) ();
+
+ // Events to track
+ VG_(init_new_mem_stack_signal) ( new_mem_stack_signal );
+ VG_(init_die_mem_stack_signal) ( die_mem_stack_signal );
+
+ // Profiling events
+ VGP_(register_profile_event)(VgpGetXPt, "get-XPt");
+ VGP_(register_profile_event)(VgpGetXPtSearch, "get-XPt-search");
+ VGP_(register_profile_event)(VgpCensus, "census");
+ VGP_(register_profile_event)(VgpCensusHeap, "census-heap");
+ VGP_(register_profile_event)(VgpCensusSnapshot, "census-snapshot");
+ VGP_(register_profile_event)(VgpCensusTreeSize, "census-treesize");
+ VGP_(register_profile_event)(VgpUpdateXCon, "update-XCon");
+ VGP_(register_profile_event)(VgpCalcSpacetime2, "calc-spacetime2");
+ VGP_(register_profile_event)(VgpPrintHp, "print-hp");
+ VGP_(register_profile_event)(VgpPrintXPts, "print-XPts");
+
+ // HP_Chunks
+ malloc_list = VG_(HT_construct)();
+
+ // Dummy node at top of the context structure.
+ alloc_xpt = new_XPt(0, NULL, /*is_bottom*/False);
+
+ sk_assert( VG_(getcwd_alloc)(&base_dir) );
+}
+
+void SK_(post_clo_init)(void)
+{
+ ms_interval = 1;
+
+ // Do an initial sample for t = 0
+ hp_census();
+}
+
+/*------------------------------------------------------------*/
+/*--- Instrumentation ---*/
+/*------------------------------------------------------------*/
+
+UCodeBlock* SK_(instrument)(UCodeBlock* cb_in, Addr orig_addr)
+{
+ return cb_in;
+}
+
+/*------------------------------------------------------------*/
+/*--- Spacetime recomputation ---*/
+/*------------------------------------------------------------*/
+
+// Although we've been calculating spacetime along the way, because the
+// earlier calculations were done at a finer timescale, the .spacetime field
+// might not agree with what hp2ps sees, because we've thrown away some of
+// the information. So recompute it at the scale that hp2ps sees, so we can
+// confidently determine which contexts hp2ps will choose for displaying as
+// distinct bands. This recomputation only happens to the significant ones
+// that get printed in the .hp file, so it's cheap.
+//
+// The spacetime calculation:
+// ( a[0]*d(0,1) + a[1]*(d(0,1) + d(1,2)) + ... + a[N-1]*d(N-2,N-1) ) / 2
+// where
+// a[N] is the space at census N
+// d(A,B) is the time interval between censi A and B
+// and
+// d(A,B) + d(B,C) == d(A,C)
+//
+// Key point: we can calculate the area for a census without knowing the
+// previous or subsequent censi's space; because any over/underestimates
+// for this census will be reversed in the next, balancing out. This is
+// important, as getting the previous/next census entry for a particular
+// AP is a pain with this data structure, but getting the prev/next
+// census time is easy.
+//
+// Each heap calculation gets added to its context's spacetime2 field.
+// The ULong* values are all running totals, hence the use of "+=" everywhere.
+
+// This does the calculations for a single census.
+static void calc_spacetime2b(Census* census, UInt d_t1_t2,
+ ULong* twice_heap_ST,
+ ULong* twice_heap_admin_ST,
+ ULong* twice_stack_ST)
+{
+ UInt i, j;
+ XPtSnapshot* xpt_snapshot;
+
+ // Heap --------------------------------------------------------
+ if (clo_heap) {
+ for (i = 0; NULL != census->xtree_snapshots[i]; i++) {
+ // Compute total heap spacetime2 for the entire XTree using only the
+ // top-XPt (the first XPt in xtree_snapshot).
+ *twice_heap_ST += d_t1_t2 * census->xtree_snapshots[i][0].space;
+
+ // Increment spacetime2 for every XPt in xtree_snapshot (inc. top one)
+ for (j = 0; NULL != census->xtree_snapshots[i][j].xpt; j++) {
+ xpt_snapshot = & census->xtree_snapshots[i][j];
+ xpt_snapshot->xpt->spacetime2 += d_t1_t2 * xpt_snapshot->space;
+ }
+ }
+ *twice_heap_ST += d_t1_t2 * census->others_space;
+ }
+
+ // Heap admin --------------------------------------------------
+ if (clo_heap_admin > 0)
+ *twice_heap_admin_ST += d_t1_t2 * census->heap_admin_space;
+
+ // Stack(s) ----------------------------------------------------
+ if (clo_stacks)
+ *twice_stack_ST += d_t1_t2 * census->stacks_space;
+}
+
+// This does the calculations for all censi.
+static void calc_spacetime2(ULong* heap2, ULong* heap_admin2, ULong* stack2)
+{
+ UInt i, N = curr_census;
+
+ VGP_PUSHCC(VgpCalcSpacetime2);
+
+ *heap2 = 0;
+ *heap_admin2 = 0;
+ *stack2 = 0;
+
+ if (N <= 1)
+ return;
+
+ calc_spacetime2b( &censi[0], censi[1].ms_time - censi[0].ms_time,
+ heap2, heap_admin2, stack2 );
+
+ for (i = 1; i <= N-2; i++) {
+ calc_spacetime2b( & censi[i], censi[i+1].ms_time - censi[i-1].ms_time,
+ heap2, heap_admin2, stack2 );
+ }
+
+ calc_spacetime2b( & censi[N-1], censi[N-1].ms_time - censi[N-2].ms_time,
+ heap2, heap_admin2, stack2 );
+ // Now get rid of the halves. May lose a 0.5 on each, doesn't matter.
+ *heap2 /= 2;
+ *heap_admin2 /= 2;
+ *stack2 /= 2;
+
+ VGP_POPCC(VgpCalcSpacetime2);
+}
+
+/*------------------------------------------------------------*/
+/*--- Writing the graph file ---*/
+/*------------------------------------------------------------*/
+
+static Char* make_filename(Char* dir, Char* suffix)
+{
+ Char* filename;
+
+ /* Block is big enough for dir name + massif.<pid>.<suffix> */
+ filename = VG_(malloc)((VG_(strlen)(dir) + 32)*sizeof(Char));
+ VG_(sprintf)(filename, "%s/massif.%d%s", dir, VG_(getpid)(), suffix);
+
+ return filename;
+}
+
+// Make string acceptable to hp2ps (sigh): remove spaces, escape parentheses.
+static Char* clean_fnname(Char *d, Char* s)
+{
+ Char* dorig = d;
+ while (*s) {
+ if (' ' == *s) { *d = '%'; }
+ else if ('(' == *s) { *d++ = '\\'; *d = '('; }
+ else if (')' == *s) { *d++ = '\\'; *d = ')'; }
+ else { *d = *s; };
+ s++;
+ d++;
+ }
+ *d = '\0';
+ return dorig;
+}
+
+static void file_err ( Char* file )
+{
+ VG_(message)(Vg_UserMsg, "error: can't open output file `%s'", file );
+ VG_(message)(Vg_UserMsg, " ... so profile results will be missing.");
+}
+
+/* Format, by example:
+
+ JOB "a.out -p"
+ DATE "Fri Apr 17 11:43:45 1992"
+ SAMPLE_UNIT "seconds"
+ VALUE_UNIT "bytes"
+ BEGIN_SAMPLE 0.00
+ SYSTEM 24
+ END_SAMPLE 0.00
+ BEGIN_SAMPLE 1.00
+ elim 180
+ insert 24
+ intersect 12
+ disin 60
+ main 12
+ reduce 20
+ SYSTEM 12
+ END_SAMPLE 1.00
+ MARK 1.50
+ MARK 1.75
+ MARK 1.80
+ BEGIN_SAMPLE 2.00
+ elim 192
+ insert 24
+ intersect 12
+ disin 84
+ main 12
+ SYSTEM 24
+ END_SAMPLE 2.00
+ BEGIN_SAMPLE 2.82
+ END_SAMPLE 2.82
+ */
+static void write_hp_file(void)
+{
+ Int i, j;
+ Int fd, res;
+ Char *hp_file, *ps_file, *aux_file;
+ Char* cmdfmt;
+ Char* cmdbuf;
+ Int cmdlen;
+
+ VGP_PUSHCC(VgpPrintHp);
+
+ // Open file
+ hp_file = make_filename( base_dir, ".hp" );
+ ps_file = make_filename( base_dir, ".ps" );
+ aux_file = make_filename( base_dir, ".aux" );
+ fd = VG_(open)(hp_file, VKI_O_CREAT|VKI_O_TRUNC|VKI_O_WRONLY,
+ VKI_S_IRUSR|VKI_S_IWUSR);
+ if (fd < 0) {
+ file_err( hp_file );
+ VGP_POPCC(VgpPrintHp);
+ return;
+ }
+
+ // File header, including command line
+ SPRINTF(buf, "JOB \"");
+ for (i = 0; i < VG_(client_argc); i++)
+ SPRINTF(buf, "%s ", VG_(client_argv)[i]);
+ SPRINTF(buf, /*" (%d ms/sample)\"\n"*/ "\"\n"
+ "DATE \"\"\n"
+ "SAMPLE_UNIT \"ms\"\n"
+ "VALUE_UNIT \"bytes\"\n", ms_interval);
+
+ // Censi
+ for (i = 0; i < curr_census; i++) {
+ Census* census = & censi[i];
+
+ // Census start
+ SPRINTF(buf, "MARK %d.0\n"
+ "BEGIN_SAMPLE %d.0\n",
+ census->ms_time, census->ms_time);
+
+ // Heap -----------------------------------------------------------
+ if (clo_heap) {
+ // Print all the significant XPts from that census
+ for (j = 0; NULL != census->xtree_snapshots[j]; j++) {
+ // Grab the jth top-XPt
+ XTreeSnapshot xtree_snapshot = & census->xtree_snapshots[j][0];
+ if ( ! VG_(get_fnname)(xtree_snapshot->xpt->eip, buf2, 16)) {
+ VG_(sprintf)(buf2, "???");
+ }
+ SPRINTF(buf, "x%x:%s %d\n", xtree_snapshot->xpt->eip,
+ clean_fnname(buf3, buf2), xtree_snapshot->space);
+ }
+
+ // Remaining heap block alloc points, combined
+ if (census->others_space > 0)
+ SPRINTF(buf, "other %d\n", census->others_space);
+ }
+
+ // Heap admin -----------------------------------------------------
+ if (clo_heap_admin > 0 && census->heap_admin_space)
+ SPRINTF(buf, "heap-admin %d\n", census->heap_admin_space);
+
+ // Stack(s) -------------------------------------------------------
+ if (clo_stacks)
+ SPRINTF(buf, "stack(s) %d\n", census->stacks_space);
+
+ // Census end
+ SPRINTF(buf, "END_SAMPLE %d.0\n", census->ms_time);
+ }
+
+ // Close file
+ sk_assert(fd >= 0);
+ VG_(close)(fd);
+
+ // Attempt to convert file using hp2ps
+ cmdfmt = "%s/hp2ps -c -t1 %s";
+ cmdlen = VG_(strlen)(VG_(libdir)) + VG_(strlen)(hp_file)
+ + VG_(strlen)(cmdfmt);
+ cmdbuf = VG_(malloc)( sizeof(Char) * cmdlen );
+ VG_(sprintf)(cmdbuf, cmdfmt, VG_(libdir), hp_file);
+ res = VG_(system)(cmdbuf);
+ VG_(free)(cmdbuf);
+ if (res != 0) {
+ VG_(message)(Vg_UserMsg,
+ "Conversion to PostScript failed. Try converting manually.");
+ } else {
+ // remove the .hp and .aux file
+ VG_(unlink)(hp_file);
+ VG_(unlink)(aux_file);
+ }
+
+ VG_(free)(hp_file);
+ VG_(free)(ps_file);
+ VG_(free)(aux_file);
+
+ VGP_POPCC(VgpPrintHp);
+}
+
+/*------------------------------------------------------------*/
+/*--- Writing the XPt text/HTML file ---*/
+/*------------------------------------------------------------*/
+
+static void percentify(Int n, Int pow, Int field_width, char xbuf[])
+{
+ int i, len, space;
+
+ VG_(sprintf)(xbuf, "%d.%d%%", n / pow, n % pow);
+ len = VG_(strlen)(xbuf);
+ space = field_width - len;
+ if (space < 0) space = 0; /* Allow for v. small field_width */
+ i = len;
+
+ /* Right justify in field */
+ for ( ; i >= 0; i--) xbuf[i + space] = xbuf[i];
+ for (i = 0; i < space; i++) xbuf[i] = ' ';
+}
+
+// Nb: uses a static buffer, each call trashes the last string returned.
+static Char* make_perc(ULong spacetime, ULong total_spacetime)
+{
+ static Char mbuf[32];
+
+ UInt p = 10;
+ percentify(spacetime * 100 * p / total_spacetime, p, 5, mbuf);
+ return mbuf;
+}
+
+// Nb: passed in XPt is a lower-level XPt; %eips are grabbed from
+// bottom-to-top of XCon, and then printed in the reverse order.
+static UInt pp_XCon(Int fd, XPt* xpt)
+{
+ Addr rev_eips[clo_depth+1];
+ Int i = 0;
+ Int n = 0;
+ Bool is_HTML = ( XHTML == clo_format );
+ Char* maybe_br = ( is_HTML ? "<br>" : "" );
+ Char* maybe_indent = ( is_HTML ? " " : "" );
+
+ sk_assert(NULL != xpt);
+
+ while (True) {
+ rev_eips[i] = xpt->eip;
+ n++;
+ if (alloc_xpt == xpt->parent) break;
+ i++;
+ xpt = xpt->parent;
+ }
+
+ for (i = n-1; i >= 0; i--) {
+ // -1 means point to calling line
+ VG_(describe_eip)(rev_eips[i]-1, buf2, BUF_LEN);
+ SPRINTF(buf, " %s%s%s\n", maybe_indent, buf2, maybe_br);
+ }
+
+ return n;
+}
+
+// Important point: for HTML, each XPt must be identified uniquely for the
+// HTML links to all match up correctly. Using xpt->eip is not
+// sufficient, because function pointers mean that you can call more than
+// one other function from a single code location. So instead we use the
+// address of the xpt struct itself, which is guaranteed to be unique.
+
+static void pp_all_XPts2(Int fd, Queue* q, ULong heap_spacetime,
+ ULong total_spacetime)
+{
+ UInt i;
+ XPt *xpt, *child;
+ UInt L = 0;
+ UInt c1 = 1;
+ UInt c2 = 0;
+ ULong sum = 0;
+ UInt n;
+ Char *eip_desc, *perc;
+ Bool is_HTML = ( XHTML == clo_format );
+ Char* maybe_br = ( is_HTML ? "<br>" : "" );
+ Char* maybe_p = ( is_HTML ? "<p>" : "" );
+ Char* maybe_ul = ( is_HTML ? "<ul>" : "" );
+ Char* maybe_li = ( is_HTML ? "<li>" : "" );
+ Char* maybe_fli = ( is_HTML ? "</li>" : "" );
+ Char* maybe_ful = ( is_HTML ? "</ul>" : "" );
+ Char* end_hr = ( is_HTML ? "<hr>" :
+ "=================================" );
+ Char* depth = ( is_HTML ? "<code>--depth</code>" : "--depth" );
+
+ SPRINTF(buf, "== %d ===========================%s\n", L, maybe_br);
+
+ while (NULL != (xpt = (XPt*)dequeue(q))) {
+ // Check that non-top-level XPts have a zero .spacetime field.
+ if (xpt->parent != alloc_xpt) sk_assert( 0 == xpt->spacetime );
+
+ // Check that the sum of all children .spacetime2s equals parent's
+ // (unless alloc_xpt, when it should == 0).
+ if (alloc_xpt == xpt) {
+ sk_assert(0 == xpt->spacetime2);
+ } else {
+ sum = 0;
+ for (i = 0; i < xpt->n_children; i++) {
+ sum += xpt->children[i]->spacetime2;
+ }
+ //sk_assert(sum == xpt->spacetime2);
+ // It's possible that not all the children were included in the
+ // spacetime2 calculations. Hopefully almost all of them were, and
+ // all the important ones.
+// sk_assert(sum <= xpt->spacetime2);
+// sk_assert(sum * 1.05 > xpt->spacetime2 );
+// if (sum != xpt->spacetime2) {
+// VG_(printf)("%ld, %ld\n", sum, xpt->spacetime2);
+// }
+ }
+
+ if (xpt == alloc_xpt) {
+ SPRINTF(buf, "Heap allocation functions accounted for "
+ "%s of measured spacetime%s\n",
+ make_perc(heap_spacetime, total_spacetime), maybe_br);
+ } else {
+ // Remember: spacetime2 is space.time *doubled*
+ perc = make_perc(xpt->spacetime2 / 2, total_spacetime);
+ if (is_HTML) {
+ SPRINTF(buf, "<a name=\"b%x\"></a>"
+ "Context accounted for "
+ "<a href=\"#a%x\">%s</a> of measured spacetime<br>\n",
+ xpt, xpt, perc);
+ } else {
+ SPRINTF(buf, "Context accounted for %s of measured spacetime\n",
+ perc);
+ }
+ n = pp_XCon(fd, xpt);
+ sk_assert(n == L);
+ }
+
+ // Sort children by spacetime2
+ VG_(ssort)(xpt->children, xpt->n_children, sizeof(XPt*),
+ XPt_cmp_spacetime2);
+
+ SPRINTF(buf, "%s\nCalled from:%s\n", maybe_p, maybe_ul);
+ for (i = 0; i < xpt->n_children; i++) {
+ child = xpt->children[i];
+
+ // Stop when <1% of total spacetime
+ if (child->spacetime2 * 1000 / (total_spacetime * 2) < 5) {
+ UInt n_insig = xpt->n_children - i;
+ Char* s = ( n_insig == 1 ? "" : "s" );
+ Char* and = ( 0 == i ? "" : "and " );
+ Char* other = ( 0 == i ? "" : "other " );
+ SPRINTF(buf, " %s%s%d %sinsignificant place%s%s\n\n",
+ maybe_li, and, n_insig, other, s, maybe_fli);
+ break;
+ }
+
+ // Remember: spacetime2 is space.time *doubled*
+ perc = make_perc(child->spacetime2 / 2, total_spacetime);
+ eip_desc = VG_(describe_eip)(child->eip-1, buf2, BUF_LEN);
+ if (is_HTML) {
+ SPRINTF(buf, "<li><a name=\"a%x\"></a>", child );
+
+ if (child->n_children > 0) {
+ SPRINTF(buf, "<a href=\"#b%x\">%s</a>", child, perc);
+ } else {
+ SPRINTF(buf, "%s", perc);
+ }
+ SPRINTF(buf, ": %s\n", eip_desc);
+ } else {
+ SPRINTF(buf, " %6s: %s\n\n", perc, eip_desc);
+ }
+
+ if (child->n_children > 0) {
+ enqueue(q, (void*)child);
+ c2++;
+ }
+ }
+ SPRINTF(buf, "%s%s", maybe_ful, maybe_p);
+ c1--;
+
+ // Putting markers between levels of the structure:
+ // c1 tracks how many to go on this level, c2 tracks how many we've
+ // queued up for the next level while finishing off this level.
+ // When c1 gets to zero, we've changed levels, so print a marker,
+ // move c2 into c1, and zero c2.
+ if (0 == c1) {
+ L++;
+ c1 = c2;
+ c2 = 0;
+ if (! is_empty_queue(q) ) { // avoid empty one at end
+ SPRINTF(buf, "== %d ===========================%s\n", L, maybe_br);
+ }
+ } else {
+ SPRINTF(buf, "---------------------------------%s\n", maybe_br);
+ }
+ }
+ SPRINTF(buf, "%s\n\nEnd of information. Rerun with a bigger "
+ "%s value for more.\n", end_hr, depth);
+}
+
+static void pp_all_XPts(Int fd, XPt* xpt, ULong heap_spacetime,
+ ULong total_spacetime)
+{
+ Queue* q = construct_queue(100);
+ enqueue(q, xpt);
+ pp_all_XPts2(fd, q, heap_spacetime, total_spacetime);
+ destruct_queue(q);
+}
+
+static void
+write_text_file(ULong total_ST, ULong heap_ST)
+{
+ Int fd, i;
+ Char* text_file;
+ Char* maybe_p = ( XHTML == clo_format ? "<p>" : "" );
+
+ VGP_PUSHCC(VgpPrintXPts);
+
+ // Open file
+ text_file = make_filename( base_dir,
+ ( XText == clo_format ? ".txt" : ".html" ) );
+
+ fd = VG_(open)(text_file, VKI_O_CREAT|VKI_O_TRUNC|VKI_O_WRONLY,
+ VKI_S_IRUSR|VKI_S_IWUSR);
+ if (fd < 0) {
+ file_err( text_file );
+ VGP_POPCC(VgpPrintXPts);
+ return;
+ }
+
+ // Header
+ if (XHTML == clo_format) {
+ SPRINTF(buf, "<html>\n"
+ "<head>\n"
+ "<title>%s</title>\n"
+ "</head>\n"
+ "<body>\n",
+ text_file);
+ }
+
+ // Command line
+ SPRINTF(buf, "Command: ");
+ for (i = 0; i < VG_(client_argc); i++)
+ SPRINTF(buf, "%s ", VG_(client_argv)[i]);
+ SPRINTF(buf, "\n%s\n", maybe_p);
+
+ if (clo_heap)
+ pp_all_XPts(fd, alloc_xpt, heap_ST, total_ST);
+
+ sk_assert(fd >= 0);
+ VG_(close)(fd);
+
+ VGP_POPCC(VgpPrintXPts);
+}
+
+/*------------------------------------------------------------*/
+/*--- Finalisation ---*/
+/*------------------------------------------------------------*/
+
+static void
+print_summary(ULong total_ST, ULong heap_ST, ULong heap_admin_ST,
+ ULong stack_ST)
+{
+ VG_(message)(Vg_UserMsg, "Total spacetime: %,ld ms.B", total_ST);
+
+ // Heap --------------------------------------------------------------
+ if (clo_heap)
+ VG_(message)(Vg_UserMsg, "heap: %s",
+ make_perc(heap_ST, total_ST) );
+
+ // Heap admin --------------------------------------------------------
+ if (clo_heap_admin)
+ VG_(message)(Vg_UserMsg, "heap admin: %s",
+ make_perc(heap_admin_ST, total_ST));
+
+ sk_assert( VG_(HT_count_nodes)(malloc_list) == n_heap_blocks );
+
+ // Stack(s) ----------------------------------------------------------
+ if (clo_stacks)
+ VG_(message)(Vg_UserMsg, "stack(s): %s",
+ make_perc(stack_ST, total_ST));
+
+ if (VG_(clo_verbosity) > 1) {
+ sk_assert(n_xpts > 0); // always have alloc_xpt
+ VG_(message)(Vg_DebugMsg, " allocs: %u", n_allocs);
+ VG_(message)(Vg_DebugMsg, "zeroallocs: %u (%d%%)", n_zero_allocs,
+ n_zero_allocs * 100 / n_allocs );
+ VG_(message)(Vg_DebugMsg, " frees: %u", n_frees);
+ VG_(message)(Vg_DebugMsg, " XPts: %u (%d B)", n_xpts,
+ n_xpts*sizeof(XPt));
+ VG_(message)(Vg_DebugMsg, " bot-XPts: %u (%d%%)", n_bot_xpts,
+ n_bot_xpts * 100 / n_xpts);
+ VG_(message)(Vg_DebugMsg, " top-XPts: %u (%d%%)", alloc_xpt->n_children,
+ alloc_xpt->n_children * 100 / n_xpts);
+ VG_(message)(Vg_DebugMsg, "c-reallocs: %u", n_children_reallocs);
+ VG_(message)(Vg_DebugMsg, "snap-frees: %u", n_snapshot_frees);
+ VG_(message)(Vg_DebugMsg, "atmp censi: %u", n_attempted_censi);
+ VG_(message)(Vg_DebugMsg, "fake censi: %u", n_fake_censi);
+ VG_(message)(Vg_DebugMsg, "real censi: %u", n_real_censi);
+ VG_(message)(Vg_DebugMsg, " halvings: %u", n_halvings);
+ }
+}
+
+void SK_(fini)(Int exit_status)
+{
+ ULong total_ST = 0;
+ ULong heap_ST = 0;
+ ULong heap_admin_ST = 0;
+ ULong stack_ST = 0;
+
+ // Do a final (empty) sample to show program's end
+ hp_census();
+
+ // Redo spacetimes of significant contexts to match the .hp file.
+ calc_spacetime2(&heap_ST, &heap_admin_ST, &stack_ST);
+ total_ST = heap_ST + heap_admin_ST + stack_ST;
+ write_hp_file ( );
+ write_text_file( total_ST, heap_ST );
+ print_summary ( total_ST, heap_ST, heap_admin_ST, stack_ST );
+}
+
+VG_DETERMINE_INTERFACE_VERSION(SK_(pre_clo_init), 0)
+
+/*--------------------------------------------------------------------*/
+/*--- end ms_main.c ---*/
+/*--------------------------------------------------------------------*/
+
diff --git a/massif/tests/Makefile.am b/massif/tests/Makefile.am
new file mode 100644
index 0000000..5c3b76b
--- /dev/null
+++ b/massif/tests/Makefile.am
@@ -0,0 +1,6 @@
+noinst_SCRIPTS = filter_stderr
+
+EXTRA_DIST = $(noinst_SCRIPTS) \
+ true_html.stderr.exp true_html.vgtest \
+ true_text.stderr.exp true_text.vgtest
+
diff --git a/massif/tests/true_html.stderr.exp b/massif/tests/true_html.stderr.exp
new file mode 100644
index 0000000..c18e180
--- /dev/null
+++ b/massif/tests/true_html.stderr.exp
@@ -0,0 +1,6 @@
+
+
+Total spacetime:
+heap:
+heap admin:
+stack(s):
diff --git a/massif/tests/true_html.vgtest b/massif/tests/true_html.vgtest
new file mode 100644
index 0000000..8d56835
--- /dev/null
+++ b/massif/tests/true_html.vgtest
@@ -0,0 +1,2 @@
+prog: ../../tests/true
+vgopts: --format=html
diff --git a/massif/tests/true_text.stderr.exp b/massif/tests/true_text.stderr.exp
new file mode 100644
index 0000000..c18e180
--- /dev/null
+++ b/massif/tests/true_text.stderr.exp
@@ -0,0 +1,6 @@
+
+
+Total spacetime:
+heap:
+heap admin:
+stack(s):
diff --git a/massif/tests/true_text.vgtest b/massif/tests/true_text.vgtest
new file mode 100644
index 0000000..841ae1f
--- /dev/null
+++ b/massif/tests/true_text.vgtest
@@ -0,0 +1,2 @@
+prog: ../../tests/true
+vgopts: --format=text
