Ali second side: Do you know the ALGORITHM of JVM three-color marking?

Welcome everyone to pay attention to my wechat public number [old week chat architecture], Java back-end mainstream technology stack principle, source code analysis, architecture and a variety of Internet high concurrency, high performance, high availability of solutions.

One, foreword

I have to say that ali’s interview was very quality, this question directly asked the JVM’s underlying algorithm implementation. Before we talk about the JVM’s tricolor labeling algorithm, let’s talk about the JVM’s common object survival determination algorithm and garbage collection algorithm. There are reference counting algorithm and reachability analysis algorithm. Reference counting can cause circular reference problems, and by default, the JVM uses an reachability analysis algorithm to determine whether an object is alive. And the garbage collection algorithms: mark-clean, mark-copy, mark-clean, and on top of that, the generational collection algorithms (new generation/old generation), each generation adopts a different collection algorithm to improve the overall allocation and collection efficiency.

So the first thing that these garbage collection algorithms do is they use the reachabability analysis algorithm to determine whether an object is alive or not, and they have to mark it first, and of course, if you don’t mark it and find the garbage, how do you collect it? The reachability analysis algorithm searches through a series of “GC Roots” objects as root nodes. If there is no reachability path between “GC Roots” and an object, it is said that the object is unreachable.

So far, all garbage collectors have had to pause The user thread during The root node enumeration step, so there is no doubt that they will face The “Stop The World” problem. Ah? “Stop The World”, or STW, means that The root node enumeration process must be performed in a consistent snapshot. In other words, it is like a persistent snapshot. At some point in time, The process is frozen. If the entire root node collection object reference is still changing during the root node enumeration, then the garbage collection analysis will not be accurate, so all user threads must be paused during garbage collection.

To solve or reduce pauses in user threads, three-color labeling algorithms come in. In order to let you understand why there is a three-color marker algorithm, Lao Zhou in the preface here paved a lot, hope to you see the following content will be helpful, then we will enter our topic.

Two and three color labeling algorithm

2.1 Basic Algorithm

Prior agreement:

According to the accessibility analysis algorithm, the traversal access starts with GC Roots.

• In the initial state, all objects are white, only the GC Roots are black.

• In the initial marking stage, the objects directly associated with GC Roots mark are set to gray.

• The concurrent markup phase scans the entire reference chain.
  • If there are no children, turn this node black.
  • If there are child nodes, the current node becomes black and the child nodes become gray.

• The concurrent marking phase is repeated until the grey object has no other child reference.

• The scan is complete

  The black object is a living object, and the white object is a dead and recyclable object.

  That is, (A, D, E, F, G) reachable is the living object, and (B, C, H) unreachable and recyclable object.

2.2 Defects of three-color labeling algorithm

If you remember from our introduction, all garbage collectors must suspend user threads during the root node enumeration step, resulting in STW, which is unacceptable for real-time systems. To solve or reduce the user thread pause problem, we introduced the three-color marker algorithm.

The tricolor labeling algorithm also has drawbacks. In the concurrent labeling phase, because the user thread and the GC thread are running at the same time, multiple or missed labeling may occur.

More than 2.3 standard

Suppose the application executes objD.fieldE = null (D > E reference broken)

If D > E is broken, E, F, and G are unreachable and should be reclaimed. However, since E is greyed, it will continue to be traversed as if it were a living object. The end result is that this part of the object is still marked as alive, meaning that this round of GC does not reclaim this part of memory.

The part of memory that should have been reclaimed but was not, is called floating garbage. Floating garbage does not affect the correctness of the application, it just has to wait until the next round of garbage collection to be cleared.

In addition, for the new objects after the start of concurrent marking, the usual practice is to directly treat all as black, and the epicycle will not be cleared. This part of the object may become garbage during the period, which is also considered part of floating garbage.

2.4 the leakage

Suppose the GC thread has already traversed E (gray), and the application thread executes first:

var G = objE.fieldG; 
objE.fieldG = null;  // Grey E breaks reference to white G
objD.fieldG = G;  // Black D refers to white G
Copy the code

At this point, we cut back to the GC thread, because E has no reference to G, so G is not set to gray; Although D rereferences G, it will not redo the traversal process because D is already black.

The final result is that G will remain white and will be removed as garbage. This directly affects the correctness of the application and is unacceptable.

It is not difficult to analyze that the missing mark can occur only when the following two conditions are met:

• One or more black objects rereference white objects; The black object member variable has a new reference.
• The gray object breaks the reference (direct or indirect) to the white object; That is, the reference to the original member variable of the gray object has changed.

The following code:

var G = objE.fieldG; / / 1. Read
objE.fieldG = null;  / / 2. Write
objD.fieldG = G;     / / 3. Write
Copy the code

In any of the three steps above, we simply record the object G and then iterate over it as a gray object. For example, put it into a particular collection and wait until the original GC Roots have traversed (concurrent marking) and then the objects of that collection have traversed (re-marking).

