Linux 内核物理页面内存分配

0x00 前言

之前分析一个Linux内核的洞,需要对内存分配这块比较熟悉,这篇文章之前的学习笔记整理。
以下所有的源码分析基于linux-4.20-rc3。这篇文件断断续续写了快一个月,这里面东西还有好多,等之后再找时间补上。

0x01 UMA和NUMA模型

1.1 UMA模型

一致存储器访问(Uniform-Memory-Access,简称UMA)模型,一致性意指无论在什么时候,处理器只能为内存的每个数据保持或共享唯一一个数值。物理存储器备所有处理器均匀共享。所有处理对所有存储内存有相同的访问时间。在Linux中,在这种模式下还是使用节点,但是时一个单独的节点,它包含了系统中的所有物理内存。

1.2 NUMA模型

非一致存储器访问(Nonuniform-Memory-Access,简称NUMA)模型,是一种分布式存储器访问方式,处理器可以同时访问不同的存储器地址。NUMA总是多处理器计算机,在这种模式下,给定CPU对不同的内存单元的访问时间可能不一样。

-w590

在这种模式下。系统的物理内存被划分为多个节点(node)。在一个单独的节点内,任一给定的CPU访问页面所需的时间都是相同的。对于不同的CPU,访问时间可能不同。每个node被分配有本地存储器空间。所有node中的处理器都可以访问全部的物理存储器,但是访问本地node比访问其他node所需的时间要少的多。

0x02 Linux物理内存组织形式

2.1 内存组织形式

Linux把物理内存分为三个层次来管理:节点(node)、区域(zone)、页面(page)。
LinuxNUMA中内存访问速度一致的部分划分为一个节点(node),然后每个节点(node)有分为多个区域(zone),每个区域(zone)又包含多个页面(page)。三者关系如下图:

-w541


每个节点(node)都有一个类型为pg_data_t的描述符,所有节点的描述符存放在一个单向链表里,由变量pgdat_list指向。系统中的每个结点都通过pgdat_list链表pg_data_t->node_next连接起来,该链接以NULL为结束标志。在UMA中,pgdat_list变量指向一个链表,该链表只有一个元素,这个元素就是节点0描述符,它被存放在contig_page_data变量中。 每个区域(zone)都有一个类型为zone_t的描述符,用以表示内存的某个范围,低端范围的16MB被描述为ZONE_DMA,某些工业标准体系结构中的(ISA)设备需要用到它,然后是可直接映射到内核的普通内存域ZONE_NORMAL,最后是超出了内核段的物理地址域ZONE_HIGHMEM,被称为高端内存。是系统中预留的可用内存空间, 不能被内核直接映射。
-w780

2.2 相关数据结构

2.2.1 内存节点描述符 - struct pglist_data

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
typedef struct pglist_data {
//节点区域:在x86下,有,ZONE_HIGHMEM,ZONE_NORMAL,
//ZONE_DMA;在x86_64,CPU中区域有DMA、DMA32和NORMAL三部分
//管理当前节点zone描述符数组。
struct zone node_zones[MAX_NR_ZONES];
//分配区域时的顺序,由函数free_area_init_core()调用mm/page_alloc.c 中函数build_zonelists()设置;
/*页分配器使用的zonelist数据结构的数组,将所有节点的管理区按一定的关联链接成一个链表,分配内存时会按照链表的顺序进行分配
它是zonelist结构的数组,长度为MAX_ZONELISTS。如果内核未配置NUMA,则长度为1,否则,长度为2。该数组中0号元素指定了备用的内存管理区链表,也就是当前系统中所有的zone。1号元素指定了当前节点中的管理区链表。除非分配内存时指定了GFP_THISNODE标志而采用本地内存节点上的zonelist,一般均采用备用zonelist。
*/
struct zonelist node_zonelists[MAX_ZONELISTS];
//number of zone,usually in range of 1~3,not all zones have 3 zones.
int nr_zones;
#ifdef CONFIG_FLAT_NODE_MEM_MAP /* means !SPARSEMEM */
//first page address in array mem_map to this node
//指向节点中所有页描述符的数组的指针
struct page *node_mem_map;
......
//在numa架构中,页框会有两个下标,一个是在buddy系统中的下标,一个是在所有页框中的下标
//比如在节点2中的页框1,在buddy系统中的下标是1,在所有的页框中的下标是1001,
//该变量就是保存的该节点的第一个页框的下标,方便转换
unsigned long node_start_pfn; //the start page frame number to this node
unsigned long node_present_pages; /* total number of physical pages */
unsigned long node_spanned_pages; /* total size of physical page
range, including holes,该节点的所有物理页面,包括空洞(比如部分地址为外设I/O使用 */
int node_id;//节点ID,从0开始
/* kswaped页换出守护进程使用的等待队列 */
wait_queue_head_t kswapd_wait;

wait_queue_head_t pfmemalloc_wait;
/* 指针指向kswapd内核线程的进程描述符 */
struct task_struct *kswapd; ......
/*
* This is a per-node reserve of pages that are not available
* to userspace allocations.
*/
unsigned long totalreserve_pages;

#ifdef CONFIG_NUMA
/*
* zone reclaim becomes active if more unmapped pages exist.
*/
unsigned long min_unmapped_pages;
unsigned long min_slab_pages;
#endif /* CONFIG_NUMA */

/* Write-intensive fields used by page reclaim */
ZONE_PADDING(_pad1_)
spinlock_t lru_lock;

......

/* Fields commonly accessed by the page reclaim scanner */
struct lruvec lruvec;

unsigned long flags;

ZONE_PADDING(_pad2_)

/* Per-node vmstats */
struct per_cpu_nodestat __percpu *per_cpu_nodestats;
atomic_long_t vm_stat[NR_VM_NODE_STAT_ITEMS];
} pg_data_t;

每个结点都有一个内核线程kswapd,它的作用就是将进程或内核持有的,但是不常用的页交换到磁盘上,以腾出更多可用内存。

