This is the eleventh article in the In-depth JVM series

Article update resume:

20220317: Added a code example from Finalize () resurrection object to complement garbage collection algorithm

The automatic memory management of the Java virtual machine gives the garbage collector the memory that would otherwise be collected manually by the developer. Since it’s an automatic mechanism, we don’t normally touch it directly, but it’s important to understand the issues associated with garbage collection implementation. Let’s start with the basics of garbage collection.

The purpose of garbage collection

The purpose of garbage collection is to reclaim memory occupied by objects no longer used in heap memory, freeing resources.

Garbage collection time

Recovery time: If the Eden area of the new generation is Full, the Minor GC will be triggered. After several times of triggering the New generation GC, the surviving objects will be upgraded to the old age. If the memory required to upgrade to the old age object is larger than the remaining memory of the old age, the Full GC will be triggered. Or less is forced Full GC by the HandlePromotionFailure parameter. Full GC is also triggered when the program calls System.gc().

The contents of garbage collection

Garbage collection focuses on memory in the heap and method area. Garbage collection in the heap is mainly the collection of objects, and garbage collection in the method area is mainly the collection of discarded constants and useless classes.

Recycled content: useless classes in the method area and obsolete constant pools (run-time constant pools), objects judged dead in the heap.

Does garbage collection occur in JVM permanent generations? (How do you tell if a class is useless?)

The relationship between a method area and a persistent generation is much like the relationship between an interface and a class in Java that implements the interface, and a persistent generation is the HotSpot VIRTUAL machine’s way of implementing the method area in the VIRTUAL machine specification. Thus method regions are also known as permanent generations.

Garbage collection for the permanent generation mainly includes unloading of types and recycling of obsolete constant pools (run-time constant pools). A constant can be reclaimed when no object references it. Unloading of types is more complicated. The following three points must be met:

  • All instances of the class have been reclaimed, meaning that there are no instances of the class in the Java heap.
  • The ClassLoader that loaded the class has been reclaimed.
  • The java.lang.Class object corresponding to this Class is not referenced anywhere, and the methods of this Class cannot be accessed anywhere through reflection.

A virtual machine can recycle useless classes that meet the above three conditions. This is only “yes”, not necessarily recycled when they are no longer used.

If a reference to an object is set to NULL, does the garbage collector immediately free the memory occupied by the object?

Memory occupied by objects is not immediately freed. If a reference to an object is set to NULL, it only disconnects the reference to the object in the current thread stack frame. The garbage collector is a thread running in the background and scans the object reference only when the user thread reaches a safe point or safe region. When an object is scanned and not referenced, the object will be marked. In this case, the memory of the object will not be released immediately, because some objects are recoverable (reference is recovered in finalize method). Object memory is cleared only if it is determined that the object cannot recover a reference.

So how do you determine if someone is dead?

How do you determine if a subject is dead

There are two ways to determine whether an object is alive or not. Reference counting and accessibility analysis.

Many textbook algorithms for determining whether an object is alive are as follows: add a reference counter to the object and increment it by one each time it is referenced; When a reference is invalid, the counter value is reduced by one; An object whose counter is zero at any point in time cannot be used again. The above statement is not true, and reference counting alone cannot solve the problem of objects referring to each other in a loop, as shown in the following case:

The result of the above code shows that the memory was reclaimed, which means that the virtual machine did not abandon the reclamation of the two objects because they reference each other, which illustrates that the Java virtual machine does not rely on reference counting algorithms to determine whether objects are alive or not.

Java currently uses the Reachability Analysis algorithm to determine whether objects are alive or not. Through a series of objects called “GC Roots” as the starting point, search down from these nodes. The path taken by the nodes is called the reference chain. If an object is not connected to GC Roots by any reference chain, it is proved that the object is not available.

Even if an object is judged to be unreachable in the reachability analysis algorithm, it is not “necessary to die”. At this time, they are still in the “probation” stage temporarily. In order to truly declare an object dead, at least two marking processes must be experienced:

  1. If an object does not have a chain of references connected to GC Roots after reachability analysis, it will be marked for the first time;
  2. A filter is then made on whether the object needs to execute the Finalize () method. If the object does not override the Finalize () method, or if the Finalize () method has already been called by the virtual machine, then the virtual machine considers both cases “unnecessary to execute”. If the object is judged to be necessary to execute the Finalize () method, and there is still no resurrected object after the execution, the object is considered dead.

Here we use an example to illustrate the object resurrection situation:

