go

go源码阅读 map

chainhelen

— 阅读时间 11 分钟
分享
go源码阅读 map

序

关于map的实现，我按照我的思路来看源码，中间尝试了挺多的case，最终选了一些来作为实例
可能跟网上其他人不太一样　

准备工作

首先做一些准备工作，跳过一下与编译无关的过程，例如搜索依赖关系　　　

  1. 样例代码
    新建临时目录test_map，在该目录下写入样例代码
// main.go
package main

import (
	"fmt"
)

func test_map() {
	s := make(map[string]int, 3)

	s["chainhelen1"] = 1000
	s["chainhelen2"] = 2000
	s["chainhelen3"] = 3000

	fmt.Printf("chainhelen1 %d\n", s["chainhelen1"])
	fmt.Printf("chainhelen2 %d\n", s["chainhelen2"])
	fmt.Printf("chainhelen3 %d\n", s["chainhelen3"])
}

func main() {
	test_map()
}

  1. importcfg

    新建文件importcfg，内容如下

    # import config
packagefile fmt=/usr/local/go/pkg/linux_amd64/fmt.a
packagefile runtime=/usr/local/go/pkg/linux_amd64/runtime.a

    为了最终可以link成可执行文件，新增文件.link

    packagefile command-line-arguments=$WORK/b001/_pkg_.a
packagefile fmt=/usr/local/go/pkg/linux_amd64/fmt.a
packagefile runtime=/usr/local/go/pkg/linux_amd64/runtime.a
packagefile errors=/usr/local/go/pkg/linux_amd64/errors.a
packagefile internal/fmtsort=/usr/local/go/pkg/linux_amd64/internal/fmtsort.a
packagefile io=/usr/local/go/pkg/linux_amd64/io.a
packagefile math=/usr/local/go/pkg/linux_amd64/math.a
packagefile os=/usr/local/go/pkg/linux_amd64/os.a
packagefile reflect=/usr/local/go/pkg/linux_amd64/reflect.a
packagefile strconv=/usr/local/go/pkg/linux_amd64/strconv.a
packagefile sync=/usr/local/go/pkg/linux_amd64/sync.a
packagefile unicode/utf8=/usr/local/go/pkg/linux_amd64/unicode/utf8.a
packagefile internal/bytealg=/usr/local/go/pkg/linux_amd64/internal/bytealg.a
packagefile internal/cpu=/usr/local/go/pkg/linux_amd64/internal/cpu.a
packagefile runtime/internal/atomic=/usr/local/go/pkg/linux_amd64/runtime/internal/atomic.a
packagefile runtime/internal/math=/usr/local/go/pkg/linux_amd64/runtime/internal/math.a
packagefile runtime/internal/sys=/usr/local/go/pkg/linux_amd64/runtime/internal/sys.a
packagefile sort=/usr/local/go/pkg/linux_amd64/sort.a
packagefile sync/atomic=/usr/local/go/pkg/linux_amd64/sync/atomic.a
packagefile math/bits=/usr/local/go/pkg/linux_amd64/math/bits.a
packagefile internal/poll=/usr/local/go/pkg/linux_amd64/internal/poll.a
packagefile internal/syscall/unix=/usr/local/go/pkg/linux_amd64/internal/syscall/unix.a
packagefile internal/testlog=/usr/local/go/pkg/linux_amd64/internal/testlog.a
packagefile syscall=/usr/local/go/pkg/linux_amd64/syscall.a
packagefile time=/usr/local/go/pkg/linux_amd64/time.a
packagefile unicode=/usr/local/go/pkg/linux_amd64/unicode.a
packagefile internal/race=/usr/local/go/pkg/linux_amd64/internal/race.a

    得到这些文件的方式很简单，只需要在go build的时候多加一个 -x 参数，就能知道中间的过程了并且得到中间临时文件的内容

  2. ssa.html

    这个可以提前生成一下，作为一些辅助信息查看　

    GOSSAFUNC=test_map /usr/local/go/pkg/tool/linux_amd64/compile -o ./_pkg_.a ./main.go

    抽象语法树

    对于源码来说，编译器前端部分比较关心的是生成抽象语法树是长什么样的　　

    有三种方式：

    1. 用goland调试go/src/cmd/compile，配置之前文章有，断点下在lines := parseFiles(flag.Args())之后，查看xtop变量
    2. 生成ssa.html，就是/usr/local/go/pkg/tool/linux_amd64/compile-o ./_pkg_.a ./main.go加上GOSSAFUN=test_map
    3. 打印出来抽象语法树， /usr/local/go/pkg/tool/linux_amd64/compile-o ./_pkg_.a ./main.go的时候加上-W参数

    不过2、3方法看到是已经处理过的ast，可以看到源码中s := make(map[string]int ,3)已经变成了初始化buckets

    断点方式// Phase 3: Type check function bodies.，使用第一种断点方法看一下Phase 3之前的ast

    xtop.Nbody.slice[0].Right.Left 这个节点对应源码中"make"这个关键词
