引言

本文以go1.14 darwin/amd64中的原子操作为例，探究原子操作的汇编实现，引出LOCK指令前缀、可见性、MESI协议、Store Buffer、Invalid Queue、内存屏障，通过对CPU体系结构的探究，从而理解以上概念，并在最终给出一些事实。

Go中的原子操作

我们以atomic.CompareAndSwapInt32为例，它的函数原型是：

func CompareAndSwapInt32(addr *int32, old, new int32) (swapped bool)

对应的汇编代码为：

// sync/atomic/asm.s 24行
TEXT ·CompareAndSwapInt32(SB),NOSPLIT,$0
	JMP	runtime∕internal∕atomic·Cas(SB)

通过跳转指令JMP跳转到了runtime∕internal∕atomic·Cas(SB)，由于架构的不同对应的汇编代码也不同，我们看下amd64平台对应的代码：

// runtime/internal/atomic/asm_amd64.s 17行
TEXT runtime∕internal∕atomic·Cas(SB),NOSPLIT,$0-17
	MOVQ	ptr+0(FP), BX // 将函数第一个实参即addr加载到BX寄存器
	MOVL	old+8(FP), AX // 将函数第二个实参即old加载到AX寄存器
	MOVL	new+12(FP), CX // // 将函数第一个实参即new加载到CX寄存器
	LOCK // 本文关键指令，下面会详述
	CMPXCHGL	CX, 0(BX) // 把AX寄存器中的内容(即old)与BX寄存器中地址数据(即addr)指向的数据做比较如果相等则把第一个操作数即CX中的数据(即new)赋值给第二个操作数
	SETEQ	ret+16(FP) // SETEQ与CMPXCHGL配合使用，在这里如果CMPXCHGL比较结果相等则设置本函数返回值为1，否则为0(16(FP)是返回值即swapped的地址)
	RET // 函数返回

从上面代码中可以看到本文的关键：LOCK。它实际是一个指令前缀，它后面必须跟read-modify-write指令，比如：ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, CMPXCHG16B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD, XCHG。

LOCK实现原理

在早期CPU上LOCK指令会锁总线，即其他核心不能再通过总线与内存通讯，从而实现该核心对内存的独占。

这种做法虽然解决了问题但是性能太差，所以在Intel P6 CPU（P6是一个架构，并非具体CPU）引入一个优化：如果数据已经缓存在CPU cache中，则锁缓存，否则还是锁总线。

Cache Coherency

CPU Cache与False Sharing 一文中详细介绍了CPU缓存的结构，CPU缓存带来了一致性问题，举个简单的例子：

// 假设CPU0执行了该函数
var a int = 0
go func fnInCpu0() {
    time.Sleep(1 * time.Second)
    a = 1 // 2. 在CPU1加载完a之后CPU0仅修改了自己核心上的cache但是没有同步给CPU1
}()
// CPU1执行了该函数
go func fnInCpu1() {
    fmt.Println(a) // 1. CPU1将a加载到自己的cache，此时a=0
    time.Sleep(3 * time.Second)
    fmt.Println(a) // 3. CPU1从cache中读到a=0，但此时a已经被CPU0修改为0了
}()

上例中由于CPU没有保证缓存的一致性，导致了两个核心之间的同一数据不可见从而程序出现了问题，所以CPU必须保证缓存的一致性，下面将介绍CPU是如何通过MESI协议做到缓存一致的。

MESI是以下四种cacheline状态的简称：

• M(Modified)：此状态为该cacheline被该核心修改，并且保证不会在其他核心的cacheline上
• E(Exclusive)：标识该cacheline被该核心独占，其他核心上没有该行的副本。该核心可直接修改该行而不用通知其他核心。
• S(Share)：该cacheline存在于多个核心上，但是没有修改，当前核心不能直接修改，修改该行必须与其他核心协商。
• I(Invaild)：该cacheline无效，cacheline的初始状态，说明要么不在缓存中，要么内容已过时。

核心之间协商通信需要以下消息机制：

• Read: CPU发起数据读取请求，请求中包含数据的地址
• Read Response: Read消息的响应，该消息有可能是内存响应的，有可能是其他核心响应的（即该地址存在于其他核心上cacheline中，且状态为Modified，这时必须返回最新数据）
• Invalidate: 核心通知其他核心将它们自己核心上对应的cacheline置为Invalid
• Invalidate ACK: 其他核心对Invalidate通知的响应，将对应cacheline置为Invalid之后发出该确认消息
• Read Invalidate: 相当于Read消息+Invalidate消息，即当前核心要读取数据并修改该数据。
• Write Back: 写回，即将Modified的数据写回到低一级存储器中，写回会尽可能地推迟内存更新，只有当替换算法要驱逐更新过的块时才写回到低一级存储器中。

