深入理解Linux Kernel 第1部分 内存

Author Avatar
Cesare (MINGJU LI) Feb 14, 2020

写在前面

本来是准备专门看看关于Linux的KVM和虚拟化这一部分的内容的，但是果然做学问还是不能建空中楼阁，如果不对Linux有深入的了解就想学习这部分的内容的话无异于天方夜谭，前些日子看完了关于程序设计模式的书…所以这回决定开一个新坑，准备扎扎实实的把深入理解Linux内核这部书读完。只不过与之前设计模式那部分的文档不同，当时写下那部分的博客主要是为了像我一样的菜鸡程序员能够轻松的对设计模式有一个认知。但是此次的这一系列博客更多的是为了能够记录自己在本书中的感悟的点点滴滴。

什么是Linux

我自己是十分抗拒写这个部分的内容的，因为我大概已经读了若干本关于Linux/Unix/操作系统的书了，这个“读了”却往往没有读完，不过每本的第一章倒是都读了。还是按照自己的理解在这一部分随便写写。

Unix和Linux

一个老生常谈的问题就是，Linux和Unix是啥关系？Linux是Linus Torvalds开发的类Unix系统，然而因为Linux是一个开源的系统（遵循GNU公共许可证–GPL），所以获得了全世界程序员的支持和喜爱。现在的Linux流行开来，主要使用在PC机和嵌入式，或者一些小型企业的服务器上，而Unix垄断着大型企业的关键性应用领域。

什么是开源许可证？：如果用到了开源代码，就应该按照协议进行开源。License是软件的授权许可，里面详尽表述了你获得代码后拥有的权利，可以对别人的作品进行何种操作，何种操作又是被禁止的。我们借助下图来描述目前的开源许可证（图片来自于网络）

目前市场上的很多（类）Unix系统已经形成了迥异的风格并有许多重要的不同之处，但是内核通常共享基本的设计思想和特征，并且大部分的系统都遵循一个通用的标准（如IEEE的POSIX），这对于程序的开发者而言当然是极好的消息，因为这就意味着在Linux下几乎不用去对源码打补丁或者做修改就能够编译和运行目前的大部分Unix程序。

Linux囊括了Unix的全部特点，包括虚拟存储、虚拟文件系统、轻量级进程、信号等等，这些每一点我们都会在后面的章节去详细的描述。Linux的版本号也是有学问的，这里就不再多做赘述，关于这一点可以在网上获取更多的信息。

类Unix/不同发行版本的Linux：

  1. 类Unix系统是指继承UNIX的设计风格演变出来的系统（比如GNU/Linux、FreeBSD、OpenBSD、SUN公司的Solaris、Minix、QNX等），这些操作系统继承了原始UNIX的特性，有许多相似处，并且都在一定程度上遵守POSIX规范，但是它们却并不含有UNIX的源代码。
  2. Linux只是一个kernel，个人或团体可按自己的需求定制kernel和应用软件，所以就诞生了很多发行版本的Linux，有的针对桌面用户，有的致力于为服务器提供高效的管理等等。Linux的发行版本可以大体分为两类，一类是商业公司维护的发行版本，一类是社区组织维护的发行版本，前者以著名的Redhat（RHEL）为代表，后者以Debian为代表。

Linux的基本概念

  1. 多用户系统：计算机能够并发且独立的执行属于两个或多个用户的若干应用程序。
  2. 用户和组：每个用户（由唯一的一个数字来标识–用户标识符UID）都在机器上有私用空间，同时为了和其他用户有选择地共享资料，每个用户都是一个或多个用户组（由唯一的用户组标识符标识）的一名成员。root用户能够访问系统中的每一个文件，干涉每一个用户程序的活动。
  3. 进程：进程是程序执行时的一个实例，在地址空间中执行一个单独的指令序列。
  4. 内核体系结构：大部分的Unix的内核是比较庞大的，与之相对的是微内核。微内核操作系统要求内核有一个很小的函数集，包括几个同步原语、简单的调度程序等，使其能够实现操作系统级的功能如内存分配、系统调用等。微内核相比大型的内核由很多的优点，这里不再赘述。而Linux为了达到微内核理论上的优点又不影响性能，Linux内核提供了模块。模块是一个目标文件，其代码可以在运行时链接到内核或从内核解除链接，这样我们就精简了内核的功能，并且在需要的时候又可以满足我们对于内核的需求。

