go-內存機制(3) - 內存分配

go的內存分配

Go在程序啟動的時候仅淑，會先向操作系統(tǒng)申請一塊內存（注意這時還只是一段虛擬的地址空間滤祖，并不會真正地分配內存）陋气，切成小塊后自己進行管理议忽。

申請到的內存塊被分配了三個區(qū)域，在X64上分別是512MB村刨，16GB告抄，512GB大小

Golang有一套自己的內存管理機制，自主的去完成內存分配烹困、垃圾回收玄妈、內存管理等過程，從而避免頻繁的向操作系統(tǒng)申請、釋放內存拟蜻，有效的提升go語言的處理性能绎签。
Golang的內存管理是基于tcmalloc模型設計，但又有些差異酝锅，局部緩存并不是分配給進程或者線程诡必，而是分配給P（Processor）；Golang的GC是stop the world搔扁，并不是每個進程單獨進行GC爸舒；golang語言對span的管理更有效率。

基本概念

1.Span

span是golang內存管理的基本單位稿蹲，每個span管理指定規(guī)格（以page為單位）的內存塊扭勉，內存池分配出不同規(guī)格的內存塊就是通過span體現出來的，應用程序創(chuàng)建對象就是通過找到對應規(guī)格的span來存儲的苛聘，

下面我們看一下mspan的結構涂炎。

//go:notinheap
type mspan struct {
    next *mspan     // next span in list, or nil if none
    prev *mspan     // previous span in list, or nil if none
    list *mSpanList // For debugging. TODO: Remove.

    startAddr uintptr // address of first byte of span aka s.base()
    npages    uintptr // number of pages in span

    manualFreeList gclinkptr // list of free objects in mSpanManual spans


    freeindex uintptr //freeindex是0到nelems之間的位置索引，標記下一個空對象索引设哗。
    // TODO: Look up nelems from sizeclass and remove this field if it
    // helps performance.
    nelems uintptr // number of object in the span.

    
    allocCache uint64

    allocBits  *gcBits
    gcmarkBits *gcBits

    // sweep generation:
    // if sweepgen == h->sweepgen - 2, the span needs sweeping
    // if sweepgen == h->sweepgen - 1, the span is currently being swept
    // if sweepgen == h->sweepgen, the span is swept and ready to use
    // if sweepgen == h->sweepgen + 1, the span was cached before sweep began and is still cached, and needs sweeping
    // if sweepgen == h->sweepgen + 3, the span was swept and then cached and is still cached
    // h->sweepgen is incremented by 2 after every GC

    sweepgen    uint32
    divMul      uint16        // for divide by elemsize - divMagic.mul
    baseMask    uint16        // if non-0, elemsize is a power of 2, & this will get object allocation base
    allocCount  uint16        // number of allocated objects
    spanclass   spanClass     // size class and noscan (uint8)
    state       mSpanStateBox // mSpanInUse etc; accessed atomically (get/set methods)
    needzero    uint8         // needs to be zeroed before allocation
    divShift    uint8         // for divide by elemsize - divMagic.shift
    divShift2   uint8         // for divide by elemsize - divMagic.shift2
    elemsize    uintptr       // computed from sizeclass or from npages
    limit       uintptr       // end of data in span
    speciallock mutex         // guards specials list
    specials    *special      // linked list of special records sorted by offset.
}

根據源碼和圖結合來看唱捣，會更加容易理解mspan，每一個mspan就是用來給程序分配對象空間的网梢，也就是說一般我們對象都會放到mspan中管理震缭，這里我們重點解釋一下如圖所示的幾個屬性，startAddr 是該mspan在arena區(qū)域的首地址战虏，freeindex 用來表示下一個可能是空對象的位置拣宰，也就是說freeindex之前的元素（存儲對象的空間）均是已經被使用的，freeindex之后的元素可能被使用可能沒被使用活烙，allocCache是從freeindex開始對后續(xù)元素分配情況進行緩存標記徐裸，通過freeindex和allocCache結合進行查找未分配的元素位置效率會更高遣鼓，我們能快速的找到一個空對象分配給程序使用啸盏，而不用全局遍歷。allocBits用來標識該span中所有元素的使用分配情況骑祟，gcmarkBits 用來sweep過程進行標記垃圾對象的回懦，用于后續(xù)gc。

2.怎么區(qū)分span

那么要想區(qū)分不同規(guī)格的span次企，我們必須要有一個標識怯晕，每個span通過splanclass標識屬于哪種規(guī)格的span，golang的span規(guī)格一共有67種缸棵，具體查看:

// 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%
//    10        144        8192       56         128     11.82%
//舟茶。。。吧凉。隧出。
//    56      13568       40960        3         256      9.99%
//    57      14336       57344        4           0      5.35%
//    58      16384       16384        1           0     12.49%
//    59      18432       73728        4           0     11.11%
//    60      19072       57344        3         128      3.57%
//    61      20480       40960        2           0      6.87%
//    62      21760       65536        3         256      6.25%
//    63      24576       24576        1           0     11.45%
//    64      27264       81920        3         128     10.00%
//    65      28672       57344        2           0      4.91%
//    66      32768       32768        1           0     12.50%

其中：

class：分類id或者規(guī)格id，也就是spanclass, 表示該span可存儲的對象規(guī)格類型
bytes/obj：該列代表能存儲每個對象的字節(jié)數阀捅，也就是說可以存儲多大的對象胀瞪，字段是elemsize
bytes/span：每個span占用堆的字節(jié)數，也即頁數頁大小,npages8KB
objects: 每個span可分配的元素個數饲鄙，或者說可存儲的對象個數凄诞，也就是nelems，也即（bytes/spans）/（bytes/obj）
tail bytes: 每個span產生的內存碎片忍级，也即（bytes/span）%（bytes/obj）
max waste：最大浪費比例帆谍，（bytes/obj-最小使用量）objects/(bytes/span)100,比如classId=2 最小使用量是9bytes，則max waste=（16-9）512/8192100=43.75%

通過上表轴咱，我們可以很清楚的知道在創(chuàng)建一個對象時候既忆，需要去選哪一個splanclass的span去獲取內存空間，一個span能存多少這樣大小的對象等等信息嗦玖，非常清晰而又盡可能節(jié)約的去使用內存患雇。另外上表可見最大的對象是32KB大小，超過32KB大小的由特殊的class表示宇挫，該class ID為0苛吱，每個class只包含一個對象。所以上面只有列出了1-66器瘪。

內存管理組件

怎么把這些各種規(guī)格孤立的span串起來翠储？下面我們來說一下golang的內存管理組件，內存分配是由內存分配器完成橡疼，分配器由3種組件構成：mcache援所、mcentral、mheap欣除，我們來詳細講一下每個組件住拭。

我們知道golang之所有有很強的并發(fā)能力，依賴于它的G-P-M并發(fā)模型
)历帚，

1.mcache

mcache就綁在并發(fā)模型的P上滔岳，也就是說我們每一個P都會有一個mcahe綁定，用來給協(xié)程分配對象存儲空間的挽牢。下面具體看一下mcache的結構

type mcache struct {
    // The following members are accessed on every malloc,
    // so they are grouped here for better caching.
    next_sample uintptr // trigger heap sample after allocating this many bytes
    local_scan  uintptr // bytes of scannable heap allocated

    // Allocator cache for tiny objects w/o pointers.
    // See "Tiny allocator" comment in malloc.go.

    // tiny points to the beginning of the current tiny block, or
    // nil if there is no current tiny block.
    //
    // tiny is a heap pointer. Since mcache is in non-GC'd memory,
    // we handle it by clearing it in releaseAll during mark
    // termination.
    tiny             uintptr
    tinyoffset       uintptr
    local_tinyallocs uintptr // number of tiny allocs not counted in other stats

    // The rest is not accessed on every malloc.

    alloc [numSpanClasses]*mspan // spans to allocate from, indexed by spanClass

    stackcache [_NumStackOrders]stackfreelist

    // Local allocator stats, flushed during GC.
    local_largefree  uintptr                  // bytes freed for large objects (>maxsmallsize)
    local_nlargefree uintptr                  // number of frees for large objects (>maxsmallsize)
    local_nsmallfree [_NumSizeClasses]uintptr // number of frees for small objects (<=maxsmallsize)

    // flushGen indicates the sweepgen during which this mcache
    // was last flushed. If flushGen != mheap_.sweepgen, the spans
    // in this mcache are stale and need to the flushed so they
    // can be swept. This is done in acquirep.
    flushGen uint32
}

