Go的汇编不是像 C/C++ 一样，对机器码的直接描述，而是兼容跨平台需求实现的半抽象化的指令集。

https://go.dev/doc/asm

汇编分析（Go 1.17）

我们用一个简单的例子来开始汇编分析：

package main

func main() {
	add(1, 3)
}

func add(i, j int) int {
	return i + j
}

汇编结果，删去了一些无关的输出：

# go tool compile -S -l -N main.go
"".main STEXT size=54 args=0x0 locals=0x18 funcid=0x0
        0x0000 00000 (main.go:3)        TEXT    "".main(SB), ABIInternal, $24-0
        0x0000 00000 (main.go:3)        CMPQ    SP, 16(R14)
        0x0004 00004 (main.go:3)        PCDATA  $0, $-2
        0x0004 00004 (main.go:3)        JLS     47
        0x0006 00006 (main.go:3)        PCDATA  $0, $-1
        0x0006 00006 (main.go:3)        SUBQ    $24, SP
        0x000a 00010 (main.go:3)        MOVQ    BP, 16(SP)
        0x000f 00015 (main.go:3)        LEAQ    16(SP), BP
        0x0014 00020 (main.go:3)        FUNCDATA        $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
        0x0014 00020 (main.go:3)        FUNCDATA        $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
        0x0014 00020 (main.go:4)        MOVL    $1, AX
        0x0019 00025 (main.go:4)        MOVL    $3, BX
        0x001e 00030 (main.go:4)        PCDATA  $1, $0
        0x001e 00030 (main.go:4)        NOP
        0x0020 00032 (main.go:4)        CALL    "".add(SB)
        0x0025 00037 (main.go:5)        MOVQ    16(SP), BP
        0x002a 00042 (main.go:5)        ADDQ    $24, SP
        0x002e 00046 (main.go:5)        RET
        0x002f 00047 (main.go:5)        NOP
        0x002f 00047 (main.go:3)        PCDATA  $1, $-1
        0x002f 00047 (main.go:3)        PCDATA  $0, $-2
        0x002f 00047 (main.go:3)        CALL    runtime.morestack_noctxt(SB)
        0x0034 00052 (main.go:3)        PCDATA  $0, $-1
        0x0034 00052 (main.go:3)        JMP     0

"".add STEXT nosplit size=56 args=0x10 locals=0x10 funcid=0x0
        0x0000 00000 (main.go:7)        TEXT    "".add(SB), NOSPLIT|ABIInternal, $16-16
        0x0000 00000 (main.go:7)        SUBQ    $16, SP
        0x0004 00004 (main.go:7)        MOVQ    BP, 8(SP)
        0x0009 00009 (main.go:7)        LEAQ    8(SP), BP
        0x000e 00014 (main.go:7)        FUNCDATA        $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
        0x000e 00014 (main.go:7)        FUNCDATA        $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
        0x000e 00014 (main.go:7)        FUNCDATA        $5, "".add.arginfo1(SB)
        0x000e 00014 (main.go:7)        MOVQ    AX, "".i+24(SP)
        0x0013 00019 (main.go:7)        MOVQ    BX, "".j+32(SP)
        0x0018 00024 (main.go:7)        MOVQ    $0, "".~r2(SP)
        0x0020 00032 (main.go:8)        MOVQ    "".i+24(SP), AX
        0x0025 00037 (main.go:8)        ADDQ    "".j+32(SP), AX
        0x002a 00042 (main.go:8)        MOVQ    AX, "".~r2(SP)
        0x002e 00046 (main.go:8)        MOVQ    8(SP), BP
        0x0033 00051 (main.go:8)        ADDQ    $16, SP
        0x0037 00055 (main.go:8)        RET

FUNCDATA和PCDATA是由编译器引入的，主要包含垃圾回收时使用的信息，这里略过。

本文的分析基于 OpenResty 的 Lua 分支（https://github.com/openresty/luajit2）。

核心 API

table 的 API 定义在 src/lib_table.c 中，API 分为三个部分：

标准库函数：

• table.insert() - 向 table 插入元素
• table.remove() - 移除 table 元素
• table.concat() - 连接 table 元素为字符串
• table.sort() - 对 table 进行排序
• table.maxn() - 找到 table 中最大数字键
• table.move() - 移动 table 元素

LuaJIT 扩展函数：

• table.new() - 预分配指定大小的 table

OpenResty 扩展函数：

• table.clear() - 清空 table 内容
• table.clone() - 克隆 table
• table.nkeys() - 获取 table 键的数量
• table.isarray() - 检查是否为数组
• table.isempty() - 检查 table 是否为空

数据结构

typedef struct Node {
  TValue val;         // 值对象，必须是第一个字段
  TValue key;         // 键对象
  MRef next;          // 哈希链指针
#if !LJ_GC64
  MRef freetop;       // 32位架构下的空闲节点顶部指针(存储在node[0])
#endif
} Node;

