第八章--内存管理

        整个系统的性能取决于如何有效地管理动态内存。因此，现在所有多任务操作系统都在尽力优化对动态内存的使用，也就是说，尽可能做到当需要时分配，不需要时释放。
一、页框管理
        Linux采用4KB页框大小作为标准的内存分配单元。基于以下两个原因，这会使事情变得简单：
        * 由分页单元引发的缺页异常很容易得到解释，或者是由于请求的页存在但不允许进程对其访问，或者是由于请求的页不存在。在第二种情况下，内存分配器必须找到一个4KB的空闲页框，并将其分配给进程。
        * 虽然4KB和4MB都是磁盘块大小的倍数，但是在绝大多数情况下，当主存和磁盘之间传输小数据块更高效。
1.1、页描述符
        内核必须记录每个页框当前的状态。例如，内核必须能区分哪些页框包含的是属于进程的页，而哪些页框包含的是内核代码或内核数据。类似地，内核还必须能够确定动态内存中的页框是否空闲。如果动态内存中的页框不包含有用的数据，那么这个页框就是空闲的。在以下情况下页框是不空闲的：包含用户态进程的数据、某个软件高速缓存的数据、动态分配的内核数据结构、设备驱动程序缓冲的数据、内核模块的代码等等。
        页框的状态信息保存在一个类型为page的页描述符中，所有的页描述符存放在mem_map数组中。因为每个描述符长度为32字节，所以mem_map所需要的空间略小于整个RAM的1%。virt_to_page(addr)宏产生线性地址addr对应的页描述符地址。pfn_to_page(pfn)宏产生与页框号pfn对应的页描述符地址。
1.2、非一致内存访问(NUMA)
          Linux2.6支持非一致内存访问(Non-Uniform Memory Access，NUMA)模型，在这种模型中，给定CPU对不同内存单元的访问时间可能不一样。系统的物理内存被划分为几个节点(node)。在一个单独的节点内，任一给定CPU访问页面所需的时间都是相同的。然而，对不同的CPU，这个时间可能就不同。对每个CPU而言，内核都试图把耗时节点的访问次数减到最少，这就要小心地选择CPU最常引用的内核数据结构的存放位置。
        在80x86结构中，把物理内存分组在一个单独的节点中可能显得没有用处；但是，这种方式有助于内存代码的处理更具有可移植性，因为内核假定在所有的体系结构中物理内存都被划分为一个或多个节点。
1.3、内存管理区
        在一个理想的计算机体系结构中，一个页框就是一个内存存储单元，可用于任何事情：存放内核数据和用户数据、缓冲磁盘数据等等。任何种类的数据页都可以存放在任何页框中，没有什么限制。
        但是，实际的计算机体系结构有硬件的制约，这限制了页框可以使用的方式，尤其是，Linux内核必须处理80x86体系结构的两种硬件约束：
        * ISA总线的直接内存存取(DMA)处理器有一个严格的限制：它们只能对RAM的前16MB寻址。
        * 在具有大容量RAM的现代32位计算机中，CPU不能直接访问所有的物理内存，因为线性地址空间太小。
        为了应对这两种限制，Linux2.6把每个内存节点的物理内存划分为3个管理区(zone)。在80x86 UMA体系结构中的管理区为：
        ZONE_DMA：包含低于16MB的内存页框。
        ZONE_NORMAL：包含高于16MB且低于896MB的内存页框。
        ZONE_HIGHMEM：包含从896MB开始高于896MB的内存页框。
        ZONE_DMA区包含的页框可以由老式基于ISA的设备通过DMA使用。
        ZONE_DMA和ZONE_NORMAL区包含内存的“常规”页框，通过把它们线性地址映射到线性地址空间的第4个GB，内核就可以直接进行访问。相反，ZONE_HIGHMEM区包含的内存页不能由内核直接访问，尽管它们也线性地映射到了线性地址空间的第4个GB。在64位体系结构上ZONE_HIGHMEM区总是空的。
        当内核调用一个内存分配函数时，必须指明请求页框所在的管理区。内核通常指明它愿意使用哪个管理区。
