Linux 内核内存管理

今天读完了 Understanding the Linux Kernel 的第八章，主要描述了 Linux 内核如何为自己分配动态内存。这一章涉及了很多很复杂的内容，组织形式对我来说也不太友好，有种盲人摸象的感觉。直到全部看完，才有了一个相对比较完整的理解。这篇博客希望能让我之后再回来看的时候，减少我自己的认知负担。这篇博客主要分为以下几个部分：

内核态地址空间结构
物理内存页的分配
虚拟地址映射

这里声明一下，以下的内容都是基于 Linux 2.6 在 80x86 架构上的实现。

内核态地址空间结构

大家都知道，操作系统本身的目的，是为了给上层的应用提供各种资源的抽象。对于内存，操作系统使用了虚拟地址来为各个应用提供了安全易用的使用接口。而内核态地址空间，是一个进程只有在内核态时才可以使用的虚拟地址空间。Linux 把大于等于 0xC0000000 (3GB) 的这一片虚拟地址空间分配给了内核态。这一片空间中的每一部分，不是生来平等的，而是分成了几个部分，每一个部分都用不同的用途。这些部分按照虚拟地址从小到大排序依次是：

3GB ~ 3GB + 896M (high_memory): 这一部分的虚拟地址是直接映射到了 0~896M 这一片物理内存。这个映射是固定不变的（虚拟地址减去 3G 就是物理地址）。这部分包含了 _DMA_（可以用于 direct memory access）和 _normal_。这之后的部分在 Linux 中被称为 _high memory_。
high_memory ~ VMALLOC_START: 这一部分是留空的，用来保证内存访问安全。如果有代码一不小心访问了这部分内存，会被捕捉到。
VMALLOC_START ~ VMALLOC_END: 这一部分是 _vmalloc area_，主要用来映射非连续内存。
VMALLOC_END ~ PKMAP_BASE: 这一部分也是留空，用来保证访问安全的。
PKMAP_BASE ~ FIXADDR_START: 这一部分是用于永久映射的，详细的讨论见下文。
FIXADDR_START ~ 4GB: 这一部分是用于固定映射的。固定映射是为了一些指定的用途建立的到物理内存的映射，比如 APIC（高级可编程中断控制器）。

memory_space

内存分配的一般流程

不管内核怎么为自己分配内存，都依赖于实际的物理内存页的分配。除此之外，内核还需要分配内存来存放这个分配的描述符，以及创建从虚拟地址到新的物理内存的映射。所以，一般的流程如下：

为元数据分配内存 (注意，这一步也是一个内存分配的过程)
实际的物理内存分配
更新分配的元数据
分配虚拟地址空间，更新页表

这上面 4 个步骤的顺序，在不同的情况下会有一些不同，并且在某些情况下，只需要某几个步骤。但是大体的思路是这样的。接下来我们来看看其中重要步骤的实现。

物理内存页的分配

内核将物理内存抽象为 _page frame_（页框）。每一个分配获得的 page frame 都对应到了一个页描述符（struct page）。这些页描述符都保存在了 mem_map 这个数组中。

分配物理页框的入口函数是 alloc_pages，它也有一些变种，比如 __get_free_pages。这里要注意的一点是，alloc_pages 返回的物理页框，都是连续的。

// gfp 是 get free page 的缩写。
// gfp_mask 是分配内存时需要的一些参数，下面再详细解释
// order: 表示需要 2**order 个 page frame。
page* alloc_pages(unsigned int gfp_mask, unsigned int order) {
  // alloc_pages_node -> __alloc_pages
}

page* alloc_pages(unsigned int gfp_mask) { return alloc_pages(gfp_masks, 0); }

// __get_free_pages 的主要区别是它的返回值是虚拟地址
unsigned long __get_free_pages(unsigned int gfp_mask, unsigned int order) {
  return page_address(alloc_pages(gfp_mask, order));
}

unsigned long __get_free_pages(unsigned int gfp_mask) {
  return __get_free_pages(gfp_mask, 0);
}

接下来我们具体看看 __alloc_pages 的实现。

Zoned Page Frame Allocator

__alloc_pages 的实现被称为 zoned page frame allocator (以下简称 zoned allocator)。它的特点是将物理内存分为若干个 zone，对应的数据结构是 struct zone。它在分配内存的时候，会根据参数（gfpmask）从合适的 zone 中去分配内存。在 Linux 2.6 中，内核将物理内存分为了三部分：DMA，normal 和 high memory。这三个部分恰好就对应了内核态地址空间的分配。DMA 和 normal 对应了 3GB 到 3GB + 876M 这一段的虚拟地址。

当 zoned allocator 找到一个合适的区可以分配内存的时候，它会使用 buddy system 算法，来从这个 zone 所对应的物理内存中挑选出合适的部分。

Buddy System

Buddy system 需要解决的问题是 external fragmentation。回忆一下，上面的 alloc_pages 返回的是连续的物理页框。如果我们在处理内存分配请求的时候过于随意，就会导致有很多零碎的物理页框。这些页框可能分散各处，即使总量很多，也没法满足连续的物理内存的需求。

