Mit6.828 Day26~30 Lab4 PartA Multiprocessor Support and Cooperative Multitasking

Mit6.828 Day26~30 Lab4 PartA Multiprocessor Support and Cooperative Multitasking

摘要:MIT6.828 Lab4 PartA

0x01 写在前面

以下是本人有感而发的废话,可略过:

最近忙着打CTF,以及处理一些别的事情,所以Lab这边稍稍又停了几天。CTF可能还要再打一阵子,别的事情也算是有了着落。不得不感慨,时间真快啊,转眼就快九月份,想想一个多月前,自己给自己排了不少的任务,到现在也只不过完成了一半左右,但一半左右也算蛮好了,总比浑浑噩噩什么也没干来得强。这一个月的学习,让我对计算机方面的知识有了更为深刻的理解,补充了我的某些盲区,扩宽了我的知识面,在网络安全也有了更多的体悟与思考,总体而言还是有收获的。还是有很多地方应该抓紧去学习,数据结构与算法、数学、英语、剩下半本计算机组成,然后还要把专业课的知识过一过,下个学期期末结束后,就应该开始正式准备考研了。自己初步的计划是,下个学期抓紧把数据结构与算法方面的知识弄个清晰明了;把微积分、概率论好好再自己过一遍,把离散数学学一学;然后专业课搞好,不要像这个学期一般绩点爆炸了。然后其他方面,想多出去走走吧,多认识些朋友,能在安全圈多结交志同道合的师傅。

回到Lab上来,Lab4的标题为preemptive multitasking,抢占性的多任务,开始有意思的部分——进程管理。从assignment到due历时三个星期,我想看看自己能否在十五天内完成所有的任务,包括中间的HW以及材料阅读部分。开始吧,时间不多了。

0x02 Part A: Multiprocessor Support and Cooperative Multitasking

上来首先告知我们增加的文件,需要进行第一步的浏览。

Multiprocessor Support

JOS运行的CPU模型为SMP(symmetric multiprocessing, 均衡多进程),这意味着每个CPU可以得到灯亮的系统资源以及I/O总线。引导处理器(bootstrap processor,BSP),应用处理器(application processor,APs)

SMP系统中,每个CPU都有一个本地APIC。两个作用:一传送中断信号;二基于其所连接的CPU一个独一无二的标识符。

处理器通过内存映射I/O(MMIO)访问LAPIC,LAPIC被安置在一个开始于物理内存地址0xfe000000的空洞中,这个位置无法正常访问到。在虚拟内存中,该位置位于起始于MMIOBASE的4MB大小的缝隙里,我们需要去映射这块区域。

Exercise 1

这个exercise里我们要去实现pmap.c中的mmio_map_region函数。根据注释里的提示,调用boot_map_region()函数还是很好实现的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void *
mmio_map_region(physaddr_t pa, size_t size)
{
static uintptr_t base = MMIOBASE;

// Your code here:
void *ret;

size_t needsize;
uintptr_t obase = base;
needsize = ROUNDUP(size, PGSIZE);
if(base+size>MMIOLIM||base+size<MMIOBASE)
panic("mmio_map_region overflow!");

boot_map_region(kern_pgdir, base, needsize, pa, PTE_PCD|PTE_PWT|PTE_W);
base+=needsize;
ret = (void *)obase;

return ret;
//panic("mmio_map_region not implemented");
}

这边一定要注意PTE权限问题,加入PTE_W,否则将无法查找到CPU

Application Processor Bootstrap

BSP在启动APs之前需要从BIOS的MP configuration中获取对应的信息,比如CPU的数量、对应的APIC ID以及APLIC对应的MMIO的地址。这些有mp_init()函数完成

而后,boot_aps()函数将AP的入口代码复制到一个可被寻址的位置,0x7000(MPENTRY_PADDR)

再后,boot_aps()通过发送STARTUP IPS来激活每个AP,这是通过在入口代码所初始化的CS:IP地址所做到的

在这之后,AP进入到保护模式,调用mp_main()

Exercise 2

这个部分要求:

1)先阅读kern/init.c中的boot_aps()和mp_main()以及kern/mpentry.S中的汇编代码。在理解了整个控制流转移后,

2)修改kern/pmap.c中的page_init()以避免将MPENTRY_PADDR加入到free list,从而可以确保我们能够安全的复制并在相应的物理地址上运行AP的启动代码。

