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层,预期的输出为:
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_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内核的完善应包含以下内容:
提示:
理论上,我们希望你了解函数调用时栈帧的结构,通过fp寄存器(s0)寻找各个栈帧;然而,编译器一般会优化掉fp,使得它的值始终为0,在发生函数调用时也不保存这个寄存器,实验的Makefile已经使用-fno-omit-frame-pointer
禁止了此项优化。
第一章中的 举例 程序中,函数调用的栈帧(此时 bar 函数作为叶子调用函数)类似下图:
注意,函数调用的叶子结点一般不会将ra保存到栈中;
如果你发现使用fp追踪栈底难度太大,可以假设用户程序的函数调用产生的栈帧总是定长的;为了获得这个长度,你可以:
$ 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文件中的字节偏移位置等等。
// 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的类型变量)
这里有代码,但是被ban了
我们找到了字符串表的头结构,顺理成章地可以根据offset成员获得字符串表本身的结构.用下面的程序获得之,并存入到elf_shstrtab里面.其中elf_shstrtab存放着这个section所有的内容.
这里有代码,但是被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节的首地址的偏移)
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的内容.
这里有代码,但是被ban了
加载完毕了之后我们就可以利用这些信息来找符号了.
我们已经知道了符号表的基本结构:
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是当前符号的值.可以用下面的宏来进行操作
#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结构的数组.
uint64 sym_num = symtab_size / sizeof(elf_sym);
elf_sym* symbols = (elf_sym*)elf_symtab;
我们再来看看函数调用的时候的结构吧,我们这个实验函数是没有形式参数的,所以说函数在压栈的时候是只压两个元素的.
这个时候我们把符号表打印出来:其中第一项是函数的符号地址,第二项就是函数在栈中的大小,最后一个就是函数的名字
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是一种特别的宏,这个代表这个符号是函数.
这里有代码,但是被ban了
基本的处理方式就是这样子的,在user_lib.c中实现函数,实现的方式就是进行系统调用,然后在sys_call里面完善do_syscall,就是加一个case而已,然后再syscall函数里面进行处理,这个时候交付给vmm.c,process.c都可以.
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文件夹下)的代码,使得用户程序在发生异常时,内核能够输出触发异常的用户程序的源文件名和对应代码行,如上面的应用预期输出如下:
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_challenge2_errorline
$ git checkout lab1_challenge2_errorline
//继承lab1_3以及之前的答案
$ git merge lab1_3_irq -m "continue to work on lab1_challenge1"
注意:**不同于基础实验,挑战实验的基础代码具有更大的不完整性,可能无法直接通过构造过程。**同样,不同于基础实验,我们在代码中也并未专门地哪些地方的代码需要填写,哪些地方的代码无须填写。这样,我们留给读者更大的“想象空间”。
首先我们观察一下process的结构:
// 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这个段的内容.
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型数组)
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] = '\0';
接着就是找到对应的代码了,这个时候我们可以使用spike_file相关操作来进行文件读取(因为已经知道路径了)
这个时候就可以用下面俩函数
spike_file_t* spike_file_open(path, O_RDONLY, 0);//打开文件
读了多长 spike_file_pread(读取文件的文件指针,读到哪里,最长读多长,从哪里开始读)
由于我们赖皮地知道了代码在第几行,所以说打开这个文件,读前面n-1行的元素,找到偏移地址就好了.(有多赖皮呢?我们甚至可以找到check的程序,我嫖下来给大家观看)
#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含量,具体怎么统计的,请看下面的代码
这里有代码,但是被ban了
首先我们先用pread函数读取127个元素,然后用while循环处理掉这一行的代码,这样就少了一行,下一次读取就从这一行的’\n’的下一个ASCII开始读(程序中inner_off就代表这一行除了’\n’有几个字符),那么下一次读取就从inner_off+1个字符后开始,刚好处理一行.
比如说第一次处理code就是这个:
这里有代码,但是被ban了
下一次处理code就变成了这个,整体往前前进了一行:
这里有代码,但是被ban了
到了这一步,前面的line-1行已经全部被处理了,那么我就只要第line行的字符就可以啦,处理方法如下:(处理到这一步code的内容已经整体前进了line-1行,现在code的第一个字符是异常代码的第一个ASCII,简单点说就是前面line-1行的元素已经全部处理完了),处理的方式就是利用offset
这里有代码,但是被ban了
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在最后一次计算时会访问数组越界地址,由于该处虚拟地址尚未有对应的物理地址映射,因此属于非法地址的访问,这是不被允许的,对于这种缺页异常,应该提示用户并退出程序执行。如上的应用预期输出如下:
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_challenge1_pagefault
$ git checkout lab2_challenge1_pagefaults
//继承lab2_3以及之前的答案
$ git merge lab2_3_pagefault -m "continue to work on lab2_challenge1"
注意:**不同于基础实验,挑战实验的基础代码具有更大的不完整性,可能无法直接通过构造过程。**同样,不同于基础实验,我们在代码中也并未专门地哪些地方的代码需要填写,哪些地方的代码无须填写。这样,我们留给读者更大的“想象空间”。
根据实验解析我们可以知道:我们首先要对虚拟地址空间进行监控,这个时候我们设置一个数据元素,假设为malloc_stack_pages来代表我们申请了多少块页.(这个元素一开始为0,每发生一次缺页中断我们就申请一块页)
如果是正常的缺页中断,那么我们可以根据lab2_3的指示进行处理.
如果是数组越界,那么编译器得到的访问地址必定相差很大,那么我们可以这样做,判断当前出现缺页中断的虚地址的地址是不是在可控的范围内,如果可控就进行中断,如果不可控就不做,那么我们只需要在处理缺页中断的地方添加上一段就可以:
就这么简单.
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("%s\n",p);
22 exit(0);
23 return 0;
24 }
以上程序先利用better_malloc分别申请100和50个字节的一个物理页的内存,然后使用better_free释放掉100个字节,向50个字节中复制一串字符串,进行输出。原本的pke中malloc的实现是非常简化的(一次直接分配一个页面),你的挑战任务是修改内核(包括machine文件夹下)的代码,使得应用程序的malloc能够在一个物理页中分配,并对各申请块进行合理的管理,如上面的应用预期输出如下:
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_challenge2_singlepageheap
$ git checkout lab2_challenge2_singlepageheap
//继承lab2_challenge1以及之前的答案
$ git merge lab2_3_pagefault -m "continue to work on lab2_challenge2"
注意:**不同于基础实验,挑战实验的基础代码具有更大的不完整性,可能无法直接通过构造过程。**同样,不同于基础实验,我们在代码中也并未专门地哪些地方的代码需要填写,哪些地方的代码无须填写。这样,我们留给读者更大的“想象空间”。
实验要求我们每一次malloc不是申请一个页,每一次malloc都检查一遍目前该进程已经有的内存空间,在这个内存空间中进行地址分配.
首先我们知道这个是分块内存,所以说我们可以申明块的结构和存储一堆块的数组结构.
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数组的第一个元素(这里偷懒了,只申请了一个块)
这里有代码,但是被ban了
这里是用最佳适应算法,如果一个块是最小的,就要把这个块放在第一个位置,然后把其他的块都往后移动一格.
这里有代码,但是被ban了
如果不是最小的,就找到最适合这个块放置的位置,找到位置就是前面比我小,后面比我大,后面的先往后移动一位,这个块就放在这个空出来的位置上.
这里有代码,但是被ban了
最后先判断一下有没有越界,没有越界就继续做,如果越界的话就要继续申请物理块然后把块页转化信息写进页表中.
这里有代码,但是被ban了
接着就是到达最后了,最后的情况就是这个是最大的块,就直接插入到最后一个.反正插入到最后一个是最简单的,直接默默地走在最后一个即可.
接着就是free,我们需要通过二分查找找到传进来的free地址是否能和某一个块的首地址匹配上.
这里有代码,但是被ban了
如果匹配不上就panic,如果匹配上了就做接下来的free操作:
这里有代码,但是被ban了
首先第一步,看看free之后是不是能够空出一整个页来,如果能空出一整页的话,这一整页就可以释放了,接着就是把这一个内存块从数组中抽出来,后面的元素一一往前移动.
由于数据集太弱了,狗都能过,所以说不代表我这个方法一定正确.
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系统调用是进程管理中一个非常重要的系统调用,它主要有两大功能:
在以上程序中,父进程把flag变量赋值为0,然后fork生成一个子进程,接着通过wait函数等待子进程的退出。子进程把自己的变量flag赋值为1,然后fork生成孙子进程,接着通过wait函数等待孙子进程的退出。孙子进程给自己的变量flag赋值为2并在退出时输出信息,然后子进程退出时输出信息,最后父进程退出时输出信息。由于fork之后父子进程的数据段相互独立(同一虚拟地址对应不同的物理地址),子进程对全局变量的赋值不影响父进程全局变量的值,因此结果如下:
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_challenge1_wait
$ git checkout lab3_challenge1_wait
//继承lab3_3以及之前的答案
$ git merge lab3_3_rrsched -m "continue to work on lab3_challenge1"
注意:不同于基础实验,挑战实验的基础代码具有更大的不完整性,可能无法直接通过构造过程。 同样,不同于基础实验,我们在代码中也并未专门地哪些地方的代码需要填写,哪些地方的代码无须填写。这样,我们留给读者更大的“想象空间”。
首先第一步,我们要在do_fork函数中添加关于数据段的支持,那么在复制的时候只需要添加case DATA_SEGMENT的处理就可以.
对于代码段,我们是直接进行复制,虚拟地址直接合并的,如下面程序所示.
这里有代码,但是被ban了
就直接在子进程的虚地址转换表中添加父进程的代码段首地址和父进程的代码段首地址对应的实地址之间的映射,把父进程的实地址复制给子进程
但是对于数据段,父进程和子进程是不共享的,所以说要生成申请一个新的页给子进程.所以说虚地址是互通的,但是实地址不是互通的.改正成:
这里有代码,但是被ban了
对于等待的处理.我们首先先判断是指定一个儿子还是指定所有的儿子.
这个时候我们在process数据结构里面定义一个新的元素,这个元素就是blockmap,就是等待谁结束停止阻塞,由于一个进程可以等待多个进程,我们做一个处理,就是第26位为1代表这个进程在等待pid==26的进程结束.
所以说我们可以利用parent的结构来进行blockmap的处理,当某个进程的parent是当前进程,代表这个进程是你的儿子,所以说我们就可以指定,(blockmap一定程度上记录着儿子的信息.) 可以是blockmap |= 1<<pid
这里有代码,但是被ban了
那对于所有的进程呢?一样的的嘛,不过少了特判和break
那么对于exit也要进行改变,当一个进程结束的时候有可能会通知给其他进程.?代表这个进程是某个进程的儿子,某个进程正在等待您结束呢?用位运算就可以完成.
if (?) != 0 && proc->parent->pid == procs[i].pid && procs[i].status == BLOCKED) {
procs[i].status = READY;
insert_to_ready_queue(&procs[i]);
}
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 %d\n", 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 %d\n", i);
25 sem_V(child_sem[0]);
26 }
27 }
28 exit(0);
29 return 0;
30 }
以上程序通过信号量的增减,控制主进程和两个子进程的输出按主进程,第一个子进程,第二个子进程,主进程,第一个子进程,第二个子进程……这样的顺序轮流输出,如上面的应用预期输出如下:
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_challenge2_semaphore
$ git checkout lab3_challenge2_semaphore
//继承lab3_3以及之前的答案
$ git merge lab3_3_rrsched -m "continue to work on lab3_challenge1"
注意:不同于基础实验,挑战实验的基础代码具有更大的不完整性,可能无法直接通过构造过程。 同样,不同于基础实验,我们在代码中也并未专门地哪些地方的代码需要填写,哪些地方的代码无须填写。这样,我们留给读者更大的“想象空间”。
我觉得lab3_1比lab3_2难一点,因为3_2就是一个模拟题.
在主程序中用编号来模拟信号灯的序号,我们在程序中也同样做.
首先用一个数组来代表信号灯的值,再用一个数组来代表等待队列尾(上学期学过信号灯=值+一个等待队列.)
如果新建一个新的信号灯,那么就是初始化等待队列而已(判断初值不能为负),并且维护一个值,代表当前已经生成的信号灯的数量.(方便我们对数组的某一个元素初始化).
P操作:就是先-1,如果小于0的话,就让这个进程阻塞,放入到等待队列队首
V操作:先+1,如果等待队列不为空的话就让等待队列队首投入就绪状态.(出队)
由于process结构体有一个元素就是等待队列下一个元素,所以说我们可以进行模拟