Nov 21, 2023 8 min read linux内存管理

内存管理2_伙伴系统

1、背景分析

Linux内核需要有效地管理内存，以支持各种类型的应用和服务。传统的内存分配方法（如连续内存分配）存在一些不足，例如内存碎片和分配效率低下。频繁的申请和释放不同大小的连续页框必然会导致已分配的页框块分散了许多小块的空闲页框，可能会产生的问题就是：即使内存页框是充足的，但要申请一个大的页框可能也会因为没有足够的连续页框而失败。

为了避免内存碎片化而引发上述问题，通常可以有两种方法：

使用分页单元把不连续的页框映射到连续的线性空间。
使用一种适当的技术用以记录当前连续页框的情况，避免分配小组连续页框的时候对大的页框进行切割。

为了解决上述问题，Linux内核引入了伙伴系统（Buddy System）。这主要是因为内核中确实需要连续页框，并且连续页框的存在有助于保持CPU Cache中的TLB命中率。

2、伙伴系统原理

伙伴系统通过将内存分成多个大小相等的块（block），按2的幂次方规划（称为“order”），并维护不同order的空闲块链表来工作。这种方法使得内存的分配和释放更加高效，减少了内存碎片。

伙伴系统吧内存分成了11个块链表，每个链表包含1、2、4、8、16、32、64、128、256、512和1024个连续页框即2^0~10，最大的1024个页框块则是4MB的内存大小。

2.1-关键步骤

初始化：内存在系统启动时被分成块，按order组织成链表。
分配：根据需求选择合适大小的块，如无合适块，则分割更大块。
释放：释放的块返回链表，相邻空闲块合并。

3、伙伴系统在linux中的实现

3.1-`free_area`

struct free_area：定义空闲块链表。

struct free_area {
	struct list_head	free_list[MIGRATE_TYPES]; // 连续页框的具体地址
	unsigned long		nr_free; // 有多少个空闲的对应大小的页框
};

而上述结构体被定义在了zone的结构体之中，可以看到每一个内存区里都有11个free_area结构体。

#define MAX_ORDER 10

struct zone {
  ......
	/* free areas of different sizes */
	struct free_area	free_area[MAX_ORDER + 1];
  ......
}

可以看到，free_area中第K个元素，对应这个2^k大小的连续页面，如上文原理分析，最多是2¹⁰的也就是1024个连续页框。

3.2-分配函数

前一篇文章中我们分析到内存申请和释放页框过程中是存在从伙伴系统直接获取或还原的，所以直接切入到这部分代码：

/*
 * get_page_from_freelist goes through the zonelist trying to allocate
 * a page.
 */
static struct page *
get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
						const struct alloc_context *ac)
{
	......
retry:
	no_fallback = alloc_flags & ALLOC_NOFRAGMENT;
	z = ac->preferred_zoneref;
  // 遍历所有内存区域（zones），寻找满足空闲页面需求的区域。
	for_next_zone_zonelist_nodemask(zone, z, ac->highest_zoneidx,
					ac->nodemask) {
		struct page *page;
		unsigned long mark;

    // 如果当前的zone不可以用的话则直接退出当前的遍历
		if (cpusets_enabled() &&
			(alloc_flags & ALLOC_CPUSET) &&
			!__cpuset_zone_allowed(zone, gfp_mask))
				continue;
		......
    // 在NUMA架构中，尽量避免远端内存的分配，如果发现不是本地的内存就再找一次
    // 即使代价是造成内存碎片化
		if (no_fallback && nr_online_nodes > 1 &&
		    zone != ac->preferred_zoneref->zone) {
			int local_nid;

			local_nid = zone_to_nid(ac->preferred_zoneref->zone);
			if (zone_to_nid(zone) != local_nid) {
				alloc_flags &= ~ALLOC_NOFRAGMENT;
				goto retry;
			}
		}

		/* 检查水位线，避免内存耗尽了 */
		if (test_bit(ZONE_BELOW_HIGH, &zone->flags))
			goto check_alloc_wmark;

		mark = high_wmark_pages(zone);
		if (zone_watermark_fast(zone, order, mark,
					ac->highest_zoneidx, alloc_flags,
					gfp_mask))
			goto try_this_zone;
		else
			set_bit(ZONE_BELOW_HIGH, &zone->flags);

// 省略部分主要是在检查水位线失败时的其他处理逻辑
check_alloc_wmark:
	......
try_this_zone:
    /* 关键的分配函数，尝试从当前zone区域的freelist中分配page。*/
		page = rmqueue(ac->preferred_zoneref->zone, zone, order,
				gfp_mask, alloc_flags, ac->migratetype);
	......
	return NULL;
}

进一步会调用到rmqueue_buddy->__rmqueue->__rmqueue_cma_fallback->__rmqueue_smallest执行页的获取。

/*
 * Go through the free lists for the given migratetype and remove
 * the smallest available page from the freelists
 */
static __always_inline
struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
						int migratetype)
{
	unsigned int current_order;
	struct free_area *area;
	struct page *page;

	/* Find a page of the appropriate size in the preferred list */
	for (current_order = order; current_order <= MAX_ORDER; ++current_order) { // 从请求order开始遍历free_area
		area = &(zone->free_area[current_order]);
		page = get_page_from_free_area(area, migratetype); // 从当前的伙伴系统里试着拿出一个free块
		if (!page)
			continue; // 没拿到的话就再找下一个大小的free_area
		del_page_from_free_list(page, zone, current_order); // 把当前的内存组从free list删除
		expand(zone, page, order, current_order, migratetype);// 如果找到的页面大于请求的order，将其拆分为更小的块
		set_pcppage_migratetype(page, migratetype); // 设置页面的迁移类型。
		trace_mm_page_alloc_zone_locked(page, order, migratetype,
				pcp_allowed_order(order) &&
				migratetype < MIGRATE_PCPTYPES);
		return page;
	}

	return NULL;
}

