Go語(yǔ)言 內(nèi)存池

Go的內(nèi)存分配器采用了跟tcmalloc庫(kù)相同的實(shí)現(xiàn)，是一個(gè)帶內(nèi)存池的分配器，底層直接調(diào)用操作系統(tǒng)的mmap等函數(shù)。

作為一個(gè)內(nèi)存池，回憶一下跟它相關(guān)的基本部分。首先，它會(huì)向操作系統(tǒng)申請(qǐng)大塊內(nèi)存，自己管理這部分內(nèi)存。然后，它是一個(gè)池子，當(dāng)上層釋放內(nèi)存時(shí)它不實(shí)際歸還給操作系統(tǒng)，而是放回池子重復(fù)利用。接著，內(nèi)存管理中必然會(huì)考慮的就是內(nèi)存碎片問題，如果盡量避免內(nèi)存碎片，提高內(nèi)存利用率，像操作系統(tǒng)中的首次適應(yīng)，最佳適應(yīng)，最差適應(yīng)，伙伴算法都是一些相關(guān)的背景知識(shí)。另外，Go是一個(gè)支持goroutine這種多線程的語(yǔ)言，所以它的內(nèi)存管理系統(tǒng)必須也要考慮在多線程下的穩(wěn)定性和效率問題。

在多線程方面，很自然的做法就是每條線程都有自己的本地的內(nèi)存，然后有一個(gè)全局的分配鏈，當(dāng)某個(gè)線程中內(nèi)存不足后就向全局分配鏈中申請(qǐng)內(nèi)存。這樣就避免了多線程同時(shí)訪問共享變量時(shí)的加鎖。 在避免內(nèi)存碎片方面，大塊內(nèi)存直接按頁(yè)為單位分配，小塊內(nèi)存會(huì)切成各種不同的固定大小的塊，申請(qǐng)做任意字節(jié)內(nèi)存時(shí)會(huì)向上取整到最接近的塊，將整塊分配給申請(qǐng)者以避免隨意切割。

Go中為每個(gè)系統(tǒng)線程分配一個(gè)本地的MCache(前面介紹的結(jié)構(gòu)體M中的MCache域)，少量的地址分配就直接從MCache中分配，并且定期做垃圾回收，將線程的MCache中的空閑內(nèi)存返回給全局控制堆。小于32K為小對(duì)象，大對(duì)象直接從全局控制堆上以頁(yè)(4k)為單位進(jìn)行分配，也就是說(shuō)大對(duì)象總是以頁(yè)對(duì)齊的。一個(gè)頁(yè)可以存入一些相同大小的小對(duì)象，小對(duì)象從本地內(nèi)存鏈表中分配，大對(duì)象從中心內(nèi)存堆中分配。

大約有100種內(nèi)存塊類別，每一類別都有自己對(duì)象的空閑鏈表。小于32kB的內(nèi)存分配被向上取整到對(duì)應(yīng)的尺寸類別，從相應(yīng)的空閑鏈表中分配。一頁(yè)內(nèi)存只可以被分裂成同一種尺寸類別的對(duì)象，然后由空閑鏈表分配器管理。

分配器的數(shù)據(jù)結(jié)構(gòu)包括:

• FixAlloc: 固定大小(128kB)的對(duì)象的空閑鏈分配器,被分配器用于管理存儲(chǔ)
• MHeap: 分配堆,按頁(yè)的粒度進(jìn)行管理(4kB)
• MSpan: 一些由MHeap管理的頁(yè)
• MCentral: 對(duì)于給定尺寸類別的共享的free list
• MCache: 用于小對(duì)象的每M一個(gè)的cache

我們可以將Go語(yǔ)言的內(nèi)存管理看成一個(gè)兩級(jí)的內(nèi)存管理結(jié)構(gòu)，MHeap和MCache。上面一級(jí)管理的基本單位是頁(yè)，用于分配大對(duì)象，每次分配都是若干連續(xù)的頁(yè)，也就是若干個(gè)4KB的大小。使用的數(shù)據(jù)結(jié)構(gòu)是MHeap和MSpan，用BestFit算法做分配，用位示圖做回收。下面一級(jí)管理的基本單位是不同類型的固定大小的對(duì)象，更像一個(gè)對(duì)象池而不是內(nèi)存池，用引用計(jì)數(shù)做回收。下面這一級(jí)使用的數(shù)據(jù)結(jié)構(gòu)是MCache。

MHeap

