文章目录

操作系统 ucoreOS 实验记录

(本周任务完成)目前实验进度:[Lab 4 内核线程管理]
本文参考整合了多方资料,面向实验速通选手。
本实验做完和做懂是两码事,建议还是认真看一下。

前言

近期 操作系统导论 这门课程进入了实验阶段, ucoreOS 实验共由 9个部分 构成,实验内容基本涵盖了构建一个简易操作系统的全部流程,具有很高的实用意义,故写下这篇文章以记录实验过程。如果你在实验过程中遇到了什么问题可以在下方留言讨论,同时敬请指正文章内容。

实验资料

Lab 0 操作系统实验准备

实验目的

  • 了解操作系统开发实验环境
  • 熟悉命令行方式的编译、调试工程
  • 掌握基于硬件模拟器的调试技术
  • 熟悉C语言编程和指针的概念
  • 了解X86汇编语言

实验内容(操作部分)

ucore系统结构概览

1

设置实验环境

准备Linux系统

本实验是在 Linux系统 上进行的,推荐使用 虚拟机 安装运行,我使用的系统是安装在VMware Workstation Pro 16.0上的Kali Linux 2022.2 ,你可以使用其他系统,相信各位在前面的课程中已经安装好了Ubuntu 20.04系统,可以直接拿来用,如果想要安装其他的版本可以自行搜索相关教程。(本实验不推荐使用WSL,之前我使用的是 WSL2 下的 Ubuntu 20.04.4 LTS ,但经常遇到一些莫名其妙的BUG。虽然本实验中不适合用,但WSL本身是有一些优点的,如果你的系统已经升级为了 Windows 11 并且想要尝试在WSL2中安装Linux,可以参考森大的这篇文章 Windows Subsystem for Linux 2 的艺术 进行操作。)

2

我实验时使用的系统如下图所示。

3

安装GCC编译环境

GCC的重要性不言而喻,它一般是系统自带就有的,如果你不确定是否已经安装,可以运行以下命令来安装编译构建时必需的工具:

sudo apt-get update    //更新软件包列表
sudo apt-get install build-essential    //安装编译必需软件包

输入gcc --version时能看到版本号则为安装正确。

4

安装GDB

运行以下命令安装GDB调试工具:

sudo apt-get install gdb

输入gdb --version时能看到版本号则为安装正确。

5

安装Git工具

Git工具用于操作和管理代码仓库,我们平时要从Github克隆仓库代码到本地时会经常用到,可以运行以下命令进行安装:

sudo apt-get install git

输入git --version时能看到版本号则为安装正确。

6

克隆实验仓库

克隆时需要注意的一点是,我们的实验用的是 ucore ,而代码仓库的 main 分支上的是 rcore ,我们克隆下来后还需要切换为 master 分支才行。具体命令如下:

git clone https://github.com/chyyuu/os_kernel_lab.git    //克隆实验仓库
cd os_kernel_lab    //切换至仓库目录
git checkout origin/master    //切换至master分支
git checkout -b master    //基于远程master分支在本地建立master分支

由于不科学的原因,我们克隆的时候可能会异常地慢,但可惜之前很多能用的镜像加速都被封了,且在Linux上配置科学上网有一定难度,所以综合下来考虑,还是搁这硬等它下载好比较妥当,一共90M左右其实还好。

如图所示即为操作正确,分支必须为 master ,仓库目录下必须有 labcodes 文件夹。

7

安装硬件模拟器QEMU

QEMU 是优秀且知名的一款 硬件模拟器工具 ,对于我们的实验而言,它可用于模拟一台 X86 计算机,让 ucore 能够在其上运行。

使用下面的命令安装QEMU:

sudo apt-get install qemu qemu-system-i386  //安装qemu的i386模拟器

// 如果安装完后直接输入qemu没有反应,则运行以下指令
sudo ln -s /usr/bin/qemu-system-i386 /usr/bin/qemu  //建立x86模拟器的软链接

当输入命令 qemu --version 能看到版本号时则代表安装成功。

8

使用硬件模拟器QEMU

此处直接引用了实验指导书上的内容

qemu 运行可以有多参数,格式如:

qemu [options] [disk_image]

其中 disk_image 即硬盘镜像文件。

部分参数说明:

`-hda file'        `-hdb file' `-hdc file' `-hdd file'
    使用 file  作为硬盘0、1、2、3镜像。
`-fda file'  `-fdb file'
    使用 file  作为软盘镜像,可以使用 /dev/fd0 作为 file 来使用主机软盘。
`-cdrom file'
    使用 file  作为光盘镜像,可以使用 /dev/cdrom 作为 file 来使用主机 cd-rom。
`-boot [a|c|d]'
    从软盘(a)、光盘(c)、硬盘启动(d),默认硬盘启动。
`-snapshot'
    写入临时文件而不写回磁盘镜像,可以使用 C-a s 来强制写回。
`-m megs'
    设置虚拟内存为 msg M字节,默认为 128M 字节。
`-smp n'
    设置为有 n 个 CPU 的 SMP 系统。以 PC 为目标机,最多支持 255 个 CPU。
`-nographic'
    禁止使用图形输出。
