基于 Go 1.4，相關(guān)文件位于 src/runtime 目錄。文章忽略了 32bit 代碼，有興趣的可自行查看源碼文件。為便于閱讀，示例代碼做過裁剪。

1. Memory Allocator

Go 內(nèi)存分配器基于 tcmalloc 模型，這在 malloc.h 頭部注釋中有明確說明。

Memory allocator, based on tcmalloc.
http://goog-perftools.sourceforge.net/doc/tcmalloc.html

核心目標(biāo)很簡單：

• 從 mmap 申請大塊內(nèi)存，自主管理，減少系統(tǒng)調(diào)用。
• 基于塊的內(nèi)存復(fù)用體系，加快內(nèi)存分配和回收操作。

分配器以頁為單位向操作系統(tǒng)申請大塊內(nèi)存。這些大塊內(nèi)存由 n 個地址連續(xù)的頁組成，并用名為 span 的對象進(jìn)行管理。

malloc.h

PageShift" = 13,
PageSize" = 1<<PageShift, // 8192 bytes

當(dāng)需要時，span 所管理內(nèi)存被切分成多個大小相等的小塊，每個小塊可存儲一個對象，故稱作 object。

分配器以 32KB 為界，將對象分為大小兩種。

malloc.h

MaxSmallSize = 32<<10,

大對象直接找一個大小合適的 span，這個無需多言。小對象則以 8 的倍數(shù)分為不同大小等級 (size class)。比如 class1 為 8 字節(jié)，可存儲 1 ~ 8 字節(jié)大小的對象。

NumSizeClasses = 67,

當(dāng)然，實(shí)際的對應(yīng)規(guī)則并不是連續(xù)和固定的，會根據(jù)一些經(jīng)驗(yàn)和測試結(jié)果進(jìn)行調(diào)整，以獲得最佳的性能和內(nèi)存利用率。

malloc.h

// Size classes. Computed and initialized by InitSizes.
//
// SizeToClass(0 <= n <= MaxSmallSize) returns the size class,
//" 1 <= sizeclass < NumSizeClasses, for n.
//" Size class 0 is reserved to mean "not small".
//
// class_to_size[i] = largest size in class i
// class_to_allocnpages[i] = number of pages to allocate when
//" making new objects in class i

int32" runtime·SizeToClass(int32);

extern"int32" runtime·class_to_size[NumSizeClasses];
extern"int32" runtime·class_to_allocnpages[NumSizeClasses];
extern"int8" runtime·size_to_class8[1024/8 + 1];
extern"int8" runtime·size_to_class128[(MaxSmallSize-1024)/128 + 1];

為了管理好內(nèi)存，分配器使用三級組件來完成不同操作。

• heap: 全局根對象。負(fù)責(zé)向操作系統(tǒng)申請內(nèi)存，管理由垃圾回收器收回的空閑 span 內(nèi)存塊。
• central: 從 heap 獲取空閑 span，并按需要將其切分成 object 塊。heap 管理著多個central 對象，每個 central 負(fù)責(zé)處理一種等級的內(nèi)存分配需求。
• cache: 運(yùn)行期，每個 cache 都與某個具體線程相綁定，實(shí)現(xiàn)無鎖內(nèi)存分配操作。其內(nèi)部有個以等級為序號的數(shù)組，持有多個切分好的 span 對象。缺少空間時，向等級對應(yīng)的 central 獲取新的 span 即可。

簡單描述一下內(nèi)存分配和回收流程。

分配流程：

• 通過 size class 反查表計(jì)算待分配對象等級。
• 從 cache.alloc[sizeclass] 找到等級相同的 span。
• 從 span 切分好的鏈表中提取可用 object。
• 如 span 沒剩余空間，則從 heap.central[sizeclass] 找到對應(yīng) central，獲取 span。
• 如 central 沒可用 span，則向 heap 申請，并切割成所需等級的 object 鏈表。
• 如 heap 也沒有多余 span，那么就向操作系統(tǒng)申請新的內(nèi)存。

回收流程：

• 垃圾回收器或其他行為引發(fā)內(nèi)存回收操作。
• 將可回收 object 交還給所屬 span。
• 將 span 交給對應(yīng) central 管理，以便某個 cache 重新獲取。
• 如 span 內(nèi)存全部收回，那么將其返還給 heap，以便被重新切分復(fù)用。
• 垃圾回收器定期掃描 heap 所管理的空閑 spans，釋放超期不用的物理內(nèi)存。

從 heap 申請和回收 span 的過程中，分配器會嘗試合并地址相鄰的 span 塊，以形成更大內(nèi)存塊，減少碎片。

1.1 初始化

分配器管理算法依賴連續(xù)內(nèi)存地址。因此，在初始化時，分配器會預(yù)留一塊巨大的虛擬地址空間。該空間被成三個部分：

• arena: 用戶內(nèi)存實(shí)際分配范圍。
• bitmap: 為每個地址提供 4bit 標(biāo)記位，用于垃圾回收操作。
• spans: 記錄每個頁所對應(yīng) span 地址，用于反查和合并操作。

http://wiki.jikexueyuan.com/project/the-go-study-notes-fourth-edition/images/21.png" alt="" />

在 64 位系統(tǒng)下，arena 最大容量是 128GB，bitmap 8GB，spans 128MB。這些內(nèi)存并非一次性分配，而是隨著 arena 線性增加，每個區(qū)域都有指針標(biāo)記當(dāng)前分配位置。

malloc.h

struct MHeap
{
    // span lookup
    MSpan** spans;
    uintptr spans_mapped;

    // range of addresses we might see in the heap
    byte *bitmap;
    uintptr bitmap_mapped;
    byte *arena_start;
    byte *arena_used;
    byte *arena_end;
    bool arena_reserved;
};

