GC algorithm notes: reference counting

I.

In the process of processing, the memory is managed by increasing or decreasing counters through mutator, and there is no time to open GC explicitly.

new_obj(size){
    obj = pickup_chunk(size, $free_list)
    
    if(obj == NULL)
        allocation_fail()
    else 
        obj.ref_cnt = 1
        return obj
}

 

update_ptr(ptr, obj){
    inc_ref_cnt(obj)
    dec_ref_cnt(*ptr)
    *ptr = obj
}

inc_ref_cnt(obj){
    obj.ref_cnt++
}

dec_ref_cnt(obj){
    obj.ref_cnt--
    if(obj.ref_cnt == 0)
        for(child: children(obj))
            dec_ref_cnt(*child)
        reclaim(obj)
}

 

Advantage:

1. Garbage can be recycled immediately

2. Short maximum pause time

3. It is unnecessary to search along the pointer

 

Disadvantages:

1. The increase and decrease of counter is heavy

2. The counter needs to occupy many bits

3. complicated implementation

4. Circular reference cannot be recycled

 

2: Delayed reference counting

One of the reasons for the heavy processing of counter increment and decrement is that the references from the root change frequently.

We let the change in the pointer referenced from the root not be reflected on the counter.

In addition, ZCT is used. ZCT is a table, which records in advance the object whose counter value changes to 0 under the action of Dec ref cnt() function.

dec_ref_cnt(obj){
    obj.ref_cnt--
    if(obj.ref_cnt == 0)
        if(is_full($zct) == TRUE)
            scan_zct()
        push($zct, obj)
}
new_obj(size){
    obj = pickup_chunk(size, $free_list)
    
    if(obj == NULL)
        scan_zct()
        obj = pickup_chunk(size, $free_list)
        if(obj == NULL)
            allocation_fail()
    
    obj.ref_cnt = 1
    return obj
}
scan_zct(){
    for(r : $roots)
        (*r).ref_cnt++
    
    for(obj : $zct)
        if(obj.ref_cnt == 0)
            remove($zct, obj)
            delete(obj)

    for(r : $roots)
        (*r).ref_cnt--
}
delete(obj){
    for(child : children(obj))
        (*child).ref_cnt--
        if((*child).ref_cnt == 0)
            delete(*child)

    
    reclaim(obj)
}

Advantage:

Reduce the burden of frequent change counter

Disadvantages:

The maximum pause time has been extended and the advantage of immediate garbage collection has been lost.

3: Sticky reference counting

In order to reduce the counter bit width.

We assume that the number of bits used for the counter is 5, and if it is greater than 31, it will overflow. In this case, two methods are used:

1. Do nothing

A lot of objects die soon after they are born, and there are few spillovers.

2. Manage with GC mark clear algorithm

make_sweep_for_counter_overflow(){
    reset_all_ref_cnt()
    mark_phase()
    sweep_phase()
}

mark_phase(){
    for(r : $roots)
        push(*r, $mark_stack)
    
    while(is_empty($mark_stack) == FALSE)
        obj = pop($mark_stack)
        obj.ref_cnt++
        if(obj.ref_cnt == 1)
            for(child : children(obj))
                push(*child, $mark_stack)
}

sweep_phase()
{
    sweeping = $heap_top
    while(sweeping < $heap_end)
        if(sweeping.ref_cnt == 0)
            reclaim(sweeping)
        
        sweeping += sweeping.size
}

4: 1-bit reference counting

An extreme example of sticky reference counting.

The counter has only one bit, 0 means the number of references is 1, 1 means the number of references is greater than 1

copy_ptr(dest_ptr, src_ptr){
    delete_ptr(dest_ptr)
    *dest_ptr = *src_ptr
    set_multiple_tag(dest_ptr)
    if(tag(src_ptr) == UNIQUE)
        set_multiple_tag(src_ptr)
}

delete_ptr(ptr)
{
    if(tag(ptr) == UNIQUE)
        reclaim(*ptr)
}

 

5: Partial marking - removal method

Only GC mark clear algorithm is used for those with possible circular references, and reference counting method is used for memory management of other objects.

Such a method of using GC mark clear algorithm only for a part of the object group is called "partial mark clear algorithm". Objects are managed by four different colors.

1. Black: absolutely not the object of garbage

2. White: absolutely the object of garbage

3. Gray: objects searched

4. Shadow: may be the object of recycling garbage

 

dec_ref_cnt(obj)
{
    obj.ref_cnt--
    if(obj.ref_cnt == 0)
        delete(obj)
    else if(obj.color != HATCH)
        obj.color = HATCH
        enqueue(obj, $hatch_queue)
}

 

new_obj(size)
{
    obj = pickup_chunk(size)
    if(obj != NULL)
        obj.color = BLACK
        obj.ref_cnt = 1
        return obj
    else if(is_empty($hatch_queue) == FALSE)
        scan_hatch_queue()
        return new_obj(size)
    else
        allocation_fail()
}
scan_hatch_queue()
{
    obj = dequeue($hatch_queue)
    if(obj.color == HATCH)
        paint_gray(obj)
        scan_gray(obj)
        collect_white(obj)
    else if(is_empty($hatch_queue) == FALSE)
        scan_hatch_queue()
}

paint_gray(obj){
    if(obj.color == (BLACK|HATCH))
        obj.color = GRAY
        for(child : children(obj))
            (*child).ref_cnt -- 
            paint_gray(*child)
}

scan_gray(obj){
    if(obj.color == GRAY)
        if(obj.ref_cnt > 0)
            paint_black(obj)
        else
            obj.color = WHITE
            for(child : children(obj))
                scan_gray(*child)
}

paint_black(obj){
    obj.color = BLACK
    for(child : children(obj))
        (*child).ref_cnt++
        if((*child).color != BLACK)
            paint_black(*child)
}

collect_white(obj){
    if(obj.color == WHITE)
        obj.color = BLACK
        for(child : children(obj))
            collect_white(*child)
        reclaim(obj)
}

 

Generation of recycling waste:

1. Generate circular reference

2. Delete references from external to circular references

 

 

 

Published 46 original articles, won praise 5, visited 1422
Private letter follow

Posted on Wed, 11 Mar 2020 23:32:36 -0700 by kbrij