Linux 教程 | 内存管理篇之页框管理

背景:

页框管理是Linux系统的基本功能,主要负责维护RAM资源，完成系统对RAM资源请求的分配。 Linux 把 RAM 每 4KB( $2^{12}$ )划分为一个页框,这样正好与页大小相等或为页框的整数倍，便于请求页框。

利用页框机制有助于灵活分配内存地址，因为分配时不必要求必须有大块的连续内存，系统可以离散寻找空闲页凑出所需要的内存供进程使用。 虽然如此，但是实际上系统使用内存时还是倾向于分配连续的内存块，因为分配连续内存时，页表不需要更改，因此能降低TLB的刷新率。

为了能够在保存连续页的同时，又能满足对启动内存需求的分配， 页框在分配上使用了伙伴系统。

下面我们通过细节介绍下过程.

页框管理的数据结构:

page

在内核中每一个物理页框对应有一个页描述符(struct page), 所有的页描述符存放在一个mem_map线性数组之中。 每一个页框的页框号(address >> PAGE_SHIFT), 为页描述符在 mem_map 数组的位置(下标)。 每一个描述符占用32字节长度的大小，所以 mem_map 所用空间约占RAM %1(32B/32KB)左右.

关于页描述符，位于include/linux/mm.h 可以找到其定义:

struct page {
  /**
	 * 一组标志，
	 *   - 也对页框所在的管理区进行编号
	 *   - 描述页框的状态: 如 页被锁定，IO错误, 被访问，被修改位于活动页，位于slab 等。
	 */
	page_flags_t flags;		

  /**
	 * 页框的引用计数。
	 *   - 小于0表示没有人使用。
	 *   - 大于0表示使用人数目
	 */
	atomic_t _count;

  /**
	 * 页框中的页表项数目（没有则为-1）
	 *		-1:		表示没有页表项引用该页框。
	 *		0:		表明页是非共享的。
	 *		>0:		表示而是共享的。
	 */
	atomic_t _mapcount;

  /**
	 * 可用于正在使用页的内核成分（如在缓冲页的情况下，它是一个缓冲器头指针。）
	 * 如果页是空闲的，则该字段由伙伴系统使用。
	 * 当用于伙伴系统时，如果该页是一个2^k的空闲页块的第一个页，那么它的值就是k.
	 * 这样，伙伴系统可以查找相邻的伙伴，以确定是否可以将空闲块合并成2^(k+1)大小的空闲块。
	 */
	unsigned long private;


  /**
	 * 当页被插入页高速缓存时使用或者当页属于匿名页时使用）。
	 * 		如果mapping字段为空，则该页属于交换高速缓存(swap cache)。
	 *		如果mapping字段不为空，且最低位为1，表示该页为匿名页。同时该字段中存放的是指向anon_vma描述符的指针。
	 *		如果mapping字段不为空，且最低位为0，表示该页为映射页。同时该字段指向对应文件的address_space对象。
	 */
	struct address_space *mapping;

  /**
	 * 作为不同的含义被几种内核成分使用。
	 *  - 在页磁盘映象或匿名区中表示存放在页框中的数据的位置。不是页内偏移量，而是该页面相对于文件起始位置，以页面为大小的偏移量
	 *  - 或者它存放在一个换出页标志符。表示所有者的地址空间中以页大小为单位的偏移量，也就是磁盘映像中页中数据的位置 page->index是区域内的页索引或是页的线性地址除以PAGE_SIZE
	 */
	pgoff_t index;			

