Linux深入理解内存管理25

Linux深入理解内存管理25（基于Linux6.6）---伙伴系统页面释放介绍

一、概述

1. 释放页面

当进程或内核模块不再使用某个内存页面时，需要通过伙伴系统释放该页面。释放的过程包括以下几个步骤：

1. 标记页面为可用：释放的页面会被标记为“空闲”，并且加入到对应大小的空闲链表中。

2. 寻找伙伴：系统会检查释放的页面是否有“伙伴”页面。伙伴系统的核心思想是将相邻的、大小相同的空闲页面称为“伙伴”，它们的物理地址相隔一定距离。

2. 伙伴的概念

在伙伴系统中，内存是按大小为 2 的幂次方进行分配和管理的，内存块的大小分别是 4KB、8KB、16KB 等。每个内存块都有一个伙伴，它们是同一个大小的内存块，且它们的物理地址是相邻的。

例如：

• 一个 8KB 内存块的伙伴就是与它在物理内存中紧邻的 8KB 内存块。
• 两个 8KB 空闲块如果相邻，它们就形成了一个 16KB 的空闲块。

3. 释放后的合并过程

释放页面时，如果它的伙伴也处于空闲状态，系统就会执行合并操作，将两个相邻的空闲块合并成一个更大的空闲块，放回空闲链表中，合并后的内存块大小是原来块大小的两倍。例如：

• 如果释放的是一个 4KB 的页面，且它的伙伴（相邻的 4KB 页面）也是空闲的，那么这两个 4KB 的页面就会合并成一个 8KB 的块。
• 如果合并后的 8KB 块仍然有伙伴，并且它也为空闲的，则继续进行合并，直到没有伙伴或者无法再合并为止。

4. 合并操作的步骤

释放一个内存块后，系统会依次执行以下检查和操作：

1. 检查伙伴是否空闲：首先，内核会检查释放页面的伙伴是否也为空闲状态。如果是，说明它们可以合并为一个更大的块。

2. 合并两个空闲块：如果伙伴为空闲，则将两个空闲块合并成一个更大的块。合并后的块会从当前级别的空闲链表中删除，并插入到更大块级别的空闲链表中。

3. 继续合并：如果合并后的新块仍然有伙伴，且它们也是空闲的，则继续进行合并操作。这个过程会一直进行，直到不能再合并为止。

4. 更新空闲链表：每次合并后，空闲链表会被更新，将合并后的块放回到空闲链表中。

5. 合并操作的终止条件

合并操作会一直进行，直到满足以下任一条件为止：

• 没有更多的伙伴：当两个相邻的空闲块没有伙伴（即它们不再是相邻的块），合并操作终止。
• 达到最大块大小：当内存块已经是系统所支持的最大块大小时，也不能继续合并。

6. 释放过程中可能出现的情况

• 无伙伴可合并：如果释放的页面没有伙伴或其伙伴已经被分配出去，那么它就无法进行合并操作。此时，该页面会单独处于空闲状态，并且该块大小会保留原状。

• 空闲链表的维护：每个大小的空闲块都有对应的空闲链表。在释放过程中，空闲链表的维护非常重要，因为它决定了内存块能否合并，内存的碎片化程度等。

7.free_pages

对于内存释放函数也可以归纳到一个主要的函数(__free_pages)，只是用不同的参数调用而已，前者是通过page，后者是通过虚拟地址addr，其定义如下

extern void __free_pages(struct page *page, unsigned int order);
extern void free_pages(unsigned long addr, unsigned int order);

对于free_pages和__free_pages之间的关系，首先需要将虚拟地址转换成指向struct page的指针：

mm/page_alloc.c 

void free_pages(unsigned long addr, unsigned int order)
{
	if (addr != 0) {
		VM_BUG_ON(!virt_addr_valid((void *)addr));
		__free_pages(virt_to_page((void *)addr), order);
	}
}

EXPORT_SYMBOL(free_pages);

对于__free_pages是一个基础函数，用于实现内核API中所有涉及到内存释放的接口函数，其代码流程如下：

mm/page_alloc.c 

