Two weekends of garbage collection, and I’m spitting blood

nagging

Today’s liver goods, the author has liver vomiting blood, read a book to check the information sorted out the 10,000 words of garbage recycling related knowledge, although it is very long, but after reading, I believe you will have a lot of goods, ah, the weekend did not, the heart is very painful.

We’ll get right down to business with “Interview Must-Ask” garbage collection, and after reading you’ll learn all of the following, “including but not limited to” :

How is it found? What does OopMap do? Why do WE need STW? What does a memory set do? What are the seven common garbage collectors? Tricolor labeling algorithm? Why does A CMS have fragmentation? G1 causes Full GC? .

How are garbage objects found?

Reference counting algorithm

Add a counter to the object

• Every time it is referenced somewhere, the counter is incremented by one
• Each time a reference is invalid, the counter is decayed by one

“When the counter is 0, the object is garbage.”

The principle of this scheme is simple and the determination is very efficient, but there may be additional cases to consider.

Such as two “circular reference” * * * *, a object references the b objects, object b also cited a object, a and b object has no longer be referenced by other objects, but normally the two objects are garbage, because there is no other objects in the use, but in the counter value is not zero, so reference counting algorithm will not be able to recycle them.

This algorithm is compared to “directly find garbage” and then recycle it, also known as “direct garbage collection”.

Root reachable algorithm

This is also ** the “default JVM” ** algorithm for finding garbage

The principle is to define a series of Roots, which we call “GC Roots”, and search from “GC Roots” down the path we call “reference chain”. When there is no reference chain between an object and “GC Roots”, This object can then be garbage collected.

Object 6, Object 7, and Object 8 have previous references to each other, but are not connected to “GC Roots”, so they will be recycled as garbage.

In Java, there are ** “fixed GC Roots object” and “unfixed temporary GC Roots object:” **

“Fixed GC Roots:”

• 1. In ** “objects referenced in the virtual machine stack (local variables of stack frames)” **, such as parameters, local variables, temporary variables, etc. used in the method stack that each thread is called.
• In the method area ** “objects referenced by class static attributes” **, such as Java class reference static variables.
• In the method area ** “constant reference object” **, such as a reference in the string constant pool.
• In the method stack “objects referenced by JNI (such as Native methods)”.
• Java “virtual machine references”, such as Class objects corresponding to basic data types, some resident exception objects (null pointer exceptions, OOM, etc.), and Class loaders.
• All “objects held by Synchronized” **.
• “Jmxbeans, callback local code caches registered in JVMTI, and so on” reflect the internal conditions of the Java virtual machine.

“Temporary GC Roots:”

“Why are there temporary GC Roots?”

Most of the current garbage collection is “generational collection and local collection”. If only a part of the local collection, then we must consider “objects in the current region may be referenced by objects in other regions” **. At this time, the associated objects should be added to GC Roots to ensure the accuracy of the root reachable algorithm.

This algorithm uses “reverse thinking” to find what is being used and what is left is garbage, also known as “indirect garbage collection”.

Four reference types

Strong reference

“Object o = new Object()” is a strong reference, and it’s the kind of reference we use most often in our code.

In any case, the garbage collector will not reclaim the referenced object as long as the strong reference relationship exists.

Soft references

When there is insufficient memory, soft reference objects are reclaimed.

String str = new String(“abc”); // SoftReference softRef = new SoftReference(STR); // SoftReference softRef = new SoftReference(STR);

Soft references are used to describe objects that are useful but unnecessary.

A weak reference

Weak references are weaker than soft references in that they ** “only survive until the next garbage collection” **.

That is, the garbage collector starts working and reclaims all objects that are associated only with weak references.

// WeakReference weakRef = new WeakReference(STR);

Weak references are used in ThreadLocal to prevent memory leaks.

Phantom reference

A virtual reference is the weakest type of reference, and its sole purpose is to serve as a notification.

For example, Zero Copy creates out-of-heap memory, and virtual references are used here to store this information in a queue for subsequent collection management of out-of-heap memory.

Generation collection theory

Most garbage collectors are designed to follow the theory of generational collection, which is based on two generational hypotheses:

• “Weak generation hypothesis” : most objects rise and die.
• The “strong generation hypothesis” : the more garbage collections an object goes through, the harder it is to die.

The design principles for both hypotheses are the same:

The garbage collector ** “should divide the JVM into different regions” ** so that objects that are more difficult to collect can be grouped together so that the frequency of garbage collection in this region is reduced and the overhead of garbage collection is reduced. The rest of the region (generally the new generation) can be collected at a higher frequency and can be collected at a lower cost by only caring about the objects that are still alive and not having to mark the garbage to be collected.