  struct list_head lru;	// 包含页的最近最少使用的双向链表的指针， 用于伙伴系统

#if defined(WANT_PAGE_VIRTUAL)
  /**
	 * 如果进行了内存映射，就是内核虚拟地址。对存在高端内存的系统来说有意义。
	 * 否则是NULL
	 */
	void *virtual;
#endif /* WANT_PAGE_VIRTUAL */

与页描述符相关的宏定义

内核可以使用相关方法来定位每一个地址对应的页描述符地址。

#define __pa(x)			((unsigned long)(x)-PAGE_OFFSET)
#define pfn_to_page(pfn)	(mem_map + (pfn))                          // 根据页框号来定位页描述符
#define virt_to_page(kaddr)	pfn_to_page(__pa(kaddr) >> PAGE_SHIFT)   // 内核线性地址定位页描述符
#define page_address(page) ((page)->virtual)                         // 返回描述符对应的内核虚拟地址(内存映射)

节点 node

在 linux 2.6 版本内核中支持一种 NUMA(非一致内存访问) 模型, 它支持根据CPU对不同内存单元访问时间的不同，将物理内存划分为不同的节点，每个节点中，指定CPU对节点内任意内存单元访问时间都是相同的。

每个节点具有一个节点描述符(struct pg_data_t) 的数据结构来表示, 所有的节点都使用单链表来统一维护(pg_data_t-> pgdat_next)。

节点描述符的定义位于include/linux/mmzone.h中 :

typedef struct pglist_data {
	struct zone node_zones[MAX_NR_ZONES];              // 节点管理区描述符数组
	struct zonelist node_zonelists[GFP_ZONETYPES];     // 页分配器使用的zonelist数据结构的数组。
	int nr_zones;                                      // 节点中管理区的个数
	struct page *node_mem_map;                         // 节点中页描述符的数组
	struct bootmem_data *bdata;                        // 用在内核初始化阶段
	unsigned long node_start_pfn;                      // 节点中第一个页框的下标
	unsigned long node_present_pages;                  // 内存结点的大小，不包含空洞（以页为单位）
	unsigned long node_spanned_pages;                  // 节点的大小，包括空洞
	int node_id;                                       // 节点标识符
	struct pglist_data *pgdat_next;                    // 内存节点链表的下一项。该字段构成node单链表。
	wait_queue_head_t kswapd_wait;                     // Kswapd页换出守护进程使用的等待队列
	struct task_struct *kswapd;                        // 指针指向kswapd内核线程的进程描述符。
	int kswapd_max_order;                              // Kswapd将要创建的空闲块大小取对数的值。
} pg_data_t;

但在8086体系架构中只使用了UMA(一致访问内存) 模型，从理论上并不需要NUMA的支持， 但是为了代码可移植性，还是把所有的RAM所有物理内存都放在一个节点描述符中。

/**
 * 支持NUMA。
 * 这个元素由contig_page_data表示。它包含在一个只有一个结点的链表中，这个链表被pgdat_list指向。
 */
struct pglist_data contig_page_data = { .bdata = &contig_bootmem_data };

管理区描述符 zone

理想架构中，页框作为内存存储单元可以存储内核和用户数据，磁盘数据缓存等等。任何页数据都可以存在任何页框中，没有任何限制。然而真实的架构有着硬件限制。

Linux内核必须处理 80x86 架构的两个硬件限制：

• 旧ISA总线的DMA处理器有一个严格的限制：它们只能寻址RAM的前16MB空间。
• 现代32位计算机有很多RAM，CPU不能直接访问所有的物理内存，因为线性地址空间太小了。(内核线性地址只有3G到4G这1GB，而RAM当前比这大得多，设计成一对一肯定是不行的，所以映射机制是个复杂的大杂烩。)

为了应付这两个限制，Linux在80x86 UMA架构中分割物理内存node成3个zones:

• ZONE_DMA : 包含低16MB的内存页框，用于兼容旧ISA总线DMA处理器
• ZONE_NORMAL : 包含16MB到896MB的内存页框
• ZONE_HIGHMEM : 包含高于896MB的内存页框

说明:

• ZONE_DMA 给旧ISA总线设备用。ZONE_DMA 和 ZONE_NORMAL 包含内存的常规页框，通过线性映射到4GB的线性地址空间，它们可以被 内核 直接使用。(详细过程将在内核地址空间篇中介绍)

• ZONE_HIGHMEM 包含不能够直接被内核访问的内存页框。

• 此外，因为x64虚拟地址空间的膨胀，ZONE_HIGHMEN zone在64bit机器上总是空的(没有存在的必要)。

有关管理区描述符的定义位于include/linux/mmzone.h中:

struct zone {

	unsigned long		free_pages;                                // 管理区空闲页的数目
	unsigned long		pages_min;                                 // 管理区中保留页的数目
  unsigned long   pages_low;                                 // 回收页框使用的下界。同时也被管理区分配器为作为阈值使用。
  unsigned long   pages_high;                                // 回收页框使用的上界，同时也被管理区分配器作为阈值使用。
	unsigned long		lowmem_reserve[MAX_NR_ZONES];              // 为内存不足保留的页框，分别为各种内存域指定了若干页,用于一些无论如何都不能失败的关键性内存分配

  /**
	 * 用于实现单一页框的特殊高速缓存。
	 * 每内存管理区对每CPU都有一个。包含热高速缓存和冷高速缓存。
	 * 内核使用这些列表来保存可用于满足实现的“新鲜”页。
	 * 有些页帧很可能在CPU高速缓存中，因此可以快速访问，称之为热。
	 * 未缓存的页帧称之为冷的。
	 */
	struct per_cpu_pageset	pageset[NR_CPUS];

	spinlock_t		lock;                                    // 保护该描述符的自旋锁

  /**
	 * 标识出管理区中的空闲页框块。
	 * 包含11个元素，被伙伴系统使用。分别对应大小的1,2,4,8,16,32,128,256,512,1024连续空闲块的链表。
	 * 第k个元素标识所有大小为2^k的空闲块。free_list字段指向双向循环链表的头。
	 * free_list是free_area的内部结构，是个双向环回链表节点。
	 */
	struct free_area	free_area[MAX_ORDER];


	ZONE_PADDING(_pad1_)                                    // 为了cache line对齐加的pad

	spinlock_t		lru_lock;	                                // 活动以及非活动链表使用的自旋锁。
	struct list_head	active_list;                          // 管理区中的活动页链表
	struct list_head	inactive_list;                        // 管理区中的非活动页链表。
	unsigned long		nr_scan_active;                         // 回收内存时需要扫描的活动页数。
	unsigned long		nr_scan_inactive;                       // 回收内存时需要扫描的非活动页数目。
	unsigned long		nr_active;                              // 管理区的活动链表上的页数目。
	unsigned long		nr_inactive;                            // 管理区的非活动链表上的页数目。
	unsigned long		pages_scanned;	                        // 管理区内回收页框时使用的计数器。
	int			        all_unreclaimable;                      // 在管理区中填满不可回收页时此标志被置位                   


	int temp_priority;                                      // 临时管理区的优先级。
	int prev_priority;                                      // 管理区优先级，范围在12和0之间。


	ZONE_PADDING(_pad2_)

	wait_queue_head_t	* wait_table;                         // 进程等待队列的散列表。这些进程正在等待管理区中的某页。
	unsigned long		wait_table_size;                        // 等待队列散列表的大小。
	unsigned long		wait_table_bits;                        // 等待队列散列表数组的大小。值为2^order


	struct pglist_data	*zone_pgdat;                        // 内存节点。
	struct page		*zone_mem_map;                            // 指向管理区的第一个页描述符的指针。这个指针是数组mem_map的一个元素。

