探索Go内存管理(分配)

基于1.8.3版本,64位Linux操作系统

1、概述

Go内存管理基于 tcmalloc,使用连续虚拟地址,以页(8k)为单位、多级缓存进行管理;

在分配内存时,需要对size进行对齐处理,根据best-fit找到合适的mspan,对未用完的内存还会拆分成其他大小的mspan继续使用

在new一个object时(忽略逃逸分析),根据object的size做不同的分配策略:

• 极小对象(size<16byte)直接在当前P的mcache上的tiny缓存上分配;
• 小对象(16byte <= size <= 32k)在当前P的mcache上对应slot的空闲列表中分配,无空闲列表则会继续向mcentral申请(还是没有则向mheap申请);
• 大对象(size>32k)直接通过mheap申请。

2、数据结构

2.1 mspan

mspan并不直接拥有内存空间,它负责管理起始地址为startAddr、级别(预分配页个数)为sizeclass的连续地址空间。

摘取重点内容(下同)
type mspan struct {
 //双向链表
 next *mspan 
 prev *mspan 
 //起始地址
 startAddr uintptr 
 //包含多少页
 npages uintptr 
 //
 stackfreelist gclinkptr 
 //有多少对象
 nelems uintptr 
 //gc相关
 sweepgen uint32
 //级别
 sizeclass uint8 
 //已被mcache使用
 incache bool 
 //状态
 state mSpanState
}

2.2 mcache

Go为Per-thread (in Go, per-P)分配了mcache管理结构,所以对其操作是不需要锁的,每个mcache有大小为67的mspan数组,存储不同级别大小的mspan

type mcache struct {
 tiny uintptr
 tinyoffset uintptr
 alloc [_NumSizeClasses]*mspan
 stackcache [_NumStackOrders]stackfreelist
 ...
}

2.3 mcentral

mcentral集中管理,当在mcache申请失败的时候,会向mcentral申请;mcentral有个关键方法cacheSpan(),它是整个分配的核心算法

type mcentral struct {
 lock mutex
 sizeclass int32
 nonempty mSpanList 
 empty mSpanList 
}

2.4 mheap

mheap是真实拥有虚拟地址的结构,同时拥有67个级别的mcentral,以及所有分配的mspan。

// _NumSizeClasses := 67
// _MaxMHeapList := 128
type mheap struct {
 lock mutex
 //size < 128 * 8k(1M)的可用mspanList
 free [_MaxMHeapList]mSpanList 
 //size >= 128 * 8k(1M)的可用mspanList
 freelarge mSpanList 
 busy [_MaxMHeapList]mSpanList 
 busylarge mSpanList 
 
 //gc相关
 sweepgen uint32 
 sweepdone uint32 
 //所有的mspan
 allspans []*mspan 
 //页到span的查找表
 spans []*mspan
 //位图
 bitmap uintptr 
 bitmap_mapped uintptr
 //真实申请的内存起始地址
 arena_start uintptr
 //真实申请的内存目前可用起始地址
 arena_used uintptr 
 //真实申请的内存结束地址
 arena_end uintptr
 //分级的mcentral
 central [_NumSizeClasses]struct {
 mcentral mcentral
 pad [sys.CacheLineSize]byte
 }
 ...
}

2.5 四者的关系示图

3、初始化

初始化时,Go向系统申请预留一段连续虚拟地址,大小(64位机器上)为512M(spans_mapped)+16G(bitmap_mapped)+512G(arena)

向系统申请预留的连续地址空间
+----------+-----------+-----------------------------+
| spans | bitmap | arena |
| 512M | 16G | 512G |
+----------+-----------+-----------------------------+

mheap的初始化在func mallocinit()中,而mallocinit被schedinit()调用
/src/runtime/proc.go

// The bootstrap sequence is:
//
// call osinit
// call schedinit
// make & queue new G
// call runtime·mstart
//
// The new G calls runtime·main.

mallocinit的逻辑为:

func mallocinit() {
 // 0. 检查系统/硬件信息,bala bala
 // 1. 计算预留空间大小
 arenaSize := round(_MaxMem, _PageSize)
 bitmapSize = arenaSize / (sys.PtrSize * 8 / 2)
 spansSize = arenaSize / _PageSize * sys.PtrSize
 spansSize = round(spansSize, _PageSize)
 // 2. 尝试预留地址(区分不同平台 略)
 for i := 0; i <= 0x7f; i++ {
 ...
 pSize = bitmapSize + spansSize + arenaSize + _PageSize
 p = uintptr(sysReserve(unsafe.Pointer(p), pSize, &reserved))
 }
 // 3. 初始化部分mheap中变量
 p1 := round(p, _PageSize)
 spansStart := p1
 mheap_.bitmap = p1 + spansSize + bitmapSize
 mheap_.arena_start = p1 + (spansSize + bitmapSize)
 mheap_.arena_end = p + pSize
 mheap_.arena_used = p1 + (spansSize + bitmapSize)
 mheap_.arena_reserved = reserved
 
 // 4. 其他部分初始化,67个mcentral在这里初始化
 mheap_.init(spansStart, spansSize)
 _g_ := getg()
 _g_.m.mcache = allocmcache()
}

mheap的初始化方法

// Initialize the heap.
func (h *mheap) init(spansStart, spansBytes uintptr) {
 // 0. xxalloc.init
 // 1. free、busy init
 for i := range h.free {
 h.free[i].init()
 h.busy[i].init()
 }
 h.freelarge.init()
 h.busylarge.init()
 // 2. mcentral初始化
 for i := range h.central {
 h.central[i].mcentral.init(int32(i))
 }
 
 // 3. spans初始化
 sp := (*slice)(unsafe.Pointer(&h.spans))
 sp.array = unsafe.Pointer(spansStart)
 sp.len = 0
 sp.cap = int(spansBytes / sys.PtrSize)
}

mcentral的初始化比较简单,设置自己的级别,同时将两个mspanList初始化

而mcache的初始化在func procresize(nprocs int32) *p中,procresize也在schedinit()中调用,顺序在mallocinit()之后,也就是说发生在mheap于mcentral的初始化后面

func procresize(nprocs int32) *p {
 // 0. bala bala
 // 1. 初始化P
 for i := int32(0); i < nprocs; i++ {
 pp := allp[i]
 //初始化每个P的mcache
 if pp.mcache == nil {
 if old == 0 && i == 0 {
 if getg().m.mcache == nil {
 throw("missing mcache?")
 }
 pp.mcache = getg().m.mcache 
 } else {
 pp.mcache = allocmcache()
 }
 }
 }
}

而allocmcache比较简单

func allocmcache() *mcache {
 lock(&mheap_.lock)
 c := (*mcache)(mheap_.cachealloc.alloc())
 unlock(&mheap_.lock)
 for i := 0; i < _NumSizeClasses; i++ {
 c.alloc[i] = &emptymspan
 }
 c.next_sample = nextSample()
 return c
}

至此,管理结构mheap、67个mcentral及每个P的mcache都初始化完毕,接下来进入重点--分配阶段。

4、分配

前面说过,在分配对象内存时,根据对象的大小分为3个级别:极小、小、大;在这里我们假设关闭内联优化,即没有逃逸的存在。当new一个对象时,调用的是:

func newobject(typ *_type) unsafe.Pointer {
 return mallocgc(typ.size, typ, true)
}

mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
 
 dataSize := size
 c := gomcache()
 var x unsafe.Pointer
 noscan := typ == nil || typ.kind&kindNoPointers != 0
 if size <= maxSmallSize {
 if noscan && size < maxTinySize {
 // 极小对象
 } else {
 // 小对象
 } else {
 // 大对象
 }
}

我们将针对这三类一一分析

• 首先是极小对象(<16byte)

