Go語言——內(nèi)存管理

參考：

圖解 TCMalloc

Golang 內(nèi)存管理

Go 內(nèi)存管理

問題

1. 內(nèi)存碎片：避免內(nèi)存碎片严沥，提高內(nèi)存利用率。
2. 多線程：穩(wěn)定性中姜，效率問題消玄。

內(nèi)存分配

內(nèi)存劃分

• arena即為所謂的堆區(qū)，應(yīng)用中需要的內(nèi)存從這里分配, 大小為512G丢胚，為了方便管理把arena區(qū)域劃分成一個個的page翩瓜，每個page為8KB,一共有512GB/8KB個頁
• spans區(qū)域存放span的指針，每個指針對應(yīng)一個page携龟，所以span區(qū)域的大小為(512GB/8KB) * 指針大小8byte = 512M
• bitmap區(qū)域大小也是通過arena計算出來512GB / (指針大小(8 byte) * 8 / 2) = 16G兔跌，用于表示arena區(qū)域中哪些地址保存了對象, 并且對象中哪些地址包含了指針，主要用于GC峡蟋。

分配細(xì)節(jié)

1. object size > 32K坟桅，則使用 mheap 直接分配。
2. object size < 16 byte层亿，不包含指針使用 mcache 的小對象分配器 tiny 直接分配桦卒；包含指針分配策略與[16 B, 32 K]類似。
3. object size >= 16 byte && size <=32K byte 時匿又，先使用 mcache 中對應(yīng)的 size class 分配方灾。
4. 如果 mcache 對應(yīng)的 size class 的 span 已經(jīng)沒有可用的塊，則向 mcentral 請求碌更。
5. 如果 mcentral 也沒有可用的塊裕偿，則向 mheap 申請，并切分痛单。
6. 如果 mheap 也沒有合適的 span嘿棘，則向操作系統(tǒng)申請。

span

可以看出span是一個非常重要的數(shù)據(jù)結(jié)構(gòu)旭绒，每個span包含若干個連續(xù)的page鸟妙。

小對象分配會在span page中劃分更小的粒度；大對象通過多頁實現(xiàn)挥吵。

size class

go1.10\src\runtime\sizeclasses.go

// 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%

//    ...
//    65      28672       57344        2           0      4.91%
//    66      32768       32768        1           0     12.50%

上表中每列含義如下：

• class： class ID重父，每個span結(jié)構(gòu)中都有一個class ID, 表示該span可處理的對象類型
• bytes/obj：該class代表對象的字節(jié)數(shù)
• bytes/span：每個span占用堆的字節(jié)數(shù)，也即頁數(shù)*頁大小
• objects: 每個span可分配的對象個數(shù)忽匈，也即（bytes/spans）/（bytes/obj）
• tail bytes: 每個span產(chǎn)生的內(nèi)存碎片房午，也即（bytes/spans）%（bytes/obj）

上表可見最大的對象是32K大小，超過32K大小的由特殊的class表示丹允，該class ID為0郭厌，每個class只包含一個對象袋倔。所以上面只有列出了1-66。

有點像裝箱算法折柠，按照規(guī)格分配宾娜，減少內(nèi)存碎片。

struct

span是內(nèi)存管理的基本單位扇售，每個span用來管子特定的size class對象碳默，根據(jù)size class，span將若干個頁分成塊進(jìn)行管理缘眶。

go1.10\src\runtime\mheap.go

type mspan struct {
    next *mspan     // next span in list, or nil if none
    prev *mspan     // previous span in list, or nil if none
   
    startAddr uintptr // address of first byte of span aka s.base()
    npages    uintptr // number of pages in span
    
    nelems uintptr // number of object in the span.
    
    allocBits  *gcBits
    gcmarkBits *gcBits
    
    allocCount  uint16     // number of allocated objects
    spanclass   spanClass  // size class and noscan (uint8)
    
    elemsize    uintptr    // computed from sizeclass or from npages
}

