深入理解Linux内核——内存管理（3）

提要：本系列文章主要参考MIT 6.828课程以及两本书籍《深入理解Linux内核》 《深入Linux内核架构》对Linux内核内容进行总结。
内存管理的实现覆盖了多个领域：

1. 内存中的物理内存页的管理
2. 分配大块内存的伙伴系统
3. 分配较小内存的slab、slub、slob分配器
4. 分配非连续内存块的vmalloc分配器
5. 进程的地址空间

上一节介绍了内存管理相关的主要数据结构以及它们之间的关系，本节主要介绍这些数据结构的初始化，方便在介绍内存分配时读者思路更加清晰（这部分内容主要参考《深入Linux内核架构》）。

函数start_kernel()负责完成Linux内核的初始化工作，内存管理相关数据结构的初始化也是从这里进行的。下图给出 start_kernel的代码流程图，其中只包括内存管理相关的系统初始化函数。

各个函数的作用简述如下：

函数名	描述
setup_arch	特定于体系结构的设置函数，由于内存管理实际上管理的是真正物理内存的应用，务必会与不同体系结构有联系，在本方法中还会初始化自举分配器
setup_per_cpu_areas	在SMP系统上，初始化源代码中定义的per-cpu变量（这种变量每个CPU有一个副本，因此叫per-cpu），在非SMP系统上该函数是一个空操作
build_all_zonelists	建立结点和内存域的数据结构（重要）
mem_init	用于停用bootmem分配器（自举分配器）并迁移到实际的内存管理函数
kmem_cache_init	初始化内核内部用于小块内存区的分配器
setup_per_cpu_pageset	为struct zone中的pageset数组的第一个元素分配内存，负责冷热分配器相关的设置

为了简化记忆，笔者做了如下的总结：

1. 由于内存管理是对物理内存的管理，因此必须了解整体体系结构相关信息，因此先需要通过BIOS等提供的API获取这些信息并进行配置。
2. 在内存管理初期，需要对内存管理本身使用的空间进行分配，因此需要初始化一个自举分配器完成这项工作
3. 通过已经存在的自举分配器就可以创建3层数据结构，即下图结构：
   
4. 内存管理的基本数据结构已经初始化，剩下的内存管理功能可以交给伙伴系统了，就需要将自举分配器占用的内存释放掉或者交由伙伴系统管理
5. 为slab分配器进行一些简单的配置

那我们依序开始。

setup_arch

由于内存管理管理的是真实的物理内存，因此，需要和体系结构强相关，setup_arch函数主要负责这一部分内容。下图给出了setup_arch中与内存管理相关的代码流程图：

各个函数职责如下：

方法名	职责
machine_specific_memory_setup	正如上一节中介绍的，为了获取物理内存中的保留内存地址（没有被使用的，即未来管理的真实内存），BIOS提供了一个一组物理地址范围和其对应的内存类型的表，生成该表就是在这个方法
parse_cmdline_early	内核通过该方法分析命令行，进而获取mem=XXX[KkmM]、highmem=XXX[kKmM]或memmap=XXX[KkmM]” “@XXX[KkmM]这类参数。
setup_memory	该函数主要负责如下3件事：1. 确定（每个结点）可用的物理内存页的数目。2. 初始化bootmem分配器（这部分会单独介绍）。3. 接下来分配各种内存区，例如，运行第一个用户空间过程所需的最初的RAM磁盘
paging_init	初始化内核页表并启用内存分页
zone_sizes_init	初始化系统中所有结点的pgdat_t实例，首先使用add_active_range，对可用的物理内存建立一个相对简单的列表。体系结构无关的函数free_area_init_nodes接下来使用该信息建立完备的内核数据结构。

本部分主要介绍两个内容：

1. 因为Linux极大程度使用页式管理，为了保证完成性，这里简单介绍paging_init函数（可以跳过）
2. 为了加速访问页，Linux实现了一个冷热分配器（hot-n-cold allocator），这里介绍冷热缓存的初始化（引出free_area_init_nodes，这个函数很重要）

paging_init

paging_init负责按照指定方式（通常是3：1）划分虚拟地址空间，代码流程图如下：