Buddy system 解决这个问题的方式，就是将连续的物理内存分类。对于每个内存分配请求，我们根据请求的大小寻找合适的分类进行分配。具体来说，Buddy system 将连续内存按照 2 的幂分成若干个列表。比如，第一个列表包含了若干个长度为 1 个页框的连续物理页，第二个则包含了若干长度为 2 个页框的连续物理页。当我们收到一个需要 4 个页框的内存分配请求时，我们从 4 对应的列表开始搜索，一旦找到一个非空列表，就从列表中取一个元素。如果这个列表中的元素对应的物理内存空间比请求的大小大，我们会把这段空间拆分成多个 2 个幂。比如，如果我们使用长度为 16 的列表来满足大小为 4 的请求，我们会把 16 拆成 8 + 4 + 4。出去需要被分配的 4 之外，其他长度为 8 和 4 的物理内存，会插入到对应的列表中，满足之后的内存分配。当我们释放内存的时候，我们也会使用类似的算法，把相邻的物理内存合并。

Buddy system 的入口函数是 [__rmqueue(struct zone *zone, unsigned int order)]，它会从 zone->free_area 这个数组的第 order 个元素开始，需要合适的内存块。

物理内存的分配

上面介绍了部分，是以物理页框为内存分配的单位。然而，在实际的使用中，我们往往不会直接时候一个页框。相反，我们往往是根据我们需要的数据结构，来申请内存。为了处理这种请求，Linux 内核实现了 Slab Allocator。

Slab Allocator 使用了两种抽象：Cache 和 Slab。一个 Cache（struct kmem_cache_t）用来处理固定大小的内存分配请求，它包含了多个 Slab（struct slab），每个 Slab 对应到了若干个连续的物理页框，是实际的物理内存来源。

Slab Allocator 是基于 zoned allocator 实现的，它的入口函数是 kmem_cache_alloc，简单的伪代码实现如下：

// kmem_cache_t 指明的对应的 cache。
// 这里不需要指定大小，因为每个 cache 能分配的大小是固定的。
void* kmem_cache_alloc(kmem_cache_t *cachep, int flags) {
  // 这里的 ac 是 cache 中每个 cpu 对应的本地缓存，目的是为了减少 contention
  // 分配的时候只会从 array_cache 中取第一个空闲的。
  //
  // cache_alloc_refill 做的事情是把 cache 拥有的 slab 中的内存放到 array_cache 中。
  struct array_cache *ac = cachep->array[smp_processor_id()];
  if (ac->avail) {
    return ((void**)(ac + 1)[--ac->avail]);
  } else {
    return cache_alloc_refill(cachep, flags);
  }
}

// 这个方法是为了 cache 分配 slab。
// 它会调用 alloc_pages，也就是 zoned allocator。
int cache_grow(kmem_cache_t * cachep, int flags, int nodeid) {
  // kmem_getpages -> alloc_pages
}

虚拟地址映射

内存分配的另一个重要部分，就是建立虚拟地址的映射。只有有了映射，内核代码才可以访问内存。对于不同的内存，建立映射的方式也不尽相同。具体分为以下几类：

非 high memory 的虚拟地址映射到的物理内存就是 0~896M。这个映射在初始化页表的时候，已经配置好了，不需要再额外配置。
对于 high memory 的虚拟地址部分，它的映射分为三种：
1. 永久内核映射，它将 PKMAP_BASE ~ FIXADDR_START 的虚拟地址映射到物理内存。它的入口函数是 kmap。
2. 临时内核映射，它将固定映射中的 FIX_KMAP_BEGIN 到 FIX_KMAP_END 这部分映射到物理内存。它的入口函数是 kmap_atomic。
3. 非连续内存管理，它将 VMALLOC_START ~ VMALLOC_END 的虚拟地址映射到物理内存。它的入口函数是 map_vm_area。

这三种映射方式有不同的特性，所以会使用在不同的场景。

永久内核映射

永久内核映射之所以被称为永久，是因为，除非有明确的 release，否则这个映射一直存在。由于这部分的虚拟地址空间是有限的，所以建立这种类型的映射可能会 block，也就意味着它不能在中断处理函数中使用。

临时内核映射

临时内核映射的特点是它本身没有修改的保护，需要内核代码编写者自己保证不会有不同的内核控制路径同时使用一个虚拟地址映射到不同的物理内存。这也是为什么它不会阻塞的原因。

非连续内存管理

非连续内存管理比较特殊，它在处理打断内存分配请求的时候，不会分配连续的物理页。Linux 在实现它的时候，将 VMALLOC_START ~ VMALLOC_END 这段虚拟地址分成了若干个非连续内存区（描述符的数据结构是 struct vm_struct）。每一个内存分配都会生成一个 vm_struct，它的入口函数是 vmalloc。

void* vmalloc(unsigned long size) {
  // 分配一个空闲的 vm area。
  struct vm_struct *area = get_vm_area(size, VM_ALLOC>);

  // 分配页描述符需要的内存
  // kmalloc 底层调用的是 slab allocator
  area->pages = kmalloc(array_size, GFP_KERNEL);

  // 分配若干个物理页
  // 注意这里多次调用 alloc_page，分配的就是多个彼此不连续的物理页
  for (int i = 0; i < area->nr_pages; i ++) {
    area->pages[i] = alloc_page(...);
  }

  // 建立虚拟地址映射
  // 它会更新页表
  map_vm_area(area, area->pages);
  return area->addr;
}

这个函数的实现，恰好就对应了内存分配的一般流程的几个步骤。

总结

Linux 内核的内存管理的实现，实际上有明确的分层。最上层是 vmalloc，它依赖于 slab allocator。slab allocator 又依赖于 zoned allocator。而 zoned allocator 又依赖于 buddy system。在物理内存分配之外，虚拟地址的映射又分成了一种形式。从这个角度来看，内核的内存管理似乎就更清晰了。

瞎扯

目录