手画状态转移图

这里有个存疑的地方：CPU从内存中读到数据I状态是转移到S还是E，查资料时两种说法都有。个人认为应该是E，因为这样另外一个核心要加载副本时只需要去当前核心上取就行了不需要读内存，性能会更高些，如果你有不同看法欢迎在评论区交流。

一些规律

1. CPU在修改cacheline时要求其他持有该cacheline副本的核心失效，并通过Invalidate ACK来接收反馈
2. cacheline为M意味着内存上的数据不是最新的，最新的数据在该cacheline上
3. 数据在cacheline时，如果状态为E，则直接修改;如果状态为S则需要广播Invalidate消息，收到Invalidate ACK后修改状态为M;如果状态为I（包括cache miss）则需要发出Read Invalidate

Store Buffer

当CPU要修改一个S状态的数据时需要发出Invalidate消息并等待ACK才写数据，这个过程显然是一个同步过程，但这对于对计算速度要求极高的CPU来说显然是不可接受的，必须对此优化。 因此我们考虑在CPU与cache之间加一个buffer，CPU可以先将数据写入到这个buffer中并发出消息，然后它就可以去做其他事了，待消息响应后再从buffer写入到cache中。但这有个明显的逻辑漏洞，考虑下这段代码：

a = 1
b = a + 1

假设a初始值为0，然后CPU执行a=1，数据被写入Store Buffer还没有落地就紧接着执行了b=a+1，这时由于a还没有修改落地，因此CPU读到的还是0，最终计算出来b=1。

为了解决这个明显的逻辑漏洞，又提出了Store Forwarding：CPU可以把Buffer读出来传递(forwarding)给下面的读取操作，而不用去cache中读。

这倒是解决了上面的漏洞，但是还存在另外一个问题，我们看下面这段代码：

a = 0
flag = false
func runInCpu0() {
    a = 1
    flag = true
}

func runInCpu1() {
    while (!flag) {
   	continue
    }
    print(a)
}

对于上面的代码我们假设有如下执行步骤：

1. 假定当前a存在于cpu1的cache中，flag存在于cpu0的cache中，状态均为E。
2. cpu1先执行while(!flag)，由于flag不存在于它的cache中，所以它发出Read flag消息
3. cpu0执行a=1，它的cache中没有a，因此它将a=1写入Store Buffer，并发出Invalidate a消息
4. cpu0执行flag=true，由于flag存在于它的cache中并且状态为E，所以将flag=true直接写入到cache，状态修改为M
5. cpu0接收到Read flag消息，将cache中的flag=true发回给cpu1，状态修改为S
6. cpu1收到cpu0的Read Response：flat=true，结束while(!flag)循环
7. cpu1打印a，由于此时a存在于它的cache中a=0，所以打印出来了0
8. cpu1此时收到Invalidate a消息，将cacheline状态修改为I，但为时已晚
9. cpu0收到Invalidate ACK，将Store Buffer中的数据a=1刷到cache中

从代码角度看，我们的代码好像变成了

func runInCpu0() {
    flag = true
    a = 1
}

好像是被重新排序了，这其实是一种 伪重排序，必须提出新的办法来解决上面的问题

写屏障

CPU从软件层面提供了 写屏障(write memory barrier) 指令来解决上面的问题，linux将CPU写屏障封装为smp_wmb()函数。写屏障解决上面问题的方法是先将当前Store Buffer中的数据刷到cache后再执行屏障后面的写入操作。

SMP: Symmetrical Multi-Processing，即多处理器。

这里你可能好奇上面的问题是硬件问题，CPU为什么不从硬件上自己解决问题而要求软件开发者通过指令来避免呢？其实很好回答：CPU不能为了这一个方面的问题而抛弃Store Buffer带来的巨大性能提升，就像CPU不能因为分支预测错误会损耗性能增加功耗而放弃分支预测一样。

还是以上面的代码为例，前提保持不变，这时我们加入写屏障：

a = 0
flag = false
func runInCpu0() {
    a = 1
    smp_wmb()
    flag = true
}

func runInCpu1() {
    while (!flag) {
   	continue
    }
    print(a)
}

当cpu0执行flag=true时，由于Store Buffer中有a=1还没有刷到cache上，所以会先将a=1刷到cache之后再执行flag=true，当cpu1读到flag=true时，a也就=1了。