2.2.2 管理区描述符 - struct zone

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
struct zone {
/* zone watermarks, access with *_wmark_pages(zone) macros
page_min,page_low,page_high反应了区域的空闲页面的数量
page_min : zone中保留页的数量
page_low : 回收页框使用的下界,同时也被管理区分配器作为阀值使用,一般这个数字是pages_min的5/4
page_high : 回收页框使用的上界,同时也被管理区分配器作为阀值使用,一般这个数字是pages_min的3/2

*/
unsigned long watermark[NR_WMARK];

unsigned long nr_reserved_highatomic;

//针对每个区域保存的物理页面数量,保证在任何情况下,内存分配都不会失败
long lowmem_reserve[MAX_NR_ZONES];

#ifdef CONFIG_NUMA
int node;
#endif
struct pglist_data *zone_pgdat;//指向该区域的节点pg_data_t
/* 实现每CPU页框高速缓存,里面包含每个CPU的单页框的链表 */
struct per_cpu_pageset __percpu *pageset;

#ifndef CONFIG_SPARSEMEM
/*
* Flags for a pageblock_nr_pages block. See pageblock-flags.h.
* In SPARSEMEM, this map is stored in struct mem_section
*/
unsigned long *pageblock_flags;
#endif /* CONFIG_SPARSEMEM */

/* zone_start_pfn == zone_start_paddr >> PAGE_SHIFT
那个zone_mem_map结构已经不存在,而是由 zone_start_pfn 地址来代替,
通过这种方式查找出来的pfn是某个内存区域特有的!比如是ZONE_DMA/ZONE_NORMAL/ZONE_HIGHMEM的第一个pfn号码!
*/
unsigned long zone_start_pfn;
/* managed_pages 是这个zone被Buddy管理的所有的page数目,
* 计算的方式:
* managed_pages = present_pages - reserved_pages
* 其中reserved_pages包括被Bootmem分配走的内存
*/
unsigned long managed_pages;
/* spanned_pages 是这个zone跨越的所有物理内存的page数目
* 包括内存空洞,它的计算方式:
* spanned_pages = zone_end_pfn - zone_start_pfn
*/
unsigned long spanned_pages;
/* present_pages 是这个zone在物理内存真实存在的所有page数目,
* 它的计算方式:
* present_pages = spanned_pages - absent_pages
* 其中absent_pages指的是内存空洞的page数目
*/
unsigned long present_pages;

const char *name;//区域的名字:DMA\DMA32\NORMAL\HIGHMEN\MOVEABLE

#ifdef CONFIG_MEMORY_ISOLATION
/*
* Number of isolated pageblock. It is used to solve incorrect
* freepage counting problem due to racy retrieving migratetype
* of pageblock. Protected by zone->lock.
*/
/* 在内存隔离中表示隔离的页框块数量 */
unsigned long nr_isolate_pageblock;
#endif

#ifdef CONFIG_MEMORY_HOTPLUG
/* see spanned/present_pages for more description */
seqlock_t span_seqlock;
#endif
......
/* 伙伴算法分配使用的保存空闲页面的结构,标识出管理区中的空闲页框块,用于伙伴系统。 MAX_ORDER为11,分别代表包含大小为1,2,4,8,16,32,64,128,256,512,1024个连续页框的链表 */
*/
struct free_area free_area[MAX_ORDER];

/* zone flags, see below */
unsigned long flags;

/* Primarily protects free_area */
spinlock_t lock;//spinlock防止对区域的并发访问

......
} ____cacheline_internodealigned_in_smp;

此管理区描述符中的实际把所有属于该管理区的页框保存在两个地方:struct free_area free_area[MAX_ORDER]和struct per_cpu_pageset __percpu * pageset。free_area是这个管理区的伙伴系统,而pageset是这个区的每CPU页框高速缓存。对管理区的理解需要结合伙伴系统和每CPU页框高速缓存

2.2.3 页框描述符 - struct page

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
struct page {
/*包含有很多信息,包括此页框属于的node结点号,此页框属于的zone号和此页框的属性。 */
unsigned long flags;
/*
* Five words (20/40 bytes) are available in this union.
* WARNING: bit 0 of the first word is used for PageTail(). That
* means the other users of this union MUST NOT use the bit to
* avoid collision and false-positive PageTail().
*/
union {
struct { /* Page cache and anonymous pages */
/**
用于将此页描述符放入相应的链表,比如伙伴系统或者每CPU页框高速缓存。 */
struct list_head lru;
/* See page-flags.h for PAGE_MAPPING_FLAGS
用于页描述符,当页被插入页高速缓存中时使用,或者当页属于匿名区时使用
*/
struct address_space *mapping;
pgoff_t index; /* Our offset within mapping. */
/**
* @private: Mapping-private opaque data.
* Usually used for buffer_heads if PagePrivate.
* Used for swp_entry_t if PageSwapCache.
* Indicates order in the buddy system if PageBuddy.
*/
unsigned long private;
};
struct { /* slab, slob and slub */
union {
struct list_head slab_list; /* uses lru */
struct { /* Partial pages */
struct page *next;
#ifdef CONFIG_64BIT
int pages; /* Nr of pages left */
int pobjects; /* Approximate count */
#else
short int pages;
short int pobjects;
#endif
};
};
struct kmem_cache *slab_cache; /* not slob */
/* Double-word boundary */
void *freelist; /* first free object */
union {
void *s_mem; /* slab: first object */
unsigned long counters; /* SLUB */
struct { /* SLUB */
unsigned inuse:16;
unsigned objects:15;
unsigned frozen:1;
};
};
};
struct { /* Tail pages of compound page */
unsigned long compound_head; /* Bit zero is set */

/* First tail page only */
unsigned char compound_dtor;
unsigned char compound_order;
atomic_t compound_mapcount;
};
struct { /* Second tail page of compound page */
unsigned long _compound_pad_1; /* compound_head */
unsigned long _compound_pad_2;
struct list_head deferred_list;
};
struct { /* Page table pages */
unsigned long _pt_pad_1; /* compound_head */
pgtable_t pmd_huge_pte; /* protected by page->ptl */
unsigned long _pt_pad_2; /* mapping */
union {
struct mm_struct *pt_mm; /* x86 pgds only */
atomic_t pt_frag_refcount; /* powerpc */
};
#if ALLOC_SPLIT_PTLOCKS
spinlock_t *ptl;
#else
spinlock_t ptl;
#endif
};
struct { /* ZONE_DEVICE pages */
/** @pgmap: Points to the hosting device page map. */
struct dev_pagemap *pgmap;
unsigned long hmm_data;
unsigned long _zd_pad_1; /* uses mapping */
};

/** @rcu_head: You can use this to free a page by RCU. */
struct rcu_head rcu_head;
};

union { /* This union is 4 bytes in size. */
/*
* If the page can be mapped to userspace, encodes the number
* of times this page is referenced by a page table.
*/
atomic_t _mapcount;

/*
* If the page is neither PageSlab nor mappable to userspace,
* the value stored here may help determine what this page
* is used for. See page-flags.h for a list of page types
* which are currently stored here.
*/
unsigned int page_type;

unsigned int active; /* SLAB */
int units; /* SLOB */
};

/* Usage count. *DO NOT USE DIRECTLY*. See page_ref.h
页框的引用计数,如果为-1,则此页框空闲,并可分配给任一进程或内核;
如果大于或等于0,则说明页框被分配给了一个或多个进程,或用于存放内核数据。
page_count()返回_count加1的值,也就是该页的使用者数目
*/
atomic_t _refcount;
......
} _struct_page_alignment;