完成这个练习主要需要理解:MPENTRY_PADDR的位置在何处,其位置应该是低于basemem的。故修改代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
size_t i=0;
pages[i++].pp_ref=1;
for (; i < MPENTRY_PADDR/PGSIZE; i++) {
pages[i].pp_ref = 0;
pages[i].pp_link = page_free_list;
page_free_list = &pages[i];
}
extern unsigned char mpentry_start[], mpentry_end[];
size_t size = mpentry_end-mpentry_start;
size = ROUNDUP(size, PGSIZE);
for (; i < (MPENTRY_PADDR+size)/PGSIZE; i++) {
pages[i].pp_ref = 1;
}

执行完毕后如下,在check_kern_pgdir()发生panic:

Question 1

boot.S中,由于尚没有启用分页机制,所以我们能够指定程序开始执行的地方以及程序加载的地址;但是,在mpentry.S的时候,由于主CPU已经处于保护模式下了,因此是不能直接指定物理地址的,给定线性地址,映射到相应的物理地址是允许的。

Per-CPU State and Initialization

这部分有两个Exercise,一个是初始化从KSTACKTOP开始的每个CPU的栈,而后是初始化BSP的TSS和TSS描述符

我们需要注意以下的per-CPU相关的参数

1)每个CPU的内核栈。每个CPU有自己的内核栈,因为存在多个CPU陷入内核的情况,故需要每个CPU单独有一个内核栈防止发生冲突。percpu_kstacks[NCPU][KSTKSIZE]用于保存内核栈,可以查看inc/memlayout.h来了解CPU内核栈的位置;

2)每个CPU的任务状态段寄存器(TSS)和TSS描述符。cpus[i].cpu_ts用于保存TSS,对应的描述符在gdt[(GD_TSS0 >> 3) + i]里面;

3)每个CPU当前环境(进程)的指针。cpus[cpunum()].cpu_env

4)每个CPU系统寄存器。类似lcr3(),ltr(),lgdt(),lidt()的C函数必须保证执行过一次。

过完这些后,来到我们的Exercise部分:

Exercise 3

这个部分需要我们再次修改kern/pmap.c中的mem_init_mp()函数来映射每个CPU开始于KSTACKTOP的内核栈,每个栈的大小为KSTKSIZE字节外加KSTKGAP字节未映射的保护页。在完成这部分后我们的代码应该是可以通过check_kern_pgdir()的。

所谓的保护呀(guard pages)就是为了防止一个内核栈溢出去影响其它栈的一种机制。

代码如下:

1
2
3
4
5
6
7
8
9
10
uintptr_t perCpuStackStart;
for(int i=0; i < NCPU; i++){
perCpuStackStart = KSTACKTOP - i*(KSTKSIZE+KSTKGAP);
boot_map_region(kern_pgdir,
perCpuStackStart-KSTKSIZE,
KSTKSIZE,
PADDR(&percpu_kstacks[i]),
PTE_W | PTE_P);

}

我这边可以过check_kern_pgdir()但是有个未能处理的trap,emmm…先不管了:

来看下一个Exercise

Exercise 4

这个部分要求我们修改kern/trap.c中的trap_init_percpu()函数来完成对TSS和TSS描述符的初始化,以让其适用于所有的CPU,看样子上面的报错跟这个相关了。

我的代码:

1
2
3
4
5
6
7
8
9
int i = cpunum();
thiscpu->cpu_ts.ts_esp0 = KSTACKTOP - i*(KSTKSIZE + KSTKGAP);
thiscpu->cpu_ts.ts_ss0 = GD_KD;
thiscpu->cpu_ts.ts_iomb = sizeof(struct Taskstate);
gdt[(GD_TSS0 >> 3) + i] = SEG16(STS_T32A, (uint32_t) (&thiscpu->cpu_ts),
sizeof(struct Taskstate) - 1, 0);
gdt[(GD_TSS0 >> 3) + i].sd_s = 0;
ltr(GD_TSS0 + (i<<3));
lidt(&idt_pd);

Locking

我们首先要解决多CPU同时运行内核代码的竞争条件问题,这边提到,最简单的办法是使用大内核锁。大内核锁是一种全局锁,它在一个程序进入内核模式时持有,在程序返回用户模式时释放,在这种模型下,环境可以同时在多个CPU上运行于用户模式,但不超过一个环境可以运行于内核模式,任何其他尝试进入内核模式的环境将被强制等待。

kern/spinlock.h中声明了大内核锁,里面提供了lock_kernel和unlock_kernel两个函数来快速获取和释放锁,我们需要在以下四个地方提供大内核锁:

1)在i386_init()中,在BSP唤醒其他CPU前获得锁;

2)在mp_main()中,在初始化AP后获得锁,然后在sched_yield()中开始运行在这个AP中的进程;

