0%

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 而使用的内存空间,这是一个更加合理的做法。

反射是 Go 语言中较为难以理解的一个特性,网上讲解反射的文章有很多,但是要么讲解细致但是篇幅过长,要么讲解稍微模糊。但其实如果掌握了反射所使用到了一些技术,反射本身是很好理解的,其原理就是一个向上和向下转换的过程。本文会从反射所基于的语言特性出发,简要地分析反射这一特性是如何实现的。

unsafe.Pointer

在讨论unsafe.Pointer之前,我们先来讨论一下 C 语言中的原始指针类型以及指针之间的相互转换。在 C 语言中,所有指针都是可以相互转换的,而对指针取值其实就相当于取当前指针所声明类型长度的一段内存。我们可以利用 C 语言指针的这种特性在不同长度的结构体实现变换,最为经典的例子是 linux 链表。Go 中同样也有指针,但由于 Go 是一种 GC 语言,如果保留 C 指针的这样灵活性,将会对 GC 扫描带来很大的挑战,如果一个指针向上转换了,那么很有可能会造成内存泄露的问题。

为了实现 C 语言中这种灵活转换的特性,Go 中引入了unsafe.Pointer这一类型。unsafe.Pointer是 go 中用于实现类型转换的一种中间类,我们可以将一个长度为 n 的unsafe.Pointer视作是一个长度为 n 的数组(即内存中的某一段数据),但是这一段数组中的数据对用户来说是不可见的。在某种意义上来说,unsafe.Pointer是用来告诉 GC 扫描器这段内存已经被分配,如果需要进行垃圾清理,必须释放这段内存,防止内存泄露。在 C++ 中,这一特性是通过将析构函数作为虚函数来实现的。

为了更直观地表示这一功能,以一个代码实例来演示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type A struct {
header int
hidden unsafe.Pointer // 占位,该字段的所有信息对用户隐藏
}

type B struct {
header int
toHide int // 将会被隐藏的字段
}

func main() {
b := B{1, 1}
var a A
a = *(*A)(unsafe.Pointer(&b))
}

这段代码是可以编译通过并运行的,通过调试器来观察 a 中的值。

image-20230301110108021

可以看到,b 中 header 字段的值被拷贝给了 a,而 hidden 字段则成为了一个 8 字节长度(int 长度)的unsafe.Pointer用于占位,当 a 声明周期结束时,将会释放 header + hidden 长度的内存。要实现这一功能,必须要保证两个结构体的几个起始字段类型和顺序是相同的,并且“基类”需要以unsafe.Pointer字段结尾。

在 go 语言中,为了实现反射大量使用了这一特性,如果对这一特性不了解,建议先学习一下 linux 中的链表实现,这将有助于理解 go 的反射原理。

eface 和 iface

efaceiface是 go 中非空接口与空接口的底层实现,其原始定义代码出现在 runtime2.go:202:

1
2
3
4
5
6
7
8
9
type iface struct {
tab *itab // 存储接口与原始类的类型信息
data unsafe.Pointer // 存储原始类的其他信息
}

type eface struct {
_type *_type // 存储原始类的类型信息
data unsafe.Pointer // 存储原始类的其他信息
}

我们将代码展开,来比较两个结构体之间的差异:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
type iface struct {
// 原 tab 字段 start
inter *interfacetype // 存储接口类型信息
_type *_type // 存储原始类的类型信息
hash uint32 // copy of _type.hash. Used for type switches.
_ [4]byte // 占位,4 字节
fun [1]uintptr // variable sized. fun[0]==0 means _type does not implement inter.
// 原 tab 字段 end

data unsafe.Pointer // 存储原始类的其他信息
}

type eface struct {
_type *_type // 存储原始类的类型信息
data unsafe.Pointer // 存储原始类的其他信息
}

注意这两个类型展开后的区别,iface在起始位置比eface多了一个 inter 字段,该字段用于存储接口信息,这是为了比较不同的非空接口是否相等;而ifaceeface的最后一个字段都是unsafe.Pointer类型。暂时不考虑其中存储的数据类型,将iface.hash字段至iface.data字段也都视为字节(这些字段是为了实现与 XXtype 之间的相互转换),那么可以发现,iface实际上可以表示为如下的形式:

1
2
3
4
5
type iface struct {
inter *interfacetype // 存储接口类型信息
_type *_type // 存储原始类的类型信息
data unsafe.Pointer // 存储原始类的其他信息
}

