共计 3632 个字符,预计需要花费 10 分钟才能阅读完成。
导读 | 内核内存管理比较复杂,主要包含了 Buddy 算法,vmalloc 管理,slab 算法,kmapper 及与初始化阶段物理内存管理相关的两个模块 memblock 和 bootmem。除了上述模块外,还有内存迁移,水线检测,kmemleak,内存信息统计,PCP 等辅助内容。在本文中,我将重点介绍 Buddy 算法(又称为伙伴算法),该算法是以页为单位进行管理的。 |
目前,内核中的 Buddy 算法采用下图的方式管理内存。我把 Buddy 算法分为如下图所示的三部分,在区域一中,核心的数据结构是 struct zone;在区域二中核心的数据结构是 struct free_area free_area[MAX_ORDER];在区域三中,page 链表是核心内容。接下来,我将详细介绍这三个板块,并通过分配函数来说明 Buddy 的工作细节。
通常用 zone 代表不同的内存管理区,即把内存划分成不同的组,每个组就是一个 zone。
在内核中,每个 zone 通过结构体 struct zone 来表示,其结构体中主要成员如下:
struct zone {unsigned long watermark[NR_WMARK];
unsigned long zone_start_pfn;
unsigned long managed_pages;
unsigned long spanned_pages;
unsigned long present_pages;
struct free_area free_area[MAX_ORDER]
;
const char *name;
struct pglist_data *zone_pgdat;
}
标识内存水线的成员 unsigned long watermark[NR_WMARK],其中 NR_WMARK 定义如下:
enum zone_watermarks {
WMARK_MIN,
WMARK_LOW,
WMARK_HIGH,
NR_WMARK
};
从上面定义可知,每个 zone 存在三个水线,若当前 zone 中空闲页高于 WMARK_HIGH,则当前 zone 区的空闲内存较多;若空闲页低于 WMARK_LOW,则交换守护进程开始将内存交换到磁盘上;若空闲页低于 WMARK_MIN,则内存回收系统还需要大量回收内存。在使用 Buddy 进行内存申请时,会进行水线判断,从而进行相应的操作;
伙伴系统管理相关的成员
unsigned long zone_start_pfn;
unsigned long managed_pages;
unsigned long spanned_pages;
unsigned long present_pages;
struct free_area free_area[MAX_ORDER]
前四个是相应 zone 区对应的页号信息,free_area 是伙伴算法中的关键成员,也是区域一和区域二衔接的关键成员,每个 zone 区会划分为 MAX_ORDER 个组,数组 free_area 中的每个成员就代表一个组。
成员 const char *name 指明了对应 zone 区的名称,通常情况下为 dma,Normal 或 highmem,其中 highmem 不会出现在 64 位的系统中;下面是典型的 32 位系统中的 zone 划分方式:
ZONE_DMA(0~16M):DMA 内存分配区;
ZONE_NORMAL(16MB~896MB):普通映射的内存区域;
ZONE_HIGHMEM(896MB~):高端内存区域,其中的页不能永久映射到内核地址空间;内核一般不使用,如果要使用,通过 kmap 做动态映射;
指向 zone 区对应 node 的指针成员 struct pglist_data *zone_pgdat,node 是内存管理中的一个重要成员。对于 UMA 架构,仅有一个 node,所有的 zone 均属于同一个 node,但对于 NUMA 架
构,会有多个不同的 node,每个 node 又划分为不同的 zone,所有 zone 区也是通过 struct pglist_data 组织在一起的。
在内存管理和分配过程中,有一个重要参数 order,当我们采用 kmalloc 申请大内存时,最后会调用函数__alloc_pages_nodemask 来进行内存申请。该函数需要一个参数 order,当 order = 0 时,表示要申请的内存大小是 1(20)个页面;当 order = 1 时,表示要申请的内存大小是 2(21)个页面。
在 Buddy 算法中,把内存按照 2 的幂次方 (即 2order,order 的范围从 0 到 MAX_ORDER) 划分成不同的组,每个组分别用对应的 free_area[order]表示,例如 free_area[0]对应的就是由内存块大小为 20 个页块组成的组,free_area[1]对应的就是由内存块大小为 21 个页块组成的组,而结构体 struct zone 正是通过成员 free_area 把图 1 中的区域一和区域二串联在一起。
结构体 struct free_area 定义如下(不同平台或者不同内核会有差异,但核心思想相同):
struct free_area {struct list_head free_list[MIGRATE_TYPES];
unsigned long nr_free;
};
从该结构可以看出,每一个 free_area 又根据 MIGRATE_TYPES 划分为不同的组,每组分别通过链表 free_list 把同一类页块串联在一起,这样 free_list 就把图 1 中的区域二和区域三串联在一起了,从而间接的把区域一和区域三关联在一起了。
结构体 struct page 比较复杂,其中有一个成员 struct list_head lru,通过该成员把图 1 中区域三中的页块同区域二中对应的 free_list 链接在一起。
在此,我将通过一个示例来简要地展示 Buddy 内存分配的核心思想。当通过 Buddy 分配一个物理页 (即 order = 0) 时,会从对应 zone 区中 free_area[0]管理的区域分配一个页面(暂时先不考虑 PCP 的情况),并将该页面从 free_area[0] 链表中移除;当 free_area[0] 上没有可用的物理页时,Buddy 会在 free_area[1]上查找,若存在可用的物理页,则将该页块从 free_area[1] 的链表中移除,同时把该页块拆分成两块,其中一块插入到 free_area[0]中,另一块传递给内存请求者;倘若 free_area[1]上也没有可用页,则会继续向上查找。
下图 2 所示是没有对应 oder = 0 的页块情况,因此把 order = 1 中的一个页块进行拆分,一半返回给 order = 1 的链表,一半返回给请求者。假如 order = 1 中没有需要的页块,在内存分配过程中会继续从 order = 3 中进行查找,直到找到页块或者遍历完所有 order。
实际上,在整个内存分配过程中,会伴随很多特殊情况处理。Buddy 算法在进行内存分配时,会根据水线设置,来进行内存回收或者唤醒内核线程 kswapd,或者是采用 CPU 的冷热页面队列进行内存分配,或者是进行页面移动等。假如已经尝试页面移动,kswapd 已经唤出了一些页面,同时也进行了内存回收,依然没有可分配的内存,此时就会触发 out_of_memory。总之,这些特殊情况的处理方式均离不开图 1 所示的 Buddy 框架。
下图是我根据我本地的代码整理的采用 kmalloc 申请大内存时的调用过程(使用 kmalloc 申请小内存时不通过 Buddy),其中最关键的内存分配函数是 prepare_alloc_pages,get_page_from_freelist,rmqueue 和__alloc_pages_slowpath。感兴趣的朋友可以结合图 1 所示的框架查看这几个函数的具体实现。
当向系统释放一个物理页的时候,会通过 struct page 来推导出该 page 对应的 zone 区 (比如该 page 属于 NORMAL 区) 和对应的 page 类型,紧接着将根据对应的 order 进行页的合并 (即图 1 中区域三的部分进行合并),最后将合并后的块插入到新的 order 中去,这个合并过程一直持续下去,直到不能合并或者已经合并到最大的 order 处。例如当释放的物理页得到其属于 NORMAL 区的 free_area[0],此时 free_area[0] 中存在页面可以和释放的页面合并,从而把合并后的添加到 free_area[1]中,这个合并操作会一直持续下去,直到合并完为止。这个过程实际上就是图 2 的反过程。
内存的管理比较复杂,本文主要介绍了 Buddy 的核心思想,但这仅仅是内存管理的冰山一角,却是比较基础且核心的内容,因此了解 Buddy 整体架构是非常有必要的。
作者介绍
赵青窕,51CTO 社区编辑,从事多年驱动开发。研究兴趣包含安全 OS 和网络安全领域,发表过网络相关专利。
![post-qrcode](https://www.xgss.net/wp-content/uploads/2023/07/二维码-微信公众号256x256.jpg)