虛擬地址預(yù)留操作并非物理內(nèi)存分配，因此看到 “Hello, World” 消耗上百 GB “內(nèi)存”，無需大驚小怪。

在運(yùn)行時初始化時，會調(diào)用內(nèi)存分配器初始化函數(shù)。

proc.c

void runtime·schedinit(void)
{
    runtime·mallocinit();
}

malloc.c

void runtime·mallocinit(void)
{
    // 初始化 size class 反查表。
    runtime·InitSizes();

    // 64-bit
    if(sizeof(void*) == 8 && (limit == 0 || limit > (1<<30))) {
        arena_size = MaxMem; // 128GB
        bitmap_size = arena_size / (sizeof(void*)*8/4); // 8GB
        spans_size = arena_size / PageSize * sizeof(runtime·mheap.spans[0]);
        spans_size = ROUND(spans_size, PageSize); // 128MB

        // 嘗試從 0xc000000000 開始設(shè)置保留地址。
        // 如果失敗，則嘗試 0x1c000000000 ~ 0x7fc000000000。
        for(i = 0; i <= 0x7f; i++) {
            p = (void*)(i<<40 | 0x00c0ULL<<32);
            p_size = bitmap_size + spans_size + arena_size + PageSize;
            p = runtime·SysReserve(p, p_size, &reserved);
            if(p != nil)
                break;
        }
    }

    // 32-bit
    if (p == nil) {
        // 忽略
    }

    // 按 PageSize 對齊地址。
    // 分配器使用 Address<<PageShift 作為 PageID。
    p1 = (byte*)ROUND((uintptr)p, PageSize);

    // 設(shè)定不同區(qū)域的起始地址。
    runtime·mheap.spans = (MSpan**)p1;
    runtime·mheap.bitmap = p1 + spans_size;
    runtime·mheap.arena_start = p1 + spans_size + bitmap_size;
    runtime·mheap.arena_used = runtime·mheap.arena_start;
    runtime·mheap.arena_end = p + p_size;
    runtime·mheap.arena_reserved = reserved;

    // 初始化 heap 和當(dāng)前 cache。
    runtime·MHeap_Init(&runtime·mheap);
    g->m->mcache = runtime·allocmcache();
}

內(nèi)存地址預(yù)留操作通過 mmap PORT_NONE 實(shí)現(xiàn)。不過，在 darwin/OSX 中，并未使用 MAP_FIXED 參數(shù)，因此未必從 0xc000000000 開始。

mem_darwin.c

void* runtime·SysReserve(void *v, uintptr n, bool *reserved)
{
    void *p;

    *reserved = true;
    p = runtime·mmap(v, n, PROT_NONE, MAP_ANON|MAP_PRIVATE, -1, 0);
    if(p < (void*)4096)
        return nil;
    return p;
}

分配器根對象 heap 的初始化工作，主要是幾個 span 管理鏈表和 central 數(shù)組的創(chuàng)建。

malloc.h

MaxMHeapList = 1<<(20 - PageShift), // Maximum page length for fixed-size list in MHeap.

struct MHeap
{
    MSpan free[MaxMHeapList]; // free lists of given length
    MSpan busy[MaxMHeapList]; // busy lists of large objects of given length

    MSpan freelarge; // free lists length >= MaxMHeapList
    MSpan busylarge; // busy lists of large objects length >= MaxMHeapList

    struct MHeapCentral {
        MCentral mcentral;
        byte pad[CacheLineSize];
    } central[NumSizeClasses];
};

其中，free 和 busy 數(shù)組以 span 頁數(shù)為序號管理多個鏈表。當(dāng) central 有需要時，只需從 free 找到頁數(shù)合適的鏈表，從中提取可用 span 即可。busy 記錄的自然是已經(jīng)被使用的 span。

至于 large 鏈表，用于保存所有超出 free/busy 頁數(shù)限制的 span。

mheap.c

void runtime·MHeap_Init(MHeap *h)
{
    uint32 i;

    // 初始化一些管理類型的固定分配器。
    runtime·FixAlloc_Init(&h->spanalloc, sizeof(MSpan), RecordSpan, ...);
    runtime·FixAlloc_Init(&h->cachealloc, sizeof(MCache), ...);
    runtime·FixAlloc_Init(&h->specialfinalizeralloc, sizeof(SpecialFinalizer), ...);
    runtime·FixAlloc_Init(&h->specialprofilealloc, sizeof(SpecialProfile), ...);

    // 初始化 free/busy 數(shù)組。
    for(i=0; i<nelem(h->free); i++) {
        runtime·MSpanList_Init(&h->free[i]);
        runtime·MSpanList_Init(&h->busy[i]);
    }

    // 初始化 large 鏈表。
    runtime·MSpanList_Init(&h->freelarge);
    runtime·MSpanList_Init(&h->busylarge);

    // 創(chuàng)建所有等級的 central 對象。
    for(i=0; i<nelem(h->central); i++)
        runtime·MCentral_Init(&h->central[i].mcentral, i);
}

像 span、cache 這類管理對象，并不從 arena 區(qū)域分配，而是使用專門的 FixAlloc 分配器單獨(dú)管理。其具體實(shí)現(xiàn)細(xì)節(jié)可參考后續(xù)章節(jié)。

在 span 內(nèi)部有兩個指針，用于將多個對象串成雙向鏈表。

malloc.h

struct MSpan
{
    MSpan *next; // in a span linked list
    MSpan *prev; // in a span linked list

    pageID start; // starting page number
    uintptr npages; // number of pages in span
    MLink *freelist; // list of free objects

