不同的编程语言选择不同的方式管理内存,本节会介绍Go语言内存分配器。
Go内存分配的设计思想是:
内存分配算法采用Google的TCMalloc算法
,每个线程都会自行维护一个独立的内存池,进行内存分配时优先从该内存池中分配,当内存池不足时才会向加锁向全局内存池申请,减少系统调用并且避免不同线程对全局内存池的锁竞争把内存切分的非常细小,分为多级管理,以降低锁的粒度回收对象内存时,并没有将其真正释放掉,只是放回预先分配的大块内存中,以便复用。只有内存闲置过多的时候才会尝试归还给操作系统,降低整体开销。
接下来就开始详细的讲解:
设计原理
用户程序(mutator)内存分配器(allocator,简称分配器)垃圾收集器(collector,简称收集器)当用户程序申请内存时,它会通过内存分配器重新申请新内存。内存分配器会负责从堆中初始化相应的内存区域。
分配方法
内存分配器一般包含两种分配方法:
线性分配器空闲链表分配器
线性分配器
线性分配器具有较快的执行速度和简单的实现,但是它的缺点就是容易产生内存碎片。
图片来自于面向信仰编程
它很难利用红色的这个内存了。
因此我们需要结合其他的垃圾收集算法来整理存活对象的碎片,定期合并空闲内存。
例如有:
标记压缩法复制回收分代回收
空闲的链表分配器
当用户程序申请内存时,空闲链表分配器会依次遍历空闲内存块,找到足够大的内存,然后申请新资源并修改链表。
因为不同的内存块通过指针构成了链表,所以使用这种方式的分配器可以重新利用回收的资源,但是因为分配器分配内存时需要遍历链表,所以它的时间复杂度是O(N)。空闲链表分配器可以选择不同的策略在链表的内存块中进行选择:
首次适应 – 从链表头开始遍历,找到第一个大小大于申请内存的内存块循环首次适应 – 从上次遍历的结束位置开始遍历,选择第一个大小大于申请内存的内存块最优适应 – 从链表头遍历整个链表,选择最合适的内存块隔离适应 – 将内存分割成多个链表,每个链表中的内存块大小相同,申请内存时先找到满足条件的链表,再从链表中选择合适的内存块
Go语言使用的内存分配策略与第4种策略有些相似
该策略会将内存分割成4,8,16,32字节的内存块组成的链表,当我们向内存分配器申请8字节的内存时,它会找到满足条件的内存块并返回。这样可以减少遍历次数。
分级分配
线程缓存分配是用于分配内存的机制,它比glibc种的malloc还要快很多。Go语言的内存分配器借鉴了TCMalloc(线程缓存分配)。其核心理念是使用多级缓存将对象根据大小分类。
对象大小
因为程序中的绝大多数对象的大小都在 32KB 以下,而申请的内存大小影响 Go 语言运行时分配内存的过程和开销,所以分别处理大对象和小对象有利于提高内存分配器的性能。
多级缓存
TCMalloc和Go语言运行时分配器都会引入:
线程缓存中心缓存页堆
线程缓存属于每一个独立的线程,它能满足线程上绝大多数的分配要求。因为不涉及多线程,所以不需要锁来保护,减少了性能损耗。当线程缓存不能满足要求的时候,运行时会使用中心缓存作为补充解决小对象的内存分配。在遇到32KB以上的对象时,内存分配器会选择页堆直接分配大内存。
虚拟内存布局
Go 语言程序的 1.10 版本在启动时会初始化整片虚拟内存区域,如下所示的三个区域spans
、bitmap
和arena
分别预留了 512MB、16GB 以及 512GB 的内存空间,这些内存并不是真正存在的物理内存,而是虚拟内存:
线性内存
spans
区域存储了指向内存管理单元runtime.mspan
的指针,每个内存单元会管理几页的内存空间,每页大小为 8KB;bitmap
用于标识arena
区域中的那些地址保存了对象,位图中的每个字节都会表示堆区中的 32 字节是否空闲;arena
区域是真正的堆区,运行时会将 8KB 看做一页,这些内存页中存储了所有在堆上初始化的对象;缺点:这种机制的实现依赖于一个重要的条件:堆区的内存是连续的
稀疏内存
运行时使用二维heapArena
数组管理所有内存,每个单元都会管理64MB的内存空间。
type heapArena struct {bitmap [heapArenaBitmapBytes]bytespans [pagesPerArena]*mspanpageInUse [pagesPerArena / 8]uint8pageMarks [pagesPerArena / 8]uint8pageSpecials [pagesPerArena / 8]uint8checkmarks *checkmarksMapzeroedBase uintptr}
该结构体中的bitmap
和spans
与线性内存中的bitmap
和spans
区域一一对应,zeroedBase
字段指向了该结构体管理的内存的基地址。上述设计将原有的连续大内存切分成稀疏的小内存,而用于管理这些内存的元信息也被切成了小块。
地址空间
所有内存最终都要从操作系统中申请,所以Go语言的运行时构建了操作系统的内存管理抽象层。
这个是各种状态之间的转换流程:
内存管理组件
Go内存分配器包含几个重要组件:
内存管理单元 -->runtime.mspan
线程缓存 -->runtime.mcache
中心缓存 -->runtime.mcentral
页堆 -->runtime.mheap
所有的 Go 语言程序都会在启动时初始化如上图所示的内存布局,每一个处理器都会分配一个线程缓存runtime.mcache
用于处理微对象和小对象的分配,它们会持有内存管理单元runtime.mspan
。
每个类型的内存管理单元都会管理特定大小的对象,当内存管理单元中不存在空闲对象时,它们会从runtime.mheap
持有的 134 个中心缓存runtime.mcentral
这张图很重要,建议先看一下留个印象,然后到时候把文章看完之后可以回来返回观看。
内存管理单元
runtime.mspan
是Go语言内存管理的基本单元,该结构体中包含next和prev两个字段。
type mspan struct {next *mspan// next span in list, or nil if noneprev *mspan// previous span in list, or nil if nonelist *mSpanList // For debugging. TODO: Remove........}
//go:notinheaptype mSpanList struct {first *mspan // first span in list, or nil if nonelast *mspan // last span in list, or nil if none}
页和内存
每一个runtime.mspan
都管理npages
个8KB的页,这个页不是操作系统的页,而是其整数倍。
type mspan struct {startAddr uintptr // 起始地址npages uintptr // 页数freeindex uintptr // 扫描页中空闲对象的初始索引allocBits *gcBits // 标记内存的占用情况gcmarkBits *gcBits // 标记内存的回收情况allocCache uint64 // allocBits的补码,可用于快速查找内存中未被使用的内存...}
如上图,当结构体管理的内存不足时,运行时会以页为单位向堆中申请内存。
当用户程序或者线程向runtime.mspan
申请内存时,它会使用allocCache
字段以对象为单位在管理的内存中快速查找待分配的空间。如果我们能在内存中找到空闲的内存单元会直接返回,当内存中不包含空闲的内存时,上一级的组件runtime.mcache
会为调用runtime.mcache.refill
更新内存管理单元以满足为更多对象分配内存的需求。
状态
type mspan struct {...state mSpanStateBox...}
状态一共有4种:
var mSpanStateNames = []string{"mSpanDead","mSpanInUse","mSpanManual","mSpanFree",}
跨度类
type mspan struct {...spanclass spanClass...}
Go有68种不同大小的spanClass,用于小对象的分配
const _NumSizeClasses = 68var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, 256, 288, 320, 352, 384, 416, 448, 480, 512, 576, 640, 704, 768, 896, 1024, 1152, 1280, 1408, 1536,1792, 2048, 2304, 2688, 3072, 3200, 3456, 4096, 4864, 5376, 6144, 6528, 6784, 6912, 8192, 9472, 9728, 10240, 10880, 12288, 13568, 14336, 16384, 18432, 19072, 20480, 21760, 24576, 27264, 28672, 32768}
如果按照序号为1的spanClass(对象规格为8B)分配,每个span占用堆的字节数:8k,mspan可以保存1024个对象
如果按照序号为2的spanClass(对象规格为16B)分配,每个span占用堆的字节数:8k,mspan可以保存512个对象
…
如果按照序号为67的spanClass(对象规格为32K)分配,每个span占用堆的字节数:32k,mspan可以保存1个对象
大于32k的对象出现时,会直接从heap分配一个特殊的span,这个特殊的span的类型(class)是0, 只包含了一个大对象。
runtime.spanClass
是一个uint8
类型的整数,它的前 7 位存储着跨度类的 ID,最后一位表示是否包含指针,该类型提供的两个方法能够帮我们快速获取对应的字段。
线程缓存
mcache管理线程在本地缓存的mspan,每个goroutine绑定的P都有一个mcache
字段
type mcache struct {alloc [numSpanClasses]*mspan ...}_NumSizeClasses = 68numSpanClasses = _NumSizeClasses << 1
mcache
用Span Classes
作为索引管理多个用于分配的mspan
,它包含所有规格的mspan
。它是_NumSizeClasses
的2倍,也就是68*2=136
,其中*2是将spanClass分成了有指针和没有指针两种,方便与垃圾回收。对于每种规格,有2个mspan,一个mspan不包含指针,另一个mspan则包含指针。对于无指针对象的mspan
在进行垃圾回收的时候无需进一步扫描它是否引用了其他活跃的对象。
这也回应了前面spanClass
前7位是跨度类的ID,最后一位是是否包含指针。
中心缓存
mcentral管理全局的mspan供所有线程使用,全局mheap变量包含central字段,每个 mcentral 结构都维护在mheap结构内
type mcentral struct {spanclass spanClass // 指当前规格大小partial [2]spanSet // 有空闲object的mspan列表full [2]spanSet // 没有空闲object的mspan列表}
每个mcentral管理一种spanClass的mspan,并将有空闲空间和没有空闲空间的mspan分开管理。partial和 full的数据类型为
spanSet,表示mspans
集,可以通过pop、push来获得mspans
type spanSet struct {spineLock mutexspineunsafe.Pointer // 指向[]span的指针spineLen uintptr // Spine array length, accessed atomicallyspineCap uintptr // Spine array cap, accessed under lockindex headTailIndex // 前32位是头指针,后32位是尾指针}
简单说一下mcache
从mcentral
获取和归还mspan
的流程:
获取; 加锁,从partial
链表找到一个可用的mspan
;并将其从partial
链表删除;将取出的mspan
加入到full
链表;将mspan
返回给工作线程,解锁。归还; 加锁,将mspan
从full
链表删除;将mspan
加入到partial
链表,解锁。
页堆
runtime.mheap
是内存分配的核心结构体,Go 语言程序会将其作为全局变量存储,而堆上初始化的所有对象都由该结构体统一管理,该结构体中包含两组非常重要的字段,其中一个是全局的中心缓存列表central
,另一个是管理堆区内存区域的arenas
以及相关字段。
var mheap_ mheaptype mheap struct {lockmutex // 全局锁pagespageAlloc // 页面分配的数据结构allspans []*mspan // 所有通过 mheap_ 申请的mspans// 堆arenas [1 << arenaL1Bits]*[1 << arenaL2Bits]*heapArena// 所有中心缓存mcentralcentral [numSpanClasses]struct {mcentral mcentralpad[cpu.CacheLinePadSize - unsafe.Sizeof(mcentral{})%cpu.CacheLinePadSize]byte}...}
初始化
有几个初始化比较重要:
空闲链表分配器中心缓存
内存管理单元
func (h *mheap) alloc(npages uintptr, spanclass spanClass, needzero bool) *mspan {var s *mspansystemstack(func() {if h.sweepdone == 0 {h.reclaim(npages)}s = h.allocSpan(npages, false, spanclass, &memstats.heap_inuse)})...return s}
为了阻止内存的大量占用和堆的增长,我们在分配对应页数的内存前需要先调用runtime.mheap.reclaim
方法回收一部分内存,随后运行时通过runtime.mheap.allocSpan
分配新的内存管理单元,我们会将该方法的执行过程拆分成两个部分:
如果申请内存大小充足,那么就直接申请成功。如果申请内存大小不充足,那么就会触发扩容。扩容的时候如果申请到内存就说明扩容成功,否则就是扩容失败,运行时会直接终止当前程序。
内存分配
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {mp := acquirem()mp.mallocing = 1c := gomcache()var x unsafe.Pointernoscan := typ == nil || typ.ptrdata == 0if size <= maxSmallSize {if noscan && size < maxTinySize {// 微对象分配} else {// 小对象分配}} else {// 大对象分配}publicationBarrier()mp.mallocing = 0releasem(mp)return x}
上述代码使用runtime.gomcache
获取线程缓存并判断申请内存的类型是否为指针。我们从这个代码片段可以看出runtime.mallocgc
会根据对象的大小执行不同的分配逻辑,在前面的章节也曾经介绍过运行时根据对象大小将它们分成微对象、小对象和大对象,这里会根据大小选择不同的分配逻辑:
微对象(0, 16B)
— 先使用微型分配器,再依次尝试线程缓存、中心缓存和堆分配内存;小对象[16B, 32KB]
— 依次尝试使用线程缓存、中心缓存和堆分配内存;大对象(32KB, +∞)
— 直接在堆上分配内存;
下面依次来进行介绍:
微对象
Go 语言运行时将小于 16 字节的对象划分为微对象,它会使用线程缓存上的微分配器提高微对象分配的性能,我们主要使用它来分配较小的字符串以及逃逸的临时变量。微分配器可以将多个较小的内存分配请求合入同一个内存块中,只有当内存块中的所有对象都需要被回收时,整片内存才可能被回收。
微分配器管理的对象不可以是指针类型,管理多个对象的内存块大小maxTinySize
是可以调整的,在默认情况下,内存块的大小为 16 字节。maxTinySize
的值越大,组合多个对象的可能性就越高,内存浪费也就越严重;maxTinySize
越小,内存浪费就会越少,不过无论如何调整,8 的倍数都是一个很好的选择。
图 7-20 微分配器的工作原理
如上图所示,微分配器已经在 16 字节的内存块中分配了 12 字节的对象,如果下一个待分配的对象小于 4 字节,它会直接使用上述内存块的剩余部分,减少内存碎片,不过该内存块只有所有对象都被标记为垃圾时才会回收。
线程缓存runtime.mcache
中的tiny
字段指向了maxTinySize
大小的块,如果当前块中还包含大小合适的空闲内存,运行时会通过基地址和偏移量获取并返回这块内存:
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {...if size <= maxSmallSize {if noscan && size < maxTinySize {off := c.tinyoffsetif off+size <= maxTinySize && c.tiny != 0 {x = unsafe.Pointer(c.tiny + off)c.tinyoffset = off + sizec.local_tinyallocs++releasem(mp)return x}...}...}...}
当内存块中不包含空闲的内存时,下面的这段代码会先从线程缓存找到跨度类对应的内存管理单元runtime.mspan
,调用runtime.nextFreeFast
获取空闲的内存;当不存在空闲内存时,我们会调用runtime.mcache.nextFree
从中心缓存或者页堆中获取可分配的内存块:
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {...if size <= maxSmallSize {if noscan && size < maxTinySize {...span := c.alloc[tinySpanClass]v := nextFreeFast(span)if v == 0 {v, _, _ = c.nextFree(tinySpanClass)}x = unsafe.Pointer(v)(*[2]uint64)(x)[0] = 0(*[2]uint64)(x)[1] = 0if size < c.tinyoffset || c.tiny == 0 {c.tiny = uintptr(x)c.tinyoffset = size}size = maxTinySize}...}...return x}
获取新的空闲内存块之后,上述代码会清空空闲内存中的数据、更新构成微对象分配器的几个字段tiny
和tinyoffset
并返回新的空闲内存。
小对象
小对象是指大小为 16 字节到 32,768 字节的对象以及所有小于 16 字节的指针类型的对象,小对象的分配可以被分成以下的三个步骤:
确定分配对象的大小以及跨度类runtime.spanClass
;从线程缓存、中心缓存或者堆中获取内存管理单元并从内存管理单元找到空闲的内存空间;调用runtime.memclrNoHeapPointers
清空空闲内存中的所有数据;
大对象
运行时对于大于 32KB 的大对象会单独处理,我们不会从线程缓存或者中心缓存中获取内存管理单元,而是直接调用runtime.mcache.allocLarge
分配大片内存:
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {...if size <= maxSmallSize {...} else {var s *mspanspan = c.allocLarge(size, needzero, noscan)span.freeindex = 1span.allocCount = 1x = unsafe.Pointer(span.base())size = span.elemsize}publicationBarrier()mp.mallocing = 0releasem(mp)return x}
runtime.mcache.allocLarge
会计算分配该对象所需要的页数,它按照 8KB 的倍数在堆上申请内存:
func (c *mcache) allocLarge(size uintptr, needzero bool, noscan bool) *mspan {npages := size >> _PageShiftif size&_PageMask != 0 {npages++}...s := mheap_.alloc(npages, spc, needzero)mheap_.central[spc].mcentral.fullSwept(mheap_.sweepgen).push(s)s.limit = s.base() + sizeheapBitsForAddr(s.base()).initSpan(s)return s}
申请内存时会创建一个跨度类为 0 的runtime.spanClass
并调用runtime.mheap.alloc
分配一个管理对应内存的管理单元。
总结
首先通过计算使用的大小规格然后使用mcache
中对应大小规格的块分配。如果mcentral
中没有可用的块,则向mheap
申请,并根据算法找到最合适的mspan
。如果申请到的mspan
超出申请大小,将会根据需求进行切分,以返回用户所需的页数。剩余的页构成一个新的 mspan 放回 mheap 的空闲列表。如果 mheap 中没有可用 span,则向操作系统申请一系列新的页(最小 1MB)