内存寻址

最近学习《深入理解LINUX内核》内存寻址，本文对此知识做个总结。主要介绍80x86微处理器怎样进行芯片级的内存寻址，Linux(内核版本为2.6.11)又是如何利用寻址硬件的。

内存地址：

逻辑地址：包含在机器语言指令中用来指定一个操作数或一条指令的地址。每一个逻辑地址都由一个段（segment）和偏移量（offset）组成。
线性地址：32位无符号整数，可用来表示高达4GB的地址。范围是0x00000000到0xffffffff。
物理地址：用于内存芯片级内存单元寻址。由32位或36位无符号整数表示。

内存控制单元（MMU）通过一种称为分段单元的硬件电路把一个逻辑地址转换成线性地址；接着，再通过分页单元的硬件电路把线性地址转换成一个物理地址。

硬件中的分段

段标识符

一个逻辑地址由两部分组成：一个段标识符和一个指定段内相对地址的偏移量。
段标识符， 段标识符是由一个16位长的字段组成，称为段选择符。其中前13位是一个索引号。后面3位包含一些硬件细节。

为了快速方便地找到段选择符，处理器提供段寄存器，段寄存器的唯一目的是存放段选择符。这些段寄存器称为cs、ss、ds、es、fs和gs。尽管只有6个段寄存器，但程序可以把同一个段寄存器用于不同的目的，方法是先将其值保存在内存中，用完后再恢复。

下面三个段寄存器有专门的用途：

cs：代码段寄存器，指向包含程序指令的段。
ss：栈段寄存器，指向包含当前程序栈的段。
ds：数据段寄存器，指向包含静态数据或者全局数据段。

其它三个段寄存器作一般用途，可以指向任意的数据段。

段描述符

每个段由一个8字节的段描述符表示。它放在全局描述符（GDT）中或局部描述符（LDT）中。有几种不同类型的段和它们的段描述符如下：

理解： 段标识符的前13位，直接在段描述符表中找到一个具体的段描述符，这个描述符就描述了一个段。

快速访问段描述符

每当一个段选择符被装入段寄存器时，会从段描述符表中选中一个段描述符，由内存装入到非编程CPU寄存器中。

Intel设计的本意是，一些全局的段描述符，就放在“全局段描述符表(GDT)”中，一些局部的，例如每个进程自己的，就放在所谓的“局部段描述符表(LDT)”中。那究竟什么时候该用GDT，什么时候该用LDT呢？这是由段选择符中的T1字段表示的，=0，表示用GDT，=1表示用LDT。

GDT在内存中的地址和大小存放在CPU的gdtr控制寄存器中，而LDT则在ldtr寄存器中。

由于段描述符是8字节长，因此它在GDT或LDT内的相对地址是由段选择符的最高13位的值乘以8得到的。例如：如果GDT在0x00020000，且由段选择符所指定的索引号为2，那么相应的段描述符的地址是0x00020000 + ( 2 x 8 ).

分段单元

那么逻辑地址是怎样转换成线性地址的？如图所示

首先，给定一个完整的逻辑地址[段选择符：段内偏移地址]，

1、看段选择符的T1=0还是1，知道当前要转换是GDT中的段，还是LDT中的段，再根据相应寄存器，得到线性基地址。
2、从段选择符的index字段（前13位）计算段描述符的地址，计算公式：index字段的值 x 8(一个段描述符的大小) + 上面的线性基地址。
3、把逻辑地址的偏移量offset + 段描述符Base字段的值 = 线性地址。

以上都是基于80x86微处理器描述的，那么Linux是怎么分段的呢？

Linux中的分段

Intel要求两次转换，这样虽说是兼容了，但是却是很冗余，呵呵，没办法，硬件要求这样做了，软件就只能照办，怎么着也得形式主义一样。
另一方面，其它某些硬件平台，没有二次转换的概念，Linux也需要提供一个高层抽象，来提供一个统一的界面。所以，Linux的段式管理，事实上只是“哄骗”了一下硬件而已。

按照Intel的本意，全局的用GDT，每个进程自己的用LDT——不过Linux则对所有的进程都使用了相同的段来对指令和数据寻址。即用户数据段，用户代码段，对应的，内核中的是内核数据段和内核代码段。这样做没有什么奇怪的，本来就是走形式嘛，像我们写年终总结一样。

