This is the fourth day of my participation in the gengwen Challenge, the details of the activity view: Gengwen Challenge if ❤️ my article is helpful, welcome to like, follow. This is the biggest encouragement for me to continue my technical creation. More previous posts on my personal blog

Golang Garbage Recycling (GC) principle

What is Garbage Collection (GC)

While some of the more common garbage collection algorithms are mark-sweep and Reference Count, Golang uses mark-sweep. Three – color marking and writing barrier are used to improve the efficiency.

The tag Sweep collector is a tracking garbage collector whose workflow is roughly divided into two stages: Mark and Sweep:

  • Mark phase – fromThe root object (root)Start searching and markingThe heap 中 All living objects
  • Cleanup phase – RecycleThe heap is not markedGarbage object and willThe reclaimed memory is added to the free linked list

What is tricolor notation

Three-color marking algorithm divides the program into three categories: white, black and gray.

  • White: uncertain object
  • Gray: The surviving object and its children are to be processed
  • Black: The surviving object

Tricolor marking process

  1. Add all objects to white collection (STW).

  1. willThe root objectMarked asgrayjoinGrey collection

  1. Garbage collectorGrey collectionFetch objects one by one marked asblack. And it’sPointing to the objectMarked asgrayAlso joinGrey collection

  1. repeatStep 3 Process, until the grey set is empty

  1. After the preceding four steps are complete: YesClean up white objects; Keep black objects (Root reachable object) (STW)

Problems of tricolor method in concurrency

Because the tricolor notation has a white state to store the uncertain object. Combined with subsequent marking phases of concurrent execution, it is possible to create omissions: for example, objects that were previously marked black may now be unreachable.

However, there are still problems with concurrent execution: objects and Pointers are changed during GC.

For example: A (black) -> B (gray) -> C (white) -> D (white) Normally D objects are not recycled when added to the black collection.

However, in the concurrent case: A obtains A reference to D, and C’s reference to D is deleted by the user. This is GC running concurrently, and D has no chance of being marked black (A has already been processed, it will not be processed this time).

A (black) -> B (gray) -> C (white) ↓ D (white)Copy the code

This is clearly not allowed.

What is a write barrier

To solve this problem, Golang’s garbage collector uses a Write Barrier technique:

When an object is added or updated, color the object gray.

Write barriers do one thing: modify the original write logic and color the object gray as it is added and updated. Write barriers ensure that the tricolor notation works correctly in concurrent cases.

This way: even if the GC executes concurrently with the user program. Object references change and the garbage collector handles them correctly.

The objects marked gray by the write barrier will be sorted by the above three-color marking process starting with white in the new GC process

The complete GC is divided into four phases:

1) Mark Setup (STW), open Write Barrier 2) Marking (concurrent) 3) Mark Termination (STW), close the Write Barrier. 4) Sweeping (Sweeping, Sweeping)

reference

Fullstack garbage collector tri-color markup method