off := c.tinyoffset
// 地址对齐
if size&7 == 0 {
 off = round(off, 8)
} else if size&3 == 0 {
 off = round(off, 4)
} else if size&1 == 0 {
 off = round(off, 2)
}
//若之前tiny剩余空间够用,则将极小对象拼在一起
if off+size <= maxTinySize && c.tiny != 0 {
 // The object fits into existing tiny block.
 x = unsafe.Pointer(c.tiny + off)
 c.tinyoffset = off + size
 c.local_tinyallocs++
 mp.mallocing = 0
 releasem(mp)
 return x
}
//不若,则申请新的mspan
// Allocate a new maxTinySize block.
span := c.alloc[tinySizeClass]
v := nextFreeFast(span)
if v == 0 {
 v, _, shouldhelpgc = c.nextFree(tinySizeClass)
}
x = unsafe.Pointer(v)
(*[2]uint64)(x)[0] = 0
(*[2]uint64)(x)[1] = 0
// 新申请的剩余空间大于之前的剩余空间
if size < c.tinyoffset || c.tiny == 0 {
 c.tiny = uintptr(x)
 c.tinyoffset = size
}
size = maxTinySize

其中nextFreeFast和nextFree先跳过去,因为小对象分配时也会使用到,之后一并分析;下面是极小对象分配的示意图
先是有足够剩余空间,那么对齐都直接利用(为了便于说明问题,tinyoffset用箭头指向表示)

如果没有足够空间,则申请新的,若必要修正tiny及tinyoffset的值

• 接着分析小对象(16byte <= size <= 32k)
  介于16b到32k之间大小的对象分配比较复杂,可以结合文末的流程图,便于记忆

var sizeclass uint8
if size <= smallSizeMax-8 {
 sizeclass = size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]
} else {
 sizeclass = size_to_class128[(size-smallSizeMax+largeSizeDiv-1)/largeSizeDiv]
}
size = uintptr(class_to_size[sizeclass])
span := c.alloc[sizeclass]
v := nextFreeFast(span)
if v == 0 {
 v, span, shouldhelpgc = c.nextFree(sizeclass)
}
x = unsafe.Pointer(v)
if needzero && span.needzero != 0 {
 memclrNoHeapPointers(unsafe.Pointer(v), size)
} 

首先计算申请对象的sizeclass,以此找到对应大小的mspan;然后找到可用的地址。这里面有两个重要的方法nextFreeFast和nextFree:

// nextFreeFast returns the next free object if one is quickly available.
// Otherwise it returns 0.
func nextFreeFast(s *mspan) gclinkptr {
 //计算s.allocCache从低位起有多少个0
 theBit := sys.Ctz64(s.allocCache) 
 if theBit < 64 {
 result := s.freeindex + uintptr(theBit)
 if result < s.nelems {
 freeidx := result + 1
 if freeidx%64 == 0 && freeidx != s.nelems {
 return 0
 }
 //更新位图、可用游标
 s.allocCache >>= (theBit + 1)
 s.freeindex = freeidx
 //根据result和s.elemsize起始地址计算v
 v := gclinkptr(result*s.elemsize + s.base())
 s.allocCount++
 return v
 }
 }
 return 0
}

重点是当mcache没有可用地址时,通过nextFree向mcentral甚至mheap申请

func (c *mcache) nextFree(sizeclass uint8) (v gclinkptr, s *mspan, shouldhelpgc bool) {
 s = c.alloc[sizeclass]
 shouldhelpgc = false
 freeIndex := s.nextFreeIndex()
 if freeIndex == s.nelems {
 // The span is full.
 ...
 //重新填充当前的mcache
 systemstack(func() {
 c.refill(int32(sizeclass))
 })
 shouldhelpgc = true
 s = c.alloc[sizeclass]
 freeIndex = s.nextFreeIndex()
 }
 ...
 ...
}

向mcentral是通过refill来实现的

