Version 13 (modified by diatchki, 8 years ago) (diff)


GHC Commentary: Garbage Collecting CAFs

Files: rts/sm/GC.c, function scavange_srt in rts/sm/Scav.h

Constant Applicative Forms, or CAFs for short, are top-level values defined in a program. Essentially, they are objects that are not allocated dynamically at run-time but, instead, are part of the static data of the program. Sometimes, a CAF may refer to many values in the heap. This is why, we need to know when a CAF is never going to be used again by the program, and hence the values to which it refers may be garbage collected.

Static Reference Tables

File: includes/rts/storage/InfoTables.h

The info table of various closures may contain information about what static objects are references by the closure. This information is stored in two parts:

  1. a static reference table (SRT), which is an array of references to static objects
  2. a bitmask which specifies which of the objects are actually used by the closure.

There are two different ways to access this information depending on the size of the SRT:

  • "small": if srt_bitmask is a small bitmask, not all 1s, then GET_FUN?_SRT contains the SRT.
  • "large": if srt_bitmask is all 1s, then GET_FUN?_SRT contains a large bitmap, and the actual SRT.

Evacuating Static Objects

Files: rts/sm/GCThread.h, rts/sm/Evac.c, rts/sm/GC.c

While scavenging objects, we also process (aka "evacuate") any static objects that need to be kept alive. When a GC thread discovers a live static object, it places it on its static_objects list. Later, this list is used to scavange the static objects, potentially finding more live objects. Note that this process might find more static objects, and thus further extend the static_objects list.

When a static object is scavenged, it is removed from static_objects and placed on another list, called scavenged_static_objects. Later, we use this list to "clean up" the liveness markers from these static objects, so that we can repeat the process on the next garbage collection. Note that we can't "clean up" the liveness markers as we go along because we use them to notice cycles among the static objects.