可以看到在mcache結構體中并沒有鎖存在谱煤，這是因為每個P都會綁定一個mcache，而每個P同時只會處理一個groutine禽拔，而且不同P之間是內存隔離的刘离，因此不存在競爭情況室叉。關鍵字段都已經在代碼中解釋了，這里我們重點關注一下alloc [numSpanClasses] *mspan硫惕，由于SpanClasses一共有67種太惠，為了滿足指針對象和非指針對象，這里為每種規(guī)格的span同時準備scan和noscan兩個疲憋，因此一共有134個mspan緩存鏈表凿渊，分別用于存儲指針對象和非指針對象，這樣對非指針對象掃描的時候不需要繼續(xù)掃描它是否引用其他對象缚柳，GC掃描對象的時候對于noscan的span可以不去查看bitmap區(qū)域來標記子對象, 這樣可以大幅提升標記的效率埃脏。另外mcache在初始化時是沒有任何mspan資源的，在使用過程中會動態(tài)地申請秋忙，不斷的去填充 alloc[numSpanClasses]*mspan彩掐，通過雙向鏈表連接，如下圖所示：

通過圖示我們可以看到alloc[numSpanClasses]*mspan管理了很多不同規(guī)格不同類型的span灰追，golang對于[16B,32KB]的對象會使用這部分span進行內存分配堵幽，所以所有在這區(qū)間大小的對象都會從alloc這個數組里尋找
而對于更小的對象，我們叫它tiny對象弹澎，golang會通過tiny和tinyoffset組合尋找位置分配內存空間朴下，這樣可以更好的節(jié)約空間.

2.mcentral

type mcentral struct {
    lock      mutex
    spanclass spanClass
    nonempty  mSpanList // list of spans with a free object, ie a nonempty free list
    empty     mSpanList // list of spans with no free objects (or cached in an mcache)

    // nmalloc is the cumulative count of objects allocated from
    // this mcentral, assuming all spans in mcaches are
    // fully-allocated. Written atomically, read under STW.
    nmalloc uint64
}

我們提到mcache中的mspan都是動態(tài)申請的，那到底是去哪里申請呢苦蒿？其實當空間不足的時候殴胧，mcache會去mcentral中申請對應規(guī)格的mspan.
首先mcentral與mcache有一個明顯區(qū)別，就是有鎖存在佩迟，由于mcentral是公共資源团滥，會有多個mcache向它申請mspan，因此必須加鎖报强，另外灸姊，mcentral與mcache不同，由于P綁定了很多Goroutine秉溉，在P上會處理不同大小的對象力惯，mcache就需要包含各種規(guī)格的mspan，但mcentral不同坚嗜，同一個mcentral只負責一種規(guī)格的mspan就夠了夯膀。
mcentral也是用spanclass 進行標記規(guī)格類型诗充，該規(guī)格的所有未被使用的空閑mspan會掛載到nonempty 鏈表上苍蔬，已經被mcache拿走，未歸還的會掛載到empty 鏈表上蝴蜓，歸還后會再掛載到nonempty上碟绑，用圖表示如下俺猿，以規(guī)格sizeClass=1為例：

每一個mSpanList都掛著同一規(guī)格mspan雙向鏈表，當然這個鏈表也不是固定大小的格仲，都會動態(tài)變化的押袍。

從central獲取span步驟如下：

加鎖
從nonempty列表獲取一個可用span，并將其從鏈表中刪除
將取出的span放入empty鏈表
將span返回給線程
解鎖
線程將該span緩存進cache線程

將span歸還步驟如下：

加鎖
將span從empty列表刪除
將span加入noneempty列表
解鎖

3.mheap

mcentral 的nonempty也有用完的時候凯肋，當nonempty為空谊惭，再被申請的時候，也就是mcentral空間不足了侮东，那么它會向mheap申請新的頁圈盔，

type mheap struct {
    lock      mutex

    spans []*mspan

    bitmap        uintptr     //指向bitmap首地址，bitmap是從高地址向低地址增長的

    arena_start uintptr        //指示arena區(qū)首地址
    arena_used  uintptr        //指示arena區(qū)已使用地址位置

    central [67*2]struct {
        mcentral mcentral
        pad      [sys.CacheLineSize - unsafe.Sizeof(mcentral{})%sys.CacheLineSize]byte
    }
}

我們知道每個golang程序啟動時候會向操作系統(tǒng)申請一塊虛擬內存空間悄雅，僅僅是虛擬內存空間驱敲，真正需要的時候才會發(fā)生缺頁中斷，向系統(tǒng)申請真正的物理空間宽闲，在golang1.11版本以后众眨，申請的內存空間會放在一個heapArena數組里，由arenas [1 << arenaL1Bits]*[1 << arenaL2Bits]*heapArena表示容诬，用于應用程序內存分配娩梨，下面展示一下數組中一塊heapArena虛擬內存空間區(qū)域分配，