Linux只使用了四个主要的段类对指令和数据寻址。

段	Base	G	Limit	S	Type	DPL	D/B	P
用户代码段	0x00000000	1	0xfffff	1	10	3	1	1
用户数据段	0x00000000	1	0xfffff	1	2	3	1	1
内核代码段	0x00000000	1	0xfffff	1	10	0	1	1
内核数据段	0x00000000	1	0xfffff	1	2	0	1	1

所有的段都是从0x00000000开始的，那就是说Linux下逻辑地址和线性地址是一致的。 即逻辑地址的偏移量字段的值与线性地址的值总是相同的。

硬件中的分页

CPU的页式内存管理单元，负责把一个线性地址，最终翻译为一个物理地址。从管理和效率的角度出发，
线性地址被分为以固定长度为单位的组，称为页(page)，
分页单元把所有的RAM分成固定长度的页框（page frame）,每一个页框包含一个页，一个页框的长度和一个页的长度一致。
把线性地址映射到物理地址的数据结构称为页表（page table）。

理解：页是一组线性地址，是指包含在这组地址地址中的数据块，可以存放在任何页框或磁盘中。页框是主存的一部分，是一个存储区域。页表是数据结构，存在在主存中。

常规分页

32位的线性地址被分成3个域：
Directory(目录)：最高10位 Table(页表)：中间10位 Offset(偏移量)：最低12位

使用二级模式的目的在于减少每个进程页表所需RAM的数量。如果使用一级页表，那将需要高达$2^{20}$（32位系统，线性地址最大为4GB，每个页4KB，可分成$2^{20}$个页，每个页的地址占4个字节，级需要4MB RAM来存储）个表项。

每个活动进程必须有一个分配给它的页目录。没有必要马上为进程的所有页表都分配RAM.

通过控制寄存器cr3获取页目录的物理地址（ 操作系统负责在调度进程的时候，把这个地址装入寄存器），通过Directory字段找到页目录中的目录项，目录项存放的是页表的基地址，通过Table字段找到页表表项，表项存放的是页框的物理地址。通过Offset字段又找到页框的相对位置。offset有12位长，故每一页框含有4096字节的数据。

Directory字段和Table字段都是10位长，因此页目录和页表都可以多达1024项。那么一个页目录可以寻址到高达$1024 1024 4096 = 2^{32}$个存储单元，这和你对32位地址所期望的一样。

常规分页举例

假定内核给一个正在运行的进程分配的线性地址空间范围0x20000000到0x2003ffff。这个空间正好是是由64页组成（0x2003ffff - 0x20000000 + 1）/ 4K = 64)。
这两个线性地址的最高10位（Directory字段）的值为0x080或十进制的128，即都指向进程页目录的第129项。该目录项中包含了分配给该进程的页表的物理地址。如果没有给这个进程分配其他的线性地址，则页目录的其余1023项都填0。
中间的10位（Table字段）范围从0~0x03f，十进制即从0到63。因而只有页表的前64个表项是有意义的，其余960个表项都填0。

假设进程需要读线性地址0x20021406中的字节，步骤为：

1、Directory字段0x80选择页目录的第0x80目录项，该目录项存放的是页表的物理基地址
2、Table字段0x21选择页表的第0x21表项，该表项存放的是页框的物理基地址
3、最后，Offset字段0x406用于在目标页框中读偏移量位0x406中的字节

如果页表第0x21表项的Present标志为0，则此页就不在主存中。分页单元在线性地址转换的同时产生一个缺页异常。

扩展分页

从Pentium模型开始，80x86引入了扩展分页，它允许页框大小为4MB而不是4KB。扩展分页用于把大段连续的线性地址转换成相应的物理地址，在这些情况下，内核可以不用中间页表进行地址转换，节省内存并保留TLB项。

通过设置页目录项的Page Size标志启用扩展分页功能。分页单元把32位线性地址分成两个字段：
Directory(目录)：最高10位 Offset(偏移量)：其余22位

物理地址扩展（PAE）分页机制

处理器所支持的RAM容量受连接到地址总线上的地址管脚数限制。Intel通过在它的处理器上把管脚数从32增加到36。让寻址能力从4G（$2^{32}$）提升到64G（$2^{36}$）。

