+++ /dev/null
-\documentclass{article}
-\usepackage{code,a4wide}
-
-\usepackage{graphics,epsfig,epic,eepic,epsfig}
-
-\setlength{\parskip}{0.25cm}
-\setlength{\parsep}{0.25cm}
-\setlength{\topsep}{0cm}
-\setlength{\parindent}{0cm}
-\renewcommand{\textfraction}{0.2}
-\renewcommand{\floatpagefraction}{0.7}
-
-
-% Terminology
-\newcommand{\block}{block}
-\newcommand{\Block}{Block}
-\newcommand{\segment}{segment}
-\newcommand{\Segment}{Segment}
-\newcommand{\step}{step}
-\newcommand{\Step}{Step}
-
-\newcommand{\note}[1]{{\em $\spadesuit$ #1}}
-
-\begin{document}
-\title{Implementation of Retainer Profiling}
-\author{Sungwoo Park and Simon Peyton-Jones}
-
-\makeatactive
-\maketitle
-
-\section{Retainer Profiling}
-
-Retainer profiling~\cite{CN} is a profiling technique which is based upon a
-special view of production and consumption of heap objects at runtime:
-while producers build heap objects to form new pieces of graph,
-consumers hold pointers to these heap objects, or \emph{retain} them, so
-that they are not freed during garbage collections.
-On this basis, we refereed to such consumers as \emph{retainers}.
-Notice that an object can have more than one retainer because it can
-be pointed to by multiple objects.
-
-For each live object in the heap, retainer profiling computes
-all its retainers, or its \emph{retainer set}.
-A naive implementation of retainer profiling could consider every
-immediate ancestor of an object as its retainer.
-Although this approach appears to provide an accurate report on the
-relationship between retainers and retainees, the result can hardly be useful.
-For instance, it is pointless to scrutinize a list and treat each cons
-cell as a retainer of the following cons cell.
-This observation suggests that we need to have a way of designating only
-certain types of objects as candidates for retainers.
-In other words, we need to employ an oracle which tells whether a given
-object can be a retainer or not.
-
-Since no retainer of a particular object needs to be using the
-object actively, we can find all its retainers simply by traversing
-the graph. In other words, we do not have to distinguish those retainers
-actively exploiting it from other retainers just holding pointers
-to it (either directly or indirectly).
-Thus, retainer profiling can be accomplished simply by traversing the
-graph.
-
-Figure~\ref{fig-retaineralgorithm} shows the algorithm for retainer
-profiling. The traversal begins at every root, and proceeds
-in a depth first manner (or a breadth first manner).
-The function @R()@ returns the \emph{identity} of a given retainer such
-as its information table address or
-the name of the module which creates it.
-Notice that the retainer identity function does not need to be a
-one-to-one mapping:
-multiple objects can share the same identity.
-Such a retainer identity function reduces the cost of traversal.
-For instance, when an object
-is reached from several retainers which share the same identity, we need to
-consider only the first visit to the object.
-In other words, whichever retainer (among those sharing the same identity)
-leads to the object for the first time affects the retainer set of the object
-in consideration
-and all the other retainers can be ignored.
-Thus, the more coarse the function @R()@ is, the less
-it costs to traverse the graph for retainer profiling.
-The function @isRetainer()@ tells whether a given object is a retainer or not.
-Hence, the behavior of the retainer profiling algorithm is parameterized
-over: 1) the set of roots; 2) the function @R()@; 3) the function
-@isRetainer()@.
-
-One important invariant on the function @R()@ is that its return value
-must be consistent for a given retainer. In other words, @R()@ must return
-the same value for a given retainer no matter it is invoked.
-For this reason, the memory address of a retainer, for instance, cannot be used as
-its retainer identity because its location may change during garbage collections.
-
-\begin{figure}[ht]
-\begin{center}
-\begin{code}
-for every root r
- retain(r, r)
-
-R(r) =
- the identity of r
-
-isRetainer(c) =
- if c is a retainer then
- true
- else
- false
-
-retain(c, r) =
- if R(r) is a member of c.retainerSet then
- return
- add R(r) to c.retainerSet
- if isRetainer(c) then
- r' := c
- else
- r' := r
- for every successor c' of c
- retain(c', r')
-\end{code}
-\caption{Retainer profiling algorithm}
-\label{fig-retaineralgorithm}
-\end{center}
-\end{figure}
-
-Another way of formulating retainer profiling is in terms of fixed point
-equations on retainer sets.
-To be specific, given the two functions @isRetainer()@ and @R()@,
-the retainer set of every object is computed as the least fixed point
-solution of the following equations:
-\begin{itemize}
-\item For every root @r@,
-\begin{center}
- @R(r)@ $\in$ @r.retainerSet@.
-\end{center}
-\item For every reachable object @c@,
-\begin{center}
-$\bigcup_{\mathit{each\ ancestor\ @a@\ of\ @c@}}$ @from(a)@ $\subseteq$
-@c.retainerSet@
-\end{center}
-where @from(a)@ returns retainer(s) obtainable from @a@:
-\begin{center}
-@from(a)@ = if @isRetainer(a)@ then $\{@a@\}$ else @a.retainerSet@.
-\end{center}
-\end{itemize}
-
-This document describes the implementation of retainer profiling on
-the Glasgow Haskell Compiler runtime system.
-It explains every detail of the development so that it can be (hopefully)
-a complete maintenance guide.
-A secondary goal is to help (hopefully) those who wish to extend the system
-to implement another profiling scheme.\footnote{Unless otherwise mentioned,
-all identifiers are defined in @RetainerProfile.c@ or @RetainerSet.c@.}
-
-\section{Installing the GHC}
-
-Installing the GHC is done as follows:
-
-\begin{enumerate}
-\item Get the source code from the CVS repository.
-\begin{code}
-./ cvs checkout fpconfig
-./fptools/ cvs update -d CONTRIB common-rts distrib docs ghc glafp-utils
- hslibs literate mhms mk nofib testsuite
-\end{code}
-
-\item Set up the basic configuration.
-\begin{code}
-./fptools/ autoconf
-./fptools/ghc/ autoconf
-./fptools/ configure
-\end{code}
-
-\item Set up the configuration for development and debugging.
-\begin{code}
-./fptools/mk vi build.mk
- GhcHcOpts = -O -fasm -Rghc-timing
- SplitObjs = NO
- GhcRtsHcOpts =
- GhcRtsCcOpts = -g
- STRIP =:
-\end{code}
-@GhcLibWays@ tells the compiler to build the code for profiling as well.
-@GhcRtsHcOpts@ has additional flags for @gcc@ when compiling @.hc@ files.
-@GhcRtsCcOpts@ has additional flags for @gcc@ when compiling @.c@ files.
-Since we will implement retainer profiling in @.c@ files, we turn on the
-debugging flag @-g@.
-The empty setting for @STRIP@ tells the compiler not to remove source code
-information (generated due to the @-g@ option) from executable files so that
-they can be examined with @gdb@.
-
-\item Remove unnecessary files if needed and build everything.
-\begin{code}
-./fptools/ make
-\end{code}
-\end{enumerate}
-
-\section{Adding Retainer Set Fields}
-
-Since every Haskell closure now needs to store its retainer set at runtime,
-it must be augmented with a new field,
-namely, a \emph{retainer set field}.
-This section explains how to add such a field to Haskell closures.
-It should be clear how to generalize the idea for adding
-any number of new fields.\footnote{The GHC provides two
-ways of building executable programs from
-source files: normal way and profiling way.
-We are concerned only about profiling way, and all the pieces of code
-implementing profiling way are wrapped by the @PROFILING@
-pre-processing directive (as in @\#ifdef PROFILING@).
-Therefore, all the additions and changes that we make to the source code
-are assumed to be wrapped by the @PROFILING@ pre-processing
-directive as well unless otherwise mentioned.}
-
-\subsection{Adding a new field to Haskell closures}
-
-We want to add a retainer set field of type @retainerSet@ to every
-closure, so we create a new file @includes/StgRetainerProf.h@ where
-we define the type @retainerSet@.
-The actual definition of @retainerSet@ will be given later.
-
-\begin{code}
-/* includes/StgRetainerProf.h */
-typedef ... retainerSet;
-\end{code}
-
-We make type @retainerSet@ to be publicly available by including
-@includes/StgRetainerProf.h@ itself to @includes/Stg.h@ (not wrapped
-by @PROFILING@).
-
-\begin{code}
-/* includes/Stg.h */
-#include "StgRetainerProf.h"
-\end{code}
-
-Then we add a retainer set field @rs@ to the @StgProfHeader@ structure.
-
-\begin{code}
-/* include/Closures.h */
-typedef struct {
- CostCentreStack *ccs;
- retainerSet *rs;
-} StgProfHeader;
-\end{code}
-
-Now every closure @c@ (including static closures) has a retainer set field,
-which can be accessed with @c->header.prof.rs@ (where @c@ denotes the
-address of the closure).
-
-\subsection{Changing constants}
-
-We are ready to reflect the new size of Haskell closures to other part
-of the source code.
-This is accomplished by changing a few constants which specify the size
-of certain types of closures and their layout.
-
-When building the runtime system, the @gcc@ compiler correctly figures out
-the size of every structure on its own.
-However,
-GHC simply reads @includes/Constants.h@ to to determine the size of
-closures assumed by the runtime system.
-Thus, we must change the constants used by the GHC itself (as opposed to
-the runtime system). They are all found in @includes/Constants.h@.
-We increase each of them by 1 to reflect the retainer set field which is one
-word long:
-\begin{code}
-/* includes/Constants.h */
-#define PROF_HDR_SIZE 2
-#define SCC_UF_SIZE 5
-#define SCC_SEQ_FRAME_SIZE 4
-\end{code}
-@PROF_HDR_SIZE@ denotes the size of the structure @StgProfHeader@, which
-is now two words long.
-@SCC_UF_SIZE@ and @SCC_SEQ_FRAME_SIZE@ denote the size of the structures
-@StgUpdateFrame@ and @StgSeqFrame@ (in @includes/Closures.h@) in
-words.
-
-Now we must rebuild the GHC so that, when executed, the code generated by
-the GHC must now allocate one more word for the retainer set field than before.
-
-\begin{code}
-./fptools/ghc/ make boot
-./fptools/ghc/ make
-\end{code}
-
-The second command @make boot@ instructs the build system to analyze
-the source code dependency so that the next execution of @make@ correctly
-finds all required files.
-
-Next we change four bitmap constants which specify the layout of
-certain types of closures.
-As an example, let us consider @RET_BITMAP@, which specifies the layout
-of thunk selectors (corresponding to closure type @THUNK_SELECTOR@).
-Without a retainer set field, there is only one non-pointer (represented
-by $1$) followed by one or more pointers (represented by $0$) in the closure
-body and the bitmap representation is $0b1$, or $1$.
-With a retainer set field, which is not a pointer to another closure and thus
-represented by $1$, there are two non-pointers, and the bitmap representation
-is $0b11$, or $3$. Notice that the bitmap is interpreted in reverse order:
-the least significant bit corresponds to the first word in the closure body,
-and the second least significant bit to the second word, and so forth.
-The same rule applies to the other three bitmap constants:
-@CATCH_FRAME_BITMAP@ (for closure type @CATCH_FRAME@ and structure
-@StgCatchFrame@),
-@STOP_THREAD_BITMAP@ (for closure type @STOP_FRAME@ and structure
-@StgStopFrame@), and
-@UPD_FRAME_BITMAP@ (for closure type @UPDATE_FRAME@ and structure
-@StgUpdateFrame@).
-
-\begin{code}
-/* rts/StgStdThunks.hc */
-#define RET_BITMAP 3
-/* rts/Exception.hc */
-#define CATCH_FRAME_BITMAP 15
-/* rts/StgStartup.hc */
-#define STOP_THREAD_BITMAP 3
-/* rts/updates.hc */
-#define UPD_FRAME_BITMAP 7
-\end{code}
-
-For most closure types, the new definition of @StgProfHeader@ is
-automatically propagated to their corresponding structures.
-However, there are six closures types which are not affected by
-@StgProfHeader@. They are all stack closures:
-@RET_DYN@, @RET_BCO@, @RET_SMALL@, @RET_VEC_SMALL@, @RET_BIG@, and
-@RET_VEC_BIG@.
-If you want a new field to be added to these closures, you may
-have to modify their corresponding structures.
-
-\textbf{To do:} Presently the above changes introduce two bug in the
-runtime system.
-First, @nofib/real/symalg@ ends up with a division-by-zero
-exception if we add a new field.
-Second, the runtime system option @-auto-all@ clashes in some test files
-in the @nofib@ testing suite (e.g., @spectral/expert@).
-
-\subsection{Initialization code}
-
-When a new closure is allocated, its retainer set field may have to be
-initialized according to the way that retainer profiling is implemented.
-For instance, we could use as an initial value a pointer to an empty retainer
-set.
-Alternatively we could assign a null pointer to indicate that its retainer
-set has not been computed yet, which we adopt in our implementation.
-In either case, we have to visit the new closure and execute some initialization
-code on it so that its retainer set field is set to an appropriate value.
-
-There are three parts in the source code which need to be modified.
-dynamic closure initialization, static closure initialization,
-and update frame initialization.
-The first is accomplished by modifying the macro @SET_PROF_HDR()@ (in
-@include/ClosureMacros.h@). When a closure @c@ is created at runtime,
-@SET_PROF_HDR()@ is invoked immediately with @c@ as its first argument.
-Thus, the following code initializes the retainer set field of every
-dynamic closure to a null pointer.
-
-\begin{code}
-/* include/ClosureMacros.h */
-#define SET_PROF_HDR(c,ccs_) \
- ((c)->header.prof.ccs = ccs_, (c)->header.prof.rs = NULL)
-\end{code}
-
-Similarly, the macro @SET_STATIC_PROF_HDR()@ (in the
-same file) specifies how the retainer set field of every static closure
-is initialized, which is rewritten as follows:
-
-\begin{code}
-/* include/ClosureMacros.h */
-#define SET_STATIC_PROF_HDR(ccs_) \
- prof : { ccs : ccs_, rs : NULL },
-\end{code}
-
-\textbf{Obsolete:} Dynamic closures created through explicit C function invocations
-(in @RtsAPI.c@) are now initialized by @SET_HDR()@.
-
-%There is another way of creating dynamic closures through explicit C
-%function invocations at runtime.
-%Such functions are all defined in @RtsAPI.c@: @rts_mkChar()@, @rts_mkInt()@,
-%@rts_mkWord()@, and so forth.
-%Each function allocates memory for a new closure,
-%initializes it, and returns its address.
-%Therefore, we can simply insert in each function another initialization code
-%for retainer set fields.
-%To this end, we define a macro @setRetainerField()@ and insert it
-%in each function:
-%
-%\begin{code}
-%#define setRetainerField(p) \
-% (p)->header.prof.rs = NULL
-%\end{code}
-%
-%For instance, @rts_mkChar()@ is now defined as follows:
-%
-%\begin{code}
-%/* RtsAPI.c */
-%HaskellObj
-%rts_mkChar (HsChar c)
-%{
-% StgClosure *p = (StgClosure *)allocate(CONSTR_sizeW(0,1));
-% ...
-% setRetainerField(p);
-% return p;
-%}
-%\end{code}
-
-Finally we may need to initialize the retainer set field of an update frame
-(stack closure) when it is pushed onto the stack for the first time.
-For instance, if we want to initialize the retainer set field of update
-frames to a null pointer, we can rewrite the macro @PUSH_STD_CCCS()@
-(in @includes/Updates.h@) as follows:
-
-\begin{code}
-/* includes/Updates.h */
-#define PUSH_STD_CCCS(frame) \
- (frame->header.prof.ccs = CCCS, frame->header.prof.rs = NULL)
-\end{code}
-
-In our implementation of retainer profiling, however, the retainer set field is not
-used for any stack closure.
-Hence, the above modification is entirely unnecessary.
-Also, update frames are the only exception to the standard way of creating
-stack closures: all the other types of stack closures with a retainer set
-field are eventually initialized by
-the macro @SET\_HDR()@ (in @includes/ClosureMacros.h@), which in turn
-invokes @SET\_PROF\_HDR()@. This is not the case for update frames.
-Compare @PUSH\_UPD\_FRAME()@ (in @includes/Updates.h@) and
-@PUSH\_SEQ\_FRAME()@ (in @includes/StgMacros.h@) for clarification.
-
-\section{Retainer Sets}
-
-At the end of retainer profiling, every live closure (except stack
-closures, for which we do not compute retainer sets) is associated with
-a retainer set; there can be no closure without an associated retainer set
-because every live closure is visited during traversal.
-Since many closures may well be associated with a common retainer set,
-we want to avoid creating any particular retainer set more than once.
-This section presents the details of manipulating retainer sets in our
-implementation.
-
-\subsection{Identity of a retainer}
-
-The function @R()@ in Figure~\ref{fig-retaineralgorithm} returns
-the identity of a retainer. In order to implement it, we need
-a type for retainer identity.
-The type @retainer@ (in @includes/StgRetainerProf.h@) is introduced for
-this purpose.
-
-There are various ways of defining the type @retainer@.
-For instance, we can designate the information table address of a retainer as
-its identity as follows:
-
-\begin{code}
-struct _StgInfoTable;
-typedef struct _StgInfoTable *retainer;
-\end{code}
-
-We can also use the cost centre stack associated with the retainer:
-
-\begin{code}
-typedef CostCentreStack *retainer;
-\end{code}
-
-The function @R()@ is embodied as the function @getRetainerFrom()@ in the
-implementation, whose type is @(StgClosure *)@ $\rightarrow$ @retainer@.
-It is straightforward to define @getRetainerFrom()@ according to the definition
-of @retainer@, as illustrated below:
-
-\begin{code}
-retainer getRetainerFrom(StgClosure *c) { return get_itbl(c); }
-retainer getRetainerFrom(StgClosure *c) { return c->header.prof.ccs; }
-\end{code}
-
-\subsection{Retainer sets and the cost function}
-
-A retainer set is stored in the structure @retainerSet@
-(in @includes/StgRetainerProf.h@):
-
-\begin{code}
-typedef struct _retainerSet {
- nat num;
- nat cost;
- ...
- int id;
- retainer element[0];
-} retainerSet;
-\end{code}
-
-The field @num@ gives the number of retainers in the retainer set, which
-are all stored in the array @element[]@. Thus, the size of @element[]@
-is assumed to be @num@.
-The field @cost@ gives the sum of the \emph{costs} of those closures
-associated with the retainer set: if a closure @c@ is
-associated with the retainer set, that is, if @c@ is retained by each
-retainer in the retainer set and none else,
-the cost of @c@ is added to the field @cost@.
-The field @id@ gives a unique identification number for the retainer set.
-
-The interface to @retainerSet@ is as follows
-(see @RetainerSet.h@):
-
-\begin{description}
-\item[@void initializeAllRetainerSet(void)@] initializes the store for retainer sets.
-\item[@void refreshAllRetainerSet(void)@] refreshes each retainer set by setting
-its @cost@ field to zero. This function does destroy any retainer set.
-\item[@void closeAllRetainerSet(void)@] destroys all retainer sets and closes
-the store for retainer sets.
-\item[@retainerSet *singleton(retainer r)@] returns a singleton retainer set
-consisting of @r@ alone. If such a retainer set already exists, no new retainer
-set is created. Otherwise, a new retainer set is created.
-\item[@retainerSet *addElement(retainer r, retainerSet *rs)@] returns a retainer set
-@rs@ augmented with @r@. If such a retainer set already exists, no new retainer set
-is created. Otherwise, a new retainer set is created.
-\item[@rtsBool isMember(retainer r, retainerSet *rs)@] returns a boolean value
-indicating whether @r@ is a member of @rs@.
-\item[@void traverseAllRetainerSet(void (*f)(retainerSet *))@] invokes the function
-@f@ on every retainer set created.
-\item[@void printRetainerSetShort(FILE *, retainerSet *)@] prints a single retainer
-set.
-\item[@void outputRetainerSet(FILE *, nat *allCost, nat *numSet)@] prints all
-retainer sets. Stores the sum of all their costs in @*allCost@ and the number
-of them in @*numSet@.
-\item[@void outputAllRetainerSet(FILE *)@] prints all retainer sets.
-\end{description}
-
-We also define a \emph{cost function}, which returns the cost of a given closure,
-in order to compute the field @cost@.
-The cost function can be defined in several ways.
-A typical definition is on the size of a closure, which results in
-the field @cost@ accumulating the size of all the closures retained by a
-retainer set.
-If we just want to count the number of closures retained by the
-retainer set, we can simply set the cost of every closure to one regardless
-of its closure type.
-Furthermore, we can define the cost function flexibly according to
-the closure type.
-For instance, we can set the size of any static closure to zero so that
-it is not taken into account at all in computing the field @cost@.
-Notice that static closures are also visited during traversal because they
-may lead to other dynamic closures (e.g., static indirection closures of
-closure type @IND_STATIC@).
-This is especially desirable because we usually focus on the heap use.
-We can also selectively choose certain dynamic closure types not to contribute
-to the field @cost@.
-
-In our implementation, there are two functions related with the cost function:
-@cost()@ and @costPure()@.
-@cost()@ returns the size of the entire memory allocated for a given closure
-(even including the two fields in the structure @StgProfHeader@).
-It returns zero for static closures.
-@costPure()@ returns the size of the memory which would be allocated for
-a given closure with no profiling.
-It is defined in terms of @cost()@, and it suffices to change only @cost()@
-when a new scheme for the cost function is desired.
-@costPure()@ is put to actual use in computing the field @cost@ because it
-effectively hides the memory overhead incurred by profiling.
-
-\subsection{Implementation}
-
-The algorithm for retainer profiling in Figure~\ref{fig-retaineralgorithm}
-adds at most one retainer to an existing retainer set (or an empty retainer set)
-at any moment; it does not require a retainer set union operation.
-This observation simplifies the implementation, and
-we employ the following two functions for creating new retainer sets:
-@singleton()@, which creates a singleton retainer set, and
-@addElement()@, which adds an element to an existing retainer set.
-
-It is a frequent operation during retainer profiling to search for a retainer
-set, which may or may not exist, built from a given retainer set and a
-particular retainer.
-To efficiently implement this operation,
-we choose to store all retainer sets in a hash table and
-the structure @retainerSet@ is now extended with two new fields
-@hashKey@ and @link@.
-The field @hashKey@ stores the hash key which is obtained
-from the retainers in a retainer set.
-The field @link@ points to the next retainer set in the same bucket:
-
-\begin{code}
-typedef struct _retainerSet {
- ...
- StgWord hashKey;
- struct _retainerSet *link;
- ...
-} retainerSet;
-\end{code}
-
-The hashing function must be defined in such a way that a retainer set
-can have only one unique hash key regardless of the order its elements
-are stored, i.e., the hashing function must be additive.
-
-It is often observed that two successive executions of retainer profiling share
-a number of retainer sets in common, especially if the two executions are
-close in time.
-This also implies that the number of all retainer sets which can be created
-at any moment does not grow indefinitely regardless of the interval at which
-retainer profiling is performed; it does not grow commensurately with the
-number of times retainer profiling is executed.
-This observation eliminates the need to free the memory allocated for
-retainer sets; we can simply set the @cost@ field of every retainer set
-to zero after each retainer profiling and reuse it during the next time.
-
-\section{Graph Traversal}
-
-At the heart of retainer profiling lies \emph{graph traversal};
-the algorithm in Figure~\ref{fig-retaineralgorithm} is supposed to visit
-every closure in the graph at least once and yield statistics on the heap use.
-Since only live closures are reachable from the root, the algorithm
-does not deal with dead closures.
-
-This section presents details on how to achieve an efficient implementation of
-graph traversal without incurring extra memory overhead and compromising speed.
-
-\subsection{Goal}
-
-Traversing a graph itself can be done in a straightforward way;
-we choose either depth first search or breadth first search, and traverse
-the graph starting from a given set of roots.
-After a complete traversal, each live closure @c@ (including static closures)
-has an associated retainer set, whose address is stored in the field
-@c->header.prof.rs@.
-
-A real complication arises when retainer profiling is performed once again:
-all live closures which have survived all garbage collections since
-the previous retainer profiling
-still have an associated retainer set (indicated by
-a non-null pointer in their retainer set field), which is no longer
-valid. Any new closure created since then has
-a null pointer in its retainer set field at the beginning of retainer
-profiling and will become associated with a retainer set.
-Thus, we can no longer distinguish valid retainer set fields
-from invalid ones.
-
-A simple remedy is to linearly scan the heap at the beginning of each
-retainer profiling and set all retainer set fields to a null pointer.
-It resets the retainer set field of each dynamic closure, whether it is
-live or not with respect to the given set of root.
-This is feasible because any closure in the heap directly adjoins the
-next closure, if any.
-The problem is that we have no way of visiting all live static closures,
-for which we compute retainer sets.
-
-A moment of thought, however, reveals that we can completely avoid computing
-retainer sets for static closures. This is because retainer profiling is
-concerned only about the heap, which consists of dynamic closures and no
-static closures. In other words, we can treat every static closure as
-a bridge connecting two dynamic closures.
-For instance, if a dynamic closure @c@$_1$ has a pointer to a static
-closure @s@ and @c@ has a pointer to another dynamic closure @c@$_2$,
-we can think of the pointer in @c@$_1$ as a direct pointer to @c@$_2$.
-The big problem is that if the graph has a cycle containing static closures,
-an infinite loop occurs. In other words, we have no way of telling whether
-a static closure has been visited or not and are forced to compute
-retainer sets for static closures as well.\footnote{For instance,
-a static closure is allowed to have a self-reference in its SRT, which
-is also followed during retainer profiling.}
-
-Another remedy is to stores in every closure a time stamp for the
-retainer set field. The time stamp indicates whether the retainer
-set field is valid or no longer valid (i.e., it is for the previous
-retainer profiling).
-At the cost of one extra field in each closure, we can achieve an
-elegant implementation with little complication.
-However, it turns out that the memory overhead is too big.\footnote{A typical
-dynamic closure is only two or three words long.}
-Thus, our goal is to stick to the definition of the structure @StgProfHeader@
-given earlier and yet to achieve an elegant solution.
-
-\subsection{Basic plan}
-
-Since we visit every live object and update its retainer set field,
-any retainer set field can either be valid (the corresponding retainer
-set is valid) or point to a retainer set created during the previous
-retainer profiling.
-In order to distinguish valid retainer set fields
-from invalid ones, we exploit the least significant bit of the retainer
-set field: we maintain a one bit mark which flips over every time
-retainer profiling is performed, and judge that a retainer set field is
-valid only if its least significant bit matches the mark.
-The variable @flip@ serves for this purpose.
-The macros @isRetainerSetFieldValid()@ tests if the retainer set field
-of a give closure @c@ is valid:
-
-\begin{code}
-#define isRetainerSetFieldValid(c) \
- ((((StgWord)(c)->header.prof.rs & 1) ^ flip) == 0)
-\end{code}
-
-As an example, a retainer set field can be set to a null value conforming
-the current value of @flip@ by the macro @setRetainerSetToNull()@:
-
-\begin{code}
-#define setRetainerSetToNull(c) \
- (c)->header.prof.rs = (retainerSet *)((StgWord)NULL | flip)
-\end{code}
-
-Now, when a dynamic closure @c@ is created, its retainer set field is
-initialized to a null value conforming to the current value of
-@flip@:\footnote{Actually this is not mandatory: even when the null
-value does not conform to the current value of @flip@, it will be replaced
-by a correct null value when @c@ is visited later.}
-
-\begin{code}
-extern StgWord flip;
-#define SET_PROF_HDR(c,ccs_) \
- ((c)->header.prof.ccs = ccs_, (c)->header.prof.rs = (retainerSet *)((StgWord)NULL | flip))
-\end{code}
-
-We do not need to revise @SET_STATIC_PROF_HDR()@ if the initial value of
-@flip@ is set to $0$.\footnote{For the same reason, an initial value $1$
-does not compromise the correctness of the implementation.}
-
-\subsection{Set of roots}
-
-The set of roots consists of all thread closures (running, sleeping, or
-blocked) existing at the beginning of a retainer profiling.
-It is handily obtained in an indirect way by invoking the function
-@GetRoots()@ (in @Schedule.c@) with an appropriate argument, which must be
-a function:
-@GetRoots()@ invokes on each root known to the runtime system its argument.
-Thus, we implement a function @retainClosure()@, which initiates traversal
-from a given root and updates the retainer set of every closure reachable
-from the root,
-and invokes @GetRoots()@ with @retainClosure@ as an argument.
-
-In addition to the thread closures, weak pointers are also considered
-as roots; they may not be reachable from any thread closure yet are still
-being in used.
-A weak pointer has three pointer fields: @key@, @value@, and
-@finalizer@ (see the structure @StgWeak@ in @includes/Closures.h@).
-It turns out that these pointers may not be valid all the time:
-at a certain point during execution, for instance, the pointer @key@ may point
-to a dead closure.
-However, right after a major garbage collection, all the three pointers are
-guaranteed to be valid, i.e., they all point to live closures.
-This facilitates the handling of weak pointers if we choose to
-perform retainer profiling immediately after a major garbage collection.
-All weak pointers are found in the linked list @weak_ptr_list@
-(in @Weak.c@).
-
-See the function @computeRetainerSet()@ for details.
-
-\subsection{Static closures}
-
-When a live dynamic closure @c@ is visited for the first time during traversal,
-its retainer set field is checked against the current value of @flip@.
-If it was created at some point since the previous retainer profiling,
-its retainer set field is already set to a correct null value.
-Otherwise, it must have been visited
-during the previous retainer profiling and thus its retainer set field is
-invalid and will be set to a correct null value.
-Therefore it is unnecessary to visit all dynamic closures and set their
-retainer set field to a correct null value at the beginning of each retainer
-profiling.
-
-However, this operation is required for static closures.
-The reason is that a static closure, which is never garbage collected,
-may appear alternately in the set of live closures.
-In other words, a currently live static closure may become dead and
-be resuscitated again.
-Therefore, for a static closure, it does not help to check if its
-retainer set field conforms to the current value of @flip@.
-For instance,
-if a static closure happens to belong to the set of live closures every other
-retainer profiling, its retainer set field will never set to a null value,
-which is disastrous.
-Therefore, we choose to visit all live static closures at the beginning
-of each retainer profiling and set their retainer set field to a
-correct null value.
-
-In order to find all live static closures, we have each retainer
-profiling preceded by a major garbage collection, which knows all live
-static closures.\footnote{This is a heavy
-restriction on retainer profiling, which makes retainer profiling partially
-dependent on garbage collection.
-However, it does not affect any retainer profiling result because
-retainer profiling considers only live closures, which survive any
-garbage collection.}
-To be specific, the garbage collector builds a linked list
-@scavenged_static_objects@ (in @GC.c@) during a major garbage collection,
-which stores all live static closures of our interest.
-\footnote{
-A static closure of closure type @IND\_STATIC@ may be put in the
-list @mut\_once\_list@ of the oldest generation, instead of the list
-@scavenged\_static\_objects@.
-In our implementation, such a closure is just skipped over because it
-contains only a pointer to a dynamic closure, and we do not compute
-its retainer set.
-Thus, there is no need to traverse the list @mut\_once\_list@ of the oldest
-generation.}
-Since it destroys the linked list after finishing the major garbage collection
-(by invoking the function @zero_static_object_list()@ with
-@scavenged_static_objects@ as its argument),
-we traverse the linked list to set the retainer set field of each
-live static closure to a correct null value before its destruction.
-This is done by invoking the function
-@resetStaticObjectForRetainerProfiling()@.
-
-\textbf{To do:} In the current implemenation, if a static closure has no child
-(e.g., @CONSTR_NOCAF_STATIC@, @THUNK_STATIC@ with an empty SRT, and
-@FUN_STATIC@ with an empty SRT), we do not compute its retainer set (because
-there is no need to do). This slight optimization allows us to render
-retainer profiling no longer dependent on garbage collection due to the
-following propoerty:
-
-\begin{center}
-A static closure can alternately appear and disappear in the set of live
-closures across multiple executions of retainer profiling if and only if
-it has an empty SRT and no child.
-\end{center}
-
-Then we can completely eliminate the function
-@resetStaticObjectForRetainerProfiling()@.
-
-\subsection{Traversal}
-
-The traversal proceeds in a depth first manner and is implemented
-with two mutually recursive functions: @retainStack()@ and @retainerClosure()@.
-@retainerStack()@ can be invoked on dynamic closures holding a stack chunk:
-closure types @TSO@, @PAP@, and @AP_UPD@.
-It in turn invokes @retainerClosure()@ on each closure reachable from
-stack closures in the stack chunk. Notice that it does not invoke
-@retainerClosure()@ on those stack closures because we do not compute
-retainer sets for stack closures.
-@retainerClosure()@ iteratively traverses all live closures reachable
-from a given closure.
-It maintains its own stack to record the next scan position in every closure
-currently under consideration.\footnote{A recursive version of
-@retainerClosure()@ could be implemented easily.
-@retainerClosure()@ in our implementation is an iterative version.}
-When it encounters a closure holding a stack chunk, it invokes @retainerStack()@
-on that closure.
-Hence,
-the traversal is triggered simply by invoking @retainerClosure()@ on every root.
-
-\textbf{To do:}
-The correctness of retainer profiling is subject to the correctness
-of the two macros @IS_ARG_TAG()@ and @LOOKS_LIKE_GHC_INFO()@
-(see @retainStack()@). Since
-@LOOKS_LIKE_GHC_INFO()@ is a bit precarious macro, so I believe that
-the current implementation may not be quite safe. Also, @scavenge_stack()@
-in @GC.c@ also exploits this macro in order to identify shallow pointers.
-This can be a serious problem if a stack chunk contains some
-word which looks like a pointer but is actually not a pointer.
-
-\subsection{Sanity check}
-
-Since we assume that a retainer profiling is preceded by a major garbage
-collection,
-we expect that the size of all the dynamic closures visited during
-any retainer profiling adds up exactly to the total size of the heap.
-In fact, this is not the case; there can be closures not reachable from
-the set of roots yet residing in the heap even after a major garbage
-collection.
-
-First, a dead weak pointer remains in the heap until its finalizer
-finishes. Although its finalizer thread closure is part of the set of roots,
-the dead weak pointer itself is not reachable from any root.
-Since it cannot be visited during retainer profiling anyhow, we do not
-need to located it and set its retainer set field
-appropriately.\footnote{Dead weak pointers are identified with their
-information table @stg\_DEAD\_WEAK\_info@ (in @StgMiscClosures.hc@).
-Notice that their closure type is @CONSTR@, \emph{not} @WEAK@;
-their information table is replaced by @stg\_DEAD\_WEAK\_info@ in the
-function @scheduleFinalizers()@ (in @GC.c@).}
-
-Second,
-mutable variables (of closure type @MUT_VAR@) may remain in the heap
-even when they are not reachable from the set of roots while
-dynamic closures pointed to by them must be live.\footnote{I do not
-understand clearly why this happens :(}
-Since such mutable variables may become live again (in the sense that
-they become reachable from the set of roots), we must locate them
-and set their retainer set field appropriately after each retainer
-profiling. This is handily accomplished by traversing the list
-@mut_once_list@ in every generation.
-
-\section{Retainer Profiling Schemes}
-
-A retainer profiling scheme specifies \emph{what} retainer profiling
-yields (as opposed to \emph{how} retainer profiling computes the retainer
-set for every live object).
-It is determined primarily by the meaning of retainer identity,
-that is, the type @retainer@ (in @includes/StgRetainerProf.h@).
-The function @getRetainerFrom()@ must be defined according to the
-definition of the type @retainer@.
-
-In order for a new retain profiling scheme to fully work, we need to follow
-four steps:
-
-\begin{enumerate}
-\item Define the type @retainer@ as desired.
-\item Write @getRetainerFrom()@.
-\item Write two hashing functions @hashkeySingletone()@ and
- @hashKeyAddElement()@, which return the hash key from a single
- retainer and a retainer set with another retainer, respectively.
-\item Write two printing functions @printRetainer()@ and
- @printRetainerSetShort()@.
- These functions are employed when a retainer or a retainer set is
- printed in the output file.
-\end{enumerate}
-
-In our implementation, we use cost centre stacks for retainer identity:
-
-\begin{code}
-typedef CostCentreStack *retainer;
-\end{code}
-\begin{code}
-retainer getRetainerFrom(StgClosure *c) { return c->header.prof.ccs; }
-\end{code}
-\begin{code}
-void printRetainer(FILE *f, retainer cc)
-{
- fprintf(f,"%s[%s]", cc->label, cc->module);
-}
-\end{code}
-
-\textbf{To do:} All the closures created by @rts_mk...()@ in @RtsAPI.c@ are given
-@CCS_SYSTEM@ as their cost centre stacks. This may not be accurate indeed,
-and, for instance, @CCCS@ may be a better choice than @CCS_SYSTEM@.
-
-\section{Usage}
-
-Since cost centre stacks are used as retainer identity, a source program
-must be given proper cost centre annotations by programmers.
-Alternatively,
-we can ask the compiler to automatically insert cost centre annotations.
-For instance, the compiler option @-auto-all@ inserts a cost centre
-annotation around every top-level function as shown below
-(the @-p@ option is a must
-because we must build the executable file in a profiling way):
-
-\begin{code}
-$ ghc-inplace -o Foo.out -p -auto-all Foo.hs
-\end{code}
-
-The runtime system option @-hR@ tells the executable program to
-gather profiling statistics and report them in a @.prof@ file:
-
-\begin{code}
-$ Foo.out +RTS -hR -RTS
-\end{code}
-
-The option @-i@ can be used to
-specify a desired interval at which retainer profiling is performed.
-The default and minimum value is half a second:
-
-\begin{code}
-$ Foo.out +RTS -hR -i2.5 -RTS
-\end{code}
-
-Then, two text files are generated: a @.prof@ file and a @.hp@ file.
-The @.prof@ file records the progress of retainer profiling:
-for each retainer profiling performed during program execution,
-it shows
-the Haskell mutator time (as opposed to the user time) at which
-the retainer profiling starts,
-the average number of times a closure is visited,
-the sum of costs assigned to all retainer sets (obtained from the field
-@cost@ in each retainer set),
-and the number of all retainer sets created \emph{since} the beginning
-of program execution.
-A typical entry in a @.prof@ file looks like:
-
-\begin{code}
-Retainer Profiling: 3, at 3.530000 seconds
- Average number of visits per object = 1.687765
- Current total costs = 801844
- Number of retainer sets = 118
-\end{code}
-
-The sum of costs assigned to all retainer sets may \emph{not} be equal to the
-size of the heap.
-The discrepancy is attributed to those live object which are not reachable
-from the set of roots.
-Still it is a good estimate of the size of the heap at the moment when
-the retainer profiling was performed.
-
-The @.prof@ file also shows the contents of every retainer set which
-has been assigned a positive cost (i.e., the field @cost@) at least once;
-not every retainer set created is assigned a positive cost because quite
-a few retainer sets are created as intermediate retainer sets before
-creating a real retainer set. This results from the restriction on the way
-retainer sets are created (only one retainer can be added to an existing
-retainer set at a time).
-
-An example of the contents of a retainer set is:
-
-\begin{code}
-SET 71 = {<doFile[Main],main[Main],MAIN[MAIN]>, <synth_2[Main],doFile[Main],main[Main],MAIN[MAIN]>}
-\end{code}
-
-The retainer set has an identification number $71$.
-It is associated with two retainers, whose retainer identities are shown
-inside angle brackets @<...>@.
-For instance, the first retainer is created when the cost centre stack
-is @doFile[Main],main[Main],MAIN[MAIN]@, shown from the top to the bottom.
-Each entry in angle brackets consists of a cost centre name (e.g., @doFile@)
-and its module name (e.g., @Main@).
-
-The @.hp@ file can be supplied to the @hp2ps@ program to create a postscript
-file showing the progress of retainer profiling in a graph:
-
-\begin{code}
-$ hp2ps Foo.hs
-$ gv Foo.ps
-\end{code}
-
-An example of such a graph is shown in Figure~\ref{fig-cacheprof}.
-It shows the cost assigned to each retainer set at the point
-when a retainer profiling is performed (marked by a corresponding inverted
-triangles on the horizontal axis).
-The abbreviated contents of each retainer set is displayed in the right column.
-Due to the space limitation,
-it shows only topmost cost centres (without module names)
-instead of printing the full contents.
-For instance, @(71)doFile,synth_2@ corresponds to a retainer set shown above
-(@71@ is its identification number).
-The contents may be truncated if it is too long.
-
-Notice that the time is in the Haskell mutator time, which excludes
-the runtime system time such as garbage collection time and retainer profiling
-time. Thus, the actual execution takes longer than indicated in the
-graph. Also, the timer employed to periodically perform retainer profiling
-is not perfectly accurate. Therefore, the result may slightly vary for each
-execution of retainer profiling.
-
-\begin{figure}[ht]
-\centering
-\epsfig{file=cacheprof_p.eps,width=5in}
-\caption{A graph showing the progress of retainer profiling}
-\label{fig-cacheprof}
-\end{figure}
-
-\section{Comparision with nhc}
-
-\section{Files}
-
-This section gives a summary of changes made to the GHC in
-implementing retainer profiling.
-Only three files (@includes/StgRetainerProf.h@, @RetainerProfile.c@, and
-@RetainerProfile.h@) are new, and all others exist in the GHC.
-
-@\includes@ directory:
-
-\begin{description}
-\item[StgRetainerProf.h] defines types @retainer@ and @retainerSet@.
-\item[Stg.h] includes the header file @StgRetainerProf.h@.
-\item[Closures.h] changes structure @StgProfHeader@.
-\item[Constants.h] changes constants @PROF_HDR_SIZE@, @SCC_UF_SIZE@, and
- @SCC_SEQ_FRAME_SIZE@.
-\item[ClosureMacros.h] changes macros @SET_PROF_HDR()@ and
- @SET_STATIC_PROF_HDR()@.
-\item[Updates.h] changes macro @PUSH_STD_CCCS()@.
-\end{description}
-
-@\rts@ directory:
-
-\begin{description}
-\item[Exception.hc] changes constant @CATCH_FRAME_BITMAP@,
-\item[StgStartup.hc] changes constant @STOP_THREAD_BITMAP@.
-\item[StgStdThunks.hc] changes constant @RET_BITMAP@.
-\item[Updates.hc] changes constant @UPD_FRAME_BITMAP@.
-\item[RetainerProfile.c] implements the retainer profiling engine.
-\item[RetainerProfile.h] is the header for @RetainerProfile.c@.
-\item[RetainerSet.c] implements the abstract datatype @retainerSet@.
-\item[RetainerSet.h] defines the interface for @retainerSet@.
-\item[GC.c] invokes @resetStaticObjectForRetainerProfiling()@ in
- @GarbageCollect()@.
-\item[Itimer.c] changes @handle_tick()@.
-\item[ProfHeap.c] changes @initHeapProfiling()@ and @endHeapProfiling()@.
-\item[Profiling.c] changes @initProfilingLogFile()@ and
- @report_ccs_profiling()@.
-\item[Proftimer.c] declares @ticks_to_retainer_profiling@,
- @performRetainerProfiling@, and @doContextSwitch@.
-\item[Proftimer.h] is the header for @Proftimer.c@. Defines @PROFILING_MIN_PERIOD@,
- which specifies the minimum profiling period and the default profiling period.
-%\item[RtsAPI.c] implements @setRetainerField()@.
-\item[RtsFlags.c]
- sets @RtsFlags.ProfFlags.doHeapProfile@ and
- adds a string to @usage_text[]@ in @setupRtsFlags()@.
-\item[RtsFlags.h] defines constants @HEAP_BY_RETAINER@ and @RETAINERchar@.
-\item[RtsStartup.c] includes the header file @RetainerProfile.h@.
- Changes @shutdownHaskell()@.
-\item[Schedule.c] changes @schedule()@.
-\item[Stats.c]
- declares @RP_start_time@, @RP_tot_time@, @RPe_start_time@,
- @RPe_tot_time@.
- Changes @mut_user_time_during_GC()@, @mut_user_time()@,
- @stat_startExit()@,
- @stat_endExit()@, and
- @stat_exit()@.
- Defines
- @mut_user_time_during_RP()@,
- @stat_startRP()@, and
- @stat_endRP()@.
-\item[Stats.h] is the header for @Stats.c@.
-\item[StgMiscClosures.hc] redefines @stg_DEAD_WEAK_info@.
-\item[Storage.c] changes @initStorage()@, @memInventory()@.
-\end{description}
-
-\bibliographystyle{plain}
-\bibliography{reference}
-
-\end{document}
projects / ghc-hetmet.git / blobdiff