0%

linux-memory

Linux的内存管理可谓是学好Linux的必经之路,也是Linux的关键知识点,有人说打通了内存管理的知识,也就打通了Linux的任督二脉,这一点不夸张。有人问网上有很多Linux内存管理的内容,为什么还要看你这一篇,这正是我写此文的原因,网上碎片化的相关知识点大都是东拼西凑,先不说正确性与否,就连基本的逻辑都没有搞清楚,我可以负责任的说Linux内存管理只需要看此文一篇就可以让你入Linux内核的大门,省去你东找西找的时间,让你形成内存管理知识的闭环。

文章比较长,做好准备,深呼吸,让我们一起打开Linux内核的大门!

Overview

1.1 UMA和NUMA两种模型
共享存储型多处理机有两种模型

均匀存储器存取(Uniform-Memory-Access,简称UMA)模型

非均匀存储器存取(Nonuniform-Memory-Access,简称NUMA)模型

UMA模型

物理存储器被所有处理机均匀共享。所有处理机对所有存储字具有相同的存取时间,这就是为什么称它为均匀存储器存取的原因。每台处理机可以有私用高速缓存,外围设备也以一定形式共享。

NUMA模型

NUMA模式下,处理器被划分成多个”节点”(node), 每个节点被分配有的本地存储器空间。 所有节点中的处理器都可以访问全部的系统物理存储器,但是访问本节点内的存储器所需要的时间,比访问某些远程节点内的存储器所花的时间要少得多。

1.2 (N)UMA模型中linux内存的机构
非一致存储器访问(NUMA)模式下

处理器被划分成多个”节点”(node), 每个节点被分配有的本地存储器空间. 所有节点中的处理器都可以访问全部的系统物理存储器,但是访问本节点内的存储器所需要的时间,比访问某些远程节点内的存储器所花的时间要少得多

内存被分割成多个区域(BANK,也叫”簇”),依据簇与处理器的”距离”不同, 访问不同簇的代码也会不同. 比如,可能把内存的一个簇指派给每个处理器,或则某个簇和设备卡很近,很适合DMA,那么就指派给该设备。因此当前的多数系统会把内存系统分割成2块区域,一块是专门给CPU去访问,一块是给外围设备板卡的DMA去访问

在UMA系统中, 内存就相当于一个只使用一个NUMA节点来管理整个系统的内存. 而内存管理的其他地方则认为他们就是在处理一个(伪)NUMA系统.

Linux把物理内存划分为三个层次来管理

层次 描述
存储节点(Node) CPU被划分为多个节点(node), 内存则被分簇, 每个CPU对应一个本地物理内存, 即一个CPU-node对应一个内存簇bank,即每个内存簇被认为是一个节点
管理区(Zone) 每个物理内存节点node被划分为多个内存管理区域, 用于表示不同范围的内存, 内核可以使用不同的映射方式映射物理内存
页面(Page) 内存被细分为多个页面帧, 页面是最基本的页面分配的单位 |
2 内存节点node
2.1 为什么要用node来描述内存
这点前面是说的很明白了, NUMA结构下, 每个处理器CPU与一个本地内存直接相连, 而不同处理器之前则通过总线进行进一步的连接, 因此相对于任何一个CPU访问本地内存的速度比访问远程内存的速度要快

Linux适用于各种不同的体系结构, 而不同体系结构在内存管理方面的差别很大. 因此linux内核需要用一种体系结构无关的方式来表示内存.

因此linux内核把物理内存按照CPU节点划分为不同的node, 每个node作为某个cpu结点的本地内存, 而作为其他CPU节点的远程内存, 而UMA结构下, 则任务系统中只存在一个内存node, 这样对于UMA结构来说, 内核把内存当成只有一个内存node节点的伪NUMA

2.2 内存结点的概念
CPU被划分为多个节点(node), 内存则被分簇, 每个CPU对应一个本地物理内存, 即一个CPU-node对应一个内存簇bank,即每个内存簇被认为是一个节点

系统的物理内存被划分为几个节点(node), 一个node对应一个内存簇bank,即每个内存簇被认为是一个节点

内存被划分为结点. 每个节点关联到系统中的一个处理器, 内核中表示为pg_data_t的实例. 系统中每个节点被链接到一个以NULL结尾的pgdat_list链表中<而其中的每个节点利用pg_data_tnode_next字段链接到下一节.而对于PC这种UMA结构的机器来说, 只使用了一个成为contig_page_data的静态pg_data_t结构.

内存中的每个节点都是由pg_data_t描述,而pg_data_t由struct pglist_data定义而来, 该数据结构定义在include/linux/mmzone.h, line 615

在分配一个页面时, Linux采用节点局部分配的策略, 从最靠近运行中的CPU的节点分配内存, 由于进程往往是在同一个CPU上运行, 因此从当前节点得到的内存很可能被用到

2.3 pg_data_t描述内存节点
表示node的数据结构为typedef struct pglist_data pg_data_t, 这个结构定义在include/linux/mmzone.h, line 615中,结构体的内容如下

/*

  • The pg_data_t structure is used in machines with CONFIG_DISCONTIGMEM
  • (mostly NUMA machines?) to denote a higher-level memory zone than the
  • zone denotes.
    *
  • On NUMA machines, each NUMA node would have a pg_data_t to describe
  • it’s memory layout.
    *
  • Memory statistics and page replacement data structures are maintained on a
  • per-zone basis.
    /
    struct bootmem_data;
    typedef struct pglist_data {
    /
    包含了结点中各内存域的数据结构 , 可能的区域类型用zone_type表示/
    struct zone node_zones[MAX_NR_ZONES];
    /
    指点了备用结点及其内存域的列表,以便在当前结点没有可用空间时,在备用结点分配内存 /
    struct zonelist node_zonelists[MAX_ZONELISTS];
    int nr_zones; /
    保存结点中不同内存域的数目 */

    ifdef CONFIG_FLAT_NODE_MEM_MAP / means !SPARSEMEM /

    struct page node_mem_map; / 指向page实例数组的指针,用于描述结点的所有物理内存页,它包含了结点中所有内存域的页。 */

    ifdef CONFIG_PAGE_EXTENSION

    struct page_ext *node_page_ext;

    endif

    endif

    ifndef CONFIG_NO_BOOTMEM

    /*  在系统启动boot期间,内存管理子系统初始化之前,
    内核页需要使用内存(另外,还需要保留部分内存用于初始化内存管理子系统)
    为解决这个问题,内核使用了自举内存分配器 
    此结构用于这个阶段的内存管理  */
    
    struct bootmem_data *bdata;

    endif

    ifdef CONFIG_MEMORY_HOTPLUG

    /*
    • Must be held any time you expect node_start_pfn, node_present_pages
    • or node_spanned_pages stay constant. Holding this will also
    • guarantee that any pfn_valid() stays that way.
      *
    • pgdat_resize_lock() and pgdat_resize_unlock() are provided to
    • manipulate node_size_lock without checking for CONFIG_MEMORY_HOTPLUG.
      *
    • Nests above zone->lock and zone->span_seqlock
    • 当系统支持内存热插拨时,用于保护本结构中的与节点大小相关的字段。
    • 哪调用node_start_pfn,node_present_pages,node_spanned_pages相关的代码时,需要使用该锁。
      */
      spinlock_t node_size_lock;

      endif

      / /起始页面帧号,指出该节点在全局mem_map中的偏移
      系统中所有的页帧是依次编号的,每个页帧的号码都是全局唯一的(不只是结点内唯一) /
      unsigned long node_start_pfn;
      unsigned long node_present_pages; /
      total number of physical pages 结点中页帧的数目 /
      unsigned long node_spanned_pages; /
      total size of physical page range, including holes 该结点以页帧为单位计算的长度,包含内存空洞 /
      int node_id; /
      全局结点ID,系统中的NUMA结点都从0开始编号 /
      wait_queue_head_t kswapd_wait; /
      交换守护进程的等待队列,
      在将页帧换出结点时会用到。后面的文章会详细讨论。 /
      wait_queue_head_t pfmemalloc_wait;
      struct task_struct
      kswapd; / Protected by mem_hotplug_begin/end() 指向负责该结点的交换守护进程的task_struct。 /
      int kswapd_max_order; / 定义需要释放的区域的长度 /
      enum zone_type classzone_idx;