而当我们在更大的页框组拆分的时候，则会把多余的页框组插到其他free_area中，并把目标的order和current_order作对比。

static inline void expand(struct zone *zone, struct page *page,
	int low, int high, int migratetype)
{
	unsigned long size = 1 << high; // 要被拆分的页大小

	while (high > low) {
		high--; // 把current_order递减到实际的需求order
		size >> = 1;
		VM_BUG_ON_PAGE(bad_range(zone, &page[size]), &page[size]); // 按照当前的size把原始大小的页框组拆分

		/*
		 * Mark as guard pages (or page), that will allow to
		 * merge back to allocator when buddy will be freed.
		 * Corresponding page table entries will not be touched,
		 * pages will stay not present in virtual address space
		 */
		if (set_page_guard(zone, &page[size], high, migratetype))
			continue;

		add_to_free_list(&page[size], zone, high, migratetype); // 把拆分出来的直接加回到新的free list中
		set_buddy_order(&page[size], high);
	}
}

3.3-释放函数

当系统调用free_page的时候，伙伴系统会尝试把当前的页面还原给大的order组，这样的操作可以有效减少内存的碎片化。

static inline void __free_one_page(struct page *page,
		unsigned long pfn,
		struct zone *zone, unsigned int order,
		int migratetype, fpi_t fpi_flags)
{
	......
	VM_BUG_ON(!zone_is_initialized(zone)); // 确保传入的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); // 检查migratetype是否为MIGRATE_ISOLATE

	VM_BUG_ON_PAGE(pfn & ((1 << order) - 1), page); // 确保传入的pfn与order匹配
	VM_BUG_ON_PAGE(bad_range(zone, page), page);

  /* 尝试寻找并合并当前页面的伙伴页面 */
	while (order < MAX_ORDER) { 
		......
		buddy = find_buddy_page_pfn(page, pfn, order, &buddy_pfn); // 查找当前页的buddy
		if (!buddy)
			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)) // 查看是否找到了当前page的伙伴系统是否是守护页
			clear_page_guard(zone, buddy, order, migratetype); // 如果伙伴页面是守卫页，这一步会清除守卫页的状态，准备它们进行合并
		else
			del_page_from_free_list(buddy, zone, order); // 不是守卫页，将伙伴页面从free list中移除，以便将其与当前页面合并。
		combined_pfn = buddy_pfn & pfn;
		page = page + (combined_pfn - pfn);
		pfn = combined_pfn;
		order++;
	}

done_merging:
	set_buddy_order(page, order); // 设置合并后的页order

  /* 函数根据fpi_flags和其他条件决定将合并后的页添加到zone的free list的头部还是尾部 */
	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);
}

这里主要执行find_buddy_page_pfn查找合适的伙伴系统页面的原因

合并内存块：

当页面被释放时，系统尝试找到它的伙伴页面，以判断是否可以将这两个页面合并成一个更大的内存块。这种合并减少了内存碎片化，提高了内存利用率。
维持伙伴系统的完整性：

伙伴系统基于成对的页面块进行工作。每次分配或释放时，都必须维护这种配对关系，以确保系统的高效和一致性。
优化内存分配：

通过合并释放的页面和其伙伴页面，伙伴系统可以为未来的大块内存分配请求提供更多的连续内存，从而提高内存分配的效率。

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); // 查找当前order对应伙伴页面的页面帧号（PFN）
	struct page *buddy;

	buddy = page + (__buddy_pfn - pfn); // 通过计算得到的PFN定位伙伴页面
	if (buddy_pfn)
		*buddy_pfn = __buddy_pfn;

	if (page_is_buddy(page, buddy, order)) // 检查是否为有效伙伴页面
		return buddy;
	return NULL;
}