  /**
   * zone_start_pfn == zone_start_paddr >> PAGE_SHIFT
   */
	unsigned long		zone_start_pfn;                          // 管理区的第一个页框的下标。
	unsigned long		spanned_pages;	                         // 以页为单位的管理区的总大小，包含空洞。
	unsigned long		present_pages;	                         // 以页为单位的管理区的总大小，不包含空洞。

	char			*name;                                         // 指针指向管理区的传统名称：DMA、NORMAL、HighMem
} ____cacheline_maxaligned_in_smp;

说明 ：

由于 struct zone 结构经常被访问到, 因此这个数据结构要求以 L1 Cache 对齐. 另外, 这里的 ZONE_PADDING() 让 zone->lock 和 zone_lru_lock 这两个很热门的锁可以分布在不同的 Cahe Line 中.

一个内存 node 节点最多也就几个 zone, 因此 zone 数据结构不需要像 struct page 一样关心数据结构的大小, 因此这里的 ZONE_PADDING() 可以理解为用空间换取时间(性能). 在内存管理开发过程中, 内核开发者逐渐发现有一些自选锁竞争会非常厉害, 很难获取. 像 zone->lock 和 zone->lru_lock 这两个锁有时需要同时获取锁. 因此保证他们使用不同的 Cache Line 是内核常用的一种优化技巧.

---

页框分配机制

内核子系统中有一个 分区页框分配器 ,用于处理对连续页框组的内存分配请求。其中名为 管理区分配器 部分接受动态内存分配与释放请求。

在每个管理区内，页框被名为伙伴系统的部分来处理。为了达到更好的系统性能，一小部分页框保留在高速缓存中用于快速满足对单个页框的分配请求。

保留页框池

每个管理区都有一个保留页框池，用于满足对于非阻塞内核控制路径对于内存请求与原子内存分配情况下，出现内存不足情况下，为了减少请求失败而特地保留的。

总的保留内存页数量由min_free_kbytes变量来决定，每个管理区的保留页框数按照管理区总大小的比例来划分。

管理区描述符字段 page_min 存储了管理区内保留页框的数目。

尽管无法保证一个原子内存分配请求绝不会失败，但是内核会设法尽量减少这种不幸的事件发生的可能性。 当其请求发生内存不足时，这时候会使用保留区页框。 如果保留区页框仍无法满足， 则分配请求失败。

每CPU页框高速缓存

由于内核经常请求和释放单个页框。为了提升系统性能，每个内存管理区定义了一个每CPU页框高速缓存。所有高速缓存包含一些预先分配的页框，它们被用于满足本地CPU发出单一内存请求。

Linux为每个内存管理区和每CPU提供了两个高速缓存：热高速和冷高速。

热高速缓存 ：

如果内核或用户态进程在刚分配到页框后就立即向页框写，那么从热高速缓存中获得页框就对系统性能有利。 什么意思？ 我们知道，CPU中的硬件高速缓存存在有最近使用过的页框。而我们每次对页框存储单元的访问将都会导致原来一个存在于硬件高速缓存的一页被替换掉。 当然，除非硬件高速缓存包含有一行：它映射刚被访问的 “热”页框单元，那么我们称为“命中”。

冷高速缓存 :

如果页框将要被DMA操作填充，那么从冷高速缓存中获得页框是方便的。 在这种情况下， 不会涉及到CPU，并且硬件高速缓存的行不会被修改。 从冷高速缓存获得页框为其他类型的内存分配保存了热页框储备。

每cpu高速缓存定义:

struct per_cpu_pageset {
	/**
   * 0 ： 冷高速缓存
	 * 1 ： 热高速缓存
	 */
	struct per_cpu_pages pcp[2];
} ____cacheline_aligned_in_smp;

/**
 * 内存管理区页框高速缓存描述符
 */
struct per_cpu_pages {
	int count;		      // 高速缓存中的页框个数
	int low;		        // 下界，低于此就需要补充高速缓存。
	int high;		        // 上界，高于此则向伙伴系统释放页框。
	int batch;		      // 当需要增加或者减少高速缓存页框时，操作的页框个数。
	struct list_head list;	// 高速缓存中包含的页框描述符链表。
};

伙伴系统

伙伴系统是为了应对内存管理中的经典性问题 - 内存碎片

• 伙伴系统的分配器维护空闲页面所组成的块, 这里每一块都是2的方幂个页框大小, 方幂的指数称为阶，阶最大值为 MAX_ORDER(11)。
• 每个块的第一个页框的物理地址时改块大小的整数倍
• 所有相同大小的块使用链表维护在一起， 总共具有 MAX_ORDER 个链表，

伙伴系统采用 free_area 中的链表结构来维护由相同大小构成的块，使用管理区描述符中的free_area数组来维护所有的块链表。

struct free_area {
	struct list_head	free_list;  // page 双向链表
	unsigned long	nr_free;        // 块数量
};

伙伴系统的分配算法:

对于一个 2^{k} 个连续页框大小的内存申请， 伙伴系统首先查看 zone->free_area[k] 中是否有空闲的块。如果找到，则直接分配给请求对象。 否则， 查找 zone->free_area[k+1] 是否有空闲块，如果有: 则摘下一块，并且分成两等分，分配一份给请求对象，另一份插入到 zone->free_area[k] 中。 如果仍旧没找到， 则依次往上查找，直到满足需求。

函数 __rmqueue() 负责使用伙伴系统算法查找合适的块给请求对象 :

/**
 * 在管理区中找到一个空闲块。
 * 它需要两个参数：管理区描述符的地址和order。Order表示请求的空闲页块大小的对数值。
 * 如果页框被成功分配，则返回第一个被分配的页框的页描述符。否则返回NULL。
 * 本函数假设调用者已经禁止和本地中断并获得了自旋锁。
 */
static struct page *__rmqueue(struct zone *zone, unsigned int order)
{
	struct free_area * area;
	unsigned int current_order;
	struct page *page;

