Sepk

个人博客

0%

Lua 与 Go GC 机制的一些记录

发表于 更新于 分类于 ， ，
本文字数： 3.8k 阅读时长 ≈ 3 分钟

Lua 和 Go 都是具有 GC 机制的语言，两者在标记阶段都采用了三色标记法，但是由于两种语言的类型、特性等方面不同，它们的 GC 机制在实现上具有很大的差别。本文主要概括性地描述两种语言的 GC 实现思路，不讨论具体的实现。

Lua 的 GC 实现

Lua 中的 GC 实现是比较简单的，这主要来自于 Lua 不支持用户自定义类型、不支持指针类型，这两个特性决定了 Lua 中的对象引用机制是比较简单的。同时，Lua 是一门脚本语言，但是同样具有编译机制，从 Lua 虚拟机的角度来看，每一个 TValue 都是高度抽象化的，在 GC 的过程中可以将这些分配处的 TValue 当做一个普通的 C 对象来处理。

在 Lua 的基本对象中，并不是所有的对象都会被 GC 扫描，有一些对象是分配在栈上的，一些对象的生命周期则是由 C 程序来控制的。这些对象是不需要进行 GC 的。而其他需要 GC 的对象，则具有一个统一的 struct 头GCObject，该 struct 的定义如下：

1
2
3
4
5
6
#define CommonHeader	struct GCObject *next; lu_byte tt; lu_byte marked

/* Common type for all collectable objects */
typedef struct GCObject {
    CommonHeader;
} GCObject;

GCObject是一个非侵入式链表，所有可以被 GC 的对象都会被放入这个链表中，这是为了方便后续的扫描。Lua 这里的实现得益于它的运行环境是搭建在 C 语言之上的一个虚拟机，而非真实的物理机环境。Lua 栈上的每一个对象都是一个GCObject，而 C 语言中则只能看得到内存段。这里的实现有一些空间换时间的意味，每一个被分配出的 TValue 都加入这个头，就意味着在进行 GC 的时候就不需要再对整个 Lua 栈进行扫描了，因此在 GC 的标记起始阶段就会快很多。不过 Lua 脚本的规模并不大，一段程序需要分配出的对象并不多，所以这里的额外内存消耗的可控的。

Lua 脚本的运行起点是函数，如果脚本未定义外部函数，那么编译器会为其自动生成 main 函数。除去一些存储在 _ENV 表中的全局变量，其余对象的生命周期都是随着当前函数栈的切换而结束的。Lua 中的函数会被编译为一个Proto类型：

1
2
3
4
5
6
7
8
9
/*
** Function Prototypes
*/
typedef struct Proto {
    CommonHeader;
    ...
    GCObject *gclist;
} Proto;

可以看到，该类型中具有一个字段gclist，该字段会链接所有分配出的 GCObject。

Go 的 GC 实现

有关 Go 中 GC 机制的详细探讨，可以参考博客文章。以下内容参考了该文章。

Go 中的 GC 实现比 Lua 要更为复杂，复杂度主要来自于：指针类型、struct 类型、物理机环境。指针类型和 struct 类型使得 GC 扫描更加复杂，并且在物理机环境下对象的视图是内存段。另外， Go 主要用来编写大型的程序，如果使用类似 Lua 的 Header，可能会耗费比较多的内存，是不现实的。

在 Go 语言中，编译器会在编译期为每一个 struct 类型生成一个_type类型的对象，并且记录在 runtime 中。该类型的定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
type _type struct {
    size       uintptr
    ptrdata    uintptr // size of memory prefix holding all pointers
    hash       uint32
    tflag      tflag
    align      uint8
    fieldalign uint8
    kind       uint8
    alg        *typeAlg
    // gcdata stores the GC type data for the garbage collector.
    // If the KindGCProg bit is set in kind, gcdata is a GC program.
    // Otherwise it is a ptrmask bitmap. See mbitmap.go for details.
    gcdata    *byte
    str       nameOff
    ptrToThis typeOff
}

该类型中的gcdate字段与 GC 机制密切相关，该字段主要用于保存 struct 中指针的位置。在 GC 扫描中，指针指向的对象地址与当前地址并非连续的，需要做一些额外的处理——因为在内存中，并不能直接去确认某一段存储的是否是一个指针值。在编译期，编译器将会确认一个 struct 中所包含的指针个数以及位置，以 bitmap 的形式存储在gcdata字段中。这种实现的思路将指针的确定在编译期完成，能够避免在程序的运行阶段大幅度地对内存段进行扫描，能够有助于提升效率。

