--- /dev/null
+\documentclass{article}
+\usepackage{code,a4wide}
+
+\usepackage{graphics,epsfig,epic,eepic}
+
+\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{The GHC Storage Manager}
+\author{Simon Peyton-Jones and Sungwoo Park}
+
+\makeatactive
+\maketitle
+\section{Introduction}
+
+This document describes the details of the GHC storage manager, including
+the interface and implementation of each of its components.
+
+\section{Goals}
+
+Storage management goals are:
+\begin{itemize}
+\item Generational collection, supporting multiple generations.
+\item The ability to pin the allocation
+area into a few pages that we hope will fit entirely in the cache.
+\item Allows objects to age within a generation before getting promoted.
+\item Heap can grow as needed, rather than having to be pre-sized
+ by the programmer.
+\item We support mark/sweep/compact collection for older generations.
+This is a Good Thing when the live memory approaches the available
+physical memory, because it reduces paging.
+\item Little OS support needed. No @mmap()@ etc. All that we require is
+ the ability to call @malloc()@ to allocate a new chunk of memory.
+ There can be intervening ``sandbars'' allocated by other programs
+ (e.g. DLLs or other @malloc()@'d structures) between chunks of heap.
+\end{itemize}
+
+Language-support goals are:
+\begin{itemize}
+\item The garbage collector ``shorts out'' indirection objects introduced
+by the mutator (notably when overwriting a thunk with an indirection).
+\item The garbage collector executes selector thunks.
+For example, a thunk for
+@(fst x)@ where @x@ is a pointer to a pair @(a,b)@ would be
+evaluated by the garbage collector to just @a@. This is an important
+strategy for plugging space leaks.
+\item The garbage collector traversese the code tree, as well as
+the heap data structures, to find which CAFs are live. This is a royal pain.
+\item The garbage collector finalises some objects (typically a tiny minority).
+At the moment ``finalisation'' means ``call a C routine when this thing
+dies'' but it would be more general to schedule a call to a Haskell
+procedure.
+\end{itemize}
+
+Instrumentation goals are:
+\begin{itemize}
+\item The garbage collector can gather heap-census information for profiling.
+To this end we can force GC to happen more often than it otherwise would,
+and the collector can gather information about the type and cost-centre
+associated with each heap object.
+\end{itemize}
+
+\section{The architecture of the storage manager}
+
+The storage manager is a component of the GHC system which is responsible
+for allocating fresh memory for new objects and reclaiming memory
+that is no longer used.
+It is built on a layered architecture and consists of four main parts:
+\emph{megablock allocator}, \emph{block allocator}, \emph{heap allocator},
+and \emph{garbage collector} (Figure~\ref{fig-architecture}).
+The megablock allocator communicates directly with the underlying
+operating system and forms the lowest level of the storage manager.
+The heap allocator and garbage collector lie in the topmost level of
+the storage manager and process requests from
+the mutator (the Haskell realm at the runtime) and the runtime system.
+The block allocator lies between the two levels.
+
+\begin{figure}[ht]
+\begin{center}
+\input{architecture.eepic}
+\caption{The overall architecture of the storage manager}
+\label{fig-architecture}
+\end{center}
+\end{figure}
+
+\section{The megablock allocator}
+
+% need more elaboration - Sung
+The megablock allocator implements a direct interface to the underlying
+operating system.
+It can request a chunk of physical memory of a fixed size,
+which is called a \emph{megablock}, from the operating system and returns it
+to the block allocator. A new megablock is not initialized by the
+megablock allocator; it is later initialized by the block allocator.
+
+\subsection{Interface}
+
+\begin{description}
+\item[@void *getMBlock()@] allocates a single megablock and returns its
+starting address.
+\item[@void *getMBlocks(nat n)@] allocates @n@ contiguous megablocks
+and returns their starting address.
+\end{description}
+
+\subsection{Implementation}
+
+Since the megablock allocator communicates directly with the underlying
+operating system, its implementation relies on memory allocation functions
+provided by the operating system; thus, the implementation varies between
+platforms.
+However, every megablock is always of a fixed size $2^M$ and aligned on a
+$2^M$ boundary, regardless of the platform
+(@MBLOCK_SIZE@ in @include/Constants.h@ defines the size of megablocks).
+@mblocks_allocated@ in @MBlock.c@ stores the number of megablocks allocated.
+
+For implementation details, see @MBlock.c@, @MBlock.h@, @include/Block.h@.
+
+\section{The block allocator}
+
+The block allocator divides a megablock returned by the megablock allocator
+into a contiguous group of \emph{block descriptors} followed by another
+contiguous group of \emph{blocks}.
+
+A block is a contiguous chunk of $2^K$ bytes, starting on
+a $2^K$-byte boundary (@BLOCK_SIZE@ in
+@include/Constants.h@ defines the size of blocks).
+Each block has its own associated block descriptor, which records the
+current state of the block.
+
+Figure~\ref{fig-megablock} shows a megablock after initialization by the
+megablock allocator.
+Block descriptors occupy the lower address space and blocks the higher address
+space in the megablock.
+A block is the unit of allocation for the block allocator.
+That is, the block allocator hands over store to the heap allocator in multiples of
+one block, where multiple heap objects may be allocated.
+A contiguous group of blocks, which is called a \emph{block group}, can be
+directly handed over to the heap allocator to reduce inter-block
+linkage costs.
+The first block of a block group is called the \emph{group head}.\footnote{
+An alternative design has the block descriptor at the start of each block.
+This makes it easy to locate the block descriptor corresponding to a particular
+block, but is pessimistic for cache locality when fiddling with block descriptors.
+It also means that only the first block in a contiguous chunk of blocks can
+have a block descriptor. This in turn makes it difficult to achieve an
+efficient mostly-copying conservative (MCC) garbage collector.}
+Since block descriptors are ordered linearly, we can always locate a block
+descriptor corresponding to a particular block from the starting address
+of the block.
+
+\begin{figure}[ht]
+\begin{center}
+\input{megablock.eepic}
+\caption{A megablock after initialization}
+\label{fig-megablock}
+\end{center}
+\end{figure}
+
+\subsection{Interface}
+
+\begin{description}
+\item[@typedef struct bdescr@] is the type of block descriptors.
+\item[@void initBlockAllocator(void)@] initializes the block allocator.
+\item[@bdescr *allocBlock(void)@] requests a single block and returns
+the address of its block descriptor.
+\item[@bdescr *allocGroup(nat n)@] allocates a block group of size @n@
+and returns the address of the block descriptor for the group head.
+\item[@void freeGroup(bdescr *p)@] frees the block group where @p@ points
+to the block descriptor of the group head, and places it in a pool of
+free block groups.
+\item[@bdescr *Bdescr(StgPtr p)@] takes a pointer @p@ to any byte within
+a block and returns a pointer to its block descriptor. It is implemented as
+an @inline@ procedure.
+\end{description}
+
+\subsection{Block descriptors}
+
+A block descriptor has the following structure, defined in
+@include/Blocks.h@:
+
+\begin{code}
+typedef struct _bdescr {
+ StgPtr start;
+ StgPtr free;
+ StgWord32 blocks;
+ struct _bdescr *link;
+ /* additional fields */
+} bdescr;
+\end{code}
+
+The fields of a block descriptor have the following purposes:
+
+\begin{description}
+\item[@start@] points to the first byte of the corresponding block.
+\item[@free@] For a group head, @free@ points to the first free byte in
+the block group. For a non-group head, @free@ is set to zero to identify
+the corresponding block as a non-group head.
+\item[@blocks@] For a group head, @blocks@ stores the number of blocks
+in the block group. It is not used for non-group heads.
+\item[@link@] For a group head, @link@ is used to chain all individual
+blocks or block groups together. For a non-group head, @link@ points
+to the block descriptor of the group head.
+\end{description}
+
+\subsection{Implementation}
+
+The block allocator maintains a linked list of free block groups, whose head
+is stored in @free_list@ in @BlockAlloc.c@ (Figure~\ref{fig-freelist}).
+When @allocBlock()@ or @allocGroup()@ is called, the block allocator
+scans the linked list from @free_list@ and finds the first block group
+which can handle the request.
+If such a block group exists, it takes off the requested number of blocks
+from the block group, creates a new block group from them,
+initializes it if needed, and returns it to the caller.
+The rest of the old block group, if any, is linked back to the list of free block
+groups as another block group.
+If such a block group does not exist, the block allocator requests a megablock
+from the megablock allocator and processes the request using the new megablock.
+
+For implementation details, see @BlockAlloc.c@ and @include/Block.h@.
+
+\begin{figure}[ht]
+\begin{center}
+\input{freelist.eepic}
+\caption{Linked list of free block groups}
+\label{fig-freelist}
+\end{center}
+\end{figure}
+
+\section{Heap allocator}
+
+The role of the heap allocator in the storage manager is to allocate fresh
+memory upon requests from the mutator and the runtime system.
+Memory allocation takes place frequently during the execution of Haskell
+programs, and hence its efficiency is crucial to the overall performance.
+To handle requests from the mutator and the runtime system efficiently,
+the heap allocator maintains three different memory stores,
+each of which has its own purpose.
+
+The first store is the \emph{nursery}, where typical Haskell
+objects are born.
+The mutator itself can allocate fresh memory directly in the nursery
+without invoking an interface function:
+the configuration of the nursery is always revealed to the mutator and can even
+be changed by the mutator when it allocates fresh memory from the nursery
+on its own.
+Thus, although the small overhead in manipulating the nursery results in fast
+memory allocation, it is up to the mutator to keep the nursery in an
+uncorrupted state.
+
+The second and the third are the \emph{small object pool} and the
+\emph{large object pool}.
+The heap allocator provides a common interface function to be shared by both stores:
+the size of fresh memory requested, which is passed as an argument to the
+interface function, determines which of the two stores to be used.
+The interface function can be called by both the mutator and the runtime system.
+
+\subsection{Interface}
+
+\begin{description}
+\item[@void initStorage(void)@] initializes the storage manager. @Storage.c@.
+\item[@void allocNurseries(void)@] creates and initializes the nursery.
+@Storage.c@.
+\item[@void resetNurseries(void)@] re-initializes the nursery. @Storage.c@.
+\item[@OpenNursery(hp, hplim)@] opens an allocation area in the nursery and sets
+@hp@ and @hplim@ appropriately.
+Then the caller can freely use the memory from @hp@ to @hpLim@.
+A macro in @include/StgStorage.h@.
+\item[@CloseNursery(hp)@] closes the current allocation area beginning at @hp@
+and returns it to the storage manager.
+A macro in @include/StgStorage.h@.
+\item[@ExtendNursery(hp, hplim)@] closes the current allocation area and
+tries to find a new allocation area in the nursery.
+If it succeeds, it sets @hp@ and @hplim@ appropriately and returns @rtsTrue@;
+otherwise, it returns @rtsFalse@,
+which means that the nursery has been exhausted.
+The new allocation area is not necessarily contiguous with the old one.
+A macro in @Storage.h@.
+\item[@StgPtr allocate(nat n)@] allocates @n@ words from either the small
+object pool or the large object pool, depending on the argument @n@,
+and returns a pointer to the first byte. It \emph{always} succeeds.
+@Storage.c@.
+\end{description}
+
+\subsection{Implementation}
+
+The nursery is implemented with a fixed number of blocks (@nursery_blocks@
+in @Storage.c@ specifies the number of blocks).
+Each of these blocks forms its own block group, and they are all linked together
+by @allocNurseries()@.
+The blocks in the nursery are carefully allocated in a contiguous address
+range so that they fit next to each other in the cache.
+They are never freed.
+
+A single block called the \emph{active block} provides the allocation area for
+the mutator at any moment.
+When the free space left in the active block is not enough for the request from
+the mutator, the heap allocator sets the @free@ field in the corresponding
+block descriptor to the first free byte in the block and moves the allocation
+area to the next block.
+
+Figure~\ref{fig-nursery} shows the configuration of the nursery during
+the mutator time.
+The head of the linked list is stored in @MainRegTable.rNursery@, and
+the address of the block descriptor of the active block is stored
+in @MainRegTable.rCurrentNursery@.
+@Hp@, defined as @MainRegTable.rHp@, points to the byte before the first byte of
+the current allocation area in the active block.
+@HpLim@, defines as @MainRegTable.rHpLim@, marks the boundary of the current
+allocation area:
+it points to the last byte in the current allocation area, and thus
+all the bytes of memory addresses from @Hp@$ + 1$ to @HpLim@ are free.
+The mutator can obtain fresh memory simply by adjusting @Hp@ as long as the new
+value of @Hp@ does not exceed @HpLim@. For instance, if the mutator
+increases @Hp@ by @n@, it can now store an object of size up to @n@ at the
+address pointed to by the old value of @Hp@$ + 1$.
+
+When the runtime system runs, none of the above four pointers
+(@MainRegTable.rNursery@, @MainRegTable.rCurrentNursery@, @Hp@ and @HpLim@) are
+valid; they are simply aliases to registers.
+Instead @g0s0->blocks@\footnote{@g0s0->blocks@ is valid all the time, even during
+the mutator time. The meaning of @g0s0@ is explained in the next section.}
+can be used to retrieve the head of the linked list, and
+the @free@ field in each block descriptor points to the first free byte
+in its corresponding block.\footnote{To be precise, this is \emph{not} the
+case: a @free@ field may point to a byte past its actual boundary.
+This happens because
+the mutator first increases @hpLim@ without comparing it with the
+actual boundary when allocating fresh memory,
+and later assigns @hpLim@ to the @free@ of the corresponding block.}
+@Hp@ and @HpLim@ are not saved because they can be inferred from @free@ fields
+of the blocks descriptors in the nursery.
+
+\begin{figure}[ht]
+\begin{center}
+\input{nursery.eepic}
+\caption{Nursery during the mutator time}
+\label{fig-nursery}
+\end{center}
+\end{figure}
+
+The small object pool is implemented with a linked list of block groups,
+each of which consists of a single block (Figure~\ref{fig-smallobjectpool}).
+The head of the linked list is stored in @small_alloc_list@ in @Storage.c@.
+
+\begin{figure}[ht]
+\begin{center}
+\input{smallobjectpool.eepic}
+\caption{Small object pool}
+\label{fig-smallobjectpool}
+\end{center}
+\end{figure}
+
+The allocation in the small object pool is done in the same way as in the
+nursery; @alloc_Hp@ and @alloc_HpLim@ (both defined in @Storage.c@)
+point to the first free byte and the boundary of the small object pool,
+respectively.
+Thus, when @allocate()@ is called and the heap allocator decides to
+allocate fresh memory in the small object pool, it simply increases @alloc_Hp@
+by the size of memory requested.
+If the allocation cannot be done in the current small object pool, the
+heap allocator calls @allocBlock()@ to obtain a new block from the block
+allocator, puts it to the head of the linked list, and
+sets @alloc_Hp@ and @alloc_HpLim@ appropriately.
+
+The large object pool is also implemented with a (doubly) linked list of block
+groups (Figure~\ref{fig-largeobjectpool}).
+The difference from the small object pool is that each block group stores only
+a single object: each time the argument to @allocate()@ is
+greater than a threshold value (computed from @LARGE_OBJECT_THRESHOLD@
+in @include/Constants.h@), a new block group accommodating the requested size
+is created to store a single object.
+The new block group is put to the head of the list.
+The head of the linked list is available as @g0s0->large_objects@.
+
+\begin{figure}[ht]
+\begin{center}
+\input{largeobjectpool.eepic}
+\caption{Large object pool}
+\label{fig-largeobjectpool}
+\end{center}
+\end{figure}
+
+For implementation details, see @Storage.c@ and @include/StgStorage.h@.
+
+\section{Garbage collector}
+
+The garbage collector finds all the objects unreachable from a given set of
+roots and frees the memory allocated to them. By invoking the
+garbage collector regularly, the storage manager prevents the heap from
+growing indefinitely and allows Haskell programs to be executed at a
+reasonable memory cost.
+
+The garbage collector in the storage manager is based upon the generational
+garbage collection algorithm.
+The storage manager records the age for every object in the heap.
+An object surviving one garbage collection grows old by one \emph{step},
+and an object surviving a certain number of garbage collections
+is promoted to the next \emph{generation}.
+That is, a step can be defined as a collection of objects which have survived
+the same number of garbage collections (or a collection of objects which are
+born at some point between two particular successive garbage collections),
+and a generation as a group of steps belonging to a certain range of ages.
+Notice that the unit of garbage collections is not step but generation:
+a garbage collection applies to all the steps in a generation, and we cannot
+perform a garbage collection just on part of a generation.
+Furthermore, if a particular generation is garbage collected, so are
+all the younger generations.\footnote{Some
+authors define a generation as the set of
+all the objects created between two particular garbage collection and
+an object cannot change its generation (e.g., 1960's, 1970's, and so on).
+In this document,
+an object can change its generation as it survives garbage collections
+(e.g., teenagers, 20's, and so on).}
+
+Figure~\ref{fig-generation} illustrates how an object grows old.
+Every object is created in step $0$ of generation $0$.
+As it survives garbage collections, it is moved to the next step of the
+same generation until it is finally promoted to
+step $0$ of the next generation:
+during a garbage collection of generation $g < G$, live objects from
+step $s < S_g$ are moved to step $s + 1$, and live objects from
+the last step $S_g$ are promoted to step $0$ in generation $g + 1$.
+Live objects in step $0$ of generation $G$ stay in the same step;
+the oldest generation maintains only one step because there is no point
+in aging objects in the oldest generation.
+In this way, objects are given a decent chance of dying before being
+promoted to the next generation.
+
+\begin{figure}[ht]
+\begin{center}
+\input{generation.eepic}
+\caption{Evolution of objects through garbage collections}
+\label{fig-generation}
+\end{center}
+\end{figure}
+
+The main reason that we separate steps from generations is to
+reduce the cost of maintaining \emph{backward inter-generational pointers},
+that is, pointers from older generations to younger generations.
+Suppose that a garbage collection applies to all generations $0$
+through $g$. If an object @O@ in one of these generations is pointed to
+by another object in generation $g' > g$, we cannot free the object @O@
+even though generation $g'$ is out of consideration. Consequently
+we have to track backward inter-generational pointers to perform garbage
+collections correctly.
+Since maintaining backward pointers is costly, we
+choose to track backward inter-generational pointers only;
+we do not track backward inter-step pointers.
+
+By grouping all the objects created between two garbage collections
+and grouping multiple age groups into one generation, the garbage
+collector makes an efficient use of heap memory.
+
+\subsection{Interface}
+
+\begin{description}
+%\item[@StgClosure *MarkRoot(StgClosure *root)@] informs the garbage collector
+%that @root@ is an object in the root set. It returns the new location of
+%the object. @GC.c@.
+\item[@void *mark\_root(StgClosure **root)@] informs the garbage collector
+that @*root@ is an object in the root set. It replaces @*root@ by
+the new location of the object. @GC.c@.
+\item[@void GarbageCollect(void (*get\_roots)(evac\_fn), rtsBool force\_major\_gc)@]
+performs a garbage collection.
+@get_roots()@ is a function which is called by the garbage collector when
+it wishes to find all the objects in the root set (other than those
+it can find itself).
+Therefore it is incumbent on the caller to find the root set.
+@force_major_gc@ specifies whether a major garbage collection is required
+or not. If a major garbage collection is not required, the garbage collector
+decides an oldest generation $g$ to garbage collect on its own.
+@GC.c@.
+\item[@rtsBool doYouWantToGC(void)@] returns @rtsTrue@ if the garbage
+collector is ready to perform a garbage collection. Specifically, it returns
+@rtsTrue@ if the number of allocated blocks since the last garbage collection
+(@alloc_blocks@ in @Storage.c@) exceeds an approximate limit
+(@alloc_blocks_lim@ in @Storage.c@).
+@Storage.h@.
+\item[@void recordMutable(StgMutClosure *p)@] informs the garbage collector
+that a previously immutable object @p@ has become mutable.
+The garbage collector then puts the object @p@ in the list @mut_list@ of the
+generation to which it belongs.\footnote{It is easy to
+locate the generation to which a dynamic object belongs from its address:
+we can identify the block in which the object resides from its address,
+and the corresponding block descriptor stores pointers
+to the step and the generation (@gen@ and @step@ fields in the @bdescr@
+structure) to which it belongs.}
+It suffices to call @RecordMutable()@ only once for any object.
+
+For an object which is genuinely mutable (e.g., mutable arrays),
+it is permanently recorded as mutable.
+On the other hand,
+an object which is temporarily mutable (e.g., frozen arrays),
+can be dropped from the list @mut_list@ once its pointer has been dealt with
+during garbage collections. @Storage.h@.
+\item[@void recordOldToNewPtrs(StgMutClosure *p)@] puts the object @p@ in the
+list @mut_once_list@ of the generation to which it belongs.
+\item[@void newCAF(StgClosure *caf)@] puts the CAF @caf@ either
+in the list @caf_list@ or
+in the list @mut_once_list@ of the oldest generation,
+depending on whether it is dynamically loaded or not.
+\end{description}
+
+\subsection{Steps}
+
+A step has the following structure, defined in
+@include/StgStorage.h@:
+
+\begin{code}
+typedef struct _step {
+ unsigned int no;
+ bdescr *blocks;
+ unsigned int n_blocks;
+ bdescr *large_objects;
+ /* additional fields */
+} step;
+\end{code}
+
+The fields of a step have the following purposes (Figure~\ref{fig-step}):
+
+\begin{description}
+\item[@no@] indicates the age within its generation.
+$0$ indicates the youngest step in a generation.
+\item[@blocks@] is a linked list of all the blocks in this step
+which contain small objects.
+Each block forms its own block group.
+\item[@n\_blocks@] is the number of blocks in the linked list @blocks@.
+\item[@large\_objects@] is a (doubly) linked list of all the block groups
+in this step which contain large objects.
+Each block group stores only a single object.
+\end{description}
+
+\begin{figure}[ht]
+\begin{center}
+\input{step.eepic}
+\caption{Memory layout of a step}
+\label{fig-step}
+\end{center}
+\end{figure}
+
+The linked list @blocks@ of step $s$ in generation $g$ is created
+during a garbage collection
+from live small objects of step $s - 1$ in the same generation
+(or the last step in the previous generation if $s = 0$).
+The @free@ field in every block descriptor never changes because
+no objects are added after the garbage collection; new objects are created
+only in step $0$ in generation $0$.
+Likewise, the linked list @large_objects@ is created during a
+garbage collection from live large objects of the previous step.
+
+There are three exceptions to the above rules.
+First, both @blocks@ and @large_objects@ of
+step $0$ in generation $0$ are not filled with new objects during a garbage
+collection.
+They are simply re-initialized by the garbage collector and
+grow during during the execution of a program as new objects are
+created.
+Step $0$ in generation $0$ is accessible via a global variable @g0s0@,
+and this is the reason why the large object pool (described in the previous
+section) is indeed stored in @g0s0->large_objects@.
+For the same reason, @MainRegTable.rNursery@ holds the same address as
+@g0s0->blocks@ during the mutator time.
+Second, @blocks@ of step $1$ in generation $0$ is created not only from
+the nursery (@blocks@ of step $0$ in the same generation) but also from the
+small object pool. In other words, all the live small objects created since
+the previous garbage collection, either directly by the mutator or indirectly
+through @allocate()@, are gathered together in the same linked list.
+Finally, step $0$ of the oldest generation serves the source for itself during
+any garbage collection, i.e., $S_G = 1$, because there exists no older step.
+
+\subsection{Generations}
+
+A generation has the following structure, defined in
+@include/StgStorage.h@:
+
+\begin{code}
+typedef struct _generation {
+ unsigned int no;
+ step *steps;
+ unsigned int n_steps;
+ unsigned int max_blocks;
+ StgMutClosure *mut_list;
+ StgMutClosure *mut_once_list;
+ /* additional fields */
+} generation;
+\end{code}
+
+The fields of a generation have the following purposes (Figure~\ref{fig-gen}):
+
+\begin{description}
+\item[@no@] is the generation number.
+\item[@steps@] points to an array of @step@ structures. @steps[@$i$@]@
+corresponds to step $i$ in this generation, i.e.,
+@steps[@$i$@].no@ is equal to $i$.
+\item[@n\_steps@] is the number of @step@ structures in the array pointed to
+by @steps@.
+\item[@max\_blocks@] is the maximum number of blocks allowed in step $0$ of
+this generation. If the number of blocks allocated
+in step @0@ exceeds @max_blocks@,
+this generation is garbage collected during the next garbage collection.
+\item[@mut\_list@] links all mutable objects in this generation, that is,
+objects whose contents can be updated and hence may contain pointers to
+younger generations.
+Every object in this linked list is a dynamic object residing in the heap
+and has a structure compatible with @StgMutClosure@.
+The structure @StgMutClosure@ (@includes/Closures.h@) has a field
+@mut_link@ (called a mutable link field) of type @StgMutClosure *@, which
+points to the next object in this linked list.
+The end mark of this linked list is a pointer to a statically allocated object
+@END_MUT_LIST@ (@StoragePriv.h@).
+\item[@mut\_once\_list@] links objects in this generation whose contents
+cannot be updated any more but may already have pointers to younger generations.
+As with @mut_list@, it links only those objects whose structure is compatible
+with @StgMutClosure@ and ends with @END_MUT_LIST@.
+\end{description}
+
+\begin{figure}[ht]
+\begin{center}
+\input{gen.eepic}
+\caption{Memory layout of a generation}
+\label{fig-gen}
+\end{center}
+\end{figure}
+
+The garbage collector maintains an array @generations@ of @generation@ structure
+(defined in @Storage.c@), whose size is stored in a runtime system flag
+(@RtsFlags.GcFlags.generations@).
+The generation number of each generation coincides with its index into
+the array @generations@, i.e., @generations[@$i$@].no@ is equal to $i$.
+
+As mentioned before, lists of objects which may have pointers to younger
+generations are kept per generation, not per step. The youngest generation,
+accessible via a global variable @g0@, does not keep such a list because it
+does not have younger generations.
+
+The oldest generation, accessible via a global variable @oldest_gen@, may
+contain static objects (as opposed to dynamic objects residing in the heap)
+in its list @mut_once_list@. This happens when a static
+thunk, also known as a \emph{constant applicative form} (CAF), is entered.
+When a CAF (corresponding to closure type @THUNK_STATIC@, defined
+in @includes/ClosureTypes.h@) is entered,
+it is first put in the list @mut_once_list@ of the oldest generation
+and then overwritten with an appropriate static indirection object
+(corresponding to closure type @IND_STATIC@).\footnote{Actually a static
+indirection object does not have a @mut\_link@ field.
+We use its @static\_link@ field as a substitute for @mut\_link@.
+See the structure @StgIndStatic@ in @include/Closures.h@.}\footnote{For
+details of this operation, see the macro @UPD\_CAF()@ in @includes/Updates.h@}
+If the CAF is dynamically loaded (e.g., in an interactive environment), it is
+instead put in a separate linked list @caf_list@
+(declared in @Storage.c@).
+
+The evaluation result of the
+CAF is stored in a separate dynamic object in the heap and the static
+indirection object has a pointer to the dynamic object.
+Thus, the new static indirection object is put in the list
+@mut_once_list@ of the oldest generation (or the list @caf_list@) so that the
+dynamic object is not removed during the next garbage collection.
+Once it is created, the static indirection object remains unaltered, which
+is the reason why it is put in the @mut_once_list@ list, not in the
+@mut_list@ list.
+Since the static indirection object survives any garbage collection (because
+it comes from a static object) and would be eventually moved to the oldest
+generation,
+we put it in the @mut_once_list@ of the oldest generation as soon
+as it is created.
+
+\subsection{Implementation}
+
+The overall structure of a garbage collection is as follows:
+
+\begin{enumerate}
+\item[(1)] Initialize.
+\item[(2)] Scavenge lists @mut_once_list@ and @mut_list@ if necessary.
+\item[(3)] Scavenge CAFs.
+\item[(4)] Evacuate roots.
+\item[(5)] Scavenge objects.
+\item[(6)] Tidy up.
+\end{enumerate}
+
+\subsubsection{(1) Initialization}
+
+During initialization, the garbage collector first decides which generation
+to garbage collect.
+Specifically,
+if the argument @force_major_gc@ to @GarbageCollect()@ is @rtsFalse@,
+it decides the greatest generation number $N$ such
+that the number of blocks allocated in step $0$ of generation $N$ exceeds
+@generations[@$N$@].max_blocks@.
+If the argument @force_major_gc@ to @GarbageCollect()@ is @rtsTrue@,
+$N$ is set to the greatest generation number, namely,
+$@RtsFlags.GcFlags.generations@ - 1$.
+The garbage collector considers up to generation $N$ for garbage collection.
+A major garbage collection takes place if $N$ is set to
+$@RtsFlags.GcFlags.generations@ - 1$ during this process.
+
+Then, the garbage collector initialize the \emph{to-space} (as opposed to
+\emph{from-space}) for each step of
+each generation, which is complete with an \emph{allocation pointer} and
+an \emph{sweep pointer}.
+The to-space of a step is the memory to which any object belonging to the
+step can be copied when it survives a garbage collection.
+For instance, a live object in step $s$ of generation $g$ can first be copied
+to the to-space associated with step $s$, which eventually becomes
+associated with the next step $s + 1$ (or step $0$ of the next generation)
+during tidying up.
+This operation effectively moves an object to the next step if it survives
+a garbage collection.
+The allocation pointer points to the next free in the to-space while
+the sweep pointer points to the next object considered for scavenging.
+
+During major garbage collections,
+the static link field of every static object indicates whether it has
+been visited by the garbage collector or not.
+Therefore, the static link field of every static object must have
+a null value before a major garbage collection starts.
+The list @mut_once_list@ of the oldest generation may contain static
+indirection objects, and thus
+the garbage collector invokes @zero_mutable_list()@ on the list,
+Although this breaks up the list, it does not cause any problem because
+the list is not employed during major garbage collections.
+
+\subsubsection{\tt evacuate()}
+
+The function @evacuate()@ (defined in @GC.c@), which
+is called eventually for every live object
+(including even static objects reachable from roots),
+moves an object to
+a safe place so as not to be garbage collected.
+Before invoking the function @evacuate()@ on an object @o@, the caller specifies
+a \emph{desired generation} for @o@ in a variable @evac_gen@
+(declared in @GC.c@).
+The desired generation is the youngest generation to which the caller wishes
+@o@ to be evacuated; the garbage collector should evacuate @o@ to a
+generation no younger than the desired generation.
+
+Depending on @evac_gen@ and the generation $M$ where @o@ currently resides,
+@evacuate()@ behaves itself as follows:
+\begin{itemize}
+\item If @evac_gen@ $\leq M$ and $N < M$, it does nothing because @o@ is already
+ in a generation no younger than @evac_gen@.
+\item If @evac_gen@ $\leq M \leq N$, it evacuates @o@ to the to-space of the
+step to which @o@ currently belongs. @o@ will be moved to the next step later.
+@recordMutable()@ may be invoked on @o@ depending on its type (e.g., @MVAR@).
+\item If $M <$ @evac_gen@, @o@ is evacuated to the to-space of step $0$
+ of generation @even_gen@, which accomplishes the request.
+ This happens even when $N \leq$ @evac_gen@. Therefore, those generations
+ which are not considered for garbage collection may still be augmented
+ with new objects during garbage collection.
+ @recordMutable()@ may be invoked on @o@ depending on its type.
+\end{itemize}
+If @o@ has already been evacuated, @evacuate()@ either does nothing (when
+@even_gen@ $\leq M$) or reports
+a failure to evacuate @o@ by setting the flag @failed_to_evac@ (declared
+in @GC.c@).
+
+Evacuating a large object is handled by @evacuate_large()@.
+Since it is costly to allocate new memory blocks and copy all the contents
+of the object, the garbage collector simply removes the object form
+the list @large_alloc_list@ of its step and links it to another list,
+from which it will be scavenged later.
+
+\subsubsection{Set of roots for garbage collection}
+Part of the set of roots for garbage collection is obtained indirectly by
+invoking the function
+@get_roots()@, an argument to @GarbageCollect()@: the garbage collector
+invokes @get_roots()@ with @mark_root()@ as an argument, and @get_roots()@
+in turn invokes @mark_root()@ on each of known roots.
+The rest of the set of roots is obtained from the lists @mut_list@ and
+@mut_once_list@ of generation $N + 1$ through the oldest generation:
+any objects in these lists may have pointers to objects in generations
+$0$ to $N$, and thus must be considered as a root.
+If a major garbage collection takes place, no @mut_list@ and @mut_once_list@
+lists are consider for scavenging and step (2) is skipped.
+The entire set of roots is now specified by @get_roots()@ alone.
+
+\subsubsection{(2) Scavenging lists {\tt mut\_once\_list} and {\tt mut\_list}}
+
+Since the roots obtained from the lists @mut_list@ and @mut_once_list@ are
+already in generations $N' > N$, we only have to scavenge them.
+That is, it suffices to invoke @evacuate()@ once on each object
+which is currently pointed to by an object in these lists.
+
+When scavenging an object @r@ in the list @mut_once_list@ of generation $M$,
+the desired generation is set to $M$ for each object @o@ pointed
+to by @r@ before invoking @evacuate()@.
+The rationale is that the contents of @r@ cannot be updated any more,
+and thus @r@ is always survived by @o@; @o@ is live as long as @r@ is.
+Therefore, we wish @r@ to be evacuated to the same generation $M$ as @r@
+currently resides (not to its next step).
+If the evacuation succeeds (indicated by a @rtsFalse@ value of a variable
+@failed_to_evac@, declared in @GC.c@) for every object @o@, @r@ is removed
+from the list @mut_once_list@ because it does not hold any backward
+inter-generational pointers.\footnote{It turns out that @r@ can have only
+one such object @o@. The type of @r@ is one of the following:
+@IND\_OLDGEN@, @IND\_OLDGEN\_PERM@, @IND\_STATIC@, and @MUT\_VAR@.}
+
+Scavenging a list @mut_list@ is similar to the case of @mut_once_list@.
+When scavenging an object @r@ in the list @mut_list@ of generation $M$,
+the desired generation is set to $M$ for each object pointed to by @r@
+if @r@ is known to be immutable (e.g., @MUT_ARR_PTRS_FROZEN@,
+@IND_OLDGEN@)
+or to $0$ if @r@ is still mutable (e.g., @MUT_ARR_PTRS@, @MUT_VAR@).
+The list @mut_once_list@ is also adjusted if it is safe to remove @r@ from
+@mut_list@.
+
+\subsubsection{(3) Scavenging CAFs}
+
+When a dynamically loaded CAF is entered, it it first put to the list
+@caf_list@ and then overwritten with a static indirection object.
+The evaluation result of the CAF is stored in a dynamic object in the heap
+and the static indirection object stores a pointer to the dynamic object.
+Although the static indirection object (or the CAF) itself is never freed,
+it may be removed later from the @caf_list@ when it is reverted to the
+original CAF, and the dynamic object may not be live afterwards.
+Hence, we treat the dynamic object just as normal dynamic objects and
+set the desired generation to $0$.
+
+\subsubsection{(4) Evacuating roots}
+
+Evacuating roots (other than those in the lists @mut_once_list@ and
+@mut_list@) is simply done by invoking @get_roots()@ with @mark_root()@
+as an argument.
+Since these roots are normal dynamic objects, we set the desired generation
+to $0$.
+
+\subsubsection{(5) Scavenging}
+
+The garbage collector scavenges all the objects in the to-space of
+each step (by invoking @evacuate()@ on each object reachable from them)
+until every sweep pointer has reached its corresponding
+allocation pointer.
+It repeatedly examines all the to-spaces because not only sweep pointers
+but also allocation pointers change during scavenging:
+when an object @r@ is scavenged, each object reachable from
+@r@ is evacuated to a certain to-space, which increases the corresponding
+allocation pointer, and
+the sweep pointer of the to-space which currently contains @r@
+increases as well upon finishing scavenging the object @r@.
+Thus, the garbage collector cannot anticipate in advance how many times
+it needs to scan through all the to-spaces; it keeps scavenging until
+no objects are left to be scavenged.
+
+\subsubsection{Scavenging static objects}
+
+Since it is possible for dynamic objects to point to static objects,
+the garbage collector may invoke @evacuate()@ on static objects
+while scavenging dynamic objects in to-spaces.
+This complicates the garbage collector because
+static objects cannot be evacuated in general yet
+they may have pointers to dynamic objects, which must be evacuated.
+Thus the garbage collector needs to at least scavenge live static objects
+(as opposed to those static objects currently not reachable from roots).
+
+When a minor garbage collection is performed, any invocation of
+@evacuate()@ on static objects is simply ignored.
+Furthermore, no static object is considered for scavenging
+(except those in the list @mut_once_list@ of the oldest generation during).
+Still all dynamic objects which are marked as live due to static objects
+are safely evacuated.
+The reason is that we can reach all such dynamic objects from
+indirection static objects stored in the list
+@mut_once_list@ of the oldest generation, which is scavenged during step (2),
+and the list @caf_list@.
+In other words, in order to evacuate all such dynamic objects, it is
+sufficient to evacuate all dynamic objects reachable from
+static indirection objects in
+the list @mut_once_list@ of the oldest generation and the list @caf_list@.
+However, the garbage collector may unnecessarily scavenge certain static
+indirection objects which are no longer used.
+They are not scavenged during a major garbage collection, however.
+
+During a major garbage collection,
+if an invocation of @evacuate()@ on a static object @r@ is made,
+the garbage collector first checks whether @r@ needs to be scavenged or not.
+If its SRT (Static Reference Table) is empty and it has no other pointers,
+no dynamic objects are reachable from @r@ and it is ignored.\footnote{If
+no dynamic objects are reachable from a static object @r@ (even indirectly
+via multiple static objects),
+@r@ is not stored in \emph{any} SRT table because it would be no use attempting
+to follow any pointers in @r@.}
+Otherwise, it is put in the list @static_objects@.
+At the beginning of each scavenging loop in step (5),
+the garbage collector invokes @scavenge_static()@ if the list @static_objects@
+is not empty.
+@scavenge_static()@ scavenges the static objects in the list @static_objects@
+by invoking @evacuate()@ on every object reachable from them.
+The desired generation is set to the oldest generation (because any
+dynamic object directly pointed to by a static object lives
+forever).
+These static objects are then put in another list @scavenged_static_objects@
+and removed from the list @static_objects@.
+For a static indirection object, if the evacuation
+fails, it is put back to the list @mut_once_list@ of the oldest generation;
+it can be thought of as a CAF just entered.
+
+After a major garbage collection, therefore, the list @scavenged_static_objects@
+links all live static objects except for static indirection objects put back
+to the list @mut_once_list@ of the oldest generation.
+Dynamically loaded CAFs are found in the list @caf_list@.
+
+\subsubsection{(6) Tidying up}
+
+The garbage collector tidies up the heap by
+moving the to-space of each step to the next step.
+It also re-initialize the small object pool (which now does not contain
+any live objects), frees any large objects which have not been scavenged,
+and invokes @resetNurseries()@.
+If a major garbage collection has been performed, it
+invokes @zero_static_object_list()@ on the list @scavenged_static_objects@
+so that all static objects
+(other than those in the list @mut_once_list@ of the oldest generation)
+have a null static link field again.
+
+At this point, both the small allocation pool and the large object pool are
+empty. Upon the exit from @GarbageCollect()@, however, they may not
+be empty any more because the garbage collector invokes @scheduleFinalizer()@
+before exiting, which tries to run pending finalizers on dead weak pointers and
+may create new objects through @allocate()@.
+The nursery still remains intact.
+
+The heap may contain extra objects which are not reachable from the roots
+used during the garbage collection: 1) weak head pointers; 2) dead
+weak head pointers. Weak head pointers can be tracked from
+the list @weak_ptr_list@ (declared in @Weak.c@). However, there is no way
+of reaching dead weak pointers; they will be garbage collected during the
+next garbage collection.
+
+For implementation details, see @GC.c@.
+
+\section{State of the heap allocator and the garbage collector}
+
+The state of the heap allocator and the garbage collector is fully specified by the
+following variables:
+
+\begin{description}
+\item[@small\_alloc\_list@] is the header of the small object pool.
+\item[@alloc\_Hp@] points to the first free byte in the small object pool.
+\item[@alloc\_HpLim@] points to the boundary of the small object pool.
+\item[@generations@] is the array of @generation@ structures.
+\item[@RtsFlags.GcFlags.generations@] specifies the number of elements in
+the array @generations@.
+\item[@caf\_list@] links dynamically loaded CAFs.
+\end{description}
+
+\textbf{To do:} check if this is a complete list.
+
+The following variables are derivable, but they are given special purposes:
+
+\begin{description}
+\item[@g0s0@] points to step 0 of the youngest generation.
+\item[@oldest\_gen@] points to the oldest generation.
+\item[@g0s0->blocks@] is the header of the nursery.
+\item[@g0s0->large\_blocks@] is the header of the large object pool.
+\end{description}
+
+\section{Miscellaneous notes}
+
+\begin{itemize}
+\item To see how to add new fields to Haskell closures,
+see the document on the implementation of retainer profiling
+(section `Adding Retainer Set Fields').
+
+\item To see how to traverse the graph and visit every live closure,
+see the document on the implementation of retainer profiling
+(section `Graph Traversal').
+
+\item To see how to linearly scan the heap at any random moment during
+program execution, see the document on the implementation of LDVU profiling
+(section `Heap Censuses').
+
+\item To see how to linearly scan the from-space during garbage collections,
+see the document on the implementation of LDVU profiling
+(section `Destruction of Closures').
+
+\end{itemize}
+
+\end{document}
projects / ghc-hetmet.git / blobdiff