Question

在 mcache 里使用数组存储不同类别（sizeclass）的 span 内存块。

// mcache.go

// Per-thread (in Go, per-P) cache for small objects.
// No locking needed because it is per-thread (per-P).

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

索引

数组（mcache.alloc）长度是类别（sizeclass）的 2 倍。

每种类别按是否包含指针分 scan 和 noscan 两种，如此有助于 GC 优化。

// mheap.go

numSpanClasses = _NumSizeClasses << 1

所对应数组索引按以下算法计算：

spanclass = (sizeclass << 1) | noscan

// mheap.go

func makeSpanClass(sizeclass uint8, noscan bool) spanClass {
    return spanClass(sizeclass<<1) | spanClass(bool2int(noscan))
}

比如说，sizeclass 3：

scan : (0b11 << 1) | 0 == 0b110 == 6

noscan : (0b11 << 1) | 1 == 0b111 == 7

// malloc.go

func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {

    // 确定是否需要扫描。
    noscan := typ == nil || typ.kind&kindNoPointers != 0
    
    if size <= maxSmallSize {
        if noscan && size < maxTinySize {
            ... 微小对象 ...
        } else {
            // 小对象 ...
            
            // 计算 sizeclass，根据 noscan 转换为 spanclass，以获得索引号。
            var sizeclass uint8
            if size <= smallSizeMax-8 {
                sizeclass = size_to_class8[divRoundUp(size, smallSizeDiv)]
            } else {
                sizeclass = size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]
            }
            
            // 计算索引。
            size = uintptr(class_to_size[sizeclass])
            spc := makeSpanClass(sizeclass, noscan)
            
            // 从数组中获取指定等级的 span。
            span = c.alloc[spc]
            
            // 从 span 提取 object。
            v := nextFreeFast(span)
            if v == 0 {
                v, span, shouldhelpgc = c.nextFree(spc)
            }
            x = unsafe.Pointer(v)
        }
    } else {
        ... 大对象 ...
    }
    
    return x
}

提取

因为每个 span 仅为一种 sizeclass 服务，所以内部 object 等长。

通过地址偏移就可以划分出多个 object 块，类似数组。

// mheap.go

type mspan struct {
    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.
    spanclass  spanClass   // size class and noscan (uint8)
    
    freeindex  uintptr
    allocCache uint64
    
    allocBits  *gcBits
    gcmarkBits *gcBits
}

位图 allocBits 标记了 object 使用状况。

使用 freeindex 记录上次扫描位置，以此为顺序分配起点。

同时 allocCache 缓存 freeindex 后数据片段，以实现更高访问效率。

依据 allocBits 位图，将整个 span 内存当作 object 数组进行访问。

// malloc.go

// nextFree returns the next free object from the cached span if one is available.

func (c *mcache) nextFree(spc spanClass) (v gclinkptr, s *mspan, shouldhelpgc bool) {
 
    // 获取下一个可用 object 索引。
    s = c.alloc[spc]
    freeIndex := s.nextFreeIndex()
    
    // 如果没有剩余空间。
    if freeIndex == s.nelems {
        // 向 central 申请新 span，然后重试。
        c.refill(spc)
        s = c.alloc[spc]
        freeIndex = s.nextFreeIndex()
    }
    
    // 用索引计算出内存地址。
    v = gclinkptr(freeIndex*s.elemsize + s.base())
    
    return
}

问题关键是 freeindex 和 allocBits 的工作方式。

freeindex           
                           |           
                           v           
              +---//---+---+---+---+---+-----//----+
    allocBits |  ...   | 1 | 0 | . | 0 |     ...   |
              +---//---+---+---+---+---+-----//----+
                           |           |
                           |           |
                           +---+---+---+
                allocCache | 1 | . | 1 |
                           +---+---+---+

allocCache 从 freeindex 起，缓存 64 个二进制标记位。

相比跨字节位图，64 位整数可被寄存器存储，拥有更好访问效率。

从 allocCache 检索到可用位置，加上 freeindex 就是在 allocBits 位图里的实际索引。

注意：

allocBits 由 gcmarkBits 交换而来，内部存储是垃圾回收标记结果，故 0 才是可用位置。

填充 allocCache 时，进行反转，1 表示可用。