其他:
    可用的主机设备 dev 例如:
        vc
            虚拟终端。
        null
            空设备
        /dev/XXX
            使用主机的 tty。
        file: filename
            将输出写入到文件 filename 中。
        stdio
            标准输入/输出。
        pipe:pipename
            命令管道 pipename。
        等。
    使用 dev 设备的命令如:
        `-serial dev'
            重定向虚拟串口到主机设备 dev 中。
        `-parallel dev'
            重定向虚拟并口到主机设备 dev 中。
        `-monitor dev'
            重定向 monitor 到主机设备 dev 中。
    其他参数:
        `-s'
            等待 gdb 连接到端口 1234。
        `-p port'
            改变 gdb 连接端口到 port。
        `-S'
            在启动时不启动 CPU, 需要在 monitor 中输入 'c',才能让qemu继续模拟工作。
        `-d'
            输出日志到 qemu.log 文件。

(此处仅是举例)例如:

qemu -hda ucore.img -parallel stdio        // 让ucore在qemu模拟的x86硬件环境中运行
qemu -S -s -hda ucore.img -monitor stdio    // 开启远程调试

使用GDB配合QEMU对ucore进行源码级调试

ucore 代码编译

在实验文件夹下使用 make 命令即可,make会按照当前目录下的Makefile脚本构建项目。

例如在Lab1中:

cd ./os_kernel_lab/labcodes/lab1
make

此时在lab1目录下的bin目录中会生成一系列的目标文件:

  • ucore.img:系统镜像文件
  • kernel: ELF格式的系统内核文件,被嵌入到了ucore.img
  • bootblock: 虚拟的硬盘主引导扇区(512字节),包含了bootloader执行代码,被嵌入到了ucore.img
  • sign:小工具,用来生成符合规范的虚拟硬盘主引导扇区

还生成了很多其他文件,后续的实验会慢慢接触到。

9

使用远程调试

为了与qemu配合进行源代码级别的调试,需要先让qemu等待gdb调试器的接入并且不能让qemu中的CPU在此之前执行,因此启动qemu的时候,我们需要使用参数 -S –s 来做到这一点,这相当于在 本地的1234端口 开启远程调试服务。

在使用了前面提到的参数启动qemu之后,qemu中的CPU并不会马上开始执行,这时我们启动gdb,然后在gdb命令行界面下,使用下面的命令连接到qemu:

//此时在lab1目录下
(gdb)  target remote :1234

然后输入c(也就是continue)命令之后,qemu会继续执行下去,但是gdb由于不知道任何符号信息,并且也没有下断点,是不能进行源码级的调试的。为了让gdb获知符号信息,需要指定调试目标文件,gdb中使用file命令:

(gdb)  file ./bin/kernel    

之后gdb就会载入这个文件中的符号信息了。

这时通过gdb就可以对ucore代码进行调试了,以在lab1中调试memset函数为例:

在第一个终端中执行:

//此时在lab1目录下
qemu -S -s -hda ./bin/ucore.img -monitor stdio     // 启动qemu运行ucore并开启远程调试服务

这时会弹出一个窗口,qemu已经开始等待远程gdb的连接了,接下来打开第二个终端运行gdb。(如果你在此过程中发现鼠标指针不见了,这是因为你点击到了qemu的图形窗口导致鼠标被其捕获,使用快捷键Ctrl+Alt+G即可重新获取鼠标控制权。)

在第二个终端中执行:

cd os_kernel_lab/labcodes/lab1    //切换至lab1的目录
gdb    //启动gdb
(gdb) file ./bin/kernel    //在gdb中载入目标文件以获取符号信息
(gdb) target remote :1234    //用gdb连接至本地的1234端口进行调试
(gdb) break memset    //在memset函数处下断点
(gdb) continue    //调试至断点

10

使用GDB配置文件

从上面可以看到,为了进行源码级调试,需要输入很多指令。为了方便,可以将这些命令保存在脚本中,并让gdb在启动的时候载入。

以lab1为例,在 lab1/tools 目录下,执行完 make 后,我们可以修改 gdbinit 文件。

cd ./tools    //切换至tools目录
vim gdbinit    //使用vim修改gdbinit的文件内容,如果提示未安装则使用sudo apt-get install vim进行安装

//此时会进入文本编辑窗口,如下编辑文件内容(第5-10行),注释不用复制
file bin/kernel    //在gdb中载入目标文件以获取符号信息
set architecture i8086    //设置CPU架构为i8086
target remote :1234    //用gdb连接至本地的1234端口进行调试
break kern_init    //在内核初始化函数处设置断点
define hook-stop    //这部分设置每次单步调试都显示出附近两行的汇编以方便调试
x/2i $pc
end

//然后按下ESC键退出编辑模式,最后输入:wq后按ENTER键保存修改并退出。

使用上面编辑好的脚本启动gdb:

cd ..    //退回lab1目录
gdb -tui -x tools/gdbinit    //以gdbinit脚本启动gdb并开启源代码视图

11

Lab 0 完成

其他

后续会用到的一些指令:

make grade    // 测试编写的实验代码是否基本正确
make handin    // 如果实现基本正确(即看到上条指令输出都是OK)则生成实验打包 
make qemu    // 让OS实验工程在qemu上运行
make debug    // 实现通过gdb远程调试OS实验工程

diff 用于比较文本或者文件夹差异。 patch 可以对文件或者文件夹应用修改。

例如实验中可能会在 proj_b 中应用前一个实验 proj_a 中对文件的修改,可以使用如下命令:

diff -r -u -P proj_a_original proj_a_mine > diff.patch
cd proj_b
patch -p1 -u < ../diff.patch

注意: proj_a_original 指 proj_a 的源文件,即未经修改的源码包, proj_a_mine 修改后的代码包。第一条命令是递归的比较文件夹差异,并将结果重定向输出到 diff.patch 文件中,第三条命令是将 proj_a 的修改应用到 proj_b 文件夹中的代码中

设定调试目标架构:

此处直接引用了实验指导书上的内容

在调试的时候,我们也许需要调试非i386保护模式的代码,而是比如8086实模式的代码,这时我们需要设定当前使用的架构:

(gdb) set architecture i8086

这个方法在调试不同架构或者说不同模式的代码时还是有用处的。

13

加载调试目标:

此处直接引用了实验指导书上的内容

在上面小节,我们提到为了能够让gdb识别变量的符号,我们必须给gdb载入符号表等信息。在进行gdb本地应用程序调试的时候,因为在指定了执行文件时就已经加载了文件中包含的调试信息,因此不用再使用gdb命令专门加载了。但是在使用qemu进行远程调试的时候,我们必须手动加载符号表,也就是在gdb中用file命令。

这样加载调试信息都是按照elf文件中制定的虚拟地址进行加载的,这在静态连接的代码中没有任何问题。但是在调试含有动态链接库的代码时,动态链接库的ELF执行文件头中指定的加载虚拟地址都是0,这个地址实际上是不正确的。从操作系统角度来看,用户态的动态链接库的加载地址都是由操作系统动态分配的,没有一个固定值。然后操作系统再把动态链接库加载到这个地址,并由用户态的库链接器(linker)把动态链接库中的地址信息重新设置,自此动态链接库才可正常运行。

由于分配地址的动态性,gdb并不知道这个分配的地址是多少,因此当我们在对这样动态链接的代码进行调试的时候,需要手动要求gdb将调试信息加载到指定地址。下面,我们要求gdb将linker加载到0x6fee6180这个地址上:

(gdb) add-symbol-file android_test/system/bin/linker 0x6fee6180

12

这个方法在操作系统中调试动态链接器时特别有用。

实验内容(理论部分)

编译可调试的目标文件

为了使得编译出来的代码能够被gdb这样的调试器调试,我们需要在使用gcc编译源文件的时候添加参数: -g ,这样编译出来的目标文件中才会包含可以用于调试器进行调试的相关符号信息。

AT&T汇编基本语法

这部分内容我们在 计算机系统 课程已经学习掌握了,在此直接略过,如果还想复习一下可以 查看实验指导书上的内容

make和Makefile

此处直接引用了实验指导书上的内容

GNU make(简称make)是一种代码维护工具,在大中型项目中,它将根据程序各个模块的更新情况,自动的维护和生成目标代码。

make命令执行时,需要一个 makefile (或Makefile)文件,以告诉make命令需要怎么样的去编译和链接程序。首先,我们用一个示例来说明makefile的书写规则。以便给大家一个感性认识。这个示例来源于gnu的make使用手册,在这个示例中,我们的工程有8个c文件,和3个头文件,我们要写一个makefile来告诉make命令如何编译和链接这几个文件。我们的规则是:

  • 如果这个工程没有编译过,那么我们的所有c文件都要编译并被链接。
  • 如果这个工程的某几个c文件被修改,那么我们只编译被修改的c文件,并链接目标程序。
  • 如果这个工程的头文件被改变了,那么我们需要编译引用了这几个头文件的c文件,并链接目标程序。

只要我们的makefile写得够好,所有的这一切,我们只用一个make命令就可以完成,make命令会自动智能地根据当前的文件修改的情况来确定哪些文件需要重编译,从而自己编译所需要的文件和链接目标程序。

makefile的规则:

target ... : prerequisites ...
    command
    ...
    ...

target也就是一个目标文件,可以是object file,也可以是执行文件。还可以是一个标签(label)。prerequisites就是,要生成那个target所需要的文件或是目标。command也就是make需要执行的命令(任意的shell命令)。 这是一个文件的依赖关系,也就是说,target这一个或多个的目标文件依赖于prerequisites中的文件,其生成规则定义在 command中。如果prerequisites中有一个以上的文件比target文件要新,那么command所定义的命令就会被执行。这就是makefile的规则。也就是makefile中最核心的内容。

GDB使用

这部分内容我们在 计算机系统 课程已经学习掌握了,在此直接略过,如果还想复习一下可以 查看实验指导书上的内容 ,也可以看看肖神的文章 gdb 常用命令

GCC基本内联汇编

此处直接引用了实验指导书上的内容

GCC 提供了两类内联汇编语句: 基本内联汇编语句 扩展内联汇编语句 。GCC基本内联汇编很简单,一般是按照下面的格式:

    asm("statements");

例如:

    asm("nop"); asm("cli");

asm __asm__ 的含义是完全一样的。如果有多行汇编,则每一行都要加上 \n\t 。其中的 \n 是换行符, \t 是 tab 符,在每条指令的末尾加上这两个符号,是为了让 GCC 把内联汇编代码翻译成一般的汇编代码时能够保证换行和留有一定的空格。对于基本asm语句,GCC 编译出来的汇编代码就是双引号里的内容。例如:

        asm( "pushl %eax\n\t"
             "movl $0,%eax\n\t"
             "popl %eax"
        );

实际上 GCC 在处理汇编时,是要把asm(...)的内容"打印"到汇编文件中,所以格式控制字符是必要的。再例如:

    asm("movl %eax, %ebx");
    asm("xorl %ebx, %edx");
    asm("movl $0, _boo);

在上面的例子中,由于我们在内联汇编中改变了 edx 和 ebx 的值,但是由于 GCC 的特殊的处理方法,即先形成汇编文件,再交给 GAS 去汇编,所以 GAS 并不知道我们已经改变了 edx 和 ebx 的值,如果程序的上下文需要 edx 或 ebx 作其他内存单元或变量的暂存,就会产生预料之外的多次赋值,引起严重的后果。对于变量 _boo 也存在一样的问题。为了解决这个问题,就要用到扩展 GCC 内联汇编语法。

参考:

GCC扩展内联汇编

此处直接引用了实验指导书上的内容

使用GCC扩展内联汇编的例子如下:

#define read_cr0() ({ \
unsigned int __dummy; \
__asm__( \
    "movl %%cr0,%0\n\t" \
    :"=r" (__dummy)); \
__dummy; \
})

它代表什么含义呢?这需要从其基本格式讲起。GCC扩展内联汇编的基本格式是:

asm [volatile] ( Assembler Template
   : Output Operands
   [ : Input Operands
   [ : Clobbers ] ])

其中,__asm__ 表示汇编代码的开始,其后可以跟 __volatile__(这是可选项),其含义是避免 "asm" 指令被删除、移动或组合,在执行代码时,如果不希望汇编语句被 GCC 优化而改变位置,就需要在 asm 符号后添加 volatile 关键词:asm volatile(...);或者更详细地说明为:__asm__ __volatile__(...);然后就是小括弧,括弧中的内容是具体的内联汇编指令代码。 "" 为汇编指令部分,例如, "movl %%cr0,%0\n\t" 。数字前加前缀 "%",如%1,%2等表示使用寄存器的样板操作数。可以使用的操作数总数取决于具体CPU中通用寄存器的数量,如Intel可以有8个。指令中有几个操作数,就说明有几个变量需要与寄存器结合,由GCC在编译时根据后面输出部分和输入部分的约束条件进行相应的处理。由于这些样板操作数的前缀使用了"%",因此,在用到具体的寄存器时就在前面加两个%,如%%cr0。

输出部分 (output operand list),用以规定对输出变量(目标操作数)如何与寄存器结合的约束(constraint),输出部分可以有多个约束,互相以逗号分开。每个约束以“=”开头,接着用一个字母来表示操作数的类型,然后是关于变量结合的约束。例如,上例中:

:"=r" (__dummy)

“=r”表示相应的目标操作数(指令部分的%0)可以使用任何一个通用寄存器,并且变量__dummy 存放在这个寄存器中,但如果是:

:"=m"(__dummy)

"=m"就表示相应的目标操作数是存放在内存单元__dummy中。表示约束条件的字母很多,下表给出几个主要的约束字母及其含义:

字母含义
m, v, o内存单元
R任何通用寄存器
Q寄存器eax, ebx, ecx,edx之一
I, h直接操作数
E, F浮点数
G任意
a, b, c, d寄存器eax/ax/al, ebx/bx/bl, ecx/cx/cl或edx/dx/dl
S, D寄存器esi或edi
I常数(0~31)

输入部分 (input operand list):输入部分与输出部分相似,但没有"="。如果输入部分一个操作数所要求使用的寄存器,与前面输出部分某个约束所要求的是同一个寄存器,那就把对应操作数的编号(如"1","2"等)放在约束条件中。在后面的例子中,可看到这种情况。

修改部分 (clobber list,也称 乱码列表):这部分常常以"memory"为约束条件,以表示操作完成后内存中的内容已有改变,如果原来某个寄存器的内容来自内存,那么现在内存中这个单元的内容已经改变。乱码列表通知编译器,有些寄存器或内存因内联汇编块造成乱码,可隐式地破坏了条件寄存器的某些位(字段)。 注意,指令部分为必选项,而输入部分、输出部分及修改部分为可选项,当输入部分存在,而输出部分不存在时,冒号":"要保留,当"memory"存在时,三个冒号都要保留,例如:

#define __cli() __asm__ __volatile__("cli": : :"memory")

下面是一个例子:

int count=1;
int value=1;
int buf[10];
void main()
{
    asm(
        "cld \n\t"
        "rep \n\t"
        "stosl"
    :
    : "c" (count), "a" (value) , "D" (buf)
    );
}

得到的主要汇编代码为:

movl count,%ecx
movl value,%eax
movl buf,%edi
#APP
cld
rep
stosl
#NO_APP

cld,rep,stos这几条语句的功能是向buf中写上count个value值。冒号后的语句指明输入,输出和被改变的寄存器。通过冒号以后的语句,编译器就知道你的指令需要和改变哪些寄存器,从而可以优化寄存器的分配。其中符号"c"(count)指示要把count的值放入ecx寄存器。类似的还有:

a eax
b ebx
c ecx
d edx
S esi
D edi
I 常数值,(0 - 31)
q,r 动态分配的寄存器
g eax,ebx,ecx,edx或内存变量
A 把eax和edx合成一个64位的寄存器(use long longs)

也可以让gcc自己选择合适的寄存器。如下面的例子:

asm("leal (%1,%1,4),%0"
    : "=r" (x)
    : "0" (x)
);

这段代码的主要汇编代码为:

movl x,%eax
#APP
leal (%eax,%eax,4),%eax
#NO_APP
movl %eax,x

几点说明:

  • [1] 使用q指示编译器从eax, ebx, ecx, edx分配寄存器。 使用r指示编译器从eax, ebx, ecx, edx, esi, edi分配寄存器。
  • [2] 不必把编译器分配的寄存器放入改变的寄存器列表,因为寄存器已经记住了它们。
  • [3] "="是标示输出寄存器,必须这样用。
  • [4] 数字%n的用法:数字表示的寄存器是按照出现和从左到右的顺序映射到用"r"或"q"请求的寄存器.如果要重用"r"或"q"请求的寄存器的话,就可以使用它们。
  • [5] 如果强制使用固定的寄存器的话,如不用%1,而用ebx,则:
asm("leal (%%ebx,%%ebx,4),%0"
    : "=r" (x)
    : "0" (x) 
);

注意要使用两个%,因为一个%的语法已经被%n用掉了。

参考:

了解处理器硬件

这部分了解即可

要想深入理解ucore,就需要了解支撑ucore运行的硬件环境,即了解处理器体系结构(了解硬件对ucore带来影响)和机器指令集(读懂ucore的汇编)。ucore目前支持的硬件环境是基于Intel 80386以上的计算机系统。更多的硬件相关内容(比如保护模式等)将随着实现ucore的过程逐渐展开介绍。

Intel 80386运行模式

点击打开实验指导书浏览相关内容。

Intel 80386内存架构

点击打开实验指导书浏览相关内容。

Intel 80386寄存器

此处直接引用了实验指导书上的内容

80386的寄存器可以分为8组:通用寄存器,段寄存器,指令指针寄存器,标志寄存器,系统地址寄存器,控制寄存器,调试寄存器,测试寄存器,它们的宽度都是32位。一般程序员看到的寄存器包括通用寄存器,段寄存器,指令指针寄存器,标志寄存器

General Register(通用寄存器):EAX/EBX/ECX/EDX/ESI/EDI/ESP/EBP这些寄存器的低16位就是8086的 AX/BX/CX/DX/SI/DI/SP/BP,对于AX,BX,CX,DX这四个寄存器来讲,可以单独存取它们的高8位和低8位 (AH/AL/BH/BL/CH/CL/DH/DL)。它们的含义如下:

  • EAX:累加器
  • EBX:基址寄存器
  • ECX:计数器
  • EDX:数据寄存器
  • ESI:源地址指针寄存器
  • EDI:目的地址指针寄存器
  • EBP:基址指针寄存器
  • ESP:堆栈指针寄存器

27

Segment Register(段寄存器,也称Segment Selector,段选择符,段选择子):除了8086的4个段外(CS/DS/ES/SS),80386还增加了两个段FS/GS,这些段寄存器都是16位的,用于不同属性内存段的寻址,它们的含义如下:

  • CS:代码段(Code Segment)
  • DS:数据段(Data Segment)
  • ES:附加数据段(Extra Segment)
  • SS:堆栈段(Stack Segment)
  • FS:附加段
  • GS:附加段

28

Instruction Pointer(指令指针寄存器):EIP的低16位就是8086的IP,它存储的是下一条要执行指令的内存地址,在分段地址转换中,表示指令的段内偏移地址。

29

Flag Register(标志寄存器):EFLAGS,和8086的16位标志寄存器相比,增加了4个控制位,这20位控制/标志位的位置如下图所示:

30

相关的控制/标志位含义是:

  • CF(Carry Flag):进位标志位
  • PF(Parity Flag):奇偶标志位
  • AF(Assistant Flag):辅助进位标志位
  • ZF(Zero Flag):零标志位
  • SF(Singal Flag):符号标志位
  • IF(Interrupt Flag):中断允许标志位,由CLI,STI两条指令来控制;设置IF位使CPU可识别外部(可屏蔽)中断请求,复位IF位则禁止中断,IF位对不可屏蔽外部中断和故障中断的识别没有任何作用
  • DF(Direction Flag):向量标志位,由CLD,STD两条指令来控制
  • OF(Overflow Flag):溢出标志位
  • IOPL(I/O Privilege Level):I/O特权级字段,它的宽度为2位,它指定了I/O指令的特权级。如果当前的特权级别在数值上小于或等于IOPL,那么I/O指令可执行。否则,将发生一个保护性故障中断
  • NT(Nested Task):控制中断返回指令IRET,它宽度为1位。若NT=0,则用堆栈中保存的值恢复EFLAGS,CS和EIP从而实现中断返回;若NT=1,则通过任务切换实现中断返回。在ucore中,设置NT为0。

还有一些应用程序无法访问的控制寄存器,如CR0,CR2,CR3...

了解ucore编程方法和通用数据结构

面向对象编程方法

点击打开实验指导书浏览相关内容。

通用数据结构-双向循环链表

点击打开实验指导书浏览相关内容。

Lab 1 系统软件启动过程

实验目的

操作系统是一个软件,也需要通过某种机制加载并运行它。 在这里我们将通过另外一个更加简单的软件: bootloader 来完成这些工作。为此,我们需要完成一个能够切换到x86的保护模式并显示字符的bootloader,为启动操作系统ucore做准备。

lab1提供了一个非常小的bootloader和ucore OS,整个bootloader执行代码小于512个字节,这样才能放到硬盘的主引导扇区中。通过分析和实现这个bootloader和ucore OS,读者可以了解到:

  • 计算机原理

    • CPU的编址与寻址: 基于分段机制的内存管理
    • CPU的中断机制
    • 外设:串口/并口/CGA(Color Graphics Adapter) 彩色图形适配器,时钟,硬盘
  • bootloader软件

    • 编译运行bootloader的过程
    • 调试bootloader的方法
    • PC启动bootloader的过程
    • ELF执行文件的格式和加载
    • 外设访问:读硬盘,在CGA上显示字符串
  • ucore OS软件

    • 编译运行ucore OS的过程
    • ucore OS的启动过程
    • 调试ucore OS的方法
    • 函数调用关系:在汇编级了解函数调用栈的结构和处理过程
    • 中断管理:与软件相关的中断处理
    • 外设管理:时钟

实验内容(操作部分)

lab1中包含一个bootloader和一个OS。这个bootloader可以切换到X86保护模式,能够读磁盘并加载ELF执行文件格式,并显示字符。

实验报告要求

点击打开实验指导书浏览实验报告要求

练习总体要求:列出本实验各练习中对应的OS原理的知识点,并说明本实验中的实现部分如何对应和体现了原理中的基本概念和关键知识点。

如果你需要编写Markdown格式的实验报告,推荐下载Typora

项目组成

lab1的整体目录结构如下所示:

.
├── boot
│   ├── asm.h
│   ├── bootasm.S
│   └── bootmain.c
├── kern
│   ├── debug
│   │   ├── assert.h
│   │   ├── kdebug.c
│   │   ├── kdebug.h
│   │   ├── kmonitor.c
│   │   ├── kmonitor.h
│   │   ├── panic.c
│   │   └── stab.h
│   ├── driver
│   │   ├── clock.c
│   │   ├── clock.h
│   │   ├── console.c
│   │   ├── console.h
│   │   ├── intr.c
│   │   ├── intr.h
│   │   ├── kbdreg.h
│   │   ├── picirq.c
│   │   └── picirq.h
│   ├── init
│   │   └── init.c
│   ├── libs
│   │   ├── readline.c
│   │   └── stdio.c
│   ├── mm
│   │   ├── memlayout.h
│   │   ├── mmu.h
│   │   ├── pmm.c
│   │   └── pmm.h
│   └── trap
│       ├── trap.c
│       ├── trapentry.S
│       ├── trap.h
│       └── vectors.S
├── libs
│   ├── defs.h
│   ├── elf.h
│   ├── error.h
│   ├── printfmt.c
│   ├── stdarg.h
│   ├── stdio.h
│   ├── string.c
│   ├── string.h
│   └── x86.h
├── Makefile
└── tools
    ├── function.mk
    ├── gdbinit
    ├── grade.sh
    ├── kernel.ld
    ├── sign.c
    └── vector.c

10 directories, 48 files

bootloader部分

  • boot/bootasm.S :定义并实现了bootloader最先执行的函数start,此函数进行了一定的初始化,完成了从实模式到保护模式的转换,并调用bootmain.c中的bootmain函数。
  • boot/bootmain.c:定义并实现了bootmain函数实现了通过屏幕、串口和并口显示字符串。bootmain函数加载ucore操作系统到内存,然后跳转到ucore的入口处执行。
  • boot/asm.h:是bootasm.S汇编文件所需要的头文件,主要是一些与X86保护模式的段访问方式相关的宏定义。

ucore操作系统部分

系统初始化部分:

  • kern/init/init.c:ucore操作系统的初始化启动代码

内存管理部分:

  • kern/mm/memlayout.h:ucore操作系统有关段管理(段描述符编号、段号等)的一些宏定义
  • kern/mm/mmu.h:ucore操作系统有关X86 MMU等硬件相关的定义,包括EFLAGS寄存器中各位的含义,应用/系统段类型,中断门描述符定义,段描述符定义,任务状态段定义,NULL段声明的宏SEG_NULL, 特定段声明的宏SEG,设置中断门描述符的宏SETGATE
  • kern/mm/pmm.[ch]:设定了ucore操作系统在段机制中要用到的全局变量:任务状态段ts,全局描述符表 gdt[],加载全局描述符表寄存器的函数lgdt,临时的内核栈stack0;以及对全局描述符表和任务状态段的初始化函数gdt_init

外设驱动部分:

  • kern/driver/intr.[ch]:实现了通过设置CPU的eflags来屏蔽和使能中断的函数
  • kern/driver/picirq.[ch]:实现了对中断控制器8259A的初始化和使能操作
  • kern/driver/clock.[ch]:实现了对时钟控制器8253的初始化操作
  • kern/driver/console.[ch]:实现了对串口和键盘的中断方式的处理操作

中断处理部分:

  • kern/trap/vectors.S:包括256个中断服务例程的入口地址和第一步初步处理实现。注意,此文件是由tools/vector.c在编译ucore期间动态生成的
  • kern/trap/trapentry.S:紧接着第一步初步处理后,进一步完成第二步初步处理;并且有恢复中断上下文的处理,即中断处理完毕后的返回准备工作
  • kern/trap/trap.[ch]:紧接着第二步初步处理后,继续完成具体的各种中断处理操作

内核调试部分:

  • kern/debug/kdebug.[ch]:提供源码和二进制对应关系的查询功能,用于显示调用栈关系。其中补全print_stackframe函数是需要完成的练习。其他实现部分不必深究。
  • kern/debug/kmonitor.[ch]:实现提供动态分析命令的kernel monitor,便于在ucore出现bug或问题后,能够进入kernel monitor中,查看当前调用关系。实现部分不必深究。
  • kern/debug/panic.c | assert.h:提供了panic函数和assert宏,便于在发现错误后,调用kernel monitor。大家可在编程实验中充分利用assert宏和panic函数,提高查找错误的效率。

公共库部分

  • libs/defs.h:包含一些无符号整型的缩写定义。
  • libs/x86.h:一些用GNU C嵌入式汇编实现的C函数(由于使用了inline关键字,所以可以理解为宏)。

工具部分

  • Makefile和function.mk:指导make完成整个软件项目的编译,清除等工作。
  • sign.c:一个C语言小程序,是辅助工具,用于生成一个符合规范的硬盘主引导扇区。
  • tools/vector.c:生成vectors.S,此文件包含了中断向量处理的统一实现。

编译方法

在lab1目录下执行make,可以生成ucore.img(生成于bin目录下)。ucore.img是一个包含了bootloader或OS的硬盘镜像,通过执行如下命令可在硬件虚拟环境 qemu中运行bootloader或OS:

make qemu

则可以得到如下显示界面(仅供参考)

 (THU.CST) os is loading ...

Special kernel symbols:
  entry  0x00100000 (phys)
  etext  0x00103468 (phys)
  edata  0x0010ea18 (phys)
  end    0x0010fd80 (phys)
Kernel executable memory footprint: 64KB
ebp:0x00007b38 eip:0x00100a55 args:0x00010094 0x00010094 0x00007b68 0x00100084 
    kern/debug/kdebug.c:305: print_stackframe+21
ebp:0x00007b48 eip:0x00100d3a args:0x00000000 0x00000000 0x00000000 0x00007bb8 
    kern/debug/kmonitor.c:125: mon_backtrace+10
ebp:0x00007b68 eip:0x00100084 args:0x00000000 0x00007b90 0xffff0000 0x00007b94 
    kern/init/init.c:48: grade_backtrace2+19
ebp:0x00007b88 eip:0x001000a5 args:0x00000000 0xffff0000 0x00007bb4 0x00000029 
    kern/init/init.c:53: grade_backtrace1+27
ebp:0x00007ba8 eip:0x001000c1 args:0x00000000 0x00100000 0xffff0000 0x00100043 
    kern/init/init.c:58: grade_backtrace0+19
ebp:0x00007bc8 eip:0x001000e1 args:0x00000000 0x00000000 0x00000000 0x00103480 
    kern/init/init.c:63: grade_backtrace+26
ebp:0x00007be8 eip:0x00100050 args:0x00000000 0x00000000 0x00000000 0x00007c4f 
    kern/init/init.c:28: kern_init+79
ebp:0x00007bf8 eip:0x00007d61 args:0xc031fcfa 0xc08ed88e 0x64e4d08e 0xfa7502a8 
    <unknow>: -- 0x00007d60 --
++ setup timer interrupts
0: @ring 0
0:  cs = 8
0:  ds = 10
0:  es = 10
0:  ss = 10
+++ switch to  user  mode +++
1: @ring 3
1:  cs = 1b
1:  ds = 23
1:  es = 23
1:  ss = 23
+++ switch to kernel mode +++
2: @ring 0
2:  cs = 8
2:  ds = 10
2:  es = 10
2:  ss = 10
100 ticks
100 ticks
100 ticks
100 ticks

练习1:理解通过make生成执行文件的过程

本练习任务是 通过 静态分析代码 来了解:

  • 操作系统镜像文件 ucore.img 是如何一步步生成的?(需要比较详细地解释Makefile中每一条相关命令和命令参数的含义,以及说明命令导致的结果)
  • 一个被系统认为是 符合规范的硬盘主引导扇区的特征 是什么?

补充材料:

当执行 make 时,一般只会显示普通输出,不会显示make到底执行了哪些命令。

如想了解make执行了哪些命令,可以执行:

make clean    //有时可能要先清除之前生成过的文件

make "V="

下图是执行结果,可以看到很多细节信息被展示了出来。

14

要获取更多有关 make 命令的信息,可以执行:

man make

也可上网查找相关资料,这里推荐一个工具网站 Linux 命令查询

15

问题一解答

题目:操作系统镜像文件ucore.img是如何一步步生成的?(需要比较详细地解释Makefile中每一条相关命令和命令参数的含义,以及说明命令导致的结果)

以下是 Lab 1 Makefile 的代码:

PROJ    := challenge
EMPTY    :=
SPACE    := $(EMPTY) $(EMPTY)
SLASH    := /

V       := @
#need llvm/cang-3.5+
#USELLVM := 1
# try to infer the correct GCCPREFX
ifndef GCCPREFIX
GCCPREFIX := $(shell if i386-elf-objdump -i 2>&1 | grep '^elf32-i386$$' >/dev/null 2>&1; \
    then echo 'i386-elf-'; \
    elif objdump -i 2>&1 | grep 'elf32-i386' >/dev/null 2>&1; \
    then echo ''; \
    else echo "***" 1>&2; \
    echo "*** Error: Couldn't find an i386-elf version of GCC/binutils." 1>&2; \
    echo "*** Is the directory with i386-elf-gcc in your PATH?" 1>&2; \
    echo "*** If your i386-elf toolchain is installed with a command" 1>&2; \
    echo "*** prefix other than 'i386-elf-', set your GCCPREFIX" 1>&2; \
    echo "*** environment variable to that prefix and run 'make' again." 1>&2; \
    echo "*** To turn off this error, run 'gmake GCCPREFIX= ...'." 1>&2; \
    echo "***" 1>&2; exit 1; fi)
endif

# try to infer the correct QEMU
ifndef QEMU
QEMU := $(shell if which qemu-system-i386 > /dev/null; \
    then echo 'qemu-system-i386'; exit; \
    elif which i386-elf-qemu > /dev/null; \
    then echo 'i386-elf-qemu'; exit; \
    elif which qemu > /dev/null; \
    then echo 'qemu'; exit; \
    else \
    echo "***" 1>&2; \
    echo "*** Error: Couldn't find a working QEMU executable." 1>&2; \
    echo "*** Is the directory containing the qemu binary in your PATH" 1>&2; \
    echo "***" 1>&2; exit 1; fi)
endif

# eliminate default suffix rules
.SUFFIXES: .c .S .h

# delete target files if there is an error (or make is interrupted)
.DELETE_ON_ERROR:

# define compiler and flags
ifndef  USELLVM
HOSTCC        := gcc
HOSTCFLAGS    := -g -Wall -O2
CC        := $(GCCPREFIX)gcc
CFLAGS    := -march=i686 -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc $(DEFS)
CFLAGS    += $(shell $(CC) -fno-stack-protector -E -x c /dev/null >/dev/null 2>&1 && echo -fno-stack-protector)
else
HOSTCC        := clang
HOSTCFLAGS    := -g -Wall -O2
CC        := clang
CFLAGS    := -march=i686 -fno-builtin -fno-PIC -Wall -g -m32 -nostdinc $(DEFS)
CFLAGS    += $(shell $(CC) -fno-stack-protector -E -x c /dev/null >/dev/null 2>&1 && echo -fno-stack-protector)
endif

CTYPE    := c S

LD      := $(GCCPREFIX)ld
LDFLAGS    := -m $(shell $(LD) -V | grep elf_i386 2>/dev/null | head -n 1)
LDFLAGS    += -nostdlib

OBJCOPY := $(GCCPREFIX)objcopy
OBJDUMP := $(GCCPREFIX)objdump

COPY    := cp
MKDIR   := mkdir -p
MV        := mv
RM        := rm -f
AWK        := awk
SED        := sed
SH        := sh
TR        := tr
TOUCH    := touch -c

OBJDIR    := obj
BINDIR    := bin

ALLOBJS    :=
ALLDEPS    :=
TARGETS    :=

include tools/function.mk

listf_cc = $(call listf,$(1),$(CTYPE))

# for cc
add_files_cc = $(call add_files,$(1),$(CC),$(CFLAGS) $(3),$(2),$(4))
create_target_cc = $(call create_target,$(1),$(2),$(3),$(CC),$(CFLAGS))

# for hostcc
add_files_host = $(call add_files,$(1),$(HOSTCC),$(HOSTCFLAGS),$(2),$(3))
create_target_host = $(call create_target,$(1),$(2),$(3),$(HOSTCC),$(HOSTCFLAGS))

cgtype = $(patsubst %.$(2),%.$(3),$(1))
objfile = $(call toobj,$(1))
asmfile = $(call cgtype,$(call toobj,$(1)),o,asm)
outfile = $(call cgtype,$(call toobj,$(1)),o,out)
symfile = $(call cgtype,$(call toobj,$(1)),o,sym)

# for match pattern
match = $(shell echo $(2) | $(AWK) '{for(i=1;i<=NF;i++){if(match("$(1)","^"$$(i)"$$")){exit 1;}}}'; echo $$?)

# >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
# include kernel/user

INCLUDE    += libs/

CFLAGS    += $(addprefix -I,$(INCLUDE))

LIBDIR    += libs

$(call add_files_cc,$(call listf_cc,$(LIBDIR)),libs,)

# -------------------------------------------------------------------
# kernel

KINCLUDE    += kern/debug/ \
               kern/driver/ \
               kern/trap/ \
               kern/mm/

KSRCDIR        += kern/init \
               kern/libs \
               kern/debug \
               kern/driver \
               kern/trap \
               kern/mm

KCFLAGS        += $(addprefix -I,$(KINCLUDE))

$(call add_files_cc,$(call listf_cc,$(KSRCDIR)),kernel,$(KCFLAGS))

KOBJS    = $(call read_packet,kernel libs)

# create kernel target
kernel = $(call totarget,kernel)

$(kernel): tools/kernel.ld

$(kernel): $(KOBJS)
    @echo + ld $@
    $(V)$(LD) $(LDFLAGS) -T tools/kernel.ld -o $@ $(KOBJS)
    @$(OBJDUMP) -S $@ > $(call asmfile,kernel)
    @$(OBJDUMP) -t $@ | $(SED) '1,/SYMBOL TABLE/d; s/ .* / /; /^$$/d' > $(call symfile,kernel)

$(call create_target,kernel)

# -------------------------------------------------------------------

# create bootblock
bootfiles = $(call listf_cc,boot)
$(foreach f,$(bootfiles),$(call cc_compile,$(f),$(CC),$(CFLAGS) -Os -nostdinc))

bootblock = $(call totarget,bootblock)

$(bootblock): $(call toobj,$(bootfiles)) | $(call totarget,sign)
    @echo + ld $@
    $(V)$(LD) $(LDFLAGS) -N -e start -Ttext 0x7C00 $^ -o $(call toobj,bootblock)
    @$(OBJDUMP) -S $(call objfile,bootblock) > $(call asmfile,bootblock)
    @$(OBJCOPY) -S -O binary $(call objfile,bootblock) $(call outfile,bootblock)
    @$(call totarget,sign) $(call outfile,bootblock) $(bootblock)

$(call create_target,bootblock)

# -------------------------------------------------------------------

# create 'sign' tools
$(call add_files_host,tools/sign.c,sign,sign)
$(call create_target_host,sign,sign)

# -------------------------------------------------------------------

# create ucore.img
UCOREIMG    := $(call totarget,ucore.img)

$(UCOREIMG): $(kernel) $(bootblock)
    $(V)dd if=/dev/zero of=$@ count=10000
    $(V)dd if=$(bootblock) of=$@ conv=notrunc
    $(V)dd if=$(kernel) of=$@ seek=1 conv=notrunc

$(call create_target,ucore.img)

# >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

$(call finish_all)

IGNORE_ALLDEPS    = clean \
                  dist-clean \
                  grade \
                  touch \
                  print-.+ \
                  handin

ifeq ($(call match,$(MAKECMDGOALS),$(IGNORE_ALLDEPS)),0)
-include $(ALLDEPS)
endif

# files for grade script

TARGETS: $(TARGETS)

.DEFAULT_GOAL := TARGETS

.PHONY: qemu qemu-nox debug debug-nox
qemu-mon: $(UCOREIMG)
    $(V)$(QEMU)  -no-reboot -monitor stdio -hda $< -serial null
qemu: $(UCOREIMG)
    $(V)$(QEMU) -no-reboot -parallel stdio -hda $< -serial null
log: $(UCOREIMG)
    $(V)$(QEMU) -no-reboot -d int,cpu_reset  -D q.log -parallel stdio -hda $< -serial null
qemu-nox: $(UCOREIMG)
    $(V)$(QEMU)   -no-reboot -serial mon:stdio -hda $< -nographic
TERMINAL        :=gnome-terminal
debug: $(UCOREIMG)
    $(V)$(QEMU) -S -s -parallel stdio -hda $< -serial null &
    $(V)sleep 2
    $(V)$(TERMINAL) -e "gdb -q -tui -x tools/gdbinit"
    
debug-nox: $(UCOREIMG)
    $(V)$(QEMU) -S -s -serial mon:stdio -hda $< -nographic &
    $(V)sleep 2
    $(V)$(TERMINAL) -e "gdb -q -x tools/gdbinit"

.PHONY: grade touch

GRADE_GDB_IN    := .gdb.in
GRADE_QEMU_OUT    := .qemu.out
HANDIN            := proj$(PROJ)-handin.tar.gz

TOUCH_FILES        := kern/trap/trap.c

MAKEOPTS        := --quiet --no-print-directory

grade:
    $(V)$(MAKE) $(MAKEOPTS) clean
    $(V)$(SH) tools/grade.sh

touch:
    $(V)$(foreach f,$(TOUCH_FILES),$(TOUCH) $(f))

print-%:
    @echo $($(shell echo $(patsubst print-%,%,$@) | $(TR) [a-z] [A-Z]))

.PHONY: clean dist-clean handin packall tags
clean:
    $(V)$(RM) $(GRADE_GDB_IN) $(GRADE_QEMU_OUT) cscope* tags
    -$(RM) -r $(OBJDIR) $(BINDIR)

dist-clean: clean
    -$(RM) $(HANDIN)

handin: packall
    @echo Please visit http://learn.tsinghua.edu.cn and upload $(HANDIN). Thanks!

packall: clean
    @$(RM) -f $(HANDIN)
    @tar -czf $(HANDIN) `find . -type f -o -type d | grep -v '^\.*$$' | grep -vF '$(HANDIN)'`

tags:
    @echo TAGS ALL
    $(V)rm -f cscope.files cscope.in.out cscope.out cscope.po.out tags
    $(V)find . -type f -name "*.[chS]" >cscope.files
    $(V)cscope -bq 
    $(V)ctags -L cscope.files

(如果想详细了解Makefile每行代码具体做了什么,可以参考这篇文章

Makefile 的默认目标在第 207 行被显式指定为 205 行的 TARGETS ,而 TARGETS 的依赖为 $(TARGETS) ,这个变量在 Makefile 是空的,但是会在 tools/function.mk 中的 do_create_target 宏中被修改, do_create_target 被函数 create_target 直接调用。因此在 Makefile 中只要调用了 create_target 就会为 $(TARGETS) 增添新的一项。

经过一系列的 create_target$(TARGETS) 最终值为: bin/kernel , bin/bootblock , bin/sign , bin/ucore.img

依赖图:

16

(参考了这篇文章

Makefile中关键的代码为:

# 编译生成bin/kernel所需的文件
$(call add_files_cc,$(call listf_cc,$(KSRCDIR)),kernel,$(KCFLAGS))

# 链接生成bin/kernel
kernel = $(call totarget,kernel)

$(kernel): tools/kernel.ld

$(kernel): $(KOBJS)
    @echo + ld $@
    $(V)$(LD) $(LDFLAGS) -T tools/kernel.ld -o $@ $(KOBJS)
    @$(OBJDUMP) -S $@ > $(call asmfile,kernel)
    @$(OBJDUMP) -t $@ | $(SED) '1,/SYMBOL TABLE/d; s/ .* / /; /^$$/d' > $(call symfile,kernel)
$(call create_target,kernel)

# 创建bootblock
bootfiles = $(call listf_cc,boot)
$(foreach f,$(bootfiles),$(call cc_compile,$(f),$(CC),$(CFLAGS) -Os -nostdinc))

bootblock = $(call totarget,bootblock)

$(bootblock): $(call toobj,$(bootfiles)) | $(call totarget,sign)
    @echo + ld $@
    $(V)$(LD) $(LDFLAGS) -N -e start -Ttext 0x7C00 $^ -o $(call toobj,bootblock)
    @$(OBJDUMP) -S $(call objfile,bootblock) > $(call asmfile,bootblock)
    @$(OBJCOPY) -S -O binary $(call objfile,bootblock) $(call outfile,bootblock)
    @$(call totarget,sign) $(call outfile,bootblock) $(bootblock)

$(call create_target,bootblock)

# 创建sign工具
$(call add_files_host,tools/sign.c,sign,sign)
$(call create_target_host,sign,sign)

# 创建ucore.img
UCOREIMG    := $(call totarget,ucore.img)

$(UCOREIMG): $(kernel) $(bootblock)
    $(V)dd if=/dev/zero of=$@ count=10000
    $(V)dd if=$(bootblock) of=$@ conv=notrunc
    $(V)dd if=$(kernel) of=$@ seek=1 conv=notrunc

$(call create_target,ucore.img)

由于之前在 Lab 0 的时候已经把 Lab 1 原始文件给 make 掉了,所以这里我在 labcodes_answer/lab1_result 目录下执行 make "V=" 指令以获取日志输出,以便于后续分析,得到日志如下(已加注释)

# 构建 kernel 内核文件
# 初始化相关
+ cc kern/init/init.c    
gcc -Ikern/init/ -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Ikern/debug/ -Ikern/driver/ -Ikern/trap/ -Ikern/mm/ -c kern/init/init.c -o obj/kern/init/init.o

# 标准IO
+ cc kern/libs/stdio.c    
gcc -Ikern/libs/ -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Ikern/debug/ -Ikern/driver/ -Ikern/trap/ -Ikern/mm/ -c kern/libs/stdio.c -o obj/kern/libs/stdio.o

# 读行
+ cc kern/libs/readline.c    
gcc -Ikern/libs/ -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Ikern/debug/ -Ikern/driver/ -Ikern/trap/ -Ikern/mm/ -c kern/libs/readline.c -o obj/kern/libs/readline.o

# 异常处理相关,便于在发现错误后,调用kernel monitor。
+ cc kern/debug/panic.c    
gcc -Ikern/debug/ -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Ikern/debug/ -Ikern/driver/ -Ikern/trap/ -Ikern/mm/ -c kern/debug/panic.c -o obj/kern/debug/panic.o
kern/debug/panic.c: In function ‘__panic’:
kern/debug/panic.c:27:5: warning: implicit declaration of function ‘print_stackframe’; did you mean ‘print_trapframe’?
-Wimplicit-function-declaration]
   27 |     print_stackframe();
      |     ^~~~~~~~~~~~~~~~
      |     print_trapframe
      
# 提供源码和二进制对应关系的查询功能,用于显示调用栈关系。
+ cc kern/debug/kdebug.c    
gcc -Ikern/debug/ -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Ikern/debug/ -Ikern/driver/ -Ikern/trap/ -Ikern/mm/ -c kern/debug/kdebug.c -o obj/kern/debug/kdebug.o

# 监视器相关,提供动态分析命令的kernel monitor,便于在ucore出现bug或问题之后,能够进入kernel monitor中,查看当前调用关系。
+ cc kern/debug/kmonitor.c    
gcc -Ikern/debug/ -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Ikern/debug/ -Ikern/driver/ -Ikern/trap/ -Ikern/mm/ -c kern/debug/kmonitor.c -o obj/kern/debug/kmonitor.o

# 时钟控制相关
+ cc kern/driver/clock.c    
gcc -Ikern/driver/ -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Ikern/debug/ -Ikern/driver/ -Ikern/trap/ -Ikern/mm/ -c kern/driver/clock.c -o obj/kern/driver/clock.o

# 实现了对串口和键盘的中断方式的处理操作。
+ cc kern/driver/console.c    
gcc -Ikern/driver/ -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Ikern/debug/ -Ikern/driver/ -Ikern/trap/ -Ikern/mm/ -c kern/driver/console.c -o obj/kern/driver/console.o

# 中断处理相关
+ cc kern/driver/picirq.c    
gcc -Ikern/driver/ -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Ikern/debug/ -Ikern/driver/ -Ikern/trap/ -Ikern/mm/ -c kern/driver/picirq.c -o obj/kern/driver/picirq.o

# 实现了通过设置CPU的Eflags来屏蔽和使能中断的函数。
+ cc kern/driver/intr.c    
gcc -Ikern/driver/ -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Ikern/debug/ -Ikern/driver/ -Ikern/trap/ -Ikern/mm/ -c kern/driver/intr.c -o obj/kern/driver/intr.o

# 紧接着第二步初步处理后,继续完成具体的各种中断处理操作。
+ cc kern/trap/trap.c    
gcc -Ikern/trap/ -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Ikern/debug/ -Ikern/driver/ -Ikern/trap/ -Ikern/mm/ -c kern/trap/trap.c -o obj/kern/trap/trap.o
kern/trap/trap.c: In function ‘print_trapframe’:
kern/trap/trap.c:109:16: warning: taking address of packed member of ‘struct trapframe’ may result in an unaligned pointer value [-Waddress-of-packed-member]
  109 |     print_regs(&tf->tf_regs);
      |                ^~~~~~~~~~~~
      
# 包括256个中断服务例程的入口地址和第一步初步处理时先。
+ cc kern/trap/vectors.S    
gcc -Ikern/trap/ -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Ikern/debug/ -Ikern/driver/ -Ikern/trap/ -Ikern/mm/ -c kern/trap/vectors.S -o obj/kern/trap/vectors.o

# 紧接着第一步初步处理后,进一步完成第二步初步处理;并且又恢复中断上下文的处理,即中断处理完毕后的返回准备操作。
+ cc kern/trap/trapentry.S    
gcc -Ikern/trap/ -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Ikern/debug/ -Ikern/driver/ -Ikern/trap/ -Ikern/mm/ -c kern/trap/trapentry.S -o obj/kern/trap/trapentry.o

# 设定ucore操作系统在段机制中要用到的全局变量:任务状态栏ts,全局描述符表gdt[],加载全局描述符表寄存器的函数lgdt,临时的内核栈stack(),以及对全局描述符表和任务状态段的初始化函数gdt_init。
+ cc kern/mm/pmm.c    
gcc -Ikern/mm/ -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Ikern/debug/ -Ikern/driver/ -Ikern/trap/ -Ikern/mm/ -c kern/mm/pmm.c -o obj/kern/mm/pmm.o

# 字符串相关
+ cc libs/string.c    
gcc -Ilibs/ -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/  -c libs/string.c -o obj/libs/string.o

# 格式化输出
+ cc libs/printfmt.c    
gcc -Ilibs/ -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/  -c libs/printfmt.c -o obj/libs/printfmt.o

# 建立链接
+ ld bin/kernel    
ld -m    elf_i386 -nostdlib -T tools/kernel.ld -o bin/kernel  obj/kern/init/init.o obj/kern/libs/stdio.o obj/kern/libs/readline.o obj/kern/debug/panic.o obj/kern/debug/kdebug.o obj/kern/debug/kmonitor.o obj/kern/driver/clock.o obj/kern/driver/console.o obj/kern/driver/picirq.o obj/kern/driver/intr.o obj/kern/trap/trap.o obj/kern/trap/vectors.o obj/kern/trap/trapentry.o obj/kern/mm/pmm.o  obj/libs/string.o obj/libs/printfmt.o

/*
-m 模拟指定的连接器elf_i386
-nostdlib 不使用标准库
-T 指定命令文件为tools/kernel.ld
-o 指定输出文件名字为kernel
*/

# 构建 bootblock
# 定义并实现bootloader最先执行的start函数,此函数进行了一定的初始化,完成了从实模式到保护模式的转换,并调用了bootmain.c中的bootmain函数。
+ cc boot/bootasm.S    
gcc -Iboot/ -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Os -nostdinc -c boot/bootasm.S -o obj/boot/bootasm.o

/*
-ggdb:生成可供gdb使用的调试信息。这样才能用qemu+gdb来调试bootloader或ucore
-m32:生成适用于32位环境的代码。我们用的模拟硬件是32位的80386,所以ucore也要是32位的软件
-gstabs:生成stabs格式的调试信息。ucore的monitor可以显示出便于开发者阅读的函数调用栈信息
-nostdinc:不使用标准库。标准库是给应用程序用的,我们是编译ucore内核,OS内核是提供服务的,所以所有的服务要自给自足。
-fno-stack-protector:不生成用于检测缓冲区溢出的代码。
-Os:为减小代码大小而进行优化。根据硬件spec,主引导扇区只有512字节,我们写的简单bootloader的最终大小不能大于510字节。
-I:添加搜索头文件的路径。
-Wall:产生尽可能多的警告信息。
-fno-builtin:除非用__builtin__前缀,否则不进行builtin函数的优化
*/


# 主程序,定义并实现了bootmain函数,实现了通过屏幕、串口和并口显示字符串,bootmain函数加载ucore操作系统到内存,然后跳到ucore的入口处执行。
+ cc boot/bootmain.c    
gcc -Iboot/ -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Os -nostdinc -c boot/bootmain.c -o obj/boot/bootmain.o

# 规范化工具,用于生成一个规范的硬盘主引导扇区。
+ cc tools/sign.c    

# 使用 gcc 将 sign.c 编译成可执行文件
gcc -Itools/ -g -Wall -O2 -c tools/sign.c -o obj/sign/tools/sign.o
gcc -g -Wall -O2 obj/sign/tools/sign.o -o bin/sign

# 使用 ld 命令链接 bootasm.o、bootmain.o 至 bootblock.out
+ ld bin/bootblock
ld -m    elf_i386 -nostdlib -N -e start -Ttext 0x7C00 obj/boot/bootasm.o obj/boot/bootmain.o -o obj/bootblock.o
'obj/bootblock.out' size: 500 bytes
build 512 bytes boot sector: 'bin/bootblock' success!

/*
-m:模拟指定的连接器为elf_i386
-N:指定读取/写入文本和数据段
-e:使用指定的符号start作为程序的初始执行点
-Ttext:使用指定的地址0x7C00作为文本段的起始点
-nonstdlib:不使用标准库
*/

# 构建 ucore.img
# 使用 dd 工具创建 ucore.img 空文件
dd if=/dev/zero of=bin/ucore.img count=10000
10000+0 records in
10000+0 records out
5120000 bytes (5.1 MB, 4.9 MiB) copied, 0.0445599 s, 115 MB/s

# 使用dd工具将bin/bootblock写入ucore.img, 参数conv=notrunc表示不截断输出文件
dd if=bin/bootblock of=bin/ucore.img conv=notrunc
1+0 records in
1+0 records out
512 bytes copied, 0.0001275 s, 4.0 MB/s

# 使用dd工具将bin/kernel写入ucore.img起始的1个block后,即bootblock后, 参数seek=1表示从输出文件开头跳过1个block开始写入
dd if=bin/kernel of=bin/ucore.img seek=1 conv=notrunc
154+1 records in
154+1 records out
78968 bytes (79 kB, 77 KiB) copied, 0.0009979 s, 79.1 MB/s

由以上输出可以分析出构建 ucore.img 时大致进行了以下操作:

  • 编译了若干内核文件,构建出内核 kernel
  • 生成 bootblock 引导程序

    • 编译 bootasm.S bootmain.c ,链接 obj/bootblock.o
    • 编译 sign.c 生成 sign.o 工具
    • 使用 sign.o 工具规范化 bootblock.o ,生成 bin/bootblock 引导扇区
  • 生成 ucore.img 虚拟磁盘

    • dd初始化一个大小为 5120000bytes 且内容为0的文件
    • dd拷贝 bin/bootblock 引导文件到 ucore.img 的第一个扇区
    • dd拷贝 bin/kernel 内核文件到 ucore.img 第二个扇区往后的空间

补充:dd命令的使用

17

问题二解答

题目:一个被系统认为是符合规范的硬盘主引导扇区的特征是什么?

通常我们将包含MBR(主引导记录)引导代码的扇区称为主引导扇区。通常由3部分组成:
主引导程序(MBR,占446字节)、磁盘分区表项(占4×16个字节,负责说明磁盘上的分区情况)、结束标志位(占2个字节,其值为 55 AA )。

上题中的sign.o工具可以规范化bootblock.o,生成bin/bootblock引导扇区,因此查看sign.c源代码进行分析,代码如下(已加注释)

#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <sys/stat.h>

int
main(int argc, char *argv[]) {
    struct stat st;
    
    // 命令参数检查
    if (argc != 3) {
        fprintf(stderr, "Usage: <input filename> <output filename>\n");
        return -1;
    }
    
    // 读取文件头
    if (stat(argv[1], &st) != 0) {
        fprintf(stderr, "Error opening file '%s': %s\n", argv[1], strerror(errno));
        return -1;
    }
    
    // 输出文件大小
    printf("'%s' size: %lld bytes\n", argv[1], (long long)st.st_size);
    
    // 文件大小检查,超过510字节则报错,因为最后2个字节要用作结束标志位
    if (st.st_size > 510) {
        fprintf(stderr, "%lld >> 510!!\n", (long long)st.st_size);
        return -1;
    }
    
    char buf[512];    // 定义缓冲区
    memset(buf, 0, sizeof(buf));    // 初始化为0
    FILE *ifp = fopen(argv[1], "rb");    // 读入源文件
    int size = fread(buf, 1, st.st_size, ifp);    // 获取文件大小
    
    // 文件大小检查
    if (size != st.st_size) {
        fprintf(stderr, "read '%s' error, size is %d.\n", argv[1], size);
        return -1;
    }
    fclose(ifp);    // 释放文件
    
    // 写入结束标志位
    buf[510] = 0x55;
    buf[511] = 0xAA;
    
    // 写入目标文件
    FILE *ofp = fopen(argv[2], "wb+");
    size = fwrite(buf, 1, 512, ofp);    
    
    // 文件大小检查
    if (size != 512) {
        fprintf(stderr, "write '%s' error, size is %d.\n", argv[2], size);
        return -1;
    }
    fclose(ofp);    // 释放文件
    
    // 正常返回
    printf("build 512 bytes boot sector: '%s' success!\n", argv[2]);
    return 0;
}

由上述代码分析可以得出 符合规范的硬盘主引导扇区的特征 为:

  • 总大小为 512 bytes
  • 内容不超过 510 bytes
  • 最后 2 bytes 0x55 0xAA

练习2:使用qemu执行并调试lab1中的软件

本练习任务:

  • 从CPU加电后执行的第一条指令开始,单步跟踪BIOS的执行。
  • 在初始化位置0x7c00设置实地址断点,测试断点正常。
  • 0x7c00开始跟踪代码运行,将单步跟踪反汇编得到的代码与bootasm.S和 bootblock.asm进行比较
  • 自己找一个bootloader或内核中的代码位置,设置断点并进行测试。

补充材料:

我们主要通过硬件模拟器qemu来进行各种实验。在实验的过程中我们可能会遇上各种各样的问题,调试是必要的。qemu支持使用gdb进行的强大而方便的调试。所以用好qemu和gdb是完成各种实验的基本要素。

默认的gdb需要进行一些额外的配置才进行qemu的调试任务。qemu和gdb之间使用网络端口1234进行通讯。在打开qemu进行模拟之后,运行gdb并输入:

target remote localhost:1234    // 或 target remote 127.0.0.1:1234

即可连接qemu,此时qemu会进入暂停状态,等待gdb的命令。这点我们在Lab 0已经了解过。

gdb的地址断点

在gdb命令行中,使用b *[地址]便可以在指定内存地址设置断点,当qemu中的cpu执行到指定地址时,便会将控制权交给gdb。

关于代码的反汇编

有可能gdb无法正确获取当前qemu执行的汇编指令,通过如下配置可以在每次gdb命令行前强制反汇编当前的指令,在gdb命令行或配置文件中添加:

define hook-stop
x/i $pc
end

gdb的单步命令

在gdb中,有next, nexti, step, stepi等指令来单步调试程序,它们功能各不相同,区别在于单步的跨度上。

next 单步到程序源代码的下一行,不进入函数。
nexti 单步一条机器指令,不进入函数。
step 单步到下一个不同的源代码行(包括进入函数)。
stepi 单步一条机器指令。

问题一解答

题目:从CPU加电后执行的第一条指令开始,单步跟踪BIOS的执行。

我们在Lab 0的时候已经配置好了gdbinit,现在可以直接使用。

lab1目录下执行make debug进行调试。(在此过程中如果遇到/bin/sh: 1: gnome-terminal: not found报错,执行sudo apt-get install gnome-terminal进行安装。)

正常执行如下图:

19

接下来首先执行continue开始调试,之后使用nextsi语句进行单步调试,最后使用x /2i $pc指令查看当前位置附近的两条汇编代码。

20

问题二解答

题目:在初始化位置0x7c00设置实地址断点,测试断点正常。

首先使用b *0x7c00指令在该地址处设下断点,然后使用c指令让程序执行至断点位置,最后使用x /5i $pc指令查看当前地址附近的5条汇编代码。如下图所示测试断点正常。

21

问题三解答

题目:从0x7c00开始跟踪代码运行,将单步跟踪反汇编得到的代码与bootasm.S和 bootblock.asm进行比较。

首先打开lab1/Makefile文件,找到如图所示位置并添加-d in_asm -D lab1_asm.log参数,这样后续我们进行调试时就可以自动将运行的汇编指令保存在lab1_asm.log 中,方便对比。

22

修改完成后继续执行make debug,之后我们会看到lab1目录下多了一个新文件lab1_asm.log,将其打开,之后打开boot/bootasm.S,再打开obj/bootblock.asm,将三者进行比较。

23

可以看到三者的汇编代码本质上是对应一致的

问题四解答

题目:自己找一个bootloader或内核中的代码位置,设置断点并进行测试。

这题自由度比较高,我就选择cons_init这个函数进行调试吧。

24

25

可以看到汇编代码内call的函数是和源代码所指示的一一对应的,这部分应该是常量初始化过程。

练习3:分析bootloader进入保护模式的过程

BIOS将通过读取硬盘主引导扇区到内存,并转跳到对应内存中的位置执行bootloader。请分析bootloader是如何完成从实模式进入保护模式的。

本练习任务:

  • 为何开启A20,以及如何开启A20
  • 如何初始化GDT表
  • 如何使能进入保护模式

提示:需要阅读小节保护模式和分段机制lab1/boot/bootasm.S源码。

问题一解答

题目:为何开启A20,以及如何开启A20?

建议先阅读附录A“关于A20 Gate”

  • 为何开启A20

    • i8086提供了20根地址线,但寄存器只有16位,因此 CPU 只能访问 1MB 以内的空间。CPU 想获取数据,需对 segment 左移 4 位,再加上 offest ,最终形成一个 20位 的地址:address = segment << 4 | offset
    • 但按这种方式计算出的地址的最大值为1088KB,超过20根地址线所能表示的范围(1MB=1024KB),会发生回卷(memory wraparound)(和整数溢出有点类似)。但下一代的基于i80286的计算机系统提供了24根地址线,当CPU计算出的地址超过1MB时不会发生回卷,这就造成了向下不兼容。为了保持完全的向下兼容性,IBM在计算机系统上加个硬件逻辑来模仿早期的回绕特征,而这就是A20 Gate,通过这个模块我们在实模式下将 第20位 的地址线限制为 0,这样 CPU 就无法访问超过 1MB 的空间了。
    • A20 Gate的方法是把A20地址线控制和键盘控制器的一个输出进行AND操作,这样来控制A20地址线的打开(使能)和关闭(屏蔽/禁止)。一开始时A20地址线控制是被屏蔽的(总为0),直到系统软件通过一定的IO操作去打开它。当A20地址线控制禁止时,则程序就像在i8086中运行,1MB以上的地址不可访问;保护模式下A20地址线控制打开,之后内存寻址将不会发生回卷,这时CPU可以充分使用32位4G内存的寻址能力(内存管理能力)
  • 如何开启A20

    • 在当前环境中,所用到的键盘控制器8042的IO端口只有0x600x64两个端口。8042通过这些端口给键盘控制器或键盘发送命令读取状态输出端口P2用于特定目的。位0(P20引脚)用于实现CPU复位操作,位1(P21引脚)用于控制A20信号线的开启与否。我们要操作的位置是输出端口P2的位1,写入方法为:向64h发送0xd1命令,表示我们想要修改端口P2;然后向60h发送想要写入的数据,这里是0xdf,实现端口P2的位1(即P21)置1。

    26

    • 当我们想要向8042输出端口进行写操作的时候,在键盘缓冲区中或许还有别的数据尚未处理,因此必须首先处理这些数据。
    • 激活A20地址线的流程为: 1.禁止中断;2.等待,直到8042 Input buffer为空为止; 3.发送Write 8042 Output Port命令到8042 Input buffer;4.等待,直到8042 Input buffer为空为止;5.向端口P2写入数据。

从程序角度分析,当从初始位置%cs=0 $pc=0x7c00进入后,首先清理环境(包括将flag置0和将段寄存器置0):

# start address should be 0:7c00, in real mode, the beginning address of the running bootloader
.globl start
start:
.code16                                             # Assemble for 16-bit mode
    cli                                             # Disable interrupts
    cld                                             # String operations increment

    # Set up the important data segment registers (DS, ES, SS).
    xorw %ax, %ax                                   # Segment number zero
    movw %ax, %ds                                   # -> Data Segment
    movw %ax, %es                                   # -> Extra Segment
    movw %ax, %ss                                   # -> Stack Segment

开启A20的汇编代码如下(已加注释)

    # Enable A20:
    #  For backwards compatibility with the earliest PCs, physical
    #  address line 20 is tied low, so that addresses higher than
    #  1MB wrap around to zero by default. This code undoes this.
seta20.1:
    # 读取0x64端口
    inb $0x64, %al                                  # Wait for not busy(8042 input buffer empty).
    testb $0x2, %al            # 读取到2则表明缓冲区中没有数据
    jnz seta20.1
    
    # 接下来往0x64写入0xd1,表示请求修改8042的端口P2
    movb $0xd1, %al                                 # 0xd1 -> port 0x64
    outb %al, $0x64                                 # 0xd1 means: write data to 8042's P2 port


seta20.2:
    # 接下来继续等待input buffer为空
    inb $0x64, %al                                  # Wait for not busy(8042 input buffer empty).
    testb $0x2, %al
    jnz seta20.2
    
    # 往0x60端口写入0xdf,表示将端口P2的位1(A20选通使能)置为1,开启A20
    movb $0xdf, %al                                 # 0xdf -> port 0x60
    outb %al, $0x60                                 # 0xdf = 11011111, means set P2's A20 bit(the 1 bit) to 1

至此,A20开启,CPU进入保护模式之后可以充分使用32位4G内存的寻址能力

问题二解答

题目:如何初始化GDT表

GDT(Global Descriptor Table, 全局描述表)。同实模式一样,在保护模式下,对内存的访问仍采用短地址加偏移地址的方式。其内存的管理方式有两种,段模式页模式。在保护模式下,对于一个段的描述包括:Base Address(基址),Limit(段的最大长度),Access(权限),这三个数据加在一起被放在一个 64 bit 的数据结构中,被称为段描述符。而由于寄存器为 16 bit,很明显,我们无法直接通过 16 bit 长度的寄存器来直接使用 64 bit 的段描述符。而对此的解决方案便是将这些段描述符放入一个全局数组中,将段寄存器中的值作为下标索引(段寄存器中的高 13 bit 的内容作为索引)来间接引用。而这个全局数组便是 GDT

GDT相关的汇编代码:

# Bootstrap GDT
.p2align 2                                          # force 4 byte alignment
gdt:
    SEG_NULLASM                                     # null seg
    SEG_ASM(STA_X|STA_R, 0x0, 0xffffffff)           # code seg for bootloader and kernel
    SEG_ASM(STA_W, 0x0, 0xffffffff)                 # data seg for bootloader and kernel

gdtdesc:
    .word 0x17                                      # sizeof(gdt) - 1
    .long gdt                                       # address gdt
  • SEG_NULLASM 设置表中第一项为NULL
  • SEG_ASM(STA_X|STA_R, 0x0, 0xffffffff)设置表中第二项为代码段描述符可读可执行
  • SEG_ASM(STA_W, 0x0, 0xffffffff)设置表中第三项为数据段描述符可写

问题三解答

题目:如何使能和进入保护模式

x86 引入了几个新的控制寄存器 (Control Registers) cr0 cr1cr7 ,每个长 32 位。这其中的某些寄存器的某些位被用来控制 CPU 的工作模式,其中 cr0 的最低位,就是用来控制 CPU 是否处于保护模式的。因为控制寄存器不能直接拿来运算,所以需要通过通用寄存器来进行一次存取,设置 cr0 最低位为 1 之后就已经进入保护模式。但是由于现代 CPU 的一些特性 (乱序执行和分支预测等),在转到保护模式之后 CPU 可能仍然在跑着实模式下的代码,这显然会造成一些问题。因此必须强制 CPU 清空一次缓冲,最有效的方法就是进行一次 long jump

以下是相关的汇编代码(已加注释)

    # Switch from real to protected mode, using a bootstrap GDT
    # and segment translation that makes virtual addresses
    # identical to physical addresses, so that the
    # effective memory map does not change during the switch.
    
    # 载入GDT
    lgdt gdtdesc    

    # 将cr0寄存器PE置1,开启保护模式
    movl %cr0, %eax
    orl $CR0_PE_ON, %eax
    movl %eax, %cr0

    # Jump to next instruction, but in 32-bit code segment.
    # Switches processor into 32-bit mode.

    # 通过长跳转更新cs的基地址
    ljmp $PROT_MODE_CSEG, $protcseg

# 设置段寄存器,建立堆栈 
.code32                                             # Assemble for 32-bit mode
protcseg:
    # Set up the protected-mode data segment registers
    movw $PROT_MODE_DSEG, %ax                       # Our data segment selector
    movw %ax, %ds                                   # -> DS: Data Segment
    movw %ax, %es                                   # -> ES: Extra Segment
    movw %ax, %fs                                   # -> FS
    movw %ax, %gs                                   # -> GS
    movw %ax, %ss                                   # -> SS: Stack Segment

    # Set up the stack pointer and call into C. The stack region is from 0--start(0x7c00)
    movl $0x0, %ebp
    movl $start, %esp

    # 转到保护模式完成,call进入bootmain
    call bootmain

    # If bootmain returns (it shouldn't), loop.
spin:
    jmp spin

bootloader实模式进入保护模式的过程:

  1. 在开启A20之后,加载了GDT全局描述符表,它是被静态储存在引导区中的,载入即可。接着,将cr0寄存器的bit 0置为1,标志着从实模式转换到保护模式
  2. 由于我们无法直接或间接 mov 一个数据到 cs 寄存器中,而刚刚开启保护模式时,cs 的影子寄存器还是实模式下的值,所以需要告诉 CPU 加载新的段信息。长跳转可以设置cs寄存器,CPU 发现了 cr0 寄存器第 0 位的值是 1,就会按 GDTR 的指示找到全局描述符表GDT,然后根据索引值 把新的段描述符信息加载到 cs 影子寄存器,当然前提是进行了一系列合法的检查。所以使用一个长跳转ljmp $PROT_MODE_CSEG, $protcseg以更新cs基地址,至此CPU真正进入了保护模式,拥有了 32 位的处理能力。
  3. 进入保护模式后,设置ds,es,fs,gs,ss段寄存器,建立堆栈(0~0x7c00),最后进入bootmain函数。

练习4:分析bootloader加载ELF格式的OS的过程。

通过阅读bootmain.c,了解bootloader如何加载ELF文件。通过分析源代码和通过qemu来运行并调试bootloader&OS。

本练习任务:

  • bootloader如何读取硬盘扇区的?
  • bootloader是如何加载ELF格式的OS

提示:可阅读小节硬盘访问概述ELF文件格式概述这两小节了解。

问题一解答

题目:bootloader如何读取硬盘扇区的?

当前硬盘数据是储存到硬盘扇区中的,一个扇区大小为512字节。读一个扇区的流程大致如下:

  1. 等待磁盘准备好
  2. 发出读取扇区的命令
  3. 等待磁盘准备好
  4. 把磁盘扇区数据读到指定内存

boot/bootmain.c中相关的代码为(已加注释)

/* waitdisk - wait for disk ready */
static void
waitdisk(void) {
    // 判断磁盘是否处于忙碌状态
    while ((inb(0x1F7) & 0xC0) != 0x40)
        /* do nothing */;
}

/* readsect - read a single sector at @secno into @dst */
static void
readsect(void *dst, uint32_t secno) {
    //等待磁盘准备好
    waitdisk();        
    
    // 设置磁盘参数
    outb(0x1F2, 1);          // 往0X1F2地址中写入要读取的扇区数,由于此处需要读一个扇区,因此参数为1
    
    // 0x1F3-0x1F6 设置LBA模式的参数
    outb(0x1F3, secno & 0xFF);                // 输入LBA参数的0-7位
    outb(0x1F4, (secno >> 8) & 0xFF);        // 输入LBA参数的8-15位
    outb(0x1F5, (secno >> 16) & 0xFF);        // 输入LBA参数的16-23位
    outb(0x1F6, ((secno >> 24) & 0xF) | 0xE0);    // 输入LBA参数的24-27位(对应到0-3位),第四位为0表示从主盘读取,其余位被强制置为1
    outb(0x1F7, 0x20);                      // 发出读取扇区的指令

    //等待磁盘准备好
    waitdisk();        

    // 从0x1F0端口处读数据,除以4是因为此处是以4个字节为单位的
    insl(0x1F0, dst, SECTSIZE / 4);    
}

各地址代表的寄存器意义如下:

  • 0x1F0 R,当0x1F7不为忙状态时可以读
  • 0x1F2 R/W,扇区数寄存器,记录操作的扇区数
  • 0x1F3 R/W,扇区号寄存器,记录操作的起始扇区号
  • 0x1F4 R/W,柱面号寄存器,记录柱面号的低 8 位
  • 0x1F5 R/W,柱面号寄存器,记录柱面号的高 8 位
  • 0x1F6 R/W,驱动器/磁头寄存器,记录操作的磁头号、驱动器号和寻道方式,前 4 位代表逻辑扇区号的高 4 位,DRV = 0/1 代表主/从驱动器,LBA = 0/1 代表 CHS/LBA 方式。
  • 0x1F7 R,状态寄存器,第 6、7 位分别代表驱动器准备好/驱动器忙
  • 0x1F8 W,命令寄存器,0x20 命令代表读取扇区

readseg封装了readsect,通过迭代使其可以读取任意长度的内容,代码如下:

/* *
 * readseg - read @count bytes at @offset from kernel into virtual address @va,
 * might copy more than asked.
 * */
static void
readseg(uintptr_t va, uint32_t count, uint32_t offset) {
    uintptr_t end_va = va + count;

    // round down to sector boundary
    va -= offset % SECTSIZE;

    // translate from bytes to sectors; kernel starts at sector 1
    uint32_t secno = (offset / SECTSIZE) + 1;

    // If this is too slow, we could read lots of sectors at a time.
    // We'd write more to memory than asked, but it doesn't matter --
    // we load in increasing order.
    for (; va < end_va; va += SECTSIZE, secno ++) {
        readsect((void *)va, secno);
    }
}

问题二解答

题目:bootloader是如何加载ELF格式的OS?

首先看elfhdrproghdr相关的信息,libs/elf.h代码如下(已加注释)

#ifndef __LIBS_ELF_H__
#define __LIBS_ELF_H__

#include <defs.h>

#define ELF_MAGIC    0x464C457FU            // 小端格式下"\x7FELF"

/* 文件头 */
struct elfhdr {
    uint32_t e_magic;     // 必须等于ELF_MAGIC魔数
    uint8_t e_elf[12];    // 12 字节,每字节对应意义如下:
    // 0 : 1 = 32 位程序;2 = 64 位程序
    // 1 : 数据编码方式,0 = 无效;1 = 小端模式;2 = 大端模式
    // 2 : 只是版本,固定为 0x1
    // 3 : 目标操作系统架构
    // 4 : 目标操作系统版本
    // 5 ~ 11 : 固定为 0

    uint16_t e_type;      // 1=可重定位, 2=可执行, 3=共享对象, 4=核心镜像
    uint16_t e_machine;   // 3=x86, 4=68K, etc.
    uint32_t e_version;   // 文件版本,总为1
    uint32_t e_entry;     // 程序入口地址(如果可执行)
    uint32_t e_phoff;     // 程序段表头相对elfhdr偏移位置
    uint32_t e_shoff;     // 节头表相对elfhdr偏移量
    uint32_t e_flags;     // 处理器特定标志,通常为0
    uint16_t e_ehsize;    // 这个ELF头的大小
    uint16_t e_phentsize; // 程序头部长度
    uint16_t e_phnum;     // 段个数
    uint16_t e_shentsize; // 节头部长度
    uint16_t e_shnum;     // 节头部个数
    uint16_t e_shstrndx;  // 节头部字符索引
};

/* 程序段表头 */
struct proghdr {
    uint32_t p_type;   // 段类型
    // 1 PT_LOAD : 可载入的段
    // 2 PT_DYNAMIC : 动态链接信息
    // 3 PT_INTERP : 指定要作为解释程序调用的以空字符结尾的路径名的位置和大小
    // 4 PT_NOTE : 指定辅助信息的位置和大小
    // 5 PT_SHLIB : 保留类型,但具有未指定的语义
    // 6 PT_PHDR : 指定程序头表在文件及程序内存映像中的位置和大小
    // 7 PT_TLS : 指定线程局部存储模板

    uint32_t p_offset; // 段相对文件头的偏移值
    uint32_t p_va;     // 段的第一个字节将被放到内存中的虚拟地址
    uint32_t p_pa;     //段的第一个字节在内存中的物理地址
    uint32_t p_filesz; //段在文件中的长度
    uint32_t p_memsz;  // 段在内存映像中占用的字节数
    uint32_t p_flags;  //可读可写可执行标志位。
    uint32_t p_align;   //段在文件及内存的对齐方式
};

#endif /* !__LIBS_ELF_H__ */

结合boot/bootmain.c代码分析如下(已加注释)

#define SECTSIZE        512
#define ELFHDR          ((struct elfhdr *)0x10000)

/* bootmain - the entry of bootloader */
void
bootmain(void) {
    // read the 1st page off disk
    readseg((uintptr_t)ELFHDR, SECTSIZE * 8, 0);    //bootloader先将ELF格式的OS加载到地址0x10000

    // is this a valid ELF?
    // 通过储存在头部的幻数判断读入的ELF文件是否合法
    if (ELFHDR->e_magic != ELF_MAGIC) {
        goto bad;
    }

    struct proghdr *ph, *eph;

    // load each program segment (ignores ph flags)
    // 按照描述表将ELF文件中数据载入内存,将ELF中每个段都加载到特定的地址
    // ELF文件0x1000位置后面的0xd1ec比特被载入内存0x00100000
    // ELF文件0xf000位置后面的0x1d20比特被载入内存0x0010e000
    ph = (struct proghdr *)((uintptr_t)ELFHDR + ELFHDR->e_phoff);
    eph = ph + ELFHDR->e_phnum;
    for (; ph < eph; ph ++) {
        readseg(ph->p_va & 0xFFFFFF, ph->p_memsz, ph->p_offset);
    }

    // call the entry point from the ELF header
    // note: does not return
    // 跳转至ELF文件的程序入口点
    ((void (*)(void))(ELFHDR->e_entry & 0xFFFFFF))();

bad:
    outw(0x8A00, 0x8A00);
    outw(0x8A00, 0x8E00);

    /* do nothing */
    while (1);
}

加载ELF格式的OS的大致流程为:

  • 读取ELF的头部
  • 判断ELF文件是否合法
  • 找到ELF有关内存位置的描述表
  • 按照这个描述表将数据载入内存
  • 根据ELF头部储存的入口信息找到内核的入口并跳转

练习5:实现函数调用堆栈跟踪函数 (需要编程)

我们需要在lab1中完成kdebug.c中函数print_stackframe的实现,可以通过函数print_stackframe来跟踪函数调用堆栈中记录的返回地址。在如果能够正确实现此函数,可在lab1中执行 make qemu后,在qemu模拟器中得到类似如下的输出:

……
ebp:0x00007b28 eip:0x00100992 args:0x00010094 0x00010094 0x00007b58 0x00100096
    kern/debug/kdebug.c:305: print_stackframe+22
ebp:0x00007b38 eip:0x00100c79 args:0x00000000 0x00000000 0x00000000 0x00007ba8
    kern/debug/kmonitor.c:125: mon_backtrace+10
ebp:0x00007b58 eip:0x00100096 args:0x00000000 0x00007b80 0xffff0000 0x00007b84
    kern/init/init.c:48: grade_backtrace2+33
ebp:0x00007b78 eip:0x001000bf args:0x00000000 0xffff0000 0x00007ba4 0x00000029
    kern/init/init.c:53: grade_backtrace1+38
ebp:0x00007b98 eip:0x001000dd args:0x00000000 0x00100000 0xffff0000 0x0000001d
    kern/init/init.c:58: grade_backtrace0+23
ebp:0x00007bb8 eip:0x00100102 args:0x0010353c 0x00103520 0x00001308 0x00000000
    kern/init/init.c:63: grade_backtrace+34
ebp:0x00007be8 eip:0x00100059 args:0x00000000 0x00000000 0x00000000 0x00007c53
    kern/init/init.c:28: kern_init+88
ebp:0x00007bf8 eip:0x00007d73 args:0xc031fcfa 0xc08ed88e 0x64e4d08e 0xfa7502a8
<unknow>: -- 0x00007d72 –
……

本练习任务:

请完成实验,看看输出是否与上述显示大致一致,并解释最后一行各个数值的含义。

要求完成函数kern/debug/kdebug.c::print_stackframe的实现,提交改进后源代码包(可以编译执行),并在实验报告中简要说明实现过程,并写出对上述问题的回答。

提示:可阅读小节函数堆栈,了解编译器是如何建立函数调用关系的。在完成lab1编译后,查看lab1/obj/bootblock.asm,了解bootloader源码与机器码的语句和地址等的对应关系;查看lab1/obj/kernel.asm,了解 ucore OS源码与机器码的语句和地址等的对应关系。

补充材料:

由于显示完整的栈结构需要解析内核文件中的调试符号,较为复杂和繁琐。代码中有一些辅助函数可以使用。例如可以通过调用print_debuginfo函数完成查找对应函数名并打印至屏幕的功能。具体可以参见kdebug.c代码中的注释。

问题解答

实现后的print_stackframe代码如下(已加注释)

/*
 |  栈底方向    | 高位地址
 |    ...      |
 |    ...      |
 |  参数3       |
 |  参数2       |
 |  参数1       |
 |  返回地址     |
 |  上一层[ebp]  | <-------- [ebp]
 |  局部变量     |  低位地址
*/

void print_stackframe(void)
{
    /* LAB1 YOUR CODE : STEP 1 */
    /* (1) call read_ebp() to get the value of ebp. the type is (uint32_t);
      * (2) call read_eip() to get the value of eip. the type is (uint32_t);
      * (3) from 0 .. STACKFRAME_DEPTH
      *    (3.1) printf value of ebp, eip
      *    (3.2) (uint32_t)calling arguments [0..4] = the contents in address (uint32_t)ebp +2 [0..4]
      *    (3.3) cprintf("\n");
      *    (3.4) call print_debuginfo(eip-1) to print the C calling function name and line number, etc.
      *    (3.5) popup a calling stackframe
      *           NOTICE: the calling funciton's return addr eip  = ss:[ebp+4]
      *                   the calling funciton's ebp = ss:[ebp]
      */
    
    //读入ebp,eip
    uint32_t ebp = read_ebp(), eip = read_eip();
    uint32_t *arguments;
    int i, j;
    
    //如果ebp非零并且没有达到规定的STACKFRAME_DEPTH的上限,则继续循环打印栈上栈帧和对应函数的信息
    for (i = 0; ebp != 0 && i < STACKFRAME_DEPTH; i++)
    {
        cprintf("ebp: 0x%08x eip:0x%08x args:", ebp, eip);
        arguments = (uint32_t *)ebp + 2;
        for (j = 0; j < 4; j++)
        {
            cprintf("0x%08x  ", arguments[j]);
        }
        cprintf("\n");
        
        // eip指向的是即将执行的指令,所以如果想要查看当前函数,需要减1。
        print_debuginfo(eip-1);
        
        // 将ebp和eip设置为上一个栈帧的ebp和eip
        // 注意要先设置eip后设置ebp,否则当ebp被修改后,eip就无法找到正确的ebp
        eip = *((uint32_t *)ebp + 1);
        ebp = *(uint32_t *)ebp;
    }
}

代码分析:先用read_ebpread_eip获得最初的ebpeip寄存器的值,根据注释中的要求输出结果规范,将ebpeip输出。参数的值在ebp+2这个地址,我们用变量arguments将其保存,并通过arguments[0..3]输出参数的值,用print_debuginfo输出当前函数信息,最后用ebp指针更新下一次循环时ebpeip的值。

需要注意的是:

  • 栈的方向是从高地址向低地址增长
  • 指针运算要小心,避免因为错误的运算顺序(例如先相加,再强制转换为指针类型)而导致指针的运算错误
  • 切换栈帧时,先切换eip,后切换ebp,两者顺序不能颠倒
  • 如果想与标准答案对比自己输出的信息是否正确,在labcodes_answer/lab1_result下运行make qemu即可

代码保存后在labcodes/lab1目录下执行make qemu,应该得到如下结果:

+ cc kern/debug/kdebug.c
+ ld bin/kernel
记录了10000+0 的读入
记录了10000+0 的写出
5120000字节(5.1 MB,4.9 MiB)已复制,0.0255234 s,201 MB/s
记录了1+0 的读入
记录了1+0 的写出
512字节已复制,0.000180683 s,2.8 MB/s
记录了153+1 的读入
记录了153+1 的写出
78784字节(79 kB,77 KiB)已复制,0.000332568 s,237 MB/s
WARNING: Image format was not specified for 'bin/ucore.img' and probing guessed raw.
         Automatically detecting the format is dangerous for raw images, write operations on block 0 will be restricted.
         Specify the 'raw' format explicitly to remove the restrictions.
(THU.CST) os is loading ...

Special kernel symbols:
  entry  0x00100000 (phys)
  etext  0x0010334f (phys)
  edata  0x0010fa16 (phys)
  end    0x00110d08 (phys)
Kernel executable memory footprint: 68KB
ebp: 0x00007b28 eip:0x001009a5 args:0x00010094  0x00010094  0x00007b58  0x0010008e  
    kern/debug/kdebug.c:306: print_stackframe+21
ebp: 0x00007b38 eip:0x00100c9c args:0x00000000  0x00000000  0x00000000  0x00007ba8  
    kern/debug/kmonitor.c:125: mon_backtrace+10
ebp: 0x00007b58 eip:0x0010008e args:0x00000000  0x00007b80  0xffff0000  0x00007b84  
    kern/init/init.c:48: grade_backtrace2+33
ebp: 0x00007b78 eip:0x001000bc args:0x00000000  0xffff0000  0x00007ba4  0x00000029  
    kern/init/init.c:53: grade_backtrace1+40
ebp: 0x00007b98 eip:0x001000dc args:0x00000000  0x00100000  0xffff0000  0x0000001d  
    kern/init/init.c:58: grade_backtrace0+23
ebp: 0x00007bb8 eip:0x00100104 args:0x0010337c  0x00103360  0x000012f2  0x00000000  
    kern/init/init.c:63: grade_backtrace+34
ebp: 0x00007be8 eip:0x00100051 args:0x00000000  0x00000000  0x00000000  0x00007c4f  
    kern/init/init.c:28: kern_init+80
ebp: 0x00007bf8 eip:0x00007d72 args:0xc031fcfa  0xc08ed88e  0x64e4d08e  0xfa7502a8  
    <unknow>: -- 0x00007d71 --
++ setup timer interrupts

最后一行的含义是:最初使用堆栈的那一个函数,即bootmain。 bootloader设置的堆栈从0x7c00开始,使用call bootmain进入bootmain函数。 call指令压栈,所以bootmainebp0x7bf8。后面的unknow之后的0x00007d71bootmain函数内调用 OS kernel 入口函数指令的地址eip则为0x00007d71的下一条地址,即0x00007d72。后面的args则表示传递给bootmain函数的参数,但是由于bootmain函数不需要任何参数,因此这些打印出来的数值并没有实际意义。

31

练习6:完善中断初始化和处理 (需要编程)

本练习任务是 完成编码工作和回答如下问题:

  • 中断描述符表(也可简称为保护模式下的中断向量表)中一个表项占多少字节?其中哪几位代表中断处理代码的入口
  • 请编程完善kern/trap/trap.c中对中断向量表进行初始化的函数idt_init。在idt_init函数中,依次对所有中断入口进行初始化。使用mmu.h中的SETGATE宏,填充idt数组内容。每个中断的入口由tools/vectors.c生成,使用trap.c中声明的vectors数组即可。
  • 请编程完善trap.c中的中断处理函数trap,在对时钟中断进行处理的部分填写trap函数中处理时钟中断的部分,使操作系统每遇到100次时钟中断后,调用print_ticks子程序,向屏幕上打印一行文字:100 ticks

要求完成问题2和问题3 提出的相关函数实现,提交改进后的源代码包(可以编译执行),并在实验报告中简要说明实现过程,并写出对问题1的回答。完成这问题2和3要求的部分代码后,运行整个系统,可以看到大约每1秒会输出一次 100 ticks,而按下的键也会在屏幕上显示。

提示:可阅读小节中断与异常了解。

注意:除了系统调用中断(T_SYSCALL)使用陷阱门描述符且权限为用户态权限以外,其它中断均使用特权级(DPL)为0的中断门描述符权限为内核态权限;而ucore的应用程序处于特权级3,需要采用int 0x80指令操作(这种方式称为软中断,软件中断,Tra中断,在lab5会碰到)来发出系统调用请求,并要能实现从特权级3到特权级0的转换,所以系统调用中断(T_SYSCALL)所对应的中断门描述符中的特权级(DPL)需要设置为3

问题一解答

题目:中断描述符表(也可简称为保护模式下的中断向量表)中一个表项占多少字节?其中哪几位代表中断处理代码的入口?

kern/mm/mmu.h中可以找到表项的结构代码如下:

/* Gate descriptors for interrupts and traps */
struct gatedesc {
    unsigned gd_off_15_0 : 16;        // low 16 bits of offset in segment
    unsigned gd_ss : 16;            // segment selector
    unsigned gd_args : 5;            // # args, 0 for interrupt/trap gates
    unsigned gd_rsv1 : 3;            // reserved(should be zero I guess)
    unsigned gd_type : 4;            // type(STS_{TG,IG32,TG32})
    unsigned gd_s : 1;                // must be 0 (system)
    unsigned gd_dpl : 2;            // descriptor(meaning new) privilege level
    unsigned gd_p : 1;                // Present
    unsigned gd_off_31_16 : 16;        // high bits of offset in segment
};

中断向量表一个表项的大小为16+16+5+3+4+1+2+1+16=8*8=64bit,即8字节。其中0-15位48-63位分别为偏移量的低16位和高16位,两者拼接得到段内偏移量16-31位gd_ss段选择器。根据段选择子段内偏移地址就可以得出中断处理程序的地址

问题二解答

题目:请编程完善kern/trap/trap.c中对中断向量表进行初始化的函数idt_init。在idt_init函数中,依次对所有中断入口进行初始化。使用mmu.h中的SETGATE宏,填充idt数组内容。每个中断的入口由tools/vectors.c生成,使用trap.c中声明的vectors数组即可。

实现后的idt_init代码如下(已加注释)

/* idt_init - initialize IDT to each of the entry points in kern/trap/vectors.S */
void idt_init(void)
{
    /* LAB1 YOUR CODE : STEP 2 */
    /* (1) Where are the entry addrs of each Interrupt Service Routine (ISR)?
      *     All ISR's entry addrs are stored in __vectors. where is uintptr_t __vectors[] ?
      *     __vectors[] is in kern/trap/vector.S which is produced by tools/vector.c
      *     (try "make" command in lab1, then you will find vector.S in kern/trap DIR)
      *     You can use  "extern uintptr_t __vectors[];" to define this extern variable which will be used later.
      * (2) Now you should setup the entries of ISR in Interrupt Description Table (IDT).
      *     Can you see idt[256] in this file? Yes, it's IDT! you can use SETGATE macro to setup each item of IDT
      * (3) After setup the contents of IDT, you will let CPU know where is the IDT by using 'lidt' instruction.
      *     You don't know the meaning of this instruction? just google it! and check the libs/x86.h to know more.
      *     Notice: the argument of lidt is idt_pd. try to find it!
      */
    
    extern uintptr_t __vectors[]; //声明中断入口,__vectors定义于vector.S中
    uint32_t i;
    for (i = 0; i < (sizeof(idt) / sizeof(struct gatedesc)); i++)
    {
      // 该idt项为内核代码,所以使用GD_KTEXT段选择子
      // 中断处理程序的入口地址存放于__vectors[i]
      // 特权级为DPL_KERNEL
        SETGATE(idt[i], 0, GD_KTEXT, __vectors[i], DPL_KERNEL); //为中断程序设置内核态权限
    }
    SETGATE(idt[T_SYSCALL], 0, GD_KTEXT, __vectors[T_SYSCALL], DPL_USER); //为T_SYSCALL设置用户态权限
    lidt(&idt_pd); //使用lidt指令加载中断描述符表
}

传入SETGATE的参数:

  • 第一个参数gate是中断描述符表
  • 第二个参数istrap用来判断是中断还是trap
  • 第三个参数sel的作用是进行段的选择
  • 第四个参数off表示偏移
  • 第五个参数dpl表示中断的优先级

代码分析:题目要求我们为每个中断设置权限,只有T_SYSCALL用户态权限(DPL_USER),其他都为内核态权限(DPL_KERNEL)。首先通过__vectors[]获得所有中断的入口,再通过循环为每个中断设置权限(默认为内核态权限),为T_SYSCALL设置用户态权限,最后通过lidt将IDT的起始地址装入IDTR寄存器即可。

问题三解答

题目:请编程完善trap.c中的中断处理函数trap,在对时钟中断进行处理的部分填写trap函数中处理时钟中断的部分,使操作系统每遇到100次时钟中断后,调用print_ticks子程序,向屏幕上打印一行文字:100 ticks。

由于所有中断最后都是统一在trap_dispatch中进行处理或者分配的,因此不妨考虑在该函数中对应处理时钟中断的部分,对全局变量ticks加1,并且当计数到达100时,调用print_ticks函数,从而完成每隔一段时间打印100 ticks的功能。

实现后的trap_dispatch代码如下(本练习仅添加了下方的第18-20行)

/* trap_dispatch - dispatch based on what type of trap occurred */
static void
trap_dispatch(struct trapframe *tf)
{
    char c;

    switch (tf->tf_trapno)
    {
    case IRQ_OFFSET + IRQ_TIMER:
        /* LAB1 YOUR CODE : STEP 3 */
        /* handle the timer interrupt */
        /* (1) After a timer interrupt, you should record this event using a global variable (increase it), such as ticks in kern/driver/clock.c
         * (2) Every TICK_NUM cycle, you can print some info using a funciton, such as print_ticks().
         * (3) Too Simple? Yes, I think so!
         */
        
        // 全局变量ticks定义于kern/driver/clock.c
        ticks++;
        if (ticks % TICK_NUM == 0)//每次时钟中断之后ticks就会加1,当加到TICK_NUM次数时,打印ticks并重新开始
            print_ticks();//打印ticks
        break;
    case IRQ_OFFSET + IRQ_COM1:
        c = cons_getc();
        cprintf("serial [%03d] %c\n", c, c);
        break;
    case IRQ_OFFSET + IRQ_KBD:
        c = cons_getc();
        cprintf("kbd [%03d] %c\n", c, c);
        break;
    //LAB1 CHALLENGE 1 : YOUR CODE you should modify below codes.
    case T_SWITCH_TOU:
    case T_SWITCH_TOK:
        panic("T_SWITCH_** ??\n");
        break;
    case IRQ_OFFSET + IRQ_IDE1:
    case IRQ_OFFSET + IRQ_IDE2:
        /* do nothing */
        break;
    default:
        // in kernel, it must be a mistake
        if ((tf->tf_cs & 3) == 0)
        {
            print_trapframe(tf);
            panic("unexpected trap in kernel.\n");
        }
    }
}

代码保存后在labcodes/lab1下运行make qemu应该大致得到如下结果:

32

Lab 1 完成

扩展练习 Challenge 1(需要编程)

本练习任务:

扩展proj4,增加syscall功能,即增加一用户态函数(可执行一特定系统调用:获得时钟计数值),当内核初始完毕后,可从内核态返回到用户态的函数,而用户态的函数又通过系统调用得到内核态的服务(通过网络查询所需信息,可找老师咨询。如果完成,且有兴趣做代替考试的实验,可找老师商量)。需写出详细的设计和分析报告。完成出色的可获得适当加分。

提示: 规范一下 challenge 的流程。

kern_init 调用 switch_test,该函数如下:

    static void
    switch_test(void) {
        print_cur_status();          // print 当前 cs/ss/ds 等寄存器状态
        cprintf("+++ switch to  user  mode +++\n");
        switch_to_user();            // switch to user mode
        print_cur_status();
        cprintf("+++ switch to kernel mode +++\n");
        switch_to_kernel();         // switch to kernel mode
        print_cur_status();
    }

switch_to 函数建议通过中断处理的方式实现。主要要完成的代码是在 trap 里面处理 T_SWITCH_TO 中断,并设置好返回的状态。

在 lab1 里面完成代码以后,执行 make grade 应该能够评测结果是否正确。

开摆。

扩展练习 Challenge 2(需要编程)

本练习任务:

用键盘实现用户模式内核模式切换。具体目标是:键盘输入3时切换到用户模式,键盘输入0时切换到内核模式。 基本思路是借鉴软中断(syscall功能)的代码,并且把trap.c中软中断处理的设置语句拿过来。

注意:

 1.关于调试工具,不建议用lab1_print_cur_status()来显示,要注意到寄存器的值要在中断完成后tranentry.S里面iret结束的时候才写回,所以再trap.c里面不好观察,建议用print_trapframe(tf)

 2.关于内联汇编,最开始调试的时候,参数容易出现错误,可能的错误代码如下:

   asm volatile ( "sub $0x8, %%esp \n"
     "int %0 \n"
     "movl %%ebp, %%esp"
     : )

要去掉参数int %0 \n这一行。

3.软中断是利用了临时栈来处理的,所以有压栈和出栈的汇编语句。硬件中断本身就在内核态了,直接处理就可以了。

开摆。

实验内容(理论部分) - 从机器启动到操作系统运行的过程

此处直接引用了实验指导书上的内容

BIOS启动过程

当计算机加电后,一般不直接执行操作系统,而是执行系统初始化软件完成基本IO初始化和引导加载功能。简单地说,系统初始化软件就是在操作系统内核运行之前运行的一段小软件。通过这段小软件,我们可以初始化硬件设备、建立系统的内存空间映射图,从而将系统的软硬件环境带到一个合适的状态,以便为最终调用操作系统内核准备好正确的环境。最终引导加载程序把操作系统内核映像加载到RAM中,并将系统控制权传递给它。

对于绝大多数计算机系统而言,操作系统和应用软件是存放在磁盘(硬盘/软盘)、光盘、EPROM、ROM、Flash等可在掉电后继续保存数据的存储介质上。计算机启动后,CPU一开始会到一个特定的地址开始执行指令,这个特定的地址存放了系统初始化软件,负责完成计算机基本的IO初始化,这是系统加电后运行的第一段软件代码。对于Intel 80386的体系结构而言,PC机中的系统初始化软件由BIOS (Basic Input Output System,即基本输入/输出系统,其本质是一个固化在主板Flash/CMOS上的软件)和位于软盘/硬盘引导扇区中的OS Boot Loader(在ucore中的bootasm.S和bootmain.c)一起组成。BIOS实际上是被固化在计算机ROM(只读存储器)芯片上的一个特殊的软件,为上层软件提供最底层的、最直接的硬件控制与支持。更形象地说,BIOS就是PC计算机硬件与上层软件程序之间的一个"桥梁",负责访问和控制硬件。

以Intel 80386为例,计算机加电后,CPU从物理地址0xFFFFFFF0(由初始化的CS:EIP确定,此时CS和IP的值分别是0xF000和0xFFF0)开始执行。在0xFFFFFFF0这里只是存放了一条跳转指令,通过跳转指令跳到BIOS例行程序起始点。BIOS做完计算机硬件自检和初始化后,会选择一个启动设备(例如软盘、硬盘、光盘等),并且读取该设备的第一扇区(即主引导扇区或启动扇区)到内存一个特定的地址0x7c00处,然后CPU控制权会转移到那个地址继续执行。至此BIOS的初始化工作做完了,进一步的工作交给了ucore的bootloader。

补充信息:

Intel的CPU具有很好的向后兼容性。在16位的8086 CPU时代,内存限制在1MB范围内,且BIOS的代码固化在EPROM中。在基于Intel的8086 CPU的PC机中的EPROM被编址在1MB内存地址空间的最高64KB中。PC加电后,CS寄存器初始化为0xF000,IP寄存器初始化为0xFFF0,所以CPU要执行的第一条指令的地址为CS:IP=0xF000:0XFFF0(Segment:Offset 表示)=0xFFFF0(Linear表示)。这个地址位于被固化EPROM中,指令是一个长跳转指令 JMP F000:E05B 。这样就开启了BIOS的执行过程。

到了32位的80386 CPU时代,内存空间扩大到了4G,多了段机制和页机制,但Intel依然很好地保证了80386向后兼容8086。地址空间的变化导致无法直接采用8086的启动约定。如果把BIOS启动固件编址在0xF000起始的64KB内存地址空间内,就会把整个物理内存地址空间隔离成不连续的两段,一段是0xF000以前的地址,一段是1MB以后的地址,这很不协调。为此,intel采用了一个折中的方案:默认将执行BIOS ROM编址在32位内存地址空间的最高端,即位于4GB地址的最后一个64KB内。在PC系统开机复位时,CPU进入实模式,并将CS寄存器设置成0xF000,将它的shadow register的Base值初始化设置为0xFFFF0000,EIP寄存器初始化设置为0x0000FFF0。所以机器执行的第一条指令的物理地址是0xFFFFFFF0。80386的BIOS代码也要和以前8086的BIOS代码兼容,故地址0xFFFFFFF0处的指令还是一条长跳转指令 jmp F000:E05B 。注意,这个长跳转指令会触发更新CS寄存器和它的shadow register,即执行 jmp F000 : E05B 后,CS将被更新成0xF000。表面上看CS其实没有变化,但CS的shadow register被更新为另外一个值了,它的Base域被更新成0x000F0000,此时形成的物理地址为Base+EIP=0x000FE05B,这就是CPU执行的第二条指令的地址。此时这条指令的地址已经是1M以内了,且此地址不再位于BIOS ROM中,而是位于RAM空间中。由于Intel设计了一种映射机制,将内存高端的BIOS ROM映射到1MB以内的RAM空间里,并且可以使这一段被映射的RAM空间具有与ROM类似的只读属性。所以PC机启动时将开启这种映射机制,让4GB地址空间的最高一个64KB的内容等同于1MB地址空间的最高一个64K的内容,从而使得执行了长跳转指令后,其实是回到了早期的8086 CPU初始化控制流,保证了向下兼容。

bootloader启动过程

BIOS将通过读取硬盘主引导扇区到内存,并转跳到对应内存中的位置执行bootloader。bootloader完成的工作包括:

  • 切换到保护模式,启用分段机制
  • 读磁盘中ELF执行文件格式的ucore操作系统到内存
  • 显示字符串信息
  • 把控制权交给ucore操作系统

对应其工作的实现文件在lab1中的boot目录下的三个文件asm.h、bootasm.S和bootmain.c。下面从原理上介绍完成上述工作的计算机系统硬件和软件背景知识。

保护模式和分段机制

此处内容过多,点击打开实验指导书查看。

地址空间

分段机制涉及5个关键内容:逻辑地址(Logical Address,应用程序员看到的地址,在操作系统原理上称为虚拟地址,以后提到虚拟地址就是指逻辑地址)、物理地址(Physical Address, 实际的物理内存地址)、段描述符表(包含多个段描述符的“数组”)、段描述符(描述段的属性,及段描述符表这个“数组”中的“数组元素”)、段选择子(即段寄存器中的值,用于定位段描述符表中段描述符表项的索引)

(1) 逻辑地址空间 从应用程序的角度看,逻辑地址空间就是应用程序员编程所用到的地址空间,比如下面的程序片段: int val=100; int * point=&val;

其中指针变量point中存储的即是一个逻辑地址。在基于80386的计算机系统中,逻辑地址有一个16位的段寄存器(也称段选择子,段选择子)和一个32位的偏移量构成。

(2) 物理地址空间 从操作系统的角度看,CPU、内存硬件(通常说的“内存条”)和各种外设是它主要管理的硬件资源而内存硬件和外设分布在物理地址空间中。物理地址空间就是一个“大数组”,CPU通过索引(物理地址)来访问这个“大数组”中的内容。物理地址是指CPU提交到内存总线上用于访问计算机内存和外设的最终地址。

物理地址空间的大小取决于CPU实现的物理地址位数,在基于80386的计算机系统中,CPU的物理地址空间为4GB,如果计算机系统实际上有1GB物理内存(即我们通常说的内存条),而其他硬件设备的IO寄存器映射到起始物理地址为3GB的256MB大小的地址空间,则该计算机系统的物理地址空间如下所示:

+------------------+  <- 0xFFFFFFFF (4GB)
|     无效空间      |
|                  |
+------------------+  <- addr:3G+256M
|     256MB        |
|   IO外设地址空间   |
|                  |
+------------------+  <- 0xC0000000(3GB)
|                  |
/\/\/\/\/\/\/\/\/\/\

/\/\/\/\/\/\/\/\/\/\
|     无效空间      |
+------------------+  <- 0x40000000(1GB)
|                  |
|    实际有效内存    |
|                  |
+------------------+  <- 0x00100000 (1MB)
|     BIOS ROM     |
+------------------+  <- 0x000F0000 (960KB)
|  16-bit devices, |
|  expansion ROMs  |
+------------------+  <- 0x000C0000 (768KB)
|   VGA Display    |
+------------------+  <- 0x000A0000 (640KB)
|                  |
|    Low Memory    |
|                  |
+------------------+  <- 0x00000000

(3) 线性地址空间 一台计算机只有一个物理地址空间,但在操作系统的管理下,每个程序都认为自己独占整个计算机的物理地址空间。为了让多个程序能够有效地相互隔离和使用物理地址空间,引入线性地址空间(也称虚拟地址空间)的概念。线性地址空间的大小取决于CPU实现的线性地址位数,在基于80386的计算机系统中,CPU的线性地址空间为4GB。线性地址空间会被映射到某一部分或整个物理地址空间,并通过索引(线性地址)来访问其中的内容。线性地址又称虚拟地址,是进行逻辑地址转换后形成的地址索引,用于寻址线性地址空间。但CPU未启动分页机制时,线性地址等于物理地址;当CPU启动分页机制时,线性地址还需经过分页地址转换形成物理地址后,CPU才能访问内存硬件和外设。三种地址的关系如下所示:

  • 启动分段机制,未启动分页机制:逻辑地址--> (分段地址转换) -->线性地址==物理地址
  • 启动分段和分页机制:逻辑地址--> (分段地址转换) -->线性地址-->(分页地址转换) -->物理地址

在操作系统的管理下,采用灵活的内存管理机制,在只有一个物理地址空间的情况下,可以存在多个线性地址空间。

硬盘访问概述

bootloader让CPU进入保护模式后,下一步的工作就是从硬盘上加载并运行OS。考虑到实现的简单性,bootloader的访问硬盘都是LBA模式的PIO(Program IO)方式,即所有的IO操作是通过CPU访问硬盘的IO地址寄存器完成。

一般主板有2个IDE通道,每个通道可以接2个IDE硬盘。访问第一个硬盘的扇区可设置IO地址寄存器0x1f0-0x1f7实现的,具体参数见下表。一般第一个IDE通道通过访问IO地址0x1f0-0x1f7来实现,第二个IDE通道通过访问0x170-0x17f实现。每个通道的主从盘的选择通过第6个IO偏移地址寄存器来设置。

表格:磁盘IO地址和对应功能

第6位:为1=LBA模式;0 = CHS模式 第7位和第5位必须为1

IO地址功能
0x1f0读数据,当0x1f7不为忙状态时,可以读。
0x1f2要读写的扇区数,每次读写前,你需要表明你要读写几个扇区。最小是1个扇区
0x1f3如果是LBA模式,就是LBA参数的0-7位
0x1f4如果是LBA模式,就是LBA参数的8-15位
0x1f5如果是LBA模式,就是LBA参数的16-23位
0x1f6第0~3位:如果是LBA模式就是24-27位 第4位:为0主盘;为1从盘
0x1f7状态和命令寄存器。操作时先给命令,再读取,如果不是忙状态就从0x1f0端口读数据

当前硬盘数据是储存到硬盘扇区中,一个扇区大小为512字节。读一个扇区的流程(可参看boot/bootmain.c中的readsect函数实现)大致如下:

  1. 等待磁盘准备好
  2. 发出读取扇区的命令
  3. 等待磁盘准备好
  4. 把磁盘扇区数据读到指定内存

ELF文件格式概述

ELF(Executable and linking format)文件格式是Linux系统下的一种常用目标文件(object file)格式,有三种主要类型:

  • 用于执行的可执行文件(executable file),用于提供程序的进程映像,加载的内存执行。 这也是本实验的OS文件类型。
  • 用于连接的可重定位文件(relocatable file),可与其它目标文件一起创建可执行文件和共享目标文件。
  • 共享目标文件(shared object file),连接器可将它与其它可重定位文件和共享目标文件连接成其它的目标文件,动态连接器又可将它与可执行文件和其它共享目标文件结合起来创建一个进程映像。

这里只分析与本实验相关的ELF可执行文件类型。ELF header在文件开始处描述了整个文件的组织。ELF的文件头包含整个执行文件的控制结构,其定义在elf.h中:

struct elfhdr {
  uint magic;  // must equal ELF_MAGIC
  uchar elf[12];
  ushort type;
  ushort machine;
  uint version;
  uint entry;  // 程序入口的虚拟地址
  uint phoff;  // program header 表的位置偏移
  uint shoff;
  uint flags;
  ushort ehsize;
  ushort phentsize;
  ushort phnum; //program header表中的入口数目
  ushort shentsize;
  ushort shnum;
  ushort shstrndx;
};

program header描述与程序执行直接相关的目标文件结构信息,用来在文件中定位各个段的映像,同时包含其他一些用来为程序创建进程映像所必需的信息。可执行文件的程序头部是一个program header结构的数组, 每个结构描述了一个段或者系统准备程序执行所必需的其它信息。目标文件的 “段” 包含一个或者多个 “节区”(section) ,也就是“段内容(Segment Contents)” 。程序头部仅对于可执行文件和共享目标文件有意义。可执行目标文件在ELF头部的e_phentsize和e_phnum成员中给出其自身程序头部的大小。程序头部的数据结构如下表所示:

struct proghdr {
  uint type;   // 段类型
  uint offset;  // 段相对文件头的偏移值
  uint va;     // 段的第一个字节将被放到内存中的虚拟地址
  uint pa;
  uint filesz;
  uint memsz;  // 段在内存映像中占用的字节数
  uint flags;
  uint align;
};

根据elfhdr和proghdr的结构描述,bootloader就可以完成对ELF格式的ucore操作系统的加载过程(参见boot/bootmain.c中的bootmain函数)。

补充材料

Link addr & Load addr

Link Address是指编译器指定代码和数据所需要放置的内存地址,由链接器配置。Load Address是指程序被实际加载到内存的位置(由程序加载器ld配置)。一般由可执行文件结构信息和加载器可保证这两个地址相同。Link Addr和LoadAddr不同会导致:

  • 直接跳转位置错误
  • 直接内存访问(只读数据区或bss等直接地址访问)错误
  • 堆和栈等的使用不受影响,但是可能会覆盖程序、数据区域 注意:也存在Link地址和Load地址不一样的情况(例如:动态链接库)。

操作系统启动过程

当bootloader通过读取硬盘扇区把ucore在系统加载到内存后,就转跳到ucore操作系统在内存中的入口位置(kern/init.c中的kern_init函数的起始地址),这样ucore就接管了整个控制权。当前的ucore功能很简单,只完成基本的内存管理和外设中断管理。ucore主要完成的工作包括:

  • 初始化终端;
  • 显示字符串;
  • 显示堆栈中的多层函数调用关系;
  • 切换到保护模式,启用分段机制;
  • 初始化中断控制器,设置中断描述符表,初始化时钟中断,使能整个系统的中断机制;
  • 执行while(1)死循环。

以后的实验中会大量涉及各个函数直接的调用关系,以及由于中断处理导致的异步现象,可能对大家实现操作系统和改正其中的错误有很大影响。而理解好函数调用关系的建立机制和中断处理机制,对后续实验会有很大帮助。下面就练习5涉及的函数栈调用关系和练习6中的中断机制的建立进行阐述。

函数堆栈

栈是一个很重要的编程概念(编译课和程序设计课都讲过相关内容),与编译器和编程语言有紧密的联系。理解调用栈最重要的两点是:栈的结构,EBP寄存器的作用。一个函数调用动作可分解为:零到多个PUSH指令(用于参数入栈),一个CALL指令。CALL指令内部其实还暗含了一个将返回地址(即CALL指令下一条指令的地址)压栈的动作(由硬件完成)。几乎所有本地编译器都会在每个函数体之前插入类似如下的汇编指令:

pushl   %ebp
movl   %esp , %ebp

这样在程序执行到一个函数的实际指令前,已经有以下数据顺序入栈:参数、返回地址、ebp寄存器。由此得到类似如下的栈结构(参数入栈顺序跟调用方式有关,这里以C语言默认的CDECL为例):

+|  栈底方向        | 高位地址
 |    ...        |
 |    ...        |
 |  参数3        |
 |  参数2        |
 |  参数1        |
 |  返回地址        |
 |  上一层[ebp]    | <-------- [ebp]
 |  局部变量        |  低位地址

这两条汇编指令的含义是:首先将ebp寄存器入栈,然后将栈顶指针esp赋值给ebp。“mov ebp esp”这条指令表面上看是用esp覆盖ebp原来的值,其实不然。因为给ebp赋值之前,原ebp值已经被压栈(位于栈顶),而新的ebp又恰恰指向栈顶。此时ebp寄存器就已经处于一个非常重要的地位,该寄存器中存储着栈中的一个地址(原ebp入栈后的栈顶),从该地址为基准,向上(栈底方向)能获取返回地址、参数值,向下(栈顶方向)能获取函数局部变量值,而该地址处又存储着上一层函数调用时的ebp值。

一般而言,ss:[ebp+4]处为返回地址,ss:[ebp+8]处为第一个参数值(最后一个入栈的参数值,此处假设其占用4字节内存),ss:[ebp-4]处为第一个局部变量,ss:[ebp]处为上一层ebp值。由于ebp中的地址处总是“上一层函数调用时的ebp值”,而在每一层函数调用中,都能通过当时的ebp值“向上(栈底方向)”能获取返回地址、参数值,“向下(栈顶方向)”能获取函数局部变量值。如此形成递归,直至到达栈底。这就是函数调用栈。

中断与异常

此处内容过多,点击打开实验指导书查看。

lab1中对中断的处理实现

此处内容过多,点击打开实验指导书查看。

Lab 2 物理内存管理

实验目的

  • 理解基于段页式内存地址的转换机制
  • 理解页表的建立和使用方法
  • 理解物理内存的管理方法

实验内容(操作部分)

本次实验包含三个部分。首先了解如何发现系统中的物理内存;然后了解如何建立对物理内存的初步管理,即了解连续物理内存管理;最后了解页表相关的操作,即如何建立页表来实现虚拟内存到物理内存之间的映射,对段页式内存管理机制有一个比较全面的了解。本实验里面实现的内存管理还是非常基本的,并没有涉及到对实际机器的优化,比如针对 cache 的优化等。如果大家有余力,尝试完成扩展练习。在实验前请先阅读实验执行流程概述

项目组成

Lab2文件列表:

bash
|-- boot
| |-- asm.h
| |-- bootasm.S
| \`-- bootmain.c
|-- kern
| |-- init
| | |-- entry.S
| | \`-- init.c
| |-- mm
| | |-- default\_pmm.c
| | |-- default\_pmm.h
| | |-- memlayout.h
| | |-- mmu.h
| | |-- pmm.c
| | \`-- pmm.h
| |-- sync
| | \`-- sync.h
| \`-- trap
| |-- trap.c
| |-- trapentry.S
| |-- trap.h
| \`-- vectors.S
|-- libs
| |-- atomic.h
| |-- list.h
\`-- tools
|-- kernel.ld

相对与实验一,实验二主要增加和修改的文件如上表所示。主要改动如下:

  • boot/bootasm.S:增加了对计算机系统中物理内存布局的探测功能
  • kern/init/entry.S:根据临时段表重新暂时建立好新的段空间,为进行分页做好准备
  • kern/mm/default_pmm.[ch]:提供基本的基于链表方法的物理内存管理(分配单位为页,即4096字节)
  • kern/mm/pmm.[ch]:pmm.h定义物理内存管理类框架struct pmm_manager,基于此通用框架可以实现不同的物理内存管理策略和算法(default_pmm.[ch] 实现了一个基于此框架的简单物理内存管理策略); pmm.c包含了对此物理内存管理类框架的访问,以及与建立、修改、访问页表相关的各种函数实现
  • kern/sync/sync.h:为确保内存管理修改相关数据时不被中断打断,提供两个功能,一个是保存eflag寄存器中的中断屏蔽位信息并屏蔽中断的功能,另一个是根据保存的中断屏蔽位信息来使能中断的功能
  • libs/list.h:定义了通用双向链表结构以及相关的查找、插入等基本操作,这是建立基于链表方法的物理内存管理(以及其他内核功能)的基础。其他有类似双向链表需求的内核功能模块可直接使用list.h中定义的函数
  • libs/atomic.h:定义了对一个变量进行读写的原子操作,确保相关操作不被中断打断
  • tools/kernel.ld:ld形成执行文件的地址所用到的链接脚本。修改了ucore的起始入口和代码段的起始地址。相关细节可参看附录C

编译方法

当完成实验后,在lab2目录下执行make qemu,可以得到如下显示界面(仅供参考):

chenyu$ make qemu
(THU.CST) os is loading ...

Special kernel symbols:
  entry  0xc010002c (phys)
  etext  0xc010537f (phys)
  edata  0xc01169b8 (phys)
  end    0xc01178dc (phys)
Kernel executable memory footprint: 95KB
memory managment: default_pmm_manager
e820map:
  memory: 0009f400, [00000000, 0009f3ff], type = 1.
  memory: 00000c00, [0009f400, 0009ffff], type = 2.
  memory: 00010000, [000f0000, 000fffff], type = 2.
  memory: 07efd000, [00100000, 07ffcfff], type = 1.
  memory: 00003000, [07ffd000, 07ffffff], type = 2.
  memory: 00040000, [fffc0000, ffffffff], type = 2.
check_alloc_page() succeeded!
check_pgdir() succeeded!
check_boot_pgdir() succeeded!
-------------------- BEGIN --------------------
PDE(0e0) c0000000-f8000000 38000000 urw
  |-- PTE(38000) c0000000-f8000000 38000000 -rw
PDE(001) fac00000-fb000000 00400000 -rw
  |-- PTE(000e0) faf00000-fafe0000 000e0000 urw
  |-- PTE(00001) fafeb000-fafec000 00001000 -rw
--------------------- END ---------------------
++ setup timer interrupts
100 ticks
100 ticks
……

通过上图,我们可以看到ucore在显示其entry(入口地址)etext(代码段截止处地址)edata(数据段截止处地址)end(ucore截止处地址)的值后,探测出计算机系统中的物理内存的布局(e820map下的显示内容)。接下来ucore会以页为最小分配单位实现一个简单的内存分配管理,完成二级页表的建立,进入分页模式,执行我们设置的各种检查,最后显示ucore建立好的二级页表内容,并在分页模式下响应时钟中断

练习0:填写已有实验

本练习任务:

本实验依赖实验1。请把你做的实验1的代码填入本实验中代码中有“LAB1”的注释相应部分。

提示:可采用diff和patch工具进行半自动的合并(merge),也可用一些图形化的比较/merge工具来手动合并,比如meld,eclipse中的diff/merge工具,understand中的diff/merge工具等。

问题解答

这次要合并的部分比较少,为了避免使用工具导致的不知名错误,这次还是建议手动合并,之前试了下diffpatch,感觉不太好用,乱七八糟的。下次的合并再使用工具。

lab1中修改过的文件有:

  • kern/debug/kdebug.c
  • kern/trap/trap.c
  • kern/init/init.c(扩展题)

找到我们之前修改过的部分,复制粘贴代码到lab2对应的位置即可。

练习1:实现 first-fit 连续物理内存分配算法(需要编程)

本练习任务:

实现 first-fit 连续物理内存分配算法,在实现 first-fit 内存分配算法的回收函数时,要考虑地址连续的空闲块之间的合并操作。请在实验报告中简要说明你的设计实现过程并回答问题:你的first-fit算法是否有进一步的改进空间?

提示:在建立空闲页块链表时,需要按照空闲页块起始地址来排序,形成一个有序的链表。可能会修改default_pmm.c中的default_initdefault_init_memmapdefault_alloc_pagesdefault_free_pages等相关函数。请仔细查看和理解default_pmm.c中的注释。

问题解答

default_pmm.c代码中几乎已经实现了first-fit算法,但其中仍然存在一个问题,以至于无法通过检查。因为first-fit算法要求将空闲内存块按照地址从小到大的方式连接起来。但现成的代码还没有实现这一点,所以我们要手动修改相关的代码。

kern/mm/default_pmm.c进行下述修改:

  • default_init函数的一些解释:

    static void
    default_init(void)
    {
        list_init(&free_list);
        nr_free = 0;
    }
    • 这是一个初始化函数,free_list用来维护所有空闲的内存块,是一个双向链表,在最开始时它的prevnext都指向自身。nr_free记录了free_list中空闲page的数目。
  • 对于default_init_memmap函数:

    • 这个函数用来对块中的每个page进行初始化,并将block加入到free_list中。
    • (原先的错误代码)该函数将新页插入链表时,没有按照地址顺序插入(因为list_add是插入到free_list的后边,等价于list_add_after):

      list_add(&free_list, &(base->page_link));
    • (修改的代码)通过list_add_before使其按地址顺序插入双向链表中。这里有点抽象,因为before是相对于free_list而言的,每一次都插入到free_list的前面,本质上是插入到上一个块的后面,所以这样插入才会使得地址从小到大排序,需要自行理解一下。

      list_add_before(&free_list, &(base->page_link));
    • 修改后的整个函数代码如下:

      static void
      default_init_memmap(struct Page *base, size_t n)
      {
          assert(n > 0);
          struct Page *p = base;
          for (; p != base + n; p++)
          {
              assert(PageReserved(p));
              p->flags = p->property = 0;
              set_page_ref(p, 0);//清空引用数
          }
          base->property = n;
          SetPageProperty(base);
          nr_free += n;
          list_add_before(&free_list, &(base->page_link));
      }
  • 对于default_alloc_pages函数:

    • 这个函数用来申请指定数目的空闲page。当n大于nr_free时,free_list不能满足需求,返回NULL。若数量足够分配,则遍历free_list,查看每一个page_header,其property记录了该链表中page的数目,找到第一个合适的并将其返回。如果找到了这样的block,则将其进行切割(如果必要的话),将剩余的空间再加入到链表中。(连续空闲页表中的第一个页称为页头
    • (原先的错误代码)在将剩余空间放回链表时,没有按照地址顺序插入链表。

      if (page != NULL) {
          list_del(&(page->page_link));
          if (page->property > n) {
              struct Page *p = page + n;
              p->property = page->property - n;
              list_add(&free_list, &(p->page_link));
          }
          nr_free -= n;
          ClearPageProperty(page);
      }
    • (修改的代码)在第4行后插入SetPageProperty(p);,对切割后产生的block设置property使能;将原先的list_add(&free_list, &(p->page_link));改为list_add_after(&(page->page_link), &(p->page_link));,使用&(page->page_link)作为第一个参数,是因为要借助原先的页头作为中间人来完成链表的衔接,将剩余块插入后,在if结束后添加list_del(&(page->page_link));来删除原先页头(至此它的使命完成),至此剩余块插回链表完成。

      if (page != NULL) {
          if (page->property > n) {
              struct Page *p = page + n;
              p->property = page->property - n;
              SetPageProperty(p);
              list_add_after(&(page->page_link), &(p->page_link));
          }
          list_del(&(page->page_link));
          nr_free -= n;
          ClearPageProperty(page);
      }
    • 修改后的整个函数代码如下:

      static struct Page *
      default_alloc_pages(size_t n)
      {
          assert(n > 0);
          if (n > nr_free)
          {
              return NULL;
          }
          struct Page *page = NULL;
          list_entry_t *le = &free_list;
          while ((le = list_next(le)) != &free_list)//依次往下寻找直到回到头指针处,即已经遍历一次
          {
              struct Page *p = le2page(le, page_link);//将地址转换成页的结构
              if (p->property >= n)//由于是first-fit,则遇到的第一个大于N的块就选中即可
              {
                  page = p;
                  break;
              }
          }
          if (page != NULL)
          {
              if (page->property > n)
              {
                  struct Page *p = page + n;
                  p->property = page->property - n;
                  SetPageProperty(p);
                  list_add_after(&(page->page_link), &(p->page_link));
              }
              list_del(&(page->page_link));
              nr_free -= n;
              ClearPageProperty(page);
          }
          return page;
      }
  • 对于default_free_pages函数:

    • 这个函数把被freeblock重新加入到free_list中,并做了相应的合并操作。
    • (原先的错误代码)合并后的block被错误地加入到了链表头部(因为list_add是插入到free_list的后边,等价于list_add_aftter)。

      nr_free += n;
      list_add(&free_list, &(base->page_link));
    • (修改的代码)在两行之间添加一个for循环,用于找到合适的地址位置,将合并出来的空闲块插入空闲链表的这个位置中。举例来说,假设当前我有一个地址为0x80的块要插入到链表中,但链表现在存的块的地址有0x1、0x15、0x60、0x100,那么这个for循环的作用就是找到0x600x100之间的这个位置,便于将合并出来的空闲块插入到这里来,实现地址的顺序从小到大。至于第6行处的小于等于,是为了避免即将加入地址已经存在于链表中这种情况。

      nr_free += n;
      le = &free_list;
      while ((le = list_next(le)) != &free_list)
      {
          p = le2page(le, page_link);
          if (base + base->property <= p) {
              assert(base + base->property != p);
              break;
          }
      }
      list_add_before(le, &(base->page_link));
    • 修改后的整个函数代码如下:

      static void
      default_free_pages(struct Page *base, size_t n)
      {
          assert(n > 0);
          struct Page *p = base;
          for (; p != base + n; p++)
          {
              assert(!PageReserved(p) && !PageProperty(p));
              p->flags = 0;
              set_page_ref(p, 0);
          }
          base->property = n;
          SetPageProperty(base);
          list_entry_t *le = list_next(&free_list);
          while (le != &free_list)
          {
              p = le2page(le, page_link);
              le = list_next(le);
              if (base + base->property == p)
              {
                  base->property += p->property;
                  ClearPageProperty(p);
                  list_del(&(p->page_link));
              }
              else if (p + p->property == base)
              {
                  p->property += base->property;
                  ClearPageProperty(base);
                  base = p;
                  list_del(&(p->page_link));
              }
          }
          nr_free += n;
          le = &free_list;
          while ((le = list_next(le)) != &free_list)
          {
              p = le2page(le, page_link);
              if (base + base->property < p)
              {
                  assert(base + base->property != p);
                  break;
              }
          }
          list_add_before(le, &(base->page_link));
      }
      
  • 你的first-fit算法是否有进一步的改进空间?

    • 应该是有更好的解决方法的,但我对其的理解还没有深入到能够找到更好的改进方法的程度,因此我目前所写的代码就是我能理解范围内的最优情况了。

练习2:实现寻找虚拟地址对应的页表项(需要编程)

通过设置页表和对应的页表项,可建立虚拟内存地址物理内存地址的对应关系。其中的get_pte函数是设置页表项环节中的一个重要步骤。此函数找到一个虚地址对应的二级页表项的内核虚地址,如果此二级页表项不存在,则分配一个包含此项的二级页表。

本练习任务:

补全get_pte函数(在kern/mm/pmm.c中),实现其功能。请在实验报告中简要说明你的设计实现过程并回答如下问题:

  • 请描述页目录项(Page Directory Entry)页表项(Page Table Entry)中每个组成部分的含义以及对ucore而言的潜在用处
  • 如果ucore执行过程中访问内存,出现了页访问异常,请问硬件要做哪些事情?

提示:请仔细查看和理解get_pte函数中的注释。get_pte函数的调用关系图如下所示:

35

问题解答

问题一:通过设置页表和对应的页表项,可建立虚拟内存地址和物理内存地址的对应关系。其中的get_pte函数是设置页表项环节中的一个重要步骤。此函数找到一个虚地址对应的二级页表项的内核虚地址,如果此二级页表项不存在,则分配一个包含此项的二级页表。补全get_pte函数(在kern/mm/pmm.c中),实现其功能。

答:

实现后的get_pte函数的代码(已加注释):

pte_t *
get_pte(pde_t *pgdir, uintptr_t la, bool create)
{
    /* LAB2 EXERCISE 2: YOUR CODE
     *
     * If you need to visit a physical address, please use KADDR()
     * please read pmm.h for useful macros
     *
     * Maybe you want help comment, BELOW comments can help you finish the code
     *
     * Some Useful MACROs and DEFINEs, you can use them in below implementation.
     * MACROs or Functions:
     *   PDX(la) = the index of page directory entry of VIRTUAL ADDRESS la.
     *   KADDR(pa) : takes a physical address and returns the corresponding kernel virtual address.
     *   set_page_ref(page,1) : means the page be referenced by one time
     *   page2pa(page): get the physical address of memory which this (struct Page *) page  manages
     *   struct Page * alloc_page() : allocation a page
     *   memset(void *s, char c, size_t n) : sets the first n bytes of the memory area pointed by s
     *                                       to the specified value c.
     * DEFINEs:
     *   PTE_P           0x001                   // page table/directory entry flags bit : Present
     *   PTE_W           0x002                   // page table/directory entry flags bit : Writeable
     *   PTE_U           0x004                   // page table/directory entry flags bit : User can access
     */

    // 获取传入的线性地址中所对应的页目录项的物理地址
    // PDX(la):获取虚拟地址la的页目录项索引
    // &pgdir[PDX(la)]:根据页目录项索引,从页目录表中找到对应的页目录项的指针
    pde_t *pdep = &pgdir[PDX(la)];

    // 如果该项不可用
    if (!(*pdep & PTE_P))
    {
        struct Page *page;

        // 如果分配页面失败或者不允许分配,则返回NULL
        if (!create || (page = alloc_page()) == NULL)
            return NULL;

        // 否则进行分配
        // 设置该物理页面的引用次数为1
        set_page_ref(page, 1);

        // 获取当前物理页面所管理的物理地址
        uintptr_t pa = page2pa(page);

        // 清空该物理页面的数据(需要注意使用的是虚拟地址)
        // KADDR(pa) : 获取物理地址pa对应的内核虚拟地址
        memset(KADDR(pa), 0, PGSIZE);

        // 将新分配的页表设置权限后填入页目录项中
        *pdep = pa | PTE_U | PTE_W | PTE_P;
    }

    //KADDR(PDE_ADDR(*pdep))找到页目录项的物理地址,再将该物理地址转化为虚拟地址
    //PTX(la)得到虚拟地址la的页表项索引,则KADDR(PDE_ADDR(*pdep)))[PTX(la)]就是该页表项
    //最后返回该页表项的地址,该页表项里存的是物理页面的地址
    return &((pte_t *)KADDR(PDE_ADDR(*pdep)))[PTX(la)];
}

问题二:请描述页目录项(Page Directory Entry)和页表项(Page Table Entry)中每个组成部分的含义以及对ucore而言的潜在用处。

答:

页目录项(PDE)结构及对ucore的潜在用处如下:

      31-12          11-8      7     6    5    4     3    2   1   0
+--------------+-------------+----+-----+---+-----+-----+---+---+---+
|     Offset   |    Avail    | PS | MBZ | A | PCD | PWT | U | W | P |
+--------------+-------------+----+-----+---+-----+-----+---+---+---+
  • 0 - Present: 表示当前PTE所指向的物理页面是否驻留在内存中
  • 1 - Writeable: 表示是否允许读写
  • 2 - User: 表示该页在User(ring 3)特权级下是否允许访问
  • 3 - PageWriteThough: 表示是否使用write through缓存写策略
  • 4 - PageCacheDisable: 表示是否不对该页进行缓存
  • 5 - Access: 表示该页是否已被访问过
  • 6 - MustBeZero: 该位保留为0
  • 7 - PageSize: 这个位用来确定 32 位分页的页大小,当该位为 1 且 CR4 的 PSE 位为 1 时,页大小为4M,否则为4K
  • 8 - 11 - Available: 这四位并没有被内核或中断所使用,可保留给OS使用
  • 12-31 - Offset: 目标地址的后20位(页对齐的物理地址)

页表项(PTE)结构及对ucore的潜在用处如下:

      31-12       11-9    8    7    6   5    4     3    2   1   0
+--------------+-------+-----+----+---+---+-----+-----+---+---+---+
|     Offset   | Avail | MBZ | PS | D | A | PCD | PWT | U | W | P |
+--------------+-------+-----+----+---+---+-----+-----+---+---+---+
  • 0 - Present: 表示当前PTE所指向的物理页面是否驻留在内存中
  • 1 - Writeable: 表示是否允许读写
  • 2 - User: 表示该页在User(ring 3)特权级下是否允许访问
  • 3 - PageWriteThough: 表示是否使用write through缓存写策略
  • 4 - PageCacheDisable: 表示是否不对该页进行缓存
  • 5 - Access: 表示该页是否已被访问过
  • 6 - Dirty: 表示该页是否已被修改
  • 7 - PageSize: 页的大小类型
  • 8 - MustBeZero: 该位保留为0
  • 9-11 - Available: 这三位并没有被内核或中断所使用,可保留给OS使用
  • 12-31 - Offset: 目标地址的后20位(页对齐的物理地址)

问题三:如果ucore执行过程中访问内存,出现了页访问异常,请问硬件要做哪些事情?

答:

  • 将触发页访问异常虚地址保存到cr2寄存器中
  • 设置错误代码,触发14号中断,也就是缺页错误
  • 抛出Page Fault异常,将外存的数据读到内存中(应该是读存在硬盘上的虚拟内存分页文件)
  • 进行上下文切换,退出中断,返回到中断前的状态

练习3:释放某虚地址所在的页并取消对应二级页表项的映射(需要编程)

当释放一个包含某虚地址的物理内存页时,需要让对应此物理内存页的管理数据结构Page做相关的清除处理,使得此物理内存页成为空闲;另外还需把表示虚地址与物理地址对应关系的二级页表项清除。

本练习任务:

补全page_remove_pte函数(在 kern/mm/pmm.c 中)。请在实验报告中简要说明你的设计实现过程并回答如下问题:

  • 数据结构Page的全局变量(其实是一个数组)的每一项与页表中的页目录项页表项有无对应关系?如果有,其对应关系是什么?
  • 如果希望虚拟地址物理地址相等,则需要如何修改lab2才能完成此事?(鼓励通过编程来具体完成这个问题)

提示:请仔细查看和理解page_remove_pte函数中的注释。page_remove_pte函数的调用关系图如下所示:

36

问题解答

问题一:当释放一个包含某虚地址的物理内存页时,需要让对应此物理内存页的管理数据结构Page做相关的清除处理,使得此物理内存页成为空闲;另外还需把表示虚地址与物理地址对应关系的二级页表项清除。补全page_remove_pte函数。

答:

实现后的page_remove_pte函数的代码(已加注释):

static inline void
page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep)
{
    /* LAB2 EXERCISE 3: YOUR CODE
     *
     * Please check if ptep is valid, and tlb must be manually updated if mapping is updated
     *
     * Maybe you want help comment, BELOW comments can help you finish the code
     *
     * Some Useful MACROs and DEFINEs, you can use them in below implementation.
     * MACROs or Functions:
     *   struct Page *page pte2page(*ptep): get the according page from the value of a ptep
     *   free_page : free a page
     *   page_ref_dec(page) : decrease page->ref. NOTICE: ff page->ref == 0 , then this page should be free.
     *   tlb_invalidate(pde_t *pgdir, uintptr_t la) : Invalidate a TLB entry, but only if the page tables being
     *                        edited are the ones currently in use by the processor.
     * DEFINEs:
     *   PTE_P           0x001                   // page table/directory entry flags bit : Present
     */

    // 如果传入的页表项是可用的
    if (*ptep & PTE_P)
    {
        // 获取该页表项所对应的地址
        struct Page *page = pte2page(*ptep);

        // 如果该页的引用次数在减1后为0,表明仅被我们当前引用了1次,可以释放
        if (page_ref_dec(page) == 0)
            // 释放当前页
            free_page(page);

        // 二级页表表项清零
        *ptep = 0;

        // 刷新TLB中该页的缓存使其无效(当且仅当正在编辑的页表是处理器当前正在使用的页表时)
        /*
         TLB(Translation Lookaside Buffer)转换检测缓冲区是一个内存管理单元,是用于改进虚拟地址到物理地址转换速度的缓存。
         其中每一行都保存着一个由单个PTE(Page Table Entry,页表项)组成的块。
         如果没有TLB,则每次取数据都需要两次访问内存。
        */
        tlb_invalidate(pgdir, la);
    }
}

当完成所有练习后,在lab2目录下执行make qemu,应该大致得到以下结果,三个check检查均通过

42

执行make grade应该得到以下结果:

43

问题二:数据结构Page的全局变量(其实是一个数组)的每一项与页表中的页目录项和页表项有无对应关系?如果有,其对应关系是什么?

答:

当页目录项或页表项有效时,Page数组中的项与页目录项或页表项存在对应关系。实际上,每个页目录项记录一个页表的信息,每个页表项记录一个物理页的信息。页目录表中存放着数个页表项,这些页表项中存放了某个二级页表所在物理页的信息,包括该二级页表的物理地址,但使用线性地址的头部PDX(Page Directory Index)来索引页目录表。而页表(二级页表)与页目录(一级页表)具有类似的特性,页表中的页表项指向所管理的物理页的物理地址,使用线性地址的中部PTX(Page Table Index)来索引页表。页目录项保存的物理页面地址(即某个页表),以及页表项保存的物理页面地址都对应于Page数组中的某一页。

另:为什么页目录表中存放的是物理地址呢?

可能是为了防止递归查找。即原先查找页目录表的目的是想将某个线性地址转换为物理地址,但如果页目录表中存放的是二级页表的线性地址,则需要先查找该二级页表的物理地址,此时需要递归查找,这可能会出现永远也查找不到物理地址的情况。

问题三:如果希望虚拟地址与物理地址相等,则需要如何修改lab2才能完成此事?

答:

注意,这部分仅用于回答问题,不要实际去修改代码,否则会导致make qemu报错,因为check检查函数不允许内核基地址为0x0,删掉第三个check函数也许可行。

  • 先将tools/kernel.ld中的第10行内核加载地址0xC0100000修改为0x00100000

    // 代码第10行 修改前:
    . = 0xC0100000;
    
    // 代码第10行 修改后:
    . = 0x00100000;
  • 再将kern/mm/memlayout.h中的第56行内核偏移地址0xC0000000修改为0x00000000

    // 代码第56行 修改前:
    #define KERNBASE            0xC0000000
    
    // 代码第56行 修改后:
    #define KERNBASE            0x00000000
  • 关闭页机制,这一步是为了保证运行时不报错。将kern/init/entry.S开启页机制的那一段代码删除即可。否则在分页模式,取消掉 boot_pgdir[0] 的页表下 kern_init 会被置于一个根本无法访问到的地址。

    # 代码第14-17行 修改前:
    movl %cr0, %eax
    orl $(CR0_PE | CR0_PG | CR0_AM | CR0_WP | CR0_NE | CR0_TS | CR0_EM | CR0_MP), %eax
    andl $~(CR0_TS | CR0_EM), %eax
    movl %eax, %cr0
    
    # 代码第14-17行 修改后:
    # 直接删除第14-17行代码
Lab 2 完成

扩展练习Challenge1:buddy system(伙伴系统)分配算法(需要编程)

Buddy System算法把系统中的可用存储空间划分为存储块(Block)来进行管理, 每个存储块的大小必须是2的n次幂(Pow(2, n)), 即1, 2, 4, 8, 16, 32, 64, 128...

本练习任务:

参考伙伴分配器的一个极简实现, 在ucore中实现buddy system分配算法,要求有比较充分的测试用例说明实现的正确性需要有设计文档

开摆。

扩展练习Challenge2:任意大小的内存单元slub分配算法(需要编程)

slub算法,实现两层架构的高效内存单元分配,第一层是基于页大小的内存分配,第二层是在第一层基础上实现基于任意大小的内存分配。

本练习任务:

参考linux的slub分配算法,在ucore中实现slub分配算法。要求有比较充分的测试用例说明实现的正确性需要有设计文档。可简化实现,能够体现其主体思想即可。

开摆。

实验内容(理论部分)

此处直接引用了实验指导书上的内容

接下来将首先对实验的执行流程做个介绍,并进一步介绍如何探测物理内存的大小与布局,如何以页为单位来管理计算机系统中的物理内存,如何设计物理内存页的分配算法,最后比较详细地分析了在80386的段页式硬件机制下,ucore操作系统把段式内存管理的功能弱化,并实现以分页为主的页式内存管理的过程。

实验执行流程概述

本次实验主要完成ucore内核对物理内存的管理工作。参考ucore总控函数kern_init的代码,可以清楚地看到在调用完成物理内存初始化的pmm_init函数之前和之后,是已有lab1实验的工作,好像没啥修改。其实不然,ucore有两个方面的扩展。首先,bootloader的工作有增加,在bootloader中,完成了对物理内存资源的探测工作(可进一步参阅附录A附录B,让ucore kernel在后续执行中能够基于bootloader探测出的物理内存情况进行物理内存管理初始化工作。其次,bootloader不像lab1那样,直接调用kern_init函数,而是先调用位于lab2/kern/init/entry.S中的kern_entry函数。kern_entry函数的主要任务是为执行kern_init建立一个良好的C语言运行环境(设置堆栈),而且临时建立了一个段映射关系,为之后建立分页机制的过程做一个准备。完成这些工作后,才调用kern_init函数。

kern_init函数在完成一些输出并对lab1实验结果的检查后,将进入物理内存管理初始化的工作,即调用pmm_init函数完成物理内存的管理,这也是我们lab2的内容。接着是执行中断和异常相关的初始化工作,即调用pic_init函数和idt_init函数等,这些工作与lab1的中断异常初始化工作的内容是相同的。

为了完成物理内存管理,这里首先需要探测可用的物理内存资源;了解到物理内存位于什么地方,有多大之后,就以固定页面大小来划分整个物理内存空间,并准备以此为最小内存分配单位来管理整个物理内存,管理在内核运行过程中每页内存,设定其可用状态(free的,used的,还是reserved的),这其实就对应了我们在课本上讲到的连续内存分配概念和原理的具体实现;接着ucore kernel就要建立页表, 启动分页机制,让CPU的MMU把预先建立好的页表中的页表项读入到TLB中,根据页表项描述的虚拟页(Page)与物理页帧(Page Frame)的对应关系完成CPU对内存的读、写和执行操作。这一部分其实就对应了我们在课本上讲到内存映射、页表、多级页表等概念和原理的具体实现。

在代码分析上,建议根据执行流程来直接看源代码,并可采用GDB源码调试的手段来动态地分析ucore的执行过程。内存管理相关的总体控制函数是pmm_init函数,它完成的主要工作包括:

  • 初始化物理内存页管理器框架pmm_manager;
  • 建立空闲的page链表,这样就可以分配以页(4KB)为单位的空闲内存了;
  • 检查物理内存页分配算法;
  • 为确保切换到分页机制后,代码能够正常执行,先建立一个临时二级页表;
  • 建立一一映射关系的二级页表;
  • 使能分页机制;
  • 重新设置全局段描述符表;
  • 取消临时二级页表;
  • 检查页表建立是否正确;
  • 通过自映射机制完成页表的打印输出(这部分是扩展知识)

另外,主要注意的相关代码内容包括:

  • boot/bootasm.S中探测内存部分(从probe_memory到finish_probe的代码);
  • 管理每个物理页的Page数据结构(在mm/memlayout.h中),这个数据结构也是实现连续物理内存分配算法的关键数据结构,可通过此数据结构来完成空闲块的链接和信息存储,而基于这个数据结构的管理物理页数组起始地址就是全局变量pages,具体初始化此数组的函数位于page_init函数中;
  • 用于实现连续物理内存分配算法的物理内存页管理器框架pmm_manager,这个数据结构定义了实现内存分配算法的关键函数指针,而同学需要完成这些函数的具体实现;
  • 设定二级页表和建立页表项以完成虚实地址映射关系,这与硬件相关,且用到不少内联函数,源代码相对难懂一些。具体完成页表和页表项建立的重要函数是boot_map_segment函数,而get_pte函数是完成虚实映射关键的关键。

探测系统物理内存布局

当 ucore 被启动之后,最重要的事情就是知道还有多少内存可用,一般来说,获取内存大小的方法有 BIOS 中断调用直接探测两种。但BIOS 中断调用方法是一般只能在实模式下完成,而直接探测方法必须在保护模式下完成。通过 BIOS 中断获取内存布局有三种方式,都是基于INT 15h中断,分别为88h e801h e820h。但是并非在所有情况下这三种方式都能工作。在 Linux kernel 里,采用的方法是依次尝试这三种方法。而在本实验中,我们通过e820h中断获取内存信息。因为e820h中断必须在实模式下使用,所以我们在 bootloader 进入保护模式之前调用这个 BIOS 中断,并且把 e820 映射结构保存在物理地址0x8000处。具体实现详见boot/bootasm.S。有关探测系统物理内存方法和具体实现的信息参见lab2实验指导的附录A附录B

以页为单位管理物理内存

指导书传送门

物理内存页分配算法实现

指导书传送门

实现分页机制

在本实验中,需要重点了解和实现基于页表的页机制和以页为单位的物理内存管理方法和分配算法等。由于ucore OS是基于80386 CPU实现的,所以CPU在进入保护模式后,就直接使能了段机制,并使得ucore OS需要在段机制的基础上建立页机制。下面比较详细地介绍了实现分页机制的过程。

段页式管理基本概念

如图4在保护模式中,x86 体系结构将内存地址分成三种:逻辑地址(也称虚地址)、线性地址和物理地址。逻辑地址即是程序指令中使用的地址,物理地址是实际访问内存的地址。逻辑地址通过段式管理的地址映射可以得到线性地址,线性地址通过页式管理的地址映射得到物理地址。

段页式管理总体框架图:

38

段式管理前一个实验已经讨论过。在 ucore 中段式管理只起到了一个过渡作用,它将逻辑地址不加转换直接映射成线性地址,所以我们在下面的讨论中可以对这两个地址不加区分(目前的 OS 实现也是不加区分的)。

如图所示,页式管理将线性地址分成三部分(图中的 Linear Address 的 Directory 部分、 Table 部分和 Offset 部分)。ucore 的页式管理通过一个二级的页表实现。一级页表的起始物理地址存放在 cr3 寄存器中,这个地址必须是一个页对齐的地址,也就是低 12 位必须为 0。目前,ucore 用boot_cr3(mm/pmm.c)记录这个值。

分页机制管理图:

39

建立段页式管理中需要考虑的关键问题

为了实现分页机制,需要建立好虚拟内存和物理内存的页映射关系,即正确建立二级页表。此过程涉及硬件细节,不同的地址映射关系组合,相对比较复杂。总体而言,我们需要思考如下问题:

  • 如何在建立页表的过程中维护全局段描述符表(GDT)和页表的关系,确保ucore能够在各个时间段上都能正常寻址?
  • 对于哪些物理内存空间需要建立页映射关系?
  • 具体的页映射关系是什么?
  • 页目录表的起始地址设置在哪里?
  • 页表的起始地址设置在哪里,需要多大空间?
  • 如何设置页目录表项的内容?
  • 如何设置页表项的内容?

系统执行中地址映射的三个阶段

指导书传送门

建立虚拟页和物理页帧的地址映射关系

指导书传送门

附录

Lab 3 虚拟内存管理

实验目的

  • 了解虚拟内存的Page Fault异常处理实现
  • 了解页替换算法在操作系统中的实现

实验内容(操作部分)

本次实验是在实验二的基础上,借助于页表机制和实验一中涉及的中断异常处理机制,完成Page Fault异常处理和FIFO页替换算法的实现,结合磁盘提供的缓存空间,从而能够支持虚存管理,提供一个比实际物理内存空间“更大”的虚拟内存空间给系统使用。这个实验与实际操作系统中的实现比较起来要简单,不过需要了解实验一和实验二的具体实现。实际操作系统系统中的虚拟内存管理设计与实现是相当复杂的,涉及到与进程管理系统、文件系统等的交叉访问。如果大家有余力,可以尝试完成扩展练习,实现extended clock页替换算法。

项目组成

|-- boot
|-- kern
| |-- driver
| | |-- …
| | |-- ide.c
| | \`-- ide.h
| |-- fs
| | |-- fs.h
| | |-- swapfs.c
| | \`-- swapfs.h
| |-- init
| | |-- …
| | \`-- init.c
| |-- mm
| | |-- default\_pmm.c
| | |-- default\_pmm.h
| | |-- memlayout.h
| | |-- mmu.h
| | |-- pmm.c
| | |-- pmm.h
| | |-- swap.c
| | |-- swap.h
| | |-- swap\_fifo.c
| | |-- swap\_fifo.h
| | |-- vmm.c
| | \`-- vmm.h
| |-- sync
| \`-- trap
| |-- trap.c
| \`-- …
|-- libs
| |-- list.h
| \`-- …
\`-- tools

相对与实验二,实验三主要改动如下:

  • kern/mm/default_pmm.[ch]:实现基于struct pmm_manager类框架的Fist-Fit物理内存分配参考实现(分配最小单位为页,即4096字节),相关分配页和释放页等实现会间接被kmalloc/kfree等函数使用。
  • kern/mm/pmm.[ch]:pmm.h定义物理内存分配类框架struct pmm_manager。pmm.c包含了对此物理内存分配类框架的访问,以及与建立、修改、访问页表相关的各种函数实现。在本实验中会用到kmalloc/kfree等函数。
  • libs/list.h:定义了通用双向链表结构以及相关的查找、插入等基本操作,这是建立基于链表方法的物理内存管理(以及其他内核功能)的基础。在lab0文档中有相关描述。其他有类似双向链表需求的内核功能模块可直接使用list.h中定义的函数。在本实验中会多次用到插入,删除等操作函数。
  • kern/driver/ide.[ch]:定义和实现了内存页swap机制所需的磁盘扇区的读写操作支持;在本实验中会涉及通过swapfs_*函数间接使用文件中的函数。故了解即可。
  • kern/fs/*:定义和实现了内存页swap机制所需从磁盘读数据到内存页和写内存数据到磁盘上去的函数 swapfs_read/swapfs_write。在本实验中会涉及使用这两个函数。
  • kern/mm/memlayout.h:修改了struct Page,增加了两项pra_*成员结构,其中pra_page_link可以用来建立描述各个页访问情况(比如根据访问先后)的链表。在本实验中会涉及使用这两个成员结构,以及le2page等宏。
  • kern/mm/vmm.[ch]:vmm.h描述了mm_struct,vma_struct等表述可访问的虚存地址访问的一些信息,下面会进一步详细讲解。vmm.c涉及mm,vma结构数据的创建/销毁/查找/插入等函数,这些函数在check_vma、check_vmm等中被使用,理解即可。而page fault处理相关的do_pgfault函数是本次实验需要涉及完成的。
  • kern/mm/swap.[ch]:定义了实现页替换算法类框架struct swap_manager。swap.c包含了对此页替换算法类框架的初始化、页换入/换出等各种函数实现。重点是要理解何时调用swap_out和swap_in函数。和如何在此框架下连接具体的页替换算法实现。check_swap函数以及被此函数调用的_fifo_check_swap函数完成了对本次实验中的练习2:FIFO页替换算法基本正确性的检查,可了解,便于知道为何产生错误。
  • kern/mm/swap_fifo.[ch]:FIFO页替换算法的基于页替换算法类框架struct swap_manager的简化实现,主要被swap.c的相关函数调用。重点是_fifo_map_swappable函数(可用于建立页访问属性和关系,比如访问时间的先后顺序)和_fifo_swap_out_victim函数(可用于实现挑选出要换出的页),当然换出哪个页需要借助于fifo_map_swappable函数建立的某种属性关系,已选出合适的页。
  • kern/mm/mmu.h:其中定义了页表项的各种属性位,比如PTE_PPET_DPET_A等,对于实现扩展实验的clock算法会有帮助。

本次实验的主要练习集中在vmm.c中的do_pgfault函数和swap_fifo.c中的fifo_map_swappable函数、fifo_swap_out_victim函数。

编译执行

在完成实验后,编译并运行代码的命令如下:

make
make qemu

则可以得到如附录所示的显示内容(仅供参考,不是标准答案输出)

$ make qemu
(THU.CST) os is loading ...

Special kernel symbols:
  entry  0xc010002a (phys)
  etext  0xc01081c3 (phys)
  edata  0xc011fac8 (phys)
  end    0xc0120cf0 (phys)
Kernel executable memory footprint: 132KB
ebp:0xc011ef48 eip:0xc0100a51 args:0x00010094 0x00000000 0xc011ef78 0xc01000b8 
    kern/debug/kdebug.c:308: print_stackframe+21
ebp:0xc011ef58 eip:0xc0100d4f args:0x00000000 0x00000000 0x00000000 0xc011efc8 
    kern/debug/kmonitor.c:129: mon_backtrace+10
ebp:0xc011ef78 eip:0xc01000b8 args:0x00000000 0xc011efa0 0xffff0000 0xc011efa4 
    kern/init/init.c:56: grade_backtrace2+19
ebp:0xc011ef98 eip:0xc01000d9 args:0x00000000 0xffff0000 0xc011efc4 0x0000002a 
    kern/init/init.c:61: grade_backtrace1+27
ebp:0xc011efb8 eip:0xc01000f5 args:0x00000000 0xc010002a 0xffff0000 0xc010006d 
    kern/init/init.c:66: grade_backtrace0+19
ebp:0xc011efd8 eip:0xc0100115 args:0x00000000 0x00000000 0x00000000 0xc0108200 
    kern/init/init.c:71: grade_backtrace+26
ebp:0xc011eff8 eip:0xc010007a args:0x00000000 0x00000000 0x0000ffff 0x40cf9a00 
    kern/init/init.c:31: kern_init+79
memory management: default_pmm_manager
e820map:
  memory: 0009fc00, [00000000, 0009fbff], type = 1.
  memory: 00000400, [0009fc00, 0009ffff], type = 2.
  memory: 00010000, [000f0000, 000fffff], type = 2.
  memory: 07ee0000, [00100000, 07fdffff], type = 1.
  memory: 00020000, [07fe0000, 07ffffff], type = 2.
  memory: 00040000, [fffc0000, ffffffff], type = 2.
check_alloc_page() succeeded!
check_pgdir() succeeded!
check_boot_pgdir() succeeded!
-------------------- BEGIN --------------------
PDE(0e0) c0000000-f8000000 38000000 urw
  |-- PTE(38000) c0000000-f8000000 38000000 -rw
PDE(001) fac00000-fb000000 00400000 -rw
  |-- PTE(000e0) faf00000-fafe0000 000e0000 urw
  |-- PTE(00001) fafeb000-fafec000 00001000 -rw
--------------------- END ---------------------
check_vma_struct() succeeded!
page fault at 0x00000100: K/W [no page found].
check_pgfault() succeeded!
check_vmm() succeeded.
ide 0:      10000(sectors), 'QEMU HARDDISK'.
ide 1:     262144(sectors), 'QEMU HARDDISK'.
SWAP: manager = fifo swap manager
BEGIN check_swap: count 31966, total 31966
setup Page Table for vaddr 0X1000, so alloc a page
setup Page Table vaddr 0~4MB OVER!
set up init env for check_swap begin!
page fault at 0x00001000: K/W [no page found].
page fault at 0x00002000: K/W [no page found].
page fault at 0x00003000: K/W [no page found].
page fault at 0x00004000: K/W [no page found].
set up init env for check_swap over!
write Virt Page c in fifo_check_swap
write Virt Page a in fifo_check_swap
write Virt Page d in fifo_check_swap
write Virt Page b in fifo_check_swap
write Virt Page e in fifo_check_swap
page fault at 0x00005000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x1000 to disk swap entry 2
write Virt Page b in fifo_check_swap
write Virt Page a in fifo_check_swap
page fault at 0x00001000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x2000 to disk swap entry 3
swap_in: load disk swap entry 2 with swap_page in vadr 0x1000
write Virt Page b in fifo_check_swap
page fault at 0x00002000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x3000 to disk swap entry 4
swap_in: load disk swap entry 3 with swap_page in vadr 0x2000
write Virt Page c in fifo_check_swap
page fault at 0x00003000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x4000 to disk swap entry 5
swap_in: load disk swap entry 4 with swap_page in vadr 0x3000
write Virt Page d in fifo_check_swap
page fault at 0x00004000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x5000 to disk swap entry 6
swap_in: load disk swap entry 5 with swap_page in vadr 0x4000
count is 7, total is 7
check_swap() succeeded!
++ setup timer interrupts
100 ticks
100 ticks
100 ticks
100 ticks

实验执行流程概述

本次实验主要完成ucore内核对虚拟内存的管理工作。其总体设计思路还是比较简单,即首先完成初始化虚拟内存管理机制,即需要设置好哪些页需要放在物理内存中,哪些页不需要放在物理内存中,而是可被换出到硬盘上,并涉及完善建立页表映射、页访问异常处理操作等函数实现。然后就执行一组访存测试,看看我们建立的页表项是否能够正确完成虚实地址映射,是否正确描述了虚拟内存页在物理内存中还是在硬盘上,是否能够正确把虚拟内存页在物理内存和硬盘之间进行传递,是否正确实现了页面替换算法等。lab3的总体执行流程如下。

首先是初始化过程。参考ucore总控函数init的代码,可以看到在调用完成虚拟内存初始化的vmm_init函数之前,需要首先调用pmm_init函数完成物理内存的管理,这也是我们lab2已经完成的内容。接着是执行中断和异常相关的初始化工作,即调用pic_init函数和idt_init函数等,这些工作与lab1的中断异常初始化工作的内容是相同的。

在调用完idt_init函数之后,将进一步调用三个lab3中才有的新函数vmm_init、ide_init和swap_init。这三个函数涉及了本次实验中的两个练习。第一个函数vmm_init是检查我们的练习1是否正确实现了。为了表述不在物理内存中的“合法”虚拟页,需要有数据结构来描述这样的页,为此ucore建立了mm_struct和vma_struct数据结构(接下来的小节中有进一步详细描述),假定我们已经描述好了这样的“合法”虚拟页,当ucore访问这些“合法”虚拟页时,会由于没有虚实地址映射而产生页访问异常。如果我们正确实现了练习1,则do_pgfault函数会申请一个空闲物理页,并建立好虚实映射关系,从而使得这样的“合法”虚拟页有实际的物理页帧对应。这样练习1就算完成了。

ide_init和swap_init是为练习2准备的。由于页面置换算法的实现存在对硬盘数据块的读写,所以ide_init就是完成对用于页换入换出的硬盘(简称swap硬盘)的初始化工作。完成ide_init函数后,ucore就可以对这个swap硬盘进行读写操作了。swap_init函数首先建立swap_manager,swap_manager是完成页面替换过程的主要功能模块,其中包含了页面置换算法的实现(具体内容可参考5小节)。然后会进一步调用执行check_swap函数在内核中分配一些页,模拟对这些页的访问,这会产生页访问异常。如果我们正确实现了练习2,就可通过do_pgfault来调用swap_map_swappable函数来查询这些页的访问情况并间接调用实现页面置换算法的相关函数,把“不常用”的页换出到磁盘上。

ucore在实现上述技术时,需要解决三个关键问题:

  1. 当程序运行中访问内存产生page fault异常时,如何判定这个引起异常的虚拟地址内存访问是越界、写只读页的“非法地址”访问还是由于数据被临时换出到磁盘上或还没有分配内存的“合法地址”访问?
  2. 何时进行请求调页/页换入换出处理?
  3. 如何在现有ucore的基础上实现页替换算法?

练习0:填写已有实验

本实验依赖实验1/2。请把你做的实验1/2的代码填入本实验中代码中有“LAB1”,“LAB2”的注释相应部分。

问题解答

lab1中修改过的文件有:

  • kern/debug/kdebug.c
  • kern/trap/trap.c

lab2中修改过的文件有:

  • kern/mm/default_pmm.c
  • kern/mm/pmm.c

我使用的是Visual Studio Code的代码比较功能来半自动合并,这样比较稳妥。大致操作是:找到上一个实验修改的代码文件,右键-选择以进行比较,再找到本次实验对应的那个代码文件,右键-与已选项目进行比较,之后就会显示代码差异结果,找到相应的部分复制粘贴到本次实验的代码中保存即可。

例如,将旧的kdebug.c和新的进行比较,得到:

44

那么我们就将红色的部分复制粘贴到新的代码文件上,以此类推,要注意的是新的代码文件中很可能会添加一些语句,注意辨别,这些不要改动。

练习1:给未被映射的地址映射上物理页(需要编程)

完成do_pgfault函数(在mm/vmm.c中),给未被映射的地址映射上物理页。设置访问权限的时候需要参考页面所在 VMA 的权限,同时需要注意映射物理页时需要操作内存控制结构所指定的页表,而不是内核的页表。注意:在LAB3 EXERCISE 1处填写代码。执行make qemu后,如果通过check_pgfault函数的测试后,会有check_pgfault() succeeded!的输出,表示练习1基本正确。

请在实验报告中简要说明你的设计实现过程。请回答如下问题:

  • 请描述页目录项(Page Directory Entry)和页表项(Page Table Entry)中组成部分对ucore实现页替换算法的潜在用处。
  • 如果ucore的缺页服务例程在执行过程中访问内存,出现了页访问异常,请问硬件要做哪些事情?

问题解答

实现后的do_pgfault函数代码如下(已加注释,练习二也顺带贴上了):

int do_pgfault(struct mm_struct *mm, uint32_t error_code, uintptr_t addr)
{
    int ret = -E_INVAL;
    // 获取触发pgfault的虚拟地址所在的虚拟页
    struct vma_struct *vma = find_vma(mm, addr);

    pgfault_num++;
    // 如果当前访问的虚拟地址不在已经分配的虚拟页中
    if (vma == NULL || vma->vm_start > addr)
    {
        cprintf("not valid addr %x, and  can not find it in vma\n", addr);
        goto failed;
    }
    // 检测错误码,这里的检测不涉及特权判断。
    switch (error_code & 3)
    {
    default:
        /* error code flag : default is 3 ( W/R=1, P=1): write, present */
        // 写,同时存在物理页,则写时复制
        // 需要注意的是,default会执行case2的代码,也就是判断是否有写权限。

    case 2:
        /* error code flag : (W/R=1, P=0): write, not present */
        // 读,同时不存在物理页
        // 同时如果当前操作是写入,但所在虚拟页不允许写入
        if (!(vma->vm_flags & VM_WRITE))
        {
            cprintf("do_pgfault failed: error code flag = write AND not present, but the addr's vma cannot write\n");
            goto failed;
        }
        break;
    case 1:
        /* error code flag : (W/R=0, P=1): read, present */
        // 读,同时存在物理页。那就不可能会调用page fault,如果真的发生了则表明某个地方存在异常,直接failed。
        cprintf("do_pgfault failed: error code flag = read AND present\n");
        goto failed;
    case 0:
        /* error code flag : (W/R=0, P=0): read, not present */
        // 写,同时不存在物理页面
        // 如果当前操作是读取,但所在虚拟页不允许读取或执行
        if (!(vma->vm_flags & (VM_READ | VM_EXEC)))
        {
            cprintf("do_pgfault failed: error code flag = read AND not present, but the addr's vma cannot read or exec\n");
            goto failed;
        }
    }
    /* IF (write an existed addr ) OR
     *    (write an non_existed addr && addr is writable) OR
     *    (read  an non_existed addr && addr is readable)
     * THEN
     *    continue process
     */
    // 设置页表项的权限
    uint32_t perm = PTE_U;
    if (vma->vm_flags & VM_WRITE)
    {
        perm |= PTE_W;
    }
    addr = ROUNDDOWN(addr, PGSIZE);

    ret = -E_NO_MEM;

    pte_t *ptep = NULL;
    /*LAB3 EXERCISE 1: YOUR CODE
    * Maybe you want help comment, BELOW comments can help you finish the code
    *
    * Some Useful MACROs and DEFINEs, you can use them in below implementation.
    * MACROs or Functions:
    *   get_pte : get an pte and return the kernel virtual address of this pte for la
    *             if the PT contians this pte didn't exist, alloc a page for PT (notice the 3th parameter '1')
    *   pgdir_alloc_page : call alloc_page & page_insert functions to allocate a page size memory & setup
    *             an addr map pa<--->la with linear address la and the PDT pgdir
    * DEFINES:
    *   VM_WRITE  : If vma->vm_flags & VM_WRITE == 1/0, then the vma is writable/non writable
    *   PTE_W           0x002                   // page table/directory entry flags bit : Writeable
    *   PTE_U           0x004                   // page table/directory entry flags bit : User can access
    * VARIABLES:
    *   mm->pgdir : the PDT of these vma
    *
    */
    // 查找当前虚拟地址所对应的页表项
    if ((ptep = get_pte(mm->pgdir, addr, 1)) == NULL)
    {
        cprintf("get_pte in do_pgfault failed\n");
        goto failed;
    }
    // 如果这个页表项所对应的物理页不存在,则
    if (*ptep == 0)
    {
        // 分配一块物理页,并设置页表项
        if (pgdir_alloc_page(mm->pgdir, addr, perm) == NULL)
        {
            cprintf("pgdir_alloc_page in do_pgfault failed\n");
            goto failed;
        }
    }
    else
    {
        /* LAB3 EXERCISE 2: YOUR CODE */
        // 如果这个页表项所对应的物理页存在,但不在内存中
        // 如果swap已经初始化完成
        if (swap_init_ok)
        {
            struct Page *page = NULL;
            // 将目标数据加载到某块新的物理页中
            // 该物理页可能是尚未分配的物理页,也可能是从别的已分配物理页中取的
            if ((ret = swap_in(mm, addr, &page)) != 0)
            {
                cprintf("swap_in in do_pgfault failed\n");
                goto failed;
            }
            // 将该物理页与对应的虚拟地址关联,同时设置页表。
            page_insert(mm->pgdir, page, addr, perm);
            // 当前缺失的页已经加载回内存中,所以设置当前页为可swap。
            swap_map_swappable(mm, addr, page, 1);
            page->pra_vaddr = addr;
        }
        else
        {
            cprintf("no swap_init_ok but ptep is %x, failed\n", *ptep);
            goto failed;
        }
    }
    ret = 0;
failed:
    return ret;
}

问题一答:

页目录项(PDE)结构及对ucore的潜在用处如下:

      31-12          11-8      7     6    5    4     3    2   1   0
+--------------+-------------+----+-----+---+-----+-----+---+---+---+
|     Offset   |    Avail    | PS | MBZ | A | PCD | PWT | U | W | P |
+--------------+-------------+----+-----+---+-----+-----+---+---+---+
  • 0 - Present: 表示当前PTE所指向的物理页面是否驻留在内存中
  • 1 - Writeable: 表示是否允许读写
  • 2 - User: 表示该页在User(ring 3)特权级下是否允许访问
  • 3 - PageWriteThough: 表示是否使用write through缓存写策略
  • 4 - PageCacheDisable: 表示是否不对该页进行缓存
  • 5 - Access: 表示该页是否已被访问过
  • 6 - MustBeZero: 该位保留为0
  • 7 - PageSize: 这个位用来确定 32 位分页的页大小,当该位为 1 且 CR4 的 PSE 位为 1 时,页大小为4M,否则为4K
  • 8 - 11 - Available: 这四位并没有被内核或中断所使用,可保留给OS使用
  • 12-31 - Offset: 目标地址的后20位(页对齐的物理地址)

页表项(PTE)结构及对ucore的潜在用处如下:

      31-12       11-9    8    7    6   5    4     3    2   1   0
+--------------+-------+-----+----+---+---+-----+-----+---+---+---+
|     Offset   | Avail | MBZ | PS | D | A | PCD | PWT | U | W | P |
+--------------+-------+-----+----+---+---+-----+-----+---+---+---+
  • 0 - Present: 表示当前PTE所指向的物理页面是否驻留在内存中
  • 1 - Writeable: 表示是否允许读写
  • 2 - User: 表示该页在User(ring 3)特权级下是否允许访问
  • 3 - PageWriteThough: 表示是否使用write through缓存写策略
  • 4 - PageCacheDisable: 表示是否不对该页进行缓存
  • 5 - Access: 表示该页是否已被访问过
  • 6 - Dirty: 表示该页是否已被修改
  • 7 - PageSize: 页的大小类型
  • 8 - MustBeZero: 该位保留为0
  • 9-11 - Available: 这三位并没有被内核或中断所使用,可保留给OS使用
  • 12-31 - Offset: 目标地址的后20位(页对齐的物理地址)

问题二答:

  • 将触发页访问异常虚地址保存到cr2寄存器中
  • 压入EFLAGSCS, EIP错误码中断号当前内核栈
  • 保存上下文
  • 执行新的缺页中断程序
  • 恢复上下文
  • 继续执行上一级的缺页服务例程

练习2:补充完成基于FIFO的页面替换算法(需要编程)

完成vmm.c中的do_pgfault函数,并且在实现FIFO算法的swap_fifo.c中完成map_swappableswap_out_victim函数。注意:在LAB3 EXERCISE 2处填写代码。执行make qemu后,如果通过check_swap函数的测试后,会有check_swap() succeeded!的输出,表示练习2基本正确。

请在实验报告中简要说明你的设计实现过程。请在实验报告中回答如下问题:

  • 如果要在ucore上实现extended clock页替换算法,现有的swap_manager框架是否足以支持在ucore中实现此算法?如果是,请给出你的设计方案。如果不是,请给出你的新的扩展和基此扩展的设计方案。并需要回答如下问题:

    • 需要被换出的页的特征是什么?
  • 在ucore中如何判断具有这样特征的页?

    • 何时进行换入和换出操作?

问题解答

练习1中已经完成了do_pgfault函数。要实现FIFO算法的swap,只需当新加入一个物理页时,将该物理页加入至链表首部,当需要换出某个物理页时,选择链表末尾的物理页换出,这样就能实现先入先出的效果了。实现后的_fifo_map_swappable_fifo_swap_out_victim函数代码如下(已加注释):

/*
 * (3)_fifo_map_swappable: According FIFO PRA, we should link the most recent arrival page at the back of pra_list_head qeueue
 */
static int
_fifo_map_swappable(struct mm_struct *mm, uintptr_t addr, struct Page *page, int swap_in)
{
    list_entry_t *head = (list_entry_t *)mm->sm_priv;
    list_entry_t *entry = &(page->pra_page_link);

    assert(entry != NULL && head != NULL);
    //record the page access situlation
    /*LAB3 EXERCISE 2: YOUR CODE*/
    //(1)link the most recent arrival page at the back of the pra_list_head qeueue.
    list_add(head, entry);
    return 0;
}
/*
 *  (4)_fifo_swap_out_victim: According FIFO PRA, we should unlink the  earliest arrival page in front of pra_list_head qeueue,
 *                            then assign the value of *ptr_page to the addr of this page.
 */
static int
_fifo_swap_out_victim(struct mm_struct *mm, struct Page **ptr_page, int in_tick)
{
    list_entry_t *head = (list_entry_t *)mm->sm_priv;
    assert(head != NULL);
    assert(in_tick == 0);
    /* Select the victim */
    /*LAB3 EXERCISE 2: YOUR CODE*/
    //(1)  unlink the  earliest arrival page in front of pra_list_head qeueue
    //(2)  assign the value of *ptr_page to the addr of this page
    list_entry_t *le = head->prev;
    assert(head != le);
    struct Page *p = le2page(le, pra_page_link);
    list_del(le);
    assert(p != NULL);
    *ptr_page = p;
    return 0;
}

答:

  • 现有的swap_manager框架可以支持在ucore中实现此算法,设计方案见扩展练习1
  • PTE_P(Present)和PTE_D(Dirty)位均为0
  • 获取到线性地址所对应的页表项,之后配合掩码使用位运算判断PTE_PPTE_D标志位
  • 1.缺页时换入。2.物理页帧满时换出。

当完成所有练习后,在lab3目录下执行make qemu,应该得到如下结果:

(THU.CST) os is loading ...

Special kernel symbols:
  entry  0xc0100036 (phys)
  etext  0xc0108de8 (phys)
  edata  0xc0125000 (phys)
  end    0xc0126114 (phys)
Kernel executable memory footprint: 153KB
ebp:0xc0121f38 eip:0xc01009ea args:0x00010094 0x00010094 0xc0121f68 0xc01000d3 
    kern/debug/kdebug.c:335: print_stackframe+21
ebp:0xc0121f48 eip:0xc0100ce1 args:0x00000000 0x00000000 0x00000000 0xc0121fb8 
    kern/debug/kmonitor.c:129: mon_backtrace+10
ebp:0xc0121f68 eip:0xc01000d3 args:0x00000000 0xc0121f90 0xffff0000 0xc0121f94 
    kern/init/init.c:59: grade_backtrace2+33
ebp:0xc0121f88 eip:0xc0100101 args:0x00000000 0xffff0000 0xc0121fb4 0x0000002a 
    kern/init/init.c:65: grade_backtrace1+40
ebp:0xc0121fa8 eip:0xc0100121 args:0x00000000 0xc0100036 0xffff0000 0x0000001d 
    kern/init/init.c:71: grade_backtrace0+23
ebp:0xc0121fc8 eip:0xc0100149 args:0xc0108e1c 0xc0108e00 0x00001114 0x00000000 
    kern/init/init.c:76: grade_backtrace+34
ebp:0xc0121ff8 eip:0xc0100087 args:0xc0108fb0 0xc0108fb8 0xc0100c65 0xc0108fd7 
    kern/init/init.c:32: kern_init+80
memory management: default_pmm_manager
e820map:
  memory: 0009fc00, [00000000, 0009fbff], type = 1.
  memory: 00000400, [0009fc00, 0009ffff], type = 2.
  memory: 00010000, [000f0000, 000fffff], type = 2.
  memory: 07ee0000, [00100000, 07fdffff], type = 1.
  memory: 00020000, [07fe0000, 07ffffff], type = 2.
  memory: 00040000, [fffc0000, ffffffff], type = 2.
check_alloc_page() succeeded!
check_pgdir() succeeded!
check_boot_pgdir() succeeded!
-------------------- BEGIN --------------------
PDE(0e0) c0000000-f8000000 38000000 urw
  |-- PTE(38000) c0000000-f8000000 38000000 -rw
PDE(001) fac00000-fb000000 00400000 -rw
  |-- PTE(000e0) faf00000-fafe0000 000e0000 urw
  |-- PTE(00001) fafeb000-fafec000 00001000 -rw
--------------------- END ---------------------
check_vma_struct() succeeded!
page fault at 0x00000100: K/W [no page found].
check_pgfault() succeeded!
check_vmm() succeeded.
ide 0:      10000(sectors), 'QEMU HARDDISK'.
ide 1:     262144(sectors), 'QEMU HARDDISK'.
SWAP: manager = fifo swap manager
BEGIN check_swap: count 1, total 31962
setup Page Table for vaddr 0X1000, so alloc a page
setup Page Table vaddr 0~4MB OVER!
set up init env for check_swap begin!
page fault at 0x00001000: K/W [no page found].
page fault at 0x00002000: K/W [no page found].
page fault at 0x00003000: K/W [no page found].
page fault at 0x00004000: K/W [no page found].
set up init env for check_swap over!
write Virt Page c in fifo_check_swap
write Virt Page a in fifo_check_swap
write Virt Page d in fifo_check_swap
write Virt Page b in fifo_check_swap
write Virt Page e in fifo_check_swap
page fault at 0x00005000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x1000 to disk swap entry 2
write Virt Page b in fifo_check_swap
write Virt Page a in fifo_check_swap
page fault at 0x00001000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x2000 to disk swap entry 3
swap_in: load disk swap entry 2 with swap_page in vadr 0x1000
write Virt Page b in fifo_check_swap
page fault at 0x00002000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x3000 to disk swap entry 4
swap_in: load disk swap entry 3 with swap_page in vadr 0x2000
write Virt Page c in fifo_check_swap
page fault at 0x00003000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x4000 to disk swap entry 5
swap_in: load disk swap entry 4 with swap_page in vadr 0x3000
write Virt Page d in fifo_check_swap
page fault at 0x00004000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x5000 to disk swap entry 6
swap_in: load disk swap entry 5 with swap_page in vadr 0x4000
write Virt Page e in fifo_check_swap
page fault at 0x00005000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x1000 to disk swap entry 2
swap_in: load disk swap entry 6 with swap_page in vadr 0x5000
write Virt Page a in fifo_check_swap
page fault at 0x00001000: K/R [no page found].
swap_out: i 0, store page in vaddr 0x2000 to disk swap entry 3
swap_in: load disk swap entry 2 with swap_page in vadr 0x1000
count is 0, total is 7
check_swap() succeeded!
++ setup timer interrupts
100 ticks
kbd [097] a
kbd [000] 
100 ticks
kbd [098] b
kbd [000] 
kbd [099] c
100 ticks
kbd [000] 
100 ticks
kbd [000] 
kbd [003] 
kbd [000] 
kbd [000] 
100 ticks
qemu-system-i386: terminating on signal 2

执行make grade,应该得到如下结果:

45

Lab 3 完成

扩展练习 Challenge 1:实现识别dirty bit的 extended clock页替换算法(需要编程)

问题解答

  • FIFO的基础上实现swap_out_victim函数即可。
  • 该函数中查找一块可用于换出的物理页,最多只需要遍历三次:

    • 第一次查找 !PTE_A & !PTE_D ,同时重置当前页的PTE_A,为第二次遍历的条件打基础
    • 第二次查找 !PTE_A & !PTE_D , 同时重置当前页的PTE_D,为第三次遍历的条件打基础
    • 第三次查找,肯定能找到
  • 这里需要注意对于PTE_D的操作,若第一次、第二次遍历都找不到符合要求的物理页,则必须对PTE_D进行操作,重置该标志位。还有一点需要注意,在每次修改PTE标志位后,都需要重置TLB缓存

实现后的_extend_clock_swap_out_victim函数代码如下(已加注释):

static int
_extend_clock_swap_out_victim(struct mm_struct *mm, struct Page ** ptr_page, int in_tick)
{
    list_entry_t *head=(list_entry_t*) mm->sm_priv;
        assert(head != NULL);
    assert(in_tick==0);

    // 第一次查找 !PTE_A & !PTE_D,同时重置当前页的PTE_A
    // 第二次查找 !PTE_A & !PTE_D, 同时重置当前页的PTE_D
    // 第三次查找,肯定能找到
    for(int i = 0; i < 3; i++)
    {
        list_entry_t *le = head->prev;
        assert(head!=le);
        while(le != head)
        {
            struct Page *p = le2page(le, pra_page_link);
            pte_t* ptep = get_pte(mm->pgdir, p->pra_vaddr, 0);
            // 如果满足未使用未修改这两个条件,则直接分配
            if(!(*ptep & PTE_A) && !(*ptep & PTE_D))
            {
                list_del(le);
                assert(p !=NULL);
                *ptr_page = p;
                return 0;
            }
            // 如果在第一次查找中,访问到了一个已经使用过的PTE,则标记为未使用。
            if(i == 0)
                *ptep &= ~PTE_A;
            // 如果在第二次查找中,访问到了一个已修改过的PTE,则标记为未修改。
            else if(i == 1)
                *ptep &= ~PTE_D;

            le = le->prev;
            // 遍历了一回,肯定修改了标志位,所以要刷新TLB
            tlb_invalidate(mm->pgdir, le);
        }
    }
    // 按照前面的assert与if,不可能会执行到此处,所以return -1
    return -1;
}

扩展练习 Challenge 2:实现不考虑实现开销和效率的LRU页替换算法(需要编程)

开摆。

Lab 4 内核线程管理

实验目的

  • 了解内核线程创建/执行的管理过程
  • 了解内核线程的切换和基本调度过程

实验内容(操作部分)

实验2/3完成了物理和虚拟内存管理,这给创建内核线程(内核线程是一种特殊的进程)打下了提供内存管理的基础。当一个程序加载到内存中运行时,首先通过ucore OS的内存管理子系统分配合适的空间,然后就需要考虑如何分时使用CPU来“并发”执行多个程序,让每个运行的程序(这里用线程或进程表示)“感到”它们各自拥有“自己”的CPU。

本次实验首先接触的是内核线程的管理。内核线程是一种特殊的进程,内核线程与用户进程的区别有两个:

  • 内核线程只运行在内核态
  • 用户进程会在在用户态和内核态交替运行
  • 所有内核线程共用ucore内核内存空间,不需为每个内核线程维护单独的内存空间
  • 而用户进程需要维护各自的用户内存空间

项目组成

├── boot   
├── kern  
│ ├── debug  
│ ├── driver  
│ ├── fs   
│ ├── init  
│ │ ├── init.c   
│ │ └── ...  
│ ├── libs  
│ │ ├── rb\_tree.c  
│ │ ├── rb\_tree.h  
│ │ └── ...   
│ ├── mm   
│ │ ├── kmalloc.c   
│ │ ├── kmalloc.h   
│ │ ├── memlayout.h   
│ │ ├── pmm.c   
│ │ ├── pmm.h   
│ │ ├── swap.c   
│ │ ├── vmm.c   
│ │ └── ...   
│ ├── process  
│ │ ├── entry.S  
│ │ ├── proc.c   
│ │ ├── proc.h  
│ │ └── switch.S  
│ ├── schedule  
│ │ ├── sched.c  
│ │ └── sched.h  
│ ├── sync  
│ │ └── sync.h  
│ └── trap  
│ ├── trapentry.S  
│ └── ...  
├── libs  
│ ├── hash.c   
│ ├── stdlib.h  
│ ├── unistd.h   
│ └── ...  
├── Makefile  
└── tools

相对与实验三,实验四中主要改动如下:

  • kern/process/ (新增进程管理相关文件)

    • proc.[ch]:新增:实现进程、线程相关功能,包括:创建进程/线程,初始化进程/线程,处理进程/线程退出等功能
    • entry.S:新增:内核线程入口函数kernel_thread_entry的实现
    • switch.S:新增:上下文切换,利用堆栈保存、恢复进程上下文
  • kern/init/

    • init.c:修改:完成进程系统初始化,并在内核初始化后切入idle进程
  • kern/mm/ (基本上与本次实验没有太直接的联系,了解kmalloc和kfree如何使用即可)

    • kmalloc.[ch]:新增:定义和实现了新的kmalloc/kfree函数。具体实现是基于slab分配的简化算法 (只要求会调用这两个函数即可)
    • memlayout.h:增加slab物理内存分配相关的定义与宏 (可不用理会)。
    • pmm.[ch]:修改:在pmm.c中添加了调用kmalloc_init函数,取消了老的kmalloc/kfree的实现;在pmm.h中取消了老的kmalloc/kfree的定义
    • swap.c:修改:取消了用于check的Line 185的执行
    • vmm.c:修改:调用新的kmalloc/kfree
  • kern/trap/

    • trapentry.S:增加了汇编写的函数forkrets,用于do_fork调用的返回处理。
  • kern/schedule/

    • sched.[ch]:新增:实现FIFO策略的进程调度
  • kern/libs

    • rb_tree.[ch]:新增:实现红黑树,被slab分配的简化算法使用(可不用理会)

编译执行

编译并运行代码的命令如下:

make
make qemu

则可以得到如下的显示内容(仅供参考,不是标准答案输出)

(THU.CST) os is loading ...

Special kernel symbols:
  entry  0xc010002a (phys)
  etext  0xc010a708 (phys)
  edata  0xc0127ae0 (phys)
  end    0xc012ad58 (phys)

...

++ setup timer interrupts
this initproc, pid = 1, name = "init"
To U: "Hello world!!".
To U: "en.., Bye, Bye. :)"
kernel panic at kern/process/proc.c:354:
    process exit!!.

Welcome to the kernel debug monitor!!
Type 'help' for a list of commands.
K> qemu: terminating on signal 2

实验执行流程概述

lab2和lab3完成了对内存的虚拟化,但整个控制流还是一条线串行执行。lab4将在此基础上进行CPU的虚拟化,即让ucore实现分时共享CPU,实现多条控制流能够并发执行。从某种程度上,我们可以把控制流看作是一个内核线程。本次实验将首先接触的是内核线程的管理。内核线程是一种特殊的进程,内核线程与用户进程的区别有两个:内核线程只运行在内核态而用户进程会在用户态和内核态交替运行;所有内核线程直接使用共同的ucore内核内存空间,不需为每个内核线程维护单独的内存空间而用户进程需要维护各自的用户内存空间。从内存空间占用情况这个角度上看,我们可以把线程看作是一种共享内存空间的轻量级进程。

为了实现内核线程,需要设计管理线程的数据结构,即进程控制块(在这里也可叫做线程控制块)。如果要让内核线程运行,我们首先要创建内核线程对应的进程控制块,还需把这些进程控制块通过链表连在一起,便于随时进行插入,删除和查找操作等进程管理事务。这个链表就是进程控制块链表。然后在通过调度器(scheduler)来让不同的内核线程在不同的时间段占用CPU执行,实现对CPU的分时共享。那lab4中是如何一步一步实现这个过程的呢?

我们还是从lab4/kern/init/init.c中的kern_init函数入手分析。在kern_init函数中,当完成虚拟内存的初始化工作后,就调用了proc_init函数,这个函数完成了idleproc内核线程和initproc内核线程的创建或复制工作,这也是本次实验要完成的练习。idleproc内核线程的工作就是不停地查询,看是否有其他内核线程可以执行了,如果有,马上让调度器选择那个内核线程执行(请参考cpu_idle函数的实现)。所以idleproc内核线程是在ucore操作系统没有其他内核线程可执行的情况下才会被调用。接着就是调用kernel_thread函数来创建initproc内核线程。initproc内核线程的工作就是显示“Hello World”,表明自己存在且能正常工作了。

调度器会在特定的调度点上执行调度,完成进程切换。在lab4中,这个调度点就一处,即在cpu_idle函数中,此函数如果发现当前进程(也就是idleproc)的need_resched置为1(在初始化idleproc的进程控制块时就置为1了),则调用schedule函数,完成进程调度和进程切换。进程调度的过程其实比较简单,就是在进程控制块链表中查找到一个“合适”的内核线程,所谓“合适”就是指内核线程处于“PROC_RUNNABLE”状态。在接下来的switch_to函数(在后续有详细分析,有一定难度,需深入了解一下)完成具体的进程切换过程。一旦切换成功,那么initproc内核线程就可以通过显示字符串来表明本次实验成功。

接下来将主要介绍了进程创建所需的重要数据结构--进程控制块 proc_struct,以及ucore创建并执行内核线程idleproc和initproc的两种不同方式,特别是创建initproc的方式将被延续到实验五中,扩展为创建用户进程的主要方式。另外,还初步涉及了进程调度(实验六涉及并会扩展)和进程切换内容。

练习0:填写已有实验

本实验依赖实验1/2/3。请把你做的实验1/2/3的代码填入本实验中代码中有“LAB1”,“LAB2”,“LAB3”的注释相应部分。

问题解答

运行meld,选择lab3lab4目录进行比较,根据图形提示将之前修改的代码复制进lab4的代码中。

46

lab1中修改过的文件有:

  • kern/debug/kdebug.c
  • kern/trap/trap.c

lab2中修改过的文件有:

  • kern/mm/default_pmm.c
  • kern/mm/pmm.c

lab3中修改过的文件有:

  • kern/mm/vmm.c
  • kern/mm/swap_fifo.c

练习1:分配并初始化一个进程控制块(需要编码)

alloc_proc函数(位于kern/process/proc.c中)负责分配并返回一个新的struct proc_struct结构,用于存储新建立的内核线程的管理信息。ucore需要对这个结构进行最基本的初始化,你需要完成这个初始化过程。

提示:alloc_proc函数的实现中,需要初始化的proc_struct结构中的成员变量至少包括:state/pid/runs/kstack/need_resched/parent/mm/context/tf/cr3/flags/name

请在实验报告中简要说明你的设计实现过程。请回答如下问题:

  • 请说明proc_structstruct context contextstruct trapframe *tf成员变量含义和在本实验中的作用是什么?(提示:通过看代码和编程调试可以判断出来)

问题解答

alloc_proc函数的实现如下:

// alloc_proc - alloc a proc_struct and init all fields of proc_struct
static struct proc_struct *
alloc_proc(void)
{
    struct proc_struct *proc = kmalloc(sizeof(struct proc_struct));
    if (proc != NULL)
    {
        //LAB4:EXERCISE1 YOUR CODE
        /*
        * below fields in proc_struct need to be initialized
        *       enum proc_state state;                      // Process state
        *       int pid;                                    // Process ID
        *       int runs;                                   // the running times of Proces
        *       uintptr_t kstack;                           // Process kernel stack
        *       volatile bool need_resched;                 // bool value: need to be rescheduled to release CPU?
        *       struct proc_struct *parent;                 // the parent process
        *       struct mm_struct *mm;                       // Process's memory management field
        *       struct context context;                     // Switch here to run process
        *       struct trapframe *tf;                       // Trap frame for current interrupt
        *       uintptr_t cr3;                              // CR3 register: the base addr of Page Directroy Table(PDT)
        *       uint32_t flags;                             // Process flag
        *       char name[PROC_NAME_LEN + 1];               // Process name
        */
        proc->state = PROC_UNINIT;                           //初始化状态
        proc->pid = -1;                                      //初始化pid
        proc->runs = 0;                                      //初始化运行时
        proc->kstack = 0;                                    //初始化内核栈
        proc->need_resched = 0;                              //设置进程是否需要重排以释放CPU
        proc->parent = NULL;                                 //父进程
        proc->mm = NULL;                                     //进程的内存管理域
        memset(&(proc->context), 0, sizeof(struct context)); //初始化上下文
        proc->tf = NULL;                                     //初始化中断帧
        proc->cr3 = boot_cr3;                                // 内核线程页表使用的是boot_cr3
        proc->flags = 0;                                     //设置进程标识
        memset(proc->name, 0, PROC_NAME_LEN);                //初始化进程名称
    }
    return proc;
}
  • struct context context:储存进程当前状态,用于进程切换中上下文的保存与恢复。需要注意的是,与trapframe所保存的用户态上下文不同,context保存的是线程的当前上下文。这个上下文可能是执行用户代码时的上下文,也可能是执行内核代码时的上下文。在uCore中,所有的进程在内核中是相对独立的,使用context保存寄存器的目的就在于在内核态中能够进行上下文之间的切换。
  • struct trapframe* tf:中断帧的指针。总是指向内核栈的某个位置:当进程从用户空间跳到内核空间时,中断帧记录了进程在被中断前的状态。当内核需要跳回用户空间时,需要调整中断帧以恢复让进程继续执行的各寄存器值。

练习2:为新创建的内核线程分配资源(需要编码)

创建一个内核线程需要分配和设置好很多资源。kernel_thread函数通过调用do_fork函数完成具体内核线程的创建工作。do_kernel函数会调用alloc_proc函数来分配并初始化一个进程控制块,但alloc_proc只是找到了一小块内存用以记录进程的必要信息,并没有实际分配这些资源。ucore一般通过do_fork实际创建新的内核线程。do_fork的作用是,创建当前内核线程的一个副本,它们的执行上下文、代码、数据都一样,但是存储位置不同。在这个过程中,需要给新内核线程分配资源,并且复制原进程的状态。你需要完成在kern/process/proc.c中的do_fork函数中的处理过程。

它的大致执行步骤包括:

  • 调用alloc_proc,首先获得一块用户信息块
  • 为进程分配一个内核栈
  • 复制原进程的内存管理信息到新进程(但内核线程不必做此事)
  • 复制原进程上下文到新进程
  • 将新进程添加到进程列表
  • 唤醒新进程
  • 返回新进程号

请在实验报告中简要说明你的设计实现过程。请回答如下问题:

  • 请说明ucore是否做到给每个新fork的线程一个唯一的id?请说明你的分析和理由。

问题解答

do_fork函数的实现如下(已加注释):

/* do_fork -     parent process for a new child process
 * @clone_flags: used to guide how to clone the child process
 * @stack:       the parent's user stack pointer. if stack==0, It means to fork a kernel thread.
 * @tf:          the trapframe info, which will be copied to child process's proc->tf
 */
int do_fork(uint32_t clone_flags, uintptr_t stack, struct trapframe *tf)
{
    int ret = -E_NO_FREE_PROC;
    struct proc_struct *proc;
    if (nr_process >= MAX_PROCESS)
    {
        goto fork_out;
    }
    ret = -E_NO_MEM;
    //LAB4:EXERCISE2 YOUR CODE
    /*
     * Some Useful MACROs, Functions and DEFINEs, you can use them in below implementation.
     * MACROs or Functions:
     *   alloc_proc:   create a proc struct and init fields (lab4:exercise1)
     *   setup_kstack: alloc pages with size KSTACKPAGE as process kernel stack
     *   copy_mm:      process "proc" duplicate OR share process "current"'s mm according clone_flags
     *                 if clone_flags & CLONE_VM, then "share" ; else "duplicate"
     *   copy_thread:  setup the trapframe on the  process's kernel stack top and
     *                 setup the kernel entry point and stack of process
     *   hash_proc:    add proc into proc hash_list
     *   get_pid:      alloc a unique pid for process
     *   wakeup_proc:  set proc->state = PROC_RUNNABLE
     * VARIABLES:
     *   proc_list:    the process set's list
     *   nr_process:   the number of process set
     */

    //    1. call alloc_proc to allocate a proc_struct
    //    2. call setup_kstack to allocate a kernel stack for child process
    //    3. call copy_mm to dup OR share mm according clone_flag
    //    4. call copy_thread to setup tf & context in proc_struct
    //    5. insert proc_struct into hash_list && proc_list
    //    6. call wakeup_proc to make the new child process RUNNABLE
    //    7. set ret vaule using child proc's pid

    // 分配进程控制块
    if ((proc = alloc_proc()) == NULL)
        goto fork_out;

    // 设置子进程的父进程为当前进程
    proc->parent = current;

    // 分配内核栈
    if (setup_kstack(proc) != 0)
        goto bad_fork_cleanup_proc;

    // 根据clone_flags的指导进行虚拟页数据的复制
    if (copy_mm(clone_flags, proc) != 0)
        goto bad_fork_cleanup_kstack;

    // 复制线程的状态,包括寄存器上下文等
    copy_thread(proc, stack, tf);

    // 将子进程的进程控制块添加进hash list
    // 并且不能让中断处理程序打断这一步操作
    bool intr_flag;
    local_intr_save(intr_flag);
    {
        proc->pid = get_pid();
        hash_proc(proc);
        list_add(&proc_list, &(proc->list_link));
        nr_process++;
    }
    local_intr_restore(intr_flag);

    // 唤醒子进程
    wakeup_proc(proc);

    // 返回子进程的pid
    ret = proc->pid;

fork_out:
    return ret;

bad_fork_cleanup_kstack:
    put_kstack(proc);
bad_fork_cleanup_proc:
    kfree(proc);
    goto fork_out;
}

ucore可以做到给每个新fork的线程唯一的一个ID,首先看get_pid函数的代码:

// get_pid - alloc a unique pid for process
static int
get_pid(void)
{
    static_assert(MAX_PID > MAX_PROCESS);
    struct proc_struct *proc;
    list_entry_t *list = &proc_list, *le;
    static int next_safe = MAX_PID, last_pid = MAX_PID;
    if (++last_pid >= MAX_PID)
    {
        last_pid = 1;
        goto inside;
    }
    if (last_pid >= next_safe)
    {
    inside:
        next_safe = MAX_PID;
    repeat:
        le = list;
        while ((le = list_next(le)) != list)
        {
            proc = le2proc(le, list_link);
            if (proc->pid == last_pid)
            {
                if (++last_pid >= next_safe)
                {
                    if (last_pid >= MAX_PID)
                    {
                        last_pid = 1;
                    }
                    next_safe = MAX_PID;
                    goto repeat;
                }
            }
            else if (proc->pid > last_pid && next_safe > proc->pid)
            {
                next_safe = proc->pid;
            }
        }
    }
    return last_pid;
}

上述代码实际上是构建了一个区间,通过确认没有进程的id在这个区间内部,来分配一个合适的pid。第一句assert可以保证进程数一定不会多于可以分配的进程标识号的数目。接下来,函数将扫描所有的进程,找到一个当前没被使用的进程号,存储在last_pid中,作为新进程的进程号。具体来说,循环扫描每一个当前进程,当一个现有的进程号和last_pid相等时,则将last_pid+1;当现有的进程号大于last_pid时,则意味着在已经扫描的进程中[last_pid, min(next_safe, proc->pid)]这段进程号尚未被占用,继续扫描。这样可以保证返回的新进程号一定没有被占用,即具有唯一的id。

练习3:阅读代码,理解 proc_run 函数和它调用的函数如何完成进程切换的。(无编码工作)

请在实验报告中简要说明你对proc_run函数的分析,并回答如下问题:

  • 在本实验的执行过程中,创建且运行了几个内核线程?
  • 语句local_intr_save(intr_flag);....local_intr_restore(intr_flag);在这里有何作用?请说明理由。

问题解答

proc_run函数分析如下:

// proc_run - make process "proc" running on cpu
// NOTE: before call switch_to, should load  base addr of "proc"'s new PDT
void
proc_run(struct proc_struct *proc) {
// 如果要调度的进程不是当前进程的话进行如下操作
    if (proc != current) {
        bool intr_flag;
        struct proc_struct *prev = current, *next = proc;
// 关闭中断,防止进程调度过程中发生其他中断导致嵌套的进程调度
        local_intr_save(intr_flag);
        {
// 当前进程设为待调度的进程
            current = proc;
// 加载待调度进程的内核栈基地址和页表基地址
            load_esp0(next->kstack + KSTACKSIZE);
            lcr3(next->cr3);
// 保存原线程的寄存器并恢复待调度线程的寄存器
            switch_to(&(prev->context), &(next->context));
        }
// 恢复中断
        local_intr_restore(intr_flag);
    }
}

保存寄存器和恢复待调度进程的寄存器部分代码在switch_to中:

.text
.globl switch_to
switch_to:                      # switch_to(from, to)
    # save from's registers
    movl 4(%esp), %eax          # 获取当前进程的context结构地址
    popl 0(%eax)                # 将eip保存至当前进程的context结构
    movl %esp, 4(%eax)          # 将esp保存至当前进程的context结构
    movl %ebx, 8(%eax)          # 将ebx保存至当前进程的context结构
    movl %ecx, 12(%eax)         # 将ecx保存至当前进程的context结构
    movl %edx, 16(%eax)         # 将edx保存至当前进程的context结构
    movl %esi, 20(%eax)         # 将esi保存至当前进程的context结构
    movl %edi, 24(%eax)         # 将edi保存至当前进程的context结构
    movl %ebp, 28(%eax)         # 将ebp保存至当前进程的context结构

    # restore to's registers
    movl 4(%esp), %eax          # 获取下一个进程的context结构地址
                                # 需要注意的是,其地址不是8(%esp),因为之前已经pop过一次。
    movl 28(%eax), %ebp         # 恢复ebp至下一个进程的context结构
    movl 24(%eax), %edi         # 恢复edi至下一个进程的context结构
    movl 20(%eax), %esi         # 恢复esi至下一个进程的context结构
    movl 16(%eax), %edx         # 恢复edx至下一个进程的context结构
    movl 12(%eax), %ecx         # 恢复ecx至下一个进程的context结构
    movl 8(%eax), %ebx          # 恢复ebx至下一个进程的context结构
    movl 4(%eax), %esp          # 恢复esp至下一个进程的context结构
    pushl 0(%eax)               # 插入下一个进程的eip,以便于ret到下个进程的代码位置。
    ret

本实验在执行过程中,创建且运行了两个内核线程:

  • idleproc:ucore的第一个内核线程,完成内核中各个子系统的初始化,之后立即调度,执行其他进程。
  • initproc:"hello world"线程。

语句 local_intr_save(intr_flag);....local_intr_restore(intr_flag);的作用是:

在进程调度开始前关闭中断,在结束进程调度后开启中断,以防止在进程调度过程中产生中断导致进程调度的嵌套,使得这两行代码之间的代码块形成原子操作,关键的代码不会被打断,从而避免引起一些未预料到的错误,避免条件竞争。

当完成所有练习后,在lab4目录下执行make qemu,应该得到如下结果:

(THU.CST) os is loading ...

Special kernel symbols:
  entry  0xc0100036 (phys)
  etext  0xc0109ed1 (phys)
  edata  0xc012b000 (phys)
  end    0xc012e154 (phys)
Kernel executable memory footprint: 185KB
memory management: default_pmm_manager
e820map:
  memory: 0009fc00, [00000000, 0009fbff], type = 1.
  memory: 00000400, [0009fc00, 0009ffff], type = 2.
  memory: 00010000, [000f0000, 000fffff], type = 2.
  memory: 07ee0000, [00100000, 07fdffff], type = 1.
  memory: 00020000, [07fe0000, 07ffffff], type = 2.
  memory: 00040000, [fffc0000, ffffffff], type = 2.
check_alloc_page() succeeded!
check_pgdir() succeeded!
check_boot_pgdir() succeeded!
-------------------- BEGIN --------------------
PDE(0e0) c0000000-f8000000 38000000 urw
  |-- PTE(38000) c0000000-f8000000 38000000 -rw
PDE(001) fac00000-fb000000 00400000 -rw
  |-- PTE(000e0) faf00000-fafe0000 000e0000 urw
  |-- PTE(00001) fafeb000-fafec000 00001000 -rw
--------------------- END ---------------------
use SLOB allocator
kmalloc_init() succeeded!
check_vma_struct() succeeded!
page fault at 0x00000100: K/W [no page found].
check_pgfault() succeeded!
check_vmm() succeeded.
ide 0:      10000(sectors), 'QEMU HARDDISK'.
ide 1:     262144(sectors), 'QEMU HARDDISK'.
SWAP: manager = fifo swap manager
BEGIN check_swap: count 1, total 31951
setup Page Table for vaddr 0X1000, so alloc a page
setup Page Table vaddr 0~4MB OVER!
set up init env for check_swap begin!
page fault at 0x00001000: K/W [no page found].
page fault at 0x00002000: K/W [no page found].
page fault at 0x00003000: K/W [no page found].
page fault at 0x00004000: K/W [no page found].
set up init env for check_swap over!
write Virt Page c in fifo_check_swap
write Virt Page a in fifo_check_swap
write Virt Page d in fifo_check_swap
write Virt Page b in fifo_check_swap
write Virt Page e in fifo_check_swap
page fault at 0x00005000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x1000 to disk swap entry 2
write Virt Page b in fifo_check_swap
write Virt Page a in fifo_check_swap
page fault at 0x00001000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x2000 to disk swap entry 3
swap_in: load disk swap entry 2 with swap_page in vadr 0x1000
write Virt Page b in fifo_check_swap
page fault at 0x00002000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x3000 to disk swap entry 4
swap_in: load disk swap entry 3 with swap_page in vadr 0x2000
write Virt Page c in fifo_check_swap
page fault at 0x00003000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x4000 to disk swap entry 5
swap_in: load disk swap entry 4 with swap_page in vadr 0x3000
write Virt Page d in fifo_check_swap
page fault at 0x00004000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x5000 to disk swap entry 6
swap_in: load disk swap entry 5 with swap_page in vadr 0x4000
write Virt Page e in fifo_check_swap
page fault at 0x00005000: K/W [no page found].
swap_out: i 0, store page in vaddr 0x1000 to disk swap entry 2
swap_in: load disk swap entry 6 with swap_page in vadr 0x5000
write Virt Page a in fifo_check_swap
page fault at 0x00001000: K/R [no page found].
swap_out: i 0, store page in vaddr 0x2000 to disk swap entry 3
swap_in: load disk swap entry 2 with swap_page in vadr 0x1000
count is 0, total is 5
check_swap() succeeded!
++ setup timer interrupts
this initproc, pid = 1, name = "init"
To U: "Hello world!!".
To U: "en.., Bye, Bye. :)"
kernel panic at kern/process/proc.c:389:
    process exit!!.

stack trackback:
Welcome to the kernel debug monitor!!
Type 'help' for a list of commands.
K> 

执行make grade,应该得到如下结果:

47

Lab 4 完成

扩展练习Challenge:实现支持任意大小的内存分配算法

这不是本实验的内容,其实是上一次实验内存的扩展,但考虑到现在的slab算法比较复杂,有必要实现一个比较简单的任意大小内存分配算法。可参考本实验中的slab如何调用基于页的内存分配算法(注意,不是要你关注slab的具体实现)来实现first-fit/best-fit/worst-fit/buddy等支持任意大小的内存分配算法。

下面是相关的Linux实现文档,供参考:SLOBSLAB

开摆。


暂无留言

发表留言