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 ==