Go語言 內(nèi)存池

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

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

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

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

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

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

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

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

MHeap

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

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

通過一個基地址+(頁號*頁大小)，就可以定位到這個MSpan的實際的地址空間了，基地址是在MHeap中存儲了的。

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

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

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

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

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

    MSpan *map[1<<MHeapMap_Bits];

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

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

MCache

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

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

分配一個小對象(<32kB)的過程：

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

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

釋放一個小對象也是類似的過程:

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

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

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

MCentral

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

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

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

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

其它

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

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