X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=ghc%2Fdocs%2Fstorage-mgt%2Frp.tex;fp=ghc%2Fdocs%2Fstorage-mgt%2Frp.tex;h=79975ab63e2de5213a828f0d9cd1d40d70d9e4cf;hb=1ff1d1f21de84d4a24573c736573dabf0d7e3e6a;hp=0000000000000000000000000000000000000000;hpb=1c2f7e7126127fc9191aee7672618520b6b310c5;p=ghc-hetmet.git diff --git a/ghc/docs/storage-mgt/rp.tex b/ghc/docs/storage-mgt/rp.tex new file mode 100644 index 0000000..79975ab --- /dev/null +++ b/ghc/docs/storage-mgt/rp.tex @@ -0,0 +1,1027 @@ +\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} + +\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 identity of a given retainer such +as its memory address, 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 determined +uniquely by: 1) the set of roots; 2) the function @R()@; 3) the function +@isRetainer()@. + +\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@, @R(r)@ $\in$ @r.retainerSet@. +\item For every object @c@, +$\bigcup_{\mathit{each\ ancestor\ @a@\ of\ @c@}}$ @from(a)@ $\subseteq$ +@c.retainerSet@. +\item @from(a)@ = if @isRetainer(a)@ then @a.retainerSet@ else $\{@a@\}$. +\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@} + +\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 +./ cvs checkout fptools +\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 + GhcLibWays = p + 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/ rm dll green-card haggis happy hdirect hood libraries +./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, +the GHC simply reads @includes/Constants.h@ to to determine the size of +closures assumed by the runtime system. +Thus, we 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. + +Since these constants are used when building the GHC (by another compiler), +we must rebuild the GHC. In other words, when executed, the code generated by +the GHC must now allocate one more word for the retainer set field than before, +and hence it is inevitable to rebuild the GHC, which is done as follows: + +\begin{code} +./fptools/ghc/ make clean +./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:} Currently the above changes introduce a new bug in the +runtime system. For instance, @nofib/real/symalg@ ends up with a division-by-zero +exception if we add a new field. + +\subsection{Initialization code} + +When a new closure is created, 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 four parts in the source code which need to be modified. +dynamic closure initialization, static closure initialization, +closure creation through C function invocation, +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} + +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.\footnote{In our implementation of +retainer profiling, the retainer set field is not used for any stack closure. +Hence, the following 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.} +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} + +\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. + +We 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()@. + +\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. + +\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} + +\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 = {, } +\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[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@. +\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}