algorithmgc-learning前言
algorithm, c, gc
Source
Edit
History

什么是Root

Catalogue
  1. 1. 当前root的定义
    1. 1.1. root结构体定义
    2. 1.2. 添加root
  2. 2. Real Root 尝试
    1. 2.1. 寄存器的扫描
    2. 2.2. 系统栈的扫描

github: https://github.com/brewlin/garbage-collect

讲root根之前我们要先理解什么是gc 回收，怎么定义垃圾等等,区别垃圾可以简单这么理解:

  1. 如果某对象没有被任何地方引用 - 垃圾对象
  2. 如果某对象至少还有一次被引用 - 合法对象

那么如何辨别对象没有被任何地方引用呢，这就是root的作用了

当前root的定义

root根在不同场景有不同的意思，但有一点不变通过root能够访问到的对象一定是合法对象，则不应该被清除

root通常有以下的形式表示:

  • 全局变量空间
  • 寄存器
  • 函数栈

并非只有上面的空间才能成为根,通常情况下对于动态运行时语言来说，都会在程序层面创建一个集合，然后自己来管理分配的对象，实现了根对象的管理

当前系列的gc实现不会真的去搜索上面的这些区域去实现根的查找,因为这样有些复杂而且不方便测试和演示

为了更加集中于gc算法的实现表示，采用了一个roots数组来作为根，有如下的规则:

  1. 只要是存在数组里的对象，都称为可达对象，一定是合法对象，不可以回收
  2. 只要不在数组里的对象，都是不可达对象，作为垃圾需要回收(被引用的内存除外)

root结构体定义

root结构体的定义

1
2
3
4
5
//gc.h
typedef struct root_{
    void *ptr; //从heap中申请的内存地址
    void *optr;//用户栈变量的地址
}root;

ptr 指向了我们从heaps中分配的内存地址,也就是用户使用的对象

opr 指向了用户变量的地址，这里讲一下这个成员的作用:

在有些算法中，例如gc复制算法,在执行gc之后，也许当前对象不是垃圾对象不会被回收,但是:当前对象的内存发生了拷贝，内存位置发生了改变

1
2
Obj* p = gc_malloc(sizeof(Obj));
gc();

例如这种情况，optr的作用就体现出来了，在发生gc复制后，p本来应该指向新的空间，但是如果不更新p的值的话那么就会导致异常

因为我们的根保留了引用对象的地址(临时变量基本都是存储在栈上的，其实就是保留了栈的地址rbp - offset),这样只需要在gc执行复制的时候将引用对象一并修改了即可

root全局数组的定义

1
2
3
#define  ROOT_RANGES_LIMIT 100000
extern   size_t root_used;
extern   root roots[ROOT_RANGES_LIMIT];

为了方便测试，直接在栈上分配了默认100000大小的根,通过root_used来记录根对象的个数

添加root

1
2
Obj* p= gc_malloc(Obj);
add_roots(&p);

通过add_roots将对象加入root，成为可达对象，那么只要一直在root中，当前对象永远不会被回收

&p注意这里是引用，在上面部分说了，如果执行的内存被拷贝到新地址了，需要同时更新p的地址

Real Root 尝试

上面基本都是讲的模拟的根，那么我们来尝试一下可不可以实现真正意义的根访问呢

这里的测试主要分为寄存器的访问，系统栈的遍历搜索

完整代码可以在gc-try下测试

寄存器的扫描

首先来统计一下我们在程序运行期间能够使用到的寄存器

  1. 函数参数寄存器: rdi,rsi,rdx,rcx,r8,r9 多的就存放在栈上了不用管
  2. 通用寄存器 : rax,rbx,rbp,rsp,%10-%15

不严谨的说上面这些寄存器是我们最常用的通用寄存器，也就是说寄存器里面可能存储着有我们的对象，需要我们gc的时候进行扫描

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void scan_register()
{
    void *reg;
    if(reg = get_sp())  gc_mark(*(void**)reg);
    if(reg = get_bp())  gc_mark(*(void**)reg);
    if(reg = get_di())  gc_mark(*(void**)reg);
    if(reg = get_si())  gc_mark(*(void**)reg);
    if(reg = get_dx())  gc_mark(*(void**)reg);
    if(reg = get_cx())  gc_mark(*(void**)reg);
    if(reg = get_r8())  gc_mark(*(void**)reg);
    if(reg = get_r9())  gc_mark(*(void**)reg);
    if(reg = get_ax())  gc_mark(*(void**)reg);
    if(reg = get_bx())  gc_mark(*(void**)reg);
}

上面相关的函数可以在这里找到/gc-try/root.s

系统栈的扫描

这里是gc过程的一部分遍历root

1
2
3
4
5
6
7
//现在开始是真正的扫描系统栈空间
void * cur_sp = get_sp();
//高低往低地址增长
assert(sp_start >= cur_sp);
for (; cur_sp < sp_start ; cur_sp += 4){
    gc_mark(*(void**)cur_sp);
}

  1. 通过get_sp() 直接获取当前的系统栈顶,也就是rsp寄存器的地址
  2. sp_start 是我们在main开始前记录的栈起始位置
  3. [sp_start,cur_sp] 这个区间就是我们当前的栈范围，直接扫描整个区间就可以访问我们所有的可达变量
  4. (void**)cur_sp 是一个解引用操作，此时获取的值就是我们的代码里的临时变量

要理解我们扫描栈的意义就要先理解什么是栈，一张图说明一下c的函数栈帧结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
                         +--------------+  -> 这里就是函数A的栈帧范围了
                         |              |  
                    +    |              |
                    |    +--------------+
                    |    |              |
                    |    |   arg(N-1)   |  -> 参数超过6个后，其他参数就放在这里
                    |    |              |
                    |    +--------------+
                    |    |              |
                    |    |Return address|  -> 这里指向函数A的中断的下一个指令地址
Stack grows down    |    |              |
                    |    +--------------+
                    |    |              |
                    |    |     %rbp     |  -> 这里指向函数A的起始栈帧rbp
                    |    |              |
                    |    +--------------+  -> 下面就是函数B的栈帧，当前rbp
                    |    |              |
                    |    |  local(N-1)  |  -> 函数B的本地变量
                    |    |              |
                    v    +--------------+  
                         |              |
                         |              |
                         +--------------+  -> 当前栈顶

上面get_sp()函数是通过汇编实现获取当前寄存器rsp的值，如下:

1
2
3
4
5
.text
.globl get_sp
get_sp:
    movq %rsp,%rax
    ret

其实就是简单的返回了rsp寄存器的值而已，翻译为c函数的话像这样:

1
2
3
void *get_sp(){
    return register(rsp);
}

到这里就是实现了真正意义上的根root，只要当前栈未被释放，那么当前栈帧上能搜索到的的对象都是合法对象