2.2.4 每CPU页框高速缓存 - struct per_cpu_pages

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct per_cpu_pages {
int count; /* number of pages in the list */
/*
上界,当此CPU高速缓存中页框个数大于high,则会将batch个页框放回伙伴系统
*/
int high;
/* 在高速缓存中将要添加或被删去的页框个数 */
int batch;

/* Lists of pages, one per migrate type stored on the pcp-lists
页框的链表,如果需要冷高速缓存,从链表尾开始获取页框,如果需要热高速缓存,从链表头开始获取页框
*/
struct list_head lists[MIGRATE_PCPTYPES];
};

0x03 页面分配与回收API

下图展示了内核内存分配回收的一些API函数:

-w782

所有的内存分配API函数最后都会调用alloc_pages函数,而alloc_pages函数的定义依赖于NUMA或者UMA架构。

3.1 NUMA架构alloc_pages函数实现

NUMA架构下,具体定义如下:

1
2
3
4
5
6
7
8
503 #ifdef CONFIG_NUMA
504 extern struct page *alloc_pages_current(gfp_t gfp_mask, unsigned order);
505
506 static inline struct page *
507 alloc_pages(gfp_t gfp_mask, unsigned int order)
508 {
509 return alloc_pages_current(gfp_mask, order);
510 }

alloc_pages函数这里会调用alloc_pages_current函数,具体的分配调用路径为:

1
2
3
4
5
6
7
alloc_pages(gfp_t gfp_mask, unsigned int order)
--> alloc_pages_current(gfp_mask, order)
--> alloc_page_interleave(gfp, order, interleave_nodes(pol))
| --> __alloc_pages(gfp, order, nid)
| --> __alloc_pages_nodemask(gfp_mask, order, preferred_nid, NULL)
|
--> __alloc_pages_nodemask(gfp, order,policy_node(gfp, pol, numa_node_id()),policy_nodemask(gfp, pol))

根据内存分配策略选择最终内存分配函数__alloc_pages_nodemask

3.2 UMA架构alloc_pages函数实现

UMA架构下,具体定义如下:

1
2
3
514 #else
515 #define alloc_pages(gfp_mask, order) \
516 alloc_pages_node(numa_node_id(), gfp_mask, order)

具体的分配调用路径为:

1
2
3
4
5
alloc_pages(gfp_mask, order)
--> alloc_pages_node(numa_node_id(), gfp_mask, order)
--> __alloc_pages_node(nid, gfp_mask, order)
--> __alloc_pages(gfp_mask, order, nid)
--> __alloc_pages_nodemask(gfp_mask, order, preferred_nid, NULL)

最后会调用__alloc_pages_nodemask函数,该函数被称为伙伴算法的心脏,它处理实质性的内存分配。

0x04 __alloc_pages_nodemask()函数源码分析

__alloc_pages_nodemask函数位于mm/kasan/page_alloc.c。在详细分析之前先将里面要用到的一些重要标志放在前面说明。内核在进行内存分配过程中,会用到一些标志来辅助该过程。

4.1 water_mark–水准

当系统中的空闲内存不断被消耗,kswapd守护进程就会被唤醒去释放页面。若内存空闲率很低,kswapd就会同步地释放内存,有时称为直接回收(direct-reclaim)路径。
每个zone有三个water mark:page_lowpage_minpage_high。关于zone_water_mark定义位于文件include/linux/mmzone.h

1
2
3
4
5
6
7
8
9
10
265 enum zone_watermarks {
266 WMARK_MIN,
267 WMARK_LOW,
268 WMARK_HIGH,
269 NR_WMARK
270 };
271
272 #define min_wmark_pages(z) (z->watermark[WMARK_MIN])
273 #define low_wmark_pages(z) (z->watermark[WMARK_LOW])
274 #define high_wmark_pages(z) (z->watermark[WMARK_HIGH])

区域水准和内存空闲页面的关系如下图:

-w744

在不同的空闲页面的水准上,会采取不同的动作:

  • WMARK_MIN: 当空闲页面的数量降到WMARK_MIN时,buddy分配器会唤醒 kswapd 守护进程以同步的方式进行直接内存回收(direct-reclaim)。
  • WMARK_LOW: 当空闲页面的数量降到WMARK_LOW时,buddy分配器会唤醒 kswapd 守护进程进行内存回收。
  • WMARK_HIGH: 此时kswapd进程会进入休眠