public class CanReliveObj {

  public static CanReliveObj obj;

  @Override
  protected void finalize(a) throws Throwable {
    super.finalize();
    System.out.println("CanReliveObj finalize called");
    System.out.println("Obj has been resurrected.");
    obj = this;
  }

  @Override
  public String toString(a) {
    return "CanReliveObj";
  }

  public static void main(String[] args) throws InterruptedException {
    obj = new CanReliveObj();
    System.out.println("First GC");
    obj = null;
    System.gc();
    Thread.sleep(1000);
    if(obj == null){
      System.out.println("Obj to null");
    }else{
      System.out.println("Don't obj to null");
    }
    System.out.println("Second GC");
    obj = null;
    System.gc();
    Thread.sleep(1000);
    if(obj == null){
      System.out.println("Obj to null");
    }else{
      System.out.println("Don't obj to null"); }}}Copy the code

The execution result is as follows:

The first GC CanReliveObj Finalize called obj was resurrectednullThe second GC OBj isnull
Copy the code

As you can see, the obj object is resurrected after the first GC. Although the reference to obj has been cleared in the system, in the Finalize method, the object’s this reference is passed inside the method, and if the reference leaks, the object will be resurrected. Of course, the Finalize method will only be called once, so the obj object cannot be resurrected on the second GC.

In general, GC Roots include (but are not limited to) the following:

  • Objects referenced in the virtual machine stack (the local variable table in the stack frame), such as parameters, local variables, temporary variables, etc. used in the method stack called by each thread.
  • An object referenced by a class static attribute in a method area, such as a Java class reference type static variable.
  • Objects that are constant references in the method area, such as references in the String Constant pool (String Table).
  • Objects referenced by JNI (commonly referred to as Native methods) in the Native method stack.
  • Internal references to the Java virtual machine, such as Class objects corresponding to basic data types, resident exception objects (NullPointExcepiton, OutOfMemoryError), and system Class loaders.
  • All objects held by the synchronized keyword.
  • Jmxbeans that reflect Java virtual machine internals, callbacks registered in JVMTI, local code caches, and so on.

In addition to these fixed COLLECTION of GC Roots, other objects can be added “temporarily” to form a complete collection of GC Roots, depending on the garbage collector selected by the user and the memory region currently reclaimed.

Although the algorithm of accessibility analysis itself is very simple, there are still many other problems to be solved in practice.

For example, in a multithreaded environment, other threads may update references in objects that have already been accessed, resulting in false positives (setting references to null) or false positives (setting references to objects that have not been accessed). False positives do no harm, and the Java virtual machine at most loses some garbage collection opportunities. Missing is more troublesome because the garbage collector may reclaim the memory of objects that are actually still being referenced. Once an object that has been reclaimed is accessed from the original reference, it is likely that the Java virtual machine will crash.

Or how to find GC Roots quickly.

Enumerated the GC Roots

Fixing the nodes that can be used as GC Roots is mainly in global references (such as constant or class static attributes) and execution contexts (such as local variable tables in stack frames). Although the goal is clear, it is not easy to make the lookup process efficient. The size of the method area alone is often hundreds of trillions, and there are so many classes, constants, and so on that it can take a long time to go through all the references that originate there.

Now accessibility analysis algorithm find references of longest chain process can already do concurrent with user threads, but always must be in the root node enumeration in a can ensure the consistency in the snapshot to – here is the meaning of “consistency” during the entire enumeration execution subsystem looks like frozen at some point in time, will not appear in the process of analysis, If the object reference relationship of the root node set is still changing, the accuracy of the analysis result cannot be guaranteed.

Currently HotSpot virtual machines are using exact garbage collection (HotSpot is based on exact memory management, where the vm knows exactly what kind of data is in a particular location in memory), so when the user thread stops, It is not necessary to have a reference location that checks all execution contexts and globally; the virtual machine should have a direct way of knowing where object references are stored.

In HotSpot’s solution, a set of data structures called OopMap are used to do this. Once the class-loading action is complete, HotSpot calculates what type of data is at what offsets within the object and, during just-in-time compilation, records which locations in the stack and registers are references at specific locations. This allows the collector to quickly find GC Roots through OopMap during scanning.

Safer SafePoint

Each JIT-compiled method also records an OopMap at a number of locations, where references are placed on the stack and in registers when an instruction to that method is executed. The GC will then look up these OOPmaps as it scans the stack to know where the references are. These specific locations are mainly in:

1. The end of the loop

2. Before the method returns/after the call instruction of the method is called

3. Possible position of throwing exceptions

This location is known as a safepoint **.

As can be seen, HotSpot uses OopMap data structure as a space for time method, but it does not generate OopMap for each instruction, which will require a lot of extra storage space, resulting in higher space costs.

Safety point selection criteria: whether there are characteristics that make the program run for a long time is the criteria.

The number of safe points should be neither too small to make the GC wait too long, nor too large to overburden the runtime.

Only when a safe point is reached will the currently executing program Stop the world and proceed to GC.

Here comes a new concept called stop-the-world.

Stop-the-world

Stop-the-world, which stops the work of other non-garbage collection threads until garbage collection is complete. This causes garbage collection to be called GC pauses. Stop-the-world is implemented through a safepoint mechanism. When the Java virtual machine receives a stop-the-world request, it waits for all threads to reach a safe point before allowing the thread requesting stop-the-world to work exclusively.

For safe points, another consideration is how to get all threads (not really the ones making JNI calls here) to run to the nearest safe point and then pause when garbage collection occurs.

There are two options: presuspension and Voluntary Suspension,

  • Preemptive interrupts do not require the thread to execute the relevant code to actively cooperate. During GC, all threads are interrupted first, and if it is found that some threads have not reached the safe point, the thread is resumed until it reaches the safe point. Few virtual machine implementations now use preemptive interrupts to suspend threads in response to GC events.
  • The idea of active interrupt is that when the garbage collection needs to interrupt the thread, it does not operate directly on the thread, but simply sets a flag bit. Each thread will take the initiative to poll this flag during the execution process. Once it finds that the interrupt flag is true, it voluntarily interrupts and suspends at the nearest safe point.

For JNI methods in Java threads, they are neither executed by the INTERPRETER in the JVM nor generated by the JIT compiler in the JVM, so OopMap information is missing. So how does GC maintain accuracy when it comes to stack frames like this?

HotSpot’s solution is that all references passing through the JNI call boundary (parameters passed to the JNI method by calling it, return values returned from the JNI method) must be wrapped in a “handle.” JNI must also wrap Pointers with handles when it needs to call Java apis. In this implementation, the “object” written in the JNI method is not actually a pointer to the object directly, but rather points to a handle through which the object can be accessed indirectly. There is no need to scan the stack frame of a JNI method when it is scanned — just scan the handle table to get all the objects in the GC heap that are accessible from the JNI method.

However, this means that the wrapper/unwrapper overhead of calling JNI methods is one of the reasons that JNI methods are slow to call.

For example, when a Java program executes native code through JNI, if the code does not access Java objects, call Java methods, or return to the original Java methods, the Java virtual machine stack does not change, which means that the native code can act as the same safe point. As long as you don’t leave this safe point, the Java virtual machine can continue to run this native code while garbage is collected.

The safe point mechanism ensures that the program execution will not take too long to reach a safe point that can be entered into the garbage collection process. But what about when the program “doesn’t execute”? So-called program execution is not allocated processor time, typical scenario is user threads in the Sleep state or Blocked state, the threads can’t respond to the virtual machine interrupt request, can’t go to a safe place to interrupt a hang oneself, the virtual machine also obviously could not continue waiting thread is activated again allocate processor time. In this case, the Safe Region must be introduced to solve the problem.

Safety zone SafeRegion

The Safepoint mechanism guarantees that a program will run into a Safepoint ready for GC for a short period of time, but there are some exceptions, such as JNI methods, sleep, blocks, and so on, where the JVM has no control over execution and cannot respond to GC events.

A safe zone is one that ensures that no reference relationship changes within a code fragment, so it is safe to start garbage collection anywhere in the zone. We can also think of the safety zone as a point of safety that has been stretched.

When a user thread executes code in SafeRegion, it first identifies itself as having entered SafeRegion, during which time the virtual machine does not have to deal with threads that have declared themselves to be in a safe zone to initiate garbage collection. When the thread wants to leave SafeRegion, it checks to see if the virtual machine has completed the root enumeration (or any other part of the garbage collection process that requires suspending the user thread). If so, the thread assumes that nothing happened and continues. Otherwise it must wait until it receives a signal that it can leave the safe area.

Concurrency accessibility analysis