有文章指出CPU还有一种实现写屏障的方法：CPU将当前store buffer中的条目打标，然后将屏障后的“写入操作”也写到Store Buffer中，cpu继续干其他的事，当被打标的条目全部刷到cache中，之后再刷后面的条目。

Invalid Queue

上文通过写屏障解决了伪重排序的问题后，还要思考另一个问题，那就是Store Buffer size是有限的，当Store Buffer满了之后CPU还是要卡住等待Invalidate ACK。Invalidate ACK耗时的主要原因是CPU需要先将自己cacheline状态修改I后才响应ACK，如果一个CPU很繁忙或者处于S状态的副本特别多，可能所有CPU都在等它的ACK。

CPU优化这个问题的方式是搞一个Invalid Queue，CPU先将Invalidate消息放到这个队列中，接着就响应Invalidate ACK。然而这又带来了新的问题，还是以上面的代码为例

a = 0
flag = false
func runInCpu0() {
    a = 1
    smp_wmb()
    flag = true
}

func runInCpu1() {
    while (!flag) {
   	continue
    }
    print(a)
}

我们假设a在CPU0和CPU1中，且状态均为S，flag由CPU0独占

1. CPU0执行a=1，因为a状态为S，所以它将a=1写入Store Buffer，并发出Invalidate a消息
2. CPU1执行while(!flag)，由于其cache中没有flag，所以它发出Read flag消息
3. CPU1收到CPU0的Invalidate a消息，并将此消息写入了Invalid Queue，接着就响应了Invlidate ACK
4. CPU0收到CPU1的Invalidate ACK后将a=1刷到cache中，并将其状态修改为了M
5. CPU0执行到smp_wmb()，由于Store Buffer此时为空所以就往下执行了
6. CPU0执行flag=true，因为flag状态为E，所以它直接将flag=true写入到cache，状态被修改为了M
7. CPU0收到了Read flag消息，因为它cache中有flag，因此它响应了Read Response，并将状态修改为S
8. CPU1收到Read flag Response，此时flag=true，所以结束了while循环
9. CPU1打印a，由于a存在于它的cache中且状态为S，所以直接将cache中的a打印出来了，此时a=0，这显然发生了错误。
10. CPU1这时才处理Invalid Queue中的消息将a状态修改为I，但为时已晚

为了解决上面的问题，CPU提出了读屏障指令，linux将其封装为了smp_rwm()函数。放到我们的代码中就是这样：

...
func runInCpu1() {
    while (!flag) {
   	continue
    }
    smp_rwm()
    print(a)
}

当CPU执行到smp_rwm()时，会将Invalid Queue中的数据处理完成后再执行屏障后面的读取操作，这就解决了上面的问题了。

除了上面提到的读屏障和写屏障外，还有一种全屏障，它其实是读屏障和写屏障的综合体，兼具两种屏障的作用，在linux中它是smp_mb()函数。 文章开始提到的LOCK指令其实兼具了内存屏障的作用。

几个问题

问题1: CPU采用MESI协议实现缓存同步，为什么还要LOCK

答： 1. MESI协议只维护缓存一致性，与可见性有关，与原子性无关。一个非原子性的指令需要加上lock前缀才能保证原子性。

问题2: 一条汇编指令是原子性的吗

1. read-modify-write 内存的指令不是原子性的，以INC mem_addr为例，我们假设数据已经缓存在了cache上，指令的执行需要先将数据从cache读到执行单元中，再执行+1，然后写回到cache。
2. 对于没有对齐的内存，读取内存可能需要多次读取，这不是原子性的。（在某些CPU上读取未对齐的内存是不被允许的）
3. 其他未知原因…

问题3: Go中的原子读

我们看一个读取8字节数据的例子，直接看golang atomic.LoadUint64()汇编：

// uint64 atomicload64(uint64 volatile* addr);
1. TEXT runtime∕internal∕atomic·Load64(SB), NOSPLIT, $0-12
2.	MOVL	ptr+0(FP), AX // 将第一个参数加载到AX寄存器
3.	TESTL	$7, AX // 判断内存是否对齐
4.	JZ	2(PC) // 跳到这条指令的下两条处，即跳转到第6行
5.	MOVL	0, AX // crash with nil ptr deref 引用0x0地址会触发错误
6.	MOVQ	(AX), M0 // 将内存地址指向的数据加载到M0寄存器
7.	MOVQ	M0, ret+4(FP) // 将M0寄存器中数据(即内存指向的位置)给返回值
8.	EMMS // 清除M0寄存器
9.	RET