Resignations require STW, because if the application keeps running, the collection might keep adding new objects and never run out. Of course, concurrent tagging also allows most of the collection to run first, thus shortening the time to re-tag STW, which is an optimization problem. See? The three-color labeling algorithm can not completely solve the STW problem, but can only shorten the TIME of STW as far as possible to minimize the pause time.

Read barrier and write barrier

To address the problem of missing tags, the JVM team has adopted a read barrier and write barrier solution.

Read barrier is the first step of interception; Write barriers are used to block the second and third steps.

Their purpose is simple: to record the object G before and after the read and write.

3.1 read barrier

oop oop_field_load(oop* field) {
    pre_load_barrier(field); // Read barrier - operation before reading
    return *field;
}
Copy the code

The read barrier is directed at the first step: var G = obje.fieldg; When reading a member variable, record it first.

void pre_load_barrier(oop* field, oop old_value) {  
    if($gc_phase == GC_CONCURRENT_MARK && ! isMarkd(field)) { oop old_value = *field; remark_set.add(old_value);// Record the objects read}}Copy the code

It’s conservative, but it’s safe. In condition 1 (one or more black objects rereference white objects), the rereference is made only if the white object is obtained, and the read barrier is in effect.

3.2 write barriers

Let’s look at the second and third write operations. When we assign a member variable to an object, the underlying code is:

/ * * *@paramField A member variable of an object, such as e.ferrdg *@paramNew_value New value, such as null */
void oop_field_store(oop* field, oop new_value) { 
    *field = new_value; // Assign
} 
Copy the code

A write barrier is simply a process (similar to Spring AOP concepts) that is applied before and after assignment to an object’s member variables.

void oop_field_store(oop* field, oop new_value) {  
    pre_write_barrier(field); // Write barrier - Pre-write operation
    *field = new_value; 
    post_write_barrier(field, value); // Write barrier - After write operation
}
Copy the code

Incremental Update and Snapshot At The Beginning (SATB)

4.1 Incremental Update

When the reference to the member variable of object D changes (objd. fieldG = G;) We can use the write barrier to record D’s new member variable reference object G:

void post_write_barrier(oop* field, oop new_value) {  
    if($gc_phase == GC_CONCURRENT_MARK && ! isMarkd(field)) { remark_set.add(new_value);// Record the newly referenced object}}Copy the code

The idea is that instead of requiring the original snapshot to be retained, new references are logged for traversal, known as Incremental updates.

The incremental update breaks condition 1 of the missed mark: [one or more black objects re-reference white objects], thus ensuring no missed mark.

4.2 Original Snapshot

When references to member variables of object E change (obje.fieldg = null;) We can use the write barrier to record the reference object G to E’s original member variable:

void pre_write_barrier(oop* field) {
    oop old_value = *field; // Get the old value
    remark_set.add(old_value); // Record the original reference object
}
Copy the code

When the reference to the original member variable changes, record the original reference object.

The idea is to try to keep The object graph At The Beginning, The Snapshot At The Beginning (SATB), so that when The GC Roots are determined At a certain point, The object graph At that point is already determined.

For example, if E refers to G at that time, then subsequent tokens should follow the object graph at that time (E refers to G). If there is a change in the period, you can record it to ensure that the markup remains in the original view.

SATB breaks condition 2: [Grey object disconnects reference (direct or indirect reference) to white object], thus ensuring no omission.

Five, the summary

In the GC algorithm based on the accessibility analysis, the marking process almost all borrowed the algorithm idea of three-color marking, although the implementation methods are not the same, such as the marking methods of stack, queue, multi-color pointer, etc.

For the read and write barrier, taking Java HotSpot VM as an example, the processing scheme for the missing mark when concurrent marking is as follows:

• CMS: write barrier + incremental update
• The G1, Shenandoah: Write barrier + original snapshot
• ZGC: read barrier

Have you ever wondered why the above scheme is like this?

• The original snapshot is more efficient than the incremental update (although the original snapshot may cause more floating garbage) because there is no need to deep scan the deleted reference object again during the rescaling phase.
• However, CMS will do deep scanning for the root object of incremental reference. Since many objects are located in different regions, CMS is in an old region, and the cost of deep scanning for objects in G1 will be higher than that in CMS. Therefore, G1 chooses the original snapshot instead of deep scanning for objects, and simply marks. Wait until the next GC to scan in depth.
• And ZGC has an iconic pointer it USES is the design of the dyeing technology, dyeing pointer can significantly reduce the number of used memory barriers in the process of garbage collection, memory barriers, especially write barriers usually for the purpose of recording changes in object references, if these information directly to maintenance in the pointer, obviously could save some special record operation. ZGC doesn’t use a write barrier, only a read barrier, which is obviously a performance benefit.

Ok, this interview question said here, I believe you follow Lao Zhou’s article to read down, in the mind have their own want to answer, we next time goodbye.