10

以size class 10為例嘱根，npages=1，nelems=56巷懈，spanclass=10该抒，elemsize=144；startAddr指arena區(qū)位置顶燕；next和prev指spans區(qū)凑保，span鏈表；allocBits是一個bitmap涌攻，標(biāo)記分配塊分配情況欧引，這個設(shè)計我也用過，之前用redis bitmap實現(xiàn)了IPAM恳谎。

cache

從上面我們知道go通過span來分配內(nèi)存芝此，那在哪里用span？通過之前的學(xué)習(xí)Go語言——goroutine并發(fā)模型因痛，我們知道每個P都有mcache婚苹，通過mcache管理每個G需要的內(nèi)存。

go1.10\src\runtime\mcache.go

type mcache struct {
   tiny             uintptr
   tinyoffset       uintptr
    
   alloc [numSpanClasses]*mspan // spans to allocate from, indexed by spanClass
}

numSpanClasses = _NumSizeClasses << 1
_NumSizeClasses = 67

alloc是span數(shù)組鸵膏，長度是67 << 1膊升，說明每種size class有2組元素。第一組span對象中包含了指針谭企，叫做scan廓译，表示需要gc scan；第二組沒有指針债查，叫做noscan非区。提高gc scan性能。

mcache初始沒有span攀操，G先從central動態(tài)申請span院仿，并緩存在cache秸抚。

central

go1.10\src\runtime\mcentral.go

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
}

• lock: 多個G并發(fā)從central申請span速和，所以需要lock歹垫，保證一致性
• spanclass : 每個mcentral管理著一組有相同size class的span列表
• nonempty: 指還有內(nèi)存可用的span列表
• empty: 指沒有內(nèi)存可用的span列表
• nmalloc: 指累計分配的對象個數(shù)

線程從central獲取span步驟如下：

1. 加鎖
2. 從nonempty列表獲取一個可用span，并將其從鏈表中刪除
3. 將取出的span放入empty鏈表
4. 將span返回給線程
5. 解鎖
6. 線程將該span緩存進(jìn)cache

線程將span歸還步驟如下：

1. 加鎖
2. 將span從empty列表刪除
3. 將span加入nonempty列表
4. 解鎖

heap

central只管理特定的size class span颠放，所以必然有一個更上層的數(shù)據(jù)結(jié)構(gòu)排惨，管理所有的sizeclass central，這就是heap碰凶。

go1.10\src\runtime\mheap.go

