第二章--内存寻址

一、内存地址
        当使用80x86微处理器时，有三种不同的地址：
        逻辑地址(logical address)：包含在机器语言指令中用来指定一个操作数或一条指令的地址。这个寻址方式在80x86著名的分段结构中表现得尤为具体，它促使MS-DOS或Windows程序员把程序分成若干段。每一个逻辑地址都由一个段(segment)和偏移量(offset或displacement)组成，偏移量指明了从段开始的地方到实际地址之间的距离。
        线性地址(linear address)(也称虚拟地址virtual address)：是一个32位无符号整数，可以用来表示高达4GB的地址，也就是，高达4294967296个内存单元。线性地址通常用十六进制数字表示，范围：0x0000 0000到0xffff ffff。
        物理地址(physical address)：用于内存芯片级内存单元寻址。它们与从微处理器的地址引脚发送到内存总线上的电信号相对应。物理地址由32位或36位无符号整数表示。
        内存控制单元(MMU)通过一种称为分段单元(segmentation unit)的硬件电路把一个逻辑地址转换成线性地址；接着，第二个称为分页单元(paging unit)的硬件电路把线性地址转换成一个物理地址。

二、硬件中的分段
2.1、段选择符和段寄存器
        一个逻辑地址由两部分组成：一个段标识符和一个指定段内相对地址的偏移量。段标识符是一个16位长的字段，称为段选择符(Segment Selector)，而偏移量是一个32位长的字段。
        处理器提供段寄存器，段寄存器的唯一目的是存放段选择符。这些段寄存器称为cs、ss、ds、es、fs和gs。尽管只有6个段寄存器，但程序可以把同一个段寄存器用于不同的目的，方法是先将其值保存在内存中，用完后再恢复。
        下面三个段寄存器有专门的用途：
        cs：代码段寄存器，指向包含程序指令的段。
        ss：栈段寄存器，指向包含当前程序栈的段。
        ds：数据段寄存器，指向包含静态数据或者全局数据段。
        其它三个段寄存器作一般用途，可以指向任意的数据段。
        cs寄存器还有一个很重要的功能：它包含一个两位的字段，用以指明CPU的当前特权级(CPL)。值为0代表最高优先级，值为3代表最低优先级。Linux只用0级和3级，分别称为内核态和用户态。
2.2、段描述符
        每个段由一个8字节的段描述符(Segment Descriptor)表示，它描述了段的特征。段描述符放在全局描述符表(Global Descriptor Table, GDT)或局部描述符表(Local Descripotr Table，LDT)中。
        有几种不同类型的段以及和它们对应的段描述符。下面列出了Linux中被广泛采用的类型：
        代码段描述符：
        表示这个段描述符代表一个代码段，它可以放在GDT或LDT中。该描述符置S标志为1(非系统段)。
        数据段描述符：
        表示这个段描述符代表一个数据段，它可以放在GDT或LDT中。该描述符置S标志为1。栈段是通过一般的数据段实现的。
        任务状态段描述符(TSSD)：
        表示这个段描述符代表一个任务状态段(Task State Segment，TSS)，也就是说这个段用于保存处理器寄存器的内容。它只能出现在GDT中。根据相应的进程是否正在CPU上运行，其Type字段的值分别为11或9。这个描述符的S标志置为0。
        局部描述符表描述符(LDTD)：
        表示这个段描述符代表一个包含LDT的段，它只出现在GDT中。相应的Type字段的值为2，S标志为0。
2.3、快速访问段描述符

2.4、分段单元
        分段单元(segmentation unit)执行以下操作：
        * 先检查段选择符的TI字段，以决定段描述符保存在哪一个描述符表中。TI字段指明描述符是在GDT中(在这种情况下，分段单元从gdtr寄存器中得到GDT的线性基地址)还是在激活的LDT中(在这种情况下，分段单元从ldtr寄存器中得到LDT的线性基地址)。
        * 从段选择符的index字段计算段描述符的地址，index字段的值乘以8(一个段描述符的大小)，这个结果与gdtr或ldtr寄存器中的内容相加。
        * 把逻辑地址的偏移量与段描述符Base字段的值相加就得到了线性地址。
