This is a reading note for The algorithm and Implementation of Garbage Recycling

What is a Mark Sweep GC?

GC mark-clearing algorithm consists of a marking phase and a clearing phase. In the mark phase, all live objects are marked, and in the clear phase, unmarked objects, that is, inactive objects, are reclaimed.

Noun explanation:

In the GC world, an object is a collection of data that is utilized by an application. Is the basic unit of GC. Generally, it consists of headers and fields.

Live objects: Objects that can be referenced by a reference program are called live objects. (Objects that can be directly or indirectly extracted from the global variable space)

Inactive objects: Objects that cannot be referenced by a program are called inactive objects. (This is the target of the purge.)

The pseudo-code for the mark-clear algorithm is shown below:

func mark_sweep(a){
    mark_phase()   // Mark the phase
    sweep_phase()  // Clear phase
} 
Copy the code

Mark phase

The marking phase is the process of traversing and marking objects.

The pseudo-code of marking stage is as follows:

func mark_phase(a){
    for (r : $roots)  // In the marking phase, all active objects are marked
        mark(*r)
}

func mark(a){
    if (obj.mark == False)
        obj.mark = True            // Mark the active object found first
        for (child: children(obj)) // Then recursively mark the object that can be accessed through the pointer array
            mark(*child)
}
Copy the code

Here $root is the starting point of the pointer object, through which you can traverse all live objects.

The following figure shows the state of the heap in memory before and after tagging

Sweep phase

During the cleanup phase, the Collector walks through the heap to reclaim unmarked objects (garbage) for reuse.

The pseudo-code of the sweep_phase() function is implemented as follows:

func sweep_phase(a){
    sweeping = $heap_start            // First assign the first address of the heap to the jie
    while(sweeping < $head_end){
        if(sweeping.mark == TRUE)
            // Set it to FALSE if it is a marked state, and TRUE if it is a live object during the marked phase
            sweeping.mark == FALSE    
        else:
            sweeping.next = $free_list   // Concatenate the inactive objects to the $free_list header position
            $free_list = sweeping
        sweeping += sweeping.size
    }     
}
Copy the code

The size field refers to the field that stores the size of an object, defined in the object header.

The next field is only used when generating free lists and extracting blocks from free lists.

A chunk is a space prepared in advance for the use of objects.

The block generation path of the block in memory is: block -> active object -> garbage -> block ->…

During the cleanup phase we recycle the inactive. A reclaimed object is a block of objects connected to a one-way linked list called a free list. And then when you reallocate space you just walk through the free list and you find the chunks.

The following is the state of the heap after the cleanup phase:

distribution

The purpose of recycling garbage is to redistribute it

When a program requests a chunk, how can it be allocated a chunk of the appropriate size?

Assign pseudocode as follows:

func new_obj(size){  // size is the desired block size
    chunk = pickup_chunk(size, $free_list)  // Traverse $free_list for blocks greater than or equal to size
    if(chunk ! = NULL)return chunk
    else
        allocation_fail()   // If no partition size is found, allocation failed
}
Copy the code

The pickup_chunk() function returns not only the size of the chunk, but also the larger chunk(which is then split into the size chunk and the remaining chunk after removing size, and returned to the free list).

There are three types of allocation strategies: first-fit, best-fit, and worst-fit

First-fit: Returns immediately if a block size is greater than or equal to size is found

Best-fit: Find the same size and return it