type mheap struct {
   lock      mutex
   
   spans []*mspan

   // Malloc stats.
   largealloc  uint64                  // bytes allocated for large objects
   nlargealloc uint64                  // number of large object allocations
   largefree   uint64                  // bytes freed for large objects (>maxsmallsize)
   nlargefree  uint64                  // number of frees for large objects (>maxsmallsize)
    
   // range of addresses we might see in the heap
   bitmap        uintptr // Points to one byte past the end of the bitmap
   bitmap_mapped uintptr

   arena_start uintptr
   arena_used  uintptr // Set with setArenaUsed.

   arena_alloc uintptr
   arena_end   uintptr

   arena_reserved bool

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

• spans：映射span -> page
• large：大對象暮芭，>32K
• bitmap： gc
• arena： arena區(qū)相關(guān)信息，pages欲低，堆區(qū)
• central：通過size class管理span辕宏，每種size class對應(yīng)兩個central

heap

code

前面都是背景知識，現(xiàn)在開始具體的分配過程

go1.10\src\runtime\malloc.go

注釋

小對象

• 申請

// Allocating a small object proceeds up a hierarchy of caches:
//
// 1. Round the size up to one of the small size classes
//    and look in the corresponding mspan in this P's mcache.
//    Scan the mspan's free bitmap to find a free slot.
//    If there is a free slot, allocate it.
//    This can all be done without acquiring a lock.
//
// 2. If the mspan has no free slots, obtain a new mspan
//    from the mcentral's list of mspans of the required size
//    class that have free space.
//    Obtaining a whole span amortizes the cost of locking
//    the mcentral.
//
// 3. If the mcentral's mspan list is empty, obtain a run
//    of pages from the mheap to use for the mspan.
//
// 4. If the mheap is empty or has no page runs large enough,
//    allocate a new group of pages (at least 1MB) from the
//    operating system. Allocating a large run of pages
//    amortizes the cost of talking to the operating system.

1. 將申請的內(nèi)存大小砾莱，向上取整成對應(yīng)的size class瑞筐；并且從P的mcache中找對應(yīng)的mspan。
2. 如果mspan有空閑slot腊瑟，就分配聚假。這個過程不需要lock，因為只有一個G會向P申請闰非。
3. 如果mspan沒有空閑slot膘格，就從mcentral獲取新的mspan。這個過程需要lock财松，因為會有多個G同時申請瘪贱。
4. 如果mcentral沒有mspan，就從mheap申請辆毡。
5. 如果mheap空間不足政敢，就想OS申請一組page，最少1MB胚迫。

• 釋放

// Sweeping an mspan and freeing objects on it proceeds up a similar
// hierarchy:
//
// 1. If the mspan is being swept in response to allocation, it
//    is returned to the mcache to satisfy the allocation.
//
// 2. Otherwise, if the mspan still has allocated objects in it,
//    it is placed on the mcentral free list for the mspan's size
//    class.
//
// 3. Otherwise, if all objects in the mspan are free, the mspan
//    is now "idle", so it is returned to the mheap and no longer
//    has a size class.
//    This may coalesce it with adjacent idle mspans.
//
// 4. If an mspan remains idle for long enough, return its pages
//    to the operating system.

1. 如果mspan在響應(yīng)分配時被掃描喷户，就返回mcache以滿足分配。（不是很理解）
2. 如果mspan中有分配的對象访锻，就將它放置到mcentral的free list中
3. 如果mspan空閑褪尝，就返回mheap，并且不關(guān)聯(lián)size class期犬，即變成page
4. 如果msapn空閑很久河哑，就把page還給OS，縮容龟虎。

大對象

// Allocating and freeing a large object uses the mheap
// directly, bypassing the mcache and mcentral. 

大對象都是直接操作mheap璃谨，跳過mcache和mcentral

實現(xiàn)

tiny( < 16 byte )

off := c.tinyoffset
// Align tiny pointer for required (conservative) alignment.
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)
}
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
}
// Allocate a new maxTinySize block.
span := c.alloc[tinySpanClass]
v := nextFreeFast(span)
if v == 0 {
   v, _, shouldhelpgc = c.nextFree(tinySpanClass)
}
x = unsafe.Pointer(v)
(*[2]uint64)(x)[0] = 0
(*[2]uint64)(x)[1] = 0
// See if we need to replace the existing tiny block with the new one
// based on amount of remaining free space.
if size < c.tinyoffset || c.tiny == 0 {
   c.tiny = uintptr(x)
   c.tinyoffset = size
}
size = maxTinySize

tinyoffset表示tiny當(dāng)前分配到什么地址了，之后的分配根據(jù) tinyoffset 尋址。

1. 先根據(jù)要分配的對象大小進(jìn)行地址對齊佳吞，比如size是8的倍數(shù)拱雏，tinyoffset 和 8 對齊。
2. 然后就是進(jìn)行分配底扳。如果tiny剩余的空間不夠用铸抑，則重新申請一個 16 byte 的內(nèi)存塊，并分配給 object衷模。
3. 如果新塊剩余空間比老快大鹊汛，就用新的內(nèi)存塊替換。

large（> 32 k）

var s *mspan
shouldhelpgc = true
systemstack(func() {
   s = largeAlloc(size, needzero, noscan)
})
s.freeindex = 1
s.allocCount = 1
x = unsafe.Pointer(s.base())
size = s.elemsize

