UCore学习笔记

lab1

练习1：理解make的执行过程

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

在此练习中，大家需要通过静态分析代码来了解：

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

以下代码摘自make命令的输出。

+ cc kern/init/init.c
gcc -Ikern/init/ -march=i686 -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
#编译kern/init/init.c 输出obj/kern/init/init.o
+ cc kern/libs/stdio.c
gcc -Ikern/libs/ -march=i686 -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/ -march=i686 -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
#编译kern/libs/stdio.c readlin.c
#输出obj/kern/libs/stdio.o readline.o
+ cc kern/debug/panic.c
gcc -Ikern/debug/ -march=i686 -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
+ cc kern/debug/kdebug.c
gcc -Ikern/debug/ -march=i686 -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
+ cc kern/debug/kmonitor.c
gcc -Ikern/debug/ -march=i686 -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
#编译kern/debug/panic.c kdebug.c kmonitor.c
#输出obj/kern/debug/panic.o kdebug.o kmonitor.o
+ cc kern/driver/clock.c
gcc -Ikern/driver/ -march=i686 -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/ -march=i686 -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/ -march=i686 -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
+ cc kern/driver/intr.c
gcc -Ikern/driver/ -march=i686 -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
#编译kern/driver/clock.c console.c  picirq.c intr.c
#输出obj/kern/driver/clock.o console.o picirq.o intr.o
+ cc kern/trap/trap.c
gcc -Ikern/trap/ -march=i686 -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
+ cc kern/trap/vectors.S
gcc -Ikern/trap/ -march=i686 -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/ -march=i686 -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
#编译kern/trap/文件夹下的trap.c vectors.S trapentry.S
#生成obj/kern/trap/trap.o vectors.o trapentry.o

+ cc kern/mm/pmm.c
gcc -Ikern/mm/ -march=i686 -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
#编译kern/mm/pmm.c
#生成obj/kern/mm/pmm.o

+ cc libs/string.c
gcc -Ilibs/ -march=i686 -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/ -march=i686 -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/  -c libs/printfmt.c -o obj/libs/printfmt.o
#编译libs/string.c printfmt.c
#生成libs/printfmt.c

+ 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
#链接成可执行文件bin/kernel

+ cc boot/bootasm.S
gcc -Iboot/ -march=i686 -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Os -nostdinc -c boot/bootasm.S -o obj/boot/bootasm.o
+ cc boot/bootmain.c
gcc -Iboot/ -march=i686 -fno-builtin -fno-PIC -Wall -ggdb -m32 -gstabs -nostdinc  -fno-stack-protector -Ilibs/ -Os -nostdinc -c boot/bootmain.c -o obj/boot/bootmain.o
#编译boot/bootasm.S bootmain.c
#输出obj/boot/bootasm.o bootmain.o

+ cc tools/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
#编译tools/sign.c 生产sign.o 转化为库文件sign

+ 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
#链接生成二进制文件bin/bootblock

'obj/bootblock.out' size: 492 bytes
build 512 bytes boot sector: 'bin/bootblock' success!
#obj/bootblock.out大小为492字节，提示构建512字节的bin/bootblock文件成功

#先解释一下dd命令
#dd是linux下强大的数据复制工具。
#if = FILE 表示从FILE中读取数据。
#of = FILE 表示写入数据到FILE中。
#ibs = BYETS 表示读取数据时，一次性读BYTES大小的块。不指定默认512字节。
#obs = BYETS 表示写入数据时，一次性写BYTES大小的块。不指定默认512字节。
#count = N 表示总共读取或者写入N * ibs(obs)字节数的数据。
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.0195807 s, 261 MB/s
#从/dev/zero文件(“零”设备，无限提供0x00)中读取数据
#写入到bin/ucore.img文件中
#count=10000表示读取10000*512字节的数据
#即ucore.img大小为5,120,000字节。

#拓展
#/dev/null “空设备”，任何输入到这个设备的数据都被丢弃。
#/dev/random 随机数设备，依赖系统中断不断产生随机字节流。产生速度较慢，但随机性好。
#/dev/urandom 不依赖系统中断，速度快，随机性较低。

#conv = notrunc 表示如果目的文件已经存在，那么不要截断文件内容。默认会截断成0字节大小。一般配合oflag = append使用，不截断并且以追加的方式写入数据。
dd if=bin/bootblock of=bin/ucore.img conv=notrunc
1+0 records in
1+0 records out
512 bytes copied, 5.4334e-05 s, 9.4 MB/s
#将bootblock写入ucore.img的第一个块

#seek = 1 表示从输出文件ucore.img跳过一个块再开始复制。
#skip = blocks 表示从输入文件跳过blocks个块再开始复制。
dd if=bin/kernel of=bin/ucore.img seek=1 conv=notrunc
146+1 records in
146+1 records out
74816 bytes (75 kB, 73 KiB) copied, 0.000374306 s, 200 MB/s
#将kernel复制到ucore.img中。

关于makefile

makefile很复杂，后面有空再继续详细分析（偷懒）

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

熟悉使用qemu和gdb进行的调试工作，我们进行如下的小练习：

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

qemu和gcc的使用不是很难，这里就掠过了，主要说一下x86加电启动的原理。

i8086的启动过程

i8086有20根地址总线，实模式下内存空间布局如下：

起始	结束	大小	用途
0xFFFF0	0xFFFFF	16B	BIOS入口地址，此地址也属于BIOS代码，同样属于顶部64KB。这里的16字节的内容是长跳转指令jmp F000:E05B
0xF0000	0xFFFEF	64KB-16B	BIOS范围是F0000～FFFFF共64KB，最上面的16字节是BIOS入口地址。
0xC8000	0xEFFFF	160KB	映射硬件适配器的ROM或者内存映射式I/O。
0xC0000	0xC7FFF	32KB	显示适配器BIOS。
0xB8000	0xBFFFF	32KB	用于文本模式显示适配器。
0xB0000	0xB7FFF	32KB	用于黑白显示适配器。
0xA0000	0xAFFFF	64KB	用于彩色显示适配器。
0x9FC00	0x9FFFF	1KB	EBDA(Extended BIOS Data Area)扩展BIOS数据区。
0x07E00	0x9FBFF	622080B约608KB	可用区域。(可用于加载GDT)
0x07C00	0x07DFF	512B	MBR被BIOS加载到此处，共512字节。
0x00500	0x07BFF	30464B约30KB	可用区域。
0x00400	0x004FF	256B	BIOS Data Area(BIOS数据区)。
0x00000	0x003FF	1KB	Interrupt Vector Table(中断向量表)。

• 从低地址向高地址看，0到0x9FFFF为DRAM，有640KB。

• 顶部的0xF0000到0xFFFFF为ROM，有64KB，储存BIOS代码。

• PC加电后，CS寄存器初始化为0xF000，IP寄存器初始化为0xFFF0，于是CPU执行的第一条指令的地址是CS:IP = 0xFFFF0，是一条跳转指令jmp F000:E05B。开始BIOS执行过程。

• BIOS主要做两件事：初始化硬件和建立中断向量表。建立中断向量表，其他程序就能通过中断调用BIOS已经实现的硬件控制函数。

• BIOS的最后一项工作是校验0盘0道1扇区的内容，如果BIOS发现这个扇区最后两个字节是0x55AA，那么BIOS就会将这个扇区的内容加载到内存0x7C00处，用的是命令jmp 0:7C00。之后的工作便交给BOOTLoader(MBR)。

拓展

到了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。

练习3：BootLoader进入保护模式的过程

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

提示：需要阅读**小节“保护模式和分段机制”**和lab1/boot/bootasm.S源码，了解如何从实模式切换到保护模式，需要了解：

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

预备知识

控制寄存器

CR0是处理器内部的控制寄存器（Control Register, CR），之所以有0后缀，是因为还存在CR1，CR2...CR8。

CR0是一个32位寄存器，包含一系列用于控制处理器操作模式和运行状态的标志位。

它的最低位是保护模式允许位（Protection Enable, PE）。

当该位为1时，处理器进入保护模式。

段描述符和全局描述符表

和一个段有关的信息需要8个字节（64）位来描述，所以称为段描述符（Segemnt Descriptor）。每个段需要一个描述符，为了存放这些描述符，需要在内存中开辟一段空间。这段空间里，所有的描述符都是挨在一起，集中存放的，这就构成一个段描述符表。

主要的段描述符表是全局描述符表（Global Descriptor Table, GDT）。所谓全局，意味着是为整个软硬件系统服务的。在进入保护模式前，必须定义全局描述符表。

由于GDT的界限是16位的，所以该表最大2¹⁶字节，也就是65536字节（64KB）。而一个段描述符大小8字节，故最多可以定义2¹³也就是8192个段描述符。

处理器内部有一个48位的寄存器，称为全局描述符表寄存器（GDTR），用于跟踪全局描述符表。寄存器分为32位的线性地址和16位的边界。32位的线性基地址保存的是全局描述符表在内存中的起始地址，16位边界部分保存的是全局描述符表的边界（界限），在数值上等于表的大小减一。

处理器规定，GDT描述符表的0号描述符必须是空描述符，或者叫哑描述符或NULL描述符。

段选择子和描述符高速缓存器

8086处理器是16位的，有4个段寄存器：CS、DS、ES、SS。在32位的x86处理器中，又增加了2个段寄存器FS和GS 。

而在32位处理器中，这6个段寄存器又分为可见部分和隐藏部分。如下图：

当处理器位于保护模式时，前16位和8086相同，按照传统的方式寻址1MB的内存，使用方法也没有变化。

每个寄存器的隐藏部分，称为段描述符高速缓存器。用来存放段线性基地址、段界限和段属性。

在8086处理器下，访问内存采用的是逻辑地址，即段寄存器中保存的地址左移4位，再加上偏移地址。

但是在32位处理器的实模式下，则是先将段地址左移4位，然后传送到段描述符高速缓存器。此后就一直使用描述符高速缓存器对应的低20位作为段地址。

引用一个段，就是执行将段地址传送到段寄存器的指令。如jump 0xf000:0x5000。

通常代码段的修改使用转移和调用指令进行的。而数据段则是采用中间寄存器，如：

mov ax,0x2000
mov ds,ax

只要DS段寄存器内容没有改变，以后每次访问内存都是直接使用DS描述符高速缓存器中的内容。

在32位处理器的实模式下，只能向段寄存器传送16位的逻辑地址（此时处理器不把它看作描述符选择子），所以此时处理器仍然只能访问1MB内存。也就是说，在实模式下，段寄存器对应的描述符高速缓存器的内容仅低20位有效，高12位全零。

在保护模式下，这6个段寄存器叫做段选择器，同时内存访问方式也发生了改变。

此时传送到段选择器的内容不是逻辑段地址，而是段描述符在描述符表中的索引号。

在保护模式下访问一个段时，传送到段选择器的是段选择子。段选择子由三部分组成：

其中

• 高13位(15~3)是描述符索引号。正好可以与GDT中$2^{13}$也就是8192个段描述符一一对应。

• TI表示描述符表指示器。TI=0表示描述符在GDT中；TI=1表示描述符在LDT中。

• 对数据段来说，低两位RPL是请求特权级。对代码段来说，第两位是由CPU维护的当前特权字段（Current Privilege Level， CPL）。

由于GDT的线性基地址在GDTR中，而每个描述符大小是8个字节。因此，描述符的表内偏移地址是描述符索引号乘以8。

所以当每次处理器遇到改变段选择器的值的指令时（比如pop、mov、jmp、call、iret、retf），就根据指令中的索引号乘以8作为偏移地址，然后与GDTR中的线性地址相加，来得到访问GDT的地址。若一切正常（比如没有超出GDT的界限），就把找到的段描述符加载到不可见的描述符高速缓存部分。

A20地址线

进入保护模式之前，还要处理第21根地址线，编号为A20哑描述符或NULL描述符。

为了让实模式下的最大内存地址0xfffff加一后回绕到0x00000而不是变成0x100000，需要将A20地址线恒置0。

80286时代，IBM公司使用一个与门来控制第21根地址线A20。这个与门的端口号是0x60。向该端口写入数据时，若第1为1，那么该与门其中一个输入就是1。