Op 值为 ONONAME(2)
Sym.Name 值为 "make"

    Phase 3之后的ast 已经没有了以上节点，对应Node变成了

    xtop.Nbody.slice[0].Right 这个节点对应源码中"make"这个关键词
Op 值为　OMAKEMAP (72)

    也就是是说在类型检查的时候，对于关键词make就会变成对应的类型的操作节点类型

    make(map) 对应 OMAKEMAP;make(chan) 对应 OMAKECHAN;make([]) 对应 OMAKESLICE

具体代码流程可以看这

map_compile.svg

实现

接下来看一下map的实现（具体怎么和运行时关联上的，还没有深入理解）

上图最右下角的地方，显示了hmapType := hmap(t)这个就是编译期间长得样子　　

// hmap builds a type representing a Hmap structure for the given map type.
// Make sure this stays in sync with runtime/map.go.
func hmap(t *types.Type) *types.Type {
...
	fields := []*types.Field{
		makefield("count", types.Types[TINT]),
		makefield("flags", types.Types[TUINT8]),
		makefield("B", types.Types[TUINT8]),
		makefield("noverflow", types.Types[TUINT16]),
		makefield("hash0", types.Types[TUINT32]), // Used in walk.go for OMAKEMAP.
		makefield("buckets", types.NewPtr(bmap)), // Used in walk.go for OMAKEMAP.
		makefield("oldbuckets", types.NewPtr(bmap)),
		makefield("nevacuate", types.Types[TUINTPTR]),
		makefield("extra", types.Types[TUNSAFEPTR]),
	}
...
}

可以看到编译期间的map结构体类型是动态构造出来的，而且注释上明确写了需要与runtime/map.go同步

那么具体看一下 runtime/map.go的实现 ，核心结构如下

// A header for a Go map.
type hmap struct {
   count     int    // 等于当前 map 已经存储的元素个数
   flags     uint8  // 标志位，例如如果当前 map 正在写 h.flags&hashWriting == 1
   　　　　　　　　　  // 并发写的 panic 也是利用这个标志位查出来的
   B         uint8  // 2^B 代表 buckets 数量 
                    // 整个 map最多能容纳 6.5 * 2^B 个元素，13/2=6.5是装载因子
   noverflow uint16 // 大致上溢出的bucket数量，目前我还不清楚保留这个是干嘛的
   hash0     uint32 // hash种子，会让数据的key值更加随机化
   buckets    unsafe.Pointer // 2^B Buckets个数组，当count = 0时该值可能为零
   oldbuckets unsafe.Pointer // 旧buckets的大小，当扩容时候非nil
   nevacuate  uintptr        // 扩容时候的搬迁进度，小于该值的buckets说明数据已经搬迁完成

   extra *mapextra // 可配置的，目前我也不清楚这个是干嘛的
}

上面属性buckets中每一个元素bucket对应如下结构，同样在runtime/map.go文件中

// A bucket for a Go map.
type bmap struct {
	// bucketCnt=1<<3=8，tophash是8个字节大小
	// tophash代表了当前bucket中每个元素key的hash高８位
	
　　 // 如果tophash[0] < minTopHash（默认为5，对应有个func tophash代码可知正常一定大于5)
　　 // 那么tophash[i]就代表了bucket中第i个key的tophash
	tophash [bucketCnt]uint8
	
	// 紧接着就是8个key，和8个values值，大概长这样
	// [k1][k2]..[k8][v1][v2]...[v8]
	
	//　再接着就是溢出bmap的指针
}

上面的结构定义不完整，剩余的部分在上面注释中，而实际的在编译过程中，完成的结构代码是在上图bmap := bmap(t) 完成的

func bmap(t *types.Type) *types.Type {
...
	keys := makefield("keys", arr)
...
	values := makefield("values", arr)
...
	overflow := makefield("overflow", otyp)
...
}

大概最终形成在内存中的长得样子

map_compile2.svg

注释

放在最后是因为我做了核心函数的代码细节注释，如果只是想理解大致实现，没有必要看最后的部分

而且源码的注释写得很清楚，大部分我只是做一些简单翻译