void __free_pages(struct page *page, unsigned int order)
{
	/* get PageHead before we drop reference */
	int head = PageHead(page);

	if (put_page_testzero(page))
		free_the_page(page, order);
	else if (!head)
		while (order-- > 0)
			free_the_page(page + (1 << order), order);
}
EXPORT_SYMBOL(__free_pages);

• 首先，调用put_page_testzero来查看该页是否还有其他引用（struct page结构中的_count），如果没有被引用，就走到对应的页面释放流程中，如果还被引用，就啥也不做
• 由申请页面的时候，会区分是申请的单页还是多页，那么释放的时候，就也做同样的处理。会判断所需释放的内存是单页还是较大的内存块。
• 如果释放的是单页，则不还给伙伴系统，还是放回per-cpu缓存中。

二、free_the_page流程

2.1、冷页与热页的定义

1. 热页（Hot Pages）：指的是当前或者近期内被频繁访问的内存页面。这些页面通常包含正在运行的程序或操作的关键数据，可能被多个线程或进程频繁使用。

2. 冷页（Cold Pages）：指的是长时间未被访问的内存页面。冷页一般对应那些不再频繁使用的数据或者程序代码，通常属于系统中不活跃的部分。

2.2、冷页与热页的释放策略

在内存管理中，对待冷页和热页的释放策略通常不同。以下是针对两类页面释放的基本概述：

1. 热页的释放

热页通常被认为是系统中重要的内存区域，需要尽量保持在物理内存中，以保证系统的性能。释放热页的情况较少，因为热页代表着正在积极使用的内存区域。

• 减少热页的释放：当内存不足时，操作系统尽量避免释放热页，而是保留它们在内存中。如果热页必须被换出（例如交换到磁盘），操作系统通常会尝试将其存放到快速的交换设备中（如 SSD），以减少访问延迟。

• 使用缓存策略：热页往往会被操作系统的内存管理机制（如页面替换算法）优先保留。例如，使用 LRU（Least Recently Used） 算法时，最近被访问的页面更有可能被保留在内存中，避免被换出。

• 交换与优先级：在系统内存紧张时，热页可能会被移动到交换区或压缩内存中，但这种情况通常是最后的选择。操作系统可以根据页面的访问频率和使用模式动态调整热页的存储位置。

2. 冷页的释放

冷页的释放是内存管理中更常见的操作。因为冷页不再频繁访问，它们对系统的性能影响较小，可以被释放或换出到磁盘，从而腾出内存给其他需要的热页。

• 换出到磁盘：当系统内存紧张时，操作系统会选择将冷页换出到交换空间（Swap Space）或交换文件中。这样，冷页就不占用主内存，从而为活跃的页面腾出空间。

• 页面回收：对于冷页，操作系统通常会根据一系列策略（如 页面置换算法，如 LRU、CLOCK 等）来决定是否换出冷页。在内存资源紧张时，冷页比热页更有可能被回收和清除。

• 懒惰回收：冷页的回收通常是延迟的，系统可能并不会立即释放它们，而是根据内存压力逐步处理这些页面。对于一些长期未访问的冷页，系统可能会在下次访问之前主动将它们清除或移动到外部存储。

3. 冷页与热页的释放比较

2.3、冷页与热页的回收机制

回收热页和冷页的机制可以通过以下几种方式来进行优化：

1. 内存页替换算法（Page Replacement Algorithm）：

   • LRU（Least Recently Used）：LRU 算法会优先回收最近没有被访问的冷页。这对于冷页回收非常有效，因为它能确保活跃的热页被尽可能保留。
   • CLOCK 算法：CLOCK 算法是一种近似的 LRU 算法，它使用环形结构和“访问位”来追踪页面的访问情况。对于冷页，它可以高效地决定是否换出这些页面。

2. 内存压缩（Memory Compression）：

   • 操作系统也可以通过内存压缩技术来处理冷页，在不完全换出到磁盘的情况下，压缩冷页以节省内存空间。这在某些系统中被称为 zswap 或 zram，能够有效减少对磁盘的频繁访问。

3. 内存分层管理（Memory Tiering）：

   • 在现代硬件中，操作系统可能会支持内存分层管理，将热页存储在高性能的内存区域（如 DRAM），而将冷页移动到较慢的存储区域（如 SSD 或硬盘）中。这种方式可以优化内存使用和性能。

 mm/page_alloc.c 