By default, the JVM uses a reachability analysis algorithm to determine whether an object is dead. Reachability analysis theoretically requires that the entire process be based on a consistent snapshot, which means that the user thread must be frozen throughout. Although GC Roots are a small fraction of Java heap objects, and even if GC Roots can be found quickly with OopMap, the pause times they bring are very short and relatively fixed, which can be understood as not increasing with the number of objects in the heap.

However, continuing through the object graph from GC Roots, the pause time for this step must be directly proportional to the size of the Java heap: the larger the heap, the more objects are stored, the more complex the object graph structure, and the longer the pause time for marking more objects.

The “mark” phase is the phase that exists for all garbage collectors using the reachability analysis algorithm. If you can cut down the downtime in this part of the “tagging” process, the benefits will be systemic.

So what problem does concurrent markup solve?

** is to eliminate the pause time in this section. That is to have the garbage collector and the user thread running at the same time, working concurrently. ** is what we call the phase of concurrent markup.

Before we introduce concurrent tags, we need to introduce a new concept, “tricolor tags.”

What is “tricolor”? Understanding the Java Virtual Machine (3rd Edition) describes it as follows:

  • White: indicates that the object has not been accessed by the garbage collector. Obviously, at the beginning of the reachability analysis, all objects are white. If at the end of the analysis, all objects are still white, that is, they are unreachable.
  • Black: Indicates that the object has been accessed by the garbage collector and that all references to the object have been scanned. The black object indicates that it has been scanned, and it is safe and survivable. If there is another object reference pointing 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 the garbage collector, but at least one reference to the object has not been scanned.

As shown below:

As you can see, the gray object is an intermediate state between the black object and the white object. When the marking process is complete, there are only black and white objects, and the white objects are the ones that need to be reclaimed.

If only the garbage collection thread is working during the scan of the reachability analysis, there should be no problem.

But what about the garbage collector running at the same time as the user thread?

The garbage collector colors the object graph while the user thread is modifying the reference relationship. When the reference relationship changes, the object graph changes, which can have two consequences:

  • One is to mismark dead objects as alive, which is not a good thing, but is actually tolerable, creating a bit of floating garbage that escapes the current collection and can be cleaned up next time.

  • One is to falsely mark a previously alive object as dead, which is so serious that a program still needs to use it

    The object was reclaimed, and the program is bound to fail because of it.

In the end, we learned that in addition to floating garbage, concurrent markup also had the problem of “object disappearance.”

Floating garbage has little impact and can be cleared next time. The key is how to solve the problem of “object disappearance”. Let’s use pictures to illustrate this problem.

Let’s take a look at the normal tagging process:

The first is the initial state, very simple, only GC Roots are black. At the same time, note that the arrow direction in the following picture represents directed direction. For example, there are two reference chains in the following picture: root node ->4->5->6 and root node ->4->5->7. Note that object 2 is not in the reference chain of the root node.

If it is a normal scan, the final image is displayed as follows:

Because gray objects are always between black and white, only white and black are left when the scan is complete. Black objects are alive objects, and white objects are dead objects that can be reclaimed.

So to demonstrate the case of “object disappearance” :

There is a reference between object 5 and object 7. If, during the scan, the user thread removes the reference between object 5 and object 7 (denoted by a dotted line) and associates object 4 with object 7 instead. Since the scan can’t go back, only down, object 7 will be forgotten.

The final result is shown as follows:

Compared to the previously analyzed object graph at the end of a normal scan, it can be seen intuitively that object 7 is treated as garbage collection. This is where the object disappears.

How do you solve the object disappearance problem?

There’s a big guy named Wilson who, in 1994, theoretically proved that the problem of “object disappearance” occurs if and only if the following two conditions are met: an object that should be black is mislabeled as white:

  • Condition 1: The assignor inserts one or more new references from black objects to white objects.
  • Condition 2: The assignment removes all direct or indirect references from a gray object to the white object.

Note: The white object in condition 2 refers to the white object in condition 1.

Therefore, we have reason to believe that condition 1 and condition 2 are sequential, that is, the assignment must insert one or more new references from the black object to the white object, and then the assignment must delete all direct or indirect references from the gray object to the white object. In this case, the object disappears.

There are two solutions: Incremental Update and Snapshot At The Beginning (SATB).

In the HotSpot virtual machine, CMS does concurrent marking based on incremental updates, whereas G1 uses raw snapshots.

What is incremental update?