• “Cross-generation reference hypothesis” : If a new generation object has a cross-generation reference, but the old object is difficult to die, then over time, the new generation object will gradually become the old object, and the cross-generation reference will be eliminated.

Since cross-generation references are rare, we should not scan the entire old age for a few cross-generation references. Instead, we need to create a ** “memory set” ** in the new generation object to record the reference information.

Memory set: “Divide the old years into chunks with N objects in each region” to maintain the accuracy of the memory set data when the object reference information changes, so that every time a “Minor GC” occurs, only the objects in the memory set are added to the “GC Roots”.

Three garbage collection algorithms

Mark clearing algorithm

The implementation of this algorithm is very simple, there are two ways [image upload…(image.png-4217FD-1608451822685-0)]

• 1. Mark trash and remove it
• 2. Mark the inventory and recycle the rest of the space

This algorithm has two drawbacks

• 1. The more objects there are, the more time it takes
• 2. Tag clearing will lead to fragmentation. If there is a large object allocation, it is likely that the allocation will not be enough to start another garbage collection action

Mark copy algorithm

This algorithm solves the problem of fragmentation of the first algorithm.

Is * * * “” open up two pieces of the same area, the object only in one area distribution, and then to” tag “out the” survival of the object, the overall move to another room “in sequence, the diagram below, you can see the recovery after the object is arranged orderly, it only need to move the cursor can be completed, the efficiency is very high, “Then reclaim the space before removal” **.

The disadvantages of this algorithm are also obvious

• Waste too much memory, making the available space “half” as it used to be

Tag sorting algorithm

This algorithm can be said to be a combination of the first two algorithms, both mark deletion, and sorting function.

The algorithm finds the living objects by using a mark-clearing algorithm, moves all the “living objects, toward one end of space”, and reclaims the rest of memory.

However, this algorithm has the disadvantage of having to suspend the user’s application (” STW “) to move an object.

STW

The “stop-the-world” mechanism in Java, STW for short, is that all other threads of The Java application are suspended (except for The garbage collector helper) while The garbage collection algorithm is being executed. A global pause in Java in which all Java code stops and native code can execute but cannot interact with the JVM.

Why do WE need STW

In Java applications ** reference relationships are constantly “changing”, so there are a number of situations where “spam” can go wrong.

Imagine if Object A is currently garbage, and the GC marks it as garbage, but there are other objects pointing to Object A before it is cleared, and Object A is no longer garbage, then without STW the relationship has to be maintained indefinitely to collect the correct information.

For example, in the fall, the roads are covered with golden leaves. The sanitation workers sweep the streets, but they can never clean them because there is always a constant flow of leaves.

How does garbage collector find GC Roots?

We explained previously that the root reachable algorithm uses GC Roots to find viable objects, and also defined GC Roots. So how does the garbage collector find GC Roots?

First of all, “to ensure the accuracy of the results, GC Roots enumeration should be done in the case of STW”, but as Java applications become larger, it is not possible to check each object individually for GC Root, which would consume a lot of time.

A natural idea would be to swap space for time and at some point write down all the positions on the stack representing references so that when it comes time to actually gc it can be read directly rather than scanned bit by bit. In fact, most mainstream virtual machines do just that, such as HotSpot, which uses a data structure called OopMap to record such information.

OopMap

As we know, a thread means a stack, a stack consists of multiple stack frames, a stack frame corresponds to a method, a method may have multiple safety points. When gc occurs, the program first stops at the nearest safe point and then updates its OopMap, noting which locations on the stack represent references. When enumerating the root node, the OopMap of each stack frame is recursively traversed, and these objects can be found by the memory address of the referenced objects recorded in the stack (GC Roots).

Using OopMap can ** “avoid full stack scan” ** and speed up the enumeration of root nodes. But that’s not the whole point. Another, more fundamental use is to help HotSpot implement precise GC (that is, accurate memory management so that the virtual machine knows exactly what type of data is being stored somewhere in memory).

safer

From a thread perspective, safe points can be understood as “special points” in code execution where the current state of the virtual machine is safe.

For example, “Method calls, loop jumps, exception jumps, and so on are places where safety points are generated.”

You can pause at this point if you need to, for example, during GC, you need to suspend all active threads, but the thread has not reached a safe point at this point, so it should continue to execute and pause when it reaches the next safe point, waiting for GC to end.

So how do you get threads to run to the nearest safe point during garbage collection? There are ** “two ways” ** :

• Preemptive interrupt
• Active interrupt

Preemptive interrupt: At STW, all threads are “completely interrupted”, if the interrupt is not at a safe point, then “reactivated”, “until the safe point is reached”.

Active interrupt: A flag bit is placed at the safe point, and each thread executes to poll for this flag bit and, if true, suspends at the nearest safe point.

But what if some threads are in the sleep state?

