【内存管理】页面分配机制

前言

Linux内核中是如何分配出页面的，如果我们站在CPU的角度去看这个问题，CPU能分配出来的页面是以物理页面为单位的。也就是我们计算机中常讲的分页机制。本文就看下Linux内核是如何管理，释放和分配这些物理页面的。

伙伴算法

伙伴系统的定义

大家都知道，Linux内核的页面分配器的基本算法是基于伙伴系统的，伙伴系统通俗的讲就是以2^order 分配内存的。这些内存块我们就称为伙伴。

何为伙伴

两个块大小相同
两个块地址连续
两个块必须是同一个大块分离出来的

下面我们举个例子理解伙伴分配算法。假设我们要管理一大块连续的内存，有64个页面，假设现在来了一个请求，要分配8个页面。总不能把64个页面全部给他使用吧。

截图_20240623133911

首先把64个页面一切为二，每部分32个页面。

截图_20240623134103

把32个页面给请求者还是很大，这个时候会继续拆分为16个。

截图_20240623134157

最后会将16个页面继续拆分为8个，将其返回给请求者，这就完成了第一个请求。

截图_20240623134617

这个时候，第二个请求者也来了，同样的请求8个页面，这个时候系统就会把另外8个页面返回给请求者。

截图_20240623134828

假设现在有第三个请求者过来了，它请求4个页面。这个时候之前的8个页面都被分配走了，这个时候就要从16个页面的内存块切割了，切割后变为每份8个页面。最后将8个页面的内存块一分为二后返回给调用者。

截图_20240623134934

截图_20240623135122

假设前面分配的8个页面都已经用完了，这个时候可以把两个8个页面合并为16个页面。

截图_20240623135232

以上例子就是伙伴系统的简单的例子，大家可以通过这个例子通俗易懂的理解伙伴系统。

另外一个例子将要去说明三个条件中的第三个条件：两个块必须要是从同一个大块中分离出来的，这两个块才能称之为伙伴，才能去合并为一个大块。

我们以8个页面的一个大块为例子来说明，如图A0所示。将A0一分为二分，分别为 B0,B1。

B0：4页

B1：4页

再将B0，B1继续切分：

C0：2页

C1：2页

C2：2页

C3：2页

最后可以将C0，C1，C2，C3切分为1个页面大小的内存块。

我们从C列来看，C0，C1称之为伙伴关系，C2，C3为伙伴关系。

同理，page0 和 page1也为伙伴关系，因为他们都是从C0分割出来的。

截图_20240623140813

假设，page0正在使用，page1 和 page2都是空闲的。那page1 和 page 2 可以合并成一个大的内存块吗？

我们从上下级的关系来看，page 1，page 2 并不属于一个大内存块切割而来的，不属于伙伴关系。

如果我们把page 1 page 2，page4 page 5 合并了，看下结果会是什么样子。

截图_20240623141028

page0和page3 就会变成大内存块中孤零零的空洞了。page 0 和 page3 就无法再和其他块合并了。这样就形成了外碎片化。因此，内核的伙伴系统是极力避免这种清空发生的。

伙伴系统在内核中的实现

下面我们看下内核中是怎么实现伙伴系统的。

截图_20240623143810

上面这张图是内核中早期伙伴系统的实现

内核中把内存以2^order 为单位分为多个链表。order范围为[0，MAX_ORDER-1]，MAX_ORDER一般为11。因此，Linux内核中可以分配的最大的内存块为2^10= 4M，术语叫做page block。

内核中有一个叫free_area的数据结构，这个数据结构为链表的数组。数组的大小为MAX_ORDER。数组的每个成员为一个链表。分别表示对应order的空闲链表。以上就是早期的伙伴系统的页面分配器的实现。

现在的伙伴系统中的页面分配器的实现，为了解决内存碎片化的问题，在Linux内核2.6.4中引入了迁移类型的算法缓解内存碎片化的问题。

我们看这张图，现在的页面分配器中，每个free_area数组成员中都增加了一个迁移类型。也就是说在每个order链表中多增加了一个链表。例如，order = 0 的链表中，新增了MOVABLE 链表，UNMOVABLE 链表，RECLAIMABLE链表。随着内核的发展，迁移类型越来越多，但常用的就那三个。

迁移类型

在Linux内核2.6.4内核中引入了反碎片化的概念，反碎片化就是根据迁移类型来实现的。我们知道迁移类型是根据page block来划分的。我们看下常用的迁移类型。