ifdef CONFIG_COMPACTION

int kcompactd_max_order;
enum zone_type kcompactd_classzone_idx;
wait_queue_head_t kcompactd_wait;
struct task_struct *kcompactd;

endif

ifdef CONFIG_NUMA_BALANCING

/* Lock serializing the migrate rate limiting window */
spinlock_t numabalancing_migrate_lock;

/* Rate limiting time interval */
unsigned long numabalancing_migrate_next_window;

/* Number of pages migrated during the rate limiting time interval */
unsigned long numabalancing_migrate_nr_pages;

endif

ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT

/*
 * If memory initialisation on large machines is deferred then this
 * is the first PFN that needs to be initialised.
 */
unsigned long first_deferred_pfn;

endif / CONFIG_DEFERRED_STRUCT_PAGE_INIT /

ifdef CONFIG_TRANSPARENT_HUGEPAGE

spinlock_t split_queue_lock;
struct list_head split_queue;
unsigned long split_queue_len;

endif

} pg_data_t;
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
字段 描述
node_zones 每个Node划分为不同的zone,分别为ZONE_DMA,ZONE_NORMAL,ZONE_HIGHMEM
node_zonelists 这个是备用节点及其内存域的列表,当当前节点的内存不够分配时,会选取访问代价最低的内存进行分配。分配内存操作时的区域顺序,当调用free_area_init_core()时,由mm/page_alloc.c文件中的build_zonelists()函数设置
nr_zones 当前节点中不同内存域zone的数量,1到3个之间。并不是所有的node都有3个zone的,比如一个CPU簇就可能没有ZONE_DMA区域
node_mem_map node中的第一个page,它可以指向mem_map中的任何一个page,指向page实例数组的指针,用于描述该节点所拥有的的物理内存页,它包含了该页面所有的内存页,被放置在全局mem_map数组中
bdata 这个仅用于引导程序boot 的内存分配,内存在启动时,也需要使用内存,在这里内存使用了自举内存分配器,这里bdata是指向内存自举分配器的数据结构的实例
node_start_pfn pfn是page frame number的缩写。这个成员是用于表示node中的开始那个page在物理内存中的位置的。是当前NUMA节点的第一个页帧的编号,系统中所有的页帧是依次进行编号的,这个字段代表的是当前节点的页帧的起始值,对于UMA系统,只有一个节点,所以该值总是0
node_present_pages node中的真正可以使用的page数量
node_spanned_pages 该节点以页帧为单位的总长度,这个不等于前面的node_present_pages,因为这里面包含空洞内存
node_id node的NODE ID 当前节点在系统中的编号,从0开始
kswapd_wait node的等待队列,交换守护列队进程的等待列表
kswapd_max_order 需要释放的区域的长度,以页阶为单位
classzone_idx 这个字段暂时没弄明白,不过其中的zone_type是对ZONE_DMA,ZONE_DMA32,ZONE_NORMAL,ZONE_HIGH,ZONE_MOVABLE,__MAX_NR_ZONES的枚举
2.5 结点的内存管理域
typedef struct pglist_data {
/ 包含了结点中各内存域的数据结构 , 可能的区域类型用zone_type表示/
struct zone node_zones[MAX_NR_ZONES];
/ 指点了备用结点及其内存域的列表,以便在当前结点没有可用空间时,在备用结点分配内存 /
struct zonelist node_zonelists[MAX_ZONELISTS];
int nr_zones; / 保存结点中不同内存域的数目 /

} pg_data_t;
1
2
3
4
5
6
7
8
node_zones[MAX_NR_ZONES]数组保存了节点中各个内存域的数据结构,

而node_zonelist则指定了备用节点以及其内存域的列表, 以便在当前结点没有可用空间时, 在备用节点分配内存.

nr_zones存储了结点中不同内存域的数目

2.6 结点的内存页面
typedef struct pglist_data
{
struct page node_mem_map; / 指向page实例数组的指针,用于描述结点的所有物理内存页,它包含了结点中所有内存域的页。 */

/* /*起始页面帧号,指出该节点在全局mem_map中的偏移
系统中所有的页帧是依次编号的,每个页帧的号码都是全局唯一的(不只是结点内唯一)  */
unsigned long node_start_pfn;
unsigned long node_present_pages; /* total number of physical pages 结点中页帧的数目 */
unsigned long node_spanned_pages; /* total size of physical page range, including holes                     该结点以页帧为单位计算的长度,包含内存空洞 */
int node_id;        /*  全局结点ID,系统中的NUMA结点都从0开始编号  */

} pg_data_t;
1
2
3
4
5
6
7
8
9
10
11
其中node_mem_map是指向页面page实例数组的指针, 用于描述结点的所有物理内存页. 它包含了结点中所有内存域的页.

node_start_pfn是该NUMA结点的第一个页帧的逻辑编号. 系统中所有的节点的页帧是一次编号的, 每个页帧的编号是全局唯一的. node_start_pfn在UMA系统中总是0, 因为系统中只有一个内存结点, 因此其第一个页帧编号总是0.

node_present_pages指定了结点中页帧的数目, 而node_spanned_pages则给出了该结点以页帧为单位计算的长度. 二者的值不一定相同, 因为结点中可能有一些空洞, 并不对应真正的页帧.

2.7 交换守护进程
typedef struct pglist_data
{
wait_queue_head_t kswapd_wait; / 交换守护进程的等待队列,
在将页帧换出结点时会用到。后面的文章会详细讨论。
/
wait_queue_head_t pfmemalloc_wait;
struct task_struct kswapd; / Protected by mem_hotplug_begin/end() 指向负责该结点的交换守护进程的task_struct。 */
};
1
2
3
4
5
6
7
kswapd指向了负责将该结点的交换守护进程的task_struct. 在将页帧换出结点时会唤醒该进程.

kswap_wait是交换守护进程(swap daemon)的等待队列

而kswapd_max_order用于页交换子系统的实现, 用来定义需要释放的区域的长度.

3 结点状态
3.1 结点状态标识node_states
内核用enum node_state变量标记了内存结点所有可能的状态信息, 其定义在include/linux/nodemask.h?v=4.7, line 381

enum node_states {
N_POSSIBLE, / The node could become online at some point
结点在某个时候可能变成联机
/
N_ONLINE, / The node is online
节点是联机的
/
N_NORMAL_MEMORY, / The node has regular memory
结点是普通内存域
/

ifdef CONFIG_HIGHMEM

N_HIGH_MEMORY,      /* The node has regular or high memory 
                       结点是普通或者高端内存域*/

else

N_HIGH_MEMORY = N_NORMAL_MEMORY,

endif

ifdef CONFIG_MOVABLE_NODE

N_MEMORY,           /* The node has memory(regular, high, movable) */

else

N_MEMORY = N_HIGH_MEMORY,

endif

N_CPU,      /* The node has one or more cpus */
NR_NODE_STATES

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
状态 描述
N_POSSIBLE 结点在某个时候可能变成联机
N_ONLINE 节点是联机的
N_NORMAL_MEMORY 结点是普通内存域
N_HIGH_MEMORY 结点是普通或者高端内存域
N_MEMORY 结点是普通,高端内存或者MOVEABLE域
N_CPU 结点有一个或多个CPU
其中N_POSSIBLE, N_ONLINE和N_CPU用于CPU和内存的热插拔.

对内存管理有必要的标志是N_HIGH_MEMORY和N_NORMAL_MEMORY, 如果结点有普通或高端内存则使用N_HIGH_MEMORY, 仅当结点没有高端内存时才设置N_NORMAL_MEMORY

N_NORMAL_MEMORY,    /* The node has regular memory
                        结点是普通内存域 */

ifdef CONFIG_HIGHMEM

N_HIGH_MEMORY,      /* The node has regular or high memory 
                       结点是高端内存域*/

else

/*  没有高端内存域, 仍设置N_NORMAL_MEMORY  */
N_HIGH_MEMORY = N_NORMAL_MEMORY,

endif

1
2
3
4
5
6
7
8
9
同样ZONE_MOVABLE内存域同样用类似的方法设置, 仅当系统中存在ZONE_MOVABLE内存域内存域(配置了CONFIG_MOVABLE_NODE参数)时, N_MEMORY才被设定, 否则则被设定成N_HIGH_MEMORY, 而N_HIGH_MEMORY设定与否同样依赖于参数CONFIG_HIGHMEM的设定

ifdef CONFIG_MOVABLE_NODE

N_MEMORY,           /* The node has memory(regular, high, movable) */

else

N_MEMORY = N_HIGH_MEMORY,

endif

1
2
3
4
5
3.2 结点状态设置函数
内核提供了辅助函数来设置或者清楚位域活特定结点的一个比特位

static inline int node_state(int node, enum node_states state)
static inline void node_set_state(int node, enum node_states state)
static inline void node_clear_state(int node, enum node_states state)
static inline int num_node_state(enum node_states state)
1
2
3
4
此外宏for_each_node_state(node, state)用来迭代处于特定状态的所有结点,

define for_each_node_state(node, state) \