因为 allocCache 通过统计低位 0 数量找到第一可用位 1。

找到后，allocCache 右移，剔除掉已扫描过的低位。

如此，下次可继续通过统计低位 0 查找可用位。

右移同时，须更新 freeindex。

               H           L
  allocCache:  11...11000100     // 统计低位 0 数量，找到第一个 1。

1. 统计（Ctz64）低位（L）二进制 0 数量，确定第一个可用位 bitIndex = 2 。

2. 计算基于位图的实际索引 result = freeindex + bitIndex 。

3. 右移 allocCache，剔除掉已扫描过的低位。 allocCache >> (bitIndex + 1) ，含本次。

4. 更新 freeindex，否则下次计算偏移位置错误。

               H           L
  allocCache:  00011...11000     // 右移剔除掉低位 100 后的结果。

正因为右移操作，才需要在填充缓存时反转。毕竟 0000 怎么右移都没有变化，1111 就成了 0111。

// mbitmap.go

// nextFreeIndex returns the index of the next free object in s at
// or after s.freeindex.

func (s *mspan) nextFreeIndex() uintptr {
    
    sfreeindex := s.freeindex
    snelems := s.nelems
    
    // 没有可用空间。
    if sfreeindex == snelems {
        return sfreeindex
    }
    
    // 从缓存查找第一个可用位。
    aCache := s.allocCache
    bitIndex := sys.Ctz64(aCache)  // 统计低位 0 数量。
    
    // 无可用位，刷新缓存。（刷新后未必有可用位，循环填充）
    for bitIndex == 64 {
        
        // 计算填充位置，或超出当前 span 范围。
        sfreeindex = (sfreeindex + 64) &^ (64 - 1)
        if sfreeindex >= snelems {
            s.freeindex = snelems
            return snelems
        }
        
        // 填充缓存，重试。
        whichByte := sfreeindex / 8
        s.refillAllocCache(whichByte)
        aCache = s.allocCache
        bitIndex = sys.Ctz64(aCache)
    }
    
    // 基于位图，计算索引。
    result := sfreeindex + uintptr(bitIndex)
    if result >= snelems {
        s.freeindex = snelems
        return snelems
    }
    
    // 右移缓存，并调整 freeindex。
    s.allocCache >>= uint(bitIndex + 1)
    sfreeindex = result + 1
    s.freeindex = sfreeindex
    
    return result
}

优先使用快速版本，仅检查缓存。没有无关调用，不填充，不扩容，一切为了性能。

// malloc.go

// nextFreeFast returns the next free object if one is quickly available.

func nextFreeFast(s *mspan) gclinkptr {
    
    // 统计缓存内 0 数量。
    theBit := sys.Ctz64(s.allocCache)
    
    if theBit < 64 {
        // 计算位图索引。
        result := s.freeindex + uintptr(theBit)
        
        if result < s.nelems {
            
            // 调整相关数据（缓存右移，更新 freeindex）
            freeidx := result + 1
            s.allocCache >>= uint(theBit + 1)
            s.freeindex = freeidx
            
            // 计算并返回内存地址。
            return gclinkptr(result*s.elemsize + s.base())
        }
    }
    
    return 0
}

扩容

如果 cache 内对应 span 没有剩余空间，那么需要从 central 扩容。

// mcache.go

// refill acquires a new span of span class spc for c. This span will
// have at least one free object. The current span in c must be full.

func (c *mcache) refill(spc spanClass) {
    
    // 解除当前 span 状态。
    s := c.alloc[spc] 
    if s != &emptymspan {
        // 通过调整代龄，表示不再被 mcache 持有。
        atomic.Store(&s.sweepgen, mheap_.sweepgen)
    }
    
    // 从 central 获取新的 span，设置代龄表示被 mcache 使用。
    s = mheap_.central[spc].mcentral.cacheSpan()
    s.sweepgen = mheap_.sweepgen + 3
    c.alloc[spc] = s
}

与 cache 类似， central 同样分 scan、noscan 两类。

// mheap.go

type mheap struct {
    // central is indexed by spanClass.
    central [numSpanClasses]struct {
        mcentral mcentral
    }
}

1.15 重构了 mcentral，使用新的结构管理内存块。