4.2 gfp_mask

__alloc_pages_nodemask函数的参数中有两个比较重要的,一个是order,代表分配物理页面数量的阶,物理页面分配必须都是2的order次幂。
gfp_mask参数为内存分配的分配掩码。分配掩码分为两部分:内存域修饰符(占低4位)、内存分配标志(从低5位开始)。
内存zone的类型有:ZONE_DMAZONE_DMA32ZONE_NORMALZONE_HIGHMEMZONE_MOVABLE。而内存域的修饰符只有以下4种,定义如下:

1
2
3
4
19 #define ___GFP_DMA              0x01u
20 #define ___GFP_HIGHMEM 0x02u
21 #define ___GFP_DMA32 0x04u
22 #define ___GFP_MOVABLE 0x08u

没有ZONE_NORMAL的修饰符是因为ZONE_NORMAL是默认的修饰符。

4.2.1 内存域修饰符与内存分配器扫描内存域顺序的关系

内存域修饰符 扫描内存域顺序
默认 ZONE_NORMAL->ZONE_DMA32->ZONE_DMA
___GFP_DMA32 ZONE_DMA32->ZONE_DMA
___GFP_DMA ZONE_DMA
_GFP_DMA&_GFP_HIGHMEM ZONE_DMA
___GFP_HIGHMEM ZONE_HIGHMEN->ZONE_MORMAL->ZONE_DMA32->ZONE_DMA

4.2.2 内存分配标志

gfp_mask分配除了低4位内存域修饰符外,其他的位的一部分做为了内存分配标识,但是这些标志一般都是组合使用,定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 23 #define ___GFP_RECLAIMABLE      0x10u
24 #define ___GFP_HIGH 0x20u
25 #define ___GFP_IO 0x40u
26 #define ___GFP_FS 0x80u
27 #define ___GFP_WRITE 0x100u
28 #define ___GFP_NOWARN 0x200u
29 #define ___GFP_RETRY_MAYFAIL 0x400u
30 #define ___GFP_NOFAIL 0x800u
31 #define ___GFP_NORETRY 0x1000u
32 #define ___GFP_MEMALLOC 0x2000u
33 #define ___GFP_COMP 0x4000u
34 #define ___GFP_ZERO 0x8000u
35 #define ___GFP_NOMEMALLOC 0x10000u
36 #define ___GFP_HARDWALL 0x20000u
37 #define ___GFP_THISNODE 0x40000u
38 #define ___GFP_ATOMIC 0x80000u
39 #define ___GFP_ACCOUNT 0x100000u
40 #define ___GFP_DIRECT_RECLAIM 0x200000u
41 #define ___GFP_KSWAPD_RECLAIM 0x400000u
42 #ifdef CONFIG_LOCKDEP
43 #define ___GFP_NOLOCKDEP 0x800000u
44 #else
45 #define ___GFP_NOLOCKDEP 0
46 #endif
```

### 4.3 struct alloc_context 结构体
该结构体封装了内存分配要用到的一些参数标识。
```c
117 struct alloc_context {
//当perferred_zone上没有合适的页可以分配时,就要按zonelist中的顺序扫描该zonelist中备用zone列表,一个个的试用,通常的顺序是high->normal->dma
118 struct zonelist *zonelist;
//表示节点的mask,这是个bit数组,数组元素的值标识着对应的结点是否可以分配内存
119 nodemask_t *nodemask;
//表示从high_zoneidx后找到的合适的zone,一般会从该zone分配;
//如果分配失败,就会从zonelist在找一个preferred_zoneref = 合适的zone
120 struct zoneref *preferred_zoneref;
//迁移类型,在zone->free_area.free_list[XXX] 作为分配下标使用,这个是用来反碎片化的,修改了以前的
//free_area结构体,在该结构体中再添加了一个数组,该数组以迁移类型为下标,每个数组元素都挂了对应迁移类型的页链表
121 int migratetype;
//表示内存分配时,所能分配的最高zone,一般从high->normal->dma的顺序来遍历,
122 enum zone_type high_zoneidx;
123 bool spread_dirty_pages;
124 };

4.4 __alloc_pages_nodemask源码分析

该函数定义在mm/page_alloc.c文件中,该函数实现的功能主要有以下三点:

  1. 进行一些必要的check,并将之后进行内存分配所要用到的一些标识进行初始化。
  2. 尝试快分配 - get_page_from_freelist()
  3. 若第2步失败,尝试慢分配 - __alloc_pages_slowpath()

4.4.1 前期check & struct alloc_context结构体变量ac初始化

首先会判断参数order是否大于MAX_ORDERMAX_ORDER定义为11order表示free_list数组的下标。

1
2
3
4
4362         if (unlikely(order >= MAX_ORDER)) {
4363 WARN_ON_ONCE(!(gfp_mask & __GFP_NOWARN));
4364 return NULL;
4365 }