MHeap層次用于直接分配較大(>32kB)的內(nèi)存空間，以及給MCentral和MCache等下層提供空間。它管理的基本單位是MSpan。MSpan是一個(gè)表示若干連續(xù)內(nèi)存頁(yè)的數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)化后如下：

    struct MSpan
    {
        PageID    start;        // starting page number
        uintptr    npages;        // number of pages in span
    };

通過(guò)一個(gè)基地址+(頁(yè)號(hào)*頁(yè)大小)，就可以定位到這個(gè)MSpan的實(shí)際的地址空間了，基地址是在MHeap中存儲(chǔ)了的。

MHeap負(fù)責(zé)將MSpan組織和管理起來(lái)，MHeap數(shù)據(jù)結(jié)構(gòu)中的重要部分如圖所示。

free是一個(gè)分配池，從free[i]出去的MSpan每個(gè)大小都i頁(yè)的,總共256個(gè)槽位。再大了之后，大小就不固定了，由large鏈起來(lái)。

分配過(guò)程： 如果能從free[]的分配池中分配，則從其中分配。如果發(fā)生切割則將剩余部分放回free[]中。比如要分配2頁(yè)大小的空間，從圖上2號(hào)槽位開始尋找，直到4號(hào)槽位有可用的MSpan，則拿一個(gè)出來(lái)，切出兩頁(yè)，剩余的部分再放回2號(hào)槽位中。 否則從large鏈表中去分配，按BestFit算法去找一塊可用空間。

化整為零簡(jiǎn)單，化零為整麻煩?；厥盏臅r(shí)候如果相鄰的塊是未使用的，要進(jìn)行合并，否則一直劃分下去就會(huì)產(chǎn)生很多碎片，找不到一個(gè)足夠大小的連續(xù)空間。因?yàn)樯婕暗胶喜?，回收?huì)比分配復(fù)雜一些，所有就有什么伙伴算法，邊界標(biāo)識(shí)算法，位示圖之類的。

Go在這里使用的類似于位示圖?？梢钥吹組Heap中有一個(gè)

    MSpan *map[1<<MHeapMap_Bits];

這個(gè)數(shù)組是一個(gè)用于將內(nèi)存地址映射成MSpan結(jié)構(gòu)體的表，每個(gè)內(nèi)存頁(yè)都會(huì)對(duì)應(yīng)到map中的一個(gè)MSpan指針，通過(guò)map就能夠?qū)⒌刂酚成涞较鄳?yīng)的MSpan。具體做法，給定一個(gè)地址，可以通過(guò)(地址-基地址)/頁(yè)大小得到頁(yè)號(hào)，再通過(guò)map[頁(yè)號(hào)]就得到了相應(yīng)的MSpan結(jié)構(gòu)體。前面說(shuō)過(guò)，MSpan就是若干連續(xù)的頁(yè)。那么，一個(gè)多頁(yè)的MSpan會(huì)占用map數(shù)組中的多項(xiàng)，有多少頁(yè)就會(huì)占用多少項(xiàng)。比如，可能map[502]到map[505]都指向同一個(gè)MSpan，這個(gè)MSpan的PageId為502，npages為4。

回收過(guò)程： 回收一個(gè)MSpan時(shí)，首先會(huì)查找它相鄰的頁(yè)的址址，再通過(guò)map映射得到該頁(yè)對(duì)應(yīng)的MSpan，如果MSpan的state是未使用，則可以將兩者進(jìn)行合并。最后會(huì)將這頁(yè)或者合并后的頁(yè)歸還到free[]分配池或者是large中。

MCache

MCache層次跟MHeap層次非常像，也是一個(gè)分配池，對(duì)每個(gè)尺寸的類別都有一個(gè)空閑對(duì)象的單鏈表。Go的內(nèi)存管理可以看成一個(gè)兩級(jí)的層次，上面一級(jí)是MHeap層次，而MCache則是下面一級(jí)。

每個(gè)M都有一個(gè)自己的局部?jī)?nèi)存緩存MCache，這樣分配小對(duì)象的時(shí)候直接從MCache中分配，就不用加鎖了，這是Go能夠在多線程環(huán)境中高效地進(jìn)行內(nèi)存分配的重要原因。MCache是用于小對(duì)象的分配。

分配一個(gè)小對(duì)象(<32kB)的過(guò)程：