从80486开始，处理器本身有了A20M#引脚，意思是A20屏蔽（A20 Mask），它是低电平有效的。

输入输出控制器集中芯片ICH的处理器接口部分，有一个用于兼容老式设备的端口0x92，它的第7～2位保留未使用。0号位叫INIT_NOW，意思是“现在初始化”，用于初始化处理器。

当它从0跳变到1时，ICH芯片会使处理器的INIT#引脚电平变低（有效），并保持至少16个PCI时钟周期。也就是说，向这个端口写1，将会导致处理器复位，计算机重启。

0x92端口的1号位用于控制A20，叫做替代的A20门控制（Alternate A20 Gate, ALT_A20_GATE）,它与来自端口0x60键盘控制器的A20控制线一起，通过或门连接到处理器的A20M#引脚。由于速度很快，又称Fast A20。

当INIT_NOW从0跳变到1时，ALT_A20_GATE置1，也就是说计算机启动时，第21根地址线是自动启用的。

端口0x92是可读写的，所以要先从该端口读出原数据，将第2位修改为1，然后再写入该端口，这样A20号地址线就启用了。

代码分析

bootasm.S

代码的第8、9行：

.set PROT_MODE_CSEG,        0x8                     # kernel code segment selector
.set PROT_MODE_DSEG,        0x10                    # kernel data segment selector
.set CR0_PE_ON,             0x1                     # protected mode enable flag

• 首先是保护模式下代码段的设置：

  0x8 = 00001 0 00

  所以代码段选择子选择的是1号段描述符（因为0号是空描述符）。

• 数据段的设置同理：

  0x10 = 00010 0 00

  数据段选择子选择的是2号段描述符。

• 紧接着设置CR0寄存器的保护模式使能位（PE）。

代码的第13~17行：

.globl start
start:
.code16                                             # Assemble for 16-bit mode
    cli                                             # Disable interrupts
    cld                                             # String operations increment

.globl使得链接程序(ld)能够看到后面紧跟着的标签，这里是start，所以在这里用来标记程序的入口点标号。汇编器就会在链接时查找文件中start符号代表的地址，把它设置为整个程序的入口。

start:标号则告诉汇编器，这里是程序入口点，汇编器把它标记的指令作为执行的第一条指令，也就是.code16。

.code16告诉编译器这里应该生成16位的指令。

cli用来禁止中断的发生。

cld则让指令的地址以递增的形式变化。

代码的第19~23行：

    # 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

首先将%ax寄存器与自身异或，数据清零。

然后将分别将数据段寄存器、附加段寄存器、堆栈段寄存器分别清零。

代码第29~35行：

seta20.1:
    inb $0x64, %al                        # Wait for not busy(8042 input buffer empty).
    testb $0x2, %al
    jnz seta20.1

    movb $0xd1, %al                       # 0xd1 -> port 0x64
    outb %al, $0x64                       # 0xd1 means: write data to 8042's P2 port

首先简单说一下ps/2键盘硬件。具体见参考资料。

对于驱动来说，和键盘相关的主要有两个芯片：

• intel 8042芯片
• intel 8048芯片

8042位于主板上，CPU通过I/O端口直接和这个芯片进行通信，获得键盘按键的扫描码或者发送各种键盘命令。

8048位于键盘中，这个芯片主要用于获取键盘按键扫描码，然后与8042进行通信。

像8042，8048这样的芯片，本身就是一个小的处理器，它的内部有自己的处理器，有自己的 Ram，有自己的寄存器，等等。

8042 有 4 个 8 bits 的寄存器，他们是 Status Register（状态寄存器），Output Buffer（输出缓冲器），Input Buffer（输入缓冲器），Control Register（控制寄存器）。使用两个 IO 端口，0x60 和 0x64。

驱动中把 0x60 叫数据端口，把 0x64 叫命令端口。

向8042发送命令的方法：

• 读取状态寄存器，判断bit1，状态寄存器bit1为0，说明输入缓冲器为空，可以写入。
• 保证状态寄存器bit1为0，然后对64h端口进行写操作，写入命令。

回到代码，先看第30行：

inb $0x64, %al

这条指令将端口号0x64对应的状态寄存器的数据读入%ax寄存器中。

testb $0x2, %al

test指令是用来检测一个位是否为1的。原理是将源操作数与目的操作数进行and操作，并根据结果设置标志寄存器。在这里0x2=10，所以检测的是bit1。

若bit1为1，则下面紧跟着的jnz seta20.1指令满足跳转条件（非零，即ZF=0，表示零标志没有被置位），循环继续执行。

若bit1为0，则test指令的结果是0，ZF标志位置1，后面的jnz指令不满足跳转条件，程序顺序执行。

movb $0xd1, %al指令将要发送给8042的命令装载到%al寄存器中。命令0xd1表示准备写Output端口，然后通过0x60端口写入一个字节。

outb %al, $0x64将命令写入到0x64端口，告诉8042准备写Output端口。

代码第37~43行：

seta20.2:
    inb $0x64, %al                     # Wait for not busy(8042 input buffer empty).
    testb $0x2, %al
    jnz seta20.2

    movb $0xdf, %al                     # 0xdf -> port 0x60
    outb %al, $0x60                     # 0xdf = 11011111, means set P2's A20 bit(the 1 bit) to 1

这一段循环与上面与一段循环大同小异。

首先通过inb、testb、jnz三条指令检测输入缓冲器是否为空，为空则可以写入。

紧接着movb、outb两条指令向0x60端口写入数据。

下图是804x的逻辑图

可以看出，bit1是控制A20选通的。

所以0xdf可以让A20启用。

打开A20地址线还有很多方法。具体见参考资料1、参考资料2

代码第49~52行

    lgdt gdtdesc
    movl %cr0, %eax
    orl $CR0_PE_ON, %eax
    movl %eax, %cr0

先看一下第49行指令的标准格式：

lgdt m48         ;lgdt m16&m32

m48表示，这条指令的操作数是一个48位（6字节）的连续区域。在16位模式下，该地址是16位的；32位模式下，该地址是32位的。

在这6字节的内存区域中，要求前（低）16位是GDT界限值（GDT大小字节数减一），后32位是GDT的基地址。

在初始状态下（计算机启动之后），GDTR的基地址被初始化位0x00000000，界限值是0xffff。

所以，lgdt gdtdesc指令从标号gdtesc处开始加载GDT。

接下来转到标号gdtesc处(84~86行)。

gdtdesc:
    .word 0x17                                      # sizeof(gdt) - 1
    .long gdt                                       # address gdt

根据lgdt指令的要求，这里先声明一个字大小（16位）的内存区域。值为GDT界限值，因为后面的GDT有三个段描述符，所以这里的大小是$3\times8-1=23 = 0{\rm x}17$。

紧接着声明一个long（32位）大小的内存区域，跳转到标号gdt处，也就是段描述符表定义处。即，这32位就是GDT的基地址。

标号gdt处的代码为：

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

这里是引用了文件asm.h中的宏。

SEG_NULLASM首先定义一个空段，因为前面提到过，处理器规定，GDT描述符表的0号描述符必须是空描述符，或者叫哑描述符或NULL描述符。

SEG_ASM(STA_X|STA_R, 0x0, 0xffffffff)定义了一个执行、读的代码段，段基址是0x0，段大小是0xffffffff，（实际上就是0xfffff乘以4KB）。

SEG_ASM(STA_W, 0x0, 0xffffffff)定义了一个读、写的数据段，段基址也是0x0，段大小和上面的代码段一样。

很显然，ucore为了让实验简单一点（实际上还是很难），就设置了一个段。

关于这几个宏、段类型的详细信息，请看对asm.h文件的分析。

回到前面的代码，第50~52行：

movl %cr0, %eax
orl $CR0_PE_ON, %eax
movl %eax, %cr0

这三行代码很明显，将cr0寄存器的PE位置1，打开通向保护模式的大门。

接下来执行的就是代码的56行：

ljmp $PROT_MODE_CSEG, $protcseg

一个长跳转指令直接跳到代码段（其实就是当前段）的标号protcseg处。

然后是58行：

.code32

告诉编译器接下来是以32位来编译代码。

我们终于进入保护模式了！！

接下来以保护模式运行标号protcseg处的代码：

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

注意，在32位保护模式下，x86的寻址方式是以段寄存器（此时叫段选择子）的隐藏部分中的32位基址来寻址的。

所以此时，只要将段选择子赋值给各个段寄存器就行了（实际上因为ucore只有一个段）,cpu会自动将GDT中对应段选择子的段描述符赋值到各个段寄存器的隐藏部分。

    # 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

设置基址指针寄存器为0x0，堆栈指针寄存器为标号start处（即0x7c00）。

在实模式下，栈的推进是从0x7c00向下推进的（因为0~0x7c00有一段空闲区）。从0x7c00处，代码（bootloarder）则是向上推进。

至于ucore为什么在进入保护模式后仍把堆栈指针急寄存器设为0x7c00，我还不是很清楚（个人猜测是为了方便，简单，哈哈）。

最后就是调用bootmain函数了。详情见练习4。

BTW，还有最后两行代码：

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

加入bootmain异常退出了，就陷入死循环。

asm.h

这个头文件是用来定义段描述表的。

先看SEG_NULLASM宏

/* Normal segment */
#define SEG_NULLASM                                             \
    .word 0, 0;                                                 \
    .byte 0, 0, 0, 0

很明显，这是定义了一个空描述符表（哑描述符或NULL描述符）。

接下来是SEG_ASM(type,base,lim)宏

#define SEG_ASM(type,base,lim)                                  \
    .word (((lim) >> 12) & 0xffff), ((base) & 0xffff);          \
    .byte (((base) >> 16) & 0xff), (0x90 | (type)),             \
        (0xC0 | (((lim) >> 28) & 0xf)), (((base) >> 24) & 0xff)

首先是三个参数type、base、lim

• type是段描述符的类型（4位）。

• base是段描述符的基地址（32位）。

• lim表示传入的段界限值（在这里默认是32位的，而且只用到了高20位。所以我个人认为这是多此一举了，因为段描述符中段界限值也只有20位）。

为了方便理解这个宏是如何定义段描述符的，先回顾一下段描述符的结构：

这里我们把64位的段描述符拆分成高32位和低32位，分别对应图中上半部分和下半部分。

先看低32位的赋值：

这个宏首先定一个了两个字（16位）大小的内存区域，值分别为(lim) >> 12) & 0xffff和(base) & 0xffff。

显然，(lim) >> 12) & 0xffff是赋值给了段描述符中0...15位的段界限值。这里取传入的lim的值第12...31位与0xffff进行逻辑与，所以只保留了lim的第12...27位。

(base) & 0xffff则是将传入的基地址的低16位赋值给段描述符中的16...31位的基地址。

再看高32位的赋值：

这个宏紧接着定义了四个字节（8位）大小的内存区域，值分别为((base) >> 16) & 0xff), (0x90 | (type)),(0xC0 | (((lim) >> 28) & 0xf)), (((base) >> 24) & 0xff)

(base) >> 16) & 0xff首先将base值右移16位（因为低16位已经在前面存入低32位中的基地址部分了），然后与0xff进行逻辑与，即保留8位，然后将这8位（即base的16..23位）赋值给段描述符的16..23位。

