3 ms·

The GC process does a full mark-and-sweep collection, so eventually it will have processed the entire heap. At that point, all garbage that existed when the col

by cwp 16y ago

The GC process does a full mark-and-sweep collection, so eventually it will have processed the entire heap. At that point, all garbage that existed when the collection started will have been collected, although new garbage will have been created by the program in the meantime. Similarly, all objects that survived the collection will have had their pointers fixed, and new objects will have had the correct pointers in the first place. The purpose of the read barrier is to allow the program to keep running while collection is happening. It lets the VM trap access to the parts of memory that the GC is working on, and do little bits of the collection algorithm in the program threads so they don't have to stop and wait for the GC thread to finish what it's doing.

modeless 16y ago
I guess I don't understand how the mark phase can work while the program is running. If the program is constantly modifying references then how does the GC know when it's done marking? If the program modifies an object that's already been scanned during this mark phase, does the GC have to go back and re-scan that object? If so, then how can you guarantee the mark phase will complete without stopping the program at some point?
- cwp 16y ago
  That's definitely the hard part. :-) From the interview: "We will find all the live objects in the heap in a single pass. We will never have to revisit any reference." So, no the GC never has to revisit any object, and it completes when it's scanned all live objects. The read-barrier is what prevents the program from interfering with the marking phase. That bit about unmapping virtual memory happens later when marked objects are being moved. As the GC walks through memory it's marking references by setting (or clearing) a bit in the pointer. Meanwhile the program goes about modifying objects by copying references - first reading them into a register and then writing them back out to the object's storage on the heap. The read triggers the read-barrier. If the reference being read has already been marked, great. If not, the trap handler marks the reference before allowing the program to continue. The write operation then writes a marked reference on to the heap, so no need for the GC thread to return to that object. Make sense?
  - modeless 16y ago
    How do you mark a single reference? Don't you have to mark all its children recursively, in the worst case scanning the whole heap (if this cycle just started and the GC thread hasn't gotten far yet) before returning control to the program?
    - psykotic 16y ago
      Marking is concurrent. The read barrier trap only has to mark the immediate reference. If the mutator that triggered the trap proceeds to reference one of the reference's children before the marker thread has gotten around to it, that will trigger another trap.
      - psykotic 16y ago
        BTW, you can read more in Cliff Click's USENIX paper from 2005: https://www.usenix.org/events/vee05/full_papers/p46-click.pdf https://www.usenix.org/events/vee05/full_papers/p46-click.pd...
    - cwp 16y ago
      Ah good catch. That detail isn't apparent from the interview. See this paper for more: https://www.usenix.org/events/vee05/full_papers/p46-click.pdf https://www.usenix.org/events/vee05/full_papers/p46-click.pd.... Basically, references contain flags that indicate whether the GC thread has already visited that reference. When the read-barrier traps, the handler checks the flag. If the reference has been visited already, fine. If not, it gets added to the GC thread's queue of objects to visit. Then the program marks the reference as visited, and continues. New objects are always marked visited, and aren't collected until the following GC cycle, so the current mark phase is guaranteed to complete.
    - rayiner 16y ago
      So when you're marking, you're working off a mark stack. You pop an object off the market stack, scan it and mark each of its children, then put any newly-marked children onto the mark stack. Note that the mark stack separates when an object gets marked from when it is scanned and its children marked. So when the read barrier triggers, you can mark the object and put it on the mark stack, as if you'd just scanned its parent. The object's children will get recursively marked when the marker processes the object from the mark stack, but that can happen independently of the read barrier fault.

by cwp 16y ago

modeless 16y ago

I guess I don't understand how the mark phase can work while the program is running. If the program is constantly modifying references then how does the GC know when it's done marking? If the program modifies an object that's already been scanned during this mark phase, does the GC have to go back and re-scan that object? If so, then how can you guarantee the mark phase will complete without stopping the program at some point?

cwp 16y ago
That's definitely the hard part. :-) From the interview: "We will find all the live objects in the heap in a single pass. We will never have to revisit any reference." So, no the GC never has to revisit any object, and it completes when it's scanned all live objects. The read-barrier is what prevents the program from interfering with the marking phase. That bit about unmapping virtual memory happens later when marked objects are being moved. As the GC walks through memory it's marking references by setting (or clearing) a bit in the pointer. Meanwhile the program goes about modifying objects by copying references - first reading them into a register and then writing them back out to the object's storage on the heap. The read triggers the read-barrier. If the reference being read has already been marked, great. If not, the trap handler marks the reference before allowing the program to continue. The write operation then writes a marked reference on to the heap, so no need for the GC thread to return to that object. Make sense?
- modeless 16y ago
  How do you mark a single reference? Don't you have to mark all its children recursively, in the worst case scanning the whole heap (if this cycle just started and the GC thread hasn't gotten far yet) before returning control to the program?
  - psykotic 16y ago
    Marking is concurrent. The read barrier trap only has to mark the immediate reference. If the mutator that triggered the trap proceeds to reference one of the reference's children before the marker thread has gotten around to it, that will trigger another trap.
    - psykotic 16y ago
      BTW, you can read more in Cliff Click's USENIX paper from 2005: https://www.usenix.org/events/vee05/full_papers/p46-click.pdf https://www.usenix.org/events/vee05/full_papers/p46-click.pd...
  - cwp 16y ago
    Ah good catch. That detail isn't apparent from the interview. See this paper for more: https://www.usenix.org/events/vee05/full_papers/p46-click.pdf https://www.usenix.org/events/vee05/full_papers/p46-click.pd.... Basically, references contain flags that indicate whether the GC thread has already visited that reference. When the read-barrier traps, the handler checks the flag. If the reference has been visited already, fine. If not, it gets added to the GC thread's queue of objects to visit. Then the program marks the reference as visited, and continues. New objects are always marked visited, and aren't collected until the following GC cycle, so the current mark phase is guaranteed to complete.
  - rayiner 16y ago
    So when you're marking, you're working off a mark stack. You pop an object off the market stack, scan it and mark each of its children, then put any newly-marked children onto the mark stack. Note that the mark stack separates when an object gets marked from when it is scanned and its children marked. So when the read barrier triggers, you can mark the object and put it on the mark stack, as if you'd just scanned its parent. The object's children will get recursively marked when the marker processes the object from the mark stack, but that can happen independently of the read barrier fault.