    uint8 sizeclass; // size class
    uint8 state; // MSpanInUse etc
    uintptr elemsize; // computed from sizeclass or from npages
};

mheap.c

void runtime·MSpanList_Init(MSpan *list)
{
    list->state = MSpanListHead;
    list->next = list;
    list->prev = list;
}

至于 central，同樣是完成兩個 span 管理鏈表的初始化操作。其中 nonempty 鏈表保存有剩余 object 空間，等待被 cache 獲取的 span。而 empty 則保存沒有剩余空間或已被 cache 獲取的 span。

malloc.h

struct MCentral
{
    int32 sizeclass;
    MSpan nonempty; // list of spans with a free object
    MSpan empty; // list of spans with no free objects (or cached in an MCache)
};

mcentral.c

void runtime·MCentral_Init(MCentral *c, int32 sizeclass)
{
    c->sizeclass = sizeclass;
    runtime·MSpanList_Init(&c->nonempty);
    runtime·MSpanList_Init(&c->empty);
}

最后，用固定分配器創(chuàng)建 cache 對象，并初始化其 alloc 數(shù)組。

malloc.h

struct MCache
{
    MSpan* alloc[NumSizeClasses]; // spans to allocate from
};

mcache.c

// dummy MSpan that contains no free objects.
MSpan runtime·emptymspan;

MCache* runtime·allocmcache(void)
{
    // 使用固定分配器創(chuàng)建 cache 對象。
    c = runtime·FixAlloc_Alloc(&runtime·mheap.cachealloc);

    // 初始化內(nèi)存。
    runtime·memclr((byte*)c, sizeof(*c));

    // 初始化 alloc 數(shù)組，用來保存從 central 獲取的不同等級 span 對象。
    for(i = 0; i < NumSizeClasses; i++)
        c->alloc[i] = &runtime·emptymspan;

    return c;
}

1.2 分配流程

相關(guān)包裝函數(shù)，最終通過 mallocgc 函數(shù)完成內(nèi)存分配操作。

malloc.go

func newobject(typ *_type) unsafe.Pointer {
    return mallocgc(uintptr(typ.size), typ, flags)
}

func newarray(typ *_type, n uintptr) unsafe.Pointer {
    return mallocgc(uintptr(typ.size)*n, typ, flags)
}

在分配過程中，需要判斷大小對象，還有對小于 16 字節(jié)的微小對象做額外處理。

malloc.h

MaxSmallSize = 32<<10,

TinySize = 16,
TinySizeClass = 2,

malloc.go

func mallocgc(size uintptr, typ *_type, flags uint32) unsafe.Pointer {
    // 當(dāng)前 cache 對象。
    c := gomcache()

    var s *mspan
    var x unsafe.Pointer

    // 判斷是否小對象。
    if size <= maxSmallSize {
        // 對于小于 16 字節(jié)的微小對象，做額外處理。
        if flags&flagNoScan != 0 && size < maxTinySize {
            // 獲取當(dāng)前 cache tiny 塊剩余大小。
            tinysize := uintptr(c.tinysize)

            // 如果 tiny 塊空間足夠...
            if size <= tinysize {
                tiny := unsafe.Pointer(c.tiny)

                // 地址對齊。
                if size&7 == 0 {
                    tiny = roundup(tiny, 8)
                } else if size&3 == 0 {
                    tiny = roundup(tiny, 4)
                } else if size&1 == 0 {
                    tiny = roundup(tiny, 2)
                }

                // 實(shí)際大小 = 對象大小 + 對齊所需大小(對齊后地址 - 原地址)。
                size1 := size + (uintptr(tiny) - uintptr(unsafe.Pointer(c.tiny)))

                // 再次判斷空間是否足夠...
                if size1 <= tinysize {
                    // x = 對齊后地址
                    x = tiny

                    // 調(diào)整剩余空間記錄。
                    c.tiny = (*byte)(add(x, size))
                    c.tinysize -= uintptr(size1)
                    c.local_tinyallocs++

                    return x
                }
            }

            // 如果 tiny 塊空間不足，則從 alloc[2] 獲取新的 tiny/object 塊。
            s = c.alloc[tinySizeClass]
            v := s.freelist

            // 如果該 span 沒有可用 object ...
            if v == nil {
            // 從 central 獲取新的 span。
            mp := acquirem()
            mp.scalararg[0] = tinySizeClass
            onM(mcacheRefill_m)
            releasem(mp)

            // 獲取 tiny/object 塊。
            s = c.alloc[tinySizeClass]
            v = s.freelist
        }

        // 提取 tiny 塊后，調(diào)整 span.freelist 鏈表。
        s.freelist = v.next
        s.ref++

        // 初始化 tiny 塊內(nèi)存。
        x = unsafe.Pointer(v)
        (*[2]uint64)(x)[0] = 0
        (*[2]uint64)(x)[1] = 0

        // 如果新 tiny 塊剩余空間大于原 tiny 塊，那么就換一下。
        if maxTinySize-size > tinysize {
            // 調(diào)整剩余位置指針和大小。
            c.tiny = (*byte)(add(x, size))
            c.tinysize = uintptr(maxTinySize - size)
        }
        size = maxTinySize
    } else { // 普通小對象
        var sizeclass int8

        // 計(jì)算對應(yīng)的等級。
        if size <= 1024-8 {
            sizeclass = size_to_class8[(size+7)>>3]
        } else {
            sizeclass = size_to_class128[(size-1024+127)>>7]
        }
        size = uintptr(class_to_size[sizeclass])

        // 從 alloc 數(shù)組獲取對應(yīng)的 span。
        s = c.alloc[sizeclass]

        // 從 span 鏈表提取 object。
        v := s.freelist

        // 如果 span 沒有剩余 object，則從 central 獲取新的 span。
        if v == nil {
            mp := acquirem()
            mp.scalararg[0] = uintptr(sizeclass)
            onM(mcacheRefill_m)
            releasem(mp)
            s = c.alloc[sizeclass]
            v = s.freelist
        }

        // 調(diào)整 span 鏈表。
        s.freelist = v.next
        s.ref++

        // 初始化內(nèi)存。
        x = unsafe.Pointer(v)
        if flags&flagNoZero == 0 {
            v.next = nil
            if size > 2*ptrSize && ((*[2]uintptr)(x))[1] != 0 {
                memclr(unsafe.Pointer(v), size)
            }
        }
    }
    c.local_cachealloc += intptr(size)
} else { // 大對象
    mp := acquirem()
    mp.scalararg[0] = uintptr(size)
    mp.scalararg[1] = uintptr(flags)

    // 直接從 heap 分配一個適用的 span。
    // onM 是切換到 M.g0 棧執(zhí)行函數(shù)，相關(guān)細(xì)節(jié)參考后續(xù)章節(jié)。
    onM(largeAlloc_m)

    s = (*mspan)(mp.ptrarg[0])
    mp.ptrarg[0] = nil
    releasem(mp)
    x = unsafe.Pointer(uintptr(s.start << pageShift))
    size = uintptr(s.elemsize)
}

// 在 bitmap 做標(biāo)記。
{
    arena_start := uintptr(unsafe.Pointer(mheap_.arena_start))
    off := (uintptr(x) - arena_start) / ptrSize
    xbits := (*uint8)(unsafe.Pointer(arena_start - off/wordsPerBitmapByte - 1))
    shift := (off % wordsPerBitmapByte) * gcBits

    // ...
}

marked:
    // 檢查分配計(jì)數(shù)器，以決定是否觸發(fā)垃圾回收操作。
    if memstats.heap_alloc >= memstats.next_gc {
        gogc(0)
    }

    return x
}