Incremental updates to destruction is the first condition (assignment by inserting one or more new reference object from black to white objects, when the black object insert a new white object references, with the newly inserted record reference, such as concurrent scanning is done, then these records of the dark object references as the root, to scan again.

A black object becomes a gray object once a reference to a white object is inserted.

What is a raw snapshot?

Original snapshot is to destroy the second condition (assignment deleted from the gray object to all this white object reference) directly or indirectly, when grey object to remove points to the white object reference relations, will delete the record reference, at the end of the concurrent scan then these records of grey objects in the reference relationship as the root, to scan again.

This can be simplified as: whether the reference relationship is deleted or not, the search will be based on the snapshot of the object graph at the moment when the scan is started.

Note that no matter the insertion or deletion of reference records in the above introduction, the recording operation of the virtual machine is implemented through the write barrier. More on write barriers later.

Incremental updates use a post-write Barrier to record all new references.

The original snapshot uses a pre-write Barrier to record old references to all reference relationships that are about to be deleted.

Garbage collection algorithm

Mark-clear algorithm

Algorithms are divided into “mark” and “clear” phases: in the mark phase, all reachable objects starting from the root node are marked through the root node first. Therefore, unmarked objects are unreferenced junk objects. Then in the sweep phase, all unmarked objects are cleared. It is the most basic collection algorithm, the subsequent algorithms are to improve its shortcomings. There are two obvious problems with this garbage collection algorithm:

  • Efficiency. The reclaimed space is discontinuous. In the process of heap space allocation of objects, especially the memory allocation of large objects, the work efficiency of discontinuous memory space is lower than that of continuous space.
  • Space debris (a large number of discontinuous debris will be generated after the marker is cleared)

Mark-copy algorithm

To solve the efficiency problem, “copy” collection algorithms emerged. It divides memory into two equally sized pieces and uses one piece at a time. When this area of memory is used up, the surviving objects are copied to another area, and then the used space is cleaned up again. In this way, half of the memory range is reclaimed each time.

If most objects in memory are alive, this algorithm incurs a large overhead of inter-memory replication, but if most objects are recyclable, the replication algorithm needs to copy a relatively small number of live objects. While this algorithm does not cause space debris problems, it comes at the cost of cutting system memory in half.

The garbage collector introduced later uses the idea of replication algorithm, and the new generation is divided into Eden space, from survivor, and to survivor. The FROM and to Spaces are regarded as two space blocks of the same size, equal status, and roles can be swapped for replication.

Mark-collation algorithm

The efficiency of mark-copy algorithm will decrease when the survival rate of the object is high. More importantly, if you do not want to waste 50% of the space, you need to have extra space for allocation guarantee, in the extreme case that all objects in the memory used are 100% alive, so in the old days, this algorithm generally cannot be used directly.

According to the characteristics of the old era, a mark-finishing algorithm is proposed, and some optimization is made on the basis of the mark-clearing algorithm. Like the mark-clean algorithm, the mark-clean algorithm marks all reachable objects first, starting at the root node, but then, instead of directly retrieving the recyclable objects, it moves all surviving objects to one end and then directly cleans up memory beyond the end boundary. This method not only avoids fragmentation, but also does not require two pieces of the same memory space, so it is cost-effective.

The final effect of the mark-clean algorithm is the same as that of memory defragmentation after the execution of the mark-clean algorithm.

Generational algorithm

The current virtual machine garbage collection adopts generational collection algorithm, which has no new idea, but divides the memory into several blocks according to the different object life cycle. The Java heap is generally divided into the new generation and the old generation, so that we can choose the appropriate garbage collection algorithm based on the characteristics of each generation.

For example, in the new generation, a large number of objects die in each collection, so a mark-copy algorithm can be used to complete each garbage collection at a small cost of copying objects. Older objects have a higher chance of survival, and there is no extra space for allocation guarantees, so we must choose the “mark-clean” or “mark-clean” algorithm for garbage collection.

conclusion

The basics of garbage collection are introduced in detail above, including:

  • Why recycle?

  • When is garbage collection?

  • Recycle what?

  • Reclaim dead objects, so how do you determine that an object is dead?

    • Reachability analysis algorithm, problems and solutions in concurrent environment are introduced.
    • This section describes security points and zones
    • Stop-the-world

  • Comb through existing garbage collection algorithms

Stay tuned for more on the garbage collector, JVM memory allocation, and more in the next lecture.

reference

Interviewer: You say you are familiar with the JVM? So you talk about concurrent accessibility analysis

In-depth Understanding of the Java Virtual Machine

JVM- How to determine whether a piece of data is real data or a reference to an object

Find the pointer/reference on the stack