> ## Content Index > Fetch the complete content index at: https://blog.hacking.pub/llms.txt > Use this file to discover other available public pages before exploring further. # go源码阅读 map - URL: https://blog.hacking.pub/2019/07/21/goyuan-ma-map/ - Published: 2019-07-21T12:43:43.000Z - Updated: 2019-07-21T12:43:43.000Z - Author: chainhelen - Tags: go, go语言, golang, 源码剖析, map, hmap, go源码 #### 序 关于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](./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](https://blog.hacking.pub/qiniu/go%E6%BA%90%E7%A0%81%E9%98%85%E8%AF%BB%20map/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](https://blog.hacking.pub/qiniu/go%E6%BA%90%E7%A0%81%E9%98%85%E8%AF%BB%20map/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`是可以的