linux使用伙伴系统来管理物理内存页。

一、伙伴系统原理

1. 伙伴关系

定义：由一个母实体分成的两个各方面属性一致的两个子实体，这两个子实体就处于伙伴关系。在操作系统分配内存的过程中，一个内存块常常被分成两个大小相等的内存块，这两个大小相等的内存块就处于伙伴关系。它满足 3 个条件 ：

•  两个块具有相同大小记为 2^K
•  它们的物理地址是连续的
•  从同一个大块中拆分出来

2. 伙伴算法的实现原理

为了便于页面的维护，将多个页面组成内存块，每个内存块都有 2 的方幂个页，方幂的指数被称为阶 order。order相同的内存块被组织到一个空闲链表中。伙伴系统基于2的方幂来申请释放内存页。
当申请内存页时，伙伴系统首先检查与申请大小相同的内存块链表中，检看是否有空闲页，如果有就将其分配出去，并将其从链表中删除，否则就检查上一级，即大小为申请大小的2倍的内存块空闲链表，如果该链表有空闲内存，就将其分配出去，同时将剩余的一部分（即未分配出去的一半）加入到下一级空闲链表中；如果这一级仍没有空闲内存；就检查它的上一级，依次类推，直到分配成功或者彻底失败，在成功时还要按照伙伴系统的要求，将未分配的内存块进行划分并加入到相应的空闲内存块链表
在释放内存页时，会检查其伙伴是否也是空闲的，如果是就将它和它的伙伴合并为更大的空闲内存块，该检查会递归进行，直到发现伙伴正在被使用或者已经合并成了最大的内存块。

二、linux中的伙伴系统相关的结构

系统中的每个物理内存页（页帧）都对应一个struct page数据结构，每个节点都包含了多个zone，每个zone都有struct zone表示，其中保存了用于伙伴系统的数据结构。zone中的

用于管理该zone的伙伴系统信息。伙伴系统将基于这些信息管理该zone的物理内存。该数组中每个数组项用于管理一个空闲内存页块链表，同一个链表中的内存页块的大小相同，并且大小为2的数组下标次方页。MAX_ORDER定义了支持的最大的内存页块大小。
struct free_area的定义如下

• nr_free:其中nr_free表示内存页块的数目，对于0阶的表示以1页为单位计算，对于1阶的以2页为单位计算，n阶的以2的n次方为单位计算。
• free_list:用于将具有该大小的内存页块连接起来。由于内存页块表示的是连续的物理页，因而对于加入到链表中的每个内存页块来说，只需要将内存页块中的第一个页加入该链表即可。因此这些链表连接的是每个内存页块中第一个内存页，使用了struct page中的struct list_head成员lru。free_list数组元素的每一个对应一种属性的类型，可用于不同的目地，但是它们的大小和组织方式相同。

因此在伙伴系统看来，一个zone中的内存组织方式如下图所示：

基于伙伴系统的内存管理方式专注于内存节点的某个内存域的管理，但是系统中的所有zone都会通过备用列表连接起来。伙伴系统和内存域/节点的关系如下图所示：

系统中伙伴系统的当前信息可以通过/proc/buddyinfo查看：

这是我的PC上的信息，这些信息描述了每个zone中对应于每个阶的空闲内存页块的数目，从左到右阶数依次升高。

三、避免碎片

1.碎片概念

伙伴系统也存在一些问题，在系统长时间运行后，物理内存会出现很多碎片，如图所示：
 
这是虽然可用内存页还有很多，但是最大的连续物理内存也只有一页，这对于用户程序不成问题，因为用户程序通过页表映射，应用程序看到的总是连续的虚拟内存。但是对于内核来说就不行了，因为内核有时候需要使用连续的物理内存。

2.linux解决方案

碎片问题也存在于文件系统，文件系统中的碎片可以通过工具来解决，即分析文件系统，然后重新组织文件的位置，但是这种方不适用于内核，因为有些物理页时不能随意移动。内核采用的方法是反碎片（anti-fragmentation）。为此内核根据页的可移动性将其划分为3种不同的类型：

