Kernel

linux 内核内存管理-1

一、内存管理简介

内存管理的实现涵盖了许多领域 - 内存中的物理内存页的管理 - 分配大块内存的伙伴系统 - 分配较小块内存的slab、slub、slob分配器 - 分配非连续内存块的vmalloc机制 - 进程的地址空间

有两种类型计算机，分别以不同的方式管理物理内存 - 1.UMA计算机(一致内存访问，uniform memory access) 将可用内存以连续方式组织起来。SMP系统中的每一个处理器访问各个内存区域都是同样快 - 2.NUMA计算机(非一致的内存访问,non-uniform memory access)总是多处理器计算机。系统的各个CPU都有本的的内存，可以支持特别快的内存访问。各个处理器之间通过总线连接起来，以支持对其他CPU的本地访问，当然比访问本地内存慢一点。

一些名词

冷热页 :struct zone的pagent成员用于实现冷热分配器。内核说页是热的，意味该页已经加载到CPU高速缓存中,与在内存中的页相比，其数据能够更快的访问。相反，冷页则不在高速缓存中。

页帧 : 页帧代表系统内存的最小单位，对内存中的每一个页都会创建struct page的一个实例。内核程序需要保持该结构尽可能小。IA-32系统，标准页的大小为4Kb。

页表 : 层次化的页表用于支持对大地址空间的快速、高效的管理。页表用于建立用户进程的虚拟地址空间和系统物理内存(内存，页帧)之间的关联。到目前为止，讨论的结构主要用描述内存的结构，同时指定了其中包含的页帧的数量和状态。页表用于向每个进程提供一致的虚拟地址空间。应用程序看到的地址空间是一个连续的内存区。该表也将虚拟内存映射到物理内存，因而支持共享内存的实现(几个进程同时共享的内存)，还可以在不额外增加物理内存的情况下，将页换到块设备来增加有效可用的内存空间。

二.内存地址

### 1.各种地址 ###

逻辑地址
逻辑是指由程序产生的与段相关的偏移地址部分。例如，你在进行C语言指针编程中，可以读取指针变量本身值(&操作)，实际上这个值就是逻辑地址，它是相对于你当前进程数据段的地址，不和绝对物理地址相干。只有在Intel实模式下，逻辑地址才和物理地址相等（因为实模式没有分段或分页机制,Cpu不进行自动地址转换）；逻辑也就是在Intel保护模式下程序执行代码段限长内的偏移地址（假定代码段、数据段如果完全一样）。应用程序员仅需与逻辑地址打交道，而分段和分页机制对您来说是完全透明的，仅由系统编程人员涉及。应用程序员虽然自己可以直接操作内存，那也只能在操作系统给你分配的内存段操作。（也就是说，咱们应用程序中看到的地址都是逻辑地址。） 如果是程序员，那么逻辑地址对你来说应该是轻而易举就可以理解的。我们在写C代码的时候经常说我们定义的结构体首地址的偏移量，函数的入口偏移量，数组首地址等等。当我们在考究这些概念的时候，其实是相对于你这个程序而言的。并不是对于整个操作系统而言的。也就是说，逻辑地址是相对于你所编译运行的具体的程序（或者叫进程吧，事实上在运行时就是当作一个进程来执行的）而言。你的编译好的程序的入口地址可以看作是首地址，而逻辑地址我们通常可以认为是在这个程序中，编译器为我们分配好的相对于这个首地址的偏移，或者说以这个首地址为起点的一个相对的地址值。（PS：这么来看，逻辑地址就是一个段内偏移量，但是这么说违背了逻辑地址的定义，在intel段是管理中，一个逻辑地址，是由一个段标识符加上一个指定段内相对地址的偏移量，表示为 [段标识符：段内偏移量]）.
当我们双击一个可执行程序时，就是给操作系统提供了这个程序运行的入口地址。之后shell把可执行文件的地址传入内核。进入内核后，会fork一个新的进程出来，新的进程首先分配相应的内存区域。这里会碰到一个著名的概念叫做Copy On Write，即写时复制技术。这里不详细讲述，总之新的进程在fork出来之后，新的进程也就获得了整个的PCB结构，继而会调用exec函数转而去将磁盘中的代码加载到内存区域中。这时候，进程的PCB就被加入到可执行进程的队列中，当CPU调度到这个进程的时候就真正的执行了。
我们大可以把程序运行的入口地址理解为逻辑地址的起始地址，也就是说，一个程序的开始的地址。以及以后用到的程序的相关数据或者代码相对于这个起始地址的位置（这是由编译器事先安排好的），就构成了我们所说的逻辑地址。逻辑地址就是相对于一个具体的程序（事实上是一个进程，即程序真正被运行时的相对地址）而言的。这么理解在细节上有一定的偏差，只要领会即可。 总之一句话，逻辑地址是相对于应用程序而言的。 逻辑地址产生的历史背景： 追根求源，Intel的8位机8080CPU，数据总线（DB）为8位，地址总线（AB）为16位。那么这个16位地址信息也是要通过8位数据总线来传送，也是要在数据通道中的暂存器，以及在CPU中的寄存器和内存中存放的，但由于AB正好是DB的整数倍，故不会产生矛盾！ 但当上升到16位机后，Intel8086/8088CPU的设计由于当年IC集成技术和外封装及引脚技术的限制，不能超过40个引脚。但又感觉到8位机原来的地址寻址能力2^16＝64KB太少了，但直接增加到16的整数倍即令AB＝32位又是达不到的。故而只能把AB暂时增加4条成为20条。则 2^20＝1MB的寻址能力已经增加了16倍。但此举却造成了AB的20位和DB的16位之间的矛盾，20位地址信息既无法在DB上传送，又无法在16位的CPU寄存器和内存单元中存放。于是应运而生就产生了CPU段结构的原理。Intel为了兼容，将远古时代的段式内存管理方式保留了下来，也就存在了逻辑地址.