1、64GB的RAM被分为$2^{24}$个页框，页表项的物理地址字段从20位扩展到了24位。 所以PAE的页表项为64位，所以一个4KB的页表只能包含512个表项。
2、引入页目录指针表（Page Directory Pointer Table，PDPT）的页表新级别，它由4个64位表项组成。
3、cr3控制寄存器包含一个27位的页目录指针表（PDPT）基地址字段。

未启用PAE下2M分页的页表结构：

启用PAE下4K分页的页表结构

线性地址的映射过程如下：

1、cr3：指向一个PDPT基地址
2、地址的31～30：确定PDPT项
3、地址的29～21：确定页目录项中的一个
此处，发生了分支：

A.如果页目录项的PS标志位等于0，那么页大小是4K
4）地址的20～12：确定页表的某一项
5）地址的11～0：确定偏移
B. 如果PS=1，启用大页
4）地址的20～0：确定2M页中的偏移量。

总之，一旦cr3被设置，就可能寻址高达4GB RAM。如果我们希望对更多的RAM寻址，就必须在cr3中放置一个新值，或该表PDPT的内容。然而，使用PAE的主要问题是线性地址仍然32位长。这就迫使内核编程人员用同一线性地址映射到不同的RAM区。很明显，PAE并没有扩大进程的线性地址空间，因为它只处理物理地址。此外，只有内核能够修改进程的页表，所以在用户态下运行的进程不能使用大于4GB的物理地址空间。另一方面，PAE允许内核使用容量高达64GB的RAM，从而显著增加了系统中的进程数量。

64位系统中的分页

32位处理器普遍采用两级分页。然而两级分页并不适用于采用64位系统的计算机。
原因如下 :
首先假设一个大小为4KB的标准页，4KB覆盖$2^{12}$个地址，所以offset字段是12位。如果我们现在决定仅仅使用64位中的48位来寻址(这个限制仍然能使我们自在地拥有256TB的寻址空间！)，剩下的48-12=36位被分配给Table和Directory字段。如果我们决定为两个字段各预留18位，那么每个进程的页目录和页表都含有$2^{18}$个项，即超过256000个项。
由于这个原因，所有64位处理器的硬件分页系统都使用了额外的分页级别。使用的级别数量取决于处理器的类型。

平台名称	页大小	寻址使用位数	分页级别	线性地址分级
alpha	8KB	43	3	10+10+10+13
ia64	4KB	39	3	9+9+9+12
ppc64	4KB	41	3	10+10+9+12
x86_64	4KB	48	4	9+9+9+9+12

硬件高速缓存

当今的微处理器时钟频率接近几个GHz，而动态RAM芯片的存取时间是时钟周期的数百倍。为此，80x86体系结构中引入了一个叫行(line)的新单位。行由几十个连续的字节组成，以脉冲突发模式在慢速DRAM和快速的静态RAM（SRAM）之间传送，用来实现高速缓存。

高速缓存单元插在分页单元和主内存之间。包含一个硬件高速缓存内存和一个高度缓存控制器：
高速缓存内存：存放内存中真正的行。
高速缓存控制器：存放一个表项数组，每个表项对应高速缓存内存中的一个行。

转换后援缓冲器（TLB）

转换后援缓冲器（TLB）的高速缓存用于加快线性地址的转换。当一个线性地址第一次使用时，通过慢速访问RAM的页表计算出相应的物理地址。同时，物理地址被存放在一个TLB表项中，以便以后对同一个线性地址的引用可以快速地得到转换。

Linux中的分页

Linux采用了一种同时适用于32位和64位系统的普通分页模型。直到2.6.10版本，Linux采用三级分页的模型。从2.6.11版本开始，采用了四级分页模型。这4种页表分别称为：

页全局目录PGD（对应X86的页目录）
页上级目录PUD（新引进的）
页中间目录PMD（新引进的）
页表PT（对应X86的页表）。

页全局目录包含若干上级目录的地址，页上级目录又依次包含若干页中间目录的地址，而页中间目录又包含若干页表的地址。每一个页表项指向一个页框。线性地址因此被分成五个部分。图中没有显示位数，因为每一部分的大小与具体的计算机体系结构有关。