• 不可移动的页：在内存中有固定位置，不能移动。分配给核心内核的页大多是此种类型
• 可回收的页：不能移动，但是可以删除，其内容可以从某些源重新生成。
• 可移动的页：可以随意移动。属于用户进程的页属于这种类型，因为它们是通过页表映射的，因而在移动后只需要更新用户进程页表即可。

页的可移动性取决于它属于上述三类中的哪一类，内核将页面按照不同的可移动性进行分组，通过这种技术，虽然在不可移动页中仍可能出现碎片，但是由于具有不同可移动性的页不会进入同一个组，因而其它两个类型的内存块就可以获得较好的“对抗碎片”的特性。
需要注意的是按照可移动性对内存页进行分组时在运行中进行的，而不是在一开始就设置好的。

1.数据结构

内核定义了MIGRATE_TYPES中迁移类型，其定义如下： 
其中前三种分别对应于三种可移动性，其它几种的含义：

• MIGRATE_PCPTYPES：是per_cpu_pageset，即用来表示每CPU页框高速缓存的数据结构中的链表的迁移类型数目
• MIGRATE_RESERVE：是在前三种的列表中都没用可满足分配的内存块时，就可以从MIGRATE_RESERVE分配
• MIGRATE_ISOLATE：用于跨越NUMA节点移动物理内存页，在大型系统上，它有益于将物理内存页移动到接近于是用该页最频繁地CPU

每种类型都对应free_list中的一个数组项。
类似于从zone中的分配，如果无法从指定的迁移类型分配到页，则会按照fallbacks指定的次序从备用迁移类型中尝试分配，它定义在page_alloc.c中。
虽然该特性总是编译进去的，但是该特性只有在系统中有足够的内存可以分配到每种迁移类型对应的链表时才有意义，也就是说每个可以迁移性链表都要有“适量”的内存，内核需要对“适量”的判断是基于两个宏的：

• pageblock_order：内核认为够大的一个分配的阶。
• pageblock_nr_pages：内核认为启用该特性时每个迁移链表需要具有的最少的内存页数。它的定义是基于pageblock_order的。

基于这个“适量”的概念内核会在build_all_zonelists中判断是否要启用该特性。page_group_by_mobility_disabled表示是否启用了该特性。
内核定义了两个标志：__GFP_MOVABLE和 __GFP_RECLAIMABLE分别用来表示可移动迁移类型和可回收迁移类型，如果没有设置这两个标志，则表示是不可移动的。如果页面迁移特性被禁止了，则所有的页都是不可移动页。
struct zone中包含了一个字段pageblock_flags，它用于跟踪包含pageblock_nr_pages个页的内存区的属性。在初始化期间，内核自动保证对每个迁移类型，在pageblock_flags中都分配了足够存储NR_PAGEBLOCK_BITS个比特的空间。
set_pageblock_migratetype用于设置一个以指定的页为起始地址的内存区的迁移类型。
页的迁移类型是预先分配好的，对应的比特位总是可用，在页释放时，必须将其返还给正确的链表。get_pageblock_migratetype可用于从struct page中获取页的迁移类型。
通过/proc/pagetypeinfo可以获取系统当前的信息。
在内存初始化期间memmap_init_zone会将所有的内存页都初始化为可移动的。该函数在paging_init中会最终被调到（会经过一些中间函数，其中就有free_area_init_node）。

3．虚拟可移动内存

内核还提供了一种机制来解决碎片问题，即使用虚拟内存域ZONE_MOVABLE。其思想是：可用内存划分为两个部分，一部分用于可移动分配，一部分用于不可移动分配。这样就防止了不可移动页向可移动内存区域引入碎片。
该机制需要管理员来配置两部分内存的大小。
kernel参数kernelcore用于指定用于不可移动分配的内存数量，如果指定了该参数，其值会保存在required_kernelcore会基于它来计算。
kernel参数movablecore用于指定用于可移动分配的内存数量，如果指定了该参数，则其值会被保存在required_movablecore中，同时会基于它来计算required_kernelcore，代码如下（函数find_zone_movable_pfns_for_nodes）：
如果计算出来的required_kernelcore为0，则该机制将无效。
该zone是一个虚拟zone，它不和任何物理内存相关联，该域中的内存可能来自高端内存或者普通内存。用于不可移动分配的内存会被均匀的分布到系统的各个内存节点中；同时用于可移动分配的内存只会取自最高内存域的内存，zone_movable_pfn记录了取自各个节点的用于可移动分配的内存的起始地址。

