The runtime system

Everything so far has been about producing an object file. This chapter is about what that object file links against.

The RTS is a substantial C program (garbage collection, thread scheduling, software transactional memory, profiling, the bytecode interpreter), and it is not optional. Laziness needs something to update thunks; lightweight threads need something to schedule them; allocation needs something to collect.

Its Notes are written in C comments, which is why the handbook’s extractor learns /* ... */ as well as {- ... -}. There are 184 of them.

The storage manager

GHC’s collector is generational and copying, and it is tuned for a language that allocates ferociously. Most Haskell allocations die immediately (a thunk is forced once and becomes garbage), so the youngest generation is collected often and cheaply, and only survivors are promoted.

Allocation itself is a pointer bump. The heap check emitted at Cmm level confirms there is room; if there is, allocating is incrementing a register.

Copying collection has a consequence worth internalising: objects move. A pointer held in a C library across a garbage collection is not valid unless it was pinned. This is why the FFI has pinned allocation, and why ByteString uses it.

The trade-off with a copying collector is pause time, which is what the non-moving collector addresses: a concurrent mark-and-sweep collector for the oldest generation, so a large heap does not mean a long pause:

When the non-moving collector is in use we must be careful to ensure that any
references to objects in the non-moving generation from younger generations
are pushed to the mark queue.

In particular we need to ensure that we handle newly-promoted objects are
correctly marked. For instance, consider this case:

    generation 0                          generation 1
   ──────────────                        ──────────────

                                           ┌───────┐
     ┌───────┐                             │   A   │
     │   B   │ ◁────────────────────────── │       │
     │       │ ──┬─────────────────┐       └───────┘
     └───────┘   ┆        after GC │
                 ┆                 │
     ┌───────┐   ┆ before GC       │       ┌───────┐
     │   C   │ ◁┄┘                 └─────▷ │   C'  │
     │       │                             │       │
     └───────┘                             └───────┘


In this case object C started off in generation 0 and was evacuated into
generation 1 during the preparatory GC. However, the only reference to C'
is from B, which lives in the generation 0 (via aging); this reference will
not be visible to the concurrent non-moving collector (which can only

traverse the generation 1 heap). Consequently, upon evacuating C we need to
ensure that C' is added to the update remembered set as we know that it will
continue to be reachable via B (which is assumed to be reachable as it lives
in a younger generation).

Where this happens depends upon the type of the object (e.g. C'):

 - In the case of "normal" small heap-allocated objects this happens in
   alloc_for_copy.
 - In the case of compact region this happens in evacuate_compact.
 - In the case of large objects this happens in evacuate_large.

See also Note [Aging under the non-moving collector] in NonMoving.c.

Concurrency here means real concurrency: mutator threads run while marking is in progress, so the collector needs a write barrier and a story for objects that move underneath it.

The scheduler

Haskell threads are not OS threads. forkIO creates a lightweight thread with a small, growable stack; the RTS multiplexes many of them onto a few OS threads called capabilities. Millions of threads is a reasonable thing to do.

Scheduling is cooperative, and the yield points are the heap checks. A thread that allocates will periodically reach one, which is where the RTS can take control. This has a well-known consequence: a tight non-allocating loop cannot be preempted, which is why such a loop can hang a program at -threaded.

Blocking on an MVar or an STM transaction removes a thread from the run queue entirely; the thread is placed on the queue of whatever it is waiting for and woken only when that changes. There is no polling.

Thunks, updates, and blackholes

Laziness lives here. Entering a thunk runs its code and overwrites it with the result, so the work is not repeated. That is the update.

If two threads enter the same thunk at once, both would compute it. The RTS overwrites a thunk under evaluation with a blackhole, so a second thread entering it blocks rather than duplicating work. Blackholes also make certain deadlocks detectable: a thread blocked on a blackhole owned by a thread blocked on the first is a cycle the RTS can find.

In GHC the garbage collector is responsible for identifying deadlocked
programs. Providing for this responsibility is slightly tricky in the
non-moving collector due to the existence of aging. In particular, the
non-moving collector cannot traverse objects living in a young generation
but reachable from the non-moving generation, as described in Note [Aging
under the non-moving collector].

However, this can pose trouble for deadlock detection since it means that we
may conservatively mark dead closures as live. Consider this case:

      moving heap  ┆  non-moving heap
    ───────────────┆──────────────────
                   ┆
     MVAR_QUEUE ←───── TSO ←───────────── gen1 mut_list
       ↑  │  ╰────────↗  │
       │  │        ┆     │
       │  │        ┆     ↓
       │  ╰──────────→ MVAR
       ╰─────────────────╯
                   ┆

In this case we have a TSO blocked on a dead MVar. Because the MVAR_TSO_QUEUE on
which it is blocked lives in the moving heap, the TSO is necessarily on the
oldest generation's mut_list. As in Note [Aging under the non-moving

collector], the MVAR_TSO_QUEUE will be evacuated. If MVAR_TSO_QUEUE is aged
(e.g. evacuated to the young generation) then the MVAR will be added to the
mark queue. Consequently, we will falsely conclude that the MVAR is still
alive and fail to spot the deadlock.

