# 页面分配器

页面分配器把整个虚拟地址空间划分（假想的）成一个个8KB对齐的大小为8KB的页面，分配器采用位图管理页面分配情况。因为虚拟地址空间过于庞大，所以对位图做了划分，每512个页面，使用一个位图。

type pageAlloc struct {
    summary [summaryLevels][]pallocSum
    chunks [1<< pallocChunksL1Bits]*[1 << pallocChunksL2Bits]pallocData
    searchAddr offAddr
    start,end chunkIdx
    inUse addrRanges
    scav struct {
        inUse addrRanges
        gen uint32
        reservationBytes uintptr
        released uintptr
        scavLWM offAddr
        freeHWM offAddr
    }
    mheapLock *mutex
    sysStat *uint64
    test bool
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# Chunks

位图的存放与chunks相关，chunks 是一个维数组，第一维存的是指向第二维数组的指针，第二维数组中存的是pallocData结构，这个结构中存放着两种位图，下图所示

chunks

chunks 一维二维的大小与平台相关，对于64位架构来说，其虚拟地址空间地址长度是48位的（虽然现在已经有硬件支持到57位地址，但是只有linux 操作系统支持这种硬件，并且linux 内核在选取mmap地址的时候不会考虑高于1 << 47 的，除非是用户自己指定这样的地址）。下表列出了不同地址长度的虚拟地址空间的chunks数组的大小。上图是根据48位地址长度绘制的。

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

1
2
3
4
5

一个pallocData 存放着512个连续页面的位图信息，包括是否分配和是否释放两种位图，512个页面两种位图总共占用16个uint64，耗费128个字节。对于地址长度是48位的平台来说，第一维会占用64KB的大小（指针长度8字节，2^13个指针），而第二维数组用的时候才开辟，一次性占用1MB（2^13 * sizeof(pallocData)）。chunks 的设计相比所有的位图放在一起，节省了大量空间。

# Summary

页面分配器的数据结构中，还有一个叫summary的结构，这个结构是用于加速寻找指定长度的连续空闲页面的

summary 是一颗数组实现的radix tree，这棵树高度为5层，如下图所示。这棵树的每一层，都能够完整的表示整个虚拟地址空间(虽然图中画的上窄下宽)，只不过表示的粒度不同。以虚拟地址长度48位为例子做讨论，summary的第一层有2^14个节点，节点 i 中存储着虚拟地址介于 [( 2^ 48 / 2 ^ 14) * (i - 1),( 2^ 48 / 2 ^ 14) * i) 这块虚拟地址空间的页面信息。第二层到最后一层与第一层一样，每个节点存的信息都是同等类型的，不过第二层到最后一层节点数逐层递增，每层是上一层的8倍，可以理解为把上一层的某个节点表示的一段虚拟地址空间做了更细的划分，分成了8份。最后一层一个节点表示的虚拟地址空间长度与chunks中的pallocData相同，是512个页面的大小

summary

每一层的节点里边存放的数据都是pallocSum，pallocSum是一个uint64类型的值，里边压缩存储了三个信息，start、max、end，分别代表了所表示的这块虚拟地址空间起始连续空闲页面的个数、最大连续空闲页面个数、末尾连续最大空闲页面个数。下图是一个pallocSum的一个简单示意

pallocSum

pallocSum是uint64，总共有64位，start max enx分别占用21位，剩下的一位如果是1的话，表示start max end 都是 2^21，在64为系统下，树上最高一层的节点表示的空间大小就是2^21个页面

# 查询

查询若干连续空闲页面的过程，需要先从第一层开始查询，顺序扫描每个节点，每个节点的start可以和前一个节点（如果有的话）的end组成长度为start + end 的连续空闲页面，如果这不能够满足分配需求的话，就查看节点的max是否能满足需求，如果满足就进入到下层继续搜索，否则继续沿着该层继续搜索其他节点。

query
以上图为例子、只做简单示意，图中只绘制了两层，第一层只保留一个节点
如果要寻找8个连续的空闲页面，在搜索第一层的节点，发现其start 满足搜索条件，则停止搜索。如果要寻找连续40个空闲页面，第一层max是75，满足40个空闲页面的需求，则进入下层搜索。下层第一个节点的end与第二个节点的start 总共是64个连续页面，搜索结束。

# 更新

当查询到有可满足需求的连续页面时，或者是当页面被回收释放的时候，需要更新对应范围内的summary，更新从最第层开始，逐层更新到最顶层，如果某一层更新前后pallocSum不变，就不需要继续更新上一层了。
对于最底部的层，重新计算pallocSum的方式需要操作pallocData中的pallocBits，pallocBits 由8个uint64组成，总共512位。但是计算start end 和 max 并不会逐位扫描，计算过程中把uint64拆成8个bytes，利用查表的方式以常数时间计算出这个字节trailing zero的数量，leading zero的数量同样通过查表得出，字节中最多连续0的数量同样是通过查表得出。
对于其他层节点的更新，需要根据其8个子节点的pallocSum计算得到自身的pallocSum，算法的复杂度是O(n)，一遍扫描即可，并且与计算最底层pallocSum是类似的，最底层的pallocSum也是由64个bytes的leading zero（start）、字节中最多连续0的数量（max）、trailing zero （end）计算得到的。

update

# per-P cache

每个P都有一个页面的缓存结构，这样可以避免频繁的访问全局的页面分配器，pageCache能够缓存的页面数量是64个，cache 是用于表示哪些页面已经被分配的位图，base存着的是这64个连续页面的首地址。

type pageCache struct {
	base  uintptr // base address of the chunk
	cache uint64  // 64-bit bitmap representing free pages (1 means free)
	scav  uint64  // 64-bit bitmap representing scavenged pages (1 means scavenged)
}

1
2
3
4
5

有了page cache，每次分配页面，都会先从pageCache中分配（如果页面数量小于16个的话），如果pageCache不能满足要求，或者一次性需求分配的页数太多，大于等于16个，就直接使用全局的页面分配器分配。

当page cache为空的时候，会从全局的页面分配器中分配64个页面（不一定全是空闲的）作为填充。

← runtime off-heap object allocator on-heap object allocator →