那么，对于使用二级管理架构32位的硬件，现在又是四级转换了，它们怎么能够协调地工作起来呢？嗯，来看这种情况下，怎么来划分线性地址吧！
从硬件的角度，32位线性地址被分成了三部分——也就是说，不管软件怎么做，最终落实到硬件，也只认识这三位老大。
从软件的角度，由于多引入了两部份，也就是说，共有五部分。——要让二层架构的硬件认识五部份也很容易，在地址划分的时候，将页上级目录和页中间目录的长度设置为0就可以了。
这样，操作系统见到的是五部份，硬件还是按它死板的三部份划分，也不会出错，也就是说大家共建了和谐计算机系统。

同理，启用了物理地址扩展的32位系统使用了三级页表。Linux的页全局目录对应80x86的页目录指针表（PDPT），取消了页上级目录，页中间目录对应80x86的页目录，Linux的页表对应80x86的页表。

这样，虽说是多此一举，但是考虑到64位地址，使用四层转换架构的CPU，我们就不再把中间两个设为0了，这样，软件与硬件再次和谐——抽像就是强大呀！！！

每一个进程都有它自己的页全局目录和自己的页表集。当发生进程切换时，Linux把cr3控制寄存器的内容保存在前一个执行进程的描述符中，然后把下一个要执行进程的描述符的值装入cr3寄存器中。因此，当进程重新开始在CPU上执行时，分页单元指向一组正确的页表。

物理内存布局

在初始化阶段，内核必须建立一个物理地址映射来指定哪些物理地址范围内对内核可用而哪些不可用。

内核将下列页框记为保留，保留页框中的页绝不能被动态分配或交换到磁盘上：

1、在不可用的物理地址范围内的页框
2、含有内核代码和已初始化的数据结构的页框

一般来说，Linux内核安装在RAM中从物理地址0x00100000开始的地方，也就是说，从第二个MB开始。为什么内核没有安装在RAM第一个MB开始的地方？因为PC体系结构有几个独特的地方必须考虑到：

1、页框0由BIOS使用，存放加电自检（POST）期间检查到的系统硬件配置。
2、物理地址从0x000a0000到0x000fffff的范围通常留给BIOS例程，并且映射ISA图形卡上的内部内存。
3、第一个MB内的其他页框可能由特定计算机模型保留。

为了避免把内核装入一组不连续的页框里，Linux更愿意跳过RAM的第一个MB。明确地说，Linux把PC体系结构未保留的页框来动态存放所分配的页。

下图显示Linux怎样填充前3MB的RAM。我们假设内核需要小于3MB的RAM。
符号_text对应于物理地址0x00100000，表示内核代码第一个字节的地址。
符号_etext表示内核代码的结束位置，初始化内核数据的开始位置。
符号_edata表示初始化的内核数据结束位置，未初始化内核数据的开始位置。
符号_end表示未初始化内核的数据结束位置。

进程页表

进程的地址空间分为两部分：
从0x00000000到0xbfffffff的（3G，用户空间）线性地址，无论进程运行在用户态还是内核态都可以寻址。
从0xc0000000到0xffffffff的（1G，内核空间）线性地址，只有内核态的进程才能寻址。

当进程运行在用户态时，它产生的线性地址小于0xc0000000；当进程运行在内核态时，它执行内核代码，所产生的地址大于等于0xc0000000，但是，在某些情况下，内核为了检索或者存放数据必须访问用户态线性地址空间。

页全局目录的第一部分表项映射的线性地址小于0xc0000000（在PAE未启用时是前768项，PAE启用时是前3项），具体大小依赖于特定进程。在0xc0000000之后的表项对所有进程来说都应该是相同的，他们等于主内核页全局目录的相应表项。

内核页表

内核维持着一组自己使用的页表，驻留在所谓的主内核页全局目录中。内核如何初始化自己的页表，这个过程分为两个阶段。
第一阶段，内核创建一个有限的地址空间。这个最小限度的地址空间仅够将内核装入RAM和对其初始化的核心数据结构。
第二阶段，内核充分利用剩余的RAM并适当地建立分页表。

临时内核页表

临时内核页全局目录是在内核编译过程中静态初始化的，而临时页表是有startup_32()汇编语言函数初始化的。