typedef struct GCtab {
  GCHeader;           // GC 通用头部：nextgc, marked, gct
  uint8_t nomm;       // 元方法负缓存掩码
  int8_t colo;        // 数组共址标记 (-1表示已分离, >0表示共址大小)
  MRef array;         // 数组部分指针
  GCRef gclist;       // GC 链表指针
  GCRef metatable;    // 元表引用
  MRef node;          // 哈希部分指针
  uint32_t asize;     // 数组部分大小 [0, asize-1]
  uint32_t hmask;     // 哈希掩码 (哈希部分大小-1)
#if LJ_GC64
  MRef freetop;       // 64位架构下的空闲节点顶部指针
#endif
} GCtab;

可以看到，GCtab 中同时定义了数组部分 array 和哈希部分 node。

Lua 的并发（Concurrency）设计核心在于其轻量级、嵌入式的哲学，以及对协作式多任务的首选。它通过强大的协程机制实现并发，但本身不提供多线程/多进程的并行能力。

多线程/多进程

• 核心语言无内置支持： Lua 语言本身的核心 VM 被设计为单线程执行。它不提供内置的语法或标准库来直接创建和管理线程（std::thread）或进程（fork）。
• 独立的 Lua State： 一个 Lua VM 实例被称为一个“Lua State”。每个 Lua State 是完全独立的运行时环境，拥有自己的全局变量、栈、打开的文件、垃圾回收器等。它们之间默认不共享任何数据。
• 宿主语言的责任： 如果需要在 Lua 中实现真正的并行（多核利用），必须依赖于宿主语言（如 C/C++）的多线程/多进程机制。
  • 实现方式： 在宿主语言的每个线程或进程中，创建并运行一个独立的 Lua State。
  • 数据交换： 这些独立的 Lua State 之间无法直接共享内存。数据交换必须通过宿主语言提供的进程间通信 (IPC) 或线程间通信 (ITC) 机制（如消息队列、共享内存、管道、套接字等）来完成。
  • 优点： 简单安全，因为 Lua State 之间是隔离的，避免了复杂的并发同步问题。
  • 缺点： 额外的通信开销和复杂性，且无法在单个 Lua State 内部实现并行。
• 第三方库（封装）： 存在一些第三方库（如 LuaLanes）试图提供在 Lua 中模拟多线程/多进程的 API。这些库通常是在底层创建独立的 Lua State，并封装了 IPC 机制，方便 Lua 开发者使用，但其本质仍然是基于宿主语言的底层能力和独立的 Lua State。

协程

协程的设计与实现

• 设计理念： Lua 协程是为了提供协作式多任务 (Cooperative Multitasking) 而设计。它们允许在单个线程中实现任务的暂停和恢复，以模拟并发，而无需复杂的锁机制。
• “有栈协程” (Stackful Coroutines)： Lua 协程是有栈的。这里的“栈”指的不是操作系统的 C 语言栈，而是 Lua 虚拟机内部维护的Lua VM 栈。
  • Lua VM 栈： 每个协程在创建时都会分配一个独立的 Lua VM 栈（或在需要时动态扩展）。这个栈存储着协程的局部变量、函数参数、中间表达式结果和函数调用上下文。
• 实现机制：
  • coroutine.create(function)： 创建一个新的协程（一个thread类型的值），但并不立即执行。它会分配并初始化一个新的 Lua VM 栈。
  • coroutine.yield(...) (保存栈)： 当一个协程调用 yield 时，Lua VM 会：
    1. 保存当前 Lua VM 栈的完整状态（包括所有活跃的栈帧、局部变量值、程序计数器等）。这些信息会被存储在协程对象本身（在堆上分配）中。
    2. 暂停当前协程的执行。
    3. 将控制权返回给调用 coroutine.resume 的那个协程或主线程。 C 语言栈会正常展开，yield 作为一个 C 函数正常返回。
  • coroutine.resume(co, ...) (恢复栈)： 当一个协程被 resume 时，Lua VM 会：
    1. 从协程对象中加载并恢复其之前保存的 Lua VM 栈状态。 这包括设置栈顶指针、恢复所有栈帧和程序计数器，使得协程能够从上次 yield 的点继续执行。
    2. 将控制权转移给被恢复的协程。 C 语言栈上会为 resume 函数创建一个新的栈帧，并在其中运行被恢复的 Lua 协程。
• 优点： 简单、高效、避免了与 OS 栈相关的复杂性，并且由于是协作式的，没有竞态条件和锁的开销。
• 缺点： 无法利用多核 CPU。

协程示例：

Lua 和 LuaJIT

Lua

Lua 是一个开源项目，由巴西里约热内卢天主教大学的 Roberto Ierusalimschy、Luiz Henrique de Figueiredo 和 Waldemar Celes 创建。它的版本控制相对简单明了。

Lua 的版本体系

