Once, I thought it was enough to read these things at ordinary times, belonging to the kind of energy spent half a day to understand, and then two days on the natural forget things.
As a result, this is what ah, what is card table, what is the three-color marking method, these ghost questions are interviewed to ask, the volume is finished.
Reference counting & reachability analysis
To do garbage collection GC, we first have to decide how do we know if an object is alive? Generally speaking, there are two ways.
Reference counting, add a counter to an object, and whenever there is a reference to it, the counter is +1, and when the reference is invalidated, it is -1, so an object with a counter value of 0 is a reclaimable object, but there is one problem that can’t be solved with circular references.
For today’s virtual machines, the main algorithm used is the reachability analysis algorithm.
First, define the collection of GC ROOTS and search down through GC ROOTS. The path of the search process is called reference chain. If an object does not have any reference chain to GC ROOTS, it is unreachable and can be reclaimed.
The unreachable object needs to be marked twice. For the first time, it will be marked for the first time, if finalize() method needs to be executed, then the object will be put into the queue to wait for Finalize () to be executed. If it is successfully associated with other objects on the reference chain in Finalize (), Will be removed from the collection of recyclable objects. (But using finalize() method is not recommended.)
Generational collection
Now that we have the basis of how to determine the survival of objects, the next question is how to do garbage collection GC. Commercial virtual machines today are basically generational collection implementations, which are based on two assumptions:
- The vast majority of the objects are ephemeral
- The more collections an object survives, the less likely it is to die
From these two hypotheses came the young generation and the old generation that we see today.
Because it’s generational, GC is also generational.
The young generation is used to store objects that die quickly. The young generation GC is called MinorGC. Every time the young generation runs out of memory, we trigger MinorGC.
The FullGC is called OldGC. Many people now call it FullGC, but this is not accurate. FullGC should refer to both young and OldGC.
According to the reachability analysis algorithm we used above to determine the survival of objects, if we do MinorGC, will any objects be referenced by the old age? Will there be objects referenced by the young generation in OldGC?
If so, we would have to do not only GC Roots, but also go back to the old age when doing MinorGC, which would be a performance problem.
So here comes another hypothesis…
Intergenerational citations are in the minority compared to contemporaneous citations.
This has led to a new solution. Instead of scanning the entire old age, we simply create a data structure for the young generation, called A Remembered Set. It divides the old age into N areas and identifies which areas will have cross-generational references.
When doing MinorGC in the future, just add GC Roots to these memory areas that contain cross-generational references and scan with them.
Card table
Say that finish these, just arrived the first topic: card table.
A card table is actually an implementation of a memory set, and if a memory set is an interface, then a card table is its implementation class.
For the HotSpot virtual machine, the card table is implemented as a byte array.
CARD_TABLE [this address >> 9] = 0;This code represents the logic of the card table markup. In fact, the card table maps blocks of memory addresses called card pages. The code shows that the size of each card page is 2^9=512 bytes.
If converted to hexadecimal, element 0, 1 of the array maps to the card pages of memory addresses 0x0000 ~ 0x01FF(0-511), 0x0200 ~ 0x03FF(512-1023).
As long as there is one or more cross-generational object Pointers to an object in a card page, change the card table array element at that position to 1, indicating that the position is dirty, or 0 if it is not.
In GC, simply add the card page object pointer with the value of 1 to GC Roots for scanning.
With card tables, we don’t need to scan the entire age when MinorGC is happening, and performance is greatly improved.
The problem with the card table
Write barriers
The element of the card table array is changed to a 1, or dirty state, by a write barrier for HotSpot, which is essentially an update when the reference is assigned to the object of the current generation, in a manner similar to the AOP aspect idea.
Void oop_field_store(oop* field, oop new_value) {// reference field assignment *field = new_value; Post_write_barrier (field, new_value); }The problem with write barriers is the additional performance overhead, but that’s not a big problem and is acceptable.
False sharing
Another problem I’ve written about in my previous post is fake sharing (check out my previous post if you don’t know what fake sharing is).
A cache row is usually 64 bytes, and a card table element is 1 byte. The memory size of the card page is 64*512=32KB.
If multiple threads just update objects that fall within this 32KB range, then performance will be affected.
How to solve the pseudo sharing problem?
-xx :+UseCondCardMark is added after JDK7. It indicates whether the card table update is enabled or not, and is marked dirty only if it is not marked.
if (CARD_TABLE [this address >> 9] ! = 0) CARD_TABLE [this address >> 9] = 0;Three-color labeling
Card tables address the performance issues of cross-generational collection and root node enumeration. With these measures, the STW pauses caused by the process of enumerating root nodes are manageable.
Another problem is how to mark these objects efficiently starting with GC Roots, which is the role of three-color labeling. Because the more objects there are in the heap, the longer the pause time of the tag will obviously be.
Using the now-familiar CMS or G1 as an example, the first two steps of GC are as follows:
- Initial tag: Tag objects that GC ROOT can associate with. This step requires STW, but the pause is short.
- Concurrent marking: The process of traversing the entire object graph from the directly associated object of GCRoots takes a long time, but it can now be executed concurrently with the user thread. This efficiency problem is the concern of the three-color marking.
In the trichromatic notation, objects traversed starting with GC Roots are marked with the following three colors:
- White, at the beginning of the traversal, all the objects are white
- Grey, has been scanned by the garbage collector, but at least one reference has not been scanned
- Black, is scanned by the garbage collector, and all references to this object are scanned, and is a safe living object
The process of labeling is as follows: first, make sure that all objects are white when traversing from GC Roots.
Then the A\G object is scanned and becomes gray, and then all references to the A\G object are scanned and the A\G object becomes black.
B\C objects start to be scanned and become gray, and their references become black as they are scanned.
Then D will go from gray to black as well.
The last remaining E\F node is the object that can be reclaimed.
The problem of three-color marking
Although the trichromatic method is efficient, it also raises other problems.
First of all, we said that the process of concurrent marking is not STW, your mother is cleaning, and you have been throwing garbage, it does not matter, the big deal is that there is still some garbage not clean.
For the three-color mark, the object that should be cleaned is marked as alive, so this GC cannot clean this object, which is called floating garbage, the solution is to wait for the next GC to clean up, this time is not clean, wait for your mother to clean up the next time.
On the other hand, if you mark a living object as needing to be cleaned up, it’s a bit of a problem, and your program is in trouble.
Therefore, the study shows that only when both conditions are met can the problem of object disappearance occur:
- One or more references to black to white objects were inserted
- Removed all references to gray to white objects
Then, there are two solutions to this problem: incremental update and raw snapshot, where CMS uses incremental update and G1 uses raw snapshot if the corresponding garbage collector is used.
So the idea is that if I want to satisfy both, then I only have to break one of the conditions and that’s fine, right?
So, look at A scene in our example above, suppose A scan, just become gray, C C – > D references to delete right now, at the same time A – > D added reference (at the same time satisfy the two conditions), it was according to order the following D should become black (black objects should not be clean up), but because of the C – > D have no reference, A has become A black object, it will not be rescan, so even if A->D reference is added, D will only become A white object and will be ruthlessly cleaned up.
The incremental update solution is that he records the newly inserted references and rescan them with the black object as the root after the scan. Doesn’t that look like an incremental update? Sweep the newly inserted record again!
The original snapshot breaks the second condition by recording the reference to be deleted and rescan it with the gray object as the root after the scan. So it’s like a snapshot, whether you delete it or not, you’ll end up doing it all over again.