四、初始化内存域和节点数据结构

在内存管理的初始化中，架构相关的代码要完成系统中可用内存的检测，并要将相关信息提交给架构无关的代码。架构无关的代码free_area_init_nodes负责完成管理数据结构的创建。该函数需要一个参数max_zone_pfn，它由架构相关的代码提供，其中保存了每个内存域的最大可用页帧号。内核定义了两个数组：

这两个数组在free_area_init_nodes用于保存来自max_zone_pfn的信息，并将它转变成[low，high]的形式。
然后内核开始调用find_zone_movable_pfns_for_nodes对ZONE_MOVABLE域进行初始化。

然后内核开始为每一个节点调用free_area_init_node，这个函数将完成：

1. 调用calculate_node_totalpages计算节点中页的总数
2. 调用alloc_node_mem_map负责初始化struct pglist_data中的node_mem_map，为它分配的内存将用于存储本节点的所有物理内存的struct page结构。这片内存将对其到伙伴系统的最大分配阶上。而且如果当前节点是第0个节点，则该指针信息还将保存在全局变量mem_map中。
3. 调用free_area_init_core完成初始化进一步的初始化

free_area_init_core将完成内存域数据结构的初始化，在这个函数中

1. nr_kernel_pages记录直接映射的页面数目，而nr_all_pages则记录了包括高端内存中页数在内的页数
2. 会调用zone_pcp_init初始化该内存域的每CPU缓存
3. 会调用init_currently_empty_zone初始化该zone的wait_table，free_area列表
4. 调用memmap_init初始化zone的页，所有页都被初始化为可移动的

五、分配器API

伙伴系统只能分配2的整数幂个页。因此申请时，需要指定请求分配的阶。
有很多分配和释放页的API，都定义在gfp.h中。最简单的是alloc_page(gfp_mask)用来申请一个页， free_page(addr)用来释放一个页。
这里更值得关注的获取页面时的参数gfp_mask，所有获取页面的API都需要指定该参数。它用来影响分配器的行为，其中有是分配器提供的标志，标志有两种：
zone修饰符：用于告诉分配器从哪个zone分配内存
行为修饰符：告诉分配器应该如何进行分配
其中zone修饰符定义为

这些定义都一目了然，需要指出的是如果同时指定了__GFP_MOVABLE和__GFP_HIGHMEM，则会从虚拟的ZONE_MOVABLE分配。
更详细的可以参考gfp.h，其中包含了所有的标志及其含义。

1.分配页

__alloc_pages会完成最终的内存分配，它是伙伴系统的核心代码（但是在内核代码中，这种命名方式的函数都是需要小心调用的，一般都是给实现该功能的代码自己调用，不作为API提供出去的，因而它的包装器才是对外提供的API，也就是alloc_pages_node）。

1.选择页

选择页中最重要的函数是get_page_from_freelist，它负责通过标志和分配阶来判断分配是否可以进行，如果可以就进行实际的分配。该函数还会调用zone_watermark_ok根据指定的标识判断是否可以从给定的zone中进行分配。该函数需要struct zonelist的指针指向备用zone，当当前zone不能满足分配需求时就依次遍历该列表尝试进行分配。整体的分配流程是：

1. 调用get_page_from_freelist尝试进行分配，如果成功就返回分配到的页，否则
2. 唤醒kswapd，然后再次调用get_page_from_freelist尝试进行分配，如果成功就返回分配的页，否则
3. 如果分配的标志允许不检查阈值进行分配，则以ALLOC_NO_WATERMARKS为标志再次调用get_page_from_freelist尝试分配，如果成功则返回分配的页；如果不允许不检查阈值或者仍然失败，则
4. 如果不允许等待，就分配失败，否则
5. 如果支持压缩，则尝试先对内存进行一次压缩，然后再调用get_page_from_freelist，如果成功就返回，否则
6. 进行内存回收，然后再调用get_page_from_freelist，如果成功就返回，否则
7. 根据回收内存并尝试分配的结果以及分配标志，可能会调用OOM杀死一个进程然后再尝试分配，也可能不执行OOM这一步的操作，如果执行了，则在失败后可能就彻底失败，也可能重新回到第2步，也可能继续下一步
8. 回到第2步中调用get_page_from_freelist的地方或者再尝试一次先压缩后分配，如果走了先压缩再分配这一步，这就是最后一次尝试了，要么成功要么失败，不会再继续尝试了

