Editing Yhc/RTS/GC (section)

== Mark ==

Yhc uses a fairly standard [[Yhc/RTS/PointerReversal]] mark phase to find all the heap nodes that are reachable from the program roots (and thus are still alive).

One thing of interest is that Yhc uses a seperate table of mark bits rather than having the mark bit as a field of each heap node. This is described in [[Yhc/RTS/Machine]].

The program roots for Yhc are:
  - For each process stack (see [[Yhc/RTS/Machine]]):
       - The stack itself (stacks are heap nodes).
       - All the entries in the stack that are 'stack data' (i.e. not stack frames).       
       - For each stack frame the vapptr pointer.

  - For each heap global (see [[Yhc/RTS/Primitive]]):
       - The contents of the global pointer.

  - For each FInfo node which is reachable from the heap:
       - All the references to heap nodes in the constant table of the FInfo.

The most complicated part is the FInfos. FInfos have constant-tables which contain references to heap nodes and references to other FInfos that the function might call (see [[Yhc/RTS/Machine]]).

Thus the constant tables act as another form of program root, however, we only need to save the nodes referenced in a constant table of a FInfo if that FInfo is reachable from some node in the heap. A FInfo is reachable if it is either referenced by a node in the heap or it is referenced from a reachable FInfo.

Thus when a node in the heap is marked, if it is an application to a FInfo then the FInfo is added to end of the list of live FInfos. The first FInfo in this list is stored in the global variable G_firstCaf (the name 'Caf' here is a historical carry over from nhc, it is not only Cafs that are of interest in this process).

The 'link' field in the FInfo (see [[Yhc/RTS/Machine]]) is used to link the FInfos in the list together. It also serves as a 'mark bit' for the FInfo; if a FInfo's link field is already set then this FInfo has already been added to the list.

When all the heap nodes reachable from the other (non-FInfo) roots have been marked the FInfo list is traversed. All nodes that are referenced from the constant table are marked and all new FInfos references from the constant table are added to the end of the FInfo list.

Marking the heap is O(L) where L is the number of live objects in the heap.