CAS 在 Go 言语中的完结

什么是 CAS ？

CAS (Compare And Swap) 是原子操作的一种，通常用于多线程（协程）环境下对某个值进行原子更改。它的功用是判别内存中某个变量当时的值是否是咱们预期的值，假如是咱们预期的值则将其更新成咱们指定的新值，否则就坚持当时值。以 CAS(v, expected, newV) 为例：

graph LR
Start --> Compare{v == expected?};
Compare -- Yes --> Swap[Swap: v = newV];
Swap --> End;
Compare -- No --> End;

Go 言语中许多并发原语都是依靠信号量和原子操作完结的。下面是互斥锁*Mutex.Lock办法中运用 CAS atomic.CompareAndSwapInt32的示例：

func (m *Mutex) Lock() {
    // 假如此时m.state == 0，则阐明锁未被占用，获取锁（将锁的状态改为mutexLocked）
	if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
        // ...
		return
	}
	// ...
}

从上面的流程图中能够看出 CAS 实际由两个阶段组成：1. Compare, 比较变量当时值和咱们预期的值是否持平，若持平进入过程2；2. Swap, 将变量赋值为新值。

触摸过多线程（协程）的同学应该知道，过程1和过程2本身就不是并发安全的，更何况 CAS 由两个过程组成。咱们通常运用锁机制来确保并发安全，但是互斥锁的完结又运用了 CAS ，这岂不是死循环了？实际上 CAS 是一种非常底层的并发原语，需求运用特定的 CPU 指令完结。不同的 CPU 架构（具体来说是指令集）供给了不同的指令，如 amd64 主要运用 LOCK 和 COMXCHG 指令来完结 CAS。

Go 言语通过 sync/atomic 包向用户暴露了各种原子操作的办法：CAS、Load、Store等。 不过sync/atomic 包只是对 runtime 包中对原子操作完结的一个调用。如图 1 所示，Go言语在 runtime 中完结了根据 amd64, arm, loong64, mips64 等架构的原子操作， CAS 也包括其中（本文根据 Go 1.16 版别）：

CAS 在 Go 语言中的实现
图 1. Go 言语根据不同 CPU 架构的原子操作完结，runtime/internal/atomic

以 atomic.CompareAndSwapInt32 为例

以 amd64 架构下的 atomic.CompareAndSwapInt32 办法为例介绍 CAS 的完结。下面是此办法在 sync/atomic/asm.s 中的汇编代码：

TEXT CompareAndSwapInt32(SB),NOSPLIT,$0
	JMP	runtime/internal/atomicCas(SB)

Go汇编中函数界说的语法如下：

TEXT symbol(SB), [flags,] $framesize[-argsize]

函数的界说由5个部分组成：

  • TEXT：Go汇编言语中的指令，用于界说一个函数；
  • symbol(SB)：symbol是包途径函数名，包途径能够省略。SB寄存器的值是代码段的起始方位，symbol(SB)用于获取此函数在代码段中的起始方位，即函数的进口；
  • flags：可选，指示函数的一些特别行为，NOSPLIT 表明 “Don’t insert stack check preamble.”；
  • $framesize：函数的栈帧巨细；
  • -argsize：可选，此函数参数和回来值的巨细。

根据Go汇编中函数界说的语法，上面的汇编代码界说了 atomic.CompareAndSwapInt32 办法，办法体内只要一条 JMP 指令，跳转到 runtime/internal/atomicCas 办法处持续履行。

下面是 Cas 办法的伪代码和汇编代码，代码坐落 runtime/internal/atomic/atomic_amd64.s 中：

// bool Cas(int32 *ptr, int32 old, int32 new)
// Atomically:
//	if(*ptr == old){
//		*ptr = new;
//		return 1;
//	} else
//		return 0;
TEXT Cas(SB),NOSPLIT,$0-17
	MOVQ	ptr+0(FP), BX
	MOVL	old+8(FP), AX
	MOVL	new+12(FP), CX
	LOCK
	CMPXCHGL	CX, 0(BX)
	SETEQ	ret+16(FP)
	RET

代码的上半部分注释是 Cas 的伪代码，针对 int32 类型进行比较和替换。下半部分是实在的汇编代码，首要看一下函数界说：

TEXT Cas(SB),NOSPLIT,$0-17

Cas 函数接纳3个参数：8字节的 *int32 类型 ptr，4字节的 int32 类型 old，4字节的 int32 类型new；回来值为1字节的 bool 类型。因此 Cas 办法参数和回来值的巨细为 8 + 4 + 4 + 1 = 17 字节，所以在函数界说中 argsize 的巨细为17。

Go汇编运用的是 caller-save 形式，被调用函数的入参参数、回来值都由调用者准备、保护。因此当需求调用一个函数时，调用方 caller 需求先将这些作业准备好，才调用下一个函数。假设由函数 func1 调用 Cas，下图是程序运转过程中的栈帧布局：

CAS 在 Go 语言中的实现
图 2. func1 调用 Cas 办法的栈帧布局