第3行TESTL指令对两个操作数按位与，如果结果为0，则将ZF设置为1，否则为0。所以这一行其实是判断传进来的内存地址是不是8的整数倍。

第4行JZ指令判断如果ZF即零标志位为1则执行跳转到第二个操作数指定的位置，结合第三行就是如果传入的内存地址是8的整数倍，即内存已对齐，则跳转到第6行，否则继续往下执行。

关于内存对齐可以看下我这篇文章：理解内存对齐 。

虽然MOV指令是原子性的，但是汇编中貌似没有加入内存屏障，那Golang是怎么实现可见性的呢？我这里也并没有完全的理解，不过大概意思是Golang的atomic会保证顺序一致性，详情可看下这篇文章：Memory Order Guarantees in Go。

问题4：Go中的原子写

仍然以写一个8字节数据的操作为例，直接看golang atomic.LoadUint64()汇编：

TEXT runtime∕internal∕atomic·Store64(SB), NOSPLIT, $0-16
	MOVQ	ptr+0(FP), BX
	MOVQ	val+8(FP), AX
	XCHGQ	AX, 0(BX)
	RET

虽然没有LOCK指令，但XCHGQ指令具有LOCK的效果，所以还是原子性而且可见的。

总结

这篇文章花费了我大量的时间与精力，主要原因是刚开始觉得原子性只是个小问题，但是随着不断的深入挖掘，翻阅无数资料，才发现底下潜藏了无数的坑。

由于精力原因本文还有一些很重要的点没有讲到，比如acquire/release 语义等等。

另外客观讲本文问题很多，较真的话可能会对您造成一定的困扰，建议您可以将本文作为您研究计算机底层架构的一个契机，自行研究这方面的技术。

参考资料

• 内存屏障的来历
• MESI协议 - 维基百科，自由的百科全书
• c++ - Does golang atomic.Load have a acquire semantics? - Stack Overflow
• golang-notes/memory_barrier.md at master · cch123/golang-notes · GitHub
• Memory Order Guarantees in Go

先说结论

• uintptr 是一个地址数值，它不是指针，与地址上的对象没有引用关系，垃圾回收器不会因为有一个uintptr类型的值指向某对象而不回收该对象。
• unsafe.Pointer是一个指针，类似于C的void *，它与地址上的对象存在引用关系，垃圾回收器会因为有一个unsafe.Pointer类型的值指向某对象而不回收该对象。
• 任何指针都可以转为unsafe.Pointer
• unsafe.Pointer可以转为任何指针
• uintptr可以转换为unsafe.Pointer
• unsafe.Pointer可以转换为uintptr
• 指针不能直接转换为uintptr

为什么需要uintptr这个类型呢？

理论上说指针不过是一个数值，即一个uint，但实际上在go中unsafe.Pointer是不能通过强制类型转换为一个uint的，只能将unsafe.Pointer强制类型转换为一个uintptr。

var v1 float64 = 1.1
var v2 *float64 = &v1
_ = int(v2) // 这里编译报错：cannot convert unsafe.Pointer(v2) (type unsafe.Pointer) to type uint

但是可以将一个unsafe.Pointer强制类型转换为一个uintptr：

var v1 float64 = 1.1
var v2 *float64 = &v1
var v3 uintptr = uintptr(unsafe.Pointer(v2))
v4 := uint(v3)
fmt.Println(v3, v4) // v3和v4打印出来的值是相同的

可以理解为uintptr是专门用来指针操作的uint。 另外需要指出的是指针不能直接转为uintptr，即

var a float64
uintptr(&a) 这里会报错，不允许将*float64转为uintptr

一个🌰

通过上面的描述如果你还是一头雾水的话，不妨看下下面这个实际案例：

package foo

type Person struct {
	Name string
	age  int
}

上面的代码中我们在foo包中定义了一个结构体Person，只导出了Name字段，而没有导出age字段，就是说在另外的包中我们只能直接操作Person.Name而不能直接操作Person.age，但是利用unsafe包可以绕过这个限制使我们能够操作Person.age。

package main

func main() {
	p := &foo.Person{
		Name: "张三",
	}

	fmt.Println(p)
	// *Person是不能直接转换为*string的，所以这里先将*Person转为unsafe.Pointer，再将unsafe.Pointer转为*string
	pName := (*string)(unsafe.Pointer(p)) 
	*pName = "李四"

	// 正常手段是不能操作Person.age的这里先通过uintptr(unsafe.Pointer(pName))得到Person.Name的地址
	// 通过unsafe.Sizeof(p.Name)得到Person.Name占用的字节数
	// Person.Name的地址 + Person.Name占用的字节数就得到了Person.age的地址，然后将地址转为int指针。
	pAge := (*int)(unsafe.Pointer((uintptr(unsafe.Pointer(pName)) + unsafe.Sizeof(p.Name))))
	// 将p的age字段修改为12
	*pAge = 12

	fmt.Println(p)
}

