... | ... | @@ -25,12 +25,12 @@ Unlifted types cannot currently be used to represent terminating functions: an u |
|
|
## Heap Objects
|
|
|
|
|
|
|
|
|
All heap objects have the same basic layout, embodied by the type `StgClosure` in [Closures.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/storage/Closures.h)[](/trac/ghc/export/HEAD/ghc/includes/rts/storage/Closures.h). The diagram below shows the layout of a heap object:
|
|
|
All heap objects have the same basic layout, embodied by the type `StgClosure` in [Closures.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/storage/Closures.h). The diagram below shows the layout of a heap object:
|
|
|
|
|
|
[](/trac/ghc/attachment/wiki/Commentary/Rts/Storage/HeapObjects/heap-object.png)
|
|
|
|
|
|
|
|
|
A heap object always begins with a *header*, defined by `StgHeader` in [Closures.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/storage/Closures.h)[](/trac/ghc/export/HEAD/ghc/includes/rts/storage/Closures.h):
|
|
|
A heap object always begins with a *header*, defined by `StgHeader` in [Closures.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/storage/Closures.h):
|
|
|
|
|
|
```wiki
|
|
|
typedef struct {
|
... | ... | @@ -59,7 +59,7 @@ The compiler also needs to know the layout of heap objects, and the way this inf |
|
|
## Info Tables
|
|
|
|
|
|
|
|
|
The info table contains all the information that the runtime needs to know about the closure. The layout of info tables is defined by `StgInfoTable` in [InfoTables.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/storage/InfoTables.h)[](/trac/ghc/export/HEAD/ghc/includes/rts/storage/InfoTables.h). The basic info table layout looks like this:
|
|
|
The info table contains all the information that the runtime needs to know about the closure. The layout of info tables is defined by `StgInfoTable` in [InfoTables.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/storage/InfoTables.h). The basic info table layout looks like this:
|
|
|
|
|
|
[](/trac/ghc/attachment/wiki/Commentary/Rts/Storage/HeapObjects/basic-itbl.png)
|
|
|
|
... | ... | @@ -68,8 +68,8 @@ Where: |
|
|
|
|
|
|
|
|
- The *closure type* is a constant describing the kind of closure this is (function, thunk, constructor etc.). All
|
|
|
the closure types are defined in [ClosureTypes.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/storage/ClosureTypes.h)[](/trac/ghc/export/HEAD/ghc/includes/rts/storage/ClosureTypes.h), and many of them have corresponding C struct
|
|
|
definitions in [Closures.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/storage/Closures.h)[](/trac/ghc/export/HEAD/ghc/includes/rts/storage/Closures.h).
|
|
|
the closure types are defined in [ClosureTypes.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/storage/ClosureTypes.h), and many of them have corresponding C struct
|
|
|
definitions in [Closures.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/storage/Closures.h).
|
|
|
|
|
|
- The *SRT bitmap* field is used to support [garbage collection of CAFs](commentary/rts/storage/gc/CAFs).
|
|
|
|
... | ... | @@ -134,9 +134,9 @@ The payload consists of a mixture of pointers and non-pointers, described by a b |
|
|
The size field gives the size of the payload, and each bit of the bitmap is 0 if the corresponding word of payload contains a pointer to a live object.
|
|
|
|
|
|
|
|
|
The macros `MK_SMALL_BITMAP`, `BITMAP_SIZE`, and `BITMAP_BITS` in [InfoTables.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/storage/InfoTables.h)[](/trac/ghc/export/HEAD/ghc/includes/rts/storage/InfoTables.h) provide ways to conveniently operate on small bitmaps.
|
|
|
The macros `MK_SMALL_BITMAP`, `BITMAP_SIZE`, and `BITMAP_BITS` in [InfoTables.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/storage/InfoTables.h) provide ways to conveniently operate on small bitmaps.
|
|
|
|
|
|
**Large bitmaps.** If the size of the stack frame is larger than the 27 words that a small bitmap can describe, then the fallback mechanism is the large bitmap. A large bitmap is a separate structure, containing a single word size and a multi-word bitmap: see `StgLargeBitmap` in [InfoTables.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/storage/InfoTables.h)[](/trac/ghc/export/HEAD/ghc/includes/rts/storage/InfoTables.h).
|
|
|
**Large bitmaps.** If the size of the stack frame is larger than the 27 words that a small bitmap can describe, then the fallback mechanism is the large bitmap. A large bitmap is a separate structure, containing a single word size and a multi-word bitmap: see `StgLargeBitmap` in [InfoTables.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/storage/InfoTables.h).
|
|
|
|
|
|
---
|
|
|
|
... | ... | @@ -151,7 +151,7 @@ Objects fall into two categories: |
|
|
scattered through the object code, and only the linker knows where.
|
|
|
|
|
|
|
|
|
To find out whether a particular object is dynamic or static, use the [HEAP_ALLOCED()](commentary/rts/storage/heap-alloced) macro, from [rts/sm/HeapAlloc.h](https://gitlab.haskell.org/ghc/ghc/tree/master/rts/sm/HeapAlloc.h)[](/trac/ghc/export/HEAD/ghc/rts/sm/HeapAlloc.h). This macro works by consulting a bitmap (or structured bitmap) that tells for each [megablock](commentary/rts/storage#structure-of-blocks) of memory whether it is part of the dynamic heap or not.
|
|
|
To find out whether a particular object is dynamic or static, use the [HEAP_ALLOCED()](commentary/rts/storage/heap-alloced) macro, from [rts/sm/HeapAlloc.h](https://gitlab.haskell.org/ghc/ghc/tree/master/rts/sm/HeapAlloc.h). This macro works by consulting a bitmap (or structured bitmap) that tells for each [megablock](commentary/rts/storage#structure-of-blocks) of memory whether it is part of the dynamic heap or not.
|
|
|
|
|
|
### Dynamic objects
|
|
|
|
... | ... | @@ -159,7 +159,7 @@ To find out whether a particular object is dynamic or static, use the [HEAP_ALLO |
|
|
Dynamic objects have a minimum size, because every object must be big
|
|
|
enough to be overwritten by a
|
|
|
forwarding pointer ([Forwarding Pointers](#ForwardingPointers)) during GC.
|
|
|
The minimum size of the payload is given by `MIN_PAYLOAD_SIZE` in [includes/rts/Constants.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/Constants.h)[](/trac/ghc/export/HEAD/ghc/includes/rts/Constants.h).
|
|
|
The minimum size of the payload is given by `MIN_PAYLOAD_SIZE` in [includes/rts/Constants.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/Constants.h).
|
|
|
|
|
|
### Static objects
|
|
|
|
... | ... | @@ -177,7 +177,7 @@ all the static objects in order to [garbage collect CAFs](commentary/rts/CAFs). |
|
|
The static link field resides after the normal payload, so that the
|
|
|
static variant of an object has compatible layout with the dynamic
|
|
|
variant. To access the static link field of a closure, use the
|
|
|
`STATIC_LINK()` macro from [includes/rts/storage/ClosureMacros.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/storage/ClosureMacros.h)[](/trac/ghc/export/HEAD/ghc/includes/rts/storage/ClosureMacros.h).
|
|
|
`STATIC_LINK()` macro from [includes/rts/storage/ClosureMacros.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/storage/ClosureMacros.h).
|
|
|
|
|
|
---
|
|
|
|
... | ... | @@ -336,7 +336,7 @@ This technique comes from the Phil Wadler paper [Fixing some space leaks with a |
|
|
|
|
|
There is a fixed set of pre-compiled selector thunks built into the
|
|
|
RTS, representing offsets from 0 to `MAX_SPEC_SELECTOR_THUNK`,
|
|
|
see [rts/StgStdThunks.cmm](https://gitlab.haskell.org/ghc/ghc/tree/master/rts/StgStdThunks.cmm)[](/trac/ghc/export/HEAD/ghc/rts/StgStdThunks.cmm).
|
|
|
see [rts/StgStdThunks.cmm](https://gitlab.haskell.org/ghc/ghc/tree/master/rts/StgStdThunks.cmm).
|
|
|
The info tables are labelled `__sel_n_upd_info` where `n` is the
|
|
|
offset. Non-updating versions are also built in, with info tables
|
|
|
labelled `_sel_n_noupd_info`.
|
... | ... | @@ -352,7 +352,7 @@ Partial applications are tricky beasts. |
|
|
|
|
|
A partial application, closure type `PAP`, represents a function
|
|
|
applied to too few arguments. Partial applications are only built by
|
|
|
the [generic apply functions](commentary/rts/haskell-execution/function-calls#generic-apply) in [rts/Apply.cmm](https://gitlab.haskell.org/ghc/ghc/tree/master/rts/Apply.cmm)[](/trac/ghc/export/HEAD/ghc/rts/Apply.cmm).
|
|
|
the [generic apply functions](commentary/rts/haskell-execution/function-calls#generic-apply) in [rts/Apply.cmm](https://gitlab.haskell.org/ghc/ghc/tree/master/rts/Apply.cmm).
|
|
|
|
|
|
<table><tr><th> Header </th>
|
|
|
<th> Arity </th>
|
... | ... | @@ -378,7 +378,7 @@ Where: |
|
|
- The payload is the sequence of arguments already applied to
|
|
|
this function. The pointerhood of these words are described
|
|
|
by the function's bitmap (see `scavenge_PAP_payload()` in
|
|
|
[rts/sm/Scav.c](https://gitlab.haskell.org/ghc/ghc/tree/master/rts/sm/Scav.c)[](/trac/ghc/export/HEAD/ghc/rts/sm/Scav.c) for an example of traversing a PAP).
|
|
|
[rts/sm/Scav.c](https://gitlab.haskell.org/ghc/ghc/tree/master/rts/sm/Scav.c) for an example of traversing a PAP).
|
|
|
|
|
|
|
|
|
There is just one standard form of PAP. There is just one info table
|
... | ... | @@ -426,7 +426,7 @@ It represents computation of a thunk that was suspended midway through evaluatio |
|
|
|
|
|
Since the payload is a chunk of stack, the GC can use its normal stack-walking code to traverse it.
|
|
|
|
|
|
`AP_STACK` closures are built by `raiseAsync()` in [rts/RaiseAsync.c](https://gitlab.haskell.org/ghc/ghc/tree/master/rts/RaiseAsync.c)[](/trac/ghc/export/HEAD/ghc/rts/RaiseAsync.c) when an [asynchronous exception](commentary/rts/async-exceptions) is raised. It's fairly typical for the end of an AP_STACK's payload to have another AP_STACK: you'll get one per update frame.
|
|
|
`AP_STACK` closures are built by `raiseAsync()` in [rts/RaiseAsync.c](https://gitlab.haskell.org/ghc/ghc/tree/master/rts/RaiseAsync.c) when an [asynchronous exception](commentary/rts/async-exceptions) is raised. It's fairly typical for the end of an AP_STACK's payload to have another AP_STACK: you'll get one per update frame.
|
|
|
|
|
|
### Indirections
|
|
|
|
... | ... | @@ -450,7 +450,7 @@ There are several variants of indirection: |
|
|
The update code (`stg_upd_frame_info` and friends) checks whether the updatee is in the youngest
|
|
|
generation before deciding which kind of indirection to use.
|
|
|
- `IND_STATIC`: a static indirection, arises when we update a `THUNK_STATIC`. A new `IND_STATIC`
|
|
|
is placed on the mutable list when it is created (see `newCaf()` in [rts/sm/Storage.c](https://gitlab.haskell.org/ghc/ghc/tree/master/rts/sm/Storage.c)[](/trac/ghc/export/HEAD/ghc/rts/sm/Storage.c)).
|
|
|
is placed on the mutable list when it is created (see `newCaf()` in [rts/sm/Storage.c](https://gitlab.haskell.org/ghc/ghc/tree/master/rts/sm/Storage.c)).
|
|
|
|
|
|
### Byte-code objects
|
|
|
|
... | ... | @@ -537,11 +537,11 @@ TSOs are ordinary objects that live in the heap, so we can use the existing allo |
|
|
GHC keeps divides stacks into stack chunks, with logic to handle stack underflow and overflow: [http://hackage.haskell.org/trac/ghc/blog/stack-chunks](http://hackage.haskell.org/trac/ghc/blog/stack-chunks)
|
|
|
|
|
|
|
|
|
The TSO structure contains several fields. For full details see [includes/rts/storage/TSO.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/storage/TSO.h)[](/trac/ghc/export/HEAD/ghc/includes/rts/storage/TSO.h). Some of the more important fields are:
|
|
|
The TSO structure contains several fields. For full details see [includes/rts/storage/TSO.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/storage/TSO.h). Some of the more important fields are:
|
|
|
|
|
|
- *link*: field for linking TSOs together in a list. For example, the threads blocked on an `MVar` are kept in
|
|
|
a queue threaded through the link field of each TSO.
|
|
|
- *global_link*: links all TSOs together; the head of this list is `all_threads` in [rts/Schedule.c](https://gitlab.haskell.org/ghc/ghc/tree/master/rts/Schedule.c)[](/trac/ghc/export/HEAD/ghc/rts/Schedule.c).
|
|
|
- *global_link*: links all TSOs together; the head of this list is `all_threads` in [rts/Schedule.c](https://gitlab.haskell.org/ghc/ghc/tree/master/rts/Schedule.c).
|
|
|
- *what_next*: how to resume execution of this thread. The valid values are:
|
|
|
|
|
|
- `ThreadRunGhc`: continue by returning to the top stack frame.
|
... | ... | @@ -550,7 +550,7 @@ The TSO structure contains several fields. For full details see [includes/rts/s |
|
|
- `ThreadRelocated`: this thread ran out of stack and has been relocated to a larger TSO; the link field points
|
|
|
to its new location.
|
|
|
- `ThreadComplete`: this thread has finished and can be garbage collected when it is unreachable.
|
|
|
- *why_blocked*: for a blocked thread, indicates why the thread is blocked. See [includes/rts/Constants.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/Constants.h)[](/trac/ghc/export/HEAD/ghc/includes/rts/Constants.h) for
|
|
|
- *why_blocked*: for a blocked thread, indicates why the thread is blocked. See [includes/rts/Constants.h](https://gitlab.haskell.org/ghc/ghc/tree/master/includes/rts/Constants.h) for
|
|
|
the list of possible values.
|
|
|
- *block_info*: for a blocked thread, gives more information about the reason for blockage, eg. when blocked on an
|
|
|
|
... | ... | |