// mcentral.go

// Central list of free objects of a given size.

type mcentral struct {
    spanclass spanClass
    
	partial [2]spanSet   // list of spans with a free object
	full    [2]spanSet   // list of spans with no free objects
}

无论 partial，还是 full，都有两个 spanSet 集合，分别表示已清理（swept）和未清理（unswept）。

访问时：

swept =partial[sweepgen/2%2]

unswept = partial[1-sweepgen/2%2]

随着回收代龄的增加（+2/per），两个集合的角色会互相调换。

gen 0: swept = 0/2%2 = 0, unswept = 1 - 0/2%2 = 1

gen 2: swept = 2/2%2 = 1, unswept = 1 - 2/2%2 = 0

gen 4: swept = 4/2%2 = 0, unswept = 1 - 4/2%2 = 1

// mcentral.go

func (c *mcentral) partialSwept(sweepgen uint32) *spanSet {
	return &c.partial[sweepgen/2%2]
}

每个 span 都有一个与垃圾回收相关的代龄状态标记。

// mheap.go

type mspan struct {
    
    // 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
    // if sweepgen == h->sweepgen + 1, the span was cached before sweep began and is still cached, and needs sweeping
    // if sweepgen == h->sweepgen + 3, the span was swept and then cached and is still cached
    // h->sweepgen is incremented by 2 after every GC
    sweepgen    uint32
    
}

+0: 正常状态，清理完成等待使用。

+1: 上一周期被 cache 拿走尚在使用的。（上一周期的 +3，因为当前 gen += 2 才变成 +1 的）

+3: 被 cache 拿走，正在使用的。

-2: 新周期开始，从 0 - 2 转变，需要清理。

-1: 正在清理状态。结束后被调整为 0。

依次尝试 partial swept、partial unswept、full unswept 集合查找，直到从 heap 重新分配。

鉴于清理操作动作较大，未避免花费太多时间，采取了尝试总次数限制。

// mcentral.go

// Allocate a span to use in an mcache.

func (c *mcentral) cacheSpan() *mspan {
    
    if !go115NewMCentralImpl {
        return c.oldCacheSpan()
    }
    
	// 尝试总次数限制。
    // 超出，则直接分配新的 span。
    // 避免查找可用空间花费太多时间。
    spanBudget := 100
    
    var s *mspan
    
    // 直接从 partail swept 集合提取。
    if s = c.partialSwept(sg).pop(); s != nil {
        goto havespan
    }
    
	// 尝试从 partail unswept 集合提取。
	for ; spanBudget >= 0; spanBudget-- {
        
        s = c.partialUnswept(sg).pop()
        if s == nil {
            break
        }
        
        // 检查并修改 sweepgen 状态。
        if atomic.Load(&s.sweepgen) == sg-2 && atomic.Cas(&s.sweepgen, sg-2, sg-1) {
            s.sweep(true)
            goto havespan
        }
	}
    
	// 尝试 full unswept 集合。
	for ; spanBudget >= 0; spanBudget-- {
        
        s = c.fullUnswept(sg).pop()
        if s == nil {
            break
        }
        
        // 检查并修改 sweepgen 状态。
        if atomic.Load(&s.sweepgen) == sg-2 && atomic.Cas(&s.sweepgen, sg-2, sg-1) {
            s.sweep(true)
            
            // 检查是否有剩余空间。
            freeIndex := s.nextFreeIndex()
            if freeIndex != s.nelems {
                s.freeindex = freeIndex
                goto havespan
            }
            
            // 没有剩余空间，加入 full swept 集合。
            c.fullSwept(sg).push(s)
        }
    }
    
	// 无法从 central 获取，那么直接从 heap 分配。
    s = c.grow()
    if s == nil {
        return nil
    }
    
havespan:
    
    // 初始化相关状态...
    
    return s
}

func (c *mcentral) grow() *mspan {
    s := mheap_.alloc(npages, c.spanclass, true)
    return s
}

垃圾回收时会调用 flushmcache 将 cache 所持有的 span 全部归还给所属 central。

如此，central 就持有部分剩余空间的 span。

当然，这不影响将其交给其他 cache 使用，毕竟 object 没有地址重叠。