打印结果为：

$ go run main.go
&{张三 0}
&{李四 12}

需要注意的是下面这段代码比较长：

pAge := (*int)(unsafe.Pointer((uintptr(unsafe.Pointer(pName)) + unsafe.Sizeof(p.Name))))

但是尽量不要分成两段代码，像这样：

temp := uintptr(unsafe.Pointer(pName)) + unsafe.Sizeof(p.Name))
pAge := (*int)(unsafe.Pointer(temp)

原因是在第二行语句时，已经没有指针指向p了，这时p可能会回收掉了，这时得到的地址temp就是个野指针了，不知道指向谁了，是比较危险的。

另外一个原因是在当前Go（golang版本：1.14）的内存管理机制中不会迁移内存，但是不保证以后的版本内存管理机制中有迁移内存的操作，一旦发生了内存迁移指针地址发生变更，上面的分段代码就有可能出现严重问题。

关于Go的内存管理可以参看这篇文章：https://draveness.me/golang/docs/part3-runtime/ch07-memory/golang-memory-allocator/，读完这篇文章相信你就能理解上面的内存迁移问题。

除了上面两点外还有一个原因是在Go 1.3上，当栈需要增长时栈可能会发生移动，对于下面的代码：

var obj int
fmt.Println(uintptr(unsafe.Pointer(&obj)))
bigFunc() // bigFunc()增大了栈
fmt.Println(uintptr(unsafe.Pointer(&obj)))

完全有可能打印出来两个地址。

通过上面的例子应该明白了为什么这个包名为unsafe，因为使用起来确实有风险，所以尽量不要使用这个包。

我之所以研究unsafe.Pointer完全是因为我要在多线程的环境中采用原子操作避免竞争问题，所以我用到了atomic.LoadPointer(addr *unsafe.Pointer)。不过我后面发现了atomic包提供了一个atomic.Value结构体，这个结构体提供的方法使我避免显式使用了unsafe.Pointer。所以你也正在使用atomic.LoadPointer()不妨看看atomic.Value是不是可以解决你的问题，这是我一点提醒。

参考资料

• Go语言实战笔记（二十七）| Go unsafe Pointer
• garbage collection - Does Go guarantee constant addresses? - Stack Overflow

一、CPU 缓存架构

现代多核CPU会在每个核心上加上一个较小的SRAM高速缓存存储器称为：L1高速缓存，其中L1缓存由分为dcache数据缓存，icache指令缓存。在L1缓存的下级加一个较大的L2高速缓存， 然后会再L2之下加一个多核共享的L3高速缓存。它们之间的逻辑结构大概是这样的：

相较于访问CPU高速缓存来说访问主存简直太慢了，Jeff Dean曾给出过这样一组数字：

• L1缓存访问时间 0.5ns
• 分支预测错误 5ns
• L2缓存访问时间 7ns
• 主存访问 100ns

https://colin-scott.github.io/personal_website/research/interactive_latency.html 给出了不同年份这些指标的数字，

1.1 通用的高速缓存存储器结构

告诉缓存被划分为S = 2 ^ s个高速缓存组(cache set),每个组含有E个高速缓存行(cache line)，每个行又由B = 2 ^ b个字节的数据块(block)和有一个标识该行是否有效(即是否已过期或者已修改)的有效位(valid bit),以及t个标记位(tag bit)组成。物理结构大概是下图这样：

高速缓存的大小指的是所有数据块的大小的和，即：B * E * S。

假设当前CPU地址总线有m位，从而主存有M=2^m个地址，所以每个内存地址会有m位。当CPU需要从主存加载地址为A的内存块上的字节时，会先从CPU高速缓存中获取，这时候问题来了，应该到高速缓存的什么位置去拿呢？实际上会将m位地址A划分为以下几段：

这里的m、t、b、s都是二进制数，不要想成十进制数哦

从而有m = t + b + s CPU会根据A地址中间的s位定位主存地址A映射到了哪个组中，然后根据开头的t位与组内的E个行的标记位挨个比对以确认地址A映射到了哪一行(这里有文章说是并行查询)，这时会检查该行的有效位标识该行是否有效，如果有效的话最后根据后b位就直接定位主存地址A映射到了数据块中的哪个字节上了。如果通过以上的步骤没有找到对应的高速缓存地址的话，高速缓存会向主存请求包含A地址的数据块的一个拷贝，CPU必须等待，当被请求的块到达高速缓存中时高速缓存会将这个块放到对应的位置上，然后从数据块中抽取出A地址上的字节返回给CPU。注意：高速缓存从主存中一次请求的是一个数据块而非具体地址上的一个字节，这非常关键！

CSAPP书中提到了为什么选择中间位作为组索引位，其大概意思是选择中间位能够使连续内存映射到不同的组上，提高高速缓存利用率并且减小冲突覆盖的问题，但是个人感觉其解释是按照特定平台来描述的，并没有普适所有平台，这里就不以我昏昏使你昭昭了，待后续查阅更加合理的解释再说。

根据E的不同我们将高速缓存划分为以下三类：

• 直接映射高速缓存
• 组相连高速缓存
• 全相连高速缓存

1.2 直接映射高速缓存

每组只有一行即E=1的高速缓存称为直接映射高速缓存。这种缓存一旦定位到了组后就无需查询对应行了。

1.2.1 直接映射高速缓存的冲突不命中

假设当前计算机b=16即数据块为16个字节，高速缓存中有两个组，s=5即内存地址的第5位决定内存地址映射到哪个组上，有下面的一段golang代码

func foo(x [8]int32, y [8]int32) int32 {
	var sum int32 = 0
	for i := 0; i < 8; i++ {
		sum += x[i] * y[i]
	}

	return sum
}

上面的程序中x与y占用了8 * 4 = 2 ^ 5 = 32个字节，假设x被加载到地址为0-31的内存之中，y被加载到32-63之中，sum存在于寄存器中，不占用内存地址。如下图所示 运行时，第一次循环中，CPU需要先加载x[0]，由于高速缓存中一开始并没有，所以会从主存中加载x[0]-x[3]共16个字节（数据块的大小）的数据到高速缓存的组0中再返回给CPU，接下来同样的道理会将y[0]-y[3]加载到高速缓存的组0中。这时候由于每组只有一个行就导致了上一步加载进来的x[0]-x[3]被覆盖了，下一次循环中要加载x[1]时，x[1]就不在高速缓存中了，所以又必须去内存中加载一次，结果从内存中加载会的数据又把第二次加载进来的y[0]-y[3]给覆盖了，之后的每次循环都存在这个问题，导致每次都回冲突不命中。这种高速缓存反复地加载和驱逐相同的高速缓存块的组的情况称为抖动(thrash)。

为了解决这个问题我们可以将x和y两个数组的长度定为12，即：

func foo(x [12]int32, y [12]int32) int32

这样的话再看下分布情况：

这样的话由于y[0]-y[3]与x[0]-x[3]不在一个组上就不会出现抖动问题了。

1.3 组相联高速缓存

组相联高速缓存每组中有多个行。

1.4 全相联高速缓存

全相联高速缓存只有一个组。

1.5 写的问题

如果CPU要写一个已经缓存了的字时，有两种方法将该数据写到下层缓存中： 1. 直写，最简单的一种方法，直接将数据写入到下层缓存。但是这种方案每次写都回引起总线流量 2. 写回，为每个行单独维护一个修改位dirty bit，标识这个缓存块被修改过，只有当替换算法要驱逐更新过的块时才将它写入到下一层缓存中。

写不命中通常有两种方法： 1. 写分配，加载低一层的缓存到高速缓存中，然后更新这个数据块。缺点是每次不命中都会导致一个块从低一层传送到高速缓存。 2. 非写分配，避开高速缓存，直接把这个数据写入到低一层中。

直写通常是非写分配的，写会通常是写分配的。

二、伪共享False Sharing

通过上文了解CPU的缓存结构后我们做一个实验来引出伪共享的问题，实验前我们先看下实验机器的一些信息。Mac上通过sysctl -a查看机器信息，这里我过滤了下只拿出来与此实验相关的一些机器指标:

hw.cachelinesize: 64 // Cacheline 64字节
hw.l1icachesize: 32768
hw.l1dcachesize: 32768 // L1数据缓存32K
hw.l2cachesize: 262144 // L2缓存256K
hw.l3cachesize: 6291456 // L3缓存6M
machdep.cpu.core_count: 4 // 4核
machdep.cpu.thread_count: 8

现在我们定义一个程序，有2个线程，两个变量a和b，线程1循环n次执行a++操作，线程2执行n次b++操作，我们用Go来描述：

type SimpleStruct struct {
	n int32
}

type PaddedStruct struct {
	n int32
	_ CacheLinePad
}

type CacheLinePad struct {
	_ [CacheLinePadSize]byte
}

const CacheLinePadSize = 64

const Num = 10000000

func BenchmarkSimple(b *testing.B) {
	structA := SimpleStruct{}
	structB := SimpleStruct{}
	wg := sync.WaitGroup{}

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		wg.Add(2)
		go func() { // 为方便下文描述这个线程称为structA线程
			var j int32
			for j = 0; j < Num; j++ {
				structA.n += j
			}
			wg.Done()
		}()
		go func() { // 为方便下文描述这个线程称为structB线程
			var j int32
			for j = 0; j < Num; j++ {
				structB.n += j
			}
			wg.Done()
		}()
		wg.Wait()
	}
}