    for_each_node_mask((__node), node_states[__state])

1
2
而for_each_online_node(node)则负责迭代所有的活动结点.

如果内核编译只支持当个结点(即使用平坦内存模型), 则没有结点位图, 上述操作该位图的函数则变成空操作, 其定义形式如下, 参见include/linux/nodemask.h?v=4.7, line 406

参见内核

if MAX_NUMNODES > 1

/*   some real function  */

else

/*  some NULL function  */

endif

1
2
3
4
5
4 查找内存结点
node_id作为全局节点id。 系统中的NUMA结点都是从0开始编号的

4.1 linux-2.4中的实现
pgdat_next指针域和pgdat_list内存结点链表

而对于NUMA结构的系统中, 在linux-2.4.x之前的内核中所有的节点,内存结点pg_data_t都有一个next指针域pgdat_next指向下一个内存结点. 这样一来系统中所有结点都通过单链表pgdat_list链接起来, 其末尾是一个NULL指针标记.

这些节点都放在该链表中,均由函数init_bootmem_core()初始化结点

for_each_pgdat(pgdat)来遍历node节点

那么内核提供了宏函数for_each_pgdat(pgdat)来遍历node节点, 其只需要沿着node_next以此便立即可, 参照include/linux/mmzone.h?v=2.4.37, line 187

/**

  • for_each_pgdat - helper macro to iterate over nodes
  • @pgdat - pg_data_t * variable
  • Meant to help with common loops of the form
  • pgdat = pgdat_list;
  • while(pgdat) {
  • pgdat = pgdat->node_next;
  • }
    */

    define for_each_pgdat(pgdat) \

     for (pgdat = pgdat_list; pgdat; pgdat = pgdat->node_next)
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    4.2 linux-3.x~4.x的实现
    node_data内存节点数组

在新的linux3.x~linux4.x的内核中,内核移除了pg_data_t的pgdat_next之指针域, 同时也删除了pgdat_list链表, 参见Remove pgdat list和Remove pgdat list ver.2

但是定义了一个大小为MAX_NUMNODES类型为pg_data_t数组node_data,数组的大小根据CONFIG_NODES_SHIFT的配置决定. 对于UMA来说,NODES_SHIFT为0,所以MAX_NUMNODES的值为1.

for_each_online_pgdat遍历所有的内存结点

内核提供了for_each_online_pgdatfor_each_online_pgdat(pgdat)来遍历节点

/**

  • for_each_online_pgdat - helper macro to iterate over all online nodes
  • @pgdat - pointer to a pg_data_t variable
    */

    define for_each_online_pgdat(pgdat) \

     for (pgdat = first_online_pgdat();              \
          pgdat;                                     \
          pgdat = next_online_pgdat(pgdat))
    
    1
    2
    3
    4
    5
    6
    7
    8
    其中first_online_pgdat可以查找到系统中第一个内存节点的pg_data_t信息, next_online_pgdat则查找下一个内存节点.

下面我们来看看first_online_pgdat和next_online_pgdat是怎么实现的.

first_online_node和next_online_node返回结点编号

由于没了next指针域pgdat_next和全局node链表pgdat_list, 因而内核提供了first_online_node指向第一个内存结点, 而通过next_online_node来查找其下一个结点, 他们是通过状态node_states的位图来查找结点信息的, 定义在include/linux/nodemask.h?v4.7, line 432

// http://lxr.free-electrons.com/source/include/linux/nodemask.h?v4.7#L432

define first_online_node first_node(node_states[N_ONLINE])

define first_memory_node first_node(node_states[N_MEMORY])

static inline int next_online_node(int nid)
{
return next_node(nid, node_states[N_ONLINE]);
}
1
2
3
4
5
6
7
first_online_node和next_online_node返回所查找的node结点的编号, 而有了编号, 我们直接去node_data数组中按照编号进行索引即可去除对应的pg_data_t的信息.内核提供了NODE_DATA(node_id)宏函数来按照编号来查找对应的结点, 它的工作其实其实就是从node_data数组中进行索引

NODE_DATA(node_id)查找编号node_id的结点pg_data_t信息

移除了pg_data_t->pgdat_next指针域. 但是所有的node都存储在node_data数组中, 内核提供了函数NODE_DATA直接通过node编号索引节点pg_data_t信息, 参见NODE_DATA的定义

extern struct pglist_data *node_data[];

define NODE_DATA(nid) (node_data[(nid)])

1
2
在UMA结构的机器中, 只有一个node结点即contig_page_data, 此时NODE_DATA直接指向了全局的contig_page_data, 而与node的编号nid无关, 参照include/linux/mmzone.h?v=4.7, line 858, 其中全局唯一的内存node结点contig_page_data定义在mm/nobootmem.c?v=4.7, line 27, linux-2.4.37

ifndef CONFIG_NEED_MULTIPLE_NODES

extern struct pglist_data contig_page_data;

define NODE_DATA(nid) (&contig_page_data)

define NODE_MEM_MAP(nid) mem_map

else
/ …… /

endif

1
2
3
4
5
6
7
first_online_pgdat和next_online_pgdat返回结点的pg_data_t

首先通过first_online_node和next_online_node找到节点的编号

然后通过NODE_DATA(node_id)查找到对应编号的结点的pg_data_t信息

struct pglist_data *first_online_pgdat(void)
{
return NODE_DATA(first_online_node);
}

struct pglist_data next_online_pgdat(struct pglist_data pgdat)
{
int nid = next_online_node(pgdat->node_id);

if (nid == MAX_NUMNODES)
    return NULL;
return NODE_DATA(nid);

}

Node

Zone

Page

Highmem

本文内容主要来自ilinuxkernel.com,并对该部分内容进行了扩充。

下图展示的部分内容包含了本文的知识点,值得细细分析。
img

Linux内核地址空间划分

通常32位Linux进程地址空间划分0~3G为用户空间,3~4G为空间。注意这里是32位进程地址空间划分,64位进程地址空间划分是不同的。
img

Linux内核高端内存的由来

当内核模块代码或线程访问内存时,代码中的内存地址都为逻辑地址,而对应到真正的物理内存地址,需要地址一对一的映射,如逻辑地址0xc0000003对应的物理地址为0x3,0xc0000004对应的物理地址为0x4,… …,逻辑地址与物理地址对应的关系为:
物理地址 = 逻辑地址 – 0xC0000000

假设按照上述简单的地址映射关系,那么内核逻辑地址空间访问为0xc0000000 ~ 0xffffffff,那么对应的物理内存范围就为0x0 ~ 0x40000000,即只能访问1G物理内存。若机器中安装8G物理内存,那么内核就只能访问前1G物理内存,后面7G物理内存将会无法访问,因为内核的地址空间已经全部映射到物理内存地址范围0x0 ~ 0x40000000。即使安装了8G物理内存,那么物理地址为0x40000001的内存,内核该怎么去访问呢?代码中必须要有内存逻辑地址的,0xc0000000 ~ 0xffffffff的地址空间已经被用完了,所以无法访问物理地址0x40000000以后的内存。

显然不能将内核地址空间0xc0000000 ~ 0xfffffff全部用来简单的地址映射。x86架构中将物理地址空间划分三部分:ZONE_DMA、ZONE_NORMAL和ZONE_HIGHMEM。ZONE_HIGHMEM即为高端内存,这就是高端内存概念的由来。

在x86结构中,三种类型的区域如下:

  • ZONE_DMA 物理内存开始的16MB
  • ZONE_NORMAL 物理内存的16MB~896MB
  • ZONE_HIGHMEM 物理内存的896MB ~ 结束

img

Linux内核高端内存的理解

前面我们解释了高端内存的由来。 Linux将物理地址空间划分为三部分ZONE_DMA、ZONE_NORMAL和ZONE_HIGHMEM,高端内存HIGH_MEM地址空间映射的内核线性地址范围为0xF8000000 ~ 0xFFFFFFFF(896MB~1024MB)。

当内核想访问高于896MB物理地址内存时,从0xF8000000 ~ 0xFFFFFFFF地址空间范围内找一段相应大小空闲的逻辑地址空间,借用一会。借用这段逻辑地址空间,建立映射到想访问的那段物理内存(即填充内核页表),临时用一会,用完后归还。这样别人也可以借用这段地址空间访问其他物理内存,实现了使用有限的地址空间,访问所有所有物理内存。如下图:
img

例如内核想访问2G开始的一段大小为1MB的物理内存,即物理地址范围为0x80000000 ~ 0x800FFFFF。访问之前先找到一段1MB大小的空闲地址空间,假设找到的空闲地址空间为0xF8700000 ~ 0xF87FFFFF,用这1MB的逻辑地址空间映射到物理地址空间0x80000000 ~ 0x800FFFFF的内存。

当内核访问完0x80000000 ~ 0x800FFFFF物理内存后,就将0xF8700000 ~ 0xF87FFFFF内核线性空间释放。这样其他进程或代码也可以使用0xF8700000 ~ 0xF87FFFFF这段地址访问其他物理内存。

从上面的描述,我们可以知道高端内存的最基本思想:借一段地址空间,建立临时地址映射,用完后释放,达到这段地址空间可以循环使用,访问所有物理内存。

高端内存的映射

0xF8000000 ~ 0xFFFFFFFF(896MB~1024MB)的128MB内核线性地址空间被划分为3部分:VMALLOC_START~VMALLOC_END、KMAP_BASE~FIXADDR_START和FIXADDR_START~4G。

img

对于高端内存,可以通过 alloc_page() 或者其它函数获得对应的 page,但是要想访问实际物理内存,还得把 page 转为线性地址才行,也就是说,我们需要为高端内存对应的 page 找一个线性空间,这个过程称为高端内存映射。

对应128MB内核线性地址空间的3部分,高端内存映射有三种方式:

  • 映射到”内核动态映射空间”(noncontiguous memory allocation)

这种方式很简单,因为通过 vmalloc() ,在”内核动态映射空间”申请内存的时候,就从高端内存获得页面,因此说高端内存有可能映射到”内核动态映射空间”中。

  • 持久内核映射(permanent kernel mapping)

内核专门留出一块线性空间,从 PKMAP_BASE 到 FIXADDR_START ,用于映射高端内存。在 2.6内核上,这个地址范围是 4G-8M 到 4G-4M 之间。这个空间叫”持久内核映射空间”。通过kmap(),可以把一个 page 映射到这个空间来。因为允许永久映射的数量有限,当不再需要高端内存时,应该解除映射,这可以通过kunmap()函数来完成。

  • 临时映射(temporary kernel mapping)

内核在 FIXADDR_START 到 FIXADDR_TOP(4GB)之间保留了一些线性空间用于特殊需求。这个空间称为”固定映射空间”,在这个空间中,有一部分用于高端内存的临时映射。
这个空间具有如下特点:

  1. 每个 CPU 占用一块空间
  2. 在每个 CPU 占用的那块空间中,又分为多个小空间,每个小空间大小是 1 个 page,每个小空间用于一个目的,这些目的定义在 kmap_types.h 中的 km_type 中。

当要进行一次临时映射的时候,需要指定映射的目的,根据映射目的,可以找到对应的小空间,然后把这个空间的地址作为映射地址。这意味着一次临时映射会导致以前的映射被覆盖。通过kmap_atomic()可实现临时映射。

常见问题

\1. 用户空间是否有高端内存概念?

用户空间没有高端内存概念,只有内核空间才存在高端内存。

\2. 64位内核中有高端内存吗?

目前现实中,64位Linux内核不存在高端内存,因为64位内核可以支持超过512GB内存。若机器安装的物理内存超过内核地址空间范围,就会存在高端内存。

\3. 高端内存和物理地址、线性地址的关系?

高端内存只和物理地址有关系,和线性地址没有直接关系。

Paging

Evolve

PTE

Bootmem

Memblock

Paging_init

CPU访问内存的过程

我喜欢用图的方式来说明问题,简单直接:

图片

蓝色部分是cpu,灰色部分是内存,白色部分就是cpu访问内存的过程,也是地址转换的过程。在解释地址转换的本质前我们先理解下几个概念:

  1. TLB:MMU工作的过程就是查询页表的过程。如果把页表放在内存中查询的时候开销太大,因此为了提高查找效率,专门用一小片访问更快的区域存放地址转换条目。(当页表内容有变化的时候,需要清除TLB,以防止地址映射出错。)
  2. Caches:cpu和内存之间的缓存机制,用于提高访问速率,armv8架构的话上图的caches其实是L2 Cache,这里就不做进一步解释了。

虚拟地址转换为物理地址的本质

我们知道内核中的寻址空间大小是由CONFIG_ARM64_VA_BITS控制的,这里以48位为例,ARMv8中,Kernel Space的页表基地址存放在TTBR1_EL1寄存器中,User Space页表基地址存放在TTBR0_EL0寄存器中,其中内核地址空间的高位为全1,(0xFFFF0000_00000000 ~ 0xFFFFFFFF_FFFFFFFF),用户地址空间的高位为全0,(0x00000000_00000000 ~ 0x0000FFFF_FFFFFFFF)

图片

有了宏观概念,下面我们以内核态寻址过程为例看下是如何把虚拟地址转换为物理地址的。

我们知道linux采用了分页机制,通常采用四级页表,页全局目录(PGD),页上级目录(PUD),页中间目录(PMD),页表(PTE)。如下:

图片

  1. 从CR3寄存器中读取页目录所在物理页面的基址(即所谓的页目录基址),从线性地址的第一部分获取页目录项的索引,两者相加得到页目录项的物理地址。
  2. 第一次读取内存得到pgd_t结构的目录项,从中取出物理页基址取出,即页上级页目录的物理基地址。
  3. 从线性地址的第二部分中取出页上级目录项的索引,与页上级目录基地址相加得到页上级目录项的物理地址。
  4. 第二次读取内存得到pud_t结构的目录项,从中取出页中间目录的物理基地址。
  5. 从线性地址的第三部分中取出页中间目录项的索引,与页中间目录基址相加得到页中间目录项的物理地址。
  6. 第三次读取内存得到pmd_t结构的目录项,从中取出页表的物理基地址。
  7. 从线性地址的第四部分中取出页表项的索引,与页表基址相加得到页表项的物理地址。
  8. 第四次读取内存得到pte_t结构的目录项,从中取出物理页的基地址。
  9. 从线性地址的第五部分中取出物理页内偏移量,与物理页基址相加得到最终的物理地址。
  10. 第五次读取内存得到最终要访问的数据。

整个过程是比较机械的,每次转换先获取物理页基地址,再从线性地址中获取索引,合成物理地址后再访问内存。不管是页表还是要访问的数据都是以页为单位存放在主存中的,因此每次访问内存时都要先获得基址,再通过索引(或偏移)在页内访问数据,因此可以将线性地址看作是若干个索引的集合。

Linux内存初始化

有了armv8架构访问内存的理解,我们来看下linux在内存这块的初始化就更容易理解了。

创建启动页表:

在汇编代码阶段的head.S文件中,负责创建映射关系的函数是create_page_tables。create_page_tables函数负责identity mapping和kernel image mapping。

