Linux 深度探险
首页 死磕 Java 优质系列 Java 技术总览 Java 面试宝典 关于我

Linux内存管理 - zoned page frame allocator - 2

转
 2024-04-02  阅读(0)
©版权
原文作者：LoyenWang 原文地址： https://www.cnblogs.com/LoyenWang/p/11666939.html

背景

  • Read the fucking source code! --By 鲁迅
  • A picture is worth a thousand words. --By 高尔基

说明：

  1. Kernel版本：4.14
  2. ARM64处理器，Contex-A53，双核
  3. 使用工具：Source Insight 3.5， Visio

1. 概述

本文将分析Buddy System。
Buddy System伙伴系统，是通过将物理内存划分为页面来进行管理的系统，支持连续的物理页面分配和释放。此外，使用与碎片相关的算法来确保最大的连续页面。

先通过一个例子大体介绍一下原理吧：
空闲的物理页框按大小分组成0~MAX_ORDER个链表，每个链表存放页框的大小为2的n次幂，其中n在0 ~ MAX_ORDER-1中取值。

假设请求分配2^8 = 256个页框块：

  1. 检查n = 8的链表，检查是否有空闲块，找到了则直接返回；
  2. 没有找到满足需求的，则查找n = 9的链表，找到512大小空闲块，拆分成两个256大小块，将其中一个256大小块返回，另一个256大小块添加到n = 8的链表中；
  3. 在n = 9的链表中没有找到合适的块，则查找n = 10的链表，找到1024大小空闲块，将其拆分成512 + 256 + 256大小的块，返回需要获取的256大小的块，将剩下的512大小块插入n = 9链表中，剩下的256大小块插入n = 8的链表中；

合并过程是上述流程的逆过程，试图将大小相等的Buddy块进行合并成单独的块，并且会迭代合并下去，尝试合并成更大的块。合并需要满足要求：

  1. 两个Buddy块大小一致；
  2. 它们的物理地址连续；
  3. 第一个Buddy块的起始地址为 (2 x N x 4K)的整数倍，其中4K为页面大小，N为Buddy块的大小；

202404022325536501.png

struct page结构中，与Buddy System相关的字段有：

  • _mapcount： 用于标记page是否处在Buddy System中，设置成-1或PAGE_BUDDY_MAPCOUNT_VALUE(-128)；
  • private： 一个2^k次幂的空闲块的第一个页描述符中，private字段存放了块的order值，也就是k值；
  • index： 存放MIGRATE类型；
  • _refcount： 用户使用计数值，没有用户使用为0，有使用的话则增加；

合并时如下图所示：

202404022325539202.png

2. Buddy页面分配

Buddy页面分配的流程如下图所示：

202404022325541793.png

从上图中可以看出，在页面进行分配的时候，有以下四个步骤：

  1. 如果申请的是order = 0的页面，直接选择从pcp中进行分配，并直接退出；
  2. order > 0时，如果分配标志中设置了ALLOC_HARDER，则从free_list[MIGRATE_HIGHATOMIC]的链表中进行页面分配，分配成功则返回；
  3. 前两个条件都不满足，则在正常的free_list[MIGRATE_*]中进行分配，分配成功则直接则返回；
  4. 如果3中分配失败了，则查找后备类型fallbacks[MIGRATE_TYPES][4]，并将查找到的页面移动到所需的MIGRATE类型中，移动成功后，重新尝试分配；

如下图：

202404022325544084.png

上述分配的过程，前3个步骤都会调用到__rmqueue_smallest，第4步调用__rmqueue_fallback，将从这两个函数来分析。

2.1 __rmqueue_smallest

__rmqueue_smallest的源代码比较简单，贴上来看看吧：

    static 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) {
    		area = &(zone->free_area[current_order]);
    		page = list_first_entry_or_null(&area->free_list[migratetype],
    							struct page, lru);
    		if (!page)
    			continue;
    		list_del(&page->lru);
    		rmv_page_order(page);
    		area->nr_free--;
    		expand(zone, page, order, current_order, area, migratetype);
    		set_pcppage_migratetype(page, migratetype);
    		return page;
    	}
    
    	return NULL;
    }

从代码中可以看出：

  1. 从申请的order大小开始查找目标MIGRATE类型链表中页表，如果没有找到，则从更大的order中查找，直到MAX_ORDER；
  2. 查找到页表之后，从对应的链表中删除掉，并调用expand函数进行处理；