为了进行 GC，必须为分配出的 Go 对象建立起标识位，从而判断内存段中的对象类型。在生成对象时，go 语言不仅仅会开辟出对象所需要的内存，同样也会开辟出一片内存区域来存储_type类型的指针。可以类比使用malloc函数时，会多出 20 字节的大小来分配空间的相关信息。当需要进行 GC 扫描时，会先读取出_type类型，将当前对象设置为已经标记，然后根据gcdata字段来确定是否含有指针以及下一次扫描的范围。Go 进行对象创建的函数是runtime/malloc.go中的newobject，该函数在内部仅仅调用了mallocgc函数。mallocgc函数较长，但是其中大部分内容与 GC 无关，该函数中与 GC 相关的部分是判别type类型是否需要 GC 扫描，如果对象需要 GC 扫描，会使用heapBitsSetType函数来进行一些工作。

Go 中 GC 扫描是从 goroutine 栈上开始的，当 GC 开始时，程序将会从栈的起始位置开始，按照已经预留好的类型信息逐个进行扫描和确认。对象的内存区域使用的是scanblock函数，这个函数会以 8 字节为步进值，对一个对象所在的内存空间进行扫描，判断内存空间中是否有指针存在，并且判断指针的有效性。若指针有效会将指针指向的对象加入到灰色标记对象中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func scanblock(b0, n0 uintptr, ptrmask *uint8, gcw *gcWork, stk *stackScanState) {
  b := b0
  n := n0
  // 本次扫描达到地址 n 后结束
  for i := uintptr(0); i < n; {
    // 计算当前地址偏移量上是否是指针，如果不是指针则地址 +8 
    bits := uint32(*addb(ptrmask, i/(sys.PtrSize*8)))
    if bits == 0 {
      i += sys.PtrSize * 8
      continue
    }
    // 当前位置上有指针
    for j := 0; j < 8 && i < n; j++ {
      // 指针类型？只有标识了指针类型的，才有可能走到下面的逻辑去；
      if bits&1 != 0 {
        // 类型转换，获取当前内存地址存储的指针值
        p := *(*uintptr)(unsafe.Pointer(b + i))
        if p != 0 {
          if obj, span, objIndex := findObject(p, b, i); obj != 0 {
            // 将指针指向的对象标记为灰色
            greyobject(obj, b, i, span, gcw, objIndex)
          } else if stk != nil && p >= stk.stack.lo && p < stk.stack.hi {
            stk.putPtr(p)
          }
        }
      }
      bits >>= 1
      i += sys.PtrSize
    }
  }
}

简单对比分析

本质上来说，Lua 和 Go 中的 GC 思想都是类似的，核心要点就是要记录下每一个内存段上所存储的类型，然后再根据一定的方式来依次访问分配出的每一个对象。Lua 中的 tt 和 Go 中的 _type 都是为了记录类型的相关内容，但由于 Go 的复杂度更高，因此需要实现更多的功能。

由于 Lua 语言是比较简单的，对象的分配和回收都建立在 C 语言层面之上，天然具有较高的抽象性；Lua 中的 GC 实现使用了链表头的形式，这一组织形式意味着 Lua 中可以更快地寻找到需要 GC 的对象，但是这种实现方式对空间的浪费比较严重。Lua 的 GC 扫描也是较为简单的，这主要还是因为 Lua 中每一段都被包裹在一个函数中，比较容易找到对象的分配位置，只需要在函数中记录每一个分配的对象即可。整体来说，Lua 的 GC 实现比较浪费空间，但是 GC 的性能可能会较好一点，这主要来自于 Lua 独特的对象管理机制。

Go 中的 GC 机制重点在于指针位置的确认上，借助 struct 的内存对齐机制和 bitmap 存储机制可以简单高效地记录 struct 中的每一个指针。在扫描方面，虽然 Go 程序的运行是以 goroutine 为起点的，但由于 Go 程序一般规模较大，直接记录每一个可 GC 的对象需要耗费大量的内存空间，这是不太现实的。使用栈扫描虽然会在一定程度上降低起始标记阶段的性能，但是会极大地降低因为 GC 而使用的内存空间，这是一个更加合理的做法。