2.移出所选择的页

在函数get_page_from_freelist中，会首先在zonelist中找到一个具有足够的空闲页的zone，然后会调用buffered_rmqueue进行处理，在分配成功时，该函数会把所分配的内存页从zone的free_list中移出，并且保证剩余的空闲内存页满足伙伴系统的要求，该函数还会把内存页的迁移类型存放在page的private域中。
该函数的步骤如图所示：

可以看出buffered_rmqueue的工作过程为：

1. 如果申请的是单页，会做特殊处理，内核会利用每CPU的缓存加速这个过程。并且在必要的时候会首先填充每CPU的缓存。函数rmqueue_bulk用于从伙伴系统获取内存页，并添加到指定的链表，它会调用函数__rmqueue。
2. 如果是分配多个页，则会首先调用__rmqueue从内存域的伙伴系统中选择合适的内存块，这一步可能失败，因为虽然内存域中有足够数目的空闲页，但是页不一定是连续的，如果是这样这一步就会返回NULL。在这一步中如果需要还会将大的内存块分解成小的内存块来进行分配，即按照伙伴系统的要求进行分配。
3. 无论是分配单页还是多个页，如果分配成功，在返回分配的页之前都要调用prep_new_page，如果这一步的处理不成功就会重新进行分配（跳转到函数buffered_rmqueue的开始），否则返回分配的页。

函数__rmqueue的执行过程：

1. 首先调用__rmqueue_smallest尝试根据指定的zone，分配的阶，迁移类型进行分配，该函数根据指定的信息进行查找，在找到一个可用的空闲内存页块后会将该内存页块从空闲内存页块链表中删除，并且会调用expand使得剩余的内存页块满足伙伴系统的要求。如果在这一步成功就返回，否则执行下一步
2. 调用__rmqueue_fallback尝试从备用zone分配。该函数用于根据前一类型的备用列表尝试从其它备用列表分配，但是需要注意的是这里会首先尝试最大的分配阶，依次降低分配的阶，直到指定的分配的阶，采用这个策略是为了避免碎片—如果要用其它迁移类型的内存，就拿一块大的过来，而不是在其它迁移类型的小区域中到处引入碎片。同时如果从其它迁移类型的空闲内存页块分配到的是一个较大的阶，则整块内存页块的迁移类型可能会发生改变，从原来的类型改变为申请分配时所请求的类型（即迁移类型发生了改变）。分配成功时的动作和__rmqueue_smallest类似，移出内存页，调用expand。

函数prep_new_page的操作

1. 对页进行检查，以确保页确实是可用的，否则就返回一个非0值导致分配失败
2. 设置页的标记以及引用计数等等。
3. 如果设置而来__GFP_COMP标志，则调用prep_compound_page将页组织成复合页（hugetlb会用到这个）。

复合页的结构如图所示：

复合页具有如下特性：

• 复合页中第一个页称为首页，其它所拥有页都称为尾页
• 组成复合页的所有的private域都指向首页
• 第一个尾页的lru的next域指向释放复合页的函数指针
• 第一个尾页的lru的prev域用于指向复合页所对应的分配的阶，即多少个页

2.释放页

__free_pages是释放页的核心函数，伙伴系统提供出去的API都是它的包装器。其流程：

1. 减小页的引用计数，如果计数不为0则直接返回，否则
2.  如果释放的是单页，则调用free_hot_cold_page，否则
3.  调用__free_pages_ok