func BenchmarkSimplePad(b *testing.B) {
	structB := SimpleStruct{}
	structA := PaddedStruct{}
	wg := sync.WaitGroup{}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		wg.Add(2)
		go func() {
			var j int32
			for j = 0; j < Num; j++ {
				structA.n += j
			}
			wg.Done()
		}()
		go func() {
			var j int32
			for j = 0; j < Num; j++ {
				structB.n += j
			}
			wg.Done()
		}()
		wg.Wait()
	}
}

运行benchmark go test -bench=. 得到以下结果 可以看到我们只在结构体中加入了一个64字节的元素性能就得到了极大的提高，这是为什么呢？

我们看下Simple这个函数的代码，假设structA线程运行在core1上，structB线程运行在core2s上，假设structA线程先执行，它会将structA这个变量与structB一起加载到core1的L1的同一cacheline中，structB线程也会将structA这个变量与structB一起加载到core2的L1的同一cacheline，structA线程修改了structA的值，它会将这个事件同步到core2上，导致core2上cacheline失效，这时就需要从低一层存储中加载最新数据，然后structB又修改了structB，又导致了cacheline失效，循环往复导致了运行效率极低。

而SimplePad这个函数中structA中加入了cachelinesize个字节，使得structA和structB处于不同的cacheline上，也就避免了上面的问题。

