Zhuanlan.zhihu.com/p/77943973 can reference documentation

Mark & Sweep

Modern high-level programming languages manage memory in two ways: automatic and manual. Programming languages such as C and C++ use manual memory management. Engineers need to actively apply for or release memory when writing code. Languages such as PHP, Java, and Go use automatic memory management systems with memory allocators and garbage collectors to allocate and reclaim memory on their behalf, often referred to as GC. Mainstream garbage collection algorithms:

  • Reference counting
  • Tracking garbage collection

The three-color tagging that Go now uses is one of the traceable garbage collection algorithms.

Basically, layer by layer, what’s not tracked is garbage

STW

  • Stop the world, some phases of the GC require all mutators to be stopped to determine the current reference relationship.
  • This is where a lot of people worry about GC, and this is where the optimization of the GC algorithm comes in.

Root

  • The root object is an object that the Mutator can access directly without going through any other object.
    • Such as global objects, data in stack objects, etc.
  • Through the Root object. We can track down other surviving objects.

It is also called “Mark” and “Sweep”

Tracking algorithm

This algorithm is implemented in strict accordance with the idea of tracking algorithm:

  • Stop the World pauses the program
  • Mark: All reachable objects are found and marked by Root and objects directly and indirectly accessed by Root.
  • Sweep: Iterates over the heap objects, and flags the flagged objects. All untagged objects are added to freelist, which can be used for redistribution.
  • Start the Wrold recovery program

The biggest problem with this algorithm is that the whole program needs to be completely paused during GC execution. The naive Mark Sweep is the whole STW, and the allocation speed is slow and the memory fragmentation rate is high.

The marking process requires STW because the object reference relationship can affect the correctness of the marking result if it is modified during the marking phase.

Concurrent GC has two meanings:

  • Each mark or sweep itself is executed concurrently by multiple threads (coroutines).
  • Mutator (application) and Collector (garbage collector) run simultaneously (background)

The concurrent layer is easier to implement, as STW is performed as a whole during GC, so the object reference relationship does not change, and by chunking the Mark or sweep task, multiple threads (coroutines) ConnCurrent can execute the mark or sweep task.

In the case of the backgroud layer, which means mutator and Mark sweep run simultaneously, it’s more complicated.

  • Prior to version 1.3, the mark-sweep approach was used, requiring STW throughout the process.
  • Version 1.3 separated the marking and cleaning operations, marking procedure STW, and cleaning process concurrently.

Version 1.3

Backgroup sweep is relatively easy to implement, because after Mark, the reference relation is all determined, which objects are alive and which are to be swept are known, and the objects of sweep are no longer referenced (green). These objects are no longer assigned until the sweep ends, so the sweep and mutator run together. These objects, whether globally or on the stack, can be safely cleaned up.

Version 1.5

Version 1.5 uses tricolor marking during marking. Both marking and sweeping are performed concurrently, but the marking phase requires some time before and after the STW to prepare the GC and re-scan the stack.

Why does it take a while?

Tri-color Mark & Sweep

Three-color marking is an improvement on the mark clearing method, which requires a long time STW during the whole execution. Go is changed to three-color marking method from version 1.5. Initially, all memory is marked as white, and then roots are added to the queue to be scanned (when entering the queue, roots are regarded as turning gray). A concurrent Goroutine is then used to scan the pointer in the queue. If the pointer references other Pointers, the referenced pointer is also queued and the scanned object is treated as black.

White objects: Potential garbage whose memory may be reclaimed by the garbage collector. Black objects: Active objects, including objects that do not have any references to external Pointers and objects reachable from the root, whose children are not scanned by the garbage collector. Gray objects: Objects that are active because there are external Pointers to white objects and the garbage collector scans their children.

Tri-color Marking

The garbage collector starts at root and recurses through the memory space following Pointers. Objects assigned to the span of noscan are not scanned. However, this process is not done by the same Goroutine; each pointer is queued in the work pool and then the backbench coroutine that is seen first and marked as a work coroutine is queued out of the pool, scans the object, and queues the pointer found in it.

Tri-color Coloring

Dyeing process:

  • Step1 at first all objects are considered white
  • Step2 the root nodes (stacks, heap, global variables) are colored gray
  • Once the main process is complete, the GC will:
  • Step3 select a gray object and mark it as black
  • Step4 iterate over all Pointers to this object and gray out all objects referenced by it
  • Eventually all objects need to be dyed.

step1

step2

step3

step4

After marking

Black objects are the objects in memory that are being used, and white objects are the objects to be collected. Because the instance of struct2 is created in an anonymous function and cannot be accessed from the stack, it remains white and can be cleared.

The internal realization principle of color:

Each span has a bitmap property called gcmarkBits, which tracks the scan and sets the corresponding bit to 1.

Write Barrier

Version 1.5 uses tricolor marking during marking. There are four main stages in the collection process, in which both marking and cleaning are performed concurrently, but before and after the marking stage, STW needs a certain amount of time to do GC preparation and stack re-scan.

To use concurrent garbage collection, where multiple mutators and marks are executed concurrently, we need to achieve either of two tri-color invariants to ensure correctness in both concurrent and incremental markup algorithms:

  • Strong trichromatic invariance: black objects do not point to white objects, only to gray objects or black objects.
  • Weak trichromatic invariance: The white object to which the black object points must contain a reachable path from the gray object through multiple white objects.

It can be seen that a white object referenced by a black object is doomed to fail to ensure its own survival through the black object. Meanwhile, if all the reachable relations between gray objects that can reach it are destroyed, then the white object is bound to be regarded as garbage removal. Therefore, when the above two conditions are met at the same time, the problem of object loss will occur. If the white object refers to other objects downstream, and this path is the only path to the downstream object, then they are also dead.

In order to prevent the occurrence of this phenomenon, the easiest way is to STW, direct ban on other user program about the relationship between object references, but STW process has obvious waste of resources, has a great influence on all of the user program, how to ensure the object without loss of reasonable as far as possible, improve the efficiency of GC, How about reducing STW time?

Stop The World