Unix的文件系统

聊完了Linux再来聊聊Unix。Unix的操作系统的核心思想体现在文件系统之中。从用户的观点来看，Unix的文件被组织在一个树结构的命名空间中，除了叶节点表示文件以外，所有的节点都表示目录名。

Unix的每一个进程都有一个当前的工作目录，它属于进程执行上下文。

硬链接和软连接：用户可以让一个文件指向另一个文件

Unix的文件可以时下列类型之一：普通文件、目录、符号链接、面向块的设备文件、面向字符的设备文件、管道和命名管道以及套接字。前三种时Unix文件系统的基本类型，设备文件与I/O设备以及驱动程序相关，而管道和套接字是进程间通信的特殊文件。

每个操作系统中的文件可以分为两部分，文件的内容和描述文件的信息。文件的内容不包含任何控制信息（如文件长度等），而描述文件的信息包含在一个名为索引节点（node）的数据结构中。每个文件都有自己的索引节点，文件系统通过索引节点来标识文件。

文件的潜在用户分为三种：文件的所有者，其他同组用户和其他用户。访问权限也有三种，分别是读、写和执行。我们因此就有了3*3=9位的权限标识符，除此以外我们还有三种附加的标记（这三种标记通常应用到可执行文件上来表示对于内核的一些特殊的需求）：

  1. suid:当进程执行一个文件时通常保持进程拥有者的UID，但是如果设置了可执行文件的suid位，那么进程就获得了该文件拥有者的UID
  2. sgid:当进程执行一个文件时通常保持进程组的ID，但是如果设置了可执行文件的sgid位，那么进程就获得了该文件用户组的ID
  3. sticky:设置了sitcky标志位的可执行文件相当于向内核发出一个请求，当程序执行结束后依然将其保留在内存

Unix内核概述

Unix内核提供了应用程序可以运行的环境，因此内核必须实现一组服务以及相应的接口。应用程序会使用这些接口，但是通常不会和硬件资源之间交互，这一小节我们虽然标题时Unix的内核概述，但是实际上我们也不吝笔墨在介绍Unix的进程的一些概念上。

Unix内核都利用了内核态和用户态。当一个程序在用户态下执行时，它不能直接访问内核数据结构或者程序，而用户态下这些限制则不会生效。对于一个进程而言，大部分时间下都处于用户态，只有在需要内核提供服务时才切换到内核态，并且一完成相关服务马上回到用户态下。

但是要注意的是，内核本身并不是一个进程，而是进程的管理者，使用系统调用的机制来实现用户态和内核态的切换。除了用户进程以外，Unix系统中包括几个内核线程，从系统启动到系统关闭一直都处于活跃状态。这个中断和切换的机制是相当复杂的，我们后面会用比较大的篇幅去介绍，这里不多赘述。

为了让内核能够管理进程，每一个进程都由一个进程描述符（听起来像是一个字符串，实际上是一个比较复杂的数据结构哦！）表示，这个描述符包含进程当前状态的全部信息。当内核暂停一个程序的执行时，九八几个相关寄存器的内容保存在进程描述符中，这些寄存器的内容包括

  1. 程序计数器和栈指针寄存器
  2. 通用寄存器
  3. 浮点寄存器
  4. 包含CPU状态信息的处理器控制寄存器
  5. 用来跟踪对RAM访问的内存管理寄存器

当内核决定恢复进程的执行时，它用进程描述符中保存的信息就能够恢复一个进程到挂起前的状态了。当然了，进程在等待状态下的等待状态也可以由进程描述符（队列）实现。同时，Unix允许多个进程同时在内核态下执行（可重入内核）。当然了实际上在单处理器系统中只有一个进程在真正运行，但是许多进程可能在内核态下被阻塞。每个进程都运行在私有地址空间中，包括私有栈、私有数据区和代码区等等。当在内核态运行时，进程可以访问内核的数据区和代码区，但是使用另外的私有栈。因为可重入的内核设计到不同的进程访问内核的数据，我们不希望不同的两个进程破坏数据的一致性，所以同步机制成为了可重入内核实现的关键。