Lua 的版本号通常是 X.Y 的形式，例如 5.1, 5.2, 5.3, 5.4。

• X (主版本号/Major Version): 表示一个重大更新，通常会引入不兼容的更改（breaking changes），新的核心特性，或者对虚拟机架构的显著改进。从 5.x 到 5.y，y 增加通常意味着语法、API 或语义的更改，可能需要修改现有代码。
  • 例子:
    • Lua 5.0: 引入了协程 (coroutines)。
    • Lua 5.1: 引入了模块系统 (module system)、vararg 参数的改进。
    • Lua 5.2: 引入了 goto 语句、环境 (environments) 的重新设计、新的 _ENV 上值。
    • Lua 5.3: 引入了整数类型、位操作 (bitwise operations)、UTF-8 支持。
    • Lua 5.4: 引入了新的垃圾回收器、弱表 (weak tables) 的改进。
• Y (次版本号/Minor Version) 或补丁版本 (Patch Version): 在主版本中，通常用于表示错误修复、性能优化或次要的功能增强。这些更改通常是向后兼容的（backward compatible），不会破坏现有代码运行。有时候，一个版本号会是 X.Y.Z 的形式，Z 就代表补丁版本。
  • 例子: Lua 5.3.1, Lua 5.3.2, Lua 5.3.3 等等。这些通常是修复 bug。

LuaJIT

https://github.com/LuaJIT/LuaJIT

无锁数据结构和传统的数据结构在内存管理有一点区别是：当数据不用了，需要释放内存时，传统数据结构直接调用free()就可以了，但是无锁数据结构不行。举个例子，如下图所示，T1正在读取b1的时候，T2释放了b1，T1中的指针就变成了野指针，造成不安全的内存访问。

因此，在无锁数据结构中，内存的释放操作一般要延后执行，即保证没有线程能够访问到该片内存后，再执行内存回收。这种方式被称作Safe Memory Reclamation（SMR）。

从上述例子中，我们可以从两个方面去理解一个SMR算法：

1. 如何保护正在使用的数据不被释放？
2. 什么时候能安全地释放已经被标记为需要释放的内存？

下面介绍两种常用的SMR算法：

1. Hazard Pointers（Protected Pointers）
2. Epoch-Based Reclamation（基于代际的内存释放）

Hazard Pointers

Hazard Pointers的基本思想是线程访问数据块时会将指针记录下来，其它线程尝试释放内存时会感知到数据块引用的存在，从而延迟释放内存，直到所有线程对该数据块的访问结束。

如上图所示，使用hazard pointers有如下几个步骤：

1. 在线程访问共享数据时，先调用reserve()方法，将指针记录在一个list内；
2. T2线程尝试释放释放b1时，调用retire()，因为检测到还有线程访问b1，延迟释放内存；
3. 因为内存没有真正释放，T1能在b1 retire后继续访问b1。访问结束后，T1调用unreserve()将指针从list中移除；
4. T3调用gc()（可以周期性运行，也可以事件触发），遍历所有retired的数据块，如果list内没有指向数据块的指针，即可以真正回收内存。

Hazard Pointers有些致命的缺点：

1. 不够快。因为reserve()保护的指针需要立即被gc()感知到，所以，两个函数都需要引入开销非常大的store-load fence。在遍历整个数据结构时，每个数据块都会调用reserve()，导致遍历效率降低；
2. 并不是所有的数据结构都适用Hazard Pointers。在前文的Lock-free Linked List中，我们也提过Harris-Michael‘s traversing是为了专门支持Hazard Pointers的。Harris’s traversing会retire一个连续的数据块，这样，即便T1线程保护了其中一个数据块，gc()仍然可以回收其它的数据块内存，T1线程访问next指针时，仍然会出现问题。

Epoch-Based Reclamation

Hazard Pointers只保护无锁数据结构中真正被访问的那部分数据，这也导致了上文中Hazard Pointers的两个缺陷。与Hazard Pointers不同的是，EBR保护的是数据结构中所有可能潜在的访问。这样也就不需要频繁地在线程间同步。

每个线程在访问数据结构前都会开启一个代际（epoch）。T1在代际e中retire了b1和b2。那么什么时候能安全地reclaim b1和b2的内存呢？

如上图，我们在这个EBR算法中规定了一个代际一致性规则：并发的代际之间最多只能相差1。也就是说，只要T1还没有调用set_quiescent()结束掉e代，那么其它线程通过set_active()开启的代际号只能是e+1。而所有的e+1代的线程是有可能引用到b1和b2的。当e代结束，T2开启e+2代时，因为e+2代和e代不存在同时发生的可能性（通过代际一致性规则保证），所以在e+2代是不可能访问到e代retire的b1和b2的。到了e+3代，表示所有可能访问到b1和b2的e+1代都已经结束，此时即可安全地回收b1和b2内存。

不同的代际一致性规则，可以安全回收的代际是不一样的。