实际上,去掉inter字段后,iface就成为了eface,因此只需要在该字段上进行相关操作,就能够实现两者之间的相互转换。用一张图来表示两者之间的关系:

eface and iface

XXtype 类型

在 runtime/type.go 文件中,有如下结构体的定义:interfacetype, methodtype , maptype, arraytype, chantype, slicetype, functype, ptrtype, structtype。这些结构体表示了在接口中,go 语言中各种类型的存储形式。值得注意的是,这些结构体全部以_type类型的字段作为起始,这一类型同样被接口用于记录类型。以 structtype为例:

1
2
3
4
5
6
7
type structtype struct {
// Type 信息
typ _type
// Value 信息
pkgPath name // 4 字节
fields []structfield // 24 字节
}

以同一字段作为起始位置,这种做法在 C 中比较常见,其实就是通过统一字段加类型转换的方式实现了零成本的多态,例如 linux 链表,Lua LValue 的实现,都是使用了这种思想。go 中的指针虽然带有类型检查,不能强制转换,但是同样可以使用unsafe.Pointer来实现类似的“向上转换”。事实上,如果将structtype中 Value 信息部分视作一个unsafe.Pointer,那么就可以将其视作是一个eface类型。在 go 中,空接口就是使用这种方式来存储类型信息的,因为空接口没有任何方法,只需要进行类型转换和比较,因此只需要保留 Type 信息字段即可。另外注意到在 typ 字段后的字节(不同 struct 中字段名不同)都是一个指针类型,长度是四个字节,这个长度与iface中的 hash 字段是相互对应的。

iface-xxtype

用一张图像来表示更为直观,iface结构体的第二和第三个字段与 XXtype 中的第一个和第二个字段是对齐的,两个结构体的长度也是相同的;这也意味着 XXtype 与eface结构体的第一个字段是对齐的,二者的结构体也是相同的。三者之间可以通过一定的方式相互转换,这是接口赋值与反射的基础原理。

struct 与 interface 的转换

读到这里,应该可以隐约明白 Relect 是如何实现的了,但是其中还有比较关键的一步,那就是structtype类型究竟是如何生成并且被存储到一个空接口或非空接口中的。许多博客文章起始都没有提到这一点,或者是对这一点介绍地较为简略。

在零成本抽样的 C++ 中以虚函数表的形式来实现了多态,然而这一功能并非 Zero Cost;同样地,在 go 中一个 struct 被赋值给一个它所实现的 interface,这个过程并不是零成本的。go 编译器隐藏了一些必要的工作:在编译时,编译器会增加一些代码来完成这些额外的工作。

在如下的代码片段中:

1
2
3
4
5
6
7
8
9
10
11
// B 是一个接口
type B interface {}
// A 是一个结构体
type A struct {}

func main() {
var b B
a := A{}
// 编译器会做许多额外工作
b = a
}

当 struct A 被赋值给 interface B 时,经过 go 编译器编译后的代码,实际上会实现如下的逻辑:

  • 若生成一个非空接口,将接口所需的interfacetype类型信息拷贝到栈上;
  • 在符号表中寻找 A 类型及其实现的方法,以及 A 实例 data,将这些拷贝到栈上;
  • 调用convT2E64(t *_type, elem unsafe.Pointer) (e eface)生成空接口,或调用convT2I(tab *itab, elem unsafe.Pointer) (i iface)生成非空接口。

这个过程实际上是在搜寻所需要的类型信息,并将类型信息与类型实例中各字段的值打包在一起,生成一个 XXtype 类型实例,最终使用“向上转换”生成接口实例。这个过程中发生了值的拷贝,因为利用unsafe.Pointer实现“向上转换”的前提是数据是连续的。无法确定 A 实例中值在内存中的地址前有足够的空间来分配生成接口所需的字段,因为需要将 A 实例的值拷贝到内存中的其他区域。可以看到,struct 到 interface 的转换其实是一个代价较大的操作。

Reflect 的实现

既然已经知道,struct 赋值给 interface 之后会发生什么,那么理解 Reflect 的实现就是一个非常简单的事情。Reflect 主要实现了取值和取类型这两类的操作。

取类型

首先分析一下取类型的源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
func TypeOf(i any) Type {
// 这一步是为了取空接口中完整的数据类型
eface := *(*emptyInterface)(unsafe.Pointer(&i)) // emptyInterface 与 eface 是 alias 的关系
return toType(eface.typ)
}