Unix的信号机制使得系统事件能够报告给进程。每个事件都有一个信号编号。在操作系统中一共有两种系统事件

  1. 异步通告：当用户在terminal按下ctrl+c时向进程发送中断信号SIGINT
  2. 同步错误或者异常；当进程访问非法内存地址时内核向这个进程发送一个SIGSEGV信号

如果没有理解啥叫“异步”啥叫“同步”的话呢，我到觉得也没有必要强求，因为这两个词从文法上来讲是反义词所以人们喜欢对比去理解这两个概念，但是事实上我认为这不是不理解就会不得了的概念，不理解？没事，咱接着看就得了。

Unix通过fork()和_exit()系统调用来创建和终止一个进程。调用fork()的是父进程，而新进程是它的子进程。父子进程能够找到对方是因为描述每个进程的数据结构种都包含两个指针，一个直接指向父进程一个直接指向子进程。现代Unix系统引入了进程组的概念，使得多个进程能够作为一个整体来工作。。

Unix内存管理

终于，到了令人又爱又恨的内存管理。在实际的工作中，我们常常能够碰见诸如内存泄漏，栈溢出等问题，这些都是和操作系统的内存管理有着密不可分的联系。内存管理可以说是Unix种最精密也最复杂的活动，我们在这一节描述一些内存管理的主要的问题。

虚拟内存作为内存的一个抽象，处于应用程序（进程）的内存请求和硬件内存管理单元（MMU）之间。核心思想就是虚拟地址空间，进程所用的一组内存地址不同于物理内存地址，当进程使用一个虚拟地址时内核和MMU协同定位其在内存中的实际物理位置。使用虚拟内存允许若干个程序并发的执行，应用程序所需内存大于可用物理内存时也可以执行，并且在其他方面也具有实际意义的好处。

所有的Unix操作系统都将RAM划分为两个部分，一部分专门用于存放内核映像（也就是内核代码和内核静态数据结构），另一部分由虚拟内存系统来处理。内核内存分配器（Kernel Memory Allocator）试图满足系统中对于内存的请求。

进程的虚拟地址空间包括了进程可以引用的所有虚拟内存地址。内核通常用一组内存区描述符来描述虚拟地址空间。内核分配给进程的虚拟地址空间由以下区域组成：

  1. 程序的可执行代码
  2. 程序的初始化数据
  3. 程序的未初始化数据
  4. 初始程序栈（即用户态栈）
  5. 所需共享库的可执行代码和数据
  6. 堆（由程序动态请求的内存）

所有的Unix系统都采用了请求调页的内存分配策略来处理内存。

设备驱动程序

内核通过设备驱动程序与I/O设备进行交互。设备驱动程序包含在内核种，由控制一个或多个设备的数据结构和函数组成，这些设备包括硬盘、键盘、鼠标、监视器和网络接口等等。通过特定的接口，每个驱动程序可以与内核的其他部分相互作用。

就像我们上文中提到的，特定设备的代码（驱动程序）可以被封装成为可以动态的链接进内核的模块，这样动态的方式使得设备的管理更加的轻量级。

内存的寻址

程序员偶尔会引用内存地址（这在C++编程种格外常见，但是对于python/java而言，懂得内存管理的奥妙的人就少很多了）来访问内存单元内容。我们这本书借助x86的架构来说明内存的使用。

x86 VS ARM：x86架构和ARM架构是CPU的两种架构，简单的来说两者代表了目前比较流行的两种CPU的产品，x86长于性能而ARM长于功耗，所以x86能够在家用电脑等领域呼风唤雨，而ARM在服务器以及嵌入式开发中独占鳌头。

