13_ARMv8_内存管理（一）-内存管理要素
carloscn opened this issue · 0 comments
13_ARMv8_内存管理（一）-内存管理要素
我们ELF的学习的一节课中看到MMU的一些作用，有一点初步的了解，这一节我们具体的展开MMU的设计。
- 以ELF作为引子展开MMU的作用，为了和ELF做一些知识关联工作。[13_ARMv8_内存管理与MMU（一）-内存管理要素]
- 以《操作系统概念》的虚拟内存管理一节，为MMU做一些理论和基础知识的储备。[13_ARMv8_内存管理与MMU（一）-内存管理要素]
- 以《ARMv8体系架构》的MMU为例子，了解在CPU层级MMU的实现和配置。[13_ARMv8_内存管理与MMU（二） - ARMv8架构虚拟内存MMU]
- 以《Linux内核》的内存管理为例子，来研究MMU怎么实现的。[Linux_Kernel_MMU设计（一）]
1. 内存管理的发展史
我把MMU相关发展史整理成脑图，最开始是没有MMU的概念的，可以成为单道运行，方式就是直接加载到物理内存中运行。后来有了MMU，是以分段管理的方式，分为静态和动态两种方式[参考：内存分配（静态与动态分区)]，静态需要程序员自己去分区然后运行，动态就是使用换入和换出技术，这两种方式虽然改善了地址空间安全和允许多进程的问题，但是静态分区带来的进程限制和动态分区带来的碎片也是让人头疼的。后面就引入了MMU，最开始的MMU只有分段且保留了动态分区的换入和换出技术，ELF文件的代码段、数据段、进行合并之后分成了一个比较大的段[参考：内存分配（分段法）]，不同进程的多个段也映射到物理内存的区域，如果物理内存不够根据局部性原理1也使用换入和换出技术，效率依然很低。最后，在分段的基础上又进一步进行分页[参考：内存分配（分页法）]，把数据段或者程序段按照页大小进行分页、合并、共享，最终使用管理页的方式映射到物理内存，当执行的时候发现所需要的程序段或者数据段不在物理内存中，在缺页异常中同样使用换入和换出技术，把页加载进来。
2. 内存管理原理与要素
为何要提出内存管理的概念？为了性能的改进，多个进程保存在内存中，必须共享内存2。我们在内存管理之前，先讨论一些关于内存管理的技术问题，这样我们才能更深入的了解内存管理和之后的MMU设计。
2.1 多角度看内存管理的需求
从CPU角度，CPU没有办法直接访问磁盘（外存上面的数据），只能访问内存的数据，如果访问外存的数据，也要先copy这些数据从磁盘到内存中。CPU有个特性，如果使用CPU指令访问的数据是从CPU寄存器来的，那么只需要一个时钟周期；但如果给定CPU指令参数是一个内存的地址，让CPU去访问内存，那就需要多个CPU时钟周期，根据叠加原理，这个会大大降低CPU处理数据的速度，而CPU在等待指令调取内存的过程中，处于一种暂停（stall）状态，因此引入了高速缓存（cache），对于cache的访问，是由硬件管理的，操作系统无需理会。这一坨的想表达的意思有两个，CPU访问内存的速度是一个很在意的事情，而且，速度是需要硬件来支持的。
从多个进程的角度，每一个进程都该有一部分属于自己的内存空间。在多用户空间，必须保证这些私有的内存空间不会被其他进程访问到。对于内存空间的保护，也是需要由硬件管理。至少在处理器级别上面，存在基地址寄存器（base register）一个含有最小的合法地址的寄存器；还需要有界限地址寄存器（limit register）一个指定范围大小的寄存器。CPU需要具备对于内存地址的检查的能力，当非法地址被访问的时候CPU硬件需要抛出异常，OS则需要收到异常之后将此异常作为致命错误。CPU此时被要求提供一些特权指令，OS被要求这些特权指令只能在内核态准许使用。3(在ARMv8异常处理之后EL1等级)。
从单个程序的角度，程序经过编译和链接最终成为ELF二进制的形态是存储在外存上面的。程序能够执行是需要Load到内存中的，我们在4的博客中提到动态链接的概念。二进制程序运行的时候数据在RAM和ROM之间游走。OS在外存上面将进程排序，形成输入队列（input queue），输入队列和进程是两个互相配合工作的机制。进程初始化fork()->从输入队列中提取进程指令和数据->进程销毁->数据释放。程序要经过编译（汇编）、链接器、加载器、最后是运行状态，在编译的时候，编译器会将地址和符号进行绑定(bind)5，这样是为了重定位(relocation)5，经过链接器的时候再将这些符号（地址）重定位到绝对地址。每次绑定（重定位）都是从一个地址空间到另一个地址空间的映射。
- 编译时（compile stage）：生成每个文件的.o目标文件，这就有两种可能性，一种是，已知了程序加载的驻留地址，此时编译可以直接生成绝对代码(absolute code)，适用于没有虚拟内存管理的情况；一种是，不知道程序加载的驻留地址，那就必须在ELF阶段又重定位的手段，对地址重新映射，此时依赖的就是符号（symbol）。（我们看到ELF的VMA都是从0开始的5），此时的地址也成为程序的链接地址67。
- 加载时（load stage/link stage）：这个阶段生成重定位代码(relocatable code)。博客4动态链接中这个阶段决定，第一，对多个目标文件的符号进行链接，第二，全局符号的GOT处理（地址无关代码技术4），第三，决定哪些符号属于PLT延迟绑定4。链接阶段对地址再一次重新映射，可以是虚拟地址7。
- 运行时（runtime stage）：运行时，动态链接技术中进程可以从自己的内存段转移到另一个内存段，这也得益于延迟绑定技术48。此时地址还是会被重新定位为同样也是虚拟地址7。
2.2 连续内存分配
连续性(contiguous memory allocation)：多个进程放入内存中，输入队列中需要连续分配，一个进程需要紧密挨着另一个进程的内存。**注意这不是指是在两个不同进程运行时堆区域的分配，**而是输入队列的进程。这一部分可能有一些在发展史上已经被弃用的机制，比如静态和动态分区、分段这类的，我们决定还是要整理下来，因为即使是被废弃掉，很多**已经融入到了当前的设计。
2.2.1 内存保护
**区域：**内存一部分是分给操作系统(kernel space)，一部分是给用户进程(user space)。操作系统可以放在低内存地址，也可以放在高内存地址，影响着一决定的主要因素是中断向量的位置。因为reset中断向量的原因9，程序员通常将操作系统放在和中断向量对齐的位置，中断向量表是由硬件设计决定的。
在硬件上应该有这样的逻辑设计，限定寄存器用于安全CPU地址发出的合法性进行检测，要求每个逻辑地址必须在限定寄存器内，CPU调度器选择一个进程来执行的时候，作为上下文切换的一部分，分派器会重新加载[限定寄存器]和[重定位寄存器]的值。
重定位寄存器还有个一个比较重要的作用，就是可以允许操作系统的内存动态地大小改变。比如一些不常用的APP或者服务程序，这些内存会被重新征用并且会被覆盖原数据。这类程序被称为暂时(transient)操作系统代码10。
2.2.2 内存分配（静态与动态分区）
在直接load到物理内存的之后，伟大的程序设计师们又提出了分区（partition）——静态和动态分区的模型，将单道程序变为多道程序(multiprogramming)，静态多道使用的进程是有限的（受限于分区数、分区的大小），动态多道的使用限制于碎片。他们统称为多分区方法（multiple-partition method）。静态分区，如果有一个进程已经释放掉了，进程输入队列里面有排队的进程，这个进程就会被调入到这个静态分区内。古老的IBM OS/360操作系统，就是使用这种方法11。
可变分区方案(variable-partition)，操作系统需要利用表来记录内存的空闲和占用情况。这里面比较重要的概念是关于孔（hole）的。在可变分区方案中，并没有kernel空间和userspace空间的划分，所有的内存都可以用于用户进程。操作系统会分配一个比较大的内存，这个内存叫做孔。因此就可以看到，内存上面有大大小小的孔，孔上面有进程的空间（内存-> 多个孔 -> 进程空间）。操作系统进程的任务就非常明确了：在表和输入队列中根据调度算法来堆进程进行换入和换出。进程需要处理两个逻辑：
- 孔对于输入队列内的进程太小了：进程调度一面要等待足够大的空间的孔，一面要扫描输入队列看看是否有小进程可以插入该孔。
- 孔对于输入队列内的进程太大了：把孔分为两份，一份孔分给进程，另一份孔还回孔集合。内存释放或者还回的孔构成连续的条件，孔们将会合并。
孔的分配也是要有依据的，并不能够随心所欲的分配大小，这里涉及动态存储分配问题（dynamic storage-allocation problem），会有很多论文来研究这个问题。如何从孔的集合中为输入队列的进程问题找到合适大小的孔，这里是有分配原则的，首次适应（first-fit）、最优适应（best-fit）和最差适应（worst-fit）。首次适应和最优适应在性能和利用空间方面都优于最差适应12，这种优势也是完全有代价的，首次适应和最优适应的确是性能和空间利用率优于最差适应，但最差适应没有外部碎片(external fragmentation)。为了获取比较优秀的性能和空间，对于外部碎片也要另想办法进行弥补，试图既要好的性能和空间利用率，又要没有外部碎片。（外部碎片发生在，当总的可用内存之和可以满足输入队列的请求，但这些可用内存并不是连续的，而是无序的分布在内存上面形成大大小小的孔，这个就是外部碎片）。不管使用什么优化，假设有N个可分配块，那么可能有0.5N个块为外部碎片，就有1/3的内存不可以使用，这一特性被称为50%规则（ 50-percent rule）。外部碎片是孔与孔之间的不连续导致的碎片，还有孔内的碎片属于内部碎片（internal fragmentation），输入队列中比如实际大小是5字节，但是是个孔大小是6字节，这个孔被分配给了输入队列的这个进程，那么产生1字节的内部碎片。
解决孔与孔之间的碎片问题，一种解决方法就是紧缩（compaction），通过对内存进行乾坤大挪移，整理碎片为连续的的内存，这种方法也用在文件系统中，比如过去的windows操作系统需要磁盘碎片整理。紧缩方法被限定于具备重定位功能的进程，而且紧随操作还要有一定的开销，这种方法有局限性也是昂贵的。
解决孔与孔之间的碎片的另一种方法，就是分段及分页，分段和分页允许逻辑地址空间是不连续的，只要有物理内存可用，就允许为进程分配空间。处理器中引入的MMU就是这个功能。
2.2.3 内存分配（分段法）
2.2.3.1 从elf角度看分段内存
我们在13的ELF进程虚拟空间的时候有涉及过MMU，在MMU这一节我们做个知识关联。在这个ELF文件中，我们每个.o文件都会有自己的.text .data .rodata 甚至是自己的section，当链接器对这些目标文件进行链接的时候，就会把所有的目标文件的段进行合并和对齐13，合并后的段叫做segment，这些segment在MMU角度来看就是内存分段管理的段。下图是我们摘录于13的图片，SEG0，SEG1，SEG2就是ELF合并之后的段。段按照页的大小（一般是4096）进行分页，第一个页是SEG2和SEG1.1的共享页，第二个页是SEG1.2独占的页，相应地，第三个页是SEG1.3和SEG0的共享页。
从ELF角度，我们对于MMU的知识储备仅仅是这些，为什么要分页我们也搞清楚了。这里还需要注意一下，
1. 堆和栈的虚拟地址称为稀疏地址空间（Sparse），只有堆和堆栈生长的时候，才需要实际的物理页14，并非在ELF阶段映射。
2. .bss段和__libcfreere_ptrs的剩余部分放在堆段中，位于Linux内核代码fs/Binfmt_elf.c 中的load_elf_interp() 和 elf_map(),中15。
elf段的合并按照以下方式：
2.2.3.2 从cpu角度看分段内存
我们从ELF的角度（程序员的视图）理解的分段，每个模块都应该包含“堆和堆栈”、“库”、“主程序”，而不需要关心ELF这些段到底在内存的什么位置，最多最多我们也就是知道每个段都有自己的段名（段号）和段的偏移16。实际上CPU拿到<段号, 偏移>是有一定的作用的。我们在ELF上面了解到使用readelf -S main就可以查看到各个段的段表（segment table），段表中的每个段是有自己的基地址的（segment base）和段界限（segment limit）。
上图中s是段号，d是偏移，CPU会对 s+d进行判断，判断依据就是基地址+段界限寄存器，如果在范围内就会从物理内存读相应的数据，如果超越了限制，就会让操作系统陷入trap中。
这里有个例子，假设一，在逻辑地址空间上有5个段，分别是符号表，函数，主程序，栈；假设二，操作系统段表中存储着limit和base寄存器的值。在屋里内存缝补就是右边框图所示的。这里需要注意的是，段和编号无关，是无序的。
2.2.4 内存分配（分页法）
分页的方法可以有效的帮助避免孔和孔之间的外部碎片，而且可以免除换入换出地址映射的麻烦（每一次换入换出都需要自己去重新映射地址），但是也有不好之处，操作系统为每一个进程维护一个页的副本，因此，分页增加了进程上下文切换的开销。另外分页不会产生外部碎片，但是内部碎片依然会存在，如果一个进程内存的尾部大小不满一个帧的大小，那么就会出现内部碎片。
我们需要来区分一下页帧（帧，frame）和页面（页，page）的概念，页帧和页面大小是一致的，都是一个页的大小，可以通过getpagesize的命令行来获取操作系统的页大小。区别是，页帧是对于物理内存而言的，页面是对于逻辑内存而言的。逻辑内存上的页面通过页表（page table）f(x)规则映射物理内存上面，页表上面有页码（page number）和页偏移（page offset) ，页码是页表的索引，页表上面包含所在物理内存的基地址。
逻辑内存上面，连续的页内存page0 - 3，在页表中左侧是页码，页码通过f(x)关系转换到物理内存的页帧上面。所以CPU至少要收到页码和页偏移，才可以寻到想要找的地址。p是页码，页码通过f(x)关系找到对应的物理内存的页帧，偏移offset无需转换。分页也是一种动态的重定位，只是这个重定位操作系统和程序员都无法感知到。采用分页类似于采用一组基地址寄存器，每个基地址对应一个内存帧。
我们需要关注一下，对于一个输入队列的进程，分页机制如何去加载他的内存的。操作系统务必能感知到现在有多少的帧没有被使用，有多少帧已经被分配出去了。这些信息保存在操作系统的数据结构帧表中(frame table)。当进程加载进来的时候，elf的segment就会被按照帧的大小进行分页，比如这里面elf（进程）需要4个页，操作系统会从空闲帧的列表中拿出4个帧给elf（填充到页表中），同时空闲帧列表需要相应的做减员操作，此时完成进程的帧分配。
我们看到分页机制，操作系统不可能完全通过软件逻辑和数据结构实现，还要依靠CPU架构来实现一些功能。第一个页表的维护，假设我们考虑页面也是一种存入内存中的数据结构，在软件上我们不得不手动为其分配一个特殊的页面，其次CPU在每次进程上下文切换的时候查表都要访问到内存中才可以，这简直就是灾难。我们不得不考虑把页表做到架构里面去。当操作系统启动一个进程的时候，首先加载用户的寄存器，并保存用户页表到正确的硬件页表上面，这样就能减少上下文切换带来的开销。从操作系统的角度，我们给架构设计提出一些思路。
- 页表比较小的时候，页表可以作为一组专用的寄存器，这些寄存器最好是高效的逻辑电路；设定特权指令访问这些寄存器。
- 页表比较大的时候，页表无法完全被寄存器cover住，页表需要放在内存中，但是需要将页表的基地址寄存器PTBR指向页表，改变寄存器就可以改变页表了。但是，这里还是每当我们访问页的时候就会出现两次内存访问，一次基地址，一次到字节偏移，查找内存的速度被减弱50%，这也不是能被接受的。
- 页表比较大的时候，使用PTBR指向内存，并设定TLB（translation look-aside buffer）机制提升访问性能。
对于第三种方法，设定TLB（采用了专用的、小的、查找迅速的高速硬件缓冲，转换表缓冲区），并配合流水线技术，就会减小开销。TLB和页表是配合使用的，当CPU产生一个逻辑地址后，它的页码就被发送到TLB中。就有两种可能性：
- 命中概率P
1：如果找到这个页码（命中），那就直接使用； - 未命中概率P
2：没有找到这个页码（未命中，miss），那么就需要访问页表，不同CPU架构会有不同的处理，armv8架构会从硬件抛出缺页异常，call进操作系统的异常中断处理函数，手动去查页表得到地址，同时也会增加/替换TLB。
如果TLB已经满了，会对TLB进行替换，替换是有相关策略的，比如LRU最近最少使用替换、轮转替换、随机替换等，不同CPU对于替换权限不太一样，有的允许操作系统替换，有的CPU自己会替换。TLB中也有的条目是固定的，不允许被替换的，那一定是重要的内核代码了。
分页保护机制，页表除了能够查找逻辑地址和物理地址的映射，还有保护的作用，在页表后面添加一个有效-无效的位（valid-invalid），用以表示这个页所对应的页帧读写权限，错误的权限会导致产生硬件陷阱。在一个页帧内部，也有Page-Table Lengh Register表示页表的大小，该寄存器可以检查每个逻辑地址真正使用帧内内存的大小。
分页共享机制，分页还有个好处就是支持共享。我们在学习ELF的时候知道，对于同一个ELF文件，我们多次启动，那么这些进程就会共享ELF的代码段，数据段和堆和栈是独立的；还有Linux的System-V提供的ipc机制的内存共享。能够支持这样的操作是得益于分页机制。我们约定，只有可重入代码（reentrant code）或纯代码（pure code）的页可以被共享。
页表结构有很多种，不同处理器采用不同的策略，有分层页表，对于64位的架构分层页表是不适合的；处理大于32位地址空间的使用哈希页表，采用虚拟页码作为哈希值；还有倒置页表等等页表，我们可以查询一些资料，对于内表内部结构不做讨论了。
3. 虚拟内存管理
在上一章所讨论的方法，所有讨论都基于一个点：同时将多个进程保存在内存中以求多道程序可以并行运行。即便是TLB，我们也假设所有的指令和数据都应在内存中了。我们的虚拟内存管理可以依靠外存，把内存抽象成无限延展的线性空间。内存管理要素面相的问题是，当内存数据已经被加载了，我怎么提高CPU访问内存的效率；虚拟内存管理面向的问题是，实际的空间不够怎么办？我如何减少换入换出？换入换出之后我怎么维护进程的数据？
如果我们的虚拟内存大于实际的物理内存，虚拟内存是通过请求调页（demand page）方式把页帧换入和换出。
A进程的数据并没有并删除掉，而是被换出到外存上面；将B进程的数据换入到物理内存中。进程并不是被全部数据和指令换入和换出，调页程序（paper）换入的B进程会猜测用到B进程哪些页，这个被称为惰性交换器（lazy swapper）。在硬件上，使用有效-无效标识位来标志该页面是否有效，如图所示：
正常的逻辑内存是用A-H共8个页，进程只有ACF三个页被调入到物理内存中，因此在页表中标识位有效位，其余页面被标注为无效位。逻辑内存中A-H在外存上都有副本。如果这个时候进程执行D的内存，D此时被页表标记为无效，此时硬件应该发出缺页错误（page fault），操作系统陷入到缺页异常中，处理缺页异常应该有以下动作：
- 检查PCB（process control block）进程控制块和内部表，确定该饮用时有效的还是无效的内存访问。（是否在进程地址空间内，请求的地址缺页有两种可能，一种是在进程的空间中，但是没有被加载到物理内存；还有一种是，请求的地址压根外存上也没有，所以需要检查进程的内部表，确定是否请求的地址合法。）如果引用无效，就终止进程，如果引用有效，立即马上调入所属页面到物理内存中。
- 找到一个空闲帧，调度磁盘操作，把外存的所属页面写入到空闲帧中。
- 更新内部表以及更新页表。
- 回到刚才的错误指令，重新执行。
写时复制（copy on write），想象一个场景，如果我们复制一个进程的时候，还需要重新做这部分工作吗？先需要操作系统猜测load什么页到物理内存中，然后重复的做一遍这样的工作。我们不由的去反思了，父进程踩过的坑为什么子进程还需要去走一遍，这是多么低效的考虑。既然内存的分页，提供了内存共享的好处，为什么我们不让子进程最大程度利用父进程的内存空间？这样既能节约空间，也能在一定程度上减少缺页异常。所以搞计算机的大佬们研究出了写时复制。写时复制，当一个进程fork()的时候，最大程度的会利用父进程的地址空间，当子进程对共享空间修改操作的时候，会对修改的页创建一个副本，并把父进程link到副本的内存页上面。
那么这个新页面来自于哪里？操作系统需要为这类请求提供一个页面池（page pool)。当进程的堆栈和堆要扩展或者写时复制的时候，通常分配这些空闲页面。Linux提供了系统调用fork()的变种，vfork()虚拟内存fork，这个操作不同于fork操作，采用vfork，父进程被挂起，子进程直接使用父进程的地址空间，因为没有写时复制的操作，如果子进程在运行时候对数据进行了修改，那么当恢复父进程的时候，这部分修改对父进程而言是可见的。因此应该谨慎使用vfork，当子进程使用vfork被创建的时候，应该立即调用exec，复制一份数据17。
虚拟内存管理调优手段，通常都是从页面置换算法入手。我们这里就不具体展开讨论了，可以参考，基本页面置换、FIFO页面置换、最优页面置换、LRU（最近最少使用）页面置换、近似LRU页面置换。从帧分配的角度讲，分给进程的帧数也有相应的算法，比如，比例分配等。
系统抖动（trashing），如果低优先级的进程所分配的帧数低于计算机体系结构需要的最小帧数，那么必须暂定该进程的执行。然后调出他的所有剩余页面，以便释放所有分配的帧，这个规定引入了中级CPU调度的换进换出层。在没有足够帧的进程，那么很快就会产生缺页错误。此时，必须置换页面。然而，由于它所有的页面都在使用中，并没有成功调页，返回之后继续产生缺页错误，周而复始，这个被称为系统抖动，因为调页没有成功，CPU在缺页中断中往复，并没真的使用CPU，此时CPU利用率是低的，然而CPU调度程序看到CPU利用率低，会进而增加多道程度，多道程序增加导致缺页中断队列变长，最终就导致，CPU利用率低，缺页异常队列变长，任务还没完成。这里没有硬件设备可以支持这样的操作，只能通过局部置换算法和优先级置换算法调节抖动的发生。为了防止抖动在进程上面也可以做一些工作，比如进程调度平衡分配帧数。
4. 问题回顾
Q1：在计算机的发展历史中，为什么会出现分段和分页机制？
在比较早期的计算机系统里面，没有MMU，这里可以分为单道和多道运行。单道时期，是把程序直接load到物理内存，没有进程、地址空间保护、也没有换入换出技术。后来发展出多道，多道前期使用静态分区法，程序员在编译阶段自己划分进程空间，这个阶段支持了有限的固定的多进程，也对地址空间进行了保护，但还不支持换入换出，后来发展了动态分区法，这个阶段支持了换入换出技术，所以可以允许动态加载多进程，因为是进程分别映射，所以也对地址空间进行保护，但有个非常大的弊端，就是碎片化产生，还有效率比较低。再后来就提出了基于动态加载的分段机制，分段机制是MMU概念最早的雏形，在进程上根据局部性原理对程序分段，各种代码段，分段加载。保留了动态加载的好处，因为局部性原理分段的使用，大大减少了换入换出的几率，因此提升了效率。后来在分段的基础上提出了分页，也就是我们现在用的，对段进行再分页管理。