Meta: Heap traversal and dumping

[wks]

Requirements

There are requirements for heap traversal / heap dumping / object dumping:

• by GC developers
  • in production setting
    • Some GC algorithms need to enumerate live objects. For example, MarkCompact enumerates live objects in the MarkCompactSpace to compact objects.
  • for debugging
    • For debugging, GC developers want to inspect the object graph to see abnormal nodes
    • Related issue: Heap dumping for debugging GC or VM binding #805 A fail-slow mechanism for recording the trace during GC.
    • Related issue: Heap introspection API for debugging #1302 A fine-grained heap introspection API during mutator time.
• by VMs
  • Related issue: API for enumerating objects #795
  • All allocated objects (reachable or not, in no particular order)
    • Ruby:
      • ObjectSpace.each_object
    • JVM TI: IterateThroughHeap
    • Implemented in Heap traversal #1174
  • Subgraph (from given objects or from roots)
    • Ruby:
      • ObjectSpace.dump(obj) (from given obj)
      • ObjectSpace.dump_all (from roots)
      • rb_ractor_make_shareable
      • rb_objspace_reachable_objects_from
      • rb_objspace_reachable_objects_from_root
    • JVM TI: FollowReferences (from given object or all roots, depending on parameter)

Traversal mode

This is about both implementation and the API. Some requirements (such as ObjectSpace.each_object) can only be implemented in one way or another. Others (such as debugging) can use either way.

• Global / space-local metadata
  • Enumerating all objects using VO-bit
    • This method may visit dead (but not yet reclaimed) objects.
  • Enumerating objects in MarkCompactSpace using local metadata
• Transitive closure
  • From given object
  • From roots
    • This method only visits reachable objects from roots, but not dead (but not yet reclaimed) objects.

Time

Whether it happens at mutator time or GC time will have an impact on the implementation, such as synchornisation or the possibility of missing any newly allocated objects.

• At GC time
  • MarkCompact
    • during forwarding. The Plan is in total control of synchronisation.
  • Debugging
    • just before GC (all objects are in from-space)
    • just after GC (all objects are in to-space)
    • as we compute transitive closure (some objects are not yet moved while others are. Beware of inconsistent state!)
• At mutator time
  • whole-heap traversal (may miss some objects)
  • subgraph traversal (relatively deterministic unless other mutator threads interfere)