在x86的架构中我们需要区分以下三种地址

  1. 逻辑地址：在机器语言指令中用来指定一个操作数或一条指令的地址，一个逻辑地址由一个段和一个偏移量组成，偏移量指示从段开始的地方到实际地址之间的距离
  2. 线性地址（虚拟地址）：一个32位无符号数，可以用来表达高达4GB（2^32）的地址，从0x00000000到0xffffffff
  3. 物理地址：用于内存寻址，与微处理器的地址引脚发送到内存总线上的电信号相对应，由32位或36位无符号数组成

MMU通过分段单元将一个逻辑地址转换成线性地址，接着通过分页单元将一个线性地址转换成物理地址。Intel处理器以两种不同的方式进行地址转换：保护模式和实模式。

逻辑地址

从逻辑地址谈起，一般一个段标识符是16位的段选择符，偏移量是32位的字段。不难理解，具体的线性地址（虚拟地址）是通过逻辑地址得到的，而逻辑地址是根据段选择符进行偏移得到的，我们希望快速方便的找到段选择符。因此，处理器提供了段寄存器来存放段选择符，这些段寄存器为cs/ss/ds/es/fs/gs，其中具有专门用途的是

  1. cs：代码段寄存器，指向包含程序指令的段
  2. ss：栈段寄存器，指向包含当前程序栈的段
  3. ds：数据段寄存器，指向包含静态数据和全局数据的段

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

通常情况下，GDT是唯一的，但是每个进程都可以创建和维护自己的一个LDT，GDT在主存中的地址和大小存放在gdtr控制寄存器中，当前正在被使用的LDT地址和大小存放在ldtr控制寄存器中。

加速逻辑地址访问

逻辑地址由16位段选择符+32位偏移量组成，段寄存器仅仅存放段选择符。那么为了加速逻辑地址到线性地址的转换，x86提供了一种附加的非编程的寄存器，供6个可编程的段寄存器使用。

非编程的寄存器：不能被程序员所设置的寄存器

米一个非编程的寄存器都有8个字节的段描述符，由相应的段寄存器的段选择符来指定，当一个段选择符被装入段寄存器时，相应的段描述符就由内存装入对应的非编程CPU寄存器，这样我们就避免了访问GDT或LDT，处理器只需要访问段描述符的非编程寄存器即可。仅当段寄存器的内容改变时才有必要访问GDT或LDT。

从逻辑地址到线性地址

  1. 检查段选择符的TI字段，以决定段描述符在GDT还是LDT中(不考虑加速逻辑地址访问)
  2. 从段选择符的index字段计算段描述符的地址，index的值乘以8(每个描述符的大小)加上gdtr或ldtr寄存器中的内容
  3. 把上述结果与段描述符base字段的值相加就得到了线性地址

Linux的分段

我们在上文中提到了段选择符段描述符等等，但是为什么我们要进行分段呢？

事实上，分段和分页在某种程度上有些多余，因为他们都可以划分进程的物理地址空间，而通常情况下分页方式对于Linux来说是更好的选择：

  1. 分段可以给每一个进程分配不同的线性地址空间
  2. 分页可以把同一线性地址空间映射到不同的物理空间

运行在用户态的Linux进程都使用用户代码段和数据代码段来对指令和数据寻址，而运行在内核态的Linux进程都使用内核代码段和内核数据段来寻址。

CPU的当前特权级(CPL)反映了进程是处于用户态还是内核态下面，CPL=3（用户态）时ds寄存器必须含有用户数据段的段选择符，CPL=0（内核态）时ds寄存器必须含有内核数据段的段选择符。

ss寄存器也是同理，CPL=3（用户态）时ss寄存器必须指向用户数据段的用户栈，CPL=0（内核态）时ds寄存器必须含有内核数据段的内核栈。

Linux GDT

单处理器系统中只有一个GDT，多处理器系统中每个CPU对应一个GDT，每个GDT中包含18个段描述符和14个未使用的项，这18个段描述符里有4个，分别是用户态和内核太下的代码段和数据段，其余的暂不在博客中讨论。

Linux LDT

大多数用户态下的Linux程序不适用局部描述符。

分页：从线性地址到物理地址

