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


Ignore:
Timestamp:
Sep 6, 2006 3:19:13 PM (9 years ago)
Author:
simonmar
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Rts/HeapObjects

    v4 v5  
    11[ Up: [wiki:Commentary/Rts] ]
     2[[PageOutline]]
    23
    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.
    4041
    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.
    4247
    4348== Info Tables ==
     
    4752[[Image(basic-itbl.png)]]
    4853
    49 == Types of Heap Object ==
     54Where:
     55 
     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)]].
     59
     60 * The ''SRT bitmap'' field is used to support [wiki:Commentary/Rts/CAFs garbage collection of CAFs].
     61
     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.
     73
     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.
     79
     80Some types of object add more fields to the end of the info table, notably functions, return addresses, and thunks.
     81
     82=== {{{TABLES_NEXT_TO_CODE}}} ===
     83
     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]. 
     85
     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.
     87
     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).
     89
     90== Dynamic vs. Static objects ==
     91
     92Objects fall into two categories:
     93
     94 * ''dynamic'' objects reside in the heap, and may be moved by the garbage collector.
     95
     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.
     98
     99To find out whether a particular object is dynamic or static, use the {{{HEAP_ALLOCED()}}} macro, from [[GhcFile(rts/MBlock.h)]].
     100
     101=== Dynamic objects ===
     102
     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)]].
     107
     108=== Static objects ===
     109
     110All static objects have closure types ending in {{{_STATIC}}}, eg. {{{CONSTR_STATIC}}} for static data constructors.
     111
     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].
     117
     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)]].
     122
     123== Types of object ==
     124
     125=== Data Constructors ===
     126
     127All data constructors have pointers-first layout:
     128
     129|| Header || Pointers... || Non-pointers... ||
     130
     131Data constructor closure types:
     132
     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.
     141
     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]).
     143
     144Symbols related to a data constructor X:
     145
     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
     152
     153=== Function Closures ===
     154
     155A function closure represents a Haskell function.  For example:
     156{{{
     157  f = \x -> let g = \y -> x + y
     158            in g x
     159}}}
     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.
     161 
     162All function closures have pointers-first layout:
     163
     164|| Header || Pointers... || Non-pointers... ||
     165
     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}}}.
     167
     168Function closure types:
     169
     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
     173
     174Symbols related to a function {{{f}}}:
     175
     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.
     181
     182=== Thunks ===
     183
     184A thunk represents an expression that is not obviously in head normal
     185form.  For example, consider the following top-level definitions:
     186{{{
     187  range = between 1 10
     188  f = \x -> let ys = take x range
     189            in sum ys
     190}}}
     191Here the right-hand sides of {{{range}}} and {{{ys}}} are both thunks;
     192the former is static while the latter is dynamic.
     193
     194Thunks have pointers-first layout:
     195
     196|| Header || Pointers... || Non-pointers... ||
     197
     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].
     201
     202There are several forms of thunk:
     203
     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.
     208
     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}}}).
     212
     213The only label associated with a thunk is its info table:
     214
     215 * {{{f_info}}} is f's info table.
     216
     217=== Selector thunks ===
     218
     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
     222{{{
     223x = case y of (a,b) -> a
     224}}}
     225is a selector thunk.  A selector thunk is laid out like this:
     226
     227|| Header || Selectee pointer ||
     228
     229The layout word contains the byte offset of the desired word in the
     230selectee.  Note that this is different from all other thunks.
     231
     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.
     237
     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}}}.
     244
     245=== Partial applications ===
     246
     247Partial applications are tricky beasts.
     248
     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.
     253
     254|| Header || Arity || No. of words || Function closure || Payload... ||
     255
     256Where:
     257
     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.
     260
     261 * ''No. of words'' refers to the size of the payload in words.
     262
     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.
     268
     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).
     273
     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}}}.
     278
     279=== Generic application ===
     280
     281An {{{AP}}} object is very similar to a {{{PAP}}}, and has identical layout:
     282
     283|| Header || Arity || No. of words || Function closure || Payload... ||
     284
     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.
     288
     289The arity field is always zero (it wouldn't help to omit this field,
     290because it is only half a word anyway).
     291
     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.
     293
     294=== Stack application ===
     295
     296An {{{AP_STACK}}} is a special kind of object:
     297
     298|| Header || Size || Closure || Payload... ||
     299
     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.
     301
     302Since the payload is a chunk of stack, the GC can use its normal stack-walking code to traverse it.
     303
     304{{{AP_STACK}}} closures are built by {{{raiseAsync()}}} in [[GhcFile(rts/RaiseAsync.c)]] when an [wiki:Commentary/Rts/AsyncExceptions asynchronous exception] is raised.
     305
     306=== Indirections ===
     307
     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.
     311
     312The basic layout of an indirection is simply
     313
     314|| Header || Target closure ||
     315
     316There are several variants of indirection:
     317
     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)]].
     331
     332=== Byte-code objects ===
     333
     334{{{BCO}}}
     335
     336=== Black holes ===
     337
     338{{{BLACKHOLE}}}, {{{CAF_BLACKHOLE}}}
     339
     340=== Arrays ===
     341
     342{{{ARR_WORDS}}}, {{{MUT_ARR_PTRS_CLEAN}}}, {{{MUT_ARR_PTRS_DIRTY}}}, {{{MUT_ARR_PTRS_FROZEN0}}},
     343{{{MUT_ARR_PTRS_FROZEN}}}
     344
     345=== MVars ===
     346
     347{{{MVar}}}
     348
     349=== Weak pointers ===
     350
     351{{{Weak}}}
     352
     353=== Stable Names ===
     354
     355{{{STABLE_NAME}}}
     356
     357=== Thread objects ===
     358
     359{{{TSO}}}
     360
     361=== STM objects ===
     362
     363These object types are used by [wiki:Commentary/Rts/STM STM]: {{{TVAR_WAIT_QUEUE}}}, {{{TVAR}}}, {{{TREC_CHUNK}}}, {{{TREC_HEADER}}}.
     364
     365=== Forwarding pointers ===
     366
     367The {{{EVACUATED}}} object only appears temporarily during GC.  An object which has been copied into to-space (''evacuated'') is replaced by an {{{EVACUATED}} object:
     368
     369|| Header || Forwarding pointer ||
     370
     371which points to the new location of the object.
    50372
    51373== The stack, and stack objects ==
     374
     375=== Return addresses ===
     376
     377{{{RET_BCO}}},
     378{{{RET_SMALL}}},
     379{{{RET_VEC_SMALL}}},
     380{{{RET_BIG}}},
     381{{{RET_VEC_BIG}}},
     382{{{RET_DYN}}},
     383{{{RET_FUN}}},
     384{{{UPDATE_FRAME}}},
     385{{{CATCH_FRAME}}},
     386{{{STOP_FRAME}}},
     387{{{ATOMICALLY_FRAME}}},
     388{{{CATCH_RETRY_FRAME}}},
     389{{{CATCH_STM_FRAME}}}
     390
     391== Objects for PAR, GRAN ==
     392
     393{{{BLOCKED_FETCH}}}, {{{FETCH_ME}}}, {{{FETCH_ME_BQ}}}, {{{RBH}}}, {{{REMOTE_REF}}}
     394
     395== Bitmaps ==