密码保护：华中科技大学操作系统挑战实验(PKE)基础解析
lab1_challenge1 打印用户程序调用栈（难度：★★☆☆☆）
给定应用
- user/app_print_backtrace.c
1 /*
2 * Below is the given application for lab1_challenge1_backtrace.
3 * This app prints all functions before calling print_backtrace().
4 */
5
6 #include "user_lib.h"
7 #include "util/types.h"
8
9 void f8() { print_backtrace(7); }
10 void f7() { f8(); }
11 void f6() { f7(); }
12 void f5() { f6(); }
13 void f4() { f5(); }
14 void f3() { f4(); }
15 void f2() { f3(); }
16 void f1() { f2(); }
17
18 int main(void) {
19 printu("back trace the user app in the following:n");
20 f1();
21 exit(0);
22 return 0;
23 }以上程序在真正调用系统调用print_backtrace(7)之前的函数调用关系比复杂，图示起来有以下关系：
main -> f1 -> f2 -> f3 -> f4 -> f5 -> f6 -> f7 -> f8
print_backtrace(7)的作用是将以上用户程序的函数调用关系，从最后的f8向上打印7层，预期的输出为：
代码语言：javascript复制In m_start, hartid:0
HTIF is available!
(Emulated) memory size: 2048 MB
Enter supervisor mode...
Application: obj/app_print_backtrace
Application program entry point (virtual address): 0x0000000081000072
Switching to user mode...
back trace the user app in the following:
f8
f7
f6
f5
f4
f3
f2
User exit with code:0.
System is shutting down with exit code 0.实验内容
本实验为挑战实验，基础代码将继承和使用lab1_3完成后的代码：
- （先提交lab1_3的答案，然后）切换到lab1_challenge1_backtrace、继承lab1_3中所做修改：
//切换到lab1_challenge1_backtrace
$ git checkout lab1_challenge1_backtrace
//继承lab1_3以及之前的答案
$ git merge lab1_3_irq -m "continue to work on lab1_challenge1"注意：**不同于基础实验，挑战实验的基础代码具有更大的不完整性，可能无法直接通过构造过程。**例如，由于以上的用户代码中print_backtrace()系统调用并未实现，所以构造时就会报错。同样，不同于基础实验，我们在代码中也并未专门地哪些地方的代码需要填写，哪些地方的代码无须填写。这样，我们留给读者更大的“想象空间”。
- 本实验的具体要求为：
通过修改PKE内核，来实现从给定应用（user/app_print_backtrace.c）到预期输出的转换。
对于print_backtrace()函数的实现要求：
应用程序调用print_backtrace()时，应能够通过控制输入的参数（如例子user/app_print_backtrace.c中的7）控制回溯的层数。例如，如果调用print_backtrace(5)则只输出5层回溯；如果调用print_backtrace(100)，则应只回溯到main函数就停止回溯（因为调用的深度小于100）。
实验指导
为完成该挑战，PKE内核的完善应包含以下内容：
- 系统调用路径上的完善，可参见3.2中的知识；
- 在操作系统内核中获取用户程序的栈。这里需要注意的是，PKE系统中当用户程序通过系统调用陷入到内核时，会切换到S模式的“用户内核”栈，而不是在用户栈上继续操作。我们的print_backtrace()函数的设计目标是回溯并打印用户进程的函数调用情况，所以，进入操作系统内核后，需要找到用户进程的用户态栈来开始回溯；
- 找到用户态栈后，我们需要了解用户态栈的结构。实际上，这一点在我们的第一章就有举例来说明，读者可以回顾一下第一章的例子；
- 通过用户栈找到函数的返回地址后，需要将虚拟地址转换为源程序中的符号。这一点，读者需要了解ELF文件中的符号节（.symtab section），以及字符串节（.strtab section）的相关知识，了解这两个节（section）里存储的内容以及存储的格式等内容。对ELF的这两个节，网上有大量的介绍，例如这里，或阅读Linux Man Page。
提示：
理论上，我们希望你了解函数调用时栈帧的结构，通过fp寄存器(s0)寻找各个栈帧；然而，编译器一般会优化掉fp，使得它的值始终为0，在发生函数调用时也不保存这个寄存器，实验的Makefile已经使用-fno-omit-frame-pointer禁止了此项优化。
第一章中的 举例 程序中，函数调用的栈帧（此时 bar 函数作为叶子调用函数）类似下图：
注意，函数调用的叶子结点一般不会将ra保存到栈中；
如果你发现使用fp追踪栈底难度太大，可以假设用户程序的函数调用产生的栈帧总是定长的；为了获得这个长度，你可以：
代码语言：javascript复制$ riscv64-unknown-elf-objdump -d obj/app_print_backtrace观察f1~ f8开始时的汇编代码，特别注意用户态函数do_user_call，它的栈帧与f1 等略有不同。
使用这种方法虽然在局部变量太多，或者函数参数较多时无法正确实现 backtrace 功能，也不是我们预期的做法，但我们进行测试时确实会使用简单的测试用例（没有参数，局部变量），因此可以通过
实验解析
首先最基本的,我们要了解ELF文件的基本组成.
ELF文件主要是由两个视角组成,一个是链接时的视角,还有一个执行时的视角,两个视角组成不同的两种组成
在这个时候我们发现有三个非常关键的结构,一个是总结全部的ELF头部,还有一个程序头部表,用来指导如何创建一个新的进程来进行执行.节区头部表用来记录程序静态的链接信息.
首先是总的ELF头部信息.
typedef struct elf_header_t {
uint32 magic;
uint8 elf[12];
uint16 type; /* Object file type */
uint16 machine; /* Architecture */
uint32 version; /* Object file version */
uint64 entry; /* Entry point virtual address */
uint64 phoff; /* Program header table file offset */
uint64 shoff; /* Section header table file offset */
uint32 flags; /* Processor-specific flags */
uint16 ehsize; /* ELF header size in bytes */
uint16 phentsize; /* Program header table entry size */
uint16 phnum; /* Program header table entry count */
uint16 shentsize; /* Section header table entry size */
uint16 shnum; /* Section header table entry count */
uint16 shstrndx; /* Section header string table index */
} elf_header;
我们首先解释一下成员信息:
1、e_entry表示程序入口地址
2、e_ehsize：ELF Header结构大小
3、e_phoff、e_phentsize、e_phnum：描述Program Header Table的偏移、大小、结构(有多少个段首部)。
4、e_shoff、e_shentsize、e_shnum：描述Section Header Table的偏移、大小、数量(有多少个节首部)。
5、 e_shstrndx：这一项描述的是字符串表在Section Header Table中的索引，值25表示的是Section Header Table中第25项是字符串表（String Table）。一般等于e_shnum – 1
6、编译后比较固定的字段：e_ident 、 e_machine 、e_version 、e_entry 、e_flags 、e_ehsize
7、目前e_ehsize = 52字节，e_shentsize = 40字节，e_phentsize = 32字节，这些值都是固定值，某些加固会修改这些值造成静态解析失败，可以修改回这些固定值
一个ELF文件中到底有哪些具体的 sections，由包含在这个ELF文件中的 section head table(SHT)决定。在SHT中，针对每一个section，都设置有一个条目（entry），用来描述对应的这个section，其内容主要包括该 section 的名称、类型、大小以及在整个ELF文件中的字节偏移位置等等。
代码语言：javascript复制// elf section header
typedef struct elf_sect_header_t{
uint32 name;
uint32 type;
uint64 flags;
uint64 addr; /*the first byte of the section.*/
uint64 offset;/*此成员的取值给出节区的第一个字节与文件头之间的偏移*/
uint64 size;
uint32 link;
uint32 info;
uint64 addralign;
uint64 entsize;
} elf_sect_header;一个程序里面有许许多多的节(段),在这个实验里面我们要关注两个段,一个是.symtab,还有就是.strtab段.
了解了基本的ELF文件信息,这个时候我们做的第一步就是更改ELF文件的加载方式.首先在ELF头文件中我们了解到有一个成员叫做shstrndx,这个表示了字符串表是第几个section,这个时候我们可以根据字符串表是第几个section获得其SHT的数据,如下面程序所示:因为我们知道找到section table是连续存放的,我们可以根据section table的连续性找到字符串表所在的位置.
总的地址:第一个SHT的地址 它是第几个SHT*一个SHT的内容(sh_addr是之前已经定义好的一个section_table的类型变量)
代码语言：javascript复制这里有代码,但是被ban了我们找到了字符串表的头结构,顺理成章地可以根据offset成员获得字符串表本身的结构.用下面的程序获得之,并存入到elf_shstrtab里面.其中elf_shstrtab存放着这个section所有的内容.
代码语言：javascript复制这里有代码,但是被ban了String table sections 保存着以 NULL 终止的一系列字符，一般我们称为字符串。object 文件使用这些字符串来描绘符号和 section 名。一个字符串的参考是一个 string table section 的索引。第一个字节，即索引 0，被定义保存着一个 NULL 字符。同样的，一个 string table 的最后一个字节保存着一个NULL 字符，所有的字符串都是以 NULL 终止。索引 0 的字符串是没有名字或者说是 NULL，它的解释依靠上下文。一个空的 string table section 是允许的；它的 section header 的成员 sh_size 将为 0。对空的 string table 来说，非 0 的索引是没有用的。
查阅资料发现SHT的name保存着该section的名字,但是设计ELF的人用一种很巧妙的方式保存了下来,所有的数据都放在String table sections这个段里面,name就是表示这个节的名字对于String table section这个节的偏移.就是地址可以用下面的公式表示:
地址=String table节的首地址 SHT的name字段(SHT的name字段存储了这个节的名字对于String table节的首地址的偏移)
代码语言：javascript复制00000000
0000001b
.text
00000021
.rodata
00000029
.rodata.str1.8
00000038
.debug_info
00000044
.debug_abbrev
00000052
.debug_loc
0000005d
.debug_aranges
0000006c
.debug_line
00000078
.debug_str
00000083
.comment
0000008c
.riscv.attributes
0000009e
.debug_frame
000000ab
.debug_ranges
00000001
.symtab
00000009
.strtab
00000011
.shstrtab我们找到了字段的名字这个时候就可以根据名字找到symtab字段和strtab字段了.用下面的程序,遍历一遍所有的section,找到匹配的即可.elf_symtab存放symtab的内容,elf_strtab存放strtab的内容.
做法就是遍历所有section,找到每个section的名字比较即可.找到了对应的Section就把Section的首地址拿出来,取整个Section的内容.
代码语言：javascript复制这里有代码,但是被ban了加载完毕了之后我们就可以利用这些信息来找符号了.
我们已经知道了符号表的基本结构:
代码语言：javascript复制typedef struct {
Elf32_Word st_name;
Elf32_Addr st_value;
Elf32_Word st_size;
unsigned char st_info;
unsigned char st_other;
Elf32_Half st_shndx;
} Elf32_Sym;每一个符号都可以用一个结构表示,结构之间是线性地址分配的.
其中st_name的形式和之前SHT的name形式一样,也是这个符号对应的字符串对于strtab内容的第一个字节的字节地址的偏移,所以说名字就是strtab name
st_value存储的是符号值,一般是地址.
st_info是当前符号的值.可以用下面的宏来进行操作
代码语言：javascript复制#define ELF32_ST_BIND(i) ((i)>>4)
#define ELF32_ST_TYPE(i) ((i)&0xf)
#define ELF32_ST_INFO(b, t) (((b)<<4) ((t)&0xf))了解了这个结构之后我们就可以把这个Section的内容解释称一个Symbol结构的数组.
代码语言：javascript复制uint64 sym_num = symtab_size / sizeof(elf_sym);
elf_sym* symbols = (elf_sym*)elf_symtab;我们再来看看函数调用的时候的结构吧,我们这个实验函数是没有形式参数的,所以说函数在压栈的时候是只压两个元素的.
这个时候我们把符号表打印出来:其中第一项是函数的符号地址,第二项就是函数在栈中的大小,最后一个就是函数的名字
代码语言：javascript复制810002e0 car
810002ca print
810002e0 20 car
810002ca 22 print
810000c6 516 vsnprintf
810000a0 38 print_backtrace
8100031c 40 main
81000000 24 do_user_call
81000308 20 foo
81000018 98 printu
8100007a 38 exit
810002f4 20 bar这个时候我们找到栈顶地址,栈顶地址可以通过栈帧进行获得,就是s0.我们知道函数调用层级越低占堆栈地址越高,比如说main->foo->bar->car->print
我们不需要考虑内核栈.
首先是找到栈帧中栈顶寄存器的值,就是s0,然后经过推算找到对应函数的值,一开始首先要把tf 8来抵消depth这个元素来进行处理.接着我们就可以根据地址元素和每个符号对应元素的大小进行输出了.输出的方式如下:遍历符号表然后找到target匹配的结果输出即可.(当target与符号表里面的元素值大致一样即可.)
其中STT_FUNC是一种特别的宏,这个代表这个符号是函数.
代码语言：javascript复制这里有代码,但是被ban了基本的处理方式就是这样子的,在user_lib.c中实现函数,实现的方式就是进行系统调用,然后在sys_call里面完善do_syscall,就是加一个case而已,然后再syscall函数里面进行处理,这个时候交付给vmm.c,process.c都可以.
lab1_challenge2 打印异常代码行（难度：★★★★☆）
给定应用
- user/app_errorline.c（和lab1_2的应用一致）
1 /*
2 * Below is the given application for lab1_challenge2 (same as lab1_2).
3 * This app attempts to issue M-mode instruction in U-mode, and consequently raises an exception.
4 */
5
6 #include "user_lib.h"
7 #include "util/types.h"
8
9 int main(void) {
10 printu("Going to hack the system by running privilege instructions.n");
11 // we are now in U(user)-mode, but the "csrw" instruction requires M-mode privilege.
12 // Attempting to execute such instruction will raise illegal instruction exception.
13 asm volatile("csrw sscratch, 0");
14 exit(0);
15 }
16 以上程序试图在用户态读取在内核态才能读取的寄存器sscratch，因此此处会触发illegal instruction异常，你的任务是修改内核（包括machine文件夹下）的代码，使得用户程序在发生异常时，内核能够输出触发异常的用户程序的源文件名和对应代码行，如上面的应用预期输出如下：
代码语言：javascript复制In m_start, hartid:0
HTIF is available!
(Emulated) memory size: 2048 MB
Enter supervisor mode...
Application: obj/app_errorline
Application program entry point (virtual address): 0x0000000081000000
Switch to user mode...
Going to hack the system by running privilege instructions.
Runtime error at user/app_errorline.c:13
asm volatile("csrw sscratch, 0");
Illegal instruction!
System is shutting down with exit code -1.实验内容
本实验为挑战实验，基础代码将继承和使用lab1_3完成后的代码：
- （先提交lab1_3的答案，然后）切换到lab1_challenge2_errorline、继承lab1_3（注意，不是继承lab1_challenge1_backtrace！PKE的挑战实验之间无继承关联）中所做修改：
//切换到lab1_challenge2_errorline
$ git checkout lab1_challenge2_errorline
//继承lab1_3以及之前的答案
$ git merge lab1_3_irq -m "continue to work on lab1_challenge1"注意：**不同于基础实验，挑战实验的基础代码具有更大的不完整性，可能无法直接通过构造过程。**同样，不同于基础实验，我们在代码中也并未专门地哪些地方的代码需要填写，哪些地方的代码无须填写。这样，我们留给读者更大的“想象空间”。
- 本实验的具体要求为：通过修改PKE内核（包括machine文件夹下的代码），使得用户程序在发生异常时，内核能够输出触发异常的用户程序的源文件名和对应代码行。
- 注意：虽然在示例的app_errorline.c中只触发了非法指令异常，但最终测试时你的内核也应能够对其他会导致panic的异常和其他源文件输出正确的结果。
- 文件名规范：需要包含路径，如果是用户源程序发生的错误，路径为相对路径，如果是调用的标准库内发生的错误，路径为绝对路径。
- 为了降低挑战的难度，本实验在elf.c中给出了debug_line段的解析函数make_addr_line。这个函数接受三个参数，ctx为elf文件的上下文指针，这个可以参考文件中的其他函数；debug_line为指向.debug_line段数据的指针，你需要读取elf文件中名为.debug_line的段保存到缓冲区中，然后将缓冲区指针传入这个参数；length为.debug_line段数据的长度。
- 函数调用结束后，process结构体的dir、file、line三个指针会各指向一个数组，dir数组存储所有代码文件的文件夹路径字符串指针，如/home/abc/bcd的文件夹路径为/home/abc，本项目user文件夹下的app_errorline.c文件夹路径为user；file数组存储所有代码文件的文件名字符串指针以及其文件夹路径在dir数组中的索引；line数组存储所有指令地址，代码行号，文件名在file数组中的索引三者的映射关系。如某文件第3行为a = 0，被编译成地址为0x1234处的汇编代码li ax, 0和0x1238处的汇编代码sd 0(s0), ax。那么file数组中就包含两项，addr属性分别为0x1234和0x1238，line属性为3，file属性为“某文件”的文件名在file数组中的索引。
- 注意：dir、file、line三个数组会依次存储在debug_line数据缓冲区之后，dir数组和file数组的大小为64。所以如果你用静态数组来存储debug_line段数据，那么这个数组必须足够大；或者你也可以把debug_line直接放在程序所有需映射的段数据之后，这样可以保证有足够大的动态空间。
实验指导
- 为完成该挑战，需要利用用户程序编译时产生的调试信息，目前最广泛使用的调试信息格式是DWARF，可以参考这里了解其格式，该网站的参考文献中也给出了DWARF的完整文档地址，必要时可参考。
- 你对内核代码的修改可能包含以下内容：
- 修改读取elf文件的代码，找到包含调试信息的段，将其内容保存起来（可以保存在用户程序的地址空间中）
- 在适当的位置调用debug_line段解析函数，对调试信息进行解析，构造指令地址-源代码行号-源代码文件名的对应表，注意，连续行号对应的不一定是连续的地址，因为一条源代码可以对应多条指令。
- 在异常中断处理函数中，通过相应寄存器找到触发异常的指令地址，然后在上述表中查找地址对应的源代码行号和文件名输出
实验解析
首先我们观察一下process的结构:
代码语言：javascript复制// code file struct, including directory index and file name char pointer
typedef struct {
uint64 dir; char *file;
} code_file;
// address-line number-file name table
typedef struct {
uint64 addr, line, file;
} addr_line;
// the extremely simple definition of process, used for begining labs of PKE
typedef struct process {
// pointing to the stack used in trap handling.
uint64 kstack;
// trapframe storing the context of a (User mode) process.
trapframe* trapframe;
char *debugline; char **dir; code_file *file; addr_line *line; int line_ind;
}process;多出来五个元素,一个是debugline,一个是dir,一个是code_file,一个是line,最后就是line_ind,了解这五个元素非常有必要.
首先就是debugline,其实本质上就是.debugline这个section的所有内容.
所以说函数的第一步就是找到debugline这个段的内容.
代码语言：javascript复制 1 if (!strcmp(elf_shstrtab sh_addr.name, ".debugline")) {
2 if (elf_fpread(ctx, elf_debug_line, sh_addr.size, sh_addr.offset) != sh_addr.size)
3 return EL_EIO;
4 break;
5 }还是和lab1_1一样的做法,找到”.debugline”的存在,把所有的东西塞给老师提供的make_addr_size()函数里面.
首先是dir,dir是一个二级指针,指向了一个存放指针的数组,这些数组的元素是指针,指向了一个字符串,存储的都是所有代码文件可能存在的文件夹的名字.
举个例子,比如说我们的PKE.*dir可能指向user ,*(dir 1)可能指向kernel.
code_file就是存储了所有代码文件的信息,有多少个.c和.h文件,code_file这个数组就有多少元素.每个代码文件所对应的结构体保存了所在的文件夹的信息(索引),还保留了代码文件本身的信息.
addr_line就是保存了所有指令的指令地址,代码行号和这一行代码对应着哪一个文件里面的(具体在哪一行.c,.h)可以通过file和line两个元素确定这个指令对于哪个文件的哪一行.
接着就是处理中断了,这一次处理的中断是在M态下进行处理,我们对Illegal instructions的中断进行一个更改,添加一个对于print_error函数的调用,实现print_error就非常重要
下面介绍思路:
首先第一步,使用read_csr函数找到断点,断点的位置就是在mepc这个地方.
第二步就是找到断点这条指令对应的addr_line结构体,用while循环即可.
找到了结构体就可以知道了文件夹的名字,代码的名字(因为存的是索引地址),这个时候就可以构造出path了,就是文件的名字,已知addr_line,可以找到对应的code_file结构体,根据code_file结构体就可以找到dir的位置.(path是一个char型数组)
代码语言：javascript复制 size_t dir_len = strlen((char*)current->dir[current->file[illegal_addr_line->file].dir]);
size_t file_name_len = strlen((char*)current->file[illegal_addr_line->file].file);
size_t path_len = dir_len file_name_len 1;
char path[path_len 1];
strcpy(path, current->dir[current->file[illegal_addr_line->file].dir]);
path[dir_len] = '/';
strcpy(path dir_len 1, current->file[illegal_addr_line->file].file);
path[path_len] = ' ';接着就是找到对应的代码了,这个时候我们可以使用spike_file相关操作来进行文件读取(因为已经知道路径了)
这个时候就可以用下面俩函数
spike_file_t* spike_file_open(path, O_RDONLY, 0);//打开文件
读了多长 spike_file_pread(读取文件的文件指针,读到哪里,最长读多长,从哪里开始读)
由于我们赖皮地知道了代码在第几行,所以说打开这个文件,读前面n-1行的元素,找到偏移地址就好了.(有多赖皮呢?我们甚至可以找到check的程序,我嫖下来给大家观看)
代码语言：javascript复制#include "user_lib.h"
int main(void) {
printu("Going to hack the system by running privilege instructions.n");
// we are now in U(user)-mode, but the "csrw" instruction requires M-mode privilege.
// Attempting to execute such instruction will raise illegal instruction exception.
asm volatile("csrw sscratch, 0");
exit(0);
}21
0
16
74
0
0
86
85
35还输出每一行代码的ASCII含量,具体怎么统计的,请看下面的代码
代码语言：javascript复制 这里有代码,但是被ban了首先我们先用pread函数读取127个元素,然后用while循环处理掉这一行的代码,这样就少了一行,下一次读取就从这一行的’n’的下一个ASCII开始读(程序中inner_off就代表这一行除了’n’有几个字符),那么下一次读取就从inner_off 1个字符后开始,刚好处理一行.
比如说第一次处理code就是这个:
代码语言：javascript复制这里有代码,但是被ban了下一次处理code就变成了这个,整体往前前进了一行:
代码语言：javascript复制这里有代码,但是被ban了到了这一步,前面的line-1行已经全部被处理了,那么我就只要第line行的字符就可以啦,处理方法如下:(处理到这一步code的内容已经整体前进了line-1行,现在code的第一个字符是异常代码的第一个ASCII,简单点说就是前面line-1行的元素已经全部处理完了),处理的方式就是利用offset
这里有代码,但是被ban了
lab2_challenge1 复杂缺页异常（难度：★☆☆☆☆）
给定应用
- user/app_sum_sequence.c
1 /*
2 * The application of lab2_4.
3 * Based on application of lab2_3.
4 */
5
6 #include "user_lib.h"
7 #include "util/types.h"
8
9 //
10 // compute the summation of an arithmetic sequence. for a given "n", compute
11 // result = n (n-1) (n-2) ... 0
12 // sum_sequence() calls itself recursively till 0. The recursive call, however,
13 // may consume more memory (from stack) than a physical 4KB page, leading to a page fault.
14 // PKE kernel needs to improved to handle such page fault by expanding the stack.
15 //
16 uint64 sum_sequence(uint64 n, int *p) {
17 if (n == 0)
18 return 0;
19 else
20 return *p=sum_sequence( n-1, p 1 ) n;
21 }
22
23 int main(void) {
24 // FIRST, we need a large enough "n" to trigger pagefaults in the user stack
25 uint64 n = 1024;
26
27 // alloc a page size array(int) to store the result of every step
28 // the max limit of the number is 4kB/4 = 1024
29
30 // SECOND, we use array out of bound to trigger pagefaults in an invalid address
31 int *ans = (int *)naive_malloc();
32
33 printu("Summation of an arithmetic sequence from 0 to %ld is: %ld n", n, sum_sequence(n 1, ans) );
34
35 exit(0);
36 }程序思路基本同lab2_3一致，对给定n计算0到n的和，但要求将每一步递归的结果保存在数组ans中。创建数组时，我们使用了当前的malloc函数申请了一个页面（4KB）的大小，对应可以存储的个数上限为1024。在函数调用时，我们试图计算1025求和，首先由于n足够大，所以在函数递归执行时会触发用户栈的缺页，你需要对其进行正确处理，确保程序正确运行；其次，1025在最后一次计算时会访问数组越界地址，由于该处虚拟地址尚未有对应的物理地址映射，因此属于非法地址的访问，这是不被允许的，对于这种缺页异常，应该提示用户并退出程序执行。如上的应用预期输出如下：
代码语言：javascript复制In m_start, hartid:0
HTIF is available!
(Emulated) memory size: 2048 MB
Enter supervisor mode...
PKE kernel start 0x0000000080000000, PKE kernel end: 0x000000008000e000, PKE kernel size: 0x000000000000e000 .
free physical memory address: [0x000000008000e000, 0x0000000087ffffff]
kernel memory manager is initializing ...
KERN_BASE 0x0000000080000000
physical address of _etext is: 0x0000000080004000
kernel page table is on
User application is loading.
user frame 0x0000000087fbc000, user stack 0x000000007ffff000, user kstack 0x0000000087fbb000
Application: ./obj/app_sum_sequence
Application program entry point (virtual address): 0x00000000000100da
Switching to user mode...
handle_page_fault: 000000007fffdff8
handle_page_fault: 000000007fffcff8
handle_page_fault: 000000007fffbff8
handle_page_fault: 000000007fffaff8
handle_page_fault: 000000007fff9ff8
handle_page_fault: 000000007fff8ff8
handle_page_fault: 000000007fff7ff8
handle_page_fault: 000000007fff6ff8
handle_page_fault: 0000000000401000
this address is not available!
System is shutting down with exit code -1.根据结果可以看出：前八个缺页是由于函数递归调用引起的，而最后一个缺页是对动态申请的数组进行越界访问造成的，访问非法地址，程序报错并退出。
实验内容
本实验为挑战实验，基础代码将继承和使用lab2_3完成后的代码：
- （先提交lab2_3的答案，然后）切换到lab2_challenge1_pagefaults、继承lab2_3中所做修改：
//切换到lab2_challenge1_pagefault
$ git checkout lab2_challenge1_pagefaults
//继承lab2_3以及之前的答案
$ git merge lab2_3_pagefault -m "continue to work on lab2_challenge1"注意：**不同于基础实验，挑战实验的基础代码具有更大的不完整性，可能无法直接通过构造过程。**同样，不同于基础实验，我们在代码中也并未专门地哪些地方的代码需要填写，哪些地方的代码无须填写。这样，我们留给读者更大的“想象空间”。
- 本实验的具体要求为：通过修改PKE内核（包括machine文件夹下的代码），使得对于不同情况的缺页异常进行不同的处理。
- 文件名规范：需要包含路径，如果是用户源程序发生的错误，路径为相对路径，如果是调用的标准库内发生的错误，路径为绝对路径。
实验指导
- 你对内核代码的修改可能包含以下内容：
- 修改进程的数据结构以对虚拟地址空间进行监控。
- 修改kernel/strap.c中的异常处理函数。对于合理的缺页异常，扩大内核栈大小并为其映射物理块；对于非法地址缺页，报错并退出程序。
实验解析
根据实验解析我们可以知道:我们首先要对虚拟地址空间进行监控,这个时候我们设置一个数据元素,假设为malloc_stack_pages来代表我们申请了多少块页.(这个元素一开始为0,每发生一次缺页中断我们就申请一块页)
如果是正常的缺页中断,那么我们可以根据lab2_3的指示进行处理.
如果是数组越界,那么编译器得到的访问地址必定相差很大,那么我们可以这样做,判断当前出现缺页中断的虚地址的地址是不是在可控的范围内,如果可控就进行中断,如果不可控就不做,那么我们只需要在处理缺页中断的地方添加上一段就可以:
就这么简单.
lab2_challenge2 堆空间管理 （难度：★★★★☆）
给定应用
- user/app_singlepageheap.c
1 /*
2 * Below is the given application for lab2_challenge2_singlepageheap.
3 * This app performs malloc memory.
4 */
5
6 #include "user_lib.h"
7 #include "util/types.h"
8 #include "util/string.h"
9 int main(void) {
10
11 char str[20] = "hello world.";
12 char *m = (char *)better_malloc(100);
13 char *p = (char *)better_malloc(50);
14 if((uint64)p - (uint64)m > 512 ){
15 printu("you need to manage the vm space precisely!");
16 exit(-1);
17 }
18 better_free((void *)m);
19
20 strcpy(p,str);
21 printu("%sn",p);
22 exit(0);
23 return 0;
24 }以上程序先利用better_malloc分别申请100和50个字节的一个物理页的内存，然后使用better_free释放掉100个字节，向50个字节中复制一串字符串，进行输出。原本的pke中malloc的实现是非常简化的（一次直接分配一个页面），你的挑战任务是修改内核(包括machine文件夹下)的代码，使得应用程序的malloc能够在一个物理页中分配，并对各申请块进行合理的管理，如上面的应用预期输出如下：
代码语言：javascript复制In m_start, hartid:0
HTIF is available!
(Emulated) memory size: 2048 MB
Enter supervisor mode...
PKE kernel start 0x0000000080000000, PKE kernel end: 0x0000000080008000, PKE kernel size: 0x0000000000008000 .
free physical memory address: [0x0000000080008000, 0x0000000087ffffff]
kernel memory manager is initializing ...
KERN_BASE 0x0000000080000000
physical address of _etext is: 0x0000000080005000
kernel page table is on
User application is loading.
user frame 0x0000000087fbc000, user stack 0x000000007ffff000, user kstack 0x0000000087fbb000
Application: obj/app_singlepageheap
Application program entry point (virtual address): 0x00000000000100b0
Switch to user mode...
hello world.
User exit with code:0.
System is shutting down with exit code 0.通过应用程序和对应的预期结果可以看出：两次申请的空间在同一页面，并且释放第一块时，不会释放整个页面，所以需要你设计合适的数据结构对各块进行管理，使得better_malloc申请的空间更加“紧凑”。
实验内容
本实验为挑战实验，基础代码将继承和使用lab2_challenge1完成后的代码：
- （先提交lab2_3的答案，然后）切换到lab2_challenge2、继承lab2_3中所做修改：
//切换到lab2_challenge2_singlepageheap
$ git checkout lab2_challenge2_singlepageheap
//继承lab2_challenge1以及之前的答案
$ git merge lab2_3_pagefault -m "continue to work on lab2_challenge2"注意：**不同于基础实验，挑战实验的基础代码具有更大的不完整性，可能无法直接通过构造过程。**同样，不同于基础实验，我们在代码中也并未专门地哪些地方的代码需要填写，哪些地方的代码无须填写。这样，我们留给读者更大的“想象空间”。
- 本实验的具体要求为：通过修改PKE内核（包括machine文件下的代码），实现优化后的malloc函数，使得应用程序两次申请块在同一页面，并且能够正常输出存入第二块中的字符串”hello world”。
- 文件名规范：需要包含路径，如果是用户源程序发生的错误，路径为相对路径，如果是调用的标准库内发生的错误，路径为绝对路径。
实验指导
- 为完成该挑战，你需要对进程的虚拟地址空间进行管理，建议参考Linux的内存分配策略从而实现malloc。
- 你对内核代码的修改可能包含以下内容：
- 增加内存控制块数据结构对分配的内存块进行管理。
- 修改process的数据结构以扩展对虚拟地址空间的管理，后续对于heap的扩展，需要对新增的虚拟地址添加对应的物理地址映射。
- 设计函数对进程的虚拟地址空间进行管理，借助以上内容具体实现heap扩展。
- 设计malloc函数和free函数对内存块进行管理。
实验解析
实验要求我们每一次malloc不是申请一个页,每一次malloc都检查一遍目前该进程已经有的内存空间,在这个内存空间中进行地址分配.
首先我们知道这个是分块内存,所以说我们可以申明块的结构和存储一堆块的数组结构.
代码语言：javascript复制typedef struct mem_block{
int start;
int end;
}mem_block;
mem_block mem_blocks[16];
mem_blocks[0].start//当前分块的第一个虚拟地址
mem_blocks[0].end//最后一个地址
mem_blocks_numbers ;//几个块这个时候由于只有一个进程,这个数据结构就只有一个,设置在进程块也可以,设置在vmm.h也可以.
如果是申明的第一个块,首先先申请需要的物理块,接着初始化mem_blocks数组的第一个元素(这里偷懒了,只申请了一个块)
代码语言：javascript复制这里有代码,但是被ban了这里是用最佳适应算法,如果一个块是最小的,就要把这个块放在第一个位置,然后把其他的块都往后移动一格.
代码语言：javascript复制这里有代码,但是被ban了如果不是最小的,就找到最适合这个块放置的位置,找到位置就是前面比我小,后面比我大,后面的先往后移动一位,这个块就放在这个空出来的位置上.
代码语言：javascript复制这里有代码,但是被ban了最后先判断一下有没有越界,没有越界就继续做,如果越界的话就要继续申请物理块然后把块页转化信息写进页表中.
代码语言：javascript复制这里有代码,但是被ban了接着就是到达最后了,最后的情况就是这个是最大的块,就直接插入到最后一个.反正插入到最后一个是最简单的,直接默默地走在最后一个即可.
接着就是free,我们需要通过二分查找找到传进来的free地址是否能和某一个块的首地址匹配上.
代码语言：javascript复制这里有代码,但是被ban了如果匹配不上就panic,如果匹配上了就做接下来的free操作:
代码语言：javascript复制这里有代码,但是被ban了首先第一步,看看free之后是不是能够空出一整个页来,如果能空出一整页的话,这一整页就可以释放了,接着就是把这一个内存块从数组中抽出来,后面的元素一一往前移动.
由于数据集太弱了,狗都能过,所以说不代表我这个方法一定正确.
lab3_challenge1 进程等待和数据段复制（难度：★★☆☆☆）
给定应用
- user/app_wait.c
1 /*
2 * This app fork a child process, and the child process fork a grandchild process.
3 * every process waits for its own child exit then prints.
4 * Three processes also write their own global variables "flag"
5 * to different values.
6 */
7
8 #include "user/user_lib.h"
9 #include "util/types.h"
10
11 int flag;
12 int main(void) {
13 flag = 0;
14 int pid = fork();
15 if (pid == 0) {
16 flag = 1;
17 pid = fork();
18 if (pid == 0) {
19 flag = 2;
20 printu("Grandchild process end, flag = %d.n", flag);
21 } else {
22 wait(pid);
23 printu("Child process end, flag = %d.n", flag);
24 }
25 } else {
26 wait(-1);
27 printu("Parent process end, flag = %d.n", flag);
28 }
29 exit(0);
30 return 0;
31 }wait系统调用是进程管理中一个非常重要的系统调用，它主要有两大功能：
- 当一个进程退出之后，它所占用的资源并不一定能够立即回收，比如该进程的内核栈目前就正用来进行系统调用处理。对于这种问题，一种典型的做法是当进程退出的时候内核立即回收一部分资源并将该进程标记为僵尸进程。由父进程调用wait函数的时候再回收该进程的其他资源。
- 父进程的有些操作需要子进程运行结束后获得结果才能继续执行，这时wait函数起到进程同步的作用。
在以上程序中，父进程把flag变量赋值为0，然后fork生成一个子进程，接着通过wait函数等待子进程的退出。子进程把自己的变量flag赋值为1，然后fork生成孙子进程，接着通过wait函数等待孙子进程的退出。孙子进程给自己的变量flag赋值为2并在退出时输出信息，然后子进程退出时输出信息，最后父进程退出时输出信息。由于fork之后父子进程的数据段相互独立（同一虚拟地址对应不同的物理地址），子进程对全局变量的赋值不影响父进程全局变量的值，因此结果如下：
代码语言：javascript复制In m_start, hartid:0
HTIF is available!
(Emulated) memory size: 2048 MB
Enter supervisor mode...
PKE kernel start 0x0000000080000000, PKE kernel end: 0x0000000080009000, PKE kernel size: 0x0000000000009000 .
free physical memory address: [0x0000000080009000, 0x0000000087ffffff]
kernel memory manager is initializing ...
KERN_BASE 0x0000000080000000
physical address of _etext is: 0x0000000080005000
kernel page table is on
Switch to user mode...
in alloc_proc. user frame 0x0000000087fbc000, user stack 0x000000007ffff000, user kstack 0x0000000087fbb000
User application is loading.
Application: obj/app_wait
CODE_SEGMENT added at mapped info offset:3
DATA_SEGMENT added at mapped info offset:4
Application program entry point (virtual address): 0x00000000000100b0
going to insert process 0 to ready queue.
going to schedule process 0 to run.
User call fork.
will fork a child from parent 0.
in alloc_proc. user frame 0x0000000087fae000, user stack 0x000000007ffff000, user kstack 0x0000000087fad000
do_fork map code segment at pa:0000000087fb2000 of parent to child at va:0000000000010000.
going to insert process 1 to ready queue.
going to schedule process 1 to run.
User call fork.
will fork a child from parent 1.
in alloc_proc. user frame 0x0000000087fa1000, user stack 0x000000007ffff000, user kstack 0x0000000087fa0000
do_fork map code segment at pa:0000000087fb2000 of parent to child at va:0000000000010000.
going to insert process 2 to ready queue.
going to schedule process 2 to run.
Grandchild process end, flag = 2.
User exit with code:0.
going to insert process 1 to ready queue.
going to schedule process 1 to run.
Child process end, flag = 1.
User exit with code:0.
going to insert process 0 to ready queue.
going to schedule process 0 to run.
Parent process end, flag = 0.
User exit with code:0.
no more ready processes, system shutdown now.
System is shutting down with exit code 0.实验内容
本实验为挑战实验，基础代码将继承和使用lab3_3完成后的代码：
- （先提交lab3_3的答案，然后）切换到lab3_challenge1_wait、继承lab3_3中所做修改：
//切换到lab3_challenge1_wait
$ git checkout lab3_challenge1_wait
//继承lab3_3以及之前的答案
$ git merge lab3_3_rrsched -m "continue to work on lab3_challenge1"注意：不同于基础实验，挑战实验的基础代码具有更大的不完整性，可能无法直接通过构造过程。 同样，不同于基础实验，我们在代码中也并未专门地哪些地方的代码需要填写，哪些地方的代码无须填写。这样，我们留给读者更大的“想象空间”。
- 本实验的具体要求为：
- 通过修改PKE内核和系统调用，为用户程序提供wait函数的功能，wait函数接受一个参数pid：
- 当pid为-1时，父进程等待任意一个子进程退出即返回子进程的pid；
- 当pid大于0时，父进程等待进程号为pid的子进程退出即返回子进程的pid；
- 如果pid不合法或pid大于0且pid对应的进程不是当前进程的子进程，返回-1。
- 补充do_fork函数，实验3_1实现了代码段的复制，你需要继续实现数据段的复制并保证fork后父子进程的数据段相互独立。
- 通过修改PKE内核和系统调用，为用户程序提供wait函数的功能，wait函数接受一个参数pid：
- 注意：最终测试程序可能和给出的用户程序不同，但都只涉及wait函数、fork函数和全局变量读写的相关操作。
实验指导
- 你对内核代码的修改可能包含添加系统调用、在内核中实现wait函数的功能以及对do_fork函数的完善。
实验解析
首先第一步,我们要在do_fork函数中添加关于数据段的支持,那么在复制的时候只需要添加case DATA_SEGMENT的处理就可以.
对于代码段,我们是直接进行复制,虚拟地址直接合并的,如下面程序所示.
代码语言：javascript复制 这里有代码,但是被ban了就直接在子进程的虚地址转换表中添加父进程的代码段首地址和父进程的代码段首地址对应的实地址之间的映射,把父进程的实地址复制给子进程
但是对于数据段,父进程和子进程是不共享的,所以说要生成申请一个新的页给子进程.所以说虚地址是互通的,但是实地址不是互通的.改正成:
代码语言：javascript复制 这里有代码,但是被ban了对于等待的处理.我们首先先判断是指定一个儿子还是指定所有的儿子.
这个时候我们在process数据结构里面定义一个新的元素,这个元素就是blockmap,就是等待谁结束停止阻塞,由于一个进程可以等待多个进程,我们做一个处理,就是第26位为1代表这个进程在等待pid==26的进程结束.
所以说我们可以利用parent的结构来进行blockmap的处理,当某个进程的parent是当前进程,代表这个进程是你的儿子,所以说我们就可以指定,(blockmap一定程度上记录着儿子的信息.) 可以是blockmap |= 1<<pid
代码语言：javascript复制这里有代码,但是被ban了那对于所有的进程呢?一样的的嘛,不过少了特判和break
那么对于exit也要进行改变,当一个进程结束的时候有可能会通知给其他进程.?代表这个进程是某个进程的儿子,某个进程正在等待您结束呢?用位运算就可以完成.
代码语言：javascript复制 if (?) != 0 && proc->parent->pid == procs[i].pid && procs[i].status == BLOCKED) {
procs[i].status = READY;
insert_to_ready_queue(&procs[i]);
}lab3_challenge2 实现信号量（难度：★★★☆☆）
给定应用
- user/app_semaphore.c
1 /*
2 * This app create two child process.
3 * Use semaphores to control the order of
4 * the main process and two child processes print info.
5 */
6 #include "user/user_lib.h"
7 #include "util/types.h"
8
9 int main(void) {
10 int main_sem, child_sem[2];
11 main_sem = sem_new(1);
12 for (int i = 0; i < 2; i ) child_sem[i] = sem_new(0);
13 int pid = fork();
14 if (pid == 0) {
15 pid = fork();
16 for (int i = 0; i < 10; i ) {
17 sem_P(child_sem[pid == 0]);
18 printu("Child%d print %dn", pid == 0, i);
19 if (pid != 0) sem_V(child_sem[1]); else sem_V(main_sem);
20 }
21 } else {
22 for (int i = 0; i < 10; i ) {
23 sem_P(main_sem);
24 printu("Parent print %dn", i);
25 sem_V(child_sem[0]);
26 }
27 }
28 exit(0);
29 return 0;
30 }以上程序通过信号量的增减，控制主进程和两个子进程的输出按主进程，第一个子进程，第二个子进程，主进程，第一个子进程，第二个子进程……这样的顺序轮流输出，如上面的应用预期输出如下：
代码语言：javascript复制In m_start, hartid:0
HTIF is available!
(Emulated) memory size: 2048 MB
Enter supervisor mode...
PKE kernel start 0x0000000080000000, PKE kernel end: 0x0000000080009000, PKE kernel size: 0x0000000000009000 .
free physical memory address: [0x0000000080009000, 0x0000000087ffffff]
kernel memory manager is initializing ...
KERN_BASE 0x0000000080000000
physical address of _etext is: 0x0000000080005000
kernel page table is on
Switch to user mode...
in alloc_proc. user frame 0x0000000087fbc000, user stack 0x000000007ffff000, user kstack 0x0000000087fbb000
User application is loading.
Application: obj/app_semaphore
CODE_SEGMENT added at mapped info offset:3
DATA_SEGMENT added at mapped info offset:4
Application program entry point (virtual address): 0x00000000000100b0
going to insert process 0 to ready queue.
going to schedule process 0 to run.
User call fork.
will fork a child from parent 0.
in alloc_proc. user frame 0x0000000087fae000, user stack 0x000000007ffff000, user kstack 0x0000000087fad000
do_fork map code segment at pa:0000000087fb2000 of parent to child at va:0000000000010000.
going to insert process 1 to ready queue.
Parent print 0
going to schedule process 1 to run.
User call fork.
will fork a child from parent 1.
in alloc_proc. user frame 0x0000000087fa2000, user stack 0x000000007ffff000, user kstack 0x0000000087fa1000
do_fork map code segment at pa:0000000087fb2000 of parent to child at va:0000000000010000.
going to insert process 2 to ready queue.
Child0 print 0
going to schedule process 2 to run.
Child1 print 0
going to insert process 0 to ready queue.
going to schedule process 0 to run.
Parent print 1
going to insert process 1 to ready queue.
going to schedule process 1 to run.
Child0 print 1
going to insert process 2 to ready queue.
going to schedule process 2 to run.
Child1 print 1
going to insert process 0 to ready queue.
going to schedule process 0 to run.
Parent print 2
going to insert process 1 to ready queue.
going to schedule process 1 to run.
Child0 print 2
going to insert process 2 to ready queue.
going to schedule process 2 to run.
Child1 print 2
going to insert process 0 to ready queue.
going to schedule process 0 to run.
Parent print 3
going to insert process 1 to ready queue.
going to schedule process 1 to run.
Child0 print 3
going to insert process 2 to ready queue.
going to schedule process 2 to run.
Child1 print 3
going to insert process 0 to ready queue.
going to schedule process 0 to run.
Parent print 4
going to insert process 1 to ready queue.
going to schedule process 1 to run.
Child0 print 4
going to insert process 2 to ready queue.
going to schedule process 2 to run.
Child1 print 4
going to insert process 0 to ready queue.
going to schedule process 0 to run.
Parent print 5
going to insert process 1 to ready queue.
going to schedule process 1 to run.
Child0 print 5
going to insert process 2 to ready queue.
going to schedule process 2 to run.
Child1 print 5
going to insert process 0 to ready queue.
going to schedule process 0 to run.
Parent print 6
going to insert process 1 to ready queue.
going to schedule process 1 to run.
Child0 print 6
going to insert process 2 to ready queue.
going to schedule process 2 to run.
Child1 print 6
going to insert process 0 to ready queue.
going to schedule process 0 to run.
Parent print 7
going to insert process 1 to ready queue.
going to schedule process 1 to run.
Child0 print 7
going to insert process 2 to ready queue.
going to schedule process 2 to run.
Child1 print 7
going to insert process 0 to ready queue.
going to schedule process 0 to run.
Parent print 8
going to insert process 1 to ready queue.
going to schedule process 1 to run.
Child0 print 8
going to insert process 2 to ready queue.
going to schedule process 2 to run.
Child1 print 8
going to insert process 0 to ready queue.
going to schedule process 0 to run.
Parent print 9
going to insert process 1 to ready queue.
User exit with code:0.
going to schedule process 1 to run.
Child0 print 9
going to insert process 2 to ready queue.
User exit with code:0.
going to schedule process 2 to run.
Child1 print 9
User exit with code:0.
no more ready processes, system shutdown now.
System is shutting down with exit code 0.实验内容
本实验为挑战实验，基础代码将继承和使用lab3_3完成后的代码：
- （先提交lab3_3的答案，然后）切换到lab3_challenge2_semaphore、继承lab3_3中所做修改：
//切换到lab3_challenge2_semaphore
$ git checkout lab3_challenge2_semaphore
//继承lab3_3以及之前的答案
$ git merge lab3_3_rrsched -m "continue to work on lab3_challenge1"注意：不同于基础实验，挑战实验的基础代码具有更大的不完整性，可能无法直接通过构造过程。 同样，不同于基础实验，我们在代码中也并未专门地哪些地方的代码需要填写，哪些地方的代码无须填写。这样，我们留给读者更大的“想象空间”。
- 本实验的具体要求为：通过修改PKE内核和系统调用，为用户程序提供信号量功能。
- 注意：最终测试程序可能和给出的用户程序不同，但都只涉及信号量的相关操作。
实验指导
- 你对内核代码的修改可能包含以下内容：
- 添加系统调用，使得用户对信号量的操作可以在内核态处理
- 在内核中实现信号量的分配、释放和PV操作，当P操作处于等待状态时能够触发进程调度
实验解析
我觉得lab3_1比lab3_2难一点,因为3_2就是一个模拟题.
在主程序中用编号来模拟信号灯的序号,我们在程序中也同样做.
首先用一个数组来代表信号灯的值,再用一个数组来代表等待队列尾(上学期学过信号灯=值 一个等待队列.)
如果新建一个新的信号灯,那么就是初始化等待队列而已(判断初值不能为负),并且维护一个值,代表当前已经生成的信号灯的数量.(方便我们对数组的某一个元素初始化).
P操作:就是先-1,如果小于0的话,就让这个进程阻塞,放入到等待队列队首
V操作:先 1,如果等待队列不为空的话就让等待队列队首投入就绪状态.(出队)
由于process结构体有一个元素就是等待队列下一个元素,所以说我们可以进行模拟