  • identity map:是指把idmap_text区域的物理地址映射到相等的虚拟地址上,这种映射完成后,其虚拟地址等于物理地址。idmap_text区域都是一些打开MMU相关的代码。
  • kernel image map:将kernel运行需要的地址(kernel txt、rodata、data、bss等等)进行映射。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
arch/arm64/kernel/head.S:
ENTRY(stext)
bl preserve_boot_args
bl el2_setup // Drop to EL1, w0=cpu_boot_mode
adrp x23, __PHYS_OFFSET
and x23, x23, MIN_KIMG_ALIGN - 1 // KASLR offset, defaults to 0
bl set_cpu_boot_mode_flag
bl __create_page_tables
/*
* The following calls CPU setup code, see arch/arm64/mm/proc.S for
* details.
* On return, the CPU will be ready for the MMU to be turned on and
* the TCR will have been set.
*/
bl __cpu_setup // initialise processor
b __primary_switch
ENDPROC(stext)

__create_page_tables主要执行的就是identity map和kernel image map:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 __create_page_tables:
......
create_pgd_entry x0, x3, x5, x6
mov x5, x3 // __pa(__idmap_text_start)
adr_l x6, __idmap_text_end // __pa(__idmap_text_end)
create_block_map x0, x7, x3, x5, x6

/*
* Map the kernel image (starting with PHYS_OFFSET).
*/
adrp x0, swapper_pg_dir
mov_q x5, KIMAGE_VADDR + TEXT_OFFSET // compile time __va(_text)
add x5, x5, x23 // add KASLR displacement
create_pgd_entry x0, x5, x3, x6
adrp x6, _end // runtime __pa(_end)
adrp x3, _text // runtime __pa(_text)
sub x6, x6, x3 // _end - _text
add x6, x6, x5 // runtime __va(_end)
create_block_map x0, x7, x3, x5, x6
......

其中调用create_pgd_entry进行PGD及所有中间level(PUD, PMD)页表的创建,调用create_block_map进行PTE页表的映射。关于四级页表的关系如下图所示,这里就不进一步解释了。

汇编结束后的内存映射关系如下图所示:

图片

等内存初始化后就可以进入真正的内存管理了,初始化我总结了一下,大体分为四步:

  1. 物理内存进系统前
  2. 用memblock模块来对内存进行管理
  3. 页表映射
  4. zone初始化

Linux是如何组织物理内存的?

  • node 目前计算机系统有两种体系结构:
  1. 非一致性内存访问 NUMA(Non-Uniform Memory Access)意思是内存被划分为各个node,访问一个node花费的时间取决于CPU离这个node的距离。每一个cpu内部有一个本地的node,访问本地node时间比访问其他node的速度快
  2. 一致性内存访问 UMA(Uniform Memory Access)也可以称为SMP(Symmetric Multi-Process)对称多处理器。意思是所有的处理器访问内存花费的时间是一样的。也可以理解整个内存只有一个node。
  • zone

ZONE的意思是把整个物理内存划分为几个区域,每个区域有特殊的含义

  • page

代表一个物理页,在内核中一个物理页用一个struct page表示。

  • page frame

为了描述一个物理page,内核使用struct page结构来表示一个物理页。假设一个page的大小是4K的,内核会将整个物理内存分割成一个一个4K大小的物理页,而4K大小物理页的区域我们称为page frame

图片

  • page frame num(pfn)

pfn是对每个page frame的编号。故物理地址和pfn的关系是:

物理地址>>PAGE_SHIFT = pfn

  • pfn和page的关系

内核中支持了好几个内存模型:CONFIG_FLATMEM(平坦内存模型)CONFIG_DISCONTIGMEM(不连续内存模型)CONFIG_SPARSEMEM_VMEMMAP(稀疏的内存模型)目前ARM64使用的稀疏的类型模式。

系统启动的时候,内核会将整个struct page映射到内核虚拟地址空间vmemmap的区域,所以我们可以简单的认为struct page的基地址是vmemmap,则:

vmemmap+pfn的地址就是此struct page对应的地址。

zoned page frame allocator

页框分配在内核里的机制我们叫做分区页框分配器(zoned page frame allocator),在linux系统中,分区页框分配器管理着所有物理内存,无论你是内核还是进程,都需要请求分区页框分配器,这时才会分配给你应该获得的物理内存页框。当你所拥有的页框不再使用时,你必须释放这些页框,让这些页框回到管理区页框分配器当中。

有时候目标管理区不一定有足够的页框去满足分配,这时候系统会从另外两个管理区中获取要求的页框,但这是按照一定规则去执行的,如下:

  • 如果要求从DMA区中获取,就只能从ZONE_DMA区中获取。
  • 如果没有规定从哪个区获取,就按照顺序从 ZONE_NORMAL -> ZONE_DMA 获取。
  • 如果规定从HIGHMEM区获取,就按照顺序从 ZONE_HIGHMEM -> ZONE_NORMAL -> ZONE_DMA 获取。

图片

内核中根据不同的分配需求有6个函数接口来请求页框,最终都会调用到__alloc_pages_nodemask。

图片

1
2
3
4
5
6
7
8
9
struct page *
__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order, int preferred_nid,
nodemask_t *nodemask)
{
page = get_page_from_freelist(alloc_mask, order, alloc_flags, &ac);//fastpath分配页面:从pcp(per_cpu_pages)和伙伴系统中正常的分配内存空间
......
page = __alloc_pages_slowpath(alloc_mask, order, &ac);//slowpath分配页面:如果上面没有分配到空间,调用下面函数慢速分配,允许等待和回收
......
}

在页面分配时,有两种路径可以选择,如果在快速路径中分配成功了,则直接返回分配的页面;快速路径分配失败则选择慢速路径来进行分配。总结如下:

  • 正常分配(或叫快速分配):
  1. 如果分配的是单个页面,考虑从per CPU缓存中分配空间,如果缓存中没有页面,从伙伴系统中提取页面做补充。
  2. 分配多个页面时,从指定类型中分配,如果指定类型中没有足够的页面,从备用类型链表中分配。最后会试探保留类型链表。
  • 慢速(允许等待和页面回收)分配:
  1. 当上面两种分配方案都不能满足要求时,考虑页面回收、杀死进程等操作后在试。

伙伴算法

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
static struct page *
get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
const struct alloc_context *ac)
{
for_next_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx, ac->nodemask)
{
if (!zone_watermark_fast(zone, order, mark, ac_classzone_idx(ac), alloc_flags))
{
ret = node_reclaim(zone->zone_pgdat, gfp_mask, order);
switch (ret) {
case NODE_RECLAIM_NOSCAN:
continue;
case NODE_RECLAIM_FULL:
continue;
default:
if (zone_watermark_ok(zone, order, mark, ac_classzone_idx(ac), alloc_flags))
goto try_this_zone;

continue;
}
}

try_this_zone: //本zone正常水位
page = rmqueue(ac->preferred_zoneref->zone, zone, order, gfp_mask, alloc_flags, ac->migratetype);
}

return NULL;
}

首先遍历当前zone,按照HIGHMEM->NORMAL的方向进行遍历,判断当前zone是否能够进行内存分配的条件是首先判断free memory是否满足low water mark水位值,如果不满足则进行一次快速的内存回收操作,然后再次检测是否满足low water mark,如果还是不能满足,相同步骤遍历下一个zone,满足的话进入正常的分配情况,即rmqueue函数,这也是伙伴系统的核心。

Buddy 分配算法

在看函数前,我们先看下算法,因为我一直认为有了“道”的理解才好进一步理解“术”。

图片

假设这是一段连续的页框,阴影部分表示已经被使用的页框,现在需要申请一个连续的5个页框。这个时候,在这段内存上不能找到连续的5个空闲的页框,就会去另一段内存上去寻找5个连续的页框,这样子,久而久之就形成了页框的浪费。为了避免出现这种情况,Linux内核中引入了伙伴系统算法(Buddy system)。把所有的空闲页框分组为11个块链表,每个块链表分别包含大小为1,2,4,8,16,32,64,128,256,512和1024个连续页框的页框块。最大可以申请1024个连续页框,对应4MB大小的连续内存。每个页框块的第一个页框的物理地址是该块大小的整数倍,如图:

图片

假设要申请一个256个页框的块,先从256个页框的链表中查找空闲块,如果没有,就去512个页框的链表中找,找到了则将页框块分为2个256个页框的块,一个分配给应用,另外一个移到256个页框的链表中。如果512个页框的链表中仍没有空闲块,继续向1024个页框的链表查找,如果仍然没有,则返回错误。页框块在释放时,会主动将两个连续的页框块合并为一个较大的页框块。