(0x90 | (type)这里的或是什么意思呢？

先看一下0x90的二进制：1001 0000

因为传入的type是4位的，所以与0x90或也就是将0x90的高4位和type的值拼在一起，得到的是1001 xxxx。

最后，将这个结果赋值到段描述符高32位的8~15位中。

结合图中来看，也就是对应P=1、DPL=00、S=1、TYPE=xxxx。

也就是段存在、特权级最高、描述符为代码或数据、类型由输入决定。

0xC0 | (((lim) >> 28) & 0xf)

同样的，0xC0的二进制：1100 0000

将lim右移28位以后与0xf进行逻辑或保留低四位（其实没必要），然后与0xC0的高四位拼在一起，对应赋值给高32位的16...23位。

结合图中来看，也就是G=1、D/B=1、AVL=0，段限长19..16位被对应赋值。

也就是段界限的粒度是4KB，默认大小是32位、系统软件位无效。

最后的((base) >> 24) & 0xff就是将基地址的高8位赋值了。

最后是定义段类型（type）所需要用到的宏。

/* Application segment type bits */
#define STA_X       0x8     // Executable segment
#define STA_E       0x4     // Expand down (non-executable segments)
#define STA_C       0x4     // Conforming code segment (executable only)
#define STA_W       0x2     // Writeable (non-executable segments)
#define STA_R       0x2     // Readable (executable segments)
#define STA_A       0x1     // Accessed

当需要定义段类型时，只需要将对应的宏进行逻辑或即可。

关于段类型，可以参考下面这个表格：

练习4：BootLoader加载ELF格式的OS的过程

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

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

代码分析

bootmain.c

bootmain.c主要用来将ELF可执行文件加载到硬盘中。

主要执行过程

先看33、34行：

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

定义了两个宏：

SECTSIZE表示一个扇区的大小，512字节。

ELFHDR用来定义一个elfhdr结构体类型的指针，这个指针的地址是0x10000。

bootmain执行的第一行代码在89行：

    readseg((uintptr_t)ELFHDR, SECTSIZE * 8, 0);

调用readseg函数，这三个变量分别是va(虚拟地址)、count（表示要连续读取的字节数）、offset偏移量，

在这里，

• va=0x10000，也就是将要读取的kernel在内存中的起始地址。

• count = SECTSIZE * 8 = 4KB正好是x86上一个页的大小。

• 偏移量offset=0。

对于readseg函数执行的详细过程，请看后面对readseg函数执行过程的详细分析。

这里直接说一下结果，这个函数执行完毕以后，bootmain就将kernel的第一页从磁盘上（在ucore实验中也就是ucore.img文件的从第二个扇区开始的一页）读到了内存的0x10000处。

然后就是代码的92~94行：

if (ELFHDR->e_magic != ELF_MAGIC) {
        goto bad;
    }

当kernel（对应的是kernel.elf，内核的可执行文件）的第一页加载到内存的0x10000处以后，此时ELFHDR宏对应的结构体指针就指向了kernel的ELF Header了。

然后就是检查是否是合法的elf文件。若不是，就跳转到bad标号处。

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

这时它会向端口 0x8a00（8470-8476）输出几个字。在真实硬件中，并没有设备连接到该端口，所以这段代码相当于什么也没有做。如果引导加载器是在 PC 模拟器上运行，那么端口 0x8a00 则会连接到模拟器并把控制权交还给模拟器本身。无论是否使用模拟器，这段代码接下来都会执行一个死循环。而一个真正的引导加载器则应该会尝试输出一些调试信息。

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

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

当kernel的头部正常加载以后，接下来开始加载程序段。

	struct proghdr *ph, *eph;

    // load each program segment (ignores ph flags)
    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);
    }

首先将*ph指针的值设置为ELFHDR中Program Headr表中的地址。

其中ELFHDR->e_phoff是program header表相对于ELFHDR的偏移量。

eph指向的是program header表的最后一项的地址。

接下来一个循环就是每次从program header表中，根据当前的program header读取对应的程序段到内存中。

最后，调用kernel的入口点函数，在这里，ELFHDR->entry的值是0x100000，也就是init.c文件中的kern_init函数在内存中的位置。至此，BootLoader就把ELF格式的OS加载到内存中了。

((void (*)(void))(ELFHDR->e_entry & 0xFFFFFF))();

值得注意的是，通过gdb单步调试分析0x10000处的elfhdr，可以得到如下信息：

(gdb) x/1aw 0x10000
0x10000:        0x464c457f
(gdb) x/12ab 0x10004
0x10004:        0x1     0x1     0x1     0x0     0x0     0x0     0x0     0x0
0x1000c:        0x0     0x0     0x0     0x0
(gdb) x/2ah 0x10010
0x10010:        0x2     0x3
(gdb) x/2aw 0x10014
0x10014:        0x1     0x100000 <kern_init>

对比一下下面提到的elfhdr结构体，可以得出一些有用的信息：

• 机器类型是x86
• 内核的入口点函数是在0x100000处。

elfhdr结构体

ELF header在文件开始处描述了整个文件的组织。ELF的文件头包含整个执行文件的控制结构。

在头文件elf.h中可以找到这个结构体的定义，把注释大概翻译了一下：

struct elfhdr {
    uint32_t e_magic;     // must equal ELF_MAGIC
    					  //必须等于ELF_MAGIC这个串
    uint8_t e_elf[12];	  //一个12*8位的数组
    uint16_t e_type;      // 1=relocatable, 2=executable, 3=shared object, 4=core image
    					  // 1表示可重定位，2表示可执行，3表示共享目标文件，4表示是内核镜像
    uint16_t e_machine;   // 3=x86, 4=68K, etc.
    uint32_t e_version;   // file version, always 1
    uint32_t e_entry;     // entry point if executable
    					  // 如果是可执行文件，这里是入口点
    uint32_t e_phoff;     // file position of program header or 0
    uint32_t e_shoff;     // file position of section header or 0
    uint32_t e_flags;     // architecture-specific flags, usually 0
    uint16_t e_ehsize;    // size of this elf header
    uint16_t e_phentsize; // size of an entry in program header
    uint16_t e_phnum;     // number of entries in program header or 0
    uint16_t e_shentsize; // size of an entry in section header
    uint16_t e_shnum;     // number of entries in section header or 0
    uint16_t e_shstrndx;  // section number that contains section name strings
};

对应的还有proghdr：

/* program section header */
struct proghdr {
    uint32_t p_type;   // loadable code or data, dynamic linking info,etc.
    uint32_t p_offset; // file offset of segment
    uint32_t p_va;     // virtual address to map segment
    uint32_t p_pa;     // physical address, not used
    uint32_t p_filesz; // size of segment in file
    uint32_t p_memsz;  // size of segment in memory (bigger if contains bss）
    uint32_t p_flags;  // read/write/execute bits
    uint32_t p_align;  // required alignment, invariably hardware page size
};

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

readseg函数

代码如下：

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);
    }
}

这个函数首先用传进来的起始地址va求出来了结束地址end_va。

然后用偏移量offset对SECSIZE求余，然后用va减去余数。

这里关于偏移量的理解，我在网上搜了很久，感觉比较靠谱的说法是，offset表示kernel在磁盘中相对于扇区开头的偏移量。因为我们要把kernel读取到va处，而readseg一次是读取一整个扇区的，所以要把kernel之前offset个字节的数据读取到va之前offset个字节的区域。所以这里将va向前偏移offset个字节。

接下来就是计算secno了，由于我们的ucore.img文件中0号扇区是储存bootblock的，所以扇区号从1开始。

最后是一个for循环，调用readsect函数连续读取扇区。关于readsect函数的原理，请看对readsec函数的分析。

readsect函数

static void
readsect(void *dst, uint32_t secno) {
    // wait for disk to be ready
    waitdisk();

    outb(0x1F2, 1);                         // count = 1
    outb(0x1F3, secno & 0xFF);
    outb(0x1F4, (secno >> 8) & 0xFF);
    outb(0x1F5, (secno >> 16) & 0xFF);
    outb(0x1F6, ((secno >> 24) & 0xF) | 0xE0);
    outb(0x1F7, 0x20);                      // cmd 0x20 - read sectors

    // wait for disk to be ready
    waitdisk();

    // read a sector
    insl(0x1F0, dst, SECTSIZE / 4);
}

从readseg函数进来以后，*dst指针指向的是当前扇区的起始地址，secno表示当前读取的扇区的扇区号。

waitdisk函数用于等待硬盘空闲，具体请看对waitdisk函数的分析。

接下来的七行outb函数是用来发出读取硬盘的命令的。具体参数可以参见下表：

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端口读数据

发送命令以后，再次用waitdisk函数等待硬盘空闲。

然后就是调用insl函数，因为这里传入的第三个参数是SECSIZE/4，所以是进行整个扇区的读取。具体是为什么，怎么读的，请看对insl函数的分析。

waitdisk函数

static void
waitdisk(void) {
    while ((inb(0x1F7) & 0xC0) != 0x40)
        /* do nothing */;
}

0x1F7端口对应的是状态和命令寄存器

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

从0x1F7端口读取一个字节，与0xC0=1100 0000进行逻辑与，保留第7位和第6位，当等于0100 0000时，也就是第6位为1时，此时是LBA模式，硬盘空闲，退出循环。

在ucore实验中，磁盘应该总是LBA格式的，具体原因我在StackOerflow上找到一个提问可以参考。

insl函数

在x86.h文件中找到函数insl(uint32_t port, void *addr, int cnt)的定义：

static inline void
insl(uint32_t port, void *addr, int cnt) {
    asm volatile (
            "cld;"
            "repne; insl;"
            : "=D" (addr), "=c" (cnt)
            : "d" (port), "0" (addr), "1" (cnt)
            : "memory", "cc");
}

gdb反编译后的指令如下：

0x00007cfc <+138>:   cld
0x00007cfd <+139>:   repnz insl (%dx),%es:(%edi)

这里gdb应该是有点小bug，反编译出来把repne指令变成了repnz指令。

在bootblock.asm中，可以看到机器码：

    7cfc:	fc                   	cld    
    7cfd:	f2 6d                	repnz insl (%dx),%es:(%edi)

f2对应的应该是repne指令，关于指令对应的机器码可以看这篇文章

关于这个repne insl指令，找了很久，终于在stackoverflow上找到了比较准确的解释。

repne是一个重复字符串操作前缀，终止条件如下：

重复前缀	终止条件 1	终止条件 2
REP	ECX=0	无
REPE/REPZ	ECX=0	ZF=0
REPNE/REPNZ	ECX=0	ZF=1

所以repne指令可以通过设置ecx寄存器的值来控制后面跟着的insl指令的执行次数。

简单地说，就是将ecx个双字（在这里因为后缀是l表示双字，也可以是字，字节）从端口edx输入到内存es:edi处。

所以，当传入的cnt是SECSIZE/4时，读取的字节数就是整个扇区大小的字节数。

练习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 –
……

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

预备知识

一个函数调用动作可分解为：零到多个PUSH指令（用于参数入栈），一个CALL指令。

CALL指令内部其实还暗含了一个将返回地址（即CALL指令下一条指令的地址）压栈的动作（由硬件完成）。几乎所有本地编译器都会在每个函数体之前插入类似如下的汇编指令：

pushl   %ebp
movl   %esp , %ebp

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

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

分析函数调用栈结构

代码实现及输出结果分析

以下是我实现的代码：

 	//读取ebp eip的值
    uint32_t ebp = read_ebp();
    uint32_t eip = read_eip();
    
    //两个临时变量i，j
    uint32_t i, j, k, count;
    //让i等于当前ebp寄存器的内容，也就是上一层ebp值的地址。
    //让j等于当前eip寄存器的内容，也就是当前的函数返回地址。
	//count表示当前循环的深度。

    //当i!=0也就是ebp不等于0,并且count小于栈的深度时循环。
    //每次让i的值变为上一层ebp的值。
    for(i=ebp, j=eip, count=0;
        i!=0 && count<STACKFRAME_DEPTH;
        j=*(uint32_t *)(i+4), i=*(uint32_t *)i, count++){
        //输出当前ebp，eip的值
        cprintf("ebp: 0x%08x eip: 0x%08x ", i, j);

        cprintf("arg: ");
        //打印四个参数，分别是i+8，i+12，i+16，i+20
        for(k=0; k<4; k++){
            cprintf("%08x ",*(uint32_t *)(i+8+k*4));
        }
        cprintf("\n");
        //打印当前eip-1
        print_debuginfo(j-1);
        
    }

输出结果：

Kernel executable memory footprint: 64KB
ebp: 0x00007b28 eip: 0x00100a63 arg: 00010094 00010094 00007b58 00100092 
    kern/debug/kdebug.c:308: print_stackframe+21
ebp: 0x00007b38 eip: 0x00100092 arg: 00000000 00000000 00000000 00007ba8 
    kern/init/init.c:48: grade_backtrace2+33