上面是做一些基本的check ,然后调用prepare_alloc_pages()函数对struct alloc_context结构体变量ac进行初始化赋值。跟进该函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
4299 static inline bool prepare_alloc_pages(gfp_t gfp_mask, unsigned int order,
4300 int preferred_nid, nodemask_t *nodemask,
4301 struct alloc_context *ac, gfp_t *alloc_mask,
4302 unsigned int *alloc_flags)
4303 {
//获取内存分配时,所能分配内存的最高zone,通常的顺序是:HIGHMEN->NORMAL->DMA。high_zoneidx是_zonerefs数组的下标,
4304 ac->high_zoneidx = gfp_zone(gfp_mask);
//当perferred_zone上没有合适的页可以分配时,就要按zonelist中的顺序扫描该zonelist中备用zone列表,一个个的试用
4305 ac->zonelist = node_zonelist(preferred_nid, gfp_mask);
4306 ac->nodemask = nodemask;
//根据gfp_mask标识转换成相应的migratetype
4307 ac->migratetype = gfpflags_to_migratetype(gfp_mask);
//检查cpusets功能是否开启,这个是一个cgroup的子模块, 如果没有设置nodemask就会用cpusets配置的cpuset_current_mems_allowed来限制在哪个node上分配,这个也是在NUMA结构当中才会有用的.
4309 if (cpusets_enabled()) {
4310 *alloc_mask |= __GFP_HARDWALL;
4311 if (!ac->nodemask)
4312 ac->nodemask = &cpuset_current_mems_allowed;
4313 else
4314 *alloc_flags |= ALLOC_CPUSET;
4315 }
4316
4317 fs_reclaim_acquire(gfp_mask);
4318 fs_reclaim_release(gfp_mask);
//might_sleep_if,判断gfp_mask & __GFP_DIRECT_RECLAIM), 表示当前内存压力比较大需要直接回收内存, 会循环睡眠同步等待页可用,
4320 might_sleep_if(gfp_mask & __GFP_DIRECT_RECLAIM);
//而might_sleep_if是一个debug函数,标记当前函数在if为true的时候表示可能会进入睡眠, 如果当前调用进入了一个不可睡眠的上下文就会报错. should_fail_alloc_page会做一些预检查, 一些无法分配的条件会直接报错.
4322 if (should_fail_alloc_page(gfp_mask, order))
4323 return false;
//判断是否开启了连续内存分配器,并且要求迁移类型为可移动
4325 if (IS_ENABLED(CONFIG_CMA) && ac->migratetype == MIGRATE_MOVABLE)
4326 *alloc_flags |= ALLOC_CMA;
4327
4328 return true;
4329 }

回到__alloc_pages_nodemask函数,接着调用finalise_ac(gfp_mask, &ac)函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
4331 /* Determine whether to spread dirty pages and what the first usable zone */
4332 static inline void finalise_ac(gfp_t gfp_mask, struct alloc_context *ac)
4333 {
4334 /* Dirty zone balancing only done in the fast path */
4335 ac->spread_dirty_pages = (gfp_mask & __GFP_WRITE);
4336
4337 /*
4338 * The preferred zone is used for statistics but crucially it is
4339 * also used as the starting point for the zonelist iterator. It
4340 * may get reset for allocations that ignore memory policies.
4341 */
4342 ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,
4343 ac->high_zoneidx, ac->nodemask);
4344 }

finalise_ac函数会对ac->preferred_zoneref 进行赋值,即可用来分配内存的zone。如何来查找可用来内存分配的zone,在下面详细说明一下。
first_zones_zonelist函数会根据zonelisthighidx,nodemask这几个参数,最终选择一个zone最为第一个可用来内存分配的zone。内存分配的zone的寻找,是通过遍历zonelist_zonerefs数组来做的,struct zonelist结构体定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
590 /*
591 * This struct contains information about a zone in a zonelist. It is stored
592 * here to avoid dereferences into large structures and lookups of tables
593 */
594 struct zoneref {
595 struct zone *zone; /* Pointer to actual zone */
596 int zone_idx; /* zone_idx(zoneref->zone) */
597 };
598 .......
613 struct zonelist {
614 struct zoneref _zonerefs[MAX_ZONES_PER_ZONELIST + 1];
615 };

_zonerefs数组的大小为MAX_ZONES_PER_ZONELIST + 1MAX_ZONES_PER_ZONELIST的值取决于最大节点数和每个节点最大zone数,

1
2
575 /* Maximum number of zones on a zonelist */
576 #define MAX_ZONES_PER_ZONELIST (MAX_NUMNODES * MAX_NR_ZONES)
1
10 #define MAX_NR_ZONES 5 /* __MAX_NR_ZONES */

查找最大能分配的zone的逻辑是在zonelist中找到第一个idxhighidx小的zone返回作为内存分配的首先zone
函数调用链如下:

1
2
3
first_zones_zonelist(ac->zonelist,ac->high_zoneidx, ac->nodemask)
--> first_zones_zonelist(struct zonelist *zonelist,enum zone_type highest_zoneidx,nodemask_t *nodes)
--> next_zones_zonelist(struct zoneref *z, enum zone_type highest_zoneidx, nodemask_t *nodes)

最终的查找逻辑是在next_zones_zonelist函数中实现:

1
2
3
4
5
6
7
8
989 static __always_inline struct zoneref *next_zones_zonelist(struct zoneref *z,
990 enum zone_type highest_zoneidx,
991 nodemask_t *nodes)
992 {
993 if (likely(!nodes && zonelist_zone_idx(z) <= highest_zoneidx))
994 return z;
995 return __next_zones_zonelist(z, highest_zoneidx, nodes);
996 }

由于highest_zoneidx是最大的区域,所以只要小于该区域的zone就是首选zone。

4.4.2 快分配 – get_page_from_freelist

到这里内存分配需用到的参数标识都初始化完了,回到__alloc_pages_nodemask函数,接下来会调用关键函数get_page_from_freelist进程快速内存分配。如果分配失败,会继续尝试其他途径分配所需内存,也叫做慢分配。
具体的源码比较多,下面就简单的说明下该函数的一些操作:

1
2
3
4
5
1. 首先进入一个for循环,遍历ac->zonelist中不大于zc->highidx的所有zone:for_next_zone_zonelist_nodemask
2. 接下来会检查是否开启了cpuset而且设置了ALLOC_CPUSET标志就检查看当前CPU是否允许在内存域zone所在结点中分配内存。
3. 检查ac->spread_dirty_pages的值,ac->spread_dirty_pages不为零标识本次内存分配用于写,可能增加赃页数。并且检查当前zone所在节点的脏页面是否超标,若超标则跳过,遍历下一个zone。
4. 获取该zone的水准,并检查该zone的空闲页面时候在水准之上。若该zone的空闲页面在水准之下,则会进行空闲页回收,在该zone设置了水准标志的前提下,并且设置了可回收标志。
5. 在上面内存回收之后,水准满足要求,或者没有设置水准标志,会尝试在该zone进行内存分配。调用rmqueue函数尝试分配。
1
2
3
4
5
6
7
3359 //执行到这里表示选择的zone有空闲内存
3360 try_this_zone:
3361 //尝试内存分配
3362 page = rmqueue(ac->preferred_zoneref->zone, zone, order,
3363 gfp_mask, alloc_flags, ac->migratetype);
3364 if (page) {
3365

执行到这块代码,代表当前zone有空闲内存,调用函数rmqueue函数尝试内存分配。

4.4.2.1 rmqueue

rmqueue函数的作用是从当前的zone分配空闲页面。分配时存在三种情况。

  1. order==0,表示分配单页,这个时候调用rmqueue_pcplist()函数分配,即从冷热页中找。
  2. 如果order不为0,并且设置了ALLOC_HARDER标志,表示一次高优先级的分配。调用__rmqueue_smallest()函数,从前一类型为MIGRATE_HIGHATOMIC的链表中去分配。MIGRATE_HIGHATOMIC类型的页面用于一些紧急的情况下的内存分分配。
  3. 如果前面的情况都不是,则调用__rmqueue()函数从伙伴系统中按照指定迁移类型的链表中去分配。
  4. 如果在指定迁移类型链表中仍然没有就尝试到其他迁移类型中取偷取。

具体的调用流程为:

1
2
3
4
5
rmqueue()--> if(order==0) --> rmqueue_pcplist()//分配单页的情况
|
--> if(alloc_flags & ALLOC_HARDER) --> __rmqueue_smallest()//进行高优先级分配
|
--> __rmqueue()//除了前面两种情况
4.4.2.2 rmqueue_pcplist()

order==0,分配冷热页,首先取出当前CPUpcp,根据迁移类型取出对应链表pcp->list,然后调用__rmqueue_pcplist函数分配。

1
2
3
2970         pcp = &this_cpu_ptr(zone->pageset)->pcp;
2971 list = &pcp->lists[migratetype];
2972 page = __rmqueue_pcplist(zone, migratetype, pcp, list);

__rmqueue_pcplist函数会判断传进来的指定类型的链表list是否为空,若为空,则从伙伴系统中分配一批放到pcp->lists[migratetype]中。

1
2
3
4
5
6
2943                 if (list_empty(list)) {
2944
//如果指定类型链表为空就从伙伴系统中分配一批(pcp->batch)放到pcp->lists[migratetype]中
2946 pcp->count += rmqueue_bulk(zone, 0,
2947 pcp->batch, list,
2948 migratetype);

然后从链表头中取一页,并将该页从pcp->lists[migratetype]中删除。

1
2
3
2953                 page = list_first_entry(list, struct page, lru);
2954 list_del(&page->lru);
2955 pcp->count--;
4.4.2.3 __rmqueue_smallest()

函数__rmqueue_smallest从指定迁移类型migratetype中去分配order阶的页块。如果order阶对应的链表没有空闲块就从更大阶的链表中去分配,将更大的页块拆解将剩余部分挂到对应order的链表中去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
1948 /*
1949 * Go through the free lists for the given migratetype and remove
1950 * the smallest available page from the freelists
1951 */
1952 static __always_inline
1953 struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
1954 int migratetype)
1955 {
1956 unsigned int current_order;
1957 struct free_area *area;
1958 struct page *page;
1959
1960 /* Find a page of the appropriate size in the preferred list
1961 *从指定阶到MAX_ORDER的伙伴链表中去查找迁移类型为migratetype的空闲页块*/
1962 for (current_order = order; current_order < MAX_ORDER; ++current_order) {
1963 area = &(zone->free_area[current_order]);//取order阶的free_area
1964 page = list_first_entry_or_null(&area->free_list[migratetype],
1965 struct page, lru);//取free_area中指定migratetype的页块
1966 if (!page)
1967 continue;//如果指定order的free_area->free_list[migratetype]为空,则从更大的阶的area取获取页块
1968 list_del(&page->lru);//将页块从对应阶的链表中删除
1969 rmv_page_order(page);//清楚伙伴系统标志,设置页阶为0
1970 area->nr_free--;//对应阶的free_area中的空闲块的数量减一
1971 //将current_order阶的页块拆成小块,并将小块放到对应的阶的链表中去
1972 expand(zone, page, order, current_order, area, migratetype);
1973 //设置页的迁移类型为page->index = migratetype
1974 set_pcppage_migratetype(page, migratetype);
1975 return page;
1976 }
1977
1978 return NULL;
1979 }
4.4.2.4 __rmqueue()

__rmqueue函数会首先调用__rmqueue_smallest函数从指定迁移类型中分配order阶的页块,在__rmqueue_smallest函数分配失败后,会尝试从伙伴系统的备选迁移类中盗取页。调用__rmqueue_smallest函数分配空闲页的逻辑在上面已经分析了,下面主要分析fallback过程。

在详细分析alloc_fallbacks函数之前,首先看一下备用迁移类型表,定义在mm/page_alloc.c文件中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1982 /*
1983 * This array describes the order lists are fallen back to when
1984 * the free lists for the desirable migrate type are depleted
1985 */
1986 static int fallbacks[MIGRATE_TYPES][4] = {
1987 [MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_TYPES },
1988 [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_TYPES },
1989 [MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES },
1990 #ifdef CONFIG_CMA
1991 [MIGRATE_CMA] = { MIGRATE_TYPES }, /* Never used */
1992 #endif
1993 #ifdef CONFIG_MEMORY_ISOLATION
1994 [MIGRATE_ISOLATE] = { MIGRATE_TYPES }, /* Never used */
1995 #endif
1996 };

这是一个二维数组,该数组描绘的是当指定迁移类型分配无法满足时,fallback时选择的迁移类型遍历的前后顺序。

__rmqueue_cma_fallback函数的处理根据编译选项而定,这里不做分析,具体分析__rmqueue_fallback函数。该函数的具体处理逻辑如下:

  • 循环取出fallbacks[migratetype][i]备用迁移类型,根据该信息和current_order去指定的列表寻找页块。
1
2
3
4
5
6
7
8
9
2397         for (current_order = MAX_ORDER - 1; current_order >= order;
2398 --current_order) {
2399 area = &(zone->free_area[current_order]);
2400 //循环取出fallbacks[migratetype][i]备用迁移类型,根据该信息和current_order尝试找出合适盗取页块,并返回迁移类型
2401 fallback_mt = find_suitable_fallback(area, current_order,
2402 start_migratetype, false, &can_steal);
2403 if (fallback_mt == -1)//如果没有找到合适的盗取页块,尝试下一个order
2404 continue;
2405

find_suitabl _fallback函数会根据参数current_orderstart_migratetype,首先判断current_orderarea是否有空闲页,若有空闲页,则根据start_migratetype迁移类型循环取出fallbacks[start_migratetype][i]数组中的备用迁移类型fallback_mt,并判断area->free_list[fallback_mt]是否有空闲块。并且判断是否可以进行页块盗取,若满足的条件1)order >= pageblock_order/2;2)迁移类型为MIGRATE_RECLAIMABLE;3)迁移类型为MIGRATE_UNMOVABLE,就可以进行盗取。

  • 当所请求的迁移类型为可移动时,最好的做法是窃取和拆分最小的可用页块而不是最大的可用页块,因为即使下次请求可移动页块fall back时不是这块页块时,也不会造成永久性碎片。