分為三個區(qū)域览徒，分別是：

spans區(qū)域：存放span指針地址的地方姚建，每個指針大小是8Byte
bitmap區(qū)域：用于標記arena區(qū)域中哪些地址保存了對象, 并且對象中哪些地址包含了指針，主要用于GC
arena區(qū)域：heap區(qū)域吱殉，程序內存分配的地方掸冤，管理的最小基本單位是頁，golang一個page的大小是：8KB

可以看出spans大小等于arenaSize/8KB友雳，可以理解為有多少page就準備出對應數量的“地址格子”稿湿，來充分保證能存下所有的span地址。

對于bitmap區(qū)域押赊，由于bitmap是用來標記每個地址空間的使用情況饺藤，我們知道指針大小是8Byte，因此需要arenaSize/8個流礁，一個bitmap可以標記四個地址涕俗，因此再除4。

介紹完三個區(qū)域神帅，我們再來看一下central [numSpanClasses]再姑，它就是管理的所有規(guī)格mcentral的集合，同樣是134種找御，pad對齊填充用于確保 mcentrals 以 CacheLineSize 個字節(jié)數分隔元镀，所以每一個 MCentral.lock 都可以獲取自己的緩存行绍填。而fixalloc類型的相關成員都是用來分配span、mache等對象的內存分配器栖疑，這里大家不要搞暈讨永，具體來講，以span舉例遇革，每一個span也需要空間存儲卿闹，這個就是在spanalloc這個二叉樹堆上存儲，拿到這個對象萝快，將startAddr 指向arena區(qū)域內的npages的內存空間才是給mcache使用的比原，或者說給P進行對象分配的。另外杠巡，由于mheap也是公共資源量窘，一定也要有鎖的存在。

下面結合圖看一下：

從上圖可以更清楚的看到氢拥，一個mheap會有134種mcentral蚌铜，而每一種規(guī)格的mcentral會掛載該規(guī)格的mspan鏈表。

前面我們講過tiny對象和小對象的內存分配嫩海，那大于 32KB 的對象怎么辦呢冬殃？golang將大于32KB的對象定義為大對象，直接通過 mheap 分配叁怪。這些大對象的申請是以一個全局鎖為代價的审葬，所以同時只能服務一個P申請，大對象內存分配一定是頁（8KB）的整數倍奕谭。

不管多大對象涣觉，一切的空間都是從mheap獲取的，那mheap要是不足了呢血柳？就只能向操作系統(tǒng)申請了官册。

內存分配原則

針對待分配對象的大小不同有不同的分配邏輯：
(0, 16B) 且不包含指針的對象： Tiny分配
(0, 16B) 包含指針的對象：小對象分配
[16B, 32KB] : 小對象分配
(32KB, -) : 大對象分配

、难捌、

tiny對象內存分配膝宁，直接向mcache的tiny對象分配器申請，如果空間不足根吁，則向mcache的tinySpanClass規(guī)格的span鏈表申請员淫，如果沒有，則向mcentral申請對應規(guī)格mspan击敌，依舊沒有介返，則向mheap申請，最后都用光則向操作系統(tǒng)申請愚争。
小對象內存分配映皆，先向本線程mcache申請挤聘，發(fā)現mspan沒有空閑的空間轰枝，向mcentral申請對應規(guī)格的mspan捅彻，如果mcentral對應規(guī)格沒有，向mheap申請對應頁初始化新的mspan鞍陨，如果也沒有步淹，則向操作系統(tǒng)申請，分配頁诚撵。
大對象內存分配缭裆，直接向mheap申請spanclass=0，如果沒有則向操作系統(tǒng)申請寿烟。

總結

Golang內存分配是個相當復雜的過程澈驼，其中還摻雜了GC的處理。
總的分配過程筛武，

獲取當前p的mcahce->
根基對象的大小計算出合適的class->
是否為指針對象->
從mcache的alloc[class]的鏈表中查詢是否存在可用的span->
如果mcache沒有可用的span則從mcentral申請一個新的span加入mcache中->
如果mcentral中也沒有可用的span則從mheap中申請一個新的span加入mcentral->
從該span中獲取到空閑對象地址并返回

1、Golang程序啟動時申請一大塊內存并劃分成spans徘六、bitmap内边、arena區(qū)域
2、arena區(qū)域按頁劃分成一個個小塊待锈。
3漠其、span管理一個或多個頁。
4竿音、mcentral管理多個span供線程申請使用
5和屎、mcache作為線程私有資源，資源來源于mcentral春瞬。