三、Linux中的分段
        分段和分页都可以划分进程的物理地址空间；分段可以给每一个进程分配不同的线性地址空间，而分页可以把同一线性地址空间映射到不同的物理空间。与分段相比，Linux更喜欢使用分页方式，因为：
        1、当所有进程使用相同的段寄存器值时，内存管理变得更简单，也就是说她们能共享同样的一组线性地址。
        2、Linux设计目标之一是可以把它移植到绝大多数流行的处理器平台上。然后，RISC体系结构对分段的支持很有限。
        2.6版的Linux只有在80x86结构下才需要使用分段。
        运行在用户态的所有Linux进程都使用一对相同的段来对指令和数据寻址。这两个段就是所谓的用户代码段和用户数据段。类似地，运行在内核态的所有Linux进程都使用一对相同的段来对指令和数据寻址：它们分别叫做内核代码段和内核数据段。
        相应的段选择符由宏__USER_CS，__USER_DS，__KERNEL_CS和__KERNEL_DS分别定义。例如，为了对内核代码段寻址，内核只需要把__KERNEL_CS宏产生的值装进cs段寄存器即可。
        注意，与段相关的线性地址从0开始，达到2³²-1的寻址限长。这就意味着在用户态或内核态下的所有进程可以使用相同的逻辑地址。
        所有段都从0x0000 0000开始，这可以得出另一个重要结论，那就是在Linux下逻辑地址与线性地址是一致的，即逻辑地址的偏移量字段与相应的线性地址的值总是一致的。
        如前所述，CPU的当前特权级(CPL)反应了进程是在用户态还是内核态，并由存放在cs寄存器中的段选择符的RPL字段指定。只要当前特权级被改变，一些段寄存器必须相应地更新。例如，当CPL = 3时(用户态)，ds寄存器必须含有用户数据段的段选择符，而当CPL = 0时，ds寄存器必须含有内核数据段的段选择符。
3.1、Linux GDT
        在单处理器系统中只有一个GDT，而在多处理器系统中每个CPU对应一个GDT。所有的GDT都存放在cpu_gdt_table数组中，而所有GDT的地址和它们的大小被存放在cpu_gdt_descr数组中。
3.2、Linux LDT

四、硬件中的分页
        分页单元(paging unit)把线性地址转换成物理地址。其中的一个关键任务就是把所请求的访问类型与线性地址的访问权限相比较，如果这次内存访问是无效的，就产生一个缺页异常。
        为了效率起见，线性地址被分成以固定长度为单位的组，称为页(page)。页内部连续的线性地址被映射到连续的物理地址中。这样，内核可以指定一个页的物理地址和其存取权限，而不用指定页所包含的全部线性地址的存取权限。使用术语“页”既指一组线性地址，又指包含在这组地址中的数据。
        分页单元把所有的RAM分成固定长度的页框(page frame)(有时叫做物理页)。每一个页框包含一个页(page)，也就是说一个页框的长度与一个页的长度一致。页框是主存的一部分，因此也是一个存储区域。区分一页和一个页框是很重要的，前者只是一个数据块，可以存放在任何页框或磁盘中。
        把线性地址映射到物理地址的数据结构称为页表(page table)。页表存放在主存中，并在启用分页单元之前必须由内核对页表进行适当的初始化。