3)在trap()中,当从用户模式中陷入时获得锁,我们可以通过检查tf_cs的低位来判断陷入是在内核模式中开始的还是在内核模式中开始的;

4)在env_run()中,恰好在切换到用户模式前释放锁。不要过早也不要过晚,否则会导致竞争条件。

Exercise 5

这个部分的Exercise修改上面提到的地方以加入大内核锁。加的代码不多,跟着提示来就可,重在理解为何要如此去添加这些加锁、释放锁的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// boot_aps()
lock_kernel();
// Starting non-boot CPUs
boot_aps();

// mp_main()
lock_kernel();
sched_yield();

// trap()
if ((tf->tf_cs & 3) == 3) {
// Trapped from user mode.
// Acquire the big kernel lock before doing any
// serious kernel work.
// LAB 4: Your code here.
lock_kernel();
assert(curenv);

// env_run()
lcr3(PADDR(curenv->env_pgdir));
unlock_kernel();
env_pop_tf(&curenv->env_tf);

Question 2

这个问题是为何有了大内核锁之后可以保证一次只有一个CPU运行在内核模式还需要多个内核栈呢?

答案很好理解,每次CPU运行退出后可能会保留一些将来有需要的信息在内核栈中,故需要多个内核栈来防止这些内容的丢失。

Round-Robin Scheduling

我们的下一个任务是去修改JOS内核从而让它可以以轮询的方式切换多个进程,轮询调度在JOS中以以下方式工作:

1)kern/sched.c中的sched_yield()用于遍历envs[]数组来获得第一个状态为RUNNABLE的进程,而后调用env_run()来跳转到这个进程;

2)需要注意的是sched_yield必须保证不能在两个不同的CPU上运行同一个进程;

3)教案为我们提供了一个新的系统调用sys_yield(),用户进程可以自发的调用sys_yield从而将自己当前所在的CPU让给别的进程。

Exercise 6

这个Exercise要求我们完成以下的工作:

1)实现上面所提到的sched_yield的功能,并且修改syscall()以捕获sys_yield();

2)在mp_main()中调用sched_yield();

3)修改kern/init.c来创造更多的进程,让它们运行于user/yield.c中

首先修改后的syscall():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
syscall(uint32_t syscallno, uint32_t a1, uint32_t a2, uint32_t a3, uint32_t a4, uint32_t a5)
{
// Call the function corresponding to the 'syscallno' parameter.
// Return any appropriate return value.
// LAB 3: Your code here.

//panic("syscall not implemented");

switch (syscallno) {
case (SYS_cputs):
sys_cputs((const char *)a1, (size_t)a2);
return 0;
case (SYS_cgetc):
return sys_cgetc();
case (SYS_getenvid):
return sys_getenvid();
case (SYS_env_destroy):
return sys_env_destroy(a1);
case (SYS_yield):
sys_yield();
return 0;
default:
return -E_INVAL;
}
}

创建多个子进程:

1
2
3
4
5
6
7
8
9
10
11
12
#if defined(TEST)
// Don't touch -- used by grading script!
ENV_CREATE(TEST, ENV_TYPE_USER);
#else
// Touch all you want.
ENV_CREATE(user_yield, ENV_TYPE_USER);
ENV_CREATE(user_yield, ENV_TYPE_USER);
ENV_CREATE(user_yield, ENV_TYPE_USER);
#endif // TEST*

// Schedule and run the first user environment!
sched_yield();

这个地方因为之前merge的冲突问题导致无法执行到教案那般,后面修改好了就行,我佛了,卡了我快一个星期!

这边最后的执行结果如下:

question 3

这个部分主要为了弄明白为何在加载了CR3寄存器中的内容后(页目录切换了)或者之前都可以进行对e的解引用。

在我们lab3实现的过程中,任务的env_pgdir是基于kern_pgdir产生的,也就是说对于UTOP上的地址映射关系在两个页表中是一样的。而e所对应的Env结构由操作系统管理,在虚拟空间地址都是UENVS-UPAGES的范围,因此在所有用户环境的映射也是一样的

question 4

这个问题主要需要我们弄明白旧环境的值被存在了哪里,存的过程在哪里发生。根据我们的理解,这个发生过程应该是在系统调用产生陷入时发生的。

用户环境进行环境切换是通过系统调用syscall(),最终通过kern/trap.c中的trap()产生异常然后陷入内核。因而中断触发会进入trapentry.S的代码入口然后调用trap(),系统会在栈上创建一个Trapframe然后赋给用户环境的env_tf从而保护用户环境寄存器。如下所示代码片段:

1
2
3
4
5
6
7
8
9
10
11
12
>_alltraps:
;ds es
push %ds
push %es
pushal #;其余寄存器