expand函数的处理逻辑就跟本文概述中讲的例子一样，当在大的order链表中申请到了内存后，剩余部分会插入到其他的order链表中，来一张图就清晰了：

202404022325546455.png

2.2 __rmqueue_fallback

当上述过程没有分配到内存时，便会开始从后备迁移类型中进行分配。
其中，定义了一个全局的二维fallbacks的数组，并根据该数组进行查找，代码如下：

    /*
     * This array describes the order lists are fallen back to when
     * the free lists for the desirable migrate type are depleted
     */
    static int fallbacks[MIGRATE_TYPES][4] = {
    	[MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_TYPES },
    	[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_TYPES },
    	[MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES },
    #ifdef CONFIG_CMA
    	[MIGRATE_CMA]         = { MIGRATE_TYPES }, /* Never used */
    #endif
    #ifdef CONFIG_MEMORY_ISOLATION
    	[MIGRATE_ISOLATE]     = { MIGRATE_TYPES }, /* Never used */
    #endif
    };

202404022325548756.png

__rmqueue_fallback完成的主要工作就是从后备fallbacks中找到一个迁移类型页面块，将其移动到目标类型中，并重新进行分配。
下图将示例整个流程：

202404022325551167.png

3. Buddy页面释放

页面释放是申请的逆过程，相对来说要简单不少，先看一下函数调用图吧：

202404022325553598.png

当order = 0时，会使用Per-CPU Page Frame来释放，其中：

  • MIGRATE_UNMOVABLE, MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE三个按原来的类型释放；

  • MIGRATE_CMA, MIGRATE_HIGHATOMIC类型释放到MIGRATE_UNMOVABLE类型中；

  • MIGRATE_ISOLATE类型释放到Buddy系统中；
    此外，在PCP释放的过程中，发生溢出时，会调用free_pcppages_bulk()来返回给Buddy系统。来一张图就清晰了：

    202404022325556069.png

在整个释放过程中，核心函数为__free_one_page，该函数的核心逻辑部分如下所示：

    continue_merging:
    	while (order < max_order - 1) {
    		buddy_pfn = __find_buddy_pfn(pfn, order);
    		buddy = page + (buddy_pfn - pfn);
    
    		if (!pfn_valid_within(buddy_pfn))
    			goto done_merging;
    		if (!page_is_buddy(page, buddy, order))
    			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 {
    			list_del(&buddy->lru);
    			zone->free_area[order].nr_free--;
    			rmv_page_order(buddy);
    		}
    		combined_pfn = buddy_pfn & pfn;
    		page = page + (combined_pfn - pfn);
    		pfn = combined_pfn;
    		order++;
    	}
  • __find_buddy_pfn： 根据释放页面的pfn计算对应的buddy_pfn，比如pfn = 0x1000, order = 3，则buddy_pfn = 0x1008，pfn = 0x1008, order = 3，则buddy_pfn = 0x1000；
  • page_is_buddy：将page和buddy进行配对处理，判断是否能配对；
  • 进行combine之后，再将pfn指向合并后的开始位置，继续往上一阶进行合并处理；

按照惯例，再来张图片吧：

2024040223255586510.png

不得不说，还有很多细节没有去扣，一旦沉沦，将难以自拔，待续吧。

2024040223255607211.png

Java 面试宝典是大明哥全力打造的 Java 精品面试题，它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题，而是一套完整的 Java 知识体系，一套你 Java 知识点的扫盲贴。

它的内容包括：

  • 大厂真题：Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
  • 原创内容：Java 面试宝典内容全部都是大明哥原创，内容全面且通俗易懂，回答部分可以直接作为面试回答内容。
  • 持续更新：一次购买，永久有效。大明哥会持续更新 3+ 年，累计更新 1000+，宝典会不断迭代更新，保证最新、最全面。
  • 覆盖全面：本宝典累计更新 1000+，从 Java 入门到 Java 架构的高频面试题，实现 360° 全覆盖。
  • 不止面试：内容包含面试题解析、内容详解、知识扩展，它不仅仅只是一份面试题，更是一套完整的 Java 知识体系。
  • 宝典详情：https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
  • 宝典总览：https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
  • 宝典进展：https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw

目前 Java 面试宝典累计更新 400+ 道，总字数 42w+。大明哥还在持续更新中，下图是大明哥在 2024-12 月份的更新情况：

想了解详情的小伙伴，扫描下面二维码加大明哥微信【daming091】咨询

同时，大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ，回复【面试题】 即可免费领取。

阅读全文
文章标签： LinuxLinux 核心原理