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


Ignore:
Timestamp:
Sep 6, 2006 3:19:13 PM (8 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 ==