初始化
// 正常初始化map的代码，hint是只是make传入的大小（注意这里影响的是bucket数量，而不是容纳元素数量）
// 如果编译器发现当前的map可以直接使用栈内存，那么参数传入的h *hmap就是非空；否则h为nil，函数会将其创建在堆上面
func makemap(t *maptype, hint int, h *hmap) *hmap {
　　// 计算用户传入的make大小会使用多大内存，如果太大的，直接将其值置为零
	mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
	if overflow || mem > maxAlloc {
		hint = 0
	}

	// 如果 h *hmap为空就是在栈上；否则在堆上面创建
	if h == nil {
		h = new(hmap)
	}
	// hash种子
	h.hash0 = fastrand()

	// 主要保证 2^B * 6.5 >= hint
	// 2^B代表bucket数量，6.5是装载因子，保证有足够多的容量可以容纳所有容量
	B := uint8(0)
	for overLoadFactor(hint, B) {
		B++
	}
	h.B = B

	// allocate initial hash table
	// if B == 0, the buckets field is allocated lazily later (in mapassign)
	// If hint is large zeroing this memory could take a while.
	
	// 如果 B == 0，buckets的内存懒分配，等到mapassign的时候分配
	if h.B != 0 {
		var nextOverflow *bmap
		// buckets 内存分配，nextOverflow 主要是提前分配好准备溢出的buckets
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
		if nextOverflow != nil {
			h.extra = new(mapextra)
			h.extra.nextOverflow = nextOverflow
		}
	}
	return h
}

对应上面代码分配内存的地方makeBucketArray

// dirtyalloc 是为了可以内存复用，对于上面的makemap来看，其实并没有复用
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
	if b >= 4 {
	    // 对于make(map)初始值大于 4（即2^4=16个buckets）
	    // 提前额外申请2^(b-4)个buckets作为Overflow
		nbuckets += bucketShift(b - 4)
		
		// 向上取整，这个主要为了方便内存管理，对齐go中内存的大小
		// 主要代码在 go/src/runtime/sizeclasses.go
		// class  bytes/obj  bytes/span  objects  tail waste  max waste
		//     1          8        8192     1024           0     87.50%
		//     2         16        8192      512           0     43.75%
		//     3         32        8192      256           0     46.88%
		//     4         48        8192      170          32     31.52%
		//     5         64        8192      128           0     23.44%
		//     6         80        8192      102          32     19.07%
		//     7         96        8192       85          32     15.95%
		//     8        112        8192       73          16     13.56%
		//     9        128        8192       64           0     11.72%
		up := roundupsize(sz)
	}

	// 分配内存
		buckets = newarray(t.bucket, int(nbuckets))

	if base != nbuckets {
		// 设置上面多申请的内存作为 overflow
		nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
		
		// 这个东西是为了让最后一个bucket的overflow，指向开头的bucket
		// 类似于起始亦结尾，蛇头咬蛇尾
		last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
		last.setoverflow(t, (*bmap)(buckets))
	}
	return buckets, nextOverflow
}
访问元素
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // 可以参照上面的流程，看到 b，是可能保存该数据的 bucket
    // 第一层遍历b、b后续overflow的bucket，第二层遍历bucket里面的所有的key
bucketloop:
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
	    ...
	            // 小对象value一点关系都没有
				if t.indirectvalue() {
					v = *((*unsafe.Pointer)(v))
				}
         ...
	}
}

这里有个很有趣的东西关于indirective()，如果出现value的值width很大，那么实际底层value存储的是指针

当出现map的value width过大，访问数据将不会调用直接调用mapcess1，而是调用mapaccess1_fat

这个 width 边界大小在 cmd/compile/internal/gc/reflect.go 定义的，MAXVALSIZE = 128　　

arr := [129]int{1}
mp := make(map[string][129]int)
mp["hello"] = arr
b := mp["hello"]

value 在底层被定义成指针代码 refect.go:1292，例如上面代码 访问mp["hello"] 就会调用 mapaccess1_fat

同样的key也有类似优化

这里面有个很容混淆的概念，如果map的value类型是指针，实际不会触发这种机制，因为指针在64位机器就是8字节的无符号整型

赋值
func mapassign(t *maptype, h *hmap, key unsafe.Point) {
    ...
    // 计算hash
    hash := alg.hash(key, uintptr(h.hash0))
    
    // 类似懒加载，上面初始化讲过
    if h.buckets == nil {
		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
	}
    ....
    
    // 取余数，因为 m % (2^N)等于 m & (2^N - 1)
    // 这个原理是因为2^N的二进制只有第N位是１，2^N-1末尾都是１
    bucket := hash & bucketMask(h.B)
    
    // 如果可以搬迁，那么进行一步搬迁工作
    if h.growing() {
		growWork(t, h, bucket)
	}
	
	// 找到对应的bucket插入位置 i，和原来的key，key对应的val（如果存在的话）
	var inserti *uint8
	var insertk unsafe.Pointer
	var val unsafe.Point
	
	// 都说`tophash`是为了快速是错，不知真假
	top := tophash(hash)
	for {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
			...
}

遗留

迭代器

这部分源码挺好读，就是编译进去的问题

迁移

只赋值并且该key不存在的情况下，才可能触发迁移hashGrow

一旦进入正在迁移状态，只有赋值、删除会发生迁移两组bucket迁移（也可能是一组，组就是上图上面的一列bmap）；第一组是当前所操作的key所在bucket，第二组是会做顺序bucket迁移（也就是小于nevacuate都说明已经迁移完成的原因）　

调试

dlv的调试是进不了runtime的源码中，而gdb是可以的

阅读更多