Confirmed users
329
edits
Sfink/Moving GC: Difference between revisions
Jump to navigation
Jump to search
clarify some small things
(minor fixups) |
(clarify some small things) |
||
| Line 1: | Line 1: | ||
All garbage | All garbage collectors (GC) need to know what objects are reachable and therefore need | ||
to be alive. Tracing GCs require a way to find the exact set of objects that are | |||
currently reachable. This requires knowing about all pointers into the JS heap | currently reachable. This requires knowing about all pointers into the JS heap | ||
("roots"), as well as all pointers within the JS heap (the "heap graph"). GC | ("roots"), as well as all pointers within the JS heap (the "heap graph"). GC | ||
will do a graph traversal starting from the roots and visiting everything | will do a graph traversal starting from the roots and visiting everything | ||
reachable | reachable. | ||
A generational garbage collector (GGC) defines a subset of the JS heap as the | A generational garbage collector (GGC) defines a subset of the JS heap as the | ||
"nursery", and allocates most objects out of this nursery in the expectation | "nursery", and allocates most objects out of this nursery in the expectation | ||
that many of them will die quickly (become unused and | that many of them will die quickly (become unused and unreachable). The | ||
collector periodically sweeps through the nursery, packing only the live | collector periodically sweeps through the nursery, packing only the live | ||
objects into another area so that the nursery is empty and available for new | objects into another area so that the nursery is empty and available for new | ||
allocations again. It is important that this nursery sweep (a "minor | allocations again. It is important that this nursery sweep (a "minor | ||
collection") only | collection") only needs to look at the *live* objects (plus some bookkeeping | ||
information), NOT the full heap | information), NOT the full heap or even a percentage of it -- you want the | ||
cost of minor collections to be proportional only | cost of minor collections to be proportional to only the amount of live data in | ||
the nursery, and independent of the amount of garbage. | the nursery, and independent of the amount of garbage. | ||
| Line 23: | Line 24: | ||
heap are recorded, then the main program is allowed to continue running but is | heap are recorded, then the main program is allowed to continue running but is | ||
interrupted periodically so the incremental collector can gradually trace the | interrupted periodically so the incremental collector can gradually trace the | ||
whole heap graph. Because the graph can change during this sweep, any | whole heap graph. Because the graph can change during the overall duration of this sweep, any | ||
intra-heap reference that is deleted must be marked (treated as live): such | intra-heap reference that is deleted must be marked (treated as live): such | ||
referents are usually either dead or reachable from somewhere else, but it's also possible that the main program | |||
moved a reference from a part of the heap that has not yet been scanned to a | moved a reference from a part of the heap that has not yet been scanned to a | ||
part that has already been scanned, and so | part that has already been scanned, and so the referent will not get marked during the | ||
rest of the incremental collection. This adds a required capability (3): a | rest of the incremental collection. This adds a required capability (3): a | ||
record of all pointers within the heap that were deleted while incremental GC | record of all pointers within the heap that were deleted while incremental GC | ||
was active. Note | was active. (Note: this is actually accomplished by pushing them on the same mark stack used to record the current state of the incremental GC.) | ||
Capability #1 means that we need to be able to find and update all pointers | Capability #1 means that we need to be able to find and update all pointers | ||
| Line 40: | Line 41: | ||
modify a pointer into the heap, you may need to do something before and/or after | modify a pointer into the heap, you may need to do something before and/or after | ||
the write to update bookkeeping information. Capability #2 requires a | the write to update bookkeeping information. Capability #2 requires a | ||
"post-barrier", an action taken after the write occurs | "post-write barrier" aka post barrier, an action taken after the write occurs, to store a record of | ||
any new pointer value that points (or might point) into the nursery. Capability #3 | any new pointer value that points (or might point) into the nursery. Capability #3 | ||
requires a "pre-barrier", an action taken before the write occurs, so it can | requires a "pre-write barrier" aka pre barrier, an action taken before the write occurs, so it can | ||
mark the overwritten value as live (before it is lost from the | mark the overwritten value as live (before it is lost from the | ||
graph). | graph). The exact timing isn't critical; the pre barrier really just needs the old value | ||
and the post barrier needs the new value, but both could run either before or after the actual | |||
write (as long as there's no possibility of a GC in between the barrier and the write!) | |||
--- | --- | ||
| Line 57: | Line 60: | ||
updatable during a moving GC. This is usually accomplished with Rooted<T>, | updatable during a moving GC. This is usually accomplished with Rooted<T>, | ||
Handle<T>, and MutableHandle<T>, though aggregates of various sorts will also | Handle<T>, and MutableHandle<T>, though aggregates of various sorts will also | ||
use | use Auto*Rooter classes. Pointers from the stack to either the | ||
stack or the C++ heap don't matter. | stack or the C++ heap don't matter (such pointers are not pointing to GC things.) | ||
Pointers from the C++ heap to the JS heap must be findable and updatable, and | Pointers from the C++ heap to the JS heap must be findable and updatable, and | ||
| Line 68: | Line 71: | ||
barriered, in case they change to point to the nursery (for GGC) or move an | barriered, in case they change to point to the nursery (for GGC) or move an | ||
unscanned subgraph into the already-scanned region (for IGC). Pointers from | unscanned subgraph into the already-scanned region (for IGC). Pointers from | ||
tenured to the stack (?!) or the C++ heap don't matter. | tenured to the stack (?!) or the C++ heap don't matter (again, these aren't pointing at GC things.) | ||
Pointers from the nursery are the same as those from tenured, except it doesn't | Pointers from the nursery are the same as those from tenured, except it doesn't | ||
matter for GGC if a nursery pointer points to the nursery vs tenured. So the | matter for GGC if a nursery pointer points to the nursery vs tenured since everything still alive in the nursery will be scanned. So the | ||
post barrier is not needed. The pre barrier is not needed because incremental GC does a nursery collection | post barrier is not needed. The pre barrier is not needed because incremental GC does a nursery collection when it begins, and anything | ||
allocated from that point to the end of the GC will always be treated as live. | |||