本篇开始总结内存问题的分析，在分析之前先简单梳理下内存的基础知识。
一、虚拟内存
在早期的计算机中，程序是直接运行在物理内存上的。这样带来不少问题：
地址空间不隔离存在安全性问题、超过物理内存大小的内存需求无法得到更好满足，分配空闲内存的位置无法确定带来了重定位问题等。
为解决以上问题，引入了虚拟内存概念：
它是程序和物理内存中引入的一个中间层，属于内存管理策略的范畴。
虚拟内存：
程序都有自己独立的进程地址空间，且程序认为它拥有连续的可用的内存（一个连续完整的虚拟地址空间，但不保证物理内存连续，物理内存不够的情况下，部分数据还会暂时存储在外部磁盘存储器上，在需要时进行数据交换），虚拟内存与物理内存直接建立映射关系来一一对应。
而Linux的内存管理就是建立在虚拟内存概念之上。
1.1 虚拟内存划分
从Linux操作系统层次上，可将Linux虚拟内存划分为用户空间和内核空间。以32位操作系统为例，最大寻址范围是4G，也就是整个虚拟地址空间是4G，Linux简化了分段机制，使得虚拟地址与线性地址总是一致的。Linux一般把这个4G的地址空间划分为两个部分：其中 0～3G为用户程序地址空间，虚地址0x00000000到0xBFFFFFFF,供各个进程使用；3G～4G为内核的地址空间，虚拟地址 0xC0000000到0xFFFFFFFF, 供内核使用。
这里有两点：
用户进程通常情况下只能访问用户空间( 0～3G)的虚拟地址，不能访问内核空间的虚拟地址。例外情况只有用户进程进行系统调用（代表用户进程在内核态执行）等时刻可以访问到内核空间。
每个进程的用户空间（0-3G）完全独立、互不相干，内核空间（3G-4G）则由则由所有进程以及内核共享。
1.2 地址介绍
物理地址：内存条的单元地址。
逻辑地址：机器语言指令中用来指定一个操作数或者是一条指令的地址。
线性地址（虚拟地址）：内存管理创造的一种地址。
流程：
1.3 地址间映射方案
从上面流程可知，地址转换之间存在两种映射方案：分段与分页。
分段：使用了大小可变的块来管理内存。适合处理复杂系统的逻辑分区，映射的段表存储在线性地址空间。
分页：使用了大小不变的块来管理内存。适合管理物理内存，映射的页表保存在物理地址空间。
这里重点再看看虚拟地址查询物理地址过程：
虚拟地址与物理地址通过页表建立映射关系，CPU通过MMU（Memory Management Unit ：内存管理单元）访问页表来查询虚拟地址对应的物理地址。
页表结构：
依次按顺序判断：是否命中（命中：想要的数据在内存中）、是否满足RWX权限、是否满足User/Kernel权限，只要一项不满足，MMU会给CPU发出page fault，CPU自动跳到fault的代码去处理fault。全满足，那么MMU就去访问内存条上对应的地址。
二、内存组织与划分
2.1 页（page）
内核把页作为内存管理的基本单位。MMU也是以页为单位来管理页表。大多数32位体系结构支持4KB的页，而64位支持8KB的页(可通过命令来查看系统page大小：getconf -a | grep -i 'page')。内核中用struct page来表示系统中的每个物理页。
2.2 区（zone）
由于硬件限制，内核对特性不同的页是区别对待的，内核将内存按地址的顺序分成了不同的区，有的硬件只能访问有专门的区。区的划分本身没有任何物理意义，只不过是内核为了管理页而采取的一种逻辑上的分组。
主要关注的区有3个：
| 区 | 描述 | 物理内存 |
|---|---|---|
| ZONE_DMA | 直接内存访问，无需映射 | <16MB |
| ZONE_NORMAL | 一一对应映射页 | 16～896MB |
| ZONE_HIGHMEM | 动态映射页 | >896MB |
Linux将4G的线性地址空间分为2部分，0-3G为user space，3G-4G为kernel space。以上三个区都是针对这1G的kernel space而言的。
总结：
对0-3G的用户空间来说，其实不太关注物理地址是否连续，连续不连续都是在虚拟地址层面上谈的，区别也就是查询和插入的效率差别。
对3G-4G的内核空间来说，详细划分了三个区来满足各种物理内存需求。
DMA zone:直接访问物理内存，不需要映射，可以满足某些硬件设备的内存需求。
Normal zone:虚拟地址与物理地址是一一映射关系，如果需要连续物理内存这部分能满足。
High zone:虚拟地址与物理地址是动态映射关系，它的意义是为了能够访问所有的物理地址空间（1G空间显然无法满足，所以需要出一块动态映射区域），因此这部分内存不一定能满足连续物理内存需求，但是它提升了物理地址空间访问范围。
注：供硬件设备使用的物理内存地址必须是连续的，而供软件使用的物理内存地址则不要求必须是连续的。
三、内存分配
内存按page组织按zone划分之后，接下来看看如何分配内存。
3.1内存分配算法
1）Buddy算法
把空闲的页以2的n次方为单位进行管理，Buddy算法最主要的的特点任何时候区域里的空闲内存都能以2的n次方进行拆分或合并。整个kernel space都采用buddy算法进行管理，因此Linux最底层的内存申请都是以2n 为单位的（page）。
例如，假设ZONE_NORMAL有16页内存（24），此时有人申请一页内存，Buddy算法会把剩下的15页拆分成8+4+2+1，放到不同的链表中去。此时再申请4页，直接给4页，若再申请4页，则从8页中给4页，正好剩下4页。Buddy算法的精髓在于任何正整数都可以拆分成2的n次方之和。
通过/proc/buddyinfo可以看到内存空闲的一些情况：
Buddy算法的优点是避免了内存的外部碎片，但是长期运行后，大片的内存会比较少，而1页，2页，4页这种内存会非常多，当我们分配大片连续内存的时候就会出问题。换句话说就是以产生内部碎片为代价来避免外部碎片的产生。 Linux针对大内存的物理地址分配，采用Buddy伙伴算法，如果是针对小于一个page的内存，频繁的分配和释放，则不宜用Buddy伙伴算法。
注：所谓“内部碎片”，是指系统已经分配给用户使用、用户自己没有用到的那部分存储空间；所谓“外部碎片”，是指系统无法把它分配出去供用户使用的那部分存储空间。
2）slab算法
频繁的分配/释放内存必然导致系统性能的下降，所以有必要为频繁分配/释放的对象建立高速缓存。linux中的高速缓存是用所谓 slab 层来实现的，slab层即内核中管理高速缓存的机制。
整个slab层的原理如下：
- 可以在内存中建立各种对象的高速缓存(比如进程描述相关的结构 task_struct 的高速缓存)。
- 除了针对特定对象的高速缓存以外，也有通用对象的高速缓存。
- 每个高速缓存中包含多个 slab，slab用于管理缓存的对象。
- slab中包含多个缓存的对象，物理上由一页或多个连续的页组成。
文件接口：/proc/slabinfo
上图所示为slabinfo文件的内容，第一行为表头：
| Name | Object name |
|---|---|
| Active_objs | 已经激活的投入使用的object个数 |
| Num_objs | 为这个object分配的小内存块个数 |
| Objsize | 每一个内存块的大小 |
| Objperslab | 每一个Slab分区包含的object个数 |
| Pagesperslab | 每个Slab分区包含的page的个数 |
| Active_slabs | 已经激活的投入使用的Slab分区个数 |
| Num_slabs | 为这个object分配的Slab分区个数 |
最后再说一句，slab只用于分配低端内存，所分配的内存也只会被映射到物理内存映射区，所以vmalloc跟slab一毛钱关系都没有。
3.2 内存分配函数
1）按页获取（最原始方法）：
以下分配内存的方法参见：<linux/gfp.h>
| 方法 | 描述 |
|---|---|
| alloc_page(gfp_mask) | 只分配一页，返回指向页结构的指针 |
| alloc_pages(gfp_mask, order) | 分配 2^order 个页，返回指向第一页页结构的指针 |
| __get_free_page(gfp_mask) | 只分配一页，返回指向其逻辑地址的指针 |
| __get_free_pages(gfp_mask, order) | 分配 2^order 个页，返回指向第一页逻辑地址的指针 |
| get_zeroed_page(gfp_mask) | 只分配一页，让其内容填充为0，返回指向其逻辑地址的指针 |
alloc** 方法和 get** 方法的区别在于，一个返回的是内存的物理地址，一个返回内存物理地址映射后的逻辑地址。
如果无须直接操作物理页结构体的话，一般使用 get** 方法。
2）按字节获取(用的最多的获取方法)
| 方法 | 描述 |
|---|---|
| kmalloc | 分配的内存物理地址是连续的，虚拟地址也是连续的。分配小块内存，分配效率高。 |
| vmalloc | 分配的内存物理地址是不连续的，虚拟地址是连续的。分配大块内存，分配效率低。 |
尽管只有很少的硬件设备使用内存的场合需要用到连续的物理内存，但是很多内核代码还是使用kmalloc来分配内存而不是vmalloc主要还是出于性能考虑。在映射效率上，kmalloc明显高于vmalloc。kmalloc的物理地址和虚拟地址之间的映射比较简单，只需要将物理地址的第一页和虚拟地址的第一页关联起来即可。而vmalloc由于物理地址是不连续的，所以要将物理地址的每一页都和虚拟地址关联起来才行。当然除非是不得已需要大块内存时会考虑使用vmalloc。
3）slab层获取（效率最高的获取方法）
这里主要是针对高速缓存来处理。
| 方法 | 描述 |
|---|---|
| kmem_cache_create | 高速缓存的创建 |
| kmem_cache_alloc | 从高速缓存中分配对象 |
| kmem_cache_free | 向高速缓存释放对象 |
| kmem_cache_destroy | 高速缓存的销毁 |
总结：
在众多的内存分配函数中，如何选择合适的内存分配函数很重要，下面总结了一些选择的原则：
| 应用场景 | 分配函数选择 |
|---|---|
| 如果需要物理上连续的页 | 选择低级页分配器或者 kmalloc 函数 |
| 如果kmalloc分配是可以睡眠 | 指定 GFP_KERNEL 标志 |
| 如果kmalloc分配是不能睡眠 | 指定 GFP_ATOMIC 标志 |
| 如果不需要物理上连续的页 | vmalloc 函数 (vmalloc 的性能不如 kmalloc) |
| 如果需要高端内存 | alloc_pages 函数获取 page 的地址，在用 kmap 之类的函数进行映射 |
| 如果频繁撤销/创建教导的数据结构 | 建立slab高速缓存 |
3.3 用户态函数
| 函数 | 描述 |
|---|---|
| malloc | 动态内存分配，用于在堆上申请一块连续的指定大小的内存块区域 |
| mmap | 通过映射同一个普通文件实现共享内存。普通文件被映射到进程地址空间后，进程可以像访问普通内存一样对文件进行访问，不必再调用read()，write（）等操作。 |
四、缺页中断
在执行一条指令时，如果发现他要访问的页没有在内存中（即存在位为0），那么停止该指令的执行，并产生一个页不存在的异常，然后进行故障处理，排除异常之后原先引起的异常的指令就可以继续执行，而不再产生异常。
缺页中断处理：
do_page_fault是缺页中断的核心函数，主要工作交给__do_page_fault处理，然后进行一些异常处理__do_kernel_fault和__do_user_fault。__do_page_fault主要工作交给handle_mm_fault；handle_mm_fault的核心又是handle_pte_fault。
handle_pte_fault()函数根据页表项pte所描述的物理页框是否在物理内存中，分为两大类：
请求调页：被访问的页框不在主存中，那么此时必须分配一个页框，分为线性映射、非线性映射、swap情况下映射。
写实复制：被访问的页存在，但是该页是只读的，内核需要对该页进行写操作，此时内核将这个已存在的只读页中的数据复制到一个新的页框中。
把缺页中断处理当成一个黑盒，就是采取一切手段让你需要访问的页面存在于内存中，并且能正常读写，显然这个过程是耗时的。
内容有点多，打算分上下两篇来总结，上篇就先总结到这吧。这里主要是梳理了下基本概念，对细节感兴趣的可以自己去撸Linux内核。
参考：
《Linux内核设计与实现》
《奔跑吧Linux内核 基于Linux4.x内核源代码问题分析》
https://www.cnblogs.com/wang_yb/archive/2013/05/23/3095907.html
https://www.cnblogs.com/wuchanming/p/4756911.html
http://www.wowotech.net/memory_management/233.html