static inline void free_the_page(struct page *page, unsigned int order)
{
	if (pcp_allowed_order(order))		/* Via pcp? */
		free_unref_page(page, order);
	else
		__free_pages_ok(page, order, FPI_NONE);
}

/*
 * Free a pcp page
 */
void free_unref_page(struct page *page, unsigned int order)
{
	unsigned long flags;
	unsigned long __maybe_unused UP_flags;
	struct per_cpu_pages *pcp;
	struct zone *zone;
	unsigned long pfn = page_to_pfn(page);
	int migratetype;

	if (!free_unref_page_prepare(page, pfn, order))
		return;

	/*
	 * We only track unmovable, reclaimable and movable on pcp lists.
	 * Place ISOLATE pages on the isolated list because they are being
	 * offlined but treat HIGHATOMIC as movable pages so we can get those
	 * areas back if necessary. Otherwise, we may have to free
	 * excessively into the page allocator
	 */
	migratetype = get_pcppage_migratetype(page);
	if (unlikely(migratetype >= MIGRATE_PCPTYPES)) {
		if (unlikely(is_migrate_isolate(migratetype))) {
			free_one_page(page_zone(page), page, pfn, order, migratetype, FPI_NONE);
			return;
		}
		migratetype = MIGRATE_MOVABLE;
	}

	zone = page_zone(page);
	pcp_trylock_prepare(UP_flags);
	pcp = pcp_spin_trylock_irqsave(zone->per_cpu_pageset, flags);
	if (pcp) {
		free_unref_page_commit(zone, pcp, page, migratetype, order);
		pcp_spin_unlock_irqrestore(pcp, flags);
	} else {
		free_one_page(zone, page, pfn, order, migratetype, FPI_NONE);
	}
	pcp_trylock_finish(UP_flags);
}

对于冷页和热页，主要表现是当一个页被释放时，默认设置为热页的话，因为该页可能有些地址的数据还是处于映射到CPU cache，当该CPU上有进程申请单个页框时，优先把这些热页分配出去，这样能提高cache的命中率，提高效率，则软件上的实现方式也比较简单，热页，则直接加入到CPU页框高速缓存链表的链表头，冷页则直接加入到链表尾。

三、__free_pages_ok流程

再看看连续页框的释放，连续页框释放主要是__free_pages_ok()函数。

mm/page_alloc.c

static void __free_pages_ok(struct page *page, unsigned int order,
			    fpi_t fpi_flags)
{
	unsigned long flags;
	int migratetype;
	unsigned long pfn = page_to_pfn(page);
	struct zone *zone = page_zone(page);

	if (!free_pages_prepare(page, order, true, fpi_flags)) //释放前pcp的准备工作，检查释放满足释放条件
		return;

	migratetype = get_pfnblock_migratetype(page, pfn);//获取页框所在pageblock的页框类型

	spin_lock_irqsave(&zone->lock, flags);
	if (unlikely(has_isolate_pageblock(zone) ||
		is_migrate_isolate(migratetype))) {
		migratetype = get_pfnblock_migratetype(page, pfn);
	}
	__free_one_page(page, pfn, zone, order, migratetype, fpi_flags); //释放函数
	spin_unlock_irqrestore(&zone->lock, flags);

	__count_vm_events(PGFREE, 1 << order);
}

对于该接口无论是释放单页还是连续页，在释放时，会获取该页所载的pageblock的类型，然后把此页设置成pageblock一致的类型，因为有一种情况，比如一个pageblock为MIGRATE_MOVABLE类型，并且有部分页已经被使用(这些正在被使用的页都为MIGRATE_MOVABLE)，然后MIGRATE_RECLAIMABLE类型的页不足，需要从MIGRATE_MOVABLE这里获取这个pageblock到MIGRATE_RECLAIMABLE类型中，这个pageblock的类型就被修改成了MIGRATE_RECLAIMABLE，这样就造成了正在使用的页的类型会与pageblock的类型不一致。最后调用free_one_page函数，其定义如下：
mm/page_alloc.c

