First ：

Blogger is a handsome boy, You can call me Mountain fish King
Personal home page ： An Yuge's personal homepage
If it helps you, I hope to support the blogger for three consecutive times

go The garbage collection of

notes ：Go The garbage collection used in the language uses the tag cleaning algorithm . Garbage collection will stoptheworld. But in the Go Language 1.3 In the version , It realizes accurate garbage collection and parallel garbage collection , Greatly improve the speed of garbage collection , During garbage collection, the system will not get stuck for a long time .

1. Mark sweep algorithm

（1） Tag cleaning algorithm is a very basic garbage collection algorithm , The algorithm has a marked initial root Area , And a controlled reactor area .root Area is mainly the stack and global data area when the program runs to the current time . In the controlled reactor area , A lot of data is not needed by the program in the future , This kind of data can be recycled as garbage .

（2） Determine whether an object is garbage , Just look from root Whether the object of the region has a direct or indirect reference to this object . If no object references it , It means that it is not used , Therefore, it can be safely recycled as garbage .

（3） The tag sweeping algorithm is divided into two stages , They are marking stage and cleaning stage .
Marking stage , from root Regional departure , Scan all root The object directly or indirectly referenced by the object of the region , Mark all these pairs ;
Cleaning stage , Scan the entire heap , Recycle all unmarked objects .

2. Bitmap tags and memory layout

Since the garbage collection algorithm requires objects to be marked with garbage collection , Obviously, there needs to be a marker bit . The general practice is to add a tag field to the object structure , Some optimizations will use the low order of the object pointer to mark , It's just some strange skills .Go Didn't do it , Its object and C The structure object of is exactly the same , Non intrusive marker bits are used , Let's see how it works .

The heap area corresponds to a marked bitmap area , Every word in the heap （ No byte, It is word） There will be corresponding marker bits in the marker bit area . Every machine word （32 Bit or 64 position ） Will be corresponding 4 Flag bit of bit . therefore 64 The byte corresponding to each marked bitmap in the bit system 16 Bytes in the heap .

Although it is a heap byte corresponding 4 Bit marker bit , But the memory layout of the marked bitmap area is not by 4 One by one , It is 16 Heap bytes are a group , Pack and store their tag bit information . Each group 64 The bit marked bitmap includes... From top to bottom ：
16 Special bit of bit 、 Marker bit ;
16 Garbage collection flag bit of bit ;
16 No pointer to bit / The marker bit of the block boundary ;
16 Allocated flag bits of bit .

This design makes it easy to traverse the corresponding bits of a type .

As mentioned earlier, the heap area and the marked bitmap area of the heap address are stored separately , In fact, they are based on mheap.arena_start The address is boundary , Up is the heap address space actually used , Down is the marked bitmap area . With 64 For example, bit system , The formula for calculating the tag bit of an address in the heap is as follows ：

The offset = Address - mheap.arena_start
Tag bit address = mheap.arena_start - The offset /16 - 1
displacement = The offset % 16
Marker bit = * Tag bit address >> displacement
Basic marking process

3. The process of marking

1. From the simplest point of view , Basic marking process , There is an implementation without any optimized markup , Corresponding to function debug_scanblock.
debug_scanblock Functions are implemented recursively , Single threaded , Simpler and slower scanblock edition . The parameters received by this function are a pointer indicating the address to be scanned , And the number of bytes .

2. First, send the incoming address , Align by machine byte size . Then each address of the area to be scanned ：
Find what it belongs to MSpan, Convert the address to MSpan The address of the object in .
According to the address of the object , Find the tag bit in the corresponding tag bitmap .

3. Judge the marker bit , If it is unassigned, skip . Otherwise, add a special bit mark （debug_scanblock With special bit code mark position ） Finish marking .

4. Judge whether the pointer free mark bit is marked in the mark bit , without , Call recursively debug_scanblock.
This recursive version of the marking algorithm is still easy to understand . The details involved have been mentioned in the previous section , For example, any given address , Find its tag bit information . Obviously, only one pointer free bit is used here , There is no precise garbage collection .

At the end

Last ：
For students who just started , It will sound a little confused , But it doesn't matter , You may as well go Cattle guest Take a look for go Freshmen will certainly be of great help . Don't worry , Don't panic , There is moonlight under the moon , Follow the moonlight to find the moon , come quick Cattle guest Well ！