4.1、常规分页
        32位的线性地址被分成3个域：
        Directory(目录)：最高10位。
        Table(页表)：中间10位。
        Offset(偏移量)：最低12位。
        线性地址的转换分两步完成，每一步都基于一种转换表，第一种转换表称为页目录表(page directory)，第二种转换表称为页表(page table)。

        正在使用的页目录的物理地址存放在控制寄存器cr3中。线性地址内的Directory字段决定页目录中的目录项，而目录项指向适当的页表。地址的Table字段依次又决定页表中的表项，而表项含有页所在的页框的物理地址。Offset字段决定页框内的相对位置。由于它是12位长，故每一页含有4096字节的数据。
        Directory字段和Table字段都是10位长，因此页目录和页表都可以多达1024项。那么一个页目录可以寻址到高达1024*1024*4096=2³²个存储单元，这和32位地址所期望的一样。
        页目录项和页表项有同样的结构，每项都包含下面的字段：
        Present标志：
        如果被置为1，所指的页(或页表)就在主存中；如果该标志为0，则这一页不在主存中，此时这个表项剩余的位可由操作系统用于自己的目的。如果执行一个地址转换所需的页表项或页目录项中Present标志被清0，那么分页单元就把该线性地址转换所需的页表项或页目录项中Present标志被清0，那么分页单元就把该线性地址存放在控制寄存器cr2中，并产生14号异常：缺页异常。
        包含页框物理地址最高20位的字段：
        由于每一个页框有4KB的容量，它的物理地址必须是4096的倍数，因此物理地址的最低12位总为0.如果这个字段指向一个页目录，相应的页框就含有一个页表；如果它指向一个页表，相应的页框就含有一页数据。
        Accessed标志：
        每当分页单元对相应页框进行寻址时就设置这个标志。当选中的页被交换出去时，这一标志就可以由操作系统使用。分页单元从来不重置这个标志，而是必须由操作系统去做。
        Dirty标志：
        只应用于页表项中。每当对一个页框进行写操作时就设置这个标志。与Accessed标志一样，当选中的页被交换出去时，这一标志就可以由操作系统使用。分页单元从来不重置这个标志，而是必须由操作系统去做。
        Read/Write标志：
        含有页或页表的存取权限(Read/Write或Read)。
        User/Supervisor标志：
        含有访问页或页表所需的特权级。
        PCD和PWT标志：
        控制硬件高速缓存处理页或页表的方式。
        Page Size标志：
        只应用于页目录项。如果设置为1，则页目录项指的是2MB或4MB页框。
        Global标志：
        只应用于页表项。这个标志是在Pentium Pro中引入的，用来防止常用页从TLB高速缓存中刷新出去。只有在cr4寄存器的页全局启用(Page Global Enable, PGE)标志置位时这个标志才起作用。
4.2、扩展分页
        从Pentium模型开始，80x86微处理器引入了扩展分页(externded paging)，它允许页框大小为4MB而不是4KB。扩展分页用于把大段连续的线性地址转换成相应的物理地址，在这种情况下，内核可以不用中间页表进行地址转换，从而节省内存并保留TLB项。

        正如前面所述，通过设置页目录项的Page Size标志启用扩展分页功能。在这种情况下，分页单元把32位线性地址分成两个字段：
        Directory：最高10位。
        Offfset：其余22位。
        扩展分页和正常分页的页目录项基本相同，除了：
        * Page Size标志必须被设置。
        * 20位物理地址字段只有最高10位是有意义的。这是因为每一个物理地址都是在以4MB为边界的地方开始的，故这个地址的最低22位为0。
        通过设置cr4处理器寄存器的PSE标志能使扩展分页与常规分页共存。
4.3、硬件保护方案
        与页和页表相关的特权级只有两个，因为特权由前面“常规分页”一节中所提到的User/Supervisor标志所控制。若这个标志为0，只有当CPL小于3(这意味着对于Linux而言，处理器处于内核态)时才能对页寻址；若该标志为1，则总能对页寻址。
        此外，与段的3种存取权限(读，写，执行)不同的是，页的存取权限只有两种(读，写)。如果页目录项或页表项的Read/Write标志等于0，说明相应的页表或页是只读的，否则是可读写的。
4.4、常规分页举例
        假设进程需要读线性地址0x20021406中的字节。这个地址由分页单元按下面的方法处理：
        1、Directory字段的0x80用于选择页目录的第0x80目录项，此目录项指向和该进程的页相关的页表。
        2、Table字段0x21用于选择页表的第0x21表项，此表项指向包含所需页的页框。
        3、最后，Offet字段0x406用于在目标页框中读偏移量为0x406中的字节。
        如果页表第0x21表项的Present标志为0，则此页就不在主存中；在这种情况下，分页单元在线性地址转换的同时产生一个缺页异常。无论何时，当进程试图访问限定在0x2000 0000到0x2003 ffff范围之外的线性地址时，都将产生一个缺页异常，因为这些页表项都填充了0，尤其是它们的Present标志都被清0。