线性地址（Linear Address）
线性地址是逻辑地址到物理地址变换之间的中间层。程序代码会产生逻辑地址，或者说是段中的偏移地址，加上相应段的基地址就生成了一个线性地址。如果启用了分页机制，那么线性地址可以再经变换以产生一个物理地址。若没有启用分页机制，那么线性地址直接就是物理地址。Intel 80386的线性地址空间容量为4G（2的32次方即32根地址总线寻址）。
我们知道每台计算机有一个CPU（我们从单CPU来说吧。多CPU的情况应该是雷同的），最终所有的指令操作或者数据等等的运算都得由这个CPU来进行，而与CPU相关的寄存器就是暂存一些相关信息的存储记忆设备。因此，从CPU的角度出发的话，我们可以将计算机的相关设备或者部件简单分为两类：一是数据或指令存储记忆设备（如寄存器，内存等等），一种是数据或指令通路（如地址线，数据线等等）。线性地址的本质就是“CPU所看到的地址”。如果我们追根溯源，就会发现线性地址的就是伴随着Intel的X86体系结构的发展而产生的。当32位CPU出现的时候，它的可寻址范围达到4GB，而相对于内存大小来说，这是一个相当巨大的数字，我们也一般不会用到这么大的内存。那么这个时候CPU可见的4GB空间和内存的实际容量产生了差距。而线性地址就是用于描述CPU可见的这4GB空间。我们知道在多进程操作系统中，每个进程拥有独立的地址空间，拥有独立的资源。但对于某一个特定的时刻，只有一个进程运行于CPU之上。此时，CPU看到的就是这个进程所占用的4GB空间，就是这个线性地址。而CPU所做的操作，也是针对这个线性空间而言的。之所以叫线性空间，大概是因为人们觉得这样一个连续的空间排列成一线更加容易理解吧。其实就是CPU的可寻址范围。
对linux而言，CPU将4GB划分为两个部分，0-3GB为用户空间（也可以叫核外空间），3-4GB为内核空间（也可以叫核内空间）。操作系统相关的代码，即内核部分的代码数据都会映射到内核空间，而用户进程则会映射到用户空间。至于系统是如何将线性地址转换到实际的物理内存上，在下一篇文章讲解，无外乎段式管理和页式管理。

物理地址（Physical Address）
物理地址是指出现在CPU外部地址总线上的寻址物理内存的地址信号，是地址变换的最终结果地址。如果启用了分页机制，那么线性地址会使用页目录和页表中的项变换成物理地址。如果没有启用分页机制，那么线性地址就直接成为物理地址了。

MemoryMangement Unit负责从逻辑地址到物理地址的转化。逻辑地址是段标识+段内偏移量的形式，MMU通过查询段表，可以把逻辑地址转化为线性地址。如果cpu没有开启分页功能，那么线性地址就是物理地址；如果cpu开启了分页功能，MMU还需要查询页表来将线性地址转化为物理地址： 逻辑地址 ----（段表）---> 线性地址 — （页表）—> 物理地址
不同的逻辑地址可以映射到同一个线性地址上；不同的线性地址也可以映射到同一个物理地址上；所以是多对一的关系。另外，同一个线性地址，在发生换页以后，也可能被重新装载到另外一个物理地址上。所以这种多对一的映射关系也会随时间发生变化。