‘ ‘worst-fit’ : find the largest chunk and divide it into size and remaining size (this method tends to produce lots of smaller chunks

merge

According to different allocation strategies, there will be a large number of small blocks in the allocation process. If the blocks are continuous, we can merge the small blocks into a large block. The merger is completed in the clearance stage, and the clearance code containing the merger strategy is as follows:

func sweep_phase(a){
    sweeping = $heap_start            // First assign the first address of the heap to the jie
    while(sweeping < $head_end){
        if(sweeping.mark == TRUE)
            // Set it to FALSE if it is a marked state, and TRUE if it is a live object during the marked phase
            sweeping.mark == FALSE    
        else:
            if(sweeping == $free_list + $free_list.size)  // The heap address is exactly the same size as the free list
                $free_list.size += sweeping.size
            else
                sweeping.next = $free_list   // Concatenate the inactive objects to the $free_list header position
                $free_list = sweeping
        sweeping += sweeping.size
    }     
}
Copy the code

$heap_end = $heap_start + HEAP_SIZE

== $free_list + $free_list.size == the addresses of the heaps that need to be cleared are adjacent to the idle links

Optimal/lack of points

advantages

  • Implement a simple
  • withConservative GC algorithmCompatible with

disadvantages

  • Fragmentation is severe (as can be seen from the allocation algorithm described above, it is easy to produce a large number of small chunks
  • Slow allocation (since free blocks are realized by linked lists, the blocks may not be continuous, and each allocation requires traversing the free list, or in extreme cases, traversing the entire list.
  • withCopy-on-write technologyAre not compatible

Copy-on-write is a method of memory optimization used by many UNIX operating systems. For example, in Linux, when the fork() function is used to copy processes, most of the memory space is not copied, only processes are copied, and only memory data is copied if the contents of memory are changed.

However, if you use a marker clearing algorithm, the memory will be set to flag bits, and copying that should not occur will occur frequently.

Multiple free linked lists

The mark-clearing algorithm described above uses only a free linked list to uniformly process blocks of different sizes. But doing so requires traversing each time to find the right pieces, which can be a waste of time.

Here we use multiple free linked lists to store inactive objects. For example: two word blocks into a free list, three word blocks into another free list, and so on.

In this case, if we need to allocate a three-word block, we only need to query the corresponding three-word free list.

How many free lists do I have to make?

Because programs do not request particularly large chunks, we usually set an upper limit on the size of the chunks, such as 100, and anything larger than that makes up a special free linked list. So 101 free lists are enough.

Bitmap tag

In a pure GC mark-sweep algorithm, bits for tokens are allocated in the object header. The algorithm handles both the object and the header, but this is incompatible with copy-on-write.

Bitmap notation only collects and tabulates the flag bits of each object and does not manage the object together. Instead of setting the position in the head of the object when marking, it sets the position in a specific table.

It is important in bitmap markup that the position of the bits in the bitmap table correspond to the individual objects in the heap. Typically a word in the heap is allocated to a bit.

The pseudo-code implementation of the mark() function in bitmap markup is as follows:

func mark(obj){
    obj_num = (obj - $heap_start) / WORD_LENGTH  // WORD_LENGTH is a constant that represents the bit width of a word in the machine
    index = obj_num / WORD_LENGTH
    offset = obj_num % WORD_LENGTH
    
    if ($bitmap_tbl[index] & (1 << offset)) == 0
        $bitmap_tbl[index] |= (1 << offset)
        for (child: children(obj)) // Then recursively mark the object that can be accessed through the pointer array
            mark(*child)
}
Copy the code

Where obj_num refers to the number from the front of the bitmap table, the flag bit of obj is in the number. For example, the obj_num of E is 8.

Obj_num divided by WORD_LENGTH yields index and remainder offset to represent the row and column numbers of the bitmap table, respectively.

advantages

  • Compatible with copy-on-write technology
  • Clearing is more efficient (just traverse the bitmap table and remove only flag bits in the table).

Delay to clear

The time it takes to clean up is proportional to the size of the heap. The larger the heap, the longer the mark-clean action takes and the more it affects the program.

Lazy sweep is a method of reducing the maximum pause time for a program due to the cost of cleaning operations.

Maximum pause time, the maximum time for which program execution is suspended for GC.

In delayed sweep, new_obj() calls lazy_sweep() when allocating. If it can allocate a chunk with a clear operation, it returns a chunk, and if it cannot allocate a chunk, it performs a mark operation. This step is then repeated until the partition or allocation_fail is found

The suspension time of the program can be reduced by the method of delayed elimination, but the delay effect is not uniform. For example, the heap has just been marked:

At this time, active objects and inactive objects are adjacent to the distribution, if the program around the active object to start clearing, it finds objects are active objects can not be cleared, can only keep traversing, the pause time will become longer.

Refer to the link

  • Garbage collection algorithm and implementation
  • Draw Ruby and Python garbage collection

Finally, thanks to the girlfriend support and tolerance, than ❤️

Around the male can also enter the keywords for historical article: male number & small program | | concurrent design mode & coroutines