从零到一手写操作系统（七、内存 5）linux buddy system）
如果追忆会荡起涟漪，那么今天的秋红落叶和晴空万里都归你
https://aeneag.xyz
微信公众号：技术乱舞
艾恩凝
手写操作系统目录
7.7）buddy system(Linux)
linux系统中，管理物理内存页面的是伙伴系统，负责分配比页更小的内存对象是slab分配器
7.7.1）表示页page
Linux 也是使用分页机制管理物理内存的，即 Linux 把物理内存分成 4KB 大小的页面进行管理。目前宏观了解linux内核中，一个 page 结构表示一个物理内存页面。
7.7.2）表示区zone
linux内核中，因为有硬件限制，所有物理内存页并不能归结为同样的属性。因此把相同属性的物理内存页面归结到了一个区中。
区的划分根据不同的硬件平台划分。
1enum migratetype {
2 MIGRATE_UNMOVABLE, //不能移动的
3 MIGRATE_MOVABLE, //可移动和
4 MIGRATE_RECLAIMABLE,
5 MIGRATE_PCPTYPES, //属于pcp list的
6 MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES,
7#ifdef CONFIG_CMA
8 MIGRATE_CMA, //属于CMA区的
9#endif
10#ifdef CONFIG_MEMORY_ISOLATION
11 MIGRATE_ISOLATE,
12#endif
13 MIGRATE_TYPES
14};
15//页面空闲链表头
16struct free_area {
17 struct list_head free_list[MIGRATE_TYPES];
18 unsigned long nr_free;
19};
20struct zone {
21 unsigned long _watermark[NR_WMARK];
22 unsigned long watermark_boost;
23 //预留的内存页面数
24 unsigned long nr_reserved_highatomic;
25 //内存区属于哪个内存节点
26#ifdef CONFIG_NUMA
27 int node;
28#endif
29 struct pglist_data *zone_pgdat;
30 //内存区开始的page结构数组的开始下标
31 unsigned long zone_start_pfn;
32 atomic_long_t managed_pages;
33 //内存区总的页面数
34 unsigned long spanned_pages;
35 //内存区存在的页面数
36 unsigned long present_pages;
37 //内存区名字
38 const char *name;
39 //挂载页面page结构的链表
40 struct free_area free_area[MAX_ORDER];
41 //内存区的标志
42 unsigned long flags;
43 /*保护free_area的自旋锁*/
44 spinlock_t lock;
45};
free_area结构数组，就是实现伙伴系统的重要结构，MAX_ORDER 的值默认为 11，分别表示挂载地址连续的 page 结构数目为 1，2，4，8，16，32……最大为 1024。
free_area 结构中又是一个 list_head 链表数组，该数组将具有相同迁移类型的 page 结构尽可能地分组，有的页面可以迁移，有的不可以迁移，同一类型的所有相同 order 的 page 结构，就构成了一组 page 结构块。
这样做的目的就是为了让内存页迁移更加高效，可以有效降低内存碎片。
7.7.3）表示内存节点
在很多服务器和大型计算机上，如果物理内存是分布式的，由多个计算节点组成，那么每个 CPU 核都会有自己的本地内存，CPU 在访问它的本地内存的时候就比较快，访问其他 CPU 核内存的时候就比较慢，这种体系结构被称为 Non-Uniform Memory Access（NUMA）。
1struct zoneref {
2 struct zone *zone;//内存区指针
3 int zone_idx; //内存区对应的索引
4};
5struct zonelist {
6 struct zoneref _zonerefs[MAX_ZONES_PER_ZONELIST + 1];
7};
8//zone枚举类型 从0开始
9enum zone_type {
10#ifdef CONFIG_ZONE_DMA
11 ZONE_DMA,
12#endif
13#ifdef CONFIG_ZONE_DMA32
14 ZONE_DMA32,
15#endif
16 ZONE_NORMAL,
17#ifdef CONFIG_HIGHMEM
18 ZONE_HIGHMEM,
19#endif
20 ZONE_MOVABLE,
21#ifdef CONFIG_ZONE_DEVICE
22 ZONE_DEVICE,
23#endif
24 __MAX_NR_ZONES
25
26};
27//定义MAX_NR_ZONES为__MAX_NR_ZONES 最大为6
28DEFINE(MAX_NR_ZONES, __MAX_NR_ZONES);
29//内存节点
30typedef struct pglist_data {
31 //定一个内存区数组，最大为6个zone元素
32 struct zone node_zones[MAX_NR_ZONES];
33 //两个zonelist，一个是指向本节点的的内存区，另一个指向由本节点分配不到内存时可选的备用内存区。
34 struct zonelist node_zonelists[MAX_ZONELISTS];
35 //本节点有多少个内存区
36 int nr_zones;
37 //本节点开始的page索引号
38 unsigned long node_start_pfn;
39 //本节点有多少个可用的页面
40 unsigned long node_present_pages;
41 //本节点有多少个可用的页面包含内存空洞
42 unsigned long node_spanned_pages;
43 //节点id
44 int node_id;
45 //交换内存页面相关的字段
46 wait_queue_head_t kswapd_wait;
47 wait_queue_head_t pfmemalloc_wait;
48 struct task_struct *kswapd;
49 //本节点保留的内存页面
50 unsigned long totalreserve_pages;
51 //自旋锁
52 spinlock_t lru_lock;
53} pg_data_t;
自己实现的系统类似于伙伴系统。
7.7.4）伙伴结构
7.7.5）分配页面
首先要找到内存节点，接着找到内存区，然后合适的空闲链表，最后在其中找到页的 page 结构，完成物理内存页面的分配。
所有的接口函数都会调用到 alloc_pages 函数，而这个函数最终会调用 __alloc_pages_nodemask 函数完成内存页面的分配。
分配：
内存页面的主要函数，这个 __alloc_pages_nodemask 函数主要干了三件事
- 准备分配页面的参数；
- 进入快速分配路径；
- 若快速分配路径没有分配到页面，就进入慢速分配路径。
1struct page *__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order, int preferred_nid, nodemask_t *nodemask)
2{
3 struct page *page;
4 unsigned int alloc_flags = ALLOC_WMARK_LOW;
5 gfp_t alloc_mask;
6 struct alloc_context ac = { };
7 //分配页面的order大于等于最大的order直接返回NULL
8 if (unlikely(order >= MAX_ORDER)) {
9 WARN_ON_ONCE(!(gfp_mask & __GFP_NOWARN));
10 return NULL;
11 }
12 gfp_mask &= gfp_allowed_mask;
13 alloc_mask = gfp_mask;
14 //准备分配页面的参数放在ac变量中
15 if (!prepare_alloc_pages(gfp_mask, order, preferred_nid, nodemask, &ac, &alloc_mask, &alloc_flags))
16 return NULL;
17 alloc_flags |= alloc_flags_nofragment(ac.preferred_zoneref->zone, gfp_mask);
18 //进入快速分配路径
19 page = get_page_from_freelist(alloc_mask, order, alloc_flags, &ac);
20 if (likely(page))
21 goto out;
22 alloc_mask = current_gfp_context(gfp_mask);
23 ac.spread_dirty_pages = false;
24 ac.nodemask = nodemask;
25 //进入慢速分配路径
26 page = __alloc_pages_slowpath(alloc_mask, order, &ac);
27out:
28 return page;
29}
准备分配页面的参数
1struct alloc_context {
2 struct zonelist *zonelist;
3 nodemask_t *nodemask;
4 struct zoneref *preferred_zoneref;
5 int migratetype;
6 enum zone_type highest_zoneidx;
7 bool spread_dirty_pages;
8};
9
10static inline bool prepare_alloc_pages(gfp_t gfp_mask, unsigned int order,
11 int preferred_nid, nodemask_t *nodemask,
12 struct alloc_context *ac, gfp_t *alloc_mask,
13 unsigned int *alloc_flags)
14{
15 //从哪个内存区分配内存
16 ac->highest_zoneidx = gfp_zone(gfp_mask);
17 //根据节点id计算出zone的指针
18 ac->zonelist = node_zonelist(preferred_nid, gfp_mask);
19 ac->nodemask = nodemask;
20 //计算出free_area中的migratetype值，比如如分配的掩码为GFP_KERNEL，那么其类型为MIGRATE_UNMOVABLE；
21 ac->migratetype = gfp_migratetype(gfp_mask);
22 //处理CMA相关的分配选项
23 *alloc_flags = current_alloc_flags(gfp_mask, *alloc_flags);
24 ac->spread_dirty_pages = (gfp_mask & __GFP_WRITE);
25 //搜索nodemask表示的节点中可用的zone保存在preferred_zoneref
26 ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,
27 ac->highest_zoneidx, ac->nodemask);
28 return true;
29}
repare_alloc_pages 函数根据传递进入的参数，就能找出要分配内存区、候选内存区以及内存区中空闲链表的 migratetype 类型。它把这些全部收集到 ac 结构中，只要它返回 true，就说明分配内存页面的参数已经准备ok
快速分配路径
快速分配路径不会处理内存页面合并和回收
这个函数的逻辑就是遍历所有的候选内存区，然后针对每个内存区检查水位线，是不是执行内存回收机制，当一切检查通过之后，就开始调用 rmqueue 函数执行内存页面分配。
慢速分配路径
慢速路径最主要的不同是它会执行页面回收，回收页面之后会进行多次重复分配，直到最后分配到内存页面，或者分配失败
1static inline struct page *
2__alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
3 struct alloc_context *ac)
4{
5 bool can_direct_reclaim = gfp_mask & __GFP_DIRECT_RECLAIM;
6 const bool costly_order = order > PAGE_ALLOC_COSTLY_ORDER;
7 struct page *page = NULL;
8 unsigned int alloc_flags;
9 unsigned long did_some_progress;
10 enum compact_priority compact_priority;
11 enum compact_result compact_result;
12 int compaction_retries;
13 int no_progress_loops;
14 unsigned int cpuset_mems_cookie;
15 int reserve_flags;
16
17retry:
18 //唤醒所有交换内存的线程
19 if (alloc_flags & ALLOC_KSWAPD)
20 wake_all_kswapds(order, gfp_mask, ac);
21 //依然调用快速分配路径入口函数尝试分配内存页面
22 page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
23 if (page)
24 goto got_pg;
25
26 //尝试直接回收内存并且再分配内存页面
27 page = __alloc_pages_direct_reclaim(gfp_mask, order, alloc_flags, ac,
28 &did_some_progress);
29 if (page)
30 goto got_pg;
31
32 //尝试直接压缩内存并且再分配内存页面
33 page = __alloc_pages_direct_compact(gfp_mask, order, alloc_flags, ac,
34 compact_priority, &compact_result);
35 if (page)
36 goto got_pg;
37 //检查对于给定的分配请求，重试回收是否有意义
38 if (should_reclaim_retry(gfp_mask, order, ac, alloc_flags,
39 did_some_progress > 0, &no_progress_loops))
40 goto retry;
41 //检查对于给定的分配请求，重试压缩是否有意义
42 if (did_some_progress > 0 &&
43 should_compact_retry(ac, order, alloc_flags,
44 compact_result, &compact_priority,
45 &compaction_retries))
46 goto retry;
47 //回收、压缩内存已经失败了，开始尝试杀死进程，回收内存页面
48 page = __alloc_pages_may_oom(gfp_mask, order, ac, &did_some_progress);
49 if (page)
50 goto got_pg;
51got_pg:
52 return page;
53}
内存压缩不是指压缩内存中的数据，而是指移动内存页面，进行内存碎片整理，腾出更大的连续的内存空间。如果内存碎片整理了，还是不能成功分配内存，就要杀死进程以便释放更多内存页面
如何分配内存页面？
实际完成分配任务的是 rmqueue 函数
1static inline struct page *rmqueue(struct zone *preferred_zone,
2 struct zone *zone, unsigned int order,
3 gfp_t gfp_flags, unsigned int alloc_flags,
4 int migratetype)
5{
6 unsigned long flags;
7 struct page *page;
8 if (likely(order == 0)) {
9 if (!IS_ENABLED(CONFIG_CMA) || alloc_flags & ALLOC_CMA ||
10 migratetype != MIGRATE_MOVABLE) {
11 //如果order等于0,就说明是分配一个页面，说就从pcplist中分配
12 page = rmqueue_pcplist(preferred_zone, zone, gfp_flags,
13 migratetype, alloc_flags);
14 goto out;
15 }
16 }
17 //加锁并关中断
18 spin_lock_irqsave(&zone->lock, flags);
19 do {
20 page = NULL;
21 if (order > 0 && alloc_flags & ALLOC_HARDER) {
22 //从free_area中分配
23 page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
24 }
25 if (!page)
26 //它最后也是调用__rmqueue_smallest函数
27 page = __rmqueue(zone, order, migratetype, alloc_flags);
28 } while (page && check_new_pages(page, order));
29 spin_unlock(&zone->lock);
30 zone_statistics(preferred_zone, zone);
31 local_irq_restore(flags);
32out:
33 return page;
34}
rmqueue_pcplist 函数，在请求分配一个页面的时候，就是用它从 pcplist 中分配页面的。所谓的 pcp 是指，每个 CPU 都有一个内存页面高速缓冲，由数据结构 per_cpu_pageset 描述，包含在内存区中。
在 Linux 内核中，系统会经常请求和释放单个页面。如果针对每个 CPU，都建立出预先分配了单个内存页面的链表，用于满足本地 CPU 发出的单一内存请求，就能提升系统的性能
1struct per_cpu_pages {
2 int count; //列表中的页面数
3 int high; //页面数高于水位线，需要清空
4 int batch; //从伙伴系统增加/删除的块数
5 //页面列表，每个迁移类型一个。
6 struct list_head lists[MIGRATE_PCPTYPES];
7};
8struct per_cpu_pageset {
9 struct per_cpu_pages pcp;
10#ifdef CONFIG_NUMA
11 s8 expire;
12 u16 vm_numa_stat_diff[NR_VM_NUMA_STAT_ITEMS];
13#endif
14#ifdef CONFIG_SMP
15 s8 stat_threshold;
16 s8 vm_stat_diff[NR_VM_ZONE_STAT_ITEMS];
17#endif
18};
19static struct page *__rmqueue_pcplist(struct zone *zone, int migratetype,unsigned int alloc_flags,struct per_cpu_pages *pcp,
20 struct list_head *list)
21{
22 struct page *page;
23 do {
24 if (list_empty(list)) {
25 //如果list为空，就从这个内存区中分配一部分页面到pcp中来
26 pcp->count += rmqueue_bulk(zone, 0,
27 pcp->batch, list,
28 migratetype, alloc_flags);
29 if (unlikely(list_empty(list)))
30 return NULL;
31 }
32 //获取list上第一个page结构
33 page = list_first_entry(list, struct page, lru);
34 //脱链
35 list_del(&page->lru);
36 //减少pcp页面计数
37 pcp->count--;
38 } while (check_new_pcp(page));
39 return page;
40}
41static struct page *rmqueue_pcplist(struct zone *preferred_zone,
42 struct zone *zone, gfp_t gfp_flags,int migratetype, unsigned int alloc_flags)
43{
44 struct per_cpu_pages *pcp;
45 struct list_head *list;
46 struct page *page;
47 unsigned long flags;
48 //关中断
49 local_irq_save(flags);
50 //获取当前CPU下的pcp
51 pcp = &this_cpu_ptr(zone->pageset)->pcp;
52 //获取pcp下迁移的list链表
53 list = &pcp->lists[migratetype];
54 //摘取list上的page结构
55 page = __rmqueue_pcplist(zone, migratetype, alloc_flags, pcp, list);
56 //开中断
57 local_irq_restore(flags);
58 return page;
59}
但是，遇到多个内存页面的分配请求，就会调用 __rmqueue_smallest 函数，从 free_area 数组中分配。
1static inline struct page *get_page_from_free_area(struct free_area *area,int migratetype)
2{//返回free_list[migratetype]中的第一个page若没有就返回NULL
3 return list_first_entry_or_null(&area->free_list[migratetype],
4 struct page, lru);
5}
6static inline void del_page_from_free_list(struct page *page, struct zone *zone,unsigned int order)
7{
8 if (page_reported(page))
9 __ClearPageReported(page);
10 //脱链
11 list_del(&page->lru);
12 //清除page中伙伴系统的标志
13 __ClearPageBuddy(page);
14 set_page_private(page, 0);
15 //减少free_area中页面计数
16 zone->free_area[order].nr_free--;
17}
18
19static inline void add_to_free_list(struct page *page, struct zone *zone,
20 unsigned int order, int migratetype)
21{
22 struct free_area *area = &zone->free_area[order];
23 //把一组page的首个page加入对应的free_area中
24 list_add(&page->lru, &area->free_list[migratetype]);
25 area->nr_free++;
26}
27//分割一组页
28static inline void expand(struct zone *zone, struct page *page,
29 int low, int high, int migratetype)
30{
31 //最高order下连续的page数 比如high = 3 size=8
32 unsigned long size = 1 << high;
33 while (high > low) {
34 high--;
35 size >>= 1;//每次循环左移一位 4,2,1
36 //标记为保护页，当其伙伴被释放时，允许合并
37 if (set_page_guard(zone, &page[size], high, migratetype))
38 continue;
39 //把另一半pages加入对应的free_area中
40 add_to_free_list(&page[size], zone, high, migratetype);
41 //设置伙伴
42 set_buddy_order(&page[size], high);
43 }
44}
45
46static __always_inline struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,int migratetype)
47{
48 unsigned int current_order;
49 struct free_area *area;
50 struct page *page;
51 for (current_order = order; current_order < MAX_ORDER; ++current_order) {
52 //获取current_order对应的free_area
53 area = &(zone->free_area[current_order]);
54 //获取free_area中对应migratetype为下标的free_list中的page
55 page = get_page_from_free_area(area, migratetype);
56 if (!page)
57 continue;
58 //脱链page
59 del_page_from_free_list(page, zone, current_order);
60 //分割伙伴
61 expand(zone, page, order, current_order, migratetype);
62 set_pcppage_migratetype(page, migratetype);
63 return page;
64 }
65 return NULL;
66}
分割伙伴页面，然后加入到新的伙伴上。
吾心信其可行，
则移山填海之难，
终有成功之日！
——孙文
则移山填海之难，
终有成功之日！
——孙文
评论
0 评论