函數(shù)雖然有點(diǎn)長，但不算太復(fù)雜。

• 盡可能將微小對象組合到一個 16 字節(jié)的 tiny 塊中，據(jù)說可提高性能。
• 小對象從 cache.alloc[] 找到等級相同的 span，并從其 freelist 鏈表獲取 object。
• 大對象直接從 heap 分配。

malloc.h

struct MCache
{
    // Allocator cache for tiny objects w/o pointers.
    byte* tiny;
    uintptr tinysize;

    MSpan* alloc[NumSizeClasses]; // spans to allocate from
};

除基本的分配操作外，還需要關(guān)注內(nèi)存不足時的 “擴(kuò)張” 過程。這需要一點(diǎn)耐心和細(xì)心。

首先，當(dāng) cache.alloc[] 中對應(yīng)的 span 沒有剩余 object 時，會觸發(fā)從 central 獲取新span 操作。

malloc.c

void runtime·mcacheRefill_m(void)
{
    runtime·MCache_Refill(g->m->mcache, (int32)g->m->scalararg[0]);
}

mcache.c

MSpan* runtime·MCache_Refill(MCache *c, int32 sizeclass)
{
    MSpan *s;

    // 當(dāng)前沒有剩余空間的 span。
    s = c->alloc[sizeclass];
    if(s->freelist != nil)
        runtime·throw("refill on a nonempty span");

    // 取消 incache 標(biāo)記。
    if(s != &runtime·emptymspan)
        s->incache = false;

    // 從 heap.central[] 數(shù)組找到對應(yīng)的 central，并獲取新的 span。
    s = runtime·MCentral_CacheSpan(&runtime·mheap.central[sizeclass].mcentral);

    // 保存到 cache.alloc 數(shù)組。
    c->alloc[sizeclass] = s;

    return s;
}

從 central 新獲取的 span 會替代原有對象，被保存到 alloc 數(shù)組中。

需要提前說明一點(diǎn)背景知識：從 Go 1.3 開始，垃圾回收算法就有很大變動。其中標(biāo)記階段需要執(zhí)行 StopTheWorld，然后用多線程并發(fā)執(zhí)行標(biāo)記操作。待標(biāo)記結(jié)束后，立即恢復(fù)StartTheWorld，用單獨(dú)的 goroutine 執(zhí)行清理操作。

因此在執(zhí)行 CacheSpan 時，某些 span 可能還未完成清理。此時主動觸發(fā)回收操作，有助于提高內(nèi)存復(fù)用率，避免向操作系統(tǒng)過度申請內(nèi)存。

malloc.h

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
h->sweepgen is incremented by 2 after every GC

mcentral.c