ebp: 0x00007b58 eip: 0x001000bc arg: 00000000 00007b80 ffff0000 00007b84 
    kern/init/init.c:53: grade_backtrace1+38
ebp: 0x00007b78 eip: 0x001000db arg: 00000000 ffff0000 00007ba4 00000029 
    kern/init/init.c:58: grade_backtrace0+23
ebp: 0x00007b98 eip: 0x00100101 arg: 00000000 00100000 ffff0000 0000001d 
    kern/init/init.c:63: grade_backtrace+34
ebp: 0x00007bb8 eip: 0x00100055 arg: 001032dc 001032c0 0000130a 00000000 
    kern/init/init.c:28: kern_init+84
ebp: 0x00007be8 eip: 0x00007d72 arg: 00000000 00000000 00000000 00007c4f 
    <unknow>: -- 0x00007d71 --
ebp: 0x00007bf8 eip: 0x00007c4f arg: c031fcfa c08ed88e 64e4d08e fa7502a8 
    <unknow>: -- 0x00007c4e --

可以看到，最后一行，ebp:0x00007bf8，表示第一个函数调用的ebp值位于内存的0x00007bf8。

而这第一个函数调用的返回值是eip:0x00007c4f，表示第一个函数的返回地址是0x00007c4f。到bootblock.asm中，找到了返回地址处的指令：

00007c4f <spin>:

    # If bootmain returns (it shouldn't), loop.
spin:
    jmp spin
    7c4f:	eb fe                	jmp    7c4f <spin>
    7c51:	8d 76 00             	lea    0x0(%esi),%esi

也就是spin死循环。结合我们前面对boot.asm文件的分析，也就是说，如果bootmian函数返回了（正常情况下是不应该返回的），此时栈底的函数返回地址就是之前的spin死循环。

同样可以分析倒数第二行，

ebp: 0x00007be8 eip: 0x00007d72 arg: 00000000 00000000 00000000 00007c4f 
    <unknow>: -- 0x00007d71 --

在bootmain.c中找到了这里的返回地址对应的代码：

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

结合我们之前对bootmain函数的分析，当读取扇区出错时，函数的返回地址就是这里。

练习6 完善中断初始化和处理 （需要编程）

预备知识

在操作系统中，有三种特殊的中断事件。

• 由CPU外部设备引起的外部事件如I/O中断、时钟中断、控制台中断等是异步产生的（即产生的时刻不确定），与CPU的执行无关，我们称之为异步中断(asynchronous interrupt)也称外部中断,简称中断(interrupt)。
• 而把在CPU执行指令期间检测到不正常的或非法的条件(如除零错、地址访问越界)所引起的内部事件称作同步中断(synchronous interrupt)，也称内部中断，简称异常(exception)。
• 把在程序中使用请求系统服务的系统调用而引发的事件，称作陷入中断(trap interrupt)，也称软中断(soft interrupt)，系统调用(system call)简称trap。在后续试验中会进一步讲解系统调用。

任务的特权级保护

任务、LDT、TSS以及TSS描述符

在这里，我们暂且把进程（Process）称为任务（Task）。

为了有效地实现任务之间的隔离，每个任务都有自己的描述符表，称为局部描述符表（Local Descriptor Table, LDT），并且把自己专属的段的描述符放到LDT中。

由于每个任务都有自己的LDT，所以每个任务私有的段都应该在LDT中进行描述。另外，与GDT不同的是，LDT的0号描述符也是有效的，可以使用的。

由于有多个LDT，为了访问它们，类似GDT的，LDT有全局描述符表寄存器（LDT Regiter: LDTR）。和GDTR一样，LDTR是48位的，包含32位线性基地址和16位界限字段。

由于在一个多任务的操作系统中，会有很多任务在轮流执行，正在执行的任务称为当前任务（Current Task）。而LDTR总是指向当前任务的LDT。

当要执行改变段寄存器的值的指令时，处理器会检查段选择子的T1位，为1时，就会用LDTR去访问LDT，并根据段选择子的索引来选取对应的段描述符，送到段寄存器的描述符高速缓存器去。

当任务切换发生时，为了保存当前任务的状态，并且在下次执行时重新恢复它们，每个任务都有一个额外的内存区域保存相关信息，这叫做任务状态段（Task State Segment，TSS）。(如下图)

TSS有固定的格式，最小尺寸是104字节。处理器在任务切换时，能够读取其中的信息。

和LDT一样，处理器用TR寄存器（Task Register，TR）来指向当前任务的TSS，且TSS只有一个。当任务切换发生时，处理器将当前的任务现场信息保存到由TR寄存器指向的TSS，然后再把TR指向新的TSS，并从新任务的TSS中恢复现场。

就像其它段描述符描述段的一些性质一样，TSS描述符用来描述TSS的某些性质。TSS描述符仅可能存放在GDT中。

全局空间和局部空间

顾名思义，全局地址空间由全局描述符表（GDT）指定，局部地址空间由局部描述符表（LDT）指定。通常，任务会在自己的局部空间运行，当它需要使用操作系统提供的服务时，转入到全局空间执行。

特权级保护

Intel处理器有四个特权级，级别由高到低分别是00、01、10、11。

操作系统内核拥有特权级0，系统服务程序的特权级通常是1和2。应用程序的特权级别则是3，也就是最低的。这也就是为什么每个描述符都有2比特的DPL位（Dscriptor Privilege， 描述符特权级）。描述符总是指向它所描述的对象，所以该字段实际上就是目标对象的特权级。

比如，对于数据段来说，DPL决定了访问它们所应当具备的最低特权级。如果有一个数据段，描述符的DPL字段是2，那么只有0，1，2特权级的程序才能访问它。特权级为3的程序试图访问它时，会被处理器阻止，并引发异常中断。

当处理器正在一个代码段中取指令和执行指令时，那个代码段的特权级叫做当前特权级（Current Privilege， CPL）。正在执行的这个代码段，其选择子位于段寄存器CS（ECS）中，最低两位就是当前特权级（CPL）的数值。所以，当操作系统的代码正在执行时，当前特权级就是0。应用程序正在执行时，当前特权级就是3。

这其实就是把一个任务分成特权级截然不同的两部分，全局部分特权级为0，局部空间特权级则是3。当任务在自己的局部空间内执行时，他的当前特权级CPL是3，当它通过调用系统服务，进入操作系统内核，在全局空间执行时。当前特权级CPL就变成了0。

不同特权级的指令所承担的职责和在操作系统中扮演的角色也是不一样的，比如，停机指令hlt和对控制寄存器cr0的写操作，像这样的指令只能由最高特权级的程序来作。这样的指令称为特权指令（Privileged Instructions）。像这样的指令还有加载全局描述符表的指令lgdt、加载局部描述符表的指令lldt、加载任务寄存器指令ltr、读写控制寄存器的move指令等等。

除了对特权敏感的指令外，处理器还对各个特权级别所能执行的I/O操作进行控制。通常，这指的是端口访问许可权。因为对设备的访问都是通过端口进行的。

如图，EFLAGS寄存器的13、12位是输入输出特权级（I/O Privilege Level， IOPL），代表当前任务的I/O特权级别。

任务由操作系统创建，与之相关的信息都在任务自己的TSS中，其中就有一个EFLAGS寄存器的副本，用于指示与这个任务相关的机器状态。

回顾一下关于段描述符的TPYE类型字段：

• C=0时，这个代码段只能供相同特权级的程序使用。

• C=1时，这个代码段称为依从的代码段，可以从特权级比它低的程序调用并进入。并且，依从的代码段不是在它的特权级上运行，而是在调用它的程序的特权级上运行。也就是说，当控制权转移到依从的代码段上执行时，当前特权级CPL不变。被调用的过程的特权级依从于调用者的特权级。

在任何时候，都不允许将控制从较高的特权级转移到较低的特权级。

调用门

除了依从的代码段，另一种在特权级之间的转换方法是使用门（Gate）。门是另一种形式的描述符，称为门描述符，简称门。和段描述符不同，段描述符用于描述内存段，而门描述符用于描述可执行的代码，比如一段程序、一个过程（例程）或者一个任务。

门有几种类型，不同特权级之间的过程调用可以使用系统（调用）门；中断门/陷阱门是作为中断处理过程使用的；任务门对应着单个的任务，用于执行任务切换。

在这里主要先说一下调用门描述符

调用门描述符结构：

系统（调用）门（System gate）
类型码1100用来让用户态的进程访问Intel 的陷阱门，因此，门描述符的DPL 为3。通过系统门来激活4 个Linux 异常处理程序，它们的向量是3、4、5 及128，也就是说，在用户态下，可以使用int 3、into、bound 及int 0x80 四条汇编指令。

调用门可以安装在GDT或者LDT中。不能安装在IDT中。

使用jmp far指令和call far指令，就可以通过调用门进行控制转移。这两条指令的区别在于：

• jmp far指令不改变当前特权级（用于进入非依从的代码段，此时特权级要相同，比如程序内的跳转）。
• call far指令会将当前特权级提升到目标代码的特权级（用于系统调用）。

要注意的是，除了从特权级高的例程返回外，不允许将控制从特权级高的代码段转移到特权级低的代码段。

为了防止特权级低的代码段通过call far系统调用来访问特权级比它高的代码段或者数据段，处理器引入了请求特权级（Requested Privilege Level，RPL）。比如下图：

当要将控制进行转移时，无论当前程序是要访问一个代码段还是一个数据段，总要提供一个段选择子，以及段内偏移量（也就是入口点）。为了访问内存中的数据，总要把段选择子装载到段寄存器（DS、ES、FS或GS中）。这个过程可以看作一个请求，请求者提供一个段选择子，请求访问一个段。所以，RPL指的就是请求者的特权级别。

操作系统是知道选择子的来源的，当选择子来自于一个除了它自己之外的程序时，操作系统就会将请求者提供的选择子的RPL字段设置为请求者的特权级（通过arpl指令）。

总结特权级之间的关系如下（数值上进行比较）：

将控制直接转移到非依从的代码段：

• CPL$=$选择子对应的段描述符的DPL

• RPL$=$选择子对应的段描述符的DPL

将控制直接转移到依从的代码段：

• CPL$\geq$选择子对应的段描述符的DPL

• RPL$\geq$选择子对应的段描述符的DPL

每当处理器执行一个将段选择子传送到段寄存器的mov指令时，就会检查以下两个条件：

• CPL$\leq$选择子对应的段描述符的DPL

• RPL$\leq$选择子对应的段描述符的DPL

若以上条件不成立，就会引发异常中断。

另外，因为栈段特权级要和CPL相同，所以在对栈段寄存器SS的内容进行修改时，要求满足以下条件：

• CPL$=$选择子对应的段描述符的DPL

• RPL$=$选择子对应的段描述符的DPL

因此，当用call far进行控制转移时，还要切换栈，也就是从低特权级的栈切换到高特权级的栈。这个过程就是通过TR寄存器找到当前任务的TSS，然后从中取得特权级高的栈的地址信息，然后进行栈切换。所以，对于特权级为3的任务来说，最多还要额外定义特权级为0、1、2的三个栈，以便在特权级发生转换时使用。

栈切换前，段寄存器SS指向的是旧栈，ESP指向旧栈的栈顶，也就是最后一个被压入的要传送给服务例程的参数。栈切换后，处理器自动替换SS和ESP中的内容。

但是我们并不需要程序员来关心栈的切换和参数的复制，因为操作系统在栈切换之前会执行pop edx指令，也就是把要传递的最后一个参数出栈到edx寄存器中。

这些额外创建的栈，他们的描述符位于任务自己的LDT中。同时，还要在任务的TSS中进行登记。回看一下上面的TSS的示意图，偏移4～24处用于登记对应特权级的栈段选择子以及相应的ESP的初始值。任务自己的栈信息位于偏移量56（ESP）和80（SS）处。

任务门

当中断发生时，如果该中断号对应的门是任务门，那么，就要进行任务切换。处理器中断当前任务的执行，保存当前任务的现场，并转换到另一个任务中去执行。