2.地址的转换

X86的地址转换（MMU）

address1.png

address2.png

段是虚拟地址空间的基本单位，段机制必须把虚拟地址空间的一个地址转换为线线地址空间的一个线性地址。 用三个方面来描述段: - 段的基地址(Base Address):在线性地址空间中段的起始地址。 - 段的界限(Limit)：在虚拟地址空间中，段内可以使用的最大偏移量 - 段的保护属性(Attribute):表示段的特性。例如：该段是否可以被读出或写入。

为了加快对这些表的访问，Intel设计了专门的寄存器，以存放这些表的基地址及表的长度界限。这些寄存器只供操作系统使用。

存放索引或叫段号，因此，这里的段寄存器也叫选择符，即从描述符中选择某个段。 address3.png

15-3表示引索号 索引号，或者直接理解成数组下标——那它总要对应一个数组吧，它又是什么东东的索引呢？这个就是“段描述符(segment descriptor)”，段描述符具体地址描述了一个。这样，很多个段描述符，就组了一个数组，叫“段描述符表”，这样，可以通过段标识符的前13位，直接在段描述符表中找到一个具体的段描述符，这个描述符就描述了一个段.看看描述符里面究竟有什么东东——也就是它究竟是如何描述的，就理解段究竟有什么东东了，每一个段描述符由8个字节组成，如下图： address4.png 

  字段名	     说明
  Base	     包含段的首字节的线性地址
  G	             粒度标志，如果为0，则段大小以字节为单位，否则以4096字节的倍数计算
  Limit  	     存放段最后一个内存单元的偏移量，从而决定段的长度。如果G被置为0，则一个段的大小在一个字节到1MB之间变化，否则，将在4KB到4GB之间变化
  S	            系统标志，如果被置为0，则这是一个系统段，否则为普通的代码段或者数据段      
  Type	    描述了段的类型特征和它的存取权限                      
  DPL	    描述符特权等级字段，用于限制这个段的存取。它表示为访问这个段而要求的CPU最小的优先级，因此DPL设置为0的段只能当CPL为0时，也就是内核态才可以访问。DPL设为3则堆任何CPL值都是可访问的                 
  P	            Segment-Present标志，等于0表示段当前不在主存中。Linux总是把此标志设为1，因为Linux从来不把整个段交换到磁盘上去
  D或B	    称为D或B标志，取决于是代码段还是数据段，D和B的含义在两种情况下有区别，如果段偏移量的地址是32位长，就基本上把它设置为1，如果偏移量是16位长，则清零
  AVL	   可以由操作系统使用，但是被Linux忽略

TI表示GDT/LDT的选择，TI=0，表示用GDT，TI=1表示用LDT。GDT在内存中的地址和大小存放在CPU的gdtr控制寄存器中，而LDT则在ldtr寄存器中。

address5.png

3.linux的段管理

Linux的段式管理，事实上只是“哄骗”了一下硬件而已。 按照Intel的本意，全局的用GDT，每个进程自己的用LDT——不过Linux则对所有的进程都使用了相同的段来对指令和数据寻址。即用户数据段，用户代码段，对应的，内核中的是内核数据段和内核代码段。 按照Intel的本意，全局的用GDT，每个进程自己的用LDT——不过Linux则对所有的进程都使用了相同的段来对指令和数据寻址。即用户数据段，用户代码段，对应的，内核中的是内核数据段和内核代码段。

#define GDT_ENTRY_DEFAULT_USER_CS        14
#define __USER_CS (GDT_ENTRY_DEFAULT_USER_CS * 8 + 3)

#define GDT_ENTRY_DEFAULT_USER_DS        15
#define __USER_DS (GDT_ENTRY_DEFAULT_USER_DS * 8 + 3)

#define GDT_ENTRY_KERNEL_BASE        12

#define GDT_ENTRY_KERNEL_CS                (GDT_ENTRY_KERNEL_BASE + 0)
#define __KERNEL_CS (GDT_ENTRY_KERNEL_CS * 8)

#define GDT_ENTRY_KERNEL_DS                (GDT_ENTRY_KERNEL_BASE + 1)
#define __KERNEL_DS (GDT_ENTRY_KERNEL_DS * 8)

上面的宏计算后如下:

#define __USER_CS 115        [00000000 1110  0  11]
#define __USER_DS 123        [00000000 1111  0  11]
#define __KERNEL_CS 96       [00000000 1100  0  00]
#define __KERNEL_DS 104      [00000000 1101  0  00]