2.1 题外话

1. 关于多核间同步缓存我没有查到特别好的文章，所以我就不妄加解释了，如果你想深入研究的话可以搜索这个关键词：MESI协议
2. 上面的实验代码来自于【译】CPU 高速缓存原理和应用。最初在我在做这个实验时，写的实验代码是这样的： var a int32 var pad [64]byte{} var b int32 ...

运行benchmark后发现运行时间并没有缩短，后来获取了a、pad、b的地址后才发现go将pad这个变量分配到了堆上，a和b两个变量在内存上还是紧挨着的，你做实验的话可以吸收这个经验：如果加上pad后发现运行时间没有缩短的话确认下a和b是不是真的被分隔到了两个cacheline上。

参考资料

• 深入理解计算机系统
• Numbers Everyone Should Know
• Go and CPU Caches
• 【译】CPU 高速缓存原理和应用

相信大家都听说过内存对齐的概念，不过这里还是通过一个现象来引出本篇话题。

一、求一个结构体的size

猜下下面这个结构体会占用多少字节

type S struct {
    B byte  // Go中一个byte占1字节，int32占4个字节，int64占8个字节
    I64 int64
    I32 int32
}

是不是以为是1+8+4 = 13个字节？写段代码验证下：

type S struct {
	B   byte
	I64 int64
	I32 int32
}

func main() {
	s := S{}
	fmt.Printf("s size:%d\n", unsafe.Sizeof(s))
}

输出：

s size:24

与预想显然不同，这是为什么呢？答案是编译器替我们做了内存对齐。

二、什么是内存对齐

要理解这个问题需要先了解一下字长的概念以及内存的物理结构

2.1 字长

在计算器领域，对于某种特定的计算机设计而言，字（word）是用于表示其自然的数据单位的术语。在这个特定计算机中，字是其用来一次性处理事务的一个固定长度的位（bit）组。一个字的位数即为字长。

字长在计算机结构和操作的多个方面均有体现，计算机中大多数寄存器（这里应该是指通用寄存器）的大小是一个字长。

上面这段话可能太过于概念化不太好理解，那么请看下面的这段64位机器上的GUN汇编器语法的汇编代码：

movq (%ecx) %eax

这段汇编代码是将eax这个寄存器中的数据作为地址访问内存，并将内存中的数据加载到eax寄存器中。

