ULK 内存寻址

绪论

绪论中从总体的框架介绍了一下操作系统、文件系统与Unix内核相关内容，不予过多赘述。

一个新学到的内容是可重入(内核，这意味着多个进程可以同时在内核下执行。这个特性太过于自然以至于让我一直没有注意到也没有在教材上见过，如果某个进程在内核态中被阻塞被挂起，那么它当然不应该影响到其余进程对CPU的使用。在可重入内核的要求下，内核控制路径就会被交替执行。

自旋锁是在多处理器系统中可能采用的一种同步方式。因为信号量操作太慢了，当某些互斥访问时间很短时，使用信号量就很低效。自旋锁本质上就是不断查询是否可用，是一种忙等待，但是在上述场合自旋锁是很有效的。

内核处理信号有五种默认的方式（终止、终止并核心转储、忽略、挂起、恢复），其中**核心转储(core dump)**是指将执行上下文和进程地址空间中的内容写入一个文件，该文件保存了程序终止前的各种信息，可以使用gdb结合源程序进行调试，用于恢复终止前的案发现场。默认的Linux设置好像是不生成core文件，可以使用ulimit -c查看core允许使用的大小，在文件/proc/sys/kernel/core_pattern中添加一条记录给出core允许使用的大小就可以开启核心转储功能。

另一个没怎么了解过的是进程组和登陆会话。进程组其实就是有一堆进程们，他们之间可能有兄弟关系、父子关系等，使用进程组可以比较统一地管理许多进程。而一个会话则可能包含多个进程组，但只有一个前台进程组。会话也有一个组长，即创建会话的进程。一个会话可以有一个控制终端，也可以没有控制终端，只有会话组长才可以打开控制终端。因而，在Daemon的实现中，先创建第一子进程来生成一个新的会话脱离原来的会话与进程组，并成为会话组长，再创建第二子进程成为该会话的成员，以防止其打开终端，这样就能创建一个使用独立的进程组、独立的登陆会话且不是会话组长、父进程是init的守护进程。

今天大概花了3个小时看这章并整理笔记，明天把2章内存寻址看了。

内存寻址

本章主要介绍80x86微处理器的内存寻址方式以及Linux如何利用寻址硬件的。

在x86系统下，有三种不同的地址：

• 逻辑地址。每一个逻辑地址由段和偏移量组成。
• 线性地址（也称虚拟地址）。这是一个32位的无符号整数。
• 物理地址。用于内存芯片级的内存单元寻址，由32位/36位无符号整数表示。

内存控制单元（MMU）通过若干硬件电路对地址进行转化，如下图所示。

此外，在多处理器系统中，由于所有CPU共享统一内存，存在一种称为内存仲裁器的硬件电路延迟/分配CPU对内存的访问。但是从编程的角度来看，仲裁器由硬件电路管理，是隐藏的。

硬件中的分段

80286模型以后，Intel处理器有两种不同的地址转换方式：实地址模式和保护模式。实地址其实就是段寄存器内容左移四位再与偏移地址相加的结果，有效的寻址范围为1MB；而保护模式则是使用段寄存器的高13位作为段选择符，在GDT或LDT中查找相应的段描述符，该描述符会给出32位基址地址，使用该地址与偏移量相加即可寻址4GB的内容。下面我们主要讨论保护模式下的地址转化方式。

段选择符和段寄存器

段选择符为16位长的字段，最低2位RPL表示请求者特权级，第3位TI指示该段描述符在GDT中（TI=0）或在LDT中（TI=1）

为了快速的找到段选择符，处理器提供了6个段寄存器，其唯一目的就是存放段选择符。

6个寄存器中有3个有特殊用途：

• cs: 代码段寄存器
• ss: 栈段寄存器
• ds: 数据段寄存器

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

cs寄存器还有一个2位的字段，用于知名CPU当前的特权级。Linux只使用0（内核态）和3（用户态）。

段描述符

每个段都由一个8字节的段描述符(Segment Descriptor)表示，它表述了段的特征。段描述符放在全局描述符表（Global Descriptor Table, GDT）或局部描述符表（Local Descriptor Table, LDT）中。

通常只有一个GDT，而每个进程如果需要附加的段则可以使用LDT。GDT在主存中的地址和大小存放在gdtr控制寄存器中，当前正在使用的LDT则放在ldtr控制寄存器中。

下图给出段描述符字段的结构与描述。

Linux使用如下一些描述符的类型：

• 代码段描述符。指明一个代码段，可以放在GDT/LDT中，S为1。

• 数据段描述符。指明一个数据段，可以放在GDT/LDT中，S为1。栈段是通过一般的数据段实现的。

• 任务状态段描述符（TSSD）。指明一个任务状态段，该段用于保存处理器寄存器的内容。只能出现在GDT中，根据进程是否在CPU上运行，Type类型又分别为11/9，S标志为0. 事实上, 其区别在于第41个bit, B(Busy)字段, 用于区分该段是否正在使用.

• 局部描述符表描述符。该描述符指明的段用于存放LDT，该描述符只存在于GDT中。

GPT的大小为$2^{16}$, 且第0项总是被设置为0表示无效，因而一个GPT中最多可以拥有$2^{13}-1$个段描述符。

快速访问段描述符

x86处理器提供一种附加的非编程用的寄存器，专门供6个段寄存器使用，每个寄存器可以存放一个8字节的段描述符。每当一个段选择符被装入段寄存器中，其对应的段描述符就由内存装入到对应的特殊寄存器中。以后针对该段的地址访问就不需要每次都去查描述符表，而直接可以从寄存器中获取相应的地址信息。

分段单元

下面说明分段单元如何将逻辑地址转换为线性地址。

• 首先检查段选择符的TI位，用于决定描述符在GDT还是LDT中，从对应的gdtr/ldtr中获得描述表的基地址。
• 获取段选择符的高13位地址，将该地址乘以8（一个段描述符的大小）后与描述符表的基址相加，即得到当前段的描述符。
• 获取描述符内的基址信息，与逻辑地址的偏移量相加即得到了线性地址。

Linux中的分段

Linux中用户态的所有进程使用同一对相同的代码段和数据段，内核态中的所有进程也使用一对相同的代码段和数据段，下标给出这四个重要段的描述符信息。

可以看出，这四个段的线性地址都从0开始，有$2^{32}-1$的寻址限长，这意味着无论用户态还是内核态的所有进程都可以使用相同的逻辑地址。此外也可以发现，LInux下逻辑地址和线性地址总是一致的。

Linux GDT

一个CPU对应一个GDT，每个GDT有18个段描述符和14个空的、未使用的、保留的描述符。

下图给出GDT的布局图：

18个描述符分别为：

• 4个上述的代码段和数据段描述符
• TSS任务状态段
• 一个缺省的LDT段描述符，这个段通常为所有进程共享
• 3个局部线程存储（Thread-Local Storage）段：这种机制允许多线程应用使用最多3个局部于县城的数据段。
• 3个与高级电源管理(AMP)有关的段。
• 5个与支持即插即用功能(PnP)的BIOS服务程序有关的段
• 内核用于处理“双重错误”异常的特殊TSS段

Linux LDT

大多数Linux程序不使用LDT，因而内核定义了一个缺省的LDT段。在某些情况下，进程需要创建自己的LDT，如Wine运行面向段的MS/Windows程序。modify_ldt()系统调用允许进程创建自己的LDT。

硬件中的分页

从80386开始，所有的x86处理器都支持分页，它通过设置cr0寄存器中的PG标志启用，PG=0时线性地址直接解释成物理地址。

32位的线性地址分为3个域：

• 目录：高10位
• 页表：中间10位
• 偏移量：最低12位

线性地址的转化分两步完成，第一次使用页目录表，第二次使用页表。这种二级模式的目的在于减少每个进程页表所需要RAM的数量。(动态分配)

正在使用的页目录的物理地址存放在控制寄存器cr3中，目录字段决定页目录中的目录项，而目录项指向相应的页表。

页目录项和页表项有相同的结构，都包含如下的字段：

拓展分页

从奔腾模型开始，x86处理器引入了拓展分页，允许页框大小为4MB， 用于将大段连续的线性地址转换为对应的物理地址。在这种情况下，内核可以节省内存并保留TLB项。

在拓展分页下，分页单元将32位划分为10/22，页目录项的字段也基本相同，除了：

• Page Size标志必须设置
• 20位的物理地址只有最高10位有意义

通过设置cr3的PSE标志能够使得拓展分页与常规分页共存。

硬件保护方案

若页表项中的User/SUpervisor标志位为0，则只有内核态可以对页寻址，不然则总能对页寻址。

另外，与段的3种存储权限（读写执行）不同，对页只有两种权限（读写）。当Read/Write为0时，则该页只读，否则可读可写。

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

为了拓展32位x86所支持的RAM容量，Intel在处理器上将引脚数从32提高到了64，使得最大的寻址能力达到64GB。但是相应的也需要一种分页机制，将32位的线性地址转换到36位的物理地址才能真正地增加可用的地址。

PAE所采取的主要变化其实是将页表项从32位变成了64位，同时引入了一个新的页表级别：页目录指针表（PDPT），它由4个64位的表项组成，每一项均能够指向一个页目录。由于PDPT存放在RAM的前4GB中，且按照32位对齐，因而使用27位即可对PDPT进行寻址，这27位地址就放在cr3控制寄存器中。

每次解释32位地址时，首先从cr3中获取到PDPT的地址，接下来取高两位选择一个表项，接下来根据9位选择一个目录项，再根据9位选择一个表项，最终12位决定页内偏移。

借助cr3或PDPT，就可以使用32位的虚拟地址来寻址36位的物理地址了。其本质其实就是动态的变化cr3中的地址，完成地址的扩充。

由于只有内核能够修改进程的页表，所以PAE允许内核使用64GB的RAM，但是用户态态的进程仍然只能使用4GB的物理空间。

64位系统中的分页

一般都使用多级分页的方式来避免页表中存在过多的表项

硬件高速缓存

高速缓存单元由两部分组成，一个是高速缓存控制器，一个是SRAM高速缓存。书中对于具体的描述不详，博客 浅析CPU高速缓存(cache)与 Cache直接映射、组相连映射以及全相连映射比较不错顺便偷图。

Cache引入了一个新的单位“行”，一行由几十个连续的字节组成，是DRAM和SRAM交换的单位。其中存储着许多行数据，高速缓存控制器则存放着一个表项数组，每个表项对应高速缓存中的一行, 拥有标签和描述高速缓存行状态的几个标志。

当访问一个主存单元时，首先将地址划分为标记、组索引、块偏移三个结构。通过组索引来选择cache中的某一个组，接下来遍历该组中所有的行信息，检查该行的标签是否与地址中的标签相同，如果相同则cache命中，根据块偏移即可访问到对应的存储在Cache中主存字节内容。

下图给出了一个生动的过程。(大概也不那么生动, 右侧对于实际内存的映射有点奇怪):

从内存的观点看, 内存按照$2^b$的大小被划分为块, 间隔为$2^s$的块被放入同一组(组索引相同), 组内则根据高地址作为标记区分不同的块.

特殊的, 根据组内行数不同, 又可以将Cache的组织方式分为直接映射(组内仅有1行)和全相联映射(仅有1组).

• 直接映射是最简单的地址映射方式，它的硬件简单，成本低，地址变换速度快，而且不涉及替换算法问题。但是这种方式不够灵活，Cache的存储空间得不到充分利用，每个主存块只有一个固定位置可存放，容易产生冲突，使Cache效率下降，因此只适合大容量Cache采用

• 全相联映射方式比较灵活，主存的各块可以映射到Cache的任一块中，Cache的利用率高，块冲突概率低，只要淘汰Cache中的某一块，即可调入主存的任一块。但是，由于Cache比较电路的设计和实现比较困难，这种方式只适合于小容量Cache采用。

另一个有趣的问题是，cache中存的地址是虚拟地址还是物理地址？

参考一些博客：https://zhuanlan.zhihu.com/p/107096130 (排版的很漂亮，但是大概是 这篇博客的中文翻译版本), https://blog.csdn.net/hx_op/article/details/89244618

一般来说有以下几种的cache地址组织方式：

• VIVT(Virtual Index Virtual Tage)
• PIPT(Physical Index Physical Tag) 首先将虚拟地址通过TLB或页表等分页单元映射到物理地址，再取其位作为Tag、Index
• VIPT 一方面通过虚拟地址的Index寻址Cache块，另一方面同时地让MMU映射虚拟地址，使用物理地址作为Tag进行行匹配。

Cache在组织过程中可能存在 别名(alias), 歧义(ambiguity)这两种问题。别名是指多个cache行映射到了同一个物理块，这会导致数据一致性的问题。歧义是指一个cache行指向了多个物理块，这往往发生在多个进程访问cache时，一种解决方案是在切换进程上下文时刷新cache。

VIVT存在上述两种问题，但是硬件设计上较为简单，并且每次查询chache时不需要MMU转换物理地址，一定程度上提升了速度。

PIPT不存在上述两种问题，因为物理地址显然不会冲突。虽然其在软件层面基本不需要维护，但是在硬件层面比VIVT复杂很多。

VIPT不存在歧义，有可能存在别名问题。 首先说明歧义问题。其实这一点还是很费解的，因为网上的资料要么直接说一句“因为使用物理地址作为Tag，所以不会产生歧义”，要么是像第一篇参考博客一样，说明了一种特殊实现下的无歧义情况。这种特殊实现是使用高20位作为Tag(默认页大小4KB)，这样的话显然是不会产生歧义。但是离我心中的设想还是差了点味道，本以为是对于任意的实现都不会产生歧义。接下来说明别名问题。文中费大力气说明了如果偏移量+索引号占的位数不超过页大小（即不超过12位），那么就不会产生别名，因为此时VIPT就是PIPT。？？？这不是很傻逼的行文方式吗。。这么说来的话，综合来看，当Tag不小于20位时，此时显然就是PIPT，则不会产生别名和歧义；不然则有可能产生上述问题。不知道我的理解是否正确，暂此打住。

PIVT一般不使用。因为一方面必须等到物理地址转换完成后才能进入cache组查找，另一方面又可能产生各种错误，非常垃圾。

https://stackoverflow.com/questions/20787522/cache-addressing-methods-confusion

多级Cache

• 可以通过getconf -a | grep -i cache查看本机的cache信息

• 可以通过/sys/devices/system/cpu/cpu0/cache/indexX/*文件查看cache信息

一级cache通常又分为数据cache(index0)和指令cache(index1).

附本机的cache信息:

 1LEVEL1_ICACHE_SIZE                 32768
 2LEVEL1_ICACHE_ASSOC                
 3LEVEL1_ICACHE_LINESIZE             64
 4LEVEL1_DCACHE_SIZE                 49152
 5LEVEL1_DCACHE_ASSOC                12
 6LEVEL1_DCACHE_LINESIZE             64
 7LEVEL2_CACHE_SIZE                  1310720
 8LEVEL2_CACHE_ASSOC                 10
 9LEVEL2_CACHE_LINESIZE              64
10LEVEL3_CACHE_SIZE                  25165824
11LEVEL3_CACHE_ASSOC                 12
12LEVEL3_CACHE_LINESIZE              64
13LEVEL4_CACHE_SIZE                  0
14LEVEL4_CACHE_ASSOC                 
15LEVEL4_CACHE_LINESIZE 

转换后援缓冲器TLB

神秘的名字

TLB全称Translation Lookaside Buffer

该结构其实就是一个虚拟地址到物理地址转换的高速缓存表。

当cr3寄存器被修改后，硬件自动使TLB中所有项无效，因为此时新的一组页表被启用了。

Linux中的分页

Linux使用一种同时使用32位和64位系统的分页模型，从2.6.11开始采用四级分页模型：PGD、PUD、PMD、PT。

Linux的分页机制使得以下功能得以实现：

• 给每一个进程分配一块不同的物理地时，防止寻址错误
• 区分页和页框，这是虚拟内存机制的基本要素

线性地址字段

有一些预定义的宏说明了线性地址的偏移与位数、页表项的增删改查、页表标志位的读写、页分配等操作，这里就不再说明了。。其实是没有搞得太清楚，毕竟没有去阅读源码

2022/7/17 更新：

在include/asm-i38/page.h, include/asm-i386/pgtable-3level-def.h等中定义了若干的页表处理宏，如: PAGE_SHIFT， PMD_SHIFT, PUD_SHIFT, PGDIR_SHIFT (地址偏移量，在采用大型页或PAE选项时可能有所变化)；PTRS_PER_PTE, PTRS_PER_PME,PTRS_PER_PUE,PTRS_PER_PGD (PAE?512, 512, 1, 4: 1024, 1, 1, 1024)

页表处理

对于基本的函数/宏操作略去。

提一些注意点：

• pmd_bad宏检查目录项是否指向一个不可用的页表，如果：

  • 页不在主存中，present被清零

  • 页只读，Read/Write被清零

  • Accessed/Dirty位被清零（对于现存的页表而言，Linux强制设置这些标志）

  则该宏产生1。而pud_bad和pgd_bad总产生0,且没有定义pte_bad宏，因为对于页表项而言上述的几点均是合法的。

• 如果一个页表项 的present/Page Size（只对目录项有意义）为1时，则pte_present结果为1.这是由于存在一种情况，某页确实存在于主存中，但是却没有读、写、操作权，内核就会将其present和PS标志分别置为0和1，以此来区分缺页异常。

物理内存布局

Linux内核将不可用地址的页框、含有内核代码和已初始化的数据结构的页框标记为保留，保留页框无法被动态分配或交换到磁盘上。

一般来说，Linux内核在RAM中从第二个MB开始，因为PC体系有几个特殊的地方：

• 页框0由BIOS使用，存放加电自检时检测道德系统配置。

• 物理地址0x000a0000到0x000fffff的范围通常留给BIOS例程，并且映射图形卡上的内部内存。

• 第1MB内的页框可能由特定的计算机模型保留

为了避免把内核装入一组不连续的页框，Linux更愿意跳过RAM的第一个RAM。

进程页表

当进程运行在用户态时，其产生的虚拟地址小于0xc0000000；而当其运行在内核态时，其产生的虚拟地址则大于等于0xc0000000。在某些情况下，内核为了检索或存放数据需要访问用户态的地址空间。

进程页全局目录pgd的第一部分映射的虚拟地址小于0xc0000000， PAE未开启时为768项，开启后为3项，均最大寻址3GB的地址范围。剩余的表项对于所有的进程都是相同的，都等于主内核pgd的相应表项。

内核页表

在内核映像刚被装入内存后，CPU仍然处于实模式，分页功能没有启动。

第一阶段，内核创建一个包含其代码段、数据段、初始页表和用于存放动态数据结构的128KB的空间。

第二阶段，内核利用剩余的RAM建立分页表（留坑）

固定映射的线性地址

内核线性地址空间范围：3GB-4GB (0xc0000000-0xffffffff)

内核线性地址空间[3GB,3GB+896MB]—–（线性映射）———-物理地址空间[0,896M]

内核线性地址空间[3GB+896MB,4GB]用来实现“非连续内存分配”和“固定映射”

处理硬件高速缓存和TLB

处理硬件高速缓存：x86处理器自动处理高速缓存的同步，所以对应的内核不需要处理缓存的刷新；但是内核可以为不能同步高速缓存的处理器提供刷新接口。

处理TLB：决定tlb内映射是否有效的不是硬件而是内核。Linux2.6提供了几种不同的TLB刷新方法， 内核在写入新的pgd到cr3中应该自动完成tlb的更新，但是有一些情况下会避免对其的更新：

• 两个使用相同页表集的进程之间的切换（第七章的schedule）

• 一个普通进程和一个内核进程之间的切换（内核并不拥有自己的页表集，而是使用刚刚CPU上刚执行过的进程的页表）

内核使用懒惰TLB的方式来避免多处理器下的无用TLB刷新，具体内容不予展开。。