To avoid this sort of situation we disable aging when we are starting a
major GC specifically for deadlock detection (as done by
scheduleDetectDeadlock). This condition is recorded by the
deadlock_detect_gc global variable declared in GC.h. Setting this has a few
effects on the preparatory GC:

 - Evac.c:alloc_for_copy forces evacuation to the non-moving generation.

 - The evacuation logic usually responsible for pushing objects living in
   the non-moving heap to the mark queue is disabled. This is safe because
   we know that all live objects will be in the non-moving heap by the end
   of the preparatory moving collection.

The interpreter

GHCi does not compile to machine code by default. GHC/StgToByteCode.hs produces bytecode, and rts/Interpreter.c runs it, sharing the same heap objects and the same garbage collector as compiled code. Interpreted and compiled code interoperate directly, which is why you can load a package compiled to machine code and call into it from an interpreted expression.

We have a bco (obj), and its arguments are all on the stack. We can start
executing the byte codes.

The stack is in one of two states. First, if this BCO is a
function (in run_BCO_fun or run_BCO)

   |     ....      |
   +---------------+
   |     arg2      |
   +---------------+
   |     arg1      |
   +---------------+

Second, if this BCO is a case cont., as per Note [Case continuation BCOs] (only
in run_BCO):

   |     ....      |
   +---------------+
   |     fv2       |
   +---------------+
   |     fv1       |
   +---------------+
   |     BCO       |
   +---------------+

   | stg_ctoi_ret_ |
   +---------------+
   |    retval     |
   +---------------+
   | stg_ret_..... |
   +---------------+

where retval is the value being returned to this continuation.
In the event of a stack check, heap check, context switch,
or breakpoint, we need to leave the stack in a sane state so
the garbage collector can find all the pointers.

 (1) BCO is a function:  the BCO's bitmap describes the
     pointerhood of the arguments.

 (2) BCO is a continuation: BCO's bitmap describes the
     pointerhood of the free variables.

To reconstruct a valid stack state for yielding (such that when we return to
the interpreter we end up in the same place from where we yielded), we need to
differentiate the two cases again:

  (1) For function BCOs, the arguments are directly on top of the stack, so it
  suffices to add a `stg_apply_interp_info` frame header using the BCO that is
  being applied to these arguments (i.e. the `obj` being run)

  (2) For continuation BCOs, the stack is already consistent -- that's why we
  keep the ret and ctoi frame on top of the stack when we start executing it.

  We couldn't reconstruct a valid stack that resumes the case continuation
  execution just from the return and free vars values alone because we wouldn't
  know what kind of result it was (are we returning a pointer, non pointer int,
  a tuple? etc.); especially considering some frames have different sizes,
  notably unboxed tuple return frames (see Note [unboxed tuple bytecodes and tuple_BCO]).

  For consistency, the first instructions in a case continuation BCO, right
  after a possible BRK_FUN heading it, are two SLIDEs to remove the stg_ret_
  and stg_ctoi_ frame headers, leaving only the return value followed by the
  free vars. Theses slides use statically known offsets computed in StgToByteCode.hs.
  Following the continuation BCO diagram above, SLIDING would result in:

   |     ....      |
   +---------------+
   |     fv2       |
   +---------------+
   |     fv1       |
   +---------------+
   |    retval     |
   +---------------+

Reading the source yourself

The RTS is a different kind of code from the compiler: C, performance-critical, and with a lot of load-bearing macros.

1. rts/include/rts/storage/Closures.h first. Every heap object layout is here, and nothing else makes sense without it.
2. rts/Schedule.c: the main scheduler loop is readable and central.
3. rts/sm/GC.c for the collector; rts/sm/NonMoving.c only afterwards.
4. docs/rts/ and docs/storage-mgt/ in the tree contain design documents that predate and explain much of the code.

Build with -debug and run with +RTS -Ds to trace the scheduler. The RTS is also the one part of GHC you can meaningfully experiment with in isolation: it is a C library, and its behaviour is observable with ordinary C tooling.