我们可以看到mov指令的后缀是q，意味着该指令将加载一个64位的数据到eax寄存器中，这样一条指令可以操作一个64位的数据，说明该机器的字长为64位，同时这段代码能够执行则说明我们机器上的CPU中的eax寄存器必定是64位的，而一条指令能够从内存中加载一个64位的数据也说明了数据总线的位宽也为64位，说明了我们的CPU可以一次从内存中加载8个字节的数据。

2.2 64位内存物理结构

内存是由若干个黑色颗粒组成的，每个内存颗粒叫做一个chip，每个chip是由8个bank组成，每个bank是二维平面上的矩阵，矩阵中的每个元素保存1个字节也就是8个bit。

对于内存中连续的8个字节比如0x0000-0x0007，并非位于一个bank上，而是位于8个bank上，每个bank保存一个字节，8个bank像是垂直叠在一起，物理上它们并不是连续的。 之所以这样设计是基于电路工作效率考虑，这样的设计可以并行取8个字节的数据，如果想取址0x0000-0x0007，每个bank只需要工作一次就可以取到，IO效率比较高，如果这8个字节在同一个bank上则需要串行读取该bank8次才能取到。

结合上面的结构图可以看到0x0000-0x0007是一列，0x0008-0x000F是另外一列，如果从内存中取8-15字节的数据也可以一次取出来，但如果我们要取1-9的数据就需要先取0-7的数据，再取8-15的数据然后拼起来，这样的话就会产生两次内存IO。所以基于性能的考虑某些CPU会强制只能读取8的倍数的内存，而这也导致了编译器再此类平台上编译时必须做内存对齐。

2.3 Cacheline

CPU通常会将Cacheline size个字节一次加载到高速缓存中(即L1、L2、L3缓存)。 这部分内容我后续会写一篇博客专门介绍下CPU高速缓存结构。

2.4 再来看结构体size的问题

以下均以64位平台，即：64位宽内存以及64位cpu(数据总线64位，寄存器64位)、cacheline size=64byte为前提

type S struct {
    B byte
    I64 int64
    I32 int32
}

在不了解内存对齐前我们可能会简单以为结构体在内存中可能是这样排列的： 总共占用13个字节。我们可以看到 I64 这个字段的内存地址是1-8，而在64位平台上为了将这个字段加载到寄存器中，CPU需要两次内存IO。
但做内存对齐后： 总共占用20个字节，I64这个字段的内存地址是8-15，为了将这个字段加载到寄存器中，只需要一次内存IO即可。 我们写段代码验证下是否真的占用了20个字节：

type S struct {
	B   byte
	I64 int64
	I32 int32
}

func main() {
	s := S{}
	fmt.Printf("s size: %d, align: %d\n", unsafe.Sizeof(s), unsafe.Alignof(s))
}

输出：

s size: 24, align: 8

程序输出了24，而非上面我们以为的20，这是怎么回事呢？原因是结构体本身也必须要做对齐，它必须在后面再额外占用4个字节以使自己的size为8的倍数。

上面的结构体如果后面跟一个4字节的变量的话理论上说不用对齐也能保证一次内存IO就可加载，所以结构体对齐的根本原因目前我还不是特别能理解，可能为编译器做的优化，了解的同学欢迎在评论区指点一下

我们再调整下结构体的声明：

type S struct {
    B byte
    I32 int32
    I64 int64
}

再做内存对齐的话该结构体在内存中应该就是下面这个样子了： 这时总共占用16个字节，相比较上面我们节省了8个字节。 写段代码验证下：

type S struct {
	B   byte
	I32 int32
	I64 int64
}
func main() {
	s := S{}
	fmt.Printf("s size:%v, s.B地址:%v, s.I32地址:%v, s.I64地址:%v\n", unsafe.Sizeof(s), &s.B, &s.I32, &s.I64)
}

输出结果:

s size:16, s.B地址:0xc0000b4010, s.I32地址:0xc0000b4014, s.I64地址:0xc0000b4018

确实占用了16字节，但貌似I32这个字段跟我们预想的不太一样，它被对齐到了4的倍数地址上，而非紧跟在B后边，这大概是编译器编译一套代码可以运行在32位又可以运行在64位平台上吧，目前没有查到相关资料姑且这么认为吧。

参考资料

字 (计算机))

带你深入理解内存对齐最底层原理

通过go mod download下载公司gitlab仓库代码时提示unknown revision 由于是私有仓库且回车执行命令后并没有输入密码的提示，所以猜测是go mod download时git clone 没有输入密码提示

一番搜索后发现解决方案如下：

// 设置永久存储账号密码
git config credential.helper store
// git pull过程中允许输入用户名密码
export GIT_TERMINAL_PROMPT=1