Three color mark removal method

1、 Overview of tricolor marking algorithm

When we do garbage scanning , I have learned two algorithms ： Reference counting and reachability analysis , stay Java We mainly use reachability analysis .

The three basic algorithms of reachability algorithm are ： Mark - eliminate , Mark - Copy , Mark - eliminate . If it's in STW Under the circumstances , Then neither algorithm will go wrong , It's just efficiency . But with the development of calculator hardware , The corresponding computer software technology and ideas are also progressing . For example, on the basis of multiple concurrency , Reduce STW Time for , Complete the garbage removal , Edge clear edge marker , This leads to Tri-color Marking Algorithm .

Tricolor refers to ： black 、 gray 、 white

• black : Represents the object and has been accessed by the garbage collector , And the references of this object have been scanned . Black objects represent and have been scanned , He survived safely , If there are other object references pointing to black objects , No need to scan again . Black objects can't be direct （ Without going through the gray object ） Point to a white object .
• gray : Indicates that the object has been accessed by the garbage collector , But at least one reference on this object has not been scanned
• white : Indicates that the object has not been accessed by the garbage collector . Obviously at the beginning of accessibility analysis , All objects are white , For example, at the end of the analysis , Still a white object , That is to say, it's impossible .

2、 The process of tricolor marking

Suppose there's white now 、 black 、 Grey three sets ( Represents the color of the current object )

1. At first , All objects are in In the white collection
2. take GC Roots Move directly referenced objects to In the grey set
3. from Grey sets Get object ：
   • Put the object to which this object refers into In the grey set
   • Put this object into In the black collection
4. Repeat step 3, until Grey sets Empty end
5. After the end , Still in White set The object of is GC Roots Unreachable , Can be recycled .

notes ： If the object is still white after the tag ends , It means that you have “ Can't find ” Where is the object , It's impossible to be quoted again . For example, there is no reference to H 了 , It's white , There can be no more object references to it .

3、 Existing problems

Both user threads and garbage collection threads are threads , Naturally there is a pause time , If the time slice of the garbage collection thread is up , The user thread does other operations , This leads to the problems of wrong and missing marks .

3.1 Wrong mark

Marked as not garbage , It's rubbish （ Also known as floating garbage ）, Pictured ：

The garbage collection thread has just D Finish sweeping , take D Marked black , The garbage collection thread time is up , The garbage collection thread is paused . The user thread will D Point to E Change the relationship of to ,D.E=null, From our point of view ,E It's garbage , however E Still grey , After scanning E after ,E Will turn black , But this does not affect the execution of the program , In the next garbage collection , The garbage collection thread will E Recycle .

3.2 Missing mark

This problem is quite serious , As shown in the figure below

Garbage collection thread take D Marked in black , Express D The scan is complete . Go now Scan his references E, But at this time The garbage collection thread is paused , The user thread performs such an operation ：E.G = null, D.G = G. Then the garbage collection thread comes back Continue scanning E,** At this time in E It seems ,G Is an unreachable object . however D And then I quote G, But D It's black , I won't go back and do it again , Garbage collection is over ,G Its color is white , To be removed ,D To call G object , A null pointer exception occurred .** It's really a terrible thing .

4、 Solve the problem of killing by mistake

As described above , Wrong killing only happens when The following two conditions occur simultaneously , Will happen ：

1. Black objects point to white objects
2. The gray object that originally pointed to the white object was disconnected from him

4.1 CMS： Write barriers + Incremental updating （Incremental Update）

stay CMS in , If this happens ： Black objects point to white objects （D.G = G）, Before performing the operation , Use Hook function ( Write barriers , Be similar to AOP), Put the object D From black to gray , This makes it possible to scan D 了 .

So for the grey set , It is an incremental update .

4.2 G1： Write barriers + Original snapshot （STAB）

stay G1 in , This is the case ： Gray objects break references to white objects (E.G = null), Before performing the operation , Use Hook function ( Write barriers , Be similar to AOP), Record the reference to be deleted , At the end of the concurrent scan , Scan again .

And the idea is that ： Taste Try to keep the object graph at the beginning , The original snapshot （Snapshot At The Beginning,SATB）, At some point Of GC Roots after , At that time, the object graph was determined .

such as at that time D It's quoting G Of , Then the subsequent tags should follow the object diagram of this moment （D Quote G）. If the period changes , You can record it , Make sure that the tags are still as they were .