分页单元负责把线性地址转换成物理地址。线性地址被分成以固定长度位单位的组，称为页，页内部连续的线性地址被映射到连续的物理地址中。每个进程有一个属于自己的页目录表，可通过 CR3 寄存器找到，当进程切换的时候，只需要将新进程的页目录把地址加载到 CR3 寄存器中即可。而内核也有一个独立于其它进程的页目录表，保存在swapper_pg_dir[]数组中。

分页单元把RAM分成固定长度的页框（我们很多时候称之为物理页），每一个页框包含一个页。

页和页框：页只是一个数据块，可以存放在任何页框或磁盘中，而页框是主存的一部分，也是一个存储区域。

把线性地址映射到物理地址的数据结构称为页表，页表存放在主存中，并且在启用分页单元前由内核对页表进行初始化

主存/内存/RAM/ROM：

从80386起，Intel处理器的分页单元处理4KB的页，32位的线性地址被分为3个域：

  1. Directory: 目录10bit
  2. Table: 页表10bit
  3. Offset: 偏移量12bit (2^12=4*2^10=4KB)

线性地址的转换分为两步完成，每一步都基于一种转换表，第一种称为页目录表，第二种称为页表。

使用这种二级模式的目的是减少每个进程页表所需要的RAM的数量，如果简单的使用一级页表，那么对于32位的系统以及4KB大小的页，我们需要2^20个表项（每项4个字节时，我们需要4MB RAM）来表示每个进程的页表。

一级页表的缺点在于即使一个进程并不使用那个范围内的所有地址，我们都需要使用一个4MB的内存区域来储存页表。而二级模式通过只为进程实际使用的虚拟内存区域来请求页表来减少内存容量（只在进程实际需要一个页表时才给该页表分配RAM）。

我们要将正在使用的页目录的物理地址存放在控制寄存器cr3中，线性地址内的Directory字段决定页目录中的目录项，而目录项指向适当的页表，地址的Table决定页表中的表象，而表项含有页所在页框的物理地址，Offset字段决定页框内的相对位置。

不管是页目录表还是页表，其每一项的内容是相同的

  1. Present标志：如果被置为1，所指的页或页表就在主存中，如果该标志为0，则这一页不在主存中
  2. 包含页框物理地址最高20位的字段：如果这一项指向一个页目录，那么相应的页框就含有一个页表，如果它指向一个页表，那么相应的页框就含有一页数据
  3. 标志：Accessed标志/Dirty标志/…

与段的3种存取权限不同（读，写，执行），页的存取权限只有两种，如果页目录项或页表项的Read/Write标志等于0，表示对应的页表或页是只读的，否则是可读写的。

扩展分页

从Pentium开始，x86引入了扩展分页，允许页框大小为4MB而不是4KB。在这种情况下，32位地址被分为了10位的Directory和22位的Offset，内核可以不用中间页表进行地址转换，从而节省内存。

常规分页（一个例子）

假设内核给一个正在运行的进程分配的线性地址空间是从0x20000000到0x2003ffff，这个空间由64页组成。注意，这里的地址属于线性地址，我们不关心包含这些页的页框的物理地址，事实上一些页甚至可能不在主存中。

我们从分配给线程的最高10位开始看，这两个地址以最高10位（Directory）是相同的，都是0b0010000000，表示为十六进制是0x080，表示为十进制是128。因此这两个地址的Directory字段都指向进程页目录表的第129项，这一项中含有分配给该进程的页表的物理地址，如果没有给这个进程分配其他的线性地址，那么页目录表的其余1023项（Directory位共有10位，这意味着Directory对应的页目录表有1024项）均为0。

中间10位的值从0到0x03f，或十进制从0到63，因而页表中只有前63个表项是有意的，其余的960个表项都填0。

假设进程需要获取线性地址0x20021406中的地址，那么分页单元会进行如下的处理

  1. Directory字段的0x080用于选择页目录表的第0x080项，此项指向和进程相关的页的页表
  2. Table字段0x21用于选择页表的第0x21项，此项指向包含所需页的页框
  3. Offset字段0x406用于在目标页框中读偏移量位0x406中的字节