任务门可以用于在中断发生时进行任务切换，所以，任务门应该指向要切换的任务的TSS。所以，在任务门描述符中有一个TSS选择子。如下图：

同样的，P位表示该门是否有效。DPL是任务门描述符的特权级，DPL对因中断而发起的任务切换不起作用。**因为处理器在发生中断时，不会去检查特权级。**但是当以非中断的方式发起任务切换时，DPL就有用了。

当中断发生时，处理器用中断号乘以8作为索引在IDT中取得一个中断描述符，当这个描述符是一个任务门描述符时，处理器就知道此时应该发起任务切换了。

接着，处理器从这个任务门描述符中取得TSS选择子，再用TSS选择子访问GDT，取出新任务的TSS。在转换到新任务执行之前，处理器先将当前任务的状态保存起来。此时通过访问TR即可得到当前任务的TSS的地址。当前任务的状态保存结束以后，就访问新任务的TSS，并从中恢复各个寄存器的内容。最后，TR指向新任务的TSS的地址，处理器便开始执行新的任务。当新任务开始执行后，处理器自动把它的TSS描述符的B位置1，表示该任务的状态“忙”。

当中断发生时，可以执行常规的中断处理过程，也可以进行任务切换。他们都要用iret指令返回。前者是返回到同一个任务内的不同代码段，后者是返回到被中断的那个任务。

EFLAGS寄存器里有一个NT位（位14)，意思是嵌套任务标志（Nested Task Flag）。同时每个任务的TSS中都有一个任务链接域，里面可以存放前一个任务的TSS描述符选择子。

当NT位为1时，表示当前任务是嵌套于其他任务内的，并能够通过TSS返回前一个任务。当因中断进行任务切换时，处理器将当前任务状态保存到TSS中，把当前任务的段选择子填入新任务的TSS中的任务链接域，然后切换到新的任务。

除了使用中断进行任务切换，还可以使用远过程调用指令call far和远距离跳转指令jmp far进行任务切换。

当处理器执行这两条指令时，若段选择子对应的段描述符时普通的代码段描述符，就按照普通的段间转移规则执行；如果是调用门，就按照调用门规则执行；如果是TSS描述符或者任务门描述符，就执行任务切换。此时，指令中的第二个操作数（32位的偏移量）被忽略。因为执行任务切换时，所有处理器的状态都可以通过TSS获得。

中断描述符表，中断门、陷阱门

中断和异常

中断包括硬件中断和软件中断。

• 硬件中断时由外位硬件设备发出的中断信号引发的。当I/O接口发出中断请求时，会被8295A和I/O APIC这样的中的官控制器收集，当处理器处理完当前指令后，开始处理中断。

• 软中断是由int n指令引发的中断处理，n叫做中断号或者类型码。

异常分为三种：

• 程序错误异常。
• 软件发起的异常。通常由into、int3和bound指令主动发起。比如，溢出检测指令into执行时，会检查EFLAGS寄存器的OF标志位，若为1，则引发异常。
• 机器检查异常。

根据异常的严重程度，又可以分为以下三种：

• 故障（Faults）。故障通常是可以纠正的，如缺页故障，处理器将所需要的页从磁盘换入到内存中以后，
• 陷阱（Traps）。如果陷阱条件成立的话，陷阱中断则在执行截获陷阱条件的指令之后立刻产生。如into、int3指令。陷阱返回后处理的是截获陷阱的指令的下一条指令。
• 终止（Aborts）。标志着最严重的错误，比如硬件错误、系统表（GDT、LDT等）中的数据不一致或者无效。此时，通常操作系统会终止当前任务。

中断描述符表

在实模式下，采用的是中断向量表（IVT）的形式，位于内存地址0x00～0x3FF处，大小为1KB。

中断向量表的每一个表项大小是4个字节，分别是段地址和偏移地址。所以实模式下的中断向量表有256个表项。

当中断发生时，处理器要么产生一个中断向量，要么直接从int n指令中得到中断向量，或者从中断控制器接受一个中断向量，然后将该中断向量作为索引访问中断向量表。具体做法是，将中断向量乘以4，访问到对应的表项。

下图是保护模式下的中断和异常向量分配：

在保护模式下，处理器对中断的管理是类似的，只不过是用中断描述符表（Interrupt Descriptor Table, IDT）。

顾名思义，这个表里存放的是和中断处理过程有关的描述符。包括**中断门、陷阱门和任务门。**格式如下图所示：

1．任务门（Task gate）
其类型码为101，门中包含了一个进程的TSS 段选择符，但偏移量部分没有使用，因为TSS本身是作为一个段来对待的，因此，任务门不包含某一个入口函数的地址。TSS 是Intel 所提供的任务切换机制，但是 Linux 并没有采用任务门来进行任务切换。

2．中断门（Interrupt gate）
其类型码为110，中断门包含了一个中断或异常处理程序所在段的选择符和段内偏移量。当控制权通过中断门进入中断处理程序时，处理器清IF 标志，即关中断，以避免嵌套中断的发生。中断门中的DPL（Descriptor Privilege Level）为0，因此，用户态的进程不能访问Intel 的中断门。所有的中断处理程序都由中断门激活，并全部限制在内核态。

3．陷阱门（Trap gate）
其类型码为111，与中断门类似，其唯一的区别是，控制权通过陷阱门进入处理程序时维持IF 标志位不变，也就是说，不关中断。

中断门和陷阱门描述符只允许放在IDT内，而任务门可以位于GDT、LDT和IDT中。

处理器内部，有一个48位的中断描述符表寄存器（Interrupt Descriptor Table Register, IDTR），保存这中断描述符表在内存中的线性基地址和界限，也就是说，IDT可以位于内存中任何地方。和GDT一样，整个系统中只需要一个IDT就够了，所以GDTR和IDTR不像LDTR和TR，没有也不需要选择器部分。

为了利用cache使处理器工作性能最大化，通常IDT的基地址是8字节对齐的。处理器复位时，IDTR的基地址部分为0，界限部分为0xFFFF。

16位的表界限意味着IDT和GDT、LDT一样，大小可以是64KB。但是，由于处理器只能识别256种中断，所以通常只使用2KB。其他空余的位值应该将描述符的P位清零（不在内存中）。

在保护模式下，当中断和异常发生时，处理器用中断向量乘以8的结果去访问IDT，从中取得对应的描述符。

对于中断门和陷阱门，处理器根据选择子的T1位（0访问GDT，1访问LDT），去访问GDT或者LDT，取出目标代码段的段描述符。接着，从段描述符中取得目标代码段的基地址，然后与门描述符中的偏移量相加，就得到了中断处理程序的32位线性地址。当没有开启分页功能时，该线性地址就是物理地址。否则，送到页部件转换成物理地址。当处理器用中断向量访问IDT时，如果要访问的地址超出了IDT的界限，则产生常规保护异常（#GP）。

如果中断是被用户态程序中的指令所触发的（比如软件执行int n产生的中断），还会增加一个额外的检查：门的DPL必须具有与CPL相同或更低的特权。**这就防止了用户代码随意触发中断。**如果这些检查失败，会产生一个一般保护异常（general-protection exception）。

问题一

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

中断描述符表中一个表项8个字节，除了任务门描述符外，每个表项中有16位的段选择子和32位的偏移量，根据段选择子到GDT中寻找对应的段描述符，然后用得到的段基址和32位的偏移量相加，就得到中断处理程序的代码入口。对于任务门描述符来说，16位的段选择子是TSS段选择子，处理器根据这个段选择子到GDT中选择对应的TSS描述符，TSS描述符中就描述了要切换的程序的相关状态信息，其中就包括了程序位置。

问题二

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

先要说明的是，ucore在这里实现中断的方式比较简单，并不是标准的实现中断的方式（即对应的中断号直接跳转到对应的中断服务程序）。而是由同一个函数根据中断号来处理所有的中断。

vectors.S文件是由tools文件夹下的vector.c文件统一生成的。

在文件vectors.S中，定义了一个__vectors数组，其中有256个vector向量。其中每一个vector向量都是一个中断服务例程，所做的事情就是将0压栈（表示没有错误代码），再将中断号压栈。最后，所有的vector都会统一跳转到标号alltraps处。

标号__alltraps是ucore中对所有的中断进行统一处理的函数。首先将相关寄存器压栈，创建trapframe，然后调用trap.c文件中的trap函数处理中断。

__vectors数组的主要作用是用来初始化中断向量表（因为中断向量表最多有256个表项），所以__vectors数组的向量数也是256。

而idt_init函数就是用来初始化中断向量表的。

对于这个函数，我实现的代码如下:

			extern uintptr_t __vectors[];
      int i;
      for(i=0; i<256; i++){
        SETGATE(idt[i], 0, 8, __vectors[i], 0);
      }
      lidt(&idt_pd);

代码第一行首先是声明引用vectors数组。下面的一个循环是用来根据每一个对每一个idt表项，用对应的vector来初始化。

SETGATE这个宏可以在mmu.h文件中找到：

/* *
 * Set up a normal interrupt/trap gate descriptor
 *   - istrap: 1 for a trap (= exception) gate, 0 for an interrupt gate
 *   - sel: Code segment selector for interrupt/trap handler
 *   - off: Offset in code segment for interrupt/trap handler
 *   - dpl: Descriptor Privilege Level - the privilege level required
 *          for software to invoke this interrupt/trap gate explicitly
 *          using an int instruction.
 * */
#define SETGATE(gate, istrap, sel, off, dpl) {            \
    (gate).gd_off_15_0 = (uint32_t)(off) & 0xffff;        \
    (gate).gd_ss = (sel);                                \
    (gate).gd_args = 0;                                    \
    (gate).gd_rsv1 = 0;                                    \
    (gate).gd_type = (istrap) ? STS_TG32 : STS_IG32;    \
    (gate).gd_s = 0;                                    \
    (gate).gd_dpl = (dpl);                                \
    (gate).gd_p = 1;                                    \
    (gate).gd_off_31_16 = (uint32_t)(off) >> 16;        \
}

这个宏用来初始化一个中断描述符。五个参数的作用分别是：

• gate表示传入的门描述符
• istrap表示传入的门描述符的类型，是中断还是异常（陷阱）
• sel表示中断描述符对应的中断服务程序的段选择子
• off表示中断描述符对应的中断服务程序的段内偏移量
• dpl表示优先级。在这里，除了调用门描述符，其他都应该是0，即最高优先级。

所以，在上面的循环中，每一次传入的参数的意义是：

• idt[i]表示当前要初始化的描述符
• 0默认全部为中断
• 8因为前面提到了，ucore的GDT只有3个段，0是空描述符，1是代码段描述符，2是数据段描述符。而中断服务程序应该位于代码段，所以这里段选择子的值应该是1000b。即在GDT中选择1号段，RPL是00。
• __vectors[i]
• 0表示当前服务程序的特权级是最高级别。

做完了这个题目之后，我才发现在memlayout.h文件中有对整个ucore内存结构进行定义的宏。

其中就有GDT中各个描述符的对应的索引号。

所以上面的sel参数其实可以用GD_KTEXT这个宏进行替换。

问题三

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

我在上面提到了，__alltraps函数创建了trapframe以后，调用trap函数根据中断号处理对应的中断。

先看一下__alltraps函数是如何创建trapframe的：

# push registers to build a trap frame
    # therefore make the stack look like a struct trapframe
    pushl %ds
    pushl %es
    pushl %fs
    pushl %gs
    #	Push AX, CX, DX, BX, original SP, BP, SI, and DI.
    pushal

    # load GD_KDATA into %ds and %es to set up data segments for kernel
    movl $GD_KDATA, %eax
    movw %ax, %ds
    movw %ax, %es

    # push %esp to pass a pointer to the trapframe as an argument to trap()
    pushl %esp

    # call trap(tf), where tf=%esp
    call trap

trapframe结构体在trap.h文件中的定义：