方括号后是这四个段选择符的16位二制表示，它们的索引号和T1字段值也可以算出来了

> __USER_CS               index= 14   T1=0
> __USER_DS               index= 15   T1=0
> __KERNEL_CS             index= 12   T1=0
> __KERNEL_DS             index= 13   T1=0

T1均为0，则表示都使用了GDT，再来看初始化GDT的内容中相应的12-15项(arch/i386/head.S)：

> .quad 0x00cf9a000000ffff        /* 0x60 kernel 4GB code at 0x00000000 */
> .quad 0x00cf92000000ffff        /* 0x68 kernel 4GB data at 0x00000000 */
> .quad 0x00cffa000000ffff        /* 0x73 user 4GB code at 0x00000000 */
> .quad 0x00cff2000000ffff        /* 0x7b user 4GB data at 0x00000000 */

这样，给定一个段内偏移地址，按照前面转换公式，0 + 段内偏移，转换为线性地址，可以得出重要的结论，“在Linux下，逻辑地址与线性地址总是一致（是一致，不是有些人说的相同）的，即逻辑地址的偏移量字段的值与线性地址的值总是相同的。！！！”

4.linux页表管理

页表概述
在虚拟内存中，页表是个映射表的概念, 即从进程能理解的线性地址(linear address)映射到存储器上的物理地址(phisical address)。很显然，这个页表是需要常驻内存的东西, 以应对频繁的查询映射需要(实际上，现代支持VM的处理器都有一个叫TLB的硬件级页表缓存部件，本文不讨论）。

设想一个典型的32位的X86系统，它的虚拟内存用户空间(user space)大小为3G, 并且典型的一个页表项(page table entry, pte)大小为4 bytes，每一个页(page)大小为4k bytes。那么这3G空间一共有(3G/4k=)786432个页面，每个页面需要一个pte来保存映射信息，这样一共需要786432个pte!

如何存储这些信息呢？一个直观的做法是用数组来存储，这样每个页能存储(4k/4=)1K个，这样一共需要(786432/1k=)768个连续的物理页面(phsical page)。而且，这只是一个进程，如果要存放所有N个进程，这个数目还要乘上N! 这是个巨大的数目，哪怕内存能提供这样数量的空间，要找到连续768个连续的物理页面在系统运行一段时间后碎片化的情况下，也是不现实的

linux的页表实现
上面这种理论上的讨论显然不是实际情况。由于程序存在局部化特征, 这意味着在特定的时间内只有部分内存会被频繁访问，具体点，进程空间中的text段(即程序代码), 堆， 共享库，栈都是固定在进程空间的某个特定部分，这样导致进程空间其实是非常稀疏的, 于是，从硬件层面开始，页表的实现就是采用分级页表的方式，Linux内核当然也这么做。所谓分级简单说就是，把整个进程空间分成区块，区块下面可以再细分，这样在内存中只要常驻某个区块的页表即可，这样可以大量节省内存。

address6.png

二级页表

2-level-table2

2-level-table 一个32位虚拟地址如上图划分。当在进行地址转换时，

address7.png

  • 结合在CR3寄存器中存放的页目录(page directory, PGD)的这一页的物理地址，再加上从虚拟地址中抽出高10位叫做页目录表项(内核也称这为pgd)的部分作为偏移, 即定位到可以描述该地址的pgd;

  • 从该pgd中可以获取可以描述该地址的页表的物理地址，再加上从虚拟地址中抽取中间10位作为偏移, 即定位到可以描述该地址的pte;

  • 在这个pte中即可获取该地址对应的页的物理地址, 加上从虚拟地址中抽取的最后12位，即形成该页的页内偏移, 即可最终完成从虚拟地址到物理地址的转换。 从上述过程中，可以看出，对虚拟地址的分级解析过程，实际上就是不断深入页表层次，逐渐定位到最终地址的过程，所以这一过程被叫做page talbe walk。

** 举个例子 **
- 假如操作系统给一个正在运行的进程分配的线性地址空间范围是0x20000000~0x2003fff.这个空间由64页组成. - 从分配给进程的线性地址的最高10位(分页硬件机制把它自动解析成页目录域)开始。这两个地址都是以2开头，后面跟着0,因此高10位有相同的值，即十六进制的0x080或十进制的128.因此，这两个地址的页目录域都指向进程页目录的第129项。相应的目录项中必须包含分配给进程的页表的物理地址。如果给这个进程没有分配其它的线性地址，则页目录的其余1023项都为0.则该进程在页目录只占一项。

address8.png 至于这种做法为什么能节省内存，举个更简单的例子更容易明白。比如要记录16个球场的使用情况，每张纸能记录4个场地的情况。采用4+4+4+4，共4张纸即可记录，但问题是球场使用得很少，有时候一整张纸记录的4个球场都没人使用。于是，采用4 x 4方案，即把16个球场分为4组，同样每张纸刚好能记录4组情况。这样，使用一张纸A来记录4个分组球场情况，当某个球场在使用时，只要额外使用多一张纸B来记录该球场，同时，在A上记录”某球场由纸B在记录”即可。这样在大部分球场使用很少的情况下，只要很少的纸即困记录，当有球场被使用，有需要再用额外的纸来记录，当不用就擦除。这里一个很重要的前提就是:局部性。

三级页表

当X86引入物理地址扩展(Pisycal Addrress Extension, PAE)后，可以支持大于4G的物理内存(36位），但虚拟地址依然是32位，原先的页表项不适用，它实际多4 bytes被扩充到8 bytes，这意味着，每一页现在能存放的pte数目从1024变成512了(4k/8)。相应地，页表层级发生了变化，Linus新增加了一个层级，叫做页中间目录(page middle directory, PMD), 变成：

**四级页表**
4-level-table.png

在2004年10月，当时的X86_64架构代码的维护者Andi Kleen提交了一个叫做4level page tables for Linux的PATCH系列，为Linux内核带来了4级页表的支持。在他的解决方案中，不出意料地，按照X86_64规范，新增了一个PML4的层级, 在这种解决方案中，X86_64拥一个有512条目的PML4, 512条目的PGD, 512条目的PMD, 512条目的PTE。对于仍使用3级目录的架构来说，它们依然拥有一个虚拟的PML4,相关的代码会在编译时被优化掉。 这样，就把Linux内核的3级列表扩充为4级列表。这系列PATCH工作得不错，不久被纳入Andrew Morton的-mm树接受测试。

从硬件的角度，32位地址被分成了三部份——也就是说，不管理软件怎么做，最终落实到硬件，也只认识这三位老大。 从软件的角度，由于多引入了两部份，，也就是说，共有五部份。——要让二层架构的硬件认识五部份也很容易，在地址划分的时候，将页上级目录和页中间目录的长度设置为0就可以了。 这样，操作系统见到的是五部份，硬件还是按它死板的三部份划分，也不会出错，也就是说大家共建了和谐计算机系统

这样，虽说是多此一举，但是考虑到64位地址，使用四层转换架构的CPU，我们就不再把中间两个设为0了，这样，软件与硬件再次和谐——抽像就是强大呀！！！ 例如，一个逻辑地址已经被转换成了线性地址，0x08147258，换成二制进，也就是： 0000100000 0101000111 001001011000
内核对这个地址进行划分
PGD = 0000100000
PUD = 0
PMD = 0
PT = 0101000111
offset = 001001011000

现在来理解Linux针对硬件的花招，因为硬件根本看不到所谓PUD,PMD，所以，本质上要求PGD索引，直接就对应了PT的地址。而不是再到PUD和PMD中去查数组（虽然它们两个在线性地址中，长度为0，2^0 =1，也就是说，它们都是有一个数组元素的数组），那么，内核如何合理安排地址呢？ 从软件的角度上来讲，因为它的项只有一个，32位，刚好可以存放与PGD中长度一样的地址指针。那么所谓先到PUD，到到PMD中做映射转换，就变成了保持原值不变，一一转手就可以了。这样，就实现了“逻辑上指向一个PUD，再指向一个PDM，但在物理上是直接指向相应的PT的这个抽像，因为硬件根本不知道有PUD、PMD这个东西”。

然后交给硬件，硬件对这个地址进行划分，看到的是：
页目录 = 0000100000
PT = 0101000111
offset = 001001011000
嗯，先根据0000100000(32)，在页目录数组中索引，找到其元素中的地址，取其高20位，找到页表的地址，页表的地址是由内核动态分配的，接着，再加一个offset，就是最终的物理地址了。

总结

  • linux 采用分页存储管理。虚拟地址空间划分成固定的“页”，由MMU在运行时将虚拟地址映射成某个物理页面中的地址。
  • IA32的MMU对程序中的虚拟地址先进行段式映射(虚拟地址转线性地址)，然后才能进行页式映射(线性地址转换为物理地址)
  • linux巧妙地使段式映射实际上不起什么作用。