MIGRATE_UNMOVABLE：在内存中有固定位置，不能随意移动，比如内核分配的内存。那为什么内核分配的不能迁移呢？因此要迁移页面，首先要把物理页面的映射关系断开，在新的地方分配物理页面，重新建立映射关系。在断开映射关系的途中，如果内核继续访问这个页面，会导致oop错误或者系统crash。因为内核是敏感区，内核必须保证它使用的内存是安全的。这一点和用户进程不一样。如果是用户进程使用的内存，我们将其断开后，用户进程再去访问，就会产生缺页中断，重新去寻找可用物理内存然后建立映射关系。
MIGRATE_MOVABLE：可以随意移动，用户态app分配的内存，mlock，mmap分配的匿名页面。
MIGRATE_RECLAIMABLE：不能移动可以删除回收，比如文件映射。

内存碎片化的产生

伙伴系统的迁移算法可以解决一些碎片化的问题，但在内存管理的方面，长期存在一个问题。从系统启动，长期运行之后，经过大量的分配-释放过程，还是会产生很多碎片，下面我们看下，这些碎片是怎么产生的。

我们以8个page的内存块为例，假设page3是被内核使用的，比如alloc_page(GFP_KERNRL)，所以它属于不可移动的页面，它就像一个桩一样，插入在一大块内存的中间。

尽管其他的页面都是空闲页面，导致page0 ~ page 7 不能合并为一个大块的内存。

下面我们看下，迁移类型是怎么解决这类问题的。我们知道，迁移算法是以page block为单位工作的，一个page block大小就是页面分配器能分配的最大内存块。也就是说，一个page block 中的页面都是属于一个迁移类型的。所以，就不会存在上面说的多个page中夹着一个不可迁移的类型的情况。

页面分配和释放常用的函数

页面分配函数

alloc_pages是内核中常用的分配物理内存页面的函数，用于分配2^order个连续的物理页。

static inline struct page *alloc_pages(gfp_t gfp_mask, unsigned int order)

gfp_mask：gfp的全称是get free page，因此gfp_mask表示页面分配的方法。gfp_mask的具体分类后面我们会详细介绍。
order：页面分配器使用伙伴系统按照顺序请求页面分配。所以只能以2的幂内存分配。例如，请求order=3的页面分配，最终会分配2 ^ 3 = 8页。arm64当前默认MAX_ORDER为11，即最多一次性分配2 ^（MAX_ORDER-1）个页。
返回值：返回指向第一个page的struct page指针

__get_free_page() 是页面分配器提供给调用者的最底层的内存分配函数。它分配连续的物理内存。__get_free_page() 函数本身是基于 buddy 实现的。在使用 buddy 实现的物理内存管理中最小分配粒度是以页为单位的。

unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)

返回值：返回第一个page映射后的虚拟地址。

#define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0)

alloc_page 是宏定义，逻辑是调用 alloc_pages，传递给 order 参数的值为 0，表示需要分配的物理页个数为 2 的 0 次方，即 1 个物理页，需要用户传递参数 GFP flags。

释放函数

void free_pages(unsigned long addr, unsigned int order)

释放2^order大小的页块,传入参数是页框首地址的虚拟地址

#define __free_page(page) __free_pages((page), 0)

释放一个页，传入参数是指向该页对应的虚拟地址

#define free_page(addr) free_pages((addr), 0)

释放一个页，传入参数是页框首地址的虚拟地址

gfp_mask标志位

行为修饰符

标志	描述
GFP_WAIT	分配器可以睡眠
GFP_HIGH	分配器可以访问紧急的内存池
GFP_IO	不能直接移动，但可以删除
GFP_FS	分配器可以启动文件系统IO
GFP_REPEAT	在分配失败的时候重复尝试
GFP_NOFAIL	分配失败的时候重复进行分配，直到分配成功位置
GFP_NORETRY	分配失败时不允许再尝试

zone 修饰符

标志	描述
GFP_DMA	从ZONE_DMA中分配内存（只存在与X86）
GFP_HIGHMEM	可以从ZONE_HIGHMEM或者ZONE_NOMAL中分配

水位修饰符

标志	描述
GFP_ATOMIC	分配过程中不允许睡眠，通常用作中断处理程序、下半部、持有自旋锁等不能睡眠的地方
GFP_KERNEL	常规的内存分配方式，可以睡眠
GFP_USER	常用于用户进程分配内存
GFP_HIGHUSER	需要从ZONE_HIGHMEM开始进行分配，也是常用于用户进程分配内存
GFP_NOIO	分配可以阻塞，但不会启动磁盘IO
GFP_NOFS	可以阻塞，可以启动磁盘，但不会启动文件系统操作

GFP_MASK和zone 以及迁移类型的关系

GFP_MASK除了表示分配行为之外，还可以表示从那些ZONE来分配内存。还可以确定从那些迁移类型的page block 分配内存。

我们以ARM为例，由于ARM架构没有ZONE_DMA的内存，因此只能从ZONE_HIGHMEM或者ZONE_NOMAL中分配.