临时页全局目录放在swapper_pg_dir变量中。临时页表在pg0变量处开始存放，紧接在内核未初始化的数据段后面。

分页的第一个阶段的目标是允许在实模式下和保护模式下都能很容易得对内核寻址，假定是8MB。

startup_32()函数通过向cr3控制寄存器装入swapper_pg_dir的地址及设置cr0控制寄存器的PG标志启用分页单元。

当RAM小于896MB时的最终内核页表

由内核页表所提供的最终映射必须把从0xc00000000开始的线性地址转化为从0开始的物理地址。宏pa用于把从PAGE_OFFSET开始的线性地址转换成相应的物理地址，宏va做相反的转化。

主内核页全局目录仍然保存在swapper_pg_dir变量中由paging_init()函数初始化。

由startup_32()函数创建的物理内存前8MB的恒等映射用来完成内核的初始化阶段，当这种映射不再必要时，内核调用zap_low_mappings()函数来清除对应的页表项。

当RAM大小在896MB和4096MB之间时的最终内核页表

linux在初始化阶段可以做的最好的事就是把一个具有896MB的RAM窗口映射到内核线性地址空间。如果一个程序需要对现有的RAM的其余部分寻址，那就必须把某些其他的线性地址间隔映射到所需的RAM，即剩余的RAM留着不映射由动态映射来处理。

当RAM大于4096MB时的最终内核页表

页全局目录中的前三项与用户线性地址空间相对应，内核用一个空页的地址对这三项进行初始化。第四项用页中间目录的地址初始化，该页中间目录是通过调用alloc_bootmen_low_pages()分配的。页中间目录的前448项用RAM前896MB的物理地址填充。

然后页全局目录的第四项被拷贝到第一项中，这样好为线性地址的前896MB中的低物理内存映射做镜像。为了完成SMP系统的初始化，这个映射是必须的：当这个映射不再必要时，内核通过调用zap_low_mappings()来清除对应的页表项。

固定映射的线性地址

我们看到内核线性地址第四个GB的初始部分映射系统的物理内存。但是，至少128MB的线性地址总是留作他用，因为内核使用这些线性地址实现非连续内存分配和固定映射的线性地址。

内核线性地址空间范围：3GB-4GB (0xc0000000-0xffffffff)
内核线性地址空间[3GB,3GB+896MB]————-（线性映射）—————物理地址空间[0,896M]
内核线性地址空间[3GB+896MB,4GB]用来实现“非连续内存分配”和“固定映射”

固定映射的线性地址以“任意方式”（与前896MB线性映射方式相比）映射任何物理地址空间，固定映射使用的线性地址位于线性地址第4个GB末端

处理硬件高速缓存和TLB

处理硬件高速缓存

硬件高速缓存是通过高速缓存行寻址的。为了使高速缓存的命中率达到最优化：

1、一个数据结构中最常使用的字段放在该数据结构内的低偏移部分，以便它们能给处于高速缓存的同一行中。
2、当为一大组数据结构分配空间时，内核试图把它们都存放在内存中，以便所有高速缓存行按同一方式使用。

处理TLB

TLB作用

页表一般都很大，并且存放在内存中，所以处理器引入MMU后，读取指令、数据需要访问两次内存：首先通过查询页表得到物理地址，然后访问该物理地址读取指令、数据。为了减少因为MMU导致的处理器性能下降，引入了TLB，TLB是Translation Lookaside Buffer的简称，可翻译为“地址转换后援缓冲器”，也可简称为“快表”。简单地说，TLB就是页表的Cache，其中存储了当前最可能被访问到的页表项，其内容是部分页表项的一个副本。只有在TLB无法完成地址翻译任务时，才会到内存中查询页表，这样就减少了页表查询导致的处理器性能下降。
TLB中的项由两部分组成：标识和数据。标识中存放的是虚地址的一部分，而数据部分中存放物理页号、存储保护信息以及其他一些辅助信息。

TLB原理

当cpu要访问一个虚拟地址/线性地址时，CPU会首先根据虚拟地址的高20位（20是x86特定的，不同架构有不同的值）在TLB中查找。如果是表中没有相应的表项，称为TLB miss，需要通过访问慢速RAM中的页表计算出相应的物理地址。同时，物理地址被存放在一个TLB表项中，以后对同一线性地址的访问，直接从TLB表项中获取物理地址即可，称为TLB hit。