/* registers as pushed by pushal */
struct pushregs {
    uint32_t reg_edi;
    uint32_t reg_esi;
    uint32_t reg_ebp;
    uint32_t reg_oesp;            /* Useless */
    uint32_t reg_ebx;
    uint32_t reg_edx;						//顺序正好和pushal的顺序相反。
    uint32_t reg_ecx;
    uint32_t reg_eax;
};
struct trapframe {
    struct pushregs tf_regs;
    uint16_t tf_gs;
    uint16_t tf_padding0;
    uint16_t tf_fs;
    uint16_t tf_padding1;
    uint16_t tf_es;
    uint16_t tf_padding2;
    uint16_t tf_ds;
    uint16_t tf_padding3;
    uint32_t tf_trapno;
    /* below here defined by x86 hardware */
    uint32_t tf_err;
    uintptr_t tf_eip;
    uint16_t tf_cs;
    uint16_t tf_padding4;
    uint32_t tf_eflags;
    /* below here only when crossing rings, such as from user to kernel */
    uintptr_t tf_esp;
    uint16_t tf_ss;
    uint16_t tf_padding5;
} __attribute__((packed));

从中可以分析出，依次push ds, es, fs, gs进入__alltraps之前的push 0, trapno的顺序都是有意义的。因为堆栈的地址是向下递减的，而trapframe结构体中成员变量的地址是向上递增的。所以相反的顺序才能构造出trapframe结构体。

接下来分析trap函数。trap函数如下：

void
trap(struct trapframe *tf) {
    // dispatch based on what type of trap occurred
    trap_dispatch(tf);
    // cprintf("in trap function\n");
}

可见，调用了trap_dispatch函数，在这个函数中，就是根据中断号利用switch语句处理对应的中断，找到处理时钟中断的case，我实现的打印时钟中断的代码如下：

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!
         */
         // cprintf("in timer interrupt function\n");
         if(++ticks==100){
           print_ticks();
           ticks=0;
         }
        break;

ticks全局变量是定义在clock.c文件中的，每次时钟中断让ticks+1，每满100打印一次100ticks。

拓展练习

Challenge 1（需要编程）

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

关于调用门，可以看一下前面对调用门的描述（调用门对用户程序特权级有一些限制）。

由于如果使用调用门实现这个函数，需要修改中断描述符表，添加一个特权级为3（用户态）的调用门描述符，还要重新在trap.c文件中添加一个用与处理这个调用门的中断服务例程，比较麻烦，所以这里直接用已经定义好的中断门（处理器这时不会检查CPL、RPL、DPL的关系）来实现。

首先请看一下我对这个练习中引发软中断时trapframe压栈过程的分析：

当程序触发一个软中断时，处理器会首先检查是否发生了特权级转换。如果发生了特权级转换，就会进行栈切换操作。如下：

|           |								|              |
|           |								|              |
|           |								|     ss(旧)   |
|    ...    |								|    esp(旧)   |<---esp
|    ebp    |<---esp			        	|    flag(压入)|   ||
|    ...    |								|    cs(压入)  |   ||
|           |								|    eip(压入) |   ||
|           |								|      ...     |  \ /
|           |								|              |	
|           |								|              |
|           |								|              |
|    旧栈    |							 |      新栈     |

处理器会先将旧特权级对应的栈的SS和ESP复制。然后从TSS读取转并换到的特权级的SS以及ESP，将原来的SS和ESP的内容压入新栈中。

在执行完中断函数后，最后一条指令时irt指令。iret指令执行之前，也会检查是否发生了特权级切换。如果发生了特权级切换，则会在将eip、cs、flag相继出栈后，再把栈帧（trapframe）中应该有的ss、esp寄存器的值弹出，然后将恢复到ss、esp中。






如果没有发生特权级转换，也就是下面这种情况。处理器是不会发生栈切换操作，也不会把ss、esp寄存器压栈的。但是在这个练习中，为了实现在中断程序内部进行特权级转换，我们需要人为地把ss、esp寄存器的值压入到当前的栈中，用来保存返回状态（因为我们返回时，已经从内核态切换到用户态了，请继续往下看）。
｜          ｜               ｜             ｜
｜    ...   ｜               ｜   ...       ｜
｜    ebp   ｜<---esp        ｜   ebp       ｜
｜    ...   ｜               ｜   ss(旧)    ｜
｜          ｜               ｜ esp(&ss(旧))｜<---esp
｜          ｜               ｜             ｜
｜          ｜               ｜             ｜
｜          ｜               ｜             ｜
｜          ｜               ｜             ｜
｜  压栈前   ｜               ｜     压栈后   ｜

当中断处理程序结束以后，我们修改了cs、ds、ss、es对应的段寄存器的内容（修改为了用户态对应的段）。最后一条指令是iret指令，此时处理器发现我们的特权级发生了改变（当前中断处理程序是运行在内核态的，所以从内核态变成了用户态），就会依次把栈中ss、esp的值复制并恢复到ss、esp寄存器中。
所以可以看出，如果我们前面没有将ss和esp压栈。这时候处理器恢复的ss和esp寄存器的值就是错误的（是上面的ebp和ebp+4）。
|           |								｜             ｜
|    ...    |								｜      ...    ｜
|    ebp    |								｜      ebp    ｜
|    ss(旧) |							  ｜    ss(旧)   ｜<---esp
|    esp(旧)|<---esp				 	｜ esp(&ss(旧))｜   
|  flag(弹出)|	/\				   ｜    (flag)   ｜
|   cs(弹出) |	||					 ｜     ...     ｜
|   eip(弹出)|	||					 ｜             ｜
|    ...    |  							｜             ｜
|           |								｜             ｜
|    恢复前  |								｜      恢复后  ｜
需要注意的是
恢复后的esp指向的是栈中旧的ss保存的地址，我们要恢复到中断处理之前的状态，也就是应该让esp指向ebp，所以要执行esp+4.

在trap.h文件中，可以看到预先为我们定义好了两个中断号：

/* *
 * These are arbitrarily chosen, but with care not to overlap
 * processor defined exceptions or interrupt vectors.
 * */
#define T_SWITCH_TOU                120    // user/kernel switch
#define T_SWITCH_TOK                121    // user/kernel switch

所以我们只需要在trap.c中修改对应的中断处理函数，然后在kern_init函数中发出对应的中断就行。

首先分析一下如何从用户态进入内核态。

直接看我的代码：

static void
lab1_switch_to_user(void) {
    //LAB1 CHALLENGE 1 : TODO
    //调用切换到用户态的中断
    asm volatile("pushl %ss");
    asm volatile("pushl %esp");
    asm volatile(
      "int $120"
    );
    asm volatile("addl $0x4, %esp");
    //cprintf("int 120 returns!\n");
}

前面两句内联汇编首先将寄存器ss、esp压栈。由于当前程序段仍然运行在内核态，所以软中断并不存在特权级切换，也就不会发生栈切换操作。

随后触发120号中断，对应的处理函数在trap.c中:

case T_SWITCH_TOU:
        // cprintf("now in interrupt\n");
         // print_trapframe(tf);
        /*asm volatile("movl %%ax, %%cs\n\t"::"a"(GD_UTEXT));
        asm volatile("movl %%ax, %%ds\n\t"::"a"(GD_UDATA));*/
        tf->tf_cs = USER_CS;
        tf->tf_ds = USER_DS;
        tf->tf_es = USER_DS;
        tf->tf_ss = USER_DS;
        tf->tf_eflags = tf->tf_eflags | FL_IOPL_3;
        // cprintf("%d ticks\n", &ticks);
        print_ticks();
        // print_trapframe(tf);
        break;

经过lab1_switch_to_user触发软中断后，我们怎么让返回处程序运行在用户呢？很简单，只要把段选择子改成用户态的段选择子就行了。

按理来说，通常情况下，修改了段选择子(相关的宏可以在mmlayout.h文件中找到)，段基址也就会发生改变，从而我们要向能够返回引发中断的那段代码，需要修改trapframe中eip寄存器的值，进行程序重定位，这样当中断结束后，处理器才能正确的从trapframe中恢复返回地址。但是ucore实验中，因为我们之前定义的段的基地址都是0，所以这里不需要修改eip来重定向返回地址。

需要注意的是，因为我们在lab1_switch_to_user函数中还调用了涉及IO的函数，而从中断返回后，lab1_switch_to_user函数的特权级已经发生了改变，所以我们在返回之前还要修改eflags寄存器的IO特权级（eflag寄存器对应的宏定义在mmu.h文件中），否则在调用有关IO的函数是就会引发13号异常（保护异常）。（这个地方我之前没注意，卡了好久）。

break以后，处理器会回到trapentry.S文件中继续执行。弹出对应的寄存器。

最后一条iret指令，会进行特权级检查，此时发现我们的特权级从0变成了3，就会在弹出eip、cs、eflag寄存器的值以后，继续弹出esp、ss寄存器的值。

注意⚠️，esp恢复以后实际指向的还是ebp-4的位置，那里是之前压栈的ss的内容。所以，我们为了让esp恢复到进入这个函数之前的状态，应该将esp+4，而ss是刚才由处理器自动出栈恢复的，不需要我们去修改。在这里，应该是不能直接用popl ss指令的，这样会引发13号保护异常（亲测，被坑了好久，但是我猜想应该可以用两条指令popl ax; movl %ax, %ss代替，但是没有试过）。

从lab1_switch_to_user函数返回后，程序旧运行在用户态了。

接下来，准备在lab1_switch_to_kernel函数中从用户态切换回内核态。

static void
lab1_switch_to_kernel(void) {
    //LAB1 CHALLENGE 1 :  TODO
    //调用切换到内核态的中断
  //  asm volatile("pushl %ss");
    //asm volatile("pushl %esp");
    asm volatile(
      "int $121"
    );
    asm volatile("popl %esp");
    // asm volatile("addl $0x4, %esp");
    //cprintf("int 120 returns!\n");

}

由于我们刚才切换到了用户态，这时，程序再通过中断转换到内核态时要进行栈切换，并将当前栈的ss和esp压入到新栈中。所以这里我把ss和esp压栈的指令注释掉并保留在这里，方便和前面对比。

这个临时栈的定义在pmm.c文件中。这个文件定义了内核的TSS，然后重新定义了一个GDT，并将其地址加载到了GDTR中。随后在72行定义了uint8_t stack0[1024];，再将这个栈设置为TSS的stack0。这样一来，就可以从用户态切换到内核态了（当然这么做因为只是这当前这个练习比较特殊，后面应该会通过常规方法来进行特权级的切换）。

触发121号中断前，我们需要注意，因为处理器在进入中断处理程序前，会检查CPL和中断描述符的DPL，要求CPL级别必须高于或者等于中断描述符的DPL级别（这么做也可以防止用户随意通过软中断来访问内核）。

因为在init_idt函数中，我们把所有的中断描述符的DPL都设置成了0，所以，在这个练习中，我们要在init_idt函数中把第121号中断的DPL改成3

      SETGATE(idt[121],0,8,__vectors[121],3);

这样才能正常通过int n指令触发第121号中断，否则会引发第13号异常保护（这里也卡了我好久）。

一切准备就绪后，就可以进入中断处理程序了：

case T_SWITCH_TOK:
         // print_trapframe(tf);
        tf->tf_cs = KERNEL_CS;
        tf->tf_ds = KERNEL_DS;
        tf->tf_es = KERNEL_DS;
        tf->tf_ss = KERNEL_DS;
        tf->tf_eflags = tf->tf_eflags ^ FL_IOPL_3;
         // print_trapframe(tf);
        // panic("T_SWITCH_** ??\n");
        break;

处理方式和前面大同小异，这里我把FL_IOPL_3和eflags进行异或，来清除之前设置的IO特权级3。

注意⚠️到，由于从中断（运行在内核态）返回后，我们的代码处于内核态，所以这时没有发生特权级转换，处理器也就不会从栈中弹出esp、ss寄存器的值。

用gdb在asm volatile("popl %esp");处设置断点。info r查看此时各个寄存器的值，可以看到：

esp            0x110d18            0x110d18 <stack0+1016>
ebp            0x7b98              0x7b98

此时esp是指向新栈中保存的旧的esp的值的（参考我上面画的图）。可以通过打印esp指向的地址内容验证：

(gdb) x $esp
0x110d18 <stack0+1016>: 0x00007b98

所以，我们需要做的最后一步就是将esp寄存器弹出就行了。

