... | ... | @@ -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 [includes/rts/storage/Closures.h](/trac/ghc/browser/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](/trac/ghc/browser/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:
|
|
|
|
|
|
[](/trac/ghc/attachment/wiki/Commentary/Rts/Storage/HeapObjects/heap-object.png)
|
|
|
|
|
|
|
|
|
A heap object always begins with a *header*, defined by `StgHeader` in [includes/rts/storage/Closures.h](/trac/ghc/browser/ghc/includes/rts/storage/Closures.h):
|
|
|
A heap object always begins with a *header*, defined by `StgHeader` in [Closures.h](/trac/ghc/browser/includes/rts/storage/Closures.h)[](/trac/ghc/export/HEAD/ghc/includes/rts/storage/Closures.h):
|
|
|
|
|
|
```wiki
|
|
|
typedef struct {
|
... | ... | @@ -62,7 +62,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 [includes/rts/storage/InfoTables.h](/trac/ghc/browser/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](/trac/ghc/browser/includes/rts/storage/InfoTables.h)[](/trac/ghc/export/HEAD/ghc/includes/rts/storage/InfoTables.h). The basic info table layout looks like this:
|
|
|
|
|
|
[](/trac/ghc/attachment/wiki/Commentary/Rts/Storage/HeapObjects/basic-itbl.png)
|
|
|
|
... | ... | @@ -71,8 +71,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 [includes/rts/storage/ClosureTypes.h](/trac/ghc/browser/ghc/includes/rts/storage/ClosureTypes.h), and many of them have corresponding C struct
|
|
|
definitions in [includes/rts/storage/Closures.h](/trac/ghc/browser/ghc/includes/rts/storage/Closures.h).
|
|
|
the closure types are defined in [ClosureTypes.h](/trac/ghc/browser/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](/trac/ghc/browser/includes/rts/storage/Closures.h)[](/trac/ghc/export/HEAD/ghc/includes/rts/storage/Closures.h).
|
|
|
|
|
|
- The *SRT bitmap* field is used to support [garbage collection of CAFs](commentary/rts/ca-fs).
|
|
|
|
... | ... | @@ -137,9 +137,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 1 if the corresponding word of payload contains a pointer to a live object.
|
|
|
|
|
|
|
|
|
The macros `MK_BITMAP`, `BITMAP_SIZE`, and `BITMAP_BITS` in [includes/rts/storage/InfoTables.h](/trac/ghc/browser/ghc/includes/rts/storage/InfoTables.h) provide ways to conveniently operate on small bitmaps.
|
|
|
The macros `MK_BITMAP`, `BITMAP_SIZE`, and `BITMAP_BITS` in [InfoTables.h](/trac/ghc/browser/includes/rts/storage/InfoTables.h)[](/trac/ghc/export/HEAD/ghc/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 [includes/rts/storage/InfoTables.h](/trac/ghc/browser/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](/trac/ghc/browser/includes/rts/storage/InfoTables.h)[](/trac/ghc/export/HEAD/ghc/includes/rts/storage/InfoTables.h).
|
|
|
|
|
|
---
|
|
|
|
... | ... | @@ -154,7 +154,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/MBlock.h](/trac/ghc/browser/ghc/rts/sm/MBlock.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/MBlock.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
|
|
|
|
... | ... | @@ -162,7 +162,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](/trac/ghc/browser/ghc/includes/rts/Constants.h).
|
|
|
The minimum size of the payload is given by `MIN_PAYLOAD_SIZE` in [includes/rts/Constants.h](/trac/ghc/browser/includes/rts/Constants.h)[](/trac/ghc/export/HEAD/ghc/includes/rts/Constants.h).
|
|
|
|
|
|
### Static objects
|
|
|
|
... | ... | @@ -180,7 +180,7 @@ all the static objects in order to [garbage collect CAFs](commentary/rts/ca-fs). |
|
|
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](/trac/ghc/browser/ghc/includes/rts/storage/ClosureMacros.h).
|
|
|
`STATIC_LINK()` macro from [includes/rts/storage/ClosureMacros.h](/trac/ghc/browser/includes/rts/storage/ClosureMacros.h)[](/trac/ghc/export/HEAD/ghc/includes/rts/storage/ClosureMacros.h).
|
|
|
|
|
|
---
|
|
|
|
... | ... | @@ -337,7 +337,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](/trac/ghc/browser/ghc/rts/StgStdThunks.cmm).
|
|
|
see [rts/StgStdThunks.cmm](/trac/ghc/browser/rts/StgStdThunks.cmm)[](/trac/ghc/export/HEAD/ghc/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`.
|
... | ... | @@ -379,7 +379,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](/trac/ghc/browser/ghc/rts/sm/Scav.c) for an example of traversing a PAP).
|
|
|
[rts/sm/Scav.c](/trac/ghc/browser/rts/sm/Scav.c)[](/trac/ghc/export/HEAD/ghc/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
|
... | ... | @@ -427,7 +427,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](/trac/ghc/browser/ghc/rts/RaiseAsync.c) when an [asynchronous exception](commentary/rts/async-exceptions) is raised.
|
|
|
`AP_STACK` closures are built by `raiseAsync()` in [rts/RaiseAsync.c](/trac/ghc/browser/rts/RaiseAsync.c)[](/trac/ghc/export/HEAD/ghc/rts/RaiseAsync.c) when an [asynchronous exception](commentary/rts/async-exceptions) is raised.
|
|
|
|
|
|
### Indirections
|
|
|
|
... | ... | @@ -458,7 +458,7 @@ There are several variants of indirection: |
|
|
cost center in an indirection, so we can't eliminate the indirection.
|
|
|
- `IND_OLDGEN_PERM`: same as above, but for the old generation.
|
|
|
- `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](/trac/ghc/browser/ghc/rts/sm/Storage.c)).
|
|
|
is placed on the mutable list when it is created (see `newCaf()` in [rts/sm/Storage.c](/trac/ghc/browser/rts/sm/Storage.c)[](/trac/ghc/export/HEAD/ghc/rts/sm/Storage.c)).
|
|
|
|
|
|
### Byte-code objects
|
|
|
|
... | ... | @@ -494,14 +494,14 @@ Closure type `TSO` is a Thread State Object. It represents the complete state o |
|
|
TSOs are ordinary objects that live in the heap, so we can use the existing allocation and garbage collection machinery to manage them. This gives us one important benefit: the garbage collector can detect when a blocked thread is unreachable, and hence can never become runnable again. When this happens, we can notify the thread by sending it the `BlockedIndefinitely` exception.
|
|
|
|
|
|
|
|
|
GHC keeps stacks contiguous, there are no "stack chunk" objects. This is simpler, but means that when growing a stack we have to copy the old contents to a larger area (see `threadStackOverflow()` in [rts/Schedule.c](/trac/ghc/browser/ghc/rts/Schedule.c)). (EZY: I'm pretty sure this is not the case anymore, see [ http://hackage.haskell.org/trac/ghc/blog/stack-chunks](http://hackage.haskell.org/trac/ghc/blog/stack-chunks))
|
|
|
GHC keeps stacks contiguous, there are no "stack chunk" objects. This is simpler, but means that when growing a stack we have to copy the old contents to a larger area (see `threadStackOverflow()` in [rts/Schedule.c](/trac/ghc/browser/rts/Schedule.c)[](/trac/ghc/export/HEAD/ghc/rts/Schedule.c)). (EZY: I'm pretty sure this is not the case anymore, see [ 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](/trac/ghc/browser/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](/trac/ghc/browser/includes/rts/storage/TSO.h)[](/trac/ghc/export/HEAD/ghc/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](/trac/ghc/browser/ghc/rts/Schedule.c).
|
|
|
- *global_link*: links all TSOs together; the head of this list is `all_threads` in [rts/Schedule.c](/trac/ghc/browser/rts/Schedule.c)[](/trac/ghc/export/HEAD/ghc/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.
|
... | ... | @@ -510,7 +510,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](/trac/ghc/browser/ghc/includes/rts/Constants.h) for
|
|
|
- *why_blocked*: for a blocked thread, indicates why the thread is blocked. See [includes/rts/Constants.h](/trac/ghc/browser/includes/rts/Constants.h)[](/trac/ghc/export/HEAD/ghc/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
|
|
|
|
... | ... | |