The safety area

In order to solve this problem, the concept of safe area is introduced

A security zone is an extension of a security point where “references do not change in a piece of code”. When a thread executes in a safe zone, it first identifies itself as in the safe zone, so that when the JVM initiates a GC during that time, the thread that identifies itself as in the “safe zone” state is left alone, waiting for the root node enumeration or the entire GC process to complete before it can proceed.

Talk about garbage collectors

I’ve talked a lot about garbage collection algorithms, so there are a lot of options when it comes to practice, and garbage collectors are the real practitioners. Here are 10 garbage collectors

Serial

Serial is a “single-threaded” garbage collector that “takes care of the next generation of garbage collection with replication algorithms” and works with the CMS garbage collector.

In STW, there is “only one thread” ** to do garbage collection, so it is expected to be slow.

But it does consume the least extra memory of any garbage collector, yes, simply because of its simplicity.

ParNew

ParNew is a “multi-threaded” garbage collector that “takes care of the next generation of garbage collection using replication algorithms” and can work with the CMS garbage collector.

It is the multithreaded version of Serial, with the main difference being that multiple threads can be used to clean up garbage during STW.

Pararllel Scavenge

The Pararllel Scavenge is the Pararllel Exploiter, a multi-threaded garbage collector that is “responsible for the next generation of garbage recycling using replication algorithms” and works with Serial Old and Parallel Old garbage collectors.

Similar to ParNew, the Parallel collector is used for young generation recycling using replication algorithms. Unlike ParNew, the Parallel Avenge avenge is “designed to achieve a controlled throughput” **.

Throughput = program running time/(program running time +GC time).

If the program runs for 99s, GC takes 1s and throughput =99/ (99+1) =99%. The Parallel Exploiture provides two parameters for precise throughput control, the -xx MaxGCPauseMillis for maximum GC downtime and the -xx GCTimeRatio for direct throughput control.

“Shorter pause time is more suitable for programs that need to interact with users”. Good response speed can improve user experience, while high throughput can efficiently use CPU time to complete the program’s computing tasks as soon as possible, which is mainly suitable for tasks that do not need too much interaction in the background.

Serial Old

Serial Old is a “single-threaded” garbage collector that “takes care of the legacy garbage collection using a mark-collation algorithm,” possibly working with CMS.

In fact, it is an older version of Serial, and the whole link is very different from Serial.

Parallel Old

Parallel Old is the Pararllel Scavenge avenge avenge avenge avenge avenge avenge avenge avenge avenge avenge avenge avenge

Parallel Old is an older version of the Pararllel Scavenge. It is also designed to be throughput first, and PS + Po is a popular combination.

CMS

CMS can be said to be a “generational” garbage collector that supports working with user threads, achieving the “feat” of “concurrent garbage collection”.

• 1. Initial tag

  • The initial tagging is only for tagging objects that are “directly associated with GC Roots”. The overall speed is very fast. To ensure accurate tagging, this part will run in the state of “STW”.

• 2. Concurrent markup

  • Concurrent marking this phase will find ** “all references” relationships directly based on the objects associated with the first step. This part of the user thread “concurrent running” **, although time-consuming, does not have a significant impact.

• 3. Re-label

  • To tag is to solve the second step of concurrent mark as a result of the wrong case, here is simple, for example: concurrent tag is a hasn’t been any object references, the garbage collector to the object the garbage, later in the mark process, a reference by other objects, if not to tag will occur “mistakenly clearing” * * * *.
  • This section is also marked in the case of “STW”.

• 4. Concurrent clearing

  • This step is the final cleanup phase, where the previously “truly garbage” objects are collected, and this is executed concurrently with the user thread.

CMS’s ** “Three disadvantages” ** :

• 1. The execution efficiency of user threads is affected

  • By default, CMS starts the number of collection threads (processor cores + 3) / 4. Since it is cleaned concurrently with user threads, it will inevitably affect the execution speed of user threads, and this effect “increases with the decreasing number of core threads”. So the JVM provides a CMS variant of the “incremental concurrent collector”, which is designed to reduce the amount of time that garbage collection threads spend on resources, so that the collection time is perceived to be longer, which “reduces the efficiency of garbage processing per unit of time” **, also a mitigative solution.

• 2. “Floating garbage”

  • The CMS actually cleans up garbage with the user thread. When the user thread “cleans up” garbage, the user thread creates new garbage. This garbage is called floating garbage and can only be removed until the next garbage collection.

• 3. Fragmented space will be created

  • CMS uses the token-delete algorithm to clean up garbage, but the drawback of this algorithm is that it can produce ** “fragmentation”, which may later “cause large objects to be unallocated” and trigger “use with Serial Old” to deal with the fragmentation problem. Of course, this is also in the case of “STW”. So when Java applications are very large, if the CMS garbage collector is used and fragmentation occurs, it will take a long time for the STW to deal with the fragmentation.