4.5、物理地址扩展(PAE)分页机制

4.6、64位系统中的分页

4.7、硬件高速缓存

4.8、转换后援缓冲器(TLB)
        在多处理系统中，每个CPU都有自己的TLB。

五、Linux中的分页

        从2.6.11版本开始，Linux采用了四级分页模型，如上图展示的4种页表分别称为：
        * 页全局目录(Page Global Directory)
        * 页上级目录(Page Upper Directory)
        * 页中间目录(Page Middle Directory)
        * 页表(Page Table)
        页全局目录包含若干页上级目录的地址，页上级目录又依次包含若干页中间目录的地址，而页中间目录又包含若干页表的地址。每一个页表项指向一个页框。线性地址因此被分成五个部分。上图没有显示位数，因为每一部分的大小与具体的计算机体系结构有关。
        Linux的进程处理很大程度上依赖于分页。事实上，线性地址到物理地址的自动转换使下面的设计目标变得可行：
        1、给每一个进程分配一块不同的物理地址空间，这确保了可以有效地防止寻址错误。
        2、区别页(即一组数据)和页框(即主存中的物理地址)之不同，这就允许存在在某个页框中的一个页，然后保存到磁盘上，以后重新装入这同一页时又可以被装在不同的页框中。这就是虚拟内存机制的基本要素。
        每一个进程有它自己的页全局目录和自己的页表集。当发生进程切换时，Linux把cr3控制寄存器的内容保存在前一个执行进程的描述符中，然后把下一个要执行进程的描述符的值装入cr3寄存器中，因此，当新进程重新开始在CPU上执行时，分页单元指向一组正确的页表。
5.1、线性地址字段
        PAGE_SHIFT：
        指定Offset字段的位数。当用于80x86处理器时，它产生的值为12。由于页内所有地址都必须能放到Offset字段中，因此80x86系统的页的大小是2¹² = 4096字节。PAGE_SHIFT的值为12可以看作是以2为底的页大小的对数。这个宏由PAGE_SIZE使用用以返回页的大小。最后，PAGE_MASK宏产生的值为0xffff f000，用以屏蔽Offset字段的所有位。
        PMD_SHIFT：
        指定线性地址的Offset字段和Table字段的总位数；换句话说，是页中间目录项可以映射的区域大小的对数。PMD_SIZE宏用于计算由页中间目录的一个单独表项所映射的区域大小，也就是一个页表的大小。PMD_MASK宏用于屏蔽Offset字段与Table字段的所有位。
        当PAE被禁用时，PMD_SHIFT产生的值为22(来自Offset的12位加上来自Table的10位)，PMD_SIZE产生的值为2²²或4MB，PMD_MASK产生的值为0xffc0 0000。相反，当PAE被激活时，PMD_SHIFT产生的值为21(来自Offset的12位加上来自Table的9位)，PMD_SIZE产生的值为2²¹或2MB，PMD_MASK产生的值为0xffe0 0000。
        PMD_SHIFT：
        确定页上级目录项能映射的区域大小的对数。PUD_SIZE宏用于计算页全局目录中的一个单独表项所能映射的区域大小。PUD_MASK宏用于屏蔽Offset字段、Table字段、Middle Air字段和Upper Air字段的所有位。
        PGDIR_SHIFT：
        确定页全局目录项能映射的区域大小的对数。PGDIR_SIZE宏用于计算页全局目录中一个单独表项所能映射区域的大小。PGDIR_MASK宏用于屏蔽Offset、Table、Middle Air及Upper Air字段的所有位。
        PTRS_PER_PTE，PTRS_PER_PMD，PTRS_PER_PUD以及PTRS_PER_PGD：
        用于计算页表、页中间目录、页上级目录和页全局目录表中表项的个数。当PAE被禁止时，它们产生的值分别为1024，1，1和1024。当PAE被激活时，产生的值分别为512，512，1和4。