#;load DS and ES with GD_KD (不能用立即数设置段寄存器)
mov $GD_KD, %ax
mov %ax, %ds
mov %ax, %es
pushl %esp
call trap

这里我们将环境的现场全部保护起来压栈使得其结构与Trapframe一样,然后调用trap()就可以使得其作为tf被保存。

challenges部分以后有能力再搞,继续肝Part A的最后一个部分。

System Calls for Environment Creation

目前我们所有的环境都是在内核下创建的,但我们也有必要去实现由用户模式下创建环境的功能。

在unix操作系统中,存在一个fork系统调用,它可以用来复制一个跟父进程一模一样的子进程(通过复制它的整个地址空间),父进程与子进程之间的不同在于两者的进程ID(PID)不同。

在父进程中,fork返回子进程ID在子进程中,返回0。父进程子进程有自己独立的地址空间,两者对自身的修改彼此不可见。

我们会实现一个名为dumbfork.c的测试文件,其中包含了五个函数(系统调用):

1)sys_exofork()用于创建一个空白的新环境;

2)sys_env_set_status()用于给予指定的环境ENV_RUNNABLE或ENV_NOT_RUNNABLE状态;

3)sys_page_alloc()用于分配物理内存并映射到指定的环境的地址空间中的虚拟地址上;

4)sys_page_map()通过映射一块环境的地址空间到另一个环境上实现页面的复制;

5)sys_page_unmap()用于取消映射。

Exercise 7

这个Exercise要求我们去实现上面提到的五个系统调用,并且保证syscall()调用了他们,我们会使用到之前我们在pmap.c和env.c中看到的那些函数,特别强调一下envidenv()函数,在我们调用这个函数时,传递1给checkperm这个形式参数。

这边我们一个个来看吧,首先我们来实现以下sys_exofork()这个函数。

实现这个函数的关键点在于我们需要去知道如何在子进程中返回PID为0。这点我们可以通过阅读inc/lib.c中的代码获得答案:

1
2
3
4
5
6
7
8
sys_exofork(void)
{
envid_t ret;
asm volatile("int %2"
: "=a" (ret)
: "a" (SYS_exofork), "i" (T_SYSCALL));
return ret;
}

我们看到这个地方触发中断,而后应该进入trap.c中的trap_dispatch()

1
2
3
4
case (T_SYSCALL):
ret = syscall(tf->tf_regs.reg_eax, tf->tf_regs.reg_edx, tf->tf_regs.reg_ecx, tf->tf_regs.reg_ebx, tf->tf_regs.reg_edi, tf->tf_regs.reg_esi);
tf->tf_regs.reg_eax = ret;
break;

我们注意到这里的ret赋给了tf->tf_regs.reg_eax,这里设置了返回值。

再后我们通过env_run()返回用户态。

1
2
3
4
5
6
7
8
9
trap_dispatch(tf);         // <-  这里是上面的返回,返回值存在了其tf的reg_eax中

// If we made it to this point, then no other environment was
// scheduled, so we should return to the current environment
// if doing so makes sense.
if (curenv && curenv->env_status == ENV_RUNNING)
env_run(curenv);
else
sched_yield()

所以最后我们实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
sys_exofork(void)
{
// Create the new environment with env_alloc(), from kern/env.c.
// It should be left as env_alloc created it, except that
// status is set to ENV_NOT_RUNNABLE, and the register set is copied
// from the current environment -- but tweaked so sys_exofork
// will appear to return 0.

// LAB 4: Your code here.
// For child process
struct Env * cenv;
int errno;
if((errno = env_alloc(&cenv, curenv->env_id))<0){
return errno;
}

cenv->env_tf = curenv->env_tf;
cenv->env_status = ENV_NOT_RUNNABLE;

cenv->env_tf.tf_regs.reg_eax = 0; // When fork in child process
return cenv->env_id; // When fork in parent process
//panic("sys_exofork not implemented");

}

我们继续来看下一个函数sys_env_set_status(),这个函数用于给予指定的环境ENV_RUNNABLE或ENV_NOT_RUNNABLE状态,这个其实很好实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
sys_env_set_status(envid_t envid, int status)
{
// Hint: Use the 'envid2env' function from kern/env.c to translate an
// envid to a struct Env.
// You should set envid2env's third argument to 1, which will
// check whether the current environment has permission to set
// envid's status.

// LAB 4: Your code here.
// panic("sys_env_set_status not implemented");
if((status != ENV_RUNNABLE) && (status != ENV_NOT_RUNNABLE)){
return -E_INVAL;
}
struct *Env cenv;
int errno;
if((errno = envid2env(envid, &cenv, 1))<0){
return errno;
}
env->env_status=status;
return 0;
}

