Note [Scavenging the non-moving heap]
The moving GC promotes objects from the moving heap into the non-moving heap via evacuation and subsequent scavenging. This of course raises the question of how to keep track of which objects still require scavenging. The story here is as follows: - each GC thread maintains a list, `todo_seg`, of "todo" segments which still have outstanding scavenging work - similar to the moving collector, we use the scan pointer of a segment's block descriptor to track the first yet-to-be-scavenged object. - the first time we evacuate into an segment during a GC, we push the segment onto the `todo_seg` list - scavenge_find_work checks `todo_seg` as a source of scavenging work The scan pointer requires very careful treatment here. Specifically, we must only scavenge objects which we evacuated in the current GC to avoid issues like #21885. objects evacuated to the non-moving generation. In particular, objects can be allocated into the non-moving generation by two ways: a. evacuation out of from-space by the garbage collector b. direct allocation by the mutator Like all evacuation, objects moved by (a) must be scavenged, since they may contain references to other objects located in from-space.. However, we must not neglect to consider objects allocated by path (b). In short, the problem is that objects directly allocated by the mutator may become unreachable (but not swept, since the containing segment is not yet full), at which point they may contain references to swept objects. Specifically, we observed this in #21885 in the following way: 1. the mutator (specifically in #21885, a `lockCAF`) allocates an object (specifically a blackhole, which here we will call `blkh`; see Note [Static objects under the nonmoving collector] for the reason why) on the non-moving heap. The bitmap of the allocated block remains 0 (since allocation doesn't affect the bitmap) and the containing segment's (which we will call `blkh_seg`) `next_free` is advanced. 2. We enter the blackhole, evaluating the blackhole to produce a result (specificaly a cons cell) in the nursery 3. The blackhole gets updated into an indirection pointing to the cons cell; it is pushed to the generational remembered set 4. we perform a GC, the cons cell is evacuated into the nonmoving heap (into segment `cons_seg`) 5. the cons cell is marked 6. the GC concludes 7. the CAF and blackhole become unreachable 8. `cons_seg` is filled 9. we start another GC; the cons cell is swept 10. we start a new GC 11. something is evacuated into `blkh_seg`, adding it to the "todo" list 12. we attempt to scavenge `blkh_seg` (namely, all unmarked blocks between `scan` and `next_free`, which includes `blkh`). We attempt to evacuate `blkh`'s indirectee, which is the previously-swept cons cell. This is unsafe, since the indirectee is no longer a valid heap object. The problem here was that the scavenging logic previously assumed that (a) was the only source of allocations into the non-moving heap and therefore *all* unmarked blocks between `scan` and `next_free` were evacuated. However, due to (b) this is not true, since the scan pointer was only updated (1) when the segment was initialized (to point to block 0), and (2) when an object is scavenged (by advancing it to the next block). Consequently, at the beginning of a GC `scan` may point a block which was allocated by the mutator since the last GC. The solution is to ensure that that the scanned region only encompasses the region of objects allocated for evacuation during the present GC. We do this by updating `scan` as we push the segment to the todo-segment list to point to the block which was evacuated into.
References 0
This Note does not link to any other.