从上面可以知道Buddy算法一直在对页框做拆开合并拆开合并的动作。Buddy算法牛逼就牛逼在运用了世界上任何正整数都可以由2^n的和组成。这也是Buddy算法管理空闲页表的本质。空闲内存的信息我们可以通过以下命令获取:

图片

也可以通过echo m > /proc/sysrq-trigger来观察buddy状态,与/proc/buddyinfo的信息是一致的:

图片

Buddy 分配函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static inline
struct page *rmqueue(struct zone *preferred_zone,
struct zone *zone, unsigned int order,
gfp_t gfp_flags, unsigned int alloc_flags,
int migratetype)
{
if (likely(order == 0)) { //如果order=0则从pcp中分配
page = rmqueue_pcplist(preferred_zone, zone, order, gfp_flags, migratetype);
}
do {
page = NULL;
if (alloc_flags & ALLOC_HARDER) {//如果分配标志中设置了ALLOC_HARDER,则从free_list[MIGRATE_HIGHATOMIC]的链表中进行页面分配
page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
}
if (!page) //前两个条件都不满足,则在正常的free_list[MIGRATE_*]中进行分配
page = __rmqueue(zone, order, migratetype);
} while (page && check_new_pages(page, 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
static struct page *
get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
const struct alloc_context *ac)
{
for_next_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx, ac->nodemask)
{
if (!zone_watermark_fast(zone, order, mark, ac_classzone_idx(ac), alloc_flags))
{
ret = node_reclaim(zone->zone_pgdat, gfp_mask, order);
switch (ret) {
case NODE_RECLAIM_NOSCAN:
continue;
case NODE_RECLAIM_FULL:
continue;
default:
if (zone_watermark_ok(zone, order, mark, ac_classzone_idx(ac), alloc_flags))
goto try_this_zone;

continue;
}
}

try_this_zone: //本zone正常水位
page = rmqueue(ac->preferred_zoneref->zone, zone, order, gfp_mask, alloc_flags, ac->migratetype);
}

return NULL;
}

可以看到在进行伙伴算法分配前有个关于水位的判断,今天我们就看下水位的概念。

简单的说在使用分区页面分配器中会将可以用的free pages与zone里的水位(watermark)进行比较。

水位初始化

  • nr_free_buffer_pages 是获取ZONE_DMA和ZONE_NORMAL区中高于high水位的总页数nr_free_buffer_pages = managed_pages - high_pages
  • min_free_kbytes 是总的min大小,min_free_kbytes = 4 * sqrt(lowmem_kbytes)
  • setup_per_zone_wmarks 根据总的min值,再加上各个zone在总内存中的占比,然后通过do_div就计算出他们各自的min值,进而计算出各个zone的水位大小。min,low,high的关系如下:low = min *125%;
  • high = min * 150%
  • min:low:high = 4:5:6
  • setup_per_zone_lowmem_reserve 当从Normal失败后,会尝试从DMA申请分配,通过lowmem_reserve[DMA],限制来自Normal的分配请求。其值可以通过/proc/sys/vm/lowmem_reserve_ratio来修改。

图片

从这张图可以看出:

  • 如果空闲页数目min值,则该zone非常缺页,页面回收压力很大,应用程序写内存操作就会被阻塞,直接在应用程序的进程上下文中进行回收,即direct reclaim。
  • 如果空闲页数目小于low值,kswapd线程将被唤醒,并开始释放回收页面。
  • 如果空闲页面的值大于high值,则该zone的状态很完美, kswapd线程将重新休眠。

内存碎片化整理

什么是内存碎片化

Linux物理内存碎片化包括两种:内部碎片化和外部碎片化。

  • 内部碎片化:

指分配给用户的内存空间中未被使用的部分。例如进程需要使用3K bytes物理内存,于是向系统申请了大小等于3Kbytes的内存,但是由于Linux内核伙伴系统算法最小颗粒是4K bytes,所以分配的是4Kbytes内存,那么其中1K bytes未被使用的内存就是内存内碎片。

  • 外部碎片化:

指系统中无法利用的小内存块。例如系统剩余内存为16K bytes,但是这16K bytes内存是由4个4K bytes的页面组成,即16K内存物理页帧号#1不连续。在系统剩余16K bytes内存的情况下,系统却无法成功分配大于4K的连续物理内存,该情况就是内存外碎片导致。

碎片化整理算法

Linux内存对碎片化的整理算法主要应用了内核的页面迁移机制,是一种将可移动页面进行迁移后腾出连续物理内存的方法。

假设存在一个非常小的内存域如下:

图片

蓝色表示空闲的页面,白色表示已经被分配的页面,可以看到如上内存域的空闲页面(蓝色)非常零散,无法分配大于两页的连续物理内存。

下面演示一下内存规整的简化工作原理,内核会运行两个独立的扫描动作:第一个扫描从内存域的底部开始,一边扫描一边将已分配的可移动(MOVABLE)页面记录到一个列表中:

图片

另外第二扫描是从内存域的顶部开始,扫描可以作为页面迁移目标的空闲页面位置,然后也记录到一个列表里面:

图片

等两个扫描在域中间相遇,意味着扫描结束,然后将左边扫描得到的已分配的页面迁移到右边空闲的页面中,左边就形成了一段连续的物理内存,完成页面规整。

图片

碎片化整理的三种方式

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
static struct page *
__alloc_pages_direct_compact(gfp_t gfp_mask, unsigned int order,
unsigned int alloc_flags, const struct alloc_context *ac,
enum compact_priority prio, enum compact_result *compact_result)
{
struct page *page;
unsigned int noreclaim_flag;

if (!order)
return NULL;

noreclaim_flag = memalloc_noreclaim_save();
*compact_result = try_to_compact_pages(gfp_mask, order, alloc_flags, ac,
prio);
memalloc_noreclaim_restore(noreclaim_flag);

if (*compact_result <= COMPACT_INACTIVE)
return NULL;

count_vm_event(COMPACTSTALL);

page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);

if (page) {
struct zone *zone = page_zone(page);

zone->compact_blockskip_flush = false;
compaction_defer_reset(zone, order, true);
count_vm_event(COMPACTSUCCESS);
return page;
}

count_vm_event(COMPACTFAIL);

cond_resched();

return NULL;
}

在linux内核里一共有3种方式可以碎片化整理,我们总结如下:

图片

Alloc_page

Kmalloc

Kmap

Slab

在Linux中,伙伴系统是以页为单位分配内存。但是现实中很多时候却以字节为单位,不然申请10Bytes内存还要给1页的话就太浪费了。slab分配器就是为小内存分配而生的。slab分配器分配内存以Byte为单位。但是slab分配器并没有脱离伙伴系统,而是基于伙伴系统分配的大内存进一步细分成小内存分配。

他们之间的关系可以用一张图来描述:

图片

流程分析

kmem_cache_alloc 主要四步:

  1. 先从 kmem_cache_cpu->freelist中分配,如果freelist为null

图片

  1. 接着去 kmem_cache_cpu->partital链表中分配,如果此链表为null

图片

  1. 接着去 kmem_cache_node->partital链表分配,如果此链表为null

图片

  1. 重新分配一个slab。

Vmalloc

根据前面的系列文章,我们知道了buddy system是基于页框分配器,kmalloc是基于slab分配器,而且这些分配的地址都是物理内存连续的。但是随着碎片化的积累,连续物理内存的分配就会变得困难,对于那些非DMA访问,不一定非要连续物理内存的话完全可以像malloc那样,将不连续的物理内存页框映射到连续的虚拟地址空间中,这就是vmap的来源)(提供把离散的page映射到连续的虚拟地址空间),vmalloc的分配就是基于这个机制来实现的。

图片

vmalloc最小分配一个page,并且分配到的页面不保证是连续的,因为vmalloc内部调用alloc_page多次分配单个页面。

图片

vmalloc的区域就是在上图中VMALLOC_START - VMALLOC_END之间,可通过/proc/vmallocinfo查看。

图片

vmalloc流程主要分以下三步:

  1. 从VMALLOC_START到VMALLOC_END查找空闲的虚拟地址空间(hole)
  2. 根据分配的size,调用alloc_page依次分配单个页面.
  3. 把分配的单个页面,映射到第一步中找到的连续的虚拟地址。把分配的单个页面,映射到第一步中找到的连续的虚拟地址。