1.4、保留的页框池
        可以用两种不同的方法来满足内存分配请求。如果有足够的空闲内存可用，请求就会被立刻满足。否则，必须回收一些内存，并且将发出请求的内核控制路径阻塞，直到有内存被释放。
        当请求内存时，一些内核控制路径不能被阻塞。例如，这种情况发生在处理中断或在执行临界区内的代码时。在这些情况下，一条内核控制路径应当产生原子内存分配请求(使用GFP_ATOMIC标志)。原子请求从不被阻塞：如果没有足够的空闲页，则仅仅是分配失败而已。
        内核为原子内存分配请求保留了一个页框池，只有在内存不足时才使用。
1.5、分区页框分配器
        被称作分区页框分配器(zoned page frame allocator)的内核子系统，处理对连续页框组的内存分配请求。
1.5.1、请求和释放页框
        可以通过6个稍有差别的函数和宏请求页框。除非另作说明，一般情况下，它们都返回第一个所分配页的线性地址，或者如果分配失败，则返回NULL。
        后备管理区：对管理区修饰符的每一个设置，相应的链表包含的内存管理区能在原来的管理区缺少页框的情况下被用于满足内存分配请求。在80x86 UMA体系结构中，后备管理区如下：
        * 如果__GFP_DMA标志被置位，则只能从ZONE_DMA内存管理区获取页框。
        * 否则，如果__GFP_HIGHMEM标志没有被置位，则只能按优先次序从ZONE_NORMAL和ZONE_DMA内存管理区获取页框。
        * 否则(__GFP_HIGHMEM标志被置位)，则可以按优先次序对ZONE_HIGHMEM、ZONE_NORMAL和ZONE_DMA内存管理区获得页框。
1.6、高端内存页框的内核映射
        与直接映射的物理内存末端、高端内存的始端所对应的线性地址存放在high_memory变量中，它被设置为896MB。896MB边界以上的页框并不映射在内核线性地址空间的第4个GB，因此，内核不能直接访问它们。这就意味着，返回所分配页框线性地址的页分配器函数不适用于高端内存，即不适用于ZONE_HIGHMEM内存管理区内的页框。
        内核可以采用三种不同的机制将页框映射到高端内存；分别叫做永久内核映射、临时内核映射及非连续内存分配。
        建立永久内核映射可能阻塞当前进程；这发生在空闲页表项不存在时，也就是在高端内存上没有页表项可以用作页框的“窗口”时。因此，永久内核映射不能用于中断处理程序和可延迟函数。相反，建立临时内核映射绝不会要求阻塞当前进程；不过，它的缺点是只有很少的临时内核映射可以同时建立起来。
        使用临时内核映射的内核控制路径必须保证当前没有其他的内核控制路径在使用同样的映射。这意味着内核控制路径永远不能被阻塞，否则其他内核控制路径有可能使用同一个窗口来映射其他的高端内存页。
1.6.1、永久内核映射

1.6.2、临时内核映射
        临时内核映射比永久内核映射的实现要简单；此外，它们可以用在中断处理程序和可延迟函数的内部，因为它们从不阻塞当前进程。
        在高端内存的任一页框都可以通过一个“窗口”(为此而保留的一个页表项)映射到内核地址空间。留给临时内核映射的窗口数是非常少的。
1.7、伙伴系统算法
        从本质上说，避免外碎片的方法有两种：
        * 利用分页单元把一组非连续的空闲页框映射到连续的线性地址空间。
        * 开发一种适当的技术来记录现存的空闲连续页框块的情况，以尽量避免为满足对小块的请求而分割大的空闲块。
          基于以下三种原因，内核首选第二种方法：
          * 在某些情况下，连续的页框确实是必要的，因为连续的线性地址不足以满足请求。一个典型的例子就是给DMA处理器分配缓冲区的内存请求。因为当在一次单独的I/O操作中传送几个磁盘扇区的数据时，DMA忽略分页单元而直接访问地址总线，因此，所请求的缓冲区就必须位于连续的页框中。
          * 即使连续页框的分配并不是很必要，但它在保持内核页表不变方面所起的作用也是不容忽视的。修改页表会怎样呢？从第二章我们知道，频繁地修改页表势必导致平均访问内存次数的增加，因为这会使CPU频繁地刷新转换后援缓冲器(TLB)的内容。
          * 内核通过4MB的页可以访问大块连续的物理内存。这样减少了转换后援缓冲器失效率，因此提高了访问内存的平均速度。
        Linux采用著名的伙伴系统(buddy system)算法来解决外碎片问题。把所有的空闲页框分组为11个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512和1024个连续的页框。对1024个页框的最大请求对应着4MB大小的连续RAM块。每个块的第一个页框的物理地址是该块大小的整数倍。
