Question

堆内存包括向操作系统申请的新内存，以及垃圾回收后待复用的闲置内存。

相关分配和重用，由独立单元 pageAlloc 完成。

继 1.12 使用树堆（treap），1.13 合并树堆后，1.14 再次改进。

// mheap.go

type mheap struct {
    pages pageAlloc     // page allocation data structure
}

func (h *mheap) init() {
    h.pages.init(&h.lock, &memstats.gc_sys)
}

pageAlloc

存储堆内存元数据。

• summary : 摘要信息，用于查找操作。
• chunks : 位图数组，标记使用和释放状态。

// mpagealloc.go

// Pages are managed using a bitmap that is sharded into chunks.
// In the bitmap, 1 means in-use, and 0 means free. 

type pageAlloc struct {
    summary [summaryLevels][]pallocSum                                     // 摘要信息。
    chunks  [1 << pallocChunksL1Bits]*[1 << pallocChunksL2Bits]pallocData  // 状态位图。
}

所谓摘要，是将内存块（chunk）的 start、max、end 打包成一个 64 位整数。

// mpagealloc.go

// pallocSum is a packed summary type which packs three numbers: start, max,
// and end into a single 8-byte value. 

type pallocSum uint64

func packPallocSum(start, max, end uint) pallocSum {
    return pallocSum((uint64(start) & (maxPackedValue - 1)) |
                    ((uint64(max) & (maxPackedValue - 1)) << logMaxPackedValue) |
                    ((uint64(end) & (maxPackedValue - 1)) << (2 * logMaxPackedValue)))
}

位图使用和 heapArena 类似的稀疏数组。

// mpagealloc.go

// heapAddrBits | L1 Bits | L2 Bits | L2 Entry Size
// ------------------------------------------------
// 32           | 0       | 10      | 128 KiB
// 33 (iOS)     | 0       | 11      | 256 KiB
// 48           | 13      | 13      | 1 MiB

使用位图，意味着 heap 不再使用 span 进行管理闲置内存。

需要时，查找摘要，返回可用地址，标记相关位图即可。

如此，分割和合并，也只需更新摘要信息。

// mpallocbits.go

type pageBits   [pallocChunkPages / 64]uint64
type pallocBits pageBits

type pallocData struct {
    pallocBits             // 分配位图。
    scavenged pageBits     // 物理内存释放位图。
}

alloc

相比以前版本，分配过程更简洁明了。

// mheap.go

func (h *mheap) alloc(npages uintptr, spanclass spanClass, needzero bool) *mspan {
    s = h.allocSpan(npages, false, spanclass, &memstats.heap_inuse)
    return s
}

func (h *mheap) allocSpan(npages uintptr, manual bool, spanclass spanClass, sysStat *uint64) (s *mspan) {
    
    base, scav := uintptr(0), uintptr(0)
    
    ...
    
    // 分配内存。
    if base == 0 {
        base, scav = h.pages.alloc(npages)
        
        // 分配失败！扩张后重试。
        if base == 0 {
            if !h.grow(npages) { return nil }
            base, scav = h.pages.alloc(npages)
        }
    }
    
    // 创建 mspan，用于管理待使用内存块。
    if s == nil {
        s = h.allocMSpanLocked()
    }
    
HaveSpan:
    
    // 初始化 span 属性。
    s.init(base, npages)
    
    if manual {
        ...
    } else {
        // 设置 span 相关属性。
        s.spanclass = spanclass
        s.freeindex = 0
        s.allocCache = ^uint64(0) // all 1s indicating all free.
        s.gcmarkBits = newMarkBits(s.nelems)
        s.allocBits = newAllocBits(s.nelems)
    }
    
    // 补上被释放的物理内存。
    if scav != 0 {
        sysUsed(unsafe.Pointer(base), nbytes)
    }
    
    // 填充 heapArena.spans 反查表。
    h.setSpans(s.base(), npages, s)
}

通过查询摘要，找到符合预期的内存块（chunk）。

first-fit : 第一块（内存地址最小）大小合适（等于或大雨需求）的内存块。

Allocation is performed using an address-ordered first-fit approach.

find searches for the first (address-ordered) contiguous free region of

npages in size and returns a base address for that region.

// mpagealloc.go

func (s *pageAlloc) alloc(npages uintptr) (addr uintptr, scav uintptr) {
    
    // 超出已有块，表示内存不足，无法分配。
    if chunkIndex(s.searchAddr.addr()) >= s.end {
        return 0, 0
    }
    
    // 通过摘要搜索。
    addr, searchAddr = s.find(npages)
    if addr == 0 {
        return 0, 0
    }
    
Found:
    
    // 标记使用和释放位图，统计释放（scav）数量。
    // 更新摘要信息（pageAlloc.update）。
    scav = s.allocRange(addr, npages)
    
    return addr, scav
}

func (s *pageAlloc) allocRange(base, npages uintptr) uintptr {
    chunk := s.chunkOf(sc)
    scav += chunk.scavenged.popcntRange(si, ei+1-si)
    chunk.allocRange(si, ei+1-si)
    
    // 更新摘要信息。
    s.update(base, npages, true, true)
    
    return uintptr(scav) * pageSize
}

// mpallocbits.go

func (m *pallocData) allocRange(i, n uint) {
    // Clear the scavenged bits when we alloc the range.
    m.pallocBits.allocRange(i, n)
    m.scavenged.clearRange(i, n)
}

没找到合适内存块时，须向操作系统申请。

sysGrow 比对摘要数据，增补不足，使得 新增 + 剩余 >= 所需 。

// mpagealloc.go

func (s *pageAlloc) grow(base, size uintptr) {
    
    // 对齐（4MB），确定首位地址。
    limit := alignUp(base+size, pallocChunkBytes)
    base = alignDown(base, pallocChunkBytes)
    
    // 向操作系统申请内存。
    s.sysGrow(base, limit)      // mpagealloc_64bit.go
    
    // 更新相关管理信息。
    ...
    s.update(base, size/pageSize, true, false)
}

free

归还内存块，只需清除使用标记，更新摘要信息即可。

更新操作，会合并相邻自由空间的摘要信息。

// mheap.go

func (h *mheap) freeSpan(s *mspan) {
    h.freeSpanLocked(s, true, true)
}

func (h *mheap) freeSpanLocked(s *mspan, acctinuse, acctidle bool) {
    // 放回内存块。
    h.pages.free(s.base(), s.npages)
    
    // 释放 mspan 管理对象。
    h.freeMSpanLocked(s)
}

// mpagealloc.go

func (s *pageAlloc) free(base, npages uintptr) {
    
    sc, ec := chunkIndex(base), chunkIndex(limit)
    si, ei := chunkPageIndex(base), chunkPageIndex(limit)
    
    // 清除使用标记。
    if sc == ec {
        // The range doesn't cross any chunk boundaries.
        s.chunkOf(sc).free(si, ei+1-si)
    } else {
        // The range crosses at least one chunk boundary.
        s.chunkOf(sc).free(si, pallocChunkPages-si)
        for c := sc + 1; c < ec; c++ {
            s.chunkOf(c).freeAll()
        }
        s.chunkOf(ec).free(0, ei+1)
    }
    
    // 更新摘要。
    s.update(base, npages, true, false)
}

// mpallocbits.go

// free frees the range [i, i+n) of pages in the pallocBits.
func (b *pallocBits) free(i, n uint) {
    (*pageBits)(b).clearRange(i, n)
}

// clearRange clears bits in the range [i, i+n).
func (b *pageBits) clearRange(i, n uint) {
    ...
}