Changes between Version 4 and Version 5 of Commentary/Rts/HeapObjects

Sep 6, 2006 3:19:13 PM (9 years ago)



  • Commentary/Rts/HeapObjects

    v4 v5  
    11[ Up: [wiki:Commentary/Rts] ]
    34= GHC Commentary: The Layout of Heap Objects =
    3940The most important part of the header is the ''info pointer'', which points to the info table for the closure.  In the default build, this is all the header contains, so a header is normally just one word.  In other builds, the header may contain extra information: eg. in a profilnig build it also contains information about who built the closure.
    41 Most of the runtime is insensitive to the size of {{{StgHeader}}}; that is, we are careful not to hardcode the offset to the payload anywhere, instead we use C struct indexing or {{{sizeof(StgHeader)}}}.  This makes it easy to extend {{{StgHeader}}} with new fields if we need to.
     42Most of the runtime is insensitive to the size of {{{StgHeader}}};
     43that is, we are careful not to hardcode the offset to the payload
     44anywhere, instead we use C struct indexing or {{{sizeof(StgHeader)}}}.
     45This makes it easy to extend {{{StgHeader}}} with new fields if we
     46need to.
    4348== Info Tables ==
    49 == Types of Heap Object ==
     56 * The ''closure type'' is a constant describing the kind of closure this is (function, thunk, constructor etc.).  All
     57   the closure types are defined in [[GhcFile(includes/ClosureTypes.h)]], and many of them have corresponding C struct
     58   definitions in [[GhcFile(includes/Closures.h)]].
     60 * The ''SRT bitmap'' field is used to support [wiki:Commentary/Rts/CAFs garbage collection of CAFs].
     62 * The ''layout'' field describes the layout of the closure for the garbage collector.  The GC needs to know
     63   two things: how many words there are in the payload, and which of those words are pointers.  There are various ways
     64   in which a closure may be laid out:
     65   * ''fixed layout'': the layout is fixed by the closure type, the layout field in the info table is ignored.  eg.
     66     MUT_VAR closures have fixed layout.
     67   * ''pointers first'': the payload consists of zero or more pointers followed by zero or more non-pointers.
     68     This is the most common layout: constructors, functions and thunks use this layout.  The  layout field contains
     69     two half-word-sized fields:
     70     * Number of pointers
     71     * Number of non-pointers
     72   * ''bitmap'': the layout is described by a bitmap (see [wiki:Commentary/Rts/HeapObjects#Bitmaps bitmaps], below).  Stack frames generally have bitmap layout.
     74 * The ''entry code'' for the closure is usually the code that will ''evaluate'' the closure.  There is one exception:
     75   for functions, the entry code will apply the function to the arguments given in registers or on the stack, according
     76   to the calling convention.  The entry code assumes all the arguments are present - to apply a function to fewer arguments
     77   or to apply an unknown function, the [wiki:Commentary/Rts/HaskellExecution/EvalApply generic apply functions] must
     78   be used.
     80Some types of object add more fields to the end of the info table, notably functions, return addresses, and thunks.
     82=== {{{TABLES_NEXT_TO_CODE}}} ===
     84Note that the info table is followed immediately by the entry code, rather than the code being at the end of an indirect pointer.  This both reduces the size of the info table and eliminates one indirection when jumping to the entry code; however, arranging to generate code like this presents some difficulties when compiling via C, see [wiki:Commentary/Mangler]. 
     86GHC can generate code that uses the indirect pointer instead; the {{{TABLES_NEXT_TO_CODE}}} turns on the optimised layout.  Generally {{{TABLES_NEXT_TO_CODE}}} is turned off when compiling unregisterised.
     88When {{{TABLES_NEXT_TO_CODE}}} is off, info tables get another field, {{{entry}}}, which points to the entry code.  In a generated object file, each symbol {{{X_info}}} representing an info table will have an associated symbol {{{X_entry}}} pointing to the entry code (in {{{TABLES_NEXT_TO_CODE}}}, the entry symbol is omitted to keep the size of symbol tables down).
     90== Dynamic vs. Static objects ==
     92Objects fall into two categories:
     94 * ''dynamic'' objects reside in the heap, and may be moved by the garbage collector.
     96 * ''static'' objects reside in the compiled object code.  They are never moved, because pointers to such objects are
     97   scattered through the object code, and only the linker knows where.
     99To find out whether a particular object is dynamic or static, use the {{{HEAP_ALLOCED()}}} macro, from [[GhcFile(rts/MBlock.h)]].
     101=== Dynamic objects ===
     103Dynamic objects have a minimum size, because every object must be big
     104enough to be overwritten by a
     105[wiki:Commentary/Rts/HeapObjects#ForwardingPointers forwarding pointer] during GC.
     106The minimum size of the payload is given by {{{MIN_PAYLOAD_SIZE}}} in [[GhcFile(includes/Constants.h)]].
     108=== Static objects ===
     110All static objects have closure types ending in {{{_STATIC}}}, eg. {{{CONSTR_STATIC}}} for static data constructors.
     112Static objects have an additional field, called the ''static link
     113field''.  The static link field is used by the GC to link all the
     114static objects in a list, and so that it can tell whether it has
     115visited a particular static object or not - the GC needs to traverse
     116all the static objects in order to [wiki:Commentary/Rts/CAFs garbage collect CAFs].
     118The static link field resides after the normal payload, so that the
     119static variant of an object has compatible layout with the dynamic
     120variant.  To access the static link field of a closure, use the
     121{{{STATIC_LINK()}}} macro from [[GhcFile(includes/ClosureMacros.h)]].
     123== Types of object ==
     125=== Data Constructors ===
     127All data constructors have pointers-first layout:
     129|| Header || Pointers... || Non-pointers... ||
     131Data constructor closure types:
     133 * ({{{CONSTR}}}: a vanilla, dynamically allocated constructor
     134 * {{{CONSTR_p_n}}}: a constructor whose layout is encoded in the closure type (eg. {{{CONSTR_1_0}}} has one pointer
     135   and zero non-pointers.  Having these closure types speeds up GC a little for common layouts.
     136 * {{{CONSTR_INTLIKE}}}, {{{CONSTR_CHARLIKE}}}: special closure types corresponding to types like {{{Int}}} and
     137   {{{Char}}}.  The RTS includes some static instances of these types so that instead of allocating a new {{{Char}}}
     138   on the heap, we can use the static RTS instance instead and save some heap space.  See   
     139   [[GhcFile(rts/StgMiscClosures.cmm)]].
     140 * {{{CONSTR_STATIC}}}: a statically allocated constructor.
     142The entry code for a constructor returns immediately to the topmost stack frame, because the data constructor is already in WHNF.  The return convention may be vectored or non-vectored, depending on the type (see [wiki:Commentary/Rts/HaskellExecution#ReturnConvention]).
     144Symbols related to a data constructor X:
     146 * X_{{{con_info}}}: info table for a dynamic instance of X
     147 * X_{{{static_info}}}: info table for a static instance of X
     148 * X_{{{info}}}: the ''wrapper'' for X (a function, equivalent to the
     149   curried function {{{X}}} in Haskell, see
     150   [wiki:Commentary/Compiler/DataCon]). 
     151 * X_{{{closure}}}: static closure for X's wrapper
     153=== Function Closures ===
     155A function closure represents a Haskell function.  For example:
     157  f = \x -> let g = \y -> x + y
     158            in g x
     160Here, {{{f}}} would be represented by a static function closure (see below), and {{{g}}} a dynamic function closure.  Every function in the Haskell program generates a new info table and entry code, and top-level functions additionally generate a static closure.
     162All function closures have pointers-first layout:
     164|| Header || Pointers... || Non-pointers... ||
     166The payload of the function closure contains the free variables of the function: in the example above, a closure for {{{g}}} would have a payload containing a pointer to {{{x}}}.
     168Function closure types:
     170 * {{{FUN}}}: a vanilla, dynamically allocated function
     171 * {{{FUN_p_n}}}: same, specialised for layout (see constructors above)
     172 * {{{FUN_STATIC}}}: a static (top-level) function closure
     174Symbols related to a function {{{f}}}:
     176 * {{{f_info}}}: f's info table and code
     177 * {{{f_closure}}}: f's static closure, if f is a top-level function.
     178   The static closure has no payload, because there are no free
     179   variables of a top-level function.  It does have a static link
     180   field, though.
     182=== Thunks ===
     184A thunk represents an expression that is not obviously in head normal
     185form.  For example, consider the following top-level definitions:
     187  range = between 1 10
     188  f = \x -> let ys = take x range
     189            in sum ys
     191Here the right-hand sides of {{{range}}} and {{{ys}}} are both thunks;
     192the former is static while the latter is dynamic.
     194Thunks have pointers-first layout:
     196|| Header || Pointers... || Non-pointers... ||
     198As for function closures, the payload contains the free variables of
     199the expression.  A thunk differs from a function closure in that it
     200can be [wiki:Commentary/Rts/HaskellExecution#Updates updated].
     202There are several forms of thunk:
     204 * {{{THUNK}}}, {{{THUNK_p_n}}}: vanilla, dynamically allocated
     205   thunks.  Dynamic thunks are overwritten with normal indirections
     206   {{{IND}}}, or old generation indirections {{{IND_OLDGEN}}} when
     207   evaluated.
     209 * {{{THUNK_STATIC}}}: a static thunk is also known as a ''constant
     210   applicative form'', or ''CAF''.  Static thunks are overwritten with
     211   static indirections ({{{IND_STATIC}}}).
     213The only label associated with a thunk is its info table:
     215 * {{{f_info}}} is f's info table.
     217=== Selector thunks ===
     219{{{THUNK_SELECTOR}}} is a (dynamically allocated) thunk whose entry
     220code performs a simple selection operation from a data constructor
     221drawn from a single-constructor type.  For example, the thunk
     223x = case y of (a,b) -> a
     225is a selector thunk.  A selector thunk is laid out like this:
     227|| Header || Selectee pointer ||
     229The layout word contains the byte offset of the desired word in the
     230selectee.  Note that this is different from all other thunks.
     232The garbage collector "peeks" at the selectee's tag (in its info
     233table).  If it is evaluated, then it goes ahead and does the
     234selection, and then behaves just as if the selector thunk was an
     235indirection to the selected field.  If it is not evaluated, it
     236treats the selector thunk like any other thunk of that shape.
     238There is a fixed set of pre-compiled selector thunks built into the
     239RTS, representing offsets from 0 to {{{MAX_SPEC_SELECTOR_THUNK}}},
     240see [[GhcFile(rts/StgMiscThunks.cmm)]].
     241The info tables are labelled {{{__sel_n_upd_info}}} where {{{n}}} is the
     242offset.  Non-updating versions are also built in, with info tables
     243labelled {{{_sel_n_noupd_info}}}.
     245=== Partial applications ===
     247Partial applications are tricky beasts.
     249A partial application, closure type {{{PAP}}}, represents a function
     250applied to too few arguments.  Partial applications are only built by
     251the [wiki:Commentary/Rts/HaskellExecution/EvalApply generic apply]
     252functions in AutoApply.cmm.
     254|| Header || Arity || No. of words || Function closure || Payload... ||
     258 * ''Arity'' is the arity of the PAP.  For example, a function with
     259   arity 3 applied to 1 argument would leave a PAP with arity 2.
     261 * ''No. of words'' refers to the size of the payload in words.
     263 * ''Function closure'' is the function to which the arguments are
     264   applied.  Note that this is always a pointer to one of the
     265   {{{FUN}}} family, never a {{{PAP}}}.  If a {{{PAP}}} is applied
     266   to more arguments to give a new {{{PAP}}}, the arguments from
     267   the original {{{PAP}}} are copied to the new one.
     269 * The payload is the sequence of arguments already applied to
     270   this function.  The pointerhood of these words are described
     271   by the function's bitmap (see {{{scavenge_PAP_payload()}}} in
     272   [[GhcFile(rts/GC.c)]] for an example of traversing a PAP).
     274There is just one standard form of PAP. There is just one info table
     275too, called {{{stg_PAP_info}}}.  A PAP should never be entered, so its
     276entry code causes a failure.  PAPs are applied by the generic apply
     277functions in {{{AutoApply.cmm}}}.
     279=== Generic application ===
     281An {{{AP}}} object is very similar to a {{{PAP}}}, and has identical layout:
     283|| Header || Arity || No. of words || Function closure || Payload... ||
     285The difference is that an {{{AP}}} is not necessarily in WHNF.  It is
     286a thunk that represents the application of the specified function to
     287the given arguments.
     289The arity field is always zero (it wouldn't help to omit this field,
     290because it is only half a word anyway).
     292{{{AP}}} closures are used mostly by the byte-code interpreter, so that it only needs a single form of thunk object.  Interpreted thunks are always represented by the application of a {{{BCO}}} to its free variables.
     294=== Stack application ===
     296An {{{AP_STACK}}} is a special kind of object:
     298|| Header || Size || Closure || Payload... ||
     300It represents computation of a thunk that was suspended midway through evaluation.  In order to continue the computation, copy the payload onto the stack (the payload was originally the stack of the suspended computation), and enter the closure.
     302Since the payload is a chunk of stack, the GC can use its normal stack-walking code to traverse it.
     304{{{AP_STACK}}} closures are built by {{{raiseAsync()}}} in [[GhcFile(rts/RaiseAsync.c)]] when an [wiki:Commentary/Rts/AsyncExceptions asynchronous exception] is raised.
     306=== Indirections ===
     308Indirection closures just point to other closures. They are introduced
     309when a thunk is updated to point to its value.  The entry code for all
     310indirections simply enters the closure it points to.
     312The basic layout of an indirection is simply
     314|| Header || Target closure ||
     316There are several variants of indirection:
     318 * {{{IND}}}: is the vanilla, dynamically-allocated indirection.
     319   It is removed by the garbage collector.  An {{{IND}}} only exists in the youngest generation. 
     320   The update code ({{{stg_upd_frame_info}}} and friends) checks whether the updatee is in the youngest
     321   generation before deciding which kind of indirection to use.
     322 * {{{IND_OLDGEN}}}: an old generation indirection.  Same layout as {{{IND}}}.  This used to have
     323   different layout when the old-generation mutable list was threaded through the objects, but now
     324   {{{IND_OLDGEN}}} is exactly the same as {{{IND}}} (and there's no good reason to have it at all, I think).
     325 * {{{IND_PERM}}}: sometimes we don't want an indirection to be removed by the GC, so we use {{{IND_PERM}}} instead.
     326   The profiler is one user of this closure type; cost-center semantics requires that we keep track of the
     327   cost center in an indirection, so we can't eliminate the indirection.
     328 * {{{IND_OLDGEN_PERM}}}: same as above, but for the old generation.
     329 * {{{IND_STATIC}}}: a static indirection, arises when we update a {{{THUNK_STATIC}}}.  A new {{{IND_STATIC}}}
     330   is placed on the mutable list when it is created (see {{{newCaf()}}} in [[GhcFile(rts/Storage.c)]].
     332=== Byte-code objects ===
     336=== Black holes ===
     338{{{BLACKHOLE}}}, {{{CAF_BLACKHOLE}}}
     340=== Arrays ===
     345=== MVars ===
     349=== Weak pointers ===
     353=== Stable Names ===
     357=== Thread objects ===
     361=== STM objects ===
     363These object types are used by [wiki:Commentary/Rts/STM STM]: {{{TVAR_WAIT_QUEUE}}}, {{{TVAR}}}, {{{TREC_CHUNK}}}, {{{TREC_HEADER}}}.
     365=== Forwarding pointers ===
     367The {{{EVACUATED}}} object only appears temporarily during GC.  An object which has been copied into to-space (''evacuated'') is replaced by an {{{EVACUATED}} object:
     369|| Header || Forwarding pointer ||
     371which points to the new location of the object.
    51373== The stack, and stack objects ==
     375=== Return addresses ===
     391== Objects for PAR, GRAN ==
     393{{{BLOCKED_FETCH}}}, {{{FETCH_ME}}}, {{{FETCH_ME_BQ}}}, {{{RBH}}}, {{{REMOTE_REF}}}
     395== Bitmaps ==