free_hot_cold_page会把页返还给每-CPU缓存而不是直接返回给伙伴系统，因为如果每次都返还给伙伴系统，那么将会出现每次的分配和释放都需要伙伴系统进行分割和合并的情况，这将极大的降低分配的效率。因而这里采用的是一种“惰性合并”，单页会首先返还给每-CPU缓存，当每-CPU缓存的页面数大于一个阈值时（pcp->high），则一次将pcp->patch个页返还给伙伴系统。free_pcppages_bulk在free_hot_cold_page中用于将内存页返还给伙伴系统，它会调用函数__free_one_page。
函数__free_pages_ok最终页会调到__free_one_page来释放页，__free_one_page会将页面释放返还给伙伴系统，同时在必要时进行递归合并。
在__free_one_page进行合并时，需要找到释放的page的伙伴的页帧号，这是通过__find_buddy_index来完成的，其代码非常简单：
根据异或的规则，这个结果刚好可以得到邻居的页帧号。因为根据linux的管理策略以及伙伴系统的定义，伙伴系统中每个内存页块的第一个页帧号用来标志该页，因此对于order阶的两个伙伴，它们只有1<<order这个比特位是不同的，这样，只需要将该比特与取反即可，而根据异或的定义，一个比特和0异或还是本身，一个比特和1异或刚好可以取反。因此就得到了这个算式。
如果可以合并还需要取得合并后的页帧号，这个更简单，只需要让两个伙伴的页帧号相与即可。
__free_one_page调用page_is_buddy来对伙伴进行判断，以决定是否可以合并。

六、不连续内存页的分配

内核总是尝试使用物理上连续的内存区域，但是在分配内存时，可能无法找到大片的物理上连续的内存区域，这时候就需要使用不连续的内存，内核分配了其虚拟地址空间的一部分（vmalloc区）用于管理不连续内存页的分配。
每个vmalloc分配的子区域都自包含的，在内核的虚拟地址空间中vmalloc子区域之间都通过一个内存页隔离开来，这个间隔用来防止不正确的访问。

1. 用vmalloc分配内存

vmalloc用来分配在虚拟地址空间连续，但是在物理地址空间不一定连续的内存区域。它只需要一个以字节为单位的长度参数。为了节省宝贵的较低端的内存区域，vmalloc会使用高端内存进行分配。
内核使用struct vm_struct来管理vmalloc分配的每个子区域，其定义如下：
每个vmalloc子区域都对应一个该结构的实例。

• next：指向下一个vmalloc子区域
• addr：vmalloc子区域在内核虚拟地址空间的起始地址
• size：vmalloc子区域的长度
• flags：与该区域相关标志
• pages：指针，指向映射到虚拟地址空间的物理内存页的struct page实例
• nr_pages：映射的物理页面数目
• phys_addr：仅当用ioremap映射了由物理地址描述的内存页时才需要改域，它保存物理地址
• caller：申请者

2. 创建vmalloc子区域

所有的vmalloc子区域都被连接保存在vmlist中，该链表按照addr排序，顺序是从小到大。当创建一个新的子区域时需要，需要找到一个合适的位置。查找合适的位置采用的是首次适用算法，即从vmalloc区域找到第一个可以满足需求的区域，查找这样的区域是通过函数__get_vm_area_node完成的。其分配过程以下几步：

1. 调用__get_vm_area_node找到合适的区域
2. 调用__vmalloc_area_node分配物理内存页
3. 调用map_vm_area将物理内存页映射到内核的读你地址空间
4. 将新的子区域插入vmlist链表

在从伙伴系统分配物理内存页时使用了标志：GFP_KERNEL | __GFP_HIGHMEM
还有其它的方式来建立虚拟地址空间的连续映射：

1. vmalloc_32：与vmallo工作方式相同，但是确保所使用的物理地址总可以用32位指针寻址
2. vmap：将一组物理页面映射到连续的虚拟地址空间
3. ioremap：特定于处理器的分配函数，用于将取自物理地址空间而、由系统总线用于I/O操作的一个内存块，映射到内核的虚拟地址空间

3. 释放内存

vfree用于释放vmalloc和vmalloc_32分配的内存空间，vunmap用于释放由vmap和ioremap分配的空间（iounmap会调到vunmap）。最终都会归结到函数__vunmap。
__vunmap的执行过程：

1. 调用remove_vm_area从vmlist中找到一个子区域，然后将其从子区域删除，再解除物理页面的映射
2. 如果设置了deallocate_pages，则将物理页面归还给伙伴系统
3. 释放管理虚拟内存的数据结构struct vm_struct

七、内核映射

