伙伴系统Buddy System深度拆解与源码分析伙伴系统Buddy System是Linux物理内存管理的核心负责管理系统中所有的空闲物理页解决了连续物理内存分配的外部碎片问题是整个内存管理子系统的基石。所有的物理内存分配无论是用户态的页分配还是内核的slab分配最终都会落到伙伴系统的分配与释放接口。3.1 伙伴系统解决的核心问题内存分配最核心的两个问题内部碎片分配的内存大于实际需要的内存导致内存浪费比如需要100字节分配了4KB页剩下的4000字节无法被利用由slab分配器解决外部碎片系统中有足够的空闲内存但都是分散的小页无法分配连续的大内存块由伙伴系统解决。传统的内存分配算法比如首次适配、最佳适配都会导致严重的外部碎片系统运行一段时间后无法分配连续的大内存哪怕总空闲内存足够。伙伴系统通过分阶管理、合并空闲块的机制完美解决了外部碎片问题同时保证了分配和释放的高效性。3.2 伙伴系统的核心原理伙伴系统的核心思想非常简单分阶管理把物理内存按2的幂次划分为不同阶数的块order从0到MAX_ORDER-1默认MAX_ORDER11对应块大小为2^0~2^10个连续页4KB~4MB空闲块管理每个Zone的free_area[MAX_ORDER]数组对应每个阶数的空闲块链表相同大小的空闲块挂在同一个链表中分配逻辑当需要分配n个连续页时找到大于等于n的最小2的幂次对应的阶数如果该阶数有空闲块直接分配如果没有向上找更大的阶数把大的块拆分为两个小的伙伴块直到得到需要的大小剩下的块挂到对应阶数的链表中释放逻辑释放内存块时检查它的伙伴块是否也是空闲的如果是就把两个伙伴块合并为一个更大的块继续向上检查合并直到伙伴块不是空闲的把最终的块挂到对应阶数的链表中。什么是伙伴块两个块必须满足以下三个条件才是伙伴块才能合并两个块的大小相同都是2^order个页两个块的物理地址是连续的第一个块的起始物理地址必须是2^(order1)个页的整数倍。举个例子order0的块1页伙伴块是相邻的1页且起始地址是2页的整数倍order1的块2页伙伴块是相邻的2页起始地址是4页的整数倍以此类推。3.3 伙伴系统的核心数据结构伙伴系统的核心数据结构是struct free_area每个Zone的free_area[MAX_ORDER]数组定义在include/linux/mmzone.h中struct free_area { // 该阶数的空闲块链表 struct list_head free_list[MIGRATE_TYPES]; // 该阶数的空闲块总数 unsigned long nr_free; };核心字段解析free_list[MIGRATE_TYPES]空闲块链表按迁移类型分类每个迁移类型对应一个链表这是内核防碎片的核心优化r_free该阶数的空闲块总数统计该阶数有多少个空闲块。迁移类型MIGRATE_TYPES为了进一步减少内存碎片内核把空闲块按迁移类型分类不同类型的内存分配从对应的迁移类型链表中分配避免不可移动的页分散在内存中导致无法合并大的空闲块。核心迁移类型迁移类型核心含义适用场景MIGRATE_UNMOVABLE不可移动页物理地址固定不能移动内核分配的不可移动对象比如内核栈、slab对象MIGRATE_MOVABLE可移动页物理地址可以移动通过反向映射更新页表用户态的页、页缓存、可移动的内核对象MIGRATE_RECLAIMABLE可回收页不能移动但可以通过回收释放可回收的slab对象比如目录项缓存、inode缓存MIGRATE_HIGHATOMIC高优先级原子分配用于中断上下文等不能睡眠的场景原子内存分配MIGRATE_CMA连续内存分配用于设备驱动的大连续内存分配设备驱动、多媒体、GPUMIGRATE_ISOLATE隔离的页不能被分配用于内存热插拔、碎片整理内存热插拔、碎片整理核心设计思想不可移动的页只能从MIGRATE_UNMOVABLE类型的链表中分配可移动的页从MIGRATE_MOVABLE类型的链表中分配避免不可移动的页分散在可移动的内存中导致大的连续块被拆分无法合并从根源上减少内存碎片。3.4 伙伴系统核心流程源码解析伙伴系统的核心函数定义在mm/page_alloc.c中我们基于Linux 6.6内核拆解分配、释放、合并的核心流程。3.4.1 核心分配流程alloc_pages()伙伴系统的核心分配入口是alloc_pages()宏最终会落到__alloc_pages_nodemask()函数这是伙伴系统分配的核心函数被称为「内核内存分配的心脏」。分配流程的核心步骤alloc_pages(gfp_mask, order)↓__alloc_pages_nodemask(gfp_mask, order, nodemask)↓1. 解析分配参数gfp_mask、order、允许分配的节点/Zone↓2. 快速路径分配get_page_from_freelist()├→ 按zonelist的顺序遍历Zone检查空闲内存是否高于水位线├→ 从对应order、迁移类型的free_list中取空闲块├→ 如果块大小大于需要的order拆分块剩下的块挂到对应阶数的链表├→ 分配成功返回page结构体└→ 分配失败进入慢速路径↓3. 慢速路径分配__alloc_pages_slowpath()├→ 唤醒kswapd内核线程异步回收内存├→ 直接内存回收同步释放内存├→ 内存碎片整理合并空闲块├→ OOM Killer杀死进程释放内存└→ 所有方法都失败返回NULL分配失败核心函数深度解析1.快速路径get_page_from_freelist()这是伙伴系统最常用的分配路径无锁、无睡眠性能极高99%的内存分配都会在快速路径完成。核心逻辑遍历允许的Zone列表检查Zone的空闲内存是否高于分配要求的水位线如果满足就从对应order、迁移类型的空闲链表中取出第一个空闲块如果该阶数没有空闲块就向上找更大的阶数找到后拆分块把剩余的部分挂到低阶的链表中返回分配的页。块拆分逻辑示例需要分配order01页当前order0没有空闲块order1有空闲块就把order1的2页块拆分为两个order0的伙伴块一个分配出去另一个挂到order0的空闲链表中。2.慢速路径__alloc_pages_slowpath()只有当快速路径分配失败时才会进入慢速路径会执行内存回收、碎片整理、OOM等操作可能会阻塞睡眠。核心执行顺序先唤醒kswapd内核线程异步回收内存然后再次尝试快速路径分配如果还是失败执行直接内存回收同步回收不活跃的页再次尝试分配如果还是失败执行内存碎片整理合并空闲的块尝试分配连续的大内存如果还是失败且分配允许OOM调用OOM Killer杀死占用内存多的进程释放内存所有方法都失败后返回NULL分配失败。3.4.2 核心释放流程__free_pages()内存释放的核心入口是__free_pages()函数最终落到free_one_page()函数完成页的释放、伙伴块的检查与合并。释放流程的核心步骤__free_pages(struct page *page, unsigned int order)↓free_the_page(page, order)↓free_one_page(page_zone(page), page, pfn, order, migratetype)↓1. 检查页的合法性清除页的标志位重置引用计数↓2. 循环检查当前块的伙伴块是否空闲├→ 计算当前块的伙伴块的pfn├→ 检查伙伴块是否空闲、是否是相同阶数、相同迁移类型├→ 如果是把伙伴块从空闲链表中移除和当前块合并为更大的块├→ order加1继续向上检查合并└→ 如果伙伴块不空闲停止合并↓3. 把最终合并后的块挂到对应order、迁移类型的空闲链表中↓4. 更新Zone的空闲页数统计唤醒等待空闲内存的进程核心合并逻辑示例释放一个order0的页它的伙伴块也是空闲的就合并为order1的块如果这个order1的块的伙伴块也是空闲的继续合并为order2的块直到伙伴块不空闲把最终的块挂到对应order的链表中。3.5 伙伴系统的工程实践与避坑指南1.gfp_mask标志位的正确使用伙伴系统分配的核心参数是gfp_mask标志位决定了分配的行为、允许的睡眠、分配的Zone、迁移类型等很多内核驱动的bug都是因为gfp_mask使用错误导致的。a.高频使用的标志位与适用场景标志位核心含义适用场景GFP_KERNEL内核常规分配允许睡眠、允许IO、允许回收内核进程上下文的常规内存分配最常用GFP_ATOMIC原子分配不允许睡眠不能阻塞中断上下文、软中断、自旋锁持有期间的内存分配GFP_USER用户态内存分配允许睡眠、IO、回收为用户进程分配内存GFP_HIGHUSER从高端内存分配用于用户态内存用户态的大内存分配GFP_DMA从ZONE_DMA分配用于ISA设备DMA老旧ISA设备驱动GFP_DMA32从ZONE_DMA32分配用于32位DMA32位PCI设备驱动__GFP_NOFAIL分配不允许失败会一直重试直到成功绝对不能失败的核心分配谨慎使用__GFP_NOWARN分配失败不打印警告日志预期可能失败的分配避免日志刷屏b.避坑指南中断上下文、自旋锁持有期间绝对不能使用允许睡眠的标志位比如GFP_KERNEL必须使用GFP_ATOMIC否则会导致内核死锁、崩溃。2.内存碎片化的排查与优化系统运行时间长了之后会出现内存碎片化表现为总空闲内存很多但无法分配连续的大内存比如大页分配失败内核日志出现page allocation failure。排查方法查看伙伴系统的空闲块分布cat /proc/buddyinfo查看每个Zone、每个order的空闲块数量如果高阶的空闲块很少低阶的很多说明碎片化严重查看内存碎片化程度cat /sys/kernel/debug/extfrag/extfrag_index数值越接近1碎片化越严重。优化方案手动触发内存碎片整理echo 1 /proc/sys/vm/compact_memory开启自动碎片整理echo 1 /proc/sys/vm/compact_unevictable_allowed内核启动参数设置kernelcore和movablecore把大部分内存划分为ZONE_MOVABLE减少碎片化调整vm.extfrag_threshold参数降低碎片整理的触发阈值提前整理碎片。3.page allocation failure故障定位内核日志出现page allocation failure: order:5, mode:0x...说明伙伴系统分配连续内存失败是线上常见的内存故障。定位流程从日志中获取分配的order、modegfp_mask、失败的Zone查看/proc/buddyinfo确认对应Zone的对应order是否有空闲块查看/proc/meminfo确认系统的空闲内存、Slab占用、页缓存占用、匿名页占用查看/proc/zoneinfo确认Zone的水位线、空闲页数、低内存预留常见根因内存碎片化严重、内存水位线设置过高、内存被slab/页缓存占用、进程内存泄漏、OOM配置不合理。临时解决方案手动触发内存回收echo 3 /proc/sys/vm/drop_caches释放页缓存、目录项、inode缓存手动触发碎片整理echo 1 /proc/sys/vm/compact_memory调大vm.min_free_kbytes提升内存水位线预留更多空闲内存。4.MAX_ORDER的调优MAX_ORDER默认是11对应最大的连续块是1024页4MB如果需要分配更大的连续物理内存比如1GB大页需要调整MAX_ORDER和内核启动参数。避坑指南MAX_ORDER不能随意调大否则会导致伙伴系统的内存开销增加碎片整理难度变大除非有明确的大连续内存分配需求否则保持默认值即可。
Linux内核学习轨迹第五部：内存管理子系统-物理内存管理：伙伴系统（Buddy System）深度拆解（第三小节）
伙伴系统Buddy System深度拆解与源码分析伙伴系统Buddy System是Linux物理内存管理的核心负责管理系统中所有的空闲物理页解决了连续物理内存分配的外部碎片问题是整个内存管理子系统的基石。所有的物理内存分配无论是用户态的页分配还是内核的slab分配最终都会落到伙伴系统的分配与释放接口。3.1 伙伴系统解决的核心问题内存分配最核心的两个问题内部碎片分配的内存大于实际需要的内存导致内存浪费比如需要100字节分配了4KB页剩下的4000字节无法被利用由slab分配器解决外部碎片系统中有足够的空闲内存但都是分散的小页无法分配连续的大内存块由伙伴系统解决。传统的内存分配算法比如首次适配、最佳适配都会导致严重的外部碎片系统运行一段时间后无法分配连续的大内存哪怕总空闲内存足够。伙伴系统通过分阶管理、合并空闲块的机制完美解决了外部碎片问题同时保证了分配和释放的高效性。3.2 伙伴系统的核心原理伙伴系统的核心思想非常简单分阶管理把物理内存按2的幂次划分为不同阶数的块order从0到MAX_ORDER-1默认MAX_ORDER11对应块大小为2^0~2^10个连续页4KB~4MB空闲块管理每个Zone的free_area[MAX_ORDER]数组对应每个阶数的空闲块链表相同大小的空闲块挂在同一个链表中分配逻辑当需要分配n个连续页时找到大于等于n的最小2的幂次对应的阶数如果该阶数有空闲块直接分配如果没有向上找更大的阶数把大的块拆分为两个小的伙伴块直到得到需要的大小剩下的块挂到对应阶数的链表中释放逻辑释放内存块时检查它的伙伴块是否也是空闲的如果是就把两个伙伴块合并为一个更大的块继续向上检查合并直到伙伴块不是空闲的把最终的块挂到对应阶数的链表中。什么是伙伴块两个块必须满足以下三个条件才是伙伴块才能合并两个块的大小相同都是2^order个页两个块的物理地址是连续的第一个块的起始物理地址必须是2^(order1)个页的整数倍。举个例子order0的块1页伙伴块是相邻的1页且起始地址是2页的整数倍order1的块2页伙伴块是相邻的2页起始地址是4页的整数倍以此类推。3.3 伙伴系统的核心数据结构伙伴系统的核心数据结构是struct free_area每个Zone的free_area[MAX_ORDER]数组定义在include/linux/mmzone.h中struct free_area { // 该阶数的空闲块链表 struct list_head free_list[MIGRATE_TYPES]; // 该阶数的空闲块总数 unsigned long nr_free; };核心字段解析free_list[MIGRATE_TYPES]空闲块链表按迁移类型分类每个迁移类型对应一个链表这是内核防碎片的核心优化r_free该阶数的空闲块总数统计该阶数有多少个空闲块。迁移类型MIGRATE_TYPES为了进一步减少内存碎片内核把空闲块按迁移类型分类不同类型的内存分配从对应的迁移类型链表中分配避免不可移动的页分散在内存中导致无法合并大的空闲块。核心迁移类型迁移类型核心含义适用场景MIGRATE_UNMOVABLE不可移动页物理地址固定不能移动内核分配的不可移动对象比如内核栈、slab对象MIGRATE_MOVABLE可移动页物理地址可以移动通过反向映射更新页表用户态的页、页缓存、可移动的内核对象MIGRATE_RECLAIMABLE可回收页不能移动但可以通过回收释放可回收的slab对象比如目录项缓存、inode缓存MIGRATE_HIGHATOMIC高优先级原子分配用于中断上下文等不能睡眠的场景原子内存分配MIGRATE_CMA连续内存分配用于设备驱动的大连续内存分配设备驱动、多媒体、GPUMIGRATE_ISOLATE隔离的页不能被分配用于内存热插拔、碎片整理内存热插拔、碎片整理核心设计思想不可移动的页只能从MIGRATE_UNMOVABLE类型的链表中分配可移动的页从MIGRATE_MOVABLE类型的链表中分配避免不可移动的页分散在可移动的内存中导致大的连续块被拆分无法合并从根源上减少内存碎片。3.4 伙伴系统核心流程源码解析伙伴系统的核心函数定义在mm/page_alloc.c中我们基于Linux 6.6内核拆解分配、释放、合并的核心流程。3.4.1 核心分配流程alloc_pages()伙伴系统的核心分配入口是alloc_pages()宏最终会落到__alloc_pages_nodemask()函数这是伙伴系统分配的核心函数被称为「内核内存分配的心脏」。分配流程的核心步骤alloc_pages(gfp_mask, order)↓__alloc_pages_nodemask(gfp_mask, order, nodemask)↓1. 解析分配参数gfp_mask、order、允许分配的节点/Zone↓2. 快速路径分配get_page_from_freelist()├→ 按zonelist的顺序遍历Zone检查空闲内存是否高于水位线├→ 从对应order、迁移类型的free_list中取空闲块├→ 如果块大小大于需要的order拆分块剩下的块挂到对应阶数的链表├→ 分配成功返回page结构体└→ 分配失败进入慢速路径↓3. 慢速路径分配__alloc_pages_slowpath()├→ 唤醒kswapd内核线程异步回收内存├→ 直接内存回收同步释放内存├→ 内存碎片整理合并空闲块├→ OOM Killer杀死进程释放内存└→ 所有方法都失败返回NULL分配失败核心函数深度解析1.快速路径get_page_from_freelist()这是伙伴系统最常用的分配路径无锁、无睡眠性能极高99%的内存分配都会在快速路径完成。核心逻辑遍历允许的Zone列表检查Zone的空闲内存是否高于分配要求的水位线如果满足就从对应order、迁移类型的空闲链表中取出第一个空闲块如果该阶数没有空闲块就向上找更大的阶数找到后拆分块把剩余的部分挂到低阶的链表中返回分配的页。块拆分逻辑示例需要分配order01页当前order0没有空闲块order1有空闲块就把order1的2页块拆分为两个order0的伙伴块一个分配出去另一个挂到order0的空闲链表中。2.慢速路径__alloc_pages_slowpath()只有当快速路径分配失败时才会进入慢速路径会执行内存回收、碎片整理、OOM等操作可能会阻塞睡眠。核心执行顺序先唤醒kswapd内核线程异步回收内存然后再次尝试快速路径分配如果还是失败执行直接内存回收同步回收不活跃的页再次尝试分配如果还是失败执行内存碎片整理合并空闲的块尝试分配连续的大内存如果还是失败且分配允许OOM调用OOM Killer杀死占用内存多的进程释放内存所有方法都失败后返回NULL分配失败。3.4.2 核心释放流程__free_pages()内存释放的核心入口是__free_pages()函数最终落到free_one_page()函数完成页的释放、伙伴块的检查与合并。释放流程的核心步骤__free_pages(struct page *page, unsigned int order)↓free_the_page(page, order)↓free_one_page(page_zone(page), page, pfn, order, migratetype)↓1. 检查页的合法性清除页的标志位重置引用计数↓2. 循环检查当前块的伙伴块是否空闲├→ 计算当前块的伙伴块的pfn├→ 检查伙伴块是否空闲、是否是相同阶数、相同迁移类型├→ 如果是把伙伴块从空闲链表中移除和当前块合并为更大的块├→ order加1继续向上检查合并└→ 如果伙伴块不空闲停止合并↓3. 把最终合并后的块挂到对应order、迁移类型的空闲链表中↓4. 更新Zone的空闲页数统计唤醒等待空闲内存的进程核心合并逻辑示例释放一个order0的页它的伙伴块也是空闲的就合并为order1的块如果这个order1的块的伙伴块也是空闲的继续合并为order2的块直到伙伴块不空闲把最终的块挂到对应order的链表中。3.5 伙伴系统的工程实践与避坑指南1.gfp_mask标志位的正确使用伙伴系统分配的核心参数是gfp_mask标志位决定了分配的行为、允许的睡眠、分配的Zone、迁移类型等很多内核驱动的bug都是因为gfp_mask使用错误导致的。a.高频使用的标志位与适用场景标志位核心含义适用场景GFP_KERNEL内核常规分配允许睡眠、允许IO、允许回收内核进程上下文的常规内存分配最常用GFP_ATOMIC原子分配不允许睡眠不能阻塞中断上下文、软中断、自旋锁持有期间的内存分配GFP_USER用户态内存分配允许睡眠、IO、回收为用户进程分配内存GFP_HIGHUSER从高端内存分配用于用户态内存用户态的大内存分配GFP_DMA从ZONE_DMA分配用于ISA设备DMA老旧ISA设备驱动GFP_DMA32从ZONE_DMA32分配用于32位DMA32位PCI设备驱动__GFP_NOFAIL分配不允许失败会一直重试直到成功绝对不能失败的核心分配谨慎使用__GFP_NOWARN分配失败不打印警告日志预期可能失败的分配避免日志刷屏b.避坑指南中断上下文、自旋锁持有期间绝对不能使用允许睡眠的标志位比如GFP_KERNEL必须使用GFP_ATOMIC否则会导致内核死锁、崩溃。2.内存碎片化的排查与优化系统运行时间长了之后会出现内存碎片化表现为总空闲内存很多但无法分配连续的大内存比如大页分配失败内核日志出现page allocation failure。排查方法查看伙伴系统的空闲块分布cat /proc/buddyinfo查看每个Zone、每个order的空闲块数量如果高阶的空闲块很少低阶的很多说明碎片化严重查看内存碎片化程度cat /sys/kernel/debug/extfrag/extfrag_index数值越接近1碎片化越严重。优化方案手动触发内存碎片整理echo 1 /proc/sys/vm/compact_memory开启自动碎片整理echo 1 /proc/sys/vm/compact_unevictable_allowed内核启动参数设置kernelcore和movablecore把大部分内存划分为ZONE_MOVABLE减少碎片化调整vm.extfrag_threshold参数降低碎片整理的触发阈值提前整理碎片。3.page allocation failure故障定位内核日志出现page allocation failure: order:5, mode:0x...说明伙伴系统分配连续内存失败是线上常见的内存故障。定位流程从日志中获取分配的order、modegfp_mask、失败的Zone查看/proc/buddyinfo确认对应Zone的对应order是否有空闲块查看/proc/meminfo确认系统的空闲内存、Slab占用、页缓存占用、匿名页占用查看/proc/zoneinfo确认Zone的水位线、空闲页数、低内存预留常见根因内存碎片化严重、内存水位线设置过高、内存被slab/页缓存占用、进程内存泄漏、OOM配置不合理。临时解决方案手动触发内存回收echo 3 /proc/sys/vm/drop_caches释放页缓存、目录项、inode缓存手动触发碎片整理echo 1 /proc/sys/vm/compact_memory调大vm.min_free_kbytes提升内存水位线预留更多空闲内存。4.MAX_ORDER的调优MAX_ORDER默认是11对应最大的连续块是1024页4MB如果需要分配更大的连续物理内存比如1GB大页需要调整MAX_ORDER和内核启动参数。避坑指南MAX_ORDER不能随意调大否则会导致伙伴系统的内存开销增加碎片整理难度变大除非有明确的大连续内存分配需求否则保持默认值即可。