MSpan* runtime·MCentral_CacheSpan(MCentral *c)
{
    // 當(dāng)前垃圾回收代齡 (隨每次回收操作遞增)。
    sg = runtime·mheap.sweepgen;
retry:
    // 嘗試從 nonempty 鏈表中獲取可用 span。
    for(s = c->nonempty.next; s != &c->nonempty; s = s->next) {
        // 如果 span 標(biāo)記為等待回收，那么主動執(zhí)行清理操作。
        if(s->sweepgen == sg-2 && runtime·cas(&s->sweepgen, sg-2, sg-1)) {
            // 將 span 移動到鏈表尾部。
            runtime·MSpanList_Remove(s);
            runtime·MSpanList_InsertBack(&c->empty, s);
            // 執(zhí)行垃圾清理。
            runtime·MSpan_Sweep(s, true);
            goto havespan;
        }

        // 如果正在后臺回收，則跳過。
        if(s->sweepgen == sg-1) {
            // the span is being swept by background sweeper, skip
            continue;
        }

        // 可用 span，將其轉(zhuǎn)移到 empty 鏈表。
        runtime·MSpanList_Remove(s);
        runtime·MSpanList_InsertBack(&c->empty, s);
        goto havespan;
    }

    // 嘗試從 emtpy 鏈表獲取 span，目標(biāo)是那些等待清理的 span。
    for(s = c->empty.next; s != &c->empty; s = s->next) {
        // 如果是等待回收的 span，主動執(zhí)行回收操作。
        if(s->sweepgen == sg-2 && runtime·cas(&s->sweepgen, sg-2, sg-1)) {
            // 將該 span 移到 empty 鏈表尾部。
            runtime·MSpanList_Remove(s);
            runtime·MSpanList_InsertBack(&c->empty, s);

            // 執(zhí)行垃圾清理操作。
            runtime·MSpan_Sweep(s, true);

            // 如果回收后 freelist 鏈表不為空，表示有可用空間。
            if(s->freelist != nil)
                goto havespan;

            goto retry;
        }

        // 如果正在后臺回收，跳過。
        if(s->sweepgen == sg-1) {
            continue;
        }

        // 處理過的 span，其代齡都已經(jīng)標(biāo)記為 sg，終止嘗試。
        break;
    }

    // 如果 central 中沒有找到可用 span，則向 heap 獲取新的 span。
    s = MCentral_Grow(c);
    if(s == nil)
        return nil;

    // 將 span 插入到 empty 鏈表。
    runtime·MSpanList_InsertBack(&c->empty, s);

havespan:
    // 設(shè)置待返回 span 的相關(guān)屬性。
    cap = (s->npages << PageShift) / s->elemsize;
    n = cap - s->ref;

    // 標(biāo)記被 cache 使用。
    s->incache = true;

    return s;
}

相比 Go 1.3，cache 部分又做了很大的改進(jìn)。代碼更加簡潔，流程也更加清晰。

而當(dāng) central 空間不足時，就需要從 heap 獲取新 span 來完成擴(kuò)張操作。這其中就包括對 span 所管理內(nèi)存進(jìn)行切分，形成 object freelist 鏈表。

mcentral.c

static MSpan* MCentral_Grow(MCentral *c)
{
    MLink **tailp, *v;
    byte *p;
    MSpan *s;

    // 計(jì)算所需 span 的大小信息。
    npages = runtime·class_to_allocnpages[c->sizeclass];
    size = runtime·class_to_size[c->sizeclass];
    n = (npages << PageShift) / size;

    // 從 heap 獲取 span。
    s = runtime·MHeap_Alloc(&runtime·mheap, npages, c->sizeclass, 0, 1);
    if(s == nil)
        return nil;

    // 將 span 所管理的內(nèi)存切分成 freelist/object 鏈表。
    tailp = &s->freelist;
    p = (byte*)(s->start << PageShift); // 起始地址。PageID(start) = p >> PageShift
    s->limit = p + size*n;
    for(i=0; i<n; i++) {
        v = (MLink*)p;
        *tailp = v;
        tailp = &v->next;
        p += size;
    }
    *tailp = nil;

    // 標(biāo)記。
    runtime·markspan((byte*)(s->start<<PageShift), size, n, ...));

    return s;
}

前面在 mallocgc 中提及的大對象分配，也是用的 MHeap_Alloc 函數(shù)。

malloc.c

void runtime·largeAlloc_m(void)
{
    size = g->m->scalararg[0];
    npages = size >> PageShift;

    s = runtime·MHeap_Alloc(&runtime·mheap, npages, 0, 1, !(flag & FlagNoZero));
    g->m->ptrarg[0] = s;
}

mheap.c

MSpan* runtime·MHeap_Alloc(MHeap *h, uintptr npage, int32 sizeclass, bool large, ...)
{
    // 判斷是否在 g0 棧執(zhí)行。
    if(g == g->m->g0) {
        s = mheap_alloc(h, npage, sizeclass, large);
    } else {
        ...
    }

    return s;
}

static MSpan* mheap_alloc(MHeap *h, uintptr npage, int32 sizeclass, bool large)
{
    MSpan *s;

    // 如果垃圾回收操作未結(jié)束，那么嘗試主動收回一些空間，以避免內(nèi)存過度增長。
    // we need to sweep and reclaim at least n pages.
    if(!h->sweepdone)
        MHeap_Reclaim(h, npage);

    // 返回可用 span。
    s = MHeap_AllocSpanLocked(h, npage);
    if(s != nil) {
        // 標(biāo)記代齡等狀態(tài)。
        runtime·atomicstore(&s->sweepgen, h->sweepgen);
        s->state = MSpanInUse;
        s->freelist = nil;
        s->ref = 0;
        s->sizeclass = sizeclass;
        s->elemsize = (sizeclass==0 
        s->npages<<PageShift : runtime·class_to_size[sizeclass]);

        // 如果是大對象...
        if(large) {
            mstats.heap_objects++;
            mstats.heap_alloc += npage<<PageShift;

            // 根據(jù)頁數(shù)，插入到合適的 busy 鏈表。
            if(s->npages < nelem(h->free))
                runtime·MSpanList_InsertBack(&h->busy[s->npages], s);
            else
                runtime·MSpanList_InsertBack(&h->busylarge, s);
        }
    }

    return s;
}

從 heap 獲取 span 算法：

• 以頁數(shù)為序號，從 free[] 提取鏈表，從中返回可用 span。
• 如鏈表為空，則繼續(xù)從頁數(shù)更大的鏈表中查找。
• 如 free[] 所有鏈表均沒找到可用 span，就從 freelarge 鏈表中提取。
• 直到向操作系統(tǒng)申請新的 span 塊。