1. pagetable_init首先初始化系统的页表，以swapper_pg_dir为基础（该变量此前用于保存临时数据）。接下来启用在所有现代IA-32系统上可用的两个扩展：
   • 对超大内存页的支持。这些特别标记的页，其长度为4 MiB，而不是普通的4 KiB。该选项用于不会换出的内核页
   • 如有可能，内核页会设置另一个属性（_PAGE_GLOBAL）。在上下文切换期间，设置了_PAGE_GLOBAL位的页，对应的TLB缓存项不从TLB刷出。由于内核总是出现于虚拟地址空间中同样的位置，这提高了系统性能
2. 借助于kernel_physical_mapping_init，将物理内存页（或前896 MiB，正如上一节的讨论）映射到虚拟地址空间中从PAGE_OFFSET开始的位置。
3. 接下来建立固定映射项和持久内核映射对应的内存区。同样是用适当的值填充页表。
4. 在用pagetable_init完成页表初始化之后，则将cr3寄存器设置为指向全局页目录（swapper_pg_dir）的指针。此时必须激活新的页表
5. 由于TLB缓存项仍然包含了启动时分配的一些内存地址数据，此时也必须刷出。__flush_all_tlb可完成所需的工作。与上下文切换期间相反，设置了_PAGE_GLOBAL位的页也要刷出。
6. kmap_init初始化全局变量kmap_pte。在从高端内存域将页映射到内核地址空间时，会使用该变量存入相应内存区的页表项。此外，用于高端内存内核映射的第一个固定映射内存区的地址保存在全局变量kmem_vstart中。

冷热缓存的初始化

struct zone的pageset成员用于实现冷热分配器（hot-n-cold allocator）。

1. 页是热的，意味着页已经加载到CPU高速缓存，与在内存中的页相比，其数据能够更快地访问。
2. 页是冷的，则不在高速缓存中。

struct zone {
    ...
    struct per_cpu_pageset pageset[NR_CPUS];
    ...
};

在多处理器系统上每个CPU都有一个或多个高速缓存，各个CPU的管理必须是独立的（从struct 名字也可以看出来per_cpu_pageset）。这里的NR_CPUS是一个可以在编译时间配置的宏常，表示内核支持的CPU的最大数目。struct per_cpu_pageset代码如下：

struct per_cpu_pageset {
    struct per_cpu_pages pcp[2]; /* 索引0对应热页，索引1对应冷页 */
} ____cacheline_aligned_in_smp;

由注释可以看到，对于每个cpu都包含了一个struct per_cpu_pages数组，长度为2，pcp[0]存储热页，pcp[1]存储冷页。struct per_cpu_pages结构体代码如下：

struct per_cpu_pages {
    int count; /* 列表中页数 */
    int high; /* 页数上限stake，在需要的情况下清空列表 */
    int batch; /* 添加/删除多页块的时候，块的大小 */
    struct list_head list; /* 页的链表 */
};

多处理器下，pageset结构形如下图：

而pageset属性的初始化，就由setup_arch()完成，具体来说是free_area_init_nodes()函数，伙伴系统的数据结构初始化也是由这个方法完成的，因此会看setup_arch处介绍该函数时，描述是体系结构无关的函数free_area_init_nodes接下来使用该信息建立完备的内核数据结构。

free_area_init_nodes()调用zone_pcp_init初始化冷热缓存。可以看到struct per_cpu_pages主要包括两个属性：

1. high：页数上限stake，在需要的情况下清空列表
2. batch: 添加/删除多页块的时候，块的大小

static __devinit void zone_pcp_init(struct zone *zone)
{
    int cpu;
    unsigned long batch = zone_batchsize(zone);
    for (cpu = 0; cpu present_pages)
        printk(KERN_DEBUG " %s zone: %lu pages, LIFO batch:%lun",zone->name, zone->present_pages, batch);
}

zone_pcp_init通过调用zone_batchsize计算batch的具体值，然后再通过setup_pageset以batch为参考初始化每个struct per_cpu_pages：

inline void setup_pageset(struct per_cpu_pageset *p, unsigned long batch)
{
    struct per_cpu_pages *pcp;
    memset(p, 0, sizeof(*p));
    pcp = &p->pcp[0]; /* 热 */
    pcp->count = 0;
    pcp->high = 6 * batch;
    pcp->batch = max(1UL, 1 * batch);
    INIT_LIST_HEAD(&pcp->list);
    pcp = &p->pcp[1]; /* 冷 */
    pcp->count = 0;
    pcp->high = 2 * batch;
    pcp->batch = max(1UL, batch/2);
    INIT_LIST_HEAD(&pcp->list);
}