图片

缺页异常

当进程访问这些还没建立映射关系的虚拟地址时,处理器会自动触发缺页异常。

ARM64把异常分为同步异常和异步异常,通常异步异常指的是中断(可看《上帝视角看中断》),同步异常指的是异常。关于ARM异常处理的文章可参考《ARMv8异常处理简介》。

当处理器有异常发生时,处理器会先跳转到ARM64的异常向量表中:

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
ENTRY(vectors)
kernel_ventry 1, sync_invalid // Synchronous EL1t
kernel_ventry 1, irq_invalid // IRQ EL1t
kernel_ventry 1, fiq_invalid // FIQ EL1t
kernel_ventry 1, error_invalid // Error EL1t

kernel_ventry 1, sync // Synchronous EL1h
kernel_ventry 1, irq // IRQ EL1h
kernel_ventry 1, fiq_invalid // FIQ EL1h
kernel_ventry 1, error_invalid // Error EL1h

kernel_ventry 0, sync // Synchronous 64-bit EL0
kernel_ventry 0, irq // IRQ 64-bit EL0
kernel_ventry 0, fiq_invalid // FIQ 64-bit EL0
kernel_ventry 0, error_invalid // Error 64-bit EL0

#ifdef CONFIG_COMPAT
kernel_ventry 0, sync_compat, 32 // Synchronous 32-bit EL0
kernel_ventry 0, irq_compat, 32 // IRQ 32-bit EL0
kernel_ventry 0, fiq_invalid_compat, 32 // FIQ 32-bit EL0
kernel_ventry 0, error_invalid_compat, 32 // Error 32-bit EL0
#else
kernel_ventry 0, sync_invalid, 32 // Synchronous 32-bit EL0
kernel_ventry 0, irq_invalid, 32 // IRQ 32-bit EL0
kernel_ventry 0, fiq_invalid, 32 // FIQ 32-bit EL0
kernel_ventry 0, error_invalid, 32 // Error 32-bit EL0
#endif
END(vectors)

以el1下的异常为例,当跳转到el1_sync函数时,读取ESR的值以判断异常类型。根据类型跳转到不同的处理函数里,如果是data abort的话跳转到el1_da函数里,instruction abort的话跳转到el1_ia函数里:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
el1_sync:
kernel_entry 1
mrs x1, esr_el1 // read the syndrome register
lsr x24, x1, #ESR_ELx_EC_SHIFT // exception class
cmp x24, #ESR_ELx_EC_DABT_CUR // data abort in EL1
b.eq el1_da
cmp x24, #ESR_ELx_EC_IABT_CUR // instruction abort in EL1
b.eq el1_ia
cmp x24, #ESR_ELx_EC_SYS64 // configurable trap
b.eq el1_undef
cmp x24, #ESR_ELx_EC_SP_ALIGN // stack alignment exception
b.eq el1_sp_pc
cmp x24, #ESR_ELx_EC_PC_ALIGN // pc alignment exception
b.eq el1_sp_pc
cmp x24, #ESR_ELx_EC_UNKNOWN // unknown exception in EL1
b.eq el1_undef
cmp x24, #ESR_ELx_EC_BREAKPT_CUR // debug exception in EL1
b.ge el1_dbg
b el1_inv

流程图如下:

图片

do_page_fault

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
static int __do_page_fault(struct mm_struct *mm, unsigned long addr,
unsigned int mm_flags, unsigned long vm_flags,
struct task_struct *tsk)
{
struct vm_area_struct *vma;
int fault;

vma = find_vma(mm, addr);
fault = VM_FAULT_BADMAP; //没有找到vma区域,说明addr还没有在进程的地址空间中
if (unlikely(!vma))
goto out;
if (unlikely(vma->vm_start > addr))
goto check_stack;

/*
* Ok, we have a good vm_area for this memory access, so we can handle
* it.
*/
good_area://一个好的vma
/*
* Check that the permissions on the VMA allow for the fault which
* occurred.
*/
if (!(vma->vm_flags & vm_flags)) {//权限检查
fault = VM_FAULT_BADACCESS;
goto out;
}

//重新建立物理页面到VMA的映射关系
return handle_mm_fault(vma, addr & PAGE_MASK, mm_flags);

check_stack:
if (vma->vm_flags & VM_GROWSDOWN && !expand_stack(vma, addr))
goto good_area;
out:
return fault;
}

do_page_fault函数能看出来,当触发异常的虚拟地址属于某个vma,并且拥有触发页错误异常的权限时,会调用到handle_mm_fault函数来建立vma和物理地址的映射,而handle_mm_fault函数的主要逻辑是通过handle_mm_fault来实现的。

__handle_mm_fault

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static int __handle_mm_fault(struct vm_area_struct *vma, unsigned long address,
unsigned int flags)
{
......
//查找页全局目录,获取地址对应的表项
pgd = pgd_offset(mm, address);
//查找页四级目录表项,没有则创建
p4d = p4d_alloc(mm, pgd, address);
if (!p4d)
return VM_FAULT_OOM;

//查找页上级目录表项,没有则创建
vmf.pud = pud_alloc(mm, p4d, address);
......
//查找页中级目录表项,没有则创建
vmf.pmd = pmd_alloc(mm, vmf.pud, address);
......
//处理pte页表
return handle_pte_fault(&vmf);
}

图片

do_anonymous_page

匿名页缺页异常,对于匿名映射,映射完成之后,只是获得了一块虚拟内存,并没有分配物理内存,当第一次访问的时候:

  1. 如果是读访问,会将虚拟页映射到0页,以减少不必要的内存分配
  2. 如果是写访问,用alloc_zeroed_user_highpage_movable分配新的物理页,并用0填充,然后映射到虚拟页上去
  3. 如果是先读后写访问,则会发生两次缺页异常:第一次是匿名页缺页异常的读的处理(虚拟页到0页的映射),第二次是写时复制缺页异常处理。

从上面的总结我们知道,第一次访问匿名页时有三种情况,其中第一种和第三种情况都会涉及到0页。

do_fault

图片

do_swap_page

上面已经讲过,pte对应的内容不为0(页表项存在),但是pte所对应的page不在内存中时,表示此时pte的内容所对应的页面在swap空间中,缺页异常时会通过do_swap_page()函数来分配页面。

do_swap_page发生在swap in的时候,即查找磁盘上的slot,并将数据读回。