mheap.c

static MSpan* MHeap_AllocSpanLocked(MHeap *h, uintptr npage)
{
    uintptr n;
    MSpan *s, *t;
    pageID p;

    // 以頁數(shù)為序號，從 heap.free[] 中查找鏈表。
    // 如果當(dāng)前鏈表沒有可用 span，則從頁數(shù)更大的鏈表中提取。
    for(n=npage; n < nelem(h->free); n++) {
        if(!runtime·MSpanList_IsEmpty(&h->free[n])) {
            s = h->free[n].next;
            goto HaveSpan;
        }
    }

    // 如果 free 所有鏈表都沒找到合適的 span，則嘗試更大的 large 鏈表。
    if((s = MHeap_AllocLarge(h, npage)) == nil) {
        // 還沒找到，就只能新申請內(nèi)存了。
        if(!MHeap_Grow(h, npage))
            return nil;

        // 重新查找合適的 span。
        // 每次向操作系統(tǒng)申請內(nèi)存最少 1MB/128Pages，而 heap.free 最大下標(biāo) 127，
        // 因此 FreeSpanLocked 函數(shù)會將其放到 freelarge 鏈表中。
        if((s = MHeap_AllocLarge(h, npage)) == nil)
            return nil;
    }

HaveSpan:
    // 將找到的 span 從 free 鏈表中移除。
    runtime·MSpanList_Remove(s);

    // 如果該 span 曾釋放過物理內(nèi)存，那么重新映射。
    if(s->npreleased > 0) {
        runtime·SysUsed((void*)(s->start<<PageShift), s->npages<<PageShift);
        mstats.heap_released -= s->npreleased<<PageShift;
        s->npreleased = 0;
    }

    // 如果返回的 span 頁數(shù)多于需要 ...
    if(s->npages > npage) {
        // 新建一個 span 對象 t，用來管理尾部多余內(nèi)存空間。
        t = runtime·FixAlloc_Alloc(&h->spanalloc);
        runtime·MSpan_Init(t, s->start + npage, s->npages - npage);

        // 調(diào)整實(shí)際所需的內(nèi)存大小。
        s->npages = npage;
        p = t->start;
        p -= ((uintptr)h->arena_start>>PageShift);

        // 在 spans 區(qū)域標(biāo)記 span 指針。
        if(p > 0)
            h->spans[p-1] = s;
        h->spans[p] = t;
        h->spans[p+t->npages-1] = t;

        // 將切出來的多余 span，重新放回 heap 管理鏈表中。
        MHeap_FreeSpanLocked(h, t, false, false);
        s->state = MSpanFree;
    }

    // 在 spans 中標(biāo)記待所有頁對應(yīng)指針。
    p = s->start;
    p -= ((uintptr)h->arena_start>>PageShift);
    for(n=0; n<npage; n++)
        h->spans[p+n] = s;

    return s;
}

當(dāng)找到的 span 大小超出預(yù)期時，分配器會執(zhí)行切割操作，將多余的內(nèi)存做成新 span 放回 heap 管理鏈表中。

從 large 里查找 span 的算法被稱作 BestFit。很簡單，通過循環(huán)遍歷，找到大小最合適的目標(biāo)。

mheap.c

MHeap_AllocLarge(MHeap *h, uintptr npage)
{
    return BestFit(&h->freelarge, npage, nil);
}

static MSpan* BestFit(MSpan *list, uintptr npage, MSpan *best)
{
    MSpan *s;

    for(s=list->next; s != list; s=s->next) {
        if(s->npages < npage)
            continue;
        if(best == nil
        || s->npages < best->npages
        || (s->npages == best->npages && s->start < best->start))
            best = s;
    }
    return best;
}

接著看看將 span 放回 heap 管理鏈表的 FreeSpanLocked 操作。

mheap.c

static void MHeap_FreeSpanLocked(MHeap *h, MSpan *s, bool acctinuse, bool acctidle)
{
    MSpan *t;
    pageID p;
    // 修正狀態(tài)標(biāo)記。
    s->state = MSpanFree;

    // 從當(dāng)前鏈表中移除。
    runtime·MSpanList_Remove(s);

    // 這兩個參數(shù)會影響垃圾回收的物理內(nèi)存釋放操作。
    s->unusedsince = runtime·nanotime();
    s->npreleased = 0;

    // 實(shí)際地址。
    p = s->start;
    p -= (uintptr)h->arena_start >> PageShift;

    // 通過 heap.spans 檢查左側(cè)相鄰 span。
    // 如果左側(cè)相鄰 span 也是空閑狀態(tài)，則合并。
    if(p > 0 && (t = h->spans[p-1]) != nil && t->state != MSpanInUse &&
            t->state != MSpanStack) {
        // 修正屬性。
        s->start = t->start;
        s->npages += t->npages;
        s->npreleased = t->npreleased; // absorb released pages
        s->needzero |= t->needzero;

        // 新起始地址。
        p -= t->npages;

        // 重新標(biāo)記 spans。
        h->spans[p] = s;

        // 釋放左側(cè) span 原對象。
        runtime·MSpanList_Remove(t);
        t->state = MSpanDead;
        runtime·FixAlloc_Free(&h->spanalloc, t);
    }

    // 嘗試合并右側(cè) span。
    if((p+s->npages)*sizeof(h->spans[0]) < h->spans_mapped &&
        (t = h->spans[p+s->npages]) != nil &&
        t->state != MSpanInUse && t->state != MSpanStack) {
    s->npages += t->npages;
    s->npreleased += t->npreleased;
    s->needzero |= t->needzero;
    h->spans[p + s->npages - 1] = s;
    runtime·MSpanList_Remove(t);
    t->state = MSpanDead;
    runtime·FixAlloc_Free(&h->spanalloc, t);
}
    // 根據(jù) span 頁數(shù)，插入到合適的鏈表中。
    if(s->npages < nelem(h->free))
        runtime·MSpanList_Insert(&h->free[s->npages], s);
    else
        runtime·MSpanList_Insert(&h->freelarge, s);
}