在内核中有两个数据结构来表示从那些地方开始分配内存。

struct zonelist {
	struct zoneref _zonerefs[MAX_ZONES_PER_ZONELIST + 1];
};struct zonelist

zonelist是一个zone的链表。一次分配的请求是在zonelist上执行的。开始在链表的第一个zone上分配，如果失败，则根据优先级降序访问其他zone。
zlcache_ptr 指向zonelist的缓存。为了加速对zonelist的读取操作 ,用_zonerefs 保存zonelist中每个zone的index。

struct zoneref {
	struct zone *zone;	/* Pointer to actual zone */
	int zone_idx;		/* zone_idx(zoneref->zone) */
};

页面分配器是基于ZONE来设计的，因此页面的分配有必要确定那些zone可以用于本次页面分配。系统会优先使用ZONE_HIGHMEM，然后才是ZONE_NORMAL 。

基于zone 的设计思想，在分配物理页面的时候理应以zone_hignmem优先，因为hign_mem 在zone_ref中排在zone_normal的前面。而且，ZONE_NORMAL是线性映射的，线性映射的内存会优先给内核态使用。

页面分配的时候从那个迁移类型中分配出内存呢?

函数static inline int gfp_migratetype(const gfp_t gfp_flags)可以根据掩码类型转换出迁移类型，从那个迁移类型分配页面。比如GFP_KERNEL是从UNMOVABLE类型分配页面的。

ZONE水位

页面分配器是基于ZONE的机制来实现的，怎么去管理这些空闲页面呢？Linux内核中定义了三个警戒线，WATERMARK_MIN，WATERMARK_LOW，WATERMARK_HIGH。大家可以看下面这张图，就是分配水位和警戒线的关系。

最低水线(WMARK_MIN)：当剩余内存在min以下时，则系统内存压力非常大。一般情况下min以下的内存是不会被分配的，min以下的内存默认是保留给特殊用途使用，属于保留的页框，用于原子的内存请求操作。
比如：当我们在中断上下文申请或者在不允许睡眠的地方申请内存时，可以采用标志GFP_ATOMIC来分配内存，此时才会允许我们使用保留在min水位以下的内存。
低水线(WMARK_LOW)：空闲页数小数低水线，说明该内存区域的内存轻微不足。默认情况下，该值为WMARK_MIN的125%
高水线(WMARK_HIGH)：如果内存区域的空闲页数大于高水线，说明该内存区域水线充足。默认情况下，该值为WMARK_MAX的150%

在进行内存分配的时候，如果分配器（比如buddy allocator）发现当前空余内存的值低于”low”但高于”min”，说明现在内存面临一定的压力，那么在此次内存分配完成后，kswapd将被唤醒，以执行内存回收操作。在这种情况下，内存分配虽然会触发内存回收，但不存在被内存回收所阻塞的问题，两者的执行关系是异步的

对于kswapd来说，要回收多少内存才算完成任务呢？只要把空余内存的大小恢复到”high”对应的watermark值就可以了，当然，这取决于当前空余内存和”high”值之间的差距，差距越大，需要回收的内存也就越多。”low”可以被认为是一个警戒水位线，而”high”则是一个安全的水位线。

如果内存分配器发现空余内存的值低于了”min”，说明现在内存严重不足。这里要分两种情况来讨论，一种是默认的操作，此时分配器将同步等待内存回收完成，再进行内存分配，也就是direct reclaim。还有一种特殊情况，如果内存分配的请求是带了PF_MEMALLOC标志位的，并且现在空余内存的大小可以满足本次内存分配的需求，那么也将是先分配，再回收。

per-cpu页面分配

内核会经常请求和释放单个页框，比如网卡驱动。

页面分配器分配和释放页面的时候需要申请一把锁：zone->lock
- 为了提高单个页框的申请和释放效率，内核建立了per-cpu页面告诉缓存池
- 其中存放了若干预先分配好的页框
当请求单个页框时，直接从本地cpu的页框告诉缓存池中获取页框
- 不必申请锁
- 不必进行复杂的页框分配操作
体现了预先建立缓存池的优势，而且是每个CPU有一个独立的缓存池

per-cpu数据结构

由于页框频繁的分配和释放，内核在每个zone中放置了一些事先保留的页框。这些页框只能由来自本地CPU的请求使用。zone中有一个成员pageset字段指向per-cpu的高速缓存，高速缓存由struct per_cpu_pages数据结构来描述。

struct per_cpu_pages {
	int count;		/* number of pages in the list */
	int high;		/* high watermark, emptying needed */
	int batch;		/* chunk size for buddy add/remove */

	/* Lists of pages, one per migrate type stored on the pcp-lists */
	struct list_head lists[MIGRATE_PCPTYPES];
};