为什么不弹出ss？因为这时候ss的值已经是内核代码段的选择子了（这是从TSS中恢复的）。

至此，我们就又从用户态切换回到了内核态了。

可以看到qemu正常输出：

切换到用户态后输出段寄存器的值，然后切换到内核态输出段寄存器的值，最后陷入kern_init中的while死循环，时钟中断正常。

Challenge 2（需要编程）

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

这个拓展练习暂时还没有思路（先鸽了）。

因为按照我challenge1的思路，当软中断发生时，由于没有发生特权级改变，所以我们可以人为在函数中压入ss和esp的值。

但是在这里是硬件中断，我们没法在中断发生前人为压入ss和esp的值。

虽然我想到了一种解决思路，就是在中断处理函数内部修改trapframe所在堆栈的结构，在trapframe下面加入ss和esp的值。但是，这样修改由会引起别的麻烦，即，堆栈中压入的一些ebp的值也要相应的发生改变。这样修改比较麻烦，还没实现成功。

lab2

系统启动流程

lab2中的ucore启动流程与lab1中不大一样。由于加入了虚拟内存技术，所以bootasm中增加了探测物理内存的代码块，并且入口函数不再是kern_init函数，而是新增加的一个文件entry.S。

bootasm.S

首先还是bootasm.S

通过BIOS中断获取内存可调用参数为e820h的INT 15h BIOS中断。BIOS通过系统内存映射地址描述符（Address Range Descriptor）格式来表示系统物理内存布局，其具体表示如下：

Offset  Size    Description
00h    8字节   base address               #系统内存块基地址
08h    8字节   length in bytes            #系统内存大小
10h    4字节   type of address range     #内存类型

对于其中的类型字段：

Values for System Memory Map address type:
01h    memory, available to OS
02h    reserved, not available (e.g. system ROM, memory-mapped device)
03h    ACPI Reclaim Memory (usable by OS after reading ACPI tables)
04h    ACPI NVS Memory (OS is required to save this memory between NVS sessions)
other  not defined yet -- treat as Reserved

int 15中断的返回值：

eflags的CF位：若INT 15中断执行成功，则不置位，否则置位；

eax：534D4150h ('SMAP') ；

es:di：指向保存地址范围描述符的缓冲区,此时缓冲区内的数据已由BIOS填写完毕

ebx：下一个地址范围描述符的计数地址

ecx：返回BIOS往ES:DI处写的地址范围描述符的字节大小

ah：失败时保存出错代码

bootasm中探测物理内存的代码如下：

probe_memory:
    movl $0, 0x8000
    xorl %ebx, %ebx       //ebx：如果是第一次调用或内存区域扫描完毕，则为0。 
                          //如果不是，则存放上次调用之后的计数值；
    movw $0x8004, %di     //es:di指向保存地址范围描述符结构的缓冲区，BIOS把信息写入这个结构的起始地址
start_probe:
    movl $0xE820, %eax    //INT 15的中断调用参数
    movl $20, %ecx        //保存地址范围描述符的内存大小,应该大于等于20字节
    movl $SMAP, %edx      //534D4150h (即4个ASCII字符“SMAP”) ，这只是一个签名而已
    int $0x15
    jnc cont              //cf位为0则跳转到cont处
    movw $12345, 0x8000
    jmp finish_probe
cont:
    addw $20, %di        //每次让di指向下一个地址描述符
    incl 0x8000          //对应e820map的nr_map变量，表示可用内存区域的个数
    cmpl $0, %ebx        //检查是否结束扫描
    jnz start_probe
finish_probe:

用来保存地址描述符的结构体如下,定义在mmlayout.h中：

struct e820map {
                  int nr_map;
                  struct {
                                    long long addr;
                                    long long size;
                                    long type;
                  } map[E820MAX];
};

最后，会跳到bootmain.c执行。

entry.S

bootmain.c中做的工作和之前一样。所以这里就不分析了。

与之前不同的是，bootmian会调用entry.S作为入口，再由entry.S调用kern_init函数。所以这里分析一下entry.S文件的工作。

首先引入头文件，然后定义了一个用于虚拟地址转为物理地址的REALLOC重定位函数。

#include <mmu.h>
#include <memlayout.h>

#define REALLOC(x) (x - KERNBASE)

这个重定位函数是什么意思呢？可以看到在kernel.ld链接脚本中有这么一行：

/* Load the kernel at this address: "." means the current address */
    . = 0xC0100000;

也就是说，链接器把内核的虚拟地址定位到了0xC0100000。

而我们内核加载的物理地址是0x100000。

所以，此时的虚拟地址其实就是物理地址加上了0xc0000000的偏移。

所以，将虚拟地址减去KERNBASE（0xc0000000）就得到了实际的物理地址。

下面就是kern_entry的代码段，分析我直接写在注释里：

.text
.globl kern_entry
kern_entry:
    # load pa of boot pgdir
    movl $REALLOC(__boot_pgdir), %eax    #获得页目录表的物理地址，关于页目录表怎么来的，请往下看
    movl %eax, %cr3                      #将页目录表的物理地址存到cr3寄存器（cr3的作用就是这个）

    # enable paging                      #这一段就是修改cr0寄存器，使能页式存储
    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
	
		# 进入虚拟存储模式后处理器会重新熏寻址
		# 但此时eip仍然是0x1...（之前没有开启虚拟存储，eip直接用物理地址）
		# 这也是为什么要将虚拟地址的0～4MB内存也映射到物理地址的0～4MB内存
    # update eip
    # now, eip = 0x1.....
    leal next, %eax
    # 利用leal指令将next标号的地址加载到eax中。此时next标号的地址应该是用虚拟地址表示的。
    # 利用gdb单步调试，也可以验证这个结论： eax 0xc010001e
    # set eip = KERNBASE + 0x1.....
    jmp *%eax
    # jmp跳转到next标号处处理器会根据eax中的虚拟地址在页目录表中查找到对应的表项，然后去查找对应的页表中的表项，取得物理地址的高20位，再跟虚拟地址的低12位拼在一起得到真正的物理地址。在这里，由于我们的页表__boot_pt1是按顺序映射的，所以也就是说在这里物理地址就是低22位。
next:
		# 清空页目录表的第一项，解除虚拟地址0～4MB的映射
    # unmap va 0 ~ 4M, it's temporary mapping
    xorl %eax, %eax
    movl %eax, __boot_pgdir

		# 接下来是设置堆栈
    # set ebp, esp
    movl $0x0, %ebp
    # the kernel stack region is from bootstack -- bootstacktop,
    # the kernel stack size is KSTACKSIZE (8KB)defined in memlayout.h
    movl $bootstacktop, %esp
    # now kernel stack is ready , call the first C function
    call kern_init

# should never get here
spin:
    jmp spin

下面这一段数据段就是用来初始化内核栈的。大小是两个页面。

.data
.align PGSIZE
    .globl bootstack         //声明栈
bootstack:
    .space KSTACKSIZE        //大小8kB，也就是两个页面
    .globl bootstacktop      
bootstacktop:               //指向栈顶，此时栈为空（注意，栈的顺序是从高内存往下递减的）。

下面的代码是页表的初始化：

ucore是采用二级页表的形式。这一段就是用来创建页目录表，以及一个页表项，用来将虚拟地址0~4MB和KERNBASE~KERNBASE+4MB映射到物理地址的0~4MB。

下面是页表项cr3寄存器和页表项的结构：

cr3寄存器在32位处理器的各位含义：

页目录表项各位的含义：

页表项各位的含义：

# kernel builtin pgdir
# an initial page directory (Page Directory Table, PDT)
# These page directory table and page table can be reused!
.section .data.pgdir
.align PGSIZE
__boot_pgdir:
.globl __boot_pgdir
    # map va 0 ~ 4M to pa 0 ~ 4M (temporary)
    .long REALLOC(__boot_pt1) + (PTE_P | PTE_U | PTE_W) #将页目录表的第一个表项指向__boot_pt1页表
    # 由于一个页目录项对应一个页表。而一个页表能够管理4MB的地址
    # 所以KERNBASE >> PGSHIFT >> 10 计算得到的是管理虚拟地址KERNBASE + (0 ~ 4M)的页表对应的页目录表项的偏移量。 具体来说，>> PGSHIFT计算的是KERNBASE在物理地址的第几页，而 >> 10计算的是KERNBASE在第几个页表（因为一个页表有2^10个表项）。
    # << 2 左移两位是因为一个表项4个字节。
    # (. - __boot_pgdir)即用当前地址减去__boot_pgdir的起始地址，也就是之前的页表项所占用的内存。
    .space (KERNBASE >> PGSHIFT >> 10 << 2) - (. - __boot_pgdir) # pad to PDE of KERNBASE
    # 此时定位到了第二个页目录表项的起始地址。随后将第二个页目录表项对应的页表设置为__boot_pt1
    # map va KERNBASE + (0 ~ 4M) to pa 0 ~ 4M
    .long REALLOC(__boot_pt1) + (PTE_P | PTE_U | PTE_W)
    .space PGSIZE - (. - __boot_pgdir) # pad to PGSIZE，按页对齐

#设置页表。
.set i, 0
__boot_pt1:
.rept 1024
    .long i * PGSIZE + (PTE_P | PTE_W)
    .set i, i + 1
.endr

练习1：实现 first-fit 连续物理内存分配算法（需要编程）

这个练习比较坑，有很多细节需要注意。

主要需要实现default_pmm.c文件中的3个函数：default_init_memmap，default_alloc_pages， default_free_pages。下面请看分析。

先看一下我画的free_list的大概结构：

ucore中用一个page结构体来管理一个页帧，所有的page结构体在内存中是连续的，起始位置在ucore结束地址按页向上对齐的地方。page结构体定义如下：

struct Page {
    int ref;                        // page frame's reference counter
    uint32_t flags;                 // array of flags that describe the status of the page frame
    unsigned int property;          // the num of free block, used in first fit pm manager
    list_entry_t page_link;         // free list link
};

而一些连续的页面，就构成一个空闲内存块。

其中的page_link是一个包含两个指针的结构体，这两个指针分别用来指向前一个空闲内存块的第一个page结构体和后一个空闲内存块的第一个page结构体。

free_area结构体中有两个成员变量free_list链表和nr_free（表示空闲页帧数）。

free_list链表用来保存每个连续内存块的第一个page结构体（first page）。它是一个双向循环链表。

接下来明确一下调用过程：

CALL GRAPH: kern_init --> pmm_init --> page_init --> init_memmap -->pmm_manager -->init_memmap.

在调用init_memmap之前，page_init会将可用的物理地址段传过来，接着在init_memmap函数中初始化连续的page结构体。

要注意最后一句将page结构体插入链表时，由于传过来的地址是从低到高的，而我们希望构成的链表page的地址也是从低到高的，所以我们每次要将page插在表尾。

注意看我调用list_add函数时的第一个参数，是有讲究的。list_prev(&free_list)表示表尾的节点。

static void
default_init_memmap(struct Page *base, size_t n) {
  	// assert断言函数用来验证括号内的表达式是否正确
    assert(n > 0);
    struct Page *p = base;
    for (; p != base + n; p ++) {
        // page_init调用时，把所有的page都设置为内核保留状态了
        assert(PageReserved(p));
        // 因为这个函数是初始化空闲内存用的，所以把PG_reserved和PG_property都置0
        p->flags = p->property = 0;
        // 将ref也置0
        set_page_ref(p, 0);
    }

    base->property = n;
    // 将这一块连续内存空间的第一个页的PG_property置1表示空闲
    SetPageProperty(base);
    // 总的空闲页数+n
    nr_free += n;
    // 把这个连续空闲的内存块加入到空闲区域链表中
    // 每次将新的高地址插在表尾
    list_add(list_prev(&free_list), &(base->page_link));
}

PG_reserved位和PG_property位的定义在mmlayout.h中：

/* Flags describing the status of a page frame */
#define PG_reserved                 0       // if this bit=1: the Page is reserved for kernel, cannot be used in alloc/free_pages; otherwise, this bit=0