在此，我們看到了 heap.spans 的作用。合并零散內(nèi)存塊，以提供更大復(fù)用空間，這有助于減少內(nèi)存碎片，是內(nèi)存管理算法的一個重要設(shè)計(jì)目標(biāo)。

最后，就是剩下如何向操作系統(tǒng)申請新的內(nèi)存了。

malloc.h

HeapAllocChunk = 1<<20," " // Chunk size for heap growth

mheap.c

static bool MHeap_Grow(MHeap *h, uintptr npage)
{
    // 每次申請的內(nèi)存總是 64KB 的倍數(shù)，最小 1MB。
    npage = ROUND(npage, (64<<10)/PageSize);
    ask = npage<<PageShift;
    if(ask < HeapAllocChunk)
        ask = HeapAllocChunk;

    // 申請內(nèi)存。
    v = runtime·MHeap_SysAlloc(h, ask);

    // 創(chuàng)建新的 span 對象進(jìn)行管理。
    s = runtime·FixAlloc_Alloc(&h->spanalloc);
    runtime·MSpan_Init(s, (uintptr)v>>PageShift, ask>>PageShift);
    p = s->start;
    p -= ((uintptr)h->arena_start>>PageShift);

    // 在 heap.spans 中標(biāo)記地址。
    h->spans[p] = s;
    h->spans[p + s->npages - 1] = s;

    // 設(shè)置狀態(tài)。
    runtime·atomicstore(&s->sweepgen, h->sweepgen);
    s->state = MSpanInUse;

    // 放回 heap 的管理鏈表，嘗試執(zhí)行合并操作。
    MHeap_FreeSpanLocked(h, s, false, true);
    return true;
}

申請時，需判斷目標(biāo)地址是否在 arena 范圍內(nèi)，且必須從 arena_used 開始。

malloc.c

void* runtime·MHeap_SysAlloc(MHeap *h, uintptr n)
{
    // 在 arena 范圍內(nèi)。
    if(n <= h->arena_end - h->arena_used) {
        // 使用 arena_used 地址。
        p = h->arena_used;
        runtime·SysMap(p, n, h->arena_reserved, &mstats.heap_sys);

        // 調(diào)整下一次分配位置。
        h->arena_used += n;

        // 同步增加 spans、bitmap 管理內(nèi)存。
        runtime·MHeap_MapBits(h);
        runtime·MHeap_MapSpans(h);

        return p;
    }

    ...
}

mem_linux.c

void runtime·SysMap(void *v, uintptr n, bool reserved, uint64 *stat)
{
    p = runtime·mmap(v, n, PROT_READ|PROT_WRITE, MAP_ANON|MAP_FIXED|MAP_PRIVATE, -1, 0);
}

mem_darwin.c

void runtime·SysMap(void *v, uintptr n, bool reserved, uint64 *stat)
{
    p = runtime·mmap(v, n, PROT_READ|PROT_WRITE, MAP_ANON|MAP_FIXED|MAP_PRIVATE, -1, 0);
}

至此，對象內(nèi)存分配和內(nèi)存擴(kuò)展的步驟結(jié)束。

1.3 釋放流程

垃圾回收器通過調(diào)用 MSpan_Sweep 函數(shù)完成內(nèi)存回收操作。

mgc0.c

bool runtime·MSpan_Sweep(MSpan *s, bool preserve)
{
    // 當(dāng)前垃圾回收代齡。
    sweepgen = runtime·mheap.sweepgen;

    arena_start = runtime·mheap.arena_start;

    // 獲取 span 相關(guān)信息。
    cl = s->sizeclass;
    size = s->elemsize;
    if(cl == 0) {
        // 大對象。
        n = 1;
    } else {
        // 小對象。
        npages = runtime·class_to_allocnpages[cl];
        n = (npages << PageShift) / size;
    }

    res = false;
    nfree = 0;
    end = &head;
    c = g->m->mcache;
    sweepgenset = false;

    // 標(biāo)記 freelist 里的 object，這些對象未被使用，無需再次檢查。
    for(link = s->freelist; link != nil; link = link->next) {
        off = (uintptr*)link - (uintptr*)arena_start;
        bitp = arena_start - off/wordsPerBitmapByte - 1;
        shift = (off % wordsPerBitmapByte) * gcBits;
        *bitp |= bitMarked<<shift;
    }

    // 釋放 finalizer、profiler 關(guān)聯(lián)對象。
    specialp = &s->specials;
    special = *specialp;
    while(special != nil) {
        // ...
    }

    // 計(jì)算標(biāo)記位開始位置。
    p = (byte*)(s->start << PageShift);
    off = (uintptr*)p - (uintptr*)arena_start;
    bitp = arena_start - off/wordsPerBitmapByte - 1;
    shift = 0;
    step = size/(PtrSize*wordsPerBitmapByte);
    bitp += step;
    if(step == 0) {
        // 8-byte objects.
        bitp++;
        shift = gcBits;
    }

    // 遍歷該 span 所有 object。
    for(; n > 0; n--, p += size) {
        // 獲取標(biāo)記位。
        bitp -= step;
        if(step == 0) {
            if(shift != 0)
                bitp--;
            shift = gcBits - shift;
        }

    xbits = *bitp;
    bits = (xbits>>shift) & bitMask;

    // 如果 object 對象標(biāo)記為可達(dá) (Marked)，則跳過。
    // 包括 freelist 里的未使用對象。
    if((bits&bitMarked) != 0) {
        *bitp &= ~(bitMarked<<shift);
        continue;
    }

    // 重置標(biāo)記位。
    *bitp = (xbits & ~((bitMarked|(BitsMask<<2))<<shift)) |
            ((uintptr)BitsDead<<(shift+2));
    if(cl == 0) { // 大對象。
        // 清除全部標(biāo)記位。
        runtime·unmarkspan(p, s->npages<<PageShift);

        // 重置代齡。
        runtime·atomicstore(&s->sweepgen, sweepgen);
        sweepgenset = true;

        if(runtime·debug.efence) {
            // ...
        } else
            // 將大對象所使用的 span 歸還給 heap。
            runtime·MHeap_Free(&runtime·mheap, s, 1);

            // 調(diào)整 next_gc 閾值。
            runtime·xadd64(&mstats.next_gc,
                -(uint64)(size * (runtime·gcpercent + 100)/100));
            res = true;
        } else { // 小對象。
            // 將可回收對象添加到一個鏈表中。
            end->next = (MLink*)p;
            end = (MLink*)p;
            nfree++;
        }
    }

    // 如可回收小對象數(shù)量大于0。
    if(nfree > 0) {
        // 調(diào)整 next_gc 閾值。
        runtime·xadd64(&mstats.next_gc,
                        -(uint64)(nfree * size * (runtime·gcpercent + 100)/100));

    // 釋放收集的 object 鏈表。
    res = runtime·MCentral_FreeSpan(&runtime·mheap.central[cl].mcentral, s, nfree,head.next, end, preserve);
    }

    return res;
}