1
2
3
4
5
6
7
8
9
10
2423 find_smallest:
2424 for (current_order = order; current_order < MAX_ORDER;
2425 current_order++) {
2426 area = &(zone->free_area[current_order]);
2427 fallback_mt = find_suitable_fallback(area, current_order,
2428 start_migratetype, false, &can_steal);
2429 if (fallback_mt != -1)
2430 break;
2431 }
2432

从请求的页块的阶开始遍历当前zonefree_area,直到找到一个最小的可用页块。

  • 当找到合适的页块后,就会进行页块的盗取或借用。
1
2
3
4
5
6
2439 do_steal:
2440 page = list_first_entry(&area->free_list[fallback_mt],
2441 struct page, lru);
2442 //这里找到合适的页块,该函数会判断是直接盗取(改变整个页块的迁移类型)还是借用(仅分配但不改变页块迁移类型)
2443 steal_suitable_fallback(zone, page, start_migratetype, can_steal);
2444

4.4.3 慢分配 alloc_pages_slowpath

在快分配失败后,系统会尝试其他各种途径来分配到内存,alloc_pages_slowpath的具体实现步骤如下:

  1. 降低水准ALLOC_WMARK_MIN重新构建分配标志。如果设置了__GFP_KSWAPD_RECLAIM标志则唤醒kswaped进程进行页面回收。
  2. 调用get_page_from_freelist尝试重新分配.
  3. 前面的步骤没有分配到内存,并且order大于0,进行内存压缩和页的迁移,然后尝试内存分配。
  4. 前面的步骤没有分配到内存,如果设置了__GFP_KSWAPD_RECLAIM则唤醒kswaped进程,确保kswaped进程在循环中不会睡眠。
  5. 前面的步骤没有分配到内存,对gfp_mask分析看是否可以进行无水准分配。
  6. 前面的步骤没有分配到内存,在调整zonelistalloc_flags之后再次尝试分配。
  7. 前面的步骤没有分配到内存,直接进行内存回收之后尝试内存分配。
  8. 若内存回收没有分配到所需内存,就直接进行内存压缩之后尝试内存分配。
  9. 如果没有回收到足够的内存就尝试杀死一些进程然后尝试分配内存。
  10. 如果仍然没有分配到内存,分配标志中设置了__GFP_NOFAIL就设置ALLOC_HARDER尝试做内存分配

0x05 页框释放回收

释放页框的函数调用链如下:

1
2
3
4
5
6
7
8
free_pages()
--> __free_pages()
--> if (order == 0 )--> free_unref_page(0) // 释放单页
| --> free_unref_page_commit()
| --> 该页的pageblock的迁移类型不是CPU高速缓存类型,则返回伙伴系统 --> free_one_page()
| --> 放入CPU高速缓 ,默认为热页,如果缓存中页的数量大于pcp->high,则将pcp->batch数量的页返回伙伴系统 --> free_pcppages_bulk()
--> else --> __free_pages_ok()
--> free_one_page()//将页块放回伙伴系统,并且会尝试合并

函数free_pages()用于释放内存页,传入的参数是页虚拟地址和order,首先将page虚拟地址转换成页描述符,然后调用__free_pages()函数进一步处理。__free_pages()函数首先判断该页框是否还有进程在使用,即_count变量是否为0。如果没有进程在使用当前页框,则根据order值判断是释放的单页还是页块。

1
2
3
4
5
6
7
//判断是否还有进程在使用当前页框
if (put_page_testzero(page)) {
4476 if (order == 0)//释放单页
4477 free_unref_page(page);
4478 else
4479 __free_pages_ok(page, order);
4480 }

5.1 释放单页

free_unref_page_commit()函数中首先会获取该页框所在pageblock的迁移类型,根据得到的migratetype来判断是否属于CPU高速缓存,如果不是,则调用free_one_page放回伙伴系统。

1
2
3
4
5
6
7
2786         if (migratetype >= MIGRATE_PCPTYPES) {
2787 if (unlikely(is_migrate_isolate(migratetype))) {//如果不是CPU高速缓存类型,则放回伙伴系统
2788 free_one_page(zone, page, pfn, 0, migratetype);
2789 return;
2790 }
2791 migratetype = MIGRATE_MOVABLE;
2792 }