为了简化汇编代码的编写，Go汇编引入了 FP 伪寄存器，用于在汇编中愈加简便地寻址参数和回来值。FP 的值表明第一个参数的地址，在图2中就表明参数 ptr 的地址。Go汇编语法要求，通过 FP 伪寄存器拜访变量时必须有一个标识符前缀，一般运用参数对应的变量名作为前缀（伪寄存器编译后都会转成实在的物理寄存器，不会在最终生成的汇编代码中有任何伪寄存器）。因此汇编代码中的前3行的效果是寻址参数将其复制到特定寄存器中：

MOVQ	ptr+0(FP), BX	// 将ptr的值复制到BX寄存器，MOVQ中的Q表明操作数宽度为8字节
MOVL	old+8(FP), AX	// 将old的值复制到AX寄存器，MOVL中的L表明操作数宽度为4字节
MOVL	new+12(FP), CX	// 将new的值复制到CX寄存器，MOVL中的L表明操作数宽度为4字节

Go汇编的风格和常见的Intel风格、AT&T风格不太相同：

  • 操作数的宽度：Intel汇编中运用AX、EAX、RAX不同的寄存器名称表明操作数的宽度；Go汇编运用指令的后缀表明操作数的宽度，W代表16位，L代表32位，Q表明64位；
  • 操作数顺序：Intel汇编中源操作数在后，意图操作数在前；Go汇编中源操作数在前，意图操作数在后；
  • 地址表明：Intel汇编中的[ESP + EBX * 2 + 16]，在Go汇编中表明为16(SP)(BX * 2)

接下来是 LOCK 指令：

LOCK

参阅 AMD64 Architecture Programmer’s Manual Volume 3:General-Purpose and System Instructions（亦可参阅Intel的技能手册），LOCK 指令的介绍如下：

LOCK prefix:

The LOCK prefix causes certain kinds of memory read-modify-write instructions to occur atomically.

译：LOCK前缀使得某些类型的内存读-修改-写指令以原子方法发生。

The prefix is intended to give the processor exclusive use of shared memory in a multiprocessor system.

译：LOCK前缀旨在使某个处理器在多处理器系统中独占同享内存。

The LOCK prefix can only be used with forms of the following instructions that write a memory operand: ADC, ADD, AND, BTC, BTR, BTS, CMPXCHG, CMPXCHG8B, CMPXCHG16B, DEC, INC, NEG, NOT, OR, SBB, SUB, XADD, XCHG, and XOR.

译：LOCK前缀只能与以下写入内存操作数的指令形式一起运用：ADC, ADD, AND, BTC, BTR, BTS, CMPXCHG, CMPXCHG8B, CMPXCCHG16B, DEC, INC, NEG, NOT, OR, SBB, SUB, XADD, XCHG和XOR。

LOCK 指令使得接下来的 COMXCHGL 指令独占同享内存，以原子的形式完结。COMXCHGL 指令的效果就是比较（COM）并交换（XCHG）：

CMPXCHG (Compare and Exchange):

Compares the value in the AL, AX, EAX, or RAX register with the value in a register or a memory location (first operand). If the two values are equal, the instruction copies the value in the second operand to the first operand and sets the ZF flag in the rFLAGS register to 1. Otherwise, it copies the value in the first operand to the AL, AX, EAX, or RAX register and clears the ZF flag to 0.

译：将AL、AX、EAX或RAX寄存器中的值与寄存器或内存方位（第一个操作数）中的值进行比较。假如两个值持平，则指令将第二个操作数中的值复制到第一个操作数，并将rFLAGS寄存器中的ZF标志设置为1。否则，将第一个操作数中的值拷贝到AL、AX、EAX或RAX寄存器，并将ZF标志清除为0。

LOCK	// 使得接下来的COMXCHGL指令独占同享内存，以原子的形式完结
CMPXCHGL	CX, 0(BX)
/*
if AX == [BX] { // 比较 *ptr和old
	ZF = 1 // 记录比较结果
	[BX] = CX // 假如持平则令*ptr = new
} else { // 假如不持平坚持*ptr不变
	ZF = 0 // 记录比较结果
	AX = [BX] // side effect
}
*/

接下来的 SETEQ 指令会读取 ZF 寄存器的值，假如 ZF 寄存器的值为1，则将回来值 swapped 置为1 (true)，反之置为0 (false)。最终是 RET 指令用于函数回来，至此 func1 调用 atomic.CompareAndSwapInt32 的流程结束（实际上调用的是 runtime 下的 Cas 办法）：

SETEQ	ret+16(FP)
RET

总结

Go 言语针对不同的 CPU 架构，运用 Plan9 汇编调用相应的 CPU 指令，完结了对 CAS 操作的支撑。其实除了 CAS，Go 言语对一些如 Store, Add 等其他原子操作的支撑都是运用相似的方法完结的。

ABI

  • 函数调用栈的布局归于 abi 范畴的知识，Go 在 1.17 版别之后供给了 abi 文件，方位坐落源码 src/cmd/compile/internal-abi.md。也是在 1.17 版别 Go 开始运用寄存器传参，之前是栈传参；
  • Plan9 汇编能够参阅 Rob Pike 编写的 A Manual for the Plan 9 assembler 以及官方文档中 A Quick Guide to Go’s Assembler.

最终

I do and I understand.