> For the complete documentation index, see [llms.txt](https://richardweiyang-2.gitbook.io/kernel-exploring/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://richardweiyang-2.gitbook.io/kernel-exploring/nei-cun-guan-li/00-memory_a_bottom_up_view/00_page_allocator/03-sparsemem.md). # 寻找页结构体的位置 今天要来讲讲linux内核中的SPARSEMEM。 这其实是一个内核可配置项，比如在arch/x86/Kconfig中可以看到如下的配置。 ``` config ARCH_SPARSEMEM_ENABLE def_bool y depends on X86_64 || NUMA || X86_32 || X86_32_NON_STANDARD select SPARSEMEM_STATIC if X86_32 select SPARSEMEM_VMEMMAP_ENABLE if X86_64 ``` 也就是只要是满足depends on这四个条件之一，默认都会开启SPARSEMEM。 书接上回，我们提出了一个思考题：page结构体究竟是存放在哪里？你有找到么？如果没有的话，那就由我来给大家絮叨絮叨。另外前文那张经典的数据结构关系图中一个未露面的成员zone\_mem\_map在本文中将会出现。不过刚才那张图有点老，当前代码中使用的可能是他的孙子辈吧。 估计你现在还是一头雾水，莫名来了这么多名词，概念，也不知道哪个是哪个。其实这个东西说难也不难。刚开始理解时略有些麻烦，但是看明白之后也没有太多内容。 找个舒服的地儿，倒杯茶，让我给你一一道来。 ## 有啥好处? 先来说说用它的好处，否则大家都不知道这是干啥的。在原始[补丁](https://lwn.net/Articles/134804/)中，作者做了些比较详细的描述。我列举一下： * 对于有内存空洞的设备，减少系统struct page使用的内存 * 内存热插拔系统需要使用 * 在NUMA系统上支持内存的overlap 后两者究竟是怎么用的，暂时还不清楚。减少系统struct page使用的内存，那是肯定的。因为在最原始的实现中，系统struct page是一个超大的静态数组。不管对应的物理地址是否有内存存在，都会有对应的struct page对应。而使用了SPARSEMEM后，只有有效的page才会有对应的struct page存在。 在减少内存使用的同时，也带来了一个问题。 * pfn\_to\_page()计算会比原来的慢 针对这点，内核中又引入了SPARSEMEM\_VMEMMAP。这个以后再来讲解，这次先关注SPARSEMEM本身。 ## 实现思想 SPARSEMEM提出了一个新的概念 > section 这个section就是比page更大一些的内存区域，但是呢一般意义上又比node的范围要小些。比如在x86\_64平台上，这个的大小就是(2^27) = 128M。 整个系统的物理内存就被分成一个个section，并由mem\_section结构体表示。而这个结构体中保存了该section范围内struct page结构体的地址。 那是怎么做到节省了struct page的内存的呢？ 在没有使用SPARSEMEM前，page结构体是一个连续数组。也就是说如果整个系统最大会支持多少内存，都得预先分配好空间。哪怕中间有一段物理内存是空的，也得留着。 使用了SPARSEMEM后，如果有一个section是空的，也就是内存中有128M的空洞，那这个section中的struct page内存空间就不会被分配。从而节省了一定的空间。这么看其实要达到节省内存的条件还是蛮高的，至少得有128M的空洞。等等，而且这128M还得要对齐的。这种情况真的多么？ 而且这也是为什么做内存热插拔时，要求至少时128M的原因。有意思吧。 ## 图解数据结构 讲的多了，用图来给大家展示一下。 ### mem\_section\[]\[] 先来看看全局mem\_section数组。这个数组的每一个元素是mem\_section结构体，名字上有重复，大家要注意。 每个数组的元素管理了128M的内存。这样，可以很容易的通过pfn（page frame number）找到对应的section。 ``` mem_section[NR_SECTION_ROOTS][SECTIONS_PER_ROOT] = [DIV_ROUND_UP(NR_MEM_SECTIONS, SECTIONS_PER_ROOT)] [SECTIONS_PER_ROOT] [0] [1] [SECTIONS_PER_ROOT - 1] +------------+------------+ +------------+------------+ [0] | | | ... | | | +------------+------------+ +------------+------------+ +------------+------------+ +------------+------------+ [1] | | | ... | | | +------------+------------+ +------------+------------+ +------------+------------+ +------------+------------+ [2] | | | ... | | | +------------+------------+ +------------+------------+ ``` 怎么样，这么看是不是还挺简单的。就是用数组去覆盖整个内存的区域，然后分块管理么。 这里我们再来看看mem\_section定义里的一些数字的含义。 首先看看二维数组大小的定义。 ``` #define SECTIONS_PER_ROOT (PAGE_SIZE / sizeof (struct mem_section)) #define NR_SECTION_ROOTS DIV_ROUND_UP(NR_MEM_SECTIONS, SECTIONS_PER_ROOT) struct mem_section mem_section[NR_SECTION_ROOTS][SECTIONS_PER_ROOT] ``` 这里可以看出mem\_section这个二维数组的第二维正好是一个PAGE\_SIZE的大小。 而整个数组中一共有NR\_MEM\_SECTIONS个元素。因为这是一个二维数组定义，所以整个系统中所能处理的物理内存大小也就由此决定了。 接下来我们就来看看这个数组个数，以及系统所能处理的物理内存最大值。 ``` # define SECTION_SIZE_BITS 27 /* matt - 128 is convenient right now */ # define MAX_PHYSMEM_BITS (pgtable_l5_enabled() ? 52 : 46) #define SECTIONS_SHIFT (MAX_PHYSMEM_BITS - SECTION_SIZE_BITS) #define NR_MEM_SECTIONS (1UL << SECTIONS_SHIFT) ``` 在上面的定义中我们可以得到两个信息： 1. 每个mem\_section代表的内存大小是 2^27 = 128M 2. 系统能处理的最大内存是事先定义好的MAX\_PHYSMEM\_BITS 比如在x86系统上，如果没有5级页表，最大支持的是2^46=64T内存。而每个section支持的是2^27=128M。 所以以此可以得出整个mem\_section二维数组的个数是2^(46-27)=2^19，也就是一共有 2^19 个section。 ### section中的struct page 接下来我们再来看看section中是如何管理这个struct page的。 ``` mem_section +-----------------------------+ |usage | | (mem_section_usage *) | | | | | +-----------------------------+ mem_map[PAGES_PER_SECTION] |section_mem_map | ----> +------------------------+ | (unsigned long) | [0] |struct page | | | | | | | +------------------------+ +-----------------------------+ [1] |struct page | | | +------------------------+ [2] |struct page | | | +------------------------+ | | . . . . . . | | +------------------------+ |struct page | | | +------------------------+ [PAGES_PER_SECTION - 1] |struct page | | | +------------------------+ ``` 需要注意一点的是section\_mem\_map对应的内存是动态分配的。所以如果这个section对应的物理内存不存在，即便是mem\_section的空间会被分配，其对应的struct page的空间是不会被分配的。这样起到了节省内存的作用。 **page结构体在这里** **page结构体在这里** **page结构体在这里** 重要的事情说三遍。 ### section中的usage 接着我们看看结构中的另一个成员usage(struct mem\_section\_usage) ``` mem_section +-----------------------------+ |section_mem_map | | (unsigned long) | | | +-----------------------------+ |usage | | (mem_section_usage *) | | +-------------------------+ | |subsection_map | SUBSECTIONS_PER_SECTION = | | (bitmap) | (1UL << (SECTION_SIZE_BITS - SUBSECTION_SHIFT)) | | | = (1UL << (27 - 21)) | | | | | | | | | [(1UL << (PFN_SECTION_SHIFT - pageblock_order))]个 | | | each 4/8bits represents a pageblock type | |pageblock_flags[0] | get_pfnblock_flags_mask() / get_pfnblock_migratetype() | | (unsigned long) ---|--->+----+----+----+---...---+----+----+ +---+-------------------------+ | | | | | | | | | | | | | | +----+----+----+---...---+----+----+ ``` 在这个结构中我们可以看到，一个section还可以在两个概念上进一步划分： * subsection: 每2MB作为一个subsection * pageblock: pageblock\_order作为一个pageblock 其中subsection\_map在函数subsection\_map\_init()中初始化。 而pageblock\_flags在memmap\_init()过程中设置。 ## 变慢了么？ 刚才我们就说到了使用了这个模型后pfn\_to\_page()的访问会变慢。那我们来看看是不是真的呢？ 先看看原始的定义： ``` #define __pfn_to_page(pfn) (mem_map + ((pfn) - ARCH_PFN_OFFSET)) ``` 再来看看更改后的定义： ``` #define __pfn_to_page(pfn) \ ({ unsigned long __pfn = (pfn); \ struct mem_section *__sec = __pfn_to_section(__pfn); \ __section_mem_map_addr(__sec) + __pfn; \ }) ``` 更改后，需要先找到section，然后再计算出page的地址。这个样比原来多了一步，确实是慢了一些。 ## 互相转换 理解了SPARSEMEM的模型后，我们就可以理解这两个在内核中重要的转换了 * \_\_pfn\_to\_page() * \_\_page\_to\_pfn() 也就是物理地址和page结构体之间的互相转换。 ``` /* * Note: section's mem_map is encoded to reflect its start_pfn. * section[i].section_mem_map == mem_map's address - start_pfn; */ #define __page_to_pfn(pg) \ ({ const struct page *__pg = (pg); \ int __sec = page_to_section(__pg); \ (unsigned long)(__pg - __section_mem_map_addr(__nr_to_section(__sec))); \ }) #define __pfn_to_page(pfn) \ ({ unsigned long __pfn = (pfn); \ struct mem_section *__sec = __pfn_to_section(__pfn); \ __section_mem_map_addr(__sec) + __pfn; \ }) ``` 它们都定义在同一个头文件中。这个定义也非常的巧妙，section\_mem\_map尽然包含了start\_pfn。这样的结果就是计算时不需要再去计算一次整个section的起始地址了。是不是觉得很赞～ 好了，这个SPARSEMEM就讲到这里～我想大家已经知道page结构体是在什么地方的了～ ## 初始化流程 最后来看一下启动时sparsemem代码执行顺序。 ``` start_kernel() setup_arch() x86_init.paging.pagetable_init() -> paging_init() sparse_init() memblock_present() mark section present sparse_init_nid() setup section's section_mem_map/usage sparse_init_early_section() sparse_init_subsection_map() setup section's usage->subsection_map node_clear_state(0, N_MEMORY); node_clear_state(0, N_NORMAL_MEMORY) ``` 简单来说分了三步： * 标注哪些section是存在的 * 给存在的section分配memmap/usermap * 标记subsection: **目前标记subsection时，如果subsection中只有部分内存，也会标记存在** memblock\_present()标记了present的section，肯定有内存在。但其中可能有空缺。 sparse\_init\_nid()会遍历所有标记了present的section, 并设置好对应section上的section\_mem\_map/usage。 sparse\_init\_subsection\_map()又重新扫描了一遍section，目的是标记usage->subsection\_map。subsection的大小是2M， (SUBSECTION\_SHIFT 21)。 ## 常用API ### for\_each\_present\_section\_nr(start, section\_nr) ## SPARSEMEM\_VMEMMAP 在上面"变慢了么"部分，我们看到采用了sparsemem后，pfn<->page之间的转换步骤变多了。而这个转换在内核中却是一个非常频繁的操作。于是乎，内核中增加了SPARSEMEM\_VMEMMAP配置。 我们先看看这个内核中是如何描述这个配置的。 ``` SPARSEMEM_VMEMMAP uses a virtually mapped memmap to optimise pfn_to_page and page_to_pfn operations. This is the most efficient option when sufficient kernel resources are available. ``` 总的来说也没有什么神秘的，也就是用空间换时间。通过将地址转换关系写到页表中，来加速两者之间的转换。 具体的转换暂且按下不表，我有点好奇的是我们需要分配多少虚拟地址空间能满足系统最大支持的物理内存？我们尝试来计算一下。 已知 * 最大支持的物理内存 = 2 ^ MAX\_PHYSMEM\_BITS = 2 ^ 46 = 64T * 一个page表达 2 ^ 12 = 4K * 一个page占64 byte 由此可以计算支持最大物理内存所对应的page需要的虚拟空间 ``` 64T / 4K * 64 = 1T ``` 所以地址空间中需要1T才能真正满足最大物理内存的情况。 这一点我们在[内核文档](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/Documentation/arch/x86/x86_64/mm.rst)中也能得到印证。 ``` ffffea0000000000 | -22 TB | ffffeaffffffffff | 1 TB | virtual memory map (vmemmap_base) ``` 而这个ffffea0000000000正是地址映射的起始地址。 ``` #define __VMEMMAP_BASE_L4 0xffffea0000000000UL #define VMEMMAP_START __VMEMMAP_BASE_L4 #define vmemmap ((struct page *)VMEMMAP_START) #define __pfn_to_page(pfn) (vmemmap + (pfn)) ``` 不过这个感觉有点危险，如果那天page里面又塞了啥东西，那就要爆了。不过也由此可见，page里面应该不让轻易随便改动，尤其是加新的值。 ### vmemmap的映射和分配 ``` sparse_init() sparse_metadata_init() // for_each_early_section_nr() // 只遍历early section sparse_metadata_init_nid() sparse_usage_init() // 分配usage空间，包含subsection和pageblock __populate_section_memmap() // 拿到mmep，也就是当前section的struct page的内存 sparse_init_one_section() // struct page设置到mem_section->section_mem_map，usage设置到usage(包括pageblock) ``` 我们知道page struct的分配在sparse\_init()->\_\_populate\_section\_memmap()按照Section为单位分配和映射. 但具体是怎么做的呢？ 我们这里展开学习一下。 这个过程有很多变体，我们这里先看最基础的： ``` // 从sparse_metadata_init_nid()调用， pfn是section所含的起始pfn __populate_section_memmap(pfn, nr_pages /*=PAGES_PER_SECTION*/, nid, altmap /*=NULL*/, pgmap /*=NULL*/) // [start, end)就是接下来要映射的空间 start = (unsigned long) pfn_to_page(pfn) end = start + nr_pages * sizeof(struct page) vmemmap_populate(start, end, nid, altmap/*=NULL*/) vmemmap_populate_basepages(start, end, nid, NULL) -> vmemmap_populate_range(start, end, nid, NULL, -1, 0) // for (; addr < end; addr += PAGE_SIZE) // 逐个页面映射 vmemmap_populate_address(addr, nid, NULL, -1, 0) -> vmemmap_pte_populate(pmd, addr, nid, NULL, -1, 0); pte = pte_offset_kernel(pmd, addr) p = vmemmap_alloc_pte(pfn, nid, NULL, 0) // 返回的是线性映射的虚拟地址 return vmemmap_alloc_block_buf(PAGE_SIZE, nid, NULL) return vmemmap_alloc_block(PAGE_SIZE, nid) // 通过memblock分配一个物理页 return memmap_alloc(PAGE_SIZE, PAGE_SIZE, __pa(MAX_DMA_ADDRESS), nid, false) ptpfn = PHYS_PFN(__pa(p)); // 转换成pfn entry = pfn_pte(ptpfn, PAGE_KERNEL); // pte中写入的是pfn set_pte_at(&init_mm, addr, pte, entry); // 设置到页面上，完成映射 ``` **注**： 这里有个很有意思的地方， **struct page的大小不一定是2的指数次对齐的**. 在struct page定义中我们看到有一个对齐的标志：\_struct\_page\_alignment。 ``` #ifdef CONFIG_HAVE_ALIGNED_STRUCT_PAGE #define _struct_page_alignment __aligned(2 * sizeof(unsigned long)) #else #define _struct_page_alignment __aligned(sizeof(unsigned long)) #endif ``` 也就是最多是16字节对齐。那这就有一个问题 --> 某一个struct page会跨越页的边界。 所以在上面分配/映射struct page的过程中，就是按照一页页的方式逐个映射的。 而另一个有意思的地方是： **整个section对应的struct page是页对齐的**。 可以说这是个巧合，也可以说是内核开发者巧妙的安排。计算过程如下： 假设是4K的页，一个section就是128M 那就是128M / 4K = 32K 个页面 所占用的struct page大小是： 32K \* S。 这个大小肯定是4K的整数倍。 PS： 但是PAGE\_SHIFT可以配置。。。目前不确定如果PAGE\_SHIFT变大后section还是128M的话会怎么样。。。 ### 节约struct page分配的优化 刚才说了， vmemmap的分配/映射有很多优化，这里先看vmemmap\_pte\_populate()的一个。 **这个优化的作用是减少struct page的分配** ``` // for (; addr < end; addr += PAGE_SIZE) // 逐个页面映射 vmemmap_populate_address(addr, nid, NULL, -1, 0) vmemmap_pte_populate(pmd, addr, nid, NULL, -1, 0); pte = pte_offset_kernel(pmd, addr); pfn = page_to_pfn((struct page*)addr); p = vmemmap_alloc_pte(pfn, nid, NULL, 0) // 区别在分配页这里 if (vmemmap_optimizable_pfn(pfn)) // struct page大小必须是2的指数 if (!is_power_of_2(sizeof(struct page))) return false order = pfn_to_section_compound_order(pfn) nr_pages = 1UL << order; return (pfn & (nr_pages - 1)) >= VMEMMAP_OPTIMIZATION_NR_STRUCT_PAGES; { // 跳过第一个页后 vmemmap_shared_tail_page(order, zone) idx = order - VMEMMAP_OPTIMIZATION_MIN_ORDER page = zone->vmemmap_tails[idx] if (page) return page // 如果已经分配过了，就重用 addr = vmemmap_alloc_block(PAGE_SIZE, zone_to_nid(zone)) // 否则的话，再分配 prep_compound_tail() // 当作tail来初始化 page = virt_to_page(addr) // 这里很巧妙，因为实际上这时映射还没有建立 zone->vmemmap_tails[idx] = page return page } ptpfn = PHYS_PFN(__pa(p)); entry = pfn_pte(ptpfn, PAGE_KERNEL) set_pte_at(&init_mm, addr, pte, entry) ``` 这个优化有一个前提条件：populate前我们直到这一段空间内存将一直以大页形式存在。 假设我们直到一端空间一直以2M大页形式存在， 那么就可以将后续的tail指向一个模板。而且这个模板是zone为单位的。 ``` 【单个 2MB hugetlb 页的 vmemmap，相对下标】 vmemmap 虚拟页 大页内 index 范围 内容 PTE 指向 #0 [0, 64) head+63 tail 独立物理页 #1 [64,128) 纯 tail 共享模板 ... #7 [448,512) 纯 tail 共享模板 ``` 对于能优化的范围(vmemmap\_optimizable\_pfn(pfn))， 在分配vmemmap的时候就初始化了struct page。所以在memmap\_init\_range()过程中，回跳过这部分。