基于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