	/**
	 * 从所请求的order开始，扫描每个可用块链表进行循环搜索。
	 */
	for (current_order = order; current_order < MAX_ORDER; ++current_order) {
		area = zone->free_area + current_order;
		/**
		 * 对应的空闲块链表为空，在更大的空闲块链表中进行循环搜索。
		 */
		if (list_empty(&area->free_list))
			continue;

		/**
		 * 运行到此，说明有合适的空闲块。
		 */
		page = list_entry(area->free_list.next, struct page, lru);
		/**
		 * 首先在空闲块链表中删除第一个页框描述符。
		 */
		list_del(&page->lru);
		rmv_page_order(page);
		area->nr_free--;
		/**
		 * 并减少空闲管理区的空闲页数量。
		 */
		zone->free_pages -= 1UL << order;
		/**
		 * 如果2^order空闲块链表中没有合适的空闲块，那么就是从更大的空闲链表中分配的。
		 * 将剩余的空闲块分散到合适的链表中去。
		 */
		return expand(zone, page, order, current_order, area);
	}

	/**
	 * 直到循环结束都没有找到合适的空闲块，就返回NULL。
	 */
	return NULL;
}

static inline struct page *
 expand(struct zone *zone, struct page *page, int low, int high, struct free_area *area)
{
	unsigned long size = 1 << high;

	while (high > low) {
		area--;
		high--;
		size >>= 1;
		BUG_ON(bad_range(zone, &page[size]));
        /*
         * 后半部分(page[size])加入free_area->free_list中，并设定order
         * 前半部分(page)，继续进行分裂或者返回
         */
		list_add(&page[size].lru, &area->free_list);
		area->nr_free++;
		set_page_order(&page[size], high);
	}
	return page;
}

伙伴系统的回收算法:

回收算法根据提供的块大小，将块放到大小对应的链表中。 如果放入过程中发现有伙伴块， 则合并伙伴， 形成更大的块放到上层链表中。

**
 * 按照伙伴系统的策略释放页框。
 * page-被释放块中所包含的第一个页框描述符的地址。
 * zone-管理区描述符的地址。
 * order-块大小的对数。
 * base-纯粹由于效率的原因而引入。其实可以从其他三个参数计算得出。
 * 该函数假定调用者已经禁止本地中断并获得了自旋锁。
 */
static inline void __free_pages_bulk (struct page *page, struct page *base,
		struct zone *zone, unsigned int order)
{
	/**
	 * page_idx包含块中第一个页框的下标。
	 * 这是相对于管理区中的第一个页框而言的。
	 */
	unsigned long page_idx;
	struct page *coalesced;
	/**
	 * order_size用于增加管理区中空闲页框的计数器。
	 */
	int order_size = 1 << order;

	if (unlikely(order))
		destroy_compound_page(page, order);

	page_idx = page - base;

	/**
	 * 大小为2^k的块，它的线性地址都是2^k * 2 ^ 12的整数倍。
	 * 相应的，它在管理区的偏移应该是2^k倍。
	 */
	BUG_ON(page_idx & (order_size - 1));
	BUG_ON(bad_range(zone, page));

	/**
	 * 增加管理区的空闲页数
	 */
	zone->free_pages += order_size;
	/**
	 * 最多循环10 - order次。每次都将一个块和它的伙伴进行合并。
	 * 每次从最小的块开始，向上合并。
	 */
	while (order < MAX_ORDER-1) {
		struct free_area *area;
		struct page *buddy;
		int buddy_idx;

		/**
		 * 最小块的下标。它是要合并的块的伙伴。
		 * 注意异或操作的用法，是如何用来寻找伙伴的。
		 * 相当于在page_idx加上或者减去1 << order的距离就是buddy_idx
		 */
		buddy_idx = (page_idx ^ (1 << order));
		/**
		 * 通过伙伴的下标找到页描述符的地址。
		 */
		buddy = base + buddy_idx;
		if (bad_range(zone, buddy))
			break;
		/**
		 * 判断伙伴块是否是大小为order的空闲页框的第一个页。
		 * 首先，伙伴的第一个页必须是空闲的(_count == -1)
		 * 同时，必须属于动态内存(PG_reserved被清0,PG_reserved为1表示留给内核或者没有使用)
		 * 最后，其private字段必须是order
		 */
		if (!page_is_buddy(buddy, order))
			break;
		/**
		 * 运行到这里，说明伙伴块可以与当前块合并。
		 */
		/* Move the buddy up one level. */
		/**
		 * 伙伴将被合并，将它从现有链表中取下。
		 */
		list_del(&buddy->lru);
		area = zone->free_area + order;
		area->nr_free--;
		rmv_page_order(buddy);
        /*
         * 计算parent_idx
         */
		page_idx &= buddy_idx;
		/**
		 * 将合并了的块再与它的伙伴进行合并。
		 */
		order++;
	}