如果在第二步中，页表第0x21项的Present标志位0，那么这一页就不在主存中。在这种情况下，分页单元在线性地址转换的同时会产生一个缺页异常。

从32位寻址到36位寻址：对于大型服务器来说，他们往往需要比4GB更大的内存来运行数以千计的进程，现在Interl的处理器的寻址能力已经达到了2^36=64GB，当然在使用的过程中，我们页引入了新的分页机制。

64位系统：现在64位的家用机和个人电脑也已称为主流，64位支持的寻址空间为2^64，大于1亿GB。在Linux中，对于64位系统常常采用四级模式，将地址分为Global Dir/Upper Dir/Middle Dir/Table/Offer来进行页寻址。

硬件高速缓存

众所周知，目前电脑运算速度的瓶颈出现在RAM的存取之中，CPU可能在这个过程中等待相当长的时间，为了解决这个问题，我们引入了硬件高速缓存，原理是一般来说，最近最常用的相邻地址在将来被又用到的可能性很大，所以引入小而快的内存来存放最近经常使用的代码和数据（我们常称之为“行”）。

高速缓存单元位于分页单元和主内存之间，包含一个硬件高速缓存内存和高速缓存控制器。其中

  1. 硬件高速缓存内存：存放真正的数据内容（行）
  2. 高速缓存控制器：存放一个表项数组，数组中每一个元素对应硬件高速缓存内存中的一个行。

当CPU试图访问一个RAM存储单元时，CPU先去检查高速缓存控制器，判断是否命中一个告诉缓存。当

  1. 命中一个高速缓存（Hooray！）：通过高速缓存内存进行快速的读写
  2. 没有命中高速缓存：高速缓存行被写回内存中，并且必要的话将正确的行从RAM中取出放到高速缓存的表项中

转换后援缓冲器（TLB：Translation Lookaside Buffer）

x86处理器常常使用名为TLB的高速缓存用于加快线性地址的转换，当一个线性地址第一次被使用的时候，通过访问RAM中的页（目录）表计算相应的物理地址，同时物理地址被存放在TLB的一个表项中，这样下次对于同一个线性地址的引用可以快速地得到转换。

物理内存布局

在初始化阶段，内核需要建立一个物理地址映射来指定哪些物理地址范围对内核可用而哪些不可用（不可用的原因可能是因为他们映射硬件设备I/O的共享内存，或者因为相应的页框含有BIOS数据）。

BIOS: BIOS是英文”Basic Input Output System”的缩略词，直译过来后中文名称就是”基本输入输出系统”。BIOS是个人电脑启动时加载的第一个软件。 其实，它是一组固化到计算机内主板上一个ROM芯片上的程序，它保存着计算机最重要的基本输入输出的程序、开机后自检程序和系统自启动程序，它可从CMOS中读写系统设置的具体信息。其主要功能是为计算机提供最底层的、最直接的硬件设置和控制。

一般来说，Linux内核放在RAM中物理地址从0x00100000开始的地方，所需的页框总数取决于内核的配置方案，通常情况下内核可以被安装在小于3MB的RAM中。那么为什么不从0x00000000开始？从0x00000000到0x000fffff这2^20=1MB的地方被什么使用了？

这是因为页框0由BIOS使用，同时物理地址从0x000a0000到0x000fffff的范围通常留给BIOS例程。

进程页表

进程的线性空间分为两部分

  1. 0x00000000到0xbfffffff的线性地址，无论程序运行在用户态还是内核态都可以寻址
  2. 0xc0000000到0xffffffff的线性地址，只有内核态的进程才能寻址

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

内核页表

内核维持一组自己使用的页表，驻留在主内核页全局目录（master kernel Page Global Directory）中系统初始化后，这组页表没有被任何进程或内核线程使用。内核初始化自己的页表分为两个阶段

  1. 第一个阶段：内核创建一个有限的地址空间，包括内核的代码段和数据段，初始页表和存放动态数据的共128KB的空间，这个最小限度的地址空间仅够将内核装入RAM和对其初始化的核心数据结构
  2. 第二个阶段：内核利用剩余的RAM并建立分页表。