想像一下x86_32架构下没有TLB的存在时的情况，对线性地址的访问，首先从PGD中获取PTE（第一次内存访问），在PTE中获取页框地址（第二次内存访问），最后访问物理地址，总共需要3次RAM的访问。如果有TLB存在，并且TLB hit，那么只需要一次RAM访问即可。

TLB表项

TLB内部存放的基本单位是页表条目，对应着RAM中存放的页表条目。页表条目的大小固定不变的，所以TLB容量越大，所能存放的页表条目越多，TLB hit的几率也越大。但是TLB容量毕竟是有限的，因此RAM页表和TLB页表条目无法做到一一对应。因此CPU收到一个线性地址，那么必须快速做两个判断：

1、所需的页表是否已经缓存在TLB内部（TLB miss或者TLB hit）
2、所需的页表在TLB的哪个条目内

为了尽量减少CPU做出这些判断所需的时间，那么就必须在TLB页表条目和内存页表条目之间的对应方式做足功夫

全相连 - full associative
在这种组织方式下，TLB cache中的表项和线性地址之间没有任何关系，也就是说，一个TLB表项可以和任意线性地址的页表项关联。这种关联方式使得TLB表项空间的利用率最大。但是延迟也可能相当的大，因为每次CPU请求，TLB硬件都把线性地址和TLB的表项逐一比较，直到TLB hit或者所有TLB表项比较完成。特别是随着CPU缓存越来越大，需要比较大量的TLB表项，所以这种组织方式只适合小容量TLB

直接匹配
每一个线性地址块都可通过模运算对应到唯一的TLB表项，这样只需进行一次比较，降低了TLB内比较的延迟。但是这个方式产生冲突的几率非常高，导致TLB miss的发生，降低了命中率。

比如，我们假定TLB cache共包含16个表项，CPU顺序访问以下线性地址块：1, 17 , 1, 33。当CPU访问地址块1时，1 mod 16 = 1，TLB查看它的第一个页表项是否包含指定的线性地址块1，包含则命中，否则从RAM装入；然后CPU访问地址块17，17 mod 16 = 1，TLB发现它的第一个页表项对应的不是线性地址块17，TLB miss发生，TLB访问RAM把地址块17的页表项装入TLB；CPU接下来访问地址块1，此时又发生了miss，TLB只好访问RAM重新装入地址块1对应的页表项。因此在某些特定访问模式下，直接匹配的性能差到了极点

组相连 - set-associative

为了解决全相连内部比较效率低和直接匹配的冲突，引入了组相连。这种方式把所有的TLB表项分成多个组，每个线性地址块对应的不再是一个TLB表项，而是一个TLB表项组。CPU做地址转换时，首先计算线性地址块对应哪个TLB表项组，然后在这个TLB表项组顺序比对。按照组长度，我们可以称之为2路，4路，8路。

经过长期的工程实践，发现8路组相连是一个性能分界点。8路组相连的命中率几乎和全相连命中率几乎一样，超过8路，组内对比延迟带来的缺点就超过命中率提高带来的好处了。

这三种方式各有优缺点，组相连是个折衷的选择，适合大部分应用环境。当然针对不同的领域，也可以采用其他的cache组织形式。

TLB表项更新

TLB表项更新可以有TLB硬件自动发起，也可以有软件主动更新

1、TLB miss发生后，CPU从RAM获取页表项，会自动更新TLB表项
2、TLB中的表项在某些情况下是无效的，比如进程切换，更改内核页表等，此时CPU硬件不知道哪些TLB表项是无效的，只能由软件在这些场景下，刷新TLB。

在linux kernel软件层，提供了丰富的TLB表项刷新方法，但是不同的体系结构提供的硬件接口不同。比如x86_32仅提供了两种硬件接口来刷新TLB表项：

1、向cr3寄存器写入值时，会导致处理器自动刷新非全局页的TLB表项
2、在Pentium Pro以后，invlpg汇编指令用来无效指定线性地址的单个TLB表项无效。

参考

《深入理解LINUX内核》
物理地址扩展（PAE）分页机制
TLB的作用及工作原理