	/**
	 * 伙伴不能与当前块合并。
	 * 将块插入适当的链表，并以块大小的order更新第一个页框的private字段。
	 */
	coalesced = base + page_idx;
	set_page_order(coalesced, order);
	list_add(&coalesced->lru, &zone->free_area[order].free_list);
	zone->free_area[order].nr_free++;
}

页框分配器:

页框分配接口:

页框分配函数位于 include/linux/gfp.h 中定义:

/**
 * 分配2^order个连续的页框。它返回第一个所分配页框描述符的地址或者返回NULL
 */
#define alloc_pages(gfp_mask, order) \
		alloc_pages_node(numa_node_id(), gfp_mask, order)

/**
 * 用于获得一个单独页框的宏
 * 它返回所分配页框描述符的地址，如果失败，则返回NULL
 * alloc_page就是alloc_pages的特例
 */
#define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0)

/**
 * 类似于alloc_pages，但是它返回第一个所分配页的线性地址。
 * 从实现中发现，使用场景在内核空间中使用内存映射
 */
fastcall unsigned long __get_free_pages(unsigned int gfp_mask, unsigned int order)
{
	struct page * page;
	page = alloc_pages(gfp_mask, order);
	if (!page)
		return 0;
	return (unsigned long) page_address(page);
}

/**
 * 用于获得一个单独页框的宏。返回线性地址
 */
#define __get_free_page(gfp_mask) \
		__get_free_pages((gfp_mask),0)


/**
 * 用于获取填满0的页框。
 * 返回的是页框对应的虚拟地址VA
 */
fastcall unsigned long get_zeroed_page(unsigned int gfp_mask)
{
	struct page * page;

	/*
	 * get_zeroed_page() returns a 32-bit address, which cannot represent
	 * a highmem page
	 */
	BUG_ON(gfp_mask & __GFP_HIGHMEM);

	page = alloc_pages(gfp_mask | __GFP_ZERO, 0);
	if (page)
		return (unsigned long) page_address(page);
	return 0;
}

/**
 * 用于获得适用于DMA的页框。
 */
#define __get_dma_pages(gfp_mask, order) \
		__get_free_pages((gfp_mask) | GFP_DMA,(order))


static inline struct page *alloc_pages_node(int nid, unsigned int gfp_mask,
						unsigned int order)
{
	if (unlikely(order >= MAX_ORDER))
		return NULL;

	return __alloc_pages(gfp_mask, order,
		NODE_DATA(nid)->node_zonelists + (gfp_mask & GFP_ZONEMASK));
}

页框分配细节实现:

可以看出，分配页框系列函数都是 alloc_pages 的包装，做了些善后工作，传递了不同的参数。 alloc_pages 又调用了 __alloc_pages

所以根本还是在 __alloc_pages 函数中:

/**
 * 请求分配一组连续页框，它是管理区分配器的核心
 * gfp_mask：在内存分配请求中指定的标志
 * order：   连续分配的页框数量的对数(实际分配的是2^order个连续的页框)
 * zonelist: zonelist数据结构的指针。该结构按优先次序描述了适于内存分配的内存管理区
 */
struct page * fastcall
__alloc_pages(unsigned int gfp_mask, unsigned int order,
		struct zonelist *zonelist)
{
	const int wait = gfp_mask & __GFP_WAIT;
	struct zone **zones, *z;
	struct page *page;
	struct reclaim_state reclaim_state;
	struct task_struct *p = current;
	int i;
	int classzone_idx;
	int do_retry;
	int can_try_harder;
	int did_some_progress;

	might_sleep_if(wait);

	/*
	 * The caller may dip into page reserves a bit more if the caller
	 * cannot run direct reclaim, or is the caller has realtime scheduling
	 * policy
	 */
	can_try_harder = (unlikely(rt_task(p)) && !in_interrupt()) || !wait;

	zones = zonelist->zones;       /* the list of zones suitable for gfp_mask */

	if (unlikely(zones[0] == NULL)) {
		return NULL;
	}

	classzone_idx = zone_idx(zones[0]);

 restart:
  	/**
     * 扫描包含在zonelist数据结构中的每个内存管理区:
     *
  	 *  - 这里可以看到对zonelist的扫描顺序，是按索引从前向后的。
  	 *  - 那么zonelist是如何布局的呢？如何为不同zone区分高低贵贱呢？
  	 *  - 对于UMA架构比较简单，因为只有单一node，在build_zonelists中可以一探究竟
  	 *  - 简单归纳来说，HIGHMEM最廉价、NORMAL次之，DMA最昂贵。
  	 */
	for (i = 0; (z = zones[i]) != NULL; i++) {
		/**
		 * 对于每个内存管理区，该函数将空闲页框的个数与一个阀值进行比较
		 * 该值取决于内存分配标志、当前进程的类型及管理区被函数检查的次数。
		 * 实际上，如果空闲内存不足，那么每个内存管理区一般会被检查几次。
		 * 每一次在所请求的空闲内存最低量的基础上使用更低的值进行扫描。
		 * 因此，这段循环代码会被复制几次，而变化很小。
		 */

		/**
		 * zone_watermark_ok 辅助函数接收几个参数，它们决定内存管理区中空闲页框个数的阀值min。
		 * 这是对内存管理区的第一次扫描，在第一次扫描中，阀值设置为z->pages_low
		 */
		if (!zone_watermark_ok(z, order, z->pages_low, classzone_idx, 0, 0))
			continue;
		/*
		 * 这个函数就是关键的分配函数，它杂糅了伙伴系统分配策略 + 本地CPU高速缓存
		 */
		page = buffered_rmqueue(z, order, gfp_mask);
		if (page)
			goto got_pg;
	}

	/**
	 * 一般来说，应当在上一次扫描时得到内存。
	 *  - 运行到此，表示内存已经紧张了（xie.baoyou注：没有连续的页框可供分配了）
	 *  - 就唤醒 kswapd 内核线程来异步的开始回收页框。
	 */
	for (i = 0; (z = zones[i]) != NULL; i++)
    // 后面介绍
		wakeup_kswapd(z, order);