func largeAlloc(size uintptr, needzero bool, noscan bool) *mspan {
   if size+_PageSize < size {
      throw("out of memory")
   }
   npages := size >> _PageShift
   if size&_PageMask != 0 {
      npages++
   }

   // Deduct credit for this span allocation and sweep if
   // necessary. mHeap_Alloc will also sweep npages, so this only
   // pays the debt down to npage pages.
   deductSweepCredit(npages*_PageSize, npages)

   s := mheap_.alloc(npages, makeSpanClass(0, noscan), true, needzero)
   if s == nil {
      throw("out of memory")
   }
   s.limit = s.base() + size
   heapBitsForSpan(s.base()).initSpan(s)
   return s
}

跳過了mspan和mcentral阱冶，直接在mheap上面分配刁憋。

normal（[16 b, 32 k]）

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])
spc := makeSpanClass(sizeclass, noscan)
span := c.alloc[spc]
v := nextFreeFast(span)
if v == 0 {
   v, span, shouldhelpgc = c.nextFree(spc)
}
x = unsafe.Pointer(v)
if needzero && span.needzero != 0 {
   memclrNoHeapPointers(unsafe.Pointer(v), size)
}

對于 size 介于 16 ~ 32K byte 的內(nèi)存分配

1. 先計算應(yīng)該分配的 sizeclass，
2. 然后去 mcache 里面 alloc[sizeclass] 申請木蹬，
3. 如果 mcache.alloc[sizeclass] 不足以申請职祷，則 mcache 向 mcentral 申請，然后再分配届囚。
4. mcentral 給 mcache 分配完之后會判斷自己需不需要擴(kuò)充有梆，如果需要則向 mheap 申請。

計算出 sizeclass意系，那么就可以去 mcache.alloc[sizeclass] 分配了泥耀，注意這是一個 mspan 指針，真正的分配函數(shù)是 nextFreeFast() 函數(shù):

// nextFreeFast returns the next free object if one is quickly available.
// Otherwise it returns 0.
func nextFreeFast(s *mspan) gclinkptr {
   theBit := sys.Ctz64(s.allocCache) // Is there a free object in the 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 >>= uint(theBit + 1)
         s.freeindex = freeidx
         s.allocCount++
         return gclinkptr(result*s.elemsize + s.base())
      }
   }
   return 0
}

allocCache 這里是用位圖表示內(nèi)存是否可用蛔添，1 表示可用痰催。然后通過 span 里面的 freeindex 和 elemsize 來計算地址即可。
當(dāng)mcache沒有可用地址時迎瞧，通過nextFree向mcentral甚至mheap申請:

func (c *mcache) nextFree(spc spanClass) (v gclinkptr, s *mspan, shouldhelpgc bool) {
   s = c.alloc[spc]
   shouldhelpgc = false
   freeIndex := s.nextFreeIndex()
    
   if freeIndex == s.nelems {
      systemstack(func() {
         c.refill(spc)
      })
      shouldhelpgc = true
      s = c.alloc[spc]

      freeIndex = s.nextFreeIndex()
   }

   if freeIndex >= s.nelems {
      throw("freeIndex is not valid")
   }

   v = gclinkptr(freeIndex*s.elemsize + s.base())
   s.allocCount++
   return
}

mcache 向 mcentral夸溶，如果 mcentral 不夠，則向 mheap 申請凶硅。

// Gets a span that has a free object in it and assigns it
// to be the cached span for the given sizeclass. Returns this span.
func (c *mcache) refill(spc spanClass) {
   _g_ := getg()

   _g_.m.locks++
   // Return the current cached span to the central lists.
   s := c.alloc[spc]

   // Get a new cached span from the central lists.
   s = mheap_.central[spc].mcentral.cacheSpan()

   c.alloc[spc] = s
   _g_.m.locks--
}