func (c *mcache) refill(sizeclass int32) *mspan {
 _g_ := getg()
 _g_.m.locks++
 // 想mcentral归还当前的mspan
 s := c.alloc[sizeclass]
 if uintptr(s.allocCount) != s.nelems {
 throw("refill of span with free space remaining")
 }
 if s != &emptymspan {
 s.incache = false
 }
 // 获取新的, mcentral.cacheSpan()重点分析
 s = mheap_.central[sizeclass].mcentral.cacheSpan()
 ...
 c.alloc[sizeclass] = s
 _g_.m.locks--
 return s
}

下面是一个很长的调用链路...

func (c *mcentral) cacheSpan() *mspan {
 ...
retry:
 var s *mspan
 //先从非空列表中找
 for s = c.nonempty.first; s != nil; s = s.next {
 ...
 goto havespan
 }
 //没有则从空列表中找
 for s = c.empty.first; s != nil; s = s.next {
 ...
 goto retry
 }
 //实在没有,那么申请吧 
 s = c.grow()
 if s == nil {
 return nil
 }
 
havespan:
 //
 return s
}
// 由mcentral申请
func (c *mcentral) grow() *mspan {
 ...
 s := mheap_.alloc(npages, c.sizeclass, false, true)
 ...
 return s
}
//由mheap申请
func (h *mheap) alloc(npage uintptr, sizeclass int32, large bool, needzero bool) *mspan {
 ...
 systemstack(func() {
 s = h.alloc_m(npage, sizeclass, large)
 })
 ...
 return s
}
func (h *mheap) alloc_m(npage uintptr, sizeclass int32, large bool) *mspan {
 ...
 s := h.allocSpanLocked(npage)
 ...
 return s
}
//Best-fit算法
func (h *mheap) allocSpanLocked(npage uintptr) *mspan {
 //先从128页以内(1M)的free列表中寻找
 for i := int(npage); i < len(h.free); i++ {
 list = &h.free[i]
 ...
 }
 // Best-fit 对于大对象申请也会用到这个方法
 //基本思路是找到最小可以满足需求的mspan,如果有多个,选择地址最小的
 list = &h.freelarge
 s = h.allocLarge(npage)
 if s == nil {
 //如果mheap也没有空间了,向系统申请吧
 if !h.grow(npage) {
 return nil
 }
 s = h.allocLarge(npage)
 if s == nil {
 return nil
 }
 }
HaveSpan:
 //转移s
 list.remove(s)
 if s.inList() {
 throw("still in list")
 }
 //对于申请到的内存大于想要的,将其拆分,避免浪费
 if s.npages > npage {
 ...
 h.freeSpanLocked(t, false, false, s.unusedsince)
 s.state = _MSpanFree
 }
 
 return s
}
//向系统申请空间
func (h *mheap) grow(npage uintptr) bool {
 //计算页数
 npage = round(npage, (64<<10)/_PageSize)
 ask := npage << _PageShift
 if ask < _HeapAllocChunk {
 ask = _HeapAllocChunk
 }
 v := h.sysAlloc(ask)
 ...
}
func (h *mheap) sysAlloc(n uintptr) unsafe.Pointer {
 ...
 // sysReserve调用mmap预留空间,至此调用链结束
 p := uintptr(sysReserve(unsafe.Pointer(h.arena_end), p_size, &reserved))
 ... 
}

• 最后是大对象

var s *mspan
shouldhelpgc = true
systemstack(func() {
 // largeAlloc会调用mheap_.alloc,这个方法在小对象申请时已经追踪过
 s = largeAlloc(size, needzero)
})
s.freeindex = 1
s.allocCount = 1
x = unsafe.Pointer(s.base())
size = s.elemsize

• 内存分配的流程图

  
  
  流程图
  

  流程图

5、参考文献

[1]. https://github.com/qyuhen
[2]. http://legendtkl.com/2017/04/02/golang-alloc/
[3]. https://tracymacding.gitbooks.io/implementation-of-golang/content/memory/memory_core_data_structure.html

本文来自:简书

感谢作者:Love语鬼

查看原文:探索Go内存管理(分配)

• 编辑
• 预览