G1

G1(Garbage First) : As the name implies, “Garbage First”, officially rated as a “landmark” achievement in Garbage collector technology.

G1 recycling is no longer aimed at the whole Cenozoic, the whole old, or the whole heap. G1 can collect “any space in heap memory”, and is measured not by age but by “garbage collection”. This fits the name of G1 garbage collector, which is garbage first, which is known as G1’s “Mixed GC” mode.

Of course, I mean ** garbage collection is not designed by age, but G1 is designed by age. Let’s take a look at G1’s heap partition:

The G1 garbage collector divides the heap into ** “same-sized regions” **, with each Region playing a role: H, S, E, and O.

E represents Eden region, S represents Survivor region, and H represents Humongous(G1 is used to allocate ** “region of large objects” **, and for super-large objects that Humongous cannot allocate, they will be allocated in N consecutive Humongous). The remaining dark blue represents the Old region, and the gray represents the free region.

In HotSpot’s implementation, the entire heap is divided into about 2048 regions. Each Region ranges in size from 1 to 32MB, depending on the size of the heap.

New objects are also created when garbage is marked concurrently, and G1 handles these objects like this:

Add Region to “add a space for objects to be allocated in concurrent reclamation”, and design two TAMS(Top at Mark Start) Pointers for this Region. This Region is used to allocate new objects in concurrent reclamation. If objects are added, you only need to move the TAMS pointer. And these ** “new objects are marked alive by default” so that “they don’t interfere with the marking process” **.

However, there is a problem with this approach. It is possible that “garbage collection is slower than new object allocation” **, which can lead to “Full GC” and long STW.

In the design concept of G1, “the smallest reclamation unit is Region”, each reclamation size is N times of Region, so G1 “how to choose which Region to recycle” **?

G1 tracks the value of garbage within each Region, depending on the size of the collection space and the collection time, and then ** “maintains a priority list” ** to collect the most valuable Reigon regions.

Steps performed:

• Initial tag:

  • Mark the objects that GC Roots can “directly associate” with
  • Modifying the value of TAMS to facilitate concurrent collection is the new object assignment
  • It was done during the Minor GC period (” STW “)

• Concurrent flags:

  • Scan the entire object reference graph against the object just associated, and the user thread ** “execute concurrently” **
  • Records the values referenced by SATB(original snapshot) at the time of concurrency

• Final mark:

  • In “STW,” process the small number of SATB(original snapshot) records left over from step 2

• Filter recycling:

  • Maintain the priority list mentioned earlier
  • Reclaim Region based on ** Priority List and User Set Maximum pause time **
  • Copy ** surviving objects ** from the Region to be reclaimed to the Region that does not need to be reclaimed. Then reclaim the Region to be reclaimed
  • This part is executed under “STW” and is multi-threaded

Three color tag

Here we mentioned a concept called “SATB raw snapshot”. There is an extension of SATB, “tricolor tagging algorithm”, which is the algorithm used by garbage collector to mark garbage. Here we briefly describe:

Divide objects into ** “three colors” ** :

• White: Objects that have not been accessed by the GC (white means garbage after being marked by the GC)
• Black silk: Living object
• Gray: Objects accessed by GC, but at least one reference in the object reference chain has not been scanned

We know that it is possible to mismark ** while ** is “concurrent marking”. Here are two examples:

• 1. An object that is initially marked as “alive” but “becomes garbage” during concurrent marking
• 2. An object initially marked as ** “garbage” but “becomes a viable object” ** during concurrent marking

In the first case, the impact is not so great, but it is equivalent to the garbage is not cleaned up, and then the next time to clean up.

The second situation is dangerous, is making the “use of the object is suddenly cleaned up” **, the consequences can be serious.

What is ** the “cause of the second condition” **?

• 1.** “add” one or more new references to “black to white” objects
• 2. Delete the direct or indirect reference from the gray object to the white object.

The problem arises when both conditions ** satisfy.

So to solve this problem, we introduced the solution of ** Incremental Update and ** raw snapshot (SATB) :

Incremental updates break the first condition: ** “record when adding a new reference” ** This reference information, rescan in subsequent STW scans (CMS usage scheme).

The original snapshot breaks the second condition: “record when removing references” by scanning these recorded gray objects as roots in subsequent STW scans (G1 usage scenario).

Nagging at the end

In fact, we only introduce the 7 most commonly used garbage collectors here, because the remaining Shenandoah, ZGC and Epsilon garbage collectors can be separately explained into an article. The author will not add them to this article, and I will write about these garbage collectors separately in the future

I’ll see you next time. I’m going to keep fit