static void free_one_page(struct zone *zone,
				struct page *page, unsigned long pfn,
				unsigned int order,
				int migratetype, fpi_t fpi_flags)
{
	unsigned long flags;

	spin_lock_irqsave(&zone->lock, flags);
	if (unlikely(has_isolate_pageblock(zone) ||
		is_migrate_isolate(migratetype))) {
		migratetype = get_pfnblock_migratetype(page, pfn);
	}
	__free_one_page(page, pfn, zone, order, migratetype, fpi_flags);
//释放page开始的order次方个页框到伙伴系统，这些页框的类型时migratetype
	spin_unlock_irqrestore(&zone->lock, flags);
}

整个释放过程的核心函数使__free_one_page，依据申请的算法，那么释放就涉及到对页面能够进行合并的。相关的内存区被添加到伙伴系统中适当的free_area列表中，在释放时，该函数将其合并为一个连续的内存区，放置到高一阶的free_are列表中。如果还能合并一个进一步的伙伴对，那么也进行合并，转移到更高阶的列表中。该过程会一致重复下去，直至所有可能的伙伴对都已经合并，并将改变尽可能向上传播。
mm/page_alloc.c

static inline void __free_one_page(struct page *page,
		unsigned long pfn,
		struct zone *zone, unsigned int order,
		int migratetype, fpi_t fpi_flags)
{
	struct capture_control *capc = task_capc(zone);
	unsigned long buddy_pfn = 0;
	unsigned long combined_pfn;
	struct page *buddy;
	bool to_tail;

	VM_BUG_ON(!zone_is_initialized(zone));
	VM_BUG_ON_PAGE(page->flags & PAGE_FLAGS_CHECK_AT_PREP, page);

	VM_BUG_ON(migratetype == -1);
	if (likely(!is_migrate_isolate(migratetype)))
		__mod_zone_freepage_state(zone, 1 << order, migratetype);

	VM_BUG_ON_PAGE(pfn & ((1 << order) - 1), page);
	VM_BUG_ON_PAGE(bad_range(zone, page), page);

	while (order < MAX_ORDER - 1) {
		if (compaction_capture(capc, page, order, migratetype)) {
			__mod_zone_freepage_state(zone, -(1 << order),
								migratetype);
			return;
		}

		buddy = find_buddy_page_pfn(page, pfn, order, &buddy_pfn);//找到与当前页属于同一个阶的伙伴页面索引
		if (!buddy)
			goto done_merging;

		if (unlikely(order >= pageblock_order)) {
			/*
			 * We want to prevent merge between freepages on pageblock
			 * without fallbacks and normal pageblock. Without this,
			 * pageblock isolation could cause incorrect freepage or CMA
			 * accounting or HIGHATOMIC accounting.
			 */
			int buddy_mt = get_pageblock_migratetype(buddy);

			if (migratetype != buddy_mt
					&& (!migratetype_is_mergeable(migratetype) ||
						!migratetype_is_mergeable(buddy_mt)))
				goto done_merging;
		}

		/*
		 * Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page,
		 * merge with it and move up one order.
		 */
		if (page_is_guard(buddy))
			clear_page_guard(zone, buddy, order, migratetype);
		else
			del_page_from_free_list(buddy, zone, order);
		combined_pfn = buddy_pfn & pfn;
		page = page + (combined_pfn - pfn);
		pfn = combined_pfn;
		order++;
	}

done_merging:
	set_buddy_order(page, order);

	if (fpi_flags & FPI_TO_TAIL)
		to_tail = true;
	else if (is_shuffle_order(order))
		to_tail = shuffle_pick_tail();
	else
		to_tail = buddy_merge_likely(pfn, buddy_pfn, page, order);

	if (to_tail)
		add_to_free_list_tail(page, zone, order, migratetype);
	else
		add_to_free_list(page, zone, order, migratetype);

	/* Notify page reporting subsystem of freed page */
	if (!(fpi_flags & FPI_SKIP_REPORT_NOTIFY))
		page_reporting_notify_free(order);
}

但内核如何知道一个伙伴对的两个部分都位于空闲页的列表中呢？为将内存块放回伙伴系统，内核必须计算潜在的伙伴地址，以及在有可能合并的情况下合并后内存块的索引。内核提供辅助函数用于计算。