該回收函數(shù)在分配流程 CacheSpan 中也曾提及過。

大對象釋放很簡單，調(diào)用 FreeSpanLocked 將 span 重新放回 heap 管理鏈表即可。

mheap.c

void runtime·MHeap_Free(MHeap *h, MSpan *s, int32 acct)
{
    mheap_free(h, s, acct);
}

static void mheap_free(MHeap *h, MSpan *s, int32 acct)
{
    MHeap_FreeSpanLocked(h, s, true, true);
}

至于收集的所有小對象，會被追加到 span.freelist 鏈表。如該 span 收回全部 object，則也將其歸還給 heap。

mcentral.c

bool runtime·MCentral_FreeSpan(MCentral *c, MSpan *s, int32 n, MLink *start, ...)
{
    // span 不能是 cache 正在使用的對象。
    if(s->incache)
        runtime·throw("freespan into cached span");

    // 將收集的 object 鏈表追加到 span.freelist。
    wasempty = s->freelist == nil;
    end->next = s->freelist;
    s->freelist = start;
    s->ref -= n;

    // 將 span 轉(zhuǎn)移到 central.nonempty 鏈表。
    if(wasempty) {
        runtime·MSpanList_Remove(s);
        runtime·MSpanList_Insert(&c->nonempty, s);
    }

    // 重置回收代齡。
    runtime·atomicstore(&s->sweepgen, runtime·mheap.sweepgen);

    if(s->ref != 0) {
        return false;
    }

    // 如果 span 收回全部 object (span.ref == 0)，從 central 管理鏈表移除。
    runtime·MSpanList_Remove(s);
    s->needzero = 1;
    s->freelist = nil;

    // 清除標(biāo)記位。
    runtime·unmarkspan((byte*)(s->start<<PageShift), s->npages<<PageShift);

    // 將 span 交還給 heap。
    runtime·MHeap_Free(&runtime·mheap, s, 0);
    return true;
}

釋放操作最終結(jié)果，僅僅是將可回收對象歸還給 span.freelist 或 heap.free 鏈表，以便后續(xù)分配操作復(fù)用。至于物理內(nèi)存釋放，則由垃圾回收器的特殊定時操作完成。

1.4 其他

除了用戶內(nèi)存，分配器還需額外的 span、cache 等對象來維持系統(tǒng)運(yùn)轉(zhuǎn)。這些管理對象所需內(nèi)存不從 arena 區(qū)域分配，不占用與 GC Heap 分配算法有關(guān)的內(nèi)存地址。

系統(tǒng)為每種管理對象初始化一個固定分配器 FixAlloc。

malloc.h

struct FixAlloc
{
    uintptr size; // 固定分配長度。
    void (*first)(void *arg, byte *p); // 關(guān)聯(lián)函數(shù)。
    void* arg; // first 函數(shù)調(diào)用參數(shù)。
    MLink* list; // 可復(fù)用空間鏈表。
    byte* chunk; // 后備內(nèi)存塊當(dāng)前分配指針。
    uint32 nchunk; // 后備內(nèi)存塊可用長度。
    uintptr inuse; // 后備內(nèi)存塊已使用長度。
};

mheap.c

void runtime·MHeap_Init(MHeap *h)
{
    runtime·FixAlloc_Init(&h->spanalloc, sizeof(MSpan), RecordSpan, ...);
    runtime·FixAlloc_Init(&h->cachealloc, sizeof(MCache), nil, ...);
    runtime·FixAlloc_Init(&h->specialfinalizeralloc, sizeof(SpecialFinalizer), ...);
    runtime·FixAlloc_Init(&h->specialprofilealloc, sizeof(SpecialProfile), ...);
}

FixAlloc 初始化過程很簡單。

mfixalloc.c

void runtime·FixAlloc_Init(FixAlloc *f, uintptr size,
            void (*first)(void*, byte*), void *arg, uint64 *stat)
{
    f->size = size;
    f->first = first;
    f