5.2、页表处理
        pte_t、pmd_t、pud_t、pgd_t和pgprot_t分别描述页表项、页中间目录项、页上级目录和页全局目录项的格式。当PAE被激活时它们都是64位的数据类型，否则都是32位数据类型。pgprot_t是另一个64位(PAE激活时)或32位(PAE禁用时)的数据类型，它表示与一个单独表项相关的保护标志。
        宏pmd_bad由函数使用并通过输入参数传递来检查页中间目录项。如果目录项指向一个不能使用的页表，也就是说，如果至少出现以下条件中的一个，则这个宏产生的值为1：
        * 页不在主存中(Present标志被清除)。
        * 页只允许读访问(Read/Write标志被清除)。
        * Accessed或者Dirty位被清除(对于每个现有的页表，Linux总是强制设置这些标志)。

        如果PAE被激活，内核使用三级页表。当内核创建一个新的页全局目录时，同时也分配四个相应的页中间目录；只有当父页全局目录被释放时，这四个页中间目录才得以释放。

5.3、物理内存布局
        在初始化阶段，内核必须建立一个物理地址映射来指定哪些物理地址范围对内核可用而哪些不可用(或者因为它们映射硬件设备I/O的共享内存，或者因为相应的页框含有BIOS数据)。
        内核将下列页框记为保留：
        1、在不可用的物理地址范围内的页框。
        2、含有内核代码和已初始化的数据结构的页框。
        保留页框中的页绝不能被动态分配或交换到磁盘上。

5.4、进程列表
        进程的线性地址空间分成两部分：
        1、从0x0000 0000到0xbfff ffff的线性地址，无论进程运行在用户态还是内核态都可以寻址。
        2、从0xc000 0000到0xffff ffff的线性地址，只有内核态的进程才能寻址。
        当进程运行在用户态时，它产生的线性地址小于0xc000 0000；当进程运行在内核态时，它执行内核代码，所产生的地址大于等于0xc000 0000。但是，在某些情况下，内核为了检索或存放数据必须访问用户态线性地址空间。
        宏PAGE_OFFSET产生的值是0xc000 0000，这就是进程在线性地址空间中的偏移量，也是内核生存空间的开始之处。
5.5、内核页表
        描述内核如果初始化自己的页表分为两个阶段，事实上，内核映射刚刚被装入内存后，CPU仍然运行于实模式，所以分页功能没有被启用。
        第一个阶段，内核创建一个有限的地址空间，包括内核的代码段和数据段，初始页表和用于存放动态数据结构的共128KB大小的空间。这个最小限度的地址空间仅够将内核装入RAM和对其初始化的核心数据结构。
        第二个阶段，内核充分利用剩余的RAM并适当地建立分页表。
5.5.1、临时内核页表

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

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

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

5.6、固定映射的线性地址

5.7、处理硬件高速缓存和TLB
5.7.1、处理硬件高速缓存
        为了使高速缓存的命中率达到最优化，内核在下列决策中考虑体系结构：
        * 一个数据结构中最常使用的字段放在该数据结构内的低偏移部分，以便它们能够处于高速缓存的同一行中。
        * 当为一大组数据结构分配空间时，内核试图把它们都存放在主存中，以便所有高速缓存行按同一方式使用。
5.7.2、处理TLB
        任何进程切换都会暗示着更换活动页表集。相对于过期页表，本地TLB表项必须被刷新；这个过程在内核把新的页全局目录的地址写入cr3控制寄存器时会自动完成。不过内核在下列情况下将避免TLB被刷新：
        * 当两个使用相同页表集的普通进程之间执行进程切换时。
        * 当在一个普通进程和一个内核线程间执行进程切换时。内核线程并不拥有自己的页表集；更确切地说，它们使用刚在CPU上执行过的普通进程的页表集。
        除了进程切换以外，还有其他几种情况下内核需要刷新TLB中的一些表项。例如，当内核为某个用户态进程分配页框并将它的物理地址存入页表项时，它必须刷新与相应线性地址对应的任何本地TLB表项。在多处理器系统中，如果有多个CPU在使用相同的页表集，那么内核还必须刷新这些CPU上使用相同页表集的TLB表项。