Implement canonical reference counting plan and RCImmix

[wks]

TL;DR: We need to port the RC and RCImmix plans from JikesRVM.

The algorithms

Reference counting is one of the basic canonical GC algorithms alongside MarkSweep, MarkCompact, and Semispace. The notable difference is its use of reference counting instead of tracing as the way to identify garbage. We need to include RC as well for completeness.

Here we list the algorithms we need to port to the Rust version of mmtk-core, and their characteristics:

• RC
  • Based on the RC plan in JikesRVM MMTk.
    • Use the same free-list allocator as MarkSweep
    • Primarily use RC, but also use back-up tracing.
    • Use deferral
    • Use coalescing
  • Apply optimisations introduced by Shahriyar et al. in ISMM'12
    • Limit the reference count bits.
    • Lazy mod-buf insertion.
    • Objects are allocated dead.
• RCImmix (Shahriyar et al. in OOPSLA'13)
  • Use the Immix allocator
  • Maintain a live-object counter for each Immix line
  • Move objects (1) when a young object survived a GC, and (2) when doing full-heap backup tracing

Related work

The LXR GC algorithm is based on RCImmix. The code is in a separate branch, but is not merged yet.

[k-sareen]

From memory there are/were flags that you could turn on and off to approximate RCImmix in LXR itself. In fact I believe Table 7 in the LXR paper demonstrates this. @wenyuzhao can clarify further.