Note [Dirty flags in the non-moving collector]

rts/sm/NonMoving.c:424 rts

Some mutable object types (e.g. MUT_VARs, TVARs) have a one-bit dirty flag
encoded in their info table pointer. The moving collector uses this flag
to minimize redundant mut_list entries. The flag is preserves the following
simple invariant:

    An object being marked as dirty implies that the object is on mut_list.

This allows a nice optimisation in the write barrier (e.g. dirty_MUT_VAR):
if we write to an already-dirty object there is no need to
push it to the mut_list as we know it's already there.

During GC (scavenging) we will then keep track of whether all of the
object's reference have been promoted. If so we can mark the object as clean.
If not then we re-add it to mut_list and mark it as dirty.

In the non-moving collector we use the same dirty flag to implement a
related optimisation on the non-moving write barrier: Specifically, the
snapshot invariant only requires that the non-moving write barrier applies
to the *first* mutation to an object after collection begins. To achieve this,
we impose the following invariant:

    An object being marked as dirty implies that all of its fields are on
    the mark queue (or, equivalently, update remembered set).

With this guarantee we can safely make the write barriers dirty objects
no-ops. We perform this optimisation for the following object types:

 - MVAR
 - TVAR
 - MUT_VAR

However, maintaining this invariant requires great care. For instance,
consider the case of an MVar (which has two pointer fields) before
preparatory collection:

   Non-moving heap     ┊      Moving heap
        gen 1          ┊         gen 0
 ──────────────────────┼────────────────────────────────
                       ┊
        MVAR A  ────────────────→ X
       (dirty)  ───────────╮
                       ┊   ╰────→ Y
                       ┊          │
                       ┊          │
          ╭───────────────────────╯
          │            ┊
          ↓            ┊
          Z            ┊
                       ┊

During the preparatory collection we promote Y to the nonmoving heap but
fail to promote X. Since the failed_to_evac field is conservative (being set
if *any* of the fields are not promoted), this gives us:

   Non-moving heap     ┊      Moving heap
        gen 1          ┊         gen 0
 ──────────────────────┼────────────────────────────────
                       ┊
        MVAR A  ────────────────→ X
       (dirty)         ┊
          │            ┊
          │            ┊
          ↓            ┊
          Y            ┊
          │            ┊
          │            ┊
          ↓            ┊
          Z            ┊
                       ┊

This is bad. When we resume mutation a mutator may mutate MVAR A; since it's
already dirty we would fail to add Y to the update remembered set, breaking the
snapshot invariant and potentially losing track of the liveness of Z.

To avoid this nonmovingScavengeOne we eagerly pushes the values of the
fields of all objects which it fails to evacuate (e.g. MVAR A) to the update
remembered set during the preparatory GC. This allows us to safely skip the
non-moving write barrier without jeopardizing the snapshot invariant.

References 0

This Note does not link to any other.

Referenced by 2