Three color tag, incremental updating with the original snapshot | August more challenges

# JVM garbage collector # G1 Garbage collector # JVM garbage collector # G1 garbage collector # G1 garbage collector # G1 garbage collector

Three color tag

The CMS garbage collector and G1 garbage collector both have concurrent marking process, so how do these two garbage collectors mark, the answer is tricolor marking. In the tri-color notation, objects encountered by Gcroots during the reachability analysis traversal of objects are marked with the following three colors based on whether they have been accessed:

  • Black: indicates that the object has been accessed by the garbage collector and all references to the object have been scanned together. The black object indicates that it is safe and survivable. If there are other object references to the black object, there is no need to scan again. A black object cannot point directly to a white object (without passing the gray object).

  • Gray: Indicates that the object has been accessed by garbage collection, but that the object’s related reference objects have not been scanned.

  • White: white said haven’t visited by the garbage collector, such as start accessibility analysis algorithm, all objects are white, after accessibility analysis algorithm, the object being accessed will become a black or white, if at the end of the analysis, object or white, that the object is inaccessible.

Therefore, since it is a concurrent mark, it may exist. For example, the D object may exist at the beginning, then it is removed or not at the beginning, and then it is added. Then, multiple marks or missing marks may occur, as shown in the following figure:

This concurrency phase results in two cases, multiple bids and missed bids:

  • Multiple bids: generates floating garbage
  • Missing labels: Missing labels can cause referenced objects to be deleted as garbage, which can cause bugs. The solution to this is incremental updates and raw snapshots

Incremental Update

Incremental update means that when a black object adds a reference to a white one, it will record the new reference back to itself, and then scan the black object in these recorded reference relationships as the root after the concurrent tag scanning overnight. So when a black object adds a reference to a white object, it becomes a gray object

Snapshot At The Beginning

Original snapshot. (SATB) is when there is a need to delete the object pointed to gray white object references, record the deleted references, again after the concurrent, then these records with gray object relations in as the root, to scan again, so you can scan the white object, and then these objects are marked as black (purpose is to make it An object can survive the current gc cleanup and be rescan for the next GC, or it may be floating garbage.

Write barriers

Both the insertion of the reference relationship record by incremental update and the deletion of the reference relationship record by original snapshot are implemented through write barriers. Write barriers are similar to AOP in Spring in that they add processing before and after assignment operations.

  • Write barriers implement incremental updates: When a reference to a member variable of an object changes, such as a new reference (a.b = B), we can use write barriers to record the reference of a member variable to object B.

  • Write barrier implementation SATB: When the reference of an object’s member variable changes, for example, the reference disappears (A.B.C = null), we can use the write barrier to record the reference of b’s original member variable c.

conclusion

For CMS and G1 collectors, the main processing methods for missing marks in concurrent marking are as follows:

  • CMS: Incremental update + write barrier
  • G1: Write barrier +STAB

Why is G1 SATB? CMS with incremental updates?

G1 is more efficient than STAB. SATB is more efficient than incremental updates, but it also generates more floating garbage because SATB does not need to deeply scan deleted references again during the relabelling phase. CMS is a fixed old age partition, whereas G1 has many regios N, so that many objects are located in different regions, and CMS only needs to conduct depth scan for one region. If G1 chooses incremental update, the cost will be relatively high. Therefore, G1 chooses SATB, simply marking, and carries out depth scan in the next GC. Q.E.D.