1.7.1、数据结构

1.7.2、分配块

1.7.3、释放块

1.8、每CPU页框高速缓存
        为了提升系统性能，每个内存管理区定义了一个“每CPU”页框高速缓存。所有“每CPU”高速缓存包含一些预先分配的页框，它们被用于满足本地CPU发出的单一内存请求。
        这里为每个内存管理区和每个CPU提供了两个高速缓存：一个热高速缓存，它存放的页框中所包含的内容很可能就在CPU硬件高速缓存中；还有一个冷高速缓存。
1.8.1、通过每CPU页框高速缓存分配页框

1.8.2、释放页框到每CPU页框高速缓存
        应该注意的是，在当前的Linux2.6内核版本中，从没有页框被释放到冷高速缓存中：至于硬件高速缓存，内核总是假设被释放的页框是热的。当然，这并不意味着冷高速缓存是空的：当达到下界时通过buffered_rmqueue()补充冷高速缓存。
1.9、管理区分配器
        管理区分配器是内核页框分配器的前端。该成分必须分配一个包含足够多空闲页框的内存管理区，使他能满足内存请求。管理区分配器必须满足几个目标：
        * 它应当保护保留的页框池。
        * 当内存不足且允许阻塞当前进程时，它应当触发页框回收算法；一旦某些页框被释放，管理区分配器将再次尝试分配。
        * 如果可能，它应当保存小而珍贵的ZONE_DMA内存管理区。例如，如果是对ZONE_NORMAL或ZONE_HIGHMEM页框的请求，那么管理区分配器会不太愿意分配ZONE_DMA内存管理区中的页框。

1.9.1、释放一组页框

二、内存区管理
        本章讨论具有连续的物理地址和任意长度的内存单元。
        伙伴系统算法采用页框作为基本内存区，这适合对大块内存的请求，但如果处理对小内存区的请求，比如说几十或几百个字节就不好用了。
        内碎片的产生主要是由于请求内存的大小与分配给它的大小不匹配而造成的。
2.1、slab分配器

2.2、高速缓存描述符

2.3、slab描述符

2.4、普通和专用高速缓存
        高速缓存被分为两种类型：普通和专用。普通高速缓存只由slab分配器用于自己的目的，而专用高速缓存由内核的其余部分使用。
        所有普通和专用高速缓存的名字都可以在运行期间通过读取/proc/slabinfo文件得到。这个文件也指明每个高速缓存中空闲对象的个数和已分配对象的个数。
2.5、slab分配器与分区页框分配器的接口
        当slab分配器创建新的slab时，它依靠分区页框分配器来获得一组连续的空闲页框。为了达到此目的，它调用kmem_getpages()函数。

2.6、给高速缓存分配slab
        一个新创建的高速缓存没有包含任何slab，因此也没有空闲对象，只有当以下两个条件都为真时，才给高速缓存分配slab：
        * 已发出一个分配新对象的请求。
        * 高速缓存不包含任何空闲对象。

2.7、从高速缓存中释放slab
        在两种条件下才能撤销slab：
        * slab高速缓存中有太多的空闲对象。
        * 被周期性调用的定时器函数确定是否有完全未使用的slab能被释放。

2.8、对象描述符
        每个对象都有类型为kmem_bufctl_t的一个描述符。对象描述符存放在一个数组中，位于相应的slab描述符之后。因此，与slab描述符本身类似，slab的对象描述符也可以用两种可能的方式来存放。
        外部对象描述符：存放在slab的外面，位于高速缓存描述符的slabp_cache字段指向的一个普通高速缓存中。内存区的大小(尤其是存放对象描述符的普通高速缓存的大小)取决于在slab中所存放的对象个数(高速缓存描述符的num字段)。
        内部对象描述符：存放在slab内部，正好位于描述符所描述的对象之前。