// 类型转换与封装
func toType(t *rtype) Type {
if t == nil {
return nil
}
return t
}

这段源码虽然很短,但是理解起来还是稍微困难的。感觉这里理解困难的点主要在于 go 是自举,这里用了一些 go 语言编译中的一些特性,如果用 C 的眼光去看这段代码,其实会更好理解。这段代码其实主要做了以下工作:

  • 在传参阶段,将 struct 转换为 any 类型,这一步发生了上一节中所讲内容;
  • 对 any 类型 i 进行原地转换,这一步是为了取接口中存储的原始值;
  • 将原始值中的 type 字段传递给一个接口 Type,实现封装。

可以注意到,这个过程中发生了两次接口的赋值,由于接口赋值需要拷贝数据,因此在反射中只取类型也是一个代价高昂的操作。最好不要重复获取一个对象的 Type。

取值

对一个对象进行反射取值操作,最终会得到一个Value结构体,结构体的实现如下:

1
2
3
4
5
type Value struct {
typ *rtype
ptr unsafe.Pointer // data
flag // 操作标识
}

可以看到Value其实就是一个eface加上一个flag标识位,该标识位用于表示可以被采取什么样的操作。事实上,它就是由eface拼接得到的:

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
func ValueOf(i any) Value {
if i == nil {
return Value{}
}
// 防止 GC,这里不需要关心
escapes(i)
// 关键过程发生在这里
return unpackEface(i)
}

func unpackEface(i any) Value {
// 取得空接口中的原始数据
e := (*emptyInterface)(unsafe.Pointer(&i))
// NOTE: don't read e.word until we know whether it is really a pointer or not.
t := e.typ
if t == nil {
return Value{}
}
// 生成标志位
f := flag(t.Kind())
if ifaceIndir(t) {
f |= flagIndir
}
// 将类型,数据,标志位进行拼接
return Value{t, e.word, f}
}

这个过程中仍然是发生了两次拷贝,一次是 struct 传入 any 接口,一次是创建 Value 结构体。注意到,Value 这里使用的是复制后的数据,因此如果想使用反射来修改原数据,一定要传入指针。

取字段

反射中的取字段是将Value类型向下转换来实现的。在Value.ptr字段中存储了 XXtype 除类型头外的所有信息,在获取 Value 的基础上再使用“向下转换”可以获取类型具体,我们以获取 struct 中字段个数的方法为例:

1
2
3
4
5
6
7
8
func (v Value) NumField() int {
// 通过 flag 字段检验类型
v.mustBe(Struct)
// Value 向下转换,得到 structType
tt := (*structType)(unsafe.Pointer(v.typ))
// 返回 structType 中的信息
return len(tt.fields)
}

代码中比较关键的过程就是使用unsafe.Pointer来向下转换,这里向下转换能够成为是因为ValueefaceXXtype的同源性,这三者本身就是相同的。

在反射中需要如果使用字段的名称来获取字段,需要经过如下代码,该代码最终是:

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
func (v Value) FieldByName(name string) Value {
v.mustBe(Struct)
if f, ok := v.typ.FieldByName(name); ok {
return v.FieldByIndex(f.Index)
}
return Value{}
}
// 该函数是调用链的最后一环
func (t *structType) FieldByName(name string) (f StructField, present bool) {
// Quick check for top-level name, or struct without embedded fields.
hasEmbeds := false
if name != "" {
// 核心:遍历并且比较各个字段的名称
for i := range t.fields {
tf := &t.fields[i]
if tf.name.name() == name {
return t.Field(i), true
}
if tf.embedded() {
hasEmbeds = true
}
}
}
if !hasEmbeds {
return
}
return t.FieldByNameFunc(func(s string) bool { return s == name })
}

可以看到,FieldByName函数其实是使用遍历加比较字符串的方式来确认字段是否匹配的,当结构体的字段数量较大,并且字段名较长时,性能就会比较差。

总结

Reflect 的实现其实并不是很难,阻碍理解的地方主要在于 struct 与 interface 的转换、unsafe.Pointer 的使用这两点。由于 interface 和 Reflect 中需要全量拷贝值,因此使用引用类型是一个非常明智的抉择。但与之相对的,大量使用引用类型会导致 GC 问题。可以考虑将类型取指针后再赋值给接口。