golang的內存分配

本篇文章主要介紹golang的內存分配，文中關于內存分配的算法以及mcache的介紹均以實例展示，有需要的朋友可以參考一下。

• 程序內存大致可以分為5個段text、data、bss、stack、heap

• 其中text段用于程序指令、文字、靜態常量

• data與bss段用于存儲全局變量

• stack段用于存儲函數調用與函數內的變量，stack段的數據可以被CPU快速訪問，stack段的大小在運行時是不能增加和減少的，銷毀只是通過棧指針的移動來實現的。同時，這也是為什么程序有時候會報錯stack overflow的原因。

• stack段的內存分配是編譯器實現的，我們無需關心。同時stack通常的大小是有限的。

• 因此對于大內存的分配，或者想手動創建或釋放內存，就只能夠對heap段進行操作，這就是俗稱的動態分配內存。例如c語言中的malloc、calloc、free以及C++中的new、delete

• 內存的分配屬于操作系統級別的操作、因此不管是cc++語言的分配，最后都需要調用操作系統的接口。以linux為例，malloc代碼可能調用了操作系統接口mmap分配內存

• linux操作系統提供的內存分配接口如下：

  • mmap/munmap 映射/釋放 指定大小的內存.

  • brk/sbrk – 改變`data`段`結束的位置來擴展heap段的內存

  • madvise – 給操作系統建議如何管理內存

  • set_thread_area/get_thread_area – 操作線程本地存儲空間

• 動態內存分配是操作系統為我們做的事情，其效率直接影響到運行在操作系統上的程序。對于一般的程序來說，例如c語言中實現的malloc,最后都是通過調用操作系統的接口來實現的。

• 動態內存的調度是一個艱難復雜的話題，其要實現的目標包括：

  • 快速分配和釋放

  • 內存開銷小

  • 使用所有內存

  • 避免碎片化

• 內存分配的算法包括了：

  • K&R malloc

  • Region-based allocator

  • Buddy allocator

  • dlmalloc

  • slab allocator

• 同時，由于算法解決的目標等不同，還會有不同的變種，其他的目標包括：

  • 內存開銷小（例如buddy的元數據很大）

  • 良好的內存位置

  • cpu核心增加時，擴展性好

  • 并發malloc / free

• GO語言在進行動態內存分配時，實質調用了上面的操作系統接口。由于Go語言并沒有調用c語言的malloc等函數來分配，組織內存，因此，其必須實現自己的內存組織和調度方式。

• GO語言借鑒了TCMalloc(Thread-Caching Malloc)的內存分配方式

TCMalloc(Thread-Caching Malloc)

• TCMalloc是一種內存分配算法，比GNU C庫中的malloc要快2倍，正如其名字一樣，其是對于每一個線程構建了緩存內存。

• TCMalloc解決了多線程時內存分配的鎖競爭問題

• TCMalloc對于小對象的分配非常高效

• TCMalloc的核心思想是將內存劃分為多個級別，以減少鎖的粒度。在TCMalloc內部，內存管理分為兩部分：小對象內存（thread memory）和大對象內存（page heap）。

• 小對象內存管理將內存頁分成多個固定大小的可分配的free列表。因此，每個線程都會有一個無鎖的小對象緩存，這使得在并行程序下分配小對象（<= 32k）非常有效。下圖的對象代表的是字節。

• 分配小對象時
  

  • 我們將在相同大小的線程本地free list中查找，如果有，則從列表中刪除第一個對象并返回它

  • 如果free list中為空，我們從中央free list中獲取對象（中央free list由所有線程共享），將它們放在線程本地free list中，并返回其中一個對象

  • 如果中央free list也為空，將從中央頁分配器中分配內存頁，并將其分割為一組相同大小的對象，并將新對象放在中央free list中。和之前一樣，將其中一些對象移動到線程本地空閑列表中

• 大對象內存管理由頁集合組成，將其稱為頁堆（page heap）當分配的對象大于32K時，將使用大對象分配方式。

• 第k個free list列表是包含k大小頁的free list。第256個列表比較特殊，是長度大于等于256頁的free list。

• 分配大對象時，對于滿足k大小頁的分配
  

  • 我們在第k個free list中查找

  • 如果該free list為空，則我們查找下一個更大的free list，依此類推，最終，如有必要，我們將查找最后一個空閑列表。如果更大的free list符合條件，則會進行內存分割以符合當前大小。

  • 如果失敗，我們將從操作系統中獲取內存。

• 內存是通過連續頁（稱為Spans）的運行來管理的（Go也根據Spans來管理內存）

• 在TCMalloc中，span有兩種狀態，已分配或是free狀態。如果為free，則span是位于頁堆列表中的一個。如果已分配，則它要么是已移交給應用程序的大對象，要么是已分成多個小對象的序列。
  

• go內存分配器最初是基于TCMalloc的

• Go allocator與TCMalloc類似，內存的管理由一系列頁（spans/mspan對象）組成，使用（線程/協程）本地緩存并根據內存大小進行劃分。

mspan

• 在go語言中，Spans是8K或更大的連續內存區域。可以在runtime/mheap.go中對應的mspan結構

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
    nelems uintptr // number of object in the span.
    allocCache uint64
    allocBits  *gcBits
    gcmarkBits *gcBits
    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有三種類型，分別是：
  

  • idle：沒有對象，可以釋放回操作系統；或重新用于堆內存；或重新用于棧內存

  • in use：至少具有一個堆對象，并且可能有更多空間

  • stack：用于協程棧。可以存在于棧中，也可以存在于堆中，但不能同時存在于兩者中。

mcache

• Go 像 TCMalloc 一樣為每一個 邏輯處理器（P）（Logical Processors） 提供一個本地線程緩存（Local Thread Cache）稱作 mcache，所以如果 Goroutine 需要內存可以直接從 mcache 中獲取，由于在同一時間只有一個 Goroutine 運行在 邏輯處理器（P）（Logical Processors） 上，所以中間不需要任何鎖的參與。mcache 包含所有大小規格的 mspan 作為緩存。

• 對于每一種大小規格都有兩個類型：

  • scan -- 包含指針的對象。

  • noscan -- 不包含指針的對象。

• 采用這種方法的好處之一就是進行垃圾回收時 noscan 對象無需進一步掃描是否引用其他活躍的對象。

mcentral

• mcentral是被所有邏輯處理器共享的

• mcentral 對象收集所有給定規格大小的 span。每一個 mcentral 都包含兩個 mspan 的列表：

  • empty mspanList -- 沒有空閑對象或 span 已經被 mcache 緩存的 span 列表

  • nonempty mspanList -- 有空閑對象的 span 列表

• 每一個 mcentral 結構體都維護在 mheap 結構體內。

mheap

• Go 使用 mheap 對象管理堆，只有一個全局變量。持有虛擬地址空間。

• 就上我們從上圖看到的：mheap 存儲了 mcentral 的數組。這個數組包含了各個的 span 的 mcentral。

central [numSpanClasses]struct {
    mcentral mcentral
    pad      [unsafe.Sizeof(mcentral{})%sys.CacheLineSize]byte
}

• 由于我們有各個規格的 span 的 mcentral，當一個 mcache 從 mcentral 申請 mspan 時，只需要在獨立的 mcentral 級別中使用鎖，所以其它任何 mcache 在同一時間申請不同大小規格的 mspan 將互不受影響可以正常申請。

• pad為格外增加的字節。對齊填充（Pad）用于確保 mcentrals 以 CacheLineSize 個字節數分隔，所以每一個 MCentral.lock 都可以獲取自己的緩存行（cache line），以避免偽共享（false sharing）問題。

• 圖中對應的free[_MaxMHeapList]mSpanList：一個 spanList 數組。每一個 spanList 中的 mspan 包含 1 ~ 127（_MaxMHeapList - 1）個頁。例如，free[3] 是一個包含 3 個頁的 mspan 鏈表。free 表示 free list，表示未分配。對應 busy list。

• freelarge mSpanList：一個 mspan 的列表，每一個元素(mspan)的頁數大于 127，通過 mtreap 結構體管理。busylarge與之相對應。

• 在進行內存分配時，go按照大小分成3種對象類
  

  • 小于16個字節的對象Tiny類

  • 適用于最大32 kB的Small類

  • 適用于大對象的large類

• Small類會被分為大約有70個大小，每一個大小都擁有一個free list

• 引入Tiny這一微小對象是為了適應小字符串和獨立的轉義變量。

• Tiny微小對象將幾個微小的分配請求組合到一個16字節的內存塊中

• 當分配Tiny對象時：
  

  • 查看協程的mcache的相應tiny槽

  • 根據分配對象的大小，將現有子對象（如果存在）的大小四舍五入為8、4或2個字節

  • 如果當前分配對象與現有tiny子對象適合，請將其放置在此處

• 如果tiny槽未發現合適的塊：
  

  • 查看協程的mcache中相應的mspan

  • 掃描mspan的bitmap以找到可用插槽

  • 如果有空閑插槽，對其進行分配并將其用作新的小型插槽對象（這一切都可以在不獲取鎖的情況下完成）

• 如果mspan沒有可用插槽：
  

  • 從mcentral的所需大小類的mspan列表中獲得一個新的mspan

• 如果mspan的列表為空：
  

  • 從mheap獲取內存頁以用于mspan

• 如果mheap為空或沒有足夠大的內存頁
  

  • 從操作系統中分配一組新的頁（至少1MB）

  • Go 會在操作系統分配超大的頁（稱作 arena），分配大量內存頁將分攤與OS溝通的成本

• small對象分配與Tiny對象類似，

• 分配和釋放大對象直接使用mheap，就像在TCMalloc中一樣，管理了一組free list

• 大對象被四舍五入為頁大小（8K）的倍數，在free list中查找第k個free list，如果其為空，則繼續查找更大的一個free list，直到第128個free list

• 如果在第127個free list中找不到，我們在剩余的大內存頁（mspan.freelarge字段）中查找跨度，如果失敗，則從操作系統獲取。

• 關于golang的內存分配就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果喜歡這篇文章，不如把它分享出去讓更多的人看到。