2.9、对齐内存中的对象
        slab分配器所管理的对象可以在内存中进行对其，也就是说，存放它们的内存单元的起始物理地址是一个给定常量的倍数，通常是2的倍数。这个常量就叫对齐因子(alignment factor)。
        slab分配器所允许的最大对齐因子是4096，即页框大小。这就意味着通过访问对象的物理地址或线性地址就可以对其对象。在这两种情况下，只有最低的12位才可以通过对其来改变。

2.10、slab着色
        slab分配器利用空闲未用的字节free来对slab着色。术语“着色”只是用来再细分slab，并允许内存分配器把对象展开在不同的线性地址之中。这样的话，内核从微处理器的硬件高速缓存中可能获得最好性能。

2.11、空闲slab对象的本地高速缓存
        高速缓存描述符的array字段是一组指向array_cache数据结构的指针，系统中的每个CPU对应于一个元素。每个array_cache数据结构是空闲对象的本地高速缓存的一个描述符。
        注意，本地高速缓存描述符并不包含本地高速缓存本身的地址；事实上，它正好位于描述符之后。当然，本地高速缓存存放的是指向已释放对象的指针，而不是对象本身，对象本身总是位于高速缓存的slab中。
        在多处理器系统中，小对象使用的slab高速缓存同样包含一个附加的本地高速缓存，它的地址被存放在高速缓存描述符的list.shared字段中。共享的本地高速缓存正如它的名字暗示的那样，被所有CPU共享，它使得将空闲对象从一个本地高速缓存移动到另一个高速缓存的任务更容易。它的初始化大小等于batchcount字段的值的8倍。
2.12、分配slab对象
        通过调用kmem_cache_alloc()函数可以获得新对象。参数cachep指向高速缓存描述符，新空闲对象必须从该高速缓存描述符获得，而参数flag表示传递给分区页框分配器函数的标志，该高速缓存的所有slab应当是满的。

2.13、释放slab对象
        kmem_cache_free()函数释放一个曾经由slab分配器分配给某个内核函数的对象，它的参数为cachep和objp，前者是高速缓存描述符的地址，而后者是将被释放对象的地址。

2.14、通用对象

2.15、内存池
        不应该将内存池与前面“保留的页框池”一节中描述的保留页框混淆。实际上这些页框只能用于满足中断处理程序或内部临界区发出的原子内存分配请求。而内存池是动态内存的储备，只能被特定的内核成分(即池的“拥有者”)使用。拥有者通常不使用储备；但是，如果动态内存变得极其稀有以至于所有普通内存分配请求都将失败的话，那么作为最后的解决手段，内核成分就能调用特定的内存池函数提取储备得到所需的内存。因此，创建一个内存池就像手头存放一些罐装食物作为储备，当没有新鲜食物时就使用开罐器。
        一个内存池常常叠加在slab分配器之上----也就是说，它被用来保存slab对象的储备。但是一般而言，内存池能被用来分配任何一种类型的动态内存，从整个页框到使用kmalloc()分配的小内存区。因此，我们一般将内存池处理的内存单元看作“内存元素”。

三、非连续内存区管理
        通过连续的线性地址来访问非连续的页框这样一种分配模式会很有意义。这种模式的主要优点是避免了外碎片，而缺点是必须打乱内核页表。
3.1、非连续内存区的线性地址
        要查找线性地址的一个空闲区，我们可以用PAGE_OFFSET开始查找(通常为0xc000 0000，即第4个GB的起始地址)。下图显示了如何使用第4个GB的线性地址：
        * 内存区的开始部分包含的是对前896MB RAM进行映射的线性地址；直接映射的物理内存末尾所对应的线性地址保存在high_memory变量中。
        * 内存区的结尾部分包含的是固定映射的线性地址。
        * 从PKMAP_BASE开始，我们查找用于高端内存页框的永久内核映射的线性地址。
        * 其余的线性地址可以用于非连续内存区。在物理内存映射的末尾与第一个内存区之间插入一个大小为8MB(宏VMALLOC_OFFSET)的安全区，目的是为了“捕获”对内存的越界访问。出于同样的理由，插入其他4KB大小的安全区来隔离非连续的内存区。
        为非连续内存区保留的线性地址空间的起始地址由VMALLOC_START宏定义，而末尾地址由VMALLOC_END宏定义。
3.2、非连续内存区的描述符
        每个非连续内存区都对应着一个类型为vm_struct的描述符。

3.3、分配非连续内存区

3.4、释放非连续内存区