1. 將小對(duì)象大小向上取整到一個(gè)對(duì)應(yīng)的尺寸類別，查找相應(yīng)的MCache的空閑鏈表。如果鏈表不空，直接從上面分配一個(gè)對(duì)象。這個(gè)過(guò)程可以不必加鎖。
2. 如果MCache自由鏈?zhǔn)强盏?通過(guò)從MCentral自由鏈拿一些對(duì)象進(jìn)行補(bǔ)充。
3. 如果MCentral自由鏈?zhǔn)强盏?則通過(guò)MHeap中拿一些頁(yè)對(duì)MCentral進(jìn)行補(bǔ)充，然后將這些內(nèi)存截?cái)喑梢?guī)定的大小。
4. 如果MHeap是空的,或者沒有足夠大小的頁(yè)了,從操作系統(tǒng)分配一組新的頁(yè)(至少1MB)。分配一大批的頁(yè)分?jǐn)偭藦牟僮飨到y(tǒng)分配的開銷。

注意上面表述中的用詞“一些”。從MCentral中拿“一些“自由鏈對(duì)象補(bǔ)充MCache分?jǐn)偭嗽L問MCentral加鎖的開銷。從MHeap中分配“一些“的頁(yè)補(bǔ)充MCentral分?jǐn)偭藢?duì)MHeap加鎖的開銷。

釋放一個(gè)小對(duì)象也是類似的過(guò)程:

1. 查找對(duì)象所屬的尺寸類別，將它添加到MCache的自由鏈。
2. 如果MCache自由鏈太長(zhǎng)或者M(jìn)Cache內(nèi)存大多了，則返還一些到MCentral自由鏈。
3. 如果在某個(gè)范圍的所有的對(duì)象都?xì)w還到MCentral鏈了，則將它們歸還到頁(yè)堆。

歸還到MHeap就結(jié)束了，目前還是沒有歸還到操作系統(tǒng)。

MCache層次僅用于分配小對(duì)象，分配和釋放大的對(duì)象則是直接使用MHeap的，跳過(guò)MCache和MCentral自由鏈。MCache和MCentral中自由鏈的小對(duì)象可能是也可能不是清0了的。對(duì)象的第2個(gè)字節(jié)作為標(biāo)記，當(dāng)它是0時(shí)，此對(duì)象是清0了的。頁(yè)堆中的總是清零的，當(dāng)一定范圍的對(duì)象歸還到頁(yè)堆時(shí)，需要先清零。這樣才符合Go語(yǔ)言規(guī)范：分配一個(gè)對(duì)象不進(jìn)行初始化，它的默認(rèn)值是該類型的零值。

MCentral

MCentral層次是作為MCache和MHeap的連接。對(duì)上，它從MHeap中申請(qǐng)MSpan；對(duì)下，它將MSpan劃分成各種小尺寸對(duì)象，提供給MCache使用。

    struct MCentral
    {
        Lock;
        int32 sizeclass;
        MSpan nonempty;
        MSpan empty;
        int32 nfree;
    };

注意，每個(gè)MSpan只會(huì)分割成同種大小的對(duì)象。每個(gè)MCentral也是只含同種大小的對(duì)象。MCentral結(jié)構(gòu)中，有一個(gè)nonempty的MSpan鏈和一個(gè)empty的MSpan鏈，分別表示還有空間的MSpan和裝滿了對(duì)象的MSpan。如圖所示： 

分配還是很簡(jiǎn)單，直接從MCentral->nonempty->freelist分配。如果發(fā)現(xiàn)freelist空了，則說(shuō)明這一塊MSpan滿了，將它移到MCentral->empty。 前面說(shuō)過(guò)，回收比分配復(fù)雜，因?yàn)樯婕暗胶喜ⅰ＿@里的合并是通過(guò)引用計(jì)數(shù)實(shí)現(xiàn)的。從MSpan中每劃出一個(gè)對(duì)象，則引用計(jì)數(shù)加一，每回收一個(gè)對(duì)象，則引用計(jì)數(shù)減一。如果減完之后引用計(jì)數(shù)為零了，則說(shuō)明這整塊的MSpan已經(jīng)沒被使用了，可以將它歸還給MHeap。

其它

本節(jié)的內(nèi)存池涉及的文件包括：

• malloc.h 頭文件
• malloc.goc 最外層的包裝
• msize.c 將各種大小向上取整到相應(yīng)的尺寸類別
• mheap.c 對(duì)應(yīng)MHeap中相關(guān)實(shí)現(xiàn),還有MSpan
• mcache.c 對(duì)應(yīng)MCache中相關(guān)實(shí)現(xiàn)
• mcentral.c 對(duì)應(yīng)MCentral中相關(guān)實(shí)現(xiàn)
• mem_linux.c SysAlloc等sys相關(guān)的實(shí)現(xiàn)