mm/internal.h 

/*
 * Find the buddy of @page and validate it.
 * @page: The input page
 * @pfn: The pfn of the page, it saves a call to page_to_pfn() when the
 *       function is used in the performance-critical __free_one_page().
 * @order: The order of the page
 * @buddy_pfn: The output pointer to the buddy pfn, it also saves a call to
 *             page_to_pfn().
 *
 * The found buddy can be a non PageBuddy, out of @page's zone, or its order is
 * not the same as @page. The validation is necessary before use it.
 *
 * Return: the found buddy page or NULL if not found.
 */
static inline struct page *find_buddy_page_pfn(struct page *page,
			unsigned long pfn, unsigned int order, unsigned long *buddy_pfn)
{
	unsigned long __buddy_pfn = __find_buddy_pfn(pfn, order);
	struct page *buddy;

	buddy = page + (__buddy_pfn - pfn);
	if (buddy_pfn)
		*buddy_pfn = __buddy_pfn;

	if (page_is_buddy(page, buddy, order))
		return buddy;
	return NULL;
}

对于__free_one_page试图释放一个order的一个内存块，有可能不只是当前内存块与能够与其合并的伙伴直接合并，而且高阶的伙伴也可以合并，因此内核需要找到可能的最大分配阶。假设释放一个0阶内存块，即一页，该页的索引值为10，假设页10是合并两个3阶伙伴最后形成一个4阶的内存块，计算如下图所示：

第一遍寻找到页10的伙伴页11，由于需要的不是伙伴的页号，而是指向对应page的实例指针，buddy_index-page_idx就派上用场了，该值表示当前页与伙伴系统的差值，page指针加上该值，即可得到伙伴page的实例。

然后通过page_is_buddy需要改指针来检查伙伴系统是否是空闲，如果恰好是空闲，那么久可以合并这两个伙伴。这时候就需要将页11从伙伴系统中移除，重新合并形成一个更大的内存块，而rmv_page_order负责清楚PG_buddy标志和private数据。然后下一遍循环工作类似，但这一次order=1，也就是说，内核试图合并两个2页的伙伴，得到一个4页的内存块，其合并图如下图所示：

四、总结

在伙伴系统中，内存释放过程是基于块的合并（即“伙伴合并”）机制的，具体来说，释放内存的过程包括以下几个步骤：

1. 标记页面为空闲

• 当一个内存块被释放时，操作系统首先将该块标记为空闲状态。这是最基础的操作，表示该块现在可以被重新分配给其他请求。

2. 检查伙伴块是否为空闲

• 每个内存块都有一个伙伴块。一个块的伙伴是大小相同且地址相邻的另一块内存。释放后，系统会检查该块的伙伴块是否也为空闲。如果伙伴块为空闲状态，系统将尝试将这两个块合并为一个更大的块。

3. 合并伙伴块

• 如果块的伙伴也为空闲状态，操作系统会将这两个块合并，形成一个更大的空闲块。这个合并操作通常会递归进行，即合并后新的大块仍然需要检查它是否有空闲的伙伴。
• 合并后的块的大小是原来块的两倍。例如，如果一个 4KB 的块与另一个 4KB 的块合并，那么新形成的块将是 8KB。

合并过程会一直进行，直到没有可合并的伙伴，或者合并后的块大小已经达到系统内存管理的最大块大小。

4. 处理合并后的块

• 如果合并后的块大小达到了一个系统可接受的大小（即最大内存块大小），那么就不再继续合并，直接返回空闲状态。
• 如果合并后的块仍然有更大的伙伴可以合并，则继续进行合并操作，直到无法进一步合并。

伙伴系统的释放过程总结：

1. 释放内存块：将该内存块标记为“空闲”。
2. 检查伙伴块：检查该内存块的伙伴是否为空闲。
3. 合并空闲伙伴：如果伙伴为空闲，将该块与伙伴合并，形成一个更大的内存块。
4. 递归合并：如果新的更大的块还具有空闲的伙伴，继续进行合并。
5. 返回空闲块：最终返回一个空闲的大块，等待后续的内存分配。