Shulou(Shulou.com)06/03 Report--

This article introduces the relevant knowledge of "how to achieve GC". In the operation of actual cases, many people will encounter such a dilemma. Next, let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

The implementation of garbage Collector ❝

This part of the content, the author so far, feel uncomfortable welcome to join the group discussion. Because I can't write something that is uncertain and mislead others. I want to be a moral writer.

❞

I stood on Mr. Zhou's shoulder and sang "this is how HotSpot implements the garbage collector!"

Root node enumeration

From the previous article, we learned something that can be fixed as a GC Roots, including static variables, constants, and method runtime context. We also know the reachability analysis algorithm (if you are not clear here, please refer to the author's first two articles, > "data-itemshowtype=" 0 "tab=" innerlink "data-linktype=" 2 "> put a portal here > >). However, with so many references at runtime, all of them can't be scanned by a virtual machine, GC for 2 seconds and scanning for 8 hours.

So you have the first stage of root node enumeration, which is to directly scan the part that is directly related to GC Roots. The operation of this step requires "Stop The World" (Stop The World is a term used to describe the state in which the user thread is paused at the safe point, which will be mentioned next).

When reachability analysis, the execution context and global references are not scanned one by one. In HotSpot, there is a data structure called OopMap that holds reference information. This common object pointer records the global reference and the relevant location of the execution context "specific" during class loading and immediate compilation, respectively. (this place is related to the following content, write it down.)

❝

OopMap (Ordinary Object Pointer) up to now, this part of the content can be seen according to the compilation results of the code, interested can be studied. The picture is from "in depth understanding the Java virtual machine" 3.4.1 code listings 3-3

OopMap ❞Security Point

From the above we know that what GC needs to do is to find out those referenced objects through OopMap, and this OopMap stores two kinds of data, one of which is global references, so it can be said that when the class is loaded, it will not change. What about the execution context? The method calls, stack frames, and so many variables (this part has been learned before, if not clear, you can go back to the previous article review, > "data-itemshowtype=" 0 "tab=" innerlink "data-linktype=" 2 "> re-summon portal > >). Wouldn't it be crazy to save all the bytecode instructions? So hotspot is not crazy, it only stores some specific locations to record this information in OopMap. There are several such specific locations during the execution of the program, and these specific locations are called "safe points".

You can only GC at a safe point

With security, we should know that GC can't be done all the time. You have to wait until the program reaches the safe point. It is not difficult to understand why, if you execute GC between two security points, whether it will lead to some execution context-sensitive references you do not know, because OopMap only stores the content of instructions in the nearest security point.

Where is the safe place?

After you understand that you have to wait until a safe point to GC, there is a new problem. (it is really difficult for GC to do it once.) you say this safe point, how many appropriate points do you put, and how much interval is reasonable? put it far away. You can't do GC for half a day and half a day. You can do it whenever you want to, but you have to know that this safe point is also an instruction. Do you think it's appropriate to insert so many extra instructions into the program? And this game should also be stored, ah, not OopMap to know. So the developers of hotspot studied it. Finally, there is a solution to compare ginkgo biloba.

Because the execution time of general instructions is very short, the solution is to give it a safe point in some parts of long-time execution, to prevent the program from executing for a long time. I have no way to GC. According to the characteristics of long-time execution, some places are obviously selected to sacrifice to heaven, they are method calls, loop back to the edge, abnormal jumps.

How to get to the safe point

Now we know that GC needs to find the relevant references in GC Roots through OopMap, and we know that we need to start looking for these references when we pause at the safe point, but there is a problem again. I know that GC should pause when the thread executes to the safe point, but how can each thread reach the nearest safe point and pause?

There are two ways, the virtual machine is forced to wait for you to get to the safe point, and the other depends on self-consciousness.

What does a virtual machine mean by forcibly waiting for you to get to a safe point? he also has a name "Preemptive Suspension", which is pre-emptive (preemptive interrupt). The virtual machine directly interrupts the user thread, and then see if you reach the safe point, continue to run, and then interrupt. Run again and again until all threads reach the safe point and the over task is completed.

Compared to the virtual machine against me to a safe point, I might as well consciously point * * Voluntary Suspension * * active interrupt. The virtual machine sends a safe point set signal, and all threads poll this set signal, and once the signal is true, the current thread will suspend when the nearest safe point arrives.

Life is short, I choose self-consciousness. Nowadays, most virtual machines choose a conscious way to reach the safe point. After all, pre-emptive strike is too immoral.

❝

The point-to-point content is the implementation of the polling operation of the thread. Because it needs to be executed frequently and efficiently. HotSpot uses only one assembly instruction to do this.

Test% eax,0x160100 when the user thread needs to be paused, the virtual machine makes the memory page of the 0x160100 unreadable. When the thread executes the test instruction, it generates a trap exception signal, and then suspends the thread to wait in the pre-registered exception handler.

❞security zone

This part can be regarded as an extension of the safe point, because during the execution of the program, there is no guarantee that all threads are running, or waiting or blocking, etc., so there is the concept of safe zone. This part of the area indicates that in this area, the reference relationship of the object will not change. It will not affect the normal progress of GC. When the user thread executes to the safe zone, it will mark itself that it is now in the safe zone. GC don't mind me. When the user thread comes out of the safe zone, say hello to GC, "GC, are you done?" I'm coming out. "if there is no GC action at this time, then you can come out. If this is in the root node enumeration phase, or at the stage where the collection process requires the user thread to pause, then the user thread will have to wait until the end of the GC to get out of the safe zone."

Memory set (Remembered Set)

The above GC process is fine when only the new generation of memory is used, but when it is not used in the old years, but once there is the problem of cross-generation reference mentioned in the previous article, it needs to be considered. Cross-generation reference refers to the existence of pointers that reference new-generation objects in the old era. In order to solve the problem caused by the intergenerational reference of objects, the garbage collector established a data structure called memory set (Remembered Set) in the new generation, which is used to record the pointer set from the non-collection area to the collection area. This will be used later not only in this new-generation and old-age collector, but also in the subsequent area collector.

❝

Zone collectors refer to G1, ZGC and Shenandoah collectors.

❞Card Table (Card Table)

With the concept of memory set, consider how to save information with intergenerational references, and you can save all objects with intergenerational references, but this takes up too much memory and is not easy to maintain. Therefore, there is a better recording scheme, which is to divide memory by region and record the part of memory with intergenerational references, which is called "card table".

HotSpot divides the whole heap into card pages with a size of 512 bytes and maintains them as a card table. The size of each card table defaults to 1 byte to store an identification bit 0 or 1 for each card. This identification bit represents the corresponding card "whether it is possible to have a reference to the new generation object". If possible, then this card is a "dirty card". In GC, you only need to filter the objects in the memory area corresponding to the dirty card, and you don't need to scan all the objects.

❝

Be careful not to confuse the concepts of memory sets and card tables, one is the defined data structure, and the other is the specific implementation method.

❞write barrier

Know that the use of card tables to solve intergenerational or cross-memory problems, when a card page may have intergenerational references, it will become dirty, then what is the process of getting dirty? How did it come true?

Normally, the time when the card table becomes dirty is when objects in the current area refer to objects in other areas, and the table is updated as a dirty table. If the interpretation and execution can be carried out one by one, the virtual machine can judge and operate according to the instructions of variable assignment, but in the process of instant compilation, this requires some corresponding machine instructions to operate. In the HotSpot virtual machine, the write barrier (Write Barrier) technology is used to maintain the card table state. "different from volatile's reordering barrier instruction! "

The specific implementation of this write barrier is divided into two, one is called the pre-write barrier and the other is called the post-write barrier. Their operation is similar to AOP, where they can make a notification before and after a variable assignment operation. Post-write barriers are mostly used in hotspot. In this way, the corresponding card table can be updated to a dirty table after the variable assignment operation.

Virtual sharing

Write barrier brings a problem, which is caused by CPU. Today's CPU cache contains data stored in buffer rows. In the case of multi-core processors, multiple threads may share a buffer line. For example, if the size of a buffer line is 32 kb, then a card table with 64 card pages (64 * 512 bytes) may be on the same buffer line. To address the wasted performance overhead of multiple threads updating the same buffer row at the same time. When hotspot updates the status of the card table, it adds a judgment of whether the current card table is a dirty table, and if it is a dirty table, it will no longer update the table.

❝

After JDK 7, the HotSpot virtual machine added a new parameter-XX:+UseCondCardMark, which is used to determine whether or not to turn on card table updates. Turning it on will increase the overhead of an additional judgment, but it can avoid the problem of pseudo-sharing, each of which has its own performance loss. Whether to open it or not should be tested and weighed according to the actual operation of the application.

Reachability Analysis of ❞concurrency

The above has gone through the details of the entire garbage collection process, and then we will take a look at the highlight, the reachability analysis algorithm, which is the inner part of the scan that has been mentioned above.

We know that the reachability analysis algorithm needs to pause the user thread before it can be used, that is, it needs Stop The World. Although the pause time for root node enumeration is very short, it still needs to be paused. At the same time, the pause will grow as the object of the system grows, which is proportional to the number of objects in the system.

Tricolor mark

At present, tricolor tags are used in the description of reachability analysis algorithms.

❝

I hope the content of this piece can be related to the previous finalize method. Remember the place we mentioned in the previous article where we saved ourselves once? we can look back later. This can help you deepen your understanding of this piece. Of course, only I will give you such a detailed reminder.

❞White: the color of death, that is, objects that are not referenced. It will only happen before GC starts marking work (before marking, everyone is white), and after GC work (marking is finished, you are white) Black: GC has already started to work here, and confirm that this node is alive, there are valid references, that is, all references to this object have been scanned. Objects referenced by black nodes must survive. The reachability analysis algorithm will not scan nodes that are already black (important, which will be used later in the understanding of tricolor marking) gray: GC has already started working here, but there is at least one reference on this object that has not been scanned. Concurrently marked problem ❝

Mr. Zhou's "in-depth understanding of the Java Virtual Machine" (third Edition) 3.4.6 illustrations

The picture in this example quotes Aleksey Shipilev's keynote speech on DEVOXX 2017: "Shenandoah GC Part I:The Garbage Collector That Could".

❞marking schematic diagram

The last two cases in the figure above illustrate the marking problem in the concurrency phase. Because concurrent markup means that the worker thread of the GC executes concurrently with the user thread, there is a situation where the object reference is changed while marking.

There are two kinds of problems in concurrent marking, one is missing mark, the other is mismarking. Omission means that an object that should be white is not marked white, and this problem generally does not have much impact. Waste a portion of memory at most and mark it again for recycling the next time you GC. Another kind of problem is mismarking. These two problems can be reflected in the last two above.

The harm of mismarking is very serious, if an object being referenced is mistakenly marked as white. Then the object is cleared after the end of the GC, which may directly cause the system to crash.

The cause of this problem has been confirmed, and mismarking will occur only if and only if the following two points are met.

The assigner inserts more than one reference from the black node to the white node and removes all references from the gray node to the white node directly or indirectly.

Through these two cases, it is not difficult for us to understand the occurrence of mismarking, because the rule of black node is that it will not be scanned, while gray will be scanned again. Therefore, the corresponding solution is relatively clear, just do not let the above two conditions be met at the same time. HotSpot uses incremental update and original snapshot solutions for the above two points, respectively.

Incremental update means that if a reference relationship is directed from a black node to a white node, then these black nodes need to be re-scanned as the root node at the end of the concurrent tag, that is, after the black node has a new reference relationship, it becomes a gray node. (this scheme is used by relabeling in the CMS collector)

The original snapshot means that if a gray node deletes a reference to a white node, the deleted reference needs to be recorded and rescanned as the root node in the reference relationship to the record at the end of the concurrent tag. Whether the object is deleted or not, it will be re-scanned again. (this is the scheme used by the final tag of G1)

"how to achieve GC" content is introduced here, thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.