	/**
	 * 执行对内存管理区的第二次扫描，将值 z->pages_min 作为阀值传入。
   * 并确定是否要是用保留页框池
	 *  - 这个值已经在上一步的基础上降低了
	 *      pages_low 一般是 pages_min 的 5/4，pages_high 一般是pages_min的3/2
	 *  - 当然，实际的min值还是要由can_try_harder和gfp_high确定。
	 * z->pages_min仅仅是一个参考值而已。
	 */
	for (i = 0; (z = zones[i]) != NULL; i++) {
    // 这时候如果 __GFP_HIGH或者非中断被置位，这时候将会调用预留区页框
		if (!zone_watermark_ok(z, order, z->pages_min, classzone_idx, can_try_harder,
				       gfp_mask & __GFP_HIGH))
			continue;
		/*
		 * 第二次扫描后，可能因为阈值的降低也可能因为异步的kswapd内核线程回收了页框
		 * 此时已经可以满足分配需求了
		 */
		page = buffered_rmqueue(z, order, gfp_mask);
		if (page)
			goto got_pg;
	}

	/**
	 * 上一步都还没有获得内存，系统内存肯定是不足了。
	 */

	/**
	 * 如果产生内存分配的内核控制路径不是一个中断处理程序或者可延迟函数，
	 * 并且它试图回收页框（PF_MEMALLOC，TIF_MEMDIE标志被置位）, 那么才对内存管理区进行第三次扫描。
	 */
	if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE))) && !in_interrupt()) {
		/* go through the zonelist yet again, ignoring mins */
		for (i = 0; (z = zones[i]) != NULL; i++) {
			/**
			 * 本次扫描就不调用zone_watermark_ok，它忽略阀值，这样才能从预留的页中分配页。
			 * 允许这样做，因为是这个进程想要归还页框，那就暂借一点给它吧（呵呵，舍不得孩子套不到狼）。
			 */
			page = buffered_rmqueue(z, order, gfp_mask);
			if (page)
				goto got_pg;
		}

    // 确实是没有了
		goto nopage;
	}

	/**
	 * 如果gfp_mask的__GFP_WAIT标志没有被置位，函数就返回NULL。
   * 说明为内核控制路径或者是原子性分配内存操作， 当第二次尝试分配发现内存不满足， 则抛出分配失败
	 */
	if (!wait)
		goto nopage;

rebalance:
	/**
	 * 如果当前进程能够被阻塞，调用cond_resched检查是否有其他进程需要CPU
	 */
	cond_resched();

	/**
	 * 设置PF_MEMALLOC标志来表示进程已经准备好执行内存回收。
	 */
	p->flags |= PF_MEMALLOC;
	reclaim_state.reclaimed_slab = 0;

  /**
	 * 将 reclaim_state 数据结构指针存入 reclaim_state。这个结构只包含一个字段reclaimed_slab，初始值为0
	 */
	p->reclaim_state = &reclaim_state;

	/**
	 * 调用try_to_free_pages寻找一些页框来回收。
	 * 这个函数可能会阻塞当前进程。一旦返回，就重设PF_MEMALLOC，并再次调用cond_resched
	 */
	did_some_progress = try_to_free_pages(zones, gfp_mask, order);

	p->reclaim_state = NULL;
	p->flags &= ~PF_MEMALLOC;

	cond_resched();

	/**
	 * 如果已经回收了一些页框，那么执行第二遍扫描类似的操作。
	 */
	if (likely(did_some_progress)) {

		for (i = 0; (z = zones[i]) != NULL; i++) {
      // 这时候如果 __GFP_HIGH或者非中断被置位，这时候将会调用预留区页框
			if (!zone_watermark_ok(z, order, z->pages_min, classzone_idx,
              can_try_harder, gfp_mask & __GFP_HIGH))
				continue;

			page = buffered_rmqueue(z, order, gfp_mask);
			if (page)
				goto got_pg;
		}
	} else if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {

		/**
		 * 没有释放任何页框，说明内核遇到很大麻烦了。因为内存少又不能释放页框。
		 * 如果允许杀死进程：__GFP_FS被置位并且__GFP_NORETRY标志为0。
		 * 那就开始准备杀死进程吧。
		 */

		/**
		 * 再扫描一次内存管理区。
		 * 这样做有点莫名其妙，既然申请少一点的内存都不行，为什么还要传入z->pages_high？？它看起来更不会成功。
		 * 其实这样做还是有道理的：实际上，只有另一个内核控制路径已经杀死一个进程来回收它的内存后，这步才会成功。
		 * 因此，这步避免了两个（而不是一个）无辜的进程被杀死。
		 */
		for (i = 0; (z = zones[i]) != NULL; i++) {
			if (!zone_watermark_ok(z, order, z->pages_high,
					       classzone_idx, 0, 0))
				continue;

			page = buffered_rmqueue(z, order, gfp_mask);
			if (page)
				goto got_pg;
		}

		/**
		 * 还是不行，就杀死一些进程再试吧。
		 */
		out_of_memory(gfp_mask);

		goto restart;
	}

	/**
	 * 如果内存分配请求不能被满足，那么函数决定是否应当继续扫描内存管理区。
	 * 如果__GFP_NORETRY被清除，并且内存分配请求跨越了多达8个页框或者__GFP_REPEAT被置位，或者__GFP_NOFAIL被置位。
	 */
	do_retry = 0;
	if (!(gfp_mask & __GFP_NORETRY)) {
		if ((order <= 3) || (gfp_mask & __GFP_REPEAT))
			do_retry = 1;
		if (gfp_mask & __GFP_NOFAIL)
			do_retry = 1;
	}
	/**
	 * 要重试，就调用 blk_congestion_wait 使进程休眠一会。再跳到rebalance 重试。
	 */
	if (do_retry) {
		blk_congestion_wait(WRITE, HZ/50);
		goto rebalance;
	}
	/**
	 * 既然不用重试，那就执行到nopage 返回NULL 了。
	 */