换入的过程如下:

  1. 查找swap cache中是否存在所查找的页面,如果存在,则根据swap cache引用的内存页,重新映射并更新页表;如果不存在,则分配新的内存页,并添加到swap cache的引用中,更新内存页内容完成后,更新页表。
  2. 换入操作结束后,对应swap area的页引用减1,当减少到0时,代表没有任何进程引用了该页,可以进行回收。
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
int do_swap_page(struct vm_fault *vmf)
{
......
//根据pte找到swap entry, swap entry和pte有一个对应关系
entry = pte_to_swp_entry(vmf->orig_pte);
......
if (!page)
//根据entry从swap缓存中查找页, 在swapcache里面寻找entry对应的page
//Lookup a swap entry in the swap cache
page = lookup_swap_cache(entry, vma_readahead ? vma : NULL,
vmf->address);
//没有找到页
if (!page) {
if (vma_readahead)
page = do_swap_page_readahead(entry,
GFP_HIGHUSER_MOVABLE, vmf, &swap_ra);
else
//如果swapcache里面找不到就在swap area里面找,分配新的内存页并从swap area中读入
page = swapin_readahead(entry,
GFP_HIGHUSER_MOVABLE, vma, vmf->address);
......
//获取一个pte的entry,重新建立映射
vmf->pte = pte_offset_map_lock(vma->vm_mm, vmf->pmd, vmf->address,
&vmf->ptl);
......
//anonpage数加1,匿名页从swap空间交换出来,所以加1
//swap page个数减1,由page和VMA属性创建一个新的pte
inc_mm_counter_fast(vma->vm_mm, MM_ANONPAGES);
dec_mm_counter_fast(vma->vm_mm, MM_SWAPENTS);
pte = mk_pte(page, vma->vm_page_prot);
......
flush_icache_page(vma, page);
if (pte_swp_soft_dirty(vmf->orig_pte))
pte = pte_mksoft_dirty(pte);
//将新生成的PTE entry添加到硬件页表中
set_pte_at(vma->vm_mm, vmf->address, vmf->pte, pte);
vmf->orig_pte = pte;
//根据page是否为swapcache
if (page == swapcache) {
//如果是,将swap缓存页用作anon页,添加反向映射rmap中
do_page_add_anon_rmap(page, vma, vmf->address, exclusive);
mem_cgroup_commit_charge(page, memcg, true, false);
//并添加到active链表中
activate_page(page);
//如果不是
} else { /* ksm created a completely new copy */
//使用新页面并复制swap缓存页,添加反向映射rmap中
page_add_new_anon_rmap(page, vma, vmf->address, false);
mem_cgroup_commit_charge(page, memcg, false, false);
//并添加到lru链表中
lru_cache_add_active_or_unevictable(page, vma);
}

//释放swap entry
swap_free(entry);
......
if (vmf->flags & FAULT_FLAG_WRITE) {
//有写请求则写时复制
ret |= do_wp_page(vmf);
if (ret & VM_FAULT_ERROR)
ret &= VM_FAULT_ERROR;
goto out;
}
......
return ret;
}

图片

do_wp_page

走到这里说明页面在内存中,只是PTE只有读权限,而又要写内存的时候就会触发do_wp_page。

do_wp_page函数用于处理写时复制(copy on write),其流程比较简单,主要是分配新的物理页,拷贝原来页的内容到新页,然后修改页表项内容指向新页并修改为可写(vma具备可写属性)。

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
static int do_wp_page(struct vm_fault *vmf)
__releases(vmf->ptl)
{
struct vm_area_struct *vma = vmf->vma;

//从页表项中得到页帧号,再得到页描述符,发生异常时地址所在的page结构
vmf->page = vm_normal_page(vma, vmf->address, vmf->orig_pte);
if (!vmf->page) {
//没有page结构是使用页帧号的特殊映射
/*
* VM_MIXEDMAP !pfn_valid() case, or VM_SOFTDIRTY clear on a
* VM_PFNMAP VMA.
*
* We should not cow pages in a shared writeable mapping.
* Just mark the pages writable and/or call ops->pfn_mkwrite.
*/
if ((vma->vm_flags & (VM_WRITE|VM_SHARED)) ==
(VM_WRITE|VM_SHARED))
//处理共享可写映射
return wp_pfn_shared(vmf);

pte_unmap_unlock(vmf->pte, vmf->ptl);
//处理私有可写映射
return wp_page_copy(vmf);
}

/*
* Take out anonymous pages first, anonymous shared vmas are
* not dirty accountable.
*/
if (PageAnon(vmf->page) && !PageKsm(vmf->page)) {
int total_map_swapcount;
if (!trylock_page(vmf->page)) {
//添加原来页的引用计数,方式被释放
get_page(vmf->page);
//释放页表锁
pte_unmap_unlock(vmf->pte, vmf->ptl);
lock_page(vmf->page);
vmf->pte = pte_offset_map_lock(vma->vm_mm, vmf->pmd,
vmf->address, &vmf->ptl);
if (!pte_same(*vmf->pte, vmf->orig_pte)) {
unlock_page(vmf->page);
pte_unmap_unlock(vmf->pte, vmf->ptl);
put_page(vmf->page);
return 0;
}
put_page(vmf->page);
}
//单身匿名页面的处理
if (reuse_swap_page(vmf->page, &total_map_swapcount)) {
if (total_map_swapcount == 1) {
/*
* The page is all ours. Move it to
* our anon_vma so the rmap code will
* not search our parent or siblings.
* Protected against the rmap code by
* the page lock.
*/
page_move_anon_rmap(vmf->page, vma);
}
unlock_page(vmf->page);
wp_page_reuse(vmf);
return VM_FAULT_WRITE;
}
unlock_page(vmf->page);
} else if (unlikely((vma->vm_flags & (VM_WRITE|VM_SHARED)) ==
(VM_WRITE|VM_SHARED))) {
//共享可写,不需要复制物理页,设置页表权限即可
return wp_page_shared(vmf);
}

/*
* Ok, we need to copy. Oh, well..
*/
get_page(vmf->page);

pte_unmap_unlock(vmf->pte, vmf->ptl);
//私有可写,复制物理页,将虚拟页映射到物理页
return wp_page_copy(vmf);
}

CMA

CMA是reserved的一块内存,用于分配连续的大块内存。当设备驱动不用时,内存管理系统将该区域用于分配和管理可移动类型页面;当设备驱动使用时,此时已经分配的页面需要进行迁移,又用于连续内存分配;其用法与DMA子系统结合在一起充当DMA的后端,具体可参考《没有IOMMU的DMA操作》。

CMA区域 cma_areas 的创建

CMA区域的创建有两种方法,一种是通过dts的reserved memory,另外一种是通过command line参数和内核配置参数。

  • dts方式:
1
2
3
4
5
6
7
8
9
10
reserved-memory {
/* global autoconfigured region for contiguous allocations */
linux,cma {
compatible = "shared-dma-pool";
reusable;
size = <0 0x28000000>;
alloc-ranges = <0 0xa0000000 0 0x40000000>;
linux,cma-default;
};
};

device tree中可以包含reserved-memory node,系统启动的时候会打开rmem_cma_setup

RESERVEDMEM_OF_DECLARE(cma, “shared-dma-pool”, rmem_cma_setup);

  • command line方式:cma=nn[MG]@[start[MG][-end[MG]]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static int __init early_cma(char *p)
{
pr_debug("%s(%s)\n", __func__, p);
size_cmdline = memparse(p, &p);
if (*p != '@') {
/*
if base and limit are not assigned,
set limit to high memory bondary to use low memory.
*/
limit_cmdline = __pa(high_memory);
return 0;
}
base_cmdline = memparse(p + 1, &p);
if (*p != '-') {
limit_cmdline = base_cmdline + size_cmdline;
return 0;
}
limit_cmdline = memparse(p + 1, &p);

return 0;
}
early_param("cma", early_cma);

系统在启动的过程中会把cmdline里的nn, start, end传给函数dma_contiguous_reserve,流程如下:

setup_arch—->arm64_memblock_init—->dma_contiguous_reserve->dma_contiguous_reserve_area->cma_declare_contiguous

图片

将CMA区域添加到Buddy System

为了避免这块reserved的内存在不用时候的浪费,内存管理模块会将CMA区域添加到Buddy System中,用于可移动页面的分配和管理。CMA区域是通过cma_init_reserved_areas接口来添加到Buddy System中的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static int __init cma_init_reserved_areas(void)
{
int i;

for (i = 0; i < cma_area_count; i++) {
int ret = cma_activate_area(&cma_areas[i]);

if (ret)
return ret;
}

return 0;
}
core_initcall(cma_init_reserved_areas);

其实现比较简单,主要分为两步:

  1. 把该页面设置为MIGRATE_CMA标志
  2. 通过__free_pages将页面添加到buddy system中

图片

CMA分配

《没有IOMMU的DMA操作》里讲过,CMA是通过cma_alloc分配的。cma_alloc->alloc_contig_range(…, MIGRATE_CMA,…),向刚才释放给buddy system的MIGRATE_CMA类型页面,重新“收集”过来。

图片

用CMA的时候有一点需要注意:

也就是上图中黄色部分的判断。CMA内存在分配过程是一个比较“重”的操作,可能涉及页面迁移、页面回收等操作,因此不适合用于atomic context。比如之前遇到过一个问题,当内存不足的情况下,向U盘写数据的同时操作界面会出现卡顿的现象,这是因为CMA在迁移的过程中需要等待当前页面中的数据回写到U盘之后,才会进一步的规整为连续内存供gpu/display使用,从而出现卡顿的现象。

图片

总结

至此,从CPU开始访问内存,到物理页的划分,再到内核页框分配器的实现,以及slab分配器的实现,最后到CMA等连续内存的使用,把Linux内存管理的知识串了起来,算是形成了整个闭环。相信如果掌握了本篇内容,肯定打开了Linux内核的大门,有了这个基石,祝愿大家接下来的内核学习越来越轻松。

参考资料