#define PG_property                 1       // if this bit=1: the Page is the head page of a free memory block(contains some continuous_addrress pages), and can be used in alloc_pages;
                                            // if this bit=0: if the Page is the the head page of a free memory block, then this Page and the memory block is alloced. Or this Page isn't the head page.

翻译成人话就是，

如果该页可以供我们分配，则PG_reserved位为0，否则被kernel所保留，PG_reserved位为1.

而PG_property位为1表示该page结构体对应的页帧是一个空闲内存块的first page，有空闲内存可以给我们分配，其他情况为0.

下面是first fit算法的实现函数，详细的分析都在注释当中：

static struct Page *
default_alloc_pages(size_t n) {
    // 先检查n是不是大于0
    assert(n > 0);
    // n大于所有空闲页面的总和直接返回NULL
    if (n > nr_free) {
        return NULL;
    }
    //要返回的page指针，默认为NULL
    struct Page *page = NULL;
    //取得free_list的头节点
    list_entry_t *le = &free_list;
    //每次将le指向下一个节点的le，当发现回到表头时退出循环
    while ((le = list_next(le)) != &free_list) {
        //用le2page宏取得le对应的Page结构体的指针
        struct Page *p = le2page(le, page_link);
        //若当前的p满足要分配的大小，将p赋值给page变量并返回
        if (p->property >= n) {
            page = p;
            break;
        }
    }
    //退出循环时，若page不为空则进行分配
    if (page != NULL) {
        //先把当前的page从链表中删除
        // list_del(&(page->page_link));
        //空闲页大于n的情况，切割内存块。不需要考虑等于n，因为等于n直接分配，不用切割
        if (page->property > n) {
            struct Page *p = page + n;
            // 将p的flag的property位置为1表示空闲内存块的首页，property设置为p后连续空闲页的大小
            SetPageProperty(p);
            p->property = page->property - n;


            //将p加入到空闲区链表中
            list_add(&(page->page_link), &(p->page_link));

            // cprintf("in alloc func, the p's ref value is: %d\n", page_ref(p));
            // cprintf("in alloc func, the page's ref value is: %d\n", page_ref(page));
        }

        // 总空闲页数-n
        nr_free -= n;
        //将包括page在内的n页全部分配出去，page的property应该变成0表示已占用
        page->property = 0;
        ClearPageProperty(page);
      	//将page从链表中删除
        list_del(&(page->page_link));
    }
    return page;
}

下面是页面回收函数。

关于页面回收，注意要考虑三种情况：

• 回收的内存块尾部和已有内存快相邻
• 回收的内存块头部和已有内存快相邻
• 回收的内存块头部和尾部都和已有内存快相邻

少考虑一种情况都会导致check函数失败（亲身经历）

还有就是在这里要按照地址顺序将base插入链表。否则后面的check函数也无法通过。

详细的分析都在注释当中：

static void
default_free_pages(struct Page *base, size_t n) {
    //要释放的页面数应该大于0
    assert(n > 0);
    struct Page *p = base;
    for (; p != base + n; p ++) {
        // PG_reserved和PG_property位都应该为0，表示当前页可已被占用
        assert(!PageReserved(p) && !PageProperty(p));
        p->flags = 0;
        // 引用数置0
        set_page_ref(p, 0);
    }
    //因为释放了n个页，property属性置为n，作为首页，property位置1
    base->property = n;
    SetPageProperty(base);

    list_entry_t *le = list_next(&free_list);
    while (le != &free_list) {
        p = le2page(le, page_link);
        //以下是两种合并情况
        //如果base的末尾和p的起始重合
        if (base + base->property == p) {
            // 将base设置为第一个page
            base->property += p->property;
            p->property = 0;
            ClearPageProperty(p);
            //将base添加到p之前
            list_add(list_prev(&p->page_link), &(base->page_link));
            //将p删去即可
            list_del(&(p->page_link));

            break;
        }
        //如果p的末尾和base的起始重合
        else if (p + p->property == base) {
            // 将p设置为该内存块的第一个page
            p->property += base->property;
            // 由于p已经在链表中，只要修改p的属性就行，然后将base变为普通的page
            base->property = 0;
            ClearPageProperty(base);
            //如果此时p的边界又和下一个page重合，则它们应该合并
            struct Page* nextPage = le2page(list_next(le), page_link);
            if(p + p->property == nextPage){
                p->property += nextPage->property;
                nextPage->property = 0;
                ClearPageProperty(nextPage);
                list_del(list_next(le));
            }
            break;

        }
        //第三种情况就是都没找到
        else {

        }
        le = list_next(le);

    }
    // 没有可合并的块，按照地址顺序将base插入链表。
    if(le == &free_list){
      le = list_next(&free_list);
      // 只要找到了地址大于base的page，就把base插在它前面
      while(le != &free_list){
        if(le2page(le, page_link) > base){
          list_add(list_prev(le), &(base->page_link));
          break;
        }
        le = list_next(le);
      }
      // 如果没找到，就插在表尾
      if(le == &free_list){
        list_add(list_prev(&free_list), &(base->page_link));
      }

    }

    nr_free += n;
}

debug了好久，最终成功通过检查：

练习2：实现寻找虚拟地址对应的页表项（需要编程）

通过设置页表和对应的页表项，可建立虚拟内存地址和物理内存地址的对应关系。其中的get_pte函数是设置页表项环节中的一个重要步骤。此函数找到一个虚地址对应的二级页表项的内核虚地址，如果此二级页表项不存在，则分配一个包含此项的二级页表。本练习需要补全get_pte函数 in kern/mm/pmm.c，实现其功能。请仔细查看和理解get_pte函数中的注释。

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

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

第一个问题：

页目录表项用于检索二级页表。二级页表的页表项用于得到所要寻找的页的物理地址。最后，根据二级页表得到的页帧的物理地址加上虚地址中的偏移量得到实际的物理地址。

第二个问题：

~~这个实验中并没有具体出现缺页的情况，~~很悲剧的是，我最后make qemu运行的时候发现lab1的challenge的代码又不能正常运行了，用gdb单步调试后发现，原来在lab1的challenge的代码块内发生了页故障（page fault），中断号14。

我也在网上找到了这个问题答案。当ucore执行过程中出现了页访问异常，硬件需要完成的事情分别如下：

• 将发生错误的线性地址保存在cr2寄存器中;
• 在中断栈中依次压入EFLAGS，CS, EIP，以及页访问异常码error code，如果page fault是发生在用户态，则还需要先压入ss和esp，并且切换到内核栈；
• 根据中断描述符表查询到对应page fault的ISR，跳转到对应的ISR处执行，接下来将由软件进行page fault处理；

关于页目录表和页表的寻址方式，请看下图：

代码实现：

//get_pte - get 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
// parameter:
//  pgdir:  the kernel virtual base address of PDT
//  la:     the linear address need to map
//  create: a logical value to decide if alloc a page for PT
// return vaule: the kernel virtual address of this pte
pte_t *
get_pte(pde_t *pgdir, uintptr_t la, bool create) {
    // 页目录表和页表的下标
    uint32_t pageDirectoryIndex = PDX(la);
    uint32_t pageTableIndex = PTX(la);
    // 得到页目录表的表项
    pde_t* pageDirEnrty =  pgdir + pageDirectoryIndex;
    pte_t* pageTableEntry;
    //若p位为0，则检查create
    if((*pageDirEnrty & PTE_P) != PTE_P){
        if(create){
          //申请新页
          struct Page* newPage = alloc_page();
          page_ref_inc(newPage);
          uintptr_t* newPageTablePhysicAddr = page2pa(newPage);

          //设置页目录表项 高20位是新页表的物理地址 将低三位置位
          *pageDirEnrty = (uint32_t)newPageTablePhysicAddr & 0xFFFFF000 | PTE_P | PTE_W | PTE_U;
          // 把新页表全部置0
          memset(KADDR(newPageTablePhysicAddr), 0, PGSIZE);
          // 得到新页表的页表项
          pageTableEntry = (pte_t*)KADDR(newPageTablePhysicAddr) + pageTableIndex;
          // cprintf("pageTableEntry: %08x", *pageTableEntry);
          return pageTableEntry;
        }
        else{
          return NULL;
        }
    }


    // 得到页表的物理地址
    pte_t* pageTablePhysicAddr = *pageDirEnrty & 0xFFFFF000;
    // 根据虚地址索引得到得到页表项
    pageTableEntry = (pte_t*)KADDR(pageTablePhysicAddr) + pageTableIndex;
    return pageTableEntry;
}

其中用到了pmm.h和string.h文件中的几个宏：

PDX(la) : 获得虚地址的页目录表项索引（高10位）
KADDR(pa) : 将物理地址转化为内核虚地址
set_page_ref(page,1) : 将page结构体的ref值置1
page_ref_inc(newPage) : 将page的ref值加1 
page2pa(page): 得到page结构体的物理地址
struct Page * alloc_page() : 分配一页
memset(void *s, char c, size_t n) : 将虚拟地址s开头的连续n个字节设置为c

总结一下，get_pte函数完成的工作就是根据传入的页目录地址和虚地址查找页表项。

如果对应的页表项不存在，则根据create的值决定是创建页表还是返回null。

完成练习2以后，kernel还不能正常工作，需要完成练习3。

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

当释放一个包含某虚地址的物理内存页时，需要让对应此物理内存页的管理数据结构Page做相关的清除处理，使得此物理内存页成为空闲；另外还需把表示虚地址与物理地址对应关系的二级页表项清除。请仔细查看和理解page_remove_pte函数中的注释。为此，需要补全在 kern/mm/pmm.c中的page_remove_pte函数。

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

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

问题一：

Page结构体与页目录项和页表项是有对应关系的。

在这个练习中，物理地址加上偏移量0xC0000000可以得到虚拟地址（在这里也是线性地址）。而通过虚拟地址，我们又可以访问到相应的页目录表和页表。由于Page结构体和物理内存每一页之间又是一一对应的关系，所以实际上在这个练习中可以根据Page结构得到页表项的地址。

问题二：

当前物理地址和虚拟地址是存在一个0xC0000000的偏移量的。所以想要让物理地址等于虚拟地址，只需要在kernel.ld链接脚本中将这个偏移量设置为0就行了。

代码实现：

static inline void
page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) {

          //(1) check if this page table entry is present
          //(2) find corresponding page to pte
          //(3) decrease page reference
          //(4) and free this page when page reference reachs 0
          //(5) clear second page table entry
          //(6) flush tlb


      //如果p位存在
      if((*ptep & PTE_P) == PTE_P){
          // 得到物理地址
          struct Page* page = pte2page(*ptep);
        	// ref减一
          page_ref_dec(page);
        	// 如果ref值为0了，则释放该页
          if(!page_ref(page)){
            free_page(page);
          }
        	// 清空二级页表项
          *ptep = 0;
        	// 使tlb中对应表项失效
          tlb_invalidate(pgdir, la);
      }


}

练习3的实现还是比较简单的。最后qemu运行结果如下：

可以看到页分配算法和页表项相关的检查都通过了，最后时钟中断正常。但是lab1的challenge的代码不能正常工作了，会引发页故障。后续再想想怎么修改吧。

lab3

练习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的缺页服务例程在执行过程中访问内存，出现了页访问异常，请问硬件要做哪些事情？

练习2：补充完成基于FIFO的页面替换算法（需要编程）

完成vmm.c中的do_pgfault函数，并且在实现FIFO算法的swap_fifo.c中完成map_swappable和swap_out_victim函数。通过对swap的测试。注意：在LAB3 EXERCISE 2处填写代码。执行

make　qemu

后，如果通过check_swap函数的测试后，会有“check_swap() succeeded!”的输出，表示练习2基本正确。

请在实验报告中简要说明你的设计实现过程。

请在实验报告中回答如下问题：

• 如果要在ucore上实现"extended clock页替换算法"请给你的设计方案，现有的swap_manager框架是否足以支持在ucore中实现此算法？如果是，请给你的设计方案。如果不是，请给出你的新的扩展和基此扩展的设计方案。并需要回答如下问题
  • 需要被换出的页的特征是什么？
  • 在ucore中如何判断具有这样特征的页？
  • 何时进行换入和换出操作？

Q.E.D.