nopage:
	if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {
		printk(KERN_WARNING "%s: page allocation failure."
			" order:%d, mode:0x%x\n",
			p->comm, order, gfp_mask);
		dump_stack();
	}
	return NULL;
got_pg:
	zone_statistics(zonelist, z);
	return page;
}


/**
 * zone_watermark_ok辅助函数接收几个参数，它们决定内存管理区中空闲页框个数的阀值min。
 * 特别的，如果满足下列两个条件，则该函数返回1：
 *     1、除了被分配的页框外，在内存管理区中至少还有min个空闲页框，不包括为内存不足保留的页框（zone的lowmem_reserve字段）。
 *     2、除了被分配的页框外，这里在order至少为k的块中，起码还有min/2^k个空闲页框。其中对每个k，取值在1和order之间。
 *
 * 作为参数传递的基本值可以是内存管理区界值pages_min,pages_low,pages_high中的任意一个。
 */
int zone_watermark_ok(struct zone *z, int order, unsigned long mark,
		      int classzone_idx, int can_try_harder, int gfp_high)
{
	/* free_pages my go negative - that's OK */
	long min = mark, free_pages = z->free_pages - (1 << order) + 1; /*free_pages是除了要分配的页框(1<<order)后剩余的空闲页面*/
	int o;

	/**
	 * 如果gfp_high标志被置位。则base除2。
	 * 注意这里不是：min /= 2;
	 * 一般来说，如果gfp_mask的__GFP_HIGH标志被置位，那么这个标志就会为1
	 * 换句话说，就是指从高端内存中分配。
	 */
	if (gfp_high)
		min -= min / 2;
	/**
	 * 如果作为参数传递的can_try_harder标志被置位，这个值再减少1/4
	 * can_try_harder=1一般是当：gfp_mask中的__GFP_WAIT标志被置位，或者当前进程是一个实时进程并且在进程上下文中已经完成了内存分配。
	 */
	if (can_try_harder)
		min -= min / 4;

    /*
     * 除了被分配的页框外，在内存管理区中至少还有min个空闲页框，不包括为内存不足保留的页框（zone的lowmem_reserve字段）。
     */
	if (free_pages <= min + z->lowmem_reserve[classzone_idx])
		return 0;

    /*
     * 除了被分配的页框外，这里在order至少为k的块中，起码还有min/2^k个空闲页框。其中对每个k，取值在1和order之间。
     */
	for (o = 0; o < order; o++) {
		/* At the next order, this order's pages become unavailable */
		free_pages -= z->free_area[o].nr_free << o;

		/* Require fewer higher order pages to be free */
		min >>= 1;

		if (free_pages <= min)
			return 0;
	}
	return 1;
}

综上, 如果满足资源需求，则调用 buffered_rmqueue 函数分配资源：

/**
 * 返回第一个被分配的页框的页描述符。如果内存管理区没有所请求大小的一组连续页框，则返回NULL。
 * 在指定的内存管理区中分配页框。它使用每CPU页框高速缓存来处理单一页框请求。
 * zone:内存管理区描述符的地址。
 * order：请求分配的内存大小的对数,0表示分配一个页框。
 * gfp_flags:分配标志，如果gfp_flags中的__GFP_COLD标志被置位，那么页框应当从冷高速缓存中获取，否则应当从热高速缓存中获取（只对单一页框请求有意义。）
 */
static struct page *
buffered_rmqueue(struct zone *zone, int order, int gfp_flags)
{
	unsigned long flags;
	struct page *page = NULL;
	int cold = !!(gfp_flags & __GFP_COLD);

	/**
	 * 如果order!=0，则每CPU页框高速缓存就不能被使用。
	 * 因为高速缓存仅限于单页分配，这是固有的设计，就是为了加速单页请求分配的效率。
	 */
	if (order == 0) {
		struct per_cpu_pages *pcp;

		/**
		 * 检查由__GFP_COLD标志所标识的内存管理区本地CPU高速缓存是否需要被补充。
		 * 其count字段小于或者等于low
		 */
		pcp = &zone->pageset[get_cpu()].pcp[cold];
		local_irq_save(flags);
		/**
		 * 当前缓存中的页框数低于low，需要从伙伴系统中补充页框。
		 * 调用rmqueue_bulk函数从伙伴系统中分配batch个单一页框
		 * rmqueue_bulk反复调用__rmqueue，直到缓存的页框达到low。
		 */
		if (pcp->count <= pcp->low)
			pcp->count += rmqueue_bulk(zone, 0,
						pcp->batch, &pcp->list);
		/**
		 * 如果count为正，函数从高速缓存链表中获得一个页框。
		 * count减1
		 */
		if (pcp->count) {
			page = list_entry(pcp->list.next, struct page, lru);
			list_del(&page->lru);
			pcp->count--;
		}
		local_irq_restore(flags);
		/**
		 * 没有和get_cpu配对使用呢？
		 * 这就是内核，外层一定调用了get_cpu。这种代码看起来头疼。
		 */
		put_cpu();
	}

	/**
	 * 内存请求没有得到满足，或者是因为请求跨越了几个连续页框，或者是因为被选中的页框高速缓存为空。
	 * 调用__rmqueue函数(因为已经保护了，直接调用__rmqueue即可)从伙伴系统中分配所请求的页框。
	 */
	if (page == NULL) {
		spin_lock_irqsave(&zone->lock, flags);
		page = __rmqueue(zone, order);
		spin_unlock_irqrestore(&zone->lock, flags);
	}

	/**
	 * 如果内存请求得到满足，函数就初始化（第一个）页框的页描述符
	 */
	if (page != NULL) {
		BUG_ON(bad_range(zone, page));
		/**
		 * 将第一个页清除一些标志，将private字段置0，并将页框引用计数器置1。
		 */
		mod_page_state_zone(zone, pgalloc, 1 << order);
		prep_new_page(page, order);

		/**
		 * 如果__GFP_ZERO标志被置位，则将被分配的区域填充0。
		 */
		if (gfp_flags & __GFP_ZERO)
			prep_zero_page(page, order, gfp_flags);

		if (order && (gfp_flags & __GFP_COMP))
			prep_compound_page(page, order);
	}
	return page;
}