否则该页加入CPU高速缓存,默认为热页。

1
2
3
4
2793 //放入CPU高速缓存中,默认将当前页当成热页,放入相应迁移类型的链表的表头。如果是冷页,则会添加到链表尾
2794 pcp = &this_cpu_ptr(zone->pageset)->pcp;
2795 list_add(&page->lru, &pcp->lists[migratetype]);
2796 pcp->count++;

如果CPU高速缓存中的页数高于其最大值pcp->high,则会将pcp->batch数量的页放回伙伴系统。

1
2
3
4
2798         if (pcp->count >= pcp->high) {
2799 unsigned long batch = READ_ONCE(pcp->batch);
2800 free_pcppages_bulk(zone, batch, pcp);
2801 }

5.1.2 free_pcppages_bulk()

CPU高速缓存中的页数高于最大值时,要回收pcp->batch数量的页到伙伴系统。具体回收CPU高速缓存中的那些迁移类型列表的那些页,具体的实现逻辑在free_pcppages_bulk()函数,pcp lists中根据迁移类型不同有多个不同的链表,要释放pcp->batch数量的页到伙伴系统,该函数会根据迁移类型循环遍历pcp lists,每次取出一个非空的链表,释放batch_free数量的页,直到释放完了pcp->batch个页,具体代码逻辑:

1
2
3
4
5
6
1115                 do {
1116 batch_free++;
1117 if (++migratetype == MIGRATE_PCPTYPES)//MIGRATE_PCPTYPES == 3
1118 migratetype = 0;
1119 list = &pcp->lists[migratetype];
1120 } while (list_empty(list));

由代码可以看出,越后面的list释放的页越多,一次比前一个链表多释放一个页。
在前面已经选出的链表,循环释放batch_free个页。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
1126                 do {
1127 //取list的最后一个页
1128 page = list_last_entry(list, struct page, lru);
1129 /* must delete to avoid corrupting pcp list */
1130 list_del(&page->lru);//将该页从lru链表中删除
1131 pcp->count--;
1132 /* 在释放之前进行一些检查,会调用free_pages_check()函数
* 检测page的flag,maping,_count,_mapcount来判断是否可以释放*/
1133 if (bulkfree_pcp_prepare(page))
1134 continue;//如果不可以,则继续遍历下一页
1135 //将取出的页添加到head为链表头的list
1136 list_add_tail(&page->lru, &head);
1137
1138 /*
1139 * We are going to put the page back to the global
1140 * pool, prefetch its buddy to speed up later access
1141 * under zone->lock. It is believed the overhead of
1142 * an additional test and calculating buddy_pfn here
1143 * can be offset by reduced memory latency later. To
1144 * avoid excessive prefetching due to large count, only
1145 * prefetch buddy for the first pcp->batch nr of pages.
1146 */
1147 if (prefetch_nr++ < pcp->batch)
1148 prefetch_buddy(page);
1149 } while (--count && --batch_free && !list_empty(list));
1150 }

当遍历完pcp lists中的list,所有要放回到buddy系统的count个页框现在全部链接在以head为表头的list中,然后调用list_for_each_entry_safe宏将该list中的所有的页通过__free_one_page()函数放回到buddy系统中。

1
2
3
4
5
6
7
8
9
10
11
1160         list_for_each_entry_safe(page, tmp, &head, lru) {
1161 int mt = get_pcppage_migratetype(page);
1162 /* MIGRATE_ISOLATE page should not go to pcplists */
1163 VM_BUG_ON_PAGE(is_migrate_isolate(mt), page);
1164 /* Pageblock could have been isolated meanwhile */
1165 if (unlikely(isolated_pageblocks))
1166 mt = get_pageblock_migratetype(page);
1167
1168 __free_one_page(page, page_to_pfn(page), zone, 0, mt);
1169 trace_mm_page_pcpu_drain(page, 0, mt);
1170 }

5.1 释放多页

order大于0,回调用__free_pages_ok()函数来进行回收。

1
2
3
4
5
6
7
8
9
10
11
12
1266         unsigned long pfn = page_to_pfn(page);//获取页框号
1267 //各种检查
1268 if (!free_pages_prepare(page, order, true))
1269 return;
1270 //获取当前页框的迁移类型
1271 migratetype = get_pfnblock_migratetype(page, pfn);
1272 local_irq_save(flags);
1273 //统计当前CPU一共释放的页框数
1274 __count_vm_events(PGFREE, 1 << order);
1275 //释放页块
1276 free_one_page(page_zone(page), page, pfn, order, migratetype);
1277 local_irq_restore(flags);

在进行一些必要的检查之后,调用核心函数free_one_page()释放order阶个页框到buddy系统。并且回收的时候还会检查相邻页块是否空闲,如果空闲,会进行合并成大块,添加到相应阶的链表中,继续往后检查,直到检查到max_order-1的链表为止。具体逻辑__free_one_page()函数中。

5.2.1 __free_one_page()

5.2.1.1 pageblock

在内核中,内存被分成一小块一小块的,每个小块被称为一个pageblock,每个pageblock包含order阶个空闲页框,并且都属于同一类型。
详细分析TODO

0xFF Reference

https://blog.csdn.net/chenying126/article/details/78385364
http://www.ilinuxkernel.com
https://www.cnblogs.com/zhaoyl/p/3695517.html
https://www.jeanleo.com/2018/09/06/【linux内存源码分析】页面迁移/
https://github.com/gatieme/LDD-LinuxDeviceDrivers/blob/master/study/kernel/02-memory/01-description/01-memory/README.md
https://blog.csdn.net/YuZhiHui_No1/article/details/50776300
https://cloud.tencent.com/developer/article/1379737
分配掩码:https://github.com/gatieme/LDD-LinuxDeviceDrivers/tree/master/study/kernel/02-memory/04-buddy/05-free_page
https://www.cnblogs.com/tolimit/p/5287801.html
https://www.cnblogs.com/tolimit/p/4610974.html