再看sys_page_alloc(),照着hint来走即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
static int
sys_page_alloc(envid_t envid, void *va, int perm)
{
// Hint: This function is a wrapper around page_alloc() and
// page_insert() from kern/pmap.c.
// Most of the new code you write should be to check the
// parameters for correctness.
// If page_insert() fails, remember to free the page you
// allocated!

// LAB 4: Your code here.
//panic("sys_page_alloc not implemented");
struct Env * cenv;
// Judging if the env exist or not
if(envid2env(envid, &cenv, 1)<0)
return -E_BAD_ENV;
// Juding if the va>=UTOP or va is not page-aligned
if((uintptr_t)va>UTOP||PGOFF(va))
return -INVAL;
if(!(perm & PTE_U) || !(perm & PTE_P) || (perm & (~PTE_SYSCALL))){
return -E_INVAL;
}

struct PageInfo* pg_info;
pg_info = page_alloc(0);
if(!pg_info)
return -E_NO_MEM;
if(page_insert(env->env_pgdir, pg_info, va, perm) < 0){
//page table could not be allocated
page_free(pg_info);
return -E_NO_MEM;
}
return 0;

}

继续往下看sys_page_map():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct Env *srcenv, *dstenv;
if((envid2env(srcenvid, &srcenv, 1) < 0) || (envid2env(dstenv, &dstenv, 1) < 0)){
return -E_BAD_ENV;
}
if (((uintptr_t)srcva >= UTOP) || ((uintptr_t)dstva >= UTOP) ||
(PGOFF(srcva) != 0) || (PGOFF(dstva) != 0)) {
return -E_INVAL;
}
struct PageInfo *srcpage;
pte_t * src_pte;
// get src_va pageinfo and src_ page table entry
if ((srcpage = page_lookup(srcenv->env_pgdir, srcva, &src_pte)) ==
NULL) {
return -E_INVAL;
}
// check perm
if ((perm & (~PTE_SYSCALL)) || !(perm & PTE_U) || !(perm & PTE_P)) {
return -E_INVAL;
}

// perm has PTE_W -> srcva writable
if ((perm & PTE_W) && (!((*src_pte) & PTE_W))) {
// perm has PTE_W while srcva ISN'T writable
return -E_INVAL;
}

// insert srcpage to dst_va
if (page_insert(dstenv->env_pgdir, srcpage, dstva, perm) < 0) {
return -E_NO_MEM;
}
return 0;

最后看一下sys_page_unmap():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static int
sys_page_unmap(envid_t envid, void *va)
{
// Hint: This function is a wrapper around page_remove().

// LAB 4: Your code here.
//panic("sys_page_unmap not implemented");
struct Env *env;
if (envid2env(envid, &env, true) < 0){
return -E_BAD_ENV;
}
if ((uintptr_t)va >= UTOP || PGOFF(va) != 0){
return -E_INVAL;
}
page_remove(env->env_pgdir, va);
return 0;
}

最后我们修改下syscall():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
switch (syscallno) {
case (SYS_cputs):
sys_cputs((const char *)a1, (size_t)a2);
return 0;
case (SYS_cgetc):
return sys_cgetc();
case (SYS_getenvid):
return sys_getenvid();
case (SYS_env_destroy):
return sys_env_destroy(a1);
case (SYS_yield):
sys_yield();
return 0;
case SYS_exofork:
return sys_exofork();
case SYS_env_set_status:
return sys_env_set_status((envid_t)a1, (int)a2);
case SYS_page_alloc:
return sys_page_alloc((envid_t)a1, (void*)a2, (int)a3);
case SYS_page_map:
return sys_page_map((envid_t)a1, (void*)a2, (envid_t)a3, (void*)a4, (int)a5);
case SYS_page_unmap:
return sys_page_unmap((envid_t)a1, (void*)a2);
default:
return -E_INVAL;
}

我们运行下,得到如下结果:

image-20201010213759325

至此Part A完成

0x03 可有可无的总结

因为比赛的原因加上git merge出的问题,Lab4的Part A前前后后时间跨度至少有一个半月,惭愧啊。

整个part A实现的主要是多个CPU执行、进程的轮询调度以及最后的在用户模式下创建环境。不多讲了(其实是脑子里以及一团浆糊了。

但是尽管有点懵,经过了这次的Lab后,我对主从式的多核CPU有了一定的理解,对于轮询调度,加锁有了一定的理解,最后对fork也有了之前没有的体会。

还是有收获的吧。

最后,git conflict杀我。


评论