页框回收接口:

/**
 * 首先检查page指向的页描述符。
 * 如果该页框未被保留，就把描述符的count字段减1
 * 如果count变为0,就假定从与page对应的页框开始的2^order个连续页框不再被使用。
 * 这种情况下，该函数释放页框。
 */
fastcall void __free_pages(struct page *page, unsigned int order)
{
  	/*
  	 * 如果是保留的页框或者引用计数-1不为0，则不用释放页框。
  	 * 前者是因为保留页框本来就不用释放（通过flags的PG_reserved位标识），
  	 * 后者是因为当前尚有进程引用该页框（比如经典的父子进程）
  	 */
	if (!PageReserved(page) && put_page_testzero(page)) {
		if (order == 0)
			free_hot_page(page);
		else
			__free_pages_ok(page, order);
	}
}

/**
 * 类似于__free_pages，但是它接收的参数为要释放的第一个页框的线性地址。
 */
fastcall void free_pages(unsigned long addr, unsigned int order)
{
	if (addr != 0) {
		BUG_ON(!virt_addr_valid((void *)addr));
		__free_pages(virt_to_page((void *)addr), order);
	}
}

/* 和alloc相反，此时用virt_to_page来从线性地址到page进行转换，本质上调用依然是__free_pages */

/* 衍生出的另两个order为0的特例 */

/**
 * 释放page指向的页框
 */
#define __free_page(page) __free_pages((page), 0)

/**
 * 释放线性地址addr对应的页框。
 */
#define free_page(addr) free_pages((addr),0)

页框回收细节实现:

对于单页的回收，调用了 free_hot_page :

void fastcall free_hot_page(struct page *page)
{
  	// cold为0，表示是热高速缓存
	free_hot_cold_page(page, 0);
}

/**
 * 释放单个页框到页框高速缓存。
 * page-要释放的页框描述符地址。
 * cold-释放到热高速缓存还是冷高速缓存中
 */
static void fastcall free_hot_cold_page(struct page *page, int cold)
{
	/**
	 * page_zone从page->flag中，获得page所在的内存管理区描述符。
	 */
	struct zone *zone = page_zone(page);
	struct per_cpu_pages *pcp;
	unsigned long flags;

	arch_free_page(page, 0);

	kernel_map_pages(page, 1, 0);
	inc_page_state(pgfree);
	if (PageAnon(page))
		page->mapping = NULL;
	free_pages_check(__FUNCTION__, page);
	/**
	 * 冷高速缓存还是热高速缓存??
	 */
	pcp = &zone->pageset[get_cpu()].pcp[cold];
	local_irq_save(flags);
	/**
	 * 如果缓存的页框太多，就清除一些。
	 * 调用free_pages_bulk将这些页框释放给伙伴系统。
	 * 当然，需要更新一下count计数。
	 */
	if (pcp->count >= pcp->high)
		pcp->count -= free_pages_bulk(zone, pcp->batch, &pcp->list, 0);
	/**
	 * 将释放的页框加到高速缓存链表上。并增加count字段。
	 */
	list_add(&page->lru, &pcp->list);
	pcp->count++;
	local_irq_restore(flags);
	put_cpu();
}

当 order != 0 的情况下 ， 函数调用了 __free_pages_ok

void __free_pages_ok(struct page *page, unsigned int order)
{
	LIST_HEAD(list);
	int i;

	arch_free_page(page, order);

	mod_page_state(pgfree, 1 << order);

#ifndef CONFIG_MMU
	if (order > 0)
		for (i = 1 ; i < (1 << order) ; ++i)
			__put_page(page + i);
#endif

	for (i = 0 ; i < (1 << order) ; ++i)
		free_pages_check(__FUNCTION__, page + i);
	list_add(&page->lru, &list);
	kernel_map_pages(page, 1<<order, 0);
	free_pages_bulk(page_zone(page), 1, &list, order);
}

从上面可以看出，不管是对于单页回收时，页高速缓存中页数过多，还是多页回收的情况，最终都是通过了 free_pages_bulk 函数，将这些页框释放给伙伴系统。

static int
free_pages_bulk(struct zone *zone, int count,
		struct list_head *list, unsigned int order)
{
	unsigned long flags;
	struct page *base, *page = NULL;
	int ret = 0;

	base = zone->zone_mem_map;
	spin_lock_irqsave(&zone->lock, flags);
	zone->all_unreclaimable = 0;
	zone->pages_scanned = 0;

  // 可以支持同时回收多次页框
	while (!list_empty(list) && count--) {
		page = list_entry(list->prev, struct page, lru);
		/* have to delete it as __free_pages_bulk list manipulates */
		list_del(&page->lru);
		__free_pages_bulk(page, base, zone, order);
		ret++;
	}
	spin_unlock_irqrestore(&zone->lock, flags);
	return ret;
}

---

说明 :

• 内核版本 2.6.11.2
• 处理机: i386

参考文档 :

document/深入理解linux内核中文第三版.pdf at master · saligia-eva/document · GitHub

The Linux Kernel Archives

Linux内核学习——内存管理之页框管理 r00tk1t’s blog

Linux内存管理 hustyangju的足迹 - CSDN博客