可以看到:

1. 对于热页，high=6*batch，batch=max(1UL, 1 * batch)
2. 对于冷页，high=2*batch，batch=max(1UL, batch/2)

冷页列表的stake稍低一些，因为冷页并不放置到缓存中，只用于一些关注性能的操作（当然，在内核中这样的操作属于少数）。最后给出batch的计算方法即zone_batchsize:

static int __devinit zone_batchsize(struct zone *zone)
{
    int batch;
    batch = zone->present_pages / 1024;
    if (batch * PAGE_SIZE > 512 * 1024)
        batch = (512 * 1024) / PAGE_SIZE;
    batch /= 4;
    if (batch 

公式比较复杂（用的时候找得到出处就好），但上述代码计算得到的batch，大约相当于内存域中页数的0.25‰。

结点和内存域初始化

注意：初始化系统中所有结点的pgdat_t实例是在setup_arch中的zone_sizes_init完成的。

build_all_zonelists负责建立管理结点和其内存域所需的数据结构，这里我们主要关注的是zonelist的组织顺序。在UMA系统中，只有一个结点需要管理，为了方便通过node id获取具体的pg_data_t（后面称作结点描述符）实例信息，linux提供了如下的宏：

#define NODE_DATA(nid)

但对于UMA来说，这个宏的实现就是如下代码：

#define NODE_DATA(nid) (&contig_page_data)

我们在上一节介绍Node时，注意中提到了contig_page_data就是UMA中唯一的结点。

但是整个Node中有3个管理区，三个管理区的分配次序如何呢？

我们在Node的数据结构中找到了一个名为node_zonelists的属性，该属性主要用于指定备用结点及其内存域的列表，以便在当前结点没有可用空间时，在备用结点分配内存，例如如果ZONE_HIGHMEM内存域内存不够分配时，可以尝试向ZONE_NORMAL请求分配内存。

typedef struct pglist_data {
    ...
    struct zonelist node_zonelists[MAX_ZONELISTS];
    ...
} pg_data_t;

#define MAX_ZONES_PER_ZONELIST (MAX_NUMNODES * MAX_NR_ZONES)
struct zonelist {
    ...
    struct zone *zones[MAX_ZONES_PER_ZONELIST + 1]; // NULL分隔
};

在介绍Zone时，我们介绍了3类Zone：

名称	描述
ZONE_DMA	包含低于16MB的内存页框
ZONE_DMA32	使用32位地址字可寻址、适合DMA的内存域。显然，只有在64位系统上，两种DMA内存域才有差别
ZONE_NORMAL	包含高于16MB且低于896MB的内存页框
ZONE_HIGHMEM	包含从896MB开始高于896MB的内存页框

这三类内存中ZONE_DMA部分，ISA可以对其进行直接寻址，ZONE_NORMAL也是直接映射到内核空间的，而ZONE_HIGHMEM就需要选择性的映射到内核空间中。在这3类内存中：

1. ZONE_DMA是最昂贵的，它用于外设和系统之间的数据传输
2. ZONE_NORMAL其次，许多内核数据结构必须保存在该内存域
3. ZONE_HIGHMEM最廉价，因为内核没有任何部分依赖于从该内存域分配的内存。

针对这个情况，内核针对当前内存结点的备选结点，定义了一个等级次序，确定这一等级次序的函数就是build_zonelists函数。

内核在调用了build_all_zonelists后，会将工作委托给__build_all_zonelists，该函数只是简单的对每个结点都调用build_zonelists:

static int __build_all_zonelists(void *dummy)
{
    int nid;
        for_each_online_node(nid) {
            pg_data_t *pgdat = NODE_DATA(nid);
            build_zonelists(pgdat);
            ...
        }
    return 0;
}

结构体zonelist的定义如下：

#define MAX_ZONES_PER_ZONELIST (MAX_NUMNODES * MAX_NR_ZONES)
struct zonelist {
    ...
    struct zone *zones[MAX_ZONES_PER_ZONELIST + 1]; // NULL分隔
};

其长度为Node数*Zone数+1，最后一个结点是NULL负责标记列表结尾。在pg_data_t中，node_zonelists的长度为MAX_ZONELISTS

typedef struct pglist_data {
    ...
    struct zonelist node_zonelists[MAX_ZONELISTS];
    ...
} pg_data_t;

这个长度是多少呢？build_zonelists()函数给出了这个答案：

static void __init build_zonelists(pg_data_t *pgdat)
{
  int node, local_node;
  enum zone_type i,j;
  local_node = pgdat->node_id;
  for (i = 0; i node_zonelists + i;
      j = build_zonelists_node(pgdat, zonelist, 0, i);
  ...
}

build_zonelists()函数为每个ZONE创建了一个zonelist用于表示其备用内存域列表，填充该列表的工作主要交给build_zonelists_node()方法：

static int __init build_zonelists_node(pg_data_t *pgdat, struct zonelist *zonelist,
    int nr_zones, enum zone_type zone_type)
{
    struct zone *zone;
    do {
        // 通过指针获取zone_type类型的zone
        zone = pgdat->node_zones + zone_type;
        // 如果有空闲空间，则将zone添加到zonelists中
        if (populated_zone(zone)) {
            zonelist->zones[nr_zones++] = zone;
        }
        // 选取更为昂贵的zone判断是否加入到备用列表中
        zone_type--;
    } while (zone_type >= 0);
    return nr_zones;
}

这里有一个小细节，在内核中zone_type使用如下enum来保存：

enum zone_type {
#ifdef CONFIG_ZONE_DMA
    ZONE_DMA,
#endif
#ifdef CONFIG_ZONE_DMA32
    ZONE_DMA32,
#endif
    ZONE_NORMAL,
#ifdef CONFIG_HIGHMEM
    ZONE_HIGHMEM,
#endif
    ZONE_MOVABLE,
    MAX_NR_ZONES
};

因此，每次zone_type --就是选取了更为昂贵的内存区域。因此，内核在build_zonelists中按分配代价从昂贵到低廉的次序，迭代了结点中所有的内存域。而在build_zonelists_node中，则按照分配代价从低廉到昂贵的次序，迭代了分配代价不低于当前内存域的内存域。

举一个例子，对于一个系统拥有4个结点，其结点2的高端内存即ZONE_HIGHMEM的备用列表创建过程大致如下：

因为zonelist还会引用其它结点的内存域，因此需要确定结点之间的次序，相关代码如下：

static void __init build_zonelists(pg_data_t *pgdat)
{
  ...
  for (node = local_node + 1; node zones[j] = NULL;
  }
}

实际上就是先引用大于当前结点的结点，再引用小于当结点结点。对总数N个结点中的结点m来说，内核生成备用列表时，选择备用结点的顺序总是：m 、m+1、m+2、…、 N-1、0、1、…、 m-1。这确保了不过度使用任何结点。最终结点2即第三个结点上的每个Zone的备用列表如下：

自举分配器

在启动过程期间，尽管内存管理尚未初始化，但内核仍然需要分配内存以创建各种数据结构。bootmem分配器用于在启动阶段早期分配内存。

显然，对该分配器的需求集中于简单性方面，而不是性能和通用性。因此内核开发者决定实现一个 最先适配（first-fit）分配器用于在启动阶段管理内存，这是可能想到的最简单方式。

传统操作系统课本会介绍4种动态分区分配方法：

这里选用的是首次适应算法（通常效果最好）：

该分配器使用一个位图来管理页，位图比特位的数目与系统中物理内存页的数目相同。比特位为1，表示已用页；比特位为0，表示空闲页。因为该过程不是很高效，因为每次分配都必须从头扫描比特链。因此在内核完全初始化之后，不能将该分配器用于内存管理。

为了实现该自举分配器，内核使用了如下结构：

typedef struct bootmem_data {
    // 保存了系统中第一个页的编号，大多数体系结构下都是零
    unsigned long node_boot_start;
    // 是可以直接管理的物理地址空间中最后一页的编号。换句话说，即ZONE_NORMAL的结束页
    unsigned long node_low_pfn;
    // 是指向存储分配位图的内存区的指针。
    void *node_bootmem_map;
    // last_pos是上一次分配的页的编号。如果没有请求分配整个页，则last_offset用作该页内部的偏移量。这使得bootmem分配器可以分配小于一整页的内存区
    unsigned long last_offset;
    unsigned long last_pos;
    // last_success指定位图中上一次成功分配内存的位置，新的分配将由此开始。尽管这使得最先适配算法稍快了一点，但仍然无法真正代替更复杂的技术。
    unsigned long last_success;
    // 内存不连续的系统可能需要多个bootmem分配器。
    struct list_head list;
} bootmem_data_t;

初始化

bootmem分配器的初始化是一个特定于体系结构的过程，此外还取决于所述计算机的内存布局。IA-32使用setup_memory，setup_bootmem_allocator来初始化bootmem分配器，而AMD64则使用contig_initmem_init。

对内核的接口

bootmem对于分配内存提供了如下接口：

1. alloc_bootmem(size)和alloc_bootmem_pages(size)按指定大小在ZONE_NORMAL内存域分配内存。数据是对齐的，这使得内存或者从可适用于L1高速缓存的理想位置开始，或者从页边界开始
2. alloc_bootmem_low和alloc_bootmem_low_pages的工作方式类似于上述函数，只是从ZONE_DMA内存域分配内存

这些函数都是__alloc_bootmem的前端，后者将实际工作委托给__alloc_bootmem_nopanic。由于可以注册多个bootmem分配器,__alloc_bootmem_core会遍历所有的分配器，直至分配成功为止。

在NUMA系统上，__alloc_bootmem_node则用于实现该API函数。首先，工作传递到__alloc_bootmem_core，尝试在该结点的bootmem分配器进行分配。如果失败，则后退到__alloc_bootmem，并将尝试所有的结点。

void * __init __alloc_bootmem(unsigned long size, unsigned long align,unsigned long goal)

__alloc_bootmem需要3个参数来᧿述内存分配请求：size是所需内存区的长度，align表示数据的对齐方式，而goal指定了开始搜索适当空闲内存区的起始地址。在进行内存分配时，大致执行如下操作（和课本上讲述的首次适应算法步骤基本类似）：

1. 从goal开始，扫᧿位图，查找满足分配请求的空闲内存区。
2. 如果目标页紧接着上一次分配的页，即bootmem_data-> last_pos，内核会检查bootmem_data->last_offset，判断所需的内存（包括对齐数据所需的空间）是否能够在上一页分配或从上一页开始分配。
3. 新分配的页在位图对应的比特位设置为1。最后一页的数目也保存在bootmem_data->last_pos。如果该页未完全分配，则相应的偏移量保存在bootmem_data->last_offset;否则，该值设置为0。

bootmem提供了free_bootmem和free_bootmem_node（NUMA）来释放内存，但这两个方法都将具体逻辑委托给__free_bootmem_core。

停用bootmem分配器和释放初始化数据

在系统初始化进行到伙伴系统分配器能够承担内存管理的责任后，必须停用bootmem分配器，停用过程调用free_bootmem和free_bootmem_node（NUMA）函数来完成：

1. 首先扫᧿bootmem分配器的页位图，释放每个未用的页。到伙伴系统的接口是__free_pages_bootmem函数，该函数对每个空闲页调用。该函数内部依赖于标准函数__free_page。它使得这些页并入伙伴系统的数据结构，在其中作为空闲页管理，可用于分配。
2. 在页位图已经完全扫᧿之后，它占据的内存空间也必须释放。此后，只有伙伴系统可用于内存分配。

许多内核代码块和数据表只在系统初始化阶段需要，因此不必要在内核内存中保持其数据结构的初始化例程。

内核提供了两个属性（__init和__initcall）用于标记初始化函数和数据，释放内存时，只需要删除这部分数据就可以了。使用样例如下：

int __init hyper_hopper_probe(struct net_device *dev)

static char stilllooking_msg[] __initdata = "still searching...";

初始化函数实现的背后，其一般性的思想在于，将数据保持在内核映像的一个特定部分，在启动结束时可以完全从内存删除。可以从上面两个label的宏定义看到：

#define __init __attribute__ ((__section__ (".init.text"))) __cold
#define __initdata __attribute__ ((__section__ (".init.data")))

__attribute__是一个特殊的GNU C关键字，属性即通过该关键字使用。__section__属性用于通知编译器将随后的数据或函数分别写入二进制文件（ELF文件）的.init.data和.init.text段。前缀__cold还通知编译器，通向该函数的代码路径可能性较低，即该函数不会经常调用，对初始化函数通常是这样。

因此只需要了解这两个段的起始和终止地址，对应释放这部分就可以了。内核定义了一对变量__init_begin和__init_end，负责完成该工作。

总结

本部分主要介绍了内核管理主要数据结构的初始化内容，下一节我们会开始介绍伙伴系统。