高端内存可通过vmalloc机制映射到内核的虚拟地址空间，但是高端内存往内核虚拟地址空间的映射并不依赖于vmalloc，而vmalloc是用于管理不连续内存的，它也并不依赖于高端内存。

1.持久内核映射

如果想要将高端内存长期映射到内核中，则必须使用kmap函数。该函数需要一个page指针用于指向需要映射的页面。如果没有启用高端内存，则该函数直接返回页的地址，因为所有页面都可以直接映射。如果启用了高端内存，则：

• 如果不是高端内存的页面，则直接返回页面地址，否则
• 调用kmap_high进行处理

1.使用的数据结构

vmalloc区域后的持久映射区域用于建立持久映射。pkmap_count是一个有LAST_PKMAP个元素的数组，每个元素对应一个持久映射。每个元素的值是被映射页的一个使用计数器：

1. 0：相关的页么有被使用
2. 1：该位置关联的页已经映射，但是由于CPU的TLB没有刷新而不能使用
3. 大于1的其它值：表示该页的引用计数，n表示有n-1处在使用该页

数据结构
用于建立物理页和其在虚拟地址空间位置之间的关系。

• page：指向全局数据结构mem_map数组中的page实例的指针
• virtual：该页在虚拟地址空间中分配的位置

所有的持久映射保存在一个散列表page_address_htable中，并用链表处理冲突，page_slot是散列函数。
函数page_address用于根据page实例获取器对应的虚拟地址。其处理过程：

1. 如果不是高端内存直接根据page获得虚拟地址（利用__va(paddr)），否则
2. 在散列表中查找该page对应的struct page_address_map实例，获取其虚拟地址

2.创建映射

函数kmap_high完成映射的实际创建，其工作过程：

1. 调用page_address获取对应的虚拟地址
2. 如果没有获取到，则调用map_new_virtual获取虚拟地址
3. pkmap_count数组中对应于该虚拟地址的元素的引用计数加1

新映射的创建在map_new_virtual中完成，其工作过程：
 

1. 执行一个无限循环：
   1. 更新last_pkmap_nr为last_pkmap_nr+1
   2. 同时如果last_pkmap_nr为0，调用flush_all_zero_pkmaps，flush CPU高速缓存
   3. 检查pkmap_count数组中索引last_pkmap_nr对应的元素的引用计数是否为0，如果是0就退出循环，否则
   4. 将自己加入到一个等待队列
   5. 调度其它任务
   6. 被唤醒时会首先检查是否有其它任务已经完成了新映射的创建，如果是就直接返回
   7. 回到循环头部重新执行
2. 获取与该索引对应的虚拟地址
3. 修改内核页表，将该页映射到获取到的虚拟地址
4. 更新该索引对应的pkmap_count元素的引用计数为1
5. 调用set_page_address将新的映射加入到page_address_htable中

flush_all_zero_pkmaps的工作过程：

1. 调用flush_cache_kmaps执行高速缓存flush动作
2. 遍历pkmap_count中的元素，如果某个元素的值为1就将其减小为0，并删除相关映射同时设置需要刷新标记
3. 如果需要刷新，则调用flush_tlb_kernel_range刷新指定的区域对应的tlb。

3.解除映射

kunmap用于解除kmap创建的映射，如果不是高端内存，什么都不做，否则kunmap_high将完成实际的工作。kunmap_high的工作很简单，将对应的pkmap_count中的元素的引用计数的值减1，如果新值为1，则看是否有任务在pkmap_map_wait上等待，如果有就唤醒它。根据该机制的涉及原理，该函数不能将引用计数减小到小于1，否则就是一个BUG。

2.临时内核映射

kmap不能用于无法休眠的上线文，如果要在不可休眠的上下文调用，则需要调用kmap_atomic。它是原子的，特定于架构的。同样的只有是高端内存时才会做实际的映射。
kmap_atomic使用了固定映射机制。在固定映射区域，系统中每个CPU都有一个对应的“窗口”，每个窗口对应于KM_TYPE_NR中不同的类型都有一项。这个映射的核心代码如下（取自powerpc）：
固定映射区域为用于kmap_atomic预留内存区的代码如下：

转：https://blog.csdn.net/goodluckwhh/article/details/9989695